Skip to content
zit Artifact [fa54e956da]
Login

Artifact [fa54e956da]

Check-ins Using Download Hex

Artifact fa54e956da924adb9ea94036b2163954479361cc71327f206c9cf388e1384f47:

const std = @import("std");
const builtin = @import("builtin");
const artifact = @import("artifact.zig");
const fast_export = @import("git_fast_export.zig");
const logstore = @import("logstore.zig");
const editor = @import("submanifest_editor.zig");
const control_paths = @import("control_paths.zig");
const submanifest = @import("repository.zig").submanifest;
const update = @import("update.zig");

/// Tree types at the importer seam. These alias canonical editor types; they
/// do not introduce a selectable runtime policy.
pub const TreeStore = editor.TreeStore;
pub const TreeFormat = editor.TreeFormat;
pub const RootView = editor.RootView;
pub const TreeCommand = editor.TreeCommand;
pub const BuildResult = editor.BuildResult;
pub const TreeError = editor.Error;
pub const LoadedBytes = editor.LoadedBytes;
pub const TreeStoreError = editor.StoreError;
/// Import policy deliberately has one repository-wide partition choice. The
/// translator resolves it once at initialization and never reconsiders it per
/// event or commit.
pub const Attribution = enum {
    committer,
    author,
};

/// What an import should do about draft-fossil-submanifests-00 sub-manifests.
///
/// "Analyze" and "a tree at an unspecified k" are the same request, so they are
/// one variant rather than two: `.tree = null` means "the resolver picks",
/// which is exactly what the preflight's analyzed §6.3 optimum feeds. Folding
/// them keeps the illegal fourth state -- flat AND pinned -- unrepresentable
/// everywhere past the argument parser.
pub const SubmanifestChoice = union(enum) {
    /// §8.1's default posture: never partition, so no S card and no
    /// SUBMANIFEST artifact appears anywhere in the imported history.
    flat,
    /// Emit trees. Null takes the analyzed optimum or the built-in default.
    tree: ?u4,
};

pub const UserOptions = struct {
    submanifest: SubmanifestChoice = .{ .tree = null },
    attribution: Attribution = .committer,
    tree_cache_bytes: usize = 1 << 20,
};

fn validateImportedPath(path: []const u8) !void {
    return control_paths.validateWorktreePath(path);
}

/// Import work observed at the parser/translator boundary. These counters are
/// deliberately independent of a tree implementation so opt-in benchmark
/// policies exercise exactly the same fast-export and ref finalization path.
pub const CpuClock = enum {
    thread_rusage,
    process_rusage,
};

pub const WorkCounters = struct {
    blobs: u64 = 0,
    commits: u64 = 0,
    resets: u64 = 0,
    tags: u64 = 0,
    changed_paths: u64 = 0,
    emitted_nodes: u64 = 0,
    reused_nodes: u64 = 0,
    max_tree_height: u8 = 0,
    cache_high_water_bytes: usize = 0,
    inherited_full_tree_materializations: u64 = 0,
    /// Tree entries omitted because the source names a Git submodule (Git mode
    /// 160000). Zit has no gitlink entry, so the import drops them; counting
    /// them here keeps that silent omission observable to every caller that
    /// already reads `WorkCounters`.
    skipped_submodule_entries: u64 = 0,
    tree_apply_count: u64 = 0,
    tree_apply_cpu_ns: u64 = 0,
    tree_apply_cpu_clock: CpuClock = treeApplyCpuClock(),
    /// Tree entries fed to a normalized-tree digest. One per file per commit,
    /// so this is the cost of semantic identity stated plainly rather than
    /// hidden inside import wall time.
    tree_digest_entries: u64 = 0,
    /// Entries whose content facts were not in the per-blob table and had to
    /// be read back out of the log. Zero on every import whose tree entries
    /// all came from this stream's blobs, which is every import: a nonzero
    /// count is a defect, so it is counted rather than silently absorbed.
    tree_digest_reloads: u64 = 0,
};
pub const ResolvedOptions = struct {
    /// The editor format's shape, resolved once for the whole import. Callers
    /// that need the pinned k for a config frame read it back out of `.tree`;
    /// there is deliberately no second copy of it to disagree with.
    shape: editor.TreeFormat.Shape,
    attribution: Attribution,
};

pub fn resolveOptions(options: UserOptions) !ResolvedOptions {
    const shape: editor.TreeFormat.Shape = switch (options.submanifest) {
        .flat => .flat,
        .tree => |requested| blk: {
            const k = requested orelse 5;
            if (k < artifact.min_k or k > artifact.max_k) return error.InvalidSubmanifestK;
            break :blk .{ .tree = .{
                .k = k,
                .height_max = @intCast(artifact.max_construct_height),
            } };
        },
    };
    return .{ .shape = shape, .attribution = options.attribution };
}

/// draft-fossil-submanifests-00 §6.3's analysis pass run over a NAME SET
/// alone, so an import can pin the analyzed optimum before it has read a
/// single object.
///
/// This is sound, not an approximation of the real scan: §6.1's partition
/// predicate counts leading zero bits of PH(name) — "the SHA3-256 digest of a
/// decoded filename" — so which names group together is fully determined by
/// the names. The §6.3 objective's other input is byte counts, and a hash
/// token's width is fixed by `algo`, not by what it hashes. Naming each card
/// by the digest of its own filename therefore yields the same grouping and
/// the same widths the real F-set would, with distinct tokens throughout.
///
/// `names` need not be sorted or unique — `buildTree`'s strict-canonical-order
/// precondition is established here. Returns null when the set cannot
/// partition at all (§6.2 step 2's flat outcome), which is the caller's signal
/// to keep its own default rather than invent a pin from nothing.
pub fn analyzeSubmanifestK(
    gpa: std.mem.Allocator,
    names: []const []const u8,
    algo: artifact.HashAlgo,
) std.mem.Allocator.Error!?u4 {
    if (names.len < 2) return null;

    const sorted = try gpa.dupe([]const u8, names);
    defer gpa.free(sorted);
    std.mem.sort([]const u8, sorted, {}, struct {
        fn less(_: void, a: []const u8, b: []const u8) bool {
            return artifact.compareBytes(a, b) == .lt;
        }
    }.less);

    // One arena for the whole scan: the synthetic cards and their hash tokens
    // live exactly as long as the twelve `cost` calls that read them.
    var arena_state = std.heap.ArenaAllocator.init(gpa);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    var entries: std.ArrayList(artifact.FCard) = .empty;
    try entries.ensureTotalCapacity(arena, sorted.len);
    var previous: ?[]const u8 = null;
    for (sorted) |name| {
        if (previous) |last| if (artifact.compareBytes(last, name) != .lt) continue;
        previous = name;
        var hash_buf: [64]u8 = undefined;
        const hash = artifact.artifactName(algo, name, &hash_buf);
        entries.appendAssumeCapacity(.{
            .filename = name,
            .hash = try arena.dupe(u8, hash),
            .perm = null,
            .old_name = null,
            .mode = .regular,
        });
    }
    if (entries.items.len < 2) return null;

    var costs: [artifact.max_k - artifact.min_k + 1]submanifest.Cost = undefined;
    var n: usize = 0;
    var k: u4 = artifact.min_k;
    while (true) : (k += 1) {
        costs[n] = try submanifest.cost(gpa, entries.items, k, algo);
        n += 1;
        if (k == artifact.max_k) break;
    }
    const winner = submanifest.best(costs[0..n]) orelse return null;
    return winner.k;
}

/// Classifies a raw Git tree-entry mode. Mode 160000 is reported as `.gitlink`
/// rather than refused: whether a submodule stops an import is import policy,
/// which lives in the translator, not in mode classification.
pub fn modeFromGit(mode: u32) !fast_export.FileMode {
    return switch (mode) {
        0o100644 => .regular,
        0o100755 => .executable,
        0o120000 => .symlink,
        0o160000 => .gitlink,
        else => error.UnknownMode,
    };
}

const RusageSelector = enum(i32) {
    self = 0,
    thread = 1,
};

/// Linux supports `RUSAGE_THREAD`; all other targets use the portable
/// process selector so a benchmark never passes an unsupported rusage value.
pub fn treeApplyCpuClock() CpuClock {
    return if (builtin.os.tag == .linux) .thread_rusage else .process_rusage;
}

fn treeApplyCpuNs() u64 {
    return rusageCpuNs(treeApplyCpuClock());
}

fn rusageCpuNs(clock: CpuClock) u64 {
    const selector: RusageSelector = switch (clock) {
        .thread_rusage => .thread,
        .process_rusage => .self,
    };
    const usage = std.posix.getrusage(@intFromEnum(selector));
    const seconds: u64 = @intCast(usage.utime.sec + usage.stime.sec);
    const micros: u64 = @intCast(usage.utime.usec + usage.stime.usec);
    return seconds * std.time.ns_per_s + micros * std.time.ns_per_us;
}

/// Commit references retain their exact immutable importer object position,
/// rather than inferring identity from a deduplicated Zit check-in hash.
pub const CommitMarkState = struct {
    checkin_hash: []u8,
    object_index: usize,
};

const ObjectKind = enum { blob, commit };

const MarkState = union(enum) {
    blob: []u8,
    commit: CommitMarkState,
    tagged: []u8,

    fn hash(self: *const MarkState) []const u8 {
        return switch (self.*) {
            .blob, .tagged => |artifact_hash| artifact_hash,
            .commit => |state| state.checkin_hash,
        };
    }
};

const OidState = struct {
    kind: ObjectKind,
    hash: []u8,
    object_index: ?usize = null,
};

/// `BuildResult.root` viewed as a parent. The two unions are structurally
/// identical and deliberately distinct types -- one is "what a build produced",
/// the other "what a build reads" -- so the conversion is spelled out at the
/// one seam that needs to read back a tree it just wrote.
fn rootViewOf(root: editor.RootRun) editor.RootView {
    return switch (root) {
        .flat => |cards| .{ .flat = cards },
        .tree => |cards| .{ .tree = cards },
    };
}

const ParentRoot = struct {
    bytes: []u8,
    manifest: artifact.Manifest,

    fn deinit(self: *ParentRoot, gpa: std.mem.Allocator) void {
        self.manifest.deinit();
        gpa.free(self.bytes);
        self.* = undefined;
    }

    fn view(self: *const ParentRoot) editor.RootView {
        if (self.manifest.s.len != 0) return .{ .tree = self.manifest.s };
        return .{ .flat = self.manifest.f };
    }
};

const CommitFlushObservation = struct {
    serialized_f_cards: u64,
    staged_artifact_bytes: u64,
};

const StagedNode = struct {
    name: []u8,
    bytes: []u8,
};

const StagingStore = struct {
    gpa: std.mem.Allocator,
    base: editor.TreeStore,
    nodes: std.ArrayList(StagedNode) = .empty,

    fn init(gpa: std.mem.Allocator, base: editor.TreeStore) StagingStore {
        return .{ .gpa = gpa, .base = base };
    }

    fn deinit(self: *StagingStore) void {
        for (self.nodes.items) |node| {
            self.gpa.free(node.name);
            self.gpa.free(node.bytes);
        }
        self.nodes.deinit(self.gpa);
        self.* = undefined;
    }

    fn treeStore(self: *StagingStore) editor.TreeStore {
        return .{ .ctx = self, .load_fn = load, .put_fn = put, .put_batch_fn = putBatch };
    }

    fn load(ctx: *anyopaque, allocator: std.mem.Allocator, name: []const u8) editor.StoreError!editor.LoadedBytes {
        const self: *StagingStore = @ptrCast(@alignCast(ctx));
        for (self.nodes.items) |node| {
            if (!std.mem.eql(u8, node.name, name)) continue;
            const bytes = allocator.dupe(u8, node.bytes) catch return error.OutOfMemory;
            return .{ .bytes = bytes, .allocator = allocator };
        }
        return self.base.load_fn(self.base.ctx, allocator, name);
    }

    fn put(ctx: *anyopaque, name: []const u8, bytes: []const u8) editor.StoreError!void {
        const self: *StagingStore = @ptrCast(@alignCast(ctx));
        for (self.nodes.items) |node| {
            if (!std.mem.eql(u8, node.name, name)) continue;
            if (!std.mem.eql(u8, node.bytes, bytes)) return error.StorageFailure;
            return;
        }
        var name_buf: [64]u8 = undefined;
        if (!std.mem.eql(u8, name, artifact.artifactName(.sha1, bytes, &name_buf))) return error.StorageFailure;
        try self.nodes.ensureUnusedCapacity(self.gpa, 1);
        const owned_name = self.gpa.dupe(u8, name) catch return error.OutOfMemory;
        errdefer self.gpa.free(owned_name);
        const owned_bytes = self.gpa.dupe(u8, bytes) catch return error.OutOfMemory;
        self.nodes.appendAssumeCapacity(.{ .name = owned_name, .bytes = owned_bytes });
    }

    fn putBatch(ctx: *anyopaque, nodes: []const editor.StoreBatchNode) editor.StoreError!void {
        const self: *StagingStore = @ptrCast(@alignCast(ctx));
        for (nodes) |node| try put(self, node.name, node.bytes);
    }

    fn observation(self: *const StagingStore, checkin_bytes: []const u8) !CommitFlushObservation {
        var flush_observation = CommitFlushObservation{
            .serialized_f_cards = try serializedFCardCount(self.gpa, checkin_bytes),
            .staged_artifact_bytes = @intCast(checkin_bytes.len),
        };
        for (self.nodes.items) |node| {
            var existing = self.base.load_fn(self.base.ctx, self.gpa, node.name) catch |err| switch (err) {
                error.MissingNode => {
                    flush_observation.serialized_f_cards = std.math.add(u64, flush_observation.serialized_f_cards, try serializedFCardCount(self.gpa, node.bytes)) catch return error.Overflow;
                    flush_observation.staged_artifact_bytes = std.math.add(u64, flush_observation.staged_artifact_bytes, @intCast(node.bytes.len)) catch return error.Overflow;
                    continue;
                },
                else => return err,
            };
            defer existing.deinit();
            if (!std.mem.eql(u8, existing.bytes, node.bytes)) return error.StorageFailure;
        }
        return flush_observation;
    }

    fn flush(
        self: *const StagingStore,
        checkin_name: []const u8,
        checkin_bytes: []const u8,
    ) editor.StoreError!void {
        var batch: std.ArrayList(editor.StoreBatchNode) = .empty;
        defer batch.deinit(self.gpa);
        try batch.ensureTotalCapacity(self.gpa, self.nodes.items.len + 1);
        for (self.nodes.items) |node| {
            batch.appendAssumeCapacity(.{ .name = node.name, .bytes = node.bytes });
        }
        batch.appendAssumeCapacity(.{ .name = checkin_name, .bytes = checkin_bytes });
        try self.base.put_batch_fn(self.base.ctx, batch.items);
    }
};

fn serializedFCardCount(gpa: std.mem.Allocator, bytes: []const u8) !u64 {
    var manifest = try artifact.parse(gpa, bytes);
    defer manifest.deinit();
    return @intCast(manifest.f.len);
}

const OwnedIdentity = struct {
    name: []u8,
    email: []u8,
    timestamp: i64,
    timezone_offset_minutes: i16,

    fn deinit(self: *OwnedIdentity, gpa: std.mem.Allocator) void {
        gpa.free(self.name);
        gpa.free(self.email);
        self.* = undefined;
    }
};

/// One imported check-in, kept in stream order so that a commit's first parent
/// always precedes it.
///
/// The `commit <ref>` header the export stream carried is deliberately NOT
/// recorded here. `git fast-export` emits every commit exactly once, attributed
/// to whichever ref's traversal reached it first, so that header answers "which
/// ref was the stream emitting under" and never "which branch is this commit
/// on". Reading it as a branch is ISSUE #26: it left a plain single-branch
/// repository importing with no branches at all, and could scramble the
/// topology of any repository with more than one head — how badly depended on
/// the order fast-export's traversal happened to reach them in. Branch identity
/// is decided from the commit graph by `labelBranches`; the ref a commit
/// arrived under is not an input to anything.
const ImportedObject = struct {
    oid: ?[]u8,
    hash: []u8,
    first_parent_index: ?usize,
    tree_height: u8,
    is_merge: bool,
    /// This commit's ordered parent check-in names -- exactly the run the P
    /// card carries -- and their Git OIDs in the same order, an absent OID
    /// recorded as the empty string so the two runs stay index-aligned.
    ///
    /// Recorded rather than re-read from the stored check-in for the same
    /// reason `tree_digest` is: the verification pass that needs them compares
    /// them AGAINST that check-in, and a value derived from the thing under
    /// test proves nothing about it. Both outer slices are owned; every string
    /// inside borrows an earlier object's `hash` or `oid`, which this importer
    /// keeps alive at least as long as this record.
    parents: [][]const u8,
    parent_oids: [][]const u8,
    author: OwnedIdentity,
    committer: OwnedIdentity,
    /// This commit's Fossil-mirror candidate state, inherited by its children
    /// through `first_parent_index`. Carried here for the same reason
    /// `tree_height` is: it is a per-commit fact a descendant needs and cannot
    /// recompute from the stream alone.
    mirror: MirrorState,
    /// This commit's emitted file set, digested. Recorded rather than
    /// recomputed on demand because the S nodes it covers live in a
    /// commit-local staging store that is gone by the time anyone asks.
    tree_digest: Digest,
    /// This commit's Git identity, mapping and mirror decision, digested.
    provenance_digest: Digest,
    decision: MirrorDecisionKind,
    /// Meaningful only when `decision` is `.retained`.
    retain_reason: MirrorRetainReason,

    fn deinit(self: *ImportedObject, gpa: std.mem.Allocator) void {
        if (self.oid) |oid| gpa.free(oid);
        gpa.free(self.hash);
        gpa.free(self.parents);
        gpa.free(self.parent_oids);
        self.author.deinit(gpa);
        self.committer.deinit(gpa);
        self.mirror.deinit(gpa);
        self.* = undefined;
    }
};
/// What one distinct blob's payload is, recorded once at ingestion.
///
/// Three facts, none of which can be recovered later without rereading the
/// payload out of the log — which is the reread every consumer of this table
/// exists to avoid.
const BlobFacts = struct {
    /// The content digest under the supported artifact algorithm this import
    /// does NOT name blobs with. Between the key and this, the classifier can
    /// prove content identity against a mirror under either Fossil hash policy
    /// -- wapp's mirror is SHA3-256, so without it every commit would retain.
    alternate: [32]u8,
    /// The payload's SHA-256, the normalized-tree digest's content identity.
    /// Deliberately a third algorithm: the digest must not change meaning when
    /// the import's artifact-naming algorithm does.
    content: Digest,
    length: u64,
    /// The Git blob OID the stream carried, borrowed from the blob record that
    /// first named this content. Null when the export carried no original IDs.
    oid: ?[]const u8,
};

const ImportedBlob = struct {
    oid: ?[]u8,
    hash: []u8,

    fn deinit(self: *ImportedBlob, gpa: std.mem.Allocator) void {
        if (self.oid) |oid| gpa.free(oid);
        gpa.free(self.hash);
        self.* = undefined;
    }
};

// ---------------------------------------------------------------------------
// Fossil Git-mirror metadata classification
// ---------------------------------------------------------------------------
//
// A repository mirrored out of Fossil with `fossil git export` carries root
// files that are not project content: `manifest` is the check-in artifact
// itself, `manifest.uuid` is its name, `manifest.tags` is its branch/tag
// summary. Which of the three appear is the source repository's `manifest`
// SETTING, so any subset may be present and none of them is guaranteed --
// there is no fixed pair.
//
// Importing a mirror stores all of it: on the wapp corpus that is 252 distinct
// `manifest` blobs across 252 commits, one per commit and never shared, for a
// project whose native history tracks no file named `manifest` at all. The
// classifier proves, per commit and cryptographically, that those bytes are
// reconstructible from what the import already holds, so packing may drop them.
//
// It fails closed in both directions. Any invalid, unreadable or inconclusive
// signal retains EVERY present candidate, and no outcome ever omits a strict
// subset of them -- so a genuine top-level project file named `manifest`
// cannot be dropped by accident, and half a mirror's metadata can never be
// dropped either.

/// The exact root filenames a Fossil→Git mirror injects, in the order
/// `checkout.manifest_selectors` names them. Borrowed from `update` rather
/// than retyped: the set this may drop must be exactly the set `zit update`
/// writes.
pub const mirror_candidate_names = update.manifest_paths;

/// The line fossil appends to the exported `manifest`. Stripping it is what
/// makes `manifest.uuid` verifiable: with the line in place the exported file
/// hashes to nothing the mirror names, so no commit could ever validate.
pub const mirror_sterilizer = update.sterilizer;

const candidate_manifest = 0;
const candidate_uuid = 1;
const candidate_tags = 2;

/// The index of `path` in `mirror_candidate_names`, or null. Only an exact
/// root name is a candidate: `dir/manifest` and `Manifest` are ordinary files.
fn mirrorCandidateIndex(path: []const u8) ?usize {
    for (mirror_candidate_names, 0..) |name, index| {
        if (std.mem.eql(u8, name, path)) return index;
    }
    return null;
}

