[ty] Improve Black benchmark performance
diff --git a/crates/ty_python_core/src/builder.rs b/crates/ty_python_core/src/builder.rs index 8b69bdf..1ac8707 100644 --- a/crates/ty_python_core/src/builder.rs +++ b/crates/ty_python_core/src/builder.rs
@@ -176,6 +176,7 @@ .map_or_else(|| fallback, |snapshots| &snapshots.truthy) .clone() } + fn falsy(&self) -> FlowSnapshot { let Self { fallback, @@ -455,13 +456,12 @@ self.try_node_context_stack_manager.enter_nested_scope(); let file_scope_id = self.scopes.push(scope); + let scope_id = ScopeId::new(self.db, self.file, file_scope_id); self.place_tables.push(PlaceTableBuilder::default()); self.use_def_maps - .push(UseDefMapBuilder::new(is_class_scope)); + .push(UseDefMapBuilder::new(scope_id, is_class_scope)); let ast_id_scope = self.ast_ids.push(AstIdsBuilder::default()); - let scope_id = ScopeId::new(self.db, self.file, file_scope_id); - self.scope_ids_by_scope.push(scope_id); let previous = self.scopes_by_node.insert(node.node_key(), file_scope_id); debug_assert_eq!(previous, None);
diff --git a/crates/ty_python_core/src/reachability_constraints.rs b/crates/ty_python_core/src/reachability_constraints.rs index 2df6cf4..a4a7235 100644 --- a/crates/ty_python_core/src/reachability_constraints.rs +++ b/crates/ty_python_core/src/reachability_constraints.rs
@@ -352,6 +352,10 @@ a: ScopedReachabilityConstraintId, b: ScopedReachabilityConstraintId, ) -> ScopedReachabilityConstraintId { + if a == b { + return a; + } + match (a, b) { (ALWAYS_TRUE, _) | (_, ALWAYS_TRUE) => return ALWAYS_TRUE, (ALWAYS_FALSE, other) | (other, ALWAYS_FALSE) => return other, @@ -422,6 +426,10 @@ a: ScopedReachabilityConstraintId, b: ScopedReachabilityConstraintId, ) -> ScopedReachabilityConstraintId { + if a == b { + return a; + } + match (a, b) { (ALWAYS_FALSE, _) | (_, ALWAYS_FALSE) => return ALWAYS_FALSE, (ALWAYS_TRUE, other) | (other, ALWAYS_TRUE) => return other,
diff --git a/crates/ty_python_core/src/use_def.rs b/crates/ty_python_core/src/use_def.rs index f237ac1..bbf269a 100644 --- a/crates/ty_python_core/src/use_def.rs +++ b/crates/ty_python_core/src/use_def.rs
@@ -255,7 +255,7 @@ use crate::reachability_constraints::{ ReachabilityConstraints, ReachabilityConstraintsBuilder, ScopedReachabilityConstraintId, }; -use crate::scope::{FileScopeId, ScopeKind, ScopeLaziness}; +use crate::scope::{FileScopeId, ScopeId, ScopeKind, ScopeLaziness}; use crate::symbol::ScopedSymbolId; use crate::use_def::place_state::{ Bindings, Declarations, EnclosingSnapshot, LiveBindingsIterator, LiveDeclaration, @@ -430,6 +430,9 @@ /// Applicable definitions and constraints for every use of a name. #[derive(Debug, PartialEq, Eq, salsa::Update, get_size2::GetSize)] pub struct UseDefMap<'db> { + /// The scope this use-def map describes. + scope: ScopeId<'db>, + /// Array of [`Definition`] in this scope. Only the first entry should be [`DefinitionState::Undefined`]; /// this represents the implicit "unbound"/"undeclared" definition of every place. all_definitions: FrozenIndexVec<ScopedDefinitionId, DefinitionState<'db>>, @@ -546,6 +549,10 @@ } impl<'db> UseDefMap<'db> { + pub fn scope(&self) -> ScopeId<'db> { + self.scope + } + pub fn reachability_constraints(&self) -> &ReachabilityConstraints { &self.reachability_constraints } @@ -863,6 +870,7 @@ boundness_analysis: BoundnessAnalysis, ) -> BindingWithConstraintsIterator<'map, 'db> { BindingWithConstraintsIterator { + scope: self.scope, all_definitions: &self.all_definitions, predicates: &self.predicates, reachability_constraints: &self.reachability_constraints, @@ -877,6 +885,7 @@ boundness_analysis: BoundnessAnalysis, ) -> DeclarationsIterator<'map, 'db> { DeclarationsIterator { + scope: self.scope, all_definitions: &self.all_definitions, predicates: &self.predicates, reachability_constraints: &self.reachability_constraints, @@ -918,6 +927,7 @@ #[derive(Clone, Debug)] pub struct BindingWithConstraintsIterator<'map, 'db> { + scope: ScopeId<'db>, all_definitions: &'map IndexSlice<ScopedDefinitionId, DefinitionState<'db>>, predicates: &'map Predicates<'db>, reachability_constraints: &'map ReachabilityConstraints, @@ -926,6 +936,10 @@ } impl<'map, 'db> BindingWithConstraintsIterator<'map, 'db> { + pub const fn scope(&self) -> ScopeId<'db> { + self.scope + } + pub const fn predicates(&self) -> &'map Predicates<'db> { self.predicates } @@ -990,6 +1004,7 @@ #[derive(Clone)] pub struct DeclarationsIterator<'map, 'db> { + scope: ScopeId<'db>, all_definitions: &'map IndexSlice<ScopedDefinitionId, DefinitionState<'db>>, predicates: &'map Predicates<'db>, reachability_constraints: &'map ReachabilityConstraints, @@ -998,6 +1013,10 @@ } impl<'map, 'db> DeclarationsIterator<'map, 'db> { + pub const fn scope(&self) -> ScopeId<'db> { + self.scope + } + pub const fn predicates(&self) -> &'map Predicates<'db> { self.predicates } @@ -1069,6 +1088,9 @@ #[derive(Debug)] pub(super) struct UseDefMapBuilder<'db> { + /// The scope this use-def map describes. + scope: ScopeId<'db>, + /// Append-only array of [`DefinitionState`]. all_definitions: IndexVec<ScopedDefinitionId, DefinitionState<'db>>, @@ -1125,8 +1147,9 @@ } impl<'db> UseDefMapBuilder<'db> { - pub(super) fn new(is_class_scope: bool) -> Self { + pub(super) fn new(scope: ScopeId<'db>, is_class_scope: bool) -> Self { Self { + scope, all_definitions: IndexVec::from_iter([DefinitionState::Undefined]), used_bindings: IndexVec::from_iter([false]), predicates: PredicatesBuilder::default(), @@ -1933,6 +1956,7 @@ let multi_bindings_by_use = MultiBindingsByUse::from_map(self.multi_bindings_by_use); UseDefMap { + scope: self.scope, all_definitions: self.all_definitions.into(), used_bindings: self.used_bindings.into(), predicates: self.predicates.build(),
diff --git a/crates/ty_python_core/src/use_def/place_state.rs b/crates/ty_python_core/src/use_def/place_state.rs index e36f28d..45cd3ea 100644 --- a/crates/ty_python_core/src/use_def/place_state.rs +++ b/crates/ty_python_core/src/use_def/place_state.rs
@@ -50,6 +50,46 @@ use crate::narrowing_constraints::ScopedNarrowingConstraint; use crate::reachability_constraints::ScopedReachabilityConstraintId; +fn add_and_constraint( + reachability_constraints: &mut ReachabilityConstraintsBuilder, + a: ScopedReachabilityConstraintId, + b: ScopedReachabilityConstraintId, +) -> ScopedReachabilityConstraintId { + if a == b { + return a; + } + + match (a, b) { + (ScopedReachabilityConstraintId::ALWAYS_FALSE, _) + | (_, ScopedReachabilityConstraintId::ALWAYS_FALSE) => { + ScopedReachabilityConstraintId::ALWAYS_FALSE + } + (ScopedReachabilityConstraintId::ALWAYS_TRUE, other) + | (other, ScopedReachabilityConstraintId::ALWAYS_TRUE) => other, + _ => reachability_constraints.add_and_constraint(a, b), + } +} + +fn add_or_constraint( + reachability_constraints: &mut ReachabilityConstraintsBuilder, + a: ScopedReachabilityConstraintId, + b: ScopedReachabilityConstraintId, +) -> ScopedReachabilityConstraintId { + if a == b { + return a; + } + + match (a, b) { + (ScopedReachabilityConstraintId::ALWAYS_TRUE, _) + | (_, ScopedReachabilityConstraintId::ALWAYS_TRUE) => { + ScopedReachabilityConstraintId::ALWAYS_TRUE + } + (ScopedReachabilityConstraintId::ALWAYS_FALSE, other) + | (other, ScopedReachabilityConstraintId::ALWAYS_FALSE) => other, + _ => reachability_constraints.add_or_constraint(a, b), + } +} + /// A newtype-index for a definition in a particular scope. #[newtype_index] #[derive(Ord, PartialOrd, salsa::Update, get_size2::GetSize)] @@ -164,9 +204,16 @@ reachability_constraints: &mut ReachabilityConstraintsBuilder, constraint: ScopedReachabilityConstraintId, ) { + if constraint == ScopedReachabilityConstraintId::ALWAYS_TRUE { + return; + } + for declaration in &mut self.live_declarations { - declaration.reachability_constraint = reachability_constraints - .add_and_constraint(declaration.reachability_constraint, constraint); + declaration.reachability_constraint = add_and_constraint( + reachability_constraints, + declaration.reachability_constraint, + constraint, + ); } } @@ -176,6 +223,10 @@ } fn merge(&mut self, b: Self, reachability_constraints: &mut ReachabilityConstraintsBuilder) { + if *self == b { + return; + } + let a = std::mem::take(self); // Invariant: merge_join_by consumes the two iterators in sorted order, which ensures that @@ -188,8 +239,11 @@ for zipped in a.merge_join_by(b, |a, b| a.declaration.cmp(&b.declaration)) { match zipped { EitherOrBoth::Both(a, b) => { - let reachability_constraint = reachability_constraints - .add_or_constraint(a.reachability_constraint, b.reachability_constraint); + let reachability_constraint = add_or_constraint( + reachability_constraints, + a.reachability_constraint, + b.reachability_constraint, + ); self.live_declarations.push(LiveDeclaration { declaration: a.declaration, reachability_constraint, @@ -339,9 +393,16 @@ reachability_constraints: &mut ReachabilityConstraintsBuilder, constraint: ScopedNarrowingConstraint, ) { + if constraint == ScopedNarrowingConstraint::ALWAYS_TRUE { + return; + } + for binding in &mut self.live_bindings { - binding.narrowing_constraint = reachability_constraints - .add_and_constraint(binding.narrowing_constraint, constraint); + binding.narrowing_constraint = add_and_constraint( + reachability_constraints, + binding.narrowing_constraint, + constraint, + ); } } @@ -351,9 +412,16 @@ reachability_constraints: &mut ReachabilityConstraintsBuilder, constraint: ScopedReachabilityConstraintId, ) { + if constraint == ScopedReachabilityConstraintId::ALWAYS_TRUE { + return; + } + for binding in &mut self.live_bindings { - binding.reachability_constraint = reachability_constraints - .add_and_constraint(binding.reachability_constraint, constraint); + binding.reachability_constraint = add_and_constraint( + reachability_constraints, + binding.reachability_constraint, + constraint, + ); } } @@ -367,6 +435,10 @@ b: Self, reachability_constraints: &mut ReachabilityConstraintsBuilder, ) { + if *self == b { + return; + } + let a = std::mem::take(self); if let Some((a, b)) = a @@ -374,7 +446,7 @@ .zip(b.unbound_narrowing_constraint) { self.unbound_narrowing_constraint = - Some(reachability_constraints.add_or_constraint(a, b)); + Some(add_or_constraint(reachability_constraints, a, b)); } // Invariant: merge_join_by consumes the two iterators in sorted order, which ensures that @@ -389,12 +461,18 @@ EitherOrBoth::Both(a, b) => { // If the same definition is visible through both paths, we OR the narrowing // constraints: the type should be narrowed by whichever path was taken. - let narrowing_constraint = reachability_constraints - .add_or_constraint(a.narrowing_constraint, b.narrowing_constraint); + let narrowing_constraint = add_or_constraint( + reachability_constraints, + a.narrowing_constraint, + b.narrowing_constraint, + ); // For reachability constraints, we also merge using a ternary OR operation: - let reachability_constraint = reachability_constraints - .add_or_constraint(a.reachability_constraint, b.reachability_constraint); + let reachability_constraint = add_or_constraint( + reachability_constraints, + a.reachability_constraint, + b.reachability_constraint, + ); debug_assert_eq!(a.can_be_shadowed, b.can_be_shadowed); self.live_bindings.push(LiveBinding { @@ -465,6 +543,10 @@ reachability_constraints: &mut ReachabilityConstraintsBuilder, constraint: ScopedReachabilityConstraintId, ) { + if constraint == ScopedReachabilityConstraintId::ALWAYS_TRUE { + return; + } + self.bindings .record_reachability_constraint(reachability_constraints, constraint); self.declarations @@ -490,6 +572,10 @@ b: PlaceState, reachability_constraints: &mut ReachabilityConstraintsBuilder, ) { + if *self == b { + return; + } + self.bindings.merge(b.bindings, reachability_constraints); self.declarations .merge(b.declarations, reachability_constraints);
diff --git a/crates/ty_python_semantic/resources/mdtest/bidirectional.md b/crates/ty_python_semantic/resources/mdtest/bidirectional.md index d6b09ee..e2c1b81 100644 --- a/crates/ty_python_semantic/resources/mdtest/bidirectional.md +++ b/crates/ty_python_semantic/resources/mdtest/bidirectional.md
@@ -852,24 +852,6 @@ ``` ```py -def returns_list_int(x: list[int]) -> list[int]: - return x - -def takes_list_str(x: list[str]) -> None: ... - -def _() -> list[int]: - x6_return_call = [] - reveal_type(x6_return_call) # revealed: list[int] - return returns_list_int(x6_return_call) - -def _() -> None: - x6_append_then_return_call = [] - x6_append_then_return_call.append(1) - reveal_type(x6_append_then_return_call) # revealed: list[int | str] - return takes_list_str(x6_append_then_return_call) # error: [invalid-argument-type] -``` - -```py x7 = [] x7[:] = [1, "2", 3.0] reveal_type(x7) # revealed: list[int | str | float]
diff --git a/crates/ty_python_semantic/src/place.rs b/crates/ty_python_semantic/src/place.rs index 1a36d05..f3d7cf3 100644 --- a/crates/ty_python_semantic/src/place.rs +++ b/crates/ty_python_semantic/src/place.rs
@@ -7,7 +7,9 @@ }; use crate::dunder_all::dunder_all_names; -use crate::reachability::{ReachabilityConstraintsExtension, evaluate_reachability}; +use crate::reachability::{ + ReachabilityEvaluationCache, evaluate_reachability, evaluate_reachability_with_cache, +}; use crate::types::narrow::NarrowingEvaluatorExtension; use crate::types::{ DynamicType, KnownClass, MemberLookupPolicy, Type, TypeAndQualifiers, TypeQualifiers, @@ -580,7 +582,25 @@ db: &'db dyn Db, bindings_with_constraints: BindingWithConstraintsIterator<'_, 'db>, ) -> PlaceWithDefinition<'db> { - place_from_bindings_impl(db, bindings_with_constraints, RequiresExplicitReExport::No) + place_from_bindings_impl( + db, + bindings_with_constraints, + RequiresExplicitReExport::No, + None, + ) +} + +pub(super) fn place_from_bindings_with_reachability_cache<'db>( + db: &'db dyn Db, + bindings_with_constraints: BindingWithConstraintsIterator<'_, 'db>, + reachability_cache: &ReachabilityEvaluationCache<'db>, +) -> PlaceWithDefinition<'db> { + place_from_bindings_impl( + db, + bindings_with_constraints, + RequiresExplicitReExport::No, + Some(reachability_cache), + ) } /// Build a declared type from a [`DeclarationsIterator`]. @@ -595,7 +615,20 @@ db: &'db dyn Db, declarations: DeclarationsIterator<'_, 'db>, ) -> PlaceFromDeclarationsResult<'db> { - place_from_declarations_impl(db, declarations, RequiresExplicitReExport::No) + place_from_declarations_impl(db, declarations, RequiresExplicitReExport::No, None) +} + +pub(crate) fn place_from_declarations_with_reachability_cache<'db>( + db: &'db dyn Db, + declarations: DeclarationsIterator<'_, 'db>, + reachability_cache: &ReachabilityEvaluationCache<'db>, +) -> PlaceFromDeclarationsResult<'db> { + place_from_declarations_impl( + db, + declarations, + RequiresExplicitReExport::No, + Some(reachability_cache), + ) } type DeclaredTypeAndConflictingTypes<'db> = ( @@ -881,7 +914,7 @@ ConsideredDefinitions::AllReachable => use_def.reachable_declarations(place_id), }; - let declared = place_from_declarations_impl(db, declarations, requires_explicit_reexport) + let declared = place_from_declarations_impl(db, declarations, requires_explicit_reexport, None) .ignore_conflicting_declarations(); let all_considered_bindings = || match considered_definitions { @@ -893,7 +926,7 @@ // inferred type, without unioning with `Unknown`, because it cannot be modified. if let Some(qualifiers) = declared.is_bare_final() { let bindings = all_considered_bindings(); - return place_from_bindings_impl(db, bindings, requires_explicit_reexport) + return place_from_bindings_impl(db, bindings, requires_explicit_reexport, None) .place .with_qualifiers(qualifiers); } @@ -912,7 +945,7 @@ qualifiers, } if qualifiers.contains(TypeQualifiers::CLASS_VAR) => { let bindings = all_considered_bindings(); - match place_from_bindings_impl(db, bindings, requires_explicit_reexport).place { + match place_from_bindings_impl(db, bindings, requires_explicit_reexport, None).place { Place::Defined(DefinedPlace { ty: inferred, origin, @@ -956,7 +989,7 @@ } => { let bindings = all_considered_bindings(); let boundness_analysis = bindings.boundness_analysis(); - let inferred = place_from_bindings_impl(db, bindings, requires_explicit_reexport); + let inferred = place_from_bindings_impl(db, bindings, requires_explicit_reexport, None); let place = match inferred.place { // Place is possibly undeclared and definitely unbound @@ -999,7 +1032,7 @@ let bindings = all_considered_bindings(); let boundness_analysis = bindings.boundness_analysis(); let mut inferred = - place_from_bindings_impl(db, bindings, requires_explicit_reexport).place; + place_from_bindings_impl(db, bindings, requires_explicit_reexport, None).place; if boundness_analysis == BoundnessAnalysis::AssumeBound { if let Place::Defined(defined) = inferred { @@ -1077,6 +1110,8 @@ enum DeclarationsBoundnessEvaluator<'map, 'db> { AssumeBound, BasedOnUnboundVisibility { + scope: ScopeId<'db>, + reachability_cache: Option<&'map ReachabilityEvaluationCache<'db>>, unbound_visibility: Option<DeclarationWithConstraint<'db>>, reachability_constraints: &'map ReachabilityConstraints, predicates: &'map IndexSlice<ScopedPredicateId, Predicate<'db>>, @@ -1099,6 +1134,8 @@ } } DeclarationsBoundnessEvaluator::BasedOnUnboundVisibility { + scope, + reachability_cache, reachability_constraints, unbound_visibility, predicates, @@ -1113,7 +1150,14 @@ is_non_exported(db, def, requires_explicit_reexport) }) => { - reachability_constraints.evaluate(db, predicates, reachability_constraint) + evaluate_reachability_with_cache( + db, + reachability_cache, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ) } _ => Truthiness::AlwaysFalse, }; @@ -1329,7 +1373,9 @@ db: &'db dyn Db, bindings_with_constraints: BindingWithConstraintsIterator<'_, 'db>, requires_explicit_reexport: RequiresExplicitReExport, + reachability_cache: Option<&ReachabilityEvaluationCache<'db>>, ) -> PlaceWithDefinition<'db> { + let scope = bindings_with_constraints.scope(); let predicates = bindings_with_constraints.predicates(); let reachability_constraints = bindings_with_constraints.reachability_constraints(); let boundness_analysis = bindings_with_constraints.boundness_analysis(); @@ -1354,7 +1400,14 @@ // expressions, which is extra work and can lead to cycles. let unbound_visibility = || { unbound_reachability_constraint.map(|reachability_constraint| { - reachability_constraints.evaluate(db, predicates, reachability_constraint) + evaluate_reachability_with_cache( + db, + reachability_cache, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ) }) }; @@ -1383,7 +1436,14 @@ } DefinitionState::Deleted => { deleted_reachability = deleted_reachability.or_else(|| { - reachability_constraints.evaluate(db, predicates, reachability_constraint) + evaluate_reachability_with_cache( + db, + reachability_cache, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ) }); return None; } @@ -1393,8 +1453,14 @@ return None; } - let static_reachability = - reachability_constraints.evaluate(db, predicates, reachability_constraint); + let static_reachability = evaluate_reachability_with_cache( + db, + reachability_cache, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ); if static_reachability.is_always_false() { // If the static reachability evaluates to false, the binding is either not reachable @@ -1685,7 +1751,9 @@ db: &'db dyn Db, declarations_iterator: DeclarationsIterator<'_, 'db>, requires_explicit_reexport: RequiresExplicitReExport, + reachability_cache: Option<&ReachabilityEvaluationCache<'db>>, ) -> PlaceFromDeclarationsResult<'db> { + let scope = declarations_iterator.scope(); let predicates = declarations_iterator.predicates(); let reachability_constraints = declarations_iterator.reachability_constraints(); let boundness_analysis = declarations_iterator.boundness_analysis(); @@ -1702,6 +1770,8 @@ let unbound_visibility = declarations_iterator.peek().cloned(); declarations = Either::Right(declarations_iterator); DeclarationsBoundnessEvaluator::BasedOnUnboundVisibility { + scope, + reachability_cache, unbound_visibility, predicates, reachability_constraints, @@ -1728,8 +1798,14 @@ return None; } - let static_reachability = - reachability_constraints.evaluate(db, predicates, reachability_constraint); + let static_reachability = evaluate_reachability_with_cache( + db, + reachability_cache, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ); if static_reachability.is_always_false() { None
diff --git a/crates/ty_python_semantic/src/reachability.rs b/crates/ty_python_semantic/src/reachability.rs index e914003..e0724e5 100644 --- a/crates/ty_python_semantic/src/reachability.rs +++ b/crates/ty_python_semantic/src/reachability.rs
@@ -193,13 +193,16 @@ //! [Kleene]: <https://en.wikipedia.org/wiki/Three-valued_logic#Kleene_and_Priest_logics> //! [bdd]: https://en.wikipedia.org/wiki/Binary_decision_diagram +use std::cell::RefCell; + use crate::{ Db, dunder_all::dunder_all_names, place::{DefinedPlace, Definedness, Place, RequiresExplicitReExport, imported_symbol}, types::{ CallableTypes, ClassLiteral, IntersectionBuilder, KnownClass, NarrowingConstraint, Type, - TypeContext, UnionType, enum_metadata, infer_expression_type, infer_narrowing_constraints, + TypeContext, UnionType, enum_metadata, infer_narrowing_constraints, + infer_same_file_expression_type, }, }; use ruff_index::IndexSlice; @@ -218,6 +221,7 @@ ScopedPredicateId, }, reachability_constraints::{ReachabilityConstraints, ScopedReachabilityConstraintId}, + scope::ScopeId, }; fn singleton_to_type(db: &dyn Db, singleton: ast::Singleton) -> Type<'_> { @@ -251,7 +255,7 @@ match kind { PatternPredicateKind::Singleton(singleton) => singleton_to_type(db, *singleton), PatternPredicateKind::Value(value) => { - let ty = infer_expression_type(db, *value, TypeContext::default()); + let ty = infer_same_file_expression_type(db, *value, TypeContext::default()); // Only return the type if it's single-valued. For non-single-valued types // (like `str`), we can't definitively exclude any specific type from // subsequent patterns because the pattern could match any value of that type. @@ -263,7 +267,7 @@ } PatternPredicateKind::Class(class_expr, kind) => { if kind.is_irrefutable() { - infer_expression_type(db, *class_expr, TypeContext::default()) + infer_same_file_expression_type(db, *class_expr, TypeContext::default()) .to_instance(db) .unwrap_or(Type::Never) .top_materialization(db) @@ -532,7 +536,8 @@ heap_size = get_size2::GetSize::get_heap_size )] fn analyze_pattern_predicate<'db>(db: &'db dyn Db, predicate: PatternPredicate<'db>) -> Truthiness { - let subject_ty = infer_expression_type(db, predicate.subject(db), TypeContext::default()); + let subject_ty = + infer_same_file_expression_type(db, predicate.subject(db), TypeContext::default()); if let Some(truthiness) = analyze_enum_literal_union_pattern_predicate(db, predicate, subject_ty) @@ -631,8 +636,21 @@ base_ty: Type<'db>, place: ScopedPlaceId, ) -> Type<'db> { + match id { + ScopedReachabilityConstraintId::ALWAYS_TRUE + | ScopedReachabilityConstraintId::AMBIGUOUS => return base_ty, + ScopedReachabilityConstraintId::ALWAYS_FALSE => return Type::Never, + _ => {} + } + let mut projector = NarrowingProjector::new(db, self, predicates, place); let projected_root = projector.project(id); + if projected_root == ProjectedNarrowingNodeId::ALWAYS_FALSE { + return Type::Never; + } + if projected_root == ProjectedNarrowingNodeId::ALWAYS_TRUE { + return base_ty; + } let mut context = ProjectedNarrowingContext { db, base_ty, @@ -705,7 +723,6 @@ if_false: ProjectedNarrowingNodeId, } -/// Reduced reachability graph containing only predicates relevant to one place. #[derive(Default)] struct ProjectedNarrowingGraph<'db> { nodes: Vec<ProjectedNarrowingNode>, @@ -1017,7 +1034,7 @@ ) -> Truthiness { match predicate_kind { PatternPredicateKind::Value(value) => { - let value_ty = infer_expression_type(db, *value, TypeContext::default()); + let value_ty = infer_same_file_expression_type(db, *value, TypeContext::default()); if subject_ty.is_single_valued(db) { Truthiness::from(subject_ty.is_equivalent_to(db, value_ty)) @@ -1068,7 +1085,7 @@ truthiness } PatternPredicateKind::Class(class_expr, kind) => { - let class_ty = infer_expression_type(db, *class_expr, TypeContext::default()) + let class_ty = infer_same_file_expression_type(db, *class_expr, TypeContext::default()) .as_class_literal() .map(|class| Type::instance(db, class.top_materialization(db))); @@ -1130,7 +1147,7 @@ match predicate.node { PredicateNode::Expression(test_expr) => { - infer_expression_type(db, test_expr, TypeContext::default()) + infer_same_file_expression_type(db, test_expr, TypeContext::default()) .bool(db) .negate_if(!predicate.is_positive) } @@ -1146,7 +1163,7 @@ // selection algorithm). // Avoiding this on the happy-path is important because these constraints can be // very large in number, since we add them on all statement level function calls. - let ty = infer_expression_type(db, callable, TypeContext::default()); + let ty = infer_same_file_expression_type(db, callable, TypeContext::default()); // Short-circuit for well known types that are known not to return `Never` when called. // Without the short-circuit, we've seen that threads keep blocking each other @@ -1184,7 +1201,8 @@ } else if all_overloads_return_never { Truthiness::AlwaysFalse } else { - let call_expr_ty = infer_expression_type(db, call_expr, TypeContext::default()); + let call_expr_ty = + infer_same_file_expression_type(db, call_expr, TypeContext::default()); if call_expr_ty.is_equivalent_to(db, Type::Never) { Truthiness::AlwaysFalse } else { @@ -1268,11 +1286,7 @@ use_def: &'map UseDefMap<'db>, binding: &BindingWithConstraints<'map, 'db>, ) -> Truthiness { - use_def.reachability_constraints().evaluate( - db, - use_def.predicates(), - binding.reachability_constraint, - ) + evaluate_reachability(db, use_def, binding.reachability_constraint) } pub(crate) fn evaluate_reachability( @@ -1285,6 +1299,81 @@ .evaluate(db, use_def.predicates(), reachability) } +pub(crate) struct ReachabilityEvaluationCache<'db> { + primary_scope: ScopeId<'db>, + primary_entries: RefCell<FxHashMap<ScopedReachabilityConstraintId, Truthiness>>, + other_entries: RefCell<FxHashMap<(ScopeId<'db>, ScopedReachabilityConstraintId), Truthiness>>, +} + +impl<'db> ReachabilityEvaluationCache<'db> { + pub(crate) fn new(primary_scope: ScopeId<'db>) -> Self { + Self { + primary_scope, + primary_entries: RefCell::new(FxHashMap::default()), + other_entries: RefCell::new(FxHashMap::default()), + } + } + + pub(crate) fn evaluate( + &self, + db: &'db dyn Db, + scope: ScopeId<'db>, + reachability_constraints: &ReachabilityConstraints, + predicates: &IndexSlice<ScopedPredicateId, Predicate<'db>>, + reachability: ScopedReachabilityConstraintId, + ) -> Truthiness { + match reachability { + ScopedReachabilityConstraintId::ALWAYS_TRUE => return Truthiness::AlwaysTrue, + ScopedReachabilityConstraintId::ALWAYS_FALSE => return Truthiness::AlwaysFalse, + ScopedReachabilityConstraintId::AMBIGUOUS => return Truthiness::Ambiguous, + _ => {} + } + + if scope == self.primary_scope { + if let Some(cached) = self.primary_entries.borrow().get(&reachability) { + return *cached; + } + + let result = reachability_constraints.evaluate(db, predicates, reachability); + self.primary_entries + .borrow_mut() + .insert(reachability, result); + return result; + } + + if let Some(cached) = self.other_entries.borrow().get(&(scope, reachability)) { + return *cached; + } + + let result = reachability_constraints.evaluate(db, predicates, reachability); + self.other_entries + .borrow_mut() + .insert((scope, reachability), result); + result + } +} + +pub(crate) fn evaluate_reachability_with_cache<'db>( + db: &'db dyn Db, + cache: Option<&ReachabilityEvaluationCache<'db>>, + scope: ScopeId<'db>, + reachability_constraints: &ReachabilityConstraints, + predicates: &IndexSlice<ScopedPredicateId, Predicate<'db>>, + reachability: ScopedReachabilityConstraintId, +) -> Truthiness { + if let Some(cache) = cache { + cache.evaluate( + db, + scope, + reachability_constraints, + predicates, + reachability, + ) + } else { + reachability_constraints.evaluate(db, predicates, reachability) + } +} + pub(crate) trait DeclarationsIteratorExtension<'db> { fn any_reachable( self, @@ -1306,6 +1395,7 @@ db: &'db dyn Db, mut predicate: impl FnMut(DefinitionState<'db>) -> bool, ) -> bool { + let scope = self.scope(); let predicates = self.predicates(); let reachability_constraints = self.reachability_constraints(); @@ -1316,9 +1406,15 @@ .. }| { predicate(declaration) - && !reachability_constraints - .evaluate(db, predicates, reachability_constraint) - .is_always_false() + && !evaluate_reachability_with_cache( + db, + None, + scope, + reachability_constraints, + predicates, + reachability_constraint, + ) + .is_always_false() }, ) } @@ -1328,6 +1424,7 @@ db: &'db dyn Db, mut predicate: impl FnMut(DefinitionState<'db>) -> bool, ) -> Option<ScopedDefinitionId> { + let scope = self.scope(); let reachability_predicates = self.predicates(); let reachability_constraints = self.reachability_constraints(); @@ -1338,9 +1435,15 @@ reachability_constraint, }| { (predicate(declaration) - && !reachability_constraints - .evaluate(db, reachability_predicates, reachability_constraint) - .is_always_false()) + && !evaluate_reachability_with_cache( + db, + None, + scope, + reachability_constraints, + reachability_predicates, + reachability_constraint, + ) + .is_always_false()) .then_some(declaration_order) }, )
diff --git a/crates/ty_python_semantic/src/types.rs b/crates/ty_python_semantic/src/types.rs index 450be8f..2368e18 100644 --- a/crates/ty_python_semantic/src/types.rs +++ b/crates/ty_python_semantic/src/types.rs
@@ -28,8 +28,8 @@ pub use self::diagnostic::{TypeCheckDiagnostics, UNDEFINED_REVEAL, UNRESOLVED_REFERENCE}; pub(crate) use self::infer::{ InferredDeclaration, TypeContext, infer_complete_scope_types, infer_deferred_types, - infer_definition_types, infer_expression_type, infer_expression_types, infer_scope_types, - is_discarded_dict_key_assignment, + infer_definition_types, infer_expression_type, infer_expression_types, + infer_same_file_expression_type, infer_scope_types, is_discarded_dict_key_assignment, }; pub(crate) use self::iteration::extract_fixed_length_iterable_element_types; pub use self::known_instance::KnownInstanceType;
diff --git a/crates/ty_python_semantic/src/types/infer/builder.rs b/crates/ty_python_semantic/src/types/infer/builder.rs index 1e15202..bb72c4c 100644 --- a/crates/ty_python_semantic/src/types/infer/builder.rs +++ b/crates/ty_python_semantic/src/types/infer/builder.rs
@@ -33,9 +33,10 @@ RequiresExplicitReExport, TypeOrigin, builtins_module_scope, builtins_symbol, class_body_implicit_symbol, explicit_global_symbol, loop_header_reachability, module_type_implicit_global_declaration, module_type_implicit_global_symbol, place_by_id, - place_from_bindings, place_from_declarations, typing_extensions_symbol, + place_from_bindings_with_reachability_cache, place_from_declarations_with_reachability_cache, + typing_extensions_symbol, }; -use crate::reachability::ReachabilityConstraintsExtension; +use crate::reachability::{ReachabilityEvaluationCache, evaluate_reachability_with_cache}; use crate::types::add_inferred_python_version_hint_to_diagnostic; use crate::types::call::bind::MatchingOverloadIndex; use crate::types::call::{Binding, Bindings, CallArguments, CallError, CallErrorKind}; @@ -236,6 +237,9 @@ /// An expression cache shared across builders during multi-inference. expression_cache: Option<Rc<RefCell<ExpressionCache<'db>>>>, + /// Reachability evaluations reused while inferring this region. + reachability_cache: Rc<ReachabilityEvaluationCache<'db>>, + /// Type qualifiers (`Required`, `NotRequired`, etc.) for annotation expressions. /// Only populated for expressions that have non-empty qualifiers. qualifiers: FxHashMap<ExpressionNodeKey, TypeQualifiers>, @@ -366,6 +370,7 @@ deferred_state: DeferredExpressionState::None, expressions: FxHashMap::default(), expression_cache: None, + reachability_cache: Rc::new(ReachabilityEvaluationCache::new(scope)), qualifiers: FxHashMap::default(), type_expression_flags: FxHashMap::default(), collection_use_constraints: FxHashMap::default(), @@ -1233,8 +1238,12 @@ (use_def.declarations_at_binding(binding), true) }; - let (mut place_and_quals, conflicting) = place_from_declarations(self.db(), declarations) - .into_place_and_conflicting_declarations(); + let (mut place_and_quals, conflicting) = place_from_declarations_with_reachability_cache( + self.db(), + declarations, + &self.reachability_cache, + ) + .into_place_and_conflicting_declarations(); if let Some(conflicting) = conflicting { // TODO point out the conflicting declarations in the diagnostic? @@ -1343,28 +1352,32 @@ let use_def = self.index.use_def_map(declaration.file_scope(self.db())); let prior_bindings = use_def.bindings_at_definition(declaration); // unbound_ty is Never because for this check we don't care about unbound - let inferred_ty = place_from_bindings(self.db(), prior_bindings) - .place - .with_qualifiers(TypeQualifiers::empty()) - .or_fall_back_to(self.db(), || { - // Fallback to bindings declared on `types.ModuleType` if it's a global symbol - let scope = self.scope().file_scope_id(self.db()); - let place = self - .index - .place_table(scope) - .place(declaration.place(self.db())); + let inferred_ty = place_from_bindings_with_reachability_cache( + self.db(), + prior_bindings, + &self.reachability_cache, + ) + .place + .with_qualifiers(TypeQualifiers::empty()) + .or_fall_back_to(self.db(), || { + // Fallback to bindings declared on `types.ModuleType` if it's a global symbol + let scope = self.scope().file_scope_id(self.db()); + let place = self + .index + .place_table(scope) + .place(declaration.place(self.db())); - if let PlaceExprRef::Symbol(symbol) = &place - && scope.is_global() - { - module_type_implicit_global_symbol(self.db(), symbol.name()) - } else { - Place::Undefined.into() - } - }) - .place - .ignore_possibly_undefined() - .unwrap_or(Type::Never); + if let PlaceExprRef::Symbol(symbol) = &place + && scope.is_global() + { + module_type_implicit_global_symbol(self.db(), symbol.name()) + } else { + Place::Undefined.into() + } + }) + .place + .ignore_possibly_undefined() + .unwrap_or(Type::Never); let ty = if inferred_ty.is_assignable_to(self.db(), ty.inner_type()) { ty } else { @@ -2209,11 +2222,13 @@ .symbol_id(&nested_bindings_kind.name) .unwrap(); let use_def = self.index.use_def_map(declaration.file_scope_id); - let Some(ty) = - place_from_bindings(db, use_def.reachable_bindings(nested_symbol_id.into())) - .place - .raw_type() - else { + let Some(ty) = place_from_bindings_with_reachability_cache( + db, + use_def.reachable_bindings(nested_symbol_id.into()), + &self.reachability_cache, + ) + .place + .raw_type() else { continue; }; union.add_in_place(ty); @@ -5061,8 +5076,8 @@ } } - fn return_statement_type_context(&self, has_value: bool) -> TypeContext<'db> { - if has_value { + fn infer_return_statement(&mut self, ret: &ast::StmtReturn) { + let tcx = if ret.value.is_some() { nearest_enclosing_function(self.db(), self.index, self.scope()) .map(|func| { // When inferring expressions within a function body, @@ -5093,136 +5108,7 @@ .unwrap_or_default() } else { TypeContext::default() - } - } - - fn return_call_collection_use_constraints( - &mut self, - statement: Statement<'db>, - use_expression: ExpressionNodeKey, - ) -> Option<FxIndexSet<Type<'db>>> { - fn add_overloads_from_binding<'a, 'db>( - overloads_with_binding: &mut Vec<(&'a Binding<'db>, &'a CallableBinding<'db>)>, - binding: &'a CallableBinding<'db>, - ) { - match binding.matching_overload_index() { - MatchingOverloadIndex::Single(_) | MatchingOverloadIndex::Multiple(_) => { - overloads_with_binding.extend( - binding - .matching_overloads() - .map(|(_, overload)| (overload, binding)), - ); - } - - // If there is a single overload that does not match, normal argument inference still - // uses its parameter context for better diagnostics, so do the same here. - MatchingOverloadIndex::None => { - if let [overload] = binding.overloads() { - overloads_with_binding.push((overload, binding)); - } - } - } - } - - let Statement::Other(statement) = statement else { - return None; }; - - let ast::Stmt::Return(ret) = statement.node_ref(self.db()).node(self.module()) else { - return None; - }; - - let ast::StmtReturn { - value: Some(value), .. - } = ret - else { - return None; - }; - - let ast::Expr::Call(call_expression) = value.as_ref() else { - return None; - }; - - let ast::ExprCall { - func, - arguments, - range: _, - node_index: _, - } = call_expression; - - // Starred arguments need their expression types to bind the call shape. Fall back to the - // full statement query rather than duplicating that logic here. - if arguments - .args - .iter() - .any(|argument| argument.is_starred_expr()) - || arguments - .keywords - .iter() - .any(|keyword| keyword.arg.is_none()) - { - return None; - } - - let argument_index = - arguments - .iter_source_order() - .enumerate() - .find_map(|(index, argument)| { - (ExpressionNodeKey::from(argument.value()) == use_expression).then_some(index) - })?; - - let mut speculative_builder = self.speculate(); - let callable_type = - speculative_builder.infer_maybe_standalone_expression(func, TypeContext::default()); - let call_arguments = CallArguments::from_arguments(arguments, |_, _| Type::unknown()); - let bindings = callable_type - .bindings(self.db()) - .match_parameters(self.db(), &call_arguments); - - if matches!( - bindings.argument_forms().get(argument_index), - Some(Some(ParameterForm::Type)) - ) { - return None; - } - - let mut overloads_with_binding = Vec::new(); - bindings.visit_type_context_callables(&mut |binding| { - add_overloads_from_binding(&mut overloads_with_binding, binding); - }); - - let constraints = ConstraintSetBuilder::new(); - let call_expression_tcx = self.return_statement_type_context(true); - let mut collection_constraints = FxIndexSet::default(); - - for (overload, binding) in overloads_with_binding { - let Some(parameter_context) = overload.argument_type_context( - self.db(), - &constraints, - binding, - &call_arguments, - argument_index, - call_expression_tcx, - ) else { - continue; - }; - - if let Some(parameter_type) = parameter_context.type_context().annotation { - if parameter_type.has_unspecialized_type_var(self.db()) { - return None; - } - - collection_constraints.insert(parameter_type); - } - } - - (!collection_constraints.is_empty()).then_some(collection_constraints) - } - - fn infer_return_statement(&mut self, ret: &ast::StmtReturn) { - let tcx = self.return_statement_type_context(ret.value.is_some()); - if let Some(ty) = self.infer_optional_expression(ret.value.as_deref(), tcx) { let range = ret .value @@ -7066,21 +6952,9 @@ { // For unconstrained collection literals, collect any constraints created by later uses // of this definition in the scope. - let mut seen_constraints = FxIndexSet::default(); for (statement, use_expression) in self.index.constraining_collection_uses(collection_def) { - if let Some(constraints) = - self.return_call_collection_use_constraints(statement, use_expression) - { - for constraint in constraints { - if seen_constraints.insert(constraint) { - builder.infer(identity_instance, constraint).ok()?; - } - } - continue; - } - let statement_use_types = infer_statement_types(self.db(), statement); if let Some(divergent) = statement_use_types @@ -7094,11 +6968,13 @@ generic_context .repeat_specialization(self.db(), Type::Divergent(divergent)) }); - let constraint = Type::instance(self.db(), divergent_instance); - if seen_constraints.insert(constraint) { - builder.infer(identity_instance, constraint).ok()?; - } + builder + .infer( + identity_instance, + Type::instance(self.db(), divergent_instance), + ) + .ok()?; } else if let Some(constraints) = statement_use_types.collection_use_constraints(collection_def) { @@ -7107,9 +6983,7 @@ continue; } - if seen_constraints.insert(*constraint) { - builder.infer(identity_instance, *constraint).ok()?; - } + builder.infer(identity_instance, *constraint).ok()?; } } } @@ -7978,7 +7852,11 @@ let mut elements: Vec<(&str, Type<'db>)> = Vec::new(); for bindings in use_def.multi_bindings_at_use(keyword.scoped_use_id(db, self.file())) { - let place = place_from_bindings(db, bindings.clone()); + let place = place_from_bindings_with_reachability_cache( + db, + bindings.clone(), + &self.reachability_cache, + ); let Some(key) = place.first_definition.and_then(definition_key) else { continue; }; @@ -8845,12 +8723,16 @@ // reveal_type(c.x) # revealed: int // ``` ApplicableConstraints::ConstrainedBindings(bindings) => { + let scope = bindings.scope(); let reachability_constraints = bindings.reachability_constraints(); let predicates = bindings.predicates(); let mut union = UnionBuilder::new(db); for binding in bindings { - let static_reachability = reachability_constraints.evaluate( + let static_reachability = evaluate_reachability_with_cache( db, + Some(&self.reachability_cache), + scope, + reachability_constraints, predicates, binding.reachability_constraint, ); @@ -9018,7 +8900,12 @@ // If we're inferring types of deferred expressions, look them up from end-of-scope. if self.is_deferred() { let place = if let Some(place_id) = place_table.place_id(expr) { - place_from_bindings(db, use_def.reachable_bindings(place_id)).place + place_from_bindings_with_reachability_cache( + db, + use_def.reachable_bindings(place_id), + &self.reachability_cache, + ) + .place } else { assert!( self.in_string_annotation(), @@ -9049,7 +8936,12 @@ } let use_id = expr_ref.scoped_use_id(db, self.file()); - let place = place_from_bindings(db, use_def.bindings_at_use(use_id)).place; + let place = place_from_bindings_with_reachability_cache( + db, + use_def.bindings_at_use(use_id), + &self.reachability_cache, + ) + .place; (place, Some(use_id)) } @@ -9098,7 +8990,11 @@ return Place::Undefined.into(); } EnclosingSnapshotResult::FoundBindings(bindings) => { - let mut place_and_qualifiers = place_from_bindings(db, bindings); + let mut place_and_qualifiers = place_from_bindings_with_reachability_cache( + db, + bindings, + &self.reachability_cache, + ); if assume_bound && let Place::Defined(defined) = place_and_qualifiers.place { place_and_qualifiers.place = Place::Defined(defined.with_definedness(Definedness::AlwaysDefined)); @@ -9303,7 +9199,13 @@ } } EnclosingSnapshotResult::FoundBindings(bindings) => { - let place = place_from_bindings(db, bindings).place.map_type(|ty| { + let place = place_from_bindings_with_reachability_cache( + db, + bindings, + &self.reachability_cache, + ) + .place + .map_type(|ty| { self.narrow_place_with_applicable_constraints( place_expr, ty, @@ -10332,6 +10234,7 @@ // builder only state expression_cache: _, + reachability_cache: _, typevar_binding_context: _, deferred_state: _, called_functions: _, @@ -10413,6 +10316,7 @@ // builder only state expression_cache: _, + reachability_cache: _, dataclass_field_specifiers: _, typevar_binding_context: _, deferred_state: _, @@ -10507,6 +10411,7 @@ bindings, called_functions, expression_cache: _, + reachability_cache: _, declarations: _, deferred: _, scope: _, @@ -10561,6 +10466,7 @@ // builder only state expression_cache: _, + reachability_cache: _, dataclass_field_specifiers: _, typevar_binding_context: _, deferred_state: _, @@ -10653,6 +10559,7 @@ // Builder only state expression_cache: _, + reachability_cache: _, dataclass_field_specifiers: _, typevar_binding_context: _, deferred_state: _, @@ -10706,6 +10613,7 @@ deferred_state, typevar_binding_context, ref expression_cache, + ref reachability_cache, ref return_types_and_ranges, ref dataclass_field_specifiers, @@ -10738,6 +10646,7 @@ builder.typevar_binding_context = typevar_binding_context; builder.context.inference_flags = self.inference_flags(); builder.expression_cache.clone_from(expression_cache); + builder.reachability_cache.clone_from(reachability_cache); builder .return_types_and_ranges .clone_from(return_types_and_ranges); @@ -10770,6 +10679,7 @@ // builder only state expression_cache: _, + reachability_cache: _, typevar_binding_context: _, deferred_state: _, called_functions: _,