scryer-engine 0.3.0

use std::collections::{HashMap, HashSet};
use std::path::{Path, PathBuf};

use tree_sitter::{Node, Parser};

use super::fallback::ScmFallbackResolver;
use crate::parsers::{crate_root_for, module_path_for};
use crate::payload::{RawCodeGraphEdge, RawScope, RawSymbol, RawSymbolReference, Via};

/// Output of cross-file reference extraction for a file.
#[derive(Debug, Clone, Default)]
pub struct ExtractedReferences {
    pub file_path: PathBuf,
    pub references: Vec<RawSymbolReference>,
    pub edges: Vec<RawCodeGraphEdge>,
}

/// The tree-sitter grammar for a source file, by extension.
///
/// The one place that maps extensions to grammars for reference extraction, so the resolver
/// and `reference_target_at` can't disagree. JavaScript uses the TypeScript grammars.
fn tree_sitter_language_for(rel_path: &Path) -> Option<tree_sitter::Language> {
    let ext = rel_path.extension()?.to_str()?.to_ascii_lowercase();
    match ext.as_str() {
        "rs" => Some(tree_sitter_rust::LANGUAGE.into()),
        "py" => Some(tree_sitter_python::LANGUAGE.into()),
        "ts" | "js" => Some(tree_sitter_typescript::LANGUAGE_TYPESCRIPT.into()),
        "tsx" | "jsx" => Some(tree_sitter_typescript::LANGUAGE_TSX.into()),
        _ => None,
    }
}

/// Symbols by bare name: `(defining file, qualified name, kind)`, ordered by file path and then by
/// position in the file, so lookups never depend on hash order.
type GlobalSymbols<'a> = HashMap<&'a str, Vec<(&'a Path, &'a str, &'a str)>>;

fn build_global_symbols<'a>(
    all_symbols: &'a HashMap<PathBuf, Vec<RawSymbol>>,
    all_scopes: &HashMap<PathBuf, Vec<RawScope>>,
) -> GlobalSymbols<'a> {
    let mut files: Vec<_> = all_symbols.iter().collect();
    files.sort_by(|a, b| a.0.cmp(b.0));
    let mut global: GlobalSymbols = HashMap::with_capacity(all_symbols.len() * 4);
    for (path, syms) in files {
        let scopes = all_scopes.get(path).map_or(&[][..], Vec::as_slice);
        for sym in syms {
            // Kind `free_fn`: a function that can be named on its own, unlike a method.
            let kind = if is_free_function(sym, scopes) {
                FREE_FN
            } else {
                sym.kind.as_str()
            };
            global.entry(sym.name.as_str()).or_default().push((
                path.as_path(),
                sym.qualified_name.as_str(),
                kind,
            ));
        }
    }
    global
}

/// Choose among same-named symbols for a bare name used in `from`: the same file, then the
/// same directory, then the first file in path order. (Ingest applies the same rule when it
/// links by name.)
fn pick_global<'a>(candidates: &[(&Path, &'a str, &'a str)], from: &Path) -> Option<&'a str> {
    // Only symbols in the same language: a name that exists in a Python file is not what a
    // Rust call means.
    let same = || {
        candidates
            .iter()
            .filter(|(p, _, _)| crate::parsers::same_language(p, from))
    };
    same()
        .find(|(p, _, _)| *p == from)
        .or_else(|| same().find(|(p, _, _)| p.parent() == from.parent()))
        .or_else(|| same().next())
        .map(|(_, qualified, _)| *qualified)
}

/// Kind label in [`GlobalSymbols`] for a function that can be named by itself.
const FREE_FN: &str = "free_fn";

/// Whether a symbol of this [`GlobalSymbols`] kind can be what a bare name refers to: not a
/// method (which needs a receiver or a `Type::` path) and not a `use` stub, which only names
/// something defined elsewhere.
fn nameable_kind(kind: &str) -> bool {
    !matches!(kind, "fn" | "method" | "reexport")
}

/// A function that a bare identifier can refer to: not a method, which needs a receiver or a
/// `Type::` path. Methods are the functions that sit in a class or `impl` scope.
fn is_free_function(sym: &RawSymbol, scopes: &[RawScope]) -> bool {
    sym.kind == "fn"
        && !sym
            .scope_local_id
            .and_then(|id| scopes.iter().find(|s| s.local_id == id))
            .is_some_and(|scope| scope.scope_kind == "class")
}

fn is_rust_file(rel_path: &Path) -> bool {
    !matches!(
        rel_path.extension().and_then(|e| e.to_str()),
        Some("py" | "ts" | "tsx" | "js" | "jsx")
    )
}

/// Resolves each reference candidate of a file: the project's one definition of the name, else a symbol of the file, else a by-name pick.
pub struct CrossFileResolver;

impl CrossFileResolver {
    /// Resolve all references and call graph edges across a collection of project files.
    ///
    /// `root_crate` is the name of the project's root Cargo package, if it has one. The result
    /// does not depend on the order of `files`: symbols are tabled in path order and every
    /// file is resolved against the complete table.
    pub fn resolve_project(
        files: &[(PathBuf, String)],
        all_symbols: &HashMap<PathBuf, Vec<RawSymbol>>,
        all_scopes: &HashMap<PathBuf, Vec<RawScope>>,
        root_crate: Option<&str>,
    ) -> anyhow::Result<HashMap<PathBuf, ExtractedReferences>> {
        let global_symbols = build_global_symbols(all_symbols, all_scopes);

        // Everything below runs in path order, whatever order `files` arrived in.
        let mut sorted: Vec<&(PathBuf, String)> = files.iter().collect();
        sorted.sort_by(|a, b| a.0.cmp(&b.0));

        let mut results = HashMap::new();
        for (rel_path, content) in sorted {
            let candidates = collect_candidates(rel_path, content)?;
            let extracted = Self::resolve_candidates(
                rel_path,
                candidates,
                all_symbols,
                all_scopes,
                &global_symbols,
                root_crate,
            );
            results.insert(rel_path.clone(), extracted);
        }

        Ok(results)
    }

