summaryrefslogtreecommitdiff
path: root/src/rollback.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/rollback.zig')
-rw-r--r--src/rollback.zig180
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"));