From 4020d55aca63f2ba0b3d9bf580f36b0f4ee66f43 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 30 Sep 2026 12:56:16 -0300 Subject: A backward search along one long line takes time in the line's length, not its square: ?a? over 117 KB goes from 6.4 s to 0.03 s The 9P fuzzer (seed 124) hung a session for over 5 s on `?a?` in a 117 KB file of one line. A backward search is every forward match up to the limit, so Regex.find ran once per match. Each call looked back from its start to the line's start, and forward to the line's end, over the whole line each time. That is quadratic, and the step budget, which counts only mvzr's steps, never saw it. find now keeps where it last learned a line starts and ends in the same text, and looks back only to there. The literal prefix's look back stops at the known part of the line. Co-Authored-By: Claude Opus 5.5 --- src/ninep/addr.zig | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'src/ninep') diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig index 9674a323..df2cfaf0 100644 --- a/src/ninep/addr.zig +++ b/src/ninep/addr.zig @@ -384,6 +384,21 @@ test "an address is evaluated from the current one, as acme's are" { try testing.expectEqualStrings(e_order, th.wr(q, qaddr, "/a/,/b/").reply.ename); } +test "a backward search along one long line takes time in its length, not its square" { + const gpa = testing.allocator; + const line = try gpa.alloc(u8, 7 * 16800); + defer gpa.free(line); + for (0..16800) |i| @memcpy(line[i * 7 ..][0..7], "answer "); + const p = try th.withFile(gpa, line); + defer p.deinit(); + const t0 = std.Io.Timestamp.now(testing.io, .awake); + try testing.expectEqual(Status.ok, th.wr(p, Node.of(th.serialOf(p), .addr), "?a?").reply.status); + // Quadratic, it took seconds (6.4 s through 9P in Debug); linear, a + // few milliseconds. + const took = t0.durationTo(std.Io.Timestamp.now(testing.io, .awake)).toNanoseconds(); + try testing.expect(took < std.time.ns_per_s); +} + test "an alternation anchoring some branches and not others is refused with why, a $ not counting" { const p = try th.withFile(testing.allocator, "def\nfoo\n"); defer p.deinit(); -- cgit v1.3