A regular expression search comes back: costly patterns refused, long lines windowed, 300 ms deadline

mvzr backtracks with no bound on its work (a*a*a*a*x over a hundred a's takes a
second, each repeat multiplying by the haystack length), and a search runs holding
the editor's turn, so one pasted pattern froze the editor. pardes does not write or
vendor a regex engine, so regexp.zig bounds what it hands mvzr: more than four
repeats is refused, a line longer than a window sized from measured worst cases is
searched in half-overlapping windows, and a deadline stops the search. addr names
each failure; normal s/S keeps what it found. The prescan also stops reading an
escaped backslash before n as a newline, and ends a class where mvzr does.

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

6 files changed, 184 insertions, 53 deletions

diff --git a/.agents/skills/pardes-9p/SKILL.md b/.agents/skills/pardes-9p/SKILL.md
index a9cecaf8..330f029d 100644
--- a/.agents/skills/pardes-9p/SKILL.md
+++ b/.agents/skills/pardes-9p/SKILL.md
@@ -140,7 +140,8 @@ 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), and `/re/` wraps unless `limit` is set. A failed address says
+longest), `/re/` wraps unless `limit` is set, and since mvzr backtracks a
+pattern with more than four `*`/`+`/`{}` is refused. 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/docs/fs.md b/docs/fs.md
index 3b49105d..2c565ade 100644
--- a/docs/fs.md
+++ b/docs/fs.md
@@ -280,13 +280,21 @@ 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`.
 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` or `bad regular
-expression`. A failed write to `addr` leaves no address at all, where acme
+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
 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 f2855b3a..087b83d0 100644
