//! 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");
/// 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");
/// The §4.1 zlib container codec — a leaf below repostate, so the direct file
/// import is layer-legal. `MemStore` stores wire-backed entries verbatim and
/// inflates them through this single shared codec.
const codec = @import("container.zig");
/// The artifact layer — one step below repostate in the RFC layering
/// (delta -> artifact -> repostate), so a direct file import is layer-legal and
/// introduces no cycle (`artifact.zig` imports nothing but `std`). Used by the
/// draft-fossil-submanifests-00 §7/§9 support below for the artifact-type
/// enumeration (§9.2) and the §5 tree-walk seam types the §7.4 memo decorates.
const artifact = @import("artifact.zig");
/// The materialized read-image (`repoimage.zig`): the hot query answers of a
/// derived `RepoState`, laid out as dense integer-addressed columns. When a
/// warm read loads one, `RepoState` runs in `.image` backing and its freed
/// query methods read the columns instead of re-deriving the hashmaps. The
/// representation stays hidden there; this module only holds the loaded view.
const repoimage = @import("repoimage.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 = &.{},
/// The check-in's C-card comment, verbatim ("" for none). Carried so the
/// mtime-ordered listings render without re-reading and re-parsing every
/// manifest — the cost that dominated an unlimited `zit timeline` on a
/// large store. Display overrides (`zit amend`) still outrank it at
/// render time through the tagxref, exactly as before.
comment: []const u8 = "",
};
/// 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,
/// True when `rid` has BYTES TO SERVE VERBATIM — see the `held` method's
/// doc for the full contract. A vtable entry rather than a derivation
/// because the predicate must be answerable WITHOUT I/O: the responder
/// calls it for every rid on every round, and a log-backed store deriving
/// it from `wire()`/`content()` would re-read the whole log each round. A
/// RAM-backed store answers from a field read; a log-backed store answers
/// from its index. Both do so without materialising anything.
held: *const fn (context: *anyopaque, rid: Rid) bool,
};
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);
}
/// True when `rid` has BYTES TO SERVE VERBATIM — a retained §4.1 container
/// (`wire()`) or already-materialised plaintext (`content()`) — as opposed
/// to a bare phantom (Sync §3.3 r24). The held-vs-phantom predicate the
/// request composer and persist pass need WITHOUT forcing a `content()`
/// inflate: a wire-backed entry answers from its container's presence alone,
/// so a clone that stores every artifact wire-backed never materialises (and
/// memoises) plaintext just to classify it.
///
/// NOT equal to `content(rid) != null`: a wire-backed container may be held
/// yet NOT reconstructable — a §7.2/§7.7 full container retained verbatim
/// whose stored bytes fail to inflate is `held()==true` with
/// `content()==null`. `held()` means "I can retransmit its wire form"; it does
/// NOT promise materialisable plaintext. A caller that needs plaintext (e.g.
/// the §3.2 upload composer, which builds a file card from `content()`) MUST
/// gate on `content()`, never infer materialisability from `held()`.
///
/// Dispatched through the vtable rather than derived from `wire()`/`content()`
/// so a store answers it WITHOUT materialising a frame: the semantics are
/// still "a rid is held when it has a wire form or plaintext", but a log-backed
/// store proves that from its resident index instead of a disk read, while a
/// RAM-backed store returns exactly what the old derivation did.
pub fn held(self: ArtifactStore, rid: Rid) bool {
return self.vtable.held(self.context, rid);
}
/// How many of the store's rids are `held()` — the Sync §3.3 r24 held-set
/// size, and the aggregate the serve and persist passes classify by. Derived
/// from `held()` over the dense `1..=count` rid range exactly as `held()` is
/// derived from the vtable, so no store implements it specially and no caller
/// re-implements the loop with a worse predicate.
///
/// This is a count of SERVABLE artifacts, NOT of materialisable ones: an
/// entry whose retained container fails to inflate is counted here (it is
/// still retransmitted verbatim and still persisted), and nothing is
/// inflated to produce the answer. A caller that needs the number of
/// artifacts whose PLAINTEXT it can read must gate on `content()` itself and
/// pay for it knowingly.
pub fn heldCount(self: ArtifactStore) usize {
var n: usize = 0;
const total = self.count();
var rid: Rid = 1;
while (rid <= total) : (rid += 1) {
if (self.held(rid)) n += 1;
}
return n;
}
};
/// 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,
/// Total plaintext this store has ever INFLATED from a retained container,
/// in bytes, monotonic across `releasePlaintext`. Not used by the store; it
/// is the work counter that makes "answering a round does not inflate the
/// store" a testable property rather than a wall-clock claim. `bytes` held
/// by a raw `put` never lands here — only work `content()` performed.
inflated_bytes: usize = 0,
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,
.held = heldImpl,
};
/// A MemStore entry is held when it carries a wire container OR materialised
/// plaintext — the RAM twin of the old `wire() != null or content() != null`
/// derivation, but reading the two fields directly so it never inflates a
/// container to answer (the whole reason `held` is a vtable slot).
fn heldImpl(context: *anyopaque, rid: Rid) bool {
const self: *MemStore = @ptrCast(@alignCast(context));
const entry = self.entryOf(rid);
return entry.wire != null or entry.bytes != null;
}
/// 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 = codec.decode(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
self.inflated_bytes += plain.len;
return plain;
}
const plain = codec.decode(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
self.inflated_bytes += plain.len;
return plain;
}
/// Drop every memoised plaintext that can be re-derived from a retained
/// container, restoring the store to the "containers, not inflated history"
/// shape `loadContentStore` builds. An entry with no `wire` keeps its bytes:
/// they are the only copy.
///
/// The memo is a per-read accelerator, not state: `content()` re-inflates on
/// demand and answers identically, so this is observable only as memory. It
/// exists because a store that OUTLIVES the read that inflated into it would
/// otherwise retain the whole repository's plaintext for the process's life
/// — a caller that keeps a long-lived store calls this when its readers are
/// done, and every borrowed `content()` slice is invalidated by the call.
pub fn releasePlaintext(self: *MemStore) void {
for (self.entries.items) |*entry| {
if (entry.wire == null) continue;
if (entry.bytes) |b| {
self.gpa.free(b);
entry.bytes = null;
}
}
}
/// Total memoised plaintext currently held across all entries, in bytes — a
/// test/accounting probe. Zero when every entry is wire-backed or phantom
/// (the clone-receive invariant: containers, not inflated history). Rises
/// only as `content()` materialises plaintext or a raw `put` stores it.
pub fn plaintextBytesHeld(self: *const MemStore) usize {
var total: usize = 0;
for (self.entries.items) |entry| {
if (entry.bytes) |b| total += b.len;
}
return total;
}
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)];
}
};
/// A per-request WRITE OVERLAY over a base store that must not be mutated.
///
/// A stateless sync responder freely writes into the store it answers over: it
/// interns a phantom for every hash a peer announces, upgrades a phantom with
/// pushed content, retains wire forms, and memoises plaintext. That is correct
/// when the store is a throwaway snapshot, and silently wrong when one snapshot
/// is reused across rounds — the phantoms and upgrades one round writes change
/// what the next round decides to send. An overlay restores the throwaway
/// property without the throwaway cost: every write lands here, every read falls
/// through to the base, and dropping the overlay restores the base exactly.
///
/// Rid space: the base's rids `1..=base_count` keep their identity, and rids
/// above `base_count` are this overlay's own additions, so the dense
/// `1..=count()` walk every peer performs still enumerates the union. A hash the
/// base already knows NEVER gets a second rid — `intern`/`put` return the base's
/// rid and, when the base holds it only as a phantom, the supplied bytes are
/// recorded against that same rid in `upgraded`.
///
/// What still crosses into the base: `content()` on a wire-backed base entry
/// inflates and memoises plaintext there. That is content-addressed and
/// therefore idempotent — the base answers the same bytes with or without it —
/// so it is isolation-neutral. It is NOT memory-neutral: the memo outlives the
/// overlay, so a caller holding a base across many overlays must call
/// `MemStore.releasePlaintext` once the overlay is gone, or the base accumulates
/// the plaintext of everything every request ever read.
///
/// Retained DELTA forms are resolved by the sub-store that holds them, so a
/// delta whose basis lives only in the base cannot be reconstructed here. See
/// `retainImpl`.
pub const OverlayStore = struct {
gpa: std.mem.Allocator,
base: ArtifactStore,
/// The base's rid count, fixed at construction: the base is immutable for
/// this overlay's lifetime, so the split point never moves.
base_count: usize,
/// Entries for hashes the base does not know at all. Local rid `l` here is
/// the global rid `base_count + l`.
added: MemStore,
/// Bytes supplied this request for a rid the base holds as a PHANTOM. The
/// global rid stays the base's; `shadow_of` maps it to the local rid here.
upgraded: MemStore,
shadow_of: std.AutoHashMapUnmanaged(Rid, Rid) = .empty,
pub fn init(gpa: std.mem.Allocator, base: ArtifactStore) OverlayStore {
return .{
.gpa = gpa,
.base = base,
.base_count = base.count(),
.added = MemStore.init(gpa),
.upgraded = MemStore.init(gpa),
};
}
pub fn deinit(self: *OverlayStore) void {
self.shadow_of.deinit(self.gpa);
self.added.deinit();
self.upgraded.deinit();
self.* = undefined;
}
/// The type-erased store interface over this instance.
pub fn store(self: *OverlayStore) ArtifactStore {
return .{ .context = self, .vtable = &vtable };
}
/// How many artifacts THIS REQUEST made servable that the base did not
/// already serve — new hashes plus upgraded base phantoms. Zero for a pure
/// read round, which is what tells the serve layer that nothing needs to be
/// made durable. Counted over the overlay alone, so it costs nothing in the
/// size of the base.
pub fn writtenCount(self: *OverlayStore) usize {
return self.added.store().heldCount() + self.upgraded.store().heldCount();
}
const vtable = ArtifactStore.VTable{
.intern = internImpl,
.put = putImpl,
.content = contentImpl,
.hashOf = hashOfImpl,
.lookup = lookupImpl,
.count = countImpl,
.wire = wireImpl,
.retain = retainImpl,
.held = heldImpl,
};
/// Route held-ness exactly as `wireImpl`/`contentImpl` route their reads: an
/// added rid is answered by `added`, a shadowed base rid is held when the
/// overlay's upgrade holds it OR the base already did, and a plain base rid
/// defers to the base. Equivalent to the old `wire()!=null or content()!=null`
/// derivation, but each sub-store answers from its own index without I/O.
fn heldImpl(context: *anyopaque, rid: Rid) bool {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (rid > self.base_count) return self.added.store().held(rid - self.base_count);
if (self.shadow_of.get(rid)) |l| {
if (self.upgraded.store().held(l)) return true;
}
return self.base.held(rid);
}
/// The overlay-local rid in `upgraded` shadowing base `rid`, creating it (as
/// a phantom carrying the base's hash) when this is the first write against
/// that rid.
fn shadowFor(self: *OverlayStore, rid: Rid) error{OutOfMemory}!Rid {
if (self.shadow_of.get(rid)) |l| return l;
try self.shadow_of.ensureUnusedCapacity(self.gpa, 1);
const l = try self.upgraded.store().intern(self.base.hashOf(rid));
self.shadow_of.putAssumeCapacity(rid, l);
return l;
}
fn internImpl(context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (self.base.lookup(hash)) |rid| return rid;
return self.base_count + try self.added.store().intern(hash);
}
fn putImpl(context: *anyopaque, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (self.base.lookup(hash)) |rid| {
// Content is addressed by hash: a base entry whose plaintext is
// already readable carries these very bytes, so this put is a no-op
// — and a differing answer is a hash collision, asserted exactly as
// `MemStore.putImpl` asserts it.
//
// The gate is `content()`, NOT `held()`: an entry held via a
// retained container that does not inflate is servable but has no
// readable plaintext, and returning early on it would discard the
// pushed bytes and leave `content(rid) == null` after a `put` —
// breaking the postcondition every other store honours. Paying an
// inflate here is a cold path: a peer only re-pushes what the
// negotiation already told it the server holds.
if (self.base.content(rid)) |existing| {
std.debug.assert(std.mem.eql(u8, existing, content_bytes));
return rid;
}
const l = try self.shadowFor(rid);
_ = try self.upgraded.store().put(hash, content_bytes);
std.debug.assert(self.upgraded.store().content(l) != null);
return rid;
}
// NOTE for the receive side: a base that withholds a name BY POLICY (the
// sync send-side shun mask answers `lookup` null for it) reaches this arm,
// so a pushed copy of such a name lands in `added` as a genuinely held
// overlay rid for the rest of the round — and that round's inventory walk
// then announces it. Deciding whether a pushed artifact may be admitted at
// all is the caller's (sync §7.7), not this store's: an overlay cannot see
// why a base said "absent". Recorded here because this is the line where
// the consequence appears.
return self.base_count + try self.added.store().put(hash, content_bytes);
}
/// Retention is advisory (see the vtable contract): a base entry that already
/// serves a form keeps it, first form wins.
///
/// RESTRICTION — a retained `.delta` form must name a basis that lives in the
/// SAME sub-store: `MemStore` resolves a delta's basis through its own hash
/// map, so a delta retained here against a basis that exists only in the base
/// would be `held()` forever and `content()` never. The sync responder only
/// ever `intern`s and `put`s into the store it answers over, so this does not
/// arise; it is asserted rather than left latent for a future caller.
fn retainImpl(context: *anyopaque, rid: Rid, ingest: WireIngest) error{OutOfMemory}!void {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (rid > self.base_count) {
if (ingest == .delta) std.debug.assert(self.added.store().lookup(ingest.delta.src) != null);
return self.added.store().retain(rid - self.base_count, ingest);
}
if (self.base.held(rid)) return;
const l = try self.shadowFor(rid);
if (ingest == .delta) std.debug.assert(self.upgraded.store().lookup(ingest.delta.src) != null);
return self.upgraded.store().retain(l, ingest);
}
fn contentImpl(context: *anyopaque, rid: Rid) ?[]const u8 {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (rid > self.base_count) return self.added.store().content(rid - self.base_count);
if (self.shadow_of.get(rid)) |l| {
if (self.upgraded.store().content(l)) |bytes| return bytes;
}
return self.base.content(rid);
}
fn wireImpl(context: *anyopaque, rid: Rid) ?WireFrame {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (rid > self.base_count) return self.added.store().wire(rid - self.base_count);
if (self.shadow_of.get(rid)) |l| {
if (self.upgraded.store().wire(l)) |wf| return wf;
}
return self.base.wire(rid);
}
fn hashOfImpl(context: *anyopaque, rid: Rid) []const u8 {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (rid > self.base_count) return self.added.store().hashOf(rid - self.base_count);
return self.base.hashOf(rid);
}
fn lookupImpl(context: *anyopaque, hash: []const u8) ?Rid {
const self: *OverlayStore = @ptrCast(@alignCast(context));
if (self.base.lookup(hash)) |rid| return rid;
if (self.added.store().lookup(hash)) |l| return self.base_count + l;
return null;
}
fn countImpl(context: *anyopaque) usize {
const self: *OverlayStore = @ptrCast(@alignCast(context));
return self.base_count + self.added.store().count();
}
};
/// 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,
/// Which representation answers the freed queries. `.derived` reads the
/// hashmaps this struct builds via `crosslink` (the authoritative path);
/// `.image` reads a pre-materialized `repoimage.Image` (a warm read with
/// zero derivation). The public method set is identical in both — the tag
/// is an internal implementation detail behind the same interface.
backing: Backing = .derived,
/// §6.1's configured main-branch name, used as the branch value of a
/// check-in with no active branch tag. Defaults to `default_branch`
/// because §6.1 says the setting "itself defaults to trunk when the
/// setting is absent"; `RepoView` overwrites it from the config frame.
///
/// This is a FIELD rather than a parameter because it is consulted deep in
/// the leaf machinery (`branchWalk`, `sameBranch`), whose callers reach as
/// far as the public `resolve`. §6.1's requirement is that this LAYER not
/// assume a fixed string -- a value populated from config satisfies that;
/// what it forbids is the hardcoded literal `branchValueOf` used to read.
///
/// Borrowed, not owned: it points into the config bytes `RepoView` retains
/// for this state's lifetime, exactly as `RepoView.main_branch` does.
main_branch: []const u8 = default_branch,
/// The loaded read-image, set only in `.image` backing. Its column windows
/// borrow a buffer the owning `RepoView` keeps alive for this state's
/// lifetime; the one owned allocation (widened leaf rids) is freed by
/// `deinit`.
img: ?repoimage.Image = null,
/// 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,
/// Per-check-in C-card comments (owned dupes; "" for a commentless
/// manifest). Populated by `crosslink` alongside the event row; absent
/// for control artifacts and under image backing (`commentOf` returns
/// null there and the renderer falls back to the manifest read).
comments: std.AutoHashMapUnmanaged(Rid, []const u8) = .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,
};
/// The representation backing the freed query methods.
pub const Backing = enum { derived, image };
/// One materialized §8.2 resolution: a live symbolic name and the rid
/// `resolveName` selects for it. `name` borrows the interned tag-name bytes.
pub const ResolvedSymbol = struct {
name: []const u8,
rid: Rid,
};
pub fn init(gpa: std.mem.Allocator, artifact_store: ArtifactStore) RepoState {
return .{ .gpa = gpa, .store = artifact_store };
}
/// A read-image-backed state: the freed queries read `image`'s columns and
/// no derivation runs. `store` is a caller-supplied empty store (the image
/// serves hashes/lookups); the cold, non-freed methods must not be called
/// in this backing (asserted). The image's column windows must outlive the
/// returned state.
pub fn fromImage(gpa: std.mem.Allocator, artifact_store: ArtifactStore, image: repoimage.Image) RepoState {
return .{ .gpa = gpa, .store = artifact_store, .backing = .image, .img = image };
}
pub fn deinit(self: *RepoState) void {
if (self.img) |*img| img.deinit(self.gpa);
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);
var cit = self.comments.valueIterator();
while (cit.next()) |c| self.gpa.free(c.*);
self.comments.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(self.backing == .derived); // an image is read-only; deriving into it is a bug
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);
const owned_comment = try self.gpa.dupe(u8, rec.comment);
{
// Scoped: once the map owns the dupe, a later failure in this
// block must NOT free it again (deinit will).
errdefer self.gpa.free(owned_comment);
try self.comments.put(self.gpa, rid, owned_comment);
}
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(self.backing == .derived);
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 {
if (self.img) |*img| return img.isLeaf(rid);
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 {
if (self.img) |*img| return img.isOpenLeaf(rid);
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 {
if (self.img) |*img| return .{ .rids = img.leafRids() };
return .{ .rids = self.leaf_table.keys() };
}
/// The newest crosslinked check-in, or null in an unborn repository.
/// Exact walk order for a live state — `events` inserts in persisted
/// order and nothing ever removes one — and approximated by the highest
/// event rid under image backing (intern order tracks walk order except
/// for forward-referenced parents, which can only cost prefix coverage,
/// never correctness).
pub fn newestCheckin(self: *const RepoState) ?Rid {
if (self.img) |*img| {
var rid: Rid = @intCast(img.count());
while (rid >= 1) : (rid -= 1) if (img.hasEvent(rid)) return rid;
return null;
}
const rids = self.events.keys();
if (rids.len == 0) return null;
return rids[rids.len - 1];
}
/// 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 {
std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
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 {
if (self.img) |*img| return img.mtimeOf(rid);
return self.events.get(rid);
}
/// The check-in's C-card comment as crosslinked ("" for a commentless
/// manifest), or null when this state cannot answer — a control-only rid,
/// or image backing, where the caller falls back to reading the manifest.
/// Display overrides (repo-state §5.2) are the CALLER's to apply, exactly
/// as with the manifest-read path this replaces.
pub fn commentOf(self: *const RepoState, rid: Rid) ?[]const u8 {
if (self.img != null) return null; // the image does not materialize this column
return self.comments.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);
if (self.img) |*img| return img.branchOf(rid, main_branch);
std.debug.assert(self.events.contains(rid));
// The caller-supplied name and the stored one are the same §6.1 setting
// reaching this layer by two routes; a mismatch means one of them is
// stale, and the two readers would then disagree about which branch an
// untagged check-in is on -- the exact divergence this field exists to
// remove. Programmer error, so an assert rather than a reconciliation.
std.debug.assert(std.mem.eql(u8, main_branch, self.main_branch));
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, OutOfMemory }!Rid {
std.debug.assert(name.len != 0);
if (self.img) |*img| return img.resolveName(name) orelse error.NotFound;
const sym_id = self.symTagId(name) orelse return error.NotFound;
var pick: MtimeMaxPick = .{ .rs = self };
defer pick.deinit();
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;
try pick.offer(rid, mtime);
}
const result = (try pick.winner()) 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, OutOfMemory }!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) error{OutOfMemory}!?Rid {
std.debug.assert(branch.len != 0);
var pick: MtimeMaxPick = .{ .rs = self };
defer pick.deinit();
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
try pick.offer(rid, self.events.get(rid).?);
}
const best = try pick.winner();
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. Allocates only to settle an exact-`event.mtime` tie by ancestry
/// (`MtimeMaxPick`) — the hot path stays allocation-free.
pub fn resolve(self: *const RepoState, name: []const u8, want: NameType) error{ NotFound, Ambiguous, OutOfMemory }!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, OutOfMemory }!Rid {
std.debug.assert(name.len >= 1);
// A "sym-" selector normally names a user tag, whose canonical storage
// spelling is "sym-sym-...". Only when that ordinary lookup is absent
// may an imported canonical spelling address its stored "sym-..." row.
if (std.mem.startsWith(u8, name, "sym-")) {
return self.resolveName(name) catch |err| {
if (err != error.NotFound) return err;
const stored = name["sym-".len..];
if (stored.len == 0) return error.NotFound;
return self.resolveName(stored);
};
}
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 (try 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, OutOfMemory }!Rid {
std.debug.assert(name.len >= 1);
return self.dispatch(name) catch |err| {
// Only a NotFound is retryable: an ambiguity is a decided answer,
// and an allocation failure says nothing about the name's shape.
if (err != error.NotFound) 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, exact ties broken by ancestry (`MtimeMaxPick`).
fn tipForm(self: *const RepoState) error{ NotFound, OutOfMemory }!Rid {
var pick: MtimeMaxPick = .{ .rs = self };
defer pick.deinit();
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);
try pick.offer(rid, mtime);
}
const result = (try pick.winner()) orelse return error.NotFound;
// SF5 tripwire (BLOCKER-FIX-PLAN.md §3): `tip` naming a non-leaf is the
// symptom B1 presented as ("info tip" said "leaf: no" while "leaves"
// said otherwise). It is legitimate ONLY under a non-monotone clock — a
// child stamped STRICTLY EARLIER than its parent, e.g. a backdated
// commit. A child that TIES its parent's mtime means the ancestry
// tie-break above failed to fire, which is the defect itself.
if (std.debug.runtime_safety and self.backing == .derived) {
if (self.children.getPtr(result)) |kids| {
for (kids.items) |edge| {
const child_mtime = self.events.get(edge.rid) orelse continue;
std.debug.assert(child_mtime < self.events.get(result).?);
}
}
}
return result;
}
/// 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, OutOfMemory }!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, OutOfMemory }!Rid {
const bound_ms = expandTimestamp(text, mode) orelse return error.NotFound;
return (try 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) error{OutOfMemory}!?Rid {
var pick: MtimeMaxPick = .{ .rs = self };
defer pick.deinit();
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;
try pick.offer(rid, mtime);
}
return pick.winner();
}
/// 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 {
std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
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(self.backing == .derived); // cold query: image backing does not materialize this table
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 {
std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this table
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;
}
/// Total order over the whole check-in universe for the timeline listing:
/// event.mtime descending (Section 2 / Section 8.3 item 7 — the ordering
/// clock), exact-mtime ties broken by ascending full artifact hash so the
/// order is total and deterministic. Kept separate from `MtimeDescCtx`, whose
/// ties are impl-defined; here the tiebreak is load-bearing.
const TimelineOrderCtx = struct {
rs: *const RepoState,
fn lessThan(ctx: TimelineOrderCtx, a: Rid, b: Rid) bool {
const ma = ctx.rs.mtimeOf(a).?;
const mb = ctx.rs.mtimeOf(b).?;
if (ma != mb) return ma > mb; // §2/§8.3: most recent first
// §3 tiebreak: ascending full artifact hash → a byte-reproducible order.
return std.mem.order(u8, ctx.rs.store.hashOf(a), ctx.rs.store.hashOf(b)) == .lt;
}
};
/// Section 8.3 item 3's whole check-in universe: every crosslinked check-in
/// (each event rid, exactly once), ordered by event.mtime descending with an
/// ascending-full-hash tiebreak (`TimelineOrderCtx`). The single general
/// query behind `zit timeline` — ordering lives here, not in a CLI-side walk,
/// so it is testable in isolation. An empty repository yields an empty slice
/// (never an error). Caller frees the returned slice.
pub fn checkinsByMtime(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]Rid {
std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize this walk
var out: std.ArrayList(Rid) = .empty;
errdefer out.deinit(gpa);
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
try out.append(gpa, rid);
}
const slice = try out.toOwnedSlice(gpa);
errdefer gpa.free(slice);
std.mem.sort(Rid, slice, TimelineOrderCtx{ .rs = self }, TimelineOrderCtx.lessThan);
// Second pass: re-order each equal-mtime RUN so a descendant always
// lists before its ancestor (B1 — three same-second commits listed
// c1, c2, c3, oldest first, because the hash tiebreak knew nothing
// about the chain). This is a per-run pass and NOT a sort predicate:
// "descends-from, else hash" is not a strict weak order, so feeding it
// to `std.mem.sort` would be undefined behavior. Runs are bounded by
// the number of check-ins sharing one millisecond.
var gens: ?[]u32 = null;
defer if (gens) |g| gpa.free(g);
var i: usize = 0;
while (i < slice.len) {
const m = self.mtimeOf(slice[i]).?;
var j = i + 1;
while (j < slice.len and self.mtimeOf(slice[j]).? == m) j += 1;
if (j - i > 1) {
// Generations, once per render, on first need (§3.3 depth
// clock — one O(V+E) pass): the tied-run pass prunes its
// dominance walks to each run's generation band, which is
// what keeps a converted history's same-second batches (CVS
// imports emit thousands) from costing whole-DAG ancestor
// walks per comparison.
if (gens == null) gens = try self.computeGenerations(gpa);
self.orderTiedRun(slice[i..j], gens.?);
}
i = j;
}
// Postconditions: one rid per event, and the ordering clock is
// monotonically non-increasing across the whole listing (positive AND
// negative space). Within a run the order is the ancestry pass's, which
// deliberately overrides `TimelineOrderCtx`'s hash tiebreak.
std.debug.assert(slice.len == self.events.count());
for (slice, 0..) |rid, k| {
std.debug.assert(self.events.contains(rid));
if (k + 1 < slice.len)
std.debug.assert(self.mtimeOf(slice[k + 1]).? <= self.mtimeOf(rid).?);
}
return slice;
}
/// Topologically micro-order one equal-`event.mtime` run of the timeline
/// in place: descendants first (B1), concurrents deterministically. The
/// sort key is (generation DESC, full hash ASC): an ancestor's generation
/// is STRICTLY smaller than any of its descendants', so every
/// ancestor-related pair lands descendant-first — the exact property the
/// B1 fix exists for — with no ancestry walk at all. Concurrent pairs
/// (never ancestor-related, whatever their generations) order by depth
/// then hash: deterministic and byte-reproducible, replacing the old
/// repeated maximal-extraction's hash-only concurrent order, whose
/// per-comparison whole-DAG ancestor walks made a converted history's
/// same-second batches (CVS imports emit thousands) cost CPU-hours.
fn orderTiedRun(self: *const RepoState, run: []Rid, gens: []const u32) void {
std.debug.assert(run.len >= 2);
const Ctx = struct {
rs: *const RepoState,
gens: []const u32,
fn lessThan(ctx: @This(), a: Rid, b: Rid) bool {
const ga = ctx.gens[@intCast(a)];
const gb = ctx.gens[@intCast(b)];
if (ga != gb) return ga > gb; // deeper (descendant-most) first
// Equal generation: never ancestor-related; least hash.
return std.mem.order(u8, ctx.rs.store.hashOf(a), ctx.rs.store.hashOf(b)) == .lt;
}
};
std.mem.sort(Rid, run, Ctx{ .rs = self, .gens = gens }, Ctx.lessThan);
// Postcondition (negative space): generations never ascend, so no
// ancestor precedes a descendant.
for (run[0 .. run.len - 1], run[1..]) |earlier, later| {
std.debug.assert(gens[@intCast(earlier)] >= gens[@intCast(later)]);
}
}
/// Generation numbers over the crosslinked check-in DAG (§3.3 depth
/// clock): gen = 1 + the maximum parent generation, roots (and check-ins
/// whose parents were never crosslinked) at 1; non-event rids stay 0.
/// One iterative O(V+E) pass, dense by rid. A corrupt parent CYCLE is
/// broken deterministically (the in-progress parent contributes nothing)
/// rather than hanging. Caller frees the slice.
fn computeGenerations(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]u32 {
std.debug.assert(self.backing == .derived);
const in_progress = std.math.maxInt(u32);
const gens = try gpa.alloc(u32, self.store.count() + 1);
errdefer gpa.free(gens);
@memset(gens, 0);
var stack: std.ArrayList(Rid) = .empty;
defer stack.deinit(gpa);
for (self.events.keys()) |root| {
if (gens[@intCast(root)] != 0) continue;
try stack.append(gpa, root);
while (stack.items.len > 0) {
const rid = stack.items[stack.items.len - 1];
const g = gens[@intCast(rid)];
if (g != 0 and g != in_progress) {
_ = stack.pop();
continue;
}
gens[@intCast(rid)] = in_progress;
var max_parent: u32 = 0;
var ready = true;
var it = self.parentsOf(rid);
while (it.next()) |parent| {
if (!self.events.contains(parent)) continue; // phantom or control: generation base
const pg = gens[@intCast(parent)];
if (pg == in_progress) continue; // corrupt cycle: broken here, deterministically
if (pg == 0) {
ready = false;
try stack.append(gpa, parent);
continue;
}
max_parent = @max(max_parent, pg);
}
if (!ready) continue;
_ = stack.pop();
std.debug.assert(max_parent < in_progress - 1); // depth fits the clock
gens[@intCast(rid)] = max_parent + 1;
}
}
return gens;
}
/// Merge base of `a` and `b` over FULL ancestry (Section 3.3 child-to-parent
/// traversal, merge parents included per Section 3.2): the common ancestor
/// with the greatest event mtime (Section 2 / Section 8.3 item 7's ordering
/// clock), exact ties broken by ancestry — the DEEPEST tied common node,
/// true concurrents by least artifact hash (`MtimeMaxPick`). Total and
/// deterministic. Selecting an ancestor-dominated common node here picks the
/// wrong BASE for the three-way merge, which silently re-applies or drops
/// one side; a same-second diamond ties its whole common ancestry, so the
/// hash order this replaced decided it by lottery (blocker B1's merge-side
/// residual). Each endpoint is a member of its OWN ancestor set — the
/// BFS seeds each frontier with the endpoint node itself before walking
/// `parentsOf`, so a node is its own ancestor. Therefore
/// `mergeBaseOf(x, x) == x` and `mergeBaseOf(x, y) == y` whenever `y` is an
/// ancestor of `x` (the base == other equality the up-to-date refusal keys
/// on). `null` == no common ancestor (unrelated histories). Composed from
/// `parentsOf` / `mtimeOf` / `store.hashOf` — a general-purpose query with no
/// per-verb shaping (a future rebase/annotate reuses it). ambiguities.md
/// `merge-base`, implemented verbatim.
pub fn mergeBaseOf(self: *const RepoState, gpa: std.mem.Allocator, a: Rid, b: Rid) error{OutOfMemory}!?Rid {
std.debug.assert(self.backing == .derived); // cold query: image backing does not materialize the linkage table
// The full ancestor set of `a`, endpoint self-included.
var ancestors_a: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer ancestors_a.deinit(gpa);
try self.collectAncestors(gpa, a, &ancestors_a);
// Walk `b`'s ancestry (endpoint self-included) and keep the common node
// with the greatest event mtime, ties broken by the least artifact hash.
// Visited-once BFS, bounded by the artifact universe.
var visited_b: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer visited_b.deinit(gpa);
var frontier: std.ArrayList(Rid) = .empty;
defer frontier.deinit(gpa);
try frontier.append(gpa, b);
var pick: MtimeMaxPick = .{ .rs = self };
defer pick.deinit();
const bound = self.store.count();
var scanned: usize = 0;
while (frontier.pop()) |rid| {
const gop = try visited_b.getOrPut(gpa, rid);
if (gop.found_existing) continue;
scanned += 1;
std.debug.assert(scanned <= bound);
if (ancestors_a.contains(rid)) {
// A common node with no event row (a still-phantom target,
// Section 4.2 step 1) has no ordering clock and cannot win.
if (self.mtimeOf(rid)) |m| try pick.offer(rid, m);
}
var it = self.parentsOf(rid);
while (it.next()) |parent| try frontier.append(gpa, parent);
}
const best = try pick.winner();
// Postcondition: the winner is a common ancestor of both endpoints with a
// recorded event (positive space).
if (best) |chosen| {
std.debug.assert(ancestors_a.contains(chosen));
std.debug.assert(visited_b.contains(chosen));
std.debug.assert(self.mtimeOf(chosen) != null);
}
return best;
}
/// Selection accumulator shared by every "greatest `event.mtime` wins" site
/// — §8.2 plain-name resolution, §8.3 `tip` and date forms, §9 open-leaf,
/// and the merge-base scan. It keeps the running maximum AND every
/// candidate tied with it on the ordering clock, so an exact-mtime tie is
/// settled by DAG ancestry instead of by artifact-hash order.
///
/// Hash order between a check-in and its OWN ancestor is the B1 defect
/// (docs/plans/CLI-VERB-BREAKDOWN.md §B1/B2): three commits minted inside
/// one millisecond all tie, and the hash lottery hands `tip`/`trunk` an
/// ancestor of the newest check-in — silently, and differently per
/// repository.
///
/// The hot path allocates nothing and never walks ancestry: a tie needs two
/// check-ins stamped the same millisecond, so `tied` stays empty on
/// essentially every real selection and `winner` returns the running
/// maximum directly.
const MtimeMaxPick = struct {
rs: *const RepoState,
best: ?Rid = null,
best_mtime: Mtime = undefined,
/// Candidates tied with `best` on `event.mtime`, `best` itself excluded.
tied: std.ArrayList(Rid) = .empty,
fn deinit(self: *MtimeMaxPick) void {
self.tied.deinit(self.rs.gpa);
}
/// Offer one candidate. A strictly greater mtime replaces the maximum
/// and discards the tied set; an equal mtime joins it.
fn offer(self: *MtimeMaxPick, rid: Rid, mtime: Mtime) error{OutOfMemory}!void {
if (self.best == null or mtime > self.best_mtime) {
self.best = rid;
self.best_mtime = mtime;
self.tied.clearRetainingCapacity();
return;
}
if (mtime == self.best_mtime) try self.tied.append(self.rs.gpa, rid);
}
/// The selection's winner, or null when nothing was offered.
fn winner(self: *MtimeMaxPick) error{OutOfMemory}!?Rid {
const first = self.best orelse return null;
if (self.tied.items.len == 0) return first; // hot path: no ancestry walk
try self.tied.append(self.rs.gpa, first);
return try self.rs.ancestryMaximal(self.tied.items);
}
};
/// The winner of an equal-`event.mtime` tied set: the candidate that no
/// OTHER candidate descends from — a descendant always beats its ancestor
/// (§3.3 full ancestry, merge parents included). Candidates with no ancestry
/// relation are genuinely concurrent: neither the ordering clock nor the DAG
/// can separate them, so they fall back to the lexicographically least
/// artifact hash. That fallback is deterministic and byte-reproducible, and
/// it is NOT the B1 defect — the bug is hash order between ancestor-related
/// nodes, never between true concurrents.
///
/// Two phases, deliberately NOT a pairwise comparator. "Descends-from, else
/// hash" is not a strict weak order — transitivity fails across a mixed
/// comparable/incomparable triple — so folding it would depend on visit
/// order, and handing it to `std.mem.sort` would be undefined behavior.
/// Phase 1 materializes each candidate's ancestor set once (the shared
/// `collectAncestors` walk — never a second ancestry walker); phase 2 drops
/// every candidate that some other candidate has as an ancestor and takes
/// the least hash of what survives. O(k²) membership tests over a set that
/// is near-always size 1.
///
/// Derived backing only: `parentsOf` needs the linkage table. Every site
/// that can produce a tie is derived-only — image backing memoizes the
/// already-selected winner rather than re-running the selection.
fn ancestryMaximal(self: *const RepoState, tied: []const Rid) error{OutOfMemory}!Rid {
std.debug.assert(tied.len >= 1);
std.debug.assert(self.backing == .derived);
if (tied.len == 1) return tied[0];
const gpa = self.gpa;
const sets = try gpa.alloc(std.AutoHashMapUnmanaged(Rid, void), tied.len);
for (sets) |*s| s.* = .empty;
defer {
for (sets) |*s| s.deinit(gpa);
gpa.free(sets);
}
for (tied, sets) |rid, *s| try self.collectAncestors(gpa, rid, s);
var best: ?Rid = null;
for (tied) |cand| {
// `cand` is dominated when another candidate has it in its own
// ancestry — that other candidate is a descendant and outranks it.
//
// "Another" is a different check-in, not a different slot. A name can
// reach one rid through two index entries, and ancestor sets are
// self-inclusive, so skipping merely the same INDEX let a duplicate
// dominate its own copy: both were eliminated, and a tied set that was
// entirely duplicates left no maximal element at all.
var dominated = false;
for (tied, sets) |other_rid, *other| {
if (other_rid == cand) continue;
if (other.contains(cand)) {
dominated = true;
break;
}
}
if (dominated) continue;
const wins = best == null or
std.mem.order(u8, self.store.hashOf(cand), self.store.hashOf(best.?)) == .lt;
if (wins) best = cand;
}
// A finite DAG always has a maximal element, so the scan cannot come up
// empty (positive space).
const result = best.?;
// Postcondition (negative space): no other candidate descends from the
// winner — the exact property the whole tie-break exists to guarantee.
for (tied, sets) |cand, *s| {
if (cand == result) continue;
std.debug.assert(!s.contains(result));
}
return result;
}
/// Collect the full ancestor set of `start` — the endpoint itself plus every
/// rid reachable by repeated `parentsOf` (Section 3.3, merge parents
/// included) — into `set`. The frontier is seeded with `start`, so a node is
/// its own ancestor. Visited-once BFS bounded by the artifact universe.
fn collectAncestors(self: *const RepoState, gpa: std.mem.Allocator, start: Rid, set: *std.AutoHashMapUnmanaged(Rid, void)) error{OutOfMemory}!void {
var frontier: std.ArrayList(Rid) = .empty;
defer frontier.deinit(gpa);
try frontier.append(gpa, start);
const bound = self.store.count();
var scanned: usize = 0;
while (frontier.pop()) |rid| {
const gop = try set.getOrPut(gpa, rid);
if (gop.found_existing) continue;
scanned += 1;
std.debug.assert(scanned <= bound);
var it = self.parentsOf(rid);
while (it.next()) |parent| try frontier.append(gpa, parent);
}
}
/// The full ancestry of `rid` as a slice (Section 3.3, merge parents
/// included, self-inclusive) — the general-purpose ancestor-set query the
/// `annotate` version chain is built over. Order is unspecified (a
/// visited-once BFS over the hashed set); the caller imposes any
/// deterministic order it needs (annotate sorts by event mtime, ties by
/// hash). Shares the one `collectAncestors` walk `mergeBaseOf`/`isAncestorOf`/
/// `bisectSpan` use — never a second ancestry walker. Caller frees the slice.
pub fn ancestorsOf(self: *const RepoState, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]Rid {
std.debug.assert(self.backing == .derived); // cold query: the linkage table is derived-only
var set: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer set.deinit(gpa);
try self.collectAncestors(gpa, rid, &set);
const out = try gpa.alloc(Rid, set.count());
errdefer gpa.free(out);
var i: usize = 0;
var it = set.keyIterator();
while (it.next()) |k| : (i += 1) out[i] = k.*;
std.debug.assert(i == out.len);
return out;
}
/// The full ancestry of `rid` (Section 3.3, merge parents included,
/// self-inclusive) linearized into the annotate engine's PROCESSING order: a
/// topological order in which every parent precedes its child (oldest first),
/// so `annotate.attribute` resolves each parent before the child that inherits
/// from it. Topology is the PRIMARY key — a parent is ALWAYS ordered before
/// its child regardless of event mtime, so same-mtime and non-monotone
/// (clock-skewed / backdated) parent/child pairs never invert, matching
/// Fossil's generation-ordered annotate walk (`compute_direct_ancestors` +
/// `ORDER BY generation`). Among topologically-INCOMPARABLE check-ins the walk
/// (newest to oldest) takes the greatest event mtime first, ties by the
/// lexicographically greater artifact hash; the returned slice is that chain
/// REVERSED, so a linear monotone history degenerates to plain mtime-ascending
/// order (byte-identical to the pre-topology annotate output). Kahn's algorithm
/// over the reversed ancestry edges (child -> parent) with a (mtime desc, hash
/// desc) ready-queue — deterministic and total. Shares the one
/// `collectAncestors` walk `mergeBaseOf`/`ancestorsOf`/`bisectSpan` use; never a
/// second ancestry walker. ambiguities.md `annotate-attribution`. Caller frees
/// the slice.
pub fn ancestryLinearized(self: *const RepoState, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]Rid {
std.debug.assert(self.backing == .derived); // cold query: the linkage table is derived-only
var set: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer set.deinit(gpa);
try self.collectAncestors(gpa, rid, &set);
// `pending[n]` counts n's not-yet-emitted children WITHIN the set — its
// out-degree in the reversed (child -> parent) graph. A node is ready for
// the newest-to-oldest chain once every check-in descended from it has been
// emitted; the set is closed under `parentsOf`, so every parent is present.
var pending: std.AutoHashMapUnmanaged(Rid, u32) = .empty;
defer pending.deinit(gpa);
var kit = set.keyIterator();
while (kit.next()) |k| try pending.put(gpa, k.*, 0);
kit = set.keyIterator();
while (kit.next()) |k| {
var pit = self.parentsOf(k.*);
while (pit.next()) |parent| {
if (pending.getPtr(parent)) |cnt| cnt.* += 1;
}
}
// Ready set: nodes with no pending child (for a tip's ancestry, only `rid`
// itself starts here). Emit newest-first, popping the greatest (mtime, hash)
// each step; the total order yields one canonical linear extension.
var ready: std.ArrayList(Rid) = .empty;
defer ready.deinit(gpa);
kit = set.keyIterator();
while (kit.next()) |k| {
if (pending.get(k.*).? == 0) try ready.append(gpa, k.*);
}
const chain = try gpa.alloc(Rid, set.count());
errdefer gpa.free(chain);
var n: usize = 0;
while (ready.items.len != 0) {
var best: usize = 0;
for (ready.items[1..], 1..) |cand, i| {
if (self.chainBefore(cand, ready.items[best])) best = i;
}
const node = ready.swapRemove(best);
std.debug.assert(n < chain.len);
chain[n] = node;
n += 1;
var pit = self.parentsOf(node);
while (pit.next()) |parent| {
const cnt = pending.getPtr(parent) orelse continue;
std.debug.assert(cnt.* > 0);
cnt.* -= 1;
if (cnt.* == 0) try ready.append(gpa, parent);
}
}
std.debug.assert(n == chain.len); // acyclic ancestry => every node emitted
// The chain is newest -> oldest; reverse to the oldest-first processing
// order the engine consumes (every parent index strictly below its child's).
std.mem.reverse(Rid, chain);
return chain;
}
/// Chain order among topologically-incomparable check-ins (newest to oldest):
/// the greater event mtime first, ties broken by the lexicographically greater
/// artifact hash. A check-in with no event row (a phantom) has no ordering
/// clock; it sorts as mtime 0 so the order stays total and deterministic.
fn chainBefore(self: *const RepoState, a: Rid, b: Rid) bool {
const ma = self.mtimeOf(a) orelse 0;
const mb = self.mtimeOf(b) orelse 0;
if (ma != mb) return ma > mb;
return std.mem.order(u8, self.store.hashOf(a), self.store.hashOf(b)) == .gt;
}
/// Full-ancestry membership (Section 3.3): true iff `ancestor` lies in the
/// full ancestry of `descendant` — the descendant itself plus every rid
/// reachable by repeated `parentsOf` (merge parents included), WITH
/// self-membership, so `isAncestorOf(x, x) == true`. Shares the one
/// `collectAncestors` walk `mergeBaseOf` uses — no duplicated traversal.
/// mtime-INDEPENDENT, unlike `mergeBaseOf`: no ordering clock or hash
/// tiebreak enters, so this is the pure §3.3 reachability the up-to-date
/// merge refusal (B-merge-16) actually needs. `base == other` from
/// `mergeBaseOf` is NOT a sound proxy — when `other` ties another ancestor
/// on mtime and loses the least-hash tiebreak, the selection returns a
/// different node and the equality misses.
pub fn isAncestorOf(self: *const RepoState, gpa: std.mem.Allocator, ancestor: Rid, descendant: Rid) error{OutOfMemory}!bool {
var ancestors: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer ancestors.deinit(gpa);
try self.collectAncestors(gpa, descendant, &ancestors);
return ancestors.contains(ancestor);
}
/// The derived result of a bisect span computation (ambiguities.md
/// `bisect-midpoint`): the running lower bound / culprit, the untested count,
/// and the next probe.
pub const BisectOutcome = struct {
/// The mtime-earliest marked-bad check-in (ties: least artifact hash) —
/// the running lower bound of the search, and the culprit once
/// `probe == null`.
culprit: Rid,
/// The number of untested candidates (candidates minus every marked-bad
/// check-in that bears an event); 0 exactly when `probe == null`.
untested: usize,
/// The next probe: the lower median of the untested candidates ordered by
/// ascending event mtime (ties least hash), or null when none remain and
/// the culprit is final.
probe: ?Rid,
};
/// The two refusal preconditions of a bisect span, plus the shared allocation
/// failure. `InvertedMarks` — the bad check-in is an ancestor of a good one.
/// `UnrelatedHistories` — a good and the bad check-in share no ancestor.
pub const BisectError = error{ OutOfMemory, InvertedMarks, UnrelatedHistories };
/// The bisect candidate span and next probe (ambiguities.md `bisect-midpoint`,
/// implemented verbatim): the candidate set is the full-ancestry ancestor set
/// of the bad check-in (§3.3, merge parents included — every path contributes)
/// MINUS the union of every good's full-ancestry ancestor set MINUS the
/// skipped set. The "bad check-in" is the anchor = the mtime-earliest
/// marked-bad (ties least hash), which is also the culprit at termination. The
/// probe is the lower median of the untested candidates (candidates not marked
/// bad) by ascending event mtime, ties least hash. Refused, nothing computed:
/// an anchor that is an ancestor of a good (inverted marks) or a good sharing
/// no ancestor with the anchor (unrelated histories). ONE general-purpose
/// query composed from `collectAncestors`/`mergeBaseOf`/`isAncestorOf`/
/// `mtimeOf`/`store.hashOf` — never a CLI-side ancestry walk. Preconditions:
/// at least one bad and one good mark, each a crosslinked check-in.
pub fn bisectSpan(
self: *const RepoState,
gpa: std.mem.Allocator,
bad: []const Rid,
good: []const Rid,
skipped: []const Rid,
) BisectError!BisectOutcome {
std.debug.assert(self.backing == .derived); // cold query over the linkage table
std.debug.assert(bad.len != 0);
std.debug.assert(good.len != 0);
// The anchor bad = the mtime-earliest marked-bad (ties least hash): the
// running lower bound, and the culprit once no untested candidate remains.
var anchor: Rid = bad[0];
for (bad[1..]) |rid| {
if (self.bisectLess(rid, anchor)) anchor = rid;
}
// Preconditions key on THE bad check-in = the anchor. A good sharing no
// ancestor with it is unrelated histories; the anchor being an ancestor of
// a good is inverted marks. Both refuse before any candidate is built.
for (good) |g| {
if ((try self.mergeBaseOf(gpa, anchor, g)) == null) return error.UnrelatedHistories;
if (try self.isAncestorOf(gpa, anchor, g)) return error.InvertedMarks;
}
// Candidate set = full ancestry of the anchor, minus every good's full
// ancestry (each good is a member of its own set, so goods never survive),
// minus the skipped set.
var candidates: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer candidates.deinit(gpa);
try self.collectAncestors(gpa, anchor, &candidates);
for (good) |g| {
var g_anc: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer g_anc.deinit(gpa);
try self.collectAncestors(gpa, g, &g_anc);
var it = g_anc.keyIterator();
while (it.next()) |k| _ = candidates.remove(k.*);
}
for (skipped) |s| _ = candidates.remove(s);
// Untested = candidates not yet marked bad and bearing an event (a phantom
// placeholder has no ordering clock and cannot be probed).
var bad_set: std.AutoHashMapUnmanaged(Rid, void) = .empty;
defer bad_set.deinit(gpa);
for (bad) |rid| try bad_set.put(gpa, rid, {});
var untested: std.ArrayList(Rid) = .empty;
defer untested.deinit(gpa);
var cit = candidates.keyIterator();
while (cit.next()) |k| {
const rid = k.*;
if (bad_set.contains(rid)) continue;
if (self.mtimeOf(rid) == null) continue;
try untested.append(gpa, rid);
}
if (untested.items.len == 0) {
return .{ .culprit = anchor, .untested = 0, .probe = null };
}
// Order by ascending event mtime, ties least hash; the probe is the lower
// median (index (len - 1) / 2 — an even span probes the earlier element).
std.mem.sort(Rid, untested.items, self, bisectLess);
const idx = (untested.items.len - 1) / 2;
return .{ .culprit = anchor, .untested = untested.items.len, .probe = untested.items[idx] };
}
/// Probe / anchor total order: ascending event mtime, ties by least
/// (lexicographically-least) artifact hash. Defined only over check-ins that
/// bear an event — every caller filters phantoms out first.
///
/// Deliberately NOT converted to the B1 ancestry tie-break. This order picks
/// a bisect PROBE out of a candidate span; an equal-mtime tie decides only
/// which check-in is tested next, so ancestry order would change the number
/// of probes, never the culprit the search converges on. Correctness does
/// not ride on it, and a pairwise "descends-from, else hash" predicate is
/// not a strict weak order — illegal as a `std.mem.sort` comparator.
fn bisectLess(self: *const RepoState, a: Rid, b: Rid) bool {
const ma = self.mtimeOf(a).?;
const mb = self.mtimeOf(b).?;
if (ma != mb) return ma < mb;
return std.mem.order(u8, self.store.hashOf(a), self.store.hashOf(b)) == .lt;
}
/// 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
/// configured main branch when absent — the same name `branchOf`
/// falls back to, read from the one field `RepoView.setMainBranch`
/// sets, so the display name and the leaf test cannot disagree.
/// Section 6.1 forbids assuming a fixed string here.
fn branchValueOf(self: *const RepoState, rid: Rid) []const u8 {
return self.activeBranchValue(rid) orelse self.main_branch;
}
/// The interned id of tag `name`, or null when `name` was never interned in
/// this view (Section 2). A read-only sibling of `internTag`: it never
/// assigns an id — a never-seen name simply has none — so it stays `*const`.
/// "branch"/"closed" are the fixed reserved ids; every other name is looked
/// up in the `tag_names` table.
fn tagId(self: *const RepoState, name: []const u8) ?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;
return self.tag_names.get(name);
}
/// The live (non-cancel, latest-mtime-superseded) value of the tag `name` on
/// `rid` (Section 5.2/5.3), or null when no active row carries a value —
/// including when `name` was never interned (a name with no id has no rows).
/// A read-only lookup: it never assigns a tag id, so it is safe on the derived
/// read view the display sites hold. The returned bytes borrow the tagxref
/// row's stored value, valid until the next `RepoState` mutation.
pub fn activeTagValue(self: *const RepoState, rid: Rid, name: []const u8) ?[]const u8 {
std.debug.assert(name.len != 0);
const id = self.tagId(name) orelse return null;
if (self.tagxref.get(.{ .rid = rid, .tag = id })) |xr| {
if (xr.tagtype != .cancel) return xr.value; // Section 5.1: cancel is inactive
}
return null;
}
/// 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 materialized §8.2 resolution table: every live symbolic name (a
/// "sym-<name>" tag that resolves to a crosslinked check-in) paired with the
/// max-mtime rid `resolveName` selects for it. General-purpose — the read-
/// image consumer builds its name table from this. Each `name` borrows the
/// interned tag-name bytes (valid until the next mutation). Caller frees the
/// slice. Derived backing only (it reads the tag-name table).
pub fn resolvedSymbols(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]ResolvedSymbol {
std.debug.assert(self.backing == .derived);
const prefix = "sym-";
var out: std.ArrayList(ResolvedSymbol) = .empty;
errdefer out.deinit(gpa);
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) continue;
if (!std.mem.eql(u8, key[0..prefix.len], prefix)) continue;
const bare = key[prefix.len..];
// An unresolvable sym (phantom winner) is simply not listed. An
// allocation failure is NOT that: swallowing it here would drop a
// real symbol from the memoized image and make the cached view
// disagree with a derived one.
const rid = self.resolveName(bare) catch |e| switch (e) {
error.NotFound => continue,
error.OutOfMemory => return error.OutOfMemory,
};
try out.append(gpa, .{ .name = bare, .rid = rid });
}
return out.toOwnedSlice(gpa);
}
/// 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).
///
/// The `>=` skip is why crosslink ORDER is observable when a tag
/// arrives on a control artifact rather than on the check-in manifest
/// it targets: an inherited row laid down first by an ancestor's
/// propagation blocks a same-mtime direct application, where the same
/// tag carried on the check-in's own manifest would have applied
/// first (Section 4.2 step 2 before step 4a) and then been protected
/// by Section 5.5's unconditional nonzero-srcid block. `git import`
/// depends on this: it emits branch controls deepest-first for
/// exactly that reason (`git_import_impl.emitBranchControls`). Two
/// check-ins made in the same second are enough to expose it.
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
}
}
}
}
}
/// Evidence seam: propagation steps taken (one per `propagateOne` call).
/// Not consulted by the derivation; it is what makes "a cancel walk halts
/// at a rowless node" (#16) a testable claim rather than a wall-clock one.
pub var propagate_visits: u64 = 0;
/// Apply one propagation step to `child` (Section 5.4 steps 3-4):
/// qualifies iff an inherited (srcid 0) row with a strictly earlier
/// mtime — or, with NO existing row, only for a PROPAGATING tag. A
/// rowless child has nothing to cancel, and real Fossil's walk halts
/// there (tag.c: `coalesce(srcid=0 AND mtime<:mtime, tagType==2)` — the
/// LEFT-JOIN NULL falls back to "is this a propagating tag", false for a
/// cancel — gating `pqueuex_insert`). The prior "always qualifies"
/// reading came from a divergent draft copy of repo-state §5.4 step 3,
/// not from Fossil (issue #16; erratum repo-state-00-s5.4-cancel-halt).
/// 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.
fn propagateOne(self: *RepoState, child: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!bool {
propagate_visits += 1;
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 (ptype == .propagate);
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];
}
};
// ---------------------------------------------------------------------------
// draft-fossil-submanifests-00 §7/§9 — sub-manifests in synchronization and
// repository state.
//
// §7 opens with the framing that governs every rule below: "Sub-manifests are
// ordinary artifacts for every discovery and transfer purpose ... no wire-format
// change exists." Nothing here touches the wire; what the S card adds is a THIRD
// deferred-edge kind (§9.4) beside the delta-manifest baseline and the content
// delta source, plus the two disciplines a third edge kind needs to be safe: a
// sweep that terminates (§9.2) and a memo that makes the repeated parse the
// format was designed to avoid actually go away (§7.4).
// ---------------------------------------------------------------------------
/// §9.2 — the disposition of one stored structural artifact in a crosslink
/// sweep that "discovers crosslink work by negative space — selecting every
/// structural artifact for which no derived row exists".
///
/// Two variants, not a bool, because the two states are not "yes/no work" but
/// two different terminal conditions: one artifact is owed a derived row, the
/// other is finished the instant it is stored and must never be re-selected.
pub const SweepDisposition = enum {
/// The artifact produces a derived row of its own, so a sweep that finds
/// none still owes it a crosslink pass.
crosslink,
/// §7.3: the artifact "has no direct crosslink effect ... it carries no
/// state-bearing card and contributes to repository state only through the
/// manifests whose trees contain it". Negative space will therefore ALWAYS
/// find no derived row for it, so a sweep keyed on negative space alone
/// "re-selects and re-parses them on every pass, forever" (§9.2).
complete_on_arrival,
};
/// §9.2 — the sweep's admission rule, stated once, over the artifact type.
/// Exhaustive: a new artifact type cannot be added without deciding whether it
/// carries derived state, which is exactly the decision §9.2 says a sweep must
/// not make implicitly.
pub fn sweepDisposition(kind: artifact.ArtifactType) SweepDisposition {
return switch (kind) {
// A check-in manifest carries the DAG linkage and its own tags; a
// control artifact carries tags. Both own derived rows (repo-state §4.2).
.manifest, .control => .crosslink,
// §9.2's named case, plus every other type that contributes no row to
// the check-in DAG. §9.1: "Required-card logic ... MUST treat
// SUBMANIFEST (like CLUSTER) as an explicit exception" — CLUSTER is the
// precedent this rule extends, so the two sit in one arm.
.submanifest, .cluster, .wiki, .ticket, .attachment, .event, .forum => .complete_on_arrival,
};
}
comptime {
// §9.2's whole point: the sub-manifest must be OUT of the sweep. Asserted at
// compile time so the exclusion cannot be lost to a later edit of the switch.
std.debug.assert(sweepDisposition(.submanifest) == .complete_on_arrival);
std.debug.assert(sweepDisposition(.manifest) == .crosslink);
}
/// §7.1/§7.3/§9.4 — the S-reference deferred-edge table: the third edge kind.
///
/// §9.4: "Deferred-processing cascades typically know two edge kinds:
/// delta-manifest baselines and content delta sources. The S reference is a
/// third. An implementation MUST record, when a tree manifest's processing is
/// deferred (Section 7.3), enough to rediscover that manifest when the missing
/// sub-manifest arrives, and its dephantomization path MUST traverse that
/// record; a cascade that walks only the two older edge kinds leaves such a
/// check-in permanently unprocessed."
///
/// The record is keyed exactly as §7.3 states — "keyed by dependent and missing
/// hash" — with both sides interned to rids, so the table costs two integers per
/// edge and an arrival is one map lookup rather than a scan. Idempotence is
/// structural, not a check: the dependent set under a missing hash is a SET, so
/// re-recording the same gap is a no-op by construction (§7.3: "idempotently").
///
/// §7.1's "with the referencing artifact's privacy classification" has no
/// representation here: zit's `ArtifactStore` models a phantom as an interned
/// rid with no content and carries no per-entry privacy (privacy is a per-send
/// classification in sync's round tables), so an S-reference phantom is minted
/// exactly as an absent delta source's is — which is precisely what §7.1 asks
/// for. When per-entry privacy lands, it lands for both edge kinds at once.
pub const TreeDeferrals = struct {
gpa: std.mem.Allocator,
store: ArtifactStore,
/// The gap table: missing sub-manifest rid -> the set of dependent rids
/// whose processing that gap blocks. A set-valued map, so §7.3's
/// idempotence needs no guard.
gaps: std.AutoArrayHashMapUnmanaged(Rid, std.AutoArrayHashMapUnmanaged(Rid, void)) = .empty,
/// Reverse index: dependent rid -> how many distinct gaps it waits on. Kept
/// in lockstep with `gaps` so "is this manifest still deferred?" is O(1) and
/// a dependent leaves the deferred set exactly when its LAST gap closes —
/// §5.2 hard failure means a tree with any gap left is still not a file set.
waiting: std.AutoArrayHashMapUnmanaged(Rid, usize) = .empty,
pub fn init(gpa: std.mem.Allocator, store: ArtifactStore) TreeDeferrals {
return .{ .gpa = gpa, .store = store };
}
pub fn deinit(self: *TreeDeferrals) void {
for (self.gaps.values()) |*set| set.deinit(self.gpa);
self.gaps.deinit(self.gpa);
self.waiting.deinit(self.gpa);
self.* = undefined;
}
/// §7.1 — "Storing a structural artifact that carries S cards whose
/// referenced sub-manifests are absent MUST create a phantom for each
/// missing reference, with the referencing artifact's privacy
/// classification, exactly as an absent delta source creates a source
/// phantom." Returns how many of `refs` were absent, so a caller learns in
/// one pass whether this level of the closure is complete — zero means the
/// artifact's own S run resolves and processing may proceed.
///
/// Applies to EVERY S-bearing artifact, tree manifest and interior
/// sub-manifest alike: §7.1's "An interior sub-manifest's own S references
/// become known only when it arrives, so a tree of depth d converges in at
/// most d+1 pull rounds" is precisely the statement that this runs again on
/// each arrival, one level deeper.
pub fn phantomize(self: *TreeDeferrals, refs: []const []const u8) error{OutOfMemory}!usize {
var absent: usize = 0;
for (refs) |ref| {
std.debug.assert(ref.len == 40 or ref.len == 64); // §3.5 hash token
const rid = try self.store.intern(ref);
if (!self.store.held(rid)) absent += 1;
}
// `absent <= refs.len` by construction: the loop increments it at most
// once per ref. Asserting it restated the loop and, per trunk's
// release-assert guard, put a panic on a path fed by parsed refs.
return absent;
}
/// §7.3 — "record the gap keyed by dependent and missing hash,
/// idempotently, and retry on arrival." `missing` is interned here too, so
/// recording a gap always leaves the §7.1 phantom in place even when the
/// caller reached this path without a separate `phantomize`.
pub fn deferProcessing(self: *TreeDeferrals, dependent: []const u8, missing: []const u8) error{OutOfMemory}!void {
// §3.5 hash-token shape is established upstream by the card parser, which
// is the only producer of these two: `collectSubManifestRefs` rejects a
// malformed run before any of it reaches here. Asserting the length again
// added a ReleaseSafe panic on peer data without adding a check.
const missing_rid = try self.store.intern(missing);
const dependent_rid = try self.store.intern(dependent);
std.debug.assert(missing_rid != dependent_rid); // no artifact references itself
const gop = try self.gaps.getOrPut(self.gpa, missing_rid);
if (!gop.found_existing) gop.value_ptr.* = .empty;
const seen = try gop.value_ptr.getOrPut(self.gpa, dependent_rid);
if (seen.found_existing) return; // §7.3 idempotence: nothing changes
seen.value_ptr.* = {};
const w = try self.waiting.getOrPut(self.gpa, dependent_rid);
if (!w.found_existing) w.value_ptr.* = 0;
w.value_ptr.* += 1;
// `isDeferred(dependent)` now holds by construction — the waiting count
// was just incremented above and only reaches zero in `onArrival`.
}
/// §9.4 — the dephantomization path. `arrived` has just been stored;
/// append every dependent recorded against it to `out` and drop the edge,
/// so each recorded gap drives exactly one retry. A dependent whose LAST
/// gap closes leaves the deferred set; one that still waits on a sibling
/// gap stays in it, because §5.2 forbids presenting a partially resolved
/// tree as a file set.
///
/// Never interns: an arrival is a lookup over recorded edges, and minting a
/// phantom for a hash the repository has never seen is exactly what
/// [FossilSync] §3.3 forbids of a membership query.
pub fn onArrival(
self: *TreeDeferrals,
arrived: []const u8,
out: *std.ArrayListUnmanaged(Rid),
) error{OutOfMemory}!void {
// As in `deferProcessing`: the token's shape is the parser's guarantee,
// and `lookup` below answers null for anything it does not know, so a
// malformed name is already a no-op rather than a fault.
const rid = self.store.lookup(arrived) orelse return;
var kv = self.gaps.fetchSwapRemove(rid) orelse return;
defer kv.value.deinit(self.gpa);
for (kv.value.keys()) |dependent| {
try out.append(self.gpa, dependent);
const w = self.waiting.getPtr(dependent).?;
std.debug.assert(w.* >= 1);
w.* -= 1;
if (w.* == 0) _ = self.waiting.swapRemove(dependent);
}
}
/// True while `dependent`'s tree still has at least one recorded gap —
/// the §5.2 "not yet a complete file set" predicate, answered without a
/// walk.
pub fn isDeferred(self: *const TreeDeferrals, dependent: []const u8) bool {
const rid = self.store.lookup(dependent) orelse return false;
return self.waiting.contains(rid);
}
/// Distinct missing sub-manifests currently recorded. Drains to zero when a
/// tree's closure completes — the convergence oracle §7.1's "at most d+1
/// pull rounds" is measured against.
pub fn gapCount(self: *const TreeDeferrals) usize {
return self.gaps.count();
}
/// Distinct dependents currently deferred.
pub fn deferredCount(self: *const TreeDeferrals) usize {
return self.waiting.count();
}
};
/// §7.1 — a cheap, exact-enough pre-filter for "these bytes might carry an S
/// card", so a receiver pays a parse ONLY for artifacts that could add an S
/// reference. Every artifact predating this draft fails it on the first scan,
/// which is what keeps §7.1's receive-side duty off the existing hot path.
///
/// One-sided by design: false POSITIVES are permitted (a file blob whose
/// content happens to hold a line beginning `S ` is admitted, and the real
/// parse then finds no S run and mints nothing), false NEGATIVES are not. That
/// asymmetry is why this is not a second card parser and does not breach the
/// §9.3 enumeration seam: it decides who gets parsed, never what an artifact
/// means. The card grammar makes it exact on the negative side — cards are
/// LF-terminated and `s-card = %x53 SP filename SP hash LF` (§3.6), so an S
/// card is always `S` SP at the start of the artifact or right after an LF.
pub fn sBearingCandidate(bytes: []const u8) bool {
if (bytes.len >= 2 and bytes[0] == 'S' and bytes[1] == ' ') return true;
return std.mem.indexOf(u8, bytes, "\nS ") != null;
}
/// §7.2 — the transfer gate's content predicate, over one artifact's plaintext.
///
/// §7.2 names TWO shapes: "a local artifact is of type SUBMANIFEST, **or** is a
/// manifest carrying an S card". `sBearingCandidate` answers only the second.
/// The first is not a superset of it: §4.4 forbids a SUBMANIFEST carrying both
/// F and S cards, so a LEAF sub-manifest — the artifact that actually holds a
/// tree's file entries — carries F cards and NO S card and fails
/// `sBearingCandidate` outright. A gate keyed on S-bearingness alone therefore
/// ships every leaf of a tree to a peer that cannot read one, leaving the peer
/// artifacts §8 says are "unreadable -- rejected as structural, held as opaque
/// content". Refusing the tree manifest while transmitting its leaves is not a
/// weaker gate than none; it is the silent divergence §7.2 exists to prevent.
///
/// NOT a pre-filter. `sBearingCandidate` is one-sided by design (a file blob
/// whose content holds a line beginning `S ` is admitted, and the real parse
/// behind it mints nothing); that asymmetry is sound at the §7.1 phantomize
/// sites, where `collectSubManifestRefs` IS the parse behind the filter. There
/// is no parse behind this one — its answer is the transmission decision — so a
/// filter's false positive here is a REFUSAL of an artifact §7.2 never named.
/// §7.2's gated set is exactly two shapes; a file blob is neither, whatever its
/// content happens to spell. So this predicate tokenizes the whole card run
/// (§4.2) and answers from what the artifact IS:
///
/// shape one — `artifact.determineType` says SUBMANIFEST (§4.3), which is the
/// leaf and interior case and needs no S card at all;
/// shape two — the run carries an S card that actually parses (§3.6), which
/// is the tree manifest (D card present, so §4.3 does not reassign it).
///
/// Cheap on the negative side, which is every artifact in every repository that
/// predates this draft: a card run's first byte is a card letter and its second
/// is SP or LF, so a blob is rejected in two byte comparisons, before any scan.
/// The residual false positive is only a file blob that is ALSO a complete,
/// valid, D-less card sequence — content that no conforming reader can tell
/// from a sub-manifest either, and refusing it is §7.2's own outcome, never a
/// converted or downgraded transmission.
/// Is `bytes` a delta (B-card) manifest? The ingest-side dialect detector:
/// card order is ascending (§4.5.1) and B sorts before every letter but A,
/// so the answer is settled within the first two card lines — a blob is
/// rejected in two byte comparisons, exactly `transferGatedArtifact`'s cost
/// shape. Content reaching this predicate has already been §7.7-verified, so
/// a leading B card means a delta manifest, not coincidence.
pub fn deltaManifestArtifact(bytes: []const u8) bool {
if (bytes.len < 2) return false;
if (!artifact.isCardLetter(bytes[0])) return false;
if (bytes[1] != ' ' and bytes[1] != '\n') return false;
var cursor: usize = 0;
var lines: usize = 0;
while (cursor < bytes.len and lines < 2) : (lines += 1) {
const end = std.mem.indexOfScalarPos(u8, bytes, cursor, '\n') orelse return false;
const card = artifact.tokenizeCardLine(bytes[cursor .. end + 1]) orelse return false;
if (card.letter == 'B') return true;
if (card.letter > 'B') return false; // ascending order: B cannot follow
cursor = end + 1;
}
return false;
}
pub fn transferGatedArtifact(bytes: []const u8) bool {
if (bytes.len < 2) return false; // the shortest card is `X\n`
// Exact on the negative side: every line of a card run tokenizes as a card,
// so the first one does, so byte 0 is a card letter and byte 1 is SP or LF.
if (!artifact.isCardLetter(bytes[0])) return false;
if (bytes[1] != ' ' and bytes[1] != '\n') return false;
var census: artifact.Census = .{};
var s_parses = false;
var cursor: usize = 0;
// Bounded by `bytes.len`: every iteration consumes at least the line's LF.
while (cursor < bytes.len) {
const end = std.mem.indexOfScalarPos(u8, bytes, cursor, '\n') orelse return false;
const card = artifact.tokenizeCardLine(bytes[cursor .. end + 1]) orelse return false;
std.debug.assert(card.letter >= 'A' and card.letter <= 'Z'); // tokenizeCardLine's own guarantee
census.letters |= @as(u32, 1) << @intCast(card.letter - 'A');
if (card.letter == 'S' and sCardParses(card)) s_parses = true;
cursor = end + 1;
}
std.debug.assert(cursor == bytes.len);
// Shape two first: it is the tree manifest, and it is the only shape whose
// membership the type determination cannot express (a D card keeps it a
// MANIFEST). Shape one is then exactly §4.3's reassignment.
if (s_parses) return true;
return artifact.determineType(census) == .submanifest;
}
/// §3.6 — does this already-tokenized S card parse? `artifact.parseSCard` needs
/// a decode buffer at least as wide as the filename token and neither send gate
/// has an allocator in reach (both are `*const` methods on the sans-IO peer
/// structs), so the buffer is a bounded stack frame. A filename token wider than
/// it is answered `true` rather than skipped: over-long is not evidence the card
/// is inert, and §7.2's outcome for anything inside the gate is refusal, so the
/// one direction that can never be wrong here is the refusing one.
fn sCardParses(card: artifact.CardLine) bool {
std.debug.assert(card.letter == 'S');
var decode_buf: [s_card_decode_max]u8 = undefined;
const args = card.args orelse return false; // `S\n`: no filename, no hash
const first_sp = std.mem.indexOfScalar(u8, args, ' ') orelse args.len;
if (first_sp > decode_buf.len) return true; // wider than the frame: refuse, never admit
return artifact.parseSCard(card, &decode_buf) != null;
}
/// The widest §3.6 filename token `sCardParses` decodes on the stack. §4.6.1
/// caps no pathname length, so this is a frame budget, not a grammar bound —
/// generous against every pathname a repository can hold and small enough to sit
/// on a send path's stack.
const s_card_decode_max: usize = 1024;
/// §7.1 — the ONE S-reference extractor, shared by every storing boundary.
/// Appends each S card's hash token to `out` and returns true.
///
/// §7.1 is a duty of *storing*, and zit stores an artifact at two boundaries:
/// the sync receive path (`sync.Client`, in-memory) and the persist commit hook
/// (`cmd/sync.persistStore`, durable — the boundary a clone and a server-side
/// push both cross, since neither absorbs on receive). Stating the scan once
/// here is what keeps those two from drifting: a rule written twice is a rule
/// enforced on one path.
///
/// Validate-then-apply. The whole artifact is checked before a single hash is
/// appended, and a malformed card line or a malformed S card returns false with
/// `out` untouched. §7.1 phantomizes the references of "a structural artifact
/// that carries S cards"; a byte string that is not a well-formed card sequence
/// is not one, and a half-read artifact must never leave a half-minted phantom
/// set behind — the discipline `sync.absorbCluster` already applies to M cards.
///
/// Borrowing: each appended hash is a slice INTO `content` (§3.6's hash token
/// admits no escapes, so it is never rewritten through the decode buffer).
/// `content` MUST therefore outlive `out`.
pub fn collectSubManifestRefs(
gpa: std.mem.Allocator,
content: []const u8,
out: *std.ArrayListUnmanaged([]const u8),
) error{OutOfMemory}!bool {
const base = out.items.len;
if (!sBearingCandidate(content)) return true; // predates this draft: nothing to do
// Pass 1: every line must tokenize as a card. `widest` bounds the escape-
// decode buffer pass 2 needs — the longest card line is an upper bound on
// any token inside it, so one allocation covers the whole artifact.
var widest: usize = 0;
var any_s = false;
var cursor: usize = 0;
while (cursor < content.len) {
const end = std.mem.indexOfScalarPos(u8, content, cursor, '\n') orelse return false;
const line = content[cursor .. end + 1];
const card = artifact.tokenizeCardLine(line) orelse return false;
if (card.letter == 'S') {
any_s = true;
if (line.len > widest) widest = line.len;
}
cursor = end + 1;
}
std.debug.assert(cursor == content.len);
if (!any_s) return true; // a false positive from the pre-filter
const decode_buf = try gpa.alloc(u8, widest);
defer gpa.free(decode_buf);
// Pass 2: every S card must parse (§3.6). A single malformed one voids the
// whole run BEFORE anything is applied.
cursor = 0;
while (cursor < content.len) {
const end = std.mem.indexOfScalarPos(u8, content, cursor, '\n').?;
const card = artifact.tokenizeCardLine(content[cursor .. end + 1]).?;
cursor = end + 1;
if (card.letter != 'S') continue;
if (artifact.parseSCard(card, decode_buf) == null) return false;
}
// Pass 3: apply. An allocation failure here rewinds to the entry length, so
// even OOM leaves the caller a set it never half-applied.
cursor = 0;
while (cursor < content.len) {
const end = std.mem.indexOfScalarPos(u8, content, cursor, '\n').?;
const card = artifact.tokenizeCardLine(content[cursor .. end + 1]).?;
cursor = end + 1;
if (card.letter != 'S') continue;
const sc = artifact.parseSCard(card, decode_buf).?;
std.debug.assert(sc.hash.len == 40 or sc.hash.len == 64); // §3.5
out.append(gpa, sc.hash) catch |e| {
out.shrinkRetainingCapacity(base);
return e;
};
}
std.debug.assert(out.items.len > base); // `any_s` proved at least one S card
return true;
}
/// §7.4 — "Implementations SHOULD cache per-sub-manifest enumeration results
/// keyed by artifact name: unchanged subtrees are shared by hash across
/// check-ins, so a memoizing rebuild parses each distinct sub-manifest once,
/// converting rebuild cost from the sum of full file-set sizes to the sum of
/// distinct-artifact sizes. A naive implementation obtains the byte reduction
/// of this format but not the parse-count reduction that motivated it."
///
/// Written as a DECORATOR over `artifact.SubResolver` rather than as a cache
/// inside the walk, so the §5.1 walk stays byte-identical and the seam §9.3
/// mandates keeps exactly one implementation: a caller opts in by passing
/// `memo.resolver()` where it passed the store's resolver.
///
/// Safety rests on content addressing, which makes a POSITIVE answer immutable:
/// the artifact named by a hash never changes, so its F and S runs never change.
/// A NEGATIVE answer is not immutable — the missing sub-manifest arrives later
/// (§7.1) — so a miss is never cached, and the memo can therefore not pin a
/// tree as unresolvable. Every cached run is copied into the memo's own arena:
/// the inner resolver's buffers live only for one flatten, while the memo spans
/// a whole rebuild.
/// §7.4 — the memo's retention budget: the size it is TRIMMED BACK TO between
/// walks, not a point past which it stops working.
///
/// It was 4 MiB and fill-then-freeze — on reaching it the memo stopped
/// interning for the rest of the run, so the retained set froze at whatever was
/// encountered FIRST rather than what was hot, and every later resolve paid a
/// lookup that could no longer hit. Measured on a 30,000-file tree (40
/// check-ins, 10 files changed each): the true working set was 7,494 KiB
/// against that 4,096 KiB ceiling, which cost 23 points of hit rate (92% -> 69%)
/// and about 27% of import wall time on identical work. The ceiling was wrong by
/// less than a factor of two, which is why it never showed up on smaller
/// corpora.
///
/// Now that eviction is by recency, exceeding this is graceful: the memo holds
/// the most recently used views and the hit rate falls off smoothly instead of
/// stepping off a cliff. That changes what the number has to be right about — it
/// is a memory-vs-hit-rate dial, not a correctness or capacity bound, so being
/// somewhat too small costs a little speed and nothing else.
///
/// 64 MiB is chosen against the measurement above: scaling that working set by
/// width puts a pkgsrc-scale tree (~123k files) near 30 MiB, so this holds one
/// comfortably while staying a bounded, statable memory cost.
pub const submanifest_memo_budget: usize = 64 << 20;
pub const SubManifestMemo = struct {
/// One retained view. Allocated individually rather than from an arena
/// because eviction has to free ONE entry, which an arena cannot do.
/// `bytes` is this entry's own contribution to `retained`, recorded at copy
/// time so eviction can subtract exactly what insertion added rather than
/// recompute it from slices it is about to free.
const Entry = struct {
key: []u8,
view: artifact.SubManifestView,
bytes: usize,
/// Recency list links; `newer == null` marks the most recently used.
newer: ?*Entry = null,
older: ?*Entry = null,
};
gpa: std.mem.Allocator,
/// The seam a MISS falls through to. Rebindable between walks: a cached
/// answer is a deep copy the memo owns and never touches `inner`, so a
/// caller that reuses one memo across several enumerations (each with its
/// own scratch resolver) rebinds through `beginWalk`.
inner: artifact.SubResolver,
/// Artifact name -> the retained entry. Keys are owned by their entry.
entries: std.StringHashMapUnmanaged(*Entry) = .empty,
/// Recency list, most recently used at `mru`. Eviction takes from `lru`.
mru: ?*Entry = null,
lru: ?*Entry = null,
/// Resolutions answered from the memo — the parses §7.4 says a naive
/// implementation repeats.
hits: usize = 0,
/// Resolutions that reached the inner seam: the distinct-artifact count.
misses: usize = 0,
/// Entries dropped by `beginWalk` to get back under budget. A run with many
/// of these is one whose working set exceeds the budget; unlike the old
/// fill-then-freeze behaviour it stays correct and merely re-parses.
evicted: usize = 0,
/// Set when a copy could not be allocated. Not an error path: the inner
/// answer is returned uncached, so the memo degrades to the naive behaviour
/// §7.4 tolerates rather than failing a walk that would otherwise succeed.
/// It no longer means "the budget was reached" — the budget is now handled
/// by eviction, and reaching it is ordinary operation.
degraded: bool = false,
/// Bytes of retained views. Approximate by design: it counts the borrowed
/// bytes copied, not the allocator's own padding, which is enough to steer
/// eviction without making allocator internals part of the contract.
retained: usize = 0,
/// The size `beginWalk` trims back to. A field rather than a direct read of
/// `submanifest_memo_budget` so eviction is testable at a size a test can
/// actually reach — the same seam `extras.sweepBounded` takes its ceiling
/// through. Production callers leave the default.
budget: usize = submanifest_memo_budget,
pub fn init(gpa: std.mem.Allocator, inner: artifact.SubResolver) SubManifestMemo {
return .{ .gpa = gpa, .inner = inner };
}
pub fn deinit(self: *SubManifestMemo) void {
var it = self.entries.valueIterator();
while (it.next()) |e| self.destroy(e.*);
self.entries.deinit(self.gpa);
self.* = undefined;
}
/// Start a walk against `seam`, and take the ONLY safe opportunity to evict.
///
/// Eviction cannot happen inside `resolve`. `artifact.TreeWalk` keeps a
/// frame per open level, and each frame's `subs` BORROWS the view that
/// resolved it — so at any moment mid-walk up to `max_tree_depth + 1` views
/// are live, plus the open leaf's F run and `last`. Freeing an entry during
/// a `descend()` would pull memory out from under an ancestor frame that the
/// walk is still reading. The arena this memo used to allocate from made
/// that impossible by never freeing anything; per-entry allocation gives up
/// that guarantee, so the boundary has to be enforced here instead.
///
/// Between walks nothing is live: `flattenTree` dupes every emitted card
/// into the MANIFEST's own arena, so the flattened result borrows nothing
/// from the memo. That makes the moment before a walk starts the one place
/// eviction is provably safe, which is why rebinding the seam and trimming
/// are the same call rather than two the caller could get out of order.
///
/// Trimming to budget here also means growth WITHIN a walk is unbounded by
/// this budget — bounded instead by that walk's own tree, which the caller
/// is already holding a larger flattened copy of, so it adds no order of
/// magnitude.
pub fn beginWalk(self: *SubManifestMemo, seam: artifact.SubResolver) void {
self.inner = seam;
while (self.retained > self.budget) {
const victim = self.lru orelse break;
self.unlink(victim);
_ = self.entries.remove(victim.key);
self.retained -= victim.bytes;
self.destroy(victim);
self.evicted += 1;
}
}
/// The seam to hand `flattenTree`/`lookupTree` in place of the store's own.
pub fn resolver(self: *SubManifestMemo) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = SubManifestMemo.resolve };
}
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
const self: *SubManifestMemo = @ptrCast(@alignCast(ctx));
if (self.entries.get(hash)) |entry| {
self.hits += 1;
self.touch(entry);
return entry.view;
}
const view = self.inner.resolveFn(self.inner.ctx, hash) orelse return null;
self.misses += 1;
// A failed copy leaves the answer correct and merely uncached.
const copied = self.copy(hash, view) catch {
self.degraded = true;
return view;
};
return copied;
}
/// Move `e` to the most-recently-used end. Called on every hit, so recency
/// reflects use rather than insertion — the distinction that makes eviction
/// drop what is cold instead of what merely arrived first.
fn touch(self: *SubManifestMemo, e: *Entry) void {
if (self.mru == e) return;
self.unlink(e);
self.link(e);
}
fn link(self: *SubManifestMemo, e: *Entry) void {
e.newer = null;
e.older = self.mru;
if (self.mru) |m| m.newer = e;
self.mru = e;
if (self.lru == null) self.lru = e;
}
fn unlink(self: *SubManifestMemo, e: *Entry) void {
if (e.newer) |n| n.older = e.older else self.mru = e.older;
if (e.older) |o| o.newer = e.newer else self.lru = e.newer;
e.newer = null;
e.older = null;
}
/// Free one entry and everything it owns. Never touches the recency list or
/// the map: callers do that first, so this is the single place that knows
/// the ownership shape.
fn destroy(self: *SubManifestMemo, e: *Entry) void {
for (e.view.files) |f| {
self.gpa.free(f.filename);
if (f.hash) |h| self.gpa.free(h);
if (f.perm) |p| self.gpa.free(p);
if (f.old_name) |o| self.gpa.free(o);
}
self.gpa.free(e.view.files);
for (e.view.subs) |c| {
self.gpa.free(c.filename);
self.gpa.free(c.hash);
}
self.gpa.free(e.view.subs);
self.gpa.free(e.key);
self.gpa.destroy(e);
}
/// Deep-copy one resolved view into memo-owned memory and index it. Every
/// borrowed byte is duplicated: the inner resolver frees its sub-manifest
/// buffers as soon as the current flatten returns.
///
/// Partial-failure-safe: the entry is built complete, with counts tracking
/// exactly what has been allocated, so an OOM part-way frees precisely what
/// was taken and leaves the memo unchanged rather than half-populated.
fn copy(
self: *SubManifestMemo,
hash: []const u8,
view: artifact.SubManifestView,
) error{OutOfMemory}!artifact.SubManifestView {
const e = try self.gpa.create(Entry);
e.* = .{ .key = &.{}, .view = .{ .files = &.{}, .subs = &.{} }, .bytes = 0 };
// From here every failure path goes through `destroy`, which frees only
// the slices already installed on `e` — hence the empty initialisation
// above and the incremental installs below.
errdefer self.destroy(e);
e.key = try self.gpa.dupe(u8, hash);
var bytes = hash.len;
const files = try self.gpa.alloc(artifact.FCard, view.files.len);
@memset(files, .{ .filename = &.{}, .hash = null, .perm = null, .old_name = null, .mode = .regular });
e.view.files = files;
for (view.files, files) |src, *dst| {
dst.filename = try self.gpa.dupe(u8, src.filename);
dst.hash = if (src.hash) |h| try self.gpa.dupe(u8, h) else null;
dst.perm = if (src.perm) |p| try self.gpa.dupe(u8, p) else null;
dst.old_name = if (src.old_name) |o| try self.gpa.dupe(u8, o) else null;
dst.mode = src.mode;
bytes += dst.filename.len;
if (dst.hash) |h| bytes += h.len;
if (dst.perm) |p| bytes += p.len;
if (dst.old_name) |o| bytes += o.len;
}
const subs = try self.gpa.alloc(artifact.SCard, view.subs.len);
@memset(subs, .{ .filename = &.{}, .hash = &.{} });
e.view.subs = subs;
for (view.subs, subs) |src, *dst| {
dst.filename = try self.gpa.dupe(u8, src.filename);
dst.hash = try self.gpa.dupe(u8, src.hash);
bytes += dst.filename.len + dst.hash.len;
}
e.bytes = bytes;
try self.entries.put(self.gpa, e.key, e);
self.link(e);
self.retained += bytes;
return e.view;
}
};
// ---------------------------------------------------------------------------
// 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.2: activeTagValue returns a live tag value; null when the name was never interned" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rid = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
// A control artifact singleton-overrides the check-in's displayed comment
// (the exact shape `zit amend --comment` mints).
_ = try rs.ingestControlTags(h_b, 2, &.{
.{ .type = .singleton, .name = "comment", .target = h_a, .value = "hello" },
});
try t.expectEqualStrings("hello", rs.activeTagValue(rid, "comment").?);
// A name never interned in this view has no id and no rows ⇒ null.
try t.expect(rs.activeTagValue(rid, "nonesuch") == null);
// A cancel row is inactive (Section 5.1) ⇒ null, not the stale value.
_ = try rs.ingestControlTags(h_c, 3, &.{
.{ .type = .cancel, .name = "comment", .target = h_a, .value = null },
});
try t.expect(rs.activeTagValue(rid, "comment") == null);
}
test "repostate §5.3: activeTagValue reflects latest-mtime supersede (last-wins)" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rid = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
// Two controls override the same tag; the greater-mtime write wins (Section
// 5.3), regardless of ingest order — ingest the later one first.
_ = try rs.ingestControlTags(h_c, 9, &.{
.{ .type = .singleton, .name = "comment", .target = h_a, .value = "new" },
});
_ = try rs.ingestControlTags(h_b, 4, &.{
.{ .type = .singleton, .name = "comment", .target = h_a, .value = "old" },
});
try t.expectEqualStrings("new", rs.activeTagValue(rid, "comment").?);
}
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 §8.3: stored sym- selector resolves directly" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rid = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "sym-heads/main", .target = null, .value = null },
} });
try t.expectEqual(rid, try rs.resolve("sym-heads/main", .checkin));
}
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));
}
}
}
test "repostate §2/§8.3: checkinsByMtime orders check-ins by event.mtime descending" {
// rs-2-mtime-orders-checkins, rs-2-ordering-on-event-mtime, rs-8-3-7, B-timeline-2:
// §2/§8.3 item 7 make event.mtime the ordering clock; the listing is most
// recent first, independent of crosslink (insertion) order.
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 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 1 });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 2 });
const order = try rs.checkinsByMtime(t.allocator);
defer t.allocator.free(order);
// mtimes 3 > 2 > 1 ⇒ ra, rc, rb, regardless of the 3,1,2 arrival order.
try t.expectEqualSlices(Rid, &.{ ra, rc, rb }, order);
}
test "repostate §2: checkinsByMtime breaks exact-mtime ties by ascending full hash" {
// B-timeline-3: equal event.mtime ⇒ the total order falls back to ascending
// full artifact hash, making the enumeration deterministic. h_a ("a"*64) sorts
// before h_b ("b"*64), so ra precedes rb even though rb was crosslinked first.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 5 });
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5 });
const order = try rs.checkinsByMtime(t.allocator);
defer t.allocator.free(order);
try t.expect(std.mem.order(u8, h_a, h_b) == .lt); // the tiebreak's premise
try t.expectEqualSlices(Rid, &.{ ra, rb }, order);
}
test "repostate §3.2: a merge check-in is distinguished from a primary-only one" {
// rs-2-primary-parent-def, rs-2-merge-parent-def,
// rs-3-2-primary-indicator-first-hash, rs-3-2-mainline-display-must,
// rs-3-2-merge-not-mainline-predecessor, B-timeline-5: the merge marker keys on
// §3.2 parentage — a merge child carries >=1 merge parent (parentCount >= 2)
// while the first P-card hash is its single primary (mainline) parent.
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 }); // primary parent
const ro = try rs.crosslink(.{ .hash = h_b, .mtime = 2 }); // the other line
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{ h_a, h_b } });
const rsib = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{h_a} });
// §3.2: the merge child joins two lines (merge parent present); the sibling does not.
try t.expect(rs.parentCount(rc) >= 2);
try t.expectEqual(@as(usize, 1), rs.parentCount(rsib));
// §3.2: exactly one primary indicator — the FIRST P-card hash (h_a ⇒ rp), never
// the merge parent ro; the sibling's lone parent is also its primary.
try t.expectEqual(@as(?Rid, rp), rs.primaryParentOf(rc));
try t.expect(rs.primaryParentOf(rc).? != ro);
try t.expectEqual(@as(?Rid, rp), rs.primaryParentOf(rsib));
}
test "repostate merge-base: an endpoint is its own ancestor — self (B-merge-16)" {
// Review-fix #2 guard: the BFS seeds each frontier with the endpoint node
// itself before walking parentsOf, so a node is its own ancestor and
// mergeBaseOf(x, x) == x — the membership the up-to-date refusal keys on.
// ambiguities.md merge-base.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, ra, ra)); // root is its own base
try t.expectEqual(@as(?Rid, rc), try rs.mergeBaseOf(t.allocator, rc, rc)); // a deeper tip likewise
_ = rb;
}
test "repostate merge-base: an ancestor endpoint is the base (B-merge-16)" {
// y an ancestor of x ⇒ mergeBaseOf(x, y) == y (symmetric): base == other, the
// equality that fires the up-to-date refusal. Full ancestry §3.3.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, rc, ra)); // deepest ancestor
try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, ra, rc)); // symmetric
try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rc, rb)); // nearer proper ancestor
}
test "repostate isAncestorOf: mtime-tied ancestry, mtime-independently (B-merge-16)" {
// ra(100) <- rb(100) <- rc(101): rb ties ra on the ordering clock. The
// ancestry tie-break (B1) now settles that tie the only way that can be
// right — rb descends from ra, so `mergeBaseOf(rc, rb)` is rb, the ancestor
// endpoint itself. `isAncestorOf` stays the predicate the up-to-date refusal
// keys on regardless: mtime-independent, full §3.3 reachability,
// self-inclusive, and correct even where no clock can separate the nodes.
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 = 100 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 100, .parents = &.{h_a} }); // ties ra
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 101, .parents = &.{h_b} });
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 5 }); // unrelated fresh root
// CHANGED EXPECTATION (was `ra`): the old least-hash tiebreak picked ra —
// rb's own ANCESTOR — as the base of rc and rb, which is the B1 defect on
// the merge side. A descendant now beats its ancestor, so the base is rb,
// and the doc comment's `mergeBaseOf(x, y) == y whenever y is an ancestor of
// x` finally holds under an mtime tie.
try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rc, rb));
// The membership predicate is right regardless of the mtime tie.
try t.expect(try rs.isAncestorOf(t.allocator, rb, rc)); // rb is a proper ancestor of rc
try t.expect(!try rs.isAncestorOf(t.allocator, rc, rb)); // rc is not an ancestor of rb
try t.expect(try rs.isAncestorOf(t.allocator, ra, ra)); // self-membership
try t.expect(!try rs.isAncestorOf(t.allocator, rd, rc)); // unrelated node
}
test "repostate merge-base: a fork resolves to the shared ancestor (B-merge-4)" {
// Two lines off a shared trunk ra<-rb; tips rc, rd both descend from rb. The
// common ancestor with the greatest mtime is the fork point rb.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .parents = &.{h_b} });
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 6, .parents = &.{h_b} });
try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rc, rd));
try t.expectEqual(@as(?Rid, rb), try rs.mergeBaseOf(t.allocator, rd, rc)); // symmetric
_ = ra;
}
test "repostate merge-base: the greatest event.mtime among commons wins (B-merge-4)" {
// Selection is by event.mtime, not graph distance (ambiguities.md merge-base):
// the ROOT carries the greatest mtime, so it beats the nearer common ancestors
// rc and rb despite being farthest from the two tips.
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 = 100 }); // root, greatest mtime
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 20, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 30, .parents = &.{h_b} });
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 40, .parents = &.{h_c} }); // tip 1
const re = try rs.crosslink(.{ .hash = h_e, .mtime = 50, .parents = &.{h_c} }); // tip 2
// Commons {rc, rb, ra} ⇒ max mtime is ra (100).
try t.expectEqual(@as(?Rid, ra), try rs.mergeBaseOf(t.allocator, rd, re));
_ = rb;
_ = rc;
}
test "repostate merge-base: equal-mtime commons break ties by ancestry, then least hash" {
// The two halves of the B1 tie-break, on the one query where a wrong base
// silently corrupts a merge (ambiguities.md merge-base).
var ms = MemStore.init(t.allocator);
defer ms.deinit();
// Half 1 — COMPARABLE commons: ra(1) <- rx(h_b, 5) <- ry(h_c, 5), both tips
// hanging off ry. Commons {ry, rx, ra}; rx and ry tie at mtime 5.
// CHANGED EXPECTATION (was `rx`, by least hash h_b < h_c): rx is ry's own
// ancestor and ry is the actual fork point, so the old answer handed the
// three-way merge a base BEHIND the fork — it would re-apply ry's changes to
// both sides. The descendant wins.
{
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rx = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
const ry = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .parents = &.{h_b} }); // equal mtime
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 9, .parents = &.{h_c} }); // tip 1
const re = try rs.crosslink(.{ .hash = h_e, .mtime = 8, .parents = &.{h_c} }); // tip 2
try t.expectEqual(@as(?Rid, ry), try rs.mergeBaseOf(t.allocator, rd, re));
_ = ra;
_ = rx;
}
// Half 2 — INCOMPARABLE commons (unchanged behavior): rp(h_b, 5) and
// rq(h_c, 5) are concurrent children of the same root, and both tips merge
// both of them. Neither descends from the other, so the DAG cannot order
// them and the least artifact hash still decides — h_b < h_c ⇒ rp. This is
// the fallback the B1 fix deliberately preserves: hash order between TRUE
// concurrents was never the bug.
{
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rp = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
const rq = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .parents = &.{h_a} });
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 9, .parents = &.{ h_b, h_c } });
const re = try rs.crosslink(.{ .hash = h_e, .mtime = 8, .parents = &.{ h_b, h_c } });
try t.expect(std.mem.order(u8, h_b, h_c) == .lt); // the tiebreak's premise
try t.expect(!try rs.isAncestorOf(t.allocator, rp, rq)); // genuinely concurrent
try t.expect(!try rs.isAncestorOf(t.allocator, rq, rp));
try t.expectEqual(@as(?Rid, rp), try rs.mergeBaseOf(t.allocator, rd, re));
_ = ra;
}
}
test "repostate B1: one check-in named twice in a tie is not eliminated by its own copy" {
// A name can reach the same check-in through two index entries, so the same
// rid is offered twice on one selection. `offer` keeps the first as `best`
// and appends the second to `tied`; `winner` then appends `best` back, so
// `tied` holds that rid twice.
//
// Ancestor sets are self-inclusive, so each copy finds itself in the other's
// set. Dominance skipped only the same INDEX, so both copies were dominated,
// every candidate was eliminated, and the maximal element a finite DAG must
// have came up null. Dominance is about being a different check-in, not
// sitting at a different offset.
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 });
var pick = RepoState.MtimeMaxPick{ .rs = &rs };
defer pick.deinit();
try pick.offer(ra, 1);
try pick.offer(ra, 1);
try t.expectEqual(@as(?Rid, ra), try pick.winner());
// The duplicate must not shadow a real descendant either: rb descends from
// ra and ties it on the clock, so rb wins however often ra is named.
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 1, .parents = &.{h_a} });
var pick2 = RepoState.MtimeMaxPick{ .rs = &rs };
defer pick2.deinit();
try pick2.offer(ra, 1);
try pick2.offer(rb, 1);
try pick2.offer(ra, 1);
try t.expectEqual(@as(?Rid, rb), try pick2.winner());
}
test "repostate merge-base: unrelated histories yield null (B-merge-17)" {
// Disjoint chains share no common ancestor ⇒ null (the unrelated-histories
// refusal). ambiguities.md merge-base.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} }); // history 1
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3 }); // history 2, fresh root
const rd = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{h_c} });
try t.expectEqual(@as(?Rid, null), try rs.mergeBaseOf(t.allocator, rb, rd));
try t.expectEqual(@as(?Rid, null), try rs.mergeBaseOf(t.allocator, rd, rb)); // symmetric
_ = ra;
_ = rc;
}
test "repostate ancestryLinearized: identical mtime keeps parent before child (topology primary)" {
// The reviewed misattribution: a parent and child share an event mtime and the
// parent's hash sorts GREATER than the child's (h_b > h_a). The old
// mtime-then-hash order (mtime asc, hash asc) would place the child FIRST —
// inverting parent/child and charging the child a line its parent introduced.
// Topology-primary linearization keeps the parent first regardless of mtime/hash.
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_b, .mtime = 100 }); // parent, greater hash
const rc = try rs.crosslink(.{ .hash = h_a, .mtime = 100, .parents = &.{h_b} }); // child, lesser hash
try t.expect(std.mem.order(u8, h_a, h_b) == .lt); // the old-order bug's premise: child hash < parent hash
const order = try rs.ancestryLinearized(t.allocator, rc);
defer t.allocator.free(order);
// Parent before child — the invariant `attribute` relies on. (The pre-fix
// (mtime asc, hash asc) sort would have produced &.{ rc, rp }.)
try t.expectEqualSlices(Rid, &.{ rp, rc }, order);
}
test "repostate ancestryLinearized: a child with an EARLIER mtime than its parent stays after it" {
// Non-monotone clocks (skewed committer / backdated commit): the child's event
// mtime (100) is EARLIER than its parent's (200). The old mtime-ascending order
// would put the child first; topology keeps the parent first.
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 = 200 }); // parent, LATER mtime
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 100, .parents = &.{h_a} }); // child, EARLIER mtime
const order = try rs.ancestryLinearized(t.allocator, rc);
defer t.allocator.free(order);
// Parent before child despite parent.mtime > child.mtime. (Pre-fix mtime-asc
// sort would have produced &.{ rc, rp }.)
try t.expectEqualSlices(Rid, &.{ rp, rc }, order);
}
test "repostate ancestryLinearized: incomparable versions ordered deterministically, parents always first" {
// Two sibling forks off a root, joined by a merge tip. The siblings are
// topologically incomparable; the linearization is deterministic and every
// parent still precedes its child (root before both siblings, siblings before
// the merge). r(1) <- s1(10), s2(20) ; m(30) merges s1(primary), s2.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const r = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const s1 = try rs.crosslink(.{ .hash = h_b, .mtime = 10, .parents = &.{h_a} });
const s2 = try rs.crosslink(.{ .hash = h_c, .mtime = 20, .parents = &.{h_a} });
const m = try rs.crosslink(.{ .hash = h_d, .mtime = 30, .parents = &.{ h_b, h_c } });
const order = try rs.ancestryLinearized(t.allocator, m);
defer t.allocator.free(order);
// Oldest-first: root, then the incomparable siblings, then the merge tip. The
// slice is total and deterministic; parents strictly precede their children.
try t.expectEqualSlices(Rid, &.{ r, s1, s2, m }, order);
}
test "repostate §8.3 item 3: checkinsByMtime enumerates the whole check-in universe once" {
// rs-8-3-tip-global-max-mtime-ci, B-timeline-1, B-timeline-13: the query owns the
// whole-repo check-in universe (every event rid), each exactly once — no CLI-side
// walk, no duplicates, no omissions. An empty repo yields an empty slice.
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const empty = try rs.checkinsByMtime(t.allocator);
defer t.allocator.free(empty);
try t.expectEqual(@as(usize, 0), empty.len);
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
const order = try rs.checkinsByMtime(t.allocator);
defer t.allocator.free(order);
try t.expectEqual(rs.events.count(), order.len);
// Each event rid appears exactly once (count each; no phantom, no dup).
for ([_]Rid{ ra, rb, rc }) |want| {
var seen: usize = 0;
for (order) |got| {
if (got == want) seen += 1;
}
try t.expectEqual(@as(usize, 1), seen);
}
}
test "repostate: checkinsByMtime survives allocation failure without leaking" {
// A public allocating query only ever fails with OutOfMemory and frees every
// partial allocation on the way out (the errdefer/deinit discipline).
const Ctx = struct {
fn run(gpa: std.mem.Allocator) !void {
var ms = MemStore.init(gpa);
defer ms.deinit();
var rs = RepoState.init(gpa, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 3 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 1 });
const order = try rs.checkinsByMtime(gpa);
gpa.free(order);
}
};
try t.checkAllAllocationFailures(t.allocator, Ctx.run, .{});
}
// ---------------------------------------------------------------------------
// OverlayStore — a write overlay is a store in its own right, so it is tested
// as one: rid arithmetic across the base/overlay split, the phantom-upgrade
// path, and the isolation property the whole type exists for (the base is
// byte-for-byte what it was before the overlay existed).
// ---------------------------------------------------------------------------
const ov_h_a = "a" ** 64;
const ov_h_b = "b" ** 64;
const ov_h_c = "c" ** 64;
/// A §4.1 full container for `body`, owned by the caller.
fn ovContainer(gpa: std.mem.Allocator, body: []const u8) ![]u8 {
return codec.encode(gpa, body, .default);
}
test "repostate: an overlay's own additions get rids above the base and read back through the interface" {
const gpa = t.allocator;
var base = MemStore.init(gpa);
defer base.deinit();
_ = try base.store().put(ov_h_a, "alpha");
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
const s = ov.store();
const rid_b = try s.put(ov_h_b, "beta");
try t.expectEqual(@as(Rid, 2), rid_b); // base_count(1) + local 1
try t.expectEqual(@as(usize, 2), s.count());
try t.expectEqual(rid_b, s.lookup(ov_h_b).?);
try t.expectEqualStrings(ov_h_b, s.hashOf(rid_b));
try t.expectEqualStrings("beta", s.content(rid_b).?);
try t.expect(s.held(rid_b));
// A second addition keeps the offset arithmetic honest past one entry.
const rid_c = try s.intern(ov_h_c);
try t.expectEqual(@as(Rid, 3), rid_c);
try t.expectEqual(rid_c, s.lookup(ov_h_c).?);
try t.expect(s.content(rid_c) == null); // interned, still a phantom
try t.expect(!s.held(rid_c));
// The base still sees only what it always had.
try t.expectEqual(@as(usize, 1), base.store().count());
try t.expect(base.store().lookup(ov_h_b) == null);
}
test "repostate: upgrading a base phantom through an overlay leaves the base a phantom" {
const gpa = t.allocator;
var base = MemStore.init(gpa);
defer base.deinit();
const rid = try base.store().intern(ov_h_a);
_ = try base.store().put(ov_h_b, "beta"); // a second entry, so rid 1 is not the only one
{
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
const s = ov.store();
// The upgrade keeps the BASE's rid — a hash never gets a second identity.
try t.expectEqual(rid, try s.put(ov_h_a, "alpha"));
try t.expectEqual(@as(usize, 2), s.count());
try t.expectEqualStrings("alpha", s.content(rid).?);
try t.expectEqualStrings(ov_h_a, s.hashOf(rid));
try t.expect(s.held(rid));
// Retaining a wire form against the same base phantom also lands here.
const container = try ovContainer(gpa, "alpha");
defer gpa.free(container);
try s.retain(rid, .{ .full = container });
try t.expect(s.wire(rid) != null);
try t.expect(base.store().wire(rid) == null);
}
// THE ISOLATION PROPERTY: dropping the overlay restores the base exactly.
try t.expect(base.store().content(rid) == null);
try t.expect(base.store().wire(rid) == null);
try t.expect(!base.store().held(rid));
try t.expectEqual(@as(usize, 2), base.store().count());
}
test "repostate: an overlay put makes content readable even when the base holds an uninflatable form" {
const gpa = t.allocator;
var base = MemStore.init(gpa);
defer base.deinit();
// §4.1 shape (4-byte length prefix) whose payload is not a zlib stream:
// held() is true, content() is null. The base serves it verbatim, but it
// cannot answer with plaintext.
_ = try base.putWire(ov_h_a, "\x00\x00\x00\x05not-zlib");
try t.expect(base.store().held(1));
try t.expect(base.store().content(1) == null);
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
const s = ov.store();
// `put` means "this artifact's plaintext is these bytes". A store that
// silently discarded them here would leave content() null after a put.
try t.expectEqual(@as(Rid, 1), try s.put(ov_h_a, "alpha"));
try t.expectEqualStrings("alpha", s.content(1).?);
try t.expect(base.store().content(1) == null); // and the base is untouched
}
test "repostate: writtenCount counts what a round made servable, and nothing else" {
const gpa = t.allocator;
var base = MemStore.init(gpa);
defer base.deinit();
_ = try base.store().put(ov_h_a, "alpha");
const phantom_rid = try base.store().intern(ov_h_b);
// Pure read: reading every base entry writes nothing.
{
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
const s = ov.store();
_ = s.content(1);
_ = s.hashOf(phantom_rid);
_ = s.lookup(ov_h_a);
try t.expectEqual(@as(usize, 0), ov.writtenCount());
}
// Interning a hash nobody supplied bytes for is still nothing servable.
{
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
_ = try ov.store().intern(ov_h_c);
try t.expectEqual(@as(usize, 0), ov.writtenCount());
}
// A new hash with content: one.
{
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
_ = try ov.store().put(ov_h_c, "gamma");
try t.expectEqual(@as(usize, 1), ov.writtenCount());
}
// Upgrading a base phantom: one, and re-putting what the base already
// serves adds nothing.
{
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
_ = try ov.store().put(ov_h_b, "beta");
_ = try ov.store().put(ov_h_a, "alpha");
try t.expectEqual(@as(usize, 1), ov.writtenCount());
}
}
test "repostate: an overlay releases every allocation it makes under allocation failure" {
const Ctx = struct {
fn run(gpa: std.mem.Allocator) !void {
var base = MemStore.init(gpa);
defer base.deinit();
_ = try base.store().put(ov_h_a, "alpha");
_ = try base.store().intern(ov_h_b);
var ov = OverlayStore.init(gpa, base.store());
defer ov.deinit();
const s = ov.store();
_ = try s.put(ov_h_b, "beta"); // upgrade a base phantom
_ = try s.put(ov_h_c, "gamma"); // add a new hash
_ = ov.writtenCount();
}
};
try t.checkAllAllocationFailures(t.allocator, Ctx.run, .{});
}
test "repostate: releasePlaintext drops inflated bytes and keeps the containers that produced them" {
const gpa = t.allocator;
var ms = MemStore.init(gpa);
defer ms.deinit();
const container = try ovContainer(gpa, "alpha");
defer gpa.free(container);
_ = try ms.putWire(ov_h_a, container);
_ = try ms.store().put(ov_h_b, "beta"); // no container: bytes are the only copy
try t.expectEqual(@as(usize, 0), ms.plaintextBytesHeld() - "beta".len);
try t.expectEqualStrings("alpha", ms.store().content(1).?);
try t.expectEqual(@as(usize, 5), ms.inflated_bytes);
try t.expectEqual(@as(usize, 9), ms.plaintextBytesHeld());
ms.releasePlaintext();
try t.expectEqual(@as(usize, 4), ms.plaintextBytesHeld()); // only the container-less entry
try t.expectEqualStrings("beta", ms.store().content(2).?);
// The wire-backed entry still answers, by inflating again.
try t.expectEqualStrings("alpha", ms.store().content(1).?);
try t.expectEqual(@as(usize, 10), ms.inflated_bytes); // monotonic: work counted twice
}
// ---------------------------------------------------------------------------
// Tests — draft-fossil-submanifests-00 §7/§9.
// Expected values come from draft-fossil-submanifests-00 only.
// ---------------------------------------------------------------------------
/// A 64-hex synthetic artifact name built from one letter, so a test tree reads
/// as `sm('r')`, `sm('1')` rather than as sixty-four repeated characters.
fn sm(c: u8) *const [64]u8 {
return switch (c) {
'r' => "2" ** 64,
'1' => "3" ** 64,
'2' => "4" ** 64,
'3' => "5" ** 64,
'4' => "6" ** 64,
else => unreachable,
};
}
test "submanifests §9.2: a SUBMANIFEST is never re-selected by a negative-space sweep" {
// §9.2: "An implementation that discovers crosslink work by negative space
// ... MUST exclude SUBMANIFEST artifacts from the sweep, or record an
// explicit completion marker for them; otherwise it re-selects and
// re-parses them on every pass, forever."
try t.expectEqual(SweepDisposition.complete_on_arrival, sweepDisposition(.submanifest));
// §9.1: "Required-card logic ... MUST treat SUBMANIFEST (like CLUSTER) as
// an explicit exception" — CLUSTER is the type §9.2's rule is modelled on.
try t.expectEqual(SweepDisposition.complete_on_arrival, sweepDisposition(.cluster));
// The two types that DO produce a derived row keep producing one: §9.2
// narrows the sweep, it does not widen it.
try t.expectEqual(SweepDisposition.crosslink, sweepDisposition(.manifest));
try t.expectEqual(SweepDisposition.crosslink, sweepDisposition(.control));
}
test "submanifests §7.1: a missing S reference creates a phantom, a present one does not" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
_ = try ms.store().put(sm('1'), "leaf-one");
var td = TreeDeferrals.init(t.allocator, ms.store());
defer td.deinit();
// §7.1: "Storing a structural artifact that carries S cards whose
// referenced sub-manifests are absent MUST create a phantom for each
// missing reference."
const missing = try td.phantomize(&.{ sm('1'), sm('2'), sm('3') });
try t.expectEqual(@as(usize, 2), missing);
try t.expect(ms.store().lookup(sm('2')) != null); // interned as a phantom
try t.expect(!ms.store().held(ms.store().lookup(sm('2')).?));
try t.expect(ms.store().held(ms.store().lookup(sm('1')).?)); // untouched
// Idempotent: re-registering the same run mints nothing new.
const before = ms.store().count();
try t.expectEqual(@as(usize, 2), try td.phantomize(&.{ sm('1'), sm('2'), sm('3') }));
try t.expectEqual(before, ms.store().count());
}
test "submanifests §7.3/§9.4: a deferred S edge is idempotent and retried on arrival" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var td = TreeDeferrals.init(t.allocator, ms.store());
defer td.deinit();
// §7.3: "record the gap keyed by dependent and missing hash, idempotently,
// and retry on arrival."
try td.deferProcessing(sm('r'), sm('1'));
try td.deferProcessing(sm('r'), sm('1')); // idempotent
try td.deferProcessing(sm('r'), sm('2'));
try t.expectEqual(@as(usize, 2), td.gapCount());
try t.expectEqual(@as(usize, 1), td.deferredCount());
try t.expect(td.isDeferred(sm('r')));
var retry: std.ArrayListUnmanaged(Rid) = .empty;
defer retry.deinit(t.allocator);
// §9.4: "its dephantomization path MUST traverse that record" — the root
// manifest is rediscovered when the sub-manifest it waited on arrives.
try td.onArrival(sm('1'), &retry);
try t.expectEqual(@as(usize, 1), retry.items.len);
try t.expectEqual(ms.store().lookup(sm('r')).?, retry.items[0]);
// The edge is consumed: a second arrival of the same hash retries nothing.
retry.clearRetainingCapacity();
try td.onArrival(sm('1'), &retry);
try t.expectEqual(@as(usize, 0), retry.items.len);
// The other edge survives — a dependent stays deferred while ANY gap holds.
try t.expect(td.isDeferred(sm('r')));
try td.onArrival(sm('2'), &retry);
try t.expectEqual(@as(usize, 1), retry.items.len);
try t.expectEqual(@as(usize, 0), td.gapCount());
try t.expect(!td.isDeferred(sm('r')));
}
test "submanifests §9.4: an arrival that resolves no gap retries nothing" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var td = TreeDeferrals.init(t.allocator, ms.store());
defer td.deinit();
var retry: std.ArrayListUnmanaged(Rid) = .empty;
defer retry.deinit(t.allocator);
try td.onArrival(sm('4'), &retry);
try t.expectEqual(@as(usize, 0), retry.items.len);
// A bare arrival must not intern the hash: §9.4 is a lookup over recorded
// edges, never a phantom mint (Sync §3.3).
try t.expect(ms.store().lookup(sm('4')) == null);
}
test "submanifests §7.1: the S-bearing pre-filter admits every S run and rejects a flat manifest" {
try t.expect(sBearingCandidate("S name 0123\nZ x\n"));
try t.expect(sBearingCandidate("C msg\nS name 0123\nZ x\n"));
try t.expect(!sBearingCandidate("C msg\nF a 0123\nZ x\n"));
try t.expect(!sBearingCandidate("")); // no cards at all
// The filter is allowed false positives (it is a filter, not a parser) but
// never a false NEGATIVE: a run whose S card opens the artifact is admitted.
try t.expect(sBearingCandidate("S a 1\n"));
// A card letter that merely starts with S is not an S card (arity token).
try t.expect(!sBearingCandidate("SOMETHING\n"));
}
test "submanifests §7.1: the shared extractor collects every S reference, validate-then-apply" {
var refs: std.ArrayListUnmanaged([]const u8) = .empty;
defer refs.deinit(t.allocator);
const tree = "C msg\nS a.txt " ++ ("1" ** 64) ++ "\nS m.txt " ++ ("2" ** 64) ++ "\nU u\n";
try t.expect(try collectSubManifestRefs(t.allocator, tree, &refs));
try t.expectEqual(@as(usize, 2), refs.items.len);
try t.expectEqualStrings("1" ** 64, refs.items[0]);
try t.expectEqualStrings("2" ** 64, refs.items[1]);
// An artifact predating this draft appends nothing and is not a failure:
// §7.1's duty is empty for it, which is the backwards-compatibility
// guarantee stated as code.
refs.clearRetainingCapacity();
try t.expect(try collectSubManifestRefs(t.allocator, "C msg\nF a 0123\nZ x\n", &refs));
try t.expectEqual(@as(usize, 0), refs.items.len);
// Validate-then-apply: a malformed S card (a third token, §3.2) voids the
// WHOLE run — a half-read artifact never leaves a half-minted phantom set.
refs.clearRetainingCapacity();
const half = "S a.txt " ++ ("1" ** 64) ++ "\nS m.txt " ++ ("2" ** 64) ++ " extra\n";
try t.expect(!try collectSubManifestRefs(t.allocator, half, &refs));
try t.expectEqual(@as(usize, 0), refs.items.len);
// A trailing line with no LF is not a card sequence at all.
refs.clearRetainingCapacity();
try t.expect(!try collectSubManifestRefs(t.allocator, "S a.txt " ++ ("1" ** 64), &refs));
try t.expectEqual(@as(usize, 0), refs.items.len);
}
test "submanifests §7.1: the extractor appends to a caller's existing run and rewinds only its own" {
var refs: std.ArrayListUnmanaged([]const u8) = .empty;
defer refs.deinit(t.allocator);
try refs.append(t.allocator, "pre-existing");
const bad = "S a.txt " ++ ("1" ** 64) ++ "\nS m.txt zz\n"; // §3.5: `zz` is not a hash
try t.expect(!try collectSubManifestRefs(t.allocator, bad, &refs));
try t.expectEqual(@as(usize, 1), refs.items.len); // the caller's own entry survives
try t.expectEqualStrings("pre-existing", refs.items[0]);
}
test "submanifests §7.4: the memo parses each distinct sub-manifest once" {
const leaf_a = artifact.SubManifestView{ .files = &.{}, .subs = &.{} };
var counting = CountingResolver{ .view = leaf_a };
var memo = SubManifestMemo.init(t.allocator, counting.seam());
defer memo.deinit();
const r = memo.resolver();
// §7.4: "cache per-sub-manifest enumeration results keyed by artifact
// name ... a memoizing rebuild parses each distinct sub-manifest once".
_ = r.resolveFn(r.ctx, sm('1'));
_ = r.resolveFn(r.ctx, sm('1'));
_ = r.resolveFn(r.ctx, sm('2'));
_ = r.resolveFn(r.ctx, sm('1'));
try t.expectEqual(@as(usize, 2), memo.misses); // two DISTINCT names parsed
try t.expectEqual(@as(usize, 2), memo.hits);
try t.expectEqual(@as(usize, 2), counting.calls); // the inner seam saw two
}
test "submanifests §7.4: over budget, the memo evicts by recency and keeps what is hot" {
// Each view carries one F card, so an entry costs a knowable number of
// bytes and a budget can be set to hold a specific number of them.
const card = [_]artifact.FCard{.{ .filename = "f", .hash = "9" ** 64, .perm = null, .old_name = null, .mode = .regular }};
var counting = CountingResolver{ .view = .{ .files = &card, .subs = &.{} } };
var memo = SubManifestMemo.init(t.allocator, counting.seam());
defer memo.deinit();
const r = memo.resolver();
_ = r.resolveFn(r.ctx, sm('1'));
_ = r.resolveFn(r.ctx, sm('2'));
_ = r.resolveFn(r.ctx, sm('3'));
const per_entry = memo.retained / 3;
try t.expectEqual(@as(usize, 3), memo.entries.count());
// Touch '1' so it is the most recently used, leaving '2' coldest. Insertion
// order alone would drop '1'; recency must drop '2'. That difference is the
// whole change -- the previous memo froze on what arrived FIRST.
try t.expectEqual(@as(usize, 0), memo.hits);
_ = r.resolveFn(r.ctx, sm('1'));
try t.expectEqual(@as(usize, 1), memo.hits);
// Trim to two entries' worth. Eviction happens only here, never in resolve.
memo.budget = per_entry * 2;
memo.beginWalk(counting.seam());
try t.expectEqual(@as(usize, 1), memo.evicted);
try t.expectEqual(@as(usize, 2), memo.entries.count());
try t.expect(memo.retained <= memo.budget);
try t.expect(memo.entries.contains(sm('1'))); // touched, so kept
try t.expect(memo.entries.contains(sm('3')));
try t.expect(!memo.entries.contains(sm('2'))); // coldest, so dropped
// An evicted name is a MISS again, not a stale hit: eviction unindexed it
// and freed it, and the answer is re-derived from the inner seam.
const before = counting.calls;
_ = r.resolveFn(r.ctx, sm('2'));
try t.expectEqual(before + 1, counting.calls);
}
test "submanifests §7.4: a walk's own views are never evicted mid-walk" {
// `artifact.TreeWalk` keeps one frame per open level, each borrowing the
// view that resolved it, so freeing an entry inside `resolve` would pull
// memory out from under a frame still being read. Eviction is therefore
// confined to `beginWalk`; this pins that, since a future "evict as we go"
// optimisation would be a use-after-free rather than a slowdown.
const card = [_]artifact.FCard{.{ .filename = "f", .hash = "9" ** 64, .perm = null, .old_name = null, .mode = .regular }};
var counting = CountingResolver{ .view = .{ .files = &card, .subs = &.{} } };
var memo = SubManifestMemo.init(t.allocator, counting.seam());
defer memo.deinit();
memo.budget = 1; // absurdly small: every insert is already over budget
const r = memo.resolver();
const first = r.resolveFn(r.ctx, sm('1')).?;
_ = r.resolveFn(r.ctx, sm('2'));
_ = r.resolveFn(r.ctx, sm('3'));
// Nothing was dropped despite being far over budget, and the view handed
// out first is still readable -- exactly the guarantee a live frame needs.
try t.expectEqual(@as(usize, 0), memo.evicted);
try t.expectEqual(@as(usize, 3), memo.entries.count());
try t.expectEqualStrings("f", first.files[0].filename);
}
test "submanifests §7.4: an unresolvable name is never cached" {
var counting = CountingResolver{ .view = null };
var memo = SubManifestMemo.init(t.allocator, counting.seam());
defer memo.deinit();
const r = memo.resolver();
try t.expect(r.resolveFn(r.ctx, sm('1')) == null);
// A negative answer is a statement about the store at one instant — the
// sub-manifest arrives later (§7.1) — so it MUST NOT be memoized. Only the
// content-addressed positive answer is immutable.
counting.view = artifact.SubManifestView{ .files = &.{}, .subs = &.{} };
try t.expect(r.resolveFn(r.ctx, sm('1')) != null);
try t.expectEqual(@as(usize, 2), counting.calls);
}
/// A `SubResolver` whose answer BORROWS a caller-owned scratch buffer — the
/// exact lifetime the real inner seam has: `TreeStore`'s resolver hands back a
/// view into pages `TreeStore.deinit` frees the moment one flatten returns, and
/// `Repository.sub_memo` outlives many such flattens. Rewriting the scratch
/// between calls is the deterministic, in-bounds stand-in for that free.
const EphemeralResolver = struct {
/// Backs the returned view's filename bytes. Caller-owned, caller-rewritten.
scratch: []u8,
files: [1]artifact.FCard = undefined,
subs: [1]artifact.SCard = undefined,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
_ = hash;
const self: *EphemeralResolver = @ptrCast(@alignCast(ctx));
self.files[0] = .{
.filename = self.scratch,
.hash = null,
.perm = null,
.old_name = null,
.mode = .regular,
};
self.subs[0] = .{ .filename = self.scratch, .hash = sm('4') };
return .{ .files = self.files[0..1], .subs = self.subs[0..1] };
}
fn seam(self: *EphemeralResolver) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = EphemeralResolver.resolve };
}
};
test "submanifests §7.4: a memo HIT answers from the memo's own copy, never the inner seam's freed pages" {
// The deep copy in `SubManifestMemo.copy` is a LIFETIME GUARD, not an
// optimization: the inner seam's buffers die with the flatten that produced
// them, while the memo spans a whole rebuild (`Repository.sub_memo` is
// repository-lifetime, per §7.4's "unchanged subtrees are shared by hash
// ACROSS CHECK-INS"). A memo that cached the borrowed view would hand the
// second check-in a view into freed pages — a use-after-free that reads as
// a wrong file set, not a crash. This test fails the moment `resolve`
// returns/caches `view` instead of `copied`.
var scratch = "alpha.txt".*;
var inner = EphemeralResolver{ .scratch = &scratch };
var memo = SubManifestMemo.init(t.allocator, inner.seam());
defer memo.deinit();
const r = memo.resolver();
const first = r.resolveFn(r.ctx, sm('1')).?;
try t.expectEqualStrings("alpha.txt", first.files[0].filename);
try t.expectEqual(@as(usize, 1), memo.misses);
try t.expect(!memo.degraded); // the copy is what is under test; a degraded memo proves nothing
// The flatten ended: its pages are gone. Rewriting in place is the
// in-bounds, deterministic form of that — a real free would be UB the test
// could not assert on.
@memcpy(&scratch, "ZZZZZ.ZZZ");
const second = r.resolveFn(r.ctx, sm('1')).?;
try t.expectEqual(@as(usize, 1), memo.hits);
try t.expectEqual(@as(usize, 1), memo.misses); // still a HIT, not a re-parse
try t.expectEqualStrings("alpha.txt", second.files[0].filename);
try t.expectEqualStrings("alpha.txt", second.subs[0].filename);
// And the first answer — already handed to a caller — was equally owned.
try t.expectEqualStrings("alpha.txt", first.files[0].filename);
}
/// A `SubResolver` that counts inner calls and hands back one fixed answer, so
/// the memo's parse-count reduction (§7.4) is observable without a store.
const CountingResolver = struct {
view: ?artifact.SubManifestView,
calls: usize = 0,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
_ = hash;
const self: *CountingResolver = @ptrCast(@alignCast(ctx));
self.calls += 1;
return self.view;
}
fn seam(self: *CountingResolver) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = CountingResolver.resolve };
}
};