sightline-ty-python-core 0.1.0

#![warn(
    clippy::disallowed_methods,
    reason = "Prefer System trait methods over std methods in ty crates"
)]
use ruff_python_ast as ast;
use std::iter::{FusedIterator, once};
use std::sync::Arc;

use ruff_db::parsed::parsed_module;

use ruff_index::{FrozenIndexVec, IndexSlice};
use ruff_python_ast::NodeIndex;
use ruff_python_parser::semantic_errors::SemanticSyntaxError;
use ruff_text_size::TextRange;
use rustc_hash::{FxHashMap, FxHashSet};
use salsa::plumbing::AsId;
use smallvec::SmallVec;
use ty_module_resolver::ModuleName;

use crate::frozen::{FrozenMap, FrozenSet};
use crate::place::ScopedPlaceId;
pub use crate::statement::{Statement, StatementNodeKey};
use ast_ids::AstIds;
pub use ast_ids::ExpressionNodeKey;
use builder::SemanticIndexBuilder;
use definition::{Definition, DefinitionNodeKey, Definitions};
use expression::Expression;
use narrowing_constraints::ScopedNarrowingConstraint;
pub use place::{PlaceExprRef, PlaceTable};
pub use reachability_constraints::ReachabilityConstraintsBuilder;
pub use scope::FileScopeId;
use scope::{NodeWithScopeKey, NodeWithScopeRef, Scope, ScopeId, ScopeKind, ScopeLaziness};
use symbol::ScopedSymbolId;
pub use use_def::{
    ApplicableConstraints, BindingWithConstraints, BindingWithConstraintsIterator,
    DeclarationWithConstraint, DeclarationsIterator, LiveBinding, LoopHeaderId, NarrowingEvaluator,
    PredicateNarrowingTargets, ScopedDefinitionId, UseDefMap,
};
use use_def::{EnclosingSnapshotKey, ScopedEnclosingSnapshotId};

pub mod ast_ids;
pub mod ast_node_ref;
mod builder;
mod db;
pub mod definition;
pub mod expression;
pub mod frozen;
pub(crate) mod member;
pub mod narrowing_constraints;
pub mod node_key;
pub mod place;
pub mod platform;
pub mod predicate;
pub mod rank;
mod re_exports;
pub mod reachability_constraints;
pub mod scope;
pub mod statement;
pub mod symbol;
pub mod unpack;
mod use_def;
pub use db::Db;
#[cfg(any(test, feature = "testing"))]
pub use db::TestProgramDb;
pub mod program;
pub mod program_file;
pub use program::Program;
pub use program_file::ProgramFile;

/// Returns the semantic index for `file`.
///
/// Prefer using [`symbol_table`] when working with symbols from a single scope.
#[salsa::tracked(returns(ref), no_eq, heap_size=ruff_memory_usage::heap_size)]
pub fn semantic_index<'db>(db: &'db dyn Db, file: ProgramFile<'db>) -> SemanticIndex<'db> {
    let _span = tracing::trace_span!("semantic_index", ?file).entered();

    let module = parsed_module(db, file.python_file(db)).load(db);

    SemanticIndexBuilder::new(db, file, &module).build()
}

/// Returns the place table for a specific `scope`.
///
/// Using [`place_table`] over [`semantic_index`] has the advantage that
/// Salsa can avoid invalidating dependent queries if this scope's place table
/// is unchanged.
#[salsa::tracked(returns(deref), heap_size=ruff_memory_usage::heap_size)]
pub fn place_table<'db>(db: &'db dyn Db, scope: ScopeId<'db>) -> Arc<PlaceTable> {
    let program_file = scope.program_file(db);
    let _span = tracing::trace_span!("place_table", scope=?scope.as_id(), ?program_file).entered();
    let index = semantic_index(db, program_file);
    Arc::clone(&index.place_tables[scope.file_scope_id(db)])
}

/// Returns the use-def map for a specific `scope`.
///
/// Using [`use_def_map`] over [`semantic_index`] has the advantage that
/// Salsa can avoid invalidating dependent queries if this scope's use-def map
/// is unchanged.
#[salsa::tracked(returns(deref), heap_size=ruff_memory_usage::heap_size)]
pub fn use_def_map<'db>(db: &'db dyn Db, scope: ScopeId<'db>) -> Arc<UseDefMap<'db>> {
    let program_file = scope.program_file(db);
    let _span = tracing::trace_span!("use_def_map", scope=?scope.as_id(), ?program_file).entered();
    let index = semantic_index(db, program_file);
    Arc::clone(&index.use_def_maps[scope.file_scope_id(db)])
}

/// All the bindings made in a loop, which are visible to the entire loop via "loop header
/// definitions" (a.k.a. loop-back bindings)
///
/// Loop control flow analysis needs a way for uses early in the loop to see bindings that come
/// later, reflecting the fact that a previous iteration of the loop might've already executed
/// those bindings. For example:
///
/// ```py
/// x = "A"
/// while some_condition():
///     # The loop entry value (in the first iteration) and the following binding (in other
///     # iterations) are both visible at this use.
///     reveal_type(x)  # revealed: Literal["A", "B"]
///     x = "B"
/// ```
///
/// As an important special case, these loop header definitions also combine with fixpoint
/// iteration to let us infer `int` for loop variables. For example:
///
/// ```py
/// i = 0  # revealed: Literal[0]
/// while i < 1_000_000:
///     i += 1  # revealed: int
/// ```
///
/// The add-assign statement `i += 1` is both a use and a binding. The use sees the `i = 0` binding
/// at the top, and it also sees *itself* via the loop header definition of `i`. When we infer the
/// type of `i` in or after the loop, fixpoint iteration produces an ever-expanding union of
/// literals (`Literal[0, 1, 2, ...]`) until we eventually reach the threshold for widening to
/// `int` and stop iterating. (See `should_widen` and `widen_literal_types`.)
///
/// Loop header definitions are synthesized before walking the loop body, but the bindings in the
/// header are only known after walking all loop-back edges. The builder reserves a [`LoopHeaderId`]
/// before the walk, fills the corresponding header afterward, and publishes the completed headers
/// in the scope's [`UseDefMap`].
#[derive(Debug, Clone, Default, PartialEq, Eq, get_size2::GetSize)]
pub struct LoopHeader {
    bindings: FxHashMap<ScopedPlaceId, SmallVec<[LiveBinding; 1]>>,
}

impl LoopHeader {
    fn new() -> Self {
        Self {
            bindings: FxHashMap::default(),
        }
    }

    fn add_binding(&mut self, place: ScopedPlaceId, binding: LiveBinding) {
        self.bindings.entry(place).or_default().push(binding);
    }

    pub fn bindings_for_place(
        &self,
        place: ScopedPlaceId,
    ) -> impl Iterator<Item = LiveBinding> + '_ {
        self.bindings
            .get(&place)
            .map(|v: &SmallVec<[LiveBinding; 1]>| v.iter().copied())
            .into_iter()
            .flatten()
    }
}

/// Returns all attribute assignments as scope IDs for a specific class body scope.
///
/// Only call this when doing type inference on the same file as `class_body_scope`, otherwise it
/// introduces a direct dependency on that file's AST.
pub fn attribute_scopes<'db>(
    db: &'db dyn Db,
    class_body_scope: ScopeId<'db>,
) -> impl Iterator<Item = FileScopeId> + 'db {
    let index = semantic_index(db, class_body_scope.program_file(db));
    let class_scope_id = class_body_scope.file_scope_id(db);
    ChildrenIter::new(&index.scopes, class_scope_id)
        .filter_map(move |(child_scope_id, scope)| {
            let (function_scope_id, function_scope) =
                if scope.node().scope_kind() == ScopeKind::TypeParams {
                    // This could be a generic method with a type-params scope.
                    // Go one level deeper to find the function scope. The first
                    // descendant is the (potential) function scope.
                    let function_scope_id = scope.descendants().start;
                    (function_scope_id, index.scope(function_scope_id))
                } else {
                    (child_scope_id, scope)
                };
            function_scope.node().as_function()?;
            Some(function_scope_id)
        })
        .flat_map(move |func_id| {
            // Add any descendent scope that is eager and have eager scopes between the scope
            // and the method scope. Since attributes can be defined in this scope.
            let nested = index.descendent_scopes(func_id).filter_map(move |(id, s)| {
                let is_eager = s.kind().is_eager();
                let parents_are_eager = {
                    let mut all_parents_eager = true;
                    let mut current = Some(id);

                    while let Some(scope_id) = current {
                        if scope_id == func_id {
                            break;
                        }
                        let scope = index.scope(scope_id);
                        if !scope.is_eager() {
                            all_parents_eager = false;
                            break;
                        }
                        current = scope.parent();
                    }

                    all_parents_eager
                };

                (parents_are_eager && is_eager).then_some(id)
            });
            once(func_id).chain(nested)
        })
}

