A regular expression search is bounded by a step budget patched into mvzr, not windows and a repeat cap

The windows returned wrong matches: a candidate reaching a window's edge was
left to the next window, half a window on, which could answer a match starting
mid-token rather than the leftmost, and addr then pointed data's next write at
the wrong bytes. The repeat cap missed mvzr's own worst case, a chain of a?,
and alternation under a repeat, each exponential inside one mvzr call the
deadline could not interrupt; and it refused ordinary s/S patterns. build.zig
now patches the fetched mvzr at build time with a step counter on its
backtracking recursion (matchPattern), so a fresh fetch keeps it and a moved
anchor stops the build; regexp.zig gives each compiled pattern a budget, about
300 ms here, and a search that spends it fails as taking too long. Windows,
the cap and their special cases are gone, and matches are exact again.

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

7 files changed, 114 insertions, 107 deletions

diff --git a/.agents/skills/pardes-9p/SKILL.md b/.agents/skills/pardes-9p/SKILL.md
index 77acade3..393b0b0f 100644
--- a/.agents/skills/pardes-9p/SKILL.md
+++ b/.agents/skills/pardes-9p/SKILL.md
@@ -147,8 +147,9 @@ is why copying one onto another is all that acme's `addr=dot`, `dot=addr` and
 `/pattern/`, `2+1`), whose regexps are mvzr's searched as sam searches:
 `^`/`$` match at any line's start and end, `.` and `[^...]` never match a
 newline, the leftmost match wins (the first alternative there, not the
-longest), `/re/` wraps unless `limit` is set, and since mvzr backtracks a
-pattern with more than four `*`/`+`/`{}` is refused. A failed address says
+longest), `/re/` wraps unless `limit` is set, and a search that backtracks
+past a step budget (about 300 ms) fails with `regular expression search
+took too long`. A failed address says
 why (`no match for regexp`, `address out of range`) and leaves no address:
 `data` refuses until the next good one, so a missed target is never
 written at the old one. Moving `dot` scrolls the pane to it. `limit` bounds a
diff --git a/build.zig b/build.zig
index f0675a70..666e792d 100644
--- a/build.zig
+++ b/build.zig
@@ -418,7 +418,37 @@ pub fn build(b: *std.Build) void {
         .root_source_file = b.path("src/web/zstbi.zig"),
     });
 
-    const mvzr_mod = b.dependency("mvzr", .{ .target = target, .optimize = optimize }).module("mvzr");
+    // mvzr backtracks with no bound on its work (its own test "do not make
+    // this test any longer": `a?` n times is 2^n steps), and pardes searches
+    // with it holding the editor. Its matcher gets a step budget, patched into
+    // the fetched source here at build time so that a fresh fetch keeps it:
+    // each entry to matchPattern, which its backtracking recurses through,
+    // spends a step, and with none left the match fails and says so
+    // (src/regexp.zig). A bump that moves the anchor stops the build.
+    const mvzr_mod = mvzr: {
+        const dep = b.dependency("mvzr", .{ .target = target, .optimize = optimize });
+        const src = std.Io.Dir.cwd().readFileAlloc(io, dep.path("src/mvzr.zig").getPath(b), b.allocator, .limited(1 << 20)) catch @panic("read mvzr");
+        const anchor = "fn matchPattern(patt: []const RegOp, sets: []const CharSet, haystack: []const u8, i_in: usize) ?OpMatch {\n";
+        const at = (std.mem.indexOf(u8, src, anchor) orelse @panic("mvzr's matchPattern changed: redo its step budget in build.zig")) + anchor.len;
+        const spend =
+            \\    if (steps_left == 0) {
+            \\        exhausted = true;
+            \\        return null;
+            \\    }
+            \\    steps_left -= 1;
+            \\
+        ;
+        const budget =
+            \\
+            \\/// pardes's patch (its build.zig): matchPattern entries left before a
+            \\/// match gives up, and whether one did. Set by the caller per search.
+            \\pub threadlocal var steps_left: u64 = std.math.maxInt(u64);
+            \\pub threadlocal var exhausted: bool = false;
+            \\
+        ;
+        const patched = b.fmt("{s}{s}{s}{s}", .{ src[0..at], spend, src[at..], budget });
+        break :mvzr b.createModule(.{ .root_source_file = b.addWriteFiles().add("mvzr.zig", patched), .target = target, .optimize = optimize });
+    };
 
     // The C heap every C library with an allocator hook is handed: the core's
     // tree-sitter and fonts, and pdf.zig's MuPDF, which is a module of its own.
