Skip to content
zit Artifact [4c0e928b2c]
Login

Artifact [4c0e928b2c]

Check-ins Using Download Hex

Artifact 4c0e928b2cf46c1378cee8650757c07c42fa3060a2ee2d1202296c13c9171783:

//! zit — the persisted derivation cache (a library-internal `zit` module used
//! by `Repository`; reached only through that facade, not re-exported).
//!
//! A `.zit-cache` sidecar beside `.zit` is a pure MEMO of the derived repo-view:
//! repo-state §1 pins derived state as a function of the immutable log, §7.1
//! blesses precomputing the leaf table, and §7.3 keeps full rebuild as the
//! fallback — this file stores the crosslink INPUT records (in persisted order)
//! at a named log prefix so a read-only verb replays them (`RepoView`-side)
//! instead of re-reading and re-CRC'ing the whole log. Deleting the file must
//! never change any answer: it is disposable by construction.
//!
//! The cache is keyed on the append-only log's identity (`logstore.LogKey`:
//! end offset, frame count, last-frame header CRC). A key match serves the
//! cache; any mismatch, a wrong magic/version, or a failed self-checksum is a
//! MISS — the caller rebuilds from the log and rewrites the cache atomically.
//! A stale, truncated, or corrupt cache is therefore never trusted.
//!
//! This module is a dumb container: it validates magic/version/key/checksum and
//! hands the opaque record body to `RepoView`, which alone knows the record
//! format. All effects go through the injected `std.Io` seam (design-seams rule).

const std = @import("std");
const repoview = @import("repoview.zig");
const logstore = @import("logstore.zig");
const storage = @import("storage.zig");
const crc32 = @import("crc32.zig");

/// The advisory tier's one root name, beside `.zit` in the checkout root:
/// a DIRECTORY holding every disposable, regenerable derivation. Members
/// today: `repo` (this module's derived-state cache) and `vstat` (update's
/// materialization plan sidecar); the tree-checkpoint design reserves its
/// member here too. Fossil-ignored and never committed.
pub const cache_dirname: []const u8 = ".zit-cache";
/// This module's member inside `cache_dirname`. The PAYLOAD is byte-identical
/// to what the pre-directory code wrote at the root name -- only the location
/// moved, which is the whole migration story.
pub const cache_member: []const u8 = "repo";
pub const cache_filename: []const u8 = cache_dirname ++ "/" ++ cache_member;

/// One release of tolerance for the pre-directory layout, where
/// `cache_dirname` IS the cache file. Reads fall back to it; the first cache
/// WRITE migrates it wholesale -- rename to a scratch name, make the
/// directory, rename inside -- so the derivation survives without a byte
/// copied or a re-derive paid. Returns whether the path is now writable as a
/// directory member.
pub fn ensureCacheDir(io: std.Io, dir: std.Io.Dir) bool {
    const st = dir.statFile(io, cache_dirname, .{ .follow_symlinks = false }) catch |err| switch (err) {
        error.FileNotFound => {
            dir.createDir(io, cache_dirname, .default_dir) catch return false;
            return true;
        },
        else => return false,
    };
    switch (st.kind) {
        .directory => return true,
        .file => {
            // The scratch prefix, so a crash mid-migration strands a name the
            // sweep tier already owns.
            dir.rename(cache_dirname, dir, ".zit-tmp-cache-migrate", io) catch return false;
            dir.createDir(io, cache_dirname, .default_dir) catch return false;
            dir.rename(".zit-tmp-cache-migrate", dir, cache_filename, io) catch return false;
            return true;
        },
        else => return false,
    }
}

/// File magic; distinguishes a `.zit-cache` from any other file that lands at
/// the name. Eight bytes so the fixed header stays 8-aligned.
const magic = "ZITCACHE";

/// On-disk format version. Any mismatch is a MISS: the cache is disposable, so
/// the tables it serializes stay free to evolve without a migration path.
// Bumped to 2 when the shun fingerprint joined the header: extension across a
// shun change is unsound (the body may carry a record the mask must now hide),
// so the fingerprint is part of the cache's identity. An old cache simply
// misses once and is rebuilt.
const format_version: u16 = 2;

/// Materialized-image column schema version. Guards the appended image section
/// independently of the record body: a bump makes a warm `.fast_read` fall back
/// to deriving from the still-valid record body (never a wrong answer, never a
/// migration). A cache written by an older build (or with no image) carries
/// `image_len == 0`, so `.fast_read` degrades to a derive there too.
const layout_version: u16 = 1;

/// Bytes before the variable-length `main_branch`:
/// `magic(8) | format_version(2) | layout_version(2) | end(8) | frame_count(8) |
/// last_frame_offset(8) | last_header_crc(4) | main_branch_len(2) |
/// image_len(4) | shun_fp(4)` -- see the append order in `store`.
/// (Historic comment below described the v1 prefix.)
/// last_frame_offset(8) | last_header_crc(4) | main_branch_len(2) |
/// image_len(4)` = 46.
const fixed_prefix_len: usize = 50;

