summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
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);
}
},