Artifact a05fa9fa17e4b585c662c6e1d3855e5e46327db9c7490bc834382b64e742c557:
- File
src/sim/gen.zig
— part of check-in
[c52cc8cc76]
at
2026-07-20 05:33:57
on branch h10-ties
— H10: fuzz equal-mtime ties in the repository-state DST
sim/gen.zig emitted strictly-increasing unique mtimes, so the same-second selection tie -- once a real defect, the B1 regression cluster -- was only example-tested, blind to a class that already bit once.
gen.zig gains a tie-permitting mode: a seeded roll reuses the previous mtime, bounded to short runs, and each reused-mtime check-in is shaped as a linear child of the previous one, so an equal-mtime run is a real descendant chain. oracle.zig now computes the documented tie-break in resolveName, tipSlot and openLeafOf -- descendant-before-ancestor over full ancestry, then least artifact hash (repostate.zig ancestryMaximal) -- so a resolution reverting to hash order is caught, not mirrored.
dst.zig runs the tie sweep as additional coverage; the unique sweep is unchanged. Order-independence keeps its total-rule dimensions (leaf set, name resolution) under ties and skips the open-leaf set, whose equal-mtime supersede is implementation-defined (Section 5.3); the Section 6.3 branch representative is first-seen under a tie, checked in the unique sweep only.
Reverting the tie-break to hash order trips the tie sweep at seed 1. (user: dmestas, size: 21719) [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, /// 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, .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. if (clock.reused and fresh and n > 0) { const last = self.inserted_index.items[n - 1]; std.debug.assert(!self.wouldClosePrimaryCycle(last, index)); primary = 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; 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); 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 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; } };