An Edit text block is found in linear time: only a . line is parsed again

Finding where an Edit block ends parsed the whole block again for every
line, copying it into the scratch arena each time: a 10k-line $a block
took minutes and tens of GB. sam_edit.waitsFor says what the block waits
for, and while that is a text block's . line, only such a line is parsed
again (editEnd, shared by Messages and completeEnd), its copy freed. A
10k-line block now takes well under a second and 50 MB of scratch.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

2 files changed, 64 insertions, 10 deletions

diff --git a/src/ninep/ctl.zig b/src/ninep/ctl.zig
index 2a265da1..19ca949e 100644
--- a/src/ninep/ctl.zig
+++ b/src/ninep/ctl.zig
@@ -113,20 +113,40 @@ const Messages = struct {
         const edit = "Edit";
         if (!std.mem.startsWith(u8, first, edit) or (first.len > edit.len and first[edit.len] != ' ' and first[edit.len] != '\t'))
             return first;
-        const sam = @import("../sam_edit.zig");
-        while (m.at < m.data.len and sam.needsMore(m.p.scratch.allocator(), std.mem.trim(u8, m.data[start..end], " \t\r")[edit.len..])) {
-            end = std.mem.indexOfScalarPos(u8, m.data, m.at, '\n') orelse m.data.len;
-            m.at = end + 1;
-        }
+        end = editEnd(m.p, m.data, start, end, true).?;
+        m.at = end + 1;
         return std.mem.trim(u8, m.data[start..end], " \t\r");
     }
 };
 
+/// Where the Edit block whose first line is `data[start..first_end]` ends:
+/// the end of its last line, taking the lines after it while its `{`
+/// group or a/c/i text block is open. Out of lines, the end of `data` when
+/// `to_end` (a write run whole), else null (wait for more). Only a line
+/// that could end what is open is parsed again with all before it: within
+/// a text block, just a `.` line. The arena copy of each parse is freed.
+fn editEnd(p: *Pardes, data: []const u8, start: usize, first_end: usize, to_end: bool) ?usize {
+    const sam = @import("../sam_edit.zig");
+    const edit = "Edit";
+    const arena = p.scratch.allocator();
+    var end = first_end;
+    var wait = sam.waitsFor(arena, std.mem.trim(u8, data[start..end], " \t\r")[edit.len..]);
+    while (wait != .none) {
+        if (end >= data.len) return if (to_end) data.len else null;
+        const next = std.mem.indexOfScalarPos(u8, data, end + 1, '\n') orelse
+            (if (to_end) data.len else return null);
+        const line = std.mem.trim(u8, data[end + 1 .. next], " \t\r");
+        end = next;
+        if (wait == .text and !std.mem.eql(u8, line, ".")) continue;
+        wait = sam.waitsFor(arena, std.mem.trim(u8, data[start..end], " \t\r")[edit.len..]);
+    }
+    return end;
+}
+
 /// How much of `data` is whole messages, as `Messages` reads them: lines
 /// ended by a newline, an Edit block only once it closes. The rest waits
 /// for more (tree.Open.pending).
 pub fn completeEnd(p: *Pardes, data: []const u8) usize {
-    const sam = @import("../sam_edit.zig");
     const edit = "Edit";
     var whole: usize = 0;
     var at: usize = 0;
@@ -134,10 +154,8 @@ pub fn completeEnd(p: *Pardes, data: []const u8) usize {
         const start = at;
         var end = nl;
         const first = std.mem.trim(u8, data[start..end], " \t\r");
-        if (std.mem.startsWith(u8, first, edit) and (first.len == edit.len or first[edit.len] == ' ' or first[edit.len] == '\t')) {
-            while (sam.needsMore(p.scratch.allocator(), std.mem.trim(u8, data[start..end], " \t\r")[edit.len..]))
-                end = std.mem.indexOfScalarPos(u8, data, end + 1, '\n') orelse return whole;
-        }
+        if (std.mem.startsWith(u8, first, edit) and (first.len == edit.len or first[edit.len] == ' ' or first[edit.len] == '\t'))
+            end = editEnd(p, data, start, end, false) orelse return whole;
         at = end + 1;
         whole = at;
     }
@@ -1523,3 +1541,20 @@ test "Repl with no such language names a few whole, and where the rest are" {
     try testing.expect(std.mem.indexOf(u8, refused.reply.ename, "Repl: no language \"zzlang\"; - or one like zig ada bash c c_sharp clojure (") != null);
     try testing.expect(std.mem.indexOf(u8, refused.reply.ename, " more: docs/tags.md, Repl)") != null);
 }
+
+test "a 10k-line Edit text block is taken in linear time and memory" {
+    const gpa = testing.allocator;
+    const p = try withFile(gpa, "x\n");
+    defer p.deinit();
+    var block: std.ArrayList(u8) = .empty;
+    defer block.deinit(gpa);
+    try block.appendSlice(gpa, "Edit $a\n");
+    for (0..10_000) |i| try block.print(gpa, "line {d} of the block {{ with a brace }}\n", .{i});
+    try block.appendSlice(gpa, ".\n");
+    const started = std.Io.Clock.awake.now(std.testing.io);
+    try testing.expectEqual(Status.ok, wr(p, Node.of(serialOf(p), .ctl), block.items).reply.status);
+    const took = started.durationTo(std.Io.Clock.awake.now(std.testing.io)).toNanoseconds();
+    try testing.expect(took < std.time.ns_per_s);
+    try testing.expect(p.scratch.queryCapacity() < 50 * 1024 * 1024);
+    try testing.expectEqual(@as(usize, 10_001), std.mem.count(u8, p.panes[0].?.file.?.content, "\n"));
+}
diff --git a/src/sam_edit.zig b/src/sam_edit.zig
index 95d59a9d..604e2b31 100644
--- a/src/sam_edit.zig
+++ b/src/sam_edit.zig
@@ -92,6 +92,25 @@ pub fn run(arena: std.mem.Allocator, text: []const u8, dot: Range, name: []const
 /// Whether `command` stops inside a `{` group or an `a`, `c` or `i` text
 /// block still waiting for its `.` line: a writer of lines (a ctl, exec)
 /// hands an Edit the lines after it until it does not.
+/// What an Edit command still waits for: nothing, the `.` line that ends
+/// an a, c or i text block, or the `}` of a group.
+pub const Wait = enum { none, text, group };
+
+/// As `needsMore`, saying which: while a text block is open only a `.`
+/// line can end it, so a caller need not parse the block again for every
+/// line of text in it (ninep/ctl.zig, editEnd), which was quadratic.
+pub fn waitsFor(arena: std.mem.Allocator, command: []const u8) Wait {
+    var why: Why = .{};
+    const src = std.fmt.allocPrint(arena, "{s}\n", .{command}) catch return .none;
+    defer arena.free(src);
+    var ps: Parser = .{ .arena = arena, .src = src, .why = &why };
+    while (true) {
+        const c = ps.parse(0) catch
+            return if (ps.open_text) .text else if (std.mem.eql(u8, why.text(), "unmatched `{'")) .group else .none;
+        if (c == null) return if (ps.open_text) .text else .none;
+    }
+}
+
 pub fn needsMore(arena: std.mem.Allocator, command: []const u8) bool {
     var why: Why = .{};
     const src = std.fmt.allocPrint(arena, "{s}\n", .{command}) catch return false;