Artifact [377c59a770]

Artifact 377c59a770decebaf0d99941b15436639fac8ab890bb49d28acc3a1e6e3e5687:

• File src/dst.zig — part of check-in [5c445bb3f3] at 2026-09-28 02:39:03 on branch trunk — Take the writer lock inside LogStore.open and test the lock class

  LogStore.open now takes the exclusive lock before it reads the file's length and scans for the end, and a read-only handle refuses to append. purge undo opens the store through the shared writer path.

  A new DST sweep runs two to four writers interleaved against one log through a file that models the lock. It flags unlocked or misplaced appends as they happen, checks each writer sees everything committed before it locked and reads back its own writes, including deltas. A source check fails on any write-mode open of the store outside openStoreAppend. An e2e test races commits, tags and user-table writes on one store and counts what landed. (user: dmestas, size: 38453) [annotate] [blame] [check-ins using]

//! Deterministic simulation of the repository-state derivation.
//!
//! `zig build dst` runs the fast pre-commit GATE sweep (a few seeds, a few
//! thousand steps each — seconds, not minutes: the per-step oracle recompute
//! is linear in the live check-in count, so the gate stays small and DEEP
//! sweeps run out-of-band via `zig build dst -- --seeds K [--steps M]`).
//! `zig build dst -- --seed N [--steps M]` replays one seed and `--seeds K`
//! sweeps 1..K. One `std.Random.DefaultPrng.init(seed)` is the
//! sole entropy source of a run — the seed is the whole universe — so any
//! failure replays exactly from the printed `reproduce with seed=N` line.
//!
//! Phase 1 (safety), every step: crosslink one generated record and assert
//! the leaf table equals the oracle's brute-force recompute of the
//! normative leaf test (repo-state Section 7.2), over the public API only.
//! Phase 2 (liveness): assert the incrementally maintained leaf table
//! equals a full rebuild (Section 7.3), replay the record log in permuted
//! orders — exhaustively when the log holds at most 5 records, else three
//! sampled shuffles — asserting an identical leaf set by hash, and run a
//! fixed four-record fork/merge scenario through every insertion order.

const std = @import("std");
const zit = @import("zit");
const repostate = zit.repostate;
const repoimage = zit.repoimage;
const gen_mod = @import("sim/gen.zig");
const oracle_mod = @import("sim/oracle.zig");
const storage_sweep = @import("sim/storage_sweep.zig");
const sync_sweep = @import("sim/sync_sweep.zig");
const checkout_sweep = @import("sim/checkout_sweep.zig");
const assembly_sweep = @import("sim/assembly_sweep.zig");
const shun_sweep = @import("sim/shun_sweep.zig");
/// Independent lock-sweep histories per seed.
const lock_sweep_rounds = 8;
const lock_sweep = @import("sim/lock_sweep.zig");

test {
    // storage/logstore/checkout and logstore_test are now folded into the `zit`
    // module and aggregate through root.zig; dst.zig only carries its sim
    // collaborators (external to that module) and the sibling fuzz targets.
    _ = @import("sim/faulty_file.zig");
    _ = @import("sim/storage_sweep.zig");
    _ = @import("sim/net.zig");
    _ = @import("sim/sync_gen.zig");
    _ = @import("sim/sync_sweep.zig");
    _ = @import("sim/checkout_sweep.zig");
    _ = @import("sim/checkpoint_sweep.zig");
    _ = @import("sim/assembly_sweep.zig");
    _ = @import("sim/shun_sweep.zig");
    _ = @import("sim/lock_sweep.zig");
    // Sibling fuzz targets aggregate into `zig build test` here: this root
    // carries the `zit` dep (sync_fuzz) and reaches logstore/storage/sim
    // relatively (logstore_fuzz), which root.zig cannot.
    _ = @import("sync_fuzz.zig");
    _ = @import("logstore_fuzz.zig");
    // The CLI-layer wire-surface targets: this root reaches serve.zig and
    // transport.zig relatively (they are outside the `zit` module) while
    // carrying the `zit` dep those two files import.
    _ = @import("transport_fuzz.zig");
    _ = @import("serve_fuzz.zig");
    // The three-way line merge's algebraic laws. Same reason as the two above:
    // merge3.zig lives outside the `zit` module, so this root is where its
    // fuzz target's smoke tests can reach it relatively.
    _ = @import("merge3_fuzz.zig");
    // The runner itself, for its registration pin only: `zig build fuzz` has
    // no test step, so this is the only place that pin can run.
    _ = @import("fuzz_tests.zig");
}

// Pre-commit GATE budget: kept to seconds. The per-step oracle recompute is
// linear in the live check-in count, so wall-clock is ~linear in steps*seeds;
// deep coverage (dozens/hundreds of seeds x 10k steps) runs out-of-band.
const default_steps: usize = 1_000;
const default_sweep_seeds: u64 = 6;
/// Log sizes at or below this replay every permutation; larger logs get
/// `sampled_shuffles` PRNG-sampled orders instead (5! = 120 replays max).
const exhaustive_max = 5;
const sampled_shuffles = 3;

