// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-License-Identifier: MIT

//! The index compared: with a tree (`git diff-index --cached`), with the
//! working tree (`git diff-files`), and a tree with the working tree
//! through the index (`git diff-index`). Each yields the changed paths as
//! `diff.output.Pair`s, in the index's order, which is the order of their
//! paths' bytes.
//!
//! Nothing here writes the index. git's porcelain refreshes it before it
//! compares, writing the stat data of files whose contents turn out to be
//! unchanged; the plumbing does not, and lists such a file as modified,
//! with the zero object ID for the working tree side. This module does
//! what the plumbing does, from the stat data the index holds, as
//! gitformat-index(5) describes it and as experiments showed git compares
//! it:
//!
//! - a file is unchanged when its mode, its modification time and change
//!   time in whole seconds (the change time only with `core.trustctime`),
//!   its inode, owner, group and size (cut to 32 bits) are those the
//!   index records; `core.checkStat=minimal` compares only the times'
//!   seconds, the size and the mode. Nanoseconds were seen not to count;
//! - a file unchanged by its stat data is "racily clean" when it was
//!   modified in or after the second the index was written, and then its
//!   contents are hashed and compared, as git does;
//! - an entry marked assume-unchanged or skip-worktree is unchanged;
//! - an intent-to-add entry is an addition, its object ID unknown;
//! - a gitlink whose directory is empty is unchanged; one that holds a
//!   checked-out repository is refused (`SubmoduleUnsupported`).
//!
//! The working tree is reached through `WorkTree`, a seam a caller can
//! fill; `NativeWorkTree` answers from the filesystem with `statx` on
//! Linux.

const std = @import("std");
const builtin = @import("builtin");
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 Index = @import("Index.zig");
const Entry = Index.Entry;
const ObjectDatabase = @import("ObjectDatabase.zig");
const Pathspec = @import("Pathspec.zig");
const Diagnostics = @import("Diagnostics.zig");
const output = @import("diff/output.zig");
const Pair = output.Pair;
const Side = output.Side;

/// A file in the working tree, as `lstat` sees it.
pub const FileInfo = struct {
    kind: enum { file, symlink, directory, other },
    /// The permission and type bits.
    mode: u32,
    ctime_seconds: u32,
    mtime_seconds: u32,
    ino: u32,
    uid: u32,
    gid: u32,
    /// Cut to 32 bits, as the index records it.
    size: u32,
};

/// What reading the working tree can fail with.
pub const WorkTreeError = Allocator.Error || error{
    /// A file could not be stat'ed or read for a reason other than its
    /// absence.
    WorkTreeUnreadable,
    /// The filesystem cannot say what the index's stat data needs.
    WorkTreeUnsupported,
};

/// The working tree, as the comparison asks of it.
pub const WorkTree = struct {
    context: *anyopaque,
    /// `path`'s stat data, or null when there is nothing there (or a
    /// file where a directory leads to it).
    lstat: *const fn (context: *anyopaque, path: []const u8) WorkTreeError!?FileInfo,
    /// A file's contents, or a symbolic link's target.
    read: *const fn (context: *anyopaque, gpa: Allocator, path: []const u8, symlink: bool) WorkTreeError![]u8,
    /// Whether directory `path` holds anything.
    isEmptyDirectory: *const fn (context: *anyopaque, path: []const u8) WorkTreeError!bool,
};

/// The configuration the comparison reads.
pub const Options = struct {
    /// `core.fileMode`: whether the executable bit is compared.
    file_mode: bool = true,
    /// `core.trustctime`.
    trust_ctime: bool = true,
    /// `core.checkStat=minimal`.
    minimal_stat: bool = false,
    /// `core.symlinks`: false makes a symbolic link in the index a plain
    /// file in the working tree.
    symlinks: bool = true,
    /// The index file's modification time in seconds, for racily clean
    /// entries; null takes no entry for racy.
    index_mtime: ?u32 = null,
    /// `diff-index -m`: a file missing from the working tree is taken to
    /// be as the index has it.
    missing_as_index: bool = false,
    /// Compare as `git diff` does after refreshing the index: a file whose
    /// stat data changed but whose contents did not is unchanged.
    refresh: bool = false,
    /// Leave intent-to-add entries out of comparisons with the index
    /// itself, as `git diff --cached` does.
    ita_invisible: bool = false,
};

