Artifact [4e961b3c4e]

Artifact 4e961b3c4ea46cd4139ef04c0073738d24554c31fff7f8fd5c9b34c0e105d281:

• File src/submanifest_editor.zig — part of check-in [9b96469ae6] at 2026-08-02 01:29:11 on branch sub-manifest — import-git: add --no-submanifests

  Imports with sub-manifests off: flat manifests throughout and the spec-default config frame (k=0, enable off). Flat is §8.1's default shape; it is this verb's analyze-and-pin that is the deviation.

  TreeFormat.Shape becomes flat | tree{k, height_max}, so flat-with-a-k and tree-without-one stop being representable and every tree-only site traps on the wrong tag. buildFlat drains the same MergedCursor, so ordering, dedup and rename/copy/delete stay single-sourced. SubmanifestChoice replaces submanifest_k from Request down to UserOptions.

  Publication refuses if the store holds a SUBMANIFEST anyway, derived from work done rather than from the flag. Preflight analysis still runs under flat -- skipping it would put a second divergence inside the region the benchmark times.

  Closes #23. (user: dmestas, size: 109208) [annotate] [blame] [check-ins using]

const std = @import("std");
const artifact = @import("artifact.zig");
const partition = @import("submanifest_partition.zig");

/// `StringHashMapUnmanaged` uses this load factor for its default context.
const cache_index_max_load_percentage = 80;

/// How this editor names artifacts, and whether it partitions at all.
///
/// `hash_algo` sits outside `shape` because both shapes name artifacts; `k` and
/// `height_max` sit inside `.tree` because every one of their uses is on a
/// tree-only path. That placement is the point: a flat format has no field that
/// could carry a contradictory k, and every tree-only site unwraps
/// `shape.tree`, which traps rather than silently reading a stale number if the
/// flat induction (see `TreeEditor.apply`) is ever broken.
pub const TreeFormat = struct {
    hash_algo: artifact.HashAlgo,
    shape: Shape,

    /// draft-fossil-submanifests-00 §8.1 makes flat the default posture: a
    /// writer emits no S card unless the repository opted in. `.flat` is that
    /// posture expressed at the editor seam — never partition, never stage a
    /// SUBMANIFEST candidate — not a tuning of `.tree` that happens to yield
    /// one group, which no k can guarantee (`CanonicalPartitioner.push` forces
    /// a boundary unconditionally at `open == max`).
    pub const Shape = union(enum) {
        flat,
        tree: Tree,

        pub const Tree = struct {
            k: u4,
            height_max: u8,
        };
    };
};

pub const StoreError = error{
    MissingNode,
    StorageFailure,
    OutOfMemory,
};

pub const LoadedBytes = struct {
    bytes: []u8,
    allocator: std.mem.Allocator,

    pub fn deinit(self: *LoadedBytes) void {
        self.allocator.free(self.bytes);
        self.* = undefined;
    }
};

/// A complete immutable artifact group. Callers submit one group when every
/// member must become visible together.
pub const StoreBatchNode = struct {
    name: []const u8,
    bytes: []const u8,
};

pub const PutBatchFn = *const fn (*anyopaque, []const StoreBatchNode) StoreError!void;

pub const PutFn = *const fn (*anyopaque, []const u8, []const u8) StoreError!void;

pub const LoadFn = *const fn (*anyopaque, std.mem.Allocator, []const u8) StoreError!LoadedBytes;

/// The editor's only persistence boundary. A caller cannot inject parser or
/// Git state through this interface: names and exact immutable bytes are all it
/// accepts.
pub const TreeStore = struct {
    ctx: *anyopaque,
    load_fn: LoadFn,
    put_fn: PutFn,
    put_batch_fn: PutBatchFn,
};

pub const RootView = union(enum) {
    flat: []const artifact.FCard,
    tree: []const artifact.SCard,
};

pub const RootRun = union(enum) {
    flat: []const artifact.FCard,
    tree: []const artifact.SCard,
};

pub const TreeCommand = union(enum) {
    upsert: artifact.FCard,
    delete: []const u8,
    rename: struct { old: []const u8, new: []const u8 },
    copy: struct { old: []const u8, new: []const u8 },
    delete_all,
};

pub const Error = StoreError || std.mem.Allocator.Error || artifact.WriteError || error{
    InvalidFormat,
    MalformedNode,
    WrongNodeType,
    Cycle,
    HeightExceeded,
    MissingPath,
    DuplicatePath,
    InvalidCommand,
};

