Merge commit 'b5d955f' into develop-next

3 files changed, 299 insertions, 3 deletions

diff --git a/CONTRIBUTORS.md b/CONTRIBUTORS.md
index c42cb8b..530c921 100644
--- a/CONTRIBUTORS.md
+++ b/CONTRIBUTORS.md
@@ -18,3 +18,5 @@ Jonathan Raphaelson <jon@accidental.cc>
 Sam Atman <atmanistan@gmail.com>
 
 lch361 <author@lch361.net>
+
+Matteo Romano <mr.matteo.romano.02@gmail.com>
diff --git a/src/Graphemes.zig b/src/Graphemes.zig
index 1f67fc6..0338c04 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,
@@ -182,6 +187,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.
@@ -201,7 +421,7 @@ pub const State = struct {
         self.bits |= 1;
     }
     fn unsetXpic(self: *State) void {
-        self.bits ^= 1;
+        self.bits &= ~@as(u3, 1);
     }
 
     // Regional Indicatior (flags)
@@ -212,7 +432,7 @@ pub const State = struct {
         self.bits |= 2;
     }
     fn unsetRegional(self: *State) void {
-        self.bits ^= 2;
+        self.bits &= ~@as(u3, 2);
     }
 
     // Indic Conjunct
@@ -223,7 +443,7 @@ pub const State = struct {
         self.bits |= 4;
     }
     fn unsetIndic(self: *State) void {
-        self.bits ^= 4;
+        self.bits &= ~@as(u3, 4);
     }
 };
 
diff --git a/src/unicode_tests.zig b/src/unicode_tests.zig
index 8b02e98..0204b92 100644
--- a/src/unicode_tests.zig
+++ b/src/unicode_tests.zig
@@ -175,6 +175,80 @@ 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;
+            };
+        }
+    }
+}
+
 test "Segmentation Word Iterator" {
     const allocator = std.testing.allocator;
     var file = try std.fs.cwd().openFile("data/unicode/auxiliary/WordBreakTest.txt", .{});