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