brokk_bifrost_python/graph/

inverted.rs

//! Whole-workspace inverted edge builder for Python.
//!
//! Walks each file once and resolves every reference to the callee fqn it names,
//! via the shared [`build_edges`] driver. Python node fqns are dotted module
//! paths (`pkg.util.format_value`, `app.helper`), so a reference resolves through
//! the file's import binder:
//!
//! - a `from pkg.util import f` binding resolves a bare `f` to `pkg.util.f`;
//! - an `import pkg.util as u` binding resolves `u.f` to `pkg.util.f`;
//! - a same-file/same-module name resolves to that declaration's fqn.
//!
//! Parameters and local assignments shadow same-named imports and module-level
//! declarations (Python scopes are function-wide), matching the forward scan's
//! shadow handling so a local named like an import does not produce a false edge.
//! A typed receiver — a `recv: Foo` parameter or a `recv = Foo()` local —
//! resolves `recv.method` to `Foo.method` via the forward scan's shared receiver
//! typing ([`collect_scope_facts`] + [`resolve_receiver_type`]).

use super::extractor::{
    call_result_types, collect_assigned_identifiers, collect_function_scope_facts_from_node,
    collect_scope_facts_from_parsed_source, enclosing_scope_facts, is_declaration_identifier,
    slice,
};
use super::resolver::{
    annotation_reference_candidates, resolve_callable_parameter_default_types,
    resolve_constructor_types, resolve_receiver_type, resolve_visible_named_import_candidates,
    resolved_member_declarations,
};
use crate::bindings::{python_comprehension_binds_name_at, python_type_parameter_binds_name_at};
use crate::graph::PythonGraphSource;
use crate::graph_support::PythonUsageSource;
use crate::imports::{imported_module_assignment_at, resolve_fqn_candidates};
use crate::syntax::{
    attribute_chain, leftmost_identifier, python_reference_is_deferred_function_body,
};
use crate::usage_index::{
    ModuleBindingEventKind, ModuleBindingTimeline, usage_module_binding_timeline,
    usage_resolve_module_files, usage_scope_facts,
};
use brokk_bifrost_core::analyzer::symbol_path::parse_symbol_path;
use brokk_bifrost_core::analyzer::usages::inverted_edges::{
    FileEdgeScanInput, PerFileEdges, UsageReferenceKind, classify_reference_node,
};
use brokk_bifrost_core::analyzer::usages::local_inference::LocalBindingsSnapshot;
use brokk_bifrost_core::analyzer::usages::model::ImportKind;
use brokk_bifrost_core::analyzer::{CodeUnit, Language, ProjectFile, Range};
use brokk_bifrost_core::cancellation::CancellationToken;
use brokk_bifrost_core::hash::{HashMap, HashSet};
use std::sync::{Arc, Mutex};
use tree_sitter::Node;

/// The whole-pass state the per-file walk shares: the terminal-segment index
/// over `targets`, and the namespace-candidate memo the walk fills as it goes.
///
/// Built once per inverted pass and then borrowed by every worker, so
/// `brokk-bifrost-analysis`'s fan-out (`build_edge_output` + `parse_and_collect`,
/// both analysis-owned) can hold it across the parallel closure.
pub struct PythonEdgeScan<'a> {
    targets: Option<&'a HashSet<String>>,
    targets_by_terminal: HashMap<String, Vec<String>>,
    canonical_namespace_candidates: Mutex<HashMap<String, Arc<Vec<String>>>>,
}

impl<'a> PythonEdgeScan<'a> {
    /// `nodes` remains the complete caller/callee graph domain. `targets` is the
    /// subset whose inbound references this build must resolve and retain.
    pub fn new(nodes: &HashSet<String>, targets: &'a HashSet<String>) -> Self {
        debug_assert!(targets.is_subset(nodes));
        let mut targets_by_terminal: HashMap<String, Vec<String>> = HashMap::default();
        for target in targets {
            // Python fqns are dotted module paths with no other delimiter (per the
            // module doc comment above), so re-tokenizing with the shared structured
            // splitter and taking the terminal segment reproduces
            // `rsplit('.').next()`'s terminal split exactly.
            let terminal = parse_symbol_path(Language::Python, target)
                .pop()
                .unwrap_or_else(|| target.clone());
            targets_by_terminal
                .entry(terminal)
                .or_default()
                .push(target.clone());
        }
        Self {
            targets: Some(targets),
            targets_by_terminal,
            canonical_namespace_candidates: Mutex::new(HashMap::default()),
        }
    }

    /// Build a rooted scan without pre-enumerating its callee universe.
    /// Exact targets are checked against the bounded definition index as they
    /// are resolved, and the analysis layer validates graph-node eligibility.
    pub fn new_rooted() -> Self {
        Self {
            targets: None,
            targets_by_terminal: HashMap::default(),
            canonical_namespace_candidates: Mutex::new(HashMap::default()),
        }
    }