/// Trailing self-checksum width (CRC32 over every earlier byte).
const checksum_len: usize = 4;

// There is deliberately no maximum-cache-size constant here.
//
// One stood at 2 GiB, justified as bounding "a lying on-disk size before any
// allocation (TigerStyle: never trust a claimed length)". The read path never
// trusted a claimed length: it takes `stat`'s size and allocates exactly that,
// so there was no claim to distrust and nothing the cap defended against. What
// it did do was silently refuse a cache larger than a number nobody chose —
// and because a cache is advisory, that refusal is invisible, degrading to a
// full rebuild from the log with no diagnostic. A performance cliff wearing a
// security justification.
//
// The bounds that are real are stated where they bind: `std.math.cast(usize,
// st.size)` on the read (a size that cannot be addressed cannot be read) and
// the `u32` `image_len` header field on the write.

/// Try to serve `view` from the `.zit-cache` in `dir`, validating it against
/// the live `log_file` (the open `.zit`). Returns true only on a fully
/// validated HIT: correct magic and version, an intact self-checksum, a stored
/// key whose tail still matches the live log (`logstore.validateTail` — O(1), no
/// full scan), and a record body `RepoView` accepts. On a hit `view` is filled
/// and self-contained (the caller `deinit`s it). Returns false on ANY miss — no
/// file, wrong magic/version, size out of bounds, checksum failure, a stale key,
/// or a malformed body — and never errors: a cache is advisory, so a missing or
/// unreadable one just means "rebuild from the log". On a false return `view` is
/// untouched or already torn down; the caller must not `deinit` it.
/// The representation a caller wants served from a validated cache. `.full`
/// always derives the full `RepoState` from the retained record body (today's
/// path — every query answerable). `.fast_read` prefers the zero-parse image
/// section (the hot verbs' path — the freed queries only), transparently
/// falling back to the record-body derive when the cache carries no image or
/// the image is stale/malformed. Both are HITs; the choice never changes an
/// answer, only how much work a warm read pays.
pub const LoadMode = enum { full, fast_read };

pub fn tryLoad(
    gpa: std.mem.Allocator,
    io: std.Io,
    dir: std.Io.Dir,
    log_file: storage.StorageFile,
    view: *repoview.RepoView,
    mode: LoadMode,
) bool {
    var file = dir.openFile(io, cache_filename, .{}) catch
        // Legacy layout: `cache_dirname` is the cache FILE itself.
        dir.openFile(io, cache_dirname, .{}) catch return false; // absent/unreadable ⇒ miss
    defer file.close(io);
    const st = file.stat(io) catch return false;
    const size: usize = std.math.cast(usize, st.size) orelse return false;
    // A valid cache is at least the fixed header + checksum; reject anything
    // shorter (truncated). There is no upper bound beyond the `usize` cast
    // above: `size` is what `stat` reports, not what the file claims, so the
    // allocation below is the file itself and a ceiling here could only refuse
    // a cache this code had legitimately written.
    if (size < fixed_prefix_len + checksum_len) return false;

    const buf = gpa.alloc(u8, size) catch return false;
    // On the image path `buf` is handed to the view (its columns view into it);
    // on every other path it is a scratch buffer freed here.
    var owned_by_view = false;
    defer if (!owned_by_view) gpa.free(buf);
    const n = file.readPositionalAll(io, buf, 0) catch return false;
    if (n != size) return false;

    if (!std.mem.eql(u8, buf[0..8], magic)) return false;
    if (std.mem.readInt(u16, buf[8..10], .little) != format_version) return false;
    const stored_layout = std.mem.readInt(u16, buf[10..12], .little);

    // Self-checksum over everything but the trailing CRC — a torn or bitflipped
    // cache fails here and is treated as a miss, never a trusted partial view.
    const stored_crc = std.mem.readInt(u32, buf[size - checksum_len ..][0..4], .little);
    var crc = crc32.Crc32.init();
    crc.update(buf[0 .. size - checksum_len]);
    if (crc.final() != stored_crc) return false;

    // The stored key must still describe the live log's tail — the whole
    // invalidation story. Any append, truncation, or a rewritten tail changes
    // it, so a stale cache cannot validate. O(1): one stat + one header read.
    const stored_key: logstore.LogStore.LogKey = .{
        .end = std.mem.readInt(u64, buf[12..20], .little),
        .frame_count = std.mem.readInt(u64, buf[20..28], .little),
        .last_frame_offset = std.mem.readInt(u64, buf[28..36], .little),
        .last_header_crc = std.mem.readInt(u32, buf[36..40], .little),
    };
    if (!logstore.LogStore.validateTail(log_file, stored_key)) return false;

    const mbl: usize = std.mem.readInt(u16, buf[40..42], .little);
    const image_len: usize = std.mem.readInt(u32, buf[42..46], .little);
    // buf[46..50] is the shun fingerprint; the exact-tail hit path does not
    // need it -- an unchanged tail implies an unchanged shun table.
    // Validate the declared spans against the actual file size before slicing
    // (never trust a claimed-huge length): header + main_branch + record body +
    // image + checksum must fit exactly.
    if (fixed_prefix_len + mbl + image_len + checksum_len > size) return false;
    if (mbl == 0) return false; // main_branch is never empty (§6.1: unset ⇒ "trunk")
    const main_branch = buf[fixed_prefix_len .. fixed_prefix_len + mbl];
    const body_end = size - checksum_len - image_len;
    const body = buf[fixed_prefix_len + mbl .. body_end];
    const image = buf[body_end .. size - checksum_len];

    // Fast path: serve the zero-parse image when the schema matches and one is
    // present. A malformed/OOM image is not an error — fall through to the
    // record-body derive, which is still a validated HIT.
    if (mode == .fast_read and image_len > 0 and stored_layout == layout_version) {
        if (view.buildFromImage(gpa, buf, image, main_branch)) |_| {
            owned_by_view = true;
            return true;
        } else |_| {}
    }

    // Replay the records without touching the log. On any framing error the
    // view tears itself down and we fall back to a rebuild.
    view.buildFromRecordBody(gpa, body, main_branch) catch return false;
    return true;
}

