Skip to content
zit Artifact [23703a9e14]
Login

Artifact [23703a9e14]

Check-ins Using Download Hex

Artifact 23703a9e145e2248fa08f0426430dc928eabdfe02108e67d2347f07d05539260:

//! The extras enumeration query: the ONE deep sweep module behind `zit extras`
//! (contracts/extras.md, B-extras-1..18). It walks the checkout tree once with
//! explicit traversal bounds, collects every on-disk regular file or symlink
//! whose root-relative path is neither tracked (the managed set) nor a
//! never-tracked control entry, and returns them sorted ascending by bytes.
//!
//! Deep-module boundary (B-extras-18): the sweep takes an injected `std.Io`, an
//! allocator, an opened ITERABLE checkout-root dir, and the managed set — no
//! ambient filesystem, no `std.http`, no clock or randomness. It reads only the
//! tree it is handed and yields the sorted list; the verb layer only renders,
//! and `zit clean` consumes the SAME sweep unchanged (a clean that re-walks the
//! tree is an automatic revise).

const std = @import("std");
const zit = @import("zit");
const managed = zit.managed;
const control_paths = zit.control_paths;

const assert = std.debug.assert;

/// `.zit-tmp-pack`, the pack-scratch name. Owned here so the single control
/// predicate (`isControlName`) and the pack writer name it from one place;
/// `main.pack_tmp_filename` references this const (B-extras-5).
pub const pack_tmp_filename: []const u8 = ".zit-tmp-pack";

/// `.zit-cache`, the repo-cache name. The authoritative definition lives in the
/// library-internal `repocache.zig` (`repocache.cache_filename`), which is not
/// re-exported through the public `zit` surface, so the never-tracked predicate
/// mirrors the byte value here rather than importing across the CLI/library
/// boundary. Both spellings are one literal; a change to either is a review
/// tripwire (B-extras-5).
pub const cache_filename: []const u8 = ".zit-cache";

/// `.zit-import-map.jsonl`, the provenance index atomically published by
/// `import-git`. It is repository metadata, never a user working-tree file.
pub const import_map_filename: []const u8 = ".zit-import-map.jsonl";

/// `refs`, the directory containing canonical import-git ref mappings. It is
/// repository metadata, never a user working-tree root component.
pub const import_refs_dirname: []const u8 = "refs";

/// Total directory entries the walk may EXAMINE before it gives up. Reuses the
/// managed set's entry ceiling: a checkout with more loose entries than the set
/// could ever track is not one extras enumerates silently. Over this bound the
/// sweep RETURNS `error.TooMany` (a handled user-content condition, never an
/// abort) — the same shape `managed.zig` uses (B-extras-7 TigerStyle bound).
const max_entries: usize = max_sweep_entries;

/// The sweep's OWN ceiling, no longer borrowed from `managed.max_entries`.
///
/// It used to be that constant, on the reasoning that "a checkout with more
/// loose entries than the set could ever track is not one extras enumerates
/// silently". That reads well and is the wrong quantity: `managed.max_entries`
/// bounds how many paths a tracked set can REPRESENT, and is now the format's
/// u32 range — while this bounds how many directory entries a filesystem walk
/// will visit before giving up, which is a runaway-walk guard over untrusted
/// on-disk shape and has nothing to do with what the set can hold. Deriving one
/// from the other meant a change to the tracked-set format silently widened a
/// filesystem tripwire.
///
/// A tenth of a million loose files is far past any checkout a person is
/// working in and still small enough to stop a pathological tree quickly. Over
/// it the sweep RETURNS `error.TooMany` — a handled user-content condition,
/// never an abort — which `sweepBounded` already takes as a parameter, so a
/// caller needing a different ceiling passes one rather than editing this.
const max_sweep_entries: usize = 100_000;

/// Descent-depth ceiling. Deeper than any real checkout; a legitimately deeper
/// tree fails cleanly with `error.TooDeep`, it does not recurse without a bound
/// (B-extras-7). The DEPTH is the number of directory levels below the root.
const max_depth: usize = 1024;

