//! 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;
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,
};
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);
self.slots.deinit(self.gpa);
self.index_of.deinit(self.gpa);
self.edges.deinit(self.gpa);
self.* = undefined;
}
/// Record one crosslinked check-in. Idempotent per hash, mirroring the
/// linkage idempotency of repo-state Section 4.2 step 5.
pub fn apply(self: *Oracle, rec: repostate.Record) error{OutOfMemory}!void {
const child = try self.internHash(rec.hash);
if (self.slots.items[child].inserted) return;
self.slots.items[child].inserted = true;
for (rec.parents) |parent_hash| {
const parent = try self.internHash(parent_hash);
if (!self.hasEdge(parent, child)) {
try self.edges.append(self.gpa, .{ parent, child });
}
}
}
/// 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;
}
/// 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). No branch tags exist in this phase, so every
/// check-in shares the default branch and any child disqualifies.
/// 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| out[edge[0]] = 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;
}
};