//! Sparse cones: draft-fossil-sparse-cone-00 §3.
//!
//! A cone is a finite, normalized set of repository-relative path prefixes.
//! It covers a path when some member equals the path or is a `/`-terminated
//! prefix of it. 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 covered by another member
//! is dropped at construction (§3.2), which is what makes `covers` a single
//! predecessor probe and the serialized form canonical — two cones with the
//! same coverage serialize identically, so `digest` is a cache key.
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 §8: the member-count bound. A cone is operator-written policy, not
/// data; 64 prefixes is far past any workable sparse profile, and the fixed
/// bound is what makes every loop below finite by inspection.
pub const max_members: usize = 64;
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` after normalization's input, or zero members.
Bounds,
};
/// A normalized cone. Owns its member bytes.
pub const Cone = struct {
/// Sorted ascending, minimal (no member covers another), each validated.
members: []const []const u8,
/// Build from raw operator input (`--cone` values). Validates every
/// member, sorts, and drops members covered by an earlier member. The
/// result is canonical: input order never affects the stored form.
pub fn init(gpa: std.mem.Allocator, raw: []const []const u8) Error!Cone {
if (raw.len == 0) return error.Bounds;
if (raw.len > max_members) return error.Bounds;
for (raw) |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 sorted: std.ArrayList([]u8) = .empty;
errdefer {
for (sorted.items) |m| gpa.free(m);
sorted.deinit(gpa);
}
try appendSortedMinimal(gpa, &sorted, raw);
std.debug.assert(sorted.items.len >= 1);
std.debug.assert(sorted.items.len <= raw.len);
const members = try gpa.alloc([]const u8, sorted.items.len);
for (sorted.items, 0..) |m, i| members[i] = m;
sorted.deinit(gpa);
return .{ .members = 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);
self.* = undefined;
}
/// Whether the cone covers `path` (§2): some member equals it or is a
/// prefix of it at a `/` boundary. One predecessor probe suffices
/// because members are sorted and minimal: the only candidate is the
/// greatest member lexicographically <= `path`, since any other covering
/// member would be a prefix of that candidate and minimality forbids it.
pub fn covers(self: *const Cone, path: []const u8) bool {
std.debug.assert(self.members.len >= 1);
std.debug.assert(self.members.len <= max_members);
const found = predecessor(self.members, path) orelse return false;
const result = memberCovers(self.members[found], path);
if (std.debug.runtime_safety) {
// Pair assertion: the probe agrees with the exhaustive scan.
var linear = false;
for (self.members) |m| linear = linear or memberCovers(m, path);
std.debug.assert(linear == result);
}
return result;
}
/// 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).
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;
// Bounded by `max_members`, asserted at construction. Joint coverage
// by several members reports `.partial`, not `.contained` -- a
// conservative answer: descent then filters per file, so
// over-descending is a cost, never an error.
for (self.members) |member| {
switch (memberVsRange(member, first, last)) {
.disjoint => {},
.partial => any_overlap = true,
.contains_range => return .contained,
}
}
if (!any_overlap) return .disjoint;
return .partial;
}
/// Canonical serialized form: count byte, then per member a u16 LE
/// length and the bytes. Canonical because members are sorted-minimal,
/// so equal coverage yields equal bytes and `digest` is stable.
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 <= max_members);
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(gpa);
try out.append(gpa, @intCast(self.members.len));
for (self.members) |m| {
std.debug.assert(m.len <= max_member_len);
var len_bytes: [2]u8 = undefined;
std.mem.writeInt(u16, &len_bytes, @intCast(m.len), .little);
try out.appendSlice(gpa, &len_bytes);
try out.appendSlice(gpa, m);
}
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;
const count: usize = bytes[0];
if (count == 0) return error.Bounds;
if (count > max_members) return error.Bounds;
var raw: std.ArrayList([]const u8) = .empty;
defer raw.deinit(gpa);
var offset: usize = 1;
var index: usize = 0;
while (index < count) : (index += 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;
try raw.append(gpa, bytes[offset..][0..len]);
offset += len;
}
if (offset != bytes.len) return error.InvalidMember; // No residue.
var cone = try Cone.init(gpa, raw.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.
if (cone.members.len != count) return error.InvalidMember;
for (cone.members, raw.items) |normalized, original| {
if (!std.mem.eql(u8, normalized, original)) 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 };
/// 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;
}
/// Greatest index with `members[i] <= path`, or null when all sort after.
/// Binary search: bounded by log2(max_members) iterations.
fn predecessor(members: []const []const u8, path: []const u8) ?usize {
var low: usize = 0;
var high: usize = members.len; // Exclusive.
var iterations: usize = 0;
while (low < high) : (iterations += 1) {
std.debug.assert(iterations <= 8); // log2(64) + slack; loop is finite.
const mid = low + (high - low) / 2; // Floor division, intentional.
if (std.mem.order(u8, members[mid], path) == .gt) {
high = mid;
} else {
low = mid + 1;
}
}
if (low == 0) return null;
return low - 1;
}
/// Sort `raw` ascending and append only members not covered by an already
/// kept member. Sorted order guarantees a covering member sorts before
/// anything it covers, so one backward glance at the last kept member is
/// the whole minimality check.
fn appendSortedMinimal(
gpa: std.mem.Allocator,
kept: *std.ArrayList([]u8),
raw: []const []const u8,
) error{OutOfMemory}!void {
std.debug.assert(raw.len >= 1);
std.debug.assert(raw.len <= max_members);
var order: [max_members]usize = undefined;
for (raw, 0..) |_, i| order[i] = i;
std.mem.sort(usize, order[0..raw.len], raw, rawLess);
for (order[0..raw.len]) |raw_index| {
const member = raw[raw_index];
if (kept.items.len > 0) {
const last = kept.items[kept.items.len - 1];
if (memberCovers(last, member)) continue; // Covered: drop (also drops duplicates).
}
const copy = try gpa.dupe(u8, member);
errdefer gpa.free(copy);
try kept.append(gpa, copy);
}
std.debug.assert(kept.items.len >= 1);
}
fn rawLess(raw: []const []const u8, a: usize, b: usize) bool {
return std.mem.order(u8, raw[a], raw[b]) == .lt;
}
// ---------------------------------------------------------------------------
// Tests. Goal: pin the §3.2 normalization table, the covers/coversRange truth
// tables including subtree boundary bytes ('.' < '/' < '0'), canonical
// serialization, fail-closed parsing, and digest stability under member
// permutation. Method: table-driven cases over a shared fixture cone.
// ---------------------------------------------------------------------------
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.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));
}
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 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 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 covered = try Cone.init(gpa, &.{"a"});
defer covered.deinit(gpa);
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, &.{}));
try testing.expectError(error.Bounds, Cone.parse(gpa, &.{0}));
}
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);
const digest_forward = try forward.digest(gpa);
const digest_backward = try backward.digest(gpa);
const digest_other = try other.digest(gpa);
try testing.expectEqualSlices(u8, &digest_forward, &digest_backward);
try testing.expect(!std.mem.eql(u8, &digest_forward, &digest_other));
}
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);
}