diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/File.zig | 14 | ||||
| -rw-r--r-- | src/Pipe.zig | 2 | ||||
| -rw-r--r-- | src/Text.zig | 6 | ||||
| -rw-r--r-- | src/memory.zig | 9 | ||||
| -rw-r--r-- | src/pardes.zig | 11 | ||||
| -rw-r--r-- | src/replica.zig | 578 | ||||
| -rw-r--r-- | src/rollback.zig | 496 | ||||
| -rw-r--r-- | src/syntax.zig | 24 | ||||
| -rw-r--r-- | src/tape.zig | 236 | ||||
| -rw-r--r-- | src/terminal.zig | 17 | ||||
| -rw-r--r-- | src/walk.zig | 24 |
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); } }, |
