Artifact aa2ba7de6b68cdf83e4f16d1cd8494cfb91631d45a61acbebe3208fbe86951d8:
- File
src/submanifest_editor_test.zig
— part of check-in
[9b96469ae6]
at
2026-08-02 01:29:11
on branch sub-manifest
— import-git: add --no-submanifests
Imports with sub-manifests off: flat manifests throughout and the spec-default config frame (k=0, enable off). Flat is §8.1's default shape; it is this verb's analyze-and-pin that is the deviation.
TreeFormat.Shape becomes flat | tree{k, height_max}, so flat-with-a-k and tree-without-one stop being representable and every tree-only site traps on the wrong tag. buildFlat drains the same MergedCursor, so ordering, dedup and rename/copy/delete stay single-sourced. SubmanifestChoice replaces submanifest_k from Request down to UserOptions.
Publication refuses if the store holds a SUBMANIFEST anyway, derived from work done rather than from the flag. Preflight analysis still runs under flat -- skipping it would put a second divergence inside the region the benchmark times.
Closes #23. (user: dmestas, size: 107481) [annotate] [blame] [check-ins using] [more...]
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 = [_]bool{false} ** domain; for (0..initial) |index| present[index] = true; try expectExactBatch(&store, current.root, entries.cards[0..initial], &batch); var seed: u64 = 0xD1FF_EA5E_0016_0001; var command_kinds_seen = [_]bool{false} ** 5; for (1..65) |command_count| { var commands: [64]editor.TreeCommand = undefined; for (commands[0..command_count]) |*command| { command.* = nextDifferentialCommand(entries.cards, present[0..], &seed); switch (command.*) { .upsert => command_kinds_seen[0] = true, .delete => command_kinds_seen[1] = true, .rename => command_kinds_seen[2] = true, .copy => command_kinds_seen[3] = true, .delete_all => command_kinds_seen[4] = true, } } const nodes_before = store.nodes.items.len; var next = try tree_editor.apply(rootView(current.root), commands[0..command_count]); errdefer next.deinit(); try expectModel(&tree_editor, next.root, entries.cards, present[0..]); const selected = try expectedEntries(gpa, entries.cards, present[0..]); defer gpa.free(selected); var expected = try artifact.buildTree(gpa, selected, k, .sha1); defer expected.deinit(); try expectExactBatch(&store, next.root, selected, &expected); try expectNewArtifactsMatch(&store, nodes_before, &expected); current.deinit(); current = next; } for (command_kinds_seen) |seen| try std.testing.expect(seen); } fn allocationFailureRun(allocator: std.mem.Allocator) !void { const fixture_allocator = std.testing.allocator; // `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 = [_]bool{false} ** 96; @memset(first_present[0..64], true); first_present[0] = false; first_present[2] = false; first_present[66] = true; first_present[67] = true; const first_entries = try expectedEntries(gpa, entries.cards, first_present[0..]); defer gpa.free(first_entries); var first_batch = try artifact.buildTree(gpa, first_entries, 1, .sha1); defer first_batch.deinit(); try expectExactBatch(&store, first.root, first_entries, &first_batch); try expectNewArtifactsMatch(&store, first_nodes_before, &first_batch); const second_commands = [_]editor.TreeCommand{ .delete_all, .{ .upsert = entries.cards[70] }, .{ .rename = .{ .old = entries.cards[70].filename, .new = entries.cards[72].filename } }, .{ .copy = .{ .old = entries.cards[72].filename, .new = entries.cards[73].filename } }, }; const second_nodes_before = store.nodes.items.len; var second = try tree_editor.apply(rootView(first.root), &second_commands); defer second.deinit(); var second_present = [_]bool{false} ** 96; second_present[72] = true; second_present[73] = true; const second_entries = try expectedEntries(gpa, entries.cards, second_present[0..]); defer gpa.free(second_entries); var second_batch = try artifact.buildTree(gpa, second_entries, 1, .sha1); defer second_batch.deinit(); try expectExactBatch(&store, second.root, second_entries, &second_batch); try expectNewArtifactsMatch(&store, second_nodes_before, &second_batch); } test "submanifest editor flat no-op has no reused nodes" { var entries = try EntrySet.init(std.testing.allocator, 1); defer entries.deinit(std.testing.allocator); var state: u8 = 0; var tree_editor = try editor.TreeEditor.init( std.testing.allocator, .{ .ctx = &state, .load_fn = unavailableLoad, .put_fn = unavailablePut, .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" { try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationFailureRun, .{}); } fn runCanonicalBoundaryTransition(k: u4, count: usize, pad_width: u8) !void { const gpa = std.testing.allocator; var entries = try EntrySet.init(gpa, count); defer entries.deinit(gpa); for (entries.cards, 0..) |*card, index| { gpa.free(card.filename); card.filename = try std.fmt.allocPrint(gpa, "q{d:0>6}.c", .{index}); } _ = pad_width; var parent = try artifact.buildTree(gpa, entries.cards[0 .. count - 1], k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, entries.cards, k, .sha1); defer expected.deinit(); try std.testing.expect(!expected.isFlat()); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .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 = [_]bool{false} ** (initial + 2); @memset(expected_present[0..initial], true); expected_present[0] = false; expected_present[initial + 1] = true; const expected_entries = try expectedEntries(gpa, entries.cards, expected_present[0..]); defer gpa.free(expected_entries); var expected = try artifact.buildTree(gpa, expected_entries, 1, .sha1); defer expected.deinit(); var chained = try tree_editor.apply(rootView(cycled.root), &chain); defer chained.deinit(); try expectExactBatch(&store, chained.root, expected_entries, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } const CanonicalCount = enum { min_minus_one, min, max_minus_one, max, natural, final_short, }; fn naturalTreeCount(entries: []const artifact.FCard, k: u4) !usize { const span: usize = @as(usize, 1) << k; const min = span / 4; const max = 4 * span; for (min..max) |candidate| { var partitioner = partition.CanonicalPartitioner.init(std.testing.allocator, k, min, max); for (entries[0..candidate]) |card| _ = try partitioner.push(artifact.zbits(card.filename)); const checkpoint = partitioner.checkpoint(null); const bounds = try partitioner.finish(); defer std.testing.allocator.free(bounds); if (!checkpoint.final_merge_pending and bounds.len == 3) return candidate; } return error.TestUnexpectedResult; } fn applyCanonicalCount( k: u4, entries: []const artifact.FCard, count: usize, ) !void { const gpa = std.testing.allocator; const parent_count = if (count == 0) 0 else count - 1; var parent = try artifact.buildTree(gpa, entries[0..parent_count], k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, entries[0..count], k, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .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[@intFromEnum(RepoCommandKind.addition)] = true; return .{ .upsert = cards[target] }; } } else if (roll < 5) { if (firstPresent(present, index)) |target| { present[target] = false; seen[@intFromEnum(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[@intFromEnum(RepoCommandKind.content)] = true; return .{ .upsert = cards[target] }; } const target = firstAbsent(present, index).?; present[target] = true; seen[@intFromEnum(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 = [_]bool{false} ** 3; 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); }