/// Everything cache extension needs from an existing `.zit-cache`, without
/// building a view. `buf` owns the backing bytes; `main_branch` and `body`
/// are windows into it.
pub const RawCache = struct {
    buf: []u8,
    key: logstore.LogStore.LogKey,
    shun_fp: u32,
    main_branch: []const u8,
    body: []const u8,

    pub fn deinit(self: *RawCache, gpa: std.mem.Allocator) void {
        gpa.free(self.buf);
        self.* = undefined;
    }
};

/// Read and structurally validate the `.zit-cache`, returning its key, shun
/// fingerprint and record body WITHOUT checking the log's tail -- the caller
/// is deciding between "still exact", "extendable prefix" and "stale", and
/// that decision needs the stored key first. Magic, version and the
/// self-checksum are still enforced: a torn cache is null here exactly as it
/// is a miss in `tryLoad`.
pub fn loadForExtension(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) ?RawCache {
    var file = dir.openFile(io, cache_filename, .{}) catch
        dir.openFile(io, cache_dirname, .{}) catch return null;
    defer file.close(io);
    const st = file.stat(io) catch return null;
    const size: usize = std.math.cast(usize, st.size) orelse return null;
    if (size < fixed_prefix_len + checksum_len) return null;
    const buf = gpa.alloc(u8, size) catch return null;
    errdefer gpa.free(buf);
    const n = file.readPositionalAll(io, buf, 0) catch {
        gpa.free(buf);
        return null;
    };
    if (n != size) {
        gpa.free(buf);
        return null;
    }
    if (!std.mem.eql(u8, buf[0..8], magic) or
        std.mem.readInt(u16, buf[8..10], .little) != format_version)
    {
        gpa.free(buf);
        return null;
    }
    const stored_crc = std.mem.readInt(u32, buf[size - checksum_len ..][0..4], .little);
    var crc = crc32.Crc32.init();
    crc.update(buf[0 .. size - checksum_len]);
    if (crc.final() != stored_crc) {
        gpa.free(buf);
        return null;
    }
    const mbl: usize = std.mem.readInt(u16, buf[40..42], .little);
    const image_len: usize = std.mem.readInt(u32, buf[42..46], .little);
    if (fixed_prefix_len + mbl + image_len + checksum_len > size or mbl == 0) {
        gpa.free(buf);
        return null;
    }
    return .{
        .buf = buf,
        .key = .{
            .end = std.mem.readInt(u64, buf[12..20], .little),
            .frame_count = std.mem.readInt(u64, buf[20..28], .little),
            .last_frame_offset = std.mem.readInt(u64, buf[28..36], .little),
            .last_header_crc = std.mem.readInt(u32, buf[36..40], .little),
        },
        .shun_fp = std.mem.readInt(u32, buf[46..50], .little),
        .main_branch = buf[fixed_prefix_len .. fixed_prefix_len + mbl],
        .body = buf[fixed_prefix_len + mbl .. size - checksum_len - image_len],
    };
}

