//! 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);
/// 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,
};
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) { _ };
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),
/// 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;
// 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;
// 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;
}
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;
}
// 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 },
.leaf_rids = leaf_rids,
};
}
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];
}
/// 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;
// hash_off / branch_id / flags / mtime, one pass over the dense rid space.
try appendInt(gpa, &cols[@intFromEnum(Col.hash_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);
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));
// 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" },
} });
}
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));
}
}
// §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);
}