Artifact 5ea55e5c37df2ca7e9b51798890aab0848cb9ce4c02269bf876bf48fe4386db1:
- File
src/submanifest_editor_test.zig
— part of check-in
[4a95e436af]
at
2026-07-31 02:39:50
on branch sub-manifest
— submanifest: incremental apply must equal canonical construction
The incremental tree editor diverged from buildTree on realistic filename distributions. OldTreeCursor.appendPrefixAtHeight read the retained native-prefix list without consuming it, so one descriptor could be spliced into two different output levels: buildUnpublished placed the height-1 prefixes into the leaves, and mergeRootPrefixes then prepended the identical descriptor again before finishRootLevel. The emitted interior node carried the same S key twice, which fails artifact.parse's ascending-S guard, so an import aborted partway through a real history with a SyntaxError raised by our own grammar.
finishCheckpoint already guarded its own splice with a height test. That guard was an ad-hoc workaround for this same double-append, and mergeRootPrefixes never had one. The splice now consumes what it emits, so a retained descriptor lands in exactly one level and the guard becomes unnecessary rather than duplicated.
Found by importing marktext, not by the suite. Every name corpus here was uniform, and a duplicated prefix descriptor requires names that share prefixes at differing depths, so 55 tests could pass over a defect that breaks real repositories. The new seeded differential sweep generates four corpora of 136 to 240 paths with mixed depth, shared directories, dotfiles and 1 to 43 byte basenames, over every supported k with twelve batches each, and asserts it reached a tree at least three levels deep so it cannot quietly degrade into testing flat roots. It diverges in 20 of 452 batches against the unfixed editor, every divergence unparseable.
The decoded-root validation memo lands alongside it: repeated lookupTree validation against an unchanged root is answered once instead of rebuilt, which takes this file's own 56 tests from 1701 to 450 seconds over identical assertions. (user: dmestas, size: 96912) [annotate] [blame] [check-ins using]
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(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 4096, ); defer tree_editor.deinit(); var current = try tree_editor.apply(buildRoot(&batch, entries.cards[0..initial]), &.{}); defer current.deinit(); var present = [_]bool{false} ** domain; for (0..initial) |index| present[index] = true; try expectExactBatch(&store, current.root, entries.cards[0..initial], &batch); var seed: u64 = 0xD1FF_EA5E_0016_0001; var command_kinds_seen = [_]bool{false} ** 5; for (1..65) |command_count| { var commands: [64]editor.TreeCommand = undefined; for (commands[0..command_count]) |*command| { command.* = nextDifferentialCommand(entries.cards, present[0..], &seed); switch (command.*) { .upsert => command_kinds_seen[0] = true, .delete => command_kinds_seen[1] = true, .rename => command_kinds_seen[2] = true, .copy => command_kinds_seen[3] = true, .delete_all => command_kinds_seen[4] = true, } } const nodes_before = store.nodes.items.len; var next = try tree_editor.apply(rootView(current.root), commands[0..command_count]); errdefer next.deinit(); try expectModel(&tree_editor, next.root, entries.cards, present[0..]); const selected = try expectedEntries(gpa, entries.cards, present[0..]); defer gpa.free(selected); var expected = try artifact.buildTree(gpa, selected, k, .sha1); defer expected.deinit(); try expectExactBatch(&store, next.root, selected, &expected); try expectNewArtifactsMatch(&store, nodes_before, &expected); current.deinit(); current = next; } for (command_kinds_seen) |seen| try std.testing.expect(seen); } fn allocationFailureRun(allocator: std.mem.Allocator) !void { const fixture_allocator = std.testing.allocator; // `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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ) catch |err| { if (err == error.OutOfMemory) { try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try std.testing.expectEqual(@as(usize, 0), store.put_calls); try expectExactBatch(&store, buildRun(&parent, entries.cards[0..initial]), entries.cards[0..initial], &parent); } return err; }; defer tree_editor.deinit(); var commands: [target - initial]editor.TreeCommand = undefined; for (entries.cards[initial..target], commands[0..]) |card, *command| command.* = .{ .upsert = card }; var result = tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), commands[0..]) catch |err| { if (err != error.OutOfMemory) return err; try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try std.testing.expectEqual(@as(usize, 0), store.put_calls); try expectExactBatch(&store, buildRun(&parent, entries.cards[0..initial]), entries.cards[0..initial], &parent); var retried = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), commands[0..]); defer retried.deinit(); try expectExactBatch(&store, retried.root, entries.cards[0..target], &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); return error.OutOfMemory; }; defer result.deinit(); try expectExactBatch(&store, result.root, entries.cards[0..target], &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } // Pins the final-short merge in the one module both batch and editor import. test "submanifest editor partitioner owns final short merge" { var p = partition.CanonicalPartitioner.init(std.testing.allocator, 2, 2, 8); _ = try p.push(0); _ = try p.push(0); _ = try p.push(0); _ = try p.push(2); const checkpoint = p.checkpoint(null); try std.testing.expect(checkpoint.final_merge_pending); const groups = try p.finish(); defer std.testing.allocator.free(groups); try std.testing.expectEqualSlices(usize, &.{ 0, 4 }, groups); } test "submanifest editor applies Git-independent upserts transactionally" { var state: u8 = 0; var tree_editor = try editor.TreeEditor.init( std.testing.allocator, .{ .ctx = &state, .load_fn = unavailableLoad, .put_fn = unavailablePut, .put_batch_fn = unavailablePutBatch }, .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var result = try tree_editor.apply(.{ .flat = &.{} }, &.{.{ .upsert = .{ .filename = "a", .hash = "0123456789012345678901234567890123456789", .perm = null, .old_name = null, .mode = .regular, } }}); defer result.deinit(); switch (result.root) { .flat => |entries| { try std.testing.expectEqual(@as(usize, 1), entries.len); try std.testing.expectEqualStrings("a", entries[0].filename); }, .tree => return error.TestUnexpectedResult, } } test "submanifest editor fixed-seed differential sequences cover every supported k" { inline for (1..13) |raw_k| { try randomDifferential(@intCast(raw_k)); } } test "submanifest editor ordered multi-command transactions match batch trees" { const gpa = std.testing.allocator; var entries = try EntrySet.init(gpa, 96); defer entries.deinit(gpa); var parent = try artifact.buildTree(gpa, entries.cards[0..64], 1, .sha1); defer parent.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 4096, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..64]), &.{}); defer root.deinit(); const first_commands = [_]editor.TreeCommand{ .{ .upsert = entries.cards[64] }, .{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[65].filename } }, .{ .copy = .{ .old = entries.cards[1].filename, .new = entries.cards[66].filename } }, .{ .delete = entries.cards[2].filename }, .{ .rename = .{ .old = entries.cards[65].filename, .new = entries.cards[67].filename } }, .{ .delete = entries.cards[64].filename }, }; const first_nodes_before = store.nodes.items.len; var first = try tree_editor.apply(rootView(root.root), &first_commands); defer first.deinit(); var first_present = [_]bool{false} ** 96; @memset(first_present[0..64], true); first_present[0] = false; first_present[2] = false; first_present[66] = true; first_present[67] = true; const first_entries = try expectedEntries(gpa, entries.cards, first_present[0..]); defer gpa.free(first_entries); var first_batch = try artifact.buildTree(gpa, first_entries, 1, .sha1); defer first_batch.deinit(); try expectExactBatch(&store, first.root, first_entries, &first_batch); try expectNewArtifactsMatch(&store, first_nodes_before, &first_batch); const second_commands = [_]editor.TreeCommand{ .delete_all, .{ .upsert = entries.cards[70] }, .{ .rename = .{ .old = entries.cards[70].filename, .new = entries.cards[72].filename } }, .{ .copy = .{ .old = entries.cards[72].filename, .new = entries.cards[73].filename } }, }; const second_nodes_before = store.nodes.items.len; var second = try tree_editor.apply(rootView(first.root), &second_commands); defer second.deinit(); var second_present = [_]bool{false} ** 96; second_present[72] = true; second_present[73] = true; const second_entries = try expectedEntries(gpa, entries.cards, second_present[0..]); defer gpa.free(second_entries); var second_batch = try artifact.buildTree(gpa, second_entries, 1, .sha1); defer second_batch.deinit(); try expectExactBatch(&store, second.root, second_entries, &second_batch); try expectNewArtifactsMatch(&store, second_nodes_before, &second_batch); } test "submanifest editor flat no-op has no reused nodes" { var entries = try EntrySet.init(std.testing.allocator, 1); defer entries.deinit(std.testing.allocator); var state: u8 = 0; var tree_editor = try editor.TreeEditor.init( std.testing.allocator, .{ .ctx = &state, .load_fn = unavailableLoad, .put_fn = unavailablePut, .put_batch_fn = unavailablePutBatch }, .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var result = try tree_editor.apply(.{ .flat = entries.cards }, &.{}); defer result.deinit(); try std.testing.expectEqual(@as(usize, 0), result.changed_paths); try std.testing.expectEqual(@as(usize, 0), result.reused_nodes); try std.testing.expectEqual(@as(usize, 0), result.emitted_nodes); switch (result.root) { .flat => |cards| try expectFCard(entries.cards[0], cards[0]), .tree => return error.TestUnexpectedResult, } } test "submanifest editor cache budgets control decoder allocator reuse" { const gpa = std.testing.allocator; var entries = try EntrySet.init(gpa, 80); defer entries.deinit(gpa); var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1); defer batch.deinit(); try std.testing.expect(!batch.isFlat()); const full_budget: usize = 1 << 20; const budgets = [_]usize{ 0, 1, full_budget }; for (budgets, 0..) |budget, budget_index| { var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&batch); store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, budget, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{}); defer root.deinit(); _ = try tree_editor.lookup(rootView(root.root), entries.cards[0].filename); const first_load_calls = store.load_calls; const first_load_bytes = store.load_bytes; try std.testing.expect(first_load_calls != 0); try std.testing.expect(first_load_bytes != 0); _ = try tree_editor.lookup(rootView(root.root), entries.cards[0].filename); if (budget_index < 2) { // 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(), .{ .k = 1, .hash_algo = .sha1, .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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 4096, ); defer tree_editor.deinit(); var before = try tree_editor.apply(buildRoot(&parent, entries.cards[0..growth_from]), &.{}); defer before.deinit(); const before_depth = try rootDepth(&store, before.root); try std.testing.expect(before_depth >= 2); var grown = try tree_editor.apply(rootView(before.root), &.{.{ .upsert = entries.cards[growth_to - 1] }}); defer grown.deinit(); const grown_depth = try rootDepth(&store, grown.root); try std.testing.expect(grown.emitted_nodes != 0); try std.testing.expect(grown_depth > before_depth); try std.testing.expect((try tree_editor.lookup(rootView(grown.root), entries.cards[growth_to - 1].filename)) != null); var expected_grown = try artifact.buildTree(gpa, entries.cards[0..growth_to], 1, .sha1); defer expected_grown.deinit(); try expectExactBatch(&store, grown.root, entries.cards[0..growth_to], &expected_grown); var shrunk = try tree_editor.apply(rootView(grown.root), &.{.{ .delete = entries.cards[growth_to - 1].filename }}); defer shrunk.deinit(); const shrunk_depth = try rootDepth(&store, shrunk.root); // The delete reconstructs the already-stored parent shape byte-for-byte; // correct canonical reuse therefore emits no new artifact. try std.testing.expectEqual(@as(usize, 0), shrunk.emitted_nodes); try std.testing.expect(shrunk.reused_nodes != 0); try std.testing.expect(shrunk_depth < grown_depth); try std.testing.expectEqual(before_depth, shrunk_depth); var expected_present: [384]bool = undefined; @memset(expected_present[0..], false); @memset(expected_present[0..growth_from], true); try expectModel(&tree_editor, shrunk.root, entries.cards, expected_present[0..]); try std.testing.expect((try tree_editor.lookup(rootView(shrunk.root), entries.cards[growth_to - 1].filename)) == null); try expectExactBatch(&store, shrunk.root, entries.cards[0..growth_from], &parent); } test "submanifest editor preserves MAX-only sparse early root transitions" { const gpa = std.testing.allocator; var entries = try maxOnlyEntrySet(gpa, 513); defer entries.deinit(gpa); for (entries.cards) |entry| try std.testing.expectEqual(@as(u16, 1), artifact.zbits(entry.filename)); const parent_entries = try gpa.alloc(artifact.FCard, 512); defer gpa.free(parent_entries); @memcpy(parent_entries[0..1], entries.cards[0..1]); @memcpy(parent_entries[1..], entries.cards[2..]); var parent = try artifact.buildTree(gpa, parent_entries, 1, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, entries.cards, 1, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var grown = try tree_editor.apply(buildRoot(&parent, parent_entries), &.{.{ .upsert = entries.cards[1] }}); defer grown.deinit(); try std.testing.expectEqual(@as(usize, 3), try rootDepth(&store, buildRun(&parent, parent_entries))); try std.testing.expectEqual(@as(usize, 4), try rootDepth(&store, grown.root)); try expectExactBatch(&store, grown.root, entries.cards, &expected); var shrunk = try tree_editor.apply(rootView(grown.root), &.{.{ .delete = entries.cards[1].filename }}); defer shrunk.deinit(); try std.testing.expectEqual(@as(usize, 3), try rootDepth(&store, shrunk.root)); try expectExactBatch(&store, shrunk.root, parent_entries, &parent); } test "submanifest editor 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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer successful_editor.deinit(); var successful_parent = try successful_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{}); defer successful_parent.deinit(); 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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{}); defer parent_root.deinit(); try std.testing.expectError(error.StorageFailure, tree_editor.apply(rootView(parent_root.root), commands)); try std.testing.expectEqual(@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(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards[0 .. count - 1]), &.{}); defer parent_root.deinit(); var next = try tree_editor.apply(rootView(parent_root.root), &.{.{ .upsert = entries.cards[count - 1] }}); defer next.deinit(); try expectExactBatch(&store, next.root, entries.cards, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } fn finalShortTreeCount(entries: []const artifact.FCard, k: u4, minimum_groups: usize) !usize { const span: usize = @as(usize, 1) << k; const min = span / 4; const max = 4 * span; for (1..entries.len + 1) |candidate| { var partitioner = partition.CanonicalPartitioner.init(std.testing.allocator, k, min, max); for (entries[0..candidate]) |card| _ = try partitioner.push(artifact.zbits(card.filename)); const checkpoint = partitioner.checkpoint(null); const bounds = try partitioner.finish(); defer std.testing.allocator.free(bounds); if (checkpoint.final_merge_pending and bounds.len >= minimum_groups + 1) return candidate; } return error.TestUnexpectedResult; } test "submanifest editor preserves canonical MIN and MAX k forced boundaries" { const min_count = 4 * (@as(usize, 1) << artifact.min_k) + 1; const max_count = 4 * (@as(usize, 1) << artifact.max_k) + 1; try runCanonicalBoundaryTransition(artifact.min_k, min_count, 6); try runCanonicalBoundaryTransition(artifact.max_k, max_count, 6); } test "submanifest editor matches a final-short leaf merge" { const gpa = std.testing.allocator; const k: u4 = 4; var entries = try EntrySet.init(gpa, 512); defer entries.deinit(gpa); const count = try finalShortTreeCount(entries.cards, k, 2); var expected = try artifact.buildTree(gpa, entries.cards[0..count], k, .sha1); defer expected.deinit(); try std.testing.expect(!expected.isFlat()); try std.testing.expect(expected.s.len >= 2); var store = MemoryStore.init(gpa); defer store.deinit(); var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); const commands = try gpa.alloc(editor.TreeCommand, count); defer gpa.free(commands); for (entries.cards[0..count], commands) |card, *command| command.* = .{ .upsert = card }; var result = try tree_editor.apply(.{ .flat = &.{} }, commands); defer result.deinit(); try expectExactBatch(&store, result.root, entries.cards[0..count], &expected); } test "submanifest editor rejects duplicate destinations and absent sources without writes" { const gpa = std.testing.allocator; const initial = 64; var entries = try EntrySet.init(gpa, initial + 2); defer entries.deinit(gpa); var parent = try artifact.buildTree(gpa, entries.cards[0..initial], 1, .sha1); defer parent.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{}); defer root.deinit(); try std.testing.expectError(error.DuplicatePath, tree_editor.apply(rootView(root.root), &.{.{ .copy = .{ .old = entries.cards[0].filename, .new = entries.cards[1].filename, } }})); try std.testing.expectError(error.MissingPath, tree_editor.apply(rootView(root.root), &.{.{ .delete = entries.cards[initial].filename }})); try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try std.testing.expectEqual(@as(usize, 0), store.put_calls); try expectExactBatch(&store, root.root, entries.cards[0..initial], &parent); var expected = try artifact.buildTree(gpa, entries.cards[0 .. initial + 1], 1, .sha1); defer expected.deinit(); var retried = try tree_editor.apply(rootView(root.root), &.{.{ .upsert = entries.cards[initial] }}); defer retried.deinit(); try expectExactBatch(&store, retried.root, entries.cards[0 .. initial + 1], &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } test "submanifest editor gives rename cycles and chains net-path overlay semantics" { const gpa = std.testing.allocator; const initial = 64; var entries = try EntrySet.init(gpa, initial + 2); defer entries.deinit(gpa); var parent = try artifact.buildTree(gpa, entries.cards[0..initial], 1, .sha1); defer parent.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&parent, entries.cards[0..initial]), &.{}); defer root.deinit(); const cycle = [_]editor.TreeCommand{ .{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[initial].filename } }, .{ .rename = .{ .old = entries.cards[initial].filename, .new = entries.cards[0].filename } }, }; var cycled = try tree_editor.apply(rootView(root.root), &cycle); defer cycled.deinit(); try std.testing.expectEqual(@as(usize, 0), cycled.changed_paths); try std.testing.expectEqual(@as(usize, 0), cycled.emitted_nodes); try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try expectExactBatch(&store, cycled.root, entries.cards[0..initial], &parent); const chain = [_]editor.TreeCommand{ .{ .rename = .{ .old = entries.cards[0].filename, .new = entries.cards[initial].filename } }, .{ .rename = .{ .old = entries.cards[initial].filename, .new = entries.cards[initial + 1].filename } }, }; var expected_present = [_]bool{false} ** (initial + 2); @memset(expected_present[0..initial], true); expected_present[0] = false; expected_present[initial + 1] = true; const expected_entries = try expectedEntries(gpa, entries.cards, expected_present[0..]); defer gpa.free(expected_entries); var expected = try artifact.buildTree(gpa, expected_entries, 1, .sha1); defer expected.deinit(); var chained = try tree_editor.apply(rootView(cycled.root), &chain); defer chained.deinit(); try expectExactBatch(&store, chained.root, expected_entries, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } const CanonicalCount = enum { min_minus_one, min, max_minus_one, max, natural, final_short, }; fn naturalTreeCount(entries: []const artifact.FCard, k: u4) !usize { const span: usize = @as(usize, 1) << k; const min = span / 4; const max = 4 * span; for (min..max) |candidate| { var partitioner = partition.CanonicalPartitioner.init(std.testing.allocator, k, min, max); for (entries[0..candidate]) |card| _ = try partitioner.push(artifact.zbits(card.filename)); const checkpoint = partitioner.checkpoint(null); const bounds = try partitioner.finish(); defer std.testing.allocator.free(bounds); if (!checkpoint.final_merge_pending and bounds.len == 3) return candidate; } return error.TestUnexpectedResult; } fn applyCanonicalCount( k: u4, entries: []const artifact.FCard, count: usize, ) !void { const gpa = std.testing.allocator; const parent_count = if (count == 0) 0 else count - 1; var parent = try artifact.buildTree(gpa, entries[0..parent_count], k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, entries[0..count], k, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries[0..parent_count]), &.{}); defer parent_root.deinit(); var next = if (count == 0) try tree_editor.apply(rootView(parent_root.root), &.{}) else try tree_editor.apply(rootView(parent_root.root), &.{.{ .upsert = entries[count - 1] }}); defer next.deinit(); try expectExactBatch(&store, next.root, entries[0..count], &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } test "submanifest editor preserves every canonical MIN MAX natural and final partition boundary" { inline for (artifact.min_k..artifact.max_k + 1) |raw_k| { const k: u4 = @intCast(raw_k); const span: usize = @as(usize, 1) << k; const min = @max(span / 4, 1); const max = 4 * span; var entries = try EntrySet.init(std.testing.allocator, 4 * max); defer entries.deinit(std.testing.allocator); // For k=1 and k=2, the RFC MIN is 0 or 1, so a non-empty final // group cannot be shorter than MIN. The empty case pins that edge. const final_short_count = if (span / 4 <= 1) 0 else try finalShortTreeCount(entries.cards, k, 1); const counts = [_]struct { CanonicalCount, usize }{ .{ .min_minus_one, min - 1 }, .{ .min, min }, .{ .max_minus_one, max - 1 }, .{ .max, max }, .{ .natural, try naturalTreeCount(entries.cards, k) }, .{ .final_short, final_short_count }, }; for (counts) |case| { switch (case[0]) { .min_minus_one, .min, .max_minus_one, .max, .natural, .final_short => {}, } try applyCanonicalCount(k, entries.cards, case[1]); } } } fn lookupMatrixIndex(position: usize, count: usize) usize { return switch (position) { 0 => 0, 1 => count / 2, 2 => count - 1, else => unreachable, }; } test "submanifest editor observes decoded cache budgets for first middle and last lookups" { const gpa = std.testing.allocator; var entries = try EntrySet.init(gpa, 80); defer entries.deinit(gpa); var batch = try artifact.buildTree(gpa, entries.cards, 1, .sha1); defer batch.deinit(); try std.testing.expect(!batch.isFlat()); const full_budget: usize = 1 << 20; const budgets = [_]usize{ 0, 1, full_budget }; for (budgets) |budget| { for (0..3) |position| { var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&batch); store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, budget, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{}); defer root.deinit(); const index = lookupMatrixIndex(position, entries.cards.len); const calls_before = store.load_calls; const bytes_before = store.load_bytes; try std.testing.expect((try tree_editor.lookup(rootView(root.root), entries.cards[index].filename)) != null); const decoded_calls = store.load_calls - calls_before; const decoded_bytes = store.load_bytes - bytes_before; try std.testing.expect(decoded_calls != 0); try std.testing.expect(decoded_bytes != 0); try std.testing.expect((try tree_editor.lookup(rootView(root.root), entries.cards[index].filename)) != null); if (budget < decoded_bytes) { // 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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, budget, ); defer tree_editor.deinit(); var root = try tree_editor.apply(buildRoot(&batch, entries.cards), &.{}); defer root.deinit(); const index = lookupMatrixIndex(position, entries.cards.len); store.fail_load_ordinal = store.load_calls + 1; try std.testing.expectError( error.StorageFailure, tree_editor.lookup(rootView(root.root), entries.cards[index].filename), ); try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try std.testing.expectEqual(@as(usize, 0), store.put_calls); store.fail_load_ordinal = null; const missing_root = [_]artifact.SCard{ .{ .filename = entries.cards[0].filename, .hash = "0000000000000000000000000000000000000000" }, }; try std.testing.expectError( error.MissingNode, tree_editor.lookup(.{ .tree = &missing_root }, entries.cards[index].filename), ); try std.testing.expectEqual(immutable_nodes, store.nodes.items.len); try std.testing.expectEqual(@as(usize, 0), store.put_calls); } } } fn seedRawNode(store: *MemoryStore, bytes: []const u8) ![]const u8 { var name_buf: [64]u8 = undefined; const name = artifact.artifactName(.sha1, bytes, &name_buf); try MemoryStore.put(store, name, bytes); return store.nodes.items[store.nodes.items.len - 1].name; } test "submanifest editor rejects a selected route with an overlapping predecessor range" { const gpa = std.testing.allocator; const hash = "0123456789012345678901234567890123456789"; const wide_entries = [_]artifact.FCard{ .{ .filename = "a", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, .{ .filename = "z", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, }; const narrow_entries = [_]artifact.FCard{ .{ .filename = "b", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, }; var store = MemoryStore.init(gpa); defer store.deinit(); const wide_bytes = try artifact.serializeSubmanifestLeaf(gpa, &wide_entries); defer gpa.free(wide_bytes); const narrow_bytes = try artifact.serializeSubmanifestLeaf(gpa, &narrow_entries); defer gpa.free(narrow_bytes); const wide_name = try seedRawNode(&store, wide_bytes); const narrow_name = try seedRawNode(&store, narrow_bytes); const malformed_root = [_]artifact.SCard{ .{ .filename = "a", .hash = wide_name }, .{ .filename = "b", .hash = narrow_name }, }; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); try std.testing.expectError( error.MalformedNode, tree_editor.apply(.{ .tree = &malformed_root }, &.{.{ .delete = "z" }}), ); } test "submanifest editor rejects a nested predecessor rightmost overlap during apply" { const gpa = std.testing.allocator; const hash = "0123456789012345678901234567890123456789"; const left_entries = [_]artifact.FCard{ .{ .filename = "a", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, }; const wide_entries = [_]artifact.FCard{ .{ .filename = "b", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, .{ .filename = "z", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, }; const narrow_entries = [_]artifact.FCard{ .{ .filename = "c", .hash = hash, .perm = null, .old_name = null, .mode = .regular }, }; var store = MemoryStore.init(gpa); defer store.deinit(); const left_bytes = try artifact.serializeSubmanifestLeaf(gpa, &left_entries); defer gpa.free(left_bytes); const wide_bytes = try artifact.serializeSubmanifestLeaf(gpa, &wide_entries); defer gpa.free(wide_bytes); const narrow_bytes = try artifact.serializeSubmanifestLeaf(gpa, &narrow_entries); defer gpa.free(narrow_bytes); const left_name = try seedRawNode(&store, left_bytes); const wide_name = try seedRawNode(&store, wide_bytes); const narrow_name = try seedRawNode(&store, narrow_bytes); const inner_cards = [_]artifact.SCard{ .{ .filename = "a", .hash = left_name }, .{ .filename = "b", .hash = wide_name }, }; const inner_bytes = try artifact.serializeSubmanifestInterior(gpa, &inner_cards); defer gpa.free(inner_bytes); const inner_name = try seedRawNode(&store, inner_bytes); const malformed_root = [_]artifact.SCard{ .{ .filename = "a", .hash = inner_name }, .{ .filename = "c", .hash = narrow_name }, }; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); try std.testing.expectError( error.MalformedNode, tree_editor.apply(.{ .tree = &malformed_root }, &.{.{ .delete = "z" }}), ); } test "submanifest editor bounds wide deep late-upsert predecessor validation loads" { const gpa = std.testing.allocator; const count = 4097; var entries = try EntrySet.init(gpa, count); defer entries.deinit(gpa); var parent = try artifact.buildTree(gpa, entries.cards[0 .. count - 1], 1, .sha1); defer parent.deinit(); const depth = try treeBuildDepth(&parent); try std.testing.expect(depth >= 3); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); const calls_before = store.load_calls; var result = try tree_editor.apply( buildRoot(&parent, entries.cards[0 .. count - 1]), &.{.{ .upsert = entries.cards[count - 1] }}, ); defer result.deinit(); const apply_loads = store.load_calls - calls_before; try std.testing.expect(apply_loads <= depth * 16); } test "submanifest editor 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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); const calls_before = store.load_calls; var result = try tree_editor.apply( buildRoot(&parent, entries.cards), &.{.{ .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(), .{ .k = 1, .hash_algo = .sha1, .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(), .{ .k = 1, .hash_algo = .sha1, .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(), .{ .k = 1, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer ordinary.deinit(); try std.testing.expectError( error.MalformedNode, ordinary.lookup(.{ .tree = &malformed_root }, entries.cards[0].filename), ); try std.testing.expectError( error.WrongNodeType, ordinary.lookup(.{ .tree = &wrong_type_root }, entries.cards[0].filename), ); var shallow = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = 1, .hash_algo = .sha1, .height_max = 1 }, 0, ); defer shallow.deinit(); try std.testing.expectError( error.HeightExceeded, shallow.lookup(.{ .tree = batch.s }, entries.cards[0].filename), ); } fn partitionBoundsForKeys( allocator: std.mem.Allocator, keys: []const []const u8, threshold: u16, k: u4, ) ![]const usize { const span: usize = @as(usize, 1) << k; var partitioner = partition.CanonicalPartitioner.init(allocator, threshold, span / 4, 4 * span); defer partitioner.deinit(); for (keys) |key| _ = try partitioner.push(artifact.zbits(key)); return partitioner.finish(); } fn leafDescriptorKeys( allocator: std.mem.Allocator, entries: []const artifact.FCard, k: u4, ) ![]const []const u8 { const keys = try allocator.alloc([]const u8, entries.len); defer allocator.free(keys); for (entries, keys) |entry, *key| key.* = entry.filename; const bounds = try partitionBoundsForKeys(allocator, keys, k, k); defer allocator.free(bounds); if (bounds.len < 3) return error.TestUnexpectedResult; const descriptors = try allocator.alloc([]const u8, bounds.len - 1); for (descriptors, bounds[0 .. bounds.len - 1]) |*descriptor, start| { descriptor.* = entries[start].filename; } return descriptors; } fn entriesWithout( allocator: std.mem.Allocator, entries: []const artifact.FCard, removed: usize, ) ![]artifact.FCard { const retained = try allocator.alloc(artifact.FCard, entries.len - 1); for (entries[0..removed], retained[0..removed]) |entry, *slot| slot.* = entry; for (entries[removed + 1 ..], retained[removed..]) |entry, *slot| slot.* = entry; return retained; } fn containsBoundary(bounds: []const usize, index: usize) bool { for (bounds[0 .. bounds.len - 1]) |boundary| { if (boundary == index) return true; } return false; } fn descriptorIndex(descriptors: []const []const u8, key: []const u8) ?usize { for (descriptors, 0..) |descriptor, index| { if (std.mem.eql(u8, descriptor, key)) return index; } return null; } fn descriptorCheckpoint( allocator: std.mem.Allocator, descriptors: []const []const u8, k: u4, next_index: usize, ) !partition.CanonicalPartitioner.Checkpoint { const span: usize = @as(usize, 1) << k; var partitioner = partition.CanonicalPartitioner.init(allocator, 2 * @as(u16, k), span / 4, 4 * span); defer partitioner.deinit(); for (descriptors[0..next_index]) |descriptor| _ = try partitioner.push(artifact.zbits(descriptor)); return partitioner.checkpoint(descriptors[next_index]); } fn firstLeafKeyThatRemovesPredecessorBoundary( allocator: std.mem.Allocator, entries: []const artifact.FCard, k: u4, ) !usize { const keys = try allocator.alloc([]const u8, entries.len); defer allocator.free(keys); for (entries, keys) |entry, *key| key.* = entry.filename; const before_bounds = try partitionBoundsForKeys(allocator, keys, k, k); defer allocator.free(before_bounds); for (before_bounds[1 .. before_bounds.len - 1]) |selected| { const retained = try entriesWithout(allocator, entries, selected); defer allocator.free(retained); const after_keys = try allocator.alloc([]const u8, retained.len); defer allocator.free(after_keys); for (retained, after_keys) |entry, *key| key.* = entry.filename; const after_bounds = try partitionBoundsForKeys(allocator, after_keys, k, k); defer allocator.free(after_bounds); if (after_bounds.len < before_bounds.len and !containsBoundary(after_bounds, selected)) return selected; } return error.TestUnexpectedResult; } fn losesMinimumInteriorDescriptor( before_descriptors: []const []const u8, before_bounds: []const usize, after_descriptors: []const []const u8, k: u4, ) bool { const min_members = (@as(usize, 1) << k) / 4; if (min_members == 0) return false; for (before_bounds[0 .. before_bounds.len - 1], before_bounds[1..]) |start, end| { if (end - start != min_members) continue; for (before_descriptors[start..end]) |descriptor| { if (descriptorIndex(after_descriptors, descriptor) == null) return true; } } return false; } fn leafKeyThatShiftsInteriorBoundaryBeforeConvergence( allocator: std.mem.Allocator, entries: []const artifact.FCard, k: u4, require_minimum_descriptor_loss: bool, selected_only: ?usize, ) !usize { const keys = try allocator.alloc([]const u8, entries.len); defer allocator.free(keys); for (entries, keys) |entry, *key| key.* = entry.filename; const leaf_bounds = try partitionBoundsForKeys(allocator, keys, k, k); defer allocator.free(leaf_bounds); const before_descriptors = try leafDescriptorKeys(allocator, entries, k); defer allocator.free(before_descriptors); const before_bounds = try partitionBoundsForKeys(allocator, before_descriptors, 2 * @as(u16, k), k); defer allocator.free(before_bounds); for (leaf_bounds[1 .. leaf_bounds.len - 1]) |selected| { if (selected_only) |required| { if (selected != required) continue; } const retained = try entriesWithout(allocator, entries, selected); defer allocator.free(retained); const after_descriptors = leafDescriptorKeys(allocator, retained, k) catch continue; defer allocator.free(after_descriptors); const after_bounds = try partitionBoundsForKeys(allocator, after_descriptors, 2 * @as(u16, k), k); defer allocator.free(after_bounds); if (require_minimum_descriptor_loss and !losesMinimumInteriorDescriptor(before_descriptors, before_bounds, after_descriptors, k)) continue; var diverged = false; for (before_descriptors, 0..) |descriptor, before_index| { const after_index = descriptorIndex(after_descriptors, descriptor) orelse continue; const before_checkpoint = try descriptorCheckpoint(allocator, before_descriptors, k, before_index); const after_checkpoint = try descriptorCheckpoint(allocator, after_descriptors, k, after_index); if (!diverged) { if (containsBoundary(before_bounds, before_index) != containsBoundary(after_bounds, after_index) and !before_checkpoint.equivalent(after_checkpoint)) { diverged = true; } } else if (before_checkpoint.equivalent(after_checkpoint)) { return selected; } } } return error.TestUnexpectedResult; } test "submanifest editor deleting a selected leaf first key removes its predecessor boundary exactly" { const gpa = std.testing.allocator; const k: u4 = 1; var entries = try EntrySet.init(gpa, 384); defer entries.deinit(gpa); const selected = try firstLeafKeyThatRemovesPredecessorBoundary(gpa, entries.cards, k); const expected_entries = try entriesWithout(gpa, entries.cards, selected); defer gpa.free(expected_entries); var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{}); defer parent_root.deinit(); var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }}); defer result.deinit(); try expectExactBatch(&store, result.root, expected_entries, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } test "submanifest editor shifts an interior descriptor boundary until checkpoints converge exactly" { const gpa = std.testing.allocator; const k: u4 = 1; var entries = try EntrySet.init(gpa, 384); defer entries.deinit(gpa); const selected = try leafKeyThatShiftsInteriorBoundaryBeforeConvergence(gpa, entries.cards, k, false, null); const expected_entries = try entriesWithout(gpa, entries.cards, selected); defer gpa.free(expected_entries); var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{}); defer parent_root.deinit(); var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }}); defer result.deinit(); try expectExactBatch(&store, result.root, expected_entries, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } test "submanifest editor continues past a MIN-child losing descriptor until exact batch convergence" { const gpa = std.testing.allocator; const k: u4 = 3; var entries = try EntrySet.init(gpa, 1024); defer entries.deinit(gpa); const selected = try leafKeyThatShiftsInteriorBoundaryBeforeConvergence(gpa, entries.cards, k, true, 799); const expected_entries = try entriesWithout(gpa, entries.cards, selected); defer gpa.free(expected_entries); var parent = try artifact.buildTree(gpa, entries.cards, k, .sha1); defer parent.deinit(); var expected = try artifact.buildTree(gpa, expected_entries, k, .sha1); defer expected.deinit(); var store = MemoryStore.init(gpa); defer store.deinit(); try store.seed(&parent); const immutable_nodes = store.nodes.items.len; store.put_calls = 0; var tree_editor = try editor.TreeEditor.init( gpa, store.asTreeStore(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, entries.cards), &.{}); defer parent_root.deinit(); var result = try tree_editor.apply(rootView(parent_root.root), &.{.{ .delete = entries.cards[selected].filename }}); defer result.deinit(); try expectExactBatch(&store, result.root, expected_entries, &expected); try expectNewArtifactsMatch(&store, immutable_nodes, &expected); } /// 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(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 0, ); defer tree_editor.deinit(); var parent_root = try tree_editor.apply(buildRoot(&parent, 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(), .{ .k = k, .hash_algo = .sha1, .height_max = @intCast(artifact.max_construct_height) }, 4096, ); defer tree_editor.deinit(); var current = try tree_editor.apply(buildRoot(&batch, 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); }