An Edit x gives each of its searches the step budget, and a search that spends it says it took too much time

The budget was the compiled pattern's, spent over every search an x made: Edit ,x/x+/c/z/ over 100k lines ran out and failed, blamed on backtracking. Each search now starts with the whole budget, and one that spends it says regular expression search took too much time, gave up. (Not "too long": 9ns reads those words as ENAMETOOLONG.)

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

4 files changed, 25 insertions, 7 deletions

diff --git a/.agents/skills/pardes-9p/SKILL.md b/.agents/skills/pardes-9p/SKILL.md
index 0de8820a..7e1c7d98 100644
--- a/.agents/skills/pardes-9p/SKILL.md
+++ b/.agents/skills/pardes-9p/SKILL.md
@@ -295,9 +295,9 @@ refused, not silently unmatched. `^def|^ ` finds lines starting either way
 written, or just past the last `data` write): `.` is that address, not the
 selection, `/re/` searches on from its end and wraps unless `limit` is set,
 `?re?` or `-/re/` searches back, `#100,#50` fails `addresses out of order`,
-and a search that backtracks
-past a step budget (about 300 ms) fails with `regular expression search
-gave up, ...`. A failed address says
+and one search that runs past its step budget (about 300 ms; each search of
+an Edit `x` has its own) fails with `regular expression search took too
+much time, gave up`. A failed address says
 why (`no match for regexp`, `address out of range`) and leaves no address:
 `addr` reads empty and `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
diff --git a/docs/fs.md b/docs/fs.md
index 9ca5f936..5f3ef743 100644
--- a/docs/fs.md
+++ b/docs/fs.md
@@ -733,9 +733,10 @@ pattern that spans lines, `^`, `$` and `[^...]` keep mvzr's own meaning.
 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 gave up, backtracking
-past its step budget` rather
-than answer a match it is not sure of. Ordinary patterns spend a few
+about 300 ms, fails with `regular expression search took too much time,
+gave up` rather
+than answer a match it is not sure of. The budget is each search's: an
+Edit `x` over 100k lines makes 100k searches, each with its own. 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.
diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig
index c052a665..005ad593 100644
--- a/src/ninep/addr.zig
+++ b/src/ninep/addr.zig
@@ -17,7 +17,7 @@ pub const e_col_zero = "address out of range: a column counts from 1";
 pub const e_regexp = "bad regular expression";
 /// Not "took too long": 9ns reads errors by their words, and that would be
 /// ENAMETOOLONG.
-pub const e_slow = "regular expression search gave up, backtracking past its step budget";
+pub const e_slow = "regular expression search took too much time, gave up";
 pub const e_syntax = "bad address syntax";
 pub const e_order = "addresses out of order";
 
diff --git a/src/sam_edit.zig b/src/sam_edit.zig
index 113ad14f..8f7c961f 100644
--- a/src/sam_edit.zig
+++ b/src/sam_edit.zig
@@ -456,6 +456,9 @@ const Exec = struct {
     /// reaches back into what the last one took.
     fn find(ex: *Exec, rx: *regexp.Regex, from: usize, hi: usize) Failure!?regexp.Regex.Match {
         if (from > hi) return null;
+        // The budget is each search's own: an x over 100k lines makes 100k
+        // searches, none of which is the slow one.
+        rx.steps = regexp.Regex.budget;
         const m = (rx.find(ex.text, from, hi, hi) catch return fail(ex.why, "{s}", .{addr_lang.e_slow})) orelse return null;
         var start = modal.runeStart(ex.text, m.start);
         if (start < from) start = modal.runeEnd(ex.text, m.start);
@@ -694,6 +697,20 @@ fn expectEdit(text: []const u8, command: []const u8, want: []const u8) !void {
     try std.testing.expectEqualStrings(want, got);
 }
 
+test "an x over 100k lines is 100k searches, each with its own step budget" {
+    const th = @import("ninep/testing.zig");
+    const line = "x" ** 80 ++ "\n";
+    const text = try std.testing.allocator.alloc(u8, line.len * 100_000);
+    defer std.testing.allocator.free(text);
+    for (0..100_000) |k| @memcpy(text[line.len * k ..][0..line.len], line);
+    const p = try th.withFile(std.testing.allocator, text);
+    defer p.deinit();
+    const tree = @import("ninep/tree.zig");
+    const r = th.wr(p, tree.Node.of(th.serialOf(p), .ctl), "Edit ,x/x+/c/z/\n");
+    try std.testing.expectEqual(tree.Status.ok, r.reply.status);
+    try std.testing.expect(std.mem.startsWith(u8, p.panes[0].?.file.?.content, "z\nz\n"));
+}
+
 test "sam's classic commands" {
     try expectEdit("foo x foo y foo\n", ",x/foo/c/foobar/", "foobar x foobar y foobar\n");
     try expectEdit("a b\nc d\n", ",x/ /c/_/", "a_b\nc_d\n");