Artifact 497f984a86122af2fa212bc01680ff2e742ff0ff457032b8835b942d487a588d:
- File
src/cone.zig
— part of check-in
[3cb62134a3]
at
2026-08-17 01:05:04
on branch sparse-cone
— cone test: classify paths against the cone and name the deciding member (#79)
Longest match across both polarities decides coverage, so the verdict alone cannot say why a file is missing. The member prints bare so it pastes into zit cone remove. Exits 0 when every path is covered, 1 when any is elided. (user: dmestas, size: 35748) [annotate] [blame] [check-ins using] [more...]
//! 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. 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 (#79). 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); std.debug.assert(self.members.len + self.not_members.len <= max_members); 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); 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 }; /// A coverage verdict together with the member that produced it (#79). 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); }