/// Returns the module global scope of `file`.
#[salsa::tracked(returns(copy), heap_size=ruff_memory_usage::heap_size)]
pub fn global_scope<'db>(db: &'db dyn Db, file: ProgramFile<'db>) -> ScopeId<'db> {
    let _span = tracing::trace_span!("global_scope", ?file).entered();

    FileScopeId::global().to_scope_id(db, file)
}

pub enum EnclosingSnapshotResult<'map, 'db> {
    FoundConstraint(ScopedNarrowingConstraint),
    FoundBindings(BindingWithConstraintsIterator<'map, 'db>),
    NotFound,
    NoLongerInEagerContext,
}

#[derive(Debug, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
struct DefinitionsByNode<'db> {
    single: FrozenMap<DefinitionNodeKey, Definition<'db>>,
    non_single: FrozenMap<DefinitionNodeKey, Box<[Definition<'db>]>>,
}

impl<'db> DefinitionsByNode<'db> {
    fn from_map(definitions_by_node: FxHashMap<DefinitionNodeKey, Definitions<'db>>) -> Self {
        let single_count = definitions_by_node
            .values()
            .filter(|definitions| definitions.len() == 1)
            .count();
        let mut single = Vec::with_capacity(single_count);
        let mut non_single = Vec::with_capacity(definitions_by_node.len() - single_count);

        #[expect(
            clippy::iter_over_hash_type,
            reason = "each node is independently partitioned by definition count"
        )]
        for (key, definitions) in definitions_by_node {
            if definitions.len() == 1 {
                single.push((key, definitions[0]));
            } else {
                non_single.push((key, definitions.into_boxed_slice()));
            }
        }

        Self {
            single: FrozenMap::from_entries(single),
            non_single: FrozenMap::from_entries(non_single),
        }
    }

    fn get(&self, key: DefinitionNodeKey) -> Option<&[Definition<'db>]> {
        self.single
            .get(&key)
            .map(std::slice::from_ref)
            .or_else(|| self.non_single.get(&key).map(AsRef::as_ref))
    }
}

/// The place tables and use-def maps for all scopes in a file.
#[derive(Debug, get_size2::GetSize, salsa::SalsaValue)]
pub struct SemanticIndex<'db> {
    /// List of all place tables in this file, indexed by scope.
    place_tables: FrozenIndexVec<FileScopeId, Arc<PlaceTable>>,

    /// List of all scopes in this file.
    scopes: FrozenIndexVec<FileScopeId, Scope>,

    /// Map expressions to their corresponding scope.
    scopes_by_expression: ExpressionsScopeMap,

    /// Map from a node creating a definition to its definition.
    definitions_by_node: DefinitionsByNode<'db>,

    /// Map from a standalone expression to its [`Expression`] ingredient.
    expressions_by_node: FxHashMap<ExpressionNodeKey, Expression<'db>>,

    /// Map from an unpacking target to its [`unpack::Unpack`] ingredient.
    unpacks_by_target: FrozenMap<ExpressionNodeKey, unpack::Unpack<'db>>,

    /// Map from a standalone statement to its [`Statement`] ingredient.
    statements_by_node: FxHashMap<StatementNodeKey, Statement<'db>>,

    /// Map from nodes that create a scope to the scope they create.
    scopes_by_node: FxHashMap<NodeWithScopeKey, FileScopeId>,

    /// Map from a lambda expression to its containing statement.
    enclosing_lambda_statements: FrozenMap<ExpressionNodeKey, Statement<'db>>,

    // Map from a constraining use of a collection initializer to its definition.
    collections_by_use: FrozenMap<ExpressionNodeKey, Definition<'db>>,

    // Map from a collection initializer definition to statements containing a constraining use.
    uses_by_collection: FrozenMap<Definition<'db>, Box<[(Statement<'db>, ExpressionNodeKey)]>>,

    /// Map from the file-local [`FileScopeId`] to the salsa-ingredient [`ScopeId`].
    scope_ids_by_scope: FrozenIndexVec<FileScopeId, ScopeId<'db>>,

    /// Use-def map for each scope in this file.
    use_def_maps: FrozenIndexVec<FileScopeId, Arc<UseDefMap<'db>>>,

    /// Lookup table to map between node ids and ast nodes.
    ///
    /// Note: We should not depend on this map when analysing other files or
    /// changing a file invalidates all dependents.
    ast_ids: AstIds,

    /// The set of modules that are imported anywhere within this file.
    imported_modules: FrozenSet<ModuleName>,

    /// Flags about the global scope (code usage impacting inference)
    has_future_annotations: bool,

    /// Map of all of the enclosing snapshots that appear in this file.
    enclosing_snapshots: FrozenMap<EnclosingSnapshotKey, ScopedEnclosingSnapshotId>,

    /// List of all semantic syntax errors in this file.
    semantic_syntax_errors: Vec<SemanticSyntaxError>,

    /// Set of all generator functions in this file.
    generator_functions: FrozenSet<FileScopeId>,

    /// Set of all asynchronous comprehensions in this file.
    async_comprehensions: FrozenSet<FileScopeId>,

    /// Narrowing alias metadata for predicate leaf names.
    /// When a predicate references an alias variable (e.g., `is_none` from `is_none = x is None`),
    /// the alias Name node is mapped to its aliased expression for constraint-generation time.
    narrowing_alias_predicates: FrozenMap<ExpressionNodeKey, NarrowingAliasPredicate<'db>>,
}

#[derive(Debug, Clone, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
pub struct NarrowingAliasPredicate<'db> {
    /// Aliased expression, e.g., `x is None` in `is_none = x is None`.
    pub expression: Expression<'db>,
}

impl<'db> SemanticIndex<'db> {
    /// Returns the place table for a specific scope.
    ///
    /// Use the Salsa cached [`place_table()`] query if you only need the
    /// place table for a single scope.
    #[track_caller]
    pub fn place_table(&self, scope_id: FileScopeId) -> &PlaceTable {
        &self.place_tables[scope_id]
    }

