]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | //! Candidate selection. See the [rustc dev guide] for more information on how this works. |
0531ce1d | 2 | //! |
ba9703b0 | 3 | //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection |
1a4d82fc | 4 | |
1a4d82fc JJ |
5 | use self::EvaluationResult::*; |
6 | ||
74b04a01 | 7 | use super::{SelectionError, SelectionResult}; |
5e7ed085 | 8 | use rustc_errors::ErrorGuaranteed; |
0bf4aa26 | 9 | |
3dfed10e | 10 | use crate::ty; |
9fa01778 | 11 | |
74b04a01 | 12 | use rustc_hir::def_id::DefId; |
3dfed10e | 13 | use rustc_query_system::cache::Cache; |
1a4d82fc | 14 | |
3dfed10e | 15 | pub type SelectionCache<'tcx> = Cache< |
5e7ed085 FG |
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>), | |
3dfed10e XL |
20 | SelectionResult<'tcx, SelectionCandidate<'tcx>>, |
21 | >; | |
1a4d82fc | 22 | |
5e7ed085 FG |
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>), | |
27 | EvaluationResult, | |
28 | >; | |
74b04a01 | 29 | |
1a4d82fc | 30 | /// The selection process begins by considering all impls, where |
9fa01778 | 31 | /// clauses, and so forth that might resolve an obligation. Sometimes |
1a4d82fc | 32 | /// we'll be able to say definitively that (e.g.) an impl does not |
c34b1796 | 33 | /// apply to the obligation: perhaps it is defined for `usize` but the |
f9f354fc | 34 | /// obligation is for `i32`. In that case, we drop the impl out of the |
9fa01778 | 35 | /// list. But the other cases are considered *candidates*. |
1a4d82fc | 36 | /// |
d9579d0f AL |
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. | |
1a4d82fc | 41 | /// |
d9579d0f AL |
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 | |
e74abb32 | 46 | /// "type annotations needed" error. |
d9579d0f AL |
47 | /// |
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 | |
53 | /// | |
f9f354fc XL |
54 | /// ```rust, ignore |
55 | /// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; } | |
56 | /// impl<T: fmt::Debug> AsDebug for T { | |
57 | /// type Out = T; | |
58 | /// fn debug(self) -> fmt::Debug { self } | |
59 | /// } | |
60 | /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); } | |
61 | /// ``` | |
d9579d0f | 62 | /// |
60c5eb7d XL |
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`. | |
d9579d0f AL |
66 | /// |
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 | |
71 | /// #21974. | |
72 | /// | |
73 | /// If a single where-clause matches and there are no inference | |
74 | /// variables left, then it definitely matches and we can just select | |
75 | /// it. | |
76 | /// | |
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: | |
80 | /// | |
f9f354fc XL |
81 | /// ```rust, ignore |
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 } } | |
d9579d0f | 85 | /// |
f9f354fc XL |
86 | /// pub fn foo<T>(t: T) where T: Foo<bool> { |
87 | /// println!("{:?}", <T as Foo<_>>::foo(&t)); | |
88 | /// } | |
89 | /// fn main() { foo(false); } | |
90 | /// ``` | |
d9579d0f | 91 | /// |
60c5eb7d XL |
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`, | |
d9579d0f | 94 | /// so the program prints "false". However, if the where-clause is omitted, |
60c5eb7d | 95 | /// the blanket impl is selected, we unify `$0=()`, and the program prints |
d9579d0f AL |
96 | /// "()". |
97 | /// | |
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 | |
e9174d1e | 102 | /// present), and we just pick the where-clause. This is, for example, |
d9579d0f AL |
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. | |
49aad941 | 106 | #[derive(PartialEq, Eq, Debug, Clone, TypeVisitable)] |
74b04a01 | 107 | pub enum SelectionCandidate<'tcx> { |
487cf647 FG |
108 | /// A builtin implementation for some specific traits, used in cases |
109 | /// where we cannot rely an ordinary library implementations. | |
110 | /// | |
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. | |
0bf4aa26 | 114 | BuiltinCandidate { |
60c5eb7d | 115 | /// `false` if there are no *further* obligations. |
0bf4aa26 XL |
116 | has_nested: bool, |
117 | }, | |
064997fb FG |
118 | |
119 | /// Implementation of transmutability trait. | |
120 | TransmutabilityCandidate, | |
121 | ||
a2a8927a | 122 | ParamCandidate(ty::PolyTraitPredicate<'tcx>), |
e9174d1e | 123 | ImplCandidate(DefId), |
2b03887a | 124 | AutoImplCandidate, |
1a4d82fc | 125 | |
29967ef6 XL |
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 | |
2b03887a FG |
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), | |
1a4d82fc | 131 | |
a7813a04 | 132 | /// Implementation of a `Fn`-family trait by one of the anonymous types |
94222f64 | 133 | /// generated for an `||` expression. |
9c376795 FG |
134 | ClosureCandidate { |
135 | is_const: bool, | |
136 | }, | |
ea8adc8c XL |
137 | |
138 | /// Implementation of a `Generator` trait by one of the anonymous types | |
139 | /// generated for a generator. | |
140 | GeneratorCandidate, | |
1a4d82fc | 141 | |
487cf647 FG |
142 | /// Implementation of a `Future` trait by one of the generator types |
143 | /// generated for an async construct. | |
144 | FutureCandidate, | |
145 | ||
1a4d82fc | 146 | /// Implementation of a `Fn`-family trait by one of the anonymous |
60c5eb7d | 147 | /// types generated for a fn pointer type (e.g., `fn(int) -> int`) |
c295e0f8 XL |
148 | FnPointerCandidate { |
149 | is_const: bool, | |
150 | }, | |
1a4d82fc | 151 | |
2b03887a | 152 | TraitAliasCandidate, |
a1dfa0c6 | 153 | |
29967ef6 XL |
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), | |
1a4d82fc | 158 | |
94222f64 XL |
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), | |
163 | ||
c34b1796 AL |
164 | BuiltinObjectCandidate, |
165 | ||
d9579d0f | 166 | BuiltinUnsizeCandidate, |
c295e0f8 | 167 | |
5e7ed085 FG |
168 | /// Implementation of `const Destruct`, optionally from a custom `impl const Drop`. |
169 | ConstDestructCandidate(Option<DefId>), | |
1a4d82fc JJ |
170 | } |
171 | ||
92a42be0 SL |
172 | /// The result of trait evaluation. The order is important |
173 | /// here as the evaluation of a list is the maximum of the | |
174 | /// evaluations. | |
3b2f2976 XL |
175 | /// |
176 | /// The evaluation results are ordered: | |
0731742a XL |
177 | /// - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions` |
178 | /// implies `EvaluatedToAmbig` implies `EvaluatedToUnknown` | |
3b2f2976 XL |
179 | /// - `EvaluatedToErr` implies `EvaluatedToRecur` |
180 | /// - the "union" of evaluation results is equal to their maximum - | |
181 | /// all the "potential success" candidates can potentially succeed, | |
9fa01778 | 182 | /// so they are noops when unioned with a definite error, and within |
3b2f2976 | 183 | /// the categories it's easy to see that the unions are correct. |
60c5eb7d | 184 | #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)] |
83c7162d | 185 | pub enum EvaluationResult { |
60c5eb7d | 186 | /// Evaluation successful. |
1a4d82fc | 187 | EvaluatedToOk, |
60c5eb7d | 188 | /// Evaluation successful, but there were unevaluated region obligations. |
0731742a | 189 | EvaluatedToOkModuloRegions, |
04454e1e FG |
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, | |
60c5eb7d | 194 | /// Evaluation is known to be ambiguous -- it *might* hold for some |
3b2f2976 XL |
195 | /// assignment of inference variables, but it might not. |
196 | /// | |
60c5eb7d XL |
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 | |
3b2f2976 | 199 | /// would get with an empty stack, and therefore is cacheable. |
1a4d82fc | 200 | EvaluatedToAmbig, |
3b2f2976 XL |
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. | |
204 | /// | |
205 | /// This can't be trivially cached for the same reason as `EvaluatedToRecur`. | |
206 | EvaluatedToUnknown, | |
207 | /// Evaluation failed because we encountered an obligation we are already | |
208 | /// trying to prove on this branch. | |
209 | /// | |
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 | |
60c5eb7d | 213 | /// that all the obligations on this branch do not hold -- it's possible |
3b2f2976 XL |
214 | /// that we entered this branch "speculatively", and that there |
215 | /// might be some other way to prove this obligation that does not | |
60c5eb7d | 216 | /// go through this cycle -- so we can't cache this as a failure. |
3b2f2976 XL |
217 | /// |
218 | /// For example, suppose we have this: | |
219 | /// | |
220 | /// ```rust,ignore (pseudo-Rust) | |
60c5eb7d XL |
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() {} } | |
3b2f2976 | 225 | /// |
60c5eb7d XL |
226 | /// pub fn foo<T: Trait + ?Sized>() { |
227 | /// <T as Trait>::xyz(); | |
228 | /// } | |
3b2f2976 XL |
229 | /// ``` |
230 | /// | |
231 | /// When checking `foo`, we have to prove `T: Trait`. This basically | |
232 | /// translates into this: | |
233 | /// | |
83c7162d | 234 | /// ```plain,ignore |
60c5eb7d | 235 | /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait |
83c7162d | 236 | /// ``` |
3b2f2976 XL |
237 | /// |
238 | /// When we try to prove it, we first go the first option, which | |
9fa01778 | 239 | /// recurses. This shows us that the impl is "useless" -- it won't |
3b2f2976 XL |
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). | |
9fa01778 XL |
244 | // |
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. | |
3b2f2976 | 250 | EvaluatedToRecur, |
9fa01778 | 251 | /// Evaluation failed. |
92a42be0 SL |
252 | EvaluatedToErr, |
253 | } | |
254 | ||
3b2f2976 | 255 | impl EvaluationResult { |
9fa01778 | 256 | /// Returns `true` if this evaluation result is known to apply, even |
0731742a XL |
257 | /// considering outlives constraints. |
258 | pub fn must_apply_considering_regions(self) -> bool { | |
259 | self == EvaluatedToOk | |
260 | } | |
261 | ||
9fa01778 | 262 | /// Returns `true` if this evaluation result is known to apply, ignoring |
0731742a XL |
263 | /// outlives constraints. |
264 | pub fn must_apply_modulo_regions(self) -> bool { | |
265 | self <= EvaluatedToOkModuloRegions | |
266 | } | |
267 | ||
83c7162d | 268 | pub fn may_apply(self) -> bool { |
3b2f2976 | 269 | match self { |
04454e1e FG |
270 | EvaluatedToOkModuloOpaqueTypes |
271 | | EvaluatedToOk | |
272 | | EvaluatedToOkModuloRegions | |
273 | | EvaluatedToAmbig | |
274 | | EvaluatedToUnknown => true, | |
3b2f2976 | 275 | |
0bf4aa26 | 276 | EvaluatedToErr | EvaluatedToRecur => false, |
3b2f2976 XL |
277 | } |
278 | } | |
279 | ||
74b04a01 | 280 | pub fn is_stack_dependent(self) -> bool { |
3b2f2976 | 281 | match self { |
0bf4aa26 | 282 | EvaluatedToUnknown | EvaluatedToRecur => true, |
3b2f2976 | 283 | |
04454e1e FG |
284 | EvaluatedToOkModuloOpaqueTypes |
285 | | EvaluatedToOk | |
286 | | EvaluatedToOkModuloRegions | |
287 | | EvaluatedToAmbig | |
288 | | EvaluatedToErr => false, | |
3b2f2976 XL |
289 | } |
290 | } | |
291 | } | |
292 | ||
c295e0f8 | 293 | /// Indicates that trait evaluation caused overflow and in which pass. |
60c5eb7d | 294 | #[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)] |
c295e0f8 | 295 | pub enum OverflowError { |
5e7ed085 | 296 | Error(ErrorGuaranteed), |
c295e0f8 XL |
297 | Canonical, |
298 | ErrorReporting, | |
299 | } | |
83c7162d | 300 | |
5e7ed085 FG |
301 | impl From<ErrorGuaranteed> for OverflowError { |
302 | fn from(e: ErrorGuaranteed) -> OverflowError { | |
303 | OverflowError::Error(e) | |
304 | } | |
305 | } | |
306 | ||
064997fb | 307 | TrivialTypeTraversalAndLiftImpls! { |
5e7ed085 FG |
308 | OverflowError, |
309 | } | |
310 | ||
83c7162d | 311 | impl<'tcx> From<OverflowError> for SelectionError<'tcx> { |
c295e0f8 XL |
312 | fn from(overflow_error: OverflowError) -> SelectionError<'tcx> { |
313 | match overflow_error { | |
5e7ed085 FG |
314 | OverflowError::Error(e) => SelectionError::Overflow(OverflowError::Error(e)), |
315 | OverflowError::Canonical => SelectionError::Overflow(OverflowError::Canonical), | |
c295e0f8 XL |
316 | OverflowError::ErrorReporting => SelectionError::ErrorReporting, |
317 | } | |
83c7162d XL |
318 | } |
319 | } |