//! 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;
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,
/// 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 {
if (raw.len == 0) return error.Bounds;
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);
for (kept_not.items, 0..) |m, i| not_members[i] = m;
kept_members.deinit(gpa);
kept_not.deinit(gpa);
return .{ .members = members, .not_members = not_members };
}
pub fn deinit(self: *Cone, gpa: std.mem.Allocator) void {
std.debug.assert(self.members.len >= 1); // 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);
self.* = undefined;
}
/// Whether the cone covers `path` (§2): the longest member covering the
/// path decides, and it decides by its polarity. A bounded linear scan
/// over both member lists — ties are impossible (a path carried with
/// both polarities is refused at construction).
pub fn covers(self: *const Cone, path: []const u8) bool {
std.debug.assert(self.members.len >= 1);
std.debug.assert(self.members.len + self.not_members.len <= max_members);
var best_len: usize = 0;
var best_exclude = false;
for (self.members) |m| {
if (m.len >= best_len and memberCovers(m, path)) {
best_len = m.len;
best_exclude = false;
}
}
for (self.not_members) |m| {
if (m.len > best_len and memberCovers(m, path)) {
best_len = m.len;
best_exclude = true;
}
}
if (best_len == 0) return false;
return !best_exclude;
}
/// 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);
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);
std.debug.assert(std.mem.order(u8, first, last) != .gt);
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);
std.debug.assert(self.members.len + self.not_members.len <= max_members);
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(gpa);
if (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);
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;
if (bytes[0] == 0) {
// Versioned form: 0x00 lead-in, version byte, count byte.
if (bytes.len < 3) return error.InvalidMember;
if (bytes[1] != serial_version_exclusions) return error.InvalidMember;
count = bytes[2];
offset = 3;
flagged = true;
} else {
count = bytes[0];
offset = 1;
}
if (count == 0) 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.init(gpa, raw.items, raw_not.items);
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 };
/// 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 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);
}