Artifact 8189752613ae0c87a34d3ea9ec612db7f2fd8a785b72264957563db478019eb3:
- File
src/sim/gen.zig
— part of check-in
[992ff19a23]
at
2026-08-01 08:31:42
on branch sub-manifest
— dst gen: check merge parents for cycles, not just the primary chain
The generator's own note says a real check-in DAG is acyclic by construction - a manifest's hash covers its P-card - while the phantom-parent flavor lets a hash be named before its record exists, so a later pick can close a loop and must be checked. The check only ever walked primary_parent_of, and the merge parent was drawn by pickInsertedIndex with the comment "no cycle risk".
That holds for the primary chain alone. Section 3.3 ancestry, which the B1 tie-break walks, follows merge parents too: a merge edge into an already inserted check-in, paired with a phantom primary edge out of it, closes a loop the guard never looked at. ancestryMaximal then finds every candidate dominated and no maximal element, and panics - seed 192 built exactly that, 9 to 14 to 13 and back.
parent_indices records every parent index a record names, wouldCloseCycle walks that graph visited-once, and the merge draw is checked like the primary one. A losing draw degrades to the single-parent record rather than drawing again, so the seeded stream shifts as little as it can.
Pre-existing: trunk fails seed 192 identically, and gen.zig is byte-identical there. Only the default six seeds hid it. (user: dmestas, size: 24120) [annotate] [blame] [check-ins using] [more...]
//! 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 = [_]?u32{null} ** max_checkins, .parent_indices = [_][2]?u32{.{ null, null }} ** max_checkins, .branch_self_of = [_]?[]const u8{null} ** max_checkins, .emitted = [_]bool{false} ** max_checkins, .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 = [_]bool{false} ** max_checkins; 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. 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; } };