//! `Repository.changesBetween` against `feed.FileSetDiff` over the two
//! flattened file sets, on every store shape a history can take: flat, the
//! delta-manifest dialect, SHA-1-named blobs, trees at k 1, 3 and 7, and a
//! history whose emission changes k and switches between tree and flat.
//! Each history is seeded-random puts, adds, deletes, renames (with and
//! without new bytes) and executable flips with the content unchanged (the
//! seed carries symlinks, which later steps delete), made through
//! the direct-commit core in-process; every pair of check-ins must give the
//! same rows, card for card, in the same order.
const std = @import("std");
const testing = std.testing;
const repeat = @import("repeat.zig").repeat;
const artifact = @import("artifact.zig");
const logstore = @import("logstore.zig");
const storage = @import("storage.zig");
const repocache = @import("repocache.zig");
const Repository = @import("repository.zig").Repository;
const checkin = @import("core/checkin.zig");
const feed = @import("core/feed.zig");
const seed_epoch: i64 = 1_700_000_000;
/// One phase of a history: the emission it runs under and its commits.
const Phase = struct {
/// Sub-manifest k; null emits flat manifests.
k: ?u4,
steps: usize,
};
const Shape = struct {
name: []const u8,
files: usize,
sha1: bool = false,
delta: bool = false,
phases: []const Phase,
};
const shapes = [_]Shape{
.{ .name = "flat", .files = 40, .phases = &.{.{ .k = null, .steps = 14 }} },
.{ .name = "delta dialect", .files = 40, .delta = true, .phases = &.{.{ .k = null, .steps = 14 }} },
.{ .name = "sha1 names", .files = 40, .sha1 = true, .phases = &.{.{ .k = null, .steps = 10 }} },
.{ .name = "sha1 names k=3", .files = 60, .sha1 = true, .phases = &.{.{ .k = 3, .steps = 10 }} },
.{ .name = "k=1", .files = 40, .phases = &.{.{ .k = 1, .steps = 14 }} },
.{ .name = "k=3", .files = 80, .phases = &.{.{ .k = 3, .steps = 14 }} },
.{ .name = "k=7", .files = 700, .phases = &.{.{ .k = 7, .steps = 10 }} },
.{ .name = "k changes", .files = 120, .phases = &.{
.{ .k = 3, .steps = 5 },
.{ .k = 1, .steps = 4 },
.{ .k = null, .steps = 4 },
.{ .k = 5, .steps = 4 },
} },
.{ .name = "delta then tree", .files = 60, .delta = true, .phases = &.{
.{ .k = null, .steps = 5 },
.{ .k = 2, .steps = 5 },
} },
};
test "changesBetween: every pair of check-ins gives FileSetDiff's rows over the flattened sets, on every store shape" {
const gpa = testing.allocator;
for (shapes, 0..) |shape, i| {
var h: History = undefined;
try h.init(gpa, shape);
defer h.deinit();
var prng = std.Random.DefaultPrng.init(0x7d1f_0000 + i);
for (shape.phases) |phase| {
try h.setEmission(phase.k);
for (0..phase.steps) |_| try h.randomStep(prng.random());
}
var repo: Repository = undefined;
try repo.open(gpa, testing.io, h.tmp.dir, .{ .mode = .full, .bypass_cache = true });
defer repo.deinit(gpa);
try h.expectShape(&repo);
for (h.names.items) |x| for (h.names.items) |y| try expectSameRows(&repo, shape.name, x, y);
}
}
test "changesBetween: a store cone defers to the whole lists" {
const gpa = testing.allocator;
var h: History = undefined;
try h.init(gpa, .{ .name = "cone", .files = 60, .phases = &.{} });
defer h.deinit();
try h.setEmission(3);
var prng = std.Random.DefaultPrng.init(7);
for (0..3) |_| try h.randomStep(prng.random());
var cone = try @import("cone.zig").Cone.parse(gpa, "\x01\x02\x00d1");
defer cone.deinit(gpa);
repocache.writeStoreCone(gpa, testing.io, h.tmp.dir, &cone);
var repo: Repository = undefined;
try repo.open(gpa, testing.io, h.tmp.dir, .{ .mode = .full, .bypass_cache = true });
defer repo.deinit(gpa);
const a = repo.lookup(h.names.items[0]).?;
const b = repo.lookup(h.names.items[3]).?;
try testing.expect((try repo.changesBetween(gpa, a, b)) == null);
}
test "changesBetween: a missing node the comparison needs defers to the whole lists, which report it; one both trees share is not met" {
const gpa = testing.allocator;
var h: History = undefined;
try h.init(gpa, .{ .name = "phantom", .files = 0, .phases = &.{} });
defer h.deinit();
const none = repeat("0", 64);
const l1 = try h.putLeaf(&.{ .{ "a/1", "x1" }, .{ "a/2", "x2" } });
const l1b = try h.putLeaf(&.{ .{ "a/1", "x1" }, .{ "a/2", "x3" } });
const shared_phantom = [_]artifact.SCard{ .{ .filename = "a/1", .hash = l1 }, .{ .filename = "b/1", .hash = none } };
const changed_phantom = [_]artifact.SCard{ .{ .filename = "a/1", .hash = l1b }, .{ .filename = "b/1", .hash = none } };
const needs_phantom = [_]artifact.SCard{ .{ .filename = "a/1", .hash = l1 }, .{ .filename = "b/1", .hash = repeat("1", 64) } };
const m1 = try h.putTree(&shared_phantom, "2023-01-01T00:00:00.000");
const m2 = try h.putTree(&changed_phantom, "2023-01-02T00:00:00.000");
const m3 = try h.putTree(&needs_phantom, "2023-01-03T00:00:00.000");
var repo: Repository = undefined;
try repo.open(gpa, testing.io, h.tmp.dir, .{ .mode = .full, .bypass_cache = true });
defer repo.deinit(gpa);
const r1 = repo.lookup(m1).?;
const r2 = repo.lookup(m2).?;
const r3 = repo.lookup(m3).?;
var got = (try repo.changesBetween(gpa, r1, r2)) orelse return error.TestUnexpectedResult;
defer got.deinit();
try testing.expectEqual(@as(usize, 1), got.rows.len);
try testing.expectEqualStrings("a/2", got.rows[0].name);
try testing.expectEqual(feed.State.modified, got.rows[0].state);
try testing.expectError(error.BaselineUnresolvable, repo.filesWithPrefix(gpa, r1, ""));
try testing.expect((try repo.changesBetween(gpa, r1, r3)) == null);
}
fn expectSameRows(repo: *Repository, shape: []const u8, x: []const u8, y: []const u8) !void {
const gpa = testing.allocator;
const a = repo.lookup(x).?;
const b = repo.lookup(y).?;
var got = (try repo.changesBetween(gpa, a, b)) orelse {
std.debug.print("\n[{s}] {s}..{s}: changesBetween did not settle\n", .{ shape, x[0..10], y[0..10] });
return error.TestUnexpectedResult;
};
defer got.deinit();
var la = (try repo.filesWithPrefix(gpa, a, "")).?;
defer la.deinit(gpa);
var lb = (try repo.filesWithPrefix(gpa, b, "")).?;
defer lb.deinit(gpa);
var walk: feed.FileSetDiff = .init(la.iterator(), lb.iterator());
var i: usize = 0;
while (walk.next()) |want| : (i += 1) {
if (i >= got.rows.len or !sameRow(want, got.rows[i])) {
std.debug.print("\n[{s}] {s}..{s}: row {d} differs: want {s} {s}\n", .{ shape, x[0..10], y[0..10], i, @tagName(want.state), want.name });
if (i < got.rows.len) std.debug.print(" got {s} {s}\n", .{ @tagName(got.rows[i].state), got.rows[i].name });
return error.TestUnexpectedResult;
}
}
try testing.expectEqual(i, got.rows.len);
}
fn sameRow(w: feed.FileSetDiff.Row, g: feed.FileSetDiff.Row) bool {
if (w.state != g.state or !std.mem.eql(u8, w.name, g.name)) return false;
if (!eqlOpt(w.parent, g.parent)) return false;
if ((w.to_card == null) != (g.to_card == null)) return false;
const wc = w.to_card orelse return true;
const gc = g.to_card.?;
return std.mem.eql(u8, wc.filename, gc.filename) and eqlOpt(wc.hash, gc.hash) and
eqlOpt(wc.perm, gc.perm) and eqlOpt(wc.old_name, gc.old_name) and wc.mode == gc.mode;
}
fn eqlOpt(a: ?[]const u8, b: ?[]const u8) bool {
if (a == null or b == null) return a == null and b == null;
return std.mem.eql(u8, a.?, b.?);
}
const ModelFile = struct { path: []const u8, content: []const u8, mode: artifact.FileMode };
/// A store in a temporary directory, its current file set, and every
/// check-in it recorded.
const History = struct {
gpa: std.mem.Allocator,
tmp: testing.TmpDir,
arena: std.heap.ArenaAllocator,
shape: Shape,
model: std.ArrayList(ModelFile) = .empty,
names: std.ArrayList([]const u8) = .empty,
step_no: usize = 0,
/// Initializes in place. A shape with files gets a seed check-in written
/// straight into the log, so SHA-1 names are possible.
fn init(self: *History, gpa: std.mem.Allocator, shape: Shape) !void {
self.* = .{ .gpa = gpa, .tmp = testing.tmpDir(.{}), .arena = .init(gpa), .shape = shape };
errdefer self.deinit();
const first_k: ?u4 = if (shape.phases.len != 0) shape.phases[0].k else null;
var log_file: OpenLog = undefined;
try self.openLog(&log_file, true);
defer log_file.close();
try log_file.log.putConfig(.{
.hash_policy = 0,
.default_branch = "trunk",
.project_id = "",
.enable_submanifests = first_k != null,
.submanifest_k = first_k orelse 0,
.seen_delta_manifest = shape.delta,
});
if (shape.files != 0) try self.writeSeed(&log_file.log, first_k);
try log_file.log.commit();
}
fn deinit(self: *History) void {
self.arena.deinit();
self.tmp.cleanup();
}
const OpenLog = struct {
file: std.Io.File,
fs: storage.FileStorage,
log: logstore.LogStore,
fn close(self: *OpenLog) void {
self.log.deinit(testing.allocator);
self.file.close(testing.io);
}
};
/// In place: the log borrows `out.fs`, so it cannot be returned by value.
fn openLog(self: *History, out: *OpenLog, create: bool) !void {
out.file = if (create)
try self.tmp.dir.createFile(testing.io, ".zit", .{ .read = true })
else
try self.tmp.dir.openFile(testing.io, ".zit", .{ .mode = .read_write });
errdefer out.file.close(testing.io);
const size = (try out.file.stat(testing.io)).size;
out.fs = storage.FileStorage.init(testing.io, out.file, size);
out.log = try logstore.LogStore.open(self.gpa, out.fs.storageFile(), 0);
}
/// Re-pin the emission, as `zit submanifest retune` would.
fn setEmission(self: *History, k: ?u4) !void {
var held: OpenLog = undefined;
try self.openLog(&held, false);
defer held.close();
var oc = (try held.log.readConfig(self.gpa)).?;
defer oc.deinit(self.gpa);
var cfg = oc.config;
cfg.enable_submanifests = k != null;
cfg.submanifest_k = k orelse 0;
try held.log.putConfig(cfg);
try held.log.commit();
}
fn writeSeed(self: *History, log: *logstore.LogStore, k: ?u4) !void {
const a = self.arena.allocator();
const algo: artifact.HashAlgo = if (self.shape.sha1) .sha1 else .sha3_256;
var cards: std.ArrayList(artifact.FCard) = .empty;
for (0..self.shape.files) |i| {
const path = try std.fmt.allocPrint(a, "d{d}/s{d}/f{d}.txt", .{ i % 7, i % 3, i });
const content = try std.fmt.allocPrint(a, "seed {s}\n", .{path});
const mode: artifact.FileMode = if (i % 11 == 0) .executable else if (i % 13 == 5) .symlink else .regular;
try self.model.append(a, .{ .path = path, .content = content, .mode = mode });
var name_buf: [64]u8 = undefined;
const name = artifact.artifactName(algo, content, &name_buf);
var digest: [32]u8 = undefined;
const raw = digest[0 .. name.len / 2];
_ = try std.fmt.hexToBytes(raw, name);
_ = try log.put(raw, content);
try cards.append(a, .{ .filename = path, .hash = try a.dupe(u8, name), .perm = switch (mode) {
.executable => "x",
.symlink => "l",
.regular => null,
}, .old_name = null, .mode = mode });
}
std.mem.sort(artifact.FCard, cards.items, {}, struct {
fn less(_: void, x: artifact.FCard, y: artifact.FCard) bool {
return artifact.compareBytes(x.filename, y.filename) == .lt;
}
}.less);
var s_cards: []const artifact.SCard = &.{};
var f_cards: []const artifact.FCard = cards.items;
var tree: ?artifact.TreeBuild = null;
defer if (tree) |*t| t.deinit();
if (k) |kk| {
tree = try artifact.buildTree(self.gpa, cards.items, kk, .sha3_256);
if (!tree.?.isFlat()) {
for (tree.?.subs) |sub| {
var sd: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(sub.bytes, &sd, .{});
_ = try log.put(&sd, sub.bytes);
}
s_cards = tree.?.s;
f_cards = &.{};
}
}
try self.names.append(a, try putManifest(a, log, f_cards, s_cards, "2023-01-01T00:00:00.000", "seed"));
}
/// A leaf of `pairs` (name, content), stored; its name.
fn putLeaf(self: *History, pairs: []const [2][]const u8) ![]const u8 {
const a = self.arena.allocator();
var cards: std.ArrayList(artifact.FCard) = .empty;
for (pairs) |p| {
var name_buf: [64]u8 = undefined;
const name = try a.dupe(u8, artifact.artifactName(.sha3_256, p[1], &name_buf));
try cards.append(a, .{ .filename = p[0], .hash = name, .perm = null, .old_name = null, .mode = .regular });
}
const bytes = try artifact.serializeSubmanifestLeaf(a, cards.items);
var held: OpenLog = undefined;
try self.openLog(&held, false);
defer held.close();
var sd: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(bytes, &sd, .{});
_ = try held.log.put(&sd, bytes);
try held.log.commit();
return a.dupe(u8, &std.fmt.bytesToHex(sd, .lower));
}
fn putTree(self: *History, subs: []const artifact.SCard, ts: []const u8) ![]const u8 {
const a = self.arena.allocator();
var held: OpenLog = undefined;
try self.openLog(&held, false);
defer held.close();
const name = try putManifest(a, &held.log, &.{}, subs, ts, "tree");
try held.log.commit();
return name;
}
fn randomStep(self: *History, random: std.Random) !void {
const a = self.arena.allocator();
var edits: std.ArrayList(checkin.Edit) = .empty;
var touched: std.StringHashMapUnmanaged(void) = .empty;
const want = 1 + random.uintLessThan(usize, 6);
var tries: usize = 0;
while (edits.items.len < want and tries < 64) : (tries += 1) {
const salt = edits.items.len;
const roll = random.uintLessThan(u8, 100);
if (self.model.items.len == 0 or roll < 15) {
const path = try std.fmt.allocPrint(a, "d{d}/n{d}_{d}.txt", .{ random.uintLessThan(usize, 9), self.step_no, salt });
if (touched.contains(path) or self.indexOf(path) != null) continue;
try touched.put(a, path, {});
try edits.append(a, .{ .put = .{ .path = path, .bytes = try self.fresh(path, salt) } });
continue;
}
const pick = self.model.items[random.uintLessThan(usize, self.model.items.len)];
if (touched.contains(pick.path)) continue;
// The core records regular and executable files; a seed symlink
// can only leave.
if (pick.mode == .symlink and (roll < 65 or roll >= 80)) continue;
if (roll < 50) {
try touched.put(a, pick.path, {});
try edits.append(a, .{ .put = .{ .path = pick.path, .bytes = try self.fresh(pick.path, salt), .mode = pick.mode } });
} else if (roll < 65) {
// The same bytes under another mode: still a change.
try touched.put(a, pick.path, {});
const mode: artifact.FileMode = if (pick.mode == .regular) .executable else .regular;
try edits.append(a, .{ .put = .{ .path = pick.path, .bytes = pick.content, .mode = mode } });
} else if (roll < 80) {
if (self.model.items.len < 8) continue;
try touched.put(a, pick.path, {});
try edits.append(a, .{ .delete = pick.path });
} else {
const new = try std.fmt.allocPrint(a, "{s}/r{d}_{d}.txt", .{ std.fs.path.dirname(pick.path) orelse "top", self.step_no, salt });
if (touched.contains(new) or self.indexOf(new) != null) continue;
try touched.put(a, pick.path, {});
try touched.put(a, new, {});
const bytes: ?[]const u8 = if (random.boolean()) try self.fresh(new, salt) else null;
try edits.append(a, .{ .rename = .{ .old = pick.path, .new = new, .bytes = bytes, .mode = pick.mode } });
}
}
try testing.expect(edits.items.len != 0);
try self.commit(edits.items);
}
fn fresh(self: *History, path: []const u8, salt: usize) ![]const u8 {
return std.fmt.allocPrint(self.arena.allocator(), "{s} at step {d}.{d}\n", .{ path, self.step_no, salt });
}
fn indexOf(self: *const History, path: []const u8) ?usize {
for (self.model.items, 0..) |f, i| if (std.mem.eql(u8, f.path, path)) return i;
return null;
}
fn commit(self: *History, edits: []const checkin.Edit) !void {
const a = self.arena.allocator();
self.step_no += 1;
var diag: checkin.Diag = .{};
var ctx: checkin.Context = undefined;
try ctx.open(self.gpa, testing.io, self.tmp.dir, .{}, &diag);
defer ctx.deinit();
const outcome = checkin.commit(&ctx, .{
.user = "u",
.comment = try std.fmt.allocPrint(a, "step {d}", .{self.step_no}),
.now = .{ .epoch = seed_epoch + @as(i64, @intCast(self.step_no)) },
.edits = edits,
}, &diag) catch |e| {
std.debug.print("\n[{s}] commit refused: {s}: {s}\n", .{ self.shape.name, @errorName(e), diag.text() });
return e;
};
const name = switch (outcome) {
.recorded => |n| n,
else => return error.TestUnexpectedResult,
};
try self.names.append(a, try a.dupe(u8, name.slice()));
for (edits) |e| switch (e) {
.put => |p| if (self.indexOf(p.path)) |i| {
self.model.items[i].content = p.bytes;
if (p.mode) |m| self.model.items[i].mode = m;
} else try self.model.append(a, .{ .path = p.path, .content = p.bytes, .mode = p.mode orelse .regular }),
.delete => |path| _ = self.model.orderedRemove(self.indexOf(path).?),
.rename => |r| {
const i = self.indexOf(r.old).?;
self.model.items[i].path = r.new;
if (r.bytes) |b| self.model.items[i].content = b;
},
};
}
/// The history holds what its shape promises: tree check-ins with S
/// cards under a tree phase, delta manifests in the dialect.
fn expectShape(self: *History, repo: *Repository) !void {
var trees: usize = 0;
var deltas: usize = 0;
var flats: usize = 0;
for (self.names.items) |name| {
var m = (try repo.manifest(self.gpa, repo.lookup(name).?)).?;
defer m.deinit(self.gpa);
if (m.manifest.s.len != 0) trees += 1 else if (m.manifest.b != null) deltas += 1 else flats += 1;
}
var wants_tree = false;
var wants_flat = false;
for (self.shape.phases) |p| {
if (p.k != null) wants_tree = true else wants_flat = true;
}
if (wants_tree) try testing.expect(trees != 0);
if (wants_flat) try testing.expect(flats + deltas != 0);
if (self.shape.delta) try testing.expect(deltas != 0);
}
};
fn putManifest(a: std.mem.Allocator, log: *logstore.LogStore, f_cards: []const artifact.FCard, s_cards: []const artifact.SCard, ts: []const u8, comment: []const u8) ![]const u8 {
const tags = try artifact.composeCommitTags(a, .{ .branch = "trunk" });
var m: artifact.Manifest = .{
.arena_state = std.heap.ArenaAllocator.init(testing.allocator),
.kind = .manifest,
.a = null,
.b = null,
.c = .{ .comment = comment },
.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 = f_cards,
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = s_cards,
.t = tags,
};
defer m.deinit();
const bytes = try artifact.create(&m, testing.allocator);
defer testing.allocator.free(bytes);
var md: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(bytes, &md, .{});
_ = try log.put(&md, bytes);
return a.dupe(u8, &std.fmt.bytesToHex(md, .lower));
}