/// Write `body` (a `RepoView.loadCapturing` record body) plus `main_branch` and
/// `key` to the `.zit-cache` in `dir`, atomically (temp file + fsync + rename),
/// so a reader ever sees either the prior valid cache or this one — never a torn
/// file. Best-effort: a read-only directory, a full disk, or any I/O failure is
/// swallowed (the verb has already answered from the just-built view); the cache
/// is an optimization, not a correctness dependency. The temp file is deleted on
/// any early return.
pub fn store(
    gpa: std.mem.Allocator,
    io: std.Io,
    dir: std.Io.Dir,
    key: logstore.LogStore.LogKey,
    shun_fp: u32,
    main_branch: []const u8,
    body: []const u8,
    image: []const u8,
) void {
    if (main_branch.len == 0 or main_branch.len > std.math.maxInt(u16)) return; // §6.1 invariant
    if (image.len > std.math.maxInt(u32)) return; // image_len is a u32 header field
    // No aggregate ceiling: the only reason one stood here was to mirror a
    // read-side cap that was itself unfounded, so writing a cache the reader
    // would refuse is no longer possible by construction.

    var out: std.ArrayList(u8) = .empty;
    defer out.deinit(gpa);
    out.appendSlice(gpa, magic) catch return;
    appendInt(gpa, &out, u16, format_version) catch return;
    appendInt(gpa, &out, u16, layout_version) catch return;
    appendInt(gpa, &out, u64, key.end) catch return;
    appendInt(gpa, &out, u64, key.frame_count) catch return;
    appendInt(gpa, &out, u64, key.last_frame_offset) catch return;
    appendInt(gpa, &out, u32, key.last_header_crc) catch return;
    appendInt(gpa, &out, u16, @intCast(main_branch.len)) catch return;
    appendInt(gpa, &out, u32, @intCast(image.len)) catch return;
    appendInt(gpa, &out, u32, shun_fp) catch return;
    out.appendSlice(gpa, main_branch) catch return;
    out.appendSlice(gpa, body) catch return;
    out.appendSlice(gpa, image) catch return;
    var crc = crc32.Crc32.init();
    crc.update(out.items);
    appendInt(gpa, &out, u32, crc.final()) catch return;

    if (!ensureCacheDir(io, dir)) return;
    var af = dir.createFileAtomic(io, cache_filename, .{ .replace = true }) catch return;
    defer af.deinit(io);
    af.file.writePositionalAll(io, out.items, 0) catch return;
    af.file.sync(io) catch return; // durable before the rename makes it visible
    af.replace(io) catch return; // atomic rename into place
}

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 load-bearing invariant is HIT ≡ recompute (byte-identical) and
// "a stale/corrupt/wrong-key cache is never served". Fixtures build real logs
// through `LogStore` and derive with the real `RepoView`; expected values come
// from the repo-state RFC (§1 memo, §7.1 precomputed table, §7.3 rebuild).
// ===========================================================================

const artifact = @import("artifact.zig");
const repostate = @import("repostate.zig");
const repoimage = @import("repoimage.zig");
const testing = std.testing;

/// A tmp-backed writable log plus the checkout dir the cache lives in.
const Fixture = struct {
    tmp: std.testing.TmpDir,
    fs: storage.FileStorage,
    log: logstore.LogStore,

    fn init(self: *Fixture, io: std.Io) !void {
        self.tmp = testing.tmpDir(.{});
        const raw = try self.tmp.dir.createFile(io, ".zit", .{ .read = true });
        self.fs = storage.FileStorage.init(io, raw, 0);
        self.log = try logstore.LogStore.open(testing.allocator, self.fs.storageFile(), 0);
    }

    fn deinit(self: *Fixture, io: std.Io) void {
        self.log.deinit(testing.allocator);
        self.fs.file.close(io);
        self.tmp.cleanup();
    }

    /// A freshly-scanned read-only view of the log — the shape production always
    /// derives from (`openReadOnly` populates the frame-count/tail bookkeeping
    /// `logKey` reads). The writable `self.log` used for seeding does not
    /// maintain that bookkeeping, so cache-key work goes through this. Caller
    /// `deinit`s the returned store.
    fn openScan(self: *Fixture) !logstore.LogStore {
        return logstore.LogStore.openReadOnly(testing.allocator, self.fs.storageFile());
    }

    /// Store a manifest/control built by `m` under its own sha3-256 digest.
    fn put(self: *Fixture, m: *const artifact.Manifest) !void {
        const bytes = try artifact.create(m, testing.allocator);
        defer testing.allocator.free(bytes);
        var digest: [32]u8 = undefined;
        std.crypto.hash.sha3.Sha3_256.hash(bytes, &digest, .{});
        _ = try self.log.put(&digest, bytes);
    }
};

/// The 64-hex name of a serialized manifest (so a later child can name it as a
/// parent). Caller frees.
fn nameOf(m: *const artifact.Manifest) ![]u8 {
    const bytes = try artifact.create(m, testing.allocator);
    defer testing.allocator.free(bytes);
    var digest: [32]u8 = undefined;
    std.crypto.hash.sha3.Sha3_256.hash(bytes, &digest, .{});
    var hex: [64]u8 = undefined;
    const lut = "0123456789abcdef";
    for (digest, 0..) |b, i| {
        hex[i * 2] = lut[b >> 4];
        hex[i * 2 + 1] = lut[b & 0x0f];
    }
    return testing.allocator.dupe(u8, &hex);
}

