//! 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 repeat = @import("zit").repeat;
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 = @as([2]usize, @splat(0));
var wiki = @as([2]usize, @splat(0));
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 = repeat("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;
}
}