summaryrefslogtreecommitdiff
path: root/src/rollback.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/rollback.zig')
-rw-r--r--src/rollback.zig681
1 files changed, 681 insertions, 0 deletions
diff --git a/src/rollback.zig b/src/rollback.zig
new file mode 100644
index 00000000..cc10d2cc
--- /dev/null
+++ b/src/rollback.zig
@@ -0,0 +1,681 @@
+//! A replica's rollback copy (docs/next-daemon.md, phase 5): the state a
+//! speculation can write, saved before it writes, and put back where it was
+//! when the authority's order differs.
+//!
+//! Two halves:
+//! - `Epoch`, the replica core's allocator. It knows every allocation, and
+//! while a copy is held it frees nothing that was there before (a free
+//! is put off) and grows nothing of then in place. What is allocated
+//! meanwhile is the epoch's. So whatever the core held when the copy was
+//! taken is still where it was when the copy is put back.
+//! - `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.
+//!
+//! 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.
+//!
+//! 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
+//! epoch's as it was written, which is right for one remade from the text
+//! it was made of and wrong for one changed in place. The replica harness
+//! (test/replicas.zig) checks a digest at every confirmed step.
+const std = @import("std");
+const builtin = @import("builtin");
+const pardes = @import("pardes.zig");
+const walk = @import("walk.zig");
+const Allocator = std.mem.Allocator;
+const Alignment = std.mem.Alignment;
+const Pardes = pardes.Pardes;
+
+/// Blobs (walk.blob: fields annotated `.blob`) this long or longer are
+/// pinned, not copied. Checked unchanged in a safe build when the copy goes.
+const blob_min = 4096;
+const checked = builtin.mode == .debug or builtin.mode == .safe;
+
+/// An address as a hash map's key: a multiply, not a Wyhash of its bytes
+/// (every allocation of a replica's core is a lookup).
+const Addr = struct {
+ pub fn hash(_: Addr, a: usize) u64 {
+ return @as(u64, a) *% 0x9e3779b97f4a7c15;
+ }
+ pub fn eql(_: Addr, a: usize, b: usize) bool {
+ return a == b;
+ }
+};
+
+pub const Epoch = struct {
+ child: Allocator = std.heap.c_allocator,
+ /// Its own bookkeeping, never the epoch's.
+ meta: Allocator = std.heap.c_allocator,
+ live: std.HashMapUnmanaged(usize, Entry, Addr, std.hash_map.default_max_load_percentage) = .empty,
+ on: bool = false,
+ id: u32 = 0,
+ born: std.ArrayListUnmanaged(usize) = .empty,
+ deferred: std.ArrayListUnmanaged(usize) = .empty,
+ trees: pardes.syntax.HeldTrees = .{ .meta = std.heap.c_allocator },
+
+ const Entry = struct { len: usize, alignment: Alignment, epoch: u32, freed: bool = false };
+
+ pub fn allocator(e: *Epoch) Allocator {
+ return .{ .ptr = e, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } };
+ }
+
+ pub fn deinit(e: *Epoch) void {
+ var it = e.live.iterator();
+ while (it.next()) |kv| e.child.rawFree(@as([*]u8, @ptrFromInt(kv.key_ptr.*))[0..kv.value_ptr.len], kv.value_ptr.alignment, @returnAddress());
+ e.live.deinit(e.meta);
+ e.born.deinit(e.meta);
+ e.deferred.deinit(e.meta);
+ e.trees.born.deinit(e.meta);
+ e.trees.freed.deinit(e.meta);
+ }
+
+ fn mine(e: *const Epoch, entry: Entry) bool {
+ return e.on and entry.epoch == e.id;
+ }
+
+ /// The live allocation that starts at `addr`.
+ pub fn owns(e: *const Epoch, addr: usize) ?Entry {
+ const entry = e.live.get(addr) orelse return null;
+ return if (entry.freed) null else entry;
+ }
+
+ fn note(e: *Epoch, addr: usize, len: usize, alignment: Alignment) bool {
+ e.live.put(e.meta, addr, .{ .len = len, .alignment = alignment, .epoch = if (e.on) e.id else 0 }) catch return false;
+ if (e.on) e.born.append(e.meta, addr) catch {};
+ return true;
+ }
+
+ /// Every new allocation filled with this: a core reading memory it never
+ /// wrote shows as a replica's divergence (test/replicas.zig, a release
+ /// build's heap is otherwise whatever it was).
+ pub var fill: ?u8 = null;
+
+ fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 {
+ const e: *Epoch = @ptrCast(@alignCast(ctx));
+ const ptr = e.child.rawAlloc(len, alignment, ra) orelse return null;
+ if (fill) |b| @memset(ptr[0..len], b);
+ if (!e.note(@intFromPtr(ptr), len, alignment)) {
+ e.child.rawFree(ptr[0..len], alignment, ra);
+ return null;
+ }
+ return ptr;
+ }
+
+ fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool {
+ const e: *Epoch = @ptrCast(@alignCast(ctx));
+ const entry = e.live.getPtr(@intFromPtr(memory.ptr)) orelse return false;
+ // What the copy saved stays its size: the core moves instead.
+ if (e.on and !e.mine(entry.*)) return false;
+ if (!e.child.rawResize(memory, alignment, new_len, ra)) return false;
+ entry.len = new_len;
+ return true;
+ }
+
+ fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 {
+ const e: *Epoch = @ptrCast(@alignCast(ctx));
+ const old = @intFromPtr(memory.ptr);
+ const entry = e.live.get(old) orelse return null;
+ if (e.on and !e.mine(entry)) return null;
+ const ptr = e.child.rawRemap(memory, alignment, new_len, ra) orelse return null;
+ _ = e.live.remove(old);
+ e.live.put(e.meta, @intFromPtr(ptr), .{ .len = new_len, .alignment = alignment, .epoch = entry.epoch }) catch {};
+ if (e.mine(entry) and @intFromPtr(ptr) != old) e.born.append(e.meta, @intFromPtr(ptr)) catch {};
+ return ptr;
+ }
+
+ fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void {
+ const e: *Epoch = @ptrCast(@alignCast(ctx));
+ const addr = @intFromPtr(memory.ptr);
+ const entry = e.live.getPtr(addr) orelse return e.child.rawFree(memory, alignment, ra);
+ if (e.on and !e.mine(entry.*)) {
+ // Held by the copy until it is put back or let go.
+ if (!entry.freed) e.deferred.append(e.meta, addr) catch {};
+ entry.freed = true;
+ return;
+ }
+ e.child.rawFree(memory.ptr[0..entry.len], entry.alignment, ra);
+ _ = e.live.remove(addr);
+ }
+
+ fn reallyFree(e: *Epoch, addr: usize) void {
+ const entry = e.live.get(addr) orelse return;
+ e.child.rawFree(@as([*]u8, @ptrFromInt(addr))[0..entry.len], entry.alignment, @returnAddress());
+ _ = e.live.remove(addr);
+ }
+
+ fn begin(e: *Epoch) void {
+ std.debug.assert(!e.on);
+ e.id +%= 1;
+ if (e.id == 0) e.id = 1;
+ e.on = true;
+ e.born.clearRetainingCapacity();
+ e.deferred.clearRetainingCapacity();
+ e.trees.born.clearRetainingCapacity();
+ e.trees.freed.clearRetainingCapacity();
+ pardes.syntax.held_trees = &e.trees;
+ }
+
+ /// The copy put back: what the epoch made goes, what it freed stays.
+ fn discard(e: *Epoch) void {
+ for (e.born.items) |addr| if (e.live.get(addr)) |entry| if (e.mine(entry)) e.reallyFree(addr);
+ for (e.deferred.items) |addr| if (e.live.getPtr(addr)) |entry| {
+ entry.freed = false;
+ };
+ for (e.trees.born.items) |t| pardes.syntax.destroyTree(t);
+ e.end();
+ }
+
+ /// The copy let go: what the epoch freed goes now.
+ fn keep(e: *Epoch) void {
+ for (e.deferred.items) |addr| e.reallyFree(addr);
+ for (e.trees.freed.items) |t| pardes.syntax.destroyTree(t);
+ e.end();
+ }
+
+ fn end(e: *Epoch) void {
+ e.on = false;
+ e.born.clearRetainingCapacity();
+ e.deferred.clearRetainingCapacity();
+ e.trees.born.clearRetainingCapacity();
+ e.trees.freed.clearRetainingCapacity();
+ if (pardes.syntax.held_trees == &e.trees) pardes.syntax.held_trees = null;
+ }
+
+ /// 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 {
+ pardes.syntax.held_trees = if (e) |x| (if (x.on) &x.trees else null) else null;
+ }
+};
+
+pub const Copy = struct {
+ meta: Allocator = std.heap.c_allocator,
+ regions: std.ArrayListUnmanaged(Region) = .empty,
+ bytes: std.ArrayListUnmanaged(u8) = .empty,
+ seen: std.HashMapUnmanaged(Seen, void, SeenContext, std.hash_map.default_max_load_percentage) = .empty,
+ pins: std.ArrayListUnmanaged(Pin) = .empty,
+ held: bool = false,
+ epoch: ?*Epoch = null,
+ /// The field being walked, for a pin's report, and whether it is one
+ /// of the blobs: a file's text or an undo snapshot's.
+ where: []const u8 = "",
+ pinnable: bool = false,
+
+ const Region = struct { addr: usize, off: usize, len: usize };
+ const Pin = struct { addr: usize, len: usize, hash: u64, where: []const u8 };
+ const Seen = struct { addr: usize, ty: usize };
+ const SeenContext = struct {
+ pub fn hash(_: SeenContext, k: Seen) u64 {
+ return (@as(u64, k.addr) *% 0x9e3779b97f4a7c15) ^ (@as(u64, k.ty) *% 0xc2b2ae3d27d4eb4f);
+ }
+ pub fn eql(_: SeenContext, a: Seen, b: Seen) bool {
+ return a.addr == b.addr and a.ty == b.ty;
+ }
+ };
+ /// Queued: the core holds effects or inputs not drained yet, which no
+ /// copy is taken over (the replica's input waits for the authority).
+ pub const Error = Allocator.Error || error{Queued};
+
+ pub fn deinit(c: *Copy) void {
+ c.regions.deinit(c.meta);
+ c.bytes.deinit(c.meta);
+ c.seen.deinit(c.meta);
+ c.pins.deinit(c.meta);
+ }
+
+ pub fn savedBytes(c: *const Copy) usize {
+ return c.bytes.items.len;
+ }
+
+ pub fn pinnedBytes(c: *const Copy) usize {
+ var n: usize = 0;
+ for (c.pins.items) |pin| n += pin.len;
+ return n;
+ }
+
+ /// The copy of `p`, whose allocator is `e`'s, taken: from now on what
+ /// it held stays where it is until the copy is put back or let go.
+ pub fn take(c: *Copy, e: *Epoch, p: *const Pardes) Error!void {
+ std.debug.assert(!c.held);
+ // A step drains these before it ends, and a copy is taken between
+ // steps; an input of a host's without one (a view closed) may leave
+ // some until it is drained.
+ if (p.effects_len != 0 or p.in_len != 0) return error.Queued;
+ c.regions.clearRetainingCapacity();
+ c.bytes.clearRetainingCapacity();
+ c.seen.clearRetainingCapacity();
+ c.pins.clearRetainingCapacity();
+ c.epoch = e;
+ if (c.epoch.?.owns(@intFromPtr(p)) == null) @panic("rollback: the core is not its epoch's");
+ try c.object(Pardes, p);
+ e.begin();
+ c.held = true;
+ }
+
+ /// The core as it was when the copy was taken.
+ pub fn restore(c: *Copy) void {
+ std.debug.assert(c.held);
+ 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;
+ }
+
+ /// The speculation was right: the copy is not wanted.
+ pub fn release(c: *Copy) void {
+ std.debug.assert(c.held);
+ c.check();
+ c.epoch.?.keep();
+ c.held = false;
+ }
+
+ 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) {
+ 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 });
+ @panic("rollback: a pinned blob was written in place");
+ };
+ }
+
+ fn save(c: *Copy, addr: usize, len: usize) Error!void {
+ if (len == 0) return;
+ const off = c.bytes.items.len;
+ try c.bytes.appendSlice(c.meta, @as([*]const u8, @ptrFromInt(addr))[0..len]);
+ try c.regions.append(c.meta, .{ .addr = addr, .off = off, .len = len });
+ }
+
+ /// Whether the value at `addr` of type `T` was reached before.
+ fn reached(c: *Copy, comptime T: type, addr: usize) Error!bool {
+ const key: Seen = .{ .addr = addr, .ty = @intFromPtr(@typeName(T).ptr) };
+ const got = try c.seen.getOrPut(c.meta, key);
+ return got.found_existing;
+ }
+
+ /// The allocation at `addr`, saved once, whatever reaches it.
+ fn allocation(c: *Copy, addr: usize) Error!?usize {
+ const entry = c.epoch.?.owns(addr) orelse return null;
+ if (try c.reached(void, addr)) return entry.len;
+ try c.save(addr, entry.len);
+ return entry.len;
+ }
+
+ fn visit(c: *Copy, comptime T: type, v: *const T) Error!void {
+ if (comptime !heapIn(T, 0)) return;
+ switch (@typeInfo(T)) {
+ .optional => |o| if (v.*) |*payload| try c.visit(o.child, payload),
+ .array => |a| if (comptime heapIn(a.child, 0)) for (v) |*e| try c.visit(a.child, e),
+ .pointer => |p| switch (p.size) {
+ .one => try c.object(p.child, v.*),
+ .slice => try c.slice(p.child, v.*),
+ // No length to walk by: its keeper's (a C handle's buffer).
+ else => {},
+ },
+ .@"struct" => |s| {
+ if (comptime walk.machinery(T)) return;
+ // A terminal: the authority's (its emulator is never written
+ // by a speculation: terminal.zig's guards).
+ if (comptime @hasDecl(T, "digest") and @TypeOf(T.digest) == fn (*const T, *walk.Hasher) void) return;
+ if (s.layout == .@"packed") return;
+ // std's lists (a safe build's have a third field, a lock).
+ if (comptime walk.isList(T)) {
+ if (v.capacity == 0) return;
+ _ = try c.allocation(@intFromPtr(v.items.ptr));
+ const E = @typeInfo(@FieldType(T, "items")).pointer.child;
+ if (comptime heapIn(E, 0)) for (v.items) |*e| try c.visit(E, e);
+ return;
+ }
+ if (comptime @hasDecl(T, "KV") and @hasDecl(T, "Hash") and @hasField(T, "metadata")) {
+ const m = v.metadata orelse return;
+ // std's header sits before the metadata, at the start
+ // of the one allocation.
+ const header = std.mem.alignForward(usize, 2 * @sizeOf(usize) + @sizeOf(u32), @alignOf(usize));
+ _ = try c.allocation(@intFromPtr(m) - header);
+ var it = v.iterator();
+ while (it.next()) |entry| {
+ try c.visit(@TypeOf(entry.key_ptr.*), entry.key_ptr);
+ try c.visit(@TypeOf(entry.value_ptr.*), entry.value_ptr);
+ }
+ return;
+ }
+ if (comptime @hasField(T, "raw") and s.field_names.len == 1 and @hasDecl(T, "load")) return;
+ if (comptime @hasField(T, "any_future")) return;
+ if (comptime @hasField(T, "bit_length") and @hasField(T, "masks") and s.field_names.len == 2) {
+ if (v.bit_length == 0) return;
+ _ = try c.allocation(@intFromPtr(v.masks) - @sizeOf(@typeInfo(@FieldType(T, "masks")).pointer.child));
+ return;
+ }
+ inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| {
+ // What a digest covers, the caches made from it and this
+ // process's own (the views not live are among it): a
+ // safe build's free writes over what it frees, so what
+ // the speculation freed would come back as that. Not the
+ // 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;
+ c.where = @typeName(T) ++ "." ++ name;
+ c.pinnable = comptime walk.blob(T, name);
+ if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) {
+ const len = comptime walk.lengthOf(T, name).?;
+ if (comptime heapIn(@typeInfo(F).array.child, 0)) for (@field(v, name)[0..walk.lengthIn(v, len)]) |*e| try c.visit(@typeInfo(F).array.child, e);
+ } else try c.visit(F, &@field(v, name));
+ }
+ },
+ .@"union" => switch (v.*) {
+ inline else => |*payload| try c.visit(@TypeOf(payload.*), payload),
+ },
+ .error_union => |e| if (v.*) |*payload| try c.visit(e.payload, payload) else |_| {},
+ else => {},
+ }
+ }
+
+ fn object(c: *Copy, comptime P: type, ptr: *const P) Error!void {
+ if (comptime walk.machinery(P)) return;
+ const addr = @intFromPtr(ptr);
+ if (try c.reached(P, addr)) return;
+ if (comptime @hasDecl(P, "digest") and @TypeOf(P.digest) == fn (*const P, *walk.Hasher) void) return;
+ if (c.epoch.?.owns(addr) != null) {
+ _ = try c.reached(void, addr);
+ try c.fields(P, ptr);
+ }
+ try c.visit(P, ptr);
+ }
+
+ /// A struct's bytes, field by field where it says what its fields are:
+ /// all of them (this process's own too, which the epoch's frees would
+ /// leave pointing at nothing), but the queues a step drains and the
+ /// frame statistics (numbers, megabytes of them), and an array only as
+ /// far as its length says.
+ fn fields(c: *Copy, comptime T: type, v: *const T) Error!void {
+ if (comptime @typeInfo(T) != .@"struct" or !@hasDecl(T, "replica")) return c.save(@intFromPtr(v), @sizeOf(T));
+ const s = @typeInfo(T).@"struct";
+ inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| {
+ if (attr.@"comptime") continue;
+ if (comptime (annotated(T, "local", name) or annotated(T, "derived", name) or annotated(T, "authority", name)) and unsaved(name)) continue;
+ const at = @intFromPtr(&@field(v, name));
+ if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) {
+ try c.save(at, walk.lengthIn(v, comptime walk.lengthOf(T, name).?) * @sizeOf(@typeInfo(F).array.child));
+ } else if (comptime annotatedStruct(F)) {
+ try c.fields(F, &@field(v, name));
+ } else if (comptime @typeInfo(F) == .array and annotatedStruct(@typeInfo(F).array.child)) {
+ for (&@field(v, name)) |*e| try c.fields(@typeInfo(F).array.child, e);
+ } else try c.save(at, @sizeOf(F));
+ }
+ }
+
+ fn slice(c: *Copy, comptime E: type, s: []const E) Error!void {
+ if (s.len == 0) return;
+ const addr = @intFromPtr(s.ptr);
+ if (try c.reached([]const E, addr)) return;
+ if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) {
+ // A blob of rows with allocations of their own is pinned whole:
+ // they are as immutable as it, and kept alive with it.
+ const bytes = std.mem.sliceAsBytes(s);
+ try c.pins.append(c.meta, .{ .addr = addr, .len = bytes.len, .hash = if (checked) std.hash.Wyhash.hash(0, bytes) else 0, .where = c.where });
+ return;
+ }
+ _ = try c.allocation(addr);
+ if (comptime heapIn(E, 0)) for (s) |*e| try c.visit(E, e);
+ }
+};
+
+fn annotatedStruct(comptime T: type) bool {
+ return @typeInfo(T) == .@"struct" and @hasDecl(T, "replica");
+}
+
+/// The queues every step drains (empty between steps, asserted when a copy
+/// is taken: what is in their slots is nothing), the frame statistics
+/// (numbers, and a static name), and the rows a terminal was last read as
+/// (a grid's worth of text, emptied when a copy is taken and when it is
+/// put back: src/replica.zig), and a replica's predicted echo (src/echo.zig:
+/// the replica's, never its core's). And the store and Recent, a replica's
+/// own: on the host's heap (Pardes.recentGpa), which the epoch never puts a
+/// free off for, so their bytes put back would point at what is freed. A
+/// step reads what the authority holds of them off the tape
+/// (tape.authority), never a replica's.
+fn unsaved(comptime name: []const u8) bool {
+ return std.mem.eql(u8, name, "effects") or std.mem.eql(u8, name, "in_q") or std.mem.eql(u8, name, "frames") or
+ std.mem.eql(u8, name, "shell_rows") or std.mem.eql(u8, name, "echo") or std.mem.eql(u8, name, "store") or
+ std.mem.eql(u8, name, "recent");
+}
+
+fn annotated(comptime T: type, comptime kind: []const u8, comptime name: []const u8) bool {
+ @setEvalBranchQuota(100_000);
+ if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), kind)) return false;
+ inline for (@field(T.replica, kind)) |n| if (comptime std.mem.eql(u8, n, name)) return true;
+ return false;
+}
+
+/// A field no walk sees into (a C handle, a function): its own keeper's.
+fn opaqueTo(comptime F: type) bool {
+ return switch (@typeInfo(F)) {
+ .optional => |o| opaqueTo(o.child),
+ .pointer => |p| p.size == .many or p.size == .c or switch (@typeInfo(p.child)) {
+ .@"opaque", .@"fn" => true,
+ else => false,
+ },
+ else => false,
+ };
+}
+
+/// Whether a `T` can hold a pointer to the heap at all (else a walk of it
+/// finds nothing to save). Deep types count as yes.
+fn heapIn(comptime T: type, comptime depth: u32) bool {
+ if (depth > 12) return true;
+ return switch (@typeInfo(T)) {
+ .void, .null, .undefined, .bool, .int, .float, .@"enum", .error_set, .comptime_int, .comptime_float, .enum_literal, .type => false,
+ .optional => |o| heapIn(o.child, depth + 1),
+ .array => |a| a.len > 0 and heapIn(a.child, depth + 1),
+ .pointer => true,
+ .error_union => |e| heapIn(e.payload, depth + 1),
+ .@"struct" => |s| blk: {
+ if (s.layout == .@"packed") break :blk false;
+ for (s.field_types, s.field_attrs) |F, attr| if (!attr.@"comptime" and heapIn(F, depth + 1)) break :blk true;
+ break :blk false;
+ },
+ .@"union" => |u| blk: {
+ for (u.field_types) |F| if (heapIn(F, depth + 1)) break :blk true;
+ break :blk false;
+ },
+ else => true,
+ };
+}
+
+test "a copy put back is the core as it was; one let go keeps what was done" {
+ 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 = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa });
+ p.pump(.{}) catch {};
+ const before = walk.digest(Pardes, p);
+ var c: Copy = .{};
+ defer c.deinit();
+ const typed = "ox y z";
+ try c.take(&e, p);
+ for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } });
+ p.update(.{ .key = .{ .cp = pardes.Key.escape } });
+ p.pump(.{}) catch {};
+ const edited = walk.digest(Pardes, p);
+ try std.testing.expect(edited != before);
+ 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);
+ for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } });
+ p.update(.{ .key = .{ .cp = pardes.Key.escape } });
+ p.pump(.{}) catch {};
+ try std.testing.expectEqual(edited, walk.digest(Pardes, p));
+ c.release();
+ try std.testing.expectEqual(edited, walk.digest(Pardes, p));
+ p.deinit();
+ try std.testing.expectEqual(@as(usize, 0), e.live.count());
+}
+
+test "a view's slot while it is 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.
+ var e: Epoch = .{};
+ defer e.deinit();
+ const gpa = e.allocator();
+ const p = try Pardes.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa });
+ defer p.deinit();
+ p.pump(.{}) catch {};
+ _ = p.openView() orelse return error.NoView;
+ // View 0's column tag has a text of its own; out to view 1 and back.
+ const text = "the column tag of view 0, its own";
+ p.col_tags[0].own = try gpa.dupe(u8, text);
+ p.toView(1);
+ p.toView(0);
+ // The live view drops it, and its memory is another's: something the
+ // copy has no business saving.
+ const was = p.col_tags[0].own.?;
+ gpa.free(was);
+ p.col_tags[0].own = null;
+ const other = try gpa.alloc(u8, text.len);
+ defer gpa.free(other);
+ if (other.ptr != was.ptr) return error.SkipZigTest; // the heap handed out another
+ @memset(other, 'a');
+ var c: Copy = .{};
+ defer c.deinit();
+ 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(std.mem.allEqual(u8, other, 'b'));
+}
+
+test "a register's texts are pinned, not copied, and come back whole" {
+ 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 = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa });
+ p.pump(.{}) catch {};
+ // A terminal's whole grid yanked: megabytes, and joined once read.
+ const grid = try std.testing.allocator.alloc(u8, 2 << 20);
+ defer std.testing.allocator.free(grid);
+ @memset(grid, 'y');
+ const reg = pardes.Registers.default;
+ p.registers.put(gpa, reg, grid, 0, 1, true);
+ _ = p.registers.text(gpa, reg) orelse return error.NoText;
+ var c: Copy = .{};
+ defer c.deinit();
+ try c.take(&e, p);
+ try std.testing.expect(c.savedBytes() < 1 << 20);
+ 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();
+ 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'));
+ p.deinit();
+ try std.testing.expectEqual(@as(usize, 0), e.live.count());
+}
+
+test "a file's location rows are pinned whole, with what they own, and come back" {
+ const locations = @import("locations.zig");
+ 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 = "mise.toml", .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;
+ // A search's rows: each its own path.
+ const rows = try gpa.alloc(locations.Row, 500);
+ for (rows) |*row| row.* = .{ .kind = .match, .path = try gpa.dupe(u8, "src/rollback.zig"), .at = .{}, .location_end = 0, .code_start = 0 };
+ f.location_rows = rows;
+ var c: Copy = .{};
+ defer c.deinit();
+ try c.take(&e, p);
+ try std.testing.expect(c.pinnedBytes() >= rows.len * @sizeOf(locations.Row));
+ // A speculation's new search drops them, and is undone.
+ locations.freeRows(gpa, f.location_rows);
+ f.location_rows = &.{};
+ 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();
+ try std.testing.expectEqual(@as(usize, 0), e.live.count());
+}
+
+/// `Look <name>`, the name a file of the repository's, absolute.
+fn lookAt(buf: []u8, name: []const u8) ![]const u8 {
+ var cwd: [std.fs.max_path_bytes]u8 = undefined;
+ const dir = std.c.getcwd(&cwd, cwd.len) orelse return error.NoCwd;
+ return std.fmt.bufPrint(buf, "Look {s}/{s}", .{ std.mem.span(@as([*:0]u8, @ptrCast(dir))), name });
+}
+
+test "a rollback leaves the store and Recent as a speculation left them: they live on the host's heap, which no copy holds" {
+ 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 = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa });
+ p.pump(.{}) catch {};
+ var line: [std.fs.max_path_bytes + 16]u8 = undefined;
+ p.update(.{ .command = try lookAt(&line, "build.zig.zon") });
+ p.update(.{ .command = "Del" });
+ p.pump(.{}) catch {};
+ try std.testing.expectEqual(@as(usize, 1), p.store.closed.items.len);
+ // Both lists full to what they hold: the next of each moves them.
+ p.store.closed.shrinkAndFree(p.recentGpa(), p.store.closed.items.len);
+ p.recent.entries.shrinkAndFree(p.recentGpa(), p.recent.entries.items.len);
+ const recents = p.recent.entries.items.len;
+ var c: Copy = .{};
+ defer c.deinit();
+ try c.take(&e, p);
+ // A speculation opens a file and closes it (a Del a replica applies at
+ // once), and is undone.
+ p.update(.{ .command = try lookAt(&line, "build.zig") });
+ p.update(.{ .command = "Del" });
+ p.pump(.{}) catch {};
+ 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"));
+ try std.testing.expectEqual(recents + 1, p.recent.entries.items.len);
+ p.deinit();
+ try std.testing.expectEqual(@as(usize, 0), e.live.count());
+}
+
+test "a view drawn outside a step (a replica's own, another live) leaves the live view's slot holding nothing a rollback could put old bytes back through" {
+ var e: Epoch = .{};
+ defer e.deinit();
+ const gpa = e.allocator();
+ const p = try Pardes.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa });
+ defer p.deinit();
+ p.pump(.{}) catch {};
+ _ = p.openView() orelse return error.NoView;
+ const text = "the column tag of view 0, its own";
+ p.col_tags[0].own = try gpa.dupe(u8, text);
+ // View 1 read (as a replica client's frontend reads its own) while view
+ // 0 is live: 0 parked and put back.
+ const Read = struct {
+ fn read(_: void, _: *Pardes) anyerror!void {}
+ };
+ try pardes.views.within(p, 1, {}, Read.read);
+ const was = p.col_tags[0].own.?;
+ gpa.free(was);
+ p.col_tags[0].own = null;
+ const other = try gpa.alloc(u8, text.len);
+ defer gpa.free(other);
+ if (other.ptr != was.ptr) return error.SkipZigTest; // the heap handed out another
+ @memset(other, 'a');
+ var c: Copy = .{};
+ defer c.deinit();
+ try c.take(&e, p);
+ @memset(other, 'b');
+ c.restore();
+ try std.testing.expect(std.mem.allEqual(u8, other, 'b'));
+}