sphinx_ultra/env/

toctree.rs

//! Sphinx's toctree bookkeeping: the read-phase half of
//! `sphinx/environment/collectors/toctree.py` plus the two pieces of
//! `sphinx/directives/other.py` and `sphinx/environment/adapters/toctree.py`
//! that feed it.
//!
//! Three ports live here, in the order the build runs them:
//!
//! 1. [`resolve_entries`] — `TocTree.parse_content` (`directives/other.py:88`):
//!    turns the directive's raw content lines into the `entries`/`includefiles`
//!    attributes of the `toctree` node, resolving relative docnames, expanding
//!    `:glob:` patterns and dropping targets that aren't real documents. This
//!    is environment-dependent (it needs the full docname set), which is why
//!    the parser takes a `found_docs` set: Sphinx resolves at parse time too,
//!    from `env.found_docs`.
//! 2. [`build_toc`] — `TocTreeCollector.process_doc` (`collectors/toctree.py:64`):
//!    the document's local table of contents as a doctree-shaped
//!    `bullet_list`, with every `toctree` node copied into it.
//! 3. [`note_toctree`] — `adapters/toctree.py:32`: the toctree graph
//!    (`toctree_includes`, `files_to_rebuild`, `glob_toctrees`,
//!    `numbered_toctrees`).
//! 4. [`collect_relations`] / [`toctree_ancestors`] / [`check_consistency`]
//!    — the whole-project reads of that graph
//!    (`environment/__init__.py:778-823`, `adapters/toctree.py:562`), which
//!    only make sense once every document has been noted.
//!
//! 5. [`resolve_toctree`] — `_resolve_toctree` (`adapters/toctree.py:119`):
//!    the write-phase expansion of a `toctree` node into nested bullet
//!    lists, as far as the search index needs it (see its doc comment for
//!    what the HTML writer will still have to add).
//!
//! [`document_title`] is the neighbouring `TitleCollector.process_doc`
//! (`collectors/title.py:27`), which shares this module's
//! `SphinxContentsFilter` port.
//!
//! NOT here (later wave-4 tasks): `assign_section_numbers` /
//! `assign_figure_numbers` (they write `toc_secnumbers`/`toc_fignumbers` and
//! stamp `secnumber` onto the references this module builds).

use std::collections::{BTreeMap, BTreeSet};

use crate::doctree::{kinds, AttrValue, Doctree, Node, Span};
use crate::env::numbers::clean_astext;
use crate::env::BuildEnvironment;
use crate::matching;
use crate::utils::py_repr_str;

/// Sphinx's `StandardDomain._virtual_doc_names` (`domains/std/__init__.py:784-788`):
/// docnames that resolve even though no source file produces them.
///
/// Careful: `_virtual_doc_names` is a **dict**, and every consumer that
/// treats it as a name set takes `frozenset(...)` of it — i.e. its *keys*
/// (`directives/other.py:91`, `collectors/toctree.py:287`,
/// `adapters/toctree.py:330`). The middle entry is therefore `modindex`,
/// the label authors write in a toctree; `py-modindex` is that key's
/// *value*, the docname the page is finally written to, and is not itself
/// a virtual name.
pub(crate) const VIRTUAL_DOC_NAMES: [&str; 3] = ["genindex", "modindex", "search"];

// ---------------------------------------------------------------------------
// 1. Entry resolution (sphinx/directives/other.py TocTree.parse_content)
// ---------------------------------------------------------------------------

/// Everything one `toctree` directive needs resolved against the project's
/// document set — the inputs of `TocTree.parse_content`.
#[derive(Debug, Clone, Copy)]
pub struct ToctreeContent<'a> {
    /// The directive's content lines, with blank ones already removed.
    pub content: &'a [String],
    /// The containing document.
    pub docname: &'a str,
    pub glob: bool,
    pub reversed: bool,
    /// Source-table index of the `.. toctree::` marker's line (the node's
    /// `source`): every diagnostic below is stamped with it.
    pub source: u16,
    /// 1-based line of the `.. toctree::` marker. Sphinx logs every
    /// diagnostic below with `location=toctree`, i.e. the directive node's
    /// source info — *not* the offending entry's own line.
    pub line: u32,
    /// Every docname the project discovered (sphinx `env.found_docs`).
    pub found_docs: &'a BTreeSet<String>,
    /// `source_suffix`, in configuration order; the first is what
    /// `doc2path` appends for a document that does not exist.
    pub source_suffixes: &'a [&'a str],
    /// `exclude_patterns`, which decide whether a missing entry is reported
    /// as excluded or as nonexisting.
    pub exclude_patterns: &'a [String],
}

/// What kind of toctree diagnostic this is, kept alongside the Sphinx
/// message so the builder can map it onto its own coarse
/// [`crate::error::WarningType`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum ToctreeWarningKind {
    /// An entry naming a document that is excluded or absent.
    MissingDocument,
    /// A `:glob:` pattern that matched nothing.
    EmptyGlob,
    /// A document already claimed by an earlier entry.
    DuplicateEntry,
    /// Not a Sphinx diagnostic: a `:glob:` pattern this crate could not
    /// compile. Python's `fnmatch` cannot fail, so Sphinx has no equivalent
    /// — but silently treating the pattern as matching nothing would hide a
    /// real bug behind an `empty_glob` warning.
    PatternError,
}

/// One diagnostic produced while resolving a toctree's entries.
///
/// Carried on the parse record (and therefore through the document cache)
/// rather than logged on the spot: resolution happens inside the parser,
/// which has no warning sink, and a cache hit that skipped the parse must
/// still reproduce the build's warnings.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct ToctreeWarning {
    /// Source-table index of the `.. toctree::` directive's line: a
    /// toctree written inside an included file warns against THAT file
    /// (`location=toctree` is the node, whose `source` is the included
    /// file's). Deliberately not `#[serde(default)]` — the warning rides
    /// the document cache, and a pre-provenance record decoding with
    /// source 0 would name the includer again (cache-shape rule,
    /// [`crate::rst::RegistryExport::program_options`]).
    pub source: u16,
    /// 1-based line of the `.. toctree::` directive (Sphinx's
    /// `location=toctree`), within `source`.
    pub line: u32,
    /// The message, formatted exactly as Sphinx formats it.
    pub message: String,
    /// Sphinx's `type.subtype` category, or `None` where Sphinx logs the
    /// warning without a `type` (see [`crate::error::BuildWarning::category`]).
    pub category: Option<String>,
    pub kind: ToctreeWarningKind,
}

/// `toctree['entries']` (title, ref) pairs plus `toctree['includefiles']`.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ResolvedEntries {
    /// `(title, ref)`; `ref` is a resolved docname, an external URL, or the
    /// literal `self`.
    pub entries: Vec<(Option<String>, String)>,
    /// The subset of `entries` that are real documents, in the same order.
    pub includefiles: Vec<String>,
    /// Diagnostics for the entries that did not resolve. The single source
    /// of truth for toctree warnings: nothing downstream re-resolves.
    pub warnings: Vec<ToctreeWarning>,
}

impl ResolvedEntries {
    /// The `entries` attribute as docutils renders it: one Python tuple
    /// repr per item (`(None, 'intro')`), which `pformat` then
    /// `serial_escape`s and joins.
    pub fn entries_attr(&self) -> AttrValue {
        AttrValue::List(
            self.entries
                .iter()
                .map(|(title, target)| {
                    let title = match title {
                        Some(t) => py_repr_str(t),
                        None => "None".to_string(),
                    };
                    format!("({title}, {})", py_repr_str(target))
                })
                .collect(),
        )
    }

    pub fn includefiles_attr(&self) -> AttrValue {
        AttrValue::List(self.includefiles.clone())
    }
}

/// Resolve a toctree directive's content lines against the document set.
///
/// Exact port of `TocTree.parse_content` (`sphinx/directives/other.py:88-179`),
/// **including all four of its `logger.warning` calls** — they come back on
/// [`ResolvedEntries::warnings`] instead of going to a logger, because this
/// runs inside the parser. This is the project's only toctree resolver: the
/// build's user-visible toctree diagnostics are exactly these warnings, so
/// what warns and what resolves can never disagree.
///
/// The one deliberate addition is [`ToctreeWarningKind::PatternError`],
/// which has no Sphinx counterpart (see its doc comment).
///
/// Not ported: `env.note_reread()` on a missing entry (nothing consumes the
/// re-read set yet).
pub fn resolve_entries(input: &ToctreeContent<'_>) -> ResolvedEntries {
    let &ToctreeContent {
        content,
        docname,
        glob,
        reversed,
        source,
        line,
        found_docs,
        source_suffixes,
        exclude_patterns,
    } = input;

    // `all_docnames` is consumed as entries claim documents (so a glob never
    // re-lists what an earlier entry named); `frozen` keeps the full set for
    // the existence check. The current document is not a candidate: a
    // toctree entry naming its own document is "nonexisting" to Sphinx.
    let mut all: BTreeSet<&str> = found_docs.iter().map(String::as_str).collect();
    all.extend(VIRTUAL_DOC_NAMES);
    all.remove(docname);
    let frozen = all.clone();

    let mut out = ResolvedEntries::default();
    let mut warnings: Vec<ToctreeWarning> = Vec::new();
    // Takes its sink as an argument rather than capturing it, so it holds no
    // borrow across the loop body that also mutates `out`.
    let warn = |sink: &mut Vec<ToctreeWarning>,
                message: String,
                category: Option<&str>,
                kind: ToctreeWarningKind| {
        sink.push(ToctreeWarning {
            source,
            line,
            message,
            category: category.map(str::to_string),
            kind,
        });
    };

    for entry in content {
        if entry.is_empty() {
            continue;
        }
        let explicit = split_explicit_title(entry);
        let url_match = is_url(entry);

        if glob && has_glob_metachars(entry) && explicit.is_none() && !url_match {
            let pattern = docname_join(docname, entry);
            // BTreeSet iteration order == sorted(), as sphinx does.
            let mut matched: Vec<String> = Vec::new();
            let mut pattern_error = None;
            for candidate in all.iter().filter(|d| !VIRTUAL_DOC_NAMES.contains(d)) {
                match matching::pattern_match(candidate, &pattern) {
                    Ok(true) => matched.push((*candidate).to_string()),
                    Ok(false) => {}
                    Err(e) => {
                        pattern_error.get_or_insert_with(|| e.to_string());
                    }
                }
            }
            if let Some(error) = pattern_error {
                warn(
                    &mut warnings,
                    format!(
                        "toctree glob pattern {} is not usable: {error}",
                        py_repr_str(entry)
                    ),
                    None,
                    ToctreeWarningKind::PatternError,
                );
            } else if matched.is_empty() {
                warn(
                    &mut warnings,
                    format!(
                        "toctree glob pattern {} didn't match any documents",
                        py_repr_str(entry)
                    ),
                    // sphinx passes `subtype='empty_glob'` but no `type`, so
                    // no `[...]` suffix is appended.
                    None,
                    ToctreeWarningKind::EmptyGlob,
                );
            }
            for name in matched {
                all.remove(name.as_str());
                out.entries.push((None, name.clone()));
                out.includefiles.push(name);
            }
            continue;
        }

        let (title, reference) = match explicit {
            Some((title, target)) => (Some(title.to_string()), target),
            None => (None, entry.as_str()),
        };
        let mut resolved = reference;
        for suffix in source_suffixes {
            if let Some(stripped) = resolved.strip_suffix(suffix) {
                resolved = stripped;
                break;
            }
        }
        let resolved = docname_join(docname, resolved);

        if url_match || reference == "self" {
            out.entries.push((title, reference.to_string()));
            continue;
        }
        if !frozen.contains(resolved.as_str()) {
            // sphinx matches `exclude_patterns` against `doc2path(ref,
            // base=False)` — the source-relative path, which for a document
            // that does not exist is the docname plus the *first* configured
            // source suffix.
            let path = format!(
                "{resolved}{}",
                source_suffixes.first().copied().unwrap_or_default()
            );
            let (message, category) = if matches_any(&path, exclude_patterns) {
                (
                    "toctree contains reference to excluded document",
                    "toc.excluded",
                )
            } else {
                (
                    "toctree contains reference to nonexisting document",
                    "toc.not_readable",
                )
            };
            warn(
                &mut warnings,
                format!("{message} {}", py_repr_str(&resolved)),
                Some(category),
                ToctreeWarningKind::MissingDocument,
            );
            continue;
        }
        // sphinx warns when the document was already claimed, but appends
        // the entry either way.
        if !all.remove(resolved.as_str()) {
            warn(
                &mut warnings,
                format!("duplicated entry found in toctree: {resolved}"),
                Some("toc.duplicate_entry"),
                ToctreeWarningKind::DuplicateEntry,
            );
        }
        out.entries.push((title, resolved.clone()));
        out.includefiles.push(resolved);
    }

    // `:reversed:` flips the two entry lists only; diagnostics keep the
    // order they were produced in.
    if reversed {
        out.entries.reverse();
        out.includefiles.reverse();
    }
    out.warnings = warnings;
    out
}