pub const BuildResult = struct {
    root: RootRun,
    /// Zero for a flat root, the S-card level count for a rebuilt tree, and
    /// null only when an unchanged tree root was cloned without traversal.
    tree_height: ?u8,
    changed_paths: usize,
    reused_nodes: usize,
    emitted_nodes: usize,
    arena_state: std.heap.ArenaAllocator,

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

const LoadedNode = struct {
    bytes: LoadedBytes,
    manifest: artifact.Manifest,

    fn deinit(self: *LoadedNode) void {
        self.manifest.deinit();
        self.bytes.deinit();
        self.* = undefined;
    }
};

const CacheEntry = struct {
    link: std.DoublyLinkedList.Node = .{},
    name: []u8,
    node: LoadedNode,
    leases: usize = 0,
};

/// A decoded node held either by the cache or by its caller. Cached nodes stay
/// pinned while a traversal borrows them, so FIFO eviction cannot invalidate a
/// parent frame during recursive descent.
const NodeLease = union(enum) {
    cached: *CacheEntry,
    owned: LoadedNode,

    fn manifest(self: *const NodeLease) *const artifact.Manifest {
        return switch (self.*) {
            .cached => |entry| &entry.node.manifest,
            .owned => |*node| &node.manifest,
        };
    }

    fn deinit(self: *NodeLease) void {
        switch (self.*) {
            .cached => |entry| {
                std.debug.assert(entry.leases != 0);
                entry.leases -= 1;
            },
            .owned => |*node| node.deinit(),
        }
        self.* = undefined;
    }
};

/// A repository-bound reader and canonical writer. It never accepts a
/// per-commit format change and retains no parent-tree state between `apply`
/// calls; callers pass one call-scoped root view each time.
pub const TreeEditor = struct {
    gpa: std.mem.Allocator,
    store: TreeStore,
    format: TreeFormat,
    cache_bytes_max: usize,
    cache_bytes: usize = 0,
    cache_high_water: usize = 0,
    cache: std.DoublyLinkedList = .{},
    cache_index: std.StringHashMapUnmanaged(*CacheEntry) = .empty,
    lookup_arena: std.heap.ArenaAllocator,
    /// The root whose complete reachable range `lookupTree` has already walked.
    ///
    /// Validation is a pure function of the tree, and nodes are content-addressed
    /// -- `decodeNode` binds a name to hash(bytes) -- so an identical root card
    /// list names an identical tree and cannot reach a different verdict on a
    /// second walk. Keying on the root rather than on individual nodes is what
    /// makes that argument short: a per-node memo would have to reproduce every
    /// implicit input of `validateTreeNode` (`expected_first`, `upper`, `depth`),
    /// and would silently admit malformations the moment a fourth was added.
    ///
    /// This is a validation memo, not a cache: it holds no decoded bytes and is
    /// deliberately outside `cache_bytes_max`, so eviction pressure cannot defeat
    /// it and it cannot distort `cacheHighWater`.
    validated_root: ?[]const artifact.SCard = null,
    validated_root_arena: std.heap.ArenaAllocator,
    /// Direct S-card descriptors inspected by the current `apply` route.
    /// This is a testable work counter; cached-node and serialization work are
    /// intentionally excluded.
    touched_search_steps: usize = 0,

    pub fn init(
        gpa: std.mem.Allocator,
        store: TreeStore,
        format: TreeFormat,
        cache_bytes_max: usize,
    ) Error!TreeEditor {
        switch (format.shape) {
            // A flat format has no range to check: it carries no k and no
            // height, which is exactly why it cannot be misconfigured.
            .flat => {},
            .tree => |tree| if (tree.k < artifact.min_k or tree.k > artifact.max_k or
                tree.height_max == 0 or tree.height_max > @as(u8, @intCast(artifact.max_construct_height)))
            {
                return error.InvalidFormat;
            },
        }
        return .{
            .gpa = gpa,
            .store = store,
            .format = format,
            .cache_bytes_max = cache_bytes_max,
            .lookup_arena = std.heap.ArenaAllocator.init(gpa),
            .validated_root_arena = std.heap.ArenaAllocator.init(gpa),
        };
    }

    /// Rebinding moves to a new commit-local staging store. Decoded data from
    /// an older apply has no semantic value here and retaining it makes cache
    /// eviction depend on import history rather than the touched tree.
    pub fn rebindStore(self: *TreeEditor, store: TreeStore) void {
        while (self.cache.popFirst()) |link| {
            self.destroyCacheEntry(@fieldParentPtr("link", link));
        }
        self.cache_index.deinit(self.gpa);
        self.cache_index = .empty;
        self.cache_bytes = 0;
        self.store = store;
        self.invalidateValidatedRoot();
    }

    /// A new store can bind the same names to different bytes, so a verdict
    /// reached against the old one carries no weight here.
    fn invalidateValidatedRoot(self: *TreeEditor) void {
        self.validated_root = null;
        _ = self.validated_root_arena.reset(.free_all);
    }

    pub fn deinit(self: *TreeEditor) void {
        self.lookup_arena.deinit();
        self.rebindStore(self.store);
        self.validated_root_arena.deinit();
        self.* = undefined;
    }

    pub fn cacheHighWater(self: *const TreeEditor) usize {
        return self.cache_high_water;
    }

    /// Number of direct S-card descriptors inspected while locating touched
    /// paths in the most recent `apply`.
    pub fn touchedSearchSteps(self: *const TreeEditor) usize {
        return self.touched_search_steps;
    }

    /// Read an exact file card without exposing any loaded-byte or cache view.
    /// The returned card is owned by the editor until its next `lookup`,
    /// `apply`, or `deinit`.
    pub fn lookup(self: *TreeEditor, root: RootView, path: []const u8) Error!?artifact.FCard {
        // Same argument as `apply`'s, and refused the same way: `lookup` is the
        // other public entry that takes a caller-supplied `RootView`, and
        // unguarded a `.tree` root here walks into `lookupTree`'s
        // `shape.tree.height_max` and panics on the union tag instead of
        // reporting a bad argument.
        if (rootMismatchesFormat(self.format.shape, root)) return error.InvalidFormat;
        self.resetLookupArena();
        const arena = self.lookup_arena.allocator();
        return switch (root) {
            .flat => |entries| if (lookupFlat(entries, path)) |card| try cloneFCard(arena, card) else null,
            .tree => |cards| self.lookupTree(cards, path, 0, &[_][]const u8{}),
        };
    }

    pub fn apply(
        self: *TreeEditor,
        parent: RootView,
        commands: []const TreeCommand,
    ) Error!BuildResult {
        self.touched_search_steps = 0;
        // The flat induction, checked once per commit at the only place a root
        // can enter this editor.
        //
        // Base case: an import's first commit applies over `.{ .flat = &.{} }`,
        // and so does every commit after a `deleteall`. Step: the only other
        // parent is a root this editor returned, and under `.flat` both returns
        // below are flat -- the empty-command clone preserves the parent's
        // shape, and `buildFlat` is unconditionally flat. So a `.tree` parent
        // here did not come from this editor, and the tree-only machinery it
        // would wake (`OldTreeCursor.descend`, the partitioners, the checkpoint
        // splice) has no k and no height to run with.
        //
        // A returned error rather than an `assert` because `apply` is public
        // API taking a caller-supplied `RootView`: a `.tree` parent here is a
        // bad ARGUMENT, not a broken internal invariant, and callers outside
        // this file's induction can reach it. `Error` already carries
        // `InvalidFormat` for exactly that.
        if (rootMismatchesFormat(self.format.shape, parent)) return error.InvalidFormat;
        self.resetLookupArena();
        var arena_state = std.heap.ArenaAllocator.init(self.gpa);
        errdefer arena_state.deinit();
        const arena = arena_state.allocator();
        if (commands.len == 0) {
            const root: RootRun = switch (parent) {
                .flat => |entries| .{ .flat = try cloneFCards(arena, entries) },
                .tree => |cards| .{ .tree = try cloneSCards(arena, cards) },
            };
            return .{
                .root = root,
                .tree_height = switch (parent) {
                    .flat => 0,
                    .tree => null,
                },
                .changed_paths = 0,
                .reused_nodes = switch (parent) {
                    .flat => 0,
                    .tree => |cards| cards.len,
                },
                .emitted_nodes = 0,
                .arena_state = arena_state,
            };
        }

        var overlay: Overlay = .{};
        const changed = try overlay.apply(self, parent, arena, commands);
        var known_nodes: KnownNodes = .{};
        const start_path = if (overlay.clear) null else overlay.entries.items[0].path;
        var cursor = try OldTreeCursor.init(self, parent, arena, &known_nodes, start_path);
        defer cursor.deinit();
        var merged = MergedCursor.init(&cursor, &overlay, arena, self.format.shape);
        defer merged.deinit();
        var builder = StreamBuilder.init(self, arena, &known_nodes);
        const root = try builder.build(&merged);
        return .{
            .root = root.root,
            .tree_height = root.tree_height,
            .changed_paths = changed,
            .reused_nodes = root.reused_nodes,
            .emitted_nodes = root.emitted_nodes,
            .arena_state = arena_state,
        };
    }

    fn lookupTree(
        self: *TreeEditor,
        cards: []const artifact.SCard,
        path: []const u8,
        depth: u8,
        ancestry: []const []const u8,
    ) Error!?artifact.FCard {
        if (!self.rootAlreadyValidated(cards, depth)) {
            try self.validateTreeCards(cards, depth, ancestry);
            self.rememberValidatedRoot(cards, depth);
        }
        return self.lookupValidatedTree(cards, path, depth, self.lookup_arena.allocator());
    }

    fn resetLookupArena(self: *TreeEditor) void {
        self.lookup_arena.deinit();
        self.lookup_arena = std.heap.ArenaAllocator.init(self.gpa);
    }

    fn cachedNode(self: *TreeEditor, name: []const u8) ?*CacheEntry {
        return self.cache_index.get(name);
    }

    /// Retained allocation excluding the hash table. The map is charged once
    /// by capacity, rather than once per resident node.
    fn cachedBytes(name: []const u8, node: *const LoadedNode) usize {
        return @sizeOf(CacheEntry) +
            name.len +
            node.bytes.bytes.len +
            node.manifest.arena_state.queryCapacity();
    }

    /// Exact `HashMapUnmanaged` backing allocation for this map's capacity:
    /// `align(max(header, key, value),
    ///   align(value, align(key, sizeof(Header) + capacity) + capacity * sizeof(Key))
    ///     + capacity * sizeof(Value))`.
    fn cacheIndexBytes(capacity: usize) usize {
        if (capacity == 0) return 0;
        const Header = struct {
            values: [*]*CacheEntry,
            keys: [*][]const u8,
            capacity: u32,
        };
        const header_align = @alignOf(Header);
        const key_align = @alignOf([]const u8);
        const value_align = @alignOf(*CacheEntry);
        const max_align = @max(header_align, key_align, value_align);
        const metadata_end = @sizeOf(Header) + capacity;
        const keys_start = std.mem.alignForward(usize, metadata_end, key_align);
        const keys_end = keys_start + capacity * @sizeOf([]const u8);
        const values_start = std.mem.alignForward(usize, keys_end, value_align);
        const values_end = values_start + capacity * @sizeOf(*CacheEntry);
        return std.mem.alignForward(usize, values_end, max_align);
    }

    /// Predict the one capacity that the next distinct `put` can retain.
    /// The public count and load factor recover the map's availability
    /// countdown without mirroring private mutable state.
    fn nextCacheIndexCapacity(self: *const TreeEditor) usize {
        const capacity: usize = @intCast(self.cache_index.capacity());
        const count: usize = @intCast(self.cache_index.count());
        if (count < capacity * cache_index_max_load_percentage / 100) return capacity;

        const required = (count + 1) * 100 / cache_index_max_load_percentage + 1;
        return @max(
            @as(usize, 8),
            std.math.ceilPowerOfTwo(usize, required) catch unreachable,
        );
    }

    fn destroyCacheEntry(self: *TreeEditor, entry: *CacheEntry) void {
        std.debug.assert(entry.leases == 0);
        self.gpa.free(entry.name);
        entry.node.deinit();
        self.gpa.destroy(entry);
    }

    /// Evict the oldest unleased decoded nodes. Leased nodes remain stable for
    /// recursive traversal; if they alone prevent enough room, the caller
    /// receives an uncached node instead.
    fn evictFor(self: *TreeEditor, incoming: usize) bool {
        while (self.cache_bytes > self.cache_bytes_max - incoming) {
            var link = self.cache.first;
            while (link) |current| : (link = current.next) {
                const entry: *CacheEntry = @fieldParentPtr("link", current);
                if (entry.leases == 0) {
                    self.cache.remove(current);
                    _ = self.cache_index.remove(entry.name);
                    self.cache_bytes -= cachedBytes(entry.name, &entry.node);
                    self.destroyCacheEntry(entry);
                    break;
                }
            }
            if (link == null) return false;
        }
        return true;
    }

    fn decodeNode(self: *TreeEditor, name: []const u8) Error!LoadedNode {
        var bytes = try self.store.load_fn(self.store.ctx, self.gpa, name);
        errdefer bytes.deinit();
        var actual_name_buf: [64]u8 = undefined;
        if (!std.mem.eql(u8, name, artifact.artifactName(self.format.hash_algo, bytes.bytes, &actual_name_buf))) {
            return error.MalformedNode;
        }
        var manifest = artifact.parse(self.gpa, bytes.bytes) catch |err| switch (err) {
            error.OutOfMemory => return error.OutOfMemory,
            else => return error.MalformedNode,
        };
        errdefer manifest.deinit();
        if (manifest.kind != .submanifest) return error.WrongNodeType;
        if ((manifest.f.len == 0) == (manifest.s.len == 0)) return error.WrongNodeType;
        if (manifest.f.len != 0) {
            var previous: ?[]const u8 = null;
            for (manifest.f) |entry| {
                if (entry.hash == null) return error.MalformedNode;
                if (previous) |key| if (artifact.compareBytes(key, entry.filename) != .lt) return error.MalformedNode;
                previous = entry.filename;
            }
        } else {
            var previous: ?[]const u8 = null;
            for (manifest.s) |card| {
                if (previous) |key| if (artifact.compareBytes(key, card.filename) != .lt) return error.MalformedNode;
                previous = card.filename;
            }
        }
        return .{ .bytes = bytes, .manifest = manifest };
    }

    fn loadNode(self: *TreeEditor, name: []const u8) Error!NodeLease {
        const algo = artifact.nameAlgo(name.len) orelse return error.MalformedNode;
        if (algo != self.format.hash_algo) return error.MalformedNode;
        if (self.cachedNode(name)) |entry| {
            entry.leases += 1;
            return .{ .cached = entry };
        }

        var node = try self.decodeNode(name);
        const bytes = cachedBytes(name, &node);
        const index_capacity_before: usize = @intCast(self.cache_index.capacity());
        const index_bytes_before = cacheIndexBytes(index_capacity_before);
        const index_bytes_after = cacheIndexBytes(self.nextCacheIndexCapacity());
        const incoming = bytes + index_bytes_after - index_bytes_before;
        if (self.cache_bytes_max == 0 or incoming > self.cache_bytes_max or !self.evictFor(incoming)) {
            return .{ .owned = node };
        }

        const entry = self.gpa.create(CacheEntry) catch |err| {
            node.deinit();
            return err;
        };
        const cached_name = self.gpa.dupe(u8, name) catch |err| {
            self.gpa.destroy(entry);
            node.deinit();
            return err;
        };
        entry.* = .{ .name = cached_name, .node = node };
        self.cache_index.put(self.gpa, entry.name, entry) catch |err| {
            self.destroyCacheEntry(entry);
            return err;
        };
        const index_capacity_after: usize = @intCast(self.cache_index.capacity());
        self.cache.append(&entry.link);
        entry.leases = 1;
        self.cache_bytes += bytes + cacheIndexBytes(index_capacity_after) - index_bytes_before;
        self.cache_high_water = @max(self.cache_high_water, self.cache_bytes);
        return .{ .cached = entry };
    }
    /// Apply-time probing only follows the branch selected by `path`.  Public
    /// `lookup` retains complete-tree validation; an edit must not preflight
    /// unrelated file cards before it can begin rebuilding.
    fn lookupTouchedOwned(self: *TreeEditor, root: RootView, path: []const u8, arena: std.mem.Allocator) Error!?artifact.FCard {
        return switch (root) {
            .flat => |entries| if (lookupFlat(entries, path)) |card| try cloneFCard(arena, card) else null,
            .tree => |cards| self.lookupTouchedTree(cards, path, 0, &[_][]const u8{}, arena),
        };
    }

    fn lookupTouchedTree(
        self: *TreeEditor,
        cards: []const artifact.SCard,
        path: []const u8,
        depth: u8,
        ancestry: []const []const u8,
        arena: std.mem.Allocator,
    ) Error!?artifact.FCard {
        if (cards.len == 0 or artifact.compareBytes(cards[0].filename, path) == .gt) return null;
        // This is the old scan's last descriptor with first key <= `path`.
        // Route selection must stay logarithmic even when the direct root is
        // wider than a canonical local group.
        var low: usize = 0;
        var high = cards.len;
        while (low < high) {
            const mid = low + (high - low) / 2;
            self.touched_search_steps += 1;
            if (artifact.compareBytes(cards[mid].filename, path) != .gt) low = mid + 1 else high = mid;
        }
        const index = low - 1;
        const child = cards[index];
        if (index != 0) {
            const predecessor = cards[index - 1];
            if (artifact.compareBytes(predecessor.filename, child.filename) != .lt) return error.MalformedNode;
            try self.validateRightmostRange(
                predecessor.hash,
                predecessor.filename,
                child.filename,
                depth,
                ancestry,
            );
        }
        for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, child.hash)) return error.Cycle;

        var node = try self.loadNode(child.hash);
        defer node.deinit();
        const manifest = node.manifest();
        const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
        if (!std.mem.eql(u8, child.filename, actual_first)) return error.MalformedNode;
        if (manifest.f.len != 0) {
            if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
            return null;
        }

        var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
        if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
        @memcpy(next_ancestry[0..ancestry.len], ancestry);
        next_ancestry[ancestry.len] = child.hash;
        return self.lookupTouchedTree(
            manifest.s,
            path,
            depth + 1,
            next_ancestry[0 .. ancestry.len + 1],
            arena,
        );
    }
    /// Validate only the predecessor range that can reach `upper`. Decoded
    /// nodes still validate each local descriptor list, while following only
    /// the rightmost descendant prevents an apply from walking unrelated
    /// predecessor leaves.
    fn validateRightmostRange(
        self: *TreeEditor,
        name: []const u8,
        expected_first: []const u8,
        upper: []const u8,
        depth: u8,
        ancestry: []const []const u8,
    ) Error!void {
        if (depth >= self.format.shape.tree.height_max) return error.HeightExceeded;
        for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;

        var node = try self.loadNode(name);
        defer node.deinit();
        const manifest = node.manifest();
        if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;

        const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
        if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;

        if (manifest.f.len != 0) {
            if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, upper) != .lt) return error.MalformedNode;
            return;
        }

        var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
        if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
        @memcpy(next_ancestry[0..ancestry.len], ancestry);
        next_ancestry[ancestry.len] = name;
        const rightmost = manifest.s[manifest.s.len - 1];
        return self.validateRightmostRange(
            rightmost.hash,
            rightmost.filename,
            upper,
            depth + 1,
            next_ancestry[0 .. ancestry.len + 1],
        );
    }

    /// True when `cards` is byte-identical to the root already walked against
    /// the current store. Identical S cards name identical children, and a child
    /// name binds its bytes, so the two roots are the same tree all the way down.
    ///
    /// Only a whole-tree walk from the top is memoized: `depth` must be 0, which
    /// is also the only way `lookupTree` is reached. A non-zero depth would carry
    /// an ancestry and a shortened height budget that this comparison does not
    /// model, so it re-validates rather than guessing.
    fn rootAlreadyValidated(self: *const TreeEditor, cards: []const artifact.SCard, depth: u8) bool {
        if (depth != 0) return false;
        const previous = self.validated_root orelse return false;
        if (previous.len != cards.len) return false;
        for (previous, cards) |was, now| {
            if (!std.mem.eql(u8, was.filename, now.filename)) return false;
            if (!std.mem.eql(u8, was.hash, now.hash)) return false;
        }
        return true;
    }

    /// Record a root that just validated. A failed copy is not an error: the
    /// memo is an optimization, and losing it costs the next lookup a re-walk
    /// rather than a wrong answer.
    fn rememberValidatedRoot(self: *TreeEditor, cards: []const artifact.SCard, depth: u8) void {
        if (depth != 0) return;
        self.invalidateValidatedRoot();
        self.validated_root = cloneSCards(self.validated_root_arena.allocator(), cards) catch {
            self.validated_root = null;
            return;
        };
    }

    /// Validate the complete reachable range before returning any lookup
    /// result. A selected child is not enough: a malformed sibling can expand
    /// into the selected child's range and make the S run ambiguous.
    fn validateTreeCards(
        self: *TreeEditor,
        cards: []const artifact.SCard,
        depth: u8,
        ancestry: []const []const u8,
    ) Error!void {
        if (depth >= self.format.shape.tree.height_max or cards.len == 0) return error.MalformedNode;
        var previous: ?[]const u8 = null;
        for (cards, 0..) |child, index| {
            if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
            previous = child.filename;
            const upper = if (index + 1 < cards.len) cards[index + 1].filename else null;
            try self.validateTreeNode(child.hash, child.filename, upper, depth, ancestry);
        }
    }

    /// `upper` is the next sibling's advertised first key. Every descendant
    /// must be strictly below it, which makes sibling ranges disjoint.
    fn validateTreeNode(
        self: *TreeEditor,
        name: []const u8,
        expected_first: []const u8,
        upper: ?[]const u8,
        depth: u8,
        ancestry: []const []const u8,
    ) Error!void {
        if (depth >= self.format.shape.tree.height_max) return error.HeightExceeded;
        for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;
        var node = try self.loadNode(name);
        defer node.deinit();
        const manifest = node.manifest();
        if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;
        const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
        if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;
        if (manifest.f.len != 0) {
            if (upper) |next| {
                if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, next) != .lt) return error.MalformedNode;
            }
            return;
        }
        if (manifest.s.len == 0) return error.WrongNodeType;
        var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
        if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
        @memcpy(next_ancestry[0..ancestry.len], ancestry);
        next_ancestry[ancestry.len] = name;
        var previous: ?[]const u8 = null;
        for (manifest.s, 0..) |child, index| {
            if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
            previous = child.filename;
            const child_upper = if (index + 1 < manifest.s.len) manifest.s[index + 1].filename else upper;
            try self.validateTreeNode(
                child.hash,
                child.filename,
                child_upper,
                depth + 1,
                next_ancestry[0 .. ancestry.len + 1],
            );
        }
    }

    fn lookupValidatedTree(
        self: *TreeEditor,
        cards: []const artifact.SCard,
        path: []const u8,
        depth: u8,
        arena: std.mem.Allocator,
    ) Error!?artifact.FCard {
        const child = childForPath(cards, path) orelse return null;
        var node = try self.loadNode(child.hash);
        defer node.deinit();
        const manifest = node.manifest();
        if (manifest.f.len != 0) {
            if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
            return null;
        }
        if (depth + 1 >= self.format.shape.tree.height_max) return error.HeightExceeded;
        return self.lookupValidatedTree(manifest.s, path, depth + 1, arena);
    }
};

