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]>

2 files changed, 50 insertions, 3 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();
diff --git a/src/regexp.zig b/src/regexp.zig
index 575e6861..86132f60 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -47,6 +47,14 @@ pub const Regex = struct {
     /// mvzr steps left to every search with this compiled pattern together,
     /// so that addr's backward scan and s/S's many calls share one bound.
     steps: u64 = budget,
+    /// Where `find` last learned a line's start in a text (by its address
+    /// and length): the line holding `at` starts at `start`. A backward
+    /// search asks again at each match along a line, and looking back to
+    /// the line's start from the top each time was quadratic on a long one.
+    line_hint: struct { ptr: usize = 0, len: usize = 0, at: usize = 0, start: usize = 0 } = .{},
+    /// ...and where a line learned to end: the line from `start` ends at
+    /// `end` (its newline, or `hi`), asked again at each match along it.
+    end_hint: struct { ptr: usize = 0, len: usize = 0, start: usize = 0, hi: usize = 0, end: usize = 0 } = .{},
 
     /// Timed on this machine's ReleaseSafe build: 10M steps of the worst
     /// patterns take 45-80 ms, and a Debug build is ten times slower.
@@ -324,6 +332,28 @@ pub const Regex = struct {
 
     pub const Match = struct { start: usize, end: usize };
 
+    /// Where the line from `start` ends (its newline, else `hi`), `at` on
+    /// it: known when asked before of this line of this text.
+    fn lineEnd(rx: *Regex, text: []const u8, start: usize, at: usize, hi: usize) usize {
+        const h = rx.end_hint;
+        if (h.ptr == @intFromPtr(text.ptr) and h.len == text.len and h.start == start and h.hi == hi and at <= h.end) return h.end;
+        // No newline between the line's start and `at`: the look starts there.
+        const end = std.mem.indexOfScalarPos(u8, text[0..hi], at, '\n') orelse hi;
+        rx.end_hint = .{ .ptr = @intFromPtr(text.ptr), .len = text.len, .start = start, .hi = hi, .end = end };
+        return end;
+    }
+
+    /// Where the line holding `from` starts, looking back only to where
+    /// the last call learned one in this text.
+    fn lineStart(rx: *Regex, text: []const u8, from: usize) usize {
+        const h = rx.line_hint;
+        const known = h.ptr == @intFromPtr(text.ptr) and h.len == text.len and h.at <= from;
+        const lo = if (known) h.at else 0;
+        const s = if (std.mem.lastIndexOfScalar(u8, text[lo..from], '\n')) |nl| lo + nl + 1 else if (known) h.start else 0;
+        rx.line_hint = .{ .ptr = @intFromPtr(text.ptr), .len = text.len, .at = from, .start = s };
+        return s;
+    }
+
     /// The first match that starts in `from..=last` and ends by `hi`, as
     /// offsets into `text`. The text before `from` still says where lines
     /// begin.
@@ -345,7 +375,7 @@ pub const Regex = struct {
             }
             return null;
         }
-        var start: usize = if (rx.spans) 0 else if (std.mem.lastIndexOfScalar(u8, text[0..from], '\n')) |nl| nl + 1 else 0;
+        var start: usize = if (rx.spans) 0 else rx.lineStart(text, from);
         var at = from - start;
         // `^` cannot match in the middle of a line.
         if (!rx.spans and rx.bol and at > 0) {
@@ -359,7 +389,9 @@ pub const Regex = struct {
                 const q = std.mem.indexOfPos(u8, text[0..hi], start + at, rx.lit[0..rx.lit_len]) orelse return null;
                 if (q > last) return null;
                 if (q > start + at) {
-                    const line_start = if (std.mem.lastIndexOfScalar(u8, text[0..q], '\n')) |nl| nl + 1 else 0;
+                    // `start` begins a line and `start + at` is on it: the
+                    // look back ends there.
+                    const line_start = if (std.mem.lastIndexOfScalar(u8, text[start + at .. q], '\n')) |nl| start + at + nl + 1 else start;
                     if (line_start > start) {
                         start = line_start;
                         at = q - line_start;
@@ -371,7 +403,7 @@ pub const Regex = struct {
                     }
                 }
             }
-            const end = if (rx.spans) hi else std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
+            const end = if (rx.spans) hi else rx.lineEnd(text, start, start + at, hi);
             const line = text[start..end];
             // matchPos finds nothing at a haystack's very end, where `$` or
             // an empty match still can.