From 9e504559356ed985999d8625947d9b08ad582792 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 5 Nov 2026 19:47:19 -0300 Subject: rollback: a replica's core writes a file's text and its line index in place, as the session's does, and its rollback copy keeps none of their bytes: the epoch notes what each write into a text or an index that was there when the copy was taken took out (rollback.Epoch.wrote, from File.edit and shiftIndex), and putting the copy back writes that back, the newest first, before the saved bytes go back (unwrite), where a replica's edit made a whole new text and a whole new index at every key so that the copy could pin the old ones; the bridge the journal left for this goes with it: rollback.isEpoch, File.keepsBytes (a text a join is still sending is copied on write as before, memory.isPinned), the replica's copy-on-write in File.edit and shiftIndex's `keep` (its in-place shift is File.shiftStarts, which the rollback runs turned round); the journal's steps, its `done` and its entries come back as the copy saved them, an entry a speculation merged into and the redo entries it dropped being saved bytes and put-off frees; File.State's content and line_starts are annotated `.journal`, which the copy neither saves nor pins (line_starts leaves `.blob`); a write that could not be noted (no memory) fails the replica at its rollback; tests: rollback.zig's 'a text written in place under a copy comes back byte for byte: typed into its room, undone, cut, and grown past it' is new, and File.zig's 'a line index shifted in place equals a rebuilt one' becomes '..., and the edit turned round gives the one before back' (its every tenth shift made anew, as a replica's core made them, gives way to the shift turned round in a copy, as a rollback makes it) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/File.zig | 109 +++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 65 insertions(+), 44 deletions(-) (limited to 'src/File.zig') diff --git a/src/File.zig b/src/File.zig index 89acd4d8..8e5c0101 100644 --- a/src/File.zig +++ b/src/File.zig @@ -111,10 +111,15 @@ pub const State = struct { /// from the text whenever it is wanted. pub const replica = .{ .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" }, + // Big texts, dumped and sent by their hash (src/walk.zig). The + // text is written in place by `replace`, but never while a join + // sends it (memory.zig `pin`): then an edit puts a new buffer in + // its place. + .blob = .{ "content", "location_rows" }, + // Written in place in a replica's core too: its rollback copy keeps + // none of their bytes, and takes back what a speculation wrote + // (src/rollback.zig `Epoch.wrote`). + .journal = .{ "content", "line_starts" }, }; path: []u8, @@ -604,55 +609,63 @@ fn ascending(key: usize, item: usize) std.math.Order { pub const Span = struct { head: usize, tail: usize }; /// `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 { +/// at `off` (`shiftStarts`), in its own buffer, grown by an eighth more when +/// it must be. 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) 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; + const n = starts.len - (std.sort.upperBound(usize, starts, off + len, ascending) - std.sort.upperBound(usize, starts, off, ascending)) + std.mem.count(u8, bytes, "\n"); 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 { + if (n > room.len) { + out = gpa.alloc(usize, n + @max(n / 8, 512)) 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) { + @memcpy(out[0..starts.len], starts); + } else pardes.rollback.Epoch.wrote(gpa, usize, room, starts.len, n, off, f.content[off..][0..len], bytes.len); + shiftStarts(out, starts.len, n, off, len, bytes); + if (out.ptr != room.ptr) pardes.memory.freeRaw(gpa, room); + f.line_starts = out[0..n]; + f.line_cap = out.len; +} + +/// The first `len` of `room`, a line index, through the edit that puts +/// `bytes` over the `cut` bytes at `off`, in place, `n` long after it +/// (`room` holds that): 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. The +/// edit turned round (`cut` its length in, `bytes` what it took out) gives +/// the index before it back: a rollback's (src/rollback.zig `unwrite`). +pub fn shiftStarts(room: []usize, len: usize, n: usize, off: usize, cut: usize, bytes: []const u8) void { + const starts = room[0..len]; + const kept = std.sort.upperBound(usize, starts, off, ascending); + const moved = len - std.sort.upperBound(usize, starts, off + cut, ascending); + const from = len - moved; + const to = n - moved; + // The starts that move go back to front when the edit grew the index, + // front to back when it shrank it. + if (to > from) { var k = moved; while (k > 0) { k -= 1; - out[to + k] = room[from + k] - len + bytes.len; + room[to + k] = room[from + k] - cut + bytes.len; } } else for (0..moved) |k| { - out[to + k] = room[from + k] - len + bytes.len; + room[to + k] = room[from + k] - cut + bytes.len; } var i = kept; var at: usize = 0; while (std.mem.indexOfScalarPos(u8, bytes, at, '\n')) |nl| { at = nl + 1; - out[i] = off + at; + room[i] = off + at; i += 1; } - if (out.ptr != room.ptr) pardes.memory.freeRaw(gpa, room); - f.line_starts = out[0..n]; - f.line_cap = out.len; } -test "a line index shifted in place equals a rebuilt one" { +test "a line index shifted in place equals a rebuilt one, and the edit turned round gives the one before back" { const gpa = std.testing.allocator; var prng = std.Random.DefaultPrng.init(11); const r = prng.random(); @@ -668,13 +681,25 @@ test "a line index shifted in place equals a rebuilt one" { 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)]; - // 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); + const before = try gpa.dupe(usize, f.line_starts); + defer gpa.free(before); + const cut = try gpa.dupe(u8, text.items[at..][0..del]); + defer gpa.free(cut); + f.content = text.items; + shiftIndex(gpa, &f, at, del, ins[0..ins_len]); try text.replaceRange(gpa, at, del, ins[0..ins_len]); 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); + // Every tenth turned round in a copy, as a rollback takes it back. + if (round % 10 == 0) { + const room = try gpa.alloc(usize, indexRoom(&f).len); + defer gpa.free(room); + @memcpy(room[0..f.line_starts.len], f.line_starts); + shiftStarts(room, f.line_starts.len, before.len, at, ins_len, cut); + try std.testing.expectEqualSlices(usize, before, room[0..before.len]); + } } } @@ -801,8 +826,9 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { if (p.panes[id].?.file.?.line_starts.ptr == file.line_starts.ptr) break true; } else false; 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). + // Raw, as every text is freed (a replica's rollback copy keeps the + // buffers it was taken over, src/rollback.zig, and a safe build's free + // writes over what it frees). 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); @@ -850,13 +876,6 @@ pub fn replace(p: *Pardes, f: *State, off: usize, len: usize, bytes: []const u8) return edit(p, f, off, len, bytes, null, true, 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); -} - /// A replacement that takes out at least this much, and most of the text, /// keeps the old buffer for its undo (Text.Journal.swap) instead of copying /// what it takes out. @@ -882,7 +901,8 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who 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 swapping = journaled and len >= swap_min and len * 2 >= old_len; - const keep = whole == null and (swapping or keepsBytes(p, f)); + // A text a join is still sending stays as it is (memory.zig `pin`). + const keep = whole == null and (swapping or pardes.memory.isPinned(f.content)); 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; @@ -922,7 +942,7 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who reportEdit(p, f, off, len, bytes); if (f.mini) |*mini| mini.deinit(p.gpa); f.mini = null; - if (f.line_starts.len > 0) shiftIndex(p.gpa, f, off, len, bytes, pardes.rollback.isEpoch(p.gpa)); + if (f.line_starts.len > 0) shiftIndex(p.gpa, f, off, len, bytes); if (journaled and !swapping) f.history.journal.record(p.gpa, f.content, off, len, bytes.len); // ponytail: a whole-text hash per edit that keeps the saved length; a // rolling hash when that too matters. @@ -946,6 +966,7 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who } } else { const buffer = textRoom(f); + pardes.rollback.Epoch.wrote(p.gpa, u8, buffer, old_len, new_len, off, buffer[off..][0..len], bytes.len); 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); -- cgit v1.3