    /// Resolve every reference in one already-parsed file.
    ///
    /// Reaches no other file's tree: the import binder, same-file declarations,
    /// and the receiver-type facts are all derived from this file plus the
    /// analyzer's own (tree-free) caches.
    pub fn scan_file(
        &self,
        graph: &PythonGraphSource<'_>,
        python: &dyn PythonUsageSource,
        file: &ProjectFile,
        input: &FileEdgeScanInput<'_>,
        cancellation: &CancellationToken,
    ) -> Result<PerFileEdges, ProjectFile> {
        let source = input.source;
        let canonical_imports = python.import_info_of(graph.token, file);

        // Per-file resolution context from the import binder. A namespace
        // binding's module_specifier is either the full fqn (for
        // `from m import f`) or the module prefix (for `import m as u`); the
        // node-membership check downstream disambiguates which applies.
        let binder = python.import_binder_of(file);
        let mut named: HashMap<String, String> = HashMap::default();
        let mut namespace: HashMap<String, NamespaceBinding> = HashMap::default();
        for (local, binding) in &binder.bindings {
            if cancellation.is_cancelled() {
                return Err(file.clone());
            }
            match binding.kind {
                ImportKind::Named => {
                    if let Some(imported) = &binding.imported_name {
                        let module = canonical_import_module_fqn(
                            graph,
                            python,
                            file,
                            &binding.module_specifier,
                        )
                        .unwrap_or_else(|| binding.module_specifier.clone());
                        let imported_fqn = if module.ends_with('.') {
                            format!("{module}{imported}")
                        } else {
                            format!("{module}.{imported}")
                        };
                        // The binder has already resolved a `from` import's
                        // package attribute before falling back to a same-named
                        // child module. Reinterpreting a named export as a
                        // namespace here would undo that decision (#3390).
                        named.insert(local.clone(), imported_fqn);
                    }
                }
                ImportKind::Namespace => {
                    let direct_module = binding.module_specifier.clone();
                    let imported_module = binding
                        .namespace_imported_module
                        .as_deref()
                        .unwrap_or(&direct_module);
                    let module = canonical_import_module_fqn(graph, python, file, imported_module);
                    let workspace_module = module.is_some();
                    let consumed_attributes = module.as_ref().map_or(0, |_| {
                        let imported_segments =
                            parse_symbol_path(Language::Python, imported_module);
                        let bound_segments = parse_symbol_path(Language::Python, &direct_module);
                        imported_segments.len().saturating_sub(bound_segments.len())
                    });
                    let canonical_module = module.unwrap_or(direct_module);
                    let mut root_segments = parse_symbol_path(Language::Python, &canonical_module);
                    root_segments.truncate(root_segments.len().saturating_sub(consumed_attributes));
                    namespace.insert(
                        local.clone(),
                        NamespaceBinding {
                            root_module: root_segments.join("."),
                            module: canonical_module,
                            workspace_module,
                            consumed_attributes,
                        },
                    );
                }
                ImportKind::Default | ImportKind::CommonJsRequire | ImportKind::Glob => {}
            }
        }
        let same_file: HashMap<String, String> = graph
            .index
            .declarations(file)
            .into_iter()
            .map(|unit| (unit.identifier().to_string(), unit.fq_name()))
            .collect();
        let module_bindings = usage_module_binding_timeline(python, file, || {
            super::extractor::collect_module_binding_timeline(
                input.root(),
                source,
                &canonical_imports,
            )
        });

        // Per-function receiver-type facts (typed params + `x = Foo()`),
        // computed by the same routine the forward scan uses, so a typed
        // `recv.method` resolves to the receiver's class fqn.
        let Some(scope_facts) = usage_scope_facts(python, file, || {
            collect_scope_facts_from_parsed_source(graph, python, file, source, input.root())
        }) else {
            return Err(file.clone());
        };

        let mut ctx = PyScan {
            cancellation,
            graph,
            python,
            targets: self.targets,
            targets_by_terminal: &self.targets_by_terminal,
            file,
            source,
            named,
            namespace,
            same_file,
            module_bindings,
            scope_facts: scope_facts.as_ref(),
            canonical_namespace_candidates: &self.canonical_namespace_candidates,
            input,
            edges: PerFileEdges::default(),
            pending: Vec::new(),
        };
        scan_tree(input.root(), &mut ctx);
        ctx.resolve_pending();
        if cancellation.is_cancelled() {
            return Err(file.clone());
        }
        Ok(ctx.edges)
    }
}

fn reference_span(node: Node<'_>) -> (UsageReferenceKind, usize, usize) {
    (
        classify_reference_node(node),
        node.start_byte(),
        node.end_byte(),
    )
}

fn canonical_import_module_fqn(
    graph: &PythonGraphSource<'_>,
    python: &dyn PythonUsageSource,
    importing_file: &ProjectFile,
    module_specifier: &str,
) -> Option<String> {
    let resolved = usage_resolve_module_files(python, importing_file, module_specifier);
    let [module_file] = resolved.as_slice() else {
        return None;
    };
    graph
        .index
        .declarations(module_file)
        .into_iter()
        .find(CodeUnit::is_module)
        .map(|module| module.fq_name())
}

