"""Tag-based commit description for ``muse describe``.

Walks backward from a commit through its ancestor graph and finds the nearest
tag.  Returns a human-readable ``<tag>~N`` label where N is the hop count from
the tag's commit to the described commit.  N=0 means the commit is exactly on
the tag.

The walk is a BFS that visits each ancestor at most once (cycle-safe).  It
stops as soon as the first matching tag is found, so it is O(commits between
tag and HEAD) — not O(all commits).

If no matching tag is found, ``DescribeResult.tag`` is ``None`` and ``name``
falls back to the short SHA.

Walk budget::

    _MAX_WALK = 50_000 commits.  When the budget is exhausted the walk stops
    and the nearest tag found so far (if any) is returned.  The budget check
    uses ``>=`` so exactly 50 000 commits are visited — not 50 001.

Tag-selection tie-breaking::

    When multiple tags point to the same commit the lexicographically greatest
    tag name wins.  This is consistent with Git's ``--tags`` behaviour for
    lightweight tags.

Pattern matching::

    ``match_pattern`` is a ``fnmatch``-style glob applied to tag names before
    they are eligible for selection.  Only tags whose name matches the pattern
    are considered.  When ``None`` (the default) all tags are eligible.
"""

from __future__ import annotations

import fnmatch
import logging
import pathlib
from collections import deque
from typing import TypedDict

from muse.core.store import get_all_tags, read_commit


type _StrMap = dict[str, str]
logger = logging.getLogger(__name__)

_MAX_WALK = 50_000


class DescribeResult(TypedDict):
    """Result of describing a commit by its nearest tag.

    Fields:
        commit_id:  Full SHA-256 hex of the described commit.
        tag:        Nearest tag name, or ``None`` if no tag was found.
        distance:   Hop count from the tag's commit to this commit.
        short_sha:  First ``abbrev`` characters of ``commit_id``.
        name:       Human-readable description string.
        exact:      ``True`` when ``distance == 0`` and ``tag`` is not ``None``.
    """

    commit_id: str
    tag: str | None
    distance: int
    short_sha: str
    name: str
    exact: bool


def describe_commit(
    root: pathlib.Path,
    repo_id: str,
    commit_id: str,
    *,
    long_format: bool = False,
    match_pattern: str | None = None,
    first_parent: bool = False,
    abbrev: int = 12,
    exact_match: bool = False,
) -> DescribeResult:
    """Return a human-readable description of *commit_id*.

    Walks backward from *commit_id* through the parent chain using BFS and
    finds the nearest tag that satisfies the given constraints.  The
    description is ``<tag>~N`` where N is the number of hops from the tag's
    commit to *commit_id*.

    When *long_format* is ``True`` the name always includes the distance and
    short SHA even when N=0, matching Git's ``--long`` behaviour::

        v1.0.0-0-gabc12345     # long: on the tag itself (distance=0)
        v1.0.0~3-gabc12345     # long: 3 hops past the tag

    When *exact_match* is ``True`` only distance-0 hits are accepted; if no
    exact tag match exists ``tag`` is ``None`` and the walk returns the short
    SHA fallback immediately.

    When *first_parent* is ``True`` only the first parent of each merge commit
    is followed, limiting the walk to the main-line ancestry.

    When *match_pattern* is given, only tag names matching the
    ``fnmatch``-style glob are considered.

    Args:
        root:          Repository root directory.
        repo_id:       Repository UUID (used to look up tags).
        commit_id:     Starting commit to describe (typically HEAD).
        long_format:   Always include distance and short SHA in the name.
        match_pattern: ``fnmatch`` glob to filter eligible tag names.
        first_parent:  Follow only the first-parent chain (skip second parents).
        abbrev:        Length of the short SHA suffix (default 12).
        exact_match:   Only accept distance-0 hits; return SHA fallback otherwise.

    Returns:
        A :class:`DescribeResult` with the nearest tag name, hop count, and
        formatted description string.
    """
    short_sha = commit_id[:abbrev]

    _no_tag = DescribeResult(
        commit_id=commit_id,
        tag=None,
        distance=0,
        short_sha=short_sha,
        name=short_sha,
        exact=False,
    )

    # Build commit_id → tag_name map.  Multiple tags on the same commit:
    # keep the lexicographically greatest name (stable tie-break).
    all_tags = get_all_tags(root, repo_id)
    tag_by_commit: _StrMap = {}
    for t in all_tags:
        if match_pattern is not None and not fnmatch.fnmatch(t.tag, match_pattern):
            continue
        existing = tag_by_commit.get(t.commit_id)
        if existing is None or t.tag > existing:
            tag_by_commit[t.commit_id] = t.tag

    if not tag_by_commit:
        return _no_tag

    # BFS backward through parent chain.
    visited: set[str] = set()
    queue: deque[tuple[str, int]] = deque([(commit_id, 0)])

    while queue:
        cid, distance = queue.popleft()
        if cid in visited:
            continue
        visited.add(cid)

        if len(visited) >= _MAX_WALK:
            logger.warning("⚠️ describe: reached %d-commit walk limit", _MAX_WALK)
            break

        if cid in tag_by_commit:
            if exact_match and distance != 0:
                # On exact_match mode, a non-zero distance means the commit
                # isn't on a tag — stop immediately with SHA fallback.
                return _no_tag
            tag_name = tag_by_commit[cid]
            if long_format:
                name = f"{tag_name}-{distance}-g{short_sha}"
            elif distance == 0:
                name = tag_name
            else:
                name = f"{tag_name}~{distance}"
            return DescribeResult(
                commit_id=commit_id,
                tag=tag_name,
                distance=distance,
                short_sha=short_sha,
                name=name,
                exact=(distance == 0),
            )

        commit = read_commit(root, cid)
        if commit is None:
            continue
        if commit.parent_commit_id:
            queue.append((commit.parent_commit_id, distance + 1))
        if not first_parent and commit.parent2_commit_id:
            queue.append((commit.parent2_commit_id, distance + 1))

    return _no_tag