brokk_bifrost_python/

bindings.rs

use tree_sitter::Node;

use brokk_bifrost_core::hash::{HashMap, HashSet};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum PythonLexicalNameResolution {
    Unbound,
    Local,
    Nonlocal,
    Global,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum PythonDirectScopeBindingKind {
    ClassDeclaration,
    FunctionDeclaration,
    Import,
    Other,
}

/// Whether `reference` reads a target introduced by an enclosing comprehension.
///
/// Comprehensions create an implicit scope even at module level. The element
/// expression is textually before its `for` clauses but evaluates after their
/// binders. Only the first iterable evaluates in the enclosing scope; later
/// iterables use comprehension-local names, including not-yet-bound targets.
/// This structured walk models those scopes without source-text parsing.
pub fn python_comprehension_binds_name_at(name: &str, reference: Node<'_>, source: &str) -> bool {
    let mut current = reference;
    while let Some(parent) = current.parent() {
        if is_comprehension(parent.kind()) {
            let mut cursor = parent.walk();
            let clauses = parent
                .named_children(&mut cursor)
                .filter(|child| child.kind() == "for_in_clause")
                .collect::<Vec<_>>();
            let in_outer_iterable = clauses.first().is_some_and(|clause| {
                let mut cursor = clause.walk();
                clause
                    .children_by_field_name("right", &mut cursor)
                    .any(|right| {
                        right.start_byte() <= reference.start_byte()
                            && reference.end_byte() <= right.end_byte()
                    })
            });
            if in_outer_iterable {
                current = parent;
                continue;
            }
            for clause in clauses {
                let Some(target) = clause.child_by_field_name("left") else {
                    continue;
                };
                let mut bound = false;
                collect_binding_targets(target, source, &mut || true, |candidate, _| {
                    bound |= candidate == name;
                })
                .expect("unbounded comprehension target collection completes");
                if bound {
                    return true;
                }
            }
        }
        if matches!(
            parent.kind(),
            "function_definition" | "lambda" | "class_definition" | "module"
        ) {
            break;
        }
        current = parent;
    }
    false
}

/// Whether `reference` reads a PEP 695 type parameter declared by its enclosing
/// class, function, or type-alias definition.
///
/// Type parameters are lexical bindings rather than indexed workspace
/// declarations. The binder is the first identifier in each structured
/// parameter node; identifiers in bounds and constraints remain references.
pub fn python_type_parameter_binds_name_at(name: &str, reference: Node<'_>, source: &str) -> bool {
    let mut current = reference;
    let mut enclosing_functions = Vec::new();
    while let Some(parent) = current.parent() {
        if parent.kind() == "function_definition" {
            enclosing_functions.push(parent);
        }
        if matches!(
            parent.kind(),
            "class_definition" | "function_definition" | "type_alias_statement"
        ) && let Some(parameters) = parent.child_by_field_name("type_parameters")
            && !(parameters.start_byte() <= reference.start_byte()
                && reference.end_byte() <= parameters.end_byte())
        {
            let mut cursor = parameters.walk();
            for parameter in parameters.named_children(&mut cursor) {
                let binder = if parameter.kind() == "identifier" {
                    Some(parameter)
                } else {
                    first_identifier_bounded(parameter, &mut || true).flatten()
                };
                if binder.is_some_and(|binder| node_text(binder, source) == name) {
                    // Only a name that actually matched an enclosing type
                    // parameter needs the function-wide directive scans. This
                    // keeps the hot-path check for ordinary identifiers a
                    // bounded ancestor walk with no scope-inventory builds.
                    return !python_name_declared_global_at_in_functions(
                        name,
                        reference,
                        source,
                        enclosing_functions,
                    );
                }
            }
        }
        current = parent;
    }
    false
}

/// Resolve `name` through the nearest enclosing function scope. This is the
/// structured fallback for references inside nested functions that do not
/// have their own indexed `CodeUnit` scope snapshot.
pub fn python_name_resolution_at(
    name: &str,
    reference: Node<'_>,
    source: &str,
) -> PythonLexicalNameResolution {
    let mut functions = Vec::new();
    let mut current = reference;
    while let Some(parent) = current.parent() {
        if parent.kind() == "function_definition" {
            functions.push(parent);
        }
        current = parent;
    }
    python_name_resolution_at_in_functions(name, reference, source, functions)
}

fn python_name_declared_global_at_in_functions(
    name: &str,
    reference: Node<'_>,
    source: &str,
    functions: Vec<Node<'_>>,
) -> bool {
    python_name_resolution_at_in_functions(name, reference, source, functions)
        == PythonLexicalNameResolution::Global
}

fn python_name_resolution_at_in_functions(
    name: &str,
    reference: Node<'_>,
    source: &str,
    functions: Vec<Node<'_>>,
) -> PythonLexicalNameResolution {
    for function in functions {
        let parameter_names = function
            .child_by_field_name("parameters")
            .into_iter()
            .flat_map(|parameters| {
                let mut cursor = parameters.walk();
                parameters
                    .named_children(&mut cursor)
                    .filter_map(|parameter| python_parameter_name(parameter, source))
                    .collect::<Vec<_>>()
            })
            .collect::<Vec<_>>();
        let Some(inventory) =
            PythonLexicalScopeInventory::collect_bounded(function, source, parameter_names, || {
                true
            })
        else {
            return PythonLexicalNameResolution::Unbound;
        };
        let resolution = inventory.name_resolution_at(name, reference);
        match resolution {
            PythonLexicalNameResolution::Global => return PythonLexicalNameResolution::Global,
            PythonLexicalNameResolution::Local | PythonLexicalNameResolution::Nonlocal => {
                return resolution;
            }
            PythonLexicalNameResolution::Unbound => {}
        }
    }
    PythonLexicalNameResolution::Unbound
}

fn python_parameter_name(node: Node<'_>, source: &str) -> Option<String> {
    match node.kind() {
        "identifier" => Some(node_text(node, source).trim().to_string()),
        "typed_parameter"
        | "typed_default_parameter"
        | "default_parameter"
        | "list_splat_pattern"
        | "dictionary_splat_pattern" => node
            .child_by_field_name("name")
            .or_else(|| {
                let mut cursor = node.walk();
                node.named_children(&mut cursor)
                    .find(|child| child.kind() == "identifier")
            })
            .and_then(|name| python_parameter_name(name, source)),
        _ => None,
    }
    .filter(|name| !name.is_empty())
}

/// Whether this identifier is the binder (rather than a bound/constraint use)
/// of one structured PEP 695 type parameter.
pub fn python_is_type_parameter_binder(node: Node<'_>) -> bool {
    if node.kind() != "identifier" {
        return false;
    }
    let mut current = node;
    while let Some(parent) = current.parent() {
        if matches!(
            parent.kind(),
            "class_definition" | "function_definition" | "type_alias_statement"
        ) && let Some(parameters) = parent.child_by_field_name("type_parameters")
            && parameters.start_byte() <= node.start_byte()
            && node.end_byte() <= parameters.end_byte()
        {
            let mut cursor = parameters.walk();
            return parameters.named_children(&mut cursor).any(|parameter| {
                let binder = if parameter.kind() == "identifier" {
                    Some(parameter)
                } else {
                    first_identifier_bounded(parameter, &mut || true).flatten()
                };
                binder.is_some_and(|binder| binder.id() == node.id())
            });
        }
        if matches!(
            parent.kind(),
            "module" | "class_definition" | "function_definition" | "type_alias_statement"
        ) {
            return false;
        }
        current = parent;
    }
    false
}

#[derive(Clone, Copy, Debug)]
pub struct PythonDirectScopeBinding<'tree> {
    pub declaration: Node<'tree>,
    pub kind: PythonDirectScopeBindingKind,
}

