Skip to content

Commit 2f0a29e

Browse files
[ty] Record predicate truthiness alongside expression inference (#29706)
## Summary A full ty check of isort went from 204 to 172 ms in the ecosystem run. Across all 163 projects, the average timing factor was 1.00×. Local checks of two isort revisions on macOS took 16–23% less time. [Ecosystem timings](https://dqhfo45wdv0ek.cloudfront.net/ruff/pull-requests/29706/ty-ecosystem/40342132072/1/timing.html) In `if bool(stop()):`, the call to `bool` has type `bool`, but neither branch can run if `stop()` returns `Never`. Ty uses the operand types to work this out. In a loop, those types can depend on an assignment guarded by the same condition. Computing types and truthiness in separate queries can make ty revisit that loop repeatedly. We now record each predicate’s evaluation context when we index it. Expression inference computes the predicate’s truthiness alongside its operand types and recomputes it if cycle recovery widens them. Ordinary conditions and match guards both read that result. The only warning that changed consistently across ecosystem runs was in psycopg. It now lists the `int` class separately even though `type[str | Any | int]` already includes it. [Ecosystem diff](https://dqhfo45wdv0ek.cloudfront.net/ruff/pull-requests/29706/ty-ecosystem/40342132072/1/diff.html)
1 parent 60f104a commit 2f0a29e

11 files changed

Lines changed: 150 additions & 165 deletions

File tree

‎crates/ty_python_core/src/builder.rs‎

Lines changed: 42 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -2209,7 +2209,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
22092209
&mut self,
22102210
predicate_node: &'ast ast::Expr,
22112211
) -> (PredicateOrLiteral<'db>, ScopedPredicateId) {
2212-
let predicate = self.build_predicate(predicate_node, ExpressionContext::Condition);
2212+
let predicate = self.build_predicate(predicate_node, ExpressionContext::Condition, None);
22132213
let predicate_id = self.record_narrowing_constraint(predicate);
22142214
(predicate, predicate_id)
22152215
}
@@ -2218,6 +2218,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
22182218
&mut self,
22192219
predicate_node: &'ast ast::Expr,
22202220
context: ExpressionContext,
2221+
registered: Option<Expression<'db>>,
22212222
) -> PredicateOrLiteral<'db> {
22222223
// Some commonly used test expressions are eagerly evaluated as `true`
22232224
// or `false` here for performance reasons. This list does not need to
@@ -2245,35 +2246,19 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
22452246

22462247
self.register_narrowing_alias_predicates(predicate_node);
22472248

2248-
let expression = self.add_standalone_expression(predicate_node);
2249-
2250-
match resolve_to_literal(predicate_node) {
2251-
Some(literal) => PredicateOrLiteral::Literal(literal),
2252-
None => PredicateOrLiteral::Predicate(Predicate {
2253-
node: match (context, predicate_node) {
2254-
(
2255-
ExpressionContext::Condition,
2256-
ast::Expr::BoolOp(_)
2257-
| ast::Expr::If(_)
2258-
| ast::Expr::UnaryOp(ast::ExprUnaryOp {
2259-
op: ast::UnaryOp::Not,
2260-
..
2261-
}),
2262-
) => PredicateNode::Condition(expression),
2263-
(ExpressionContext::Condition, ast::Expr::Compare(compare))
2264-
if compare.ops.len() > 1 =>
2265-
{
2266-
PredicateNode::Condition(expression)
2267-
}
2268-
_ => PredicateNode::Expression {
2269-
expression,
2270-
truthiness_from_type: predicate_node.is_name_expr()
2271-
|| predicate_node.is_literal_expr(),
2272-
},
2273-
},
2274-
is_positive: true,
2275-
}),
2249+
if let Some(literal) = resolve_to_literal(predicate_node) {
2250+
if registered.is_none() {
2251+
self.add_standalone_expression(predicate_node);
2252+
}
2253+
return PredicateOrLiteral::Literal(literal);
22762254
}
2255+
2256+
let expression =
2257+
registered.unwrap_or_else(|| self.add_predicate_expression(predicate_node, context));
2258+
PredicateOrLiteral::Predicate(Predicate {
2259+
node: PredicateNode::Expression(expression),
2260+
is_positive: true,
2261+
})
22772262
}
22782263

