Skip to content
zit Artifact [0e216a3e34]
Login

Artifact [0e216a3e34]

Check-ins Using Download Hex

Artifact 0e216a3e3411efd971e75cee20096d647680f286d83f6361b2a695dc6aeecf75:

//! 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,
    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;
}

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(),
                });
            }
        },
    }
}

// ---------------------------------------------------------------------------
// 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),
    }
}