/// The iterable, no-follow open options every descended directory uses — the
/// same flags the checkout-tree walkers elsewhere open with, so a symlinked
/// directory is never entered and the walk stays inside the real tree.
const iter_open_opts: std.Io.Dir.OpenOptions = .{
    .access_sub_paths = true,
    .iterate = true,
    .follow_symlinks = false,
};

/// Closed sweep error set. There is deliberately NO "empty"/"not-found"
/// variant: an empty checkout and a checkout with no extras both yield an empty
/// `Extras` (B-extras-10). The ceilings are HANDLED errors, not asserts — a
/// legitimately deep or huge checkout is ordinary user content, not corruption,
/// and must never abort `zit`.
pub const SweepError = error{
    /// A readdir/openDir/stat failed.
    Storage,
    /// Allocation failed.
    OutOfMemory,
    /// Entries examined exceeded `max_entries`.
    TooMany,
    /// Descent depth exceeded `max_depth`.
    TooDeep,
};

/// One swept extra: its root-relative path plus the ONE bit of the walk's
/// classification a caller cannot cheaply recover — whether the on-disk entry
/// is a symlink. The walk already lstat-classified every entry (`resolveKind`);
/// carrying the verdict here keeps kind classification inside this deep module
/// instead of forcing `add`/`addremove` to re-stat and re-decide (B-add-5 and
/// commit's symlink refusal must agree with this bit, not re-derive it).
/// Readers that treat every extra alike (`extras`, `clean`) ignore the tag.
pub const Entry = struct {
    /// Root-relative, clean (no leading `/`, no `./`, no trailing `/`).
    path: []const u8,
    /// The entry is a symlink; 0.1.0 does not version symlinks, so the
    /// tracking verbs skip these while the enumerating verbs still list them.
    is_symlink: bool,
};

/// A sorted, unique, owned list of root-relative extras. Owns every path byte;
/// the caller calls `deinit`. Empty is a value, never an error (B-extras-10).
pub const Extras = struct {
    gpa: std.mem.Allocator,
    /// Strictly ascending by `path` bytes, unique. Each path heap-owned.
    entries: std.ArrayList(Entry),

    /// An empty result. Allocates nothing.
    pub fn init(gpa: std.mem.Allocator) Extras {
        return .{ .gpa = gpa, .entries = .empty };
    }

    /// Frees every owned path and the backing array.
    pub fn deinit(self: *Extras) void {
        for (self.entries.items) |e| self.gpa.free(e.path);
        self.entries.deinit(self.gpa);
        self.* = undefined;
    }

    /// The sorted extras, ascending by path bytes. Borrows `self`.
    pub fn items(self: *const Extras) []const Entry {
        return self.entries.items;
    }
};

/// The authoritative never-tracked set rooted in the first path component
/// (B-extras-5). A STRICT SUPERSET of the shipped add/rm control-file refusal
/// (`.zit`, `.zit-checkout`, `.zit-managed`, `.zit-undo`), extended with
/// transient repository artifacts, import provenance, canonical import refs,
/// and checkout-local bisection state. `control_paths` owns the public-layer
/// definition shared with the importer, so the admission and sweep boundaries
/// cannot drift. Pure; no I/O, no allocation.
pub fn isControlName(path: []const u8) bool {
    return control_paths.isReservedRoot(path);
}

/// Walk `root` (an opened ITERABLE checkout-root dir), collecting every on-disk
/// regular file or symlink whose root-relative path is neither tracked nor
/// rooted in a never-tracked control entry, sorted ascending by bytes.
/// Read-only; all I/O via `io`. The public entry uses the module ceilings; the
/// bounds are a separate parameter only so the ceiling tests can lower them.
pub fn sweep(
    gpa: std.mem.Allocator,
    io: std.Io,
    root: std.Io.Dir,
    tracked: *const managed.ManagedSet,
) SweepError!Extras {
    return sweepBounded(gpa, io, root, tracked, max_entries, max_depth);
}