const StreamEntry = struct {
    card: artifact.FCard,
    /// The exact old leaf containing `card`, if it survived the overlay.
    origin: ?[]const u8,
};

const Descriptor = struct {
    card: artifact.SCard,
    /// The old node name is deliberately propagated upward.  A canonical
    /// repaired parent can therefore be reused without retaining its children.
    origin: ?[]const u8,
};

const OverlayEntry = struct {
    path: []const u8,
    original: ?artifact.FCard,
    value: ?artifact.FCard,
};

const Overlay = struct {
    entries: std.ArrayList(OverlayEntry) = .empty,
    clear: bool = false,

    fn lowerBound(self: *const Overlay, path: []const u8) usize {
        var low: usize = 0;
        var high = self.entries.items.len;
        while (low < high) {
            const mid = low + (high - low) / 2;
            if (artifact.compareBytes(self.entries.items[mid].path, path) == .lt) low = mid + 1 else high = mid;
        }
        return low;
    }

    fn clone(self: *const Overlay, arena: std.mem.Allocator) Error!Overlay {
        var result: Overlay = .{ .clear = self.clear };
        for (self.entries.items) |entry| {
            try result.entries.append(arena, .{
                .path = try arena.dupe(u8, entry.path),
                .original = if (entry.original) |card| try cloneFCard(arena, card) else null,
                .value = if (entry.value) |card| try cloneFCard(arena, card) else null,
            });
        }
        return result;
    }

    fn get(self: *const Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, path: []const u8) Error!?artifact.FCard {
        const index = self.lowerBound(path);
        if (index < self.entries.items.len and std.mem.eql(u8, self.entries.items[index].path, path)) {
            return self.entries.items[index].value;
        }
        if (self.clear) return null;
        return editor_.lookupTouchedOwned(parent, path, arena);
    }

    fn put(self: *Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, path: []const u8, value: ?artifact.FCard) Error!void {
        const index = self.lowerBound(path);
        const owned_value = if (value) |card| try cloneFCard(arena, card) else null;
        if (index < self.entries.items.len and std.mem.eql(u8, self.entries.items[index].path, path)) {
            self.entries.items[index].value = owned_value;
            return;
        }

        const original = if (self.clear) null else try editor_.lookupTouchedOwned(parent, path, arena);
        const owned_path = try arena.dupe(u8, path);
        try self.entries.insert(arena, index, .{
            .path = owned_path,
            .original = original,
            .value = owned_value,
        });
    }

    fn netChangedPaths(self: *const Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator) Error!usize {
        var known_nodes: KnownNodes = .{};
        var old = try OldTreeCursor.init(editor_, parent, arena, &known_nodes, null);
        defer old.deinit();

        var changed: usize = 0;
        var overlay_index: usize = 0;
        while (try old.next()) |old_entry| {
            while (overlay_index < self.entries.items.len and
                artifact.compareBytes(self.entries.items[overlay_index].path, old_entry.card.filename) == .lt)
            {
                if (self.entries.items[overlay_index].value != null) changed += 1;
                overlay_index += 1;
            }

            if (overlay_index < self.entries.items.len and
                std.mem.eql(u8, self.entries.items[overlay_index].path, old_entry.card.filename))
            {
                if (self.entries.items[overlay_index].value) |card| {
                    if (!sameFCard(card, old_entry.card)) changed += 1;
                } else {
                    changed += 1;
                }
                overlay_index += 1;
            } else if (self.clear) {
                changed += 1;
            }
        }

        while (overlay_index < self.entries.items.len) : (overlay_index += 1) {
            if (self.entries.items[overlay_index].value != null) changed += 1;
        }
        return changed;
    }

    fn touchedChangedPaths(self: *const Overlay) usize {
        var changed: usize = 0;
        for (self.entries.items) |entry| {
            if (!sameOptionalFCard(entry.original, entry.value)) changed += 1;
        }
        return changed;
    }

    fn apply(self: *Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, commands: []const TreeCommand) Error!usize {
        var staged = try self.clone(arena);
        for (commands) |command| switch (command) {
            .upsert => |card| {
                if (card.hash == null) return error.InvalidCommand;
                try staged.put(editor_, parent, arena, card.filename, card);
            },
            .delete => |path| {
                if ((try staged.get(editor_, parent, arena, path)) == null) return error.MissingPath;
                try staged.put(editor_, parent, arena, path, null);
            },
            .rename => |move| {
                const source = (try staged.get(editor_, parent, arena, move.old)) orelse return error.MissingPath;
                if ((try staged.get(editor_, parent, arena, move.new)) != null) return error.DuplicatePath;

                var renamed = source;
                renamed.filename = move.new;
                try staged.put(editor_, parent, arena, move.new, renamed);
                try staged.put(editor_, parent, arena, move.old, null);
            },
            .copy => |copy| {
                const source = (try staged.get(editor_, parent, arena, copy.old)) orelse return error.MissingPath;
                if ((try staged.get(editor_, parent, arena, copy.new)) != null) return error.DuplicatePath;
                var copied = source;
                copied.filename = copy.new;
                try staged.put(editor_, parent, arena, copy.new, copied);
            },
            .delete_all => {
                staged.clear = true;
                staged.entries.clearRetainingCapacity();
            },
        };

        const changed = if (staged.clear) try staged.netChangedPaths(editor_, parent, arena) else staged.touchedChangedPaths();
        self.* = staged;
        return changed;
    }
};

fn sameFCard(left: artifact.FCard, right: artifact.FCard) bool {
    return left.mode == right.mode and
        std.mem.eql(u8, left.filename, right.filename) and
        sameOptionalBytes(left.hash, right.hash) and
        sameOptionalBytes(left.perm, right.perm) and
        sameOptionalBytes(left.old_name, right.old_name);
}

fn sameOptionalFCard(left: ?artifact.FCard, right: ?artifact.FCard) bool {
    if (left) |left_card| {
        const right_card = right orelse return false;
        return sameFCard(left_card, right_card);
    }
    return right == null;
}

fn sameOptionalBytes(left: ?[]const u8, right: ?[]const u8) bool {
    if (left) |left_bytes| {
        const right_bytes = right orelse return false;
        return std.mem.eql(u8, left_bytes, right_bytes);
    }
    return right == null;
}

const NativePrefixDescriptor = struct {
    descriptor: Descriptor,
    /// Tree height of `descriptor`: leaves are height one and an S card's
    /// height is one greater than its children.
    height: usize,
};

const SuffixFrontier = enum {
    /// A native descriptor already at the current construction height. It is
    /// a partial continuation, not a checkpoint-proof canonical group.
    descriptor,
    /// A complete old parent group was exposed; its raw parent remains at the
    /// front of the native suffix until the caller commits or reuses it.
    group,
    end,
};

