rustc_middle/traits/
select.rs

1//! Candidate selection. See the [rustc dev guide] for more information on how this works.
2//!
3//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
4
5use rustc_errors::ErrorGuaranteed;
6use rustc_hir::def_id::DefId;
7use rustc_macros::{HashStable, TypeVisitable};
8use rustc_query_system::cache::Cache;
9
10use self::EvaluationResult::*;
11use super::{SelectionError, SelectionResult};
12use crate::ty;
13
14pub type SelectionCache<'tcx, ENV> =
15    Cache<(ENV, ty::TraitPredicate<'tcx>), SelectionResult<'tcx, SelectionCandidate<'tcx>>>;
16
17pub type EvaluationCache<'tcx, ENV> = Cache<(ENV, ty::PolyTraitPredicate<'tcx>), EvaluationResult>;
18
19/// The selection process begins by considering all impls, where
20/// clauses, and so forth that might resolve an obligation. Sometimes
21/// we'll be able to say definitively that (e.g.) an impl does not
22/// apply to the obligation: perhaps it is defined for `usize` but the
23/// obligation is for `i32`. In that case, we drop the impl out of the
24/// list. But the other cases are considered *candidates*.
25///
26/// For selection to succeed, there must be exactly one matching
27/// candidate. If the obligation is fully known, this is guaranteed
28/// by coherence. However, if the obligation contains type parameters
29/// or variables, there may be multiple such impls.
30///
31/// It is not a real problem if multiple matching impls exist because
32/// of type variables - it just means the obligation isn't sufficiently
33/// elaborated. In that case we report an ambiguity, and the caller can
34/// try again after more type information has been gathered or report a
35/// "type annotations needed" error.
36///
37/// However, with type parameters, this can be a real problem - type
38/// parameters don't unify with regular types, but they *can* unify
39/// with variables from blanket impls, and (unless we know its bounds
40/// will always be satisfied) picking the blanket impl will be wrong
41/// for at least *some* generic parameters. To make this concrete, if
42/// we have
43///
44/// ```rust, ignore
45/// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
46/// impl<T: fmt::Debug> AsDebug for T {
47///     type Out = T;
48///     fn debug(self) -> fmt::Debug { self }
49/// }
50/// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
51/// ```
52///
53/// we can't just use the impl to resolve the `<T as AsDebug>` obligation
54/// -- a type from another crate (that doesn't implement `fmt::Debug`) could
55/// implement `AsDebug`.
56///
57/// Because where-clauses match the type exactly, multiple clauses can
58/// only match if there are unresolved variables, and we can mostly just
59/// report this ambiguity in that case. This is still a problem - we can't
60/// *do anything* with ambiguities that involve only regions. This is issue
61/// #21974.
62///
63/// If a single where-clause matches and there are no inference
64/// variables left, then it definitely matches and we can just select
65/// it.
66///
67/// In fact, we even select the where-clause when the obligation contains
68/// inference variables. The can lead to inference making "leaps of logic",
69/// for example in this situation:
70///
71/// ```rust, ignore
72/// pub trait Foo<T> { fn foo(&self) -> T; }
73/// impl<T> Foo<()> for T { fn foo(&self) { } }
74/// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
75///
76/// pub fn foo<T>(t: T) where T: Foo<bool> {
77///     println!("{:?}", <T as Foo<_>>::foo(&t));
78/// }
79/// fn main() { foo(false); }
80/// ```
81///
82/// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
83/// impl and the where-clause. We select the where-clause and unify `$0=bool`,
84/// so the program prints "false". However, if the where-clause is omitted,
85/// the blanket impl is selected, we unify `$0=()`, and the program prints
86/// "()".
87///
88/// Exactly the same issues apply to projection and object candidates, except
89/// that we can have both a projection candidate and a where-clause candidate
90/// for the same obligation. In that case either would do (except that
91/// different "leaps of logic" would occur if inference variables are
92/// present), and we just pick the where-clause. This is, for example,
93/// required for associated types to work in default impls, as the bounds
94/// are visible both as projection bounds and as where-clauses from the
95/// parameter environment.
96#[derive(PartialEq, Eq, Debug, Clone, TypeVisitable)]
97pub enum SelectionCandidate<'tcx> {
98    /// A built-in implementation for the `Sized` trait. This is preferred
99    /// over all other candidates.
100    SizedCandidate {
101        has_nested: bool,
102    },
103
104    /// A builtin implementation for some specific traits, used in cases
105    /// where we cannot rely an ordinary library implementations.
106    ///
107    /// The most notable examples are `Copy` and `Clone`. This is also
108    /// used for the `DiscriminantKind` and `Pointee` trait, both of which have
109    /// an associated type.
110    BuiltinCandidate {
111        /// `false` if there are no *further* obligations.
112        has_nested: bool,
113    },
114
115    /// Implementation of transmutability trait.
116    TransmutabilityCandidate,
117
118    ParamCandidate(ty::PolyTraitPredicate<'tcx>),
119    ImplCandidate(DefId),
120    AutoImplCandidate,
121
122    /// This is a trait matching with a projected type as `Self`, and we found
123    /// an applicable bound in the trait definition. The `usize` is an index
124    /// into the list returned by `tcx.item_bounds`.
125    ProjectionCandidate(usize),
126
127    /// Implementation of a `Fn`-family trait by one of the anonymous types
128    /// generated for an `||` expression.
129    ClosureCandidate {
130        is_const: bool,
131    },
132
133    /// Implementation of an `AsyncFn`-family trait by one of the anonymous types
134    /// generated for an `async ||` expression.
135    AsyncClosureCandidate,
136
137    /// Implementation of the `AsyncFnKindHelper` helper trait, which
138    /// is used internally to delay computation for async closures until after
139    /// upvar analysis is performed in HIR typeck.
140    AsyncFnKindHelperCandidate,
141
142    /// Implementation of a `Coroutine` trait by one of the anonymous types
143    /// generated for a coroutine.
144    CoroutineCandidate,
145
146    /// Implementation of a `Future` trait by one of the coroutine types
147    /// generated for an async construct.
148    FutureCandidate,
149
150    /// Implementation of an `Iterator` trait by one of the coroutine types
151    /// generated for a `gen` construct.
152    IteratorCandidate,
153
154    /// Implementation of an `AsyncIterator` trait by one of the coroutine types
155    /// generated for a `async gen` construct.
156    AsyncIteratorCandidate,
157
158    /// Implementation of a `Fn`-family trait by one of the anonymous
159    /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
160    FnPointerCandidate,
161
162    TraitAliasCandidate,
163
164    /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
165    /// position in the iterator returned by
166    /// `rustc_infer::traits::util::supertraits`.
167    ObjectCandidate(usize),
168
169    /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
170    /// The index is the position in the iterator returned by
171    /// `rustc_infer::traits::util::supertraits`.
172    TraitUpcastingUnsizeCandidate(usize),
173
174    BuiltinObjectCandidate,
175
176    BuiltinUnsizeCandidate,
177
178    BikeshedGuaranteedNoDropCandidate,
179}
180
181/// The result of trait evaluation. The order is important
182/// here as the evaluation of a list is the maximum of the
183/// evaluations.
184///
185/// The evaluation results are ordered:
186///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
187///       implies `EvaluatedToAmbig` implies `EvaluatedToAmbigStackDependent`
188///     - the "union" of evaluation results is equal to their maximum -
189///     all the "potential success" candidates can potentially succeed,
190///     so they are noops when unioned with a definite error, and within
191///     the categories it's easy to see that the unions are correct.
192#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
193pub enum EvaluationResult {
194    /// Evaluation successful.
195    EvaluatedToOk,
196    /// Evaluation successful, but there were unevaluated region obligations.
197    EvaluatedToOkModuloRegions,
198    /// Evaluation successful, but need to rerun because opaque types got
199    /// hidden types assigned without it being known whether the opaque types
200    /// are within their defining scope
201    EvaluatedToOkModuloOpaqueTypes,
202    /// Evaluation is known to be ambiguous -- it *might* hold for some
203    /// assignment of inference variables, but it might not.
204    ///
205    /// While this has the same meaning as `EvaluatedToAmbigStackDependent` -- we can't
206    /// know whether this obligation holds or not -- it is the result we
207    /// would get with an empty stack, and therefore is cacheable.
208    EvaluatedToAmbig,
209    /// Evaluation failed because of recursion involving inference
210    /// variables. We are somewhat imprecise there, so we don't actually
211    /// know the real result.
212    ///
213    /// This can't be trivially cached because the result depends on the
214    /// stack results.
215    EvaluatedToAmbigStackDependent,
216    /// Evaluation failed.
217    EvaluatedToErr,
218}
219
220impl EvaluationResult {
221    /// Returns `true` if this evaluation result is known to apply, even
222    /// considering outlives constraints.
223    pub fn must_apply_considering_regions(self) -> bool {
224        self == EvaluatedToOk
225    }
226
227    /// Returns `true` if this evaluation result is known to apply, ignoring
228    /// outlives constraints.
229    pub fn must_apply_modulo_regions(self) -> bool {
230        self <= EvaluatedToOkModuloRegions
231    }
232
233    pub fn may_apply(self) -> bool {
234        match self {
235            EvaluatedToOkModuloOpaqueTypes
236            | EvaluatedToOk
237            | EvaluatedToOkModuloRegions
238            | EvaluatedToAmbig
239            | EvaluatedToAmbigStackDependent => true,
240
241            EvaluatedToErr => false,
242        }
243    }
244
245    pub fn is_stack_dependent(self) -> bool {
246        match self {
247            EvaluatedToAmbigStackDependent => true,
248
249            EvaluatedToOkModuloOpaqueTypes
250            | EvaluatedToOk
251            | EvaluatedToOkModuloRegions
252            | EvaluatedToAmbig
253            | EvaluatedToErr => false,
254        }
255    }
256}
257
258/// Indicates that trait evaluation caused overflow and in which pass.
259#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
260pub enum OverflowError {
261    Error(ErrorGuaranteed),
262    Canonical,
263}
264
265impl From<ErrorGuaranteed> for OverflowError {
266    fn from(e: ErrorGuaranteed) -> OverflowError {
267        OverflowError::Error(e)
268    }
269}
270
271impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
272    fn from(overflow_error: OverflowError) -> SelectionError<'tcx> {
273        match overflow_error {
274            OverflowError::Error(e) => SelectionError::Overflow(OverflowError::Error(e)),
275            OverflowError::Canonical => SelectionError::Overflow(OverflowError::Canonical),
276        }
277    }
278}