/// Sphinx's `Matcher` (`util/matching.py`): does any pattern match?
/// A pattern that fails to compile matches nothing — the caller that cares
/// (glob expansion) checks compilation separately.
fn matches_any(path: &str, patterns: &[String]) -> bool {
    patterns
        .iter()
        .any(|pattern| matching::pattern_match(path, pattern).unwrap_or(false))
}

/// Split `Some Title <target>` into its two halves, as Sphinx's
/// `explicit_title_re` (`^(.+?)\s*<(.*?)>$`, `util/nodes.py`) does: the
/// **first** `<` that leaves a non-empty title wins, and the line must end
/// with `>`. A bare `<foo>` is therefore a literal target named `<foo>`,
/// not an empty-titled reference.
pub fn split_explicit_title(entry: &str) -> Option<(&str, &str)> {
    let entry = entry.strip_suffix('>')?;
    let open = entry.find('<')?;
    if open == 0 {
        return None;
    }
    let title = entry[..open].trim_end();
    if title.is_empty() {
        return None;
    }
    Some((title, &entry[open + 1..]))
}

/// Sphinx `url_re` (`(?P<schema>.+)://.*`, anchored with `.match`): *some*
/// `://` preceded by at least one character — the regex backtracks, so a
/// leading `://` does not rule out a later one satisfying the schema part.
fn is_url(entry: &str) -> bool {
    entry.match_indices("://").any(|(at, _)| at >= 1)
}

/// Sphinx `glob_re` (`.*[*?\[].*`).
fn has_glob_metachars(entry: &str) -> bool {
    entry.contains(['*', '?', '['])
}

/// Sphinx `docname_join` (`util/__init__.py`):
/// `posixpath.normpath(posixpath.join('/' + basedocname, '..', docname))[1:]`
/// — a leading `/` makes the target source-root-relative, anything else is
/// relative to the referencing document's directory, and `.`/`..` segments
/// are normalized.
pub fn docname_join(base_docname: &str, docname: &str) -> String {
    let (base, target) = match docname.strip_prefix('/') {
        Some(stripped) => ("", stripped),
        None => (
            base_docname.rsplit_once('/').map(|(d, _)| d).unwrap_or(""),
            docname,
        ),
    };

    let mut segments: Vec<&str> = Vec::new();
    for seg in base.split('/').chain(target.split('/')) {
        match seg {
            "" | "." => {}
            ".." => {
                segments.pop();
            }
            s => segments.push(s),
        }
    }
    segments.join("/")
}

// ---------------------------------------------------------------------------
// 2. build_toc (sphinx/environment/collectors/toctree.py process_doc)
// ---------------------------------------------------------------------------

/// The document's local table of contents (`env.tocs[docname]`) and its
/// entry count (`env.toc_num_entries[docname]`).
///
/// Exact port of `TocTreeCollector.process_doc`'s nested `build_toc`:
/// sections (title filtered through [`filter_title_children`], anchor `''`
/// for the first entry and `'#' + ids[0]` afterwards), `only` wrappers, and
/// — inside any other element — `toctree` copies plus the object signatures
/// of `desc` nodes, which contribute
/// `compact_paragraph[skip_section_number] > reference > literal` entries.
///
/// An empty document yields an empty `bullet_list` and 0 entries.
pub fn build_toc(doctree: &Doctree, docname: &str) -> (Node, u32) {
    let mut num_entries = 0u32;
    let toc = build_toc_level(&doctree.root.children, docname, &mut num_entries)
        .unwrap_or_else(|| Node::elem(kinds::BULLET_LIST, Span::ZERO));
    (toc, num_entries)
}

fn build_toc_level(nodes: &[Node], docname: &str, num_entries: &mut u32) -> Option<Node> {
    let mut entries: Vec<Node> = Vec::new();

    for node in nodes {
        // docutils Text nodes aren't Elements; sphinx's isinstance chain
        // skips them entirely.
        if node.kind == kinds::TEXT {
            continue;
        }

        if node.kind == kinds::SECTION {
            // sphinx: `title = sectionnode[0]` — the section's first child.
            let title_children = node
                .children
                .first()
                .map(filter_title_children)
                .unwrap_or_default();
            let anchorname = make_anchor_name(&node.attrs.ids, num_entries);

            let mut reference = Node::elem(kinds::REFERENCE, Span::ZERO);
            reference.set("anchorname", AttrValue::Str(anchorname));
            reference.set("internal", AttrValue::Int(1));
            reference.set("refuri", AttrValue::Str(docname.to_string()));
            reference.children = title_children;

            let mut para = Node::elem(kinds::COMPACT_PARAGRAPH, Span::ZERO);
            para.children.push(reference);
            let mut item = Node::elem(kinds::LIST_ITEM, Span::ZERO);
            item.children.push(para);
            if let Some(sub) = build_toc_level(&node.children, docname, num_entries) {
                item.children.push(sub);
            }
            entries.push(item);
        } else if node.kind == kinds::ONLY {
            // Deferred tag filtering: the entries stay in the toc wrapped in
            // a fresh `only` node carrying the same expression.
            let mut only = Node::elem(kinds::ONLY, Span::ZERO);
            if let Some(expr) = node.get("expr") {
                only.set("expr", expr.clone());
            }
            if let Some(sub) = build_toc_level(&node.children, docname, num_entries) {
                only.children = sub.children;
                entries.push(only);
            }
        } else {
            // Any other element: `findall()` over the whole subtree for
            // `toctree` nodes to copy into the toc and `desc` nodes whose
            // signatures become object entries. (sphinx `continue`s on
            // nested sections, which only skips *processing* them — findall
            // still descends.)
            collect_body_entries(node, docname, num_entries, &mut entries, &[]);
        }
    }

    if entries.is_empty() {
        return None;
    }
    let mut list = Node::elem(kinds::BULLET_LIST, Span::ZERO);
    list.children = entries;
    Some(list)
}

/// The `elif isinstance(sectionnode, nodes.Element)` arm of `build_toc`
/// (`collectors/toctree.py:112-181`), in document order.
///
/// Sphinx keeps a `memo_parents` map from each `desc` to the `list_item` its
/// last signature produced, and attaches a nested description's entries to
/// the nearest ancestor `desc` that has one. That "nearest memo'd ancestor"
/// is exactly what recursion already tracks, so it rides along as `path`:
/// the chain of indices from `entries` down to the list_item currently
/// standing in for `memo_parents`. `toctree` copies ignore it — sphinx
/// appends those to the section-level `entries` wherever it finds them.
fn collect_body_entries(
    node: &Node,
    docname: &str,
    num_entries: &mut u32,
    entries: &mut Vec<Node>,
    path: &[usize],
) {
    if node.kind == kinds::TEXT {
        return;
    }
    if node.kind == kinds::TOCTREE {
        entries.push(node.shallow_copy());
        return;
    }
    if node.kind == "desc" {
        // "Save the latest desc_signature as the one we put sub entries in."
        let mut child_path: Option<Vec<usize>> = None;
        for signature in node.children.iter().filter(|c| c.kind == "desc_signature") {
            let Some(entry) = object_toc_entry(node, signature, docname, num_entries) else {
                continue;
            };
            let target = resolve_attach_point(entries, path);
            target.push(entry);
            let mut deeper = path.to_vec();
            deeper.push(target.len() - 1);
            child_path = Some(deeper);
        }
        let child_path = child_path.unwrap_or_else(|| path.to_vec());
        for child in &node.children {
            collect_body_entries(child, docname, num_entries, entries, &child_path);
        }
        return;
    }
    for child in &node.children {
        collect_body_entries(child, docname, num_entries, entries, path);
    }
}

/// Walk `path` (a chain of list_item indices) down to the entry list a
/// nested object entry belongs in, creating the `bullet_list` each step
/// needs — sphinx's `if isinstance(root_entry[-1], bullet_list): ... else:
/// root_entry.append(bullet_list(...))` (`:167-175`). An empty path is the
/// section level itself.
fn resolve_attach_point<'a>(entries: &'a mut Vec<Node>, path: &[usize]) -> &'a mut Vec<Node> {
    let mut current = entries;
    for &index in path {
        let item = &mut current[index];
        if item.children.last().map(|c| c.kind) != Some(kinds::BULLET_LIST) {
            item.children
                .push(Node::elem(kinds::BULLET_LIST, Span::ZERO));
        }
        current = &mut item
            .children
            .last_mut()
            .expect("a bullet_list was just ensured")
            .children;
    }
    current
}