    /// Extract and resolve references for a single file.
    pub fn resolve_file_references(
        rel_path: &Path,
        content: &str,
        all_symbols: &HashMap<PathBuf, Vec<RawSymbol>>,
        all_scopes: &HashMap<PathBuf, Vec<RawScope>>,
        root_crate: Option<&str>,
    ) -> anyhow::Result<ExtractedReferences> {
        let global_symbols = build_global_symbols(all_symbols, all_scopes);
        let candidates = collect_candidates(rel_path, content)?;
        Ok(Self::resolve_candidates(
            rel_path,
            candidates,
            all_symbols,
            all_scopes,
            &global_symbols,
            root_crate,
        ))
    }

    fn resolve_candidates(
        rel_path: &Path,
        candidates: Vec<CandidateReference>,
        all_symbols: &HashMap<PathBuf, Vec<RawSymbol>>,
        all_scopes: &HashMap<PathBuf, Vec<RawScope>>,
        global_symbols: &GlobalSymbols<'_>,
        root_crate: Option<&str>,
    ) -> ExtractedReferences {
        let mut references = Vec::new();
        let mut edges = Vec::new();

        let file_symbols = all_symbols.get(rel_path).cloned().unwrap_or_default();
        let file_scopes = all_scopes.get(rel_path).cloned().unwrap_or_default();
        let is_rust = is_rust_file(rel_path);

        for cand in candidates {
            if cand.role == "value" {
                // Only a reference to a function counts, and it is matched against the symbol
                // table alone: a name that is not a function is a local or a type.
                let local = file_symbols
                    .iter()
                    .find(|s| s.name == cand.identifier && is_free_function(s, &file_scopes));
                let (target, via) = match local {
                    Some(sym) => (Some(sym.qualified_name.as_str()), Via::Exact),
                    None => {
                        let functions: Vec<_> = global_symbols
                            .get(cand.identifier.as_str())
                            .map(|c| {
                                c.iter()
                                    .filter(|(_, _, kind)| *kind == FREE_FN)
                                    .copied()
                                    .collect()
                            })
                            .unwrap_or_default();
                        (pick_global(&functions, rel_path), Via::Name)
                    }
                };
                if let Some(target) = target {
                    references.push(RawSymbolReference {
                        target_symbol_name: target.to_string(),
                        role: cand.role.clone(),
                        start_byte: cand.start_byte,
                        end_byte: cand.end_byte,
                        line_number: cand.line_number,
                        via,
                    });
                }
                continue;
            }

            let mut resolved_target: Option<String> = None;
            let mut via = Via::Name;

            // `self.name(..)` / `this.name(..)`: the method of the surrounding type, when it
            // has one. (A trait's default method, say, is not found here and stays by name.)
            let mut typed_receiver = false;
            if let Some(ty) = cand.receiver_type.as_deref()
                && let Some(candidates) = global_symbols.get(cand.identifier.as_str())
            {
                let own: Vec<_> = candidates
                    .iter()
                    .filter(|(_, qualified, _)| {
                        qualified.ends_with(&format!("::{ty}::{}", cand.identifier))
                            || qualified.ends_with(&format!(".{ty}.{}", cand.identifier))
                    })
                    .copied()
                    .collect();
                if let Some(qualified) = pick_global(&own, rel_path) {
                    resolved_target = Some(qualified.to_string());
                    typed_receiver = true;
                    via = Via::Exact;
                }
            }

            // `T::name(..)` with `T: Trait`: the method `name` declared by one of T's traits.
            if resolved_target.is_none()
                && !cand.bounds.is_empty()
                && let Some(candidates) = global_symbols.get(cand.identifier.as_str())
            {
                resolved_target = cand.bounds.iter().find_map(|bound| {
                    let suffix = format!("::{bound}::{}", cand.identifier);
                    candidates
                        .iter()
                        .find(|(_, qualified, _)| qualified.ends_with(&suffix))
                        .map(|(_, qualified, _)| qualified.to_string())
                });
                if resolved_target.is_some() {
                    via = Via::Exact;
                }
            }

            // Path-qualified Rust references (`crate::a::f`, `other_crate::f`, `Type::new`)
            // are resolved by qualified-name matching at ingest time.
            if resolved_target.is_none()
                && is_rust
                && let Some(path) = cand.path.as_deref()
            {
                resolved_target = normalize_rust_path(path, rel_path).map(|normalized| {
                    // Sibling crates, tests and benches name the root package by its crate
                    // name; the index calls its items `crate::...`.
                    match (root_crate, normalized.split_once("::")) {
                        (Some(root), Some((first, rest))) if first == root => {
                            format!("crate::{rest}")
                        }
                        _ => normalized,
                    }
                });
                via = Via::Exact;
            }

            // A call through a local binding: the callee is a function declared inside the
            // function that holds the call, or something that is not in the index at all.
            if cand.local && resolved_target.is_none() {
                match nested_declaration(&file_symbols, &cand.identifier, cand.start_byte) {
                    Some(symbol) => {
                        resolved_target = Some(symbol.qualified_name.clone());
                        via = Via::Exact;
                    }
                    None => continue,
                }
            }

            // Tier 1: the one definition in the project that a bare name can mean. A method
            // call names a method, which needs its receiver, so it is only ever matched by
            // name.
            let same_name = global_symbols
                .get(cand.identifier.as_str())
                .map_or(&[][..], Vec::as_slice);
            let nameable: Vec<_> = same_name
                .iter()
                .filter(|(path, _, kind)| {
                    nameable_kind(kind) && crate::parsers::same_language(path, rel_path)
                })
                .copied()
                .collect();
            if resolved_target.is_none()
                && !cand.method
                && let [(_, qualified, _)] = nameable.as_slice()
            {
                resolved_target = Some(qualified.to_string());
                via = Via::Exact;
            }

            // Tier 2: a symbol of this file with the name: its own definition or the `use`
            // that imports it. With several candidate definitions the import is the precise
            // link: it leads to the definition the file means.
            if resolved_target.is_none()
                && let Some(res) = ScmFallbackResolver::resolve_identifier(
                    &cand.identifier,
                    rel_path,
                    cand.line_number,
                    cand.col_number,
                    &file_scopes,
                    &file_symbols,
                )
            {
                resolved_target = Some(res.qualified_name);
                via = Via::Exact;
            }

            // Tier 3: by name. Among definitions a bare name can mean, else among everything
            // with the name; otherwise defer to a name lookup against the persisted index at
            // ingest time, so references into files not parsed in this pass still link.
            if resolved_target.is_none() {
                let pool: &[_] = if !cand.method && !nameable.is_empty() {
                    &nameable
                } else {
                    same_name
                };
                resolved_target = Some(
                    pick_global(pool, rel_path)
                        .map_or_else(|| cand.identifier.clone(), str::to_string),
                );
            }

            if let Some(target_qualified) = resolved_target {
                references.push(RawSymbolReference {
                    target_symbol_name: target_qualified.clone(),
                    role: cand.role.clone(),
                    start_byte: cand.start_byte,
                    end_byte: cand.end_byte,
                    line_number: cand.line_number,
                    via: if cand.in_macro {
                        Via::Macro
                    } else if cand.method && !typed_receiver {
                        // Without the receiver's type, a method call is only a name match.
                        Via::Name
                    } else {
                        via
                    },
                });

                if cand.role == "call" {
                    let enclosing = enclosing_function(&file_symbols, cand.start_byte)
                        .or(cand.enclosing_symbol);
                    if let Some(enclosing) = enclosing {
                        edges.push(RawCodeGraphEdge {
                            source_symbol_name: enclosing,
                            target_symbol_name: target_qualified.clone(),
                            edge_type: "calls".to_string(),
                        });
                    }
                } else if cand.role == "reexport"
                    && let Some(reexport_sym) = file_symbols
                        .iter()
                        .find(|s| s.name == cand.identifier && s.kind == "reexport")
                {
                    edges.push(RawCodeGraphEdge {
                        source_symbol_name: reexport_sym.qualified_name.clone(),
                        target_symbol_name: target_qualified,
                        edge_type: "reexports".to_string(),
                    });
                }
            }
        }

        // Deduplicate references and edges. Sorted first: `dedup_by` only removes adjacent
        // duplicates.
        references.sort_by(|a, b| {
            (a.start_byte, &a.role, &a.target_symbol_name).cmp(&(
                b.start_byte,
                &b.role,
                &b.target_symbol_name,
            ))
        });
        references.dedup_by(|a, b| {
            a.start_byte == b.start_byte
                && a.role == b.role
                && a.target_symbol_name == b.target_symbol_name
        });
        edges.sort_by(|a, b| {
            (&a.source_symbol_name, &a.target_symbol_name, &a.edge_type).cmp(&(
                &b.source_symbol_name,
                &b.target_symbol_name,
                &b.edge_type,
            ))
        });
        edges.dedup_by(|a, b| {
            a.source_symbol_name == b.source_symbol_name
                && a.target_symbol_name == b.target_symbol_name
                && a.edge_type == b.edge_type
        });

        ExtractedReferences {
            file_path: rel_path.to_path_buf(),
            references,
            edges,
        }
    }
}

