diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-31 06:28:48 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-31 06:28:48 -0300 |
| commit | a479792a1ab2b593642d7f648194bfa23ce01dba (patch) | |
| tree | 96ddee7d879a9084daa07db43b0b7910b072a785 /src/walk.zig | |
| parent | e179cc44fe5060c76a5b00c41e53f11209f5acd9 (diff) | |
| parent | 4c761893e5b3fdae422622cfa02104ab36633045 (diff) | |
| download | pardes-a479792a1ab2b593642d7f648194bfa23ce01dba.tar.gz pardes-a479792a1ab2b593642d7f648194bfa23ce01dba.zip | |
Merge the upstream daemon and replicated client/server refactor
Diffstat (limited to 'src/walk.zig')
| -rw-r--r-- | src/walk.zig | 1975 |
1 files changed, 1975 insertions, 0 deletions
diff --git a/src/walk.zig b/src/walk.zig new file mode 100644 index 00000000..14e1929e --- /dev/null +++ b/src/walk.zig @@ -0,0 +1,1975 @@ +//! The reflective walk over the core's state: one comptime `@typeInfo` walk +//! that hashes a session into a digest (the replay harness compares two), +//! encodes values for the tape, and dumps a session for another build to +//! load by name (`Dump`, `Load`: Restore, -l, the store, a handover, and +//! the join of phase 5). The rollback copy is to walk the same way +//! (docs/next-daemon.md). +//! +//! Values, never addresses: a pointer is followed to what it points at, a +//! slice is its elements, an ArrayList its items, a hash map its entries in +//! no order. A type the walk cannot see into (an opaque handle, a function, +//! an untagged union, a many-pointer) is a compile error naming it, until +//! the struct that holds it says what the field is: +//! +//! pub const replica = .{ +//! // This process's own: presentation, timing, the host's handles +//! // and caches. A replica has its own and never compares them. +//! .local = .{ "frames", "surface" }, +//! // Recomputed from the rest whenever it is wanted. +//! .derived = .{ "wrap_line" }, +//! // Held by the session that performs effects alone. +//! .authority = .{ "host" }, +//! // A field written only as far as another says: hashed that far. +//! .len = .{ .{ "jumps", "njumps" } }, +//! // What a field holds is made with another allocator on a load. +//! .alloc = .{ .{ "image", "image" } }, +//! // Immutable blobs: replaced whole, never written, freed raw +//! // (memory.freeRaw, freeUnfilled). A digest hashes each once and +//! // folds that word in; a replica's rollback copy pins them. +//! .blob = .{ "content" }, +//! }; +//! +//! None of the three kinds is in a digest or a dump. A type with a `pub fn +//! digest(*const T, *Hasher) void` of its own hashes itself; one with +//! `dumpWrite`, `dumpRead` (and `dumpFree`) dumps itself as bytes. +const std = @import("std"); + +pub const Hasher = std.hash.Wyhash; +const builtin = @import("builtin"); +/// Only a Debug build hashes a blob's bytes at every digest and checks its +/// kept word; a release one, ReleaseSafe the user's own, takes the word. +const rehash = builtin.mode == .debug; + +/// Whether `T.name` holds immutable blobs (`.blob`): a file's text, an undo +/// snapshot, a register's text, a file's location rows. +pub fn blob(comptime T: type, comptime name: []const u8) bool { + @setEvalBranchQuota(100_000); + if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "blob")) return false; + inline for (T.replica.blob) |n| if (comptime std.mem.eql(u8, n, name)) return true; + return false; +} + +// ---- a blob's hash, made once ---- +// +// A digest walks the whole core at every unit a replica is sent (and every +// unit a replica replays): a 100 MB file was hashed in full each time. A +// blob of `blob_min` bytes or more is hashed once instead, its word kept by +// its address, and the digest folds the word in. The word goes when the +// blob is freed (`forget`, from memory.freeRaw and freeUnfilled: every +// such blob is freed raw, for the rollback copy's pins), so an address +// used again is hashed again. A Debug build hashes the bytes all the same, +// folds those in, and stops where a kept word is not their hash: a blob +// written in place (which the pins forbid too), or freed past `forget`. A +// release build never stops there: a stale word shows as a divergence. + +const blob_min = 4096; +var blob_words: std.AutoHashMapUnmanaged(usize, struct { len: usize, word: u64 }) = .empty; +var blob_lock: std.atomic.Value(bool) = .init(false); +var blob_count: std.atomic.Value(usize) = .init(0); +threadlocal var in_blob: bool = false; +/// Off: every blob hashed whole at every digest, as before (the bench's). +pub var blob_words_on = true; + +fn lockBlobs() void { + while (blob_lock.cmpxchgWeak(false, true, .acquire, .monotonic) != null) std.atomic.spinLoopHint(); +} + +fn unlockBlobs() void { + blob_lock.store(false, .release); +} + +/// The blob at `addr` is freed: its word, if it has one, goes with it. +pub fn forget(addr: usize) void { + if (blob_count.load(.acquire) == 0) return; + lockBlobs(); + defer unlockBlobs(); + if (blob_words.remove(addr)) blob_count.store(blob_words.count(), .release); +} + +/// The word kept for the blob at `addr` (a test's). +pub fn wordOf(addr: usize) ?u64 { + lockBlobs(); + defer unlockBlobs(); + return if (blob_words.get(addr)) |b| b.word else null; +} + +/// Every word forgotten (the bench's cold digests). +pub fn forgetAll() void { + lockBlobs(); + defer unlockBlobs(); + blob_words.clearRetainingCapacity(); + blob_count.store(0, .release); +} + +/// A blob as a digest takes it: its length and its word. +fn hashBlob(comptime E: type, items: []const E, h: *Hasher) void { + const addr = @intFromPtr(items.ptr); + const word: u64 = word: { + const kept: ?u64 = if (blob_words_on) kept: { + lockBlobs(); + defer unlockBlobs(); + const b = blob_words.get(addr) orelse break :kept null; + break :kept if (b.len == items.len) b.word else null; + } else null; + // The lists are the C heap's (a replica client's, a session's join), + // which a build with no libc (the web) has neither of. + if (comptime builtin.link_libc) if (blobs_out) |list| { + list.append(std.heap.c_allocator, std.mem.sliceAsBytes(items)) catch {}; + break :word 0; + }; + if (!rehash) if (kept) |w| break :word w; + if (comptime builtin.link_libc) if (E == u8) if (unhashed_out) |list| if (kept == null) { + list.append(std.heap.c_allocator, items) catch {}; + break :word 0; + }; + in_blob = false; + defer in_blob = true; + var one = Hasher.init(0); + hashSlice(E, items, &one); + const w = one.final(); + if (kept) |k| if (k != w) std.debug.panic("walk: the {d}-byte blob at 0x{x} is not what its kept word was: written in place, or freed without memory.freeRaw", .{ items.len, addr }); + if (blob_words_on and kept == null) { + lockBlobs(); + defer unlockBlobs(); + blob_words.put(std.heap.page_allocator, addr, .{ .len = items.len, .word = w }) catch {}; + blob_count.store(blob_words.count(), .release); + } + break :word w; + }; + h.update(std.mem.asBytes(&items.len)); + h.update(std.mem.asBytes(&word)); +} + +/// Where `unhashed` notes the texts a digest would hash for want of a word. +threadlocal var unhashed_out: ?*std.ArrayListUnmanaged([]const u8) = null; +/// Where `blobs` notes every blob, hashing none. +threadlocal var blobs_out: ?*std.ArrayListUnmanaged([]const u8) = null; + +/// Every blob of `v` a digest would take as one (`blob_min` bytes and up), +/// as its bytes, onto `out` (the C heap's), hashed by none: a replica +/// client's, which knows its blobs by content (src/replica.zig `Have`). +pub fn blobs(comptime T: type, v: *const T, out: *std.ArrayListUnmanaged([]const u8)) void { + blobs_out = out; + defer blobs_out = null; + _ = digest(T, v); +} + +/// The blob texts a digest of `v` would hash now, having no word yet, onto +/// `out` (the C heap's): a walk with no blob hashed, which `makeWords` then +/// makes on another thread. A replica's join (src/replica.zig) does that +/// first: the session's step never hashes a text it never digested before. +pub fn unhashed(comptime T: type, v: *const T, out: *std.ArrayListUnmanaged([]const u8)) void { + unhashed_out = out; + defer unhashed_out = null; + _ = digest(T, v); +} + +/// The words of `texts` (`unhashed`'s), made on any thread: they must stay +/// as they are meanwhile (pinned, memory.zig), and the next digest takes +/// them. +pub fn makeWords(texts: []const []const u8) void { + for (texts) |items| { + // As hashBlob makes it (hashSlice's length, then the bytes). + var one = Hasher.init(0); + one.update(std.mem.asBytes(&items.len)); + one.update(items); + const w = one.final(); + lockBlobs(); + defer unlockBlobs(); + const got = blob_words.getOrPut(std.heap.page_allocator, @intFromPtr(items.ptr)) catch continue; + if (!got.found_existing) got.value_ptr.* = .{ .len = items.len, .word = w }; + blob_count.store(blob_words.count(), .release); + } +} + +pub fn digest(comptime T: type, v: *const T) u64 { + var h = Hasher.init(0); + hash(T, v, &h); + return h.final(); +} + +/// A digest of each field `hash` would walk, in order (what a divergence +/// is narrowed down by); `names` are theirs. +pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 { + var n: usize = 0; + const s = @typeInfo(T).@"struct"; + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime" or comptime excluded(T, name)) continue; + var h = Hasher.init(0); + const was = in_blob; + in_blob = comptime blob(T, name); + defer in_blob = was; + if (comptime lengthOf(T, name)) |len| { + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h); + } else hash(F, &@field(v, name), &h); + out[n] = h.final(); + n += 1; + } + return out[0..n]; +} + +pub fn fieldNames(comptime T: type) []const []const u8 { + comptime { + var names: []const []const u8 = &.{}; + const s = @typeInfo(T).@"struct"; + for (s.field_names, s.field_attrs) |name, attr| { + if (attr.@"comptime" or excluded(T, name)) continue; + names = names ++ .{name}; + } + return names; + } +} + +/// Types that are machinery, never state: an allocator, the Io, a lock. +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; +} + +/// Bytes that are the value whole: no padding, no pointer. +fn flat(comptime T: type) bool { + return switch (@typeInfo(T)) { + .int => @sizeOf(T) * 8 == @bitSizeOf(T), + .bool => true, + .@"enum" => |e| @sizeOf(T) * 8 == @bitSizeOf(e.tag_type), + else => false, + }; +} + +/// A field the walk cannot follow: a pointer to an opaque thing or a +/// function, or a many-pointer, bare or optional (the struct holding it is +/// named in the error, not the walk's depth). +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, + }; +} + +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| { + if (@hasField(@TypeOf(T.replica), kind)) inline for (@field(T.replica, kind)) |n| { + if (comptime std.mem.eql(u8, n, name)) return true; + }; + } + return false; +} + +/// How far the field `len` names says its array is written (null: none). +/// 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; +} + +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]; + return null; +} + +/// Every name an annotation gives is a field: a rename cannot quietly put +/// a field back in the digest. +fn checkAnnotations(comptime T: type) void { + if (!@hasDecl(T, "replica")) return; + inline for (@typeInfo(@TypeOf(T.replica)).@"struct".field_names) |kind| { + inline for (@field(T.replica, kind)) |entry| { + const name = if (comptime std.mem.eql(u8, kind, "len") or std.mem.eql(u8, kind, "alloc")) entry[0] else entry; + if (!@hasField(T, name)) @compileError("walk: " ++ @typeName(T) ++ " annotates no field " ++ name); + } + } +} + +pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { + switch (@typeInfo(T)) { + .void, .null, .undefined => {}, + .bool => h.update(&.{@intFromBool(v.*)}), + .int => hashInt(T, v.*, h), + .float => h.update(std.mem.asBytes(v)), + .@"enum" => hashEnum(T, v.*, h), + .optional => |o| if (v.*) |*payload| { + h.update(&.{1}); + hash(o.child, payload, h); + } else h.update(&.{0}), + .array => |a| if (comptime flatHash(a.child)) h.update(std.mem.sliceAsBytes(v)) else for (v) |*e| hash(a.child, e, h), + .pointer => |p| switch (p.size) { + .one => hash(p.child, v.*, h), + .slice => hashSlice(p.child, v.*, h), + else => @compileError("walk: a many-pointer has no length: " ++ @typeName(T)), + }, + .@"struct" => |s| { + if (comptime machinery(T)) return; + if (comptime @hasDecl(T, "digest") and @TypeOf(T.digest) == fn (*const T, *Hasher) void) return v.digest(h); + if (s.layout == .@"packed") return hashInt(s.backing_integer.?, @bitCast(v.*), h); + if (comptime isList(T)) + return hashSlice(@typeInfo(@FieldType(T, "items")).pointer.child, v.items, h); + if (comptime @hasDecl(T, "KV") and @hasDecl(T, "Hash") and @hasField(T, "metadata")) return hashMap(T, v, h); + // std.atomic.Value: what it holds. + if (comptime @hasField(T, "raw") and s.field_names.len == 1 and @hasDecl(T, "load")) return hash(@FieldType(T, "raw"), &v.raw, h); + // A worker's future is a handle of the host's, never state. + if (comptime @hasField(T, "any_future")) return; + // std.DynamicBitSetUnmanaged: its bits. + if (comptime @hasField(T, "bit_length") and @hasField(T, "masks") and s.field_names.len == 2) { + h.update(std.mem.asBytes(&v.bit_length)); + return h.update(std.mem.sliceAsBytes(v.masks[0 .. (v.bit_length + @bitSizeOf(usize) - 1) / @bitSizeOf(usize)])); + } + comptime checkAnnotations(T); + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + 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`)"); + const was = in_blob; + in_blob = comptime blob(T, name); + defer in_blob = was; + if (comptime lengthOf(T, name)) |len| { + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h); + } else hash(F, &@field(v, name), h); + } + }, + .@"union" => |u| { + if (u.tag_type == null) @compileError("walk: an untagged union: " ++ @typeName(T)); + const tag: u.tag_type.? = v.*; + hash(u.tag_type.?, &tag, h); + switch (v.*) { + inline else => |*payload| hash(@TypeOf(payload.*), payload, h), + } + }, + .error_set => h.update(@errorName(v.*)), + .error_union => |e| if (v.*) |*payload| { + h.update(&.{1}); + hash(e.payload, payload, h); + } else |err| { + h.update(&.{0}); + h.update(@errorName(err)); + }, + else => @compileError("walk: cannot hash " ++ @typeName(T)), + } +} + +/// Bytes a digest takes whole: an enum's are its build's number, not it. +fn flatHash(comptime T: type) bool { + return flat(T) and @typeInfo(T) != .@"enum"; +} + +/// An enum by its name, as a dump reads it, not by its number: an enum +/// made at compile time numbers its words as its build has them +/// (`registry.Builtin` has fewer in a FreeBSD build than a Linux one, which +/// has Tty9p), so a window client here of a session on the box loaded a +/// +LocationsConfig to another digest. A name's word (its hash, fixed +/// width, so that two names in a row are not one), looked up by number +/// where the words are numbered 0 up; one numbered by hand, or a value no +/// word has, by its number. +fn hashEnum(comptime T: type, v: T, h: *Hasher) void { + const e = @typeInfo(T).@"enum"; + const words: ?[e.field_names.len]u64 = comptime words: { + @setEvalBranchQuota(100_000); + var out: [e.field_names.len]u64 = undefined; + for (e.field_names, e.field_values, 0..) |name, n, i| { + if (n != i) break :words null; + out[i] = std.hash.Wyhash.hash(0, name); + } + break :words out; + }; + const n = @backingInt(v); + if (words) |table| if (n >= 0 and n < table.len) return h.update(std.mem.asBytes(&table[@intCast(n)])); + hashInt(e.tag_type, n, h); +} + +/// An integer by its value: one narrower than its bytes (a u21, an i2) has +/// bits in memory that are no part of it. +fn hashInt(comptime I: type, n: I, h: *Hasher) void { + const W = @Int(@typeInfo(I).int.signedness, @sizeOf(I) * 8); + const wide: W = n; + h.update(std.mem.asBytes(&wide)); +} + +fn hashSlice(comptime E: type, items: []const E, h: *Hasher) void { + if (in_blob and items.len * @sizeOf(E) >= blob_min) return hashBlob(E, items, h); + h.update(std.mem.asBytes(&items.len)); + if (comptime flatHash(E)) return h.update(std.mem.sliceAsBytes(items)); + for (items) |*e| hash(E, e, h); +} + +/// A hash map's entries in no order: each one's own digest, summed. +fn hashMap(comptime T: type, v: *const T, h: *Hasher) void { + var sum: u64 = 0; + var it = v.iterator(); + while (it.next()) |entry| { + var one = Hasher.init(0); + hash(@TypeOf(entry.key_ptr.*), entry.key_ptr, &one); + hash(@TypeOf(entry.value_ptr.*), entry.value_ptr, &one); + sum +%= one.final(); + } + h.update(std.mem.asBytes(&v.count())); + h.update(std.mem.asBytes(&sum)); +} + +/// The value as bytes, the same walk: what the tape carries (src/tape.zig), +/// to a replica of another build too (a window of a terminal's session, a +/// Linux client of a FreeBSD one). Native byte order, which every machine +/// pardes runs on shares, and an error by its name: its number is its +/// build's own (a Linux terminal's FileNotFound is a window's +/// NoDefaultValue). What a field is laid out as (a std.Io.File.Stat's +/// `nlink` is another width on FreeBSD) is the tape's shape, which +/// wire.semantics hashes (`shape`). +pub fn encode(comptime T: type, v: *const T, w: *std.Io.Writer) std.Io.Writer.Error!void { + switch (@typeInfo(T)) { + .void, .null, .undefined => {}, + .bool, .int, .float, .@"enum" => try w.writeAll(std.mem.asBytes(v)), + .optional => |o| if (comptime machinery(o.child)) try w.writeByte(0) else if (v.*) |*payload| { + try w.writeByte(1); + try encode(o.child, payload, w); + } else try w.writeByte(0), + .array => |a| if (comptime flat(a.child)) try w.writeAll(std.mem.sliceAsBytes(v)) else for (v) |*e| try encode(a.child, e, w), + .pointer => |p| switch (p.size) { + .one => try encode(p.child, v.*, w), + .slice => { + try w.writeAll(std.mem.asBytes(&v.len)); + if (comptime flat(p.child)) try w.writeAll(std.mem.sliceAsBytes(v.*)) else for (v.*) |*e| try encode(p.child, e, w); + }, + else => @compileError("walk: a many-pointer has no length: " ++ @typeName(T)), + }, + .@"struct" => |s| { + if (comptime machinery(T)) return; + if (s.layout == .@"packed") return w.writeAll(std.mem.asBytes(v)); + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime" or comptime excluded(T, name)) continue; + try encode(F, &@field(v, name), w); + } + }, + .@"union" => |u| { + if (u.tag_type == null) @compileError("walk: an untagged union: " ++ @typeName(T)); + const tag: u.tag_type.? = v.*; + try encode(u.tag_type.?, &tag, w); + switch (v.*) { + inline else => |*payload| try encode(@TypeOf(payload.*), payload, w), + } + }, + .error_set => try encodeError(T, v.*, w), + .error_union => |e| if (v.*) |*payload| { + try w.writeByte(1); + try encode(e.payload, payload, w); + } else |err| { + try w.writeByte(0); + try encodeError(e.error_set, err, w); + }, + else => @compileError("walk: cannot encode " ++ @typeName(T)), + } +} + +/// What `encode` lays each of `types` out as, in words: each field, element +/// and tag where it goes, an enum's names and numbers, an error as an +/// error (it goes by its name). wire.semantics hashes the tape's: builds +/// whose tapes differ in shape, as a FreeBSD std.Io.File.Stat differs from +/// a Linux one, refuse each other's replicas in words, not read each other +/// out of step. +pub fn shape(comptime types: []const type) []const u8 { + comptime { + @setEvalBranchQuota(10_000_000); + var out: []const u8 = ""; + for (types) |T| out = out ++ shapeOf(T, 0) ++ "\n"; + return out; + } +} + +fn shapeOf(comptime T: type, comptime depth: u8) []const u8 { + comptime { + if (depth > 32) @compileError("walk: the tape's shape nests past 32 deep at " ++ @typeName(T) ++ ": a type that holds itself?"); + return switch (@typeInfo(T)) { + .void, .null, .undefined => "v", + .bool => "b", + .int => |i| std.fmt.comptimePrint("{t}{d}", .{ i.signedness, i.bits }), + .float => |f| std.fmt.comptimePrint("f{d}", .{f.bits}), + .@"enum" => |e| blk: { + var out: []const u8 = shapeOf(e.tag_type, depth + 1) ++ "{"; + for (e.field_names, e.field_values) |n, v| out = out ++ std.fmt.comptimePrint("{s}={d},", .{ n, v }); + break :blk out ++ "}"; + }, + .optional => |o| if (machinery(o.child)) "0" else "?" ++ shapeOf(o.child, depth + 1), + .array => |a| std.fmt.comptimePrint("[{d}]", .{a.len}) ++ shapeOf(a.child, depth + 1), + .pointer => |p| switch (p.size) { + .one => shapeOf(p.child, depth + 1), + .slice => "[]" ++ shapeOf(p.child, depth + 1), + else => @compileError("walk: a many-pointer has no length: " ++ @typeName(T)), + }, + .@"struct" => |s| blk: { + if (machinery(T)) break :blk ""; + var out: []const u8 = if (s.layout == .@"packed") "p{" else "{"; + for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime" or excluded(T, name)) continue; + out = out ++ name ++ ":" ++ shapeOf(F, depth + 1) ++ ","; + } + break :blk out ++ "}"; + }, + .@"union" => |u| blk: { + var out: []const u8 = shapeOf(u.tag_type.?, depth + 1) ++ "("; + for (u.field_names, u.field_types) |name, F| out = out ++ name ++ ":" ++ shapeOf(F, depth + 1) ++ ","; + break :blk out ++ ")"; + }, + .error_set => "error", + .error_union => |e| "!" ++ shapeOf(e.payload, depth + 1), + else => @compileError("walk: cannot encode " ++ @typeName(T)), + }; + } +} + +/// An error by its name. An `anyerror` must be one `decode` can read back +/// (`errorNamed`): a Debug build stops at one that is not, as it is taped. +fn encodeError(comptime E: type, err: E, w: *std.Io.Writer) std.Io.Writer.Error!void { + if (comptime E == anyerror and builtin.mode == .debug) if (errorNamed(E, @errorName(err)) == null) + std.debug.panic("walk: error.{s} is taped as an anyerror, which a replica reads back only as one of tape.Failure's: add the set it comes from", .{@errorName(err)}); + try writeName(w, @errorName(err)); +} + +/// The error of `E` called `name`. `anyerror` keeps no list of its names +/// to look one up in: one is read back as one of tape.Failure's, what a +/// host reports as failed (the tape's only anyerrors). +fn errorNamed(comptime E: type, name: []const u8) ?E { + const Named = if (E == anyerror) @import("tape.zig").Failure else E; + inline for (@typeInfo(Named).error_set.error_names.?) |n| if (std.mem.eql(u8, name, n)) return @field(Named, n); + return null; +} + +pub const Reader = struct { + bytes: []const u8, + at: usize = 0, + + pub fn take(r: *Reader, n: usize) error{EndOfTape}![]const u8 { + if (r.bytes.len - r.at < n) return error.EndOfTape; + defer r.at += n; + return r.bytes[r.at..][0..n]; + } + + fn scalar(r: *Reader, comptime T: type) error{EndOfTape}!T { + return std.mem.bytesToValue(T, try r.take(@sizeOf(T))); + } +}; + +/// What an error read back is when this build has none of that name (an +/// OS's own, a newer build's): the tape is another build's, and diverges. +pub const TapeError = error{ EndOfTape, OutOfMemory, NoSuchError }; + +/// The inverse of `encode`; slices (and what a pointer points at) are made +/// in `a`. A field `encode` left out is its default. +pub fn decode(comptime T: type, r: *Reader, a: std.mem.Allocator) TapeError!T { + switch (@typeInfo(T)) { + .void, .null, .undefined => return {}, + .bool => return (try r.take(1))[0] != 0, + .int, .float, .@"enum" => return r.scalar(T), + .optional => |o| { + if ((try r.take(1))[0] == 0) return null; + if (comptime machinery(o.child)) unreachable; + return try decode(o.child, r, a); + }, + .array => |a_info| { + var out: T = undefined; + if (comptime flat(a_info.child)) { + @memcpy(std.mem.sliceAsBytes(&out), try r.take(@sizeOf(T))); + } else for (&out) |*e| { + e.* = try decode(a_info.child, r, a); + } + return out; + }, + .pointer => |p| switch (p.size) { + .one => { + const out = try a.create(p.child); + out.* = try decode(p.child, r, a); + return out; + }, + .slice => { + const n = try r.scalar(usize); + const out = try a.alloc(p.child, n); + if (comptime flat(p.child)) { + @memcpy(std.mem.sliceAsBytes(out), try r.take(n * @sizeOf(p.child))); + } else for (out) |*e| { + e.* = try decode(p.child, r, a); + } + return out; + }, + else => @compileError("walk: a many-pointer has no length: " ++ @typeName(T)), + }, + .@"struct" => |s| { + if (s.layout == .@"packed") return r.scalar(T); + var out: T = undefined; + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime") continue; + if (comptime excluded(T, name)) { + const default = attr.default_value_ptr orelse @compileError("walk: " ++ name ++ " has no default to decode to"); + @field(out, name) = @as(*const F, @ptrCast(@alignCast(default))).*; + } else if (comptime @typeInfo(F) == .error_set) { + // No `!anyerror` to return it through: read in place. + try decodeError(F, r, &@field(out, name)); + } else @field(out, name) = try decode(F, r, a); + } + return out; + }, + .@"union" => |u| { + const tag = try decode(u.tag_type.?, r, a); + inline for (u.field_names, u.field_types) |name, F| if (tag == @field(u.tag_type.?, name)) { + return @unionInit(T, name, try decode(F, r, a)); + }; + unreachable; + }, + .error_union => |e| { + if ((try r.take(1))[0] != 0) return try decode(e.payload, r, a); + // The value's error, not decode's own. + var err: e.error_set = undefined; + try decodeError(e.error_set, r, &err); + return @as(T, err); + }, + else => @compileError("walk: cannot decode " ++ @typeName(T)), + } +} + +/// An error by its name, as `encode` wrote it, into `out`: no error union +/// holds an error set. +fn decodeError(comptime E: type, r: *Reader, out: *E) TapeError!void { + const len = try r.scalar(u16); + out.* = errorNamed(E, try r.take(len)) orelse return error.NoSuchError; +} + +test "a value comes back from its bytes" { + const E = union(enum) { key: struct { cp: u21, text: []const u8 }, tick, failed: anyerror!u32 }; + var buf: [256]u8 = undefined; + var w: std.Io.Writer = .fixed(&buf); + const values = [_]E{ .{ .key = .{ .cp = 'x', .text = "x" } }, .tick, .{ .failed = error.FileNotFound }, .{ .failed = 9 } }; + for (&values) |*v| try encode(E, v, &w); + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + var r: Reader = .{ .bytes = w.buffered() }; + for (&values) |*v| try std.testing.expectEqual(digest(E, v), digest(E, &try decode(E, &r, arena.allocator()))); + try std.testing.expectEqual(r.bytes.len, r.at); +} + +test "an error is taped by its name, which another build reads back as its own" { + // The build's number for an error is its own: 451 of 505 names were + // numbered otherwise in a Linux window's build than a terminal's, so a + // window replica read a terminal session's FileNotFound as another. + var buf: [64]u8 = undefined; + var w: std.Io.Writer = .fixed(&buf); + const failed: error{ FileNotFound, NotDir }!u32 = error.NotDir; + try encode(@TypeOf(failed), &failed, &w); + try std.testing.expectEqualSlices(u8, "\x00\x06\x00NotDir", w.buffered()); + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + var r: Reader = .{ .bytes = w.buffered() }; + try std.testing.expectError(error.NotDir, try decode(@TypeOf(failed), &r, arena.allocator())); + // A name this build's set lacks (an OS's own): the tape is another + // build's, and the replay diverges rather than read some other error. + r = .{ .bytes = "\x00\x0c\x00FileTooLarge" }; + try std.testing.expectError(error.NoSuchError, decode(@TypeOf(failed), &r, arena.allocator())); + // An anyerror (a host's report) is read back as one of tape.Failure's. + const Report = struct { err: anyerror }; + w = .fixed(&buf); + try encode(Report, &.{ .err = error.FileNotFound }, &w); + r = .{ .bytes = w.buffered() }; + try std.testing.expectEqual(error.FileNotFound, (try decode(Report, &r, arena.allocator())).err); +} + +test "an enum is digested by its name, which another build may number otherwise" { + // registry.Builtin as a Linux build makes it (Tty9p in it) and as a + // FreeBSD one does: LocationsConfig is another number in each. + const Linux = enum { Look, Tty9p, LocationsConfig }; + const FreeBSD = enum { Look, LocationsConfig }; + const S = struct { from: Linux, also: [2]Linux }; + const T = struct { from: FreeBSD, also: [2]FreeBSD }; + try std.testing.expectEqual(digest(S, &.{ .from = .LocationsConfig, .also = .{ .Look, .LocationsConfig } }), digest(T, &.{ .from = .LocationsConfig, .also = .{ .Look, .LocationsConfig } })); + try std.testing.expect(digest(S, &.{ .from = .Look, .also = .{ .Look, .Look } }) != digest(S, &.{ .from = .Tty9p, .also = .{ .Look, .Look } })); +} + +test "a digest is of values: the same text at two addresses is one digest" { + const S = struct { name: []const u8, n: u32, next: ?*const u32 }; + const a = "same text"; + var b: [9]u8 = undefined; + @memcpy(&b, a); + const x: u32 = 7; + const y: u32 = 7; + try std.testing.expectEqual(digest(S, &.{ .name = a, .n = 1, .next = &x }), digest(S, &.{ .name = &b, .n = 1, .next = &y })); + try std.testing.expect(digest(S, &.{ .name = a, .n = 1, .next = &x }) != digest(S, &.{ .name = a, .n = 2, .next = &x })); +} + +test "an annotated field is in no digest, and a length cuts its array" { + const S = struct { + kept: u32, + cache: u32, + ring: [4]u8, + ring_len: u8, + pub const replica = .{ .derived = .{"cache"}, .len = .{.{ "ring", "ring_len" }} }; + }; + try std.testing.expectEqual( + digest(S, &.{ .kept = 1, .cache = 2, .ring = .{ 1, 2, 9, 9 }, .ring_len = 2 }), + digest(S, &.{ .kept = 1, .cache = 3, .ring = .{ 1, 2, 0, 0 }, .ring_len = 2 }), + ); +} + +// ---- the dump: the same walk, by name, for another build ---- +// +// A dump (docs/next-daemon.md, phase 2) is `dump_magic`, then a table of +// every type its roots' walk reaches -- each struct's and union's fields by +// name, each enum's names, each number's width -- then each root's value, +// laid out as `encode` lays it out but for three things: an enum or a +// union's tag is its place among the table's names, a pointer or a slice met +// again is a reference to the first (what two fields share is shared again), +// and a type with a `dumpWrite` of its own is its bytes, counted. +// +// A build that is not the writer's matches by name: a field added since +// takes its default, one removed is passed over, one whose kind changed +// takes its default and says so (`Decoder.notes`). With no default to take, +// the value it is part of is refused (`error.Incompatible`), and an element +// of an array of optional pointers (a session's panes) is then left out, +// nothing above it. A dump whose table is this build's own is read field +// after field, no name asked. +// +// Native byte order: the machines pardes runs on are all little-endian. + +pub const dump_magic = "pardes-dump\x00\x02\n"; + +const Kind = enum(u8) { skip, void, bool, int, float, @"enum", optional, one, slice, array, prefix, @"struct", @"union", err, error_union, custom, bitset }; + +/// std's lists: their items, not the capacity behind them (nor, in a safe +/// build, the lock that checks no pointer into them moves). +pub fn isList(comptime T: type) bool { + if (@typeInfo(T) != .@"struct" or !@hasField(T, "items") or !@hasField(T, "capacity")) return false; + const n = @typeInfo(T).@"struct".field_names.len; + return n == 2 or (n == 3 and @hasField(T, "pointer_stability")); +} +fn isAtomic(comptime T: type) bool { + return @typeInfo(T) == .@"struct" and @hasField(T, "raw") and @typeInfo(T).@"struct".field_names.len == 1 and @hasDecl(T, "load"); +} +fn isBitset(comptime T: type) bool { + return @typeInfo(T) == .@"struct" and @hasField(T, "bit_length") and @hasField(T, "masks") and @typeInfo(T).@"struct".field_names.len == 2; +} + +/// A field written only as far as its `len` says: a count, then that many. +fn Prefix(comptime E: type) type { + return struct { + pub const element = E; + }; +} + +/// What the dump walks `T` as: an atomic as what it holds, a list as its +/// items. +fn Canon(comptime T: type) type { + if (comptime isAtomic(T)) return Canon(@FieldType(T, "raw")); + if (comptime isList(T)) return []@typeInfo(@FieldType(T, "items")).pointer.child; + return T; +} + +fn kindOf(comptime T: type) Kind { + return switch (@typeInfo(T)) { + .void, .null, .undefined => .void, + .bool => .bool, + .int => .int, + .float => .float, + .@"enum" => .@"enum", + .optional => .optional, + .array => .array, + .pointer => |p| switch (p.size) { + .one => .one, + .slice => .slice, + else => @compileError("walk: a many-pointer has no length: " ++ @typeName(T)), + }, + .@"struct" => if (machinery(T) or @hasField(T, "any_future")) + .skip + else if (@hasDecl(T, "dumpWrite")) + .custom + else if (@hasDecl(T, "element") and T == Prefix(T.element)) + .prefix + else if (isBitset(T)) + .bitset + else + .@"struct", + .@"union" => |u| if (u.tag_type == null) @compileError("walk: an untagged union: " ++ @typeName(T)) else .@"union", + .error_set => .err, + .error_union => .error_union, + else => @compileError("walk: cannot dump " ++ @typeName(T)), + }; +} + +/// The fields of struct `T` a dump holds, in order. +fn dumpFields(comptime T: type) []const [:0]const u8 { + comptime { + @setEvalBranchQuota(1_000_000); + var names: []const [:0]const u8 = &.{}; + const s = @typeInfo(T).@"struct"; + for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime" or excluded(T, name) or kindOf(Canon(F)) == .skip) continue; + if (opaqueTo(F)) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is " ++ @typeName(F) ++ ", which no walk sees into: say what it is (`replica`)"); + names = names ++ .{name}; + } + return names; + } +} + +/// The type a dump walks field `name` of `T` as. +fn FieldDump(comptime T: type, comptime name: []const u8) type { + const F = @FieldType(T, name); + if (comptime cutArray(T, name)) return Prefix(Canon(@typeInfo(F).array.child)); + return Canon(F); +} + +/// A fixed array a `len` cuts, which a dump writes as far as it says. A +/// slice it cuts (a text's room for its ranges, made whole) is written +/// whole, room and all, which only plain numbers may be: a load gives it +/// the room it had. +fn cutArray(comptime T: type, comptime name: []const u8) bool { + const F = @FieldType(T, name); + if (comptime lengthOf(T, name) == null) return false; + if (@typeInfo(F) == .array) return true; + if (!plain(Element(F))) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is a slice a `len` cuts, of what a dump cannot write past the cut"); + return false; +} + +/// Every bit pattern one of its values: what a dump may write where +/// nothing was ever written. +fn plain(comptime T: type) bool { + return switch (@typeInfo(T)) { + .int, .float => true, + .array => |a| plain(a.child), + .@"struct" => |st| st.layout != .@"packed" and blk: { + for (st.field_types) |F| if (!plain(F)) break :blk false; + break :blk true; + }, + else => false, + }; +} + +fn children(comptime T: type) []const type { + comptime { + return switch (kindOf(T)) { + .optional => &.{Canon(@typeInfo(T).optional.child)}, + .one, .slice => &.{Canon(@typeInfo(T).pointer.child)}, + .array => &.{Canon(@typeInfo(T).array.child)}, + .prefix => &.{T.element}, + .error_union => &.{Canon(@typeInfo(T).error_union.payload)}, + .@"struct" => blk: { + var out: []const type = &.{}; + for (dumpFields(T)) |name| out = out ++ .{FieldDump(T, name)}; + break :blk out; + }, + .@"union" => blk: { + var out: []const type = &.{}; + for (@typeInfo(T).@"union".field_types) |F| out = out ++ .{Canon(F)}; + break :blk out; + }, + else => &.{}, + }; + } +} + +fn collect(comptime T: type, comptime list: []const type) []const type { + comptime { + for (list) |U| if (U == T) return list; + var out: []const type = list ++ .{T}; + if (kindOf(T) == .@"struct") checkAnnotations(T); + for (children(T)) |C| out = collect(C, out); + return out; + } +} + +/// Every type the walk of `roots` reaches, each once. +fn graph(comptime roots: []const type) []const type { + comptime { + @setEvalBranchQuota(100_000_000); + var list: []const type = &.{}; + for (roots) |R| list = collect(Canon(R), list); + return list; + } +} + +fn indexIn(comptime types: []const type, comptime T: type) u32 { + comptime { + @setEvalBranchQuota(100_000_000); + for (types, 0..) |U, i| if (U == T) return i; + @compileError("walk: not in the dump's table: " ++ @typeName(T)); + } +} + +/// How many bytes an integer of `bits` is written in: its own size. +fn intBytes(bits: u16) usize { + return if (bits == 0) 0 else if (bits <= 8) 1 else if (bits <= 16) 2 else if (bits <= 32) 4 else if (bits <= 64) 8 else 16; +} + +fn writeName(w: *std.Io.Writer, name: []const u8) !void { + try w.writeAll(std.mem.asBytes(&@as(u16, @intCast(name.len)))); + try w.writeAll(name); +} + +fn writeU32(w: *std.Io.Writer, n: u32) !void { + try w.writeAll(std.mem.asBytes(&n)); +} + +fn writeTable(comptime types: []const type, w: *std.Io.Writer) !void { + try writeU32(w, types.len); + inline for (types) |T| { + const k = comptime kindOf(T); + try w.writeByte(@intFromEnum(k)); + switch (k) { + .int => { + try w.writeByte(@intFromBool(@typeInfo(T).int.signedness == .signed)); + try w.writeAll(std.mem.asBytes(&@as(u16, @typeInfo(T).int.bits))); + }, + .float => try w.writeAll(std.mem.asBytes(&@as(u16, @typeInfo(T).float.bits))), + .@"enum" => { + const e = @typeInfo(T).@"enum"; + const tag = @typeInfo(e.tag_type).int; + try w.writeByte(@intFromBool(tag.signedness == .signed)); + try w.writeAll(std.mem.asBytes(&@as(u16, tag.bits))); + try writeU32(w, e.field_names.len); + inline for (e.field_names, e.field_values) |name, value| { + try writeName(w, name); + try w.writeAll(std.mem.asBytes(&@as(i128, value))); + } + }, + .array => { + try w.writeAll(std.mem.asBytes(&@as(u64, @typeInfo(T).array.len))); + try writeU32(w, comptime indexIn(types, children(T)[0])); + }, + .optional, .one, .slice, .prefix, .error_union => try writeU32(w, comptime indexIn(types, children(T)[0])), + .@"struct" => { + const names = comptime dumpFields(T); + try writeU32(w, names.len); + inline for (names) |name| { + try writeName(w, name); + try writeU32(w, comptime indexIn(types, FieldDump(T, name))); + } + }, + .@"union" => { + const u = @typeInfo(T).@"union"; + try writeU32(w, u.field_names.len); + inline for (u.field_names, u.field_types) |name, F| { + try writeName(w, name); + try writeU32(w, comptime indexIn(types, Canon(F))); + } + }, + .custom => try writeName(w, @typeName(T)), + .skip, .void, .bool, .err, .bitset => {}, + } + } +} + +/// Integers by value, in the bytes `intBytes` gives them: a `u21`'s +/// padding is no part of it. +fn putInt(comptime I: type, n: I, w: *std.Io.Writer) !void { + const info = @typeInfo(I).int; + const W = @Int(info.signedness, intBytes(info.bits) * 8); + const wide: W = n; + try w.writeAll(std.mem.asBytes(&wide)); +} + +/// Bytes the walk may copy whole between builds when both sides agree on +/// them: integers and bools (an enum's numbers may not be the other's). +fn isSigned(comptime T: type) bool { + return @typeInfo(T) == .int and @typeInfo(T).int.signedness == .signed; +} + +fn plainBytes(comptime T: type) bool { + return switch (@typeInfo(T)) { + .int => @sizeOf(T) * 8 == @bitSizeOf(T), + .bool => true, + else => false, + }; +} + +/// The table of `types` as bytes, made once a process (it is the build's): +/// a store record or a dump writes it, a load compares it. +fn tableOf(comptime types: []const type) []const u8 { + const Once = struct { + // Of these types alone: a container that named none of its + // function's parameters would be one for every table. + const of = types; + /// 0 none, 1 being made, 2 made. + var state: std.atomic.Value(u8) = .init(0); + var bytes: []const u8 = &.{}; + }; + if (Once.state.load(.acquire) == 2) return Once.bytes; + if (Once.state.cmpxchgStrong(0, 1, .acquire, .monotonic) == null) { + var out: std.Io.Writer.Allocating = .init(std.heap.page_allocator); + writeTable(types, &out.writer) catch @panic("walk: out of memory for a dump's table"); + Once.bytes = out.toOwnedSlice() catch @panic("walk: out of memory for a dump's table"); + Once.state.store(2, .release); + } else while (Once.state.load(.acquire) != 2) std.atomic.spinLoopHint(); + return Once.bytes; +} + +/// A blob's bytes a dump left out (`Dump.deferred`): they go at `at`. +pub const Deferred = struct { at: usize, bytes: []const u8 }; + +/// Writes a dump of `roots`' values, one `put` each in order. +pub fn Dump(comptime roots: []const type) type { + return struct { + const Self = @This(); + pub const types = graph(roots); + + gpa: std.mem.Allocator, + out: std.Io.Writer.Allocating, + memo: std.AutoHashMapUnmanaged(Key, u32) = .empty, + shared: u32 = 0, + /// Set: a `.blob`'s bytes (of `blob_min` and up) are not written but + /// noted, where they go and what they are; the dump with them put + /// back in place is the dump. A replica's join streams them from + /// its writer thread (src/replica.zig), the session's step paying + /// for the rest alone. + deferred: ?*std.ArrayListUnmanaged(Deferred) = null, + in_blob: bool = false, + + const Key = struct { addr: usize, len: usize, ty: u32 }; + + pub fn init(gpa: std.mem.Allocator) !Self { + var d: Self = .{ .gpa = gpa, .out = .init(gpa) }; + errdefer d.out.deinit(); + try d.out.writer.writeAll(dump_magic); + try d.out.writer.writeAll(tableOf(types)); + return d; + } + + pub fn deinit(d: *Self) void { + d.memo.deinit(d.gpa); + d.out.deinit(); + } + + /// The dump, the caller's (gpa). + pub fn finish(d: *Self) ![]u8 { + d.memo.deinit(d.gpa); + d.memo = .empty; + return d.out.toOwnedSlice(); + } + + pub fn put(d: *Self, comptime T: type, v: *const T) !void { + try writeU32(&d.out.writer, comptime indexIn(types, Canon(T))); + try d.value(T, v); + } + + /// Whether the pointer or slice at `addr` was met before: its + /// reference written if so, else 0 and it is noted. + fn seen(d: *Self, comptime T: type, addr: usize, len: usize) Error!bool { + const w = &d.out.writer; + if (len == 0) { + try writeU32(w, 0); + return false; + } + const got = try d.memo.getOrPut(d.gpa, .{ .addr = addr, .len = len, .ty = comptime indexIn(types, Canon(T)) }); + if (got.found_existing) { + try writeU32(w, got.value_ptr.*); + return true; + } + d.shared += 1; + got.value_ptr.* = d.shared; + try writeU32(w, 0); + return false; + } + + const Error = std.Io.Writer.Error || std.mem.Allocator.Error; + + fn items(d: *Self, comptime E: type, slice: []const E) Error!void { + const w = &d.out.writer; + try w.writeAll(std.mem.asBytes(&@as(u64, slice.len))); + if (comptime flat(E)) return w.writeAll(std.mem.sliceAsBytes(slice)); + for (slice) |*e| try d.value(E, e); + } + + fn value(d: *Self, comptime T: type, v: *const T) Error!void { + if (comptime isAtomic(T)) return d.value(@FieldType(T, "raw"), &v.raw); + const w = &d.out.writer; + if (comptime isList(T)) { + const E = @typeInfo(@FieldType(T, "items")).pointer.child; + if (try d.seen([]E, @intFromPtr(v.items.ptr), v.items.len)) return; + return d.items(E, v.items); + } + switch (comptime kindOf(T)) { + .skip, .void => {}, + .bool => try w.writeByte(@intFromBool(v.*)), + .int => try putInt(T, v.*, w), + .float => try w.writeAll(std.mem.asBytes(v)), + .@"enum" => try putInt(@typeInfo(T).@"enum".tag_type, @intFromEnum(v.*), w), + .optional => if (v.*) |*payload| { + try w.writeByte(1); + try d.value(@typeInfo(T).optional.child, payload); + } else try w.writeByte(0), + .one => { + const C = @typeInfo(T).pointer.child; + if (try d.seen(T, @intFromPtr(v.*), @max(1, @sizeOf(C)))) return; + try d.value(C, v.*); + }, + .slice => { + const E = @typeInfo(T).pointer.child; + if (try d.seen(T, @intFromPtr(v.ptr), v.len)) return; + if (comptime flat(E)) if (d.in_blob) if (d.deferred) |later| { + const bytes = std.mem.sliceAsBytes(v.*); + if (bytes.len >= blob_min) { + try w.writeAll(std.mem.asBytes(&@as(u64, v.len))); + return later.append(d.gpa, .{ .at = d.out.writer.end, .bytes = bytes }); + } + }; + try d.items(E, v.*); + }, + .array => { + const E = @typeInfo(T).array.child; + if (comptime flat(E)) return w.writeAll(std.mem.sliceAsBytes(v)); + for (v) |*e| try d.value(E, e); + }, + .prefix => unreachable, + .@"struct" => { + const packed_struct = comptime @typeInfo(T).@"struct".layout == .@"packed"; + inline for (comptime dumpFields(T)) |name| { + const F = @FieldType(T, name); + const was = d.in_blob; + d.in_blob = was or comptime blob(T, name); + defer d.in_blob = was; + if (comptime cutArray(T, name)) { + const all = &@field(v, name); + try d.items(@typeInfo(F).array.child, all[0..@min(all.len, lengthIn(v, comptime lengthOf(T, name).?))]); + } else if (packed_struct) { + const copy: F = @field(v, name); + try d.value(F, ©); + } else try d.value(F, &@field(v, name)); + } + }, + .@"union" => { + const tag = std.meta.activeTag(v.*); + const ordinal: u16 = inline for (@typeInfo(T).@"union".field_names, 0..) |name, i| { + if (tag == @field(std.meta.Tag(T), name)) break i; + } else unreachable; + try w.writeAll(std.mem.asBytes(&ordinal)); + switch (v.*) { + inline else => |*payload| try d.value(@TypeOf(payload.*), payload), + } + }, + .err => try writeName(w, @errorName(v.*)), + .error_union => if (v.*) |*payload| { + try w.writeByte(1); + try d.value(@typeInfo(T).error_union.payload, payload); + } else |err| { + try w.writeByte(0); + try writeName(w, @errorName(err)); + }, + .custom => { + const at = d.out.writer.end; + try w.writeAll(&std.mem.toBytes(@as(u64, 0))); + T.dumpWrite(v, d.gpa, w) catch return error.WriteFailed; + const n: u64 = d.out.writer.end - at - 8; + @memcpy(d.out.writer.buffer[at..][0..8], std.mem.asBytes(&n)); + }, + .bitset => { + try w.writeAll(std.mem.asBytes(&@as(u64, v.bit_length))); + const words = (v.bit_length + @bitSizeOf(usize) - 1) / @bitSizeOf(usize); + if (words > 0) try w.writeAll(std.mem.sliceAsBytes(v.masks[0..words])); + }, + } + } + }; +} + +/// One value `T` as a dump of its own (gpa): a closed pane, a terminal's +/// parts that are not its emulator. +pub fn save(comptime T: type, gpa: std.mem.Allocator, v: *const T) ![]u8 { + var d = try Dump(&.{T}).init(gpa); + errdefer d.deinit(); + try d.put(T, v); + return d.finish(); +} + +pub const DecodeError = error{ EndOfDump, BadDump, Incompatible, OutOfMemory }; + +/// The allocators a `replica.alloc` annotation may name, beside the +/// loader's own: `.alloc = .{ .{ "image", "image" } }` makes what field +/// `image` holds with `allocs.image`. +pub const Allocators = struct { + image: ?std.mem.Allocator = null, + pdf: ?std.mem.Allocator = null, + terminal: ?std.mem.Allocator = null, +}; + +fn allocOf(comptime T: type, comptime name: []const u8) ?[]const u8 { + if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "alloc")) return null; + inline for (T.replica.alloc) |pair| if (comptime std.mem.eql(u8, pair[0], name)) return pair[1]; + return null; +} + +fn countOf(n: u64) DecodeError!usize { + return std.math.cast(usize, n) orelse error.BadDump; +} + +/// An allocation a load made: what a reference to it finds, and what a +/// failed load frees. +const Made = struct { bytes: []u8, alignment: std.mem.Alignment, gpa: std.mem.Allocator, dead: bool = false }; + +/// A type as the dump's writer had it. +const SrcType = struct { + kind: Kind, + signed: bool = false, + bits: u16 = 0, + child: u32 = 0, + len: u64 = 0, + /// A struct's or union's fields, an enum's names (and `value`s). + fields: []const SrcField = &.{}, +}; +const SrcField = struct { name: []const u8, ty: u32 = 0, value: i128 = 0 }; + +/// Reads a dump of `roots`, one `into` or `get` each in order. +pub fn Load(comptime roots: []const type) type { + return struct { + const Self = @This(); + const types = graph(roots); + + /// Where what is read is made (a `replica.alloc` field's own + /// allocator while it is read). + gpa: std.mem.Allocator, + /// The loader's own lists'. + own: std.mem.Allocator, + bytes: []const u8, + at: usize = 0, + arena: std.heap.ArenaAllocator, + src: []SrcType = &.{}, + /// Its table is this build's: no name is asked. + same: bool = false, + /// Each pointer and slice made so far: what a reference finds, and + /// what `rollback` frees. + shared: std.ArrayList(Made) = .empty, + /// What a type's `dumpRead` made, freed by its `dumpFree` too. + customs: std.ArrayList(struct { ptr: *anyopaque, gpa: std.mem.Allocator, free: *const fn (*anyopaque, std.mem.Allocator) void }) = .empty, + /// What was let go, for the person whose session it is. + notes: std.ArrayList(u8) = .empty, + /// The field being read, for a note. + field: []const u8 = "", + /// Where a field's annotation (`replica.alloc`) says its values are + /// made instead of `gpa`. + allocs: Allocators = .{}, + + pub fn init(gpa: std.mem.Allocator, bytes: []const u8) DecodeError!Self { + var l: Self = .{ .gpa = gpa, .own = gpa, .bytes = bytes, .arena = .init(gpa) }; + errdefer l.arena.deinit(); + if (!std.mem.startsWith(u8, bytes, dump_magic)) return error.BadDump; + l.at = dump_magic.len; + const table_at = l.at; + try l.readTable(); + l.same = std.mem.eql(u8, tableOf(types), bytes[table_at..l.at]); + return l; + } + + pub fn deinit(l: *Self) void { + l.shared.deinit(l.own); + l.customs.deinit(l.own); + l.notes.deinit(l.own); + l.arena.deinit(); + } + + /// Everything read so far freed: a load that fails leaves nothing. + /// What it was read into must not be used after (nor freed). + pub fn rollback(l: *Self) void { + for (l.customs.items) |c| c.free(c.ptr, c.gpa); + for (l.shared.items) |m| if (m.bytes.len > 0) m.gpa.rawFree(m.bytes, m.alignment, @returnAddress()); + l.customs.clearRetainingCapacity(); + l.shared.clearRetainingCapacity(); + } + + fn made(l: *Self, bytes: []u8, alignment: std.mem.Alignment) DecodeError!usize { + try l.shared.append(l.own, .{ .bytes = bytes, .alignment = alignment, .gpa = l.gpa }); + return l.shared.items.len - 1; + } + + fn take(l: *Self, n: usize) DecodeError![]const u8 { + if (l.bytes.len - l.at < n) return error.EndOfDump; + defer l.at += n; + return l.bytes[l.at..][0..n]; + } + + fn scalar(l: *Self, comptime T: type) DecodeError!T { + return std.mem.bytesToValue(T, try l.take(@sizeOf(T))); + } + + /// A count, as this machine counts (a wasm32 one has 32 bits). + fn count(l: *Self) DecodeError!usize { + return countOf(try l.scalar(u64)); + } + + fn name(l: *Self) DecodeError![]const u8 { + return l.take(try l.scalar(u16)); + } + + fn readTable(l: *Self) DecodeError!void { + const a = l.arena.allocator(); + const n = try l.scalar(u32); + if (n > l.bytes.len) return error.BadDump; + l.src = try a.alloc(SrcType, n); + for (l.src) |*t| { + const k = std.enums.fromInt(Kind, (try l.take(1))[0]) orelse return error.BadDump; + t.* = .{ .kind = k }; + switch (k) { + .int => { + t.signed = (try l.take(1))[0] != 0; + t.bits = try l.scalar(u16); + }, + .float => t.bits = try l.scalar(u16), + .@"enum" => { + t.signed = (try l.take(1))[0] != 0; + t.bits = try l.scalar(u16); + const list = try a.alloc(SrcField, try l.scalar(u32)); + for (list) |*f| f.* = .{ .name = try l.name(), .value = try l.scalar(i128) }; + t.fields = list; + }, + .array => { + t.len = try l.scalar(u64); + t.child = try l.scalar(u32); + }, + .optional, .one, .slice, .prefix, .error_union => t.child = try l.scalar(u32), + .@"struct", .@"union" => { + const nfields = try l.scalar(u32); + if (nfields > l.bytes.len) return error.BadDump; + const list = try a.alloc(SrcField, nfields); + for (list) |*f| f.* = .{ .name = try l.name(), .ty = try l.scalar(u32) }; + t.fields = list; + }, + .custom => _ = try l.name(), + .skip, .void, .bool, .err, .bitset => {}, + } + } + for (l.src) |t| { + if (t.child >= n) return error.BadDump; + for (t.fields) |f| if (f.ty >= n) return error.BadDump; + } + } + + pub fn note(l: *Self, comptime fmt: []const u8, args: anytype) void { + if (l.notes.items.len > 4096) return; + l.notes.print(l.own, fmt ++ "\n", args) catch {}; + } + + fn root(l: *Self) DecodeError!u32 { + const ty = try l.scalar(u32); + if (ty >= l.src.len) return error.BadDump; + return ty; + } + + /// The next root, made: what it points at is `gpa`'s. + pub fn get(l: *Self, comptime T: type) DecodeError!T { + var out: T = undefined; + try l.fresh(T, &out); + try l.value(T, try l.root(), &out); + return out; + } + + /// The next root read into `out` as it stands: a field the dump + /// holds is replaced (what it held is not freed), every other one + /// is left as it is. A field another build cannot give is left too, + /// and noted. + pub fn into(l: *Self, comptime T: type, out: *T) DecodeError!void { + const ty = try l.root(); + const s = l.src[ty]; + if (s.kind != .@"struct") return error.BadDump; + try l.fields(T, s, out, true); + } + + /// `out` as a new `T` is before its fields are read: each field's + /// default, an allocator the dump's. + fn fresh(l: *Self, comptime T: type, out: *T) DecodeError!void { + if (comptime @typeInfo(T) != .@"struct" or isList(T) or isAtomic(T) or isBitset(T) or kindOf(T) == .custom) return; + if (comptime kindOf(T) == .skip) return; + const s = @typeInfo(T).@"struct"; + inline for (s.field_names, s.field_types, s.field_attrs) |field, F, attr| { + if (attr.@"comptime") continue; + if (comptime attr.default_value_ptr) |dp| { + @field(out, field) = @as(*const F, @ptrCast(@alignCast(dp))).*; + } else if (comptime F == std.mem.Allocator) { + @field(out, field) = l.gpa; + } else if (comptime !walkedField(T, field)) { + @compileError("walk: " ++ @typeName(T) ++ "." ++ field ++ " has no default to load to"); + } + } + } + + fn walkedField(comptime T: type, comptime field: []const u8) bool { + inline for (comptime dumpFields(T)) |n| if (comptime std.mem.eql(u8, n, field)) return true; + return false; + } + + /// Whether the source's `ty` and `T` are of one kind, else the + /// source's value passed over. + fn kindMatches(l: *Self, comptime T: type, ty: u32) DecodeError!bool { + if (l.same) return true; + const want = comptime kindOf(Canon(T)); + const got = l.src[ty].kind; + if (got == want) return true; + // A field that came to hold a count and so many, or stopped. + if ((want == .array and got == .prefix) or (want == .prefix and got == .array)) return true; + try l.skip(ty); + return false; + } + + fn readInt(l: *Self, comptime I: type, s: SrcType) DecodeError!I { + if (l.same) { + const info = @typeInfo(I).int; + const W = @Int(info.signedness, intBytes(info.bits) * 8); + return @intCast(try l.scalar(W)); + } + const n = intBytes(s.bits); + const raw = try l.take(n); + var wide: u128 = 0; + for (raw, 0..) |b, i| wide |= @as(u128, b) << @intCast(i * 8); + if (s.signed and n > 0) { + const shift: u7 = @intCast(128 - n * 8); + const signed: i128 = @as(i128, @bitCast(wide << shift)) >> shift; + return std.math.cast(I, signed) orelse error.Incompatible; + } + return std.math.cast(I, wide) orelse error.Incompatible; + } + + /// `T` read from the source's type `ty` into `out`, which `fresh` + /// has made ready. + fn value(l: *Self, comptime T: type, ty: u32, out: *T) DecodeError!void { + if (comptime isAtomic(T)) { + const R = @FieldType(T, "raw"); + var raw: R = undefined; + try l.fresh(R, &raw); + try l.value(R, ty, &raw); + out.* = .{ .raw = raw }; + return; + } + // A field this build compiles out (a PDF slot where there is no + // MuPDF): passed over, said only when it held something. + if (comptime kindOf(Canon(T)) == .void) if (!l.same and l.src[ty].kind != .void) { + const held = l.src[ty].kind != .optional or (l.at < l.bytes.len and l.bytes[l.at] != 0); + try l.skip(ty); + if (held) l.note("{s}: not in this build", .{l.field}); + return; + }; + if (!try l.kindMatches(T, ty)) return error.Incompatible; + const s = l.src[ty]; + if (comptime isList(T)) { + const E = @typeInfo(@FieldType(T, "items")).pointer.child; + const got = try l.slice(E, s); + out.* = .empty; + out.items = got; + out.capacity = got.len; + return; + } + switch (comptime kindOf(T)) { + .skip, .void => {}, + .bool => out.* = (try l.take(1))[0] != 0, + .int => out.* = try l.readInt(T, s), + .float => { + if (l.same or s.bits == @typeInfo(T).float.bits) { + out.* = try l.scalar(T); + } else if (s.bits == 32) { + out.* = @floatCast(try l.scalar(f32)); + } else if (s.bits == 64) { + out.* = @floatCast(try l.scalar(f64)); + } else return error.Incompatible; + }, + .@"enum" => { + const e = @typeInfo(T).@"enum"; + if (l.same) { + out.* = @enumFromInt(try l.readInt(e.tag_type, s)); + return; + } + const n = try l.readInt(i128, s); + const was = for (s.fields) |f| { + if (f.value == n) break f.name; + } else null; + if (was) |w| inline for (e.field_names) |field| if (std.mem.eql(u8, w, field)) { + out.* = @field(T, field); + return; + }; + if (e.mode == .nonexhaustive and was == null) + if (std.math.cast(e.tag_type, n)) |tag| { + out.* = @enumFromInt(tag); + return; + }; + l.note("{s}: no {s} here", .{ l.field, was orelse "such value" }); + return error.Incompatible; + }, + .optional => { + const C = @typeInfo(T).optional.child; + if ((try l.take(1))[0] == 0) { + out.* = null; + return; + } + if (comptime kindOf(Canon(C)) == .skip) { + out.* = if (comptime C == std.mem.Allocator) l.gpa else null; + return; + } + // A slice's or a pointer's null is its address: set to + // an undefined payload, the optional itself is undefined, + // and ReleaseSafe's optimizer read it as null (a pane's + // `?[]u8` command one byte long, every field after it out + // of step). Read through a local and set it from that. + if (comptime @typeInfo(C) == .pointer) { + var payload: C = undefined; + try l.value(C, s.child, &payload); + out.* = payload; + return; + } + out.* = @as(C, undefined); + try l.fresh(C, &out.*.?); + l.value(C, s.child, &out.*.?) catch |err| { + out.* = null; + return err; + }; + }, + .one => { + const C = @typeInfo(T).pointer.child; + if (try l.ref()) |again| { + out.* = @ptrCast(@alignCast(again.ptr)); + return; + } + const one = try l.gpa.create(C); + const at = l.made(std.mem.asBytes(one), .of(C)) catch |err| { + l.gpa.destroy(one); + return err; + }; + try l.fresh(C, one); + l.value(C, s.child, one) catch |err| { + // Left half made: no later reference may find it. + l.shared.items[at].dead = true; + return err; + }; + out.* = one; + }, + .slice => { + const E = @typeInfo(T).pointer.child; + const got = try l.slice(E, s); + if (comptime @typeInfo(T).pointer.sentinel_ptr != null) @compileError("walk: a sentinel slice: " ++ @typeName(T)); + out.* = got; + }, + .array => { + const E = @typeInfo(T).array.child; + const n: u64 = if (s.kind == .prefix) try l.scalar(u64) else s.len; + try l.elements(E, s.child, n, out); + }, + .prefix => unreachable, + .@"struct" => try l.fields(T, s, out, false), + .@"union" => { + const u = @typeInfo(T).@"union"; + const ordinal = try l.scalar(u16); + if (ordinal >= s.fields.len) return error.BadDump; + const was = s.fields[ordinal]; + inline for (u.field_names, u.field_types, 0..) |field, F, i| { + if (if (l.same) ordinal == i else std.mem.eql(u8, was.name, field)) { + out.* = @unionInit(T, field, undefined); + try l.fresh(F, &@field(out.*, field)); + return l.value(F, was.ty, &@field(out.*, field)); + } + } + try l.skip(was.ty); + l.note("{s}: no {s} here", .{ l.field, was.name }); + return error.Incompatible; + }, + .err => out.* = try l.errorNamed(T), + .error_union => { + const P = @typeInfo(T).error_union.payload; + if ((try l.take(1))[0] != 0) { + var payload: P = undefined; + try l.fresh(P, &payload); + try l.value(P, s.child, &payload); + out.* = payload; + } else out.* = try l.errorNamed(@typeInfo(T).error_union.error_set); + }, + .custom => { + const bytes = try l.take(try l.count()); + T.dumpRead(out, l.gpa, bytes) catch |err| { + if (err == error.OutOfMemory) return error.OutOfMemory; + l.note("{s}: {t}", .{ l.field, err }); + return error.Incompatible; + }; + if (comptime @hasDecl(T, "dumpFree")) try l.customs.append(l.own, .{ .ptr = out, .gpa = l.gpa, .free = @ptrCast(&T.dumpFree) }); + }, + .bitset => { + const bits = try l.count(); + out.* = try .initEmpty(l.gpa, bits); + const words = (bits + @bitSizeOf(usize) - 1) / @bitSizeOf(usize); + if (words > 0) @memcpy(std.mem.sliceAsBytes(out.masks[0..words]), try l.take(words * @sizeOf(usize))); + }, + } + } + + fn errorNamed(l: *Self, comptime E: type) DecodeError!E { + const was = try l.name(); + const names = @typeInfo(E).error_set.error_names orelse @compileError("walk: anyerror cannot be loaded by name: " ++ @typeName(E)); + inline for (names) |field| if (std.mem.eql(u8, was, field)) return @field(E, field); + return error.Incompatible; + } + + /// A reference to a pointer or slice made before, or null for a + /// new one (its length then read). + fn ref(l: *Self) DecodeError!?[]u8 { + const n = try l.scalar(u32); + if (n == 0) return null; + if (n > l.shared.items.len) return error.BadDump; + const got = l.shared.items[n - 1]; + if (got.dead) return error.Incompatible; + return got.bytes; + } + + fn slice(l: *Self, comptime E: type, s: SrcType) DecodeError![]E { + if (try l.ref()) |again| return @as([*]E, @ptrCast(@alignCast(again.ptr)))[0 .. again.len / @max(1, @sizeOf(E))]; + const n = try l.count(); + if (n == 0) return &.{}; + if (n > l.bytes.len) return error.BadDump; + const many = try l.gpa.alloc(E, n); + const at = l.made(std.mem.sliceAsBytes(many), .of(E)) catch |err| { + l.gpa.free(many); + return err; + }; + l.elements(E, s.child, n, many) catch |err| { + l.shared.items[at].dead = true; + return err; + }; + return many; + } + + /// `n` elements of the source's type `ty` into `out` (an array or + /// a slice), as many as it holds, the rest passed over. + fn elements(l: *Self, comptime E: type, ty: u32, n: u64, out: anytype) DecodeError!void { + const keep: usize = @intCast(@min(n, out.len)); + const s = l.src[ty]; + const bulk = if (comptime flat(E)) l.same or (comptime plainBytes(E)) and s.kind == (comptime kindOf(E)) and + (s.kind == .bool or (s.bits == @bitSizeOf(E) and s.signed == isSigned(E))) else false; + if (bulk) { + if (n > l.bytes.len) return error.EndOfDump; + @memcpy(std.mem.sliceAsBytes(out[0..keep]), try l.take(keep * @sizeOf(E))); + _ = try l.take(@intCast((n - keep) * @sizeOf(E))); + return; + } + // An array of optional pointers (a session's panes): one that + // cannot be read is left out, not the array. + const droppable = comptime @typeInfo(E) == .optional and @typeInfo(@typeInfo(E).optional.child) == .pointer; + var failed = false; + for (0..try countOf(n)) |i| { + if (i >= keep) { + try l.skip(ty); + continue; + } + try l.fresh(E, &out[i]); + l.value(E, ty, &out[i]) catch |err| { + if (err != error.Incompatible) return err; + if (droppable) { + out[i] = null; + l.note("{s}[{d}] left out", .{ l.field, i }); + } else failed = true; + }; + } + if (failed) return error.Incompatible; + } + + fn fields(l: *Self, comptime T: type, s: SrcType, out: *T, existing: bool) DecodeError!void { + const names = comptime dumpFields(T); + const packed_struct = comptime @typeInfo(T).@"struct".layout == .@"packed"; + const outer = l.field; + defer l.field = outer; + if (l.same) { + if (s.fields.len != names.len) return error.BadDump; + inline for (names, 0..) |field, k| { + l.field = field; + try l.oneField(T, field, s.fields[k].ty, out, packed_struct, existing); + } + return; + } + var found: std.StaticBitSet(@max(1, names.len)) = .empty; + var failed = false; + for (s.fields) |f| { + const k: ?usize = inline for (names, 0..) |field, k| { + if (std.mem.eql(u8, f.name, field)) break k; + } else null; + const at = k orelse { + try l.skip(f.ty); + continue; + }; + found.set(at); + inline for (names, 0..) |field, i| if (i == at) { + l.field = field; + l.oneField(T, field, f.ty, out, packed_struct, existing) catch |err| { + if (err != error.Incompatible) return err; + const attr = comptime @typeInfo(T).@"struct".field_attrs[std.meta.fieldIndex(T, field).?]; + if (comptime attr.default_value_ptr) |dp| { + @field(out, field) = @as(*const @FieldType(T, field), @ptrCast(@alignCast(dp))).*; + l.note("{s}.{s}: its kind changed; its default taken", .{ @typeName(T), field }); + } else if (existing) { + l.note("{s}.{s}: its kind changed; left as it was", .{ @typeName(T), field }); + } else failed = true; + }; + }; + } + // A field the writer did not have: its default (`fresh`), or + // the value cannot be made. + inline for (names, 0..) |field, i| if (!found.isSet(i)) { + const attr = comptime @typeInfo(T).@"struct".field_attrs[std.meta.fieldIndex(T, field).?]; + if (comptime attr.default_value_ptr == null) { + if (!existing) { + l.note("{s}.{s}: not in the dump", .{ @typeName(T), field }); + failed = true; + } + } + }; + if (failed) return error.Incompatible; + } + + fn oneField(l: *Self, comptime T: type, comptime field: []const u8, ty: u32, out: *T, comptime packed_struct: bool, existing: bool) DecodeError!void { + const F = @FieldType(T, field); + const gpa = l.gpa; + defer l.gpa = gpa; + if (comptime allocOf(T, field)) |which| if (@field(l.allocs, which)) |a| { + l.gpa = a; + }; + if (comptime cutArray(T, field)) { + return l.value(F, ty, &@field(out, field)); + } + // A struct held in place in one read as it stands (the root's): + // what it does not hold stays as it is too. + if (comptime kindOf(Canon(F)) == .@"struct" and Canon(F) == F and @typeInfo(F).@"struct".layout != .@"packed") if (existing) { + if (!try l.kindMatches(F, ty)) return error.Incompatible; + return l.fields(F, l.src[ty], &@field(out, field), true); + }; + if (packed_struct) { + var copy: F = undefined; + try l.fresh(F, ©); + try l.value(F, ty, ©); + @field(out, field) = copy; + return; + } + try l.fresh(F, &@field(out, field)); + try l.value(F, ty, &@field(out, field)); + } + + /// The source's value of type `ty` passed over. + fn skip(l: *Self, ty: u32) DecodeError!void { + const s = l.src[ty]; + switch (s.kind) { + .skip, .void => {}, + .bool => _ = try l.take(1), + .int, .@"enum" => _ = try l.take(intBytes(s.bits)), + .float => _ = try l.take(s.bits / 8), + .optional => if ((try l.take(1))[0] != 0) try l.skip(s.child), + .one => if (try l.scalar(u32) == 0) { + _ = try l.made(&.{}, .@"1"); + l.shared.items[l.shared.items.len - 1].dead = true; + try l.skip(s.child); + }, + .slice => if (try l.scalar(u32) == 0) { + const n = try l.scalar(u64); + if (n > 0) { + _ = try l.made(&.{}, .@"1"); + l.shared.items[l.shared.items.len - 1].dead = true; + } + try l.skipMany(s.child, n); + }, + .prefix => try l.skipMany(s.child, try l.scalar(u64)), + .array => try l.skipMany(s.child, s.len), + .@"struct" => for (s.fields) |f| try l.skip(f.ty), + .@"union" => { + const ordinal = try l.scalar(u16); + if (ordinal >= s.fields.len) return error.BadDump; + try l.skip(s.fields[ordinal].ty); + }, + .err => _ = try l.name(), + .error_union => if ((try l.take(1))[0] != 0) try l.skip(s.child) else { + _ = try l.name(); + }, + .custom => _ = try l.take(try l.count()), + .bitset => _ = try l.take((try l.count() + 63) / 64 * 8), + } + } + + fn skipMany(l: *Self, ty: u32, n: u64) DecodeError!void { + const s = l.src[ty]; + if (s.kind == .int or s.kind == .bool) { + const size: u64 = if (s.kind == .bool) 1 else intBytes(s.bits); + if (n > l.bytes.len) return error.EndOfDump; + _ = try l.take(@intCast(n * size)); + return; + } + for (0..try countOf(n)) |_| try l.skip(ty); + } + }; +} + +/// A value `save` made, `gpa`'s; what was let go is said in `notes` when +/// it is given. +pub fn load(comptime T: type, gpa: std.mem.Allocator, bytes: []const u8, notes: ?*std.ArrayList(u8)) DecodeError!T { + var l = try Load(&.{T}).init(gpa, bytes); + defer l.deinit(); + errdefer l.rollback(); + const v = try l.get(T); + if (notes) |n| try n.appendSlice(gpa, l.notes.items); + return v; +} + +test "an optional slice comes back, and the fields after it" { + const S = struct { before: u32 = 0, command: ?[]u8 = null, after: u32 = 0 }; + var text = "sleep 30".*; + const bytes = try save(S, std.testing.allocator, &.{ .before = 1, .command = &text, .after = 2 }); + defer std.testing.allocator.free(bytes); + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + const back = try load(S, arena.allocator(), bytes, null); + try std.testing.expectEqualStrings("sleep 30", back.command.?); + try std.testing.expectEqual(2, back.after); +} + +test "a dump comes back whole: shared things shared, lists and runs as long as they were" { + const gpa = std.testing.allocator; + const Leaf = struct { n: u21, name: []const u8 }; + const Mode = enum { a, b, c }; + const S = struct { + mode: Mode = .a, + leaf: *Leaf, + same_leaf: *Leaf, + text: []u8, + same_text: []u8, + list: std.ArrayList(u16) = .empty, + maybe: ?Leaf = null, + either: union(enum) { none, some: u32, many: []const u16 } = .none, + ring: [4]u8 = @splat(0), + ring_len: u8 = 0, + room: []i32 = &.{}, + room_len: u8 = 0, + cache: u64 = 7, + alloc: std.mem.Allocator, + flags: packed struct { x: bool = false, y: u3 = 0 } = .{}, + pub const replica = .{ .derived = .{"cache"}, .len = .{ .{ "ring", "ring_len" }, .{ "room", "room_len" } } }; + }; + var leaf: Leaf = .{ .n = 0x1fffff, .name = "leaf" }; + var room = [_]i32{ 4, 5, -1, -1 }; + var text = "shared text".*; + var list: std.ArrayList(u16) = .empty; + defer list.deinit(gpa); + try list.appendSlice(gpa, &.{ 1, 2, 3 }); + const x: S = .{ .mode = .c, .leaf = &leaf, .same_leaf = &leaf, .text = &text, .same_text = &text, .list = list, .maybe = .{ .n = 3, .name = "maybe" }, .either = .{ .many = &.{ 9, 8 } }, .ring = .{ 5, 6, 0xAA, 0xAA }, .ring_len = 2, .room = &room, .room_len = 2, .cache = 99, .alloc = gpa, .flags = .{ .x = true, .y = 5 } }; + const bytes = try save(S, gpa, &x); + defer gpa.free(bytes); + var arena: std.heap.ArenaAllocator = .init(gpa); + defer arena.deinit(); + const y = try load(S, arena.allocator(), bytes, null); + try std.testing.expectEqual(digest(S, &x), digest(S, &y)); + try std.testing.expect(y.leaf == y.same_leaf and y.text.ptr == y.same_text.ptr); + try std.testing.expectEqual(@as(u64, 7), y.cache); + try std.testing.expectEqualSlices(u16, &.{ 1, 2, 3 }, y.list.items); + try std.testing.expectEqual(true, y.flags.x); + // A slice its `len` cuts keeps its room. + try std.testing.expectEqual(@as(usize, 4), y.room.len); + try std.testing.expectEqualSlices(i32, &.{ 4, 5 }, y.room[0..2]); + // A fixpoint: what was read is written as it was. + const again = try save(S, gpa, &y); + defer gpa.free(again); + try std.testing.expectEqualSlices(u8, bytes, again); +} + +test "a dump crosses builds: a field added takes its default, one removed is passed over, one changed is left out" { + const gpa = std.testing.allocator; + const Old = struct { + const Color = enum { red, green, blue }; + const Pane = struct { name: []const u8, color: Color = .red, gone: u32 = 1, width: u16 = 0, kind: u32 = 0 }; + panes: [3]?*Pane = @splat(null), + count: u8 = 0, + renamed: u32 = 0, + }; + const New = struct { + // Values renumbered and one added before the others. + const Color = enum { cyan, blue, red, green }; + const Wide = struct { a: u8 }; + const Pane = struct { added: bool = true, color: Color = .cyan, width: u32 = 0, name: []const u8, kind: Wide = .{ .a = 4 } }; + // A pane's required field changed kind: that pane is left out. + const Strict = struct { name: u8 }; + panes: [4]?*Pane = @splat(null), + count: u16 = 0, + renamed_now: u32 = 5, + }; + var one: Old.Pane = .{ .name = "one", .color = .blue, .gone = 9, .width = 300, .kind = 2 }; + var two: Old.Pane = .{ .name = "two", .color = .green }; + const old: Old = .{ .panes = .{ &one, null, &two }, .count = 2, .renamed = 7 }; + const bytes = try save(Old, gpa, &old); + defer gpa.free(bytes); + var arena: std.heap.ArenaAllocator = .init(gpa); + defer arena.deinit(); + // The notes are made where the load's values are. + var notes: std.ArrayList(u8) = .empty; + const new = try load(New, arena.allocator(), bytes, ¬es); + try std.testing.expectEqual(@as(u16, 2), new.count); + try std.testing.expectEqual(@as(u32, 5), new.renamed_now); + const a = new.panes[0].?; + try std.testing.expectEqualStrings("one", a.name); + try std.testing.expectEqual(New.Color.blue, a.color); + try std.testing.expectEqual(@as(u32, 300), a.width); + try std.testing.expect(a.added); + try std.testing.expectEqual(@as(u8, 4), a.kind.a); + try std.testing.expect(new.panes[1] == null and new.panes[3] == null); + try std.testing.expectEqual(New.Color.green, new.panes[2].?.color); + try std.testing.expect(std.mem.indexOf(u8, notes.items, "kind") != null); + + const Strict = struct { + const Pane = struct { name: u8 }; + panes: [3]?*Pane = @splat(null), + count: u8 = 0, + }; + notes.clearRetainingCapacity(); + const strict = try load(Strict, arena.allocator(), bytes, ¬es); + try std.testing.expect(strict.panes[0] == null and strict.panes[2] == null); + try std.testing.expectEqual(@as(u8, 2), strict.count); + try std.testing.expect(std.mem.indexOf(u8, notes.items, "left out") != null); + + // And back: the newer build's dump read by the older one. + const newer = try save(New, gpa, &new); + defer gpa.free(newer); + const back = try load(Old, arena.allocator(), newer, null); + try std.testing.expectEqualStrings("two", back.panes[2].?.name); + try std.testing.expectEqual(@as(u32, 1), back.panes[0].?.gone); + try std.testing.expectEqual(Old.Color.blue, back.panes[0].?.color); +} + +test "a dump that is not one, or is cut short, is refused" { + const gpa = std.testing.allocator; + const S = struct { a: u32, b: []const u8 }; + try std.testing.expectError(error.BadDump, load(S, gpa, "not a dump", null)); + const bytes = try save(S, gpa, &.{ .a = 1, .b = "bee" }); + defer gpa.free(bytes); + // What it made before the end is freed again. + try std.testing.expectError(error.EndOfDump, load(S, gpa, bytes[0 .. bytes.len - 2], null)); +} + +test "a blob is hashed once and folded in as a word; one written in place is not its word, which a Debug build checks; a freed one's word goes" { + const memory = @import("memory.zig"); + const digestOfBlob = struct { + fn of(items: []const u8) u64 { + var h = Hasher.init(0); + hashSlice(u8, items, &h); + return h.final(); + } + }.of; + const gpa = std.testing.allocator; + const File = struct { + pub const replica = .{ .blob = .{"content"} }; + content: []u8, + cursor: u32 = 0, + }; + const text = try gpa.alloc(u8, 64 << 10); + @memset(text, 'a'); + var f: File = .{ .content = text }; + const before = digest(File, &f); + try std.testing.expect(wordOf(@intFromPtr(text.ptr)) != null); + // The same word again: nothing it holds moved. + try std.testing.expectEqual(before, digest(File, &f)); + // Written in place, which a blob never is: its kept word is no longer + // its hash, which a Debug build's digest checks (and panics at) where a + // release build's would fold the old word in. + text[1000] = 'b'; + try std.testing.expect(wordOf(@intFromPtr(text.ptr)).? != digestOfBlob(text)); + text[1000] = 'a'; + try std.testing.expectEqual(digestOfBlob(text), wordOf(@intFromPtr(text.ptr)).?); + // Freed, its word goes: an address used again is hashed again. + memory.freeUnfilled(gpa, text); + try std.testing.expect(wordOf(@intFromPtr(text.ptr)) == null); +} |