/// One object signature's toc entry (`collectors/toctree.py:129-157`), or
/// `None` for the three skips: no `_toc_name` (the domain opted out of toc
/// entries for this objtype), `:no-contents-entry:` on the description, and
/// no ids (`:no-index:`).
fn object_toc_entry(
    desc: &Node,
    signature: &Node,
    docname: &str,
    num_entries: &mut u32,
) -> Option<Node> {
    let toc_name = match signature.get("_toc_name") {
        Some(AttrValue::Str(name)) if !name.is_empty() => name.clone(),
        _ => return None,
    };
    if matches!(desc.get("no-contents-entry"), Some(AttrValue::Int(1))) {
        return None;
    }
    if signature.attrs.ids.is_empty() {
        return None;
    }
    let anchorname = make_anchor_name(&signature.attrs.ids, num_entries);

    let mut literal = Node::elem(kinds::LITERAL, Span::ZERO);
    literal.children.push(Node::text_node(toc_name, Span::ZERO));
    let mut reference = Node::elem(kinds::REFERENCE, Span::ZERO);
    reference.set("anchorname", AttrValue::Str(anchorname));
    reference.set("internal", AttrValue::Int(1));
    reference.set("refuri", AttrValue::Str(docname.to_string()));
    reference.children.push(literal);
    let mut para = Node::elem(kinds::COMPACT_PARAGRAPH, Span::ZERO);
    para.set("skip_section_number", AttrValue::Int(1));
    para.children.push(reference);
    let mut item = Node::elem(kinds::LIST_ITEM, Span::ZERO);
    item.children.push(para);
    Some(item)
}

/// `_make_anchor_name` (`collectors/toctree.py:381`): the very first entry
/// of a document gets the empty anchor (it *is* the page), everything after
/// gets `'#' + ids[0]`.
fn make_anchor_name(ids: &[String], num_entries: &mut u32) -> String {
    let anchor = if *num_entries == 0 {
        String::new()
    } else {
        // sphinx indexes ids[0] unconditionally (an id-less section past the
        // first would raise there); an id-less section yields a bare "#".
        format!("#{}", ids.first().map(String::as_str).unwrap_or(""))
    };
    *num_entries += 1;
    anchor
}

/// `SphinxContentsFilter` (`sphinx/transforms/__init__.py:350`) over
/// docutils' `ContentsFilter`/`TreeCopyVisitor`
/// (`docutils/transforms/parts.py:154`): a copy of the title's children with
/// reference-ish wrappers unwrapped (children kept, wrapper dropped) and
/// footnote/citation references and images dropped whole.
fn filter_title_children(title: &Node) -> Vec<Node> {
    let mut out = Vec::new();
    filter_into(&title.children, &mut out);
    out
}

fn filter_into(children: &[Node], out: &mut Vec<Node>) {
    for child in children {
        match child.kind {
            // SkipNode: the node and its children are dropped. (docutils'
            // base filter would keep an image's `alt` text; sphinx's
            // override drops images outright.)
            kinds::FOOTNOTE_REFERENCE | kinds::CITATION_REFERENCE | kinds::IMAGE => {}
            // SkipDeparture on a visit that never copied the node: the
            // wrapper vanishes, its children land in the enclosing parent.
            kinds::REFERENCE | kinds::TARGET | kinds::PROBLEMATIC | kinds::PENDING_XREF => {
                filter_into(&child.children, out);
            }
            kinds::TEXT => out.push(child.clone()),
            _ => {
                let mut copy = child.shallow_copy();
                filter_into(&child.children, &mut copy.children);
                out.push(copy);
            }
        }
    }
}

// ---------------------------------------------------------------------------
// 3. note_toctree (sphinx/environment/adapters/toctree.py)
// ---------------------------------------------------------------------------

/// Record one `toctree` node's file relations in the environment.
///
/// Port of `note_toctree` (`adapters/toctree.py:32-47`). Note the
/// `setdefault` in `env.toctree_includes.setdefault(docname, []).extend(...)`:
/// the key is created even when the toctree includes nothing.
pub fn note_toctree(env: &mut BuildEnvironment, docname: &str, toctree: &Node) {
    if matches!(toctree.get("glob"), Some(AttrValue::Int(n)) if *n != 0) {
        env.glob_toctrees.insert(docname.to_string());
    }
    if matches!(toctree.get("numbered"), Some(AttrValue::Int(n)) if *n != 0) {
        env.numbered_toctrees.insert(docname.to_string());
    }

    let include_files: &[String] = match toctree.get("includefiles") {
        Some(AttrValue::List(files)) => files,
        _ => &[],
    };
    for include_file in include_files {
        env.files_to_rebuild
            .entry(include_file.clone())
            .or_default()
            .insert(docname.to_string());
    }
    env.toctree_includes
        .entry(docname.to_string())
        .or_default()
        .extend(include_files.iter().cloned());
}

/// Every `toctree` node inside a built toc, in the order
/// [`build_toc`] copied them in — which is the order Sphinx calls
/// `note_toctree` in, since it notes each node at the moment it copies it.
pub fn toctree_copies(toc: &Node) -> Vec<&Node> {
    let mut out = Vec::new();
    fn walk<'a>(node: &'a Node, out: &mut Vec<&'a Node>) {
        if node.kind == kinds::TOCTREE {
            out.push(node);
        }
        for child in &node.children {
            walk(child, out);
        }
    }
    walk(toc, &mut out);
    out
}

// ---------------------------------------------------------------------------
// 4. Whole-project reads of the toctree graph
// ---------------------------------------------------------------------------

/// `[parent, prev, next]` — one document's place in the global document
/// order, as `env.collect_relations()` records it.
pub type Relation = (Option<String>, Option<String>, Option<String>);

/// Every document's `[parent, prev, next]`, from a pre-order walk of the
/// toctree graph rooted at `env.root_doc`.
///
/// Port of `BuildEnvironment.collect_relations`
/// (`environment/__init__.py:778-795`) over [`traverse_toctree`]. `prev`/
/// `next` are the flattened document order, so the first child of a
/// document has that document as its `prev` — Sphinx's chain is linear, not
/// sibling-scoped.
pub fn collect_relations(env: &BuildEnvironment) -> BTreeMap<String, Relation> {
    let order = traverse_toctree(&env.toctree_includes, &env.root_doc);
    let mut relations = BTreeMap::new();

    let mut prev: Option<String> = None;
    for (index, (parent, docname)) in order.iter().enumerate() {
        let next = order.get(index + 1).map(|(_, doc)| doc.clone());
        relations.insert(docname.clone(), (parent.clone(), prev.take(), next));
        prev = Some(docname.clone());
    }
    relations
}

/// Pre-order depth-first walk of `toctree_includes` from `root`, yielding
/// `(parent, docname)` once per document — the first visit wins.
///
/// Port of `_traverse_toctree` (`environment/__init__.py:914-939`) with one
/// deliberate difference: **descent is guarded by the visited set, not just
/// yielding**. Sphinx recurses into every child unconditionally and only
/// filters the *yields*, so a mutual `A -> B -> A` cycle recurses without
/// bound and raises `RecursionError` — a real, oracle-verified sphinx 9.1.0
/// crash (`tests/fixtures/env_differential.json` records `relations: null`
/// for the `toctree_circular` project because of it). For an acyclic graph
/// the two are equivalent: re-descending into an already-visited document
/// can only re-yield documents that were already yielded, and those are
/// filtered out anyway.
///
/// The walk is iterative for the same reason it is guarded: an explicit
/// stack cannot overflow on a deep document tree.
///
/// Sphinx logs `self referenced toctree found. Ignored.` (`toc.circular`)
/// when a document's toctree includes the document itself, and drops that
/// subtree. The drop is ported; the warning is not, because the branch is
/// unreachable in this pipeline — [`resolve_entries`] removes the current
/// document from its own candidate set, so a self-entry never reaches
/// `toctree_includes`; it is reported at parse time as
/// `toctree contains reference to nonexisting document` instead (which is
/// exactly what the oracle records for the `toctree_self_ref` project).
pub fn traverse_toctree(
    toctree_includes: &BTreeMap<String, Vec<String>>,
    root: &str,
) -> Vec<(Option<String>, String)> {
    let mut out: Vec<(Option<String>, String)> = Vec::new();
    let mut visited: BTreeSet<String> = BTreeSet::new();
    let mut stack: Vec<(Option<String>, String)> = vec![(None, root.to_string())];

    while let Some((parent, docname)) = stack.pop() {
        if parent.as_deref() == Some(docname.as_str()) {
            continue;
        }
        if !visited.insert(docname.clone()) {
            continue;
        }
        if let Some(children) = toctree_includes.get(&docname) {
            // Reversed, so the explicit stack pops them left-to-right.
            for child in children.iter().rev() {
                stack.push((Some(docname.clone()), child.clone()));
            }
        }
        out.push((parent, docname));
    }
    out
}

/// The chain of toctree parents above `docname`, nearest first, starting
/// with `docname` itself.
///
/// Port of `_get_toctree_ancestors` (`adapters/toctree.py:562-575`). A
/// document with no toctree parent has no ancestors at all — not even
/// itself — and the `d not in ancestors` guard stops the walk on a cycle
/// (which is why this function, unlike `_traverse_toctree`, survives the
/// circular corpus project).
///
/// When a document has several toctree parents the last one wins, matching
/// Sphinx's `parent |= dict.fromkeys(children, p)` over `toctree_includes`.
/// Sphinx iterates that dict in read order and this map iterates in docname
/// order; both resolve to the same "largest parent docname" for the sorted
/// read order every build of this crate performs.
pub fn toctree_ancestors(
    toctree_includes: &BTreeMap<String, Vec<String>>,
    docname: &str,
) -> Vec<String> {
    let mut parent: BTreeMap<&str, &str> = BTreeMap::new();
    for (container, children) in toctree_includes {
        for child in children {
            parent.insert(child.as_str(), container.as_str());
        }
    }

    let mut ancestors: Vec<String> = Vec::new();
    let mut current = docname;
    while let Some(next) = parent.get(current) {
        if ancestors.iter().any(|seen| seen == current) {
            break;
        }
        ancestors.push(current.to_string());
        current = next;
    }
    ancestors
}

/// Whether a [`ConsistencyMessage`] is a warning (counts toward `-W`) or an
/// informational note.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ConsistencyLevel {
    Warning,
    Info,
}