/// The text to parse for `content`: Rust sources are prepared (see
/// [`crate::parsers::rust::prepare_source`]), which keeps every byte offset; other languages
/// are parsed as written.
fn prepared_source<'a>(rel_path: &Path, content: &'a str) -> std::borrow::Cow<'a, str> {
    if rel_path.extension().and_then(|e| e.to_str()) == Some("rs") {
        crate::parsers::rust::prepare_source(content)
    } else {
        std::borrow::Cow::Borrowed(content)
    }
}

/// Parse `content` and collect the reference candidates in it. A file with no grammar, or
/// that tree-sitter cannot parse at all, has none.
fn collect_candidates(rel_path: &Path, content: &str) -> anyhow::Result<Vec<CandidateReference>> {
    // No grammar for this extension: nothing to extract (and never parse it as Rust).
    let Some(language) = tree_sitter_language_for(rel_path) else {
        return Ok(Vec::new());
    };
    let mut parser = Parser::new();
    parser.set_language(&language).map_err(|e| {
        anyhow::anyhow!(
            "Failed to set tree-sitter language for {}: {e}",
            rel_path.display()
        )
    })?;
    let Some(tree) = parser.parse(prepared_source(rel_path, content).as_bytes(), None) else {
        return Ok(Vec::new());
    };
    let mut visitor = ReferenceVisitor {
        source: content,
        candidates: Vec::new(),
        locals: Vec::new(),
        generics: Vec::new(),
        types: Vec::new(),
    };
    visitor.traverse(tree.root_node(), None);
    Ok(visitor.candidates)
}

