"""Toctree adapter for sphinx.environment."""

from __future__ import annotations

import warnings
from typing import TYPE_CHECKING

from docutils import nodes
from docutils.nodes import Element

from sphinx import addnodes
from sphinx.deprecation import RemovedInSphinx11Warning
from sphinx.locale import __
from sphinx.util import logging, url_re
from sphinx.util.matching import Matcher
from sphinx.util.nodes import _only_node_keep_children, clean_astext

if TYPE_CHECKING:
    from collections.abc import Iterable, Set
    from typing import Any

    from docutils.nodes import Node

    from sphinx.builders import Builder
    from sphinx.environment import BuildEnvironment
    from sphinx.util.tags import Tags


logger = logging.getLogger(__name__)


def note_toctree(
    env: BuildEnvironment, docname: str, toctreenode: addnodes.toctree
) -> None:
    """Note a TOC tree directive in a document and gather information about
    file relations from it.
    """
    if toctreenode['glob']:
        env.glob_toctrees.add(docname)
    if toctreenode.get('numbered'):
        env.numbered_toctrees.add(docname)
    include_files = toctreenode['includefiles']
    for include_file in include_files:
        # note that if the included file is rebuilt, this one must be
        # too (since the TOC of the included file could have changed)
        env.files_to_rebuild.setdefault(include_file, set()).add(docname)
    env.toctree_includes.setdefault(docname, []).extend(include_files)


def document_toc(env: BuildEnvironment, docname: str, tags: Tags) -> Node:
    """Get the (local) table of contents for a document.

    Note that this is only the sections within the document.
    For a ToC tree that shows the document's place in the
    ToC structure, use `get_toctree_for`.
    """
    tocdepth = env.metadata[docname].get('tocdepth', 0)
    try:
        toc = _toctree_copy(env.tocs[docname], 2, tocdepth, False, tags)
    except KeyError:
        # the document does not exist any more:
        # return a dummy node that renders to nothing
        return nodes.paragraph()

    for node in toc.findall(nodes.reference):
        node['refuri'] = node['anchorname'] or '#'
    return toc


def global_toctree_for_doc(
    env: BuildEnvironment,
    docname: str,
    builder: Builder,
    *,
    tags: Tags = ...,  # type: ignore[assignment]
    collapse: bool = False,
    includehidden: bool = True,
    maxdepth: int = 0,
    titles_only: bool = False,
) -> Element | None:
    """Get the global ToC tree at a given document.

    This gives the global ToC, with all ancestors and their siblings.
    """
    if tags is ...:
        warnings.warn(
            "'tags' will become a required keyword argument "
            'for global_toctree_for_doc() in Sphinx 11.0.',
            RemovedInSphinx11Warning,
            stacklevel=2,
        )
        tags = builder.tags

    resolved = (
        _resolve_toctree(
            env,
            docname,
            builder,
            toctree_node,
            prune=True,
            maxdepth=int(maxdepth),
            titles_only=titles_only,
            collapse=collapse,
            includehidden=includehidden,
            tags=tags,
        )
        for toctree_node in env.master_doctree.findall(addnodes.toctree)
    )
    toctrees = [toctree for toctree in resolved if toctree is not None]

    if not toctrees:
        return None
    result = toctrees[0]
    for toctree in toctrees[1:]:
        result.extend(toctree.children)
    return result


