//! 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. Check-in mtimes are strictly increasing
//! and unique: equal-mtime behaviour is implementation-defined by the spec
//! (repo-state Sections 5.3, 8.2), so unique mtimes keep order-independence
//! a fair invariant while the tie rules get their own cited unit tests.
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,
/// 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,
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 = [_]?u32{null} ** max_checkins,
.branch_self_of = [_]?[]const u8{null} ** max_checkins,
.emitted = [_]bool{false} ** max_checkins,
.next_index = 0,
.next_mtime = 0,
};
}
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());
return self.reissue();
}
if (self.inserted.items.len > 0 and self.random.uintLessThan(u8, 100) < 4) {
return self.reissue();
}
const index = if (self.promised.items.len > 0 and self.random.uintLessThan(u8, 100) < 25)
self.popPromised()
else
try self.freshIndex();
return self.emit(index);
}
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) error{OutOfMemory}!repostate.Record {
const gpa = self.arena.allocator();
var parents: []const []const u8 = &.{};
var primary: ?u32 = null;
const n = self.inserted.items.len;
if (n > 0) {
const roll = self.random.uintLessThan(u8, 100);
if (roll < 70) {
if (self.pickPrimaryIndex(index)) |p| {
primary = p;
parents = try self.dupeParents(&.{self.hashes.items[p]});
}
} else if (roll < 78 and n >= 2) {
if (self.pickPrimaryIndex(index)) |a| {
primary = a;
const b = self.pickInsertedIndex(); // merge parent: no cycle risk
parents = if (a == b)
try self.dupeParents(&.{self.hashes.items[a]})
else
try self.dupeParents(&.{ self.hashes.items[a], self.hashes.items[b] });
}
} else if (roll < 84) {
if (self.pickPrimaryIndex(index)) |p| {
primary = 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;
parents = try self.dupeParents(&.{self.hashes.items[future]});
}
// Otherwise, or when no cycle-safe candidate exists: a fresh
// root with no parents.
}
self.primary_parent_of[index] = primary;
const tags = try self.genTags(primary, index);
self.next_mtime += 1;
const rec = repostate.Record{
.hash = self.hashes.items[index],
.mtime = self.next_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 primary-ancestor chain reaches `index` — a
/// cycle `index` naming `candidate` as its own primary parent would
/// close. Bounded by `max_checkins`: an acyclic chain has length below
/// that bound.
fn wouldClosePrimaryCycle(self: *const Gen, candidate: u32, index: u32) bool {
var cur: ?u32 = candidate;
var steps: usize = 0;
while (cur) |c| {
if (c == index) return true;
steps += 1;
std.debug.assert(steps <= max_checkins + 1);
cur = self.primary_parent_of[c];
}
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 ancestor chain 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.wouldClosePrimaryCycle(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
/// `wouldClosePrimaryCycle`). 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.
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;
}
};