Artifact 06fee982dbf61d657d33ed1c9ef5b2e2b9ce88103c612d0c5ef6dbd8d14d11a6:
- File
src/git_import_verify.zig
— part of check-in
[c120b93af5]
at
2026-08-05 18:39:07
on branch sub-manifest
— verify: share one sub-manifest memo across every commit
verifyCommits flattened each check-in's whole S-tree against the published store through a resolver that died with the call, so a node near the root was re-fetched, re-inflated and re-parsed once per descendant check-in -- the cost a89b63ad05 removed from deriveCandidateHints, still present here.
repostate.SubManifestMemo already does this for Repository.flattenIfTree, and documents rebinding `inner` for reuse across walks; the log-only path had no way to hold one. flattenTreeFromLogMemo takes a caller-owned slot and the Verifier keeps one for the whole pass.
Byte-identical output. The win is commit count times inter-commit node sharing: 121 commits over 12,000 files touching 6 per commit, 9.88s to 8.19s. Wide per-commit churn destroys the sharing and is unchanged, never slower.
test 3495/3495, fmt. Issue #33. (user: dmestas, size: 53196) [annotate] [blame] [check-ins using]
//! The pre-publication verifier for a packed import generation. //! //! Tasks 3 to 5 gave `zit import-git` the authority to DELETE artifacts from a //! repository and publish the result. This is the proof that what it published //! is the raw generation minus exactly the candidate-only drop set, and that //! nothing else moved. It is the safety net under an irreversible operation, so //! every clause below returns its OWN error and prints its own name: an //! operator who is told only "verification failed" cannot tell a dropped //! artifact from a tampered provenance line, and those two need different //! answers. //! //! Ordered, and the order is load-bearing. Storage-level facts come first //! because every semantic clause reads content and a clause that read corrupt //! bytes would report the wrong thing about them. Within the semantic half, //! commits are walked in stream order, and within one commit the tree comes //! before the parents and the parents before the attribution -- so the most //! direct explanation of a divergence is always the one that fires. //! //! The one refinement to a naive `packed == raw - drop_set` name comparison is //! documented at `deferDifference`: a check-in's NAME is a function of its //! content, so a check-in appearing or disappearing is never an independent //! fact. It is the shadow of a content change, and the content clauses are what //! explain content. Such a difference is therefore deferred, not dropped -- if //! no later clause explains it, it is reported at the end under its own name. //! //! SCOPE, stated so the operator-facing promise is not read wider than it is. //! What this file proves is a relation between generation 1, generation 2 and //! the witness the import took of its own decisions: the published generation //! is the raw one minus exactly the candidate-only drop set, every published //! check-in flattens/parents/attributes to what the import recorded, and the //! three staging files agree with all of it. What it does NOT prove is that //! generation 1 was a faithful translation of the Git stream -- that is the //! translator's own contract, established by the e2e lane against real `git`. //! An artifact a translation bug wrote into generation 1, that is in no drop //! set and that packing faithfully carried forward, satisfies every clause //! here. "Nothing else moved" is the claim; "the source was right" is not. const std = @import("std"); const zit = @import("zit"); const artifact = zit.artifact; const git_import = zit.git_import; const logstore = zit.logstore; const repoview = zit.repoview; const repostate = zit.repostate; const Repository = zit.Repository; /// One named invariant. The token each renders is the operator-facing contract: /// `import-git: verifier: <token>`. pub const Clause = enum { raw_store_unreadable, raw_rehash_mismatch, packed_store_unreadable, artifact_rehash_mismatch, delta_base_mismatch, retained_omitted_artifact, dropped_noncandidate_artifact, dropped_required_artifact, added_artifact, checkin_unresolvable, checkin_name_mismatch, normalized_tree_digest_mismatch, parent_order_mismatch, attribution_mismatch, ref_target_mismatch, tag_mismatch, provenance_record_mismatch, provenance_digest_mismatch, repository_view_mismatch, checkout_invalid, map_unreadable, pub fn token(self: Clause) []const u8 { return switch (self) { .raw_store_unreadable => "raw-store-unreadable", .raw_rehash_mismatch => "raw-rehash-mismatch", .packed_store_unreadable => "packed-store-unreadable", .artifact_rehash_mismatch => "artifact-rehash-mismatch", .delta_base_mismatch => "delta-base-mismatch", .retained_omitted_artifact => "retained-omitted-artifact", .dropped_noncandidate_artifact => "dropped-noncandidate-artifact", .dropped_required_artifact => "dropped-required-artifact", .added_artifact => "added-artifact", .checkin_unresolvable => "checkin-unresolvable", .checkin_name_mismatch => "checkin-name-mismatch", .normalized_tree_digest_mismatch => "normalized-tree-digest-mismatch", .parent_order_mismatch => "parent-order-mismatch", .attribution_mismatch => "attribution-mismatch", .ref_target_mismatch => "ref-target-mismatch", .tag_mismatch => "tag-mismatch", .provenance_record_mismatch => "provenance-record-mismatch", .provenance_digest_mismatch => "provenance-digest-mismatch", .repository_view_mismatch => "repository-view-mismatch", .checkout_invalid => "checkout-invalid", .map_unreadable => "map-unreadable", }; } /// The error a clause refuses with. One per clause, so a caller can switch /// on the reason rather than on a printed string. pub fn err(self: Clause) Error { return switch (self) { .raw_store_unreadable => error.VerifierRawStoreUnreadable, .raw_rehash_mismatch => error.VerifierRawRehashMismatch, .packed_store_unreadable => error.VerifierPackedStoreUnreadable, .artifact_rehash_mismatch => error.VerifierArtifactRehashMismatch, .delta_base_mismatch => error.VerifierDeltaBaseMismatch, .retained_omitted_artifact => error.VerifierRetainedOmittedArtifact, .dropped_noncandidate_artifact => error.VerifierDroppedNoncandidateArtifact, .dropped_required_artifact => error.VerifierDroppedRequiredArtifact, .added_artifact => error.VerifierAddedArtifact, .checkin_unresolvable => error.VerifierCheckinUnresolvable, .checkin_name_mismatch => error.VerifierCheckinNameMismatch, .normalized_tree_digest_mismatch => error.VerifierNormalizedTreeDigestMismatch, .parent_order_mismatch => error.VerifierParentOrderMismatch, .attribution_mismatch => error.VerifierAttributionMismatch, .ref_target_mismatch => error.VerifierRefTargetMismatch, .tag_mismatch => error.VerifierTagMismatch, .provenance_record_mismatch => error.VerifierProvenanceRecordMismatch, .provenance_digest_mismatch => error.VerifierProvenanceDigestMismatch, .repository_view_mismatch => error.VerifierRepositoryViewMismatch, .checkout_invalid => error.VerifierCheckoutInvalid, .map_unreadable => error.VerifierMapUnreadable, }; } }; pub const Error = error{ VerifierRawStoreUnreadable, VerifierRawRehashMismatch, VerifierPackedStoreUnreadable, VerifierArtifactRehashMismatch, VerifierDeltaBaseMismatch, VerifierRetainedOmittedArtifact, VerifierDroppedNoncandidateArtifact, VerifierDroppedRequiredArtifact, VerifierAddedArtifact, VerifierCheckinUnresolvable, VerifierCheckinNameMismatch, VerifierNormalizedTreeDigestMismatch, VerifierParentOrderMismatch, VerifierAttributionMismatch, VerifierRefTargetMismatch, VerifierTagMismatch, VerifierProvenanceRecordMismatch, VerifierProvenanceDigestMismatch, VerifierRepositoryViewMismatch, VerifierCheckoutInvalid, VerifierMapUnreadable, OutOfMemory, }; const hex_name_len = 2 * logstore.max_hash_len; /// A generation's artifact names, in persisted order and as a set. const Inventory = struct { order: std.ArrayList([]const u8) = .empty, set: std.StringHashMapUnmanaged(void) = .empty, fn add(self: *Inventory, gpa: std.mem.Allocator, name: []const u8) !void { try self.order.append(gpa, name); try self.set.put(gpa, name, {}); } }; /// A name difference whose explanation the content clauses may still own. const Deferred = struct { clause: Clause, name: []const u8, }; /// One artifact's content identity, memoized across the whole tree sweep. A /// wide repository names the same blob from many commits, and without this the /// normalized-tree recompute would be quadratic in the history rather than /// linear in the store. const ContentFacts = struct { length: u64, digest: git_import.Digest, }; /// One `kind:"commit"` record of the finalized JSONL. const MapCommit = struct { oid: []const u8, zit: []const u8, author: MapIdentity, committer: MapIdentity, tree_digest: []const u8, provenance_digest: []const u8, }; const MapIdentity = struct { name: []const u8, email: []const u8, timestamp: i64, timezone_offset_minutes: i64, }; /// One `kind:"ref"` or `kind:"tag"` record, reduced to the mapping it asserts. const MapMapping = struct { canonical: []const u8, target: []const u8, }; const RefRow = struct { canonical: []const u8, target: []const u8, }; pub const Input = struct { /// Generation 1, frozen. raw: *logstore.LogStore, /// Generation 2, frozen -- the one that will be published. packed_generation: *logstore.LogStore, /// What the import decided, captured before the freeze destroyed it. witness: *const git_import.ImportWitness, /// The classifier's candidate-only drop set, as hex artifact names. drop_names: []const []const u8, /// The finalized provenance map, verbatim. map: []const u8, /// The `refs` interop file, verbatim. refs: []const u8, /// The header `writeRefs` opens `refs` with. refs_header: []const u8, /// The branch `.zit-checkout` names. checkout_branch: []const u8, }; /// Run the ordered pipeline. Returns on the FIRST clause that refuses, having /// already printed its name and enough detail to act on. pub fn verify(gpa: std.mem.Allocator, input: Input, err: *std.Io.Writer) Error!void { var arena_state = std.heap.ArenaAllocator.init(gpa); defer arena_state.deinit(); var self: Verifier = .{ .gpa = gpa, .arena = arena_state.allocator(), .err = err, .input = input, }; defer self.deinit(); return self.run(); } const Verifier = struct { gpa: std.mem.Allocator, /// Names, parsed records and memo keys. Freed in one act by `verify`. arena: std.mem.Allocator, err: *std.Io.Writer, input: Input, raw: Inventory = .{}, packed_names: Inventory = .{}, drops: std.StringHashMapUnmanaged(void) = .empty, deferred: std.ArrayList(Deferred) = .empty, facts: std.StringHashMapUnmanaged(ContentFacts) = .empty, /// Witnessed check-in name -> the name the published generation carries for /// it. Identity for every commit no content clause had to explain. resolved: std.StringHashMapUnmanaged([]const u8) = .empty, /// Shared across EVERY commit's tree enumeration, which is the point: /// adjacent check-ins share nearly all of their sub-manifest nodes, so a /// per-call memo would throw away the sharing the format exists to create /// and re-inflate a root-adjacent node once per descendant check-in. /// Keyed by artifact name, so a hit is the same artifact by content /// address. Bounded by the memo's own retention budget, and it degrades to /// the naive behaviour rather than failing when that budget is met. sub_memo: ?repostate.SubManifestMemo = null, map_commits: std.ArrayList(MapCommit) = .empty, map_refs: std.ArrayList(MapMapping) = .empty, map_tags: std.ArrayList(MapMapping) = .empty, map_summary_digest: ?[]const u8 = null, // Indexes, not conveniences. Every lookup below sits inside a loop over // the whole import, so a linear scan would make verification quadratic in // the history -- unnoticeable on a fixture and ruinous on a real one. map_commit_index: std.StringHashMapUnmanaged(usize) = .empty, map_ref_index: std.StringHashMapUnmanaged(usize) = .empty, map_tag_index: std.StringHashMapUnmanaged(usize) = .empty, witness_ref_index: std.StringHashMapUnmanaged(usize) = .empty, witness_oid_index: std.StringHashMapUnmanaged(usize) = .empty, /// Every mirror-candidate artifact name any witnessed commit carried. The /// drop set is only allowed to name these. witness_candidate_names: std.StringHashMapUnmanaged(void) = .empty, /// One memo for the PUBLISHED generation, shared by every semantic clause. /// A delta chain runs to `logstore.max_delta_chain` frames, and every /// content read below sits inside a loop over the whole import -- reading /// uncached would multiply the store by the chain depth, once per clause. packed_cache: logstore.PlaintextCache = .{}, fn deinit(self: *Verifier) void { self.packed_cache.deinit(self.gpa); self.witness_candidate_names.deinit(self.gpa); // Every allocation these hold came from the arena; only the maps' own // spines are the general allocator's. self.raw.order.deinit(self.gpa); self.raw.set.deinit(self.gpa); self.packed_names.order.deinit(self.gpa); self.packed_names.set.deinit(self.gpa); self.drops.deinit(self.gpa); self.deferred.deinit(self.gpa); self.facts.deinit(self.gpa); self.resolved.deinit(self.gpa); // Owns an arena holding every cached node view; the walk itself never // frees it, because the whole point is that the views outlive the // check-in that first resolved them. if (self.sub_memo) |*memo| memo.deinit(); self.map_commits.deinit(self.gpa); self.map_refs.deinit(self.gpa); self.map_tags.deinit(self.gpa); self.map_commit_index.deinit(self.gpa); self.map_ref_index.deinit(self.gpa); self.map_tag_index.deinit(self.gpa); self.witness_ref_index.deinit(self.gpa); self.witness_oid_index.deinit(self.gpa); } fn fail(self: *Verifier, clause: Clause, comptime fmt: []const u8, args: anytype) Error { self.err.print("import-git: verifier: {s}: " ++ fmt ++ "\n", .{clause.token()} ++ args) catch {}; return clause.err(); } fn run(self: *Verifier) Error!void { for (self.input.drop_names) |name| try self.drops.put(self.gpa, name, {}); for (self.input.witness.refs, 0..) |mapping, index| { try self.witness_ref_index.put(self.gpa, mapping.canonical, index); } for (self.input.witness.commits, 0..) |commit, index| { for (commit.candidates) |slot| { const candidate = slot orelse continue; try self.witness_candidate_names.put(self.gpa, candidate.name, {}); } const oid = commit.oid orelse continue; try self.witness_oid_index.put(self.gpa, oid, index); } try self.readMap(); // 0. The drop set is CANDIDATE-only. Every later clause proves the // published generation is the raw one minus this set; that only // means what it should if the set itself holds nothing but mirror // metadata. True by construction -- the classifier builds it out of // `mirror_candidate_names` alone -- and checked anyway, because // "the equation holds against whatever names it was handed" is a // materially weaker statement than the one this file promises. for (self.input.drop_names) |name| { if (self.witness_candidate_names.contains(name)) continue; return self.fail(.dropped_noncandidate_artifact, "{s} is in the drop set but is no commit's mirror candidate", .{name}); } // 1. Every raw artifact reconstructs and hashes to its name. // // `packLog` already did this for every frame it KEPT. What is left, // and what this pass exists for, is the drop set: the artifacts // about to be deleted forever are the only ones nothing else looks // at, and "these bytes really were what the classifier decided // about" is the last chance to establish that. try self.sweep(self.input.raw, .raw); // 2. The same, over the generation that will actually be published. // `packLog` verified its own output too -- but that was before this // file was closed, and this is the copy that gets renamed. try self.sweep(self.input.packed_generation, .packed_generation); // 3. packed == raw - drop_set, as an explicit name-set difference. try self.compareNameSets(); // 4-6. Every witnessed commit, resolved out of the published store and // compared against what the import decided it was. try self.verifyCommits(); // 7. Every branch, lightweight tag and annotated tag. try self.verifyRefs(); // 8. Every provenance record, recomputed. try self.verifyProvenance(); // 9. The repository view, derived from scratch. try self.verifyRepositoryView(); // Anything clauses 4-9 declined to explain. try self.reportDeferred(); } // -- 1 and 2: reconstruct and rehash ----------------------------------- const Generation = enum { raw, packed_generation, fn label(self: Generation) []const u8 { return switch (self) { .raw => "raw", .packed_generation => "packed", }; } }; fn sweep(self: *Verifier, log: *logstore.LogStore, generation: Generation) Error!void { const rehash: Clause = switch (generation) { .raw => .raw_rehash_mismatch, .packed_generation => .artifact_rehash_mismatch, }; const rids = try log.ridsInPersistedOrder(self.gpa); defer self.gpa.free(rids); // Bases persist strictly before their deltas, so walking persisted // order keeps each base hot and collapses a delta chain's read // amplification to about one pass over the store. var cache = logstore.PlaintextCache.init(); defer cache.deinit(self.gpa); for (rids) |rid| { var buffer: [hex_name_len]u8 = undefined; const transient = hexName(log.hashOf(rid), &buffer); const content = log.contentUnmasked(self.gpa, rid, &cache) catch |e| { // Reconstruction FAILED rather than produced wrong bytes. On a // delta frame that is a statement about the chain -- a base // that is not the one the payload was encoded against -- and it // is a different repair from a frame whose bytes rotted. const clause: Clause = if (log.kindOf(rid) == .delta) .delta_base_mismatch else rehash; return self.fail(clause, "{s} generation: {s} cannot be reconstructed: {s}", .{ generation.label(), transient, @errorName(e), }); } orelse { // Unreachable today: `ridsInPersistedOrder` filters phantoms // and `contentUnmasked` returns null for nothing else. Refused // rather than skipped all the same -- a `continue` here would // leave the name out of the inventory, and a name missing from // the inventory is a name `compareNameSets` can never find. The // clause standing guard over an irreversible delete would then // report success for an artifact physically present in the // published store, which is the wrong direction to degrade in. return self.fail(rehash, "{s} generation: {s} has no content", .{ generation.label(), transient }); }; defer self.gpa.free(content); if (!artifact.verify(transient, content)) { return self.fail(rehash, "{s} generation: {s} does not hash to its name", .{ generation.label(), transient, }); } const name = try self.arena.dupe(u8, transient); switch (generation) { .raw => try self.raw.add(self.gpa, name), .packed_generation => try self.packed_names.add(self.gpa, name), } } } // -- 3: the name-set difference ---------------------------------------- /// A check-in's name is derived from its bytes, so a check-in that appears /// or disappears is never an independent fact: it is the shadow of a /// content change, and clauses 4 to 8 are what explain content changes. /// Reporting the shadow first would mean an artifact-set-preserving tree /// edit and a reordered parent run both surfaced as "an artifact was /// added", which tells an operator nothing about what actually moved. /// /// So a difference among CHECK-INS is deferred -- never discarded. If no /// later clause explains it, `reportDeferred` states it under its own name, /// and the rename still blocks publication either way. fn deferDifference(self: *Verifier, clause: Clause, log: *logstore.LogStore, name: []const u8) Error!void { if (!self.namesCheckin(log, name)) return self.fail(clause, "{s}", .{name}); try self.deferred.append(self.gpa, .{ .clause = clause, .name = name }); } fn compareNameSets(self: *Verifier) Error!void { // Upward: nothing the classifier authorized dropping survived. This is // the direction that would silently make the whole omission pointless, // and it is checked first because it can never be a shadow of anything. for (self.input.drop_names) |name| { if (self.packed_names.set.contains(name)) { return self.fail(.retained_omitted_artifact, "{s} is in the drop set and still in the packed generation", .{name}); } } // Downward: everything else generation 1 held is still here. for (self.raw.order.items) |name| { if (self.drops.contains(name)) continue; if (self.packed_names.set.contains(name)) continue; try self.deferDifference(.dropped_required_artifact, self.input.raw, name); } // Outward: the pack invented nothing. for (self.packed_names.order.items) |name| { if (self.raw.set.contains(name)) continue; try self.deferDifference(.added_artifact, self.input.packed_generation, name); } } /// First deferral wins, for the same reason the pipeline stops at its first /// refusing clause: one difference is an explanation, a list of them is a /// diff. If any survived to here, none of clauses 4 to 9 accounted for it. fn reportDeferred(self: *Verifier) Error!void { if (self.deferred.items.len == 0) return; const item = self.deferred.items[0]; return self.fail(item.clause, "{s} (no content clause accounts for it)", .{item.name}); } // -- 4 to 6: every commit ---------------------------------------------- fn verifyCommits(self: *Verifier) Error!void { // Stream order, and that is what makes commit-major iteration safe: a // parent always precedes its children, so a check-in whose content // changed trips its OWN tree or parent clause before any child's parent // clause can trip on the resulting rename. for (self.input.witness.commits) |*commit| { const name = self.publishedNameOf(commit); try self.resolved.put(self.gpa, commit.checkin, name); // The one assertion the map exists to make -- "this Git commit // became THIS Zit check-in" -- and the map is a file under test, // not an authority. Without this a tampered map redirects the // verifier instead of being caught by it: exchange the `zit` values // of two commits that share a tree, a parent run and a selected // identity and clauses 4 to 8 all read the wrong-but-consistent // check-in and pass. // // Deferred rather than immediate, for `deferDifference`'s reason: // the two store faults that permute a check-in's content rename it // and carry the rename into the map, so the tree or parent clause // must be what fires. Nothing escapes -- `reportDeferred` states it // when nothing else did. if (!std.mem.eql(u8, name, commit.checkin)) { try self.deferred.append(self.gpa, .{ .clause = .checkin_name_mismatch, .name = name }); } const bytes = (self.contentByName(self.input.packed_generation, name) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(.checkin_unresolvable, "{s}: {s} cannot be reconstructed", .{ self.describe(commit), name }), }) orelse return self.fail(.checkin_unresolvable, "{s}: {s} is absent from the packed generation", .{ self.describe(commit), name }); defer self.gpa.free(bytes); var manifest = artifact.parse(self.gpa, bytes) catch |e| { return self.fail(.checkin_unresolvable, "{s}: {s} does not parse: {s}", .{ self.describe(commit), name, @errorName(e) }); }; defer manifest.deinit(); if (manifest.kind != .manifest) { return self.fail(.checkin_unresolvable, "{s}: {s} is a {s}, not a check-in", .{ self.describe(commit), name, @tagName(manifest.kind) }); } // Either root shape, flattened through the same ยง5.1 enumeration // seam every reader uses -- against the PUBLISHED store, which is // the whole difference from the import's own digest: the S nodes it // covered lived in a commit-local staging store that no longer // exists. if (manifest.s.len != 0) { Repository.flattenTreeFromLogMemo(self.gpa, self.input.packed_generation, &manifest, &self.sub_memo) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(.checkin_unresolvable, "{s}: {s} does not enumerate: {s}", .{ self.describe(commit), name, @errorName(e) }), }; } const files = manifest.flattened orelse manifest.f; try self.verifyTreeDigest(commit, name, files); try self.verifyParents(commit, name, &manifest); try self.verifyAttribution(commit, name, &manifest); } } /// The name the published generation carries for `commit`. The finalized /// map is the authority when it names one, because the map ships WITH the /// store and an operator reads them together; the witness is the fallback /// for a commit the stream carried no OID for, which therefore has no map /// line at all. fn publishedNameOf(self: *Verifier, commit: *const git_import.WitnessCommit) []const u8 { const oid = commit.oid orelse return commit.checkin; const record = self.mapCommitOf(oid) orelse return commit.checkin; return record.zit; } fn describe(self: *Verifier, commit: *const git_import.WitnessCommit) []const u8 { _ = self; return commit.oid orelse "(no original-oid)"; } fn verifyTreeDigest( self: *Verifier, commit: *const git_import.WitnessCommit, name: []const u8, files: []const artifact.FCard, ) Error!void { var builder = git_import.TreeDigestBuilder.init(); var previous: ?[]const u8 = null; for (files) |card| { // Checked rather than asserted: the builder asserts canonical order // because its producers guarantee it, and this one is reading a // store it is not allowed to trust. if (previous) |last| { if (artifact.compareBytes(last, card.filename) != .lt) { return self.fail(.checkin_unresolvable, "{s}: {s} enumerates '{s}' out of canonical order", .{ self.describe(commit), name, card.filename }); } } previous = card.filename; const hash = card.hash orelse { return self.fail(.checkin_unresolvable, "{s}: {s} has no content for '{s}'", .{ self.describe(commit), name, card.filename }); }; const facts = (try self.contentFacts(hash)) orelse { return self.fail(.normalized_tree_digest_mismatch, "{s}: {s} names absent content {s} at '{s}'", .{ self.describe(commit), name, hash, card.filename }); }; builder.entry(card.filename, card.mode, facts.length, facts.digest); } const recomputed = builder.final(); if (!std.mem.eql(u8, &recomputed, &commit.tree_digest)) { var want: [64]u8 = undefined; var got: [64]u8 = undefined; return self.fail(.normalized_tree_digest_mismatch, "{s}: {s} flattens to {s}, imported as {s}", .{ self.describe(commit), name, git_import.formatDigest(recomputed, &got), git_import.formatDigest(commit.tree_digest, &want), }); } } fn verifyParents( self: *Verifier, commit: *const git_import.WitnessCommit, name: []const u8, manifest: *const artifact.Manifest, ) Error!void { if (manifest.p.len > 1) { return self.fail(.parent_order_mismatch, "{s}: {s} carries {d} P cards", .{ self.describe(commit), name, manifest.p.len }); } const text: []const u8 = if (manifest.p.len == 0) "" else (manifest.p[0].parents orelse ""); var seen: usize = 0; var parts = std.mem.splitScalar(u8, text, ' '); while (parts.next()) |stored| { if (stored.len == 0) continue; if (seen >= commit.parents.len) { return self.fail(.parent_order_mismatch, "{s}: {s} names more than the {d} imported parents", .{ self.describe(commit), name, commit.parents.len }); } // Through the same substitution the check-in itself went through, // so a renamed parent is accounted for once -- as its own deferred // difference -- rather than a second time here. const expected = self.resolved.get(commit.parents[seen]) orelse commit.parents[seen]; if (!std.mem.eql(u8, stored, expected)) { return self.fail(.parent_order_mismatch, "{s}: {s} names {s} as parent {d}, imported with {s}", .{ self.describe(commit), name, stored, seen, expected }); } seen += 1; } if (seen != commit.parents.len) { return self.fail(.parent_order_mismatch, "{s}: {s} names {d} parents, imported with {d}", .{ self.describe(commit), name, seen, commit.parents.len }); } } fn verifyAttribution( self: *Verifier, commit: *const git_import.WitnessCommit, name: []const u8, manifest: *const artifact.Manifest, ) Error!void { const selected = self.input.witness.selected(commit); const card = manifest.u orelse { return self.fail(.attribution_mismatch, "{s}: {s} carries no U card", .{ self.describe(commit), name }); }; if (!std.mem.eql(u8, card.login, selected.name)) { return self.fail(.attribution_mismatch, "{s}: {s} is attributed to '{s}', imported as '{s}'", .{ self.describe(commit), name, card.login, selected.name }); } // The record half. The store carries only the SELECTED identity, so a // map that exchanged the two would leave the store untouched and every // artifact hashing correctly -- this is the only clause that can see it. const oid = commit.oid orelse return; const record = self.mapCommitOf(oid) orelse return; try self.expectIdentity(commit, "author", record.author, commit.author); try self.expectIdentity(commit, "committer", record.committer, commit.committer); } fn expectIdentity( self: *Verifier, commit: *const git_import.WitnessCommit, role: []const u8, recorded: MapIdentity, imported: git_import.WitnessIdentity, ) Error!void { if (std.mem.eql(u8, recorded.name, imported.name) and std.mem.eql(u8, recorded.email, imported.email) and recorded.timestamp == imported.timestamp and recorded.timezone_offset_minutes == imported.timezone_offset_minutes) return; return self.fail(.attribution_mismatch, "{s}: recorded {s} '{s} <{s}> {d}' but imported '{s} <{s}> {d}'", .{ self.describe(commit), role, recorded.name, recorded.email, recorded.timestamp, imported.name, imported.email, imported.timestamp, }); } // -- 7: refs, lightweight tags and annotated tags ----------------------- fn verifyRefs(self: *Verifier) Error!void { var rows: std.ArrayList(RefRow) = .empty; defer rows.deinit(self.gpa); var row_index: std.StringHashMapUnmanaged(usize) = .empty; defer row_index.deinit(self.gpa); try self.parseRefs(&rows); // Indexed like every other lookup in this file. A mirror can carry tens // of thousands of refs, and this lookup sits inside the loop over all // of them. for (rows.items, 0..) |row, index| try row_index.put(self.gpa, row.canonical, index); for (self.input.witness.refs) |mapping| { const clause = clauseForRef(mapping.canonical); const expected = self.resolved.get(mapping.target) orelse mapping.target; const row = findRow(&row_index, rows.items, mapping.canonical) orelse { return self.fail(clause, "'{s}' is missing from refs", .{mapping.canonical}); }; if (!std.mem.eql(u8, row.target, expected)) { return self.fail(clause, "'{s}' points at {s}, imported at {s}", .{ mapping.canonical, row.target, expected }); } // A ref naming something the published store does not hold is a // repository nobody can check out, however well its rows compare. if (!self.packed_names.set.contains(row.target)) { return self.fail(clause, "'{s}' points at {s}, which the packed generation does not hold", .{ mapping.canonical, row.target }); } // The map's own copy of the same mapping. Annotated tags are // deliberately absent from its `ref` records and appear as `tag` // records instead, so each is looked for where it belongs. const recorded = if (mapping.annotated) self.findMapping(&self.map_tag_index, self.map_tags.items, mapping.canonical) else self.findMapping(&self.map_ref_index, self.map_refs.items, mapping.canonical); const found = recorded orelse { return self.fail(clause, "'{s}' has no record in the import map", .{mapping.canonical}); }; if (!std.mem.eql(u8, found.target, expected)) { return self.fail(clause, "'{s}' is recorded at {s}, imported at {s}", .{ mapping.canonical, found.target, expected }); } } for (rows.items) |row| { if (self.witnessedRef(row.canonical) != null) continue; return self.fail(clauseForRef(row.canonical), "'{s}' is in refs but was never imported", .{row.canonical}); } // The same "nothing the import did not produce" sweep the commit // records get, over the map's own ref and tag records. Without it a map // could carry a mapping for a tag that was never imported and every // clause above would still pass -- each one only ever reads the map // FROM the witness side. for (self.map_refs.items) |record| { if (self.witnessedRef(record.canonical) != null) continue; return self.fail(.ref_target_mismatch, "the import map records ref '{s}', which was never imported", .{record.canonical}); } for (self.map_tags.items) |record| { if (self.witnessedRef(record.canonical) != null) continue; return self.fail(.tag_mismatch, "the import map records tag '{s}', which was never imported", .{record.canonical}); } } fn parseRefs(self: *Verifier, rows: *std.ArrayList(RefRow)) Error!void { const body = self.input.refs; if (!std.mem.startsWith(u8, body, self.input.refs_header)) { return self.fail(.ref_target_mismatch, "refs does not open with its version header", .{}); } var lines = std.mem.splitScalar(u8, body[self.input.refs_header.len..], '\n'); while (lines.next()) |line| { if (line.len == 0) continue; const space = std.mem.lastIndexOfScalar(u8, line, ' ') orelse { return self.fail(.ref_target_mismatch, "refs row '{s}' has no target", .{line}); }; try rows.append(self.gpa, .{ .canonical = line[0..space], .target = line[space + 1 ..] }); } } fn witnessedRef(self: *Verifier, canonical: []const u8) ?*const git_import.WitnessRef { const index = self.witness_ref_index.get(canonical) orelse return null; return &self.input.witness.refs[index]; } /// Which clause owns a ref row. A tag and a branch are different kinds of /// mapping and a change that turns one into the other is a tag change, not /// a retarget -- so the clause follows the canonical namespace. fn clauseForRef(canonical: []const u8) Clause { return if (std.mem.startsWith(u8, canonical, "sym-tags/")) .tag_mismatch else .ref_target_mismatch; } fn findRow(index: *const std.StringHashMapUnmanaged(usize), rows: []const RefRow, canonical: []const u8) ?RefRow { const at = index.get(canonical) orelse return null; return rows[at]; } fn findMapping( self: *Verifier, index: *const std.StringHashMapUnmanaged(usize), items: []const MapMapping, canonical: []const u8, ) ?MapMapping { _ = self; const at = index.get(canonical) orelse return null; return items[at]; } // -- 8: provenance ------------------------------------------------------ fn verifyProvenance(self: *Verifier) Error!void { for (self.input.witness.commits) |*commit| { const oid = commit.oid orelse continue; const record = self.mapCommitOf(oid) orelse { return self.fail(.provenance_record_mismatch, "{s} has no commit record in the import map", .{oid}); }; var buffer: [64]u8 = undefined; const tree = git_import.formatDigest(commit.tree_digest, &buffer); if (!std.mem.eql(u8, record.tree_digest, tree)) { return self.fail(.provenance_record_mismatch, "{s} records tree digest {s}, imported as {s}", .{ oid, record.tree_digest, tree }); } // Two comparisons, and they are worth different amounts. The // recompute runs `provenanceDigestOf` over the witnessed inputs and // compares it to the digest the import recorded from the SAME // inputs -- so it can only fail if `captureWitness` dropped a digest // input, which is a narrow but real class of bug and the only one // reachable from inside a verifier. The comparison that follows it, // against the value the JSONL actually carries, is the one that // sees a tampered line. const recomputed = self.provenanceDigestOf(commit); var want: [64]u8 = undefined; const rendered = git_import.formatDigest(recomputed, &want); if (!std.mem.eql(u8, &recomputed, &commit.provenance_digest)) { var imported: [64]u8 = undefined; return self.fail(.provenance_digest_mismatch, "{s} recomputes to {s}, imported as {s}", .{ oid, rendered, git_import.formatDigest(commit.provenance_digest, &imported), }); } if (!std.mem.eql(u8, record.provenance_digest, rendered)) { return self.fail(.provenance_digest_mismatch, "{s} records {s}, recomputes to {s}", .{ oid, record.provenance_digest, rendered }); } } // Nothing in the map that the import did not produce. for (self.map_commits.items) |record| { if (self.witness_oid_index.contains(record.oid)) continue; return self.fail(.provenance_record_mismatch, "the import map records {s}, which was never imported", .{record.oid}); } // The whole-import digest. Its inputs -- annotated-tag-origin refs and // every tagger identity -- are deliberately not all present in the // JSONL, so the summary's value is checked against the witnessed one // rather than re-derived from the file it sits in. const summary = self.map_summary_digest orelse { return self.fail(.provenance_record_mismatch, "the import map carries no summary record", .{}); }; var buffer: [64]u8 = undefined; const expected = git_import.formatDigest(self.input.witness.provenance_digest, &buffer); if (!std.mem.eql(u8, summary, expected)) { return self.fail(.provenance_digest_mismatch, "the summary records {s}, imported as {s}", .{ summary, expected }); } } fn provenanceDigestOf(self: *Verifier, commit: *const git_import.WitnessCommit) git_import.Digest { const selected = self.input.witness.selected(commit); var candidates: [git_import.mirror_candidate_names.len]git_import.ProvenanceCandidate = undefined; var present: usize = 0; for (commit.candidates) |slot| { const candidate = slot orelse continue; candidates[present] = .{ .path = candidate.path, .name = candidate.name, .oid = candidate.oid orelse "", }; present += 1; } return git_import.provenanceDigestOf(.{ .oid = commit.oid orelse "", .parent_oids = commit.parent_oids, .attribution = @tagName(self.input.witness.attribution), .identity_name = selected.name, .identity_email = selected.email, .identity_timestamp = selected.timestamp, .identity_zone_minutes = selected.timezone_offset_minutes, .tree_digest = commit.tree_digest, .decision = @tagName(commit.decision), .reason = if (commit.decision == .retained) @tagName(commit.reason) else "", .candidates = candidates[0..present], .checkin = commit.checkin, }); } fn mapCommitOf(self: *Verifier, oid: []const u8) ?MapCommit { const index = self.map_commit_index.get(oid) orelse return null; return self.map_commits.items[index]; } // -- 9: the repository, derived from scratch ---------------------------- fn verifyRepositoryView(self: *Verifier) Error!void { var view: repoview.RepoView = undefined; // `load` is transactional -- it tears itself down on failure -- so the // `defer` belongs strictly after the `catch`, and a `deinit` reached on // the failure path would be a double free rather than the leak it looks // like. view.load(self.gpa, self.input.packed_generation) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(.repository_view_mismatch, "the packed generation does not crosslink: {s}", .{@errorName(e)}), }; defer view.deinit(self.gpa); if (!std.mem.eql(u8, view.main_branch, self.input.witness.primary_branch)) { return self.fail(.repository_view_mismatch, "derives default branch '{s}', imported as '{s}'", .{ view.main_branch, self.input.witness.primary_branch }); } // Every published check-in is a check-in to the DERIVED view too, not // merely a well-formed artifact that parses as one. This is what makes // the crosslink pass a statement rather than a smoke test: a manifest // the repository declines to crosslink -- no D card the reader accepts, // no event row -- is a check-in `zit timeline` will never show and // `zit update` will never reach, however cleanly it hashes. var seen: std.StringHashMapUnmanaged(void) = .empty; defer seen.deinit(self.gpa); for (self.input.witness.commits) |*commit| { const name = self.resolved.get(commit.checkin) orelse commit.checkin; if ((try seen.fetchPut(self.gpa, name, {})) != null) continue; const rid = view.lookup(name) orelse { return self.fail(.repository_view_mismatch, "{s}: {s} is not in the derived repository", .{ self.describe(commit), name }); }; if (view.state.mtimeOf(rid) == null) { return self.fail(.repository_view_mismatch, "{s}: {s} crosslinks no check-in event", .{ self.describe(commit), name }); } } if (self.input.checkout_branch.len == 0) { return self.fail(.checkout_invalid, "the published checkout names no branch", .{}); } if (!std.mem.eql(u8, self.input.checkout_branch, self.input.witness.primary_branch)) { return self.fail(.checkout_invalid, "the published checkout names '{s}', imported as '{s}'", .{ self.input.checkout_branch, self.input.witness.primary_branch }); } } // -- the finalized map -------------------------------------------------- fn readMap(self: *Verifier) Error!void { var lines = std.mem.splitScalar(u8, self.input.map, '\n'); while (lines.next()) |line| { if (line.len == 0) continue; var parsed = std.json.parseFromSlice(std.json.Value, self.gpa, line, .{}) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, else => return self.fail(.map_unreadable, "a record does not parse: {s}", .{@errorName(e)}), }; defer parsed.deinit(); const object = switch (parsed.value) { .object => |value| value, else => return self.fail(.map_unreadable, "a record is not an object", .{}), }; const kind = stringOf(object.get("kind")) orelse { return self.fail(.map_unreadable, "a record carries no kind", .{}); }; if (std.mem.eql(u8, kind, "commit")) { const record: MapCommit = .{ .oid = try self.mapString(object, "oid"), .zit = try self.mapString(object, "zit"), .author = try self.mapIdentity(object, "author"), .committer = try self.mapIdentity(object, "committer"), .tree_digest = try self.mapString(object, "tree_digest"), .provenance_digest = try self.mapString(object, "provenance_digest"), }; try self.map_commit_index.put(self.gpa, record.oid, self.map_commits.items.len); try self.map_commits.append(self.gpa, record); } else if (std.mem.eql(u8, kind, "ref")) { const record: MapMapping = .{ .canonical = try self.mapString(object, "canonical"), .target = try self.mapString(object, "zit"), }; try self.map_ref_index.put(self.gpa, record.canonical, self.map_refs.items.len); try self.map_refs.append(self.gpa, record); } else if (std.mem.eql(u8, kind, "tag")) { const record: MapMapping = .{ .canonical = try self.mapString(object, "canonical"), .target = try self.mapString(object, "target_zit"), }; try self.map_tag_index.put(self.gpa, record.canonical, self.map_tags.items.len); try self.map_tags.append(self.gpa, record); } else if (std.mem.eql(u8, kind, "summary")) { self.map_summary_digest = try self.mapString(object, "provenance_digest"); } } } fn mapString(self: *Verifier, object: std.json.ObjectMap, field: []const u8) Error![]const u8 { const value = stringOf(object.get(field)) orelse { return self.fail(.map_unreadable, "a record carries no '{s}'", .{field}); }; // Duped: the parse arena dies with the line. return try self.arena.dupe(u8, value); } fn mapIdentity(self: *Verifier, object: std.json.ObjectMap, field: []const u8) Error!MapIdentity { const value = object.get(field) orelse { return self.fail(.map_unreadable, "a record carries no '{s}'", .{field}); }; const inner = switch (value) { .object => |o| o, else => return self.fail(.map_unreadable, "'{s}' is not an identity", .{field}), }; return .{ .name = try self.mapString(inner, "name"), .email = try self.mapString(inner, "email"), .timestamp = integerOf(inner.get("timestamp")) orelse { return self.fail(.map_unreadable, "'{s}' carries no timestamp", .{field}); }, .timezone_offset_minutes = integerOf(inner.get("timezone_offset_minutes")) orelse { return self.fail(.map_unreadable, "'{s}' carries no timezone offset", .{field}); }, }; } // -- content helpers ---------------------------------------------------- /// The content identity of one artifact of the published generation, /// memoized by name. fn contentFacts(self: *Verifier, name: []const u8) Error!?ContentFacts { if (self.facts.get(name)) |found| return found; const bytes = (self.contentByName(self.input.packed_generation, name) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, // Every artifact in this store already reconstructed cleanly in // clause 2, so this is unreachable in practice; treating it as // absent keeps the caller's one failure path honest. else => return null, }) orelse return null; defer self.gpa.free(bytes); var facts: ContentFacts = .{ .length = bytes.len, .digest = undefined }; std.crypto.hash.sha2.Sha256.hash(bytes, &facts.digest, .{}); try self.facts.put(self.gpa, try self.arena.dupe(u8, name), facts); return facts; } fn contentByName(self: *Verifier, log: *logstore.LogStore, name: []const u8) !?[]u8 { var digest: [logstore.max_hash_len]u8 = undefined; const raw = rawName(name, &digest) orelse return null; const rid = log.lookup(raw) orelse return null; // The published generation is read by every semantic clause and is the // one whose chains packing deepened; the raw generation is read here // only on the rare deferred-difference path, so it gets no memo. const cache: ?*logstore.PlaintextCache = if (log == self.input.packed_generation) &self.packed_cache else null; return log.contentUnmasked(self.gpa, rid, cache); } /// Strict `artifact.parse`, deliberately -- not the lenient /// `parseForImport` the read path uses for fossil-origin history. What is /// being read here is an artifact THIS import wrote seconds ago through the /// canonical builder, so anything the strict reader rejects is a writer /// defect, and admitting it would publish a repository whose own writer /// cannot round-trip it. fn namesCheckin(self: *Verifier, log: *logstore.LogStore, name: []const u8) bool { const bytes = (self.contentByName(log, name) catch return false) orelse return false; defer self.gpa.free(bytes); var manifest = artifact.parse(self.gpa, bytes) catch return false; defer manifest.deinit(); return manifest.kind == .manifest; } }; fn hexName(digest: []const u8, buffer: *[hex_name_len]u8) []const u8 { return std.fmt.bufPrint(buffer, "{x}", .{digest}) catch unreachable; } fn rawName(name: []const u8, buffer: *[logstore.max_hash_len]u8) ?[]const u8 { if (name.len != 40 and name.len != 64) return null; const raw = buffer[0 .. name.len / 2]; _ = std.fmt.hexToBytes(raw, name) catch return null; return raw; } fn stringOf(value: ?std.json.Value) ?[]const u8 { return switch (value orelse return null) { .string => |text| text, else => null, }; } fn integerOf(value: ?std.json.Value) ?i64 { return switch (value orelse return null) { .integer => |number| number, else => null, }; }