    /// Returns alias metadata for an alias Name node in a predicate, if one exists.
    pub fn narrowing_alias_predicate(
        &self,
        key: impl Into<ExpressionNodeKey>,
    ) -> Option<&NarrowingAliasPredicate<'db>> {
        self.narrowing_alias_predicates.get(&key.into())
    }

    /// Returns the use-def map for a specific scope.
    ///
    /// Use the Salsa cached [`use_def_map()`] query if you only need the
    /// use-def map for a single scope.
    #[track_caller]
    pub fn use_def_map(&self, scope_id: FileScopeId) -> &UseDefMap<'db> {
        &self.use_def_maps[scope_id]
    }

    /// Returns the set of modules that are imported anywhere in this file.
    ///
    /// This set only considers `import` statements, not `from...import` statements.
    /// See `ModuleLiteralType::available_submodule_attributes` for discussion
    /// of why this analysis is intentionally limited.
    pub fn imported_modules(&self) -> impl Iterator<Item = &ModuleName> {
        self.imported_modules.iter()
    }

    #[track_caller]
    fn ast_ids(&self) -> &AstIds {
        &self.ast_ids
    }

    /// Returns the ID of the `expression`'s enclosing scope.
    #[track_caller]
    pub fn expression_scope_id<E>(&self, expression: &E) -> FileScopeId
    where
        E: HasTrackedScope,
    {
        self.try_expression_scope_id(expression)
            .expect("Expression to be part of a scope if it is from the same module")
    }

    /// Returns the ID of the `expression`'s enclosing scope.
    pub fn try_expression_scope_id<E>(&self, expression: &E) -> Option<FileScopeId>
    where
        E: HasTrackedScope,
    {
        self.scopes_by_expression.try_get(expression)
    }

    /// Returns the [`Scope`] of the `expression`'s enclosing scope.
    #[allow(unused)]
    #[track_caller]
    pub fn expression_scope(&self, expression: &impl HasTrackedScope) -> &Scope {
        &self.scopes[self.expression_scope_id(expression)]
    }

    /// Returns the [`Scope`] with the given id.
    #[track_caller]
    pub fn scope(&self, id: FileScopeId) -> &Scope {
        &self.scopes[id]
    }

    pub fn scope_ids(&self) -> impl Iterator<Item = ScopeId<'db>> + '_ {
        self.scope_ids_by_scope.iter().copied()
    }

    pub fn symbol_is_global_in_scope(&self, symbol: ScopedSymbolId, scope: FileScopeId) -> bool {
        self.place_table(scope).symbol(symbol).is_global()
    }

    /// Returns `true` if the given symbol in the given scope resolves to the global scope, either
    /// because:
    ///
    /// 1. The given scope *is* the global scope.
    /// 2. The symbol is explicitly declared `global` in the given scope.
    /// 3. The symbol is a free variable in the given scope, and no enclosing function scope
    ///    defines it.
    ///
    /// The third case requires walking ancestor scopes until we encounter either a binding or a
    /// `nonlocal` declaration (those aren't allowed to resolve to the global scope, so we don't
    /// need to chase them).
    pub fn symbol_resolves_to_global_scope(
        &self,
        symbol: ScopedSymbolId,
        scope: FileScopeId,
    ) -> bool {
        let symbol = self.place_table(scope).symbol(symbol);
        let name = symbol.name();
        // Note that `visible_ancestor_scopes` includes the starting scope itself.
        for (visible_scope_id, _) in self.visible_ancestor_scopes(scope) {
            if visible_scope_id.is_global() {
                // We return `true` here even if the global variable isn't actually defined. That
                // case will be probably a diagnostic elsewhere.
                return true;
            }
            let place_table = self.place_table(visible_scope_id);
            let Some(visible_symbol_id) = place_table.symbol_id(name) else {
                continue;
            };
            let visible_symbol = place_table.symbol(visible_symbol_id);
            if visible_symbol.is_global() {
                return true;
            }
            if visible_symbol.is_local() || visible_symbol.is_nonlocal() {
                return false;
            }
        }
        unreachable!("should return true at the global scope above");
    }

    /// Returns the id of the parent scope.
    pub fn parent_scope_id(&self, scope_id: FileScopeId) -> Option<FileScopeId> {
        let scope = self.scope(scope_id);
        scope.parent()
    }

    /// Returns the parent scope of `scope_id`.
    #[track_caller]
    pub fn parent_scope(&self, scope_id: FileScopeId) -> Option<&Scope> {
        Some(&self.scopes[self.parent_scope_id(scope_id)?])
    }

    /// Return the [`Definition`] of the class enclosing this method, given the
    /// method's body scope, or `None` if it is not a method.
    pub fn class_definition_of_method(
        &self,
        function_body_scope: FileScopeId,
    ) -> Option<Definition<'db>> {
        let current_scope = self.scope(function_body_scope);
        if current_scope.kind() != ScopeKind::Function {
            return None;
        }
        let parent_scope_id = current_scope.parent()?;
        let parent_scope = self.scope(parent_scope_id);

        let class_scope = match parent_scope.kind() {
            ScopeKind::Class => parent_scope,
            ScopeKind::TypeParams => {
                let class_scope_id = parent_scope.parent()?;
                let potentially_class_scope = self.scope(class_scope_id);

                match potentially_class_scope.kind() {
                    ScopeKind::Class => potentially_class_scope,
                    _ => return None,
                }
            }
            _ => return None,
        };

        class_scope
            .node()
            .as_class()
            .map(|node_ref| self.expect_single_definition(node_ref))
    }

    pub fn enclosing_lambda_statement(&self, lambda: ExpressionNodeKey) -> Option<Statement<'db>> {
        self.enclosing_lambda_statements.get(&lambda).copied()
    }

    /// If this is a potentially constraining use of an unannotated collection initializer, returns
    /// its definition.
    pub fn unannotated_collection_initializer(
        &self,
        collection_use: &ast::Expr,
    ) -> Option<Definition<'db>> {
        self.collections_by_use.get(&collection_use.into()).copied()
    }

    /// Returns all potentially constraining uses of the given unannotated collection initializer.
    pub fn constraining_collection_uses(
        &self,
        collection_def: Definition<'db>,
    ) -> impl Iterator<Item = (Statement<'db>, ExpressionNodeKey)> {
        self.uses_by_collection
            .get(&collection_def)
            .into_iter()
            .flat_map(|uses| uses.iter().copied())
    }

    pub fn is_in_type_checking_block(&self, scope_id: FileScopeId, range: TextRange) -> bool {
        self.ancestor_scopes(scope_id).any(|(scope_id, _)| {
            self.use_def_map(scope_id)
                .is_range_in_type_checking_block(range)
        })
    }

    /// Returns an iterator over the descendent scopes of `scope`.
    fn descendent_scopes(&self, scope: FileScopeId) -> DescendantsIter<'_> {
        DescendantsIter::new(&self.scopes, scope)
    }

    /// Returns an iterator over the direct child scopes of `scope`.
    pub fn child_scopes(&self, scope: FileScopeId) -> ChildrenIter<'_> {
        ChildrenIter::new(&self.scopes, scope)
    }

    /// Returns an iterator over all ancestors of `scope`, starting with `scope` itself.
    pub fn ancestor_scopes(&self, scope: FileScopeId) -> AncestorsIter<'_> {
        AncestorsIter::new(&self.scopes, scope)
    }

    /// Returns an iterator over ancestors of `scope` that are visible for name resolution,
    /// starting with `scope` itself. This follows Python's lexical scoping rules where
    /// class scopes are skipped during name resolution (except for the starting scope
    /// if it happens to be a class scope).
    ///
    /// For example, in this code:
    /// ```python
    /// x = 1
    /// class A:
    ///     x = 2
    ///     def method(self):
    ///         print(x)  # Refers to global x=1, not class x=2
    /// ```
    /// The `method` function can see the global scope but not the class scope.
    pub fn visible_ancestor_scopes(&self, scope: FileScopeId) -> VisibleAncestorsIter<'_> {
        VisibleAncestorsIter::new(&self.scopes, scope)
    }

    /// Returns the [`definition::Definition`] salsa ingredient(s) for `definition_key`.
    ///
    /// There will only ever be >1 `Definition` associated with a `definition_key`
    /// if the definitions are created by a wildcard (`*`) import.
    #[track_caller]
    pub fn definitions(&self, definition_key: impl Into<DefinitionNodeKey>) -> &[Definition<'db>] {
        self.definitions_by_node
            .get(definition_key.into())
            .expect("definition should be present in the semantic index")
    }

    /// Returns the [`definition::Definition`] salsa ingredient(s) for `definition_node`, if any.
    pub fn try_definitions(
        &self,
        definition_node: ast::AnyNodeRef<'_>,
    ) -> Option<&[Definition<'db>]> {
        let definition_key = DefinitionNodeKey::from_node_ref(definition_node);
        self.definitions_by_node.get(definition_key)
    }

    /// Returns the [`definition::Definition`] salsa ingredient for `definition_key`.
    ///
    /// ## Panics
    ///
    /// If the number of definitions associated with the key is not exactly 1 and
    /// the `debug_assertions` feature is enabled, this method will panic.
    ///
    /// It is generally safe to use this method for any AST node that does not
    /// correspond to a `*` (wildcard) import, since those are the only situations
    /// that can result in multiple definitions being associated with a single AST
    /// node.
    #[track_caller]
    pub fn expect_single_definition(
        &self,
        definition_key: impl Into<DefinitionNodeKey> + std::fmt::Debug + Copy,
    ) -> Definition<'db> {
        let definitions = self.definitions(definition_key);
        debug_assert_eq!(
            definitions.len(),
            1,
            "Expected exactly one definition to be associated with AST node {definition_key:?} but found {}",
            definitions.len()
        );
        definitions[0]
    }

    pub fn try_definition(
        &self,
        definition_key: impl Into<DefinitionNodeKey>,
    ) -> Option<Definition<'db>> {
        self.definitions_by_node
            .single
            .get(&definition_key.into())
            .copied()
    }

    /// Returns the [`Expression`] ingredient for an expression node.
    /// Panics if we have no expression ingredient for that node. We can only call this method for
    /// standalone-inferable expressions, which we call `add_standalone_expression` for in
    /// `SemanticIndexBuilder`.
    #[track_caller]
    pub fn expression(&self, expression_key: impl Into<ExpressionNodeKey>) -> Expression<'db> {
        self.expressions_by_node[&expression_key.into()]
    }

    pub fn try_expression(
        &self,
        expression_key: impl Into<ExpressionNodeKey>,
    ) -> Option<Expression<'db>> {
        self.expressions_by_node
            .get(&expression_key.into())
            .copied()
    }

    /// Returns the [`unpack::Unpack`] ingredient for an unpacking target, if any.
    pub fn try_unpack(&self, target: impl Into<ExpressionNodeKey>) -> Option<unpack::Unpack<'db>> {
        self.unpacks_by_target.get(&target.into()).copied()
    }

    pub fn is_standalone_expression(&self, expression_key: impl Into<ExpressionNodeKey>) -> bool {
        self.expressions_by_node
            .contains_key(&expression_key.into())
    }

    pub fn try_statement(
        &self,
        statement_key: impl Into<StatementNodeKey>,
    ) -> Option<Statement<'db>> {
        self.statements_by_node.get(&statement_key.into()).copied()
    }

    /// Returns the id of the scope that `node` creates.
    /// This is different from [`definition::Definition::scope`] which
    /// returns the scope in which that definition is defined in.
    #[track_caller]
    pub fn node_scope(&self, node: NodeWithScopeRef) -> FileScopeId {
        self.scopes_by_node[&node.node_key()]
    }

    /// Returns the id of the scope that `node` creates, if it exists.
    pub fn try_node_scope(&self, node: NodeWithScopeRef) -> Option<FileScopeId> {
        self.scopes_by_node.get(&node.node_key()).copied()
    }

    /// Returns the id of the scope that the node identified by `key` creates.
    ///
    /// This is useful when you have a [`NodeWithScopeKey`] constructed from an
    /// [`AstNodeRef`](crate::ast_node_ref::AstNodeRef) and want to avoid loading
    /// the parsed module just to look up the scope.
    pub fn node_scope_by_key(&self, key: NodeWithScopeKey) -> FileScopeId {
        self.scopes_by_node[&key]
    }

    /// Checks if there is an import of `__future__.annotations` in the global scope, which affects
    /// the logic for type inference.
    pub fn has_future_annotations(&self) -> bool {
        self.has_future_annotations
    }

    /// Returns
    /// * `NoLongerInEagerContext` if the nested scope is no longer in an eager context
    ///   (that is, not every scope that will be traversed is eager) and no lazy snapshots were found.
    /// *  an iterator of bindings for a particular nested scope reference if the bindings exist.
    /// *  a narrowing constraint if there are no bindings, but there is a narrowing constraint for an enclosing scope place.
    /// * `NotFound` if the narrowing constraint / bindings do not exist in the nested scope.
    pub fn enclosing_snapshot(
        &self,
        enclosing_scope: FileScopeId,
        expr: PlaceExprRef,
        nested_scope: FileScopeId,
    ) -> EnclosingSnapshotResult<'_, 'db> {
        for (ancestor_scope_id, ancestor_scope) in self.ancestor_scopes(nested_scope) {
            if ancestor_scope_id == enclosing_scope {
                break;
            }
            if !ancestor_scope.is_eager() {
                if let PlaceExprRef::Symbol(symbol) = expr
                    && let Some(place_id) =
                        self.place_tables[enclosing_scope].symbol_id(symbol.name())
                {
                    let key = EnclosingSnapshotKey {
                        enclosing_scope,
                        enclosing_place: place_id.into(),
                        nested_scope,
                        nested_laziness: ScopeLaziness::Lazy,
                    };
                    if let Some(id) = self.enclosing_snapshots.get(&key) {
                        return self.use_def_maps[enclosing_scope]
                            .enclosing_snapshot(*id, key.nested_laziness);
                    }
                }
                return EnclosingSnapshotResult::NoLongerInEagerContext;
            }
        }
        let Some(place_id) = self.place_tables[enclosing_scope].place_id(expr) else {
            return EnclosingSnapshotResult::NotFound;
        };
        let key = EnclosingSnapshotKey {
            enclosing_scope,
            enclosing_place: place_id,
            nested_scope,
            nested_laziness: ScopeLaziness::Eager,
        };
        let Some(id) = self.enclosing_snapshots.get(&key) else {
            return EnclosingSnapshotResult::NotFound;
        };
        self.use_def_maps[enclosing_scope].enclosing_snapshot(*id, key.nested_laziness)
    }

    pub fn semantic_syntax_errors(&self) -> &[SemanticSyntaxError] {
        &self.semantic_syntax_errors
    }
}