/// The perm token `treeCommand` writes for `mode`, so a restored candidate is
/// byte-identical to the entry the ordinary translation would have produced.
fn mirrorPerm(mode: artifact.FileMode) ?[]const u8 {
    return switch (mode) {
        .regular => null,
        .executable => "x",
        .symlink => "l",
    };
}

/// One candidate root file's Git truth at one commit, borrowed for the length
/// of that commit's translation.
const MirrorEntry = struct {
    hash: []const u8,
    mode: artifact.FileMode,
};

/// The same fact, owned, so it can be inherited by later commits.
const OwnedMirrorEntry = struct {
    hash: []u8,
    mode: artifact.FileMode,
};

/// What the three candidate root paths held at one imported commit, and what
/// this import decided about them.
///
/// Inherited along first-parent links because a mirror re-exports only the
/// files a commit changed: a commit that never mentions `manifest.tags` still
/// has it in its Git tree -- on wapp, 243 of 252 commits inherit the same
/// trunk blob -- and a classifier blind to that would compare an incomplete
/// tree against the mirror's own F cards and retain on every commit.
const MirrorState = struct {
    entries: [3]?OwnedMirrorEntry = .{ null, null, null },
    /// True when the emitted tree omits EVERY present entry. Never partially
    /// true: the decision is all-or-nothing.
    omitted: bool = false,
    /// The mirror's own Fossil check-in UUID, proven against this commit's
    /// tree, ordered parents and committer instant. Non-null only when
    /// `omitted`, so a retained or unproven parent cannot satisfy a child's
    /// P-card gate -- "not yet proven" and "disproven" are both inconclusive.
    validated_uuid: ?[]u8 = null,

    fn deinit(self: *MirrorState, gpa: std.mem.Allocator) void {
        for (self.entries) |slot| if (slot) |entry| gpa.free(entry.hash);
        if (self.validated_uuid) |uuid| gpa.free(uuid);
        self.* = undefined;
    }
};

const empty_mirror_state: MirrorState = .{};

/// Why a commit's mirror candidates were retained. Bounded and exhaustive:
/// every non-omission names a reason, because "it did not work" is not
/// something an operator inspecting a mirror import can act on.
pub const MirrorRetainReason = enum {
    /// The commit's tree holds none of the three candidate names.
    no_candidates,
    /// `manifest` or `manifest.uuid` is absent. `manifest.tags` is a dependent
    /// member: it is never dropped on its own.
    incomplete_pair,
    /// A rename or copy moved content into or out of a candidate path, so the
    /// commit's Git truth for that path is not reconstructible from the
    /// inherited state alone.
    unsupported_command,
    /// A candidate is executable, a symlink, or otherwise not an ordinary file.
    non_regular_mode,
    /// `manifest.uuid` is not exactly one canonical lowercase artifact name.
    uuid_syntax,
    /// The name in `manifest.uuid` does not hash the sterilized `manifest`.
    uuid_mismatch,
    /// A candidate blob could not be read back out of the log.
    candidate_unreadable,
    /// The sterilized `manifest` is not a parseable artifact.
    manifest_parse,
    /// It parses, but is not a complete flat check-in: a delta baseline, an
    /// S-bearing tree, or another artifact type entirely.
    manifest_shape,
    /// Its F-card set is not the commit's tree with the candidates removed.
    tree_mismatch,
    /// Its P cards are not the proven UUIDs of the ordered Git parents.
    parent_unproven,
    /// Its D card is not the Git committer instant at whole-second precision.
    timestamp_mismatch,
    /// `manifest.tags` is present but is not fossil's branch/tag file.
    tags_malformed,
};

const mirror_retain_reason_count = @typeInfo(MirrorRetainReason).@"enum".fields.len;

/// Per-import mirror census. Reported rather than logged so a caller can
/// decide whether a zero validated count on a real mirror is expected (a
/// repository with `manifest=off`) or the symptom of a broken gate.
pub const MirrorCensus = struct {
    commits_with_candidates: u64 = 0,
    commits_validated: u64 = 0,
    commits_retained: u64 = 0,
    f_cards_compared: u64 = 0,
    /// An F-card hash answered by comparing artifact names, which is possible
    /// only when the mirror's hash policy is this import's. No table is
    /// consulted on this path, so it is counted apart from the cache.
    name_comparisons: u64 = 0,
    /// A tree entry whose F-card hash was answered out of the per-blob digest
    /// table, because the mirror's hash policy is the other one. A miss on an
    /// already ingested blob is a defect, not a licence to reread it, so both
    /// are counted and both are visible.
    digest_cache_hits: u64 = 0,
    digest_cache_misses: u64 = 0,
    /// Distinct artifact names that were the content of an omitted candidate.
    candidate_artifacts: u64 = 0,
    retained_by_reason: [mirror_retain_reason_count]u64 = @splat(0),

    pub fn reason(self: *const MirrorCensus, which: MirrorRetainReason) u64 {
        return self.retained_by_reason[@intFromEnum(which)];
    }
};

/// Per-commit candidate bookkeeping, threaded through command translation.
const MirrorTrack = struct {
    /// The three paths' content after this commit's commands, in Git truth --
    /// whether or not the emitted tree will carry them.
    shadow: [3]?MirrorEntry,
    /// Whether any candidate path is in play at all. False for the whole of an
    /// ordinary import, which is what keeps every non-mirror repository on
    /// exactly the pre-existing single-apply path.
    active: bool,
    /// A rename or copy touched a candidate path. Such a commit is retained
    /// and its Git truth is re-read from the emitted tree instead.
    unsupported: bool = false,

    fn init(parent: *const MirrorState) MirrorTrack {
        var self = MirrorTrack{ .shadow = .{ null, null, null }, .active = false };
        for (parent.entries, 0..) |slot, index| {
            const entry = slot orelse continue;
            self.shadow[index] = .{ .hash = entry.hash, .mode = entry.mode };
            self.active = true;
        }
        return self;
    }

    /// Records `command`'s effect on the candidate paths and answers whether
    /// it belongs in the candidate-free command list the classifier applies.
    fn observe(self: *MirrorTrack, command: editor.TreeCommand) bool {
        switch (command) {
            .upsert => |card| {
                const index = mirrorCandidateIndex(card.filename) orelse return true;
                self.active = true;
                self.shadow[index] = .{ .hash = card.hash.?, .mode = card.mode };
                return false;
            },
            .delete => |path| {
                const index = mirrorCandidateIndex(path) orelse return true;
                self.active = true;
                self.shadow[index] = null;
                return false;
            },
            // A rename or copy across the candidate boundary carries content
            // whose provenance this bookkeeping does not model. Rather than
            // guess, the commit is retained and its state re-read from the
            // tree it actually emitted, which is the full Git tree.
            .rename => |names| {
                if (mirrorCandidateIndex(names.old) == null and
                    mirrorCandidateIndex(names.new) == null) return true;
                self.active = true;
                self.unsupported = true;
                return true;
            },
            .copy => |names| {
                if (mirrorCandidateIndex(names.old) == null and
                    mirrorCandidateIndex(names.new) == null) return true;
                self.active = true;
                self.unsupported = true;
                return true;
            },
            .delete_all => {
                self.shadow = .{ null, null, null };
                return true;
            },
        }
    }

    fn pairPresent(self: *const MirrorTrack) bool {
        return self.shadow[candidate_manifest] != null and self.shadow[candidate_uuid] != null;
    }

    /// Whether Git truth holds any candidate at all after this commit's
    /// commands. A commit that deleted all three has no incomplete pair -- it
    /// has no candidates, and the two are different facts to report.
    fn anyPresent(self: *const MirrorTrack) bool {
        for (self.shadow) |slot| {
            if (slot != null) return true;
        }
        return false;
    }

    /// Git truth for a candidate path: whether the tree Git describes holds a
    /// file there right now. `omitSubmodule` needs this rather than a lookup
    /// in the emitted tree, which a validated parent deliberately left the
    /// candidates out of.
    fn present(self: *const MirrorTrack, index: usize) bool {
        return self.shadow[index] != null;
    }
};

/// One commit's classification outcome. `reason` is meaningful only when
/// `omit` is false; `uuid` is owned and non-null only when it is true.
const MirrorDecision = struct {
    omit: bool = false,
    reason: MirrorRetainReason = .no_candidates,
    uuid: ?[]u8 = null,

    fn retain(why: MirrorRetainReason) MirrorDecision {
        return .{ .omit = false, .reason = why };
    }

    fn deinit(self: *MirrorDecision, gpa: std.mem.Allocator) void {
        if (self.uuid) |uuid| gpa.free(uuid);
        self.* = undefined;
    }
};

/// Resolves S-card references against a commit-local staging store, so a
/// just-built tree root can be flattened before any of it reaches the log.
/// `repository.submanifest.flattenTreeFromLog` cannot serve here: at
/// classification time the S nodes exist only in the staging store.
const StagedSubResolver = struct {
    gpa: std.mem.Allocator,
    staged: *StagingStore,
    loaded: std.ArrayList(LoadedSub) = .empty,
    /// The first error a resolution failed with. §5.2 gives the resolver only
    /// "resolved" and "absent" to answer with, so without this an allocation
    /// failure reads to the caller exactly like a tree that does not resolve
    /// -- and gets reported as a malformed tree rather than as OOM.
    failure: ?anyerror = null,

    const LoadedSub = struct {
        bytes: editor.LoadedBytes,
        manifest: artifact.Manifest,
    };

    fn deinit(self: *StagedSubResolver) void {
        for (self.loaded.items) |*item| {
            item.manifest.deinit();
            item.bytes.deinit();
        }
        self.loaded.deinit(self.gpa);
        self.* = undefined;
    }

    fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
        const self: *StagedSubResolver = @ptrCast(@alignCast(ctx));
        var bytes = StagingStore.load(self.staged, self.gpa, hash) catch |err| {
            self.failure = self.failure orelse err;
            return null;
        };
        var manifest = artifact.parse(self.gpa, bytes.bytes) catch |err| {
            self.failure = self.failure orelse err;
            bytes.deinit();
            return null;
        };
        // draft-fossil-submanifests-00 §5.2 collapses "absent" and "present but
        // not a SUBMANIFEST" into one fatal outcome; null is that outcome.
        if (manifest.kind != .submanifest) {
            manifest.deinit();
            bytes.deinit();
            return null;
        }
        self.loaded.append(self.gpa, .{ .bytes = bytes, .manifest = manifest }) catch |err| {
            self.failure = self.failure orelse err;
            manifest.deinit();
            bytes.deinit();
            return null;
        };
        const item = &self.loaded.items[self.loaded.items.len - 1];
        return .{ .files = item.manifest.f, .subs = item.manifest.s };
    }
};

/// A bare S-bearing `Manifest` whose only purpose is to be flattened. Built
/// here rather than in `artifact` because nothing else needs a manifest with
/// no cards: this is a walk over `subs`, expressed through the ordinary §5.1
/// enumeration seam so it cannot diverge from what readers see.
fn treeWalkShell(gpa: std.mem.Allocator, subs: []const artifact.SCard) artifact.Manifest {
    return .{
        .arena_state = std.heap.ArenaAllocator.init(gpa),
        .kind = .manifest,
        .a = null,
        .b = null,
        .c = null,
        .d = null,
        .e = null,
        .g = null,
        .h = null,
        .i = null,
        .k = null,
        .l = null,
        .n = null,
        .r = null,
        .u = null,
        .z = null,
        .w = null,
        .f = &.{},
        .j = &.{},
        .m = &.{},
        .p = &.{},
        .q = &.{},
        .s = subs,
        .t = &.{},
    };
}

/// Whether a Fossil D card names the same whole second as the Git committer
/// instant. Fossil records sub-second precision Git cannot carry, so the
/// fractional part is dropped -- but only after it is proven to BE a
/// fractional part, so trailing text is a mismatch rather than junk ignored.
fn mirrorTimestampMatches(actual: []const u8, expected: []const u8) bool {
    std.debug.assert(expected.len == 19);
    if (actual.len < 19) return false;
    if (!std.mem.eql(u8, actual[0..19], expected)) return false;
    if (actual.len == 19) return true;
    if (actual[19] != '.') return false;
    if (actual.len == 20) return false;
    for (actual[20..]) |byte| {
        if (byte < '0' or byte > '9') return false;
    }
    return true;
}

/// One LF-terminated line, or null once `rest` is exhausted. A final line
/// missing its LF is not a line: fossil's file always ends in one, and
/// accepting a truncated tail would let a mangled blob pass the grammar.
fn nextTagLine(rest: *[]const u8) ?[]const u8 {
    if (rest.len == 0) return null;
    const lf = std.mem.indexOfScalar(u8, rest.*, '\n') orelse return null;
    const line = rest.*[0..lf];
    rest.* = rest.*[lf + 1 ..];
    return line;
}

/// Whether a `manifest.tags` blob is exactly what fossil writes for a
/// check-in, and what `update.deriveTargetFacts` reproduces: `branch <name>LF`
/// then one or more `tag <name>LF`. Anything else -- no branch line, no tag
/// line, an unknown keyword, a bare name, trailing bytes -- is not fossil's
/// file and therefore not provably redundant.
fn mirrorTagsGrammar(bytes: []const u8) bool {
    var rest = bytes;
    const branch = nextTagLine(&rest) orelse return false;
    if (!std.mem.startsWith(u8, branch, "branch ")) return false;
    if (branch.len == "branch ".len) return false;
    var tags: usize = 0;
    while (nextTagLine(&rest)) |line| {
        if (!std.mem.startsWith(u8, line, "tag ")) return false;
        if (line.len == "tag ".len) return false;
        tags += 1;
    }
    return tags != 0 and rest.len == 0;
}

/// `bytes` without fossil's sterilizing line, or `bytes` unchanged when it is
/// absent. Present-or-absent is accepted; a partial or repositioned line is
/// not, and simply fails the hash gate that follows.
fn stripMirrorSterilizer(bytes: []const u8) []const u8 {
    if (!std.mem.endsWith(u8, bytes, mirror_sterilizer)) return bytes;
    return bytes[0 .. bytes.len - mirror_sterilizer.len];
}

/// The supported artifact algorithm that is NOT `named_by`. A Zit artifact
/// name already IS the digest under `named_by`, so between the name and this
/// one digest a mirror under either Fossil hash policy can be answered.
fn alternateAlgo(named_by: artifact.HashAlgo) artifact.HashAlgo {
    return switch (named_by) {
        .sha1 => .sha3_256,
        .sha3_256 => .sha1,
    };
}

/// Hex width of `alternateAlgo(named_by)`'s digest.
fn alternateDigestLen(named_by: artifact.HashAlgo) usize {
    return switch (alternateAlgo(named_by)) {
        .sha1 => 20,
        .sha3_256 => 32,
    };
}

/// `content`'s digest under `alternateAlgo(named_by)`, left-aligned in `out`.
fn alternateContentDigest(named_by: artifact.HashAlgo, content: []const u8, out: *[32]u8) void {
    switch (alternateAlgo(named_by)) {
        .sha1 => {
            var digest: [20]u8 = undefined;
            std.crypto.hash.Sha1.hash(content, &digest, .{});
            @memcpy(out[0..digest.len], &digest);
        },
        .sha3_256 => std.crypto.hash.sha3.Sha3_256.hash(content, out, .{}),
    }
}

/// `bytes` without its single canonical trailing LF. Exactly one is removed:
/// a second LF leaves an empty final token, which `validateName` rejects.
fn trimSingleTrailingLf(bytes: []const u8) []const u8 {
    if (bytes.len == 0 or bytes[bytes.len - 1] != '\n') return bytes;
    return bytes[0 .. bytes.len - 1];
}

// ---------------------------------------------------------------------------
// Semantic import digests
// ---------------------------------------------------------------------------
//
// Two domain-separated SHA-256 values give an import a semantic identity that
// survives repacking. A Zit check-in hash cannot: it covers the comment, the
// login, the D card, the S-card partition and the parent hashes, so a flat
// import and a tree import of the same Git commit have different check-in
// names while being the same tree. These digests answer "is this the same
// content at the same paths" and "is this the same Git history, mapped the
// same way", which is exactly what the packed generation must be verified
// against.
//
// SHA-256 is neither of Zit's artifact-naming algorithms and is not used to
// name anything. It is an importer/verifier field: no artifact card carries
// it, no log frame carries it, and nothing on the sync wire changes.
//
// Every variable-length field is prefixed with its length as an unsigned
// 64-bit big-endian integer, so no concatenation of two field sets can
// produce the same byte stream as a third.

pub const Digest = [32]u8;

pub const tree_digest_domain = "zit-import-git-tree-v1\x00";
pub const provenance_digest_domain = "zit-import-git-provenance-v1\x00";

/// Which provenance scope a digest covers. One domain with an explicit scope
/// rather than two domains: the design names a single provenance domain, and
/// a per-commit record and the repository chain must still be impossible to
/// confuse for one another.
const provenance_scope_commit: u8 = 1;
const provenance_scope_repository: u8 = 2;

/// A length-framed SHA-256 absorber. Copyable by value, which is what lets
/// `finalizeRefs` finish the repository chain twice and get the same answer
/// both times without disturbing the running import.
const DigestWriter = struct {
    hasher: std.crypto.hash.sha2.Sha256,

    fn init(domain: []const u8) DigestWriter {
        var self = DigestWriter{ .hasher = std.crypto.hash.sha2.Sha256.init(.{}) };
        self.hasher.update(domain);
        return self;
    }

    fn byte(self: *DigestWriter, value: u8) void {
        self.hasher.update(&[_]u8{value});
    }

    /// A bare unsigned 64-bit big-endian value: a count, or a framed field's
    /// own length.
    fn number(self: *DigestWriter, value: u64) void {
        var buffer: [8]u8 = undefined;
        std.mem.writeInt(u64, &buffer, value, .big);
        self.hasher.update(&buffer);
    }

    /// A signed value in the same width, two's complement. Timestamps and
    /// timezone offsets are signed and both directions occur in real streams.
    fn signed(self: *DigestWriter, value: i64) void {
        self.number(@bitCast(value));
    }

    fn field(self: *DigestWriter, bytes: []const u8) void {
        self.number(bytes.len);
        self.hasher.update(bytes);
    }

    /// A fixed-width value that needs no frame because its width is pinned by
    /// the schema at this position.
    fn fixed(self: *DigestWriter, bytes: []const u8) void {
        self.hasher.update(bytes);
    }

    fn identity(self: *DigestWriter, value: OwnedIdentity) void {
        self.field(value.name);
        self.field(value.email);
        self.signed(value.timestamp);
        self.signed(value.timezone_offset_minutes);
    }

    fn final(self: *DigestWriter) Digest {
        var out: Digest = undefined;
        var copy = self.hasher;
        copy.final(&out);
        return out;
    }
};

/// The one-byte permission encoding the normalized-tree digest uses. Fixed by
/// the digest schema rather than by `artifact.FileMode`'s tag values, so a
/// later reordering of that enum cannot silently change every digest.
fn treePermissionByte(mode: artifact.FileMode) u8 {
    return switch (mode) {
        .regular => 0,
        .executable => 1,
        .symlink => 2,
    };
}

pub fn formatDigest(digest: Digest, out: *[64]u8) []const u8 {
    return std.fmt.bufPrint(out, "{x}", .{digest[0..]}) catch unreachable;
}

/// The Git object format a 40- or 64-hex OID belongs to. Empty when the
/// stream carried no original ID at all, which is a different fact from
/// "SHA-1" and must not digest the same.
fn gitObjectFormat(oid: []const u8) []const u8 {
    return switch (oid.len) {
        40 => "sha1",
        64 => "sha256",
        else => "",
    };
}

/// The normalized-tree digest, absorbed one entry at a time.
///
/// Public because the packed-generation verifier recomputes the same digest
/// from a store rather than from importer state. Two implementations of one
/// digest schema is exactly the drift a verifier must not have: a verifier
/// that agrees with a second copy of the producer's bug proves nothing.
pub const TreeDigestBuilder = struct {
    writer: DigestWriter,
    previous: ?[]const u8 = null,

    pub fn init() TreeDigestBuilder {
        return .{ .writer = DigestWriter.init(tree_digest_domain) };
    }

    /// One entry. Canonical path order is the caller's contract and is
    /// asserted here: the digest is a set identity, not a listing order, and
    /// an out-of-order feed would silently make it neither. `path` need not
    /// outlive the call beyond the next one.
    pub fn entry(
        self: *TreeDigestBuilder,
        path: []const u8,
        mode: artifact.FileMode,
        length: u64,
        content: Digest,
    ) void {
        if (self.previous) |last| std.debug.assert(artifact.compareBytes(last, path) == .lt);
        self.previous = path;
        self.writer.field(path);
        self.writer.byte(treePermissionByte(mode));
        self.writer.number(length);
        self.writer.fixed(&content);
    }

    pub fn final(self: *TreeDigestBuilder) Digest {
        return self.writer.final();
    }
};

