//! Artifact-level DST sweep for the unclassifiable-artifact state-assembly
//! rule (Repository State erratum
//! `repo-state-00-s4-unclassifiable-artifact`).
//!
//! `update.assembleState` reads raw artifacts out of a `LogStore` and derives
//! check-in state. Repository State §4 splits a classification decline from an
//! integrity failure BY THE NAME: bytes that hash to the name they are stored
//! under arrived correctly and are merely opaque to state (skipped); bytes that
//! do NOT are damage and stay fatal (`error.Corrupt`). Verification runs BEFORE
//! the skip, so those two conditions never collapse into one. Two unit tests in
//! `update.zig` sit on the defect site; this sweep pins the same split with a
//! generator that emits artifacts whose card sets fall around the §5.2
//! required-card table, some stored under their true hash and some misnamed,
//! and an INDEPENDENT oracle that predicts the assembly verdict.
//!
//! The oracle carries its own transcription of the §5.2 Table 4 allowed/
//! required card sets and the §5.3 Table 5 latest-wins type rule — never
//! importing `artifact.zig`'s private masks — so a divergence between the two
//! transcriptions is a test failure worth having. This independent-recompute
//! discipline mirrors `src/sim/oracle.zig`, which brute-force recomputes the
//! repostate invariants rather than trusting the production derivation.
//!
//! Generator emission discipline (keeps the oracle §5.4-free): every artifact
//! carries a D card (never dropped) so its first card letter is <= 'M' and it
//! always frames past the §5.5 fast-path; every artifact carries a Z card
//! (never dropped) with a correct §6.2 self-checksum, and the drop mutation
//! never removes Z, so a W card is never the artifact's final card (which would
//! frame as a §4.7.18 syntax error, not a classification decline). T cards are
//! always `+tag <hash>` (add sign, non-self target) and E/T never co-occur, so
//! the §5.4 per-type semantic checks are never reached with a failing input —
//! classification failure is purely §5.2 checkLegality (a disallowed card or a
//! missing required card). Any violation of that reasoning still surfaces: it
//! would make the actual verdict disagree with the oracle, i.e. VerdictMismatch.
//!
//! The same discipline puts SUBMANIFEST out of the random sweep's reach: no
//! base sets the S bit and D is never dropped, so the
//! draft-fossil-submanifests-00 §4.3 reassignment never fires along the
//! generator's paths, and §4.4's three sub-manifest semantic checks are (like
//! §5.4's) deliberately unmodelled. So that the oracle's two `.submanifest`
//! rows are not an untested transcription, the unit-level cross-check at the
//! bottom of this file drives hand-written D-less card sets through both
//! classifiers — one F card apart from one S card, never both, which is the
//! only §4.4 shape the oracle can honestly predict.
const std = @import("std");
const repeat = @import("zit").repeat;
const zit = @import("zit");
const artifact = zit.artifact;
const logstore = zit.logstore;
const update = zit.update;
const faulty_file = @import("faulty_file.zig");
const ArtifactType = artifact.ArtifactType;
/// This sweep's closed error set: it neither joins nor perturbs the repostate
/// `Failure` set. `Io` collapses every storage-layer error the in-memory
/// backend can raise (never expected on a healthy `FaultyFile`).
pub const SweepError = error{
OutOfMemory,
/// The independent oracle and `assembleState` disagreed on the verdict
/// (Corrupt vs. success), or the oracle and the generator disagreed on
/// whether a built artifact is classifiable.
VerdictMismatch,
/// A skipped (unclassifiable, or classifiable-but-non-participating)
/// artifact left a record in the derived state.
SkipContributedState,
/// A seed failed to exercise one of the three verdict paths the sweep
/// exists to cover (verifying skip, misnamed Corrupt, all-verifying
/// success), or the classifiable-misnamed tolerance path.
CoverageGap,
/// The draft-fossil-submanifests-00 §5.1 tree walk disagreed with the
/// generator's own file list, its R card, or its single-name lookup
/// answer; or a deliberately broken tree failed with an error other than
/// the one §5.1 names for that breakage.
WalkMismatch,
/// The §6.2 construction differential failed on the WRITER side: a
/// constructed artifact did not parse or was not a SUBMANIFEST, a
/// sub-manifest was referenced before it appeared in storage order, a flat
/// build carried sub-manifests or an S run, or the walk of a constructed
/// tree did not reproduce the file set or the R card the flat manifest of
/// the same entries carries.
ConstructMismatch,
Io,
};
/// Per-seed step budget. Each step is a fresh in-memory log of at most seven
/// tiny artifacts, so the whole sweep stays in the seconds-scale gate.
const steps_per_seed: usize = 24;
/// Independent, disjoint PRNG stream off the shared seed (fixed odd mix so this
/// sweep neither reads nor perturbs any sibling sweep's stream).
const seed_mix: u64 = 0xA55E_3B1E_C0DE_4711;
// ---------------------------------------------------------------------------
// Card-set algebra
// ---------------------------------------------------------------------------
fn bit(c: u8) u32 {
std.debug.assert(c >= 'A' and c <= 'Z');
return @as(u32, 1) << @intCast(c - 'A');
}
fn maskOf(comptime s: []const u8) u32 {
var m: u32 = 0;
for (s) |c| m |= bit(c);
return m;
}
// ---------------------------------------------------------------------------
// Independent oracle: §5.3 type resolution + §5.2 card legality
// ---------------------------------------------------------------------------
/// §5.3 Table 5 type-setting letters, ascending, and the type each assigns.
/// Folding in ascending order with unconditional overwrite reproduces
/// "the alphabetically latest present type-setting card wins". S joins the
/// MANIFEST-setting letters per draft-fossil-submanifests-00 §4.3.
const setting_letters = "ABEFGHIJKLMQRS";
fn settingType(c: u8) ArtifactType {
return switch (c) {
'A' => .attachment,
'B', 'F', 'Q', 'R', 'S' => .manifest,
'E' => .event,
'G', 'H', 'I' => .forum,
'J', 'K' => .ticket,
'L' => .wiki,
'M' => .cluster,
else => unreachable,
};
}
/// §5.3: the latest-wins type, else the §5.3 p2 fallback, then the
/// submanifests §4.3 reassignment post-pass. This generator emits no C card
/// and no P card, so the fallback is always CONTROL; the C disjunct is
/// transcribed anyway to keep the recompute faithful to the RFC.
fn determineType(mask: u32) ArtifactType {
var result: ?ArtifactType = null;
for (setting_letters) |c| {
if (mask & bit(c) != 0) result = settingType(c);
}
const finalized: ArtifactType = if (result) |r|
r
else if (mask & bit('C') != 0)
.manifest
else
.control;
// submanifests §4.3: a finalized MANIFEST with no D card is SUBMANIFEST.
if (finalized == .manifest and mask & bit('D') == 0) return .submanifest;
return finalized;
}
/// §5.2 Table 4 "Allowed cards" (independent transcription).
fn allowedMask(t: ArtifactType) u32 {
return switch (t) {
.manifest => maskOf("BCDFNPQRSTUZ"), // submanifests §4.2 adds S
.cluster => maskOf("MZ"),
.control => maskOf("DTUZ"),
.wiki => maskOf("CDLNPUWZ"),
.ticket => maskOf("DJKUZ"),
.attachment => maskOf("ACDNUZ"),
.event => maskOf("CDENPTUWZ"),
.forum => maskOf("DGHINPUWZ"),
.submanifest => maskOf("FSZ"), // submanifests §4.2 Table 1
};
}
/// §5.2 Table 4 "Required cards" (independent transcription).
fn requiredMask(t: ArtifactType) u32 {
return switch (t) {
.manifest => maskOf("DZ"),
.cluster => maskOf("MZ"),
.control => maskOf("DTUZ"),
.wiki => maskOf("DLUWZ"),
.ticket => maskOf("DJKUZ"),
.attachment => maskOf("ADZ"),
.event => maskOf("DEWZ"),
.forum => maskOf("DUWZ"),
.submanifest => maskOf("Z"),
};
}
const Class = struct { classifiable: bool, kind: ArtifactType };
/// §5.3 → §5.2 classify, independent of `artifact.classify`. §5.4 semantics are
/// intentionally not modeled: the generator's emission discipline keeps them a
/// no-op on every artifact it builds (see the file header), and any lapse
/// surfaces as a verdict disagreement rather than a silent pass.
fn classify(mask: u32) Class {
const t = determineType(mask);
if (mask & ~allowedMask(t) != 0) return .{ .classifiable = false, .kind = t }; // §5.2-r1
if (mask & requiredMask(t) != requiredMask(t)) return .{ .classifiable = false, .kind = t }; // §5.2-r2
return .{ .classifiable = true, .kind = t };
}
/// Does a misnamed artifact of this class turn assembly fatal? Repository State
/// §4: an unclassifiable artifact is verified before the skip, so a misnamed
/// one is Corrupt; a classified MANIFEST/CONTROL is verified before it
/// contributes, so a misnamed one is Corrupt; every other classified kind is
/// skipped WITHOUT verification, so a misnamed one is tolerated.
fn corruptWhenMisnamed(c: Class) bool {
if (!c.classifiable) return true;
return c.kind == .manifest or c.kind == .control;
}
// ---------------------------------------------------------------------------
// Generator: base card sets and the mutations around the §5.2 table
// ---------------------------------------------------------------------------
const Base = struct {
mask: u32,
/// Required letters, excluding D and Z, that the drop mutation may remove
/// (dropping either would either lose the framing floor or leave a W card
/// last — both syntax faults, not classification declines).
droppable: []const u8,
/// A non-type-setting letter outside this type's allowed set, so adding it
/// yields a §5.2-r1 DisallowedCard without changing the resolved type.
/// Null for EVENT, whose allowed set already contains every non-type-
/// setting letter this vocabulary uses.
disallowed: ?u8,
};
const bases = [_]Base{
.{ .mask = maskOf("DFZ"), .droppable = "F", .disallowed = 'W' }, // 0 manifest
.{ .mask = maskOf("DTUZ"), .droppable = "TU", .disallowed = 'W' }, // 1 control
.{ .mask = maskOf("DLUWZ"), .droppable = "LUW", .disallowed = 'T' }, // 2 wiki
.{ .mask = maskOf("DJKUZ"), .droppable = "JKU", .disallowed = 'W' }, // 3 ticket
.{ .mask = maskOf("DAZ"), .droppable = "A", .disallowed = 'W' }, // 4 attachment
.{ .mask = maskOf("DEWZ"), .droppable = "EW", .disallowed = null }, // 5 event
.{ .mask = maskOf("DGUWZ"), .droppable = "GUW", .disallowed = 'T' }, // 6 forum
};
/// Bases whose clean card set classifies as a NON-manifest, NON-control kind,
/// so a clean instance is skipped (never crosslinked) yet is genuinely
/// classifiable — the shape that pins the misnamed-but-tolerated contract.
const clean_base_idx = [_]usize{ 2, 3, 4, 5, 6 };
/// Bases that carry a usable disallowed-card mutation (every base but EVENT).
const disallowed_base_idx = [_]usize{ 0, 1, 2, 3, 4, 6 };
const Profile = enum { clean, drop, disallowed };
/// One planned artifact: its card-set mask and how it is stored.
const Plan = struct {
mask: u32,
misnamed: bool,
};
/// Build the mask for a profile, drawing a base and (for the mutations) a
/// specific card to remove or add.
fn planMask(random: std.Random, profile: Profile) u32 {
switch (profile) {
.clean => {
const b = bases[clean_base_idx[random.uintLessThan(usize, clean_base_idx.len)]];
return b.mask;
},
.drop => {
const b = bases[random.uintLessThan(usize, bases.len)];
const letter = b.droppable[random.uintLessThan(usize, b.droppable.len)];
return b.mask & ~bit(letter);
},
.disallowed => {
const b = bases[disallowed_base_idx[random.uintLessThan(usize, disallowed_base_idx.len)]];
return b.mask | bit(b.disallowed.?);
},
}
}
// ---------------------------------------------------------------------------
// Artifact byte emission (syntactically valid §4.7 cards, ascending order)
// ---------------------------------------------------------------------------
const filler_hash = repeat("a", 40); // a valid lowercase-hex SHA-1 token
/// Emit the artifact's bytes for `mask`, salting the D/E timestamp with `salt`
/// (0..59) so distinct artifacts within one step get distinct bytes and hence
/// distinct names. Every present letter is emitted once, in ascending order,
/// with a payload its §4.7 parser accepts; the Z card is sealed last with a
/// correct §6.2 self-checksum.
fn emit(gpa: std.mem.Allocator, mask: u32, salt: u32) SweepError![]u8 {
std.debug.assert(salt < 60);
var ts_buf: [19]u8 = undefined;
const ts = std.fmt.bufPrint(&ts_buf, "2007-07-21T14:00:{d:0>2}", .{salt}) catch unreachable;
var body: std.ArrayList(u8) = .empty;
defer body.deinit(gpa);
const w = &body;
if (mask & bit('A') != 0) try append(gpa, w, "A afile " ++ filler_hash ++ "\n");
if (mask & bit('D') != 0) {
try append(gpa, w, "D ");
try append(gpa, w, ts);
try append(gpa, w, "\n");
}
if (mask & bit('E') != 0) {
try append(gpa, w, "E ");
try append(gpa, w, ts);
try append(gpa, w, " " ++ filler_hash ++ "\n");
}
if (mask & bit('F') != 0) try append(gpa, w, "F afile " ++ filler_hash ++ "\n");
if (mask & bit('G') != 0) try append(gpa, w, "G " ++ filler_hash ++ "\n");
if (mask & bit('J') != 0) try append(gpa, w, "J status open\n");
if (mask & bit('K') != 0) try append(gpa, w, "K " ++ filler_hash ++ "\n");
if (mask & bit('L') != 0) try append(gpa, w, "L RockShoxBugs\n");
if (mask & bit('S') != 0) try append(gpa, w, "S afile " ++ filler_hash ++ "\n");
if (mask & bit('T') != 0) try append(gpa, w, "T +sym-tag " ++ filler_hash ++ "\n");
if (mask & bit('U') != 0) try append(gpa, w, "U alice\n");
if (mask & bit('W') != 0) try append(gpa, w, "W 5\nhello\n");
if (mask & bit('Z') != 0) {
var sum_buf: [32]u8 = undefined;
const sum = artifact.selfChecksum(body.items, &sum_buf);
try append(gpa, w, "Z ");
try append(gpa, w, sum);
try append(gpa, w, "\n");
}
return body.toOwnedSlice(gpa) catch return error.OutOfMemory;
}
fn append(gpa: std.mem.Allocator, w: *std.ArrayList(u8), s: []const u8) SweepError!void {
w.appendSlice(gpa, s) catch return error.OutOfMemory;
}
/// Store `bytes` under a chosen raw SHA-1 name and return that name's 40-hex
/// form. `misnamed` stores it under a hash of an unrelated preimage, so
/// `artifact.verify` fails; otherwise it stores under the true content hash.
fn store(log: *logstore.LogStore, bytes: []const u8, misnamed: bool, out_hex: *[40]u8) SweepError!void {
var raw: [20]u8 = undefined;
if (misnamed) {
var h = std.crypto.hash.Sha1.init(.{});
h.update("assembly-sweep-misname\x00");
h.update(bytes);
h.final(&raw);
} else {
std.crypto.hash.Sha1.hash(bytes, &raw, .{});
}
out_hex.* = std.fmt.bytesToHex(raw, .lower);
_ = log.put(&raw, bytes) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Storage => error.Io,
};
}
// ---------------------------------------------------------------------------
// Sweep
// ---------------------------------------------------------------------------
const Counters = struct {
verifying_skip: usize = 0,
misnamed_corrupt: usize = 0,
classifiable_misnamed_ok: usize = 0,
success: usize = 0,
};
/// One artifact as it was actually stored, with the oracle's verdict about it.
const Stored = struct {
hex: [40]u8,
class: Class,
misnamed: bool,
};
pub fn run(gpa: std.mem.Allocator, seed: u64) SweepError!void {
var prng = std.Random.DefaultPrng.init(seed +% seed_mix);
const random = prng.random();
var counters: Counters = .{};
var step: usize = 0;
while (step < steps_per_seed) : (step += 1) {
try runStep(gpa, random, step, &counters);
}
// Every seed must have exercised each verdict path at least once; the first
// three steps force them deterministically, so this only ever fires if the
// step schedule below is broken.
if (counters.verifying_skip == 0 or
counters.misnamed_corrupt == 0 or
counters.classifiable_misnamed_ok == 0 or
counters.success == 0) return error.CoverageGap;
try runWalk(gpa, seed);
try runConstruct(gpa, seed);
}
fn runStep(gpa: std.mem.Allocator, random: std.Random, step: usize, counters: *Counters) SweepError!void {
var faulty = faulty_file.FaultyFile.init(gpa, random);
defer faulty.deinit();
var log = logstore.LogStore.open(gpa, faulty.storageFile(), 0) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
else => error.Io,
};
defer log.deinit(gpa);
// The always-clean, always-true-named target manifest. It carries a
// distinguishing F payload the generated manifests never use, so it cannot
// alias one of them; generated artifacts take salts 1.. so their bytes stay
// distinct from each other.
var target_hex: [40]u8 = undefined;
{
var body: std.ArrayList(u8) = .empty;
defer body.deinit(gpa);
try append(gpa, &body, "D 2007-07-21T14:00:00\nF zit-dst-target " ++ filler_hash ++ "\n");
var sum_buf: [32]u8 = undefined;
const sum = artifact.selfChecksum(body.items, &sum_buf);
try append(gpa, &body, "Z ");
try append(gpa, &body, sum);
try append(gpa, &body, "\n");
try store(&log, body.items, false, &target_hex);
}
var plans: std.ArrayList(Plan) = .empty;
defer plans.deinit(gpa);
try planStep(gpa, random, step, &plans);
var stored: std.ArrayList(Stored) = .empty;
defer stored.deinit(gpa);
var expect_corrupt = false;
var salt: u32 = 1;
for (plans.items) |p| {
const class = classify(p.mask);
const bytes = try emit(gpa, p.mask, salt);
defer gpa.free(bytes);
salt += 1;
var hex: [40]u8 = undefined;
try store(&log, bytes, p.misnamed, &hex);
stored.append(gpa, .{ .hex = hex, .class = class, .misnamed = p.misnamed }) catch return error.OutOfMemory;
if (p.misnamed and corruptWhenMisnamed(class)) expect_corrupt = true;
}
if (update.assembleState(gpa, &log, &target_hex)) |assembly_const| {
var assembly = assembly_const;
defer assembly.deinit();
if (expect_corrupt) return error.VerdictMismatch;
counters.success += 1;
// No skipped artifact — unclassifiable, or classifiable-but-non-
// participating — may leave a record in the derived state. Only the
// target manifest is ever crosslinked.
for (stored.items) |s| {
if (assembly.state.store.lookup(&s.hex) != null) return error.SkipContributedState;
if (!s.class.classifiable and !s.misnamed) counters.verifying_skip += 1;
if (s.class.classifiable and
s.class.kind != .manifest and
s.class.kind != .control and
s.misnamed) counters.classifiable_misnamed_ok += 1;
}
} else |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => {
if (!expect_corrupt) return error.VerdictMismatch;
counters.misnamed_corrupt += 1;
},
// Any other error means assembly declined a store the oracle judged
// sound (or accepted one it judged Corrupt): a genuine mismatch.
else => return error.VerdictMismatch,
}
}
/// The step's artifact plan. Steps 0-2 are forced to guarantee each verdict
/// path is covered every seed; later steps are a random mix of 1..6 artifacts.
fn planStep(gpa: std.mem.Allocator, random: std.Random, step: usize, plans: *std.ArrayList(Plan)) SweepError!void {
switch (step) {
// Verifying skip: one unclassifiable artifact stored under its true
// hash → tolerated, assembly succeeds.
0 => try plans.append(gpa, .{ .mask = planMask(random, .drop), .misnamed = false }),
// Misnamed Corrupt: one unclassifiable artifact stored under a wrong
// name → integrity failure, assembly is fatal.
1 => try plans.append(gpa, .{ .mask = planMask(random, .drop), .misnamed = true }),
// Classifiable-misnamed tolerance: one clean non-manifest artifact
// under a wrong name → skipped without verification, still succeeds.
2 => try plans.append(gpa, .{ .mask = planMask(random, .clean), .misnamed = true }),
else => {
const k = 1 + random.uintLessThan(usize, 6);
var i: usize = 0;
while (i < k) : (i += 1) {
const profile: Profile = switch (random.uintLessThan(u8, 3)) {
0 => .clean,
1 => .drop,
else => .disallowed,
};
try plans.append(gpa, .{
.mask = planMask(random, profile),
.misnamed = random.boolean(),
});
}
},
}
}
// ---------------------------------------------------------------------------
// draft-fossil-submanifests-00 §5 tree-walk sweep
// ---------------------------------------------------------------------------
//
// A second, independent lane over the same seed. The generator draws a random
// sorted file-name set and partitions it into leaves and interior nodes at a
// random, deliberately NON-canonical shape — §6 lets a reader accept any
// partition ("a reader ... MUST NOT reject an artifact because its partition
// differs from the canonical construction"), and the writer-side construction
// of §6.2 is a later slice, so the sweep must not assume it.
//
// The oracle is the generated name list itself, independent by construction:
// the generator never consults the walk, and the manifest's R card is built
// here from the §6.3.2 input string with a direct MD5 rather than through
// `artifact.aggregateChecksum`, so a wrong walk cannot agree with a wrong
// aggregate.
//
// Sub-manifests are real artifacts named by their genuine SHA3-256, resolved
// through an in-memory table keyed by those names. Mutations act on the table
// and on copies of an S run, not on artifact bytes, because several of the
// shapes §5.1 must reject — a swapped sibling pair, a 17-artifact spine, a
// reference cycle — cannot be reached through `parse` at all: §3.4 rejects a
// descending S run, and content addressing forbids a cycle among honestly
// named artifacts. That is exactly why the walk owns those checks.
/// Per-seed tree-walk steps. Each builds one tree of at most a few dozen tiny
/// artifacts, so the lane stays inside the seconds-scale gate.
const walk_steps_per_seed: usize = 16;
/// Independent, disjoint PRNG stream off the shared seed.
const walk_seed_mix: u64 = 0x51D2_7A44_9E13_0BB7;
/// Names are drawn as `pNNN.c` with three fixed digits, so lexical order and
/// numeric order coincide and the generated list is sorted under the §4.5.3
/// canonical comparator by construction.
const name_space: usize = 1000;
/// The largest generated file set, and the widest random group.
const max_files: usize = 40;
const max_group: usize = 5;
/// The most interior levels the valid lane builds: depth stays far inside
/// §5.1's bound of 16, which the dedicated spine lane probes instead.
const max_levels: usize = 3;
/// One generated sub-manifest: its key (§6.2, "the decoded filename of the
/// first file entry in its subtree"), its genuine artifact name, its bytes,
/// and the parse of those bytes the walk reads through.
const TreeNode = struct {
key: []const u8,
name: []const u8,
bytes: []const u8,
manifest: artifact.Manifest,
};
/// One resolvable artifact in the walk's store. `present` and `submanifest`
/// model §5.2's two hard failures separately so a mutation can pick either.
const ViewEntry = struct {
name: []const u8,
view: artifact.SubManifestView,
present: bool = true,
submanifest: bool = true,
/// Per-artifact read count: the swap lane below asserts that an
/// out-of-order key costs no read at all, which is the only observable
/// difference between §5.1's step-3 ordering check and the step-4 check
/// that would otherwise reject the same tree one artifact later.
reads: usize = 0,
};
/// §5.2 resolver over the generated table, counting reads so §5.3's "at most
/// 16 per lookup" is measured.
const ViewStore = struct {
entries: []ViewEntry,
reads: usize = 0,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
const self: *ViewStore = @ptrCast(@alignCast(ctx));
for (self.entries) |*e| {
if (!std.mem.eql(u8, e.name, hash)) continue;
if (!e.present or !e.submanifest) return null; // §5.2 collapse
self.reads += 1;
e.reads += 1;
return e.view;
}
return null;
}
fn seam(self: *ViewStore) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = ViewStore.resolve };
}
};
/// A generated tree, arena-owned end to end.
const Tree = struct {
arena: std.heap.ArenaAllocator,
gpa: std.mem.Allocator,
names: [][]const u8,
contents: [][]const u8,
nodes: []TreeNode,
/// The manifest's own S run, as (key, node index) pairs in key order.
top: []usize,
manifest_bytes: []const u8,
manifest: artifact.Manifest,
fn deinit(self: *Tree) void {
self.manifest.deinit();
for (self.nodes) |*n| n.manifest.deinit();
self.arena.deinit();
}
/// The resolver table over every generated sub-manifest.
fn entries(self: *Tree, out: []ViewEntry) []ViewEntry {
std.debug.assert(out.len >= self.nodes.len);
for (self.nodes, 0..) |*n, i| {
out[i] = .{
.name = n.name,
.view = .{ .files = n.manifest.f, .subs = n.manifest.s },
};
}
return out[0..self.nodes.len];
}
};
fn oom(_: anytype) SweepError {
return error.OutOfMemory;
}
/// Append `s` to `w`, mapping the allocator's error into the sweep's set.
fn wappend(a: std.mem.Allocator, w: *std.ArrayList(u8), s: []const u8) SweepError!void {
w.appendSlice(a, s) catch return error.OutOfMemory;
}
/// Seal a card body into an artifact: body plus the §6.2 Z self-checksum.
fn sealArtifact(a: std.mem.Allocator, body: []const u8) SweepError![]const u8 {
var out: std.ArrayList(u8) = .empty;
try wappend(a, &out, body);
var sum_buf: [32]u8 = undefined;
const sum = artifact.selfChecksum(body, &sum_buf);
try wappend(a, &out, "Z ");
try wappend(a, &out, sum);
try wappend(a, &out, "\n");
return out.toOwnedSlice(a) catch return error.OutOfMemory;
}
/// The 64-hex SHA3-256 artifact name of `bytes`, arena-owned.
fn sha3Name(a: std.mem.Allocator, bytes: []const u8) SweepError![]const u8 {
const out = a.alloc(u8, 64) catch return error.OutOfMemory;
_ = artifact.artifactName(.sha3_256, bytes, out[0..64]);
return out;
}
/// Build one random tree. `random` is consumed for the name count, the name
/// draw, and every group boundary; nothing about the walk influences it.
fn genTree(gpa: std.mem.Allocator, random: std.Random) SweepError!Tree {
var self = Tree{
.arena = std.heap.ArenaAllocator.init(gpa),
.gpa = gpa,
.names = &.{},
.contents = &.{},
.nodes = &.{},
.top = &.{},
.manifest_bytes = &.{},
.manifest = undefined,
};
errdefer self.arena.deinit();
const a = self.arena.allocator();
// 1. A sorted, distinct name set (`drawNames`, shared with the §6.2
// construct lane so both sweep the same name universe).
const drawn = try drawNames(a, random, 1 + random.uintLessThan(usize, max_files));
self.names = drawn.names;
self.contents = drawn.contents;
// 2. Leaves: a random contiguous partition of the file list.
var nodes: std.ArrayList(TreeNode) = .empty;
var level: std.ArrayList(usize) = .empty;
var i: usize = 0;
while (i < self.names.len) {
const n = @min(1 + random.uintLessThan(usize, max_group), self.names.len - i);
var body: std.ArrayList(u8) = .empty;
for (self.names[i .. i + n], self.contents[i .. i + n]) |nm, ct| {
try wappend(a, &body, "F ");
try wappend(a, &body, nm);
try wappend(a, &body, " ");
try wappend(a, &body, try sha3Name(a, ct));
try wappend(a, &body, "\n");
}
level.append(a, nodes.items.len) catch return error.OutOfMemory;
nodes.append(a, try makeNode(gpa, a, self.names[i], body.items)) catch return error.OutOfMemory;
i += n;
}
// 3. Interior levels, each a random partition of the level below. A group
// of one member is a single-child node -- non-canonical (§6.2 step 3
// stops on a non-reducing scan) but legal for a reader, which is the
// point of generating it.
var levels: usize = 0;
const want_levels = random.uintLessThan(usize, max_levels + 1);
while (levels < want_levels and level.items.len > 1) : (levels += 1) {
var next: std.ArrayList(usize) = .empty;
var j: usize = 0;
while (j < level.items.len) {
const n = @min(1 + random.uintLessThan(usize, max_group), level.items.len - j);
var body: std.ArrayList(u8) = .empty;
for (level.items[j .. j + n]) |child| {
try wappend(a, &body, "S ");
try wappend(a, &body, nodes.items[child].key);
try wappend(a, &body, " ");
try wappend(a, &body, nodes.items[child].name);
try wappend(a, &body, "\n");
}
const key = nodes.items[level.items[j]].key;
next.append(a, nodes.items.len) catch return error.OutOfMemory;
nodes.append(a, try makeNode(gpa, a, key, body.items)) catch return error.OutOfMemory;
j += n;
}
level = next;
}
self.nodes = nodes.items;
self.top = level.items;
// 4. The manifest. Its R card is built here from the §6.3.2 input string
// with a direct MD5 -- never through `aggregateChecksum`, which the
// sweep is checking.
var r_input: std.ArrayList(u8) = .empty;
for (self.names, self.contents) |nm, ct| {
const line = std.fmt.allocPrint(a, "{s} {d}\n", .{ nm, ct.len }) catch return error.OutOfMemory;
try wappend(a, &r_input, line);
try wappend(a, &r_input, ct);
}
var md5: [16]u8 = undefined;
std.crypto.hash.Md5.hash(r_input.items, &md5, .{});
const r_hex = std.fmt.bytesToHex(md5, .lower);
var mbody: std.ArrayList(u8) = .empty;
try wappend(a, &mbody, "C tree\\ssweep\nD 2026-01-01T00:00:00\nR ");
try wappend(a, &mbody, &r_hex);
try wappend(a, &mbody, "\n");
for (self.top) |idx| {
try wappend(a, &mbody, "S ");
try wappend(a, &mbody, nodes.items[idx].key);
try wappend(a, &mbody, " ");
try wappend(a, &mbody, nodes.items[idx].name);
try wappend(a, &mbody, "\n");
}
try wappend(a, &mbody, "U dst\n");
self.manifest_bytes = try sealArtifact(a, mbody.items);
self.manifest = artifact.parse(gpa, self.manifest_bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.WalkMismatch, // the generator must emit valid artifacts
};
if (self.manifest.kind != .manifest or self.manifest.s.len != self.top.len) {
self.manifest.deinit();
return error.WalkMismatch;
}
return self;
}
/// Seal one node's card body, name it, and parse it -- a generated node that
/// does not parse as a SUBMANIFEST is a generator bug, reported as such.
///
/// The bytes live on the tree's arena, but the parse takes `gpa`: a `Tree` is
/// returned by value, so an arena nested inside it would hold a pointer to the
/// pre-move frame and free through it at `deinit`.
fn makeNode(gpa: std.mem.Allocator, a: std.mem.Allocator, key: []const u8, body: []const u8) SweepError!TreeNode {
const bytes = try sealArtifact(a, body);
const name = try sha3Name(a, bytes);
const m = artifact.parse(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.WalkMismatch,
};
if (m.kind != .submanifest) return error.WalkMismatch;
return .{ .key = key, .name = name, .bytes = bytes, .manifest = m };
}
/// The tree-walk lane: one valid tree per step, then one randomly chosen
/// breakage that §5.1 names an error for.
fn runWalk(gpa: std.mem.Allocator, seed: u64) SweepError!void {
var prng = std.Random.DefaultPrng.init(seed +% walk_seed_mix);
const random = prng.random();
var step: usize = 0;
while (step < walk_steps_per_seed) : (step += 1) {
var tree = try genTree(gpa, random);
defer tree.deinit();
try walkValid(gpa, &tree);
try walkLookup(&tree, random);
try walkBroken(gpa, &tree, random);
}
// The two shapes no honestly named artifact set can express: a spine past
// the depth bound, and a reference cycle.
try walkSpine(random);
try walkCycle(random);
}
/// The valid lane: `flattenTree` must reproduce the generator's name list
/// exactly, and `aggregateChecksum` over that enumeration must reproduce the
/// R card the generator computed independently (§5.5).
fn walkValid(gpa: std.mem.Allocator, tree: *Tree) SweepError!void {
var buf: [512]ViewEntry = undefined;
var vs = ViewStore{ .entries = tree.entries(&buf) };
var m = artifact.parse(gpa, tree.manifest_bytes) catch return error.WalkMismatch;
defer m.deinit();
m.flattenTree(vs.seam()) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.WalkMismatch, // a valid tree must walk
};
const flat = m.flattened orelse return error.WalkMismatch;
if (flat.len != tree.names.len) return error.WalkMismatch;
for (flat, tree.names) |f, want| {
if (!std.mem.eql(u8, f.filename, want)) return error.WalkMismatch;
if (f.hash == null) return error.WalkMismatch; // §4.4
}
var tracked: std.ArrayList(artifact.TrackedFile) = .empty;
defer tracked.deinit(gpa);
for (flat, tree.contents) |f, ct| {
tracked.append(gpa, .{ .name = f.filename, .content = ct }) catch return error.OutOfMemory;
}
var digest: [32]u8 = undefined;
const got = artifact.aggregateChecksum(tracked.items, &digest);
if (!std.mem.eql(u8, got, m.r.?.checksum)) return error.WalkMismatch;
}
/// §5.3: every generated name must be found, an absent one must not be, and
/// no lookup may read more than `max_tree_depth` sub-manifests.
fn walkLookup(tree: *Tree, random: std.Random) SweepError!void {
var buf: [512]ViewEntry = undefined;
for (tree.names) |want| {
var vs = ViewStore{ .entries = tree.entries(&buf) };
const got = (artifact.lookupTree(tree.manifest.s, want, vs.seam()) catch
return error.WalkMismatch) orelse return error.WalkMismatch;
if (!std.mem.eql(u8, got.filename, want)) return error.WalkMismatch;
if (vs.reads > artifact.max_tree_depth) return error.WalkMismatch;
}
// An absent probe: `zNNN.c` sorts above every generated name, and `a` below
// every one, so both non-membership shapes §5.3 distinguishes are covered.
var probe: [8]u8 = undefined;
const absent = std.fmt.bufPrint(&probe, "z{d:0>3}.c", .{random.uintLessThan(usize, name_space)}) catch
return error.WalkMismatch;
for ([_][]const u8{ absent, "a" }) |name| {
var vs = ViewStore{ .entries = tree.entries(&buf) };
const got = artifact.lookupTree(tree.manifest.s, name, vs.seam()) catch
return error.WalkMismatch;
if (got != null) return error.WalkMismatch;
if (vs.reads > artifact.max_tree_depth) return error.WalkMismatch;
}
}
/// One randomly chosen breakage of the generated tree, each with the error
/// §5.1 names for it. Every case drives `TreeWalk` directly, because a mutated
/// S run is not something `parse` would ever hand back.
fn walkBroken(gpa: std.mem.Allocator, tree: *Tree, random: std.Random) SweepError!void {
var buf: [512]ViewEntry = undefined;
var entries = tree.entries(&buf);
// A mutable copy of the manifest's own S run, so the swap case can reorder
// it without touching the parsed manifest.
var subs = gpa.alloc(artifact.SCard, tree.manifest.s.len) catch return error.OutOfMemory;
defer gpa.free(subs);
@memcpy(subs, tree.manifest.s);
// Set by the swap case: the artifact the walk must reject without ever
// resolving it (§5.1 step 3 before §5.2's read, per §10).
var unread: ?[]const u8 = null;
const want: anyerror = switch (random.uintLessThan(u8, 4)) {
// §5.2: the referenced artifact is absent.
0 => blk: {
entries[random.uintLessThan(usize, entries.len)].present = false;
break :blk error.SubUnresolvable;
},
// §5.2 / §3.6: present, but not of type SUBMANIFEST.
1 => blk: {
entries[random.uintLessThan(usize, entries.len)].submanifest = false;
break :blk error.SubUnresolvable;
},
// §5.1 step 4: a leaf whose first emitted filename is no longer
// byte-identical to its key.
2 => blk: {
var found = false;
for (entries) |*e| {
if (e.view.subs.len != 0 or e.view.files.len < 2) continue;
e.view.files = e.view.files[1..];
found = true;
break;
}
if (!found) return; // every leaf holds one file: nothing to behead
break :blk error.FirstFilenameMismatch;
},
// §5.1 step 3: an enumeration that no longer strictly ascends across
// sibling slices. Swapping an adjacent pair of the manifest's own S
// run leaves each subtree intact and each key still matching its
// node, so the only rule left to break is the LAST ordering.
else => blk: {
if (subs.len < 2) return; // a single-slice tree has no siblings
const at = random.uintLessThan(usize, subs.len - 1);
std.mem.swap(artifact.SCard, &subs[at], &subs[at + 1]);
unread = subs[at + 1].hash; // the demoted key: must never be read
break :blk error.OrderViolation;
},
};
var vs = ViewStore{ .entries = entries };
var walk = artifact.TreeWalk.init(subs, vs.seam());
while (true) {
const next = walk.next() catch |e| {
if (e != want) return error.WalkMismatch;
if (unread) |h| {
for (entries) |entry| {
if (std.mem.eql(u8, entry.name, h) and entry.reads != 0) return error.WalkMismatch;
}
}
return;
};
if (next == null) return error.WalkMismatch; // the walk had to fail
}
}
/// §5.1 step 3's depth bound, on a single-key spine of random length: legal
/// at or below `max_tree_depth` sub-manifests (counting the leaf, §2), and
/// `DepthExceeded` above it.
fn walkSpine(random: std.Random) SweepError!void {
const depth = artifact.max_tree_depth - 3 + random.uintLessThan(usize, 8);
var names: [32][4]u8 = undefined;
var runs: [32][1]artifact.SCard = undefined;
var entries: [32]ViewEntry = undefined;
const files = [_]artifact.FCard{
.{ .filename = "k", .hash = repeat("a", 64), .perm = null, .old_name = null, .mode = .regular },
};
for (0..depth) |i| {
names[i] = .{ 's', '0' + @as(u8, @intCast(i / 100)), '0' + @as(u8, @intCast((i / 10) % 10)), '0' + @as(u8, @intCast(i % 10)) };
}
for (0..depth - 1) |i| {
runs[i] = .{.{ .filename = "k", .hash = &names[i + 1] }};
entries[i] = .{ .name = &names[i], .view = .{ .files = &.{}, .subs = &runs[i] } };
}
entries[depth - 1] = .{ .name = &names[depth - 1], .view = .{ .files = &files, .subs = &.{} } };
var vs = ViewStore{ .entries = entries[0..depth] };
const root = [_]artifact.SCard{.{ .filename = "k", .hash = &names[0] }};
var walk = artifact.TreeWalk.init(&root, vs.seam());
if (walk.next()) |got| {
if (depth > artifact.max_tree_depth) return error.WalkMismatch;
if (got == null or !std.mem.eql(u8, got.?.filename, "k")) return error.WalkMismatch;
} else |e| {
if (depth <= artifact.max_tree_depth) return error.WalkMismatch;
if (e != error.DepthExceeded) return error.WalkMismatch;
}
}
/// §5.1 step 3's repeated-artifact check, on a chain of random length whose
/// last node points back at one already on the stack.
fn walkCycle(random: std.Random) SweepError!void {
const len = 2 + random.uintLessThan(usize, 4);
var names: [8][4]u8 = undefined;
var runs: [8][1]artifact.SCard = undefined;
var entries: [8]ViewEntry = undefined;
for (0..len) |i| {
names[i] = .{ 'c', '0', '0', '0' + @as(u8, @intCast(i)) };
}
const back = random.uintLessThan(usize, len); // any node already on the stack
for (0..len) |i| {
const target = if (i + 1 < len) i + 1 else back;
runs[i] = .{.{ .filename = "k", .hash = &names[target] }};
entries[i] = .{ .name = &names[i], .view = .{ .files = &.{}, .subs = &runs[i] } };
}
var vs = ViewStore{ .entries = entries[0..len] };
const root = [_]artifact.SCard{.{ .filename = "k", .hash = &names[0] }};
var walk = artifact.TreeWalk.init(&root, vs.seam());
if (walk.next()) |_| {
return error.WalkMismatch; // a cycle can never enumerate
} else |e| {
if (e != error.ReferenceCycle) return error.WalkMismatch;
}
}
// ---------------------------------------------------------------------------
// Tests — run a handful of seeds under `zig build test` (the sweep also joins
// the per-seed `zig build dst` gate via dst.zig).
// ---------------------------------------------------------------------------
test "assembly_sweep pins the unclassifiable-artifact verify-then-skip split" {
var seed: u64 = 1;
while (seed <= 8) : (seed += 1) {
try run(std.testing.allocator, seed);
}
}
test "assembly_sweep oracle agrees with the reference classifier on the vocabulary" {
// Cross-check the independent transcription against `artifact.classify`
// over the exact card sets the generator builds, so a table typo cannot
// hide behind a verdict that happens to match. This is a unit-level guard;
// the sweep's load-bearing check is oracle-vs-assembleState above.
const gpa = std.testing.allocator;
for (bases, 0..) |b, bi| {
var masks: [16]u32 = undefined;
var n: usize = 0;
masks[n] = b.mask;
n += 1;
for (b.droppable) |letter| {
masks[n] = b.mask & ~bit(letter);
n += 1;
}
if (b.disallowed) |letter| {
masks[n] = b.mask | bit(letter);
n += 1;
}
for (masks[0..n]) |mask| try expectOracleAgrees(gpa, mask, bi);
}
}
test "assembly_sweep oracle agrees with the reference classifier on D-less card sets" {
// The random sweep never reaches SUBMANIFEST (see the file header), which
// would leave the oracle's two draft-fossil-submanifests-00 rows an
// untested transcription. Cross-check them here instead: dropping D from a
// card set the emitter can still frame (first letter <= 'M') is exactly the
// §4.3 reassignment trigger.
//
// F and S are probed apart, never together: §4.4 rejects a SUBMANIFEST
// carrying both, and that per-type semantic check is as deliberately
// unmodelled here as §5.4's are, so an F+S mask would diverge by design.
const gpa = std.testing.allocator;
const masks = [_]u32{
maskOf("FZ"), // SUBMANIFEST, legal
maskOf("SZ"), // SUBMANIFEST, legal -- pins S in the allowed row
maskOf("SZ") | bit('T'), // §4.2-r1: T is outside F S Z
maskOf("S"), // §4.2-r2: Z is required
};
for (masks) |mask| try expectOracleAgrees(gpa, mask, null);
}
/// One card set through both classifiers: the oracle's transcription and
/// `artifact.parseForImport`. `base` names the generator base a mask came from,
/// for the diagnostic; null when the mask was written out by hand.
fn expectOracleAgrees(gpa: std.mem.Allocator, mask: u32, base: ?usize) !void {
const bytes = try emit(gpa, mask, 1);
defer gpa.free(bytes);
const want: Class = classify(mask);
if (artifact.parseForImport(gpa, bytes)) |m_const| {
var m = m_const;
defer m.deinit(gpa);
try std.testing.expect(want.classifiable);
try std.testing.expectEqual(want.kind, m.manifest.kind);
} else |err| switch (err) {
error.OutOfMemory => return err,
error.SyntaxError => {
std.debug.print("base {?d} mask {x} framed as SyntaxError\n", .{ base, mask });
return error.TestUnexpectedResult;
},
else => try std.testing.expect(!want.classifiable),
}
}
// ---------------------------------------------------------------------------
// draft-fossil-submanifests-00 §6 -- the flat-vs-tree construction differential
// ---------------------------------------------------------------------------
//
// The walk lane above proves a reader agrees with a GENERATED tree. This lane
// closes the loop on the writer: §6.2 builds the tree, §5.1 walks it back, and
// the enumeration must be the flat file list the construction started from --
// "the same list a flat manifest would carry" (§A.3) -- with the §5.5 R card
// over the walked enumeration equal to the R card over the flat one. Nothing
// here consults the construction's internals: it sees only the artifacts and
// the S run a caller would store.
/// Per-seed construction steps.
const construct_steps_per_seed: usize = 12;
/// Independent, disjoint PRNG stream off the shared seed.
const construct_seed_mix: u64 = 0x2C4B_9E07_51A3_D6F5;
/// The pinned partition parameter for the differential (submanifests §6.3: k is
/// a pinned repository setting, never a per-commit choice). Appendix A pins 3,
/// and the determinism lane below enumerates the whole supported 1..12 range
/// rather than sampling it.
const construct_k: u4 = 3;
/// The construction input: an ascending name set with contents, and the flat F
/// card list a baseline manifest would carry for it.
const NameSet = struct {
arena: std.heap.ArenaAllocator,
names: [][]const u8,
contents: [][]const u8,
entries: []artifact.FCard,
fn deinit(self: *NameSet) void {
self.arena.deinit();
}
};
/// A chosen name set: parallel, ascending, same length.
const NameList = struct {
names: [][]const u8,
contents: [][]const u8,
};
/// The name universe `p000.c` .. `p999.c` with matching contents, materialized
/// for the entries `chosen` marks. This is the ONE place that spelling lives,
/// so the walk lane and the construct lane cannot drift into different name
/// universes. Scanning the presence table in order yields §4.5.3 ordering
/// without a sort: fixed-width digits make numeric and lexical order coincide.
fn namesOf(a: std.mem.Allocator, chosen: *const [name_space]bool) SweepError!NameList {
var names: std.ArrayList([]const u8) = .empty;
var contents: std.ArrayList([]const u8) = .empty;
for (chosen, 0..) |on, i| {
if (!on) continue;
names.append(a, std.fmt.allocPrint(a, "p{d:0>3}.c", .{i}) catch
return error.OutOfMemory) catch return error.OutOfMemory;
contents.append(a, std.fmt.allocPrint(a, "/* {d:0>3} */\n", .{i}) catch
return error.OutOfMemory) catch return error.OutOfMemory;
}
return .{ .names = names.items, .contents = contents.items };
}
/// A random distinct draw of `want` names.
fn drawNames(a: std.mem.Allocator, random: std.Random, want: usize) SweepError!NameList {
std.debug.assert(want <= name_space);
var chosen = @as([name_space]bool, @splat(false));
var drawn: usize = 0;
while (drawn < want) {
const i = random.uintLessThan(usize, name_space);
if (chosen[i]) continue;
chosen[i] = true;
drawn += 1;
}
return namesOf(a, &chosen);
}
/// The first `want` names, in order: a FIXED shape, so a step built on it
/// always produces the same tree. The forced construct steps use this rather
/// than a draw, which is what turns their coverage from likely into certain.
fn firstNames(a: std.mem.Allocator, want: usize) SweepError!NameList {
std.debug.assert(want <= name_space);
var chosen = @as([name_space]bool, @splat(false));
for (chosen[0..want]) |*on| on.* = true;
return namesOf(a, &chosen);
}
/// Which names a construction step runs on: a random distinct draw, or the
/// fixed leading run the forced steps need.
const NamePick = union(enum) {
draw: struct { random: std.Random, count: usize },
first: usize,
};
/// Build the construction input: the names, their contents, and the flat F card
/// list a baseline manifest would carry for them.
fn genNames(gpa: std.mem.Allocator, pick: NamePick) SweepError!NameSet {
var self = NameSet{
.arena = std.heap.ArenaAllocator.init(gpa),
.names = &.{},
.contents = &.{},
.entries = &.{},
};
errdefer self.arena.deinit();
const a = self.arena.allocator();
const drawn = switch (pick) {
.draw => |d| try drawNames(a, d.random, d.count),
.first => |n| try firstNames(a, n),
};
var entries: std.ArrayList(artifact.FCard) = .empty;
for (drawn.names, drawn.contents) |name, content| {
entries.append(a, .{
.filename = name,
.hash = try sha3Name(a, content),
.perm = null,
.old_name = null,
.mode = .regular,
}) catch return error.OutOfMemory;
}
self.names = drawn.names;
self.contents = drawn.contents;
self.entries = entries.items;
return self;
}
/// Wider than the walk lane's sets: the construction only reaches a second
/// height once a set is big enough for the height-1 scan to reduce it.
const construct_max_files: usize = 120;
/// The §5.5 / [FossilArtifact] §6.3.2 aggregate over a name/content list.
fn aggregateOver(names: []const []const u8, contents: []const []const u8, out: *[32]u8) []u8 {
var agg: artifact.ChecksumAggregator = .{};
for (names, contents) |n, c| agg.update(n, c);
return agg.final(out);
}
/// What the construct lane must actually reach across a seed. Without this the
/// lane passes vacuously: `constructStep` returns early on a flat build, so a
/// `buildTree` that always took §6.2 step 2's exit -- a total regression of the
/// MUST-emit rule -- would leave every assertion below unexecuted and the sweep
/// green.
const ConstructCounters = struct {
/// §6.2 step 2's fewer-than-two-groups exit.
flat: usize = 0,
/// A tree: at least two leaves, the differential fully executed.
tree: usize = 0,
/// A tree with an interior level -- a sub-manifest carrying S cards, which
/// is the only shape that exercises step 3's scan at h >= 1.
multi_level: usize = 0,
};
/// The shapes forced onto the leading steps rather than waited for: §6.2 step
/// 2's two exits (N = 0, the empty check-in Fossil permits, and N = 1, which
/// yields one group), and a set big enough that step 3 forms an interior level
/// at k = 3. Fixed leading runs, so each is the same tree every seed, which is
/// what makes the coverage gate a schedule check rather than a coin flip.
const construct_forced = [_]usize{ 0, 1, 100 };
/// One construction step: build, walk back, and compare against the flat set.
fn constructStep(
gpa: std.mem.Allocator,
random: std.Random,
step: usize,
counters: *ConstructCounters,
) SweepError!void {
var set = try genNames(gpa, if (step < construct_forced.len)
.{ .first = construct_forced[step] }
else
// From 0 to `construct_max_files`, so the free steps can still draw
// either step-2 exit on their own.
.{ .draw = .{ .random = random, .count = random.uintLessThan(usize, construct_max_files + 1) } });
defer set.deinit();
var tb = try artifact.buildTree(gpa, set.entries, construct_k, .sha3_256);
defer tb.deinit();
// §6.2 step 2: a flat build must be exactly the fewer-than-two-groups case,
// and it must leave the caller's existing flat path untouched -- no
// sub-manifests to store and no S run to emit.
if (tb.isFlat()) {
if (tb.subs.len != 0 or tb.s.len != 0) return error.ConstructMismatch;
counters.flat += 1;
return;
}
counters.tree += 1;
if (set.entries.len < 2) return error.ConstructMismatch;
// Parse every constructed sub-manifest into the §5.2 resolver table. This
// is the caller's storage step, in the list order §6.2 requires, and the
// check below is that no artifact references one that comes later.
var parsed: std.ArrayList(artifact.Manifest) = .empty;
defer {
for (parsed.items) |*m| m.deinit();
parsed.deinit(gpa);
}
var interior = false;
for (tb.subs) |sub| {
const m = artifact.parse(gpa, sub.bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.ConstructMismatch, // the writer must emit valid artifacts
};
parsed.append(gpa, m) catch return error.OutOfMemory;
if (m.kind != .submanifest) return error.ConstructMismatch;
// An S-carrying sub-manifest is an interior node: step 3 formed a level
// above the leaves on this build.
if (m.s.len != 0) interior = true;
}
if (interior) counters.multi_level += 1;
var i: usize = 0;
while (i < tb.subs.len) : (i += 1) {
for (parsed.items[i].s) |sc| {
var found = false;
for (tb.subs[0..i]) |prior| found = found or std.mem.eql(u8, prior.name, sc.hash);
if (!found) return error.ConstructMismatch; // referenced before stored
}
}
var entries_buf: std.ArrayList(ViewEntry) = .empty;
defer entries_buf.deinit(gpa);
for (tb.subs, parsed.items) |sub, *m| {
entries_buf.append(gpa, .{
.name = sub.name,
.view = .{ .files = m.f, .subs = m.s },
}) catch return error.OutOfMemory;
}
var vs = ViewStore{ .entries = entries_buf.items };
// The manifest a writer would emit: the flat file set replaced by the S
// run, its R card the §5.5 aggregate over the enumeration.
var flat_r: [32]u8 = undefined;
_ = aggregateOver(set.names, set.contents, &flat_r);
var m: artifact.Manifest = .{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.a = null,
.b = null,
.c = .{ .comment = "construct sweep" },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = .{ .checksum = &flat_r },
.u = .{ .login = "dst" },
.z = null,
.w = null,
.f = &.{},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = tb.s,
.t = &.{},
};
defer m.deinit();
const bytes = artifact.create(&m, gpa) catch return error.OutOfMemory;
defer gpa.free(bytes);
var tree = artifact.parse(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.ConstructMismatch,
};
defer tree.deinit();
if (tree.kind != .manifest or tree.s.len != tb.s.len) return error.ConstructMismatch;
tree.flattenTree(vs.seam()) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.ConstructMismatch,
};
const walked = tree.flattened.?;
// The differential: the walked enumeration IS the flat file list, token for
// token, and its R card is the flat set's R card.
if (walked.len != set.entries.len) return error.ConstructMismatch;
for (walked, set.entries) |got, want| {
if (!std.mem.eql(u8, got.filename, want.filename)) return error.ConstructMismatch;
if (got.hash == null or !std.mem.eql(u8, got.hash.?, want.hash.?)) return error.ConstructMismatch;
}
var walked_names: std.ArrayList([]const u8) = .empty;
defer walked_names.deinit(gpa);
for (walked) |f| walked_names.append(gpa, f.filename) catch return error.OutOfMemory;
var walked_r: [32]u8 = undefined;
_ = aggregateOver(walked_names.items, set.contents, &walked_r);
if (!std.mem.eql(u8, &walked_r, &flat_r)) return error.ConstructMismatch;
if (!std.mem.eql(u8, tree.r.?.checksum, &walked_r)) return error.ConstructMismatch;
}
/// §6.2's byte-identity obligation, swept: two builds of one name set must
/// agree artifact for artifact, at every k the writer MUST support (§6.3:
/// "MUST support every value from 1 to 12 inclusive"). The whole range is
/// enumerated rather than sampled, so no seed can miss a value.
///
/// This reaches per-build state (an unreset scratch, a reused level array), not
/// unordered-container iteration: Zig's hash maps seed identically per process,
/// so a hashmap in the construction would repeat-build byte-identically here.
/// The guard against that is structural -- no unordered container appears in
/// the construction at all -- with the Appendix A vectors and the pinned build
/// in artifact_test.zig as the values that would move.
fn constructDeterminism(gpa: std.mem.Allocator, set: *const NameSet) SweepError!void {
var k: u4 = artifact.min_k;
while (k <= artifact.max_k) : (k += 1) {
var first = try artifact.buildTree(gpa, set.entries, k, .sha3_256);
defer first.deinit();
var second = try artifact.buildTree(gpa, set.entries, k, .sha3_256);
defer second.deinit();
if (first.isFlat() != second.isFlat()) return error.ConstructMismatch;
if (first.subs.len != second.subs.len or first.s.len != second.s.len) return error.ConstructMismatch;
for (first.subs, second.subs) |a_sub, b_sub| {
if (!std.mem.eql(u8, a_sub.bytes, b_sub.bytes)) return error.ConstructMismatch;
if (!std.mem.eql(u8, a_sub.name, b_sub.name)) return error.ConstructMismatch;
}
for (first.s, second.s) |a_s, b_s| {
if (!std.mem.eql(u8, a_s.filename, b_s.filename)) return error.ConstructMismatch;
if (!std.mem.eql(u8, a_s.hash, b_s.hash)) return error.ConstructMismatch;
}
}
}
/// The construction lane: one differential per step, plus the determinism
/// enumeration on the seed's first name set, gated on the three outcomes the
/// lane exists to cover.
fn runConstruct(gpa: std.mem.Allocator, seed: u64) SweepError!void {
var prng = std.Random.DefaultPrng.init(seed +% construct_seed_mix);
const random = prng.random();
var determinism_set = try genNames(gpa, .{
.draw = .{ .random = random, .count = random.uintLessThan(usize, construct_max_files + 1) },
});
defer determinism_set.deinit();
try constructDeterminism(gpa, &determinism_set);
var counters: ConstructCounters = .{};
var step: usize = 0;
while (step < construct_steps_per_seed) : (step += 1) {
try constructStep(gpa, random, step, &counters);
}
// Every seed must reach both sides of §6.2 step 2 and at least one build
// that formed an interior level. `construct_forced` puts all three on the
// first three steps deterministically, so this only ever fires if that
// schedule breaks -- or if the construction stopped producing the shape.
if (counters.flat == 0 or counters.tree == 0 or counters.multi_level == 0) {
return error.CoverageGap;
}
}