/// What comparing can fail with.
pub const Error = WorkTreeError || ObjectDatabase.ReadError || tree.Iterator.Error || error{
    NotATree,
    /// A gitlink's directory holds a checked-out repository, whose
    /// `HEAD` zig-git does not read.
    SubmoduleUnsupported,
};

/// Which stage of an unmerged path `diff-files` compares with the working
/// tree: `-1`, `-2` or `-3`, or none for `-0`.
pub const Stage = enum { none, base, ours, theirs };

/// Changed paths and the paths they hold.
pub const Pairs = struct {
    list: std.ArrayList(Pair) = .empty,
    arena: std.heap.ArenaAllocator,

    pub fn init(gpa: Allocator) Pairs {
        return .{ .arena = .init(gpa) };
    }

    pub fn deinit(p: *Pairs, gpa: Allocator) void {
        p.list.deinit(gpa);
        p.arena.deinit();
    }

    fn add(p: *Pairs, gpa: Allocator, status: output.Status, path: []const u8, old: Side, new: Side) Allocator.Error!void {
        try p.list.append(gpa, .{ .status = status, .path = try p.arena.allocator().dupe(u8, path), .old = old, .new = new });
    }
};

fn none(format: Format) Side {
    return .{ .id = Id.zero(format) };
}

fn entrySide(e: *const Entry) Side {
    return .{ .mode = e.mode, .id = e.id };
}

/// The mode git gives a working tree file for comparison with `e`.
pub fn worktreeMode(e: *const Entry, info: FileInfo, options: Options) u32 {
    switch (info.kind) {
        .symlink => return if (options.symlinks) 0o120000 else e.mode,
        .directory => return 0o160000,
        .file, .other => {
            if (!options.symlinks and e.mode == 0o120000) return 0o120000;
            if (!options.file_mode and (e.mode & 0o170000) == 0o100000) return e.mode;
            return if (info.mode & 0o100 != 0) 0o100755 else 0o100644;
        },
    }
}

/// Whether the working tree file `info` is the one entry `e` records, by
/// its stat data alone; racily clean entries still need their contents
/// compared (`isRacy`).
pub fn statMatches(e: *const Entry, info: FileInfo, options: Options) bool {
    if (worktreeMode(e, info, options) != e.mode) return false;
    if (info.mtime_seconds != e.mtime.seconds) return false;
    if (options.trust_ctime and info.ctime_seconds != e.ctime.seconds) return false;
    if (info.size != e.size) return false;
    if (!options.minimal_stat) {
        if (info.ino != e.ino or info.uid != e.uid or info.gid != e.gid) return false;
    }
    return true;
}

/// Whether `e` may have changed in the second the index was written, so
/// that its stat data cannot vouch for it.
pub fn isRacy(e: *const Entry, options: Options) bool {
    const written = options.index_mtime orelse return false;
    return e.mtime.seconds >= written;
}