struct CandidateReference {
    identifier: String,
    /// Full path text for scoped references (`a::b::f`), without generic arguments.
    path: Option<String>,
    role: String,
    start_byte: usize,
    end_byte: usize,
    line_number: u32,
    col_number: u32,
    enclosing_symbol: Option<String>,
    /// A method call (`recv.name(...)`): the callee is resolved without knowing the receiver's
    /// type, so it can only ever be matched by name.
    method: bool,
    /// Found by scanning the tokens of a macro invocation rather than by parsing a call.
    in_macro: bool,
    /// For `T::name(..)` where `T` is a generic parameter: the traits `T` is bounded by.
    bounds: Vec<String>,
    /// For `self.name(..)`, `this.name(..)` and `Self::name(..)`: the type whose method it is,
    /// when the surrounding `impl` or class names one.
    receiver_type: Option<String>,
    /// A call of a bare name that is bound inside an enclosing function (`let f = ..; f()`,
    /// a parameter, a nested `const`): the callee is that binding, so only a declaration in
    /// this file can be it, never a same-named symbol elsewhere.
    local: bool,
}

struct ReferenceVisitor<'a> {
    source: &'a str,
    candidates: Vec<CandidateReference>,
    /// Names bound anywhere inside each enclosing function (parameters, `let`, assignment
    /// targets), innermost last. A name in here is a local, not a function, whatever it is
    /// called.
    locals: Vec<HashSet<String>>,
    /// Trait bounds of the generic parameters in scope (`T: Tr`, `where U: Tr`), innermost last.
    generics: Vec<HashMap<String, Vec<String>>>,
    /// The type of `self`: the `impl` target or class being visited, innermost last (`None`
    /// where it is unknown, such as a trait's default methods).
    types: Vec<Option<String>>,
}