def _resolve_toctree(
    env: BuildEnvironment,
    docname: str,
    builder: Builder,
    toctree: addnodes.toctree,
    *,
    prune: bool = True,
    maxdepth: int = 0,
    titles_only: bool = False,
    collapse: bool = False,
    includehidden: bool = False,
    tags: Tags,
) -> Element | None:
    """Resolve a *toctree* node into individual bullet lists with titles
    as items, returning None (if no containing titles are found) or
    a new node.

    If *prune* is True, the tree is pruned to *maxdepth*, or if that is 0,
    to the value of the *maxdepth* option on the *toctree* node.
    If *titles_only* is True, only toplevel document titles will be in the
    resulting tree.
    If *collapse* is True, all branches not containing docname will
    be collapsed.
    """
    if toctree.get('hidden', False) and not includehidden:
        return None

    # For reading the following two helper function, it is useful to keep
    # in mind the node structure of a toctree (using HTML-like node names
    # for brevity):
    #
    # 

    #   

    #     

    #     

    #     ...
    #     

    #       ...
    #     
    #   

    # 

    #
    # The transformation is made in two passes in order to avoid
    # interactions between marking and pruning the tree.
    # See: https://github.com/sphinx-doc/sphinx/issues/1046

    toctree_ancestors = _get_toctree_ancestors(env.toctree_includes, docname)
    included = Matcher(env.config.include_patterns)
    excluded = Matcher(env.config.exclude_patterns)

    maxdepth = maxdepth or toctree.get('maxdepth', -1)
    if not titles_only and toctree.get('titlesonly', False):
        titles_only = True
    if not includehidden and toctree.get('includehidden', False):
        includehidden = True

    tocentries = _entries_from_toctree(
        env,
        prune,
        titles_only,
        collapse,
        includehidden,
        tags,
        toctree_ancestors,
        included,
        excluded,
        toctree,
        [],
    )
    if not tocentries:
        return None

    newnode = addnodes.compact_paragraph('', '')
    if caption := toctree.attributes.get('caption'):
        caption_node = nodes.title(caption, '', *[nodes.Text(caption)])
        caption_node.line = toctree.line
        caption_node.source = toctree.source
        caption_node.rawsource = toctree['rawcaption']
        if hasattr(toctree, 'uid'):
            # move uid to caption_node to translate it
            caption_node.uid = toctree.uid  # type: ignore[attr-defined]
            del toctree.uid
        newnode.append(caption_node)
    newnode.extend(tocentries)
    newnode['toctree'] = True

    # prune the tree to maxdepth, also set toc depth and current classes
    _toctree_add_classes(newnode, 1, docname)
    newnode = _toctree_copy(newnode, 1, maxdepth if prune else 0, collapse, tags)

    if (
        isinstance(newnode[-1], nodes.Element) and len(newnode[-1]) == 0
    ):  # No titles found
        return None

    # set the target paths in the toctrees (they are not known at TOC
    # generation time)
    for refnode in newnode.findall(nodes.reference):
        if url_re.match(refnode['refuri']) is None:
            rel_uri = builder.get_relative_uri(docname, refnode['refuri'])
            refnode['refuri'] = rel_uri + refnode['anchorname']
    return newnode


def _entries_from_toctree(
    env: BuildEnvironment,
    prune: bool,
    titles_only: bool,
    collapse: bool,
    includehidden: bool,
    tags: Tags,
    toctree_ancestors: Set[str],
    included: Matcher,
    excluded: Matcher,
    toctreenode: addnodes.toctree,
    parents: list[str],
    subtree: bool = False,
) -> list[Element]:
    """Return TOC entries for a toctree node."""
    entries: list[Element] = []
    for title, ref in toctreenode['entries']:
        try:
            toc, refdoc = _toctree_entry(
                title,
                ref,
                env,
                prune,
                collapse,
                tags,
                toctree_ancestors,
                included,
                excluded,
                toctreenode,
                parents,
            )
        except LookupError:
            continue

        # children of toc are:
        # - list_item + compact_paragraph + (reference and subtoc)
        # - only + subtoc
        # - toctree
        children: Iterable[nodes.Element] = toc.children  # type: ignore[assignment]

        # if titles_only is given, only keep the main title and
        # sub-toctrees
        if titles_only:
            # delete everything but the toplevel title(s)
            # and toctrees
            for top_level in children:
                # nodes with length 1 don't have any children anyway
                if len(top_level) > 1:
                    if subtrees := list(top_level.findall(addnodes.toctree)):
                        top_level[1][:] = subtrees  # type: ignore[index]
                    else:
                        top_level.pop(1)
        # resolve all sub-toctrees
        for sub_toc_node in list(toc.findall(addnodes.toctree)):
            if sub_toc_node.get('hidden', False) and not includehidden:
                continue
            for i, entry in enumerate(
                _entries_from_toctree(
                    env,
                    prune,
                    titles_only,
                    collapse,
                    includehidden,
                    tags,
                    toctree_ancestors,
                    included,
                    excluded,
                    sub_toc_node,
                    [refdoc, *parents],
                    subtree=True,
                ),
                start=sub_toc_node.parent.index(sub_toc_node) + 1,
            ):
                sub_toc_node.parent.insert(i, entry)
            sub_toc_node.parent.remove(sub_toc_node)

        entries.extend(children)

    if not subtree:
        ret = nodes.bullet_list()
        ret += entries
        return [ret]

    return entries


