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}