Skip to content
zit Artifact [97fec6f1af]
Login

Artifact [97fec6f1af]

Check-ins Using Download Hex

Artifact 97fec6f1afdbabd7e4604119326dd0acfb0bb5ab94f098e6597e06629f69e17d:

//! Repository State — draft-fossil-repo-state-00.
//!
//! Repository state is derived, not stored: branches, tags, leaves, closed
//! markers, and the current-trunk check-in are computed from the crosslinked
//! set of artifacts. This module owns that derivation over the parent DAG and
//! the tag records defined by the Artifact Format.
//!
//! Input is a `Record` — one check-in's linkage/tag facts — rather than raw
//! manifest bytes; a thin manifest-to-Record adapter arrives with manifest
//! assembly. Artifact identity (hash-to-rid, phantoms) lives behind the
//! `ArtifactStore` boundary so tests and the simulation harness can inject
//! an in-memory store. Nothing here touches ambient time, randomness, the
//! filesystem, or the network.

const std = @import("std");
/// delta §4 apply — repostate sits above `delta` in the RFC layering
/// (delta -> artifact -> repostate), so a direct file import is layer-legal
/// and introduces no cycle. Used to reconstruct a delta-wire entry's plaintext.
const delta = @import("delta.zig");
/// The §4.1 zlib container codec — a leaf below repostate, so the direct file
/// import is layer-legal. `MemStore` stores wire-backed entries verbatim and
/// inflates them through this single shared codec.
const codec = @import("container.zig");

/// The materialized read-image (`repoimage.zig`): the hot query answers of a
/// derived `RepoState`, laid out as dense integer-addressed columns. When a
/// warm read loads one, `RepoState` runs in `.image` backing and its freed
/// query methods read the columns instead of re-deriving the hashmaps. The
/// representation stays hidden there; this module only holds the loaded view.
const repoimage = @import("repoimage.zig");

/// A stored artifact's local integer identifier (Section 2). Local to a
/// repository; not part of the artifact model and not synchronised.
pub const Rid = u64;

/// A check-in's modification time (Section 3.1's event.mtime). Ordinal
/// comparison alone drives Sections 7-9's leaf/branch/current-trunk views.
/// Section 8.3 form 7 (date-form name resolution) additionally interprets
/// both a parsed timestamp and every stored event.mtime on one shared
/// millisecond timeline — Unix-epoch milliseconds computed by a pure
/// civil-date calculation below, never an ambient clock. The choice of
/// epoch is encapsulated in that calculation and is epoch-independent for
/// *which* check-in resolves: the calendar-to-timeline mapping is
/// monotonic and applied identically to the query bound and to stored
/// mtimes, so every other derived view — which only ever compares mtimes
/// against each other — is unaffected by this reinterpretation.
pub const Mtime = u64;

/// Tag type values (Section 5.1). The integer encoding is normative: every
/// tag reference is persisted with one of exactly these three small
/// integers.
pub const TagType = enum(u2) {
    /// value 0, surface syntax `-`: removes or blocks a tag.
    cancel = 0,
    /// value 1, surface syntax `+`: applies to a single check-in only.
    singleton = 1,
    /// value 2, surface syntax `*`: applies to the target and, absent an
    /// intervening cancel, its primary-chain descendants.
    propagate = 2,
};

/// One validated T-card, post-parse (Section 4.1 validation happens in the
/// artifact layer). A null `target` designates a self-tag: the tag applies
/// to the artifact being crosslinked (Section 4.2 step 1).
pub const TagOp = struct {
    type: TagType,
    name: []const u8,
    target: ?[]const u8,
    value: ?[]const u8,
};

/// One check-in's crosslink input: its hash, event time, parent references
/// in P-card order, and validated tag cards.
pub const Record = struct {
    hash: []const u8,
    mtime: Mtime,
    /// Parent hashes in manifest order; `parents[0]` is the primary parent
    /// (Section 3.2). Empty for an initial check-in.
    parents: []const []const u8 = &.{},
    tags: []const TagOp = &.{},
};

/// Sync §4.1/§7.2 — a stored artifact's on-the-wire cfile payload: the §4.1
/// zlib `container` (4-byte big-endian uncompressed length + RFC1950 stream)
/// retransmitted byte-for-byte. Borrows the store; valid until the next
/// mutation. USIZE needs no separate field: it is the container's first four
/// bytes (§4.1). A distinct type from `content()`'s plaintext `[]const u8` so
/// the two never blur at the vtable boundary.
pub const WireFrame = struct {
    container: []const u8,
    /// Null for the §7.2 full form (the container reconstructs the whole
    /// artifact; USIZE is its own 4-byte prefix). Non-null for the delta form:
    /// the container holds a [FossilDelta] against `src_hash`, and `target_size`
    /// is the reconstructed-artifact size (the cfile USIZE, delta §3.2 — NEVER
    /// the container prefix, which is the raw delta length). The full-form call
    /// sites are unchanged: they never read this field.
    delta: ?Delta = null,

    pub const Delta = struct {
        /// The basis artifact's wire name (DELTASRC), borrowing the store.
        src_hash: []const u8,
        /// delta §3.2 — the reconstructed target length; the cfile USIZE.
        target_size: u64,
    };
};

/// Sync §7.2/§4.1 — the wire form a receiver retains for an already-stored rid
/// so a later serve retransmits it verbatim. The write-side twin of
/// `WireFrame`: `retain()` records what `wire()` later reads. Advisory — a
/// store MAY drop it and the receiver still persists correct plaintext, so no
/// correctness rests on retention, only compactness on re-serve.
pub const WireIngest = union(enum) {
    /// A §4.1 full-artifact zlib container, retained verbatim (the §7.2 full
    /// form; USIZE is the container's own 4-byte prefix).
    full: []const u8,
    /// A §4.1 zlib container of a [FossilDelta] against `src` (DELTASRC), plus
    /// the reconstructed-target size (delta §3.2 — the cfile USIZE, NEVER the
    /// container prefix).
    delta: Delta,

    pub const Delta = struct {
        src: []const u8,
        container: []const u8,
        target_size: u64,
    };
};