/// The walk context, threaded down the recursion so each frame carries the
/// shared allocator, io, tracked set, output list, and the running entry
/// counter plus the two ceilings. Keeps `sweepDir` a pure structural walk.
const Context = struct {
    gpa: std.mem.Allocator,
    io: std.Io,
    tracked: *const managed.ManagedSet,
    list: *std.ArrayList(Entry),
    visited: usize,
    entry_ceiling: usize,
    depth_ceiling: usize,
};

fn sweepBounded(
    gpa: std.mem.Allocator,
    io: std.Io,
    root: std.Io.Dir,
    tracked: *const managed.ManagedSet,
    entry_ceiling: usize,
    depth_ceiling: usize,
) SweepError!Extras {
    var result = Extras.init(gpa);
    errdefer result.deinit();

    var ctx: Context = .{
        .gpa = gpa,
        .io = io,
        .tracked = tracked,
        .list = &result.entries,
        .visited = 0,
        .entry_ceiling = entry_ceiling,
        .depth_ceiling = depth_ceiling,
    };
    try sweepDir(&ctx, root, "", 0);

    std.mem.sort(Entry, result.entries.items, {}, lessThanPath);

    // Postconditions (positive AND negative space, B-extras-2/3/4/5): the list
    // is strictly ascending and unique, every path is clean and root-relative,
    // none is tracked, and no path is rooted in a control entry.
    assert(strictlyAscending(result.entries.items));
    for (result.entries.items) |e| {
        const p = e.path;
        assert(p.len != 0);
        assert(p[0] != '/');
        assert(p[p.len - 1] != '/');
        assert(!std.mem.startsWith(u8, p, "./"));
        assert(!tracked.contains(p));
        assert(!isControlName(p));
    }
    return result;
}

/// One directory level. Iterates `dir`'s entries, classifying each: a file or
/// symlink is collected (its own root-relative path), a directory is descended
/// (unless a root-level control dir), a special file is neither. The `visited`
/// ceiling bounds the loop; `depth` bounds the descent (B-extras-6/7/8/9).
fn sweepDir(ctx: *Context, dir: std.Io.Dir, prefix: []const u8, depth: usize) SweepError!void {
    if (depth >= ctx.depth_ceiling) return error.TooDeep;

    var it = dir.iterate();
    while (it.next(ctx.io) catch return error.Storage) |entry| {
        ctx.visited += 1;
        if (ctx.visited > ctx.entry_ceiling) return error.TooMany;

        const full = joinRootRel(ctx.gpa, prefix, entry.name) catch return error.OutOfMemory;
        var keep = false;
        defer if (!keep) ctx.gpa.free(full);

        // Root-level control entries are neither emitted nor descended: control
        // files are excluded and control directories pruned (B-extras-5/-6).
        // Below the root the names carry no special meaning.
        if (depth == 0 and isControlName(full)) continue;

        const kind = try resolveKind(ctx, dir, entry);
        switch (kind) {
            // A regular file OR a symlink is an extra iff its root-relative path
            // is not tracked (B-extras-4): the contract's extras set subtracts
            // the managed set from BOTH kinds. A tracked path never appears even
            // when the on-disk entry is a symlink whose name matches a managed
            // key. A symlink is listed by its own path but never followed — no
            // descent, no target resolution (B-extras-9).
            .file, .sym_link => {
                if (ctx.tracked.contains(full)) continue;
                ctx.list.append(
                    ctx.gpa,
                    .{ .path = full, .is_symlink = kind == .sym_link },
                ) catch return error.OutOfMemory;
                keep = true;
            },
            .directory => {
                var child = dir.openDir(ctx.io, entry.name, iter_open_opts) catch return error.Storage;
                defer child.close(ctx.io);
                try sweepDir(ctx, child, full, depth + 1);
                // The directory itself is never emitted (B-extras-8); only files
                // within it can appear. `full` is freed by the defer above.
            },
            // A block/char/fifo/socket special file is not an extra by the
            // contract's definition (a regular file or symlink) and not a
            // directory to descend — a correct-by-definition exclusion.
            else => {},
        }
    }
}

