//! Repository State — draft-fossil-repo-state-00.
//!
//! Repository state is derived, not stored: branches, tags, leaves, closed
//! markers, and the current-trunk check-in are computed from the crosslinked
//! set of artifacts. This module owns that derivation over the parent DAG and
//! the tag records defined by the Artifact Format.
//!
//! Input is a `Record` — one check-in's linkage/tag facts — rather than raw
//! manifest bytes; a thin manifest-to-Record adapter arrives with manifest
//! assembly. Artifact identity (hash-to-rid, phantoms) lives behind the
//! `ArtifactStore` boundary so tests and the simulation harness can inject
//! an in-memory store. Nothing here touches ambient time, randomness, the
//! filesystem, or the network.
const std = @import("std");
/// A stored artifact's local integer identifier (Section 2). Local to a
/// repository; not part of the artifact model and not synchronised.
pub const Rid = u64;
/// A check-in's modification time as an opaque ordinal. Only its ordering is
/// consumed by the derived views (Sections 8 and 9); no wall-clock meaning
/// is attached here.
pub const Mtime = u64;
/// Tag type values (Section 5.1). The integer encoding is normative: every
/// tag reference is persisted with one of exactly these three small
/// integers.
pub const TagType = enum(u2) {
/// value 0, surface syntax `-`: removes or blocks a tag.
cancel = 0,
/// value 1, surface syntax `+`: applies to a single check-in only.
singleton = 1,
/// value 2, surface syntax `*`: applies to the target and, absent an
/// intervening cancel, its primary-chain descendants.
propagate = 2,
};
/// One validated T-card, post-parse (Section 4.1 validation happens in the
/// artifact layer). A null `target` designates a self-tag: the tag applies
/// to the artifact being crosslinked (Section 4.2 step 1).
pub const TagOp = struct {
type: TagType,
name: []const u8,
target: ?[]const u8,
value: ?[]const u8,
};
/// One check-in's crosslink input: its hash, event time, parent references
/// in P-card order, and validated tag cards.
pub const Record = struct {
hash: []const u8,
mtime: Mtime,
/// Parent hashes in manifest order; `parents[0]` is the primary parent
/// (Section 3.2). Empty for an initial check-in.
parents: []const []const u8 = &.{},
tags: []const TagOp = &.{},
};
/// The artifact identity boundary: hash-to-rid interning, content storage,
/// and phantom placeholders (Section 4.2 step 1). A runtime vtable so the
/// simulation harness and tests inject an in-memory implementation while a
/// durable store can slot in later without touching the derivation code.
pub const ArtifactStore = struct {
context: *anyopaque,
vtable: *const VTable,
pub const VTable = struct {
/// Resolve a hash to its rid, creating a phantom placeholder — an
/// rid that carries no content yet — when the hash is unknown
/// (Section 4.2 step 1).
intern: *const fn (context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid,
/// Store content for a hash, upgrading a phantom in place.
/// Idempotent: content is addressed by hash, so a repeat put of the
/// same hash carries the same bytes.
put: *const fn (context: *anyopaque, hash: []const u8, content: []const u8) error{OutOfMemory}!Rid,
/// The stored bytes for a rid, or null while it is a phantom.
content: *const fn (context: *anyopaque, rid: Rid) ?[]const u8,
/// The hash that names a rid. Every rid, phantom or not, has one.
hashOf: *const fn (context: *anyopaque, rid: Rid) []const u8,
};
pub fn intern(self: ArtifactStore, hash: []const u8) error{OutOfMemory}!Rid {
return self.vtable.intern(self.context, hash);
}
pub fn put(self: ArtifactStore, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
return self.vtable.put(self.context, hash, content_bytes);
}
pub fn content(self: ArtifactStore, rid: Rid) ?[]const u8 {
return self.vtable.content(self.context, rid);
}
pub fn hashOf(self: ArtifactStore, rid: Rid) []const u8 {
return self.vtable.hashOf(self.context, rid);
}
};
/// In-memory `ArtifactStore`: rids are assigned densely in intern order
/// (index + 1, so rid 0 stays invalid), and a phantom is an entry whose
/// bytes are still null.
pub const MemStore = struct {
gpa: std.mem.Allocator,
by_hash: std.StringHashMapUnmanaged(Rid) = .empty,
entries: std.ArrayList(Entry) = .empty,
const Entry = struct {
hash: []u8,
bytes: ?[]u8,
};
pub fn init(gpa: std.mem.Allocator) MemStore {
return .{ .gpa = gpa };
}
pub fn deinit(self: *MemStore) void {
for (self.entries.items) |entry| {
self.gpa.free(entry.hash);
if (entry.bytes) |bytes| self.gpa.free(bytes);
}
self.entries.deinit(self.gpa);
self.by_hash.deinit(self.gpa);
self.* = undefined;
}
/// The type-erased store interface over this instance.
pub fn store(self: *MemStore) ArtifactStore {
return .{ .context = self, .vtable = &vtable };
}
const vtable = ArtifactStore.VTable{
.intern = internImpl,
.put = putImpl,
.content = contentImpl,
.hashOf = hashOfImpl,
};
fn internImpl(context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid {
const self: *MemStore = @ptrCast(@alignCast(context));
std.debug.assert(hash.len != 0);
if (self.by_hash.get(hash)) |rid| return rid;
// New hash: create a phantom placeholder (Section 4.2 step 1).
// Capacity is reserved before the map insert so a failure leaves no
// partial entry behind.
try self.entries.ensureUnusedCapacity(self.gpa, 1);
const owned = try self.gpa.dupe(u8, hash);
errdefer self.gpa.free(owned);
const rid: Rid = self.entries.items.len + 1;
try self.by_hash.put(self.gpa, owned, rid);
self.entries.appendAssumeCapacity(.{ .hash = owned, .bytes = null });
return rid;
}
fn putImpl(context: *anyopaque, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
const self: *MemStore = @ptrCast(@alignCast(context));
const rid = try internImpl(context, hash);
const entry = self.entryOf(rid);
if (entry.bytes) |existing| {
// Content is addressed by hash: a repeat put carries identical
// bytes, so upgrading twice is a no-op.
std.debug.assert(std.mem.eql(u8, existing, content_bytes));
} else {
entry.bytes = try self.gpa.dupe(u8, content_bytes);
}
return rid;
}
fn contentImpl(context: *anyopaque, rid: Rid) ?[]const u8 {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entryOf(rid).bytes;
}
fn hashOfImpl(context: *anyopaque, rid: Rid) []const u8 {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entryOf(rid).hash;
}
fn entryOf(self: *MemStore, rid: Rid) *Entry {
std.debug.assert(rid >= 1 and rid <= self.entries.items.len);
return &self.entries.items[@intCast(rid - 1)];
}
};
/// The derived repository state: the check-in DAG (Section 3) and the leaf
/// table (Section 7), maintained by the crosslink procedure (Section 4.2).
/// Tag cross-references, branch membership, and name resolution build on
/// this next.
pub const RepoState = struct {
gpa: std.mem.Allocator,
store: ArtifactStore,
/// One row per crosslinked check-in: rid to event mtime. Presence here
/// is the Section 4.2 step 5 idempotency guard, and its key set is the
/// leaf-candidate set (Section 7.3: every check-in, phantoms excluded).
events: std.AutoArrayHashMapUnmanaged(Rid, Mtime) = .empty,
/// Parent linkage rows, unique per (parent, child) pair (Section 3.1).
plinks: std.AutoArrayHashMapUnmanaged(PlinkKey, PlinkRow) = .empty,
/// The precomputed leaf table (Section 7.1): membership only, no
/// open/closed metadata of its own.
leaf_table: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
/// Deferred leaf rechecks (Section 7.3), applied as a batch before the
/// table is considered consistent.
pending_leaf: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
/// Tag cross-reference table (Section 5.2): at most one live row per
/// (rid, tag) pair, enforced by keying the map on that pair directly.
tagxref: std.AutoHashMapUnmanaged(TagKey, Xref) = .empty,
/// User tag names interned to ids 10 and up (Section 2 reserves 8 and
/// 9). Owns the duplicated name bytes.
tag_names: std.StringHashMapUnmanaged(TagId) = .empty,
next_tag: TagId = first_user_tag,
const PlinkKey = struct {
parent: Rid,
child: Rid,
};
const PlinkRow = struct {
/// Set on exactly the row for the first parent listed (Section 3.2).
is_primary: bool,
/// The child check-in's modification time (Section 3.1).
mtime: Mtime,
/// Delta-manifest baseline id (Section 3.1); resolved once the
/// manifest adapter supplies B-card linkage.
baseline: Rid,
};
/// Interned tag identifier (Section 2): a fixed small integer per name,
/// with 8 ("branch") and 9 ("closed") reserved and every other name
/// interned starting at 10.
const TagId = u32;
const branch_tag_id: TagId = 8;
const closed_tag_id: TagId = 9;
const first_user_tag: TagId = 10;
const default_branch = "trunk";
const TagKey = struct {
rid: Rid,
tag: TagId,
};
/// One tagxref row (Section 5.2).
const Xref = struct {
tagtype: TagType,
/// The artifact whose T-card directly applied the tag, or zero when
/// the row instead reflects a value propagated in from an ancestor.
srcid: Rid,
/// The artifact that originally holds the propagating tag.
origid: Rid,
/// Owned duplicate of the tag's value payload, or null.
value: ?[]u8,
mtime: Mtime,
};
pub fn init(gpa: std.mem.Allocator, artifact_store: ArtifactStore) RepoState {
return .{ .gpa = gpa, .store = artifact_store };
}
pub fn deinit(self: *RepoState) void {
var xit = self.tagxref.valueIterator();
while (xit.next()) |xr| {
if (xr.value) |v| self.gpa.free(v);
}
self.tagxref.deinit(self.gpa);
var nit = self.tag_names.keyIterator();
while (nit.next()) |name| self.gpa.free(name.*);
self.tag_names.deinit(self.gpa);
self.events.deinit(self.gpa);
self.plinks.deinit(self.gpa);
self.leaf_table.deinit(self.gpa);
self.pending_leaf.deinit(self.gpa);
self.* = undefined;
}
/// Crosslink one check-in record (Section 4.2): intern its hash, derive
/// its linkage rows with parents interned to phantoms when absent
/// (step 1), route its T-cards into direct application and propagation
/// (steps 2-4), re-propagate the primary parent's tag state so a fresh
/// child inherits it (step 4a), and apply the batch of deferred leaf
/// rechecks (Section 7.3). Linkage derivation is idempotent (step 5): a
/// rid that already has an event row keeps its existing linkage, but
/// tag application and propagation still run on every call. Content
/// type is not carried by `Record` yet, so the step 2 applicability
/// gate and the step 3 cluster path are not reachable here — every
/// record is treated as control/manifest, matching the only kind this
/// layer produces. Only allocation can fail.
pub fn crosslink(self: *RepoState, rec: Record) error{OutOfMemory}!Rid {
std.debug.assert(rec.hash.len != 0);
const rid = try self.store.intern(rec.hash);
const linkage_new = !self.events.contains(rid);
if (linkage_new) {
try self.events.put(self.gpa, rid, rec.mtime);
for (rec.parents, 0..) |parent_hash, i| {
std.debug.assert(parent_hash.len != 0);
const parent = try self.store.intern(parent_hash);
// A manifest cannot name its own hash as a parent: the hash
// covers the manifest's content, including its P card.
std.debug.assert(parent != rid);
const gop = try self.plinks.getOrPut(self.gpa, .{ .parent = parent, .child = rid });
if (!gop.found_existing) {
// Section 3.1: a repeated parent reference collapses
// into the single row for the pair, first wins.
gop.value_ptr.* = .{ .is_primary = i == 0, .mtime = rec.mtime, .baseline = 0 };
}
}
// Section 7.3: a new parent-link schedules a recheck of the
// affected check-in and each of its direct parents.
try self.scheduleLeafRecheck(rid);
}
// Section 4.2 steps 1-4: apply each T-card directly, then, for a
// propagating or cancel type, walk the propagation from the
// resolved target using the row's own post-application state (so a
// Section 5.3 skip still re-walks the winning value rather than the
// losing one).
for (rec.tags) |op| {
const target = if (op.target) |uuid| try self.store.intern(uuid) else rid;
try self.applyDirect(target, op, rid, rec.mtime);
if (op.type != .singleton) {
const tag = try self.internTag(op.name);
const stored = self.tagxref.get(.{ .rid = target, .tag = tag });
std.debug.assert(stored != null);
// Section 5.4: a singleton driving propagation is always
// downgraded to cancel first; the stored row can only be
// singleton here if a later-mtime direct write elsewhere
// won the Section 5.3 skip over this op's own effect.
const pt: TagType = if (stored.?.tagtype == .singleton) .cancel else stored.?.tagtype;
try self.propagate(target, tag, pt, stored.?.value, stored.?.origid, stored.?.mtime);
}
}
// Section 4.2 step 4a: re-propagate the primary parent's tag set so
// a newly linked child inherits it regardless of arrival order.
if (self.primaryParentOf(rid)) |parent| {
try self.repropagateSet(parent);
}
try self.applyPendingLeafChecks();
const post = self.events.count();
std.debug.assert(post >= 1 and self.pending_leaf.count() == 0);
return rid;
}
/// Whether `rid` is a leaf, answered from the precomputed leaf table
/// (Section 7.1).
pub fn isLeaf(self: *const RepoState, rid: Rid) bool {
return self.leaf_table.contains(rid);
}
/// Whether `rid` is an open leaf (Section 7.4): a member of the leaf
/// table that does not carry an active closed tag.
pub fn isOpenLeaf(self: *const RepoState, rid: Rid) bool {
return self.isLeaf(rid) and !self.hasActiveClosed(rid);
}
/// Iterate the leaf table (Section 7.1). Invalidated by any mutation of
/// the repository state.
pub fn leaves(self: *const RepoState) LeafIterator {
return .{ .rids = self.leaf_table.keys() };
}
/// Recompute the entire leaf table from scratch (Section 7.3 full
/// rebuild): every check-in is a candidate — roots included — and is a
/// leaf exactly when it has no same-branch child, with no
/// primary/merge filter. Whole-table cost; reserved for explicit
/// rebuilds rather than routine updates.
pub fn rebuildLeaves(self: *RepoState) error{OutOfMemory}!void {
self.leaf_table.clearRetainingCapacity();
for (self.events.keys()) |rid| {
if (!self.hasSameBranchChild(rid)) {
try self.leaf_table.put(self.gpa, rid, {});
}
}
}
/// The number of distinct parents of `child` (Section 3.3
/// child-to-parent lookup); merge parents included.
pub fn parentCount(self: *const RepoState, child: Rid) usize {
var n: usize = 0;
for (self.plinks.keys()) |key| {
if (key.child == child) n += 1;
}
return n;
}
/// The primary parent of `child` (Section 3.2), or null for a root or
/// an unknown rid. At most one linkage row per child carries the
/// primary indicator.
pub fn primaryParentOf(self: *const RepoState, child: Rid) ?Rid {
for (self.plinks.keys(), self.plinks.values()) |key, row| {
if (key.child == child and row.is_primary) return key.parent;
}
return null;
}
/// The event mtime recorded for a crosslinked check-in, or null when
/// `rid` has no event row (a phantom, or never crosslinked).
pub fn mtimeOf(self: *const RepoState, rid: Rid) ?Mtime {
return self.events.get(rid);
}
/// Apply every scheduled leaf recheck and clear the schedule
/// (Section 7.3 batch application). The check adds no new entries to
/// the schedule, so the batch is bounded by its size at entry.
fn applyPendingLeafChecks(self: *RepoState) error{OutOfMemory}!void {
const n = self.pending_leaf.count();
for (self.pending_leaf.keys()[0..n]) |rid| {
try self.leafCheckOne(rid);
}
std.debug.assert(self.pending_leaf.count() == n);
self.pending_leaf.clearRetainingCapacity();
}
/// Recompute leaf membership for a single rid (Section 7.3 incremental
/// check): removed when it has a same-branch child, inserted otherwise,
/// tolerating already-present. A rid without an event row is not a
/// check-in (a phantom placeholder) and never enters the table.
fn leafCheckOne(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
const is_leaf = self.events.contains(rid) and !self.hasSameBranchChild(rid);
if (is_leaf) {
try self.leaf_table.put(self.gpa, rid, {});
} else {
_ = self.leaf_table.swapRemove(rid);
}
}
/// The canonical leaf test's disqualifier (Section 7.2): any
/// parent-link naming `rid` as parent whose child is on the same
/// branch. Deliberately NOT filtered by the primary/merge distinction —
/// a same-branch child reached only via a merge edge still counts.
fn hasSameBranchChild(self: *const RepoState, rid: Rid) bool {
for (self.plinks.keys()) |key| {
if (key.parent == rid and self.sameBranch(rid, key.child)) return true;
}
return false;
}
/// Whether two check-ins are on the same branch: their branch values
/// (Section 6.1) compare equal.
fn sameBranch(self: *const RepoState, a: Rid, b: Rid) bool {
return std.mem.eql(u8, self.branchValueOf(a), self.branchValueOf(b));
}
/// The branch value of `rid` (Section 6.1): the value of its active
/// (tagtype > 0) branch tag, or the default branch name when no such
/// tag is in effect (Section 6.4). The configurable main-branch setting
/// is not derived here yet; the fallback is the literal default.
fn branchValueOf(self: *const RepoState, rid: Rid) []const u8 {
if (self.tagxref.get(.{ .rid = rid, .tag = branch_tag_id })) |xr| {
if (xr.tagtype != .cancel) {
if (xr.value) |v| return v;
}
}
return default_branch;
}
/// Whether `rid` carries an active closed tag (Section 7.4).
fn hasActiveClosed(self: *const RepoState, rid: Rid) bool {
if (self.tagxref.get(.{ .rid = rid, .tag = closed_tag_id })) |xr| {
return xr.tagtype != .cancel;
}
return false;
}
/// Intern a tag name to its id (Section 2): "branch" and "closed" are
/// the fixed ids 8 and 9; every other name is assigned the next id
/// starting at 10, first-seen order.
fn internTag(self: *RepoState, name: []const u8) error{OutOfMemory}!TagId {
std.debug.assert(name.len != 0);
if (std.mem.eql(u8, name, "branch")) return branch_tag_id;
if (std.mem.eql(u8, name, "closed")) return closed_tag_id;
if (self.tag_names.get(name)) |id| return id;
std.debug.assert(self.next_tag < std.math.maxInt(TagId));
const owned = try self.gpa.dupe(u8, name);
errdefer self.gpa.free(owned);
const id = self.next_tag;
try self.tag_names.put(self.gpa, owned, id);
self.next_tag += 1;
return id;
}
/// Direct tag application (Section 5.3): supersede-by-mtime with a
/// >=-skip, raw type stored verbatim (srcid the carrier, origid the
/// target), value cleared to null for a cancel. The Section 5.4
/// singleton-to-cancel downgrade is a propagation-entry concern, not
/// applied to the stored row here (a stored singleton stays active).
fn applyDirect(self: *RepoState, target: Rid, op: TagOp, srcid: Rid, mtime: Mtime) error{OutOfMemory}!void {
std.debug.assert(target >= 1);
const tag = try self.internTag(op.name);
const key = TagKey{ .rid = target, .tag = tag };
const existing = self.tagxref.get(key);
if (existing) |e| {
if (e.mtime >= mtime) return; // step 1: skip
}
var new_value: ?[]u8 = null;
if (op.type != .cancel) { // step 3: cancel clears to null
if (op.value) |v| new_value = try self.gpa.dupe(u8, v);
}
errdefer if (new_value) |v| self.gpa.free(v);
// `put` assigns the value atomically with the insert/overwrite, so
// no half-initialized slot can be left behind on an OOM path — a
// manual getOrPut-then-assign would leave the newly created slot
// uninitialized if the dupe above failed after the slot existed.
try self.tagxref.put(self.gpa, key, .{ .tagtype = op.type, .srcid = srcid, .origid = target, .value = new_value, .mtime = mtime });
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
}
std.debug.assert(self.tagxref.get(key).?.mtime >= mtime);
if (tag == branch_tag_id) try self.scheduleLeafRecheck(target); // Section 7.6 b1
}
/// Propagation walk (Section 5.4) rooted at `start`, carrying `ptype`
/// (propagate or cancel only) with `value`/`origid`/`mtime` down the
/// primary-child chain until no further child qualifies. Bounded by the
/// primary-parent forest: in-degree <= 1 on primary edges means each
/// node is reachable from one walk at most once, so pops are bounded by
/// the crosslinked check-in count.
fn propagate(self: *RepoState, start: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!void {
std.debug.assert(ptype == .cancel or ptype == .propagate);
var worklist: std.ArrayList(Rid) = .empty;
defer worklist.deinit(self.gpa);
try worklist.append(self.gpa, start);
const max_pops = self.events.count() + 1;
var pops: usize = 0;
var head: usize = 0;
while (head < worklist.items.len) : (head += 1) {
const a = worklist.items[head];
pops += 1;
std.debug.assert(pops <= max_pops);
for (self.plinks.keys(), self.plinks.values()) |key, row| {
if (key.parent != a or !row.is_primary) continue; // never a merge edge
const child = key.child;
const changed = try self.propagateOne(child, tag, ptype, value, origid, mtime);
if (changed) {
try worklist.append(self.gpa, child);
if (tag == branch_tag_id) try self.scheduleLeafRecheck(child); // Section 7.6 b2
}
}
}
}
/// Apply one propagation step to `child` (Section 5.4 steps 3-4):
/// qualifies iff no existing row, or an inherited (srcid 0) row with a
/// strictly earlier mtime. A nonzero-srcid row is never overwritten
/// (Section 5.5); an equal mtime is retained. Returns whether the child
/// was updated, so the caller can enqueue it for further propagation —
/// a no-op cancel delete on an absent row still counts, matching the
/// literal "always qualifies" text of step 3.
fn propagateOne(self: *RepoState, child: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!bool {
const key = TagKey{ .rid = child, .tag = tag };
const existing = self.tagxref.get(key);
const qualifies = if (existing) |e| (e.srcid == 0 and e.mtime < mtime) else true;
if (!qualifies) return false;
if (existing) |e| std.debug.assert(e.srcid == 0); // never overwrite a direct row
switch (ptype) {
.propagate => {
var new_value: ?[]u8 = null;
if (value) |v| new_value = try self.gpa.dupe(u8, v);
errdefer if (new_value) |v| self.gpa.free(v);
// Store first, free the old value only once the put has
// succeeded: freeing before a fallible put would leave the
// map's still-live entry pointing at freed memory if the put
// itself failed (matches applyDirect's ordering).
try self.tagxref.put(self.gpa, key, .{ .tagtype = .propagate, .srcid = 0, .origid = origid, .value = new_value, .mtime = mtime });
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
}
},
.cancel => {
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
_ = self.tagxref.remove(key);
}
},
.singleton => unreachable, // rejected by the propagate() precondition
}
return true;
}
const SnapRow = struct { tag: TagId, xr: Xref };
/// Re-propagate `parent`'s full tag set (Section 4.2 step 4a): a
/// snapshot first, since the map mutates during the walk. Every
/// singleton row is downgraded to cancel per the Section 5.4 driving
/// rule; cancel and propagate rows pass through unchanged.
fn repropagateSet(self: *RepoState, parent: Rid) error{OutOfMemory}!void {
var rows: std.ArrayList(SnapRow) = .empty;
defer rows.deinit(self.gpa);
var it = self.tagxref.iterator();
while (it.next()) |entry| {
if (entry.key_ptr.rid == parent) {
try rows.append(self.gpa, .{ .tag = entry.key_ptr.tag, .xr = entry.value_ptr.* });
}
}
for (rows.items) |row| {
const pt: TagType = if (row.xr.tagtype == .singleton) .cancel else row.xr.tagtype;
std.debug.assert(pt == .cancel or pt == .propagate);
try self.propagate(parent, row.tag, pt, row.xr.value, row.xr.origid, row.xr.mtime);
}
}
/// Schedule an incremental leaf recheck for `rid` and each of its
/// direct parents (Section 7.3), tolerating an rid with no parents yet.
fn scheduleLeafRecheck(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
try self.pending_leaf.put(self.gpa, rid, {});
for (self.plinks.keys()) |key| {
if (key.child == rid) try self.pending_leaf.put(self.gpa, key.parent, {});
}
}
};
/// Iterator over the leaf table, in table order.
pub const LeafIterator = struct {
rids: []const Rid,
index: usize = 0,
pub fn next(self: *LeafIterator) ?Rid {
if (self.index == self.rids.len) return null;
defer self.index += 1;
return self.rids[self.index];
}
};
// ---------------------------------------------------------------------------
// Tests. Expected values come from draft-fossil-repo-state-00 only.
// ---------------------------------------------------------------------------
const t = std.testing;
// 64-hex-character hashes, distinct per letter.
const h_a = "a" ** 64;
const h_b = "b" ** 64;
const h_c = "c" ** 64;
const h_d = "d" ** 64;
const h_e = "e" ** 64;
const h_f = "f" ** 64;
const h_g = "0" ** 64;
const h_h = "1" ** 64;
fn countLeaves(rs: *const RepoState) usize {
var it = rs.leaves();
var n: usize = 0;
while (it.next()) |_| n += 1;
return n;
}
test "repostate §2: intern assigns one stable rid per hash" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
const s = ms.store();
const ra = try s.intern(h_a);
const rb = try s.intern(h_b);
try t.expect(ra != rb);
try t.expectEqual(ra, try s.intern(h_a));
try t.expectEqualStrings(h_a, s.hashOf(ra));
try t.expectEqualStrings(h_b, s.hashOf(rb));
}
test "repostate §4.2: an interned but absent artifact is a phantom with no content" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
const s = ms.store();
const rid = try s.intern(h_a);
try t.expectEqual(@as(?[]const u8, null), s.content(rid));
// The referenced artifact arrives: the phantom upgrades in place.
try t.expectEqual(rid, try s.put(h_a, "payload"));
try t.expectEqualStrings("payload", s.content(rid).?);
// A repeat put of the same hash is a no-op.
try t.expectEqual(rid, try s.put(h_a, "payload"));
try t.expectEqualStrings("payload", s.content(rid).?);
}
test "repostate §5.1: tag types encode cancel=0, singleton=1, propagate=2" {
try t.expectEqual(0, @intFromEnum(TagType.cancel));
try t.expectEqual(1, @intFromEnum(TagType.singleton));
try t.expectEqual(2, @intFromEnum(TagType.propagate));
}
test "repostate §3.1: a repeated parent reference collapses to one linkage row" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{ h_a, h_a } });
try t.expectEqual(@as(usize, 1), rs.parentCount(rb));
try t.expectEqual(@as(?Rid, ra), rs.primaryParentOf(rb));
try t.expect(!rs.isLeaf(ra));
try t.expect(rs.isLeaf(rb));
}
test "repostate §3.2: the first listed parent is the primary parent" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 2 });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{ h_a, h_b } });
try t.expectEqual(@as(usize, 2), rs.parentCount(rc));
try t.expectEqual(@as(?Rid, ra), rs.primaryParentOf(rc));
}
test "repostate §3.2: a sole parent is the primary parent" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expectEqual(@as(?Rid, ra), rs.primaryParentOf(rb));
}
test "repostate §4.2: re-crosslinking a linked artifact is a linkage no-op" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rb_again = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expectEqual(rb, rb_again);
try t.expectEqual(@as(usize, 1), rs.parentCount(rb));
try t.expectEqual(@as(usize, 1), countLeaves(&rs));
try t.expect(rs.isLeaf(rb));
}
test "repostate §4.2: an absent parent hash yields a phantom, resolved when it arrives" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
// The child arrives first; its parent hash resolves to a phantom
// placeholder rather than a fatal error.
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const ra = rs.primaryParentOf(rb).?;
try t.expectEqual(@as(?Mtime, null), rs.mtimeOf(ra));
// A phantom is not a check-in: it never enters the leaf table.
try t.expect(!rs.isLeaf(ra));
try t.expect(rs.isLeaf(rb));
try t.expectEqual(@as(usize, 1), countLeaves(&rs));
// The referenced artifact arrives and is crosslinked: the recorded
// linkage becomes visible in the derived views.
try t.expectEqual(ra, try rs.crosslink(.{ .hash = h_a, .mtime = 1 }));
try t.expectEqual(@as(?Mtime, 1), rs.mtimeOf(ra));
try t.expect(!rs.isLeaf(ra));
try t.expect(rs.isLeaf(rb));
try t.expectEqual(@as(usize, 1), countLeaves(&rs));
}
test "repostate §7.2: a child reached only via a merge edge disqualifies the leaf" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_a} });
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_b, h_c } });
// rc's only child rd is reached via a non-primary (merge) edge; the
// canonical test applies no primary/merge filter.
try t.expect(!rs.isLeaf(rb));
try t.expect(!rs.isLeaf(rc));
try t.expect(rs.isLeaf(rd));
try t.expectEqual(@as(usize, 1), countLeaves(&rs));
}
test "repostate §7.3: a root check-in with no children is a leaf" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
try t.expect(rs.isLeaf(ra));
var it = rs.leaves();
try t.expectEqual(@as(?Rid, ra), it.next());
try t.expectEqual(@as(?Rid, null), it.next());
}
test "repostate §7.3: a new child retroactively removes its parent's leaf status" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
try t.expect(rs.isLeaf(ra));
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect(!rs.isLeaf(ra));
try t.expect(rs.isLeaf(rb));
}
test "repostate §7.3: full rebuild reproduces the incrementally maintained table" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_a} });
_ = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_b, h_c } });
// An independent root with no children: a candidate the rebuild MUST
// include even though it appears in no parent-link.
const re = try rs.crosslink(.{ .hash = h_e, .mtime = 5 });
var before: [8]Rid = undefined;
const n_before = collectLeaves(&rs, &before);
try rs.rebuildLeaves();
var after: [8]Rid = undefined;
const n_after = collectLeaves(&rs, &after);
try t.expectEqual(n_before, n_after);
std.mem.sort(Rid, before[0..n_before], {}, std.sort.asc(Rid));
std.mem.sort(Rid, after[0..n_after], {}, std.sort.asc(Rid));
try t.expectEqualSlices(Rid, before[0..n_before], after[0..n_after]);
try t.expect(rs.isLeaf(re));
try t.expect(!rs.isLeaf(rb));
try t.expect(!rs.isLeaf(rc));
}
/// White-box lookup of a tagxref row by tag name, for test assertions only.
fn tagRowFor(rs: *RepoState, rid: Rid, name: []const u8) error{OutOfMemory}!?RepoState.Xref {
const tag = try rs.internTag(name);
return rs.tagxref.get(.{ .rid = rid, .tag = tag });
}
test "repostate §5.3: a strictly later mtime supersedes an earlier one" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v2", xr.value.?);
try t.expectEqual(@as(Mtime, 6), xr.mtime);
}
test "repostate §5.3: a strictly earlier mtime is skipped" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v1", xr.value.?);
}
test "repostate §5.3: an equal-mtime re-application is skipped" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
// Derivation §5.3.1: ">= ... MUST be skipped"; the equal-mtime case is
// impl-defined, so our >= retains the existing (first) write.
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v1", xr.value.?);
}
test "repostate §5.3: a cancel application clears the value to null" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5, .tags = &.{
.{ .type = .cancel, .name = "t1", .target = null, .value = "z" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqual(TagType.cancel, xr.tagtype);
try t.expect(xr.value == null);
}
test "repostate §5.3/§4.2: a singleton tag triggers no propagation walk" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "v" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
const xr = (try tagRowFor(&rs, try rs.store.intern(h_a), "t1")).?;
try t.expectEqual(TagType.singleton, xr.tagtype);
}
test "repostate §5.2: tagxref holds at most one row per (rid, tag)" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
try t.expectEqual(@as(usize, 1), rs.tagxref.count());
try t.expectEqualStrings("v2", (try tagRowFor(&rs, ra, "t1")).?.value.?);
}
test "repostate §5.4: a propagating tag reaches primary-chain descendants" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expectEqualStrings("v", (try tagRowFor(&rs, rb, "t1")).?.value.?);
try t.expectEqualStrings("v", (try tagRowFor(&rs, rc, "t1")).?.value.?);
}
test "repostate §5.4: a propagated row carries origin value and mtime with srcid 0" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 3, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
const xr = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqual(@as(Rid, 0), xr.srcid);
try t.expectEqual(ra, xr.origid);
try t.expectEqualStrings("v", xr.value.?);
try t.expectEqual(@as(Mtime, 3), xr.mtime);
}
test "repostate §5.4: propagation does not cross a merge edge" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} }); // primary child of A
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 3 }); // unrelated root R
// M's primary parent is R; B is only a merge (non-primary) parent.
const rm = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_c, h_b } });
try t.expect((try tagRowFor(&rs, rm, "t1")) == null);
}
test "repostate §5.4: a directly-applied entry is never overwritten by propagation" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v1" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqualStrings("v2", xr.value.?);
try t.expect(xr.srcid != 0);
}
test "repostate §5.4: an inherited entry of equal mtime is retained" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const tag = try rs.internTag("t1");
// Seed an inherited row directly (white-box): the exact tie condition
// under test is not otherwise reachable through crosslink alone.
const old_val = try t.allocator.dupe(u8, "old");
try rs.tagxref.put(t.allocator, .{ .rid = rc, .tag = tag }, .{ .tagtype = .propagate, .srcid = 0, .origid = rp, .value = old_val, .mtime = 5 });
try rs.propagate(rp, tag, .propagate, "new", rp, 5);
const xr = rs.tagxref.get(.{ .rid = rc, .tag = tag }).?;
try t.expectEqualStrings("old", xr.value.?);
}
test "repostate §5.5: a cancel tag halts propagation to descendants" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .cancel, .name = "t1", .target = null, .value = null },
} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
try t.expectEqual(TagType.cancel, (try tagRowFor(&rs, rb, "t1")).?.tagtype);
}
test "repostate §5.5: a singleton on a parent blocks propagation through it" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
const xrb = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqual(TagType.singleton, xrb.tagtype);
try t.expectEqualStrings("w", xrb.value.?);
}
test "repostate §5.4: the propagation entry rejects a singleton, reaching descendants as cancel" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
}
test "repostate §4.2 step 1: a tag on an absent target attaches to its phantom and survives arrival" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = h_h, .value = "v" },
} });
const rh = try rs.store.intern(h_h);
try t.expect(!rs.isLeaf(rh)); // phantom, not a check-in
try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
const rh_again = try rs.crosslink(.{ .hash = h_h, .mtime = 2 });
try t.expectEqual(rh, rh_again);
try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
try t.expect(rs.isLeaf(rh));
}
test "repostate §4.2 step 4: a new child inherits its primary parent's propagating tag" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const xr = (try tagRowFor(&rs, rc, "t1")).?;
try t.expectEqualStrings("v", xr.value.?);
try t.expectEqual(@as(Rid, 0), xr.srcid);
try t.expectEqual(rp, xr.origid);
}
test "repostate §4.2 step 5: re-crosslink re-runs tag application idempotently" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rec = Record{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} };
const r1 = try rs.crosslink(rec);
const before = countLeaves(&rs);
const r2 = try rs.crosslink(rec);
try t.expectEqual(r1, r2);
try t.expectEqual(before, countLeaves(&rs));
try t.expectEqual(@as(usize, 1), rs.tagxref.count());
try t.expectEqualStrings("v", (try tagRowFor(&rs, r1, "t1")).?.value.?);
}
test "repostate §7.2/§6.1: a fork onto a new branch leaves the parent a leaf of its own branch" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .propagate, .name = "branch", .target = null, .value = "feature" },
} });
try t.expect(rs.isLeaf(ra));
try t.expect(rs.isLeaf(rb));
}
test "repostate §7.6: directly applying a branch tag re-evaluates leaf status" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect(!rs.isLeaf(ra)); // same branch, has a child
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .tags = &.{
.{ .type = .propagate, .name = "branch", .target = h_b, .value = "feature" },
} });
try t.expect(rs.isLeaf(ra));
}
test "repostate §7.6: branch propagation re-evaluates a descendant's leaf status" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
// C carries its own direct branch tag, so it blocks any further
// propagation past it (Section 5.5: a nonzero-srcid row is never
// overwritten by an inherited one).
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b}, .tags = &.{
.{ .type = .propagate, .name = "branch", .target = null, .value = "trunk" },
} });
try t.expect(!rs.isLeaf(ra));
try t.expect(!rs.isLeaf(rb)); // same branch (trunk) as its child C
try t.expect(rs.isLeaf(rc));
// A, a pre-existing check-in with a child already in place, now gets a
// branch tag. The walk reaches B — B carries no direct branch row of
// its own, so it inherits "feature" — while C's direct "trunk" row
// blocks the walk from reaching any further. B did not itself get
// crosslinked by this call, so nothing but the propagation step re-
// evaluates it. Derivation Section 7.6 second bullet: "when a branch
// tag propagates to descendants, each descendant that gains or loses
// the propagating tag MUST have its leaf status re-evaluated."
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 10, .tags = &.{
.{ .type = .propagate, .name = "branch", .target = null, .value = "feature" },
} });
try t.expect(!rs.isLeaf(ra)); // A still shares a branch with child B
try t.expect(rs.isLeaf(rb)); // B's only child C stayed on trunk: B gained leaf status
try t.expect(rs.isLeaf(rc));
}
test "repostate §7.4: a leaf carrying an active closed marker is not an open leaf" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "closed", .target = null, .value = null },
} });
try t.expect(rs.isLeaf(ra));
try t.expect(!rs.isOpenLeaf(ra));
}
test "repostate §7.4: cancelling the closed marker reopens the leaf" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "closed", .target = null, .value = null },
} });
try t.expect(!rs.isOpenLeaf(ra));
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 6, .tags = &.{
.{ .type = .cancel, .name = "closed", .target = h_a, .value = null },
} });
try t.expect(rs.isOpenLeaf(ra));
}
fn collectLeaves(rs: *const RepoState, out: []Rid) usize {
var it = rs.leaves();
var n: usize = 0;
while (it.next()) |rid| : (n += 1) out[n] = rid;
return n;
}
fn crosslinkNoLeak(gpa: std.mem.Allocator) !void {
var ms = MemStore.init(gpa);
defer ms.deinit();
var rs = RepoState.init(gpa, ms.store());
defer rs.deinit();
// Self-branch root plus a tag on a not-yet-stored (phantom) target, so
// internTag/applyDirect/propagate all allocate.
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "branch", .target = null, .value = "feature" },
.{ .type = .propagate, .name = "t1", .target = h_g, .value = "v" },
} });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
// Phantom parent plus a merge, so every allocation site is exercised.
_ = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_b, h_c } });
// A cancel and a singleton (+closed), exercising the value-clear and
// downgrade-at-repropagation paths.
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_a}, .tags = &.{
.{ .type = .cancel, .name = "t1", .target = null, .value = null },
.{ .type = .singleton, .name = "closed", .target = null, .value = null },
} });
_ = try rs.crosslink(.{ .hash = h_g, .mtime = 5 }); // the phantom target arrives
try rs.rebuildLeaves();
}
test "repostate §4.2: crosslink survives allocation failure without leaking" {
try t.checkAllAllocationFailures(t.allocator, crosslinkNoLeak, .{});
}