/// The artifact identity boundary: hash-to-rid interning, content storage,
/// and phantom placeholders (Section 4.2 step 1). A runtime vtable so the
/// simulation harness and tests inject an in-memory implementation while a
/// durable store can slot in later without touching the derivation code.
pub const ArtifactStore = struct {
    context: *anyopaque,
    vtable: *const VTable,

    pub const VTable = struct {
        /// Resolve a hash to its rid, creating a phantom placeholder — an
        /// rid that carries no content yet — when the hash is unknown
        /// (Section 4.2 step 1).
        intern: *const fn (context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid,
        /// Store content for a hash, upgrading a phantom in place.
        /// Idempotent: content is addressed by hash, so a repeat put of the
        /// same hash carries the same bytes.
        put: *const fn (context: *anyopaque, hash: []const u8, content: []const u8) error{OutOfMemory}!Rid,
        /// The stored bytes for a rid, or null while it is a phantom.
        content: *const fn (context: *anyopaque, rid: Rid) ?[]const u8,
        /// The hash that names a rid. Every rid, phantom or not, has one.
        hashOf: *const fn (context: *anyopaque, rid: Rid) []const u8,
        /// Resolve a hash to its rid WITHOUT creating a phantom; null when the
        /// hash is unknown. Unlike `intern`, this is a pure membership query —
        /// a receiver deciding whether it holds gimme'd content must not mint a
        /// phantom for a hash it has never seen (Sync §3.3).
        lookup: *const fn (context: *anyopaque, hash: []const u8) ?Rid,
        /// The number of entries in the store. Rids are dense in `1..=count`,
        /// so a peer walks every entry with `rid in 1..=count` and classifies
        /// each via `content(rid)` (null => phantom, non-null => held) to
        /// announce holdings and request phantoms (Sync §3.2/§3.3).
        count: *const fn (context: *anyopaque) usize,
        /// Sync §7.2 — the stored full-content §4.1 container for `rid`,
        /// retransmitted verbatim, or null when the store holds no such form
        /// for it (a raw, delta, or phantom entry; the serve loop then falls
        /// back to compressing `content()`). Nullable and general: any store
        /// MAY decline and the server still answers correctly, so this never
        /// special-cases one backing store.
        wire: *const fn (context: *anyopaque, rid: Rid) ?WireFrame,
        /// Sync §7.2/§4.1 — retain the wire form the peer delivered for `rid`
        /// (already `put`/reconstructed) so a later serve retransmits the
        /// stored form verbatim. The write-side twin of `wire`. Advisory: a
        /// store MAY ignore it and the receiver still persists correct
        /// plaintext, so correctness never depends on retention. Only
        /// `OutOfMemory` escapes.
        retain: *const fn (context: *anyopaque, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void,
    };

    pub fn intern(self: ArtifactStore, hash: []const u8) error{OutOfMemory}!Rid {
        return self.vtable.intern(self.context, hash);
    }

    pub fn put(self: ArtifactStore, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
        return self.vtable.put(self.context, hash, content_bytes);
    }

    pub fn content(self: ArtifactStore, rid: Rid) ?[]const u8 {
        return self.vtable.content(self.context, rid);
    }

    pub fn hashOf(self: ArtifactStore, rid: Rid) []const u8 {
        return self.vtable.hashOf(self.context, rid);
    }

    pub fn lookup(self: ArtifactStore, hash: []const u8) ?Rid {
        return self.vtable.lookup(self.context, hash);
    }

    pub fn count(self: ArtifactStore) usize {
        return self.vtable.count(self.context);
    }

    pub fn wire(self: ArtifactStore, rid: Rid) ?WireFrame {
        return self.vtable.wire(self.context, rid);
    }

    pub fn retain(self: ArtifactStore, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void {
        return self.vtable.retain(self.context, rid, ingest);
    }

    /// True when `rid` has BYTES TO SERVE VERBATIM — a retained §4.1 container
    /// (`wire()`) or already-materialised plaintext (`content()`) — as opposed
    /// to a bare phantom (Sync §3.3 r24). The held-vs-phantom predicate the
    /// request composer and persist pass need WITHOUT forcing a `content()`
    /// inflate: a wire-backed entry answers from its container's presence alone,
    /// so a clone that stores every artifact wire-backed never materialises (and
    /// memoises) plaintext just to classify it.
    ///
    /// NOT equal to `content(rid) != null`: a wire-backed container may be held
    /// yet NOT reconstructable — a §7.2/§7.7 full container retained verbatim
    /// whose stored bytes fail to inflate is `held()==true` with
    /// `content()==null`. `held()` means "I can retransmit its wire form"; it does
    /// NOT promise materialisable plaintext. A caller that needs plaintext (e.g.
    /// the §3.2 upload composer, which builds a file card from `content()`) MUST
    /// gate on `content()`, never infer materialisability from `held()`. Derived
    /// from the existing vtable, so no store implements it specially.
    pub fn held(self: ArtifactStore, rid: Rid) bool {
        if (self.vtable.wire(self.context, rid) != null) return true;
        return self.vtable.content(self.context, rid) != null;
    }
};

/// In-memory `ArtifactStore`: rids are assigned densely in intern order
/// (index + 1, so rid 0 stays invalid), and a phantom is an entry whose
/// bytes are still null.
pub const MemStore = struct {
    gpa: std.mem.Allocator,
    by_hash: std.StringHashMapUnmanaged(Rid) = .empty,
    entries: std.ArrayList(Entry) = .empty,

    const Entry = struct {
        hash: []u8,
        /// The plaintext, or null. For a `wire`-backed entry this is null
        /// until the first plaintext read materialises (and memoises) it.
        bytes: ?[]u8,
        /// The stored §4.1 container this entry retransmits verbatim (Sync
        /// §7.2), or null for a raw `put` or a phantom. An entry that carries a
        /// container materialises its plaintext lazily into `bytes` on first
        /// `content()` (memoised there), so the clone serve path never inflates.
        /// For a delta-wire entry (`wire_delta` non-null) the container holds a
        /// [FossilDelta], not the whole artifact.
        wire: ?[]u8 = null,
        /// Sync §7.2 delta form: when set, `wire` is a §4.1 container of a
        /// [FossilDelta] against `src_hash`, and `target_size` is the
        /// reconstructed size (the cfile USIZE, delta §3.2). content()
        /// reconstructs against the (materialised) basis lazily; `wire()`
        /// serves the delta form. Null for a full-form or raw entry.
        wire_delta: ?WireDelta = null,
    };

    const WireDelta = struct { src_hash: []u8, target_size: u64 };

    /// Sync §4.1 — the container's declared uncompressed length is bounded
    /// before any inflate, so a lying length field cannot drive unbounded
    /// allocation. Mirrors `logstore.max_payload`.
    const max_wire_payload: usize = 1 << 30;

    /// Explicit upper bound on delta-chain reconstruction depth while
    /// materialising a delta-wire entry's plaintext — the read-side twin of
    /// `logstore.max_delta_chain`, with headroom for a retained foreign chain.
    /// A chain deeper than this yields null (treated as unreconstructable),
    /// never unbounded recursion.
    const max_wire_delta_chain: usize = 64;

    pub fn init(gpa: std.mem.Allocator) MemStore {
        return .{ .gpa = gpa };
    }

    pub fn deinit(self: *MemStore) void {
        for (self.entries.items) |entry| {
            self.gpa.free(entry.hash);
            if (entry.bytes) |bytes| self.gpa.free(bytes);
            if (entry.wire) |container| self.gpa.free(container);
            if (entry.wire_delta) |wd| self.gpa.free(wd.src_hash);
        }
        self.entries.deinit(self.gpa);
        self.by_hash.deinit(self.gpa);
        self.* = undefined;
    }

    /// The type-erased store interface over this instance.
    pub fn store(self: *MemStore) ArtifactStore {
        return .{ .context = self, .vtable = &vtable };
    }

    const vtable = ArtifactStore.VTable{
        .intern = internImpl,
        .put = putImpl,
        .content = contentImpl,
        .hashOf = hashOfImpl,
        .lookup = lookupImpl,
        .count = countImpl,
        .wire = wireImpl,
        .retain = retainImpl,
    };

    /// Sync §7.2/§4.1 — record the wire form the peer delivered for `rid`
    /// verbatim so `wire()` re-serves it. Unlike `putWire`/`putWireDelta`, this
    /// sets the container even when `bytes` is already materialised: the receive
    /// path stores reconstructed plaintext via `put` FIRST, then retains the
    /// wire that produced it. Idempotent: a second retain for an rid already
    /// carrying a container is a no-op (content is hash-addressed, so the first
    /// retained form stands). Duplicates the container (and `src`) — the store
    /// owns its bytes, matching `put`.
    fn retainImpl(context: *anyopaque, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void {
        const self: *MemStore = @ptrCast(@alignCast(context));
        const entry = self.entryOf(rid);
        if (entry.wire != null) return; // already retained; first form wins
        switch (ingest) {
            .full => |container| {
                std.debug.assert(container.len >= 4); // §4.1 — 4-byte length prefix
                entry.wire = try self.gpa.dupe(u8, container);
            },
            .delta => |d| {
                std.debug.assert(d.container.len >= 4); // §4.1 — 4-byte length prefix
                std.debug.assert(d.src.len != 0);
                const c = try self.gpa.dupe(u8, d.container);
                errdefer self.gpa.free(c);
                const s = try self.gpa.dupe(u8, d.src);
                entry.wire = c;
                entry.wire_delta = .{ .src_hash = s, .target_size = d.target_size };
            },
        }
    }

    /// Sync §4.1/§7.2 — store the already-encoded full-content §4.1 `container`
    /// for `hash` verbatim so a clone serves it without recompressing (the whole
    /// point of serving the stored form). Idempotent + phantom-upgrade like
    /// `put`; the plaintext is NOT materialised here — `content()` inflates
    /// lazily on first read. The `container` is duplicated (the store owns its
    /// bytes, matching `put`), so the caller's transient buffer may be freed.
    pub fn putWire(
        self: *MemStore,
        hash: []const u8,
        container: []const u8,
    ) error{OutOfMemory}!Rid {
        std.debug.assert(container.len >= 4); // §4.1 — the container carries at least its 4-byte length prefix
        const rid = try internImpl(self, hash);
        const entry = self.entryOf(rid);
        // Content is addressed by hash: a repeat of the same hash carries the
        // same artifact, and §4.1 receivers are level-independent, so a
        // re-encoded container need not be byte-identical — keep the first.
        if (entry.wire != null) return rid;
        entry.wire = try self.gpa.dupe(u8, container);
        return rid;
    }

    /// Sync §7.2 delta form — store the already-encoded §4.1 `container` of a
    /// [FossilDelta] against `src_hash`, plus the reconstructed-target
    /// `target_size` (the cfile USIZE, delta §3.2), so a clone serves the delta
    /// form verbatim without re-encoding. Idempotent + phantom-upgrade like
    /// `putWire`; the plaintext materialises lazily against the basis on first
    /// `content()`. Duplicates both the container and `src_hash` (the store owns
    /// its bytes). Precondition: the basis is (or will be) stored under
    /// `src_hash` for `content()` to reconstruct — a serve snapshot inserts the
    /// basis at an earlier rid (loadContentStore's persisted order).
    pub fn putWireDelta(
        self: *MemStore,
        hash: []const u8,
        container: []const u8,
        src_hash: []const u8,
        target_size: u64,
    ) error{OutOfMemory}!Rid {
        std.debug.assert(container.len >= 4); // §4.1 — the container carries its 4-byte length prefix
        std.debug.assert(src_hash.len != 0);
        const rid = try internImpl(self, hash);
        const entry = self.entryOf(rid);
        // Content is addressed by hash: a repeat carries the same artifact.
        if (entry.wire != null or entry.bytes != null) return rid;
        const c = try self.gpa.dupe(u8, container);
        errdefer self.gpa.free(c);
        const s = try self.gpa.dupe(u8, src_hash);
        entry.wire = c;
        entry.wire_delta = .{ .src_hash = s, .target_size = target_size };
        return rid;
    }

    fn internImpl(context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid {
        const self: *MemStore = @ptrCast(@alignCast(context));
        std.debug.assert(hash.len != 0);
        if (self.by_hash.get(hash)) |rid| return rid;
        // New hash: create a phantom placeholder (Section 4.2 step 1).
        // Capacity is reserved before the map insert so a failure leaves no
        // partial entry behind.
        try self.entries.ensureUnusedCapacity(self.gpa, 1);
        const owned = try self.gpa.dupe(u8, hash);
        errdefer self.gpa.free(owned);
        const rid: Rid = self.entries.items.len + 1;
        try self.by_hash.put(self.gpa, owned, rid);
        self.entries.appendAssumeCapacity(.{ .hash = owned, .bytes = null });
        return rid;
    }

    fn putImpl(context: *anyopaque, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
        const self: *MemStore = @ptrCast(@alignCast(context));
        const rid = try internImpl(context, hash);
        const entry = self.entryOf(rid);
        if (entry.bytes) |existing| {
            // Content is addressed by hash: a repeat put carries identical
            // bytes, so upgrading twice is a no-op.
            std.debug.assert(std.mem.eql(u8, existing, content_bytes));
        } else {
            entry.bytes = try self.gpa.dupe(u8, content_bytes);
        }
        return rid;
    }

    fn contentImpl(context: *anyopaque, rid: Rid) ?[]const u8 {
        const self: *MemStore = @ptrCast(@alignCast(context));
        return self.materialize(rid);
    }

    /// The plaintext for `rid`: the memoised `bytes` if present, else — for a
    /// `wire`-backed entry — the stored §4.1 container inflated and memoised
    /// into `bytes` so the borrowed `[]const u8` `content()` contract holds
    /// (MemStore owns `bytes` until `deinit`). Returns null for a phantom (no
    /// `bytes`, no `wire`) and — since the vtable `content` cannot signal an
    /// error — for a container that fails to inflate (an OOM or, for a validated
    /// store, never-occurring corrupt frame). A null here is safe: every
    /// held/phantom classification on the correctness path treats an entry with
    /// a non-null `wire` as held via `wire()`, never re-deriving that fact from
    /// `content()`.
    fn materialize(self: *MemStore, rid: Rid) ?[]const u8 {
        return self.materializeDepth(rid, max_wire_delta_chain);
    }

    /// `materialize` with an explicit delta-chain depth bound. A delta-wire
    /// entry inflates its container to the raw [FossilDelta], resolves the basis
    /// by hash, materialises the basis (one depth deeper), and applies the delta
    /// — memoising the result. `depth == 0` on a delta entry yields null
    /// (chain too deep), never unbounded recursion.
    fn materializeDepth(self: *MemStore, rid: Rid, depth: usize) ?[]const u8 {
        const entry = self.entryOf(rid);
        if (entry.bytes) |b| return b;
        const container = entry.wire orelse return null;
        if (entry.wire_delta) |wd| {
            if (depth == 0) return null; // bounded: a chain deeper than the cap is unreconstructable here
            const raw = codec.decode(self.gpa, container, max_wire_payload) catch return null;
            defer self.gpa.free(raw);
            const src_rid = self.by_hash.get(wd.src_hash) orelse return null;
            const src = self.materializeDepth(src_rid, depth - 1) orelse return null;
            const plain = delta.apply(self.gpa, src, raw) catch return null;
            self.entryOf(rid).bytes = plain; // memoise; entries is not resized here, so the pointer is stable
            return plain;
        }
        const plain = codec.decode(self.gpa, container, max_wire_payload) catch return null;
        self.entryOf(rid).bytes = plain; // memoise; entries is not resized here, so the pointer is stable
        return plain;
    }

    /// Total memoised plaintext currently held across all entries, in bytes — a
    /// test/accounting probe. Zero when every entry is wire-backed or phantom
    /// (the clone-receive invariant: containers, not inflated history). Rises
    /// only as `content()` materialises plaintext or a raw `put` stores it.
    pub fn plaintextBytesHeld(self: *const MemStore) usize {
        var total: usize = 0;
        for (self.entries.items) |entry| {
            if (entry.bytes) |b| total += b.len;
        }
        return total;
    }

    fn wireImpl(context: *anyopaque, rid: Rid) ?WireFrame {
        const self: *MemStore = @ptrCast(@alignCast(context));
        const entry = self.entryOf(rid);
        const container = entry.wire orelse return null;
        if (entry.wire_delta) |wd| {
            return .{ .container = container, .delta = .{ .src_hash = wd.src_hash, .target_size = wd.target_size } };
        }
        return .{ .container = container };
    }

    fn hashOfImpl(context: *anyopaque, rid: Rid) []const u8 {
        const self: *MemStore = @ptrCast(@alignCast(context));
        return self.entryOf(rid).hash;
    }

    fn lookupImpl(context: *anyopaque, hash: []const u8) ?Rid {
        const self: *MemStore = @ptrCast(@alignCast(context));
        std.debug.assert(hash.len != 0);
        return self.by_hash.get(hash);
    }

    fn countImpl(context: *anyopaque) usize {
        const self: *MemStore = @ptrCast(@alignCast(context));
        return self.entries.items.len;
    }

    fn entryOf(self: *MemStore, rid: Rid) *Entry {
        std.debug.assert(rid >= 1 and rid <= self.entries.items.len);
        return &self.entries.items[@intCast(rid - 1)];
    }
};

/// The derived repository state: the check-in DAG (Section 3) and the leaf
/// table (Section 7), maintained by the crosslink procedure (Section 4.2).
/// Tag cross-references, branch membership, and name resolution build on
/// this next.
pub const RepoState = struct {
    gpa: std.mem.Allocator,
    store: ArtifactStore,
    /// Which representation answers the freed queries. `.derived` reads the
    /// hashmaps this struct builds via `crosslink` (the authoritative path);
    /// `.image` reads a pre-materialized `repoimage.Image` (a warm read with
    /// zero derivation). The public method set is identical in both — the tag
    /// is an internal implementation detail behind the same interface.
    backing: Backing = .derived,
    /// The loaded read-image, set only in `.image` backing. Its column windows
    /// borrow a buffer the owning `RepoView` keeps alive for this state's
    /// lifetime; the one owned allocation (widened leaf rids) is freed by
    /// `deinit`.
    img: ?repoimage.Image = null,
    /// One row per crosslinked check-in: rid to event mtime. Presence here
    /// is the Section 4.2 step 5 idempotency guard, and its key set is the
    /// leaf-candidate set (Section 7.3: every check-in, phantoms excluded).
    events: std.AutoArrayHashMapUnmanaged(Rid, Mtime) = .empty,
    /// Parent linkage rows, unique per (parent, child) pair (Section 3.1).
    plinks: std.AutoArrayHashMapUnmanaged(PlinkKey, PlinkRow) = .empty,
    /// The precomputed leaf table (Section 7.1): membership only, no
    /// open/closed metadata of its own.
    leaf_table: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
    /// Deferred leaf rechecks (Section 7.3), applied as a batch before the
    /// table is considered consistent.
    pending_leaf: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
    /// Tag cross-reference table (Section 5.2): at most one live row per
    /// (rid, tag) pair, enforced by keying the map on that pair directly.
    tagxref: std.AutoHashMapUnmanaged(TagKey, Xref) = .empty,
    /// User tag names interned to ids 10 and up (Section 2 reserves 8 and
    /// 9). Owns the duplicated name bytes.
    tag_names: std.StringHashMapUnmanaged(TagId) = .empty,
    next_tag: TagId = first_user_tag,
    /// Adjacency index over `plinks`, keyed by parent rid to its child edges,
    /// so the Section 7.2 same-branch-child test and the Section 5.4
    /// propagation walk cost O(out-degree) instead of a scan of every linkage
    /// row. `plinks` is append-only — exactly one row per (parent, child) pair,
    /// first write wins (Section 3.1) — so each edge is appended once here and
    /// never mutated or removed, which is what keeps the index a faithful
    /// mirror rather than a second source of truth.
    children: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(Edge)) = .empty,
    /// Adjacency index over `plinks`, keyed by child rid to its parent edges,
    /// so primary-parent lookup (Section 3.2), parent counting (Section 3.3),
    /// and leaf-recheck scheduling (Section 7.3) cost O(in-degree). Maintained
    /// in lockstep with `children` from the same append-only linkage rows.
    parents_by_child: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(Edge)) = .empty,
    /// Index over `tagxref`, keyed by rid to the tag ids that currently have a
    /// live row on it, so the Section 4.2 step 4a re-propagation snapshots one
    /// rid's rows in O(its tag count) rather than iterating the whole table. It
    /// is kept exactly precise — a tag is added the instant its (rid, tag) row
    /// is first created and removed the instant that row is deleted — so a
    /// listed tag always resolves to a live `tagxref` row.
    rid_tags: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(TagId)) = .empty,

    /// One adjacency edge: the rid at the other end of a linkage row, plus that
    /// row's Section 3.2 primary indicator. In `children` the rid is the child;
    /// in `parents_by_child` it is the parent.
    const Edge = struct {
        rid: Rid,
        is_primary: bool,
    };

    const PlinkKey = struct {
        parent: Rid,
        child: Rid,
    };

    const PlinkRow = struct {
        /// Set on exactly the row for the first parent listed (Section 3.2).
        is_primary: bool,
        /// The child check-in's modification time (Section 3.1).
        mtime: Mtime,
        /// Delta-manifest baseline id (Section 3.1); resolved once the
        /// manifest adapter supplies B-card linkage.
        baseline: Rid,
    };

    /// Interned tag identifier (Section 2): a fixed small integer per name,
    /// with 8 ("branch") and 9 ("closed") reserved and every other name
    /// interned starting at 10.
    const TagId = u32;
    const branch_tag_id: TagId = 8;
    const closed_tag_id: TagId = 9;
    const first_user_tag: TagId = 10;
    const default_branch = "trunk";

    const TagKey = struct {
        rid: Rid,
        tag: TagId,
    };

    /// One tagxref row (Section 5.2).
    const Xref = struct {
        tagtype: TagType,
        /// The artifact whose T-card directly applied the tag, or zero when
        /// the row instead reflects a value propagated in from an ancestor.
        srcid: Rid,
        /// The artifact that originally holds the propagating tag.
        origid: Rid,
        /// Owned duplicate of the tag's value payload, or null.
        value: ?[]u8,
        mtime: Mtime,
    };

    /// The representation backing the freed query methods.
    pub const Backing = enum { derived, image };

    /// One materialized §8.2 resolution: a live symbolic name and the rid
    /// `resolveName` selects for it. `name` borrows the interned tag-name bytes.
    pub const ResolvedSymbol = struct {
        name: []const u8,
        rid: Rid,
    };

    pub fn init(gpa: std.mem.Allocator, artifact_store: ArtifactStore) RepoState {
        return .{ .gpa = gpa, .store = artifact_store };
    }

    /// A read-image-backed state: the freed queries read `image`'s columns and
    /// no derivation runs. `store` is a caller-supplied empty store (the image
    /// serves hashes/lookups); the cold, non-freed methods must not be called
    /// in this backing (asserted). The image's column windows must outlive the
    /// returned state.
    pub fn fromImage(gpa: std.mem.Allocator, artifact_store: ArtifactStore, image: repoimage.Image) RepoState {
        return .{ .gpa = gpa, .store = artifact_store, .backing = .image, .img = image };
    }

    pub fn deinit(self: *RepoState) void {
        if (self.img) |*img| img.deinit(self.gpa);
        var xit = self.tagxref.valueIterator();
        while (xit.next()) |xr| {
            if (xr.value) |v| self.gpa.free(v);
        }
        self.tagxref.deinit(self.gpa);
        var nit = self.tag_names.keyIterator();
        while (nit.next()) |name| self.gpa.free(name.*);
        self.tag_names.deinit(self.gpa);
        self.events.deinit(self.gpa);
        self.plinks.deinit(self.gpa);
        for (self.children.values()) |*list| list.deinit(self.gpa);
        self.children.deinit(self.gpa);
        for (self.parents_by_child.values()) |*list| list.deinit(self.gpa);
        self.parents_by_child.deinit(self.gpa);
        for (self.rid_tags.values()) |*list| list.deinit(self.gpa);
        self.rid_tags.deinit(self.gpa);
        self.leaf_table.deinit(self.gpa);
        self.pending_leaf.deinit(self.gpa);
        self.* = undefined;
    }

    /// Crosslink one check-in record (Section 4.2): intern its hash, derive
    /// its linkage rows with parents interned to phantoms when absent
    /// (step 1), route its T-cards into direct application and propagation
    /// (steps 2-4), re-propagate the primary parent's tag state so a fresh
    /// child inherits it (step 4a), and apply the batch of deferred leaf
    /// rechecks (Section 7.3). Linkage derivation is idempotent (step 5): a
    /// rid that already has an event row keeps its existing linkage, but
    /// tag application and propagation still run on every call. Content
    /// type is not carried by `Record` yet, so the step 2 applicability
    /// gate and the step 3 cluster path are not reachable here — every
    /// record is treated as control/manifest, matching the only kind this
    /// layer produces. Only allocation can fail.
    pub fn crosslink(self: *RepoState, rec: Record) error{OutOfMemory}!Rid {
        std.debug.assert(self.backing == .derived); // an image is read-only; deriving into it is a bug
        std.debug.assert(rec.hash.len != 0);
        const rid = try self.store.intern(rec.hash);
        const linkage_new = !self.events.contains(rid);
        if (linkage_new) {
            try self.events.put(self.gpa, rid, rec.mtime);
            for (rec.parents, 0..) |parent_hash, i| {
                std.debug.assert(parent_hash.len != 0);
                const parent = try self.store.intern(parent_hash);
                // A manifest cannot name its own hash as a parent: the hash
                // covers the manifest's content, including its P card.
                std.debug.assert(parent != rid);
                const gop = try self.plinks.getOrPut(self.gpa, .{ .parent = parent, .child = rid });
                if (!gop.found_existing) {
                    // Section 3.1: a repeated parent reference collapses
                    // into the single row for the pair, first wins.
                    gop.value_ptr.* = .{ .is_primary = i == 0, .mtime = rec.mtime, .baseline = 0 };
                    // Mirror the new linkage row into both adjacency indexes.
                    try self.indexPlink(parent, rid, i == 0);
                }
            }
            // Section 7.3: a new parent-link schedules a recheck of the
            // affected check-in and each of its direct parents.
            try self.scheduleLeafRecheck(rid);
        }
        // Section 4.2 steps 1-4: apply each T-card directly, then propagate
        // propagating and cancel effects from their resolved targets.
        try self.applyTagOps(rid, rec.mtime, rec.tags);
        // Section 4.2 step 4a: re-propagate the primary parent's tag set so
        // a newly linked child inherits it regardless of arrival order.
        if (self.primaryParentOf(rid)) |parent| {
            try self.repropagateSet(parent);
        }
        try self.applyPendingLeafChecks();
        const post = self.events.count();
        std.debug.assert(post >= 1 and self.pending_leaf.count() == 0);
        return rid;
    }

    /// Ingest the direct and propagated T-card effects of a control artifact.
    /// The control carrier is interned solely to preserve its source identity:
    /// it never gains an event, parent-link, or leaf-table entry. Scheduled
    /// rechecks update only the affected, already-crosslinked check-ins.
    pub fn ingestControlTags(self: *RepoState, control_hash: []const u8, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!Rid {
        std.debug.assert(self.backing == .derived);
        std.debug.assert(control_hash.len != 0);
        const carrier = try self.store.intern(control_hash);
        try self.applyTagOps(carrier, mtime, tags);
        try self.applyPendingLeafChecks();
        return carrier;
    }

    /// Section 4.2 steps 1-4: apply each T-card directly, then, for a
    /// propagating or cancel type, walk the propagation from the resolved
    /// target using the row's own post-application state (so a Section 5.3
    /// skip still re-walks the winning value rather than the losing one).
    fn applyTagOps(self: *RepoState, carrier: Rid, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!void {
        for (tags) |op| {
            const target = if (op.target) |uuid| try self.store.intern(uuid) else carrier;
            try self.applyDirect(target, op, carrier, mtime);
            if (op.type != .singleton) {
                const tag = try self.internTag(op.name);
                const stored = self.tagxref.get(.{ .rid = target, .tag = tag });
                std.debug.assert(stored != null);
                // Section 5.4: a singleton driving propagation is always
                // downgraded to cancel first; the stored row can only be
                // singleton here if a later-mtime direct write elsewhere
                // won the Section 5.3 skip over this op's own effect.
                const pt: TagType = if (stored.?.tagtype == .singleton) .cancel else stored.?.tagtype;
                try self.propagate(target, tag, pt, stored.?.value, stored.?.origid, stored.?.mtime);
            }
        }
    }

    /// Whether `rid` is a leaf, answered from the precomputed leaf table
    /// (Section 7.1).
    pub fn isLeaf(self: *const RepoState, rid: Rid) bool {
        if (self.img) |*img| return img.isLeaf(rid);
        return self.leaf_table.contains(rid);
    }

    /// Whether `rid` is an open leaf (Section 7.4): a member of the leaf
    /// table that does not carry an active closed tag.
    pub fn isOpenLeaf(self: *const RepoState, rid: Rid) bool {
        if (self.img) |*img| return img.isOpenLeaf(rid);
        return self.isLeaf(rid) and !self.hasActiveClosed(rid);
    }

    /// Iterate the leaf table (Section 7.1). Invalidated by any mutation of
    /// the repository state.
    pub fn leaves(self: *const RepoState) LeafIterator {
        if (self.img) |*img| return .{ .rids = img.leafRids() };
        return .{ .rids = self.leaf_table.keys() };
    }

    /// Recompute the entire leaf table from scratch (Section 7.3 full
    /// rebuild): every check-in is a candidate — roots included — and is a
    /// leaf exactly when it has no same-branch child, with no
    /// primary/merge filter. Whole-table cost; reserved for explicit
    /// rebuilds rather than routine updates.
    pub fn rebuildLeaves(self: *RepoState) error{OutOfMemory}!void {
        self.leaf_table.clearRetainingCapacity();
        for (self.events.keys()) |rid| {
            if (!self.hasSameBranchChild(rid)) {
                try self.leaf_table.put(self.gpa, rid, {});
            }
        }
    }

    /// Record one linkage row in both adjacency indexes: `child` under
    /// `parent` in `children`, and `parent` under `child` in
    /// `parents_by_child`. Called exactly once per newly created `plinks` row,
    /// so no edge is ever duplicated.
    fn indexPlink(self: *RepoState, parent: Rid, child: Rid, is_primary: bool) error{OutOfMemory}!void {
        std.debug.assert(parent != child);
        const cg = try self.children.getOrPut(self.gpa, parent);
        if (!cg.found_existing) cg.value_ptr.* = .empty;
        try cg.value_ptr.append(self.gpa, .{ .rid = child, .is_primary = is_primary });
        const pg = try self.parents_by_child.getOrPut(self.gpa, child);
        if (!pg.found_existing) pg.value_ptr.* = .empty;
        try pg.value_ptr.append(self.gpa, .{ .rid = parent, .is_primary = is_primary });
    }

    /// Record that `rid` now carries a live `tagxref` row for `tag`. Called
    /// only when a (rid, tag) row transitions from absent to present, so a tag
    /// is never listed twice for one rid (asserted in safe builds).
    fn addRidTag(self: *RepoState, rid: Rid, tag: TagId) error{OutOfMemory}!void {
        const gop = try self.rid_tags.getOrPut(self.gpa, rid);
        if (!gop.found_existing) gop.value_ptr.* = .empty;
        if (std.debug.runtime_safety) {
            for (gop.value_ptr.items) |existing| std.debug.assert(existing != tag);
        }
        try gop.value_ptr.append(self.gpa, tag);
    }

    /// Drop `tag` from `rid`'s tag list when its `tagxref` row is removed. The
    /// row is unique per (rid, tag), so exactly one entry matches; a caller
    /// only reaches here for a row that existed, so the list is non-null.
    fn removeRidTag(self: *RepoState, rid: Rid, tag: TagId) void {
        const list = self.rid_tags.getPtr(rid) orelse return;
        for (list.items, 0..) |listed, i| {
            if (listed == tag) {
                _ = list.swapRemove(i);
                return;
            }
        }
    }

    /// The number of distinct parents of `child` (Section 3.3
    /// child-to-parent lookup); merge parents included.
    pub fn parentCount(self: *const RepoState, child: Rid) usize {
        if (self.parents_by_child.getPtr(child)) |list| return list.items.len;
        return 0;
    }

    /// The primary parent of `child` (Section 3.2), or null for a root or
    /// an unknown rid. At most one linkage row per child carries the
    /// primary indicator.
    pub fn primaryParentOf(self: *const RepoState, child: Rid) ?Rid {
        if (self.parents_by_child.getPtr(child)) |list| {
            for (list.items) |e| {
                if (e.is_primary) return e.rid;
            }
        }
        return null;
    }

    /// Iterate the parents of a child (Section 3.3 child-to-parent lookup):
    /// the primary parent and every merge parent alike, in linkage-row order.
    /// Section 3.1 keeps one linkage row per (parent, child) pair, so each
    /// parent is yielded exactly once. Invalidated by any RepoState mutation.
    pub const ParentIterator = struct {
        edges: []const Edge,
        i: usize = 0,

        pub fn next(self: *ParentIterator) ?Rid {
            // Bounded by the in-degree; each step strictly advances i.
            if (self.i >= self.edges.len) return null;
            const e = self.edges[self.i];
            self.i += 1;
            return e.rid;
        }
    };

    /// The parents of `child` (Section 3.3): a general-purpose iterator over
    /// its linkage rows, primary and merge alike. A root — or an unknown rid —
    /// yields nothing. Closed set: returns rids only, never an error.
    pub fn parentsOf(self: *const RepoState, child: Rid) ParentIterator {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
        const edges: []const Edge = if (self.parents_by_child.getPtr(child)) |list| list.items else &.{};
        return .{ .edges = edges };
    }

    /// The event mtime recorded for a crosslinked check-in, or null when
    /// `rid` has no event row (a phantom, or never crosslinked).
    pub fn mtimeOf(self: *const RepoState, rid: Rid) ?Mtime {
        if (self.img) |*img| return img.mtimeOf(rid);
        return self.events.get(rid);
    }

    /// A check-in's branch (Section 6.1): the value of its active
    /// (tagtype > 0) branch tag, or `main_branch` when no such tag is in
    /// effect (Section 6.4's active-tag filter applies uniformly — a
    /// cancelled branch tag falls back exactly like a missing one). The
    /// default-branch name is a repository-local setting, so the caller
    /// supplies it rather than this layer assuming a fixed string.
    pub fn branchOf(self: *const RepoState, rid: Rid, main_branch: []const u8) []const u8 {
        std.debug.assert(main_branch.len != 0);
        if (self.img) |*img| return img.branchOf(rid, main_branch);
        std.debug.assert(self.events.contains(rid));
        const result = self.activeBranchValue(rid) orelse main_branch;
        std.debug.assert(result.len != 0);
        return result;
    }

    /// Resolve a plain symbolic name (Section 8.1/8.2): the check-in
    /// carrying an active "sym-<name>" tag with the greatest event.mtime.
    /// Closed-ness and leaf-ness of a candidate are not inputs to this
    /// selection (Section 8.2's two MUST-NOT clauses). Selection keys on
    /// each candidate's own event.mtime, not the tagxref row's stored
    /// mtime: a row a candidate inherited by propagation carries its
    /// origin's application mtime, but the inheriting check-in can itself
    /// be newer or older than that origin.
    pub fn resolveName(self: *const RepoState, name: []const u8) error{NotFound}!Rid {
        std.debug.assert(name.len != 0);
        if (self.img) |*img| return img.resolveName(name) orelse error.NotFound;
        const sym_id = self.symTagId(name) orelse return error.NotFound;
        var best: ?Rid = null;
        var best_mtime: Mtime = undefined;
        var it = self.tagxref.iterator();
        var scanned: usize = 0;
        const bound = self.tagxref.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (entry.key_ptr.tag != sym_id or entry.value_ptr.tagtype == .cancel) continue;
            const rid = entry.key_ptr.rid;
            // A tag row can sit on a phantom that has not itself been
            // crosslinked yet (Section 4.2 step 1); it has no event.mtime
            // and so is not a resolvable candidate.
            const mtime = self.events.get(rid) orelse continue;
            if (best == null or mtime > best_mtime) {
                best = rid;
                best_mtime = mtime;
            }
        }
        const result = best orelse return error.NotFound;
        std.debug.assert(self.events.contains(result));
        return result;
    }

    /// Current-trunk (Section 9; Section 2 "Current-trunk"): resolve the
    /// repository's configured default branch name. The procedure applies
    /// uniformly — the default branch is not special-cased beyond supplying
    /// its name.
    pub fn currentTrunk(self: *const RepoState, main_branch: []const u8) error{NotFound}!Rid {
        std.debug.assert(main_branch.len != 0);
        return self.resolveName(main_branch);
    }

    /// A branch's open leaf (Section 9): among check-ins that (a) carry an
    /// active branch tag whose value equals `branch`, (b) are members of
    /// the leaf table, and (c) do not carry an active closed tag, the one
    /// with the greatest event.mtime — or null when no check-in qualifies.
    /// Condition (a) uses the active branch tag strictly: a tagless
    /// check-in attributed to `branch` only through the Section 6.4
    /// default-branch fallback does not qualify (Section 6.1: the fallback
    /// "does not by itself make such a check-in ... the open leaf ... of
    /// that branch").
    pub fn openLeafOf(self: *const RepoState, branch: []const u8) ?Rid {
        std.debug.assert(branch.len != 0);
        var best: ?Rid = null;
        var best_mtime: Mtime = undefined;
        var scanned: usize = 0;
        const bound = self.leaf_table.count();
        for (self.leaf_table.keys()) |rid| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            const value = self.activeBranchValue(rid) orelse continue;
            if (!std.mem.eql(u8, value, branch)) continue;
            if (self.hasActiveClosed(rid)) continue;
            std.debug.assert(self.events.contains(rid)); // leaf_table rids are always check-ins
            const mtime = self.events.get(rid).?;
            if (best == null or mtime > best_mtime) {
                best = rid;
                best_mtime = mtime;
            }
        }
        if (best) |result| {
            std.debug.assert(self.isLeaf(result) and !self.hasActiveClosed(result));
            std.debug.assert(std.mem.eql(u8, self.activeBranchValue(result).?, branch));
        }
        return best;
    }

    /// A name-resolution request's target shape (Section 8.1). This layer
    /// models only check-ins — Section 8.3's other reserved keywords
    /// (current/prev/next/ckout) need an open local checkout, out of scope
    /// for an artifact-derived layer — so `checkin` is the RFC's
    /// unconstrained-or-"ci" request and `branch` is a "b*" request, routed
    /// through the branch-walk post-process to the branch's first check-in.
    pub const NameType = enum { checkin, branch };

    /// One Section 6.3 derived branch-listing row. `name` borrows the
    /// underlying tagxref value bytes and is valid only until the next
    /// `RepoState` mutation frees or overwrites that row.
    pub const BranchEntry = struct {
        name: []const u8,
        tip: Rid,
        mtime: Mtime,
        count: usize,
        closed: bool,
    };

    /// One active tag row surfaced for a check-in (Section 5.1/5.2). `name`
    /// is the raw interned tag name — the "branch"/"closed" reserved literals
    /// (Section 2) or a user key; `value` borrows the tagxref row's stored
    /// payload (null when the row carries none, Section 5.2). Valid only until
    /// the next `RepoState` mutation — the same lifetime contract as
    /// `BranchEntry`.
    pub const TagEntry = struct {
        name: []const u8,
        tagtype: TagType,
        value: ?[]const u8,
    };

    const WalkVariant = enum { earliest_on_branch, first_off_branch };
    const TimestampMode = enum { upper_bound, direct };

    /// Section 8.3 symbolic-name resolution: dispatch the ordered forms,
    /// retry once on trailing punctuation, then — for a branch-type
    /// request — post-process through the branch-walk's "earliest still on
    /// branch" variant (Section 8.3's final paragraph) so the result is the
    /// branch's first check-in rather than wherever the tag currently
    /// points. Allocation-free.
    pub fn resolve(self: *const RepoState, name: []const u8, want: NameType) error{ NotFound, Ambiguous }!Rid {
        std.debug.assert(name.len >= 1);
        const rid = try self.dispatchWithRetry(name);
        std.debug.assert(self.events.contains(rid));
        const result = if (want == .branch) self.branchWalk(rid, .earliest_on_branch) else rid;
        std.debug.assert(self.events.contains(result));
        return result;
    }

    /// Section 8.3 dispatch: the ordered forms, committing to whichever
    /// prefix or shape matches first. A matched prefix that fails its own
    /// validation (an unknown rid:, an empty tag:, a malformed date) is
    /// rejected outright rather than falling through to a later form.
    fn dispatch(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
        std.debug.assert(name.len >= 1);
        if (std.mem.startsWith(u8, name, "rid:")) return self.ridForm(name[4..]);
        if (std.mem.startsWith(u8, name, "tag:")) {
            const rest = name[4..];
            if (rest.len == 0) return error.NotFound;
            return self.resolveName(rest);
        }
        if (std.mem.eql(u8, name, "tip")) return self.tipForm();
        if (std.mem.startsWith(u8, name, "root:")) return self.branchDerivedForm(name[5..], .first_off_branch);
        if (std.mem.startsWith(u8, name, "start:")) return self.branchDerivedForm(name[6..], .earliest_on_branch);
        if (std.mem.startsWith(u8, name, "merge-in:")) return self.branchDerivedForm(name[9..], .first_off_branch);
        if (std.mem.startsWith(u8, name, "date:")) return self.dateForm(name[5..], .upper_bound);
        if (std.mem.startsWith(u8, name, "utc:")) return self.dateForm(name[4..], .upper_bound);
        if (std.mem.startsWith(u8, name, "local:")) return self.dateForm(name[6..], .direct);
        if (expandTimestamp(name, .upper_bound)) |bound_ms| {
            return self.dateResolve(bound_ms) orelse error.NotFound;
        }
        if (isHexPrefixShape(name)) {
            if (try self.hashPrefixMatch(name)) |rid| return rid;
            // 0 matches: not a hash after all — fall through to the plain rule.
        }
        return self.resolveName(name);
    }

    /// Section 8.3 trailing-punctuation retry, wrapping `dispatch`: on
    /// `NotFound` only (an `Ambiguous` rejection is never retried), strip
    /// exactly one trailing punctuation byte and recurse. Bounded: the
    /// slice strictly shrinks by one byte per retry, so the recursion depth
    /// cannot exceed the initial length.
    fn dispatchWithRetry(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
        std.debug.assert(name.len >= 1);
        return self.dispatch(name) catch |err| {
            if (err == error.Ambiguous) return err;
            if (!isPunctChar(name[name.len - 1])) return error.NotFound;
            const stripped = name[0 .. name.len - 1];
            std.debug.assert(stripped.len < name.len);
            if (stripped.len == 0) return error.NotFound;
            return self.dispatchWithRetry(stripped);
        };
    }

    /// Section 8.3 form 1: a numeric rid, valid only when it names a
    /// crosslinked check-in.
    fn ridForm(self: *const RepoState, digits: []const u8) error{NotFound}!Rid {
        if (digits.len == 0) return error.NotFound;
        const rid = std.fmt.parseInt(Rid, digits, 10) catch return error.NotFound;
        if (!self.events.contains(rid)) return error.NotFound;
        return rid;
    }

    /// Section 8.3 form 3 (tip only; current/prev/next/ckout need an open
    /// local checkout, out of scope here): the check-in with the global
    /// maximum event.mtime.
    fn tipForm(self: *const RepoState) error{NotFound}!Rid {
        var best: ?Rid = null;
        var best_mtime: Mtime = undefined;
        var scanned: usize = 0;
        const bound = self.events.count();
        for (self.events.keys(), self.events.values()) |rid, mtime| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (best == null or mtime > best_mtime) {
                best = rid;
                best_mtime = mtime;
            }
        }
        return best orelse error.NotFound;
    }

    /// Section 8.3 forms 4-6: resolve `br` through the full procedure, then
    /// rewrite via the Section 8.4 branch-walk.
    fn branchDerivedForm(self: *const RepoState, br: []const u8, variant: WalkVariant) error{ NotFound, Ambiguous }!Rid {
        if (br.len == 0) return error.NotFound;
        const base = try self.resolve(br, .checkin);
        return self.branchWalk(base, variant);
    }

    /// Section 8.4 branch-walk: from `start`, follow the primary-parent
    /// chain toward the root, tracking whether each ancestor still carries
    /// the same branch identity as `start` (Section 6.1's branch-of-check-
    /// in notion, default-branch fallback included — the walk needs a
    /// branch value at every step, and an untagged check-in's branch is
    /// still well-defined via that fallback). `.earliest_on_branch` returns
    /// the deepest ancestor that still carries it; `.first_off_branch`
    /// returns the first ancestor that dropped it. A primary-parent chain
    /// that never leaves the branch (a root-only branch) has no such node
    /// for `.first_off_branch`; both variants then fall back to the
    /// deepest ancestor reached (documented edge case). A primary parent
    /// that is only a phantom (not yet crosslinked, Section 4.2 step 1)
    /// halts the walk there too: it is not yet a resolvable check-in, so
    /// its branch identity is unresolved rather than "off branch".
    fn branchWalk(self: *const RepoState, start: Rid, variant: WalkVariant) Rid {
        std.debug.assert(self.events.contains(start));
        const target = self.branchValueOf(start);
        var cur = start;
        var steps: usize = 0;
        const bound = self.events.count();
        while (self.primaryParentOf(cur)) |parent| {
            if (!self.events.contains(parent)) break;
            steps += 1;
            std.debug.assert(steps <= bound);
            const pbranch = self.branchValueOf(parent);
            if (!std.mem.eql(u8, pbranch, target)) {
                if (variant == .first_off_branch) return parent;
                return cur;
            }
            cur = parent;
        }
        return cur;
    }

    /// Section 8.3 form 7: parse `text` to an upper-bound millisecond
    /// timestamp (or pass it through directly for the deprecated `local:`
    /// form) and select the most recent qualifying event.
    fn dateForm(self: *const RepoState, text: []const u8, mode: TimestampMode) error{NotFound}!Rid {
        const bound_ms = expandTimestamp(text, mode) orelse return error.NotFound;
        return self.dateResolve(bound_ms) orelse error.NotFound;
    }

    /// Section 8.3 form 7 selection: the check-in with the greatest
    /// event.mtime not exceeding `bound_ms`, on the millisecond timeline
    /// documented on `Mtime`.
    fn dateResolve(self: *const RepoState, bound_ms: u64) ?Rid {
        var best: ?Rid = null;
        var best_mtime: Mtime = undefined;
        var scanned: usize = 0;
        const bound = self.events.count();
        for (self.events.keys(), self.events.values()) |rid, mtime| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (mtime > bound_ms) continue;
            if (best == null or mtime > best_mtime) {
                best = rid;
                best_mtime = mtime;
            }
        }
        return best;
    }

    /// Section 8.3 form 8: match `prefix` against crosslinked check-ins'
    /// content hashes (phantoms excluded — this layer resolves names to
    /// check-ins). More than one match is rejected as ambiguous (the
    /// section's "-1" sentinel does not apply to an unsigned `Rid`;
    /// `error.Ambiguous` is the equivalent outcome for this layer).
    fn hashPrefixMatch(self: *const RepoState, prefix: []const u8) error{Ambiguous}!?Rid {
        std.debug.assert(prefix.len >= 4 and prefix.len <= 64);
        var match: ?Rid = null;
        var count: usize = 0;
        var scanned: usize = 0;
        const bound = self.events.count();
        for (self.events.keys()) |rid| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            const hash = self.store.hashOf(rid);
            if (hash.len >= prefix.len and std.mem.eql(u8, hash[0..prefix.len], prefix)) {
                match = rid;
                count += 1;
            }
        }
        if (count > 1) return error.Ambiguous;
        return match;
    }

    /// Section 6.3 derived branch listing: group active branch-tag rows
    /// (`tagtype > 0`) by value, one entry per distinct value with its
    /// greatest-mtime member as representative. Sorted by name ascending
    /// (presentation order; callers wanting Section 6.3's other listed
    /// orderings re-sort). Caller frees the returned slice.
    pub fn branches(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]BranchEntry {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
        const Group = struct { tip: Rid, mtime: Mtime, count: usize };
        var groups: std.StringHashMapUnmanaged(Group) = .empty;
        defer groups.deinit(gpa);
        var it = self.tagxref.iterator();
        var scanned: usize = 0;
        const bound = self.tagxref.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (entry.key_ptr.tag != branch_tag_id or entry.value_ptr.tagtype == .cancel) continue;
            const rid = entry.key_ptr.rid;
            const mtime = self.events.get(rid) orelse continue; // tag on a still-phantom target
            const value = entry.value_ptr.value orelse continue; // a branch tag always carries a value
            const gop = try groups.getOrPut(gpa, value);
            if (!gop.found_existing) {
                gop.value_ptr.* = .{ .tip = rid, .mtime = mtime, .count = 1 };
            } else {
                gop.value_ptr.count += 1;
                if (mtime > gop.value_ptr.mtime) {
                    gop.value_ptr.tip = rid;
                    gop.value_ptr.mtime = mtime;
                }
                // Exact-mtime tie: keep the first-seen representative —
                // implementation-defined per Section 8.2's own tie note.
            }
        }
        var out: std.ArrayList(BranchEntry) = .empty;
        errdefer out.deinit(gpa);
        var kit = groups.iterator();
        var kscanned: usize = 0;
        const kbound = groups.count();
        while (kit.next()) |g| {
            kscanned += 1;
            std.debug.assert(kscanned <= kbound);
            std.debug.assert(self.events.contains(g.value_ptr.tip));
            std.debug.assert(std.mem.eql(u8, self.activeBranchValue(g.value_ptr.tip).?, g.key_ptr.*));
            try out.append(gpa, .{
                .name = g.key_ptr.*,
                .tip = g.value_ptr.tip,
                .mtime = g.value_ptr.mtime,
                .count = g.value_ptr.count,
                .closed = self.hasActiveClosed(g.value_ptr.tip),
            });
        }
        const slice = try out.toOwnedSlice(gpa);
        std.mem.sort(BranchEntry, slice, {}, branchNameLessThan);
        return slice;
    }

    fn branchNameLessThan(_: void, a: BranchEntry, b: BranchEntry) bool {
        return std.mem.order(u8, a.name, b.name) == .lt;
    }

    /// Section 5.1/5.2/6.4: the active tags on `rid`, each with its stored
    /// value payload, sorted by raw tag name ascending. A tag reference is
    /// active iff its tagtype is greater than zero (Section 5.1/Section 2);
    /// a cancel row (tagtype 0, surface `-`) is inactive by definition and is
    /// excluded, so every returned entry has `tagtype != .cancel`. The
    /// tagxref keying (Section 5.2's UNIQUE (rid, tag)) guarantees at most one
    /// live row per (rid, tag), so each tag name appears at most once. Caller
    /// frees the returned slice; the borrowed name/value bytes are valid until
    /// the next `RepoState` mutation.
    pub fn tagsOf(self: *const RepoState, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]TagEntry {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
        std.debug.assert(rid >= 1);
        var out: std.ArrayList(TagEntry) = .empty;
        errdefer out.deinit(gpa);
        var it = self.tagxref.iterator();
        var scanned: usize = 0;
        const bound = self.tagxref.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (entry.key_ptr.rid != rid) continue;
            if (entry.value_ptr.tagtype == .cancel) continue; // Section 5.1: inactive
            try out.append(gpa, .{
                .name = self.tagNameOf(entry.key_ptr.tag),
                .tagtype = entry.value_ptr.tagtype,
                .value = entry.value_ptr.value,
            });
        }
        const slice = try out.toOwnedSlice(gpa);
        std.mem.sort(TagEntry, slice, {}, tagNameLessThan);
        // Section 5.1 postcondition: every surfaced row is active (positive +
        // negative space), and the listing is name-ascending with distinct
        // names (the (rid, tag) UNIQUE constraint, Section 5.2).
        for (slice, 0..) |e, i| {
            std.debug.assert(e.tagtype != .cancel);
            if (i + 1 < slice.len) std.debug.assert(std.mem.order(u8, e.name, slice[i + 1].name) == .lt);
        }
        return slice;
    }

    /// Section 5.1/6.4 (+ Section 4.2 step 1 phantom exclusion): the distinct
    /// active tag names in use anywhere. A name appears iff some crosslinked
    /// check-in holds an active (tagtype > 0) row for it; a row sitting on a
    /// not-yet-arrived phantom target (Section 4.2 step 1) does not count —
    /// it becomes visible once the referenced artifact is crosslinked. Names
    /// are raw: the "branch"/"closed" reserved literals and reserved-prefix
    /// names (Section 2) are included, and the caller decides which are
    /// user-facing. Sorted ascending. Names borrow interned bytes; caller
    /// frees the returned slice.
    pub fn tagNames(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![][]const u8 {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
        var ids: std.AutoHashMapUnmanaged(TagId, void) = .empty;
        defer ids.deinit(gpa);
        var it = self.tagxref.iterator();
        var scanned: usize = 0;
        const bound = self.tagxref.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (entry.value_ptr.tagtype == .cancel) continue; // Section 5.1: inactive
            if (!self.events.contains(entry.key_ptr.rid)) continue; // Section 4.2 step 1: phantom
            try ids.put(gpa, entry.key_ptr.tag, {});
        }
        var out: std.ArrayList([]const u8) = .empty;
        errdefer out.deinit(gpa);
        var kit = ids.keyIterator();
        var kscanned: usize = 0;
        const kbound = ids.count();
        while (kit.next()) |id| {
            kscanned += 1;
            std.debug.assert(kscanned <= kbound);
            try out.append(gpa, self.tagNameOf(id.*));
        }
        const slice = try out.toOwnedSlice(gpa);
        std.mem.sort([]const u8, slice, {}, nameLessThan);
        // Distinct by construction (deduped by tag id); the sort makes the
        // distinctness invariant adjacency-checkable.
        for (slice, 0..) |name, i| {
            if (i + 1 < slice.len) std.debug.assert(!std.mem.eql(u8, name, slice[i + 1]));
        }
        return slice;
    }

    fn tagNameLessThan(_: void, a: TagEntry, b: TagEntry) bool {
        return std.mem.order(u8, a.name, b.name) == .lt;
    }

    fn nameLessThan(_: void, a: []const u8, b: []const u8) bool {
        return std.mem.order(u8, a, b) == .lt;
    }

    /// Section 7.5 ambiguity test: `rid` is a leaf and at least one *other*
    /// open leaf shares its branch (the canonical leaf test's own default-
    /// branch-inclusive same-branch comparison). Non-leaf short-circuits to
    /// false per the section's first MUST.
    pub fn isAmbiguousLeaf(self: *const RepoState, rid: Rid) bool {
        if (!self.isLeaf(rid)) return false;
        var scanned: usize = 0;
        const bound = self.leaf_table.count();
        for (self.leaf_table.keys()) |other| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (other == rid) continue;
            if (!self.isOpenLeaf(other)) continue;
            if (self.sameBranch(rid, other)) return true;
        }
        return false;
    }

    const MtimeDescCtx = struct {
        rs: *const RepoState,

        fn lessThan(ctx: MtimeDescCtx, a: Rid, b: Rid) bool {
            return ctx.rs.mtimeOf(a).? > ctx.rs.mtimeOf(b).?;
        }
    };

    /// Section 7.5 SHOULD reporting: every open leaf of `branch` (the
    /// strict active-tag membership `openLeafOf` also uses — a tagless
    /// check-in attributed to `branch` only through the default-branch
    /// fallback does not qualify), ordered by event.mtime descending.
    /// Exact-mtime ties are implementation-defined, per Section 8's own
    /// tie note. Caller frees the returned slice.
    pub fn openLeavesOf(self: *const RepoState, gpa: std.mem.Allocator, branch: []const u8) error{OutOfMemory}![]Rid {
        std.debug.assert(branch.len != 0);
        var out: std.ArrayList(Rid) = .empty;
        errdefer out.deinit(gpa);
        var scanned: usize = 0;
        const bound = self.leaf_table.count();
        for (self.leaf_table.keys()) |rid| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (self.hasActiveClosed(rid)) continue;
            const value = self.activeBranchValue(rid) orelse continue;
            if (!std.mem.eql(u8, value, branch)) continue;
            try out.append(gpa, rid);
        }
        const slice = try out.toOwnedSlice(gpa);
        std.mem.sort(Rid, slice, MtimeDescCtx{ .rs = self }, MtimeDescCtx.lessThan);
        for (slice) |rid| {
            std.debug.assert(self.isOpenLeaf(rid));
            std.debug.assert(std.mem.eql(u8, self.activeBranchValue(rid).?, branch));
        }
        return slice;
    }

    /// Total order over the whole check-in universe for the timeline listing:
    /// event.mtime descending (Section 2 / Section 8.3 item 7 — the ordering
    /// clock), exact-mtime ties broken by ascending full artifact hash so the
    /// order is total and deterministic. Kept separate from `MtimeDescCtx`, whose
    /// ties are impl-defined; here the tiebreak is load-bearing.
    const TimelineOrderCtx = struct {
        rs: *const RepoState,

        fn lessThan(ctx: TimelineOrderCtx, a: Rid, b: Rid) bool {
            const ma = ctx.rs.mtimeOf(a).?;
            const mb = ctx.rs.mtimeOf(b).?;
            if (ma != mb) return ma > mb; // §2/§8.3: most recent first
            // §3 tiebreak: ascending full artifact hash → a byte-reproducible order.
            return std.mem.order(u8, ctx.rs.store.hashOf(a), ctx.rs.store.hashOf(b)) == .lt;
        }
    };

    /// Section 8.3 item 3's whole check-in universe: every crosslinked check-in
    /// (each event rid, exactly once), ordered by event.mtime descending with an
    /// ascending-full-hash tiebreak (`TimelineOrderCtx`). The single general
    /// query behind `zit timeline` — ordering lives here, not in a CLI-side walk,
    /// so it is testable in isolation. An empty repository yields an empty slice
    /// (never an error). Caller frees the returned slice.
    pub fn checkinsByMtime(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]Rid {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this walk
        var out: std.ArrayList(Rid) = .empty;
        errdefer out.deinit(gpa);
        var scanned: usize = 0;
        const bound = self.events.count();
        for (self.events.keys()) |rid| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            try out.append(gpa, rid);
        }
        const slice = try out.toOwnedSlice(gpa);
        std.mem.sort(Rid, slice, TimelineOrderCtx{ .rs = self }, TimelineOrderCtx.lessThan);
        // Postconditions: one rid per event, and a strict total order — no
        // adjacent pair is out of order (positive AND negative space).
        std.debug.assert(slice.len == self.events.count());
        for (slice, 0..) |rid, i| {
            std.debug.assert(self.events.contains(rid));
            if (i + 1 < slice.len)
                std.debug.assert(!TimelineOrderCtx.lessThan(.{ .rs = self }, slice[i + 1], rid));
        }
        return slice;
    }

    /// Merge base of `a` and `b` over FULL ancestry (Section 3.3 child-to-parent
    /// traversal, merge parents included per Section 3.2): the common ancestor
    /// with the greatest event mtime (Section 2 / Section 8.3 item 7's ordering
    /// clock), ties broken by the lexicographically-least artifact hash. Total
    /// and deterministic. Each endpoint is a member of its OWN ancestor set — the
    /// BFS seeds each frontier with the endpoint node itself before walking
    /// `parentsOf`, so a node is its own ancestor. Therefore
    /// `mergeBaseOf(x, x) == x` and `mergeBaseOf(x, y) == y` whenever `y` is an
    /// ancestor of `x` (the base == other equality the up-to-date refusal keys
    /// on). `null` == no common ancestor (unrelated histories). Composed from
    /// `parentsOf` / `mtimeOf` / `store.hashOf` — a general-purpose query with no
    /// per-verb shaping (a future rebase/annotate reuses it). ambiguities.md
    /// `merge-base`, implemented verbatim.
    pub fn mergeBaseOf(self: *const RepoState, gpa: std.mem.Allocator, a: Rid, b: Rid) error{OutOfMemory}!?Rid {
        std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize the linkage table
        // The full ancestor set of `a`, endpoint self-included.
        var ancestors_a: std.AutoHashMapUnmanaged(Rid, void) = .empty;
        defer ancestors_a.deinit(gpa);
        try self.collectAncestors(gpa, a, &ancestors_a);

        // Walk `b`'s ancestry (endpoint self-included) and keep the common node
        // with the greatest event mtime, ties broken by the least artifact hash.
        // Visited-once BFS, bounded by the artifact universe.
        var visited_b: std.AutoHashMapUnmanaged(Rid, void) = .empty;
        defer visited_b.deinit(gpa);
        var frontier: std.ArrayList(Rid) = .empty;
        defer frontier.deinit(gpa);
        try frontier.append(gpa, b);

        var best: ?Rid = null;
        var best_mtime: Mtime = undefined;
        const bound = self.store.count();
        var scanned: usize = 0;
        while (frontier.pop()) |rid| {
            const gop = try visited_b.getOrPut(gpa, rid);
            if (gop.found_existing) continue;
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (ancestors_a.contains(rid)) {
                // A common node with no event row (a still-phantom target,
                // Section 4.2 step 1) has no ordering clock and cannot win.
                if (self.mtimeOf(rid)) |m| {
                    const wins = best == null or m > best_mtime or
                        (m == best_mtime and std.mem.order(u8, self.store.hashOf(rid), self.store.hashOf(best.?)) == .lt);
                    if (wins) {
                        best = rid;
                        best_mtime = m;
                    }
                }
            }
            var it = self.parentsOf(rid);
            while (it.next()) |parent| try frontier.append(gpa, parent);
        }
        // Postcondition: the winner is a common ancestor of both endpoints with a
        // recorded event (positive space).
        if (best) |chosen| {
            std.debug.assert(ancestors_a.contains(chosen));
            std.debug.assert(visited_b.contains(chosen));
            std.debug.assert(self.mtimeOf(chosen) != null);
        }
        return best;
    }

    /// Collect the full ancestor set of `start` — the endpoint itself plus every
    /// rid reachable by repeated `parentsOf` (Section 3.3, merge parents
    /// included) — into `set`. The frontier is seeded with `start`, so a node is
    /// its own ancestor. Visited-once BFS bounded by the artifact universe.
    fn collectAncestors(self: *const RepoState, gpa: std.mem.Allocator, start: Rid, set: *std.AutoHashMapUnmanaged(Rid, void)) error{OutOfMemory}!void {
        var frontier: std.ArrayList(Rid) = .empty;
        defer frontier.deinit(gpa);
        try frontier.append(gpa, start);
        const bound = self.store.count();
        var scanned: usize = 0;
        while (frontier.pop()) |rid| {
            const gop = try set.getOrPut(gpa, rid);
            if (gop.found_existing) continue;
            scanned += 1;
            std.debug.assert(scanned <= bound);
            var it = self.parentsOf(rid);
            while (it.next()) |parent| try frontier.append(gpa, parent);
        }
    }

    /// Full-ancestry membership (Section 3.3): true iff `ancestor` lies in the
    /// full ancestry of `descendant` — the descendant itself plus every rid
    /// reachable by repeated `parentsOf` (merge parents included), WITH
    /// self-membership, so `isAncestorOf(x, x) == true`. Shares the one
    /// `collectAncestors` walk `mergeBaseOf` uses — no duplicated traversal.
    /// mtime-INDEPENDENT, unlike `mergeBaseOf`: no ordering clock or hash
    /// tiebreak enters, so this is the pure §3.3 reachability the up-to-date
    /// merge refusal (B-merge-16) actually needs. `base == other` from
    /// `mergeBaseOf` is NOT a sound proxy — when `other` ties another ancestor
    /// on mtime and loses the least-hash tiebreak, the selection returns a
    /// different node and the equality misses.
    pub fn isAncestorOf(self: *const RepoState, gpa: std.mem.Allocator, ancestor: Rid, descendant: Rid) error{OutOfMemory}!bool {
        var ancestors: std.AutoHashMapUnmanaged(Rid, void) = .empty;
        defer ancestors.deinit(gpa);
        try self.collectAncestors(gpa, descendant, &ancestors);
        return ancestors.contains(ancestor);
    }

    /// The derived result of a bisect span computation (ambiguities.md
    /// `bisect-midpoint`): the running lower bound / culprit, the untested count,
    /// and the next probe.
    pub const BisectOutcome = struct {
        /// The mtime-earliest marked-bad check-in (ties: least artifact hash) —
        /// the running lower bound of the search, and the culprit once
        /// `probe == null`.
        culprit: Rid,
        /// The number of untested candidates (candidates minus every marked-bad
        /// check-in that bears an event); 0 exactly when `probe == null`.
        untested: usize,
        /// The next probe: the lower median of the untested candidates ordered by
        /// ascending event mtime (ties least hash), or null when none remain and
        /// the culprit is final.
        probe: ?Rid,
    };

    /// The two refusal preconditions of a bisect span, plus the shared allocation
    /// failure. `InvertedMarks` — the bad check-in is an ancestor of a good one.
    /// `UnrelatedHistories` — a good and the bad check-in share no ancestor.
    pub const BisectError = error{ OutOfMemory, InvertedMarks, UnrelatedHistories };

    /// The bisect candidate span and next probe (ambiguities.md `bisect-midpoint`,
    /// implemented verbatim): the candidate set is the full-ancestry ancestor set
    /// of the bad check-in (§3.3, merge parents included — every path contributes)
    /// MINUS the union of every good's full-ancestry ancestor set MINUS the
    /// skipped set. The "bad check-in" is the anchor = the mtime-earliest
    /// marked-bad (ties least hash), which is also the culprit at termination. The
    /// probe is the lower median of the untested candidates (candidates not marked
    /// bad) by ascending event mtime, ties least hash. Refused, nothing computed:
    /// an anchor that is an ancestor of a good (inverted marks) or a good sharing
    /// no ancestor with the anchor (unrelated histories). ONE general-purpose
    /// query composed from `collectAncestors`/`mergeBaseOf`/`isAncestorOf`/
    /// `mtimeOf`/`store.hashOf` — never a CLI-side ancestry walk. Preconditions:
    /// at least one bad and one good mark, each a crosslinked check-in.
    pub fn bisectSpan(
        self: *const RepoState,
        gpa: std.mem.Allocator,
        bad: []const Rid,
        good: []const Rid,
        skipped: []const Rid,
    ) BisectError!BisectOutcome {
        std.debug.assert(self.backing == .derived); // cold query over the linkage table
        std.debug.assert(bad.len != 0);
        std.debug.assert(good.len != 0);

        // The anchor bad = the mtime-earliest marked-bad (ties least hash): the
        // running lower bound, and the culprit once no untested candidate remains.
        var anchor: Rid = bad[0];
        for (bad[1..]) |rid| {
            if (self.bisectLess(rid, anchor)) anchor = rid;
        }

        // Preconditions key on THE bad check-in = the anchor. A good sharing no
        // ancestor with it is unrelated histories; the anchor being an ancestor of
        // a good is inverted marks. Both refuse before any candidate is built.
        for (good) |g| {
            if ((try self.mergeBaseOf(gpa, anchor, g)) == null) return error.UnrelatedHistories;
            if (try self.isAncestorOf(gpa, anchor, g)) return error.InvertedMarks;
        }

        // Candidate set = full ancestry of the anchor, minus every good's full
        // ancestry (each good is a member of its own set, so goods never survive),
        // minus the skipped set.
        var candidates: std.AutoHashMapUnmanaged(Rid, void) = .empty;
        defer candidates.deinit(gpa);
        try self.collectAncestors(gpa, anchor, &candidates);
        for (good) |g| {
            var g_anc: std.AutoHashMapUnmanaged(Rid, void) = .empty;
            defer g_anc.deinit(gpa);
            try self.collectAncestors(gpa, g, &g_anc);
            var it = g_anc.keyIterator();
            while (it.next()) |k| _ = candidates.remove(k.*);
        }
        for (skipped) |s| _ = candidates.remove(s);

        // Untested = candidates not yet marked bad and bearing an event (a phantom
        // placeholder has no ordering clock and cannot be probed).
        var bad_set: std.AutoHashMapUnmanaged(Rid, void) = .empty;
        defer bad_set.deinit(gpa);
        for (bad) |rid| try bad_set.put(gpa, rid, {});

        var untested: std.ArrayList(Rid) = .empty;
        defer untested.deinit(gpa);
        var cit = candidates.keyIterator();
        while (cit.next()) |k| {
            const rid = k.*;
            if (bad_set.contains(rid)) continue;
            if (self.mtimeOf(rid) == null) continue;
            try untested.append(gpa, rid);
        }

        if (untested.items.len == 0) {
            return .{ .culprit = anchor, .untested = 0, .probe = null };
        }

        // Order by ascending event mtime, ties least hash; the probe is the lower
        // median (index (len - 1) / 2 — an even span probes the earlier element).
        std.mem.sort(Rid, untested.items, self, bisectLess);
        const idx = (untested.items.len - 1) / 2;
        return .{ .culprit = anchor, .untested = untested.items.len, .probe = untested.items[idx] };
    }

    /// Probe / anchor total order: ascending event mtime, ties by least
    /// (lexicographically-least) artifact hash. Defined only over check-ins that
    /// bear an event — every caller filters phantoms out first.
    fn bisectLess(self: *const RepoState, a: Rid, b: Rid) bool {
        const ma = self.mtimeOf(a).?;
        const mb = self.mtimeOf(b).?;
        if (ma != mb) return ma < mb;
        return std.mem.order(u8, self.store.hashOf(a), self.store.hashOf(b)) == .lt;
    }

    /// Apply every scheduled leaf recheck and clear the schedule
    /// (Section 7.3 batch application). The check adds no new entries to
    /// the schedule, so the batch is bounded by its size at entry.
    fn applyPendingLeafChecks(self: *RepoState) error{OutOfMemory}!void {
        const n = self.pending_leaf.count();
        for (self.pending_leaf.keys()[0..n]) |rid| {
            try self.leafCheckOne(rid);
        }
        std.debug.assert(self.pending_leaf.count() == n);
        self.pending_leaf.clearRetainingCapacity();
    }

    /// Recompute leaf membership for a single rid (Section 7.3 incremental
    /// check): removed when it has a same-branch child, inserted otherwise,
    /// tolerating already-present. A rid without an event row is not a
    /// check-in (a phantom placeholder) and never enters the table.
    fn leafCheckOne(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
        const is_leaf = self.events.contains(rid) and !self.hasSameBranchChild(rid);
        if (is_leaf) {
            try self.leaf_table.put(self.gpa, rid, {});
        } else {
            _ = self.leaf_table.swapRemove(rid);
        }
    }

    /// The canonical leaf test's disqualifier (Section 7.2): any
    /// parent-link naming `rid` as parent whose child is on the same
    /// branch. Deliberately NOT filtered by the primary/merge distinction —
    /// a same-branch child reached only via a merge edge still counts.
    fn hasSameBranchChild(self: *const RepoState, rid: Rid) bool {
        if (self.children.getPtr(rid)) |list| {
            for (list.items) |e| {
                if (self.sameBranch(rid, e.rid)) return true;
            }
        }
        return false;
    }

    /// Whether two check-ins are on the same branch: their branch values
    /// (Section 6.1) compare equal.
    fn sameBranch(self: *const RepoState, a: Rid, b: Rid) bool {
        return std.mem.eql(u8, self.branchValueOf(a), self.branchValueOf(b));
    }

    /// The active branch-tag value for `rid` (Section 6.1), or null when no
    /// active (tagtype > 0) row is present. No default here: the caller
    /// decides what absence means — `branchOf`'s Section 6.4 fallback to
    /// the configured main branch, versus `openLeafOf`'s strict
    /// non-membership (a tagless check-in is never that branch's open leaf).
    fn activeBranchValue(self: *const RepoState, rid: Rid) ?[]const u8 {
        if (self.tagxref.get(.{ .rid = rid, .tag = branch_tag_id })) |xr| {
            if (xr.tagtype != .cancel) {
                if (xr.value) |v| return v;
            }
        }
        return null;
    }

    /// The branch value of `rid` used by the same-branch leaf test
    /// (Section 6.1, Section 6.4 fallback): `activeBranchValue`, or the
    /// literal default branch when absent. Leaf derivation is internal
    /// bookkeeping, not parameterized by the configurable main-branch
    /// setting the way `branchOf` is.
    fn branchValueOf(self: *const RepoState, rid: Rid) []const u8 {
        return self.activeBranchValue(rid) orelse default_branch;
    }

    /// The interned id of tag `name`, or null when `name` was never interned in
    /// this view (Section 2). A read-only sibling of `internTag`: it never
    /// assigns an id — a never-seen name simply has none — so it stays `*const`.
    /// "branch"/"closed" are the fixed reserved ids; every other name is looked
    /// up in the `tag_names` table.
    fn tagId(self: *const RepoState, name: []const u8) ?TagId {
        std.debug.assert(name.len != 0);
        if (std.mem.eql(u8, name, "branch")) return branch_tag_id;
        if (std.mem.eql(u8, name, "closed")) return closed_tag_id;
        return self.tag_names.get(name);
    }

    /// The live (non-cancel, latest-mtime-superseded) value of the tag `name` on
    /// `rid` (Section 5.2/5.3), or null when no active row carries a value —
    /// including when `name` was never interned (a name with no id has no rows).
    /// A read-only lookup: it never assigns a tag id, so it is safe on the derived
    /// read view the display sites hold. The returned bytes borrow the tagxref
    /// row's stored value, valid until the next `RepoState` mutation.
    pub fn activeTagValue(self: *const RepoState, rid: Rid, name: []const u8) ?[]const u8 {
        std.debug.assert(name.len != 0);
        const id = self.tagId(name) orelse return null;
        if (self.tagxref.get(.{ .rid = rid, .tag = id })) |xr| {
            if (xr.tagtype != .cancel) return xr.value; // Section 5.1: cancel is inactive
        }
        return null;
    }

    /// Whether `rid` carries an active closed tag (Section 7.4).
    fn hasActiveClosed(self: *const RepoState, rid: Rid) bool {
        if (self.tagxref.get(.{ .rid = rid, .tag = closed_tag_id })) |xr| {
            return xr.tagtype != .cancel;
        }
        return false;
    }

    /// Intern a tag name to its id (Section 2): "branch" and "closed" are
    /// the fixed ids 8 and 9; every other name is assigned the next id
    /// starting at 10, first-seen order.
    fn internTag(self: *RepoState, name: []const u8) error{OutOfMemory}!TagId {
        std.debug.assert(name.len != 0);
        if (std.mem.eql(u8, name, "branch")) return branch_tag_id;
        if (std.mem.eql(u8, name, "closed")) return closed_tag_id;
        if (self.tag_names.get(name)) |id| return id;
        std.debug.assert(self.next_tag < std.math.maxInt(TagId));
        const owned = try self.gpa.dupe(u8, name);
        errdefer self.gpa.free(owned);
        const id = self.next_tag;
        try self.tag_names.put(self.gpa, owned, id);
        self.next_tag += 1;
        return id;
    }

    /// The interned id of "sym-<name>", or null when that name has never
    /// been tagged (Section 2: symbolic names are stored internally with a
    /// "sym-" prefix). A scan rather than a concatenated-key lookup: tag
    /// names are owned, arbitrary-length strings with no RFC-mandated
    /// bound, so building "sym-" ++ name would allocate for a read-only
    /// query that has no other reason to.
    fn symTagId(self: *const RepoState, name: []const u8) ?TagId {
        const prefix = "sym-";
        var it = self.tag_names.iterator();
        var scanned: usize = 0;
        const bound = self.tag_names.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            const key = entry.key_ptr.*;
            if (key.len != prefix.len + name.len) continue;
            if (!std.mem.eql(u8, key[0..prefix.len], prefix)) continue;
            if (std.mem.eql(u8, key[prefix.len..], name)) return entry.value_ptr.*;
        }
        return null;
    }

    /// The materialized §8.2 resolution table: every live symbolic name (a
    /// "sym-<name>" tag that resolves to a crosslinked check-in) paired with the
    /// max-mtime rid `resolveName` selects for it. General-purpose — the read-
    /// image consumer builds its name table from this. Each `name` borrows the
    /// interned tag-name bytes (valid until the next mutation). Caller frees the
    /// slice. Derived backing only (it reads the tag-name table).
    pub fn resolvedSymbols(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]ResolvedSymbol {
        std.debug.assert(self.backing == .derived);
        const prefix = "sym-";
        var out: std.ArrayList(ResolvedSymbol) = .empty;
        errdefer out.deinit(gpa);
        var it = self.tag_names.iterator();
        var scanned: usize = 0;
        const bound = self.tag_names.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            const key = entry.key_ptr.*;
            if (key.len <= prefix.len) continue;
            if (!std.mem.eql(u8, key[0..prefix.len], prefix)) continue;
            const bare = key[prefix.len..];
            const rid = self.resolveName(bare) catch continue; // an unresolvable sym (phantom winner) is not listed
            try out.append(gpa, .{ .name = bare, .rid = rid });
        }
        return out.toOwnedSlice(gpa);
    }

    /// The interned name of tag `id` (Section 2): the fixed "branch"/"closed"
    /// literals for the reserved ids 8/9, else the `tag_names` key that maps
    /// to `id`, found by a reverse scan bounded by the interned-name count.
    /// `id` is only ever passed from a live tagxref row, so a user id always
    /// has an interned name and the scan always resolves.
    fn tagNameOf(self: *const RepoState, id: TagId) []const u8 {
        if (id == branch_tag_id) return "branch";
        if (id == closed_tag_id) return "closed";
        var it = self.tag_names.iterator();
        var scanned: usize = 0;
        const bound = self.tag_names.count();
        while (it.next()) |entry| {
            scanned += 1;
            std.debug.assert(scanned <= bound);
            if (entry.value_ptr.* == id) return entry.key_ptr.*;
        }
        unreachable; // id came from a live row, so its name is interned
    }

    /// Direct tag application (Section 5.3): supersede-by-mtime with a
    /// >=-skip, raw type stored verbatim (srcid the carrier, origid the
    /// target), value cleared to null for a cancel. The Section 5.4
    /// singleton-to-cancel downgrade is a propagation-entry concern, not
    /// applied to the stored row here (a stored singleton stays active).
    fn applyDirect(self: *RepoState, target: Rid, op: TagOp, srcid: Rid, mtime: Mtime) error{OutOfMemory}!void {
        std.debug.assert(target >= 1);
        const tag = try self.internTag(op.name);
        const key = TagKey{ .rid = target, .tag = tag };
        const existing = self.tagxref.get(key);
        if (existing) |e| {
            if (e.mtime >= mtime) return; // step 1: skip
        }
        var new_value: ?[]u8 = null;
        if (op.type != .cancel) { // step 3: cancel clears to null
            if (op.value) |v| new_value = try self.gpa.dupe(u8, v);
        }
        errdefer if (new_value) |v| self.gpa.free(v);
        // `put` assigns the value atomically with the insert/overwrite, so
        // no half-initialized slot can be left behind on an OOM path — a
        // manual getOrPut-then-assign would leave the newly created slot
        // uninitialized if the dupe above failed after the slot existed.
        try self.tagxref.put(self.gpa, key, .{ .tagtype = op.type, .srcid = srcid, .origid = target, .value = new_value, .mtime = mtime });
        // The map now owns the value; disarm the errdefer so a later failure
        // (addRidTag, scheduleLeafRecheck) cannot double-free what deinit will.
        new_value = null;
        if (existing) |e| {
            if (e.value) |old| self.gpa.free(old);
        } else {
            // First row for this (rid, tag): mirror it into the tag index.
            try self.addRidTag(target, tag);
        }
        std.debug.assert(self.tagxref.get(key).?.mtime >= mtime);
        if (tag == branch_tag_id) try self.scheduleLeafRecheck(target); // Section 7.6 b1
    }

    /// Propagation walk (Section 5.4) rooted at `start`, carrying `ptype`
    /// (propagate or cancel only) with `value`/`origid`/`mtime` down the
    /// primary-child chain until no further child qualifies. Bounded by the
    /// primary-parent forest: in-degree <= 1 on primary edges means each
    /// node is reachable from one walk at most once, so pops are bounded by
    /// the crosslinked check-in count.
    fn propagate(self: *RepoState, start: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!void {
        std.debug.assert(ptype == .cancel or ptype == .propagate);
        var worklist: std.ArrayList(Rid) = .empty;
        defer worklist.deinit(self.gpa);
        try worklist.append(self.gpa, start);
        const max_pops = self.events.count() + 1;
        var pops: usize = 0;
        var head: usize = 0;
        while (head < worklist.items.len) : (head += 1) {
            const a = worklist.items[head];
            pops += 1;
            std.debug.assert(pops <= max_pops);
            // The child set of `a` is fixed for the whole walk: linkage rows are
            // built during crosslink's linkage phase, before any tag op runs, so
            // `children` is never mutated here and this pointer stays valid.
            if (self.children.getPtr(a)) |list| {
                for (list.items) |e| {
                    if (!e.is_primary) continue; // never a merge edge
                    const child = e.rid;
                    const changed = try self.propagateOne(child, tag, ptype, value, origid, mtime);
                    if (changed) {
                        try worklist.append(self.gpa, child);
                        if (tag == branch_tag_id) try self.scheduleLeafRecheck(child); // Section 7.6 b2
                    }
                }
            }
        }
    }

    /// Apply one propagation step to `child` (Section 5.4 steps 3-4):
    /// qualifies iff no existing row, or an inherited (srcid 0) row with a
    /// strictly earlier mtime. A nonzero-srcid row is never overwritten
    /// (Section 5.5); an equal mtime is retained. Returns whether the child
    /// was updated, so the caller can enqueue it for further propagation —
    /// a no-op cancel delete on an absent row still counts, matching the
    /// literal "always qualifies" text of step 3.
    fn propagateOne(self: *RepoState, child: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!bool {
        const key = TagKey{ .rid = child, .tag = tag };
        const existing = self.tagxref.get(key);
        const qualifies = if (existing) |e| (e.srcid == 0 and e.mtime < mtime) else true;
        if (!qualifies) return false;
        if (existing) |e| std.debug.assert(e.srcid == 0); // never overwrite a direct row
        switch (ptype) {
            .propagate => {
                var new_value: ?[]u8 = null;
                if (value) |v| new_value = try self.gpa.dupe(u8, v);
                errdefer if (new_value) |v| self.gpa.free(v);
                // Store first, free the old value only once the put has
                // succeeded: freeing before a fallible put would leave the
                // map's still-live entry pointing at freed memory if the put
                // itself failed (matches applyDirect's ordering).
                try self.tagxref.put(self.gpa, key, .{ .tagtype = .propagate, .srcid = 0, .origid = origid, .value = new_value, .mtime = mtime });
                // The map now owns the value; disarm the errdefer so a failing
                // addRidTag below cannot double-free what deinit will free.
                new_value = null;
                if (existing) |e| {
                    if (e.value) |old| self.gpa.free(old);
                } else {
                    // First row for this (rid, tag): mirror it into the index.
                    try self.addRidTag(child, tag);
                }
            },
            .cancel => {
                if (existing) |e| {
                    if (e.value) |old| self.gpa.free(old);
                    _ = self.tagxref.remove(key);
                    self.removeRidTag(child, tag);
                }
            },
            .singleton => unreachable, // rejected by the propagate() precondition
        }
        return true;
    }

    const SnapRow = struct { tag: TagId, xr: Xref };

    /// Re-propagate `parent`'s full tag set (Section 4.2 step 4a): a
    /// snapshot first, since the map mutates during the walk. Every
    /// singleton row is downgraded to cancel per the Section 5.4 driving
    /// rule; cancel and propagate rows pass through unchanged.
    fn repropagateSet(self: *RepoState, parent: Rid) error{OutOfMemory}!void {
        var rows: std.ArrayList(SnapRow) = .empty;
        defer rows.deinit(self.gpa);
        if (self.rid_tags.getPtr(parent)) |tags| {
            for (tags.items) |tag| {
                // rid_tags is precise: every listed tag has a live tagxref row.
                const xr = self.tagxref.get(.{ .rid = parent, .tag = tag }).?;
                try rows.append(self.gpa, .{ .tag = tag, .xr = xr });
            }
        }
        for (rows.items) |row| {
            const pt: TagType = if (row.xr.tagtype == .singleton) .cancel else row.xr.tagtype;
            std.debug.assert(pt == .cancel or pt == .propagate);
            try self.propagate(parent, row.tag, pt, row.xr.value, row.xr.origid, row.xr.mtime);
        }
    }

    /// Schedule an incremental leaf recheck for `rid` and each of its
    /// direct parents (Section 7.3), tolerating an rid with no parents yet.
    fn scheduleLeafRecheck(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
        try self.pending_leaf.put(self.gpa, rid, {});
        // Snapshot the parent count first: `pending_leaf.put` never mutates
        // `parents_by_child`, so the edge slice stays valid across the loop.
        if (self.parents_by_child.getPtr(rid)) |list| {
            for (list.items) |e| try self.pending_leaf.put(self.gpa, e.rid, {});
        }
    }
};

/// Days since 1970-01-01 for a proleptic-Gregorian civil date (Howard
/// Hinnant's public-domain `days_from_civil` calendar identity — plain
/// integer math, not derived from any Fossil/libfossil source). Backs the
/// Section 8.3 form 7 date-form parser below, placing a parsed timestamp
/// and stored event.mtime values on one millisecond timeline. Inputs must
/// already be range-validated (see `parseDateTime`).
fn daysFromCivil(y_in: i64, m: u8, d: u8) i64 {
    std.debug.assert(m >= 1 and m <= 12);
    std.debug.assert(d >= 1 and d <= 31);
    var y = y_in;
    if (m <= 2) y -= 1;
    const era: i64 = @divFloor(if (y >= 0) y else y - 399, 400);
    const yoe: i64 = y - era * 400;
    const mp: i64 = @mod(@as(i64, m) + 9, 12);
    const doy: i64 = @divFloor(153 * mp + 2, 5) + @as(i64, d) - 1;
    const doe: i64 = yoe * 365 + @divFloor(yoe, 4) - @divFloor(yoe, 100) + doy;
    return era * 146_097 + doe - 719_468;
}

fn isLeapYear(y: i64) bool {
    return @mod(y, 4) == 0 and (@mod(y, 100) != 0 or @mod(y, 400) == 0);
}

fn daysInMonth(y: i64, m: u8) u8 {
    return switch (m) {
        1, 3, 5, 7, 8, 10, 12 => 31,
        4, 6, 9, 11 => 30,
        2 => if (isLeapYear(y)) @as(u8, 29) else 28,
        else => unreachable, // m range-checked by parseDateTime before this call
    };
}

const DatePrecision = enum { date_only, minute, second, fraction };

const DateParts = struct {
    y: u16,
    mo: u8,
    d: u8,
    h: u8,
    mi: u8,
    s: u8,
    /// 1-3 ASCII digits, empty below `.fraction` precision.
    frac: []const u8,
    precision: DatePrecision,
};

/// Fixed-field parse of a Section 8.3 form 7 timestamp:
/// `YYYY-MM-DD[ HH:MM[:SS[.f{1,3}]]]`. Never panics on malformed input
/// (fuzz-safe): every field is range-checked and a bad byte returns null
/// rather than trapping.
fn parseDateTime(text: []const u8) ?DateParts {
    if (text.len < 10) return null;
    const y = std.fmt.parseInt(u16, text[0..4], 10) catch return null;
    if (text[4] != '-') return null;
    const mo = std.fmt.parseInt(u8, text[5..7], 10) catch return null;
    if (mo < 1 or mo > 12) return null;
    if (text[7] != '-') return null;
    const d = std.fmt.parseInt(u8, text[8..10], 10) catch return null;
    if (d < 1 or d > daysInMonth(y, mo)) return null;
    if (text.len == 10) return .{ .y = y, .mo = mo, .d = d, .h = 0, .mi = 0, .s = 0, .frac = &.{}, .precision = .date_only };

    if (text.len < 16 or text[10] != ' ') return null;
    const h = std.fmt.parseInt(u8, text[11..13], 10) catch return null;
    if (h > 23) return null;
    if (text[13] != ':') return null;
    const mi = std.fmt.parseInt(u8, text[14..16], 10) catch return null;
    if (mi > 59) return null;
    if (text.len == 16) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = 0, .frac = &.{}, .precision = .minute };

    if (text.len < 19 or text[16] != ':') return null;
    const s = std.fmt.parseInt(u8, text[17..19], 10) catch return null;
    if (s > 59) return null;
    if (text.len == 19) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = &.{}, .precision = .second };

    if (text.len < 21 or text.len > 23 or text[19] != '.') return null;
    const frac = text[20..];
    for (frac) |c| if (!std.ascii.isDigit(c)) return null;
    return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = frac, .precision = .fraction };
}