/// The entry's kind, trusting readdir only for the three kinds it names
/// reliably. On a filesystem whose readdir returns `.unknown` (DT_UNKNOWN), a
/// real file or symlink is stat-classified with a no-follow lstat rather than
/// dropped — silently skipping it would violate B-extras-1/-9 and TigerStyle's
/// no-silent-truncation. A stat failure surfaces as `error.Storage`.
fn resolveKind(ctx: *Context, dir: std.Io.Dir, entry: std.Io.Dir.Entry) SweepError!std.Io.File.Kind {
    if (entry.kind == .file or entry.kind == .sym_link or entry.kind == .directory)
        return entry.kind;
    const st = dir.statFile(ctx.io, entry.name, .{ .follow_symlinks = false }) catch
        return error.Storage;
    // A stat that still cannot name the kind is an impossible platform state —
    // a real file/symlink is already classified by lstat.
    assert(st.kind != .unknown);
    return st.kind;
}

/// Builds a root-relative path from a parent `prefix` and an entry `name`
/// (B-extras-3): a root file (empty prefix) is its bare name — no separator
/// prepended — a nested file is `prefix ++ "/" ++ name`. `/` separators, no
/// leading `./`, no leading `/`. Owned by the caller.
fn joinRootRel(gpa: std.mem.Allocator, prefix: []const u8, name: []const u8) error{OutOfMemory}![]u8 {
    if (prefix.len == 0) return gpa.dupe(u8, name);
    const out = try gpa.alloc(u8, prefix.len + 1 + name.len);
    @memcpy(out[0..prefix.len], prefix);
    out[prefix.len] = '/';
    @memcpy(out[prefix.len + 1 ..], name);
    return out;
}

fn lessThanPath(_: void, a: Entry, b: Entry) bool {
    return std.mem.lessThan(u8, a.path, b.path);
}

/// Whether `entries` is strictly ascending by path bytes (hence sorted and
/// unique). The `is_symlink` tag never participates in the order.
fn strictlyAscending(entries: []const Entry) bool {
    if (entries.len < 2) return true;
    for (entries[1..], entries[0 .. entries.len - 1]) |cur, prev| {
        if (std.mem.order(u8, prev.path, cur.path) != .lt) return false;
    }
    return true;
}

// ---------------------------------------------------------------------------
// Tests. Oracle: contracts/extras.md (B-extras-N). Expected values derive from
// the clause text and inline ASCII byte values, never from running fossil.
// Tests bind `std.testing.io` + a `tmpDir`; the sweep is handed an iterable
// re-open of the tmp root.
// ---------------------------------------------------------------------------

const testing = std.testing;

/// Opens `tmp`'s root as an iterable, no-follow handle for the sweep — the same
/// shape the verb hands `sweep` after re-opening `probeRoot`'s non-iterable
/// handle. Caller closes.
fn openIterable(io: std.Io, tmp: std.Io.Dir) !std.Io.Dir {
    return tmp.openDir(io, ".", iter_open_opts);
}

/// An empty managed set (nothing tracked) for the common case.
fn emptyManaged() managed.ManagedSet {
    return managed.ManagedSet.init(testing.allocator);
}

/// Asserts the sweep's items equal `expected` exactly, in order.
fn expectItems(result: *const Extras, expected: []const []const u8) !void {
    try testing.expectEqual(expected.len, result.items().len);
    for (expected, result.items()) |want, got| try testing.expectEqualStrings(want, got.path);
}

test "extras B-extras-2/3: collect-then-sort yields byte-lexicographic order" {
    // On disk: file `b`, file `a.txt`, dir `a/` holding file `z`; none tracked.
    // ASCII: `a.txt` vs `a/z` differ at index 1, `.`=0x2E < `/`=0x2F ⇒ `a.txt`
    // sorts before `a/z`; both precede `b` (0x62). A naive DFS that descends `a`
    // before emitting the sibling `a.txt` would emit `a/z` first — the wrong,
    // enumeration-order-dependent answer this ordering rules out.
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try touchAt(io, tmp.dir, "b");
    try touchAt(io, tmp.dir, "a.txt");
    try tmp.dir.createDir(io, "a", .default_dir);
    try touchAt(io, tmp.dir, "a/z");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);

    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try expectItems(&result, &.{ "a.txt", "a/z", "b" });
}