impl<'a> ReferenceVisitor<'a> {
    fn text(&self, node: Node) -> &'a str {
        &self.source[node.start_byte()..node.end_byte()]
    }

    /// Visit what a callee expression contains besides the name being called: the receiver of
    /// a method call (`value` in Rust, `object` in Python and TypeScript) and anything wrapped
    /// around the callee. Plain names have nothing more to visit.
    fn traverse_callee(&mut self, func: Node, current_enclosing: Option<&str>) {
        match func.kind() {
            "identifier" | "scoped_identifier" | "field_identifier" | "type_identifier" => {}
            "field_expression" | "attribute" | "member_expression" => {
                if let Some(receiver) = func
                    .child_by_field_name("value")
                    .or_else(|| func.child_by_field_name("object"))
                {
                    self.traverse(receiver, current_enclosing);
                }
            }
            // `f::<T>()`: the callee is wrapped, and may itself be a method call.
            "generic_function" => {
                if let Some(inner) = func.child_by_field_name("function") {
                    self.traverse_callee(inner, current_enclosing);
                }
            }
            _ => self.traverse(func, current_enclosing),
        }
    }

    /// Visit what a parameter list contains besides the parameter names: the types
    /// (`opts: &UpdateOptions<'_>`) and default values (`def f(x=target())`). The names
    /// themselves are bindings, not references.
    fn traverse_parameters(&mut self, params: Node, current_enclosing: Option<&str>) {
        let mut cursor = params.walk();
        for param in params.children(&mut cursor) {
            match param.kind() {
                // Rust, TypeScript: the annotation (and a TypeScript default value).
                "parameter" | "required_parameter" | "optional_parameter" => {
                    for field in ["type", "value"] {
                        if let Some(child) = param.child_by_field_name(field) {
                            self.traverse(child, current_enclosing);
                        }
                    }
                }
                // Python: the default value.
                "default_parameter" | "typed_default_parameter" => {
                    if let Some(value) = param.child_by_field_name("value") {
                        self.traverse(value, current_enclosing);
                    }
                }
                _ => {}
            }
        }
    }

    /// The path text of a scoped callee. `<T as Trait>::name` is `Trait::name` (the trait is
    /// what the call names; `T` is only the receiver); other paths lose their generic arguments.
    fn call_path(&self, func: Node) -> String {
        let qualified = func
            .child_by_field_name("path")
            .filter(|p| p.kind() == "bracketed_type")
            .and_then(|p| p.named_child(0))
            .filter(|q| q.kind() == "qualified_type")
            .and_then(|q| q.child_by_field_name("alias"));
        match (qualified, func.child_by_field_name("name")) {
            (Some(alias), Some(name)) => {
                format!("{}::{}", strip_generics(self.text(alias)), self.text(name))
            }
            _ => strip_generics(self.text(func)),
        }
    }

    /// Traits the generic parameter `name` is bounded by, if it is one in scope.
    fn bounds_of(&self, name: &str) -> Option<Vec<String>> {
        self.generics
            .iter()
            .rev()
            .find_map(|scope| scope.get(name).cloned())
    }

    /// Record the calls written inside a macro's token tree. Tokens are flat, so a call is an
    /// identifier directly followed by a parenthesised token tree; the `a::b::` run before it
    /// is its path and a `.` before it makes it a method call. Nested token trees are
    /// scanned too (`assert_eq!(f(g(1)), 2)`), and a name after `fn` is a definition.
    fn scan_token_tree(&mut self, tree: Node, current_enclosing: Option<&str>) {
        let mut cursor = tree.walk();
        let tokens: Vec<Node> = tree.children(&mut cursor).collect();
        for (i, token) in tokens.iter().enumerate() {
            match token.kind() {
                "token_tree" => self.scan_token_tree(*token, current_enclosing),
                "identifier" => {
                    let called = tokens.get(i + 1).is_some_and(|next| {
                        next.kind() == "token_tree"
                            && next.child(0).is_some_and(|open| open.kind() == "(")
                    });
                    let defined = i > 0 && tokens[i - 1].kind() == "fn";
                    if !called || defined {
                        continue;
                    }
                    let method = i > 0 && tokens[i - 1].kind() == ".";
                    // Walk back over `ident ::` pairs to the start of the path.
                    let mut first = i;
                    while first >= 2
                        && tokens[first - 1].kind() == "::"
                        && matches!(
                            tokens[first - 2].kind(),
                            "identifier" | "self" | "crate" | "super"
                        )
                    {
                        first -= 2;
                    }
                    let path = (!method && first < i).then(|| {
                        strip_generics(&self.source[tokens[first].start_byte()..token.end_byte()])
                    });
                    self.candidates.push(CandidateReference {
                        identifier: self.text(*token).to_string(),
                        path,
                        role: "call".to_string(),
                        start_byte: token.start_byte(),
                        end_byte: token.end_byte(),
                        line_number: (token.start_position().row + 1) as u32,
                        col_number: token.start_position().column as u32,
                        enclosing_symbol: current_enclosing.map(|s| s.to_string()),
                        method,
                        in_macro: true,
                        bounds: Vec::new(),
                        receiver_type: None,
                        local: false,
                    });
                }
                _ => {}
            }
        }
    }

    fn traverse(&mut self, node: Node, current_enclosing: Option<&str>) {
        match node.kind() {
            "impl_item" | "trait_item" => {
                self.generics
                    .push(collect_generic_bounds(node, self.source));
                // `impl Tr for Type` and `impl Type` are both about `Type`; a trait's own
                // default methods do not know their `Self`.
                let self_type = (node.kind() == "impl_item")
                    .then(|| node.child_by_field_name("type"))
                    .flatten()
                    .and_then(|t| type_name(t, self.source));
                self.types.push(self_type);
                let mut cursor = node.walk();
                for child in node.children(&mut cursor) {
                    self.traverse(child, current_enclosing);
                }
                self.types.pop();
                self.generics.pop();
            }

            // A class (Python `class`, TypeScript `class`): `self`/`this` is that class.
            "class_definition" | "class_declaration" | "abstract_class_declaration" | "class" => {
                let name = node
                    .child_by_field_name("name")
                    .map(|n| self.text(n).to_string());
                self.types.push(name);
                let mut cursor = node.walk();
                for child in node.children(&mut cursor) {
                    self.traverse(child, current_enclosing);
                }
                self.types.pop();
            }

            "function_item"
            | "function_definition"
            | "function_declaration"
            | "method_definition" => {
                let name = node
                    .child_by_field_name("name")
                    .map(|n| self.text(n))
                    .unwrap_or("anonymous_fn");

                self.locals.push(collect_bindings(node, self.source));
                self.generics
                    .push(collect_generic_bounds(node, self.source));
                let mut cursor = node.walk();
                for child in node.children(&mut cursor) {
                    match child.kind() {
                        "visibility_modifier" => {}
                        // Parameter names are not references, but their types and default
                        // values are: `fn f(x: &Opts)`, `def f(x=target())`.
                        "parameters" | "formal_parameters" => {
                            self.traverse_parameters(child, Some(name))
                        }
                        _ => self.traverse(child, Some(name)),
                    }
                }
                self.locals.pop();
                self.generics.pop();
            }

            // A name used as a value (`let f = target;`, `register(target)`, `return target`).
            // Kept only if it is not a local and, in the resolver, names a function.
            "identifier"
                if is_value_position(node)
                    && !self.locals.iter().any(|l| l.contains(self.text(node)))
                    && !in_parse_error(node) =>
            {
                self.candidates.push(CandidateReference {
                    identifier: self.text(node).to_string(),
                    path: None,
                    role: "value".to_string(),
                    start_byte: node.start_byte(),
                    end_byte: node.end_byte(),
                    line_number: (node.start_position().row + 1) as u32,
                    col_number: node.start_position().column as u32,
                    enclosing_symbol: current_enclosing.map(|s| s.to_string()),
                    method: false,
                    in_macro: false,
                    bounds: Vec::new(),
                    receiver_type: None,
                    local: false,
                });
            }

            "call_expression" | "call" => {
                if let Some(func) = node.child_by_field_name("function") {
                    // `f::<T>()` wraps the callee in a generic_function node.
                    let func = if func.kind() == "generic_function" {
                        func.child_by_field_name("function").unwrap_or(func)
                    } else {
                        func
                    };
                    let self_type = self.types.last().cloned().flatten();
                    let on_self = match func.kind() {
                        "field_expression" => func
                            .child_by_field_name("value")
                            .is_some_and(|v| v.kind() == "self"),
                        "attribute" => func
                            .child_by_field_name("object")
                            .is_some_and(|o| matches!(self.text(o), "self" | "cls")),
                        "member_expression" => func
                            .child_by_field_name("object")
                            .is_some_and(|o| o.kind() == "this"),
                        _ => false,
                    };
                    let mut path =
                        (func.kind() == "scoped_identifier").then(|| self.call_path(func));
                    // `Self::name(..)` names the impl's own type.
                    if let (Some(p), Some(ty)) = (&mut path, &self_type)
                        && let Some(rest) = p.strip_prefix("Self::")
                    {
                        *p = format!("{ty}::{rest}");
                    }
                    let receiver_type = if on_self { self_type } else { None };
                    // `T::name(..)` with `T` a generic parameter resolves through its bounds.
                    let bounds = match (&path, func.kind()) {
                        (Some(path), "scoped_identifier") => path
                            .split_once("::")
                            .filter(|(_, rest)| !rest.contains("::"))
                            .and_then(|(first, _)| self.bounds_of(first))
                            .unwrap_or_default(),
                        _ => Vec::new(),
                    };
                    let ident_info = match func.kind() {
                        "identifier" => Some((
                            self.text(func).to_string(),
                            func.start_byte(),
                            func.end_byte(),
                            (func.start_position().row + 1) as u32,
                            func.start_position().column as u32,
                        )),
                        "scoped_identifier" => func.child_by_field_name("name").map(|n| {
                            (
                                self.text(n).to_string(),
                                n.start_byte(),
                                n.end_byte(),
                                (n.start_position().row + 1) as u32,
                                n.start_position().column as u32,
                            )
                        }),
                        "field_expression" => func.child_by_field_name("field").map(|n| {
                            (
                                self.text(n).to_string(),
                                n.start_byte(),
                                n.end_byte(),
                                (n.start_position().row + 1) as u32,
                                n.start_position().column as u32,
                            )
                        }),
                        "attribute" => func.child_by_field_name("attribute").map(|n| {
                            (
                                self.text(n).to_string(),
                                n.start_byte(),
                                n.end_byte(),
                                (n.start_position().row + 1) as u32,
                                n.start_position().column as u32,
                            )
                        }),
                        "member_expression" => func.child_by_field_name("property").map(|n| {
                            (
                                self.text(n).to_string(),
                                n.start_byte(),
                                n.end_byte(),
                                (n.start_position().row + 1) as u32,
                                n.start_position().column as u32,
                            )
                        }),
                        _ => None,
                    };

                    let method = matches!(
                        func.kind(),
                        "field_expression" | "attribute" | "member_expression"
                    );
                    if let Some((id, sb, eb, ln, col)) = ident_info {
                        let local = func.kind() == "identifier"
                            && self.locals.iter().any(|l| l.contains(&id));
                        self.candidates.push(CandidateReference {
                            identifier: id,
                            path,
                            role: "call".to_string(),
                            start_byte: sb,
                            end_byte: eb,
                            line_number: ln,
                            col_number: col,
                            enclosing_symbol: current_enclosing.map(|s| s.to_string()),
                            method,
                            in_macro: false,
                            bounds,
                            receiver_type,
                            local,
                        });
                    }
                }

                if let Some(args) = node
                    .child_by_field_name("arguments")
                    .or_else(|| node.child_by_field_name("argument_list"))
                {
                    let mut cursor = args.walk();
                    for child in args.children(&mut cursor) {
                        self.traverse(child, current_enclosing);
                    }
                }

                // The callee's own name was recorded above, but calls earlier in a chain
                // (`a().b().c()`: `a` and `b`) sit in its receiver, so walk that too.
                if let Some(func) = node.child_by_field_name("function") {
                    self.traverse_callee(func, current_enclosing);
                }
            }

            // Macro arguments are an opaque token tree, so no `call_expression` exists inside.
            // Scan the tokens for `name(...)`, `a::b(...)` and `.name(...)` instead.
            "macro_invocation" => {
                let mut cursor = node.walk();
                for child in node.children(&mut cursor) {
                    if child.kind() == "token_tree" {
                        self.scan_token_tree(child, current_enclosing);
                    }
                }
            }

            "type_identifier" => {
                // Ensure this is not a declaration name
                let is_decl = node.parent().is_some_and(|p| {
                    (p.kind() == "struct_item"
                        || p.kind() == "enum_item"
                        || p.kind() == "trait_item"
                        || p.kind() == "type_item")
                        && p.child_by_field_name("name") == Some(node)
                });

                if !is_decl {
                    let path = node
                        .parent()
                        .filter(|p| p.kind() == "scoped_type_identifier")
                        .map(|p| strip_generics(self.text(p)));
                    self.candidates.push(CandidateReference {
                        identifier: self.text(node).to_string(),
                        path,
                        role: "type_annotation".to_string(),
                        start_byte: node.start_byte(),
                        end_byte: node.end_byte(),
                        line_number: (node.start_position().row + 1) as u32,
                        col_number: node.start_position().column as u32,
                        enclosing_symbol: current_enclosing.map(|s| s.to_string()),
                        method: false,
                        in_macro: false,
                        bounds: Vec::new(),
                        receiver_type: None,
                        local: false,
                    });
                }
            }

            "use_declaration" => {
                let is_pub = node
                    .children(&mut node.walk())
                    .any(|c| c.kind() == "visibility_modifier" && self.text(c).trim() == "pub");
                let role = if is_pub { "reexport" } else { "import" };

                let items = crate::parsers::extract_use_items(self.source, node);
                for item in items {
                    self.candidates.push(CandidateReference {
                        identifier: item.local_name,
                        path: Some(item.target_path),
                        role: role.to_string(),
                        start_byte: item.start_byte,
                        end_byte: item.end_byte,
                        line_number: item.start_line,
                        col_number: item.col_number,
                        enclosing_symbol: current_enclosing.map(|s| s.to_string()),
                        method: false,
                        in_macro: false,
                        bounds: Vec::new(),
                        receiver_type: None,
                        local: false,
                    });
                }
            }

            _ => {
                let mut cursor = node.walk();
                for child in node.children(&mut cursor) {
                    self.traverse(child, current_enclosing);
                }
            }
        }
    }
}