/// One present mirror candidate, as the provenance digest covers it.
pub const ProvenanceCandidate = struct {
    path: []const u8,
    name: []const u8,
    /// The empty string when the stream carried no OID for the content, which
    /// is a different fact from "no candidate" and digests differently.
    oid: []const u8,
};

/// Everything one commit's provenance digest is taken over, as plain values.
///
/// Split out from the importer so the digest has exactly one implementation
/// that both the import and the pre-publication verifier call. The verifier
/// reaches it holding a captured witness rather than live importer state, so
/// nothing here may be a method on the importer.
pub const ProvenanceInputs = struct {
    /// The empty string when the stream carried no original ID.
    oid: []const u8,
    /// Ordered, first parent first; an unknown parent contributes "".
    parent_oids: []const []const u8,
    attribution: []const u8,
    identity_name: []const u8,
    identity_email: []const u8,
    identity_timestamp: i64,
    identity_zone_minutes: i64,
    tree_digest: Digest,
    decision: []const u8,
    /// The empty string for any decision but a retention.
    reason: []const u8,
    candidates: []const ProvenanceCandidate,
    checkin: []const u8,
};

/// One commit's provenance digest: its Git identity and ordered parents, the
/// attribution the import selected, its normalized tree, its mirror decision
/// with the OIDs that decision was about, and the Zit check-in it became.
///
/// The check-in name alone would not do. Two imports of the same commit under
/// different `--attribution` or different root shapes produce different
/// check-in names for identical Git history, and an import that wrongly
/// dropped a mirror candidate would produce a perfectly self-consistent
/// check-in. This covers the mapping, not just its result.
pub fn provenanceDigestOf(inputs: ProvenanceInputs) Digest {
    var writer = DigestWriter.init(provenance_digest_domain);
    writer.byte(provenance_scope_commit);
    writer.field(inputs.oid);
    writer.field(gitObjectFormat(inputs.oid));

    writer.number(inputs.parent_oids.len);
    for (inputs.parent_oids) |value| writer.field(value);

    writer.field(inputs.attribution);
    writer.field(inputs.identity_name);
    writer.field(inputs.identity_email);
    writer.signed(inputs.identity_timestamp);
    writer.signed(inputs.identity_zone_minutes);

    writer.fixed(&inputs.tree_digest);
    // Names, not ordinals. A digest keyed on `@intFromEnum` would change
    // meaning the day someone reorders a reason, silently and for every commit
    // ever imported; a name only changes when it is renamed, which is a change
    // anyone can see in the diff.
    writer.field(inputs.decision);
    writer.field(inputs.reason);
    writer.number(inputs.candidates.len);
    for (inputs.candidates) |candidate| {
        writer.field(candidate.path);
        writer.field(candidate.name);
        writer.field(candidate.oid);
    }
    writer.field(inputs.checkin);
    return writer.final();
}

/// What one commit's mirror candidates were decided to be.
pub const MirrorDecisionKind = enum {
    /// The commit's tree held no candidate path.
    none,
    /// Every present candidate was proven redundant and left out of the tree.
    omitted,
    /// Every present candidate was kept as an ordinary Git file.
    retained,
};

/// One present candidate root file at one commit, as the ledger reports it.
/// All three slices borrow from the importer and are valid until it is
/// deinitialized.
pub const LedgerCandidate = struct {
    /// The exact root name: one of `mirror_candidate_names`.
    path: []const u8,
    /// The Zit artifact name of its content.
    name: []const u8,
    /// The Git blob OID the stream carried for that content, when it did.
    oid: ?[]const u8,
};

/// One imported commit's semantic identity and mirror decision.
pub const LedgerCommit = struct {
    oid: ?[]const u8,
    /// The Zit check-in artifact name.
    name: []const u8,
    tree_digest: Digest,
    provenance_digest: Digest,
    decision: MirrorDecisionKind,
    /// Meaningful only when `decision` is `.retained`.
    reason: MirrorRetainReason,
    candidates: [mirror_candidate_names.len]?LedgerCandidate,
};

/// One artifact that was the content of at least one omitted candidate.
pub const LedgerArtifact = struct {
    name: []const u8,
    /// Emitted tree entries naming this artifact across the whole import.
    retained_references: u64,
    /// Whether the packed generation may drop it, which is exactly
    /// `retained_references == 0`.
    dropped: bool,
};

/// The importer's verification ledger: everything a later pass needs to prove
/// that a packed generation is the same repository as the raw one, without
/// re-deriving it from the same code that produced it.
///
/// Every slice inside borrows from the importer. The ledger owns only its two
/// outer arrays.
pub const VerificationLedger = struct {
    commits: []LedgerCommit,
    candidates: []LedgerArtifact,
    /// The whole import: every commit's provenance digest in stream order,
    /// then the ordered ref and tag mappings.
    provenance_digest: Digest,

    pub fn deinit(self: *VerificationLedger, gpa: std.mem.Allocator) void {
        gpa.free(self.commits);
        gpa.free(self.candidates);
        self.* = undefined;
    }
};

// ---------------------------------------------------------------------------
// The import witness
// ---------------------------------------------------------------------------
//
// The ledger above borrows every string in it from the importer, which the
// publication transaction destroys at the freeze -- before the raw generation
// is packed and long before the packed one is verified. So the ledger, on its
// own, cannot be what a pre-publication verifier compares a store against: by
// the time that verifier runs, every name in it dangles.
//
// This is that comparison's surviving half. It is the same facts, deep-copied
// into one arena, plus the two runs the ledger never carried (ordered parents
// in both naming systems) and the resolved refs. Nothing here borrows the
// importer, so it outlives the freeze by construction rather than by careful
// ordering.

pub const WitnessIdentity = struct {
    name: []const u8,
    email: []const u8,
    timestamp: i64,
    timezone_offset_minutes: i16,
};

pub const WitnessCandidate = struct {
    path: []const u8,
    name: []const u8,
    oid: ?[]const u8,
};

pub const WitnessCommit = struct {
    oid: ?[]const u8,
    /// The Zit check-in artifact name this commit became.
    checkin: []const u8,
    /// Ordered parent check-in names, first parent first.
    parents: []const []const u8,
    /// The same run in Git's names; "" where the stream carried none.
    parent_oids: []const []const u8,
    author: WitnessIdentity,
    committer: WitnessIdentity,
    tree_digest: Digest,
    provenance_digest: Digest,
    decision: MirrorDecisionKind,
    reason: MirrorRetainReason,
    candidates: [mirror_candidate_names.len]?WitnessCandidate,
};

pub const WitnessRef = struct {
    source: []const u8,
    canonical: []const u8,
    target: []const u8,
    /// Whether this ref exists because an annotated tag put it there. Those
    /// refs are deliberately absent from the finalized JSONL's `ref` records,
    /// so a verifier that did not know which ones they are would read their
    /// absence as a dropped mapping.
    annotated: bool,
};

/// Everything the pre-publication verifier compares the packed generation
/// against, owned outright.
pub const ImportWitness = struct {
    arena_state: std.heap.ArenaAllocator,
    attribution: Attribution,
    /// Stream order, parallel to the ledger's commits.
    commits: []const WitnessCommit,
    refs: []const WitnessRef,
    /// The whole-import provenance digest.
    provenance_digest: Digest,
    primary_branch: []const u8,

    pub fn deinit(self: *ImportWitness) void {
        self.arena_state.deinit();
        self.* = undefined;
    }

    /// This import's selected attribution for `commit` -- the one identity the
    /// check-in's U and D cards actually carry.
    pub fn selected(self: *const ImportWitness, commit: *const WitnessCommit) WitnessIdentity {
        return switch (self.attribution) {
            .committer => commit.committer,
            .author => commit.author,
        };
    }
};

const CanonicalRefState = struct {
    active_count: usize,
};

/// The two source refs a `CanonicalRefCollision` must name, borrowed from the
/// importer's own ref states and valid until it is deinitialized. Retained
/// rather than formatted for the same reason `FileCommandOverrun` is: the
/// importer has no output channel, and the error name alone leaves an operator
/// with a repository it cannot import and no idea which two refs to look at.
///
/// The surviving collision is a genuine one: two distinct source refs that
/// normalize to a byte-identical canonical name, such as `refs/heads/./release`
/// and `refs/heads/release`. Names that merely differ by letter case are not a
/// collision — `refs` is one packed file, so it holds both.
pub const RefCollision = struct {
    first_source: []const u8,
    second_source: []const u8,
    canonical: []const u8,
};

const RefOrigin = enum { commit, reset, annotated_tag };

const RefState = struct {
    source: []u8,
    canonical: []u8,
    target: ?[]u8,
    origin: RefOrigin,

    fn deinit(self: *RefState, gpa: std.mem.Allocator) void {
        gpa.free(self.source);
        gpa.free(self.canonical);
        if (self.target) |target| gpa.free(target);
        self.* = undefined;
    }
};

const PendingRef = union(enum) {
    existing: struct {
        index: usize,
        target: ?[]u8,
        origin: RefOrigin,
    },
    new: RefState,

    fn deinit(self: *PendingRef, gpa: std.mem.Allocator) void {
        switch (self.*) {
            .existing => |*state| if (state.target) |target| gpa.free(target),
            .new => |*state| state.deinit(gpa),
        }
        self.* = undefined;
    }

    fn publish(self: *PendingRef, importer: anytype) void {
        switch (self.*) {
            .existing => |state| {
                const current = &importer.ref_states.items[state.index];
                const canonical = importer.canonical_ref_index.getPtr(current.canonical).?;
                if (current.target == null and state.target != null) canonical.active_count += 1;
                if (current.target != null and state.target == null) canonical.active_count -= 1;
                const old = current.target;
                current.target = state.target;
                current.origin = state.origin;
                if (old) |target| importer.gpa.free(target);
            },
            .new => |state| {
                const index = importer.ref_states.items.len;
                importer.ref_states.appendAssumeCapacity(state);
                importer.ref_index.putAssumeCapacity(state.source, index);
                if (importer.canonical_ref_index.getPtr(state.canonical)) |canonical| {
                    if (state.target != null) canonical.active_count += 1;
                } else {
                    importer.canonical_ref_index.putAssumeCapacity(
                        state.canonical,
                        .{ .active_count = if (state.target == null) 0 else 1 },
                    );
                }
            },
        }
        self.* = undefined;
    }
};

const ImportedTag = struct {
    source: []u8,
    name: []u8,
    oid: ?[]u8,
    target: []u8,
    tagger: OwnedIdentity,
    message: []u8,

    fn deinit(self: *ImportedTag, gpa: std.mem.Allocator) void {
        gpa.free(self.source);
        gpa.free(self.name);
        if (self.oid) |oid| gpa.free(oid);
        gpa.free(self.target);
        self.tagger.deinit(gpa);
        gpa.free(self.message);
        self.* = undefined;
    }
};

pub const FinalizeOptions = struct {
    default_branch: ?[]const u8 = null,
};

pub const FinalizedRef = struct {
    source: []u8,
    canonical: []u8,
    target: []u8,
};

pub const FinalizedRefs = struct {
    controls: [][]u8,
    provenance_jsonl: []u8,
    refs: []FinalizedRef,
    primary_branch: []u8,
    /// Whether this import actually stored an S-bearing artifact, so the caller
    /// can set `seen_submanifest`. The latch's contract is "set when the first S
    /// reference is stored" (logstore.zig), and it is one-way — so it must be
    /// derived from what was emitted, not from whether trees were merely
    /// ENABLED. An import that pins k but whose sources are all small enough to
    /// stay flat stores no S reference and must leave the latch false.
    stored_submanifest: bool,
    /// What a later verification pass compares the packed generation against.
    /// Its strings borrow from the importer that produced it, so it must be
    /// read before that importer is deinitialized.
    ledger: VerificationLedger,

    pub fn deinit(self: *FinalizedRefs, gpa: std.mem.Allocator) void {
        self.ledger.deinit(gpa);
        for (self.controls) |bytes| gpa.free(bytes);
        gpa.free(self.controls);
        gpa.free(self.provenance_jsonl);
        for (self.refs) |mapping| {
            gpa.free(mapping.source);
            gpa.free(mapping.canonical);
            gpa.free(mapping.target);
        }
        gpa.free(self.refs);
        gpa.free(self.primary_branch);
        self.* = undefined;
    }
};

pub const IncrementalTreePolicy = struct {
    pub fn apply(
        tree_editor: *editor.TreeEditor,
        _: std.mem.Allocator,
        tree_store: editor.TreeStore,
        parent: editor.RootView,
        commands: []const editor.TreeCommand,
        result: *editor.BuildResult,
        cache_high_water: *usize,
    ) editor.Error!void {
        tree_editor.rebindStore(tree_store);
        result.* = try tree_editor.apply(parent, commands);
        cache_high_water.* = tree_editor.cacheHighWater();
    }

    pub fn inheritedFullTreeMaterialization(_: RootView) bool {
        return false;
    }
};
pub const NoopObserver = struct {
    pub fn beforeEvent(_: *NoopObserver, _: *const WorkCounters, _: fast_export.Event) !void {}
    pub fn beforeCommitFlush(_: *NoopObserver, _: *const WorkCounters, _: anytype) !void {}
    pub fn afterCommitFlush(_: *NoopObserver, _: *const WorkCounters, _: anytype) void {}
    pub fn afterEvent(_: *NoopObserver, _: *const WorkCounters, _: fast_export.Event) !void {}
};