22792264
fn visit_condition(&mut self, test: &'ast ast::Expr) {
@@ -2405,8 +2390,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
24052390
let place_table = self.current_place_table();
24062391

24072392
match pred.node {
2408-
PredicateNode::Expression { expression, .. }
2409-
| PredicateNode::Condition(expression) => {
2393+
PredicateNode::Expression(expression) => {
24102394
let expression_node = expression.node_ref(self.db).node(self.module);
24112395
let mut places = PossiblyNarrowedPlacesBuilder::new(self.db, place_table)
24122396
.expression(expression_node);
@@ -2838,7 +2822,8 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
28382822
// See the comment in TypeInferenceBuilder::infer_match_pattern for more details.
28392823

28402824
let kind = self.predicate_kind(pattern);
2841-
let guard = guard.map(|guard| self.add_standalone_expression(guard));
2825+
let guard =
2826+
guard.map(|guard| self.add_predicate_expression(guard, ExpressionContext::Condition));
28422827

28432828
PatternPredicate::new(
28442829
self.db,
@@ -2908,6 +2893,22 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
29082893
self.add_standalone_expression_impl(expression_node, ExpressionKind::Normal, None)
29092894
}
29102895

2896+
/// Record a predicate in the context in which Python tests it.
2897+
fn add_predicate_expression(
2898+
&mut self,
2899+
node: &ast::Expr,
2900+
context: ExpressionContext,
2901+
) -> Expression<'db> {
2902+
self.add_standalone_expression_impl(
2903+
node,
2904+
ExpressionKind::Predicate {
2905+
context,
2906+
in_loop: self.in_loop_context(),
2907+
},
2908+
None,
2909+
)
2910+
}
2911+
29112912
/// Record an expression that is immediately assigned to a target, and that needs to be a Salsa
29122913
/// ingredient, because we need to infer its type standalone (type narrowing tests, RHS of an
29132914
/// assignment.)
@@ -3755,7 +3756,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
37553756
value,
37563757
));
37573758
let condition_flow_snapshots = self.take_condition_flow_snapshots(value);
3758-
let predicate = self.build_predicate(value, context);
3759+
let predicate = self.build_predicate(value, context, None);
37593760
let possibly_narrowed = self.compute_possibly_narrowed_places(&predicate);
37603761
let predicate_id = match op {
37613762
ast::BoolOp::And => self.add_predicate(predicate),
@@ -4297,7 +4298,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
42974298

42984299
self.visit_condition(test);
42994300
let condition_flow_snapshot = self.flow_snapshot_for_condition(test);
4300-
let predicate = self.build_predicate(test, ExpressionContext::Condition);
4301+
let predicate = self.build_predicate(test, ExpressionContext::Condition, None);
43014302

43024303
if msg.is_some()
43034304
|| self
@@ -4615,6 +4616,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
46154616

46164617
// Visit the test expression after creating loop headers, so that loop-back values
46174618
// are visible.
4619+
let outer_loop = self.push_loop();
46184620
self.visit_condition(test);
46194621
let condition_flow_snapshot = self.flow_snapshot_for_condition(test);
46204622

@@ -4628,7 +4630,6 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
46284630
let (predicate, predicate_id) = self.record_expression_narrowing_constraint(test);
46294631
self.record_reachability_constraint_id(predicate_id);
46304632

4631-
let outer_loop = self.push_loop();
46324633
self.visit_body(body);
46334634
let this_loop = self.pop_loop(outer_loop);
46344635

@@ -5003,8 +5004,12 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
50035004
self.flow_snapshot()
50045005
};
50055006

5006-
let (guard_predicate, guard_predicate_id) =
5007-
self.record_expression_narrowing_constraint(guard);
5007+
let guard_predicate = self.build_predicate(
5008+
guard,
5009+
ExpressionContext::Condition,
5010+
match_pattern_predicate.guard(self.db),
5011+
);
5012+
let guard_predicate_id = self.record_narrowing_constraint(guard_predicate);
50085013
let guard_reachability_constraint =
50095014
self.record_reachability_constraint_id(guard_predicate_id);
50105015
let guard_success = self.flow_snapshot();

‎crates/ty_python_core/src/expression.rs‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@ use salsa;
7878
/// Condition context does not propagate through calls or assignment expressions: in
7979
/// `if f(x and False)`, the call's result controls the branch, but its argument is evaluated in
8080
/// value context.
81-
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
81+
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, get_size2::GetSize)]
8282
pub enum ExpressionContext {
8383
/// Produce the expression's result object for the enclosing code to use.
8484
Value,
@@ -91,6 +91,11 @@ pub enum ExpressionContext {
9191
pub enum ExpressionKind {
9292
/// An ordinary value expression, such as `1` in `self.x: int = 1`.
9393
Normal,
94+
/// A predicate whose truthiness is recorded in its evaluation context.
95+
Predicate {
96+
context: ExpressionContext,
97+
in_loop: bool,
98+
},
9499
/// The callable part of a call, such as `list[T]` in `list[T]()`.
95100
///
96101
/// Type variables used to specialize the callable must already be bound. A constructor call

‎crates/ty_python_core/src/predicate.rs‎

Lines changed: 2 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -160,18 +160,8 @@ impl<'ast> StatementCall<'ast> {
160160

161161
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
162162
pub enum PredicateNode<'db> {
163-
/// The truthiness of an expression's resulting value.
164-
Expression {
165-
expression: Expression<'db>,
166-
/// Names and literals need only their inferred type, avoiding a separate truthiness query.
167-
truthiness_from_type: bool,
168-
},
169-
/// A boolean operation, `not`, conditional expression, or chained comparison evaluated
170-
/// directly as a condition.
171-
///
172-
/// In `if x and False`, the truthy branch is unreachable. But after `y = x and False`,
173-
/// `if y` may be truthy: it can call `x.__bool__` a second time and get a different result.
174-
Condition(Expression<'db>),
163+
/// The truthiness of an expression in its evaluation context.
164+
Expression(Expression<'db>),
175165
/// Whether a context manager's exit return type allows an exception to be suppressed.
176166
///
177167
/// Resolved during type inference because the context manager's type is unavailable during

‎crates/ty_python_semantic/src/reachability.rs‎

Lines changed: 8 additions & 90 deletions
Original file line numberDiff line numberDiff line change
@@ -202,14 +202,13 @@ use crate::{
202202
place::{DefinedPlace, Definedness, Place, RequiresExplicitReExport, imported_symbol},
203203
types::{
204204
CallableType, ComparisonSoundnessPolicy, EnumClassLiteral, KnownInstanceType,
205-
NarrowingConstraint, SpecialFormType, TruthinessAnalyzer, Type, TypeContext, UnionType,
205+
NarrowingConstraint, SpecialFormType, Type, TypeContext, UnionType,
206206
definite_match_pattern_type, definite_match_pattern_type_for_subject, equality_truthiness,
207-
expand_type, infer_expression_types, infer_narrowing_constraints,
207+
expand_type, infer_narrowing_constraints, infer_predicate_truthiness,
208208
infer_same_file_expression_type, mapping_pattern_type, pattern_binding_fallthrough_type,
209209
sequence_pattern_type_builder, singleton_pattern_type,
210210
},
211211
};
212-
use ruff_db::parsed::parsed_module;
213212
use ruff_index::{Idx, IndexSlice};
214213
use ruff_python_ast::name::Name;
215214
use ruff_text_size::TextRange;
@@ -220,7 +219,7 @@ use ty_python_core::{
220219
FileScopeId, NarrowingEvaluator, PredicateNarrowingTargets, ScopedDefinitionId, SemanticIndex,
221220
Truthiness, UseDefMap,
222221
definition::{DefinitionKind, DefinitionState},
223-
expression::{Expression, ExpressionContext},
222+
expression::Expression,
224223
narrowing_constraints::{NarrowingConstraints, ScopedNarrowingConstraint},
225224
place::ScopedPlaceId,
226225
place_table,
@@ -313,7 +312,7 @@ fn pattern_guard_allows_all_matches(db: &dyn Db, predicate: PatternPredicate<'_>
313312
// Condition analysis recovers cycles as ambiguous, so an unresolved guard cannot exclude values.
314313
predicate
315314
.guard(db)
316-
.is_none_or(|guard| condition_truthiness(db, guard).is_always_true())
315+
.is_none_or(|guard| infer_predicate_truthiness(db, guard).is_always_true())
317316
}
318317

319318
/// Narrow `subject_ty` by a match pattern.
@@ -595,8 +594,7 @@ const CONTROL_FLOW_REACHABILITY_CHECKPOINT_INTERVAL: usize = 16;
595594
const NARROWING_EVALUATION_CHECKPOINT_INTERVAL: usize = 8;
596595
fn predicate_scope<'db>(db: &'db dyn Db, predicate: &Predicate<'db>) -> ScopeId<'db> {
597596
match predicate.node {
598-
PredicateNode::Expression { expression, .. }
599-
| PredicateNode::Condition(expression)
597+
PredicateNode::Expression(expression)
600598
| PredicateNode::ContextManagerSuppresses { expression, .. } => expression.scope(db),
601599
PredicateNode::IsNonTerminalCall(call) => call.callable(db).scope(db),
602600
PredicateNode::Pattern(pattern) => pattern.scope(db),
@@ -1946,62 +1944,6 @@ fn context_manager_suppresses<'db>(
19461944
)
19471945
}
19481946

1949-
/// Test an expression's result object, accounting for operands that cannot complete.
1950-
/// Separate value and condition queries use the expression directly as their Salsa key, avoiding
1951-
/// an additional interner for pairs of expressions and evaluation contexts.
1952-
#[salsa::tracked(
1953-
returns(copy),
1954-
cycle_initial = |_, _, _| Truthiness::Ambiguous,
1955-
cycle_fn = |_, cycle: &salsa::Cycle, previous: &Truthiness, result: Truthiness, _| widen_truthiness(cycle, *previous, result),
1956-
heap_size = get_size2::GetSize::get_heap_size
1957-
)]
1958-
fn value_truthiness<'db>(db: &'db dyn Db, expression: Expression<'db>) -> Truthiness {
1959-
expression_truthiness(db, expression, ExpressionContext::Value)
1960-
}
1961-
1962-
/// Follow short-circuit conditions without testing their result objects again.
1963-
#[salsa::tracked(
1964-
returns(copy),
1965-
cycle_initial = |_, _, _| Truthiness::Ambiguous,
1966-
cycle_fn = |_, cycle: &salsa::Cycle, previous: &Truthiness, result: Truthiness, _| widen_truthiness(cycle, *previous, result),
1967-
heap_size = get_size2::GetSize::get_heap_size
1968-
)]
1969-
fn condition_truthiness<'db>(db: &'db dyn Db, expression: Expression<'db>) -> Truthiness {
1970-
expression_truthiness(db, expression, ExpressionContext::Condition)
1971-
}
1972-
1973-
fn widen_truthiness(cycle: &salsa::Cycle, previous: Truthiness, result: Truthiness) -> Truthiness {
1974-
// A condition can control whether one of its own inputs is reachable. Expression inference
1975-
// can lose its previous result when it ceases to be a cycle head, so its type widening alone
1976-
// does not ensure that the condition's truthiness converges. Delay widening here to avoid
1977-
// retaining imprecise results from the first few iterations.
1978-
if cycle.iteration() > crate::TAINTED_CYCLES {
1979-
previous.union(result)
1980-
} else {
1981-
result
1982-
}
1983-
}
1984-
1985-
/// Keep this separate from type inference: `bool(never)` has type `bool`, but cannot produce a
1986-
/// boolean outcome. The calling query caches that distinction and widens it during inference cycles.
1987-
fn expression_truthiness<'db>(
1988-
db: &'db dyn Db,
1989-
expression: Expression<'db>,
1990-
context: ExpressionContext,
1991-
) -> Truthiness {
1992-
let env = ProgramEnvironment::from_scope(expression.scope(db));
1993-
let module = parsed_module(db, expression.python_file(db)).load(db);
1994-
let inference = infer_expression_types(db, expression, TypeContext::default());
1995-
let node = expression.node_ref(db).node(&module);
1996-
TruthinessAnalyzer::new(
1997-
db,
1998-
&env,
1999-
|node| inference.expression_type(node),
2000-
|node| inference.comparison_truthiness(node),
2001-
)
2002-
.truthiness(node, context)
2003-
}
2004-
20051947
/// Evaluate a predicate, returning `Uninhabited` when it cannot produce a boolean outcome.
20061948
///
20071949
/// Unlike ambiguous truthiness, an uninhabited condition does not make either branch reachable.
@@ -2011,24 +1953,8 @@ fn analyze_single(db: &dyn Db, env: &ProgramEnvironment<'_>, predicate: &Predica
20111953
let _span = tracing::trace_span!("analyze_single", ?predicate).entered();
20121954

20131955
match predicate.node {
2014-
PredicateNode::Expression {
2015-
expression: test_expr,
2016-
truthiness_from_type: true,
2017-
} => {
2018-
let inference = infer_expression_types(db, test_expr, TypeContext::default());
2019-
let ty = inference.expression_type(test_expr.node_ref(db));
2020-
if ty.is_equivalent_to(db, env, Type::Never) {
2021-
Truthiness::Uninhabited
2022-
} else {
2023-
ty.bool(db, env).negate_if(!predicate.is_positive)
2024-
}
2025-
}
2026-
PredicateNode::Expression {
2027-
expression: test_expr,
2028-
truthiness_from_type: false,
2029-
} => value_truthiness(db, test_expr).negate_if(!predicate.is_positive),
2030-
PredicateNode::Condition(test_expr) => {
2031-
condition_truthiness(db, test_expr).negate_if(!predicate.is_positive)
1956+
PredicateNode::Expression(expression) => {
1957+
infer_predicate_truthiness(db, expression).negate_if(!predicate.is_positive)
20321958
}
20331959
PredicateNode::ContextManagerSuppresses {
20341960
expression,
@@ -2460,15 +2386,7 @@ class TargetB:
24602386
let predicate = use_def
24612387
.predicates()
24622388
.iter()
2463-
.find(|predicate| {
2464-
matches!(
2465-
predicate.node,
2466-
PredicateNode::Expression {
2467-
truthiness_from_type: true,
2468-
..
2469-
}
2470-
)
2471-
})
2389+
.find(|predicate| matches!(predicate.node, PredicateNode::Expression(_)))
24722390
.unwrap();
24732391
let predicates: Predicates = std::iter::repeat_n(*predicate, DEPTH).collect();
24742392

‎crates/ty_python_semantic/src/types.rs‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -38,9 +38,10 @@ pub(crate) use self::diagnostic::TypeCheckDiagnostics;
3838
pub(crate) use self::diagnostic::register_lints;
3939
pub use self::diagnostic::{UNDEFINED_REVEAL, UNRESOLVED_REFERENCE};
4040
pub(crate) use self::infer::{
41-
InferredDeclaration, TruthinessAnalyzer, TypeContext, infer_complete_scope_types,
42-
infer_deferred_types, infer_definition_types, infer_expression_type, infer_expression_types,
43-
infer_same_file_expression_type, infer_scope_types, is_discarded_dict_key_assignment,
41+
InferredDeclaration, TypeContext, infer_complete_scope_types, infer_deferred_types,
42+
infer_definition_types, infer_expression_type, infer_expression_types,
43+
infer_predicate_truthiness, infer_same_file_expression_type, infer_scope_types,
44+
is_discarded_dict_key_assignment,
4445
};
4546
use self::infer::{
4647
infer_function_default_types, infer_legacy_type_alias, legacy_type_alias_parameters,

0 commit comments

Comments
 (0)