/// Per-apply immutable node names. The map owns arena-backed keys and avoids
/// re-scanning every previously visited node for each emitted candidate.
const KnownNodes = struct {
    index: std.StringHashMapUnmanaged(void) = .empty,

    fn contains(self: *const KnownNodes, name: []const u8) bool {
        return self.index.contains(name);
    }

    fn remember(self: *KnownNodes, arena: std.mem.Allocator, name: []const u8) std.mem.Allocator.Error!void {
        if (self.index.contains(name)) return;
        const owned = try arena.dupe(u8, name);
        try self.index.put(arena, owned, {});
    }
};

/// A decoded node on the active left-to-right path. `index` is the next child
/// not yet committed to the cursor's current descriptor level.
const CursorFrame = struct {
    name: []const u8,
    node: NodeLease,
    index: usize = 0,
};

/// Checkpoint traversal has exactly two terminal states. A continuation owns a
/// live fixed-depth frontier whose next canonical group is still at the same
/// descriptor height. A root handoff owns the measured height of the direct
/// root just exhausted; it is not EOF convergence.
const CheckpointState = union(enum) {
    continuation: struct {
        group_depth: usize,
    },
    root: struct {
        height: usize,
    },
};

/// In-order walk over old F cards.  At most one decoded node per tree height is
/// live; every returned card is consumed before advancing can evict its frame.
const OldTreeCursor = struct {
    editor_: *TreeEditor,
    root: RootView,
    arena: std.mem.Allocator,
    known_nodes: *KnownNodes,
    flat_index: usize = 0,
    root_index: usize = 0,
    previous_root: ?[]const u8 = null,
    previous_card: ?[]const u8 = null,
    previous_card_buf: std.ArrayList(u8) = .empty,
    saved_previous_card_buf: std.ArrayList(u8) = .empty,
    frames: std.ArrayList(CursorFrame) = .empty,
    /// Between checkpoint steps this is either a same-height continuation or
    /// the explicit direct-root handoff. There is no inferred EOF state.
    checkpoint: ?CheckpointState = null,
    /// Untouched direct siblings strictly before the localized scan. Each
    /// descriptor remains at its old tree height; no old prefix subtree is
    /// expanded into leaves or F cards.
    prefix: std.ArrayList(NativePrefixDescriptor) = .empty,
    /// Untouched direct siblings after the checkpoint. A stack exposes the
    /// leftmost native descriptor without flattening a higher subtree; each
    /// descriptor remains at its original tree height until its parent group
    /// is the proven splice frontier.
    suffix: std.ArrayList(NativePrefixDescriptor) = .empty,
    fn init(
        editor_: *TreeEditor,
        root: RootView,
        arena: std.mem.Allocator,
        known_nodes: *KnownNodes,
        start_path: ?[]const u8,
    ) Error!OldTreeCursor {
        var cursor: OldTreeCursor = .{
            .editor_ = editor_,
            .root = root,
            .arena = arena,
            .known_nodes = known_nodes,
        };
        errdefer cursor.deinit();
        if (start_path) |path| try cursor.seek(path);
        return cursor;
    }

    fn deinit(self: *OldTreeCursor) void {
        for (self.frames.items) |*frame| frame.node.deinit();
        self.frames.deinit(self.editor_.gpa);
        self.previous_card_buf.deinit(self.editor_.gpa);
        self.saved_previous_card_buf.deinit(self.editor_.gpa);
        self.* = undefined;
    }

    fn remember(self: *OldTreeCursor, name: []const u8) Error!void {
        try self.known_nodes.remember(self.arena, name);
    }

    fn descend(self: *OldTreeCursor, name: []const u8, expected_first: ?[]const u8) Error!void {
        if (self.frames.items.len >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
        for (self.frames.items) |frame| if (std.mem.eql(u8, frame.name, name)) return error.Cycle;
        var node = try self.editor_.loadNode(name);
        errdefer node.deinit();
        const manifest = node.manifest();
        const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
        if (expected_first) |key| if (!std.mem.eql(u8, key, actual_first)) return error.MalformedNode;
        try self.remember(name);
        try self.frames.append(self.editor_.gpa, .{ .name = name, .node = node });
    }
    fn discardLastFrame(self: *OldTreeCursor) void {
        const finished = self.frames.pop().?;
        var owned = finished;
        owned.node.deinit();
    }

    fn directRootHeight(self: *OldTreeCursor, frame: *const CursorFrame) Error!usize {
        var height: usize = 1;
        var manifest = frame.node.manifest();
        var owned: ?NodeLease = null;
        errdefer if (owned) |*node| node.deinit();

        while (manifest.f.len == 0) {
            if (manifest.s.len == 0) return error.WrongNodeType;
            if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
            const loaded = try self.editor_.loadNode(manifest.s[0].hash);
            if (owned) |*node| node.deinit();
            owned = loaded;
            height += 1;
            manifest = owned.?.manifest();
        }
        if (owned) |*node| node.deinit();
        return height;
    }

    fn recordRootCheckpoint(self: *OldTreeCursor) Error!void {
        if (self.frames.items.len != 1) return error.MalformedNode;
        self.checkpoint = .{ .root = .{
            .height = try self.directRootHeight(&self.frames.items[0]),
        } };
    }

    fn finishCheckpointFrame(self: *OldTreeCursor) Error!void {
        if (self.frames.items.len == 0) return error.MalformedNode;
        if (self.frames.items.len == 1) try self.recordRootCheckpoint();
        self.discardLastFrame();
    }

    fn setCheckpointContinuation(self: *OldTreeCursor, group_depth: usize) void {
        self.checkpoint = .{ .continuation = .{
            .group_depth = group_depth,
        } };
    }
    fn checkpointDepth(self: *const OldTreeCursor) Error!usize {
        return switch (self.checkpoint orelse return error.MalformedNode) {
            .continuation => |continuation| continuation.group_depth,
            .root => error.MalformedNode,
        };
    }

    fn takeRootCheckpoint(self: *OldTreeCursor) Error!usize {
        const state = self.checkpoint orelse return error.MalformedNode;
        self.checkpoint = null;
        return switch (state) {
            .root => |root| root.height,
            .continuation => error.MalformedNode,
        };
    }

    fn descendRightmostLeaf(self: *OldTreeCursor) Error!void {
        while (true) {
            const frame = &self.frames.items[self.frames.items.len - 1];
            const manifest = frame.node.manifest();
            if (manifest.f.len != 0) return;
            if (manifest.s.len == 0) return error.WrongNodeType;
            frame.index = manifest.s.len;
            const child = manifest.s[manifest.s.len - 1];
            try self.descend(child.hash, child.filename);
        }
    }

    /// Reopen the immediately preceding leaf when one exists. A late deletion
    /// may shrink the final group that crosses this leaf boundary, so the
    /// predecessor is mutable input rather than a frozen prefix descriptor.
    fn rewindToPredecessorLeaf(self: *OldTreeCursor) Error!void {
        var has_predecessor = self.root_index > 1;
        if (!has_predecessor and self.frames.items.len > 1) {
            for (self.frames.items[0 .. self.frames.items.len - 1]) |frame| {
                if (frame.index > 1) {
                    has_predecessor = true;
                    break;
                }
            }
        }
        if (!has_predecessor) return;

        self.discardLastFrame();
        while (self.frames.items.len != 0) {
            const parent_index = self.frames.items.len - 1;
            const parent = &self.frames.items[parent_index];
            std.debug.assert(parent.index != 0);
            const selected_index = parent.index - 1;
            if (selected_index != 0) {
                parent.index = selected_index;
                const manifest = parent.node.manifest();
                const child = manifest.s[selected_index - 1];
                try self.descend(child.hash, child.filename);
                return self.descendRightmostLeaf();
            }
            self.discardLastFrame();
        }

        std.debug.assert(self.root_index > 1);
        const roots = switch (self.root) {
            .flat => unreachable,
            .tree => |cards| cards,
        };
        const selected_index = self.root_index - 1;
        self.root_index = selected_index;
        const child = roots[selected_index - 1];
        try self.descend(child.hash, child.filename);
        return self.descendRightmostLeaf();
    }

    fn setPreviousCard(self: *OldTreeCursor, filename: []const u8) std.mem.Allocator.Error!void {
        self.previous_card_buf.clearRetainingCapacity();
        try self.previous_card_buf.appendSlice(self.editor_.gpa, filename);
        self.previous_card = self.previous_card_buf.items;
    }

    fn savePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
        self.saved_previous_card_buf.clearRetainingCapacity();
        if (self.previous_card) |previous| try self.saved_previous_card_buf.appendSlice(self.editor_.gpa, previous);
    }

    fn restorePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
        if (self.saved_previous_card_buf.items.len == 0) {
            self.previous_card = null;
            return;
        }
        try self.setPreviousCard(self.saved_previous_card_buf.items);
    }

    fn returned(self: *OldTreeCursor, card: artifact.FCard, origin: ?[]const u8) Error!StreamEntry {
        if (self.previous_card) |previous| if (artifact.compareBytes(previous, card.filename) != .lt) return error.MalformedNode;
        try self.setPreviousCard(card.filename);
        return .{ .card = card, .origin = origin };
    }

    fn atLeafEnd(self: *const OldTreeCursor) bool {
        if (self.frames.items.len == 0) return false;
        const frame = self.frames.items[self.frames.items.len - 1];
        const manifest = frame.node.manifest();
        return manifest.f.len != 0 and frame.index == manifest.f.len;
    }
    fn atRootEnd(self: *const OldTreeCursor) bool {
        if (self.frames.items.len != 0) return false;
        return switch (self.root) {
            .flat => |entries| self.flat_index == entries.len,
            .tree => |cards| self.root_index == cards.len,
        };
    }

    fn appendLeaf(self: *OldTreeCursor, name: []const u8, manifest: *const artifact.Manifest, out: *std.ArrayList(Descriptor)) Error!void {
        std.debug.assert(manifest.f.len != 0);
        const first = manifest.f[0].filename;
        if (self.previous_card) |previous| if (artifact.compareBytes(previous, first) != .lt) return error.MalformedNode;
        try self.setPreviousCard(manifest.f[manifest.f.len - 1].filename);
        const hash = try self.arena.dupe(u8, name);
        try out.append(self.arena, .{
            .card = .{ .filename = try self.arena.dupe(u8, first), .hash = hash },
            .origin = hash,
        });
    }

    fn appendDescriptor(self: *OldTreeCursor, card: artifact.SCard, out: *std.ArrayList(Descriptor)) Error!void {
        const filename = try self.arena.dupe(u8, card.filename);
        const hash = try self.arena.dupe(u8, card.hash);
        try out.append(self.arena, .{
            .card = .{ .filename = filename, .hash = hash },
            .origin = hash,
        });
    }
    fn appendNativePrefix(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!void {
        const filename = try self.arena.dupe(u8, card.filename);
        const hash = try self.arena.dupe(u8, card.hash);
        try self.prefix.append(self.arena, .{
            .descriptor = .{
                .card = .{ .filename = filename, .hash = hash },
                .origin = hash,
            },
            .height = height,
        });
        try self.remember(hash);
    }

    fn nativeDescriptor(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!NativePrefixDescriptor {
        const filename = try self.arena.dupe(u8, card.filename);
        const hash = try self.arena.dupe(u8, card.hash);
        return .{
            .descriptor = .{
                .card = .{ .filename = filename, .hash = hash },
                .origin = hash,
            },
            .height = height,
        };
    }

    fn appendNativeSuffix(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!void {
        try self.suffix.append(self.arena, try self.nativeDescriptor(card, height));
    }

    /// Transfer exactly one remaining direct root card into the suffix stack.
    /// Descended siblings are stacked in reverse order, so a pop always
    /// advances left-to-right without moving the unvisited root slice.
    fn fillSuffixFromRoot(self: *OldTreeCursor, root_height: usize) Error!bool {
        if (self.suffix.items.len != 0) return true;
        const roots = switch (self.root) {
            .flat => return false,
            .tree => |cards| cards,
        };
        if (self.root_index == roots.len) return false;
        const child = roots[self.root_index];
        if (self.previous_root) |previous| {
            if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
        }
        self.previous_root = child.filename;
        self.root_index += 1;
        try self.appendNativeSuffix(child, root_height);
        return true;
    }

    /// Expose the next native suffix frontier at `target_height`. A complete
    /// group remains represented by its raw parent on the stack until the
    /// caller has proved a checkpoint at the following group boundary.
    fn appendRootSuffixFrontierAtHeight(
        self: *OldTreeCursor,
        root_height: usize,
        target_height: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!SuffixFrontier {
        if (target_height == 0 or target_height > root_height) return error.MalformedNode;
        while (true) {
            if (!try self.fillSuffixFromRoot(root_height)) return .end;
            const current = &self.suffix.items[self.suffix.items.len - 1];
            if (current.height < target_height) return error.MalformedNode;
            if (current.height == target_height) {
                const descriptor = self.suffix.pop().?;
                try out.append(self.arena, descriptor.descriptor);
                return .descriptor;
            }
            if (current.height == target_height + 1) {
                var node = try self.editor_.loadNode(current.descriptor.card.hash);
                defer node.deinit();
                try self.remember(current.descriptor.card.hash);
                const manifest = node.manifest();
                const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
                if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
                if (manifest.s.len > max_members) return error.MalformedNode;
                for (manifest.s) |child| {
                    try self.appendDescriptor(child, out);
                    try self.remember(child.hash);
                }
                return .group;
            }

            const parent = self.suffix.pop().?;
            var node = try self.editor_.loadNode(parent.descriptor.card.hash);
            defer node.deinit();
            try self.remember(parent.descriptor.card.hash);
            const manifest = node.manifest();
            const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
            if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
            if (manifest.s.len > max_members) return error.MalformedNode;
            const child_height = parent.height - 1;
            var index = manifest.s.len;
            while (index != 0) {
                index -= 1;
                try self.appendNativeSuffix(manifest.s[index], child_height);
            }
        }
    }

    fn commitRootSuffixFrontier(self: *OldTreeCursor, target_height: usize) Error!void {
        if (self.suffix.items.len == 0) return error.MalformedNode;
        if (self.suffix.items[self.suffix.items.len - 1].height != target_height + 1) return error.MalformedNode;
        _ = self.suffix.pop();
    }

    fn appendRootSuffixAtRootHeight(
        self: *OldTreeCursor,
        root_height: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!void {
        while (true) {
            if (!try self.fillSuffixFromRoot(root_height)) return;
            if (self.suffix.items[self.suffix.items.len - 1].height != root_height) return error.MalformedNode;
            const descriptor = self.suffix.pop().?;
            try out.append(self.arena, descriptor.descriptor);
        }
    }

    /// Splice every retained native descriptor of exactly `height` into `out`.
    /// A descriptor belongs to exactly one output level, so the spliced
    /// entries are consumed here: a later level that re-asks for the same
    /// height would otherwise re-emit a node the current level already owns.
    /// The single fallible step precedes every mutation, so a failed splice
    /// leaves the retained prefix untouched.
    fn appendPrefixAtHeight(self: *OldTreeCursor, height: usize, out: *std.ArrayList(Descriptor)) Error!usize {
        var matches: usize = 0;
        for (self.prefix.items) |entry| {
            if (entry.height == height) matches += 1;
        }
        if (matches == 0) return 0;

        try out.ensureUnusedCapacity(self.arena, matches);
        var kept: usize = 0;
        for (self.prefix.items) |entry| {
            if (entry.height == height) {
                out.appendAssumeCapacity(entry.descriptor);
            } else {
                self.prefix.items[kept] = entry;
                kept += 1;
            }
        }
        self.prefix.items.len = kept;
        return matches;
    }

    fn hasPrefixAtHeight(self: *const OldTreeCursor, height: usize) bool {
        for (self.prefix.items) |entry| if (entry.height == height) return true;
        return false;
    }
    /// A native descriptor at the next level is the predecessor group for the
    /// localized frontier. Reopen it instead of carrying a shallower
    /// descriptor across the height boundary.
    fn takePrefixAtHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
        var index = self.prefix.items.len;
        while (index != 0) {
            index -= 1;
            if (self.prefix.items[index].height == height) return self.prefix.orderedRemove(index);
        }
        return null;
    }

    /// Remove the closest retained ancestor strictly above `height`. The
    /// rightmost such descriptor is the only old subtree adjacent to the
    /// localized frontier.
    fn takePrefixAboveHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
        var candidate_index: ?usize = null;
        var candidate_height: usize = std.math.maxInt(usize);
        for (self.prefix.items, 0..) |entry, index| {
            if (entry.height <= height) continue;
            if (entry.height < candidate_height or entry.height == candidate_height) {
                candidate_index = index;
                candidate_height = entry.height;
            }
        }
        if (candidate_index) |index| return self.prefix.orderedRemove(index);
        return null;
    }

    /// Rewind a retained ancestor to the current construction height without
    /// flattening it. Every descent retains the older direct siblings at their
    /// own formation height, then follows only the rightmost child because it
    /// is adjacent to the edited suffix.
    fn reopenRightmostPrefixAtHeight(
        self: *OldTreeCursor,
        group: NativePrefixDescriptor,
        child_height: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!void {
        std.debug.assert(group.height > child_height + 1);
        var current = group;
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
        while (current.height > child_height + 1) {
            var node = try self.editor_.loadNode(current.descriptor.card.hash);
            defer node.deinit();
            const manifest = node.manifest();
            if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
            if (manifest.s.len > max_members) return error.MalformedNode;

            const next_height = current.height - 1;
            for (manifest.s[0 .. manifest.s.len - 1]) |child| {
                try self.appendNativePrefix(child, next_height);
            }
            const rightmost = manifest.s[manifest.s.len - 1];
            const filename = try self.arena.dupe(u8, rightmost.filename);
            const hash = try self.arena.dupe(u8, rightmost.hash);
            try self.remember(hash);
            current = .{
                .descriptor = .{
                    .card = .{ .filename = filename, .hash = hash },
                    .origin = hash,
                },
                .height = next_height,
            };
        }
        try self.reopenPrefixGroup(current, child_height, out);
    }

    /// Expand exactly one predecessor group into its direct descriptor stream.
    /// Earlier descriptors at that height remain native prefix candidates.
    fn reopenPrefixGroup(
        self: *OldTreeCursor,
        group: NativePrefixDescriptor,
        child_height: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!void {
        std.debug.assert(group.height == child_height + 1);
        var node = try self.editor_.loadNode(group.descriptor.card.hash);
        defer node.deinit();
        const manifest = node.manifest();
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
        if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
        if (manifest.s.len > max_members) return error.MalformedNode;
        for (manifest.s) |child| {
            try self.appendDescriptor(child, out);
            try self.remember(child.hash);
        }
    }

    /// Descend to the changed leaf, then reopen its predecessor. Earlier
    /// siblings remain direct descriptors at their original heights, so the
    /// cursor never walks their leaves or F cards.
    fn seek(self: *OldTreeCursor, path: []const u8) Error!void {
        switch (self.root) {
            .flat => {
                self.flat_index = 0;
                return;
            },
            .tree => |roots| {
                if (roots.len == 0) return error.MalformedNode;
                const root_index = childIndexForPath(roots, path);
                self.root_index = root_index + 1;
                try self.descend(roots[root_index].hash, roots[root_index].filename);

                while (true) {
                    const frame = &self.frames.items[self.frames.items.len - 1];
                    const manifest = frame.node.manifest();
                    if (manifest.f.len != 0) break;
                    if (manifest.s.len == 0) return error.WrongNodeType;
                    const child_index = childIndexForPath(manifest.s, path);
                    frame.index = child_index + 1;
                    try self.descend(manifest.s[child_index].hash, manifest.s[child_index].filename);
                }
                try self.rewindToPredecessorLeaf();

                const leaf_height = self.frames.items.len;
                for (roots[0 .. self.root_index - 1]) |child| {
                    try self.appendNativePrefix(child, leaf_height);
                }
                for (self.frames.items[0 .. self.frames.items.len - 1], 0..) |frame, depth| {
                    const manifest = frame.node.manifest();
                    const child_index = frame.index - 1;
                    const child_height = leaf_height - depth - 1;
                    for (manifest.s[0..child_index]) |child| {
                        try self.appendNativePrefix(child, child_height);
                    }
                }
            },
        }
    }

    /// The checkpoint look-ahead has already entered its next leaf. Complete
    /// that leaf, then expose the remainder of its immediate parent group.
    /// The resulting continuation state retains its fixed group depth: frames
    /// below it are the next-level frontier, while every retired frame has
    /// contributed all direct children to this continuation or the rebuilt
    /// descriptor stream.
    fn appendCheckpointLevel(
        self: *OldTreeCursor,
        include_next_leaf: bool,
        out: *std.ArrayList(Descriptor),
    ) Error!bool {
        if (self.frames.items.len > self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
        self.checkpoint = null;

        if (include_next_leaf) {
            if (self.frames.items.len == 0) return error.MalformedNode;
            const leaf = self.frames.items[self.frames.items.len - 1];
            const manifest = leaf.node.manifest();
            if (manifest.f.len == 0) return error.WrongNodeType;
            if (manifest.f.len > max_members) return error.MalformedNode;
            try self.appendLeaf(leaf.name, manifest, out);
            try self.finishCheckpointFrame();
        }
        if (self.frames.items.len == 0) return false;

        const frame = &self.frames.items[self.frames.items.len - 1];
        const manifest = frame.node.manifest();
        if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
        if (manifest.s.len > max_members) return error.MalformedNode;
        while (frame.index < manifest.s.len) {
            const child = manifest.s[frame.index];
            frame.index += 1;
            try self.appendDescriptor(child, out);
        }
        try self.finishCheckpointFrame();
        if (self.frames.items.len == 0) return false;
        self.setCheckpointContinuation(self.frames.items.len);
        return true;
    }

    /// Continue exactly one semantic descriptor height. A direct-root
    /// completion ends this state immediately; its siblings remain native for
    /// root handoff rather than becoming a provisional same-height suffix.
    fn appendNextCheckpointGroup(
        self: *OldTreeCursor,
        group_depth: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!bool {
        if (try self.checkpointDepth() != group_depth) return error.MalformedNode;
        if (self.frames.items.len > self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
        const roots = switch (self.root) {
            .flat => return false,
            .tree => |cards| cards,
        };

        while (true) {
            if (self.frames.items.len == group_depth + 1) {
                const frame = &self.frames.items[self.frames.items.len - 1];
                const manifest = frame.node.manifest();
                if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
                if (manifest.s.len > max_members) return error.MalformedNode;
                while (frame.index < manifest.s.len) {
                    const child = manifest.s[frame.index];
                    frame.index += 1;
                    try self.appendDescriptor(child, out);
                }
                if (group_depth == 0) {
                    try self.finishCheckpointFrame();
                    return false;
                }
                self.discardLastFrame();
                self.setCheckpointContinuation(group_depth);
                if (self.frames.items.len != group_depth) return error.MalformedNode;
                return true;
            }
            if (self.frames.items.len > group_depth + 1) return error.MalformedNode;

            if (self.frames.items.len != 0) {
                const frame = &self.frames.items[self.frames.items.len - 1];
                const manifest = frame.node.manifest();
                if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
                if (manifest.s.len > max_members) return error.MalformedNode;
                if (frame.index < manifest.s.len) {
                    const child = manifest.s[frame.index];
                    frame.index += 1;
                    try self.descend(child.hash, child.filename);
                    continue;
                }
                if (self.frames.items.len == 1) try self.recordRootCheckpoint();
                self.discardLastFrame();
                continue;
            }

            if (self.root_index == roots.len) return false;
            self.checkpoint = null;
            const child = roots[self.root_index];
            if (self.previous_root) |previous| {
                if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
            }
            self.previous_root = child.filename;
            self.root_index += 1;
            try self.descend(child.hash, child.filename);
        }
    }

    fn next(self: *OldTreeCursor) Error!?StreamEntry {
        switch (self.root) {
            .flat => |entries| {
                if (self.flat_index == entries.len) return null;
                const card = entries[self.flat_index];
                self.flat_index += 1;
                return @as(?StreamEntry, try self.returned(card, null));
            },
            .tree => |roots| while (true) {
                if (self.frames.items.len == 0) {
                    if (self.root_index == roots.len) return null;
                    const child = roots[self.root_index];
                    if (self.previous_root) |previous| if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
                    self.previous_root = child.filename;
                    self.root_index += 1;
                    try self.descend(child.hash, child.filename);
                    continue;
                }
                const frame = &self.frames.items[self.frames.items.len - 1];
                const manifest = frame.node.manifest();
                if (manifest.f.len != 0) {
                    if (frame.index < manifest.f.len) {
                        const card = manifest.f[frame.index];
                        frame.index += 1;
                        return @as(?StreamEntry, try self.returned(card, frame.name));
                    }
                } else {
                    if (frame.index < manifest.s.len) {
                        const child = manifest.s[frame.index];
                        frame.index += 1;
                        try self.descend(child.hash, child.filename);
                        continue;
                    }
                }
                if (self.frames.pop()) |finished| {
                    var owned = finished;
                    owned.node.deinit();
                }
            },
        }
    }
};

const MergedCursor = struct {
    old: *OldTreeCursor,
    overlay: *const Overlay,
    old_next: ?StreamEntry = null,
    overlay_index: usize = 0,
    /// Null under a flat format. Absence is structural rather than a flag a
    /// reader could forget to consult -- and it is not cosmetic: `consumeOld`
    /// hashes one retained filename per card per commit, which in the mode
    /// built to be measured would be O(files x commits) of pure waste feeding
    /// a checkpoint machinery that flat mode never consults.
    old_partitioner: ?partition.CanonicalPartitioner,
    last_was_old: bool = false,

    fn init(old: *OldTreeCursor, overlay: *const Overlay, arena: std.mem.Allocator, shape: TreeFormat.Shape) MergedCursor {
        return .{
            .old = old,
            .overlay = overlay,
            .old_partitioner = switch (shape) {
                .flat => null,
                .tree => |tree| blk: {
                    const span: usize = @as(usize, 1) << tree.k;
                    break :blk partition.CanonicalPartitioner.init(arena, @as(u16, tree.k), span / 4, 4 * span);
                },
            },
        };
    }

    fn deinit(self: *MergedCursor) void {
        if (self.old_partitioner) |*partitioner| partitioner.deinit();
        self.* = undefined;
    }

    fn consumeOld(self: *MergedCursor) Error!StreamEntry {
        const old = self.old_next.?;
        try self.old.setPreviousCard(old.card.filename);
        self.old_next = null;
        if (self.old_partitioner) |*partitioner| {
            _ = try partitioner.push(artifact.zbits(old.card.filename));
        }
        return old;
    }

    fn suffixCheckpoint(self: *MergedCursor) Error!?partition.CanonicalPartitioner.Checkpoint {
        const partitioner = if (self.old_partitioner) |*value| value else return null;
        if (!self.last_was_old or self.overlay.clear or self.overlay_index != self.overlay.entries.items.len) return null;
        if (self.old_next == null) {
            try self.old.savePreviousCard();
            self.old_next = try self.old.next();
            try self.old.restorePreviousCard();
        }
        return partitioner.checkpoint(if (self.old_next) |old| old.card.filename else null);
    }

    fn next(self: *MergedCursor) Error!?StreamEntry {
        self.last_was_old = false;
        while (true) {
            if (self.old_next == null) self.old_next = try self.old.next();
            const patch = if (self.overlay_index < self.overlay.entries.items.len) self.overlay.entries.items[self.overlay_index] else null;
            if (self.old_next) |old| {
                if (patch) |entry| {
                    switch (artifact.compareBytes(old.card.filename, entry.path)) {
                        .lt => {
                            const retained = try self.consumeOld();
                            if (!self.overlay.clear) {
                                self.last_was_old = true;
                                return retained;
                            }
                        },
                        .gt => {
                            self.overlay_index += 1;
                            if (entry.value) |card| return .{ .card = card, .origin = null };
                        },
                        .eq => {
                            _ = try self.consumeOld();
                            self.overlay_index += 1;
                            if (entry.value) |card| return .{ .card = card, .origin = null };
                        },
                    }
                } else {
                    const retained = try self.consumeOld();
                    if (!self.overlay.clear) {
                        self.last_was_old = true;
                        return retained;
                    }
                }
            } else {
                if (patch) |entry| {
                    self.overlay_index += 1;
                    if (entry.value) |card| return .{ .card = card, .origin = null };
                } else return null;
            }
        }
    }
};

const StreamBuild = struct {
    root: RootRun,
    tree_height: u8,
    reused_nodes: usize,
    emitted_nodes: usize,
};

const StreamBuilder = struct {
    editor_: *TreeEditor,
    arena: std.mem.Allocator,
    known_nodes: *const KnownNodes,
    reused_nodes: usize = 0,
    emitted_nodes: usize = 0,
    staged: std.ArrayList(StoreBatchNode) = .empty,

    fn init(editor_: *TreeEditor, arena: std.mem.Allocator, known_nodes: *const KnownNodes) StreamBuilder {
        return .{ .editor_ = editor_, .arena = arena, .known_nodes = known_nodes };
    }

    /// A candidate can recreate an immutable ancestor that the current tree
    /// no longer reaches after a grow/shrink boundary. Consult storage after
    /// the traversal-local fast path, but only reuse bytes that exactly match
    /// the candidate serialization.
    fn known(self: *const StreamBuilder, name: []const u8, bytes: []const u8) Error!bool {
        if (self.known_nodes.contains(name)) return true;
        var loaded = self.editor_.store.load_fn(self.editor_.store.ctx, self.editor_.gpa, name) catch |err| switch (err) {
            error.MissingNode => return false,
            else => return err,
        };
        defer loaded.deinit();
        if (!std.mem.eql(u8, loaded.bytes, bytes)) return error.MalformedNode;
        return true;
    }

    /// Store writes are delayed until the complete output root and every
    /// descriptor have been allocated.  This leaves no allocation failure
    /// after the first newly-addressable artifact is written.
    fn publishStaged(self: *StreamBuilder) Error!void {
        if (self.staged.items.len == 0) return;

        const batch: []const StoreBatchNode = self.staged.items;
        try self.editor_.store.put_batch_fn(self.editor_.store.ctx, batch);
        self.emitted_nodes += batch.len;
    }

    fn emitLeaf(self: *StreamBuilder, group: []const StreamEntry, out: *std.ArrayList(Descriptor)) Error!void {
        try out.ensureUnusedCapacity(self.arena, 1);
        try self.staged.ensureUnusedCapacity(self.arena, 1);
        const cards = try self.arena.alloc(artifact.FCard, group.len);
        for (group, cards) |entry, *card| card.* = entry.card;
        const bytes = artifact.serializeSubmanifestLeaf(self.arena, cards) catch |e| switch (e) {
            error.OutOfMemory => return error.OutOfMemory,
            // The partitioner never emits an empty group, and `cards[0]` below
            // would fault if it did. Mapped rather than asserted: the editor
            // already has the vocabulary for "the node we would emit is not
            // well formed", and a refusal survives --release=fast.
            error.EmptySubmanifest => return error.MalformedNode,
        };
        const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
        const already_known = try self.known(name, bytes);
        const descriptor: Descriptor = .{
            .card = .{ .filename = cards[0].filename, .hash = name },
            .origin = if (already_known) name else null,
        };
        if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
            .name = name,
            .bytes = bytes,
        });
        out.appendAssumeCapacity(descriptor);
    }

    fn emitInterior(self: *StreamBuilder, group: []const Descriptor, out: *std.ArrayList(Descriptor)) Error!void {
        try out.ensureUnusedCapacity(self.arena, 1);
        try self.staged.ensureUnusedCapacity(self.arena, 1);
        const cards = try self.arena.alloc(artifact.SCard, group.len);
        for (group, cards) |entry, *card| card.* = entry.card;
        const bytes = artifact.serializeSubmanifestInterior(self.arena, cards) catch |e| switch (e) {
            error.OutOfMemory => return error.OutOfMemory,
            // See `emitLeaf`: an empty member list is not a node this editor can
            // name, and `cards[0]` below assumes it never happens.
            error.EmptySubmanifest => return error.MalformedNode,
        };
        const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
        const already_known = try self.known(name, bytes);
        const descriptor: Descriptor = .{
            .card = .{ .filename = cards[0].filename, .hash = name },
            .origin = if (already_known) name else null,
        };
        if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
            .name = name,
            .bytes = bytes,
        });
        out.appendAssumeCapacity(descriptor);
    }

    /// draft-fossil-submanifests-00 §8.1's default posture: the merged stream
    /// IS the root.
    ///
    /// This duplicates none of the merge semantics -- rename, copy, delete,
    /// `deleteall`, ordering and dedup all stay in `Overlay` and
    /// `MergedCursor`, which this drains unchanged. What it drops is only the
    /// tree apparatus: no partitioner, no leaf or interior serialization, no
    /// staged node, and therefore no SUBMANIFEST artifact anywhere.
    ///
    /// `merged.old.prefix` is necessarily empty here -- prefix descriptors are
    /// pushed only from `OldTreeCursor` frames, and frames come only from
    /// `descend`, which only a `.tree` root reaches. `apply` has already
    /// refused a `.tree` parent under this format, so there is nothing to
    /// splice and the whole checkpoint path is dead.
    ///
    /// `StreamEntry.origin` is deliberately not carried. It names the old node
    /// a retained card came from, and its only reader is `emitLeaf`'s node
    /// reuse test -- flat mode emits no node, so duping it would be an arena
    /// allocation and copy per card per commit whose result nothing reads. That
    /// is the same O(files x commits) waste `MergedCursor.old_partitioner`
    /// avoids, in the mode built to be measured. Collecting `FCard` directly
    /// rather than `StreamEntry` makes the omission structural.
    fn buildFlat(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
        var cards: std.ArrayList(artifact.FCard) = .empty;
        // Bounded by the merged stream, whose length is one commit's path set.
        // The enforcing ceiling is the export reader's `max_events` /
        // `max_total_data` (`git_import_cli.zig`), which cap the commands that
        // reach `Overlay` before any of them reach here; the editor adds no
        // ceiling of its own in flat mode because it builds no level.
        while (try merged.next()) |entry| {
            // The card is cloned, not borrowed: `merged.next()` hands out cards
            // pointing into `OldTreeCursor`'s loaded node bytes, which are
            // released on the next advance, and this list outlives the whole
            // walk. The tree path pays the same clone, one layer earlier, when
            // it builds its `StreamEntry`s.
            try cards.append(self.arena, try cloneFCard(self.arena, entry.card));
        }
        // The local form of the invariant this whole mode turns on, checked at
        // the commit that would break it rather than at the end of the import.
        // An `assert` and not a returned error: both counters are this
        // builder's own, so a nonzero one is a broken internal invariant.
        std.debug.assert(self.emitted_nodes == 0);
        std.debug.assert(self.reused_nodes == 0);
        std.debug.assert(self.staged.items.len == 0);
        return .{
            .root = .{ .flat = try cards.toOwnedSlice(self.arena) },
            .tree_height = 0,
            // Literals rather than the counters: flat emits and reuses no node,
            // and saying so structurally keeps the claim from drifting into
            // "whatever the counters happen to hold".
            .reused_nodes = 0,
            .emitted_nodes = 0,
        };
    }

    fn buildUnpublished(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
        const tree = switch (self.editor_.format.shape) {
            .flat => return self.buildFlat(merged),
            .tree => |value| value,
        };
        const span: usize = @as(usize, 1) << tree.k;
        var partitioner = partition.CanonicalPartitioner.init(self.arena, @as(u16, tree.k), span / 4, 4 * span);
        defer partitioner.deinit();
        var pending: std.ArrayList(StreamEntry) = .empty;
        var current: std.ArrayList(StreamEntry) = .empty;
        var leaves: std.ArrayList(Descriptor) = .empty;
        const prefix_leaves = try merged.old.appendPrefixAtHeight(1, &leaves);
        self.reused_nodes += prefix_leaves;
        while (try merged.next()) |entry| {
            if (try partitioner.push(artifact.zbits(entry.card.filename))) {
                if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
                pending = current;
                current = .empty;
            }
            try current.append(self.arena, .{
                .card = try cloneFCard(self.arena, entry.card),
                .origin = if (entry.origin) |name| try self.arena.dupe(u8, name) else null,
            });

            if (!merged.last_was_old or !merged.old.atLeafEnd()) continue;
            const old_checkpoint = (try merged.suffixCheckpoint()) orelse continue;
            const next_key = old_checkpoint.next_key orelse continue;
            const new_checkpoint = partitioner.checkpoint(next_key);
            if (!partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) continue;

            if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
            try self.emitLeaf(current.items, &leaves);
            // suffixCheckpoint prefetched one card from the next leaf. Its
            // frame remains live, so hand the old cursor to the level builder
            // rather than expanding its entire suffix into leaf descriptors.
            merged.old_next = null;
            return self.finishCheckpoint(leaves, merged.old);
        }
        const bounds = try partitioner.finish();
        if (bounds.len == 0 or partition.groupCount(bounds) <= 1) {
            // A retained old descriptor forces a tree even when the merged
            // stream alone reduces to one group. `prefix_leaves` counts the
            // height-one descriptors already spliced into `leaves`; whatever
            // remains in `prefix` sits above them.
            if (prefix_leaves != 0 or merged.old.prefix.items.len != 0) {
                if (pending.items.len != 0) try pending.appendSlice(self.arena, current.items);
                if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves) else if (current.items.len != 0) try self.emitLeaf(current.items, &leaves);
                return self.finishTree(leaves, merged.old);
            }
            if (pending.items.len != 0) try pending.appendSlice(self.arena, current.items);
            return .{
                .root = .{ .flat = try streamCards(self.arena, if (pending.items.len != 0) pending.items else current.items) },
                .tree_height = 0,
                .reused_nodes = self.reused_nodes,
                .emitted_nodes = self.emitted_nodes,
            };
        }
        const final_boundary = partitioner.count - current.items.len;
        var keeps_final_boundary = false;
        for (bounds[1 .. bounds.len - 1]) |boundary| {
            if (boundary == final_boundary) {
                keeps_final_boundary = true;
                break;
            }
        }
        if (keeps_final_boundary) {
            try self.emitLeaf(pending.items, &leaves);
            try self.emitLeaf(current.items, &leaves);
        } else {
            try pending.appendSlice(self.arena, current.items);
            try self.emitLeaf(pending.items, &leaves);
        }
        return self.finishTree(leaves, merged.old);
    }

    fn build(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
        var result = try self.buildUnpublished(merged);
        try self.publishStaged();
        result.reused_nodes = self.reused_nodes;
        result.emitted_nodes = self.emitted_nodes;
        return result;
    }

    fn finishTree(self: *StreamBuilder, leaves: std.ArrayList(Descriptor), old: *OldTreeCursor) Error!StreamBuild {
        var level = leaves;
        var height: usize = 1;
        while (height < self.editor_.format.shape.tree.height_max) {
            const next_height = height + 1;
            if (old.takePrefixAtHeight(next_height)) |predecessor_group| {
                var reopened: std.ArrayList(Descriptor) = .empty;
                try old.reopenPrefixGroup(predecessor_group, height, &reopened);
                try reopened.appendSlice(self.arena, level.items);
                level = reopened;
            }

            var rebuilt: std.ArrayList(Descriptor) = .empty;
            if (!try self.buildInteriorLevel(level.items, height, &rebuilt)) {
                // A retained ancestor can skip the immediate next height. Walk
                // only its rightmost path to recover the direct predecessor
                // stream, leaving all earlier siblings native and bounded.
                if (old.takePrefixAboveHeight(next_height)) |ancestor| {
                    var reopened: std.ArrayList(Descriptor) = .empty;
                    try old.reopenRightmostPrefixAtHeight(ancestor, height, &reopened);
                    try reopened.appendSlice(self.arena, level.items);
                    level = reopened;
                    continue;
                }
                break;
            }

            var next: std.ArrayList(Descriptor) = .empty;
            const reused = try old.appendPrefixAtHeight(next_height, &next);
            self.reused_nodes += reused;
            try next.appendSlice(self.arena, rebuilt.items);
            level = next;
            height = next_height;
        }
        return .{
            .root = .{ .tree = try descriptorCards(self.arena, level.items) },
            .tree_height = @intCast(height),
            .reused_nodes = self.reused_nodes,
            .emitted_nodes = self.emitted_nodes,
        };
    }
    fn mergeRootPrefixes(
        self: *StreamBuilder,
        old: *OldTreeCursor,
        level: *std.ArrayList(Descriptor),
        height: usize,
    ) Error!void {
        while (true) {
            const next_height = height + 1;
            if (old.takePrefixAtHeight(next_height)) |predecessor_group| {
                var reopened: std.ArrayList(Descriptor) = .empty;
                try old.reopenPrefixGroup(predecessor_group, height, &reopened);
                try reopened.appendSlice(self.arena, level.items);
                level.* = reopened;
                continue;
            }
            if (old.takePrefixAboveHeight(next_height)) |ancestor| {
                var reopened: std.ArrayList(Descriptor) = .empty;
                try old.reopenRightmostPrefixAtHeight(ancestor, height, &reopened);
                try reopened.appendSlice(self.arena, level.items);
                level.* = reopened;
                continue;
            }
            break;
        }
        // Last chance to splice: `finishRootLevel` never consults the cursor
        // again, so anything still retained here would be dropped from the
        // tree. The splice is consuming, so this is a no-op whenever the
        // caller already owns this height rather than a second copy of it.
        if (old.hasPrefixAtHeight(height)) {
            var prefixed: std.ArrayList(Descriptor) = .empty;
            self.reused_nodes += try old.appendPrefixAtHeight(height, &prefixed);
            try prefixed.appendSlice(self.arena, level.items);
            level.* = prefixed;
        }
    }

    fn finishRootLevel(
        self: *StreamBuilder,
        level: std.ArrayList(Descriptor),
        start_height: usize,
    ) Error!StreamBuild {
        var current = level;
        var height = start_height;
        while (height < self.editor_.format.shape.tree.height_max) {
            var raised: std.ArrayList(Descriptor) = .empty;
            if (!try self.buildInteriorLevel(current.items, height, &raised)) break;
            current = raised;
            height += 1;
        }
        return .{
            .root = .{ .tree = try descriptorCards(self.arena, current.items) },
            .tree_height = @intCast(height),
            .reused_nodes = self.reused_nodes,
            .emitted_nodes = self.emitted_nodes,
        };
    }

    /// Rebuild each descriptor height until an equivalent old checkpoint, then
    /// hand the final direct-root node to the result only at its measured
    /// height. A cursor level is fixed-depth even when continuation crosses
    /// several exhausted ancestors, so a height advances exactly once per
    /// rebuilt descriptor level.
    fn finishCheckpoint(
        self: *StreamBuilder,
        leaves: std.ArrayList(Descriptor),
        old: *OldTreeCursor,
    ) Error!StreamBuild {
        var level = leaves;
        var height: usize = 1;
        var include_next_leaf = true;
        var root_height: ?usize = null;
        while (true) {
            if (height > 1 and old.hasPrefixAtHeight(height)) {
                var prefixed: std.ArrayList(Descriptor) = .empty;
                self.reused_nodes += try old.appendPrefixAtHeight(height, &prefixed);
                try prefixed.appendSlice(self.arena, level.items);
                level = prefixed;
            }

            var old_continuation: std.ArrayList(Descriptor) = .empty;
            var old_group_start: ?usize = null;
            if (root_height == null) {
                const has_parent = try old.appendCheckpointLevel(include_next_leaf, &old_continuation);
                self.reused_nodes += old_continuation.items.len;
                if (has_parent) {
                    if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;

                    const group_depth = try old.checkpointDepth();
                    var splice_at: ?usize = null;
                    var reached_root = false;
                    while (splice_at == null) {
                        const continuation_start = old_continuation.items.len;
                        if (!try old.appendNextCheckpointGroup(group_depth, &old_continuation)) {
                            reached_root = true;
                            break;
                        }
                        self.reused_nodes += old_continuation.items.len - continuation_start;
                        if (old_group_start == null) old_group_start = continuation_start;
                        splice_at = try self.findInteriorSplice(
                            level.items,
                            old_continuation.items,
                            old_group_start,
                            height,
                        );
                    }
                    if (!reached_root) {
                        var next: std.ArrayList(Descriptor) = .empty;
                        try self.buildInteriorPrefix(level.items, old_continuation.items, old_group_start, height, &next);
                        level = next;
                        height += 1;
                        include_next_leaf = false;
                        continue;
                    }
                }
                const measured_root_height = try old.takeRootCheckpoint();
                if (height > measured_root_height) return error.MalformedNode;
                root_height = measured_root_height;
            }

            const native_root_height = root_height.?;
            if (height == native_root_height) {
                const suffix_start = old_continuation.items.len;
                try old.appendRootSuffixAtRootHeight(native_root_height, &old_continuation);
                self.reused_nodes += old_continuation.items.len - suffix_start;
                try level.appendSlice(self.arena, old_continuation.items);
                try self.mergeRootPrefixes(old, &level, height);
                return self.finishRootLevel(level, height);
            }
            if (height > native_root_height) return error.MalformedNode;
            if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;

            var splice_at: ?usize = null;
            while (splice_at == null) {
                const frontier_start = old_continuation.items.len;
                switch (try old.appendRootSuffixFrontierAtHeight(native_root_height, height, &old_continuation)) {
                    .descriptor => {
                        self.reused_nodes += old_continuation.items.len - frontier_start;
                    },
                    .group => {
                        self.reused_nodes += old_continuation.items.len - frontier_start;
                        if (old_group_start == null) old_group_start = frontier_start;
                        splice_at = try self.findInteriorSplice(
                            level.items,
                            old_continuation.items,
                            old_group_start,
                            height,
                        );
                        // `buildInteriorPrefix` reconstructs every exposed
                        // group into the next level, including a group whose
                        // splice starts at its first child. The raw suffix
                        // parent must therefore be consumed before that next
                        // level can append it again at root height.
                        try old.commitRootSuffixFrontier(height);
                    },
                    .end => {
                        try level.appendSlice(self.arena, old_continuation.items);
                        try self.mergeRootPrefixes(old, &level, height);
                        return self.finishRootLevel(level, height);
                    },
                }
            }

            var next: std.ArrayList(Descriptor) = .empty;
            try self.buildInteriorPrefix(level.items, old_continuation.items, old_group_start, height, &next);
            level = next;
            height += 1;
            include_next_leaf = false;
        }
    }

    /// Reuse begins only at the start of a complete untouched old canonical
    /// group. The initial checkpoint remainder may be mid-group, so it is
    /// replayed into the rebuilt state but never treated as old state.
    fn findInteriorSplice(
        self: *StreamBuilder,
        rebuilt: []const Descriptor,
        old_continuation: []const Descriptor,
        old_group_start: ?usize,
        height: usize,
    ) Error!?usize {
        const start = old_group_start orelse return null;
        const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
        const min_members = span / 4;
        const max_members = 4 * span;
        var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
        defer old_partitioner.deinit();
        var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
        defer new_partitioner.deinit();
        var equivalent_splices: std.ArrayList(usize) = .empty;

        for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
        for (old_continuation[0..start]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
        for (old_continuation[start..], start..) |entry, old_index| {
            if (old_partitioner.count != 0 and old_partitioner.bounds.items.len >= 2) {
                const open_members = old_partitioner.count - old_partitioner.bounds.items[old_partitioner.bounds.items.len - 1];
                const starts_old_group = open_members == max_members or
                    (artifact.zbits(entry.card.filename) >= threshold and open_members >= min_members);
                if (starts_old_group) {
                    const old_checkpoint = old_partitioner.checkpoint(entry.card.filename);
                    const new_checkpoint = new_partitioner.checkpoint(entry.card.filename);
                    if (partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) {
                        try equivalent_splices.append(self.arena, old_index);
                    }
                }
            }
            _ = try old_partitioner.push(artifact.zbits(entry.card.filename));
            _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
        }

        const old_bounds = try old_partitioner.finish();
        for (equivalent_splices.items) |candidate| {
            for (old_bounds) |bound| {
                if (bound == candidate - start) return candidate;
            }
        }
        return null;
    }

    /// `rebuilt` is the newly emitted continuation. `old_continuation` is
    /// independently read from the old descriptor stream. Once both
    /// partitioners reach the same checkpoint at an old canonical boundary,
    /// the old partitioner owns the remaining suffix rather than replaying it
    fn buildInteriorPrefix(
        self: *StreamBuilder,
        rebuilt: []const Descriptor,
        old_continuation: []const Descriptor,
        old_group_start: ?usize,
        height: usize,
        out: *std.ArrayList(Descriptor),
    ) Error!void {
        const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
        const min_members = span / 4;
        const max_members = 4 * span;
        const splice_at = try self.findInteriorSplice(rebuilt, old_continuation, old_group_start, height);
        if (splice_at) |old_splice| {
            const start = old_group_start orelse return error.MalformedNode;
            var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
            defer old_partitioner.deinit();
            for (old_continuation[start..]) |entry| _ = try old_partitioner.push(artifact.zbits(entry.card.filename));
            const old_bounds = try old_partitioner.finish();

            var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
            defer new_partitioner.deinit();
            for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
            for (old_continuation[0..old_splice]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
            // The equivalent checkpoint owns the still-open new group. Do not
            // call `finish`: its EOF rule would serialize that partial group
            // and prevent the old suffix from supplying its canonical tail.
            const completed_bounds = new_partitioner.bounds.items;

            var rebuilt_start: usize = 0;
            for (completed_bounds[1..]) |end| {
                if (end <= rebuilt.len) {
                    try self.emitInterior(rebuilt[rebuilt_start..end], out);
                } else if (rebuilt_start >= rebuilt.len) {
                    try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. end - rebuilt.len], out);
                } else {
                    const members = try self.arena.alloc(Descriptor, end - rebuilt_start);
                    const rebuilt_members = rebuilt.len - rebuilt_start;
                    @memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
                    @memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
                    try self.emitInterior(members, out);
                }
                rebuilt_start = end;
            }
            // `old_splice` is the next item at the equivalent checkpoint. The
            // partitioner has deliberately not consumed it, so its boundary
            // is absent from `bounds`; finalize the preceding canonical group
            // explicitly instead of dropping it or serializing the suffix's
            // open final group.
            const prefix_end = rebuilt.len + old_splice;
            if (rebuilt_start != prefix_end) {
                if (prefix_end <= rebuilt.len) {
                    try self.emitInterior(rebuilt[rebuilt_start..prefix_end], out);
                } else if (rebuilt_start >= rebuilt.len) {
                    try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. old_splice], out);
                } else {
                    const members = try self.arena.alloc(Descriptor, prefix_end - rebuilt_start);
                    const rebuilt_members = rebuilt.len - rebuilt_start;
                    @memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
                    @memcpy(members[rebuilt_members..], old_continuation[0..old_splice]);
                    try self.emitInterior(members, out);
                }
            }

            var old_start = start;
            for (old_bounds[1..]) |relative_end| {
                const end = start + relative_end;
                if (old_start >= old_splice) try self.emitInterior(old_continuation[old_start..end], out);
                old_start = end;
            }
            return;
        }

        var fallback = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
        defer fallback.deinit();
        for (rebuilt) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
        for (old_continuation) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
        const fallback_bounds = try fallback.finish();
        if (fallback_bounds.len < 2) return error.MalformedNode;
        var fallback_start: usize = 0;
        for (fallback_bounds[1..]) |end| {
            if (end <= rebuilt.len) {
                try self.emitInterior(rebuilt[fallback_start..end], out);
            } else if (fallback_start >= rebuilt.len) {
                try self.emitInterior(old_continuation[fallback_start - rebuilt.len .. end - rebuilt.len], out);
            } else {
                const members = try self.arena.alloc(Descriptor, end - fallback_start);
                const rebuilt_members = rebuilt.len - fallback_start;
                @memcpy(members[0..rebuilt_members], rebuilt[fallback_start..]);
                @memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
                try self.emitInterior(members, out);
            }
            fallback_start = end;
        }
    }
    /// a singleton or non-reducing level is returned to its caller unchanged.
    fn buildInteriorLevel(self: *StreamBuilder, input: []const Descriptor, height: usize, out: *std.ArrayList(Descriptor)) Error!bool {
        const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
        var partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, span / 4, 4 * span);
        defer partitioner.deinit();
        for (input) |entry| _ = try partitioner.push(artifact.zbits(entry.card.filename));
        const bounds = try partitioner.finish();
        const count = partition.groupCount(bounds);
        if (count <= 1 or count >= input.len) return false;
        var start: usize = 0;
        for (bounds[1..]) |end| {
            try self.emitInterior(input[start..end], out);
            start = end;
        }
        return true;
    }
};

