Artifact [98000540f7]

Artifact 98000540f71b1f8fa8a33d2f1da885a6c9c2507108fb1bc95630c3b6b4fab0dc:

• File src/artifact_fuzz.zig — part of check-in [72bba34ada] at 2026-07-28 03:31:28 on branch sub-manifest — Sub-manifest: complete the conformance corpus

  Sub-manifests have no reference implementation to check against, so the corpus is the oracle and had to be built rather than assumed. Adds the eleven vectors Appendix A.5 requires that were missing, among them the three-level tree whose absence is why the step-5 cursor contradiction survived into an implementation: no published artifact carried an interior node, so nothing exercised that path.

  Every authored vector is generated by the implementation and then rechecked along a path that shares no code with it, and each derived name is compared against the constant the test pins, so no hash in the corpus is hand-written. Two fuzz targets cover S-card classification and the tree walk.

  One A.5 bullet is not satisfiable as written: the re-tune vector asks for two parameters over the A.1 name list that yield trees sharing no sub-manifest, but that list's single qualifying boundary falls in the same place for the first three values and is suppressed above them. No vector was invented for it; an erratum is drafted and a test pins the finding so it stays visible. (user: dmestas, size: 39200) [annotate] [blame] [check-ins using] [more...]

//! Seeded, parameterized fuzz targets for the artifact format
//! (draft-fossil-artifact-format-00). Registered in fuzz_tests.zig.
//!
//! Contract for every target here, matching the module's own "every
//! rejection reason collapses to null/false/an error" posture: no panic, no
//! UB -- only a declared error, a null/false, or a value whose invariants
//! this file checks. `parseGarbage` drives the real §4/§5 `parse()`
//! pipeline (framing through classification) on arbitrary bytes;
//! `parseStructured` instead reaches the sixteen `parseXCard` entry points
//! directly, exercising each card's own §4.7.x grammar in isolation rather
//! than through the card-loop's dispatch.

const std = @import("std");
const zit = @import("zit");
const artifact = zit.artifact;

/// Fill `buf` with a mix of plausible card bytes (letters, digits, the
/// grammar's punctuation) and pure noise, biased toward reaching past the
/// first gate of whatever parser sees it.
fn fillGarbage(rand: std.Random, buf: []u8) void {
    const plausible = "ABCDEFGHIJKLMNPQRTUWZ 0123456789abcdef\n+-.:T";
    for (buf) |*b| b.* = if (rand.uintLessThan(u8, 3) == 0)
        plausible[rand.uintLessThan(usize, plausible.len)]
    else
        rand.int(u8);
}

// ---------------------------------------------------------------------------
// parseGarbage — §4 top-level entry point.
// ---------------------------------------------------------------------------

/// `parse` on arbitrary bytes never crashes: only a declared `ParseError` or
/// a `Manifest` value comes back.
///
/// No reachability assertion: the outcome space does not partition here. Random
/// bytes never satisfy §4 framing/syntax, so `parse` returns `SyntaxError`
/// every time — measured 20_000/20_000 SyntaxError at seed 1, zero accepts and
/// zero classification-stage (`ClassifyError`) rejections. The accept arm and
/// the classify variants are reached where structure exists: `createRoundTrip`
/// for accept, the deterministic §5 classify tests for the rest.
pub fn parseGarbage(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var buf: [512]u8 = undefined;
        const len = rand.uintLessThan(usize, buf.len + 1);
        fillGarbage(rand, buf[0..len]);
        if (artifact.parse(gpa, buf[0..len])) |m| {
            var mm = m;
            mm.deinit();
        } else |_| {}
    }
}

// ---------------------------------------------------------------------------
// parseStructured — the sixteen §4.7.x parseXCard entry points.
// ---------------------------------------------------------------------------

/// The card letters that have a `parseXCard` entry point today (the 21-letter
/// closed alphabet minus R/T/U/W, not yet implemented, and Z, which has no
/// per-card parser at all).
const parseable_letters = "ABCDEFGHIJKLMNPQ";
comptime {
    std.debug.assert(parseable_letters.len == 16);
}

/// One SP-joined token: a structured draw (hash-length hex, a timestamp
/// literal, a `q-sign` byte) or pure noise. Returns the written length,
/// capped to `buf.len`.
fn genOneToken(rand: std.Random, buf: []u8) usize {
    if (buf.len == 0) return 0;
    return switch (rand.uintLessThan(u8, 4)) {
        0 => blk: {
            const want: usize = if (rand.boolean()) 40 else 64;
            const n = @min(want, buf.len);
            for (buf[0..n]) |*b| b.* = "0123456789abcdef"[rand.uintLessThan(usize, 16)];
            break :blk n;
        },
        1 => blk: {
            const lit = timestamp_literals[rand.uintLessThan(usize, timestamp_literals.len)];
            const n = @min(lit.len, buf.len);
            @memcpy(buf[0..n], lit[0..n]);
            break :blk n;
        },
        2 => blk: {
            buf[0] = if (rand.boolean()) '+' else '-';
            break :blk 1;
        },
        else => blk: {
            const n = rand.uintLessThan(usize, @min(buf.len, 24) + 1);
            fillGarbage(rand, buf[0..n]);
            break :blk n;
        },
    };
}

