From c8a3ecc3bcb36f0259f4d8ad2e0cdfcdc3183c9f Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Mon, 28 Sep 2026 12:39:43 -0300 Subject: 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 --- src/ninep/addr.zig | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'src/ninep/addr.zig') 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); -- cgit v1.3