fn streamCards(arena: std.mem.Allocator, entries: []const StreamEntry) std.mem.Allocator.Error![]const artifact.FCard {
    const cards = try arena.alloc(artifact.FCard, entries.len);
    for (entries, cards) |entry, *card| card.* = entry.card;
    return cards;
}

fn descriptorCards(arena: std.mem.Allocator, entries: []const Descriptor) std.mem.Allocator.Error![]const artifact.SCard {
    const cards = try arena.alloc(artifact.SCard, entries.len);
    for (entries, cards) |entry, *card| card.* = entry.card;
    return cards;
}

/// A `.tree` root handed to a `.flat` editor. Both public entry points that
/// accept a caller-supplied `RootView` -- `apply` and `lookup` -- refuse it
/// here, so the same bad argument gets the same answer from both rather than
/// `InvalidFormat` from one and a union-tag panic from the other. See `apply`
/// for why no such root can exist under the flat induction.
fn rootMismatchesFormat(shape: TreeFormat.Shape, root: RootView) bool {
    return std.meta.activeTag(shape) == .flat and std.meta.activeTag(root) == .tree;
}

fn lookupFlat(entries: []const artifact.FCard, path: []const u8) ?artifact.FCard {
    const index = lowerBound(entries, path);
    if (index < entries.len and std.mem.eql(u8, entries[index].filename, path)) return entries[index];
    return null;
}