struct PyScan<'a> {
    cancellation: &'a CancellationToken,
    graph: &'a PythonGraphSource<'a>,
    python: &'a dyn PythonUsageSource,
    targets: Option<&'a HashSet<String>>,
    targets_by_terminal: &'a HashMap<String, Vec<String>>,
    file: &'a ProjectFile,
    source: &'a str,
    named: HashMap<String, String>,
    namespace: HashMap<String, NamespaceBinding>,
    same_file: HashMap<String, String>,
    module_bindings: Arc<ModuleBindingTimeline>,
    scope_facts: &'a HashMap<CodeUnit, LocalBindingsSnapshot<String>>,
    canonical_namespace_candidates: &'a Mutex<HashMap<String, Arc<Vec<String>>>>,
    input: &'a FileEdgeScanInput<'a>,
    edges: PerFileEdges,
    /// Rooted-mode existence checks deferred until [`PyScan::resolve_pending`] runs
    /// them as one batch instead of one live store round trip per reference. Empty
    /// and unused in bounded (`targets: Some`) mode, where membership is already a
    /// local hash check.
    pending: Vec<PendingCallee>,
}

/// One reference site's deferred existence check, resolved in [`PyScan::resolve_pending`]
/// after a single [`PythonSource::prefetch_definitions`] batch has warmed every candidate
/// name below. Each variant mirrors the immediate-check logic its call site used to run
/// inline; deferring only changes when the check runs, not what it decides.
enum PendingCallee {
    /// Record `callee` if it has a definition.
    Direct {
        callee: String,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    },
    /// Record `direct` if it has a definition; otherwise expand it into every
    /// workspace candidate `canonical_namespace_candidates` finds.
    WithNamespaceFallback {
        direct: String,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    },
    /// Record `direct` if it has a definition; otherwise record every fqn in
    /// `inherited` that does.
    WithAncestorFallback {
        direct: String,
        inherited: Vec<String>,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    },
}

struct NamespaceBinding {
    root_module: String,
    module: String,
    workspace_module: bool,
    consumed_attributes: usize,
}