/// The comparison of an index with the working tree, and of a tree with
/// either.
pub const Comparison = struct {
    gpa: Allocator,
    io: Io,
    db: ObjectDatabase,
    format: Format,
    index: *const Index,
    pathspec: *const Pathspec,
    worktree: ?WorkTree = null,
    options: Options = .{},

    /// Whether the working tree file at `e.path` is unchanged from `e`.
    fn unchanged(c: *Comparison, e: *const Entry, info: FileInfo) Error!bool {
        if (e.assumeValid() or e.skipWorktree()) return true;
        if (!statMatches(e, info, c.options)) {
            // A refresh looks at the contents of a file whose stat data
            // changed, if its mode did not.
            if (!c.options.refresh or worktreeMode(e, info, c.options) != e.mode) return false;
        } else if (!isRacy(e, c.options)) return true;
        // Racily clean: the contents decide.
        const wt = c.worktree.?;
        const data = try wt.read(wt.context, c.gpa, e.path, info.kind == .symlink and c.options.symlinks);
        defer c.gpa.free(data);
        return object.hash(c.format, .blob, data).eql(e.id);
    }

    /// The working tree side for entry `e`: null when the file is gone.
    fn worktreeSide(c: *Comparison, e: *const Entry) Error!?Side {
        const wt = c.worktree.?;
        if (e.assumeValid() or e.skipWorktree()) return entrySide(e);
        const info = try wt.lstat(wt.context, e.path) orelse {
            if (c.options.missing_as_index) return entrySide(e);
            return null;
        };
        if (e.mode == 0o160000) {
            if (info.kind != .directory) return .{ .mode = worktreeMode(e, info, c.options), .id = Id.zero(c.format), .id_known = false, .worktree = true };
            if (try wt.isEmptyDirectory(wt.context, e.path)) return entrySide(e);
            return error.SubmoduleUnsupported;
        }
        if (info.kind == .directory) return null;
        if (e.intentToAdd()) return .{ .mode = worktreeMode(e, info, c.options), .id = Id.zero(c.format), .id_known = false, .worktree = true };
        if (try c.unchanged(e, info)) return entrySide(e);
        return .{ .mode = worktreeMode(e, info, c.options), .id = Id.zero(c.format), .id_known = false, .worktree = true };
    }

    /// The index against the working tree, as `git diff-files` lists it;
    /// `stage` chooses what an unmerged path is compared with.
    pub fn filesAgainstWorktree(c: *Comparison, stage: ?Stage, pairs: *Pairs) Error!void {
        const entries = c.index.entries;
        var i: usize = 0;
        while (i < entries.len) {
            const e = &entries[i];
            if (e.stage() != 0) {
                var end = i;
                while (end < entries.len and std.mem.eql(u8, entries[end].path, e.path)) end += 1;
                defer i = end;
                if (!c.pathspec.matches(e.path, false)) continue;
                const wt = c.worktree.?;
                const info = try wt.lstat(wt.context, e.path);
                var new_side = none(c.format);
                if (info) |inf| new_side.mode = worktreeMode(e, inf, c.options);
                try pairs.add(c.gpa, .unmerged, e.path, none(c.format), new_side);
                const want: u2 = switch (stage orelse .ours) {
                    .none => continue,
                    .base => 1,
                    .ours => 2,
                    .theirs => 3,
                };
                for (entries[i..end]) |*s| {
                    if (s.stage() != want) continue;
                    const side = try c.worktreeSide(s) orelse {
                        try pairs.add(c.gpa, .deleted, s.path, entrySide(s), none(c.format));
                        break;
                    };
                    if (side.id_known and side.id.eql(s.id) and side.mode == s.mode) break;
                    try pairs.add(c.gpa, output.statusOf(entrySide(s), side), s.path, entrySide(s), side);
                    break;
                }
                continue;
            }
            i += 1;
            if (e.isSparseDirectory()) continue;
            if (!c.pathspec.matches(e.path, e.mode == 0o160000)) continue;
            if (e.intentToAdd()) {
                const side = try c.worktreeSide(e) orelse continue;
                try pairs.add(c.gpa, .added, e.path, none(c.format), side);
                continue;
            }
            const side = try c.worktreeSide(e) orelse {
                try pairs.add(c.gpa, .deleted, e.path, entrySide(e), none(c.format));
                continue;
            };
            if (side.id_known and side.id.eql(e.id) and side.mode == e.mode) continue;
            try pairs.add(c.gpa, output.statusOf(entrySide(e), side), e.path, entrySide(e), side);
        }
    }

    /// A tree's files, flattened, in the order of their paths.
    fn flatten(c: *Comparison, root: ?Id, arena: Allocator) Error![]const TreeFile {
        var files: std.ArrayList(TreeFile) = .empty;
        if (root) |r| try c.walk(r, "", arena, &files);
        return files.items;
    }

    fn walk(c: *Comparison, id: Id, prefix: []const u8, arena: Allocator, files: *std.ArrayList(TreeFile)) Error!void {
        var o = c.db.read(c.io, c.gpa, id, null) catch |err| switch (err) {
            error.ObjectNotFound => {
                if (id.eql(object.hash(c.format, .tree, ""))) return;
                return err;
            },
            else => |e| return e,
        };
        defer o.deinit(c.gpa);
        if (o.kind != .tree) return error.NotATree;
        var it = tree.iterate(c.format, o.data);
        while (try it.next()) |e| {
            const path = try std.mem.concat(arena, u8, &.{ prefix, e.name });
            if (e.mode() == .directory) {
                if (c.pathspec.reach(path) == .none) continue;
                const sub = try std.mem.concat(arena, u8, &.{ path, "/" });
                try c.walk(e.id, sub, arena, files);
                continue;
            }
            if (!c.pathspec.matches(path, e.mode() == .gitlink)) continue;
            try files.append(arena, .{ .path = path, .side = .{ .mode = @backingInt(e.mode()), .id = e.id } });
        }
    }

    const TreeFile = struct { path: []const u8, side: Side };

    /// A tree against the index (`worktree` false, `--cached`) or against
    /// the working tree through it, as `git diff-index` lists them.
    pub fn treeAgainst(c: *Comparison, root: ?Id, worktree: bool, pairs: *Pairs) Error!void {
        var arena_state: std.heap.ArenaAllocator = .init(c.gpa);
        defer arena_state.deinit();
        const files = try c.flatten(root, arena_state.allocator());
        // A tree's flattened paths sort as the index's do.
        std.mem.sort(TreeFile, @constCast(files), {}, struct {
            fn lt(_: void, a: TreeFile, b: TreeFile) bool {
                return std.mem.order(u8, a.path, b.path) == .lt;
            }
        }.lt);
        const entries = c.index.entries;
        var ti: usize = 0;
        var ii: usize = 0;
        while (ti < files.len or ii < entries.len) {
            // Skip index entries the pathspec leaves out.
            if (ii < entries.len) {
                const e = &entries[ii];
                if (e.isSparseDirectory() or !c.pathspec.matches(e.path, e.mode == 0o160000) or
                    (!worktree and c.options.ita_invisible and e.intentToAdd()))
                {
                    ii += 1;
                    continue;
                }
            }
            const order: std.math.Order = if (ti >= files.len) .gt else if (ii >= entries.len) .lt else std.mem.order(u8, files[ti].path, entries[ii].path);
            switch (order) {
                .lt => {
                    try pairs.add(c.gpa, .deleted, files[ti].path, files[ti].side, none(c.format));
                    ti += 1;
                },
                .gt, .eq => {
                    const e = &entries[ii];
                    const t: ?Side = if (order == .eq) files[ti].side else null;
                    if (order == .eq) ti += 1;
                    if (e.stage() != 0) {
                        var end = ii;
                        while (end < entries.len and std.mem.eql(u8, entries[end].path, e.path)) end += 1;
                        ii = end;
                        if (!worktree) {
                            try pairs.add(c.gpa, .unmerged, e.path, t orelse none(c.format), none(c.format));
                            continue;
                        }
                        // Against the working tree, an unmerged path is
                        // the file there, whatever its stages.
                        const wt = c.worktree.?;
                        const info = try wt.lstat(wt.context, e.path);
                        const new: ?Side = if (info) |inf| Side{ .mode = worktreeMode(e, inf, c.options), .id = Id.zero(c.format), .id_known = false, .worktree = true } else null;
                        try c.addPair(pairs, e.path, t, new);
                        continue;
                    }
                    ii += 1;
                    var new: ?Side = entrySide(e);
                    if (worktree) {
                        new = try c.worktreeSide(e);
                        if (e.intentToAdd()) if (new) |*n| {
                            n.id = Id.zero(c.format);
                            n.id_known = false;
                            n.worktree = true;
                        };
                    }
                    try c.addPair(pairs, e.path, t, new);
                },
            }
        }
    }

    fn addPair(c: *Comparison, pairs: *Pairs, path: []const u8, old: ?Side, new: ?Side) Error!void {
        const o = old orelse none(c.format);
        const n = new orelse none(c.format);
        if (!o.present() and !n.present()) return;
        if (o.present() and n.present() and n.id_known and o.id.eql(n.id) and o.mode == n.mode) return;
        try pairs.add(c.gpa, output.statusOf(o, n), path, o, n);
    }
};