pub struct AncestorsIter<'a> {
    scopes: &'a IndexSlice<FileScopeId, Scope>,
    next_id: Option<FileScopeId>,
}

impl<'a> AncestorsIter<'a> {
    fn new(scopes: &'a IndexSlice<FileScopeId, Scope>, start: FileScopeId) -> Self {
        Self {
            scopes,
            next_id: Some(start),
        }
    }
}

impl<'a> Iterator for AncestorsIter<'a> {
    type Item = (FileScopeId, &'a Scope);

    fn next(&mut self) -> Option<Self::Item> {
        let current_id = self.next_id?;
        let current = &self.scopes[current_id];
        self.next_id = current.parent();

        Some((current_id, current))
    }
}

impl FusedIterator for AncestorsIter<'_> {}

pub struct VisibleAncestorsIter<'a> {
    inner: AncestorsIter<'a>,
    starting_scope_kind: ScopeKind,
    yielded_count: usize,
}

impl<'a> VisibleAncestorsIter<'a> {
    fn new(scopes: &'a IndexSlice<FileScopeId, Scope>, start: FileScopeId) -> Self {
        let starting_scope = &scopes[start];
        Self {
            inner: AncestorsIter::new(scopes, start),
            starting_scope_kind: starting_scope.kind(),
            yielded_count: 0,
        }
    }
}

impl<'a> Iterator for VisibleAncestorsIter<'a> {
    type Item = (FileScopeId, &'a Scope);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (scope_id, scope) = self.inner.next()?;
            self.yielded_count += 1;

            // Always return the first scope (the starting scope)
            if self.yielded_count == 1 {
                return Some((scope_id, scope));
            }

            // Skip class scopes for subsequent scopes (following Python's lexical scoping rules)
            // Exception: type parameter scopes can see names defined in an immediately-enclosing class scope
            if scope.kind() == ScopeKind::Class {
                // Allow annotation scopes to see their immediately-enclosing class scope exactly once
                if self.starting_scope_kind.is_annotation() && self.yielded_count == 2 {
                    return Some((scope_id, scope));
                }
                continue;
            }

            return Some((scope_id, scope));
        }
    }
}

