//! Sparse-cone classification (draft-fossil-sparse-cone-00 sections 5.1,
//! 5.2, 6.3; draft-fossil-horizon-00 section 4): which artifacts a
//! cone-scoped transfer keeps, and which absences are deliberate. Shared by
//! the clone/pull/sync client layer and the cone-aware server, which is why
//! it lives in the library rather than the CLI: both sides must classify
//! identically or a server could withhold what its client would have kept.
const std = @import("std");
const artifact = @import("artifact.zig");
const repostate = @import("repostate.zig");
const cone_mod = @import("cone.zig");
const codec = @import("container.zig");
const logstore = @import("logstore.zig");
const repocache = @import("repocache.zig");
const crc32 = @import("crc32.zig");
const structgraph = @import("structgraph.zig");
/// Sparse-cone RFC sections 5.1 and 6.3, horizon draft section 4.1: decide,
/// per held artifact, whether a cone-scoped clone persists it. KEEPS every
/// artifact that parses as structural (manifests, sub-manifest nodes,
/// control, wiki, tickets, technotes, forum, attachments, clusters -- holding
/// more than the section 5.1 minimum is sound and keeps this pass simple),
/// every blob an in-cone F card of a check-in in the held set names, every
/// attachment source, and -- conservatively -- every blob nothing references
/// at all. ELIDES exactly the blobs whose every reference is an F card the
/// cone does not keep: out-of-cone by path, or, under a horizon, named only
/// by trees below it. Eliding writes nothing new: phantoms never reach disk,
/// and the next open re-interns the dangling references, which the local
/// cone then classifies as elided.
pub const SparseClassification = struct {
/// Rids a cone-scoped persist keeps (structural + in-cone-referenced +
/// unreferenced-held).
keep: std.DynamicBitSetUnmanaged,
/// Rids referenced by at least one F card the cone does not keep.
/// `out_only` minus `keep` is the elided set -- the only absence class
/// sync must not spontaneously request (RFC section 5.2 rule 3). A
/// phantom referenced by nothing (cluster-only, unversioned) is NOT here
/// and stays a transit phantom: suppression never widens past what a
/// held F card proves out-of-cone.
out_only: std.DynamicBitSetUnmanaged,
/// Horizon draft section 5.3 -- under a structural horizon, the rids of
/// check-ins below the horizon that a held check-in in K names as a
/// parent: the boundary hashes the origin labels for the client. Empty
/// without a structural horizon. Owned.
boundary: []const repostate.Rid = &.{},
pub fn elided(self: *const SparseClassification, rid: repostate.Rid) bool {
// A rid interned AFTER classification (an arrival mid-run) is beyond
// the bitsets and is never elided -- new content is wanted content.
if (rid >= self.keep.capacity()) return false;
return self.out_only.isSet(rid) and !self.keep.isSet(rid);
}
pub fn deinit(self: *SparseClassification, gpa: std.mem.Allocator) void {
self.keep.deinit(gpa);
self.out_only.deinit(gpa);
gpa.free(self.boundary);
self.* = undefined;
}
};
/// Set `rid` in `bits`, growing the set when the rid is beyond it. Classification
/// INTERNS every name a held F card cites (a phantom is session state the
/// store creates on demand, repo-state section 4.2), so rids can appear past
/// the count the sets were sized for; growing keeps the invariant "every
/// classified rid is addressable" without a second counting pass.
fn setGrow(bits: *std.DynamicBitSetUnmanaged, gpa: std.mem.Allocator, rid: repostate.Rid) error{OutOfMemory}!void {
if (rid >= bits.capacity()) try bits.resize(gpa, rid + 1, false);
bits.set(rid);
}
pub const ClassifyOptions = struct {
/// Intern every name a held F or P card cites that the store does not
/// hold, so the phantoms sync creates for them later are classifiable.
/// The client wants this; an origin classifying over a snapshot shared
/// across rounds must not grow it (see the serve-side classifier).
intern_absent: bool = true,
/// Leave the boundary parents (held check-ins' parents the store lacks)
/// out of the elided set. A client classifying before a pull cannot tell
/// a parent below the horizon from one it has not fetched yet; the origin
/// can, filters its answers by its own keep set, and labels the ones
/// below. Verbs that only read keep the default and treat them as elided.
boundary_transit: bool = false,
};
/// Where a classification reads an artifact's graph references from.
pub const Source = union(enum) {
/// Read and parse the artifacts: any cone, interning on a client.
parse,
/// Walk the embedder's structural graph (an origin's, horizon-only cones:
/// the graph carries no filenames, so `covers` cannot be asked of it).
graph: *const structgraph.Graph,
};
const FileRef = struct { target: repostate.Rid, in_path: bool };
/// One artifact's graph references, resolved to rids (see `ClassifyState.refsOf`).
const Refs = struct {
kind: structgraph.Kind,
parents: []const repostate.Rid,
baseline: ?repostate.Rid,
nodes: []const repostate.Rid,
files: []const FileRef,
attachment_source: ?repostate.Rid,
};
pub fn classifyKeepRids(
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
) error{OutOfMemory}!SparseClassification {
return classifyKeepRidsOpts(gpa, store, sparse, .{});
}
/// Resolve a cited name to a rid under the options: intern when allowed,
/// otherwise look up and skip what the store cannot name.
fn cite(store: repostate.ArtifactStore, name: []const u8, opts: ClassifyOptions) error{OutOfMemory}!?repostate.Rid {
if (opts.intern_absent) return try store.intern(name);
return store.lookup(name);
}
/// Classify the whole store in one pass: a fresh state extended from rid 1.
pub fn classifyKeepRidsOpts(
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
) error{OutOfMemory}!SparseClassification {
var st = try ClassifyState.init(gpa, store.count());
defer st.deinit(gpa);
try st.extend(gpa, store, sparse, opts, .parse);
return st.finalize(gpa, store, opts);
}
/// The classification as a function of the log PREFIX it has read, so the
/// artifacts appended since can be classified without re-reading the rest.
///
/// Every set below is monotone in the rids appended -- a check-in enters K
/// and never leaves it, a blob named above the horizon stays above, a
/// manifest reached from K stays reached -- with exactly one exception: an
/// artifact that arrives AFTER something already held cited it (a parent
/// pushed after its child, a baseline after its delta). Such an arrival can
/// pull old check-ins into K, so the names of every unresolved P, B and S
/// citation are kept (`dangling`) and an arrival that matches one sends the
/// caller back to a full pass. F-card citations are not tracked: a blob that
/// arrives after the manifest naming it classifies as an unreferenced
/// holding, which keeps it -- more than the exact answer, never less, and
/// section 5.1 permits keeping more.
///
/// `keep_ref` is the keep set BEFORE the unreferenced-holding rule, which
/// `finalize` applies over the whole store each time: a blob kept only
/// because nothing named it yet must become elided when a below-horizon
/// manifest naming it arrives later.
pub const ClassifyState = struct {
/// Whether the horizon's C is held, so the horizon sets mean anything.
/// A state that is not placed is never persisted (see `classifyCached`).
placed: bool = false,
/// Rids a cone-scoped persist keeps by rule: structural artifacts the
/// cone keeps, blobs an in-cone kept manifest names in time, attachment
/// sources. The unreferenced-holding rule is applied at `finalize`.
keep_ref: std.DynamicBitSetUnmanaged,
/// Rids referenced by at least one F card the cone does not keep.
referenced: std.DynamicBitSetUnmanaged,
/// Horizon draft section 3.1 -- the held set K of check-ins.
in_k: std.DynamicBitSetUnmanaged,
/// C's ancestry, for the `leaves` rule's stopping set. Empty otherwise.
anc_c: std.DynamicBitSetUnmanaged,
/// The structural artifacts K's trees reach (K's manifests, their
/// baselines and sub-manifest nodes).
reach: std.DynamicBitSetUnmanaged,
/// The blobs some check-in in K names, directly or through a node.
above: std.DynamicBitSetUnmanaged,
/// Horizon draft section 5.3 -- parents K's check-ins name that are not
/// in K. Filtered against `in_k` at `finalize` (the `leaves` rule can
/// pull a boundary check-in into K later).
boundary: std.ArrayListUnmanaged(repostate.Rid) = .empty,
/// Names P, B and S cards cite that the store does not hold; owned.
dangling: std.StringHashMapUnmanaged(void) = .empty,
/// Every held rid in 1..=n_done has been through the passes.
n_done: repostate.Rid = 0,
pub fn init(gpa: std.mem.Allocator, n: usize) error{OutOfMemory}!ClassifyState {
var st: ClassifyState = .{
.keep_ref = .{},
.referenced = .{},
.in_k = .{},
.anc_c = .{},
.reach = .{},
.above = .{},
};
errdefer st.deinit(gpa);
st.keep_ref = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.referenced = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.in_k = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.anc_c = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.reach = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.above = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
return st;
}
pub fn deinit(self: *ClassifyState, gpa: std.mem.Allocator) void {
self.keep_ref.deinit(gpa);
self.referenced.deinit(gpa);
self.in_k.deinit(gpa);
self.anc_c.deinit(gpa);
self.reach.deinit(gpa);
self.above.deinit(gpa);
self.boundary.deinit(gpa);
var it = self.dangling.keyIterator();
while (it.next()) |k| gpa.free(k.*);
self.dangling.deinit(gpa);
self.* = undefined;
}
fn grow(self: *ClassifyState, gpa: std.mem.Allocator, len: usize) error{OutOfMemory}!void {
inline for (.{ &self.keep_ref, &self.referenced, &self.in_k, &self.anc_c, &self.reach, &self.above }) |b| {
if (b.capacity() < len) try b.resize(gpa, len, false);
}
}
fn isSet(b: *const std.DynamicBitSetUnmanaged, rid: repostate.Rid) bool {
return rid < b.capacity() and b.isSet(rid);
}
/// Record a P/B/S citation the store does not hold.
fn dangle(self: *ClassifyState, gpa: std.mem.Allocator, name: []const u8) error{OutOfMemory}!void {
if (self.dangling.contains(name)) return;
const owned = try gpa.dupe(u8, name);
errdefer gpa.free(owned);
try self.dangling.putNoClobber(gpa, owned, {});
}
/// Resolve a P/B/S citation: the rid when the store holds it (interning
/// or not per `opts`), null -- and a `dangling` record -- otherwise.
fn citeGraph(self: *ClassifyState, gpa: std.mem.Allocator, store: repostate.ArtifactStore, name: []const u8, opts: ClassifyOptions) error{OutOfMemory}!?repostate.Rid {
const rid = try cite(store, name, opts);
if (rid == null or !store.held(rid.?)) try self.dangle(gpa, name);
return rid;
}
/// Does an artifact in `from..=count` carry a name a held artifact cited
/// before it arrived? Then the monotone extension is not exact.
pub fn arrivalWasCited(self: *const ClassifyState, store: repostate.ArtifactStore, from: repostate.Rid) bool {
if (self.dangling.count() == 0) return false;
const n = store.count();
var rid = from;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
if (self.dangling.contains(store.hashOf(rid))) return true;
}
return false;
}
/// One artifact's graph references for the passes, resolved to rids:
/// from the embedder's structural graph when it has one that covers the
/// rid, otherwise by reading and parsing the artifact. Slices live in
/// `arena` until its next reset. Null for a blob or an unheld rid.
///
/// Parsed, under a horizon, every P, B and S name is cited (interned on
/// a client, looked up on an origin) so the phantoms sync creates for
/// them later are classifiable, and the ones the store does not hold are
/// recorded as dangling. Every F name is cited likewise: a blob this
/// store does not hold must still be classified, or the phantom sync
/// creates for it is beyond these sets and `elided` answers false --
/// which is a spontaneous request for every elided blob on every pull.
/// From the graph nothing is interned: the graph is what is held, and a
/// classification over it is an origin's, which filters by keep alone.
fn refsOf(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
arena: std.mem.Allocator,
rid: repostate.Rid,
want: enum { full, kind_only },
) error{OutOfMemory}!?Refs {
if (!store.held(rid)) return null;
switch (source) {
.graph => |g| if (rid <= g.n) {
const rec = g.record(rid) orelse return null;
// The main pass asks only the kind and the attachment source;
// the walks ask the rest. Widening every reference of 1.25M
// artifacts to pass over them once is most of a classification.
var parents: []repostate.Rid = &.{};
var nodes: []repostate.Rid = &.{};
if (want == .full) {
parents = try arena.alloc(repostate.Rid, rec.parents.len);
for (rec.parents, parents) |r, *o| o.* = r;
nodes = try arena.alloc(repostate.Rid, rec.nodes.len);
for (rec.nodes, nodes) |r, *o| o.* = r;
}
// F targets are not in the graph; `filesOf` reads them for the
// few artifacts the reach walk visits, and the main pass has
// no use for them: see the end of `extend`.
return .{
.kind = rec.kind,
.parents = parents,
.baseline = if (rec.baseline) |r| r else null,
.nodes = nodes,
.files = &.{},
.attachment_source = if (rec.attachment_source) |r| r else null,
};
},
.parse => {},
}
if (!structgraph.mayBeStructural(gpa, store, rid)) return null; // a content blob, by its first bytes, before any inflate
const plain = store.content(rid) orelse return null;
if (!structgraph.looksStructural(plain)) return null;
const im = artifact.parseForImport(arena, plain) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return null, // not structural: a content blob, classified by its referencers
};
const m = &im.manifest;
const graph_cite = sparse.horizon != null;
var parents: std.ArrayListUnmanaged(repostate.Rid) = .empty;
for (m.p) |pc| {
var it = pc.hashes();
while (it.next()) |ph| {
const r = (if (graph_cite) try self.citeGraph(gpa, store, ph, opts) else store.lookup(ph)) orelse continue;
try parents.append(arena, r);
}
}
const baseline: ?repostate.Rid = if (m.b) |bc| (if (graph_cite) try self.citeGraph(gpa, store, bc.hash, opts) else store.lookup(bc.hash)) else null;
var nodes: std.ArrayListUnmanaged(repostate.Rid) = .empty;
for (m.s) |sc| {
const r = (if (graph_cite) try self.citeGraph(gpa, store, sc.hash, opts) else store.lookup(sc.hash)) orelse continue;
try nodes.append(arena, r);
}
var files: std.ArrayListUnmanaged(FileRef) = .empty;
for (m.f) |fc| {
const h = fc.hash orelse continue; // delete marker names nothing
const target = (try cite(store, h, opts)) orelse continue;
try files.append(arena, .{ .target = target, .in_path = sparse.covers(fc.filename) });
}
var attachment_source: ?repostate.Rid = null;
if (m.a) |ac| {
if (ac.source) |src| attachment_source = store.lookup(src);
}
return .{
.kind = switch (m.kind) {
.manifest => .manifest,
.submanifest => .submanifest,
.cluster => .cluster,
else => .other,
},
.parents = parents.items,
.baseline = baseline,
.nodes = nodes.items,
.files = files.items,
.attachment_source = attachment_source,
};
}
/// The held rids an artifact's F cards name, for the reach walk: from the
/// parsed artifact when the source is the graph (which carries none),
/// else from `refs`.
fn filesOf(
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
source: Source,
arena: std.mem.Allocator,
rid: repostate.Rid,
refs: *const Refs,
) error{OutOfMemory}![]const FileRef {
switch (source) {
.parse => return refs.files,
.graph => |g| if (rid > g.n) return refs.files,
}
_ = gpa;
const plain = store.content(rid) orelse return &.{};
const im = artifact.parseForImport(arena, plain) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return &.{},
};
var files: std.ArrayListUnmanaged(FileRef) = .empty;
for (im.manifest.f) |fc| {
const h = fc.hash orelse continue;
const target = store.lookup(h) orelse continue;
try files.append(arena, .{ .target = target, .in_path = true });
}
return files.items;
}
/// Classify the held rids in `n_done+1..=count()`, folding them into the
/// sets. Equivalent to one pass over the whole store when `n_done` is 0.
pub fn extend(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
) error{OutOfMemory}!void {
const from: repostate.Rid = self.n_done + 1;
const n: repostate.Rid = store.count();
try self.grow(gpa, n + 1);
// The graph's unresolved citations are this state's too: an arrival
// matching one must send the next extension back to a full pass.
switch (source) {
.graph => |g| {
var it = g.dangling.keyIterator();
while (it.next()) |k| try self.dangle(gpa, k.*);
},
.parse => {},
}
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
// Horizon draft section 4.2 -- under a horizon, a blob is above it
// when some check-in in K names it. Computed first, as bitsets over
// rids, so the pass below can ask one question per F card.
// Structural artifacts that newly joined K's reach in this extension
// are re-classified below: they were unkept, and are kept now.
var newly_reached: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer newly_reached.deinit(gpa);
if (sparse.horizon) |h| try self.extendHorizon(gpa, store, sparse, h, opts, source, from, &arena_state, &newly_reached);
// A horizon this store cannot place elides nothing. After a deepen
// the cone names a check-in the store does not hold yet; until the
// pull brings it, no hash can be proven below the horizon, and
// classifying everything as elided would make that pull request
// nothing (which is exactly what it did). The origin, which holds C,
// keeps filtering.
const above: ?*const std.DynamicBitSetUnmanaged = if (sparse.horizon != null and self.placed) &self.above else null;
const structural = self.placed and if (sparse.horizon) |h| h.depth == .structural else false;
var rid: repostate.Rid = from;
while (rid <= n) : (rid += 1) try self.classifyRid(gpa, store, sparse, opts, source, &arena_state, rid, above, structural);
for (newly_reached.items) |r| try self.classifyRid(gpa, store, sparse, opts, source, &arena_state, r, above, structural);
// Over the graph the main pass saw no F cards. What they would have
// decided follows from two sets: a blob a kept manifest names in
// time is exactly a blob some reached artifact names (`above`, with
// every path in the cone), and a blob only unkept manifests name is
// a cited blob that is not above. So keep the former and mark every
// cited blob referenced: `finalize` keeps what is referenced by
// nothing and elides what is referenced and not kept, as the
// per-artifact pass would have.
if (source == .graph and self.placed) {
const g = source.graph;
try self.grow(gpa, @max(self.above.capacity(), g.cited.capacity()));
self.keep_ref.setUnion(self.above);
var cited = try g.cited.clone(gpa);
defer cited.deinit(gpa);
if (cited.capacity() < self.referenced.capacity()) try cited.resize(gpa, self.referenced.capacity(), false);
if (self.referenced.capacity() < cited.capacity()) try self.referenced.resize(gpa, cited.capacity(), false);
self.referenced.setUnion(cited);
}
self.n_done = n;
}
/// One held artifact through the keep rules (see `extend`).
fn classifyRid(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
arena_state: *std.heap.ArenaAllocator,
rid: repostate.Rid,
above: ?*const std.DynamicBitSetUnmanaged,
structural: bool,
) error{OutOfMemory}!void {
_ = arena_state.reset(.retain_capacity);
const refs = (try self.refsOf(gpa, store, sparse, opts, source, arena_state.allocator(), rid, .kind_only)) orelse return;
// Horizon draft sections 4.5 and 5.1: under a horizon a cluster is
// never kept (its members are below the horizon as often as not, and
// the client acts on none of them); under a STRUCTURAL horizon a
// check-in manifest or sub-manifest node is kept only when K reaches
// it. Everything else structural persists, whatever its age.
const unkept_structural = (sparse.horizon != null and refs.kind == .cluster) or
(structural and (refs.kind == .manifest or refs.kind == .submanifest) and !isSet(&self.reach, rid));
if (unkept_structural) {
// Classified elided, not transit: a held artifact the policy drops
// must never be requested back by the next sync. Its F cards are
// still walked below, as references the cone does not keep, so
// the blobs only it names classify elided rather than as
// unreferenced holdings the last pass would keep.
try setGrow(&self.referenced, gpa, rid);
} else {
try setGrow(&self.keep_ref, gpa, rid); // every other structural artifact persists (spine included)
}
// F cards: flat runs, delta patch runs, and sub-manifest leaf runs all
// name blobs by full decoded path -- one rule covers all three.
for (refs.files) |f| {
const in_time = if (above) |a| isSet(a, f.target) else true;
if (!unkept_structural and f.in_path and in_time) {
try setGrow(&self.keep_ref, gpa, f.target);
} else {
try setGrow(&self.referenced, gpa, f.target);
}
}
// An attachment's source blob is non-file content (section 5.1's
// "non-manifest structural artifacts dense" extends to what they
// directly carry).
if (!unkept_structural) {
if (refs.attachment_source) |target| try setGrow(&self.keep_ref, gpa, target);
}
}
/// Horizon draft sections 3.1 and 4.2 -- K from the P cards of the held
/// check-ins under the rule, then the blobs of K's trees through B and S
/// cards, then the boundary. Over the rids from `from`, seeded by the sets
/// as they stand; the full pass is the case `from == 1`.
///
/// Deliberately an over-approximation in one direction: a delta manifest's
/// deletions and overrides are not applied, so a blob the baseline named and
/// the delta removed is still counted above. Keeping more than the exact
/// tree is sound (section 5.1 says so of every structural artifact) and it
/// makes the closure a plain reachability walk with one visited set, which
/// is what keeps this O(K's reach) rather than O(K x tree).
fn extendHorizon(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
horizon: cone_mod.Horizon,
opts: ClassifyOptions,
source: Source,
from: repostate.Rid,
arena_state: *std.heap.ArenaAllocator,
newly_reached: *std.ArrayListUnmanaged(repostate.Rid),
) error{OutOfMemory}!void {
const n: repostate.Rid = store.count();
// A C this store does not hold, or holds only as a phantom, yields the
// empty set: nothing is above a horizon the store cannot see.
const c_rid = store.lookup(horizon.hash) orelse return;
if (!store.held(c_rid)) return;
const first_placement = !self.placed;
self.placed = true;
// Pass 1: the check-in graph as child edges, from the P cards of the
// check-ins in range. Edges to parents this store does not hold are
// dropped (and recorded): a boundary hash is below the horizon by
// construction.
const Edge = struct { parent: repostate.Rid, child: repostate.Rid };
var edges: std.ArrayListUnmanaged(Edge) = .empty;
defer edges.deinit(gpa);
var is_checkin = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
defer is_checkin.deinit(gpa);
var has_child = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
defer has_child.deinit(gpa);
var rid: repostate.Rid = from;
while (rid <= n) : (rid += 1) {
_ = arena_state.reset(.retain_capacity);
const refs = (try self.refsOf(gpa, store, sparse, opts, source, arena_state.allocator(), rid, .full)) orelse continue;
if (refs.kind != .manifest) continue;
is_checkin.set(rid);
for (refs.parents) |parent| {
if (!store.held(parent)) continue;
try edges.append(gpa, .{ .parent = parent, .child = rid });
try setGrow(&has_child, gpa, parent);
}
}
// Adjacency by parent: sort edges, then index ranges. Bounded by the
// edge count, which is at most the P-card count of the range.
std.mem.sort(Edge, edges.items, {}, struct {
fn less(_: void, x: Edge, y: Edge) bool {
return x.parent < y.parent;
}
}.less);
// Pass 2: K. Descendants of C by BFS over child edges, seeded by C on
// its first placement and by every edge from a check-in already in K.
var in_k_before = try self.in_k.clone(gpa);
defer in_k_before.deinit(gpa);
var work: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer work.deinit(gpa);
if (first_placement) {
self.in_k.set(c_rid);
try work.append(gpa, c_rid);
}
for (edges.items) |e| {
if (self.in_k.isSet(e.parent) and !self.in_k.isSet(e.child)) {
self.in_k.set(e.child);
try work.append(gpa, e.child);
}
}
while (work.pop()) |cur| {
const first = lowerBound(edges.items, cur);
var i = first;
while (i < edges.items.len and edges.items[i].parent == cur) : (i += 1) {
const child = edges.items[i].child;
if (self.in_k.isSet(child)) continue;
self.in_k.set(child);
try work.append(gpa, child);
}
}
if (horizon.rule == .leaves) {
// Ancestors of C, so a leaf's walk knows where C's ancestry begins.
// Fixed once C is held: an ancestor arriving later is a cited
// arrival (full pass).
if (first_placement) try self.walkParents(gpa, store, sparse, opts, source, arena_state, c_rid, &self.anc_c, null);
// Every check-in in range without a held child is a leaf. Closed
// leaves are not excluded here (that needs the tag derivation);
// including them keeps more, never less.
rid = from;
while (rid <= n) : (rid += 1) {
if (!is_checkin.isSet(rid) or isSet(&has_child, rid)) continue;
if (self.in_k.isSet(rid) or self.anc_c.isSet(rid)) continue;
// Walk this leaf's ancestry into K, stopping at C's ancestry
// (the nearest common ancestor is included) or at K.
try self.walkParents(gpa, store, sparse, opts, source, arena_state, rid, &self.in_k, &self.anc_c);
}
}
// Pass 3: the blobs of K's trees -- every F-card target reachable from
// a K manifest through B and S cards, one visited set (`reach`) over
// structural rids so shared baselines and nodes are expanded once. The
// same walk records the boundary: a parent a K check-in names that is
// not itself in K (horizon draft section 5.3). Seeded by the check-ins
// that entered K in this extension.
var reach_before = try self.reach.clone(gpa);
defer reach_before.deinit(gpa);
const visited = &self.reach;
work.clearRetainingCapacity();
rid = 1;
while (rid <= n) : (rid += 1) {
if (self.in_k.isSet(rid) and !isSet(&in_k_before, rid)) {
visited.set(rid);
try work.append(gpa, rid);
}
}
var boundary_seen = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
defer boundary_seen.deinit(gpa);
for (self.boundary.items) |b| try setGrow(&boundary_seen, gpa, b);
while (work.pop()) |cur| {
_ = arena_state.reset(.retain_capacity);
const refs = (try self.refsOf(gpa, store, sparse, opts, source, arena_state.allocator(), cur, .full)) orelse continue;
// The keep decision for a blob K names must be reachable whether
// or not the store holds its bytes yet (cited, so a phantom).
for (try filesOf(gpa, store, source, arena_state.allocator(), cur, &refs)) |f| try setGrow(&self.above, gpa, f.target);
if (self.in_k.isSet(cur)) {
for (refs.parents) |parent| {
// A boundary parent this store never held (a structural
// clone's own C has one) is still a classifiable rid where
// the source interns, so it counts as elided and is never
// requested.
if (isSet(&self.in_k, parent)) continue;
if (parent >= boundary_seen.capacity()) try boundary_seen.resize(gpa, parent + 1, false);
if (boundary_seen.isSet(parent)) continue;
boundary_seen.set(parent);
try self.boundary.append(gpa, parent);
}
}
if (refs.baseline) |base| {
if (store.held(base) and !isSet(visited, base)) {
try setGrow(visited, gpa, base);
try work.append(gpa, base);
}
}
for (refs.nodes) |node| {
if (store.held(node) and !isSet(visited, node)) {
try setGrow(visited, gpa, node);
try work.append(gpa, node);
}
}
}
// The structural artifacts below `from` that K reaches only now: an
// old baseline a new delta manifest in K builds on, or an old
// check-in the `leaves` rule pulled in. They re-classify as kept.
rid = 1;
while (rid < from) : (rid += 1) {
if (self.reach.isSet(rid) and !isSet(&reach_before, rid)) try newly_reached.append(gpa, rid);
}
}
/// Walk `start`'s ancestry through P cards, setting `out` for every
/// check-in reached. When `stop` is given, a check-in already in `stop` is
/// set in `out` (the nearest common ancestor is held) and not expanded.
/// Bounded by the check-in count: `out` is the visited set.
fn walkParents(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
arena_state: *std.heap.ArenaAllocator,
start: repostate.Rid,
out: *std.DynamicBitSetUnmanaged,
stop: ?*const std.DynamicBitSetUnmanaged,
) error{OutOfMemory}!void {
var work: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer work.deinit(gpa);
if (isSet(out, start)) return;
try setGrow(out, gpa, start);
try work.append(gpa, start);
while (work.pop()) |cur| {
if (stop) |st| if (isSet(st, cur)) continue;
_ = arena_state.reset(.retain_capacity);
const refs = (try self.refsOf(gpa, store, sparse, opts, source, arena_state.allocator(), cur, .full)) orelse continue;
for (refs.parents) |parent| {
if (isSet(out, parent)) continue;
try setGrow(out, gpa, parent);
try work.append(gpa, parent);
}
}
}
/// The classification the sets describe for the store as it stands: the
/// unreferenced-holding rule over every held rid, the boundary as elided
/// unless the caller treats it as transit.
pub fn finalize(
self: *const ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
opts: ClassifyOptions,
) error{OutOfMemory}!SparseClassification {
const n: repostate.Rid = store.count();
const len = @max(self.keep_ref.capacity(), @max(self.referenced.capacity(), n + 1));
var keep = try self.keep_ref.clone(gpa);
errdefer keep.deinit(gpa);
if (keep.capacity() < len) try keep.resize(gpa, len, false);
var out_only = try self.referenced.clone(gpa);
errdefer out_only.deinit(gpa);
if (out_only.capacity() < len) try out_only.resize(gpa, len, false);
// A held blob nothing referenced stays: unknown provenance is kept,
// and "referenced only by an F card the cone does not keep" is the
// sole elision. Interned phantoms are not held, so they never enter.
var rid: repostate.Rid = 1;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
if (keep.isSet(rid)) continue;
if (!out_only.isSet(rid)) keep.set(rid);
}
// Horizon draft section 5.3 -- boundary check-ins are referenced by a
// held P card and never kept: elided, so verification counts them and
// sync never asks for them. A boundary parent the `leaves` rule has
// since pulled into K is no boundary.
var boundary: std.ArrayListUnmanaged(repostate.Rid) = .empty;
errdefer boundary.deinit(gpa);
for (self.boundary.items) |b| {
if (isSet(&self.in_k, b)) continue;
try boundary.append(gpa, b);
if (!opts.boundary_transit) try setGrow(&out_only, gpa, b);
}
// The two sets must address the same rids: a rid only one of them
// grew to reads as unset in the other, which is the right answer, but
// `elided` indexes both by one capacity test.
const final_len = @max(keep.capacity(), out_only.capacity());
if (keep.capacity() < final_len) try keep.resize(gpa, final_len, false);
if (out_only.capacity() < final_len) try out_only.resize(gpa, final_len, false);
return .{ .keep = keep, .out_only = out_only, .boundary = try boundary.toOwnedSlice(gpa) };
}
};
// ---------------------------------------------------------------------------
// The persisted state: a `.zit-cache` sidecar keyed to the log prefix it
// classified, so a store that only grew since is classified by reading the
// growth. Bits are kept for log rids only (1..=n_rids); a phantom's rid is
// session state and is never written. Boundary members are written by name
// for the same reason. Advisory: any doubt is a full pass, never an error.
// ---------------------------------------------------------------------------
const sidecar_magic: *const [8]u8 = "ZITHZNCL";
const sidecar_version: u16 = 1;
/// Member name: `cone-` plus the first 24 hex digits of the cone digest.
const sidecar_member_prefix = "cone-";
fn sidecarMember(digest: *const [32]u8, buf: *[sidecar_member_prefix.len + 24]u8) []const u8 {
@memcpy(buf[0..sidecar_member_prefix.len], sidecar_member_prefix);
const hex = std.fmt.bytesToHex(digest[0..12], .lower);
@memcpy(buf[sidecar_member_prefix.len..], &hex);
return buf;
}
fn putInt(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, comptime T: type, v: T) error{OutOfMemory}!void {
var buf: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &buf, v, .little);
try out.appendSlice(gpa, &buf);
}
fn putBits(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, bits: *const std.DynamicBitSetUnmanaged, n_bits: usize) error{OutOfMemory}!void {
// Exactly the first `n_bits` bits, as little-endian 64-bit words.
const words = (n_bits + 63) / 64;
try putInt(out, gpa, u64, n_bits);
var w: usize = 0;
while (w < words) : (w += 1) {
var word: u64 = 0;
var i: usize = 0;
while (i < 64) : (i += 1) {
const bit = w * 64 + i;
if (bit >= n_bits) break;
if (bit < bits.capacity() and bits.isSet(bit)) word |= @as(u64, 1) << @intCast(i);
}
try putInt(out, gpa, u64, word);
}
}
const Reader = struct {
buf: []const u8,
pos: usize = 0,
fn int(self: *Reader, comptime T: type) ?T {
const size = @sizeOf(T);
if (self.pos + size > self.buf.len) return null;
const v = std.mem.readInt(T, self.buf[self.pos..][0..size], .little);
self.pos += size;
return v;
}
fn bytes(self: *Reader, len: usize) ?[]const u8 {
if (self.pos + len > self.buf.len) return null;
const s = self.buf[self.pos..][0..len];
self.pos += len;
return s;
}
fn bits(self: *Reader, gpa: std.mem.Allocator) error{OutOfMemory}!?std.DynamicBitSetUnmanaged {
const n_bits: usize = std.math.cast(usize, self.int(u64) orelse return null) orelse return null;
const words = (n_bits + 63) / 64;
var set = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n_bits);
errdefer set.deinit(gpa);
var w: usize = 0;
while (w < words) : (w += 1) {
const word = self.int(u64) orelse return null;
var i: usize = 0;
while (i < 64) : (i += 1) {
const bit = w * 64 + i;
if (bit >= n_bits) break;
if ((word >> @intCast(i)) & 1 != 0) set.set(bit);
}
}
return set;
}
};
fn putNames(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, names: []const []const u8) error{OutOfMemory}!void {
try putInt(out, gpa, u32, @intCast(names.len));
for (names) |nm| {
try out.append(gpa, @intCast(nm.len));
try out.appendSlice(gpa, nm);
}
}
/// Serialize `st` for a store whose first `n_rids` rids are the log's frames
/// under `key`. Null when a name does not fit its length byte.
pub fn serializeState(
gpa: std.mem.Allocator,
key: logstore.LogStore.LogKey,
n_rids: u64,
digest: *const [32]u8,
st: *const ClassifyState,
store: repostate.ArtifactStore,
) error{OutOfMemory}!?[]u8 {
var out: std.ArrayListUnmanaged(u8) = .empty;
errdefer out.deinit(gpa);
try out.appendSlice(gpa, sidecar_magic);
try putInt(&out, gpa, u16, sidecar_version);
try putInt(&out, gpa, u64, key.end);
try putInt(&out, gpa, u64, key.frame_count);
try putInt(&out, gpa, u64, key.last_frame_offset);
try putInt(&out, gpa, u32, key.last_header_crc);
try putInt(&out, gpa, u64, n_rids);
try out.appendSlice(gpa, digest);
try out.append(gpa, if (st.placed) 1 else 0);
const n_bits: usize = @intCast(n_rids + 1);
inline for (.{ &st.keep_ref, &st.referenced, &st.in_k, &st.anc_c, &st.reach, &st.above }) |b| try putBits(&out, gpa, b, n_bits);
// Boundary by name: a phantom's rid is this session's.
var names: std.ArrayListUnmanaged([]const u8) = .empty;
defer names.deinit(gpa);
for (st.boundary.items) |b| {
const nm = store.hashOf(b);
if (nm.len > 255) return null;
try names.append(gpa, nm);
}
try putNames(&out, gpa, names.items);
names.clearRetainingCapacity();
var it = st.dangling.keyIterator();
while (it.next()) |k| {
if (k.*.len > 255) return null;
try names.append(gpa, k.*);
}
try putNames(&out, gpa, names.items);
var crc = crc32.Crc32.init();
crc.update(out.items);
try putInt(&out, gpa, u32, crc.final());
return try out.toOwnedSlice(gpa);
}
pub const ParsedState = struct {
key: logstore.LogStore.LogKey,
n_rids: u64,
digest: [32]u8,
state: ClassifyState,
/// Borrowed from the blob.
boundary_names: []const []const u8,
pub fn deinit(self: *ParsedState, gpa: std.mem.Allocator) void {
self.state.deinit(gpa);
gpa.free(self.boundary_names);
}
};
/// Parse a sidecar blob: magic, version and CRC must hold, or null. The
/// state's `boundary` list is left empty; the caller resolves
/// `boundary_names` against its store (see `classifyCached`).
pub fn parseState(gpa: std.mem.Allocator, blob: []const u8) error{OutOfMemory}!?ParsedState {
if (blob.len < 8 + 2 + 4) return null;
if (!std.mem.eql(u8, blob[0..8], sidecar_magic)) return null;
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc.final()) return null;
var r: Reader = .{ .buf = blob[0 .. blob.len - 4], .pos = 8 };
if ((r.int(u16) orelse return null) != sidecar_version) return null;
const key = logstore.LogStore.LogKey{
.end = r.int(u64) orelse return null,
.frame_count = r.int(u64) orelse return null,
.last_frame_offset = r.int(u64) orelse return null,
.last_header_crc = r.int(u32) orelse return null,
};
const n_rids = r.int(u64) orelse return null;
const digest_bytes = r.bytes(32) orelse return null;
const placed = (r.bytes(1) orelse return null)[0];
if (placed > 1) return null;
var st: ClassifyState = .{
.placed = placed == 1,
.keep_ref = .{},
.referenced = .{},
.in_k = .{},
.anc_c = .{},
.reach = .{},
.above = .{},
.n_done = std.math.cast(repostate.Rid, n_rids) orelse return null,
};
errdefer st.deinit(gpa);
st.keep_ref = (try r.bits(gpa)) orelse return null;
st.referenced = (try r.bits(gpa)) orelse return null;
st.in_k = (try r.bits(gpa)) orelse return null;
st.anc_c = (try r.bits(gpa)) orelse return null;
st.reach = (try r.bits(gpa)) orelse return null;
st.above = (try r.bits(gpa)) orelse return null;
const n_boundary = r.int(u32) orelse return null;
const boundary_names = try gpa.alloc([]const u8, n_boundary);
errdefer gpa.free(boundary_names);
for (boundary_names) |*slot| {
const len = (r.bytes(1) orelse return null)[0];
slot.* = r.bytes(len) orelse return null;
}
const n_dangling = r.int(u32) orelse return null;
var i: u32 = 0;
while (i < n_dangling) : (i += 1) {
const len = (r.bytes(1) orelse return null)[0];
const nm = r.bytes(len) orelse return null;
try st.dangle(gpa, nm);
}
if (r.pos != r.buf.len) return null;
var digest: [32]u8 = undefined;
@memcpy(&digest, digest_bytes);
return .{ .key = key, .n_rids = n_rids, .digest = digest, .state = st, .boundary_names = boundary_names };
}
/// Classify `store` under `sparse`, reading the `.zit-cache` sidecar for
/// this cone when the log it was keyed to is still a prefix of `log` and
/// nothing has arrived that a held artifact already cited, and writing the
/// state back for the next caller. The first `log.entryCount()` rids of
/// `store` must be the log's frames in order (the holdings adapters' rid
/// contract); rids beyond are session phantoms or appendix and are classified
/// but never persisted. A store that cannot place its horizon is classified
/// in full and leaves no sidecar: that state is transient. Any sidecar
/// trouble is a full pass, never an error.
pub fn classifyCached(
gpa: std.mem.Allocator,
io: std.Io,
cache_dir: std.Io.Dir,
log: *const logstore.LogStore,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
) error{OutOfMemory}!SparseClassification {
const digest = try sparse.digest(gpa);
var member_buf: [sidecar_member_prefix.len + 24]u8 = undefined;
const member = sidecarMember(&digest, &member_buf);
const n_log: u64 = log.entryCount();
var st: ?ClassifyState = null;
defer if (st) |*s| s.deinit(gpa);
if (try repocache.loadMember(gpa, io, cache_dir, member)) |blob| {
defer gpa.free(blob);
if (try parseState(gpa, blob)) |parsed_const| {
var parsed = parsed_const;
var adopt = parsed.state.placed and
std.mem.eql(u8, &parsed.digest, &digest) and
parsed.n_rids <= n_log and
logstore.LogStore.validatePrefix(log.file, parsed.key);
if (adopt) adopt = !parsed.state.arrivalWasCited(store, @intCast(parsed.n_rids + 1));
if (adopt) {
// Boundary members back to rids: interned on a client (a
// boundary parent is a classifiable phantom there), looked up
// on an origin, dropped when neither can name them.
for (parsed.boundary_names) |nm| {
if (try cite(store, nm, opts)) |rid| try parsed.state.boundary.append(gpa, rid);
}
st = parsed.state;
gpa.free(parsed.boundary_names);
} else {
parsed.deinit(gpa);
}
}
}
if (st == null) st = try ClassifyState.init(gpa, store.count());
try st.?.extend(gpa, store, sparse, opts, source);
const result = try st.?.finalize(gpa, store, opts);
// Persist what the log rids determined. The key is the log as scanned
// (frames, config included); `n_log` is the entries that became rids.
if (st.?.placed or sparse.horizon == null) {
if (log.logKey()) |key| {
if (try serializeState(gpa, key, n_log, &digest, &st.?, store)) |blob| {
defer gpa.free(blob);
repocache.storeNamedMember(io, cache_dir, member, blob);
}
} else |_| {}
}
return result;
}
/// First index in the parent-sorted edge list whose parent is >= `parent`.
fn lowerBound(edges: anytype, parent: repostate.Rid) usize {
var lo: usize = 0;
var hi: usize = edges.len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
if (edges[mid].parent < parent) lo = mid + 1 else hi = mid;
}
return lo;
}
/// Re-exported for the verbs that classify by reading: the two-byte peek and
/// the first-card test live with the graph that is built from them.
pub const looksStructural = structgraph.looksStructural;
// ---------------------------------------------------------------------------
// Tests. Goal: pin the horizon keep predicate of draft-fossil-horizon §4.2
// over a small real check-in graph: blobs named only below C are elided,
// blobs named by C or its descendants are kept, the `leaves` rule pulls a
// side branch's ancestry (and its blobs) into K, a path cone intersects the
// horizon on blobs, and a C the store does not hold keeps nothing. Method:
// manifests minted by the artifact writer into a MemStore, classified, and
// compared against hand-computed keep/elide verdicts.
// ---------------------------------------------------------------------------
const testing = std.testing;
const Fixture = struct {
ms: repostate.MemStore,
// Blob names: 64-hex, distinct.
f_old: []const u8 = "1111111111111111111111111111111111111111111111111111111111111111",
f_keep: []const u8 = "2222222222222222222222222222222222222222222222222222222222222222",
f_new: []const u8 = "3333333333333333333333333333333333333333333333333333333333333333",
f_branch: []const u8 = "4444444444444444444444444444444444444444444444444444444444444444",
f_other: []const u8 = "5555555555555555555555555555555555555555555555555555555555555555",
// Manifest names, filled by `build`.
c1: [64]u8 = undefined,
c2: [64]u8 = undefined,
c3: [64]u8 = undefined, // C
c4: [64]u8 = undefined,
b1: [64]u8 = undefined, // a leaf forked from c1
fn store(self: *Fixture) repostate.ArtifactStore {
return self.ms.store();
}
/// Mint and store one check-in; returns its name into `out`.
fn checkin(self: *Fixture, ts: []const u8, parent: ?[]const u8, files: []const artifact.FCard, out: *[64]u8) !void {
var parent_buf: [1]artifact.PCard = undefined;
var p: []const artifact.PCard = &.{};
if (parent) |ph| {
parent_buf[0] = .{ .parents = ph, .count = 1 };
p = parent_buf[0..1];
}
var m = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(testing.allocator),
.kind = .manifest,
.a = null,
.b = null,
.c = .{ .comment = "c" },
.d = .{ .timestamp = ts },
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = files,
.j = &.{},
.m = &.{},
.p = p,
.q = &.{},
.t = &.{},
};
defer m.deinit();
const bytes = try artifact.create(&m, testing.allocator);
defer testing.allocator.free(bytes);
const name = artifact.artifactName(.sha3_256, bytes, out);
_ = try self.store().put(name, bytes);
}
fn fcard(name: []const u8, hash: []const u8) artifact.FCard {
return .{ .filename = name, .hash = hash, .perm = null, .old_name = null, .mode = .regular };
}
/// c1 -> c2 -> c3 (C) -> c4, with b1 forked from c1.
/// c1: src/keep.txt=f_keep, src/old.txt=f_old
/// c2: same as c1
/// c3: src/keep.txt=f_keep (old.txt deleted)
/// c4: src/keep.txt=f_keep, src/new.txt=f_new, other/x=f_other
/// b1: src/branch.txt=f_branch, src/keep.txt=f_keep
fn build(self: *Fixture) !void {
const s = self.store();
for ([_][]const u8{ self.f_old, self.f_keep, self.f_new, self.f_branch, self.f_other }) |h| {
_ = try s.put(h, h); // any content; the name is what the F cards cite
}
const c1_files = [_]artifact.FCard{ fcard("src/keep.txt", self.f_keep), fcard("src/old.txt", self.f_old) };
try self.checkin("2026-01-01T00:00:00", null, &c1_files, &self.c1);
try self.checkin("2026-01-02T00:00:00", &self.c1, &c1_files, &self.c2);
const c3_files = [_]artifact.FCard{fcard("src/keep.txt", self.f_keep)};
try self.checkin("2026-01-03T00:00:00", &self.c2, &c3_files, &self.c3);
const c4_files = [_]artifact.FCard{ fcard("other/x", self.f_other), fcard("src/keep.txt", self.f_keep), fcard("src/new.txt", self.f_new) };
try self.checkin("2026-01-04T00:00:00", &self.c3, &c4_files, &self.c4);
const b1_files = [_]artifact.FCard{ fcard("src/branch.txt", self.f_branch), fcard("src/keep.txt", self.f_keep) };
try self.checkin("2026-01-05T00:00:00", &self.c1, &b1_files, &self.b1);
}
fn rid(self: *Fixture, hash: []const u8) repostate.Rid {
return self.store().lookup(hash).?;
}
};
test "horizon §4.1/§4.2: descendants rule keeps C's and its descendants' blobs, elides the rest, holds every manifest" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = .descendants });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
// Every manifest is structural and kept, above or below the horizon.
for ([_][]const u8{ &fx.c1, &fx.c2, &fx.c3, &fx.c4, &fx.b1 }) |m| try testing.expect(cls.keep.isSet(fx.rid(m)));
// Blobs in the trees of C and c4 are kept.
try testing.expect(cls.keep.isSet(fx.rid(fx.f_keep)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_new)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_other)));
// Named only below the horizon, or only on a branch outside K: elided.
try testing.expect(cls.elided(fx.rid(fx.f_old)));
try testing.expect(cls.elided(fx.rid(fx.f_branch)));
try testing.expect(!cls.elided(fx.rid(fx.f_keep)));
}
test "horizon §3.1: the leaves rule pulls a side branch's ancestry into K, and its blobs with it" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = .leaves });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
// b1 is an open leaf forked at c1: K gains b1 and c1 (the nearest common
// ancestor), so f_branch and f_old (named by c1) are above the horizon.
try testing.expect(cls.keep.isSet(fx.rid(fx.f_branch)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_old)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_keep)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_new)));
}
test "horizon §3.2: a path cone and a horizon intersect on blobs" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
var cone = try cone_mod.Cone.initHorizon(gpa, &.{"src"}, &.{}, .{ .hash = &fx.c3, .rule = .descendants });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
try testing.expect(cls.keep.isSet(fx.rid(fx.f_keep)));
try testing.expect(cls.keep.isSet(fx.rid(fx.f_new)));
try testing.expect(cls.elided(fx.rid(fx.f_other))); // above the horizon, outside the path cone
try testing.expect(cls.elided(fx.rid(fx.f_old))); // inside the path cone, below the horizon
}
test "horizon §4.2: a C this store does not hold elides nothing, so the pull that brings it can ask" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
const absent = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
for ([_]cone_mod.HorizonDepth{ .content, .structural }) |depth| {
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = absent, .rule = .descendants, .depth = depth });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
// This is a clone between a deepen and its pull: the cone names a
// check-in the store does not hold. Nothing can be proven below the
// horizon, so nothing is elided; the origin, which holds C, filters.
try testing.expect(cls.keep.isSet(fx.rid(&fx.c1)));
try testing.expect(cls.keep.isSet(fx.rid(&fx.c4)));
for ([_][]const u8{ fx.f_old, fx.f_keep, fx.f_new, fx.f_branch, fx.f_other }) |h| try testing.expect(!cls.elided(fx.rid(h)));
}
}
test "horizon: classifying the appended artifacts over a prior state equals one pass over the whole store" {
const gpa = testing.allocator;
// The fixture in two arrivals: blobs and c1..c3 first, then c4 and the
// side leaf b1 -- a push of new work onto a store already classified.
for ([_]cone_mod.HorizonRule{ .descendants, .leaves }) |rule| {
for ([_]cone_mod.HorizonDepth{ .content, .structural }) |depth| {
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
const s = fx.store();
for ([_][]const u8{ fx.f_old, fx.f_keep, fx.f_new, fx.f_branch, fx.f_other }) |h| _ = try s.put(h, h);
const c1_files = [_]artifact.FCard{ Fixture.fcard("src/keep.txt", fx.f_keep), Fixture.fcard("src/old.txt", fx.f_old) };
try fx.checkin("2026-01-01T00:00:00", null, &c1_files, &fx.c1);
try fx.checkin("2026-01-02T00:00:00", &fx.c1, &c1_files, &fx.c2);
const c3_files = [_]artifact.FCard{Fixture.fcard("src/keep.txt", fx.f_keep)};
try fx.checkin("2026-01-03T00:00:00", &fx.c2, &c3_files, &fx.c3);
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = rule, .depth = depth });
defer cone.deinit(gpa);
const opts: ClassifyOptions = .{ .intern_absent = false };
var st = try ClassifyState.init(gpa, s.count());
defer st.deinit(gpa);
try st.extend(gpa, s, &cone, opts, .parse);
const n_first = st.n_done;
// Second arrival.
const c4_files = [_]artifact.FCard{ Fixture.fcard("other/x", fx.f_other), Fixture.fcard("src/keep.txt", fx.f_keep), Fixture.fcard("src/new.txt", fx.f_new) };
try fx.checkin("2026-01-04T00:00:00", &fx.c3, &c4_files, &fx.c4);
const b1_files = [_]artifact.FCard{ Fixture.fcard("src/branch.txt", fx.f_branch), Fixture.fcard("src/keep.txt", fx.f_keep) };
try fx.checkin("2026-01-05T00:00:00", &fx.c1, &b1_files, &fx.b1);
try testing.expect(!st.arrivalWasCited(s, n_first + 1));
try st.extend(gpa, s, &cone, opts, .parse);
var incremental = try st.finalize(gpa, s, opts);
defer incremental.deinit(gpa);
var full = try classifyKeepRidsOpts(gpa, s, &cone, opts);
defer full.deinit(gpa);
var r: repostate.Rid = 1;
while (r <= s.count()) : (r += 1) {
try testing.expectEqual(full.keep.isSet(r), incremental.keep.isSet(r));
try testing.expectEqual(full.elided(r), incremental.elided(r));
}
try testing.expectEqual(full.boundary.len, incremental.boundary.len);
// And the sidecar round-trips the state.
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const digest = try cone.digest(gpa);
const blob = (try serializeState(gpa, key, s.count(), &digest, &st, s)).?;
defer gpa.free(blob);
var parsed = (try parseState(gpa, blob)).?;
defer parsed.deinit(gpa);
try testing.expectEqual(key, parsed.key);
try testing.expectEqualSlices(u8, &digest, &parsed.digest);
try testing.expectEqual(st.placed, parsed.state.placed);
try testing.expectEqual(st.n_done, parsed.state.n_done);
try testing.expectEqual(st.boundary.items.len, parsed.boundary_names.len);
try testing.expectEqual(st.dangling.count(), parsed.state.dangling.count());
r = 1;
while (r <= s.count()) : (r += 1) {
try testing.expectEqual(st.keep_ref.isSet(r), parsed.state.keep_ref.isSet(r));
try testing.expectEqual(st.in_k.isSet(r), parsed.state.in_k.isSet(r));
try testing.expectEqual(st.above.isSet(r), parsed.state.above.isSet(r));
}
}
}
}
test "horizon: classifying over the structural graph equals classifying by reading, for both rules and depths" {
const gpa = testing.allocator;
for ([_]cone_mod.HorizonRule{ .descendants, .leaves }) |rule| {
for ([_]cone_mod.HorizonDepth{ .content, .structural }) |depth| {
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
const s = fx.store();
var g: structgraph.Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = rule, .depth = depth });
defer cone.deinit(gpa);
const opts: ClassifyOptions = .{ .intern_absent = false };
var by_graph = try ClassifyState.init(gpa, s.count());
defer by_graph.deinit(gpa);
try by_graph.extend(gpa, s, &cone, opts, .{ .graph = &g });
var from_graph = try by_graph.finalize(gpa, s, opts);
defer from_graph.deinit(gpa);
var by_read = try classifyKeepRidsOpts(gpa, s, &cone, opts);
defer by_read.deinit(gpa);
var r: repostate.Rid = 1;
while (r <= s.count()) : (r += 1) {
try testing.expectEqual(by_read.keep.isSet(r), from_graph.keep.isSet(r));
try testing.expectEqual(by_read.elided(r), from_graph.elided(r));
}
try testing.expectEqual(by_read.boundary.len, from_graph.boundary.len);
}
}
}
test "horizon §5.1/§5.3: the structural depth elides manifests K does not reach and reports the boundary" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = .descendants, .depth = .structural });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
// K = {c3, c4}: their manifests are kept; c1, c2 and the side leaf b1 are
// elided structure, not transit (they must never be requested back).
try testing.expect(cls.keep.isSet(fx.rid(&fx.c3)));
try testing.expect(cls.keep.isSet(fx.rid(&fx.c4)));
try testing.expect(cls.elided(fx.rid(&fx.c1)));
try testing.expect(cls.elided(fx.rid(&fx.c2)));
try testing.expect(cls.elided(fx.rid(&fx.b1)));
// Blobs: as under the content depth.
try testing.expect(cls.keep.isSet(fx.rid(fx.f_keep)));
try testing.expect(cls.elided(fx.rid(fx.f_old)));
// The boundary is exactly c2, the one parent a K check-in names below K.
try testing.expectEqual(@as(usize, 1), cls.boundary.len);
try testing.expectEqual(fx.rid(&fx.c2), cls.boundary[0]);
}