Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Two trees compared: both walked in step, in the order git sorts tree//! entries, passing over every subtree whose object ID is the same on both//! sides and every one a pathspec cannot reach, and yielding each entry//! that differs — added, deleted or modified — with its mode, object ID//! and path. It is what a history limited to paths asks of each commit,//! TREESAME or not, and what a diff starts from; it produces no text.//!//! Entries are what git calls leaves: files, symbolic links and gitlinks.//! A directory is never yielded itself; what is below it is. git sorts//! entries by name, a directory's name as if it ended in `/`, so a file//! `a` and a directory `a` are different entries: the file is deleted//! and what is in the directory added, as `git diff-tree -r` lists them.//! An entry whose mode changes, `100644` to `100755` or a file to a//! symbolic link, is modified. Modes are compared as git shows them, so//! two spellings of one mode are the same.//!//! A missing side, as for a root commit, is the empty tree, and so is the//! well-known empty tree when the object database does not hold it, as//! git knows it without reading it.
const std = @import("std");const Allocator = std.mem.Allocator;const Io = std.Io;
const object = @import("object.zig");const Id = object.Id;const Format = object.Format;const tree = @import("tree.zig");const ObjectDatabase = @import("ObjectDatabase.zig");const Diagnostics = @import("Diagnostics.zig");const Pathspec = @import("Pathspec.zig");
const TreeDiff = @This();
gpa: Allocator,io: Io,db: ObjectDatabase,format: Format,pathspec: *const Pathspec,frames: std.ArrayList(Frame) = .empty,path: std.ArrayList(u8) = .empty,/// Whether to go into subtrees (`-r`); otherwise a subtree that differs/// is yielded as an entry of its own, as `git diff-tree` without `-r`/// does.recursive: bool = true,/// Whether to yield each subtree gone into before what is below it/// (`-t`).show_trees: bool = false,/// A subtree yielded under `show_trees`, to go into on the next call.pending: ?struct { old: ?Id, new: ?Id, all: bool } = null,
/// How an entry differs.pub const Status = enum { added, deleted, modified };
/// One side of a changed entry.pub const Side = struct { mode: tree.Mode, /// The mode as the tree spells it. raw_mode: u32, id: Id,};
/// An entry that differs.pub const Change = struct { status: Status, /// From the top of the tree; valid until the next call to `next`. path: []const u8, /// Null when added. old: ?Side, /// Null when deleted. new: ?Side,};
/// What comparing can fail with: reading a tree, a tree that is not one/// (`NotATree`, the diagnostic naming it), or a malformed tree.pub const Error = ObjectDatabase.ReadError || tree.Iterator.Error || error{NotATree};
const Walker = struct { object: ?ObjectDatabase.Object = null, it: tree.Iterator, peeked: ?tree.Entry = null, done: bool = false,
fn peek(w: *Walker, diag: ?*Diagnostics, id: ?Id) Error!?tree.Entry { if (w.peeked) |e| return e; if (w.done) return null; w.peeked = w.it.next() catch |err| { if (diag) |d| { d.reset(); d.object_id = id; } return err; }; if (w.peeked == null) w.done = true; return w.peeked; }};
const Frame = struct { old: Walker, new: Walker, old_id: ?Id, new_id: ?Id, /// The length of `path` for this frame's entries, its own name and /// `/` included. path_len: usize, /// Whether every entry below matches the pathspec. all: bool,
fn deinit(f: *Frame, gpa: Allocator) void { if (f.old.object) |*o| o.deinit(gpa); if (f.new.object) |*o| o.deinit(gpa); }};
/// A comparison reading trees from `db`, limited to what `pathspec`/// matches; both must outlive it.pub fn init(gpa: Allocator, io: Io, db: ObjectDatabase, format: Format, pathspec: *const Pathspec) TreeDiff { return .{ .gpa = gpa, .io = io, .db = db, .format = format, .pathspec = pathspec };}
/// Frees everything.pub fn deinit(d: *TreeDiff) void { d.clear(); d.frames.deinit(d.gpa); d.path.deinit(d.gpa); d.* = undefined;}
fn clear(d: *TreeDiff) void { d.pending = null; for (d.frames.items) |*f| f.deinit(d.gpa); d.frames.clearRetainingCapacity(); d.path.clearRetainingCapacity();}
fn readTree(d: *TreeDiff, id: ?Id, diag: ?*Diagnostics) Error!Walker { const the_id = id orelse return .{ .it = tree.iterate(d.format, "") }; var o = d.db.read(d.io, d.gpa, the_id, diag) catch |err| switch (err) { error.ObjectNotFound => { if (the_id.eql(object.hash(d.format, .tree, ""))) return .{ .it = tree.iterate(d.format, "") }; return err; }, else => |e| return e, }; if (o.kind != .tree) { o.deinit(d.gpa); if (diag) |dg| { dg.reset(); dg.object_id = the_id; } return error.NotATree; } return .{ .object = o, .it = tree.iterate(d.format, o.data) };}
fn push(d: *TreeDiff, old: ?Id, new: ?Id, all: bool, diag: ?*Diagnostics) Error!void { var o = try d.readTree(old, diag); errdefer if (o.object) |*x| x.deinit(d.gpa); var n = try d.readTree(new, diag); errdefer if (n.object) |*x| x.deinit(d.gpa); try d.frames.append(d.gpa, .{ .old = o, .new = n, .old_id = old, .new_id = new, .path_len = d.path.items.len, .all = all });}
/// Starts comparing `old` with `new`, either of which may be null for the/// empty tree.pub fn start(d: *TreeDiff, old: ?Id, new: ?Id, diag: ?*Diagnostics) Error!void { d.clear(); if (old != null and new != null and old.?.eql(new.?)) return; const r = d.pathspec.reach(""); if (r == .none) return; try d.push(old, new, r == .all, diag);}
/// How two entry names sort, a directory's as if it ended in `/`.fn order(a: tree.Entry, b: tree.Entry) std.math.Order { const n = @min(a.name.len, b.name.len); switch (std.mem.order(u8, a.name[0..n], b.name[0..n])) { .eq => {}, else => |o| return o, } const ca: u8 = if (a.name.len > n) a.name[n] else if (a.mode() == .directory) '/' else 0; const cb: u8 = if (b.name.len > n) b.name[n] else if (b.mode() == .directory) '/' else 0; return std.math.order(ca, cb);}
fn setPath(d: *TreeDiff, frame_len: usize, name: []const u8) Allocator.Error!void { d.path.shrinkRetainingCapacity(frame_len); try d.path.appendSlice(d.gpa, name);}
fn side(e: tree.Entry) Side { return .{ .mode = e.mode(), .raw_mode = e.raw_mode, .id = e.id };}
/// The next entry that differs, or null after the last.pub fn next(d: *TreeDiff, diag: ?*Diagnostics) Error!?Change { if (d.pending) |p| { d.pending = null; try d.path.append(d.gpa, '/'); try d.push(p.old, p.new, p.all, diag); } while (d.frames.items.len != 0) { const fi = d.frames.items.len - 1; var f = &d.frames.items[fi]; const a = try f.old.peek(diag, f.old_id); const b = try f.new.peek(diag, f.new_id); if (a == null and b == null) { f.deinit(d.gpa); d.frames.items.len -= 1; continue; } const frame_len = f.path_len; const all = f.all; const which: std.math.Order = if (a == null) .gt else if (b == null) .lt else order(a.?, b.?); var old_entry: ?tree.Entry = null; var new_entry: ?tree.Entry = null; switch (which) { .lt => { old_entry = a; f.old.peeked = null; }, .gt => { new_entry = b; f.new.peeked = null; }, .eq => { old_entry = a; new_entry = b; f.old.peeked = null; f.new.peeked = null; }, } const name = (old_entry orelse new_entry.?).name; const old_dir = if (old_entry) |e| e.mode() == .directory else false; const new_dir = if (new_entry) |e| e.mode() == .directory else false; if (old_dir or new_dir) { // Equal names sort together only when both are directories. if (old_entry != null and new_entry != null and old_entry.?.id.eql(new_entry.?.id)) continue; try d.setPath(frame_len, name); var below_all = all; var descend = true; if (!d.recursive) { if (!all and !d.pathspec.showsDirectory(d.path.items)) continue; } else if (!all) switch (d.pathspec.reach(d.path.items)) { .none => { // A tree is listed by the positive patterns alone, // though an exclusion keeps the walk out of it. if (!d.show_trees or !d.pathspec.reachesIgnoringExclusions(d.path.items)) continue; descend = false; }, .some => {}, .all => below_all = true, }; const old_id = if (old_entry) |e| e.id else null; const new_id = if (new_entry) |e| e.id else null; if (!d.recursive or d.show_trees) { // A directory on one side only, against a file on the // other, sorts apart from it; here only directories meet. if (d.recursive and descend) d.pending = .{ .old = old_id, .new = new_id, .all = below_all }; return .{ .status = if (old_entry == null) .added else if (new_entry == null) .deleted else .modified, .path = d.path.items, .old = if (old_entry) |e| side(e) else null, .new = if (new_entry) |e| side(e) else null, }; } try d.path.append(d.gpa, '/'); try d.push(old_id, new_id, below_all, diag); continue; } if (old_entry != null and new_entry != null) { if (old_entry.?.id.eql(new_entry.?.id) and old_entry.?.mode() == new_entry.?.mode()) continue; } try d.setPath(frame_len, name); const gitlink = (if (new_entry) |e| e.mode() == .gitlink else false) or (if (old_entry) |e| e.mode() == .gitlink else false); if (!all and !d.pathspec.matches(d.path.items, gitlink)) continue; return .{ .status = if (old_entry == null) .added else if (new_entry == null) .deleted else .modified, .path = d.path.items, .old = if (old_entry) |e| side(e) else null, .new = if (new_entry) |e| side(e) else null, }; } return null;}
/// Whether anything the pathspec matches differs between `old` and/// `new`: whether a commit with tree `new` is not TREESAME to a parent/// with tree `old`.pub fn differs(d: *TreeDiff, old: ?Id, new: ?Id, diag: ?*Diagnostics) Error!bool { try d.start(old, new, diag); const found = try d.next(diag) != null; d.clear(); return found;}
// -- tests -------------------------------------------------------------------
const testing = std.testing;const fixture = @import("testing/fixture.zig");const fuzz_input = @import("testing/fuzz.zig");const DiskDatabase = @import("DiskDatabase.zig");
test "changes are what git diff-tree -r lists" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); const write = struct { fn f(r: *fixture.Repo, path: []const u8, data: []const u8) !void { if (std.fs.path.dirname(path)) |dir| try r.tmp.dir.createDirPath(r.io, dir); try r.tmp.dir.writeFile(r.io, .{ .sub_path = path, .data = data }); } }.f; try write(&repo, "a", "1"); try write(&repo, "a.b", "1"); try write(&repo, "d/e/f", "1"); try write(&repo, "d/g", "1"); try write(&repo, "x", "1"); try write(&repo, "same/s", "1"); try repo.git(&.{ "add", "-A" }); try repo.commit("one"); try repo.git(&.{ "rm", "-q", "a", "d/g" }); try write(&repo, "a/inside", "2"); try write(&repo, "d/e/f", "2"); try write(&repo, "d/h", "2"); try write(&repo, "x", "1"); try repo.git(&.{ "add", "-A" }); try repo.git(&.{ "update-index", "--chmod=+x", "x" }); try repo.commit("two");
var db = try DiskDatabase.open(gpa, repo.io, .{ .objects_path = ".git/objects", .base = repo.tmp.dir, .format = repo.object_format }, null); defer db.close(repo.io); const tree_of = struct { fn f(r: *fixture.Repo, rev: []const u8) !Id { const out = try r.output(&.{ "rev-parse", rev }); defer r.gpa.free(out); return Id.parseHex(r.object_format, std.mem.trimEnd(u8, out, "\n")); } }.f; const old = try tree_of(&repo, "HEAD~1^{tree}"); const new = try tree_of(&repo, "HEAD^{tree}"); for ([_][]const []const u8{ &.{}, &.{"d"}, &.{"*f"}, &.{":!d/e"}, &.{"a"}, &.{"nothing"} }) |specs| { var ps = try Pathspec.parse(gpa, specs, .{}, null); defer ps.deinit(gpa); var args: std.ArrayList([]const u8) = .empty; defer args.deinit(gpa); try args.appendSlice(gpa, &.{ "diff-tree", "-r", "--no-renames", "HEAD~1", "HEAD", "--" }); try args.appendSlice(gpa, specs); const want = try repo.output(args.items); defer gpa.free(want); var got: std.Io.Writer.Allocating = .init(gpa); defer got.deinit(); var diff = init(gpa, repo.io, db.database(), repo.object_format, &ps); defer diff.deinit(); try diff.start(old, new, null); while (try diff.next(null)) |c| { const zero = object.Id.zero(repo.object_format); const letter: u8 = switch (c.status) { .added => 'A', .deleted => 'D', .modified => if (c.old.?.mode.kind() == c.new.?.mode.kind() and (c.old.?.mode == .symlink) == (c.new.?.mode == .symlink)) 'M' else 'T', }; try got.writer.print(":{o:0>6} {o:0>6} {f} {f} {c}\t{s}\n", .{ if (c.old) |s| @backingInt(s.mode) else 0, if (c.new) |s| @backingInt(s.mode) else 0, if (c.old) |s| s.id else zero, if (c.new) |s| s.id else zero, letter, c.path, }); } try testing.expectEqualStrings(want, got.written()); try testing.expectEqual(want.len != 0, try diff.differs(old, new, null)); }}
/// An object database of objects held in memory, for the fuzz test.const Memory = struct { format: Format, objects: []const struct { id: Id, data: []const u8 },
fn database(m: *Memory) ObjectDatabase { return .{ .ptr = m, .vtable = &.{ .contains = contains, .readHeader = readHeader, .read = read, .stream = stream } }; } fn find(m: *Memory, id: Id) ?[]const u8 { for (m.objects) |o| if (o.id.eql(id)) return o.data; return null; } fn contains(ptr: *anyopaque, _: Io, id: Id, _: ?*Diagnostics) ObjectDatabase.ContainsError!bool { const m: *Memory = @ptrCast(@alignCast(ptr)); return m.find(id) != null; } fn readHeader(ptr: *anyopaque, _: Io, id: Id, _: ?*Diagnostics) ObjectDatabase.ReadError!object.Header { const m: *Memory = @ptrCast(@alignCast(ptr)); const data = m.find(id) orelse return error.ObjectNotFound; return .{ .kind = .tree, .size = data.len, .len = 0 }; } fn read(ptr: *anyopaque, _: Io, gpa: Allocator, id: Id, _: ?*Diagnostics) ObjectDatabase.ReadError!ObjectDatabase.Object { const m: *Memory = @ptrCast(@alignCast(ptr)); const data = m.find(id) orelse return error.ObjectNotFound; const copy = try gpa.dupe(u8, data); return .{ .kind = .tree, .data = copy, .allocation = copy }; } fn stream(_: *anyopaque, _: Io, _: Allocator, _: Id, _: *Io.Writer, _: ?*Diagnostics) ObjectDatabase.StreamError!object.Header { return error.ObjectNotFound; }};
fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void { var buffer: [512]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); // Two trees' contents and a pathspec, separated by "\n--\n"; every // subtree an entry names is one of the two trees. var parts = std.mem.splitSequence(u8, input, "\n--\n"); const old_data = parts.next() orelse ""; const new_data = parts.next() orelse ""; const spec = parts.next() orelse ""; const format: Format = .sha1; const old_id = object.hash(format, .tree, old_data); const new_id = object.hash(format, .tree, new_data); var memory: Memory = .{ .format = format, .objects = &.{ .{ .id = old_id, .data = old_data }, .{ .id = new_id, .data = new_data } } }; const gpa = testing.allocator; var ps = Pathspec.parse(gpa, if (spec.len == 0) &.{} else &.{spec}, .{}, null) catch return; defer ps.deinit(gpa); var diff = init(gpa, testing.io, memory.database(), format, &ps); defer diff.deinit(); diff.start(old_id, new_id, null) catch return; // A tree naming itself would go on for ever; stop somewhere. var n: usize = 0; while (n < 1000) : (n += 1) { const c = diff.next(null) catch return orelse break; try testing.expect(c.path.len != 0); try testing.expect(c.old != null or c.new != null); if (diff.frames.items.len > 64) break; } // The same trees on both sides differ nowhere. try testing.expect(!try diff.differs(old_id, old_id, null));}
test "fuzz: tree comparison" { try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/tree-diff"), } });}