//! 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 repeat = @import("zit").repeat;
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 = repeat("a", 64);
const hb = repeat("b", 64);
const hc = repeat("c", 64);
const hd = repeat("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: [check_names.len]?[]const u8 = @splat(null);
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;
}