fn childForPath(cards: []const artifact.SCard, path: []const u8) ?artifact.SCard {
    var candidate: ?artifact.SCard = null;
    for (cards) |card| {
        if (artifact.compareBytes(card.filename, path) == .gt) break;
        candidate = card;
    }
    return candidate;
}

/// Index of the direct child that contains `path`, or the first child when the
/// requested path precedes the range. This is a binary seek over S cards, never
/// an F-card walk.
fn childIndexForPath(cards: []const artifact.SCard, path: []const u8) usize {
    std.debug.assert(cards.len != 0);
    var low: usize = 0;
    var high = cards.len;
    while (low < high) {
        const mid = low + (high - low) / 2;
        if (artifact.compareBytes(cards[mid].filename, path) != .gt) low = mid + 1 else high = mid;
    }
    return if (low == 0) 0 else low - 1;
}

fn lowerBound(entries: []const artifact.FCard, path: []const u8) usize {
    var low: usize = 0;
    var high = entries.len;
    while (low < high) {
        const mid = low + (high - low) / 2;
        if (artifact.compareBytes(entries[mid].filename, path) == .lt) low = mid + 1 else high = mid;
    }
    return low;
}

fn nameArtifact(
    arena: std.mem.Allocator,
    algo: artifact.HashAlgo,
    bytes: []const u8,
) std.mem.Allocator.Error![]const u8 {
    var scratch: [64]u8 = undefined;
    return arena.dupe(u8, artifact.artifactName(algo, bytes, &scratch));
}