#[derive(Clone, Debug)]
struct PythonLocalBinding<'tree> {
    name: Box<str>,
    declaration: Node<'tree>,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum PythonLocalBindingKind {
    FunctionOnly,
    Other,
}

#[derive(Clone, Debug)]
struct PythonComprehensionBinding {
    name: Box<str>,
    start_byte: usize,
    end_byte: usize,
    enclosing_iterable_ranges: Vec<(usize, usize)>,
}

/// Function-scope Python bindings discovered from tree-sitter structure.
///
/// The inventory models Python's whole-function symbol-table behavior while
/// retaining the implicit scope of comprehension targets. Construction is
/// iterative and every inspected node is gated by `scope_step`; `None` means
/// the caller stopped discovery and must conservatively avoid module fallback.
pub struct PythonLexicalScopeInventory<'tree> {
    locals: Vec<PythonLocalBinding<'tree>>,
    bindings: PythonLexicalScopeBindings,
}

/// Completed function binding facts without borrowed tree-sitter nodes.
/// Retain these only under the identity of the exact source that produced them.
pub struct PythonLexicalScopeBindings {
    parameters: HashSet<Box<str>>,
    local_names: HashMap<Box<str>, PythonLocalBindingKind>,
    binding_writes: HashSet<Box<str>>,
    globals: HashSet<Box<str>>,
    nonlocals: HashSet<Box<str>>,
    comprehensions: Vec<PythonComprehensionBinding>,
}

impl PythonLexicalScopeBindings {
    pub fn name_resolution_at(
        &self,
        name: &str,
        reference: Node<'_>,
    ) -> PythonLexicalNameResolution {
        let reference_byte = reference.start_byte();
        if self.comprehensions.iter().any(|binding| {
            binding.name.as_ref() == name
                && binding.start_byte <= reference_byte
                && reference_byte < binding.end_byte
                && !binding
                    .enclosing_iterable_ranges
                    .iter()
                    .any(|(start, end)| *start <= reference_byte && reference_byte < *end)
        }) {
            return PythonLexicalNameResolution::Local;
        }
        if self.nonlocals.contains(name) {
            return PythonLexicalNameResolution::Nonlocal;
        }
        if self.globals.contains(name) {
            return PythonLexicalNameResolution::Global;
        }
        if self.parameters.contains(name) || self.local_names.contains_key(name) {
            PythonLexicalNameResolution::Local
        } else {
            PythonLexicalNameResolution::Unbound
        }
    }

