//! Deterministic operation generator for the repository-state simulation.
//!
//! Every choice — topology, merge/fork mix, phantom references, re-issues —
//! is drawn from the single `std.Random` handed in by the driver, so one
//! seed reproduces the whole run. In the default mode (`init`) check-in
//! mtimes are strictly increasing and unique, so order-independence stays a
//! fair invariant. `initTies` opts into a tie-permitting mode: a seeded
//! `tie_prob`-in-100 roll reuses the previous mtime, bounded to short runs,
//! and each reused-mtime fresh check-in is shaped as a LINEAR CHILD of the
//! previous one, so an equal-mtime run is a real descendant chain — the B1
//! defect shape (repostate_test.zig REGRESSION B1; repostate.zig:1429),
//! where the documented tie-break is descendant-before-ancestor then least
//! hash rather than raw hash order. The default mode draws NO tie PRNG, so
//! its seed streams are byte-identical to before this mode existed.
const std = @import("std");
const repostate = @import("zit").repostate;
/// Universe cap: bounds the per-step oracle recompute and every replay.
pub const max_checkins: u32 = 256;
/// Fixed branch-name pool for self-tag branch roots (repo-state Section
/// 6.2's writer-side branch creation is out of scope here — only the
/// propagating *branch self-tag a branch root carries, shaped to also emit
/// the matching sym-<name> marker so name resolution has something to
/// resolve). Exposed so the driver can probe resolution/open-leaf per name.
pub const branch_names = [_][]const u8{ "trunk", "feature", "topic" };
/// Fixed user-tag pool for the apply_tag/tag_phantom flavors, disjoint from
/// the reserved "branch"/"closed" names.
const user_tag_names = [_][]const u8{ "t1", "t2" };
pub const Gen = struct {
random: std.Random,
arena: std.heap.ArenaAllocator,
/// Hash string per issued index; a 64-hex-digit name unique per index.
hashes: std.ArrayList([]const u8),
/// Unique records in first-crosslink order: the replay log.
inserted: std.ArrayList(repostate.Record),
/// Indices whose hash has been named as a parent but whose record has
/// not been emitted yet (phantoms, repo-state Section 4.2 step 1).
promised: std.ArrayList(u32),
/// The originating index of each `inserted` record, same length and
/// order as `inserted` — recovers the numeric index behind a picked
/// hash for the cycle check below.
inserted_index: std.ArrayList(u32),
/// Primary-parent index per index, mirroring repo-state Section 3.2,
/// tracked so a later pick can be checked against closing a cycle. A
/// real check-in DAG is acyclic by construction (a manifest's hash
/// covers its own P-card, so it cannot name a not-yet-existing
/// descendant as a parent); the phantom-parent flavor below lets a
/// hash be referenced before its record exists, which — unlike real
/// content addressing — does not by itself rule out a later pick
/// closing a loop, so this must be checked explicitly.
primary_parent_of: [max_checkins]?u32,
/// EVERY parent index named at each index — the primary one above and the
/// merge parent both. §3.3 ancestry, which is what the tie-break walks,
/// follows merge parents too, so a cycle check that reads only the primary
/// chain is checking a subgraph and can pass while the real one loops. Two
/// slots is the maximum any record here names.
parent_indices: [max_checkins][2]?u32,
/// The self-applied branch name at each index (Section 6.2 branch-root
/// self-tag), or null when that index carries none — mirrors the
/// oracle's `Slot.branch_self`, tracked here so a later branch-root
/// pick can find and cancel its primary parent's active sym-tag.
branch_self_of: [max_checkins]?[]const u8,
/// Whether `emit` has run for an index yet. Distinguishes "a genuine,
/// resolved root with no branch tag" from "a phantom future primary
/// parent (Section 4.2 step 1) not yet emitted" — both read as
/// `null`/`null` in `primary_parent_of`/`branch_self_of` otherwise, but
/// only the former is safe to read a branch identity from.
emitted: [max_checkins]bool,
next_index: u32,
next_mtime: repostate.Mtime,
/// Tie mode (0 = off, the default): probability in 100 that a check-in
/// reuses the previous mtime instead of advancing the clock, producing an
/// equal-mtime run. Zero short-circuits every tie roll, so the default
/// mode's PRNG stream is unchanged.
tie_prob: u8,
/// Reuses since the last strict clock advance — bounds a run so ties
/// cluster into SHORT equal-mtime chains instead of an unbounded
/// same-second pile-up.
tie_run_len: u32,
/// Cap on `tie_run_len`: a run holds at most `tie_run_max` reuses (so at
/// most `tie_run_max + 1` check-ins share one mtime). Zero in the default
/// mode, where it is never consulted.
tie_run_max: u32,
pub fn init(gpa: std.mem.Allocator, random: std.Random) Gen {
return .{
.random = random,
.arena = std.heap.ArenaAllocator.init(gpa),
.hashes = .empty,
.inserted = .empty,
.promised = .empty,
.inserted_index = .empty,
.primary_parent_of = @as([max_checkins]?u32, @splat(null)),
.parent_indices = @as([max_checkins][2]?u32, @splat(.{ null, null })),
.branch_self_of = @splat(null),
.emitted = @as([max_checkins]bool, @splat(false)),
.next_index = 0,
.next_mtime = 0,
.tie_prob = 0,
.tie_run_len = 0,
.tie_run_max = 0,
};
}
/// Tie-permitting variant of `init` (TEST-HARDENING §2 H10): `tie_prob`
/// (1..100) is the per-check-in probability of reusing the previous
/// mtime, `tie_run_max` (>= 1) bounds a run's reuse count. Otherwise
/// identical to `init` — same topology mix, same PRNG source.
pub fn initTies(gpa: std.mem.Allocator, random: std.Random, tie_prob: u8, tie_run_max: u32) Gen {
std.debug.assert(tie_prob >= 1 and tie_prob <= 100);
std.debug.assert(tie_run_max >= 1);
var g = init(gpa, random);
g.tie_prob = tie_prob;
g.tie_run_max = tie_run_max;
return g;
}
pub fn deinit(self: *Gen) void {
self.arena.deinit();
self.* = undefined;
}
/// Unique records emitted so far, in first-crosslink order.
pub fn log(self: *const Gen) []const repostate.Record {
return self.inserted.items;
}
/// Produce the record to crosslink this step: usually a new check-in,
/// sometimes a re-issue of an already-linked record (probing linkage
/// idempotency, repo-state Section 4.2 step 5). Once the universe cap
/// is reached, promised phantoms are drained and every further step
/// re-issues.
pub fn next(self: *Gen) error{OutOfMemory}!repostate.Record {
if (self.next_index >= max_checkins) {
if (self.promised.items.len > 0) return self.emit(self.popPromised(), false);
return self.reissue();
}
if (self.inserted.items.len > 0 and self.random.uintLessThan(u8, 100) < 4) {
return self.reissue();
}
if (self.promised.items.len > 0 and self.random.uintLessThan(u8, 100) < 25) {
return self.emit(self.popPromised(), false);
}
return self.emit(try self.freshIndex(), true);
}
/// Advance the event clock, or — in tie mode — reuse the previous mtime
/// with a bounded, seeded probability. `.reused` reports whether this was
/// a tie. In the default mode (`tie_prob == 0`) the guard short-circuits
/// before the PRNG draw, so the clock strictly increases and no entropy is
/// consumed — existing seed streams stay byte-identical.
fn nextMtime(self: *Gen) struct { mtime: repostate.Mtime, reused: bool } {
const can_reuse = self.next_mtime > 0 and self.tie_prob > 0 and self.tie_run_len < self.tie_run_max;
if (can_reuse and self.random.uintLessThan(u8, 100) < self.tie_prob) {
self.tie_run_len += 1;
return .{ .mtime = self.next_mtime, .reused = true };
}
self.next_mtime += 1;
self.tie_run_len = 0;
return .{ .mtime = self.next_mtime, .reused = false };
}
fn reissue(self: *Gen) repostate.Record {
std.debug.assert(self.inserted.items.len > 0);
return self.inserted.items[self.random.uintLessThan(usize, self.inserted.items.len)];
}
/// Build and log the record for `index`, with parents drawn from the
/// weighted topology mix: linear child, merge, duplicated parent
/// listing (Section 3.1), phantom parent (Section 4.2 step 1), or a
/// fresh root.
fn emit(self: *Gen, index: u32, fresh: bool) error{OutOfMemory}!repostate.Record {
const gpa = self.arena.allocator();
// Decide the event clock FIRST, so a reused mtime can shape the parent
// pick below. In the default mode this draws no PRNG (see `nextMtime`),
// leaving the topology roll the first draw exactly as before.
const clock = self.nextMtime();
var parents: []const []const u8 = &.{};
var primary: ?u32 = null;
const n = self.inserted.items.len;
// Tie-run chain bias (H10): a reused-mtime FRESH check-in becomes a
// linear child of the most recently inserted check-in, so an
// equal-mtime run is a descendant chain (the B1 shape) — the tie-break
// the oracle mirrors then separates a descendant from its ancestor,
// rather than the run being unrelated concurrents the least-hash
// fallback settles anyway. `fresh` guarantees `index` has no
// descendants yet, so a new parent edge into it cannot close a cycle.
// Every parent index named below, so `wouldCloseCycle` sees the same
// graph §3.3 ancestry does.
var parent_ix: [2]?u32 = .{ null, null };
if (clock.reused and fresh and n > 0) {
const last = self.inserted_index.items[n - 1];
std.debug.assert(!self.wouldCloseCycle(last, index));
primary = last;
parent_ix[0] = last;
parents = try self.dupeParents(&.{self.hashes.items[last]});
} else if (n > 0) {
const roll = self.random.uintLessThan(u8, 100);
if (roll < 70) {
if (self.pickPrimaryIndex(index)) |p| {
primary = p;
parent_ix[0] = p;
parents = try self.dupeParents(&.{self.hashes.items[p]});
}
} else if (roll < 78 and n >= 2) {
if (self.pickPrimaryIndex(index)) |a| {
primary = a;
parent_ix[0] = a;
// The merge parent is an ancestry edge like any other and
// needs the same check the primary one gets. It used to be
// waved through as "no cycle risk", which held only for the
// primary chain: pairing a merge edge into an already
// inserted check-in with a phantom primary edge out of it
// closes a loop in the full graph, and the tie-break then
// finds every candidate dominated and no maximal element.
//
// A losing draw degrades to the single-parent record rather
// than drawing again, so the seeded stream shifts as little
// as it can.
const b = self.pickInsertedIndex();
if (a == b or self.wouldCloseCycle(b, index)) {
parents = try self.dupeParents(&.{self.hashes.items[a]});
} else {
parent_ix[1] = b;
parents = try self.dupeParents(&.{ self.hashes.items[a], self.hashes.items[b] });
}
}
} else if (roll < 84) {
if (self.pickPrimaryIndex(index)) |p| {
primary = p;
parent_ix[0] = p;
parents = try self.dupeParents(&.{ self.hashes.items[p], self.hashes.items[p] });
}
} else if (roll < 92 and self.next_index < max_checkins) {
const future = try self.freshIndex();
try self.promised.append(gpa, future);
primary = future;
parent_ix[0] = future;
parents = try self.dupeParents(&.{self.hashes.items[future]});
}
// Otherwise, or when no cycle-safe candidate exists: a fresh
// root with no parents.
}
self.parent_indices[index] = parent_ix;
self.primary_parent_of[index] = primary;
const tags = try self.genTags(primary, index);
const rec = repostate.Record{
.hash = self.hashes.items[index],
.mtime = clock.mtime,
.parents = parents,
.tags = tags,
};
try self.inserted.append(gpa, rec);
try self.inserted_index.append(gpa, index);
self.emitted[index] = true;
return rec;
}
/// Whether `candidate`'s ancestry reaches `index` — the cycle that naming
/// `candidate` as a parent of `index` would close.
///
/// This walks EVERY parent edge, not just the primary chain. The primary-only
/// version passed on graphs whose merge edges closed a loop, because a merge
/// parent was drawn with no check at all; §3.3 ancestry then walked the loop
/// the check never looked at. Visited-once, so it terminates even if a cycle
/// somehow already exists, and each index is pushed at most once.
fn wouldCloseCycle(self: *const Gen, candidate: u32, index: u32) bool {
var visited = @as([max_checkins]bool, @splat(false));
var stack: [max_checkins]u32 = undefined;
var top: usize = 0;
stack[top] = candidate;
top += 1;
visited[candidate] = true;
while (top > 0) {
top -= 1;
const c = stack[top];
if (c == index) return true;
for (self.parent_indices[c]) |maybe_parent| {
const p = maybe_parent orelse continue;
if (visited[p]) continue;
visited[p] = true;
stack[top] = p;
top += 1;
}
}
return false;
}
/// An already-inserted index safe to use as `index`'s primary parent —
/// scanning at most every inserted item, from a random offset, for one
/// whose ancestry does not already reach `index`. Null only when every
/// candidate would close a cycle.
fn pickPrimaryIndex(self: *Gen, index: u32) ?u32 {
const n = self.inserted_index.items.len;
std.debug.assert(n > 0);
const start = self.random.uintLessThan(usize, n);
var i: usize = 0;
while (i < n) : (i += 1) {
const candidate = self.inserted_index.items[(start + i) % n];
if (!self.wouldCloseCycle(candidate, index)) return candidate;
}
return null;
}
fn pickInsertedIndex(self: *Gen) u32 {
const n = self.inserted_index.items.len;
std.debug.assert(n > 0);
return self.inserted_index.items[self.random.uintLessThan(usize, n)];
}
/// The nearest primary-ancestor-or-self carrying a self-applied branch
/// tag (Section 6.1), or null when the chain never sets one — mirrors
/// `Oracle.nearestSelfBranch` so a branch-root pick here can find the
/// active sym-tag it must cancel. Bounded by `max_checkins`: the
/// primary chain is acyclic by construction (see `wouldCloseCycle`, which
/// keeps the whole parent graph acyclic). Callers must first confirm
/// `primaryChainResolved` on the same starting index — an unemitted
/// node on the chain reads identically to a true root here, which is
/// only correct once that's ruled out.
fn nearestSelfBranch(self: *const Gen, index: u32) ?[]const u8 {
var cur: ?u32 = index;
var steps: usize = 0;
while (cur) |c| {
if (self.branch_self_of[c]) |v| return v;
steps += 1;
std.debug.assert(steps <= max_checkins + 1);
cur = self.primary_parent_of[c];
}
return null;
}
/// Whether `nearestSelfBranch(start)` would walk only emitted nodes —
/// i.e. the whole primary chain from `start` up to either a self-tagged
/// branch root or a genuine parentless root is already resolved, with
/// no not-yet-emitted (phantom, Section 4.2 step 1) node truncating it
/// early. `emitted[c] == false` and "c is a resolved root with no
/// branch tag" are otherwise indistinguishable in `primary_parent_of`/
/// `branch_self_of` (both default to null), so a branch-root cancel
/// decision may only walk a chain this confirms resolved — otherwise a
/// phantom ancestor's eventual real branch tag would propagate straight
/// through the branch root later (Section 5.5 blocks only the specific
/// tag id a node directly writes), leaving two active sym tags live on
/// its descendants. Bounded by `max_checkins`, mirroring
/// `nearestSelfBranch`'s acyclic walk.
fn primaryChainResolved(self: *const Gen, start: ?u32) bool {
var cur = start;
var steps: usize = 0;
while (cur) |c| {
if (!self.emitted[c]) return false;
if (self.branch_self_of[c] != null) return true;
steps += 1;
std.debug.assert(steps <= max_checkins + 1);
cur = self.primary_parent_of[c];
}
return true;
}
/// Section 6.2 branch-root emission, shaped so the real crosslink's
/// materialized tag state matches the oracle's nearest-self model: the
/// propagating branch tag and its matching sym-<name> marker land
/// together, and — when the primary parent already sits on a different
/// self-tagged branch — a cancel of that branch's sym-tag lands first
/// ("cancel every pre-existing active sym-* tag on the branch-root
/// check-in"). This keeps exactly one active sym tag live per
/// check-in, so DST invariants (b)/(c) compare like against like.
fn branchRootTags(self: *Gen, primary: ?u32, index: u32, name: []const u8) error{OutOfMemory}![]const repostate.TagOp {
const gpa = self.arena.allocator();
self.branch_self_of[index] = name;
const sym_name = try std.fmt.allocPrint(gpa, "sym-{s}", .{name});
var ops: std.ArrayList(repostate.TagOp) = .empty;
if (primary) |p| {
if (self.nearestSelfBranch(p)) |prev| {
if (!std.mem.eql(u8, prev, name)) {
const prev_sym = try std.fmt.allocPrint(gpa, "sym-{s}", .{prev});
try ops.append(gpa, .{ .type = .cancel, .name = prev_sym, .target = null, .value = null });
}
}
}
try ops.append(gpa, .{ .type = .propagate, .name = "branch", .target = null, .value = name });
try ops.append(gpa, .{ .type = .propagate, .name = sym_name, .target = null, .value = name });
return ops.toOwnedSlice(gpa);
}
/// Draw at most one T-card for the record being emitted, from the
/// weighted flavor mix: branch-root self-tag, apply_tag (+/-/*) on a
/// user tag, close_leaf/reopen on the closed tag, or a tag targeting a
/// not-yet-inserted (phantom) hash. Every flavor besides the branch
/// root needs at least one already-inserted artifact to target.
fn genTags(self: *Gen, primary: ?u32, index: u32) error{OutOfMemory}![]const repostate.TagOp {
const roll = self.random.uintLessThan(u8, 100);
// A primary whose chain is not fully resolved — the direct parent
// or any deeper primary ancestor is still an unemitted phantom
// (Section 4.2 step 1, the "future" flavor below) — has no
// knowable branch identity yet. Branch-rooting through it would
// skip the cancel of whichever sym-tag that ancestor turns out to
// carry, and the real ancestor's tag — once it does resolve —
// would then propagate straight through this node into its own
// descendants on a different tag id than the one this node blocks
// (Section 5.5 blocks only the specific tag id a node directly
// wrote). Checking the WHOLE chain, not just the direct parent,
// keeps the "one active sym per check-in" property the oracle's
// nearest-self model depends on.
// A parentless root always carries its branch tag, as Fossil's own
// initial check-in does. Without one its descendants hold no branch
// row, and Section 7.3's leaf table then legitimately depends on
// arrival order (an untagged root is rechecked only when a tagged
// child arrives after it), which the order-independence invariants
// cannot express; the unit tests cover that shape.
if (primary == null) {
const name = branch_names[self.random.uintLessThan(usize, branch_names.len)];
return self.branchRootTags(null, index, name);
}
const primary_resolved = self.primaryChainResolved(primary);
if (roll < 8 and primary_resolved) {
const name = branch_names[self.random.uintLessThan(usize, branch_names.len)];
return self.branchRootTags(primary, index, name);
}
if (self.inserted.items.len == 0) return &.{};
if (roll < 24) {
const kind = self.random.uintLessThan(u8, 3);
const ttype: repostate.TagType = switch (kind) {
0 => .singleton,
1 => .cancel,
else => .propagate,
};
const name = user_tag_names[self.random.uintLessThan(usize, user_tag_names.len)];
const target = if (self.random.boolean()) null else self.pickInserted();
const value: ?[]const u8 = if (ttype == .cancel) null else "v";
return self.dupeTags(&.{
.{ .type = ttype, .name = name, .target = target, .value = value },
});
}
if (roll < 32) {
const target = if (self.random.boolean()) null else self.pickInserted();
return self.dupeTags(&.{
.{ .type = .singleton, .name = "closed", .target = target, .value = null },
});
}
if (roll < 38) {
const target = if (self.random.boolean()) null else self.pickInserted();
return self.dupeTags(&.{
.{ .type = .cancel, .name = "closed", .target = target, .value = null },
});
}
if (roll < 44 and self.next_index < max_checkins) {
const future = try self.freshIndex();
try self.promised.append(self.arena.allocator(), future);
return self.dupeTags(&.{
.{ .type = .propagate, .name = user_tag_names[0], .target = self.hashes.items[future], .value = "v" },
});
}
return &.{};
}
fn dupeTags(self: *Gen, tags: []const repostate.TagOp) error{OutOfMemory}![]const repostate.TagOp {
return self.arena.allocator().dupe(repostate.TagOp, tags);
}
fn pickInserted(self: *Gen) []const u8 {
const n = self.inserted.items.len;
std.debug.assert(n > 0);
return self.inserted.items[self.random.uintLessThan(usize, n)].hash;
}
fn dupeParents(self: *Gen, parents: []const []const u8) error{OutOfMemory}![]const []const u8 {
return self.arena.allocator().dupe([]const u8, parents);
}
fn popPromised(self: *Gen) u32 {
std.debug.assert(self.promised.items.len > 0);
const at = self.random.uintLessThan(usize, self.promised.items.len);
return self.promised.swapRemove(at);
}
/// Issue the next index and its hash: 64 hex digits derived from the
/// index, unique within the run.
fn freshIndex(self: *Gen) error{OutOfMemory}!u32 {
std.debug.assert(self.next_index < max_checkins);
const index = self.next_index;
self.next_index += 1;
const hash = try std.fmt.allocPrint(self.arena.allocator(), "{x:0>64}", .{index + 1});
std.debug.assert(hash.len == 64);
try self.hashes.append(self.arena.allocator(), hash);
std.debug.assert(self.hashes.items.len == self.next_index);
return index;
}
};