Artifact [9ffc65e9bf]

Artifact 9ffc65e9bfcdecc91f077637ce89cb4157ba374c291b7a4642884d941f70bd4f:

• File src/dst.zig — part of check-in [464b82c888] at 2026-07-20 04:37:48 on branch h7-degraded — Prove sync liveness under a degraded, never-healed wire

  The sync sweep proved convergence only after the network fully healed, so a protocol that converges on a perfect wire but livelocks under sustained loss would still pass.

  Phase 2b runs a fresh session over a wire held at a fixed drop/dup rate, never healed, asserting the same convergence and termination oracles within a window scaled from the loss rate: expected rounds are the clean window over (1 - p_loss) squared per direction, times a safety factor, recomputed in a comment rather than a magic number. No corruption is injected -- a corrupted body is already a lost round.

  The protocol converges comfortably: over 200 seeds the worst run took 7, 13, and 18 rounds at 10, 25, and 40 percent loss, against windows of 160, 228, and 356 -- no livelock. The gate joins at 10 percent; the soak sweeps the wider rate set. Pinning the window below the real need trips the liveness oracle, so the check is not vacuous. The liveness-under-faults discipline follows TigerBeetle's VOPR. (user: dmestas, size: 31472) [annotate] [blame] [check-ins using] [more...]

//! 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");

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");
    // 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,
};

/// 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);
        };
        // 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);
        };
    }
    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;
}

fn runSeed(gpa: std.mem.Allocator, seed: u64, steps: usize) 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 = gen_mod.Gen.init(gpa, random);
    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);
        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);

    // 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);

    // 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 = 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 = 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 = 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 = 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) — unique mtimes make the resolved
/// check-in deterministic, so a replay that disagrees is a real order
/// dependency, not a fair tie. Phantom arrival order (Section 4.2 step 1)
/// is exercised by every child-before-parent permutation; the open-leaf set
/// additionally exercises closed-tag skip ordering (Section 7.4).
fn checkOrderIndependence(gpa: std.mem.Allocator, log: []const repostate.Record, random: std.Random) Failure!void {
    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);
            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);
        }
    }
}

/// `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);
        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`.
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,
) 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;
    }
    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;
}