/// Converts a fixed 3-ASCII-digit buffer to its numeric value (0-999).
/// Every byte must be a decimal digit: `expandTimestamp` fills `buf` only
/// from `'0'`/`'9'` padding or from `DateParts.frac`, whose bytes
/// `parseDateTime` already range-checked with `std.ascii.isDigit`.
fn digits3ToMs(buf: [3]u8) u16 {
    for (buf) |c| std.debug.assert(std.ascii.isDigit(c));
    return @as(u16, buf[0] - '0') * 100 + @as(u16, buf[1] - '0') * 10 + (buf[2] - '0');
}

/// Section 8.3 form 7 upper-bound / direct expansion, returning a Unix-
/// epoch millisecond bound (or null on a malformed timestamp).
/// `.upper_bound` pads an under-specified field to its latest instant per
/// the precision table (date-only -> 23:59:59.999, minute -> :59.999,
/// second -> .999; a fractional field is copied, padded to three digits
/// with trailing 9s, and advanced by one millisecond unless already .999 —
/// .1 -> .199 -> .200, .12 -> .129 -> .130, .123 -> .124, .999 stays).
/// `.direct` (the deprecated local: form) parses the literal fields with
/// no expansion — an absent field is zero and a given fraction is read at
/// face value, matching a bare julianday() parse.
fn expandTimestamp(text: []const u8, mode: RepoState.TimestampMode) ?u64 {
    const parts = parseDateTime(text) orelse return null;
    var h = parts.h;
    var mi = parts.mi;
    var s = parts.s;
    var ms: u16 = 0;
    switch (mode) {
        .upper_bound => switch (parts.precision) {
            .date_only => {
                h = 23;
                mi = 59;
                s = 59;
                ms = 999;
            },
            .minute => {
                s = 59;
                ms = 999;
            },
            .second => ms = 999,
            .fraction => {
                var buf = [3]u8{ '9', '9', '9' };
                for (parts.frac, 0..) |c, i| buf[i] = c;
                ms = digits3ToMs(buf);
                if (ms != 999) ms += 1;
            },
        },
        .direct => switch (parts.precision) {
            .date_only, .minute, .second => {},
            .fraction => {
                var buf = [3]u8{ '0', '0', '0' };
                for (parts.frac, 0..) |c, i| buf[i] = c;
                ms = digits3ToMs(buf);
            },
        },
    }
    const days = daysFromCivil(@as(i64, parts.y), parts.mo, parts.d);
    const total_ms: i64 = days * 86_400_000 +
        @as(i64, h) * 3_600_000 +
        @as(i64, mi) * 60_000 +
        @as(i64, s) * 1_000 +
        @as(i64, ms);
    if (total_ms < 0) return null; // pre-epoch: outside this layer's ms timeline
    return @intCast(total_ms);
}

