Artifact 50dca92cdedd59026bb35362fe60b3c0edc48407fb3adb4a4c1957c6977511eb:
- File
src/repoimage.zig
— part of check-in
[9033c13f21]
at
2026-09-17 17:04:25
on branch trunk
— Remove issue-tracker numbers from source and documents
The tracker is disposable and does not live with the source, so a number is a dangling pointer. Every zit#NN and #NN reference in code comments, test names, help text, smoke labels, identifiers, release notes and errata is replaced by enough context to stand alone, or by a short plain statement of the problem. No behaviour changed. (user: dmestas, size: 55013) [annotate] [blame] [check-ins using]
//! zit — the materialized read-image: the hot query answers of a fully-derived //! `RepoState`, laid out as dense integer-addressed columns so a warm read can //! serve `leaves`/`log`/`timeline` with ZERO re-derivation. The derivation //! (`crosslink`: nine hashmaps + tag propagation + adjacency) is what a warm //! read pays today; this module memoises its RESULT once, at cache-write, and //! reloads it as offset-addressed windows — no hashmap fill, no propagation, no //! adjacency walk, no relocation. //! //! Provenance of the technique (plain engineering attribution): //! - Roc / Richard Feldman — reload an on-disk cache image without re-parsing. //! - Zig compiler / Andrew Kelley — dense integer-indexed arrays as the load //! format: relocation-free, offset-addressed sections read in place. //! - Casey Muratori / game-dev — struct-of-arrays column layout for locality. //! - compact_arena — a distinct `enum(u32)` index family per column so one //! column's slot can never address another's storage. //! //! Boundary (Ousterhout): the representation is information-hidden here. The //! cache (`repocache`) moves opaque bytes and never sees a column; `RepoState` //! delegates its freed query methods to an `Image` and keeps its public //! interface byte-identical. The image is a MEMO of RFC-derived answers — the //! leaf table (repo-state §7.1), the open predicate (§7.4), event times //! (§7.5/§8.3), branch-of (§6.1), and symbolic-name resolution (§8.2) — never a //! second source of truth. //! //! Safety (TigerStyle): the format is untrusted on load. Every span is //! validated once, before any column is read (bounds, CSR monotonicity, //! terminal-offset equality, every stored rid in range); ANY violation makes //! `Image.load` return null, which the caller treats as a MISS and derives. A //! returned `Image` therefore answers every query strictly in bounds: the //! guarantee rests on LOAD-TIME validation — every column length, CSR span, and //! stored rid/branch-id is range-checked with `return null` before the `Image` //! is handed back, so every later index is provably in range even in ReleaseFast //! (where the belt-and-suspenders per-deref asserts compile out). All image //! bytes are `[]const u8`. const std = @import("std"); const repostate = @import("repostate.zig"); const Rid = repostate.Rid; const Mtime = repostate.Mtime; /// Sentinel branch-name id: the rid carries no active branch tag, so `branchOf` /// falls back to the caller's `main_branch` (§6.1/§6.4). `0xFFFF_FFFF` cannot /// collide with a real name id (`< n_branch_names`, itself `<= n_rids`). const no_branch: u32 = std.math.maxInt(u32); /// A rid with no U-card login (a control artifact, or a manifest without one). const no_user: u32 = std.math.maxInt(u32); /// The columns, in a fixed order. Their directory entries (`(offset,len)` u32 /// pairs) follow the four scalar counts at the head of the image section. const Col = enum(u8) { /// `n_rids * 8` — event mtime per rid slot (0 when the rid has no event). mtime, /// `n_rids * 1` — bit0 has_event, bit1 is_leaf, bit2 leaf_closed. flags, /// `n_rids * 4` — active-branch name id per rid, or `no_branch`. branch_id, /// `(n_rids + 1) * 4` — CSR offsets into `hash_pool` per rid slot. hash_off, /// variable — concatenated artifact hashes, addressed by `hash_off`. hash_pool, /// `n_leaves * 4` — leaf rids in `leaf_table` iteration order (§7.1). leaf_rids, /// `(n_branch_names + 1) * 4` — CSR offsets into `branch_pool`. branch_off, /// variable — concatenated distinct branch-value bytes. branch_pool, /// `(n_syms + 1) * 4` — CSR offsets into `sym_pool`. sym_off, /// variable — concatenated bare symbolic names (§8.2, "sym-" stripped). sym_pool, /// `n_syms * 4` — the resolved rid per symbolic name (§8.2 max-mtime). sym_rid, /// `(n_rids + 1) * 4` — CSR offsets into the parent edge columns per rid. parent_off, /// `n_parent_edges * 4` — parent rid per edge, narrowed to the column index /// width the rid space is already asserted to fit. parent_rid, /// `n_parent_edges * 1` — the §3.2 primary flag per parent edge. Kept /// rather than inferred: the primary parent is selected by it, and merge /// edges are skipped by it, so an image without it answers ancestry /// questions wrongly rather than refusing them. parent_primary, /// `(n_rids + 1) * 4` — CSR offsets into the child edge columns per rid. /// Stored rather than transposed from the parent columns at load: the /// transpose would be an O(edges) allocation on every open, which is /// exactly the cost this image exists to avoid. child_off, /// `n_child_edges * 4` — child rid per edge. child_rid, /// `n_child_edges * 1` — the primary flag per child edge. child_primary, /// `(n_tag_names + 1) * 4` — CSR offsets into `tag_name_pool`. tag_name_off, /// variable — the distinct tag names, interned in first-seen order. tag_name_pool, /// `(n_rids + 1) * 4` — CSR offsets into `comment_pool` per rid slot. comment_off, /// variable — concatenated C-card comments, addressed by `comment_off`. comment_pool, /// `n_rids * 4` — interned login id per rid slot, or `no_user`. user_id, /// `(n_users + 1) * 4` — CSR offsets into `user_pool`. user_off, /// variable — concatenated distinct U-card logins. Interned rather than /// stored per rid: a repository has a handful of committers and hundreds /// of thousands of check-ins. user_pool, /// `(n_rids + 1) * 4` — CSR offsets into the per-rid tag entry columns. /// /// The whole §5 tag surface, stored RESOLVED and ACTIVE: the derive has /// already applied §5.1's cancel rule and §5.3's mtime precedence, so a /// cancelled tag is simply absent here and no reader re-judges precedence. /// The same trade `branch_id` makes with the §6.1 fallback — and the same /// one fossil makes, where `tagxref` holds one row per (rid, tag) with /// propagation flattened in by `tag_propagate` at write time so its readers /// are group-bys rather than precedence evaluations. rid_tag_off, /// `n_tag_entries * 4` — the tag-name id per entry. rid_tag_name, /// `n_tag_entries * 1` — bits 0-1 the §5.1 tagtype, bit 2 value-present. /// The presence bit is carried rather than inferred from a zero-length /// span: a tag may legitimately be active with an empty value, and that is /// a different fact from carrying none. rid_tag_flags, /// `(n_tag_entries + 1) * 4` — CSR offsets into `rid_tag_value_pool`. rid_tag_value_off, /// variable — the resolved tag values. rid_tag_value_pool, /// `(n_rids + 1) * 4` — CSR offsets into the per-rid Q-card entry columns. /// Most rids own an empty span; `info` reads its one rid's. pick_off, /// `n_picks * 1` — the card's sign (`artifact.QSign` tag value). pick_sign, /// `(n_picks + 1) * 4` — CSR offsets into `pick_target_pool`. pick_target_off, /// variable — the picked check-ins' hashes, concatenated. pick_target_pool, }; const col_count = @typeInfo(Col).@"enum".fields.len; /// Scalar counts (4 × u32) then the column directory (`col_count` × (u32,u32)). /// Everything after this header is column storage, offset-addressed from the /// image section's first byte. const header_len: usize = 4 * 4 + col_count * 8; /// A distinct index family per column so a slot minted for one column cannot, /// at compile time, address another (compact_arena's typed-index discipline). const RidSlot = enum(u32) { _ }; const LeafSlot = enum(u32) { _ }; const SymSlot = enum(u32) { _ }; const EdgeSlot = enum(u32) { _ }; const TagNameSlot = enum(u32) { _ }; const TagEntrySlot = enum(u32) { _ }; const PickSlot = enum(u32) { _ }; /// The §5.2 display overrides `info` and `timeline` render. Kept as a named /// set after the general tag layer landed, because these three are read by /// position in a fixed order and naming them here keeps that order in one /// place rather than spelled at each call site. pub const DisplayOverride = enum(u8) { comment, user, date }; pub const override_kinds: u32 = @typeInfo(DisplayOverride).@"enum".fields.len; pub const override_names = [override_kinds][]const u8{ "comment", "user", "date" }; /// One resolved, active tag on one rid. pub const TagRow = struct { name: []const u8, tagtype: u2, value: ?[]const u8, }; const tag_value_present_bit: u8 = 1 << 2; fn ridSlot(rid: Rid) RidSlot { std.debug.assert(rid >= 1); return @enumFromInt(@as(u32, @intCast(rid - 1))); } /// A fixed-width little-endian column keyed by its own index family `Ix`. Every /// `at` asserts the index against `len` before reading, so no access depends on /// a safety-check panic (idiom #3). `bytes` is a validated window: `Image.load` /// has already proven `bytes.len == len * @sizeOf(T)`. fn Column(comptime Ix: type, comptime T: type) type { return struct { bytes: []const u8, len: u32, const Self = @This(); const width = @sizeOf(T); fn at(self: Self, ix: Ix) T { const i: u32 = @intFromEnum(ix); std.debug.assert(i < self.len); const off = @as(usize, i) * width; return std.mem.readInt(T, self.bytes[off..][0..width], .little); } }; } /// A validated, offset-addressed view over an image section. Holds only /// `[]const u8` windows into the caller-owned cache buffer, plus one small /// owned `[]Rid` (the widened leaf list `leaves()` returns). `load` is the only /// constructor and never trusts its input; `deinit` frees the one allocation. pub const Image = struct { n_rids: u32, n_syms: u32, n_branch_names: u32, mtime: Column(RidSlot, u64), flags: Column(RidSlot, u8), branch_id: Column(RidSlot, u32), hash_off: Column(RidSlot, u32), // n_rids + 1 entries hash_pool: []const u8, branch_off: Column(SymSlot, u32), // reuse SymSlot family for name CSRs branch_pool: []const u8, sym_off: Column(SymSlot, u32), // n_syms + 1 entries sym_pool: []const u8, sym_rid: Column(SymSlot, u32), parent_off: Column(RidSlot, u32), // n_rids + 1 entries parent_rid: Column(EdgeSlot, u32), parent_primary: Column(EdgeSlot, u8), child_off: Column(RidSlot, u32), // n_rids + 1 entries child_rid: Column(EdgeSlot, u32), child_primary: Column(EdgeSlot, u8), tag_name_off: Column(TagNameSlot, u32), // n_tag_names + 1 tag_name_pool: []const u8, rid_tag_off: Column(RidSlot, u32), // n_rids + 1 rid_tag_name: Column(TagEntrySlot, u32), rid_tag_flags: Column(TagEntrySlot, u8), rid_tag_value_off: Column(TagEntrySlot, u32), // n_tag_entries + 1 rid_tag_value_pool: []const u8, n_tag_names: u32, /// Per-rid C-card comment and U-card login, so a listing renders without /// reading and parsing a manifest per row. `zit leaves` paid one such read /// per leaf — a second on sqlite's 472 — because the image did not carry /// these two columns and the accessors fell back. comment_off: Column(RidSlot, u32), comment_pool: []const u8, user_id: Column(RidSlot, u32), user_off: Column(SymSlot, u32), user_pool: []const u8, n_users: u32, /// Per-rid Q cards: sign and target per entry, addressed by a /// per-rid CSR — `info`'s provenance line without a manifest read. pick_off: Column(RidSlot, u32), pick_sign: Column(PickSlot, u8), pick_target_off: Column(PickSlot, u32), pick_target_pool: []const u8, n_picks: u32, /// Leaf rids widened to `Rid` in `leaf_table` order — the slice `leaves()` /// yields. Owned; freed by `deinit`. Bounded by the leaf count (dozens), /// so this one O(n_leaves) fill is negligible against a full derive. leaf_rids: []Rid, const has_event_bit: u8 = 1 << 0; const is_leaf_bit: u8 = 1 << 1; const leaf_closed_bit: u8 = 1 << 2; /// Parse and fully validate `image` (the cache's image section). Returns /// null on ANY structural violation — the caller then treats it as a MISS /// and derives. On success every query is guaranteed in-bounds. pub fn load(gpa: std.mem.Allocator, image: []const u8) error{OutOfMemory}!?Image { if (image.len < header_len) return null; const n_rids = std.mem.readInt(u32, image[0..4], .little); const n_leaves = std.mem.readInt(u32, image[4..8], .little); const n_syms = std.mem.readInt(u32, image[8..12], .little); const n_branch_names = std.mem.readInt(u32, image[12..16], .little); // Column windows, each validated to lie fully inside the image and to // match the length its counts imply (never trust a claimed span). var win: [col_count][]const u8 = undefined; for (0..col_count) |c| { const base = 16 + c * 8; const off = std.mem.readInt(u32, image[base..][0..4], .little); const len = std.mem.readInt(u32, image[base + 4 ..][0..4], .little); const end = std.math.add(usize, off, len) catch return null; if (off < header_len or end > image.len) return null; win[@intFromEnum(@as(Col, @enumFromInt(c)))] = image[off..end]; } // Expected fixed-width column lengths, overflow-guarded. const l_mtime = mul(n_rids, 8) orelse return null; const l_flags: usize = n_rids; const l_branch_id = mul(n_rids, 4) orelse return null; const l_hash_off = mul(add1(n_rids) orelse return null, 4) orelse return null; const l_leaf = mul(n_leaves, 4) orelse return null; const l_branch_off = mul(add1(n_branch_names) orelse return null, 4) orelse return null; const l_sym_off = mul(add1(n_syms) orelse return null, 4) orelse return null; const l_sym_rid = mul(n_syms, 4) orelse return null; if (win[@intFromEnum(Col.mtime)].len != l_mtime) return null; if (win[@intFromEnum(Col.flags)].len != l_flags) return null; if (win[@intFromEnum(Col.branch_id)].len != l_branch_id) return null; if (win[@intFromEnum(Col.hash_off)].len != l_hash_off) return null; if (win[@intFromEnum(Col.leaf_rids)].len != l_leaf) return null; if (win[@intFromEnum(Col.branch_off)].len != l_branch_off) return null; if (win[@intFromEnum(Col.sym_off)].len != l_sym_off) return null; if (win[@intFromEnum(Col.sym_rid)].len != l_sym_rid) return null; // Adjacency: the CSR offset columns are rid-keyed like `hash_off`, and // the two edge columns of a direction must agree on their edge count — // a rid column longer than its primary column would read a flag that // was never written. const l_adj_off = l_hash_off; // both are (n_rids + 1) * 4 if (win[@intFromEnum(Col.parent_off)].len != l_adj_off) return null; if (win[@intFromEnum(Col.child_off)].len != l_adj_off) return null; if (win[@intFromEnum(Col.parent_rid)].len % 4 != 0) return null; if (win[@intFromEnum(Col.child_rid)].len % 4 != 0) return null; const n_parent_edges: u32 = @intCast(win[@intFromEnum(Col.parent_rid)].len / 4); const n_child_edges: u32 = @intCast(win[@intFromEnum(Col.child_rid)].len / 4); if (win[@intFromEnum(Col.parent_primary)].len != n_parent_edges) return null; if (win[@intFromEnum(Col.child_primary)].len != n_child_edges) return null; if (win[@intFromEnum(Col.rid_tag_off)].len != l_hash_off) return null; // both (n_rids + 1) * 4 if (win[@intFromEnum(Col.rid_tag_name)].len % 4 != 0) return null; const n_tag_entries: u32 = @intCast(win[@intFromEnum(Col.rid_tag_name)].len / 4); if (win[@intFromEnum(Col.rid_tag_flags)].len != n_tag_entries) return null; const l_tag_value_off = mul(add1(n_tag_entries) orelse return null, 4) orelse return null; if (win[@intFromEnum(Col.rid_tag_value_off)].len != l_tag_value_off) return null; if (win[@intFromEnum(Col.tag_name_off)].len % 4 != 0) return null; if (win[@intFromEnum(Col.tag_name_off)].len < 4) return null; const n_tag_names: u32 = @intCast(win[@intFromEnum(Col.tag_name_off)].len / 4 - 1); // CSR span validation: offsets start at 0, are non-decreasing, and the // terminal offset equals the pool length. Proven before any span read. if (!validCsr(win[@intFromEnum(Col.hash_off)], add1(n_rids).?, win[@intFromEnum(Col.hash_pool)].len)) return null; if (!validCsr(win[@intFromEnum(Col.branch_off)], add1(n_branch_names).?, win[@intFromEnum(Col.branch_pool)].len)) return null; if (!validCsr(win[@intFromEnum(Col.sym_off)], add1(n_syms).?, win[@intFromEnum(Col.sym_pool)].len)) return null; // The adjacency CSRs address EDGE COUNTS rather than byte pools, so the // terminal offset is the edge count, not a length in bytes. if (!validCsr(win[@intFromEnum(Col.parent_off)], add1(n_rids).?, n_parent_edges)) return null; if (!validCsr(win[@intFromEnum(Col.child_off)], add1(n_rids).?, n_child_edges)) return null; if (!validCsr(win[@intFromEnum(Col.tag_name_off)], add1(n_tag_names).?, win[@intFromEnum(Col.tag_name_pool)].len)) return null; if (!validCsr(win[@intFromEnum(Col.rid_tag_off)], add1(n_rids).?, n_tag_entries)) return null; if (!validCsr(win[@intFromEnum(Col.rid_tag_value_off)], add1(n_tag_entries).?, win[@intFromEnum(Col.rid_tag_value_pool)].len)) return null; // Every entry must name a real tag name, proven before any query can // dereference one. { const nb = win[@intFromEnum(Col.rid_tag_name)]; var i: usize = 0; while (i < nb.len) : (i += 4) { if (std.mem.readInt(u32, nb[i..][0..4], .little) >= n_tag_names) return null; } } // Every stored rid must name a real slot; every branch id a real name. const leaf_bytes = win[@intFromEnum(Col.leaf_rids)]; const sym_rid_bytes = win[@intFromEnum(Col.sym_rid)]; for (0..n_leaves) |i| { const r = std.mem.readInt(u32, leaf_bytes[i * 4 ..][0..4], .little); if (r < 1 or r > n_rids) return null; } for (0..n_syms) |i| { const r = std.mem.readInt(u32, sym_rid_bytes[i * 4 ..][0..4], .little); if (r < 1 or r > n_rids) return null; } // Every edge endpoint must name a real slot, checked before any query // can dereference one. for ([2]Col{ .parent_rid, .child_rid }) |c| { const bytes = win[@intFromEnum(c)]; var i: usize = 0; while (i < bytes.len) : (i += 4) { const r = std.mem.readInt(u32, bytes[i..][0..4], .little); if (r < 1 or r > n_rids) return null; } } const branch_id_bytes = win[@intFromEnum(Col.branch_id)]; for (0..n_rids) |i| { const id = std.mem.readInt(u32, branch_id_bytes[i * 4 ..][0..4], .little); if (id != no_branch and id >= n_branch_names) return null; } // The login pool's entry count comes from its own CSR length rather // than a header scalar, so the four scalars (and `header_len`) stay // as they were. const user_off_bytes = win[@intFromEnum(Col.user_off)]; if (user_off_bytes.len < 4 or user_off_bytes.len % 4 != 0) return null; const n_users: u32 = @intCast(user_off_bytes.len / 4 - 1); if (win[@intFromEnum(Col.comment_off)].len != l_hash_off) return null; // (n_rids + 1) * 4 if (win[@intFromEnum(Col.user_id)].len != l_branch_id) return null; // n_rids * 4 // `validCsr` counts OFFSETS, not entries: a run of n has n + 1. if (!validCsr(win[@intFromEnum(Col.comment_off)], add1(n_rids) orelse return null, win[@intFromEnum(Col.comment_pool)].len)) return null; if (!validCsr(user_off_bytes, add1(n_users) orelse return null, win[@intFromEnum(Col.user_pool)].len)) return null; const user_id_bytes = win[@intFromEnum(Col.user_id)]; for (0..n_rids) |i| { const id = std.mem.readInt(u32, user_id_bytes[i * 4 ..][0..4], .little); if (id != no_user and id >= n_users) return null; } // Q cards: the entry count comes from the sign column's own // length, as the login count does from its CSR. const pick_sign_bytes = win[@intFromEnum(Col.pick_sign)]; const n_picks: u32 = std.math.cast(u32, pick_sign_bytes.len) orelse return null; if (win[@intFromEnum(Col.pick_off)].len != l_hash_off) return null; // (n_rids + 1) * 4 if (win[@intFromEnum(Col.pick_target_off)].len != mul(add1(n_picks) orelse return null, 4) orelse return null) return null; if (!validCsr(win[@intFromEnum(Col.pick_off)], add1(n_rids).?, n_picks)) return null; if (!validCsr(win[@intFromEnum(Col.pick_target_off)], add1(n_picks).?, win[@intFromEnum(Col.pick_target_pool)].len)) return null; for (pick_sign_bytes) |b| { if (b > 1) return null; } // Widen the leaf rids once (bounded by leaf count). This is the only // allocation the image owns. const leaf_rids = try gpa.alloc(Rid, n_leaves); for (0..n_leaves) |i| { leaf_rids[i] = std.mem.readInt(u32, leaf_bytes[i * 4 ..][0..4], .little); } return .{ .n_rids = n_rids, .n_syms = n_syms, .n_branch_names = n_branch_names, .mtime = .{ .bytes = win[@intFromEnum(Col.mtime)], .len = n_rids }, .flags = .{ .bytes = win[@intFromEnum(Col.flags)], .len = n_rids }, .branch_id = .{ .bytes = win[@intFromEnum(Col.branch_id)], .len = n_rids }, .hash_off = .{ .bytes = win[@intFromEnum(Col.hash_off)], .len = add1(n_rids).? }, .hash_pool = win[@intFromEnum(Col.hash_pool)], .branch_off = .{ .bytes = win[@intFromEnum(Col.branch_off)], .len = add1(n_branch_names).? }, .branch_pool = win[@intFromEnum(Col.branch_pool)], .sym_off = .{ .bytes = win[@intFromEnum(Col.sym_off)], .len = add1(n_syms).? }, .sym_pool = win[@intFromEnum(Col.sym_pool)], .sym_rid = .{ .bytes = win[@intFromEnum(Col.sym_rid)], .len = n_syms }, .parent_off = .{ .bytes = win[@intFromEnum(Col.parent_off)], .len = add1(n_rids).? }, .parent_rid = .{ .bytes = win[@intFromEnum(Col.parent_rid)], .len = n_parent_edges }, .parent_primary = .{ .bytes = win[@intFromEnum(Col.parent_primary)], .len = n_parent_edges }, .child_off = .{ .bytes = win[@intFromEnum(Col.child_off)], .len = add1(n_rids).? }, .child_rid = .{ .bytes = win[@intFromEnum(Col.child_rid)], .len = n_child_edges }, .child_primary = .{ .bytes = win[@intFromEnum(Col.child_primary)], .len = n_child_edges }, .tag_name_off = .{ .bytes = win[@intFromEnum(Col.tag_name_off)], .len = add1(n_tag_names).? }, .tag_name_pool = win[@intFromEnum(Col.tag_name_pool)], .rid_tag_off = .{ .bytes = win[@intFromEnum(Col.rid_tag_off)], .len = add1(n_rids).? }, .rid_tag_name = .{ .bytes = win[@intFromEnum(Col.rid_tag_name)], .len = n_tag_entries }, .rid_tag_flags = .{ .bytes = win[@intFromEnum(Col.rid_tag_flags)], .len = n_tag_entries }, .rid_tag_value_off = .{ .bytes = win[@intFromEnum(Col.rid_tag_value_off)], .len = add1(n_tag_entries).? }, .rid_tag_value_pool = win[@intFromEnum(Col.rid_tag_value_pool)], .comment_off = .{ .bytes = win[@intFromEnum(Col.comment_off)], .len = add1(n_rids).? }, .comment_pool = win[@intFromEnum(Col.comment_pool)], .user_id = .{ .bytes = win[@intFromEnum(Col.user_id)], .len = n_rids }, .user_off = .{ .bytes = user_off_bytes, .len = add1(n_users).? }, .user_pool = win[@intFromEnum(Col.user_pool)], .n_users = n_users, .pick_off = .{ .bytes = win[@intFromEnum(Col.pick_off)], .len = add1(n_rids).? }, .pick_sign = .{ .bytes = pick_sign_bytes, .len = n_picks }, .pick_target_off = .{ .bytes = win[@intFromEnum(Col.pick_target_off)], .len = add1(n_picks).? }, .pick_target_pool = win[@intFromEnum(Col.pick_target_pool)], .n_picks = n_picks, .n_tag_names = n_tag_names, .leaf_rids = leaf_rids, }; } /// One adjacency edge as the image stores it. pub const Edge = struct { rid: Rid, is_primary: bool }; /// Which adjacency relation to walk. pub const Dir = enum { parents, children }; /// A bounded walk over one rid's edges in one direction. Holds windows the /// caller already proved in-bounds at `load`, so `next` reads without /// re-validating; the span is fixed at construction and strictly advances. pub const EdgeIterator = struct { rids: Column(EdgeSlot, u32), primary: Column(EdgeSlot, u8), i: u32, end: u32, pub fn next(self: *EdgeIterator) ?Edge { if (self.i >= self.end) return null; const slot: EdgeSlot = @enumFromInt(self.i); self.i += 1; return .{ .rid = self.rids.at(slot), .is_primary = self.primary.at(slot) != 0 }; } }; /// `rid`'s edges in `dir`. An out-of-range rid yields an empty walk rather /// than refusing: the derived tables answer the same way for a rid with no /// linkage rows, and the two backings must not differ on that. pub fn edgesOf(self: *const Image, dir: Dir, rid: Rid) EdgeIterator { const off = switch (dir) { .parents => self.parent_off, .children => self.child_off, }; const rids = switch (dir) { .parents => self.parent_rid, .children => self.child_rid, }; const primary = switch (dir) { .parents => self.parent_primary, .children => self.child_primary, }; if (rid < 1 or rid > self.n_rids) return .{ .rids = rids, .primary = primary, .i = 0, .end = 0 }; const i: u32 = @intCast(rid - 1); const start = off.at(@enumFromInt(i)); const end = off.at(@enumFromInt(i + 1)); std.debug.assert(start <= end); // validCsr proved non-decreasing at load return .{ .rids = rids, .primary = primary, .i = start, .end = end }; } fn tagNameAt(self: *const Image, id: u32) []const u8 { std.debug.assert(id < self.n_tag_names); const lo = self.tag_name_off.at(@enumFromInt(id)); const hi = self.tag_name_off.at(@enumFromInt(id + 1)); std.debug.assert(lo <= hi and hi <= self.tag_name_pool.len); return self.tag_name_pool[lo..hi]; } /// A bounded walk over one rid's resolved, active tags. pub const TagIterator = struct { img: *const Image, i: u32, end: u32, pub fn next(self: *TagIterator) ?TagRow { if (self.i >= self.end) return null; const slot: TagEntrySlot = @enumFromInt(self.i); self.i += 1; const flags = self.img.rid_tag_flags.at(slot); const vlo = self.img.rid_tag_value_off.at(@enumFromInt(@intFromEnum(slot))); const vhi = self.img.rid_tag_value_off.at(@enumFromInt(@intFromEnum(slot) + 1)); std.debug.assert(vlo <= vhi and vhi <= self.img.rid_tag_value_pool.len); return .{ .name = self.img.tagNameAt(self.img.rid_tag_name.at(slot)), .tagtype = @intCast(flags & 0b11), .value = if (flags & tag_value_present_bit != 0) self.img.rid_tag_value_pool[vlo..vhi] else null, }; } }; /// `rid`'s active tags. An unknown rid walks empty, matching what the /// derived table answers for a rid carrying no rows. pub fn tagsOf(self: *const Image, rid: Rid) TagIterator { if (rid < 1 or rid > self.n_rids) return .{ .img = self, .i = 0, .end = 0 }; const i: u32 = @intCast(rid - 1); const lo = self.rid_tag_off.at(@enumFromInt(i)); const hi = self.rid_tag_off.at(@enumFromInt(i + 1)); std.debug.assert(lo <= hi); return .{ .img = self, .i = lo, .end = hi }; } /// The resolved value of the active tag `name` on `rid`, or null when it /// carries none. Null value with the tag present is distinguishable: the /// caller gets the row's own optional. pub fn activeTagValue(self: *const Image, rid: Rid, name: []const u8) ?TagRow { var it = self.tagsOf(rid); while (it.next()) |row| { if (std.mem.eql(u8, row.name, name)) return row; } return null; } pub fn deinit(self: *Image, gpa: std.mem.Allocator) void { gpa.free(self.leaf_rids); self.* = undefined; } /// The number of interned rids (dense `1..=count`). pub fn count(self: *const Image) usize { return self.n_rids; } /// Whether `rid` carries an event row (§4.2 step 5): the image mirror of /// `events.contains`. pub fn hasEvent(self: *const Image, rid: Rid) bool { if (rid < 1 or rid > self.n_rids) return false; return self.flags.at(ridSlot(rid)) & has_event_bit != 0; } /// The event mtime of `rid`, or null when it has no event (§7.5/§8.3). pub fn mtimeOf(self: *const Image, rid: Rid) ?Mtime { if (!self.hasEvent(rid)) return null; return self.mtime.at(ridSlot(rid)); } /// Leaf-table membership (§7.1). pub fn isLeaf(self: *const Image, rid: Rid) bool { if (rid < 1 or rid > self.n_rids) return false; return self.flags.at(ridSlot(rid)) & is_leaf_bit != 0; } /// Open-leaf predicate (§7.4): a leaf with no active closed tag. pub fn isOpenLeaf(self: *const Image, rid: Rid) bool { if (!self.isLeaf(rid)) return false; return self.flags.at(ridSlot(rid)) & leaf_closed_bit == 0; } /// The leaf rids in `leaf_table` order (§7.1) — the slice `leaves()` yields. pub fn leafRids(self: *const Image) []const Rid { return self.leaf_rids; } /// The active-branch value of `rid` (§6.1), or `main_branch` when the rid /// carries no active branch tag (§6.4 fallback). Precondition (mirrors the /// derived `branchOf`): `rid` bears an event. pub fn branchOf(self: *const Image, rid: Rid, main_branch: []const u8) []const u8 { std.debug.assert(main_branch.len != 0); std.debug.assert(self.hasEvent(rid)); const id = self.branch_id.at(ridSlot(rid)); if (id == no_branch) return main_branch; return self.nameSpan(self.branch_off, self.branch_pool, id); } /// The interned hash of `rid` (its lowercase-hex name). pub fn hashOf(self: *const Image, rid: Rid) []const u8 { std.debug.assert(rid >= 1 and rid <= self.n_rids); const slot = ridSlot(rid); const lo = self.hash_off.at(slot); const hi = self.hash_off.at(@enumFromInt(@intFromEnum(slot) + 1)); std.debug.assert(lo <= hi and hi <= self.hash_pool.len); return self.hash_pool[lo..hi]; } /// `rid`'s C-card comment ("" when it has none), and its U-card login /// ("" likewise) — the two columns a listing needs per row. pub fn commentOf(self: *const Image, rid: Rid) ?[]const u8 { std.debug.assert(rid >= 1 and rid <= self.n_rids); // Both columns are written exactly where `crosslink` filled the // derived maps — i.e. for a rid that gained an event. A control // artifact has neither, and the two backings must agree that the // answer is "unknown", not "empty". if (!self.hasEvent(rid)) return null; const slot = ridSlot(rid); const lo = self.comment_off.at(slot); const hi = self.comment_off.at(@enumFromInt(@intFromEnum(slot) + 1)); std.debug.assert(lo <= hi and hi <= self.comment_pool.len); return self.comment_pool[lo..hi]; } pub fn userOf(self: *const Image, rid: Rid) ?[]const u8 { std.debug.assert(rid >= 1 and rid <= self.n_rids); if (!self.hasEvent(rid)) return null; const id = self.user_id.at(ridSlot(rid)); if (id == no_user) return ""; std.debug.assert(id < self.n_users); const lo = self.user_off.at(@enumFromInt(id)); const hi = self.user_off.at(@enumFromInt(id + 1)); std.debug.assert(lo <= hi and hi <= self.user_pool.len); return self.user_pool[lo..hi]; } /// How many Q cards `rid` carries; 0 for every rid without one. pub fn pickCount(self: *const Image, rid: Rid) u32 { std.debug.assert(rid >= 1 and rid <= self.n_rids); const slot = ridSlot(rid); const lo = self.pick_off.at(slot); const hi = self.pick_off.at(@enumFromInt(@intFromEnum(slot) + 1)); std.debug.assert(lo <= hi and hi <= self.n_picks); return hi - lo; } /// `rid`'s `i`th Q card in manifest order; `i < pickCount(rid)`. pub fn pickAt(self: *const Image, rid: Rid, i: u32) repostate.Pick { std.debug.assert(i < self.pickCount(rid)); const slot: PickSlot = @enumFromInt(self.pick_off.at(ridSlot(rid)) + i); const lo = self.pick_target_off.at(slot); const hi = self.pick_target_off.at(@enumFromInt(@intFromEnum(slot) + 1)); std.debug.assert(lo <= hi and hi <= self.pick_target_pool.len); return .{ .sign = @enumFromInt(self.pick_sign.at(slot)), .target = self.pick_target_pool[lo..hi], }; } /// The rid whose hash equals `hash`, or null (the image mirror of /// `store.lookup`). A linear scan bounded by `n_rids`; the sole caller is /// the current-checkout mark, one lookup per read. pub fn lookup(self: *const Image, hash: []const u8) ?Rid { var rid: Rid = 1; while (rid <= self.n_rids) : (rid += 1) { if (std.mem.eql(u8, self.hashOf(rid), hash)) return rid; } return null; } /// Symbolic-name resolution (§8.2): the memoised max-mtime rid for `name`, /// or null when no live symbolic tag names it. A linear scan bounded by /// `n_syms` (branch/tag count, not artifact count). pub fn resolveName(self: *const Image, name: []const u8) ?Rid { var i: u32 = 0; while (i < self.n_syms) : (i += 1) { if (std.mem.eql(u8, self.nameSpan(self.sym_off, self.sym_pool, i), name)) { return self.sym_rid.at(@enumFromInt(i)); } } return null; } fn nameSpan(self: *const Image, off: Column(SymSlot, u32), pool: []const u8, i: u32) []const u8 { _ = self; const lo = off.at(@enumFromInt(i)); const hi = off.at(@enumFromInt(i + 1)); std.debug.assert(lo <= hi and hi <= pool.len); return pool[lo..hi]; } }; fn mul(a: u32, b: usize) ?usize { return std.math.mul(usize, a, b) catch null; } fn add1(a: u32) ?u32 { return std.math.add(u32, a, 1) catch null; } /// A CSR offset column of `n` u32 entries is valid when it starts at 0, is /// non-decreasing, and its terminal entry equals the pool length. fn validCsr(off_bytes: []const u8, n: u32, pool_len: usize) bool { std.debug.assert(off_bytes.len == @as(usize, n) * 4); if (n == 0) return false; // always at least the terminal 0 for an empty pool var prev: u32 = std.mem.readInt(u32, off_bytes[0..4], .little); if (prev != 0) return false; var i: u32 = 1; while (i < n) : (i += 1) { const cur = std.mem.readInt(u32, off_bytes[i * 4 ..][0..4], .little); if (cur < prev) return false; prev = cur; } return prev == pool_len; } /// Materialize the hot query answers of a fully-derived `RepoState` into the /// image section bytes, appended to `out`. Reads `rs` through its PUBLIC /// surface only (the store, `mtimeOf`, `isLeaf`, `isOpenLeaf`, `branchOf`, /// `leaves`, `resolvedSymbols`), so the representation stays owned here. The /// materialized branch value is the final `branchOf` answer under this repo's /// `main_branch`, so the fallback is already baked in (§6.1/§6.4). pub fn serialize( gpa: std.mem.Allocator, rs: *const repostate.RepoState, main_branch: []const u8, out: *std.ArrayList(u8), ) error{OutOfMemory}!void { std.debug.assert(main_branch.len != 0); const n_usize = rs.store.count(); std.debug.assert(n_usize <= std.math.maxInt(u32)); // TigerStyle: rid space fits the column index const n_rids: u32 = @intCast(n_usize); var cols: [col_count]std.ArrayList(u8) = undefined; for (&cols) |*c| c.* = .empty; defer for (&cols) |*c| c.deinit(gpa); // Branch-value interning: distinct active branch strings, first-seen order. var branch_ids: std.StringHashMapUnmanaged(u32) = .empty; defer branch_ids.deinit(gpa); var n_branch_names: u32 = 0; // Logins interned the way branch values are: a repository has a handful of // committers and hundreds of thousands of check-ins. var user_ids: std.StringHashMapUnmanaged(u32) = .empty; defer user_ids.deinit(gpa); var n_users: u32 = 0; // hash_off / branch_id / flags / mtime, one pass over the dense rid space. try appendInt(gpa, &cols[@intFromEnum(Col.hash_off)], u32, 0); try appendInt(gpa, &cols[@intFromEnum(Col.comment_off)], u32, 0); try appendInt(gpa, &cols[@intFromEnum(Col.user_off)], u32, 0); var rid: Rid = 1; while (rid <= n_rids) : (rid += 1) { const has_event = rs.mtimeOf(rid) != null; const is_leaf = rs.isLeaf(rid); var f: u8 = 0; if (has_event) f |= Image.has_event_bit; if (is_leaf) f |= Image.is_leaf_bit; if (is_leaf and !rs.isOpenLeaf(rid)) f |= Image.leaf_closed_bit; try cols[@intFromEnum(Col.flags)].append(gpa, f); try appendInt(gpa, &cols[@intFromEnum(Col.mtime)], u64, if (has_event) rs.mtimeOf(rid).? else 0); const comment = rs.commentOf(rid) orelse ""; try cols[@intFromEnum(Col.comment_pool)].appendSlice(gpa, comment); try appendInt(gpa, &cols[@intFromEnum(Col.comment_off)], u32, @intCast(cols[@intFromEnum(Col.comment_pool)].items.len)); var uid: u32 = no_user; if (rs.userOf(rid)) |login| { const ugop = try user_ids.getOrPut(gpa, login); if (!ugop.found_existing) { ugop.value_ptr.* = n_users; ugop.key_ptr.* = login; // borrows rs's owned dupe for this call try cols[@intFromEnum(Col.user_pool)].appendSlice(gpa, login); try appendInt(gpa, &cols[@intFromEnum(Col.user_off)], u32, @intCast(cols[@intFromEnum(Col.user_pool)].items.len)); n_users += 1; } uid = ugop.value_ptr.*; } try appendInt(gpa, &cols[@intFromEnum(Col.user_id)], u32, uid); var bid: u32 = no_branch; if (has_event) { const value = rs.branchOf(rid, main_branch); const gop = try branch_ids.getOrPut(gpa, value); if (!gop.found_existing) { gop.value_ptr.* = n_branch_names; gop.key_ptr.* = value; // borrows rs's tagxref bytes for this call's duration try appendInt(gpa, &cols[@intFromEnum(Col.branch_off)], u32, @intCast(cols[@intFromEnum(Col.branch_pool)].items.len)); try cols[@intFromEnum(Col.branch_pool)].appendSlice(gpa, value); n_branch_names += 1; } bid = gop.value_ptr.*; } try appendInt(gpa, &cols[@intFromEnum(Col.branch_id)], u32, bid); const hash = rs.store.hashOf(rid); try cols[@intFromEnum(Col.hash_pool)].appendSlice(gpa, hash); try appendInt(gpa, &cols[@intFromEnum(Col.hash_off)], u32, @intCast(cols[@intFromEnum(Col.hash_pool)].items.len)); } // Terminal branch_off (CSR closes at the pool length). try appendInt(gpa, &cols[@intFromEnum(Col.branch_off)], u32, @intCast(cols[@intFromEnum(Col.branch_pool)].items.len)); // The §5 tag surface, RESOLVED and ACTIVE. `tagsOf` is the derive's own // answer -- cancel already filtered, precedence already applied -- so this // stores what a reader needs and never the inputs it would have to judge. { var tag_ids: std.StringHashMapUnmanaged(u32) = .empty; defer tag_ids.deinit(gpa); var n_tag_names: u32 = 0; var entries: u32 = 0; try appendInt(gpa, &cols[@intFromEnum(Col.tag_name_off)], u32, 0); try appendInt(gpa, &cols[@intFromEnum(Col.rid_tag_off)], u32, 0); try appendInt(gpa, &cols[@intFromEnum(Col.rid_tag_value_off)], u32, 0); var r: Rid = 1; while (r <= n_rids) : (r += 1) { const rows = try rs.tagsOf(gpa, r); defer gpa.free(rows); for (rows) |row| { const gop = try tag_ids.getOrPut(gpa, row.name); if (!gop.found_existing) { gop.value_ptr.* = n_tag_names; gop.key_ptr.* = row.name; // borrows rs's tag-name bytes for this call try cols[@intFromEnum(Col.tag_name_pool)].appendSlice(gpa, row.name); try appendInt(gpa, &cols[@intFromEnum(Col.tag_name_off)], u32, @intCast(cols[@intFromEnum(Col.tag_name_pool)].items.len)); n_tag_names += 1; } try appendInt(gpa, &cols[@intFromEnum(Col.rid_tag_name)], u32, gop.value_ptr.*); var flags: u8 = @intFromEnum(row.tagtype); if (row.value) |v| { flags |= tag_value_present_bit; try cols[@intFromEnum(Col.rid_tag_value_pool)].appendSlice(gpa, v); } try cols[@intFromEnum(Col.rid_tag_flags)].append(gpa, flags); try appendInt(gpa, &cols[@intFromEnum(Col.rid_tag_value_off)], u32, @intCast(cols[@intFromEnum(Col.rid_tag_value_pool)].items.len)); entries += 1; } try appendInt(gpa, &cols[@intFromEnum(Col.rid_tag_off)], u32, entries); } } // Q cards, per rid in manifest order, through `picksOf` — the // same door `info` reads. { var n_picks: u32 = 0; try appendInt(gpa, &cols[@intFromEnum(Col.pick_off)], u32, 0); try appendInt(gpa, &cols[@intFromEnum(Col.pick_target_off)], u32, 0); var r: Rid = 1; while (r <= n_rids) : (r += 1) { const picks = try rs.picksOf(gpa, r); defer gpa.free(picks); for (picks) |pk| { try cols[@intFromEnum(Col.pick_sign)].append(gpa, @intFromEnum(pk.sign)); try cols[@intFromEnum(Col.pick_target_pool)].appendSlice(gpa, pk.target); try appendInt(gpa, &cols[@intFromEnum(Col.pick_target_off)], u32, @intCast(cols[@intFromEnum(Col.pick_target_pool)].items.len)); n_picks += 1; } try appendInt(gpa, &cols[@intFromEnum(Col.pick_off)], u32, n_picks); } } // Adjacency, both directions, read through the same `edgesOf` door every // query uses — so the image cannot disagree with the derive about what an // edge set contains. Written as a CSR whose terminal offset is the EDGE // COUNT (the other CSRs here close at a byte-pool length). { const dirs = [2]struct { dir: repostate.RepoState.EdgeDir, off: Col, rids: Col, prim: Col }{ .{ .dir = .parents, .off = .parent_off, .rids = .parent_rid, .prim = .parent_primary }, .{ .dir = .children, .off = .child_off, .rids = .child_rid, .prim = .child_primary }, }; for (dirs) |d| { var edges: u32 = 0; try appendInt(gpa, &cols[@intFromEnum(d.off)], u32, 0); var r: Rid = 1; while (r <= n_rids) : (r += 1) { var it2 = rs.edgesOf(d.dir, r); while (it2.next()) |e| { std.debug.assert(e.rid >= 1 and e.rid <= n_rids); try appendInt(gpa, &cols[@intFromEnum(d.rids)], u32, @intCast(e.rid)); try cols[@intFromEnum(d.prim)].append(gpa, if (e.is_primary) 1 else 0); edges += 1; } try appendInt(gpa, &cols[@intFromEnum(d.off)], u32, edges); } } } // leaf_rids in leaf-table iteration order (§7.1). var it = rs.leaves(); while (it.next()) |lr| { std.debug.assert(lr >= 1 and lr <= n_rids); try appendInt(gpa, &cols[@intFromEnum(Col.leaf_rids)], u32, @intCast(lr)); } // sym table (§8.2): the memoised max-mtime rid per live symbolic name. const syms = try rs.resolvedSymbols(gpa); defer gpa.free(syms); var n_syms: u32 = 0; try appendInt(gpa, &cols[@intFromEnum(Col.sym_off)], u32, 0); for (syms) |s| { std.debug.assert(s.rid >= 1 and s.rid <= n_rids); try cols[@intFromEnum(Col.sym_pool)].appendSlice(gpa, s.name); try appendInt(gpa, &cols[@intFromEnum(Col.sym_off)], u32, @intCast(cols[@intFromEnum(Col.sym_pool)].items.len)); try appendInt(gpa, &cols[@intFromEnum(Col.sym_rid)], u32, @intCast(s.rid)); n_syms += 1; } // Assemble: counts, directory (offsets relative to the image start), columns. try appendInt(gpa, out, u32, n_rids); try appendInt(gpa, out, u32, @intCast(cols[@intFromEnum(Col.leaf_rids)].items.len / 4)); try appendInt(gpa, out, u32, n_syms); try appendInt(gpa, out, u32, n_branch_names); var running: u32 = @intCast(header_len); for (cols) |c| { try appendInt(gpa, out, u32, running); try appendInt(gpa, out, u32, @intCast(c.items.len)); running = std.math.add(u32, running, @intCast(c.items.len)) catch return error.OutOfMemory; } for (cols) |c| try out.appendSlice(gpa, c.items); } fn appendInt(gpa: std.mem.Allocator, s: *std.ArrayList(u8), comptime T: type, v: T) error{OutOfMemory}!void { var buf: [@sizeOf(T)]u8 = undefined; std.mem.writeInt(T, &buf, v, .little); try s.appendSlice(gpa, &buf); } // =========================================================================== // Tests. The oracle is a fully-derived `RepoState`: an image loaded from its // serialization must answer every query IDENTICALLY (the query-equivalence // invariant). Expected values come from the state the RFC-derived `crosslink` // produces — never fossil. §7.1 leaf table, §7.4 open predicate, §7.5/§8.3 // event times, §6.1 branch-of, §8.2 name resolution. // =========================================================================== const testing = std.testing; fn h(comptime c: u8) []const u8 { return &[_]u8{c} ** 40; // a 40-byte stand-in hash; identity is all the store needs } /// Build a small derived state exercising every column: two branches, an open /// trunk leaf, a closed feature leaf, a phantom (eventless) parent, and /// symbolic tags on trunk and feature. fn seedState(rs: *repostate.RepoState) !void { // c1 root on trunk (§6.1 branch value "trunk"); tagged sym-trunk (§8.2). _ = try rs.crosslink(.{ .hash = h('a'), .mtime = 100, .tags = &.{ .{ .type = .propagate, .name = "branch", .target = null, .value = "trunk" }, .{ .type = .propagate, .name = "sym-trunk", .target = null, .value = null }, } }); // c2 child of c1, still trunk, newer — makes c1 a non-leaf, c2 the trunk leaf. _ = try rs.crosslink(.{ .hash = h('b'), .mtime = 200, .parents = &.{h('a')}, .tags = &.{ .{ .type = .propagate, .name = "branch", .target = null, .value = "trunk" }, .{ .type = .propagate, .name = "sym-trunk", .target = null, .value = null }, } }); // c3 child of c1 on branch "feature", closed (§7.4) — a closed leaf. _ = try rs.crosslink(.{ .hash = h('c'), .mtime = 150, .parents = &.{h('a')}, .tags = &.{ .{ .type = .propagate, .name = "branch", .target = null, .value = "feature" }, .{ .type = .propagate, .name = "sym-feature", .target = null, .value = null }, .{ .type = .singleton, .name = "closed", .target = null, .value = null }, } }); // c5 child of a never-crosslinked phantom parent "z" — a leaf with an // eventless rid ("z") in the intern space (branch_id == no_branch). _ = try rs.crosslink(.{ .hash = h('e'), .mtime = 250, .parents = &.{h('z')}, .tags = &.{ .{ .type = .propagate, .name = "branch", .target = null, .value = "trunk" }, } }); // c6 child of c2 cherry-picking c3 and backing out c1: two Q // cards on one rid, no edge to either target. _ = try rs.crosslink(.{ .hash = h('f'), .mtime = 300, .parents = &.{h('b')}, .tags = &.{ .{ .type = .propagate, .name = "branch", .target = null, .value = "trunk" }, }, .picks = &.{ .{ .sign = .cherrypick, .target = h('c') }, .{ .sign = .backout, .target = h('a') }, } }); } fn expectImageEqualsDerived(gpa: std.mem.Allocator, rs: *repostate.RepoState, main_branch: []const u8) !void { var body: std.ArrayList(u8) = .empty; defer body.deinit(gpa); try serialize(gpa, rs, main_branch, &body); var img = (try Image.load(gpa, body.items)) orelse return error.TestUnexpectedResult; defer img.deinit(gpa); const n = rs.store.count(); try testing.expectEqual(n, img.count()); // §7.5/§8.3 mtimeOf, §7.1 isLeaf, §7.4 isOpenLeaf, §6.1 branchOf, hashOf — // for every rid in the dense space. var rid: Rid = 1; while (rid <= n) : (rid += 1) { try testing.expectEqual(rs.mtimeOf(rid), img.mtimeOf(rid)); try testing.expectEqual(rs.isLeaf(rid), img.isLeaf(rid)); try testing.expectEqual(rs.isOpenLeaf(rid), img.isOpenLeaf(rid)); try testing.expectEqualStrings(rs.store.hashOf(rid), img.hashOf(rid)); try testing.expectEqual(rid, img.lookup(rs.store.hashOf(rid)).?); if (rs.mtimeOf(rid) != null) { try testing.expectEqualStrings(rs.branchOf(rid, main_branch), img.branchOf(rid, main_branch)); } // Q cards: same count, same order, same sign and target. const picks = try rs.picksOf(gpa, rid); defer gpa.free(picks); try testing.expectEqual(@as(u32, @intCast(picks.len)), img.pickCount(rid)); for (picks, 0..) |pk, i| { const got = img.pickAt(rid, @intCast(i)); try testing.expectEqual(pk.sign, got.sign); try testing.expectEqualStrings(pk.target, got.target); } } // §7.1 leaf set AND iteration order are byte-identical. var di = rs.leaves(); const image_leaves = img.leafRids(); var k: usize = 0; while (di.next()) |lr| : (k += 1) { try testing.expect(k < image_leaves.len); try testing.expectEqual(lr, image_leaves[k]); } try testing.expectEqual(k, image_leaves.len); // §8.2 name resolution: every live symbolic name resolves identically, and // an unknown name is null in both. const syms = try rs.resolvedSymbols(gpa); defer gpa.free(syms); for (syms) |s| { try testing.expectEqual(rs.resolveName(s.name) catch null, img.resolveName(s.name)); try testing.expect(img.resolveName(s.name).? == s.rid); } try testing.expectEqual(@as(?Rid, null), img.resolveName("no-such-branch-xyz")); } test "repoimage §7.1/§7.4/§7.5/§6.1/§8.2: image load is query-equivalent to a from-scratch derive" { const gpa = testing.allocator; var store = repostate.MemStore.init(gpa); defer store.deinit(); var rs = repostate.RepoState.init(gpa, store.store()); defer rs.deinit(); try seedState(&rs); try expectImageEqualsDerived(gpa, &rs, "trunk"); } test "repoimage §7.1: an empty repository serializes and reloads to an empty image" { const gpa = testing.allocator; var store = repostate.MemStore.init(gpa); defer store.deinit(); var rs = repostate.RepoState.init(gpa, store.store()); defer rs.deinit(); try expectImageEqualsDerived(gpa, &rs, "trunk"); } test "repoimage: garbage / truncated bytes are a MISS (load null), never a crash or wrong answer" { const gpa = testing.allocator; // A valid image to truncate and mangle. var store = repostate.MemStore.init(gpa); defer store.deinit(); var rs = repostate.RepoState.init(gpa, store.store()); defer rs.deinit(); try seedState(&rs); var body: std.ArrayList(u8) = .empty; defer body.deinit(gpa); try serialize(gpa, &rs, "trunk", &body); // Every truncation of a valid image is rejected (a short read can never // pass span validation) — and never crashes. for (0..body.items.len) |cut| { try testing.expect((try Image.load(gpa, body.items[0..cut])) == null); } // Seeded random blobs: load must not crash; a non-null image must answer // every query in-bounds (the validation guarantees it). var prng = std.Random.DefaultPrng.init(0xC0FFEE); const rnd = prng.random(); var iter: usize = 0; while (iter < 4000) : (iter += 1) { const len = rnd.intRangeAtMost(usize, 0, 512); const blob = try gpa.alloc(u8, len); defer gpa.free(blob); rnd.bytes(blob); if (try Image.load(gpa, blob)) |*loaded| { var img = loaded.*; defer img.deinit(gpa); var r: Rid = 1; const cnt = img.count(); while (r <= cnt and r <= 4096) : (r += 1) { _ = img.mtimeOf(r); _ = img.isOpenLeaf(r); _ = img.hashOf(r); if (img.hasEvent(r)) _ = img.branchOf(r, "trunk"); } _ = img.leafRids(); _ = img.resolveName("x"); _ = img.lookup("y"); } } } test "repoimage: a bit-flipped rid or CSR offset is rejected by span validation" { const gpa = testing.allocator; var store = repostate.MemStore.init(gpa); defer store.deinit(); var rs = repostate.RepoState.init(gpa, store.store()); defer rs.deinit(); try seedState(&rs); var body: std.ArrayList(u8) = .empty; defer body.deinit(gpa); try serialize(gpa, &rs, "trunk", &body); // Corrupt the first leaf rid to an out-of-range value: validation rejects. var mangled = try gpa.dupe(u8, body.items); defer gpa.free(mangled); const leaf_dir_base = 16 + @intFromEnum(Col.leaf_rids) * 8; const leaf_off = std.mem.readInt(u32, mangled[leaf_dir_base..][0..4], .little); std.mem.writeInt(u32, mangled[leaf_off..][0..4], 0xFFFF_FFFF, .little); try testing.expect((try Image.load(gpa, mangled)) == null); }