    pub fn resolves_to_local_function(&self, name: &str, reference: Node<'_>) -> bool {
        let reference_byte = reference.start_byte();
        !self.parameters.contains(name)
            && !self.comprehensions.iter().any(|binding| {
                binding.name.as_ref() == name
                    && binding.start_byte <= reference_byte
                    && reference_byte < binding.end_byte
                    && !binding
                        .enclosing_iterable_ranges
                        .iter()
                        .any(|(start, end)| *start <= reference_byte && reference_byte < *end)
            })
            && self.local_names.get(name) == Some(&PythonLocalBindingKind::FunctionOnly)
    }

    /// Whether the active callable obtains `name` from a runtime binding
    /// rather than an untouched function or import declaration.
    pub fn has_runtime_callable_binding_at(&self, name: &str, reference: Node<'_>) -> bool {
        let reference_byte = reference.start_byte();
        self.parameters.contains(name)
            || self.binding_writes.contains(name)
            || self.comprehensions.iter().any(|binding| {
                binding.name.as_ref() == name
                    && binding.start_byte <= reference_byte
                    && reference_byte < binding.end_byte
                    && !binding
                        .enclosing_iterable_ranges
                        .iter()
                        .any(|(start, end)| *start <= reference_byte && reference_byte < *end)
            })
    }
}

#[derive(Clone, Copy)]
struct ScanFrame<'tree> {
    node: Node<'tree>,
    in_comprehension: bool,
}

