//! 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).
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,
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,
.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();
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);
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)];
}
/// 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) error{OutOfMemory}![]const repostate.TagOp {
const roll = self.random.uintLessThan(u8, 100);
if (roll < 8) {
const name = branch_names[self.random.uintLessThan(usize, branch_names.len)];
return self.dupeTags(&.{
.{ .type = .propagate, .name = "branch", .target = null, .value = 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;
}
};