const timestamp_literals = [_][]const u8{
    "2017-12-06T15:36:24.287", "2017-12-06", "15:36:24", "now", "2451545",
};

/// Fill `buf` with 0-4 SP-joined tokens (`genOneToken`). Returns the written
/// length.
fn genTokens(rand: std.Random, buf: []u8) usize {
    const token_count = rand.uintLessThan(usize, 5);
    var w: usize = 0;
    var t: usize = 0;
    while (t < token_count and w < buf.len) : (t += 1) {
        if (t != 0) {
            buf[w] = ' ';
            w += 1;
            if (w >= buf.len) break;
        }
        w += genOneToken(rand, buf[w..]);
    }
    return w;
}

/// Call the one `parseXCard` matching `card.letter` -- every parser's sole
/// caller precondition beyond argument shape (`std.debug.assert(card.letter
/// == '<X>')`), upheld here since `letter` is always drawn from
/// `parseable_letters`. `decode_buf` sized to the raw args length is always
/// sufficient: every parser's decoded fields are a subset of the same raw
/// bytes (decodeEscapes never grows), so no per-letter sizing is needed.
fn dispatchParse(card: artifact.CardLine, decode_buf: []u8) void {
    switch (card.letter) {
        'A' => _ = artifact.parseACard(card, decode_buf),
        'B' => _ = artifact.parseBCard(card),
        'C' => _ = artifact.parseCCard(card, decode_buf),
        'D' => _ = artifact.parseDCard(card),
        'E' => _ = artifact.parseECard(card),
        'F' => _ = artifact.parseFCard(card, decode_buf),
        'G' => _ = artifact.parseGCard(card),
        'H' => _ = artifact.parseHCard(card, decode_buf),
        'I' => _ = artifact.parseICard(card),
        'J' => _ = artifact.parseJCard(card, decode_buf),
        'K' => _ = artifact.parseKCard(card),
        'L' => _ = artifact.parseLCard(card, decode_buf),
        'M' => _ = artifact.parseMCard(card),
        'N' => _ = artifact.parseNCard(card, decode_buf),
        'P' => _ = artifact.parsePCard(card),
        'Q' => _ = artifact.parseQCard(card),
        else => unreachable, // letter always drawn from parseable_letters
    }
}

/// Every `parseXCard` on a structured-or-garbage card line never crashes:
/// only a declared per-card struct or null comes back (§4.7.2-§4.7.14).
///
/// No reachability assertion: this is sixteen heterogeneous per-card parsers
/// (optionals and error unions over distinct struct types), not one binary
/// outcome — there is no single accept/reject split to require, and each
/// card's accept and reject arms are pinned by its own deterministic §4.7.x
/// test in artifact.zig.
pub fn parseStructured(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var argbuf: [256]u8 = undefined;
        var decode_buf: [256]u8 = undefined;
        const letter = parseable_letters[rand.uintLessThan(usize, parseable_letters.len)];
        const args: ?[]const u8 = if (rand.boolean()) null else argbuf[0..genTokens(rand, &argbuf)];
        const card: artifact.CardLine = .{ .letter = letter, .args = args };
        dispatchParse(card, decode_buf[0..if (args) |a| a.len else 0]);
    }
}

// ---------------------------------------------------------------------------
// cardLine — §4.2 tokenizeCardLine.
// ---------------------------------------------------------------------------

/// Fill `buf` with a well-formed line for `tokenizeCardLine`'s precondition
/// (non-empty, no embedded LF, terminated by exactly one LF); content before
/// the LF is otherwise arbitrary. Returns the written length.
fn genLine(rand: std.Random, buf: []u8) usize {
    const body_len = 1 + rand.uintLessThan(usize, buf.len - 1);
    for (buf[0 .. body_len - 1]) |*b| {
        b.* = rand.int(u8);
        if (b.* == '\n') b.* = ' ';
    }
    buf[body_len - 1] = '\n';
    return body_len;
}

/// `tokenizeCardLine` on an arbitrary well-formed line never crashes, and
/// any returned `args` is a subslice of the input (§4.2).
///
/// No reachability assertion: `tokenize` needs a valid card letter in a
/// specific shape that a random first byte rarely forms — measured 38/20_000
/// tokenized at seed 1 — so the accept arm is too thin to floor robustly, and
/// it is pinned by the deterministic §4.2 tokenizer tests.
pub fn cardLine(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var buf: [128]u8 = undefined;
        const len = genLine(rand, &buf);
        const line = buf[0..len];
        if (artifact.tokenizeCardLine(line)) |card| {
            try std.testing.expect(artifact.isCardLetter(card.letter));
            if (card.args) |a| try std.testing.expect(a.len <= line.len);
        }
    }
}