impl<'tree> PythonLexicalScopeInventory<'tree> {
    /// `parameter_names` is the callable's formal-parameter name stream. The
    /// layout it comes from is resolved by `analyzer/lexical_definitions.rs`,
    /// which dispatches through the analysis-side language registry and so
    /// cannot be named here; `analyzer/python/lexical_scope.rs` in
    /// `brokk-bifrost-analysis` is the one caller that computes it, under the
    /// same `scope_step` meter this walk uses.
    pub fn collect_bounded(
        callable: Node<'tree>,
        source: &str,
        parameter_names: impl IntoIterator<Item = String>,
        mut scope_step: impl FnMut() -> bool,
    ) -> Option<Self> {
        let mut inventory = Self {
            locals: Vec::new(),
            bindings: PythonLexicalScopeBindings {
                parameters: parameter_names.into_iter().map(Box::<str>::from).collect(),
                local_names: HashMap::default(),
                binding_writes: HashSet::default(),
                globals: HashSet::default(),
                nonlocals: HashSet::default(),
                comprehensions: Vec::new(),
            },
        };
        let Some(body) = callable.child_by_field_name("body") else {
            return Some(inventory);
        };
        let mut stack = vec![ScanFrame {
            node: body,
            in_comprehension: false,
        }];

        while let Some(frame) = stack.pop() {
            if !scope_step() {
                return None;
            }
            let node = frame.node;
            let nested_scope = node != body
                && matches!(
                    node.kind(),
                    "function_definition" | "lambda" | "class_definition"
                );
            if nested_scope {
                if matches!(node.kind(), "function_definition" | "class_definition")
                    && let Some(name) = node.child_by_field_name("name")
                {
                    inventory.record_local_node(name, source);
                }
                // Defaults, annotations, bases, and type-parameter expressions
                // execute in an enclosing scope. Keep scanning those headers
                // for walrus/comprehension bindings while pruning the nested
                // callable or class body itself.
                push_nested_scope_header_children(
                    &mut stack,
                    node,
                    frame.in_comprehension,
                    &mut scope_step,
                )?;
                continue;
            }

            match node.kind() {
                "global_statement" => {
                    collect_direct_identifier_names(node, source, &mut scope_step, |name| {
                        inventory.bindings.globals.insert(name.into());
                    })?;
                    continue;
                }
                "nonlocal_statement" => {
                    collect_direct_identifier_names(node, source, &mut scope_step, |name| {
                        inventory.bindings.nonlocals.insert(name.into());
                    })?;
                    continue;
                }
                "import_statement" | "import_from_statement" => {
                    collect_import_bindings(node, &mut scope_step, |binding| {
                        inventory.record_local_node(binding, source)
                    })?;
                    continue;
                }
                "assignment" | "augmented_assignment" => {
                    if let Some(target) = node.child_by_field_name("left") {
                        collect_binding_targets(
                            target,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                    }
                }
                "type_alias_statement" => {
                    if let Some(target) = node.child_by_field_name("left")
                        && let Some(binding) = first_identifier_bounded(target, &mut scope_step)?
                    {
                        inventory.record_local_node(binding, source);
                    }
                }
                "named_expression" => {
                    // PEP 572 binds a comprehension walrus in the containing
                    // non-comprehension scope, so this remains a function local.
                    if let Some(target) = node.child_by_field_name("name") {
                        collect_binding_targets(
                            target,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                    }
                }
                "for_statement" => {
                    if let Some(target) = node.child_by_field_name("left") {
                        collect_binding_targets(
                            target,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                    }
                }
                "for_in_clause" => {
                    // These occur inside comprehensions and belong to their
                    // implicit scope. The enclosing comprehension records them.
                }
                "delete_statement" => {
                    for target in named_children_bounded(node, &mut scope_step)? {
                        collect_binding_targets(
                            target,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                    }
                    continue;
                }
                "as_pattern" => {
                    if let Some(alias) = node.child_by_field_name("alias") {
                        collect_binding_targets(
                            alias,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                        push_named_children_except(
                            &mut stack,
                            node,
                            alias,
                            frame.in_comprehension,
                            &mut scope_step,
                        )?;
                        continue;
                    }
                }
                "except_clause" => {
                    // Older grammar shapes expose the alias directly. Current
                    // tree-sitter-python nests it in an `as_pattern`, handled
                    // above when the clause's children are scanned.
                    if let Some(alias) = node.child_by_field_name("alias") {
                        collect_binding_targets(
                            alias,
                            source,
                            &mut scope_step,
                            |name, declaration| {
                                inventory.record_binding_write(name, declaration);
                            },
                        )?;
                    }
                }
                "case_clause" => {
                    let children = named_children_bounded(node, &mut scope_step)?;
                    for child in children.iter().copied() {
                        if child.kind() == "case_pattern" {
                            collect_match_pattern_bindings(
                                child,
                                source,
                                &mut scope_step,
                                |name, declaration| {
                                    inventory.record_binding_write(name, declaration);
                                },
                            )?;
                        }
                    }
                    for child in children.into_iter().rev() {
                        if child.kind() != "case_pattern" {
                            stack.push(ScanFrame {
                                node: child,
                                in_comprehension: frame.in_comprehension,
                            });
                        }
                    }
                    continue;
                }
                kind if is_comprehension(kind) => {
                    let range = (node.start_byte(), node.end_byte());
                    let children = named_children_bounded(node, &mut scope_step)?;
                    let enclosing_iterable_ranges = if let Some(first_clause) = children
                        .iter()
                        .copied()
                        .find(|child| child.kind() == "for_in_clause")
                    {
                        children_by_field_name_bounded(first_clause, "right", &mut scope_step)?
                            .into_iter()
                            .map(|iterable| (iterable.start_byte(), iterable.end_byte()))
                            .collect()
                    } else {
                        Vec::new()
                    };
                    for clause in children
                        .iter()
                        .copied()
                        .filter(|child| child.kind() == "for_in_clause")
                    {
                        if let Some(target) = clause.child_by_field_name("left") {
                            collect_binding_targets(target, source, &mut scope_step, |name, _| {
                                inventory.bindings.comprehensions.push(
                                    PythonComprehensionBinding {
                                        name: name.into(),
                                        start_byte: range.0,
                                        end_byte: range.1,
                                        enclosing_iterable_ranges: enclosing_iterable_ranges
                                            .clone(),
                                    },
                                );
                            })?;
                        }
                    }
                    for child in children.into_iter().rev() {
                        stack.push(ScanFrame {
                            node: child,
                            in_comprehension: true,
                        });
                    }
                    continue;
                }
                _ => {}
            }

            push_named_children(&mut stack, node, frame.in_comprehension, &mut scope_step)?;
        }

        // `global` and `nonlocal` are whole-function directives regardless of
        // source order. Neither declaration may become a semantic local.
        inventory.locals.retain(|binding| {
            !inventory.bindings.globals.contains(binding.name.as_ref())
                && !inventory.bindings.nonlocals.contains(binding.name.as_ref())
        });
        inventory.bindings.local_names.retain(|name, _| {
            !inventory.bindings.globals.contains(name.as_ref())
                && !inventory.bindings.nonlocals.contains(name.as_ref())
        });
        Some(inventory)
    }

    pub fn into_bindings(self) -> PythonLexicalScopeBindings {
        self.bindings
    }

    pub fn name_resolution_at(
        &self,
        name: &str,
        reference: Node<'_>,
    ) -> PythonLexicalNameResolution {
        self.bindings.name_resolution_at(name, reference)
    }

    pub fn resolves_to_local_function(&self, name: &str, reference: Node<'_>) -> bool {
        self.bindings.resolves_to_local_function(name, reference)
    }

    pub fn has_runtime_callable_binding_at(&self, name: &str, reference: Node<'_>) -> bool {
        self.bindings
            .has_runtime_callable_binding_at(name, reference)
    }

    pub fn local_function_declaration(
        &self,
        name: &str,
        reference: Node<'_>,
    ) -> Option<Node<'tree>> {
        self.resolves_to_local_function(name, reference)
            .then(|| {
                self.locals
                    .iter()
                    .find(|binding| binding.name.as_ref() == name)
                    .and_then(|binding| binding.declaration.parent())
                    .filter(|declaration| declaration.kind() == "function_definition")
            })
            .flatten()
    }

    pub fn local_bindings(&self) -> impl Iterator<Item = (&str, Node<'tree>)> + '_ {
        self.locals
            .iter()
            .map(|binding| (binding.name.as_ref(), binding.declaration))
    }

    fn record_local_node(&mut self, node: Node<'tree>, source: &str) {
        let name = node_text(node, source);
        self.record_local(name, node);
    }

    fn record_local(&mut self, name: &str, declaration: Node<'tree>) {
        if name.is_empty() {
            return;
        }
        let binding_kind = if is_function_declaration_name(declaration) {
            PythonLocalBindingKind::FunctionOnly
        } else {
            PythonLocalBindingKind::Other
        };
        match self.bindings.local_names.entry(name.into()) {
            std::collections::hash_map::Entry::Vacant(entry) => {
                entry.insert(binding_kind);
                self.locals.push(PythonLocalBinding {
                    name: name.into(),
                    declaration,
                });
            }
            std::collections::hash_map::Entry::Occupied(mut entry) => {
                entry.insert(PythonLocalBindingKind::Other);
            }
        }
    }

    fn record_binding_write(&mut self, name: &str, declaration: Node<'tree>) {
        if !name.is_empty() {
            self.bindings.binding_writes.insert(name.into());
        }
        self.record_local(name, declaration);
    }
}

fn is_function_declaration_name(node: Node<'_>) -> bool {
    node.parent().is_some_and(|parent| {
        parent.kind() == "function_definition"
            && parent
                .child_by_field_name("name")
                .is_some_and(|name| name.id() == node.id())
    })
}

/// Return the bindings introduced directly by `node`.
///
/// Descendant traversal remains the caller's responsibility. This lets the
/// semantic file walk build a module binding inventory without adding a
/// second whole-file scan, while reusing the same structured target handling
/// as function symbol-table discovery.
pub fn python_direct_scope_bindings_bounded<'tree>(
    node: Node<'tree>,
    source: &str,
    mut scope_step: impl FnMut() -> bool,
) -> Option<Vec<PythonDirectScopeBinding<'tree>>> {
    let mut bindings = Vec::new();

    match node.kind() {
        "function_definition" => {
            if let Some(name) = node.child_by_field_name("name") {
                bindings.push(PythonDirectScopeBinding {
                    declaration: name,
                    kind: if is_direct_module_definition_bounded(node, &mut scope_step)? {
                        PythonDirectScopeBindingKind::FunctionDeclaration
                    } else {
                        PythonDirectScopeBindingKind::Other
                    },
                });
            }
        }
        "class_definition" => {
            if let Some(name) = node.child_by_field_name("name") {
                bindings.push(PythonDirectScopeBinding {
                    declaration: name,
                    kind: if is_direct_module_definition_bounded(node, &mut scope_step)? {
                        PythonDirectScopeBindingKind::ClassDeclaration
                    } else {
                        PythonDirectScopeBindingKind::Other
                    },
                });
            }
        }
        "import_statement" | "import_from_statement" => {
            let module_level = is_direct_module_definition_bounded(node, &mut scope_step)?;
            collect_import_bindings(node, &mut scope_step, |declaration| {
                bindings.push(PythonDirectScopeBinding {
                    declaration,
                    kind: if module_level {
                        PythonDirectScopeBindingKind::Import
                    } else {
                        PythonDirectScopeBindingKind::Other
                    },
                });
            })?;
        }
        "assignment" | "augmented_assignment" => {
            if let Some(target) = node.child_by_field_name("left") {
                collect_binding_targets(target, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "type_alias_statement" => {
            if let Some(target) = node.child_by_field_name("left")
                && let Some(declaration) = first_identifier_bounded(target, &mut scope_step)?
            {
                bindings.push(PythonDirectScopeBinding {
                    declaration,
                    kind: PythonDirectScopeBindingKind::Other,
                });
            }
        }
        "named_expression" => {
            if let Some(target) = node.child_by_field_name("name") {
                collect_binding_targets(target, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "for_statement" => {
            if let Some(target) = node.child_by_field_name("left") {
                collect_binding_targets(target, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "delete_statement" => {
            for target in named_children_bounded(node, &mut scope_step)? {
                collect_binding_targets(target, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "as_pattern" => {
            if let Some(alias) = node.child_by_field_name("alias") {
                collect_binding_targets(alias, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "except_clause" => {
            if let Some(alias) = node.child_by_field_name("alias") {
                collect_binding_targets(alias, source, &mut scope_step, |_, declaration| {
                    bindings.push(PythonDirectScopeBinding {
                        declaration,
                        kind: PythonDirectScopeBindingKind::Other,
                    });
                })?;
            }
        }
        "case_clause" => {
            for child in named_children_bounded(node, &mut scope_step)? {
                if child.kind() == "case_pattern" {
                    collect_match_pattern_bindings(
                        child,
                        source,
                        &mut scope_step,
                        |_, declaration| {
                            bindings.push(PythonDirectScopeBinding {
                                declaration,
                                kind: PythonDirectScopeBindingKind::Other,
                            });
                        },
                    )?;
                }
            }
        }
        _ => {}
    }
    Some(bindings)
}

/// Whether a module or class execution scope binds `target_name` anywhere in
/// its direct scope. Nested callable and class bodies are separate scopes, but
/// their headers still execute in this scope. A wildcard import keeps the
/// name's runtime identity open even when it does not expose a static binder.
pub fn python_module_or_class_scope_binds_name_bounded(
    scope: Node<'_>,
    target_name: &str,
    source: &str,
    mut scope_step: impl FnMut() -> bool,
) -> Option<bool> {
    assert!(matches!(scope.kind(), "module" | "class_definition"));
    let body = scope.child_by_field_name("body").unwrap_or(scope);
    let mut stack = vec![body];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        if node.kind() == "wildcard_import" {
            return Some(true);
        }
        if python_direct_scope_bindings_bounded(node, source, &mut scope_step)?
            .into_iter()
            .any(|binding| node_text(binding.declaration, source) == target_name)
        {
            return Some(true);
        }
        let excluded_body = matches!(
            node.kind(),
            "class_definition" | "function_definition" | "lambda"
        )
        .then(|| node.child_by_field_name("body").map(|body| body.id()))
        .flatten();
        let mut cursor = node.walk();
        stack.extend(
            node.named_children(&mut cursor)
                .filter(|child| Some(child.id()) != excluded_body),
        );
    }
    Some(false)
}

pub fn python_unambiguous_module_class_binding_bounded(
    root: Node<'_>,
    source: &str,
    target_name: &str,
    scope_step: impl FnMut() -> bool,
) -> Option<bool> {
    Some(
        python_unambiguous_module_binding_bounded(root, source, target_name, scope_step)?
            == Some(PythonDirectScopeBindingKind::ClassDeclaration),
    )
}

/// The kind of the module scope's one binding of `target_name`.
///
/// `Some(None)` says the module does not bind the name, binds it more than
/// once, or leaves its identity open through a wildcard import; the name is
/// then not a proven reference to one module-level declaration. `None` says the
/// bounded walk ran out of work.
pub fn python_unambiguous_module_binding_bounded(
    root: Node<'_>,
    source: &str,
    target_name: &str,
    mut scope_step: impl FnMut() -> bool,
) -> Option<Option<PythonDirectScopeBindingKind>> {
    let mut matched = None;
    let mut stack = vec![root];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        // A later unconditional declaration replaces an earlier wildcard
        // binding; a wildcard after it leaves its identity open.
        if node.kind() == "wildcard_import" && matched.is_some() {
            return Some(None);
        }
        for binding in python_direct_scope_bindings_bounded(node, source, &mut scope_step)? {
            if node_text(binding.declaration, source) != target_name {
                continue;
            }
            if matched.is_some() {
                return Some(None);
            }
            matched = Some(binding.kind);
            if binding.kind == PythonDirectScopeBindingKind::Other {
                return Some(Some(PythonDirectScopeBindingKind::Other));
            }
        }

        let body = matches!(
            node.kind(),
            "function_definition" | "class_definition" | "lambda"
        )
        .then(|| node.child_by_field_name("body").map(|child| child.id()))
        .flatten();
        let name = matches!(node.kind(), "function_definition" | "class_definition")
            .then(|| node.child_by_field_name("name").map(|child| child.id()))
            .flatten();
        for child in named_children_bounded(node, &mut scope_step)?
            .into_iter()
            .filter(|child| Some(child.id()) != body && Some(child.id()) != name)
            .rev()
        {
            stack.push(child);
        }
    }
    Some(matched)
}

fn is_direct_module_definition_bounded(
    node: Node<'_>,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<bool> {
    if !scope_step() {
        return None;
    }
    let Some(mut parent) = node.parent() else {
        return Some(false);
    };
    if parent.kind() == "decorated_definition" {
        if !scope_step() {
            return None;
        }
        let Some(grandparent) = parent.parent() else {
            return Some(false);
        };
        parent = grandparent;
    }
    Some(parent.kind() == "module")
}

fn collect_direct_identifier_names(
    node: Node<'_>,
    source: &str,
    scope_step: &mut impl FnMut() -> bool,
    mut record: impl FnMut(&str),
) -> Option<()> {
    for child in named_children_bounded(node, scope_step)? {
        if child.kind() == "identifier" {
            let name = node_text(child, source);
            if !name.is_empty() {
                record(name);
            }
        }
    }
    Some(())
}

fn collect_import_bindings<'tree>(
    statement: Node<'tree>,
    scope_step: &mut impl FnMut() -> bool,
    mut record: impl FnMut(Node<'tree>),
) -> Option<()> {
    let mut cursor = statement.walk();
    let mut imports = Vec::new();
    for imported in statement.children_by_field_name("name", &mut cursor) {
        if !scope_step() {
            return None;
        }
        imports.push(imported);
    }
    for imported in imports {
        if let Some(alias) = imported.child_by_field_name("alias") {
            record(alias);
            continue;
        }
        let name = imported.child_by_field_name("name").unwrap_or(imported);
        let binding = if statement.kind() == "import_statement" {
            first_identifier_bounded(name, scope_step)?
        } else {
            last_identifier_bounded(name, scope_step)?
        };
        if let Some(binding) = binding {
            record(binding);
        }
    }
    Some(())
}

fn first_identifier_bounded<'tree>(
    root: Node<'tree>,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<Option<Node<'tree>>> {
    let mut stack = vec![root];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        if node.kind() == "identifier" {
            return Some(Some(node));
        }
        let children = named_children_bounded(node, scope_step)?;
        stack.extend(children.into_iter().rev());
    }
    Some(None)
}

fn last_identifier_bounded<'tree>(
    root: Node<'tree>,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<Option<Node<'tree>>> {
    let mut result = None;
    let mut stack = vec![root];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        if node.kind() == "identifier" {
            result = Some(node);
            continue;
        }
        let children = named_children_bounded(node, scope_step)?;
        stack.extend(children.into_iter().rev());
    }
    Some(result)
}

fn collect_binding_targets<'tree>(
    target: Node<'tree>,
    source: &str,
    scope_step: &mut impl FnMut() -> bool,
    mut record: impl FnMut(&str, Node<'tree>),
) -> Option<()> {
    let mut stack = vec![target];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        match node.kind() {
            // These mutate an existing object and do not bind either the
            // receiver or member name in the function.
            "attribute" | "subscript" => continue,
            "identifier" | "keyword_identifier" => {
                let name = node_text(node, source);
                if !name.is_empty() {
                    record(name, node);
                }
                continue;
            }
            _ => {}
        }
        let children = named_children_bounded(node, scope_step)?;
        if node.kind() == "as_pattern_target" && children.is_empty() {
            let name = node_text(node, source);
            if !name.is_empty() {
                record(name, node);
            }
            continue;
        }
        stack.extend(children.into_iter().rev());
    }
    Some(())
}

fn collect_match_pattern_bindings<'tree>(
    pattern: Node<'tree>,
    source: &str,
    scope_step: &mut impl FnMut() -> bool,
    mut record: impl FnMut(&str, Node<'tree>),
) -> Option<()> {
    let mut stack = vec![pattern];
    while let Some(node) = stack.pop() {
        if !scope_step() {
            return None;
        }
        match node.kind() {
            "dotted_name" => {
                let identifiers = named_children_bounded(node, scope_step)?
                    .into_iter()
                    .filter(|child| child.kind() == "identifier")
                    .collect::<Vec<_>>();
                if let [binding] = identifiers.as_slice() {
                    let name = node_text(*binding, source);
                    if !name.is_empty() {
                        record(name, *binding);
                    }
                }
                continue;
            }
            "splat_pattern" => {
                for child in named_children_bounded(node, scope_step)? {
                    if child.kind() == "identifier" {
                        let name = node_text(child, source);
                        if !name.is_empty() {
                            record(name, child);
                        }
                    }
                }
                continue;
            }
            "class_pattern" => {
                let mut children = named_children_bounded(node, scope_step)?;
                if children
                    .first()
                    .is_some_and(|child| child.kind() == "dotted_name")
                {
                    children.remove(0);
                }
                stack.extend(children.into_iter().rev());
                continue;
            }
            "keyword_pattern" => {
                let mut children = named_children_bounded(node, scope_step)?;
                if children
                    .first()
                    .is_some_and(|child| child.kind() == "identifier")
                {
                    children.remove(0);
                }
                stack.extend(children.into_iter().rev());
                continue;
            }
            "dict_pattern" => {
                let key_ids = children_by_field_name_bounded(node, "key", scope_step)?
                    .into_iter()
                    .map(|key| key.id())
                    .collect::<HashSet<_>>();
                let children = named_children_bounded(node, scope_step)?;
                stack.extend(
                    children
                        .into_iter()
                        .filter(|child| !key_ids.contains(&child.id()))
                        .rev(),
                );
                continue;
            }
            "as_pattern" => {
                if let Some(alias) = node.child_by_field_name("alias") {
                    collect_binding_targets(alias, source, scope_step, &mut record)?;
                    let children = named_children_bounded(node, scope_step)?;
                    stack.extend(
                        children
                            .into_iter()
                            .filter(|child| child.id() != alias.id())
                            .rev(),
                    );
                    continue;
                }
                let mut children = named_children_bounded(node, scope_step)?;
                if let Some(alias) = children
                    .last()
                    .copied()
                    .filter(|child| child.kind() == "identifier")
                {
                    let name = node_text(alias, source);
                    if !name.is_empty() {
                        record(name, alias);
                    }
                    children.pop();
                }
                stack.extend(children.into_iter().rev());
                continue;
            }
            "identifier" => {
                // Direct identifiers are match `as` aliases handled by their
                // parent. Keyword names and class heads are likewise skipped.
                continue;
            }
            kind if is_pattern_literal(kind) => continue,
            _ => {}
        }
        let children = named_children_bounded(node, scope_step)?;
        stack.extend(children.into_iter().rev());
    }
    Some(())
}

fn push_named_children<'tree>(
    stack: &mut Vec<ScanFrame<'tree>>,
    node: Node<'tree>,
    in_comprehension: bool,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<()> {
    for child in named_children_bounded(node, scope_step)?.into_iter().rev() {
        stack.push(ScanFrame {
            node: child,
            in_comprehension,
        });
    }
    Some(())
}

fn push_named_children_except<'tree>(
    stack: &mut Vec<ScanFrame<'tree>>,
    node: Node<'tree>,
    excluded: Node<'tree>,
    in_comprehension: bool,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<()> {
    for child in named_children_bounded(node, scope_step)?
        .into_iter()
        .filter(|child| child.id() != excluded.id())
        .rev()
    {
        stack.push(ScanFrame {
            node: child,
            in_comprehension,
        });
    }
    Some(())
}

fn push_nested_scope_header_children<'tree>(
    stack: &mut Vec<ScanFrame<'tree>>,
    node: Node<'tree>,
    in_comprehension: bool,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<()> {
    let body = node.child_by_field_name("body").map(|child| child.id());
    let name = node.child_by_field_name("name").map(|child| child.id());
    for child in named_children_bounded(node, scope_step)?
        .into_iter()
        .filter(|child| Some(child.id()) != body && Some(child.id()) != name)
        .rev()
    {
        stack.push(ScanFrame {
            node: child,
            in_comprehension,
        });
    }
    Some(())
}

fn named_children_bounded<'tree>(
    node: Node<'tree>,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<Vec<Node<'tree>>> {
    let mut cursor = node.walk();
    let mut children = Vec::new();
    for child in node.named_children(&mut cursor) {
        if !scope_step() {
            return None;
        }
        children.push(child);
    }
    Some(children)
}

fn children_by_field_name_bounded<'tree>(
    node: Node<'tree>,
    field: &str,
    scope_step: &mut impl FnMut() -> bool,
) -> Option<Vec<Node<'tree>>> {
    let mut cursor = node.walk();
    let mut children = Vec::new();
    for child in node.children_by_field_name(field, &mut cursor) {
        if !scope_step() {
            return None;
        }
        children.push(child);
    }
    Some(children)
}

fn is_comprehension(kind: &str) -> bool {
    matches!(
        kind,
        "list_comprehension"
            | "set_comprehension"
            | "dictionary_comprehension"
            | "generator_expression"
    )
}

fn is_pattern_literal(kind: &str) -> bool {
    matches!(
        kind,
        "string"
            | "concatenated_string"
            | "integer"
            | "float"
            | "complex_pattern"
            | "true"
            | "false"
            | "none"
    )
}

fn node_text<'a>(node: Node<'_>, source: &'a str) -> &'a str {
    brokk_bifrost_core::analyzer::common::node_source_text_trimmed(node, source)
}

#[cfg(test)]
mod tests {
    #[test]
    fn only_the_first_comprehension_iterable_uses_the_enclosing_scope() {
        let source = "def run(first, second):\n    return [second for first in first for second in second]\n";
        let mut parser = tree_sitter::Parser::new();
        parser
            .set_language(&tree_sitter_python::LANGUAGE.into())
            .unwrap();
        let tree = parser.parse(source, None).unwrap();
        let mut stack = vec![tree.root_node()];
        let comprehension = loop {
            let node = stack.pop().expect("fixture contains a comprehension");
            if node.kind() == "list_comprehension" {
                break node;
            }
            let mut cursor = node.walk();
            stack.extend(node.named_children(&mut cursor));
        };
        let mut cursor = comprehension.walk();
        let clauses = comprehension
            .named_children(&mut cursor)
            .filter(|node| node.kind() == "for_in_clause")
            .collect::<Vec<_>>();
        let outer = clauses[0].child_by_field_name("right").unwrap();
        let inner = clauses[1].child_by_field_name("right").unwrap();
        assert!(!super::python_comprehension_binds_name_at(
            "first", outer, source
        ));
        assert!(super::python_comprehension_binds_name_at(
            "second", inner, source
        ));
    }
}