test "extras B-extras-4: a tracked file on disk is never collected" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try touchAt(io, tmp.dir, "keep");
    try touchAt(io, tmp.dir, "loose");

    var set = emptyManaged();
    defer set.deinit();
    _ = try set.insert("keep");

    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try expectItems(&result, &.{"loose"});
}

test "extras B-extras-5: root control entries are excluded" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // Every never-tracked control FILE at the root, plus one real file.
    // Derived from the shared registry, so a rename or addition there reaches
    // this sweep automatically instead of leaving a stale literal behind.
    inline for (control_paths.reserved) |entry| {
        if (comptime !entry.prefix) try touchAt(io, tmp.dir, entry.name);
    }
    try touchAt(io, tmp.dir, ".zit-update-txn-crashed"); // the prefix entry, as a crash leaves it
    try touchAt(io, tmp.dir, "real");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try expectItems(&result, &.{"real"});
}

test "extras B-extras-6: control directories are pruned, not descended" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // `.zit/`, `.zit-pack-tmp/`, and imported `refs/`, each holding a file
    // that must never leak.
    try tmp.dir.createDir(io, ".zit", .default_dir);
    try touchAt(io, tmp.dir, ".zit/object");
    try tmp.dir.createDir(io, ".zit-tmp-pack", .default_dir);
    try touchAt(io, tmp.dir, ".zit-tmp-pack/scratch");
    // Any name under the scratch prefix, not only the ones zit writes today:
    // the prefix is the contract, and junk a crashed future verb strands must
    // already be invisible.
    try tmp.dir.createDir(io, ".zit-tmp-junk-x", .default_dir);
    try touchAt(io, tmp.dir, ".zit-tmp-junk-x/leftover");
    // The advisory tier's directory form: members must never surface.
    try tmp.dir.createDir(io, ".zit-cache", .default_dir);
    try touchAt(io, tmp.dir, ".zit-cache/repo");
    try touchAt(io, tmp.dir, ".zit-cache/vstat");
    try tmp.dir.createDir(io, import_refs_dirname, .default_dir);
    try touchAt(io, tmp.dir, "refs/sym-heads");
    try touchAt(io, tmp.dir, "visible");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try expectItems(&result, &.{"visible"});
}

test "extras B-extras-7: files at depth are found" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try tmp.dir.createDirPath(io, "sub/dir");
    try touchAt(io, tmp.dir, "sub/dir/name");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try expectItems(&result, &.{"sub/dir/name"});
}

test "extras B-extras-8: an empty directory contributes nothing" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try tmp.dir.createDir(io, "d", .default_dir); // wholly empty

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try testing.expectEqual(@as(usize, 0), result.items().len);
}

test "extras B-extras-9: a symlink is listed but never followed" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // A real dir `target/` holding `inner`, and a symlink `ln` → `target`.
    try tmp.dir.createDir(io, "target", .default_dir);
    try touchAt(io, tmp.dir, "target/inner");
    tmp.dir.symLink(io, "target", "ln", .{}) catch |e| switch (e) {
        // A platform/sandbox that cannot create symlinks cannot exercise this.
        error.AccessDenied, error.PermissionDenied => return error.SkipZigTest,
        else => return e,
    };

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    // `ln` is listed (its own path); the walk never descends it, so `ln/inner`
    // never appears. `target/inner` (a real file) does.
    try expectItems(&result, &.{ "ln", "target/inner" });
    // The walk's kind verdict rides out on the entry so `add`/`addremove` can
    // skip symlinks without re-stat'ing (B-add-5 / 0.1.0 symlink refusal): the
    // symlink carries the tag, the real file does not.
    try testing.expect(result.items()[0].is_symlink);
    try testing.expect(!result.items()[1].is_symlink);
}

