//! Storage §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. Like `.zit-checkout` (see checkout.zig) it is
//! per-working-copy state materialized atomically into `.zit-managed` beside
//! the working tree; 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 §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 (§E order-independence).
const std = @import("std");
const assert = std.debug.assert;
/// 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,
};
/// The managed-set file, resolved relative to the injected checkout dir.
pub const filename: []const u8 = ".zit-managed";
/// 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;
/// Fixed upper bound on the in-memory / on-disk entry count. A u32 count field
/// carries it (21 bits); the array is capped here.
pub const max_entries: usize = 1 << 20;
/// Authoritative aggregate on-disk bound. Enforced symmetrically: on insert
/// growth (so `write` can never exceed it) and on `read` before allocation (so
/// a lying file cannot force an oversized allocation).
pub const max_file_bytes: usize = 64 << 20;
/// 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;
/// 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). Invariant: `bytes <= max_file_bytes`.
bytes: usize,
/// 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 and the backing array.
pub fn deinit(self: *ManagedSet) void {
for (self.paths.items) |p| self.gpa.free(p);
self.paths.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;
}
/// 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;
}
/// 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.
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;
}
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;
const count: usize = std.mem.readInt(u32, payload[0..4], .little);
if (count > max_entries) return error.Corrupt;
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;
}
if (pos != payload.len) return error.Corrupt; // no trailing bytes
assert(self.paths.items.len == count);
assert(self.bytes == payload.len);
assert(self.sortedUnique());
return self;
}
/// Materializes the set atomically into `filename`: encode into a
/// heap buffer (sized by `self.bytes` — the only deviation from
/// checkout.zig's stack buffer, since the payload is variable-size), then
/// the proven write-temp + fsync + rename-replace sequence. A crash
/// mid-write leaves the prior file intact. Every I/O failure collapses to
/// `error.Storage`.
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);
var af = dir.createFileAtomic(io, filename, .{ .replace = true }) catch return error.Storage;
defer af.deinit(io);
af.file.writePositionalAll(io, bytes, 0) catch return error.Storage;
af.file.sync(io) catch return error.Storage; // fsync data before the rename
af.replace(io) catch return error.Storage; // atomic rename into place
}
/// Reads and parses `filename` into an owned set. An absent file reads as
/// the empty set (`FileNotFound` is absence, not an error, §E). The file
/// size is checked against `max_file_bytes` BEFORE allocation, so a lying
/// file cannot force an oversized allocation. 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 {
var file = dir.openFile(io, filename, .{}) catch |e| switch (e) {
error.FileNotFound => return init(gpa),
else => return error.Storage,
};
defer file.close(io);
const st = file.stat(io) catch return error.Storage;
if (st.size > max_file_bytes) return error.Corrupt; // reject before alloc
const size: usize = @intCast(st.size);
const buf = gpa.alloc(u8, size) catch return error.OutOfMemory;
defer gpa.free(buf);
const n = file.readPositionalAll(io, buf, 0) catch return error.Storage;
return parse(gpa, buf[0..n]);
}
};
// ---------------------------------------------------------------------------
// Tests (storage-track-plan.md §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 §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 §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 §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 §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 §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 §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("" ** 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 §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 §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 §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, 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 §E: parse rejects malformed records (one case per condition)" {
const gpa = testing.allocator;
// count = (1<<20)+1, little-endian, as a bare 4-byte header.
const over_count = comptime blk: {
var b: [4]u8 = undefined;
std.mem.writeInt(u32, &b, @as(u32, max_entries) + 1, .little);
break :blk b;
};
const cases = [_][]const u8{
&[_]u8{ 0x00, 0x00, 0x00 }, // truncated count (3 of 4 bytes)
&over_count, // count exceeds max_entries
&[_]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 §E: a file larger than max_file_bytes is rejected before allocation" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
// Sparse write of one byte at offset max_file_bytes => size = max_file_bytes+1,
// without materializing 64 MiB of data.
{
var f = try tmp.dir.createFile(io, filename, .{});
defer f.close(io);
try f.writePositionalAll(io, &[_]u8{0x00}, @as(u64, max_file_bytes));
}
try testing.expectError(error.Corrupt, ManagedSet.read(testing.allocator, io, tmp.dir));
}
test "managed §E: insert of an over-long path is rejected with TooLong" {
var s = ManagedSet.init(testing.allocator);
defer s.deinit();
const ok = "a" ** max_path_len;
try testing.expect(try s.insert(ok)); // exactly max_path_len is accepted
const too_long = "b" ** (max_path_len + 1);
try testing.expectError(error.TooLong, s.insert(too_long));
}
test "managed §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]);
}
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);
// 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 §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));
}
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 §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 §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 §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 });
}