const std = @import("std");
const artifact = @import("artifact.zig");
const partition = @import("submanifest_partition.zig");
const editor = @import("submanifest_editor.zig");
fn unavailableLoad(_: *anyopaque, _: std.mem.Allocator, _: []const u8) editor.StoreError!editor.LoadedBytes {
return error.MissingNode;
}
fn unavailablePut(_: *anyopaque, _: []const u8, _: []const u8) editor.StoreError!void {
return error.StorageFailure;
}
const MemoryStore = struct {
const Node = struct {
name: []u8,
bytes: []u8,
};
gpa: std.mem.Allocator,
nodes: std.ArrayList(Node) = .empty,
load_calls: usize = 0,
load_bytes: usize = 0,
put_calls: usize = 0,
fail_load_ordinal: ?usize = null,
fail_put_ordinal: ?usize = null,
fn init(gpa: std.mem.Allocator) MemoryStore {
return .{ .gpa = gpa };
}
fn deinit(self: *MemoryStore) void {
for (self.nodes.items) |node| {
self.gpa.free(node.name);
self.gpa.free(node.bytes);
}
self.nodes.deinit(self.gpa);
self.* = undefined;
}
fn asTreeStore(self: *MemoryStore) editor.TreeStore {
return .{ .ctx = self, .load_fn = load, .put_fn = put };
}
fn borrow(self: *const MemoryStore, name: []const u8) ?[]const u8 {
for (self.nodes.items) |node| {
if (std.mem.eql(u8, node.name, name)) return node.bytes;
}
return null;
}
fn load(ctx: *anyopaque, allocator: std.mem.Allocator, name: []const u8) editor.StoreError!editor.LoadedBytes {
const self: *MemoryStore = @ptrCast(@alignCast(ctx));
self.load_calls += 1;
if (self.fail_load_ordinal) |ordinal| {
if (self.load_calls == ordinal) return error.StorageFailure;
}
const bytes = self.borrow(name) orelse return error.MissingNode;
self.load_bytes += bytes.len;
return .{ .bytes = try allocator.dupe(u8, bytes), .allocator = allocator };
}
fn put(ctx: *anyopaque, name: []const u8, bytes: []const u8) editor.StoreError!void {
const self: *MemoryStore = @ptrCast(@alignCast(ctx));
self.put_calls += 1;
if (self.fail_put_ordinal) |ordinal| {
if (self.put_calls == ordinal) return error.StorageFailure;
}
for (self.nodes.items) |node| {
if (std.mem.eql(u8, node.name, name)) {
if (!std.mem.eql(u8, node.bytes, bytes)) return error.StorageFailure;
return;
}
}
const owned_name = try self.gpa.dupe(u8, name);
errdefer self.gpa.free(owned_name);
const owned_bytes = try self.gpa.dupe(u8, bytes);
errdefer self.gpa.free(owned_bytes);
try self.nodes.append(self.gpa, .{ .name = owned_name, .bytes = owned_bytes });
}
fn seed(self: *MemoryStore, build: *const artifact.TreeBuild) editor.StoreError!void {
for (build.subs) |sub| try put(self, sub.name, sub.bytes);
}
};
const EntrySet = struct {
cards: []artifact.FCard,
fn init(allocator: std.mem.Allocator, count: usize) !EntrySet {
const cards = try allocator.alloc(artifact.FCard, count);
var initialized: usize = 0;
errdefer {
for (cards[0..initialized]) |card| allocator.free(card.filename);
allocator.free(cards);
}
for (cards, 0..) |*card, index| {
card.* = .{
.filename = try std.fmt.allocPrint(allocator, "p{d:0>8}.c", .{index}),
.hash = "0123456789012345678901234567890123456789",
.perm = null,
.old_name = null,
.mode = .regular,
};
initialized += 1;
}
return .{ .cards = cards };
}
fn deinit(self: *EntrySet, allocator: std.mem.Allocator) void {
for (self.cards) |card| allocator.free(card.filename);
allocator.free(self.cards);
self.* = undefined;
}
};
fn maxOnlyEntrySet(allocator: std.mem.Allocator, count: usize) !EntrySet {
const cards = try allocator.alloc(artifact.FCard, count);
var initialized: usize = 0;
errdefer {
for (cards[0..initialized]) |card| allocator.free(card.filename);
allocator.free(cards);
}
var candidate: usize = 0;
while (initialized < cards.len) : (candidate += 1) {
const filename = try std.fmt.allocPrint(allocator, "m{d:0>12}.c", .{candidate});
if (artifact.zbits(filename) != 1) {
allocator.free(filename);
continue;
}
cards[initialized] = .{
.filename = filename,
.hash = "0123456789012345678901234567890123456789",
.perm = null,
.old_name = null,
.mode = .regular,
};
initialized += 1;
}
return .{ .cards = cards };
}
fn rootView(root: editor.RootRun) editor.RootView {
return switch (root) {
.flat => |cards| .{ .flat = cards },
.tree => |cards| .{ .tree = cards },
};
}
fn buildRoot(build: *const artifact.TreeBuild, entries: []const artifact.FCard) editor.RootView {
return if (build.isFlat()) .{ .flat = entries } else .{ .tree = build.s };
}
fn buildRun(build: *const artifact.TreeBuild, entries: []const artifact.FCard) editor.RootRun {
return if (build.isFlat()) .{ .flat = entries } else .{ .tree = build.s };
}
fn rootDepth(store: *const MemoryStore, root: editor.RootRun) !usize {
var name = switch (root) {
.flat => return 0,
.tree => |cards| blk: {
if (cards.len == 0) return 0;
break :blk cards[0].hash;
},
};
var depth: usize = 0;
while (true) {
const bytes = store.borrow(name) orelse return error.MissingNode;
var manifest = try artifact.parse(std.testing.allocator, bytes);
defer manifest.deinit();
depth += 1;
if (manifest.f.len != 0) return depth;
if (manifest.s.len == 0) return error.TestUnexpectedResult;
name = manifest.s[0].hash;
}
}
fn treeBuildDepth(build: *const artifact.TreeBuild) !usize {
if (build.isFlat()) return 0;
var name = build.s[0].hash;
var depth: usize = 0;
while (true) {
const bytes = for (build.subs) |sub| {
if (std.mem.eql(u8, sub.name, name)) break sub.bytes;
} else return error.MissingNode;
var manifest = try artifact.parse(std.testing.allocator, bytes);
defer manifest.deinit();
depth += 1;
if (manifest.f.len != 0) return depth;
if (manifest.s.len == 0) return error.TestUnexpectedResult;
name = manifest.s[0].hash;
}
}
fn expectModel(tree_editor: *editor.TreeEditor, root: editor.RootRun, entries: []const artifact.FCard, present: []const bool) !void {
for (entries, present) |entry, expected| {
const actual = try tree_editor.lookup(rootView(root), entry.filename);
try std.testing.expectEqual(expected, actual != null);
if (actual) |card| try std.testing.expectEqualStrings(entry.filename, card.filename);
}
}
fn expectOptionalString(expected: ?[]const u8, actual: ?[]const u8) !void {
if (expected) |value| {
try std.testing.expect(actual != null);
try std.testing.expectEqualStrings(value, actual.?);
} else try std.testing.expect(actual == null);
}
fn expectFCard(expected: artifact.FCard, actual: artifact.FCard) !void {
try std.testing.expectEqualStrings(expected.filename, actual.filename);
try expectOptionalString(expected.hash, actual.hash);
try expectOptionalString(expected.perm, actual.perm);
try expectOptionalString(expected.old_name, actual.old_name);
try std.testing.expectEqual(expected.mode, actual.mode);
}
fn expectSCards(expected: []const artifact.SCard, actual: []const artifact.SCard) !void {
try std.testing.expectEqual(expected.len, actual.len);
for (expected, actual) |expected_card, actual_card| {
try std.testing.expectEqualStrings(expected_card.filename, actual_card.filename);
try std.testing.expectEqualStrings(expected_card.hash, actual_card.hash);
}
}
fn expectedEntries(
allocator: std.mem.Allocator,
entries: []const artifact.FCard,
present: []const bool,
) ![]artifact.FCard {
var count: usize = 0;
for (present) |value| {
if (value) count += 1;
}
const selected = try allocator.alloc(artifact.FCard, count);
var index: usize = 0;
for (entries, present) |card, value| {
if (!value) continue;
selected[index] = card;
index += 1;
}
return selected;
}
fn expectedSubIndex(build: *const artifact.TreeBuild, name: []const u8) ?usize {
for (build.subs, 0..) |sub, index| {
if (std.mem.eql(u8, sub.name, name)) return index;
}
return null;
}
fn expectReachableSubArtifacts(
store: *const MemoryStore,
build: *const artifact.TreeBuild,
name: []const u8,
seen: []bool,
) !void {
const index = expectedSubIndex(build, name) orelse return error.TestUnexpectedResult;
try std.testing.expect(!seen[index]);
seen[index] = true;
const bytes = store.borrow(name) orelse return error.MissingNode;
try std.testing.expectEqualSlices(u8, build.subs[index].bytes, bytes);
var manifest = try artifact.parse(std.testing.allocator, bytes);
defer manifest.deinit();
if (manifest.f.len != 0) return;
if (manifest.s.len == 0) return error.TestUnexpectedResult;
for (manifest.s) |card| try expectReachableSubArtifacts(store, build, card.hash, seen);
}
fn expectExactBatch(
store: *const MemoryStore,
root: editor.RootRun,
entries: []const artifact.FCard,
build: *const artifact.TreeBuild,
) !void {
switch (root) {
.flat => |actual| {
try std.testing.expect(build.isFlat());
try std.testing.expectEqual(entries.len, actual.len);
for (entries, actual) |expected_card, actual_card| try expectFCard(expected_card, actual_card);
},
.tree => |actual| {
try std.testing.expect(!build.isFlat());
try expectSCards(build.s, actual);
},
}
const seen = try std.testing.allocator.alloc(bool, build.subs.len);
defer std.testing.allocator.free(seen);
@memset(seen, false);
switch (root) {
.flat => try std.testing.expectEqual(@as(usize, 0), build.subs.len),
.tree => |cards| for (cards) |card| try expectReachableSubArtifacts(store, build, card.hash, seen),
}
for (seen) |value| try std.testing.expect(value);
}
fn expectNewArtifactsMatch(
store: *const MemoryStore,
initial_count: usize,
build: *const artifact.TreeBuild,
) !void {
for (store.nodes.items[initial_count..]) |node| {
const index = expectedSubIndex(build, node.name) orelse return error.TestUnexpectedResult;
try std.testing.expectEqualSlices(u8, build.subs[index].bytes, node.bytes);
}
}
fn firstPresent(present: []const bool, start: usize) ?usize {
for (0..present.len) |offset| {
const index = (start + offset) % present.len;
if (present[index]) return index;
}
return null;
}
fn firstAbsent(present: []const bool, start: usize) ?usize {
for (0..present.len) |offset| {
const index = (start + offset) % present.len;
if (!present[index]) return index;
}
return null;
}
fn nextRandom(state: *u64) u32 {
state.* = state.* *% 6364136223846793005 +% 1442695040888963407;
return @truncate(state.* >> 32);
}
fn nextDifferentialCommand(
entries: []const artifact.FCard,
present: []bool,
state: *u64,
) editor.TreeCommand {
const index = @as(usize, nextRandom(state)) % entries.len;
return switch (nextRandom(state) % 5) {
0 => blk: {
present[index] = true;
break :blk .{ .upsert = entries[index] };
},
1 => if (firstPresent(present, index)) |source| blk: {
present[source] = false;
break :blk .{ .delete = entries[source].filename };
} else blk: {
present[index] = true;
break :blk .{ .upsert = entries[index] };
},
2 => if (firstPresent(present, index)) |source| {
if (firstAbsent(present, index + 1)) |destination| {
present[source] = false;
present[destination] = true;
return .{ .rename = .{
.old = entries[source].filename,
.new = entries[destination].filename,
} };
}
present[index] = true;
return .{ .upsert = entries[index] };
} else blk: {
present[index] = true;
break :blk .{ .upsert = entries[index] };
},
3 => if (firstPresent(present, index)) |source| {
if (firstAbsent(present, index + 1)) |destination| {
present[destination] = true;
return .{ .copy = .{
.old = entries[source].filename,
.new = entries[destination].filename,
} };
}
present[index] = true;
return .{ .upsert = entries[index] };
} else blk: {
present[index] = true;
break :blk .{ .upsert = entries[index] };
},
else => blk: {
@memset(present, false);
break :blk .delete_all;
},
};
}
fn randomDifferential(k: u4) !void {
const gpa = std.testing.allocator;
const domain = 128;
const initial = 64;
var entries = try EntrySet.init(gpa, domain);
defer entries.deinit(gpa);
var store = MemoryStore.init(gpa);
defer store.deinit();
var batch = try artifact.buildTree(gpa, entries.cards[0..initial], k, .sha1);
defer batch.deinit();
try store.seed(&batch);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
4096,
);
defer tree_editor.deinit();
var current = try tree_editor.apply(buildRoot(&batch, entries.cards[0..initial]), &.{});
defer current.deinit();
var present = [_]bool{false} ** domain;
for (0..initial) |index| present[index] = true;
try expectExactBatch(&store, current.root, entries.cards[0..initial], &batch);
var seed: u64 = 0xD1FF_EA5E_0016_0001;
var command_kinds_seen = [_]bool{false} ** 5;
for (1..65) |command_count| {
var commands: [64]editor.TreeCommand = undefined;
for (commands[0..command_count]) |*command| {
command.* = nextDifferentialCommand(entries.cards, present[0..], &seed);
switch (command.*) {
.upsert => command_kinds_seen[0] = true,
.delete => command_kinds_seen[1] = true,
.rename => command_kinds_seen[2] = true,
.copy => command_kinds_seen[3] = true,
.delete_all => command_kinds_seen[4] = true,
}
}
const nodes_before = store.nodes.items.len;
var next = try tree_editor.apply(rootView(current.root), commands[0..command_count]);
errdefer next.deinit();
try expectModel(&tree_editor, next.root, entries.cards, present[0..]);
const selected = try expectedEntries(gpa, entries.cards, present[0..]);
defer gpa.free(selected);
var expected = try artifact.buildTree(gpa, selected, k, .sha1);
defer expected.deinit();
try expectExactBatch(&store, next.root, selected, &expected);
try expectNewArtifactsMatch(&store, nodes_before, &expected);
current.deinit();
current = next;
}
for (command_kinds_seen) |seen| try std.testing.expect(seen);
}
fn allocationFailureRun(allocator: std.mem.Allocator) !void {
const fixture_allocator = std.testing.allocator;
const initial = 64;
const target = 96;
var entries = try EntrySet.init(fixture_allocator, target);
defer entries.deinit(fixture_allocator);
var parent = try artifact.buildTree(fixture_allocator, entries.cards[0..initial], 1, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(fixture_allocator, entries.cards[0..target], 1, .sha1);
defer expected.deinit();
var store = MemoryStore.init(fixture_allocator);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = editor.TreeEditor.init(
allocator,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
) catch |err| {
if (err == error.OutOfMemory) {
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
try expectExactBatch(&store, buildRun(&parent, entries.cards[0..initial]), entries.cards[0..initial], &parent);
}
return err;
};
defer tree_editor.deinit();
var commands: [target - initial]editor.TreeCommand = undefined;
for (entries.cards[initial..target], commands[0..]) |card, *command| command.* = .{ .upsert = card };
var result = tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), commands[0..]) catch |err| {
if (err != error.OutOfMemory) return err;
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
try expectExactBatch(&store, buildRun(&parent, entries.cards[0..initial]), entries.cards[0..initial], &parent);
var retried = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), commands[0..]);
defer retried.deinit();
try expectExactBatch(&store, retried.root, entries.cards[0..target], &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
return error.OutOfMemory;
};
defer result.deinit();
try expectExactBatch(&store, result.root, entries.cards[0..target], &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
// Pins the final-short merge in the one module both batch and editor import.
test "submanifest editor partitioner owns final short merge" {
var p = partition.CanonicalPartitioner.init(std.testing.allocator, 2, 2, 8);
_ = try p.push(0);
_ = try p.push(0);
_ = try p.push(0);
_ = try p.push(2);
const checkpoint = p.checkpoint(null);
try std.testing.expect(checkpoint.final_merge_pending);
const groups = try p.finish();
defer std.testing.allocator.free(groups);
try std.testing.expectEqualSlices(usize, &.{ 0, 4 }, groups);
}
test "submanifest editor applies Git-independent upserts transactionally" {
var state: u8 = 0;
var tree_editor = try editor.TreeEditor.init(
std.testing.allocator,
.{ .ctx = &state, .load_fn = unavailableLoad, .put_fn = unavailablePut },
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var result = try tree_editor.apply(.{ .flat = &.{} }, &.{.{ .upsert = .{
.filename = "a",
.hash = "0123456789012345678901234567890123456789",
.perm = null,
.old_name = null,
.mode = .regular,
} }});
defer result.deinit();
switch (result.root) {
.flat => |entries| {
try std.testing.expectEqual(@as(usize, 1), entries.len);
try std.testing.expectEqualStrings("a", entries[0].filename);
},
.tree => return error.TestUnexpectedResult,
}
}
test "submanifest editor fixed-seed differential sequences cover every supported k" {
inline for (1..13) |raw_k| {
try randomDifferential(@intCast(raw_k));
}
}
test "submanifest editor ordered multi-command transactions match batch trees" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 96);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards[0..64], 1, .sha1);
defer parent.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
4096,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..64]), &.{});
defer root.deinit();
const first_commands = [_]editor.TreeCommand{
.{ .upsert = entries.cards[64] },
.{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[65].filename } },
.{ .copy = .{ .old = entries.cards[1].filename, .new = entries.cards[66].filename } },
.{ .delete = entries.cards[2].filename },
.{ .rename = .{ .old = entries.cards[65].filename, .new = entries.cards[67].filename } },
.{ .delete = entries.cards[64].filename },
};
const first_nodes_before = store.nodes.items.len;
var first = try tree_editor.apply(rootView(root.root), &first_commands);
defer first.deinit();
var first_present = [_]bool{false} ** 96;
@memset(first_present[0..64], true);
first_present[0] = false;
first_present[2] = false;
first_present[66] = true;
first_present[67] = true;
const first_entries = try expectedEntries(gpa, entries.cards, first_present[0..]);
defer gpa.free(first_entries);
var first_batch = try artifact.buildTree(gpa, first_entries, 1, .sha1);
defer first_batch.deinit();
try expectExactBatch(&store, first.root, first_entries, &first_batch);
try expectNewArtifactsMatch(&store, first_nodes_before, &first_batch);
const second_commands = [_]editor.TreeCommand{
.delete_all,
.{ .upsert = entries.cards[70] },
.{ .rename = .{ .old = entries.cards[70].filename, .new = entries.cards[72].filename } },
.{ .copy = .{ .old = entries.cards[72].filename, .new = entries.cards[73].filename } },
};
const second_nodes_before = store.nodes.items.len;
var second = try tree_editor.apply(rootView(first.root), &second_commands);
defer second.deinit();
var second_present = [_]bool{false} ** 96;
second_present[72] = true;
second_present[73] = true;
const second_entries = try expectedEntries(gpa, entries.cards, second_present[0..]);
defer gpa.free(second_entries);
var second_batch = try artifact.buildTree(gpa, second_entries, 1, .sha1);
defer second_batch.deinit();
try expectExactBatch(&store, second.root, second_entries, &second_batch);
try expectNewArtifactsMatch(&store, second_nodes_before, &second_batch);
}
test "submanifest editor flat no-op has no reused nodes" {
var entries = try EntrySet.init(std.testing.allocator, 1);
defer entries.deinit(std.testing.allocator);
var state: u8 = 0;
var tree_editor = try editor.TreeEditor.init(
std.testing.allocator,
.{ .ctx = &state, .load_fn = unavailableLoad, .put_fn = unavailablePut },
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var result = try tree_editor.apply(.{ .flat = entries.cards }, &.{});
defer result.deinit();
try std.testing.expectEqual(@as(usize, 0), result.changed_paths);
try std.testing.expectEqual(@as(usize, 0), result.reused_nodes);
try std.testing.expectEqual(@as(usize, 0), result.emitted_nodes);
switch (result.root) {
.flat => |cards| try expectFCard(entries.cards[0], cards[0]),
.tree => return error.TestUnexpectedResult,
}
}
test "submanifest editor cache budgets control decoder allocator reuse" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 80);
defer entries.deinit(gpa);
var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer batch.deinit();
try std.testing.expect(!batch.isFlat());
const full_budget: usize = 1 << 20;
const budgets = [_]usize{ 0, 1, full_budget };
for (budgets, 0..) |budget, budget_index| {
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&batch);
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
budget,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{});
defer root.deinit();
_ = try tree_editor.lookup(rootView(root.root), entries.cards[0].filename);
const first_load_calls = store.load_calls;
const first_load_bytes = store.load_bytes;
try std.testing.expect(first_load_calls != 0);
try std.testing.expect(first_load_bytes != 0);
_ = try tree_editor.lookup(rootView(root.root), entries.cards[0].filename);
if (budget_index < 2) {
try std.testing.expectEqual(first_load_calls * 2, store.load_calls);
try std.testing.expectEqual(first_load_bytes * 2, store.load_bytes);
try std.testing.expectEqual(@as(usize, 0), tree_editor.cacheHighWater());
} else {
try std.testing.expectEqual(first_load_calls, store.load_calls);
try std.testing.expectEqual(first_load_bytes, store.load_bytes);
try std.testing.expect(tree_editor.cacheHighWater() != 0);
try std.testing.expect(tree_editor.cacheHighWater() <= full_budget);
}
}
}
test "submanifest editor splits, merges, grows, and shrinks constructible roots" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 384);
defer entries.deinit(gpa);
var prior_height: usize = 0;
var growth_from: usize = 0;
var growth_to: usize = 0;
for (1..entries.cards.len + 1) |count| {
var build = try artifact.buildTree(gpa, entries.cards[0..count], 1, .sha1);
errdefer build.deinit();
const height = try treeBuildDepth(&build);
build.deinit();
if (prior_height >= 2 and height > prior_height) {
growth_from = count - 1;
growth_to = count;
break;
}
prior_height = height;
}
try std.testing.expect(growth_from != 0);
try std.testing.expect(growth_to != 0);
var store = MemoryStore.init(gpa);
defer store.deinit();
var parent = try artifact.buildTree(gpa, entries.cards[0..growth_from], 1, .sha1);
defer parent.deinit();
try store.seed(&parent);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
4096,
);
defer tree_editor.deinit();
var before = try tree_editor.apply(buildRoot(&parent, entries.cards[0..growth_from]), &.{});
defer before.deinit();
const before_depth = try rootDepth(&store, before.root);
try std.testing.expect(before_depth >= 2);
var grown = try tree_editor.apply(rootView(before.root), &.{.{ .upsert = entries.cards[growth_to - 1] }});
defer grown.deinit();
const grown_depth = try rootDepth(&store, grown.root);
try std.testing.expect(grown.emitted_nodes != 0);
try std.testing.expect(grown_depth > before_depth);
try std.testing.expect((try tree_editor.lookup(rootView(grown.root), entries.cards[growth_to - 1].filename)) != null);
var expected_grown = try artifact.buildTree(gpa, entries.cards[0..growth_to], 1, .sha1);
defer expected_grown.deinit();
try expectExactBatch(&store, grown.root, entries.cards[0..growth_to], &expected_grown);
var shrunk = try tree_editor.apply(rootView(grown.root), &.{.{ .delete = entries.cards[growth_to - 1].filename }});
defer shrunk.deinit();
const shrunk_depth = try rootDepth(&store, shrunk.root);
// The delete reconstructs the already-stored parent shape byte-for-byte;
// correct canonical reuse therefore emits no new artifact.
try std.testing.expectEqual(@as(usize, 0), shrunk.emitted_nodes);
try std.testing.expect(shrunk.reused_nodes != 0);
try std.testing.expect(shrunk_depth < grown_depth);
try std.testing.expectEqual(before_depth, shrunk_depth);
var expected_present: [384]bool = undefined;
@memset(expected_present[0..], false);
@memset(expected_present[0..growth_from], true);
try expectModel(&tree_editor, shrunk.root, entries.cards, expected_present[0..]);
try std.testing.expect((try tree_editor.lookup(rootView(shrunk.root), entries.cards[growth_to - 1].filename)) == null);
try expectExactBatch(&store, shrunk.root, entries.cards[0..growth_from], &parent);
}
test "submanifest editor preserves MAX-only sparse early root transitions" {
const gpa = std.testing.allocator;
var entries = try maxOnlyEntrySet(gpa, 513);
defer entries.deinit(gpa);
for (entries.cards) |entry| try std.testing.expectEqual(@as(u16, 1), artifact.zbits(entry.filename));
const parent_entries = try gpa.alloc(artifact.FCard, 512);
defer gpa.free(parent_entries);
@memcpy(parent_entries[0..1], entries.cards[0..1]);
@memcpy(parent_entries[1..], entries.cards[2..]);
var parent = try artifact.buildTree(gpa, parent_entries, 1, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer expected.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var grown = try tree_editor.apply(buildRoot(&parent, parent_entries), &.{.{ .upsert = entries.cards[1] }});
defer grown.deinit();
try std.testing.expectEqual(@as(usize, 3), try rootDepth(&store, buildRun(&parent, parent_entries)));
try std.testing.expectEqual(@as(usize, 4), try rootDepth(&store, grown.root));
try expectExactBatch(&store, grown.root, entries.cards, &expected);
var shrunk = try tree_editor.apply(rootView(grown.root), &.{.{ .delete = entries.cards[1].filename }});
defer shrunk.deinit();
try std.testing.expectEqual(@as(usize, 3), try rootDepth(&store, shrunk.root));
try expectExactBatch(&store, shrunk.root, parent_entries, &parent);
}
test "submanifest editor every put failure preserves immutable parent and retries" {
const gpa = std.testing.allocator;
const initial = 64;
const target = 96;
var entries = try EntrySet.init(gpa, target);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards[0..initial], 1, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, entries.cards[0..target], 1, .sha1);
defer expected.deinit();
const commands = try gpa.alloc(editor.TreeCommand, target - initial);
defer gpa.free(commands);
for (entries.cards[initial..target], commands) |card, *command| command.* = .{ .upsert = card };
var successful_store = MemoryStore.init(gpa);
defer successful_store.deinit();
try successful_store.seed(&parent);
const successful_immutable_nodes = successful_store.nodes.items.len;
successful_store.put_calls = 0;
var successful_editor = try editor.TreeEditor.init(
gpa,
successful_store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer successful_editor.deinit();
var successful_parent = try successful_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{});
defer successful_parent.deinit();
var successful = try successful_editor.apply(rootView(successful_parent.root), commands);
defer successful.deinit();
try std.testing.expect(successful.emitted_nodes != 0);
try expectExactBatch(&successful_store, successful.root, entries.cards[0..target], &expected);
try expectNewArtifactsMatch(&successful_store, successful_immutable_nodes, &expected);
for (0..successful.emitted_nodes) |failure_index| {
const ordinal = failure_index + 1;
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
store.fail_put_ordinal = ordinal;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{});
defer parent_root.deinit();
try std.testing.expectError(error.StorageFailure, tree_editor.apply(rootView(parent_root.root), commands));
try std.testing.expectEqual(ordinal, store.put_calls);
try std.testing.expectEqual(immutable_nodes + failure_index, store.nodes.items.len);
try expectExactBatch(&store, parent_root.root, entries.cards[0..initial], &parent);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
store.fail_put_ordinal = null;
store.put_calls = 0;
var retried = try tree_editor.apply(rootView(parent_root.root), commands);
defer retried.deinit();
try std.testing.expectEqual(successful.emitted_nodes - failure_index, retried.emitted_nodes);
try std.testing.expectEqual(immutable_nodes + successful.emitted_nodes, store.nodes.items.len);
try expectExactBatch(&store, retried.root, entries.cards[0..target], &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
}
test "submanifest editor propagates every allocation failure" {
try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationFailureRun, .{});
}
fn runCanonicalBoundaryTransition(k: u4, count: usize, pad_width: u8) !void {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, count);
defer entries.deinit(gpa);
for (entries.cards, 0..) |*card, index| {
gpa.free(card.filename);
card.filename = try std.fmt.allocPrint(gpa, "q{d:0>6}.c", .{index});
}
_ = pad_width;
var parent = try artifact.buildTree(gpa, entries.cards[0 .. count - 1], k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, entries.cards, k, .sha1);
defer expected.deinit();
try std.testing.expect(!expected.isFlat());
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards[0 .. count - 1]), &.{});
defer parent_root.deinit();
var next = try tree_editor.apply(rootView(parent_root.root), &.{.{ .upsert = entries.cards[count - 1] }});
defer next.deinit();
try expectExactBatch(&store, next.root, entries.cards, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
fn finalShortTreeCount(entries: []const artifact.FCard, k: u4, minimum_groups: usize) !usize {
const span: usize = @as(usize, 1) << k;
const min = span / 4;
const max = 4 * span;
for (1..entries.len + 1) |candidate| {
var partitioner = partition.CanonicalPartitioner.init(std.testing.allocator, k, min, max);
for (entries[0..candidate]) |card| _ = try partitioner.push(artifact.zbits(card.filename));
const checkpoint = partitioner.checkpoint(null);
const bounds = try partitioner.finish();
defer std.testing.allocator.free(bounds);
if (checkpoint.final_merge_pending and bounds.len >= minimum_groups + 1) return candidate;
}
return error.TestUnexpectedResult;
}
test "submanifest editor preserves canonical MIN and MAX k forced boundaries" {
const min_count = 4 * (@as(usize, 1) << artifact.min_k) + 1;
const max_count = 4 * (@as(usize, 1) << artifact.max_k) + 1;
try runCanonicalBoundaryTransition(artifact.min_k, min_count, 6);
try runCanonicalBoundaryTransition(artifact.max_k, max_count, 6);
}
test "submanifest editor matches a final-short leaf merge" {
const gpa = std.testing.allocator;
const k: u4 = 4;
var entries = try EntrySet.init(gpa, 512);
defer entries.deinit(gpa);
const count = try finalShortTreeCount(entries.cards, k, 2);
var expected = try artifact.buildTree(gpa, entries.cards[0..count], k, .sha1);
defer expected.deinit();
try std.testing.expect(!expected.isFlat());
try std.testing.expect(expected.s.len >= 2);
var store = MemoryStore.init(gpa);
defer store.deinit();
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
const commands = try gpa.alloc(editor.TreeCommand, count);
defer gpa.free(commands);
for (entries.cards[0..count], commands) |card, *command| command.* = .{ .upsert = card };
var result = try tree_editor.apply(.{ .flat = &.{} }, commands);
defer result.deinit();
try expectExactBatch(&store, result.root, entries.cards[0..count], &expected);
}
test "submanifest editor rejects duplicate destinations and absent sources without writes" {
const gpa = std.testing.allocator;
const initial = 64;
var entries = try EntrySet.init(gpa, initial + 2);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards[0..initial], 1, .sha1);
defer parent.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{});
defer root.deinit();
try std.testing.expectError(error.DuplicatePath, tree_editor.apply(rootView(root.root), &.{.{ .copy = .{
.old = entries.cards[0].filename,
.new = entries.cards[1].filename,
} }}));
try std.testing.expectError(error.MissingPath, tree_editor.apply(rootView(root.root), &.{.{ .delete = entries.cards[initial].filename }}));
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
try expectExactBatch(&store, root.root, entries.cards[0..initial], &parent);
var expected = try artifact.buildTree(gpa, entries.cards[0 .. initial + 1], 1, .sha1);
defer expected.deinit();
var retried = try tree_editor.apply(rootView(root.root), &.{.{ .upsert = entries.cards[initial] }});
defer retried.deinit();
try expectExactBatch(&store, retried.root, entries.cards[0 .. initial + 1], &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
test "submanifest editor gives rename cycles and chains net-path overlay semantics" {
const gpa = std.testing.allocator;
const initial = 64;
var entries = try EntrySet.init(gpa, initial + 2);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards[0..initial], 1, .sha1);
defer parent.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{});
defer root.deinit();
const cycle = [_]editor.TreeCommand{
.{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[initial].filename } },
.{ .rename = .{ .old = entries.cards[initial].filename, .new = entries.cards[0].filename } },
};
var cycled = try tree_editor.apply(rootView(root.root), &cycle);
defer cycled.deinit();
try std.testing.expectEqual(@as(usize, 0), cycled.changed_paths);
try std.testing.expectEqual(@as(usize, 0), cycled.emitted_nodes);
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try expectExactBatch(&store, cycled.root, entries.cards[0..initial], &parent);
const chain = [_]editor.TreeCommand{
.{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[initial].filename } },
.{ .rename = .{ .old = entries.cards[initial].filename, .new = entries.cards[initial + 1].filename } },
};
var expected_present = [_]bool{false} ** (initial + 2);
@memset(expected_present[0..initial], true);
expected_present[0] = false;
expected_present[initial + 1] = true;
const expected_entries = try expectedEntries(gpa, entries.cards, expected_present[0..]);
defer gpa.free(expected_entries);
var expected = try artifact.buildTree(gpa, expected_entries, 1, .sha1);
defer expected.deinit();
var chained = try tree_editor.apply(rootView(cycled.root), &chain);
defer chained.deinit();
try expectExactBatch(&store, chained.root, expected_entries, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
const CanonicalCount = enum {
min_minus_one,
min,
max_minus_one,
max,
natural,
final_short,
};
fn naturalTreeCount(entries: []const artifact.FCard, k: u4) !usize {
const span: usize = @as(usize, 1) << k;
const min = span / 4;
const max = 4 * span;
for (min..max) |candidate| {
var partitioner = partition.CanonicalPartitioner.init(std.testing.allocator, k, min, max);
for (entries[0..candidate]) |card| _ = try partitioner.push(artifact.zbits(card.filename));
const checkpoint = partitioner.checkpoint(null);
const bounds = try partitioner.finish();
defer std.testing.allocator.free(bounds);
if (!checkpoint.final_merge_pending and bounds.len == 3) return candidate;
}
return error.TestUnexpectedResult;
}
fn applyCanonicalCount(
k: u4,
entries: []const artifact.FCard,
count: usize,
) !void {
const gpa = std.testing.allocator;
const parent_count = if (count == 0) 0 else count - 1;
var parent = try artifact.buildTree(gpa, entries[0..parent_count], k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, entries[0..count], k, .sha1);
defer expected.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries[0..parent_count]), &.{});
defer parent_root.deinit();
var next = if (count == 0)
try tree_editor.apply(rootView(parent_root.root), &.{})
else
try tree_editor.apply(rootView(parent_root.root), &.{.{ .upsert = entries[count - 1] }});
defer next.deinit();
try expectExactBatch(&store, next.root, entries[0..count], &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
test "submanifest editor preserves every canonical MIN MAX natural and final partition boundary" {
inline for (artifact.min_k..artifact.max_k + 1) |raw_k| {
const k: u4 = @intCast(raw_k);
const span: usize = @as(usize, 1) << k;
const min = @max(span / 4, 1);
const max = 4 * span;
var entries = try EntrySet.init(std.testing.allocator, 4 * max);
defer entries.deinit(std.testing.allocator);
// For k=1 and k=2, the RFC MIN is 0 or 1, so a non-empty final
// group cannot be shorter than MIN. The empty case pins that edge.
const final_short_count = if (span / 4 <= 1)
0
else
try finalShortTreeCount(entries.cards, k, 1);
const counts = [_]struct { CanonicalCount, usize }{
.{ .min_minus_one, min - 1 },
.{ .min, min },
.{ .max_minus_one, max - 1 },
.{ .max, max },
.{ .natural, try naturalTreeCount(entries.cards, k) },
.{ .final_short, final_short_count },
};
for (counts) |case| {
switch (case[0]) {
.min_minus_one, .min, .max_minus_one, .max, .natural, .final_short => {},
}
try applyCanonicalCount(k, entries.cards, case[1]);
}
}
}
fn lookupMatrixIndex(position: usize, count: usize) usize {
return switch (position) {
0 => 0,
1 => count / 2,
2 => count - 1,
else => unreachable,
};
}
test "submanifest editor observes decoded cache budgets for first middle and last lookups" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 80);
defer entries.deinit(gpa);
var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer batch.deinit();
try std.testing.expect(!batch.isFlat());
const full_budget: usize = 1 << 20;
const budgets = [_]usize{ 0, 1, full_budget };
for (budgets) |budget| {
for (0..3) |position| {
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&batch);
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
budget,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{});
defer root.deinit();
const index = lookupMatrixIndex(position, entries.cards.len);
const calls_before = store.load_calls;
const bytes_before = store.load_bytes;
try std.testing.expect((try tree_editor.lookup(rootView(root.root), entries.cards[index].filename)) != null);
const decoded_calls = store.load_calls - calls_before;
const decoded_bytes = store.load_bytes - bytes_before;
try std.testing.expect(decoded_calls != 0);
try std.testing.expect(decoded_bytes != 0);
try std.testing.expect((try tree_editor.lookup(rootView(root.root), entries.cards[index].filename)) != null);
if (budget < decoded_bytes) {
try std.testing.expectEqual(calls_before + 2 * decoded_calls, store.load_calls);
try std.testing.expectEqual(bytes_before + 2 * decoded_bytes, store.load_bytes);
try std.testing.expectEqual(@as(usize, 0), tree_editor.cacheHighWater());
} else {
try std.testing.expectEqual(calls_before + decoded_calls, store.load_calls);
try std.testing.expectEqual(bytes_before + decoded_bytes, store.load_bytes);
try std.testing.expect(tree_editor.cacheHighWater() != 0);
try std.testing.expect(tree_editor.cacheHighWater() <= budget);
}
}
}
}
test "submanifest editor distinguishes lookup storage and missing-node faults across decoded budgets" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 80);
defer entries.deinit(gpa);
var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer batch.deinit();
try std.testing.expect(!batch.isFlat());
const budgets = [_]usize{ 0, 1, 1 << 20 };
for (budgets) |budget| {
for (0..3) |position| {
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&batch);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
budget,
);
defer tree_editor.deinit();
var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{});
defer root.deinit();
const index = lookupMatrixIndex(position, entries.cards.len);
store.fail_load_ordinal = store.load_calls + 1;
try std.testing.expectError(
error.StorageFailure,
tree_editor.lookup(rootView(root.root), entries.cards[index].filename),
);
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
store.fail_load_ordinal = null;
const missing_root = [_]artifact.SCard{
.{ .filename = entries.cards[0].filename, .hash = "0000000000000000000000000000000000000000" },
};
try std.testing.expectError(
error.MissingNode,
tree_editor.lookup(.{ .tree = &missing_root }, entries.cards[index].filename),
);
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
}
}
}
fn seedRawNode(store: *MemoryStore, bytes: []const u8) ![]const u8 {
var name_buf: [64]u8 = undefined;
const name = artifact.artifactName(.sha1, bytes, &name_buf);
try MemoryStore.put(store, name, bytes);
return store.nodes.items[store.nodes.items.len - 1].name;
}
test "submanifest editor rejects a selected route with an overlapping predecessor range" {
const gpa = std.testing.allocator;
const hash = "0123456789012345678901234567890123456789";
const wide_entries = [_]artifact.FCard{
.{ .filename = "a", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
.{ .filename = "z", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
};
const narrow_entries = [_]artifact.FCard{
.{ .filename = "b", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
};
var store = MemoryStore.init(gpa);
defer store.deinit();
const wide_bytes = try artifact.serializeSubmanifestLeaf(gpa, &wide_entries);
defer gpa.free(wide_bytes);
const narrow_bytes = try artifact.serializeSubmanifestLeaf(gpa, &narrow_entries);
defer gpa.free(narrow_bytes);
const wide_name = try seedRawNode(&store, wide_bytes);
const narrow_name = try seedRawNode(&store, narrow_bytes);
const malformed_root = [_]artifact.SCard{
.{ .filename = "a", .hash = wide_name },
.{ .filename = "b", .hash = narrow_name },
};
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
try std.testing.expectError(
error.MalformedNode,
tree_editor.apply(.{ .tree = &malformed_root }, &.{.{ .delete = "z" }}),
);
}
test "submanifest editor rejects a nested predecessor rightmost overlap during apply" {
const gpa = std.testing.allocator;
const hash = "0123456789012345678901234567890123456789";
const left_entries = [_]artifact.FCard{
.{ .filename = "a", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
};
const wide_entries = [_]artifact.FCard{
.{ .filename = "b", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
.{ .filename = "z", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
};
const narrow_entries = [_]artifact.FCard{
.{ .filename = "c", .hash = hash, .perm = null, .old_name = null, .mode = .regular },
};
var store = MemoryStore.init(gpa);
defer store.deinit();
const left_bytes = try artifact.serializeSubmanifestLeaf(gpa, &left_entries);
defer gpa.free(left_bytes);
const wide_bytes = try artifact.serializeSubmanifestLeaf(gpa, &wide_entries);
defer gpa.free(wide_bytes);
const narrow_bytes = try artifact.serializeSubmanifestLeaf(gpa, &narrow_entries);
defer gpa.free(narrow_bytes);
const left_name = try seedRawNode(&store, left_bytes);
const wide_name = try seedRawNode(&store, wide_bytes);
const narrow_name = try seedRawNode(&store, narrow_bytes);
const inner_cards = [_]artifact.SCard{
.{ .filename = "a", .hash = left_name },
.{ .filename = "b", .hash = wide_name },
};
const inner_bytes = try artifact.serializeSubmanifestInterior(gpa, &inner_cards);
defer gpa.free(inner_bytes);
const inner_name = try seedRawNode(&store, inner_bytes);
const malformed_root = [_]artifact.SCard{
.{ .filename = "a", .hash = inner_name },
.{ .filename = "c", .hash = narrow_name },
};
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
try std.testing.expectError(
error.MalformedNode,
tree_editor.apply(.{ .tree = &malformed_root }, &.{.{ .delete = "z" }}),
);
}
test "submanifest editor bounds wide deep late-upsert predecessor validation loads" {
const gpa = std.testing.allocator;
const count = 4097;
var entries = try EntrySet.init(gpa, count);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards[0 .. count - 1], 1, .sha1);
defer parent.deinit();
const depth = try treeBuildDepth(&parent);
try std.testing.expect(depth >= 3);
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
const calls_before = store.load_calls;
var result = try tree_editor.apply(
buildRoot(&parent, entries.cards[0 .. count - 1]),
&.{.{ .upsert = entries.cards[count - 1] }},
);
defer result.deinit();
const apply_loads = store.load_calls - calls_before;
try std.testing.expect(apply_loads <= depth * 16);
}
test "submanifest editor reports malformed wrong-type and height lookup nodes distinctly" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 80);
defer entries.deinit(gpa);
var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer batch.deinit();
try std.testing.expect(!batch.isFlat());
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&batch);
const malformed_root = [_]artifact.SCard{
.{ .filename = "a", .hash = batch.s[0].hash },
};
const wrong_type_body = "M 0123456789012345678901234567890123456789\n";
var checksum: [32]u8 = undefined;
var wrong_type_bytes: [80]u8 = undefined;
const serialized_wrong_type = try std.fmt.bufPrint(
&wrong_type_bytes,
"{s}Z {s}\n",
.{ wrong_type_body, artifact.selfChecksum(wrong_type_body, &checksum) },
);
const wrong_type_name = try seedRawNode(&store, serialized_wrong_type);
const wrong_type_root = [_]artifact.SCard{
.{ .filename = entries.cards[0].filename, .hash = wrong_type_name },
};
var ordinary = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer ordinary.deinit();
try std.testing.expectError(
error.MalformedNode,
ordinary.lookup(.{ .tree = &malformed_root }, entries.cards[0].filename),
);
try std.testing.expectError(
error.WrongNodeType,
ordinary.lookup(.{ .tree = &wrong_type_root }, entries.cards[0].filename),
);
var shallow = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = 1, .hash_algo = .sha1, .height_max = 1 },
0,
);
defer shallow.deinit();
try std.testing.expectError(
error.HeightExceeded,
shallow.lookup(.{ .tree = batch.s }, entries.cards[0].filename),
);
}
fn partitionBoundsForKeys(
allocator: std.mem.Allocator,
keys: []const []const u8,
threshold: u16,
k: u4,
) ![]const usize {
const span: usize = @as(usize, 1) << k;
var partitioner = partition.CanonicalPartitioner.init(allocator, threshold, span / 4, 4 * span);
defer partitioner.deinit();
for (keys) |key| _ = try partitioner.push(artifact.zbits(key));
return partitioner.finish();
}
fn leafDescriptorKeys(
allocator: std.mem.Allocator,
entries: []const artifact.FCard,
k: u4,
) ![]const []const u8 {
const keys = try allocator.alloc([]const u8, entries.len);
defer allocator.free(keys);
for (entries, keys) |entry, *key| key.* = entry.filename;
const bounds = try partitionBoundsForKeys(allocator, keys, k, k);
defer allocator.free(bounds);
if (bounds.len < 3) return error.TestUnexpectedResult;
const descriptors = try allocator.alloc([]const u8, bounds.len - 1);
for (descriptors, bounds[0 .. bounds.len - 1]) |*descriptor, start| {
descriptor.* = entries[start].filename;
}
return descriptors;
}
fn entriesWithout(
allocator: std.mem.Allocator,
entries: []const artifact.FCard,
removed: usize,
) ![]artifact.FCard {
const retained = try allocator.alloc(artifact.FCard, entries.len - 1);
for (entries[0..removed], retained[0..removed]) |entry, *slot| slot.* = entry;
for (entries[removed + 1 ..], retained[removed..]) |entry, *slot| slot.* = entry;
return retained;
}
fn containsBoundary(bounds: []const usize, index: usize) bool {
for (bounds[0 .. bounds.len - 1]) |boundary| {
if (boundary == index) return true;
}
return false;
}
fn descriptorIndex(descriptors: []const []const u8, key: []const u8) ?usize {
for (descriptors, 0..) |descriptor, index| {
if (std.mem.eql(u8, descriptor, key)) return index;
}
return null;
}
fn descriptorCheckpoint(
allocator: std.mem.Allocator,
descriptors: []const []const u8,
k: u4,
next_index: usize,
) !partition.CanonicalPartitioner.Checkpoint {
const span: usize = @as(usize, 1) << k;
var partitioner = partition.CanonicalPartitioner.init(allocator, 2 * @as(u16, k), span / 4, 4 * span);
defer partitioner.deinit();
for (descriptors[0..next_index]) |descriptor| _ = try partitioner.push(artifact.zbits(descriptor));
return partitioner.checkpoint(descriptors[next_index]);
}
fn firstLeafKeyThatRemovesPredecessorBoundary(
allocator: std.mem.Allocator,
entries: []const artifact.FCard,
k: u4,
) !usize {
const keys = try allocator.alloc([]const u8, entries.len);
defer allocator.free(keys);
for (entries, keys) |entry, *key| key.* = entry.filename;
const before_bounds = try partitionBoundsForKeys(allocator, keys, k, k);
defer allocator.free(before_bounds);
for (before_bounds[1 .. before_bounds.len - 1]) |selected| {
const retained = try entriesWithout(allocator, entries, selected);
defer allocator.free(retained);
const after_keys = try allocator.alloc([]const u8, retained.len);
defer allocator.free(after_keys);
for (retained, after_keys) |entry, *key| key.* = entry.filename;
const after_bounds = try partitionBoundsForKeys(allocator, after_keys, k, k);
defer allocator.free(after_bounds);
if (after_bounds.len < before_bounds.len and !containsBoundary(after_bounds, selected)) return selected;
}
return error.TestUnexpectedResult;
}
fn losesMinimumInteriorDescriptor(
before_descriptors: []const []const u8,
before_bounds: []const usize,
after_descriptors: []const []const u8,
k: u4,
) bool {
const min_members = (@as(usize, 1) << k) / 4;
if (min_members == 0) return false;
for (before_bounds[0 .. before_bounds.len - 1], before_bounds[1..]) |start, end| {
if (end - start != min_members) continue;
for (before_descriptors[start..end]) |descriptor| {
if (descriptorIndex(after_descriptors, descriptor) == null) return true;
}
}
return false;
}
fn leafKeyThatShiftsInteriorBoundaryBeforeConvergence(
allocator: std.mem.Allocator,
entries: []const artifact.FCard,
k: u4,
require_minimum_descriptor_loss: bool,
selected_only: ?usize,
) !usize {
const keys = try allocator.alloc([]const u8, entries.len);
defer allocator.free(keys);
for (entries, keys) |entry, *key| key.* = entry.filename;
const leaf_bounds = try partitionBoundsForKeys(allocator, keys, k, k);
defer allocator.free(leaf_bounds);
const before_descriptors = try leafDescriptorKeys(allocator, entries, k);
defer allocator.free(before_descriptors);
const before_bounds = try partitionBoundsForKeys(allocator, before_descriptors, 2 * @as(u16, k), k);
defer allocator.free(before_bounds);
for (leaf_bounds[1 .. leaf_bounds.len - 1]) |selected| {
if (selected_only) |required| {
if (selected != required) continue;
}
const retained = try entriesWithout(allocator, entries, selected);
defer allocator.free(retained);
const after_descriptors = leafDescriptorKeys(allocator, retained, k) catch continue;
defer allocator.free(after_descriptors);
const after_bounds = try partitionBoundsForKeys(allocator, after_descriptors, 2 * @as(u16, k), k);
defer allocator.free(after_bounds);
if (require_minimum_descriptor_loss and
!losesMinimumInteriorDescriptor(before_descriptors, before_bounds, after_descriptors, k)) continue;
var diverged = false;
for (before_descriptors, 0..) |descriptor, before_index| {
const after_index = descriptorIndex(after_descriptors, descriptor) orelse continue;
const before_checkpoint = try descriptorCheckpoint(allocator, before_descriptors, k, before_index);
const after_checkpoint = try descriptorCheckpoint(allocator, after_descriptors, k, after_index);
if (!diverged) {
if (containsBoundary(before_bounds, before_index) != containsBoundary(after_bounds, after_index) and
!before_checkpoint.equivalent(after_checkpoint))
{
diverged = true;
}
} else if (before_checkpoint.equivalent(after_checkpoint)) {
return selected;
}
}
}
return error.TestUnexpectedResult;
}
test "submanifest editor deleting a selected leaf first key removes its predecessor boundary exactly" {
const gpa = std.testing.allocator;
const k: u4 = 1;
var entries = try EntrySet.init(gpa, 384);
defer entries.deinit(gpa);
const selected = try firstLeafKeyThatRemovesPredecessorBoundary(gpa, entries.cards, k);
const expected_entries = try entriesWithout(gpa, entries.cards, selected);
defer gpa.free(expected_entries);
var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1);
defer expected.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{});
defer parent_root.deinit();
var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }});
defer result.deinit();
try expectExactBatch(&store, result.root, expected_entries, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
test "submanifest editor shifts an interior descriptor boundary until checkpoints converge exactly" {
const gpa = std.testing.allocator;
const k: u4 = 1;
var entries = try EntrySet.init(gpa, 384);
defer entries.deinit(gpa);
const selected = try leafKeyThatShiftsInteriorBoundaryBeforeConvergence(gpa, entries.cards, k, false, null);
const expected_entries = try entriesWithout(gpa, entries.cards, selected);
defer gpa.free(expected_entries);
var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1);
defer expected.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{});
defer parent_root.deinit();
var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }});
defer result.deinit();
try expectExactBatch(&store, result.root, expected_entries, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
test "submanifest editor continues past a MIN-child losing descriptor until exact batch convergence" {
const gpa = std.testing.allocator;
const k: u4 = 3;
var entries = try EntrySet.init(gpa, 1024);
defer entries.deinit(gpa);
const selected = try leafKeyThatShiftsInteriorBoundaryBeforeConvergence(gpa, entries.cards, k, true, 799);
const expected_entries = try entriesWithout(gpa, entries.cards, selected);
defer gpa.free(expected_entries);
var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1);
defer expected.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{});
defer parent_root.deinit();
var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }});
defer result.deinit();
try expectExactBatch(&store, result.root, expected_entries, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}