impl PyScan<'_> {
    /// The callee fqn a bare name refers to: a named import, a namespace import of
    /// a symbol (module_specifier is the full fqn), or a same-file declaration.
    fn bare_callee(&self, text: &str, node: Node<'_>) -> Option<String> {
        if let Some(fqn) = self.named.get(text) {
            return Some(fqn.clone());
        }
        if let Some(fqn) = self.namespace.get(text) {
            return self
                .visible_namespace_root(text, node)
                .or_else(|| Some(fqn.root_module.clone()));
        }
        if let Some(fqn) = self.same_file.get(text) {
            return Some(fqn.clone());
        }
        None
    }

    fn visible_namespace_root(&self, local: &str, node: Node<'_>) -> Option<String> {
        let events = self.module_bindings.get(local)?;
        let cutoff = if python_reference_is_deferred_function_body(node) {
            usize::MAX
        } else {
            node.start_byte()
        };
        let visible: Vec<_> = events
            .iter()
            .filter(|event| event.visible_from <= cutoff)
            .collect();
        let start = visible
            .iter()
            .rposition(|event| {
                if event.conditional {
                    return false;
                }
                match &event.kind {
                    ModuleBindingEventKind::ImportModule {
                        module,
                        consumed_attributes,
                    } => *consumed_attributes == 0 && module != local,
                    ModuleBindingEventKind::FromImport { .. } | ModuleBindingEventKind::Other => {
                        true
                    }
                }
            })
            .unwrap_or(0);
        let mut roots = visible[start..]
            .iter()
            .filter_map(|event| match &event.kind {
                ModuleBindingEventKind::ImportModule {
                    module,
                    consumed_attributes,
                } => {
                    let mut segments = parse_symbol_path(Language::Python, module);
                    segments.truncate(segments.len().saturating_sub(*consumed_attributes));
                    let root = segments.join(".");
                    canonical_import_module_fqn(self.graph, self.python, self.file, &root)
                        .or(Some(root))
                }
                ModuleBindingEventKind::FromImport { .. } | ModuleBindingEventKind::Other => None,
            })
            .collect::<Vec<_>>();
        roots.sort();
        roots.dedup();
        (roots.len() == 1).then(|| roots.remove(0))
    }

    /// The class fqn `receiver` is typed as within the given scope `facts` — a
    /// typed parameter or a `recv = Class()` local — so `recv.method` resolves to
    /// `Class.method`. Reuses the forward scan's receiver typing.
    fn receiver_type_fqn(
        &self,
        facts: &LocalBindingsSnapshot<String>,
        receiver: &str,
    ) -> Option<String> {
        let resolution = facts.resolution_for(receiver);
        let type_name = resolution
            .as_precise()
            .and_then(|targets| targets.iter().next())?;
        // `target_self_file = false`: resolve only via this file's imports and its
        // own declarations. The forward path's workspace-wide first-match fallback
        // is gated on matching a known target owner; the inverted builder has no
        // target to validate against, so enabling it would let an unimported,
        // non-local type name bind to an unrelated same-named class elsewhere.
        resolve_receiver_type(self.graph, self.python, self.file, type_name, false)
            .map(|unit| unit.fq_name())
    }

    fn record(&mut self, callee: String, node: Node<'_>) {
        let (kind, start, end) = reference_span(node);
        // Bounded mode already knows every valid callee as a local hash set, so
        // `accepts_target` is a cheap in-memory check: no reason to defer it.
        // Rooted mode has no such set; `accepts_target` there falls through to a
        // live store lookup, so every rooted-mode reference is deferred and
        // resolved together in `resolve_pending`, batching what would otherwise be
        // one round trip per reference.
        if self.targets.is_none() {
            self.pending.push(PendingCallee::Direct {
                callee,
                kind,
                start,
                end,
            });
            return;
        }
        self.record_direct(callee, kind, start, end);
    }

    /// Record `direct`, or expand it into `canonical_namespace_candidates` when it
    /// has no definition. Splits out from `record` because the choice of fallback
    /// itself depends on the same existence check `record` defers, so bounded and
    /// rooted mode must each make that choice at the same point `record` does.
    fn record_direct_or_namespace_fallback(&mut self, direct: String, node: Node<'_>) {
        let (kind, start, end) = reference_span(node);
        if self.targets.is_none() {
            self.pending.push(PendingCallee::WithNamespaceFallback {
                direct,
                kind,
                start,
                end,
            });
            return;
        }
        self.record_namespace_fallback(direct, kind, start, end);
    }

    /// Record `direct`, or every fqn in `inherited` that has a definition when
    /// `direct` does not. `inherited` is resolved eagerly (a local type-hierarchy
    /// walk, not a store round trip) so only the existence checks are deferred.
    fn record_direct_or_ancestor_fallback(
        &mut self,
        direct: String,
        inherited: Vec<String>,
        node: Node<'_>,
    ) {
        let (kind, start, end) = reference_span(node);
        if self.targets.is_none() {
            self.pending.push(PendingCallee::WithAncestorFallback {
                direct,
                inherited,
                kind,
                start,
                end,
            });
            return;
        }
        self.record_ancestor_fallback(direct, inherited, kind, start, end);
    }

    /// `record`'s immediate (bounded-mode) decision, also `resolve_pending`'s
    /// `Direct` resolution once its batch has warmed the cache. One place for
    /// the accept/reject decision so the two callers cannot drift apart.
    fn record_direct(
        &mut self,
        callee: String,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    ) {
        self.record_if_accepted(callee, kind, start, end);
    }

    fn record_if_accepted(
        &mut self,
        callee: String,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    ) -> bool {
        if !self.accepts_target(&callee) {
            return false;
        }
        self.edges.record_kind(self.input, callee, kind, start, end);
        true
    }

    /// `record_direct_or_namespace_fallback`'s immediate decision, also
    /// `resolve_pending`'s `WithNamespaceFallback` resolution.
    fn record_namespace_fallback(
        &mut self,
        direct: String,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    ) {
        if self.accepts_target(&direct) {
            self.edges.record_kind(self.input, direct, kind, start, end);
            return;
        }
        // Each candidate needs its own `accepts_target` check, not just workspace
        // membership: in bounded mode a namespace candidate can be a real declaration
        // that simply isn't one of the caller's requested targets.
        for resolved in self.canonical_namespace_candidates(&direct).iter() {
            self.record_direct(resolved.clone(), kind, start, end);
        }
    }

    /// `record_direct_or_ancestor_fallback`'s immediate decision, also
    /// `resolve_pending`'s `WithAncestorFallback` resolution.
    fn record_ancestor_fallback(
        &mut self,
        direct: String,
        inherited: Vec<String>,
        kind: UsageReferenceKind,
        start: usize,
        end: usize,
    ) {
        if self.record_if_accepted(direct, kind, start, end) {
            return;
        }
        for candidate in inherited {
            self.record_if_accepted(candidate, kind, start, end);
        }
    }

    /// Resolve every rooted-mode reference `record` and its siblings deferred,
    /// in one batch instead of one live store round trip per reference. A no-op
    /// in bounded mode, which never defers (see `record`).
    fn resolve_pending(&mut self) {
        if self.pending.is_empty() {
            return;
        }
        let mut names = Vec::new();
        for item in &self.pending {
            if self.cancellation.is_cancelled() {
                return;
            }
            match item {
                PendingCallee::Direct { callee, .. } => names.push(callee.clone()),
                PendingCallee::WithNamespaceFallback { direct, .. } => names.push(direct.clone()),
                PendingCallee::WithAncestorFallback {
                    direct, inherited, ..
                } => {
                    names.push(direct.clone());
                    names.extend(inherited.iter().cloned());
                }
            }
        }
        self.graph.index.prefetch_definitions(&names);
        for item in std::mem::take(&mut self.pending) {
            if self.cancellation.is_cancelled() {
                return;
            }
            match item {
                PendingCallee::Direct {
                    callee,
                    kind,
                    start,
                    end,
                } => self.record_direct(callee, kind, start, end),
                PendingCallee::WithNamespaceFallback {
                    direct,
                    kind,
                    start,
                    end,
                } => self.record_namespace_fallback(direct, kind, start, end),
                PendingCallee::WithAncestorFallback {
                    direct,
                    inherited,
                    kind,
                    start,
                    end,
                } => self.record_ancestor_fallback(direct, inherited, kind, start, end),
            }
        }
    }

    fn record_unproven_name(&mut self, name: &str, node: Node<'_>) {
        self.edges
            .record_unproven_name_at_node(self.input, name, node);
    }

    fn accepts_target(&self, fqn: &str) -> bool {
        self.targets.map_or_else(
            || self.graph.index.definitions(fqn).next().is_some(),
            |targets| targets.contains(fqn),
        )
    }

    fn may_have_target_terminal(&self, terminal: &str) -> bool {
        self.targets.is_none() || self.targets_by_terminal.contains_key(terminal)
    }

    fn canonical_namespace_candidates(&self, direct: &str) -> Arc<Vec<String>> {
        if let Some(cached) = self
            .canonical_namespace_candidates
            .lock()
            .expect("Python namespace candidate cache mutex poisoned")
            .get(direct)
            .cloned()
        {
            return cached;
        }

        let resolved: Arc<Vec<String>> = Arc::new(
            resolve_fqn_candidates(self.python, None, direct, |name| {
                self.graph.index.definitions(name).collect()
            })
            .into_iter()
            .map(|unit| unit.fq_name())
            .collect(),
        );
        self.canonical_namespace_candidates
            .lock()
            .expect("Python namespace candidate cache mutex poisoned")
            .entry(direct.to_string())
            .or_insert_with(|| resolved.clone())
            .clone()
    }
}

