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

//! Naming a commit by the nearest tag it descends from, as `git describe`
//! does. git-describe(1)'s "Search Strategy" describes it; the rest was
//! found by comparing with git over generated histories:
//!
//! - **Names** (`Names`): by default the annotated tags, with `tags` every
//!   tag, with `all` every ref, peeled to commits; a tag of something that
//!   is not a commit names nothing. With `match` and `exclude`, only those
//!   whose name below `refs/tags/` (and with `all`, `refs/heads/` or
//!   `refs/remotes/`, refs of other kinds never) a `match` glob matches
//!   and no `exclude` glob does.
//! - **One commit, several names**: an annotated tag beats a lightweight
//!   one, which beats any other ref; a later tagger date an earlier one;
//!   and otherwise the first in ref order wins.
//! - **The search**: a commit with a name is named by it. Otherwise the
//!   commits it descends from are visited newest commit date first (only
//!   first parents with `first_parent`), and the first `candidates` with a
//!   name are candidates; the one with the smallest depth wins, the first
//!   found among equals. The depth is counted as `search` says, which is
//!   not always what `git log <tag>..<commit>` would list.

const std = @import("std");
const Allocator = std.mem.Allocator;
const Io = std.Io;

const object = @import("object.zig");
const Id = object.Id;
const Diagnostics = @import("Diagnostics.zig");
const ObjectDatabase = @import("ObjectDatabase.zig");
const RefStore = @import("RefStore.zig");
const Commits = @import("Commits.zig");
const Index = Commits.Index;
const Tag = @import("tag.zig").Tag;
const wildmatch = @import("wildmatch.zig");

/// Which refs name commits.
pub const Options = struct {
    /// `--tags`: lightweight tags too.
    tags: bool = false,
    /// `--all`: every ref.
    all: bool = false,
    /// `--match`, each.
    match: []const []const u8 = &.{},
    /// `--exclude`, each.
    exclude: []const []const u8 = &.{},
};

/// A name for a commit.
pub const Name = struct {
    /// The ref's whole name.
    ref: []const u8,
    /// As `git describe` writes it: below `refs/tags/`, or with `all`
    /// below `refs/`.
    shown: []const u8,
    /// Whether the ref points at an annotated tag.
    annotated: bool,
    /// The outer tag's tagger date, for an annotated tag.
    date: i64 = 0,
    /// What the ref points at, or for an annotated tag what the tag
    /// does: the object `--long` abbreviates for a commit named by it.
    target: Id,
};

/// Every commit that has a name, and its best one.
pub const Names = struct {
    arena: std.heap.ArenaAllocator,
    map: std.AutoHashMapUnmanaged([object.max_byte_length]u8, Name) = .empty,
    /// The commits lightweight tags point at, when only annotated tags
    /// name commits, for git's hint to try `--tags`.
    light: std.AutoHashMapUnmanaged([object.max_byte_length]u8, void) = .empty,

    /// Frees everything.
    pub fn deinit(n: *Names) void {
        n.arena.deinit();
        n.* = undefined;
    }

    /// The best name of `commit`, if it has one.
    pub fn of(n: *const Names, commit: Id) ?Name {
        return n.map.get(commit.bytes);
    }

    /// Whether nothing has a name.
    pub fn isEmpty(n: *const Names) bool {
        return n.map.count() == 0;
    }
};

/// Whether `a` names a commit better than `b`: an annotated tag before a
/// lightweight one before any other ref, then the later tagger date.
fn better(a: Name, b: Name) bool {
    if (kindOf(a) != kindOf(b)) return kindOf(a) < kindOf(b);
    return a.date > b.date;
}

/// The name a ref is matched by, or null for a ref that cannot match.
fn matchName(name: []const u8, all: bool) ?[]const u8 {
    if (std.mem.startsWith(u8, name, "refs/tags/")) return name["refs/tags/".len..];
    if (!all) return null;
    for ([_][]const u8{ "refs/heads/", "refs/remotes/" }) |p| if (std.mem.startsWith(u8, name, p)) return name[p.len..];
    return null;
}