fn checkinManifest(ts: []const u8, parent: ?[]const u8, tags: []const artifact.TCard, pbuf: []artifact.PCard) artifact.Manifest {
    var p_slice: []const artifact.PCard = &.{};
    if (parent) |par| {
        pbuf[0] = .{ .parents = par, .count = 1 };
        p_slice = pbuf[0..1];
    }
    return .{
        .arena_state = std.heap.ArenaAllocator.init(testing.allocator),
        .kind = .manifest,
        .a = null,
        .b = null,
        .c = .{ .comment = "c" },
        .d = .{ .timestamp = ts },
        .e = null,
        .g = null,
        .h = null,
        .i = null,
        .k = null,
        .l = null,
        .n = null,
        .r = null,
        .u = .{ .login = "u" },
        .z = null,
        .w = null,
        .f = &.{},
        .j = &.{},
        .m = &.{},
        .p = p_slice,
        .q = &.{},
        .t = tags,
    };
}

fn controlManifest(ts: []const u8, tags: []const artifact.TCard) artifact.Manifest {
    return .{
        .arena_state = std.heap.ArenaAllocator.init(testing.allocator),
        .kind = .control,
        .a = null,
        .b = null,
        .c = null,
        .d = .{ .timestamp = ts },
        .e = null,
        .g = null,
        .h = null,
        .i = null,
        .k = null,
        .l = null,
        .n = null,
        .r = null,
        .u = .{ .login = "u" },
        .z = null,
        .w = null,
        .f = &.{},
        .j = &.{},
        .m = &.{},
        .p = &.{},
        .q = &.{},
        .t = tags,
    };
}

/// Build a small but structurally rich repo: a trunk root, a same-branch child,
/// a second root that forks trunk, and a control that closes a leaf — exercising
/// leaves, branches, propagation, and a control artifact.
fn seedRepo(fx: *Fixture) !void {
    var pbuf: [1]artifact.PCard = undefined;

    const branch_root = [_]artifact.TCard{.{ .sign = .propagate, .name = "branch", .target = null, .value = "trunk" }};
    var root_m = checkinManifest("2020-01-01T00:00:00", null, &branch_root, &pbuf);
    defer root_m.deinit();
    const root = try nameOf(&root_m);
    defer testing.allocator.free(root);
    try fx.put(&root_m);

    var child_m = checkinManifest("2020-01-02T00:00:00", root, &.{}, &pbuf);
    defer child_m.deinit();
    const child = try nameOf(&child_m);
    defer testing.allocator.free(child);
    try fx.put(&child_m);

    var root2_m = checkinManifest("2020-01-03T00:00:00", null, &branch_root, &pbuf);
    defer root2_m.deinit();
    const root2 = try nameOf(&root2_m);
    defer testing.allocator.free(root2);
    try fx.put(&root2_m);

    const close = [_]artifact.TCard{.{ .sign = .add, .name = "closed", .target = root2, .value = null }};
    var ctl_m = controlManifest("2020-01-04T00:00:00", &close);
    defer ctl_m.deinit();
    try fx.put(&ctl_m);
}

/// Assert two views are observably identical across every derived query the
/// verbs read. Rids match between the views because the same records intern in
/// the same order, so a per-rid comparison is valid.
fn expectViewsEqual(a: *repoview.RepoView, b: *repoview.RepoView) !void {
    try testing.expectEqualStrings(a.main_branch, b.main_branch);
    try testing.expectEqual(a.store.store().count(), b.store.store().count());

    // Leaf table: same membership AND same iteration order (§7.5 SHOULD order).
    var la = a.state.leaves();
    var lb = b.state.leaves();
    while (la.next()) |ra| {
        const rb = lb.next() orelse return error.LeafCountMismatch;
        try testing.expectEqual(ra, rb);
    }
    try testing.expect(lb.next() == null);

    const count = a.store.store().count();
    var rid: repostate.Rid = 1;
    while (rid <= count) : (rid += 1) {
        try testing.expectEqualStrings(a.hashOf(rid), b.hashOf(rid));
        try testing.expectEqual(a.state.mtimeOf(rid), b.state.mtimeOf(rid));
        try testing.expectEqual(a.state.isLeaf(rid), b.state.isLeaf(rid));
        try testing.expectEqual(a.state.isOpenLeaf(rid), b.state.isOpenLeaf(rid));
        try testing.expectEqual(a.state.isAmbiguousLeaf(rid), b.state.isAmbiguousLeaf(rid));
        // branchOf requires an event row (§6.1): skip eventless phantoms and
        // control carriers, whose absence-of-event was already asserted above.
        if (a.state.mtimeOf(rid) != null)
            try testing.expectEqualStrings(a.state.branchOf(rid, a.main_branch), b.state.branchOf(rid, b.main_branch));

        const ta = try a.state.tagsOf(testing.allocator, rid);
        defer testing.allocator.free(ta);
        const tb = try b.state.tagsOf(testing.allocator, rid);
        defer testing.allocator.free(tb);
        try testing.expectEqual(ta.len, tb.len);
        for (ta, tb) |ea, eb| {
            try testing.expectEqualStrings(ea.name, eb.name);
            try testing.expectEqual(ea.tagtype, eb.tagtype);
        }
    }

    const ba = try a.state.branches(testing.allocator);
    defer testing.allocator.free(ba);
    const bb = try b.state.branches(testing.allocator);
    defer testing.allocator.free(bb);
    try testing.expectEqual(ba.len, bb.len);
    for (ba, bb) |ea, eb| {
        try testing.expectEqualStrings(ea.name, eb.name);
        try testing.expectEqual(ea.tip, eb.tip);
        try testing.expectEqual(ea.closed, eb.closed);
    }

    const na = try a.state.tagNames(testing.allocator);
    defer testing.allocator.free(na);
    const nb = try b.state.tagNames(testing.allocator);
    defer testing.allocator.free(nb);
    try testing.expectEqual(na.len, nb.len);
    for (na, nb) |ea, eb| try testing.expectEqualStrings(ea, eb);
}

