summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/walk.zig393
1 files changed, 393 insertions, 0 deletions
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 }),
+ );
+}