def _toctree_entry(
    title: str,
    ref: str,
    env: BuildEnvironment,
    prune: bool,
    collapse: bool,
    tags: Tags,
    toctree_ancestors: Set[str],
    included: Matcher,
    excluded: Matcher,
    toctreenode: addnodes.toctree,
    parents: list[str],
) -> tuple[Element, str]:
    from sphinx.domains.std import StandardDomain

    try:
        refdoc = ''
        if url_re.match(ref):
            toc = _toctree_url_entry(title, ref)
        elif ref == 'self':
            toc = _toctree_self_entry(title, toctreenode['parent'], env.titles)
        elif ref in StandardDomain._virtual_doc_names:
            toc = _toctree_generated_entry(title, ref)
        else:
            if ref in parents:
                logger.warning(
                    __('circular toctree references detected, ignoring: %s <- %s'),
                    ref,
                    ' <- '.join(parents),
                    location=ref,
                    type='toc',
                    subtype='circular',
                )
                msg = 'circular reference'
                raise LookupError(msg)

            toc, refdoc = _toctree_standard_entry(
                title,
                ref,
                env.metadata[ref].get('tocdepth', 0),
                env.tocs[ref],
                toctree_ancestors,
                prune,
                collapse,
                tags,
            )

        if not toc.children:
            # empty toc means: no titles will show up in the toctree
            logger.warning(
                __(
                    'toctree contains reference to document %r that '
                    "doesn't have a title: no link will be generated"
                ),
                ref,
                location=toctreenode,
                type='toc',
                subtype='no_title',
            )
    except KeyError:
        # this is raised if the included file does not exist
        ref_path = str(env.doc2path(ref, False))
        if excluded(ref_path):
            message = __('toctree contains reference to excluded document %r')
            subtype = 'excluded'
        elif not included(ref_path):
            message = __('toctree contains reference to non-included document %r')
            subtype = 'not_included'
        else:
            message = __('toctree contains reference to non-existing document %r')
            subtype = 'not_readable'

        logger.warning(message, ref, location=toctreenode, type='toc', subtype=subtype)
        raise
    return toc, refdoc


def _toctree_url_entry(title: str, ref: str) -> nodes.bullet_list:
    if title is None:
        title = ref
    reference = nodes.reference(
        '', '', internal=False, refuri=ref, anchorname='', *[nodes.Text(title)]
    )
    para = addnodes.compact_paragraph('', '', reference)
    item = nodes.list_item('', para)
    toc = nodes.bullet_list('', item)
    return toc


def _toctree_self_entry(
    title: str,
    ref: str,
    titles: dict[str, nodes.title],
) -> nodes.bullet_list:
    # 'self' refers to the document from which this
    # toctree originates
    if not title:
        title = clean_astext(titles[ref])
    reference = nodes.reference(
        '', '', internal=True, refuri=ref, anchorname='', *[nodes.Text(title)]
    )
    para = addnodes.compact_paragraph('', '', reference)
    item = nodes.list_item('', para)
    # don't show subitems
    toc = nodes.bullet_list('', item)
    return toc


def _toctree_generated_entry(title: str, ref: str) -> nodes.bullet_list:
    from sphinx.domains.std import StandardDomain

    docname, sectionname = StandardDomain._virtual_doc_names[ref]
    if not title:
        title = sectionname
    reference = nodes.reference('', title, internal=True, refuri=docname, anchorname='')
    para = addnodes.compact_paragraph('', '', reference)
    item = nodes.list_item('', para)
    # don't show subitems
    toc = nodes.bullet_list('', item)
    return toc


def _toctree_standard_entry(
    title: str,
    ref: str,
    maxdepth: int,
    toc: nodes.bullet_list,
    toctree_ancestors: Set[str],
    prune: bool,
    collapse: bool,
    tags: Tags,
) -> tuple[nodes.bullet_list, str]:
    refdoc = ref
    if ref in toctree_ancestors and (not prune or maxdepth <= 0):
        toc = toc.deepcopy()
    else:
        toc = _toctree_copy(toc, 2, maxdepth, collapse, tags)

    if title and toc.children and len(toc.children) == 1:
        child = toc.children[0]
        for refnode in child.findall(nodes.reference):
            if refnode['refuri'] == ref and not refnode['anchorname']:
                refnode.children[:] = [nodes.Text(title)]
    return toc, refdoc


def _toctree_add_classes(node: Element, depth: int, docname: str) -> None:
    """Add 'toctree-l%d' and 'current' classes to the toctree."""
    for subnode in node.children:
        if isinstance(subnode, (addnodes.compact_paragraph, nodes.list_item)):
            # for 
 and 
, indicate the depth level and recurse
            subnode['classes'].append(f'toctree-l{depth - 1}')
            _toctree_add_classes(subnode, depth, docname)
        elif isinstance(subnode, nodes.bullet_list):
            # for 
, just recurse
            _toctree_add_classes(subnode, depth + 1, docname)
        elif isinstance(subnode, nodes.reference):
            # for , identify which entries point to the current
            # document and therefore may not be collapsed
            if subnode['refuri'] == docname:
                if not subnode['anchorname']:
                    # give the whole branch a 'current' class
                    # (useful for styling it differently)
                    branchnode: Element = subnode
                    while branchnode:
                        branchnode['classes'].append('current')
                        branchnode = branchnode.parent
                # mark the list_item as "on current page"
                if subnode.parent.parent.get('iscurrent'):
                    # but only if it's not already done
                    return
                while subnode:
                    subnode['iscurrent'] = True
                    subnode = subnode.parent