fn scan_tree(root: Node<'_>, ctx: &mut PyScan<'_>) {
    // A stack of in-scope local names, one frame per enclosing function. A name
    // bound in any frame shadows a same-named import/declaration.
    let mut scopes: Vec<FunctionScope> = Vec::new();
    walk(root, ctx, &mut scopes, None);
}

fn walk(
    node: Node<'_>,
    ctx: &mut PyScan<'_>,
    scopes: &mut Vec<FunctionScope>,
    facts: Option<usize>,
) {
    let mut merged_facts = Vec::new();
    let mut stack = vec![WalkFrame::Enter { node, facts }];
    while let Some(frame) = stack.pop() {
        if ctx.cancellation.is_cancelled() {
            return;
        }
        match frame {
            WalkFrame::Enter { node, facts } => match node.kind() {
                "import_statement" | "import_from_statement" => {}
                // A function (or lambda) opens a scope; its parameters and the names it
                // assigns are local throughout it, so collect them up front. Resolve the
                // scope's receiver-type facts once here and thread them down.
                "function_definition" | "lambda" => {
                    let function_scope = collect_function_scope(node, ctx.source);
                    let scope_facts = merged_enclosing_scope_facts(
                        ctx.graph,
                        ctx.file,
                        ctx.scope_facts,
                        &mut merged_facts,
                        node,
                        ctx.source,
                        facts,
                    );
                    push_function_children(node, facts, scope_facts, function_scope, &mut stack);
                }
                // A class body is not a function scope: code at the class-body level has
                // no enclosing-function facts. Methods inside re-resolve their own facts.
                "class_definition" => push_children(node, None, &mut stack),
                "identifier" => {
                    if !handle_annotation_reference(node, ctx) {
                        handle_identifier(node, ctx, scopes);
                    }
                    push_children(node, facts, &mut stack);
                }
                "attribute" => {
                    if handle_annotation_reference(node, ctx) {
                        continue;
                    }
                    let scope_facts = facts.and_then(|id| merged_facts.get(id));
                    handle_attribute(node, ctx, scopes, scope_facts);
                    push_children(node, facts, &mut stack);
                }
                "string_content" => {
                    handle_annotation_reference(node, ctx);
                }
                "keyword_argument" => {
                    handle_keyword_argument(node, ctx, scopes);
                    if let Some(value) = node.child_by_field_name("value") {
                        stack.push(WalkFrame::Enter { node: value, facts });
                    }
                }
                _ => push_children(node, facts, &mut stack),
            },
            WalkFrame::ExitScope => {
                scopes.pop();
            }
            WalkFrame::EnterScope(scope) => scopes.push(scope),
        }
    }
}

enum WalkFrame<'tree> {
    Enter {
        node: Node<'tree>,
        facts: Option<usize>,
    },
    EnterScope(FunctionScope),
    ExitScope,
}

fn push_children<'tree>(
    node: Node<'tree>,
    facts: Option<usize>,
    stack: &mut Vec<WalkFrame<'tree>>,
) {
    brokk_bifrost_core::analyzer::tree_walk::push_named_children_reversed_as(node, stack, |node| {
        WalkFrame::Enter { node, facts }
    });
}