/// Capture the record body + key + main_branch for `fx`'s current log (through a
/// freshly-scanned read-only store, as production does), then build a
/// from-scratch reference view. Caller `deinit`s `ref` and frees `body`.
fn captureAndReference(fx: *Fixture, ref: *repoview.RepoView, body: *std.ArrayList(u8)) !logstore.LogStore.LogKey {
    var ro = try fx.openScan();
    defer ro.deinit(testing.allocator);
    const key = try ro.logKey();
    var capture: repoview.RepoView = undefined;
    try capture.loadCapturing(testing.allocator, &ro, body);
    // The reference is a plain from-scratch derivation over the same log.
    try ref.load(testing.allocator, &ro);
    capture.deinit(testing.allocator);
    return key;
}

test "cache §1/§7.1: a hit reconstructs a byte-identical view for a representative repo" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "");

    var hit: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &hit, .full));
    defer hit.deinit(testing.allocator);
    try expectViewsEqual(&ref, &hit);
}

test "cache §1: hit equals from-scratch derivation for random check-in op-sequences" {
    const io = testing.io;
    // The DST derivation oracle in miniature: random DAGs of varied sizes,
    // each proved to round-trip through the on-disk cache byte-identically.
    var prng = std.Random.DefaultPrng.init(0xca6e_5eed);
    const rand = prng.random();

    for ([_]usize{ 1, 2, 5, 12, 30, 64 }) |n| {
        var fx: Fixture = undefined;
        try fx.init(io);
        defer fx.deinit(io);

        var names: std.ArrayList([]u8) = .empty;
        defer {
            for (names.items) |nm| testing.allocator.free(nm);
            names.deinit(testing.allocator);
        }
        var pbuf: [1]artifact.PCard = undefined;
        var day: usize = 0;
        while (day < n) : (day += 1) {
            var tsbuf: [32]u8 = undefined;
            const ts = try std.fmt.bufPrint(&tsbuf, "2021-01-01T00:00:{d:0>2}", .{day % 60});
            // Roughly half the check-ins descend from a random earlier one; the
            // rest are fresh roots — a mix of chains, forks, and independent tips.
            const parent: ?[]const u8 = if (names.items.len != 0 and rand.boolean())
                names.items[rand.intRangeLessThan(usize, 0, names.items.len)]
            else
                null;
            const tags: []const artifact.TCard = if (parent == null)
                &[_]artifact.TCard{.{ .sign = .propagate, .name = "branch", .target = null, .value = "trunk" }}
            else
                &.{};
            var m = checkinManifest(ts, parent, tags, &pbuf);
            defer m.deinit();
            try names.append(testing.allocator, try nameOf(&m));
            try fx.put(&m);
        }

        var body: std.ArrayList(u8) = .empty;
        defer body.deinit(testing.allocator);
        var ref: repoview.RepoView = undefined;
        const key = try captureAndReference(&fx, &ref, &body);
        defer ref.deinit(testing.allocator);

        store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "");
        var hit: repoview.RepoView = undefined;
        try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &hit, .full));
        defer hit.deinit(testing.allocator);
        try expectViewsEqual(&ref, &hit);
    }
}

test "cache §7.3: a grown-log key mismatch is a miss (caller rebuilds, then rewrites)" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    ref.deinit(testing.allocator);
    store(testing.allocator, io, fx.tmp.dir, key, 0, "trunk", body.items, "");

    // Grow the log by one control artifact: the live tail advances, so the
    // cache written at the old key must now MISS (validateTail sees the change).
    var ctl = controlManifest("2020-02-01T00:00:00", &[_]artifact.TCard{.{ .sign = .add, .name = "wip", .target = null, .value = null }});
    defer ctl.deinit();
    try fx.put(&ctl);

    var view: repoview.RepoView = undefined;
    try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &view, .full));

    // The rebuild+rewrite path yields a hit again at the new key.
    var body2: std.ArrayList(u8) = .empty;
    defer body2.deinit(testing.allocator);
    var ref2: repoview.RepoView = undefined;
    const grown_key = try captureAndReference(&fx, &ref2, &body2);
    defer ref2.deinit(testing.allocator);
    try testing.expect(grown_key.end != key.end); // the key genuinely advanced
    store(testing.allocator, io, fx.tmp.dir, grown_key, 0, ref2.main_branch, body2.items, "");
    var hit2: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &hit2, .full));
    defer hit2.deinit(testing.allocator);
    try expectViewsEqual(&ref2, &hit2);
}

