//! 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");
const flate = std.compress.flate;
/// delta §4 apply — repostate sits above `delta` in the RFC layering
/// (delta -> artifact -> repostate), so a direct file import is layer-legal
/// and introduces no cycle. Used to reconstruct a delta-wire entry's plaintext.
const delta = @import("delta.zig");
/// 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 (Section 3.1's event.mtime). Ordinal
/// comparison alone drives Sections 7-9's leaf/branch/current-trunk views.
/// Section 8.3 form 7 (date-form name resolution) additionally interprets
/// both a parsed timestamp and every stored event.mtime on one shared
/// millisecond timeline — Unix-epoch milliseconds computed by a pure
/// civil-date calculation below, never an ambient clock. The choice of
/// epoch is encapsulated in that calculation and is epoch-independent for
/// *which* check-in resolves: the calendar-to-timeline mapping is
/// monotonic and applied identically to the query bound and to stored
/// mtimes, so every other derived view — which only ever compares mtimes
/// against each other — is unaffected by this reinterpretation.
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 = &.{},
};
/// Sync §4.1/§7.2 — a stored artifact's on-the-wire cfile payload: the §4.1
/// zlib `container` (4-byte big-endian uncompressed length + RFC1950 stream)
/// retransmitted byte-for-byte. Borrows the store; valid until the next
/// mutation. USIZE needs no separate field: it is the container's first four
/// bytes (§4.1). A distinct type from `content()`'s plaintext `[]const u8` so
/// the two never blur at the vtable boundary.
pub const WireFrame = struct {
container: []const u8,
/// Null for the §7.2 full form (the container reconstructs the whole
/// artifact; USIZE is its own 4-byte prefix). Non-null for the delta form:
/// the container holds a [FossilDelta] against `src_hash`, and `target_size`
/// is the reconstructed-artifact size (the cfile USIZE, delta §3.2 — NEVER
/// the container prefix, which is the raw delta length). The full-form call
/// sites are unchanged: they never read this field.
delta: ?Delta = null,
pub const Delta = struct {
/// The basis artifact's wire name (DELTASRC), borrowing the store.
src_hash: []const u8,
/// delta §3.2 — the reconstructed target length; the cfile USIZE.
target_size: u64,
};
};
/// Sync §7.2/§4.1 — the wire form a receiver retains for an already-stored rid
/// so a later serve retransmits it verbatim. The write-side twin of
/// `WireFrame`: `retain()` records what `wire()` later reads. Advisory — a
/// store MAY drop it and the receiver still persists correct plaintext, so no
/// correctness rests on retention, only compactness on re-serve.
pub const WireIngest = union(enum) {
/// A §4.1 full-artifact zlib container, retained verbatim (the §7.2 full
/// form; USIZE is the container's own 4-byte prefix).
full: []const u8,
/// A §4.1 zlib container of a [FossilDelta] against `src` (DELTASRC), plus
/// the reconstructed-target size (delta §3.2 — the cfile USIZE, NEVER the
/// container prefix).
delta: Delta,
pub const Delta = struct {
src: []const u8,
container: []const u8,
target_size: u64,
};
};
/// 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,
/// Resolve a hash to its rid WITHOUT creating a phantom; null when the
/// hash is unknown. Unlike `intern`, this is a pure membership query —
/// a receiver deciding whether it holds gimme'd content must not mint a
/// phantom for a hash it has never seen (Sync §3.3).
lookup: *const fn (context: *anyopaque, hash: []const u8) ?Rid,
/// The number of entries in the store. Rids are dense in `1..=count`,
/// so a peer walks every entry with `rid in 1..=count` and classifies
/// each via `content(rid)` (null => phantom, non-null => held) to
/// announce holdings and request phantoms (Sync §3.2/§3.3).
count: *const fn (context: *anyopaque) usize,
/// Sync §7.2 — the stored full-content §4.1 container for `rid`,
/// retransmitted verbatim, or null when the store holds no such form
/// for it (a raw, delta, or phantom entry; the serve loop then falls
/// back to compressing `content()`). Nullable and general: any store
/// MAY decline and the server still answers correctly, so this never
/// special-cases one backing store.
wire: *const fn (context: *anyopaque, rid: Rid) ?WireFrame,
/// Sync §7.2/§4.1 — retain the wire form the peer delivered for `rid`
/// (already `put`/reconstructed) so a later serve retransmits the
/// stored form verbatim. The write-side twin of `wire`. Advisory: a
/// store MAY ignore it and the receiver still persists correct
/// plaintext, so correctness never depends on retention. Only
/// `OutOfMemory` escapes.
retain: *const fn (context: *anyopaque, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void,
};
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);
}
pub fn lookup(self: ArtifactStore, hash: []const u8) ?Rid {
return self.vtable.lookup(self.context, hash);
}
pub fn count(self: ArtifactStore) usize {
return self.vtable.count(self.context);
}
pub fn wire(self: ArtifactStore, rid: Rid) ?WireFrame {
return self.vtable.wire(self.context, rid);
}
pub fn retain(self: ArtifactStore, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void {
return self.vtable.retain(self.context, rid, ingest);
}
};
/// 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,
/// The plaintext, or null. For a `wire`-backed entry this is null
/// until the first plaintext read materialises (and memoises) it.
bytes: ?[]u8,
/// The stored §4.1 container this entry retransmits verbatim (Sync
/// §7.2), or null for a raw `put` or a phantom. An entry that carries a
/// container materialises its plaintext lazily into `bytes` on first
/// `content()` (memoised there), so the clone serve path never inflates.
/// For a delta-wire entry (`wire_delta` non-null) the container holds a
/// [FossilDelta], not the whole artifact.
wire: ?[]u8 = null,
/// Sync §7.2 delta form: when set, `wire` is a §4.1 container of a
/// [FossilDelta] against `src_hash`, and `target_size` is the
/// reconstructed size (the cfile USIZE, delta §3.2). content()
/// reconstructs against the (materialised) basis lazily; `wire()`
/// serves the delta form. Null for a full-form or raw entry.
wire_delta: ?WireDelta = null,
};
const WireDelta = struct { src_hash: []u8, target_size: u64 };
/// Sync §4.1 — the container's declared uncompressed length is bounded
/// before any inflate, so a lying length field cannot drive unbounded
/// allocation. Mirrors `logstore.max_payload`.
const max_wire_payload: usize = 1 << 30;
/// Explicit upper bound on delta-chain reconstruction depth while
/// materialising a delta-wire entry's plaintext — the read-side twin of
/// `logstore.max_delta_chain`, with headroom for a retained foreign chain.
/// A chain deeper than this yields null (treated as unreconstructable),
/// never unbounded recursion.
const max_wire_delta_chain: usize = 64;
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);
if (entry.wire) |container| self.gpa.free(container);
if (entry.wire_delta) |wd| self.gpa.free(wd.src_hash);
}
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,
.lookup = lookupImpl,
.count = countImpl,
.wire = wireImpl,
.retain = retainImpl,
};
/// Sync §7.2/§4.1 — record the wire form the peer delivered for `rid`
/// verbatim so `wire()` re-serves it. Unlike `putWire`/`putWireDelta`, this
/// sets the container even when `bytes` is already materialised: the receive
/// path stores reconstructed plaintext via `put` FIRST, then retains the
/// wire that produced it. Idempotent: a second retain for an rid already
/// carrying a container is a no-op (content is hash-addressed, so the first
/// retained form stands). Duplicates the container (and `src`) — the store
/// owns its bytes, matching `put`.
fn retainImpl(context: *anyopaque, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void {
const self: *MemStore = @ptrCast(@alignCast(context));
const entry = self.entryOf(rid);
if (entry.wire != null) return; // already retained; first form wins
switch (ingest) {
.full => |container| {
std.debug.assert(container.len >= 4); // §4.1 — 4-byte length prefix
entry.wire = try self.gpa.dupe(u8, container);
},
.delta => |d| {
std.debug.assert(d.container.len >= 4); // §4.1 — 4-byte length prefix
std.debug.assert(d.src.len != 0);
const c = try self.gpa.dupe(u8, d.container);
errdefer self.gpa.free(c);
const s = try self.gpa.dupe(u8, d.src);
entry.wire = c;
entry.wire_delta = .{ .src_hash = s, .target_size = d.target_size };
},
}
}
/// Sync §4.1/§7.2 — store the already-encoded full-content §4.1 `container`
/// for `hash` verbatim so a clone serves it without recompressing (the whole
/// point of serving the stored form). Idempotent + phantom-upgrade like
/// `put`; the plaintext is NOT materialised here — `content()` inflates
/// lazily on first read. The `container` is duplicated (the store owns its
/// bytes, matching `put`), so the caller's transient buffer may be freed.
pub fn putWire(
self: *MemStore,
hash: []const u8,
container: []const u8,
) error{OutOfMemory}!Rid {
std.debug.assert(container.len >= 4); // §4.1 — the container carries at least its 4-byte length prefix
const rid = try internImpl(self, hash);
const entry = self.entryOf(rid);
// Content is addressed by hash: a repeat of the same hash carries the
// same artifact, and §4.1 receivers are level-independent, so a
// re-encoded container need not be byte-identical — keep the first.
if (entry.wire != null) return rid;
entry.wire = try self.gpa.dupe(u8, container);
return rid;
}
/// Sync §7.2 delta form — store the already-encoded §4.1 `container` of a
/// [FossilDelta] against `src_hash`, plus the reconstructed-target
/// `target_size` (the cfile USIZE, delta §3.2), so a clone serves the delta
/// form verbatim without re-encoding. Idempotent + phantom-upgrade like
/// `putWire`; the plaintext materialises lazily against the basis on first
/// `content()`. Duplicates both the container and `src_hash` (the store owns
/// its bytes). Precondition: the basis is (or will be) stored under
/// `src_hash` for `content()` to reconstruct — a serve snapshot inserts the
/// basis at an earlier rid (loadContentStore's persisted order).
pub fn putWireDelta(
self: *MemStore,
hash: []const u8,
container: []const u8,
src_hash: []const u8,
target_size: u64,
) error{OutOfMemory}!Rid {
std.debug.assert(container.len >= 4); // §4.1 — the container carries its 4-byte length prefix
std.debug.assert(src_hash.len != 0);
const rid = try internImpl(self, hash);
const entry = self.entryOf(rid);
// Content is addressed by hash: a repeat carries the same artifact.
if (entry.wire != null or entry.bytes != null) return rid;
const c = try self.gpa.dupe(u8, container);
errdefer self.gpa.free(c);
const s = try self.gpa.dupe(u8, src_hash);
entry.wire = c;
entry.wire_delta = .{ .src_hash = s, .target_size = target_size };
return rid;
}
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.materialize(rid);
}
/// The plaintext for `rid`: the memoised `bytes` if present, else — for a
/// `wire`-backed entry — the stored §4.1 container inflated and memoised
/// into `bytes` so the borrowed `[]const u8` `content()` contract holds
/// (MemStore owns `bytes` until `deinit`). Returns null for a phantom (no
/// `bytes`, no `wire`) and — since the vtable `content` cannot signal an
/// error — for a container that fails to inflate (an OOM or, for a validated
/// store, never-occurring corrupt frame). A null here is safe: every
/// held/phantom classification on the correctness path treats an entry with
/// a non-null `wire` as held via `wire()`, never re-deriving that fact from
/// `content()`.
fn materialize(self: *MemStore, rid: Rid) ?[]const u8 {
return self.materializeDepth(rid, max_wire_delta_chain);
}
/// `materialize` with an explicit delta-chain depth bound. A delta-wire
/// entry inflates its container to the raw [FossilDelta], resolves the basis
/// by hash, materialises the basis (one depth deeper), and applies the delta
/// — memoising the result. `depth == 0` on a delta entry yields null
/// (chain too deep), never unbounded recursion.
fn materializeDepth(self: *MemStore, rid: Rid, depth: usize) ?[]const u8 {
const entry = self.entryOf(rid);
if (entry.bytes) |b| return b;
const container = entry.wire orelse return null;
if (entry.wire_delta) |wd| {
if (depth == 0) return null; // bounded: a chain deeper than the cap is unreconstructable here
const raw = containerDecode(self.gpa, container, max_wire_payload) catch return null;
defer self.gpa.free(raw);
const src_rid = self.by_hash.get(wd.src_hash) orelse return null;
const src = self.materializeDepth(src_rid, depth - 1) orelse return null;
const plain = delta.apply(self.gpa, src, raw) catch return null;
self.entryOf(rid).bytes = plain; // memoise; entries is not resized here, so the pointer is stable
return plain;
}
const plain = containerDecode(self.gpa, container, max_wire_payload) catch return null;
self.entryOf(rid).bytes = plain; // memoise; entries is not resized here, so the pointer is stable
return plain;
}
fn wireImpl(context: *anyopaque, rid: Rid) ?WireFrame {
const self: *MemStore = @ptrCast(@alignCast(context));
const entry = self.entryOf(rid);
const container = entry.wire orelse return null;
if (entry.wire_delta) |wd| {
return .{ .container = container, .delta = .{ .src_hash = wd.src_hash, .target_size = wd.target_size } };
}
return .{ .container = container };
}
fn hashOfImpl(context: *anyopaque, rid: Rid) []const u8 {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entryOf(rid).hash;
}
fn lookupImpl(context: *anyopaque, hash: []const u8) ?Rid {
const self: *MemStore = @ptrCast(@alignCast(context));
std.debug.assert(hash.len != 0);
return self.by_hash.get(hash);
}
fn countImpl(context: *anyopaque) usize {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entries.items.len;
}
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)];
}
};
/// Sync §4.1 L1192-1213 — decode the fossil zlib container (4-byte big-endian
/// uncompressed length, then an RFC1950 zlib stream) that `MemStore` stores
/// verbatim for a wire-backed entry. `max_output` bounds the declared length
/// before any inflate work, and the stream is pumped no further than
/// `declared + 1` bytes, so a length lie cannot drive unbounded allocation.
/// Decode is compression-level-independent (§4.1 L1204-1206). A short header,
/// a length mismatch, or a bad stream is `error.Corrupt`. This is the store
/// layer's own §4.1 reader — `logstore` and `sync` each carry their own cited
/// copy at their layer; a single shared codec is a noted follow-up (repostate
/// sits below `sync` and cannot import it, and above `logstore` which imports
/// this module).
fn containerDecode(gpa: std.mem.Allocator, wire: []const u8, max_output: usize) error{ OutOfMemory, Corrupt }![]u8 {
if (wire.len < 4) return error.Corrupt;
const declared = std.mem.readInt(u32, wire[0..4], .big);
if (declared > max_output) return error.Corrupt;
var fr = std.Io.Reader.fixed(wire[4..]);
const window = gpa.alloc(u8, flate.max_window_len) catch return error.OutOfMemory;
defer gpa.free(window);
var dc = flate.Decompress.init(&fr, .zlib, window);
var aw = std.Io.Writer.Allocating.init(gpa);
defer aw.deinit();
const cap: usize = @as(usize, declared) + 1;
var total: usize = 0;
const max_iters: usize = wire.len + cap + 64;
var iters: usize = 0;
while (total < cap and iters < max_iters) : (iters += 1) {
const n = dc.reader.stream(&aw.writer, .limited(cap - total)) catch |err| switch (err) {
error.EndOfStream => break,
error.WriteFailed => return error.OutOfMemory,
error.ReadFailed => return error.Corrupt,
};
total += n;
}
if (iters >= max_iters) return error.Corrupt;
if (total != declared) return error.Corrupt;
const out = aw.toOwnedSlice() catch return error.OutOfMemory;
std.debug.assert(out.len == declared);
return out;
}
/// 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,
/// Adjacency index over `plinks`, keyed by parent rid to its child edges,
/// so the Section 7.2 same-branch-child test and the Section 5.4
/// propagation walk cost O(out-degree) instead of a scan of every linkage
/// row. `plinks` is append-only — exactly one row per (parent, child) pair,
/// first write wins (Section 3.1) — so each edge is appended once here and
/// never mutated or removed, which is what keeps the index a faithful
/// mirror rather than a second source of truth.
children: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(Edge)) = .empty,
/// Adjacency index over `plinks`, keyed by child rid to its parent edges,
/// so primary-parent lookup (Section 3.2), parent counting (Section 3.3),
/// and leaf-recheck scheduling (Section 7.3) cost O(in-degree). Maintained
/// in lockstep with `children` from the same append-only linkage rows.
parents_by_child: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(Edge)) = .empty,
/// Index over `tagxref`, keyed by rid to the tag ids that currently have a
/// live row on it, so the Section 4.2 step 4a re-propagation snapshots one
/// rid's rows in O(its tag count) rather than iterating the whole table. It
/// is kept exactly precise — a tag is added the instant its (rid, tag) row
/// is first created and removed the instant that row is deleted — so a
/// listed tag always resolves to a live `tagxref` row.
rid_tags: std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(TagId)) = .empty,
/// One adjacency edge: the rid at the other end of a linkage row, plus that
/// row's Section 3.2 primary indicator. In `children` the rid is the child;
/// in `parents_by_child` it is the parent.
const Edge = struct {
rid: Rid,
is_primary: bool,
};
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);
for (self.children.values()) |*list| list.deinit(self.gpa);
self.children.deinit(self.gpa);
for (self.parents_by_child.values()) |*list| list.deinit(self.gpa);
self.parents_by_child.deinit(self.gpa);
for (self.rid_tags.values()) |*list| list.deinit(self.gpa);
self.rid_tags.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 };
// Mirror the new linkage row into both adjacency indexes.
try self.indexPlink(parent, rid, i == 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 propagate
// propagating and cancel effects from their resolved targets.
try self.applyTagOps(rid, rec.mtime, rec.tags);
// 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;
}
/// Ingest the direct and propagated T-card effects of a control artifact.
/// The control carrier is interned solely to preserve its source identity:
/// it never gains an event, parent-link, or leaf-table entry. Scheduled
/// rechecks update only the affected, already-crosslinked check-ins.
pub fn ingestControlTags(self: *RepoState, control_hash: []const u8, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!Rid {
std.debug.assert(control_hash.len != 0);
const carrier = try self.store.intern(control_hash);
try self.applyTagOps(carrier, mtime, tags);
try self.applyPendingLeafChecks();
return carrier;
}
/// 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).
fn applyTagOps(self: *RepoState, carrier: Rid, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!void {
for (tags) |op| {
const target = if (op.target) |uuid| try self.store.intern(uuid) else carrier;
try self.applyDirect(target, op, carrier, 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);
}
}
}
/// 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, {});
}
}
}
/// Record one linkage row in both adjacency indexes: `child` under
/// `parent` in `children`, and `parent` under `child` in
/// `parents_by_child`. Called exactly once per newly created `plinks` row,
/// so no edge is ever duplicated.
fn indexPlink(self: *RepoState, parent: Rid, child: Rid, is_primary: bool) error{OutOfMemory}!void {
std.debug.assert(parent != child);
const cg = try self.children.getOrPut(self.gpa, parent);
if (!cg.found_existing) cg.value_ptr.* = .empty;
try cg.value_ptr.append(self.gpa, .{ .rid = child, .is_primary = is_primary });
const pg = try self.parents_by_child.getOrPut(self.gpa, child);
if (!pg.found_existing) pg.value_ptr.* = .empty;
try pg.value_ptr.append(self.gpa, .{ .rid = parent, .is_primary = is_primary });
}
/// Record that `rid` now carries a live `tagxref` row for `tag`. Called
/// only when a (rid, tag) row transitions from absent to present, so a tag
/// is never listed twice for one rid (asserted in safe builds).
fn addRidTag(self: *RepoState, rid: Rid, tag: TagId) error{OutOfMemory}!void {
const gop = try self.rid_tags.getOrPut(self.gpa, rid);
if (!gop.found_existing) gop.value_ptr.* = .empty;
if (std.debug.runtime_safety) {
for (gop.value_ptr.items) |existing| std.debug.assert(existing != tag);
}
try gop.value_ptr.append(self.gpa, tag);
}
/// Drop `tag` from `rid`'s tag list when its `tagxref` row is removed. The
/// row is unique per (rid, tag), so exactly one entry matches; a caller
/// only reaches here for a row that existed, so the list is non-null.
fn removeRidTag(self: *RepoState, rid: Rid, tag: TagId) void {
const list = self.rid_tags.getPtr(rid) orelse return;
for (list.items, 0..) |listed, i| {
if (listed == tag) {
_ = list.swapRemove(i);
return;
}
}
}
/// 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 {
if (self.parents_by_child.getPtr(child)) |list| return list.items.len;
return 0;
}
/// 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 {
if (self.parents_by_child.getPtr(child)) |list| {
for (list.items) |e| {
if (e.is_primary) return e.rid;
}
}
return null;
}
/// Iterate the parents of a child (Section 3.3 child-to-parent lookup):
/// the primary parent and every merge parent alike, in linkage-row order.
/// Section 3.1 keeps one linkage row per (parent, child) pair, so each
/// parent is yielded exactly once. Invalidated by any RepoState mutation.
pub const ParentIterator = struct {
edges: []const Edge,
i: usize = 0,
pub fn next(self: *ParentIterator) ?Rid {
// Bounded by the in-degree; each step strictly advances i.
if (self.i >= self.edges.len) return null;
const e = self.edges[self.i];
self.i += 1;
return e.rid;
}
};
/// The parents of `child` (Section 3.3): a general-purpose iterator over
/// its linkage rows, primary and merge alike. A root — or an unknown rid —
/// yields nothing. Closed set: returns rids only, never an error.
pub fn parentsOf(self: *const RepoState, child: Rid) ParentIterator {
const edges: []const Edge = if (self.parents_by_child.getPtr(child)) |list| list.items else &.{};
return .{ .edges = edges };
}
/// 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);
}
/// A check-in's branch (Section 6.1): the value of its active
/// (tagtype > 0) branch tag, or `main_branch` when no such tag is in
/// effect (Section 6.4's active-tag filter applies uniformly — a
/// cancelled branch tag falls back exactly like a missing one). The
/// default-branch name is a repository-local setting, so the caller
/// supplies it rather than this layer assuming a fixed string.
pub fn branchOf(self: *const RepoState, rid: Rid, main_branch: []const u8) []const u8 {
std.debug.assert(main_branch.len != 0);
std.debug.assert(self.events.contains(rid));
const result = self.activeBranchValue(rid) orelse main_branch;
std.debug.assert(result.len != 0);
return result;
}
/// Resolve a plain symbolic name (Section 8.1/8.2): the check-in
/// carrying an active "sym-<name>" tag with the greatest event.mtime.
/// Closed-ness and leaf-ness of a candidate are not inputs to this
/// selection (Section 8.2's two MUST-NOT clauses). Selection keys on
/// each candidate's own event.mtime, not the tagxref row's stored
/// mtime: a row a candidate inherited by propagation carries its
/// origin's application mtime, but the inheriting check-in can itself
/// be newer or older than that origin.
pub fn resolveName(self: *const RepoState, name: []const u8) error{NotFound}!Rid {
std.debug.assert(name.len != 0);
const sym_id = self.symTagId(name) orelse return error.NotFound;
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.key_ptr.tag != sym_id or entry.value_ptr.tagtype == .cancel) continue;
const rid = entry.key_ptr.rid;
// A tag row can sit on a phantom that has not itself been
// crosslinked yet (Section 4.2 step 1); it has no event.mtime
// and so is not a resolvable candidate.
const mtime = self.events.get(rid) orelse continue;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
const result = best orelse return error.NotFound;
std.debug.assert(self.events.contains(result));
return result;
}
/// Current-trunk (Section 9; Section 2 "Current-trunk"): resolve the
/// repository's configured default branch name. The procedure applies
/// uniformly — the default branch is not special-cased beyond supplying
/// its name.
pub fn currentTrunk(self: *const RepoState, main_branch: []const u8) error{NotFound}!Rid {
std.debug.assert(main_branch.len != 0);
return self.resolveName(main_branch);
}
/// A branch's open leaf (Section 9): among check-ins that (a) carry an
/// active branch tag whose value equals `branch`, (b) are members of
/// the leaf table, and (c) do not carry an active closed tag, the one
/// with the greatest event.mtime — or null when no check-in qualifies.
/// Condition (a) uses the active branch tag strictly: a tagless
/// check-in attributed to `branch` only through the Section 6.4
/// default-branch fallback does not qualify (Section 6.1: the fallback
/// "does not by itself make such a check-in ... the open leaf ... of
/// that branch").
pub fn openLeafOf(self: *const RepoState, branch: []const u8) ?Rid {
std.debug.assert(branch.len != 0);
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
const value = self.activeBranchValue(rid) orelse continue;
if (!std.mem.eql(u8, value, branch)) continue;
if (self.hasActiveClosed(rid)) continue;
std.debug.assert(self.events.contains(rid)); // leaf_table rids are always check-ins
const mtime = self.events.get(rid).?;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
if (best) |result| {
std.debug.assert(self.isLeaf(result) and !self.hasActiveClosed(result));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(result).?, branch));
}
return best;
}
/// A name-resolution request's target shape (Section 8.1). This layer
/// models only check-ins — Section 8.3's other reserved keywords
/// (current/prev/next/ckout) need an open local checkout, out of scope
/// for an artifact-derived layer — so `checkin` is the RFC's
/// unconstrained-or-"ci" request and `branch` is a "b*" request, routed
/// through the branch-walk post-process to the branch's first check-in.
pub const NameType = enum { checkin, branch };
/// One Section 6.3 derived branch-listing row. `name` borrows the
/// underlying tagxref value bytes and is valid only until the next
/// `RepoState` mutation frees or overwrites that row.
pub const BranchEntry = struct {
name: []const u8,
tip: Rid,
mtime: Mtime,
count: usize,
closed: bool,
};
/// One active tag row surfaced for a check-in (Section 5.1/5.2). `name`
/// is the raw interned tag name — the "branch"/"closed" reserved literals
/// (Section 2) or a user key; `value` borrows the tagxref row's stored
/// payload (null when the row carries none, Section 5.2). Valid only until
/// the next `RepoState` mutation — the same lifetime contract as
/// `BranchEntry`.
pub const TagEntry = struct {
name: []const u8,
tagtype: TagType,
value: ?[]const u8,
};
const WalkVariant = enum { earliest_on_branch, first_off_branch };
const TimestampMode = enum { upper_bound, direct };
/// Section 8.3 symbolic-name resolution: dispatch the ordered forms,
/// retry once on trailing punctuation, then — for a branch-type
/// request — post-process through the branch-walk's "earliest still on
/// branch" variant (Section 8.3's final paragraph) so the result is the
/// branch's first check-in rather than wherever the tag currently
/// points. Allocation-free.
pub fn resolve(self: *const RepoState, name: []const u8, want: NameType) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
const rid = try self.dispatchWithRetry(name);
std.debug.assert(self.events.contains(rid));
const result = if (want == .branch) self.branchWalk(rid, .earliest_on_branch) else rid;
std.debug.assert(self.events.contains(result));
return result;
}
/// Section 8.3 dispatch: the ordered forms, committing to whichever
/// prefix or shape matches first. A matched prefix that fails its own
/// validation (an unknown rid:, an empty tag:, a malformed date) is
/// rejected outright rather than falling through to a later form.
fn dispatch(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
if (std.mem.startsWith(u8, name, "rid:")) return self.ridForm(name[4..]);
if (std.mem.startsWith(u8, name, "tag:")) {
const rest = name[4..];
if (rest.len == 0) return error.NotFound;
return self.resolveName(rest);
}
if (std.mem.eql(u8, name, "tip")) return self.tipForm();
if (std.mem.startsWith(u8, name, "root:")) return self.branchDerivedForm(name[5..], .first_off_branch);
if (std.mem.startsWith(u8, name, "start:")) return self.branchDerivedForm(name[6..], .earliest_on_branch);
if (std.mem.startsWith(u8, name, "merge-in:")) return self.branchDerivedForm(name[9..], .first_off_branch);
if (std.mem.startsWith(u8, name, "date:")) return self.dateForm(name[5..], .upper_bound);
if (std.mem.startsWith(u8, name, "utc:")) return self.dateForm(name[4..], .upper_bound);
if (std.mem.startsWith(u8, name, "local:")) return self.dateForm(name[6..], .direct);
if (expandTimestamp(name, .upper_bound)) |bound_ms| {
return self.dateResolve(bound_ms) orelse error.NotFound;
}
if (isHexPrefixShape(name)) {
if (try self.hashPrefixMatch(name)) |rid| return rid;
// 0 matches: not a hash after all — fall through to the plain rule.
}
return self.resolveName(name);
}
/// Section 8.3 trailing-punctuation retry, wrapping `dispatch`: on
/// `NotFound` only (an `Ambiguous` rejection is never retried), strip
/// exactly one trailing punctuation byte and recurse. Bounded: the
/// slice strictly shrinks by one byte per retry, so the recursion depth
/// cannot exceed the initial length.
fn dispatchWithRetry(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
return self.dispatch(name) catch |err| {
if (err == error.Ambiguous) return err;
if (!isPunctChar(name[name.len - 1])) return error.NotFound;
const stripped = name[0 .. name.len - 1];
std.debug.assert(stripped.len < name.len);
if (stripped.len == 0) return error.NotFound;
return self.dispatchWithRetry(stripped);
};
}
/// Section 8.3 form 1: a numeric rid, valid only when it names a
/// crosslinked check-in.
fn ridForm(self: *const RepoState, digits: []const u8) error{NotFound}!Rid {
if (digits.len == 0) return error.NotFound;
const rid = std.fmt.parseInt(Rid, digits, 10) catch return error.NotFound;
if (!self.events.contains(rid)) return error.NotFound;
return rid;
}
/// Section 8.3 form 3 (tip only; current/prev/next/ckout need an open
/// local checkout, out of scope here): the check-in with the global
/// maximum event.mtime.
fn tipForm(self: *const RepoState) error{NotFound}!Rid {
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys(), self.events.values()) |rid, mtime| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
return best orelse error.NotFound;
}
/// Section 8.3 forms 4-6: resolve `br` through the full procedure, then
/// rewrite via the Section 8.4 branch-walk.
fn branchDerivedForm(self: *const RepoState, br: []const u8, variant: WalkVariant) error{ NotFound, Ambiguous }!Rid {
if (br.len == 0) return error.NotFound;
const base = try self.resolve(br, .checkin);
return self.branchWalk(base, variant);
}
/// Section 8.4 branch-walk: from `start`, follow the primary-parent
/// chain toward the root, tracking whether each ancestor still carries
/// the same branch identity as `start` (Section 6.1's branch-of-check-
/// in notion, default-branch fallback included — the walk needs a
/// branch value at every step, and an untagged check-in's branch is
/// still well-defined via that fallback). `.earliest_on_branch` returns
/// the deepest ancestor that still carries it; `.first_off_branch`
/// returns the first ancestor that dropped it. A primary-parent chain
/// that never leaves the branch (a root-only branch) has no such node
/// for `.first_off_branch`; both variants then fall back to the
/// deepest ancestor reached (documented edge case). A primary parent
/// that is only a phantom (not yet crosslinked, Section 4.2 step 1)
/// halts the walk there too: it is not yet a resolvable check-in, so
/// its branch identity is unresolved rather than "off branch".
fn branchWalk(self: *const RepoState, start: Rid, variant: WalkVariant) Rid {
std.debug.assert(self.events.contains(start));
const target = self.branchValueOf(start);
var cur = start;
var steps: usize = 0;
const bound = self.events.count();
while (self.primaryParentOf(cur)) |parent| {
if (!self.events.contains(parent)) 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;
}
/// Section 8.3 form 7: parse `text` to an upper-bound millisecond
/// timestamp (or pass it through directly for the deprecated `local:`
/// form) and select the most recent qualifying event.
fn dateForm(self: *const RepoState, text: []const u8, mode: TimestampMode) error{NotFound}!Rid {
const bound_ms = expandTimestamp(text, mode) orelse return error.NotFound;
return self.dateResolve(bound_ms) orelse error.NotFound;
}
/// Section 8.3 form 7 selection: the check-in with the greatest
/// event.mtime not exceeding `bound_ms`, on the millisecond timeline
/// documented on `Mtime`.
fn dateResolve(self: *const RepoState, bound_ms: u64) ?Rid {
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys(), self.events.values()) |rid, mtime| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (mtime > bound_ms) continue;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
return best;
}
/// Section 8.3 form 8: match `prefix` against crosslinked check-ins'
/// content hashes (phantoms excluded — this layer resolves names to
/// check-ins). More than one match is rejected as ambiguous (the
/// section's "-1" sentinel does not apply to an unsigned `Rid`;
/// `error.Ambiguous` is the equivalent outcome for this layer).
fn hashPrefixMatch(self: *const RepoState, prefix: []const u8) error{Ambiguous}!?Rid {
std.debug.assert(prefix.len >= 4 and prefix.len <= 64);
var match: ?Rid = null;
var count: usize = 0;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
const hash = self.store.hashOf(rid);
if (hash.len >= prefix.len and std.mem.eql(u8, hash[0..prefix.len], prefix)) {
match = rid;
count += 1;
}
}
if (count > 1) return error.Ambiguous;
return match;
}
/// Section 6.3 derived branch listing: group active branch-tag rows
/// (`tagtype > 0`) by value, one entry per distinct value with its
/// greatest-mtime member as representative. Sorted by name ascending
/// (presentation order; callers wanting Section 6.3's other listed
/// orderings re-sort). Caller frees the returned slice.
pub fn branches(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]BranchEntry {
const Group = struct { tip: Rid, mtime: Mtime, count: usize };
var groups: std.StringHashMapUnmanaged(Group) = .empty;
defer groups.deinit(gpa);
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.key_ptr.tag != branch_tag_id or entry.value_ptr.tagtype == .cancel) continue;
const rid = entry.key_ptr.rid;
const mtime = self.events.get(rid) orelse continue; // tag on a still-phantom target
const value = entry.value_ptr.value orelse continue; // a branch tag always carries a value
const gop = try groups.getOrPut(gpa, value);
if (!gop.found_existing) {
gop.value_ptr.* = .{ .tip = rid, .mtime = mtime, .count = 1 };
} else {
gop.value_ptr.count += 1;
if (mtime > gop.value_ptr.mtime) {
gop.value_ptr.tip = rid;
gop.value_ptr.mtime = mtime;
}
// Exact-mtime tie: keep the first-seen representative —
// implementation-defined per Section 8.2's own tie note.
}
}
var out: std.ArrayList(BranchEntry) = .empty;
errdefer out.deinit(gpa);
var kit = groups.iterator();
var kscanned: usize = 0;
const kbound = groups.count();
while (kit.next()) |g| {
kscanned += 1;
std.debug.assert(kscanned <= kbound);
std.debug.assert(self.events.contains(g.value_ptr.tip));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(g.value_ptr.tip).?, g.key_ptr.*));
try out.append(gpa, .{
.name = g.key_ptr.*,
.tip = g.value_ptr.tip,
.mtime = g.value_ptr.mtime,
.count = g.value_ptr.count,
.closed = self.hasActiveClosed(g.value_ptr.tip),
});
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort(BranchEntry, slice, {}, branchNameLessThan);
return slice;
}
fn branchNameLessThan(_: void, a: BranchEntry, b: BranchEntry) bool {
return std.mem.order(u8, a.name, b.name) == .lt;
}
/// Section 5.1/5.2/6.4: the active tags on `rid`, each with its stored
/// value payload, sorted by raw tag name ascending. A tag reference is
/// active iff its tagtype is greater than zero (Section 5.1/Section 2);
/// a cancel row (tagtype 0, surface `-`) is inactive by definition and is
/// excluded, so every returned entry has `tagtype != .cancel`. The
/// tagxref keying (Section 5.2's UNIQUE (rid, tag)) guarantees at most one
/// live row per (rid, tag), so each tag name appears at most once. Caller
/// frees the returned slice; the borrowed name/value bytes are valid until
/// the next `RepoState` mutation.
pub fn tagsOf(self: *const RepoState, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]TagEntry {
std.debug.assert(rid >= 1);
var out: std.ArrayList(TagEntry) = .empty;
errdefer out.deinit(gpa);
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.key_ptr.rid != rid) continue;
if (entry.value_ptr.tagtype == .cancel) continue; // Section 5.1: inactive
try out.append(gpa, .{
.name = self.tagNameOf(entry.key_ptr.tag),
.tagtype = entry.value_ptr.tagtype,
.value = entry.value_ptr.value,
});
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort(TagEntry, slice, {}, tagNameLessThan);
// Section 5.1 postcondition: every surfaced row is active (positive +
// negative space), and the listing is name-ascending with distinct
// names (the (rid, tag) UNIQUE constraint, Section 5.2).
for (slice, 0..) |e, i| {
std.debug.assert(e.tagtype != .cancel);
if (i + 1 < slice.len) std.debug.assert(std.mem.order(u8, e.name, slice[i + 1].name) == .lt);
}
return slice;
}
/// Section 5.1/6.4 (+ Section 4.2 step 1 phantom exclusion): the distinct
/// active tag names in use anywhere. A name appears iff some crosslinked
/// check-in holds an active (tagtype > 0) row for it; a row sitting on a
/// not-yet-arrived phantom target (Section 4.2 step 1) does not count —
/// it becomes visible once the referenced artifact is crosslinked. Names
/// are raw: the "branch"/"closed" reserved literals and reserved-prefix
/// names (Section 2) are included, and the caller decides which are
/// user-facing. Sorted ascending. Names borrow interned bytes; caller
/// frees the returned slice.
pub fn tagNames(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![][]const u8 {
var ids: std.AutoHashMapUnmanaged(TagId, void) = .empty;
defer ids.deinit(gpa);
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.value_ptr.tagtype == .cancel) continue; // Section 5.1: inactive
if (!self.events.contains(entry.key_ptr.rid)) continue; // Section 4.2 step 1: phantom
try ids.put(gpa, entry.key_ptr.tag, {});
}
var out: std.ArrayList([]const u8) = .empty;
errdefer out.deinit(gpa);
var kit = ids.keyIterator();
var kscanned: usize = 0;
const kbound = ids.count();
while (kit.next()) |id| {
kscanned += 1;
std.debug.assert(kscanned <= kbound);
try out.append(gpa, self.tagNameOf(id.*));
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort([]const u8, slice, {}, nameLessThan);
// Distinct by construction (deduped by tag id); the sort makes the
// distinctness invariant adjacency-checkable.
for (slice, 0..) |name, i| {
if (i + 1 < slice.len) std.debug.assert(!std.mem.eql(u8, name, slice[i + 1]));
}
return slice;
}
fn tagNameLessThan(_: void, a: TagEntry, b: TagEntry) bool {
return std.mem.order(u8, a.name, b.name) == .lt;
}
fn nameLessThan(_: void, a: []const u8, b: []const u8) bool {
return std.mem.order(u8, a, b) == .lt;
}
/// Section 7.5 ambiguity test: `rid` is a leaf and at least one *other*
/// open leaf shares its branch (the canonical leaf test's own default-
/// branch-inclusive same-branch comparison). Non-leaf short-circuits to
/// false per the section's first MUST.
pub fn isAmbiguousLeaf(self: *const RepoState, rid: Rid) bool {
if (!self.isLeaf(rid)) return false;
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |other| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (other == rid) continue;
if (!self.isOpenLeaf(other)) continue;
if (self.sameBranch(rid, other)) return true;
}
return false;
}
const MtimeDescCtx = struct {
rs: *const RepoState,
fn lessThan(ctx: MtimeDescCtx, a: Rid, b: Rid) bool {
return ctx.rs.mtimeOf(a).? > ctx.rs.mtimeOf(b).?;
}
};
/// Section 7.5 SHOULD reporting: every open leaf of `branch` (the
/// strict active-tag membership `openLeafOf` also uses — a tagless
/// check-in attributed to `branch` only through the default-branch
/// fallback does not qualify), ordered by event.mtime descending.
/// Exact-mtime ties are implementation-defined, per Section 8's own
/// tie note. Caller frees the returned slice.
pub fn openLeavesOf(self: *const RepoState, gpa: std.mem.Allocator, branch: []const u8) error{OutOfMemory}![]Rid {
std.debug.assert(branch.len != 0);
var out: std.ArrayList(Rid) = .empty;
errdefer out.deinit(gpa);
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (self.hasActiveClosed(rid)) continue;
const value = self.activeBranchValue(rid) orelse continue;
if (!std.mem.eql(u8, value, branch)) continue;
try out.append(gpa, rid);
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort(Rid, slice, MtimeDescCtx{ .rs = self }, MtimeDescCtx.lessThan);
for (slice) |rid| {
std.debug.assert(self.isOpenLeaf(rid));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(rid).?, branch));
}
return slice;
}
/// 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 {
if (self.children.getPtr(rid)) |list| {
for (list.items) |e| {
if (self.sameBranch(rid, e.rid)) 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 active branch-tag value for `rid` (Section 6.1), or null when no
/// active (tagtype > 0) row is present. No default here: the caller
/// decides what absence means — `branchOf`'s Section 6.4 fallback to
/// the configured main branch, versus `openLeafOf`'s strict
/// non-membership (a tagless check-in is never that branch's open leaf).
fn activeBranchValue(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 null;
}
/// The branch value of `rid` used by the same-branch leaf test
/// (Section 6.1, Section 6.4 fallback): `activeBranchValue`, or the
/// literal default branch when absent. Leaf derivation is internal
/// bookkeeping, not parameterized by the configurable main-branch
/// setting the way `branchOf` is.
fn branchValueOf(self: *const RepoState, rid: Rid) []const u8 {
return self.activeBranchValue(rid) orelse 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;
}
/// The interned id of "sym-<name>", or null when that name has never
/// been tagged (Section 2: symbolic names are stored internally with a
/// "sym-" prefix). A scan rather than a concatenated-key lookup: tag
/// names are owned, arbitrary-length strings with no RFC-mandated
/// bound, so building "sym-" ++ name would allocate for a read-only
/// query that has no other reason to.
fn symTagId(self: *const RepoState, name: []const u8) ?TagId {
const prefix = "sym-";
var it = self.tag_names.iterator();
var scanned: usize = 0;
const bound = self.tag_names.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
const key = entry.key_ptr.*;
if (key.len != prefix.len + name.len) continue;
if (!std.mem.eql(u8, key[0..prefix.len], prefix)) continue;
if (std.mem.eql(u8, key[prefix.len..], name)) return entry.value_ptr.*;
}
return null;
}
/// The interned name of tag `id` (Section 2): the fixed "branch"/"closed"
/// literals for the reserved ids 8/9, else the `tag_names` key that maps
/// to `id`, found by a reverse scan bounded by the interned-name count.
/// `id` is only ever passed from a live tagxref row, so a user id always
/// has an interned name and the scan always resolves.
fn tagNameOf(self: *const RepoState, id: TagId) []const u8 {
if (id == branch_tag_id) return "branch";
if (id == closed_tag_id) return "closed";
var it = self.tag_names.iterator();
var scanned: usize = 0;
const bound = self.tag_names.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.value_ptr.* == id) return entry.key_ptr.*;
}
unreachable; // id came from a live row, so its name is interned
}
/// 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 });
// The map now owns the value; disarm the errdefer so a later failure
// (addRidTag, scheduleLeafRecheck) cannot double-free what deinit will.
new_value = null;
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
} else {
// First row for this (rid, tag): mirror it into the tag index.
try self.addRidTag(target, tag);
}
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);
// The child set of `a` is fixed for the whole walk: linkage rows are
// built during crosslink's linkage phase, before any tag op runs, so
// `children` is never mutated here and this pointer stays valid.
if (self.children.getPtr(a)) |list| {
for (list.items) |e| {
if (!e.is_primary) continue; // never a merge edge
const child = e.rid;
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 });
// The map now owns the value; disarm the errdefer so a failing
// addRidTag below cannot double-free what deinit will free.
new_value = null;
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
} else {
// First row for this (rid, tag): mirror it into the index.
try self.addRidTag(child, tag);
}
},
.cancel => {
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
_ = self.tagxref.remove(key);
self.removeRidTag(child, tag);
}
},
.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);
if (self.rid_tags.getPtr(parent)) |tags| {
for (tags.items) |tag| {
// rid_tags is precise: every listed tag has a live tagxref row.
const xr = self.tagxref.get(.{ .rid = parent, .tag = tag }).?;
try rows.append(self.gpa, .{ .tag = tag, .xr = xr });
}
}
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, {});
// Snapshot the parent count first: `pending_leaf.put` never mutates
// `parents_by_child`, so the edge slice stays valid across the loop.
if (self.parents_by_child.getPtr(rid)) |list| {
for (list.items) |e| try self.pending_leaf.put(self.gpa, e.rid, {});
}
}
};
/// Days since 1970-01-01 for a proleptic-Gregorian civil date (Howard
/// Hinnant's public-domain `days_from_civil` calendar identity — plain
/// integer math, not derived from any Fossil/libfossil source). Backs the
/// Section 8.3 form 7 date-form parser below, placing a parsed timestamp
/// and stored event.mtime values on one millisecond timeline. Inputs must
/// already be range-validated (see `parseDateTime`).
fn daysFromCivil(y_in: i64, m: u8, d: u8) i64 {
std.debug.assert(m >= 1 and m <= 12);
std.debug.assert(d >= 1 and d <= 31);
var y = y_in;
if (m <= 2) y -= 1;
const era: i64 = @divFloor(if (y >= 0) y else y - 399, 400);
const yoe: i64 = y - era * 400;
const mp: i64 = @mod(@as(i64, m) + 9, 12);
const doy: i64 = @divFloor(153 * mp + 2, 5) + @as(i64, d) - 1;
const doe: i64 = yoe * 365 + @divFloor(yoe, 4) - @divFloor(yoe, 100) + doy;
return era * 146_097 + doe - 719_468;
}
fn isLeapYear(y: i64) bool {
return @mod(y, 4) == 0 and (@mod(y, 100) != 0 or @mod(y, 400) == 0);
}
fn daysInMonth(y: i64, m: u8) u8 {
return switch (m) {
1, 3, 5, 7, 8, 10, 12 => 31,
4, 6, 9, 11 => 30,
2 => if (isLeapYear(y)) @as(u8, 29) else 28,
else => unreachable, // m range-checked by parseDateTime before this call
};
}
const DatePrecision = enum { date_only, minute, second, fraction };
const DateParts = struct {
y: u16,
mo: u8,
d: u8,
h: u8,
mi: u8,
s: u8,
/// 1-3 ASCII digits, empty below `.fraction` precision.
frac: []const u8,
precision: DatePrecision,
};
/// Fixed-field parse of a Section 8.3 form 7 timestamp:
/// `YYYY-MM-DD[ HH:MM[:SS[.f{1,3}]]]`. Never panics on malformed input
/// (fuzz-safe): every field is range-checked and a bad byte returns null
/// rather than trapping.
fn parseDateTime(text: []const u8) ?DateParts {
if (text.len < 10) return null;
const y = std.fmt.parseInt(u16, text[0..4], 10) catch return null;
if (text[4] != '-') return null;
const mo = std.fmt.parseInt(u8, text[5..7], 10) catch return null;
if (mo < 1 or mo > 12) return null;
if (text[7] != '-') return null;
const d = std.fmt.parseInt(u8, text[8..10], 10) catch return null;
if (d < 1 or d > daysInMonth(y, mo)) return null;
if (text.len == 10) return .{ .y = y, .mo = mo, .d = d, .h = 0, .mi = 0, .s = 0, .frac = &.{}, .precision = .date_only };
if (text.len < 16 or text[10] != ' ') return null;
const h = std.fmt.parseInt(u8, text[11..13], 10) catch return null;
if (h > 23) return null;
if (text[13] != ':') return null;
const mi = std.fmt.parseInt(u8, text[14..16], 10) catch return null;
if (mi > 59) return null;
if (text.len == 16) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = 0, .frac = &.{}, .precision = .minute };
if (text.len < 19 or text[16] != ':') return null;
const s = std.fmt.parseInt(u8, text[17..19], 10) catch return null;
if (s > 59) return null;
if (text.len == 19) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = &.{}, .precision = .second };
if (text.len < 21 or text.len > 23 or text[19] != '.') return null;
const frac = text[20..];
for (frac) |c| if (!std.ascii.isDigit(c)) return null;
return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = frac, .precision = .fraction };
}
/// Converts a fixed 3-ASCII-digit buffer to its numeric value (0-999).
/// Every byte must be a decimal digit: `expandTimestamp` fills `buf` only
/// from `'0'`/`'9'` padding or from `DateParts.frac`, whose bytes
/// `parseDateTime` already range-checked with `std.ascii.isDigit`.
fn digits3ToMs(buf: [3]u8) u16 {
for (buf) |c| std.debug.assert(std.ascii.isDigit(c));
return @as(u16, buf[0] - '0') * 100 + @as(u16, buf[1] - '0') * 10 + (buf[2] - '0');
}
/// Section 8.3 form 7 upper-bound / direct expansion, returning a Unix-
/// epoch millisecond bound (or null on a malformed timestamp).
/// `.upper_bound` pads an under-specified field to its latest instant per
/// the precision table (date-only -> 23:59:59.999, minute -> :59.999,
/// second -> .999; a fractional field is copied, padded to three digits
/// with trailing 9s, and advanced by one millisecond unless already .999 —
/// .1 -> .199 -> .200, .12 -> .129 -> .130, .123 -> .124, .999 stays).
/// `.direct` (the deprecated local: form) parses the literal fields with
/// no expansion — an absent field is zero and a given fraction is read at
/// face value, matching a bare julianday() parse.
fn expandTimestamp(text: []const u8, mode: RepoState.TimestampMode) ?u64 {
const parts = parseDateTime(text) orelse return null;
var h = parts.h;
var mi = parts.mi;
var s = parts.s;
var ms: u16 = 0;
switch (mode) {
.upper_bound => switch (parts.precision) {
.date_only => {
h = 23;
mi = 59;
s = 59;
ms = 999;
},
.minute => {
s = 59;
ms = 999;
},
.second => ms = 999,
.fraction => {
var buf = [3]u8{ '9', '9', '9' };
for (parts.frac, 0..) |c, i| buf[i] = c;
ms = digits3ToMs(buf);
if (ms != 999) ms += 1;
},
},
.direct => switch (parts.precision) {
.date_only, .minute, .second => {},
.fraction => {
var buf = [3]u8{ '0', '0', '0' };
for (parts.frac, 0..) |c, i| buf[i] = c;
ms = digits3ToMs(buf);
},
},
}
const days = daysFromCivil(@as(i64, parts.y), parts.mo, parts.d);
const total_ms: i64 = days * 86_400_000 +
@as(i64, h) * 3_600_000 +
@as(i64, mi) * 60_000 +
@as(i64, s) * 1_000 +
@as(i64, ms);
if (total_ms < 0) return null; // pre-epoch: outside this layer's ms timeline
return @intCast(total_ms);
}
/// Parse a direct timestamp into the repository's millisecond timeline.
/// Canonical artifact D-card datetimes use `T` as their date/time separator;
/// normalize that byte only, then reuse the Section 8.3 direct conversion.
pub fn parseMtime(timestamp: []const u8) ?Mtime {
if (timestamp.len > 10 and timestamp[10] == 'T') {
// D-cards require a full seconds field, with an optional 1-3 digit
// fractional component. The direct parser validates every other byte.
if (timestamp.len < 19 or timestamp.len > 23) return null;
var normalized: [23]u8 = undefined;
std.mem.copyForwards(u8, normalized[0..timestamp.len], timestamp);
normalized[10] = ' ';
return expandTimestamp(normalized[0..timestamp.len], .direct);
}
return expandTimestamp(timestamp, .direct);
}
/// Section 8.3 form 8 shape test: a hex string long enough to be an
/// unambiguous prefix (4 chars) and no longer than the maximum artifact-
/// hash length (64, the sha3-256 case).
fn isHexPrefixShape(name: []const u8) bool {
if (name.len < 4 or name.len > 64) return false;
for (name) |c| if (!std.ascii.isHex(c)) return false;
return true;
}
fn isPunctChar(c: u8) bool {
return std.ascii.isPunctuation(c);
}
/// 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;
}
/// 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.?);
}
// ---------------------------------------------------------------------------
// §8 name resolution, §6.3 branch enumeration, §7.5 ambiguous-leaf reporting.
// ---------------------------------------------------------------------------
test "repostate §8.3: date upper-bound expansion of fractional seconds" {
const cases = [_]struct { in: []const u8, want: []const u8 }{
.{ .in = "2026-07-10 08:30:15.1", .want = "2026-07-10 08:30:15.200" },
.{ .in = "2026-07-10 08:30:15.12", .want = "2026-07-10 08:30:15.130" },
.{ .in = "2026-07-10 08:30:15.123", .want = "2026-07-10 08:30:15.124" },
.{ .in = "2026-07-10 08:30:15.999", .want = "2026-07-10 08:30:15.999" },
};
for (cases) |c| {
const got = expandTimestamp(c.in, .upper_bound).?;
// The literal target, parsed with no expansion, is the independent
// check on the padding rule's output.
const want = expandTimestamp(c.want, .direct).?;
try t.expectEqual(want, got);
}
}
test "repostate §8.3: date upper-bound expansion by precision" {
try t.expectEqual(expandTimestamp("2026-07-10 23:59:59.999", .direct).?, expandTimestamp("2026-07-10", .upper_bound).?);
try t.expectEqual(expandTimestamp("2026-07-10 08:30:59.999", .direct).?, expandTimestamp("2026-07-10 08:30", .upper_bound).?);
try t.expectEqual(expandTimestamp("2026-07-10 08:30:15.999", .direct).?, expandTimestamp("2026-07-10 08:30:15", .upper_bound).?);
}
test "repostate §8.3: date: selects the most recent event at or before the bound" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const day9 = expandTimestamp("2026-07-09 12:00:00.000", .direct).?;
const day10 = expandTimestamp("2026-07-10 00:00:00.500", .direct).?;
const r9 = try rs.crosslink(.{ .hash = h_a, .mtime = day9 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = day10, .parents = &.{h_a} });
try t.expectEqual(r9, try rs.resolve("date:2026-07-09", .checkin));
}
test "repostate §8.3: local: uses julianday directly without upper-bound expansion" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const midnight = expandTimestamp("2026-07-10 00:00:00.000", .direct).?;
const noon = expandTimestamp("2026-07-10 12:00:00.000", .direct).?;
const r_mid = try rs.crosslink(.{ .hash = h_a, .mtime = midnight });
const r_noon = try rs.crosslink(.{ .hash = h_b, .mtime = noon, .parents = &.{h_a} });
// date: bounds at end-of-day, so the noon event still qualifies; local:
// passes midnight through directly, excluding noon.
try t.expectEqual(r_noon, try rs.resolve("date:2026-07-10", .checkin));
try t.expectEqual(r_mid, try rs.resolve("local:2026-07-10", .checkin));
}
/// True when `edges` holds exactly one entry naming `rid` with `is_primary`.
fn edgeMatches(edges: []const RepoState.Edge, rid: Rid, is_primary: bool) bool {
var hits: usize = 0;
for (edges) |e| {
if (e.rid == rid and e.is_primary == is_primary) hits += 1;
}
return hits == 1;
}
fn edgeSlice(map: *const std.AutoArrayHashMapUnmanaged(Rid, std.ArrayListUnmanaged(RepoState.Edge)), key: Rid) []const RepoState.Edge {
if (map.getPtr(key)) |list| return list.items;
return &.{};
}
// §3.1 parent links, §4 crosslink, §5 tags, §7 leaf-set: the adjacency indexes
// (children / parents_by_child / rid_tags) are pure acceleration of the exact
// same derivation the full linear scans compute. This proves the equivalence
// directly — for random op sequences the indexed answers are byte-for-byte the
// linear-scan answers, and the incrementally maintained leaf table equals a
// from-scratch brute-force recomputation over the raw plinks/tagxref tables.
test "repostate: optimized crosslink == from-scratch derivation for random op sequences" {
const branches = [_][]const u8{ "trunk", "feature", "topic" };
const cust = "cust";
var seed: u64 = 0;
while (seed < 64) : (seed += 1) {
var prng = std.Random.DefaultPrng.init(seed);
const rand = prng.random();
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const n = rand.intRangeAtMost(usize, 1, 24);
var hashes: [24][64]u8 = undefined;
for (0..n) |i| {
@memset(&hashes[i], 'a');
_ = std.fmt.bufPrint(hashes[i][0..16], "{x:0>16}", .{i}) catch unreachable;
}
for (0..n) |i| {
var parent_buf: [3][]const u8 = undefined;
var pn: usize = 0;
const want_parents = if (i == 0) 0 else rand.intRangeAtMost(usize, 0, @min(@as(usize, 3), i));
// Distinct prior indices as parents; parents[0] is the primary.
var picked: [24]bool = [_]bool{false} ** 24;
while (pn < want_parents) {
const j = rand.intRangeLessThan(usize, 0, i);
if (picked[j]) continue;
picked[j] = true;
parent_buf[pn] = &hashes[j];
pn += 1;
}
var tag_buf: [3]TagOp = undefined;
var tn: usize = 0;
if (pn == 0) {
// A root seeds a propagating branch tag (§6.1).
tag_buf[tn] = .{ .type = .propagate, .name = "branch", .target = null, .value = branches[rand.intRangeLessThan(usize, 0, branches.len)] };
tn += 1;
}
if (rand.boolean()) {
const sign: TagType = if (rand.boolean()) .propagate else if (rand.boolean()) .singleton else .cancel;
const target: ?[]const u8 = if (rand.boolean() or i == 0) null else &hashes[rand.intRangeLessThan(usize, 0, i)];
tag_buf[tn] = .{ .type = sign, .name = cust, .target = target, .value = if (sign == .cancel) null else "v" };
tn += 1;
}
if (rand.boolean()) {
const sign: TagType = if (rand.boolean()) .singleton else .cancel;
tag_buf[tn] = .{ .type = sign, .name = "closed", .target = null, .value = null };
tn += 1;
}
_ = try rs.crosslink(.{ .hash = &hashes[i], .mtime = @intCast(i + 1), .parents = parent_buf[0..pn], .tags = tag_buf[0..tn] });
}
// (1) plinks <-> adjacency indexes are a faithful mirror.
var child_edges: usize = 0;
for (rs.children.values()) |list| child_edges += list.items.len;
var parent_edges: usize = 0;
for (rs.parents_by_child.values()) |list| parent_edges += list.items.len;
try t.expectEqual(rs.plinks.count(), child_edges);
try t.expectEqual(rs.plinks.count(), parent_edges);
for (rs.plinks.keys(), rs.plinks.values()) |key, row| {
try t.expect(edgeMatches(edgeSlice(&rs.children, key.parent), key.child, row.is_primary));
try t.expect(edgeMatches(edgeSlice(&rs.parents_by_child, key.child), key.parent, row.is_primary));
}
// (2) tagxref <-> rid_tags is exactly precise.
var listed_tags: usize = 0;
for (rs.rid_tags.values()) |list| listed_tags += list.items.len;
try t.expectEqual(rs.tagxref.count(), listed_tags);
var xit = rs.tagxref.iterator();
while (xit.next()) |entry| {
const rid = entry.key_ptr.rid;
const tag = entry.key_ptr.tag;
var found = false;
if (rs.rid_tags.getPtr(rid)) |list| {
for (list.items) |lt| {
if (lt == tag) found = true;
}
}
try t.expect(found);
}
// (3) indexed accessors == brute-force linear scans, per rid.
for (rs.events.keys()) |rid| {
var brute_parents: usize = 0;
var brute_primary: ?Rid = null;
for (rs.plinks.keys(), rs.plinks.values()) |key, row| {
if (key.child != rid) continue;
brute_parents += 1;
if (row.is_primary) brute_primary = key.parent;
}
try t.expectEqual(brute_parents, rs.parentCount(rid));
try t.expectEqual(brute_primary, rs.primaryParentOf(rid));
var brute_same_branch = false;
for (rs.plinks.keys()) |key| {
if (key.parent == rid and rs.sameBranch(rid, key.child)) brute_same_branch = true;
}
// (4) leaf table == from-scratch brute-force over the raw tables.
const brute_leaf = !brute_same_branch;
try t.expectEqual(brute_leaf, rs.leaf_table.contains(rid));
}
}
}