// ---------------------------------------------------------------------------
// escapes — §4.3 decodeEscapes.
// ---------------------------------------------------------------------------

/// `decodeEscapes` on an arbitrary token never crashes; the decoded length
/// never exceeds the token's, and a backslash-free token decodes to itself
/// (§4.3).
///
/// No reachability assertion: `decodeEscapes` is total — it always returns a
/// decoded slice, there is no accept/reject arm to partition; the invariant is
/// the length/identity bound.
pub fn escapes(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var tok_buf: [128]u8 = undefined;
        var out_buf: [128]u8 = undefined;
        const len = rand.uintLessThan(usize, tok_buf.len + 1);
        fillGarbage(rand, tok_buf[0..len]);
        const token = tok_buf[0..len];
        const out = artifact.decodeEscapes(token, out_buf[0..len]);
        try std.testing.expect(out.len <= token.len);
        if (std.mem.indexOfScalar(u8, token, '\\') == null) {
            try std.testing.expectEqualSlices(u8, token, out);
        }
    }
}

// ---------------------------------------------------------------------------
// timestamp — §4.6.4 classifyTimestamp.
// ---------------------------------------------------------------------------

/// `classifyTimestamp` on arbitrary bytes never crashes (§4.6.4).
///
/// No reachability assertion: of the five `TimestampForm`s only `.julian` (a
/// bare digit run) is reachable from random bytes — measured 29 julian /
/// 19_971 null per 20_000 at seed 1, and zero date/time/date_time/relative,
/// which need `-`/`:`/`T` structure random input essentially never forms. One
/// thin arm plus null is not a partition worth flooring; the five forms are
/// pinned by the deterministic §4.6.4 classify tests.
pub fn timestamp(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var buf: [64]u8 = undefined;
        const len = rand.uintLessThan(usize, buf.len + 1);
        fillGarbage(rand, buf[0..len]);
        _ = artifact.classifyTimestamp(buf[0..len]);
    }
}

// ---------------------------------------------------------------------------
// framing — §4.1/§4.1.1/§6.2 frame, stripSignatureWrapper, verifyZCard.
// ---------------------------------------------------------------------------

/// The framing trio on arbitrary bytes never crashes; `stripSignatureWrapper`
/// and `frame` never grow their input (§4.1.1, §4.1).
///
/// No reachability assertion: random bytes never form a §4.1-framable body —
/// measured `frame` returned null 20_000/20_000 at seed 1 — and `verifyZCard`
/// only ever reaches `.absent` (plus a 2/20_000 incidental `.mismatch`), never
/// `.match`, which needs a real Z card. The accept and match arms are pinned by
/// `createRoundTrip` and the deterministic §6.2 verify tests.
pub fn framing(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var buf: [256]u8 = undefined;
        const len = rand.uintLessThan(usize, buf.len + 1);
        fillGarbage(rand, buf[0..len]);
        const bytes = buf[0..len];

        const stripped = artifact.stripSignatureWrapper(bytes);
        try std.testing.expect(stripped.len <= bytes.len);
        if (artifact.frame(bytes)) |framed| try std.testing.expect(framed.len <= bytes.len);
        _ = artifact.verifyZCard(bytes);
    }
}

// ---------------------------------------------------------------------------
// predicates — §4.5.3/§4.6 compare*, isSimplePathname, isWikiName, isReservedFilename.
// ---------------------------------------------------------------------------

fn reverseOrder(o: std.math.Order) std.math.Order {
    return switch (o) {
        .lt => .gt,
        .gt => .lt,
        .eq => .eq,
    };
}

