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]>

1 files changed, 17 insertions, 5 deletions

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);