//! 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 * 8` — the row's §5.3 mtime: the time of the artifact
/// that applied it, carried down by propagation. A reader that replays new
/// tags against stored ones (the push rule's branch check) needs it to
/// judge precedence exactly as the derive would.
rid_tag_mtime,
/// `(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,
mtime: Mtime,
};
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_mtime: Column(TagEntrySlot, u64),
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;
if (win[@intFromEnum(Col.rid_tag_mtime)].len != (mul(n_tag_entries, 8) orelse return null)) 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_mtime = .{ .bytes = win[@intFromEnum(Col.rid_tag_mtime)], .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,
.mtime = self.img.rid_tag_mtime.at(slot),
};
}
};
/// `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_mtime)], u64, row.mtime);
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);
}