test "cache: a corrupt, truncated, wrong-magic, or wrong-version cache is a miss, never trusted" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    ref.deinit(testing.allocator);
    store(testing.allocator, io, fx.tmp.dir, key, 0, "trunk", body.items, "");

    // Read the freshly written cache back so we can mutate copies of it.
    var f = try fx.tmp.dir.openFile(io, cache_filename, .{});
    const sz = (try f.stat(io)).size;
    const original = try testing.allocator.alloc(u8, @intCast(sz));
    defer testing.allocator.free(original);
    _ = try f.readPositionalAll(io, original, 0);
    f.close(io);

    const rewrite = struct {
        fn go(dir: std.Io.Dir, aio: std.Io, bytes: []const u8) !void {
            var af = try dir.createFileAtomic(aio, cache_filename, .{ .replace = true });
            defer af.deinit(aio);
            try af.file.writePositionalAll(aio, bytes, 0);
            try af.replace(aio);
        }
    }.go;

    // (a) A flipped self-checksum byte ⇒ miss.
    {
        const bad = try testing.allocator.dupe(u8, original);
        defer testing.allocator.free(bad);
        bad[bad.len - 1] ^= 0xff;
        try rewrite(fx.tmp.dir, io, bad);
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
    // (b) A flipped body byte (checksum now fails) ⇒ miss.
    {
        const bad = try testing.allocator.dupe(u8, original);
        defer testing.allocator.free(bad);
        bad[bad.len / 2] ^= 0x01;
        try rewrite(fx.tmp.dir, io, bad);
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
    // (c) Truncated to half its length ⇒ miss (short read / bad checksum).
    {
        try rewrite(fx.tmp.dir, io, original[0 .. original.len / 2]);
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
    // (d) Wrong magic ⇒ miss.
    {
        const bad = try testing.allocator.dupe(u8, original);
        defer testing.allocator.free(bad);
        bad[0] = 'X';
        try rewrite(fx.tmp.dir, io, bad);
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
    // (e) Wrong version ⇒ miss.
    {
        const bad = try testing.allocator.dupe(u8, original);
        defer testing.allocator.free(bad);
        std.mem.writeInt(u16, bad[8..10], format_version + 1, .little);
        try rewrite(fx.tmp.dir, io, bad);
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
}

test "cache migration: a legacy root FILE still hits, and the first write moves it into the directory" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    // Write at the member path, then DEMOTE the layout to the legacy shape:
    // the directory collapses to a single root file holding the same bytes.
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "");
    var member = try fx.tmp.dir.openFile(io, cache_filename, .{});
    const sz = (try member.stat(io)).size;
    const bytes = try testing.allocator.alloc(u8, @intCast(sz));
    defer testing.allocator.free(bytes);
    _ = try member.readPositionalAll(io, bytes, 0);
    member.close(io);
    try fx.tmp.dir.deleteTree(io, cache_dirname);
    {
        var legacy = try fx.tmp.dir.createFile(io, cache_dirname, .{});
        defer legacy.close(io);
        try legacy.writePositionalAll(io, bytes, 0);
    }

    // (c) The legacy file still serves a validated HIT through the fallback.
    var hit: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &hit, .full));
    defer hit.deinit(testing.allocator);
    try expectViewsEqual(&ref, &hit);

    // The first write migrates: the root name becomes a directory, the
    // derivation lands inside it, and the payload still parses as the same
    // format (`tryLoad` from the member is a fresh validated hit).
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "");
    const st = try fx.tmp.dir.statFile(io, cache_dirname, .{ .follow_symlinks = false });
    try testing.expect(st.kind == .directory);
    var rehit: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &rehit, .full));
    defer rehit.deinit(testing.allocator);
    try expectViewsEqual(&ref, &rehit);

    // (d) Deleting the whole directory changes no answer -- the next reader
    // simply derives cold.
    try fx.tmp.dir.deleteTree(io, cache_dirname);
    var cold: repoview.RepoView = undefined;
    try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &cold, .full));
}

test "cache: an atomic rewrite over a corrupt cache lands a valid, servable one" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    // Plant a garbage cache member first (a prior torn/foreign file). The
    // planting itself needs the directory the production writer would have
    // made.
    {
        try testing.expect(ensureCacheDir(io, fx.tmp.dir));
        var af = try fx.tmp.dir.createFileAtomic(io, cache_filename, .{ .replace = true });
        defer af.deinit(io);
        try af.file.writePositionalAll(io, "garbage not a cache", 0);
        try af.replace(io);
    }

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    // The garbage file is a clean miss...
    {
        var v: repoview.RepoView = undefined;
        try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
    }
    // ...and the atomic store replaces it in place with a servable cache.
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "");
    var hit: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &hit, .full));
    defer hit.deinit(testing.allocator);
    try expectViewsEqual(&ref, &hit);
}

test "cache: tryLoad on an absent cache is a miss, not an error" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);
    var v: repoview.RepoView = undefined;
    try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .full));
}

