diff options
| -rw-r--r-- | .agents/skills/pardes-9p/SKILL.md | 6 | ||||
| -rw-r--r-- | docs/fs.md | 7 | ||||
| -rw-r--r-- | src/ninep/addr.zig | 2 | ||||
| -rw-r--r-- | src/sam_edit.zig | 17 |
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 @@ -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"); |