const std = @import("std");
const artifact = @import("artifact.zig");
const partition = @import("submanifest_partition.zig");
/// `StringHashMapUnmanaged` uses this load factor for its default context.
const cache_index_max_load_percentage = 80;
/// How this editor names artifacts, and whether it partitions at all.
///
/// `hash_algo` sits outside `shape` because both shapes name artifacts; `k` and
/// `height_max` sit inside `.tree` because every one of their uses is on a
/// tree-only path. That placement is the point: a flat format has no field that
/// could carry a contradictory k, and every tree-only site unwraps
/// `shape.tree`, which traps rather than silently reading a stale number if the
/// flat induction (see `TreeEditor.apply`) is ever broken.
pub const TreeFormat = struct {
hash_algo: artifact.HashAlgo,
shape: Shape,
/// draft-fossil-submanifests-00 §8.1 makes flat the default posture: a
/// writer emits no S card unless the repository opted in. `.flat` is that
/// posture expressed at the editor seam — never partition, never stage a
/// SUBMANIFEST candidate — not a tuning of `.tree` that happens to yield
/// one group, which no k can guarantee (`CanonicalPartitioner.push` forces
/// a boundary unconditionally at `open == max`).
pub const Shape = union(enum) {
flat,
tree: Tree,
pub const Tree = struct {
k: u4,
height_max: u8,
};
};
};
pub const StoreError = error{
MissingNode,
StorageFailure,
OutOfMemory,
};
pub const LoadedBytes = struct {
bytes: []u8,
allocator: std.mem.Allocator,
pub fn deinit(self: *LoadedBytes) void {
self.allocator.free(self.bytes);
self.* = undefined;
}
};
/// A complete immutable artifact group. Callers submit one group when every
/// member must become visible together.
pub const StoreBatchNode = struct {
name: []const u8,
bytes: []const u8,
};
pub const PutBatchFn = *const fn (*anyopaque, []const StoreBatchNode) StoreError!void;
pub const PutFn = *const fn (*anyopaque, []const u8, []const u8) StoreError!void;
pub const LoadFn = *const fn (*anyopaque, std.mem.Allocator, []const u8) StoreError!LoadedBytes;
/// The editor's only persistence boundary. A caller cannot inject parser or
/// Git state through this interface: names and exact immutable bytes are all it
/// accepts.
pub const TreeStore = struct {
ctx: *anyopaque,
load_fn: LoadFn,
put_fn: PutFn,
put_batch_fn: PutBatchFn,
};
pub const RootView = union(enum) {
flat: []const artifact.FCard,
tree: []const artifact.SCard,
};
pub const RootRun = union(enum) {
flat: []const artifact.FCard,
tree: []const artifact.SCard,
};
pub const TreeCommand = union(enum) {
upsert: artifact.FCard,
delete: []const u8,
rename: struct { old: []const u8, new: []const u8 },
copy: struct { old: []const u8, new: []const u8 },
delete_all,
};
pub const Error = StoreError || std.mem.Allocator.Error || artifact.WriteError || error{
InvalidFormat,
MalformedNode,
WrongNodeType,
Cycle,
HeightExceeded,
MissingPath,
DuplicatePath,
InvalidCommand,
};
pub const BuildResult = struct {
root: RootRun,
/// Zero for a flat root, the S-card level count for a rebuilt tree, and
/// null only when an unchanged tree root was cloned without traversal.
tree_height: ?u8,
changed_paths: usize,
reused_nodes: usize,
emitted_nodes: usize,
arena_state: std.heap.ArenaAllocator,
pub fn deinit(self: *BuildResult) void {
self.arena_state.deinit();
self.* = undefined;
}
};
const LoadedNode = struct {
bytes: LoadedBytes,
manifest: artifact.Manifest,
fn deinit(self: *LoadedNode) void {
self.manifest.deinit();
self.bytes.deinit();
self.* = undefined;
}
};
const CacheEntry = struct {
link: std.DoublyLinkedList.Node = .{},
name: []u8,
node: LoadedNode,
leases: usize = 0,
};
/// A decoded node held either by the cache or by its caller. Cached nodes stay
/// pinned while a traversal borrows them, so FIFO eviction cannot invalidate a
/// parent frame during recursive descent.
const NodeLease = union(enum) {
cached: *CacheEntry,
owned: LoadedNode,
fn manifest(self: *const NodeLease) *const artifact.Manifest {
return switch (self.*) {
.cached => |entry| &entry.node.manifest,
.owned => |*node| &node.manifest,
};
}
fn deinit(self: *NodeLease) void {
switch (self.*) {
.cached => |entry| {
std.debug.assert(entry.leases != 0);
entry.leases -= 1;
},
.owned => |*node| node.deinit(),
}
self.* = undefined;
}
};
/// A repository-bound reader and canonical writer. Callers pass one
/// call-scoped root view each time; only immutable root identity and its
/// construction parameter survive as partition evidence between calls.
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,
/// Derivation evidence survives store rebinding: hashes bind immutable
/// bytes, and only this construction under `canonical_k` records a root.
canonical_root: ?[]const artifact.SCard = null,
canonical_k: ?u4 = null,
canonical_root_arena: std.heap.ArenaAllocator,
/// Direct S-card descriptors inspected by the current `apply` route.
/// This is a testable work counter; cached-node and serialization work are
/// intentionally excluded.
touched_search_steps: usize = 0,
pub fn init(
gpa: std.mem.Allocator,
store: TreeStore,
format: TreeFormat,
cache_bytes_max: usize,
) Error!TreeEditor {
switch (format.shape) {
// A flat format has no range to check: it carries no k and no
// height, which is exactly why it cannot be misconfigured.
.flat => {},
.tree => |tree| if (tree.k < artifact.min_k or tree.k > artifact.max_k or
tree.height_max == 0 or tree.height_max > @as(u8, @intCast(artifact.max_construct_height)))
{
return error.InvalidFormat;
},
}
return .{
.gpa = gpa,
.store = store,
.format = format,
.cache_bytes_max = cache_bytes_max,
.lookup_arena = std.heap.ArenaAllocator.init(gpa),
.validated_root_arena = std.heap.ArenaAllocator.init(gpa),
.canonical_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.canonical_root_arena.deinit();
self.* = undefined;
}
pub fn cacheHighWater(self: *const TreeEditor) usize {
return self.cache_high_water;
}
/// Number of direct S-card descriptors inspected while locating touched
/// paths in the most recent `apply`.
pub fn touchedSearchSteps(self: *const TreeEditor) usize {
return self.touched_search_steps;
}
/// Read an exact file card without exposing any loaded-byte or cache view.
/// The returned card is owned by the editor until its next `lookup`,
/// `apply`, or `deinit`.
pub fn lookup(self: *TreeEditor, root: RootView, path: []const u8) Error!?artifact.FCard {
// Same argument as `apply`'s, and refused the same way: `lookup` is the
// other public entry that takes a caller-supplied `RootView`, and
// unguarded a `.tree` root here walks into `lookupTree`'s
// `shape.tree.height_max` and panics on the union tag instead of
// reporting a bad argument.
if (rootMismatchesFormat(self.format.shape, root)) return error.InvalidFormat;
self.resetLookupArena();
const arena = self.lookup_arena.allocator();
return switch (root) {
.flat => |entries| if (lookupFlat(entries, path)) |card| try cloneFCard(arena, card) else null,
.tree => |cards| self.lookupTree(cards, path, 0, &[_][]const u8{}),
};
}
pub fn apply(
self: *TreeEditor,
parent: RootView,
commands: []const TreeCommand,
) Error!BuildResult {
self.touched_search_steps = 0;
// The flat induction, checked once per commit at the only place a root
// can enter this editor.
//
// Base case: an import's first commit applies over `.{ .flat = &.{} }`,
// and so does every commit after a `deleteall`. Step: the only other
// parent is a root this editor returned, and under `.flat` both returns
// below are flat -- the empty-command clone preserves the parent's
// shape, and `buildFlat` is unconditionally flat. So a `.tree` parent
// here did not come from this editor, and the tree-only machinery it
// would wake (`OldTreeCursor.descend`, the partitioners, the checkpoint
// splice) has no k and no height to run with.
//
// A returned error rather than an `assert` because `apply` is public
// API taking a caller-supplied `RootView`: a `.tree` parent here is a
// bad ARGUMENT, not a broken internal invariant, and callers outside
// this file's induction can reach it. `Error` already carries
// `InvalidFormat` for exactly that.
if (rootMismatchesFormat(self.format.shape, parent)) return error.InvalidFormat;
self.resetLookupArena();
var arena_state = std.heap.ArenaAllocator.init(self.gpa);
errdefer arena_state.deinit();
const arena = arena_state.allocator();
const compatible_parent = self.hasCanonicalBasis(parent);
if (commands.len == 0 and compatible_parent) {
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 or !compatible_parent or overlay.entries.items.len == 0) null else overlay.entries.items[0].path;
var cursor = try OldTreeCursor.init(self, parent, arena, &known_nodes, start_path);
defer cursor.deinit();
var merged = MergedCursor.init(&cursor, &overlay, arena, self.format.shape);
if (!compatible_parent) {
if (merged.old_partitioner) |*partitioner| partitioner.deinit();
merged.old_partitioner = null;
}
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 hasCanonicalBasis(self: *const TreeEditor, root: RootView) bool {
const cards = switch (root) {
.flat => return switch (self.format.shape) {
.flat => true,
.tree => false,
},
.tree => |cards| cards,
};
const k = switch (self.format.shape) {
.flat => return false,
.tree => |tree| tree.k,
};
if (self.canonical_k != k) return false;
const known = self.canonical_root orelse return false;
if (known.len != cards.len) return false;
for (known, cards) |was, now| {
if (!std.mem.eql(u8, was.filename, now.filename) or !std.mem.eql(u8, was.hash, now.hash)) return false;
}
return true;
}
// Only this editor's completed construction supplies partition evidence;
// structural validation and the current setting do not prove parent k.
fn rememberCanonicalBasis(self: *TreeEditor, root: RootRun) Error!void {
self.canonical_root = null;
self.canonical_k = null;
_ = self.canonical_root_arena.reset(.free_all);
const cards = switch (root) {
.flat => return,
.tree => |cards| cards,
};
const owned = try cloneSCards(self.canonical_root_arena.allocator(), cards);
self.canonical_root = owned;
self.canonical_k = self.format.shape.tree.k;
}
fn lookupTree(
self: *TreeEditor,
cards: []const artifact.SCard,
path: []const u8,
depth: u8,
ancestry: []const []const u8,
) Error!?artifact.FCard {
if (!self.rootAlreadyValidated(cards, depth)) {
try self.validateTreeCards(cards, depth, ancestry);
self.rememberValidatedRoot(cards, depth);
}
return self.lookupValidatedTree(cards, path, depth, self.lookup_arena.allocator());
}
fn resetLookupArena(self: *TreeEditor) void {
self.lookup_arena.deinit();
self.lookup_arena = std.heap.ArenaAllocator.init(self.gpa);
}
fn cachedNode(self: *TreeEditor, name: []const u8) ?*CacheEntry {
return self.cache_index.get(name);
}
/// Retained allocation excluding the hash table. The map is charged once
/// by capacity, rather than once per resident node.
fn cachedBytes(name: []const u8, node: *const LoadedNode) usize {
return @sizeOf(CacheEntry) +
name.len +
node.bytes.bytes.len +
node.manifest.arena_state.queryCapacity();
}
/// Exact `HashMapUnmanaged` backing allocation for this map's capacity:
/// `align(max(header, key, value),
/// align(value, align(key, sizeof(Header) + capacity) + capacity * sizeof(Key))
/// + capacity * sizeof(Value))`.
fn cacheIndexBytes(capacity: usize) usize {
if (capacity == 0) return 0;
const Header = struct {
values: [*]*CacheEntry,
keys: [*][]const u8,
capacity: u32,
};
const header_align = @alignOf(Header);
const key_align = @alignOf([]const u8);
const value_align = @alignOf(*CacheEntry);
const max_align = @max(header_align, key_align, value_align);
const metadata_end = @sizeOf(Header) + capacity;
const keys_start = std.mem.alignForward(usize, metadata_end, key_align);
const keys_end = keys_start + capacity * @sizeOf([]const u8);
const values_start = std.mem.alignForward(usize, keys_end, value_align);
const values_end = values_start + capacity * @sizeOf(*CacheEntry);
return std.mem.alignForward(usize, values_end, max_align);
}
/// Predict the one capacity that the next distinct `put` can retain.
/// The public count and load factor recover the map's availability
/// countdown without mirroring private mutable state.
fn nextCacheIndexCapacity(self: *const TreeEditor) usize {
const capacity: usize = @intCast(self.cache_index.capacity());
const count: usize = @intCast(self.cache_index.count());
if (count < capacity * cache_index_max_load_percentage / 100) return capacity;
const required = (count + 1) * 100 / cache_index_max_load_percentage + 1;
return @max(
@as(usize, 8),
std.math.ceilPowerOfTwo(usize, required) catch unreachable,
);
}
fn destroyCacheEntry(self: *TreeEditor, entry: *CacheEntry) void {
std.debug.assert(entry.leases == 0);
self.gpa.free(entry.name);
entry.node.deinit();
self.gpa.destroy(entry);
}
/// Evict the oldest unleased decoded nodes. Leased nodes remain stable for
/// recursive traversal; if they alone prevent enough room, the caller
/// receives an uncached node instead.
fn evictFor(self: *TreeEditor, incoming: usize) bool {
while (self.cache_bytes > self.cache_bytes_max - incoming) {
var link = self.cache.first;
while (link) |current| : (link = current.next) {
const entry: *CacheEntry = @fieldParentPtr("link", current);
if (entry.leases == 0) {
self.cache.remove(current);
_ = self.cache_index.remove(entry.name);
self.cache_bytes -= cachedBytes(entry.name, &entry.node);
self.destroyCacheEntry(entry);
break;
}
}
if (link == null) return false;
}
return true;
}
fn decodeNode(self: *TreeEditor, name: []const u8) Error!LoadedNode {
var bytes = try self.store.load_fn(self.store.ctx, self.gpa, name);
errdefer bytes.deinit();
var actual_name_buf: [64]u8 = undefined;
if (!std.mem.eql(u8, name, artifact.artifactName(self.format.hash_algo, bytes.bytes, &actual_name_buf))) {
return error.MalformedNode;
}
var manifest = artifact.parse(self.gpa, bytes.bytes) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.MalformedNode,
};
errdefer manifest.deinit();
if (manifest.kind != .submanifest) return error.WrongNodeType;
if ((manifest.f.len == 0) == (manifest.s.len == 0)) return error.WrongNodeType;
if (manifest.f.len != 0) {
var previous: ?[]const u8 = null;
for (manifest.f) |entry| {
if (entry.hash == null) return error.MalformedNode;
if (previous) |key| if (artifact.compareBytes(key, entry.filename) != .lt) return error.MalformedNode;
previous = entry.filename;
}
} else {
var previous: ?[]const u8 = null;
for (manifest.s) |card| {
if (previous) |key| if (artifact.compareBytes(key, card.filename) != .lt) return error.MalformedNode;
previous = card.filename;
}
}
return .{ .bytes = bytes, .manifest = manifest };
}
fn loadNode(self: *TreeEditor, name: []const u8) Error!NodeLease {
const algo = artifact.nameAlgo(name.len) orelse return error.MalformedNode;
if (algo != self.format.hash_algo) return error.MalformedNode;
if (self.cachedNode(name)) |entry| {
entry.leases += 1;
return .{ .cached = entry };
}
var node = try self.decodeNode(name);
const bytes = cachedBytes(name, &node);
const index_capacity_before: usize = @intCast(self.cache_index.capacity());
const index_bytes_before = cacheIndexBytes(index_capacity_before);
const index_bytes_after = cacheIndexBytes(self.nextCacheIndexCapacity());
const incoming = bytes + index_bytes_after - index_bytes_before;
if (self.cache_bytes_max == 0 or incoming > self.cache_bytes_max or !self.evictFor(incoming)) {
return .{ .owned = node };
}
const entry = self.gpa.create(CacheEntry) catch |err| {
node.deinit();
return err;
};
const cached_name = self.gpa.dupe(u8, name) catch |err| {
self.gpa.destroy(entry);
node.deinit();
return err;
};
entry.* = .{ .name = cached_name, .node = node };
self.cache_index.put(self.gpa, entry.name, entry) catch |err| {
self.destroyCacheEntry(entry);
return err;
};
const index_capacity_after: usize = @intCast(self.cache_index.capacity());
self.cache.append(&entry.link);
entry.leases = 1;
self.cache_bytes += bytes + cacheIndexBytes(index_capacity_after) - index_bytes_before;
self.cache_high_water = @max(self.cache_high_water, self.cache_bytes);
return .{ .cached = entry };
}
/// Apply-time probing only follows the branch selected by `path`. Public
/// `lookup` retains complete-tree validation; an edit must not preflight
/// unrelated file cards before it can begin rebuilding.
fn lookupTouchedOwned(self: *TreeEditor, root: RootView, path: []const u8, arena: std.mem.Allocator) Error!?artifact.FCard {
return switch (root) {
.flat => |entries| if (lookupFlat(entries, path)) |card| try cloneFCard(arena, card) else null,
.tree => |cards| self.lookupTouchedTree(cards, path, 0, &[_][]const u8{}, arena),
};
}
fn lookupTouchedTree(
self: *TreeEditor,
cards: []const artifact.SCard,
path: []const u8,
depth: u8,
ancestry: []const []const u8,
arena: std.mem.Allocator,
) Error!?artifact.FCard {
if (cards.len == 0 or artifact.compareBytes(cards[0].filename, path) == .gt) return null;
// This is the old scan's last descriptor with first key <= `path`.
// Route selection must stay logarithmic even when the direct root is
// wider than a canonical local group.
var low: usize = 0;
var high = cards.len;
while (low < high) {
const mid = low + (high - low) / 2;
self.touched_search_steps += 1;
if (artifact.compareBytes(cards[mid].filename, path) != .gt) low = mid + 1 else high = mid;
}
const index = low - 1;
const child = cards[index];
if (index != 0) {
const predecessor = cards[index - 1];
if (artifact.compareBytes(predecessor.filename, child.filename) != .lt) return error.MalformedNode;
try self.validateRightmostRange(
predecessor.hash,
predecessor.filename,
child.filename,
depth,
ancestry,
);
}
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, child.hash)) return error.Cycle;
var node = try self.loadNode(child.hash);
defer node.deinit();
const manifest = node.manifest();
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, child.filename, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
return null;
}
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = child.hash;
return self.lookupTouchedTree(
manifest.s,
path,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
arena,
);
}
/// Validate only the predecessor range that can reach `upper`. Decoded
/// nodes still validate each local descriptor list, while following only
/// the rightmost descendant prevents an apply from walking unrelated
/// predecessor leaves.
fn validateRightmostRange(
self: *TreeEditor,
name: []const u8,
expected_first: []const u8,
upper: []const u8,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.shape.tree.height_max) return error.HeightExceeded;
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;
var node = try self.loadNode(name);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, upper) != .lt) return error.MalformedNode;
return;
}
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = name;
const rightmost = manifest.s[manifest.s.len - 1];
return self.validateRightmostRange(
rightmost.hash,
rightmost.filename,
upper,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
);
}
/// True when `cards` is byte-identical to the root already walked against
/// the current store. Identical S cards name identical children, and a child
/// name binds its bytes, so the two roots are the same tree all the way down.
///
/// Only a whole-tree walk from the top is memoized: `depth` must be 0, which
/// is also the only way `lookupTree` is reached. A non-zero depth would carry
/// an ancestry and a shortened height budget that this comparison does not
/// model, so it re-validates rather than guessing.
fn rootAlreadyValidated(self: *const TreeEditor, cards: []const artifact.SCard, depth: u8) bool {
if (depth != 0) return false;
const previous = self.validated_root orelse return false;
if (previous.len != cards.len) return false;
for (previous, cards) |was, now| {
if (!std.mem.eql(u8, was.filename, now.filename)) return false;
if (!std.mem.eql(u8, was.hash, now.hash)) return false;
}
return true;
}
/// Record a root that just validated. A failed copy is not an error: the
/// memo is an optimization, and losing it costs the next lookup a re-walk
/// rather than a wrong answer.
fn rememberValidatedRoot(self: *TreeEditor, cards: []const artifact.SCard, depth: u8) void {
if (depth != 0) return;
self.invalidateValidatedRoot();
self.validated_root = cloneSCards(self.validated_root_arena.allocator(), cards) catch {
self.validated_root = null;
return;
};
}
/// Validate the complete reachable range before returning any lookup
/// result. A selected child is not enough: a malformed sibling can expand
/// into the selected child's range and make the S run ambiguous.
fn validateTreeCards(
self: *TreeEditor,
cards: []const artifact.SCard,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.shape.tree.height_max or cards.len == 0) return error.MalformedNode;
var previous: ?[]const u8 = null;
for (cards, 0..) |child, index| {
if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
previous = child.filename;
const upper = if (index + 1 < cards.len) cards[index + 1].filename else null;
try self.validateTreeNode(child.hash, child.filename, upper, depth, ancestry);
}
}
/// `upper` is the next sibling's advertised first key. Every descendant
/// must be strictly below it, which makes sibling ranges disjoint.
fn validateTreeNode(
self: *TreeEditor,
name: []const u8,
expected_first: []const u8,
upper: ?[]const u8,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.shape.tree.height_max) return error.HeightExceeded;
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;
var node = try self.loadNode(name);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (upper) |next| {
if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, next) != .lt) return error.MalformedNode;
}
return;
}
if (manifest.s.len == 0) return error.WrongNodeType;
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = name;
var previous: ?[]const u8 = null;
for (manifest.s, 0..) |child, index| {
if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
previous = child.filename;
const child_upper = if (index + 1 < manifest.s.len) manifest.s[index + 1].filename else upper;
try self.validateTreeNode(
child.hash,
child.filename,
child_upper,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
);
}
}
fn lookupValidatedTree(
self: *TreeEditor,
cards: []const artifact.SCard,
path: []const u8,
depth: u8,
arena: std.mem.Allocator,
) Error!?artifact.FCard {
const child = childForPath(cards, path) orelse return null;
var node = try self.loadNode(child.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len != 0) {
if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
return null;
}
if (depth + 1 >= self.format.shape.tree.height_max) return error.HeightExceeded;
return self.lookupValidatedTree(manifest.s, path, depth + 1, arena);
}
};
const StreamEntry = struct {
card: artifact.FCard,
/// The exact old leaf containing `card`, if it survived the overlay.
origin: ?[]const u8,
};
const Descriptor = struct {
card: artifact.SCard,
/// The old node name is deliberately propagated upward. A canonical
/// repaired parent can therefore be reused without retaining its children.
origin: ?[]const u8,
};
const OverlayEntry = struct {
path: []const u8,
original: ?artifact.FCard,
value: ?artifact.FCard,
};
const Overlay = struct {
entries: std.ArrayList(OverlayEntry) = .empty,
clear: bool = false,
fn lowerBound(self: *const Overlay, path: []const u8) usize {
var low: usize = 0;
var high = self.entries.items.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (artifact.compareBytes(self.entries.items[mid].path, path) == .lt) low = mid + 1 else high = mid;
}
return low;
}
fn clone(self: *const Overlay, arena: std.mem.Allocator) Error!Overlay {
var result: Overlay = .{ .clear = self.clear };
for (self.entries.items) |entry| {
try result.entries.append(arena, .{
.path = try arena.dupe(u8, entry.path),
.original = if (entry.original) |card| try cloneFCard(arena, card) else null,
.value = if (entry.value) |card| try cloneFCard(arena, card) else null,
});
}
return result;
}
fn get(self: *const Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, path: []const u8) Error!?artifact.FCard {
const index = self.lowerBound(path);
if (index < self.entries.items.len and std.mem.eql(u8, self.entries.items[index].path, path)) {
return self.entries.items[index].value;
}
if (self.clear) return null;
return editor_.lookupTouchedOwned(parent, path, arena);
}
fn put(self: *Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, path: []const u8, value: ?artifact.FCard) Error!void {
const index = self.lowerBound(path);
const owned_value = if (value) |card| try cloneFCard(arena, card) else null;
if (index < self.entries.items.len and std.mem.eql(u8, self.entries.items[index].path, path)) {
self.entries.items[index].value = owned_value;
return;
}
const original = if (self.clear) null else try editor_.lookupTouchedOwned(parent, path, arena);
const owned_path = try arena.dupe(u8, path);
try self.entries.insert(arena, index, .{
.path = owned_path,
.original = original,
.value = owned_value,
});
}
fn netChangedPaths(self: *const Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator) Error!usize {
var known_nodes: KnownNodes = .{};
var old = try OldTreeCursor.init(editor_, parent, arena, &known_nodes, null);
defer old.deinit();
var changed: usize = 0;
var overlay_index: usize = 0;
while (try old.next()) |old_entry| {
while (overlay_index < self.entries.items.len and
artifact.compareBytes(self.entries.items[overlay_index].path, old_entry.card.filename) == .lt)
{
if (self.entries.items[overlay_index].value != null) changed += 1;
overlay_index += 1;
}
if (overlay_index < self.entries.items.len and
std.mem.eql(u8, self.entries.items[overlay_index].path, old_entry.card.filename))
{
if (self.entries.items[overlay_index].value) |card| {
if (!sameFCard(card, old_entry.card)) changed += 1;
} else {
changed += 1;
}
overlay_index += 1;
} else if (self.clear) {
changed += 1;
}
}
while (overlay_index < self.entries.items.len) : (overlay_index += 1) {
if (self.entries.items[overlay_index].value != null) changed += 1;
}
return changed;
}
fn touchedChangedPaths(self: *const Overlay) usize {
var changed: usize = 0;
for (self.entries.items) |entry| {
if (!sameOptionalFCard(entry.original, entry.value)) changed += 1;
}
return changed;
}
fn apply(self: *Overlay, editor_: *TreeEditor, parent: RootView, arena: std.mem.Allocator, commands: []const TreeCommand) Error!usize {
var staged = try self.clone(arena);
for (commands) |command| switch (command) {
.upsert => |card| {
if (card.hash == null) return error.InvalidCommand;
try staged.put(editor_, parent, arena, card.filename, card);
},
.delete => |path| {
if ((try staged.get(editor_, parent, arena, path)) == null) return error.MissingPath;
try staged.put(editor_, parent, arena, path, null);
},
.rename => |move| {
const source = (try staged.get(editor_, parent, arena, move.old)) orelse return error.MissingPath;
if ((try staged.get(editor_, parent, arena, move.new)) != null) return error.DuplicatePath;
var renamed = source;
renamed.filename = move.new;
try staged.put(editor_, parent, arena, move.new, renamed);
try staged.put(editor_, parent, arena, move.old, null);
},
.copy => |copy| {
const source = (try staged.get(editor_, parent, arena, copy.old)) orelse return error.MissingPath;
if ((try staged.get(editor_, parent, arena, copy.new)) != null) return error.DuplicatePath;
var copied = source;
copied.filename = copy.new;
try staged.put(editor_, parent, arena, copy.new, copied);
},
.delete_all => {
staged.clear = true;
staged.entries.clearRetainingCapacity();
},
};
const changed = if (staged.clear) try staged.netChangedPaths(editor_, parent, arena) else staged.touchedChangedPaths();
self.* = staged;
return changed;
}
};
fn sameFCard(left: artifact.FCard, right: artifact.FCard) bool {
return left.mode == right.mode and
std.mem.eql(u8, left.filename, right.filename) and
sameOptionalBytes(left.hash, right.hash) and
sameOptionalBytes(left.perm, right.perm) and
sameOptionalBytes(left.old_name, right.old_name);
}
fn sameOptionalFCard(left: ?artifact.FCard, right: ?artifact.FCard) bool {
if (left) |left_card| {
const right_card = right orelse return false;
return sameFCard(left_card, right_card);
}
return right == null;
}
fn sameOptionalBytes(left: ?[]const u8, right: ?[]const u8) bool {
if (left) |left_bytes| {
const right_bytes = right orelse return false;
return std.mem.eql(u8, left_bytes, right_bytes);
}
return right == null;
}
const NativePrefixDescriptor = struct {
descriptor: Descriptor,
/// Tree height of `descriptor`: leaves are height one and an S card's
/// height is one greater than its children.
height: usize,
};
const SuffixFrontier = enum {
/// A native descriptor already at the current construction height. It is
/// a partial continuation, not a checkpoint-proof canonical group.
descriptor,
/// A complete old parent group was exposed; its raw parent remains at the
/// front of the native suffix until the caller commits or reuses it.
group,
end,
};
/// Per-apply immutable node names. The map owns arena-backed keys and avoids
/// re-scanning every previously visited node for each emitted candidate.
const KnownNodes = struct {
index: std.StringHashMapUnmanaged(void) = .empty,
fn contains(self: *const KnownNodes, name: []const u8) bool {
return self.index.contains(name);
}
fn remember(self: *KnownNodes, arena: std.mem.Allocator, name: []const u8) std.mem.Allocator.Error!void {
if (self.index.contains(name)) return;
const owned = try arena.dupe(u8, name);
try self.index.put(arena, owned, {});
}
};
/// A decoded node on the active left-to-right path. `index` is the next child
/// not yet committed to the cursor's current descriptor level.
const CursorFrame = struct {
name: []const u8,
node: NodeLease,
index: usize = 0,
};
/// Checkpoint traversal has exactly two terminal states. A continuation owns a
/// live fixed-depth frontier whose next canonical group is still at the same
/// descriptor height. A root handoff owns the measured height of the direct
/// root just exhausted; it is not EOF convergence.
const CheckpointState = union(enum) {
continuation: struct {
group_depth: usize,
},
root: struct {
height: usize,
},
};
/// In-order walk over old F cards. At most one decoded node per tree height is
/// live; every returned card is consumed before advancing can evict its frame.
const OldTreeCursor = struct {
editor_: *TreeEditor,
root: RootView,
arena: std.mem.Allocator,
known_nodes: *KnownNodes,
flat_index: usize = 0,
root_index: usize = 0,
previous_root: ?[]const u8 = null,
previous_card: ?[]const u8 = null,
previous_card_buf: std.ArrayList(u8) = .empty,
saved_previous_card_buf: std.ArrayList(u8) = .empty,
frames: std.ArrayList(CursorFrame) = .empty,
/// Between checkpoint steps this is either a same-height continuation or
/// the explicit direct-root handoff. There is no inferred EOF state.
checkpoint: ?CheckpointState = null,
/// Untouched direct siblings strictly before the localized scan. Each
/// descriptor remains at its old tree height; no old prefix subtree is
/// expanded into leaves or F cards.
prefix: std.ArrayList(NativePrefixDescriptor) = .empty,
/// Untouched direct siblings after the checkpoint. A stack exposes the
/// leftmost native descriptor without flattening a higher subtree; each
/// descriptor remains at its original tree height until its parent group
/// is the proven splice frontier.
suffix: std.ArrayList(NativePrefixDescriptor) = .empty,
fn init(
editor_: *TreeEditor,
root: RootView,
arena: std.mem.Allocator,
known_nodes: *KnownNodes,
start_path: ?[]const u8,
) Error!OldTreeCursor {
var cursor: OldTreeCursor = .{
.editor_ = editor_,
.root = root,
.arena = arena,
.known_nodes = known_nodes,
};
errdefer cursor.deinit();
if (start_path) |path| try cursor.seek(path);
return cursor;
}
fn deinit(self: *OldTreeCursor) void {
for (self.frames.items) |*frame| frame.node.deinit();
self.frames.deinit(self.editor_.gpa);
self.previous_card_buf.deinit(self.editor_.gpa);
self.saved_previous_card_buf.deinit(self.editor_.gpa);
self.* = undefined;
}
fn remember(self: *OldTreeCursor, name: []const u8) Error!void {
try self.known_nodes.remember(self.arena, name);
}
fn descend(self: *OldTreeCursor, name: []const u8, expected_first: ?[]const u8) Error!void {
if (self.frames.items.len >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
for (self.frames.items) |frame| if (std.mem.eql(u8, frame.name, name)) return error.Cycle;
var node = try self.editor_.loadNode(name);
errdefer node.deinit();
const manifest = node.manifest();
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (expected_first) |key| if (!std.mem.eql(u8, key, actual_first)) return error.MalformedNode;
try self.remember(name);
try self.frames.append(self.editor_.gpa, .{ .name = name, .node = node });
}
fn discardLastFrame(self: *OldTreeCursor) void {
const finished = self.frames.pop().?;
var owned = finished;
owned.node.deinit();
}
fn directRootHeight(self: *OldTreeCursor, frame: *const CursorFrame) Error!usize {
var height: usize = 1;
var manifest = frame.node.manifest();
var owned: ?NodeLease = null;
errdefer if (owned) |*node| node.deinit();
while (manifest.f.len == 0) {
if (manifest.s.len == 0) return error.WrongNodeType;
if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
const loaded = try self.editor_.loadNode(manifest.s[0].hash);
if (owned) |*node| node.deinit();
owned = loaded;
height += 1;
manifest = owned.?.manifest();
}
if (owned) |*node| node.deinit();
return height;
}
fn recordRootCheckpoint(self: *OldTreeCursor) Error!void {
if (self.frames.items.len != 1) return error.MalformedNode;
self.checkpoint = .{ .root = .{
.height = try self.directRootHeight(&self.frames.items[0]),
} };
}
fn finishCheckpointFrame(self: *OldTreeCursor) Error!void {
if (self.frames.items.len == 0) return error.MalformedNode;
if (self.frames.items.len == 1) try self.recordRootCheckpoint();
self.discardLastFrame();
}
fn setCheckpointContinuation(self: *OldTreeCursor, group_depth: usize) void {
self.checkpoint = .{ .continuation = .{
.group_depth = group_depth,
} };
}
fn checkpointDepth(self: *const OldTreeCursor) Error!usize {
return switch (self.checkpoint orelse return error.MalformedNode) {
.continuation => |continuation| continuation.group_depth,
.root => error.MalformedNode,
};
}
fn takeRootCheckpoint(self: *OldTreeCursor) Error!usize {
const state = self.checkpoint orelse return error.MalformedNode;
self.checkpoint = null;
return switch (state) {
.root => |root| root.height,
.continuation => error.MalformedNode,
};
}
fn descendRightmostLeaf(self: *OldTreeCursor) Error!void {
while (true) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) return;
if (manifest.s.len == 0) return error.WrongNodeType;
frame.index = manifest.s.len;
const child = manifest.s[manifest.s.len - 1];
try self.descend(child.hash, child.filename);
}
}
/// Reopen the immediately preceding leaf when one exists. A late deletion
/// may shrink the final group that crosses this leaf boundary, so the
/// predecessor is mutable input rather than a frozen prefix descriptor.
fn rewindToPredecessorLeaf(self: *OldTreeCursor) Error!void {
var has_predecessor = self.root_index > 1;
if (!has_predecessor and self.frames.items.len > 1) {
for (self.frames.items[0 .. self.frames.items.len - 1]) |frame| {
if (frame.index > 1) {
has_predecessor = true;
break;
}
}
}
if (!has_predecessor) return;
self.discardLastFrame();
while (self.frames.items.len != 0) {
const parent_index = self.frames.items.len - 1;
const parent = &self.frames.items[parent_index];
std.debug.assert(parent.index != 0);
const selected_index = parent.index - 1;
if (selected_index != 0) {
parent.index = selected_index;
const manifest = parent.node.manifest();
const child = manifest.s[selected_index - 1];
try self.descend(child.hash, child.filename);
return self.descendRightmostLeaf();
}
self.discardLastFrame();
}
std.debug.assert(self.root_index > 1);
const roots = switch (self.root) {
.flat => unreachable,
.tree => |cards| cards,
};
const selected_index = self.root_index - 1;
self.root_index = selected_index;
const child = roots[selected_index - 1];
try self.descend(child.hash, child.filename);
return self.descendRightmostLeaf();
}
fn setPreviousCard(self: *OldTreeCursor, filename: []const u8) std.mem.Allocator.Error!void {
self.previous_card_buf.clearRetainingCapacity();
try self.previous_card_buf.appendSlice(self.editor_.gpa, filename);
self.previous_card = self.previous_card_buf.items;
}
fn savePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
self.saved_previous_card_buf.clearRetainingCapacity();
if (self.previous_card) |previous| try self.saved_previous_card_buf.appendSlice(self.editor_.gpa, previous);
}
fn restorePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
if (self.saved_previous_card_buf.items.len == 0) {
self.previous_card = null;
return;
}
try self.setPreviousCard(self.saved_previous_card_buf.items);
}
fn returned(self: *OldTreeCursor, card: artifact.FCard, origin: ?[]const u8) Error!StreamEntry {
if (self.previous_card) |previous| if (artifact.compareBytes(previous, card.filename) != .lt) return error.MalformedNode;
try self.setPreviousCard(card.filename);
return .{ .card = card, .origin = origin };
}
fn atLeafEnd(self: *const OldTreeCursor) bool {
if (self.frames.items.len == 0) return false;
const frame = self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
return manifest.f.len != 0 and frame.index == manifest.f.len;
}
fn atRootEnd(self: *const OldTreeCursor) bool {
if (self.frames.items.len != 0) return false;
return switch (self.root) {
.flat => |entries| self.flat_index == entries.len,
.tree => |cards| self.root_index == cards.len,
};
}
fn appendLeaf(self: *OldTreeCursor, name: []const u8, manifest: *const artifact.Manifest, out: *std.ArrayList(Descriptor)) Error!void {
std.debug.assert(manifest.f.len != 0);
const first = manifest.f[0].filename;
if (self.previous_card) |previous| if (artifact.compareBytes(previous, first) != .lt) return error.MalformedNode;
try self.setPreviousCard(manifest.f[manifest.f.len - 1].filename);
const hash = try self.arena.dupe(u8, name);
try out.append(self.arena, .{
.card = .{ .filename = try self.arena.dupe(u8, first), .hash = hash },
.origin = hash,
});
}
fn appendDescriptor(self: *OldTreeCursor, card: artifact.SCard, out: *std.ArrayList(Descriptor)) Error!void {
const filename = try self.arena.dupe(u8, card.filename);
const hash = try self.arena.dupe(u8, card.hash);
try out.append(self.arena, .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
});
}
fn appendNativePrefix(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!void {
const filename = try self.arena.dupe(u8, card.filename);
const hash = try self.arena.dupe(u8, card.hash);
try self.prefix.append(self.arena, .{
.descriptor = .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
},
.height = height,
});
try self.remember(hash);
}
fn nativeDescriptor(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!NativePrefixDescriptor {
const filename = try self.arena.dupe(u8, card.filename);
const hash = try self.arena.dupe(u8, card.hash);
return .{
.descriptor = .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
},
.height = height,
};
}
fn appendNativeSuffix(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!void {
try self.suffix.append(self.arena, try self.nativeDescriptor(card, height));
}
/// Transfer exactly one remaining direct root card into the suffix stack.
/// Descended siblings are stacked in reverse order, so a pop always
/// advances left-to-right without moving the unvisited root slice.
fn fillSuffixFromRoot(self: *OldTreeCursor, root_height: usize) Error!bool {
if (self.suffix.items.len != 0) return true;
const roots = switch (self.root) {
.flat => return false,
.tree => |cards| cards,
};
if (self.root_index == roots.len) return false;
const child = roots[self.root_index];
if (self.previous_root) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
self.previous_root = child.filename;
self.root_index += 1;
try self.appendNativeSuffix(child, root_height);
return true;
}
/// Expose the next native suffix frontier at `target_height`. A complete
/// group remains represented by its raw parent on the stack until the
/// caller has proved a checkpoint at the following group boundary.
fn appendRootSuffixFrontierAtHeight(
self: *OldTreeCursor,
root_height: usize,
target_height: usize,
out: *std.ArrayList(Descriptor),
) Error!SuffixFrontier {
if (target_height == 0 or target_height > root_height) return error.MalformedNode;
while (true) {
if (!try self.fillSuffixFromRoot(root_height)) return .end;
const current = &self.suffix.items[self.suffix.items.len - 1];
if (current.height < target_height) return error.MalformedNode;
if (current.height == target_height) {
const descriptor = self.suffix.pop().?;
try out.append(self.arena, descriptor.descriptor);
return .descriptor;
}
if (current.height == target_height + 1) {
var node = try self.editor_.loadNode(current.descriptor.card.hash);
defer node.deinit();
try self.remember(current.descriptor.card.hash);
const manifest = node.manifest();
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
for (manifest.s) |child| {
try self.appendDescriptor(child, out);
try self.remember(child.hash);
}
return .group;
}
const parent = self.suffix.pop().?;
var node = try self.editor_.loadNode(parent.descriptor.card.hash);
defer node.deinit();
try self.remember(parent.descriptor.card.hash);
const manifest = node.manifest();
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
const child_height = parent.height - 1;
var index = manifest.s.len;
while (index != 0) {
index -= 1;
try self.appendNativeSuffix(manifest.s[index], child_height);
}
}
}
fn commitRootSuffixFrontier(self: *OldTreeCursor, target_height: usize) Error!void {
if (self.suffix.items.len == 0) return error.MalformedNode;
if (self.suffix.items[self.suffix.items.len - 1].height != target_height + 1) return error.MalformedNode;
_ = self.suffix.pop();
}
fn appendRootSuffixAtRootHeight(
self: *OldTreeCursor,
root_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
while (true) {
if (!try self.fillSuffixFromRoot(root_height)) return;
if (self.suffix.items[self.suffix.items.len - 1].height != root_height) return error.MalformedNode;
const descriptor = self.suffix.pop().?;
try out.append(self.arena, descriptor.descriptor);
}
}
/// Splice every retained native descriptor of exactly `height` into `out`.
/// A descriptor belongs to exactly one output level, so the spliced
/// entries are consumed here: a later level that re-asks for the same
/// height would otherwise re-emit a node the current level already owns.
/// The single fallible step precedes every mutation, so a failed splice
/// leaves the retained prefix untouched.
fn appendPrefixAtHeight(self: *OldTreeCursor, height: usize, out: *std.ArrayList(Descriptor)) Error!usize {
var matches: usize = 0;
for (self.prefix.items) |entry| {
if (entry.height == height) matches += 1;
}
if (matches == 0) return 0;
try out.ensureUnusedCapacity(self.arena, matches);
var kept: usize = 0;
for (self.prefix.items) |entry| {
if (entry.height == height) {
out.appendAssumeCapacity(entry.descriptor);
} else {
self.prefix.items[kept] = entry;
kept += 1;
}
}
self.prefix.items.len = kept;
return matches;
}
fn hasPrefixAtHeight(self: *const OldTreeCursor, height: usize) bool {
for (self.prefix.items) |entry| if (entry.height == height) return true;
return false;
}
/// A native descriptor at the next level is the predecessor group for the
/// localized frontier. Reopen it instead of carrying a shallower
/// descriptor across the height boundary.
fn takePrefixAtHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
var index = self.prefix.items.len;
while (index != 0) {
index -= 1;
if (self.prefix.items[index].height == height) return self.prefix.orderedRemove(index);
}
return null;
}
/// Remove the closest retained ancestor strictly above `height`. The
/// rightmost such descriptor is the only old subtree adjacent to the
/// localized frontier.
fn takePrefixAboveHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
var candidate_index: ?usize = null;
var candidate_height: usize = std.math.maxInt(usize);
for (self.prefix.items, 0..) |entry, index| {
if (entry.height <= height) continue;
if (entry.height < candidate_height or entry.height == candidate_height) {
candidate_index = index;
candidate_height = entry.height;
}
}
if (candidate_index) |index| return self.prefix.orderedRemove(index);
return null;
}
/// Rewind a retained ancestor to the current construction height without
/// flattening it. Every descent retains the older direct siblings at their
/// own formation height, then follows only the rightmost child because it
/// is adjacent to the edited suffix.
fn reopenRightmostPrefixAtHeight(
self: *OldTreeCursor,
group: NativePrefixDescriptor,
child_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
std.debug.assert(group.height > child_height + 1);
var current = group;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
while (current.height > child_height + 1) {
var node = try self.editor_.loadNode(current.descriptor.card.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
const next_height = current.height - 1;
for (manifest.s[0 .. manifest.s.len - 1]) |child| {
try self.appendNativePrefix(child, next_height);
}
const rightmost = manifest.s[manifest.s.len - 1];
const filename = try self.arena.dupe(u8, rightmost.filename);
const hash = try self.arena.dupe(u8, rightmost.hash);
try self.remember(hash);
current = .{
.descriptor = .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
},
.height = next_height,
};
}
try self.reopenPrefixGroup(current, child_height, out);
}
/// Expand exactly one predecessor group into its direct descriptor stream.
/// Earlier descriptors at that height remain native prefix candidates.
fn reopenPrefixGroup(
self: *OldTreeCursor,
group: NativePrefixDescriptor,
child_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
std.debug.assert(group.height == child_height + 1);
var node = try self.editor_.loadNode(group.descriptor.card.hash);
defer node.deinit();
const manifest = node.manifest();
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
for (manifest.s) |child| {
try self.appendDescriptor(child, out);
try self.remember(child.hash);
}
}
/// Descend to the changed leaf, then reopen its predecessor. Earlier
/// siblings remain direct descriptors at their original heights, so the
/// cursor never walks their leaves or F cards.
fn seek(self: *OldTreeCursor, path: []const u8) Error!void {
switch (self.root) {
.flat => {
self.flat_index = 0;
return;
},
.tree => |roots| {
if (roots.len == 0) return error.MalformedNode;
const root_index = childIndexForPath(roots, path);
self.root_index = root_index + 1;
try self.descend(roots[root_index].hash, roots[root_index].filename);
while (true) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) break;
if (manifest.s.len == 0) return error.WrongNodeType;
const child_index = childIndexForPath(manifest.s, path);
frame.index = child_index + 1;
try self.descend(manifest.s[child_index].hash, manifest.s[child_index].filename);
}
try self.rewindToPredecessorLeaf();
const leaf_height = self.frames.items.len;
for (roots[0 .. self.root_index - 1]) |child| {
try self.appendNativePrefix(child, leaf_height);
}
for (self.frames.items[0 .. self.frames.items.len - 1], 0..) |frame, depth| {
const manifest = frame.node.manifest();
const child_index = frame.index - 1;
const child_height = leaf_height - depth - 1;
for (manifest.s[0..child_index]) |child| {
try self.appendNativePrefix(child, child_height);
}
}
},
}
}
/// The checkpoint look-ahead has already entered its next leaf. Complete
/// that leaf, then expose the remainder of its immediate parent group.
/// The resulting continuation state retains its fixed group depth: frames
/// below it are the next-level frontier, while every retired frame has
/// contributed all direct children to this continuation or the rebuilt
/// descriptor stream.
fn appendCheckpointLevel(
self: *OldTreeCursor,
include_next_leaf: bool,
out: *std.ArrayList(Descriptor),
) Error!bool {
if (self.frames.items.len > self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
self.checkpoint = null;
if (include_next_leaf) {
if (self.frames.items.len == 0) return error.MalformedNode;
const leaf = self.frames.items[self.frames.items.len - 1];
const manifest = leaf.node.manifest();
if (manifest.f.len == 0) return error.WrongNodeType;
if (manifest.f.len > max_members) return error.MalformedNode;
try self.appendLeaf(leaf.name, manifest, out);
try self.finishCheckpointFrame();
}
if (self.frames.items.len == 0) return false;
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
while (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.appendDescriptor(child, out);
}
try self.finishCheckpointFrame();
if (self.frames.items.len == 0) return false;
self.setCheckpointContinuation(self.frames.items.len);
return true;
}
/// Continue exactly one semantic descriptor height. A direct-root
/// completion ends this state immediately; its siblings remain native for
/// root handoff rather than becoming a provisional same-height suffix.
fn appendNextCheckpointGroup(
self: *OldTreeCursor,
group_depth: usize,
out: *std.ArrayList(Descriptor),
) Error!bool {
if (try self.checkpointDepth() != group_depth) return error.MalformedNode;
if (self.frames.items.len > self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.shape.tree.k);
const roots = switch (self.root) {
.flat => return false,
.tree => |cards| cards,
};
while (true) {
if (self.frames.items.len == group_depth + 1) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
while (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.appendDescriptor(child, out);
}
if (group_depth == 0) {
try self.finishCheckpointFrame();
return false;
}
self.discardLastFrame();
self.setCheckpointContinuation(group_depth);
if (self.frames.items.len != group_depth) return error.MalformedNode;
return true;
}
if (self.frames.items.len > group_depth + 1) return error.MalformedNode;
if (self.frames.items.len != 0) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
if (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.descend(child.hash, child.filename);
continue;
}
if (self.frames.items.len == 1) try self.recordRootCheckpoint();
self.discardLastFrame();
continue;
}
if (self.root_index == roots.len) return false;
self.checkpoint = null;
const child = roots[self.root_index];
if (self.previous_root) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
self.previous_root = child.filename;
self.root_index += 1;
try self.descend(child.hash, child.filename);
}
}
/// The first key of the next sibling leaf, read straight off the
/// parent frame's S-entry: no load, no cursor motion. Null when the
/// just-finished leaf was its parent's last child (the seam streams and
/// the next gap check resumes beyond it).
fn peekNextSiblingFirst(self: *const OldTreeCursor) ?[]const u8 {
if (self.frames.items.len >= 2) {
const parent = &self.frames.items[self.frames.items.len - 2];
const siblings = parent.node.manifest().s;
if (parent.index >= siblings.len) return null;
return siblings[parent.index].filename;
}
// A two-level tree's leaves hang directly off the ROOT, which is the
// RootView rather than a frame — the k=7 production shape, where a
// frames-only peek would blind adoption entirely.
if (self.frames.items.len != 1) return null;
switch (self.root) {
.flat => return null,
.tree => |roots| {
if (self.root_index >= roots.len) return null;
return roots[self.root_index].filename;
},
}
}
/// Root-level twin of `adoptLeavesBelow` for two-level trees:
/// identical strict-less eligibility and withheld-warm-up rules, with the
/// ROOT array as the sibling run and `previous_root` as the order fence
/// (`next`'s own descent check reads it, so adoption must keep it moving).
fn adoptRootLeavesBelow(self: *OldTreeCursor, roots: []const artifact.SCard, bound: []const u8, out: *std.ArrayList(Descriptor)) Error!?Adoption {
if (self.root_index >= roots.len) return null;
var stop = self.root_index;
while (stop + 1 < roots.len and
artifact.compareBytes(roots[stop + 1].filename, bound) == .lt) stop += 1;
if (stop <= self.root_index) return null;
const adopt_until = stop - 1;
if (adopt_until < self.root_index) return null;
var adopted: usize = 0;
while (self.root_index <= adopt_until) : (self.root_index += 1) {
const child = roots[self.root_index];
if (self.previous_root) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
if (self.previous_card) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
try self.appendDescriptor(child, out);
try self.remember(child.hash);
self.previous_root = child.filename;
try self.setPreviousCard(child.filename);
adopted += 1;
}
const last = roots[adopt_until];
var node = try self.editor_.loadNode(last.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0) return error.WrongNodeType;
return .{ .adopted = adopted, .last_members = manifest.f.len };
}
/// Interior-gap fast-forward. From a just-exhausted leaf (the
/// caller checked `atLeafEnd`), adopt whole sibling leaves as descriptors
/// straight from the parent frame's S-entries — loading nothing — while
/// each candidate's entire span provably sorts below `bound` (its
/// successor's first key is <= `bound`, and F keys are strictly below
/// their successor's first). Always leaves the LAST eligible sibling
/// unadopted: that leaf streams normally as the partitioner warm-up,
/// exactly `seek`'s predecessor-leaf idiom. Adoption never crosses the
/// parent frame in this pass — the parent seam streams, and the next gap
/// check resumes adoption beyond it — so a failure to adopt is only ever
/// the cost of today's behavior.
const Adoption = struct { adopted: usize, last_members: usize };
fn adoptLeavesBelow(self: *OldTreeCursor, bound: []const u8, out: *std.ArrayList(Descriptor)) Error!?Adoption {
// The sibling run lives either in the parent FRAME (deep trees) or in
// the ROOT array (two-level trees, the production k=7 shape).
var root_siblings: []const artifact.SCard = &.{};
var root_level = false;
if (self.frames.items.len >= 2) {} else if (self.frames.items.len == 1) {
switch (self.root) {
.flat => return null,
.tree => |roots| {
root_siblings = roots;
root_level = true;
},
}
} else return null;
if (root_level) return self.adoptRootLeavesBelow(root_siblings, bound, out);
const parent = &self.frames.items[self.frames.items.len - 2];
const siblings = parent.node.manifest().s;
if (parent.index >= siblings.len) return null;
// The eligible run: candidates whose successor's first key stays at or
// below `bound`. The run's final member is withheld as warm-up.
var stop = parent.index;
// STRICTLY below `bound`: a successor first key EQUAL to the patch is
// the danger case — a DELETE of that key erases the very boundary
// that closed the candidate leaf in the old tree (bits of a vanished
// key decide nothing), so that leaf must stream and re-partition.
// With strict-less, every adopted leaf's trailing boundary is decided
// by a surviving, unpatched key with unchanged bits and unchanged
// open count — it reproduces by determinism.
while (stop + 1 < siblings.len and
artifact.compareBytes(siblings[stop + 1].filename, bound) == .lt) stop += 1;
if (stop <= parent.index) return null;
const adopt_until = stop - 1; // withhold the last eligible sibling
if (adopt_until < parent.index) return null;
var adopted: usize = 0;
while (parent.index <= adopt_until) : (parent.index += 1) {
const child = siblings[parent.index];
if (self.previous_card) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
try self.appendDescriptor(child, out);
try self.remember(child.hash);
// The adopted leaf's own last key is unknown without loading it;
// its successor's first key is a proven upper fence, so ordering
// stays checked without a read.
try self.setPreviousCard(child.filename);
adopted += 1;
}
// The ONE load adoption pays, and it buys global partitioner
// continuity: the last adopted group's true member count decides the
// first streamed boundary after the gap (`adoptGroup`).
const last = siblings[adopt_until];
var node = try self.editor_.loadNode(last.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0) return error.WrongNodeType;
return .{ .adopted = adopted, .last_members = manifest.f.len };
}
fn next(self: *OldTreeCursor) Error!?StreamEntry {
switch (self.root) {
.flat => |entries| {
if (self.flat_index == entries.len) return null;
const card = entries[self.flat_index];
self.flat_index += 1;
return @as(?StreamEntry, try self.returned(card, null));
},
.tree => |roots| while (true) {
if (self.frames.items.len == 0) {
if (self.root_index == roots.len) return null;
const child = roots[self.root_index];
if (self.previous_root) |previous| if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
self.previous_root = child.filename;
self.root_index += 1;
try self.descend(child.hash, child.filename);
continue;
}
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) {
if (frame.index < manifest.f.len) {
const card = manifest.f[frame.index];
frame.index += 1;
return @as(?StreamEntry, try self.returned(card, frame.name));
}
} else {
if (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.descend(child.hash, child.filename);
continue;
}
}
if (self.frames.pop()) |finished| {
var owned = finished;
owned.node.deinit();
}
},
}
}
};
const MergedCursor = struct {
old: *OldTreeCursor,
overlay: *const Overlay,
old_next: ?StreamEntry = null,
overlay_index: usize = 0,
/// Null under a flat format. Absence is structural rather than a flag a
/// reader could forget to consult -- and it is not cosmetic: `consumeOld`
/// hashes one retained filename per card per commit, which in the mode
/// built to be measured would be O(files x commits) of pure waste feeding
/// a checkpoint machinery that flat mode never consults.
old_partitioner: ?partition.CanonicalPartitioner,
last_was_old: bool = false,
fn init(old: *OldTreeCursor, overlay: *const Overlay, arena: std.mem.Allocator, shape: TreeFormat.Shape) MergedCursor {
return .{
.old = old,
.overlay = overlay,
.old_partitioner = switch (shape) {
.flat => null,
.tree => |tree| blk: {
const span: usize = @as(usize, 1) << tree.k;
break :blk partition.CanonicalPartitioner.init(arena, @as(u16, tree.k), span / 4, 4 * span);
},
},
};
}
fn deinit(self: *MergedCursor) void {
if (self.old_partitioner) |*partitioner| partitioner.deinit();
self.* = undefined;
}
fn consumeOld(self: *MergedCursor) Error!StreamEntry {
const old = self.old_next.?;
try self.old.setPreviousCard(old.card.filename);
self.old_next = null;
if (self.old_partitioner) |*partitioner| {
_ = try partitioner.push(artifact.zbits(old.card.filename));
}
return old;
}
/// The next overlay key still pending, or null when exhausted.
fn nextOverlayKey(self: *const MergedCursor) ?[]const u8 {
if (self.overlay_index >= self.overlay.entries.items.len) return null;
return self.overlay.entries.items[self.overlay_index].path;
}
/// The old-side checkpoint at an interior gap: `suffixCheckpoint`
/// minus its overlay-exhausted gate. PREFETCH-FREE, and that is
/// load-bearing: the suffix path's look-ahead pulls `old.next()`, which
/// pops the exhausted leaf and DESCENDS into the next one, consuming its
/// first card — position the adoption below must not have moved past.
/// At a leaf end the next leaf's first key is already in the parent's
/// S-entry, so the checkpoint needs no cursor motion at all.
fn interiorCheckpoint(self: *MergedCursor) ?partition.CanonicalPartitioner.Checkpoint {
const partitioner = if (self.old_partitioner) |*value| value else return null;
if (!self.last_was_old or self.overlay.clear) return null;
if (self.old_next != null) return null; // a live prefetch means position already advanced
const next_first = self.old.peekNextSiblingFirst() orelse return null;
return partitioner.checkpoint(next_first);
}
fn suffixCheckpoint(self: *MergedCursor) Error!?partition.CanonicalPartitioner.Checkpoint {
const partitioner = if (self.old_partitioner) |*value| value else return null;
if (!self.last_was_old or self.overlay.clear or self.overlay_index != self.overlay.entries.items.len) return null;
if (self.old_next == null) {
try self.old.savePreviousCard();
self.old_next = try self.old.next();
try self.old.restorePreviousCard();
}
return partitioner.checkpoint(if (self.old_next) |old| old.card.filename else null);
}
fn next(self: *MergedCursor) Error!?StreamEntry {
self.last_was_old = false;
while (true) {
if (self.old_next == null) self.old_next = try self.old.next();
const patch = if (self.overlay_index < self.overlay.entries.items.len) self.overlay.entries.items[self.overlay_index] else null;
if (self.old_next) |old| {
if (patch) |entry| {
switch (artifact.compareBytes(old.card.filename, entry.path)) {
.lt => {
const retained = try self.consumeOld();
if (!self.overlay.clear) {
self.last_was_old = true;
return retained;
}
},
.gt => {
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
},
.eq => {
_ = try self.consumeOld();
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
},
}
} else {
const retained = try self.consumeOld();
if (!self.overlay.clear) {
self.last_was_old = true;
return retained;
}
}
} else {
if (patch) |entry| {
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
} else return null;
}
}
}
};
const StreamBuild = struct {
root: RootRun,
tree_height: u8,
reused_nodes: usize,
emitted_nodes: usize,
};
const StreamBuilder = struct {
editor_: *TreeEditor,
arena: std.mem.Allocator,
known_nodes: *const KnownNodes,
reused_nodes: usize = 0,
emitted_nodes: usize = 0,
staged: std.ArrayList(StoreBatchNode) = .empty,
fn init(editor_: *TreeEditor, arena: std.mem.Allocator, known_nodes: *const KnownNodes) StreamBuilder {
return .{ .editor_ = editor_, .arena = arena, .known_nodes = known_nodes };
}
/// A candidate can recreate an immutable ancestor that the current tree
/// no longer reaches after a grow/shrink boundary. Consult storage after
/// the traversal-local fast path, but only reuse bytes that exactly match
/// the candidate serialization.
fn known(self: *const StreamBuilder, name: []const u8, bytes: []const u8) Error!bool {
if (self.known_nodes.contains(name)) return true;
var loaded = self.editor_.store.load_fn(self.editor_.store.ctx, self.editor_.gpa, name) catch |err| switch (err) {
error.MissingNode => return false,
else => return err,
};
defer loaded.deinit();
if (!std.mem.eql(u8, loaded.bytes, bytes)) return error.MalformedNode;
return true;
}
/// Store writes are delayed until the complete output root and every
/// descriptor have been allocated. This leaves no allocation failure
/// after the first newly-addressable artifact is written.
fn publishStaged(self: *StreamBuilder) Error!void {
if (self.staged.items.len == 0) return;
const batch: []const StoreBatchNode = self.staged.items;
try self.editor_.store.put_batch_fn(self.editor_.store.ctx, batch);
self.emitted_nodes += batch.len;
}
fn emitLeaf(self: *StreamBuilder, group: []const StreamEntry, out: *std.ArrayList(Descriptor)) Error!void {
try out.ensureUnusedCapacity(self.arena, 1);
try self.staged.ensureUnusedCapacity(self.arena, 1);
const cards = try self.arena.alloc(artifact.FCard, group.len);
for (group, cards) |entry, *card| card.* = entry.card;
const bytes = artifact.serializeSubmanifestLeaf(self.arena, cards) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
// The partitioner never emits an empty group, and `cards[0]` below
// would fault if it did. Mapped rather than asserted: the editor
// already has the vocabulary for "the node we would emit is not
// well formed", and a refusal survives --release=fast.
error.EmptySubmanifest => return error.MalformedNode,
};
const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
const already_known = try self.known(name, bytes);
const descriptor: Descriptor = .{
.card = .{ .filename = cards[0].filename, .hash = name },
.origin = if (already_known) name else null,
};
if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
.name = name,
.bytes = bytes,
});
out.appendAssumeCapacity(descriptor);
}
fn emitInterior(self: *StreamBuilder, group: []const Descriptor, out: *std.ArrayList(Descriptor)) Error!void {
try out.ensureUnusedCapacity(self.arena, 1);
try self.staged.ensureUnusedCapacity(self.arena, 1);
const cards = try self.arena.alloc(artifact.SCard, group.len);
for (group, cards) |entry, *card| card.* = entry.card;
const bytes = artifact.serializeSubmanifestInterior(self.arena, cards) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
// See `emitLeaf`: an empty member list is not a node this editor can
// name, and `cards[0]` below assumes it never happens.
error.EmptySubmanifest => return error.MalformedNode,
};
const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
const already_known = try self.known(name, bytes);
const descriptor: Descriptor = .{
.card = .{ .filename = cards[0].filename, .hash = name },
.origin = if (already_known) name else null,
};
if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
.name = name,
.bytes = bytes,
});
out.appendAssumeCapacity(descriptor);
}
/// draft-fossil-submanifests-00 §8.1's default posture: the merged stream
/// IS the root.
///
/// This duplicates none of the merge semantics -- rename, copy, delete,
/// `deleteall`, ordering and dedup all stay in `Overlay` and
/// `MergedCursor`, which this drains unchanged. What it drops is only the
/// tree apparatus: no partitioner, no leaf or interior serialization, no
/// staged node, and therefore no SUBMANIFEST artifact anywhere.
///
/// `merged.old.prefix` is necessarily empty here -- prefix descriptors are
/// pushed only from `OldTreeCursor` frames, and frames come only from
/// `descend`, which only a `.tree` root reaches. `apply` has already
/// refused a `.tree` parent under this format, so there is nothing to
/// splice and the whole checkpoint path is dead.
///
/// `StreamEntry.origin` is deliberately not carried. It names the old node
/// a retained card came from, and its only reader is `emitLeaf`'s node
/// reuse test -- flat mode emits no node, so duping it would be an arena
/// allocation and copy per card per commit whose result nothing reads. That
/// is the same O(files x commits) waste `MergedCursor.old_partitioner`
/// avoids, in the mode built to be measured. Collecting `FCard` directly
/// rather than `StreamEntry` makes the omission structural.
fn buildFlat(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
var cards: std.ArrayList(artifact.FCard) = .empty;
// Bounded by the merged stream, whose length is one commit's path set.
// The enforcing ceiling is the export reader's `max_total_data`
// (`git_import_cli.zig`), which caps the commands that reach `Overlay`
// before any of them reach here; the editor adds no ceiling of its own
// in flat mode because it builds no level.
while (try merged.next()) |entry| {
// The card is cloned, not borrowed: `merged.next()` hands out cards
// pointing into `OldTreeCursor`'s loaded node bytes, which are
// released on the next advance, and this list outlives the whole
// walk. The tree path pays the same clone, one layer earlier, when
// it builds its `StreamEntry`s.
try cards.append(self.arena, try cloneFCard(self.arena, entry.card));
}
// The local form of the invariant this whole mode turns on, checked at
// the commit that would break it rather than at the end of the import.
// An `assert` and not a returned error: both counters are this
// builder's own, so a nonzero one is a broken internal invariant.
std.debug.assert(self.emitted_nodes == 0);
std.debug.assert(self.reused_nodes == 0);
std.debug.assert(self.staged.items.len == 0);
return .{
.root = .{ .flat = try cards.toOwnedSlice(self.arena) },
.tree_height = 0,
// Literals rather than the counters: flat emits and reuses no node,
// and saying so structurally keeps the claim from drifting into
// "whatever the counters happen to hold".
.reused_nodes = 0,
.emitted_nodes = 0,
};
}
fn buildUnpublished(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
const tree = switch (self.editor_.format.shape) {
.flat => return self.buildFlat(merged),
.tree => |value| value,
};
const span: usize = @as(usize, 1) << tree.k;
var partitioner = partition.CanonicalPartitioner.init(self.arena, @as(u16, tree.k), span / 4, 4 * span);
defer partitioner.deinit();
var pending: std.ArrayList(StreamEntry) = .empty;
var current: std.ArrayList(StreamEntry) = .empty;
var leaves: std.ArrayList(Descriptor) = .empty;
// Adoption staging: descriptors land here first so a bailed
// attempt never half-splices into `leaves`.
var adopted_leaves: std.ArrayList(Descriptor) = .empty;
var interior_adopted = false;
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;
if (try merged.suffixCheckpoint()) |old_checkpoint| {
if (old_checkpoint.next_key) |next_key| {
const new_checkpoint = partitioner.checkpoint(next_key);
if (partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) {
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);
}
}
}
// An INTERIOR gap: the overlay still has entries, but the
// next one may lie many untouched leaves ahead. With the same
// equivalence proof the suffix path uses, adopt those leaves
// wholesale (no loads, no per-card streaming) and resume at the
// withheld warm-up sibling with both partitioners fresh — every
// later gap re-proves itself, so a misprediction costs streaming,
// never correctness.
interior: {
const patch_key = merged.nextOverlayKey() orelse break :interior;
const old_checkpoint = merged.interiorCheckpoint() orelse break :interior;
const next_key = old_checkpoint.next_key orelse break :interior;
if (artifact.compareBytes(next_key, patch_key) == .gt) break :interior; // patch lands in the NEXT leaf: nothing to skip
const new_checkpoint = partitioner.checkpoint(next_key);
if (!partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) break :interior;
const adoption = (try merged.old.adoptLeavesBelow(patch_key, &adopted_leaves)) orelse break :interior;
interior_adopted = true;
// Committed: the open group closes exactly where the old
// build closed it (that is what the equivalence proved), the
// adopted descriptors splice after it, and BOTH partitioners
// account the adopted groups so global boundary state stays
// the continuous build's — placeholder counts for all but the
// last group, whose true count the next streamed push reads.
if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
if (current.items.len != 0) try self.emitLeaf(current.items, &leaves);
pending = .empty;
current = .empty;
try leaves.appendSlice(self.arena, adopted_leaves.items);
adopted_leaves.clearRetainingCapacity();
self.reused_nodes += adoption.adopted;
var remaining = adoption.adopted;
// Placeholder count for all but the last group — nothing ever
// reads an interior group's size, it only needs to be a group
// (>= 1; span/4 is 0 at the smallest k).
const placeholder = @max(@as(usize, 1), span / 4);
while (remaining > 1) : (remaining -= 1) {
try partitioner.adoptGroup(placeholder);
if (merged.old_partitioner) |*old_part| try old_part.adoptGroup(placeholder);
}
try partitioner.adoptGroup(adoption.last_members);
if (merged.old_partitioner) |*old_part| try old_part.adoptGroup(adoption.last_members);
}
}
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) {
// After an interior adoption, `pending` can be legitimately
// empty here: the final boundary's predecessor group is an
// ADOPTED leaf already sitting in `leaves`.
if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
if (current.items.len != 0) try self.emitLeaf(current.items, &leaves);
} else if (pending.items.len == 0 and interior_adopted) {
// `finish` merged the short final group into its
// predecessor, and that predecessor is the LAST ADOPTED leaf:
// reopen it (the one load this path pays) and emit the union as
// the single leaf the continuous batch build would have written.
if (current.items.len != 0) {
const prior = leaves.pop() orelse return error.MalformedNode;
var node = try self.editor_.loadNode(prior.card.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0) return error.WrongNodeType;
var union_entries: std.ArrayList(StreamEntry) = .empty;
try union_entries.ensureUnusedCapacity(self.arena, manifest.f.len + current.items.len);
for (manifest.f) |card| {
union_entries.appendAssumeCapacity(.{
.card = try cloneFCard(self.arena, card),
.origin = try self.arena.dupe(u8, prior.card.hash),
});
}
union_entries.appendSlice(self.arena, current.items) catch return error.OutOfMemory;
try self.emitLeaf(union_entries.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.editor_.rememberCanonicalBasis(result.root);
errdefer {
self.editor_.canonical_root = null;
self.editor_.canonical_k = null;
}
try self.publishStaged();
result.reused_nodes = self.reused_nodes;
result.emitted_nodes = self.emitted_nodes;
return result;
}
fn finishTree(self: *StreamBuilder, leaves: std.ArrayList(Descriptor), old: *OldTreeCursor) Error!StreamBuild {
var level = leaves;
var height: usize = 1;
while (height < self.editor_.format.shape.tree.height_max) {
const next_height = height + 1;
if (old.takePrefixAtHeight(next_height)) |predecessor_group| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenPrefixGroup(predecessor_group, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level = reopened;
}
var rebuilt: std.ArrayList(Descriptor) = .empty;
if (!try self.buildInteriorLevel(level.items, height, &rebuilt)) {
// A retained ancestor can skip the immediate next height. Walk
// only its rightmost path to recover the direct predecessor
// stream, leaving all earlier siblings native and bounded.
if (old.takePrefixAboveHeight(next_height)) |ancestor| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenRightmostPrefixAtHeight(ancestor, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level = reopened;
continue;
}
break;
}
var next: std.ArrayList(Descriptor) = .empty;
const reused = try old.appendPrefixAtHeight(next_height, &next);
self.reused_nodes += reused;
try next.appendSlice(self.arena, rebuilt.items);
level = next;
height = next_height;
}
return .{
.root = .{ .tree = try descriptorCards(self.arena, level.items) },
.tree_height = @intCast(height),
.reused_nodes = self.reused_nodes,
.emitted_nodes = self.emitted_nodes,
};
}
fn mergeRootPrefixes(
self: *StreamBuilder,
old: *OldTreeCursor,
level: *std.ArrayList(Descriptor),
height: usize,
) Error!void {
while (true) {
const next_height = height + 1;
if (old.takePrefixAtHeight(next_height)) |predecessor_group| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenPrefixGroup(predecessor_group, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level.* = reopened;
continue;
}
if (old.takePrefixAboveHeight(next_height)) |ancestor| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenRightmostPrefixAtHeight(ancestor, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level.* = reopened;
continue;
}
break;
}
// Last chance to splice: `finishRootLevel` never consults the cursor
// again, so anything still retained here would be dropped from the
// tree. The splice is consuming, so this is a no-op whenever the
// caller already owns this height rather than a second copy of it.
if (old.hasPrefixAtHeight(height)) {
var prefixed: std.ArrayList(Descriptor) = .empty;
self.reused_nodes += try old.appendPrefixAtHeight(height, &prefixed);
try prefixed.appendSlice(self.arena, level.items);
level.* = prefixed;
}
}
fn finishRootLevel(
self: *StreamBuilder,
level: std.ArrayList(Descriptor),
start_height: usize,
) Error!StreamBuild {
var current = level;
var height = start_height;
while (height < self.editor_.format.shape.tree.height_max) {
var raised: std.ArrayList(Descriptor) = .empty;
if (!try self.buildInteriorLevel(current.items, height, &raised)) break;
current = raised;
height += 1;
}
return .{
.root = .{ .tree = try descriptorCards(self.arena, current.items) },
.tree_height = @intCast(height),
.reused_nodes = self.reused_nodes,
.emitted_nodes = self.emitted_nodes,
};
}
/// Rebuild each descriptor height until an equivalent old checkpoint, then
/// hand the final direct-root node to the result only at its measured
/// height. A cursor level is fixed-depth even when continuation crosses
/// several exhausted ancestors, so a height advances exactly once per
/// rebuilt descriptor level.
fn finishCheckpoint(
self: *StreamBuilder,
leaves: std.ArrayList(Descriptor),
old: *OldTreeCursor,
) Error!StreamBuild {
var level = leaves;
var height: usize = 1;
var include_next_leaf = true;
var root_height: ?usize = null;
while (true) {
if (height > 1 and old.hasPrefixAtHeight(height)) {
var prefixed: std.ArrayList(Descriptor) = .empty;
self.reused_nodes += try old.appendPrefixAtHeight(height, &prefixed);
try prefixed.appendSlice(self.arena, level.items);
level = prefixed;
}
var old_continuation: std.ArrayList(Descriptor) = .empty;
var old_group_start: ?usize = null;
if (root_height == null) {
const has_parent = try old.appendCheckpointLevel(include_next_leaf, &old_continuation);
self.reused_nodes += old_continuation.items.len;
if (has_parent) {
if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
const group_depth = try old.checkpointDepth();
var splice_at: ?usize = null;
var reached_root = false;
while (splice_at == null) {
const continuation_start = old_continuation.items.len;
if (!try old.appendNextCheckpointGroup(group_depth, &old_continuation)) {
reached_root = true;
break;
}
self.reused_nodes += old_continuation.items.len - continuation_start;
if (old_group_start == null) old_group_start = continuation_start;
splice_at = try self.findInteriorSplice(
level.items,
old_continuation.items,
old_group_start,
height,
);
}
if (!reached_root) {
var next: std.ArrayList(Descriptor) = .empty;
try self.buildInteriorPrefix(level.items, old_continuation.items, old_group_start, height, &next);
level = next;
height += 1;
include_next_leaf = false;
continue;
}
}
const measured_root_height = try old.takeRootCheckpoint();
if (height > measured_root_height) return error.MalformedNode;
root_height = measured_root_height;
}
const native_root_height = root_height.?;
if (height == native_root_height) {
const suffix_start = old_continuation.items.len;
try old.appendRootSuffixAtRootHeight(native_root_height, &old_continuation);
self.reused_nodes += old_continuation.items.len - suffix_start;
try level.appendSlice(self.arena, old_continuation.items);
try self.mergeRootPrefixes(old, &level, height);
return self.finishRootLevel(level, height);
}
if (height > native_root_height) return error.MalformedNode;
if (height >= self.editor_.format.shape.tree.height_max) return error.HeightExceeded;
var splice_at: ?usize = null;
while (splice_at == null) {
const frontier_start = old_continuation.items.len;
switch (try old.appendRootSuffixFrontierAtHeight(native_root_height, height, &old_continuation)) {
.descriptor => {
self.reused_nodes += old_continuation.items.len - frontier_start;
},
.group => {
self.reused_nodes += old_continuation.items.len - frontier_start;
if (old_group_start == null) old_group_start = frontier_start;
splice_at = try self.findInteriorSplice(
level.items,
old_continuation.items,
old_group_start,
height,
);
// `buildInteriorPrefix` reconstructs every exposed
// group into the next level, including a group whose
// splice starts at its first child. The raw suffix
// parent must therefore be consumed before that next
// level can append it again at root height.
try old.commitRootSuffixFrontier(height);
},
.end => {
try level.appendSlice(self.arena, old_continuation.items);
try self.mergeRootPrefixes(old, &level, height);
return self.finishRootLevel(level, height);
},
}
}
var next: std.ArrayList(Descriptor) = .empty;
try self.buildInteriorPrefix(level.items, old_continuation.items, old_group_start, height, &next);
level = next;
height += 1;
include_next_leaf = false;
}
}
/// Reuse begins only at the start of a complete untouched old canonical
/// group. The initial checkpoint remainder may be mid-group, so it is
/// replayed into the rebuilt state but never treated as old state.
fn findInteriorSplice(
self: *StreamBuilder,
rebuilt: []const Descriptor,
old_continuation: []const Descriptor,
old_group_start: ?usize,
height: usize,
) Error!?usize {
const start = old_group_start orelse return null;
const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
const min_members = span / 4;
const max_members = 4 * span;
var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer old_partitioner.deinit();
var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer new_partitioner.deinit();
var equivalent_splices: std.ArrayList(usize) = .empty;
for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[0..start]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[start..], start..) |entry, old_index| {
if (old_partitioner.count != 0 and old_partitioner.bounds.items.len >= 2) {
const open_members = old_partitioner.count - old_partitioner.bounds.items[old_partitioner.bounds.items.len - 1];
const starts_old_group = open_members == max_members or
(artifact.zbits(entry.card.filename) >= threshold and open_members >= min_members);
if (starts_old_group) {
const old_checkpoint = old_partitioner.checkpoint(entry.card.filename);
const new_checkpoint = new_partitioner.checkpoint(entry.card.filename);
if (partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) {
try equivalent_splices.append(self.arena, old_index);
}
}
}
_ = try old_partitioner.push(artifact.zbits(entry.card.filename));
_ = try new_partitioner.push(artifact.zbits(entry.card.filename));
}
const old_bounds = try old_partitioner.finish();
for (equivalent_splices.items) |candidate| {
for (old_bounds) |bound| {
if (bound == candidate - start) return candidate;
}
}
return null;
}
/// `rebuilt` is the newly emitted continuation. `old_continuation` is
/// independently read from the old descriptor stream. Once both
/// partitioners reach the same checkpoint at an old canonical boundary,
/// the old partitioner owns the remaining suffix rather than replaying it
fn buildInteriorPrefix(
self: *StreamBuilder,
rebuilt: []const Descriptor,
old_continuation: []const Descriptor,
old_group_start: ?usize,
height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
const min_members = span / 4;
const max_members = 4 * span;
const splice_at = try self.findInteriorSplice(rebuilt, old_continuation, old_group_start, height);
if (splice_at) |old_splice| {
const start = old_group_start orelse return error.MalformedNode;
var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer old_partitioner.deinit();
for (old_continuation[start..]) |entry| _ = try old_partitioner.push(artifact.zbits(entry.card.filename));
const old_bounds = try old_partitioner.finish();
var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer new_partitioner.deinit();
for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[0..old_splice]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
// The equivalent checkpoint owns the still-open new group. Do not
// call `finish`: its EOF rule would serialize that partial group
// and prevent the old suffix from supplying its canonical tail.
const completed_bounds = new_partitioner.bounds.items;
var rebuilt_start: usize = 0;
for (completed_bounds[1..]) |end| {
if (end <= rebuilt.len) {
try self.emitInterior(rebuilt[rebuilt_start..end], out);
} else if (rebuilt_start >= rebuilt.len) {
try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. end - rebuilt.len], out);
} else {
const members = try self.arena.alloc(Descriptor, end - rebuilt_start);
const rebuilt_members = rebuilt.len - rebuilt_start;
@memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
try self.emitInterior(members, out);
}
rebuilt_start = end;
}
// `old_splice` is the next item at the equivalent checkpoint. The
// partitioner has deliberately not consumed it, so its boundary
// is absent from `bounds`; finalize the preceding canonical group
// explicitly instead of dropping it or serializing the suffix's
// open final group.
const prefix_end = rebuilt.len + old_splice;
if (rebuilt_start != prefix_end) {
if (prefix_end <= rebuilt.len) {
try self.emitInterior(rebuilt[rebuilt_start..prefix_end], out);
} else if (rebuilt_start >= rebuilt.len) {
try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. old_splice], out);
} else {
const members = try self.arena.alloc(Descriptor, prefix_end - rebuilt_start);
const rebuilt_members = rebuilt.len - rebuilt_start;
@memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0..old_splice]);
try self.emitInterior(members, out);
}
}
var old_start = start;
for (old_bounds[1..]) |relative_end| {
const end = start + relative_end;
if (old_start >= old_splice) try self.emitInterior(old_continuation[old_start..end], out);
old_start = end;
}
return;
}
var fallback = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer fallback.deinit();
for (rebuilt) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
for (old_continuation) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
const fallback_bounds = try fallback.finish();
if (fallback_bounds.len < 2) return error.MalformedNode;
var fallback_start: usize = 0;
for (fallback_bounds[1..]) |end| {
if (end <= rebuilt.len) {
try self.emitInterior(rebuilt[fallback_start..end], out);
} else if (fallback_start >= rebuilt.len) {
try self.emitInterior(old_continuation[fallback_start - rebuilt.len .. end - rebuilt.len], out);
} else {
const members = try self.arena.alloc(Descriptor, end - fallback_start);
const rebuilt_members = rebuilt.len - fallback_start;
@memcpy(members[0..rebuilt_members], rebuilt[fallback_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
try self.emitInterior(members, out);
}
fallback_start = end;
}
}
/// a singleton or non-reducing level is returned to its caller unchanged.
fn buildInteriorLevel(self: *StreamBuilder, input: []const Descriptor, height: usize, out: *std.ArrayList(Descriptor)) Error!bool {
const span: usize = @as(usize, 1) << self.editor_.format.shape.tree.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.shape.tree.k));
var partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, span / 4, 4 * span);
defer partitioner.deinit();
for (input) |entry| _ = try partitioner.push(artifact.zbits(entry.card.filename));
const bounds = try partitioner.finish();
const count = partition.groupCount(bounds);
if (count <= 1 or count >= input.len) return false;
var start: usize = 0;
for (bounds[1..]) |end| {
try self.emitInterior(input[start..end], out);
start = end;
}
return true;
}
};
fn streamCards(arena: std.mem.Allocator, entries: []const StreamEntry) std.mem.Allocator.Error![]const artifact.FCard {
const cards = try arena.alloc(artifact.FCard, entries.len);
for (entries, cards) |entry, *card| card.* = entry.card;
return cards;
}
fn descriptorCards(arena: std.mem.Allocator, entries: []const Descriptor) std.mem.Allocator.Error![]const artifact.SCard {
const cards = try arena.alloc(artifact.SCard, entries.len);
for (entries, cards) |entry, *card| card.* = entry.card;
return cards;
}
/// A `.tree` root handed to a `.flat` editor. Both public entry points that
/// accept a caller-supplied `RootView` -- `apply` and `lookup` -- refuse it
/// here, so the same bad argument gets the same answer from both rather than
/// `InvalidFormat` from one and a union-tag panic from the other. See `apply`
/// for why no such root can exist under the flat induction.
fn rootMismatchesFormat(shape: TreeFormat.Shape, root: RootView) bool {
return std.meta.activeTag(shape) == .flat and std.meta.activeTag(root) == .tree;
}
fn lookupFlat(entries: []const artifact.FCard, path: []const u8) ?artifact.FCard {
const index = lowerBound(entries, path);
if (index < entries.len and std.mem.eql(u8, entries[index].filename, path)) return entries[index];
return null;
}
fn childForPath(cards: []const artifact.SCard, path: []const u8) ?artifact.SCard {
var candidate: ?artifact.SCard = null;
for (cards) |card| {
if (artifact.compareBytes(card.filename, path) == .gt) break;
candidate = card;
}
return candidate;
}
/// Index of the direct child that contains `path`, or the first child when the
/// requested path precedes the range. This is a binary seek over S cards, never
/// an F-card walk.
fn childIndexForPath(cards: []const artifact.SCard, path: []const u8) usize {
std.debug.assert(cards.len != 0);
var low: usize = 0;
var high = cards.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (artifact.compareBytes(cards[mid].filename, path) != .gt) low = mid + 1 else high = mid;
}
return if (low == 0) 0 else low - 1;
}
fn lowerBound(entries: []const artifact.FCard, path: []const u8) usize {
var low: usize = 0;
var high = entries.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (artifact.compareBytes(entries[mid].filename, path) == .lt) low = mid + 1 else high = mid;
}
return low;
}
fn nameArtifact(
arena: std.mem.Allocator,
algo: artifact.HashAlgo,
bytes: []const u8,
) std.mem.Allocator.Error![]const u8 {
var scratch: [64]u8 = undefined;
return arena.dupe(u8, artifact.artifactName(algo, bytes, &scratch));
}
fn cloneFCards(arena: std.mem.Allocator, entries: []const artifact.FCard) std.mem.Allocator.Error![]const artifact.FCard {
const copied = try arena.alloc(artifact.FCard, entries.len);
for (entries, copied) |entry, *dest| dest.* = try cloneFCard(arena, entry);
return copied;
}
fn cloneSCards(arena: std.mem.Allocator, cards: []const artifact.SCard) std.mem.Allocator.Error![]const artifact.SCard {
const copied = try arena.alloc(artifact.SCard, cards.len);
for (cards, copied) |card, *dest| dest.* = .{
.filename = try arena.dupe(u8, card.filename),
.hash = try arena.dupe(u8, card.hash),
};
return copied;
}
fn cloneFCard(arena: std.mem.Allocator, value: artifact.FCard) std.mem.Allocator.Error!artifact.FCard {
return .{
.filename = try arena.dupe(u8, value.filename),
.hash = if (value.hash) |hash| try arena.dupe(u8, hash) else null,
.perm = if (value.perm) |perm| try arena.dupe(u8, perm) else null,
.old_name = if (value.old_name) |old| try arena.dupe(u8, old) else null,
.mode = value.mode,
};
}
comptime {
_ = partition.CanonicalPartitioner;
}