/// The pathname/wiki-name/reserved-name/compare predicates on arbitrary
/// bytes never crash; `compareBytes` is reflexive and its swap is exactly
/// order-reversing (§4.5.3, §4.6.1-§4.6.3).
///
/// Reachability, asserted rather than assumed (the `serve_fuzz` idea): a run
/// must reach BOTH accept and reject for `isSimplePathname` and `isWikiName`,
/// or the generator has drifted so a predicate's true (or false) arm is never
/// exercised. Measured at seed 1, 20_000 rounds: simple-pathname 435 reject /
/// 19_565 accept, wiki-name 17_007 reject / 2_993 accept; at 512 rounds the
/// thinnest arm (simple-pathname reject) holds ≥6 across seeds 1-3, the floor.
/// `isReservedFilename` is deliberately excluded: it is true only for a fixed
/// name set random bytes never hit (measured 0/20_000 accept), so its accept
/// arm is unreachable here and is pinned by the deterministic §4.6.3 tests.
const predicates_min_rounds: usize = 512;
pub fn predicates(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var sp = [_]usize{0} ** 2;
    var wiki = [_]usize{0} ** 2;
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var abuf: [64]u8 = undefined;
        var bbuf: [64]u8 = undefined;
        const alen = rand.uintLessThan(usize, abuf.len + 1);
        const blen = rand.uintLessThan(usize, bbuf.len + 1);
        fillGarbage(rand, abuf[0..alen]);
        fillGarbage(rand, bbuf[0..blen]);
        const a = abuf[0..alen];
        const b = bbuf[0..blen];

        sp[@intFromBool(artifact.isSimplePathname(a))] += 1;
        wiki[@intFromBool(artifact.isWikiName(a))] += 1;
        _ = artifact.isReservedFilename(a);

        try std.testing.expectEqual(std.math.Order.eq, artifact.compareBytes(a, a));
        try std.testing.expectEqual(artifact.compareBytes(a, b), reverseOrder(artifact.compareBytes(b, a)));
    }
    if (rounds >= predicates_min_rounds and
        (sp[0] == 0 or sp[1] == 0 or wiki[0] == 0 or wiki[1] == 0))
    {
        std.debug.print(
            "artifact_predicates: {d} rounds reached simple-pathname[reject={d} accept={d}] " ++
                "wiki-name[reject={d} accept={d}] — a predicate no longer sees both arms\n",
            .{ rounds, sp[0], sp[1], wiki[0], wiki[1] },
        );
        return error.OutcomeUnreached;
    }
}

// ---------------------------------------------------------------------------
// createRoundTrip — §6/§4 create(), the writer.
// ---------------------------------------------------------------------------

const hex_chars = "0123456789abcdef";

/// Fill `buf` with random lowercase hex.
fn fillHex(rand: std.Random, buf: []u8) void {
    for (buf) |*b| b.* = hex_chars[rand.uintLessThan(usize, 16)];
}

/// Assemble a small, always-parseable MANIFEST-type artifact from a bounded
/// pool of random-but-valid card choices, with a correctly computed Z
/// checksum -- structured generation, not blind noise, so `create`'s
/// per-card writers actually get exercised (pure noise essentially never
/// satisfies the Z-checksum gate, so `parseGarbage`'s approach would drive
/// almost no traffic through `create` at all). Always emits at least one F
/// card, pinning classification to MANIFEST deterministically (§5.3) so the
/// rest of the pool (C/P/R/T/U) stays free to vary without touching §5.4's
/// per-type semantic checks.
fn genManifestCandidate(rand: std.Random, out: *std.ArrayList(u8), allocator: std.mem.Allocator) !void {
    out.clearRetainingCapacity();
    if (rand.boolean()) try out.appendSlice(allocator, "C generated\\stest\\scase\n");
    try out.appendSlice(allocator, "D 2026-07-02T11:18:42.940\n");

    const f_count = rand.uintLessThan(usize, 4) + 1; // >=1: keeps classification deterministic
    var i: usize = 0;
    while (i < f_count) : (i += 1) {
        var hbuf: [64]u8 = undefined;
        const hlen: usize = if (rand.boolean()) 40 else 64;
        fillHex(rand, hbuf[0..hlen]);
        try out.print(allocator, "F f{d:0>3}.txt {s}\n", .{ i, hbuf[0..hlen] });
    }

    if (rand.boolean()) {
        try out.appendSlice(allocator, "P\n");
    } else {
        var pbuf: [64]u8 = undefined;
        const plen: usize = if (rand.boolean()) 40 else 64;
        fillHex(rand, pbuf[0..plen]);
        try out.print(allocator, "P {s}\n", .{pbuf[0..plen]});
    }

    if (rand.boolean()) {
        var rbuf: [32]u8 = undefined;
        fillHex(rand, &rbuf);
        try out.print(allocator, "R {s}\n", .{rbuf});
    }

    if (rand.boolean()) {
        var tbuf: [64]u8 = undefined;
        const tlen: usize = if (rand.boolean()) 40 else 64;
        fillHex(rand, tbuf[0..tlen]);
        try out.print(allocator, "T +tag {s}\n", .{tbuf[0..tlen]});
    }

    if (rand.boolean()) try out.appendSlice(allocator, "U tester\n");

    var digest: [32]u8 = undefined;
    _ = artifact.selfChecksum(out.items, &digest);
    try out.print(allocator, "Z {s}\n", .{digest});
}

