From 890370f5479299940f505e1247c408064f789bd5 Mon Sep 17 00:00:00 2001 From: Matteo Romano Date: Mon, 12 May 2025 12:14:30 +0200 Subject: feat: add reverse grapheme iterator Closes #53 --- src/Graphemes.zig | 220 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/unicode_tests.zig | 74 +++++++++++++++++ 2 files changed, 294 insertions(+) (limited to 'src') diff --git a/src/Graphemes.zig b/src/Graphemes.zig index 5780ed4..3bff18d 100644 --- a/src/Graphemes.zig +++ b/src/Graphemes.zig @@ -7,6 +7,7 @@ const unicode = std.unicode; const CodePoint = @import("code_point").CodePoint; const CodePointIterator = @import("code_point").Iterator; +const CodePointReverseIterator = @import("code_point").ReverseIterator; s1: []u16 = undefined, s2: []u16 = undefined, @@ -70,6 +71,10 @@ pub fn iterator(graphemes: *const Graphemes, string: []const u8) Iterator { return Iterator.init(string, graphemes); } +pub fn reverseIterator(graphemes: *const Graphemes, string: []const u8) ReverseIterator { + return ReverseIterator.init(string, graphemes); +} + /// Indic syllable type. pub const Indic = enum { none, @@ -239,6 +244,221 @@ pub const Iterator = struct { } }; +pub const ReverseIterator = struct { + buf: [2]?CodePoint = .{ null, null }, + cp_iter: CodePointReverseIterator, + data: *const Graphemes, + /// Codepoint read from `cp_iter` but not returned by `previous` + pending: Pending = .{ .none = {} }, + + const Pending = union(enum) { + none: void, + /// Count of pending RI codepoints, it is an even number + ri_count: usize, + /// End of (Extend* ZWJ) sequence pending from failed GB11: !Emoji Extend* ZWJ x Emoji + extend_end: u32, + }; + + const Self = @This(); + + pub fn init(str: []const u8, data: *const Graphemes) Self { + var self: Self = .{ .cp_iter = .init(str), .data = data }; + self.advance(); + self.advance(); + return self; + } + + fn advance(self: *Self) void { + self.buf[1] = self.buf[0]; + self.buf[0] = self.cp_iter.prev(); + } + + pub fn prev(self: *Self) ?Grapheme { + if (self.buf[1] == null) return null; + + const grapheme_end: u32 = end: { + const codepoint = self.buf[1].?; + + switch (self.pending) { + // BUF: [?Any, Any] + .none => break :end codepoint.offset + codepoint.len, + .ri_count => |ri_count| { + std.debug.assert(ri_count > 0); + std.debug.assert(ri_count % 2 == 0); + + if (ri_count > 2) { + self.pending.ri_count -= 2; + + // Use the fact that all RI have length 4 in utf8 encoding + // since they are in range 0x1f1e6...0x1f1ff + // https://en.wikipedia.org/wiki/UTF-8#Encoding + return Grapheme{ + .len = 8, + .offset = @intCast(codepoint.offset + self.pending.ri_count * 4), + }; + } else { + self.pending = .{ .none = {} }; + break :end codepoint.offset + codepoint.len + 4; + } + }, + // BUF: [?Any, Extend] Extend* ZWJ + .extend_end => |extend_end| { + self.pending = .{ .none = {} }; + break :end extend_end; + }, + } + }; + + while (self.buf[0] != null) { + var state: State = .{}; + state.setXpic(); + state.unsetRegional(); + state.setIndic(); + + if (graphemeBreak( + self.buf[0].?.code, + self.buf[1].?.code, + self.data, + &state, + )) break; + + self.advance(); + + if (!state.hasIndic()) { + + // BUF: [?Any, Extend | Linker] Consonant + var indic_offset: u32 = self.buf[1].?.offset + self.buf[1].?.len; + + indic: while (true) { + if (self.buf[0] == null) { + self.pending = .{ .extend_end = indic_offset }; + return .{ + .len = @intCast(grapheme_end - indic_offset), + .offset = indic_offset, + }; + } + + const codepoint = self.buf[0].?; + + switch (self.data.indic(codepoint.code)) { + .Extend, .Linker => { + self.advance(); + continue :indic; + }, + .Consonant => { + // BUF: [Consonant, Extend | Linker] (Extend | Linker)* Consonant + indic_offset = codepoint.offset; + self.advance(); + + if (self.buf[0]) |cp1| { + state.setIndic(); + + if (graphemeBreak(cp1.code, self.buf[1].?.code, self.data, &state)) break; + + if (!state.hasIndic()) { + continue :indic; + } else { + break :indic; + } + } else { + break :indic; + } + }, + .none => { + // BUF: [Any, Extend | Linker] (Extend | Linker)* Consonant + self.pending = .{ .extend_end = indic_offset }; + return .{ + .len = @intCast(grapheme_end - indic_offset), + .offset = indic_offset, + }; + }, + } + } + } + + if (!state.hasXpic()) { + // BUF: [?Any, ZWJ] Emoji + var emoji_offset: u32 = self.buf[1].?.offset + self.buf[1].?.len; + + // Look for previous Emoji + emoji: while (true) { + if (self.buf[0] == null) { + self.pending = .{ .extend_end = emoji_offset }; + return .{ + .len = @intCast(grapheme_end - emoji_offset), + .offset = emoji_offset, + }; + } + + const codepoint = self.buf[0].?; + + if (self.data.gbp(codepoint.code) == .Extend) { + self.advance(); + continue :emoji; + } + + if (self.data.isEmoji(codepoint.code)) { + // BUF: [Emoji, Extend] (Extend* ZWJ Emoji)* + emoji_offset = codepoint.offset; + self.advance(); + + if (self.buf[0] != null and + // ZWJ = 0x200d + self.buf[0].?.code == 0x200d) + { + // BUF: [ZWJ, Emoji] (Extend* ZWJ Emoji)* + // Back at the beginning of the loop, "recursively" look for emoji + self.advance(); + continue :emoji; + } else { + // BUF: [?Any, Emoji] (Extend* ZWJ Emoji)* + break :emoji; + } + } else { + // BUF: [Any, Extend] (Extend* ZWJ Emoji)* + self.pending = .{ .extend_end = emoji_offset }; + return .{ + .len = @intCast(grapheme_end - emoji_offset), + .offset = emoji_offset, + }; + } + } + } + + if (state.hasRegional()) { + var ri_count: usize = 0; + while (self.buf[0] != null and + self.data.gbp(self.buf[0].?.code) == .Regional_Indicator) + { + ri_count += 1; + self.advance(); + } + + // Use the fact that all RI have length 4 in utf8 encoding + // since they are in range 0x1f1e6...0x1f1ff + // https://en.wikipedia.org/wiki/UTF-8#Encoding + if (ri_count == 0) { + // There are no pending RI codepoints + } else if (ri_count % 2 == 0) { + self.pending = .{ .ri_count = ri_count }; + return .{ .len = 8, .offset = grapheme_end - 8 }; + } else { + // Add one to count for the unused RI + self.pending = .{ .ri_count = ri_count + 1 }; + return .{ .len = 4, .offset = grapheme_end - 4 }; + } + } + } + + const grapheme_start = if (self.buf[1]) |codepoint| codepoint.offset else 0; + self.advance(); + return .{ + .len = @intCast(grapheme_end - grapheme_start), + .offset = grapheme_start, + }; + } +}; + // Predicates fn isBreaker(cp: u21, data: *const Graphemes) bool { // Extract relevant properties. diff --git a/src/unicode_tests.zig b/src/unicode_tests.zig index 2249007..828559a 100644 --- a/src/unicode_tests.zig +++ b/src/unicode_tests.zig @@ -219,3 +219,77 @@ test "Segmentation GraphemeIterator" { } } } + +test "Segmentation ReverseGraphemeIterator" { + const allocator = std.testing.allocator; + var file = try std.fs.cwd().openFile("data/unicode/auxiliary/GraphemeBreakTest.txt", .{}); + defer file.close(); + var buf_reader = std.io.bufferedReader(file.reader()); + var input_stream = buf_reader.reader(); + + const data = try Graphemes.init(allocator); + defer data.deinit(allocator); + + var buf: [4096]u8 = undefined; + var line_no: usize = 1; + + while (try input_stream.readUntilDelimiterOrEof(&buf, '\n')) |raw| : (line_no += 1) { + // Skip comments or empty lines. + if (raw.len == 0 or raw[0] == '#' or raw[0] == '@') continue; + + // Clean up. + var line = std.mem.trimLeft(u8, raw, "÷ "); + if (std.mem.indexOf(u8, line, " ÷\t#")) |octo| { + line = line[0..octo]; + } + // Iterate over fields. + var want = std.ArrayList(Grapheme).init(allocator); + defer want.deinit(); + + var all_bytes = std.ArrayList(u8).init(allocator); + defer all_bytes.deinit(); + + var graphemes = std.mem.splitSequence(u8, line, " ÷ "); + var bytes_index: u32 = 0; + + while (graphemes.next()) |field| { + var code_points = std.mem.splitScalar(u8, field, ' '); + var cp_buf: [4]u8 = undefined; + var cp_index: u32 = 0; + var gc_len: u8 = 0; + + while (code_points.next()) |code_point| { + if (std.mem.eql(u8, code_point, "×")) continue; + const cp: u21 = try std.fmt.parseInt(u21, code_point, 16); + const len = try unicode.utf8Encode(cp, &cp_buf); + try all_bytes.appendSlice(cp_buf[0..len]); + cp_index += len; + gc_len += len; + } + + try want.append(Grapheme{ .len = gc_len, .offset = bytes_index }); + bytes_index += cp_index; + } + + // std.debug.print("\nline {}: {s}\n", .{ line_no, all_bytes.items }); + var iter = data.reverseIterator(all_bytes.items); + + // Check. + var i: usize = want.items.len; + while (i > 0) { + i -= 1; + const want_gc = want.items[i]; + const got_gc = iter.prev() orelse { + std.debug.print("line {d} grapheme {d}: expected {any} found null\n", .{ line_no, i, want_gc }); + return error.TestExpectedEqual; + }; + std.testing.expectEqualStrings( + want_gc.bytes(all_bytes.items), + got_gc.bytes(all_bytes.items), + ) catch |err| { + std.debug.print("line {d} grapheme {d}: expected {any} found {any}\n", .{ line_no, i, want_gc, got_gc }); + return err; + }; + } + } +} -- cgit v1.2.3