ty_python_core/
predicate.rs

1//! _Predicates_ are Python expressions whose runtime values can affect type inference.
2//!
3//! We currently use predicates in two places:
4//!
5//! - [_Narrowing constraints_][crate::narrowing_constraints] constrain the type of
6//!   a binding that is visible at a particular use.
7//! - [_Reachability constraints_][crate::reachability_constraints] determine the
8//!   static reachability of a binding, and the reachability of a statement or expression.
9
10use crate::Program;
11use ruff_db::PythonFile;
12use ruff_db::files::File;
13use ruff_index::{FrozenIndexVec, Idx, IndexVec};
14use ruff_python_ast::{Singleton, name::Name};
15
16use crate::ProgramFile;
17use crate::ast_ids::ExpressionNodeKey;
18use crate::db::Db;
19use crate::expression::Expression;
20use crate::global_scope;
21use crate::reachability_constraints::ScopedReachabilityConstraintId;
22use crate::scope::{FileScopeId, ScopeId};
23use crate::symbol::ScopedSymbolId;
24
25// A scoped identifier for each `Predicate` in a scope.
26#[derive(Clone, Debug, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, get_size2::GetSize)]
27pub struct ScopedPredicateId(u32);
28
29impl ScopedPredicateId {
30    /// A special ID that is used for an "always true" predicate.
31    pub(crate) const ALWAYS_TRUE: ScopedPredicateId = ScopedPredicateId(0xffff_ffff);
32
33    /// A special ID that is used for an "always false" predicate.
34    pub(crate) const ALWAYS_FALSE: ScopedPredicateId = ScopedPredicateId(0xffff_fffe);
35
36    const SMALLEST_TERMINAL: ScopedPredicateId = Self::ALWAYS_FALSE;
37
38    fn is_terminal(self) -> bool {
39        self >= Self::SMALLEST_TERMINAL
40    }
41}
42
43impl Idx for ScopedPredicateId {
44    #[inline]
45    fn new(value: usize) -> Self {
46        assert!(value <= (Self::SMALLEST_TERMINAL.0 as usize));
47        #[expect(clippy::cast_possible_truncation)]
48        Self(value as u32)
49    }
50
51    #[inline]
52    fn index(self) -> usize {
53        debug_assert!(!self.is_terminal());
54        self.0 as usize
55    }
56}
57
58// A collection of predicates for a given scope.
59pub type Predicates<'db> = FrozenIndexVec<ScopedPredicateId, Predicate<'db>>;
60
61#[derive(Debug, Default)]
62pub(crate) struct PredicatesBuilder<'db> {
63    predicates: IndexVec<ScopedPredicateId, Predicate<'db>>,
64}
65
66impl<'db> PredicatesBuilder<'db> {
67    /// Adds a predicate. Note that we do not deduplicate predicates. If you add a `Predicate`
68    /// more than once, you will get distinct `ScopedPredicateId`s for each one. (This lets you
69    /// model predicates that might evaluate to different values at different points of execution.)
70    pub(crate) fn add_predicate(&mut self, predicate: Predicate<'db>) -> ScopedPredicateId {
71        self.predicates.push(predicate)
72    }
73
74    pub(crate) fn build(self) -> Predicates<'db> {
75        self.predicates.into()
76    }
77}
78
79#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
80pub struct Predicate<'db> {
81    pub node: PredicateNode<'db>,
82    pub is_positive: bool,
83}
84
85#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize)]
86pub(crate) enum PredicateOrLiteral<'db> {
87    Literal(bool),
88    Predicate(Predicate<'db>),
89}
90
91impl PredicateOrLiteral<'_> {
92    pub(crate) fn negated(self) -> Self {
93        match self {
94            PredicateOrLiteral::Literal(value) => PredicateOrLiteral::Literal(!value),
95            PredicateOrLiteral::Predicate(Predicate { node, is_positive }) => {
96                PredicateOrLiteral::Predicate(Predicate {
97                    node,
98                    is_positive: !is_positive,
99                })
100            }
101        }
102    }
103}
104
105#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
106pub struct CallableAndCallExpr<'db> {
107    pub callable: Expression<'db>,
108    pub call_expr: Expression<'db>,
109    /// Whether the call is wrapped in an `await` expression. If `true`, `call_expr` refers to the
110    /// `await` expression rather than the call itself. This is used to detect terminal `await`s of
111    /// async functions that return `Never`.
112    pub is_await: bool,
113}
114
115#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
116pub enum PredicateNode<'db> {
117    Expression(Expression<'db>),
118    /// Whether a context manager's exit return type allows an exception to be suppressed.
119    ///
120    /// Resolved during type inference because the context manager's type is unavailable during
121    /// semantic indexing.
122    ContextManagerSuppresses {
123        expression: Expression<'db>,
124        is_async: bool,
125    },
126    /// Whether semantic evaluation rules out every normal entry into a `finally` suite.
127    ///
128    /// The continuation is captured before constructing this predicate, so its constraint cannot
129    /// depend on the predicate itself. Deferring evaluation preserves terminal cleanup paths when
130    /// a context manager's suppression behavior is unavailable during semantic indexing.
131    FinallyNormalPathImpossible {
132        scope: ScopeId<'db>,
133        continuation: ScopedReachabilityConstraintId,
134    },
135    /// These predicates are recorded for statements with call expressions. As part of
136    /// reachability constraints, they are used to determine whether control flow can
137    /// continue past this statement or not.
138    ///
139    /// The predicate evaluates to
140    /// [`crate::Truthiness::AlwaysTrue`] in the common case where a call
141    /// is inferred as returning an inhabited type: in these situations, we will
142    /// infer control flow as flowing through the call expression without
143    /// terminating. If it can be statically guaranteed that a call always
144    /// returns `Never`/`NoReturn`, however, the predicate evaluates to
145    /// [`crate::Truthiness::AlwaysFalse`], signaling that control flow
146    /// ends as a result of the call: these call expressions are terminal.
147    ///
148    /// These predicates never evaluate to
149    /// [`crate::Truthiness::Ambiguous`], even if the return type of the
150    /// call is `Unknown`/`Any`, because that would result in too many false
151    /// positives.
152    IsNonTerminalCall(CallableAndCallExpr<'db>),
153    /// Whether an iterable is statically known to yield at least one item.
154    ///
155    /// Currently, this predicate is only emitted for direct `range(...)` calls. It is resolved
156    /// semantically during type checking, so calls to a shadowed `range` remain ambiguous.
157    IsNonEmptyIterable(Expression<'db>),
158    Pattern(PatternPredicate<'db>),
159    /// Whether control flow takes one branch of an OR pattern instead of its remaining
160    /// alternatives. The selected branch is unknown, but recording a predicate and its negation
161    /// preserves the fact that exactly one branch is taken.
162    OrPatternAlternative(ScopeId<'db>),
163    SubjectElementPattern(SubjectElementPatternPredicate<'db>),
164    StarImportPlaceholder(StarImportPlaceholderPredicate<'db>),
165}
166
167/// A pattern predicate applied to one expression in a sequence-display subject.
168///
169/// The full pattern determines the predicate's truth value, while `target` selects the subject
170/// occurrence whose aligned pattern constraint should be applied to a binding.
171#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
172pub struct SubjectElementPatternPredicate<'db> {
173    pub pattern: PatternPredicate<'db>,
174    pub target: ExpressionNodeKey,
175}
176
177/// Structural details for sequence patterns that affect narrowing and reachability.
178#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
179pub struct SequencePatternPredicateKind<'db> {
180    pub patterns: Box<[PatternPredicateKind<'db>]>,
181}
182
183impl<'db> SequencePatternPredicateKind<'db> {
184    /// Return `true` for `case [*rest]`, the only sequence pattern with no
185    /// length or element constraints.
186    pub fn is_irrefutable(&self) -> bool {
187        matches!(self.patterns.as_ref(), [PatternPredicateKind::Star(_)])
188    }
189
190    /// Return the patterns before and after the starred element.
191    pub fn split_around_star(
192        &self,
193    ) -> Option<(&[PatternPredicateKind<'db>], &[PatternPredicateKind<'db>])> {
194        let star_index = self
195            .patterns
196            .iter()
197            .position(|pattern| matches!(pattern, PatternPredicateKind::Star(_)))?;
198        let (prefix, star_and_suffix) = self.patterns.split_at(star_index);
199        Some((prefix, &star_and_suffix[1..]))
200    }
201}
202
203/// Structural details for a class pattern.
204#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
205pub struct ClassPatternPredicateKind<'db> {
206    pub class: Expression<'db>,
207    pub positional: Box<[PatternPredicateKind<'db>]>,
208    pub keywords: Box<[ClassPatternKeywordPredicateKind<'db>]>,
209}
210
211impl ClassPatternPredicateKind<'_> {
212    pub fn is_empty(&self) -> bool {
213        self.positional.is_empty() && self.keywords.is_empty()
214    }
215}
216
217#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
218pub struct ClassPatternKeywordPredicateKind<'db> {
219    pub attr: Name,
220    pub pattern: PatternPredicateKind<'db>,
221}
222
223/// Structural details for a mapping pattern.
224#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
225pub struct MappingPatternPredicateKind<'db> {
226    pub entries: Box<[MappingPatternEntryPredicateKind<'db>]>,
227    pub rest: Option<Name>,
228}
229
230impl MappingPatternPredicateKind<'_> {
231    pub fn is_irrefutable(&self) -> bool {
232        self.entries.is_empty()
233    }
234}
235
236#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
237pub struct MappingPatternEntryPredicateKind<'db> {
238    pub key: Expression<'db>,
239    pub pattern: PatternPredicateKind<'db>,
240}
241
242/// Pattern structure used for type narrowing, static reachability, and inferring the types of
243/// names bound by a successful match.
244#[derive(Debug, Clone, Hash, PartialEq, get_size2::GetSize, salsa::SalsaValue)]
245pub enum PatternPredicateKind<'db> {
246    Singleton(Singleton),
247    Value(Expression<'db>),
248    Or(Box<[PatternPredicateKind<'db>]>),
249    Class(ClassPatternPredicateKind<'db>),
250    Mapping(MappingPatternPredicateKind<'db>),
251    Sequence(SequencePatternPredicateKind<'db>),
252    As(Option<Box<PatternPredicateKind<'db>>>, Option<Name>),
253    Star(Option<Name>),
254}
255
256#[salsa::tracked(debug, heap_size=ruff_memory_usage::heap_size)]
257pub struct PatternPredicate<'db> {
258    #[returns(copy)]
259    pub program_file: ProgramFile<'db>,
260
261    #[returns(copy)]
262    pub file_scope: FileScopeId,
263
264    #[returns(copy)]
265    pub subject: Expression<'db>,
266
267    #[returns(ref)]
268    pub kind: PatternPredicateKind<'db>,
269
270    #[returns(copy)]
271    pub guard: Option<Expression<'db>>,
272
273    /// A reference to the pattern of the previous match case
274    #[returns(as_deref)]
275    pub previous_predicate: Option<Box<PatternPredicate<'db>>>,
276}
277
278// The Salsa heap is tracked separately.
279impl get_size2::GetSize for PatternPredicate<'_> {}
280
281impl<'db> PatternPredicate<'db> {
282    pub fn file(self, db: &'db dyn Db) -> File {
283        self.program_file(db).file(db)
284    }
285
286    pub fn python_file(self, db: &'db dyn Db) -> PythonFile<'db> {
287        self.program_file(db).python_file(db)
288    }
289
290    pub fn scope(self, db: &'db dyn Db) -> ScopeId<'db> {
291        self.file_scope(db).to_scope_id(db, self.program_file(db))
292    }
293
294    pub fn program(self, db: &'db dyn Db) -> Program<'db> {
295        self.scope(db).program(db)
296    }
297}
298
299/// A "placeholder predicate" that is used to model the fact that the boundness of a (possible)
300/// definition or declaration caused by a `*` import cannot be fully determined until type-
301/// inference time. This is essentially the same as a standard reachability constraint, so we reuse
302/// the [`Predicate`] infrastructure to model it.
303///
304/// To illustrate, say we have a module `exporter.py` like so:
305///
306/// ```py
307/// if <condition>:
308///     class A: ...
309/// ```
310///
311/// and we have a module `importer.py` like so:
312///
313/// ```py
314/// A = 1
315///
316/// from exporter import *
317/// ```
318///
319/// Since we cannot know whether or not <condition> is true at semantic-index time, we record
320/// a definition for `A` in `importer.py` as a result of the `from exporter import *` statement,
321/// but place a predicate on it to record the fact that we don't yet know whether this definition
322/// will be visible from all control-flow paths or not. Essentially, we model `importer.py` as
323/// something similar to this:
324///
325/// ```py
326/// A = 1
327///
328/// if <star_import_placeholder_predicate>:
329///     from a import A
330/// ```
331///
332/// At type-check time, the placeholder predicate for the `A` definition is evaluated by attempting
333/// to resolve the `A` symbol in `exporter.py`'s global namespace:
334/// - If it resolves to a definitely bound symbol, then the predicate resolves to [`Truthiness::AlwaysTrue`]
335/// - If it resolves to an unbound symbol, then the predicate resolves to [`Truthiness::AlwaysFalse`]
336/// - If it resolves to a possibly bound symbol, then the predicate resolves to [`Truthiness::Ambiguous`]
337///
338/// [Truthiness]: [crate::types::Truthiness]
339#[salsa::tracked(debug, heap_size=ruff_memory_usage::heap_size)]
340pub struct StarImportPlaceholderPredicate<'db> {
341    #[returns(copy)]
342    pub importing_file: ProgramFile<'db>,
343
344    /// Each symbol imported by a `*` import has a separate predicate associated with it:
345    /// this field identifies which symbol that is.
346    ///
347    /// Note that a [`ScopedPlaceId`] is only meaningful if you also know the scope
348    /// it is relative to. For this specific struct, however, there's no need to store a
349    /// separate field to hold the ID of the scope. `StarImportPredicate`s are only created
350    /// for valid `*`-import definitions, and valid `*`-import definitions can only ever
351    /// exist in the global scope; thus, we know that the `symbol_id` here will be relative
352    /// to the global scope of the importing file.
353    #[returns(copy)]
354    pub symbol_id: ScopedSymbolId,
355
356    #[returns(copy)]
357    pub referenced_file: ProgramFile<'db>,
358}
359
360// The Salsa heap is tracked separately.
361impl get_size2::GetSize for StarImportPlaceholderPredicate<'_> {}
362
363impl<'db> StarImportPlaceholderPredicate<'db> {
364    pub fn scope(self, db: &'db dyn Db) -> ScopeId<'db> {
365        // See doc-comment above [`StarImportPlaceholderPredicate::symbol_id`]:
366        // valid `*`-import definitions can only take place in the global scope.
367        global_scope(db, self.importing_file(db))
368    }
369}
370
371impl<'db> From<StarImportPlaceholderPredicate<'db>> for PredicateOrLiteral<'db> {
372    fn from(predicate: StarImportPlaceholderPredicate<'db>) -> Self {
373        PredicateOrLiteral::Predicate(Predicate {
374            node: PredicateNode::StarImportPlaceholder(predicate),
375            is_positive: true,
376        })
377    }
378}
ty_python_core/predicate.rs

ty_python_core/
predicate.rs
