//! 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,
/// Suppress the sub-manifest memo report (`--quiet`). The report is a
/// measurement, not a result, so it is the first thing a quiet run drops.
quiet: bool = false,
};
/// 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();
try self.run();
self.reportSubManifestMemo();
}
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);
}
/// Report what the sub-manifest memo actually achieved on this run.
///
/// The memo exists to collapse repeated parses of nodes that adjacent
/// check-ins share (submanifests §7.4), and its value is entirely a
/// function of how much sharing a repository has — which no benchmark can
/// stand in for, because the sharing ratio IS the variable. A corpus with
/// narrow per-commit churn shares nearly every node; a wide, heavily-touched
/// tree shares few, and the memo's bookkeeping is then paid on every miss
/// and recovered on none. Those two regimes are indistinguishable from
/// outside the process, which is why a real import that got slower could not
/// be told apart from one that got faster without re-running it for hours.
///
/// `evicted` is the load-bearing field. Zero means the whole working set
/// fit and the hit rate is the best this corpus can give. Nonzero means the
/// budget is the binding constraint: entries were dropped and later
/// re-parsed, so raising `repostate.submanifest_memo_budget` would buy hit
/// rate. That is a smooth dial now — the memo evicts by recency and keeps
/// what is hot, rather than the earlier behaviour of filling once and then
/// freezing on whatever it happened to see first.
///
/// `degraded` is separate and much rarer: an allocation failed, so an answer
/// was returned uncached. It says nothing about the budget.
/// #63 — one in-flight memo line per `memo_report_stride` commits. The
/// stride is commits rather than time so re-runs of one corpus emit an
/// identical, comparable series.
const memo_report_stride: usize = 25_000;
fn reportSubManifestMemoProgress(self: *Verifier, processed: usize) void {
if (self.input.quiet) return;
const memo = if (self.sub_memo) |*m| m else return;
const total = memo.hits + memo.misses;
if (total == 0) return;
self.err.print(
"import-git: {d} commits verified; sub-manifest memo {d}/{d} hits ({d}%), {d} KiB retained ({d} KiB budget), {d} evicted\n",
.{ processed, memo.hits, total, memo.hits * 100 / total, memo.retained / 1024, memo.budget / 1024, memo.evicted },
) catch {};
}
fn reportSubManifestMemo(self: *Verifier) void {
if (self.input.quiet) return;
const memo = if (self.sub_memo) |*m| m else return; // no tree walk ran
const total = memo.hits + memo.misses;
if (total == 0) return;
self.err.print(
"import-git: sub-manifest memo {d}/{d} hits ({d}%), {d} KiB retained, {d} evicted{s}\n",
.{
memo.hits,
total,
memo.hits * 100 / total,
memo.retained / 1024,
memo.evicted,
if (memo.degraded) " (an allocation failed; some answers uncached)" else "",
},
) catch {};
}
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.
var processed: usize = 0;
for (self.input.witness.commits) |*commit| {
processed += 1;
// #63 — the memo line every `memo_report_stride` commits, not only
// at the end: a budget-starved run (evictions climbing against a
// wide tree) is visible in minutes instead of discovered after
// hours. Same fields as the final report, so the two read as one
// series.
if (processed % memo_report_stride == 0) self.reportSubManifestMemoProgress(processed);
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,
};
}