//! 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,
};
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;
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;
}
/// A slot's branch value (Section 6.1): the nearest primary-ancestor-
/// or-self carrying a self-applied branch tag, or the default branch.
/// 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 branchValueOf(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 default_branch;
cur = parent;
steps += 1;
std.debug.assert(steps <= bound); // acyclic primary chain
}
}
/// 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;
}
}
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;
}
};