def _toctree_copy[ET: Element](
    node: ET, depth: int, maxdepth: int, collapse: bool, tags: Tags
) -> ET:
    """Utility: Cut and deep-copy a TOC at a specified depth."""
    assert not isinstance(node, addnodes.only)
    depth = max(depth - 1, 1)
    copied = _toctree_copy_seq(node, depth, maxdepth, collapse, tags, initial_call=True)
    assert len(copied) == 1
    return copied[0]  # type: ignore[return-value]


def _toctree_copy_seq(
    node: Node,
    depth: int,
    maxdepth: int,
    collapse: bool,
    tags: Tags,
    *,
    initial_call: bool = False,
    is_current: bool = False,
) -> list[Element]:
    copy: Element
    if isinstance(node, (addnodes.compact_paragraph, nodes.list_item)):
        # for 
 and 
, just recurse
        copy = node.copy()
        for subnode in node.children:
            copy += _toctree_copy_seq(  # type: ignore[assignment,operator]
                subnode, depth, maxdepth, collapse, tags, is_current='iscurrent' in node
            )
        return [copy]

    if isinstance(node, nodes.bullet_list):
        # for 
, copy if the entry is top-level
        # or, copy if the depth is within bounds and;
        # collapsing is disabled or the sub-entry's parent is 'current'.
        # The boolean is constant so is calculated outwith the loop.
        keep_bullet_list_sub_nodes = depth <= 1 or (
            (depth <= maxdepth or maxdepth <= 0)
            and (not collapse or is_current or 'iscurrent' in node)
        )
        if not keep_bullet_list_sub_nodes and not initial_call:
            return []
        depth += 1
        copy = node.copy()
        for subnode in node.children:
            copy += _toctree_copy_seq(
                subnode, depth, maxdepth, collapse, tags, is_current='iscurrent' in node
            )
        return [copy]

    if isinstance(node, addnodes.toctree):
        # copy sub toctree nodes for later processing
        return [node.copy()]

    if isinstance(node, addnodes.only):
        # only keep children if the only node matches the tags
        if not _only_node_keep_children(node, tags):
            return []
        copied: list[Element] = []
        for subnode in node.children:
            copied += _toctree_copy_seq(
                subnode, depth, maxdepth, collapse, tags, is_current='iscurrent' in node
            )
        return copied

    if isinstance(node, (nodes.reference, nodes.title)):
        # deep copy references and captions
        sub_node_copy = node.copy()
        sub_node_copy.children = [child.deepcopy() for child in node.children]
        for child in sub_node_copy.children:
            child.parent = sub_node_copy
        return [sub_node_copy]

    msg = f'Unexpected node type {node.__class__.__name__!r}!'
    raise ValueError(msg)


def _get_toctree_ancestors(
    toctree_includes: dict[str, list[str]],
    docname: str,
) -> Set[str]:
    parent: dict[str, str] = {}
    for p, children in toctree_includes.items():
        parent |= dict.fromkeys(children, p)
    ancestors: list[str] = []
    d = docname
    while d in parent and d not in ancestors:
        ancestors.append(d)
        d = parent[d]
    # use dict keys for ordered set operations
    return dict.fromkeys(ancestors).keys()


class TocTree:
    def __init__(self, env: BuildEnvironment) -> None:
        self.env = env

    def note(self, docname: str, toctreenode: addnodes.toctree) -> None:
        note_toctree(self.env, docname, toctreenode)

    def resolve(
        self,
        docname: str,
        builder: Builder,
        toctree: addnodes.toctree,
        prune: bool = True,
        maxdepth: int = 0,
        titles_only: bool = False,
        collapse: bool = False,
        includehidden: bool = False,
    ) -> Element | None:
        return _resolve_toctree(
            self.env,
            docname,
            builder,
            toctree,
            prune=prune,
            maxdepth=maxdepth,
            titles_only=titles_only,
            collapse=collapse,
            includehidden=includehidden,
            tags=builder.tags,
        )

    def get_toctree_ancestors(self, docname: str) -> list[str]:
        return [*_get_toctree_ancestors(self.env.toctree_includes, docname)]

    def get_toc_for(self, docname: str, builder: Builder) -> Node:
        return document_toc(self.env, docname, self.env._tags)

    def get_toctree_for(
        self,
        docname: str,
        builder: Builder,
        collapse: bool,
        **kwargs: Any,
    ) -> Element | None:
        return global_toctree_for_doc(
            self.env, docname, builder, tags=builder.tags, collapse=collapse, **kwargs
        )