diff --git a/docs/fs.md b/docs/fs.md
index c9b268b0..a2d8a9b2 100644
--- a/docs/fs.md
+++ b/docs/fs.md
@@ -288,21 +288,20 @@ the alternatives at that place mvzr takes the first that matches where sam
 takes the longest (`/gam|gamma/` finds `gam`); in a search begun in the
 middle of a line, `^` inside an alternation can match there; and in a
 pattern that spans lines, `^`, `$` and `[^...]` keep mvzr's own meaning.
-mvzr backtracks without bound (`a*a*a*a*x` over a hundred `a`s takes a
-second), and a search holds the editor, so a pattern with more than four
-repeats (`*`, `+`, `{m,n}`) is refused as `regular expression has more than
-four repeats`, a long line is searched in overlapping windows (64 KB for
-a pattern with at most one repeat, 256, 96 and 40 bytes for two, three and
-four), where a match longer than half a window can be missed, and a
-search still running after 300 ms fails with `regular expression search
-took too long`.
+mvzr backtracks without bound of its own (`a?` twenty times then twenty
+`a`s is 2^20 steps from each place it tries), and a search holds the editor, so pardes patches a
+step budget into mvzr's matcher (build.zig): a search that spends it,
+about 300 ms, fails with `regular expression search took too long` rather
+than answer a match it is not sure of. Ordinary patterns spend a few
+thousand steps; what runs out is exponential backtracking, and a quadratic
+pattern over a very long line (`\s*(\w+)\s*=` over 20 KB of letters).
 pardes has no regex engine of its own on purpose; these are its limits.
 Normal mode's `s` and `S` search a selection the same way (src/regexp.zig
 is the one place both call), so `^` there also means a line's start.
 
 An address that does not evaluate fails the write with why: `bad address
 syntax`, `no match for regexp`, `address out of range`, `bad regular
-expression` or one of the two costs above. A failed write to `addr` leaves no address at all, where acme
+expression` or `regular expression search took too long`. A failed write to `addr` leaves no address at all, where acme
 keeps the old one: until an address is written or `addr` is truncated,
 reading `addr`, and reading, writing or truncating `data` and `xdata`, fail
 with `no address: the last one written to addr failed`, so a script that
diff --git a/docs/helix-keys.md b/docs/helix-keys.md
index 087b83d0..41f9b364 100644
--- a/docs/helix-keys.md
+++ b/docs/helix-keys.md
@@ -250,9 +250,9 @@ compiles a runtime pattern with no allocator, called the way sam searches
 haystack, so `^` and `$` match at every line's start and end and `.` never
 crosses a newline, and a pattern naming `\n` runs over the whole selection.
 Where helix's `^` is only the selection's start, this is sam's. mvzr
-backtracks without bound, so the caps docs/fs.md gives for `addr` hold
-here too: more than four repeats will not compile (the selection is left
-alone) and a search past 300 ms keeps the matches it found so far.
+backtracks without bound of its own, so the step budget docs/fs.md gives
+for `addr` holds here too: a search that runs out of it (about 300 ms)
+keeps the matches it found so far.
 
 | Key | Behavior | Notes | Status |
 | --- | --- | --- | --- |
diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig
index 69e6dc77..cc7ca632 100644
--- a/src/ninep/addr.zig
+++ b/src/ninep/addr.zig
@@ -14,7 +14,6 @@ fn clip(n: usize) u32 {
 pub const e_no_match = "no match for regexp";
 pub const e_range = "address out of range";
 pub const e_regexp = "bad regular expression";
-pub const e_costly = "regular expression has more than four repeats";
 pub const e_slow = "regular expression search took too long";
 pub const e_syntax = "bad address syntax";
 
@@ -198,8 +197,8 @@ pub const Addr = struct {
             a.err = "no previous regular expression";
             return null;
         }
-        const rx = regexp_.Regex.compile(pat) catch |err| {
-            a.err = if (err == error.TooCostly) e_costly else e_regexp;
+        var rx = regexp_.Regex.compile(pat) catch {
+            a.err = e_regexp;
             return null;
         };
         const found = if (back) found: {
@@ -378,7 +377,7 @@ test "the address language, form by form" {
     for ([_][2][]const u8{
         .{ "zzz", e_syntax },         .{ "/nomatch/", e_no_match }, .{ "99", e_range },
         .{ "#999", e_range },         .{ "/a[/", e_regexp },        .{ "/(a/", e_regexp },
-        .{ "/*a/", e_regexp },        .{ "/a*b*c*d*e*/", e_costly },
+        .{ "/*a/", e_regexp },
     }) |c| {
         _ = th.wr(p, addr, "#0");
         try testing.expectEqualStrings(c[1], th.wr(p, addr, c[0]).reply.ename);
diff --git a/src/normal.zig b/src/normal.zig
index 09e06b13..da707e26 100644
--- a/src/normal.zig
+++ b/src/normal.zig
@@ -92,7 +92,8 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
     const snap = pane.sel_snap[0..pane.nsel_snap];
     var out: [Text.max_selections]modal.Selection = undefined;
     var m: usize = 0;
-    if (regexp.Regex.compile(pat)) |re| {
+    if (regexp.Regex.compile(pat)) |compiled| {
+        var re = compiled;
         var hay_all = text;
         if (for (pat) |c| {
             if (std.ascii.isUpper(c)) break false;
diff --git a/src/regexp.zig b/src/regexp.zig
index c758ee81..fe68585d 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -2,8 +2,8 @@
 //! sam searches (editors/acme/regx.c). `addr` (src/ninep/addr.zig) and
 //! normal mode's `s` and `S` (src/normal.zig) both call it.
 const std = @import("std");
+const builtin = @import("builtin");
 const mvzr = @import("mvzr");
-const hosted = @import("pardes.zig").hosted;
 
 /// A compiled pattern and how to run it.
 ///
@@ -13,39 +13,39 @@ const hosted = @import("pardes.zig").hosted;
 /// a pattern that names a newline (`\n`) runs over the whole text with its
 /// `.`s made `[^\n]`.
 ///
-/// mvzr backtracks, and has no bound on its work: `a*a*a*a*x` over a line of
-/// a hundred `a`s takes a second, and each repeat multiplies the cost by the
-/// haystack's length. The search runs with the editor's turn, so it must
-/// come back: a pattern with more than four repeats (`*`, `+`, `{}`) is
-/// refused, the more repeats the shorter the stretch of a line one mvzr
-/// call is given (a line longer than that is searched in overlapping
-/// windows), and a search that has run for 300 ms stops with `TooSlow`.
+/// mvzr backtracks, and has no bound on its work of its own: `a?` twenty
+/// times then twenty `a`s is 2^20 steps from each start, `a*a*a*a*x` over a line of a
+/// hundred `a`s a second. The search runs with the editor's turn, so it must
+/// come back: build.zig patches a step budget into mvzr's matcher, and a
+/// search that spends `budget` steps (about 300 ms here) stops with
+/// `TooSlow`, found nothing rather than something wrong.
 ///
 /// ponytail: mvzr takes the first alternative that matches, not sam's
 /// longest (`gam|gamma` finds `gam`); a search from the middle of a line lets
 /// `^` match there unless the pattern starts with it; across lines, `^`, `$`
-/// and `[^...]` keep mvzr's meaning; in a windowed line a match longer than
-/// half a window may be missed or `^` match at a window's start. A regex
-/// engine of sam's own would lift these; the user chose not to have one.
+/// and `[^...]` keep mvzr's meaning; and a quadratic pattern over a long
+/// enough line (`\s*(\w+)\s*=` over 20 KB of letters) runs out of budget. A
+/// regex engine of sam's own would lift these; the user chose not to have
+/// one.
 pub const Regex = struct {
     re: mvzr.Regex,
     /// 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.
     bol: bool,
-    /// The most bytes one mvzr call searches.
-    window: usize,
-    /// When searches with this pattern give up, in milliseconds.
-    deadline: i64,
+    /// mvzr steps left to every search with this compiled pattern together,
+    /// so that addr's backward scan and s/S's many calls share one bound.
+    steps: u64 = budget,
 
-    pub const Error = error{ Bad, TooCostly };
+    /// Timed on this machine's ReleaseSafe build: 10M steps of the worst
+    /// patterns take 45-80 ms, and a Debug build is ten times slower.
+    pub const budget: u64 = if (builtin.mode == .Debug) 4_000_000 else 32_000_000;
 
-    pub fn compile(pat: []const u8) Error!Regex {
+    pub fn compile(pat: []const u8) error{Bad}!Regex {
         if (pat.len == 0) return error.Bad;
         var buf: [256]u8 = undefined;
         var len: usize = 0;
         var spans = false;
-        var repeats: usize = 0;
         // Twice over the pattern: the first pass learns whether it names a
         // newline, which the second needs to rewrite its `.`s.
         for ([2]bool{ false, true }) |emit| {
@@ -54,7 +54,6 @@ pub const Regex = struct {
             // comes first (`[]a]` is an empty class, then `a]`); a `]` member
             // is written `\]`.
             var in_class = false;
-            var quantified = false;
             while (i < pat.len) : (i += 1) {
                 const c = pat[i];
                 var piece: []const u8 = pat[i .. i + 1];
@@ -63,58 +62,35 @@ pub const Regex = struct {
                     i += 1;
                     piece = pat[i - 1 .. i + 1];
                     if (pat[i] == 'n') spans = true;
-                    quantified = false;
                 } else if (in_class) {
                     in_class = c != ']';
                 } else if (c == '[') {
                     in_class = true;
-                    quantified = false;
-                } else if (c == '*' or c == '+' or c == '{' or (c == '?' and !quantified)) {
-                    // A lazy or possessive mark after a repeat is the same repeat.
-                    if (!emit and !quantified and c != '?') repeats += 1;
-                    quantified = c != '?';
-                } else {
-                    if (c == '.' and spans) piece = "[^\\n]";
-                    quantified = false;
+                } else if (c == '.' and spans) {
+                    piece = "[^\\n]";
                 }
                 if (!emit) continue;
                 if (len + piece.len > buf.len) return error.Bad;
                 @memcpy(buf[len..][0..piece.len], piece);
                 len += piece.len;
             }
-            if (repeats > 4) return error.TooCostly;
         }
-        // Sizes from timing mvzr: one call over a window of the worst text
-        // for its pattern (`a*a*a*a*x` over `a`s) takes under 40 ms, so the
-        // deadline is never overrun by much.
-        const window: usize = switch (repeats) {
-            0, 1 => 64 * 1024,
-            2 => 256,
-            3 => 96,
-            else => 40,
-        };
         return .{
             .re = mvzr.compile(buf[0..len]) orelse return error.Bad,
             .spans = spans,
             .bol = pat[0] == '^',
-            .window = window,
-            .deadline = nowMs() + 300,
         };
     }
 
-    fn nowMs() i64 {
-        if (comptime !hosted) return 0;
-        var ts: std.c.timespec = undefined;
-        _ = std.c.clock_gettime(.MONOTONIC, &ts);
-        return @as(i64, ts.sec) * 1000 + @divTrunc(@as(i64, ts.nsec), 1_000_000);
-    }
-
     pub const Match = struct { start: usize, end: usize };
 
     /// The first match that starts in `from..=last` and ends by `hi`, as
     /// offsets into `text`. The text before `from` still says where lines
     /// begin.
-    pub fn find(rx: *const Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
+    pub fn find(rx: *Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
+        mvzr.steps_left = rx.steps;
+        mvzr.exhausted = false;
+        defer rx.steps = mvzr.steps_left;
         var start: usize = if (rx.spans) 0 else if (std.mem.lastIndexOfScalar(u8, text[0..from], '\n')) |nl| nl + 1 else 0;
         var at = from - start;
         // `^` cannot match in the middle of a line.
@@ -125,27 +101,15 @@ pub const Regex = struct {
         while (start <= hi and start <= last) {
             const end = if (rx.spans) hi else std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
             const line = text[start..end];
-            // A line longer than a window is searched a window at a time,
-            // each overlapping the last by half; a match ending at a window's
-            // edge that is not the line's is left to the next window, whose
-            // `$` is not a false line end.
-            var lo = at -| at % @max(1, rx.window / 2);
-            while (true) {
-                if (comptime hosted) if (nowMs() > rx.deadline) return error.TooSlow;
-                const top = @min(line.len, lo + rx.window);
-                const hay = line[lo..top];
-                const pos = @max(at, lo) - lo;
-                // matchPos finds nothing at a haystack's very end, where `$`
-                // or an empty match still can.
-                const hit: ?[2]usize = if (pos < hay.len)
-                    (if (rx.re.matchPos(pos, hay)) |m| .{ lo + m.start, lo + m.end } else null)
-                else if (pos == hay.len and top == line.len and rx.re.isMatch(hay[pos..])) .{ lo + pos, lo + pos } else null;
-                if (hit) |h| if (top == line.len or h[1] < top) {
-                    if (start + h[0] > last) return null;
-                    return .{ .start = start + h[0], .end = start + h[1] };
-                };
-                if (top == line.len or (rx.bol and !rx.spans)) break;
-                lo += rx.window / 2;
+            // matchPos finds nothing at a haystack's very end, where `$` or
+            // an empty match still can.
+            const hit: ?[2]usize = if (at < line.len)
+                (if (rx.re.matchPos(at, line)) |m| .{ m.start, m.end } else null)
+            else if (at == line.len and rx.re.isMatch(line[at..])) .{ at, at } else null;
+            if (mvzr.exhausted) return error.TooSlow;
+            if (hit) |h| {
+                if (start + h[0] > last) return null;
+                return .{ .start = start + h[0], .end = start + h[1] };
             }
             if (end == hi) return null;
             start = end + 1;
@@ -166,13 +130,14 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li
         .{ .pat = "t.\\nbeta", .from = 0, .start = 8, .end = 15 },
         .{ .pat = "^", .from = 1, .start = 11, .end = 11 },
     }) |c| {
-        const rx = try Regex.compile(c.pat);
+        var rx = try Regex.compile(c.pat);
         const m = (try rx.find(text, c.from, text.len, text.len)).?;
         try std.testing.expectEqual(c.start, m.start);
         try std.testing.expectEqual(c.end, m.end);
     }
     _ = try Regex.compile("a.*a\\nq");
-    try std.testing.expect(try (try Regex.compile("zzz")).find(text, 0, text.len, text.len) == null);
+    var none = try Regex.compile("zzz");
+    try std.testing.expect(try none.find(text, 0, text.len, text.len) == null);
     try std.testing.expectError(error.Bad, Regex.compile(""));
     try std.testing.expectError(error.Bad, Regex.compile("a\\"));
 }
@@ -180,31 +145,43 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li
 test "a quoted backslash before n is no newline, and a class ends where mvzr ends it" {
     // `\\n` is a backslash then an n: the pattern stays on one line, so its
     // `.` is not made [^\n] and does match within the line.
-    const slash = try Regex.compile("a\\\\n.");
+    var slash = try Regex.compile("a\\\\n.");
     try std.testing.expect(!slash.spans);
     try std.testing.expectEqual(@as(usize, 0), (try slash.find("a\\nX", 0, 4, 4)).?.start);
     // `[\]x]` is a class of `]` and `x`: the escaped `]` does not end it,
     // so the `*` after it is a repeat and the `.` a newline's rewrite.
-    const class = try Regex.compile("[\\]x]*y.\\n");
+    var class = try Regex.compile("[\\]x]*y.\\n");
     try std.testing.expect(class.spans);
     try std.testing.expectEqual(@as(usize, 1), (try class.find("-]x]y!\nz", 0, 8, 8)).?.start);
     try std.testing.expect(try class.find("-]x]y\n\n", 0, 7, 7) == null);
     // mvzr reads `[]x]` as an empty class then `x]`, which nothing matches.
-    try std.testing.expect(try (try Regex.compile("[]x]")).find("x]", 0, 2, 2) == null);
+    var empty = try Regex.compile("[]x]");
+    try std.testing.expect(try empty.find("x]", 0, 2, 2) == null);
 }
 
-test "a pattern that would backtrack without end comes back promptly, refused or cut short" {
-    try std.testing.expectError(error.TooCostly, Regex.compile("a*a*a*a*a*x"));
-    // Four repeats over a long line of what they match: windows keep each
-    // mvzr call small, and the deadline ends the whole search.
-    var text: [20000]u8 = @splat('a');
-    for (0..20) |i| text[i * 1000 + 999] = '\n';
-    for ([_][]const u8{ "a*a*a*a*x", ".*.*.*x", ".*.*x", "(a*)*x", "(a|a)*x" }) |pat| {
-        const rx = try Regex.compile(pat);
-        const before = Regex.nowMs();
-        if (rx.find(&text, 0, text.len, text.len)) |m| {
-            try std.testing.expect(m == null);
-        } else |err| try std.testing.expectEqual(error.TooSlow, err);
-        if (comptime hosted) try std.testing.expect(Regex.nowMs() - before < 2000);
+test "a search that would backtrack without end runs out of budget, promptly" {
+    var line: [20000]u8 = @splat('a');
+    for ([_][]const u8{ "(a|ab)*c", "a*a*a*a*a*x", ".*.*.*x" }) |pat| {
+        var rx = try Regex.compile(pat);
+        try std.testing.expectError(error.TooSlow, rx.find(&line, 0, line.len, line.len));
     }
+    // As long a chain as mvzr compiles, over runs one `a` short of it: 2^20
+    // steps from every start.
+    for (0..line.len / 20) |i| line[i * 20 + 19] = 'b';
+    var chain = try Regex.compile("a?" ** 20 ++ "a" ** 20);
+    try std.testing.expectError(error.TooSlow, chain.find(&line, 0, line.len, line.len));
+}
+
+test "the match is the leftmost, however long the line" {
+    // A window cut into the identifier would find `x... =` from its middle.
+    const text = "let " ++ "x" ** 100 ++ " = 1";
+    var assign = try Regex.compile("\\s*(\\w+)\\s*=");
+    const m = (try assign.find(text, 0, text.len, text.len)).?;
+    try std.testing.expectEqual(@as(usize, 3), m.start);
+    try std.testing.expectEqual(@as(usize, 106), m.end);
+    // Repeats are not counted or capped.
+    var five = try Regex.compile("a*b*c*d*e*f");
+    const f = (try five.find("xxaabbf", 0, 7, 7)).?;
+    try std.testing.expectEqual(@as(usize, 2), f.start);
+    try std.testing.expectEqual(@as(usize, 7), f.end);
 }