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/File.zig | 278 ++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 197 insertions(+), 81 deletions(-) (limited to 'src/File.zig') diff --git a/src/File.zig b/src/File.zig index 94e211a1..7aac4cb9 100644 --- a/src/File.zig +++ b/src/File.zig @@ -141,13 +141,19 @@ pub const State = struct { /// What the replay digest leaves out (src/walk.zig): what is made again /// from the text whenever it is wanted. pub const replica = .{ - .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, - // Replaced whole at every edit (setContentSpan), never written. + .derived = .{ "cap", "line_starts", "line_cap", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, + // Written in place by `replace`, but never in a replica's core or + // while a join sends them (`keepsBytes`): there an edit puts a new + // buffer in their place. .blob = .{ "content", "line_starts", "location_rows" }, }; path: []u8, content: []u8, + /// The bytes `content`'s buffer has room for (0: as many as it holds): + /// an edit that must grow it grows it by an eighth more, so the keys + /// after it move no text but what follows them (`replace`). + cap: usize = 0, revision: u32 = 0, /// Revision last known to match disk, after Save or an external reload. /// Equal means the screen matches disk. @@ -190,6 +196,8 @@ pub const State = struct { scroll: usize = 0, /// `line_starts[i]` is line i's byte offset. Empty means not built yet. line_starts: []usize = &.{}, + /// The room `line_starts` has, as `cap` is `content`'s. + line_cap: usize = 0, /// One tree_sitter_gpa-owned syntax.Syn byte per highlighted source byte. highlights: []u8 = &.{}, location_rows: []locations.Row = &.{}, @@ -348,7 +356,8 @@ test "indexed source rows match uncached scans across content changes" { // An edit carries a built index forward; it must equal a fresh one. if (file.line_starts.len > 0) { const carried = file.line_starts; - defer p.gpa.free(carried); + const room = indexRoom(file); + defer p.gpa.free(room); file.line_starts = &.{}; try std.testing.expectEqualSlices(usize, try lineIndex(p.gpa, file), carried); p.gpa.free(file.line_starts); @@ -603,81 +612,100 @@ pub fn lineIndex(gpa: std.mem.Allocator, f: *State) ![]const usize { i += 1; } f.line_starts = starts; + f.line_cap = 0; return starts; } +/// The whole buffer of a text's bytes, its room past them included. +fn textRoom(f: *const State) []u8 { + return f.content.ptr[0..@max(f.cap, f.content.len)]; +} + +/// The whole buffer of a text's line index, as `textRoom` is its text's. +fn indexRoom(f: *const State) []usize { + return f.line_starts.ptr[0..@max(f.line_cap, f.line_starts.len)]; +} + /// `std.sort`'s order for offsets: a key against an item. fn ascending(key: usize, item: usize) std.math.Order { return std.math.order(key, item); } -/// The line index of `new` from `old`'s: an edit replaces one span, so -/// line starts before it stand, starts after it shift, and only the span -/// is scanned. Rebuilding scanned the whole file on every keystroke. /// The bytes a splice left alone at either end, when its caller knows them. pub const Span = struct { head: usize, tail: usize }; -fn editedLineStarts(gpa: std.mem.Allocator, starts: []const usize, old: []const u8, new: []const u8, known: ?Span) ![]usize { - const span = known orelse spanOf(old, new); - const head = span.head; - const tail = span.tail; - // A start s follows the newline at s-1: kept while that newline is in - // the common head, shifted while it is in the common tail. - const kept = std.sort.upperBound(usize, starts, head, ascending); - const old_tail_at = old.len - tail; - const moved = starts.len - std.sort.upperBound(usize, starts, old_tail_at, ascending); - const middle = new[head .. new.len - tail]; - const out = try gpa.alloc(usize, kept + std.mem.count(u8, middle, "\n") + moved); - @memcpy(out[0..kept], starts[0..kept]); - var i = kept; - var off: usize = 0; - while (std.mem.indexOfScalarPos(u8, middle, off, '\n')) |nl| { - off = nl + 1; - out[i] = head + off; - i += 1; +/// `f`'s line index through the edit that puts `bytes` over the `len` bytes +/// at `off`, in its own buffer: the starts before the edit stand, those it +/// took out go, its newlines' come in, and those after it move by what it +/// added; only the moving is a pass over the index, and only from the edit +/// on. `keep` (a replica's core, whose rollback copy holds the old index) +/// makes a new one instead, as every edit did once. On no memory the index +/// goes, to be made again when it is asked for. +fn shiftIndex(gpa: std.mem.Allocator, f: *State, off: usize, len: usize, bytes: []const u8, keep: bool) void { + const starts = f.line_starts; + const room = indexRoom(f); + const kept = std.sort.upperBound(usize, starts, off, ascending); + const moved = starts.len - std.sort.upperBound(usize, starts, off + len, ascending); + const n = kept + std.mem.count(u8, bytes, "\n") + moved; + const from = starts.len - moved; + const to = n - moved; + var out = room; + if (keep or n > room.len) { + const want = if (keep) n else n + @max(n / 8, 512); + out = gpa.alloc(usize, want) catch { + pardes.memory.freeRaw(gpa, room); + f.line_starts = &.{}; + f.line_cap = 0; + return; + }; + @memcpy(out[0..kept], starts[0..kept]); + } + // In place, the starts that move go back to front when the edit grew + // the index, front to back when it shrank it. + if (to > from and out.ptr == room.ptr) { + var k = moved; + while (k > 0) { + k -= 1; + out[to + k] = room[from + k] - len + bytes.len; + } + } else for (0..moved) |k| { + out[to + k] = room[from + k] - len + bytes.len; } - for (starts[starts.len - moved ..]) |start| { - out[i] = start + new.len - old.len; + var i = kept; + var at: usize = 0; + while (std.mem.indexOfScalarPos(u8, bytes, at, '\n')) |nl| { + at = nl + 1; + out[i] = off + at; i += 1; } - return out; + if (out.ptr != room.ptr) pardes.memory.freeRaw(gpa, room); + f.line_starts = out[0..n]; + f.line_cap = out.len; } -test "edited line index equals a rebuilt one" { +test "a line index shifted in place equals a rebuilt one" { const gpa = std.testing.allocator; - var prng = std.Random.DefaultPrng.init(7); + var prng = std.Random.DefaultPrng.init(11); const r = prng.random(); var text: std.ArrayList(u8) = .empty; defer text.deinit(gpa); for (0..300) |_| try text.append(gpa, "ab\n"[r.uintLessThan(usize, 3)]); - for (0..2000) |_| { - var old_state: State = undefined; - old_state.content = text.items; - old_state.line_starts = &.{}; - const starts = try lineIndex(gpa, &old_state); - defer gpa.free(starts); - // one random replace, like any edit through setContent + var f: State = .{ .path = &.{}, .content = text.items, .history = undefined }; + _ = try lineIndex(gpa, &f); + defer gpa.free(indexRoom(&f)); + for (0..2000) |round| { const at = r.uintAtMost(usize, text.items.len); - const del = r.uintAtMost(usize, @min(8, text.items.len - at)); - var ins: [8]u8 = undefined; - const ins_len = r.uintAtMost(usize, 8); + const del = r.uintAtMost(usize, @min(12, text.items.len - at)); + var ins: [12]u8 = undefined; + const ins_len = r.uintAtMost(usize, 12); for (ins[0..ins_len]) |*c| c.* = "ab\n"[r.uintLessThan(usize, 3)]; - const old = try gpa.dupe(u8, text.items); - defer gpa.free(old); + // In place, and every tenth as a replica's core makes it, anew. + shiftIndex(gpa, &f, at, del, ins[0..ins_len], round % 10 == 0); try text.replaceRange(gpa, at, del, ins[0..ins_len]); - // As a splice that says what it kept, and as one that does not. - const known: Span = .{ .head = at, .tail = old.len - at - del }; - const told = try editedLineStarts(gpa, starts, old, text.items, known); - defer gpa.free(told); - const edited = try editedLineStarts(gpa, starts, old, text.items, null); - try std.testing.expectEqualSlices(usize, edited, told); - defer gpa.free(edited); - var fresh_state: State = undefined; - fresh_state.content = text.items; - fresh_state.line_starts = &.{}; - const fresh = try lineIndex(gpa, &fresh_state); - defer gpa.free(fresh); - try std.testing.expectEqualSlices(usize, fresh, edited); + var fresh: State = .{ .path = &.{}, .content = text.items, .history = undefined }; + const want = try lineIndex(gpa, &fresh); + defer gpa.free(want); + try std.testing.expectEqualSlices(usize, want, f.line_starts); } } @@ -806,10 +834,10 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { p.gpa.free(file.path); // Raw, as every text is freed (a replica's rollback copy pins them, // src/rollback.zig, and a safe build's free writes over what it frees). - if (ntwins == 0) pardes.memory.freeRaw(p.gpa, file.content); + if (ntwins == 0) pardes.memory.freeRaw(p.gpa, textRoom(file)); if (file.listing) |listing| p.gpa.free(listing.names); if (file.mini) |*mini| mini.deinit(p.gpa); - if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, file.line_starts); + if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, indexRoom(file)); if (file.highlights.len > 0) p.tree_sitter_gpa.free(file.highlights); p.gpa.free(file.pager_spans); locations.freeRows(p.gpa, file.location_rows); @@ -822,13 +850,14 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { file.history.destroy(p.gpa); } -fn reportEdit(p: *Pardes, f: *State, new: []const u8) void { +/// The edit `replace` makes told to the event readers, before it is made. +fn reportEdit(p: *Pardes, f: *State, off: usize, len: usize, bytes: []const u8) void { if (p.fs.listeners == 0) return; const id = for (p.panes, 0..) |slot, i| { const pane = slot orelse continue; if (pane.file) |*state| if (state == f) break i; } else return; - pardes.ctlfs.events.noteReplace(p, id, false, f.content, new); + pardes.ctlfs.events.noteEdit(p, id, false, f.content, off, len, bytes); } pub fn setContent(p: *Pardes, f: *State, new: []u8) void { @@ -836,24 +865,67 @@ pub fn setContent(p: *Pardes, f: *State, new: []u8) void { } /// `setContent` for a splice that knows what it left alone at either end, -/// so the line index is not found again by comparing the whole text. +/// so it is not found again by comparing the whole text. The edit is what +/// lies between them, made by `edit`, which takes `new`, a whole text its +/// caller made anyway, as the text's buffer. pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { - // Twins (Zerox) take the same splice: where it is, found once here when - // the caller did not say, is what the line index wants anyway. + const span = span_in orelse spanOf(f.content, new); + _ = edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], new); +} + +/// The one change a text takes: the `len` bytes at `off` replaced by +/// `bytes`, in its own buffer, so an edit costs its bytes and what follows +/// them, never a copy of the text. False with no memory for it, and +/// nothing changed. +pub fn replace(p: *Pardes, f: *State, off: usize, len: usize, bytes: []const u8) bool { + return edit(p, f, off, len, bytes, null); +} + +/// Whether `f`'s bytes must stay as they are, an edit putting a new buffer +/// in their place: a replica's core, whose rollback copy holds them +/// (src/rollback.zig), or a text a join is still sending (memory.zig `pin`). +fn keepsBytes(p: *const Pardes, f: *const State) bool { + return pardes.rollback.isEpoch(p.gpa) or pardes.memory.isPinned(f.content); +} + +/// `replace`, or with `whole` that text's new buffer, `bytes` its middle, +/// taken as it is. Its room comes first, so an edit with no memory for it +/// changes nothing; then what holds a place in the text moves through the +/// edit (twins, other views, readers of its events, its line index), the +/// bytes go in and it is a new revision. +fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, whole: ?[]u8) bool { + const old_len = f.content.len; + const new_len = old_len - len + bytes_in.len; + const span: Span = .{ .head = off, .tail = old_len - off - len }; var twins: [pardes.MAX_PANES]usize = undefined; const ntwins = twinsOf(p, f, &twins); + const room = textRoom(f); + // Bytes of the text's own (a move within it) are copied out first: the + // text moves under them. + const own = whole == null and @intFromPtr(bytes_in.ptr) < @intFromPtr(room.ptr) + room.len and @intFromPtr(bytes_in.ptr) + bytes_in.len > @intFromPtr(room.ptr); + const bytes = if (own) p.scratch.allocator().dupe(u8, bytes_in) catch return false else bytes_in; + const keep = whole == null and keepsBytes(p, f); + const fresh: ?[]u8 = whole orelse if (keep) copySpliced(p.gpa, f.content, off, len, bytes) catch return false else null; + if (fresh == null) { + grow(p.gpa, f, new_len) catch return false; + // The twins' buffer is this one, which may have moved. + for (twins[0..ntwins]) |id| { + const tf = &p.panes[id].?.file.?; + tf.content = f.content; + tf.cap = f.cap; + } + } // The views not live keep their place in it as twins do (views.zig). const viewed = pardes.views.several(p); - const span: ?Span = span_in orelse if (ntwins > 0 or viewed) spanOf(f.content, new) else null; var parked: ParkedPlaces = .{}; - if (viewed) parked.before(p, f, span.?, new.len); + if (viewed) parked.before(p, f, span, new_len); defer if (viewed) parked.after(p); var moved: [pardes.MAX_PANES]struct { cursor: usize, scroll: usize } = undefined; for (twins[0..ntwins], 0..) |id, i| { const t = p.panes[id].?; const tf = &t.file.?; const at = lineStart(p.gpa, tf, @intCast(@max(0, t.body.cur_row))) + @as(usize, @intCast(@max(0, t.body.cur_col))); - moved[i] = .{ .cursor = spliced(@min(at, f.content.len), f.content.len, new.len, span.?), .scroll = spliced(lineStart(p.gpa, tf, tf.scroll), f.content.len, new.len, span.?) }; + moved[i] = .{ .cursor = spliced(@min(at, old_len), old_len, new_len, span), .scroll = spliced(lineStart(p.gpa, tf, tf.scroll), old_len, new_len, span) }; } const old_starts = f.line_starts.ptr; // An edit drops the rows and the colours, made for the text it changes. @@ -869,45 +941,54 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { } }; }; - reportEdit(p, f, new); + reportEdit(p, f, off, len, bytes); if (f.mini) |*mini| mini.deinit(p.gpa); f.mini = null; - // Found once for the line index and the places both (32 bytes a step). - const known = span orelse spanOf(f.content, new); - const starts: []usize = if (f.line_starts.len > 0) editedLineStarts(p.gpa, f.line_starts, f.content, new, known) catch &.{} else &.{}; - const old_len = f.content.len; + if (f.line_starts.len > 0) shiftIndex(p.gpa, f, off, len, bytes, pardes.rollback.isEpoch(p.gpa)); // ponytail: a whole-text hash per edit that keeps the saved length; a // rolling hash when that too matters. if (f.revision == f.saved_revision or f.saved_hash == null) { f.saved_hash = std.hash.Wyhash.hash(0, f.content); f.saved_len = f.content.len; } - // Raw: `free` overwrites a safe build's freed memory, a whole file's - // worth per keystroke; and its digest word goes (src/walk.zig). - pardes.memory.freeRaw(p.gpa, f.content); - f.content = new; + if (fresh) |new| { + // Raw: `free` overwrites a safe build's freed memory, a whole + // file's worth; and its digest word goes (src/walk.zig). + pardes.memory.freeRaw(p.gpa, textRoom(f)); + f.content = new[0..new_len]; + f.cap = new.len; + } else { + const buffer = textRoom(f); + const tail = old_len - off - len; + if (bytes.len != len) @memmove(buffer[off + bytes.len ..][0..tail], buffer[off + len ..][0..tail]); + @memcpy(buffer[off..][0..bytes.len], bytes); + f.content = buffer[0..new_len]; + f.cap = buffer.len; + // Written in place: a word a digest kept for it is no longer its. + pardes.walk.forget(@intFromPtr(buffer.ptr)); + } f.revision +%= 1; - f.splice = .{ .revision = f.revision, .head = known.head, .tail = known.tail, .old_len = old_len }; - if (f.saved_hash) |h| if ((f.saved_len orelse new.len) == new.len and std.hash.Wyhash.hash(0, new) == h) { + f.splice = .{ .revision = f.revision, .head = span.head, .tail = span.tail, .old_len = old_len }; + if (f.saved_hash) |h| if ((f.saved_len orelse new_len) == new_len and std.hash.Wyhash.hash(0, f.content) == h) { f.saved_revision = f.revision; }; // The clock the session that recorded read (src/tape.zig). f.mtime = pardes.tape.value(.mtime, pardes.ctlfs.events.now, .{}); - if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); - f.line_starts = starts; if (f.highlights.len > 0) p.tree_sitter_gpa.free(f.highlights); f.highlights = &.{}; f.highlight_start = 0; f.syntax_dirty = true; - if (f.pager) f.pager_diff = looksLikeDiff(new[0..@min(new.len, 64 * 1024)]); + if (f.pager) f.pager_diff = looksLikeDiff(f.content[0..@min(new_len, 64 * 1024)]); for (twins[0..ntwins], 0..) |id, i| { const t = p.panes[id].?; const tf = &t.file.?; // Its own index, built while the shared one was empty, goes; the - // shared one, freed above, is replaced. - if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, tf.line_starts); + // shared one is this one's, moved through the edit. + if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, indexRoom(tf)); tf.content = f.content; + tf.cap = f.cap; tf.line_starts = f.line_starts; + tf.line_cap = f.line_cap; tf.revision = f.revision; tf.saved_revision = f.saved_revision; tf.saved_hash = f.saved_hash; @@ -932,6 +1013,35 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { t.body.cur_col = @intCast(cursor.col); tf.scroll = positionIn(p.gpa, tf, moved[i].scroll).row; } + return true; +} + +/// Room in `f`'s buffer for `n` bytes, grown by an eighth more when it must +/// be: in place where its allocator can, else into a new buffer. +fn grow(gpa: std.mem.Allocator, f: *State, n: usize) !void { + const room = textRoom(f); + if (n <= room.len) return; + const want = n + @max(n / 8, 4096); + if (room.len > 0) if (gpa.remap(room, want)) |grown| { + pardes.walk.forget(@intFromPtr(room.ptr)); + f.content = grown[0..f.content.len]; + f.cap = grown.len; + return; + }; + const fresh = try pardes.memory.unfilled(gpa, want); + @memcpy(fresh[0..f.content.len], f.content); + pardes.memory.freeRaw(gpa, room); + f.content = fresh[0..f.content.len]; + f.cap = fresh.len; +} + +/// `text` with the `len` bytes at `off` replaced by `bytes`, in a new buffer. +fn copySpliced(gpa: std.mem.Allocator, text: []const u8, off: usize, len: usize, bytes: []const u8) ![]u8 { + const out = try pardes.memory.unfilled(gpa, text.len - len + bytes.len); + @memcpy(out[0..off], text[0..off]); + @memcpy(out[off..][0..bytes.len], bytes); + @memcpy(out[off + bytes.len ..], text[off + len ..]); + return out; } /// Each other view's cursor and scroll on a text being changed, as offsets @@ -1068,7 +1178,9 @@ pub fn zerox(p: *Pardes, from: usize, to: usize) !*Pane { pane.file = .{ .path = path, .content = f.content, + .cap = f.cap, .line_starts = f.line_starts, + .line_cap = f.line_cap, .history = f.history, .revision = f.revision, .saved_revision = f.saved_revision, @@ -1099,8 +1211,12 @@ pub fn leaveTwins(p: *Pardes, f: *State) void { const shared_index = for (twins[0..n]) |id| { if (p.panes[id].?.file.?.line_starts.ptr == f.line_starts.ptr) break true; } else false; - if (shared_index) f.line_starts = &.{}; + if (shared_index) { + f.line_starts = &.{}; + f.line_cap = 0; + } f.content = p.gpa.dupe(u8, f.content) catch p.gpa.alloc(u8, 0) catch &.{}; + f.cap = 0; f.history = History.create(p.gpa) catch f.history; // The one left is no twin now (syncTwins drops the group). if (n == 1) p.panes[twins[0]].?.file.?.twin = 0; -- cgit v1.3