Artifact [f48b214dbf]

Artifact f48b214dbfad2d89a26789be60d6d8873beaf640afb3a307d2539e6dbbb23b13:

• File src/git_import_impl.zig — part of check-in [4d7a22b93c] at 2026-08-02 19:52:18 on branch sub-manifest — import-git: decide branch membership from the commit graph

  fast-export emits each commit once, under whichever ref reached it first, so that header was provenance and not branch. A single-branch repository imported with ZERO branches; multi-head repositories were scrambled in proportion to merge activity, which at sqlite scale read as 7,421 leaves on master under repo-state §7.2's same-branch leaf test. Issue #26.

  labelBranches claims the primary's first-parent chain, then each head shallowest tip first, then inherits; emitBranchControls writes one control per segment root. Two things the plan did not anticipate: objects are folded to check-ins by hash first, because two git commits can translate to one byte-identical check-in and §5.2 allows one branch tag per rid; and controls are emitted deepest-first, because §5.3's timestamp skip would otherwise let an ancestor's propagation win over a root whose commit shares its second.

  source_ref is deleted rather than demoted -- after the change it had no readers. makeBranchControl now composes the §6.2 pair through artifact.composeCommitTags instead of a lone *branch card.

  Content was never affected: artifacts, parent links and tip content were always correct. Only derived branch state was wrong, which is why a full benchmark ran clean through it. Repairing an existing imported store means re-importing; check-in hashes survive, since branch state lives in separate controls.

  Two pre-existing expectations were rewritten, deliberately: both demanded two active branch tags on one rid, which §5.2 forbids, and were unsatisfiable rather than merely stale.

  Verified: fmt, test 3281/3281, gate, e2e 716/716, git-import-e2e 11/11, dst 6x1000. Shapes A/B/C match git branch exactly, 11/11 tip parity. (user: dmestas, size: 93820) [annotate] [blame] [check-ins using]

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;

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

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,
    author: OwnedIdentity,
    committer: OwnedIdentity,

    fn deinit(self: *ImportedObject, gpa: std.mem.Allocator) void {
        if (self.oid) |oid| gpa.free(oid);
        gpa.free(self.hash);
        self.author.deinit(gpa);
        self.committer.deinit(gpa);
        self.* = undefined;
    }
};
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;
    }
};

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,

    pub fn deinit(self: *FinalizedRefs, gpa: std.mem.Allocator) void {
        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,

        /// 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();
            return .{
                .gpa = gpa,
                .log = log,
                .format = format,
                .attribution = resolved.attribution,
                .tree_store = tree_store,
                .tree_editor = tree_editor,
                .work = .{},
                .observer = observer,
            };
        }

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

        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;
        }

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

            _ = 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.? });
            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));

            // 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.
            var tree_commands: std.ArrayList(editor.TreeCommand) = .empty;
            defer tree_commands.deinit(self.gpa);
            try tree_commands.ensureTotalCapacity(self.gpa, commit.commands.len);
            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)) |translated| {
                    tree_commands.appendAssumeCapacity(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 = &.{} };
            }

            var staged = StagingStore.init(self.gpa, self.tree_store);
            defer staged.deinit();
            var result: editor.BuildResult = undefined;
            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;
            try Policy.apply(
                &self.tree_editor,
                self.gpa,
                staged.treeStore(),
                root_view,
                tree_commands.items,
                &result,
                &cache_high_water,
            );
            if (measure_tree_apply) {
                self.work.tree_apply_count += 1;
                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;
            defer result.deinit();

            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;
            var commit_record = try self.prepareCommitRecord(commit, hash, first_parent_index, tree_height);
            errdefer commit_record.deinit(self.gpa);
            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);
            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,
        ) !?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),
                    };
                    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)) 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)) {
                        break :blk try self.omitSubmodule(parent, rename.new);
                    }
                    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)) {
                        break :blk try self.omitSubmodule(parent, copy.new);
                    }
                    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) !?editor.TreeCommand {
            try self.recordGitlinkPath(path);
            self.work.skipped_submodule_entries += 1;
            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) !bool {
            if (!self.gitlink_paths.contains(path)) return false;
            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 };
        }
        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,
            };
        }

        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_jsonl = try self.buildProvenance(refs.items);
            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,
            };
        }

        /// 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` defaults far below
            // 2^32 but is a caller-supplied default, not a ceiling, so the
            // narrowing is checked here rather than assumed from a value set two
            // modules away.
            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;
        }

        fn buildProvenance(self: *const Self, refs: []const FinalizedRef) ![]u8 {
            var out: std.ArrayList(u8) = .empty;
            errdefer out.deinit(self.gpa);
            for (self.objects.items) |object| {
                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, ",\"warning\":null}\n");
            }
            for (self.blobs.items) |blob| {
                const oid = blob.oid orelse continue;
                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, ",\"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");
            }
            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.? });
        }
    };
}

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