/// Whether an `identifier` node sits where a value is expected, so that naming a function
/// there passes the function itself: the right side of an assignment or `let`, an argument,
/// a returned or collected value, an initializer, or a decorator.
fn is_value_position(node: Node) -> bool {
    let Some(parent) = node.parent() else {
        return false;
    };
    let is_field = |field: &str| parent.child_by_field_name(field) == Some(node);
    match parent.kind() {
        "let_declaration" | "const_item" | "static_item" | "variable_declarator" => {
            is_field("value")
        }
        "assignment_expression" | "assignment" | "augmented_assignment" => is_field("right"),
        "field_initializer" | "pair" | "keyword_argument" | "reference_expression" => {
            is_field("value")
        }
        "arguments"
        | "argument_list"
        | "return_expression"
        | "return_statement"
        | "array_expression"
        | "array"
        | "tuple_expression"
        | "tuple"
        | "list"
        | "set"
        | "expression_list"
        | "shorthand_field_initializer"
        | "decorator" => true,
        _ => false,
    }
}

/// The name of a type as written in `impl ... for <type>`: `Foo`, `Foo<T>` and `a::Foo` are
/// `Foo`. `None` for types with no name of their own (references, tuples, ...).
fn type_name(node: Node, source: &str) -> Option<String> {
    match node.kind() {
        "type_identifier" => Some(source[node.start_byte()..node.end_byte()].to_string()),
        "generic_type" => type_name(node.child_by_field_name("type")?, source),
        "scoped_type_identifier" => type_name(node.child_by_field_name("name")?, source),
        _ => None,
    }
}