/// Finds the names in `refs`, reading tags from `db`.
pub fn loadNames(gpa: Allocator, io: Io, refs: RefStore, db: ObjectDatabase, options: Options, diag: ?*Diagnostics) RefStore.ReadError!Names {
    var n: Names = .{ .arena = .init(gpa) };
    errdefer n.deinit();
    const a = n.arena.allocator();
    var list = try refs.list(io, gpa, if (options.all) "refs/" else "refs/tags/", diag);
    defer list.deinit();
    for (list.entries) |e| {
        if (options.match.len != 0 or options.exclude.len != 0) {
            const m = matchName(e.name, options.all) orelse continue;
            if (options.match.len != 0) {
                const any = for (options.match) |p| {
                    if (wildmatch.match(p, m, .{})) break true;
                } else false;
                if (!any) continue;
            }
            const excluded = for (options.exclude) |p| {
                if (wildmatch.match(p, m, .{})) break true;
            } else false;
            if (excluded) continue;
        }
        const id = switch (e.value) {
            .direct => |d| d.id,
            .symbolic => blk: {
                var r = refs.resolve(io, gpa, e.name, null) catch continue;
                defer r.deinit(gpa);
                break :blk switch (r.outcome) {
                    .direct => |d| d.id,
                    else => continue,
                };
            },
            .broken => continue,
        };
        // Peel, keeping the outer tag's date.
        var current = id;
        var annotated = false;
        var date: i64 = 0;
        var target = id;
        var kind: object.Kind = .commit;
        for (0..RefStore.max_peel_depth) |_| {
            const header = db.readHeader(io, current, null) catch break;
            kind = header.kind;
            if (kind != .tag) break;
            var o = db.read(io, gpa, current, null) catch break;
            defer o.deinit(gpa);
            const t = Tag.parse(current.object_format, o.data, null) catch break;
            if (!annotated) {
                annotated = true;
                target = t.target;
                if (t.tagger()) |who| if (who.date()) |d| {
                    date = d.seconds;
                };
            }
            current = t.target;
        }
        if (kind != .commit) continue;
        const is_tag = std.mem.startsWith(u8, e.name, "refs/tags/");
        if (!options.all and !options.tags and !annotated) {
            if (is_tag) try n.light.put(a, current.bytes, {});
            continue;
        }
        const full = try a.dupe(u8, e.name);
        const name: Name = .{
            .ref = full,
            .shown = if (options.all) full["refs/".len..] else full["refs/tags/".len..],
            .annotated = annotated,
            .date = date,
            .target = target,
        };
        const gop = try n.map.getOrPut(a, current.bytes);
        if (!gop.found_existing or better(name, gop.value_ptr.*)) gop.value_ptr.* = name;
    }
    return n;
}

/// What describing a commit found.
pub const Found = struct {
    name: Name,
    /// The depth git counts: 0 for the name's own commit.
    depth: u64,
};

/// How the search goes.
pub const SearchOptions = struct {
    /// `--candidates`: how many named commits are weighed; 0 for only
    /// the commit's own name.
    candidates: usize = 10,
    /// `--first-parent`.
    first_parent: bool = false,
};

/// What a search came to.
pub const Outcome = union(enum) {
    found: Found,
    /// Nothing named the commit; `unannotated` says whether the search
    /// met a lightweight tag that `tags` would have taken, for git's hint.
    none: struct { unannotated: bool },
    /// The candidates were of more than one kind — annotated tags,
    /// lightweight tags, other refs — among which git's choice was not
    /// matched: it does not always take the candidate the rule above
    /// says, and not always one kind over another.
    mixed,
};

fn kindOf(n: Name) u2 {
    if (n.annotated) return 0;
    if (std.mem.startsWith(u8, n.ref, "refs/tags/")) return 1;
    return 2;
}

const max_candidates = 64;