/// Parse a direct timestamp into the repository's millisecond timeline.
/// Canonical artifact D-card datetimes use `T` as their date/time separator;
/// normalize that byte only, then reuse the Section 8.3 direct conversion.
pub fn parseMtime(timestamp: []const u8) ?Mtime {
    if (timestamp.len > 10 and timestamp[10] == 'T') {
        // D-cards require a full seconds field, with an optional 1-3 digit
        // fractional component. The direct parser validates every other byte.
        if (timestamp.len < 19 or timestamp.len > 23) return null;
        var normalized: [23]u8 = undefined;
        std.mem.copyForwards(u8, normalized[0..timestamp.len], timestamp);
        normalized[10] = ' ';
        return expandTimestamp(normalized[0..timestamp.len], .direct);
    }
    return expandTimestamp(timestamp, .direct);
}

/// Section 8.3 form 8 shape test: a hex string long enough to be an
/// unambiguous prefix (4 chars) and no longer than the maximum artifact-
/// hash length (64, the sha3-256 case).
fn isHexPrefixShape(name: []const u8) bool {
    if (name.len < 4 or name.len > 64) return false;
    for (name) |c| if (!std.ascii.isHex(c)) return false;
    return true;
}

fn isPunctChar(c: u8) bool {
    return std.ascii.isPunctuation(c);
}