// -- the native working tree -----------------------------------------------------

/// The working tree on disk: `statx` for stat data on Linux (elsewhere
/// `WorkTreeUnsupported`), and files read through `Io`.
pub const NativeWorkTree = struct {
    io: Io,
    /// The top of the working tree, absolute.
    top: []const u8,
    dir: Io.Dir,

    /// The `WorkTree` answering from it.
    pub fn workTree(n: *NativeWorkTree) WorkTree {
        return .{ .context = n, .lstat = lstat, .read = read, .isEmptyDirectory = isEmptyDirectory };
    }

    fn lstat(context: *anyopaque, path: []const u8) WorkTreeError!?FileInfo {
        const n: *NativeWorkTree = @ptrCast(@alignCast(context));
        if (builtin.os.tag != .linux) return error.WorkTreeUnsupported;
        const linux = std.os.linux;
        var buffer: [std.fs.max_path_bytes + 1]u8 = undefined;
        const full = std.fmt.bufPrint(&buffer, "{s}/{s}", .{ n.top, path }) catch return error.WorkTreeUnreadable;
        buffer[full.len] = 0;
        var st: linux.Statx = undefined;
        const rc = linux.statx(linux.AT.FDCWD, buffer[0..full.len :0], linux.AT.SYMLINK_NOFOLLOW, .{ .TYPE = true, .MODE = true, .UID = true, .GID = true, .INO = true, .SIZE = true, .MTIME = true, .CTIME = true }, &st);
        switch (linux.errno(rc)) {
            .SUCCESS => {},
            .NOENT, .NOTDIR => return null,
            else => return error.WorkTreeUnreadable,
        }
        const fmt = st.mode & 0o170000;
        return .{
            .kind = switch (fmt) {
                0o100000 => .file,
                0o120000 => .symlink,
                0o040000 => .directory,
                else => .other,
            },
            .mode = st.mode,
            .ctime_seconds = @truncate(@as(u64, @bitCast(st.ctime.sec))),
            .mtime_seconds = @truncate(@as(u64, @bitCast(st.mtime.sec))),
            .ino = @truncate(st.ino),
            .uid = st.uid,
            .gid = st.gid,
            .size = @truncate(st.size),
        };
    }

    fn read(context: *anyopaque, gpa: Allocator, path: []const u8, symlink: bool) WorkTreeError![]u8 {
        const n: *NativeWorkTree = @ptrCast(@alignCast(context));
        if (symlink) {
            var buffer: [std.fs.max_path_bytes]u8 = undefined;
            const len = n.dir.readLink(n.io, path, &buffer) catch return error.WorkTreeUnreadable;
            return gpa.dupe(u8, buffer[0..len]);
        }
        return n.dir.readFileAlloc(n.io, path, gpa, .unlimited) catch |err| switch (err) {
            error.OutOfMemory => |e| return e,
            else => return error.WorkTreeUnreadable,
        };
    }

    fn isEmptyDirectory(context: *anyopaque, path: []const u8) WorkTreeError!bool {
        const n: *NativeWorkTree = @ptrCast(@alignCast(context));
        var d = n.dir.openDir(n.io, path, .{ .iterate = true }) catch return error.WorkTreeUnreadable;
        defer d.close(n.io);
        var it = d.iterate();
        return (it.next(n.io) catch return error.WorkTreeUnreadable) == null;
    }
};

