1 //! Candidate selection. See the [rustc dev guide] for more information on how this works.
3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
5 use self::EvaluationResult
::*;
7 use super::{SelectionError, SelectionResult}
;
8 use rustc_errors
::ErrorGuaranteed
;
12 use rustc_hir
::def_id
::DefId
;
13 use rustc_query_system
::cache
::Cache
;
15 pub type SelectionCache
<'tcx
> = Cache
<
16 // This cache does not use `ParamEnvAnd` in its keys because `ParamEnv::and` can replace
17 // caller bounds with an empty list if the `TraitPredicate` looks global, which may happen
18 // after erasing lifetimes from the predicate.
19 (ty
::ParamEnv
<'tcx
>, ty
::TraitPredicate
<'tcx
>),
20 SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>,
23 pub type EvaluationCache
<'tcx
> = Cache
<
24 // See above: this cache does not use `ParamEnvAnd` in its keys due to sometimes incorrectly
25 // caching with the wrong `ParamEnv`.
26 (ty
::ParamEnv
<'tcx
>, ty
::PolyTraitPredicate
<'tcx
>),
30 /// The selection process begins by considering all impls, where
31 /// clauses, and so forth that might resolve an obligation. Sometimes
32 /// we'll be able to say definitively that (e.g.) an impl does not
33 /// apply to the obligation: perhaps it is defined for `usize` but the
34 /// obligation is for `i32`. In that case, we drop the impl out of the
35 /// list. But the other cases are considered *candidates*.
37 /// For selection to succeed, there must be exactly one matching
38 /// candidate. If the obligation is fully known, this is guaranteed
39 /// by coherence. However, if the obligation contains type parameters
40 /// or variables, there may be multiple such impls.
42 /// It is not a real problem if multiple matching impls exist because
43 /// of type variables - it just means the obligation isn't sufficiently
44 /// elaborated. In that case we report an ambiguity, and the caller can
45 /// try again after more type information has been gathered or report a
46 /// "type annotations needed" error.
48 /// However, with type parameters, this can be a real problem - type
49 /// parameters don't unify with regular types, but they *can* unify
50 /// with variables from blanket impls, and (unless we know its bounds
51 /// will always be satisfied) picking the blanket impl will be wrong
52 /// for at least *some* substitutions. To make this concrete, if we have
55 /// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
56 /// impl<T: fmt::Debug> AsDebug for T {
58 /// fn debug(self) -> fmt::Debug { self }
60 /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
63 /// we can't just use the impl to resolve the `<T as AsDebug>` obligation
64 /// -- a type from another crate (that doesn't implement `fmt::Debug`) could
65 /// implement `AsDebug`.
67 /// Because where-clauses match the type exactly, multiple clauses can
68 /// only match if there are unresolved variables, and we can mostly just
69 /// report this ambiguity in that case. This is still a problem - we can't
70 /// *do anything* with ambiguities that involve only regions. This is issue
73 /// If a single where-clause matches and there are no inference
74 /// variables left, then it definitely matches and we can just select
77 /// In fact, we even select the where-clause when the obligation contains
78 /// inference variables. The can lead to inference making "leaps of logic",
79 /// for example in this situation:
82 /// pub trait Foo<T> { fn foo(&self) -> T; }
83 /// impl<T> Foo<()> for T { fn foo(&self) { } }
84 /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
86 /// pub fn foo<T>(t: T) where T: Foo<bool> {
87 /// println!("{:?}", <T as Foo<_>>::foo(&t));
89 /// fn main() { foo(false); }
92 /// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
93 /// impl and the where-clause. We select the where-clause and unify `$0=bool`,
94 /// so the program prints "false". However, if the where-clause is omitted,
95 /// the blanket impl is selected, we unify `$0=()`, and the program prints
98 /// Exactly the same issues apply to projection and object candidates, except
99 /// that we can have both a projection candidate and a where-clause candidate
100 /// for the same obligation. In that case either would do (except that
101 /// different "leaps of logic" would occur if inference variables are
102 /// present), and we just pick the where-clause. This is, for example,
103 /// required for associated types to work in default impls, as the bounds
104 /// are visible both as projection bounds and as where-clauses from the
105 /// parameter environment.
106 #[derive(PartialEq, Eq, Debug, Clone, TypeFoldable, TypeVisitable)]
107 pub enum SelectionCandidate
<'tcx
> {
108 /// A builtin implementation for some specific traits, used in cases
109 /// where we cannot rely an ordinary library implementations.
111 /// The most notable examples are `sized`, `Copy` and `Clone`. This is also
112 /// used for the `DiscriminantKind` and `Pointee` trait, both of which have
113 /// an associated type.
115 /// `false` if there are no *further* obligations.
119 /// Implementation of transmutability trait.
120 TransmutabilityCandidate
,
122 ParamCandidate(ty
::PolyTraitPredicate
<'tcx
>),
123 ImplCandidate(DefId
),
126 /// This is a trait matching with a projected type as `Self`, and we found
127 /// an applicable bound in the trait definition. The `usize` is an index
128 /// into the list returned by `tcx.item_bounds`. The constness is the
129 /// constness of the bound in the trait.
130 ProjectionCandidate(usize, ty
::BoundConstness
),
132 /// Implementation of a `Fn`-family trait by one of the anonymous types
133 /// generated for an `||` expression.
138 /// Implementation of a `Generator` trait by one of the anonymous types
139 /// generated for a generator.
142 /// Implementation of a `Future` trait by one of the generator types
143 /// generated for an async construct.
146 /// Implementation of a `Fn`-family trait by one of the anonymous
147 /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
154 /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
155 /// position in the iterator returned by
156 /// `rustc_infer::traits::util::supertraits`.
157 ObjectCandidate(usize),
159 /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
160 /// The index is the position in the iterator returned by
161 /// `rustc_infer::traits::util::supertraits`.
162 TraitUpcastingUnsizeCandidate(usize),
164 BuiltinObjectCandidate
,
166 BuiltinUnsizeCandidate
,
168 /// Implementation of `const Destruct`, optionally from a custom `impl const Drop`.
169 ConstDestructCandidate(Option
<DefId
>),
172 /// The result of trait evaluation. The order is important
173 /// here as the evaluation of a list is the maximum of the
176 /// The evaluation results are ordered:
177 /// - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
178 /// implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
179 /// - `EvaluatedToErr` implies `EvaluatedToRecur`
180 /// - the "union" of evaluation results is equal to their maximum -
181 /// all the "potential success" candidates can potentially succeed,
182 /// so they are noops when unioned with a definite error, and within
183 /// the categories it's easy to see that the unions are correct.
184 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
185 pub enum EvaluationResult
{
186 /// Evaluation successful.
188 /// Evaluation successful, but there were unevaluated region obligations.
189 EvaluatedToOkModuloRegions
,
190 /// Evaluation successful, but need to rerun because opaque types got
191 /// hidden types assigned without it being known whether the opaque types
192 /// are within their defining scope
193 EvaluatedToOkModuloOpaqueTypes
,
194 /// Evaluation is known to be ambiguous -- it *might* hold for some
195 /// assignment of inference variables, but it might not.
197 /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
198 /// know whether this obligation holds or not -- it is the result we
199 /// would get with an empty stack, and therefore is cacheable.
201 /// Evaluation failed because of recursion involving inference
202 /// variables. We are somewhat imprecise there, so we don't actually
203 /// know the real result.
205 /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
207 /// Evaluation failed because we encountered an obligation we are already
208 /// trying to prove on this branch.
210 /// We know this branch can't be a part of a minimal proof-tree for
211 /// the "root" of our cycle, because then we could cut out the recursion
212 /// and maintain a valid proof tree. However, this does not mean
213 /// that all the obligations on this branch do not hold -- it's possible
214 /// that we entered this branch "speculatively", and that there
215 /// might be some other way to prove this obligation that does not
216 /// go through this cycle -- so we can't cache this as a failure.
218 /// For example, suppose we have this:
220 /// ```rust,ignore (pseudo-Rust)
221 /// pub trait Trait { fn xyz(); }
222 /// // This impl is "useless", but we can still have
223 /// // an `impl Trait for SomeUnsizedType` somewhere.
224 /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
226 /// pub fn foo<T: Trait + ?Sized>() {
227 /// <T as Trait>::xyz();
231 /// When checking `foo`, we have to prove `T: Trait`. This basically
232 /// translates into this:
235 /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
238 /// When we try to prove it, we first go the first option, which
239 /// recurses. This shows us that the impl is "useless" -- it won't
240 /// tell us that `T: Trait` unless it already implemented `Trait`
241 /// by some other means. However, that does not prevent `T: Trait`
242 /// does not hold, because of the bound (which can indeed be satisfied
243 /// by `SomeUnsizedType` from another crate).
245 // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
246 // ought to convert it to an `EvaluatedToErr`, because we know
247 // there definitely isn't a proof tree for that obligation. Not
248 // doing so is still sound -- there isn't any proof tree, so the
249 // branch still can't be a part of a minimal one -- but does not re-enable caching.
251 /// Evaluation failed.
255 impl EvaluationResult
{
256 /// Returns `true` if this evaluation result is known to apply, even
257 /// considering outlives constraints.
258 pub fn must_apply_considering_regions(self) -> bool
{
259 self == EvaluatedToOk
262 /// Returns `true` if this evaluation result is known to apply, ignoring
263 /// outlives constraints.
264 pub fn must_apply_modulo_regions(self) -> bool
{
265 self <= EvaluatedToOkModuloRegions
268 pub fn may_apply(self) -> bool
{
270 EvaluatedToOkModuloOpaqueTypes
272 | EvaluatedToOkModuloRegions
274 | EvaluatedToUnknown
=> true,
276 EvaluatedToErr
| EvaluatedToRecur
=> false,
280 pub fn is_stack_dependent(self) -> bool
{
282 EvaluatedToUnknown
| EvaluatedToRecur
=> true,
284 EvaluatedToOkModuloOpaqueTypes
286 | EvaluatedToOkModuloRegions
288 | EvaluatedToErr
=> false,
293 /// Indicates that trait evaluation caused overflow and in which pass.
294 #[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
295 pub enum OverflowError
{
296 Error(ErrorGuaranteed
),
301 impl From
<ErrorGuaranteed
> for OverflowError
{
302 fn from(e
: ErrorGuaranteed
) -> OverflowError
{
303 OverflowError
::Error(e
)
307 TrivialTypeTraversalAndLiftImpls
! {
311 impl<'tcx
> From
<OverflowError
> for SelectionError
<'tcx
> {
312 fn from(overflow_error
: OverflowError
) -> SelectionError
<'tcx
> {
313 match overflow_error
{
314 OverflowError
::Error(e
) => SelectionError
::Overflow(OverflowError
::Error(e
)),
315 OverflowError
::Canonical
=> SelectionError
::Overflow(OverflowError
::Canonical
),
316 OverflowError
::ErrorReporting
=> SelectionError
::ErrorReporting
,