Artifact e7e21800a151e65bd482a54696e8b9d5f1fda439757987293ec3ae3ac0af57b8:
- File
src/repostate.zig
— part of check-in
[82de6f83d0]
at
2026-08-18 00:02:46
on branch trunk
— repoimage: carry adjacency, and read it through one door (#98)
The image held mtimes, hashes, branch ids and the symbol table but not the parent/child relation, which is why every verb needing ancestry re-derived the whole log on open. Six CSR columns carry it now, both directions with the primary flag -- primary-parent selection and merge-edge skipping both read it, so an image without it answers wrongly rather than refusing.
The two backings hold the same relation in different shapes, so edgesOf hides which one a caller got, and the equivalence test compares them in order with a guard that fails when the corpus has no edges to compare.
Behaviour-neutral: no assert relaxed, no verb moved. Freeing those needs an events equivalent as well -- resolve reads self.events directly, and that table is empty on an image backing. (user: dmestas, size: 264728) [annotate] [blame] [check-ins using]
//! 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 { var it = self.edgesOf(.parents, child); var n: usize = 0; while (it.next()) |_| n += 1; // bounded by the in-degree 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 { var it = self.edgesOf(.parents, child); while (it.next()) |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: EdgeIterator, pub fn next(self: *ParentIterator) ?Rid { // Bounded by the in-degree; each step strictly advances. const e = self.edges.next() orelse return null; 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. /// One adjacency edge: the far endpoint and whether it is the §3.2 primary /// link. Named separately from the private `Edge` because it crosses the /// backing boundary — the derived tables hold `Edge`, the image holds two /// narrowed columns, and callers must not care which they got. pub const EdgeRef = struct { rid: Rid, is_primary: bool }; pub const EdgeDir = enum { parents, children }; /// A walk over one rid's edges that works on EITHER backing. /// /// This exists because the two backings store the same relation in /// different shapes: the derive holds `[]const Edge` (a `u64` rid and a /// bool, 16 bytes with padding), while the image holds narrowed `u32` rids /// beside a parallel flag column. Handing callers a slice would force one /// shape on both and re-materialize the other on every open, which is the /// cost the image exists to avoid. pub const EdgeIterator = union(enum) { derived: struct { edges: []const Edge, i: usize = 0 }, image: repoimage.Image.EdgeIterator, pub fn next(self: *EdgeIterator) ?EdgeRef { switch (self.*) { // Bounded by the in-degree; each step strictly advances. .derived => |*d| { if (d.i >= d.edges.len) return null; const e = d.edges[d.i]; d.i += 1; return .{ .rid = e.rid, .is_primary = e.is_primary }; }, .image => |*im| { const e = im.next() orelse return null; return .{ .rid = e.rid, .is_primary = e.is_primary }; }, } } }; /// `rid`'s edges in `dir`, from whichever backing this state has. The one /// door every adjacency query goes through, so a query cannot silently /// answer from an empty table on an image backing — which is how a wrong /// ancestry answer would otherwise be produced without any refusal. pub fn edgesOf(self: *const RepoState, dir: EdgeDir, rid: Rid) EdgeIterator { if (self.backing == .image) { // `.image` backing always carries an image; the optional is the // representation, not a case a query has to handle. return .{ .image = self.img.?.edgesOf(switch (dir) { .parents => .parents, .children => .children, }, rid) }; } const table = switch (dir) { .parents => &self.parents_by_child, .children => &self.children, }; const edges: []const Edge = if (table.getPtr(rid)) |list| list.items else &.{}; return .{ .derived = .{ .edges = edges } }; } pub fn parentsOf(self: *const RepoState, child: Rid) ParentIterator { return .{ .edges = self.edgesOf(.parents, child) }; } /// 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 (expandResolverTimestamp(name, .upper_bound)) |bound_ms| { return (try self.dateResolve(bound_ms)) orelse error.NotFound; } // Section 8.3 form 7 NAME:TIMESTAMP compound. Scanned colon by colon so // the split lands wherever the suffix first parses as a timestamp — // the timestamp's own colons make a fixed split point impossible. if (compoundSplit(name)) |c| { return self.dateResolveScoped(c.bound_ms, c.name); } 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. // Checked on EITHER backing since #98: the image carries adjacency, so // an invariant that used to be verifiable only after a full derive is // now verifiable on the path a warm read actually takes. if (std.debug.runtime_safety) { var kids = self.edgesOf(.children, result); while (kids.next()) |edge| { const child_mtime = self.mtimeOf(edge.rid) orelse continue; std.debug.assert(child_mtime < self.mtimeOf(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 = expandResolverTimestamp(text, mode) orelse return error.NotFound; return (try self.dateResolve(bound_ms)) orelse error.NotFound; } /// Section 8.3 form 7 NAME:TIMESTAMP selection: the greatest event.mtime /// not exceeding `bound_ms` among check-ins carrying an active sym-NAME /// tag (tagtype > 0) — `resolveName`'s tagxref scan with the mtime ceiling /// added. The memoised image cannot answer a date-scoped tag query (it /// materializes only each name's single max-mtime winner), and every /// resolving verb derives fully (cmd/checkout.zig's `.full` note), so the /// scan reads the real tables. fn dateResolveScoped(self: *const RepoState, bound_ms: u64, name: []const u8) error{ NotFound, OutOfMemory }!Rid { 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; const mtime = self.events.get(rid) orelse continue; if (mtime > bound_ms) continue; try pick.offer(rid, mtime); } const result = (try pick.winner()) orelse return error.NotFound; std.debug.assert(self.events.contains(result)); return result; } /// 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 { return self.tagNamesMatching(gpa, null); } /// The `tagNames` view restricted to one active tag type. A cancel is /// never active and is therefore not a valid filter. pub fn tagNamesOfType( self: *const RepoState, gpa: std.mem.Allocator, tagtype: TagType, ) error{OutOfMemory}![][]const u8 { std.debug.assert(tagtype != .cancel); return self.tagNamesMatching(gpa, tagtype); } fn tagNamesMatching( self: *const RepoState, gpa: std.mem.Allocator, tagtype: ?TagType, ) 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 (tagtype) |wanted| { if (entry.value_ptr.tagtype != wanted) continue; } 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 { var it = self.edgesOf(.children, rid); while (it.next()) |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); } /// Section 8.3 resolver-side timestamp expansion: admits the portable /// absolute form's `T` separator and one trailing `Z` ("a timestamp MUST use /// the absolute form YYYY-MM-DDTHH:MM:SS[.fraction]Z"), both of which the /// D-card parser rejects — which is why this normalization lives at the /// resolver seam and never inside `parseDateTime`: loosening the shared /// parser would make the artifact-format validator accept malformed D-cards. /// An omitted Z reads identically to a present one — the section leaves an /// unsuffixed timestamp to the display-time mode, and zit's is UTC-only. fn expandResolverTimestamp(text: []const u8, mode: RepoState.TimestampMode) ?u64 { var ts = text; if (ts.len >= 1 and ts[ts.len - 1] == 'Z') ts = ts[0 .. ts.len - 1]; if (ts.len > 10 and ts[10] == 'T') { if (ts.len > 23) return null; var buf: [23]u8 = undefined; std.mem.copyForwards(u8, buf[0..ts.len], ts); buf[10] = ' '; return expandTimestamp(buf[0..ts.len], mode); } return expandTimestamp(ts, mode); } /// A NAME:TIMESTAMP compound split (Section 8.3 form 7): the FIRST colon /// whose suffix parses as a timestamp splits the name — the timestamp's own /// colons rule out a fixed split point, and scanning forward keeps a name /// that itself contains colons (`a:b:2026-01-01`) resolvable. Null when no /// split yields a parseable timestamp (the name then continues down the /// dispatch order untouched). const CompoundSplit = struct { name: []const u8, bound_ms: u64 }; fn compoundSplit(name: []const u8) ?CompoundSplit { var i: usize = 1; while (i < name.len - 1) : (i += 1) { if (name[i] != ':') continue; if (expandResolverTimestamp(name[i + 1 ..], .upper_bound)) |bound_ms| { return .{ .name = name[0..i], .bound_ms = bound_ms }; } } return null; } /// 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, /// The walk generation that last touched this entry — how /// `walk_touched` counts each entry once per walk (#63). touched_gen: u64 = 0, /// 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. With `adaptive` set (the default), `beginWalk` raises it to /// headroom above the last walk's working set; a test (or an operator /// budget) that wants an exact ceiling clears `adaptive` first. budget: usize = submanifest_memo_budget, /// Adaptive trim target (#63). A fixed 64 MiB budget was tuned against /// ~2K-file corpora; on pkgsrc's ~124K-file tip each between-walk trim /// discarded most of a working set the NEXT walk — one commit's delta /// away — immediately re-resolved, and an import that should take tens /// of minutes took hours re-reading, re-inflating, and re-hashing the /// same store bytes. The budget therefore tracks `walk_touched` — the /// bytes of entries the FINISHED walk actually used, each counted once /// via its generation stamp — with 25% headroom, floored at the /// constant. Tracking `retained` instead would ratchet forever (retained /// only shrinks by the eviction it would then never trigger); touched /// bytes shrink the moment the trees do, so stale wide-era entries age /// out through the ordinary LRU trim. Memory stays bounded by the widest /// walk plus headroom — the bound mid-walk growth already accepts. adaptive: bool = true, /// The lower bound `adaptive` never trims beneath; also the whole budget /// when adaptation is off. Defaults to the tuned constant. floor: usize = submanifest_memo_budget, /// Bytes of entries touched (hit or inserted) during the current walk, /// each entry counted once (`touched_gen`). Reset at every `beginWalk`. walk_touched: usize = 0, /// The current walk's generation for `touched_gen` stamping. Starts at 1 /// so a fresh entry's default 0 always reads as untouched-this-walk. walk_gen: u64 = 1, 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; if (self.adaptive) { const last_walk_set = self.walk_touched; self.budget = @max(self.floor, last_walk_set + last_walk_set / 4); } self.walk_touched = 0; self.walk_gen += 1; 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); self.markTouched(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; }; if (self.entries.get(hash)) |entry| self.markTouched(entry); return copied; } /// Count `e` into the current walk's working set exactly once (#63): /// the generation stamp makes a hot entry contribute its bytes to /// `walk_touched` on first use per walk, however many hits follow. fn markTouched(self: *SubManifestMemo, e: *Entry) void { if (e.touched_gen == self.walk_gen) return; e.touched_gen = self.walk_gen; self.walk_touched += e.bytes; } /// 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)); } test "repostate §8.3: the portable T/Z absolute form resolves identically to the space form" { 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 12:00:00.000", .direct).?; const r9 = try rs.crosslink(.{ .hash = h_a, .mtime = day9 }); const r10 = try rs.crosslink(.{ .hash = h_b, .mtime = day10, .parents = &.{h_a} }); // The portable form ("a timestamp MUST use the absolute form // YYYY-MM-DDTHH:MM:SS[.fraction]Z") — with and without the Z, at second // precision and date-only-with-Z. try t.expectEqual(r9, try rs.resolve("2026-07-09T13:00:00Z", .checkin)); try t.expectEqual(r9, try rs.resolve("2026-07-09T13:00:00", .checkin)); try t.expectEqual(r9, try rs.resolve("date:2026-07-09T13:00:00Z", .checkin)); try t.expectEqual(r10, try rs.resolve("2026-07-10Z", .checkin)); // A bare Z or a Z in the middle is not a timestamp. try t.expectError(error.NotFound, rs.resolve("Z", .checkin)); } test "repostate §8.3: NAME:TIMESTAMP scopes candidates to the active sym-NAME tag" { var ms = MemStore.init(t.allocator); defer ms.deinit(); var rs = RepoState.init(t.allocator, ms.store()); defer rs.deinit(); const m_a = expandTimestamp("2026-07-09 12:00:00.000", .direct).?; const m_c = expandTimestamp("2026-07-10 12:00:00.000", .direct).?; const m_b = expandTimestamp("2026-07-11 12:00:00.000", .direct).?; // dev: a root carrying the propagating branch tag, and its child (which // inherits it, §4.2 step 4). main: an unrelated root, newer than dev's // root and older than dev's child. const r_a = try rs.crosslink(.{ .hash = h_a, .mtime = m_a, .tags = &.{ .{ .type = .propagate, .name = "sym-dev", .target = null, .value = null }, } }); const r_b = try rs.crosslink(.{ .hash = h_b, .mtime = m_b, .parents = &.{h_a} }); const r_c = try rs.crosslink(.{ .hash = h_c, .mtime = m_c, .tags = &.{ .{ .type = .propagate, .name = "sym-main", .target = null, .value = null }, } }); // Scoped: only check-ins on the named branch qualify, youngest <= bound. try t.expectEqual(r_a, try rs.resolve("dev:2026-07-10", .checkin)); try t.expectEqual(r_b, try rs.resolve("dev:2026-07-11", .checkin)); try t.expectEqual(r_c, try rs.resolve("main:2026-07-10", .checkin)); // The same bound unscoped picks the global youngest — the two answers // differ, which is the reason the compound form exists. try t.expectEqual(r_c, try rs.resolve("2026-07-10", .checkin)); // Before the branch existed, and a name that is no tag: NotFound. try t.expectError(error.NotFound, rs.resolve("dev:2026-07-08", .checkin)); try t.expectError(error.NotFound, rs.resolve("nosuch: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 #63: the adaptive budget tracks the touched working set — wide walks stop thrashing, narrow eras still trim" { 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(); // Walk 1: a three-entry working set against a floor sized to ONE entry — // the pkgsrc shape in miniature (budget far under the walk's tree). _ = r.resolveFn(r.ctx, sm('1')); const per_entry = memo.retained; memo.floor = per_entry; _ = r.resolveFn(r.ctx, sm('2')); _ = r.resolveFn(r.ctx, sm('3')); try t.expectEqual(@as(usize, 3), memo.entries.count()); try t.expectEqual(per_entry * 3, memo.walk_touched); // Boundary: the OLD fixed budget would evict two of three here and the // identical walk below would re-parse them. Adaptive sizes the budget // from the finished walk's touched bytes, so nothing evicts… memo.beginWalk(counting.seam()); try t.expectEqual(@as(usize, 0), memo.evicted); try t.expectEqual(@as(usize, 3), memo.entries.count()); // …and walk 2 — identical and wide — is all hits: zero inner re-parses, // which is the entire wall-clock fix. const inner_before = counting.calls; _ = r.resolveFn(r.ctx, sm('1')); _ = r.resolveFn(r.ctx, sm('2')); _ = r.resolveFn(r.ctx, sm('3')); try t.expectEqual(inner_before, counting.calls); // Walk 3 touches only '3': the working set SHRANK. The boundary after it // re-arms the budget from that narrow set (one entry + headroom, under // the floor here → the floor), and the trim evicts the stale wide-era // entries — adaptation is a tracker, not a ratchet. memo.beginWalk(counting.seam()); _ = r.resolveFn(r.ctx, sm('3')); try t.expectEqual(per_entry, memo.walk_touched); memo.beginWalk(counting.seam()); try t.expect(memo.evicted >= 2); try t.expectEqual(@as(usize, 1), memo.entries.count()); try t.expect(memo.retained <= memo.budget); } 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.adaptive = false; 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.adaptive = false; 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 }; } };