//! 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
}
}
/// Whether a slot holds a branch tagxref row (Section 7.3's candidacy):
/// its own branch tag, or one inherited along a primary chain whose
/// every member is inserted, since propagation cannot cross a phantom.
fn hasBranchRow(self: *const Oracle, slot: u32) bool {
var cur = slot;
var steps: usize = 0;
const bound = self.slots.items.len + 1;
while (true) {
const s = self.slots.items[cur];
if (!s.inserted) return false;
if (s.branch_self != null) return true;
cur = s.primary_parent orelse return false;
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);
// Section 7.3: only a leaf candidate can be a leaf — a check-in that
// carries a branch row, or the parent of one that does. The rest
// are never rechecked, whatever their children.
for (out, self.slots.items, 0..) |*flag, slot, i| flag.* = slot.inserted and self.hasBranchRow(@intCast(i));
for (self.edges.items) |edge| {
if (self.slots.items[edge[0]].inserted and self.hasBranchRow(edge[1])) out[edge[0]] = true;
}
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;
}
};