From 8640107e29a940d50a5eef0dc7d12689a515d856 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 5 Nov 2026 11:02:29 -0300 Subject: text journal, the primitive: File.replace(off, len, bytes) puts an edit in the text's own buffer (its tail moved with @memmove), the buffer grown by an eighth when it must be (State.cap), and moves its line index in place from the edit on (shiftIndex, State.line_cap), so a key, a backspace and a 9P write cost their bytes and what follows them, never a copy of the text (on the 50k-line file, Debug, medians against the base run beside it: edit-char 1105 -> 420 us, edit-twin 930 -> 433, body-2m 8.6 -> 4.7 ms, body-appends 173 -> 79 ms); setContent is the same edit with the caller's whole new text taken as the buffer; a replica's core (its allocator an epoch's, rollback.isEpoch) and a text a join still sends (memory.isPinned) keep their bytes, the edit putting a new buffer in their place as every edit did, so the rollback copy, its pins and the join's blobs work as they were; a pane's event readers hear an edit's span found from the edit (events.editSpan), the one diffSpan found from two texts; tests: 'edited line index equals a rebuilt one' becomes 'a line index shifted in place equals a rebuilt one' (editedLineStarts goes), 'an edit's span is where the texts before and after it differ' is new, and the panes test of history storage counts one allocation less for a redo (the index moves in place) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/ninep/events.zig | 109 +++++++++++++++++++++++++++++++-------------------- src/ninep/pane.zig | 6 +-- 2 files changed, 68 insertions(+), 47 deletions(-) (limited to 'src/ninep') diff --git a/src/ninep/events.zig b/src/ninep/events.zig index d77cc65a..e0a67ad4 100644 --- a/src/ninep/events.zig +++ b/src/ninep/events.zig @@ -550,51 +550,76 @@ pub const flag_chorded: u32 = 8; pub const Span = struct { at: u32, removed: u32, inserted: u32 }; -pub fn diffSpan(old: []const u8, new: []const u8) Span { - const both = @min(old.len, new.len); - const stride = 64; - var head: usize = 0; - while (head + stride <= both and - std.mem.eql(u8, old[head..][0..stride], new[head..][0..stride])) head += stride; - while (head < both and old[head] == new[head]) head += 1; - var tail: usize = 0; - const rest = both - head; - while (tail + stride <= rest and std.mem.eql( - u8, - old[old.len - tail - stride ..][0..stride], - new[new.len - tail - stride ..][0..stride], - )) tail += stride; - while (tail < rest and old[old.len - 1 - tail] == new[new.len - 1 - tail]) tail += 1; - return .{ - .at = @intCast(head), - .removed = @intCast(old.len - tail - head), - .inserted = @intCast(new.len - tail - head), - }; -} - -pub fn noteReplace(p: *Pardes, id: usize, on_tag: bool, old: []const u8, new: []const u8) void { +/// What an edit about to be made changes, told to the pane's event +/// readers: the `len` bytes of `old` at `off` replaced by `bytes`, as the +/// span the texts before and after it differ in (its ends grown past the +/// edit's as far as they agree), found from the edit, never the new text. +pub fn noteEdit(p: *Pardes, id: usize, on_tag: bool, old: []const u8, off: usize, len: usize, bytes: []const u8) void { const pane = p.panes[id] orelse return; if (pane.fs.readers == 0) return; - const span = diffSpan(old, new); + const span = editSpan(old, off, len, bytes); if (span.removed == 0 and span.inserted == 0) return; - if (span.removed > 0) noteAction( - p, - id, - if (on_tag) .tag_delete else .body_delete, - span.at, - span.at + span.removed, - 0, - "", - ); - if (span.inserted > 0) noteAction( - p, - id, - if (on_tag) .tag_insert else .body_insert, - span.at, - span.at + span.inserted, - 0, - new[span.at..][0..span.inserted], - ); + if (span.removed > 0) noteAction(p, id, if (on_tag) .tag_delete else .body_delete, span.at, span.at + span.removed, 0, ""); + if (span.inserted > 0) noteAction(p, id, if (on_tag) .tag_insert else .body_insert, span.at, span.at + span.inserted, 0, bytes[span.at - off ..][0..span.inserted]); +} + +/// `noteEdit` for a text replaced whole by `new`. +pub fn noteReplace(p: *Pardes, id: usize, on_tag: bool, old: []const u8, new: []const u8) void { + noteEdit(p, id, on_tag, old, 0, old.len, new); +} + +fn editSpan(old: []const u8, off: usize, len: usize, bytes: []const u8) Span { + const n = old.len - len + bytes.len; + const New = struct { + old: []const u8, + off: usize, + len: usize, + bytes: []const u8, + fn at(t: @This(), i: usize) u8 { + if (i < t.off) return t.old[i]; + if (i < t.off + t.bytes.len) return t.bytes[i - t.off]; + return t.old[i - t.bytes.len + t.len]; + } + }; + const new: New = .{ .old = old, .off = off, .len = len, .bytes = bytes }; + const both = @min(old.len, n); + var head = off; + while (head < both and old[head] == new.at(head)) head += 1; + const rest = both - head; + var tail = @min(old.len - off - len, rest); + while (tail < rest and old[old.len - 1 - tail] == new.at(n - 1 - tail)) tail += 1; + return .{ .at = @intCast(head), .removed = @intCast(old.len - tail - head), .inserted = @intCast(n - tail - head) }; +} + +test "an edit's span is where the texts before and after it differ" { + const reference = struct { + fn span(old: []const u8, new: []const u8) Span { + const both = @min(old.len, new.len); + var head: usize = 0; + while (head < both and old[head] == new[head]) head += 1; + var tail: usize = 0; + while (tail < both - head and old[old.len - 1 - tail] == new[new.len - 1 - tail]) tail += 1; + return .{ .at = @intCast(head), .removed = @intCast(old.len - tail - head), .inserted = @intCast(new.len - tail - head) }; + } + }.span; + var prng = std.Random.DefaultPrng.init(3); + const r = prng.random(); + var old: [24]u8 = undefined; + var new: [48]u8 = undefined; + var bytes: [24]u8 = undefined; + for (0..20000) |_| { + const old_len = r.uintAtMost(usize, old.len); + for (old[0..old_len]) |*c| c.* = "ab"[r.uintLessThan(usize, 2)]; + const off = r.uintAtMost(usize, old_len); + const len = r.uintAtMost(usize, old_len - off); + const n = r.uintAtMost(usize, bytes.len); + for (bytes[0..n]) |*c| c.* = "ab"[r.uintLessThan(usize, 2)]; + @memcpy(new[0..off], old[0..off]); + @memcpy(new[off..][0..n], bytes[0..n]); + @memcpy(new[off + n ..][0 .. old_len - off - len], old[off + len .. old_len]); + const new_len = old_len - len + n; + try std.testing.expectEqual(reference(old[0..old_len], new[0..new_len]), editSpan(old[0..old_len], off, len, bytes[0..n])); + } } /// Records ` ` for a pane a diff --git a/src/ninep/pane.zig b/src/ninep/pane.zig index 289639e9..ab4b2d7d 100644 --- a/src/ninep/pane.zig +++ b/src/ninep/pane.zig @@ -300,14 +300,10 @@ pub fn spliceBody(p: *Pardes, pane: *Pane, q0: usize, q1: usize, bytes: []const // An empty range deleted, or a range replaced by what it holds: no // edit, so no undo step and no new revision. if (std.mem.eql(u8, f.content[lo..hi], bytes[0..take])) return take; - const new = p.gpa.alloc(u8, f.content.len - (hi - lo) + take) catch return null; - @memcpy(new[0..lo], f.content[0..lo]); - @memcpy(new[lo..][0..take], bytes[0..take]); - @memcpy(new[lo + take ..], f.content[hi..]); const join = pane.fs.joined == f.revision; pane.fs.joined = null; if (!pane.fs.nomark and !join) panes.File.pushUndo(p, pane); - panes.File.setContentSpan(p, f, new, .{ .head = lo, .tail = f.content.len - hi }); + if (!panes.File.replace(p, f, lo, hi - lo, bytes[0..take])) return null; return take; } -- cgit v1.3