test "extras B-extras-4: a tracked symlink on disk is never collected" {
    // The managed set is a set of path strings, never re-validated against the
    // on-disk kind: a path tracked while it was a regular file stays tracked if
    // the user later replaces it with a symlink of the same name. The extras set
    // subtracts the managed set from symlinks as well as files (B-extras-4), so
    // the tracked symlink must not appear and must not trip the postcondition.
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try touchAt(io, tmp.dir, "target"); // a link target so the entry resolves
    tmp.dir.symLink(io, "target", "keep", .{}) catch |e| switch (e) {
        error.AccessDenied, error.PermissionDenied => return error.SkipZigTest,
        else => return e,
    };
    try touchAt(io, tmp.dir, "loose");

    var set = emptyManaged();
    defer set.deinit();
    _ = try set.insert("keep"); // tracked, though on disk it is now a symlink

    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    // `keep` (tracked symlink) is excluded; `target` and `loose` remain.
    try expectItems(&result, &.{ "loose", "target" });
}

test "extras B-extras-10: no extras yields an empty list" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // A checkout whose only on-disk files are all tracked ⇒ zero extras.
    try touchAt(io, tmp.dir, "a");
    try touchAt(io, tmp.dir, "b");

    var set = emptyManaged();
    defer set.deinit();
    _ = try set.insert("a");
    _ = try set.insert("b");

    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    var result = try sweep(gpa, io, root, &set);
    defer result.deinit();
    try testing.expectEqual(@as(usize, 0), result.items().len);
}

test "extras B-extras-7: max_entries ceiling returns error.TooMany, not a panic" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    for ([_][]const u8{ "f0", "f1", "f2", "f3" }) |name| try touchAt(io, tmp.dir, name);

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    // A ceiling below the entry count is a clean handled error, never a crash.
    try testing.expectError(error.TooMany, sweepBounded(gpa, io, root, &set, 2, max_depth));
}

test "extras B-extras-7: max_depth ceiling returns error.TooDeep, not a panic" {
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try tmp.dir.createDirPath(io, "a/b/c");
    try touchAt(io, tmp.dir, "a/b/c/deep");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);
    // A ceiling shallower than the tree fails cleanly (exit 1 at the verb).
    try testing.expectError(error.TooDeep, sweepBounded(gpa, io, root, &set, max_entries, 2));
}

test "extras isControlName: full keys rooted in metadata are never tracked" {
    // Add and move hand this predicate root-relative full keys, while the sweep
    // hands it root entries. Both forms share the same root-component admission.
    const control = [_][]const u8{
        ".zit",
        ".zit/object",
        ".zit-checkout",
        ".zit-managed/entries",
        ".zit-undo/transaction",
        ".zit-bisect/state",
        ".zit-cache/data",
        ".zit-vstat",
        ".zit-vstat/data",
        ".zit-tmp-pack/scratch",
        ".zit-tmp-junk-x/leftover",
        import_map_filename,
        ".zit-import-map.jsonl/sidecar",
        import_refs_dirname,
        "refs/heads/main",
    };
    for (control) |name| try testing.expect(isControlName(name));

    // A control-looking non-root component and similarly prefixed root names
    // remain ordinary managed-content candidates.
    const ordinary = [_][]const u8{
        "zit",
        "sub/.zit-cache",
        "sub",
        ".zit-other",
        ".zit-cacheable/data",
        "refs-old/heads/main",
        "sub/refs/heads/main",
        "",
    };
    for (ordinary) |name| try testing.expect(!isControlName(name));
}

test "extras B-extras-9: an unknown-kind entry is stat-classified, not dropped" {
    // `resolveKind` maps a readdir kind that is not one of the three trusted
    // kinds through a no-follow lstat rather than dropping it. A real file whose
    // `entry.kind` is forced to `.unknown` must still resolve to `.file`.
    const gpa = testing.allocator;
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try touchAt(io, tmp.dir, "u");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);

    var ctx: Context = .{
        .gpa = gpa,
        .io = io,
        .tracked = &set,
        .list = undefined,
        .visited = 0,
        .entry_ceiling = max_entries,
        .depth_ceiling = max_depth,
    };
    const forced: std.Io.Dir.Entry = .{ .name = "u", .kind = .unknown, .inode = 0 };
    try testing.expectEqual(std.Io.File.Kind.file, try resolveKind(&ctx, root, forced));
}