--- a/docs/helix-keys.md
+++ b/docs/helix-keys.md
@@ -249,7 +249,10 @@ compiles a runtime pattern with no allocator, called the way sam searches
 (`src/regexp.zig`, shared with a pane's `addr` file): each line is its own
 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.
+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.
 
 | Key | Behavior | Notes | Status |
 | --- | --- | --- | --- |
diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig
index 347a2d11..69e6dc77 100644
--- a/src/ninep/addr.zig
+++ b/src/ninep/addr.zig
@@ -14,6 +14,8 @@ 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";
 
 pub const Addr = struct {
@@ -196,8 +198,8 @@ pub const Addr = struct {
             a.err = "no previous regular expression";
             return null;
         }
-        const rx = regexp_.Regex.compile(pat) orelse {
-            a.err = e_regexp;
+        const rx = regexp_.Regex.compile(pat) catch |err| {
+            a.err = if (err == error.TooCostly) e_costly else e_regexp;
             return null;
         };
         const found = if (back) found: {
@@ -205,7 +207,10 @@ pub const Addr = struct {
             var before: ?Range = null;
             var at: usize = 0;
             while (at <= a.text.len) {
-                const m = rx.find(a.text, at, a.text.len, a.text.len) orelse break;
+                const m = (rx.find(a.text, at, a.text.len, a.text.len) catch {
+                    a.err = e_slow;
+                    return null;
+                }) orelse break;
                 const found_range: Range = .{ .q0 = clip(m.start), .q1 = clip(m.end) };
                 if (found_range.q1 <= r.q0) before = found_range;
                 last = found_range;
@@ -215,7 +220,14 @@ pub const Addr = struct {
         } else found: {
             const hi = if (a.lim) |l| @min(@as(usize, l.q1), a.text.len) else a.text.len;
             const from = @min(@as(usize, r.q1), hi);
-            const m = rx.find(a.text, from, hi, hi) orelse (if (a.lim != null or from == 0) null else rx.find(a.text, 0, from - 1, hi)) orelse break :found null;
+            const ahead = rx.find(a.text, from, hi, hi) catch {
+                a.err = e_slow;
+                return null;
+            };
+            const m = ahead orelse (if (a.lim != null or from == 0) null else rx.find(a.text, 0, from - 1, hi) catch {
+                a.err = e_slow;
+                return null;
+            }) orelse break :found null;
             break :found Range{ .q0 = clip(m.start), .q1 = clip(m.end) };
         };
         return found orelse {
@@ -366,7 +378,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/", e_regexp },        .{ "/a*b*c*d*e*/", e_costly },
     }) |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 8c5f232d..09e06b13 100644
--- a/src/normal.zig
+++ b/src/normal.zig
@@ -110,7 +110,8 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
             var at = from;
             var piece = from; // split: where the next piece begins
             while (at < to and m < Text.max_selections) {
-                const hit_at = re.find(hay_all, at, to, to) orelse break;
+                // A search too slow to finish keeps what it found so far.
+                const hit_at = (re.find(hay_all, at, to, to) catch break) orelse break;
                 if (split) {
                     out[m] = .{ .anchor = piece, .head = hit_at.start };
                     m += 1;
@@ -127,7 +128,7 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
                 m += 1;
             }
         }
-    }
+    } else |_| {}
     if (m == 0) {
         // the text CAN move under an armed prompt (a tag chord runs a
         // builtin), and these are raw offsets into the surface as it was
diff --git a/src/regexp.zig b/src/regexp.zig
index 665e51d5..c758ee81 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -3,6 +3,7 @@
 //! normal mode's `s` and `S` (src/normal.zig) both call it.
 const std = @import("std");
 const mvzr = @import("mvzr");
+const hosted = @import("pardes.zig").hosted;
 
 /// A compiled pattern and how to run it.
 ///
@@ -11,67 +12,140 @@ const mvzr = @import("mvzr");
 /// haystack's ends, its `.` any byte), so each line is its own haystack, and
 /// 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`.
+///
 /// 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. A regex engine of sam's own would lift
-/// these; the user chose not to have one.
+/// 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.
 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,
 
-    pub fn compile(pat: []const u8) ?Regex {
-        if (pat.len == 0) return null;
-        const spans = std.mem.indexOf(u8, pat, "\\n") != null;
+    pub const Error = error{ Bad, TooCostly };
+
+    pub fn compile(pat: []const u8) Error!Regex {
+        if (pat.len == 0) return error.Bad;
         var buf: [256]u8 = undefined;
         var len: usize = 0;
-        var i: usize = 0;
-        var in_class = false;
-        while (i < pat.len) : (i += 1) {
-            const c = pat[i];
-            const piece: []const u8 = if (c == '\\') piece: {
-                if (i + 1 >= pat.len) return null;
-                i += 1;
-                break :piece pat[i - 1 .. i + 1];
-            } else if (c == '.' and spans and !in_class) "[^\\n]" else pat[i .. i + 1];
-            if (len + piece.len > buf.len) return null;
-            if (c == '[') in_class = true;
-            if (c == ']') in_class = false;
-            @memcpy(buf[len..][0..piece.len], piece);
-            len += piece.len;
+        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| {
+            var i: usize = 0;
+            // mvzr ends a class at its first unescaped `]`, even one that
+            // 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];
+                if (c == '\\') {
+                    if (i + 1 >= pat.len) return error.Bad;
+                    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;
+                }
+                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;
         }
-        return .{ .re = mvzr.compile(buf[0..len]) orelse return null, .spans = spans, .bol = pat[0] == '^' };
+        // 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) ?struct { start: usize, end: usize } {
-        if (rx.spans) {
-            const m = rx.re.matchPos(from, text[0..hi]) orelse return null;
-            return if (m.start <= last) .{ .start = m.start, .end = m.end } else null;
-        }
-        var start = if (std.mem.lastIndexOfScalar(u8, text[0..from], '\n')) |nl| nl + 1 else 0;
+    pub fn find(rx: *const Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
+        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.
-        if (rx.bol and at > 0) {
+        if (!rx.spans and rx.bol and at > 0) {
             start = (std.mem.indexOfScalarPos(u8, text[0..hi], from, '\n') orelse return null) + 1;
             at = 0;
         }
         while (start <= hi and start <= last) {
-            const end = std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
+            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 line'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 (hit) |h| {
-                if (start + h[0] > last) return null;
-                return .{ .start = start + h[0], .end = start + h[1] };
+            // 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;
             }
             if (end == hi) return null;
             start = end + 1;
@@ -92,13 +166,45 @@ 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 = Regex.compile(c.pat).?;
-        const m = rx.find(text, c.from, text.len, text.len).?;
+        const 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 std.testing.expect(Regex.compile("a.*a\\nq") != null);
-    try std.testing.expect((Regex.compile("zzz").?).find(text, 0, text.len, text.len) == null);
-    try std.testing.expect(Regex.compile("") == null);
-    try std.testing.expect(Regex.compile("a\\") == null);
+    _ = try Regex.compile("a.*a\\nq");
+    try std.testing.expect(try (try Regex.compile("zzz")).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\\"));
+}
+
+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.");
+    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");
+    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);
+}
+
+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);
+    }
 }