fn push_function_children<'tree>(
    function: Node<'tree>,
    enclosing_facts: Option<usize>,
    body_facts: Option<usize>,
    function_scope: FunctionScope,
    stack: &mut Vec<WalkFrame<'tree>>,
) {
    let body = function.child_by_field_name("body");
    let mut function_scope = Some(function_scope);
    for index in (0..function.named_child_count()).rev() {
        if let Some(child) = function.named_child(index) {
            // Defaults and annotations are evaluated while defining the
            // function, before its parameters and locals exist. Only the body
            // executes in the new lexical scope.
            let facts = if body == Some(child) {
                body_facts
            } else {
                enclosing_facts
            };
            if body == Some(child) {
                stack.push(WalkFrame::ExitScope);
                stack.push(WalkFrame::Enter { node: child, facts });
                stack.push(WalkFrame::EnterScope(
                    function_scope
                        .take()
                        .expect("a function has exactly one body scope"),
                ));
            } else {
                stack.push(WalkFrame::Enter { node: child, facts });
            }
        }
    }
}

fn merged_enclosing_scope_facts(
    graph: &PythonGraphSource<'_>,
    file: &ProjectFile,
    scope_facts: &HashMap<CodeUnit, LocalBindingsSnapshot<String>>,
    merged_facts: &mut Vec<LocalBindingsSnapshot<String>>,
    node: Node<'_>,
    source: &str,
    inherited: Option<usize>,
) -> Option<usize> {
    let structural_local = collect_function_scope_facts_from_node(node, source);
    // A top-level function or class method has a complete indexed snapshot,
    // including factory-return facts that the node-only structural pass cannot
    // reconstruct. Nested functions and lambdas instead need their structural
    // declarations to shadow the inherited outer snapshot.
    let local = if inherited.is_none() && node.kind() == "function_definition" {
        enclosing_scope_facts(graph.index, file, scope_facts, node)
            .cloned()
            .unwrap_or(structural_local)
    } else {
        structural_local
    };
    match (local, inherited) {
        (local, Some(inherited_id)) => {
            let inherited = merged_facts.get(inherited_id)?;
            let merged = inherited.merged_with_shadowing(&local);
            let next_id = merged_facts.len();
            merged_facts.push(merged);
            Some(next_id)
        }
        (local, None) => {
            let next_id = merged_facts.len();
            merged_facts.push(local);
            Some(next_id)
        }
    }
}

#[derive(Default)]
struct FunctionScope {
    locals: HashSet<String>,
    parameters: HashSet<String>,
    globals: HashSet<String>,
}

fn is_shadowed(scopes: &[FunctionScope], name: &str) -> bool {
    for scope in scopes.iter().rev() {
        if scope.globals.contains(name) {
            return false;
        }
        if scope.locals.contains(name) {
            return true;
        }
    }
    false
}

fn is_receiver_parameter(scopes: &[FunctionScope], name: &str) -> bool {
    scopes
        .iter()
        .rev()
        .any(|scope| scope.parameters.contains(name))
}

fn handle_identifier(node: Node<'_>, ctx: &mut PyScan<'_>, scopes: &[FunctionScope]) {
    // The object of an `attribute` is handled by handle_attribute.
    if node
        .parent()
        .is_some_and(|parent| parent.kind() == "attribute")
    {
        return;
    }
    if is_declaration_identifier(node) {
        return;
    }
    let text = slice(node, ctx.source);
    if text.is_empty()
        || is_shadowed(scopes, text)
        || python_comprehension_binds_name_at(text, node, ctx.source)
        || python_type_parameter_binds_name_at(text, node, ctx.source)
    {
        return;
    }
    if let Some(callee) = ctx.bare_callee(text, node) {
        ctx.record(callee, node);
    }
}

fn handle_annotation_reference(node: Node<'_>, ctx: &mut PyScan<'_>) -> bool {
    let Some(candidates) =
        annotation_reference_candidates(ctx.graph, ctx.python, ctx.file, ctx.source, node, false)
    else {
        return false;
    };
    let [candidate] = candidates.as_slice() else {
        return !(node.kind() == "attribute" && candidates.is_empty());
    };

    let site = if node.kind() == "attribute" {
        node.child_by_field_name("attribute").unwrap_or(node)
    } else {
        node
    };
    ctx.record(candidate.fq_name(), site);
    true
}