fn sweepNoLeak(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, set: *const managed.ManagedSet) !void {
    var result = try sweep(gpa, io, dir, set);
    defer result.deinit();
}

test "extras sweep: allocation failure propagates without leaking" {
    const io = testing.io;
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try touchAt(io, tmp.dir, "a.txt");
    try tmp.dir.createDir(io, "sub", .default_dir);
    try touchAt(io, tmp.dir, "sub/b");
    try touchAt(io, tmp.dir, "c");

    var set = emptyManaged();
    defer set.deinit();
    var root = try openIterable(io, tmp.dir);
    defer root.close(io);

    try testing.checkAllAllocationFailures(testing.allocator, sweepNoLeak, .{ io, root, &set });
}

test "extras sweep fuzz: never crashes and always returns a valid or declared-error result" {
    // Seeded-deterministic fuzz over random real trees: whatever shape the
    // filesystem takes (nested dirs, control-looking names, symlink loops back
    // to the root, mixed kinds), the bounded walk must yield a sorted+unique
    // extras list or a declared `SweepError` — never a crash, and never an
    // unbounded descent (symlinks are listed, never followed — B-extras-2/-7/-9).
    const gpa = testing.allocator;
    const io = testing.io;
    var prng = std.Random.DefaultPrng.init(0x2117_e547_a500);
    const rand = prng.random();

    const names = [_][]const u8{ "a", "b", "c", "a.txt", ".zit-cache", ".hidden", "d" };
    var iter: usize = 0;
    while (iter < 64) : (iter += 1) {
        var tmp = testing.tmpDir(.{});
        defer tmp.cleanup();

        // Build a small random tree: at most a handful of dirs and files, plus
        // an occasional symlink pointing back up (a cycle the walk must not
        // follow). Every loop here has an explicit fixed bound.
        var dir_i: usize = 0;
        const dir_count = rand.intRangeAtMost(usize, 0, 3);
        while (dir_i < dir_count) : (dir_i += 1) {
            const d = names[rand.intRangeLessThan(usize, 0, names.len)];
            tmp.dir.createDir(io, d, .default_dir) catch {};
            const f = names[rand.intRangeLessThan(usize, 0, names.len)];
            var buf: [64]u8 = undefined;
            const path = std.fmt.bufPrint(&buf, "{s}/{s}", .{ d, f }) catch continue;
            touchAt(io, tmp.dir, path) catch {};
        }
        var file_i: usize = 0;
        const file_count = rand.intRangeAtMost(usize, 0, 4);
        while (file_i < file_count) : (file_i += 1) {
            const f = names[rand.intRangeLessThan(usize, 0, names.len)];
            touchAt(io, tmp.dir, f) catch {};
        }
        if (rand.boolean()) tmp.dir.symLink(io, ".", "loop", .{}) catch {};

        var set = emptyManaged();
        defer set.deinit();
        var root = openIterable(io, tmp.dir) catch continue;
        defer root.close(io);

        if (sweepBounded(gpa, io, root, &set, max_entries, max_depth)) |res_val| {
            var res = res_val;
            defer res.deinit();
            try testing.expect(strictlyAscending(res.items()));
            for (res.items()) |e| {
                const p = e.path;
                try testing.expect(p.len != 0);
                try testing.expect(p[0] != '/');
                try testing.expect(!std.mem.startsWith(u8, p, "./"));
            }
        } else |err| switch (err) {
            error.Storage, error.OutOfMemory, error.TooMany, error.TooDeep => {},
        }
    }
}

/// Creates an empty regular file at `path` under `dir` (parents must exist).
fn touchAt(io: std.Io, dir: std.Io.Dir, path: []const u8) !void {
    var f = try dir.createFile(io, path, .{});
    f.close(io);
}