Artifact fc4dc8fc8ec0456cb2eb10dcf791228c78f3b88527934d08cd880187f2b5f41a:
- File
src/managed.zig
— part of check-in
[9033c13f21]
at
2026-09-17 17:04:25
on branch trunk
— Remove issue-tracker numbers from source and documents
The tracker is disposable and does not live with the source, so a number is a dangling pointer. Every zit#NN and #NN reference in code comments, test names, help text, smoke labels, identifiers, release notes and errata is replaced by enough context to stand alone, or by a short plain statement of the problem. No behaviour changed. (user: dmestas, size: 45577) [annotate] [blame] [check-ins using]
//! 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 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("" ** 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 = "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 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 = "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 }); }