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.