/// `create` on every generated-parseable candidate never crashes or leaks,
/// and its output is always itself re-parseable (§6/§4 writer round-trip)
/// with a matching self-checksum (§6.2), and a second `create` over the
/// re-parsed data is byte-identical to the first (`create` is a pure
/// function of the Manifest's data, §6.3.4).
///
/// No reachability assertion: every candidate is generated parseable, so a
/// successful create/parse/create round-trip is the only outcome — there is no
/// reject arm to reach (a candidate that fails to parse is skipped, not an
/// outcome the target is testing).
pub fn createRoundTrip(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var gen: std.ArrayList(u8) = .empty;
    defer gen.deinit(gpa);

    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        try genManifestCandidate(rand, &gen, gpa);
        var m = artifact.parse(gpa, gen.items) catch continue;
        defer m.deinit();

        const out1 = try artifact.create(&m, gpa);
        defer gpa.free(out1);
        try std.testing.expectEqual(artifact.ZVerdict.match, artifact.verifyZCard(out1));

        var m1 = try artifact.parse(gpa, out1);
        defer m1.deinit();

        const out2 = try artifact.create(&m1, gpa);
        defer gpa.free(out2);
        try std.testing.expectEqualSlices(u8, out1, out2);
    }
}

// ---------------------------------------------------------------------------
// submanifestCards — draft-fossil-submanifests-00 §3/§4, the S card and the
// SUBMANIFEST type.
// ---------------------------------------------------------------------------

/// Filename TOKENS for the card target -- raw, as they appear on the wire, not
/// decoded. Drawn independently per card and deliberately not held in order, so
/// most multi-card runs violate §3.4's strict ascent and the ones that do not
/// are the accept arm. Two entries carry §4.3 escapes, so acceptance turns on
/// the DECODED name rather than the token; `e/f.c` is a path; and `bad name.c`
/// holds a raw SP, which splits into an extra token and so can only ever be
/// rejected.
const sm_names = [_][]const u8{
    "a.c", "b.c", "c.c", "d.c", "e/f.c", "g\\\\h.c", "i\\sj.c", "bad name.c",
};

/// One `F` or `S` card line into `out`. Hash tokens are drawn 40/64 (legal) or
/// a short length (illegal), and an `F` card is sometimes emitted hashless --
/// the §4.7.6 delete marker, which §4.4 forbids inside a sub-manifest.
fn genSubCard(rand: std.Random, letter: u8, out: *std.ArrayList(u8), gpa: std.mem.Allocator) !void {
    const name = sm_names[rand.uintLessThan(usize, sm_names.len)];
    if (letter == 'F' and rand.uintLessThan(u8, 8) == 0) {
        try out.print(gpa, "F {s}\n", .{name});
        return;
    }
    var hbuf: [64]u8 = undefined;
    const hlen: usize = switch (rand.uintLessThan(u8, 8)) {
        0 => 1 + rand.uintLessThan(usize, 63), // §3.5/§4.7.1 reject
        1...4 => 40,
        else => 64,
    };
    fillHex(rand, hbuf[0..hlen]);
    try out.print(gpa, "{c} {s} {s}\n", .{ letter, name, hbuf[0..hlen] });
}

/// A candidate artifact over F cards, S cards, or both, with a correct Z card
/// so the §4.1 framing gate never masks the §3/§4.4 checks under test. `D` is
/// drawn independently because it is §4.3's whole discriminator: the same card
/// set is a MANIFEST with it and a SUBMANIFEST without it.
fn genSubCandidate(rand: std.Random, out: *std.ArrayList(u8), gpa: std.mem.Allocator) !void {
    out.clearRetainingCapacity();
    if (rand.boolean()) try out.appendSlice(gpa, "D 2026-07-02T11:18:42.940\n");

    const n_f = rand.uintLessThan(usize, 3);
    const n_s = rand.uintLessThan(usize, 3);
    // Cards are emitted F before S so §4.4's card-order rule never decides the
    // outcome on its own; ordering WITHIN each run is what varies.
    var i: usize = 0;
    while (i < n_f) : (i += 1) try genSubCard(rand, 'F', out, gpa);
    i = 0;
    while (i < n_s) : (i += 1) try genSubCard(rand, 'S', out, gpa);

    var digest: [32]u8 = undefined;
    _ = artifact.selfChecksum(out.items, &digest);
    try out.print(gpa, "Z {s}\n", .{digest});
}