/// Iterator over the leaf table, in table order.
pub const LeafIterator = struct {
    rids: []const Rid,
    index: usize = 0,

    pub fn next(self: *LeafIterator) ?Rid {
        if (self.index == self.rids.len) return null;
        defer self.index += 1;
        return self.rids[self.index];
    }
};

// ---------------------------------------------------------------------------
// Tests. Expected values come from draft-fossil-repo-state-00 only.
// ---------------------------------------------------------------------------

const t = std.testing;

// 64-hex-character hashes, distinct per letter.
const h_a = "a" ** 64;
const h_b = "b" ** 64;
const h_c = "c" ** 64;
const h_d = "d" ** 64;
const h_e = "e" ** 64;
const h_f = "f" ** 64;
const h_g = "0" ** 64;
const h_h = "1" ** 64;

fn countLeaves(rs: *const RepoState) usize {
    var it = rs.leaves();
    var n: usize = 0;
    while (it.next()) |_| n += 1;
    return n;
}

/// White-box lookup of a tagxref row by tag name, for test assertions only.
fn tagRowFor(rs: *RepoState, rid: Rid, name: []const u8) error{OutOfMemory}!?RepoState.Xref {
    const tag = try rs.internTag(name);
    return rs.tagxref.get(.{ .rid = rid, .tag = tag });
}