/// Translation boundary between fast-export events and Zit artifacts. Both
/// tables own every byte they retain; callers receive borrowed object hashes.
pub fn Importer(comptime Policy: type, comptime Observer: type) type {
    return struct {
        const Self = @This();
        gpa: std.mem.Allocator,
        log: *logstore.LogStore,
        format: editor.TreeFormat,
        attribution: Attribution,
        tree_store: editor.TreeStore,
        tree_editor: editor.TreeEditor,
        work: WorkCounters,
        marks: std.AutoHashMapUnmanaged(u64, MarkState) = .empty,
        oids: std.StringHashMapUnmanaged(OidState) = .empty,
        ref_states: std.ArrayList(RefState) = .empty,
        ref_index: std.StringHashMapUnmanaged(usize) = .empty,
        canonical_ref_index: std.StringHashMapUnmanaged(CanonicalRefState) = .empty,
        objects: std.ArrayList(ImportedObject) = .empty,
        observer: Observer,
        blobs: std.ArrayList(ImportedBlob) = .empty,
        tags: std.ArrayList(ImportedTag) = .empty,
        /// Paths the source stream has declared a Git submodule (mode 160000)
        /// at least once. Owned keys; grows only, because a lineage the
        /// importer has not reached yet may still delete or rename one of them.
        gitlink_paths: std.StringHashMapUnmanaged(void) = .empty,
        /// Retained by `refuseRefCollision`. Null until `finalizeRefs` returns
        /// `CanonicalRefCollision`; borrows from `ref_states`, so it is read
        /// before the importer is deinitialized or not at all.
        ref_collision: ?RefCollision = null,

        /// Every ingested blob's content facts, keyed by the artifact name
        /// this import gave it. Taken on the one pass that already holds the
        /// payload, so neither the classifier nor the normalized-tree digest
        /// ever rereads or rehashes a blob.
        ///
        /// This table also owns the one canonical copy of every artifact name
        /// the importer keys anything by; the three tables below borrow from it.
        blob_facts: std.StringHashMapUnmanaged(BlobFacts) = .empty,
        /// How many emitted tree entries name each artifact. An artifact whose
        /// only appearances were omitted candidates has a zero count and is
        /// the only kind of artifact a later pack may drop.
        mirror_retained_refs: std.StringHashMapUnmanaged(u64) = .empty,
        /// Artifact names that were the content of at least one omitted
        /// candidate.
        mirror_candidates: std.StringHashMapUnmanaged(void) = .empty,
        /// Whether a `manifest.tags` blob satisfies fossil's branch/tag
        /// grammar, keyed by artifact name. A mirror shares a handful of these
        /// across its whole history, so the check runs once per distinct blob.
        mirror_tags_grammar: std.StringHashMapUnmanaged(bool) = .empty,
        mirror_census: MirrorCensus = .{},
        /// Every commit's provenance digest, in stream order, absorbed as it
        /// is published. Kept as a running absorber rather than a stored list
        /// so a million-commit import costs 32 bytes here, and copied rather
        /// than finalized in place so `finalizeRefs` stays repeatable.
        provenance_chain: DigestWriter,

        /// The production initializer fixes the incremental writer at compile time.
        /// No request, CLI argument, or persisted configuration can change it.
        pub fn init(
            gpa: std.mem.Allocator,
            log: *logstore.LogStore,
            tree_store: editor.TreeStore,
            options: UserOptions,
        ) !Self {
            return initObserved(gpa, log, tree_store, options, .{});
        }

        pub fn initObserved(
            gpa: std.mem.Allocator,
            log: *logstore.LogStore,
            tree_store: editor.TreeStore,
            options: UserOptions,
            observer: Observer,
        ) !Self {
            const resolved = try resolveOptions(options);
            const format: editor.TreeFormat = .{
                .hash_algo = .sha1,
                .shape = resolved.shape,
            };
            var tree_editor = try editor.TreeEditor.init(gpa, tree_store, format, options.tree_cache_bytes);
            errdefer tree_editor.deinit();
            var chain = DigestWriter.init(provenance_digest_domain);
            chain.byte(provenance_scope_repository);
            return .{
                .gpa = gpa,
                .log = log,
                .format = format,
                .attribution = resolved.attribution,
                .tree_store = tree_store,
                .tree_editor = tree_editor,
                .work = .{},
                .observer = observer,
                .provenance_chain = chain,
            };
        }

        pub fn workCounters(self: *const Self) WorkCounters {
            return self.work;
        }

        /// Every per-object table this importer grows, so the caller's entry
        /// ceiling bounds what it actually retains. The mirror tables belong
        /// here for the same reason the mark and OID tables do: each is at most
        /// one entry per distinct ingested blob, so leaving them out would
        /// understate retention on exactly the blob-heavy imports the ceiling
        /// exists to stop.
        pub fn retainedStateEntries(self: *const Self) usize {
            return self.marks.count() + self.oids.count() + self.objects.items.len +
                self.ref_states.items.len + self.blobs.items.len + self.tags.items.len +
                self.blob_facts.count() + self.mirror_retained_refs.count() +
                self.mirror_candidates.count() + self.mirror_tags_grammar.count();
        }

        pub fn deinit(self: *Self) void {
            self.tree_editor.deinit();
            var marks_it = self.marks.iterator();
            while (marks_it.next()) |entry| self.gpa.free(entry.value_ptr.hash());
            self.marks.deinit(self.gpa);

            var oids_it = self.oids.iterator();
            while (oids_it.next()) |entry| {
                self.gpa.free(entry.key_ptr.*);
                self.gpa.free(entry.value_ptr.hash);
            }
            self.oids.deinit(self.gpa);
            for (self.ref_states.items) |*state| state.deinit(self.gpa);
            self.ref_states.deinit(self.gpa);
            self.ref_index.deinit(self.gpa);
            self.canonical_ref_index.deinit(self.gpa);
            for (self.objects.items) |*object| object.deinit(self.gpa);
            for (self.blobs.items) |*blob| blob.deinit(self.gpa);
            self.blobs.deinit(self.gpa);
            self.objects.deinit(self.gpa);
            for (self.tags.items) |*tag| tag.deinit(self.gpa);
            self.tags.deinit(self.gpa);
            var gitlink_it = self.gitlink_paths.keyIterator();
            while (gitlink_it.next()) |key| self.gpa.free(key.*);
            self.gitlink_paths.deinit(self.gpa);
            // The mirror tables borrow their keys from the digest table, so
            // only that one frees them, and only after the borrowers are gone.
            self.mirror_retained_refs.deinit(self.gpa);
            self.mirror_candidates.deinit(self.gpa);
            self.mirror_tags_grammar.deinit(self.gpa);
            var digest_it = self.blob_facts.keyIterator();
            while (digest_it.next()) |key| self.gpa.free(key.*);
            self.blob_facts.deinit(self.gpa);
            // The shared editor's cache owns its decoded immutable nodes.
            self.* = undefined;
        }

        pub fn ingest(self: *Self, event: fast_export.Event) !void {
            try self.observer.beforeEvent(&self.work, event);
            switch (event) {
                .blob => |blob| {
                    try self.ingestBlob(blob);
                    self.work.blobs += 1;
                },
                .commit => |commit| {
                    try self.ingestCommit(commit);
                    self.work.commits += 1;
                },
                .tag => |tag| {
                    try self.ingestTag(tag);
                    self.work.tags += 1;
                },
                .reset => |reset| {
                    try self.ingestReset(reset);
                    self.work.resets += 1;
                },
                .done => {},
            }
            try self.observer.afterEvent(&self.work, event);
        }

        /// Drives the canonical fast-export parser into the importer. Callers own
        /// only the bytes and limits; parser leases, translation, and ref state
        /// stay on this shared path.
        pub fn ingestFastExport(self: *Self, bytes: []const u8, limits: fast_export.Limits) !void {
            const input = std.Io.Reader.fixed(bytes);
            var reader = fast_export.Reader.init(self.gpa, input, limits);
            defer reader.deinit();
            while (try reader.next()) |lease| {
                var event = lease;
                defer event.deinit();
                self.ingest(event.value) catch |err| {
                    if (comptime @hasDecl(Observer, "stopOnError")) if (self.observer.stopOnError(err)) break;
                    return err;
                };
            }
        }

        pub fn objectForMark(self: *const Self, mark: u64) ![]const u8 {
            const state = self.marks.getPtr(mark) orelse return error.UnresolvedMark;
            return state.hash();
        }

        pub fn objectForOid(self: *const Self, oid: []const u8) ![]const u8 {
            var normalized_buf: [64]u8 = undefined;
            const normalized = try canonicalOidBytes(oid, &normalized_buf);
            const state = self.oids.getPtr(normalized) orelse return error.UnresolvedMark;
            return state.hash;
        }

        fn ingestBlob(self: *Self, blob: fast_export.Blob) !void {
            if (self.marks.contains(blob.mark)) return error.DuplicateMark;
            var name_buf: [64]u8 = undefined;
            const hash = artifact.artifactName(self.format.hash_algo, blob.data, &name_buf);
            var digest_buf: [32]u8 = undefined;
            const digest = try decodeArtifactName(hash, &digest_buf);
            var oid_buf: [64]u8 = undefined;
            const oid = try canonicalOid(blob.original_oid, &oid_buf);
            const needs_oid = try self.canBindOid(oid, .blob, hash);

            try self.marks.ensureUnusedCapacity(self.gpa, 1);
            if (needs_oid) try self.oids.ensureUnusedCapacity(self.gpa, 1);
            try self.blobs.ensureUnusedCapacity(self.gpa, 1);
            try self.blob_facts.ensureUnusedCapacity(self.gpa, 1);
            const mark_hash = try self.gpa.dupe(u8, hash);
            var published = false;
            errdefer if (!published) self.gpa.free(mark_hash);
            const oid_owned = if (needs_oid) try self.gpa.dupe(u8, oid.?) else null;
            errdefer if (!published) if (oid_owned) |owned_oid| self.gpa.free(owned_oid);
            const oid_hash = if (needs_oid) try self.gpa.dupe(u8, hash) else null;
            errdefer if (!published) if (oid_hash) |value| self.gpa.free(value);
            const record_oid = if (blob.original_oid) |value| try self.gpa.dupe(u8, value) else null;
            errdefer if (record_oid) |value| self.gpa.free(value);
            const record_hash = try self.gpa.dupe(u8, hash);
            errdefer self.gpa.free(record_hash);
            const record = ImportedBlob{ .oid = record_oid, .hash = record_hash };
            // Both content digests are taken here, on the one pass that
            // already has the payload in hand. Deferring either would mean
            // rereading the blob out of the log -- at classification time for
            // the alternate, and once per tree entry per commit for the
            // SHA-256, which is exactly the reread the design forbids.
            const digest_key: ?[]u8 = if (self.blob_facts.contains(hash))
                null
            else
                try self.gpa.dupe(u8, hash);
            errdefer if (!published) if (digest_key) |key| self.gpa.free(key);
            var facts: BlobFacts = undefined;
            if (digest_key != null) {
                alternateContentDigest(self.format.hash_algo, blob.data, &facts.alternate);
                std.crypto.hash.sha2.Sha256.hash(blob.data, &facts.content, .{});
                facts.length = blob.data.len;
                facts.oid = record_oid;
            }

            _ = try self.log.putArtifact(digest, blob.data, null);
            self.marks.putAssumeCapacity(blob.mark, .{ .blob = mark_hash });
            if (oid_owned) |owned_oid| self.oids.putAssumeCapacity(owned_oid, .{ .kind = .blob, .hash = oid_hash.? });
            if (digest_key) |key| self.blob_facts.putAssumeCapacity(key, facts);
            published = true;
            self.blobs.appendAssumeCapacity(record);
        }

        fn ingestCommit(self: *Self, commit: fast_export.Commit) !void {
            if (self.marks.contains(commit.mark)) return error.DuplicateMark;
            var oid_buf: [64]u8 = undefined;
            const oid = try canonicalOid(commit.original_oid, &oid_buf);
            try self.preflightCommitOid(oid);

            var parent_hashes: std.ArrayList([]const u8) = .empty;
            defer parent_hashes.deinit(self.gpa);
            try parent_hashes.ensureTotalCapacity(self.gpa, commit.merges.len + @as(usize, if (commit.from == null) 0 else 1));

            var parent_root: ?ParentRoot = null;
            defer if (parent_root) |*root| root.deinit(self.gpa);
            var root_view: editor.RootView = .{ .flat = &.{} };
            var first_parent_index: ?usize = null;
            if (commit.from) |from| {
                const parent_index = try self.resolveCommitObjectIndex(from);
                const primary_hash = self.objects.items[parent_index].hash;
                first_parent_index = parent_index;
                parent_hashes.appendAssumeCapacity(primary_hash);
                parent_root = try self.loadParentRoot(primary_hash);
                root_view = parent_root.?.view();
            }
            for (commit.merges) |merge| parent_hashes.appendAssumeCapacity(try self.resolveCommit(merge));

            // The same ordered run, in Git's names rather than Zit's. Taken
            // here, where every parent has just been resolved, because
            // `parentOid` answers "" for anything it cannot follow -- a fine
            // answer while the resolution is fresh and a silent hole later.
            var parent_oids: std.ArrayList([]const u8) = .empty;
            defer parent_oids.deinit(self.gpa);
            try parent_oids.ensureTotalCapacity(self.gpa, parent_hashes.items.len);
            if (commit.from) |from| parent_oids.appendAssumeCapacity(self.parentOid(from));
            for (commit.merges) |merge| parent_oids.appendAssumeCapacity(self.parentOid(merge));

            // Translation runs after the parent root is resolved: a Git submodule
            // entry is only resolvable against the tree it is applied to, since
            // whether the path currently holds a real file decides whether
            // omitting it needs a delete.
            const parent_mirror: *const MirrorState = if (first_parent_index) |parent_index|
                &self.objects.items[parent_index].mirror
            else
                &empty_mirror_state;
            var mirror = MirrorTrack.init(parent_mirror);

            var tree_commands: std.ArrayList(editor.TreeCommand) = .empty;
            defer tree_commands.deinit(self.gpa);
            try tree_commands.ensureTotalCapacity(self.gpa, commit.commands.len);
            // The same list without the commands that only touch candidate
            // paths. Built lazily: a repository with no mirror metadata never
            // allocates it, and so takes exactly the pre-existing single-apply
            // path with exactly the pre-existing command list.
            var base_commands: std.ArrayList(editor.TreeCommand) = .empty;
            defer base_commands.deinit(self.gpa);
            var base_tracking = mirror.active;

            if (self.needsSubmoduleLookups(commit.commands)) {
                // `Policy.apply` leaves the editor bound to the previous commit's
                // stack-local staging store, which no longer exists. Parent-tree
                // lookups below must read the durable store instead.
                self.tree_editor.rebindStore(self.tree_store);
            }
            var effective_parent = root_view;
            for (commit.commands) |command| {
                if (try self.treeCommand(command, effective_parent, &mirror)) |translated| {
                    tree_commands.appendAssumeCapacity(translated);
                    const keeps = mirror.observe(translated);
                    if (!base_tracking and mirror.active) {
                        // The first candidate command activates the split; the
                        // commands before it were all ordinary, so they are
                        // back-filled rather than re-translated.
                        base_tracking = true;
                        try base_commands.appendSlice(self.gpa, tree_commands.items[0 .. tree_commands.items.len - 1]);
                    }
                    if (base_tracking and keeps) try base_commands.append(self.gpa, translated);
                }
                // Everything after a `deleteall` sees an empty tree, so a
                // submodule re-listed by a full-tree export needs no delete.
                if (std.meta.activeTag(command) == .delete_all) effective_parent = .{ .flat = &.{} };
            }

            // Two stores because a rejected classification must leave nothing
            // behind: `StagingStore.flush` writes every node it accumulated, so
            // a speculative build and its replacement cannot share one, or the
            // orphaned S nodes of the discarded tree would be published.
            var staged_primary = StagingStore.init(self.gpa, self.tree_store);
            defer staged_primary.deinit();
            var staged_fallback = StagingStore.init(self.gpa, self.tree_store);
            defer staged_fallback.deinit();
            var used_fallback = false;
            var result: editor.BuildResult = undefined;
            var result_live = false;
            defer if (result_live) result.deinit();
            const measure_tree_apply = self.work.commits != 0;
            const tree_apply_cpu_start = if (measure_tree_apply) treeApplyCpuNs() else 0;
            var cache_high_water: usize = 0;
            // A rejected classification applies twice, and `Policy.apply`
            // reports the editor's high water for the apply it just ran rather
            // than the run's maximum. Carrying the speculative peak across is
            // what keeps the counter a high water mark.
            var speculative_high_water: usize = 0;
            var tree_applies: u64 = 0;
            var decision = MirrorDecision.retain(.no_candidates);
            defer decision.deinit(self.gpa);

            // The classifier's tree is built FIRST, not built and then edited:
            // the candidate-free tree is both the comparand gate 5 needs and
            // the tree a validated commit emits, so the common case on a real
            // mirror -- every commit validates -- costs exactly one apply.
            if (mirror.active and !mirror.unsupported and mirror.pairPresent()) {
                var speculative: std.ArrayList(editor.TreeCommand) = .empty;
                defer speculative.deinit(self.gpa);
                try speculative.ensureTotalCapacity(self.gpa, base_commands.items.len + mirror_candidate_names.len);
                // A parent that RETAINED left its candidates in the emitted
                // tree; strip them before the commit's own commands run.
                if (!parent_mirror.omitted) {
                    for (mirror_candidate_names, 0..) |name, index| {
                        if (parent_mirror.entries[index] == null) continue;
                        speculative.appendAssumeCapacity(.{ .delete = name });
                    }
                }
                speculative.appendSliceAssumeCapacity(base_commands.items);
                try Policy.apply(
                    &self.tree_editor,
                    self.gpa,
                    staged_primary.treeStore(),
                    root_view,
                    speculative.items,
                    &result,
                    &cache_high_water,
                );
                result_live = true;
                tree_applies += 1;
                decision = try self.classifyMirror(commit, &mirror, rootViewOf(result.root), &staged_primary);
                if (decision.omit) {
                    try self.recordRetainedReferences(speculative.items);
                    try self.recordOmittedCandidates(&mirror);
                } else {
                    result.deinit();
                    result_live = false;
                    used_fallback = true;
                    speculative_high_water = cache_high_water;
                }
            } else if (mirror.active) {
                decision = MirrorDecision.retain(if (mirror.unsupported)
                    .unsupported_command
                else if (mirror.anyPresent())
                    .incomplete_pair
                else
                    // Every candidate was deleted, so there is no pair to be
                    // incomplete. The commit is only here because an ancestor
                    // had candidates.
                    .no_candidates);
            }

            if (!result_live) {
                // The retained path materializes the parent's complete Git tree
                // and then applies the commit's own commands verbatim. When the
                // parent retained too -- every commit of an ordinary import --
                // the prefix is empty and this is byte-for-byte the command
                // list this importer has always applied.
                var retained: std.ArrayList(editor.TreeCommand) = .empty;
                defer retained.deinit(self.gpa);
                var commands: []const editor.TreeCommand = tree_commands.items;
                if (parent_mirror.omitted) {
                    try retained.ensureTotalCapacity(self.gpa, tree_commands.items.len + mirror_candidate_names.len);
                    for (mirror_candidate_names, 0..) |name, index| {
                        const entry = parent_mirror.entries[index] orelse continue;
                        retained.appendAssumeCapacity(.{ .upsert = .{
                            .filename = name,
                            .hash = entry.hash,
                            .perm = mirrorPerm(entry.mode),
                            .old_name = null,
                            .mode = entry.mode,
                        } });
                    }
                    retained.appendSliceAssumeCapacity(tree_commands.items);
                    commands = retained.items;
                }
                try Policy.apply(
                    &self.tree_editor,
                    self.gpa,
                    if (used_fallback) staged_fallback.treeStore() else staged_primary.treeStore(),
                    root_view,
                    commands,
                    &result,
                    &cache_high_water,
                );
                result_live = true;
                tree_applies += 1;
                try self.recordRetainedReferences(commands);
            }
            const staged = if (used_fallback) &staged_fallback else &staged_primary;
            cache_high_water = @max(cache_high_water, speculative_high_water);

            if (measure_tree_apply) {
                // Counted per apply, not per commit: the elapsed span below
                // covers both applies of a rejected classification, so a
                // per-commit count would silently inflate the per-apply mean --
                // the one number that would reveal rejections are happening.
                self.work.tree_apply_count += tree_applies;
                self.work.tree_apply_cpu_ns += treeApplyCpuNs() - tree_apply_cpu_start;
            }
            if (Policy.inheritedFullTreeMaterialization(root_view)) self.work.inherited_full_tree_materializations += 1;
            // Restatement of the editor's flat induction at the importer seam.
            // `TreeEditor.apply` already refuses a tree parent under a flat
            // format, so this only catches a flat format that produced a tree
            // root -- an assert rather than an error because the editor, not
            // the source repository, would have to be wrong for it to fire.
            if (std.meta.activeTag(self.format.shape) == .flat) {
                std.debug.assert(std.meta.activeTag(result.root) == .flat);
            }
            const tree_height = result.tree_height orelse if (first_parent_index) |parent_index|
                self.objects.items[parent_index].tree_height
            else
                return error.MalformedNode;

            var mirror_state: MirrorState = if (decision.omit)
                try self.mirrorStateFromTrack(&mirror, decision.uuid.?)
            else if (mirror.active)
                try self.mirrorStateFromTree(rootViewOf(result.root))
            else
                .{};
            var mirror_state_owned = true;
            errdefer if (mirror_state_owned) mirror_state.deinit(self.gpa);
            const decision_kind: MirrorDecisionKind = if (!mirror.active)
                .none
            else if (decision.omit)
                .omitted
            else
                .retained;
            // Taken before the flush, while the tree's S nodes are still only
            // in the staging store: after publication they are indistinguishable
            // from any other node, but right here they are exactly this
            // commit's tree and nothing else.
            const tree_digest = try self.rootTreeDigest(rootViewOf(result.root), staged);

            const parent_text = if (parent_hashes.items.len == 0)
                null
            else
                try std.mem.join(self.gpa, " ", parent_hashes.items);
            defer if (parent_text) |text| self.gpa.free(text);
            var parent_card: artifact.PCard = undefined;
            const parent_cards: []const artifact.PCard = if (parent_text) |text| blk: {
                parent_card = .{ .parents = text, .count = parent_hashes.items.len };
                break :blk &.{parent_card};
            } else &.{};

            const attributed = switch (self.attribution) {
                .committer => commit.committer,
                .author => commit.author,
            };
            var timestamp_buf: [19]u8 = undefined;
            const timestamp = try formatWriterTimestamp(attributed.timestamp, &timestamp_buf);
            const comment = if (commit.message.len == 0) "git import" else commit.message;
            var manifest: artifact.Manifest = .{
                .arena_state = std.heap.ArenaAllocator.init(self.gpa),
                .kind = .manifest,
                .a = null,
                .b = null,
                .c = .{ .comment = comment },
                .d = .{ .timestamp = timestamp },
                .e = null,
                .g = null,
                .h = null,
                .i = null,
                .k = null,
                .l = null,
                .n = null,
                .r = null,
                .u = .{ .login = attributed.name },
                .z = null,
                .w = null,
                .f = switch (result.root) {
                    .flat => |cards| cards,
                    .tree => &.{},
                },
                .j = &.{},
                .m = &.{},
                .p = parent_cards,

                .q = &.{},
                .s = switch (result.root) {
                    .flat => &.{},
                    .tree => |cards| cards,
                },
                .t = &.{},
            };
            defer manifest.deinit();
            const bytes = try artifact.create(&manifest, self.gpa);
            defer self.gpa.free(bytes);
            var name_buf: [64]u8 = undefined;
            const hash = artifact.artifactName(self.format.hash_algo, bytes, &name_buf);
            const needs_oid = try self.canBindOid(oid, .commit, hash);
            // The preflight above makes an extant commit OID fail before TreeEditor
            // can emit a candidate node. This post-serialization check sees only a
            // newly bound identity and cannot append before map capacity is reserved.

            try self.marks.ensureUnusedCapacity(self.gpa, 1);
            if (needs_oid) try self.oids.ensureUnusedCapacity(self.gpa, 1);
            const mark_hash = try self.gpa.dupe(u8, hash);
            var published = false;
            errdefer {
                if (!published) self.gpa.free(mark_hash);
            }
            const oid_owned = if (needs_oid) try self.gpa.dupe(u8, oid.?) else null;
            errdefer {
                if (!published) if (oid_owned) |owned_oid| self.gpa.free(owned_oid);
            }
            const oid_hash = if (needs_oid) try self.gpa.dupe(u8, hash) else null;
            errdefer {
                if (!published) if (oid_hash) |value| self.gpa.free(value);
            }
            const object_index = self.objects.items.len;
            const provenance_digest = self.commitProvenanceDigest(
                commit,
                parent_oids.items,
                &mirror_state,
                decision_kind,
                decision.reason,
                tree_digest,
                hash,
            );
            var commit_record = try self.prepareCommitRecord(commit, hash, first_parent_index, tree_height);
            errdefer commit_record.deinit(self.gpa);
            commit_record.parents = try parent_hashes.toOwnedSlice(self.gpa);
            commit_record.parent_oids = try parent_oids.toOwnedSlice(self.gpa);
            commit_record.mirror = mirror_state;
            mirror_state_owned = false;
            commit_record.tree_digest = tree_digest;
            commit_record.provenance_digest = provenance_digest;
            commit_record.decision = decision_kind;
            commit_record.retain_reason = decision.reason;
            var pending_ref = try self.prepareRef(commit.ref, hash, .commit);
            errdefer pending_ref.deinit(self.gpa);

            // All TreeEditor writes remain private until every importer allocation
            // needed for this check-in's mark/OID state has succeeded.
            const observation = try staged.observation(bytes);
            try self.observer.beforeCommitFlush(&self.work, observation);
            try staged.flush(hash, bytes);
            self.observer.afterCommitFlush(&self.work, observation);
            self.objects.appendAssumeCapacity(commit_record);
            self.marks.putAssumeCapacity(commit.mark, .{ .commit = .{
                .checkin_hash = mark_hash,
                .object_index = object_index,
            } });
            if (oid_owned) |owned_oid| {
                self.oids.putAssumeCapacity(owned_oid, .{
                    .kind = .commit,
                    .hash = oid_hash.?,
                    .object_index = object_index,
                });
            }
            published = true;
            pending_ref.publish(self);
            // Absorbed only once the commit is published, so an unwound commit
            // leaves the chain exactly where it was.
            self.provenance_chain.fixed(&provenance_digest);
            // "With candidates" means Git truth actually held one, or a command
            // moved content across the boundary. A commit that inherited an
            // active namespace and then deleted every member has none, and
            // counting it would make the census disagree with its own reason.
            if (mirror.active and (mirror.anyPresent() or mirror.unsupported)) {
                self.mirror_census.commits_with_candidates += 1;
                if (decision.omit) {
                    self.mirror_census.commits_validated += 1;
                } else {
                    self.mirror_census.commits_retained += 1;
                    self.mirror_census.retained_by_reason[@intFromEnum(decision.reason)] += 1;
                }
            }
            self.work.changed_paths += result.changed_paths;
            self.work.emitted_nodes += result.emitted_nodes;
            self.work.reused_nodes += result.reused_nodes;
            self.work.cache_high_water_bytes = @max(self.work.cache_high_water_bytes, cache_high_water);
            self.work.max_tree_height = @max(self.work.max_tree_height, tree_height);
        }

        /// Translates one fast-export file command against `parent`, the tree the
        /// command is applied to. Returns null when the command contributes
        /// nothing to the Zit tree, which happens only for Git submodules: Zit has
        /// no gitlink entry, so a submodule path is absent from every tree this
        /// import writes.
        fn treeCommand(
            self: *Self,
            command: fast_export.FileCommand,
            parent: editor.RootView,
            mirror: *const MirrorTrack,
        ) !?editor.TreeCommand {
            return switch (command) {
                .modify => |modify| blk: {
                    try validateImportedPath(modify.path);
                    const mode: artifact.FileMode = switch (modify.mode) {
                        .regular => .regular,
                        .executable => .executable,
                        .symlink => .symlink,
                        .gitlink => break :blk try self.omitSubmodule(parent, modify.path, mirror),
                    };
                    break :blk .{ .upsert = .{
                        .filename = modify.path,
                        .hash = try self.resolveBlob(modify.data),
                        .perm = switch (mode) {
                            .regular => null,
                            .executable => "x",
                            .symlink => "l",
                        },
                        .old_name = null,
                        .mode = mode,
                    } };
                },
                .delete => |path| blk: {
                    try validateImportedPath(path);
                    if (try self.omittedSubmodule(parent, path, mirror)) break :blk null;
                    break :blk .{ .delete = path };
                },
                .rename => |rename| blk: {
                    try validateImportedPath(rename.old);
                    try validateImportedPath(rename.new);
                    // Moving an omitted submodule moves the omission: the
                    // destination becomes the submodule path, and a real file
                    // sitting there is replaced exactly as Git replaces it.
                    if (try self.omittedSubmodule(parent, rename.old, mirror)) {
                        break :blk try self.omitSubmodule(parent, rename.new, mirror);
                    }
                    break :blk .{ .rename = .{ .old = rename.old, .new = rename.new } };
                },
                .copy => |copy| blk: {
                    try validateImportedPath(copy.old);
                    try validateImportedPath(copy.new);
                    if (try self.omittedSubmodule(parent, copy.old, mirror)) {
                        break :blk try self.omitSubmodule(parent, copy.new, mirror);
                    }
                    break :blk .{ .copy = .{ .old = copy.old, .new = copy.new } };
                },
                .delete_all => editor.TreeCommand.delete_all,
            };
        }

        /// Records `path` as a submodule path and returns the tree command that
        /// keeps it out of the imported tree: a delete when `parent` still holds a
        /// real file there (a file replaced by a submodule), otherwise nothing.
        fn omitSubmodule(
            self: *Self,
            parent: editor.RootView,
            path: []const u8,
            mirror: *const MirrorTrack,
        ) !?editor.TreeCommand {
            try self.recordGitlinkPath(path);
            self.work.skipped_submodule_entries += 1;
            // A candidate path is answered from Git truth, not from `parent`.
            // A validated parent deliberately left its candidates out of the
            // emitted tree, so the lookup below would find nothing and emit no
            // delete -- and the stale entry would survive in the shadow state
            // and be restored into a later retained commit's tree as a regular
            // file Git does not have. The two models are allowed to disagree
            // only here, so this is the one place that has to say which wins.
            if (mirrorCandidateIndex(path)) |index| {
                if (!mirror.present(index)) return null;
                return .{ .delete = path };
            }
            if ((try self.tree_editor.lookup(parent, path)) == null) return null;
            return .{ .delete = path };
        }

        /// Whether `path` is absent from `parent` *because* this import omitted a
        /// submodule there, which is the only case where a delete, or a rename or
        /// copy source, may name a path the tree does not have.
        ///
        /// Both halves of the test do real work, and together they are why this
        /// cannot hide a genuine missing-path bug. Eligibility is restricted to
        /// paths the source itself declared mode 160000, so a command naming a
        /// path the importer should have written still reaches the tree editor and
        /// still fails with `MissingPath`. And `parent` is consulted per commit
        /// rather than trusting the recorded set alone, so a path that is a
        /// submodule on one branch and a real file on another is deleted normally
        /// on the branch where it is a file.
        fn omittedSubmodule(
            self: *Self,
            parent: editor.RootView,
            path: []const u8,
            mirror: *const MirrorTrack,
        ) !bool {
            if (!self.gitlink_paths.contains(path)) return false;
            // For a candidate path `parent` is not the authority `omitSubmodule`
            // spells out: a validated parent emitted no candidates at all, so
            // the lookup would answer "absent" for a path Git still has a file
            // at, and the delete would be dropped.
            if (mirrorCandidateIndex(path)) |index| return !mirror.present(index);
            return (try self.tree_editor.lookup(parent, path)) == null;
        }

        fn recordGitlinkPath(self: *Self, path: []const u8) !void {
            if (self.gitlink_paths.contains(path)) return;
            try self.gitlink_paths.ensureUnusedCapacity(self.gpa, 1);
            const owned = try self.gpa.dupe(u8, path);
            self.gitlink_paths.putAssumeCapacity(owned, {});
        }

        /// Whether any command in `commands` can need a parent-tree lookup. A
        /// commit that touches no submodule path skips the rebind and every
        /// lookup, so the common case pays nothing for this policy.
        fn needsSubmoduleLookups(self: *const Self, commands: []const fast_export.FileCommand) bool {
            for (commands) |command| switch (command) {
                .modify => |modify| if (modify.mode == .gitlink) return true,
                .delete => |path| if (self.gitlink_paths.contains(path)) return true,
                .rename => |rename| if (self.gitlink_paths.contains(rename.old)) return true,
                .copy => |copy| if (self.gitlink_paths.contains(copy.old)) return true,
                .delete_all => {},
            };
            return false;
        }

        fn resolveBlob(self: *const Self, reference: fast_export.ObjectRef) ![]const u8 {
            return self.resolveKind(reference, .blob);
        }

        fn resolveCommit(self: *const Self, reference: fast_export.ObjectRef) ![]const u8 {
            return switch (reference) {
                .mark => |mark| {
                    const state = self.marks.getPtr(mark) orelse return error.UnresolvedMark;
                    return switch (state.*) {
                        .commit => |commit| commit.checkin_hash,
                        .tagged => |target| target,
                        else => error.UnresolvedMark,
                    };
                },
                .oid => |raw_oid| {
                    var oid_buf: [64]u8 = undefined;
                    const oid = try canonicalOidBytes(raw_oid, &oid_buf);
                    const state = self.oids.getPtr(oid) orelse return error.UnresolvedMark;
                    if (state.kind != .commit) return error.UnresolvedMark;
                    return state.hash;
                },
            };
        }

        fn resolveCommitObjectIndex(self: *const Self, reference: fast_export.ObjectRef) !usize {
            return switch (reference) {
                .mark => |mark| {
                    const state = self.marks.getPtr(mark) orelse return error.UnresolvedMark;
                    return switch (state.*) {
                        .commit => |commit| commit.object_index,
                        else => error.UnresolvedMark,
                    };
                },
                .oid => |raw_oid| {
                    var oid_buf: [64]u8 = undefined;
                    const oid = try canonicalOidBytes(raw_oid, &oid_buf);
                    const state = self.oids.getPtr(oid) orelse return error.UnresolvedMark;
                    if (state.kind != .commit) return error.UnresolvedMark;
                    return state.object_index orelse error.UnresolvedMark;
                },
            };
        }

        fn resolveKind(self: *const Self, reference: fast_export.ObjectRef, expected: ObjectKind) ![]const u8 {
            return switch (reference) {
                .mark => |mark| {
                    const state = self.marks.getPtr(mark) orelse return error.UnresolvedMark;
                    return switch (state.*) {
                        .blob => |hash| if (expected == .blob) hash else error.UnresolvedMark,
                        else => error.UnresolvedMark,
                    };
                },
                .oid => |raw_oid| {
                    var oid_buf: [64]u8 = undefined;
                    const oid = try canonicalOidBytes(raw_oid, &oid_buf);
                    const state = self.oids.getPtr(oid) orelse return error.UnresolvedMark;
                    if (state.kind != expected or expected != .blob) return error.UnresolvedMark;
                    return state.hash;
                },
            };
        }

        fn canBindOid(self: *const Self, oid: ?[]const u8, kind: ObjectKind, hash: []const u8) !bool {
            const name = oid orelse return false;
            const existing = self.oids.getPtr(name) orelse return true;
            if (existing.kind != kind or !std.mem.eql(u8, existing.hash, hash)) return error.ConflictingOid;
            return false;
        }

        fn preflightCommitOid(self: *const Self, oid: ?[]const u8) !void {
            const name = oid orelse return;
            if (self.oids.contains(name)) return error.ConflictingOid;
        }

        fn loadParentRoot(self: *Self, hash: []const u8) !ParentRoot {
            var digest_buf: [32]u8 = undefined;
            const digest = try decodeArtifactName(hash, &digest_buf);
            const rid = self.log.lookup(digest) orelse return error.UnresolvedMark;
            const bytes = (try self.log.content(self.gpa, rid)) orelse return error.UnresolvedMark;
            errdefer self.gpa.free(bytes);
            const manifest = try artifact.parse(self.gpa, bytes);
            return .{ .bytes = bytes, .manifest = manifest };
        }
        // -------------------------------------------------------------------
        // Mirror classification
        // -------------------------------------------------------------------

        /// The importer's one canonical copy of an artifact name. Every hash a
        /// tree entry carries came from an ingested blob, so the digest table
        /// already owns the bytes; the reference and candidate tables borrow
        /// them rather than keeping a third copy of every name in the source.
        fn artifactKey(self: *const Self, hash: []const u8) ?[]const u8 {
            const key = self.blob_facts.getKeyPtr(hash) orelse return null;
            return key.*;
        }

        /// The Git blob OID this import saw for the content named `hash`.
        fn blobOid(self: *const Self, hash: []const u8) ?[]const u8 {
            const facts = self.blob_facts.getPtr(hash) orelse return null;
            return facts.oid;
        }

        /// One candidate blob's bytes, read back the way `loadParentRoot`
        /// reads a check-in. Candidate payloads ARE the evidence under test,
        /// so rereading them is the work; it is unchanged tree content that
        /// must never be reread.
        fn loadCandidateBytes(self: *Self, hash: []const u8) !?[]u8 {
            var digest_buf: [32]u8 = undefined;
            const digest = decodeArtifactName(hash, &digest_buf) catch return null;
            const rid = self.log.lookup(digest) orelse return null;
            return try self.log.content(self.gpa, rid);
        }

        /// Whether the Fossil hash `want` names the same content as the
        /// imported tree entry named `got`.
        ///
        /// Zit and Fossil both name an artifact by the raw hash of its
        /// content -- unlike Git, which prefixes `blob <len>\0` -- so a mirror
        /// whose hash policy matches this import's is answered by comparing
        /// names. The other policy is answered from the per-blob digest cache.
        /// Neither path reloads or rehashes a payload.
        fn mirrorHashMatches(self: *Self, want: []const u8, got: []const u8) bool {
            const algo = artifact.nameAlgo(want.len) orelse return false;
            // Fossil emits lowercase. Section 3 lets a reader accept an
            // uppercase artifact name but never requires it, and a name this
            // cannot compare byte-for-byte is one it cannot prove anything
            // about, so the canonical form is the only form that proves.
            if (!artifact.validateName(want)) return false;
            if (algo == self.format.hash_algo) {
                self.mirror_census.name_comparisons += 1;
                return std.mem.eql(u8, want, got);
            }
            const facts = self.blob_facts.getPtr(got) orelse {
                self.mirror_census.digest_cache_misses += 1;
                return false;
            };
            self.mirror_census.digest_cache_hits += 1;
            const width = alternateDigestLen(self.format.hash_algo);
            var hex_buf: [64]u8 = undefined;
            const hex = std.fmt.bufPrint(&hex_buf, "{x}", .{facts.alternate[0..width]}) catch return false;
            return std.mem.eql(u8, want, hex);
        }

        /// Whether the mirror's own F-card run is exactly the commit's tree
        /// with every present candidate excluded.
        ///
        /// Both sides are canonically ordered, so this is one sorted merge:
        /// equal cardinality, equal paths, equal modes, equal content, and
        /// strict ordering on the mirror's side so a duplicated or unsorted
        /// card cannot masquerade as a match.
        fn mirrorFilesMatch(
            self: *Self,
            cards: []const artifact.FCard,
            files: []const artifact.FCard,
        ) bool {
            if (cards.len != files.len) return false;
            var previous: ?[]const u8 = null;
            for (cards, files) |card, file| {
                if (previous) |last| {
                    if (artifact.compareBytes(last, card.filename) != .lt) return false;
                }
                previous = card.filename;
                if (!std.mem.eql(u8, card.filename, file.filename)) return false;
                if (card.mode != file.mode) return false;
                // Restatement of the exclusion at the point it is relied on: if
                // a candidate name reached the compared tree, the tree is not
                // the candidate-free one this gate assumes and retaining is the
                // only safe answer.
                if (mirrorCandidateIndex(file.filename) != null) return false;
                // A hashless F card is §8.2's delta deletion marker. It has no
                // content to compare, so it can never prove a tree.
                const want = card.hash orelse return false;
                const got = file.hash orelse return false;
                if (!self.mirrorHashMatches(want, got)) return false;
                self.mirror_census.f_cards_compared += 1;
            }
            return true;
        }

        /// `mirrorFilesMatch` against a just-built root of either shape. A flat
        /// root already IS the file set; a tree root is walked through the
        /// ordinary §5.1 enumeration seam against the commit-local staging
        /// store, which is the only place its S nodes exist yet.
        fn mirrorTreeMatches(
            self: *Self,
            cards: []const artifact.FCard,
            root: editor.RootView,
            staged: *StagingStore,
        ) !bool {
            switch (root) {
                .flat => |files| return self.mirrorFilesMatch(cards, files),
                .tree => |subs| {
                    // `Manifest.flattenTree` asserts a non-empty descriptor
                    // run, and the editor is not contractually forbidden from
                    // ever emitting an empty one. The answer for a tree with no
                    // descriptors is known -- no files -- so state it here
                    // rather than leave a shipped assert on repository input.
                    if (subs.len == 0) return self.mirrorFilesMatch(cards, &.{});
                    var resolver = StagedSubResolver{ .gpa = self.gpa, .staged = staged };
                    defer resolver.deinit();
                    var walked = treeWalkShell(self.gpa, subs);
                    defer walked.deinit();
                    walked.flattenTree(.{
                        .ctx = &resolver,
                        .resolveFn = StagedSubResolver.resolve,
                    }) catch |err| switch (err) {
                        error.OutOfMemory => return error.OutOfMemory,
                        // §5.2's hard failures are all "this tree cannot be
                        // enumerated", which is inconclusive, not an import
                        // fault: the tree was just built by this importer, so
                        // the retained path will rebuild it successfully.
                        // An allocation failure the resolver had to answer
                        // "absent" for is not inconclusive, and silently
                        // retaining on it would hide OOM behind a decision.
                        else => {
                            if (resolver.failure) |failure| {
                                if (failure == error.OutOfMemory) return error.OutOfMemory;
                            }
                            return false;
                        },
                    };
                    return self.mirrorFilesMatch(cards, walked.flattened.?);
                },
            }
        }

        /// Whether `reference` names a commit whose own mirror pair this
        /// import already proved, under the name `expected`.
        ///
        /// `resolveCommitObjectIndex` rather than `resolveCommit`: the proof
        /// lives on the object record, and a parent reached through a tag mark
        /// has no record to carry one. That resolves to "unproven", which is
        /// the correct inconclusive answer rather than an import failure.
        fn mirrorParentProven(self: *const Self, reference: fast_export.ObjectRef, expected: []const u8) bool {
            const index = self.resolveCommitObjectIndex(reference) catch return false;
            const proven = self.objects.items[index].mirror.validated_uuid orelse return false;
            return std.mem.eql(u8, proven, expected);
        }

        /// Whether a `manifest.tags` blob is fossil's branch/tag file,
        /// memoized per artifact name so a blob shared by hundreds of commits
        /// is read and checked once.
        fn mirrorTagsAcceptable(self: *Self, hash: []const u8) !bool {
            if (self.mirror_tags_grammar.get(hash)) |verdict| return verdict;
            const bytes = (try self.loadCandidateBytes(hash)) orelse return false;
            defer self.gpa.free(bytes);
            const verdict = mirrorTagsGrammar(bytes);
            if (self.artifactKey(hash)) |key| {
                try self.mirror_tags_grammar.put(self.gpa, key, verdict);
            }
            return verdict;
        }

        /// The §5 gates, in the order that makes a failure cheapest to reach.
        /// `root` is the commit's tree with every present candidate already
        /// excluded, which is what the F-card comparison needs.
        fn classifyMirror(
            self: *Self,
            commit: fast_export.Commit,
            track: *const MirrorTrack,
            root: editor.RootView,
            staged: *StagingStore,
        ) !MirrorDecision {
            // 1. Every present candidate is an ordinary file. A directory,
            //    symlink, executable or gitlink is not what fossil writes.
            for (track.shadow) |slot| {
                const entry = slot orelse continue;
                if (entry.mode != .regular) return MirrorDecision.retain(.non_regular_mode);
            }

            // 2. `manifest.uuid` is exactly one canonical artifact name, with
            //    the canonical single trailing LF accepted and nothing else.
            const uuid_bytes = (try self.loadCandidateBytes(track.shadow[candidate_uuid].?.hash)) orelse
                return MirrorDecision.retain(.candidate_unreadable);
            defer self.gpa.free(uuid_bytes);
            const uuid = trimSingleTrailingLf(uuid_bytes);
            if (!artifact.validateName(uuid)) return MirrorDecision.retain(.uuid_syntax);

            // 3. That name hashes the sterilized `manifest` bytes. This is the
            //    cryptographic core: a project file that merely happens to be
            //    called `manifest` cannot satisfy it.
            const manifest_bytes = (try self.loadCandidateBytes(track.shadow[candidate_manifest].?.hash)) orelse
                return MirrorDecision.retain(.candidate_unreadable);
            defer self.gpa.free(manifest_bytes);
            const sterile = stripMirrorSterilizer(manifest_bytes);
            if (!artifact.verify(uuid, sterile)) return MirrorDecision.retain(.uuid_mismatch);

            // 4. Those bytes parse as a complete flat check-in.
            //    `parseForImport` rather than `parse`: a mirror of a repository
            //    old enough to hold cvs2fossil's trailing-separator manifests
            //    would otherwise retain on every one of them, and this gate is
            //    not where that artifact is judged. Widening what parses cannot
            //    widen what drops -- gate 3 already hashed the same bytes, and
            //    gates 5 to 7 compare the parse against the tree, the parents
            //    and the instant this import independently holds.
            var imported = artifact.parseForImport(self.gpa, sterile) catch |err| switch (err) {
                error.OutOfMemory => return error.OutOfMemory,
                else => return MirrorDecision.retain(.manifest_parse),
            };
            defer imported.deinit(self.gpa);
            const mirror_manifest = &imported.manifest;
            if (mirror_manifest.kind != .manifest or
                mirror_manifest.b != null or
                mirror_manifest.s.len != 0) return MirrorDecision.retain(.manifest_shape);

            // 5. Its file set is the commit's candidate-free tree.
            if (!try self.mirrorTreeMatches(mirror_manifest.f, root, staged)) {
                return MirrorDecision.retain(.tree_mismatch);
            }

            // 6. Its ordered P cards are the proven UUIDs of the ordered Git
            //    parents. A root commit carries none.
            {
                const parent_count = @as(usize, if (commit.from == null) 0 else 1) + commit.merges.len;
                var seen: usize = 0;
                var matched = true;
                for (mirror_manifest.p) |card| {
                    var it = card.hashes();
                    while (it.next()) |token| : (seen += 1) {
                        if (seen >= parent_count) {
                            matched = false;
                            break;
                        }
                        const reference = if (seen == 0 and commit.from != null)
                            commit.from.?
                        else
                            commit.merges[seen - @as(usize, if (commit.from == null) 0 else 1)];
                        if (!self.mirrorParentProven(reference, token)) {
                            matched = false;
                            break;
                        }
                    }
                    if (!matched) break;
                }
                if (!matched or seen != parent_count) return MirrorDecision.retain(.parent_unproven);
            }

            // 7. Its D card is the GIT COMMITTER instant at whole-second
            //    precision -- deliberately not the `--attribution` selection,
            //    which changes what Zit's own D card says without changing
            //    what the mirror recorded.
            {
                const card = mirror_manifest.d orelse return MirrorDecision.retain(.timestamp_mismatch);
                var expected_buf: [19]u8 = undefined;
                const expected = formatWriterTimestamp(commit.committer.timestamp, &expected_buf) catch
                    return MirrorDecision.retain(.timestamp_mismatch);
                if (!mirrorTimestampMatches(card.timestamp, expected)) {
                    return MirrorDecision.retain(.timestamp_mismatch);
                }
            }

            // 8. `manifest.tags` is a DEPENDENT member: it is dropped only
            //    alongside a pair that passed every gate above, and only when
            //    its own bytes are fossil's branch/tag file. A malformed one
            //    keeps the whole set rather than a strict subset of it.
            if (track.shadow[candidate_tags]) |tags| {
                if (!try self.mirrorTagsAcceptable(tags.hash)) {
                    return MirrorDecision.retain(.tags_malformed);
                }
            }

            return .{ .omit = true, .uuid = try self.gpa.dupe(u8, uuid) };
        }

        /// One entry's content facts, from the table if the import ingested it
        /// -- which it always did -- and from the log if it somehow did not.
        ///
        /// The fallback exists so a table miss degrades to slow rather than to
        /// wrong: a digest that silently skipped an entry would verify a
        /// packed generation against an incomplete description of itself.
        fn contentFacts(self: *Self, name: []const u8) !BlobFacts {
            if (self.blob_facts.getPtr(name)) |facts| return facts.*;
            self.work.tree_digest_reloads += 1;
            const bytes = (try self.loadCandidateBytes(name)) orelse return error.MalformedNode;
            defer self.gpa.free(bytes);
            var facts: BlobFacts = .{
                .alternate = undefined,
                .content = undefined,
                .length = bytes.len,
                .oid = null,
            };
            alternateContentDigest(self.format.hash_algo, bytes, &facts.alternate);
            std.crypto.hash.sha2.Sha256.hash(bytes, &facts.content, .{});
            return facts;
        }

        /// The normalized-tree digest of one commit's emitted file set.
        ///
        /// Path, permission and content only: not the artifact names, not the
        /// root shape, not the S-card partition. That is the whole point --
        /// the same files at the same paths digest identically whether the
        /// builder chose a flat root or a tree, so the two shapes are provably
        /// the same repository content and a repack cannot change the answer.
        fn normalizedTreeDigest(self: *Self, files: []const artifact.FCard) !Digest {
            // Canonical order is the enumeration's contract, and it is what
            // makes the digest a set identity rather than a listing order.
            // Both producers here already guarantee it; the builder asserts it.
            var builder = TreeDigestBuilder.init();
            for (files) |card| {
                const name = card.hash orelse return error.MalformedNode;
                const facts = try self.contentFacts(name);
                builder.entry(card.filename, card.mode, facts.length, facts.content);
                self.work.tree_digest_entries += 1;
            }
            return builder.final();
        }

        /// `normalizedTreeDigest` over a just-built root of either shape. A
        /// tree root is walked through the same §5.1 enumeration seam the
        /// classifier uses, against the commit-local staging store its S nodes
        /// still live in.
        fn rootTreeDigest(self: *Self, root: editor.RootView, staged: *StagingStore) !Digest {
            switch (root) {
                .flat => |files| return self.normalizedTreeDigest(files),
                .tree => |subs| {
                    // Same guard as `mirrorTreeMatches`, same reason: an empty
                    // descriptor run digests as the empty tree, which is a
                    // pinned vector, not a panic.
                    if (subs.len == 0) return self.normalizedTreeDigest(&.{});
                    var resolver = StagedSubResolver{ .gpa = self.gpa, .staged = staged };
                    defer resolver.deinit();
                    var walked = treeWalkShell(self.gpa, subs);
                    defer walked.deinit();
                    walked.flattenTree(.{
                        .ctx = &resolver,
                        .resolveFn = StagedSubResolver.resolve,
                    }) catch |err| switch (err) {
                        error.OutOfMemory => return error.OutOfMemory,
                        // Unlike the classifier, this has no safe inconclusive
                        // answer: a tree this importer just built and cannot
                        // enumerate is a defect in the tree, and publishing it
                        // undescribed is what the digest exists to prevent.
                        // An allocation failure inside the resolver is not
                        // that defect, and must keep its own identity.
                        else => {
                            if (resolver.failure) |failure| return failure;
                            return error.MalformedNode;
                        },
                    };
                    return self.normalizedTreeDigest(walked.flattened.?);
                },
            }
        }

        /// One commit's provenance digest: its Git identity and ordered
        /// parents, the attribution this import selected, its normalized tree,
        /// its mirror decision with the OIDs that decision was about, and the
        /// Zit check-in it became.
        ///
        /// The check-in name alone would not do. Two imports of the same
        /// commit under different `--attribution` or different root shapes
        /// produce different check-in names for identical Git history, and an
        /// import that wrongly dropped a mirror candidate would produce a
        /// perfectly self-consistent check-in. This covers the mapping, not
        /// just its result.
        fn commitProvenanceDigest(
            self: *Self,
            commit: fast_export.Commit,
            parent_oids: []const []const u8,
            state: *const MirrorState,
            decision: MirrorDecisionKind,
            reason: MirrorRetainReason,
            tree_digest: Digest,
            checkin: []const u8,
        ) Digest {
            const attributed = switch (self.attribution) {
                .committer => commit.committer,
                .author => commit.author,
            };
            // Fixed width: `mirror_candidate_names` is the complete candidate
            // set, so the run can never be longer than it is.
            var candidates: [mirror_candidate_names.len]ProvenanceCandidate = undefined;
            var present: usize = 0;
            for (state.entries, mirror_candidate_names) |slot, path| {
                const entry = slot orelse continue;
                candidates[present] = .{
                    .path = path,
                    .name = entry.hash,
                    .oid = self.blobOid(entry.hash) orelse "",
                };
                present += 1;
            }
            return provenanceDigestOf(.{
                .oid = commit.original_oid orelse "",
                .parent_oids = parent_oids,
                .attribution = @tagName(self.attribution),
                .identity_name = attributed.name,
                .identity_email = attributed.email,
                .identity_timestamp = attributed.timestamp,
                .identity_zone_minutes = attributed.timezone_offset_minutes,
                .tree_digest = tree_digest,
                .decision = @tagName(decision),
                .reason = if (decision == .retained) @tagName(reason) else "",
                .candidates = candidates[0..present],
                .checkin = checkin,
            });
        }

        /// The Git OID of the commit `reference` names, or the empty string
        /// when the stream carried none. Unresolvable is not an import error
        /// here: `ingestCommit` has already resolved every parent it needs,
        /// and a reference this cannot follow simply has no OID to record.
        fn parentOid(self: *const Self, reference: fast_export.ObjectRef) []const u8 {
            const index = self.resolveCommitObjectIndex(reference) catch return "";
            return self.objects.items[index].oid orelse "";
        }

        /// Counts one retained reference per emitted tree entry. Every entry
        /// enters a tree through an upsert, and an omitted candidate is never
        /// upserted into the emitted list, so an artifact reaches a zero count
        /// exactly when nothing but omitted candidates ever named it.
        ///
        /// An upsert a later command deletes still counts. That direction is
        /// safe: it can only keep an artifact out of the drop set.
        fn recordRetainedReferences(self: *Self, commands: []const editor.TreeCommand) !void {
            for (commands) |command| {
                const card = switch (command) {
                    .upsert => |value| value,
                    else => continue,
                };
                const hash = card.hash orelse continue;
                const key = self.artifactKey(hash) orelse continue;
                const found = try self.mirror_retained_refs.getOrPut(self.gpa, key);
                if (!found.found_existing) found.value_ptr.* = 0;
                found.value_ptr.* += 1;
            }
        }

        /// Records every present candidate of a validated commit as a
        /// droppable-if-unreferenced artifact.
        ///
        /// Each one also gets an explicit zero in the reference table, so a
        /// name that reaches the drop set has been *counted* zero rather than
        /// merely not found. Absence and zero are the same number but not the
        /// same evidence, and only the counted one licenses a delete.
        fn recordOmittedCandidates(self: *Self, track: *const MirrorTrack) !void {
            for (track.shadow) |slot| {
                const entry = slot orelse continue;
                const key = self.artifactKey(entry.hash) orelse continue;
                const counted = try self.mirror_retained_refs.getOrPut(self.gpa, key);
                if (!counted.found_existing) counted.value_ptr.* = 0;
                const found = try self.mirror_candidates.getOrPut(self.gpa, key);
                if (!found.found_existing) {
                    found.value_ptr.* = {};
                    self.mirror_census.candidate_artifacts += 1;
                }
            }
        }

        /// The candidate state a retained commit hands to its children, read
        /// back out of the tree it actually emitted. A retained commit emits
        /// the complete Git tree, so three lookups are exact -- including for
        /// the rename and copy shapes the command bookkeeping declines to model.
        fn mirrorStateFromTree(self: *Self, root: editor.RootView) !MirrorState {
            var state = MirrorState{};
            errdefer state.deinit(self.gpa);
            for (mirror_candidate_names, 0..) |name, index| {
                // `lookup` reuses one arena per call, so each card is copied
                // out before the next lookup invalidates it.
                const card = (try self.tree_editor.lookup(root, name)) orelse continue;
                const hash = card.hash orelse continue;
                // The copy completes BEFORE the slot becomes non-null.
                // Assigning the literal directly writes the payload in place,
                // and an optimizer is free to set the optional's tag before
                // the failing `dupe` inside it ever returns -- leaving the
                // errdefer below to free an uninitialized pointer.
                const owned = try self.gpa.dupe(u8, hash);
                state.entries[index] = .{ .hash = owned, .mode = card.mode };
            }
            return state;
        }

        /// The candidate state a validated commit hands to its children: the
        /// Git truth the classifier just proved, plus the UUID that proves it.
        fn mirrorStateFromTrack(self: *Self, track: *const MirrorTrack, uuid: []const u8) !MirrorState {
            var state = MirrorState{ .omitted = true };
            errdefer state.deinit(self.gpa);
            for (track.shadow, 0..) |slot, index| {
                const entry = slot orelse continue;
                // Two steps for the reason `mirrorStateFromTree` spells out.
                const owned = try self.gpa.dupe(u8, entry.hash);
                state.entries[index] = .{ .hash = owned, .mode = entry.mode };
            }
            state.validated_uuid = try self.gpa.dupe(u8, uuid);
            return state;
        }

        pub fn mirrorCensus(self: *const Self) MirrorCensus {
            return self.mirror_census;
        }

        /// Artifact names used only by validated omitted candidates, sorted.
        ///
        /// Every name here has a zero retained-reference count, so removing it
        /// cannot make any emitted tree unreadable. A candidate blob that is
        /// also a real file somewhere -- the same bytes at a retained path, or
        /// a `manifest.tags` body shared with a kept commit -- has a nonzero
        /// count and stays.
        pub fn mirrorDropNames(self: *const Self, gpa: std.mem.Allocator) ![][]u8 {
            var names: std.ArrayList([]u8) = .empty;
            errdefer {
                for (names.items) |name| gpa.free(name);
                names.deinit(gpa);
            }
            var it = self.mirror_candidates.keyIterator();
            while (it.next()) |key| {
                // A counted zero, not a missing key. `recordOmittedCandidates`
                // seeds one for every candidate it records, so absence here
                // means the accounting never ran for this name -- which is the
                // one state that must never authorize a delete.
                const count = self.mirror_retained_refs.get(key.*) orelse continue;
                if (count != 0) continue;
                // Two steps, not one expression. `append(gpa, try dupe(...))`
                // evaluates the dupe first, so a growth failure inside `append`
                // leaves a name the list never took ownership of and the
                // errdefer above cannot see -- one leaked artifact name per
                // out-of-memory drop-set capture.
                const name = try gpa.dupe(u8, key.*);
                errdefer gpa.free(name);
                try names.append(gpa, name);
            }
            std.mem.sort([]u8, names.items, {}, struct {
                fn less(_: void, a: []u8, b: []u8) bool {
                    return std.mem.order(u8, a, b) == .lt;
                }
            }.less);
            return names.toOwnedSlice(gpa);
        }

        fn prepareCommitRecord(
            self: *Self,
            commit: fast_export.Commit,
            hash: []const u8,
            first_parent_index: ?usize,
            tree_height: u8,
        ) !ImportedObject {
            try self.objects.ensureUnusedCapacity(self.gpa, 1);
            const oid = if (commit.original_oid) |value| try self.gpa.dupe(u8, value) else null;
            errdefer if (oid) |value| self.gpa.free(value);
            const owned_hash = try self.gpa.dupe(u8, hash);
            errdefer self.gpa.free(owned_hash);
            var author = try cloneIdentity(self.gpa, commit.author);
            errdefer author.deinit(self.gpa);
            var committer = try cloneIdentity(self.gpa, commit.committer);
            errdefer committer.deinit(self.gpa);
            return .{
                .oid = oid,
                .hash = owned_hash,
                .first_parent_index = first_parent_index,
                .tree_height = tree_height,
                .author = author,
                .committer = committer,
                .is_merge = commit.merges.len != 0,
                // Handed over by the caller, which owns the resolved parent
                // runs and must not lose them to a half-built record.
                .parents = &.{},
                .parent_oids = &.{},
                // Filled by the caller, which owns the classified state and
                // the digests taken over it.
                .mirror = .{},
                .tree_digest = @splat(0),
                .provenance_digest = @splat(0),
                .decision = .none,
                .retain_reason = .no_candidates,
            };
        }

        fn prepareRef(self: *Self, source: []const u8, target: ?[]const u8, origin: RefOrigin) !PendingRef {
            if (self.ref_index.get(source)) |index| {
                return .{ .existing = .{
                    .index = index,
                    .target = if (target) |value| try self.gpa.dupe(u8, value) else null,
                    .origin = origin,
                } };
            }

            try self.ref_states.ensureUnusedCapacity(self.gpa, 1);
            try self.ref_index.ensureUnusedCapacity(self.gpa, 1);
            try self.canonical_ref_index.ensureUnusedCapacity(self.gpa, 1);
            const owned_source = try self.gpa.dupe(u8, source);
            errdefer self.gpa.free(owned_source);
            const canonical = try canonicalRef(self.gpa, source);
            errdefer self.gpa.free(canonical);
            const owned_target = if (target) |value| try self.gpa.dupe(u8, value) else null;
            errdefer if (owned_target) |value| self.gpa.free(value);
            return .{ .new = .{
                .source = owned_source,
                .canonical = canonical,
                .target = owned_target,
                .origin = origin,
            } };
        }

        fn setRef(self: *Self, source: []const u8, target: ?[]const u8, origin: RefOrigin) !void {
            var pending = try self.prepareRef(source, target, origin);
            pending.publish(self);
        }

        /// Names the partner `state` collided with before refusing. The scan is
        /// linear over ref states, which is affordable exactly once on a path
        /// that is about to abandon the whole import.
        fn refuseRefCollision(self: *Self, state: RefState) error{CanonicalRefCollision} {
            for (self.ref_states.items) |other| {
                if (other.target == null) continue;
                if (std.mem.eql(u8, other.source, state.source)) continue;
                if (!std.mem.eql(u8, other.canonical, state.canonical)) continue;
                // `state` is the outer loop's first colliding ref state, so it
                // is the earlier of the pair; `other` is the partner the scan
                // found. Reporting them in that order matches the order the
                // source repository declares them in.
                self.ref_collision = .{
                    .first_source = state.source,
                    .second_source = other.source,
                    .canonical = state.canonical,
                };
                break;
            }
            return error.CanonicalRefCollision;
        }

        pub fn finalizeRefs(self: *Self, options: FinalizeOptions) !FinalizedRefs {
            var refs: std.ArrayList(FinalizedRef) = .empty;
            errdefer {
                for (refs.items) |mapping| {
                    self.gpa.free(mapping.source);
                    self.gpa.free(mapping.canonical);
                    self.gpa.free(mapping.target);
                }
                refs.deinit(self.gpa);
            }
            for (self.ref_states.items) |state| {
                const target = state.target orelse continue;
                const canonical_state = self.canonical_ref_index.get(state.canonical).?;
                if (canonical_state.active_count > 1) return self.refuseRefCollision(state);
                const canonical = try self.gpa.dupe(u8, state.canonical);
                var canonical_owned = true;
                errdefer if (canonical_owned) self.gpa.free(canonical);
                const source = try self.gpa.dupe(u8, state.source);
                var source_owned = true;
                errdefer if (source_owned) self.gpa.free(source);
                const owned_target = try self.gpa.dupe(u8, target);
                var target_owned = true;
                errdefer if (target_owned) self.gpa.free(owned_target);
                try refs.append(self.gpa, .{
                    .source = source,
                    .canonical = canonical,
                    .target = owned_target,
                });
                canonical_owned = false;
                source_owned = false;
                target_owned = false;
            }

            const primary_source = blk: {
                if (options.default_branch) |requested| {
                    if (requested.len == 0) return error.InvalidPrimaryBranch;
                    for (refs.items) |mapping| {
                        if (std.mem.startsWith(u8, mapping.source, "refs/heads/") and
                            std.mem.eql(u8, mapping.source["refs/heads/".len..], requested)) break :blk requested;
                    }
                    return error.InvalidPrimaryBranch;
                }
                for (refs.items) |mapping| {
                    if (std.mem.eql(u8, mapping.source, "refs/heads/main")) break :blk "main";
                }
                for (refs.items) |mapping| {
                    if (std.mem.startsWith(u8, mapping.source, "refs/heads/")) break :blk mapping.source["refs/heads/".len..];
                }
                return error.InvalidPrimaryBranch;
            };
            const primary_branch = try self.gpa.dupe(u8, primary_source);
            errdefer self.gpa.free(primary_branch);

            var controls: std.ArrayList([]u8) = .empty;
            errdefer {
                for (controls.items) |bytes| self.gpa.free(bytes);
                controls.deinit(self.gpa);
            }
            const heads = "refs/heads/";
            try self.emitBranchControls(&controls, refs.items, primary_branch);
            for (refs.items) |mapping| {
                var target_manifest = try self.loadParentRoot(mapping.target);
                defer target_manifest.deinit(self.gpa);
                const timestamp = if (target_manifest.manifest.d) |card| card.timestamp else "1970-01-01T00:00:00";
                const login = if (target_manifest.manifest.u) |card| card.login else "git-import";
                {
                    const canonical_bytes = try makeSymbolicControl(self.gpa, mapping.target, mapping.canonical, timestamp, login);
                    errdefer self.gpa.free(canonical_bytes);
                    try controls.append(self.gpa, canonical_bytes);
                }

                if (std.mem.startsWith(u8, mapping.source, heads) and
                    std.mem.eql(u8, mapping.source[heads.len..], primary_branch))
                {
                    const primary_alias = try std.fmt.allocPrint(self.gpa, "sym-{s}", .{primary_branch});
                    defer self.gpa.free(primary_alias);
                    const alias_bytes = try makeSymbolicControl(self.gpa, mapping.target, primary_alias, timestamp, login);
                    errdefer self.gpa.free(alias_bytes);
                    try controls.append(self.gpa, alias_bytes);
                }
            }

            const provenance_digest = try self.repositoryProvenanceDigest(refs.items);
            var ledger = try self.buildLedger(provenance_digest);
            errdefer ledger.deinit(self.gpa);
            const provenance_jsonl = try self.buildProvenance(refs.items, ledger);
            errdefer self.gpa.free(provenance_jsonl);
            const owned_controls = try controls.toOwnedSlice(self.gpa);
            errdefer {
                for (owned_controls) |bytes| self.gpa.free(bytes);
                self.gpa.free(owned_controls);
            }
            const owned_refs = try refs.toOwnedSlice(self.gpa);
            errdefer {
                for (owned_refs) |mapping| {
                    self.gpa.free(mapping.source);
                    self.gpa.free(mapping.canonical);
                    self.gpa.free(mapping.target);
                }
                self.gpa.free(owned_refs);
            }
            return .{
                .controls = owned_controls,
                .provenance_jsonl = provenance_jsonl,
                .refs = owned_refs,
                .primary_branch = primary_branch,
                .stored_submanifest = self.work.emitted_nodes > 0,
                .ledger = ledger,
            };
        }

        /// ISSUE #26: emits the branch controls that reconstruct the source
        /// repository's branch topology — one per segment root, and no others.
        ///
        /// Which check-in belongs to which branch is decided by `labelBranches`
        /// from the commit graph, never from the ref a commit happened to be
        /// exported under (see `ImportedObject`). Everything below a segment
        /// root inherits its branch by propagation along primary-parent links
        /// (repo-state §5.4), so this is the whole of the branch state the
        /// import writes: the store keeps no per-commit branch table that could
        /// drift from the graph it was derived from.
        ///
        /// The primary branch gets a control at its own parentless root, which
        /// native repositories also carry (§6.2) and the importer used to skip.
        /// Without it a single-branch import produced a repository `zit branch`
        /// showed nothing for, and left every check-in untagged — its branch
        /// supplied by §6.1's default-branch fallback rather than by an actual
        /// tag, which the one reader that deliberately does not honour that
        /// fallback (`openLeafOf`, strict non-membership) then disagreed with.
        fn emitBranchControls(
            self: *Self,
            controls: *std.ArrayList([]u8),
            refs: []const FinalizedRef,
            primary_branch: []const u8,
        ) !void {
            const heads = "refs/heads/";

            // Two Git commits whose translations are byte-identical are ONE
            // check-in, so the branch graph is built over check-ins, not over
            // commits: labelling the duplicates separately would put two
            // `*branch` cards with different values on a single artifact, which
            // repo-state §5.2 has no room for (UNIQUE (rid, tag)) and which no
            // reader could resolve except by mtime luck.
            const node_of_object = try self.gpa.alloc(usize, self.objects.items.len);
            defer self.gpa.free(node_of_object);
            var object_of_node: std.ArrayList(usize) = .empty;
            defer object_of_node.deinit(self.gpa);
            var node_of_hash: std.StringHashMapUnmanaged(usize) = .empty;
            defer node_of_hash.deinit(self.gpa);
            // The map's capacity is a u32, and the commit count is a repository-
            // derived usize. `fast_export.Limits.max_events` is a caller-supplied
            // default rather than a ceiling, and the import path now sets no
            // event limit at all, so nothing upstream keeps this under 2^32.
            // The narrowing is checked here rather than assumed.
            const node_capacity = std.math.cast(u32, self.objects.items.len) orelse return error.TooManyCommits;
            try node_of_hash.ensureTotalCapacity(self.gpa, node_capacity);
            for (self.objects.items, node_of_object, 0..) |object, *node, index| {
                const found = node_of_hash.getOrPutAssumeCapacity(object.hash);
                if (!found.found_existing) {
                    found.value_ptr.* = object_of_node.items.len;
                    try object_of_node.append(self.gpa, index);
                }
                node.* = found.value_ptr.*;
            }

            // Duplicates agree on their parents by construction — a check-in's
            // parent hashes are part of the bytes its own hash covers — so the
            // representative's first parent is every duplicate's first parent.
            const first_parents = try self.gpa.alloc(?usize, object_of_node.items.len);
            defer self.gpa.free(first_parents);
            for (object_of_node.items, first_parents) |index, *slot| {
                slot.* = if (self.objects.items[index].first_parent_index) |parent| node_of_object[parent] else null;
            }
            // …and that construction argument is checked rather than trusted:
            // every object folded onto a node must agree with the node's
            // representative about the node its first parent lands on.
            for (self.objects.items, node_of_object) |object, node| {
                const folded: ?usize = if (object.first_parent_index) |parent| node_of_object[parent] else null;
                std.debug.assert(std.meta.eql(folded, first_parents[node]));
            }

            var branch_heads: std.ArrayList(BranchHead) = .empty;
            defer branch_heads.deinit(self.gpa);
            for (refs) |mapping| {
                if (!std.mem.startsWith(u8, mapping.source, heads)) continue;
                // Every ref target came from `resolveCommit`, which only ever
                // returns the check-in hash of an ingested commit, so a miss
                // means the object table and the ref table disagree. Dropping
                // the head silently would delete a branch from the destination
                // — the exact issue-#26 signature — so the import fails instead.
                const node = node_of_hash.get(mapping.target) orelse return error.UnresolvedBranchHead;
                try branch_heads.append(self.gpa, .{
                    .name = mapping.source[heads.len..],
                    .commit_index = node,
                });
            }

            const labels = try labelBranches(self.gpa, first_parents, branch_heads.items, primary_branch);
            defer self.gpa.free(labels);

            // Deepest segment root first — children strictly before their
            // ancestors, which stream order (parents first) gives by reversal.
            //
            // The order is load-bearing, not cosmetic. A branch root's control
            // is a separate artifact here, where a native branch root carries
            // its tags on the check-in manifest itself and so always applies
            // them directly *before* its parent's set re-propagates into it
            // (repo-state §4.2 step 2 then step 4a). Crosslinking an ancestor's
            // control first inverts that: the ancestor's branch propagates down
            // to the root first, and §5.3's direct application then skips on
            // `existing.mtime >= new.mtime` — so a branch whose root check-in
            // shares a timestamp with its parent, which any two commits made in
            // the same second do, silently loses its own branch and inherits
            // the parent's. Applying the deeper control first makes the row
            // direct (nonzero srcid) before the ancestor's walk reaches it,
            // where §5.5 blocks the overwrite unconditionally and no timestamp
            // comparison is involved.
            //
            // Descending node order gives that only because a first parent
            // always has the smaller index. That is the whole of the argument,
            // and a silent violation of it produces a plausible-looking
            // repository with wrong branch state — the failure mode being fixed
            // here — so it is asserted at the emit site rather than left to the
            // e2e pin alone.
            var node = object_of_node.items.len;
            while (node > 0) {
                node -= 1;
                std.debug.assert(first_parents[node] == null or first_parents[node].? < node);
                if (!labels[node].is_segment_root) continue;
                const hash = self.objects.items[object_of_node.items[node]].hash;
                var target_manifest = try self.loadParentRoot(hash);
                defer target_manifest.deinit(self.gpa);
                const timestamp = if (target_manifest.manifest.d) |card| card.timestamp else "1970-01-01T00:00:00";
                const login = if (target_manifest.manifest.u) |card| card.login else "git-import";
                // The sym this root leaves behind is its first parent's label:
                // the parent is in another segment, so its branch propagated
                // into this check-in and only a cancel takes it back off.
                const parent_branch: ?[]const u8 = if (first_parents[node]) |parent| labels[parent].branch else null;
                const bytes = try makeBranchControl(self.gpa, hash, labels[node].branch, parent_branch, timestamp, login);
                errdefer self.gpa.free(bytes);
                try controls.append(self.gpa, bytes);
            }
        }

        fn hasFirstParent(self: *Self, target: []const u8) !bool {
            var root = try self.loadParentRoot(target);
            defer root.deinit(self.gpa);
            return root.manifest.p.len != 0 and root.manifest.p[0].count != 0;
        }

        /// The whole import's provenance digest: every published commit's own
        /// digest in stream order, then the ordered ref and tag mappings.
        ///
        /// Ref and tag order is the source stream's, preserved rather than
        /// sorted: two imports that resolve the same names in a different
        /// order resolved a different repository, and a digest that sorted
        /// them would call those the same.
        fn repositoryProvenanceDigest(self: *const Self, refs: []const FinalizedRef) !Digest {
            // A copy, so finalizing here leaves the running chain untouched
            // and a second `finalizeRefs` produces the same answer.
            var writer = self.provenance_chain;
            // The chain is a bare run of fixed-width commit digests, so it is
            // the one field in this design whose boundary is not framed. Fixing
            // the count closes it here rather than relying on a preimage being
            // hard to find.
            writer.number(self.objects.items.len);
            writer.number(refs.len);
            for (refs) |mapping| {
                writer.field(mapping.source);
                writer.field(mapping.canonical);
                writer.field(mapping.target);
            }
            writer.number(self.tags.items.len);
            for (self.tags.items) |tag| {
                const canonical = try canonicalRef(self.gpa, tag.source);
                defer self.gpa.free(canonical);
                writer.field(tag.source);
                writer.field(canonical);
                writer.field(tag.name);
                writer.field(tag.oid orelse "");
                writer.field(tag.target);
                writer.identity(tag.tagger);
                writer.field(tag.message);
            }
            return writer.final();
        }

        /// Assembles the verification ledger. Every string in it borrows from
        /// this importer, so the ledger is valid exactly as long as the
        /// importer is.
        fn buildLedger(self: *const Self, provenance_digest: Digest) !VerificationLedger {
            const commits = try self.gpa.alloc(LedgerCommit, self.objects.items.len);
            errdefer self.gpa.free(commits);
            for (self.objects.items, commits) |object, *entry| {
                var candidates: [mirror_candidate_names.len]?LedgerCandidate = @splat(null);
                for (object.mirror.entries, mirror_candidate_names, 0..) |slot, path, index| {
                    const present = slot orelse continue;
                    candidates[index] = .{
                        .path = path,
                        .name = present.hash,
                        .oid = self.blobOid(present.hash),
                    };
                }
                entry.* = .{
                    .oid = object.oid,
                    .name = object.hash,
                    .tree_digest = object.tree_digest,
                    .provenance_digest = object.provenance_digest,
                    .decision = object.decision,
                    .reason = object.retain_reason,
                    .candidates = candidates,
                };
            }

            var artifacts: std.ArrayList(LedgerArtifact) = .empty;
            errdefer artifacts.deinit(self.gpa);
            try artifacts.ensureTotalCapacity(self.gpa, self.mirror_candidates.count());
            var it = self.mirror_candidates.keyIterator();
            while (it.next()) |key| {
                // Absence is NOT zero here, for the same reason it is not in
                // `mirrorDropNames`: a missing count means the accounting never
                // ran for this name, which must never read as "safe to drop".
                // The ledger and the drop set have to answer this question the
                // same way -- since packing became mandatory, `dropped` is a
                // claim about what the published store contains, not advice.
                const counted = self.mirror_retained_refs.get(key.*);
                artifacts.appendAssumeCapacity(.{
                    .name = key.*,
                    .retained_references = counted orelse 0,
                    .dropped = counted != null and counted.? == 0,
                });
            }
            std.mem.sort(LedgerArtifact, artifacts.items, {}, struct {
                fn less(_: void, a: LedgerArtifact, b: LedgerArtifact) bool {
                    return std.mem.order(u8, a.name, b.name) == .lt;
                }
            }.less);

            return .{
                .commits = commits,
                .candidates = try artifacts.toOwnedSlice(self.gpa),
                .provenance_digest = provenance_digest,
            };
        }

        /// Deep-copies the ledger, the ordered parent runs and the resolved
        /// refs into one arena, so a pass that runs after this importer is
        /// gone still has something to compare a store against.
        ///
        /// Must be called before the transaction's freeze. Everything it reads
        /// dies with the importer; everything it returns does not.
        pub fn captureWitness(self: *const Self, gpa: std.mem.Allocator, finalized: FinalizedRefs) !ImportWitness {
            var witness: ImportWitness = .{
                .arena_state = std.heap.ArenaAllocator.init(gpa),
                .attribution = self.attribution,
                .commits = &.{},
                .refs = &.{},
                .provenance_digest = finalized.ledger.provenance_digest,
                .primary_branch = "",
            };
            // One arena, so a failure part-way through frees every partial
            // copy at once rather than through a chain of errdefers that a
            // later field addition would have to remember to extend.
            errdefer witness.arena_state.deinit();
            const arena = witness.arena_state.allocator();
            witness.primary_branch = try arena.dupe(u8, finalized.primary_branch);

            const commits = try arena.alloc(WitnessCommit, self.objects.items.len);
            for (self.objects.items, finalized.ledger.commits, commits) |object, entry, *out| {
                var candidates: [mirror_candidate_names.len]?WitnessCandidate = @splat(null);
                for (entry.candidates, &candidates) |slot, *destination| {
                    const present = slot orelse continue;
                    destination.* = .{
                        // A static, not a borrow: `path` is an element of
                        // `mirror_candidate_names` and outlives everything.
                        .path = present.path,
                        .name = try arena.dupe(u8, present.name),
                        .oid = if (present.oid) |oid| try arena.dupe(u8, oid) else null,
                    };
                }
                const parents = try arena.alloc([]const u8, object.parents.len);
                for (object.parents, parents) |source, *destination| destination.* = try arena.dupe(u8, source);
                const parent_oids = try arena.alloc([]const u8, object.parent_oids.len);
                for (object.parent_oids, parent_oids) |source, *destination| destination.* = try arena.dupe(u8, source);
                out.* = .{
                    .oid = if (object.oid) |oid| try arena.dupe(u8, oid) else null,
                    .checkin = try arena.dupe(u8, object.hash),
                    .parents = parents,
                    .parent_oids = parent_oids,
                    .author = try cloneWitnessIdentity(arena, object.author),
                    .committer = try cloneWitnessIdentity(arena, object.committer),
                    .tree_digest = entry.tree_digest,
                    .provenance_digest = entry.provenance_digest,
                    .decision = entry.decision,
                    .reason = entry.reason,
                    .candidates = candidates,
                };
            }
            witness.commits = commits;

            const refs = try arena.alloc(WitnessRef, finalized.refs.len);
            for (finalized.refs, refs) |mapping, *out| {
                const state_index = self.ref_index.get(mapping.source);
                out.* = .{
                    .source = try arena.dupe(u8, mapping.source),
                    .canonical = try arena.dupe(u8, mapping.canonical),
                    .target = try arena.dupe(u8, mapping.target),
                    .annotated = if (state_index) |index|
                        self.ref_states.items[index].origin == .annotated_tag
                    else
                        false,
                };
            }
            witness.refs = refs;
            return witness;
        }

        fn appendDigestJson(self: *const Self, out: *std.ArrayList(u8), digest: Digest) !void {
            var buffer: [64]u8 = undefined;
            try appendJsonString(out, self.gpa, formatDigest(digest, &buffer));
        }

        /// The mirror decision one commit's provenance line reports: what was
        /// decided, why when it was a retention, and every candidate the
        /// decision covered -- including the dependent `manifest.tags` member,
        /// which is part of the decision and so part of its record.
        fn appendMirrorJson(self: *const Self, out: *std.ArrayList(u8), entry: LedgerCommit) !void {
            try out.appendSlice(self.gpa, "{\"decision\":\"");
            try out.appendSlice(self.gpa, @tagName(entry.decision));
            try out.appendSlice(self.gpa, "\",\"reason\":");
            if (entry.decision == .retained) {
                try appendJsonString(out, self.gpa, @tagName(entry.reason));
            } else try out.appendSlice(self.gpa, "null");
            try out.appendSlice(self.gpa, ",\"candidates\":[");
            var written: usize = 0;
            for (entry.candidates) |slot| {
                const candidate = slot orelse continue;
                if (written != 0) try out.append(self.gpa, ',');
                written += 1;
                try out.appendSlice(self.gpa, "{\"path\":");
                try appendJsonString(out, self.gpa, candidate.path);
                try out.appendSlice(self.gpa, ",\"zit\":");
                try appendJsonString(out, self.gpa, candidate.name);
                try out.appendSlice(self.gpa, ",\"oid\":");
                if (candidate.oid) |oid| {
                    try appendJsonString(out, self.gpa, oid);
                } else try out.appendSlice(self.gpa, "null");
                try out.append(self.gpa, '}');
            }
            try out.appendSlice(self.gpa, "]}");
        }

        fn buildProvenance(
            self: *const Self,
            refs: []const FinalizedRef,
            ledger: VerificationLedger,
        ) ![]u8 {
            var out: std.ArrayList(u8) = .empty;
            errdefer out.deinit(self.gpa);
            var dropped_artifacts: u64 = 0;
            for (ledger.candidates) |candidate| {
                if (candidate.dropped) dropped_artifacts += 1;
            }
            for (self.objects.items, ledger.commits) |object, entry| {
                const oid = object.oid orelse continue;
                try out.appendSlice(self.gpa, "{\"kind\":\"commit\",\"oid\":");
                try appendJsonString(&out, self.gpa, oid);
                try out.appendSlice(self.gpa, ",\"zit\":");
                try appendJsonString(&out, self.gpa, object.hash);
                try out.appendSlice(self.gpa, ",\"author\":");
                try appendIdentityJson(&out, self.gpa, object.author);
                try out.appendSlice(self.gpa, ",\"committer\":");
                try appendIdentityJson(&out, self.gpa, object.committer);
                try out.appendSlice(self.gpa, ",\"tree_digest\":");
                try self.appendDigestJson(&out, entry.tree_digest);
                try out.appendSlice(self.gpa, ",\"mirror\":");
                try self.appendMirrorJson(&out, entry);
                try out.appendSlice(self.gpa, ",\"provenance_digest\":");
                try self.appendDigestJson(&out, entry.provenance_digest);
                try out.appendSlice(self.gpa, ",\"warning\":null}\n");
            }
            for (self.blobs.items) |blob| {
                const oid = blob.oid orelse continue;
                // Same absence rule as `mirrorDropNames` and the ledger: an
                // uncounted candidate is never reported dropped. This line is
                // read alongside the packed store it ships with, so a
                // `"dropped":true` the store contradicts is a false record.
                const counted = self.mirror_retained_refs.get(blob.hash);
                const retained = counted orelse 0;
                const candidate = self.mirror_candidates.contains(blob.hash);
                const dropped = candidate and counted != null and counted.? == 0;
                try out.appendSlice(self.gpa, "{\"kind\":\"blob\",\"oid\":");
                try appendJsonString(&out, self.gpa, oid);
                try out.appendSlice(self.gpa, ",\"zit\":");
                try appendJsonString(&out, self.gpa, blob.hash);
                try out.appendSlice(self.gpa, ",\"retained_references\":");
                try appendNumber(&out, self.gpa, retained);
                try out.appendSlice(self.gpa, ",\"mirror_candidate\":");
                try out.appendSlice(self.gpa, if (candidate) "true" else "false");
                try out.appendSlice(self.gpa, ",\"dropped\":");
                try out.appendSlice(self.gpa, if (dropped) "true" else "false");
                try out.appendSlice(self.gpa, ",\"warning\":null}\n");
            }
            for (refs) |mapping| {
                const state_index = self.ref_index.get(mapping.source) orelse continue;
                const state = self.ref_states.items[state_index];
                if (state.origin == .annotated_tag) continue;
                try out.appendSlice(self.gpa, "{\"kind\":\"ref\",\"source\":");
                try appendJsonString(&out, self.gpa, mapping.source);
                try out.appendSlice(self.gpa, ",\"canonical\":");
                try appendJsonString(&out, self.gpa, mapping.canonical);
                try out.appendSlice(self.gpa, ",\"zit\":");
                try appendJsonString(&out, self.gpa, mapping.target);
                if (std.mem.startsWith(u8, mapping.source, "refs/tags/")) {
                    try out.appendSlice(self.gpa, ",\"warning\":\"lightweight tag has no annotated metadata\"}\n");
                } else try out.appendSlice(self.gpa, ",\"warning\":null}\n");
            }
            for (self.tags.items) |tag| {
                try out.appendSlice(self.gpa, "{\"kind\":\"tag\",\"source\":");
                try appendJsonString(&out, self.gpa, tag.source);
                const canonical = try canonicalRef(self.gpa, tag.source);
                defer self.gpa.free(canonical);
                try out.appendSlice(self.gpa, ",\"canonical\":");
                try appendJsonString(&out, self.gpa, canonical);
                try out.appendSlice(self.gpa, ",\"name\":");
                try appendJsonString(&out, self.gpa, tag.name);
                try out.appendSlice(self.gpa, ",\"oid\":");
                if (tag.oid) |oid| try appendJsonString(&out, self.gpa, oid) else try out.appendSlice(self.gpa, "null");
                try out.appendSlice(self.gpa, ",\"target_zit\":");
                try appendJsonString(&out, self.gpa, tag.target);
                try out.appendSlice(self.gpa, ",\"tagger\":");
                try appendIdentityJson(&out, self.gpa, tag.tagger);
                try out.appendSlice(self.gpa, ",\"message\":");
                try appendJsonString(&out, self.gpa, tag.message);
                try out.appendSlice(self.gpa, ",\"warning\":null}\n");
            }
            // One trailing record for the facts that belong to the import
            // rather than to any one object. The repository provenance digest
            // covers the ordered refs and tags, so it has nowhere else to sit.
            try out.appendSlice(self.gpa, "{\"kind\":\"summary\",\"commits\":");
            try appendNumber(&out, self.gpa, ledger.commits.len);
            try out.appendSlice(self.gpa, ",\"candidate_artifacts\":");
            try appendNumber(&out, self.gpa, ledger.candidates.len);
            try out.appendSlice(self.gpa, ",\"dropped_artifacts\":");
            try appendNumber(&out, self.gpa, dropped_artifacts);
            try out.appendSlice(self.gpa, ",\"provenance_digest\":");
            try self.appendDigestJson(&out, ledger.provenance_digest);
            try out.appendSlice(self.gpa, ",\"warning\":null}\n");
            return out.toOwnedSlice(self.gpa);
        }

        fn ingestReset(self: *Self, reset: fast_export.Reset) !void {
            const target = if (reset.target) |reference| try self.resolveCommit(reference) else null;
            try self.setRef(reset.ref, target, .reset);
        }

        fn ingestTag(self: *Self, tag: fast_export.Tag) !void {
            if (tag.mark) |mark| {
                if (self.marks.contains(mark)) return error.DuplicateMark;
                try self.marks.ensureUnusedCapacity(self.gpa, 1);
            }
            const target = try self.resolveCommit(tag.target);
            const source = try std.fmt.allocPrint(self.gpa, "refs/tags/{s}", .{tag.name});
            defer self.gpa.free(source);
            try self.tags.ensureUnusedCapacity(self.gpa, 1);
            const owned_source = try self.gpa.dupe(u8, source);
            errdefer self.gpa.free(owned_source);
            const name = try self.gpa.dupe(u8, tag.name);
            errdefer self.gpa.free(name);
            const oid = if (tag.original_oid) |value| try self.gpa.dupe(u8, value) else null;
            errdefer if (oid) |value| self.gpa.free(value);
            const owned_target = try self.gpa.dupe(u8, target);
            errdefer self.gpa.free(owned_target);
            const marked_target = if (tag.mark != null) try self.gpa.dupe(u8, target) else null;
            errdefer if (marked_target) |value| self.gpa.free(value);
            var tagger = try cloneIdentity(self.gpa, tag.tagger);
            errdefer tagger.deinit(self.gpa);
            const message = try self.gpa.dupe(u8, tag.message);
            errdefer self.gpa.free(message);
            var pending_ref = try self.prepareRef(source, target, .annotated_tag);
            errdefer pending_ref.deinit(self.gpa);
            self.tags.appendAssumeCapacity(.{
                .source = owned_source,
                .name = name,
                .oid = oid,
                .target = owned_target,
                .tagger = tagger,
                .message = message,
            });
            pending_ref.publish(self);
            if (tag.mark) |mark| self.marks.putAssumeCapacity(mark, .{ .tagged = marked_target.? });
        }
    };
}

