//! 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;
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),
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,
.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 = &.{};
const n = self.inserted.items.len;
if (n > 0) {
const roll = self.random.uintLessThan(u8, 100);
if (roll < 70) {
parents = try self.dupeParents(&.{self.pickInserted()});
} else if (roll < 78 and n >= 2) {
const a = self.pickInserted();
const b = self.pickInserted();
parents = if (std.mem.eql(u8, a, b))
try self.dupeParents(&.{a})
else
try self.dupeParents(&.{ a, b });
} else if (roll < 84) {
const p = self.pickInserted();
parents = try self.dupeParents(&.{ p, p });
} else if (roll < 92 and self.next_index < max_checkins) {
const future = try self.freshIndex();
try self.promised.append(gpa, future);
parents = try self.dupeParents(&.{self.hashes.items[future]});
}
// Otherwise: a fresh root with no parents.
}
self.next_mtime += 1;
const rec = repostate.Record{
.hash = self.hashes.items[index],
.mtime = self.next_mtime,
.parents = parents,
};
try self.inserted.append(gpa, rec);
return rec;
}
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;
}
};