/// The §3 S card grammar and the §4.3/§4.4 SUBMANIFEST rules on generated
/// artifacts: no crash, and every artifact that survives `parse` satisfies the
/// invariants §4.4 states, checked here rather than trusted.
///
/// Reachability, asserted: a run must reach an accepted artifact carrying an S
/// run, an accepted SUBMANIFEST, and a rejection. Measured at seed 1, 20_000
/// rounds: 2_241 accepted-with-S, 2_081 accepted SUBMANIFEST, 15_689 rejected;
/// at 512 rounds the thinnest arm (accepted SUBMANIFEST) holds 43-52 across
/// seeds 1-3, which is the floor.
const submanifest_cards_min_rounds: usize = 512;
pub fn submanifestCards(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var gen: std.ArrayList(u8) = .empty;
    defer gen.deinit(gpa);

    var with_s: usize = 0;
    var as_sub: usize = 0;
    var rejected: usize = 0;

    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        // §3.6's grammar in isolation, on a line the tokenizer may or may not
        // even accept: "s-card = %x53 SP filename SP hash LF".
        gen.clearRetainingCapacity();
        try genSubCard(rand, 'S', &gen, gpa);
        if (artifact.tokenizeCardLine(gen.items)) |card| {
            var decode_buf: [128]u8 = undefined;
            const args_len = if (card.args) |a| a.len else 0;
            if (artifact.parseSCard(card, decode_buf[0..args_len])) |sc| {
                // §3.6: "the hash is never decoded" -- it is a subslice of the
                // line, and the filename never grows past its raw token.
                try std.testing.expect(sc.hash.len == 40 or sc.hash.len == 64);
                try std.testing.expect(sc.filename.len <= gen.items.len);
            }
        }

        try genSubCandidate(rand, &gen, gpa);
        var m = artifact.parse(gpa, gen.items) catch {
            rejected += 1;
            continue;
        };
        defer m.deinit();

        if (m.s.len != 0) {
            with_s += 1;
            // §4.4: "a manifest carrying both F and S cards" is rejected, and
            // so is a sub-manifest carrying both.
            try std.testing.expectEqual(@as(usize, 0), m.f.len);
            // §3.4: "an S run MUST strictly ascend by decoded filename."
            for (m.s[1..], m.s[0 .. m.s.len - 1]) |cur, prev| {
                try std.testing.expectEqual(
                    std.math.Order.lt,
                    artifact.compareBytes(prev.filename, cur.filename),
                );
            }
        }

        if (m.kind == .submanifest) {
            as_sub += 1;
            // §4.3's discriminator, the other way round: a SUBMANIFEST never
            // carries a D card.
            try std.testing.expect(m.d == null);
            // §4.4: F or S, never both, never neither.
            try std.testing.expect((m.f.len == 0) != (m.s.len == 0));
            // §4.4: "a sub-manifest F card without a hash" is rejected.
            for (m.f) |fc| try std.testing.expect(fc.hash != null);
        } else {
            // With a D card the artifact stays a check-in manifest, S run or
            // not -- §5's "a manifest is a tree manifest if and only if it
            // contains an S card" never changes the TYPE.
            try std.testing.expect(m.d != null);
        }
    }

    if (rounds >= submanifest_cards_min_rounds and (with_s == 0 or as_sub == 0 or rejected == 0)) {
        std.debug.print(
            "artifact_submanifest_cards: {d} rounds reached with-S={d} submanifest={d} " ++
                "rejected={d} — an outcome is no longer generated\n",
            .{ rounds, with_s, as_sub, rejected },
        );
        return error.OutcomeUnreached;
    }
}

// ---------------------------------------------------------------------------
// submanifestTreeWalk — draft-fossil-submanifests-00 §5.1/§5.2/§5.3, the walk.
// ---------------------------------------------------------------------------

/// Artifact names for the generated node table. Ten names for at most
/// `sm_max_nodes` real nodes, so an S card drawn from the whole list points at
/// a node that does not exist about as often as at one that does -- §5.2's
/// "absent ... unresolvable" arm, generated rather than special-cased.
const sm_node_names = [_][]const u8{ "n0", "n1", "n2", "n3", "n4", "n5", "n6", "n7", "n8", "n9" };
const sm_max_nodes: usize = 8;
const sm_max_cards: usize = 3;

/// The §5.2 seam over a generated table, counting resolutions that FAILED.
/// That counter is the whole point: §5.2 says an implementation "MUST NOT
/// present a partially resolved tree as a complete file set", and a walk that
/// ran to completion after any failed resolution has done exactly that.
const SmFuzzStore = struct {
    entries: []const Entry,
    misses: usize = 0,

    const Entry = struct { name: []const u8, view: artifact.SubManifestView };

    fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
        const self: *SmFuzzStore = @ptrCast(@alignCast(ctx));
        for (self.entries) |e| {
            if (std.mem.eql(u8, e.name, hash)) return e.view;
        }
        self.misses += 1;
        return null;
    }

    fn seam(self: *SmFuzzStore) artifact.SubResolver {
        return .{ .ctx = self, .resolveFn = SmFuzzStore.resolve };
    }
};

/// Filenames for the walk, ascending under the §4.5.3 comparator. A tree built
/// by handing out disjoint slices of this list in order is legal by
/// construction, which is what makes a deliberate corruption afterwards a
/// controlled experiment rather than a coin flip.
const sm_walk_names = [_][]const u8{
    "a.c", "b.c", "c.c", "d.c", "e.c", "f.c",
    "g.c", "h.c", "i.c", "j.c", "k.c", "l.c",
};