test "repostate §5.3: a strictly later mtime supersedes an earlier one" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
    } });
    _ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
    } });
    const xr = (try tagRowFor(&rs, ra, "t1")).?;
    try t.expectEqualStrings("v2", xr.value.?);
    try t.expectEqual(@as(Mtime, 6), xr.mtime);
}

test "repostate §5.3: a strictly earlier mtime is skipped" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = 6, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
    } });
    _ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
    } });
    const xr = (try tagRowFor(&rs, ra, "t1")).?;
    try t.expectEqualStrings("v1", xr.value.?);
}

test "repostate §5.3: an equal-mtime re-application is skipped" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
    } });
    _ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
    } });
    // Derivation §5.3.1: ">= ... MUST be skipped"; the equal-mtime case is
    // impl-defined, so our >= retains the existing (first) write.
    const xr = (try tagRowFor(&rs, ra, "t1")).?;
    try t.expectEqualStrings("v1", xr.value.?);
}

test "repostate §5.3: a cancel application clears the value to null" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5, .tags = &.{
        .{ .type = .cancel, .name = "t1", .target = null, .value = "z" },
    } });
    const xr = (try tagRowFor(&rs, ra, "t1")).?;
    try t.expectEqual(TagType.cancel, xr.tagtype);
    try t.expect(xr.value == null);
}

