//! The change set between two check-ins' file sets, read in proportion to
//! what changed rather than to the size of either tree.
//!
//! Both sides are walked together in canonical name order. A side is a tree
//! check-in's S run (draft-fossil-submanifests-00 §3.6) or the effective F
//! cards of a flat or delta one (artifact §8.2). Two sub-manifest slots met at
//! the same name with the same hash hold the same files, so both are stepped
//! over unread; any other slot is opened only when its first name is the next
//! one the comparison needs. The rows are exactly a linear walk over the two
//! flattened lists: removed, added, or modified when content or mode differs,
//! in byte order of the path.
//!
//! The side-by-side walk over two S runs is libfossil's
//! (`fsl__deck_tree_diff`, src/deck.c), which `repoview`'s change index also
//! follows.
const std = @import("std");
const artifact = @import("artifact.zig");
const FCard = artifact.FCard;
const SCard = artifact.SCard;
pub const State = enum { added, modified, removed };
pub const Row = struct {
state: State,
name: []const u8,
/// The `from` side's content; null when added.
parent: ?[]const u8,
/// The `to` side's card; null when removed.
to_card: ?FCard,
};
/// One check-in's file set as the walk reads it.
pub const Side = union(enum) {
/// A tree check-in's own S cards.
tree: []const SCard,
/// A flat or delta check-in's merge walk; hash-less delete markers are
/// skipped as `Repository.EffectiveFiles` skips them.
files: artifact.MergeWalk,
};
pub const Error = artifact.TreeError || error{OutOfMemory};
/// Append to `out` the rows from `from` to `to`. The rows borrow the sides'
/// cards and the resolver's views, so they live as long as both do. A fault
/// in a sub-manifest the comparison had to read fails the whole diff, as it
/// fails the flatten; a slot stepped over is not read, so nothing inside it
/// can.
pub fn diff(gpa: std.mem.Allocator, from: Side, to: Side, resolver: artifact.SubResolver, out: *std.ArrayList(Row)) Error!void {
var a = Cursor.init(from, resolver);
var b = Cursor.init(to, resolver);
// Every pass consumes one item or opens one slot, and each slot of
// either tree is opened at most once, so the loop ends.
while (true) {
const ia = try a.head();
const ib = try b.head();
if (ia == null and ib == null) return;
// An exhausted side sorts after everything the other still holds.
const order: std.math.Order = if (ia == null) .gt else if (ib == null) .lt else artifact.compareBytes(ia.?.name(), ib.?.name());
if (ia != null and ib != null and ia.? == .sub and ib.? == .sub and order == .eq) {
const sa = ia.?.sub;
const sb = ib.?.sub;
if (std.mem.eql(u8, sa.hash, sb.hash)) {
// The same artifact: the same files, all equal.
try a.skip();
try b.skip();
continue;
}
// Two different slots starting at one name. When one is a leaf
// and the other is not, the taller tree is opened alone, so trees
// of different heights still meet at the nodes they share.
const va = try a.view(sa);
const vb = try b.view(sb);
const a_leaf = va.subs.len == 0;
const b_leaf = vb.subs.len == 0;
if (!a_leaf or b_leaf) try a.open(sa, va);
if (!b_leaf or a_leaf) try b.open(sb, vb);
continue;
}
// A slot whose first name is at or below the other side's next name
// may hold that name, or names before it: open it.
if (ia != null and ia.? == .sub and order != .gt) {
try a.open(ia.?.sub, try a.view(ia.?.sub));
continue;
}
if (ib != null and ib.? == .sub and order != .lt) {
try b.open(ib.?.sub, try b.view(ib.?.sub));
continue;
}
// Whatever is left heads with a file on the lower side; a slot on the
// other side starts strictly after it.
switch (order) {
.lt => {
const f = ia.?.file;
try a.skip();
try out.append(gpa, .{ .state = .removed, .name = f.filename, .parent = f.hash, .to_card = null });
},
.gt => {
const f = ib.?.file;
try b.skip();
try out.append(gpa, .{ .state = .added, .name = f.filename, .parent = null, .to_card = f });
},
.eq => {
const x = ia.?.file;
const y = ib.?.file;
try a.skip();
try b.skip();
if (x.mode != y.mode or !std.mem.eql(u8, x.hash.?, y.hash.?))
try out.append(gpa, .{ .state = .modified, .name = y.filename, .parent = x.hash, .to_card = y });
},
}
}
}
const Item = union(enum) {
file: FCard,
/// A slot not yet read: a whole subtree whose first name is the card's.
sub: SCard,
fn name(self: Item) []const u8 {
return switch (self) {
.file => |f| f.filename,
.sub => |s| s.filename,
};
}
};
/// One side of the walk. For a tree it keeps `TreeWalk`'s frame stack and
/// its §5.1 checks on every node it reads: the depth bound and cycle check
/// before the read, the first-name identity after it, and strict order over
/// every name it passes. A slot stepped over advances LAST to its first name
/// only, since its last is never read.
const Cursor = struct {
resolver: artifact.SubResolver,
flat: ?artifact.MergeWalk,
flat_head: ?FCard = null,
frames: [artifact.max_tree_depth + 1]Frame = undefined,
n_frames: usize = 0,
leaf: []const FCard = &.{},
leaf_i: usize = 0,
last: ?[]const u8 = null,
const Frame = struct {
subs: []const SCard,
cursor: usize,
/// Null for the manifest's own frame.
hash: ?[]const u8,
};
fn init(side: Side, resolver: artifact.SubResolver) Cursor {
switch (side) {
.files => |walk| {
var c: Cursor = .{ .resolver = resolver, .flat = walk };
c.flat_head = c.nextFlat();
return c;
},
.tree => |subs| {
var c: Cursor = .{ .resolver = resolver, .flat = null };
if (subs.len != 0) {
c.frames[0] = .{ .subs = subs, .cursor = 0, .hash = null };
c.n_frames = 1;
}
return c;
},
}
}
fn nextFlat(self: *Cursor) ?FCard {
while (self.flat.?.next()) |f| {
if (f.hash != null) return f; // §4.7.6: a hash-less card is a delete marker
}
return null;
}
fn head(self: *Cursor) artifact.TreeError!?Item {
if (self.flat != null) return if (self.flat_head) |f| .{ .file = f } else null;
if (self.leaf_i < self.leaf.len) return .{ .file = self.leaf[self.leaf_i] };
while (self.n_frames != 0) {
const top = &self.frames[self.n_frames - 1];
if (top.cursor < top.subs.len) return .{ .sub = top.subs[top.cursor] };
self.n_frames -= 1;
}
return null;
}
/// Pass the head item: a file compared, or a slot both sides share.
fn skip(self: *Cursor) artifact.TreeError!void {
if (self.flat != null) {
self.flat_head = self.nextFlat();
return;
}
const name = if (self.leaf_i < self.leaf.len) blk: {
const f = self.leaf[self.leaf_i];
self.leaf_i += 1;
break :blk f.filename;
} else blk: {
const top = &self.frames[self.n_frames - 1];
const sc = top.subs[top.cursor];
top.cursor += 1;
break :blk sc.filename;
};
if (!self.after(name)) return error.OrderViolation;
self.last = name;
}
/// The sub-manifest `sc` names, read under §5.1 step 3's checks.
fn view(self: *Cursor, sc: SCard) artifact.TreeError!artifact.SubManifestView {
if (!self.after(sc.filename)) return error.OrderViolation;
if (self.n_frames > artifact.max_tree_depth) return error.DepthExceeded;
for (self.frames[0..self.n_frames]) |fr| {
const h = fr.hash orelse continue;
if (std.mem.eql(u8, h, sc.hash)) return error.ReferenceCycle;
}
const v = self.resolver.resolveFn(self.resolver.ctx, sc.hash) orelse return error.SubUnresolvable; // §5.2
// §4.4: F cards or S cards, never both, never neither.
if ((v.subs.len == 0) == (v.files.len == 0)) return error.SubUnresolvable;
const first = if (v.subs.len == 0) v.files[0].filename else v.subs[0].filename;
if (!std.mem.eql(u8, first, sc.filename)) return error.FirstFilenameMismatch; // §5.1 steps 4 and 5
return v;
}
/// Replace the head slot `sc` with the node `v` it names.
fn open(self: *Cursor, sc: SCard, v: artifact.SubManifestView) artifact.TreeError!void {
std.debug.assert(self.flat == null and self.leaf_i == self.leaf.len);
const top = &self.frames[self.n_frames - 1];
std.debug.assert(top.subs[top.cursor].filename.ptr == sc.filename.ptr);
top.cursor += 1;
if (v.subs.len == 0) {
self.leaf = v.files;
self.leaf_i = 0;
return;
}
std.debug.assert(self.n_frames < self.frames.len); // `view` checked the depth
self.frames[self.n_frames] = .{ .subs = v.subs, .cursor = 0, .hash = sc.hash };
self.n_frames += 1;
}
fn after(self: *const Cursor, name: []const u8) bool {
const last = self.last orelse return true;
return artifact.compareBytes(last, name) == .lt;
}
};
// ---------------------------------------------------------------------------
// Tests: a fixed node table; the differential test over real stores is in
// tree_diff_test.zig.
// ---------------------------------------------------------------------------
const testing = std.testing;
const Node = struct { hash: []const u8, view: artifact.SubManifestView };
const Table = struct {
nodes: []const Node,
reads: usize = 0,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
const self: *Table = @ptrCast(@alignCast(ctx));
self.reads += 1;
for (self.nodes) |n| if (std.mem.eql(u8, n.hash, hash)) return n.view;
return null;
}
fn resolver(self: *Table) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = resolve };
}
};
fn card(name: []const u8, hash: []const u8) FCard {
return .{ .filename = name, .hash = hash, .perm = null, .old_name = null, .mode = .regular };
}
fn flatSide(cards: []const FCard) Side {
return .{ .files = .{ .baseline = cards, .delta = &.{} } };
}
fn expectRows(want: []const Row, got: []const Row) !void {
try testing.expectEqual(want.len, got.len);
for (want, got) |w, g| {
try testing.expectEqual(w.state, g.state);
try testing.expectEqualStrings(w.name, g.name);
if (w.parent) |p| try testing.expectEqualStrings(p, g.parent.?) else try testing.expect(g.parent == null);
if (w.to_card) |c| try testing.expectEqualStrings(c.hash.?, g.to_card.?.hash.?) else try testing.expect(g.to_card == null);
}
}
test "tree diff: a shared slot is never read; a changed leaf yields its changed files" {
const none = [_]SCard{};
const a1 = [_]FCard{ card("a/1", "h1"), card("a/2", "h2") };
const a2 = [_]FCard{ card("a/1", "h1"), card("a/2", "h9") };
const b1 = [_]FCard{card("b/1", "h3")};
var table = Table{ .nodes = &.{
.{ .hash = "A1", .view = .{ .files = &a1, .subs = &none } },
.{ .hash = "A2", .view = .{ .files = &a2, .subs = &none } },
.{ .hash = "B", .view = .{ .files = &b1, .subs = &none } },
} };
const from = [_]SCard{ .{ .filename = "a/1", .hash = "A1" }, .{ .filename = "b/1", .hash = "B" } };
const to = [_]SCard{ .{ .filename = "a/1", .hash = "A2" }, .{ .filename = "b/1", .hash = "B" } };
var out: std.ArrayList(Row) = .empty;
defer out.deinit(testing.allocator);
try diff(testing.allocator, .{ .tree = &from }, .{ .tree = &to }, table.resolver(), &out);
try expectRows(&.{.{ .state = .modified, .name = "a/2", .parent = "h2", .to_card = card("a/2", "h9") }}, out.items);
try testing.expectEqual(@as(usize, 2), table.reads);
}
test "tree diff: a tree of a different height meets the other at the leaf they share" {
const none = [_]SCard{};
const l1 = [_]FCard{ card("a", "h1"), card("b", "h2") };
const l2 = [_]FCard{ card("c", "h3"), card("d", "h4") };
const l2x = [_]FCard{ card("c", "h3"), card("d", "h5") };
const inner = [_]SCard{ .{ .filename = "a", .hash = "L1" }, .{ .filename = "c", .hash = "L2X" } };
var table = Table{ .nodes = &.{
.{ .hash = "L1", .view = .{ .files = &l1, .subs = &none } },
.{ .hash = "L2", .view = .{ .files = &l2, .subs = &none } },
.{ .hash = "L2X", .view = .{ .files = &l2x, .subs = &none } },
.{ .hash = "I", .view = .{ .files = &.{}, .subs = &inner } },
} };
const from = [_]SCard{ .{ .filename = "a", .hash = "L1" }, .{ .filename = "c", .hash = "L2" } };
const to = [_]SCard{.{ .filename = "a", .hash = "I" }};
var out: std.ArrayList(Row) = .empty;
defer out.deinit(testing.allocator);
try diff(testing.allocator, .{ .tree = &from }, .{ .tree = &to }, table.resolver(), &out);
try expectRows(&.{.{ .state = .modified, .name = "d", .parent = "h4", .to_card = card("d", "h5") }}, out.items);
// Against the flat list of the same files, every slot is opened.
var flat_out: std.ArrayList(Row) = .empty;
defer flat_out.deinit(testing.allocator);
const flat = [_]FCard{ card("a", "h1"), card("b", "h2"), card("c", "h3"), card("d", "h4"), card("e", "h6") };
try diff(testing.allocator, flatSide(&flat), .{ .tree = &to }, table.resolver(), &flat_out);
try expectRows(&.{
.{ .state = .modified, .name = "d", .parent = "h4", .to_card = card("d", "h5") },
.{ .state = .removed, .name = "e", .parent = "h6", .to_card = null },
}, flat_out.items);
}
test "tree diff: an absent node the comparison needs fails it; a mode change with equal content is a change" {
const none = [_]SCard{};
const l1 = [_]FCard{card("a", "h1")};
var x = card("a", "h1");
x.mode = .executable;
x.perm = "x";
const l1x = [_]FCard{x};
var table = Table{ .nodes = &.{
.{ .hash = "L1", .view = .{ .files = &l1, .subs = &none } },
.{ .hash = "L1X", .view = .{ .files = &l1x, .subs = &none } },
} };
var out: std.ArrayList(Row) = .empty;
defer out.deinit(testing.allocator);
const from = [_]SCard{.{ .filename = "a", .hash = "L1" }};
const to = [_]SCard{.{ .filename = "a", .hash = "L1X" }};
try diff(testing.allocator, .{ .tree = &from }, .{ .tree = &to }, table.resolver(), &out);
try expectRows(&.{.{ .state = .modified, .name = "a", .parent = "h1", .to_card = x }}, out.items);
const gone = [_]SCard{.{ .filename = "a", .hash = "MISSING" }};
try testing.expectError(error.SubUnresolvable, diff(testing.allocator, .{ .tree = &from }, .{ .tree = &gone }, table.resolver(), &out));
// A missing node both sides share is never asked for.
out.clearRetainingCapacity();
try diff(testing.allocator, .{ .tree = &gone }, .{ .tree = &gone }, table.resolver(), &out);
try testing.expectEqual(@as(usize, 0), out.items.len);
}