/// A generated tree. Built VALID -- a recursive partition of an ascending name
/// list, each S card keyed on the first name of the slice it covers -- and then
/// corrupted with probability one half.
///
/// Generating garbage directly was measured first and rejected: the completed
/// walk, which is the arm carrying §5.2's completeness assertion and §5.3's
/// lookup agreement, came out at 104 rounds in 20_000 (2 in 512). Almost every
/// draw died on the first S card. Building legal trees and breaking one thing
/// moves that arm to roughly half the rounds while still reaching every fault:
/// a corrupted S hash dangles, self-references or closes a cycle, a corrupted
/// key breaks step 4/5 byte-identity, and a reordered leaf breaks the ascent.
const SmFuzzTree = struct {
    fcards: [sm_max_nodes][sm_walk_names.len]artifact.FCard = undefined,
    scards: [sm_max_nodes][sm_max_cards]artifact.SCard = undefined,
    entries: [sm_max_nodes]SmFuzzStore.Entry = undefined,
    root: [sm_max_cards]artifact.SCard = undefined,
    n_nodes: usize = 0,
    n_root: usize = 0,

    const Pending = struct { node: usize, a: usize, b: usize };

    /// Cut `[a, b)` into at most `want` non-empty ascending parts, writing each
    /// part's start into `starts` and returning the part count. Every part is
    /// non-empty, so the parts are a partition and the slices stay disjoint.
    fn split(rand: std.Random, a: usize, b: usize, want: usize, starts: []usize) usize {
        const n = @min(want, b - a);
        std.debug.assert(n >= 1);
        var pos = a;
        var extra = (b - a) - n;
        for (0..n) |i| {
            starts[i] = pos;
            const take = 1 + if (i + 1 == n) extra else rand.uintLessThan(usize, extra + 1);
            extra -= take - 1;
            pos += take;
        }
        std.debug.assert(pos == b);
        return n;
    }

    fn build(self: *SmFuzzTree, rand: std.Random) void {
        const total = 2 + rand.uintLessThan(usize, sm_walk_names.len - 1);
        var pending: [sm_max_nodes]Pending = undefined;
        var n_pending: usize = 0;
        var used: usize = 0;

        var starts: [sm_max_cards + 1]usize = undefined;
        const n_root = split(rand, 0, total, 1 + rand.uintLessThan(usize, sm_max_cards), &starts);
        starts[n_root] = total;
        self.n_root = n_root;
        for (0..n_root) |i| {
            self.root[i] = .{ .filename = sm_walk_names[starts[i]], .hash = sm_node_names[used] };
            pending[n_pending] = .{ .node = used, .a = starts[i], .b = starts[i + 1] };
            n_pending += 1;
            used += 1;
        }

        // Breadth-first, so a node is always created before it is expanded and
        // the reference always points at an index already allocated.
        var head: usize = 0;
        while (head < n_pending) : (head += 1) {
            const p = pending[head];
            const span = p.b - p.a;
            const room = sm_max_nodes - used;
            // A leaf unless there is room to split and the draw says otherwise.
            if (span < 2 or room < 2 or rand.boolean()) {
                for (p.a..p.b) |i| self.fcards[p.node][i - p.a] = .{
                    .filename = sm_walk_names[i],
                    .hash = "a" ** 64,
                    .perm = null,
                    .old_name = null,
                    .mode = .regular,
                };
                self.entries[p.node] = .{
                    .name = sm_node_names[p.node],
                    .view = .{ .files = self.fcards[p.node][0..span], .subs = &.{} },
                };
                continue;
            }
            var kids: [sm_max_cards + 1]usize = undefined;
            const n_kids = split(rand, p.a, p.b, @min(room, 1 + rand.uintLessThan(usize, sm_max_cards)), &kids);
            kids[n_kids] = p.b;
            for (0..n_kids) |i| {
                self.scards[p.node][i] = .{
                    .filename = sm_walk_names[kids[i]],
                    .hash = sm_node_names[used],
                };
                pending[n_pending] = .{ .node = used, .a = kids[i], .b = kids[i + 1] };
                n_pending += 1;
                used += 1;
            }
            self.entries[p.node] = .{
                .name = sm_node_names[p.node],
                .view = .{ .files = &.{}, .subs = self.scards[p.node][0..n_kids] },
            };
        }
        self.n_nodes = used;

        if (rand.boolean()) self.corrupt(rand);
    }

    /// Break exactly one thing. One corruption per tree, not several, so the
    /// fault the walk reports is attributable.
    fn corrupt(self: *SmFuzzTree, rand: std.Random) void {
        const node = rand.uintLessThan(usize, self.n_nodes);
        const view = self.entries[node].view;
        // The S-run corruptions fall back to the manifest's own run when the
        // drawn node is a leaf: most nodes are, and without the fallback the
        // unresolvable and mismatched-key arms both starve.
        const run: []artifact.SCard = if (view.subs.len != 0)
            self.scards[node][0..view.subs.len]
        else
            self.root[0..self.n_root];
        switch (rand.uintLessThan(u8, 4)) {
            // A dangling, self-referential or back-pointing S hash: §5.2's
            // unresolvable arm, plus cycles and over-deep spines.
            0 => run[rand.uintLessThan(usize, run.len)].hash =
                sm_node_names[rand.uintLessThan(usize, sm_node_names.len)],
            // A key that no longer matches the subtree's first name: §5.1
            // steps 4 and 5.
            1 => run[rand.uintLessThan(usize, run.len)].filename =
                sm_walk_names[rand.uintLessThan(usize, sm_walk_names.len)],
            // A leaf whose F run no longer ascends: §5.1 step 4.
            2 => if (view.files.len >= 2) {
                const i = rand.uintLessThan(usize, view.files.len - 1);
                const tmp = self.fcards[node][i];
                self.fcards[node][i] = self.fcards[node][i + 1];
                self.fcards[node][i + 1] = tmp;
            },
            // A repeated name: strictly-greater, not greater-or-equal.
            else => if (view.files.len >= 2) {
                self.fcards[node][1].filename = self.fcards[node][0].filename;
            },
        }
    }
};