/// One diagnostic from [`check_consistency`], located at a document rather
/// than at a source line (Sphinx passes `location=docname`).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ConsistencyMessage {
    pub docname: String,
    pub message: String,
    /// Sphinx's `type.subtype` category; see
    /// [`crate::error::BuildWarning::category`].
    pub category: Option<String>,
    pub level: ConsistencyLevel,
}

/// Post-read consistency checks over the finished toctree graph.
///
/// Port of `BuildEnvironment.check_consistency`
/// (`environment/__init__.py:797-823`) and the `_check_toc_parents`
/// (`:942-960`) it calls: every document that no toctree reaches gets
/// `document isn't included in any toctree`, and every document reachable
/// from more than one gets an *informational* note (Sphinx uses
/// `logger.info` there, so it must not count toward `-W`).
///
/// Not ported: the `env-check-consistency` event and the per-domain
/// `check_consistency` hooks, neither of which exists yet.
///
/// `is_sphinx_source` answers, per docname, whether the file it came from
/// carries a suffix Sphinx's `source_suffix` covers. This crate's discovery
/// is deliberately wider than Sphinx's — it admits `.md` and `.txt`
/// alongside `.rst`, where Sphinx's default `source_suffix` is `{'.rst':
/// 'restructuredtext'}` (`config.py:243`, `project.py:49-88`) — and the
/// orphan warning is the one check where that difference is user-visible:
/// a `README.md` sitting in the source tree would earn a
/// `toc.not_included` warning Sphinx never emits, failing `-W` on a build
/// Sphinx passes. Everything else keeps treating those files as documents;
/// full `source_suffix` semantics arrive with MyST in wave 6.
pub fn check_consistency(
    env: &BuildEnvironment,
    is_sphinx_source: &dyn Fn(&str) -> bool,
) -> Vec<ConsistencyMessage> {
    let mut messages = Vec::new();

    let included: BTreeSet<&str> = env
        .included
        .values()
        .flatten()
        .map(String::as_str)
        .collect();

    // `all_docs` is a BTreeMap, so this is sphinx's `sorted(self.all_docs)`.
    for docname in env.all_docs.keys() {
        // Reachable from some toctree, the root itself, textually included
        // by another document, or explicitly marked `:orphan:`.
        // ...or not a document Sphinx would have read at all.
        if env.files_to_rebuild.contains_key(docname)
            || *docname == env.root_doc
            || included.contains(docname.as_str())
            || env
                .metadata
                .get(docname)
                .is_some_and(|meta| meta.contains_key("orphan"))
            || !is_sphinx_source(docname)
        {
            continue;
        }
        messages.push(ConsistencyMessage {
            docname: docname.clone(),
            message: "document isn't included in any toctree".to_string(),
            category: Some("toc.not_included".to_string()),
            level: ConsistencyLevel::Warning,
        });
    }

    // The parent list is interpolated verbatim, so its order is visible.
    // Sphinx builds it from `toctree_includes` in read (insertion) order and
    // this map iterates in docname order; both are the same order for the
    // sorted read every build of this crate performs.
    let mut toc_parents: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    for (container, children) in &env.toctree_includes {
        for child in children {
            toc_parents
                .entry(child.as_str())
                .or_default()
                .push(container.as_str());
        }
    }
    for (docname, parents) in toc_parents {
        if parents.len() <= 1 {
            continue;
        }
        // sphinx interpolates the parent list with `%s`, i.e. Python's
        // `str(list)` — a repr of each element inside brackets.
        let list = parents
            .iter()
            .map(|parent| py_repr_str(parent))
            .collect::<Vec<_>>()
            .join(", ");
        let selected = parents.iter().max().expect("len > 1");
        messages.push(ConsistencyMessage {
            docname: docname.to_string(),
            message: format!(
                "document is referenced in multiple toctrees: [{list}], \
                 selecting: {selected} <- {docname}"
            ),
            category: Some("toc.multiple_toc_parents".to_string()),
            level: ConsistencyLevel::Info,
        });
    }

    messages
}

// ---------------------------------------------------------------------------
// TitleCollector (sphinx/environment/collectors/title.py)
// ---------------------------------------------------------------------------

/// `env.titles[docname]`: a fresh `title` node holding the first section
/// title's contents, filtered exactly like a toc entry's.
///
/// Port of `TitleCollector.process_doc` (`collectors/title.py:27`). Its
/// `longtitles` differ only when the document carries a `title` attribute
/// (set by the `title` directive / `<meta>`), which nothing produces yet —
/// so the caller stores this same node under both keys.
pub fn document_title(doctree: &Doctree) -> Node {
    let mut title = Node::elem(kinds::TITLE, Span::ZERO);
    match first_section(&doctree.root) {
        Some(section) => {
            if let Some(first_child) = section.children.first() {
                title.children = filter_title_children(first_child);
            }
        }
        // sphinx: `doctree.get('title', '<no title>')`.
        None => title
            .children
            .push(Node::text_node("<no title>", Span::ZERO)),
    }
    title
}

/// First `section` in document order (docutils `findall(nodes.section)`).
fn first_section(node: &Node) -> Option<&Node> {
    for child in &node.children {
        if child.kind == kinds::SECTION {
            return Some(child);
        }
        if let Some(found) = first_section(child) {
            return Some(found);
        }
    }
    None
}

// ---------------------------------------------------------------------------
// 5. _resolve_toctree (sphinx/environment/adapters/toctree.py:119-559)
// ---------------------------------------------------------------------------

/// The docname and section name each virtual toctree target resolves to:
/// `StandardDomain._virtual_doc_names` (`domains/std/__init__.py:784-788`),
/// values included this time.
const VIRTUAL_DOCS: [(&str, &str, &str); 3] = [
    ("genindex", "genindex", "Index"),
    ("modindex", "py-modindex", "Module Index"),
    ("search", "search", "Search Page"),
];

/// The `(title, ref)` pairs of a `toctree` node's `entries` attribute, read
/// back from the Python tuple reprs [`ResolvedEntries::entries_attr`] stores
/// (`(None, 'intro')`, `('Custom', 'api')`).
pub(crate) fn toctree_entries(toctree: &Node) -> Vec<(Option<String>, String)> {
    let Some(AttrValue::List(items)) = toctree.get("entries") else {
        return Vec::new();
    };
    items
        .iter()
        .filter_map(|item| parse_entry_repr(item))
        .collect()
}

/// One `(None, 'ref')` / `('title', 'ref')` tuple repr.
fn parse_entry_repr(item: &str) -> Option<(Option<String>, String)> {
    let inner = item.strip_prefix('(')?.strip_suffix(')')?;
    let (title, rest) = match inner.strip_prefix("None") {
        Some(rest) => (None, rest),
        None => {
            let (title, rest) = parse_py_str(inner)?;
            (Some(title), rest)
        }
    };
    let (target, rest) = parse_py_str(rest.strip_prefix(", ")?)?;
    rest.is_empty().then_some((title, target))
}

/// Inverse of [`py_repr_str`]: the CPython string literal `s` starts with,
/// decoded, plus whatever follows it.
fn parse_py_str(s: &str) -> Option<(String, &str)> {
    let mut chars = s.char_indices();
    let (_, quote) = chars.next()?;
    if quote != '\'' && quote != '"' {
        return None;
    }
    let mut out = String::new();
    while let Some((at, c)) = chars.next() {
        match c {
            '\\' => {
                let (_, escaped) = chars.next()?;
                let hex_digits = match escaped {
                    'n' => {
                        out.push('\n');
                        continue;
                    }
                    'r' => {
                        out.push('\r');
                        continue;
                    }
                    't' => {
                        out.push('\t');
                        continue;
                    }
                    'x' => 2,
                    'u' => 4,
                    'U' => 8,
                    other => {
                        out.push(other);
                        continue;
                    }
                };
                let mut code = 0u32;
                for _ in 0..hex_digits {
                    let (_, digit) = chars.next()?;
                    code = code.checked_mul(16)? + digit.to_digit(16)?;
                }
                out.push(char::from_u32(code)?);
            }
            c if c == quote => return Some((out, &s[at + c.len_utf8()..])),
            c => out.push(c),
        }
    }
    None
}

fn attr_flag(node: &Node, key: &'static str) -> bool {
    matches!(node.get(key), Some(AttrValue::Int(n)) if *n != 0)
}

/// `toctree.attributes.get('caption')` when it is truthy. The parser
/// stores an absent caption the way docutils prints a `None` attribute,
/// as the string `True` (`Element.starttag`), so a caption literally
/// reading `True` is indistinguishable from none and treated as none.
fn toctree_caption(toctree: &Node) -> Option<&String> {
    match toctree.get("caption") {
        Some(AttrValue::Str(caption)) if !caption.is_empty() && caption != "True" => Some(caption),
        _ => None,
    }
}

/// Resolve a `toctree` node into the nested bullet lists Sphinx writes in
/// its place: `_resolve_toctree` (`adapters/toctree.py:119-220`) with the
/// arguments the write phase passes for a document's own toctrees
/// (`get_and_resolve_doctree`: `prune=True`, the node's own `maxdepth`,
/// `collapse=False`, `includehidden=False`).
///
/// `None` is Sphinx's "renders to nothing": a hidden toctree, one with no
/// entries, or one whose entries all name documents without a title.
///
/// The result carries exactly what the search index reads from the resolved
/// tree — the caption as a `title`, every entry's title text inside
/// `reference` nodes, pruned to `maxdepth`/`titlesonly`/`tocdepth` like
/// Sphinx prunes it. Still missing for the HTML writer: the
/// `toctree-l<N>`/`current` classes and `iscurrent` marks, the relative
/// `refuri`s, and the `circular toctree references detected` warning (the
/// circular entry is dropped as Sphinx drops it, but nothing is logged).
/// `only` nodes are kept with their children: Sphinx evaluates them against
/// the build tags, which this crate does not evaluate anywhere yet.
pub fn resolve_toctree(env: &BuildEnvironment, docname: &str, toctree: &Node) -> Option<Node> {
    if attr_flag(toctree, "hidden") {
        return None;
    }
    let maxdepth = match toctree.get("maxdepth") {
        Some(AttrValue::Int(depth)) => *depth,
        _ => -1,
    };
    let ancestors = toctree_ancestors(&env.toctree_includes, docname);
    let walk = ToctreeWalk {
        env,
        titles_only: attr_flag(toctree, "titlesonly"),
        includehidden: attr_flag(toctree, "includehidden"),
        ancestors: &ancestors,
    };
    let entries = walk.entries_from_toctree(toctree, &[], false);
    if entries.is_empty() {
        return None;
    }

    let mut newnode = Node::elem(kinds::COMPACT_PARAGRAPH, Span::ZERO);
    if let Some(caption) = toctree_caption(toctree) {
        let mut title = Node::elem(kinds::TITLE, Span::ZERO);
        title
            .children
            .push(Node::text_node(caption.clone(), Span::ZERO));
        newnode.children.push(title);
    }
    newnode.children.extend(entries);
    newnode.set("toctree", AttrValue::Int(1));

    // Prune to maxdepth. `_toctree_add_classes` runs here in Sphinx; it only
    // stamps classes, which nothing below reads.
    let newnode = toctree_copy(&newnode, 1, maxdepth);
    match newnode.children.last() {
        // `isinstance(newnode[-1], nodes.Element) and len(newnode[-1]) == 0`
        // — no titles found.
        Some(last) if last.kind != kinds::TEXT && last.children.is_empty() => None,
        _ => Some(newnode),
    }
}