fn cloneFCards(arena: std.mem.Allocator, entries: []const artifact.FCard) std.mem.Allocator.Error![]const artifact.FCard {
    const copied = try arena.alloc(artifact.FCard, entries.len);
    for (entries, copied) |entry, *dest| dest.* = try cloneFCard(arena, entry);
    return copied;
}

fn cloneSCards(arena: std.mem.Allocator, cards: []const artifact.SCard) std.mem.Allocator.Error![]const artifact.SCard {
    const copied = try arena.alloc(artifact.SCard, cards.len);
    for (cards, copied) |card, *dest| dest.* = .{
        .filename = try arena.dupe(u8, card.filename),
        .hash = try arena.dupe(u8, card.hash),
    };
    return copied;
}

fn cloneFCard(arena: std.mem.Allocator, value: artifact.FCard) std.mem.Allocator.Error!artifact.FCard {
    return .{
        .filename = try arena.dupe(u8, value.filename),
        .hash = if (value.hash) |hash| try arena.dupe(u8, hash) else null,
        .perm = if (value.perm) |perm| try arena.dupe(u8, perm) else null,
        .old_name = if (value.old_name) |old| try arena.dupe(u8, old) else null,
        .mode = value.mode,
    };
}

comptime {
    _ = partition.CanonicalPartitioner;
}