Artifact bc9e272bb3332b7b715fbcc254b63583aa294b769d423f4be48593152717dfb2:
- File
src/sim/oracle.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: 20001) [annotate] [blame] [check-ins using] [more...]
//! Brute-force oracle for the repository-state simulation. //! //! Maintains its own record log keyed by hash and recomputes the normative //! leaf test (repo-state Section 7.2) from that log on demand. It never //! reads `RepoState` internals — the driver compares the two through the //! public API only. const std = @import("std"); const repostate = @import("zit").repostate; /// Fallback branch value for a slot with no self-tagged branch root on its /// primary-ancestor chain (repo-state Section 6.1/6.4 default). const default_branch = "trunk"; pub const Oracle = struct { gpa: std.mem.Allocator, /// Hash to slot index; covers phantoms (hashes only ever named as a /// parent) as well as inserted records. index_of: std.StringHashMapUnmanaged(u32), slots: std.ArrayList(Slot), /// Parent-link edges as (parent-slot, child-slot) pairs, one per /// distinct pair per child (repo-state Section 3.1). edges: std.ArrayList([2]u32), const Slot = struct { hash: []u8, inserted: bool, /// The first-listed parent's slot (Section 3.2), set once at first /// insertion — mirrors the immutability of the real primary-parent /// linkage row. primary_parent: ?u32 = null, /// Owned dupe of a self-applied *branch value (Section 6.2), set at /// most once since the generator only self-tags a branch root at /// its own creation. branch_self: ?[]u8 = null, /// The mtime of the highest-mtime closed/reopen op seen for this /// slot as a target, and whether that op left it active. The /// generator only ever applies +closed/-closed as singleton/cancel /// (never propagate), so a slot's closed state is exactly its own /// direct writes — Section 5.5 srcid-nonzero blocking means a /// cancel's propagation walk can never touch it either. closed_mtime: ?repostate.Mtime = null, closed_active: bool = false, /// The check-in's own event.mtime (Section 8.2), set once at first /// insertion; null for a slot never inserted (a phantom). mtime: ?repostate.Mtime = null, }; pub fn init(gpa: std.mem.Allocator) Oracle { return .{ .gpa = gpa, .index_of = .empty, .slots = .empty, .edges = .empty, }; } pub fn deinit(self: *Oracle) void { for (self.slots.items) |slot| { self.gpa.free(slot.hash); if (slot.branch_self) |v| self.gpa.free(v); } self.slots.deinit(self.gpa); self.index_of.deinit(self.gpa); self.edges.deinit(self.gpa); self.* = undefined; } /// Record one crosslinked check-in: linkage derivation is idempotent /// per hash (Section 4.2 step 5), but tag effects — the two this /// oracle tracks, branch-root and closed — are applied on every call, /// matching that same step's "tag application ... still execute". pub fn apply(self: *Oracle, rec: repostate.Record) error{OutOfMemory}!void { const child = try self.internHash(rec.hash); if (!self.slots.items[child].inserted) { self.slots.items[child].inserted = true; self.slots.items[child].mtime = rec.mtime; for (rec.parents, 0..) |parent_hash, i| { const parent = try self.internHash(parent_hash); if (!self.hasEdge(parent, child)) { try self.edges.append(self.gpa, .{ parent, child }); } if (i == 0 and self.slots.items[child].primary_parent == null) { self.slots.items[child].primary_parent = parent; } } } for (rec.tags) |op| { if (op.target == null and op.type == .propagate and std.mem.eql(u8, op.name, "branch")) { if (self.slots.items[child].branch_self == null) { self.slots.items[child].branch_self = try self.gpa.dupe(u8, op.value.?); } } else if (std.mem.eql(u8, op.name, "closed")) { const target = if (op.target) |h| try self.internHash(h) else child; try self.applyClosed(target, op.type != .cancel, rec.mtime); } } } /// Section 5.3 direct-application supersede rule, specialised to the /// closed tag's single active/inactive bit: a strictly later mtime /// wins; the generator's globally unique mtimes make the >=-skip and a /// plain > comparison equivalent. fn applyClosed(self: *Oracle, target: u32, active: bool, mtime: repostate.Mtime) error{OutOfMemory}!void { const slot = &self.slots.items[target]; if (slot.closed_mtime == null or mtime > slot.closed_mtime.?) { slot.closed_mtime = mtime; slot.closed_active = active; } } /// Number of known slots (inserted records plus phantoms). pub fn count(self: *const Oracle) usize { return self.slots.items.len; } pub fn isInserted(self: *const Oracle, slot: usize) bool { return self.slots.items[slot].inserted; } pub fn hashAt(self: *const Oracle, slot: usize) []const u8 { return self.slots.items[slot].hash; } /// The nearest primary-ancestor-or-self carrying a self-applied branch /// tag (Section 6.1), or null when no such ancestor exists — the /// caller supplies the default-branch fallback (Section 6.4), mirroring /// the real `RepoState.activeBranchValue`/`branchOf` split. Correct for /// this generator's restricted branch usage (self-tag only, never /// cancelled, never named-target) because Section 5.5's srcid-nonzero /// blocking always stops inheritance at the nearest such ancestor /// regardless of arrival order. pub fn nearestSelfBranch(self: *const Oracle, slot: u32) ?[]const u8 { var cur = slot; var steps: usize = 0; const bound = self.slots.items.len + 1; while (true) { if (self.slots.items[cur].branch_self) |v| return v; const parent = self.slots.items[cur].primary_parent orelse return null; cur = parent; steps += 1; std.debug.assert(steps <= bound); // acyclic primary chain } } /// A slot's branch value (Section 6.1/6.4): `nearestSelfBranch`, or the /// default branch when absent. pub fn branchValueOf(self: *const Oracle, slot: u32) []const u8 { return self.nearestSelfBranch(slot) orelse default_branch; } /// Brute-force §8.2 plain-name resolution: the inserted slot with the /// greatest own event.mtime among those whose nearest self-branch /// equals `name` — closed/leaf-blind, matching the generator's /// co-emitted branch+sym-tag shaping (every check-in on a self-tagged /// branch carries that branch's active sym-tag too). Null when no slot /// qualifies (Section 8.2's NotFound case). An exact-mtime tie is broken /// by `ancestryMaximal` (the B1 rule), so a unique-mtime run resolves /// identically to the plain max-scan this replaced. pub fn resolveName(self: *const Oracle, name: []const u8) error{OutOfMemory}!?u32 { var best_mtime: ?repostate.Mtime = null; for (self.slots.items, 0..) |slot, i| { if (!slot.inserted) continue; const branch = self.nearestSelfBranch(@intCast(i)) orelse continue; if (!std.mem.eql(u8, branch, name)) continue; const mtime = slot.mtime.?; if (best_mtime == null or mtime > best_mtime.?) best_mtime = mtime; } const target = best_mtime orelse return null; var tied: std.ArrayList(u32) = .empty; defer tied.deinit(self.gpa); for (self.slots.items, 0..) |slot, i| { if (!slot.inserted) continue; const branch = self.nearestSelfBranch(@intCast(i)) orelse continue; if (!std.mem.eql(u8, branch, name)) continue; if (slot.mtime.? == target) try tied.append(self.gpa, @intCast(i)); } return try self.ancestryMaximal(tied.items); } /// Brute-force §9 three-condition open-leaf test over `leaf_flags` /// (one flag per slot, as produced by `leafFlags`): among slots that /// are (a) on `name` by nearest self-branch — strict, no default — /// (b) flagged as a leaf, and (c) not actively closed, the one with /// the greatest own event.mtime, or null when none qualify. pub fn openLeafOf(self: *const Oracle, name: []const u8, leaf_flags: []const bool) error{OutOfMemory}!?u32 { std.debug.assert(leaf_flags.len == self.slots.items.len); var best_mtime: ?repostate.Mtime = null; for (self.slots.items, 0..) |slot, i| { if (!leaf_flags[i]) continue; if (slot.closed_active) continue; const branch = self.nearestSelfBranch(@intCast(i)) orelse continue; if (!std.mem.eql(u8, branch, name)) continue; const mtime = slot.mtime.?; if (best_mtime == null or mtime > best_mtime.?) best_mtime = mtime; } const target = best_mtime orelse return null; var tied: std.ArrayList(u32) = .empty; defer tied.deinit(self.gpa); for (self.slots.items, 0..) |slot, i| { if (!leaf_flags[i]) continue; if (slot.closed_active) continue; const branch = self.nearestSelfBranch(@intCast(i)) orelse continue; if (!std.mem.eql(u8, branch, name)) continue; if (slot.mtime.? == target) try tied.append(self.gpa, @intCast(i)); } return try self.ancestryMaximal(tied.items); } /// Recompute the normative leaf test into `out` (one flag per slot): /// a slot is a leaf iff it is an inserted check-in and no edge names it /// as parent of a same-branch child — with no primary/merge filter /// (Section 7.2). Root check-ins with no children are leaves /// (Section 7.3). pub fn leafFlags(self: *const Oracle, out: []bool) void { std.debug.assert(out.len == self.slots.items.len); for (out, self.slots.items) |*flag, slot| flag.* = slot.inserted; for (self.edges.items) |edge| { if (std.mem.eql(u8, self.branchValueOf(edge[0]), self.branchValueOf(edge[1]))) { out[edge[0]] = false; } } } /// Recompute the open-leaf test into `out` (Section 7.4): a leaf that /// does not carry an active closed marker. pub fn openLeafFlags(self: *const Oracle, out: []bool) void { self.leafFlags(out); for (out, self.slots.items) |*flag, slot| { if (flag.* and slot.closed_active) flag.* = false; } } /// Brute-force §8.3 form 3 (tip): the inserted slot with the greatest /// own event.mtime, independent of branch. An exact-mtime tie is broken /// by `ancestryMaximal` (the B1 rule). pub fn tipSlot(self: *const Oracle) error{OutOfMemory}!?u32 { var best_mtime: ?repostate.Mtime = null; for (self.slots.items) |slot| { if (!slot.inserted) continue; const mtime = slot.mtime.?; if (best_mtime == null or mtime > best_mtime.?) best_mtime = mtime; } const target = best_mtime orelse return null; var tied: std.ArrayList(u32) = .empty; defer tied.deinit(self.gpa); for (self.slots.items, 0..) |slot, i| { if (!slot.inserted) continue; if (slot.mtime.? == target) try tied.append(self.gpa, @intCast(i)); } return try self.ancestryMaximal(tied.items); } /// Brute-force §8.4 branch-walk, mirroring `RepoState.branchWalk` /// exactly: follow `primary_parent` from `start`, tracking /// `branchValueOf` at each step. `.first_off_branch` returns the first /// ancestor whose branch value differs; `.earliest_on_branch` returns /// the deepest ancestor still matching. A chain that never diverges, or /// that runs into a not-yet-inserted (phantom) primary parent, falls /// back to the deepest ancestor reached for either variant. pub fn branchWalk(self: *const Oracle, start: u32, variant: enum { earliest_on_branch, first_off_branch }) u32 { const target = self.branchValueOf(start); var cur = start; var steps: usize = 0; const bound = self.slots.items.len + 1; while (self.slots.items[cur].primary_parent) |parent| { if (!self.slots.items[parent].inserted) break; steps += 1; std.debug.assert(steps <= bound); const pbranch = self.branchValueOf(parent); if (!std.mem.eql(u8, pbranch, target)) { if (variant == .first_off_branch) return parent; return cur; } cur = parent; } return cur; } /// Brute-force §7.5 ambiguity test over `leaf_flags` (as produced by /// `leafFlags`): false immediately when `slot` is not itself flagged as /// a leaf; otherwise true when some *other* leaf slot is open (not /// `closed_active`) and shares `slot`'s branch. pub fn isAmbiguousLeaf(self: *const Oracle, slot: u32, leaf_flags: []const bool) bool { std.debug.assert(leaf_flags.len == self.slots.items.len); if (!leaf_flags[slot]) return false; const branch = self.branchValueOf(slot); for (self.slots.items, 0..) |s, i| { if (i == slot or !leaf_flags[i] or s.closed_active) continue; if (std.mem.eql(u8, self.branchValueOf(@intCast(i)), branch)) return true; } return false; } /// One §6.3 derived branch-listing row, brute-force computed. pub const BranchGroup = struct { name: []const u8, rep: u32, mtime: repostate.Mtime, count: usize, closed: bool, }; /// Brute-force §6.3 grouping: only slots with an actual self-tagged /// branch-root ancestor (direct or inherited) qualify — mirroring /// `RepoState.branches`'s tagxref-row-only grouping, which excludes a /// check-in whose branch identity is only the untagged default /// fallback. Representative is the greatest-mtime member; the /// generator's globally unique mtimes rule out a tie. Caller frees the /// returned slice. pub fn branchGroups(self: *const Oracle, gpa: std.mem.Allocator) error{OutOfMemory}![]BranchGroup { const Group = struct { rep: u32, mtime: repostate.Mtime, count: usize }; var groups: std.StringHashMapUnmanaged(Group) = .empty; defer groups.deinit(gpa); for (self.slots.items, 0..) |s, i| { if (!s.inserted) continue; const branch = self.nearestSelfBranch(@intCast(i)) orelse continue; const mtime = s.mtime.?; const gop = try groups.getOrPut(gpa, branch); if (!gop.found_existing) { gop.value_ptr.* = .{ .rep = @intCast(i), .mtime = mtime, .count = 1 }; } else { gop.value_ptr.count += 1; if (mtime > gop.value_ptr.mtime) { gop.value_ptr.rep = @intCast(i); gop.value_ptr.mtime = mtime; } } } var out: std.ArrayList(BranchGroup) = .empty; errdefer out.deinit(gpa); var it = groups.iterator(); var scanned: usize = 0; const bound = groups.count(); while (it.next()) |g| { scanned += 1; std.debug.assert(scanned <= bound); try out.append(gpa, .{ .name = g.key_ptr.*, .rep = g.value_ptr.rep, .mtime = g.value_ptr.mtime, .count = g.value_ptr.count, .closed = self.slots.items[g.value_ptr.rep].closed_active, }); } return out.toOwnedSlice(gpa); } /// The equal-`event.mtime` tie winner, mirroring `RepoState.ancestryMaximal` /// (repostate.zig:1605; the B1 rule the regression cluster pins): the /// candidate no OTHER candidate descends from — a descendant beats its /// ancestor over full ancestry (Section 3.3, merge parents included) — /// with true concurrents settled by the least artifact hash. Two phases, /// not a pairwise comparator, for the same reason production is: /// "descends-from, else hash" is not a strict weak order. Because the /// oracle computes this independently of the real derivation, a resolution /// that reverts to raw hash order (ignoring ancestry — the original B1 /// bug) diverges here and is caught. A single-element (unique-mtime) tied /// set returns immediately, so nothing changes for the default mode. /// /// A `child -> parents` reverse index in CSR form (`head` offsets + `flat` /// parent ids) is built once from the edge list so each ancestor BFS is /// O(V+E) with only three flat allocations, not a per-node edge rescan /// (O(V·E)) nor a per-slot ArrayList. fn ancestryMaximal(self: *const Oracle, tied: []const u32) error{OutOfMemory}!?u32 { if (tied.len == 0) return null; if (tied.len == 1) return tied[0]; const gpa = self.gpa; const n = self.slots.items.len; // CSR reverse adjacency: head[c]..head[c+1] indexes `flat` for c's parents. const head = try gpa.alloc(u32, n + 1); defer gpa.free(head); @memset(head, 0); for (self.edges.items) |edge| head[edge[1] + 1] += 1; for (1..n + 1) |i| head[i] += head[i - 1]; const flat = try gpa.alloc(u32, self.edges.items.len); defer gpa.free(flat); const cursor = try gpa.alloc(u32, n); defer gpa.free(cursor); for (0..n) |i| cursor[i] = head[i]; for (self.edges.items) |edge| { flat[cursor[edge[1]]] = edge[0]; cursor[edge[1]] += 1; } const sets = try gpa.alloc(std.AutoHashMapUnmanaged(u32, void), tied.len); for (sets) |*s| s.* = .empty; defer { for (sets) |*s| s.deinit(gpa); gpa.free(sets); } var frontier: std.ArrayList(u32) = .empty; defer frontier.deinit(gpa); for (tied, sets) |start, *s| { frontier.clearRetainingCapacity(); try frontier.append(gpa, start); while (frontier.pop()) |node| { const gop = try s.getOrPut(gpa, node); if (gop.found_existing) continue; for (flat[head[node]..head[node + 1]]) |p| try frontier.append(gpa, p); } } var best: ?u32 = null; for (tied, 0..) |cand, i| { var dominated = false; for (sets, 0..) |*other, j| { if (i == j) continue; if (other.contains(cand)) { dominated = true; break; } } if (dominated) continue; const wins = best == null or std.mem.order(u8, self.slots.items[cand].hash, self.slots.items[best.?].hash) == .lt; if (wins) best = cand; } return best.?; } fn internHash(self: *Oracle, hash: []const u8) error{OutOfMemory}!u32 { if (self.index_of.get(hash)) |slot| return slot; try self.slots.ensureUnusedCapacity(self.gpa, 1); const owned = try self.gpa.dupe(u8, hash); errdefer self.gpa.free(owned); const slot: u32 = @intCast(self.slots.items.len); try self.index_of.put(self.gpa, owned, slot); self.slots.appendAssumeCapacity(.{ .hash = owned, .inserted = false }); return slot; } fn hasEdge(self: *const Oracle, parent: u32, child: u32) bool { for (self.edges.items) |edge| { if (edge[0] == parent and edge[1] == child) return true; } return false; } };