/// Contents for `diff.output`: the object database for known object IDs,
/// the working tree for the rest.
pub const Contents = struct {
    io: Io,
    db: ObjectDatabase,
    worktree: ?WorkTree,
    symlinks: bool = true,

    /// The `output.Source` reading from it.
    pub fn source(c: *Contents) output.Source {
        return .{ .context = c, .read = readSide };
    }

    fn readSide(context: *anyopaque, gpa: Allocator, pair: *const Pair, side: Side) output.Error!output.Contents {
        const c: *Contents = @ptrCast(@alignCast(context));
        if (!side.worktree) {
            var o = c.db.read(c.io, gpa, side.id, null) catch |err| switch (err) {
                error.OutOfMemory => |e| return e,
                else => return error.ContentsUnreadable,
            };
            if (o.kind != .blob) {
                o.deinit(gpa);
                return error.ContentsUnreadable;
            }
            return .{ .bytes = o.data, .allocation = o.allocation };
        }
        const wt = c.worktree orelse return error.ContentsUnreadable;
        const data = wt.read(wt.context, gpa, pair.path, side.mode == 0o120000 and c.symlinks) catch |err| switch (err) {
            error.OutOfMemory => |e| return e,
            else => return error.ContentsUnreadable,
        };
        return .{ .bytes = data, .allocation = data };
    }
};