fn handle_attribute(
    node: Node<'_>,
    ctx: &mut PyScan<'_>,
    scopes: &[FunctionScope],
    facts: Option<&LocalBindingsSnapshot<String>>,
) {
    let (Some(object), Some(attribute)) = (
        node.child_by_field_name("object"),
        node.child_by_field_name("attribute"),
    ) else {
        return;
    };
    let object_text = slice(object, ctx.source);
    let attribute_text = slice(attribute, ctx.source);
    if object_text.is_empty() || attribute_text.is_empty() {
        return;
    }
    if object.kind() == "identifier"
        && ctx.may_have_target_terminal(attribute_text)
        && let Some(module) =
            imported_module_assignment_at(node, object_text, ctx.source, |local| {
                !is_shadowed(scopes, local)
                    && ctx.namespace.get(local).is_some_and(|binding| {
                        binding.module == "importlib" && binding.consumed_attributes == 0
                    })
            })
    {
        let direct = format!("{module}.{attribute_text}");
        ctx.record_direct_or_namespace_fallback(direct, attribute);
    }
    if object.kind() == "call" && ctx.may_have_target_terminal(attribute_text) {
        for class in call_result_types(ctx.graph, ctx.python, ctx.file, ctx.source, object, facts) {
            let direct = format!("{}.{attribute_text}", class.fq_name());
            let inherited = ctx.graph.hierarchy.map_or_else(Vec::new, |provider| {
                provider
                    .get_ancestors(&class)
                    .into_iter()
                    .map(|ancestor| format!("{}.{attribute_text}", ancestor.fq_name()))
                    .collect()
            });
            ctx.record_direct_or_ancestor_fallback(direct, inherited, attribute);
        }
    }
    // `module.symbol` or a deeper `module.ns.symbol` chain rooted at a
    // namespace import. Walk the attribute structure from the leftmost imported
    // root so deep chains stay exact without source-text splitting.
    if let Some((root, attributes)) = attribute_chain(node) {
        let root_text = slice(root, ctx.source);
        if !root_text.is_empty()
            && !is_shadowed(scopes, root_text)
            && let Some(binding) = ctx.namespace.get(root_text)
        {
            let mut direct = binding.module.clone();
            let workspace_module = binding.workspace_module;
            let consumed_attributes = binding.consumed_attributes;
            if object.kind() == "identifier" {
                ctx.record(direct.clone(), object);
            }
            for member in attributes.into_iter().skip(consumed_attributes) {
                let member_text = slice(member, ctx.source);
                if member_text.is_empty() {
                    return;
                }
                direct.push('.');
                direct.push_str(member_text);
            }
            // A re-export alias can change the terminal name (`proto.module` may
            // canonically resolve to `proto.modules.define_module`), so terminal-name
            // filtering is not sound here. Namespace imports are already a narrow,
            // structured subset of attributes; resolve their workspace candidates
            // and let `record` retain only requested targets.
            if workspace_module {
                ctx.record_direct_or_namespace_fallback(direct, attribute);
            } else {
                ctx.record(direct, attribute);
            }
            return;
        }
    }

    // `recv.method` where recv is a typed local/parameter: resolve to the
    // receiver's class fqn. Unknown or ambiguous receiver facts are not enough
    // for a proven edge, but they are structured evidence that a same-named
    // member may be reachable, so bulk dead-code treats the candidate as
    // inconclusive instead of dead.
    if let Some(facts) = facts
        && ctx.may_have_target_terminal(attribute_text)
    {
        if matches!(object_text, "self" | "cls") {
            // `self.member` / `cls.member` is a same-owner reference (#1138):
            // record it as unproven inbound rather than a proven edge, so a
            // member reachable only through same-owner access reads
            // INCONCLUSIVE, never confidently dead — matching the other
            // languages.
            ctx.record_unproven_name(attribute_text, attribute);
        } else if let Some(type_fqn) = ctx.receiver_type_fqn(facts, object_text) {
            ctx.record(format!("{type_fqn}.{attribute_text}"), attribute);
        } else if object.kind() == "identifier" && !ctx.named.contains_key(object_text) {
            let resolution = facts.resolution_for(object_text);
            if resolution.is_ambiguous()
                || (resolution.is_unknown() && is_receiver_parameter(scopes, object_text))
            {
                ctx.record_unproven_name(attribute_text, attribute);
            }
        }
    }
}

fn handle_keyword_argument(node: Node<'_>, ctx: &mut PyScan<'_>, scopes: &[FunctionScope]) {
    let (Some(name), Some(arguments)) = (node.child_by_field_name("name"), node.parent()) else {
        return;
    };
    if name.kind() != "identifier" || arguments.kind() != "argument_list" {
        return;
    }
    let Some(call) = arguments.parent().filter(|parent| parent.kind() == "call") else {
        return;
    };
    let Some(function) = call.child_by_field_name("function") else {
        return;
    };
    let member = slice(name, ctx.source);
    if member.is_empty() || !ctx.may_have_target_terminal(member) {
        return;
    }
    let scoped_class_fqn = if function.kind() == "identifier" {
        enclosing_scope_facts(ctx.graph.index, ctx.file, ctx.scope_facts, function)
            .and_then(|facts| ctx.receiver_type_fqn(facts, slice(function, ctx.source)))
    } else {
        None
    };
    let function_name = (function.kind() == "identifier").then(|| slice(function, ctx.source));
    let mut default_classes = function_name.map_or_else(Vec::new, |local_name| {
        resolve_callable_parameter_default_types(
            ctx.graph, ctx.python, ctx.file, ctx.source, function, local_name,
        )
    });
    let root_shadowed = leftmost_identifier(function)
        .is_some_and(|root| is_shadowed(scopes, slice(root, ctx.source)));
    if !root_shadowed && let Some(local_name) = function_name {
        let cutoff = if python_reference_is_deferred_function_body(function) {
            usize::MAX
        } else {
            function.start_byte()
        };
        default_classes.extend(resolve_visible_named_import_candidates(
            ctx.graph,
            ctx.python,
            ctx.file,
            ctx.module_bindings.as_ref(),
            local_name,
            cutoff,
        ));
    }
    let mut classes = if function_name == Some("cls") {
        lexical_class(ctx, function).into_iter().collect()
    } else {
        if root_shadowed && scoped_class_fqn.is_none() && default_classes.is_empty() {
            return;
        }
        if !root_shadowed {
            default_classes.extend(resolve_constructor_types(
                ctx.graph, ctx.python, ctx.file, ctx.source, function,
            ));
        }
        default_classes
    };
    if let Some(fqn) = scoped_class_fqn {
        classes.extend(ctx.graph.index.definitions(&fqn).filter(CodeUnit::is_class));
        classes.sort();
        classes.dedup();
    }
    for class in classes {
        for declaration in resolved_member_declarations(ctx.graph, &class, member) {
            ctx.record(declaration.fq_name(), name);
        }
    }
}