impl FusedIterator for VisibleAncestorsIter<'_> {}

pub(crate) struct DescendantsIter<'a> {
    next_id: FileScopeId,
    descendants: std::slice::Iter<'a, Scope>,
}

impl<'a> DescendantsIter<'a> {
    fn new(scopes: &'a IndexSlice<FileScopeId, Scope>, scope_id: FileScopeId) -> Self {
        let scope = &scopes[scope_id];
        let scopes = &scopes[scope.descendants()];

        Self {
            next_id: scope_id + 1,
            descendants: scopes.iter(),
        }
    }
}

impl<'a> Iterator for DescendantsIter<'a> {
    type Item = (FileScopeId, &'a Scope);

    fn next(&mut self) -> Option<Self::Item> {
        let descendant = self.descendants.next()?;
        let id = self.next_id;
        self.next_id = self.next_id + 1;

        Some((id, descendant))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.descendants.size_hint()
    }
}

impl FusedIterator for DescendantsIter<'_> {}

impl ExactSizeIterator for DescendantsIter<'_> {}

pub struct ChildrenIter<'a> {
    parent: FileScopeId,
    descendants: DescendantsIter<'a>,
}

impl<'a> ChildrenIter<'a> {
    fn new(scopes: &'a IndexSlice<FileScopeId, Scope>, parent: FileScopeId) -> Self {
        let descendants = DescendantsIter::new(scopes, parent);

        Self {
            parent,
            descendants,
        }
    }
}

impl<'a> Iterator for ChildrenIter<'a> {
    type Item = (FileScopeId, &'a Scope);

    fn next(&mut self) -> Option<Self::Item> {
        self.descendants
            .find(|(_, scope)| scope.parent() == Some(self.parent))
    }
}

impl FusedIterator for ChildrenIter<'_> {}

/// Interval map that maps a range of expression node ids to their corresponding scopes.
///
/// Lookups require `O(log n)` time, where `n` is roughly the number of scopes (roughly
/// because sub-scopes can be interleaved with expressions in the outer scope, e.g. function, some statements, a function).
#[derive(Eq, PartialEq, Debug, get_size2::GetSize, Default)]
struct ExpressionsScopeMap(Box<[(std::ops::RangeInclusive<NodeIndex>, FileScopeId)]>);

impl ExpressionsScopeMap {
    fn try_get<E>(&self, node: &E) -> Option<FileScopeId>
    where
        E: HasTrackedScope,
    {
        let node_index = node.node_index().load();

        let entry = self
            .0
            .binary_search_by_key(&node_index, |(range, _)| *range.start());

        let index = match entry {
            Ok(index) => index,
            Err(index) => index.checked_sub(1)?,
        };

        let (range, scope) = &self.0[index];
        if range.contains(&node_index) {
            Some(*scope)
        } else {
            None
        }
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, get_size2::GetSize)]
pub enum Truthiness {
    /// For an object `x`, `bool(x)` will always return `True`
    AlwaysTrue,
    /// For an object `x`, `bool(x)` will always return `False`
    AlwaysFalse,
    /// For an object `x`, `bool(x)` could return either `True` or `False`
    Ambiguous,
}

impl Truthiness {
    pub const fn is_ambiguous(self) -> bool {
        matches!(self, Truthiness::Ambiguous)
    }

    pub const fn is_always_false(self) -> bool {
        matches!(self, Truthiness::AlwaysFalse)
    }

    pub const fn may_be_true(self) -> bool {
        !self.is_always_false()
    }

    pub const fn is_always_true(self) -> bool {
        matches!(self, Truthiness::AlwaysTrue)
    }

    #[must_use]
    pub const fn negate(self) -> Self {
        match self {
            Self::AlwaysTrue => Self::AlwaysFalse,
            Self::AlwaysFalse => Self::AlwaysTrue,
            Self::Ambiguous => Self::Ambiguous,
        }
    }

    #[must_use]
    pub const fn negate_if(self, condition: bool) -> Self {
        if condition { self.negate() } else { self }
    }

    #[must_use]
    pub fn or(self, other: Self) -> Self {
        match self {
            Truthiness::AlwaysTrue => self,
            Truthiness::AlwaysFalse => other,
            Truthiness::Ambiguous => match other {
                Truthiness::AlwaysTrue => Truthiness::AlwaysTrue,
                Truthiness::AlwaysFalse | Truthiness::Ambiguous => Truthiness::Ambiguous,
            },
        }
    }

    #[must_use]
    pub fn or_else(self, other: impl Fn() -> Self) -> Self {
        match self {
            Truthiness::AlwaysTrue => self,
            Truthiness::AlwaysFalse => other(),
            Truthiness::Ambiguous => match other() {
                Truthiness::AlwaysTrue => Truthiness::AlwaysTrue,
                Truthiness::AlwaysFalse | Truthiness::Ambiguous => Truthiness::Ambiguous,
            },
        }
    }
}

impl From<bool> for Truthiness {
    fn from(value: bool) -> Self {
        if value {
            Truthiness::AlwaysTrue
        } else {
            Truthiness::AlwaysFalse
        }
    }
}

#[derive(Clone, Copy, Debug, Hash, PartialEq, get_size2::GetSize)]
pub enum EvaluationMode {
    Sync,
    Async,
}

impl EvaluationMode {
    pub const fn from_is_async(is_async: bool) -> Self {
        if is_async {
            EvaluationMode::Async
        } else {
            EvaluationMode::Sync
        }
    }

    pub const fn is_async(self) -> bool {
        matches!(self, EvaluationMode::Async)
    }
}

/// Specifies how the boundness of a place should be determined.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum BoundnessAnalysis {
    /// The place is always considered bound.
    AssumeBound,
    /// The boundness of the place is determined based on the visibility of the implicit
    /// `unbound` binding. In the example below, when analyzing the visibility of the
    /// `x = <unbound>` binding from the position of the end of the scope, it would be
    /// `Truthiness::Ambiguous`, because it could either be visible or not, depending on the
    /// `flag()` return value. This would result in a `Definedness::PossiblyUndefined` for `x`.
    ///
    /// ```py
    /// x = <unbound>
    ///
    /// if flag():
    ///     x = 1
    /// ```
    BasedOnUnboundVisibility,
}

/// A set of places that could possibly be narrowed by a predicate.
///
/// This is a conservative upper bound - all places that actually get narrowed
/// will be in this set, but there may be additional places that end up not
/// being narrowed after full analysis.
pub type PossiblyNarrowedPlaces = FxHashSet<ScopedPlaceId>;

/// Implemented by types for which the semantic index tracks their scope.
pub trait HasTrackedScope: ast::HasNodeIndex {}

impl HasTrackedScope for ast::Expr {}
impl HasTrackedScope for ast::ExprRef<'_> {}
impl HasTrackedScope for &ast::ExprRef<'_> {}

// We never explicitly register the scope of an `Identifier`.
// However, `ExpressionsScopeMap` stores the text ranges of each scope.
// That allows us to look up the identifier's scope for as long as it's
// inside an expression (because the ranges overlap).
impl HasTrackedScope for ast::Identifier {}

#[cfg(test)]
mod tests {
    use ruff_db::{
        files::{File, system_path_to_file},
        parsed::ParsedModuleRef,
    };
    use ruff_python_ast as ast;
    use ruff_text_size::{Ranged, TextRange};

    use super::*;

    use crate::{
        ast_ids::{HasScopedUseId, ScopedUseId},
        db::tests::{TestDb, TestDbBuilder},
        definition::{
            DefinitionKind, LambdaParameterDefinitionNodeKind, ParameterDefinitionNodeKind,
        },
        program::Program,
    };