/// Describes `commit`, reading commits through `store`.
///
/// The depth is the one git counts, which git-describe(1) calls the
/// number of commits `git log <tag>..<commit>` lists but which was found
/// to be counted as git walks: commits are visited newest commit date
/// first, each passing on to its parents which candidates reach it; every
/// commit visited adds one to the depth of each candidate found so far
/// that has not reached it, and a candidate starts with the number of
/// commits visited before it. The walk stops once every commit queued is
/// reached by every candidate, or when one more candidate is met than
/// `candidates`; then the best so far is finished by walking on until
/// everything queued is reached by it.
pub fn search(gpa: Allocator, names: *const Names, store: *Commits, commit: Index, options: SearchOptions, diag: ?*Diagnostics) Commits.Error!Outcome {
    if (names.of(store.id(commit))) |n| return .{ .found = .{ .name = n, .depth = 0 } };
    var unannotated = false;
    if (options.candidates == 0) return .{ .none = .{ .unannotated = false } };
    const limit = @min(options.candidates, max_candidates);

    const Candidate = struct { commit: Index, depth: u64, flag: u64 };
    var candidates: std.ArrayList(Candidate) = .empty;
    defer candidates.deinit(gpa);
    var flags: std.AutoHashMapUnmanaged(Index, u64) = .empty;
    defer flags.deinit(gpa);
    var queue: std.ArrayList(Queued) = .empty;
    defer queue.deinit(gpa);
    var sequence: u64 = 0;
    try store.load(commit, diag);
    try flags.put(gpa, commit, 0);
    try pushQueued(gpa, &queue, .{ .time = store.time(commit), .sequence = sequence, .commit = commit });
    var visited: u64 = 0;
    var gave_up = false;
    while (popQueued(&queue)) |c| {
        visited += 1;
        if (names.light.contains(store.id(c).bytes)) unannotated = true;
        if (c != commit) {
            const id = store.id(c);
            if (names.of(id) != null) {
                if (candidates.items.len < limit) {
                    const flag = @as(u64, 1) << @intCast(candidates.items.len);
                    try candidates.append(gpa, .{ .commit = c, .depth = visited - 1, .flag = flag });
                    flags.getPtr(c).?.* |= flag;
                } else {
                    gave_up = true;
                    sequence += 1;
                    try pushQueued(gpa, &queue, .{ .time = store.time(c), .sequence = sequence, .commit = c });
                    break;
                }
            }
        }
        const mine = flags.get(c).?;
        for (candidates.items) |*cand| {
            if (mine & cand.flag == 0) cand.depth += 1;
        }
        try passOn(gpa, store, c, mine, options.first_parent, &flags, &queue, &sequence, diag);
        if (candidates.items.len != 0) {
            var all: u64 = 0;
            for (candidates.items) |cand| all |= cand.flag;
            if (everyQueuedHas(&queue, &flags, all)) break;
        }
    }
    if (candidates.items.len == 0) return .{ .none = .{ .unannotated = unannotated } };
    const first_kind = kindOf(names.of(store.id(candidates.items[0].commit)).?);
    for (candidates.items[1..]) |cand| {
        if (kindOf(names.of(store.id(cand.commit)).?) != first_kind) return .mixed;
    }
    var best = &candidates.items[0];
    for (candidates.items[1..]) |*cand| {
        if (cand.depth < best.depth) best = cand;
    }
    if (gave_up) {
        while (!everyQueuedHas(&queue, &flags, best.flag)) {
            const c = popQueued(&queue) orelse break;
            const mine = flags.get(c).?;
            if (mine & best.flag == 0) best.depth += 1;
            try passOn(gpa, store, c, mine, options.first_parent, &flags, &queue, &sequence, diag);
        }
    }
    return .{ .found = .{ .name = names.of(store.id(best.commit)).?, .depth = best.depth } };
}

fn passOn(
    gpa: Allocator,
    store: *Commits,
    c: Index,
    mine: u64,
    first_parent: bool,
    flags: *std.AutoHashMapUnmanaged(Index, u64),
    queue: *std.ArrayList(Queued),
    sequence: *u64,
    diag: ?*Diagnostics,
) Commits.Error!void {
    const n = if (first_parent) @min(store.parents(c).len, 1) else store.parents(c).len;
    for (0..n) |i| {
        const p = store.parents(c)[i];
        const gop = try flags.getOrPut(gpa, p);
        if (!gop.found_existing) {
            gop.value_ptr.* = 0;
            try store.load(p, diag);
            sequence.* += 1;
            try pushQueued(gpa, queue, .{ .time = store.time(p), .sequence = sequence.*, .commit = p });
        }
        flags.getPtr(p).?.* |= mine;
    }
}

fn everyQueuedHas(queue: *const std.ArrayList(Queued), flags: *const std.AutoHashMapUnmanaged(Index, u64), want: u64) bool {
    for (queue.items) |q| {
        if (flags.get(q.commit).? & want != want) return false;
    }
    return true;
}

const Queued = struct { time: i64, sequence: u64, commit: Index };

fn newer(a: Queued, b: Queued) bool {
    if (a.time != b.time) return a.time > b.time;
    return a.sequence < b.sequence;
}

fn pushQueued(gpa: Allocator, queue: *std.ArrayList(Queued), q: Queued) Allocator.Error!void {
    try queue.append(gpa, q);
    var i = queue.items.len - 1;
    while (i > 0) {
        const parent = (i - 1) / 2;
        if (!newer(queue.items[i], queue.items[parent])) break;
        std.mem.swap(Queued, &queue.items[i], &queue.items[parent]);
        i = parent;
    }
}

fn popQueued(queue: *std.ArrayList(Queued)) ?Index {
    const items = queue.items;
    if (items.len == 0) return null;
    const top = items[0].commit;
    items[0] = items[items.len - 1];
    queue.items.len -= 1;
    var i: usize = 0;
    const n = queue.items.len;
    while (true) {
        const l = 2 * i + 1;
        if (l >= n) break;
        var best = l;
        if (l + 1 < n and newer(queue.items[l + 1], queue.items[l])) best = l + 1;
        if (!newer(queue.items[best], queue.items[i])) break;
        std.mem.swap(Queued, &queue.items[i], &queue.items[best]);
        i = best;
    }
    return top;
}