/// §5.1's walk halts on every generated tree, and never reports completion over
/// a tree it could not fully resolve.
///
/// Three properties, in the order they matter. TERMINATION: the walk is driven
/// under a step cap far above anything a legal tree of this size can need, and
/// exceeding it is a hang, which §10's depth bound exists to prevent. ORDER:
/// every emitted filename strictly follows the last (§5.1 steps 3 and 4), so a
/// walk that reorders or repeats a slice fails here rather than silently
/// producing a file set no manifest describes. COMPLETENESS: if the walk
/// terminated normally, no resolution failed -- §5.2's "MUST NOT present a
/// partially resolved tree as a complete file set" as an assertion over the
/// seam, which is the only place the difference is observable.
///
/// Reachability, asserted: a run must reach both a completed walk and a failed
/// one. Measured at seed 1, 20_000 rounds: 13_272 completed, 6_728 failed
/// (FirstFilenameMismatch 3_043, OrderViolation 2_051, SubUnresolvable 1_563,
/// ReferenceCycle 71, DepthExceeded 0); at 512 rounds the thinner of the two
/// floored arms holds 157-182 across seeds 1-3. The per-fault split is
/// recorded, not floored -- only the completed/failed partition is asserted,
/// since that is the one carrying the completeness claim. DepthExceeded is
/// unreachable here: a 17-artifact spine needs more nodes than the table holds,
/// so it is pinned by the deterministic §5.1 step-3 tests instead.
const sm_tree_walk_min_rounds: usize = 512;
const sm_tree_walk_step_cap: usize = 4096;
pub fn submanifestTreeWalk(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
    _ = gpa;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();

    var completed: usize = 0;
    var failed: usize = 0;

    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        var tree: SmFuzzTree = .{};
        tree.build(rand);
        var store = SmFuzzStore{ .entries = tree.entries[0..tree.n_nodes] };
        const subs = tree.root[0..tree.n_root];

        var walk = artifact.TreeWalk.init(subs, store.seam());
        var last: ?[]const u8 = null;
        var emitted: usize = 0;
        var steps: usize = 0;
        const outcome: ?anyerror = while (steps < sm_tree_walk_step_cap) : (steps += 1) {
            const got = walk.next() catch |e| break e;
            const f = got orelse break null;
            // §5.1 step 4: "every emitted decoded filename MUST compare
            // strictly greater than LAST."
            if (last) |prev| {
                try std.testing.expectEqual(
                    std.math.Order.lt,
                    artifact.compareBytes(prev, f.filename),
                );
            }
            last = f.filename;
            emitted += 1;
        } else return error.WalkDidNotTerminate;

        if (outcome) |e| {
            failed += 1;
            // Only the declared §5.1/§5.2 faults, never a stray error.
            switch (e) {
                error.SubUnresolvable,
                error.DepthExceeded,
                error.ReferenceCycle,
                error.FirstFilenameMismatch,
                error.OrderViolation,
                => {},
                else => return e,
            }
            continue;
        }

        completed += 1;
        // §5.2: a completed enumeration means every S reference resolved.
        try std.testing.expectEqual(@as(usize, 0), store.misses);

        // §5.3: single-name lookup answers the same question the walk did.
        // Every emitted name must be found, and a name the tree cannot hold
        // must not be. Lookup runs on a fresh miss count so its own descent
        // cannot borrow the walk's.
        store.misses = 0;
        if (last) |name| {
            const hit = try artifact.lookupTree(subs, name, store.seam());
            try std.testing.expect(hit != null);
            try std.testing.expectEqualStrings(name, hit.?.filename);
        }
        try std.testing.expect((try artifact.lookupTree(subs, "zzz.c", store.seam())) == null);
    }

    if (rounds >= sm_tree_walk_min_rounds and (completed == 0 or failed == 0)) {
        std.debug.print(
            "artifact_submanifest_tree_walk: {d} rounds reached completed={d} failed={d} " ++
                "— an outcome is no longer generated\n",
            .{ rounds, completed, failed },
        );
        return error.OutcomeUnreached;
    }
}