//! 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 gen_mod = @import("sim/gen.zig");
const oracle_mod = @import("sim/oracle.zig");
const storage_sweep = @import("sim/storage_sweep.zig");
test {
// storage.zig deliberately isn't part of the public `zit` module yet
// (root.zig), so dst.zig is the only compilation root that reaches it;
// aggregate its tests and its sim collaborators' the same way root.zig
// aggregates the library's per-RFC modules.
_ = @import("storage.zig");
_ = @import("logstore.zig");
_ = @import("checkout.zig");
_ = @import("sim/faulty_file.zig");
_ = @import("sim/storage_sweep.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,
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;
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);
};
}
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 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);
}
/// 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;
}
/// 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| {
const got = rs.resolveName(name) catch null;
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 = 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,
};
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 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 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;
}