/// An arena copy for the witness. No errdefer: the arena is the unwind.
fn cloneWitnessIdentity(arena: std.mem.Allocator, identity: OwnedIdentity) !WitnessIdentity {
    return .{
        .name = try arena.dupe(u8, identity.name),
        .email = try arena.dupe(u8, identity.email),
        .timestamp = identity.timestamp,
        .timezone_offset_minutes = identity.timezone_offset_minutes,
    };
}

fn cloneIdentity(gpa: std.mem.Allocator, identity: fast_export.Identity) !OwnedIdentity {
    const name = try gpa.dupe(u8, identity.name);
    errdefer gpa.free(name);
    const email = try gpa.dupe(u8, identity.email);
    return .{
        .name = name,
        .email = email,
        .timestamp = identity.timestamp,
        .timezone_offset_minutes = identity.timezone_offset_minutes,
    };
}

fn canonicalRef(gpa: std.mem.Allocator, source: []const u8) ![]u8 {
    const heads = "refs/heads/";
    const tags = "refs/tags/";
    const refs = "refs/";
    const pair = if (std.mem.startsWith(u8, source, heads))
        .{ @as([]const u8, "sym-heads/"), source[heads.len..] }
    else if (std.mem.startsWith(u8, source, tags))
        .{ @as([]const u8, "sym-tags/"), source[tags.len..] }
    else if (std.mem.startsWith(u8, source, refs))
        .{ @as([]const u8, "sym-refs/"), source[refs.len..] }
    else
        return error.InvalidRef;
    const prefix: []const u8 = pair[0];
    const raw: []const u8 = pair[1];

    var out: std.ArrayList(u8) = .empty;
    errdefer out.deinit(gpa);
    try out.appendSlice(gpa, prefix);
    var wrote_component = false;
    var components = std.mem.splitScalar(u8, raw, '/');
    while (components.next()) |component| {
        if (component.len == 0 or std.mem.eql(u8, component, ".")) continue;
        if (std.mem.eql(u8, component, "..")) return error.InvalidRef;
        if (wrote_component) try out.append(gpa, '/');
        try out.appendSlice(gpa, component);
        wrote_component = true;
    }
    if (!wrote_component) return error.InvalidRef;
    return out.toOwnedSlice(gpa);
}