test "repostate §5.3/§4.2: a singleton tag triggers no propagation walk" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = null, .value = "v" },
    } });
    const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
    const xr = (try tagRowFor(&rs, try rs.store.intern(h_a), "t1")).?;
    try t.expectEqual(TagType.singleton, xr.tagtype);
}

test "repostate §5.2: tagxref holds at most one row per (rid, tag)" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
    } });
    _ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
    } });
    try t.expectEqual(@as(usize, 1), rs.tagxref.count());
    try t.expectEqualStrings("v2", (try tagRowFor(&rs, ra, "t1")).?.value.?);
}

test "repostate §5.4: a propagating tag reaches primary-chain descendants" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    try t.expectEqualStrings("v", (try tagRowFor(&rs, rb, "t1")).?.value.?);
    try t.expectEqualStrings("v", (try tagRowFor(&rs, rc, "t1")).?.value.?);
}

test "repostate §5.2: activeTagValue returns a live tag value; null when the name was never interned" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rid = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    // A control artifact singleton-overrides the check-in's displayed comment
    // (the exact shape `zit amend --comment` mints).
    _ = try rs.ingestControlTags(h_b, 2, &.{
        .{ .type = .singleton, .name = "comment", .target = h_a, .value = "hello" },
    });
    try t.expectEqualStrings("hello", rs.activeTagValue(rid, "comment").?);
    // A name never interned in this view has no id and no rows ⇒ null.
    try t.expect(rs.activeTagValue(rid, "nonesuch") == null);
    // A cancel row is inactive (Section 5.1) ⇒ null, not the stale value.
    _ = try rs.ingestControlTags(h_c, 3, &.{
        .{ .type = .cancel, .name = "comment", .target = h_a, .value = null },
    });
    try t.expect(rs.activeTagValue(rid, "comment") == null);
}

test "repostate §5.3: activeTagValue reflects latest-mtime supersede (last-wins)" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rid = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    // Two controls override the same tag; the greater-mtime write wins (Section
    // 5.3), regardless of ingest order — ingest the later one first.
    _ = try rs.ingestControlTags(h_c, 9, &.{
        .{ .type = .singleton, .name = "comment", .target = h_a, .value = "new" },
    });
    _ = try rs.ingestControlTags(h_b, 4, &.{
        .{ .type = .singleton, .name = "comment", .target = h_a, .value = "old" },
    });
    try t.expectEqualStrings("new", rs.activeTagValue(rid, "comment").?);
}

test "repostate §5.4: a propagated row carries origin value and mtime with srcid 0" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 3, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
    const xr = (try tagRowFor(&rs, rb, "t1")).?;
    try t.expectEqual(@as(Rid, 0), xr.srcid);
    try t.expectEqual(ra, xr.origid);
    try t.expectEqualStrings("v", xr.value.?);
    try t.expectEqual(@as(Mtime, 3), xr.mtime);
}

test "repostate §5.4: propagation does not cross a merge edge" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} }); // primary child of A
    _ = try rs.crosslink(.{ .hash = h_c, .mtime = 3 }); // unrelated root R
    // M's primary parent is R; B is only a merge (non-primary) parent.
    const rm = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_c, h_b } });
    try t.expect((try tagRowFor(&rs, rm, "t1")) == null);
}

test "repostate §5.4: a directly-applied entry is never overwritten by propagation" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v1" },
    } });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v2" },
    } });
    const xr = (try tagRowFor(&rs, rb, "t1")).?;
    try t.expectEqualStrings("v2", xr.value.?);
    try t.expect(xr.srcid != 0);
}

test "repostate §5.4: an inherited entry of equal mtime is retained" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const tag = try rs.internTag("t1");
    // Seed an inherited row directly (white-box): the exact tie condition
    // under test is not otherwise reachable through crosslink alone.
    const old_val = try t.allocator.dupe(u8, "old");
    try rs.tagxref.put(t.allocator, .{ .rid = rc, .tag = tag }, .{ .tagtype = .propagate, .srcid = 0, .origid = rp, .value = old_val, .mtime = 5 });
    try rs.propagate(rp, tag, .propagate, "new", rp, 5);
    const xr = rs.tagxref.get(.{ .rid = rc, .tag = tag }).?;
    try t.expectEqualStrings("old", xr.value.?);
}

test "repostate §5.5: a cancel tag halts propagation to descendants" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
        .{ .type = .cancel, .name = "t1", .target = null, .value = null },
    } });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
    try t.expectEqual(TagType.cancel, (try tagRowFor(&rs, rb, "t1")).?.tagtype);
}

test "repostate §5.5: a singleton on a parent blocks propagation through it" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
    } });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
    const xrb = (try tagRowFor(&rs, rb, "t1")).?;
    try t.expectEqual(TagType.singleton, xrb.tagtype);
    try t.expectEqualStrings("w", xrb.value.?);
}

test "repostate §5.4: the propagation entry rejects a singleton, reaching descendants as cancel" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
    } });
    const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
}

test "repostate §4.2 step 1: a tag on an absent target attaches to its phantom and survives arrival" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    _ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = h_h, .value = "v" },
    } });
    const rh = try rs.store.intern(h_h);
    try t.expect(!rs.isLeaf(rh)); // phantom, not a check-in
    try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
    const rh_again = try rs.crosslink(.{ .hash = h_h, .mtime = 2 });
    try t.expectEqual(rh, rh_again);
    try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
    try t.expect(rs.isLeaf(rh));
}

test "repostate §4.2 step 4: a new child inherits its primary parent's propagating tag" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } });
    const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const xr = (try tagRowFor(&rs, rc, "t1")).?;
    try t.expectEqualStrings("v", xr.value.?);
    try t.expectEqual(@as(Rid, 0), xr.srcid);
    try t.expectEqual(rp, xr.origid);
}

test "repostate §4.2 step 5: re-crosslink re-runs tag application idempotently" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rec = Record{ .hash = h_a, .mtime = 1, .tags = &.{
        .{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
    } };
    const r1 = try rs.crosslink(rec);
    const before = countLeaves(&rs);
    const r2 = try rs.crosslink(rec);
    try t.expectEqual(r1, r2);
    try t.expectEqual(before, countLeaves(&rs));
    try t.expectEqual(@as(usize, 1), rs.tagxref.count());
    try t.expectEqualStrings("v", (try tagRowFor(&rs, r1, "t1")).?.value.?);
}

// ---------------------------------------------------------------------------
// §8 name resolution, §6.3 branch enumeration, §7.5 ambiguous-leaf reporting.
// ---------------------------------------------------------------------------

test "repostate §8.3: date upper-bound expansion of fractional seconds" {
    const cases = [_]struct { in: []const u8, want: []const u8 }{
        .{ .in = "2026-07-10 08:30:15.1", .want = "2026-07-10 08:30:15.200" },
        .{ .in = "2026-07-10 08:30:15.12", .want = "2026-07-10 08:30:15.130" },
        .{ .in = "2026-07-10 08:30:15.123", .want = "2026-07-10 08:30:15.124" },
        .{ .in = "2026-07-10 08:30:15.999", .want = "2026-07-10 08:30:15.999" },
    };
    for (cases) |c| {
        const got = expandTimestamp(c.in, .upper_bound).?;
        // The literal target, parsed with no expansion, is the independent
        // check on the padding rule's output.
        const want = expandTimestamp(c.want, .direct).?;
        try t.expectEqual(want, got);
    }
}

test "repostate §8.3: date upper-bound expansion by precision" {
    try t.expectEqual(expandTimestamp("2026-07-10 23:59:59.999", .direct).?, expandTimestamp("2026-07-10", .upper_bound).?);
    try t.expectEqual(expandTimestamp("2026-07-10 08:30:59.999", .direct).?, expandTimestamp("2026-07-10 08:30", .upper_bound).?);
    try t.expectEqual(expandTimestamp("2026-07-10 08:30:15.999", .direct).?, expandTimestamp("2026-07-10 08:30:15", .upper_bound).?);
}

test "repostate §8.3: date: selects the most recent event at or before the bound" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const day9 = expandTimestamp("2026-07-09 12:00:00.000", .direct).?;
    const day10 = expandTimestamp("2026-07-10 00:00:00.500", .direct).?;
    const r9 = try rs.crosslink(.{ .hash = h_a, .mtime = day9 });
    _ = try rs.crosslink(.{ .hash = h_b, .mtime = day10, .parents = &.{h_a} });
    try t.expectEqual(r9, try rs.resolve("date:2026-07-09", .checkin));
}

