//! Sparse-cone classification (draft-fossil-sparse-cone-00 sections 5.1,
//! 5.2, 6.3): 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");
/// Sparse-cone RFC sections 5.1 and 6.3, Wave-2 posture: 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 names, every attachment source, and -- conservatively --
/// every blob nothing references at all. ELIDES exactly the blobs whose
/// every reference is an out-of-cone F card, and the absent sub-manifest
/// nodes 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 OUT-of-cone F card.
/// `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
/// filename 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),
/// Owns `elided_nodes`' keys.
arena: std.heap.ArenaAllocator,
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();
self.* = undefined;
}
};
/// 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 fn classifyKeepRids(
gpa: std.mem.Allocator,
store: repostate.ArtifactStore,
sparse: *const cone_mod.Cone,
) error{OutOfMemory}!SparseClassification {
const n = store.count();
var keep = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
errdefer keep.deinit(gpa);
var referenced = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
errdefer referenced.deinit(gpa);
var trees = TreeSlots.init(gpa);
defer trees.deinit();
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
var rid: repostate.Rid = 1;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
const plain = store.content(rid) orelse continue;
_ = arena_state.reset(.retain_capacity);
const aa = arena_state.allocator();
const im = artifact.parseForImport(aa, plain) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
// Not structural: a content blob. Classified by its referencers.
else => continue,
};
keep.set(rid); // every structural artifact persists (spine included)
try trees.note(store.hashOf(rid), &im.manifest);
// 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 (im.manifest.f) |fc| {
const h = fc.hash orelse continue; // delete marker names nothing
const target = store.lookup(h) orelse continue; // absent = already phantom
if (sparse.covers(fc.filename)) {
keep.set(target);
} else {
referenced.set(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 (im.manifest.a) |a| {
if (a.source) |src| {
if (store.lookup(src)) |target| keep.set(target);
}
}
}
// Sub-manifest nodes by slot. A held node is structural and already
// kept; an absent one is elided only when no slot naming it may hold a
// covered path, the same interval test a section 6.2 server descends by.
var verdicts = try trees.classify(sparse);
defer verdicts.deinit(gpa);
var node_arena = std.heap.ArenaAllocator.init(gpa);
errdefer node_arena.deinit();
var elided_nodes: std.StringHashMapUnmanaged(void) = .empty;
errdefer elided_nodes.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)) continue;
try elided_nodes.put(gpa, try node_arena.allocator().dupe(u8, e.key_ptr.*), {});
}
// A held blob nothing referenced stays: unknown provenance is kept, and
// "referenced only out-of-cone" is the sole elision.
rid = 1;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
if (keep.isSet(rid)) continue;
if (!referenced.isSet(rid)) keep.set(rid);
}
return .{ .keep = keep, .out_only = referenced, .elided_nodes = elided_nodes, .arena = node_arena };
}
/// 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 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 testing = std.testing;
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));
}