/// Trait bounds of the generic parameters declared on an item, from `<T: Tr + Other>` and
/// `where T: Tr`: parameter name to the bound traits' names (without generic arguments).
fn collect_generic_bounds(item: Node, source: &str) -> HashMap<String, Vec<String>> {
    let mut bounds: HashMap<String, Vec<String>> = HashMap::new();
    let text = |n: Node| source[n.start_byte()..n.end_byte()].to_string();
    let mut add = |name: Node, list: Option<Node>| {
        let entry = bounds.entry(text(name)).or_default();
        let Some(list) = list else { return };
        let mut cursor = list.walk();
        for bound in list.named_children(&mut cursor) {
            if matches!(
                bound.kind(),
                "type_identifier" | "scoped_type_identifier" | "generic_type"
            ) {
                entry.push(strip_generics(&text(bound)));
            }
        }
    };
    if let Some(params) = item.child_by_field_name("type_parameters") {
        let mut cursor = params.walk();
        for param in params.named_children(&mut cursor) {
            if param.kind() == "type_parameter"
                && let Some(name) = param.child_by_field_name("name")
            {
                add(name, param.child_by_field_name("bounds"));
            }
        }
    }
    let mut cursor = item.walk();
    for child in item.children(&mut cursor) {
        if child.kind() != "where_clause" {
            continue;
        }
        let mut inner = child.walk();
        for predicate in child.named_children(&mut inner) {
            if predicate.kind() == "where_predicate"
                && let Some(left) = predicate.child_by_field_name("left")
                && left.kind() == "type_identifier"
            {
                add(left, predicate.child_by_field_name("bounds"));
            }
        }
    }
    bounds
}

/// Whether `node` sits inside text tree-sitter could not parse (an `ERROR` node), where
/// identifiers are not reliably names.
fn in_parse_error(node: Node) -> bool {
    let mut current = node.parent();
    while let Some(parent) = current {
        if parent.kind() == "ERROR" {
            return true;
        }
        current = parent.parent();
    }
    false
}

/// Every `identifier` in the subtree of `node`.
fn identifiers_in<'a>(node: Node<'a>, out: &mut Vec<Node<'a>>) {
    // `Point { x, y }` patterns bind through `shorthand_field_identifier`; TypeScript
    // destructuring (`{ x }`) through `shorthand_property_identifier_pattern`.
    if matches!(
        node.kind(),
        "identifier" | "shorthand_field_identifier" | "shorthand_property_identifier_pattern"
    ) {
        out.push(node);
        return;
    }
    let mut cursor = node.walk();
    for child in node.children(&mut cursor) {
        identifiers_in(child, out);
    }
}

/// Names bound anywhere inside the function `function`: its parameters, `let` and `for`
/// patterns, closure parameters, and assignment and declaration targets. Scope-insensitive on
/// purpose: a name bound anywhere in the function is never treated as a reference to a
/// function of the same name.
fn collect_bindings(function: Node, source: &str) -> HashSet<String> {
    let mut bound: Vec<Node> = Vec::new();
    let mut stack = vec![function];
    while let Some(node) = stack.pop() {
        let kind = node.kind();
        // Rust and TypeScript parameters, `let`, `for`, `match` arms: all use a `pattern` field.
        if let Some(pattern) = node.child_by_field_name("pattern") {
            identifiers_in(pattern, &mut bound);
        }
        match kind {
            "closure_parameters" | "lambda_parameters" => identifiers_in(node, &mut bound),
            // Python parameters: bind the name, not a default value.
            "parameters" => {
                let mut cursor = node.walk();
                for param in node.children(&mut cursor) {
                    match param.kind() {
                        "identifier" => bound.push(param),
                        "default_parameter" | "typed_default_parameter" => {
                            if let Some(name) = param.child_by_field_name("name") {
                                identifiers_in(name, &mut bound);
                            }
                        }
                        "typed_parameter" | "list_splat_pattern" | "dictionary_splat_pattern" => {
                            if let Some(first) = param.named_child(0) {
                                identifiers_in(first, &mut bound);
                            }
                        }
                        _ => {}
                    }
                }
            }
            "assignment" | "for_statement" | "for_in_clause" | "augmented_assignment" => {
                if let Some(left) = node.child_by_field_name("left") {
                    identifiers_in(left, &mut bound);
                }
            }
            "variable_declarator" | "named_expression" => {
                if let Some(name) = node.child_by_field_name("name") {
                    identifiers_in(name, &mut bound);
                }
            }
            _ => {}
        }
        let mut cursor = node.walk();
        stack.extend(node.children(&mut cursor));
    }
    bound
        .into_iter()
        .map(|n| source[n.start_byte()..n.end_byte()].to_string())
        .collect()
}

