//! 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 }), ); }