A search whose pattern opens with a literal jumps to where that literal is, not through every line

Finding /line 049999/ in 1171 KB took 175.5 ms (Debug), each line run through mvzr's matcher in turn. The literal prefix (none when the pattern has a | anywhere) is found with indexOfPos first and matching starts on its line: 4.44 ms.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

1 files changed, 59 insertions, 0 deletions

diff --git a/src/regexp.zig b/src/regexp.zig
index dd2e7157..695f2b87 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -35,6 +35,11 @@ const Compiled = mvzr.SizedRegex(max_ops, 64);
 
 pub const Regex = struct {
     re: Compiled,
+    /// The literal every match starts with, when the pattern opens with one
+    /// (`line 049`, `foo` in `foo.*bar`): a search goes straight to where it
+    /// occurs rather than trying mvzr at every line.
+    lit: [32]u8 = undefined,
+    lit_len: u8 = 0,
     /// The pattern names a newline: it runs over the whole text.
     spans: bool,
     /// The pattern starts with `^`: a search begun mid-line skips the line.
@@ -53,6 +58,22 @@ pub const Regex = struct {
     /// `Anchor`: a pattern that names a newline has `^` other than first,
     /// or `$` other than just before a `\n`, which mvzr would read as the
     /// ends of the whole text and so never match where sam would.
+    /// The plain characters a pattern opens with, each of which every match
+    /// must start with: up to the first metacharacter, less the last one
+    /// when a quantifier makes it optional or repeated.
+    fn literalPrefix(pat: []const u8, out: *[32]u8) u8 {
+        // ponytail: any `|` and there is none (a match may start with
+        // another branch); a top-level-only check would keep `a(b|c)`'s.
+        if (std.mem.indexOfScalar(u8, pat, '|') != null) return 0;
+        var n: usize = 0;
+        while (n < pat.len and n < out.len) : (n += 1) {
+            if (std.mem.indexOfScalar(u8, "\\^$.[]()|*+?{}", pat[n]) != null) break;
+            out[n] = pat[n];
+        }
+        if (n < pat.len and std.mem.indexOfScalar(u8, "*?{", pat[n]) != null) n -|= 1;
+        return @intCast(n);
+    }
+
     pub fn compile(pat: []const u8) error{ Bad, Anchor, TooLong }!Regex {
         if (pat.len == 0) return error.Bad;
         // mvzr takes `^` only at its pattern's start, so `^def|^ ` (a `^`
@@ -103,7 +124,11 @@ pub const Regex = struct {
                 len += piece.len;
             }
         }
+        var lit: [32]u8 = undefined;
+        const lit_len = if (spans) 0 else literalPrefix(pat, &lit);
         return .{
+            .lit = lit,
+            .lit_len = lit_len,
             .re = Compiled.compile(buf[0..len]) orelse {
                 // Too long, or malformed: told apart by trying it with room.
                 if (mvzr.SizedRegex(4 * max_ops, 256).compile(buf[0..len]) != null) return error.TooLong;
@@ -195,6 +220,24 @@ pub const Regex = struct {
             at = 0;
         }
         while (start <= hi and start <= last) {
+            // A pattern that opens with a literal matches only where it
+            // occurs: on to the line where it next does.
+            if (rx.lit_len > 0 and !rx.spans) {
+                const q = std.mem.indexOfPos(u8, text[0..hi], start + at, rx.lit[0..rx.lit_len]) orelse return null;
+                if (q > last) return null;
+                if (q > start + at) {
+                    const line_start = if (std.mem.lastIndexOfScalar(u8, text[0..q], '\n')) |nl| nl + 1 else 0;
+                    if (line_start > start) {
+                        start = line_start;
+                        at = q - line_start;
+                    } else at = q - start;
+                    if (rx.bol and at > 0) {
+                        start = (std.mem.indexOfScalarPos(u8, text[0..hi], q, '\n') orelse return null) + 1;
+                        at = 0;
+                        continue;
+                    }
+                }
+            }
             const end = if (rx.spans) hi else std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
             const line = text[start..end];
             // matchPos finds nothing at a haystack's very end, where `$` or
@@ -252,6 +295,22 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li
     try std.testing.expectError(error.Bad, Regex.compile("a\\"));
 }
 
+test "a pattern opening with a literal finds what a search from each line finds" {
+    const text = "alpha beta\nbeta gamma\ngamma alpha\nfoo line 049999 x\n";
+    for ([_][]const u8{ "beta", "gam+a", "line 049999", "alph?a", "a.*a", "^gamma", "o+", "h$|zz", "beta|x" }) |pat| {
+        var fast = try Regex.compile(pat);
+        var slow = try Regex.compile(pat);
+        slow.lit_len = 0;
+        var from: usize = 0;
+        while (from < text.len) : (from += 1) {
+            const a = try fast.find(text, from, text.len, text.len);
+            const b = try slow.find(text, from, text.len, text.len);
+            try std.testing.expectEqual(b == null, a == null);
+            if (a) |m| try std.testing.expectEqual(b.?.start, m.start);
+        }
+    }
+}
+
 test "a pattern past 64 characters compiles, and one past the limit says so" {
     var long = try Regex.compile("a" ** 200);
     const text = "x" ++ "a" ** 200 ++ "\n";