//! Deterministic simulation of the repository-state derivation.
//!
//! `zig build dst` runs the fixed smoke sweep (seeds 1..25, 10_000 steps
//! each); `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 default_steps: usize = 10_000;
const default_sweep_seeds: u64 = 25;
/// 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,
};
/// 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()]);
}
// 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);
}
/// 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;
}
}
/// 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;
}