const Failure = error{
    OutOfMemory,
    LeafMismatch,
    LeafTableDrift,
    OpenLeafMismatch,
    RebuildMismatch,
    OrderDependence,
    NameResolutionMismatch,
    ImageMismatch,
    BranchListMismatch,
    AmbiguityMismatch,
    WalkMismatch,
    // Storage sweep (storage-track-plan.md §B — native design, no RFC).
    Io,
    MissingAcknowledged,
    PhantomFrame,
    IndexMismatch,
    HashMismatch,
    SilentCorruption,
    ConfigMismatch,
    // Lock sweep: concurrent writers against one log.
    UnlockedWrite,
    OverwroteFrames,
    LockSweepCorrupt,
    StaleView,
};

/// A name never emitted by the generator: probes resolveName/openLeafOf's
/// NotFound/null case every step alongside the branch names in use.
const absent_branch_name = "no-such-branch";
/// The full set of names probed every step and after every replay order.
const check_names = gen_mod.branch_names ++ [_][]const u8{absent_branch_name};

pub fn main(init: std.process.Init) !void {
    const gpa = init.gpa;
    const args = try init.minimal.args.toSlice(init.arena.allocator());

    var stderr_buffer: [1024]u8 = undefined;
    var stderr_writer: std.Io.File.Writer = .init(.stderr(), init.io, &stderr_buffer);
    const out = &stderr_writer.interface;

    var seed_arg: ?u64 = null;
    var seeds_arg: ?u64 = null;
    var steps: usize = default_steps;
    parseFlags(args[1..], &seed_arg, &seeds_arg, &steps) catch |e| {
        try out.print("dst: {s}\n", .{@errorName(e)});
        try out.writeAll("usage: zig build dst -- [--seed N | --seeds K] [--steps M]\n");
        try out.flush();
        std.process.exit(2);
    };

    const first: u64 = if (seed_arg) |s| s else 1;
    const total: u64 = if (seed_arg != null) 1 else seeds_arg orelse default_sweep_seeds;

    // The checkout crash-recovery sweep drives the real filesystem, so it needs a
    // process directory to make throwaway workspaces under (the in-memory sweeps
    // do not). One root for the whole run, cleaned up at the end.
    const cwd = std.Io.Dir.cwd();
    const checkout_root_name = ".zit-dst-checkout-ws";
    cwd.deleteTree(init.io, checkout_root_name) catch {};
    cwd.createDir(init.io, checkout_root_name, .default_dir) catch |e| {
        try out.print("checkout-dst: {s}\n", .{@errorName(e)});
        try out.flush();
        std.process.exit(1);
    };
    var checkout_root = cwd.openDir(init.io, checkout_root_name, .{ .access_sub_paths = true, .follow_symlinks = false }) catch |e| {
        try out.print("checkout-dst: {s}\n", .{@errorName(e)});
        try out.flush();
        std.process.exit(1);
    };
    defer {
        checkout_root.close(init.io);
        cwd.deleteTree(init.io, checkout_root_name) catch {};
    }

    var i: u64 = 0;
    while (i < total) : (i += 1) {
        const seed = first + i;
        runSeed(gpa, seed, steps) catch |e| {
            try out.print("dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // H10 (TEST-HARDENING §2) equal-mtime tie sweep: the same repostate
        // simulation under the tie-permitting generator, so the B1 same-second
        // tie-break (descendant-before-ancestor, then least hash) is fuzzed,
        // not just example-tested. Additional per-seed coverage — the
        // unique-mtime sweep above is unchanged. Shares the reproduce line.
        simulate(gpa, seed, steps, .ties) catch |e| {
            try out.print("dst-ties: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // The sync SimNet sweep is the PRIMARY sync DST (transport-simnet-plan.md
        // §A3): it joins the same per-seed gate. Its own closed error set stays
        // separate from the repostate Failure set; the reproduce line is shared.
        sync_sweep.runSeed(gpa, seed) catch |e| {
            try out.print("sync-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // The working-tree crash-recovery sweep (H2): joins the same per-seed gate
        // over the real directory surface. Its own closed error set; shared
        // reproduce line.
        checkout_sweep.run(gpa, init.io, checkout_root, seed) catch |e| {
            try out.print("checkout-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // H3 (TEST-HARDENING §2) crash-during-sync composition: the sync sweep
        // over a client store that can tear, with seeded mid-persist crash+resume.
        // Same per-seed gate; shares the reproduce line.
        sync_sweep.runCrashResume(gpa, seed) catch |e| {
            try out.print("sync-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // H7 (TEST-HARDENING §2) degraded-network liveness: a fresh session must
        // converge under a sustained, never-healed drop/dup wire within a
        // loss-scaled window. The GATE runs the single small p; the H1 soak
        // sweeps the wider `soak_degraded_pcts` via runDegradedSweep. Same
        // per-seed gate; shares the reproduce line.
        sync_sweep.runDegraded(gpa, seed) catch |e| {
            try out.print("sync-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // draft-fossil-submanifests-00 §7: the sub-manifest convergence lane —
        // a seeded tree whose closure arrives level by level must converge
        // within §7.1's `depth + 1` pull rounds, never present a partial file
        // set (§5.2), drain its §7.3/§9.4 deferral record, and reproduce the
        // same enumeration through the §7.4 memo. Its own closed error set;
        // shares the reproduce line.
        sync_sweep.runTreeSeed(gpa, seed) catch |e| {
            try out.print("submanifest-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // The artifact-assembly sweep: the §4 unclassifiable-
        // artifact verify-then-skip split, driven at the LogStore→state layer
        // with an independent card-legality oracle. Its own closed error set
        // and disjoint PRNG stream off the same seed; shares the reproduce line.
        assembly_sweep.run(gpa, seed) catch |e| {
            try out.print("assembly-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
        // S7: the shun+reclaim crash sweep. It drives `rewriteAndSwap` over the
        // real directory surface, so it shares the checkout sweep's process
        // workspace root. Its own closed error set; shared reproduce line.
        shun_sweep.run(gpa, init.io, checkout_root, seed) catch |e| {
            try out.print("shun-dst: {s}\n", .{@errorName(e)});
            try out.print("reproduce with seed={d}\n", .{seed});
            try out.flush();
            std.process.exit(1);
        };
    }
    try out.print("dst: {d} seed(s) x {d} steps ok\n", .{ total, steps });
    try out.flush();
}

/// Parse `[--seed N] [--seeds K] [--steps M]` in any order. `--seed` and
/// `--seeds` are mutually exclusive; an unknown flag or missing value is an
/// explicit error, never ignored.
fn parseFlags(args: []const []const u8, seed: *?u64, seeds: *?u64, steps: *usize) !void {
    var i: usize = 0;
    while (i < args.len) : (i += 1) {
        if (std.mem.eql(u8, args[i], "--seed")) {
            i += 1;
            if (i >= args.len) return error.MissingSeedValue;
            seed.* = try std.fmt.parseInt(u64, args[i], 0);
        } else if (std.mem.eql(u8, args[i], "--seeds")) {
            i += 1;
            if (i >= args.len) return error.MissingSeedsValue;
            seeds.* = try std.fmt.parseInt(u64, args[i], 0);
        } else if (std.mem.eql(u8, args[i], "--steps")) {
            i += 1;
            if (i >= args.len) return error.MissingStepsValue;
            steps.* = try std.fmt.parseInt(usize, args[i], 0);
        } else {
            return error.UnknownArgument;
        }
    }
    if (seed.* != null and seeds.* != null) return error.SeedAndSeedsExclusive;
}

/// Generator clock discipline for a repostate simulation run.
/// `.unique` — strictly increasing, unique mtimes (the original universe).
/// `.ties` — the H10 tie-permitting generator, so equal-mtime runs exercise
/// the B1 same-second tie-break (descendant-before-ancestor, then least
/// hash; repostate.zig:1429, repostate_test.zig REGRESSION B1).
const Mode = enum { unique, ties };

/// Tie-mode knobs (TEST-HARDENING §2 H10). `tie_prob`-in-100 per check-in
/// reuses the previous mtime; a run holds at most `tie_run_max` reuses, so
/// ties cluster into short equal-mtime chains rather than an unbounded
/// same-second pile-up. Chosen so ties (and thus the tie-break) recur every
/// few steps while the gate stays in seconds.
const tie_prob: u8 = 35;
const tie_run_max: u32 = 3;

/// One repository-state simulation run: the generated op stream (Phase 1
/// safety, per-step oracle agreement) and the Phase 2 liveness/replay checks.
/// `mode` selects the generator's clock discipline. Extracted from `runSeed`
/// so the same body serves both the unique-mtime gate seed and the additional
/// H10 tie-mode seed.
fn simulate(gpa: std.mem.Allocator, seed: u64, steps: usize, mode: Mode) Failure!void {
    var prng = std.Random.DefaultPrng.init(seed);
    const random = prng.random();

    var store = repostate.MemStore.init(gpa);
    defer store.deinit();
    var rs = repostate.RepoState.init(gpa, store.store());
    defer rs.deinit();
    var oracle = oracle_mod.Oracle.init(gpa);
    defer oracle.deinit();
    var gen = switch (mode) {
        .unique => gen_mod.Gen.init(gpa, random),
        .ties => gen_mod.Gen.initTies(gpa, random, tie_prob, tie_run_max),
    };
    defer gen.deinit();

    // The oracle's slot order is its own; keep the matching rid per slot so
    // the per-step comparison stays cheap.
    var rids: std.ArrayList(repostate.Rid) = .empty;
    defer rids.deinit(gpa);
    var flags: [gen_mod.max_checkins]bool = undefined;
    var open_flags: [gen_mod.max_checkins]bool = undefined;

    // Phase 1: safety under the generated op stream, checked every step.
    var step: usize = 0;
    while (step < steps) : (step += 1) {
        const rec = try gen.next();
        _ = try rs.crosslink(rec);
        try oracle.apply(rec);
        std.debug.assert(oracle.count() <= gen_mod.max_checkins);
        while (rids.items.len < oracle.count()) {
            try rids.append(gpa, try store.store().intern(oracle.hashAt(rids.items.len)));
        }
        try checkLeaves(&rs, rids.items, &oracle, flags[0..oracle.count()]);
        try checkOpenLeaves(&rs, rids.items, &oracle, open_flags[0..oracle.count()]);
        // Invariants (b)/(c): reuse `flags`, which checkLeaves just filled
        // with the raw (non-open) leaf recompute — exactly what
        // Oracle.openLeafOf's leaf_flags parameter expects.
        try checkNameResolution(&rs, rids.items, &oracle);
        try checkOpenLeafOf(&rs, rids.items, &oracle, flags[0..oracle.count()]);
        // Invariants (e)-(h): batch 8's §6.3/§7.5/§8.3-8.4 derivation
        // surface. `flags` still holds the raw leaf recompute from
        // checkLeaves above, unchanged by the calls in between.
        try checkAmbiguousLeaves(&rs, rids.items, &oracle, flags[0..oracle.count()]);
        try checkTip(&rs, rids.items, &oracle);
        try checkWalkForms(&rs, rids.items, &oracle);
        // §6.3 branch listing: under an equal-mtime tie the representative is
        // FIRST-SEEN / implementation-defined in production (repostate.zig:1215,
        // deliberately not the B1 total rule), so the oracle cannot mirror it
        // deterministically in tie mode. The unique sweep still pins it exactly.
        if (mode == .unique) try checkBranches(gpa, &rs, rids.items, &oracle);
    }

    // Phase 2: liveness. No pending rechecks remain (crosslink batch-applies
    // its schedule), so the incremental table must equal a full rebuild.
    try checkRebuildMatches(gpa, &rs);
    try checkOrderIndependence(gpa, gen.log(), random);
    try checkImageRoundTrip(gpa, &rs, rids.items);
    try fixedScenario(gpa);
}

fn runSeed(gpa: std.mem.Allocator, seed: u64, steps: usize) Failure!void {
    try simulate(gpa, seed, steps, .unique);

    // Storage-engine sweep (storage-track-plan.md §B): an independent
    // subsystem with its own PRNG stream off the same seed, so it neither
    // reads nor perturbs the repostate simulation above.
    try storage_sweep.run(gpa, seed, steps);

    // The writer lock: several writers interleaved against one log through a
    // file that models the lock, flagging an unlocked write or an append over
    // another writer's frames the moment it happens. The storage sweep's one
    // writer never contends for the lock, so it cannot see this class. Each
    // round is a fresh file and a fresh set of writers: the damaging schedules
    // (two writers that stat before either takes the lock) come early in a
    // file's life, so several short histories find them far more reliably
    // than one long one.
    var round: u64 = 0;
    while (round < lock_sweep_rounds) : (round += 1) {
        try lock_sweep.run(gpa, seed *% lock_sweep_rounds +% round, steps);
    }

    // Step-2 (§5/§7.2) delta-base-policy equivalence: a naive full-form store
    // and a pickBase best-of-N store decode byte-identical for every artifact
    // (subsuming identical repostate/current-trunk-hash views). Its own PRNG
    // stream off the same seed; replays from the shared reproduce line.
    try storage_sweep.pickBaseEquivalence(gpa, seed);

    // Step-3 (§6.1/§7.2-§7.3) pack-redeltify equivalence: a naive full-form
    // store and a `zit.pack.packLog`-repacked copy of a production-shaped source
    // (verbatim wire deltas over poor bases + check-in manifests) decode
    // byte-identical for every artifact, trunk tip preserved, config carried
    // through. Its own disjoint PRNG stream off the same seed.
    try storage_sweep.packRedeltifyEquivalence(gpa, seed);

    // Step-4 (§6.2/§7.2-§7.3) same-path pack equivalence: multiple interleaved
    // tracked files push each file's earlier version OUT of the bounded
    // chronological window of its later version, so pack reaches the ideal base
    // only through the §6.2 same-path manifest walk. Every artifact must still
    // decode byte-identical across a naive full-form store and the repacked copy,
    // trunk tip preserved. Its own disjoint PRNG stream off the same seed.
    try storage_sweep.packSamePathEquivalence(gpa, seed);

    // H8 (TEST-HARDENING §2 H8) online read-fault injection: after a healthy
    // open, latent bit rot (`read_rot_pct`) surfacing at content()-time must be
    // detected — every known hash reads back its exact bytes or a declared
    // corruption error, never wrong bytes as success. The append read path
    // re-verifies each frame per read, so the rot is caught. Its own disjoint
    // PRNG stream off the same seed.
    try storage_sweep.readRotSweep(gpa, seed);
}

/// Invariant (a): the leaf table equals the oracle's recompute — same
/// membership per known hash, and no extra rows.
fn checkLeaves(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
    flags: []bool,
) Failure!void {
    oracle.leafFlags(flags);
    var expected_total: usize = 0;
    for (flags, rids) |flag, rid| {
        if (flag) expected_total += 1;
        if (rs.isLeaf(rid) != flag) return error.LeafMismatch;
    }
    var it = rs.leaves();
    var actual: usize = 0;
    while (it.next()) |_| actual += 1;
    if (actual != expected_total) return error.LeafTableDrift;
}

/// Image round-trip: a `repoimage` materialized from the DST-proven derived
/// state must be query-equivalent to it — the same leaf set/order (§7.1), event
/// times (§7.5/§8.3), open predicate (§7.4), branch-of (§6.1), name resolution
/// (§8.2), hash, and lookup, for every rid the run produced. Because the op
/// stream is random and the derived state has already been checked against the
/// oracle each step, this pins that the memo cannot violate any invariant the
/// derivation owns.
fn checkImageRoundTrip(gpa: std.mem.Allocator, rs: *const repostate.RepoState, rids: []const repostate.Rid) Failure!void {
    const mb = "trunk";
    var body: std.ArrayList(u8) = .empty;
    defer body.deinit(gpa);
    try repoimage.serialize(gpa, rs, mb, &body);
    var img = (repoimage.Image.load(gpa, body.items) catch return error.OutOfMemory) orelse return error.ImageMismatch;
    defer img.deinit(gpa);

    if (img.count() != rs.store.count()) return error.ImageMismatch;
    // Leaf set AND iteration order.
    var di = rs.leaves();
    const il = img.leafRids();
    var k: usize = 0;
    while (di.next()) |lr| : (k += 1) {
        if (k >= il.len or il[k] != lr) return error.ImageMismatch;
    }
    if (k != il.len) return error.ImageMismatch;

    for (rids) |rid| {
        if (!std.meta.eql(rs.mtimeOf(rid), img.mtimeOf(rid))) return error.ImageMismatch;
        if (rs.isLeaf(rid) != img.isLeaf(rid)) return error.ImageMismatch;
        if (rs.isOpenLeaf(rid) != img.isOpenLeaf(rid)) return error.ImageMismatch;
        if (!std.mem.eql(u8, rs.store.hashOf(rid), img.hashOf(rid))) return error.ImageMismatch;
        if (img.lookup(rs.store.hashOf(rid)) != rid) return error.ImageMismatch;
        if (rs.mtimeOf(rid) != null and !std.mem.eql(u8, rs.branchOf(rid, mb), img.branchOf(rid, mb))) return error.ImageMismatch;
    }

    // §8.2 name resolution: every probed name resolves identically.
    for (check_names) |name| {
        // An allocation failure is an abort, never a mismatch verdict.
        const want = rs.resolveName(name) catch |e| switch (e) {
            error.NotFound => null,
            error.OutOfMemory => return error.OutOfMemory,
        };
        const got = img.resolveName(name);
        if (!std.meta.eql(want, got)) return error.ImageMismatch;
    }
}

/// Invariant (d): isOpenLeaf equals the oracle's open-leaf recompute
/// (repo-state Section 7.4) for every known rid.
fn checkOpenLeaves(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
    flags: []bool,
) Failure!void {
    oracle.openLeafFlags(flags);
    for (flags, rids) |flag, rid| {
        if (rs.isOpenLeaf(rid) != flag) return error.OpenLeafMismatch;
    }
}

/// Invariant (b): resolveName agrees with the oracle's brute-force
/// max-mtime scan (Section 8.2), for every generated branch name plus one
/// name the generator never emits (the NotFound case).
fn checkNameResolution(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
) Failure!void {
    for (check_names) |name| {
        // An allocation failure is an abort, never a mismatch verdict.
        const got = rs.resolveName(name) catch |e| switch (e) {
            error.NotFound => null,
            error.OutOfMemory => return error.OutOfMemory,
        };
        const want_slot = try oracle.resolveName(name);
        const want: ?repostate.Rid = if (want_slot) |slot| rids[slot] else null;
        if (got != want) return error.NameResolutionMismatch;
    }
}

/// Invariant (c): openLeafOf agrees with the oracle's brute-force
/// three-condition scan (Section 9), for the same name set as (b). `flags`
/// is the raw (non-open) leaf recompute Oracle.openLeafOf expects.
fn checkOpenLeafOf(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
    flags: []const bool,
) Failure!void {
    for (check_names) |name| {
        const got = try rs.openLeafOf(name);
        const want_slot = try oracle.openLeafOf(name, flags);
        const want: ?repostate.Rid = if (want_slot) |slot| rids[slot] else null;
        if (got != want) return error.OpenLeafMismatch;
    }
}

/// Invariant (e): isAmbiguousLeaf agrees with the oracle's brute-force
/// leaf-and-open-sibling scan (repo-state Section 7.5), for every known
/// rid. `flags` is the raw (non-open) leaf recompute `Oracle.isAmbiguousLeaf`
/// expects.
fn checkAmbiguousLeaves(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
    flags: []const bool,
) Failure!void {
    for (rids, 0..) |rid, i| {
        const want = oracle.isAmbiguousLeaf(@intCast(i), flags);
        if (rs.isAmbiguousLeaf(rid) != want) return error.AmbiguityMismatch;
    }
}

/// Invariant (f): `resolve("tip", .checkin)` agrees with the oracle's
/// brute-force global-maximum-mtime scan (Section 8.3 form 3).
fn checkTip(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
) Failure!void {
    const want_slot = try oracle.tipSlot();
    const want: ?repostate.Rid = if (want_slot) |s| rids[s] else null;
    const got: ?repostate.Rid = rs.resolve("tip", .checkin) catch |e| switch (e) {
        error.NotFound => null,
        error.Ambiguous => return error.WalkMismatch,
        error.OutOfMemory => return error.OutOfMemory,
    };
    if (got != want) return error.WalkMismatch;
}

/// Writes `prefix ++ name` into `buf`, returning the written slice. 96
/// comfortably bounds "start:"/"root:" (6/5 bytes) plus the longest
/// generator branch name ("feature", 7 bytes), so the assert is provably
/// dead against every caller here.
fn prefixedName(buf: []u8, prefix: []const u8, name: []const u8) []const u8 {
    std.debug.assert(prefix.len + name.len <= buf.len);
    @memcpy(buf[0..prefix.len], prefix);
    @memcpy(buf[prefix.len..][0..name.len], name);
    return buf[0 .. prefix.len + name.len];
}

/// Invariant (g): `resolve("start:"++name, .checkin)` and
/// `resolve("root:"++name, .checkin)` agree with the oracle's brute-force
/// primary-parent walk (Section 8.4), for each generator branch name with
/// a resolvable carrier this step.
fn checkWalkForms(
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
) Failure!void {
    for (gen_mod.branch_names) |name| {
        const base_slot = (try oracle.resolveName(name)) orelse continue;
        var buf: [96]u8 = undefined;
        const start_name = prefixedName(&buf, "start:", name);
        const got_start = rs.resolve(start_name, .checkin) catch |e| switch (e) {
            error.OutOfMemory => return error.OutOfMemory,
            else => return error.WalkMismatch,
        };
        const want_start = rids[oracle.branchWalk(base_slot, .earliest_on_branch)];
        if (got_start != want_start) return error.WalkMismatch;

        var buf2: [96]u8 = undefined;
        const root_name = prefixedName(&buf2, "root:", name);
        const got_root = rs.resolve(root_name, .checkin) catch |e| switch (e) {
            error.OutOfMemory => return error.OutOfMemory,
            else => return error.WalkMismatch,
        };
        const want_root = rids[oracle.branchWalk(base_slot, .first_off_branch)];
        if (got_root != want_root) return error.WalkMismatch;
    }
}

/// Invariant (h): `rs.branches()` agrees with the oracle's brute-force
/// grouping (Section 6.3) — same set of names, each with the same
/// representative rid, mtime, member count, and closed status.
fn checkBranches(
    gpa: std.mem.Allocator,
    rs: *const repostate.RepoState,
    rids: []const repostate.Rid,
    oracle: *const oracle_mod.Oracle,
) Failure!void {
    const got = try rs.branches(gpa);
    defer gpa.free(got);
    const want = try oracle.branchGroups(gpa);
    defer gpa.free(want);
    if (got.len != want.len) return error.BranchListMismatch;
    for (want) |w| {
        var found = false;
        for (got) |g| {
            if (!std.mem.eql(u8, g.name, w.name)) continue;
            found = true;
            if (g.tip != rids[w.rep] or g.mtime != w.mtime or g.count != w.count or g.closed != w.closed) {
                return error.BranchListMismatch;
            }
            break;
        }
        if (!found) return error.BranchListMismatch;
    }
}

/// Section 7.3: the incrementally maintained leaf table must match a
/// from-scratch full rebuild exactly.
fn checkRebuildMatches(gpa: std.mem.Allocator, rs: *repostate.RepoState) Failure!void {
    const before = try collectLeafRids(gpa, rs);
    defer gpa.free(before);
    try rs.rebuildLeaves();
    const after = try collectLeafRids(gpa, rs);
    defer gpa.free(after);
    if (!std.mem.eql(repostate.Rid, before, after)) return error.RebuildMismatch;
}

fn collectLeafRids(gpa: std.mem.Allocator, rs: *const repostate.RepoState) error{OutOfMemory}![]repostate.Rid {
    var list: std.ArrayList(repostate.Rid) = .empty;
    errdefer list.deinit(gpa);
    var it = rs.leaves();
    while (it.next()) |rid| try list.append(gpa, rid);
    const slice = try list.toOwnedSlice(gpa);
    std.mem.sort(repostate.Rid, slice, {}, std.sort.asc(repostate.Rid));
    return slice;
}

/// Derivation must not depend on crosslink order: rids differ across
/// orders, so replays are compared by leaf and open-leaf hash set, plus the
/// per-name resolved hash (Section 8.2). Two dimensions stay comparable under
/// EVERY generator mode: the leaf set is purely structural (edges + branch
/// values, mtime-independent), and name resolution's equal-mtime tie-break is
/// TOTAL (descendant-before-ancestor, then least hash — repostate.zig:1605),
/// so a replay that disagrees on either is a real order dependency, not a fair
/// tie. This is the H10 order-independence choice (b): compare replays up to
/// that documented total rule.
///
/// The open-leaf SET is the one dimension that is NOT total under ties: it
/// turns on the §5.3 closed-tag direct-application supersede, whose equal-mtime
/// behaviour is a `>=`-skip — first-application-wins, hence order-dependent and
/// implementation-defined (repostate_test.zig:2520). So when the log holds an
/// equal-mtime tie, the open-leaf comparison is skipped (the (a) fallback,
/// scoped to just this non-total dimension); with unique mtimes it is compared
/// exactly as before. Phantom arrival order (Section 4.2 step 1) is exercised
/// by every child-before-parent permutation.
fn checkOrderIndependence(gpa: std.mem.Allocator, log: []const repostate.Record, random: std.Random) Failure!void {
    // A tie makes the open-leaf set order-dependent by design (see above);
    // detect one so the replay compares only the order-independent dimensions.
    var has_ties = false;
    outer: for (log, 0..) |a, i| {
        for (log[i + 1 ..]) |b| {
            if (a.mtime == b.mtime) {
                has_ties = true;
                break :outer;
            }
        }
    }
    const compare_open = !has_ties;

    var baseline_store = repostate.MemStore.init(gpa);
    defer baseline_store.deinit();
    var baseline_rs = repostate.RepoState.init(gpa, baseline_store.store());
    defer baseline_rs.deinit();
    for (log) |rec| _ = try baseline_rs.crosslink(rec);
    const baseline = try collectLeafHashes(gpa, &baseline_rs, baseline_store.store());
    defer gpa.free(baseline);
    const baseline_open = try collectOpenLeafHashes(gpa, &baseline_rs, baseline_store.store());
    defer gpa.free(baseline_open);
    var baseline_resolve: [check_names.len]?[]const u8 = undefined;
    for (check_names, 0..) |name, i| {
        baseline_resolve[i] = resolvedHash(&baseline_rs, baseline_store.store(), name);
    }

    const order = try gpa.alloc(usize, log.len);
    defer gpa.free(order);
    for (order, 0..) |*slot, i| slot.* = i;

    if (log.len <= exhaustive_max) {
        var permutations: usize = 0;
        while (true) {
            try replayAndCompare(gpa, log, order, baseline, baseline_open, &baseline_resolve, compare_open);
            permutations += 1;
            std.debug.assert(permutations <= 120); // 5! orders at most
            if (!nextPermutation(order)) break;
        }
    } else {
        for (0..sampled_shuffles) |_| {
            random.shuffle(usize, order);
            try replayAndCompare(gpa, log, order, baseline, baseline_open, &baseline_resolve, compare_open);
        }
    }
}

/// `name` resolved against `rs`, as a hash rather than a rid so it compares
/// across replays that assign rids differently. The returned slice points
/// into `store`, which must outlive the result.
fn resolvedHash(rs: *const repostate.RepoState, store: repostate.ArtifactStore, name: []const u8) ?[]const u8 {
    const rid = rs.resolveName(name) catch return null;
    return store.hashOf(rid);
}

/// A fixed fork/merge graph replayed through all 24 insertion orders:
/// root A; children B and C of A; merge D with parents (B, C). The leaf
/// set must always be exactly {D} — C's only child arrives via a merge
/// edge, which still disqualifies it (Section 7.2), and out-of-order
/// arrival resolves through phantoms (Section 4.2 step 1).
fn fixedScenario(gpa: std.mem.Allocator) Failure!void {
    const ha = "a" ** 64;
    const hb = "b" ** 64;
    const hc = "c" ** 64;
    const hd = "d" ** 64;
    const log = [_]repostate.Record{
        .{ .hash = ha, .mtime = 1 },
        .{ .hash = hb, .mtime = 2, .parents = &.{ha} },
        .{ .hash = hc, .mtime = 3, .parents = &.{ha} },
        .{ .hash = hd, .mtime = 4, .parents = &.{ hb, hc } },
    };
    // No closed tags in this fixed scenario, so the open-leaf set equals
    // the leaf set, and no branch tag means every name resolution is
    // NotFound (null) regardless of order.
    const expected = [_][]const u8{hd};
    const expected_resolve = [_]?[]const u8{null} ** check_names.len;
    var order = [_]usize{ 0, 1, 2, 3 };
    var permutations: usize = 0;
    while (true) {
        try replayAndCompare(gpa, &log, &order, &expected, &expected, &expected_resolve, true);
        permutations += 1;
        std.debug.assert(permutations <= 24); // 4! orders
        if (!nextPermutation(&order)) break;
    }
    std.debug.assert(permutations == 24);
}

/// Replay `log[order]` into a fresh state and compare its leaf hash set,
/// open-leaf hash set, and per-name resolved hash (`check_names` order)
/// against `expected`/`expected_open`/`expected_resolve`. When `compare_open`
/// is false the open-leaf comparison is skipped — the caller has detected an
/// equal-mtime tie, which makes the open-leaf set implementation-defined
/// (§5.3 supersede; see `checkOrderIndependence`). The leaf set and name
/// resolution stay comparable regardless.
fn replayAndCompare(
    gpa: std.mem.Allocator,
    log: []const repostate.Record,
    order: []const usize,
    expected: []const []const u8,
    expected_open: []const []const u8,
    expected_resolve: []const ?[]const u8,
    compare_open: bool,
) Failure!void {
    var store = repostate.MemStore.init(gpa);
    defer store.deinit();
    var rs = repostate.RepoState.init(gpa, store.store());
    defer rs.deinit();
    for (order) |i| _ = try rs.crosslink(log[i]);
    const got = try collectLeafHashes(gpa, &rs, store.store());
    defer gpa.free(got);
    if (got.len != expected.len) return error.OrderDependence;
    for (got, expected) |a, b| {
        if (!std.mem.eql(u8, a, b)) return error.OrderDependence;
    }
    if (compare_open) {
        const got_open = try collectOpenLeafHashes(gpa, &rs, store.store());
        defer gpa.free(got_open);
        if (got_open.len != expected_open.len) return error.OrderDependence;
        for (got_open, expected_open) |a, b| {
            if (!std.mem.eql(u8, a, b)) return error.OrderDependence;
        }
    }
    for (check_names, expected_resolve) |name, want| {
        const got_resolve = resolvedHash(&rs, store.store(), name);
        if (!hashOptEql(got_resolve, want)) return error.OrderDependence;
    }
}

fn hashOptEql(a: ?[]const u8, b: ?[]const u8) bool {
    if (a == null or b == null) return a == null and b == null;
    return std.mem.eql(u8, a.?, b.?);
}

/// The leaf set as hashes, sorted lexically. The returned slices point
/// into `store`, which must outlive the result.
fn collectLeafHashes(
    gpa: std.mem.Allocator,
    rs: *const repostate.RepoState,
    store: repostate.ArtifactStore,
) error{OutOfMemory}![][]const u8 {
    var list: std.ArrayList([]const u8) = .empty;
    errdefer list.deinit(gpa);
    var it = rs.leaves();
    while (it.next()) |rid| try list.append(gpa, store.hashOf(rid));
    const slice = try list.toOwnedSlice(gpa);
    std.mem.sort([]const u8, slice, {}, hashLessThan);
    return slice;
}

/// The open-leaf set as hashes, sorted lexically (Section 7.4).
fn collectOpenLeafHashes(
    gpa: std.mem.Allocator,
    rs: *const repostate.RepoState,
    store: repostate.ArtifactStore,
) error{OutOfMemory}![][]const u8 {
    var list: std.ArrayList([]const u8) = .empty;
    errdefer list.deinit(gpa);
    var it = rs.leaves();
    while (it.next()) |rid| {
        if (rs.isOpenLeaf(rid)) try list.append(gpa, store.hashOf(rid));
    }
    const slice = try list.toOwnedSlice(gpa);
    std.mem.sort([]const u8, slice, {}, hashLessThan);
    return slice;
}

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

/// Advance `order` to the next lexicographic permutation; false once the
/// last permutation has been visited.
fn nextPermutation(order: []usize) bool {
    if (order.len < 2) return false;
    var i = order.len - 1;
    while (i > 0 and order[i - 1] >= order[i]) i -= 1;
    if (i == 0) return false;
    var j = order.len - 1;
    while (order[j] <= order[i - 1]) j -= 1;
    std.mem.swap(usize, &order[i - 1], &order[j]);
    std.mem.reverse(usize, order[i..]);
    return true;
}