    impl UseDefMap<'_> {
        fn first_public_binding(&self, symbol: ScopedSymbolId) -> Option<Definition<'_>> {
            self.end_of_scope_symbol_bindings(symbol)
                .find_map(|constrained_binding| constrained_binding.binding.definition())
        }

        fn first_public_declaration(&self, symbol: ScopedSymbolId) -> Option<Definition<'_>> {
            self.end_of_scope_symbol_declarations(symbol)
                .find_map(|declaration_with_constraint| {
                    declaration_with_constraint.declaration.definition()
                })
        }

        fn first_binding_at_use(&self, use_id: ScopedUseId) -> Option<Definition<'_>> {
            self.bindings_at_use(use_id)
                .find_map(|constrained_binding| constrained_binding.binding.definition())
        }
    }

    struct TestCase {
        db: TestDb,
        file: File,
    }

    fn test_case(content: &str) -> TestCase {
        const FILENAME: &str = "test.py";

        let db = TestDbBuilder::new()
            .with_file(FILENAME, content)
            .build()
            .unwrap();

        let file = system_path_to_file(&db, FILENAME).unwrap();

        TestCase { db, file }
    }

    fn program_file(db: &TestDb, file: File) -> ProgramFile<'_> {
        db.program().program_file(db, file)
    }

    fn names(table: &PlaceTable) -> Vec<String> {
        table
            .symbols()
            .map(|expr| expr.name().to_string())
            .collect()
    }

    #[test]
    fn empty() {
        let TestCase { db, file } = test_case("");
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        let global_names = names(global_table);

        assert_eq!(global_names, Vec::<&str>::new());
    }

    #[test]
    fn simple() {
        let TestCase { db, file } = test_case("x");
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert_eq!(names(global_table), vec!["x"]);
    }

    #[test]
    fn annotation_only() {
        let TestCase { db, file } = test_case("x: int");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(names(global_table), vec!["int", "x"]);

        let use_def = use_def_map(&db, scope);
        let declaration = use_def
            .first_public_declaration(global_table.symbol_id("x").expect("symbol to exist"))
            .unwrap();
        assert!(matches!(
            declaration.kind(&db),
            DefinitionKind::AnnotatedAssignment(_)
        ));
    }

    #[test]
    fn import() {
        let TestCase { db, file } = test_case("import foo");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(names(global_table), vec!["foo"]);
        let foo = global_table.symbol_id("foo").unwrap();

        let use_def = use_def_map(&db, scope);
        let binding = use_def.first_public_binding(foo).unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::Import(_)));
    }

    #[test]
    fn import_sub() {
        let TestCase { db, file } = test_case("import foo.bar");
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert_eq!(names(global_table), vec!["foo"]);
    }

    #[test]
    fn import_as() {
        let TestCase { db, file } = test_case("import foo.bar as baz");
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert_eq!(names(global_table), vec!["baz"]);
    }

    #[test]
    fn import_from() {
        let TestCase { db, file } = test_case("from bar import foo");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(names(global_table), vec!["foo"]);
        assert!(
            global_table
                .symbol_by_name("foo")
                .is_some_and(|symbol| { symbol.is_bound() && !symbol.is_used() }),
            "symbols that are defined get the defined flag"
        );

        let use_def = use_def_map(&db, scope);
        let binding = use_def
            .first_public_binding(global_table.symbol_id("foo").expect("symbol to exist"))
            .unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::ImportFrom(_)));
    }

    #[test]
    fn assign() {
        let TestCase { db, file } = test_case("x = foo");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(names(global_table), vec!["foo", "x"]);
        assert!(
            global_table
                .symbol_by_name("foo")
                .is_some_and(|symbol| { !symbol.is_bound() && symbol.is_used() }),
            "a symbol used but not bound in a scope should have only the used flag"
        );
        let use_def = use_def_map(&db, scope);
        let binding = use_def
            .first_public_binding(global_table.symbol_id("x").expect("symbol exists"))
            .unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::Assignment(_)));
    }

    #[test]
    fn augmented_assignment() {
        let TestCase { db, file } = test_case("x += 1");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(names(global_table), vec!["x"]);

        let use_def = use_def_map(&db, scope);
        let binding = use_def
            .first_public_binding(global_table.symbol_id("x").unwrap())
            .unwrap();

        assert!(matches!(
            binding.kind(&db),
            DefinitionKind::AugmentedAssignment(_)
        ));
    }

    #[test]
    fn class_scope() {
        let TestCase { db, file } = test_case(
            "
class C:
    x = 1
y = 2
",
        );
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert_eq!(names(global_table), vec!["C", "y"]);

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));

        let [(class_scope_id, class_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope")
        };
        assert_eq!(class_scope.kind(), ScopeKind::Class);
        assert_eq!(
            class_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "C"
        );

        let class_table = index.place_table(class_scope_id);
        assert_eq!(names(class_table), vec!["x"]);

        let use_def = index.use_def_map(class_scope_id);
        let binding = use_def
            .first_public_binding(class_table.symbol_id("x").expect("symbol exists"))
            .unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::Assignment(_)));
    }

    #[test]
    fn function_scope() {
        let TestCase { db, file } = test_case(
            "
def func():
    x = 1
y = 2
",
        );
        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["func", "y"]);

        let [(function_scope_id, function_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope")
        };
        assert_eq!(function_scope.kind(), ScopeKind::Function);
        assert_eq!(
            function_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "func"
        );

        let function_table = index.place_table(function_scope_id);
        assert_eq!(names(function_table), vec!["x"]);

        let use_def = index.use_def_map(function_scope_id);
        let binding = use_def
            .first_public_binding(function_table.symbol_id("x").expect("symbol exists"))
            .unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::Assignment(_)));
    }

    #[test]
    fn function_parameter_symbols() {
        let TestCase { db, file } = test_case(
            "
def f(a: str, /, b: str, c: int = 1, *args, d: int = 2, **kwargs):
    pass
",
        );

        let index = semantic_index(&db, program_file(&db, file));
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert_eq!(names(global_table), vec!["str", "int", "f"]);

        let [(function_scope_id, _function_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("Expected a function scope")
        };

        let function_table = index.place_table(function_scope_id);
        assert_eq!(
            names(function_table),
            vec!["a", "b", "c", "d", "args", "kwargs"],
        );

        let use_def = index.use_def_map(function_scope_id);
        for name in ["a", "b", "c", "d"] {
            let binding = use_def
                .first_public_binding(function_table.symbol_id(name).expect("symbol exists"))
                .unwrap();
            assert!(matches!(binding.kind(&db), DefinitionKind::Parameter(_)));
        }
        let args_binding = use_def
            .first_public_binding(function_table.symbol_id("args").expect("symbol exists"))
            .unwrap();
        assert!(matches!(
            args_binding.kind(&db),
            DefinitionKind::Parameter(ParameterDefinitionNodeKind::VariadicPositionalParameter(_))
        ));
        let kwargs_binding = use_def
            .first_public_binding(function_table.symbol_id("kwargs").expect("symbol exists"))
            .unwrap();
        assert!(matches!(
            kwargs_binding.kind(&db),
            DefinitionKind::Parameter(ParameterDefinitionNodeKind::VariadicKeywordParameter(_))
        ));
    }

    #[test]
    fn lambda_parameter_symbols() {
        let TestCase { db, file } = test_case("lambda a, b, c=1, *args, d=2, **kwargs: None");

        let index = semantic_index(&db, program_file(&db, file));
        let global_table = place_table(&db, global_scope(&db, program_file(&db, file)));

        assert!(names(global_table).is_empty());

        let [(lambda_scope_id, _lambda_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("Expected a lambda scope")
        };

        let lambda_table = index.place_table(lambda_scope_id);
        assert_eq!(
            names(lambda_table),
            vec!["a", "b", "c", "args", "d", "kwargs"],
        );

        let use_def = index.use_def_map(lambda_scope_id);
        for name in ["a", "b", "c", "d"] {
            let binding = use_def
                .first_public_binding(lambda_table.symbol_id(name).expect("symbol exists"))
                .unwrap();
            assert!(matches!(
                binding.kind(&db),
                DefinitionKind::LambdaParameter(LambdaParameterDefinitionNodeKind {
                    index: _,
                    lambda: _,
                    parameter: ParameterDefinitionNodeKind::Parameter(_)
                })
            ));
        }
        let args_binding = use_def
            .first_public_binding(lambda_table.symbol_id("args").expect("symbol exists"))
            .unwrap();
        assert!(matches!(
            args_binding.kind(&db),
            DefinitionKind::LambdaParameter(LambdaParameterDefinitionNodeKind {
                index: 3,
                lambda: _,
                parameter: ParameterDefinitionNodeKind::VariadicPositionalParameter(_)
            })
        ));
        let kwargs_binding = use_def
            .first_public_binding(lambda_table.symbol_id("kwargs").expect("symbol exists"))
            .unwrap();
        assert!(matches!(
            kwargs_binding.kind(&db),
            DefinitionKind::LambdaParameter(LambdaParameterDefinitionNodeKind {
                index: 5,
                lambda: _,
                parameter: ParameterDefinitionNodeKind::VariadicKeywordParameter(_)
            })
        ));
    }

    /// Test case to validate that the comprehension scope is correctly identified and that the target
    /// variable is defined only in the comprehension scope and not in the global scope.
    #[test]
    fn comprehension_scope() {
        let TestCase { db, file } = test_case(
            "
[x for x, y in iter1]
",
        );

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["iter1"]);

        let [(comprehension_scope_id, comprehension_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope")
        };

        assert_eq!(comprehension_scope.kind(), ScopeKind::Comprehension);
        assert_eq!(
            comprehension_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "<listcomp>"
        );

        let comprehension_symbol_table = index.place_table(comprehension_scope_id);

        assert_eq!(names(comprehension_symbol_table), vec!["x", "y"]);

        let use_def = index.use_def_map(comprehension_scope_id);
        for name in ["x", "y"] {
            let binding = use_def
                .first_public_binding(
                    comprehension_symbol_table
                        .symbol_id(name)
                        .expect("symbol exists"),
                )
                .unwrap();
            assert!(matches!(
                binding.kind(&db),
                DefinitionKind::Comprehension(_)
            ));
        }
    }

    /// Test case to validate that the `x` variable used in the comprehension is referencing the
    /// `x` variable defined by the inner generator (`for x in iter2`) and not the outer one.
    #[test]
    fn multiple_generators() {
        let TestCase { db, file } = test_case(
            "
[x for x in iter1 for x in iter2]
",
        );

        let index = semantic_index(&db, program_file(&db, file));
        let [(comprehension_scope_id, _)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope")
        };

        let use_def = index.use_def_map(comprehension_scope_id);

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let syntax = module.syntax();
        let element = syntax.body[0]
            .as_expr_stmt()
            .unwrap()
            .value
            .as_list_comp_expr()
            .unwrap()
            .elt
            .as_name_expr()
            .unwrap();
        let element_use_id = element.scoped_use_id(&db, program_file(&db, file));

        let binding = use_def.first_binding_at_use(element_use_id).unwrap();
        let DefinitionKind::Comprehension(comprehension) = binding.kind(&db) else {
            panic!("expected generator definition")
        };
        let target = comprehension.target(&module);
        let name = target.as_name_expr().unwrap().id().as_str();

        assert_eq!(name, "x");
        assert_eq!(target.range(), TextRange::new(23.into(), 24.into()));
    }

    /// Test case to validate that the nested comprehension creates a new scope which is a child of
    /// the outer comprehension scope and the variables are correctly defined in the respective
    /// scopes.
    #[test]
    fn nested_generators() {
        let TestCase { db, file } = test_case(
            "
[{x for x in iter2} for y in iter1]
",
        );

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["iter1"]);

        let [(comprehension_scope_id, comprehension_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope")
        };

        assert_eq!(comprehension_scope.kind(), ScopeKind::Comprehension);
        assert_eq!(
            comprehension_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "<listcomp>"
        );

        let comprehension_symbol_table = index.place_table(comprehension_scope_id);

        assert_eq!(names(comprehension_symbol_table), vec!["y", "iter2"]);

        let [(inner_comprehension_scope_id, inner_comprehension_scope)] = index
            .child_scopes(comprehension_scope_id)
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one inner generator scope")
        };

        assert_eq!(inner_comprehension_scope.kind(), ScopeKind::Comprehension);
        assert_eq!(
            inner_comprehension_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "<setcomp>"
        );

        let inner_comprehension_symbol_table = index.place_table(inner_comprehension_scope_id);

        assert_eq!(names(inner_comprehension_symbol_table), vec!["x"]);
    }

    #[test]
    fn with_item_definition() {
        let TestCase { db, file } = test_case(
            "
with item1 as x, item2 as y:
    pass
",
        );

        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["item1", "x", "item2", "y"]);

        let use_def = index.use_def_map(FileScopeId::global());
        for name in ["x", "y"] {
            let binding = use_def
                .first_public_binding(global_table.symbol_id(name).expect("symbol exists"))
                .expect("Expected with item definition for {name}");
            assert!(matches!(binding.kind(&db), DefinitionKind::WithItem(_)));
        }
    }

    #[test]
    fn with_item_unpacked_definition() {
        let TestCase { db, file } = test_case(
            "
with context() as (x, y):
    pass
",
        );

        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["context", "x", "y"]);

        let use_def = index.use_def_map(FileScopeId::global());
        for name in ["x", "y"] {
            let binding = use_def
                .first_public_binding(global_table.symbol_id(name).expect("symbol exists"))
                .expect("Expected with item definition for {name}");
            assert!(matches!(binding.kind(&db), DefinitionKind::WithItem(_)));
        }
    }

    #[test]
    fn dupes() {
        let TestCase { db, file } = test_case(
            "
def func():
    x = 1
def func():
    y = 2
",
        );
        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["func"]);
        let [
            (func_scope1_id, func_scope_1),
            (func_scope2_id, func_scope_2),
        ] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected two child scopes");
        };

        assert_eq!(func_scope_1.kind(), ScopeKind::Function);

        assert_eq!(
            func_scope1_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "func"
        );
        assert_eq!(func_scope_2.kind(), ScopeKind::Function);
        assert_eq!(
            func_scope2_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "func"
        );

        let func1_table = index.place_table(func_scope1_id);
        let func2_table = index.place_table(func_scope2_id);
        assert_eq!(names(func1_table), vec!["x"]);
        assert_eq!(names(func2_table), vec!["y"]);

        let use_def = index.use_def_map(FileScopeId::global());
        let binding = use_def
            .first_public_binding(global_table.symbol_id("func").expect("symbol exists"))
            .unwrap();
        assert!(matches!(binding.kind(&db), DefinitionKind::Function(_)));
    }

    #[test]
    fn generic_function() {
        let TestCase { db, file } = test_case(
            "
def func[T]():
    x = 1
",
        );

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["func"]);

        let [(ann_scope_id, ann_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope");
        };

        assert_eq!(ann_scope.kind(), ScopeKind::TypeParams);
        assert_eq!(
            ann_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "func"
        );
        let ann_table = index.place_table(ann_scope_id);
        assert_eq!(names(ann_table), vec!["T"]);

        let [(func_scope_id, func_scope)] =
            index.child_scopes(ann_scope_id).collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope");
        };
        assert_eq!(func_scope.kind(), ScopeKind::Function);
        assert_eq!(
            func_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "func"
        );
        let func_table = index.place_table(func_scope_id);
        assert_eq!(names(func_table), vec!["x"]);
    }

    #[test]
    fn generic_class() {
        let TestCase { db, file } = test_case(
            "
class C[T]:
    x = 1
",
        );

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));
        let global_table = index.place_table(FileScopeId::global());

        assert_eq!(names(global_table), vec!["C"]);

        let [(ann_scope_id, ann_scope)] = index
            .child_scopes(FileScopeId::global())
            .collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope");
        };

        assert_eq!(ann_scope.kind(), ScopeKind::TypeParams);
        assert_eq!(
            ann_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "C"
        );
        let ann_table = index.place_table(ann_scope_id);
        assert_eq!(names(ann_table), vec!["T"]);
        assert!(
            ann_table
                .symbol_by_name("T")
                .is_some_and(|s| s.is_bound() && !s.is_used()),
            "type parameters are defined by the scope that introduces them"
        );

        let [(class_scope_id, class_scope)] =
            index.child_scopes(ann_scope_id).collect::<Vec<_>>()[..]
        else {
            panic!("expected one child scope");
        };

        assert_eq!(class_scope.kind(), ScopeKind::Class);
        assert_eq!(
            class_scope_id
                .to_scope_id(&db, program_file(&db, file))
                .name(&db, &module),
            "C"
        );
        assert_eq!(names(index.place_table(class_scope_id)), vec!["x"]);
    }

    #[test]
    fn reachability_trivial() {
        let TestCase { db, file } = test_case("x = 1; x");
        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let scope = global_scope(&db, program_file(&db, file));
        let ast = module.syntax();
        let ast::Stmt::Expr(ast::StmtExpr {
            value: x_use_expr, ..
        }) = &ast.body[1]
        else {
            panic!("should be an expr")
        };
        let ast::Expr::Name(x_use_expr_name) = x_use_expr.as_ref() else {
            panic!("expected a Name");
        };
        let x_use_id = x_use_expr_name.scoped_use_id(&db, program_file(&db, file));
        let use_def = use_def_map(&db, scope);
        let binding = use_def.first_binding_at_use(x_use_id).unwrap();
        let DefinitionKind::Assignment(assignment) = binding.kind(&db) else {
            panic!("should be an assignment definition")
        };
        let ast::Expr::NumberLiteral(ast::ExprNumberLiteral {
            value: ast::Number::Int(num),
            ..
        }) = assignment.value(&module)
        else {
            panic!("should be a number literal")
        };
        assert_eq!(*num, 1);
    }

    #[test]
    fn expression_scope() {
        let TestCase { db, file } = test_case("x = 1;\ndef test():\n  y = 4");

        let index = semantic_index(&db, program_file(&db, file));
        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let ast = module.syntax();

        let x_stmt = ast.body[0].as_assign_stmt().unwrap();
        let x = &x_stmt.targets[0];

        assert_eq!(index.expression_scope(x).kind(), ScopeKind::Module);
        assert_eq!(index.expression_scope_id(x), FileScopeId::global());

        let def = ast.body[1].as_function_def_stmt().unwrap();
        let y_stmt = def.body[0].as_assign_stmt().unwrap();
        let y = &y_stmt.targets[0];

        assert_eq!(index.expression_scope(y).kind(), ScopeKind::Function);
    }

    #[test]
    fn scope_iterators() {
        fn scope_names<'a, 'db>(
            scopes: impl Iterator<Item = (FileScopeId, &'db Scope)>,
            db: &'db dyn Db,
            file: File,
            program: Program<'db>,
            module: &'a ParsedModuleRef,
        ) -> Vec<&'a str> {
            scopes
                .into_iter()
                .map(|(scope_id, _)| {
                    scope_id
                        .to_scope_id(db, program.program_file(db, file))
                        .name(db, module)
                })
                .collect()
        }

        let TestCase { db, file } = test_case(
            r"
class Test:
    def foo():
        def bar():
            ...
    def baz():
        pass

def x():
    pass",
        );

        let module = parsed_module(&db, program_file(&db, file).python_file(&db)).load(&db);
        let index = semantic_index(&db, program_file(&db, file));

        let descendants = index.descendent_scopes(FileScopeId::global());
        assert_eq!(
            scope_names(descendants, &db, file, db.program(), &module),
            vec!["Test", "foo", "bar", "baz", "x"]
        );

        let children = index.child_scopes(FileScopeId::global());
        assert_eq!(
            scope_names(children, &db, file, db.program(), &module),
            vec!["Test", "x"]
        );

        let test_class = index.child_scopes(FileScopeId::global()).next().unwrap().0;
        let test_child_scopes = index.child_scopes(test_class);
        assert_eq!(
            scope_names(test_child_scopes, &db, file, db.program(), &module),
            vec!["foo", "baz"]
        );

        let bar_scope = index
            .descendent_scopes(FileScopeId::global())
            .nth(2)
            .unwrap()
            .0;
        let ancestors = index.ancestor_scopes(bar_scope);

        assert_eq!(
            scope_names(ancestors, &db, file, db.program(), &module),
            vec!["bar", "foo", "Test", "<module>"]
        );
    }

    #[test]
    fn match_stmt() {
        let TestCase { db, file } = test_case(
            "
match subject:
    case a: ...
    case [b, c, *d]: ...
    case e as f: ...
    case {'x': g, **h}: ...
    case Foo(i, z=j): ...
    case k | l: ...
    case _: ...
",
        );

        let global_scope_id = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, global_scope_id);

        assert!(global_table.symbol_by_name("Foo").unwrap().is_used());
        assert_eq!(
            names(global_table),
            vec![
                "subject", "a", "b", "c", "d", "e", "f", "g", "h", "Foo", "i", "j", "k", "l"
            ]
        );

        let use_def = use_def_map(&db, global_scope_id);
        for name in ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"] {
            let binding = use_def
                .first_public_binding(global_table.symbol_id(name).expect("symbol exists"))
                .expect("Expected with item definition for {name}");
            assert!(matches!(binding.kind(&db), DefinitionKind::MatchPattern(_)));
        }
    }

    #[test]
    fn nested_match_case() {
        let TestCase { db, file } = test_case(
            "
match 1:
    case first:
        match 2:
            case second:
                pass
",
        );

        let global_scope_id = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, global_scope_id);

        assert_eq!(names(global_table), vec!["first", "second"]);

        let use_def = use_def_map(&db, global_scope_id);
        for name in ["first", "second"] {
            let binding = use_def
                .first_public_binding(global_table.symbol_id(name).expect("symbol exists"))
                .expect("Expected with item definition for {name}");
            assert!(matches!(binding.kind(&db), DefinitionKind::MatchPattern(_)));
        }
    }

    #[test]
    fn for_loops_single_assignment() {
        let TestCase { db, file } = test_case("for x in a: pass");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(&names(global_table), &["a", "x"]);

        let use_def = use_def_map(&db, scope);
        let binding = use_def
            .first_public_binding(global_table.symbol_id("x").unwrap())
            .unwrap();

        assert!(matches!(binding.kind(&db), DefinitionKind::For(_)));
    }

    #[test]
    fn for_loops_simple_unpacking() {
        let TestCase { db, file } = test_case("for (x, y) in a: pass");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(&names(global_table), &["a", "x", "y"]);

        let use_def = use_def_map(&db, scope);
        let x_binding = use_def
            .first_public_binding(global_table.symbol_id("x").unwrap())
            .unwrap();
        let y_binding = use_def
            .first_public_binding(global_table.symbol_id("y").unwrap())
            .unwrap();

        assert!(matches!(x_binding.kind(&db), DefinitionKind::For(_)));
        assert!(matches!(y_binding.kind(&db), DefinitionKind::For(_)));
    }

    #[test]
    fn for_loops_complex_unpacking() {
        let TestCase { db, file } = test_case("for [((a,) b), (c, d)] in e: pass");
        let scope = global_scope(&db, program_file(&db, file));
        let global_table = place_table(&db, scope);

        assert_eq!(&names(global_table), &["e", "a", "b", "c", "d"]);

        let use_def = use_def_map(&db, scope);
        let binding = use_def
            .first_public_binding(global_table.symbol_id("a").unwrap())
            .unwrap();

        assert!(matches!(binding.kind(&db), DefinitionKind::For(_)));
    }
}