//! Repository State — draft-fossil-repo-state-00.
//!
//! Repository state is derived, not stored: branches, tags, leaves, closed
//! markers, and the current-trunk check-in are computed from the crosslinked
//! set of artifacts. This module owns that derivation over the parent DAG and
//! the tag records defined by the Artifact Format.
//!
//! Input is a `Record` — one check-in's linkage/tag facts — rather than raw
//! manifest bytes; a thin manifest-to-Record adapter arrives with manifest
//! assembly. Artifact identity (hash-to-rid, phantoms) lives behind the
//! `ArtifactStore` boundary so tests and the simulation harness can inject
//! an in-memory store. Nothing here touches ambient time, randomness, the
//! filesystem, or the network.
const std = @import("std");
/// A stored artifact's local integer identifier (Section 2). Local to a
/// repository; not part of the artifact model and not synchronised.
pub const Rid = u64;
/// A check-in's modification time (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 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,
};
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);
}
};
/// In-memory `ArtifactStore`: rids are assigned densely in intern order
/// (index + 1, so rid 0 stays invalid), and a phantom is an entry whose
/// bytes are still null.
pub const MemStore = struct {
gpa: std.mem.Allocator,
by_hash: std.StringHashMapUnmanaged(Rid) = .empty,
entries: std.ArrayList(Entry) = .empty,
const Entry = struct {
hash: []u8,
bytes: ?[]u8,
};
pub fn init(gpa: std.mem.Allocator) MemStore {
return .{ .gpa = gpa };
}
pub fn deinit(self: *MemStore) void {
for (self.entries.items) |entry| {
self.gpa.free(entry.hash);
if (entry.bytes) |bytes| self.gpa.free(bytes);
}
self.entries.deinit(self.gpa);
self.by_hash.deinit(self.gpa);
self.* = undefined;
}
/// The type-erased store interface over this instance.
pub fn store(self: *MemStore) ArtifactStore {
return .{ .context = self, .vtable = &vtable };
}
const vtable = ArtifactStore.VTable{
.intern = internImpl,
.put = putImpl,
.content = contentImpl,
.hashOf = hashOfImpl,
.lookup = lookupImpl,
};
fn internImpl(context: *anyopaque, hash: []const u8) error{OutOfMemory}!Rid {
const self: *MemStore = @ptrCast(@alignCast(context));
std.debug.assert(hash.len != 0);
if (self.by_hash.get(hash)) |rid| return rid;
// New hash: create a phantom placeholder (Section 4.2 step 1).
// Capacity is reserved before the map insert so a failure leaves no
// partial entry behind.
try self.entries.ensureUnusedCapacity(self.gpa, 1);
const owned = try self.gpa.dupe(u8, hash);
errdefer self.gpa.free(owned);
const rid: Rid = self.entries.items.len + 1;
try self.by_hash.put(self.gpa, owned, rid);
self.entries.appendAssumeCapacity(.{ .hash = owned, .bytes = null });
return rid;
}
fn putImpl(context: *anyopaque, hash: []const u8, content_bytes: []const u8) error{OutOfMemory}!Rid {
const self: *MemStore = @ptrCast(@alignCast(context));
const rid = try internImpl(context, hash);
const entry = self.entryOf(rid);
if (entry.bytes) |existing| {
// Content is addressed by hash: a repeat put carries identical
// bytes, so upgrading twice is a no-op.
std.debug.assert(std.mem.eql(u8, existing, content_bytes));
} else {
entry.bytes = try self.gpa.dupe(u8, content_bytes);
}
return rid;
}
fn contentImpl(context: *anyopaque, rid: Rid) ?[]const u8 {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entryOf(rid).bytes;
}
fn hashOfImpl(context: *anyopaque, rid: Rid) []const u8 {
const self: *MemStore = @ptrCast(@alignCast(context));
return self.entryOf(rid).hash;
}
fn 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 entryOf(self: *MemStore, rid: Rid) *Entry {
std.debug.assert(rid >= 1 and rid <= self.entries.items.len);
return &self.entries.items[@intCast(rid - 1)];
}
};
/// The derived repository state: the check-in DAG (Section 3) and the leaf
/// table (Section 7), maintained by the crosslink procedure (Section 4.2).
/// Tag cross-references, branch membership, and name resolution build on
/// this next.
pub const RepoState = struct {
gpa: std.mem.Allocator,
store: ArtifactStore,
/// One row per crosslinked check-in: rid to event mtime. Presence here
/// is the Section 4.2 step 5 idempotency guard, and its key set is the
/// leaf-candidate set (Section 7.3: every check-in, phantoms excluded).
events: std.AutoArrayHashMapUnmanaged(Rid, Mtime) = .empty,
/// Parent linkage rows, unique per (parent, child) pair (Section 3.1).
plinks: std.AutoArrayHashMapUnmanaged(PlinkKey, PlinkRow) = .empty,
/// The precomputed leaf table (Section 7.1): membership only, no
/// open/closed metadata of its own.
leaf_table: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
/// Deferred leaf rechecks (Section 7.3), applied as a batch before the
/// table is considered consistent.
pending_leaf: std.AutoArrayHashMapUnmanaged(Rid, void) = .empty,
/// Tag cross-reference table (Section 5.2): at most one live row per
/// (rid, tag) pair, enforced by keying the map on that pair directly.
tagxref: std.AutoHashMapUnmanaged(TagKey, Xref) = .empty,
/// User tag names interned to ids 10 and up (Section 2 reserves 8 and
/// 9). Owns the duplicated name bytes.
tag_names: std.StringHashMapUnmanaged(TagId) = .empty,
next_tag: TagId = first_user_tag,
const PlinkKey = struct {
parent: Rid,
child: Rid,
};
const PlinkRow = struct {
/// Set on exactly the row for the first parent listed (Section 3.2).
is_primary: bool,
/// The child check-in's modification time (Section 3.1).
mtime: Mtime,
/// Delta-manifest baseline id (Section 3.1); resolved once the
/// manifest adapter supplies B-card linkage.
baseline: Rid,
};
/// Interned tag identifier (Section 2): a fixed small integer per name,
/// with 8 ("branch") and 9 ("closed") reserved and every other name
/// interned starting at 10.
const TagId = u32;
const branch_tag_id: TagId = 8;
const closed_tag_id: TagId = 9;
const first_user_tag: TagId = 10;
const default_branch = "trunk";
const TagKey = struct {
rid: Rid,
tag: TagId,
};
/// One tagxref row (Section 5.2).
const Xref = struct {
tagtype: TagType,
/// The artifact whose T-card directly applied the tag, or zero when
/// the row instead reflects a value propagated in from an ancestor.
srcid: Rid,
/// The artifact that originally holds the propagating tag.
origid: Rid,
/// Owned duplicate of the tag's value payload, or null.
value: ?[]u8,
mtime: Mtime,
};
pub fn init(gpa: std.mem.Allocator, artifact_store: ArtifactStore) RepoState {
return .{ .gpa = gpa, .store = artifact_store };
}
pub fn deinit(self: *RepoState) void {
var xit = self.tagxref.valueIterator();
while (xit.next()) |xr| {
if (xr.value) |v| self.gpa.free(v);
}
self.tagxref.deinit(self.gpa);
var nit = self.tag_names.keyIterator();
while (nit.next()) |name| self.gpa.free(name.*);
self.tag_names.deinit(self.gpa);
self.events.deinit(self.gpa);
self.plinks.deinit(self.gpa);
self.leaf_table.deinit(self.gpa);
self.pending_leaf.deinit(self.gpa);
self.* = undefined;
}
/// Crosslink one check-in record (Section 4.2): intern its hash, derive
/// its linkage rows with parents interned to phantoms when absent
/// (step 1), route its T-cards into direct application and propagation
/// (steps 2-4), re-propagate the primary parent's tag state so a fresh
/// child inherits it (step 4a), and apply the batch of deferred leaf
/// rechecks (Section 7.3). Linkage derivation is idempotent (step 5): a
/// rid that already has an event row keeps its existing linkage, but
/// tag application and propagation still run on every call. Content
/// type is not carried by `Record` yet, so the step 2 applicability
/// gate and the step 3 cluster path are not reachable here — every
/// record is treated as control/manifest, matching the only kind this
/// layer produces. Only allocation can fail.
pub fn crosslink(self: *RepoState, rec: Record) error{OutOfMemory}!Rid {
std.debug.assert(rec.hash.len != 0);
const rid = try self.store.intern(rec.hash);
const linkage_new = !self.events.contains(rid);
if (linkage_new) {
try self.events.put(self.gpa, rid, rec.mtime);
for (rec.parents, 0..) |parent_hash, i| {
std.debug.assert(parent_hash.len != 0);
const parent = try self.store.intern(parent_hash);
// A manifest cannot name its own hash as a parent: the hash
// covers the manifest's content, including its P card.
std.debug.assert(parent != rid);
const gop = try self.plinks.getOrPut(self.gpa, .{ .parent = parent, .child = rid });
if (!gop.found_existing) {
// Section 3.1: a repeated parent reference collapses
// into the single row for the pair, first wins.
gop.value_ptr.* = .{ .is_primary = i == 0, .mtime = rec.mtime, .baseline = 0 };
}
}
// Section 7.3: a new parent-link schedules a recheck of the
// affected check-in and each of its direct parents.
try self.scheduleLeafRecheck(rid);
}
// Section 4.2 steps 1-4: apply each T-card directly, then propagate
// propagating and cancel effects from their resolved targets.
try self.applyTagOps(rid, rec.mtime, rec.tags);
// Section 4.2 step 4a: re-propagate the primary parent's tag set so
// a newly linked child inherits it regardless of arrival order.
if (self.primaryParentOf(rid)) |parent| {
try self.repropagateSet(parent);
}
try self.applyPendingLeafChecks();
const post = self.events.count();
std.debug.assert(post >= 1 and self.pending_leaf.count() == 0);
return rid;
}
/// Ingest the direct and propagated T-card effects of a control artifact.
/// The control carrier is interned solely to preserve its source identity:
/// it never gains an event, parent-link, or leaf-table entry. Scheduled
/// rechecks update only the affected, already-crosslinked check-ins.
pub fn ingestControlTags(self: *RepoState, control_hash: []const u8, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!Rid {
std.debug.assert(control_hash.len != 0);
const carrier = try self.store.intern(control_hash);
try self.applyTagOps(carrier, mtime, tags);
try self.applyPendingLeafChecks();
return carrier;
}
/// Section 4.2 steps 1-4: apply each T-card directly, then, for a
/// propagating or cancel type, walk the propagation from the resolved
/// target using the row's own post-application state (so a Section 5.3
/// skip still re-walks the winning value rather than the losing one).
fn applyTagOps(self: *RepoState, carrier: Rid, mtime: Mtime, tags: []const TagOp) error{OutOfMemory}!void {
for (tags) |op| {
const target = if (op.target) |uuid| try self.store.intern(uuid) else carrier;
try self.applyDirect(target, op, carrier, mtime);
if (op.type != .singleton) {
const tag = try self.internTag(op.name);
const stored = self.tagxref.get(.{ .rid = target, .tag = tag });
std.debug.assert(stored != null);
// Section 5.4: a singleton driving propagation is always
// downgraded to cancel first; the stored row can only be
// singleton here if a later-mtime direct write elsewhere
// won the Section 5.3 skip over this op's own effect.
const pt: TagType = if (stored.?.tagtype == .singleton) .cancel else stored.?.tagtype;
try self.propagate(target, tag, pt, stored.?.value, stored.?.origid, stored.?.mtime);
}
}
}
/// Whether `rid` is a leaf, answered from the precomputed leaf table
/// (Section 7.1).
pub fn isLeaf(self: *const RepoState, rid: Rid) bool {
return self.leaf_table.contains(rid);
}
/// Whether `rid` is an open leaf (Section 7.4): a member of the leaf
/// table that does not carry an active closed tag.
pub fn isOpenLeaf(self: *const RepoState, rid: Rid) bool {
return self.isLeaf(rid) and !self.hasActiveClosed(rid);
}
/// Iterate the leaf table (Section 7.1). Invalidated by any mutation of
/// the repository state.
pub fn leaves(self: *const RepoState) LeafIterator {
return .{ .rids = self.leaf_table.keys() };
}
/// Recompute the entire leaf table from scratch (Section 7.3 full
/// rebuild): every check-in is a candidate — roots included — and is a
/// leaf exactly when it has no same-branch child, with no
/// primary/merge filter. Whole-table cost; reserved for explicit
/// rebuilds rather than routine updates.
pub fn rebuildLeaves(self: *RepoState) error{OutOfMemory}!void {
self.leaf_table.clearRetainingCapacity();
for (self.events.keys()) |rid| {
if (!self.hasSameBranchChild(rid)) {
try self.leaf_table.put(self.gpa, rid, {});
}
}
}
/// The number of distinct parents of `child` (Section 3.3
/// child-to-parent lookup); merge parents included.
pub fn parentCount(self: *const RepoState, child: Rid) usize {
var n: usize = 0;
for (self.plinks.keys()) |key| {
if (key.child == child) n += 1;
}
return n;
}
/// The primary parent of `child` (Section 3.2), or null for a root or
/// an unknown rid. At most one linkage row per child carries the
/// primary indicator.
pub fn primaryParentOf(self: *const RepoState, child: Rid) ?Rid {
for (self.plinks.keys(), self.plinks.values()) |key, row| {
if (key.child == child and row.is_primary) return key.parent;
}
return null;
}
/// The event mtime recorded for a crosslinked check-in, or null when
/// `rid` has no event row (a phantom, or never crosslinked).
pub fn mtimeOf(self: *const RepoState, rid: Rid) ?Mtime {
return self.events.get(rid);
}
/// A check-in's branch (Section 6.1): the value of its active
/// (tagtype > 0) branch tag, or `main_branch` when no such tag is in
/// effect (Section 6.4's active-tag filter applies uniformly — a
/// cancelled branch tag falls back exactly like a missing one). The
/// default-branch name is a repository-local setting, so the caller
/// supplies it rather than this layer assuming a fixed string.
pub fn branchOf(self: *const RepoState, rid: Rid, main_branch: []const u8) []const u8 {
std.debug.assert(main_branch.len != 0);
std.debug.assert(self.events.contains(rid));
const result = self.activeBranchValue(rid) orelse main_branch;
std.debug.assert(result.len != 0);
return result;
}
/// Resolve a plain symbolic name (Section 8.1/8.2): the check-in
/// carrying an active "sym-<name>" tag with the greatest event.mtime.
/// Closed-ness and leaf-ness of a candidate are not inputs to this
/// selection (Section 8.2's two MUST-NOT clauses). Selection keys on
/// each candidate's own event.mtime, not the tagxref row's stored
/// mtime: a row a candidate inherited by propagation carries its
/// origin's application mtime, but the inheriting check-in can itself
/// be newer or older than that origin.
pub fn resolveName(self: *const RepoState, name: []const u8) error{NotFound}!Rid {
std.debug.assert(name.len != 0);
const sym_id = self.symTagId(name) orelse return error.NotFound;
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.key_ptr.tag != sym_id or entry.value_ptr.tagtype == .cancel) continue;
const rid = entry.key_ptr.rid;
// A tag row can sit on a phantom that has not itself been
// crosslinked yet (Section 4.2 step 1); it has no event.mtime
// and so is not a resolvable candidate.
const mtime = self.events.get(rid) orelse continue;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
const result = best orelse return error.NotFound;
std.debug.assert(self.events.contains(result));
return result;
}
/// Current-trunk (Section 9; Section 2 "Current-trunk"): resolve the
/// repository's configured default branch name. The procedure applies
/// uniformly — the default branch is not special-cased beyond supplying
/// its name.
pub fn currentTrunk(self: *const RepoState, main_branch: []const u8) error{NotFound}!Rid {
std.debug.assert(main_branch.len != 0);
return self.resolveName(main_branch);
}
/// A branch's open leaf (Section 9): among check-ins that (a) carry an
/// active branch tag whose value equals `branch`, (b) are members of
/// the leaf table, and (c) do not carry an active closed tag, the one
/// with the greatest event.mtime — or null when no check-in qualifies.
/// Condition (a) uses the active branch tag strictly: a tagless
/// check-in attributed to `branch` only through the Section 6.4
/// default-branch fallback does not qualify (Section 6.1: the fallback
/// "does not by itself make such a check-in ... the open leaf ... of
/// that branch").
pub fn openLeafOf(self: *const RepoState, branch: []const u8) ?Rid {
std.debug.assert(branch.len != 0);
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
const value = self.activeBranchValue(rid) orelse continue;
if (!std.mem.eql(u8, value, branch)) continue;
if (self.hasActiveClosed(rid)) continue;
std.debug.assert(self.events.contains(rid)); // leaf_table rids are always check-ins
const mtime = self.events.get(rid).?;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
if (best) |result| {
std.debug.assert(self.isLeaf(result) and !self.hasActiveClosed(result));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(result).?, branch));
}
return best;
}
/// A name-resolution request's target shape (Section 8.1). This layer
/// models only check-ins — Section 8.3's other reserved keywords
/// (current/prev/next/ckout) need an open local checkout, out of scope
/// for an artifact-derived layer — so `checkin` is the RFC's
/// unconstrained-or-"ci" request and `branch` is a "b*" request, routed
/// through the branch-walk post-process to the branch's first check-in.
pub const NameType = enum { checkin, branch };
/// One Section 6.3 derived branch-listing row. `name` borrows the
/// underlying tagxref value bytes and is valid only until the next
/// `RepoState` mutation frees or overwrites that row.
pub const BranchEntry = struct {
name: []const u8,
tip: Rid,
mtime: Mtime,
count: usize,
closed: bool,
};
const WalkVariant = enum { earliest_on_branch, first_off_branch };
const TimestampMode = enum { upper_bound, direct };
/// Section 8.3 symbolic-name resolution: dispatch the ordered forms,
/// retry once on trailing punctuation, then — for a branch-type
/// request — post-process through the branch-walk's "earliest still on
/// branch" variant (Section 8.3's final paragraph) so the result is the
/// branch's first check-in rather than wherever the tag currently
/// points. Allocation-free.
pub fn resolve(self: *const RepoState, name: []const u8, want: NameType) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
const rid = try self.dispatchWithRetry(name);
std.debug.assert(self.events.contains(rid));
const result = if (want == .branch) self.branchWalk(rid, .earliest_on_branch) else rid;
std.debug.assert(self.events.contains(result));
return result;
}
/// Section 8.3 dispatch: the ordered forms, committing to whichever
/// prefix or shape matches first. A matched prefix that fails its own
/// validation (an unknown rid:, an empty tag:, a malformed date) is
/// rejected outright rather than falling through to a later form.
fn dispatch(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
if (std.mem.startsWith(u8, name, "rid:")) return self.ridForm(name[4..]);
if (std.mem.startsWith(u8, name, "tag:")) {
const rest = name[4..];
if (rest.len == 0) return error.NotFound;
return self.resolveName(rest);
}
if (std.mem.eql(u8, name, "tip")) return self.tipForm();
if (std.mem.startsWith(u8, name, "root:")) return self.branchDerivedForm(name[5..], .first_off_branch);
if (std.mem.startsWith(u8, name, "start:")) return self.branchDerivedForm(name[6..], .earliest_on_branch);
if (std.mem.startsWith(u8, name, "merge-in:")) return self.branchDerivedForm(name[9..], .first_off_branch);
if (std.mem.startsWith(u8, name, "date:")) return self.dateForm(name[5..], .upper_bound);
if (std.mem.startsWith(u8, name, "utc:")) return self.dateForm(name[4..], .upper_bound);
if (std.mem.startsWith(u8, name, "local:")) return self.dateForm(name[6..], .direct);
if (expandTimestamp(name, .upper_bound)) |bound_ms| {
return self.dateResolve(bound_ms) orelse error.NotFound;
}
if (isHexPrefixShape(name)) {
if (try self.hashPrefixMatch(name)) |rid| return rid;
// 0 matches: not a hash after all — fall through to the plain rule.
}
return self.resolveName(name);
}
/// Section 8.3 trailing-punctuation retry, wrapping `dispatch`: on
/// `NotFound` only (an `Ambiguous` rejection is never retried), strip
/// exactly one trailing punctuation byte and recurse. Bounded: the
/// slice strictly shrinks by one byte per retry, so the recursion depth
/// cannot exceed the initial length.
fn dispatchWithRetry(self: *const RepoState, name: []const u8) error{ NotFound, Ambiguous }!Rid {
std.debug.assert(name.len >= 1);
return self.dispatch(name) catch |err| {
if (err == error.Ambiguous) return err;
if (!isPunctChar(name[name.len - 1])) return error.NotFound;
const stripped = name[0 .. name.len - 1];
std.debug.assert(stripped.len < name.len);
if (stripped.len == 0) return error.NotFound;
return self.dispatchWithRetry(stripped);
};
}
/// Section 8.3 form 1: a numeric rid, valid only when it names a
/// crosslinked check-in.
fn ridForm(self: *const RepoState, digits: []const u8) error{NotFound}!Rid {
if (digits.len == 0) return error.NotFound;
const rid = std.fmt.parseInt(Rid, digits, 10) catch return error.NotFound;
if (!self.events.contains(rid)) return error.NotFound;
return rid;
}
/// Section 8.3 form 3 (tip only; current/prev/next/ckout need an open
/// local checkout, out of scope here): the check-in with the global
/// maximum event.mtime.
fn tipForm(self: *const RepoState) error{NotFound}!Rid {
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys(), self.events.values()) |rid, mtime| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
return best orelse error.NotFound;
}
/// Section 8.3 forms 4-6: resolve `br` through the full procedure, then
/// rewrite via the Section 8.4 branch-walk.
fn branchDerivedForm(self: *const RepoState, br: []const u8, variant: WalkVariant) error{ NotFound, Ambiguous }!Rid {
if (br.len == 0) return error.NotFound;
const base = try self.resolve(br, .checkin);
return self.branchWalk(base, variant);
}
/// Section 8.4 branch-walk: from `start`, follow the primary-parent
/// chain toward the root, tracking whether each ancestor still carries
/// the same branch identity as `start` (Section 6.1's branch-of-check-
/// in notion, default-branch fallback included — the walk needs a
/// branch value at every step, and an untagged check-in's branch is
/// still well-defined via that fallback). `.earliest_on_branch` returns
/// the deepest ancestor that still carries it; `.first_off_branch`
/// returns the first ancestor that dropped it. A primary-parent chain
/// that never leaves the branch (a root-only branch) has no such node
/// for `.first_off_branch`; both variants then fall back to the
/// deepest ancestor reached (documented edge case). A primary parent
/// that is only a phantom (not yet crosslinked, Section 4.2 step 1)
/// halts the walk there too: it is not yet a resolvable check-in, so
/// its branch identity is unresolved rather than "off branch".
fn branchWalk(self: *const RepoState, start: Rid, variant: WalkVariant) Rid {
std.debug.assert(self.events.contains(start));
const target = self.branchValueOf(start);
var cur = start;
var steps: usize = 0;
const bound = self.events.count();
while (self.primaryParentOf(cur)) |parent| {
if (!self.events.contains(parent)) break;
steps += 1;
std.debug.assert(steps <= bound);
const pbranch = self.branchValueOf(parent);
if (!std.mem.eql(u8, pbranch, target)) {
if (variant == .first_off_branch) return parent;
return cur;
}
cur = parent;
}
return cur;
}
/// Section 8.3 form 7: parse `text` to an upper-bound millisecond
/// timestamp (or pass it through directly for the deprecated `local:`
/// form) and select the most recent qualifying event.
fn dateForm(self: *const RepoState, text: []const u8, mode: TimestampMode) error{NotFound}!Rid {
const bound_ms = expandTimestamp(text, mode) orelse return error.NotFound;
return self.dateResolve(bound_ms) orelse error.NotFound;
}
/// Section 8.3 form 7 selection: the check-in with the greatest
/// event.mtime not exceeding `bound_ms`, on the millisecond timeline
/// documented on `Mtime`.
fn dateResolve(self: *const RepoState, bound_ms: u64) ?Rid {
var best: ?Rid = null;
var best_mtime: Mtime = undefined;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys(), self.events.values()) |rid, mtime| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (mtime > bound_ms) continue;
if (best == null or mtime > best_mtime) {
best = rid;
best_mtime = mtime;
}
}
return best;
}
/// Section 8.3 form 8: match `prefix` against crosslinked check-ins'
/// content hashes (phantoms excluded — this layer resolves names to
/// check-ins). More than one match is rejected as ambiguous (the
/// section's "-1" sentinel does not apply to an unsigned `Rid`;
/// `error.Ambiguous` is the equivalent outcome for this layer).
fn hashPrefixMatch(self: *const RepoState, prefix: []const u8) error{Ambiguous}!?Rid {
std.debug.assert(prefix.len >= 4 and prefix.len <= 64);
var match: ?Rid = null;
var count: usize = 0;
var scanned: usize = 0;
const bound = self.events.count();
for (self.events.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
const hash = self.store.hashOf(rid);
if (hash.len >= prefix.len and std.mem.eql(u8, hash[0..prefix.len], prefix)) {
match = rid;
count += 1;
}
}
if (count > 1) return error.Ambiguous;
return match;
}
/// Section 6.3 derived branch listing: group active branch-tag rows
/// (`tagtype > 0`) by value, one entry per distinct value with its
/// greatest-mtime member as representative. Sorted by name ascending
/// (presentation order; callers wanting Section 6.3's other listed
/// orderings re-sort). Caller frees the returned slice.
pub fn branches(self: *const RepoState, gpa: std.mem.Allocator) error{OutOfMemory}![]BranchEntry {
const Group = struct { tip: Rid, mtime: Mtime, count: usize };
var groups: std.StringHashMapUnmanaged(Group) = .empty;
defer groups.deinit(gpa);
var it = self.tagxref.iterator();
var scanned: usize = 0;
const bound = self.tagxref.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (entry.key_ptr.tag != branch_tag_id or entry.value_ptr.tagtype == .cancel) continue;
const rid = entry.key_ptr.rid;
const mtime = self.events.get(rid) orelse continue; // tag on a still-phantom target
const value = entry.value_ptr.value orelse continue; // a branch tag always carries a value
const gop = try groups.getOrPut(gpa, value);
if (!gop.found_existing) {
gop.value_ptr.* = .{ .tip = rid, .mtime = mtime, .count = 1 };
} else {
gop.value_ptr.count += 1;
if (mtime > gop.value_ptr.mtime) {
gop.value_ptr.tip = rid;
gop.value_ptr.mtime = mtime;
}
// Exact-mtime tie: keep the first-seen representative —
// implementation-defined per Section 8.2's own tie note.
}
}
var out: std.ArrayList(BranchEntry) = .empty;
errdefer out.deinit(gpa);
var kit = groups.iterator();
var kscanned: usize = 0;
const kbound = groups.count();
while (kit.next()) |g| {
kscanned += 1;
std.debug.assert(kscanned <= kbound);
std.debug.assert(self.events.contains(g.value_ptr.tip));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(g.value_ptr.tip).?, g.key_ptr.*));
try out.append(gpa, .{
.name = g.key_ptr.*,
.tip = g.value_ptr.tip,
.mtime = g.value_ptr.mtime,
.count = g.value_ptr.count,
.closed = self.hasActiveClosed(g.value_ptr.tip),
});
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort(BranchEntry, slice, {}, branchNameLessThan);
return slice;
}
fn branchNameLessThan(_: void, a: BranchEntry, b: BranchEntry) bool {
return std.mem.order(u8, a.name, b.name) == .lt;
}
/// Section 7.5 ambiguity test: `rid` is a leaf and at least one *other*
/// open leaf shares its branch (the canonical leaf test's own default-
/// branch-inclusive same-branch comparison). Non-leaf short-circuits to
/// false per the section's first MUST.
pub fn isAmbiguousLeaf(self: *const RepoState, rid: Rid) bool {
if (!self.isLeaf(rid)) return false;
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |other| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (other == rid) continue;
if (!self.isOpenLeaf(other)) continue;
if (self.sameBranch(rid, other)) return true;
}
return false;
}
const MtimeDescCtx = struct {
rs: *const RepoState,
fn lessThan(ctx: MtimeDescCtx, a: Rid, b: Rid) bool {
return ctx.rs.mtimeOf(a).? > ctx.rs.mtimeOf(b).?;
}
};
/// Section 7.5 SHOULD reporting: every open leaf of `branch` (the
/// strict active-tag membership `openLeafOf` also uses — a tagless
/// check-in attributed to `branch` only through the default-branch
/// fallback does not qualify), ordered by event.mtime descending.
/// Exact-mtime ties are implementation-defined, per Section 8's own
/// tie note. Caller frees the returned slice.
pub fn openLeavesOf(self: *const RepoState, gpa: std.mem.Allocator, branch: []const u8) error{OutOfMemory}![]Rid {
std.debug.assert(branch.len != 0);
var out: std.ArrayList(Rid) = .empty;
errdefer out.deinit(gpa);
var scanned: usize = 0;
const bound = self.leaf_table.count();
for (self.leaf_table.keys()) |rid| {
scanned += 1;
std.debug.assert(scanned <= bound);
if (self.hasActiveClosed(rid)) continue;
const value = self.activeBranchValue(rid) orelse continue;
if (!std.mem.eql(u8, value, branch)) continue;
try out.append(gpa, rid);
}
const slice = try out.toOwnedSlice(gpa);
std.mem.sort(Rid, slice, MtimeDescCtx{ .rs = self }, MtimeDescCtx.lessThan);
for (slice) |rid| {
std.debug.assert(self.isOpenLeaf(rid));
std.debug.assert(std.mem.eql(u8, self.activeBranchValue(rid).?, branch));
}
return slice;
}
/// Apply every scheduled leaf recheck and clear the schedule
/// (Section 7.3 batch application). The check adds no new entries to
/// the schedule, so the batch is bounded by its size at entry.
fn applyPendingLeafChecks(self: *RepoState) error{OutOfMemory}!void {
const n = self.pending_leaf.count();
for (self.pending_leaf.keys()[0..n]) |rid| {
try self.leafCheckOne(rid);
}
std.debug.assert(self.pending_leaf.count() == n);
self.pending_leaf.clearRetainingCapacity();
}
/// Recompute leaf membership for a single rid (Section 7.3 incremental
/// check): removed when it has a same-branch child, inserted otherwise,
/// tolerating already-present. A rid without an event row is not a
/// check-in (a phantom placeholder) and never enters the table.
fn leafCheckOne(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
const is_leaf = self.events.contains(rid) and !self.hasSameBranchChild(rid);
if (is_leaf) {
try self.leaf_table.put(self.gpa, rid, {});
} else {
_ = self.leaf_table.swapRemove(rid);
}
}
/// The canonical leaf test's disqualifier (Section 7.2): any
/// parent-link naming `rid` as parent whose child is on the same
/// branch. Deliberately NOT filtered by the primary/merge distinction —
/// a same-branch child reached only via a merge edge still counts.
fn hasSameBranchChild(self: *const RepoState, rid: Rid) bool {
for (self.plinks.keys()) |key| {
if (key.parent == rid and self.sameBranch(rid, key.child)) return true;
}
return false;
}
/// Whether two check-ins are on the same branch: their branch values
/// (Section 6.1) compare equal.
fn sameBranch(self: *const RepoState, a: Rid, b: Rid) bool {
return std.mem.eql(u8, self.branchValueOf(a), self.branchValueOf(b));
}
/// The active branch-tag value for `rid` (Section 6.1), or null when no
/// active (tagtype > 0) row is present. No default here: the caller
/// decides what absence means — `branchOf`'s Section 6.4 fallback to
/// the configured main branch, versus `openLeafOf`'s strict
/// non-membership (a tagless check-in is never that branch's open leaf).
fn activeBranchValue(self: *const RepoState, rid: Rid) ?[]const u8 {
if (self.tagxref.get(.{ .rid = rid, .tag = branch_tag_id })) |xr| {
if (xr.tagtype != .cancel) {
if (xr.value) |v| return v;
}
}
return null;
}
/// The branch value of `rid` used by the same-branch leaf test
/// (Section 6.1, Section 6.4 fallback): `activeBranchValue`, or the
/// literal default branch when absent. Leaf derivation is internal
/// bookkeeping, not parameterized by the configurable main-branch
/// setting the way `branchOf` is.
fn branchValueOf(self: *const RepoState, rid: Rid) []const u8 {
return self.activeBranchValue(rid) orelse default_branch;
}
/// Whether `rid` carries an active closed tag (Section 7.4).
fn hasActiveClosed(self: *const RepoState, rid: Rid) bool {
if (self.tagxref.get(.{ .rid = rid, .tag = closed_tag_id })) |xr| {
return xr.tagtype != .cancel;
}
return false;
}
/// Intern a tag name to its id (Section 2): "branch" and "closed" are
/// the fixed ids 8 and 9; every other name is assigned the next id
/// starting at 10, first-seen order.
fn internTag(self: *RepoState, name: []const u8) error{OutOfMemory}!TagId {
std.debug.assert(name.len != 0);
if (std.mem.eql(u8, name, "branch")) return branch_tag_id;
if (std.mem.eql(u8, name, "closed")) return closed_tag_id;
if (self.tag_names.get(name)) |id| return id;
std.debug.assert(self.next_tag < std.math.maxInt(TagId));
const owned = try self.gpa.dupe(u8, name);
errdefer self.gpa.free(owned);
const id = self.next_tag;
try self.tag_names.put(self.gpa, owned, id);
self.next_tag += 1;
return id;
}
/// The interned id of "sym-<name>", or null when that name has never
/// been tagged (Section 2: symbolic names are stored internally with a
/// "sym-" prefix). A scan rather than a concatenated-key lookup: tag
/// names are owned, arbitrary-length strings with no RFC-mandated
/// bound, so building "sym-" ++ name would allocate for a read-only
/// query that has no other reason to.
fn symTagId(self: *const RepoState, name: []const u8) ?TagId {
const prefix = "sym-";
var it = self.tag_names.iterator();
var scanned: usize = 0;
const bound = self.tag_names.count();
while (it.next()) |entry| {
scanned += 1;
std.debug.assert(scanned <= bound);
const key = entry.key_ptr.*;
if (key.len != prefix.len + name.len) continue;
if (!std.mem.eql(u8, key[0..prefix.len], prefix)) continue;
if (std.mem.eql(u8, key[prefix.len..], name)) return entry.value_ptr.*;
}
return null;
}
/// Direct tag application (Section 5.3): supersede-by-mtime with a
/// >=-skip, raw type stored verbatim (srcid the carrier, origid the
/// target), value cleared to null for a cancel. The Section 5.4
/// singleton-to-cancel downgrade is a propagation-entry concern, not
/// applied to the stored row here (a stored singleton stays active).
fn applyDirect(self: *RepoState, target: Rid, op: TagOp, srcid: Rid, mtime: Mtime) error{OutOfMemory}!void {
std.debug.assert(target >= 1);
const tag = try self.internTag(op.name);
const key = TagKey{ .rid = target, .tag = tag };
const existing = self.tagxref.get(key);
if (existing) |e| {
if (e.mtime >= mtime) return; // step 1: skip
}
var new_value: ?[]u8 = null;
if (op.type != .cancel) { // step 3: cancel clears to null
if (op.value) |v| new_value = try self.gpa.dupe(u8, v);
}
errdefer if (new_value) |v| self.gpa.free(v);
// `put` assigns the value atomically with the insert/overwrite, so
// no half-initialized slot can be left behind on an OOM path — a
// manual getOrPut-then-assign would leave the newly created slot
// uninitialized if the dupe above failed after the slot existed.
try self.tagxref.put(self.gpa, key, .{ .tagtype = op.type, .srcid = srcid, .origid = target, .value = new_value, .mtime = mtime });
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
}
std.debug.assert(self.tagxref.get(key).?.mtime >= mtime);
if (tag == branch_tag_id) try self.scheduleLeafRecheck(target); // Section 7.6 b1
}
/// Propagation walk (Section 5.4) rooted at `start`, carrying `ptype`
/// (propagate or cancel only) with `value`/`origid`/`mtime` down the
/// primary-child chain until no further child qualifies. Bounded by the
/// primary-parent forest: in-degree <= 1 on primary edges means each
/// node is reachable from one walk at most once, so pops are bounded by
/// the crosslinked check-in count.
fn propagate(self: *RepoState, start: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!void {
std.debug.assert(ptype == .cancel or ptype == .propagate);
var worklist: std.ArrayList(Rid) = .empty;
defer worklist.deinit(self.gpa);
try worklist.append(self.gpa, start);
const max_pops = self.events.count() + 1;
var pops: usize = 0;
var head: usize = 0;
while (head < worklist.items.len) : (head += 1) {
const a = worklist.items[head];
pops += 1;
std.debug.assert(pops <= max_pops);
for (self.plinks.keys(), self.plinks.values()) |key, row| {
if (key.parent != a or !row.is_primary) continue; // never a merge edge
const child = key.child;
const changed = try self.propagateOne(child, tag, ptype, value, origid, mtime);
if (changed) {
try worklist.append(self.gpa, child);
if (tag == branch_tag_id) try self.scheduleLeafRecheck(child); // Section 7.6 b2
}
}
}
}
/// Apply one propagation step to `child` (Section 5.4 steps 3-4):
/// qualifies iff no existing row, or an inherited (srcid 0) row with a
/// strictly earlier mtime. A nonzero-srcid row is never overwritten
/// (Section 5.5); an equal mtime is retained. Returns whether the child
/// was updated, so the caller can enqueue it for further propagation —
/// a no-op cancel delete on an absent row still counts, matching the
/// literal "always qualifies" text of step 3.
fn propagateOne(self: *RepoState, child: Rid, tag: TagId, ptype: TagType, value: ?[]const u8, origid: Rid, mtime: Mtime) error{OutOfMemory}!bool {
const key = TagKey{ .rid = child, .tag = tag };
const existing = self.tagxref.get(key);
const qualifies = if (existing) |e| (e.srcid == 0 and e.mtime < mtime) else true;
if (!qualifies) return false;
if (existing) |e| std.debug.assert(e.srcid == 0); // never overwrite a direct row
switch (ptype) {
.propagate => {
var new_value: ?[]u8 = null;
if (value) |v| new_value = try self.gpa.dupe(u8, v);
errdefer if (new_value) |v| self.gpa.free(v);
// Store first, free the old value only once the put has
// succeeded: freeing before a fallible put would leave the
// map's still-live entry pointing at freed memory if the put
// itself failed (matches applyDirect's ordering).
try self.tagxref.put(self.gpa, key, .{ .tagtype = .propagate, .srcid = 0, .origid = origid, .value = new_value, .mtime = mtime });
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
}
},
.cancel => {
if (existing) |e| {
if (e.value) |old| self.gpa.free(old);
_ = self.tagxref.remove(key);
}
},
.singleton => unreachable, // rejected by the propagate() precondition
}
return true;
}
const SnapRow = struct { tag: TagId, xr: Xref };
/// Re-propagate `parent`'s full tag set (Section 4.2 step 4a): a
/// snapshot first, since the map mutates during the walk. Every
/// singleton row is downgraded to cancel per the Section 5.4 driving
/// rule; cancel and propagate rows pass through unchanged.
fn repropagateSet(self: *RepoState, parent: Rid) error{OutOfMemory}!void {
var rows: std.ArrayList(SnapRow) = .empty;
defer rows.deinit(self.gpa);
var it = self.tagxref.iterator();
while (it.next()) |entry| {
if (entry.key_ptr.rid == parent) {
try rows.append(self.gpa, .{ .tag = entry.key_ptr.tag, .xr = entry.value_ptr.* });
}
}
for (rows.items) |row| {
const pt: TagType = if (row.xr.tagtype == .singleton) .cancel else row.xr.tagtype;
std.debug.assert(pt == .cancel or pt == .propagate);
try self.propagate(parent, row.tag, pt, row.xr.value, row.xr.origid, row.xr.mtime);
}
}
/// Schedule an incremental leaf recheck for `rid` and each of its
/// direct parents (Section 7.3), tolerating an rid with no parents yet.
fn scheduleLeafRecheck(self: *RepoState, rid: Rid) error{OutOfMemory}!void {
try self.pending_leaf.put(self.gpa, rid, {});
for (self.plinks.keys()) |key| {
if (key.child == rid) try self.pending_leaf.put(self.gpa, key.parent, {});
}
}
};
/// Days since 1970-01-01 for a proleptic-Gregorian civil date (Howard
/// Hinnant's public-domain `days_from_civil` calendar identity — plain
/// integer math, not derived from any Fossil/libfossil source). Backs the
/// Section 8.3 form 7 date-form parser below, placing a parsed timestamp
/// and stored event.mtime values on one millisecond timeline. Inputs must
/// already be range-validated (see `parseDateTime`).
fn daysFromCivil(y_in: i64, m: u8, d: u8) i64 {
std.debug.assert(m >= 1 and m <= 12);
std.debug.assert(d >= 1 and d <= 31);
var y = y_in;
if (m <= 2) y -= 1;
const era: i64 = @divFloor(if (y >= 0) y else y - 399, 400);
const yoe: i64 = y - era * 400;
const mp: i64 = @mod(@as(i64, m) + 9, 12);
const doy: i64 = @divFloor(153 * mp + 2, 5) + @as(i64, d) - 1;
const doe: i64 = yoe * 365 + @divFloor(yoe, 4) - @divFloor(yoe, 100) + doy;
return era * 146_097 + doe - 719_468;
}
fn isLeapYear(y: i64) bool {
return @mod(y, 4) == 0 and (@mod(y, 100) != 0 or @mod(y, 400) == 0);
}
fn daysInMonth(y: i64, m: u8) u8 {
return switch (m) {
1, 3, 5, 7, 8, 10, 12 => 31,
4, 6, 9, 11 => 30,
2 => if (isLeapYear(y)) @as(u8, 29) else 28,
else => unreachable, // m range-checked by parseDateTime before this call
};
}
const DatePrecision = enum { date_only, minute, second, fraction };
const DateParts = struct {
y: u16,
mo: u8,
d: u8,
h: u8,
mi: u8,
s: u8,
/// 1-3 ASCII digits, empty below `.fraction` precision.
frac: []const u8,
precision: DatePrecision,
};
/// Fixed-field parse of a Section 8.3 form 7 timestamp:
/// `YYYY-MM-DD[ HH:MM[:SS[.f{1,3}]]]`. Never panics on malformed input
/// (fuzz-safe): every field is range-checked and a bad byte returns null
/// rather than trapping.
fn parseDateTime(text: []const u8) ?DateParts {
if (text.len < 10) return null;
const y = std.fmt.parseInt(u16, text[0..4], 10) catch return null;
if (text[4] != '-') return null;
const mo = std.fmt.parseInt(u8, text[5..7], 10) catch return null;
if (mo < 1 or mo > 12) return null;
if (text[7] != '-') return null;
const d = std.fmt.parseInt(u8, text[8..10], 10) catch return null;
if (d < 1 or d > daysInMonth(y, mo)) return null;
if (text.len == 10) return .{ .y = y, .mo = mo, .d = d, .h = 0, .mi = 0, .s = 0, .frac = &.{}, .precision = .date_only };
if (text.len < 16 or text[10] != ' ') return null;
const h = std.fmt.parseInt(u8, text[11..13], 10) catch return null;
if (h > 23) return null;
if (text[13] != ':') return null;
const mi = std.fmt.parseInt(u8, text[14..16], 10) catch return null;
if (mi > 59) return null;
if (text.len == 16) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = 0, .frac = &.{}, .precision = .minute };
if (text.len < 19 or text[16] != ':') return null;
const s = std.fmt.parseInt(u8, text[17..19], 10) catch return null;
if (s > 59) return null;
if (text.len == 19) return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = &.{}, .precision = .second };
if (text.len < 21 or text.len > 23 or text[19] != '.') return null;
const frac = text[20..];
for (frac) |c| if (!std.ascii.isDigit(c)) return null;
return .{ .y = y, .mo = mo, .d = d, .h = h, .mi = mi, .s = s, .frac = frac, .precision = .fraction };
}
/// Converts a fixed 3-ASCII-digit buffer to its numeric value (0-999).
/// Every byte must be a decimal digit: `expandTimestamp` fills `buf` only
/// from `'0'`/`'9'` padding or from `DateParts.frac`, whose bytes
/// `parseDateTime` already range-checked with `std.ascii.isDigit`.
fn digits3ToMs(buf: [3]u8) u16 {
for (buf) |c| std.debug.assert(std.ascii.isDigit(c));
return @as(u16, buf[0] - '0') * 100 + @as(u16, buf[1] - '0') * 10 + (buf[2] - '0');
}
/// Section 8.3 form 7 upper-bound / direct expansion, returning a Unix-
/// epoch millisecond bound (or null on a malformed timestamp).
/// `.upper_bound` pads an under-specified field to its latest instant per
/// the precision table (date-only -> 23:59:59.999, minute -> :59.999,
/// second -> .999; a fractional field is copied, padded to three digits
/// with trailing 9s, and advanced by one millisecond unless already .999 —
/// .1 -> .199 -> .200, .12 -> .129 -> .130, .123 -> .124, .999 stays).
/// `.direct` (the deprecated local: form) parses the literal fields with
/// no expansion — an absent field is zero and a given fraction is read at
/// face value, matching a bare julianday() parse.
fn expandTimestamp(text: []const u8, mode: RepoState.TimestampMode) ?u64 {
const parts = parseDateTime(text) orelse return null;
var h = parts.h;
var mi = parts.mi;
var s = parts.s;
var ms: u16 = 0;
switch (mode) {
.upper_bound => switch (parts.precision) {
.date_only => {
h = 23;
mi = 59;
s = 59;
ms = 999;
},
.minute => {
s = 59;
ms = 999;
},
.second => ms = 999,
.fraction => {
var buf = [3]u8{ '9', '9', '9' };
for (parts.frac, 0..) |c, i| buf[i] = c;
ms = digits3ToMs(buf);
if (ms != 999) ms += 1;
},
},
.direct => switch (parts.precision) {
.date_only, .minute, .second => {},
.fraction => {
var buf = [3]u8{ '0', '0', '0' };
for (parts.frac, 0..) |c, i| buf[i] = c;
ms = digits3ToMs(buf);
},
},
}
const days = daysFromCivil(@as(i64, parts.y), parts.mo, parts.d);
const total_ms: i64 = days * 86_400_000 +
@as(i64, h) * 3_600_000 +
@as(i64, mi) * 60_000 +
@as(i64, s) * 1_000 +
@as(i64, ms);
if (total_ms < 0) return null; // pre-epoch: outside this layer's ms timeline
return @intCast(total_ms);
}
/// Parse a direct timestamp into the repository's millisecond timeline.
/// Canonical artifact D-card datetimes use `T` as their date/time separator;
/// normalize that byte only, then reuse the Section 8.3 direct conversion.
pub fn parseMtime(timestamp: []const u8) ?Mtime {
if (timestamp.len > 10 and timestamp[10] == 'T') {
// D-cards require a full seconds field, with an optional 1-3 digit
// fractional component. The direct parser validates every other byte.
if (timestamp.len < 19 or timestamp.len > 23) return null;
var normalized: [23]u8 = undefined;
std.mem.copyForwards(u8, normalized[0..timestamp.len], timestamp);
normalized[10] = ' ';
return expandTimestamp(normalized[0..timestamp.len], .direct);
}
return expandTimestamp(timestamp, .direct);
}
/// Section 8.3 form 8 shape test: a hex string long enough to be an
/// unambiguous prefix (4 chars) and no longer than the maximum artifact-
/// hash length (64, the sha3-256 case).
fn isHexPrefixShape(name: []const u8) bool {
if (name.len < 4 or name.len > 64) return false;
for (name) |c| if (!std.ascii.isHex(c)) return false;
return true;
}
fn isPunctChar(c: u8) bool {
return std.ascii.isPunctuation(c);
}
/// Iterator over the leaf table, in table order.
pub const LeafIterator = struct {
rids: []const Rid,
index: usize = 0,
pub fn next(self: *LeafIterator) ?Rid {
if (self.index == self.rids.len) return null;
defer self.index += 1;
return self.rids[self.index];
}
};
// ---------------------------------------------------------------------------
// Tests. Expected values come from draft-fossil-repo-state-00 only.
// ---------------------------------------------------------------------------
const t = std.testing;
// 64-hex-character hashes, distinct per letter.
const h_a = "a" ** 64;
const h_b = "b" ** 64;
const h_c = "c" ** 64;
const h_d = "d" ** 64;
const h_e = "e" ** 64;
const h_f = "f" ** 64;
const h_g = "0" ** 64;
const h_h = "1" ** 64;
fn countLeaves(rs: *const RepoState) usize {
var it = rs.leaves();
var n: usize = 0;
while (it.next()) |_| n += 1;
return n;
}
/// White-box lookup of a tagxref row by tag name, for test assertions only.
fn tagRowFor(rs: *RepoState, rid: Rid, name: []const u8) error{OutOfMemory}!?RepoState.Xref {
const tag = try rs.internTag(name);
return rs.tagxref.get(.{ .rid = rid, .tag = tag });
}
test "repostate §5.3: a strictly later mtime supersedes an earlier one" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v2", xr.value.?);
try t.expectEqual(@as(Mtime, 6), xr.mtime);
}
test "repostate §5.3: a strictly earlier mtime is skipped" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v1", xr.value.?);
}
test "repostate §5.3: an equal-mtime re-application is skipped" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
// Derivation §5.3.1: ">= ... MUST be skipped"; the equal-mtime case is
// impl-defined, so our >= retains the existing (first) write.
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqualStrings("v1", xr.value.?);
}
test "repostate §5.3: a cancel application clears the value to null" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 5, .tags = &.{
.{ .type = .cancel, .name = "t1", .target = null, .value = "z" },
} });
const xr = (try tagRowFor(&rs, ra, "t1")).?;
try t.expectEqual(TagType.cancel, xr.tagtype);
try t.expect(xr.value == null);
}
test "repostate §5.3/§4.2: a singleton tag triggers no propagation walk" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "v" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
const xr = (try tagRowFor(&rs, try rs.store.intern(h_a), "t1")).?;
try t.expectEqual(TagType.singleton, xr.tagtype);
}
test "repostate §5.2: tagxref holds at most one row per (rid, tag)" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v1" },
} });
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 6, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = h_a, .value = "v2" },
} });
try t.expectEqual(@as(usize, 1), rs.tagxref.count());
try t.expectEqualStrings("v2", (try tagRowFor(&rs, ra, "t1")).?.value.?);
}
test "repostate §5.4: a propagating tag reaches primary-chain descendants" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expectEqualStrings("v", (try tagRowFor(&rs, rb, "t1")).?.value.?);
try t.expectEqualStrings("v", (try tagRowFor(&rs, rc, "t1")).?.value.?);
}
test "repostate §5.4: a propagated row carries origin value and mtime with srcid 0" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const ra = try rs.crosslink(.{ .hash = h_a, .mtime = 3, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 5, .parents = &.{h_a} });
const xr = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqual(@as(Rid, 0), xr.srcid);
try t.expectEqual(ra, xr.origid);
try t.expectEqualStrings("v", xr.value.?);
try t.expectEqual(@as(Mtime, 3), xr.mtime);
}
test "repostate §5.4: propagation does not cross a merge edge" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
_ = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} }); // primary child of A
_ = try rs.crosslink(.{ .hash = h_c, .mtime = 3 }); // unrelated root R
// M's primary parent is R; B is only a merge (non-primary) parent.
const rm = try rs.crosslink(.{ .hash = h_d, .mtime = 4, .parents = &.{ h_c, h_b } });
try t.expect((try tagRowFor(&rs, rm, "t1")) == null);
}
test "repostate §5.4: a directly-applied entry is never overwritten by propagation" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v1" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v2" },
} });
const xr = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqualStrings("v2", xr.value.?);
try t.expect(xr.srcid != 0);
}
test "repostate §5.4: an inherited entry of equal mtime is retained" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1 });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const tag = try rs.internTag("t1");
// Seed an inherited row directly (white-box): the exact tie condition
// under test is not otherwise reachable through crosslink alone.
const old_val = try t.allocator.dupe(u8, "old");
try rs.tagxref.put(t.allocator, .{ .rid = rc, .tag = tag }, .{ .tagtype = .propagate, .srcid = 0, .origid = rp, .value = old_val, .mtime = 5 });
try rs.propagate(rp, tag, .propagate, "new", rp, 5);
const xr = rs.tagxref.get(.{ .rid = rc, .tag = tag }).?;
try t.expectEqualStrings("old", xr.value.?);
}
test "repostate §5.5: a cancel tag halts propagation to descendants" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .cancel, .name = "t1", .target = null, .value = null },
} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
try t.expectEqual(TagType.cancel, (try tagRowFor(&rs, rb, "t1")).?.tagtype);
}
test "repostate §5.5: a singleton on a parent blocks propagation through it" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rb = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a}, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
} });
const rc = try rs.crosslink(.{ .hash = h_c, .mtime = 3, .parents = &.{h_b} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
const xrb = (try tagRowFor(&rs, rb, "t1")).?;
try t.expectEqual(TagType.singleton, xrb.tagtype);
try t.expectEqualStrings("w", xrb.value.?);
}
test "repostate §5.4: the propagation entry rejects a singleton, reaching descendants as cancel" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .singleton, .name = "t1", .target = null, .value = "w" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
try t.expect((try tagRowFor(&rs, rc, "t1")) == null);
}
test "repostate §4.2 step 1: a tag on an absent target attaches to its phantom and survives arrival" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = h_h, .value = "v" },
} });
const rh = try rs.store.intern(h_h);
try t.expect(!rs.isLeaf(rh)); // phantom, not a check-in
try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
const rh_again = try rs.crosslink(.{ .hash = h_h, .mtime = 2 });
try t.expectEqual(rh, rh_again);
try t.expectEqualStrings("v", (try tagRowFor(&rs, rh, "t1")).?.value.?);
try t.expect(rs.isLeaf(rh));
}
test "repostate §4.2 step 4: a new child inherits its primary parent's propagating tag" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rp = try rs.crosslink(.{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} });
const rc = try rs.crosslink(.{ .hash = h_b, .mtime = 2, .parents = &.{h_a} });
const xr = (try tagRowFor(&rs, rc, "t1")).?;
try t.expectEqualStrings("v", xr.value.?);
try t.expectEqual(@as(Rid, 0), xr.srcid);
try t.expectEqual(rp, xr.origid);
}
test "repostate §4.2 step 5: re-crosslink re-runs tag application idempotently" {
var ms = MemStore.init(t.allocator);
defer ms.deinit();
var rs = RepoState.init(t.allocator, ms.store());
defer rs.deinit();
const rec = Record{ .hash = h_a, .mtime = 1, .tags = &.{
.{ .type = .propagate, .name = "t1", .target = null, .value = "v" },
} };
const r1 = try rs.crosslink(rec);
const before = countLeaves(&rs);
const r2 = try rs.crosslink(rec);
try t.expectEqual(r1, r2);
try t.expectEqual(before, countLeaves(&rs));
try t.expectEqual(@as(usize, 1), rs.tagxref.count());
try t.expectEqualStrings("v", (try tagRowFor(&rs, r1, "t1")).?.value.?);
}
// ---------------------------------------------------------------------------
// §8 name resolution, §6.3 branch enumeration, §7.5 ambiguous-leaf reporting.
// ---------------------------------------------------------------------------
test "repostate §8.3.7: 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.7: 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.7: 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.7: 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));
}