diff options
Diffstat (limited to 'src/walk.zig')
| -rw-r--r-- | src/walk.zig | 1120 |
1 files changed, 1117 insertions, 3 deletions
diff --git a/src/walk.zig b/src/walk.zig index 3e482e9a..ce097c0e 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -132,7 +132,7 @@ 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; + 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); } } @@ -159,8 +159,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { 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) + 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. @@ -401,3 +400,1118 @@ test "an annotated field is in no digest, and a length cuts its array" { 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 lengthOf(T, name) != null) return Prefix(Canon(@typeInfo(F).array.child)); + return Canon(F); +} + +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, + }; +} + +/// 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, + next_root: usize = 0, + + 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 writeTable(types, &d.out.writer); + 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); + d.next_root += 1; + } + + /// 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; + 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); + if (comptime lengthOf(T, name)) |len| { + const all = &@field(v, name); + try d.items(@typeInfo(F).array.child, all[0..@min(all.len, lengthIn(v, len))]); + } 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, +}; + +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; +} + +/// 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(); + var mine: std.Io.Writer.Allocating = .init(gpa); + defer mine.deinit(); + writeTable(types, &mine.writer) catch return error.OutOfMemory; + l.same = std.mem.eql(u8, mine.written(), 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))); + } + + 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 count = try l.scalar(u32); + if (count > l.bytes.len) return error.BadDump; + const list = try a.alloc(SrcField, count); + 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; + } + 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; + } + 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 n = try l.scalar(u64); + const bytes = try l.take(n); + 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.scalar(u64); + 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.scalar(u64); + 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..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 lengthOf(T, field) != null) { + 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.scalar(u64)), + .bitset => _ = try l.take((try l.scalar(u64) + 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..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 "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, + 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" }} }; + }; + var leaf: Leaf = .{ .n = 0x1fffff, .name = "leaf" }; + 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, .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 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)); +} |
