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 <[email protected]>

1 files changed, 15 insertions, 0 deletions

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