rustc_type_ir/solve/
mod.rs

1pub mod inspect;
2
3use std::hash::Hash;
4
5use derive_where::derive_where;
6#[cfg(feature = "nightly")]
7use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
8use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
9
10use crate::lang_items::SolverTraitLangItem;
11use crate::search_graph::PathKind;
12use crate::{self as ty, Canonical, CanonicalVarValues, Interner, Upcast};
13
14pub type CanonicalInput<I, T = <I as Interner>::Predicate> =
15    ty::CanonicalQueryInput<I, QueryInput<I, T>>;
16pub type CanonicalResponse<I> = Canonical<I, Response<I>>;
17/// The result of evaluating a canonical query.
18///
19/// FIXME: We use a different type than the existing canonical queries. This is because
20/// we need to add a `Certainty` for `overflow` and may want to restructure this code without
21/// having to worry about changes to currently used code. Once we've made progress on this
22/// solver, merge the two responses again.
23pub type QueryResult<I> = Result<CanonicalResponse<I>, NoSolution>;
24
25#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
26#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
27pub struct NoSolution;
28
29/// A goal is a statement, i.e. `predicate`, we want to prove
30/// given some assumptions, i.e. `param_env`.
31///
32/// Most of the time the `param_env` contains the `where`-bounds of the function
33/// we're currently typechecking while the `predicate` is some trait bound.
34#[derive_where(Clone, Hash, PartialEq, Debug; I: Interner, P)]
35#[derive_where(Copy; I: Interner, P: Copy)]
36#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
37#[cfg_attr(
38    feature = "nightly",
39    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
40)]
41pub struct Goal<I: Interner, P> {
42    pub param_env: I::ParamEnv,
43    pub predicate: P,
44}
45
46impl<I: Interner, P: Eq> Eq for Goal<I, P> {}
47
48impl<I: Interner, P> Goal<I, P> {
49    pub fn new(cx: I, param_env: I::ParamEnv, predicate: impl Upcast<I, P>) -> Goal<I, P> {
50        Goal { param_env, predicate: predicate.upcast(cx) }
51    }
52
53    /// Updates the goal to one with a different `predicate` but the same `param_env`.
54    pub fn with<Q>(self, cx: I, predicate: impl Upcast<I, Q>) -> Goal<I, Q> {
55        Goal { param_env: self.param_env, predicate: predicate.upcast(cx) }
56    }
57}
58
59/// Why a specific goal has to be proven.
60///
61/// This is necessary as we treat nested goals different depending on
62/// their source. This is used to decide whether a cycle is coinductive.
63/// See the documentation of `EvalCtxt::step_kind_for_source` for more details
64/// about this.
65///
66/// It is also used by proof tree visitors, e.g. for diagnostics purposes.
67#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
68#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
69pub enum GoalSource {
70    Misc,
71    /// A nested goal required to prove that types are equal/subtypes.
72    /// This is always an unproductive step.
73    ///
74    /// This is also used for all `NormalizesTo` goals as we they are used
75    /// to relate types in `AliasRelate`.
76    TypeRelating,
77    /// We're proving a where-bound of an impl.
78    ImplWhereBound,
79    /// Const conditions that need to hold for `[const]` alias bounds to hold.
80    AliasBoundConstCondition,
81    /// Predicate required for an alias projection to be well-formed.
82    /// This is used in three places:
83    /// 1. projecting to an opaque whose hidden type is already registered in
84    ///    the opaque type storage,
85    /// 2. for rigid projections's trait goal,
86    /// 3. for GAT where clauses.
87    AliasWellFormed,
88    /// In case normalizing aliases in nested goals cycles, eagerly normalizing these
89    /// aliases in the context of the parent may incorrectly change the cycle kind.
90    /// Normalizing aliases in goals therefore tracks the original path kind for this
91    /// nested goal. See the comment of the `ReplaceAliasWithInfer` visitor for more
92    /// details.
93    NormalizeGoal(PathKind),
94}
95
96#[derive_where(Clone, Hash, PartialEq, Debug; I: Interner, Goal<I, P>)]
97#[derive_where(Copy; I: Interner, Goal<I, P>: Copy)]
98#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
99#[cfg_attr(
100    feature = "nightly",
101    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
102)]
103pub struct QueryInput<I: Interner, P> {
104    pub goal: Goal<I, P>,
105    pub predefined_opaques_in_body: I::PredefinedOpaques,
106}
107
108impl<I: Interner, P: Eq> Eq for QueryInput<I, P> {}
109
110/// Which trait candidates should be preferred over other candidates? By default, prefer where
111/// bounds over alias bounds. For marker traits, prefer alias bounds over where bounds.
112#[derive(Clone, Copy, Debug)]
113pub enum CandidatePreferenceMode {
114    /// Prefers where bounds over alias bounds
115    Default,
116    /// Prefers alias bounds over where bounds
117    Marker,
118}
119
120impl CandidatePreferenceMode {
121    /// Given `trait_def_id`, which candidate preference mode should be used?
122    pub fn compute<I: Interner>(cx: I, trait_id: I::TraitId) -> CandidatePreferenceMode {
123        let is_sizedness_or_auto_or_default_goal = cx.is_sizedness_trait(trait_id)
124            || cx.trait_is_auto(trait_id)
125            || cx.is_default_trait(trait_id);
126        if is_sizedness_or_auto_or_default_goal {
127            CandidatePreferenceMode::Marker
128        } else {
129            CandidatePreferenceMode::Default
130        }
131    }
132}
133
134/// Possible ways the given goal can be proven.
135#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
136pub enum CandidateSource<I: Interner> {
137    /// A user written impl.
138    ///
139    /// ## Examples
140    ///
141    /// ```rust
142    /// fn main() {
143    ///     let x: Vec<u32> = Vec::new();
144    ///     // This uses the impl from the standard library to prove `Vec<T>: Clone`.
145    ///     let y = x.clone();
146    /// }
147    /// ```
148    Impl(I::ImplId),
149    /// A builtin impl generated by the compiler. When adding a new special
150    /// trait, try to use actual impls whenever possible. Builtin impls should
151    /// only be used in cases where the impl cannot be manually be written.
152    ///
153    /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`.
154    /// For a list of all traits with builtin impls, check out the
155    /// `EvalCtxt::assemble_builtin_impl_candidates` method.
156    BuiltinImpl(BuiltinImplSource),
157    /// An assumption from the environment. Stores a [`ParamEnvSource`], since we
158    /// prefer non-global param-env candidates in candidate assembly.
159    ///
160    /// ## Examples
161    ///
162    /// ```rust
163    /// fn is_clone<T: Clone>(x: T) -> (T, T) {
164    ///     // This uses the assumption `T: Clone` from the `where`-bounds
165    ///     // to prove `T: Clone`.
166    ///     (x.clone(), x)
167    /// }
168    /// ```
169    ParamEnv(ParamEnvSource),
170    /// If the self type is an alias type, e.g. an opaque type or a projection,
171    /// we know the bounds on that alias to hold even without knowing its concrete
172    /// underlying type.
173    ///
174    /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
175    /// the self type.
176    ///
177    /// ## Examples
178    ///
179    /// ```rust
180    /// trait Trait {
181    ///     type Assoc: Clone;
182    /// }
183    ///
184    /// fn foo<T: Trait>(x: <T as Trait>::Assoc) {
185    ///     // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in
186    ///     // in the trait definition.
187    ///     let _y = x.clone();
188    /// }
189    /// ```
190    AliasBound(AliasBoundKind),
191    /// A candidate that is registered only during coherence to represent some
192    /// yet-unknown impl that could be produced downstream without violating orphan
193    /// rules.
194    // FIXME: Merge this with the forced ambiguity candidates, so those don't use `Misc`.
195    CoherenceUnknowable,
196}
197
198impl<I: Interner> Eq for CandidateSource<I> {}
199
200#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
201pub enum ParamEnvSource {
202    /// Preferred eagerly.
203    NonGlobal,
204    // Not considered unless there are non-global param-env candidates too.
205    Global,
206}
207
208#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
209#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
210pub enum AliasBoundKind {
211    /// Alias bound from the self type of a projection
212    SelfBounds,
213    // Alias bound having recursed on the self type of a projection
214    NonSelfBounds,
215}
216
217#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
218#[cfg_attr(
219    feature = "nightly",
220    derive(HashStable_NoContext, Encodable_NoContext, Decodable_NoContext)
221)]
222pub enum BuiltinImplSource {
223    /// A built-in impl that is considered trivial, without any nested requirements. They
224    /// are preferred over where-clauses, and we want to track them explicitly.
225    Trivial,
226    /// Some built-in impl we don't need to differentiate. This should be used
227    /// unless more specific information is necessary.
228    Misc,
229    /// A built-in impl for trait objects. The index is only used in winnowing.
230    Object(usize),
231    /// A built-in implementation of `Upcast` for trait objects to other trait objects.
232    ///
233    /// The index is only used for winnowing.
234    TraitUpcasting(usize),
235}
236
237#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
238#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
239#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
240pub struct Response<I: Interner> {
241    pub certainty: Certainty,
242    pub var_values: CanonicalVarValues<I>,
243    /// Additional constraints returned by this query.
244    pub external_constraints: I::ExternalConstraints,
245}
246
247impl<I: Interner> Eq for Response<I> {}
248
249/// Additional constraints returned on success.
250#[derive_where(Clone, Hash, PartialEq, Debug, Default; I: Interner)]
251#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
252#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
253pub struct ExternalConstraintsData<I: Interner> {
254    pub region_constraints: Vec<ty::OutlivesPredicate<I, I::GenericArg>>,
255    pub opaque_types: Vec<(ty::OpaqueTypeKey<I>, I::Ty)>,
256    pub normalization_nested_goals: NestedNormalizationGoals<I>,
257}
258
259impl<I: Interner> Eq for ExternalConstraintsData<I> {}
260
261impl<I: Interner> ExternalConstraintsData<I> {
262    pub fn is_empty(&self) -> bool {
263        self.region_constraints.is_empty()
264            && self.opaque_types.is_empty()
265            && self.normalization_nested_goals.is_empty()
266    }
267}
268
269#[derive_where(Clone, Hash, PartialEq, Debug, Default; I: Interner)]
270#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
271#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
272pub struct NestedNormalizationGoals<I: Interner>(pub Vec<(GoalSource, Goal<I, I::Predicate>)>);
273
274impl<I: Interner> Eq for NestedNormalizationGoals<I> {}
275
276impl<I: Interner> NestedNormalizationGoals<I> {
277    pub fn empty() -> Self {
278        NestedNormalizationGoals(vec![])
279    }
280
281    pub fn is_empty(&self) -> bool {
282        self.0.is_empty()
283    }
284}
285
286#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
287#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
288pub enum Certainty {
289    Yes,
290    Maybe { cause: MaybeCause, opaque_types_jank: OpaqueTypesJank },
291}
292
293/// Supporting not-yet-defined opaque types in HIR typeck is somewhat
294/// challenging. Ideally we'd normalize them to a new inference variable
295/// and just defer type inference which relies on the opaque until we've
296/// constrained the hidden type.
297///
298/// This doesn't work for method and function calls as we need to guide type
299/// inference for the function arguments. We treat not-yet-defined opaque types
300/// as if they were rigid instead in these places.
301///
302/// When we encounter a `?hidden_type_of_opaque: Trait<?var>` goal, we use the
303/// item bounds and blanket impls to guide inference by constraining other type
304/// variables, see `EvalCtxt::try_assemble_bounds_via_registered_opaques`. We
305/// always keep the certainty as `Maybe` so that we properly prove these goals
306/// once the hidden type has been constrained.
307///
308/// If we fail to prove the trait goal via item bounds or blanket impls, the
309/// goal would have errored if the opaque type were rigid. In this case, we
310/// set `OpaqueTypesJank::ErrorIfRigidSelfTy` in the [Certainty].
311///
312/// Places in HIR typeck where we want to treat not-yet-defined opaque types as if
313/// they were kind of rigid then use `fn root_goal_may_hold_opaque_types_jank` which
314/// returns `false` if the goal doesn't hold or if `OpaqueTypesJank::ErrorIfRigidSelfTy`
315/// is set (i.e. proving it required relies on some `?hidden_ty: NotInItemBounds` goal).
316///
317/// This is subtly different from actually treating not-yet-defined opaque types as
318/// rigid, e.g. it allows constraining opaque types if they are not the self-type of
319/// a goal. It is good enough for now and only matters for very rare type inference
320/// edge cases. We can improve this later on if necessary.
321#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
322#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
323pub enum OpaqueTypesJank {
324    AllGood,
325    ErrorIfRigidSelfTy,
326}
327impl OpaqueTypesJank {
328    fn and(self, other: OpaqueTypesJank) -> OpaqueTypesJank {
329        match (self, other) {
330            (OpaqueTypesJank::AllGood, OpaqueTypesJank::AllGood) => OpaqueTypesJank::AllGood,
331            (OpaqueTypesJank::ErrorIfRigidSelfTy, _) | (_, OpaqueTypesJank::ErrorIfRigidSelfTy) => {
332                OpaqueTypesJank::ErrorIfRigidSelfTy
333            }
334        }
335    }
336
337    pub fn or(self, other: OpaqueTypesJank) -> OpaqueTypesJank {
338        match (self, other) {
339            (OpaqueTypesJank::ErrorIfRigidSelfTy, OpaqueTypesJank::ErrorIfRigidSelfTy) => {
340                OpaqueTypesJank::ErrorIfRigidSelfTy
341            }
342            (OpaqueTypesJank::AllGood, _) | (_, OpaqueTypesJank::AllGood) => {
343                OpaqueTypesJank::AllGood
344            }
345        }
346    }
347}
348
349impl Certainty {
350    pub const AMBIGUOUS: Certainty = Certainty::Maybe {
351        cause: MaybeCause::Ambiguity,
352        opaque_types_jank: OpaqueTypesJank::AllGood,
353    };
354
355    /// Use this function to merge the certainty of multiple nested subgoals.
356    ///
357    /// Given an impl like `impl<T: Foo + Bar> Baz for T {}`, we have 2 nested
358    /// subgoals whenever we use the impl as a candidate: `T: Foo` and `T: Bar`.
359    /// If evaluating `T: Foo` results in ambiguity and `T: Bar` results in
360    /// success, we merge these two responses. This results in ambiguity.
361    ///
362    /// If we unify ambiguity with overflow, we return overflow. This doesn't matter
363    /// inside of the solver as we do not distinguish ambiguity from overflow. It does
364    /// however matter for diagnostics. If `T: Foo` resulted in overflow and `T: Bar`
365    /// in ambiguity without changing the inference state, we still want to tell the
366    /// user that `T: Baz` results in overflow.
367    pub fn and(self, other: Certainty) -> Certainty {
368        match (self, other) {
369            (Certainty::Yes, Certainty::Yes) => Certainty::Yes,
370            (Certainty::Yes, Certainty::Maybe { .. }) => other,
371            (Certainty::Maybe { .. }, Certainty::Yes) => self,
372            (
373                Certainty::Maybe { cause: a_cause, opaque_types_jank: a_jank },
374                Certainty::Maybe { cause: b_cause, opaque_types_jank: b_jank },
375            ) => Certainty::Maybe {
376                cause: a_cause.and(b_cause),
377                opaque_types_jank: a_jank.and(b_jank),
378            },
379        }
380    }
381
382    pub const fn overflow(suggest_increasing_limit: bool) -> Certainty {
383        Certainty::Maybe {
384            cause: MaybeCause::Overflow { suggest_increasing_limit, keep_constraints: false },
385            opaque_types_jank: OpaqueTypesJank::AllGood,
386        }
387    }
388}
389
390/// Why we failed to evaluate a goal.
391#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
392#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
393pub enum MaybeCause {
394    /// We failed due to ambiguity. This ambiguity can either
395    /// be a true ambiguity, i.e. there are multiple different answers,
396    /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals.
397    Ambiguity,
398    /// We gave up due to an overflow, most often by hitting the recursion limit.
399    Overflow { suggest_increasing_limit: bool, keep_constraints: bool },
400}
401
402impl MaybeCause {
403    fn and(self, other: MaybeCause) -> MaybeCause {
404        match (self, other) {
405            (MaybeCause::Ambiguity, MaybeCause::Ambiguity) => MaybeCause::Ambiguity,
406            (MaybeCause::Ambiguity, MaybeCause::Overflow { .. }) => other,
407            (MaybeCause::Overflow { .. }, MaybeCause::Ambiguity) => self,
408            (
409                MaybeCause::Overflow {
410                    suggest_increasing_limit: limit_a,
411                    keep_constraints: keep_a,
412                },
413                MaybeCause::Overflow {
414                    suggest_increasing_limit: limit_b,
415                    keep_constraints: keep_b,
416                },
417            ) => MaybeCause::Overflow {
418                suggest_increasing_limit: limit_a && limit_b,
419                keep_constraints: keep_a && keep_b,
420            },
421        }
422    }
423
424    pub fn or(self, other: MaybeCause) -> MaybeCause {
425        match (self, other) {
426            (MaybeCause::Ambiguity, MaybeCause::Ambiguity) => MaybeCause::Ambiguity,
427
428            // When combining ambiguity + overflow, we can keep constraints.
429            (
430                MaybeCause::Ambiguity,
431                MaybeCause::Overflow { suggest_increasing_limit, keep_constraints: _ },
432            ) => MaybeCause::Overflow { suggest_increasing_limit, keep_constraints: true },
433            (
434                MaybeCause::Overflow { suggest_increasing_limit, keep_constraints: _ },
435                MaybeCause::Ambiguity,
436            ) => MaybeCause::Overflow { suggest_increasing_limit, keep_constraints: true },
437
438            (
439                MaybeCause::Overflow {
440                    suggest_increasing_limit: limit_a,
441                    keep_constraints: keep_a,
442                },
443                MaybeCause::Overflow {
444                    suggest_increasing_limit: limit_b,
445                    keep_constraints: keep_b,
446                },
447            ) => MaybeCause::Overflow {
448                suggest_increasing_limit: limit_a || limit_b,
449                keep_constraints: keep_a || keep_b,
450            },
451        }
452    }
453}
454
455/// Indicates that a `impl Drop for Adt` is `const` or not.
456#[derive(Debug)]
457pub enum AdtDestructorKind {
458    NotConst,
459    Const,
460}
461
462/// Which sizedness trait - `Sized`, `MetaSized`? `PointeeSized` is omitted as it is removed during
463/// lowering.
464#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
465#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
466pub enum SizedTraitKind {
467    /// `Sized` trait
468    Sized,
469    /// `MetaSized` trait
470    MetaSized,
471}
472
473impl SizedTraitKind {
474    /// Returns `DefId` of corresponding language item.
475    pub fn require_lang_item<I: Interner>(self, cx: I) -> I::TraitId {
476        cx.require_trait_lang_item(match self {
477            SizedTraitKind::Sized => SolverTraitLangItem::Sized,
478            SizedTraitKind::MetaSized => SolverTraitLangItem::MetaSized,
479        })
480    }
481}