Artifact 65016d6ae15579b7e4c7db91ea4659b21dc67533b3807ad30619a3b517ef4ed1:
- File
src/sim/assembly_sweep.zig
— part of check-in
[9d7992613f]
at
2026-07-28 00:45:44
on branch sub-manifest
— Sub-manifest: canonical tree construction, inert behind the emission gate
Implements draft-fossil-submanifests-00 section 6: zbits over the decoded filename, the group scan with its MIN/MAX member bounds, and the final-group merge. One scan serves height 0 and every height above it, so the merge applies uniformly rather than through two code paths that can drift; appendix A.4 is the vector that fails when they do.
Construction emits filenames through a minimal encoder scoped to its own output only. Existing emission keeps the escaping it has always used, so no check-in already written changes its bytes. R cards are emitted for tree manifests alone.
Nothing emits yet: the construction is wired behind a disabled flag, leaves stored before the nodes that reference them. The gate that turns it on is a later change. Tests pin k = 3, the value the appendix vectors use, and cover byte-identity against A.2, A.3 and A.4, determinism across repeated builds, and a constructed tree walking back to the entries it partitioned. (user: dmestas, size: 60700) [annotate] [blame] [check-ins using] [more...]
//! Artifact-level DST sweep for the unclassifiable-artifact state-assembly //! rule (issue #11; 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 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 = "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 = "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 = [_]bool{false} ** name_space; 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 = [_]bool{false} ** name_space; 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; } }