/// A `refs/heads/*` head reduced to what branch labelling needs: the branch
/// name it publishes and the commit it points at.
pub const BranchHead = struct {
    /// The ref with `refs/heads/` stripped — the branch name a control names.
    name: []const u8,
    /// Index into the same commit array `labelBranches` is given.
    commit_index: usize,
};

/// Where one commit lands in the reconstructed branch topology.
pub const BranchLabel = struct {
    /// The branch this commit belongs to. Borrowed from the caller's head
    /// names (or its primary-branch name), and valid only as long as they are.
    branch: []const u8,
    /// True for the deepest commit of a segment — the only check-in that needs
    /// a branch control. Every other commit inherits the branch by propagation
    /// along primary-parent links (repo-state §5.4), so the store holds no
    /// per-commit branch state that could drift.
    is_segment_root: bool,
};

/// Decides which branch each imported commit belongs to.
///
/// `git fast-export` emits every commit exactly once, attributed to whichever
/// ref's traversal reached it first, so the `commit <ref>` header answers "what
/// was the stream emitting under" and never "what branch is this commit on".
/// Git has no canonical branch-of-a-commit either, so the importer has to
/// define one. This is that definition, claiming in priority order:
///
///   1. the primary branch, from its tip down the first-parent chain to the
///      parentless root, taking every commit on the way;
///   2. every other head, in ascending tip depth (ties broken by name, so the
///      result never depends on export order), each walking first parents from
///      its tip until it meets an already-claimed commit or a parentless root;
///   3. any commit still unclaimed inherits its first parent's branch, and an
///      unclaimed parentless commit — an orphan root whose branch git deleted —
///      is labelled with the primary branch and roots its own segment. Without
///      a label nothing propagates into its chain, since propagation needs a
///      primary parent to flow through.
///
/// Merge commits fall out of rule 1 and 2 rather than needing a case: a merge
/// is reached through its first parent, so it stays on the branch it was merged
/// into, matching §5.4's rule that propagation never crosses a merge edge.
///
/// Two heads on one commit is the single degenerate case: only one segment
/// exists, the lexicographically first name claims it, and the other head is
/// represented by its symbolic control alone.
///
/// Rule 3 puts no bound on how many segments carry the primary name: a source
/// with N disconnected orphan roots yields N of them, so the bare primary name
/// resolves by the store's own mtime/least-hash tie-break rather than by
/// anything decided here. That is the honest answer — git deleted the branches
/// those roots were on and there is no name left to recover — but it is a
/// stated limit, not an oversight.
///
/// Pure: no I/O, no store access, nothing retained. The labels are a transient
/// computation consumed to place branch controls and then discarded — the
/// durable representation stays the RFC's propagating-tag machinery.
///
/// `first_parents[i]` is the index of commit `i`'s first parent, or null when
/// it is parentless; parents always precede their children, as fast-export
/// emits them. Caller owns the returned slice.
///
/// Every input rule is rejected rather than asserted, because all of this data
/// descends from a foreign repository's export stream: `InvalidCommitOrder` for
/// a first parent that does not precede its child, `InvalidBranchHead` for a
/// nameless head or one pointing outside the commit array,
/// `DuplicateBranchHead` for two heads publishing one branch name, and
/// `InvalidPrimaryBranch` — the same error `finalizeRefs` already raises — when
/// the primary name is empty or no head publishes it.
pub fn labelBranches(
    gpa: std.mem.Allocator,
    first_parents: []const ?usize,
    heads: []const BranchHead,
    primary_branch: []const u8,
) ![]BranchLabel {
    if (primary_branch.len == 0) return error.InvalidPrimaryBranch;

    const labels = try gpa.alloc(BranchLabel, first_parents.len);
    errdefer gpa.free(labels);
    // An empty branch means "not claimed yet"; git has no empty branch name, so
    // the sentinel can never collide with a real label.
    for (labels) |*label| label.* = .{ .branch = "", .is_segment_root = false };

    // Depth is how many first-parent steps separate a commit from its own
    // parentless root. Parents precede children, so one forward pass suffices.
    const depths = try gpa.alloc(usize, first_parents.len);
    defer gpa.free(depths);
    for (first_parents, depths, 0..) |first_parent, *depth, index| {
        if (first_parent) |parent| {
            if (parent >= index) return error.InvalidCommitOrder;
            depth.* = depths[parent] + 1;
        } else {
            depth.* = 0;
        }
    }

    var primary_head: ?usize = null;
    for (heads) |head| {
        if (head.name.len == 0) return error.InvalidBranchHead;
        if (head.commit_index >= first_parents.len) return error.InvalidBranchHead;
        if (std.mem.eql(u8, head.name, primary_branch)) primary_head = head.commit_index;
    }

    const order = try gpa.alloc(usize, heads.len);
    defer gpa.free(order);
    for (order, 0..) |*slot, index| slot.* = index;

    // Two heads publishing ONE name is rejected, not resolved. It would give
    // one branch two segments, and a segment root whose first parent already
    // carries the same name — a `*branch NAME` card whose cancel targets the
    // very `*sym-NAME` it establishes, which `composeCommitTags` asserts
    // against. Today's caller cannot produce it (`ref_index` keys refs by
    // source), but that proof lives in another function; this states the rule
    // where the code depends on it.
    std.mem.sort(usize, order, heads, NameOrder.before);
    for (order[0..], 0..) |head_index, position| {
        if (position == 0) continue;
        if (std.mem.eql(u8, heads[head_index].name, heads[order[position - 1]].name)) {
            return error.DuplicateBranchHead;
        }
    }

    // Rule 1: the primary branch claims before anything else, so shared history
    // below a fork stays with the branch that continues through it.
    const primary_tip = primary_head orelse return error.InvalidPrimaryBranch;
    claimSegment(labels, first_parents, primary_tip, primary_branch);

    // Rule 2: every other head, shallowest tip first. A head whose tip sits on
    // a deeper head's chain must claim its own segment before that deeper head
    // can swallow it, or it would end up with no control at all.
    std.mem.sort(usize, order, ClaimOrder{ .heads = heads, .depths = depths }, ClaimOrder.before);
    for (order) |head_index| {
        const head = heads[head_index];
        if (std.mem.eql(u8, head.name, primary_branch)) continue;
        claimSegment(labels, first_parents, head.commit_index, head.name);
    }

    // Rule 3: whatever no head reached. A parentless commit here is an orphan
    // root whose branch git deleted; labelling it primary invents no branch
    // name and keeps a tag propagating through its chain.
    for (labels, first_parents, 0..) |*label, first_parent, index| {
        if (label.branch.len != 0) continue;
        if (first_parent) |parent| {
            std.debug.assert(parent < index);
            std.debug.assert(labels[parent].branch.len != 0);
            label.branch = labels[parent].branch;
        } else {
            label.branch = primary_branch;
            label.is_segment_root = true;
        }
    }
    // Postconditions. The second is the headline symptom of issue #26 stated as
    // an invariant: a non-empty history that produces no segment root emits no
    // branch control, which is the repository that imported with no branches at
    // all. Both name only locals, so they are internal invariants about this
    // function's own output, not input validation wearing an assert.
    var segment_roots: usize = 0;
    for (labels) |label| {
        std.debug.assert(label.branch.len != 0);
        if (label.is_segment_root) segment_roots += 1;
    }
    std.debug.assert(labels.len == 0 or segment_roots != 0);
    return labels;
}

