// 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"),
    } });
}