//! Export planner + seam-enumeration tests: strict topological order with
//! the timeline order as the ready tiebreak, mark-map exclusion, and the
//! §9.3 seam-equivalence proof — the SAME file set enumerated identically
//! through a flat manifest, an S-card tree, and a delta manifest, with the
//! tree case proven to have gone through `Manifest.flattenTree` via the
//! sub-manifest memo's own counters (zero bespoke S-card walks).
const std = @import("std");
const artifact = @import("../artifact.zig");
const logstore = @import("../logstore.zig");
const storage = @import("../storage.zig");
const repostate = @import("../repostate.zig");
const Repository = @import("../repository.zig").Repository;
const export_impl = @import("git_export_impl.zig");
const testing = std.testing;
// ---------------------------------------------------------------------------
// Planner ordering over synthetic RepoState graphs.
// ---------------------------------------------------------------------------
const h = struct {
fn n(comptime c: u8) *const [64]u8 {
return &(.{c} ** 64);
}
};
fn crosslinkChain(rs: *repostate.RepoState) !void {
_ = try rs.crosslink(.{ .hash = h.n('a'), .mtime = 10, .tags = &.{
.{ .type = .propagate, .name = "sym-trunk", .target = null, .value = "trunk" },
} });
_ = try rs.crosslink(.{ .hash = h.n('b'), .mtime = 20, .parents = &.{h.n('a')} });
_ = try rs.crosslink(.{ .hash = h.n('c'), .mtime = 30, .parents = &.{h.n('b')} });
}
fn indexOf(order: []const repostate.Rid, rid: repostate.Rid) usize {
for (order, 0..) |r, i| {
if (r == rid) return i;
}
unreachable;
}
fn expectParentsFirst(rs: *const repostate.RepoState, order: []const repostate.Rid) !void {
for (order) |rid| {
var it = rs.parentsOf(rid);
while (it.next()) |parent| {
if (rs.mtimeOf(parent) == null) continue; // phantom parent: not planned
try testing.expect(indexOf(order, parent) < indexOf(order, rid));
}
}
}
test "git export planner: linear history plans oldest-first, every parent before its child" {
const gpa = testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
var rs = repostate.RepoState.init(gpa, ms.store());
defer rs.deinit();
try crosslinkChain(&rs);
var nothing = export_impl.NoneExported{};
const order = try export_impl.plan(gpa, &rs, nothing.predicate());
defer gpa.free(order);
try testing.expectEqual(@as(usize, 3), order.len);
try expectParentsFirst(&rs, order);
// Deterministic and oldest-first on a linear chain.
try testing.expectEqualStrings(h.n('a'), ms.store().hashOf(order[0]));
try testing.expectEqualStrings(h.n('c'), ms.store().hashOf(order[2]));
}
test "git export planner: fork, merge, octopus, and an mtime-skewed child all stay topological" {
const gpa = testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
var rs = repostate.RepoState.init(gpa, ms.store());
defer rs.deinit();
_ = try rs.crosslink(.{ .hash = h.n('a'), .mtime = 10, .tags = &.{
.{ .type = .propagate, .name = "sym-trunk", .target = null, .value = "trunk" },
} });
_ = try rs.crosslink(.{ .hash = h.n('b'), .mtime = 20, .parents = &.{h.n('a')} });
_ = try rs.crosslink(.{ .hash = h.n('c'), .mtime = 21, .parents = &.{h.n('a')} });
_ = try rs.crosslink(.{ .hash = h.n('d'), .mtime = 22, .parents = &.{h.n('a')} });
// Octopus-ish merge of three lines.
_ = try rs.crosslink(.{ .hash = h.n('e'), .mtime = 30, .parents = &.{ h.n('b'), h.n('c'), h.n('d') } });
// Mtime-skewed child: D card EARLIER than its parent's — must still plan
// after it (topology outranks the clock).
_ = try rs.crosslink(.{ .hash = h.n('f'), .mtime = 5, .parents = &.{h.n('e')} });
var nothing = export_impl.NoneExported{};
const order = try export_impl.plan(gpa, &rs, nothing.predicate());
defer gpa.free(order);
try testing.expectEqual(@as(usize, 6), order.len);
try expectParentsFirst(&rs, order);
}
test "git export planner: a pre-seeded mark map excludes exported prefixes from the frontier" {
const gpa = testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
var rs = repostate.RepoState.init(gpa, ms.store());
defer rs.deinit();
try crosslinkChain(&rs);
// 'a' and 'b' already exported: only 'c' plans, and its recorded parent
// counts as satisfied rather than blocking.
var seeded = export_impl.SetExported{};
defer seeded.deinit(gpa);
try seeded.hashes.put(gpa, h.n('a'), {});
try seeded.hashes.put(gpa, h.n('b'), {});
const order = try export_impl.plan(gpa, &rs, seeded.predicate());
defer gpa.free(order);
try testing.expectEqual(@as(usize, 1), order.len);
try testing.expectEqualStrings(h.n('c'), ms.store().hashOf(order[0]));
}
// ---------------------------------------------------------------------------
// Seam equivalence: flat, S-card tree, and delta manifests with ONE file set.
// ---------------------------------------------------------------------------
const FixtureRepo = struct {
tmp: std.testing.TmpDir,
fs: storage.FileStorage,
log: logstore.LogStore,
raw: std.Io.File,
io: std.Io,
fn init(self: *FixtureRepo, io: std.Io) !void {
self.io = io;
self.tmp = testing.tmpDir(.{});
self.raw = try self.tmp.dir.createFile(io, ".zit", .{ .read = true });
self.fs = storage.FileStorage.init(io, self.raw, 0);
self.log = try logstore.LogStore.open(testing.allocator, self.fs.storageFile(), 0);
try self.log.putConfig(.{ .hash_policy = 0, .default_branch = "trunk", .project_id = "p" });
}
fn seal(self: *FixtureRepo) !void {
try self.log.commit();
self.log.deinit(testing.allocator);
self.raw.close(self.io);
}
fn cleanup(self: *FixtureRepo) void {
self.tmp.cleanup();
}
fn putRaw(self: *FixtureRepo, bytes: []const u8) ![]u8 {
var digest: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(bytes, &digest, .{});
_ = try self.log.put(&digest, bytes);
const out = try testing.allocator.alloc(u8, 64);
const digits = "0123456789abcdef";
for (&digest, 0..) |b, i| {
out[i * 2] = digits[b >> 4];
out[i * 2 + 1] = digits[b & 0x0f];
}
return out;
}
};
fn fcard(name: []const u8, hash: []const u8) artifact.FCard {
return .{ .filename = name, .hash = hash, .perm = null, .old_name = null, .mode = .regular };
}
fn baseManifest(ts: []const u8, parent: ?[]const u8) artifact.Manifest {
_ = parent;
return .{
.arena_state = std.heap.ArenaAllocator.init(testing.allocator),
.kind = .manifest,
.a = null,
.b = null,
.c = .{ .comment = "c" },
.d = .{ .timestamp = ts },
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.t = &.{.{ .sign = .propagate, .name = "branch", .target = null, .value = "trunk" }},
};
}
fn collect(gpa: std.mem.Allocator, files: artifact.ManifestFiles, out: *std.ArrayList(artifact.FCard)) !void {
var it = files.iterator();
while (it.next()) |f| try out.append(gpa, f);
}
test "git export seam: flat, S-card tree, and delta manifests enumerate one identical file set through flattenTree" {
const io = testing.io;
const gpa = testing.allocator;
var repo: FixtureRepo = undefined;
try repo.init(io);
defer repo.cleanup();
// The shared file set — names diverge on the first byte so k=1 partitions.
const b1 = try repo.putRaw("alpha\n");
defer gpa.free(b1);
const b2 = try repo.putRaw("beta\n");
defer gpa.free(b2);
const b3 = try repo.putRaw("gamma\n");
defer gpa.free(b3);
const cards = [_]artifact.FCard{
fcard("adir/a.txt", b1),
fcard("bdir/b.txt", b2),
fcard("cdir/c.txt", b3),
};
// 1. FLAT manifest.
var flat_m = baseManifest("2020-01-01T00:00:00", null);
defer flat_m.deinit();
flat_m.f = &cards;
const flat_bytes = try artifact.create(&flat_m, gpa);
defer gpa.free(flat_bytes);
const flat_hash = try repo.putRaw(flat_bytes);
defer gpa.free(flat_hash);
// 2. S-card TREE over the same set: store every emitted node, then a root
// whose S run replaces the F run.
var build = try artifact.buildTree(gpa, &cards, 1, .sha3_256);
defer build.deinit();
try testing.expect(!build.isFlat());
for (build.subs) |sub| {
const name = try repo.putRaw(sub.bytes);
gpa.free(name);
}
var tree_m = baseManifest("2020-01-02T00:00:00", null);
defer tree_m.deinit();
tree_m.s = build.s;
const tree_bytes = try artifact.create(&tree_m, gpa);
defer gpa.free(tree_bytes);
const tree_hash = try repo.putRaw(tree_bytes);
defer gpa.free(tree_hash);
// 3. DELTA manifest: baseline carries two of the cards, the delta patches
// in the third — same effective set.
var base_m = baseManifest("2020-01-03T00:00:00", null);
defer base_m.deinit();
base_m.f = cards[0..2];
const base_bytes = try artifact.create(&base_m, gpa);
defer gpa.free(base_bytes);
const base_hash = try repo.putRaw(base_bytes);
defer gpa.free(base_hash);
var delta_m = baseManifest("2020-01-04T00:00:00", null);
defer delta_m.deinit();
delta_m.b = .{ .hash = base_hash };
delta_m.f = cards[2..3];
const delta_bytes = try artifact.create(&delta_m, gpa);
defer gpa.free(delta_bytes);
const delta_hash = try repo.putRaw(delta_bytes);
defer gpa.free(delta_hash);
try repo.seal();
var r: Repository = undefined;
try Repository.open(&r, gpa, io, repo.tmp.dir, .{});
defer r.deinit(gpa);
var reference: std.ArrayList(artifact.FCard) = .empty;
defer reference.deinit(gpa);
for ([_][]const u8{ flat_hash, tree_hash, delta_hash }) |hash| {
const rid = r.lookup(hash) orelse return error.TestUnexpectedResult;
var fl = (try r.files(gpa, rid)) orelse return error.TestUnexpectedResult;
defer fl.deinit(gpa);
var got: std.ArrayList(artifact.FCard) = .empty;
defer got.deinit(gpa);
var it = fl.iterator();
while (it.next()) |f| try got.append(gpa, f);
try testing.expectEqual(@as(usize, 3), got.items.len);
if (reference.items.len == 0) {
try reference.appendSlice(gpa, got.items);
// Reference cards borrow fl — dupe names for later comparison.
for (reference.items) |*card| {
card.filename = try gpa.dupe(u8, card.filename);
card.hash = try gpa.dupe(u8, card.hash.?);
}
} else {
for (reference.items, got.items) |want, gotc| {
try testing.expectEqualStrings(want.filename, gotc.filename);
try testing.expectEqualStrings(want.hash.?, gotc.hash.?);
}
}
}
for (reference.items) |card| {
gpa.free(card.filename);
gpa.free(card.hash.?);
}
reference.clearRetainingCapacity();
// The seam counter: the TREE enumeration went through flattenTree's memo
// (misses were recorded for its sub-manifests) — zero bespoke S walks —
// and DESIGN §12's parse bound holds: misses never exceed the distinct
// sub-manifests the tree actually holds.
const memo = &r.sub_memo.?;
try testing.expect(memo.misses >= 1);
try testing.expect(memo.misses <= build.subs.len);
}
// ---------------------------------------------------------------------------
// Translation (Task 5): diffs, marks, identity, fail-closed, constant state.
// ---------------------------------------------------------------------------
const fast_export = @import("git_fast_export.zig");
const TwoCommitFixture = struct {
repo: FixtureRepo,
root_hash: []u8,
child_hash: []u8,
b_shared: []u8,
b_old: []u8,
b_new: []u8,
fn init(self: *TwoCommitFixture, io: std.Io) !void {
const gpa = testing.allocator;
try self.repo.init(io);
self.b_shared = try self.repo.putRaw("shared bytes\n");
self.b_old = try self.repo.putRaw("old child bytes\n");
self.b_new = try self.repo.putRaw("new child bytes\n");
var root_m = baseManifest("2020-01-01T00:00:00", null);
defer root_m.deinit();
root_m.f = &.{ fcard("keep.txt", self.b_shared), fcard("mut.txt", self.b_old) };
const root_bytes = try artifact.create(&root_m, gpa);
defer gpa.free(root_bytes);
self.root_hash = try self.repo.putRaw(root_bytes);
var child_m = baseManifest("2020-01-02T00:00:00", null);
defer child_m.deinit();
var pbuf: [1]artifact.PCard = .{.{ .parents = self.root_hash, .count = 1 }};
child_m.p = &pbuf;
child_m.t = &.{};
// The child rewrites mut.txt (same name, new blob), deletes nothing,
// adds add.txt reusing the SHARED blob (mark reuse across commits).
child_m.f = &.{ fcard("add.txt", self.b_shared), fcard("keep.txt", self.b_shared), fcard("mut.txt", self.b_new) };
const child_bytes = try artifact.create(&child_m, gpa);
defer gpa.free(child_bytes);
self.child_hash = try self.repo.putRaw(child_bytes);
try self.repo.seal();
}
fn deinit(self: *TwoCommitFixture) void {
const gpa = testing.allocator;
gpa.free(self.root_hash);
gpa.free(self.child_hash);
gpa.free(self.b_shared);
gpa.free(self.b_old);
gpa.free(self.b_new);
self.repo.cleanup();
}
};
test "git export translate: blobs once per distinct hash, root deleteall+full, child exact diff, C/D/U mapped" {
const io = testing.io;
const gpa = testing.allocator;
var fx: TwoCommitFixture = undefined;
try fx.init(io);
defer fx.deinit();
var r: Repository = undefined;
try Repository.open(&r, gpa, io, fx.repo.tmp.dir, .{});
defer r.deinit(gpa);
var t = export_impl.Translator.init(gpa);
defer t.deinit();
// Root: deleteall + both files; two blobs emitted.
var root = try t.translateCommit(&r, r.lookup(fx.root_hash).?);
defer root.deinit();
var blobs: usize = 0;
var commits: usize = 0;
for (root.events) |event| switch (event) {
.blob => blobs += 1,
.commit => |c| {
commits += 1;
try testing.expectEqualStrings("refs/heads/trunk", c.ref);
try testing.expect(c.from == null);
try testing.expectEqual(@as(usize, 0), c.merges.len);
try testing.expectEqual(@as(usize, 3), c.commands.len);
try testing.expectEqual(fast_export.FileCommand.delete_all, c.commands[0]);
try testing.expectEqualStrings("keep.txt", c.commands[1].modify.path);
try testing.expectEqualStrings("mut.txt", c.commands[2].modify.path);
// U login synthesized to <[email protected]>; D to epoch seconds.
try testing.expectEqualStrings("u", c.committer.name);
try testing.expectEqualStrings("[email protected]", c.committer.email);
try testing.expectEqual(@as(i64, 1577836800), c.committer.timestamp);
try testing.expectEqualStrings("c", c.message);
},
else => return error.TestUnexpectedResult,
};
try testing.expectEqual(@as(usize, 2), blobs);
try testing.expectEqual(@as(usize, 1), commits);
// Child: exactly the changed paths — one NEW blob (b_new), add.txt
// reuses the shared blob's existing mark, keep.txt untouched.
var child = try t.translateCommit(&r, r.lookup(fx.child_hash).?);
defer child.deinit();
blobs = 0;
for (child.events) |event| switch (event) {
.blob => blobs += 1,
.commit => |c| {
try testing.expect(c.from != null);
try testing.expectEqual(root.mark, c.from.?.mark);
try testing.expectEqual(@as(usize, 2), c.commands.len);
try testing.expectEqualStrings("add.txt", c.commands[0].modify.path);
try testing.expectEqualStrings("mut.txt", c.commands[1].modify.path);
},
else => return error.TestUnexpectedResult,
};
try testing.expectEqual(@as(usize, 1), blobs);
// Constant retained state: one entry per commit + one per distinct blob.
try testing.expectEqual(@as(usize, 2 + 3), t.retainedStateEntries());
}
test "git export translate: diff form and deleteall form replay to the same tree model" {
const io = testing.io;
const gpa = testing.allocator;
var fx: TwoCommitFixture = undefined;
try fx.init(io);
defer fx.deinit();
var r: Repository = undefined;
try Repository.open(&r, gpa, io, fx.repo.tmp.dir, .{});
defer r.deinit(gpa);
// Arm A: the translator's diff-form child commands, applied over the
// root's tree model.
var tree_a: std.StringHashMapUnmanaged(u64) = .empty;
defer {
var keys = tree_a.keyIterator();
while (keys.next()) |k| gpa.free(k.*);
tree_a.deinit(gpa);
}
{
var t = export_impl.Translator.init(gpa);
defer t.deinit();
var root = try t.translateCommit(&r, r.lookup(fx.root_hash).?);
defer root.deinit();
var child = try t.translateCommit(&r, r.lookup(fx.child_hash).?);
defer child.deinit();
for ([_][]const fast_export.Event{ root.events, child.events }) |events| {
for (events) |event| {
if (event != .commit) continue;
for (event.commit.commands) |command| switch (command) {
.delete_all => {
var keys = tree_a.keyIterator();
while (keys.next()) |k| gpa.free(k.*);
tree_a.clearRetainingCapacity();
},
.modify => |mod| {
const gop = try tree_a.getOrPut(gpa, mod.path);
if (!gop.found_existing) gop.key_ptr.* = try gpa.dupe(u8, mod.path);
gop.value_ptr.* = mod.data.mark;
},
.delete => |path| {
if (tree_a.fetchRemove(path)) |kv| gpa.free(kv.key);
},
else => return error.TestUnexpectedResult,
};
}
}
}
// Arm B: a full deleteall enumeration of the child, content-addressed —
// the same file names must map to blobs with the same CONTENT hashes.
const child_rid = r.lookup(fx.child_hash).?;
var fl = (try r.files(gpa, child_rid)) orelse return error.TestUnexpectedResult;
defer fl.deinit(gpa);
var count: usize = 0;
var it = fl.iterator();
while (it.next()) |card| {
count += 1;
try testing.expect(tree_a.contains(card.filename));
}
try testing.expectEqual(count, tree_a.count());
}
test "git export fail-closed: a .git path segment refuses, naming the check-in and the path" {
const io = testing.io;
const gpa = testing.allocator;
var repo: FixtureRepo = undefined;
try repo.init(io);
defer repo.cleanup();
const b1 = try repo.putRaw("payload\n");
defer gpa.free(b1);
var m = baseManifest("2020-01-01T00:00:00", null);
defer m.deinit();
m.f = &.{fcard(".git/config", b1)};
const bytes = try artifact.create(&m, gpa);
defer gpa.free(bytes);
const hash = try repo.putRaw(bytes);
defer gpa.free(hash);
try repo.seal();
var r: Repository = undefined;
try Repository.open(&r, gpa, io, repo.tmp.dir, .{});
defer r.deinit(gpa);
var t = export_impl.Translator.init(gpa);
defer t.deinit();
try testing.expectError(error.ForbiddenPath, t.translateCommit(&r, r.lookup(hash).?));
try testing.expectEqualStrings(hash, t.fault.hashText());
try testing.expectEqualStrings(".git/config", t.fault.pathText());
}
test "git export fail-closed: dot, dotdot, and empty segments each refuse; sound paths pass" {
var fault: export_impl.Fault = .{};
try testing.expectError(error.ForbiddenPath, export_impl.validatePathForGit(&fault, "a/./b"));
try testing.expectError(error.ForbiddenPath, export_impl.validatePathForGit(&fault, "a/../b"));
try testing.expectError(error.ForbiddenPath, export_impl.validatePathForGit(&fault, "a//b"));
try testing.expectError(error.ForbiddenPath, export_impl.validatePathForGit(&fault, ""));
try testing.expectError(error.ForbiddenPath, export_impl.validatePathForGit(&fault, ".GIT/x"));
try export_impl.validatePathForGit(&fault, "ordinary/path.txt");
try export_impl.validatePathForGit(&fault, ".gitignore"); // a FILE named .gitignore is fine
}
test "git export refs: branch names sanitize per git-check-ref-format, deterministically" {
const gpa = testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
try testing.expectEqualStrings("refs/heads/trunk", try export_impl.refForBranch(arena, "trunk"));
try testing.expectEqualStrings("refs/heads/a-b", try export_impl.refForBranch(arena, "a b"));
try testing.expectEqualStrings("refs/heads/a-b", try export_impl.refForBranch(arena, "a:b"));
try testing.expectEqualStrings("refs/heads/_dash", try export_impl.refForBranch(arena, "-dash"));
try testing.expectEqualStrings("refs/heads/a.-b", try export_impl.refForBranch(arena, "a..b"));
try testing.expectEqualStrings("refs/heads/at{brace", try export_impl.refForBranch(arena, "at{brace")); // bare { is legal
try testing.expectEqualStrings("refs/heads/a@-b", try export_impl.refForBranch(arena, "a@{b")); // the @{ SEQUENCE is not
try testing.expectEqualStrings("refs/heads/v1.lock-", try export_impl.refForBranch(arena, "v1.lock"));
try testing.expectEqualStrings("refs/heads/unnamed", try export_impl.refForBranch(arena, ""));
try testing.expectEqualStrings("refs/heads/end-", try export_impl.refForBranch(arena, "end."));
}
test "git export fail-closed: a phantom primary parent refuses, naming both the check-in and the missing parent" {
// The libfossil corpus shape: an incomplete clone whose lineage crosses
// a parent manifest the store never received (shunned or private
// upstream). The diff has nothing to diff against — fail closed, with
// both names in the refusal.
const io = testing.io;
const gpa = testing.allocator;
var repo: FixtureRepo = undefined;
try repo.init(io);
defer repo.cleanup();
const b1 = try repo.putRaw("content\n");
defer gpa.free(b1);
const absent_parent = "e" ** 64;
var m = baseManifest("2020-01-02T00:00:00", null);
defer m.deinit();
var pbuf: [1]artifact.PCard = .{.{ .parents = absent_parent, .count = 1 }};
m.p = &pbuf;
m.t = &.{};
m.f = &.{fcard("a.txt", b1)};
const bytes = try artifact.create(&m, gpa);
defer gpa.free(bytes);
const child = try repo.putRaw(bytes);
defer gpa.free(child);
try repo.seal();
var r: Repository = undefined;
try Repository.open(&r, gpa, io, repo.tmp.dir, .{});
defer r.deinit(gpa);
var t = export_impl.Translator.init(gpa);
defer t.deinit();
try testing.expectError(error.ParentUnreadable, t.translateCommit(&r, r.lookup(child).?));
try testing.expectEqualStrings(child, t.fault.hashText());
try testing.expectEqualStrings(absent_parent, t.fault.pathText());
}