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;
}
fn unavailablePutBatch(_: *anyopaque, _: []const editor.StoreBatchNode) 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,
put_batch_calls: usize = 0,
fail_load_ordinal: ?usize = null,
fail_put_batch_item: ?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, .put_batch_fn = putBatch };
}
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;
return self.putNode(name, bytes);
}
fn putNode(self: *MemoryStore, name: []const u8, bytes: []const u8) editor.StoreError!void {
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 putBatch(ctx: *anyopaque, nodes: []const editor.StoreBatchNode) editor.StoreError!void {
const self: *MemoryStore = @ptrCast(@alignCast(ctx));
self.put_batch_calls += 1;
for (nodes, 1..) |_, ordinal| {
if (self.fail_put_batch_item) |item| {
if (item == ordinal) return error.StorageFailure;
}
}
const prior_len = self.nodes.items.len;
for (nodes) |node| {
self.putNode(node.name, node.bytes) catch |err| {
while (self.nodes.items.len > prior_len) {
const prior = self.nodes.pop().?;
self.gpa.free(prior.name);
self.gpa.free(prior.bytes);
}
return err;
};
}
}
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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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 = @as([domain]bool, @splat(false));
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 = @as([5]bool, @splat(false));
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;
// `checkAllAllocationFailures` re-runs this whole workload once per
// allocation point, so the fixture's size multiplies the cost of every
// other line here. What the sweep proves -- each failure propagates and
// leaves the store byte-identical -- is a structural property of the
// rebuild path, not of its width: it needs a parent and a target that are
// both trees rather than flat runs, and a batch spanning several commands.
// These counts are the smallest that still satisfy that, asserted below so
// a later trim cannot quietly turn this into a flat-run test.
const initial = 24;
const target = 36;
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();
try std.testing.expect(!parent.isFlat());
try std.testing.expect(!expected.isFlat());
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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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, .put_batch_fn = unavailablePutBatch },
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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 = @as([96]bool, @splat(false));
@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 = @as([96]bool, @splat(false));
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, .put_batch_fn = unavailablePutBatch },
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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) {
// The complete-tree validation walk is memoized per root and lives
// outside the byte budget, so a repeat lookup against the same root
// re-loads only the answer path. Strictly cheaper than the first
// walk, and still non-zero: with no usable cache the path itself is
// decoded again. Both bounds matter -- equality with the first walk
// means the memo stopped working, and zero means it skipped loads
// the answer actually depends on.
const repeat_calls = store.load_calls - first_load_calls;
const repeat_bytes = store.load_bytes - first_load_bytes;
try std.testing.expect(repeat_calls != 0);
try std.testing.expect(repeat_bytes != 0);
try std.testing.expect(repeat_calls < first_load_calls);
try std.testing.expect(repeat_bytes < first_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 cache retains index capacity after eviction" {
const gpa = std.testing.allocator;
var small_entries = try EntrySet.init(gpa, 1024);
defer small_entries.deinit(gpa);
var small_batch = try artifact.buildTree(gpa, small_entries.cards, 1, .sha1);
defer small_batch.deinit();
try std.testing.expect(!small_batch.isFlat());
const large_count = 16;
const large_name_len = 64 * 1024;
const large_cards = try gpa.alloc(artifact.FCard, large_count);
defer {
for (large_cards) |card| gpa.free(card.filename);
gpa.free(large_cards);
}
for (large_cards, 0..) |*card, index| {
const filename = try gpa.alloc(u8, large_name_len);
const prefix = try std.fmt.bufPrint(filename, "q{d:0>2}-", .{index});
@memset(filename[prefix.len..], 'a');
card.* = .{
.filename = filename,
.hash = "0123456789012345678901234567890123456789",
.perm = null,
.old_name = null,
.mode = .regular,
};
}
var large_batch = try artifact.buildTree(gpa, large_cards, 1, .sha1);
defer large_batch.deinit();
try std.testing.expect(!large_batch.isFlat());
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&small_batch);
try store.seed(&large_batch);
store.put_calls = 0;
// The large node nearly consumes this budget by itself. A grown index for
// the small nodes remains allocated after they are evicted, so it must
// prevent this node from being admitted.
const budget = store.borrow(large_batch.subs[0].name).?.len + 1024;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .height_max = @intCast(artifact.max_construct_height) } } },
budget,
);
defer tree_editor.deinit();
var small_root = try tree_editor.apply(buildRoot(&small_batch, small_entries.cards), &.{});
defer small_root.deinit();
for (small_entries.cards) |card| {
try std.testing.expect((try tree_editor.lookup(rootView(small_root.root), card.filename)) != null);
}
var large_root = try tree_editor.apply(buildRoot(&large_batch, large_cards), &.{});
defer large_root.deinit();
const calls_before = store.load_calls;
try std.testing.expect((try tree_editor.lookup(rootView(large_root.root), large_cards[0].filename)) != null);
const decoded_calls = store.load_calls - calls_before;
try std.testing.expect(decoded_calls != 0);
try std.testing.expect(tree_editor.cacheHighWater() <= budget);
try std.testing.expect((try tree_editor.lookup(rootView(large_root.root), large_cards[0].filename)) != null);
try std.testing.expect(store.load_calls > calls_before + decoded_calls);
}
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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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 batch publication is atomic and retries every item failure" {
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;
successful_store.put_batch_calls = 0;
var successful_editor = try editor.TreeEditor.init(
gpa,
successful_store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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();
try std.testing.expectEqual(@as(usize, 0), successful_store.put_calls);
try std.testing.expectEqual(@as(usize, 0), successful_store.put_batch_calls);
var successful = try successful_editor.apply(rootView(successful_parent.root), commands);
defer successful.deinit();
try std.testing.expect(successful.emitted_nodes > 1);
try std.testing.expectEqual(@as(usize, 0), successful_store.put_calls);
try std.testing.expectEqual(@as(usize, 1), successful_store.put_batch_calls);
try expectExactBatch(&successful_store, successful.root, entries.cards[0..target], &expected);
try expectNewArtifactsMatch(&successful_store, successful_immutable_nodes, &expected);
for (1..successful.emitted_nodes + 1) |item| {
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
const immutable_nodes = store.nodes.items.len;
store.put_calls = 0;
store.put_batch_calls = 0;
store.fail_put_batch_item = item;
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(@as(usize, 0), store.put_calls);
try std.testing.expectEqual(@as(usize, 1), store.put_batch_calls);
try std.testing.expectEqual(immutable_nodes, store.nodes.items.len);
try expectExactBatch(&store, parent_root.root, entries.cards[0..initial], &parent);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
store.fail_put_batch_item = null;
store.put_calls = 0;
store.put_batch_calls = 0;
var retried = try tree_editor.apply(rootView(parent_root.root), commands);
defer retried.deinit();
try std.testing.expectEqual(successful.emitted_nodes, retried.emitted_nodes);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
try std.testing.expectEqual(@as(usize, 1), store.put_batch_calls);
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" {
var no_grow = @import("no_grow_allocator.zig").init(std.testing.allocator);
try std.testing.checkAllAllocationFailures(no_grow.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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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 = @as([(initial + 2)]bool, @splat(false));
@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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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) {
// See the reuse test above: root validation is memoized outside
// the byte budget, so the repeat costs only the answer path.
const repeat_calls = store.load_calls - (calls_before + decoded_calls);
const repeat_bytes = store.load_bytes - (bytes_before + decoded_bytes);
try std.testing.expect(repeat_calls != 0);
try std.testing.expect(repeat_bytes != 0);
try std.testing.expect(repeat_calls < decoded_calls);
try std.testing.expect(repeat_bytes < decoded_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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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 keeps native root suffix loads bounded as width doubles" {
const gpa = std.testing.allocator;
const widths = [_]usize{ 4096, 8192 };
var suffix_loads: [widths.len]usize = undefined;
for (widths, 0..) |width, index| {
var entries = try EntrySet.init(gpa, width);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer parent.deinit();
var expected_cards = try gpa.dupe(artifact.FCard, entries.cards);
defer gpa.free(expected_cards);
expected_cards[0].hash = "abcdefabcdefabcdefabcdefabcdefabcdefabcd";
var expected = try artifact.buildTree(gpa, expected_cards, 1, .sha1);
defer expected.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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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),
&.{.{ .upsert = expected_cards[0] }},
);
defer result.deinit();
suffix_loads[index] = store.load_calls - calls_before;
try expectExactBatch(&store, result.root, expected_cards, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
try std.testing.expect(suffix_loads[0] != 0);
try std.testing.expect(suffix_loads[1] <= suffix_loads[0] + 32);
}
test "submanifest editor does not duplicate a root S card at a native suffix splice boundary" {
const gpa = std.testing.allocator;
const width = 20_000;
var entries = try EntrySet.init(gpa, width);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer parent.deinit();
var expected_cards = try gpa.dupe(artifact.FCard, entries.cards);
defer gpa.free(expected_cards);
expected_cards[0].hash = "abcdefabcdefabcdefabcdefabcdefabcdefabcd";
var expected = try artifact.buildTree(gpa, expected_cards, 1, .sha1);
defer expected.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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .height_max = @intCast(artifact.max_construct_height) } } },
0,
);
defer tree_editor.deinit();
var result = try tree_editor.apply(
buildRoot(&parent, entries.cards),
&.{.{ .upsert = expected_cards[0] }},
);
defer result.deinit();
try expectExactBatch(&store, result.root, expected_cards, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
}
test "submanifest editor touched-route search stays logarithmic as a wide root doubles" {
const gpa = std.testing.allocator;
const widths = [_]usize{ 4096, 8192 };
var inspected: [widths.len]usize = undefined;
for (widths, 0..) |width, index| {
var entries = try EntrySet.init(gpa, width);
defer entries.deinit(gpa);
var parent = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer parent.deinit();
var store = MemoryStore.init(gpa);
defer store.deinit();
try store.seed(&parent);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .height_max = @intCast(artifact.max_construct_height) } } },
16 * 1024 * 1024,
);
defer tree_editor.deinit();
var warm_replacement = entries.cards[width - 1];
warm_replacement.hash = "abcdefabcdefabcdefabcdefabcdefabcdefabcd";
var warm = try tree_editor.apply(
buildRoot(&parent, entries.cards),
&.{.{ .upsert = warm_replacement }},
);
defer warm.deinit();
var replacement = warm_replacement;
replacement.hash = "fedcbafedcbafedcbafedcbafedcbafedcbafedc";
var result = try tree_editor.apply(rootView(warm.root), &.{.{ .upsert = replacement }});
defer result.deinit();
inspected[index] = tree_editor.touchedSearchSteps();
}
try std.testing.expect(inspected[0] != 0);
try std.testing.expect(inspected[1] <= inspected[0] + 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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .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);
}
/// The 40 paths of marktext@94ca31d5, in Git order. Found by importing the
/// real repository: every synthetic name set in this file is uniform
/// (`f000123.c`), so none of them produce the group-boundary shape below.
const marktext_parent = [_][]const u8{
".babelrc",
".electron-vue/build.js",
".electron-vue/dev-client.js",
".electron-vue/dev-runner.js",
".electron-vue/webpack.main.config.js",
".electron-vue/webpack.renderer.config.js",
".electron-vue/webpack.web.config.js",
".eslintignore",
".eslintrc.js",
".gitignore",
".travis.yml",
"README.md",
"appveyor.yml",
"build/icons/256x256.png",
"build/icons/icon.icns",
"build/icons/icon.ico",
"dist/electron/.gitkeep",
"dist/web/.gitkeep",
"package.json",
"src/index.ejs",
"src/main/index.dev.js",
"src/main/index.js",
"src/renderer/App.vue",
"src/renderer/assets/.gitkeep",
"src/renderer/assets/logo.png",
"src/renderer/components/Editor.vue",
"src/renderer/editor/index.js",
"src/renderer/editor/theme.css",
"src/renderer/main.js",
"src/renderer/store/index.js",
"src/renderer/store/modules/Counter.js",
"src/renderer/store/modules/index.js",
"static/.gitkeep",
"test/.eslintrc",
"test/e2e/index.js",
"test/e2e/specs/Launch.spec.js",
"test/e2e/utils.js",
"test/unit/index.js",
"test/unit/karma.conf.js",
"test/unit/specs/LandingPage.spec.js",
};
/// The four paths marktext@ec2362f0 adds. A pure addition: nothing is renamed,
/// deleted, or re-hashed.
const marktext_added = [_][]const u8{
"package-lock.json",
"src/renderer/editor/config.js",
"src/renderer/editor/temp.model.js",
"src/renderer/editor/utils.js",
};
fn cardsFromNames(gpa: std.mem.Allocator, names: []const []const u8) ![]artifact.FCard {
const cards = try gpa.alloc(artifact.FCard, names.len);
errdefer gpa.free(cards);
for (cards, names, 0..) |*card, name, index| {
card.* = .{
.filename = name,
.hash = hash_pool[index % hash_pool.len],
.perm = null,
.old_name = null,
.mode = .regular,
};
}
std.mem.sort(artifact.FCard, cards, {}, struct {
fn less(_: void, a: artifact.FCard, b: artifact.FCard) bool {
return artifact.compareBytes(a.filename, b.filename) == .lt;
}
}.less);
return cards;
}
/// Distinct 40-hex tokens. Content hashes never affect grouping (§6.1 keys on
/// PH(filename)); they exist so leaf bytes differ the way a real F run's do.
const hash_pool = [_][]const u8{
"0000000000000000000000000000000000000001",
"0000000000000000000000000000000000000002",
"0000000000000000000000000000000000000003",
"0000000000000000000000000000000000000004",
"0000000000000000000000000000000000000005",
"0000000000000000000000000000000000000006",
"0000000000000000000000000000000000000007",
};
// Applying a pure addition incrementally must land on the same bytes a
// from-scratch `buildTree` produces. Real repository names at k=3 caught a
// shape where it did not, and the divergence was not benign: the emitted root
// run failed `artifact.parse`, so `zit import-git` aborted with `SyntaxError`
// partway through a real history. Every k is swept because the defect was
// invisible at k=1, 2, 4, 5, 8 and 12 and present only at 3.
test "submanifest editor incremental addition equals canonical build on real names" {
const gpa = std.testing.allocator;
var child_names: std.ArrayList([]const u8) = .empty;
defer child_names.deinit(gpa);
try child_names.appendSlice(gpa, &marktext_parent);
try child_names.appendSlice(gpa, &marktext_added);
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
const parent_cards = try cardsFromNames(gpa, &marktext_parent);
defer gpa.free(parent_cards);
const child_cards = try cardsFromNames(gpa, child_names.items);
defer gpa.free(child_cards);
var parent = try artifact.buildTree(gpa, parent_cards, k, .sha1);
defer parent.deinit();
var expected = try artifact.buildTree(gpa, child_cards, k, .sha1);
defer expected.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(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .height_max = @intCast(artifact.max_construct_height) } } },
0,
);
defer tree_editor.deinit();
var parent_root = try tree_editor.apply(buildRoot(&parent, parent_cards), &.{});
defer parent_root.deinit();
var commands: std.ArrayList(editor.TreeCommand) = .empty;
defer commands.deinit(gpa);
for (child_cards) |card| {
for (marktext_added) |added| {
if (std.mem.eql(u8, card.filename, added)) {
try commands.append(gpa, .{ .upsert = card });
break;
}
}
}
try std.testing.expectEqual(marktext_added.len, commands.items.len);
var result = try tree_editor.apply(rootView(parent_root.root), commands.items);
defer result.deinit();
try expectExactBatch(&store, result.root, child_cards, &expected);
try expectNewArtifactsMatch(&store, immutable_nodes, &expected);
if (k == artifact.max_k) break;
}
}
// ---------------------------------------------------------------------------
// Repository-shaped seeded differential sweep
// ---------------------------------------------------------------------------
/// The word pools below exist to produce what the uniform `p00000123.c`
/// corpora above structurally cannot: shared directory prefixes, dotfiles at
/// several depths, basenames from one to forty-three bytes, and a mix of path
/// depths. Those are the properties that decide §6.1 group boundaries on a
/// real checkout, and the marktext regression proved a defect can hide behind
/// a uniform name set at every k.
const repo_directories = [_][]const u8{
"src", "lib", "test", "build", "dist",
"docs", "assets", "scripts", "vendor", "internal",
"pkg", "cmd", "e2e", "unit", "store",
"modules", "editor", "renderer", "main", "components",
"a", "x", "icons", "spec", "config",
".github", "node_files", "very_deeply_nested_directory_name", "third_party", "web",
};
const repo_basenames = [_][]const u8{
"index", "main",
"App", "README",
"utils", "config",
"temp.model", "karma.conf",
"webpack.renderer.config", "Counter",
"LandingPage.spec", "icon",
"256x256", "dev-client",
"logo", "s",
"Editor", "package-lock",
"a_moderately_long_module_basename_for_now",
};
const repo_extensions = [_][]const u8{
"js", "ts", "zig", "c", "h", "md", "json", "yml", "png", "css", "vue", "",
};
const repo_dotfiles = [_][]const u8{
".babelrc", ".gitignore", ".eslintrc", ".eslintrc.js",
".travis.yml", ".gitkeep", ".env", ".npmrc",
".editorconfig", ".eslintignore",
};
/// One path shape. `depth` directory components precede either a dotfile or a
/// `basename[digits][.ext]` leaf name.
const RepoShape = struct {
depth: u8,
dotfile: bool,
};
const repo_shapes = [_]RepoShape{
.{ .depth = 0, .dotfile = true },
.{ .depth = 0, .dotfile = false },
.{ .depth = 1, .dotfile = true },
.{ .depth = 1, .dotfile = false },
.{ .depth = 2, .dotfile = true },
.{ .depth = 2, .dotfile = false },
.{ .depth = 3, .dotfile = false },
};
/// Indices into `repo_shapes`, repeated to weight a corpus toward one
/// repository silhouette. Repetition is the whole weighting mechanism, so a
/// mix stays readable.
const RepoMix = []const u8;
const repo_mix_deep: RepoMix = &.{ 0, 3, 5, 5, 6, 6, 6, 4 };
const repo_mix_shallow: RepoMix = &.{ 0, 0, 1, 1, 1, 2, 3, 3, 5 };
const repo_mix_dotted: RepoMix = &.{ 0, 0, 2, 2, 2, 4, 4, 3, 5, 6 };
fn generateRepoName(gpa: std.mem.Allocator, state: *u64, mix: RepoMix) ![]u8 {
const shape = repo_shapes[mix[@as(usize, nextRandom(state)) % mix.len]];
var name: std.ArrayList(u8) = .empty;
errdefer name.deinit(gpa);
for (0..shape.depth) |_| {
try name.appendSlice(gpa, repo_directories[@as(usize, nextRandom(state)) % repo_directories.len]);
try name.append(gpa, '/');
}
if (shape.dotfile) {
try name.appendSlice(gpa, repo_dotfiles[@as(usize, nextRandom(state)) % repo_dotfiles.len]);
return name.toOwnedSlice(gpa);
}
try name.appendSlice(gpa, repo_basenames[@as(usize, nextRandom(state)) % repo_basenames.len]);
const digits = nextRandom(state) % 4;
if (digits != 0) {
var scratch: [8]u8 = undefined;
const printed = std.fmt.bufPrint(&scratch, "{d}", .{nextRandom(state) % 977}) catch unreachable;
try name.appendSlice(gpa, printed);
}
const extension = repo_extensions[@as(usize, nextRandom(state)) % repo_extensions.len];
if (extension.len != 0) {
try name.append(gpa, '.');
try name.appendSlice(gpa, extension);
}
return name.toOwnedSlice(gpa);
}
fn freeRepoCorpus(gpa: std.mem.Allocator, cards: []artifact.FCard) void {
for (cards) |card| gpa.free(card.filename);
gpa.free(cards);
}
/// `count` distinct paths in canonical order, each carrying a real hash so the
/// leaf bytes differ the way a checkout's do.
fn repoCorpus(gpa: std.mem.Allocator, seed: u64, count: usize, mix: RepoMix) ![]artifact.FCard {
var names: std.ArrayList([]u8) = .empty;
defer names.deinit(gpa);
errdefer for (names.items) |name| gpa.free(name);
var state = seed;
var attempts: usize = 0;
while (names.items.len < count) {
attempts += 1;
// The pools admit far more names than any corpus asks for; exhausting
// this budget means the generator, not the draw, is wrong.
if (attempts > count * 64) return error.TestUnexpectedResult;
const candidate = try generateRepoName(gpa, &state, mix);
const duplicate = for (names.items) |existing| {
if (std.mem.eql(u8, existing, candidate)) break true;
} else false;
if (duplicate) {
gpa.free(candidate);
continue;
}
errdefer gpa.free(candidate);
try names.append(gpa, candidate);
}
std.mem.sort([]u8, names.items, {}, struct {
fn less(_: void, a: []u8, b: []u8) bool {
return artifact.compareBytes(a, b) == .lt;
}
}.less);
const cards = try gpa.alloc(artifact.FCard, names.items.len);
for (cards, names.items, 0..) |*card, name, index| {
card.* = .{
.filename = name,
.hash = hash_pool[index % hash_pool.len],
.perm = null,
.old_name = null,
.mode = .regular,
};
}
return cards;
}
const RepoCommandKind = enum(usize) { addition = 0, deletion = 1, content = 2 };
/// Additions and deletions move the §6.1 boundary set; a content-only upsert
/// leaves every boundary in place and only rewrites one leaf. Both classes
/// have to reach the same bytes `buildTree` does.
fn nextRepoCommand(
cards: []artifact.FCard,
present: []bool,
revision: []u8,
state: *u64,
seen: *[3]bool,
) editor.TreeCommand {
const index = @as(usize, nextRandom(state)) % cards.len;
const roll = nextRandom(state) % 8;
if (roll < 3) {
if (firstAbsent(present, index)) |target| {
present[target] = true;
seen[@backingInt(RepoCommandKind.addition)] = true;
return .{ .upsert = cards[target] };
}
} else if (roll < 5) {
if (firstPresent(present, index)) |target| {
present[target] = false;
seen[@backingInt(RepoCommandKind.deletion)] = true;
return .{ .delete = cards[target].filename };
}
}
if (firstPresent(present, index)) |target| {
revision[target] +%= 1;
cards[target].hash = hash_pool[(target + revision[target]) % hash_pool.len];
seen[@backingInt(RepoCommandKind.content)] = true;
return .{ .upsert = cards[target] };
}
const target = firstAbsent(present, index).?;
present[target] = true;
seen[@backingInt(RepoCommandKind.addition)] = true;
return .{ .upsert = cards[target] };
}
const RepoCase = struct {
seed: u64,
count: usize,
initial: usize,
mix: RepoMix,
};
fn repoDifferentialSweep(
case: RepoCase,
k: u4,
batches: usize,
seen: *[3]bool,
deepest: *usize,
) !void {
const gpa = std.testing.allocator;
const cards = try repoCorpus(gpa, case.seed, case.count, case.mix);
defer freeRepoCorpus(gpa, cards);
const present = try gpa.alloc(bool, cards.len);
defer gpa.free(present);
const revision = try gpa.alloc(u8, cards.len);
defer gpa.free(revision);
@memset(revision, 0);
// A seeded k-of-n draw, so the absent names are interleaved through the
// canonical order. A contiguous absent tail would make every addition
// land past the last old leaf and never exercise a native prefix splice.
var state = case.seed ^ 0x9E37_79B9_7F4A_7C15;
var remaining = case.initial;
for (present, 0..) |*flag, index| {
const left = cards.len - index;
flag.* = remaining != 0 and
(remaining == left or @as(usize, nextRandom(&state)) % left < remaining);
if (flag.*) remaining -= 1;
}
var store = MemoryStore.init(gpa);
defer store.deinit();
const initial_entries = try expectedEntries(gpa, cards, present);
defer gpa.free(initial_entries);
var batch = try artifact.buildTree(gpa, initial_entries, k, .sha1);
defer batch.deinit();
try store.seed(&batch);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = k, .height_max = @intCast(artifact.max_construct_height) } } },
4096,
);
defer tree_editor.deinit();
var current = try tree_editor.apply(buildRoot(&batch, initial_entries), &.{});
defer current.deinit();
try expectExactBatch(&store, current.root, initial_entries, &batch);
for (0..batches) |batch_index| {
var commands: std.ArrayList(editor.TreeCommand) = .empty;
defer commands.deinit(gpa);
for (0..1 + batch_index % 5) |_| {
try commands.append(gpa, nextRepoCommand(cards, present, revision, &state, seen));
}
const nodes_before = store.nodes.items.len;
var next = try tree_editor.apply(rootView(current.root), commands.items);
errdefer next.deinit();
const selected = try expectedEntries(gpa, cards, present);
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);
deepest.* = @max(deepest.*, try treeBuildDepth(&expected));
current.deinit();
current = next;
}
}
// Byte-identity against `artifact.buildTree` over repository-shaped names, at
// every supported k. The uniform corpora elsewhere in this file never produce
// a native prefix that survives to the root level, which is exactly the shape
// that spliced one retained leaf descriptor into the same output level twice.
test "submanifest editor repository-shaped seeded differentials equal canonical builds at every k" {
const cases = [_]RepoCase{
.{ .seed = 0x5EED_0001_D1FF_0001, .count = 152, .initial = 112, .mix = repo_mix_deep },
.{ .seed = 0x5EED_0002_D1FF_0002, .count = 136, .initial = 96, .mix = repo_mix_shallow },
.{ .seed = 0x5EED_0003_D1FF_0003, .count = 168, .initial = 120, .mix = repo_mix_dotted },
.{ .seed = 0x5EED_0004_D1FF_0004, .count = 240, .initial = 168, .mix = repo_mix_deep },
};
var seen = @as([3]bool, @splat(false));
var deepest: usize = 0;
for (cases) |case| {
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
try repoDifferentialSweep(case, k, 12, &seen, &deepest);
if (k == artifact.max_k) break;
}
}
for (seen) |kind| try std.testing.expect(kind);
// Without this the sweep could silently degrade to only flat and
// single-level roots, where no prefix descriptor ever crosses a height
// boundary and the assertion above would prove nothing.
try std.testing.expect(deepest >= 3);
}
/// Prove a fixture is wide enough that the flat-mode assertions below mean
/// something: `.tree` at EVERY supported k partitions this exact name set into
/// more than one canonical group. Without it a `.flat` result could simply be
/// `buildUnpublished`'s own `groupCount(bounds) <= 1` degenerate return, and
/// the tests would pass against an editor that never learned flat mode.
fn expectEveryKWouldPartition(cards: []const artifact.FCard) !void {
const gpa = std.testing.allocator;
const names = try gpa.alloc([]const u8, cards.len);
defer gpa.free(names);
for (cards, names) |card, *name| name.* = card.filename;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
const span: usize = @as(usize, 1) << k;
const bounds = try partition.groups(gpa, names, @as(u16, k), span / 4, 4 * span, artifact.zbits);
defer gpa.free(bounds);
try std.testing.expect(partition.groupCount(bounds) > 1);
if (k == artifact.max_k) break;
}
}
/// The narrowest `EntrySet` prefix `expectEveryKWouldPartition` accepts is
/// between 2048 and 3000 names; k=12 is the binding case, needing at least
/// `span / 4` names on either side of a name whose PH has 12 leading zero bits.
/// Held here so both flat tests share one measured constant rather than two
/// guesses.
const flat_fixture_width = 3072;
fn expectFlatRoot(root: editor.RootRun, expected: []const artifact.FCard) !void {
switch (root) {
.flat => |actual| {
try std.testing.expectEqual(expected.len, actual.len);
for (expected, actual) |expected_card, actual_card| try expectFCard(expected_card, actual_card);
},
.tree => return error.TestUnexpectedResult,
}
}
/// No SUBMANIFEST artifact reached the store by any route -- neither the
/// batched publication path nor a stray single put. This is the store-side
/// statement of §8.1's "MUST NOT emit an S card", and it is independent of the
/// format flag: it inspects work actually done.
fn expectNoSubmanifestStored(store: *const MemoryStore) !void {
try std.testing.expectEqual(@as(usize, 0), store.nodes.items.len);
try std.testing.expectEqual(@as(usize, 0), store.put_calls);
try std.testing.expectEqual(@as(usize, 0), store.put_batch_calls);
}
test "submanifest editor flat format keeps an empty parent flat at any width" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, flat_fixture_width);
defer entries.deinit(gpa);
try expectEveryKWouldPartition(entries.cards);
var store = MemoryStore.init(gpa);
defer store.deinit();
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .flat },
4096,
);
defer tree_editor.deinit();
const commands = try gpa.alloc(editor.TreeCommand, entries.cards.len);
defer gpa.free(commands);
for (entries.cards, commands) |card, *command| command.* = .{ .upsert = card };
var result = try tree_editor.apply(.{ .flat = &.{} }, commands);
defer result.deinit();
try expectFlatRoot(result.root, entries.cards);
try std.testing.expectEqual(@as(?u8, 0), result.tree_height);
try std.testing.expectEqual(@as(usize, 0), result.emitted_nodes);
try std.testing.expectEqual(@as(usize, 0), result.reused_nodes);
try std.testing.expectEqual(entries.cards.len, result.changed_paths);
try expectNoSubmanifestStored(&store);
}
test "submanifest editor flat format merges upserts deletes and renames over a flat parent" {
const gpa = std.testing.allocator;
// The parent alone must clear the width bar, so the appended names come out
// of a set that is wider still rather than out of the parent's own budget.
const appended = 512;
var entries = try EntrySet.init(gpa, flat_fixture_width + appended);
defer entries.deinit(gpa);
var store = MemoryStore.init(gpa);
defer store.deinit();
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .flat },
4096,
);
defer tree_editor.deinit();
// The parent is itself produced by this editor, which is the induction the
// flat mode rests on: nothing but a flat root can reach `apply` again.
const seeded = flat_fixture_width;
var present = try gpa.alloc(bool, entries.cards.len);
defer gpa.free(present);
@memset(present, false);
@memset(present[0..seeded], true);
var parent_commands: std.ArrayList(editor.TreeCommand) = .empty;
defer parent_commands.deinit(gpa);
for (entries.cards[0..seeded]) |card| try parent_commands.append(gpa, .{ .upsert = card });
var parent = try tree_editor.apply(.{ .flat = &.{} }, parent_commands.items);
defer parent.deinit();
// The parent has to be tree-worthy too, or "applied over a flat parent"
// would be a claim about a parent that was only ever going to be flat.
try expectEveryKWouldPartition(entries.cards[0..seeded]);
try expectFlatRoot(parent.root, entries.cards[0..seeded]);
// Interleave the three merge shapes the `MergedCursor` has to reconcile:
// new names that sort AFTER every retained one, deletes scattered through
// the retained run, and renames that move a card from the retained region
// into the appended one.
var commands: std.ArrayList(editor.TreeCommand) = .empty;
defer commands.deinit(gpa);
for (entries.cards[seeded + 1 ..], seeded + 1..) |card, index| {
try commands.append(gpa, .{ .upsert = card });
present[index] = true;
}
for ([_]usize{ 0, 7, 640, 1024, 2047, seeded - 1 }) |victim| {
try commands.append(gpa, .{ .delete = entries.cards[victim].filename });
present[victim] = false;
}
// `.rename` copies the source card and only replaces its filename, so with
// this fixture's uniform hash/perm/mode the result is exactly the target
// card -- the model below stays a plain presence set. The target is the one
// appended name deliberately left out of the upsert run above, so the move
// is the only thing that can put it in the output.
try commands.append(gpa, .{ .rename = .{
.old = entries.cards[13].filename,
.new = entries.cards[seeded].filename,
} });
present[13] = false;
present[seeded] = true;
var result = try tree_editor.apply(rootView(parent.root), commands.items);
defer result.deinit();
const expected = try expectedEntries(gpa, entries.cards, present);
defer gpa.free(expected);
try expectEveryKWouldPartition(expected);
try expectFlatRoot(result.root, expected);
try std.testing.expectEqual(@as(?u8, 0), result.tree_height);
try std.testing.expectEqual(@as(usize, 0), result.emitted_nodes);
try std.testing.expectEqual(@as(usize, 0), result.reused_nodes);
try expectNoSubmanifestStored(&store);
try expectModel(&tree_editor, result.root, entries.cards, present);
}
test "submanifest editor flat format refuses a tree parent it could not have produced" {
const gpa = std.testing.allocator;
var entries = try EntrySet.init(gpa, 64);
defer entries.deinit(gpa);
var store = MemoryStore.init(gpa);
defer store.deinit();
var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1);
defer batch.deinit();
try std.testing.expect(!batch.isFlat());
try store.seed(&batch);
var tree_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .flat },
4096,
);
defer tree_editor.deinit();
// A returned error, not an assert, per this repo's own rule (see
// `release_assert_test.zig`): `apply` takes the parent from its caller, so
// a tree root under a flat format is a bad argument to a public function,
// not an invariant this file established. That it is testable AT ALL is the
// point -- an assert would only be reachable as a panic.
const commands = [_]editor.TreeCommand{.{ .delete = entries.cards[0].filename }};
try std.testing.expectError(
editor.Error.InvalidFormat,
tree_editor.apply(.{ .tree = batch.s }, &commands),
);
// The empty-command clone returns before any build work, so it needs the
// same guard or it would hand a tree root straight back out of a flat editor.
try std.testing.expectError(
editor.Error.InvalidFormat,
tree_editor.apply(.{ .tree = batch.s }, &.{}),
);
// `lookup` is the other public entry taking a caller-supplied `RootView`,
// and it has live callers on the same `parent` `apply` receives (the
// submodule-omission checks in `git_import_impl.zig`). Unguarded it would
// reach `shape.tree.height_max` and panic on the union tag, so the same
// bad argument would fail two different ways on the same API.
try std.testing.expectError(
editor.Error.InvalidFormat,
tree_editor.lookup(.{ .tree = batch.s }, entries.cards[0].filename),
);
// Negative space: the guard is one-directional on purpose. A flat root
// under a TREE format is legitimate -- it is what the editor itself returns
// whenever the canonical partition yields a single group -- so neither
// entry may refuse it.
var tree_format_editor = try editor.TreeEditor.init(
gpa,
store.asTreeStore(),
.{ .hash_algo = .sha1, .shape = .{ .tree = .{ .k = 1, .height_max = @intCast(artifact.max_construct_height) } } },
4096,
);
defer tree_format_editor.deinit();
try std.testing.expect((try tree_format_editor.lookup(.{ .flat = entries.cards }, entries.cards[0].filename)) != null);
}