//! Storage plan E: the per-checkout MANAGED-PATH SET, kept OUT of the shared log.
//!
//! This is the working-copy set of repo-relative paths the user has asked zit
//! to version-control: per-working-copy state materialized atomically as the
//! managed section of the `.zit-checkout` container (checkout.zig §5.1; the
//! legacy `.zit-managed` sibling is read on a pre-container checkout). It is
//! NOT the content log (`.zit`) and NOT repostate (which derives over
//! committed artifacts). It never enters the shippable container.
//!
//! No RFC section behind this file: native storage-engine design, the same
//! oracle as checkout.zig / logstore.zig (storage-track-plan.md item E). Effects
//! flow only through an injected `std.Io` + `std.Io.Dir` (design-seams rule —
//! no ambient filesystem access); tests bind `std.testing.io` + a `tmpDir`.
//!
//! The set is held sorted-canonical in memory (ascending by path bytes,
//! deduplicated), so `iterate` is O(1), `contains` is O(log n), and the
//! persisted byte image is a pure function of the set — building the same set
//! in any insertion order yields identical bytes (plan E order-independence).
const std = @import("std");
const repeat = @import("repeat.zig").repeat;
const assert = std.debug.assert;
const checkout = @import("checkout.zig");
/// The device failed, the record on disk is not a `.zit-managed` this reader
/// can parse, or an input violated a fixed bound. Closed at the boundary so a
/// CLI caller can switch exhaustively.
pub const ManagedError = error{
/// A filesystem operation failed (open/create/write/sync/rename/stat).
Storage,
/// The on-disk record is malformed (bad length, wrong order, trailing
/// bytes, over-count). Never a crash — parse of arbitrary bytes yields
/// this or a value.
Corrupt,
/// A single path exceeds `max_path_len`.
TooLong,
/// The set is full: adding would exceed `max_entries` or `max_file_bytes`.
TooMany,
/// Allocation failed.
OutOfMemory,
};
/// Per-path upper bound. PATH_MAX, not checkout's `max_ck_str` (255 =
/// NAME_MAX): a repo-relative path spans many components and legitimately
/// reaches PATH_MAX, so 255 would reject valid deep paths.
pub const max_path_len: usize = 4096;
/// Upper bound on the entry count, DERIVED from the format: the serialized set
/// opens with a `u32` count, so that field is what can be represented and the
/// cap is exactly its range.
///
/// It was `1 << 20`. Nothing chose that — the doc even named the u32 carrier
/// while capping four thousand times below it — and it FAILED a correct
/// operation: `insert` returns `error.TooMany` at 1,048,576 tracked paths, a
/// count real monorepos reach. What actually bounds a set now is memory, which
/// is the honest bound and the one the caller can see coming.
///
/// Two consumers derive from this and must keep deriving: `undo.max_files` (an
/// image never enumerates more paths than a full set) follows correctly and
/// needs no change. `extras` used to borrow it as a directory-sweep ceiling,
/// which was never the same quantity — see `extras.max_sweep_entries`.
pub const max_entries: usize = std.math.maxInt(u32);
/// The largest PATH TABLE the format can express: a count prefix plus
/// `max_entries` length-prefixed paths of at most `max_path_len` each. Computed
/// in `u64` and clamped to `usize`, so the arithmetic cannot wrap on a 32-bit
/// target.
///
/// This bounds a list of PATHS. It says nothing about how large the file AT one
/// of those paths may be, and must never be borrowed as a content ceiling —
/// `max_tracked_file_bytes` is that bound. Conflating them is what silently
/// refused ordinary large files; see the note there.
///
/// It was a flat 64 MiB, described as "enforced symmetrically: on insert growth
/// ... and on `read` before allocation (so a lying file cannot force an
/// oversized allocation)". The read half of that was untrue — `read` allocates
/// the size `stat` reports, so no length is being claimed and there is nothing
/// to lie about — and the insert half refused correct sets at roughly a million
/// average-length paths. `read` now sizes from `stat` like every other
/// whole-file read here, and this value survives only as the format's own
/// expressible maximum, which no real set approaches.
pub const max_file_bytes: usize = @intCast(@min(
@as(u64, std.math.maxInt(usize)),
@as(u64, header_bytes) + @as(u64, max_entries) * (@as(u64, entry_overhead) + @as(u64, max_path_len)),
));
/// Upper bound on the CONTENT of one tracked working-tree file, inclusive.
///
/// Lives here rather than beside its `zit commit`/`zit diff` callers because it
/// is a property of the tracked set, and every layer that reads a tracked
/// file's bytes — commit, diff, and the undo journal's pre-image capture — has
/// to agree on it. When they disagree, a file is committable but not
/// recoverable, and the mismatch surfaces as an unrelated storage failure in
/// whichever layer holds the smaller number.
///
/// That is not hypothetical: the undo journal previously took its per-file cap
/// from `max_file_bytes` (the PATH-TABLE aggregate above, 64 MiB) on the
/// reasoning that the set's aggregate bound "doubles as the single-file
/// ceiling". It does not. Any tracked file over 64 MiB — well inside what
/// commit accepts — made `journal.record` fail, and because a pre-image must be
/// durable before any working byte moves, that aborted the entire checkout,
/// update or merge with a storage error naming nothing the operator had done.
///
/// THE VALUE IS NOT A POLICY CHOICE. It is `logstore.max_payload` — the storage
/// layer's artifact-frame ceiling — surfaced at the working-tree boundary, and
/// `main.zig` holds a comptime assert tying the two together (stated there
/// rather than here so this module keeps importing only `std`). A tracked file's
/// content becomes exactly one artifact frame, and `logstore.put`/`putArtifact`
/// ASSERT `bytes.len <= max_payload`. So this is not a limit that could be
/// raised on its own to admit larger files: without the gate here, committing an
/// oversize file would trip that assert — undefined behaviour in a release
/// build — instead of being refused.
///
/// Two further constraints independently pin the same number, so raising it
/// would require moving all three together:
/// * The wire: sync decodes cap at `logstore.max_payload`, so a larger blob
/// could not be transferred to any peer even once stored.
/// * The delta format: every integer it carries must be < 2^32 (delta-format
/// §3.1), which `delta.create` enforces as `TargetTooLarge`.
///
/// Streaming would not lift it either. Hashing could be incremental, but
/// `delta.create` indexes the whole resident source and scans the whole resident
/// target, and the undo journal serializes a pre-image in memory. Admitting
/// larger files means chunked frames, a chunk-aware delta strategy, a
/// spill-to-disk journal, and a wire change — a large-object subsystem no draft
/// in `docs/rfcs/` specifies.
///
/// Interop agrees: upstream Fossil stores blobs in SQLite, whose default
/// `SQLITE_MAX_LENGTH` is 1e9 bytes, so Fossil refuses artifacts at essentially
/// this size too. A repository zit could accept but Fossil could not hold would
/// break the round-trip this project exists to prove.
pub const max_tracked_file_bytes: usize = 1 << 30;
/// Serialized size of the empty set: just the u32 count prefix.
const header_bytes: usize = 4;
/// Per-entry serialized overhead: the u16 length prefix.
const entry_overhead: usize = 2;
/// Serialized overhead of a pending-rename record: two u16 name-length prefixes
/// (old then new). The record is an OPTIONAL trailer after the entry table.
const record_overhead: usize = 2 * entry_overhead;
/// A pending OLD→NEW rename recorded by `zit mv`, consumed by the next
/// `zit commit` to emit the §4.7.6 four-token old-name F card. Both names are
/// heap-owned repo-relative keys. At most one is pending at a time.
pub const Rename = struct {
old: []const u8,
new: []const u8,
};
/// Serialized size a `Rename` adds to the persisted image.
fn renameBytes(rn: Rename) usize {
return record_overhead + rn.old.len + rn.new.len;
}
/// A sorted, deduplicated set of heap-owned repo-relative paths, with atomic
/// self-describing persistence. Owns every byte of every path it holds.
pub const ManagedSet = struct {
gpa: std.mem.Allocator,
/// Sorted strictly-ascending by bytes, unique, each element heap-owned.
paths: std.ArrayList([]const u8),
/// Running serialized size (== the byte length `write`/`encode` produce and
/// `read`/`parse` consume, record included). Invariant: `bytes <=
/// max_file_bytes`.
bytes: usize,
/// The pending renames `zit mv` records for the next commit to consume
/// (one per moved file). Empty in the common case; a pre-mv
/// file and every post-clear file decode to empty. Names are heap-owned.
renames: std.ArrayList(Rename) = .empty,
/// An empty set. Allocates nothing.
pub fn init(gpa: std.mem.Allocator) ManagedSet {
return .{ .gpa = gpa, .paths = .empty, .bytes = header_bytes };
}
/// Frees every owned path, the pending-rename names, and the backing array.
pub fn deinit(self: *ManagedSet) void {
for (self.paths.items) |p| self.gpa.free(p);
self.paths.deinit(self.gpa);
for (self.renames.items) |rn| {
self.gpa.free(rn.old);
self.gpa.free(rn.new);
}
self.renames.deinit(self.gpa);
self.* = undefined;
}
/// Adds `path`. Idempotent: returns `true` when newly inserted, `false`
/// when already present (never an error on a duplicate — the common case
/// is defined error-free). `error.TooLong` if the path exceeds
/// `max_path_len`; `error.TooMany` if the set is full (count or aggregate
/// bytes); `error.OutOfMemory` on allocation failure. Bound violations are
/// errors, not asserts: they guard untrusted INPUT and must be testable.
pub fn insert(self: *ManagedSet, path: []const u8) ManagedError!bool {
if (path.len > max_path_len) return error.TooLong;
const loc = self.locate(path);
if (loc.found) return false;
if (self.paths.items.len >= max_entries) return error.TooMany;
const grown = self.bytes + entry_overhead + path.len;
if (grown > max_file_bytes) return error.TooMany;
const owned = self.gpa.dupe(u8, path) catch return error.OutOfMemory;
errdefer self.gpa.free(owned);
self.paths.insert(self.gpa, loc.idx, owned) catch return error.OutOfMemory;
self.bytes = grown;
assert(self.paths.items.len <= max_entries); // count bound holds
assert(self.bytes <= max_file_bytes); // aggregate bound holds
assert(self.sortedUnique()); // invariant preserved
return true;
}
/// Bulk construction from paths already in strictly ascending byte order --
/// a materialization plan's own order. `insert` is O(n) per call twice
/// over (the sorted-position memmove, and the live `sortedUnique` assert),
/// so building a 66k-entry set through it is quadratic: measured at 23.9
/// SECONDS of a pkgsrc update, dwarfing every real phase. This does the
/// same job in one pass, enforcing the order invariant on each adjacent
/// pair as it goes -- out-of-order or duplicate input is `error.Corrupt`,
/// never a silently mis-sorted set.
pub fn fromSortedPaths(gpa: std.mem.Allocator, sorted: []const []const u8) ManagedError!ManagedSet {
var self = init(gpa);
errdefer self.deinit();
if (sorted.len > max_entries) return error.TooMany;
self.paths.ensureTotalCapacity(gpa, sorted.len) catch return error.OutOfMemory;
var previous: ?[]const u8 = null;
for (sorted) |path| {
if (path.len > max_path_len) return error.TooLong;
if (previous) |last| {
if (!(std.mem.order(u8, last, path) == .lt)) return error.Corrupt;
}
previous = path;
const grown = self.bytes + entry_overhead + path.len;
if (grown > max_file_bytes) return error.TooMany;
const owned = gpa.dupe(u8, path) catch return error.OutOfMemory;
self.paths.appendAssumeCapacity(owned);
self.bytes = grown;
}
assert(self.sortedUnique()); // once, over the finished set
return self;
}
/// Membership test. Pure, O(log n).
pub fn contains(self: *const ManagedSet, path: []const u8) bool {
return self.locate(path).found;
}
/// Removes `path`. Returns whether it was present (absent is a no-op
/// returning `false` — no error). O(n) shift; not a hot path.
pub fn remove(self: *ManagedSet, path: []const u8) bool {
const loc = self.locate(path);
if (!loc.found) return false;
const owned = self.paths.orderedRemove(loc.idx);
assert(self.bytes >= header_bytes + entry_overhead + owned.len);
self.bytes -= entry_overhead + owned.len;
self.gpa.free(owned);
assert(self.sortedUnique());
return true;
}
/// Stable, sorted-ascending view of the set for `status`/`commit`. The
/// slice borrows the set and is invalidated by the next mutation.
pub fn iterate(self: *const ManagedSet) []const []const u8 {
return self.paths.items;
}
/// Records a pending OLD→NEW rename for the next commit to emit as a §4.7.6
/// old-name F card. Precondition (mv has already swapped the entry): NEW is
/// tracked and OLD is not — the record stays STRUCTURAL, never a second
/// copy of the entry membership. Records compose: a rename whose OLD is a
/// pending record's NEW extends that record (A→B then B→C is A→C), and one
/// that lands back on its own OLD cancels it (A→B then B→A is nothing), so
/// the list never says more than the tree's history does. Names are duped
/// (heap-owned). `error.TooMany` if the aggregate would exceed
/// `max_file_bytes`; `error.OutOfMemory` on allocation failure.
pub fn recordRename(self: *ManagedSet, old: []const u8, new: []const u8) ManagedError!void {
assert(old.len >= 1 and old.len <= max_path_len); // bounded, non-empty
assert(new.len >= 1 and new.len <= max_path_len);
assert(self.contains(new)); // mv inserted NEW before recording (positive space)
assert(!self.contains(old)); // mv removed OLD before recording (negative space)
for (self.renames.items, 0..) |cur, idx| {
if (!std.mem.eql(u8, cur.new, old)) continue;
// Extend (or cancel) the record that produced OLD.
self.bytes -= renameBytes(cur);
if (std.mem.eql(u8, cur.old, new)) {
self.gpa.free(cur.old);
self.gpa.free(cur.new);
_ = self.renames.orderedRemove(idx);
return;
}
const grown = self.bytes + renameBytes(.{ .old = cur.old, .new = new });
if (grown > max_file_bytes) {
self.bytes += renameBytes(cur);
return error.TooMany;
}
const new_owned = self.gpa.dupe(u8, new) catch {
self.bytes += renameBytes(cur);
return error.OutOfMemory;
};
self.gpa.free(cur.new);
self.renames.items[idx].new = new_owned;
self.bytes = grown;
return;
}
const grown = self.bytes + renameBytes(.{ .old = old, .new = new });
if (grown > max_file_bytes) return error.TooMany;
const old_owned = self.gpa.dupe(u8, old) catch return error.OutOfMemory;
errdefer self.gpa.free(old_owned);
const new_owned = self.gpa.dupe(u8, new) catch return error.OutOfMemory;
errdefer self.gpa.free(new_owned);
self.renames.append(self.gpa, .{ .old = old_owned, .new = new_owned }) catch return error.OutOfMemory;
self.bytes = grown;
assert(self.bytes <= max_file_bytes); // aggregate bound holds
}
/// The pending renames, empty when none are recorded. `runCommit` stamps
/// each renamed capture's old-name from these (§4.7.6). Borrows the set;
/// invalidated by `clearRename`/`recordRename`/`deinit`.
pub fn pendingRenames(self: *const ManagedSet) []const Rename {
return self.renames.items;
}
/// Consumes the pending rename whose NEW is `new`: frees its names and
/// restores the byte image. A no-op when none matches, so the commit that
/// carried the rename clears it exactly once.
pub fn clearRename(self: *ManagedSet, new: []const u8) void {
for (self.renames.items, 0..) |cur, idx| {
if (!std.mem.eql(u8, cur.new, new)) continue;
assert(self.bytes >= header_bytes + renameBytes(cur));
self.bytes -= renameBytes(cur);
self.gpa.free(cur.old);
self.gpa.free(cur.new);
_ = self.renames.orderedRemove(idx);
return;
}
}
/// Binary-search location of `path`: `.found` marks an exact hit at `.idx`;
/// otherwise `.idx` is the sorted insertion point. Bounded loop — at most
/// log2(max_entries) = 20 iterations.
fn locate(self: *const ManagedSet, path: []const u8) struct { idx: usize, found: bool } {
var lo: usize = 0;
var hi: usize = self.paths.items.len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
switch (std.mem.order(u8, self.paths.items[mid], path)) {
.lt => lo = mid + 1,
.gt => hi = mid,
.eq => return .{ .idx = mid, .found = true },
}
}
return .{ .idx = lo, .found = false };
}
/// Invariant check for assertions: the array is strictly ascending (hence
/// sorted and unique). No side effects.
fn sortedUnique(self: *const ManagedSet) bool {
if (self.paths.items.len < 2) return true;
for (self.paths.items[1..], self.paths.items[0 .. self.paths.items.len - 1]) |cur, prev| {
if (std.mem.order(u8, prev, cur) != .lt) return false;
}
return true;
}
/// Encodes the set into `buf` (which must hold `self.bytes`) as
/// `[count u32 LE]` then per entry `[len u16 LE][path bytes]`, entries in
/// the array's ascending order. Returns the written slice. Because the set
/// is canonical, the byte image is a pure function of the set. Public so a
/// caller composing a multi-section container splice (update's commit
/// point) can supply the managed payload alongside the checkout record.
pub fn encode(self: *const ManagedSet, buf: []u8) []const u8 {
assert(buf.len >= self.bytes);
assert(self.paths.items.len <= max_entries);
var pos: usize = 0;
std.mem.writeInt(u32, buf[pos..][0..4], @intCast(self.paths.items.len), .little);
pos += 4;
for (self.paths.items) |p| {
assert(p.len <= max_path_len);
std.mem.writeInt(u16, buf[pos..][0..2], @intCast(p.len), .little);
pos += 2;
@memcpy(buf[pos..][0..p.len], p);
pos += p.len;
}
// Trailing pending-rename records: `old_len old new_len new`, one per
// rename. None writes nothing (byte-identical to a pre-mv image).
for (self.renames.items) |rn| {
assert(rn.old.len <= max_path_len and rn.new.len <= max_path_len);
std.mem.writeInt(u16, buf[pos..][0..2], @intCast(rn.old.len), .little);
pos += 2;
@memcpy(buf[pos..][0..rn.old.len], rn.old);
pos += rn.old.len;
std.mem.writeInt(u16, buf[pos..][0..2], @intCast(rn.new.len), .little);
pos += 2;
@memcpy(buf[pos..][0..rn.new.len], rn.new);
pos += rn.new.len;
}
assert(pos == self.bytes); // running counter matches the encoding
return buf[0..pos];
}
/// Parses an `encode` record into an owned set. Every length is
/// bounds-checked against the remaining slice before use, each entry is
/// capped at `max_path_len`, entries must be strictly ascending (which
/// rejects both unsorted records and duplicates in one check), and total
/// consumption must be exact. Any violation is `error.Corrupt`; arbitrary
/// bytes never crash. Paths are duped, so the transient read buffer frees
/// cleanly. The count-driven loop is a bounded `for`, never a
/// `while`+mutable-state.
fn parse(gpa: std.mem.Allocator, payload: []const u8) ManagedError!ManagedSet {
var self = init(gpa);
errdefer self.deinit();
if (payload.len < header_bytes) return error.Corrupt;
// No `count > max_entries` check: `max_entries` IS the u32 field's range,
// so a count read from it cannot exceed the bound and the test would be
// dead code. Nothing is given up — unlike the undo journal, this loop
// allocates nothing from `count`; it appends as it parses, so a count
// larger than the payload can back fails on the first short entry below.
const count: usize = std.mem.readInt(u32, payload[0..4], .little);
var pos: usize = header_bytes;
var prev: ?[]const u8 = null;
for (0..count) |_| {
if (payload.len - pos < entry_overhead) return error.Corrupt;
const len: usize = std.mem.readInt(u16, payload[pos..][0..2], .little);
pos += entry_overhead;
if (len > max_path_len) return error.Corrupt;
if (payload.len - pos < len) return error.Corrupt;
const entry = payload[pos..][0..len];
pos += len;
if (prev) |pv| {
if (std.mem.order(u8, pv, entry) != .lt) return error.Corrupt;
}
prev = entry;
const owned = gpa.dupe(u8, entry) catch return error.OutOfMemory;
errdefer gpa.free(owned);
self.paths.append(gpa, owned) catch return error.OutOfMemory;
self.bytes += entry_overhead + len;
}
assert(self.paths.items.len == count);
// Optional trailing pending-rename record (§4.7.6 mv). Absence == exact
// entry-table consumption (a pre-mv file, and every post-clear file);
// presence == an `old_len old new_len new` frame that must consume the
// rest exactly. Every length is bounds-checked against the remaining
// slice before use; a framing failure is `error.Corrupt`, never a crash
// (one stray byte cannot frame a u16, so the old "trailing byte" reject
// still holds).
while (pos != payload.len) {
if (payload.len - pos < entry_overhead) return error.Corrupt;
const old_len: usize = std.mem.readInt(u16, payload[pos..][0..2], .little);
pos += entry_overhead;
if (old_len == 0 or old_len > max_path_len) return error.Corrupt;
if (payload.len - pos < old_len) return error.Corrupt;
const old = payload[pos..][0..old_len];
pos += old_len;
if (payload.len - pos < entry_overhead) return error.Corrupt;
const new_len: usize = std.mem.readInt(u16, payload[pos..][0..2], .little);
pos += entry_overhead;
if (new_len == 0 or new_len > max_path_len) return error.Corrupt;
if (payload.len - pos < new_len) return error.Corrupt;
const new = payload[pos..][0..new_len];
pos += new_len;
const old_owned = gpa.dupe(u8, old) catch return error.OutOfMemory;
errdefer gpa.free(old_owned);
const new_owned = gpa.dupe(u8, new) catch return error.OutOfMemory;
errdefer gpa.free(new_owned);
self.renames.append(gpa, .{ .old = old_owned, .new = new_owned }) catch return error.OutOfMemory;
self.bytes += record_overhead + old_len + new_len;
}
assert(self.bytes == payload.len);
assert(self.sortedUnique());
return self;
}
/// Materializes the set atomically as the container's managed section
/// (checkout.zig `updateSections`, consolidation §5.1): encode into a heap
/// buffer (sized by `self.bytes`, since the payload is variable-size),
/// then splice it into `.zit-checkout` through the proven write-temp +
/// fsync + rename-replace sequence. The byte image is unchanged — only
/// the file it lands in moved. A crash mid-write leaves the prior
/// generation intact.
pub fn write(self: *const ManagedSet, io: std.Io, dir: std.Io.Dir) ManagedError!void {
assert(self.paths.items.len <= max_entries);
assert(self.bytes <= max_file_bytes);
const buf = self.gpa.alloc(u8, self.bytes) catch return error.OutOfMemory;
defer self.gpa.free(buf);
const bytes = self.encode(buf);
checkout.updateSections(io, dir, &.{.{ .tag = .managed, .payload = bytes }}) catch |e| switch (e) {
error.Storage => return error.Storage,
error.Corrupt => return error.Corrupt, // the container (or legacy record) being spliced is damaged
};
}
/// Reads and parses the managed section into an owned set — from the
/// container when one exists, from the legacy `.zit-managed` sibling
/// otherwise (byte-1 dispatch in checkout.zig; the payload format is
/// identical either way). Absence reads as the empty set (plan E). A
/// malformed record is `error.Corrupt`; any other I/O failure is
/// `error.Storage`.
pub fn read(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) ManagedError!ManagedSet {
const raw = checkout.readSectionAlloc(gpa, io, dir, .managed) catch |e| switch (e) {
error.Storage => return error.Storage,
error.Corrupt => return error.Corrupt,
error.OutOfMemory => return error.OutOfMemory,
} orelse return init(gpa);
defer gpa.free(raw);
return parse(gpa, raw);
}
};
// ---------------------------------------------------------------------------
// Tests (storage-track-plan.md item E; no RFC section behind this file). Expected
// values come from the format spec above, never from running fossil.
// ---------------------------------------------------------------------------
const testing = std.testing;
/// Asserts two sets hold exactly the same paths in the same (sorted) order.
fn expectSameSet(a: *const ManagedSet, b: *const ManagedSet) !void {
const ia = a.iterate();
const ib = b.iterate();
try testing.expectEqual(ia.len, ib.len);
for (ia, ib) |pa, pb| try testing.expectEqualSlices(u8, pa, pb);
}
test "managed plan E: insert, contains, and remove form a coherent lifecycle" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
try testing.expect(!s.contains("src/main.zig"));
try testing.expect(try s.insert("src/main.zig"));
try testing.expect(s.contains("src/main.zig"));
try testing.expect(!s.contains("README"));
try testing.expect(s.remove("src/main.zig"));
try testing.expect(!s.contains("src/main.zig"));
}
test "managed plan E: insert is idempotent (a duplicate is not an error)" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
try testing.expect(try s.insert("a/b"));
try testing.expect(!(try s.insert("a/b"))); // already present -> false, no error
try testing.expectEqual(@as(usize, 1), s.iterate().len);
}
test "managed plan E: remove of an absent path is a no-op returning false" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
try testing.expect(!s.remove("never/added"));
try testing.expect(try s.insert("x"));
try testing.expect(!s.remove("y")); // present set, absent path
try testing.expectEqual(@as(usize, 1), s.iterate().len);
}
test "managed plan E: iterate is sorted ascending by bytes regardless of insert order" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
_ = try s.insert("zeta");
_ = try s.insert("alpha");
_ = try s.insert("mid");
_ = try s.insert("Alpha"); // 'A' (0x41) sorts before 'a' (0x61)
const it = s.iterate();
try testing.expectEqual(@as(usize, 4), it.len);
try testing.expectEqualStrings("Alpha", it[0]);
try testing.expectEqualStrings("alpha", it[1]);
try testing.expectEqualStrings("mid", it[2]);
try testing.expectEqualStrings("zeta", it[3]);
}
test "managed plan E: two insertion orders yield byte-identical persisted images (order-independence)" {
var a = ManagedSet.init(testing.allocator);
defer a.deinit();
var b = ManagedSet.init(testing.allocator);
defer b.deinit();
const items = [_][]const u8{ "src/z.zig", "README", "a/b/c", "src/a.zig", "docs/x" };
for (items) |p| _ = try a.insert(p);
var i = items.len;
while (i > 0) {
i -= 1;
_ = try b.insert(items[i]);
}
try testing.expectEqual(a.bytes, b.bytes);
const bufa = try testing.allocator.alloc(u8, a.bytes);
defer testing.allocator.free(bufa);
const bufb = try testing.allocator.alloc(u8, b.bytes);
defer testing.allocator.free(bufb);
try testing.expectEqualSlices(u8, a.encode(bufa), b.encode(bufb));
}
test "managed plan E: write then read round-trips a bounded set (paths may embed NUL)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
_ = try s.insert("README");
_ = try s.insert(&[_]u8{ 'a', 0x00, 'b' }); // NUL is a legal filename byte (rule 4)
_ = try s.insert("src/main.zig");
_ = try s.insert(repeat("", 0) ++ "z"); // ordinary
try s.write(io, tmp.dir);
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try expectSameSet(&s, &got);
try testing.expectEqual(s.bytes, got.bytes);
}
test "managed plan E: read of an absent managed file returns the empty set" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try testing.expectEqual(@as(usize, 0), got.iterate().len);
try testing.expectEqual(header_bytes, got.bytes);
}
test "managed plan E: a second write atomically replaces the set (last wins)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var first = ManagedSet.init(testing.allocator);
defer first.deinit();
_ = try first.insert("old/one");
_ = try first.insert("old/two");
try first.write(io, tmp.dir);
var second = ManagedSet.init(testing.allocator);
defer second.deinit();
_ = try second.insert("new/only");
try second.write(io, tmp.dir);
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try expectSameSet(&second, &got);
}
test "managed plan E: a partial write that never materializes leaves the prior set intact" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var good = ManagedSet.init(testing.allocator);
defer good.deinit();
_ = try good.insert("keep/me");
_ = try good.insert("keep/too");
try good.write(io, tmp.dir);
// Begin a fresh atomic file, write a DIFFERENT set's bytes, then drop it
// WITHOUT replace: deinit deletes the temp, a reader only sees `filename`.
{
var doomed = ManagedSet.init(testing.allocator);
defer doomed.deinit();
_ = try doomed.insert("should/vanish");
const buf = try testing.allocator.alloc(u8, doomed.bytes);
defer testing.allocator.free(buf);
const bytes = doomed.encode(buf);
var af = try tmp.dir.createFileAtomic(io, checkout.filename, .{ .replace = true });
defer af.deinit(io);
try af.file.writePositionalAll(io, bytes, 0);
// no af.replace(io): the temp is abandoned
}
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try expectSameSet(&good, &got);
}
test "managed plan E: parse rejects malformed records (one case per condition)" {
const gpa = testing.allocator;
// A count no payload could back (nothing follows the header). The old case
// here was `max_entries + 1`, which is unrepresentable now that the bound is
// the u32 field's own range — and an unbacked count was always the real
// hazard, not an over-range one.
const unbacked_count = comptime blk: {
var b: [4]u8 = undefined;
std.mem.writeInt(u32, &b, std.math.maxInt(u32), .little);
break :blk b;
};
const cases = [_][]const u8{
&[_]u8{ 0x00, 0x00, 0x00 }, // truncated count (3 of 4 bytes)
&unbacked_count, // more entries claimed than bytes to hold them
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x00 }, // truncated entry len (1 of 2)
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x10 }, // entry len 4097 > max_path_len
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x05, 0x00, 'a', 'b' }, // len 5 exceeds remaining
&[_]u8{ 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 'b', 0x01, 0x00, 'a' }, // non-ascending
&[_]u8{ 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x00, 'a' }, // duplicate (not < )
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0xff }, // trailing byte
};
for (cases) |c| try testing.expectError(error.Corrupt, ManagedSet.parse(gpa, c));
}
test "managed plan E: the aggregate bound is the format's own maximum, not a policy number" {
// This replaces a test that wrote a sparse file one byte past the old flat
// 64 MiB cap and asserted `Corrupt`. That property is gone deliberately:
// `read` sizes from `stat`, so there is no declared length to disbelieve and
// a large-but-honest set is no longer refused. Writing the same fixture
// against the derived bound would ask the filesystem for a ~17 TB file.
//
// What is worth pinning instead is that the bound is DERIVED — a count
// prefix plus `max_entries` paths of at most `max_path_len` — so that
// changing the format's field widths without revisiting it fails here.
const expected: u64 = @as(u64, header_bytes) +
@as(u64, max_entries) * (@as(u64, entry_overhead) + @as(u64, max_path_len));
try testing.expectEqual(@min(@as(u64, std.math.maxInt(usize)), expected), @as(u64, max_file_bytes));
// And the count bound is exactly the u32 count field's range: the format
// decides it, not a guess about how many files a person tracks.
try testing.expectEqual(@as(usize, std.math.maxInt(u32)), max_entries);
}
test "managed plan E: a truncated file is still rejected" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
// Shorter than the u32 count prefix: the bound that actually protects the
// reader is structural, and it is unaffected by dropping the size cap.
// Written at the retired sibling name, so this also exercises the legacy
// fold's read path (no container exists in this tmp dir).
{
var f = try tmp.dir.createFile(io, ".zit-managed", .{});
defer f.close(io);
try f.writePositionalAll(io, &[_]u8{ 0x01, 0x00 }, 0);
}
try testing.expectError(error.Corrupt, ManagedSet.read(testing.allocator, io, tmp.dir));
}
test "managed plan E: insert of an over-long path is rejected with TooLong" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
const ok = repeat("a", max_path_len);
try testing.expect(try s.insert(ok)); // exactly max_path_len is accepted
const too_long = repeat("b", (max_path_len + 1));
try testing.expectError(error.TooLong, s.insert(too_long));
}
test "managed plan E fuzz: parse never crashes and round-trips encode" {
const gpa = testing.allocator;
var prng = std.Random.DefaultPrng.init(0x2AA9ED);
const random = prng.random();
var iter: usize = 0;
while (iter < 300) : (iter += 1) {
// Build a random bounded set, encode it, parse it back, compare.
var s = ManagedSet.init(gpa);
defer s.deinit();
const n = random.uintAtMost(usize, 16);
var made: usize = 0;
while (made < n) : (made += 1) {
var pbuf: [40]u8 = undefined;
const pl = random.uintAtMost(usize, pbuf.len);
random.bytes(pbuf[0..pl]); // random bytes, NUL included, legal
_ = try s.insert(pbuf[0..pl]);
}
// Half the iterations also seed a pending rename so the record framing
// is fuzzed alongside the entry table. `new` is an actual member (so
// `contains(new)` holds); `old` is 41 bytes — longer than any random
// member (capped at 40), so `!contains(old)` holds by construction.
if (s.iterate().len > 0 and s.iterate()[0].len >= 1 and random.boolean()) {
const old_unique = repeat("z", 41);
try s.recordRename(old_unique, s.iterate()[0]);
}
const buf = try gpa.alloc(u8, s.bytes);
defer gpa.free(buf);
const bytes = s.encode(buf);
var rt = try ManagedSet.parse(gpa, bytes);
defer rt.deinit();
try expectSameSet(&s, &rt);
try testing.expectEqual(s.pendingRenames().len, rt.pendingRenames().len);
for (s.pendingRenames(), rt.pendingRenames()) |rn, rrn| {
try testing.expectEqualSlices(u8, rn.old, rrn.old);
try testing.expectEqualSlices(u8, rn.new, rrn.new);
}
// Arbitrary garbage: a value or error.Corrupt, never a crash.
var garbage: [80]u8 = undefined;
const gn = random.uintAtMost(usize, garbage.len);
random.bytes(garbage[0..gn]);
if (ManagedSet.parse(gpa, garbage[0..gn])) |*maybe| {
var v = maybe.*;
v.deinit();
} else |err| switch (err) {
error.Corrupt => {},
error.OutOfMemory, error.TooLong, error.TooMany, error.Storage => unreachable,
}
}
}
test "managed plan E: a path embedding NUL round-trips through write and read (rule 4)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const nul_path = [_]u8{ 'd', 'i', 'r', 0x00, 'f', 'i', 'l', 'e' };
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
_ = try s.insert(&nul_path);
try s.write(io, tmp.dir);
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try testing.expectEqual(@as(usize, 1), got.iterate().len);
try testing.expectEqualSlices(u8, &nul_path, got.iterate()[0]);
try testing.expect(got.contains(&nul_path));
}
test "managed plan E: a recorded rename round-trips through write/read (B-mv-18)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
_ = try s.insert("README");
_ = try s.insert("docs/new.md"); // NEW is tracked (mv already inserted it)
try s.recordRename("docs/old.md", "docs/new.md");
try s.write(io, tmp.dir);
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try expectSameSet(&s, &got);
try testing.expectEqual(s.bytes, got.bytes);
try testing.expectEqual(@as(usize, 1), got.pendingRenames().len);
const rn = got.pendingRenames()[0];
try testing.expectEqualStrings("docs/old.md", rn.old);
try testing.expectEqualStrings("docs/new.md", rn.new);
}
test "managed plan E: a set written with no rename reads back with an empty record (B-mv-18)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
_ = try s.insert("a");
_ = try s.insert("b");
try s.write(io, tmp.dir);
var got = try ManagedSet.read(testing.allocator, io, tmp.dir);
defer got.deinit();
try testing.expectEqual(@as(usize, 0), got.pendingRenames().len); // pre-mv byte image ⇒ no record
}
test "managed plan E: garbage in the record region is error.Corrupt, never a crash (B-mv-18)" {
const gpa = testing.allocator;
// Every case is a valid one-entry table (`count=1`, entry 'a') followed by a
// malformed record trailer — the record framing must reject each as Corrupt.
const cases = [_][]const u8{
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01 }, // truncated old_len (1 of 2)
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x00, 0x00 }, // old_len == 0
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x10 }, // old_len 4097 > max_path_len
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x05, 0x00, 'o' }, // old_len 5 exceeds remaining
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x00, 'o' }, // no new_len after old
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x00, 'o', 0x00, 0x00 }, // new_len == 0
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x00, 'o', 0x03, 0x00, 'n' }, // new_len 3 exceeds remaining
&[_]u8{ 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 'a', 0x01, 0x00, 'o', 0x01, 0x00, 'n', 0xff }, // trailing byte past record
};
for (cases) |c| try testing.expectError(error.Corrupt, ManagedSet.parse(gpa, c));
}
test "managed plan E: recordRename then clearRename restores the no-record byte image (B-mv-8)" {
const gpa = testing.allocator;
var s = ManagedSet.init(gpa);
defer s.deinit();
_ = try s.insert("x");
_ = try s.insert("y");
const before = s.bytes;
const buf0 = try gpa.alloc(u8, s.bytes);
defer gpa.free(buf0);
const image0 = try gpa.dupe(u8, s.encode(buf0));
defer gpa.free(image0);
try s.recordRename("x-old", "y"); // y tracked, x-old not
try testing.expect(s.bytes > before);
s.clearRename("y");
try testing.expectEqual(before, s.bytes);
try testing.expectEqual(@as(usize, 0), s.pendingRenames().len);
const buf1 = try gpa.alloc(u8, s.bytes);
defer gpa.free(buf1);
try testing.expectEqualSlices(u8, image0, s.encode(buf1)); // byte-identical to no-record
}
test "managed plan E: recordRename accumulates one record per file, extends chains, cancels inversions" {
const gpa = testing.allocator;
var s = ManagedSet.init(gpa);
defer s.deinit();
_ = try s.insert("n1");
try s.recordRename("o1", "n1");
_ = try s.insert("n2");
try s.recordRename("o2", "n2"); // a second file's rename accumulates
try testing.expectEqual(@as(usize, 2), s.pendingRenames().len);
// n1 -> n3 extends o1's record rather than adding a second hop.
_ = s.remove("n1");
_ = try s.insert("n3");
try s.recordRename("n1", "n3");
try testing.expectEqual(@as(usize, 2), s.pendingRenames().len);
try testing.expectEqualStrings("o1", s.pendingRenames()[0].old);
try testing.expectEqualStrings("n3", s.pendingRenames()[0].new);
// n2 -> o2 lands back on its own OLD: the record cancels.
_ = s.remove("n2");
_ = try s.insert("o2");
try s.recordRename("n2", "o2");
try testing.expectEqual(@as(usize, 1), s.pendingRenames().len);
// The image round-trips with exactly the surviving record.
const buf = try gpa.alloc(u8, s.bytes);
defer gpa.free(buf);
var rt = try ManagedSet.parse(gpa, s.encode(buf));
defer rt.deinit();
try testing.expectEqual(@as(usize, 1), rt.pendingRenames().len);
try testing.expectEqualStrings("o1", rt.pendingRenames()[0].old);
try testing.expectEqualStrings("n3", rt.pendingRenames()[0].new);
try testing.expectEqual(s.bytes, rt.bytes);
rt.clearRename("n3");
try testing.expectEqual(@as(usize, 0), rt.pendingRenames().len);
try testing.expectEqual(s.bytes - rt.bytes, renameBytes(.{ .old = "o1", .new = "n3" }));
}
fn insertNoLeak(gpa: std.mem.Allocator) !void {
var s = ManagedSet.init(gpa);
defer s.deinit();
_ = try s.insert("src/main.zig");
_ = try s.insert("README");
_ = try s.insert("docs/spec.txt");
}
test "managed plan E: insert propagates allocation failure without leaking" {
try testing.checkAllAllocationFailures(testing.allocator, insertNoLeak, .{});
}
fn readNoLeak(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) !void {
var s = try ManagedSet.read(gpa, io, dir);
defer s.deinit();
}
test "managed plan E: read propagates allocation failure without leaking" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var seed = ManagedSet.init(testing.allocator);
defer seed.deinit();
_ = try seed.insert("one");
_ = try seed.insert("two");
_ = try seed.insert("three");
try seed.write(io, tmp.dir);
try testing.checkAllAllocationFailures(testing.allocator, readNoLeak, .{ io, tmp.dir });
}
fn writeNoLeak(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) !void {
var s = ManagedSet.init(gpa);
defer s.deinit();
_ = try s.insert("alpha");
_ = try s.insert("beta");
try s.write(io, dir);
}
test "managed plan E: write propagates allocation failure without leaking" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
try testing.checkAllAllocationFailures(testing.allocator, writeNoLeak, .{ io, tmp.dir });
}