//! 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 -- and the absent sub-manifest nodes of the walked trees
/// whose every referencing S-card slot lies outside the cone. 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,
/// Lowercase names of the absent sub-manifest nodes elided by their
/// slots, whether or not the store has interned them. Kept apart from
/// the bitsets for two reasons: a clone stores wire-backed and never
/// interns a manifest's S references, so the persist hook that later
/// mints their phantoms can only ask by name; and a commit's structural
/// fetch must still request exactly these (section 5.3) while it keeps
/// suppressing elided blobs.
elided_nodes: std.StringHashMapUnmanaged(void) = .empty,
/// Owns `elided_nodes`' keys.
arena: std.heap.ArenaAllocator,
/// 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 = &.{},
/// Horizon draft section 5.2.1 -- the check-ins in K whose primary parent
/// is not in K: where the tag state K derives from enters from below the
/// horizon, and so where the seed must apply it. Owned.
entries: []const repostate.Rid = &.{},
/// Horizon draft section 6.2.6 -- the log position at which this cone was
/// last classified from scratch over a store it had classified before: an
/// arrival a held artifact cited can make kept what was not, below any
/// cursor handed out earlier. A reply to a cursor below this answers as
/// if none was sent. 0 when the classification only ever extended.
rekept_at: u64 = 0,
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);
}
/// Whether `name` (40 or 64 hex, either case) is an absent sub-manifest
/// node this classification elided.
pub fn elidedNode(self: *const SparseClassification, name: []const u8) bool {
var buf: [64]u8 = undefined;
if (name.len > buf.len) return false;
return self.elided_nodes.contains(std.ascii.lowerString(buf[0..name.len], name));
}
pub fn deinit(self: *SparseClassification, gpa: std.mem.Allocator) void {
self.keep.deinit(gpa);
self.out_only.deinit(gpa);
self.elided_nodes.deinit(gpa);
self.arena.deinit();
gpa.free(self.boundary);
gpa.free(self.entries);
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);
}
/// The cone as a tree-walk filter: an absent node whose slot the cone
/// cannot reach is elided, so a sparse checkout's walk steps over it.
pub fn slotFilter(cone: *const cone_mod.Cone) artifact.SlotFilter {
return .{ .ctx = cone, .mayHoldFn = coneMayHold };
}
fn coneMayHold(ctx: *const anyopaque, first: []const u8, limit: ?[]const u8) bool {
const cone: *const cone_mod.Cone = @ptrCast(@alignCast(ctx));
return cone.slotMayCover(first, limit);
}
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,
/// Classify the absent sub-manifest nodes of the walked trees by their
/// S-card slots (`SparseClassification.elided_nodes`), which reads every
/// such tree at each classification. A client wants this: those nodes
/// are what it must neither request nor count as gaps. An origin filters
/// its answers by `keep` alone and leaves it off.
elide_nodes: bool = true,
/// Also elide the HELD sub-manifest nodes whose every referencing slot
/// the cone cannot reach: the nodes a section 6.2 server never descends
/// to, so it neither sends them in a clone nor answers a gimme for them.
/// An origin wants this; a client keeps every node it holds, since a
/// commit's structural fetch (a request with no path members, which
/// keeps every node) is how it would get one back.
slot_held_nodes: 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). The graph carries
/// no filenames: the reach walk reads the artifacts it visits for their
/// F cards and asks the cone's path members of those, so a cone with
/// paths is classified over the graph at the cost of parsing K's trees.
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,
/// The primary parent (the first P-card name) when it resolves, and
/// whether the artifact names any parent at all.
primary: ?repostate.Rid = null,
has_parent: bool = false,
baseline: ?repostate.Rid,
nodes: []const repostate.Rid,
/// Whether the artifact carries S cards, resolved or not.
has_nodes: bool = false,
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, sparse, 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,
/// C and its descendants alone, without what the `leaves` rule adds: a
/// leaf outside them has its own meeting points, even when an earlier
/// meeting point's descendants already put it in K.
desc_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,
/// The held check-in manifests that carry S cards: the roots of the
/// slot walk that elides absent sub-manifest nodes (see `finalize`).
trees: 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,
/// Horizon draft section 5.2.1 -- K's check-ins whose primary parent was
/// not in K when they joined it. A superset of the exact set once the
/// `leaves` rule pulls such a parent in later: seeding a check-in whose
/// state also propagates to it restates that state, and changes nothing.
entry: std.DynamicBitSetUnmanaged,
/// 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,
/// See `SparseClassification.rekept_at`; persisted with the state.
rekept_at: u64 = 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 = .{},
.entry = .{},
.desc_c = .{},
.trees = .{},
};
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);
st.entry = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.desc_c = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
st.trees = 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.entry.deinit(gpa);
self.desc_c.deinit(gpa);
self.trees.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, &self.entry, &self.desc_c, &self.trees }) |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) {
// A 0 slot is a citation the store does not hold yet.
var pl = try std.ArrayListUnmanaged(repostate.Rid).initCapacity(arena, rec.parents.len);
for (rec.parents) |r| if (r != 0) pl.appendAssumeCapacity(r);
parents = pl.items;
var nl = try std.ArrayListUnmanaged(repostate.Rid).initCapacity(arena, rec.nodes.len);
for (rec.nodes) |r| if (r != 0) nl.appendAssumeCapacity(r);
nodes = nl.items;
}
// 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,
.primary = if (rec.parents.len != 0 and rec.parents[0] != 0) rec.parents[0] else null,
.has_parent = rec.parents.len != 0,
.baseline = if (rec.baseline) |r| r else null,
.nodes = nodes,
.has_nodes = rec.nodes.len != 0,
.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;
var primary: ?repostate.Rid = null;
var has_parent = false;
for (m.p) |pc| {
var it = pc.hashes();
while (it.next()) |ph| {
const first = !has_parent;
has_parent = true;
const r = (if (graph_cite) try self.citeGraph(gpa, store, ph, opts) else store.lookup(ph)) orelse continue;
if (first) primary = r;
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,
.primary = primary,
.has_parent = has_parent,
.baseline = baseline,
.nodes = nodes.items,
.has_nodes = m.s.len != 0,
.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`. Each carries whether the cone's path members cover
/// the name it is filed under.
fn filesOf(
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
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 = sparse.covers(fc.filename) });
}
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.
// `above_in_path` is the part of what this extension's walk reached
// that a path member covers: transient, folded into `keep_ref` below.
var newly_reached: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer newly_reached.deinit(gpa);
var above_in_path = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
defer above_in_path.deinit(gpa);
if (sparse.horizon) |h| try self.extendHorizon(gpa, store, sparse, h, opts, source, from, &arena_state, &newly_reached, &above_in_path);
// 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 under a covered path is exactly a blob some reached artifact
// names under one (`above_in_path`, which is `above` when the cone
// has no path members), and a blob only unkept manifests name, or
// named only outside the paths, is a cited blob that is not kept. 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()));
if (above_in_path.capacity() < self.keep_ref.capacity()) try above_in_path.resize(gpa, self.keep_ref.capacity(), false);
self.keep_ref.setUnion(above_in_path);
self.referenced.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)
}
if (refs.kind == .manifest and refs.has_nodes) try setGrow(&self.trees, gpa, rid);
// 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),
above_in_path: *std.DynamicBitSetUnmanaged,
) 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;
// Placed means "C is in K", not "this state was placed once": a
// sidecar keeps bits for log rids only, so a C that arrived in the
// same session it was classified in (a deepen pull) comes back from
// the sidecar unset, and must be placed again.
const first_placement = !isSet(&self.in_k, c_rid);
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.
var graph: EdgeGraph = .{};
defer graph.deinit(gpa);
try self.edgeGraph(gpa, store, sparse, opts, source, arena_state, from, &graph);
// 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 (graph.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);
}
}
try self.closeUnder(gpa, &graph, &work);
if (horizon.rule == .leaves) {
// The same closure from C alone, edges in range: a check-in
// descends from C exactly when some parent does.
try setGrow(&self.desc_c, gpa, c_rid);
var changed = true;
while (changed) {
changed = false;
for (graph.edges.items) |e| {
if (isSet(&self.desc_c, e.parent) and !isSet(&self.desc_c, e.child)) {
try setGrow(&self.desc_c, gpa, e.child);
changed = true;
}
}
}
}
var rid: repostate.Rid = undefined;
if (horizon.rule == .leaves) {
// Horizon draft section 3.1 -- the leaves rule: the descendants of
// C and of every check-in where a childless check-in's ancestry
// meets C's. Closed under descendants, as the descendants rule is,
// so every child of a check-in in K is in K and leaves and branch
// tips derive exactly. Stated over P cards: childless means no
// held child, closed or open.
// 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);
var meets: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer meets.deinit(gpa);
rid = from;
while (rid <= store.count() and rid <= graph.n) : (rid += 1) {
if (!graph.is_checkin.isSet(rid) or isSet(&graph.has_child, rid)) continue;
if (isSet(&self.desc_c, rid) or isSet(&self.anc_c, rid)) continue;
// Walk this leaf's ancestry back to C's ancestry, collecting
// where it meets it. The walk's own check-ins descend from a
// meeting point, and so join K below.
var seen = try std.DynamicBitSetUnmanaged.initEmpty(gpa, graph.n + 1);
defer seen.deinit(gpa);
try self.walkParents(gpa, store, sparse, opts, source, arena_state, rid, &seen, &self.anc_c);
var it = seen.iterator(.{});
while (it.next()) |x| if (isSet(&self.anc_c, x) and !self.in_k.isSet(x)) try meets.append(gpa, x);
}
if (meets.items.len != 0) {
// A meeting point already in the store has children the
// range's edges do not cover: close over the whole graph.
// What that keeps is old, below any cursor handed out from
// the state before it, so those cursors are void.
if (from > 1) {
self.rekept_at = n;
graph.deinit(gpa);
graph = .{};
try self.edgeGraph(gpa, store, sparse, opts, source, arena_state, 1, &graph);
}
work.clearRetainingCapacity();
for (meets.items) |m| {
if (self.in_k.isSet(m)) continue;
try setGrow(&self.in_k, gpa, m);
try work.append(gpa, m);
}
try self.closeUnder(gpa, &graph, &work);
}
}
// 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, sparse, source, arena_state.allocator(), cur, &refs)) |f| {
try setGrow(&self.above, gpa, f.target);
if (f.in_path) try setGrow(above_in_path, gpa, f.target);
}
if (self.in_k.isSet(cur)) {
// Horizon draft section 5.2.1 -- tag state reaches a check-in
// along its primary parent; one whose primary parent is not
// in K takes its state from below the horizon.
const primary_in_k = if (refs.primary) |p| isSet(&self.in_k, p) else false;
if (refs.has_parent and !primary_in_k) try setGrow(&self.entry, gpa, 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);
}
}
const Edge = struct { parent: repostate.Rid, child: repostate.Rid };
/// The check-in graph of rids `from..=count` as child edges sorted by
/// parent, with which rids are check-ins and which have a held child.
const EdgeGraph = struct {
edges: std.ArrayListUnmanaged(Edge) = .empty,
is_checkin: std.DynamicBitSetUnmanaged = .{},
has_child: std.DynamicBitSetUnmanaged = .{},
n: repostate.Rid = 0,
fn deinit(self: *EdgeGraph, gpa: std.mem.Allocator) void {
self.edges.deinit(gpa);
self.is_checkin.deinit(gpa);
self.has_child.deinit(gpa);
}
};
fn edgeGraph(
self: *ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
opts: ClassifyOptions,
source: Source,
arena_state: *std.heap.ArenaAllocator,
from: repostate.Rid,
out: *EdgeGraph,
) error{OutOfMemory}!void {
const n: repostate.Rid = store.count();
out.n = n;
out.is_checkin = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
out.has_child = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
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;
out.is_checkin.set(rid);
for (refs.parents) |parent| {
if (!store.held(parent)) continue;
try out.edges.append(gpa, .{ .parent = parent, .child = rid });
try setGrow(&out.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, out.edges.items, {}, struct {
fn less(_: void, x: Edge, y: Edge) bool {
return x.parent < y.parent;
}
}.less);
}
/// Add to K every descendant, over `graph`, of the rids in `work`.
fn closeUnder(self: *ClassifyState, gpa: std.mem.Allocator, graph: *const EdgeGraph, work: *std.ArrayListUnmanaged(repostate.Rid)) error{OutOfMemory}!void {
while (work.pop()) |cur| {
var i = lowerBound(graph.edges.items, cur);
while (i < graph.edges.items.len and graph.edges.items[i].parent == cur) : (i += 1) {
const child = graph.edges.items[i].child;
if (isSet(&self.in_k, child)) continue;
try setGrow(&self.in_k, gpa, child);
try work.append(gpa, child);
}
}
}
/// 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,
sparse: *const cone_mod.Cone,
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);
var entries: std.ArrayListUnmanaged(repostate.Rid) = .empty;
errdefer entries.deinit(gpa);
var it = self.entry.iterator(.{});
while (it.next()) |e| if (isSet(&self.in_k, e)) try entries.append(gpa, e);
var node_arena = std.heap.ArenaAllocator.init(gpa);
errdefer node_arena.deinit();
var elided_nodes: std.StringHashMapUnmanaged(void) = .empty;
errdefer elided_nodes.deinit(gpa);
if ((opts.elide_nodes or opts.slot_held_nodes) and sparse.hasPathMembers()) {
var held_out: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer held_out.deinit(gpa);
try self.elideNodes(gpa, store, sparse, &node_arena, &elided_nodes, if (opts.slot_held_nodes) &held_out else null);
// Both sets were sized to `final_len` above, which covers every
// held rid; a node interned past it is new and stays wanted.
for (held_out.items) |node| if (node < final_len) {
keep.unset(node);
out_only.set(node);
};
}
const boundary_owned = try boundary.toOwnedSlice(gpa);
errdefer gpa.free(boundary_owned);
return .{
.keep = keep,
.out_only = out_only,
.elided_nodes = elided_nodes,
.arena = node_arena,
.boundary = boundary_owned,
.entries = try entries.toOwnedSlice(gpa),
.rekept_at = self.rekept_at,
};
}
/// Sparse-cone RFC section 5.1 -- the absent sub-manifest nodes whose
/// every referencing slot the cone cannot reach, the same interval test a
/// section 6.2 server descends by. Absent ones enter `out`, named in
/// `node_arena`; held ones enter `held_out` when the caller serves (see
/// `ClassifyOptions.slot_held_nodes`), and are otherwise kept.
///
/// The walk reads the trees the classification keeps: every held tree
/// manifest, or under a placed STRUCTURAL horizon only those K's trees
/// reach (K's manifests and their baselines), since a tree below that
/// horizon and its nodes are outside the keep set by the horizon rule
/// already. Under a content horizon every tree is kept (horizon draft
/// section 4), so every tree's slots decide. Read from the roots down,
/// so it costs the held trees' S runs and never the blobs.
fn elideNodes(
self: *const ClassifyState,
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
node_arena: *std.heap.ArenaAllocator,
out: *std.StringHashMapUnmanaged(void),
held_out: ?*std.ArrayListUnmanaged(repostate.Rid),
) error{OutOfMemory}!void {
std.debug.assert(sparse.hasPathMembers());
std.debug.assert(out.count() == 0);
var trees = TreeSlots.init(gpa);
defer trees.deinit();
var parse_arena = std.heap.ArenaAllocator.init(gpa);
defer parse_arena.deinit();
var visited = try std.DynamicBitSetUnmanaged.initEmpty(gpa, store.count() + 1);
defer visited.deinit(gpa);
var work: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer work.deinit(gpa);
const k_only = self.placed and if (sparse.horizon) |h| h.depth == .structural else false;
var roots = self.trees.iterator(.{});
while (roots.next()) |root| {
const rid: repostate.Rid = @intCast(root);
if (k_only and !isSet(&self.reach, rid)) continue;
if (!store.held(rid) or isSet(&visited, rid)) continue;
try setGrow(&visited, gpa, rid);
try work.append(gpa, rid);
}
// Bounded by the held tree artifacts: `visited` admits each once.
while (work.pop()) |rid| {
_ = parse_arena.reset(.retain_capacity);
const plain = store.content(rid) orelse continue;
const im = artifact.parseForImport(parse_arena.allocator(), plain) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => continue, // unparseable: classified as a blob, names nothing
};
try trees.note(store.hashOf(rid), &im.manifest);
for (im.manifest.s) |sc| {
const child = store.lookup(sc.hash) orelse continue;
if (!store.held(child) or isSet(&visited, child)) continue;
try setGrow(&visited, gpa, child);
try work.append(gpa, child);
}
}
var verdicts = try trees.classify(sparse);
defer verdicts.deinit(gpa);
var it = verdicts.iterator();
while (it.next()) |e| {
if (e.value_ptr.*) continue; // some slot may hold a covered path
if (store.lookup(e.key_ptr.*)) |target| if (store.held(target)) {
if (held_out) |list| try list.append(gpa, target);
continue;
};
try out.put(gpa, try node_arena.allocator().dupe(u8, e.key_ptr.*), {});
}
}
};
// ---------------------------------------------------------------------------
// 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";
/// 2: carries `rekept_at`. 3: carries `entry`. 4: carries `desc_c`.
/// 5: carries `trees`.
const sidecar_version: u16 = 5;
/// 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);
try putInt(&out, gpa, u64, st.rekept_at);
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, &st.entry, &st.desc_c, &st.trees }) |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;
const rekept_at = r.int(u64) orelse return null;
var st: ClassifyState = .{
.placed = placed == 1,
.rekept_at = rekept_at,
.keep_ref = .{},
.referenced = .{},
.in_k = .{},
.anc_c = .{},
.reach = .{},
.above = .{},
.entry = .{},
.desc_c = .{},
.trees = .{},
.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;
st.entry = (try r.bits(gpa)) orelse return null;
st.desc_c = (try r.bits(gpa)) orelse return null;
st.trees = (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);
// A sidecar this cone had and could not extend from: whatever is kept
// now may include rids below a cursor handed out from the old state.
var rekept_at: u64 = 0;
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));
// A phantom the log recorded since was cited by F cards the
// extension will not re-read: its classification lives in the
// artifacts that cite it, so only a full pass recovers it.
if (adopt) {
var r: repostate.Rid = @intCast(parsed.n_rids + 1);
while (r <= n_log) : (r += 1) if (!store.held(r)) {
adopt = false;
break;
};
}
if (!adopt) rekept_at = n_log;
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());
st.?.rekept_at = rekept_at;
}
try st.?.extend(gpa, store, sparse, opts, source);
const result = try st.?.finalize(gpa, store, sparse, 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.
// Not while the store holds artifacts beyond the log (a run's arrivals,
// not yet persisted): the state depends on them, its bits for them are
// not kept, and an extension from the log prefix would not recompute
// what they decided about rids below it (C's ancestry, a meeting point).
var appendix_held = false;
var r: repostate.Rid = @intCast(n_log + 1);
while (r <= store.count()) : (r += 1) if (store.held(r)) {
appendix_held = true;
break;
};
if (!appendix_held and (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;
/// The S runs of a store's held tree artifacts, gathered in one pass and
/// classified once every parent is known. A slot's upper bound is the next
/// card's name, or for a node's final card its parent's bound (submanifests
/// §3.6), so an interior node's slots are only decidable from the root down:
/// gathering first lets nodes arrive in any order.
pub const TreeSlots = struct {
gpa: std.mem.Allocator,
arena: std.heap.ArenaAllocator,
/// Lowercase node name -> its S run, for every held S-bearing artifact.
nodes: std.StringHashMapUnmanaged(Node) = .empty,
/// Names of the held tree MANIFESTS: the walk's roots, unbounded above.
roots: std.ArrayListUnmanaged([]const u8) = .empty,
const Node = struct {
/// Card names, ascending (§3.4); `hashes[i]` is the node `names[i]`'s
/// slot refers to, lowercased.
names: []const []const u8,
hashes: []const []const u8,
};
pub fn init(gpa: std.mem.Allocator) TreeSlots {
return .{ .gpa = gpa, .arena = std.heap.ArenaAllocator.init(gpa) };
}
pub fn deinit(self: *TreeSlots) void {
self.nodes.deinit(self.gpa);
self.roots.deinit(self.gpa);
self.arena.deinit();
self.* = undefined;
}
/// Record one held artifact `name`'s S run. Copies what it keeps, so
/// `m` need not outlive the call.
pub fn note(self: *TreeSlots, name: []const u8, m: *const artifact.Manifest) error{OutOfMemory}!void {
if (m.s.len == 0) return;
const aa = self.arena.allocator();
const names = try aa.alloc([]const u8, m.s.len);
const hashes = try aa.alloc([]const u8, m.s.len);
for (m.s, 0..) |sc, i| {
names[i] = try aa.dupe(u8, sc.filename);
hashes[i] = try lowerDupe(aa, sc.hash);
}
const key = try lowerDupe(aa, name);
const gop = try self.nodes.getOrPut(self.gpa, key);
if (gop.found_existing) return; // content-addressed: the same run
gop.value_ptr.* = .{ .names = names, .hashes = hashes };
if (m.kind == .manifest) try self.roots.append(self.gpa, key);
}
/// Every node some held slot refers to, mapped to whether any of its
/// slots may hold a covered path. Keys borrow this `TreeSlots`.
pub fn classify(
self: *TreeSlots,
cone: *const cone_mod.Cone,
) error{OutOfMemory}!std.StringHashMapUnmanaged(bool) {
const gpa = self.gpa;
var verdicts: std.StringHashMapUnmanaged(bool) = .empty;
errdefer verdicts.deinit(gpa);
const Visit = struct { name: []const u8, upper: ?[]const u8 };
var work: std.ArrayListUnmanaged(Visit) = .empty;
defer work.deinit(gpa);
// A node shared by several check-ins is usually reached under one
// slot; each distinct (node, bound) pair is walked once, which also
// bounds the walk on a malformed tree.
var seen: std.StringHashMapUnmanaged(void) = .empty;
defer seen.deinit(gpa);
var key_arena = std.heap.ArenaAllocator.init(gpa);
defer key_arena.deinit();
for (self.roots.items) |root| try work.append(gpa, .{ .name = root, .upper = null });
while (work.pop()) |v| {
const key = try std.fmt.allocPrint(key_arena.allocator(), "{s}\x00{s}{s}", .{
v.name, if (v.upper == null) "-" else "+", v.upper orelse "",
});
const fresh = try seen.getOrPut(gpa, key);
if (fresh.found_existing) continue;
const node = self.nodes.get(v.name) orelse continue;
for (node.names, node.hashes, 0..) |first, child, i| {
const limit: ?[]const u8 = if (i + 1 < node.names.len) node.names[i + 1] else v.upper;
const may = cone.slotMayCover(first, limit);
const gop = try verdicts.getOrPut(gpa, child);
gop.value_ptr.* = (gop.found_existing and gop.value_ptr.*) or may;
// Descend held nodes whatever their verdict: an out-of-cone
// node's absent children are elided by the same test.
if (self.nodes.contains(child)) try work.append(gpa, .{ .name = child, .upper = limit });
}
}
return verdicts;
}
fn lowerDupe(aa: std.mem.Allocator, s: []const u8) error{OutOfMemory}![]const u8 {
const out = try aa.alloc(u8, s.len);
return std.ascii.lowerString(out, s);
}
};
// ---------------------------------------------------------------------------
// 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 {
return self.checkinParents(ts, parent, 1, files, out);
}
/// `checkin` with `count` space-separated parent names, primary first.
fn checkinParents(self: *Fixture, ts: []const u8, parent: ?[]const u8, count: usize, 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 = count };
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, &cone, 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, with and without paths" {
const gpa = testing.allocator;
const no_paths: []const []const u8 = &.{};
const src_only: []const []const u8 = &.{"src"};
for ([_]cone_mod.HorizonRule{ .descendants, .leaves }) |rule| {
for ([_]cone_mod.HorizonDepth{ .content, .structural }) |depth| for ([_][]const []const u8{ no_paths, src_only }) |paths| {
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, paths, &.{}, .{ .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, &cone, 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);
if (paths.len > 0) try testing.expect(from_graph.elided(fx.rid(fx.f_other))); // above the horizon, outside the path cone
};
}
}
test "horizon §3.1: under the leaves rule K is closed under descendants, the meeting point's child toward C included" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
// b1 forks from c1, below C = c3: c1 is where its ancestry meets C's.
var cone = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = &fx.c3, .rule = .leaves, .depth = .structural });
defer cone.deinit(gpa);
var cls = try classifyKeepRids(gpa, fx.store(), &cone);
defer cls.deinit(gpa);
// c2, c1's child toward C, is held too: without it c1 would derive as a
// leaf, which the dense repository says it is not.
for ([_][]const u8{ &fx.c1, &fx.c2, &fx.c3, &fx.c4, &fx.b1 }) |m| try testing.expect(cls.keep.isSet(fx.rid(m)));
try testing.expectEqual(@as(usize, 0), cls.boundary.len);
}
test "horizon §5.2.1: the entries are C and every check-in of K whose primary parent is below the horizon" {
const gpa = testing.allocator;
var fx = Fixture{ .ms = repostate.MemStore.init(gpa) };
defer fx.ms.deinit();
try fx.build();
// m: the side leaf b1 merges c4. Its merge parent puts it in K; its
// primary parent, and so its branch, lies below the horizon.
var parents_buf: [129]u8 = undefined;
const parents = try std.fmt.bufPrint(&parents_buf, "{s} {s}", .{ &fx.b1, &fx.c4 });
const m_files = [_]artifact.FCard{ Fixture.fcard("src/branch.txt", fx.f_branch), Fixture.fcard("src/keep.txt", fx.f_keep) };
var m: [64]u8 = undefined;
try fx.checkinParents("2026-01-06T00:00:00", parents, 2, &m_files, &m);
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);
try testing.expect(cls.keep.isSet(fx.rid(&m)));
try testing.expectEqual(@as(usize, 2), cls.entries.len);
for ([_][]const u8{ &fx.c3, &m }) |e| try testing.expect(std.mem.indexOfScalar(repostate.Rid, cls.entries, fx.rid(e)) != null);
// c4's primary parent is C: its state propagates, and it is no entry.
try testing.expect(std.mem.indexOfScalar(repostate.Rid, cls.entries, fx.rid(&fx.c4)) == null);
}
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]);
}
// ---------------------------------------------------------------------------
// Tests. Goal: pin which absent sub-manifest nodes a cone elides -- wholly
// outside, inside an exclusion, out only by the bound a PARENT's next card
// sets -- and that a node straddling the cone boundary is never elided.
// Method: a two-level tree in a MemStore with the nodes a section 6.2 server
// would not send left out, classified under a two-member cone with an
// exclusion.
// ---------------------------------------------------------------------------
const TestTree = struct {
gpa: std.mem.Allocator,
ms: repostate.MemStore,
names: std.ArrayListUnmanaged([]u8) = .empty,
fn deinit(self: *TestTree) void {
for (self.names.items) |n| self.gpa.free(n);
self.names.deinit(self.gpa);
self.ms.deinit();
}
/// Name `bytes` and, when `held`, store them. Returns the name.
fn add(self: *TestTree, bytes: []const u8, held: bool) ![]const u8 {
var buf: [64]u8 = undefined;
const name = try self.gpa.dupe(u8, artifact.artifactName(.sha3_256, bytes, &buf));
errdefer self.gpa.free(name);
try self.names.append(self.gpa, name);
if (held) _ = try self.ms.store().put(name, bytes);
return name;
}
/// A card run sealed with its Z card; `letter` is 'F' or 'S'.
fn node(self: *TestTree, head: []const u8, letter: u8, cards: []const [2][]const u8, tail: []const u8, held: bool) ![]const u8 {
var body: std.ArrayListUnmanaged(u8) = .empty;
defer body.deinit(self.gpa);
try body.appendSlice(self.gpa, head);
for (cards) |c| try body.print(self.gpa, "{c} {s} {s}\n", .{ letter, c[0], c[1] });
try body.appendSlice(self.gpa, tail);
var digest: [16]u8 = undefined;
std.crypto.hash.Md5.hash(body.items, &digest, .{});
try body.print(self.gpa, "Z {x}\n", .{&digest});
return self.add(body.items, held);
}
fn leaf(self: *TestTree, paths: []const []const u8, held: bool) ![]const u8 {
var cards: [4][2][]const u8 = undefined;
for (paths, 0..) |p, i| cards[i] = .{ p, try self.add(p, held) };
return self.node("", 'F', cards[0..paths.len], "", held);
}
};
test "sparse classifyKeepRids: absent sub-manifest nodes elide by slot, never across the boundary" {
const gpa = testing.allocator;
var t: TestTree = .{ .gpa = gpa, .ms = repostate.MemStore.init(gpa) };
defer t.deinit();
// Absent nodes are the ones a section 6.2 server skips, plus one it
// must not skip (the straddler) to prove that absence stays a hole.
const l_docs = try t.leaf(&.{ "docs/a", "docs/b" }, false); // wholly before
// Starts below `lib`: a slot ending at `lib/a` could still hold the
// path `lib` itself, so the slot before must end at or below it.
const l_lib = try t.leaf(&.{ "kit/a", "lib/a" }, true);
const l_mid = try t.leaf(&.{ "m/a", "n/a" }, false); // out only by I1's bound, rc/x
const l_straddle = try t.leaf(&.{ "rc/x", "src/a" }, false); // in: reaches src/a
const l_gen = try t.leaf(&.{ "src/gen/a", "src/gen/b" }, false); // inside the exclusion
const l_gen_tail = try t.leaf(&.{ "src/gen/c", "src/gen/d" }, true); // runs past it to src/h
const l_src = try t.leaf(&.{ "src/h", "src/z" }, true);
const l_zzz = try t.leaf(&.{"zzz/a"}, false);
const i_low = try t.node("", 'S', &.{ .{ "docs/a", l_docs }, .{ "kit/a", l_lib }, .{ "m/a", l_mid } }, "", true);
const i_src = try t.node("", 'S', &.{ .{ "rc/x", l_straddle }, .{ "src/gen/a", l_gen }, .{ "src/gen/c", l_gen_tail }, .{ "src/h", l_src } }, "", true);
const i_high = try t.node("", 'S', &.{.{ "zzz/a", l_zzz }}, "", false); // wholly after
_ = try t.node(
"C tree\nD 2026-10-21T12:00:00.000\n",
'S',
&.{ .{ "docs/a", i_low }, .{ "rc/x", i_src }, .{ "zzz/a", i_high } },
"U u\n",
true,
);
var cone = try cone_mod.Cone.init(gpa, &.{ "lib", "src" }, &.{"src/gen"});
defer cone.deinit(gpa);
var c = try classifyKeepRids(gpa, t.ms.store(), &cone);
defer c.deinit(gpa);
try testing.expect(c.elidedNode(l_docs));
try testing.expect(c.elidedNode(l_mid));
try testing.expect(c.elidedNode(l_gen));
try testing.expect(c.elidedNode(i_high));
try testing.expect(!c.elidedNode(l_straddle));
// Held nodes are never elided, whatever their slots; and a node no held
// artifact names (l_zzz, under the absent i_high) is not classified.
for ([_][]const u8{ l_lib, l_gen_tail, l_src, i_low, i_src, l_zzz }) |n| try testing.expect(!c.elidedNode(n));
// The case of the name does not matter (submanifests §3.5).
var upper: [64]u8 = undefined;
try testing.expect(c.elidedNode(std.ascii.upperString(&upper, l_docs)));
// Without the exclusion, the excluded leaf is in the cone again.
var plain = try cone_mod.Cone.init(gpa, &.{ "lib", "src" }, &.{});
defer plain.deinit(gpa);
var c2 = try classifyKeepRids(gpa, t.ms.store(), &plain);
defer c2.deinit(gpa);
try testing.expect(!c2.elidedNode(l_gen));
try testing.expect(c2.elidedNode(l_mid));
}
test "sparse classifyKeepRids: an origin serving a cone keeps only the held nodes whose slots reach it" {
const gpa = testing.allocator;
var t: TestTree = .{ .gpa = gpa, .ms = repostate.MemStore.init(gpa) };
defer t.deinit();
// The same tree as above, every node held, as on a dense origin.
const l_docs = try t.leaf(&.{ "docs/a", "docs/b" }, true);
const l_lib = try t.leaf(&.{ "kit/a", "lib/a" }, true);
const l_mid = try t.leaf(&.{ "m/a", "n/a" }, true);
const l_straddle = try t.leaf(&.{ "rc/x", "src/a" }, true);
const l_gen = try t.leaf(&.{ "src/gen/a", "src/gen/b" }, true);
const l_gen_tail = try t.leaf(&.{ "src/gen/c", "src/gen/d" }, true);
const l_src = try t.leaf(&.{ "src/h", "src/z" }, true);
const l_zzz = try t.leaf(&.{"zzz/a"}, true);
const i_low = try t.node("", 'S', &.{ .{ "docs/a", l_docs }, .{ "kit/a", l_lib }, .{ "m/a", l_mid } }, "", true);
const i_src = try t.node("", 'S', &.{ .{ "rc/x", l_straddle }, .{ "src/gen/a", l_gen }, .{ "src/gen/c", l_gen_tail }, .{ "src/h", l_src } }, "", true);
const i_high = try t.node("", 'S', &.{.{ "zzz/a", l_zzz }}, "", true);
const root = try t.node(
"C tree\nD 2026-10-21T12:00:00.000\n",
'S',
&.{ .{ "docs/a", i_low }, .{ "rc/x", i_src }, .{ "zzz/a", i_high } },
"U u\n",
true,
);
var cone = try cone_mod.Cone.init(gpa, &.{ "lib", "src" }, &.{"src/gen"});
defer cone.deinit(gpa);
const s = t.ms.store();
const kept = struct {
fn f(c: *const SparseClassification, st: repostate.ArtifactStore, name: []const u8) bool {
const rid = st.lookup(name).?;
return rid < c.keep.capacity() and c.keep.isSet(rid);
}
}.f;
// Section 6.2: a server descends only the slots that may reach the cone,
// so the nodes no such slot names are neither sent nor answered. Every
// node on a path to a covered slot stays, the straddler included.
var served = try classifyKeepRidsOpts(gpa, s, &cone, .{ .intern_absent = false, .slot_held_nodes = true });
defer served.deinit(gpa);
for ([_][]const u8{ l_docs, l_mid, l_gen, i_high, l_zzz }) |n| {
try testing.expect(!kept(&served, s, n));
try testing.expect(served.elided(s.lookup(n).?));
}
for ([_][]const u8{ root, i_low, i_src, l_lib, l_straddle, l_gen_tail, l_src }) |n| try testing.expect(kept(&served, s, n));
// A client keeps every node it holds: dropping one would make a commit
// fetch it again.
var held = try classifyKeepRids(gpa, s, &cone);
defer held.deinit(gpa);
for ([_][]const u8{ l_docs, l_mid, l_gen, i_high, l_zzz, root, i_low, i_src }) |n| try testing.expect(kept(&held, s, n));
}
test "sparse classifyKeepRids: under a structural horizon only K's trees elide absent nodes by slot" {
const gpa = testing.allocator;
var t: TestTree = .{ .gpa = gpa, .ms = repostate.MemStore.init(gpa) };
defer t.deinit();
// c1 -> c2 (C) -> c3, each naming one absent out-of-cone leaf of its own
// after a shared held in-cone one, so the leaf's slot is unbounded above
// and starts past `src`. c3 arrives in a second extension.
const l_src = try t.leaf(&.{ "src/a", "src/b" }, true);
const l_old = try t.leaf(&.{ "zz/1", "zz/2" }, false);
const l_c = try t.leaf(&.{ "zz/3", "zz/4" }, false);
const l_new = try t.leaf(&.{ "zz/5", "zz/6" }, false);
const c1 = try t.node("C one\nD 2026-10-21T12:00:00.000\n", 'S', &.{ .{ "src/a", l_src }, .{ "zz/1", l_old } }, "U u\n", true);
const head2 = try std.fmt.allocPrint(gpa, "C two\nD 2026-10-21T12:01:00.000\nP {s}\n", .{c1});
defer gpa.free(head2);
const c2 = try t.node(head2, 'S', &.{ .{ "src/a", l_src }, .{ "zz/3", l_c } }, "U u\n", true);
var structural = try cone_mod.Cone.initHorizon(gpa, &.{"src"}, &.{}, .{ .hash = c2, .rule = .descendants, .depth = .structural });
defer structural.deinit(gpa);
var st = try ClassifyState.init(gpa, t.ms.store().count());
defer st.deinit(gpa);
try st.extend(gpa, t.ms.store(), &structural, .{}, .parse);
const head3 = try std.fmt.allocPrint(gpa, "C three\nD 2026-10-21T12:02:00.000\nP {s}\n", .{c2});
defer gpa.free(head3);
_ = try t.node(head3, 'S', &.{ .{ "src/a", l_src }, .{ "zz/5", l_new } }, "U u\n", true);
try st.extend(gpa, t.ms.store(), &structural, .{}, .parse);
var c = try st.finalize(gpa, t.ms.store(), &structural, .{});
defer c.deinit(gpa);
try testing.expect(c.elidedNode(l_c));
try testing.expect(c.elidedNode(l_new)); // a tree that joined K in a later extension
try testing.expect(!c.elidedNode(l_old)); // below the horizon: not K's tree
try testing.expect(!c.elidedNode(l_src));
// A content horizon keeps every tree, so every tree's slots decide.
var content = try cone_mod.Cone.initHorizon(gpa, &.{"src"}, &.{}, .{ .hash = c2, .rule = .descendants });
defer content.deinit(gpa);
var c_content = try classifyKeepRids(gpa, t.ms.store(), &content);
defer c_content.deinit(gpa);
for ([_][]const u8{ l_old, l_c, l_new }) |n| try testing.expect(c_content.elidedNode(n));
// A horizon with no path members covers every path: nothing elides by slot.
var history_only = try cone_mod.Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = c2, .rule = .descendants, .depth = .structural });
defer history_only.deinit(gpa);
var c_history = try classifyKeepRids(gpa, t.ms.store(), &history_only);
defer c_history.deinit(gpa);
try testing.expectEqual(@as(usize, 0), c_history.elided_nodes.count());
}