Skip to content
zit Artifact [8e7635a9e3]
Login

Artifact [8e7635a9e3]

Check-ins Using Download Hex

Artifact 8e7635a9e381c894cd82a4f5df062f7281deb31815047f6dd57dfeb7c2e1935f:

//! 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. 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 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;

/// 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;
/// 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 one pending rename `zit mv` records for the next commit to consume,
    /// or null when none is pending (the common case; a pre-mv file and every
    /// post-clear file decode to null). Names are heap-owned.
    rename: ?Rename = null,

    /// 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);
        if (self.rename) |rn| {
            self.gpa.free(rn.old);
            self.gpa.free(rn.new);
        }
        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. One-shot and at-most-one: any prior pending rename is
    /// replaced, so the record never grows without bound. 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. 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)

        // Post-replace total: drop any existing record's bytes, add the new record.
        var base = self.bytes;
        if (self.rename) |cur| base -= renameBytes(cur);
        const grown = base + 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;

        if (self.rename) |cur| {
            self.gpa.free(cur.old);
            self.gpa.free(cur.new);
        }
        self.rename = .{ .old = old_owned, .new = new_owned };
        self.bytes = grown;

        assert(self.bytes <= max_file_bytes); // aggregate bound holds
    }

    /// The pending rename, or null when none is recorded. The ONE query
    /// `runCommit` uses to stamp the renamed capture's old-name (§4.7.6). Borrows
    /// the set; invalidated by `clearRename`/`recordRename`/`deinit`.
    pub fn pendingRename(self: *const ManagedSet) ?Rename {
        return self.rename;
    }

    /// Consumes the pending rename: frees its names and restores the byte image
    /// to the no-record form. Idempotent (a no-op when none is pending), so the
    /// commit that carried the rename clears it exactly once.
    pub fn clearRename(self: *ManagedSet) void {
        if (self.rename) |cur| {
            assert(self.bytes >= header_bytes + renameBytes(cur));
            self.bytes -= renameBytes(cur);
            self.gpa.free(cur.old);
            self.gpa.free(cur.new);
            self.rename = null;
        }
        assert(self.rename == null);
    }

    /// 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;
        }
        // Optional trailing pending-rename record: `old_len old new_len new`.
        // Absence writes nothing (byte-identical to a pre-mv image).
        if (self.rename) |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).
        if (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;

            if (pos != payload.len) return error.Corrupt; // no bytes past the record

            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;
            self.rename = .{ .old = old_owned, .new = new_owned };
            self.bytes += record_overhead + old_len + new_len;
        }

        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, plan E). A
    /// malformed record is `error.Corrupt`; any other I/O failure is
    /// `error.Storage`.
    ///
    /// The allocation is sized from `stat`, so it is the file rather than
    /// anything the file claims about itself. This doc used to say the size was
    /// "checked against `max_file_bytes` BEFORE allocation, so a lying file
    /// cannot force an oversized allocation" — but no length is read from the
    /// file here, so there was never a lie to prevent; the check only refused
    /// large-but-honest sets. Structural validation is `parse`'s job, and every
    /// record it reads is bounded against the payload it came from.
    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;
        // Sized from `stat`, not from a length the file declares: there is no
        // claim here to distrust, so the only genuine bound is whether the size
        // can be addressed at all. The unchecked `@intCast` this replaces was
        // also a latent 32-bit hazard, kept sound only by the flat cap above it.
        const size: usize = std.math.cast(usize, st.size) orelse return error.Corrupt;

        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 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, 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.
    {
        var f = try tmp.dir.createFile(io, filename, .{});
        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);
        if (s.pendingRename()) |rn| {
            const rrn = rt.pendingRename() orelse return error.NoRename;
            try testing.expectEqualSlices(u8, rn.old, rrn.old);
            try testing.expectEqualSlices(u8, rn.new, rrn.new);
        } else try testing.expect(rt.pendingRename() == null);

        // 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);
    const rn = got.pendingRename() orelse return error.NoRename;
    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.expect(got.pendingRename() == null); // 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();
    try testing.expectEqual(before, s.bytes);
    try testing.expect(s.pendingRename() == null);
    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 holds at most one pending rename (B-mv-18 bound)" {
    const gpa = testing.allocator;
    var s = ManagedSet.init(gpa);
    defer s.deinit();
    _ = try s.insert("n1");
    try s.recordRename("o1", "n1");

    _ = s.remove("n1");
    _ = try s.insert("n2");
    try s.recordRename("o2", "n2"); // replaces, does not accumulate

    const rn = s.pendingRename() orelse return error.NoRename;
    try testing.expectEqualStrings("o2", rn.old);
    try testing.expectEqualStrings("n2", rn.new);

    // The image carries exactly one record: it round-trips through parse.
    const buf = try gpa.alloc(u8, s.bytes);
    defer gpa.free(buf);
    var rt = try ManagedSet.parse(gpa, s.encode(buf));
    defer rt.deinit();
    const rrn = rt.pendingRename() orelse return error.NoRename;
    try testing.expectEqualStrings("o2", rrn.old);
    try testing.expectEqualStrings("n2", rrn.new);
    try testing.expectEqual(s.bytes, rt.bytes);
}

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 });
}