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/rollback.zig | 180 +++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 155 insertions(+), 25 deletions(-) (limited to 'src/rollback.zig') diff --git a/src/rollback.zig b/src/rollback.zig index 320e7949..46e00721 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -11,16 +11,23 @@ //! - `Copy`, the walker's walk of the core's state (src/walk.zig: what a //! digest covers, so views, buffers, registers, counters and terminal //! metadata), saving the bytes of every allocation it reaches, the core -//! struct's own included. A file's text, its line index, its undo -//! snapshots and a register's texts are pinned instead: an edit puts a -//! new buffer in their place (File.setContentSpan, Registers.put) and -//! never writes one, so the copy keeps a reference and the put-off free -//! keeps it alive. +//! struct's own included. A file's text and its line index are neither +//! saved nor pinned (`.journal`): an edit writes them in place, in a +//! replica's core as in the session's (File.replace), and the epoch +//! notes what each write into one of then took out (`wrote`), which +//! putting the copy back takes back, the newest first. The journal's +//! entries, a register's texts and a file's location rows are pinned +//! instead: an edit puts a new buffer in their place and never writes +//! one, so the copy keeps a reference and the put-off free keeps it +//! alive. So the journal's steps, its `done` and its entries come back +//! as they were: an entry a speculation merged into, or the steps to +//! redo it dropped, are its saved bytes and its put-off frees. //! -//! Putting the copy back writes each saved allocation's bytes over it, so -//! every pointer in them points where it did, at what was there; then the -//! epoch's allocations are freed and its put-off frees forgotten. Letting -//! the copy go (the speculation was right) makes the put-off frees. +//! Putting the copy back undoes the writes, then writes each saved +//! allocation's bytes over it, so every pointer in them points where it +//! did, at what was there; then the epoch's allocations are freed and its +//! put-off frees forgotten. Letting the copy go (the speculation was right) +//! makes the put-off frees. //! //! ponytail: an allocation reached only through a field the walk leaves //! out (a derived cache's own heap, say) is not saved; that cache is the @@ -61,8 +68,18 @@ pub const Epoch = struct { born: std.ArrayListUnmanaged(usize) = .empty, deferred: std.ArrayListUnmanaged(usize) = .empty, trees: pardes.syntax.HeldTrees = .{ .meta = std.heap.c_allocator }, + /// The writes in place into a text or a line index that was there when + /// the copy was taken (`wrote`), in order, and the bytes they took out. + writes: std.ArrayListUnmanaged(Write) = .empty, + taken: std.ArrayListUnmanaged(u8) = .empty, + /// A write could not be noted (no memory): the copy cannot be put back. + lost: bool = false, const Entry = struct { len: usize, alignment: Alignment, epoch: u32, freed: bool = false }; + /// At `off` of the text or index at `addr` (`room` long, its elements + /// `was` before the write and `len` after), `ins` bytes put over + /// `taken[at..][0..cut]`. + const Write = struct { index: bool, addr: usize, room: usize, was: usize, len: usize, off: usize, at: usize, cut: usize, ins: usize }; const vtable: Allocator.VTable = .{ .alloc = alloc, .resize = resize, .remap = remap, .free = free }; @@ -78,6 +95,8 @@ pub const Epoch = struct { e.deferred.deinit(e.meta); e.trees.born.deinit(e.meta); e.trees.freed.deinit(e.meta); + e.writes.deinit(e.meta); + e.taken.deinit(e.meta); } fn mine(e: *const Epoch, entry: Entry) bool { @@ -159,6 +178,7 @@ pub const Epoch = struct { e.id +%= 1; if (e.id == 0) e.id = 1; e.on = true; + e.lost = false; e.born.clearRetainingCapacity(); e.deferred.clearRetainingCapacity(); e.trees.born.clearRetainingCapacity(); @@ -185,6 +205,8 @@ pub const Epoch = struct { fn end(e: *Epoch) void { e.on = false; + e.writes.clearRetainingCapacity(); + e.taken.clearRetainingCapacity(); e.born.clearRetainingCapacity(); e.deferred.clearRetainingCapacity(); e.trees.born.clearRetainingCapacity(); @@ -192,6 +214,54 @@ pub const Epoch = struct { if (pardes.syntax.held_trees == &e.trees) pardes.syntax.held_trees = null; } + /// A write about to be made in place into `room`, a text's bytes or its + /// line index (`E` u8 or usize, File.zig `edit`): at the text's offset + /// `off`, `ins` bytes over `cut`, the bytes taken out, `room` `was` + /// elements long before and `len` after. Noted when `room` was there when the copy was + /// taken, so that putting it back takes the write back (`unwrite`); one + /// the epoch made goes whole. Nothing outside a replica's core. + pub fn wrote(gpa: Allocator, comptime E: type, room: []const E, was: usize, len: usize, off: usize, cut: []const u8, ins: usize) void { + if (gpa.vtable != &vtable) return; + const e: *Epoch = @ptrCast(@alignCast(gpa.ptr)); + if (!e.on) return; + const entry = e.live.get(@intFromPtr(room.ptr)) orelse return; + if (e.mine(entry)) return; + const at = e.taken.items.len; + e.taken.appendSlice(e.meta, cut) catch { + e.lost = true; + return; + }; + e.writes.append(e.meta, .{ .index = E == usize, .addr = @intFromPtr(room.ptr), .room = room.len, .was = was, .len = len, .off = off, .at = at, .cut = cut.len, .ins = ins }) catch { + e.lost = true; + }; + } + + /// Every write `wrote` noted taken back, the last first: each text and + /// index as it was when the copy was taken. + fn unwrite(e: *Epoch) void { + var i = e.writes.items.len; + while (i > 0) { + i -= 1; + const w = e.writes.items[i]; + const cut = e.taken.items[w.at..][0..w.cut]; + if (w.index) { + const room = @as([*]usize, @ptrFromInt(w.addr))[0..w.room]; + pardes.panes.File.shiftStarts(room, w.len, w.was, w.off, w.ins, cut); + } else { + const room = @as([*]u8, @ptrFromInt(w.addr))[0..w.room]; + const tail = w.len - w.off - w.ins; + @memmove(room[w.off + cut.len ..][0..tail], room[w.off + w.ins ..][0..tail]); + @memcpy(room[w.off..][0..cut.len], cut); + } + } + } + + /// Whether a write was noted into the allocation at `addr`. + fn wroteAt(e: *const Epoch, addr: usize) bool { + for (e.writes.items) |w| if (w.addr == addr) return true; + return false; + } + /// The trees of whichever core is stepped next: one in-process harness /// steps several (syntax.held_trees is process-wide). pub fn select(e: ?*Epoch) void { @@ -199,13 +269,6 @@ pub const Epoch = struct { } }; -/// Whether `a` is an epoch's: a replica's core, whose texts a copy holds, -/// so an edit puts a new buffer in place of one and never writes it -/// (File.replace). -pub fn isEpoch(a: Allocator) bool { - return a.vtable == &Epoch.vtable; -} - pub const Copy = struct { meta: Allocator = std.heap.c_allocator, regions: std.ArrayListUnmanaged(Region) = .empty, @@ -270,13 +333,17 @@ pub const Copy = struct { c.held = true; } - /// The core as it was when the copy was taken. - pub fn restore(c: *Copy) void { + /// The core as it was when the copy was taken: false when a write into + /// a text could not be noted (no memory), and that text is not. + pub fn restore(c: *Copy) bool { std.debug.assert(c.held); + const whole = !c.epoch.?.lost; + c.epoch.?.unwrite(); c.check(); for (c.regions.items) |r| @memcpy(@as([*]u8, @ptrFromInt(r.addr))[0..r.len], c.bytes.items[r.off..][0..r.len]); c.epoch.?.discard(); c.held = false; + return whole; } /// The speculation was right: the copy is not wanted. @@ -287,9 +354,11 @@ pub const Copy = struct { c.held = false; } + /// Every pinned blob as it was, but one a text became since and was + /// written as one (an undo swapped a text back into its buffer). pub fn check(c: *const Copy) void { if (comptime !checked) return; - for (c.pins.items) |pin| if (std.hash.Wyhash.hash(0, @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]) != pin.hash) { + for (c.pins.items) |pin| if (!c.epoch.?.wroteAt(pin.addr) and std.hash.Wyhash.hash(0, @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]) != pin.hash) { const now = @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]; const entry = c.epoch.?.live.get(pin.addr); std.debug.print("rollback: {s}, {d} bytes at {x}, pinned, was written in place: now {any}; entry {any}, epoch {d}\n", .{ pin.where, pin.len, pin.addr, now[0..32], entry, c.epoch.?.id }); @@ -372,7 +441,9 @@ pub const Copy = struct { // queues a step drains (undefined between steps), nor the // authority's. if (attr.@"comptime" or comptime (annotated(T, "authority", name) or ((annotated(T, "local", name) or annotated(T, "derived", name)) and unsaved(name)))) continue; - if (comptime opaqueTo(F)) continue; + // A text and its index: written in place, the epoch + // notes what each write takes out (`Epoch.wrote`). + if (comptime opaqueTo(F) or annotated(T, "journal", name)) continue; c.where = @typeName(T) ++ "." ++ name; c.pinnable = comptime walk.blob(T, name); if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { @@ -517,7 +588,7 @@ test "a copy put back is the core as it was; one let go keeps what was done" { p.pump(.{}) catch {}; const edited = walk.digest(Pardes, p); try std.testing.expect(edited != before); - c.restore(); + try std.testing.expect(c.restore()); try std.testing.expectEqual(before, walk.digest(Pardes, p)); // The same again, let go this time: what was typed stays. try c.take(&e, p); @@ -531,6 +602,65 @@ test "a copy put back is the core as it was; one let go keeps what was done" { try std.testing.expectEqual(@as(usize, 0), e.live.count()); } +test "a text written in place under a copy comes back byte for byte: typed into its room, undone, cut, and grown past it" { + var e: Epoch = .{ .child = std.testing.allocator }; + defer e.deinit(); + const gpa = e.allocator(); + const p = try Pardes.init(gpa, .{ .cols = 80, .rows = 24, .file = "build.zig", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa }); + p.pump(.{}) catch {}; + const f = for (p.panes) |slot| { + if (slot) |pane| if (pane.file) |*file| break file; + } else return error.NoFile; + const keys = struct { + fn typed(core: *Pardes, text: []const u8) void { + for (text) |k| core.update(.{ .key = .{ .cp = k, .text = &.{k} } }); + core.update(.{ .key = .{ .cp = pardes.Key.escape } }); + core.pump(.{}) catch {}; + } + }; + // One edit first, so that the text has room to be typed into. + keys.typed(p, "oa"); + try std.testing.expect(f.cap > f.content.len); + _ = try pardes.panes.File.lineIndex(gpa, f); + const text = try std.testing.allocator.dupe(u8, f.content); + defer std.testing.allocator.free(text); + const index = try std.testing.allocator.dupe(usize, f.line_starts); + defer std.testing.allocator.free(index); + const before = walk.digest(Pardes, p); + const room = f.content.ptr; + var c: Copy = .{}; + defer c.deinit(); + try c.take(&e, p); + // The copy pins none of the text. + try std.testing.expect(c.pinnedBytes() < text.len); + // Typed and undone in place; a line cut, into a buffer of the epoch's, + // and typed into past its room. + keys.typed(p, "ix y z"); + try std.testing.expectEqual(room, f.content.ptr); + keys.typed(p, "u"); + try std.testing.expectEqual(room, f.content.ptr); + keys.typed(p, "ib"); + keys.typed(p, "xd"); + var long: [16 << 10]u8 = undefined; + @memset(&long, 'q'); + long[0] = 'i'; + keys.typed(p, &long); + try std.testing.expect(f.content.ptr != room); + // Each write into the text and its index of then, noted. + try std.testing.expect(e.writes.items.len >= 4); + try std.testing.expect(c.restore()); + try std.testing.expectEqual(before, walk.digest(Pardes, p)); + try std.testing.expectEqualStrings(text, f.content); + try std.testing.expectEqualSlices(usize, index, f.line_starts); + // Let go this time: what was typed in place stays. + try c.take(&e, p); + keys.typed(p, "iz"); + c.release(); + try std.testing.expect(f.content.len > text.len); + p.deinit(); + try std.testing.expectEqual(@as(usize, 0), e.live.count()); +} + test "a view's slot, live or drawn outside a step (a replica's own, another live), keeps no pointer a rollback could put old bytes back through" { // The C heap: a freed chunk comes back to the next allocation its size. const Read = struct { @@ -571,7 +701,7 @@ test "a view's slot, live or drawn outside a step (a replica's own, another live try c.take(&e, p); // Written in place while the copy is held, then the copy put back. @memset(other, 'b'); - c.restore(); + try std.testing.expect(c.restore()); try std.testing.expect(std.mem.allEqual(u8, other, 'b')); } if (skipped) return error.SkipZigTest; @@ -597,7 +727,7 @@ test "a register's texts are pinned, not copied, and come back whole" { try std.testing.expect(c.pinnedBytes() >= 4 << 20); // A speculation yanks over it, and is undone. p.registers.put(gpa, reg, "a word", 0, 1, true); - c.restore(); + try std.testing.expect(c.restore()); const back = p.registers.value(reg, 0) orelse return error.Lost; try std.testing.expectEqual(grid.len, back.len); try std.testing.expect(std.mem.allEqual(u8, back, 'y')); @@ -626,7 +756,7 @@ test "a file's location rows are pinned whole, with what they own, and come back // A speculation's new search drops them, and is undone. locations.freeRows(gpa, f.location_rows); f.location_rows = &.{}; - c.restore(); + try std.testing.expect(c.restore()); try std.testing.expectEqual(@as(usize, 500), f.location_rows.len); try std.testing.expectEqualStrings("src/rollback.zig", f.location_rows[499].path); p.deinit(); @@ -663,7 +793,7 @@ test "a rollback leaves the store and Recent as a speculation left them: they li p.update(.{ .command = try lookAt(&line, "build.zig") }); p.update(.{ .command = "Del" }); p.pump(.{}) catch {}; - c.restore(); + try std.testing.expect(c.restore()); // What the store and Recent hold is where they say it is. try std.testing.expectEqual(@as(usize, 2), p.store.closed.items.len); try std.testing.expect(std.mem.endsWith(u8, p.store.closed.items[1].name, "build.zig")); -- cgit v1.3