fn lexical_class(ctx: &PyScan<'_>, node: Node<'_>) -> Option<CodeUnit> {
    let range = Range {
        start_byte: node.start_byte(),
        end_byte: node.end_byte(),
        start_line: 0,
        end_line: 0,
    };
    let enclosing = ctx.graph.index.enclosing_code_unit(ctx.file, &range)?;
    if enclosing.is_class() {
        Some(enclosing)
    } else {
        ctx.graph
            .index
            .parent_of(&enclosing)
            .filter(CodeUnit::is_class)
    }
}

/// The local names a function binds: its parameters plus every name it assigns.
/// Python scoping is function-wide, so a name assigned anywhere in the body is
/// local throughout; nested function/class scopes are skipped (they get their
/// own frame), but the names they bind in *this* scope are kept.
fn collect_function_scope(func: Node<'_>, source: &str) -> FunctionScope {
    let mut scope = FunctionScope::default();
    if let Some(params) = func.child_by_field_name("parameters") {
        collect_parameter_names(params, source, &mut scope.parameters);
        scope.locals.extend(scope.parameters.iter().cloned());
    }
    if let Some(body) = func.child_by_field_name("body") {
        collect_bound_targets(body, source, &mut scope.locals);
        collect_scope_globals(body, source, &mut scope.globals);
        scope.locals.retain(|name| !scope.globals.contains(name));
    }
    scope
}

fn collect_scope_globals(node: Node<'_>, source: &str, out: &mut HashSet<String>) {
    let root = node;
    let mut stack = vec![node];
    while let Some(node) = stack.pop() {
        if node.kind() == "global_statement" {
            let mut cursor = node.walk();
            for child in node.named_children(&mut cursor) {
                if child.kind() == "identifier" {
                    let name = slice(child, source).trim();
                    if !name.is_empty() {
                        out.insert(name.to_string());
                    }
                }
            }
            continue;
        }
        if node != root
            && matches!(
                node.kind(),
                "function_definition" | "lambda" | "class_definition"
            )
        {
            continue;
        }
        let mut cursor = node.walk();
        let mut children: Vec<_> = node.named_children(&mut cursor).collect();
        children.reverse();
        stack.extend(children);
    }
}

fn collect_parameter_names(params: Node<'_>, source: &str, out: &mut HashSet<String>) {
    let mut cursor = params.walk();
    for child in params.named_children(&mut cursor) {
        let name = match child.kind() {
            "identifier" => Some(child),
            // typed / default / splat parameters carry the binding either in a
            // `name` field or as their first identifier child.
            _ => child
                .child_by_field_name("name")
                .or_else(|| child.named_child(0).filter(|n| n.kind() == "identifier")),
        };
        if let Some(name) = name {
            let text = slice(name, source).trim();
            if !text.is_empty() {
                out.insert(text.to_string());
            }
        }
    }
}

/// Collect names bound by assignment within a scope, without descending into
/// nested function/class scopes (only the nested definition's own name is bound
/// here).
fn collect_bound_targets(node: Node<'_>, source: &str, out: &mut HashSet<String>) {
    let mut stack = vec![node];
    while let Some(node) = stack.pop() {
        match node.kind() {
            "function_definition" | "class_definition" => {
                if let Some(name) = node.child_by_field_name("name") {
                    let text = slice(name, source).trim();
                    if !text.is_empty() {
                        out.insert(text.to_string());
                    }
                }
                continue;
            }
            "lambda" => continue,
            "assignment" | "augmented_assignment" | "for_statement" | "for_in_clause" => {
                if let Some(left) = node.child_by_field_name("left") {
                    collect_assigned_identifiers(left, source, out);
                }
            }
            "named_expression" => {
                if let Some(name) = node.child_by_field_name("name") {
                    collect_assigned_identifiers(name, source, out);
                }
            }
            _ => {}
        }
        let mut cursor = node.walk();
        let mut children: Vec<Node<'_>> = node.named_children(&mut cursor).collect();
        children.reverse();
        stack.extend(children);
    }
}