/// Assert an image-backed view answers every FREED query identically to the
/// derived reference (§7.1 leaf set/order, §7.4 open predicate, §7.5/§8.3 event
/// times, §6.1 branch-of, §8.2 name resolution, plus hash/lookup). The cold
/// queries (`tagsOf`/`branches`/`tagNames`/adjacency) are intentionally not
/// compared — the image does not serve them; `.full` verbs do.
fn expectFreedQueriesEqual(image_view: *repoview.RepoView, ref: *repoview.RepoView) !void {
    try testing.expect(image_view.state.backing == .image);
    try testing.expectEqualStrings(ref.main_branch, image_view.main_branch);
    const count = ref.store.store().count();
    try testing.expectEqual(count, image_view.state.img.?.count());

    var la = ref.state.leaves();
    var lb = image_view.state.leaves();
    while (la.next()) |ra| {
        const rb = lb.next() orelse return error.LeafCountMismatch;
        try testing.expectEqual(ra, rb);
    }
    try testing.expect(lb.next() == null);

    var rid: repostate.Rid = 1;
    while (rid <= count) : (rid += 1) {
        try testing.expectEqualStrings(ref.hashOf(rid), image_view.hashOf(rid));
        try testing.expectEqual(rid, image_view.lookup(ref.hashOf(rid)).?);
        try testing.expectEqual(ref.state.mtimeOf(rid), image_view.state.mtimeOf(rid));
        try testing.expectEqual(ref.state.isLeaf(rid), image_view.state.isLeaf(rid));
        try testing.expectEqual(ref.state.isOpenLeaf(rid), image_view.state.isOpenLeaf(rid));
        if (ref.state.mtimeOf(rid) != null)
            try testing.expectEqualStrings(ref.state.branchOf(rid, ref.main_branch), image_view.state.branchOf(rid, image_view.main_branch));
    }

    // §8.2: every live symbolic name resolves identically through both views.
    const syms = try ref.state.resolvedSymbols(testing.allocator);
    defer testing.allocator.free(syms);
    for (syms) |s| {
        try testing.expectEqual(ref.state.resolveName(s.name) catch null, image_view.state.resolveName(s.name) catch null);
    }
}

test "cache §7.1/§7.4/§8.2: a .fast_read image load is query-equivalent to a full derive" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    var image: std.ArrayList(u8) = .empty;
    defer image.deinit(testing.allocator);
    try repoimage.serialize(testing.allocator, &ref.state, ref.main_branch, &image);
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, image.items);

    // .fast_read takes the image path; .full derives from the same cache.
    var fast: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &fast, .fast_read));
    defer fast.deinit(testing.allocator);
    try expectFreedQueriesEqual(&fast, &ref);

    var full: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &full, .full));
    defer full.deinit(testing.allocator);
    try testing.expect(full.state.backing == .derived);
    try expectViewsEqual(&ref, &full);
}

test "cache: a bit-flip anywhere in the image section fails the CRC ⇒ miss, never a wrong answer" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    var image: std.ArrayList(u8) = .empty;
    defer image.deinit(testing.allocator);
    try repoimage.serialize(testing.allocator, &ref.state, ref.main_branch, &image);
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, image.items);

    // Flip one byte inside the stored image region; the trailing CRC covers it.
    var f = try fx.tmp.dir.openFile(io, cache_filename, .{ .mode = .read_write });
    defer f.close(io);
    const sz: usize = @intCast((try f.stat(io)).size);
    // The image sits just before the 4-byte checksum; flip a byte there.
    const flip_at = sz - checksum_len - 1;
    var one: [1]u8 = undefined;
    _ = try f.readPositionalAll(io, &one, flip_at);
    one[0] ^= 0xFF;
    try f.writePositionalAll(io, &one, flip_at);
    try f.sync(io);

    var v: repoview.RepoView = undefined;
    try testing.expect(!tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .fast_read));
}

test "cache: a CRC-valid but structurally-invalid image ⇒ .fast_read falls back to the record-body derive" {
    const io = testing.io;
    var fx: Fixture = undefined;
    try fx.init(io);
    defer fx.deinit(io);
    try seedRepo(&fx);

    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(testing.allocator);
    var ref: repoview.RepoView = undefined;
    const key = try captureAndReference(&fx, &ref, &body);
    defer ref.deinit(testing.allocator);

    // A non-empty but structurally invalid image: too short for even the header,
    // so `Image.load` returns null and the fast path degrades to a full derive
    // over the record body (still a validated HIT with correct answers).
    store(testing.allocator, io, fx.tmp.dir, key, 0, ref.main_branch, body.items, "not-a-valid-image");

    var v: repoview.RepoView = undefined;
    try testing.expect(tryLoad(testing.allocator, io, fx.tmp.dir, fx.fs.storageFile(), &v, .fast_read));
    defer v.deinit(testing.allocator);
    try testing.expect(v.state.backing == .derived); // fell back to derive
    try expectViewsEqual(&ref, &v);
}