Artifact [3054898bbe]

Artifact 3054898bbe9377edfcddad47fe25ec05666a011248f90e18add776f5cf19bcb5:

• File src/submanifest_editor.zig — part of check-in [4a95e436af] at 2026-07-31 02:39:50 on branch sub-manifest — submanifest: incremental apply must equal canonical construction

  The incremental tree editor diverged from buildTree on realistic filename distributions. OldTreeCursor.appendPrefixAtHeight read the retained native-prefix list without consuming it, so one descriptor could be spliced into two different output levels: buildUnpublished placed the height-1 prefixes into the leaves, and mergeRootPrefixes then prepended the identical descriptor again before finishRootLevel. The emitted interior node carried the same S key twice, which fails artifact.parse's ascending-S guard, so an import aborted partway through a real history with a SyntaxError raised by our own grammar.

  finishCheckpoint already guarded its own splice with a height test. That guard was an ad-hoc workaround for this same double-append, and mergeRootPrefixes never had one. The splice now consumes what it emits, so a retained descriptor lands in exactly one level and the guard becomes unnecessary rather than duplicated.

  Found by importing marktext, not by the suite. Every name corpus here was uniform, and a duplicated prefix descriptor requires names that share prefixes at differing depths, so 55 tests could pass over a defect that breaks real repositories. The new seeded differential sweep generates four corpora of 136 to 240 paths with mixed depth, shared directories, dotfiles and 1 to 43 byte basenames, over every supported k with twelve batches each, and asserts it reached a tree at least three levels deep so it cannot quietly degrade into testing flat roots. It diverges in 20 of 452 batches against the unfixed editor, every divergence unparseable.

  The decoded-root validation memo lands alongside it: repeated lookupTree validation against an unchanged root is answered once instead of rebuilt, which takes this file's own 56 tests from 1701 to 450 seconds over identical assertions. (user: dmestas, size: 100534) [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;

pub const TreeFormat = struct {
    k: u4,
    hash_algo: artifact.HashAlgo,
    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 {
        if (format.k < artifact.min_k or format.k > artifact.max_k or
            format.height_max == 0 or format.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 {
        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;
        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.k);
        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.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.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.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.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.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.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.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.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.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.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.height_max) return error.HeightExceeded;
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.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.height_max) return error.HeightExceeded;
        const max_members = 4 * (@as(usize, 1) << self.editor_.format.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,
    old_partitioner: partition.CanonicalPartitioner,
    last_was_old: bool = false,

    fn init(old: *OldTreeCursor, overlay: *const Overlay, arena: std.mem.Allocator, k: u4) MergedCursor {
        const span: usize = @as(usize, 1) << k;
        return .{
            .old = old,
            .overlay = overlay,
            .old_partitioner = partition.CanonicalPartitioner.init(arena, @as(u16, k), span / 4, 4 * span),
        };
    }

    fn deinit(self: *MergedCursor) void {
        self.old_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;
        _ = try self.old_partitioner.push(artifact.zbits(old.card.filename));
        return old;
    }

    fn suffixCheckpoint(self: *MergedCursor) Error!?partition.CanonicalPartitioner.Checkpoint {
        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 self.old_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 = try artifact.serializeSubmanifestLeaf(self.arena, cards);
        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 = try artifact.serializeSubmanifestInterior(self.arena, cards);
        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 buildUnpublished(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
        const span: usize = @as(usize, 1) << self.editor_.format.k;
        var partitioner = partition.CanonicalPartitioner.init(self.arena, @as(u16, self.editor_.format.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.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.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.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.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.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.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.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.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.k;
        const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.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;
}

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