summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-29 18:19:13 -0300
committerGabriel Schneider <[email protected]>2026-10-29 20:19:19 -0300
commit3b57a72becd6dd6700d996c9c5c000e1cb53e076 (patch)
tree58e59aefe6ae067d95ce4ddf94e8155a9edd3b5a /src
parent8bad8e3701716a5f2d82d8255a39f3743b13fb96 (diff)
downloadpardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.tar.gz
pardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.zip
phase 5 part A: the speculation and rollback engine, in one process: a walker copy put back where it was, replicas that apply their own input at once and take the authority's tape as the truth, and a harness of typists over delayed links
src/rollback.zig: the replica core's allocator (`Epoch`) knows every allocation, and while a copy is held puts off frees of what was there before and refuses to grow it in place, so what the core held stays where it was. The copy (`Copy`) is the digest's walk saving the bytes of every allocation it reaches, field by field (the derived caches and this process's own too: a safe build's free writes over what it frees, and the frame arena points at what the epoch then frees), but the queues a step drains and the frame statistics; a file's text, its line index and its undo snapshots are pinned instead (made anew at each edit, never written; now freed raw everywhere), checked unchanged in a safe build. Put back, each allocation's bytes go back over it, the epoch's allocations are freed and its put-off frees forgotten; let go, they are made. Tree-sitter's trees, the C heap's, are held the same way (syntax.held_trees). src/replica.zig: an `Authority` records its core's every input to a tape in memory and hands each client's input back as a unit (origin, sequence number, its tape); a `Replica` applies its own input at once, as the authority will (update, then pump), recorded by its own tape (tape.zig's speculation mode), and for each unit in order drops its pending head when the authority recorded the same (inputs, host calls and answers: the fast path), else puts the copy back, replays the units since and this one (every digest checked) and applies its pending inputs again. A host call or a syscall stops a speculation: it is answered harmlessly, undone when it returns, and the input waits for the authority's answer; a clock or environment read is a guess the comparison checks; an emulator is the authority's (terminal.zig's writers stop a speculation; a safe build asserts none changed). The view's events (a resize, the pointer) wait. Messages are bytes: no transport yet. Each client has a view of its own (src/views.zig): the authority goes into it before the client's input (`toView`, taped), the replica's speculation the same, and the copy walks the views not live too (`parked`, each pane's `pv`). test/replicas.zig (`zig build replicas`): one authority and N replicas, a view each (`--shared` puts them in one), each client typing monkey.zig's mix at 50-200 ms over its own link (half the RTT plus 10% jitter, in order), the authority's pty echoing 2 ms later; gates: no replica diverges, every replica's digest is the authority's at quiescence; reported per RTT: inputs applied at once, stopped, waiting, fast paths, rollbacks (mispredicted, foreign), and what a speculative apply, a copy and a rollback cost. 3 clients x 100 inputs at 30, 80 and 207 ms: no divergence over 12 Debug seeds and 20 ReleaseFast ones with a filled heap; ReleaseFast p99 a speculative apply under 0.2 ms, a rollback under 1.6 ms. `zig build rollback-bench` times the real copy now (take, release, an edit, restore). What the replicas found, fixed: a release build reads what the heap had where Debug's fill made two cores agree: `col_panes` and `restore_buf` digested undefined (zeroed now), `terminal.State.reply_dropped` never set at create, `Text.sels` and `PendingPipe.ranges` digested past their length (a walker `len` cuts a slice too). PARDES_REPLICA_FILL fills a replica's allocations to show what is left. Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'src')
-rw-r--r--src/File.zig14
-rw-r--r--src/Pipe.zig2
-rw-r--r--src/Text.zig6
-rw-r--r--src/memory.zig9
-rw-r--r--src/pardes.zig11
-rw-r--r--src/replica.zig578
-rw-r--r--src/rollback.zig496
-rw-r--r--src/syntax.zig24
-rw-r--r--src/tape.zig236
-rw-r--r--src/terminal.zig17
-rw-r--r--src/walk.zig24
11 files changed, 1385 insertions, 32 deletions
diff --git a/src/File.zig b/src/File.zig
index dd6b2d34..84222191 100644
--- a/src/File.zig
+++ b/src/File.zig
@@ -1159,10 +1159,12 @@ 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);
- if (ntwins == 0) p.gpa.free(file.content);
+ // 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).
+ if (ntwins == 0) pardes.memory.freeUnfilled(p.gpa, file.content);
if (file.listing) |listing| p.gpa.free(listing.names);
if (file.mini) |*mini| mini.deinit(p.gpa);
- if (file.line_starts.len > 0 and !index_shared) p.gpa.free(file.line_starts);
+ if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, file.line_starts);
if (file.highlights.len > 0) p.tree_sitter_gpa.free(file.highlights);
p.gpa.free(file.pager_spans);
locations.freeRows(p.gpa, file.location_rows);
@@ -1264,7 +1266,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void {
};
// The clock the session that recorded read (src/tape.zig).
f.mtime = pardes.tape.value(.mtime, pardes.ctlfs.events.now, .{});
- if (f.line_starts.len > 0) p.gpa.free(f.line_starts);
+ if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts);
f.line_starts = starts;
if (f.highlights.len > 0) p.tree_sitter_gpa.free(f.highlights);
f.highlights = &.{};
@@ -1276,7 +1278,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void {
const tf = &t.file.?;
// Its own index, built while the shared one was empty, goes; the
// shared one, freed above, is replaced.
- if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) p.gpa.free(tf.line_starts);
+ if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, tf.line_starts);
tf.content = f.content;
tf.line_starts = f.line_starts;
tf.revision = f.revision;
@@ -1498,8 +1500,8 @@ pub fn relink(p: *Pardes, of: usize, id: usize, dot: ?[2]u32) void {
sf.twin = p.next_twin;
p.next_twin +%= 1;
}
- p.gpa.free(f.content);
- if (f.line_starts.len > 0) p.gpa.free(f.line_starts);
+ pardes.memory.freeUnfilled(p.gpa, f.content);
+ if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts);
f.history.destroy(p.gpa);
f.content = sf.content;
f.line_starts = sf.line_starts;
diff --git a/src/Pipe.zig b/src/Pipe.zig
index 850f9c64..239a94e4 100644
--- a/src/Pipe.zig
+++ b/src/Pipe.zig
@@ -52,6 +52,8 @@ pub fn pipeMarker(how: modal.Normal.PipeBehavior) []const u8 {
}
pub const PendingPipe = struct {
+ /// The digest's walk (src/walk.zig) of the ranges, as far as they go.
+ pub const replica = .{ .len = .{.{ "ranges", "nranges" }} };
id: u32,
pane: usize,
serial: u32,
diff --git a/src/Text.zig b/src/Text.zig
index 3f107542..da4be590 100644
--- a/src/Text.zig
+++ b/src/Text.zig
@@ -49,9 +49,9 @@ pub const SelRange = struct {
sticky: i32 = -1,
};
-/// The replay digest's walk (src/walk.zig) of the histories: as far as
-/// they go.
-pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" } } };
+/// The replay digest's walk (src/walk.zig) of the histories and the ranges:
+/// as far as they go (the ranges' room is made whole and used `nsel` deep).
+pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" }, .{ "sels", "nsel" } } };
what: What = .body,
/// The characters of a text that holds its own (gpa-owned): everything but
diff --git a/src/memory.zig b/src/memory.zig
index 47bd755d..1d082964 100644
--- a/src/memory.zig
+++ b/src/memory.zig
@@ -421,6 +421,15 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void {
if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress());
}
+/// `freeUnfilled` for a slice of any element: a text's line index, made
+/// anew at every edit too (and pinned by a replica's rollback copy,
+/// src/rollback.zig, which a safe build's overwrite would spoil).
+pub fn freeRaw(allocator: Allocator, items: anytype) void {
+ const E = @typeInfo(@TypeOf(items)).pointer.child;
+ const bytes = std.mem.sliceAsBytes(items);
+ if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(E), @returnAddress());
+}
+
/// Gives free memory back to the system, the arenas' and libc's, inside its
/// heap too: after a big result is formatted or a big pane torn down, the
/// tree-sitter arena kept 73 MiB of emptied buckets resident and glibc what
diff --git a/src/pardes.zig b/src/pardes.zig
index 75e91ee9..5d889c86 100644
--- a/src/pardes.zig
+++ b/src/pardes.zig
@@ -65,6 +65,8 @@ pub const tape = @import("tape.zig");
pub const walk = @import("walk.zig");
pub const screen_state = if (terminal_panes) @import("screen_state.zig") else struct {};
pub const views = @import("views.zig");
+pub const rollback = @import("rollback.zig");
+pub const replica = @import("replica.zig");
pub const image = @import("image.zig");
pub const dump = @import("dump.zig");
pub const lsp = @import("lsp/lsp.zig");
@@ -474,6 +476,8 @@ pub const Loc = struct {
};
test {
+ _ = @import("rollback.zig");
+ _ = @import("replica.zig");
_ = @import("modal.zig");
_ = @import("tagline.zig");
_ = @import("hunks.zig");
@@ -4412,7 +4416,10 @@ pub const Pardes = struct {
// layout: columns own x by weight; panes own y by vweight within a column.
ncol: usize = 0,
col_weight: [MAX_COLS]u64 = @splat(column_weight_unit),
- col_panes: [MAX_COLS][MAX_PANES]usize = undefined,
+ // Zeroed, not undefined: a digest takes the whole of it, a release
+ // build's heap leaves its unused slots whatever was there before, and
+ // two replicas must agree on them (src/replica.zig).
+ col_panes: [MAX_COLS][MAX_PANES]usize = @splat(@splat(0)),
col_n: [MAX_COLS]usize = @splat(0),
/// Each column's tag and the workspace's: Texts like a pane's tag, with
/// no prefix, showing a default until someone edits them.
@@ -4698,7 +4705,7 @@ pub const Pardes = struct {
/// a Restore builtin wants this dump loaded into the live session; the
/// shell consumes it via takeRestore each frame (restore contents stay host-fed)
restore_req: ?[]const u8 = null,
- restore_buf: [1024]u8 = undefined,
+ restore_buf: [1024]u8 = @splat(0),
surface: Surface = .{},
/// The view the fields above are of: whose layout, focus, pointer and
diff --git a/src/replica.zig b/src/replica.zig
new file mode 100644
index 00000000..42d94503
--- /dev/null
+++ b/src/replica.zig
@@ -0,0 +1,578 @@
+//! A session's replicas (docs/next-daemon.md, phase 5 part A): the authority
+//! orders every input and records what its core consumed (src/tape.zig);
+//! each replica runs a core of its own, applies its own inputs at once, and
+//! takes the authority's stream as the truth.
+//!
+//! A replica's state is the confirmed position plus its own pending inputs,
+//! applied on top (a speculation, recorded as the authority would record
+//! it). For each unit of the authority's stream, in order:
+//! - its own pending head, recorded the same (inputs, host calls and
+//! answers): the head goes, nothing is redone (the fast path);
+//! - else the rollback copy is put back (src/rollback.zig), the confirmed
+//! units since it are replayed, then this one, and the pending inputs
+//! are applied again.
+//! A speculation that reaches a host call or a syscall (a Host function,
+//! a `tape.site`) or an emulator (the authority's) stops: the copy is put
+//! back and the input waits for the authority's answer, one RTT late but
+//! never wrong. Clock and environment reads (`tape.value`) are made here,
+//! and the comparison catches a guess the authority did not share.
+//!
+//! No transport: messages are bytes in and out. A client's input is its
+//! id, a sequence number and the event as detached/wire.zig frames it; a
+//! unit is the input's origin (0 for the authority's own: a pty's output, a
+//! tick), its sequence number and the authority's tape of it.
+const std = @import("std");
+const builtin = @import("builtin");
+const pardes = @import("pardes.zig");
+const tape = @import("tape.zig");
+const rollback = @import("rollback.zig");
+const walk = @import("walk.zig");
+const wire = @import("detached/wire.zig");
+const Allocator = std.mem.Allocator;
+const Pardes = pardes.Pardes;
+
+const checked = builtin.mode == .debug or builtin.mode == .safe;
+const head_len = 6; // origin or client: u16le, seq: u32le
+/// Confirmed units fast-pathed under one copy before it is taken afresh:
+/// a rollback replays them all.
+const rebase_after = 32;
+
+fn header(buf: []u8, who: u16, seq: u32) void {
+ std.mem.writeInt(u16, buf[0..2], who, .little);
+ std.mem.writeInt(u32, buf[2..6], seq, .little);
+}
+
+pub const Unit = struct { origin: u16, seq: u32, tape: []const u8 };
+
+pub fn parseUnit(msg: []const u8) ?Unit {
+ if (msg.len < head_len) return null;
+ return .{ .origin = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .tape = msg[head_len..] };
+}
+
+pub const Input = struct { client: u16, seq: u32, event: pardes.Event };
+
+/// A client's input message; its event borrows `msg`.
+pub fn parseInput(msg: []const u8) ?Input {
+ if (msg.len < head_len) return null;
+ const f = (wire.framed(msg[head_len..]) catch return null) orelse return null;
+ const ev = switch (wire.decodeClient(f.tag, f.payload) catch return null) {
+ .event => |ev| ev,
+ else => return null,
+ };
+ return .{ .client = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .event = ev };
+}
+
+/// The core whose tape is `t`, stepped: tape.on is process-wide, and so
+/// are syntax.zig's held trees, so one process can step several.
+const Stepping = struct {
+ tape: ?*tape.Tape,
+ trees: ?*pardes.syntax.HeldTrees,
+
+ fn begin(t: *tape.Tape, epoch: ?*rollback.Epoch) Stepping {
+ const was: Stepping = .{ .tape = tape.on, .trees = pardes.syntax.held_trees };
+ tape.on = t;
+ rollback.Epoch.select(epoch);
+ return was;
+ }
+
+ fn end(was: Stepping) void {
+ tape.on = was.tape;
+ pardes.syntax.held_trees = was.trees;
+ }
+};
+
+fn nowNs() u64 {
+ return pardes.FrameStats.nowNs();
+}
+
+// ---- the authority ----
+
+pub const Authority = struct {
+ gpa: Allocator,
+ t: tape.Tape,
+ core: *Pardes,
+ host: pardes.Host,
+ out: std.ArrayListUnmanaged(u8) = .empty,
+ seq: u32 = 0,
+ /// Each client's view (src/views.zig): its own layout, focus and
+ /// cursors over the session's text. The first client has the session's.
+ view_of: [64]u8 = @splat(0),
+
+ /// A session booted with `opts`; `unit` is its first, which a replica
+ /// is made from.
+ pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host) !*Authority {
+ // A replay gives its core every allocator (tape.zig), and a digest
+ // tells an allocator from none.
+ var opts = options;
+ opts.image_allocator = opts.image_allocator orelse gpa;
+ opts.pdf_allocator = opts.pdf_allocator orelse gpa;
+ opts.tree_sitter_allocator = opts.tree_sitter_allocator orelse gpa;
+ opts.frame_allocator = opts.frame_allocator orelse gpa;
+ const a = try gpa.create(Authority);
+ errdefer gpa.destroy(a);
+ a.* = .{ .gpa = gpa, .t = tape.memory(gpa), .core = undefined, .host = host };
+ const was = Stepping.begin(&a.t, null);
+ defer was.end();
+ a.core = try Pardes.init(gpa, opts);
+ a.core.host = host;
+ a.core.pump(host) catch {};
+ return a;
+ }
+
+ pub fn deinit(a: *Authority) void {
+ const was = Stepping.begin(&a.t, null);
+ a.core.deinit();
+ was.end();
+ tape.release(&a.t);
+ a.out.deinit(a.gpa);
+ a.gpa.destroy(a);
+ }
+
+ /// What was recorded since the last unit, as one (the boot's, a setup's
+ /// done straight on the core).
+ pub fn unit(a: *Authority, origin: u16, seq: u32) ![]const u8 {
+ a.out.clearRetainingCapacity();
+ try a.out.appendNTimes(a.gpa, 0, head_len);
+ header(a.out.items, origin, seq);
+ try a.out.appendSlice(a.gpa, tape.taken(&a.t));
+ tape.clearTaken(&a.t);
+ return a.out.items;
+ }
+
+ /// An input of the authority's own (a pty's output, a tick, a setup's
+ /// command), recorded into the unit being made.
+ pub fn apply(a: *Authority, ev: pardes.Event) void {
+ const was = Stepping.begin(&a.t, null);
+ a.core.update(ev);
+ a.core.pump(a.host) catch {};
+ was.end();
+ }
+
+ /// One of the authority's own inputs, as its unit.
+ pub fn local(a: *Authority, ev: pardes.Event) ![]const u8 {
+ a.apply(ev);
+ a.seq += 1;
+ return a.unit(0, a.seq);
+ }
+
+ /// A view of its own for `client`, as its unit; which it is.
+ pub fn openView(a: *Authority, client: u16) !struct { view: u8, unit: []const u8 } {
+ const was = Stepping.begin(&a.t, null);
+ const k = a.core.openView() orelse {
+ was.end();
+ return error.TooManyViews;
+ };
+ a.core.pump(a.host) catch {};
+ was.end();
+ a.view_of[client] = k;
+ a.seq += 1;
+ return .{ .view = k, .unit = try a.unit(0, a.seq) };
+ }
+
+ /// One client's input, applied in the order it came, in its view: the
+ /// unit every replica takes.
+ pub fn take(a: *Authority, msg: []const u8) ![]const u8 {
+ const in = parseInput(msg) orelse return error.BadInput;
+ const was = Stepping.begin(&a.t, null);
+ a.core.toView(a.view_of[in.client]);
+ a.core.update(in.event);
+ a.core.pump(a.host) catch {};
+ was.end();
+ return a.unit(in.client, in.seq);
+ }
+};
+
+// ---- a replica ----
+
+pub const Stats = struct {
+ inputs: u32 = 0,
+ /// Applied at once and clean.
+ speculated: u32 = 0,
+ /// Stopped at a host call, a syscall or an emulator: waits one RTT.
+ stopped: u32 = 0,
+ /// Not tried: an event of the view's (a resize, the pointer), phase 4's.
+ unspeculated: u32 = 0,
+ /// The authority's unit was the pending head, recorded the same.
+ fast: u32 = 0,
+ /// The copy put back: the head recorded otherwise (a guess of the clock
+ /// the authority did not share), or another's unit first.
+ mispredicted: u32 = 0,
+ foreign: u32 = 0,
+ rebases: u32 = 0,
+ units: u32 = 0,
+ /// Nanoseconds: one speculative apply, a copy taken, a rollback (the
+ /// copy put back, the confirmed units replayed, the pending reapplied).
+ spec_ns: std.ArrayListUnmanaged(u64) = .empty,
+ copy_ns: std.ArrayListUnmanaged(u64) = .empty,
+ rollback_ns: std.ArrayListUnmanaged(u64) = .empty,
+ copy_bytes: u64 = 0,
+ copies: u32 = 0,
+
+ pub fn deinit(s: *Stats, gpa: Allocator) void {
+ s.spec_ns.deinit(gpa);
+ s.copy_ns.deinit(gpa);
+ s.rollback_ns.deinit(gpa);
+ }
+};
+
+const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null };
+
+pub const Replica = struct {
+ gpa: Allocator,
+ id: u16,
+ /// Its own view of the session (Authority.openView's).
+ view: u8 = 0,
+ /// The core's allocator; its tapes and the engine's own lists are not.
+ epoch: rollback.Epoch = .{},
+ t: tape.Tape,
+ copy: rollback.Copy = .{},
+ pending: std.ArrayListUnmanaged(Pending) = .empty,
+ /// pending[0..applied] are applied on top of the confirmed position.
+ applied: usize = 0,
+ /// The pending input that waits for the authority (it stopped at a host
+ /// call, or is the view's), and those after it with it.
+ blocked: ?u32 = null,
+ /// Confirmed units fast-pathed since the copy was taken.
+ since: std.ArrayListUnmanaged([]u8) = .empty,
+ /// Pending inputs to apply again (after a rollback).
+ dirty: bool = false,
+ next_seq: u32 = 1,
+ stats: Stats = .{},
+ diverged: ?[]const u8 = null,
+ out: std.ArrayListUnmanaged(u8) = .empty,
+ /// Nanoseconds of the rollback being made, until its reapply.
+ recovering: ?u64 = null,
+
+ /// A replica of the session whose first unit is `first`.
+ pub fn init(gpa: Allocator, id: u16, first: []const u8) !*Replica {
+ const r = try gpa.create(Replica);
+ r.* = .{ .gpa = gpa, .id = id, .t = tape.memory(gpa) };
+ r.t.core_gpa = r.epoch.allocator();
+ r.confirm(first);
+ if (r.t.core == null) {
+ r.deinit();
+ return error.NoCore;
+ }
+ return r;
+ }
+
+ pub fn deinit(r: *Replica) void {
+ if (r.t.core) |c| {
+ const was = Stepping.begin(&r.t, &r.epoch);
+ if (r.copy.held) r.copy.restore();
+ c.deinit();
+ was.end();
+ }
+ r.copy.deinit();
+ for (r.pending.items) |p| r.freePending(p);
+ r.pending.deinit(r.gpa);
+ for (r.since.items) |u| r.gpa.free(u);
+ r.since.deinit(r.gpa);
+ r.out.deinit(r.gpa);
+ r.stats.deinit(r.gpa);
+ tape.release(&r.t);
+ if (r.diverged) |why| r.gpa.free(why);
+ r.epoch.deinit();
+ r.gpa.destroy(r);
+ }
+
+ pub fn core(r: *const Replica) *Pardes {
+ return r.t.core.?;
+ }
+
+ fn freePending(r: *Replica, p: Pending) void {
+ r.gpa.free(p.msg);
+ if (p.spec) |s| r.gpa.free(s);
+ }
+
+ /// The replica's own input: applied at once when it can be, and the
+ /// message for the authority returned (valid until the next call).
+ pub fn input(r: *Replica, ev: pardes.Event) ![]const u8 {
+ r.stats.inputs += 1;
+ const seq = r.next_seq;
+ r.next_seq += 1;
+ const room = try r.gpa.alloc(u8, head_len + wire.clientBound(.{ .event = ev }));
+ defer r.gpa.free(room);
+ const n = (try wire.encodeClient(room[head_len..], .{ .event = ev })).len;
+ header(room, r.id, seq);
+ const msg = try r.gpa.dupe(u8, room[0 .. head_len + n]);
+ try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg });
+ r.dirty = true;
+ r.settle();
+ r.out.clearRetainingCapacity();
+ try r.out.appendSlice(r.gpa, msg);
+ return r.out.items;
+ }
+
+ /// One unit of the authority's stream, in its order.
+ pub fn confirm(r: *Replica, msg: []const u8) void {
+ if (r.diverged != null) return;
+ const u = parseUnit(msg) orelse return r.fail("a unit too short to read");
+ r.stats.units += 1;
+ const was = Stepping.begin(&r.t, &r.epoch);
+ defer was.end();
+ if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and
+ tape.sameRecords(r.pending.items[0].spec.?, u.tape))
+ {
+ r.stats.fast += 1;
+ r.freePending(r.pending.orderedRemove(0));
+ r.applied -= 1;
+ if (r.applied == 0) {
+ // Nothing speculative on top any more: the state is the
+ // confirmed one.
+ r.copy.release();
+ rollback.Epoch.select(null);
+ r.clearSince();
+ return;
+ }
+ const kept = r.gpa.dupe(u8, u.tape) catch return r.fail("out of memory");
+ r.since.append(r.gpa, kept) catch return r.fail("out of memory");
+ if (r.since.items.len >= rebase_after) {
+ r.stats.rebases += 1;
+ r.toConfirmed();
+ r.dirty = true;
+ }
+ return;
+ }
+ if (r.applied > 0) {
+ if (u.origin == r.id) r.stats.mispredicted += 1 else r.stats.foreign += 1;
+ if (u.origin == r.id and std.c.getenv("PARDES_REPLICA_TRACE") != null) {
+ var w: std.Io.Writer.Allocating = .init(r.gpa);
+ defer w.deinit();
+ w.writer.print("replica {d}: its input {d} was recorded otherwise; it guessed:\n", .{ r.id, u.seq }) catch {};
+ tape.describe(r.pending.items[0].spec.?, &w.writer);
+ w.writer.print("and the authority recorded:\n", .{}) catch {};
+ tape.describe(u.tape, &w.writer);
+ std.debug.print("{s}", .{w.written()});
+ }
+ r.recovering = nowNs();
+ r.toConfirmed();
+ }
+ if (tape.replayUnit(&r.t, u.tape)) |why| {
+ if (std.c.getenv("PARDES_REPLICA_TRACE") != null) {
+ var w: std.Io.Writer.Allocating = .init(r.gpa);
+ defer w.deinit();
+ w.writer.print("replica {d}: the unit of {d}/{d} diverged: {s}\n", .{ r.id, u.origin, u.seq, why }) catch {};
+ tape.describe(u.tape, &w.writer);
+ std.debug.print("{s}", .{w.written()});
+ }
+ return r.fail(why);
+ }
+ if (u.origin == r.id) {
+ if (r.pending.items.len == 0 or r.pending.items[0].seq != u.seq) return r.fail("the authority confirmed an input this replica did not send next");
+ if (r.blocked == u.seq) r.blocked = null;
+ r.freePending(r.pending.orderedRemove(0));
+ }
+ r.dirty = true;
+ }
+
+ fn fail(r: *Replica, why: []const u8) void {
+ if (r.diverged == null) r.diverged = r.gpa.dupe(u8, why) catch return;
+ }
+
+ fn clearSince(r: *Replica) void {
+ for (r.since.items) |u| r.gpa.free(u);
+ r.since.clearRetainingCapacity();
+ }
+
+ /// Back to the confirmed position: the copy put back, the units fast-
+ /// pathed since replayed.
+ fn toConfirmed(r: *Replica) void {
+ if (r.copy.held) {
+ r.copy.restore();
+ rollback.Epoch.select(null);
+ }
+ r.applied = 0;
+ for (r.since.items) |u| if (tape.replayUnit(&r.t, u)) |why| return r.fail(why);
+ r.clearSince();
+ for (r.pending.items) |*p| if (p.spec) |s| {
+ r.gpa.free(s);
+ p.spec = null;
+ };
+ }
+
+ /// The pending inputs applied again, as far as they go.
+ pub fn settle(r: *Replica) void {
+ if (!r.dirty or r.diverged != null) return;
+ r.dirty = false;
+ const was = Stepping.begin(&r.t, &r.epoch);
+ defer was.end();
+ while (r.applied < r.pending.items.len and r.blocked != r.pending.items[r.applied].seq) if (!r.speculate()) break;
+ if (r.recovering) |t0| {
+ r.stats.rollback_ns.append(r.gpa, nowNs() - t0) catch {};
+ r.recovering = null;
+ }
+ }
+
+ /// pending[applied] applied on top: whether it was.
+ fn speculate(r: *Replica) bool {
+ const p = &r.pending.items[r.applied];
+ const in = parseInput(p.msg) orelse return false;
+ switch (in.event) {
+ .key, .paste, .command => {},
+ else => {
+ // The view's (a resize, the pointer): the authority's for
+ // now, phase 4's views to come.
+ r.stats.unspeculated += 1;
+ r.blocked = p.seq;
+ return false;
+ },
+ }
+ const c = r.core();
+ if (!r.copy.held) {
+ const t0 = nowNs();
+ r.copy.take(&r.epoch, c) catch return false;
+ rollback.Epoch.select(&r.epoch);
+ r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {};
+ r.stats.copy_bytes += r.copy.savedBytes();
+ r.stats.copies += 1;
+ }
+ var terminals: [pardes.MAX_PANES]u64 = undefined;
+ if (checked) terminalDigests(c, &terminals);
+ const t0 = nowNs();
+ tape.beginSpeculation(&r.t);
+ c.toView(r.view);
+ c.update(in.event);
+ c.pump(c.host) catch {};
+ const clean = tape.endSpeculation(&r.t);
+ const dt = nowNs() - t0;
+ // Where a blob was written, should one be: the input that did.
+ if (checked and std.c.getenv("PARDES_REPLICA_TRACE") != null) r.copy.check();
+ if (!clean) {
+ // Undone, and the earlier ones applied again on the confirmed
+ // position: this one waits for the authority.
+ r.stats.stopped += 1;
+ r.blocked = p.seq;
+ const upto = r.applied;
+ r.toConfirmed();
+ while (r.applied < upto) if (!r.speculate()) break;
+ if (r.applied == 0 and r.copy.held) {
+ r.copy.release();
+ rollback.Epoch.select(null);
+ }
+ return false;
+ }
+ if (checked) {
+ var after: [pardes.MAX_PANES]u64 = undefined;
+ terminalDigests(c, &after);
+ if (!std.mem.eql(u64, &terminals, &after)) @panic("replica: a speculation wrote a terminal's emulator");
+ }
+ r.stats.speculated += 1;
+ r.stats.spec_ns.append(r.gpa, dt) catch {};
+ p.spec = r.gpa.dupe(u8, tape.taken(&r.t)) catch return false;
+ tape.clearTaken(&r.t);
+ r.applied += 1;
+ return true;
+ }
+
+ /// Nothing pending and nothing applied: the replica is the authority's
+ /// confirmed state, which `digest` says.
+ pub fn quiet(r: *const Replica) bool {
+ return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held;
+ }
+
+ pub fn digest(r: *Replica) u64 {
+ const was = Stepping.begin(&r.t, &r.epoch);
+ defer was.end();
+ return tape.digestOf(r.core());
+ }
+};
+
+fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void {
+ for (p.panes, out) |slot, *d| {
+ d.* = 0;
+ const pane = slot orelse continue;
+ const state = pane.terminal orelse continue;
+ var h = walk.Hasher.init(0);
+ state.digest(&h);
+ d.* = h.final();
+ }
+}
+
+pub fn digestOf(a: *Authority) u64 {
+ const was = Stepping.begin(&a.t, null);
+ defer was.end();
+ return tape.digestOf(a.core);
+}
+
+const TestHost = struct {
+ fn watched(_: ?*anyopaque) bool {
+ return false;
+ }
+ const vtable: pardes.Host.VTable = .{ .watched = watched };
+ fn host() pardes.Host {
+ return .{ .vtable = &vtable };
+ }
+};
+
+fn key(r: *Replica, cp: u21, sent: *std.ArrayListUnmanaged([]u8)) !void {
+ const text = [_]u8{@intCast(cp & 0x7f)};
+ const msg = try r.input(.{ .key = .{ .cp = cp, .text = if (cp < 0x80 and cp >= 0x20) &text else "" } });
+ try sent.append(std.testing.allocator, try std.testing.allocator.dupe(u8, msg));
+}
+
+test "a replica's own keys apply at once, confirm on the fast path, and end at the authority's digest" {
+ const gpa = std.testing.allocator;
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host());
+ defer a.deinit();
+ const r = try Replica.init(gpa, 1, try a.unit(0, 0));
+ defer r.deinit();
+ try std.testing.expectEqual(digestOf(a), r.digest());
+ var sent: std.ArrayListUnmanaged([]u8) = .empty;
+ defer {
+ for (sent.items) |m| gpa.free(m);
+ sent.deinit(gpa);
+ }
+ for ("oabc") |k| try key(r, k, &sent);
+ try key(r, pardes.Key.escape, &sent);
+ try std.testing.expectEqual(@as(usize, 5), r.applied);
+ for (sent.items) |m| {
+ r.confirm(try a.take(m));
+ r.settle();
+ }
+ if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why});
+ try std.testing.expect(r.diverged == null);
+ try std.testing.expectEqual(@as(u32, 5), r.stats.fast);
+ try std.testing.expect(r.quiet());
+ try std.testing.expectEqual(digestOf(a), r.digest());
+}
+
+test "another client's input first: a replica rolls back, replays it and applies its own again" {
+ const gpa = std.testing.allocator;
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host());
+ defer a.deinit();
+ const first = try gpa.dupe(u8, try a.unit(0, 0));
+ defer gpa.free(first);
+ const r1 = try Replica.init(gpa, 1, first);
+ defer r1.deinit();
+ const r2 = try Replica.init(gpa, 2, first);
+ defer r2.deinit();
+ var s1: std.ArrayListUnmanaged([]u8) = .empty;
+ var s2: std.ArrayListUnmanaged([]u8) = .empty;
+ defer {
+ for (s1.items) |m| gpa.free(m);
+ for (s2.items) |m| gpa.free(m);
+ s1.deinit(gpa);
+ s2.deinit(gpa);
+ }
+ for ("oone") |k| try key(r1, k, &s1);
+ for ("Otwo") |k| try key(r2, k, &s2);
+ // The authority hears r2 first, then r1; both hear the units in that
+ // order.
+ for ([_]*std.ArrayListUnmanaged([]u8){ &s2, &s1 }) |list| for (list.items) |m| {
+ const u = try gpa.dupe(u8, try a.take(m));
+ defer gpa.free(u);
+ r1.confirm(u);
+ r1.settle();
+ r2.confirm(u);
+ r2.settle();
+ };
+ for ([_]*Replica{ r1, r2 }) |r| {
+ if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why});
+ try std.testing.expect(r.diverged == null);
+ try std.testing.expect(r.quiet());
+ try std.testing.expectEqual(digestOf(a), r.digest());
+ }
+ try std.testing.expect(r1.stats.foreign >= 1);
+ try std.testing.expectEqual(@as(u32, 4), r2.stats.fast);
+}
diff --git a/src/rollback.zig b/src/rollback.zig
new file mode 100644
index 00000000..9137b6f6
--- /dev/null
+++ b/src/rollback.zig
@@ -0,0 +1,496 @@
+//! 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 and its undo
+//! snapshots are pinned instead: an edit puts a new buffer in their
+//! place (File.setContentSpan) 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 this long or longer (`pinned`) 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;
+
+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.AutoHashMapUnmanaged(usize, Entry) = .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.AutoHashMapUnmanaged(Seen, void) = .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 };
+ pub const Error = Allocator.Error;
+
+ 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);
+ c.regions.clearRetainingCapacity();
+ c.bytes.clearRetainingCapacity();
+ c.seen.clearRetainingCapacity();
+ c.pins.clearRetainingCapacity();
+ c.epoch = e;
+ // A step drains these before it ends: between steps they hold
+ // nothing, and a copy is taken between steps.
+ std.debug.assert(p.effects_len == 0 and p.in_len == 0);
+ 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;
+ if (comptime @hasField(T, "items") and @hasField(T, "capacity") and s.field_names.len == 2) {
+ 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) and unsaved(name)))) continue;
+ if (comptime opaqueTo(F)) continue;
+ c.where = @typeName(T) ++ "." ++ name;
+ c.pinnable = comptime pinned(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) 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 (comptime !heapIn(E, 0)) if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) {
+ 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);
+ }
+};
+
+/// The blobs: what an edit puts in place of its predecessor, never writes
+/// (File.setContentSpan), and frees raw (memory.freeUnfilled, freeRaw).
+fn pinned(comptime T: type, comptime name: []const u8) bool {
+ const File = pardes.panes.File;
+ return (T == File.State and (std.mem.eql(u8, name, "content") or std.mem.eql(u8, name, "line_starts"))) or
+ (T == File.Snapshot and std.mem.eql(u8, name, "content"));
+}
+
+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), and the frame statistics
+/// (numbers, and a static name).
+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");
+}
+
+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());
+}
diff --git a/src/syntax.zig b/src/syntax.zig
index 985a9888..858ef6a2 100644
--- a/src/syntax.zig
+++ b/src/syntax.zig
@@ -381,11 +381,35 @@ pub fn parseTree(path: []const u8, content: []const u8) ?*anyopaque {
if (!enabled) return null;
const selected = (forExt(std.fs.path.extension(path)) catch return null) orelse return null;
const tree = selected.parser.parseString(content, null) orelse return null;
+ if (held_trees) |h| h.born.append(h.meta, @ptrCast(tree)) catch {};
return @ptrCast(tree);
}
+/// While a replica's rollback copy is held (src/rollback.zig) a tree parsed
+/// is the speculation's, and one freed is put off: trees live on the C
+/// heap, which the core's allocator cannot see. Null otherwise.
+pub var held_trees: ?*HeldTrees = null;
+pub const HeldTrees = struct {
+ meta: std.mem.Allocator,
+ born: std.ArrayListUnmanaged(*anyopaque) = .empty,
+ freed: std.ArrayListUnmanaged(*anyopaque) = .empty,
+};
+
pub fn freeTree(tree: *anyopaque) void {
if (!enabled) return;
+ if (held_trees) |h| {
+ for (h.born.items, 0..) |t, i| if (t == tree) {
+ _ = h.born.swapRemove(i);
+ return destroyTree(tree);
+ };
+ h.freed.append(h.meta, tree) catch destroyTree(tree);
+ return;
+ }
+ destroyTree(tree);
+}
+
+pub fn destroyTree(tree: *anyopaque) void {
+ if (!enabled) return;
const t: *ts.Tree = @ptrCast(@alignCast(tree));
t.destroy();
}
diff --git a/src/tape.zig b/src/tape.zig
index ec38deac..70609858 100644
--- a/src/tape.zig
+++ b/src/tape.zig
@@ -127,19 +127,40 @@ pub const Tape = struct {
/// PARDES_RECORD_EVERY: a digest after every input, a nested one's too
/// (to find the step a divergence starts at), not only the host's last.
every: bool = false,
+ /// A replica applying its own input before the authority has ordered it
+ /// (src/replica.zig): recorded as the authority would record it, so the
+ /// two can be compared, but nothing is performed. A host call or a
+ /// syscall stops it (`poisoned`): what the call returns is the
+ /// authority's to say, and the input waits for it. A read of the clock
+ /// or the environment (`value`) is made here, a guess the comparison
+ /// checks.
+ speculating: bool = false,
+ poisoned: bool = false,
+ /// The allocator of the core a replay makes (a replica's rollback epoch,
+ /// src/rollback.zig), when it is not the tape's own.
+ core_gpa: ?std.mem.Allocator = null,
+ /// Where a replay keeps what a core keeps of an input (its options),
+ /// for a tape that is let go; else the tape's allocator, for good.
+ kept_arena: ?std.heap.ArenaAllocator = null,
+ /// No digests recorded (a speculation's: a replica compares what it
+ /// was given and what it asked, from a state the authority shares).
+ no_digest: bool = false,
fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void {
t.scratch.clearRetainingCapacity();
walk.encode(T, v, &t.scratch.writer) catch @panic("tape: out of memory");
const payload = t.scratch.written();
const len: u32 = @intCast(payload.len);
- t.buf.append(t.gpa, @intFromEnum(kind)) catch @panic("tape: out of memory");
+ t.buf.append(t.gpa, @backingInt(kind)) catch @panic("tape: out of memory");
t.buf.appendSlice(t.gpa, std.mem.asBytes(&len)) catch @panic("tape: out of memory");
t.buf.appendSlice(t.gpa, payload) catch @panic("tape: out of memory");
if (t.buf.items.len > 1 << 20) t.flush();
}
fn flush(t: *Tape) void {
+ // A tape in memory (a replica's, an authority's stream) is taken
+ // by whoever holds it.
+ if (t.fd < 0) return;
var at: usize = 0;
while (at < t.buf.items.len) {
const n = libc.write(t.fd, t.buf.items[at..].ptr, t.buf.items.len - at);
@@ -222,7 +243,7 @@ pub const Tape = struct {
t.wrap(core);
};
t.record(.done, void, &{});
- if (t.depth == 0 or t.every) if (t.core) |core| {
+ if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| {
var parts: Parts = undefined;
const d = digestParts(core, &parts);
t.record(.digest, []const u64, &d);
@@ -239,12 +260,12 @@ pub const Tape = struct {
const head = t.in.take(5) catch return null;
const len = std.mem.bytesToValue(u32, head[1..5]);
const payload = t.in.take(len) catch return null;
- return .{ .kind = @enumFromInt(head[0]), .payload = .{ .bytes = payload } };
+ return .{ .kind = @fromBackingInt(@intCast(head[0])), .payload = .{ .bytes = payload } };
}
fn peek(t: *const Tape) ?Kind {
if (t.in.bytes.len - t.in.at < 5) return null;
- return @enumFromInt(t.in.bytes[t.in.at]);
+ return @fromBackingInt(@intCast(t.in.bytes[t.in.at]));
}
fn diverge(t: *Tape, comptime why: []const u8, args: anytype) void {
@@ -374,7 +395,8 @@ pub const Tape = struct {
const tag = std.mem.bytesToValue(Tag, (r.take(@sizeOf(Tag)) catch return t.diverge("a short input", .{})));
r.at -= @sizeOf(Tag);
const kept = tag == .init or tag == .init_from_dump or tag == .restore;
- const input = walk.decode(Input, r, if (kept) t.gpa else t.arena.allocator()) catch return t.diverge("a short input", .{});
+ const keep = if (t.kept_arena) |*k| k.allocator() else t.gpa;
+ const input = walk.decode(Input, r, if (kept) keep else t.arena.allocator()) catch return t.diverge("a short input", .{});
const outer = t.applying;
t.applying = switch (input) {
.update => |ev| @tagName(ev),
@@ -390,13 +412,14 @@ pub const Tape = struct {
.init_from_dump => |d| d.opts,
else => unreachable,
};
- opts.image_allocator = t.gpa;
- opts.pdf_allocator = t.gpa;
- opts.tree_sitter_allocator = t.gpa;
- opts.frame_allocator = t.gpa;
+ const gpa = t.core_gpa orelse t.gpa;
+ opts.image_allocator = gpa;
+ opts.pdf_allocator = gpa;
+ opts.tree_sitter_allocator = gpa;
+ opts.frame_allocator = gpa;
t.core = switch (input) {
- .init => Pardes.init(t.gpa, opts),
- .init_from_dump => |d| pardes.dump.initFromDump(t.gpa, opts, d.bytes),
+ .init => Pardes.init(gpa, opts),
+ .init_from_dump => |d| pardes.dump.initFromDump(gpa, opts, d.bytes),
else => unreachable,
} catch |err| return t.diverge("init failed: {t}", .{err});
t.core.?.host = t.hostOf(t.mask);
@@ -608,8 +631,21 @@ fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype
}
return walk.decode(R, &ret, t.arena.allocator()) catch std.mem.zeroes(R);
}
- const real = @field(t.real.vtable.*, name).?;
const id: u16 = i;
+ if (t.speculating) {
+ // Nobody watches a replica's step: its frames are its own, drawn
+ // outside it (and the authority's host says so too, or the
+ // comparison fails).
+ if (comptime std.mem.eql(u8, name, "watched")) {
+ const r = false;
+ t.record(.host, u16, &id);
+ t.record(.ret, R, &r);
+ return r;
+ }
+ t.poisoned = true;
+ return poisonOf(R);
+ }
+ const real = @field(t.real.vtable.*, name).?;
t.record(.host, u16, &id);
t.seeFields();
const outer = !t.host_side;
@@ -639,7 +675,7 @@ pub fn value(comptime s: Site, comptime f: anytype, args: anytype) @typeInfo(@Ty
fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anytype, comptime yields: bool) @typeInfo(@TypeOf(f)).@"fn".return_type.? {
const R = @typeInfo(@TypeOf(f)).@"fn".return_type.?;
const t = on orelse return if (yields) out(f, args) else @call(.auto, f, args);
- const id: u16 = @as(u16, host_fns.len) + @intFromEnum(s);
+ const id: u16 = @as(u16, host_fns.len) + @backingInt(s);
if (t.replay) {
if (!t.expectHost(id, @tagName(s))) {
std.debug.print("replay: {s}\n", .{t.diverged orelse "?"});
@@ -651,6 +687,12 @@ fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anyt
// The host's own (a shell's spawn asking the shell), or one inside a
// site's syscall: the outer call is the record.
if (t.host_side) return if (yields) out(f, args) else @call(.auto, f, args);
+ // A syscall a speculating replica must not make: its input waits for
+ // the authority's answer.
+ if (yields and t.speculating) {
+ t.poisoned = true;
+ return poisonOf(R);
+ }
t.record(.host, u16, &id);
t.seeFields();
t.host_side = true;
@@ -679,7 +721,173 @@ fn out(comptime f: anytype, args: anytype) @typeInfo(@TypeOf(f)).@"fn".return_ty
/// Asked by `turn.yield`: a syscall a replica must never make.
pub fn replaying() bool {
- return if (on) |t| t.replay else false;
+ return if (on) |t| t.replay or t.speculating else false;
+}
+
+/// A replica speculating (src/replica.zig): state only the authority
+/// changes (a terminal's emulator) is left alone, and the input waits.
+pub fn speculating() bool {
+ return if (on) |t| t.speculating else false;
+}
+
+/// What a speculation reached is the authority's: the input is undone and
+/// waits for the authority's order.
+pub fn poison() void {
+ if (on) |t| if (t.speculating) {
+ t.poisoned = true;
+ };
+}
+
+/// A harmless stand-in for what a host call or a syscall would have
+/// returned to a speculation that is thrown away once it returns: an
+/// error where one can be said, else zeroes.
+fn poisonOf(comptime R: type) R {
+ return switch (@typeInfo(R)) {
+ .error_union => |e| if (@typeInfo(e.error_set).error_set.error_names) |errors|
+ (if (errors.len > 0) @field(e.error_set, errors[0]) else std.mem.zeroes(R))
+ else
+ error.Unexpected,
+ .optional => null,
+ .void => {},
+ .@"union" => |u| inline for (u.field_names, u.field_types) |name, F| {
+ if (comptime zeroable(F)) break @unionInit(R, name, std.mem.zeroes(F));
+ } else @compileError("tape: no harmless value of " ++ @typeName(R)),
+ else => std.mem.zeroes(R),
+ };
+}
+
+fn zeroable(comptime T: type) bool {
+ return switch (@typeInfo(T)) {
+ .int, .float, .bool, .optional, .void => true,
+ .pointer => |p| p.size == .slice,
+ .array => |a| zeroable(a.child),
+ .@"struct" => |s| blk: {
+ for (s.field_types) |F| if (!zeroable(F)) break :blk false;
+ break :blk true;
+ },
+ else => false,
+ };
+}
+
+// ---- a replica's tapes in memory (src/replica.zig) ----
+
+/// A tape recorded in memory: an authority's stream, taken unit by unit.
+pub fn memory(gpa: std.mem.Allocator) Tape {
+ return .{ .gpa = gpa, .replay = false, .scratch = .init(gpa), .arena = .init(gpa), .kept_arena = .init(gpa) };
+}
+
+/// What a tape in memory holds, given back (its core is gone already).
+pub fn release(t: *Tape) void {
+ t.buf.deinit(t.gpa);
+ t.scratch.deinit();
+ t.arena.deinit();
+ if (t.kept_arena) |*k| k.deinit();
+}
+
+/// What was recorded since the last take; the tape's to reuse after.
+pub fn taken(t: *Tape) []const u8 {
+ return t.buf.items;
+}
+
+pub fn clearTaken(t: *Tape) void {
+ t.buf.clearRetainingCapacity();
+}
+
+/// The records of `bytes`, top-level inputs and all, applied to the
+/// tape's core as the authority applied them, each digest checked; why
+/// they diverged, or null.
+pub fn replayUnit(t: *Tape, bytes: []const u8) ?[]const u8 {
+ t.replay = true;
+ t.speculating = false;
+ defer t.replay = false;
+ t.in = .{ .bytes = bytes };
+ while (t.diverged == null) {
+ const kind = t.peek() orelse break;
+ var rec = t.next().?;
+ switch (kind) {
+ .input => {
+ t.apply(&rec.payload);
+ _ = t.arena.reset(.retain_capacity);
+ },
+ .set => t.applySet(&rec.payload),
+ .digest => t.check(&rec.payload),
+ .host, .ret, .done => t.diverge("a {t} record at the top", .{kind}),
+ }
+ }
+ return t.diverged;
+}
+
+/// Starts recording `t`'s core as a speculation: the host's watched
+/// fields as they are now, nothing recorded yet.
+pub fn beginSpeculation(t: *Tape) void {
+ t.replay = false;
+ t.speculating = true;
+ t.poisoned = false;
+ t.no_digest = true;
+ t.buf.clearRetainingCapacity();
+ t.seeFields();
+}
+
+/// Whether it stayed clean (no host call, no syscall, no authority state).
+pub fn endSpeculation(t: *Tape) bool {
+ t.speculating = false;
+ t.no_digest = false;
+ return !t.poisoned;
+}
+
+/// Whether two tapes record the same inputs, host calls and answers,
+/// their digests aside.
+pub fn sameRecords(a: []const u8, b: []const u8) bool {
+ var x: walk.Reader = .{ .bytes = a };
+ var y: walk.Reader = .{ .bytes = b };
+ while (true) {
+ const ra = nextRecord(&x);
+ const rb = nextRecord(&y);
+ if (ra == null or rb == null) return ra == null and rb == null;
+ if (ra.?.kind != rb.?.kind or !std.mem.eql(u8, ra.?.payload, rb.?.payload)) return false;
+ }
+}
+
+fn nextRecord(r: *walk.Reader) ?struct { kind: Kind, payload: []const u8 } {
+ while (true) {
+ const head = r.take(5) catch return null;
+ const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return null;
+ const kind: Kind = @fromBackingInt(@intCast(head[0]));
+ if (kind != .digest) return .{ .kind = kind, .payload = payload };
+ }
+}
+
+/// A tape's records, one a line (kind; an input's or a host call's name),
+/// for a divergence's report.
+pub fn describe(bytes: []const u8, w: *std.Io.Writer) void {
+ var r: walk.Reader = .{ .bytes = bytes };
+ var depth: usize = 0;
+ while (true) {
+ const head = r.take(5) catch return;
+ const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return;
+ const kind: Kind = @fromBackingInt(@intCast(head[0]));
+ if (kind == .done or kind == .ret) depth -|= 1;
+ w.splatByteAll(' ', depth * 2) catch {};
+ switch (kind) {
+ .input => {
+ const tag = std.mem.bytesToValue(std.meta.Tag(Input), payload[0..@sizeOf(std.meta.Tag(Input))]);
+ w.print("input {t}", .{tag}) catch {};
+ if (tag == .update) w.print(" {t}", .{std.mem.bytesToValue(std.meta.Tag(pardes.Event), payload[@sizeOf(std.meta.Tag(Input))..][0..@sizeOf(std.meta.Tag(pardes.Event))])}) catch {};
+ },
+ .host => {
+ const id = std.mem.bytesToValue(u16, payload[0..2]);
+ w.print("host {s}", .{if (id < host_fns.len) host_fns[id] else @tagName(@as(Site, @fromBackingInt(@intCast(id - host_fns.len))))}) catch {};
+ },
+ else => w.print("{t} ({d} bytes)", .{ kind, payload.len }) catch {},
+ }
+ w.writeByte('\n') catch {};
+ if (kind == .input or kind == .host) depth += 1;
+ }
+}
+
+/// The digest a replica and its authority must agree on.
+pub fn digestOf(p: *const Pardes) u64 {
+ return walk.digest(Pardes, p);
}
/// PARDES_RECORD set: the tape is written from the session's first call.
diff --git a/src/terminal.zig b/src/terminal.zig
index e737a831..81fae5db 100644
--- a/src/terminal.zig
+++ b/src/terminal.zig
@@ -417,9 +417,18 @@ pub fn panFor(p: *const Pardes, pane: *const Pane, r: pardes.Rect) u16 {
return @intCast(@min(pane.rows - shown, (at + 1) -| shown));
}
+/// A replica's speculation leaves an emulator be: it is the authority's
+/// (docs/next-daemon.md, phase 5), so the input waits for its order.
+fn authorityOnly() bool {
+ if (!pardes.tape.speculating()) return false;
+ pardes.tape.poison();
+ return true;
+}
+
/// Move the emulator's viewport by `delta` shell rows (negative scrolls back).
pub fn scrollGrid(pane: *Pane, delta: i32) void {
if (comptime !enabled) return;
+ if (authorityOnly()) return;
const state = pane.terminal orelse return;
state.vt.screens.active.scroll(.{ .delta_row = delta });
}
@@ -434,6 +443,7 @@ pub fn atBottom(pane: *const Pane) bool {
/// Snap the viewport back onto live output.
pub fn followOutput(pane: *Pane) void {
if (comptime !enabled) return;
+ if (authorityOnly()) return;
const state = pane.terminal orelse return;
state.vt.screens.active.scroll(.active);
}
@@ -442,6 +452,7 @@ pub fn followOutput(pane: *Pane) void {
/// a scrollback; the next resize retries with the same numbers.
pub fn resizeGrid(pane: *Pane, gpa: std.mem.Allocator, cols: u16, rows: u16) void {
if (comptime !enabled) return;
+ if (authorityOnly()) return;
const state = pane.terminal orelse return;
if (cols != pane.cols) for (0..pane.sel.len) |button| {
pane.clearPointerSelection(button);
@@ -643,6 +654,7 @@ pub fn screenTextLen(pane: *Pane) usize {
/// Release the emulator's heap. The Pane allocation itself is the core's.
pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void {
if (comptime !enabled) return;
+ if (authorityOnly()) return;
const state = pane.terminal orelse return;
if (comptime images_enabled) state.images.deinit(gpa);
state.stream.deinit();
@@ -654,6 +666,7 @@ pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void {
/// Allocate the live emulator half of a terminal pane. Slot ownership, serial
/// assignment, and spawn effects remain core lifecycle invariants.
pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane {
+ if (authorityOnly()) return error.OutOfMemory;
const pane = try createDoc(gpa, cols, rows);
errdefer gpa.destroy(pane);
if (comptime !enabled) return pane;
@@ -674,6 +687,9 @@ pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane {
});
state.stream = .init(.{ .handler = .{ .inner = state.vt.vtHandler() }, .allocator = gpa });
state.reply_len = 0;
+ // Every field its default (create leaves them what the heap had, which
+ // a digest then reads: two replicas must agree, src/replica.zig).
+ state.reply_dropped = 0;
state.mouse_cell = null;
state.images = if (images_enabled) .{} else {};
if (comptime images_enabled) TerminalImages.installPngDecoder();
@@ -900,6 +916,7 @@ pub fn feedOutput(p: *Pardes, pane: *Pane, bytes: []const u8) void {
// There are no pty reads at all without an emulator to parse them into.
if (comptime !enabled) return;
if (pane.terminal == null) return;
+ if (authorityOnly()) return;
const has_positions = pane.ovl != null or pane.body.cur_pinned or pane.body.vsel.active or
pane.body.msel.active or pane.body.nsel > 0 or pane.body.last_edit != null or pane.look_at != null or
pane.body.ed_undo_len > 0 or pane.body.ed_redo_len > 0 or pointerRowCount(pane) > 0;
diff --git a/src/walk.zig b/src/walk.zig
index dc1664cb..3e482e9a 100644
--- a/src/walk.zig
+++ b/src/walk.zig
@@ -42,7 +42,7 @@ pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 {
if (attr.@"comptime" or comptime excluded(T, name)) continue;
var h = Hasher.init(0);
if (comptime lengthOf(T, name)) |len| {
- hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], &h);
+ hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h);
} else hash(F, &@field(v, name), &h);
out[n] = h.final();
n += 1;
@@ -63,7 +63,7 @@ pub fn fieldNames(comptime T: type) []const []const u8 {
}
/// Types that are machinery, never state: an allocator, the Io, a lock.
-fn machinery(comptime T: type) bool {
+pub fn machinery(comptime T: type) bool {
inline for (.{ std.mem.Allocator, std.Io, std.Io.Mutex, std.Io.Condition, std.Thread, std.heap.ArenaAllocator }) |M| if (T == M) return true;
return false;
}
@@ -92,7 +92,7 @@ fn opaqueTo(comptime F: type) bool {
};
}
-fn excluded(comptime T: type, comptime name: []const u8) bool {
+pub fn excluded(comptime T: type, comptime name: []const u8) bool {
@setEvalBranchQuota(100_000);
if (!@hasDecl(T, "replica")) return false;
inline for (.{ "local", "derived", "authority" }) |kind| {
@@ -104,12 +104,22 @@ fn excluded(comptime T: type, comptime name: []const u8) bool {
}
/// How far the field `len` names says its array is written (null: none).
-fn lengthIn(v: anytype, comptime len: []const u8) usize {
+/// What a `len`-cut field holds: a fixed array's, or a slice's room (a
+/// selection's ranges, made once and used `nsel` deep).
+fn Element(comptime F: type) type {
+ return switch (@typeInfo(F)) {
+ .array => |a| a.child,
+ .pointer => |p| p.child,
+ else => @compileError("walk: a `len` cuts an array or a slice, not " ++ @typeName(F)),
+ };
+}
+
+pub fn lengthIn(v: anytype, comptime len: []const u8) usize {
const n = @field(v, len);
return if (@typeInfo(@TypeOf(n)) == .optional) (if (n) |k| k else 0) else n;
}
-fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 {
+pub fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 {
@setEvalBranchQuota(100_000);
if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "len")) return null;
inline for (T.replica.len) |pair| if (comptime std.mem.eql(u8, pair[0], name)) return pair[1];
@@ -134,7 +144,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void {
.bool => h.update(&.{@intFromBool(v.*)}),
.int => hashInt(T, v.*, h),
.float => h.update(std.mem.asBytes(v)),
- .@"enum" => |e| hashInt(e.tag_type, @intFromEnum(v.*), h),
+ .@"enum" => |e| hashInt(e.tag_type, @backingInt(v.*), h),
.optional => |o| if (v.*) |*payload| {
h.update(&.{1});
hash(o.child, payload, h);
@@ -167,7 +177,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void {
if (attr.@"comptime" or comptime excluded(T, name)) continue;
if (comptime opaqueTo(F)) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is " ++ @typeName(F) ++ ", which no walk sees into: say what it is (`replica`)");
if (comptime lengthOf(T, name)) |len| {
- hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], h);
+ hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h);
} else hash(F, &@field(v, name), h);
}
},