const std = @import("std");
const artifact = @import("artifact.zig");
const partition = @import("submanifest_partition.zig");
pub const TreeFormat = struct {
k: u4,
hash_algo: artifact.HashAlgo,
height_max: u8,
};
pub const StoreError = error{
MissingNode,
StorageFailure,
OutOfMemory,
};
pub const LoadedBytes = struct {
bytes: []u8,
allocator: std.mem.Allocator,
pub fn deinit(self: *LoadedBytes) void {
self.allocator.free(self.bytes);
self.* = undefined;
}
};
/// 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: *const fn (*anyopaque, std.mem.Allocator, []const u8) StoreError!LoadedBytes,
put_fn: *const fn (*anyopaque, []const u8, []const u8) StoreError!void,
};
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,
changed_paths: usize,
reused_nodes: usize,
emitted_nodes: usize,
arena_state: std.heap.ArenaAllocator,
pub fn deinit(self: *BuildResult) void {
self.arena_state.deinit();
self.* = undefined;
}
};
const LoadedNode = struct {
bytes: LoadedBytes,
manifest: artifact.Manifest,
fn deinit(self: *LoadedNode) void {
self.manifest.deinit();
self.bytes.deinit();
self.* = undefined;
}
};
const CacheEntry = struct {
link: std.DoublyLinkedList.Node = .{},
name: []u8,
node: LoadedNode,
leases: usize = 0,
};
/// A decoded node held either by the cache or by its caller. Cached nodes stay
/// pinned while a traversal borrows them, so FIFO eviction cannot invalidate a
/// parent frame during recursive descent.
const NodeLease = union(enum) {
cached: *CacheEntry,
owned: LoadedNode,
fn manifest(self: *const NodeLease) *const artifact.Manifest {
return switch (self.*) {
.cached => |entry| &entry.node.manifest,
.owned => |*node| &node.manifest,
};
}
fn deinit(self: *NodeLease) void {
switch (self.*) {
.cached => |entry| {
std.debug.assert(entry.leases != 0);
entry.leases -= 1;
},
.owned => |*node| node.deinit(),
}
self.* = undefined;
}
};
/// A repository-bound reader and canonical writer. It never accepts a
/// per-commit format change and retains no parent-tree state between `apply`
/// calls; callers pass one call-scoped root view each time.
pub const TreeEditor = struct {
gpa: std.mem.Allocator,
store: TreeStore,
format: TreeFormat,
cache_bytes_max: usize,
cache_bytes: usize = 0,
cache_high_water: usize = 0,
cache: std.DoublyLinkedList = .{},
lookup_arena: std.heap.ArenaAllocator,
pub fn init(
gpa: std.mem.Allocator,
store: TreeStore,
format: TreeFormat,
cache_bytes_max: usize,
) Error!TreeEditor {
if (format.k < artifact.min_k or format.k > artifact.max_k or
format.height_max == 0 or format.height_max > @as(u8, @intCast(artifact.max_construct_height)))
{
return error.InvalidFormat;
}
return .{
.gpa = gpa,
.store = store,
.format = format,
.cache_bytes_max = cache_bytes_max,
.lookup_arena = std.heap.ArenaAllocator.init(gpa),
};
}
pub fn deinit(self: *TreeEditor) void {
self.lookup_arena.deinit();
while (self.cache.popFirst()) |link| {
self.destroyCacheEntry(@fieldParentPtr("link", link));
}
self.* = undefined;
}
pub fn cacheHighWater(self: *const TreeEditor) usize {
return self.cache_high_water;
}
/// Read an exact file card without exposing any loaded-byte or cache view.
/// The returned card is owned by the editor until its next `lookup`,
/// `apply`, or `deinit`.
pub fn lookup(self: *TreeEditor, root: RootView, path: []const u8) Error!?artifact.FCard {
self.resetLookupArena();
const arena = self.lookup_arena.allocator();
return switch (root) {
.flat => |entries| if (lookupFlat(entries, path)) |card| try cloneFCard(arena, card) else null,
.tree => |cards| self.lookupTree(cards, path, 0, &[_][]const u8{}),
};
}
pub fn apply(
self: *TreeEditor,
parent: RootView,
commands: []const TreeCommand,
) Error!BuildResult {
self.resetLookupArena();
var arena_state = std.heap.ArenaAllocator.init(self.gpa);
errdefer arena_state.deinit();
const arena = arena_state.allocator();
if (commands.len == 0) {
const root: RootRun = switch (parent) {
.flat => |entries| .{ .flat = try cloneFCards(arena, entries) },
.tree => |cards| .{ .tree = try cloneSCards(arena, cards) },
};
return .{
.root = root,
.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: std.ArrayList([]const u8) = .empty;
const start_path = if (overlay.clear) null else overlay.entries.items[0].path;
var cursor = try OldTreeCursor.init(self, parent, arena, &known_nodes, start_path);
defer cursor.deinit();
var merged = MergedCursor.init(&cursor, &overlay, arena, self.format.k);
defer merged.deinit();
var builder = StreamBuilder.init(self, arena, &known_nodes);
const root = try builder.build(&merged);
return .{
.root = root.root,
.changed_paths = changed,
.reused_nodes = root.reused_nodes,
.emitted_nodes = root.emitted_nodes,
.arena_state = arena_state,
};
}
fn lookupTree(
self: *TreeEditor,
cards: []const artifact.SCard,
path: []const u8,
depth: u8,
ancestry: []const []const u8,
) Error!?artifact.FCard {
try self.validateTreeCards(cards, depth, ancestry);
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 {
var link = self.cache.first;
while (link) |current| : (link = current.next) {
const entry: *CacheEntry = @fieldParentPtr("link", current);
if (std.mem.eql(u8, entry.name, name)) return entry;
}
return null;
}
fn cachedBytes(name: []const u8, node: *const LoadedNode) usize {
return @sizeOf(CacheEntry) +
name.len +
node.bytes.bytes.len +
node.manifest.arena_state.queryCapacity();
}
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 {
std.debug.assert(incoming <= self.cache_bytes_max);
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_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);
if (self.cache_bytes_max == 0 or bytes > self.cache_bytes_max or !self.evictFor(bytes)) {
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, .leases = 1 };
self.cache.append(&entry.link);
self.cache_bytes += bytes;
self.cache_high_water = @max(self.cache_high_water, self.cache_bytes);
std.debug.assert(self.cache_bytes <= self.cache_bytes_max);
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 (depth >= self.format.height_max) return error.HeightExceeded;
var selected_index: ?usize = null;
for (cards, 0..) |card, index| {
if (artifact.compareBytes(card.filename, path) == .gt) break;
selected_index = index;
}
const index = selected_index orelse return null;
const child = cards[index];
if (index != 0) {
const predecessor = cards[index - 1];
if (artifact.compareBytes(predecessor.filename, child.filename) != .lt) return error.MalformedNode;
try self.validateRightmostRange(
predecessor.hash,
predecessor.filename,
child.filename,
depth,
ancestry,
);
}
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, child.hash)) return error.Cycle;
var node = try self.loadNode(child.hash);
defer node.deinit();
const manifest = node.manifest();
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, child.filename, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
return null;
}
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = child.hash;
return self.lookupTouchedTree(
manifest.s,
path,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
arena,
);
}
/// Validate only the predecessor range that can reach `upper`. Decoded
/// nodes still validate each local descriptor list, while following only
/// the rightmost descendant prevents an apply from walking unrelated
/// predecessor leaves.
fn validateRightmostRange(
self: *TreeEditor,
name: []const u8,
expected_first: []const u8,
upper: []const u8,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.height_max) return error.HeightExceeded;
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;
var node = try self.loadNode(name);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, upper) != .lt) return error.MalformedNode;
return;
}
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = name;
const rightmost = manifest.s[manifest.s.len - 1];
return self.validateRightmostRange(
rightmost.hash,
rightmost.filename,
upper,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
);
}
/// Validate the complete reachable range before returning any lookup
/// result. A selected child is not enough: a malformed sibling can expand
/// into the selected child's range and make the S run ambiguous.
fn validateTreeCards(
self: *TreeEditor,
cards: []const artifact.SCard,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.height_max or cards.len == 0) return error.MalformedNode;
var previous: ?[]const u8 = null;
for (cards, 0..) |child, index| {
if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
previous = child.filename;
const upper = if (index + 1 < cards.len) cards[index + 1].filename else null;
try self.validateTreeNode(child.hash, child.filename, upper, depth, ancestry);
}
}
/// `upper` is the next sibling's advertised first key. Every descendant
/// must be strictly below it, which makes sibling ranges disjoint.
fn validateTreeNode(
self: *TreeEditor,
name: []const u8,
expected_first: []const u8,
upper: ?[]const u8,
depth: u8,
ancestry: []const []const u8,
) Error!void {
if (depth >= self.format.height_max) return error.HeightExceeded;
for (ancestry) |ancestor| if (std.mem.eql(u8, ancestor, name)) return error.Cycle;
var node = try self.loadNode(name);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len == 0 and manifest.s.len == 0) return error.WrongNodeType;
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (!std.mem.eql(u8, expected_first, actual_first)) return error.MalformedNode;
if (manifest.f.len != 0) {
if (upper) |next| {
if (artifact.compareBytes(manifest.f[manifest.f.len - 1].filename, next) != .lt) return error.MalformedNode;
}
return;
}
if (manifest.s.len == 0) return error.WrongNodeType;
var next_ancestry: [artifact.max_tree_depth][]const u8 = undefined;
if (ancestry.len >= next_ancestry.len) return error.HeightExceeded;
@memcpy(next_ancestry[0..ancestry.len], ancestry);
next_ancestry[ancestry.len] = name;
var previous: ?[]const u8 = null;
for (manifest.s, 0..) |child, index| {
if (previous) |key| if (artifact.compareBytes(key, child.filename) != .lt) return error.MalformedNode;
previous = child.filename;
const child_upper = if (index + 1 < manifest.s.len) manifest.s[index + 1].filename else upper;
try self.validateTreeNode(
child.hash,
child.filename,
child_upper,
depth + 1,
next_ancestry[0 .. ancestry.len + 1],
);
}
}
fn lookupValidatedTree(
self: *TreeEditor,
cards: []const artifact.SCard,
path: []const u8,
depth: u8,
arena: std.mem.Allocator,
) Error!?artifact.FCard {
const child = childForPath(cards, path) orelse return null;
var node = try self.loadNode(child.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len != 0) {
if (lookupFlat(manifest.f, path)) |card| return try cloneFCard(arena, card);
return null;
}
if (depth + 1 >= self.format.height_max) return error.HeightExceeded;
return self.lookupValidatedTree(manifest.s, path, depth + 1, arena);
}
};
const StreamEntry = struct {
card: artifact.FCard,
/// The exact old leaf containing `card`, if it survived the overlay.
origin: ?[]const u8,
};
const Descriptor = struct {
card: artifact.SCard,
/// The old node name is deliberately propagated upward. A canonical
/// repaired parent can therefore be reused without retaining its children.
origin: ?[]const u8,
};
/// Immutable bytes and their name, prepared before any persistence begins.
const PendingArtifact = struct {
name: []const u8,
bytes: []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: std.ArrayList([]const u8) = .empty;
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,
};
/// 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: *std.ArrayList([]const u8),
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,
fn init(
editor_: *TreeEditor,
root: RootView,
arena: std.mem.Allocator,
known_nodes: *std.ArrayList([]const u8),
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 {
for (self.known_nodes.items) |known| if (std.mem.eql(u8, known, name)) return;
try self.known_nodes.append(self.arena, try self.arena.dupe(u8, name));
}
fn descend(self: *OldTreeCursor, name: []const u8, expected_first: ?[]const u8) Error!void {
if (self.frames.items.len >= self.editor_.format.height_max) return error.HeightExceeded;
for (self.frames.items) |frame| if (std.mem.eql(u8, frame.name, name)) return error.Cycle;
var node = try self.editor_.loadNode(name);
errdefer node.deinit();
const manifest = node.manifest();
const actual_first = if (manifest.f.len != 0) manifest.f[0].filename else manifest.s[0].filename;
if (expected_first) |key| if (!std.mem.eql(u8, key, actual_first)) return error.MalformedNode;
try self.remember(name);
try self.frames.append(self.editor_.gpa, .{ .name = name, .node = node });
}
fn discardLastFrame(self: *OldTreeCursor) void {
const finished = self.frames.pop().?;
var owned = finished;
owned.node.deinit();
}
fn directRootHeight(self: *OldTreeCursor, frame: *const CursorFrame) Error!usize {
var height: usize = 1;
var manifest = frame.node.manifest();
var owned: ?NodeLease = null;
errdefer if (owned) |*node| node.deinit();
while (manifest.f.len == 0) {
if (manifest.s.len == 0) return error.WrongNodeType;
if (height >= self.editor_.format.height_max) return error.HeightExceeded;
const loaded = try self.editor_.loadNode(manifest.s[0].hash);
if (owned) |*node| node.deinit();
owned = loaded;
height += 1;
manifest = owned.?.manifest();
}
if (owned) |*node| node.deinit();
return height;
}
fn recordRootCheckpoint(self: *OldTreeCursor) Error!void {
if (self.frames.items.len != 1) return error.MalformedNode;
self.checkpoint = .{ .root = .{
.height = try self.directRootHeight(&self.frames.items[0]),
} };
}
fn finishCheckpointFrame(self: *OldTreeCursor) Error!void {
if (self.frames.items.len == 0) return error.MalformedNode;
if (self.frames.items.len == 1) try self.recordRootCheckpoint();
self.discardLastFrame();
}
fn setCheckpointContinuation(self: *OldTreeCursor, group_depth: usize) void {
self.checkpoint = .{ .continuation = .{
.group_depth = group_depth,
} };
}
fn checkpointDepth(self: *const OldTreeCursor) Error!usize {
return switch (self.checkpoint orelse return error.MalformedNode) {
.continuation => |continuation| continuation.group_depth,
.root => error.MalformedNode,
};
}
fn takeRootCheckpoint(self: *OldTreeCursor) Error!usize {
const state = self.checkpoint orelse return error.MalformedNode;
self.checkpoint = null;
return switch (state) {
.root => |root| root.height,
.continuation => error.MalformedNode,
};
}
fn descendRightmostLeaf(self: *OldTreeCursor) Error!void {
while (true) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) return;
if (manifest.s.len == 0) return error.WrongNodeType;
frame.index = manifest.s.len;
const child = manifest.s[manifest.s.len - 1];
try self.descend(child.hash, child.filename);
}
}
/// Reopen the immediately preceding leaf when one exists. A late deletion
/// may shrink the final group that crosses this leaf boundary, so the
/// predecessor is mutable input rather than a frozen prefix descriptor.
fn rewindToPredecessorLeaf(self: *OldTreeCursor) Error!void {
var has_predecessor = self.root_index > 1;
if (!has_predecessor and self.frames.items.len > 1) {
for (self.frames.items[0 .. self.frames.items.len - 1]) |frame| {
if (frame.index > 1) {
has_predecessor = true;
break;
}
}
}
if (!has_predecessor) return;
self.discardLastFrame();
while (self.frames.items.len != 0) {
const parent_index = self.frames.items.len - 1;
const parent = &self.frames.items[parent_index];
std.debug.assert(parent.index != 0);
const selected_index = parent.index - 1;
if (selected_index != 0) {
parent.index = selected_index;
const manifest = parent.node.manifest();
const child = manifest.s[selected_index - 1];
try self.descend(child.hash, child.filename);
return self.descendRightmostLeaf();
}
self.discardLastFrame();
}
std.debug.assert(self.root_index > 1);
const roots = switch (self.root) {
.flat => unreachable,
.tree => |cards| cards,
};
const selected_index = self.root_index - 1;
self.root_index = selected_index;
const child = roots[selected_index - 1];
try self.descend(child.hash, child.filename);
return self.descendRightmostLeaf();
}
fn setPreviousCard(self: *OldTreeCursor, filename: []const u8) std.mem.Allocator.Error!void {
self.previous_card_buf.clearRetainingCapacity();
try self.previous_card_buf.appendSlice(self.editor_.gpa, filename);
self.previous_card = self.previous_card_buf.items;
}
fn savePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
self.saved_previous_card_buf.clearRetainingCapacity();
if (self.previous_card) |previous| try self.saved_previous_card_buf.appendSlice(self.editor_.gpa, previous);
}
fn restorePreviousCard(self: *OldTreeCursor) std.mem.Allocator.Error!void {
if (self.saved_previous_card_buf.items.len == 0) {
self.previous_card = null;
return;
}
try self.setPreviousCard(self.saved_previous_card_buf.items);
}
fn returned(self: *OldTreeCursor, card: artifact.FCard, origin: ?[]const u8) Error!StreamEntry {
if (self.previous_card) |previous| if (artifact.compareBytes(previous, card.filename) != .lt) return error.MalformedNode;
try self.setPreviousCard(card.filename);
return .{ .card = card, .origin = origin };
}
fn atLeafEnd(self: *const OldTreeCursor) bool {
if (self.frames.items.len == 0) return false;
const frame = self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
return manifest.f.len != 0 and frame.index == manifest.f.len;
}
fn atRootEnd(self: *const OldTreeCursor) bool {
if (self.frames.items.len != 0) return false;
return switch (self.root) {
.flat => |entries| self.flat_index == entries.len,
.tree => |cards| self.root_index == cards.len,
};
}
fn appendLeaf(self: *OldTreeCursor, name: []const u8, manifest: *const artifact.Manifest, out: *std.ArrayList(Descriptor)) Error!void {
std.debug.assert(manifest.f.len != 0);
const first = manifest.f[0].filename;
if (self.previous_card) |previous| if (artifact.compareBytes(previous, first) != .lt) return error.MalformedNode;
try self.setPreviousCard(manifest.f[manifest.f.len - 1].filename);
const hash = try self.arena.dupe(u8, name);
try out.append(self.arena, .{
.card = .{ .filename = try self.arena.dupe(u8, first), .hash = hash },
.origin = hash,
});
}
fn appendDescriptor(self: *OldTreeCursor, card: artifact.SCard, out: *std.ArrayList(Descriptor)) Error!void {
const filename = try self.arena.dupe(u8, card.filename);
const hash = try self.arena.dupe(u8, card.hash);
try out.append(self.arena, .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
});
}
fn appendNativePrefix(self: *OldTreeCursor, card: artifact.SCard, height: usize) Error!void {
const filename = try self.arena.dupe(u8, card.filename);
const hash = try self.arena.dupe(u8, card.hash);
try self.prefix.append(self.arena, .{
.descriptor = .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
},
.height = height,
});
try self.remember(hash);
}
fn appendPrefixAtHeight(self: *const OldTreeCursor, height: usize, out: *std.ArrayList(Descriptor)) Error!usize {
const start = out.items.len;
for (self.prefix.items) |entry| {
if (entry.height != height) continue;
try out.append(self.arena, entry.descriptor);
}
return out.items.len - start;
}
fn hasPrefixAtHeight(self: *const OldTreeCursor, height: usize) bool {
for (self.prefix.items) |entry| if (entry.height == height) return true;
return false;
}
/// A native descriptor at the next level is the predecessor group for the
/// localized frontier. Reopen it instead of carrying a shallower
/// descriptor across the height boundary.
fn takePrefixAtHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
var index = self.prefix.items.len;
while (index != 0) {
index -= 1;
if (self.prefix.items[index].height == height) return self.prefix.orderedRemove(index);
}
return null;
}
/// Remove the closest retained ancestor strictly above `height`. The
/// rightmost such descriptor is the only old subtree adjacent to the
/// localized frontier.
fn takePrefixAboveHeight(self: *OldTreeCursor, height: usize) ?NativePrefixDescriptor {
var candidate_index: ?usize = null;
var candidate_height: usize = std.math.maxInt(usize);
for (self.prefix.items, 0..) |entry, index| {
if (entry.height <= height) continue;
if (entry.height < candidate_height or entry.height == candidate_height) {
candidate_index = index;
candidate_height = entry.height;
}
}
if (candidate_index) |index| return self.prefix.orderedRemove(index);
return null;
}
/// Rewind a retained ancestor to the current construction height without
/// flattening it. Every descent retains the older direct siblings at their
/// own formation height, then follows only the rightmost child because it
/// is adjacent to the edited suffix.
fn reopenRightmostPrefixAtHeight(
self: *OldTreeCursor,
group: NativePrefixDescriptor,
child_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
std.debug.assert(group.height > child_height + 1);
var current = group;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.k);
while (current.height > child_height + 1) {
var node = try self.editor_.loadNode(current.descriptor.card.hash);
defer node.deinit();
const manifest = node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
const next_height = current.height - 1;
for (manifest.s[0 .. manifest.s.len - 1]) |child| {
try self.appendNativePrefix(child, next_height);
}
const rightmost = manifest.s[manifest.s.len - 1];
const filename = try self.arena.dupe(u8, rightmost.filename);
const hash = try self.arena.dupe(u8, rightmost.hash);
try self.remember(hash);
current = .{
.descriptor = .{
.card = .{ .filename = filename, .hash = hash },
.origin = hash,
},
.height = next_height,
};
}
try self.reopenPrefixGroup(current, child_height, out);
}
/// Expand exactly one predecessor group into its direct descriptor stream.
/// Earlier descriptors at that height remain native prefix candidates.
fn reopenPrefixGroup(
self: *OldTreeCursor,
group: NativePrefixDescriptor,
child_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
std.debug.assert(group.height == child_height + 1);
var node = try self.editor_.loadNode(group.descriptor.card.hash);
defer node.deinit();
const manifest = node.manifest();
const max_members = 4 * (@as(usize, 1) << self.editor_.format.k);
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
for (manifest.s) |child| {
try self.appendDescriptor(child, out);
try self.remember(child.hash);
}
}
/// Descend to the changed leaf, then reopen its predecessor. Earlier
/// siblings remain direct descriptors at their original heights, so the
/// cursor never walks their leaves or F cards.
fn seek(self: *OldTreeCursor, path: []const u8) Error!void {
switch (self.root) {
.flat => {
self.flat_index = 0;
return;
},
.tree => |roots| {
if (roots.len == 0) return error.MalformedNode;
const root_index = childIndexForPath(roots, path);
self.root_index = root_index + 1;
try self.descend(roots[root_index].hash, roots[root_index].filename);
while (true) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) break;
if (manifest.s.len == 0) return error.WrongNodeType;
const child_index = childIndexForPath(manifest.s, path);
frame.index = child_index + 1;
try self.descend(manifest.s[child_index].hash, manifest.s[child_index].filename);
}
try self.rewindToPredecessorLeaf();
const leaf_height = self.frames.items.len;
for (roots[0 .. self.root_index - 1]) |child| {
try self.appendNativePrefix(child, leaf_height);
}
for (self.frames.items[0 .. self.frames.items.len - 1], 0..) |frame, depth| {
const manifest = frame.node.manifest();
const child_index = frame.index - 1;
const child_height = leaf_height - depth - 1;
for (manifest.s[0..child_index]) |child| {
try self.appendNativePrefix(child, child_height);
}
}
},
}
}
/// The checkpoint look-ahead has already entered its next leaf. Complete
/// that leaf, then expose the remainder of its immediate parent group.
/// The resulting continuation state retains its fixed group depth: frames
/// below it are the next-level frontier, while every retired frame has
/// contributed all direct children to this continuation or the rebuilt
/// descriptor stream.
fn appendCheckpointLevel(
self: *OldTreeCursor,
include_next_leaf: bool,
out: *std.ArrayList(Descriptor),
) Error!bool {
if (self.frames.items.len > self.editor_.format.height_max) return error.HeightExceeded;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.k);
self.checkpoint = null;
if (include_next_leaf) {
if (self.frames.items.len == 0) return error.MalformedNode;
const leaf = self.frames.items[self.frames.items.len - 1];
const manifest = leaf.node.manifest();
if (manifest.f.len == 0) return error.WrongNodeType;
if (manifest.f.len > max_members) return error.MalformedNode;
try self.appendLeaf(leaf.name, manifest, out);
try self.finishCheckpointFrame();
}
if (self.frames.items.len == 0) return false;
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
while (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.appendDescriptor(child, out);
}
try self.finishCheckpointFrame();
if (self.frames.items.len == 0) return false;
self.setCheckpointContinuation(self.frames.items.len);
return true;
}
/// Continue exactly one semantic descriptor height. A direct-root
/// completion ends this state immediately; its siblings remain native for
/// root handoff rather than becoming a provisional same-height suffix.
fn appendNextCheckpointGroup(
self: *OldTreeCursor,
group_depth: usize,
out: *std.ArrayList(Descriptor),
) Error!bool {
if (try self.checkpointDepth() != group_depth) return error.MalformedNode;
if (self.frames.items.len > self.editor_.format.height_max) return error.HeightExceeded;
const max_members = 4 * (@as(usize, 1) << self.editor_.format.k);
const roots = switch (self.root) {
.flat => return false,
.tree => |cards| cards,
};
while (true) {
if (self.frames.items.len == group_depth + 1) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
while (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.appendDescriptor(child, out);
}
if (group_depth == 0) {
try self.finishCheckpointFrame();
return false;
}
self.discardLastFrame();
self.setCheckpointContinuation(group_depth);
if (self.frames.items.len != group_depth) return error.MalformedNode;
return true;
}
if (self.frames.items.len > group_depth + 1) return error.MalformedNode;
if (self.frames.items.len != 0) {
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
if (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.descend(child.hash, child.filename);
continue;
}
if (self.frames.items.len == 1) try self.recordRootCheckpoint();
self.discardLastFrame();
continue;
}
if (self.root_index == roots.len) return false;
self.checkpoint = null;
const child = roots[self.root_index];
if (self.previous_root) |previous| {
if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
}
self.previous_root = child.filename;
self.root_index += 1;
try self.descend(child.hash, child.filename);
}
}
/// the untouched tail.
fn appendRootSuffix(self: *OldTreeCursor, out: *std.ArrayList(Descriptor)) Error!void {
const roots = switch (self.root) {
.flat => return,
.tree => |cards| cards,
};
while (self.root_index < roots.len) {
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.appendDescriptor(child, out);
}
}
/// Reuse direct-root suffixes at the final canonical descriptor height.
/// When construction stops below the old root, descend only S-card edges;
/// this never replays F cards or flattens the suffix. Every visited old
/// descriptor is an emitted descriptor at `target_height`.
fn appendRootDescriptorAtHeight(
self: *OldTreeCursor,
card: artifact.SCard,
card_height: usize,
target_height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
if (card_height < target_height or target_height == 0) return error.MalformedNode;
if (card_height == target_height) return self.appendDescriptor(card, out);
var node = try self.editor_.loadNode(card.hash);
defer node.deinit();
const manifest = node.manifest();
const max_members = 4 * (@as(usize, 1) << self.editor_.format.k);
if (manifest.f.len != 0 or manifest.s.len == 0) return error.WrongNodeType;
if (manifest.s.len > max_members) return error.MalformedNode;
for (manifest.s) |child| {
try self.appendRootDescriptorAtHeight(child, card_height - 1, target_height, out);
}
}
fn appendRootSuffixAtHeight(
self: *OldTreeCursor,
root_height: usize,
target_height: usize,
out: *std.ArrayList(Descriptor),
) Error!usize {
const start = out.items.len;
const roots = switch (self.root) {
.flat => return 0,
.tree => |cards| cards,
};
while (self.root_index < roots.len) {
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.appendRootDescriptorAtHeight(child, root_height, target_height, out);
}
return out.items.len - start;
}
fn next(self: *OldTreeCursor) Error!?StreamEntry {
switch (self.root) {
.flat => |entries| {
if (self.flat_index == entries.len) return null;
const card = entries[self.flat_index];
self.flat_index += 1;
return @as(?StreamEntry, try self.returned(card, null));
},
.tree => |roots| while (true) {
if (self.frames.items.len == 0) {
if (self.root_index == roots.len) return null;
const child = roots[self.root_index];
if (self.previous_root) |previous| if (artifact.compareBytes(previous, child.filename) != .lt) return error.MalformedNode;
self.previous_root = child.filename;
self.root_index += 1;
try self.descend(child.hash, child.filename);
continue;
}
const frame = &self.frames.items[self.frames.items.len - 1];
const manifest = frame.node.manifest();
if (manifest.f.len != 0) {
if (frame.index < manifest.f.len) {
const card = manifest.f[frame.index];
frame.index += 1;
return @as(?StreamEntry, try self.returned(card, frame.name));
}
} else {
if (frame.index < manifest.s.len) {
const child = manifest.s[frame.index];
frame.index += 1;
try self.descend(child.hash, child.filename);
continue;
}
}
if (self.frames.pop()) |finished| {
var owned = finished;
owned.node.deinit();
}
},
}
}
};
const MergedCursor = struct {
old: *OldTreeCursor,
overlay: *const Overlay,
old_next: ?StreamEntry = null,
overlay_index: usize = 0,
old_partitioner: partition.CanonicalPartitioner,
last_was_old: bool = false,
fn init(old: *OldTreeCursor, overlay: *const Overlay, arena: std.mem.Allocator, k: u4) MergedCursor {
const span: usize = @as(usize, 1) << k;
return .{
.old = old,
.overlay = overlay,
.old_partitioner = partition.CanonicalPartitioner.init(arena, @as(u16, k), span / 4, 4 * span),
};
}
fn deinit(self: *MergedCursor) void {
self.old_partitioner.deinit();
self.* = undefined;
}
fn consumeOld(self: *MergedCursor) Error!StreamEntry {
const old = self.old_next.?;
try self.old.setPreviousCard(old.card.filename);
self.old_next = null;
_ = try self.old_partitioner.push(artifact.zbits(old.card.filename));
return old;
}
fn suffixCheckpoint(self: *MergedCursor) Error!?partition.CanonicalPartitioner.Checkpoint {
if (!self.last_was_old or self.overlay.clear or self.overlay_index != self.overlay.entries.items.len) return null;
if (self.old_next == null) {
try self.old.savePreviousCard();
self.old_next = try self.old.next();
try self.old.restorePreviousCard();
}
return self.old_partitioner.checkpoint(if (self.old_next) |old| old.card.filename else null);
}
fn next(self: *MergedCursor) Error!?StreamEntry {
self.last_was_old = false;
while (true) {
if (self.old_next == null) self.old_next = try self.old.next();
const patch = if (self.overlay_index < self.overlay.entries.items.len) self.overlay.entries.items[self.overlay_index] else null;
if (self.old_next) |old| {
if (patch) |entry| {
switch (artifact.compareBytes(old.card.filename, entry.path)) {
.lt => {
const retained = try self.consumeOld();
if (!self.overlay.clear) {
self.last_was_old = true;
return retained;
}
},
.gt => {
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
},
.eq => {
_ = try self.consumeOld();
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
},
}
} else {
const retained = try self.consumeOld();
if (!self.overlay.clear) {
self.last_was_old = true;
return retained;
}
}
} else {
if (patch) |entry| {
self.overlay_index += 1;
if (entry.value) |card| return .{ .card = card, .origin = null };
} else return null;
}
}
}
};
const StreamBuild = struct {
root: RootRun,
reused_nodes: usize,
emitted_nodes: usize,
};
const StreamBuilder = struct {
editor_: *TreeEditor,
arena: std.mem.Allocator,
known_nodes: *const std.ArrayList([]const u8),
reused_nodes: usize = 0,
emitted_nodes: usize = 0,
staged: std.ArrayList(PendingArtifact) = .empty,
fn init(editor_: *TreeEditor, arena: std.mem.Allocator, known_nodes: *const std.ArrayList([]const u8)) 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 {
for (self.known_nodes.items) |known_name| if (std.mem.eql(u8, known_name, 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 {
for (self.staged.items) |pending| {
try self.editor_.store.put_fn(self.editor_.store.ctx, pending.name, pending.bytes);
self.emitted_nodes += 1;
}
}
fn emitLeaf(self: *StreamBuilder, group: []const StreamEntry, out: *std.ArrayList(Descriptor)) Error!void {
try out.ensureUnusedCapacity(self.arena, 1);
try self.staged.ensureUnusedCapacity(self.arena, 1);
const cards = try self.arena.alloc(artifact.FCard, group.len);
for (group, cards) |entry, *card| card.* = entry.card;
const bytes = try artifact.serializeSubmanifestLeaf(self.arena, cards);
const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
const already_known = try self.known(name, bytes);
const descriptor: Descriptor = .{
.card = .{ .filename = cards[0].filename, .hash = name },
.origin = if (already_known) name else null,
};
if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
.name = name,
.bytes = bytes,
});
out.appendAssumeCapacity(descriptor);
}
fn emitInterior(self: *StreamBuilder, group: []const Descriptor, out: *std.ArrayList(Descriptor)) Error!void {
try out.ensureUnusedCapacity(self.arena, 1);
try self.staged.ensureUnusedCapacity(self.arena, 1);
const cards = try self.arena.alloc(artifact.SCard, group.len);
for (group, cards) |entry, *card| card.* = entry.card;
const bytes = try artifact.serializeSubmanifestInterior(self.arena, cards);
const name = try nameArtifact(self.arena, self.editor_.format.hash_algo, bytes);
const already_known = try self.known(name, bytes);
const descriptor: Descriptor = .{
.card = .{ .filename = cards[0].filename, .hash = name },
.origin = if (already_known) name else null,
};
if (already_known) self.reused_nodes += 1 else self.staged.appendAssumeCapacity(.{
.name = name,
.bytes = bytes,
});
out.appendAssumeCapacity(descriptor);
}
fn buildUnpublished(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
const span: usize = @as(usize, 1) << self.editor_.format.k;
var partitioner = partition.CanonicalPartitioner.init(self.arena, @as(u16, self.editor_.format.k), span / 4, 4 * span);
defer partitioner.deinit();
var pending: std.ArrayList(StreamEntry) = .empty;
var current: std.ArrayList(StreamEntry) = .empty;
var leaves: std.ArrayList(Descriptor) = .empty;
const prefix_leaves = try merged.old.appendPrefixAtHeight(1, &leaves);
self.reused_nodes += prefix_leaves;
while (try merged.next()) |entry| {
if (try partitioner.push(artifact.zbits(entry.card.filename))) {
if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
pending = current;
current = .empty;
}
try current.append(self.arena, .{
.card = try cloneFCard(self.arena, entry.card),
.origin = if (entry.origin) |name| try self.arena.dupe(u8, name) else null,
});
if (!merged.last_was_old or !merged.old.atLeafEnd()) continue;
const old_checkpoint = (try merged.suffixCheckpoint()) orelse continue;
const next_key = old_checkpoint.next_key orelse continue;
const new_checkpoint = partitioner.checkpoint(next_key);
if (!partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) continue;
if (pending.items.len != 0) try self.emitLeaf(pending.items, &leaves);
try self.emitLeaf(current.items, &leaves);
// suffixCheckpoint prefetched one card from the next leaf. Its
// frame remains live, so hand the old cursor to the level builder
// rather than expanding its entire suffix into leaf descriptors.
merged.old_next = null;
return self.finishCheckpoint(leaves, merged.old);
}
const bounds = try partitioner.finish();
if (bounds.len == 0 or partition.groupCount(bounds) <= 1) {
if (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) },
.reused_nodes = self.reused_nodes,
.emitted_nodes = self.emitted_nodes,
};
}
const final_boundary = partitioner.count - current.items.len;
var keeps_final_boundary = false;
for (bounds[1 .. bounds.len - 1]) |boundary| {
if (boundary == final_boundary) {
keeps_final_boundary = true;
break;
}
}
if (keeps_final_boundary) {
try self.emitLeaf(pending.items, &leaves);
try self.emitLeaf(current.items, &leaves);
} else {
try pending.appendSlice(self.arena, current.items);
try self.emitLeaf(pending.items, &leaves);
}
return self.finishTree(leaves, merged.old);
}
fn build(self: *StreamBuilder, merged: *MergedCursor) Error!StreamBuild {
var result = try self.buildUnpublished(merged);
try self.publishStaged();
result.reused_nodes = self.reused_nodes;
result.emitted_nodes = self.emitted_nodes;
return result;
}
fn finishTree(self: *StreamBuilder, leaves: std.ArrayList(Descriptor), old: *OldTreeCursor) Error!StreamBuild {
var level = leaves;
var height: usize = 1;
while (height < self.editor_.format.height_max) {
const next_height = height + 1;
if (old.takePrefixAtHeight(next_height)) |predecessor_group| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenPrefixGroup(predecessor_group, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level = reopened;
}
var rebuilt: std.ArrayList(Descriptor) = .empty;
if (!try self.buildInteriorLevel(level.items, height, &rebuilt)) {
// A retained ancestor can skip the immediate next height. Walk
// only its rightmost path to recover the direct predecessor
// stream, leaving all earlier siblings native and bounded.
if (old.takePrefixAboveHeight(next_height)) |ancestor| {
var reopened: std.ArrayList(Descriptor) = .empty;
try old.reopenRightmostPrefixAtHeight(ancestor, height, &reopened);
try reopened.appendSlice(self.arena, level.items);
level = reopened;
continue;
}
break;
}
var next: std.ArrayList(Descriptor) = .empty;
const reused = try old.appendPrefixAtHeight(next_height, &next);
self.reused_nodes += reused;
try next.appendSlice(self.arena, rebuilt.items);
level = next;
height = next_height;
}
return .{
.root = .{ .tree = try descriptorCards(self.arena, level.items) },
.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;
}
if (old.hasPrefixAtHeight(height)) {
var prefixed: std.ArrayList(Descriptor) = .empty;
self.reused_nodes += try old.appendPrefixAtHeight(height, &prefixed);
try prefixed.appendSlice(self.arena, level.items);
level.* = prefixed;
}
}
fn finishRootLevel(
self: *StreamBuilder,
level: std.ArrayList(Descriptor),
start_height: usize,
) Error!StreamBuild {
var current = level;
var height = start_height;
while (height < self.editor_.format.height_max) {
var raised: std.ArrayList(Descriptor) = .empty;
if (!try self.buildInteriorLevel(current.items, height, &raised)) break;
current = raised;
height += 1;
}
return .{
.root = .{ .tree = try descriptorCards(self.arena, current.items) },
.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;
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;
const has_parent = try old.appendCheckpointLevel(include_next_leaf, &old_continuation);
self.reused_nodes += old_continuation.items.len;
if (!has_parent) {
const root_height = try old.takeRootCheckpoint();
if (height > root_height) return error.MalformedNode;
try level.appendSlice(self.arena, old_continuation.items);
const suffix_start = level.items.len;
if (height < root_height) {
_ = try old.appendRootSuffixAtHeight(root_height, height, &level);
} else {
try old.appendRootSuffix(&level);
}
self.reused_nodes += level.items.len - suffix_start;
try self.mergeRootPrefixes(old, &level, height);
return self.finishRootLevel(level, height);
}
if (height >= self.editor_.format.height_max) return error.HeightExceeded;
const group_depth = try old.checkpointDepth();
var old_group_start: ?usize = null;
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) {
const root_height = try old.takeRootCheckpoint();
if (height > root_height) return error.MalformedNode;
const suffix_start = old_continuation.items.len;
if (height < root_height) {
_ = try old.appendRootSuffixAtHeight(root_height, height, &old_continuation);
} else {
try old.appendRootSuffix(&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);
}
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;
}
const root_start = level.items.len;
try old.appendRootSuffix(&level);
self.reused_nodes += level.items.len - root_start;
return .{
.root = .{ .tree = try descriptorCards(self.arena, level.items) },
.reused_nodes = self.reused_nodes,
.emitted_nodes = self.emitted_nodes,
};
}
/// Reuse begins only at the start of a complete untouched old canonical
/// group. The initial checkpoint remainder may be mid-group, so it is
/// replayed into the rebuilt state but never treated as old state.
fn findInteriorSplice(
self: *StreamBuilder,
rebuilt: []const Descriptor,
old_continuation: []const Descriptor,
old_group_start: ?usize,
height: usize,
) Error!?usize {
const start = old_group_start orelse return null;
const span: usize = @as(usize, 1) << self.editor_.format.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.k));
const min_members = span / 4;
const max_members = 4 * span;
var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer old_partitioner.deinit();
var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer new_partitioner.deinit();
var equivalent_splices: std.ArrayList(usize) = .empty;
for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[0..start]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[start..], start..) |entry, old_index| {
if (old_partitioner.count != 0 and old_partitioner.bounds.items.len >= 2) {
const open_members = old_partitioner.count - old_partitioner.bounds.items[old_partitioner.bounds.items.len - 1];
const starts_old_group = open_members == max_members or
(artifact.zbits(entry.card.filename) >= threshold and open_members >= min_members);
if (starts_old_group) {
const old_checkpoint = old_partitioner.checkpoint(entry.card.filename);
const new_checkpoint = new_partitioner.checkpoint(entry.card.filename);
if (partition.CanonicalPartitioner.Checkpoint.equivalent(new_checkpoint, old_checkpoint)) {
try equivalent_splices.append(self.arena, old_index);
}
}
}
_ = try old_partitioner.push(artifact.zbits(entry.card.filename));
_ = try new_partitioner.push(artifact.zbits(entry.card.filename));
}
const old_bounds = try old_partitioner.finish();
for (equivalent_splices.items) |candidate| {
for (old_bounds) |bound| {
if (bound == candidate - start) return candidate;
}
}
return null;
}
/// `rebuilt` is the newly emitted continuation. `old_continuation` is
/// independently read from the old descriptor stream. Once both
/// partitioners reach the same checkpoint at an old canonical boundary,
/// the old partitioner owns the remaining suffix rather than replaying it
fn buildInteriorPrefix(
self: *StreamBuilder,
rebuilt: []const Descriptor,
old_continuation: []const Descriptor,
old_group_start: ?usize,
height: usize,
out: *std.ArrayList(Descriptor),
) Error!void {
const span: usize = @as(usize, 1) << self.editor_.format.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.k));
const min_members = span / 4;
const max_members = 4 * span;
const splice_at = try self.findInteriorSplice(rebuilt, old_continuation, old_group_start, height);
if (splice_at) |old_splice| {
const start = old_group_start orelse return error.MalformedNode;
var old_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer old_partitioner.deinit();
for (old_continuation[start..]) |entry| _ = try old_partitioner.push(artifact.zbits(entry.card.filename));
const old_bounds = try old_partitioner.finish();
var new_partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer new_partitioner.deinit();
for (rebuilt) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
for (old_continuation[0..old_splice]) |entry| _ = try new_partitioner.push(artifact.zbits(entry.card.filename));
// The equivalent checkpoint owns the still-open new group. Do not
// call `finish`: its EOF rule would serialize that partial group
// and prevent the old suffix from supplying its canonical tail.
const completed_bounds = new_partitioner.bounds.items;
var rebuilt_start: usize = 0;
for (completed_bounds[1..]) |end| {
if (end <= rebuilt.len) {
try self.emitInterior(rebuilt[rebuilt_start..end], out);
} else if (rebuilt_start >= rebuilt.len) {
try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. end - rebuilt.len], out);
} else {
const members = try self.arena.alloc(Descriptor, end - rebuilt_start);
const rebuilt_members = rebuilt.len - rebuilt_start;
@memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
try self.emitInterior(members, out);
}
rebuilt_start = end;
}
// `old_splice` is the next item at the equivalent checkpoint. The
// partitioner has deliberately not consumed it, so its boundary
// is absent from `bounds`; finalize the preceding canonical group
// explicitly instead of dropping it or serializing the suffix's
// open final group.
const prefix_end = rebuilt.len + old_splice;
if (rebuilt_start != prefix_end) {
if (prefix_end <= rebuilt.len) {
try self.emitInterior(rebuilt[rebuilt_start..prefix_end], out);
} else if (rebuilt_start >= rebuilt.len) {
try self.emitInterior(old_continuation[rebuilt_start - rebuilt.len .. old_splice], out);
} else {
const members = try self.arena.alloc(Descriptor, prefix_end - rebuilt_start);
const rebuilt_members = rebuilt.len - rebuilt_start;
@memcpy(members[0..rebuilt_members], rebuilt[rebuilt_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0..old_splice]);
try self.emitInterior(members, out);
}
}
var old_start = start;
for (old_bounds[1..]) |relative_end| {
const end = start + relative_end;
if (old_start >= old_splice) try self.emitInterior(old_continuation[old_start..end], out);
old_start = end;
}
return;
}
var fallback = partition.CanonicalPartitioner.init(self.arena, threshold, min_members, max_members);
defer fallback.deinit();
for (rebuilt) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
for (old_continuation) |entry| _ = try fallback.push(artifact.zbits(entry.card.filename));
const fallback_bounds = try fallback.finish();
if (fallback_bounds.len < 2) return error.MalformedNode;
var fallback_start: usize = 0;
for (fallback_bounds[1..]) |end| {
if (end <= rebuilt.len) {
try self.emitInterior(rebuilt[fallback_start..end], out);
} else if (fallback_start >= rebuilt.len) {
try self.emitInterior(old_continuation[fallback_start - rebuilt.len .. end - rebuilt.len], out);
} else {
const members = try self.arena.alloc(Descriptor, end - fallback_start);
const rebuilt_members = rebuilt.len - fallback_start;
@memcpy(members[0..rebuilt_members], rebuilt[fallback_start..]);
@memcpy(members[rebuilt_members..], old_continuation[0 .. end - rebuilt.len]);
try self.emitInterior(members, out);
}
fallback_start = end;
}
}
/// a singleton or non-reducing level is returned to its caller unchanged.
fn buildInteriorLevel(self: *StreamBuilder, input: []const Descriptor, height: usize, out: *std.ArrayList(Descriptor)) Error!bool {
const span: usize = @as(usize, 1) << self.editor_.format.k;
const threshold: u16 = @intCast((height + 1) * @as(usize, self.editor_.format.k));
var partitioner = partition.CanonicalPartitioner.init(self.arena, threshold, span / 4, 4 * span);
defer partitioner.deinit();
for (input) |entry| _ = try partitioner.push(artifact.zbits(entry.card.filename));
const bounds = try partitioner.finish();
const count = partition.groupCount(bounds);
if (count <= 1 or count >= input.len) return false;
var start: usize = 0;
for (bounds[1..]) |end| {
try self.emitInterior(input[start..end], out);
start = end;
}
return true;
}
};
fn streamCards(arena: std.mem.Allocator, entries: []const StreamEntry) std.mem.Allocator.Error![]const artifact.FCard {
const cards = try arena.alloc(artifact.FCard, entries.len);
for (entries, cards) |entry, *card| card.* = entry.card;
return cards;
}
fn descriptorCards(arena: std.mem.Allocator, entries: []const Descriptor) std.mem.Allocator.Error![]const artifact.SCard {
const cards = try arena.alloc(artifact.SCard, entries.len);
for (entries, cards) |entry, *card| card.* = entry.card;
return cards;
}
fn lookupFlat(entries: []const artifact.FCard, path: []const u8) ?artifact.FCard {
const index = lowerBound(entries, path);
if (index < entries.len and std.mem.eql(u8, entries[index].filename, path)) return entries[index];
return null;
}
fn childForPath(cards: []const artifact.SCard, path: []const u8) ?artifact.SCard {
var candidate: ?artifact.SCard = null;
for (cards) |card| {
if (artifact.compareBytes(card.filename, path) == .gt) break;
candidate = card;
}
return candidate;
}
/// Index of the direct child that contains `path`, or the first child when the
/// requested path precedes the range. This is a binary seek over S cards, never
/// an F-card walk.
fn childIndexForPath(cards: []const artifact.SCard, path: []const u8) usize {
std.debug.assert(cards.len != 0);
var low: usize = 0;
var high = cards.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (artifact.compareBytes(cards[mid].filename, path) != .gt) low = mid + 1 else high = mid;
}
return if (low == 0) 0 else low - 1;
}
fn lowerBound(entries: []const artifact.FCard, path: []const u8) usize {
var low: usize = 0;
var high = entries.len;
while (low < high) {
const mid = low + (high - low) / 2;
if (artifact.compareBytes(entries[mid].filename, path) == .lt) low = mid + 1 else high = mid;
}
return low;
}
fn nameArtifact(
arena: std.mem.Allocator,
algo: artifact.HashAlgo,
bytes: []const u8,
) std.mem.Allocator.Error![]const u8 {
var scratch: [64]u8 = undefined;
return arena.dupe(u8, artifact.artifactName(algo, bytes, &scratch));
}
fn cloneFCards(arena: std.mem.Allocator, entries: []const artifact.FCard) std.mem.Allocator.Error![]const artifact.FCard {
const copied = try arena.alloc(artifact.FCard, entries.len);
for (entries, copied) |entry, *dest| dest.* = try cloneFCard(arena, entry);
return copied;
}
fn cloneSCards(arena: std.mem.Allocator, cards: []const artifact.SCard) std.mem.Allocator.Error![]const artifact.SCard {
const copied = try arena.alloc(artifact.SCard, cards.len);
for (cards, copied) |card, *dest| dest.* = .{
.filename = try arena.dupe(u8, card.filename),
.hash = try arena.dupe(u8, card.hash),
};
return copied;
}
fn cloneFCard(arena: std.mem.Allocator, value: artifact.FCard) std.mem.Allocator.Error!artifact.FCard {
return .{
.filename = try arena.dupe(u8, value.filename),
.hash = if (value.hash) |hash| try arena.dupe(u8, hash) else null,
.perm = if (value.perm) |perm| try arena.dupe(u8, perm) else null,
.old_name = if (value.old_name) |old| try arena.dupe(u8, old) else null,
.mode = value.mode,
};
}
comptime {
_ = partition.CanonicalPartitioner;
}