/// Name order alone, for the duplicate-head check. Separate from `ClaimOrder`
/// because that one's primary key is depth, which puts two same-named heads on
/// different commits far apart.
const NameOrder = struct {
    fn before(heads: []const BranchHead, lhs: usize, rhs: usize) bool {
        return std.mem.order(u8, heads[lhs].name, heads[rhs].name) == .lt;
    }
};

/// Claim order for rule 2: ascending tip depth, ties broken by name so that two
/// heads on one commit resolve the same way no matter what order the export
/// stream declared them in.
const ClaimOrder = struct {
    heads: []const BranchHead,
    depths: []const usize,

    fn before(self: ClaimOrder, lhs: usize, rhs: usize) bool {
        const lhs_depth = self.depths[self.heads[lhs].commit_index];
        const rhs_depth = self.depths[self.heads[rhs].commit_index];
        if (lhs_depth != rhs_depth) return lhs_depth < rhs_depth;
        return std.mem.order(u8, self.heads[lhs].name, self.heads[rhs].name) == .lt;
    }
};

/// Walks first parents down from `tip`, labelling every commit no earlier claim
/// owns and marking the deepest one reached as the segment root. Claims nothing
/// when `tip` is already owned — the two-heads-on-one-commit case. A first
/// parent always precedes its child, so the walk strictly descends and ends;
/// `labelBranches` rejects the input that would break that, and the assert
/// below re-establishes it here rather than leaving an unbounded `while` whose
/// only bound is stated in a different function. Without it a violation hangs
/// the import with no diagnostic; with it, it crashes.
fn claimSegment(labels: []BranchLabel, first_parents: []const ?usize, tip: usize, branch: []const u8) void {
    var cursor = tip;
    var root: ?usize = null;
    while (labels[cursor].branch.len == 0) {
        labels[cursor].branch = branch;
        root = cursor;
        const next = first_parents[cursor] orelse break;
        std.debug.assert(next < cursor);
        cursor = next;
    }
    if (root) |index| labels[index].is_segment_root = true;
}

