//! Sparse cones: draft-fossil-sparse-cone-00 §3.
//!
//! A cone is a finite, normalized set of repository-relative path prefixes,
//! each an inclusion or an exclusion. It covers a path when the most
//! specific (longest) member covering the path is an inclusion. The absent
//! cone (no `Cone` value at all) means dense operation; that case never
//! reaches this module — callers hold `?Cone`.
//!
//! Members are stored sorted and minimal: a member whose nearest covering
//! member has the same polarity is dropped at construction (§3.2), which
//! makes the serialized form canonical — two cones with the same coverage
//! serialize identically, so `digest` is a cache key. Longest-match is
//! order-independent (any two prefix members covering one path are nested),
//! which is what lets the stored form stay sorted rather than ordered.
const std = @import("std");
const control_paths = @import("control_paths.zig");
const managed = @import("managed.zig");
/// Spec §8: member length shares the tracked-path bound, so a cone card can
/// never smuggle a longer byte string than an F card could.
pub const max_member_len: usize = managed.max_path_len;
/// Spec section 3.2: at least 64, SHOULD 255 -- scattered-file profiles
/// (individual root files beside directory subtrees) are first-class, so
/// the bound is the count byte's full range. The cap is on inclusions and
/// exclusions TOGETHER (one count byte in the serialized form). Fixed, so
/// every loop below is finite by inspection.
pub const max_members: usize = 255;
/// Serialized-form version byte for cones carrying exclusions. A version-1
/// form has no version byte at all: its first byte is a nonzero member
/// count, so the 0x00 lead-in of later versions can never collide with it.
pub const serial_version_exclusions: u8 = 2;
/// Serialized-form version byte for cones carrying a horizon member
/// (draft-fossil-horizon §3.3; sparse-cone §3.1's member-kinds rule). A
/// distinct version so an implementation predating horizons refuses the
/// cone rather than reads its lead-in as path members.
pub const serial_version_horizon: u8 = 3;
/// draft-fossil-horizon §3.1 -- the held-set rule a horizon names. The byte
/// values are the serialized form; never renumber.
pub const HorizonRule = enum(u8) {
/// K is C and every descendant of C.
descendants = 0,
/// K is the descendants set plus every open leaf's ancestry back to its
/// nearest common ancestor with C.
leaves = 1,
pub fn name(self: HorizonRule) []const u8 {
return switch (self) {
.descendants => "descendants",
.leaves => "leaves",
};
}
pub fn parse(token: []const u8) ?HorizonRule {
return std.meta.stringToEnum(HorizonRule, token);
}
};
/// draft-fossil-horizon §1.1 -- which cut a horizon takes. The byte values
/// are the serialized form; never renumber.
pub const HorizonDepth = enum(u8) {
/// §4: every structural artifact held; only blobs below the horizon elided.
content = 0,
/// §5: manifests and nodes below the horizon elided too; a seed stands in
/// for the absent ancestry. Needs an origin.
structural = 1,
pub fn name(self: HorizonDepth) []const u8 {
return switch (self) {
.content => "content",
.structural => "structural",
};
}
};
/// draft-fossil-horizon §3.1 -- the temporal member of a cone: a check-in C
/// by full artifact hash, the rule that derives the held set K from it, and
/// the depth of the cut. The hash is the canonical lower-case hex of the
/// artifact name, 40 or 64 digits, owned by the cone.
pub const Horizon = struct {
hash: []const u8,
rule: HorizonRule,
depth: HorizonDepth = .content,
/// Validate a raw hash token: 40 or 64 hex digits. Case is not an
/// error; `initHorizon` lower-cases what it stores.
pub fn validHash(token: []const u8) bool {
if (token.len != 40 and token.len != 64) return false;
for (token) |c| {
if (!std.ascii.isHex(c)) return false;
}
return true;
}
};
comptime {
// The serialized form's u16 length prefix must hold any legal member.
std.debug.assert(max_member_len <= std.math.maxInt(u16));
// The count byte in the serialized form must hold max_members.
std.debug.assert(max_members <= std.math.maxInt(u8));
}
pub const Error = error{
OutOfMemory,
/// A member failed worktree-path validation (§3.2 defers to the same
/// rules as tracked paths) or exceeded `max_member_len`.
InvalidMember,
/// A member names a reserved control root.
ReservedMember,
/// More than `max_members` in total, or zero inclusions.
Bounds,
/// An exclusion no inclusion covers: a dead rule, refused as operator
/// error (§3.2).
DeadExclusion,
/// One path given as both an inclusion and an exclusion.
Contradiction,
};
/// One member during normalization: the path and its polarity.
const Entry = struct {
path: []const u8,
exclude: bool,
};
/// A normalized cone. Owns its member bytes.
pub const Cone = struct {
/// Inclusions, sorted ascending, each validated. Never empty.
members: []const []const u8,
/// Exclusions, sorted ascending, each validated. Each is strictly
/// covered by some inclusion (dead rules are refused). Empty for a
/// cone with no exclusions.
not_members: []const []const u8,
/// draft-fossil-horizon §3.2 -- the temporal member, or null for a cone
/// of path members only. A cone MAY carry a horizon and no path members
/// at all: it then covers every path and elides by history alone.
horizon: ?Horizon = null,
/// Build from raw operator input (`--cone` / `--cone-not` values).
/// Validates every member, sorts, and drops members whose nearest
/// covering member has the same polarity. The result is canonical:
/// input order never affects the stored form.
pub fn init(
gpa: std.mem.Allocator,
raw: []const []const u8,
raw_not: []const []const u8,
) Error!Cone {
return initImpl(gpa, raw, raw_not, null);
}
/// Build a cone carrying a horizon member (draft-fossil-horizon §3.2),
/// with or without path members. `horizon.hash` is validated and copied
/// lower-cased; path members are normalized exactly as `init` does.
pub fn initHorizon(
gpa: std.mem.Allocator,
raw: []const []const u8,
raw_not: []const []const u8,
horizon: Horizon,
) Error!Cone {
return initImpl(gpa, raw, raw_not, horizon);
}
fn initImpl(
gpa: std.mem.Allocator,
raw: []const []const u8,
raw_not: []const []const u8,
horizon: ?Horizon,
) Error!Cone {
if (horizon) |h| {
if (!Horizon.validHash(h.hash)) return error.InvalidMember;
}
if (raw.len == 0) {
// Path-less: legal only as a horizon-only cone, and then an
// exclusion has nothing to subtract from (§3.3's dead rule).
if (horizon == null) return error.Bounds;
if (raw_not.len != 0) return error.DeadExclusion;
const owned_hash = try std.ascii.allocLowerString(gpa, horizon.?.hash);
errdefer gpa.free(owned_hash);
const members = try gpa.alloc([]const u8, 0);
errdefer gpa.free(members);
const not_members = try gpa.alloc([]const u8, 0);
return .{ .members = members, .not_members = not_members, .horizon = .{ .hash = owned_hash, .rule = horizon.?.rule, .depth = horizon.?.depth } };
}
if (raw.len + raw_not.len > max_members) return error.Bounds;
for ([2][]const []const u8{ raw, raw_not }) |list| {
for (list) |member| {
if (member.len > max_member_len) return error.InvalidMember;
control_paths.validateWorktreePath(member) catch |e| switch (e) {
error.InvalidPath => return error.InvalidMember,
error.ReservedPath => return error.ReservedMember,
};
}
}
var entries: [max_members]Entry = undefined;
var entry_count: usize = 0;
for (raw) |m| {
entries[entry_count] = .{ .path = m, .exclude = false };
entry_count += 1;
}
for (raw_not) |m| {
entries[entry_count] = .{ .path = m, .exclude = true };
entry_count += 1;
}
std.debug.assert(entry_count == raw.len + raw_not.len);
std.mem.sort(Entry, entries[0..entry_count], {}, entryLess);
var kept_members: std.ArrayList([]u8) = .empty;
var kept_not: std.ArrayList([]u8) = .empty;
errdefer {
for (kept_members.items) |m| gpa.free(m);
kept_members.deinit(gpa);
for (kept_not.items) |m| gpa.free(m);
kept_not.deinit(gpa);
}
try normalize(gpa, entries[0..entry_count], &kept_members, &kept_not);
std.debug.assert(kept_members.items.len >= 1);
std.debug.assert(kept_members.items.len + kept_not.items.len <= entry_count);
const members = try gpa.alloc([]const u8, kept_members.items.len);
errdefer gpa.free(members);
for (kept_members.items, 0..) |m, i| members[i] = m;
const not_members = try gpa.alloc([]const u8, kept_not.items.len);
errdefer gpa.free(not_members);
for (kept_not.items, 0..) |m, i| not_members[i] = m;
const owned_horizon: ?Horizon = if (horizon) |h|
.{ .hash = try std.ascii.allocLowerString(gpa, h.hash), .rule = h.rule, .depth = h.depth }
else
null;
kept_members.deinit(gpa);
kept_not.deinit(gpa);
return .{ .members = members, .not_members = not_members, .horizon = owned_horizon };
}
pub fn deinit(self: *Cone, gpa: std.mem.Allocator) void {
std.debug.assert(self.members.len >= 1 or self.horizon != null); // Constructed cones are never empty.
for (self.members) |m| gpa.free(m);
gpa.free(self.members);
for (self.not_members) |m| gpa.free(m);
gpa.free(self.not_members);
if (self.horizon) |h| gpa.free(h.hash);
self.* = undefined;
}
/// Whether this cone restricts by path at all. A horizon-only cone does
/// not: every path is covered and only history elides.
pub fn hasPathMembers(self: *const Cone) bool {
return self.members.len != 0;
}
/// Whether the cone covers `path` (§2): the longest member covering the
/// path decides, and it decides by its polarity.
pub fn covers(self: *const Cone, path: []const u8) bool {
return self.decide(path).covered;
}
/// The same rule as `covers`, with the member that applied it. The
/// verdict alone cannot answer "why isn't this file here" — under
/// longest match the deciding member is often neither the first nor the
/// most obvious one, and an operator carrying the gitignore habit of
/// last-match-wins will read the member list in the wrong order. Naming
/// the member is what makes the rule legible.
///
/// A bounded linear scan over both member lists — ties are impossible (a
/// path carried with both polarities is refused at construction, and two
/// distinct members of equal length cannot both be prefixes of one path).
pub fn decide(self: *const Cone, path: []const u8) Decision {
std.debug.assert(self.members.len >= 1 or self.horizon != null);
std.debug.assert(self.members.len + self.not_members.len <= max_members);
if (self.members.len == 0) return .{ .covered = true, .member = null }; // horizon-only: path-dense
var best: ?[]const u8 = null;
var best_exclude = false;
for (self.members) |m| {
if (m.len >= (if (best) |b| b.len else 0) and memberCovers(m, path)) {
best = m;
best_exclude = false;
}
}
for (self.not_members) |m| {
if (m.len > (if (best) |b| b.len else 0) and memberCovers(m, path)) {
best = m;
best_exclude = true;
}
}
const member = best orelse return .{ .covered = false, .member = null };
return .{ .covered = !best_exclude, .member = member };
}
/// Whether the subtree rooted at `dir` can contain any covered path:
/// either the cone covers `dir` itself or some inclusion lies inside
/// the subtree (a deeper re-inclusion under an exclusion counts, which
/// is why only inclusions are probed). Conservative on hollowed-out
/// subtrees: descending into one is a cost, never an error. Bounded by
/// `max_members`. `dir` is a validated worktree path, never "".
pub fn intersectsSubtree(self: *const Cone, dir: []const u8) bool {
std.debug.assert(dir.len >= 1);
std.debug.assert(self.members.len >= 1 or self.horizon != null);
if (self.covers(dir)) return true;
for (self.members) |member| {
if (memberCovers(dir, member)) return true; // member inside dir's subtree
}
return false;
}
/// Classify a sorted key interval `[first, last]` (inclusive on both
/// ends — sub-manifest nodes carry first-key and can report their last
/// key) against the cone, for S-node descent pruning (§1.3).
///
/// Exclusions narrow contiguity rather than break it (§3.2): a range
/// wholly inside an inclusion and wholly outside every exclusion is
/// `.contained`; a range an exclusion touches degrades to `.partial`
/// and is classified per file. Conservative in both directions —
/// over-descending is a cost, never an error.
pub fn coversRange(self: *const Cone, first: []const u8, last: []const u8) RangeClass {
std.debug.assert(self.members.len >= 1 or self.horizon != null);
std.debug.assert(std.mem.order(u8, first, last) != .gt);
if (self.members.len == 0) return .contained; // horizon-only: path-dense
var any_overlap = false;
var contained_by_inclusion = false;
// Bounded by `max_members`, asserted at construction. Joint coverage
// by several members reports `.partial`, not `.contained`.
for (self.members) |member| {
switch (memberVsRange(member, first, last)) {
.disjoint => {},
.partial => any_overlap = true,
.contains_range => contained_by_inclusion = true,
}
}
if (!any_overlap and !contained_by_inclusion) return .disjoint;
if (contained_by_inclusion) {
for (self.not_members) |member| {
if (memberVsRange(member, first, last) != .disjoint) return .partial;
}
return .contained;
}
return .partial;
}
/// Canonical serialized form. Without exclusions this is the version-1
/// form (count byte, then per member a u16 LE length and the bytes) —
/// exclusion-free cones keep their digest across this extension. With
/// exclusions: a 0x00 lead-in (impossible as a v1 count), the version
/// byte, the total count, then per member a polarity flag byte, the
/// u16 LE length, and the bytes, in one sorted order across both
/// polarities. Canonical because members are sorted-minimal.
pub fn serialize(self: *const Cone, gpa: std.mem.Allocator) error{OutOfMemory}![]u8 {
std.debug.assert(self.members.len >= 1 or self.horizon != null);
std.debug.assert(self.members.len + self.not_members.len <= max_members);
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(gpa);
if (self.horizon == null and self.not_members.len == 0) {
try out.append(gpa, @intCast(self.members.len));
for (self.members) |m| try appendMember(gpa, &out, m, null);
return out.toOwnedSlice(gpa);
}
try out.append(gpa, 0);
if (self.horizon) |h| {
// Version-3 form: after the count, the horizon as a rule byte, a
// depth byte, a hash-length byte and the hash digits, then the
// flagged members.
std.debug.assert(h.hash.len == 40 or h.hash.len == 64);
try out.append(gpa, serial_version_horizon);
try out.append(gpa, @intCast(self.members.len + self.not_members.len));
try out.append(gpa, @backingInt(h.rule));
try out.append(gpa, @backingInt(h.depth));
try out.append(gpa, @intCast(h.hash.len));
try out.appendSlice(gpa, h.hash);
} else {
try out.append(gpa, serial_version_exclusions);
try out.append(gpa, @intCast(self.members.len + self.not_members.len));
}
// Two-way merge of the sorted lists keeps one global sorted order.
var index_in: usize = 0;
var index_not: usize = 0;
while (index_in < self.members.len or index_not < self.not_members.len) {
const take_in = blk: {
if (index_in == self.members.len) break :blk false;
if (index_not == self.not_members.len) break :blk true;
const in_path = self.members[index_in];
const not_path = self.not_members[index_not];
break :blk std.mem.order(u8, in_path, not_path) == .lt;
};
if (take_in) {
try appendMember(gpa, &out, self.members[index_in], 0);
index_in += 1;
} else {
try appendMember(gpa, &out, self.not_members[index_not], 1);
index_not += 1;
}
}
return out.toOwnedSlice(gpa);
}
/// Parse the serialized form. Rejects anything `serialize` cannot emit:
/// authoritative checkout state is never best-effort parsed.
pub fn parse(gpa: std.mem.Allocator, bytes: []const u8) Error!Cone {
if (bytes.len < 1) return error.InvalidMember;
var raw: std.ArrayList([]const u8) = .empty;
defer raw.deinit(gpa);
var raw_not: std.ArrayList([]const u8) = .empty;
defer raw_not.deinit(gpa);
var offset: usize = undefined;
var count: usize = undefined;
var flagged = false;
var horizon: ?Horizon = null;
if (bytes[0] == 0) {
// Versioned form: 0x00 lead-in, version byte, count byte. An
// unknown version is refused, never read as path members
// (sparse-cone §3.1).
if (bytes.len < 3) return error.InvalidMember;
count = bytes[2];
offset = 3;
flagged = true;
switch (bytes[1]) {
serial_version_exclusions => {},
serial_version_horizon => {
if (bytes.len - offset < 3) return error.InvalidMember;
const rule: HorizonRule = switch (bytes[offset]) {
@backingInt(HorizonRule.descendants) => .descendants,
@backingInt(HorizonRule.leaves) => .leaves,
else => return error.InvalidMember,
};
const depth: HorizonDepth = switch (bytes[offset + 1]) {
@backingInt(HorizonDepth.content) => .content,
@backingInt(HorizonDepth.structural) => .structural,
else => return error.InvalidMember,
};
const hash_len: usize = bytes[offset + 2];
offset += 3;
if (hash_len != 40 and hash_len != 64) return error.InvalidMember;
if (bytes.len - offset < hash_len) return error.InvalidMember;
horizon = .{ .hash = bytes[offset..][0..hash_len], .rule = rule, .depth = depth };
offset += hash_len;
},
else => return error.InvalidMember,
}
} else {
count = bytes[0];
offset = 1;
}
if (count == 0 and horizon == null) return error.Bounds;
if (count > max_members) return error.Bounds;
var index: usize = 0;
while (index < count) : (index += 1) {
var exclude = false;
if (flagged) {
if (bytes.len - offset < 1) return error.InvalidMember;
switch (bytes[offset]) {
0 => {},
1 => exclude = true,
else => return error.InvalidMember,
}
offset += 1;
}
if (bytes.len - offset < 2) return error.InvalidMember;
const len = std.mem.readInt(u16, bytes[offset..][0..2], .little);
offset += 2;
if (len == 0) return error.InvalidMember;
if (bytes.len - offset < len) return error.InvalidMember;
const member = bytes[offset..][0..len];
offset += len;
if (exclude) {
try raw_not.append(gpa, member);
} else {
try raw.append(gpa, member);
}
}
if (offset != bytes.len) return error.InvalidMember; // No residue.
var cone = try Cone.initImpl(gpa, raw.items, raw_not.items, horizon);
errdefer cone.deinit(gpa);
// Round-trip identity: stored state must already be canonical. A
// stored cone whose normalization changes it was not written by
// `serialize`, and authoritative state fails closed.
const canonical = try cone.serialize(gpa);
defer gpa.free(canonical);
if (!std.mem.eql(u8, canonical, bytes)) return error.InvalidMember;
return cone;
}
/// SHA3-256 over the canonical serialized form, for cache keys (§7).
pub fn digest(self: *const Cone, gpa: std.mem.Allocator) error{OutOfMemory}![32]u8 {
const bytes = try self.serialize(gpa);
defer gpa.free(bytes);
var out: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(bytes, &out, .{});
return out;
}
};
pub const RangeClass = enum { disjoint, partial, contained };
/// A coverage verdict together with the member that produced it.
pub const Decision = struct {
/// The answer `covers` would give.
covered: bool,
/// The longest member covering the path, borrowed from the cone and
/// valid for its lifetime. Null exactly when no member covers the path,
/// which is the one case where `covered` is false with nothing to name.
/// Non-null with `covered` false means the decider was an exclusion.
member: ?[]const u8,
};
/// One serialized member: optional polarity flag, u16 LE length, bytes.
fn appendMember(
gpa: std.mem.Allocator,
out: *std.ArrayList(u8),
member: []const u8,
flag: ?u8,
) error{OutOfMemory}!void {
std.debug.assert(member.len >= 1);
std.debug.assert(member.len <= max_member_len);
if (flag) |f| try out.append(gpa, f);
var len_bytes: [2]u8 = undefined;
std.mem.writeInt(u16, &len_bytes, @intCast(member.len), .little);
try out.appendSlice(gpa, &len_bytes);
try out.appendSlice(gpa, member);
}
/// §3.2 normalization over the sorted entry list: keep a member iff its
/// nearest covering kept member has the opposite polarity (or, for an
/// inclusion, there is none); refuse a dead exclusion and a both-polarity
/// path. A covering member is a byte-prefix, so it sorts before everything
/// it covers and is already kept (or dropped as redundant against a kept
/// member of ITS polarity, which decides the same way) when a descendant
/// arrives. The nearest-ancestor probe is a bounded linear scan over the
/// kept lists, NOT a path stack: sorted order interleaves non-covered
/// siblings inside a member's byte range (`src-other` sorts between `src`
/// and `src/vendor`, since '-' < '/'), so a pop-on-mismatch stack would
/// discard ancestors that later entries still need.
fn normalize(
gpa: std.mem.Allocator,
sorted: []const Entry,
kept_members: *std.ArrayList([]u8),
kept_not: *std.ArrayList([]u8),
) Error!void {
std.debug.assert(sorted.len >= 1);
std.debug.assert(sorted.len <= max_members);
var previous: ?Entry = null;
for (sorted) |entry| {
if (previous) |prev| {
if (std.mem.eql(u8, prev.path, entry.path)) {
if (prev.exclude != entry.exclude) return error.Contradiction;
continue; // Exact duplicate: drop.
}
}
previous = entry;
// Longest kept member covering this entry, either polarity: the
// nearest ancestor. Bounded by max_members per list.
var best_len: usize = 0;
var best_exclude = false;
for (kept_members.items) |m| {
if (m.len > best_len and memberCovers(m, entry.path)) {
best_len = m.len;
best_exclude = false;
}
}
for (kept_not.items) |m| {
if (m.len > best_len and memberCovers(m, entry.path)) {
best_len = m.len;
best_exclude = true;
}
}
if (best_len == 0) {
if (entry.exclude) return error.DeadExclusion;
} else {
if (best_exclude == entry.exclude) continue; // Redundant: drop.
}
const copy = try gpa.dupe(u8, entry.path);
errdefer gpa.free(copy);
if (entry.exclude) {
try kept_not.append(gpa, copy);
} else {
try kept_members.append(gpa, copy);
}
}
if (kept_members.items.len == 0) return error.Bounds;
}
fn entryLess(_: void, a: Entry, b: Entry) bool {
return std.mem.order(u8, a.path, b.path) == .lt;
}
/// Whether `member` covers `path`: equality, or prefix at a `/` boundary.
fn memberCovers(member: []const u8, path: []const u8) bool {
std.debug.assert(member.len >= 1);
if (path.len < member.len) return false;
if (!std.mem.eql(u8, member, path[0..member.len])) return false;
if (path.len == member.len) return true;
return path[member.len] == '/';
}
/// Classify one member against a key interval. The member's covered
/// interval is [member, member ++ "/" ++ 0xFF...): every path it covers
/// sorts at or after `member` and before the first path with a sibling
/// prefix. Conservative on `.partial`: descent then filters per file, so
/// over-descending is a cost, never an error.
fn memberVsRange(member: []const u8, first: []const u8, last: []const u8) enum {
disjoint,
partial,
contains_range,
} {
std.debug.assert(member.len >= 1);
// Whole range inside the member's subtree: both endpoints covered.
if (memberCovers(member, first) and memberCovers(member, last)) return .contains_range;
// Disjoint: the member's interval ends before `first` or begins after
// `last`. The interval begins at `member` itself; it ends before any
// path that is not covered and sorts after the member's subtree.
if (std.mem.order(u8, member, last) == .gt) return .disjoint;
// `member` <= last. If `first` sorts after the member's subtree, the
// subtree ended before the range began.
if (std.mem.order(u8, first, member) == .gt and !memberCovers(member, first)) {
// `first` > member and not covered: disjoint only if no covered
// path can sort at or after `first`, i.e. the subtree's upper
// bound `member ++ '/'` (exclusive of longer shared prefixes) is
// below `first`'s prefix of the same length. Conservative check:
// compare `first` against `member` with a virtual trailing '/'.
const boundary_order = orderWithBoundary(member, first);
if (boundary_order == .lt) return .disjoint;
}
return .partial;
}
/// Order `member ++ "/"`'s subtree upper bound against `path`, without
/// allocating: `.lt` when every path in the member's subtree sorts before
/// `path`.
fn orderWithBoundary(member: []const u8, path: []const u8) std.math.Order {
const shared = @min(member.len, path.len);
const cmp = std.mem.order(u8, member[0..shared], path[0..shared]);
if (cmp != .eq) return cmp;
if (path.len <= member.len) return .gt; // `path` is a prefix of member.
// `path` extends `member`. The subtree covers exactly the extensions
// whose next byte is '/'; a smaller next byte sorts before the whole
// subtree, a larger one after it.
if (path[member.len] < '/') return .gt;
if (path[member.len] == '/') return .eq; // Covered territory.
return .lt;
}
// ---------------------------------------------------------------------------
// Tests. Goal: pin the §3.2 normalization table including polarity (dead
// exclusion, contradiction, redundancy, re-inclusion), the covers/coversRange
// truth tables including subtree boundary bytes ('.' < '/' < '0'), canonical
// serialization in both forms, fail-closed parsing, and digest stability
// under member permutation. Method: table-driven cases over fixture cones.
// ---------------------------------------------------------------------------
const testing = std.testing;
test "cone init: normalization drops covered members, sorts, and validates" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{ "src/vendor", "src", "docs/rfcs", "src/vendor/deep" }, &.{});
defer cone.deinit(gpa);
try testing.expectEqual(@as(usize, 2), cone.members.len);
try testing.expectEqual(@as(usize, 0), cone.not_members.len);
try testing.expectEqualStrings("docs/rfcs", cone.members[0]);
try testing.expectEqualStrings("src", cone.members[1]);
try testing.expectError(error.Bounds, Cone.init(gpa, &.{}, &.{}));
try testing.expectError(error.InvalidMember, Cone.init(gpa, &.{"a//b"}, &.{}));
try testing.expectError(error.InvalidMember, Cone.init(gpa, &.{"../out"}, &.{}));
try testing.expectError(error.ReservedMember, Cone.init(gpa, &.{".zit-cache/x"}, &.{}));
var too_many: [max_members + 1][]const u8 = undefined;
var names: [max_members + 1][8]u8 = undefined;
for (0..max_members + 1) |i| {
names[i] = undefined;
const written = std.fmt.bufPrint(&names[i], "d{d}", .{i}) catch unreachable;
too_many[i] = names[i][0..written.len];
}
try testing.expectError(error.Bounds, Cone.init(gpa, &too_many, &.{}));
// The cap is joint across polarities.
try testing.expectError(error.Bounds, Cone.init(gpa, too_many[0..1], too_many[1..]));
}
test "cone init: exclusion normalization, dead rules, contradiction" {
const gpa = testing.allocator;
var cone = try Cone.init(
gpa,
&.{ "src", "src/vendor/keep" },
&.{ "src/vendor", "src/vendor/junk" },
);
defer cone.deinit(gpa);
// src/vendor/junk is redundant (nearest covering member src/vendor is
// also an exclusion); src/vendor/keep survives (nearest is the
// exclusion): a re-inclusion under an exclusion.
try testing.expectEqual(@as(usize, 2), cone.members.len);
try testing.expectEqualStrings("src", cone.members[0]);
try testing.expectEqualStrings("src/vendor/keep", cone.members[1]);
try testing.expectEqual(@as(usize, 1), cone.not_members.len);
try testing.expectEqualStrings("src/vendor", cone.not_members[0]);
// An exclusion nothing covers is a dead rule.
try testing.expectError(error.DeadExclusion, Cone.init(gpa, &.{"src"}, &.{"tools"}));
// An exclusion equal to an inclusion is a contradiction.
try testing.expectError(error.Contradiction, Cone.init(gpa, &.{"src"}, &.{"src"}));
// An exclusion redundant against the missing root: a cone of only
// exclusions cannot exist (zero inclusions).
try testing.expectError(error.Bounds, Cone.init(gpa, &.{}, &.{"src/vendor"}));
// Exclusion members validate like inclusion members.
try testing.expectError(error.InvalidMember, Cone.init(gpa, &.{"src"}, &.{"src//v"}));
// A dash-sibling sorts BETWEEN a member and its subtree ('-' < '/');
// it must not sever the ancestor chain for later entries.
var dashed = try Cone.init(gpa, &.{ "src", "src-other" }, &.{"src/vendor"});
defer dashed.deinit(gpa);
try testing.expectEqual(@as(usize, 2), dashed.members.len);
try testing.expectEqual(@as(usize, 1), dashed.not_members.len);
try testing.expect(!dashed.covers("src/vendor/x"));
try testing.expect(dashed.covers("src-other/y"));
}
test "cone covers: boundary semantics, positive and negative space" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{ "src", "docs/rfcs" }, &.{});
defer cone.deinit(gpa);
try testing.expect(cone.covers("src"));
try testing.expect(cone.covers("src/cone.zig"));
try testing.expect(cone.covers("docs/rfcs/draft.txt"));
// Sibling with the member as a string prefix but no '/' boundary.
try testing.expect(!cone.covers("src2/file"));
try testing.expect(!cone.covers("srcx"));
try testing.expect(!cone.covers("docs"));
try testing.expect(!cone.covers("docs/plans/x"));
// '.' sorts before '/': the classic boundary byte.
try testing.expect(!cone.covers("src.txt"));
}
test "cone covers: longest match across polarities" {
const gpa = testing.allocator;
var cone = try Cone.init(
gpa,
&.{ "src", "src/vendor/keep" },
&.{"src/vendor"},
);
defer cone.deinit(gpa);
try testing.expect(cone.covers("src/a.zig"));
try testing.expect(!cone.covers("src/vendor"));
try testing.expect(!cone.covers("src/vendor/lib.c"));
try testing.expect(cone.covers("src/vendor/keep"));
try testing.expect(cone.covers("src/vendor/keep/deep.txt"));
// Boundary bytes against the exclusion: a sibling by string prefix.
try testing.expect(cone.covers("src/vendorx"));
try testing.expect(cone.covers("src/vendor.txt"));
}
test "cone decide: names the deciding member, longest not first" {
const gpa = testing.allocator;
var cone = try Cone.init(
gpa,
&.{ "src", "src/vendor/keep" },
&.{"src/vendor"},
);
defer cone.deinit(gpa);
// Covered by the shallow inclusion: nothing deeper applies.
const shallow = cone.decide("src/a.zig");
try testing.expect(shallow.covered);
try testing.expectEqualStrings("src", shallow.member.?);
// The exclusion is longer than the inclusion that contains it, so it
// decides — this is the case a last-match-wins reading gets wrong.
const excluded = cone.decide("src/vendor/lib.c");
try testing.expect(!excluded.covered);
try testing.expectEqualStrings("src/vendor", excluded.member.?);
// Re-inclusion deeper still: the longest member wins again, and the
// answer names it rather than the exclusion it overrode.
const nested = cone.decide("src/vendor/keep/deep.txt");
try testing.expect(nested.covered);
try testing.expectEqualStrings("src/vendor/keep", nested.member.?);
// No member covers it at all: the one verdict with nothing to name.
const uncovered = cone.decide("README");
try testing.expect(!uncovered.covered);
try testing.expect(uncovered.member == null);
// decide and covers can never disagree — covers is defined by decide.
for ([_][]const u8{
"src/a.zig", "src/vendor", "src/vendor/lib.c",
"src/vendor/keep", "src/vendorx", "src/vendor.txt",
"README", "build.zig", "src",
}) |p| try testing.expectEqual(cone.covers(p), cone.decide(p).covered);
}
test "cone coversRange: disjoint, partial, contained" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{"src"}, &.{});
defer cone.deinit(gpa);
try testing.expectEqual(RangeClass.contained, cone.coversRange("src/a.zig", "src/z.zig"));
try testing.expectEqual(RangeClass.disjoint, cone.coversRange("tools/a", "tools/z"));
try testing.expectEqual(RangeClass.disjoint, cone.coversRange("README", "docs/z"));
try testing.expectEqual(RangeClass.partial, cone.coversRange("README", "tools/z"));
// Range beginning exactly at the member.
try testing.expectEqual(RangeClass.contained, cone.coversRange("src", "src/z"));
// `src.txt` sorts between `src` and `src/`: not covered, so partial
// classification of a range containing it alongside covered paths.
try testing.expectEqual(RangeClass.partial, cone.coversRange("src.txt", "src/z"));
}
test "cone coversRange: exclusions degrade contained to partial" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{"src"}, &.{"src/vendor"});
defer cone.deinit(gpa);
// Wholly inside the inclusion, wholly outside the exclusion.
try testing.expectEqual(RangeClass.contained, cone.coversRange("src/a", "src/lib/z"));
// The exclusion intersects: per-file classification.
try testing.expectEqual(RangeClass.partial, cone.coversRange("src/a", "src/z"));
try testing.expectEqual(
RangeClass.partial,
cone.coversRange("src/vendor/a", "src/vendor/z"),
);
// Disjoint stays disjoint with exclusions present.
try testing.expectEqual(RangeClass.disjoint, cone.coversRange("tools/a", "tools/z"));
}
test "cone serialize/parse: canonical round-trip and fail-closed residue" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{ "b/dir", "a" }, &.{});
defer cone.deinit(gpa);
const bytes = try cone.serialize(gpa);
defer gpa.free(bytes);
var back = try Cone.parse(gpa, bytes);
defer back.deinit(gpa);
try testing.expectEqual(cone.members.len, back.members.len);
for (cone.members, back.members) |a, b| try testing.expectEqualStrings(a, b);
// Residue after the last member fails closed.
const padded = try std.mem.concat(gpa, u8, &.{ bytes, "x" });
defer gpa.free(padded);
try testing.expectError(error.InvalidMember, Cone.parse(gpa, padded));
// A stored form that is not canonical (member covered by another, so
// normalization would change it) fails closed rather than self-repairs.
var forged: std.ArrayList(u8) = .empty;
defer forged.deinit(gpa);
try forged.append(gpa, 2);
for ([_][]const u8{ "a", "a/sub" }) |m| {
var len_bytes: [2]u8 = undefined;
std.mem.writeInt(u16, &len_bytes, @intCast(m.len), .little);
try forged.appendSlice(gpa, &len_bytes);
try forged.appendSlice(gpa, m);
}
try testing.expectError(error.InvalidMember, Cone.parse(gpa, forged.items));
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &.{}));
// A lone zero byte is a truncated versioned lead-in, not a zero count.
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &.{0}));
// A versioned form with a zero count is the zero-count refusal.
try testing.expectError(error.Bounds, Cone.parse(gpa, &.{ 0, serial_version_exclusions, 0 }));
}
test "cone serialize/parse: exclusion form round-trips, v1 form is stable" {
const gpa = testing.allocator;
var cone = try Cone.init(
gpa,
&.{ "src", "src/vendor/keep" },
&.{"src/vendor"},
);
defer cone.deinit(gpa);
const bytes = try cone.serialize(gpa);
defer gpa.free(bytes);
// The versioned lead-in: 0x00 (never a v1 count), the version byte.
try testing.expectEqual(@as(u8, 0), bytes[0]);
try testing.expectEqual(serial_version_exclusions, bytes[1]);
try testing.expectEqual(@as(u8, 3), bytes[2]);
var back = try Cone.parse(gpa, bytes);
defer back.deinit(gpa);
try testing.expectEqual(@as(usize, 2), back.members.len);
try testing.expectEqual(@as(usize, 1), back.not_members.len);
try testing.expectEqualStrings("src/vendor", back.not_members[0]);
// An exclusion-free cone still serializes in the v1 form: no lead-in.
var plain = try Cone.init(gpa, &.{"src"}, &.{});
defer plain.deinit(gpa);
const plain_bytes = try plain.serialize(gpa);
defer gpa.free(plain_bytes);
try testing.expectEqual(@as(u8, 1), plain_bytes[0]);
// An unknown version byte fails closed.
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &.{ 0, 3, 1 }));
// A flag byte outside {0,1} fails closed.
var bad = try gpa.dupe(u8, bytes);
defer gpa.free(bad);
bad[3] = 2; // First member's flag byte.
try testing.expectError(error.InvalidMember, Cone.parse(gpa, bad));
}
test "cone digest: stable across input permutation, sensitive to coverage" {
const gpa = testing.allocator;
var forward = try Cone.init(gpa, &.{ "src", "docs" }, &.{});
defer forward.deinit(gpa);
var backward = try Cone.init(gpa, &.{ "docs", "src", "src/sub" }, &.{});
defer backward.deinit(gpa);
var other = try Cone.init(gpa, &.{ "src", "docs/rfcs" }, &.{});
defer other.deinit(gpa);
var excluded = try Cone.init(gpa, &.{ "src", "docs" }, &.{"src/vendor"});
defer excluded.deinit(gpa);
const digest_forward = try forward.digest(gpa);
const digest_backward = try backward.digest(gpa);
const digest_other = try other.digest(gpa);
const digest_excluded = try excluded.digest(gpa);
try testing.expectEqualSlices(u8, &digest_forward, &digest_backward);
try testing.expect(!std.mem.eql(u8, &digest_forward, &digest_other));
try testing.expect(!std.mem.eql(u8, &digest_forward, &digest_excluded));
}
test "cone intersectsSubtree: covered dir, ancestor dir, disjoint dir" {
const gpa = testing.allocator;
var cone = try Cone.init(gpa, &.{"src/lib"}, &.{});
defer cone.deinit(gpa);
try testing.expect(cone.intersectsSubtree("src/lib")); // the member itself
try testing.expect(cone.intersectsSubtree("src/lib/deep")); // inside the cone
try testing.expect(cone.intersectsSubtree("src")); // ancestor of a member
try testing.expect(!cone.intersectsSubtree("srcx")); // sibling by prefix
try testing.expect(!cone.intersectsSubtree("tools")); // disjoint
// A re-inclusion keeps its excluded ancestor's subtree intersecting.
var nested = try Cone.init(gpa, &.{ "src", "src/vendor/keep" }, &.{"src/vendor"});
defer nested.deinit(gpa);
try testing.expect(nested.intersectsSubtree("src/vendor"));
try testing.expect(nested.intersectsSubtree("src/vendor/keep"));
}
test "cone member bounds: at the cap and one past it" {
const gpa = testing.allocator;
const long = try gpa.alloc(u8, max_member_len + 1);
defer gpa.free(long);
@memset(long, 'a');
try testing.expectError(error.InvalidMember, Cone.init(gpa, &.{long}, &.{}));
var at_cap = try Cone.init(gpa, &.{long[0..max_member_len]}, &.{});
at_cap.deinit(gpa);
}
test "cone horizon: a horizon-only cone covers every path and round-trips in the version-3 form" {
const gpa = testing.allocator;
const hash = "ABCDEF0123456789abcdef0123456789abcdef01";
var cone = try Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = hash, .rule = .descendants });
defer cone.deinit(gpa);
try testing.expect(!cone.hasPathMembers());
try testing.expect(cone.covers("anything/at/all"));
try testing.expect(cone.intersectsSubtree("src"));
try testing.expectEqual(RangeClass.contained, cone.coversRange("a", "z"));
// The stored hash is canonical lower-case.
try testing.expectEqualStrings("abcdef0123456789abcdef0123456789abcdef01", cone.horizon.?.hash);
const bytes = try cone.serialize(gpa);
defer gpa.free(bytes);
try testing.expectEqual(@as(u8, 0), bytes[0]);
try testing.expectEqual(serial_version_horizon, bytes[1]);
try testing.expectEqual(@as(u8, 0), bytes[2]); // no path members
var back = try Cone.parse(gpa, bytes);
defer back.deinit(gpa);
try testing.expectEqualStrings(cone.horizon.?.hash, back.horizon.?.hash);
try testing.expectEqual(HorizonRule.descendants, back.horizon.?.rule);
// A horizon-only cone cannot carry an exclusion: nothing to subtract from.
try testing.expectError(error.DeadExclusion, Cone.initHorizon(gpa, &.{}, &.{"src"}, .{ .hash = hash, .rule = .descendants }));
// A bad hash is refused.
try testing.expectError(error.InvalidMember, Cone.initHorizon(gpa, &.{}, &.{}, .{ .hash = "nothex", .rule = .descendants }));
}
test "cone horizon: composes with path members, digest is sensitive to C and to the rule" {
const gpa = testing.allocator;
const c1 = "1111111111111111111111111111111111111111";
const c2 = "2222222222222222222222222222222222222222";
var a = try Cone.initHorizon(gpa, &.{ "src", "docs" }, &.{"src/vendor"}, .{ .hash = c1, .rule = .descendants });
defer a.deinit(gpa);
try testing.expect(a.covers("docs/x"));
try testing.expect(!a.covers("src/vendor/x"));
try testing.expect(!a.covers("tools/x"));
const bytes = try a.serialize(gpa);
defer gpa.free(bytes);
var back = try Cone.parse(gpa, bytes);
defer back.deinit(gpa);
try testing.expectEqual(@as(usize, 2), back.members.len);
try testing.expectEqual(@as(usize, 1), back.not_members.len);
try testing.expectEqualStrings(c1, back.horizon.?.hash);
var b = try Cone.initHorizon(gpa, &.{ "docs", "src" }, &.{"src/vendor"}, .{ .hash = c1, .rule = .descendants });
defer b.deinit(gpa);
var c = try Cone.initHorizon(gpa, &.{ "src", "docs" }, &.{"src/vendor"}, .{ .hash = c2, .rule = .descendants });
defer c.deinit(gpa);
var d = try Cone.initHorizon(gpa, &.{ "src", "docs" }, &.{"src/vendor"}, .{ .hash = c1, .rule = .leaves });
defer d.deinit(gpa);
var paths_only = try Cone.init(gpa, &.{ "src", "docs" }, &.{"src/vendor"});
defer paths_only.deinit(gpa);
const da = try a.digest(gpa);
try testing.expectEqualSlices(u8, &da, &(try b.digest(gpa))); // input order never matters
try testing.expect(!std.mem.eql(u8, &da, &(try c.digest(gpa)))); // C matters
try testing.expect(!std.mem.eql(u8, &da, &(try d.digest(gpa)))); // the rule matters
try testing.expect(!std.mem.eql(u8, &da, &(try paths_only.digest(gpa)))); // a horizon is not nothing
}
test "cone parse: an unknown serialization version is refused, never read as members" {
const gpa = testing.allocator;
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &.{ 0, 9, 1, 0, 1, 0, 'a' }));
// A version-3 form with a bad rule byte or hash length is refused too.
var bad_rule: [46]u8 = undefined;
bad_rule[0..6].* = .{ 0, serial_version_horizon, 0, 7, 0, 40 };
@memset(bad_rule[6..], 'a');
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &bad_rule));
var bad_depth: [46]u8 = undefined;
bad_depth[0..6].* = .{ 0, serial_version_horizon, 0, 0, 9, 40 };
@memset(bad_depth[6..], 'a');
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &bad_depth));
var bad_len: [45]u8 = undefined;
bad_len[0..6].* = .{ 0, serial_version_horizon, 0, 0, 0, 39 };
@memset(bad_len[6..], 'a');
try testing.expectError(error.InvalidMember, Cone.parse(gpa, &bad_len));
}
test "cone horizon: the depth round-trips and changes the digest" {
const gpa = testing.allocator;
const h = "abcdef0123456789abcdef0123456789abcdef01";
var content = try Cone.initHorizon(gpa, &.{"src"}, &.{}, .{ .hash = h, .rule = .descendants });
defer content.deinit(gpa);
var structural = try Cone.initHorizon(gpa, &.{"src"}, &.{}, .{ .hash = h, .rule = .descendants, .depth = .structural });
defer structural.deinit(gpa);
try testing.expectEqual(HorizonDepth.content, content.horizon.?.depth);
const bytes = try structural.serialize(gpa);
defer gpa.free(bytes);
var back = try Cone.parse(gpa, bytes);
defer back.deinit(gpa);
try testing.expectEqual(HorizonDepth.structural, back.horizon.?.depth);
try testing.expect(!std.mem.eql(u8, &(try content.digest(gpa)), &(try structural.digest(gpa))));
}