test "repostate §8.3: local: uses julianday directly without upper-bound expansion" {
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const midnight = expandTimestamp("2026-07-10 00:00:00.000", .direct).?;
    const noon = expandTimestamp("2026-07-10 12:00:00.000", .direct).?;
    const r_mid = try rs.crosslink(.{ .hash = h_a, .mtime = midnight });
    const r_noon = try rs.crosslink(.{ .hash = h_b, .mtime = noon, .parents = &.{h_a} });
    // date: bounds at end-of-day, so the noon event still qualifies; local:
    // passes midnight through directly, excluding noon.
    try t.expectEqual(r_noon, try rs.resolve("date:2026-07-10", .checkin));
    try t.expectEqual(r_mid, try rs.resolve("local:2026-07-10", .checkin));
}

/// True when `edges` holds exactly one entry naming `rid` with `is_primary`.
fn edgeMatches(edges: []const RepoState.Edge, rid: Rid, is_primary: bool) bool {
    var hits: usize = 0;
    for (edges) |e| {
        if (e.rid == rid and e.is_primary == is_primary) hits += 1;
    }
    return hits == 1;
}

fn edgeSlice(map: *const std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(RepoState.Edge)), key: Rid) []const RepoState.Edge {
    if (map.getPtr(key)) |list| return list.items;
    return &.{};
}

// §3.1 parent links, §4 crosslink, §5 tags, §7 leaf-set: the adjacency indexes
// (children / parents_by_child / rid_tags) are pure acceleration of the exact
// same derivation the full linear scans compute. This proves the equivalence
// directly — for random op sequences the indexed answers are byte-for-byte the
// linear-scan answers, and the incrementally maintained leaf table equals a
// from-scratch brute-force recomputation over the raw plinks/tagxref tables.
test "repostate: optimized crosslink == from-scratch derivation for random op sequences" {
    const branches = [_][]const u8{ "trunk", "feature", "topic" };
    const cust = "cust";
    var seed: u64 = 0;
    while (seed < 64) : (seed += 1) {
        var prng = std.Random.DefaultPrng.init(seed);
        const rand = prng.random();

        var ms = MemStore.init(t.allocator);
        defer ms.deinit();
        var rs = RepoState.init(t.allocator, ms.store());
        defer rs.deinit();

        const n = rand.intRangeAtMost(usize, 1, 24);
        var hashes: [24][64]u8 = undefined;
        for (0..n) |i| {
            @memset(&hashes[i], 'a');
            _ = std.fmt.bufPrint(hashes[i][0..16], "{x:0>16}", .{i}) catch unreachable;
        }

        for (0..n) |i| {
            var parent_buf: [3][]const u8 = undefined;
            var pn: usize = 0;
            const want_parents = if (i == 0) 0 else rand.intRangeAtMost(usize, 0, @min(@as(usize, 3), i));
            // Distinct prior indices as parents; parents[0] is the primary.
            var picked: [24]bool = [_]bool{false} ** 24;
            while (pn < want_parents) {
                const j = rand.intRangeLessThan(usize, 0, i);
                if (picked[j]) continue;
                picked[j] = true;
                parent_buf[pn] = &hashes[j];
                pn += 1;
            }

            var tag_buf: [3]TagOp = undefined;
            var tn: usize = 0;
            if (pn == 0) {
                // A root seeds a propagating branch tag (§6.1).
                tag_buf[tn] = .{ .type = .propagate, .name = "branch", .target = null, .value = branches[rand.intRangeLessThan(usize, 0, branches.len)] };
                tn += 1;
            }
            if (rand.boolean()) {
                const sign: TagType = if (rand.boolean()) .propagate else if (rand.boolean()) .singleton else .cancel;
                const target: ?[]const u8 = if (rand.boolean() or i == 0) null else &hashes[rand.intRangeLessThan(usize, 0, i)];
                tag_buf[tn] = .{ .type = sign, .name = cust, .target = target, .value = if (sign == .cancel) null else "v" };
                tn += 1;
            }
            if (rand.boolean()) {
                const sign: TagType = if (rand.boolean()) .singleton else .cancel;
                tag_buf[tn] = .{ .type = sign, .name = "closed", .target = null, .value = null };
                tn += 1;
            }

            _ = try rs.crosslink(.{ .hash = &hashes[i], .mtime = @intCast(i + 1), .parents = parent_buf[0..pn], .tags = tag_buf[0..tn] });
        }

        // (1) plinks <-> adjacency indexes are a faithful mirror.
        var child_edges: usize = 0;
        for (rs.children.values()) |list| child_edges += list.items.len;
        var parent_edges: usize = 0;
        for (rs.parents_by_child.values()) |list| parent_edges += list.items.len;
        try t.expectEqual(rs.plinks.count(), child_edges);
        try t.expectEqual(rs.plinks.count(), parent_edges);
        for (rs.plinks.keys(), rs.plinks.values()) |key, row| {
            try t.expect(edgeMatches(edgeSlice(&rs.children, key.parent), key.child, row.is_primary));
            try t.expect(edgeMatches(edgeSlice(&rs.parents_by_child, key.child), key.parent, row.is_primary));
        }

        // (2) tagxref <-> rid_tags is exactly precise.
        var listed_tags: usize = 0;
        for (rs.rid_tags.values()) |list| listed_tags += list.items.len;
        try t.expectEqual(rs.tagxref.count(), listed_tags);
        var xit = rs.tagxref.iterator();
        while (xit.next()) |entry| {
            const rid = entry.key_ptr.rid;
            const tag = entry.key_ptr.tag;
            var found = false;
            if (rs.rid_tags.getPtr(rid)) |list| {
                for (list.items) |lt| {
                    if (lt == tag) found = true;
                }
            }
            try t.expect(found);
        }

        // (3) indexed accessors == brute-force linear scans, per rid.
        for (rs.events.keys()) |rid| {
            var brute_parents: usize = 0;
            var brute_primary: ?Rid = null;
            for (rs.plinks.keys(), rs.plinks.values()) |key, row| {
                if (key.child != rid) continue;
                brute_parents += 1;
                if (row.is_primary) brute_primary = key.parent;
            }
            try t.expectEqual(brute_parents, rs.parentCount(rid));
            try t.expectEqual(brute_primary, rs.primaryParentOf(rid));

            var brute_same_branch = false;
            for (rs.plinks.keys()) |key| {
                if (key.parent == rid and rs.sameBranch(rid, key.child)) brute_same_branch = true;
            }
            // (4) leaf table == from-scratch brute-force over the raw tables.
            const brute_leaf = !brute_same_branch;
            try t.expectEqual(brute_leaf, rs.leaf_table.contains(rid));
        }
    }
}

test "repostate §2/§8.3: checkinsByMtime orders check-ins by event.mtime descending" {
    // rs-2-mtime-orders-checkins, rs-2-ordering-on-event-mtime, rs-8-3-7, B-timeline-2:
    // §2/§8.3 item 7 make event.mtime the ordering clock; the listing is most
    // recent first, independent of crosslink (insertion) order.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 3 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 1 });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 2 });
    const order = try rs.checkinsByMtime(t.allocator);
    defer t.allocator.free(order);
    // mtimes 3 > 2 > 1 ⇒ ra, rc, rb, regardless of the 3,1,2 arrival order.
    try t.expectEqualSlices(Rid, &.{ ra, rc, rb }, order);
}

test "repostate §2: checkinsByMtime breaks exact-mtime ties by ascending full hash" {
    // B-timeline-3: equal event.mtime ⇒ the total order falls back to ascending
    // full artifact hash, making the enumeration deterministic. h_a ("a"*64) sorts
    // before h_b ("b"*64), so ra precedes rb even though rb was crosslinked first.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 5 });
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5 });
    const order = try rs.checkinsByMtime(t.allocator);
    defer t.allocator.free(order);
    try t.expect(std.mem.order(u8, h_a, h_b) == .lt); // the tiebreak's premise
    try t.expectEqualSlices(Rid, &.{ ra, rb }, order);
}

test "repostate §3.2: a merge check-in is distinguished from a primary-only one" {
    // rs-2-primary-parent-def, rs-2-merge-parent-def,
    // rs-3-2-primary-indicator-first-hash, rs-3-2-mainline-display-must,
    // rs-3-2-merge-not-mainline-predecessor, B-timeline-5: the merge marker keys on
    // §3.2 parentage — a merge child carries >=1 merge parent (parentCount >= 2)
    // while the first P-card hash is its single primary (mainline) parent.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1 }); // primary parent
    const ro = try rs.crosslink(.{ .hash = h_b, .mtime = 2 }); // the other line
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{ h_a, h_b } });
    const rsib = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{h_a} });
    // §3.2: the merge child joins two lines (merge parent present); the sibling does not.
    try t.expect(rs.parentCount(rc) >= 2);
    try t.expectEqual(@as(usize, 1), rs.parentCount(rsib));
    // §3.2: exactly one primary indicator — the FIRST P-card hash (h_a ⇒ rp), never
    // the merge parent ro; the sibling's lone parent is also its primary.
    try t.expectEqual(@as(?Rid, rp), rs.primaryParentOf(rc));
    try t.expect(rs.primaryParentOf(rc).? != ro);
    try t.expectEqual(@as(?Rid, rp), rs.primaryParentOf(rsib));
}

test "repostate merge-base: an endpoint is its own ancestor — self (B-merge-16)" {
    // Review-fix #2 guard: the BFS seeds each frontier with the endpoint node
    // itself before walking parentsOf, so a node is its own ancestor and
    // mergeBaseOf(x, x) == x — the membership the up-to-date refusal keys on.
    // ambiguities.md merge-base.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, ra, ra)); // root is its own base
    try t.expectEqual(@as(?Rid, rc), try rs.mergeBaseOf(t.allocator, rc, rc)); // a deeper tip likewise
    _ = rb;
}

test "repostate merge-base: an ancestor endpoint is the base (B-merge-16)" {
    // y an ancestor of x ⇒ mergeBaseOf(x, y) == y (symmetric): base == other, the
    // equality that fires the up-to-date refusal. Full ancestry §3.3.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, rc, ra)); // deepest ancestor
    try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, ra, rc)); // symmetric
    try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rc, rb)); // nearer proper ancestor
}

test "repostate isAncestorOf: mtime-tied ancestry the merge-base tiebreak defeats (B-merge-16)" {
    // ra(100) <- rb(100) <- rc(101): rb ties ra on mtime, so `mergeBaseOf(rc, rb)`
    // picks the least-hash common ancestor ra, NOT rb — `base == other` would
    // MISS that rb is an ancestor of rc. `isAncestorOf` is mtime-independent and
    // gets it right: full §3.3 reachability, self-inclusive.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 100 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 100, .parents = &.{h_a} }); // ties ra
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 101, .parents = &.{h_b} });
    const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 5 }); // unrelated fresh root
    // The bug's premise: the resolved merge base is ra, not rb — so `base == other`
    // (rb) would never fire the up-to-date refusal.
    try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, rc, rb));
    // The membership predicate is right regardless of the mtime tie.
    try t.expect(try rs.isAncestorOf(t.allocator, rb, rc)); // rb is a proper ancestor of rc
    try t.expect(!try rs.isAncestorOf(t.allocator, rc, rb)); // rc is not an ancestor of rb
    try t.expect(try rs.isAncestorOf(t.allocator, ra, ra)); // self-membership
    try t.expect(!try rs.isAncestorOf(t.allocator, rd, rc)); // unrelated node
}

test "repostate merge-base: a fork resolves to the shared ancestor (B-merge-4)" {
    // Two lines off a shared trunk ra<-rb; tips rc, rd both descend from rb. The
    // common ancestor with the greatest mtime is the fork point rb.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .parents = &.{h_b} });
    const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 6, .parents = &.{h_b} });
    try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rc, rd));
    try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rd, rc)); // symmetric
    _ = ra;
}

test "repostate merge-base: the greatest event.mtime among commons wins (B-merge-4)" {
    // Selection is by event.mtime, not graph distance (ambiguities.md merge-base):
    // the ROOT carries the greatest mtime, so it beats the nearer common ancestors
    // rc and rb despite being farthest from the two tips.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 100 }); // root, greatest mtime
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 20, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 30, .parents = &.{h_b} });
    const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 40, .parents = &.{h_c} }); // tip 1
    const re = try rs.crosslink(.{ .hash = h_e, .mtime = 50, .parents = &.{h_c} }); // tip 2
    // Commons {rc, rb, ra} ⇒ max mtime is ra (100).
    try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, rd, re));
    _ = rb;
    _ = rc;
}

test "repostate merge-base: equal-mtime commons break ties by least hash (ambiguities.md)" {
    // Two common ancestors rx (h_b) and ry (h_c) share the greatest mtime (5); the
    // lexicographically-least artifact hash wins — h_b < h_c ⇒ rx.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rx = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
    const ry = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .parents = &.{h_b} }); // equal mtime
    const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 9, .parents = &.{h_c} }); // tip 1
    const re = try rs.crosslink(.{ .hash = h_e, .mtime = 8, .parents = &.{h_c} }); // tip 2
    try t.expect(std.mem.order(u8, h_b, h_c) == .lt); // the tiebreak's premise
    // Commons {ry, rx, ra}; max mtime 5 ties ry/rx ⇒ least hash h_b ⇒ rx.
    try t.expectEqual(@as(?Rid, rx), try rs.mergeBaseOf(t.allocator, rd, re));
    _ = ra;
    _ = ry;
}

test "repostate merge-base: unrelated histories yield null (B-merge-17)" {
    // Disjoint chains share no common ancestor ⇒ null (the unrelated-histories
    // refusal). ambiguities.md merge-base.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();
    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} }); // history 1
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3 }); // history 2, fresh root
    const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{h_c} });
    try t.expectEqual(@as(?Rid, null), try rs.mergeBaseOf(t.allocator, rb, rd));
    try t.expectEqual(@as(?Rid, null), try rs.mergeBaseOf(t.allocator, rd, rb)); // symmetric
    _ = ra;
    _ = rc;
}

test "repostate §8.3 item 3: checkinsByMtime enumerates the whole check-in universe once" {
    // rs-8-3-tip-global-max-mtime-ci, B-timeline-1, B-timeline-13: the query owns the
    // whole-repo check-in universe (every event rid), each exactly once — no CLI-side
    // walk, no duplicates, no omissions. An empty repo yields an empty slice.
    var ms = MemStore.init(t.allocator);
    defer ms.deinit();
    var rs = RepoState.init(t.allocator, ms.store());
    defer rs.deinit();

    const empty = try rs.checkinsByMtime(t.allocator);
    defer t.allocator.free(empty);
    try t.expectEqual(@as(usize, 0), empty.len);

    const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
    const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
    const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
    const order = try rs.checkinsByMtime(t.allocator);
    defer t.allocator.free(order);
    try t.expectEqual(rs.events.count(), order.len);
    // Each event rid appears exactly once (count each; no phantom, no dup).
    for ([_]Rid{ ra, rb, rc }) |want| {
        var seen: usize = 0;
        for (order) |got| {
            if (got == want) seen += 1;
        }
        try t.expectEqual(@as(usize, 1), seen);
    }
}

test "repostate: checkinsByMtime survives allocation failure without leaking" {
    // A public allocating query only ever fails with OutOfMemory and frees every
    // partial allocation on the way out (the errdefer/deinit discipline).
    const Ctx = struct {
        fn run(gpa: std.mem.Allocator) !void {
            var ms = MemStore.init(gpa);
            defer ms.deinit();
            var rs = RepoState.init(gpa, ms.store());
            defer rs.deinit();
            _ = try rs.crosslink(.{ .hash = h_a, .mtime = 3 });
            _ = try rs.crosslink(.{ .hash = h_b, .mtime = 1 });
            const order = try rs.checkinsByMtime(gpa);
            gpa.free(order);
        }
    };
    try t.checkAllAllocationFailures(t.allocator, Ctx.run, .{});
}