/// Remove generic arguments (`Vec::<u8>::new` → `Vec::new`) and whitespace from a path.
fn strip_generics(path: &str) -> String {
    let mut out = String::with_capacity(path.len());
    let mut depth = 0usize;
    for c in path.chars() {
        match c {
            '<' => depth += 1,
            '>' => depth = depth.saturating_sub(1),
            c if depth == 0 && !c.is_whitespace() => out.push(c),
            _ => {}
        }
    }
    out.replace("::::", "::").trim_end_matches("::").to_string()
}

/// Rewrite a Rust path relative to the file that contains it: `crate::` becomes the
/// file's crate root and `self::`/`super::` are resolved against its module path.
/// `Self::f` collapses to the bare `f`. Returns `None` for paths it can't use.
pub fn normalize_rust_path(path: &str, rel_path: &Path) -> Option<String> {
    let segments: Vec<&str> = path
        .trim_start_matches("::")
        .split("::")
        .filter(|s| !s.is_empty())
        .collect();
    let (&first, rest) = segments.split_first()?;
    if rest.is_empty() {
        return Some(first.to_string());
    }

    let mut base: Vec<String> = match first {
        "crate" => vec![crate_root_for(rel_path)],
        "self" | "super" => module_path_for(rel_path)
            .split("::")
            .map(str::to_string)
            .collect(),
        "Self" => return rest.last().map(|s| s.to_string()),
        _ => return Some(segments.join("::")),
    };

    let mut rest = rest;
    if first == "super" {
        base.pop();
    }
    while let Some((&"super", tail)) = rest.split_first() {
        base.pop();
        rest = tail;
    }
    base.extend(rest.iter().map(|s| s.to_string()));
    Some(base.join("::"))
}

/// The function or class named `name` that is declared inside a function containing `byte`:
/// the nearest one, so a nested `def` or arrow function a call refers to.
fn nested_declaration<'a>(
    symbols: &'a [RawSymbol],
    name: &str,
    byte: usize,
) -> Option<&'a RawSymbol> {
    symbols
        .iter()
        .filter(|s| s.name == name && matches!(s.kind.as_str(), "fn" | "class"))
        .filter(|s| {
            symbols.iter().any(|f| {
                matches!(f.kind.as_str(), "fn" | "method")
                    && f.start_byte <= byte
                    && byte < f.end_byte
                    && f.start_byte <= s.start_byte
                    && s.end_byte <= f.end_byte
                    && (f.start_byte, f.end_byte) != (s.start_byte, s.end_byte)
            })
        })
        .max_by_key(|s| s.start_byte)
}

/// Qualified name of the innermost symbol that holds code containing `byte`: a function or
/// method, else the `const`, variable or class whose initializer or body it is (a class
/// attribute, a property initializer, `const X: T = f();`, a script's `result = f()`).
fn enclosing_function(symbols: &[RawSymbol], byte: usize) -> Option<String> {
    symbols
        .iter()
        .filter(|s| {
            matches!(s.kind.as_str(), "fn" | "method" | "const" | "var" | "class")
                && s.start_byte <= byte
                && byte < s.end_byte
        })
        .min_by_key(|s| s.end_byte - s.start_byte)
        .map(|s| s.qualified_name.clone())
}

/// Identify the symbol named at `(line, col)` (1-based line, 0-based column) in a source
/// file and return a lookup target for it: a normalized path for path-qualified Rust
/// references, or the bare identifier otherwise. Returns `None` if the cursor is not on
/// an identifier.
pub fn reference_target_at(rel_path: &Path, content: &str, line: u32, col: u32) -> Option<String> {
    let language = tree_sitter_language_for(rel_path)?;
    let mut parser = Parser::new();
    parser.set_language(&language).ok()?;
    let tree = parser.parse(prepared_source(rel_path, content).as_bytes(), None)?;

    let point = tree_sitter::Point::new(line.checked_sub(1)? as usize, col as usize);
    let node = tree
        .root_node()
        .named_descendant_for_point_range(point, point)?;
    if !node.kind().ends_with("identifier") {
        return None;
    }
    let text = |n: Node| &content[n.start_byte()..n.end_byte()];

    let is_rust = !matches!(
        rel_path.extension().and_then(|e| e.to_str()),
        Some("py" | "ts" | "tsx" | "js" | "jsx")
    );
    if is_rust {
        let scoped_parent = node.parent().filter(|p| {
            matches!(p.kind(), "scoped_identifier" | "scoped_type_identifier")
                && p.child_by_field_name("name") == Some(node)
        });
        if let Some(parent) = scoped_parent {
            return normalize_rust_path(&strip_generics(text(parent)), rel_path);
        }
    }
    Some(text(node).to_string())
}