From 3b793d1d349c01bf6046b0f87742f16755069115 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 11:14:38 -0300 Subject: walk.zig: the reflective walker, one comptime @typeInfo walk that hashes a value (the replay digest) and encodes and decodes it (the tape's values) Values, never addresses: a pointer is followed, a slice is its elements, an ArrayList its items, a hash map its entries in no order, a DynamicBitSet its bits; an allocator, an Io, a lock or a worker's future is machinery and walks to nothing. A type it cannot see into (a pointer to an opaque thing or a function, a many-pointer, an untagged union) is a compile error naming the struct and the field, until the struct says what the field is: pub const replica = .{ .local = .{...}, .derived = .{...}, .authority = .{...}, .len = .{ .{ "jumps", "njumps" } } }; local (this process's own: frames, animations, caches of the host's), derived (made again from the rest), authority (held by the session that performs effects alone) are in no digest; `len` hashes a fixed array only as far as its length field says, since the rest is undefined (0xAA in a safe build, and a slice in it faults). A name that is no field is a compile error, so a rename cannot put a field back in quietly. `fieldDigests`/`fieldNames` give a digest a field, which is how a divergence is narrowed down. encode/decode are native byte order and an error is its number in this build: for the process that wrote it, or one of the same build. Phase 2 is to make the complete dump on the same walk (docs/next-daemon.md); nothing uses it yet. Co-Authored-By: Claude Opus 5.5 --- src/walk.zig | 393 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 393 insertions(+) create mode 100644 src/walk.zig (limited to 'src') diff --git a/src/walk.zig b/src/walk.zig new file mode 100644 index 00000000..dc1664cb --- /dev/null +++ b/src/walk.zig @@ -0,0 +1,393 @@ +//! The reflective walk over the core's state: one comptime `@typeInfo` walk +//! that hashes a session into a digest (the replay harness compares two), +//! and that the complete dump and the rollback copy are 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" } }, +//! }; +//! +//! None of the three kinds is in a digest. A type with a `pub fn +//! digest(*const T, *Hasher) void` of its own hashes itself. +const std = @import("std"); + +pub const Hasher = std.hash.Wyhash; + +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); + if (comptime lengthOf(T, name)) |len| { + hashSlice(@typeInfo(F).array.child, @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. +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, + }; +} + +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). +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 { + @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")) 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" => |e| hashInt(e.tag_type, @intFromEnum(v.*), h), + .optional => |o| if (v.*) |*payload| { + h.update(&.{1}); + hash(o.child, payload, h); + } else h.update(&.{0}), + .array => |a| if (comptime flat(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); + // std's lists: the items, not the capacity behind them. + if (comptime @hasField(T, "items") and @hasField(T, "capacity") and s.field_names.len == 2) + 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`)"); + if (comptime lengthOf(T, name)) |len| { + hashSlice(@typeInfo(F).array.child, @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)), + } +} + +/// 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 { + h.update(std.mem.asBytes(&items.len)); + if (comptime flat(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). +/// Only for the process that wrote it, or one of the same build: native +/// byte order, and an error as its number in this build. +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 w.writeAll(std.mem.asBytes(&@as(u16, @intFromError(v.*)))), + .error_union => |e| if (v.*) |*payload| { + try w.writeByte(1); + try encode(e.payload, payload, w); + } else |err| { + try w.writeByte(0); + try w.writeAll(std.mem.asBytes(&@as(u16, @intFromError(err)))); + }, + else => @compileError("walk: cannot encode " ++ @typeName(T)), + } +} + +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))); + } +}; + +/// 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) error{ EndOfTape, OutOfMemory }!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. + @field(out, name) = @errorCast(@errorFromInt(try r.scalar(u16))); + } 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_set => return @errorCast(@errorFromInt(try r.scalar(u16))), + .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. + const err: e.error_set = @errorCast(@errorFromInt(try r.scalar(u16))); + return @as(T, err); + }, + else => @compileError("walk: cannot decode " ++ @typeName(T)), + } +} + +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 "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 }), + ); +} -- cgit v1.3