/// The per-resolution context `_entries_from_toctree` threads through its
/// recursion.
struct ToctreeWalk<'a> {
    env: &'a BuildEnvironment,
    titles_only: bool,
    includehidden: bool,
    ancestors: &'a [String],
}

impl ToctreeWalk<'_> {
    /// `_entries_from_toctree` (`adapters/toctree.py:223-306`).
    fn entries_from_toctree(
        &self,
        toctreenode: &Node,
        parents: &[String],
        subtree: bool,
    ) -> Vec<Node> {
        let mut entries = Vec::new();
        for (title, reference) in toctree_entries(toctreenode) {
            let Some((mut toc, refdoc)) =
                self.toctree_entry(title.as_deref(), &reference, toctreenode, parents)
            else {
                continue;
            };

            // `:titlesonly:` keeps each entry's top-level title and its
            // sub-toctrees, and nothing else.
            if self.titles_only {
                for top_level in &mut toc.children {
                    if top_level.children.len() > 1 {
                        let subtrees = find_toctrees(top_level);
                        if subtrees.is_empty() {
                            top_level.children.remove(1);
                        } else {
                            top_level.children[1].children = subtrees;
                        }
                    }
                }
            }

            let mut sub_parents = Vec::with_capacity(parents.len() + 1);
            sub_parents.push(refdoc);
            sub_parents.extend_from_slice(parents);
            self.expand_sub_toctrees(&mut toc, &sub_parents);

            entries.extend(toc.children);
        }

        if subtree {
            entries
        } else {
            let mut list = Node::elem(kinds::BULLET_LIST, Span::ZERO);
            list.children = entries;
            vec![list]
        }
    }

    /// `_toctree_entry` (`adapters/toctree.py:309-383`): the toc for one
    /// entry plus the docname it refers to (`''` for the non-document
    /// forms), or `None` where Sphinx raises `LookupError`/`KeyError` and
    /// skips the entry.
    fn toctree_entry(
        &self,
        title: Option<&str>,
        reference: &str,
        toctreenode: &Node,
        parents: &[String],
    ) -> Option<(Node, String)> {
        if is_url(reference) {
            // `_toctree_url_entry`: only a *missing* title falls back to
            // the URL; an empty explicit title stays empty.
            let text = title.unwrap_or(reference);
            return Some((leaf_entry(text, reference), String::new()));
        }
        if reference == "self" {
            // `_toctree_self_entry`: the referencing document's own title.
            let parent = match toctreenode.get("parent") {
                Some(AttrValue::Str(parent)) => parent.as_str(),
                _ => "",
            };
            let text = match title {
                Some(title) if !title.is_empty() => title.to_string(),
                _ => self
                    .env
                    .titles
                    .get(parent)
                    .map(clean_astext)
                    .unwrap_or_default(),
            };
            return Some((leaf_entry(&text, reference), String::new()));
        }
        if let Some((_, docname, sectionname)) =
            VIRTUAL_DOCS.iter().find(|(name, _, _)| *name == reference)
        {
            // `_toctree_generated_entry`.
            let text = match title {
                Some(title) if !title.is_empty() => title,
                _ => sectionname,
            };
            return Some((leaf_entry(text, docname), String::new()));
        }
        if parents.iter().any(|parent| parent == reference) {
            // `circular toctree references detected, ignoring`.
            return None;
        }
        // `env.tocs[ref]` — a KeyError here is the "non-existing document"
        // path, which `resolve_entries` already warned about at read time.
        let toc = self.env.tocs.get(reference)?;
        let tocdepth = self
            .env
            .metadata
            .get(reference)
            .and_then(|metadata| metadata.get("tocdepth"))
            .and_then(|depth| depth.trim().parse::<i64>().ok())
            .unwrap_or(0);
        Some((
            self.standard_entry(title, reference, tocdepth, toc),
            reference.to_string(),
        ))
    }

    /// `_toctree_standard_entry` (`adapters/toctree.py:431-452`).
    fn standard_entry(
        &self,
        title: Option<&str>,
        reference: &str,
        tocdepth: i64,
        toc: &Node,
    ) -> Node {
        let mut toc =
            if self.ancestors.iter().any(|ancestor| ancestor == reference) && tocdepth <= 0 {
                toc.clone()
            } else {
                toctree_copy(toc, 2, tocdepth)
            };
        if let Some(title) = title.filter(|title| !title.is_empty()) {
            if toc.children.len() == 1 {
                replace_entry_title(&mut toc.children[0], reference, title);
            }
        }
        toc
    }

    /// The `for sub_toc_node in list(toc.findall(addnodes.toctree))` loop
    /// of `_entries_from_toctree`: every sub-toctree copied into a toc is
    /// expanded in place; a hidden one stays as the bare node Sphinx leaves
    /// behind (which renders, and indexes, as nothing).
    fn expand_sub_toctrees(&self, node: &mut Node, parents: &[String]) {
        let mut index = 0;
        while index < node.children.len() {
            if node.children[index].kind != kinds::TOCTREE {
                self.expand_sub_toctrees(&mut node.children[index], parents);
                index += 1;
                continue;
            }
            if attr_flag(&node.children[index], "hidden") && !self.includehidden {
                index += 1;
                continue;
            }
            let sub_toc_node = node.children.remove(index);
            let expanded = self.entries_from_toctree(&sub_toc_node, parents, true);
            let inserted = expanded.len();
            node.children.splice(index..index, expanded);
            index += inserted;
        }
    }
}

/// `bullet_list > list_item > compact_paragraph > reference > Text`: the
/// shape of the URL, `self` and generated entries.
fn leaf_entry(text: &str, refuri: &str) -> Node {
    let mut reference = Node::elem(kinds::REFERENCE, Span::ZERO);
    reference.set("anchorname", AttrValue::Str(String::new()));
    reference.set("refuri", AttrValue::Str(refuri.to_string()));
    reference.children.push(Node::text_node(text, Span::ZERO));
    let mut para = Node::elem(kinds::COMPACT_PARAGRAPH, Span::ZERO);
    para.children.push(reference);
    let mut item = Node::elem(kinds::LIST_ITEM, Span::ZERO);
    item.children.push(para);
    let mut toc = Node::elem(kinds::BULLET_LIST, Span::ZERO);
    toc.children.push(item);
    toc
}

/// An explicit `Title <ref>` replaces the text of the entry's own
/// reference (`refuri == ref`, no anchor).
fn replace_entry_title(node: &mut Node, reference: &str, title: &str) {
    let is_entry_reference = node.kind == kinds::REFERENCE
        && matches!(node.get("refuri"), Some(AttrValue::Str(uri)) if uri == reference)
        && matches!(node.get("anchorname"), Some(AttrValue::Str(anchor)) if anchor.is_empty());
    if is_entry_reference {
        node.children = vec![Node::text_node(title, Span::ZERO)];
        return;
    }
    for child in &mut node.children {
        replace_entry_title(child, reference, title);
    }
}

/// `findall(addnodes.toctree)` below `node`, in document order, as the
/// childless copies the toc holds anyway.
fn find_toctrees(node: &Node) -> Vec<Node> {
    let mut out = Vec::new();
    fn walk(node: &Node, out: &mut Vec<Node>) {
        for child in &node.children {
            if child.kind == kinds::TOCTREE {
                out.push(child.shallow_copy());
            }
            walk(child, out);
        }
    }
    walk(node, &mut out);
    out
}

/// `_toctree_copy` (`adapters/toctree.py:485-493`): cut and copy a toc at
/// `maxdepth` (`<= 0` means unlimited).
fn toctree_copy(node: &Node, depth: i64, maxdepth: i64) -> Node {
    let depth = (depth - 1).max(1);
    let mut copied = toctree_copy_seq(node, depth, maxdepth, true);
    debug_assert_eq!(copied.len(), 1);
    copied.pop().unwrap_or_else(|| node.shallow_copy())
}