/// The control artifact that starts `branch` at `target` — the check-in a
/// branch's segment is rooted at.
///
/// The card set is composed by `artifact.composeCommitTags`, the same unit
/// `zit commit --branch` and `zit amend --branch` use, so an imported branch
/// root is tagged exactly as a native one: the repo-state §6.2 PAIR (`*branch
/// NAME` with its propagating `*sym-NAME`) plus a cancel for the sym it leaves
/// behind. The importer used to hand-roll a lone `*branch` card, which left
/// bare branch names unresolvable and every fork still answering to its
/// parent's name (issue #26); one composer is the reason that cannot drift
/// back.
///
/// `parent_branch` is the branch of the root's first parent, or null when it
/// has none (the primary root, and orphan roots). Exactly one sym propagates
/// into any check-in — the only propagating tags in an imported store are the
/// §6.2 pair, and one branch control per segment means one pair — so the
/// parent's whole active sym set is that single name.
fn makeBranchControl(
    gpa: std.mem.Allocator,
    target: []const u8,
    branch: []const u8,
    parent_branch: ?[]const u8,
    timestamp: []const u8,
    login: []const u8,
) ![]u8 {
    var scratch = std.heap.ArenaAllocator.init(gpa);
    defer scratch.deinit();
    const arena = scratch.allocator();

    var parent_sym: [1][]const u8 = undefined;
    var parent_syms: []const []const u8 = &.{};
    if (parent_branch) |name| {
        // A segment root's first parent is always in a DIFFERENT segment (the
        // claim walk stops at the first already-claimed commit, and
        // `labelBranches` rejects two heads publishing one name), so the cancel
        // never targets the sym this very card establishes — which
        // `composeCommitTags` asserts, and which is why that rejection is a
        // rejection and not a resolution.
        parent_sym[0] = try std.mem.concat(arena, u8, &.{ artifact.sym_tag_prefix, name });
        parent_syms = parent_sym[0..1];
    }
    const cards = try artifact.composeCommitTags(arena, .{ .branch = branch, .parent_syms = parent_syms });
    artifact.retargetTCards(cards, target);

    var manifest: artifact.Manifest = .{
        .arena_state = std.heap.ArenaAllocator.init(gpa),
        .kind = .control,
        .a = null,
        .b = null,
        .c = null,
        .d = .{ .timestamp = timestamp },
        .e = null,
        .g = null,
        .h = null,
        .i = null,
        .k = null,
        .l = null,
        .n = null,
        .r = null,
        .u = .{ .login = login },
        .z = null,
        .w = null,
        .f = &.{},
        .j = &.{},
        .m = &.{},
        .p = &.{},
        .q = &.{},
        .s = &.{},
        .t = cards,
    };
    defer manifest.deinit();
    return artifact.create(&manifest, gpa);
}

fn makeSymbolicControl(
    gpa: std.mem.Allocator,
    target: []const u8,
    name: []const u8,
    timestamp: []const u8,
    login: []const u8,
) ![]u8 {
    const cards = [_]artifact.TCard{.{
        .sign = .add,
        .name = name,
        .target = target,
        .value = null,
    }};
    var manifest: artifact.Manifest = .{
        .arena_state = std.heap.ArenaAllocator.init(gpa),
        .kind = .control,
        .a = null,
        .b = null,
        .c = null,
        .d = .{ .timestamp = timestamp },
        .e = null,
        .g = null,
        .h = null,
        .i = null,
        .k = null,
        .l = null,
        .n = null,
        .r = null,
        .u = .{ .login = login },
        .z = null,
        .w = null,
        .f = &.{},
        .j = &.{},
        .m = &.{},
        .p = &.{},
        .q = &.{},
        .s = &.{},
        .t = &cards,
    };
    defer manifest.deinit();
    return artifact.create(&manifest, gpa);
}

fn appendJsonString(out: *std.ArrayList(u8), gpa: std.mem.Allocator, value: []const u8) !void {
    if (!std.unicode.utf8ValidateSlice(value)) return error.InvalidUtf8;
    try out.append(gpa, '"');
    const hex = "0123456789abcdef";
    for (value) |byte| switch (byte) {
        '"' => try out.appendSlice(gpa, "\\\""),
        '\\' => try out.appendSlice(gpa, "\\\\"),
        '\n' => try out.appendSlice(gpa, "\\n"),
        '\r' => try out.appendSlice(gpa, "\\r"),
        '\t' => try out.appendSlice(gpa, "\\t"),
        0...8, 11...12, 14...0x1f => {
            try out.appendSlice(gpa, "\\u00");
            try out.append(gpa, hex[byte >> 4]);
            try out.append(gpa, hex[byte & 0x0f]);
        },
        else => try out.append(gpa, byte),
    };
    try out.append(gpa, '"');
}

fn appendNumber(out: *std.ArrayList(u8), gpa: std.mem.Allocator, value: anytype) !void {
    var buffer: [32]u8 = undefined;
    const text = try std.fmt.bufPrint(&buffer, "{d}", .{value});
    try out.appendSlice(gpa, text);
}

fn appendIdentityJson(out: *std.ArrayList(u8), gpa: std.mem.Allocator, identity: OwnedIdentity) !void {
    try out.appendSlice(gpa, "{\"name\":");
    try appendJsonString(out, gpa, identity.name);
    try out.appendSlice(gpa, ",\"email\":");
    try appendJsonString(out, gpa, identity.email);
    try out.appendSlice(gpa, ",\"timestamp\":");
    try appendNumber(out, gpa, identity.timestamp);
    try out.appendSlice(gpa, ",\"timezone_offset_minutes\":");
    try appendNumber(out, gpa, identity.timezone_offset_minutes);
    try out.append(gpa, '}');
}

fn formatWriterTimestamp(epoch: i64, out: *[19]u8) ![]const u8 {
    // 0000-01-01T00:00:00 through 9999-12-31T23:59:59 are the complete
    // four-digit writer range. Fast-export timestamps outside it have no
    // canonical Zit D-card representation.
    const min_writer_epoch: i64 = -62167219200;
    const max_writer_epoch: i64 = 253402300799;
    if (epoch < min_writer_epoch or epoch > max_writer_epoch) return error.InvalidTimestamp;

    const days = @divFloor(epoch, @as(i64, 86400));
    const rem = @mod(epoch, @as(i64, 86400));
    const z = days + 719468;
    const era = @divFloor(z, @as(i64, 146097));
    const doe = z - era * 146097;
    const yoe = @divFloor(doe - @divFloor(doe, @as(i64, 1460)) + @divFloor(doe, @as(i64, 36524)) - @divFloor(doe, @as(i64, 146096)), @as(i64, 365));
    const doy = doe - (365 * yoe + @divFloor(yoe, @as(i64, 4)) - @divFloor(yoe, @as(i64, 100)));
    const mp = @divFloor(5 * doy + 2, @as(i64, 153));
    const day = doy - @divFloor(153 * mp + 2, @as(i64, 5)) + 1;
    const month = if (mp < 10) mp + 3 else mp - 9;
    const year = yoe + era * 400 + @as(i64, if (month <= 2) 1 else 0);
    if (year < 0 or year > 9999) return error.InvalidTimestamp;

    put2(out[0..2], @intCast(@divFloor(year, @as(i64, 100))));
    put2(out[2..4], @intCast(@mod(year, @as(i64, 100))));
    out[4] = '-';
    put2(out[5..7], @intCast(month));
    out[7] = '-';
    put2(out[8..10], @intCast(day));
    out[10] = 'T';
    put2(out[11..13], @intCast(@divFloor(rem, @as(i64, 3600))));
    out[13] = ':';
    put2(out[14..16], @intCast(@divFloor(@mod(rem, @as(i64, 3600)), @as(i64, 60))));
    out[16] = ':';
    put2(out[17..19], @intCast(@mod(rem, @as(i64, 60))));
    return out[0..19];
}

fn canonicalOid(oid: ?[]const u8, out: *[64]u8) !?[]const u8 {
    const raw = oid orelse return null;
    return try canonicalOidBytes(raw, out);
}

fn canonicalOidBytes(oid: []const u8, out: *[64]u8) ![]const u8 {
    if (oid.len == 0 or oid.len > out.len) return error.InvalidOid;
    for (oid, 0..) |byte, index| {
        out[index] = switch (byte) {
            '0'...'9', 'a'...'f' => byte,
            'A'...'F' => byte + ('a' - 'A'),
            else => return error.InvalidOid,
        };
    }
    return out[0..oid.len];
}

fn decodeArtifactName(name: []const u8, out: *[32]u8) ![]const u8 {
    const digest_len: usize = switch (name.len) {
        40 => 20,
        64 => 32,
        else => return error.InvalidArtifactName,
    };
    for (out[0..digest_len], 0..) |*byte, index| {
        const high = name[index * 2];
        const low = name[index * 2 + 1];
        if (!isLowerHex(high) or !isLowerHex(low)) return error.InvalidArtifactName;
        byte.* = (std.fmt.charToDigit(high, 16) catch return error.InvalidArtifactName) << 4 |
            (std.fmt.charToDigit(low, 16) catch return error.InvalidArtifactName);
    }
    return out[0..digest_len];
}

fn isLowerHex(byte: u8) bool {
    return (byte >= '0' and byte <= '9') or (byte >= 'a' and byte <= 'f');
}

fn put2(out: []u8, value: u32) void {
    std.debug.assert(out.len >= 2 and value < 100);
    out[0] = '0' + @as(u8, @intCast((value / 10) % 10));
    out[1] = '0' + @as(u8, @intCast(value % 10));
}