diff options
Diffstat (limited to 'src/rollback.zig')
| -rw-r--r-- | src/rollback.zig | 180 |
1 files changed, 155 insertions, 25 deletions
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")); |