/// `_toctree_copy_seq` (`adapters/toctree.py:496-559`) with `collapse`
/// off and `only` conditions taken as true (see [`resolve_toctree`]).
fn toctree_copy_seq(node: &Node, depth: i64, maxdepth: i64, initial_call: bool) -> Vec<Node> {
    match node.kind {
        kinds::COMPACT_PARAGRAPH | kinds::LIST_ITEM => {
            let mut copy = node.shallow_copy();
            for child in &node.children {
                copy.children
                    .extend(toctree_copy_seq(child, depth, maxdepth, false));
            }
            vec![copy]
        }
        kinds::BULLET_LIST => {
            let keep = depth <= 1 || depth <= maxdepth || maxdepth <= 0;
            if !keep && !initial_call {
                return Vec::new();
            }
            let mut copy = node.shallow_copy();
            for child in &node.children {
                copy.children
                    .extend(toctree_copy_seq(child, depth + 1, maxdepth, false));
            }
            vec![copy]
        }
        // Sub-toctrees are kept for the caller to expand.
        kinds::TOCTREE => vec![node.shallow_copy()],
        kinds::ONLY => node
            .children
            .iter()
            .flat_map(|child| toctree_copy_seq(child, depth, maxdepth, false))
            .collect(),
        // References and captions are deep-copied; anything else is
        // "Unexpected node type" in Sphinx, kept whole here.
        _ => vec![node.clone()],
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::rst;

    fn docs(names: &[&str]) -> BTreeSet<String> {
        names.iter().map(|s| (*s).to_string()).collect()
    }

    fn parse(source: &str, docname: &str, found: &BTreeSet<String>) -> Doctree {
        rst::parse_rst(
            source,
            &rst::ParseOptions {
                source_path: "<snippet>".to_string(),
                sphinx: true,
                docname: docname.to_string(),
                exclude_patterns: Vec::new(),
                py: Default::default(),
                srcdir: None,
                found_docs: Some(std::sync::Arc::new(found.clone())),
                ..Default::default()
            },
        )
    }

    #[test]
    fn empty_document_yields_empty_bullet_list() {
        let doctree = parse("", "index", &docs(&[]));
        let (toc, n) = build_toc(&doctree, "index");
        assert_eq!(toc.pformat(), "<bullet_list>\n");
        assert_eq!(n, 0);
    }

    #[test]
    fn first_entry_has_empty_anchor_and_later_entries_use_ids() {
        let doctree = parse("A\n=\n\nSub\n---\n\nText.\n", "a", &docs(&["a"]));
        let (toc, n) = build_toc(&doctree, "a");
        assert_eq!(n, 2);
        assert_eq!(
            toc.pformat(),
            concat!(
                "<bullet_list>\n",
                "    <list_item>\n",
                "        <compact_paragraph>\n",
                "            <reference anchorname=\"\" internal=\"1\" refuri=\"a\">\n",
                "                A\n",
                "        <bullet_list>\n",
                "            <list_item>\n",
                "                <compact_paragraph>\n",
                "                    <reference anchorname=\"#sub\" internal=\"1\" refuri=\"a\">\n",
                "                        Sub\n",
            )
        );
    }

    /// `build_toc`'s `memo_parents` bubbling (`collectors/toctree.py:159-181`),
    /// pinned against a sphinx 9.1.0 `env.tocs['a']` for this exact source:
    /// nested descriptions nest, a multi-signature description collects its
    /// children under its LAST signature, and a description that produced no
    /// entry of its own (`describe` has no `_toc_name`) is walked past, so
    /// its children land at the section level.
    #[test]
    fn object_entries_nest_under_the_nearest_description_that_has_one() {
        let doctree = parse(
            concat!(
                "A\n=\n\n",
                ".. confval:: outer\n\n   Outer body.\n\n",
                "   .. confval:: inner\n\n      Inner body.\n\n",
                "      .. confval:: deepest\n\n         Deep body.\n\n",
                ".. confval:: sibling\n\n",
                ".. confval:: multi_a\n             multi_b\n\n",
                "   .. confval:: under_multi\n\n",
                ".. describe:: nothing\n\n   .. confval:: under_describe\n",
            ),
            "a",
            &docs(&["a"]),
        );
        let (toc, n) = build_toc(&doctree, "a");
        assert_eq!(n, 9);
        assert_eq!(
            toc.pformat(),
            concat!(
                "<bullet_list>\n",
                "    <list_item>\n",
                "        <compact_paragraph>\n",
                "            <reference anchorname=\"\" internal=\"1\" refuri=\"a\">\n",
                "                A\n",
                "        <bullet_list>\n",
                "            <list_item>\n",
                "                <compact_paragraph skip_section_number=\"1\">\n",
                "                    <reference anchorname=\"#confval-outer\" internal=\"1\" refuri=\"a\">\n",
                "                        <literal>\n",
                "                            outer\n",
                "                <bullet_list>\n",
                "                    <list_item>\n",
                "                        <compact_paragraph skip_section_number=\"1\">\n",
                "                            <reference anchorname=\"#confval-inner\" internal=\"1\" refuri=\"a\">\n",
                "                                <literal>\n",
                "                                    inner\n",
                "                        <bullet_list>\n",
                "                            <list_item>\n",
                "                                <compact_paragraph skip_section_number=\"1\">\n",
                "                                    <reference anchorname=\"#confval-deepest\" internal=\"1\" refuri=\"a\">\n",
                "                                        <literal>\n",
                "                                            deepest\n",
                "            <list_item>\n",
                "                <compact_paragraph skip_section_number=\"1\">\n",
                "                    <reference anchorname=\"#confval-sibling\" internal=\"1\" refuri=\"a\">\n",
                "                        <literal>\n",
                "                            sibling\n",
                "            <list_item>\n",
                "                <compact_paragraph skip_section_number=\"1\">\n",
                "                    <reference anchorname=\"#confval-multi_a\" internal=\"1\" refuri=\"a\">\n",
                "                        <literal>\n",
                "                            multi_a\n",
                "            <list_item>\n",
                "                <compact_paragraph skip_section_number=\"1\">\n",
                "                    <reference anchorname=\"#confval-multi_b\" internal=\"1\" refuri=\"a\">\n",
                "                        <literal>\n",
                "                            multi_b\n",
                "                <bullet_list>\n",
                "                    <list_item>\n",
                "                        <compact_paragraph skip_section_number=\"1\">\n",
                "                            <reference anchorname=\"#confval-under_multi\" internal=\"1\" refuri=\"a\">\n",
                "                                <literal>\n",
                "                                    under_multi\n",
                "            <list_item>\n",
                "                <compact_paragraph skip_section_number=\"1\">\n",
                "                    <reference anchorname=\"#confval-under_describe\" internal=\"1\" refuri=\"a\">\n",
                "                        <literal>\n",
                "                            under_describe\n",
            )
        );
    }

    /// The three `build_toc` skips: no `_toc_name` (only `confval` sets one
    /// in the std domain), `:no-contents-entry:`, and an id-less signature
    /// (`:no-index:`).
    #[test]
    fn object_entries_skip_unnamed_opted_out_and_id_less_signatures() {
        let doctree = parse(
            concat!(
                "A\n=\n\n",
                ".. envvar:: HOME\n\n",
                ".. confval:: hidden\n   :no-contents-entry:\n\n",
                ".. confval:: unindexed\n   :no-index:\n\n",
                ".. confval:: kept\n",
            ),
            "a",
            &docs(&["a"]),
        );
        let (toc, n) = build_toc(&doctree, "a");
        // The section plus exactly one object entry.
        assert_eq!(n, 2);
        let out = toc.pformat();
        assert!(out.contains("#confval-kept"), "{out}");
        assert!(!out.contains("HOME"), "{out}");
        assert!(!out.contains("hidden"), "{out}");
        assert!(!out.contains("unindexed"), "{out}");
    }

    #[test]
    fn title_inline_markup_survives_but_references_are_unwrapped() {
        let doctree = parse(
            "A `link <https://x/>`_ and *em* [#f]_\n=====================================\n\n.. [#f] note\n",
            "a",
            &docs(&["a"]),
        );
        let (toc, _) = build_toc(&doctree, "a");
        // reference wrapper dropped (its text kept), footnote_reference
        // dropped whole, emphasis kept.
        assert!(toc.pformat().contains("<emphasis>\n"), "{}", toc.pformat());
        assert!(!toc.pformat().contains("<reference anchorname=\"\" internal=\"1\" refuri=\"a\">\n                A\n                <reference"));
        assert!(
            !toc.pformat().contains("footnote_reference"),
            "{}",
            toc.pformat()
        );
        assert!(toc.pformat().contains("link"), "{}", toc.pformat());
    }

    /// An `only` node's toc entries are re-wrapped in a fresh `only`
    /// carrying the same expression, so the tag filtering can happen at
    /// render time. (A section inside `.. only::` would be the other half of
    /// this branch, but the parser rejects section titles in nested content,
    /// so a toctree is what reaches the collector today.)
    #[test]
    fn only_directive_wraps_its_entries() {
        let doctree = parse(
            ".. only:: html\n\n   .. toctree::\n\n      a\n",
            "index",
            &docs(&["index", "a"]),
        );
        let (toc, n) = build_toc(&doctree, "index");
        assert_eq!(n, 0, "a copied toctree is not a numbered entry");
        assert!(
            toc.pformat()
                .starts_with("<bullet_list>\n    <only expr=\"html\">\n        <toctree "),
            "{}",
            toc.pformat()
        );

        let mut env = BuildEnvironment::default();
        for node in toctree_copies(&toc) {
            note_toctree(&mut env, "index", node);
        }
        assert_eq!(
            env.toctree_includes.get("index"),
            Some(&vec!["a".to_string()]),
            "a toctree inside `only` still contributes to the graph"
        );
    }

    #[test]
    fn toctree_node_is_copied_into_the_toc_and_noted() {
        let found = docs(&["index", "a", "b"]);
        let doctree = parse(
            "Index\n=====\n\n.. toctree::\n\n   a\n   b\n",
            "index",
            &found,
        );
        let (toc, n) = build_toc(&doctree, "index");
        assert_eq!(n, 1, "the copied toctree is not an entry");

        let mut env = BuildEnvironment::default();
        for node in toctree_copies(&toc) {
            note_toctree(&mut env, "index", node);
        }
        assert_eq!(
            env.toctree_includes.get("index"),
            Some(&vec!["a".to_string(), "b".to_string()])
        );
        assert_eq!(
            env.files_to_rebuild.get("a"),
            Some(&BTreeSet::from(["index".to_string()]))
        );
        assert!(env.glob_toctrees.is_empty());
        assert!(env.numbered_toctrees.is_empty());
    }

    #[test]
    fn note_toctree_creates_the_includes_key_even_when_empty() {
        // sphinx `setdefault(docname, []).extend([])`.
        let mut env = BuildEnvironment::default();
        let mut toctree = Node::elem(kinds::TOCTREE, Span::ZERO);
        toctree.set("includefiles", AttrValue::List(vec![]));
        note_toctree(&mut env, "index", &toctree);
        assert_eq!(env.toctree_includes.get("index"), Some(&Vec::new()));
        assert!(env.files_to_rebuild.is_empty());
    }

    #[test]
    fn glob_and_numbered_flags_reach_the_environment() {
        let mut env = BuildEnvironment::default();
        let mut toctree = Node::elem(kinds::TOCTREE, Span::ZERO);
        toctree.set("glob", AttrValue::Int(1));
        toctree.set("numbered", AttrValue::Int(999));
        toctree.set("includefiles", AttrValue::List(vec!["a".into()]));
        note_toctree(&mut env, "index", &toctree);
        assert!(env.glob_toctrees.contains("index"));
        assert!(env.numbered_toctrees.contains("index"));
    }

    /// Every `resolve_entries` input a test needs, defaulted.
    fn content<'a>(
        lines: &'a [String],
        docname: &'a str,
        found: &'a BTreeSet<String>,
    ) -> ToctreeContent<'a> {
        ToctreeContent {
            content: lines,
            docname,
            glob: false,
            reversed: false,
            source: 0,
            line: 1,
            found_docs: found,
            source_suffixes: &[".rst"],
            exclude_patterns: &[],
        }
    }

    fn lines(entries: &[&str]) -> Vec<String> {
        entries.iter().map(|s| (*s).to_string()).collect()
    }

    #[test]
    fn entries_resolve_relative_absolute_and_self_targets() {
        let found = docs(&["index", "sub/b", "sub/c", "a"]);
        let entries = lines(&[
            "c",
            "/a",
            "self",
            "https://example.invalid/x",
            "missing",
            "sub/b",
        ]);
        let resolved = resolve_entries(&content(&entries, "sub/b", &found));
        assert_eq!(
            resolved.entries,
            vec![
                (None, "sub/c".to_string()),
                (None, "a".to_string()),
                (None, "self".to_string()),
                (None, "https://example.invalid/x".to_string()),
            ],
            "missing docs drop; `sub/b` is the current document, which is not \
             a candidate for its own toctree"
        );
        assert_eq!(
            resolved.includefiles,
            vec!["sub/c".to_string(), "a".to_string()]
        );
        assert_eq!(
            resolved
                .warnings
                .iter()
                .map(|w| w.message.as_str())
                .collect::<Vec<_>>(),
            vec![
                "toctree contains reference to nonexisting document 'sub/missing'",
                "toctree contains reference to nonexisting document 'sub/sub/b'",
            ],
            "sphinx reports the *joined* docname, so a document-relative miss \
             names the directory it was resolved against"
        );
    }

    /// The oracle's `toctree_self_ref` project: a toctree entry naming its
    /// own document is not a `self referenced toctree` — parse_content
    /// removes the current document from the candidate set first, so it
    /// comes out as an ordinary missing-document warning, and never reaches
    /// `toctree_includes`.
    #[test]
    fn an_entry_naming_its_own_document_is_reported_as_nonexisting() {
        let found = docs(&["index", "a"]);
        let entries = lines(&["index", "a"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert_eq!(resolved.includefiles, vec!["a".to_string()]);
        assert_eq!(
            resolved
                .warnings
                .iter()
                .map(|w| (w.message.as_str(), w.category.as_deref()))
                .collect::<Vec<_>>(),
            vec![(
                "toctree contains reference to nonexisting document 'index'",
                Some("toc.not_readable")
            )]
        );
    }

    /// Every diagnostic is located at the `.. toctree::` marker, not at the
    /// offending entry: sphinx passes `location=toctree`, the directive node.
    #[test]
    fn diagnostics_are_located_at_the_directive() {
        let found = docs(&["index"]);
        let entries = lines(&["missing"]);
        let resolved = resolve_entries(&ToctreeContent {
            line: 12,
            ..content(&entries, "index", &found)
        });
        assert_eq!(resolved.warnings.len(), 1);
        assert_eq!(resolved.warnings[0].line, 12);
        assert_eq!(
            resolved.warnings[0].category.as_deref(),
            Some("toc.not_readable")
        );
    }

    /// A missing target that `exclude_patterns` covers is reported as
    /// *excluded* rather than *nonexisting* (`directives/other.py:150-153`),
    /// matched against `doc2path(ref, base=False)` — the docname plus the
    /// first source suffix.
    #[test]
    fn excluded_targets_get_their_own_message() {
        let found = docs(&["index"]);
        let excluded = vec!["drafts/*".to_string()];
        let entries = lines(&["drafts/wip"]);
        let resolved = resolve_entries(&ToctreeContent {
            exclude_patterns: &excluded,
            ..content(&entries, "index", &found)
        });
        assert_eq!(
            resolved.warnings[0].message,
            "toctree contains reference to excluded document 'drafts/wip'"
        );
        assert_eq!(
            resolved.warnings[0].category.as_deref(),
            Some("toc.excluded")
        );
    }

    #[test]
    fn a_document_claimed_twice_warns_but_is_still_listed() {
        let found = docs(&["index", "a"]);
        let entries = lines(&["a", "a"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert_eq!(
            resolved.includefiles,
            vec!["a".to_string(), "a".to_string()],
            "sphinx appends the duplicate either way"
        );
        assert_eq!(
            resolved.warnings[0].message,
            "duplicated entry found in toctree: a"
        );
        assert_eq!(
            resolved.warnings[0].category.as_deref(),
            Some("toc.duplicate_entry")
        );
    }

    /// `_virtual_doc_names` is a dict, and `parse_content` unions
    /// `frozenset(...)` of it into the candidate set — so the virtual names
    /// are its **keys**. `modindex` is the one an author writes in a
    /// toctree; `py-modindex` is that key's value (the docname the module
    /// index is finally written to) and is not itself a virtual name.
    #[test]
    fn the_virtual_docnames_are_the_dict_keys_not_its_values() {
        let found = docs(&["index"]);
        let entries = lines(&["genindex", "modindex", "search"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert_eq!(
            resolved.includefiles,
            vec![
                "genindex".to_string(),
                "modindex".to_string(),
                "search".to_string()
            ]
        );
        assert!(resolved.warnings.is_empty(), "{:?}", resolved.warnings);

        let entries = lines(&["py-modindex"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert!(resolved.includefiles.is_empty());
        assert_eq!(
            resolved
                .warnings
                .iter()
                .map(|w| w.message.as_str())
                .collect::<Vec<_>>(),
            vec!["toctree contains reference to nonexisting document 'py-modindex'"]
        );
    }

    #[test]
    fn glob_entries_expand_sorted_and_skip_virtual_docs() {
        let found = docs(&["index", "pages/a", "pages/b"]);
        let entries = lines(&["pages/*"]);
        let resolved = resolve_entries(&ToctreeContent {
            glob: true,
            ..content(&entries, "index", &found)
        });
        assert_eq!(
            resolved.includefiles,
            vec!["pages/a".to_string(), "pages/b".to_string()]
        );
        assert_eq!(
            resolved.entries_attr(),
            AttrValue::List(vec![
                "(None, 'pages/a')".to_string(),
                "(None, 'pages/b')".to_string()
            ])
        );
        assert!(resolved.warnings.is_empty());
    }

    /// A dead glob warns with the entry as authored (sphinx `%r` of `entry`,
    /// not of the joined pattern), and — because sphinx passes no `type` —
    /// carries no `[type.subtype]` category.
    #[test]
    fn a_glob_that_matches_nothing_warns() {
        let found = docs(&["index", "pages/a"]);
        let entries = lines(&["missing*"]);
        let resolved = resolve_entries(&ToctreeContent {
            glob: true,
            ..content(&entries, "index", &found)
        });
        assert!(resolved.includefiles.is_empty());
        assert_eq!(
            resolved.warnings,
            vec![ToctreeWarning {
                source: 0,
                line: 1,
                message: "toctree glob pattern 'missing*' didn't match any documents".to_string(),
                category: None,
                kind: ToctreeWarningKind::EmptyGlob,
            }]
        );
    }

    /// An uncompilable pattern must not masquerade as "matched nothing":
    /// that would hide the bug behind a plausible Sphinx warning.
    #[test]
    fn an_uncompilable_glob_pattern_is_reported_as_such() {
        let found = docs(&["index", "a"]);
        // `[z-a]` is a character class with a reversed range: our pattern
        // translation hands it to `regex`, which refuses it.
        let entries = lines(&["[z-a]*"]);
        let resolved = resolve_entries(&ToctreeContent {
            glob: true,
            ..content(&entries, "index", &found)
        });
        assert_eq!(resolved.warnings.len(), 1, "{:?}", resolved.warnings);
        assert_eq!(resolved.warnings[0].kind, ToctreeWarningKind::PatternError);
        assert!(
            resolved.warnings[0]
                .message
                .starts_with("toctree glob pattern '[z-a]*' is not usable:"),
            "{}",
            resolved.warnings[0].message
        );
    }

    #[test]
    fn explicit_titles_and_suffixes() {
        let found = docs(&["index", "other"]);
        let entries = lines(&["Linked <other.rst>", "<foo>"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert_eq!(
            resolved.entries,
            vec![(Some("Linked".to_string()), "other".to_string())],
            "`<foo>` is a literal (missing) target, not an empty title"
        );
        assert_eq!(
            resolved.entries_attr(),
            AttrValue::List(vec!["('Linked', 'other')".to_string()])
        );
        assert_eq!(
            resolved.warnings[0].message,
            "toctree contains reference to nonexisting document '<foo>'"
        );
    }

    #[test]
    fn reversed_flips_both_lists() {
        let found = docs(&["index", "a", "b"]);
        let entries = lines(&["a", "b"]);
        let resolved = resolve_entries(&ToctreeContent {
            reversed: true,
            ..content(&entries, "index", &found)
        });
        assert_eq!(
            resolved.includefiles,
            vec!["b".to_string(), "a".to_string()]
        );
    }

    /// `url_re` is `(?P<schema>.+)://.*` matched (not fullmatched) from the
    /// start, and `.+` backtracks: only a `://` at offset 0 with no other
    /// occurrence fails to be a URL.
    #[test]
    fn url_detection_matches_the_backtracking_regex() {
        assert!(is_url("https://example.invalid/x"));
        assert!(is_url("a://b"));
        assert!(!is_url("://leading"));
        assert!(
            is_url("://a://b"),
            "the second `://` has a non-empty schema before it"
        );
        assert!(!is_url("plain/docname"));
    }

    #[test]
    fn virtual_docnames_are_valid_entries() {
        let found = docs(&["index"]);
        let entries = lines(&["genindex"]);
        let resolved = resolve_entries(&content(&entries, "index", &found));
        assert_eq!(resolved.includefiles, vec!["genindex".to_string()]);
        assert!(resolved.warnings.is_empty());
    }

    // -----------------------------------------------------------------
    // Whole-project reads of the graph
    // -----------------------------------------------------------------

    /// An environment holding nothing but a toctree graph and a document
    /// set, which is all the graph reads look at.
    fn graph(root: &str, includes: &[(&str, &[&str])]) -> BuildEnvironment {
        let mut env = BuildEnvironment {
            root_doc: root.to_string(),
            ..Default::default()
        };
        for (container, children) in includes {
            let children: Vec<String> = children.iter().map(|c| (*c).to_string()).collect();
            for child in &children {
                env.files_to_rebuild
                    .entry(child.clone())
                    .or_default()
                    .insert((*container).to_string());
            }
            env.toctree_includes
                .insert((*container).to_string(), children);
        }
        for docname in env
            .toctree_includes
            .keys()
            .cloned()
            .chain(env.files_to_rebuild.keys().cloned())
            .collect::<Vec<_>>()
        {
            env.all_docs.insert(docname, 0);
        }
        env.all_docs.insert(root.to_string(), 0);
        env
    }

    fn relation(env: &BuildEnvironment, docname: &str) -> (String, String, String) {
        let show = |value: &Option<String>| value.clone().unwrap_or_else(|| "-".to_string());
        let (parent, prev, next) = collect_relations(env)[docname].clone();
        (show(&parent), show(&prev), show(&next))
    }

    /// The oracle's `toctree_nested` shape: `index -> [a, b]`, `a -> [a1,
    /// a2]`. `prev`/`next` chain the flattened pre-order, so `a1`'s `prev`
    /// is its own parent `a`, not a sibling.
    #[test]
    fn relations_chain_the_preorder_walk() {
        let env = graph("index", &[("index", &["a", "b"]), ("a", &["a1", "a2"])]);
        assert_eq!(
            relation(&env, "index"),
            ("-".into(), "-".into(), "a".into())
        );
        assert_eq!(
            relation(&env, "a"),
            ("index".into(), "index".into(), "a1".into())
        );
        assert_eq!(relation(&env, "a1"), ("a".into(), "a".into(), "a2".into()));
        assert_eq!(relation(&env, "a2"), ("a".into(), "a1".into(), "b".into()));
        assert_eq!(
            relation(&env, "b"),
            ("index".into(), "a2".into(), "-".into())
        );
    }

    /// The oracle's `toctree_multi_parent` shape: `c` is reachable from
    /// both `a` and `b`, and the *first* visit — depth-first through `a` —
    /// is the one that sets its parent.
    #[test]
    fn a_document_with_two_parents_keeps_the_first_visit() {
        let env = graph(
            "index",
            &[("index", &["a", "b"]), ("a", &["c"]), ("b", &["c"])],
        );
        assert_eq!(relation(&env, "c"), ("a".into(), "a".into(), "b".into()));
        assert_eq!(
            relation(&env, "b"),
            ("index".into(), "c".into(), "-".into())
        );
    }

    #[test]
    fn a_project_without_toctrees_relates_only_its_root() {
        let env = graph("index", &[]);
        assert_eq!(
            relation(&env, "index"),
            ("-".into(), "-".into(), "-".into())
        );
        assert_eq!(collect_relations(&env).len(), 1);
    }

    /// Sphinx 9.1.0 raises `RecursionError` here (its `traversed` set filters
    /// yields but never guards descent). The port must terminate and answer.
    #[test]
    fn a_mutual_cycle_terminates_instead_of_recursing_forever() {
        let env = graph("index", &[("index", &["a"]), ("a", &["b"]), ("b", &["a"])]);
        let relations = collect_relations(&env);
        assert_eq!(
            relations.keys().collect::<Vec<_>>(),
            vec!["a", "b", "index"],
            "every document is still reached exactly once"
        );
        assert_eq!(relation(&env, "b"), ("a".into(), "a".into(), "-".into()));
    }

    /// A document whose own toctree lists it (only reachable from a stale
    /// or hand-built environment — [`resolve_entries`] never produces it):
    /// sphinx drops that subtree, and so does this.
    #[test]
    fn a_self_parenting_toctree_drops_its_subtree() {
        let env = graph("index", &[("index", &["a"]), ("a", &["a"])]);
        let relations = collect_relations(&env);
        assert_eq!(relations.keys().collect::<Vec<_>>(), vec!["a", "index"]);
    }

    #[test]
    fn ancestors_walk_up_to_the_root_and_stop_on_cycles() {
        let includes = graph("index", &[("index", &["a"]), ("a", &["b"])]).toctree_includes;
        assert_eq!(toctree_ancestors(&includes, "b"), vec!["b", "a"]);
        assert_eq!(
            toctree_ancestors(&includes, "index"),
            Vec::<String>::new(),
            "a document with no toctree parent has no ancestors, not even itself"
        );

        let cyclic = graph("index", &[("a", &["b"]), ("b", &["a"])]).toctree_includes;
        assert_eq!(toctree_ancestors(&cyclic, "a"), vec!["a", "b"]);
    }

    #[test]
    fn documents_no_toctree_reaches_are_reported_as_orphans() {
        let mut env = graph("index", &[("index", &["a"])]);
        env.all_docs.insert("stray".to_string(), 0);
        env.all_docs.insert("textually_included".to_string(), 0);
        env.all_docs.insert("marked".to_string(), 0);
        env.included.insert(
            "a".to_string(),
            BTreeSet::from(["textually_included".to_string()]),
        );
        env.metadata.insert(
            "marked".to_string(),
            BTreeMap::from([("orphan".to_string(), String::new())]),
        );

        let messages = check_consistency(&env, &|_| true);
        assert_eq!(
            messages
                .iter()
                .map(|m| (m.docname.as_str(), m.level))
                .collect::<Vec<_>>(),
            vec![("stray", ConsistencyLevel::Warning)],
            "the root, toctree'd, textually included and `:orphan:` \
             documents are all exempt; {messages:?}"
        );
        assert_eq!(
            messages[0].message,
            "document isn't included in any toctree"
        );
        assert_eq!(messages[0].category.as_deref(), Some("toc.not_included"));
    }

    /// Several toctree parents is an *info*, never a warning: sphinx uses
    /// `logger.info`, so it must not be able to fail a `-W` build.
    #[test]
    fn several_toctree_parents_is_informational() {
        let env = graph(
            "index",
            &[("index", &["a", "b"]), ("a", &["c"]), ("b", &["c"])],
        );
        let messages = check_consistency(&env, &|_| true);
        assert_eq!(messages.len(), 1, "{messages:?}");
        assert_eq!(messages[0].level, ConsistencyLevel::Info);
        assert_eq!(messages[0].docname, "c");
        assert_eq!(
            messages[0].message,
            "document is referenced in multiple toctrees: ['a', 'b'], selecting: b <- c"
        );
    }

    #[test]
    fn docname_join_normalizes() {
        assert_eq!(docname_join("sub/b", "c"), "sub/c");
        assert_eq!(docname_join("sub/b", "/a"), "a");
        assert_eq!(docname_join("sub/b", "../a"), "a");
        assert_eq!(docname_join("index", "a"), "a");
    }

    #[test]
    fn document_title_filters_like_a_toc_entry() {
        let doctree = parse("A *b* c\n=======\n\nText.\n", "a", &docs(&["a"]));
        assert_eq!(
            document_title(&doctree).pformat(),
            "<title>\n    A \n    <emphasis>\n        b\n     c\n"
        );
    }

    #[test]
    fn document_title_without_a_section_says_no_title() {
        let doctree = parse("Just a paragraph.\n", "a", &docs(&["a"]));
        assert_eq!(
            document_title(&doctree).pformat(),
            "<title>\n    <no title>\n"
        );
    }

    #[test]
    fn toctree_entries_read_back_what_entries_attr_wrote() {
        let entries = ResolvedEntries {
            entries: vec![
                (None, "intro".to_string()),
                (Some("Custom <x>".to_string()), "api/it's".to_string()),
                (
                    Some("say \"hi\"".to_string()),
                    "https://example.org/a?b=c".to_string(),
                ),
                (Some("tab\there".to_string()), "self".to_string()),
            ],
            ..Default::default()
        };
        let mut toctree = Node::elem(kinds::TOCTREE, Span::ZERO);
        toctree.set("entries", entries.entries_attr());
        assert_eq!(toctree_entries(&toctree), entries.entries);
    }

    /// A three-document project: `index` lists `child`, a URL and an
    /// explicitly titled `leaf` at `:maxdepth: 2` with a caption; `child`
    /// lists `leaf` itself from under its second-level section.
    #[test]
    fn resolve_toctree_expands_like_sphinx() {
        let found = docs(&["index", "child", "leaf"]);
        let mut env = BuildEnvironment::default();
        let sources = [
            ("index", "Root\n====\n\n.. toctree::\n   :maxdepth: 2\n   :caption: Contents\n\n   child\n   https://example.org\n   Explicit <leaf>\n"),
            ("child", "Child\n=====\n\nChild Section\n-------------\n\nChild Sub\n~~~~~~~~~\n\n.. toctree::\n\n   leaf\n"),
            ("leaf", "Leaf\n====\n\nLeaf Section\n------------\n"),
        ];
        let mut doctrees = BTreeMap::new();
        for (docname, source) in sources {
            let doctree = parse(source, docname, &found);
            env.titles
                .insert(docname.to_string(), document_title(&doctree));
            let (toc, _) = build_toc(&doctree, docname);
            for toctree in toctree_copies(&toc) {
                note_toctree(&mut env, docname, toctree);
            }
            env.tocs.insert(docname.to_string(), toc);
            doctrees.insert(docname, doctree);
        }

        let toctree = find_toctrees(&doctrees["index"].root)
            .into_iter()
            .next()
            .expect("index has a toctree");
        // The childless copy carries the attributes; resolution reads only those.
        let resolved = resolve_toctree(&env, "index", &toctree).expect("renders");
        assert_eq!(
            resolved.pformat(),
            concat!(
                "<compact_paragraph toctree=\"1\">\n",
                "    <title>\n",
                "        Contents\n",
                "    <bullet_list>\n",
                "        <list_item>\n",
                "            <compact_paragraph>\n",
                "                <reference anchorname=\"\" internal=\"1\" refuri=\"child\">\n",
                "                    Child\n",
                "            <bullet_list>\n",
                "                <list_item>\n",
                "                    <compact_paragraph>\n",
                "                        <reference anchorname=\"#child-section\" internal=\"1\" refuri=\"child\">\n",
                "                            Child Section\n",
                "        <list_item>\n",
                "            <compact_paragraph>\n",
                "                <reference anchorname=\"\" refuri=\"https://example.org\">\n",
                "                    https://example.org\n",
                "        <list_item>\n",
                "            <compact_paragraph>\n",
                "                <reference anchorname=\"\" internal=\"1\" refuri=\"leaf\">\n",
                "                    Explicit\n",
                "            <bullet_list>\n",
                "                <list_item>\n",
                "                    <compact_paragraph>\n",
                "                        <reference anchorname=\"#leaf-section\" internal=\"1\" refuri=\"leaf\">\n",
                "                            Leaf Section\n",
            )
        );
        // (Verified against sphinx-build 9.1.0 on the same three sources:
        // the child's own sub-toctree lives under its second-level section
        // and is pruned by `:maxdepth: 2`, while the explicit entry keeps
        // the leaf's first-level section.)

        // A hidden toctree renders to nothing.
        let mut hidden = toctree.clone();
        hidden.set("hidden", AttrValue::Int(1));
        assert!(resolve_toctree(&env, "index", &hidden).is_none());

        // `:titlesonly:` keeps the child's title and its sub-toctree only.
        let mut titles_only = toctree.clone();
        titles_only.set("titlesonly", AttrValue::Int(1));
        let resolved = resolve_toctree(&env, "index", &titles_only).expect("renders");
        let text = resolved.astext();
        assert!(text.contains("Child") && text.contains("Leaf"));
        assert!(!text.contains("Child Section"));
    }
}