]>
Commit | Line | Data |
---|---|---|
0731742a | 1 | //! Candidate selection. See the [rustc guide] for more information on how this works. |
0531ce1d | 2 | //! |
a1dfa0c6 | 3 | //! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/resolution.html#selection |
1a4d82fc | 4 | |
1a4d82fc | 5 | use self::EvaluationResult::*; |
0bf4aa26 | 6 | use self::SelectionCandidate::*; |
1a4d82fc | 7 | |
ff7c6d11 | 8 | use super::coherence::{self, Conflict}; |
c34b1796 | 9 | use super::project; |
3b2f2976 | 10 | use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey}; |
0bf4aa26 XL |
11 | use super::util; |
12 | use super::DerivedObligationCause; | |
c34b1796 AL |
13 | use super::Selection; |
14 | use super::SelectionResult; | |
0bf4aa26 XL |
15 | use super::TraitNotObjectSafe; |
16 | use super::{BuiltinDerivedObligation, ImplDerivedObligation, ObligationCauseCode}; | |
17 | use super::{IntercrateMode, TraitQueryMode}; | |
18 | use super::{ObjectCastObligation, Obligation}; | |
19 | use super::{ObligationCause, PredicateObligation, TraitObligation}; | |
20 | use super::{OutputTypeParameterMismatch, Overflow, SelectionError, Unimplemented}; | |
21 | use super::{ | |
22 | VtableAutoImpl, VtableBuiltin, VtableClosure, VtableFnPointer, VtableGenerator, VtableImpl, | |
a1dfa0c6 | 23 | VtableObject, VtableParam, VtableTraitAlias, |
0bf4aa26 XL |
24 | }; |
25 | use super::{ | |
26 | VtableAutoImplData, VtableBuiltinData, VtableClosureData, VtableFnPointerData, | |
a1dfa0c6 | 27 | VtableGeneratorData, VtableImplData, VtableObjectData, VtableTraitAliasData, |
0bf4aa26 XL |
28 | }; |
29 | ||
9fa01778 XL |
30 | use crate::dep_graph::{DepKind, DepNodeIndex}; |
31 | use crate::hir::def_id::DefId; | |
32 | use crate::infer::{CombinedSnapshot, InferCtxt, InferOk, PlaceholderMap, TypeFreshener}; | |
33 | use crate::middle::lang_items; | |
34 | use crate::mir::interpret::GlobalId; | |
35 | use crate::ty::fast_reject; | |
36 | use crate::ty::relate::TypeRelation; | |
37 | use crate::ty::subst::{Subst, Substs}; | |
38 | use crate::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable}; | |
39 | ||
40 | use crate::hir; | |
0bf4aa26 | 41 | use rustc_data_structures::bit_set::GrowableBitSet; |
94b46f34 | 42 | use rustc_data_structures::sync::Lock; |
0bf4aa26 | 43 | use rustc_target::spec::abi::Abi; |
3b2f2976 | 44 | use std::cmp; |
9fa01778 | 45 | use std::fmt::{self, Display}; |
0bf4aa26 | 46 | use std::iter; |
1a4d82fc | 47 | use std::rc::Rc; |
9fa01778 | 48 | use crate::util::nodemap::{FxHashMap, FxHashSet}; |
1a4d82fc | 49 | |
0bf4aa26 | 50 | pub struct SelectionContext<'cx, 'gcx: 'cx + 'tcx, 'tcx: 'cx> { |
a7813a04 | 51 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, |
1a4d82fc | 52 | |
0bf4aa26 XL |
53 | /// Freshener used specifically for entries on the obligation |
54 | /// stack. This ensures that all entries on the stack at one time | |
55 | /// will have the same set of placeholder entries, which is | |
56 | /// important for checking for trait bounds that recursively | |
57 | /// require themselves. | |
a7813a04 | 58 | freshener: TypeFreshener<'cx, 'gcx, 'tcx>, |
1a4d82fc | 59 | |
0731742a | 60 | /// If `true`, indicates that the evaluation should be conservative |
1a4d82fc JJ |
61 | /// and consider the possibility of types outside this crate. |
62 | /// This comes up primarily when resolving ambiguity. Imagine | |
0731742a | 63 | /// there is some trait reference `$0: Bar` where `$0` is an |
1a4d82fc JJ |
64 | /// inference variable. If `intercrate` is true, then we can never |
65 | /// say for sure that this reference is not implemented, even if | |
66 | /// there are *no impls at all for `Bar`*, because `$0` could be | |
67 | /// bound to some type that in a downstream crate that implements | |
68 | /// `Bar`. This is the suitable mode for coherence. Elsewhere, | |
69 | /// though, we set this to false, because we are only interested | |
70 | /// in types that the user could actually have written --- in | |
0731742a | 71 | /// other words, we consider `$0: Bar` to be unimplemented if |
1a4d82fc JJ |
72 | /// there is no type that the user could *actually name* that |
73 | /// would satisfy it. This avoids crippling inference, basically. | |
ff7c6d11 | 74 | intercrate: Option<IntercrateMode>, |
a7813a04 | 75 | |
ff7c6d11 | 76 | intercrate_ambiguity_causes: Option<Vec<IntercrateAmbiguityCause>>, |
0531ce1d XL |
77 | |
78 | /// Controls whether or not to filter out negative impls when selecting. | |
79 | /// This is used in librustdoc to distinguish between the lack of an impl | |
80 | /// and a negative impl | |
83c7162d XL |
81 | allow_negative_impls: bool, |
82 | ||
83 | /// The mode that trait queries run in, which informs our error handling | |
84 | /// policy. In essence, canonicalized queries need their errors propagated | |
85 | /// rather than immediately reported because we do not have accurate spans. | |
86 | query_mode: TraitQueryMode, | |
ea8adc8c XL |
87 | } |
88 | ||
ff7c6d11 | 89 | #[derive(Clone, Debug)] |
ea8adc8c XL |
90 | pub enum IntercrateAmbiguityCause { |
91 | DownstreamCrate { | |
92 | trait_desc: String, | |
93 | self_desc: Option<String>, | |
94 | }, | |
95 | UpstreamCrateUpdate { | |
96 | trait_desc: String, | |
97 | self_desc: Option<String>, | |
98 | }, | |
99 | } | |
100 | ||
101 | impl IntercrateAmbiguityCause { | |
102 | /// Emits notes when the overlap is caused by complex intercrate ambiguities. | |
103 | /// See #23980 for details. | |
0bf4aa26 XL |
104 | pub fn add_intercrate_ambiguity_hint<'a, 'tcx>( |
105 | &self, | |
9fa01778 | 106 | err: &mut errors::DiagnosticBuilder<'_>, |
0bf4aa26 | 107 | ) { |
ff7c6d11 XL |
108 | err.note(&self.intercrate_ambiguity_hint()); |
109 | } | |
110 | ||
111 | pub fn intercrate_ambiguity_hint(&self) -> String { | |
ea8adc8c | 112 | match self { |
0bf4aa26 XL |
113 | &IntercrateAmbiguityCause::DownstreamCrate { |
114 | ref trait_desc, | |
115 | ref self_desc, | |
116 | } => { | |
ea8adc8c XL |
117 | let self_desc = if let &Some(ref ty) = self_desc { |
118 | format!(" for type `{}`", ty) | |
0bf4aa26 XL |
119 | } else { |
120 | String::new() | |
121 | }; | |
122 | format!( | |
123 | "downstream crates may implement trait `{}`{}", | |
124 | trait_desc, self_desc | |
125 | ) | |
126 | } | |
127 | &IntercrateAmbiguityCause::UpstreamCrateUpdate { | |
128 | ref trait_desc, | |
129 | ref self_desc, | |
130 | } => { | |
ea8adc8c XL |
131 | let self_desc = if let &Some(ref ty) = self_desc { |
132 | format!(" for type `{}`", ty) | |
0bf4aa26 XL |
133 | } else { |
134 | String::new() | |
135 | }; | |
136 | format!( | |
137 | "upstream crates may add new impl of trait `{}`{} \ | |
138 | in future versions", | |
139 | trait_desc, self_desc | |
140 | ) | |
ea8adc8c XL |
141 | } |
142 | } | |
143 | } | |
1a4d82fc JJ |
144 | } |
145 | ||
146 | // A stack that walks back up the stack frame. | |
147 | struct TraitObligationStack<'prev, 'tcx: 'prev> { | |
148 | obligation: &'prev TraitObligation<'tcx>, | |
149 | ||
0bf4aa26 | 150 | /// Trait ref from `obligation` but "freshened" with the |
1a4d82fc JJ |
151 | /// selection-context's freshener. Used to check for recursion. |
152 | fresh_trait_ref: ty::PolyTraitRef<'tcx>, | |
153 | ||
c34b1796 | 154 | previous: TraitObligationStackList<'prev, 'tcx>, |
1a4d82fc JJ |
155 | } |
156 | ||
0bf4aa26 | 157 | #[derive(Clone, Default)] |
1a4d82fc | 158 | pub struct SelectionCache<'tcx> { |
0bf4aa26 XL |
159 | hashmap: Lock< |
160 | FxHashMap<ty::TraitRef<'tcx>, WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>>, | |
161 | >, | |
1a4d82fc JJ |
162 | } |
163 | ||
1a4d82fc | 164 | /// The selection process begins by considering all impls, where |
9fa01778 | 165 | /// clauses, and so forth that might resolve an obligation. Sometimes |
1a4d82fc | 166 | /// we'll be able to say definitively that (e.g.) an impl does not |
c34b1796 | 167 | /// apply to the obligation: perhaps it is defined for `usize` but the |
1a4d82fc | 168 | /// obligation is for `int`. In that case, we drop the impl out of the |
9fa01778 | 169 | /// list. But the other cases are considered *candidates*. |
1a4d82fc | 170 | /// |
d9579d0f AL |
171 | /// For selection to succeed, there must be exactly one matching |
172 | /// candidate. If the obligation is fully known, this is guaranteed | |
173 | /// by coherence. However, if the obligation contains type parameters | |
174 | /// or variables, there may be multiple such impls. | |
1a4d82fc | 175 | /// |
d9579d0f AL |
176 | /// It is not a real problem if multiple matching impls exist because |
177 | /// of type variables - it just means the obligation isn't sufficiently | |
178 | /// elaborated. In that case we report an ambiguity, and the caller can | |
179 | /// try again after more type information has been gathered or report a | |
180 | /// "type annotations required" error. | |
181 | /// | |
182 | /// However, with type parameters, this can be a real problem - type | |
183 | /// parameters don't unify with regular types, but they *can* unify | |
184 | /// with variables from blanket impls, and (unless we know its bounds | |
185 | /// will always be satisfied) picking the blanket impl will be wrong | |
186 | /// for at least *some* substitutions. To make this concrete, if we have | |
187 | /// | |
188 | /// trait AsDebug { type Out : fmt::Debug; fn debug(self) -> Self::Out; } | |
189 | /// impl<T: fmt::Debug> AsDebug for T { | |
190 | /// type Out = T; | |
191 | /// fn debug(self) -> fmt::Debug { self } | |
192 | /// } | |
193 | /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); } | |
194 | /// | |
195 | /// we can't just use the impl to resolve the <T as AsDebug> obligation | |
196 | /// - a type from another crate (that doesn't implement fmt::Debug) could | |
197 | /// implement AsDebug. | |
198 | /// | |
199 | /// Because where-clauses match the type exactly, multiple clauses can | |
200 | /// only match if there are unresolved variables, and we can mostly just | |
201 | /// report this ambiguity in that case. This is still a problem - we can't | |
202 | /// *do anything* with ambiguities that involve only regions. This is issue | |
203 | /// #21974. | |
204 | /// | |
205 | /// If a single where-clause matches and there are no inference | |
206 | /// variables left, then it definitely matches and we can just select | |
207 | /// it. | |
208 | /// | |
209 | /// In fact, we even select the where-clause when the obligation contains | |
210 | /// inference variables. The can lead to inference making "leaps of logic", | |
211 | /// for example in this situation: | |
212 | /// | |
213 | /// pub trait Foo<T> { fn foo(&self) -> T; } | |
214 | /// impl<T> Foo<()> for T { fn foo(&self) { } } | |
215 | /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } } | |
216 | /// | |
217 | /// pub fn foo<T>(t: T) where T: Foo<bool> { | |
218 | /// println!("{:?}", <T as Foo<_>>::foo(&t)); | |
219 | /// } | |
220 | /// fn main() { foo(false); } | |
221 | /// | |
222 | /// Here the obligation <T as Foo<$0>> can be matched by both the blanket | |
223 | /// impl and the where-clause. We select the where-clause and unify $0=bool, | |
224 | /// so the program prints "false". However, if the where-clause is omitted, | |
225 | /// the blanket impl is selected, we unify $0=(), and the program prints | |
226 | /// "()". | |
227 | /// | |
228 | /// Exactly the same issues apply to projection and object candidates, except | |
229 | /// that we can have both a projection candidate and a where-clause candidate | |
230 | /// for the same obligation. In that case either would do (except that | |
231 | /// different "leaps of logic" would occur if inference variables are | |
e9174d1e | 232 | /// present), and we just pick the where-clause. This is, for example, |
d9579d0f AL |
233 | /// required for associated types to work in default impls, as the bounds |
234 | /// are visible both as projection bounds and as where-clauses from the | |
235 | /// parameter environment. | |
0bf4aa26 | 236 | #[derive(PartialEq, Eq, Debug, Clone)] |
1a4d82fc | 237 | enum SelectionCandidate<'tcx> { |
b7449926 | 238 | /// If has_nested is false, there are no *further* obligations |
0bf4aa26 XL |
239 | BuiltinCandidate { |
240 | has_nested: bool, | |
241 | }, | |
1a4d82fc | 242 | ParamCandidate(ty::PolyTraitRef<'tcx>), |
e9174d1e | 243 | ImplCandidate(DefId), |
abe05a73 | 244 | AutoImplCandidate(DefId), |
1a4d82fc JJ |
245 | |
246 | /// This is a trait matching with a projected type as `Self`, and | |
247 | /// we found an applicable bound in the trait definition. | |
248 | ProjectionCandidate, | |
249 | ||
a7813a04 | 250 | /// Implementation of a `Fn`-family trait by one of the anonymous types |
ea8adc8c XL |
251 | /// generated for a `||` expression. |
252 | ClosureCandidate, | |
253 | ||
254 | /// Implementation of a `Generator` trait by one of the anonymous types | |
255 | /// generated for a generator. | |
256 | GeneratorCandidate, | |
1a4d82fc JJ |
257 | |
258 | /// Implementation of a `Fn`-family trait by one of the anonymous | |
259 | /// types generated for a fn pointer type (e.g., `fn(int)->int`) | |
260 | FnPointerCandidate, | |
261 | ||
a1dfa0c6 XL |
262 | TraitAliasCandidate(DefId), |
263 | ||
1a4d82fc JJ |
264 | ObjectCandidate, |
265 | ||
c34b1796 AL |
266 | BuiltinObjectCandidate, |
267 | ||
d9579d0f | 268 | BuiltinUnsizeCandidate, |
1a4d82fc JJ |
269 | } |
270 | ||
a7813a04 XL |
271 | impl<'a, 'tcx> ty::Lift<'tcx> for SelectionCandidate<'a> { |
272 | type Lifted = SelectionCandidate<'tcx>; | |
273 | fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> { | |
274 | Some(match *self { | |
0bf4aa26 | 275 | BuiltinCandidate { has_nested } => BuiltinCandidate { has_nested }, |
a7813a04 | 276 | ImplCandidate(def_id) => ImplCandidate(def_id), |
abe05a73 | 277 | AutoImplCandidate(def_id) => AutoImplCandidate(def_id), |
a7813a04 | 278 | ProjectionCandidate => ProjectionCandidate, |
a1dfa0c6 XL |
279 | ClosureCandidate => ClosureCandidate, |
280 | GeneratorCandidate => GeneratorCandidate, | |
a7813a04 | 281 | FnPointerCandidate => FnPointerCandidate, |
a1dfa0c6 | 282 | TraitAliasCandidate(def_id) => TraitAliasCandidate(def_id), |
a7813a04 XL |
283 | ObjectCandidate => ObjectCandidate, |
284 | BuiltinObjectCandidate => BuiltinObjectCandidate, | |
285 | BuiltinUnsizeCandidate => BuiltinUnsizeCandidate, | |
286 | ||
287 | ParamCandidate(ref trait_ref) => { | |
288 | return tcx.lift(trait_ref).map(ParamCandidate); | |
289 | } | |
a7813a04 XL |
290 | }) |
291 | } | |
292 | } | |
293 | ||
1a4d82fc JJ |
294 | struct SelectionCandidateSet<'tcx> { |
295 | // a list of candidates that definitely apply to the current | |
296 | // obligation (meaning: types unify). | |
297 | vec: Vec<SelectionCandidate<'tcx>>, | |
298 | ||
299 | // if this is true, then there were candidates that might or might | |
300 | // not have applied, but we couldn't tell. This occurs when some | |
301 | // of the input types are type variables, in which case there are | |
302 | // various "builtin" rules that might or might not trigger. | |
303 | ambiguous: bool, | |
304 | } | |
305 | ||
0bf4aa26 | 306 | #[derive(PartialEq, Eq, Debug, Clone)] |
54a0048b SL |
307 | struct EvaluatedCandidate<'tcx> { |
308 | candidate: SelectionCandidate<'tcx>, | |
309 | evaluation: EvaluationResult, | |
310 | } | |
311 | ||
a7813a04 XL |
312 | /// When does the builtin impl for `T: Trait` apply? |
313 | enum BuiltinImplConditions<'tcx> { | |
314 | /// The impl is conditional on T1,T2,.. : Trait | |
315 | Where(ty::Binder<Vec<Ty<'tcx>>>), | |
316 | /// There is no built-in impl. There may be some other | |
317 | /// candidate (a where-clause or user-defined impl). | |
318 | None, | |
a7813a04 | 319 | /// It is unknown whether there is an impl. |
0bf4aa26 | 320 | Ambiguous, |
1a4d82fc JJ |
321 | } |
322 | ||
92a42be0 SL |
323 | #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)] |
324 | /// The result of trait evaluation. The order is important | |
325 | /// here as the evaluation of a list is the maximum of the | |
326 | /// evaluations. | |
3b2f2976 XL |
327 | /// |
328 | /// The evaluation results are ordered: | |
0731742a XL |
329 | /// - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions` |
330 | /// implies `EvaluatedToAmbig` implies `EvaluatedToUnknown` | |
3b2f2976 XL |
331 | /// - `EvaluatedToErr` implies `EvaluatedToRecur` |
332 | /// - the "union" of evaluation results is equal to their maximum - | |
333 | /// all the "potential success" candidates can potentially succeed, | |
9fa01778 | 334 | /// so they are noops when unioned with a definite error, and within |
3b2f2976 | 335 | /// the categories it's easy to see that the unions are correct. |
83c7162d | 336 | pub enum EvaluationResult { |
92a42be0 | 337 | /// Evaluation successful |
1a4d82fc | 338 | EvaluatedToOk, |
0731742a XL |
339 | /// Evaluation successful, but there were unevaluated region obligations |
340 | EvaluatedToOkModuloRegions, | |
3b2f2976 XL |
341 | /// Evaluation is known to be ambiguous - it *might* hold for some |
342 | /// assignment of inference variables, but it might not. | |
343 | /// | |
344 | /// While this has the same meaning as `EvaluatedToUnknown` - we can't | |
345 | /// know whether this obligation holds or not - it is the result we | |
346 | /// would get with an empty stack, and therefore is cacheable. | |
1a4d82fc | 347 | EvaluatedToAmbig, |
3b2f2976 XL |
348 | /// Evaluation failed because of recursion involving inference |
349 | /// variables. We are somewhat imprecise there, so we don't actually | |
350 | /// know the real result. | |
351 | /// | |
352 | /// This can't be trivially cached for the same reason as `EvaluatedToRecur`. | |
353 | EvaluatedToUnknown, | |
354 | /// Evaluation failed because we encountered an obligation we are already | |
355 | /// trying to prove on this branch. | |
356 | /// | |
357 | /// We know this branch can't be a part of a minimal proof-tree for | |
358 | /// the "root" of our cycle, because then we could cut out the recursion | |
359 | /// and maintain a valid proof tree. However, this does not mean | |
360 | /// that all the obligations on this branch do not hold - it's possible | |
361 | /// that we entered this branch "speculatively", and that there | |
362 | /// might be some other way to prove this obligation that does not | |
363 | /// go through this cycle - so we can't cache this as a failure. | |
364 | /// | |
365 | /// For example, suppose we have this: | |
366 | /// | |
367 | /// ```rust,ignore (pseudo-Rust) | |
368 | /// pub trait Trait { fn xyz(); } | |
369 | /// // This impl is "useless", but we can still have | |
370 | /// // an `impl Trait for SomeUnsizedType` somewhere. | |
371 | /// impl<T: Trait + Sized> Trait for T { fn xyz() {} } | |
372 | /// | |
373 | /// pub fn foo<T: Trait + ?Sized>() { | |
374 | /// <T as Trait>::xyz(); | |
375 | /// } | |
376 | /// ``` | |
377 | /// | |
378 | /// When checking `foo`, we have to prove `T: Trait`. This basically | |
379 | /// translates into this: | |
380 | /// | |
83c7162d | 381 | /// ```plain,ignore |
3b2f2976 | 382 | /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait |
83c7162d | 383 | /// ``` |
3b2f2976 XL |
384 | /// |
385 | /// When we try to prove it, we first go the first option, which | |
9fa01778 | 386 | /// recurses. This shows us that the impl is "useless" -- it won't |
3b2f2976 XL |
387 | /// tell us that `T: Trait` unless it already implemented `Trait` |
388 | /// by some other means. However, that does not prevent `T: Trait` | |
389 | /// does not hold, because of the bound (which can indeed be satisfied | |
390 | /// by `SomeUnsizedType` from another crate). | |
9fa01778 XL |
391 | // |
392 | // FIXME: when an `EvaluatedToRecur` goes past its parent root, we | |
393 | // ought to convert it to an `EvaluatedToErr`, because we know | |
394 | // there definitely isn't a proof tree for that obligation. Not | |
395 | // doing so is still sound -- there isn't any proof tree, so the | |
396 | // branch still can't be a part of a minimal one -- but does not re-enable caching. | |
3b2f2976 | 397 | EvaluatedToRecur, |
9fa01778 | 398 | /// Evaluation failed. |
92a42be0 SL |
399 | EvaluatedToErr, |
400 | } | |
401 | ||
3b2f2976 | 402 | impl EvaluationResult { |
9fa01778 | 403 | /// Returns `true` if this evaluation result is known to apply, even |
0731742a XL |
404 | /// considering outlives constraints. |
405 | pub fn must_apply_considering_regions(self) -> bool { | |
406 | self == EvaluatedToOk | |
407 | } | |
408 | ||
9fa01778 | 409 | /// Returns `true` if this evaluation result is known to apply, ignoring |
0731742a XL |
410 | /// outlives constraints. |
411 | pub fn must_apply_modulo_regions(self) -> bool { | |
412 | self <= EvaluatedToOkModuloRegions | |
413 | } | |
414 | ||
83c7162d | 415 | pub fn may_apply(self) -> bool { |
3b2f2976 | 416 | match self { |
0731742a XL |
417 | EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => { |
418 | true | |
419 | } | |
3b2f2976 | 420 | |
0bf4aa26 | 421 | EvaluatedToErr | EvaluatedToRecur => false, |
3b2f2976 XL |
422 | } |
423 | } | |
424 | ||
425 | fn is_stack_dependent(self) -> bool { | |
426 | match self { | |
0bf4aa26 | 427 | EvaluatedToUnknown | EvaluatedToRecur => true, |
3b2f2976 | 428 | |
0731742a | 429 | EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false, |
3b2f2976 XL |
430 | } |
431 | } | |
432 | } | |
433 | ||
83c7162d XL |
434 | impl_stable_hash_for!(enum self::EvaluationResult { |
435 | EvaluatedToOk, | |
0731742a | 436 | EvaluatedToOkModuloRegions, |
83c7162d XL |
437 | EvaluatedToAmbig, |
438 | EvaluatedToUnknown, | |
439 | EvaluatedToRecur, | |
440 | EvaluatedToErr | |
441 | }); | |
442 | ||
443 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
444 | /// Indicates that trait evaluation caused overflow. | |
445 | pub struct OverflowError; | |
446 | ||
0bf4aa26 | 447 | impl_stable_hash_for!(struct OverflowError {}); |
83c7162d XL |
448 | |
449 | impl<'tcx> From<OverflowError> for SelectionError<'tcx> { | |
450 | fn from(OverflowError: OverflowError) -> SelectionError<'tcx> { | |
451 | SelectionError::Overflow | |
452 | } | |
453 | } | |
454 | ||
0bf4aa26 | 455 | #[derive(Clone, Default)] |
92a42be0 | 456 | pub struct EvaluationCache<'tcx> { |
0bf4aa26 | 457 | hashmap: Lock<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>, |
1a4d82fc JJ |
458 | } |
459 | ||
a7813a04 XL |
460 | impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> { |
461 | pub fn new(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>) -> SelectionContext<'cx, 'gcx, 'tcx> { | |
1a4d82fc | 462 | SelectionContext { |
041b39d2 | 463 | infcx, |
1a4d82fc | 464 | freshener: infcx.freshener(), |
ff7c6d11 | 465 | intercrate: None, |
ff7c6d11 | 466 | intercrate_ambiguity_causes: None, |
0531ce1d | 467 | allow_negative_impls: false, |
83c7162d | 468 | query_mode: TraitQueryMode::Standard, |
1a4d82fc JJ |
469 | } |
470 | } | |
471 | ||
0bf4aa26 XL |
472 | pub fn intercrate( |
473 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, | |
474 | mode: IntercrateMode, | |
475 | ) -> SelectionContext<'cx, 'gcx, 'tcx> { | |
ff7c6d11 | 476 | debug!("intercrate({:?})", mode); |
1a4d82fc | 477 | SelectionContext { |
041b39d2 | 478 | infcx, |
1a4d82fc | 479 | freshener: infcx.freshener(), |
ff7c6d11 | 480 | intercrate: Some(mode), |
ff7c6d11 | 481 | intercrate_ambiguity_causes: None, |
0531ce1d | 482 | allow_negative_impls: false, |
83c7162d | 483 | query_mode: TraitQueryMode::Standard, |
0531ce1d XL |
484 | } |
485 | } | |
486 | ||
0bf4aa26 XL |
487 | pub fn with_negative( |
488 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, | |
489 | allow_negative_impls: bool, | |
490 | ) -> SelectionContext<'cx, 'gcx, 'tcx> { | |
0531ce1d XL |
491 | debug!("with_negative({:?})", allow_negative_impls); |
492 | SelectionContext { | |
493 | infcx, | |
494 | freshener: infcx.freshener(), | |
495 | intercrate: None, | |
496 | intercrate_ambiguity_causes: None, | |
497 | allow_negative_impls, | |
83c7162d XL |
498 | query_mode: TraitQueryMode::Standard, |
499 | } | |
500 | } | |
501 | ||
0bf4aa26 XL |
502 | pub fn with_query_mode( |
503 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, | |
504 | query_mode: TraitQueryMode, | |
505 | ) -> SelectionContext<'cx, 'gcx, 'tcx> { | |
83c7162d XL |
506 | debug!("with_query_mode({:?})", query_mode); |
507 | SelectionContext { | |
508 | infcx, | |
509 | freshener: infcx.freshener(), | |
510 | intercrate: None, | |
511 | intercrate_ambiguity_causes: None, | |
512 | allow_negative_impls: false, | |
513 | query_mode, | |
1a4d82fc JJ |
514 | } |
515 | } | |
516 | ||
ff7c6d11 XL |
517 | /// Enables tracking of intercrate ambiguity causes. These are |
518 | /// used in coherence to give improved diagnostics. We don't do | |
519 | /// this until we detect a coherence error because it can lead to | |
520 | /// false overflow results (#47139) and because it costs | |
521 | /// computation time. | |
522 | pub fn enable_tracking_intercrate_ambiguity_causes(&mut self) { | |
523 | assert!(self.intercrate.is_some()); | |
524 | assert!(self.intercrate_ambiguity_causes.is_none()); | |
525 | self.intercrate_ambiguity_causes = Some(vec![]); | |
526 | debug!("selcx: enable_tracking_intercrate_ambiguity_causes"); | |
527 | } | |
528 | ||
529 | /// Gets the intercrate ambiguity causes collected since tracking | |
530 | /// was enabled and disables tracking at the same time. If | |
531 | /// tracking is not enabled, just returns an empty vector. | |
532 | pub fn take_intercrate_ambiguity_causes(&mut self) -> Vec<IntercrateAmbiguityCause> { | |
533 | assert!(self.intercrate.is_some()); | |
534 | self.intercrate_ambiguity_causes.take().unwrap_or(vec![]) | |
535 | } | |
536 | ||
a7813a04 | 537 | pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'gcx, 'tcx> { |
1a4d82fc JJ |
538 | self.infcx |
539 | } | |
540 | ||
a7813a04 | 541 | pub fn tcx(&self) -> TyCtxt<'cx, 'gcx, 'tcx> { |
1a4d82fc JJ |
542 | self.infcx.tcx |
543 | } | |
544 | ||
a7813a04 | 545 | pub fn closure_typer(&self) -> &'cx InferCtxt<'cx, 'gcx, 'tcx> { |
c1a9b12d | 546 | self.infcx |
85aaf69f SL |
547 | } |
548 | ||
1a4d82fc JJ |
549 | /////////////////////////////////////////////////////////////////////////// |
550 | // Selection | |
551 | // | |
552 | // The selection phase tries to identify *how* an obligation will | |
553 | // be resolved. For example, it will identify which impl or | |
554 | // parameter bound is to be used. The process can be inconclusive | |
555 | // if the self type in the obligation is not fully inferred. Selection | |
556 | // can result in an error in one of two ways: | |
557 | // | |
558 | // 1. If no applicable impl or parameter bound can be found. | |
559 | // 2. If the output type parameters in the obligation do not match | |
560 | // those specified by the impl/bound. For example, if the obligation | |
561 | // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies | |
562 | // `impl<T> Iterable<T> for Vec<T>`, than an error would result. | |
563 | ||
85aaf69f SL |
564 | /// Attempts to satisfy the obligation. If successful, this will affect the surrounding |
565 | /// type environment by performing unification. | |
0bf4aa26 XL |
566 | pub fn select( |
567 | &mut self, | |
568 | obligation: &TraitObligation<'tcx>, | |
569 | ) -> SelectionResult<'tcx, Selection<'tcx>> { | |
62682a34 | 570 | debug!("select({:?})", obligation); |
a1dfa0c6 | 571 | debug_assert!(!obligation.predicate.has_escaping_bound_vars()); |
1a4d82fc | 572 | |
c34b1796 | 573 | let stack = self.push_stack(TraitObligationStackList::empty(), obligation); |
83c7162d XL |
574 | |
575 | let candidate = match self.candidate_from_obligation(&stack) { | |
576 | Err(SelectionError::Overflow) => { | |
577 | // In standard mode, overflow must have been caught and reported | |
578 | // earlier. | |
579 | assert!(self.query_mode == TraitQueryMode::Canonical); | |
580 | return Err(SelectionError::Overflow); | |
0bf4aa26 XL |
581 | } |
582 | Err(e) => { | |
583 | return Err(e); | |
584 | } | |
585 | Ok(None) => { | |
586 | return Ok(None); | |
587 | } | |
588 | Ok(Some(candidate)) => candidate, | |
8bb4bdeb XL |
589 | }; |
590 | ||
83c7162d XL |
591 | match self.confirm_candidate(obligation, candidate) { |
592 | Err(SelectionError::Overflow) => { | |
593 | assert!(self.query_mode == TraitQueryMode::Canonical); | |
0bf4aa26 XL |
594 | Err(SelectionError::Overflow) |
595 | } | |
83c7162d | 596 | Err(e) => Err(e), |
0bf4aa26 | 597 | Ok(candidate) => Ok(Some(candidate)), |
83c7162d | 598 | } |
85aaf69f SL |
599 | } |
600 | ||
1a4d82fc JJ |
601 | /////////////////////////////////////////////////////////////////////////// |
602 | // EVALUATION | |
603 | // | |
604 | // Tests whether an obligation can be selected or whether an impl | |
605 | // can be applied to particular types. It skips the "confirmation" | |
606 | // step and hence completely ignores output type parameters. | |
607 | // | |
608 | // The result is "true" if the obligation *may* hold and "false" if | |
609 | // we can be sure it does not. | |
610 | ||
611 | /// Evaluates whether the obligation `obligation` can be satisfied (by any means). | |
0bf4aa26 XL |
612 | pub fn predicate_may_hold_fatal(&mut self, obligation: &PredicateObligation<'tcx>) -> bool { |
613 | debug!("predicate_may_hold_fatal({:?})", obligation); | |
1a4d82fc | 614 | |
83c7162d XL |
615 | // This fatal query is a stopgap that should only be used in standard mode, |
616 | // where we do not expect overflow to be propagated. | |
617 | assert!(self.query_mode == TraitQueryMode::Standard); | |
618 | ||
619 | self.evaluate_obligation_recursively(obligation) | |
620 | .expect("Overflow should be caught earlier in standard query mode") | |
621 | .may_apply() | |
1a4d82fc JJ |
622 | } |
623 | ||
83c7162d XL |
624 | /// Evaluates whether the obligation `obligation` can be satisfied and returns |
625 | /// an `EvaluationResult`. | |
0bf4aa26 XL |
626 | pub fn evaluate_obligation_recursively( |
627 | &mut self, | |
628 | obligation: &PredicateObligation<'tcx>, | |
629 | ) -> Result<EvaluationResult, OverflowError> { | |
0731742a | 630 | self.evaluation_probe(|this| { |
9fa01778 XL |
631 | this.evaluate_predicate_recursively(TraitObligationStackList::empty(), |
632 | obligation.clone()) | |
92a42be0 | 633 | }) |
1a4d82fc JJ |
634 | } |
635 | ||
0731742a XL |
636 | fn evaluation_probe( |
637 | &mut self, | |
638 | op: impl FnOnce(&mut Self) -> Result<EvaluationResult, OverflowError>, | |
639 | ) -> Result<EvaluationResult, OverflowError> { | |
640 | self.infcx.probe(|snapshot| -> Result<EvaluationResult, OverflowError> { | |
641 | let result = op(self)?; | |
642 | match self.infcx.region_constraints_added_in_snapshot(snapshot) { | |
643 | None => Ok(result), | |
644 | Some(_) => Ok(result.max(EvaluatedToOkModuloRegions)), | |
645 | } | |
646 | }) | |
647 | } | |
648 | ||
92a42be0 SL |
649 | /// Evaluates the predicates in `predicates` recursively. Note that |
650 | /// this applies projections in the predicates, and therefore | |
651 | /// is run within an inference probe. | |
0bf4aa26 XL |
652 | fn evaluate_predicates_recursively<'a, 'o, I>( |
653 | &mut self, | |
654 | stack: TraitObligationStackList<'o, 'tcx>, | |
655 | predicates: I, | |
656 | ) -> Result<EvaluationResult, OverflowError> | |
657 | where | |
9fa01778 | 658 | I: IntoIterator<Item = PredicateObligation<'tcx>>, |
0bf4aa26 | 659 | 'tcx: 'a, |
1a4d82fc JJ |
660 | { |
661 | let mut result = EvaluatedToOk; | |
662 | for obligation in predicates { | |
9fa01778 | 663 | let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?; |
0bf4aa26 XL |
664 | debug!( |
665 | "evaluate_predicate_recursively({:?}) = {:?}", | |
666 | obligation, eval | |
667 | ); | |
3b2f2976 XL |
668 | if let EvaluatedToErr = eval { |
669 | // fast-path - EvaluatedToErr is the top of the lattice, | |
670 | // so we don't need to look on the other predicates. | |
83c7162d | 671 | return Ok(EvaluatedToErr); |
3b2f2976 XL |
672 | } else { |
673 | result = cmp::max(result, eval); | |
1a4d82fc JJ |
674 | } |
675 | } | |
83c7162d | 676 | Ok(result) |
1a4d82fc JJ |
677 | } |
678 | ||
0bf4aa26 XL |
679 | fn evaluate_predicate_recursively<'o>( |
680 | &mut self, | |
681 | previous_stack: TraitObligationStackList<'o, 'tcx>, | |
9fa01778 | 682 | obligation: PredicateObligation<'tcx>, |
0bf4aa26 | 683 | ) -> Result<EvaluationResult, OverflowError> { |
9fa01778 XL |
684 | debug!("evaluate_predicate_recursively(previous_stack={:?}, obligation={:?})", |
685 | previous_stack.head(), obligation); | |
686 | ||
687 | // Previous_stack stores a TraitObligatiom, while 'obligation' is | |
688 | // a PredicateObligation. These are distinct types, so we can't | |
689 | // use any Option combinator method that would force them to be | |
690 | // the same | |
691 | match previous_stack.head() { | |
692 | Some(h) => self.check_recursion_limit(&obligation, h.obligation)?, | |
693 | None => self.check_recursion_limit(&obligation, &obligation)? | |
694 | } | |
62682a34 | 695 | |
1a4d82fc JJ |
696 | match obligation.predicate { |
697 | ty::Predicate::Trait(ref t) => { | |
a1dfa0c6 | 698 | debug_assert!(!t.has_escaping_bound_vars()); |
1a4d82fc | 699 | let obligation = obligation.with(t.clone()); |
3b2f2976 | 700 | self.evaluate_trait_predicate_recursively(previous_stack, obligation) |
1a4d82fc JJ |
701 | } |
702 | ||
cc61c64b XL |
703 | ty::Predicate::Subtype(ref p) => { |
704 | // does this code ever run? | |
0bf4aa26 XL |
705 | match self.infcx |
706 | .subtype_predicate(&obligation.cause, obligation.param_env, p) | |
707 | { | |
9fa01778 XL |
708 | Some(Ok(InferOk { mut obligations, .. })) => { |
709 | self.add_depth(obligations.iter_mut(), obligation.recursion_depth); | |
710 | self.evaluate_predicates_recursively(previous_stack,obligations.into_iter()) | |
0bf4aa26 | 711 | } |
83c7162d XL |
712 | Some(Err(_)) => Ok(EvaluatedToErr), |
713 | None => Ok(EvaluatedToAmbig), | |
cc61c64b XL |
714 | } |
715 | } | |
716 | ||
0bf4aa26 XL |
717 | ty::Predicate::WellFormed(ty) => match ty::wf::obligations( |
718 | self.infcx, | |
719 | obligation.param_env, | |
720 | obligation.cause.body_id, | |
721 | ty, | |
722 | obligation.cause.span, | |
723 | ) { | |
9fa01778 XL |
724 | Some(mut obligations) => { |
725 | self.add_depth(obligations.iter_mut(), obligation.recursion_depth); | |
726 | self.evaluate_predicates_recursively(previous_stack, obligations.into_iter()) | |
0bf4aa26 XL |
727 | } |
728 | None => Ok(EvaluatedToAmbig), | |
729 | }, | |
730 | ||
0731742a XL |
731 | ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => { |
732 | // we do not consider region relationships when | |
733 | // evaluating trait matches | |
734 | Ok(EvaluatedToOkModuloRegions) | |
1a4d82fc JJ |
735 | } |
736 | ||
e9174d1e | 737 | ty::Predicate::ObjectSafe(trait_def_id) => { |
a7813a04 | 738 | if self.tcx().is_object_safe(trait_def_id) { |
83c7162d | 739 | Ok(EvaluatedToOk) |
e9174d1e | 740 | } else { |
83c7162d | 741 | Ok(EvaluatedToErr) |
e9174d1e SL |
742 | } |
743 | } | |
744 | ||
1a4d82fc | 745 | ty::Predicate::Projection(ref data) => { |
92a42be0 SL |
746 | let project_obligation = obligation.with(data.clone()); |
747 | match project::poly_project_and_unify_type(self, &project_obligation) { | |
9fa01778 XL |
748 | Ok(Some(mut subobligations)) => { |
749 | self.add_depth(subobligations.iter_mut(), obligation.recursion_depth); | |
0bf4aa26 XL |
750 | let result = self.evaluate_predicates_recursively( |
751 | previous_stack, | |
9fa01778 | 752 | subobligations.into_iter(), |
0bf4aa26 | 753 | ); |
3b2f2976 XL |
754 | if let Some(key) = |
755 | ProjectionCacheKey::from_poly_projection_predicate(self, data) | |
756 | { | |
757 | self.infcx.projection_cache.borrow_mut().complete(key); | |
758 | } | |
759 | result | |
1a4d82fc | 760 | } |
0bf4aa26 XL |
761 | Ok(None) => Ok(EvaluatedToAmbig), |
762 | Err(_) => Ok(EvaluatedToErr), | |
92a42be0 | 763 | } |
1a4d82fc | 764 | } |
a7813a04 | 765 | |
ff7c6d11 XL |
766 | ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => { |
767 | match self.infcx.closure_kind(closure_def_id, closure_substs) { | |
a7813a04 XL |
768 | Some(closure_kind) => { |
769 | if closure_kind.extends(kind) { | |
83c7162d | 770 | Ok(EvaluatedToOk) |
a7813a04 | 771 | } else { |
83c7162d | 772 | Ok(EvaluatedToErr) |
a7813a04 XL |
773 | } |
774 | } | |
0bf4aa26 | 775 | None => Ok(EvaluatedToAmbig), |
a7813a04 XL |
776 | } |
777 | } | |
ea8adc8c XL |
778 | |
779 | ty::Predicate::ConstEvaluatable(def_id, substs) => { | |
0531ce1d XL |
780 | let tcx = self.tcx(); |
781 | match tcx.lift_to_global(&(obligation.param_env, substs)) { | |
ea8adc8c | 782 | Some((param_env, substs)) => { |
0bf4aa26 XL |
783 | let instance = |
784 | ty::Instance::resolve(tcx.global_tcx(), param_env, def_id, substs); | |
0531ce1d XL |
785 | if let Some(instance) = instance { |
786 | let cid = GlobalId { | |
787 | instance, | |
0bf4aa26 | 788 | promoted: None, |
0531ce1d XL |
789 | }; |
790 | match self.tcx().const_eval(param_env.and(cid)) { | |
83c7162d | 791 | Ok(_) => Ok(EvaluatedToOk), |
0bf4aa26 | 792 | Err(_) => Ok(EvaluatedToErr), |
0531ce1d XL |
793 | } |
794 | } else { | |
83c7162d | 795 | Ok(EvaluatedToErr) |
ea8adc8c XL |
796 | } |
797 | } | |
798 | None => { | |
799 | // Inference variables still left in param_env or substs. | |
83c7162d | 800 | Ok(EvaluatedToAmbig) |
ea8adc8c XL |
801 | } |
802 | } | |
803 | } | |
1a4d82fc JJ |
804 | } |
805 | } | |
806 | ||
0bf4aa26 XL |
807 | fn evaluate_trait_predicate_recursively<'o>( |
808 | &mut self, | |
809 | previous_stack: TraitObligationStackList<'o, 'tcx>, | |
810 | mut obligation: TraitObligation<'tcx>, | |
811 | ) -> Result<EvaluationResult, OverflowError> { | |
94b46f34 | 812 | debug!("evaluate_trait_predicate_recursively({:?})", obligation); |
1a4d82fc | 813 | |
94b46f34 | 814 | if self.intercrate.is_none() && obligation.is_global() |
0bf4aa26 XL |
815 | && obligation |
816 | .param_env | |
817 | .caller_bounds | |
818 | .iter() | |
819 | .all(|bound| bound.needs_subst()) | |
820 | { | |
94b46f34 XL |
821 | // If a param env has no global bounds, global obligations do not |
822 | // depend on its particular value in order to work, so we can clear | |
823 | // out the param env and get better caching. | |
0bf4aa26 XL |
824 | debug!( |
825 | "evaluate_trait_predicate_recursively({:?}) - in global", | |
826 | obligation | |
827 | ); | |
0531ce1d | 828 | obligation.param_env = obligation.param_env.without_caller_bounds(); |
3b2f2976 XL |
829 | } |
830 | ||
831 | let stack = self.push_stack(previous_stack, &obligation); | |
92a42be0 | 832 | let fresh_trait_ref = stack.fresh_trait_ref; |
7cac9316 | 833 | if let Some(result) = self.check_evaluation_cache(obligation.param_env, fresh_trait_ref) { |
0bf4aa26 | 834 | debug!("CACHE HIT: EVAL({:?})={:?}", fresh_trait_ref, result); |
83c7162d | 835 | return Ok(result); |
92a42be0 | 836 | } |
1a4d82fc | 837 | |
3b2f2976 | 838 | let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack)); |
83c7162d | 839 | let result = result?; |
1a4d82fc | 840 | |
0bf4aa26 | 841 | debug!("CACHE MISS: EVAL({:?})={:?}", fresh_trait_ref, result); |
3b2f2976 | 842 | self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result); |
92a42be0 | 843 | |
83c7162d | 844 | Ok(result) |
1a4d82fc JJ |
845 | } |
846 | ||
0bf4aa26 XL |
847 | fn evaluate_stack<'o>( |
848 | &mut self, | |
849 | stack: &TraitObligationStack<'o, 'tcx>, | |
850 | ) -> Result<EvaluationResult, OverflowError> { | |
1a4d82fc JJ |
851 | // In intercrate mode, whenever any of the types are unbound, |
852 | // there can always be an impl. Even if there are no impls in | |
853 | // this crate, perhaps the type would be unified with | |
854 | // something from another crate that does provide an impl. | |
855 | // | |
54a0048b | 856 | // In intra mode, we must still be conservative. The reason is |
1a4d82fc JJ |
857 | // that we want to avoid cycles. Imagine an impl like: |
858 | // | |
859 | // impl<T:Eq> Eq for Vec<T> | |
860 | // | |
861 | // and a trait reference like `$0 : Eq` where `$0` is an | |
862 | // unbound variable. When we evaluate this trait-reference, we | |
863 | // will unify `$0` with `Vec<$1>` (for some fresh variable | |
864 | // `$1`), on the condition that `$1 : Eq`. We will then wind | |
865 | // up with many candidates (since that are other `Eq` impls | |
866 | // that apply) and try to winnow things down. This results in | |
867 | // a recursive evaluation that `$1 : Eq` -- as you can | |
868 | // imagine, this is just where we started. To avoid that, we | |
869 | // check for unbound variables and return an ambiguous (hence possible) | |
870 | // match if we've seen this trait before. | |
871 | // | |
872 | // This suffices to allow chains like `FnMut` implemented in | |
873 | // terms of `Fn` etc, but we could probably make this more | |
874 | // precise still. | |
0bf4aa26 XL |
875 | let unbound_input_types = stack |
876 | .fresh_trait_ref | |
877 | .skip_binder() | |
878 | .input_types() | |
879 | .any(|ty| ty.is_fresh()); | |
ff7c6d11 XL |
880 | // this check was an imperfect workaround for a bug n the old |
881 | // intercrate mode, it should be removed when that goes away. | |
0bf4aa26 XL |
882 | if unbound_input_types && self.intercrate == Some(IntercrateMode::Issue43355) { |
883 | debug!( | |
884 | "evaluate_stack({:?}) --> unbound argument, intercrate --> ambiguous", | |
885 | stack.fresh_trait_ref | |
886 | ); | |
ea8adc8c | 887 | // Heuristics: show the diagnostics when there are no candidates in crate. |
ff7c6d11 XL |
888 | if self.intercrate_ambiguity_causes.is_some() { |
889 | debug!("evaluate_stack: intercrate_ambiguity_causes is some"); | |
890 | if let Ok(candidate_set) = self.assemble_candidates(stack) { | |
891 | if !candidate_set.ambiguous && candidate_set.vec.is_empty() { | |
892 | let trait_ref = stack.obligation.predicate.skip_binder().trait_ref; | |
893 | let self_ty = trait_ref.self_ty(); | |
894 | let cause = IntercrateAmbiguityCause::DownstreamCrate { | |
895 | trait_desc: trait_ref.to_string(), | |
896 | self_desc: if self_ty.has_concrete_skeleton() { | |
897 | Some(self_ty.to_string()) | |
898 | } else { | |
899 | None | |
900 | }, | |
901 | }; | |
902 | debug!("evaluate_stack: pushing cause = {:?}", cause); | |
0bf4aa26 XL |
903 | self.intercrate_ambiguity_causes |
904 | .as_mut() | |
905 | .unwrap() | |
906 | .push(cause); | |
ff7c6d11 | 907 | } |
ea8adc8c XL |
908 | } |
909 | } | |
83c7162d | 910 | return Ok(EvaluatedToAmbig); |
92a42be0 | 911 | } |
0bf4aa26 XL |
912 | if unbound_input_types && stack.iter().skip(1).any(|prev| { |
913 | stack.obligation.param_env == prev.obligation.param_env | |
914 | && self.match_fresh_trait_refs(&stack.fresh_trait_ref, &prev.fresh_trait_ref) | |
915 | }) { | |
916 | debug!( | |
917 | "evaluate_stack({:?}) --> unbound argument, recursive --> giving up", | |
918 | stack.fresh_trait_ref | |
919 | ); | |
83c7162d | 920 | return Ok(EvaluatedToUnknown); |
1a4d82fc JJ |
921 | } |
922 | ||
923 | // If there is any previous entry on the stack that precisely | |
924 | // matches this obligation, then we can assume that the | |
925 | // obligation is satisfied for now (still all other conditions | |
926 | // must be met of course). One obvious case this comes up is | |
927 | // marker traits like `Send`. Think of a linked list: | |
928 | // | |
0bf4aa26 | 929 | // struct List<T> { data: T, next: Option<Box<List<T>>> } |
1a4d82fc JJ |
930 | // |
931 | // `Box<List<T>>` will be `Send` if `T` is `Send` and | |
932 | // `Option<Box<List<T>>>` is `Send`, and in turn | |
933 | // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is | |
934 | // `Send`. | |
935 | // | |
936 | // Note that we do this comparison using the `fresh_trait_ref` | |
0bf4aa26 | 937 | // fields. Because these have all been freshened using |
1a4d82fc JJ |
938 | // `self.freshener`, we can be sure that (a) this will not |
939 | // affect the inferencer state and (b) that if we see two | |
0bf4aa26 XL |
940 | // fresh regions with the same index, they refer to the same |
941 | // unbound type variable. | |
942 | if let Some(rec_index) = stack.iter() | |
943 | .skip(1) // skip top-most frame | |
944 | .position(|prev| stack.obligation.param_env == prev.obligation.param_env && | |
945 | stack.fresh_trait_ref == prev.fresh_trait_ref) | |
1a4d82fc | 946 | { |
0bf4aa26 XL |
947 | debug!("evaluate_stack({:?}) --> recursive", stack.fresh_trait_ref); |
948 | ||
0731742a XL |
949 | // Subtle: when checking for a coinductive cycle, we do |
950 | // not compare using the "freshened trait refs" (which | |
951 | // have erased regions) but rather the fully explicit | |
952 | // trait refs. This is important because it's only a cycle | |
953 | // if the regions match exactly. | |
0bf4aa26 | 954 | let cycle = stack.iter().skip(1).take(rec_index + 1); |
3b2f2976 XL |
955 | let cycle = cycle.map(|stack| ty::Predicate::Trait(stack.obligation.predicate)); |
956 | if self.coinductive_match(cycle) { | |
0bf4aa26 XL |
957 | debug!( |
958 | "evaluate_stack({:?}) --> recursive, coinductive", | |
959 | stack.fresh_trait_ref | |
960 | ); | |
83c7162d | 961 | return Ok(EvaluatedToOk); |
3b2f2976 | 962 | } else { |
0bf4aa26 XL |
963 | debug!( |
964 | "evaluate_stack({:?}) --> recursive, inductive", | |
965 | stack.fresh_trait_ref | |
966 | ); | |
83c7162d | 967 | return Ok(EvaluatedToRecur); |
3b2f2976 | 968 | } |
1a4d82fc JJ |
969 | } |
970 | ||
971 | match self.candidate_from_obligation(stack) { | |
92a42be0 | 972 | Ok(Some(c)) => self.evaluate_candidate(stack, &c), |
83c7162d XL |
973 | Ok(None) => Ok(EvaluatedToAmbig), |
974 | Err(Overflow) => Err(OverflowError), | |
0bf4aa26 | 975 | Err(..) => Ok(EvaluatedToErr), |
1a4d82fc JJ |
976 | } |
977 | } | |
978 | ||
3b2f2976 XL |
979 | /// For defaulted traits, we use a co-inductive strategy to solve, so |
980 | /// that recursion is ok. This routine returns true if the top of the | |
981 | /// stack (`cycle[0]`): | |
ff7c6d11 | 982 | /// |
9fa01778 XL |
983 | /// - is a defaulted trait, |
984 | /// - it also appears in the backtrace at some position `X`, | |
3b2f2976 XL |
985 | /// - all the predicates at positions `X..` between `X` an the top are |
986 | /// also defaulted traits. | |
987 | pub fn coinductive_match<I>(&mut self, cycle: I) -> bool | |
0bf4aa26 XL |
988 | where |
989 | I: Iterator<Item = ty::Predicate<'tcx>>, | |
3b2f2976 XL |
990 | { |
991 | let mut cycle = cycle; | |
992 | cycle.all(|predicate| self.coinductive_predicate(predicate)) | |
993 | } | |
994 | ||
995 | fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool { | |
996 | let result = match predicate { | |
0bf4aa26 XL |
997 | ty::Predicate::Trait(ref data) => self.tcx().trait_is_auto(data.def_id()), |
998 | _ => false, | |
3b2f2976 XL |
999 | }; |
1000 | debug!("coinductive_predicate({:?}) = {:?}", predicate, result); | |
1001 | result | |
1002 | } | |
1003 | ||
92a42be0 | 1004 | /// Further evaluate `candidate` to decide whether all type parameters match and whether nested |
9fa01778 | 1005 | /// obligations are met. Returns whether `candidate` remains viable after this further |
92a42be0 | 1006 | /// scrutiny. |
0bf4aa26 XL |
1007 | fn evaluate_candidate<'o>( |
1008 | &mut self, | |
1009 | stack: &TraitObligationStack<'o, 'tcx>, | |
1010 | candidate: &SelectionCandidate<'tcx>, | |
1011 | ) -> Result<EvaluationResult, OverflowError> { | |
1012 | debug!( | |
1013 | "evaluate_candidate: depth={} candidate={:?}", | |
1014 | stack.obligation.recursion_depth, candidate | |
1015 | ); | |
0731742a | 1016 | let result = self.evaluation_probe(|this| { |
92a42be0 | 1017 | let candidate = (*candidate).clone(); |
a7813a04 | 1018 | match this.confirm_candidate(stack.obligation, candidate) { |
0bf4aa26 XL |
1019 | Ok(selection) => this.evaluate_predicates_recursively( |
1020 | stack.list(), | |
9fa01778 | 1021 | selection.nested_obligations().into_iter() |
0bf4aa26 XL |
1022 | ), |
1023 | Err(..) => Ok(EvaluatedToErr), | |
1a4d82fc | 1024 | } |
83c7162d | 1025 | })?; |
0bf4aa26 XL |
1026 | debug!( |
1027 | "evaluate_candidate: depth={} result={:?}", | |
1028 | stack.obligation.recursion_depth, result | |
1029 | ); | |
83c7162d | 1030 | Ok(result) |
92a42be0 SL |
1031 | } |
1032 | ||
0bf4aa26 XL |
1033 | fn check_evaluation_cache( |
1034 | &self, | |
1035 | param_env: ty::ParamEnv<'tcx>, | |
1036 | trait_ref: ty::PolyTraitRef<'tcx>, | |
1037 | ) -> Option<EvaluationResult> { | |
3b2f2976 | 1038 | let tcx = self.tcx(); |
7cac9316 | 1039 | if self.can_use_global_caches(param_env) { |
3b2f2976 | 1040 | let cache = tcx.evaluation_cache.hashmap.borrow(); |
a7813a04 | 1041 | if let Some(cached) = cache.get(&trait_ref) { |
3b2f2976 | 1042 | return Some(cached.get(tcx)); |
a7813a04 XL |
1043 | } |
1044 | } | |
0bf4aa26 XL |
1045 | self.infcx |
1046 | .evaluation_cache | |
1047 | .hashmap | |
1048 | .borrow() | |
1049 | .get(&trait_ref) | |
1050 | .map(|v| v.get(tcx)) | |
92a42be0 SL |
1051 | } |
1052 | ||
0bf4aa26 XL |
1053 | fn insert_evaluation_cache( |
1054 | &mut self, | |
1055 | param_env: ty::ParamEnv<'tcx>, | |
1056 | trait_ref: ty::PolyTraitRef<'tcx>, | |
1057 | dep_node: DepNodeIndex, | |
1058 | result: EvaluationResult, | |
1059 | ) { | |
3b2f2976 XL |
1060 | // Avoid caching results that depend on more than just the trait-ref |
1061 | // - the stack can create recursion. | |
1062 | if result.is_stack_dependent() { | |
92a42be0 SL |
1063 | return; |
1064 | } | |
1065 | ||
7cac9316 | 1066 | if self.can_use_global_caches(param_env) { |
a7813a04 | 1067 | if let Some(trait_ref) = self.tcx().lift_to_global(&trait_ref) { |
0531ce1d XL |
1068 | debug!( |
1069 | "insert_evaluation_cache(trait_ref={:?}, candidate={:?}) global", | |
0bf4aa26 | 1070 | trait_ref, result, |
0531ce1d | 1071 | ); |
94b46f34 XL |
1072 | // This may overwrite the cache with the same value |
1073 | // FIXME: Due to #50507 this overwrites the different values | |
1074 | // This should be changed to use HashMapExt::insert_same | |
1075 | // when that is fixed | |
0bf4aa26 XL |
1076 | self.tcx() |
1077 | .evaluation_cache | |
1078 | .hashmap | |
1079 | .borrow_mut() | |
1080 | .insert(trait_ref, WithDepNode::new(dep_node, result)); | |
a7813a04 XL |
1081 | return; |
1082 | } | |
1083 | } | |
1084 | ||
0531ce1d XL |
1085 | debug!( |
1086 | "insert_evaluation_cache(trait_ref={:?}, candidate={:?})", | |
0bf4aa26 | 1087 | trait_ref, result, |
0531ce1d | 1088 | ); |
0bf4aa26 XL |
1089 | self.infcx |
1090 | .evaluation_cache | |
1091 | .hashmap | |
1092 | .borrow_mut() | |
1093 | .insert(trait_ref, WithDepNode::new(dep_node, result)); | |
1a4d82fc JJ |
1094 | } |
1095 | ||
9fa01778 XL |
1096 | // For various reasons, it's possible for a subobligation |
1097 | // to have a *lower* recursion_depth than the obligation used to create it. | |
1098 | // Projection sub-obligations may be returned from the projection cache, | |
1099 | // which results in obligations with an 'old' recursion_depth. | |
1100 | // Additionally, methods like ty::wf::obligations and | |
1101 | // InferCtxt.subtype_predicate produce subobligations without | |
1102 | // taking in a 'parent' depth, causing the generated subobligations | |
1103 | // to have a recursion_depth of 0 | |
1104 | // | |
1105 | // To ensure that obligation_depth never decreasees, we force all subobligations | |
1106 | // to have at least the depth of the original obligation. | |
1107 | fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>(&self, it: I, | |
1108 | min_depth: usize) { | |
1109 | it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1); | |
1110 | } | |
1111 | ||
1112 | // Check that the recursion limit has not been exceeded. | |
1113 | // | |
1114 | // The weird return type of this function allows it to be used with the 'try' (?) | |
1115 | // operator within certain functions | |
1116 | fn check_recursion_limit<T: Display + TypeFoldable<'tcx>, V: Display + TypeFoldable<'tcx>>( | |
1117 | &self, | |
1118 | obligation: &Obligation<'tcx, T>, | |
1119 | error_obligation: &Obligation<'tcx, V> | |
1120 | ) -> Result<(), OverflowError> { | |
1121 | let recursion_limit = *self.infcx.tcx.sess.recursion_limit.get(); | |
1122 | if obligation.recursion_depth >= recursion_limit { | |
1123 | match self.query_mode { | |
1124 | TraitQueryMode::Standard => { | |
1125 | self.infcx().report_overflow_error(error_obligation, true); | |
1126 | } | |
1127 | TraitQueryMode::Canonical => { | |
1128 | return Err(OverflowError); | |
1129 | } | |
1130 | } | |
1131 | } | |
1132 | Ok(()) | |
1133 | } | |
1134 | ||
1a4d82fc JJ |
1135 | /////////////////////////////////////////////////////////////////////////// |
1136 | // CANDIDATE ASSEMBLY | |
1137 | // | |
1138 | // The selection process begins by examining all in-scope impls, | |
1139 | // caller obligations, and so forth and assembling a list of | |
0731742a | 1140 | // candidates. See the [rustc guide] for more details. |
0531ce1d XL |
1141 | // |
1142 | // [rustc guide]: | |
a1dfa0c6 | 1143 | // https://rust-lang.github.io/rustc-guide/traits/resolution.html#candidate-assembly |
1a4d82fc | 1144 | |
0bf4aa26 XL |
1145 | fn candidate_from_obligation<'o>( |
1146 | &mut self, | |
1147 | stack: &TraitObligationStack<'o, 'tcx>, | |
1148 | ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { | |
1a4d82fc JJ |
1149 | // Watch out for overflow. This intentionally bypasses (and does |
1150 | // not update) the cache. | |
9fa01778 XL |
1151 | self.check_recursion_limit(&stack.obligation, &stack.obligation)?; |
1152 | ||
1a4d82fc | 1153 | |
0bf4aa26 XL |
1154 | // Check the cache. Note that we freshen the trait-ref |
1155 | // separately rather than using `stack.fresh_trait_ref` -- | |
1156 | // this is because we want the unbound variables to be | |
1157 | // replaced with fresh types starting from index 0. | |
1158 | let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate.clone()); | |
1159 | debug!( | |
1160 | "candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})", | |
1161 | cache_fresh_trait_pred, stack | |
1162 | ); | |
a1dfa0c6 | 1163 | debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars()); |
1a4d82fc | 1164 | |
0bf4aa26 XL |
1165 | if let Some(c) = |
1166 | self.check_candidate_cache(stack.obligation.param_env, &cache_fresh_trait_pred) | |
1167 | { | |
1168 | debug!("CACHE HIT: SELECT({:?})={:?}", cache_fresh_trait_pred, c); | |
c30ab7b3 | 1169 | return c; |
1a4d82fc JJ |
1170 | } |
1171 | ||
1172 | // If no match, compute result and insert into cache. | |
0bf4aa26 XL |
1173 | let (candidate, dep_node) = |
1174 | self.in_task(|this| this.candidate_from_obligation_no_cache(stack)); | |
85aaf69f | 1175 | |
0bf4aa26 XL |
1176 | debug!( |
1177 | "CACHE MISS: SELECT({:?})={:?}", | |
1178 | cache_fresh_trait_pred, candidate | |
1179 | ); | |
1180 | self.insert_candidate_cache( | |
1181 | stack.obligation.param_env, | |
1182 | cache_fresh_trait_pred, | |
1183 | dep_node, | |
1184 | candidate.clone(), | |
1185 | ); | |
1a4d82fc JJ |
1186 | candidate |
1187 | } | |
1188 | ||
3b2f2976 | 1189 | fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex) |
0bf4aa26 XL |
1190 | where |
1191 | OP: FnOnce(&mut Self) -> R, | |
3b2f2976 | 1192 | { |
0bf4aa26 XL |
1193 | let (result, dep_node) = self.tcx() |
1194 | .dep_graph | |
1195 | .with_anon_task(DepKind::TraitSelect, || op(self)); | |
3b2f2976 XL |
1196 | self.tcx().dep_graph.read_index(dep_node); |
1197 | (result, dep_node) | |
1198 | } | |
1199 | ||
54a0048b | 1200 | // Treat negative impls as unimplemented |
0bf4aa26 XL |
1201 | fn filter_negative_impls( |
1202 | &self, | |
1203 | candidate: SelectionCandidate<'tcx>, | |
1204 | ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { | |
54a0048b | 1205 | if let ImplCandidate(def_id) = candidate { |
0bf4aa26 XL |
1206 | if !self.allow_negative_impls |
1207 | && self.tcx().impl_polarity(def_id) == hir::ImplPolarity::Negative | |
1208 | { | |
1209 | return Err(Unimplemented); | |
54a0048b SL |
1210 | } |
1211 | } | |
1212 | Ok(Some(candidate)) | |
1213 | } | |
1214 | ||
0bf4aa26 XL |
1215 | fn candidate_from_obligation_no_cache<'o>( |
1216 | &mut self, | |
1217 | stack: &TraitObligationStack<'o, 'tcx>, | |
1218 | ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { | |
9cc50fc6 | 1219 | if stack.obligation.predicate.references_error() { |
b7449926 | 1220 | // If we encounter a `Error`, we generally prefer the |
9cc50fc6 SL |
1221 | // most "optimistic" result in response -- that is, the |
1222 | // one least likely to report downstream errors. But | |
1223 | // because this routine is shared by coherence and by | |
1224 | // trait selection, there isn't an obvious "right" choice | |
1225 | // here in that respect, so we opt to just return | |
1226 | // ambiguity and let the upstream clients sort it out. | |
1227 | return Ok(None); | |
1a4d82fc JJ |
1228 | } |
1229 | ||
0bf4aa26 XL |
1230 | if let Some(conflict) = self.is_knowable(stack) { |
1231 | debug!("coherence stage: not knowable"); | |
1232 | if self.intercrate_ambiguity_causes.is_some() { | |
1233 | debug!("evaluate_stack: intercrate_ambiguity_causes is some"); | |
1234 | // Heuristics: show the diagnostics when there are no candidates in crate. | |
1235 | if let Ok(candidate_set) = self.assemble_candidates(stack) { | |
1236 | let mut no_candidates_apply = true; | |
1237 | { | |
1238 | let evaluated_candidates = candidate_set | |
83c7162d XL |
1239 | .vec |
1240 | .iter() | |
0bf4aa26 XL |
1241 | .map(|c| self.evaluate_candidate(stack, &c)); |
1242 | ||
1243 | for ec in evaluated_candidates { | |
1244 | match ec { | |
1245 | Ok(c) => { | |
1246 | if c.may_apply() { | |
1247 | no_candidates_apply = false; | |
1248 | break; | |
1249 | } | |
0531ce1d | 1250 | } |
0bf4aa26 XL |
1251 | Err(e) => return Err(e.into()), |
1252 | } | |
0531ce1d | 1253 | } |
ff7c6d11 | 1254 | } |
0bf4aa26 XL |
1255 | |
1256 | if !candidate_set.ambiguous && no_candidates_apply { | |
1257 | let trait_ref = stack.obligation.predicate.skip_binder().trait_ref; | |
1258 | let self_ty = trait_ref.self_ty(); | |
1259 | let trait_desc = trait_ref.to_string(); | |
1260 | let self_desc = if self_ty.has_concrete_skeleton() { | |
1261 | Some(self_ty.to_string()) | |
1262 | } else { | |
1263 | None | |
1264 | }; | |
1265 | let cause = if let Conflict::Upstream = conflict { | |
1266 | IntercrateAmbiguityCause::UpstreamCrateUpdate { | |
1267 | trait_desc, | |
1268 | self_desc, | |
1269 | } | |
1270 | } else { | |
1271 | IntercrateAmbiguityCause::DownstreamCrate { | |
1272 | trait_desc, | |
1273 | self_desc, | |
1274 | } | |
1275 | }; | |
1276 | debug!("evaluate_stack: pushing cause = {:?}", cause); | |
1277 | self.intercrate_ambiguity_causes | |
1278 | .as_mut() | |
1279 | .unwrap() | |
1280 | .push(cause); | |
1281 | } | |
ff7c6d11 | 1282 | } |
ea8adc8c | 1283 | } |
0bf4aa26 | 1284 | return Ok(None); |
c34b1796 AL |
1285 | } |
1286 | ||
54a0048b | 1287 | let candidate_set = self.assemble_candidates(stack)?; |
1a4d82fc JJ |
1288 | |
1289 | if candidate_set.ambiguous { | |
1290 | debug!("candidate set contains ambig"); | |
1291 | return Ok(None); | |
1292 | } | |
1293 | ||
1294 | let mut candidates = candidate_set.vec; | |
1295 | ||
0bf4aa26 XL |
1296 | debug!( |
1297 | "assembled {} candidates for {:?}: {:?}", | |
1298 | candidates.len(), | |
1299 | stack, | |
1300 | candidates | |
1301 | ); | |
1a4d82fc JJ |
1302 | |
1303 | // At this point, we know that each of the entries in the | |
1304 | // candidate set is *individually* applicable. Now we have to | |
1305 | // figure out if they contain mutual incompatibilities. This | |
1306 | // frequently arises if we have an unconstrained input type -- | |
1307 | // for example, we are looking for $0:Eq where $0 is some | |
1308 | // unconstrained type variable. In that case, we'll get a | |
1309 | // candidate which assumes $0 == int, one that assumes $0 == | |
c34b1796 | 1310 | // usize, etc. This spells an ambiguity. |
1a4d82fc JJ |
1311 | |
1312 | // If there is more than one candidate, first winnow them down | |
1313 | // by considering extra conditions (nested obligations and so | |
1314 | // forth). We don't winnow if there is exactly one | |
1315 | // candidate. This is a relatively minor distinction but it | |
1316 | // can lead to better inference and error-reporting. An | |
1317 | // example would be if there was an impl: | |
1318 | // | |
1319 | // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } } | |
1320 | // | |
1321 | // and we were to see some code `foo.push_clone()` where `boo` | |
1322 | // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If | |
1323 | // we were to winnow, we'd wind up with zero candidates. | |
1324 | // Instead, we select the right impl now but report `Bar does | |
1325 | // not implement Clone`. | |
54a0048b SL |
1326 | if candidates.len() == 1 { |
1327 | return self.filter_negative_impls(candidates.pop().unwrap()); | |
1a4d82fc JJ |
1328 | } |
1329 | ||
54a0048b | 1330 | // Winnow, but record the exact outcome of evaluation, which |
83c7162d | 1331 | // is needed for specialization. Propagate overflow if it occurs. |
a1dfa0c6 XL |
1332 | let mut candidates = candidates |
1333 | .into_iter() | |
83c7162d XL |
1334 | .map(|c| match self.evaluate_candidate(stack, &c) { |
1335 | Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate { | |
54a0048b SL |
1336 | candidate: c, |
1337 | evaluation: eval, | |
83c7162d XL |
1338 | })), |
1339 | Ok(_) => Ok(None), | |
1340 | Err(OverflowError) => Err(Overflow), | |
1341 | }) | |
a1dfa0c6 XL |
1342 | .flat_map(Result::transpose) |
1343 | .collect::<Result<Vec<_>, _>>()?; | |
83c7162d | 1344 | |
0bf4aa26 XL |
1345 | debug!( |
1346 | "winnowed to {} candidates for {:?}: {:?}", | |
1347 | candidates.len(), | |
1348 | stack, | |
1349 | candidates | |
1350 | ); | |
8faf50e0 | 1351 | |
0bf4aa26 | 1352 | // If there are STILL multiple candidates, we can further |
54a0048b SL |
1353 | // reduce the list by dropping duplicates -- including |
1354 | // resolving specializations. | |
1a4d82fc JJ |
1355 | if candidates.len() > 1 { |
1356 | let mut i = 0; | |
1357 | while i < candidates.len() { | |
0bf4aa26 XL |
1358 | let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| { |
1359 | self.candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j]) | |
1360 | }); | |
1a4d82fc | 1361 | if is_dup { |
0bf4aa26 XL |
1362 | debug!( |
1363 | "Dropping candidate #{}/{}: {:?}", | |
1364 | i, | |
1365 | candidates.len(), | |
1366 | candidates[i] | |
1367 | ); | |
1a4d82fc JJ |
1368 | candidates.swap_remove(i); |
1369 | } else { | |
0bf4aa26 XL |
1370 | debug!( |
1371 | "Retaining candidate #{}/{}: {:?}", | |
1372 | i, | |
1373 | candidates.len(), | |
1374 | candidates[i] | |
1375 | ); | |
1a4d82fc | 1376 | i += 1; |
cc61c64b XL |
1377 | |
1378 | // If there are *STILL* multiple candidates, give up | |
1379 | // and report ambiguity. | |
1380 | if i > 1 { | |
1381 | debug!("multiple matches, ambig"); | |
1382 | return Ok(None); | |
1383 | } | |
1a4d82fc JJ |
1384 | } |
1385 | } | |
1386 | } | |
1387 | ||
54a0048b | 1388 | // If there are *NO* candidates, then there are no impls -- |
1a4d82fc JJ |
1389 | // that we know of, anyway. Note that in the case where there |
1390 | // are unbound type variables within the obligation, it might | |
1391 | // be the case that you could still satisfy the obligation | |
1392 | // from another crate by instantiating the type variables with | |
1393 | // a type from another crate that does have an impl. This case | |
1394 | // is checked for in `evaluate_stack` (and hence users | |
1395 | // who might care about this case, like coherence, should use | |
1396 | // that function). | |
9346a6ac | 1397 | if candidates.is_empty() { |
1a4d82fc JJ |
1398 | return Err(Unimplemented); |
1399 | } | |
1400 | ||
1401 | // Just one candidate left. | |
54a0048b | 1402 | self.filter_negative_impls(candidates.pop().unwrap().candidate) |
1a4d82fc JJ |
1403 | } |
1404 | ||
0bf4aa26 | 1405 | fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Option<Conflict> { |
ff7c6d11 | 1406 | debug!("is_knowable(intercrate={:?})", self.intercrate); |
c34b1796 | 1407 | |
ff7c6d11 XL |
1408 | if !self.intercrate.is_some() { |
1409 | return None; | |
c34b1796 AL |
1410 | } |
1411 | ||
1412 | let obligation = &stack.obligation; | |
0bf4aa26 XL |
1413 | let predicate = self.infcx() |
1414 | .resolve_type_vars_if_possible(&obligation.predicate); | |
c34b1796 | 1415 | |
a1dfa0c6 | 1416 | // OK to skip binder because of the nature of the |
c34b1796 AL |
1417 | // trait-ref-is-knowable check, which does not care about |
1418 | // bound regions | |
ea8adc8c | 1419 | let trait_ref = predicate.skip_binder().trait_ref; |
c34b1796 | 1420 | |
ff7c6d11 | 1421 | let result = coherence::trait_ref_is_knowable(self.tcx(), trait_ref); |
0bf4aa26 XL |
1422 | if let ( |
1423 | Some(Conflict::Downstream { | |
1424 | used_to_be_broken: true, | |
1425 | }), | |
1426 | Some(IntercrateMode::Issue43355), | |
1427 | ) = (result, self.intercrate) | |
1428 | { | |
ff7c6d11 XL |
1429 | debug!("is_knowable: IGNORING conflict to be bug-compatible with #43355"); |
1430 | None | |
1431 | } else { | |
1432 | result | |
1433 | } | |
c34b1796 AL |
1434 | } |
1435 | ||
9fa01778 | 1436 | /// Returns `true` if the global caches can be used. |
a7813a04 XL |
1437 | /// Do note that if the type itself is not in the |
1438 | /// global tcx, the local caches will be used. | |
7cac9316 | 1439 | fn can_use_global_caches(&self, param_env: ty::ParamEnv<'tcx>) -> bool { |
85aaf69f SL |
1440 | // If there are any where-clauses in scope, then we always use |
1441 | // a cache local to this particular scope. Otherwise, we | |
1442 | // switch to a global cache. We used to try and draw | |
1443 | // finer-grained distinctions, but that led to a serious of | |
1444 | // annoying and weird bugs like #22019 and #18290. This simple | |
1445 | // rule seems to be pretty clearly safe and also still retains | |
1446 | // a very high hit rate (~95% when compiling rustc). | |
7cac9316 | 1447 | if !param_env.caller_bounds.is_empty() { |
a7813a04 | 1448 | return false; |
85aaf69f | 1449 | } |
1a4d82fc JJ |
1450 | |
1451 | // Avoid using the master cache during coherence and just rely | |
1452 | // on the local cache. This effectively disables caching | |
1453 | // during coherence. It is really just a simplification to | |
1454 | // avoid us having to fear that coherence results "pollute" | |
1455 | // the master cache. Since coherence executes pretty quickly, | |
1456 | // it's not worth going to more trouble to increase the | |
1457 | // hit-rate I don't think. | |
ff7c6d11 | 1458 | if self.intercrate.is_some() { |
a7813a04 | 1459 | return false; |
1a4d82fc JJ |
1460 | } |
1461 | ||
1a4d82fc | 1462 | // Otherwise, we can use the global cache. |
a7813a04 | 1463 | true |
1a4d82fc JJ |
1464 | } |
1465 | ||
0bf4aa26 XL |
1466 | fn check_candidate_cache( |
1467 | &mut self, | |
1468 | param_env: ty::ParamEnv<'tcx>, | |
1469 | cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>, | |
1470 | ) -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>> { | |
3b2f2976 | 1471 | let tcx = self.tcx(); |
83c7162d | 1472 | let trait_ref = &cache_fresh_trait_pred.skip_binder().trait_ref; |
7cac9316 | 1473 | if self.can_use_global_caches(param_env) { |
3b2f2976 | 1474 | let cache = tcx.selection_cache.hashmap.borrow(); |
a7813a04 | 1475 | if let Some(cached) = cache.get(&trait_ref) { |
3b2f2976 | 1476 | return Some(cached.get(tcx)); |
a7813a04 XL |
1477 | } |
1478 | } | |
0bf4aa26 XL |
1479 | self.infcx |
1480 | .selection_cache | |
1481 | .hashmap | |
1482 | .borrow() | |
1483 | .get(trait_ref) | |
1484 | .map(|v| v.get(tcx)) | |
1a4d82fc JJ |
1485 | } |
1486 | ||
13cf67c4 XL |
1487 | /// Determines whether can we safely cache the result |
1488 | /// of selecting an obligation. This is almost always 'true', | |
1489 | /// except when dealing with certain ParamCandidates. | |
1490 | /// | |
1491 | /// Ordinarily, a ParamCandidate will contain no inference variables, | |
1492 | /// since it was usually produced directly from a DefId. However, | |
1493 | /// certain cases (currently only librustdoc's blanket impl finder), | |
1494 | /// a ParamEnv may be explicitly constructed with inference types. | |
1495 | /// When this is the case, we do *not* want to cache the resulting selection | |
1496 | /// candidate. This is due to the fact that it might not always be possible | |
1497 | /// to equate the obligation's trait ref and the candidate's trait ref, | |
1498 | /// if more constraints end up getting added to an inference variable. | |
1499 | /// | |
1500 | /// Because of this, we always want to re-run the full selection | |
1501 | /// process for our obligation the next time we see it, since | |
1502 | /// we might end up picking a different SelectionCandidate (or none at all) | |
1503 | fn can_cache_candidate(&self, | |
1504 | result: &SelectionResult<'tcx, SelectionCandidate<'tcx>> | |
1505 | ) -> bool { | |
1506 | match result { | |
1507 | Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => { | |
1508 | !trait_ref.skip_binder().input_types().any(|t| t.walk().any(|t_| t_.is_ty_infer())) | |
1509 | }, | |
1510 | _ => true | |
1511 | } | |
1512 | } | |
1513 | ||
0bf4aa26 XL |
1514 | fn insert_candidate_cache( |
1515 | &mut self, | |
1516 | param_env: ty::ParamEnv<'tcx>, | |
1517 | cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
1518 | dep_node: DepNodeIndex, | |
1519 | candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>, | |
1520 | ) { | |
3b2f2976 | 1521 | let tcx = self.tcx(); |
83c7162d | 1522 | let trait_ref = cache_fresh_trait_pred.skip_binder().trait_ref; |
13cf67c4 XL |
1523 | |
1524 | if !self.can_cache_candidate(&candidate) { | |
1525 | debug!("insert_candidate_cache(trait_ref={:?}, candidate={:?} -\ | |
1526 | candidate is not cacheable", trait_ref, candidate); | |
1527 | return; | |
1528 | ||
1529 | } | |
1530 | ||
7cac9316 | 1531 | if self.can_use_global_caches(param_env) { |
0bf4aa26 XL |
1532 | if let Err(Overflow) = candidate { |
1533 | // Don't cache overflow globally; we only produce this | |
1534 | // in certain modes. | |
1535 | } else if let Some(trait_ref) = tcx.lift_to_global(&trait_ref) { | |
3b2f2976 | 1536 | if let Some(candidate) = tcx.lift_to_global(&candidate) { |
0531ce1d XL |
1537 | debug!( |
1538 | "insert_candidate_cache(trait_ref={:?}, candidate={:?}) global", | |
0bf4aa26 | 1539 | trait_ref, candidate, |
0531ce1d | 1540 | ); |
94b46f34 XL |
1541 | // This may overwrite the cache with the same value |
1542 | tcx.selection_cache | |
0bf4aa26 XL |
1543 | .hashmap |
1544 | .borrow_mut() | |
1545 | .insert(trait_ref, WithDepNode::new(dep_node, candidate)); | |
a7813a04 XL |
1546 | return; |
1547 | } | |
1548 | } | |
1549 | } | |
1550 | ||
0531ce1d XL |
1551 | debug!( |
1552 | "insert_candidate_cache(trait_ref={:?}, candidate={:?}) local", | |
0bf4aa26 | 1553 | trait_ref, candidate, |
0531ce1d | 1554 | ); |
0bf4aa26 XL |
1555 | self.infcx |
1556 | .selection_cache | |
1557 | .hashmap | |
1558 | .borrow_mut() | |
1559 | .insert(trait_ref, WithDepNode::new(dep_node, candidate)); | |
85aaf69f SL |
1560 | } |
1561 | ||
0bf4aa26 XL |
1562 | fn assemble_candidates<'o>( |
1563 | &mut self, | |
1564 | stack: &TraitObligationStack<'o, 'tcx>, | |
1565 | ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> { | |
1a4d82fc | 1566 | let TraitObligationStack { obligation, .. } = *stack; |
e9174d1e | 1567 | let ref obligation = Obligation { |
7cac9316 | 1568 | param_env: obligation.param_env, |
e9174d1e SL |
1569 | cause: obligation.cause.clone(), |
1570 | recursion_depth: obligation.recursion_depth, | |
0bf4aa26 XL |
1571 | predicate: self.infcx() |
1572 | .resolve_type_vars_if_possible(&obligation.predicate), | |
e9174d1e SL |
1573 | }; |
1574 | ||
1575 | if obligation.predicate.skip_binder().self_ty().is_ty_var() { | |
0731742a | 1576 | // Self is a type variable (e.g., `_: AsRef<str>`). |
e9174d1e SL |
1577 | // |
1578 | // This is somewhat problematic, as the current scheme can't really | |
1579 | // handle it turning to be a projection. This does end up as truly | |
1580 | // ambiguous in most cases anyway. | |
1581 | // | |
abe05a73 | 1582 | // Take the fast path out - this also improves |
e9174d1e SL |
1583 | // performance by preventing assemble_candidates_from_impls from |
1584 | // matching every impl for this trait. | |
0bf4aa26 XL |
1585 | return Ok(SelectionCandidateSet { |
1586 | vec: vec![], | |
1587 | ambiguous: true, | |
1588 | }); | |
e9174d1e | 1589 | } |
1a4d82fc JJ |
1590 | |
1591 | let mut candidates = SelectionCandidateSet { | |
1592 | vec: Vec::new(), | |
0bf4aa26 | 1593 | ambiguous: false, |
1a4d82fc JJ |
1594 | }; |
1595 | ||
a1dfa0c6 XL |
1596 | self.assemble_candidates_for_trait_alias(obligation, &mut candidates)?; |
1597 | ||
1a4d82fc JJ |
1598 | // Other bounds. Consider both in-scope bounds from fn decl |
1599 | // and applicable impls. There is a certain set of precedence rules here. | |
476ff2be | 1600 | let def_id = obligation.predicate.def_id(); |
ea8adc8c | 1601 | let lang_items = self.tcx().lang_items(); |
0bf4aa26 | 1602 | |
ea8adc8c | 1603 | if lang_items.copy_trait() == Some(def_id) { |
0bf4aa26 XL |
1604 | debug!( |
1605 | "obligation self ty is {:?}", | |
1606 | obligation.predicate.skip_binder().self_ty() | |
1607 | ); | |
476ff2be SL |
1608 | |
1609 | // User-defined copy impls are permitted, but only for | |
1610 | // structs and enums. | |
1611 | self.assemble_candidates_from_impls(obligation, &mut candidates)?; | |
1612 | ||
1613 | // For other types, we'll use the builtin rules. | |
ea8adc8c | 1614 | let copy_conditions = self.copy_clone_conditions(obligation); |
476ff2be | 1615 | self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates)?; |
ea8adc8c | 1616 | } else if lang_items.sized_trait() == Some(def_id) { |
476ff2be SL |
1617 | // Sized is never implementable by end-users, it is |
1618 | // always automatically computed. | |
1619 | let sized_conditions = self.sized_conditions(obligation); | |
0bf4aa26 | 1620 | self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates)?; |
94b46f34 XL |
1621 | } else if lang_items.unsize_trait() == Some(def_id) { |
1622 | self.assemble_candidates_for_unsizing(obligation, &mut candidates); | |
1623 | } else { | |
1624 | if lang_items.clone_trait() == Some(def_id) { | |
0731742a | 1625 | // Same builtin conditions as `Copy`, i.e., every type which has builtin support |
94b46f34 XL |
1626 | // for `Copy` also has builtin support for `Clone`, + tuples and arrays of `Clone` |
1627 | // types have builtin support for `Clone`. | |
1628 | let clone_conditions = self.copy_clone_conditions(obligation); | |
1629 | self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates)?; | |
1630 | } | |
1631 | ||
1632 | self.assemble_generator_candidates(obligation, &mut candidates)?; | |
1633 | self.assemble_closure_candidates(obligation, &mut candidates)?; | |
1634 | self.assemble_fn_pointer_candidates(obligation, &mut candidates)?; | |
1635 | self.assemble_candidates_from_impls(obligation, &mut candidates)?; | |
1636 | self.assemble_candidates_from_object_ty(obligation, &mut candidates); | |
1a4d82fc JJ |
1637 | } |
1638 | ||
1639 | self.assemble_candidates_from_projected_tys(obligation, &mut candidates); | |
54a0048b | 1640 | self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?; |
abe05a73 | 1641 | // Auto implementations have lower priority, so we only |
c34b1796 | 1642 | // consider triggering a default if there is no other impl that can apply. |
9346a6ac | 1643 | if candidates.vec.is_empty() { |
abe05a73 | 1644 | self.assemble_candidates_from_auto_impls(obligation, &mut candidates)?; |
c34b1796 | 1645 | } |
1a4d82fc JJ |
1646 | debug!("candidate list size: {}", candidates.vec.len()); |
1647 | Ok(candidates) | |
1648 | } | |
1649 | ||
0bf4aa26 XL |
1650 | fn assemble_candidates_from_projected_tys( |
1651 | &mut self, | |
1652 | obligation: &TraitObligation<'tcx>, | |
1653 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1654 | ) { | |
e9174d1e | 1655 | debug!("assemble_candidates_for_projected_tys({:?})", obligation); |
1a4d82fc | 1656 | |
0bf4aa26 | 1657 | // before we go into the whole placeholder thing, just |
1a4d82fc | 1658 | // quickly check if the self-type is a projection at all. |
83c7162d | 1659 | match obligation.predicate.skip_binder().trait_ref.self_ty().sty { |
b7449926 XL |
1660 | ty::Projection(_) | ty::Opaque(..) => {} |
1661 | ty::Infer(ty::TyVar(_)) => { | |
0bf4aa26 XL |
1662 | span_bug!( |
1663 | obligation.cause.span, | |
1664 | "Self=_ should have been handled by assemble_candidates" | |
1665 | ); | |
1a4d82fc | 1666 | } |
0bf4aa26 | 1667 | _ => return, |
5bcae85e | 1668 | } |
1a4d82fc | 1669 | |
0731742a XL |
1670 | let result = self.infcx.probe(|snapshot| { |
1671 | self.match_projection_obligation_against_definition_bounds( | |
1672 | obligation, | |
1673 | snapshot, | |
1674 | ) | |
1a4d82fc JJ |
1675 | }); |
1676 | ||
1677 | if result { | |
1678 | candidates.vec.push(ProjectionCandidate); | |
1679 | } | |
1680 | } | |
1681 | ||
5bcae85e | 1682 | fn match_projection_obligation_against_definition_bounds( |
1a4d82fc JJ |
1683 | &mut self, |
1684 | obligation: &TraitObligation<'tcx>, | |
0731742a | 1685 | snapshot: &CombinedSnapshot<'_, 'tcx>, |
0bf4aa26 XL |
1686 | ) -> bool { |
1687 | let poly_trait_predicate = self.infcx() | |
1688 | .resolve_type_vars_if_possible(&obligation.predicate); | |
0731742a | 1689 | let (placeholder_trait_predicate, placeholder_map) = self.infcx() |
a1dfa0c6 | 1690 | .replace_bound_vars_with_placeholders(&poly_trait_predicate); |
0bf4aa26 XL |
1691 | debug!( |
1692 | "match_projection_obligation_against_definition_bounds: \ | |
0731742a XL |
1693 | placeholder_trait_predicate={:?}", |
1694 | placeholder_trait_predicate, | |
0bf4aa26 | 1695 | ); |
1a4d82fc | 1696 | |
0731742a | 1697 | let (def_id, substs) = match placeholder_trait_predicate.trait_ref.self_ty().sty { |
0bf4aa26 | 1698 | ty::Projection(ref data) => (data.trait_ref(self.tcx()).def_id, data.substs), |
b7449926 | 1699 | ty::Opaque(def_id, substs) => (def_id, substs), |
1a4d82fc | 1700 | _ => { |
54a0048b | 1701 | span_bug!( |
1a4d82fc | 1702 | obligation.cause.span, |
5bcae85e | 1703 | "match_projection_obligation_against_definition_bounds() called \ |
0bf4aa26 | 1704 | but self-ty is not a projection: {:?}", |
0731742a | 1705 | placeholder_trait_predicate.trait_ref.self_ty() |
0bf4aa26 | 1706 | ); |
1a4d82fc JJ |
1707 | } |
1708 | }; | |
0bf4aa26 XL |
1709 | debug!( |
1710 | "match_projection_obligation_against_definition_bounds: \ | |
1711 | def_id={:?}, substs={:?}", | |
1712 | def_id, substs | |
1713 | ); | |
1a4d82fc | 1714 | |
7cac9316 XL |
1715 | let predicates_of = self.tcx().predicates_of(def_id); |
1716 | let bounds = predicates_of.instantiate(self.tcx(), substs); | |
0bf4aa26 XL |
1717 | debug!( |
1718 | "match_projection_obligation_against_definition_bounds: \ | |
1719 | bounds={:?}", | |
1720 | bounds | |
1721 | ); | |
1a4d82fc | 1722 | |
0bf4aa26 | 1723 | let matching_bound = util::elaborate_predicates(self.tcx(), bounds.predicates) |
1a4d82fc | 1724 | .filter_to_traits() |
0bf4aa26 | 1725 | .find(|bound| { |
0731742a XL |
1726 | self.infcx.probe(|_| { |
1727 | self.match_projection( | |
0bf4aa26 XL |
1728 | obligation, |
1729 | bound.clone(), | |
0731742a | 1730 | placeholder_trait_predicate.trait_ref.clone(), |
0bf4aa26 XL |
1731 | &placeholder_map, |
1732 | snapshot, | |
1733 | ) | |
1734 | }) | |
1735 | }); | |
1736 | ||
1737 | debug!( | |
1738 | "match_projection_obligation_against_definition_bounds: \ | |
1739 | matching_bound={:?}", | |
1740 | matching_bound | |
1741 | ); | |
1a4d82fc JJ |
1742 | match matching_bound { |
1743 | None => false, | |
1744 | Some(bound) => { | |
1745 | // Repeat the successful match, if any, this time outside of a probe. | |
0bf4aa26 XL |
1746 | let result = self.match_projection( |
1747 | obligation, | |
1748 | bound, | |
0731742a | 1749 | placeholder_trait_predicate.trait_ref.clone(), |
0bf4aa26 XL |
1750 | &placeholder_map, |
1751 | snapshot, | |
1752 | ); | |
3157f602 | 1753 | |
1a4d82fc JJ |
1754 | assert!(result); |
1755 | true | |
1756 | } | |
1757 | } | |
1758 | } | |
1759 | ||
0bf4aa26 XL |
1760 | fn match_projection( |
1761 | &mut self, | |
1762 | obligation: &TraitObligation<'tcx>, | |
1763 | trait_bound: ty::PolyTraitRef<'tcx>, | |
0731742a XL |
1764 | placeholder_trait_ref: ty::TraitRef<'tcx>, |
1765 | placeholder_map: &PlaceholderMap<'tcx>, | |
1766 | snapshot: &CombinedSnapshot<'_, 'tcx>, | |
0bf4aa26 | 1767 | ) -> bool { |
0731742a | 1768 | debug_assert!(!placeholder_trait_ref.has_escaping_bound_vars()); |
0bf4aa26 | 1769 | self.infcx |
0731742a XL |
1770 | .at(&obligation.cause, obligation.param_env) |
1771 | .sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound) | |
0bf4aa26 | 1772 | .is_ok() |
0731742a XL |
1773 | && |
1774 | self.infcx.leak_check(false, placeholder_map, snapshot).is_ok() | |
1a4d82fc JJ |
1775 | } |
1776 | ||
1777 | /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller | |
1778 | /// supplied to find out whether it is listed among them. | |
1779 | /// | |
1780 | /// Never affects inference environment. | |
0bf4aa26 XL |
1781 | fn assemble_candidates_from_caller_bounds<'o>( |
1782 | &mut self, | |
1783 | stack: &TraitObligationStack<'o, 'tcx>, | |
1784 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1785 | ) -> Result<(), SelectionError<'tcx>> { | |
1786 | debug!( | |
1787 | "assemble_candidates_from_caller_bounds({:?})", | |
1788 | stack.obligation | |
1789 | ); | |
1a4d82fc | 1790 | |
0bf4aa26 XL |
1791 | let all_bounds = stack |
1792 | .obligation | |
1793 | .param_env | |
1794 | .caller_bounds | |
1795 | .iter() | |
1796 | .filter_map(|o| o.to_opt_poly_trait_ref()); | |
1a4d82fc | 1797 | |
cc61c64b XL |
1798 | // micro-optimization: filter out predicates relating to different |
1799 | // traits. | |
1800 | let matching_bounds = | |
1801 | all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id()); | |
1802 | ||
83c7162d XL |
1803 | // keep only those bounds which may apply, and propagate overflow if it occurs |
1804 | let mut param_candidates = vec![]; | |
1805 | for bound in matching_bounds { | |
1806 | let wc = self.evaluate_where_clause(stack, bound.clone())?; | |
1807 | if wc.may_apply() { | |
1808 | param_candidates.push(ParamCandidate(bound)); | |
1809 | } | |
1810 | } | |
1a4d82fc JJ |
1811 | |
1812 | candidates.vec.extend(param_candidates); | |
1813 | ||
1814 | Ok(()) | |
1815 | } | |
1816 | ||
0bf4aa26 XL |
1817 | fn evaluate_where_clause<'o>( |
1818 | &mut self, | |
1819 | stack: &TraitObligationStack<'o, 'tcx>, | |
1820 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>, | |
1821 | ) -> Result<EvaluationResult, OverflowError> { | |
0731742a | 1822 | self.evaluation_probe(|this| { |
a7813a04 | 1823 | match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) { |
85aaf69f | 1824 | Ok(obligations) => { |
9fa01778 | 1825 | this.evaluate_predicates_recursively(stack.list(), obligations.into_iter()) |
85aaf69f | 1826 | } |
0bf4aa26 | 1827 | Err(()) => Ok(EvaluatedToErr), |
85aaf69f SL |
1828 | } |
1829 | }) | |
1830 | } | |
1831 | ||
0bf4aa26 XL |
1832 | fn assemble_generator_candidates( |
1833 | &mut self, | |
1834 | obligation: &TraitObligation<'tcx>, | |
1835 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1836 | ) -> Result<(), SelectionError<'tcx>> { | |
ea8adc8c XL |
1837 | if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) { |
1838 | return Ok(()); | |
1839 | } | |
1840 | ||
a1dfa0c6 | 1841 | // OK to skip binder because the substs on generator types never |
ea8adc8c XL |
1842 | // touch bound regions, they just capture the in-scope |
1843 | // type/region parameters | |
1844 | let self_ty = *obligation.self_ty().skip_binder(); | |
1845 | match self_ty.sty { | |
b7449926 | 1846 | ty::Generator(..) => { |
0bf4aa26 XL |
1847 | debug!( |
1848 | "assemble_generator_candidates: self_ty={:?} obligation={:?}", | |
1849 | self_ty, obligation | |
1850 | ); | |
ea8adc8c XL |
1851 | |
1852 | candidates.vec.push(GeneratorCandidate); | |
ea8adc8c | 1853 | } |
b7449926 | 1854 | ty::Infer(ty::TyVar(_)) => { |
ea8adc8c XL |
1855 | debug!("assemble_generator_candidates: ambiguous self-type"); |
1856 | candidates.ambiguous = true; | |
ea8adc8c | 1857 | } |
0bf4aa26 | 1858 | _ => {} |
ea8adc8c | 1859 | } |
0bf4aa26 XL |
1860 | |
1861 | Ok(()) | |
ea8adc8c XL |
1862 | } |
1863 | ||
9fa01778 | 1864 | /// Checks for the artificial impl that the compiler will create for an obligation like `X : |
85aaf69f | 1865 | /// FnMut<..>` where `X` is a closure type. |
1a4d82fc | 1866 | /// |
85aaf69f | 1867 | /// Note: the type parameters on a closure candidate are modeled as *output* type |
1a4d82fc JJ |
1868 | /// parameters and hence do not affect whether this trait is a match or not. They will be |
1869 | /// unified during the confirmation step. | |
0bf4aa26 XL |
1870 | fn assemble_closure_candidates( |
1871 | &mut self, | |
1872 | obligation: &TraitObligation<'tcx>, | |
1873 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1874 | ) -> Result<(), SelectionError<'tcx>> { | |
1875 | let kind = match self.tcx() | |
1876 | .lang_items() | |
1877 | .fn_trait_kind(obligation.predicate.def_id()) | |
1878 | { | |
1a4d82fc | 1879 | Some(k) => k, |
0bf4aa26 XL |
1880 | None => { |
1881 | return Ok(()); | |
1882 | } | |
1a4d82fc JJ |
1883 | }; |
1884 | ||
a1dfa0c6 | 1885 | // OK to skip binder because the substs on closure types never |
c34b1796 AL |
1886 | // touch bound regions, they just capture the in-scope |
1887 | // type/region parameters | |
ea8adc8c | 1888 | match obligation.self_ty().skip_binder().sty { |
b7449926 | 1889 | ty::Closure(closure_def_id, closure_substs) => { |
0bf4aa26 XL |
1890 | debug!( |
1891 | "assemble_unboxed_candidates: kind={:?} obligation={:?}", | |
1892 | kind, obligation | |
1893 | ); | |
ff7c6d11 | 1894 | match self.infcx.closure_kind(closure_def_id, closure_substs) { |
ea8adc8c | 1895 | Some(closure_kind) => { |
0bf4aa26 XL |
1896 | debug!( |
1897 | "assemble_unboxed_candidates: closure_kind = {:?}", | |
1898 | closure_kind | |
1899 | ); | |
ea8adc8c XL |
1900 | if closure_kind.extends(kind) { |
1901 | candidates.vec.push(ClosureCandidate); | |
1902 | } | |
1903 | } | |
1904 | None => { | |
1905 | debug!("assemble_unboxed_candidates: closure_kind not yet known"); | |
1906 | candidates.vec.push(ClosureCandidate); | |
1907 | } | |
0bf4aa26 | 1908 | } |
ea8adc8c | 1909 | } |
b7449926 | 1910 | ty::Infer(ty::TyVar(_)) => { |
85aaf69f | 1911 | debug!("assemble_unboxed_closure_candidates: ambiguous self-type"); |
1a4d82fc | 1912 | candidates.ambiguous = true; |
1a4d82fc | 1913 | } |
0bf4aa26 | 1914 | _ => {} |
1a4d82fc | 1915 | } |
0bf4aa26 XL |
1916 | |
1917 | Ok(()) | |
1a4d82fc JJ |
1918 | } |
1919 | ||
1920 | /// Implement one of the `Fn()` family for a fn pointer. | |
0bf4aa26 XL |
1921 | fn assemble_fn_pointer_candidates( |
1922 | &mut self, | |
1923 | obligation: &TraitObligation<'tcx>, | |
1924 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1925 | ) -> Result<(), SelectionError<'tcx>> { | |
c34b1796 | 1926 | // We provide impl of all fn traits for fn pointers. |
0bf4aa26 XL |
1927 | if self.tcx() |
1928 | .lang_items() | |
1929 | .fn_trait_kind(obligation.predicate.def_id()) | |
1930 | .is_none() | |
1931 | { | |
1a4d82fc JJ |
1932 | return Ok(()); |
1933 | } | |
1934 | ||
a1dfa0c6 | 1935 | // OK to skip binder because what we are inspecting doesn't involve bound regions |
e9174d1e | 1936 | let self_ty = *obligation.self_ty().skip_binder(); |
1a4d82fc | 1937 | match self_ty.sty { |
b7449926 | 1938 | ty::Infer(ty::TyVar(_)) => { |
85aaf69f | 1939 | debug!("assemble_fn_pointer_candidates: ambiguous self-type"); |
1a4d82fc JJ |
1940 | candidates.ambiguous = true; // could wind up being a fn() type |
1941 | } | |
1a4d82fc | 1942 | // provide an impl, but only for suitable `fn` pointers |
b7449926 | 1943 | ty::FnDef(..) | ty::FnPtr(_) => { |
83c7162d | 1944 | if let ty::FnSig { |
041b39d2 XL |
1945 | unsafety: hir::Unsafety::Normal, |
1946 | abi: Abi::Rust, | |
1947 | variadic: false, | |
1948 | .. | |
0bf4aa26 XL |
1949 | } = self_ty.fn_sig(self.tcx()).skip_binder() |
1950 | { | |
041b39d2 XL |
1951 | candidates.vec.push(FnPointerCandidate); |
1952 | } | |
1a4d82fc | 1953 | } |
0bf4aa26 | 1954 | _ => {} |
1a4d82fc JJ |
1955 | } |
1956 | ||
1957 | Ok(()) | |
1958 | } | |
1959 | ||
1960 | /// Search for impls that might apply to `obligation`. | |
0bf4aa26 XL |
1961 | fn assemble_candidates_from_impls( |
1962 | &mut self, | |
1963 | obligation: &TraitObligation<'tcx>, | |
1964 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1965 | ) -> Result<(), SelectionError<'tcx>> { | |
1966 | debug!( | |
1967 | "assemble_candidates_from_impls(obligation={:?})", | |
1968 | obligation | |
1969 | ); | |
85aaf69f | 1970 | |
041b39d2 XL |
1971 | self.tcx().for_each_relevant_impl( |
1972 | obligation.predicate.def_id(), | |
83c7162d | 1973 | obligation.predicate.skip_binder().trait_ref.self_ty(), |
d9579d0f | 1974 | |impl_def_id| { |
0731742a XL |
1975 | self.infcx.probe(|snapshot| { |
1976 | if let Ok(_substs) = self.match_impl(impl_def_id, obligation, snapshot) | |
0bf4aa26 XL |
1977 | { |
1978 | candidates.vec.push(ImplCandidate(impl_def_id)); | |
1a4d82fc | 1979 | } |
d9579d0f | 1980 | }); |
0bf4aa26 | 1981 | }, |
d9579d0f | 1982 | ); |
c34b1796 AL |
1983 | |
1984 | Ok(()) | |
1985 | } | |
1986 | ||
0bf4aa26 XL |
1987 | fn assemble_candidates_from_auto_impls( |
1988 | &mut self, | |
1989 | obligation: &TraitObligation<'tcx>, | |
1990 | candidates: &mut SelectionCandidateSet<'tcx>, | |
1991 | ) -> Result<(), SelectionError<'tcx>> { | |
c34b1796 | 1992 | // OK to skip binder here because the tests we do below do not involve bound regions |
e9174d1e | 1993 | let self_ty = *obligation.self_ty().skip_binder(); |
abe05a73 | 1994 | debug!("assemble_candidates_from_auto_impls(self_ty={:?})", self_ty); |
c34b1796 AL |
1995 | |
1996 | let def_id = obligation.predicate.def_id(); | |
1997 | ||
abe05a73 | 1998 | if self.tcx().trait_is_auto(def_id) { |
c34b1796 | 1999 | match self_ty.sty { |
b7449926 | 2000 | ty::Dynamic(..) => { |
c34b1796 | 2001 | // For object types, we don't know what the closed |
32a655c1 SL |
2002 | // over types are. This means we conservatively |
2003 | // say nothing; a candidate may be added by | |
2004 | // `assemble_candidates_from_object_ty`. | |
c34b1796 | 2005 | } |
b7449926 | 2006 | ty::Foreign(..) => { |
abe05a73 XL |
2007 | // Since the contents of foreign types is unknown, |
2008 | // we don't add any `..` impl. Default traits could | |
2009 | // still be provided by a manual implementation for | |
2010 | // this trait and type. | |
2011 | } | |
0bf4aa26 | 2012 | ty::Param(..) | ty::Projection(..) => { |
c34b1796 AL |
2013 | // In these cases, we don't know what the actual |
2014 | // type is. Therefore, we cannot break it down | |
2015 | // into its constituent types. So we don't | |
2016 | // consider the `..` impl but instead just add no | |
2017 | // candidates: this means that typeck will only | |
2018 | // succeed if there is another reason to believe | |
2019 | // that this obligation holds. That could be a | |
2020 | // where-clause or, in the case of an object type, | |
2021 | // it could be that the object type lists the | |
0731742a | 2022 | // trait (e.g., `Foo+Send : Send`). See |
c34b1796 AL |
2023 | // `compile-fail/typeck-default-trait-impl-send-param.rs` |
2024 | // for an example of a test case that exercises | |
2025 | // this path. | |
2026 | } | |
b7449926 | 2027 | ty::Infer(ty::TyVar(_)) => { |
abe05a73 | 2028 | // the auto impl might apply, we don't know |
c34b1796 AL |
2029 | candidates.ambiguous = true; |
2030 | } | |
9fa01778 XL |
2031 | ty::Generator(_, _, movability) |
2032 | if self.tcx().lang_items().unpin_trait() == Some(def_id) => | |
2033 | { | |
2034 | match movability { | |
2035 | hir::GeneratorMovability::Static => { | |
2036 | // Immovable generators are never `Unpin`, so | |
2037 | // suppress the normal auto-impl candidate for it. | |
2038 | } | |
2039 | hir::GeneratorMovability::Movable => { | |
2040 | // Movable generators are always `Unpin`, so add an | |
2041 | // unconditional builtin candidate. | |
2042 | candidates.vec.push(BuiltinCandidate { | |
2043 | has_nested: false, | |
2044 | }); | |
2045 | } | |
2046 | } | |
2047 | } | |
2048 | ||
0bf4aa26 | 2049 | _ => candidates.vec.push(AutoImplCandidate(def_id.clone())), |
c34b1796 AL |
2050 | } |
2051 | } | |
2052 | ||
1a4d82fc JJ |
2053 | Ok(()) |
2054 | } | |
2055 | ||
2056 | /// Search for impls that might apply to `obligation`. | |
0bf4aa26 XL |
2057 | fn assemble_candidates_from_object_ty( |
2058 | &mut self, | |
2059 | obligation: &TraitObligation<'tcx>, | |
2060 | candidates: &mut SelectionCandidateSet<'tcx>, | |
2061 | ) { | |
2062 | debug!( | |
2063 | "assemble_candidates_from_object_ty(self_ty={:?})", | |
2064 | obligation.self_ty().skip_binder() | |
2065 | ); | |
1a4d82fc | 2066 | |
0731742a XL |
2067 | self.infcx.probe(|_snapshot| { |
2068 | // The code below doesn't care about regions, and the | |
3157f602 XL |
2069 | // self-ty here doesn't escape this probe, so just erase |
2070 | // any LBR. | |
0731742a | 2071 | let self_ty = self.tcx().erase_late_bound_regions(&obligation.self_ty()); |
c34b1796 | 2072 | let poly_trait_ref = match self_ty.sty { |
b7449926 | 2073 | ty::Dynamic(ref data, ..) => { |
0bf4aa26 XL |
2074 | if data.auto_traits() |
2075 | .any(|did| did == obligation.predicate.def_id()) | |
2076 | { | |
2077 | debug!( | |
2078 | "assemble_candidates_from_object_ty: matched builtin bound, \ | |
2079 | pushing candidate" | |
2080 | ); | |
476ff2be SL |
2081 | candidates.vec.push(BuiltinObjectCandidate); |
2082 | return; | |
c34b1796 | 2083 | } |
1a4d82fc | 2084 | |
0731742a XL |
2085 | if let Some(principal) = data.principal() { |
2086 | principal.with_self_ty(self.tcx(), self_ty) | |
2087 | } else { | |
2088 | // Only auto-trait bounds exist. | |
2089 | return; | |
2090 | } | |
c34b1796 | 2091 | } |
b7449926 | 2092 | ty::Infer(ty::TyVar(_)) => { |
c34b1796 AL |
2093 | debug!("assemble_candidates_from_object_ty: ambiguous"); |
2094 | candidates.ambiguous = true; // could wind up being an object type | |
a7813a04 | 2095 | return; |
c34b1796 | 2096 | } |
0bf4aa26 | 2097 | _ => return, |
c34b1796 | 2098 | }; |
1a4d82fc | 2099 | |
0bf4aa26 XL |
2100 | debug!( |
2101 | "assemble_candidates_from_object_ty: poly_trait_ref={:?}", | |
2102 | poly_trait_ref | |
2103 | ); | |
1a4d82fc | 2104 | |
c1a9b12d SL |
2105 | // Count only those upcast versions that match the trait-ref |
2106 | // we are looking for. Specifically, do not only check for the | |
2107 | // correct trait, but also the correct type parameters. | |
2108 | // For example, we may be trying to upcast `Foo` to `Bar<i32>`, | |
2109 | // but `Foo` is declared as `trait Foo : Bar<u32>`. | |
0731742a | 2110 | let upcast_trait_refs = util::supertraits(self.tcx(), poly_trait_ref) |
c1a9b12d | 2111 | .filter(|upcast_trait_ref| { |
0731742a | 2112 | self.infcx.probe(|_| { |
c1a9b12d | 2113 | let upcast_trait_ref = upcast_trait_ref.clone(); |
0731742a | 2114 | self.match_poly_trait_ref(obligation, upcast_trait_ref) |
0bf4aa26 | 2115 | .is_ok() |
c1a9b12d SL |
2116 | }) |
2117 | }) | |
2118 | .count(); | |
2119 | ||
2120 | if upcast_trait_refs > 1 { | |
0731742a | 2121 | // Can be upcast in many ways; need more type information. |
c34b1796 | 2122 | candidates.ambiguous = true; |
c1a9b12d | 2123 | } else if upcast_trait_refs == 1 { |
c34b1796 AL |
2124 | candidates.vec.push(ObjectCandidate); |
2125 | } | |
a7813a04 | 2126 | }) |
1a4d82fc JJ |
2127 | } |
2128 | ||
d9579d0f | 2129 | /// Search for unsizing that might apply to `obligation`. |
0bf4aa26 XL |
2130 | fn assemble_candidates_for_unsizing( |
2131 | &mut self, | |
2132 | obligation: &TraitObligation<'tcx>, | |
2133 | candidates: &mut SelectionCandidateSet<'tcx>, | |
2134 | ) { | |
d9579d0f AL |
2135 | // We currently never consider higher-ranked obligations e.g. |
2136 | // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not | |
2137 | // because they are a priori invalid, and we could potentially add support | |
2138 | // for them later, it's just that there isn't really a strong need for it. | |
2139 | // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>` | |
2140 | // impl, and those are generally applied to concrete types. | |
2141 | // | |
2142 | // That said, one might try to write a fn with a where clause like | |
2143 | // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>> | |
2144 | // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`. | |
2145 | // Still, you'd be more likely to write that where clause as | |
2146 | // T: Trait | |
2147 | // so it seems ok if we (conservatively) fail to accept that `Unsize` | |
2148 | // obligation above. Should be possible to extend this in the future. | |
a1dfa0c6 | 2149 | let source = match obligation.self_ty().no_bound_vars() { |
d9579d0f AL |
2150 | Some(t) => t, |
2151 | None => { | |
2152 | // Don't add any candidates if there are bound regions. | |
2153 | return; | |
2154 | } | |
2155 | }; | |
0bf4aa26 XL |
2156 | let target = obligation |
2157 | .predicate | |
2158 | .skip_binder() | |
2159 | .trait_ref | |
2160 | .substs | |
2161 | .type_at(1); | |
d9579d0f | 2162 | |
0bf4aa26 XL |
2163 | debug!( |
2164 | "assemble_candidates_for_unsizing(source={:?}, target={:?})", | |
2165 | source, target | |
2166 | ); | |
d9579d0f AL |
2167 | |
2168 | let may_apply = match (&source.sty, &target.sty) { | |
2169 | // Trait+Kx+'a -> Trait+Ky+'b (upcasts). | |
b7449926 | 2170 | (&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => { |
d9579d0f AL |
2171 | // Upcasts permit two things: |
2172 | // | |
0731742a XL |
2173 | // 1. Dropping builtin bounds, e.g., `Foo+Send` to `Foo` |
2174 | // 2. Tightening the region bound, e.g., `Foo+'a` to `Foo+'b` if `'a : 'b` | |
d9579d0f AL |
2175 | // |
2176 | // Note that neither of these changes requires any | |
2177 | // change at runtime. Eventually this will be | |
2178 | // generalized. | |
2179 | // | |
2180 | // We always upcast when we can because of reason | |
2181 | // #2 (region bounds). | |
0731742a | 2182 | data_a.principal_def_id() == data_b.principal_def_id() |
0bf4aa26 XL |
2183 | && data_b.auto_traits() |
2184 | // All of a's auto traits need to be in b's auto traits. | |
2185 | .all(|b| data_a.auto_traits().any(|a| a == b)) | |
d9579d0f AL |
2186 | } |
2187 | ||
2188 | // T -> Trait. | |
b7449926 | 2189 | (_, &ty::Dynamic(..)) => true, |
d9579d0f AL |
2190 | |
2191 | // Ambiguous handling is below T -> Trait, because inference | |
2192 | // variables can still implement Unsize<Trait> and nested | |
2193 | // obligations will have the final say (likely deferred). | |
0bf4aa26 | 2194 | (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => { |
d9579d0f AL |
2195 | debug!("assemble_candidates_for_unsizing: ambiguous"); |
2196 | candidates.ambiguous = true; | |
2197 | false | |
2198 | } | |
2199 | ||
2200 | // [T; n] -> [T]. | |
b7449926 | 2201 | (&ty::Array(..), &ty::Slice(_)) => true, |
d9579d0f AL |
2202 | |
2203 | // Struct<T> -> Struct<U>. | |
b7449926 | 2204 | (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => { |
d9579d0f AL |
2205 | def_id_a == def_id_b |
2206 | } | |
2207 | ||
041b39d2 | 2208 | // (.., T) -> (.., U). |
0bf4aa26 | 2209 | (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => tys_a.len() == tys_b.len(), |
041b39d2 | 2210 | |
0bf4aa26 | 2211 | _ => false, |
d9579d0f AL |
2212 | }; |
2213 | ||
2214 | if may_apply { | |
2215 | candidates.vec.push(BuiltinUnsizeCandidate); | |
2216 | } | |
2217 | } | |
2218 | ||
a1dfa0c6 XL |
2219 | fn assemble_candidates_for_trait_alias( |
2220 | &mut self, | |
2221 | obligation: &TraitObligation<'tcx>, | |
2222 | candidates: &mut SelectionCandidateSet<'tcx>, | |
2223 | ) -> Result<(), SelectionError<'tcx>> { | |
2224 | // OK to skip binder here because the tests we do below do not involve bound regions | |
2225 | let self_ty = *obligation.self_ty().skip_binder(); | |
2226 | debug!("assemble_candidates_for_trait_alias(self_ty={:?})", self_ty); | |
2227 | ||
2228 | let def_id = obligation.predicate.def_id(); | |
2229 | ||
9fa01778 | 2230 | if self.tcx().is_trait_alias(def_id) { |
a1dfa0c6 XL |
2231 | candidates.vec.push(TraitAliasCandidate(def_id.clone())); |
2232 | } | |
2233 | ||
2234 | Ok(()) | |
2235 | } | |
2236 | ||
1a4d82fc JJ |
2237 | /////////////////////////////////////////////////////////////////////////// |
2238 | // WINNOW | |
2239 | // | |
2240 | // Winnowing is the process of attempting to resolve ambiguity by | |
2241 | // probing further. During the winnowing process, we unify all | |
0bf4aa26 XL |
2242 | // type variables and then we also attempt to evaluate recursive |
2243 | // bounds to see if they are satisfied. | |
1a4d82fc | 2244 | |
9fa01778 XL |
2245 | /// Returns `true` if `victim` should be dropped in favor of |
2246 | /// `other`. Generally speaking we will drop duplicate | |
d9579d0f AL |
2247 | /// candidates and prefer where-clause candidates. |
2248 | /// | |
2249 | /// See the comment for "SelectionCandidate" for more details. | |
54a0048b SL |
2250 | fn candidate_should_be_dropped_in_favor_of<'o>( |
2251 | &mut self, | |
2252 | victim: &EvaluatedCandidate<'tcx>, | |
0bf4aa26 XL |
2253 | other: &EvaluatedCandidate<'tcx>, |
2254 | ) -> bool { | |
54a0048b | 2255 | if victim.candidate == other.candidate { |
85aaf69f SL |
2256 | return true; |
2257 | } | |
2258 | ||
0bf4aa26 XL |
2259 | // Check if a bound would previously have been removed when normalizing |
2260 | // the param_env so that it can be given the lowest priority. See | |
2261 | // #50825 for the motivation for this. | |
2262 | let is_global = | |
2263 | |cand: &ty::PolyTraitRef<'_>| cand.is_global() && !cand.has_late_bound_regions(); | |
2264 | ||
54a0048b | 2265 | match other.candidate { |
b7449926 XL |
2266 | // Prefer BuiltinCandidate { has_nested: false } to anything else. |
2267 | // This is a fix for #53123 and prevents winnowing from accidentally extending the | |
2268 | // lifetime of a variable. | |
2269 | BuiltinCandidate { has_nested: false } => true, | |
94b46f34 XL |
2270 | ParamCandidate(ref cand) => match victim.candidate { |
2271 | AutoImplCandidate(..) => { | |
2272 | bug!( | |
2273 | "default implementations shouldn't be recorded \ | |
0bf4aa26 XL |
2274 | when there are other valid candidates" |
2275 | ); | |
94b46f34 | 2276 | } |
b7449926 XL |
2277 | // Prefer BuiltinCandidate { has_nested: false } to anything else. |
2278 | // This is a fix for #53123 and prevents winnowing from accidentally extending the | |
2279 | // lifetime of a variable. | |
2280 | BuiltinCandidate { has_nested: false } => false, | |
0bf4aa26 XL |
2281 | ImplCandidate(..) |
2282 | | ClosureCandidate | |
2283 | | GeneratorCandidate | |
2284 | | FnPointerCandidate | |
2285 | | BuiltinObjectCandidate | |
2286 | | BuiltinUnsizeCandidate | |
a1dfa0c6 XL |
2287 | | BuiltinCandidate { .. } |
2288 | | TraitAliasCandidate(..) => { | |
94b46f34 XL |
2289 | // Global bounds from the where clause should be ignored |
2290 | // here (see issue #50825). Otherwise, we have a where | |
2291 | // clause so don't go around looking for impls. | |
2292 | !is_global(cand) | |
2293 | } | |
0bf4aa26 | 2294 | ObjectCandidate | ProjectionCandidate => { |
94b46f34 XL |
2295 | // Arbitrarily give param candidates priority |
2296 | // over projection and object candidates. | |
2297 | !is_global(cand) | |
0bf4aa26 | 2298 | } |
94b46f34 XL |
2299 | ParamCandidate(..) => false, |
2300 | }, | |
0bf4aa26 | 2301 | ObjectCandidate | ProjectionCandidate => match victim.candidate { |
abe05a73 | 2302 | AutoImplCandidate(..) => { |
54a0048b | 2303 | bug!( |
d9579d0f | 2304 | "default implementations shouldn't be recorded \ |
0bf4aa26 XL |
2305 | when there are other valid candidates" |
2306 | ); | |
d9579d0f | 2307 | } |
b7449926 XL |
2308 | // Prefer BuiltinCandidate { has_nested: false } to anything else. |
2309 | // This is a fix for #53123 and prevents winnowing from accidentally extending the | |
2310 | // lifetime of a variable. | |
2311 | BuiltinCandidate { has_nested: false } => false, | |
0bf4aa26 XL |
2312 | ImplCandidate(..) |
2313 | | ClosureCandidate | |
2314 | | GeneratorCandidate | |
2315 | | FnPointerCandidate | |
2316 | | BuiltinObjectCandidate | |
2317 | | BuiltinUnsizeCandidate | |
a1dfa0c6 XL |
2318 | | BuiltinCandidate { .. } |
2319 | | TraitAliasCandidate(..) => true, | |
0bf4aa26 | 2320 | ObjectCandidate | ProjectionCandidate => { |
d9579d0f AL |
2321 | // Arbitrarily give param candidates priority |
2322 | // over projection and object candidates. | |
2323 | true | |
0bf4aa26 | 2324 | } |
94b46f34 | 2325 | ParamCandidate(ref cand) => is_global(cand), |
54a0048b SL |
2326 | }, |
2327 | ImplCandidate(other_def) => { | |
2328 | // See if we can toss out `victim` based on specialization. | |
2329 | // This requires us to know *for sure* that the `other` impl applies | |
0731742a XL |
2330 | // i.e., EvaluatedToOk: |
2331 | if other.evaluation.must_apply_modulo_regions() { | |
94b46f34 XL |
2332 | match victim.candidate { |
2333 | ImplCandidate(victim_def) => { | |
2334 | let tcx = self.tcx().global_tcx(); | |
0bf4aa26 | 2335 | return tcx.specializes((other_def, victim_def)) |
0731742a XL |
2336 | || tcx.impls_are_allowed_to_overlap( |
2337 | other_def, victim_def).is_some(); | |
94b46f34 XL |
2338 | } |
2339 | ParamCandidate(ref cand) => { | |
2340 | // Prefer the impl to a global where clause candidate. | |
2341 | return is_global(cand); | |
2342 | } | |
0bf4aa26 | 2343 | _ => (), |
54a0048b SL |
2344 | } |
2345 | } | |
2346 | ||
2347 | false | |
0bf4aa26 XL |
2348 | } |
2349 | ClosureCandidate | |
2350 | | GeneratorCandidate | |
2351 | | FnPointerCandidate | |
2352 | | BuiltinObjectCandidate | |
2353 | | BuiltinUnsizeCandidate | |
2354 | | BuiltinCandidate { has_nested: true } => { | |
94b46f34 XL |
2355 | match victim.candidate { |
2356 | ParamCandidate(ref cand) => { | |
2357 | // Prefer these to a global where-clause bound | |
2358 | // (see issue #50825) | |
0731742a | 2359 | is_global(cand) && other.evaluation.must_apply_modulo_regions() |
94b46f34 XL |
2360 | } |
2361 | _ => false, | |
2362 | } | |
2363 | } | |
0bf4aa26 | 2364 | _ => false, |
1a4d82fc JJ |
2365 | } |
2366 | } | |
2367 | ||
2368 | /////////////////////////////////////////////////////////////////////////// | |
2369 | // BUILTIN BOUNDS | |
2370 | // | |
2371 | // These cover the traits that are built-in to the language | |
94b46f34 | 2372 | // itself: `Copy`, `Clone` and `Sized`. |
1a4d82fc | 2373 | |
0bf4aa26 XL |
2374 | fn assemble_builtin_bound_candidates<'o>( |
2375 | &mut self, | |
2376 | conditions: BuiltinImplConditions<'tcx>, | |
2377 | candidates: &mut SelectionCandidateSet<'tcx>, | |
2378 | ) -> Result<(), SelectionError<'tcx>> { | |
a7813a04 XL |
2379 | match conditions { |
2380 | BuiltinImplConditions::Where(nested) => { | |
2381 | debug!("builtin_bound: nested={:?}", nested); | |
2382 | candidates.vec.push(BuiltinCandidate { | |
0bf4aa26 | 2383 | has_nested: nested.skip_binder().len() > 0, |
a7813a04 | 2384 | }); |
1a4d82fc | 2385 | } |
0bf4aa26 | 2386 | BuiltinImplConditions::None => {} |
a7813a04 | 2387 | BuiltinImplConditions::Ambiguous => { |
85aaf69f | 2388 | debug!("assemble_builtin_bound_candidates: ambiguous builtin"); |
0bf4aa26 | 2389 | candidates.ambiguous = true; |
85aaf69f | 2390 | } |
1a4d82fc | 2391 | } |
0bf4aa26 XL |
2392 | |
2393 | Ok(()) | |
1a4d82fc JJ |
2394 | } |
2395 | ||
0bf4aa26 XL |
2396 | fn sized_conditions( |
2397 | &mut self, | |
2398 | obligation: &TraitObligation<'tcx>, | |
2399 | ) -> BuiltinImplConditions<'tcx> { | |
94b46f34 | 2400 | use self::BuiltinImplConditions::{Ambiguous, None, Where}; |
1a4d82fc | 2401 | |
a7813a04 | 2402 | // NOTE: binder moved to (*) |
0bf4aa26 XL |
2403 | let self_ty = self.infcx |
2404 | .shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
a7813a04 XL |
2405 | |
2406 | match self_ty.sty { | |
0bf4aa26 XL |
2407 | ty::Infer(ty::IntVar(_)) |
2408 | | ty::Infer(ty::FloatVar(_)) | |
2409 | | ty::Uint(_) | |
2410 | | ty::Int(_) | |
2411 | | ty::Bool | |
2412 | | ty::Float(_) | |
2413 | | ty::FnDef(..) | |
2414 | | ty::FnPtr(_) | |
2415 | | ty::RawPtr(..) | |
2416 | | ty::Char | |
2417 | | ty::Ref(..) | |
2418 | | ty::Generator(..) | |
2419 | | ty::GeneratorWitness(..) | |
2420 | | ty::Array(..) | |
2421 | | ty::Closure(..) | |
2422 | | ty::Never | |
2423 | | ty::Error => { | |
1a4d82fc | 2424 | // safe for everything |
83c7162d | 2425 | Where(ty::Binder::dummy(Vec::new())) |
1a4d82fc JJ |
2426 | } |
2427 | ||
b7449926 | 2428 | ty::Str | ty::Slice(_) | ty::Dynamic(..) | ty::Foreign(..) => None, |
1a4d82fc | 2429 | |
0bf4aa26 | 2430 | ty::Tuple(tys) => Where(ty::Binder::bind(tys.last().into_iter().cloned().collect())), |
1a4d82fc | 2431 | |
b7449926 | 2432 | ty::Adt(def, substs) => { |
a7813a04 XL |
2433 | let sized_crit = def.sized_constraint(self.tcx()); |
2434 | // (*) binder moved here | |
83c7162d | 2435 | Where(ty::Binder::bind( |
0bf4aa26 XL |
2436 | sized_crit |
2437 | .iter() | |
2438 | .map(|ty| ty.subst(self.tcx(), substs)) | |
2439 | .collect(), | |
cc61c64b | 2440 | )) |
1a4d82fc JJ |
2441 | } |
2442 | ||
b7449926 XL |
2443 | ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => None, |
2444 | ty::Infer(ty::TyVar(_)) => Ambiguous, | |
1a4d82fc | 2445 | |
0bf4aa26 | 2446 | ty::UnnormalizedProjection(..) |
a1dfa0c6 XL |
2447 | | ty::Placeholder(..) |
2448 | | ty::Bound(..) | |
0bf4aa26 XL |
2449 | | ty::Infer(ty::FreshTy(_)) |
2450 | | ty::Infer(ty::FreshIntTy(_)) | |
2451 | | ty::Infer(ty::FreshFloatTy(_)) => { | |
2452 | bug!( | |
2453 | "asked to assemble builtin bounds of unexpected type: {:?}", | |
2454 | self_ty | |
2455 | ); | |
1a4d82fc | 2456 | } |
a7813a04 XL |
2457 | } |
2458 | } | |
1a4d82fc | 2459 | |
0bf4aa26 XL |
2460 | fn copy_clone_conditions( |
2461 | &mut self, | |
2462 | obligation: &TraitObligation<'tcx>, | |
2463 | ) -> BuiltinImplConditions<'tcx> { | |
a7813a04 | 2464 | // NOTE: binder moved to (*) |
0bf4aa26 XL |
2465 | let self_ty = self.infcx |
2466 | .shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
1a4d82fc | 2467 | |
94b46f34 | 2468 | use self::BuiltinImplConditions::{Ambiguous, None, Where}; |
1a4d82fc | 2469 | |
a7813a04 | 2470 | match self_ty.sty { |
0bf4aa26 XL |
2471 | ty::Infer(ty::IntVar(_)) |
2472 | | ty::Infer(ty::FloatVar(_)) | |
2473 | | ty::FnDef(..) | |
2474 | | ty::FnPtr(_) | |
2475 | | ty::Error => Where(ty::Binder::dummy(Vec::new())), | |
2476 | ||
2477 | ty::Uint(_) | |
2478 | | ty::Int(_) | |
2479 | | ty::Bool | |
2480 | | ty::Float(_) | |
2481 | | ty::Char | |
2482 | | ty::RawPtr(..) | |
2483 | | ty::Never | |
2484 | | ty::Ref(_, _, hir::MutImmutable) => { | |
83c7162d XL |
2485 | // Implementations provided in libcore |
2486 | None | |
1a4d82fc JJ |
2487 | } |
2488 | ||
0bf4aa26 XL |
2489 | ty::Dynamic(..) |
2490 | | ty::Str | |
2491 | | ty::Slice(..) | |
2492 | | ty::Generator(..) | |
2493 | | ty::GeneratorWitness(..) | |
2494 | | ty::Foreign(..) | |
2495 | | ty::Ref(_, _, hir::MutMutable) => None, | |
1a4d82fc | 2496 | |
b7449926 | 2497 | ty::Array(element_ty, _) => { |
a7813a04 | 2498 | // (*) binder moved here |
83c7162d | 2499 | Where(ty::Binder::bind(vec![element_ty])) |
1a4d82fc JJ |
2500 | } |
2501 | ||
b7449926 | 2502 | ty::Tuple(tys) => { |
a7813a04 | 2503 | // (*) binder moved here |
83c7162d | 2504 | Where(ty::Binder::bind(tys.to_vec())) |
1a4d82fc JJ |
2505 | } |
2506 | ||
b7449926 | 2507 | ty::Closure(def_id, substs) => { |
ea8adc8c | 2508 | let trait_id = obligation.predicate.def_id(); |
0531ce1d XL |
2509 | let is_copy_trait = Some(trait_id) == self.tcx().lang_items().copy_trait(); |
2510 | let is_clone_trait = Some(trait_id) == self.tcx().lang_items().clone_trait(); | |
2511 | if is_copy_trait || is_clone_trait { | |
0bf4aa26 XL |
2512 | Where(ty::Binder::bind( |
2513 | substs.upvar_tys(def_id, self.tcx()).collect(), | |
2514 | )) | |
ea8adc8c | 2515 | } else { |
94b46f34 | 2516 | None |
ea8adc8c XL |
2517 | } |
2518 | } | |
2519 | ||
b7449926 | 2520 | ty::Adt(..) | ty::Projection(..) | ty::Param(..) | ty::Opaque(..) => { |
a7813a04 XL |
2521 | // Fallback to whatever user-defined impls exist in this case. |
2522 | None | |
1a4d82fc JJ |
2523 | } |
2524 | ||
b7449926 | 2525 | ty::Infer(ty::TyVar(_)) => { |
1a4d82fc JJ |
2526 | // Unbound type variable. Might or might not have |
2527 | // applicable impls and so forth, depending on what | |
2528 | // those type variables wind up being bound to. | |
a7813a04 | 2529 | Ambiguous |
1a4d82fc JJ |
2530 | } |
2531 | ||
0bf4aa26 | 2532 | ty::UnnormalizedProjection(..) |
a1dfa0c6 XL |
2533 | | ty::Placeholder(..) |
2534 | | ty::Bound(..) | |
0bf4aa26 XL |
2535 | | ty::Infer(ty::FreshTy(_)) |
2536 | | ty::Infer(ty::FreshIntTy(_)) | |
2537 | | ty::Infer(ty::FreshFloatTy(_)) => { | |
2538 | bug!( | |
2539 | "asked to assemble builtin bounds of unexpected type: {:?}", | |
2540 | self_ty | |
2541 | ); | |
1a4d82fc | 2542 | } |
c34b1796 AL |
2543 | } |
2544 | } | |
2545 | ||
2546 | /// For default impls, we need to break apart a type into its | |
2547 | /// "constituent types" -- meaning, the types that it contains. | |
2548 | /// | |
2549 | /// Here are some (simple) examples: | |
2550 | /// | |
2551 | /// ``` | |
2552 | /// (i32, u32) -> [i32, u32] | |
2553 | /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32] | |
2554 | /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32] | |
2555 | /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32] | |
2556 | /// ``` | |
c1a9b12d | 2557 | fn constituent_types_for_ty(&self, t: Ty<'tcx>) -> Vec<Ty<'tcx>> { |
c34b1796 | 2558 | match t.sty { |
0bf4aa26 XL |
2559 | ty::Uint(_) |
2560 | | ty::Int(_) | |
2561 | | ty::Bool | |
2562 | | ty::Float(_) | |
2563 | | ty::FnDef(..) | |
2564 | | ty::FnPtr(_) | |
2565 | | ty::Str | |
2566 | | ty::Error | |
2567 | | ty::Infer(ty::IntVar(_)) | |
2568 | | ty::Infer(ty::FloatVar(_)) | |
2569 | | ty::Never | |
2570 | | ty::Char => Vec::new(), | |
2571 | ||
2572 | ty::UnnormalizedProjection(..) | |
a1dfa0c6 | 2573 | | ty::Placeholder(..) |
0bf4aa26 XL |
2574 | | ty::Dynamic(..) |
2575 | | ty::Param(..) | |
2576 | | ty::Foreign(..) | |
2577 | | ty::Projection(..) | |
a1dfa0c6 | 2578 | | ty::Bound(..) |
0bf4aa26 XL |
2579 | | ty::Infer(ty::TyVar(_)) |
2580 | | ty::Infer(ty::FreshTy(_)) | |
2581 | | ty::Infer(ty::FreshIntTy(_)) | |
2582 | | ty::Infer(ty::FreshFloatTy(_)) => { | |
2583 | bug!( | |
2584 | "asked to assemble constituent types of unexpected type: {:?}", | |
2585 | t | |
2586 | ); | |
2587 | } | |
c34b1796 | 2588 | |
0bf4aa26 | 2589 | ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => { |
c1a9b12d | 2590 | vec![element_ty] |
c34b1796 | 2591 | } |
1a4d82fc | 2592 | |
0bf4aa26 XL |
2593 | ty::Array(element_ty, _) | ty::Slice(element_ty) => vec![element_ty], |
2594 | ||
b7449926 | 2595 | ty::Tuple(ref tys) => { |
c34b1796 | 2596 | // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet |
a7813a04 | 2597 | tys.to_vec() |
c1a9b12d SL |
2598 | } |
2599 | ||
0bf4aa26 | 2600 | ty::Closure(def_id, ref substs) => substs.upvar_tys(def_id, self.tcx()).collect(), |
c34b1796 | 2601 | |
b7449926 | 2602 | ty::Generator(def_id, ref substs, _) => { |
94b46f34 | 2603 | let witness = substs.witness(def_id, self.tcx()); |
0bf4aa26 XL |
2604 | substs |
2605 | .upvar_tys(def_id, self.tcx()) | |
2606 | .chain(iter::once(witness)) | |
2607 | .collect() | |
2c00a5a8 XL |
2608 | } |
2609 | ||
b7449926 | 2610 | ty::GeneratorWitness(types) => { |
2c00a5a8 XL |
2611 | // This is sound because no regions in the witness can refer to |
2612 | // the binder outside the witness. So we'll effectivly reuse | |
2613 | // the implicit binder around the witness. | |
2614 | types.skip_binder().to_vec() | |
ea8adc8c XL |
2615 | } |
2616 | ||
c34b1796 | 2617 | // for `PhantomData<T>`, we pass `T` |
0bf4aa26 | 2618 | ty::Adt(def, substs) if def.is_phantom_data() => substs.types().collect(), |
1a4d82fc | 2619 | |
0bf4aa26 | 2620 | ty::Adt(def, substs) => def.all_fields().map(|f| f.ty(self.tcx(), substs)).collect(), |
8bb4bdeb | 2621 | |
b7449926 | 2622 | ty::Opaque(def_id, substs) => { |
8bb4bdeb XL |
2623 | // We can resolve the `impl Trait` to its concrete type, |
2624 | // which enforces a DAG between the functions requiring | |
2625 | // the auto trait bounds in question. | |
7cac9316 | 2626 | vec![self.tcx().type_of(def_id).subst(self.tcx(), substs)] |
8bb4bdeb | 2627 | } |
c34b1796 AL |
2628 | } |
2629 | } | |
2630 | ||
0bf4aa26 XL |
2631 | fn collect_predicates_for_types( |
2632 | &mut self, | |
2633 | param_env: ty::ParamEnv<'tcx>, | |
2634 | cause: ObligationCause<'tcx>, | |
2635 | recursion_depth: usize, | |
2636 | trait_def_id: DefId, | |
2637 | types: ty::Binder<Vec<Ty<'tcx>>>, | |
2638 | ) -> Vec<PredicateObligation<'tcx>> { | |
c34b1796 AL |
2639 | // Because the types were potentially derived from |
2640 | // higher-ranked obligations they may reference late-bound | |
2641 | // regions. For example, `for<'a> Foo<&'a int> : Copy` would | |
2642 | // yield a type like `for<'a> &'a int`. In general, we | |
2643 | // maintain the invariant that we never manipulate bound | |
2644 | // regions, so we have to process these bound regions somehow. | |
2645 | // | |
2646 | // The strategy is to: | |
2647 | // | |
0bf4aa26 | 2648 | // 1. Instantiate those regions to placeholder regions (e.g., |
c34b1796 AL |
2649 | // `for<'a> &'a int` becomes `&0 int`. |
2650 | // 2. Produce something like `&'0 int : Copy` | |
2651 | // 3. Re-bind the regions back to `for<'a> &'a int : Copy` | |
2652 | ||
0bf4aa26 XL |
2653 | types |
2654 | .skip_binder() | |
2655 | .into_iter() | |
2656 | .flat_map(|ty| { | |
2657 | // binder moved -\ | |
2658 | let ty: ty::Binder<Ty<'tcx>> = ty::Binder::bind(ty); // <----/ | |
2659 | ||
0731742a XL |
2660 | self.infcx.in_snapshot(|_| { |
2661 | let (skol_ty, _) = self.infcx | |
a1dfa0c6 | 2662 | .replace_bound_vars_with_placeholders(&ty); |
0bf4aa26 XL |
2663 | let Normalized { |
2664 | value: normalized_ty, | |
2665 | mut obligations, | |
2666 | } = project::normalize_with_depth( | |
0731742a | 2667 | self, |
0bf4aa26 XL |
2668 | param_env, |
2669 | cause.clone(), | |
2670 | recursion_depth, | |
2671 | &skol_ty, | |
2672 | ); | |
0731742a | 2673 | let skol_obligation = self.tcx().predicate_for_trait_def( |
0bf4aa26 XL |
2674 | param_env, |
2675 | cause.clone(), | |
2676 | trait_def_id, | |
2677 | recursion_depth, | |
2678 | normalized_ty, | |
2679 | &[], | |
2680 | ); | |
2681 | obligations.push(skol_obligation); | |
0731742a | 2682 | obligations |
0bf4aa26 | 2683 | }) |
c34b1796 | 2684 | }) |
0bf4aa26 | 2685 | .collect() |
1a4d82fc JJ |
2686 | } |
2687 | ||
2688 | /////////////////////////////////////////////////////////////////////////// | |
2689 | // CONFIRMATION | |
2690 | // | |
2691 | // Confirmation unifies the output type parameters of the trait | |
2692 | // with the values found in the obligation, possibly yielding a | |
0731742a | 2693 | // type error. See the [rustc guide] for more details. |
0531ce1d XL |
2694 | // |
2695 | // [rustc guide]: | |
a1dfa0c6 | 2696 | // https://rust-lang.github.io/rustc-guide/traits/resolution.html#confirmation |
1a4d82fc | 2697 | |
0bf4aa26 XL |
2698 | fn confirm_candidate( |
2699 | &mut self, | |
2700 | obligation: &TraitObligation<'tcx>, | |
2701 | candidate: SelectionCandidate<'tcx>, | |
2702 | ) -> Result<Selection<'tcx>, SelectionError<'tcx>> { | |
2703 | debug!("confirm_candidate({:?}, {:?})", obligation, candidate); | |
1a4d82fc JJ |
2704 | |
2705 | match candidate { | |
a7813a04 | 2706 | BuiltinCandidate { has_nested } => { |
3b2f2976 XL |
2707 | let data = self.confirm_builtin_candidate(obligation, has_nested); |
2708 | Ok(VtableBuiltin(data)) | |
1a4d82fc JJ |
2709 | } |
2710 | ||
1a4d82fc | 2711 | ParamCandidate(param) => { |
85aaf69f SL |
2712 | let obligations = self.confirm_param_candidate(obligation, param); |
2713 | Ok(VtableParam(obligations)) | |
1a4d82fc JJ |
2714 | } |
2715 | ||
a1dfa0c6 XL |
2716 | ImplCandidate(impl_def_id) => Ok(VtableImpl(self.confirm_impl_candidate( |
2717 | obligation, | |
2718 | impl_def_id, | |
2719 | ))), | |
2720 | ||
abe05a73 XL |
2721 | AutoImplCandidate(trait_def_id) => { |
2722 | let data = self.confirm_auto_impl_candidate(obligation, trait_def_id); | |
2723 | Ok(VtableAutoImpl(data)) | |
c34b1796 AL |
2724 | } |
2725 | ||
a1dfa0c6 XL |
2726 | ProjectionCandidate => { |
2727 | self.confirm_projection_candidate(obligation); | |
2728 | Ok(VtableParam(Vec::new())) | |
2729 | } | |
1a4d82fc | 2730 | |
ea8adc8c XL |
2731 | ClosureCandidate => { |
2732 | let vtable_closure = self.confirm_closure_candidate(obligation)?; | |
62682a34 | 2733 | Ok(VtableClosure(vtable_closure)) |
1a4d82fc JJ |
2734 | } |
2735 | ||
ea8adc8c XL |
2736 | GeneratorCandidate => { |
2737 | let vtable_generator = self.confirm_generator_candidate(obligation)?; | |
2738 | Ok(VtableGenerator(vtable_generator)) | |
2739 | } | |
2740 | ||
a1dfa0c6 XL |
2741 | FnPointerCandidate => { |
2742 | let data = self.confirm_fn_pointer_candidate(obligation)?; | |
2743 | Ok(VtableFnPointer(data)) | |
2744 | } | |
2745 | ||
2746 | TraitAliasCandidate(alias_def_id) => { | |
2747 | let data = self.confirm_trait_alias_candidate(obligation, alias_def_id); | |
2748 | Ok(VtableTraitAlias(data)) | |
c34b1796 AL |
2749 | } |
2750 | ||
1a4d82fc JJ |
2751 | ObjectCandidate => { |
2752 | let data = self.confirm_object_candidate(obligation); | |
2753 | Ok(VtableObject(data)) | |
2754 | } | |
2755 | ||
a1dfa0c6 XL |
2756 | BuiltinObjectCandidate => { |
2757 | // This indicates something like `(Trait+Send) : | |
2758 | // Send`. In this case, we know that this holds | |
2759 | // because that's what the object type is telling us, | |
2760 | // and there's really no additional obligations to | |
2761 | // prove and no types in particular to unify etc. | |
85aaf69f | 2762 | Ok(VtableParam(Vec::new())) |
1a4d82fc | 2763 | } |
d9579d0f AL |
2764 | |
2765 | BuiltinUnsizeCandidate => { | |
54a0048b | 2766 | let data = self.confirm_builtin_unsize_candidate(obligation)?; |
d9579d0f AL |
2767 | Ok(VtableBuiltin(data)) |
2768 | } | |
1a4d82fc JJ |
2769 | } |
2770 | } | |
2771 | ||
0bf4aa26 | 2772 | fn confirm_projection_candidate(&mut self, obligation: &TraitObligation<'tcx>) { |
0731742a | 2773 | self.infcx.in_snapshot(|snapshot| { |
a7813a04 | 2774 | let result = |
0731742a XL |
2775 | self.match_projection_obligation_against_definition_bounds( |
2776 | obligation, | |
2777 | snapshot, | |
2778 | ); | |
a7813a04 XL |
2779 | assert!(result); |
2780 | }) | |
1a4d82fc JJ |
2781 | } |
2782 | ||
0bf4aa26 XL |
2783 | fn confirm_param_candidate( |
2784 | &mut self, | |
2785 | obligation: &TraitObligation<'tcx>, | |
2786 | param: ty::PolyTraitRef<'tcx>, | |
2787 | ) -> Vec<PredicateObligation<'tcx>> { | |
2788 | debug!("confirm_param_candidate({:?},{:?})", obligation, param); | |
1a4d82fc JJ |
2789 | |
2790 | // During evaluation, we already checked that this | |
2791 | // where-clause trait-ref could be unified with the obligation | |
2792 | // trait-ref. Repeat that unification now without any | |
2793 | // transactional boundary; it should not fail. | |
85aaf69f SL |
2794 | match self.match_where_clause_trait_ref(obligation, param.clone()) { |
2795 | Ok(obligations) => obligations, | |
2796 | Err(()) => { | |
0bf4aa26 XL |
2797 | bug!( |
2798 | "Where clause `{:?}` was applicable to `{:?}` but now is not", | |
2799 | param, | |
2800 | obligation | |
2801 | ); | |
1a4d82fc JJ |
2802 | } |
2803 | } | |
2804 | } | |
2805 | ||
0bf4aa26 XL |
2806 | fn confirm_builtin_candidate( |
2807 | &mut self, | |
2808 | obligation: &TraitObligation<'tcx>, | |
2809 | has_nested: bool, | |
2810 | ) -> VtableBuiltinData<PredicateObligation<'tcx>> { | |
2811 | debug!( | |
2812 | "confirm_builtin_candidate({:?}, {:?})", | |
2813 | obligation, has_nested | |
2814 | ); | |
a7813a04 | 2815 | |
ea8adc8c | 2816 | let lang_items = self.tcx().lang_items(); |
a7813a04 XL |
2817 | let obligations = if has_nested { |
2818 | let trait_def = obligation.predicate.def_id(); | |
0bf4aa26 XL |
2819 | let conditions = if Some(trait_def) == lang_items.sized_trait() { |
2820 | self.sized_conditions(obligation) | |
2821 | } else if Some(trait_def) == lang_items.copy_trait() { | |
2822 | self.copy_clone_conditions(obligation) | |
2823 | } else if Some(trait_def) == lang_items.clone_trait() { | |
2824 | self.copy_clone_conditions(obligation) | |
2825 | } else { | |
2826 | bug!("unexpected builtin trait {:?}", trait_def) | |
a7813a04 XL |
2827 | }; |
2828 | let nested = match conditions { | |
2829 | BuiltinImplConditions::Where(nested) => nested, | |
0bf4aa26 XL |
2830 | _ => bug!( |
2831 | "obligation {:?} had matched a builtin impl but now doesn't", | |
2832 | obligation | |
2833 | ), | |
a7813a04 | 2834 | }; |
7453a54e | 2835 | |
5bcae85e | 2836 | let cause = obligation.derived_cause(BuiltinDerivedObligation); |
0bf4aa26 XL |
2837 | self.collect_predicates_for_types( |
2838 | obligation.param_env, | |
2839 | cause, | |
2840 | obligation.recursion_depth + 1, | |
2841 | trait_def, | |
2842 | nested, | |
2843 | ) | |
a7813a04 XL |
2844 | } else { |
2845 | vec![] | |
1a4d82fc JJ |
2846 | }; |
2847 | ||
0bf4aa26 | 2848 | debug!("confirm_builtin_candidate: obligations={:?}", obligations); |
3b2f2976 | 2849 | |
0bf4aa26 XL |
2850 | VtableBuiltinData { |
2851 | nested: obligations, | |
2852 | } | |
1a4d82fc JJ |
2853 | } |
2854 | ||
2c00a5a8 | 2855 | /// This handles the case where a `auto trait Foo` impl is being used. |
c34b1796 AL |
2856 | /// The idea is that the impl applies to `X : Foo` if the following conditions are met: |
2857 | /// | |
2858 | /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds | |
2859 | /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds. | |
0bf4aa26 XL |
2860 | fn confirm_auto_impl_candidate( |
2861 | &mut self, | |
2862 | obligation: &TraitObligation<'tcx>, | |
2863 | trait_def_id: DefId, | |
2864 | ) -> VtableAutoImplData<PredicateObligation<'tcx>> { | |
2865 | debug!( | |
2866 | "confirm_auto_impl_candidate({:?}, {:?})", | |
2867 | obligation, trait_def_id | |
2868 | ); | |
c34b1796 | 2869 | |
83c7162d XL |
2870 | let types = obligation.predicate.map_bound(|inner| { |
2871 | let self_ty = self.infcx.shallow_resolve(inner.self_ty()); | |
2872 | self.constituent_types_for_ty(self_ty) | |
2873 | }); | |
2874 | self.vtable_auto_impl(obligation, trait_def_id, types) | |
c34b1796 AL |
2875 | } |
2876 | ||
a1dfa0c6 | 2877 | /// See `confirm_auto_impl_candidate`. |
0bf4aa26 XL |
2878 | fn vtable_auto_impl( |
2879 | &mut self, | |
2880 | obligation: &TraitObligation<'tcx>, | |
2881 | trait_def_id: DefId, | |
2882 | nested: ty::Binder<Vec<Ty<'tcx>>>, | |
2883 | ) -> VtableAutoImplData<PredicateObligation<'tcx>> { | |
abe05a73 | 2884 | debug!("vtable_auto_impl: nested={:?}", nested); |
c34b1796 | 2885 | |
5bcae85e | 2886 | let cause = obligation.derived_cause(BuiltinDerivedObligation); |
a7813a04 | 2887 | let mut obligations = self.collect_predicates_for_types( |
7cac9316 | 2888 | obligation.param_env, |
a7813a04 | 2889 | cause, |
0bf4aa26 | 2890 | obligation.recursion_depth + 1, |
a7813a04 | 2891 | trait_def_id, |
0bf4aa26 XL |
2892 | nested, |
2893 | ); | |
c34b1796 | 2894 | |
0731742a | 2895 | let trait_obligations: Vec<PredicateObligation<'_>> = self.infcx.in_snapshot(|_| { |
c34b1796 | 2896 | let poly_trait_ref = obligation.predicate.to_poly_trait_ref(); |
0731742a | 2897 | let (trait_ref, _) = self.infcx |
a1dfa0c6 | 2898 | .replace_bound_vars_with_placeholders(&poly_trait_ref); |
5bcae85e | 2899 | let cause = obligation.derived_cause(ImplDerivedObligation); |
0731742a | 2900 | self.impl_or_trait_obligations( |
0bf4aa26 XL |
2901 | cause, |
2902 | obligation.recursion_depth + 1, | |
2903 | obligation.param_env, | |
2904 | trait_def_id, | |
2905 | &trait_ref.substs, | |
0bf4aa26 | 2906 | ) |
c34b1796 AL |
2907 | }); |
2908 | ||
0bf4aa26 XL |
2909 | // Adds the predicates from the trait. Note that this contains a `Self: Trait` |
2910 | // predicate as usual. It won't have any effect since auto traits are coinductive. | |
a7813a04 | 2911 | obligations.extend(trait_obligations); |
c34b1796 | 2912 | |
abe05a73 | 2913 | debug!("vtable_auto_impl: obligations={:?}", obligations); |
c34b1796 | 2914 | |
abe05a73 | 2915 | VtableAutoImplData { |
041b39d2 | 2916 | trait_def_id, |
0bf4aa26 | 2917 | nested: obligations, |
c34b1796 AL |
2918 | } |
2919 | } | |
2920 | ||
0bf4aa26 XL |
2921 | fn confirm_impl_candidate( |
2922 | &mut self, | |
2923 | obligation: &TraitObligation<'tcx>, | |
2924 | impl_def_id: DefId, | |
2925 | ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> { | |
2926 | debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id); | |
1a4d82fc JJ |
2927 | |
2928 | // First, create the substitutions by matching the impl again, | |
2929 | // this time not in a probe. | |
0731742a XL |
2930 | self.infcx.in_snapshot(|snapshot| { |
2931 | let substs = self.rematch_impl(impl_def_id, obligation, snapshot); | |
a1dfa0c6 | 2932 | debug!("confirm_impl_candidate: substs={:?}", substs); |
5bcae85e | 2933 | let cause = obligation.derived_cause(ImplDerivedObligation); |
0731742a | 2934 | self.vtable_impl( |
0bf4aa26 XL |
2935 | impl_def_id, |
2936 | substs, | |
2937 | cause, | |
2938 | obligation.recursion_depth + 1, | |
2939 | obligation.param_env, | |
0bf4aa26 | 2940 | ) |
1a4d82fc JJ |
2941 | }) |
2942 | } | |
2943 | ||
0bf4aa26 XL |
2944 | fn vtable_impl( |
2945 | &mut self, | |
2946 | impl_def_id: DefId, | |
2947 | mut substs: Normalized<'tcx, &'tcx Substs<'tcx>>, | |
2948 | cause: ObligationCause<'tcx>, | |
2949 | recursion_depth: usize, | |
2950 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 XL |
2951 | ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> { |
2952 | debug!( | |
0731742a XL |
2953 | "vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})", |
2954 | impl_def_id, substs, recursion_depth, | |
0bf4aa26 XL |
2955 | ); |
2956 | ||
2957 | let mut impl_obligations = self.impl_or_trait_obligations( | |
2958 | cause, | |
2959 | recursion_depth, | |
2960 | param_env, | |
2961 | impl_def_id, | |
2962 | &substs.value, | |
0bf4aa26 XL |
2963 | ); |
2964 | ||
2965 | debug!( | |
2966 | "vtable_impl: impl_def_id={:?} impl_obligations={:?}", | |
2967 | impl_def_id, impl_obligations | |
2968 | ); | |
1a4d82fc | 2969 | |
92a42be0 SL |
2970 | // Because of RFC447, the impl-trait-ref and obligations |
2971 | // are sufficient to determine the impl substs, without | |
2972 | // relying on projections in the impl-trait-ref. | |
2973 | // | |
0731742a | 2974 | // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V` |
62682a34 | 2975 | impl_obligations.append(&mut substs.obligations); |
1a4d82fc | 2976 | |
0bf4aa26 XL |
2977 | VtableImplData { |
2978 | impl_def_id, | |
2979 | substs: substs.value, | |
2980 | nested: impl_obligations, | |
2981 | } | |
1a4d82fc JJ |
2982 | } |
2983 | ||
0bf4aa26 XL |
2984 | fn confirm_object_candidate( |
2985 | &mut self, | |
2986 | obligation: &TraitObligation<'tcx>, | |
2987 | ) -> VtableObjectData<'tcx, PredicateObligation<'tcx>> { | |
2988 | debug!("confirm_object_candidate({:?})", obligation); | |
1a4d82fc | 2989 | |
a1dfa0c6 XL |
2990 | // FIXME(nmatsakis) skipping binder here seems wrong -- we should |
2991 | // probably flatten the binder from the obligation and the binder | |
2992 | // from the object. Have to try to make a broken test case that | |
2993 | // results. | |
0bf4aa26 XL |
2994 | let self_ty = self.infcx |
2995 | .shallow_resolve(*obligation.self_ty().skip_binder()); | |
1a4d82fc | 2996 | let poly_trait_ref = match self_ty.sty { |
0731742a XL |
2997 | ty::Dynamic(ref data, ..) => |
2998 | data.principal().unwrap_or_else(|| { | |
2999 | span_bug!(obligation.cause.span, "object candidate with no principal") | |
3000 | }).with_self_ty(self.tcx(), self_ty), | |
0bf4aa26 | 3001 | _ => span_bug!(obligation.cause.span, "object candidate with non-object"), |
1a4d82fc JJ |
3002 | }; |
3003 | ||
c1a9b12d | 3004 | let mut upcast_trait_ref = None; |
0531ce1d | 3005 | let mut nested = vec![]; |
c1a9b12d SL |
3006 | let vtable_base; |
3007 | ||
3008 | { | |
a7813a04 XL |
3009 | let tcx = self.tcx(); |
3010 | ||
c1a9b12d SL |
3011 | // We want to find the first supertrait in the list of |
3012 | // supertraits that we can unify with, and do that | |
3013 | // unification. We know that there is exactly one in the list | |
3014 | // where we can unify because otherwise select would have | |
3015 | // reported an ambiguity. (When we do find a match, also | |
3016 | // record it for later.) | |
0bf4aa26 | 3017 | let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while( |
0731742a | 3018 | |&t| match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) { |
0bf4aa26 XL |
3019 | Ok(obligations) => { |
3020 | upcast_trait_ref = Some(t); | |
3021 | nested.extend(obligations); | |
3022 | false | |
c1a9b12d | 3023 | } |
0bf4aa26 XL |
3024 | Err(_) => true, |
3025 | }, | |
3026 | ); | |
c1a9b12d SL |
3027 | |
3028 | // Additionally, for each of the nonmatching predicates that | |
3029 | // we pass over, we sum up the set of number of vtable | |
3030 | // entries, so that we can compute the offset for the selected | |
3031 | // trait. | |
0bf4aa26 | 3032 | vtable_base = nonmatching.map(|t| tcx.count_own_vtable_entries(t)).sum(); |
1a4d82fc JJ |
3033 | } |
3034 | ||
c1a9b12d SL |
3035 | VtableObjectData { |
3036 | upcast_trait_ref: upcast_trait_ref.unwrap(), | |
041b39d2 | 3037 | vtable_base, |
0531ce1d | 3038 | nested, |
c1a9b12d | 3039 | } |
1a4d82fc JJ |
3040 | } |
3041 | ||
0bf4aa26 XL |
3042 | fn confirm_fn_pointer_candidate( |
3043 | &mut self, | |
3044 | obligation: &TraitObligation<'tcx>, | |
3045 | ) -> Result<VtableFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
3046 | debug!("confirm_fn_pointer_candidate({:?})", obligation); | |
1a4d82fc | 3047 | |
a1dfa0c6 | 3048 | // OK to skip binder; it is reintroduced below |
0bf4aa26 XL |
3049 | let self_ty = self.infcx |
3050 | .shallow_resolve(*obligation.self_ty().skip_binder()); | |
041b39d2 | 3051 | let sig = self_ty.fn_sig(self.tcx()); |
0bf4aa26 XL |
3052 | let trait_ref = self.tcx() |
3053 | .closure_trait_ref_and_return_type( | |
3054 | obligation.predicate.def_id(), | |
3055 | self_ty, | |
3056 | sig, | |
3057 | util::TupleArgumentsFlag::Yes, | |
3058 | ) | |
c34b1796 | 3059 | .map_bound(|(trait_ref, _)| trait_ref); |
1a4d82fc | 3060 | |
0bf4aa26 XL |
3061 | let Normalized { |
3062 | value: trait_ref, | |
3063 | obligations, | |
3064 | } = project::normalize_with_depth( | |
3065 | self, | |
3066 | obligation.param_env, | |
3067 | obligation.cause.clone(), | |
3068 | obligation.recursion_depth + 1, | |
3069 | &trait_ref, | |
3070 | ); | |
041b39d2 | 3071 | |
0bf4aa26 XL |
3072 | self.confirm_poly_trait_refs( |
3073 | obligation.cause.clone(), | |
3074 | obligation.param_env, | |
3075 | obligation.predicate.to_poly_trait_ref(), | |
3076 | trait_ref, | |
3077 | )?; | |
3078 | Ok(VtableFnPointerData { | |
3079 | fn_ty: self_ty, | |
3080 | nested: obligations, | |
3081 | }) | |
1a4d82fc JJ |
3082 | } |
3083 | ||
a1dfa0c6 XL |
3084 | fn confirm_trait_alias_candidate( |
3085 | &mut self, | |
3086 | obligation: &TraitObligation<'tcx>, | |
3087 | alias_def_id: DefId, | |
3088 | ) -> VtableTraitAliasData<'tcx, PredicateObligation<'tcx>> { | |
3089 | debug!( | |
3090 | "confirm_trait_alias_candidate({:?}, {:?})", | |
3091 | obligation, alias_def_id | |
3092 | ); | |
3093 | ||
0731742a XL |
3094 | self.infcx.in_snapshot(|_| { |
3095 | let (predicate, _) = self.infcx() | |
a1dfa0c6 XL |
3096 | .replace_bound_vars_with_placeholders(&obligation.predicate); |
3097 | let trait_ref = predicate.trait_ref; | |
3098 | let trait_def_id = trait_ref.def_id; | |
3099 | let substs = trait_ref.substs; | |
3100 | ||
0731742a | 3101 | let trait_obligations = self.impl_or_trait_obligations( |
a1dfa0c6 XL |
3102 | obligation.cause.clone(), |
3103 | obligation.recursion_depth, | |
3104 | obligation.param_env, | |
3105 | trait_def_id, | |
3106 | &substs, | |
a1dfa0c6 XL |
3107 | ); |
3108 | ||
3109 | debug!( | |
3110 | "confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}", | |
3111 | trait_def_id, trait_obligations | |
3112 | ); | |
3113 | ||
3114 | VtableTraitAliasData { | |
3115 | alias_def_id, | |
3116 | substs: substs, | |
3117 | nested: trait_obligations, | |
3118 | } | |
3119 | }) | |
3120 | } | |
3121 | ||
0bf4aa26 XL |
3122 | fn confirm_generator_candidate( |
3123 | &mut self, | |
3124 | obligation: &TraitObligation<'tcx>, | |
3125 | ) -> Result<VtableGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
a1dfa0c6 | 3126 | // OK to skip binder because the substs on generator types never |
ea8adc8c XL |
3127 | // touch bound regions, they just capture the in-scope |
3128 | // type/region parameters | |
0bf4aa26 XL |
3129 | let self_ty = self.infcx |
3130 | .shallow_resolve(obligation.self_ty().skip_binder()); | |
94b46f34 | 3131 | let (generator_def_id, substs) = match self_ty.sty { |
b7449926 | 3132 | ty::Generator(id, substs, _) => (id, substs), |
0bf4aa26 | 3133 | _ => bug!("closure candidate for non-closure {:?}", obligation), |
ea8adc8c XL |
3134 | }; |
3135 | ||
0bf4aa26 XL |
3136 | debug!( |
3137 | "confirm_generator_candidate({:?},{:?},{:?})", | |
3138 | obligation, generator_def_id, substs | |
3139 | ); | |
1a4d82fc | 3140 | |
0bf4aa26 | 3141 | let trait_ref = self.generator_trait_ref_unnormalized(obligation, generator_def_id, substs); |
ea8adc8c XL |
3142 | let Normalized { |
3143 | value: trait_ref, | |
0bf4aa26 XL |
3144 | mut obligations, |
3145 | } = normalize_with_depth( | |
3146 | self, | |
3147 | obligation.param_env, | |
3148 | obligation.cause.clone(), | |
3149 | obligation.recursion_depth + 1, | |
3150 | &trait_ref, | |
3151 | ); | |
3152 | ||
3153 | debug!( | |
3154 | "confirm_generator_candidate(generator_def_id={:?}, \ | |
3155 | trait_ref={:?}, obligations={:?})", | |
3156 | generator_def_id, trait_ref, obligations | |
3157 | ); | |
3158 | ||
3159 | obligations.extend(self.confirm_poly_trait_refs( | |
3160 | obligation.cause.clone(), | |
3161 | obligation.param_env, | |
3162 | obligation.predicate.to_poly_trait_ref(), | |
3163 | trait_ref, | |
3164 | )?); | |
ea8adc8c XL |
3165 | |
3166 | Ok(VtableGeneratorData { | |
94b46f34 | 3167 | generator_def_id: generator_def_id, |
ea8adc8c | 3168 | substs: substs.clone(), |
0bf4aa26 | 3169 | nested: obligations, |
ea8adc8c XL |
3170 | }) |
3171 | } | |
3172 | ||
0bf4aa26 XL |
3173 | fn confirm_closure_candidate( |
3174 | &mut self, | |
3175 | obligation: &TraitObligation<'tcx>, | |
3176 | ) -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
ea8adc8c XL |
3177 | debug!("confirm_closure_candidate({:?})", obligation); |
3178 | ||
0bf4aa26 XL |
3179 | let kind = self.tcx() |
3180 | .lang_items() | |
3181 | .fn_trait_kind(obligation.predicate.def_id()) | |
3182 | .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation)); | |
ea8adc8c | 3183 | |
a1dfa0c6 | 3184 | // OK to skip binder because the substs on closure types never |
ea8adc8c XL |
3185 | // touch bound regions, they just capture the in-scope |
3186 | // type/region parameters | |
0bf4aa26 XL |
3187 | let self_ty = self.infcx |
3188 | .shallow_resolve(obligation.self_ty().skip_binder()); | |
ea8adc8c | 3189 | let (closure_def_id, substs) = match self_ty.sty { |
b7449926 | 3190 | ty::Closure(id, substs) => (id, substs), |
0bf4aa26 | 3191 | _ => bug!("closure candidate for non-closure {:?}", obligation), |
ea8adc8c XL |
3192 | }; |
3193 | ||
0bf4aa26 | 3194 | let trait_ref = self.closure_trait_ref_unnormalized(obligation, closure_def_id, substs); |
62682a34 SL |
3195 | let Normalized { |
3196 | value: trait_ref, | |
0bf4aa26 XL |
3197 | mut obligations, |
3198 | } = normalize_with_depth( | |
3199 | self, | |
3200 | obligation.param_env, | |
3201 | obligation.cause.clone(), | |
3202 | obligation.recursion_depth + 1, | |
3203 | &trait_ref, | |
3204 | ); | |
3205 | ||
3206 | debug!( | |
3207 | "confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})", | |
3208 | closure_def_id, trait_ref, obligations | |
3209 | ); | |
3210 | ||
3211 | obligations.extend(self.confirm_poly_trait_refs( | |
3212 | obligation.cause.clone(), | |
3213 | obligation.param_env, | |
3214 | obligation.predicate.to_poly_trait_ref(), | |
3215 | trait_ref, | |
3216 | )?); | |
62682a34 | 3217 | |
0731742a XL |
3218 | // FIXME: chalk |
3219 | if !self.tcx().sess.opts.debugging_opts.chalk { | |
3220 | obligations.push(Obligation::new( | |
3221 | obligation.cause.clone(), | |
3222 | obligation.param_env, | |
3223 | ty::Predicate::ClosureKind(closure_def_id, substs, kind), | |
3224 | )); | |
3225 | } | |
a7813a04 | 3226 | |
62682a34 | 3227 | Ok(VtableClosureData { |
041b39d2 | 3228 | closure_def_id, |
62682a34 | 3229 | substs: substs.clone(), |
0bf4aa26 | 3230 | nested: obligations, |
62682a34 | 3231 | }) |
1a4d82fc JJ |
3232 | } |
3233 | ||
85aaf69f | 3234 | /// In the case of closure types and fn pointers, |
1a4d82fc JJ |
3235 | /// we currently treat the input type parameters on the trait as |
3236 | /// outputs. This means that when we have a match we have only | |
3237 | /// considered the self type, so we have to go back and make sure | |
9fa01778 | 3238 | /// to relate the argument types too. This is kind of wrong, but |
1a4d82fc JJ |
3239 | /// since we control the full set of impls, also not that wrong, |
3240 | /// and it DOES yield better error messages (since we don't report | |
3241 | /// errors as if there is no applicable impl, but rather report | |
3242 | /// errors are about mismatched argument types. | |
3243 | /// | |
b039eaaf | 3244 | /// Here is an example. Imagine we have a closure expression |
1a4d82fc JJ |
3245 | /// and we desugared it so that the type of the expression is |
3246 | /// `Closure`, and `Closure` expects an int as argument. Then it | |
3247 | /// is "as if" the compiler generated this impl: | |
3248 | /// | |
3249 | /// impl Fn(int) for Closure { ... } | |
3250 | /// | |
c34b1796 | 3251 | /// Now imagine our obligation is `Fn(usize) for Closure`. So far |
9fa01778 | 3252 | /// we have matched the self type `Closure`. At this point we'll |
c34b1796 | 3253 | /// compare the `int` to `usize` and generate an error. |
1a4d82fc JJ |
3254 | /// |
3255 | /// Note that this checking occurs *after* the impl has selected, | |
3256 | /// because these output type parameters should not affect the | |
3257 | /// selection of the impl. Therefore, if there is a mismatch, we | |
3258 | /// report an error to the user. | |
0bf4aa26 XL |
3259 | fn confirm_poly_trait_refs( |
3260 | &mut self, | |
3261 | obligation_cause: ObligationCause<'tcx>, | |
3262 | obligation_param_env: ty::ParamEnv<'tcx>, | |
3263 | obligation_trait_ref: ty::PolyTraitRef<'tcx>, | |
3264 | expected_trait_ref: ty::PolyTraitRef<'tcx>, | |
3265 | ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
1a4d82fc | 3266 | let obligation_trait_ref = obligation_trait_ref.clone(); |
7cac9316 XL |
3267 | self.infcx |
3268 | .at(&obligation_cause, obligation_param_env) | |
3269 | .sup(obligation_trait_ref, expected_trait_ref) | |
0531ce1d | 3270 | .map(|InferOk { obligations, .. }| obligations) |
54a0048b | 3271 | .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e)) |
1a4d82fc JJ |
3272 | } |
3273 | ||
0bf4aa26 XL |
3274 | fn confirm_builtin_unsize_candidate( |
3275 | &mut self, | |
3276 | obligation: &TraitObligation<'tcx>, | |
3277 | ) -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
d9579d0f AL |
3278 | let tcx = self.tcx(); |
3279 | ||
3280 | // assemble_candidates_for_unsizing should ensure there are no late bound | |
3281 | // regions here. See the comment there for more details. | |
0bf4aa26 | 3282 | let source = self.infcx |
a1dfa0c6 | 3283 | .shallow_resolve(obligation.self_ty().no_bound_vars().unwrap()); |
0bf4aa26 XL |
3284 | let target = obligation |
3285 | .predicate | |
3286 | .skip_binder() | |
3287 | .trait_ref | |
3288 | .substs | |
3289 | .type_at(1); | |
9e0c209e | 3290 | let target = self.infcx.shallow_resolve(target); |
d9579d0f | 3291 | |
0bf4aa26 XL |
3292 | debug!( |
3293 | "confirm_builtin_unsize_candidate(source={:?}, target={:?})", | |
3294 | source, target | |
3295 | ); | |
d9579d0f AL |
3296 | |
3297 | let mut nested = vec![]; | |
3298 | match (&source.sty, &target.sty) { | |
3299 | // Trait+Kx+'a -> Trait+Ky+'b (upcasts). | |
b7449926 | 3300 | (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => { |
d9579d0f | 3301 | // See assemble_candidates_for_unsizing for more info. |
83c7162d | 3302 | let existential_predicates = data_a.map_bound(|data_a| { |
0731742a XL |
3303 | let iter = |
3304 | data_a.principal().map(|x| ty::ExistentialPredicate::Trait(x)) | |
3305 | .into_iter().chain( | |
0bf4aa26 XL |
3306 | data_a |
3307 | .projection_bounds() | |
3308 | .map(|x| ty::ExistentialPredicate::Projection(x)), | |
3309 | ) | |
3310 | .chain( | |
3311 | data_b | |
3312 | .auto_traits() | |
3313 | .map(ty::ExistentialPredicate::AutoTrait), | |
3314 | ); | |
83c7162d XL |
3315 | tcx.mk_existential_predicates(iter) |
3316 | }); | |
0731742a XL |
3317 | let source_trait = tcx.mk_dynamic(existential_predicates, r_b); |
3318 | ||
3319 | // Require that the traits involved in this upcast are **equal**; | |
3320 | // only the **lifetime bound** is changed. | |
3321 | // | |
3322 | // FIXME: This condition is arguably too strong -- it | |
3323 | // would suffice for the source trait to be a | |
3324 | // *subtype* of the target trait. In particular | |
3325 | // changing from something like `for<'a, 'b> Foo<'a, | |
3326 | // 'b>` to `for<'a> Foo<'a, 'a>` should be | |
3327 | // permitted. And, indeed, in the in commit | |
3328 | // 904a0bde93f0348f69914ee90b1f8b6e4e0d7cbc, this | |
3329 | // condition was loosened. However, when the leak check was added | |
3330 | // back, using subtype here actually guies the coercion code in | |
3331 | // such a way that it accepts `old-lub-glb-object.rs`. This is probably | |
3332 | // a good thing, but I've modified this to `.eq` because I want | |
3333 | // to continue rejecting that test (as we have done for quite some time) | |
3334 | // before we are firmly comfortable with what our behavior | |
3335 | // should be there. -nikomatsakis | |
0bf4aa26 XL |
3336 | let InferOk { obligations, .. } = self.infcx |
3337 | .at(&obligation.cause, obligation.param_env) | |
0731742a | 3338 | .eq(target, source_trait) // FIXME -- see below |
0bf4aa26 | 3339 | .map_err(|_| Unimplemented)?; |
0531ce1d | 3340 | nested.extend(obligations); |
d9579d0f AL |
3341 | |
3342 | // Register one obligation for 'a: 'b. | |
0bf4aa26 XL |
3343 | let cause = ObligationCause::new( |
3344 | obligation.cause.span, | |
3345 | obligation.cause.body_id, | |
3346 | ObjectCastObligation(target), | |
3347 | ); | |
476ff2be | 3348 | let outlives = ty::OutlivesPredicate(r_a, r_b); |
0bf4aa26 XL |
3349 | nested.push(Obligation::with_depth( |
3350 | cause, | |
3351 | obligation.recursion_depth + 1, | |
3352 | obligation.param_env, | |
3353 | ty::Binder::bind(outlives).to_predicate(), | |
3354 | )); | |
d9579d0f AL |
3355 | } |
3356 | ||
3357 | // T -> Trait. | |
b7449926 | 3358 | (_, &ty::Dynamic(ref data, r)) => { |
0bf4aa26 | 3359 | let mut object_dids = data.auto_traits() |
0731742a | 3360 | .chain(data.principal_def_id()); |
0bf4aa26 XL |
3361 | if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) { |
3362 | return Err(TraitNotObjectSafe(did)); | |
d9579d0f AL |
3363 | } |
3364 | ||
0bf4aa26 XL |
3365 | let cause = ObligationCause::new( |
3366 | obligation.cause.span, | |
3367 | obligation.cause.body_id, | |
3368 | ObjectCastObligation(target), | |
3369 | ); | |
3370 | ||
3371 | let predicate_to_obligation = |predicate| { | |
3372 | Obligation::with_depth( | |
3373 | cause.clone(), | |
3374 | obligation.recursion_depth + 1, | |
3375 | obligation.param_env, | |
3376 | predicate, | |
3377 | ) | |
d9579d0f AL |
3378 | }; |
3379 | ||
476ff2be SL |
3380 | // Create obligations: |
3381 | // - Casting T to Trait | |
3382 | // - For all the various builtin bounds attached to the object cast. (In other | |
3383 | // words, if the object type is Foo+Send, this would create an obligation for the | |
3384 | // Send check.) | |
3385 | // - Projection predicates | |
0bf4aa26 XL |
3386 | nested.extend( |
3387 | data.iter() | |
3388 | .map(|d| predicate_to_obligation(d.with_self_ty(tcx, source))), | |
3389 | ); | |
d9579d0f | 3390 | |
476ff2be SL |
3391 | // We can only make objects from sized types. |
3392 | let tr = ty::TraitRef { | |
3393 | def_id: tcx.require_lang_item(lang_items::SizedTraitLangItem), | |
3394 | substs: tcx.mk_substs_trait(source, &[]), | |
3395 | }; | |
0bf4aa26 | 3396 | nested.push(predicate_to_obligation(tr.to_predicate())); |
d9579d0f AL |
3397 | |
3398 | // If the type is `Foo+'a`, ensures that the type | |
3399 | // being cast to `Foo+'a` outlives `'a`: | |
476ff2be | 3400 | let outlives = ty::OutlivesPredicate(source, r); |
0bf4aa26 XL |
3401 | nested.push(predicate_to_obligation( |
3402 | ty::Binder::dummy(outlives).to_predicate(), | |
3403 | )); | |
d9579d0f AL |
3404 | } |
3405 | ||
3406 | // [T; n] -> [T]. | |
b7449926 | 3407 | (&ty::Array(a, _), &ty::Slice(b)) => { |
0bf4aa26 XL |
3408 | let InferOk { obligations, .. } = self.infcx |
3409 | .at(&obligation.cause, obligation.param_env) | |
3410 | .eq(b, a) | |
3411 | .map_err(|_| Unimplemented)?; | |
0531ce1d | 3412 | nested.extend(obligations); |
d9579d0f AL |
3413 | } |
3414 | ||
3415 | // Struct<T> -> Struct<U>. | |
b7449926 | 3416 | (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => { |
0bf4aa26 | 3417 | let fields = def.all_fields() |
7cac9316 | 3418 | .map(|f| tcx.type_of(f.did)) |
e9174d1e | 3419 | .collect::<Vec<_>>(); |
d9579d0f | 3420 | |
62682a34 SL |
3421 | // The last field of the structure has to exist and contain type parameters. |
3422 | let field = if let Some(&field) = fields.last() { | |
3423 | field | |
d9579d0f AL |
3424 | } else { |
3425 | return Err(Unimplemented); | |
3426 | }; | |
0bf4aa26 | 3427 | let mut ty_params = GrowableBitSet::new_empty(); |
9e0c209e | 3428 | let mut found = false; |
c1a9b12d | 3429 | for ty in field.walk() { |
b7449926 | 3430 | if let ty::Param(p) = ty.sty { |
9e0c209e SL |
3431 | ty_params.insert(p.idx as usize); |
3432 | found = true; | |
62682a34 | 3433 | } |
c1a9b12d | 3434 | } |
9e0c209e | 3435 | if !found { |
62682a34 SL |
3436 | return Err(Unimplemented); |
3437 | } | |
d9579d0f | 3438 | |
62682a34 | 3439 | // Replace type parameters used in unsizing with |
b7449926 | 3440 | // Error and ensure they do not affect any other fields. |
d9579d0f AL |
3441 | // This could be checked after type collection for any struct |
3442 | // with a potentially unsized trailing field. | |
8bb4bdeb | 3443 | let params = substs_a.iter().enumerate().map(|(i, &k)| { |
9e0c209e | 3444 | if ty_params.contains(i) { |
94b46f34 | 3445 | tcx.types.err.into() |
9e0c209e SL |
3446 | } else { |
3447 | k | |
3448 | } | |
3449 | }); | |
c30ab7b3 | 3450 | let substs = tcx.mk_substs(params); |
c1a9b12d | 3451 | for &ty in fields.split_last().unwrap().1 { |
9e0c209e | 3452 | if ty.subst(tcx, substs).references_error() { |
d9579d0f AL |
3453 | return Err(Unimplemented); |
3454 | } | |
3455 | } | |
3456 | ||
62682a34 SL |
3457 | // Extract Field<T> and Field<U> from Struct<T> and Struct<U>. |
3458 | let inner_source = field.subst(tcx, substs_a); | |
3459 | let inner_target = field.subst(tcx, substs_b); | |
d9579d0f | 3460 | |
041b39d2 XL |
3461 | // Check that the source struct with the target's |
3462 | // unsized parameters is equal to the target. | |
8bb4bdeb | 3463 | let params = substs_a.iter().enumerate().map(|(i, &k)| { |
9e0c209e | 3464 | if ty_params.contains(i) { |
0531ce1d | 3465 | substs_b.type_at(i).into() |
9e0c209e SL |
3466 | } else { |
3467 | k | |
3468 | } | |
3469 | }); | |
c30ab7b3 | 3470 | let new_struct = tcx.mk_adt(def, tcx.mk_substs(params)); |
0bf4aa26 XL |
3471 | let InferOk { obligations, .. } = self.infcx |
3472 | .at(&obligation.cause, obligation.param_env) | |
3473 | .eq(target, new_struct) | |
3474 | .map_err(|_| Unimplemented)?; | |
0531ce1d | 3475 | nested.extend(obligations); |
d9579d0f | 3476 | |
62682a34 | 3477 | // Construct the nested Field<T>: Unsize<Field<U>> predicate. |
a7813a04 | 3478 | nested.push(tcx.predicate_for_trait_def( |
7cac9316 | 3479 | obligation.param_env, |
d9579d0f AL |
3480 | obligation.cause.clone(), |
3481 | obligation.predicate.def_id(), | |
3482 | obligation.recursion_depth + 1, | |
3483 | inner_source, | |
0bf4aa26 XL |
3484 | &[inner_target.into()], |
3485 | )); | |
d9579d0f AL |
3486 | } |
3487 | ||
041b39d2 | 3488 | // (.., T) -> (.., U). |
b7449926 | 3489 | (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => { |
041b39d2 XL |
3490 | assert_eq!(tys_a.len(), tys_b.len()); |
3491 | ||
3492 | // The last field of the tuple has to exist. | |
94b46f34 | 3493 | let (&a_last, a_mid) = if let Some(x) = tys_a.split_last() { |
041b39d2 XL |
3494 | x |
3495 | } else { | |
3496 | return Err(Unimplemented); | |
3497 | }; | |
94b46f34 | 3498 | let &b_last = tys_b.last().unwrap(); |
041b39d2 XL |
3499 | |
3500 | // Check that the source tuple with the target's | |
3501 | // last element is equal to the target. | |
94b46f34 | 3502 | let new_tuple = tcx.mk_tup(a_mid.iter().cloned().chain(iter::once(b_last))); |
0bf4aa26 XL |
3503 | let InferOk { obligations, .. } = self.infcx |
3504 | .at(&obligation.cause, obligation.param_env) | |
3505 | .eq(target, new_tuple) | |
3506 | .map_err(|_| Unimplemented)?; | |
0531ce1d | 3507 | nested.extend(obligations); |
041b39d2 XL |
3508 | |
3509 | // Construct the nested T: Unsize<U> predicate. | |
3510 | nested.push(tcx.predicate_for_trait_def( | |
3511 | obligation.param_env, | |
3512 | obligation.cause.clone(), | |
3513 | obligation.predicate.def_id(), | |
3514 | obligation.recursion_depth + 1, | |
3515 | a_last, | |
0bf4aa26 XL |
3516 | &[b_last.into()], |
3517 | )); | |
041b39d2 XL |
3518 | } |
3519 | ||
0bf4aa26 | 3520 | _ => bug!(), |
d9579d0f AL |
3521 | }; |
3522 | ||
a1dfa0c6 | 3523 | Ok(VtableBuiltinData { nested }) |
d9579d0f AL |
3524 | } |
3525 | ||
1a4d82fc JJ |
3526 | /////////////////////////////////////////////////////////////////////////// |
3527 | // Matching | |
3528 | // | |
3529 | // Matching is a common path used for both evaluation and | |
3530 | // confirmation. It basically unifies types that appear in impls | |
3531 | // and traits. This does affect the surrounding environment; | |
3532 | // therefore, when used during evaluation, match routines must be | |
3533 | // run inside of a `probe()` so that their side-effects are | |
3534 | // contained. | |
3535 | ||
0bf4aa26 XL |
3536 | fn rematch_impl( |
3537 | &mut self, | |
3538 | impl_def_id: DefId, | |
3539 | obligation: &TraitObligation<'tcx>, | |
0731742a XL |
3540 | snapshot: &CombinedSnapshot<'_, 'tcx>, |
3541 | ) -> Normalized<'tcx, &'tcx Substs<'tcx>> { | |
d9579d0f | 3542 | match self.match_impl(impl_def_id, obligation, snapshot) { |
0731742a | 3543 | Ok(substs) => substs, |
1a4d82fc | 3544 | Err(()) => { |
0bf4aa26 XL |
3545 | bug!( |
3546 | "Impl {:?} was matchable against {:?} but now is not", | |
3547 | impl_def_id, | |
3548 | obligation | |
3549 | ); | |
1a4d82fc JJ |
3550 | } |
3551 | } | |
3552 | } | |
3553 | ||
0bf4aa26 XL |
3554 | fn match_impl( |
3555 | &mut self, | |
3556 | impl_def_id: DefId, | |
3557 | obligation: &TraitObligation<'tcx>, | |
0731742a XL |
3558 | snapshot: &CombinedSnapshot<'_, 'tcx>, |
3559 | ) -> Result<Normalized<'tcx, &'tcx Substs<'tcx>>, ()> { | |
c1a9b12d | 3560 | let impl_trait_ref = self.tcx().impl_trait_ref(impl_def_id).unwrap(); |
1a4d82fc JJ |
3561 | |
3562 | // Before we create the substitutions and everything, first | |
3563 | // consider a "quick reject". This avoids creating more types | |
3564 | // and so forth that we need to. | |
d9579d0f | 3565 | if self.fast_reject_trait_refs(obligation, &impl_trait_ref) { |
1a4d82fc JJ |
3566 | return Err(()); |
3567 | } | |
3568 | ||
0bf4aa26 | 3569 | let (skol_obligation, placeholder_map) = self.infcx() |
a1dfa0c6 | 3570 | .replace_bound_vars_with_placeholders(&obligation.predicate); |
d9579d0f AL |
3571 | let skol_obligation_trait_ref = skol_obligation.trait_ref; |
3572 | ||
0bf4aa26 XL |
3573 | let impl_substs = self.infcx |
3574 | .fresh_substs_for_item(obligation.cause.span, impl_def_id); | |
3575 | ||
3576 | let impl_trait_ref = impl_trait_ref.subst(self.tcx(), impl_substs); | |
3577 | ||
3578 | let Normalized { | |
3579 | value: impl_trait_ref, | |
3580 | obligations: mut nested_obligations, | |
3581 | } = project::normalize_with_depth( | |
3582 | self, | |
3583 | obligation.param_env, | |
3584 | obligation.cause.clone(), | |
3585 | obligation.recursion_depth + 1, | |
3586 | &impl_trait_ref, | |
3587 | ); | |
3588 | ||
3589 | debug!( | |
3590 | "match_impl(impl_def_id={:?}, obligation={:?}, \ | |
3591 | impl_trait_ref={:?}, skol_obligation_trait_ref={:?})", | |
3592 | impl_def_id, obligation, impl_trait_ref, skol_obligation_trait_ref | |
3593 | ); | |
3594 | ||
3595 | let InferOk { obligations, .. } = self.infcx | |
3596 | .at(&obligation.cause, obligation.param_env) | |
3597 | .eq(skol_obligation_trait_ref, impl_trait_ref) | |
3598 | .map_err(|e| debug!("match_impl: failed eq_trait_refs due to `{}`", e))?; | |
0531ce1d | 3599 | nested_obligations.extend(obligations); |
1a4d82fc | 3600 | |
0731742a | 3601 | if let Err(e) = self.infcx.leak_check(false, &placeholder_map, snapshot) { |
62682a34 | 3602 | debug!("match_impl: failed leak check due to `{}`", e); |
c34b1796 | 3603 | return Err(()); |
1a4d82fc JJ |
3604 | } |
3605 | ||
62682a34 | 3606 | debug!("match_impl: success impl_substs={:?}", impl_substs); |
0731742a XL |
3607 | Ok(Normalized { |
3608 | value: impl_substs, | |
3609 | obligations: nested_obligations, | |
3610 | }) | |
1a4d82fc JJ |
3611 | } |
3612 | ||
0bf4aa26 XL |
3613 | fn fast_reject_trait_refs( |
3614 | &mut self, | |
3615 | obligation: &TraitObligation<'_>, | |
3616 | impl_trait_ref: &ty::TraitRef<'_>, | |
3617 | ) -> bool { | |
1a4d82fc JJ |
3618 | // We can avoid creating type variables and doing the full |
3619 | // substitution if we find that any of the input types, when | |
3620 | // simplified, do not match. | |
3621 | ||
0bf4aa26 XL |
3622 | obligation |
3623 | .predicate | |
3624 | .skip_binder() | |
3625 | .input_types() | |
62682a34 | 3626 | .zip(impl_trait_ref.input_types()) |
9e0c209e | 3627 | .any(|(obligation_ty, impl_ty)| { |
1a4d82fc JJ |
3628 | let simplified_obligation_ty = |
3629 | fast_reject::simplify_type(self.tcx(), obligation_ty, true); | |
0bf4aa26 | 3630 | let simplified_impl_ty = fast_reject::simplify_type(self.tcx(), impl_ty, false); |
1a4d82fc | 3631 | |
0bf4aa26 XL |
3632 | simplified_obligation_ty.is_some() |
3633 | && simplified_impl_ty.is_some() | |
3634 | && simplified_obligation_ty != simplified_impl_ty | |
1a4d82fc JJ |
3635 | }) |
3636 | } | |
3637 | ||
85aaf69f | 3638 | /// Normalize `where_clause_trait_ref` and try to match it against |
9fa01778 | 3639 | /// `obligation`. If successful, return any predicates that |
85aaf69f SL |
3640 | /// result from the normalization. Normalization is necessary |
3641 | /// because where-clauses are stored in the parameter environment | |
3642 | /// unnormalized. | |
0bf4aa26 XL |
3643 | fn match_where_clause_trait_ref( |
3644 | &mut self, | |
3645 | obligation: &TraitObligation<'tcx>, | |
3646 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>, | |
3647 | ) -> Result<Vec<PredicateObligation<'tcx>>, ()> { | |
0531ce1d | 3648 | self.match_poly_trait_ref(obligation, where_clause_trait_ref) |
85aaf69f SL |
3649 | } |
3650 | ||
3651 | /// Returns `Ok` if `poly_trait_ref` being true implies that the | |
3652 | /// obligation is satisfied. | |
0bf4aa26 XL |
3653 | fn match_poly_trait_ref( |
3654 | &mut self, | |
3655 | obligation: &TraitObligation<'tcx>, | |
3656 | poly_trait_ref: ty::PolyTraitRef<'tcx>, | |
3657 | ) -> Result<Vec<PredicateObligation<'tcx>>, ()> { | |
3658 | debug!( | |
3659 | "match_poly_trait_ref: obligation={:?} poly_trait_ref={:?}", | |
3660 | obligation, poly_trait_ref | |
3661 | ); | |
1a4d82fc | 3662 | |
0bf4aa26 XL |
3663 | self.infcx |
3664 | .at(&obligation.cause, obligation.param_env) | |
3665 | .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref) | |
3666 | .map(|InferOk { obligations, .. }| obligations) | |
3667 | .map_err(|_| ()) | |
1a4d82fc JJ |
3668 | } |
3669 | ||
1a4d82fc JJ |
3670 | /////////////////////////////////////////////////////////////////////////// |
3671 | // Miscellany | |
3672 | ||
0bf4aa26 XL |
3673 | fn match_fresh_trait_refs( |
3674 | &self, | |
3675 | previous: &ty::PolyTraitRef<'tcx>, | |
3676 | current: &ty::PolyTraitRef<'tcx>, | |
3677 | ) -> bool { | |
e9174d1e | 3678 | let mut matcher = ty::_match::Match::new(self.tcx()); |
c34b1796 AL |
3679 | matcher.relate(previous, current).is_ok() |
3680 | } | |
3681 | ||
0bf4aa26 XL |
3682 | fn push_stack<'o, 's: 'o>( |
3683 | &mut self, | |
3684 | previous_stack: TraitObligationStackList<'s, 'tcx>, | |
3685 | obligation: &'o TraitObligation<'tcx>, | |
3686 | ) -> TraitObligationStack<'o, 'tcx> { | |
3687 | let fresh_trait_ref = obligation | |
3688 | .predicate | |
3689 | .to_poly_trait_ref() | |
3690 | .fold_with(&mut self.freshener); | |
1a4d82fc JJ |
3691 | |
3692 | TraitObligationStack { | |
041b39d2 XL |
3693 | obligation, |
3694 | fresh_trait_ref, | |
c34b1796 | 3695 | previous: previous_stack, |
1a4d82fc JJ |
3696 | } |
3697 | } | |
3698 | ||
0bf4aa26 XL |
3699 | fn closure_trait_ref_unnormalized( |
3700 | &mut self, | |
3701 | obligation: &TraitObligation<'tcx>, | |
3702 | closure_def_id: DefId, | |
3703 | substs: ty::ClosureSubsts<'tcx>, | |
3704 | ) -> ty::PolyTraitRef<'tcx> { | |
a1dfa0c6 XL |
3705 | debug!( |
3706 | "closure_trait_ref_unnormalized(obligation={:?}, closure_def_id={:?}, substs={:?})", | |
3707 | obligation, closure_def_id, substs, | |
3708 | ); | |
ff7c6d11 | 3709 | let closure_type = self.infcx.closure_sig(closure_def_id, substs); |
83c7162d | 3710 | |
a1dfa0c6 XL |
3711 | debug!( |
3712 | "closure_trait_ref_unnormalized: closure_type = {:?}", | |
3713 | closure_type | |
3714 | ); | |
3715 | ||
85aaf69f SL |
3716 | // (1) Feels icky to skip the binder here, but OTOH we know |
3717 | // that the self-type is an unboxed closure type and hence is | |
3718 | // in fact unparameterized (or at least does not reference any | |
3719 | // regions bound in the obligation). Still probably some | |
3720 | // refactoring could make this nicer. | |
0bf4aa26 XL |
3721 | self.tcx() |
3722 | .closure_trait_ref_and_return_type( | |
3723 | obligation.predicate.def_id(), | |
3724 | obligation.predicate.skip_binder().self_ty(), // (1) | |
3725 | closure_type, | |
3726 | util::TupleArgumentsFlag::No, | |
3727 | ) | |
83c7162d | 3728 | .map_bound(|(trait_ref, _)| trait_ref) |
85aaf69f SL |
3729 | } |
3730 | ||
0bf4aa26 XL |
3731 | fn generator_trait_ref_unnormalized( |
3732 | &mut self, | |
3733 | obligation: &TraitObligation<'tcx>, | |
3734 | closure_def_id: DefId, | |
3735 | substs: ty::GeneratorSubsts<'tcx>, | |
3736 | ) -> ty::PolyTraitRef<'tcx> { | |
94b46f34 | 3737 | let gen_sig = substs.poly_sig(closure_def_id, self.tcx()); |
83c7162d | 3738 | |
ea8adc8c XL |
3739 | // (1) Feels icky to skip the binder here, but OTOH we know |
3740 | // that the self-type is an generator type and hence is | |
3741 | // in fact unparameterized (or at least does not reference any | |
3742 | // regions bound in the obligation). Still probably some | |
3743 | // refactoring could make this nicer. | |
62682a34 | 3744 | |
0bf4aa26 XL |
3745 | self.tcx() |
3746 | .generator_trait_ref_and_outputs( | |
3747 | obligation.predicate.def_id(), | |
3748 | obligation.predicate.skip_binder().self_ty(), // (1) | |
3749 | gen_sig, | |
3750 | ) | |
83c7162d | 3751 | .map_bound(|(trait_ref, ..)| trait_ref) |
62682a34 SL |
3752 | } |
3753 | ||
c34b1796 AL |
3754 | /// Returns the obligations that are implied by instantiating an |
3755 | /// impl or trait. The obligations are substituted and fully | |
3756 | /// normalized. This is used when confirming an impl or default | |
3757 | /// impl. | |
0bf4aa26 XL |
3758 | fn impl_or_trait_obligations( |
3759 | &mut self, | |
3760 | cause: ObligationCause<'tcx>, | |
3761 | recursion_depth: usize, | |
3762 | param_env: ty::ParamEnv<'tcx>, | |
3763 | def_id: DefId, // of impl or trait | |
3764 | substs: &Substs<'tcx>, // for impl or trait | |
0bf4aa26 | 3765 | ) -> Vec<PredicateObligation<'tcx>> { |
62682a34 | 3766 | debug!("impl_or_trait_obligations(def_id={:?})", def_id); |
92a42be0 | 3767 | let tcx = self.tcx(); |
c34b1796 | 3768 | |
92a42be0 SL |
3769 | // To allow for one-pass evaluation of the nested obligation, |
3770 | // each predicate must be preceded by the obligations required | |
3771 | // to normalize it. | |
3772 | // for example, if we have: | |
3773 | // impl<U: Iterator, V: Iterator<Item=U>> Foo for V where U::Item: Copy | |
3774 | // the impl will have the following predicates: | |
3775 | // <V as Iterator>::Item = U, | |
3776 | // U: Iterator, U: Sized, | |
3777 | // V: Iterator, V: Sized, | |
3778 | // <U as Iterator>::Item: Copy | |
3779 | // When we substitute, say, `V => IntoIter<u32>, U => $0`, the last | |
3780 | // obligation will normalize to `<$0 as Iterator>::Item = $1` and | |
3781 | // `$1: Copy`, so we must ensure the obligations are emitted in | |
3782 | // that order. | |
7cac9316 | 3783 | let predicates = tcx.predicates_of(def_id); |
9e0c209e | 3784 | assert_eq!(predicates.parent, None); |
0bf4aa26 XL |
3785 | let mut predicates: Vec<_> = predicates |
3786 | .predicates | |
3787 | .iter() | |
3788 | .flat_map(|(predicate, _)| { | |
3789 | let predicate = normalize_with_depth( | |
3790 | self, | |
3791 | param_env, | |
3792 | cause.clone(), | |
3793 | recursion_depth, | |
3794 | &predicate.subst(tcx, substs), | |
3795 | ); | |
3796 | predicate.obligations.into_iter().chain(Some(Obligation { | |
9e0c209e | 3797 | cause: cause.clone(), |
041b39d2 | 3798 | recursion_depth, |
7cac9316 | 3799 | param_env, |
0bf4aa26 | 3800 | predicate: predicate.value, |
9e0c209e | 3801 | })) |
0bf4aa26 XL |
3802 | }) |
3803 | .collect(); | |
94b46f34 | 3804 | |
0531ce1d XL |
3805 | // We are performing deduplication here to avoid exponential blowups |
3806 | // (#38528) from happening, but the real cause of the duplication is | |
3807 | // unknown. What we know is that the deduplication avoids exponential | |
94b46f34 | 3808 | // amount of predicates being propagated when processing deeply nested |
0531ce1d | 3809 | // types. |
94b46f34 XL |
3810 | // |
3811 | // This code is hot enough that it's worth avoiding the allocation | |
3812 | // required for the FxHashSet when possible. Special-casing lengths 0, | |
3813 | // 1 and 2 covers roughly 75--80% of the cases. | |
3814 | if predicates.len() <= 1 { | |
3815 | // No possibility of duplicates. | |
3816 | } else if predicates.len() == 2 { | |
3817 | // Only two elements. Drop the second if they are equal. | |
3818 | if predicates[0] == predicates[1] { | |
3819 | predicates.truncate(1); | |
3820 | } | |
3821 | } else { | |
3822 | // Three or more elements. Use a general deduplication process. | |
0bf4aa26 | 3823 | let mut seen = FxHashSet::default(); |
94b46f34 XL |
3824 | predicates.retain(|i| seen.insert(i.clone())); |
3825 | } | |
0731742a XL |
3826 | |
3827 | predicates | |
1a4d82fc | 3828 | } |
5bcae85e | 3829 | } |
1a4d82fc | 3830 | |
5bcae85e | 3831 | impl<'tcx> TraitObligation<'tcx> { |
1a4d82fc | 3832 | #[allow(unused_comparisons)] |
0bf4aa26 XL |
3833 | pub fn derived_cause( |
3834 | &self, | |
3835 | variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, | |
3836 | ) -> ObligationCause<'tcx> { | |
1a4d82fc JJ |
3837 | /*! |
3838 | * Creates a cause for obligations that are derived from | |
3839 | * `obligation` by a recursive search (e.g., for a builtin | |
2c00a5a8 | 3840 | * bound, or eventually a `auto trait Foo`). If `obligation` |
1a4d82fc JJ |
3841 | * is itself a derived obligation, this is just a clone, but |
3842 | * otherwise we create a "derived obligation" cause so as to | |
3843 | * keep track of the original root obligation for error | |
3844 | * reporting. | |
3845 | */ | |
3846 | ||
5bcae85e SL |
3847 | let obligation = self; |
3848 | ||
1a4d82fc JJ |
3849 | // NOTE(flaper87): As of now, it keeps track of the whole error |
3850 | // chain. Ideally, we should have a way to configure this either | |
3851 | // by using -Z verbose or just a CLI argument. | |
3852 | if obligation.recursion_depth >= 0 { | |
9cc50fc6 SL |
3853 | let derived_cause = DerivedObligationCause { |
3854 | parent_trait_ref: obligation.predicate.to_poly_trait_ref(), | |
0bf4aa26 | 3855 | parent_code: Rc::new(obligation.cause.code.clone()), |
1a4d82fc | 3856 | }; |
9cc50fc6 | 3857 | let derived_code = variant(derived_cause); |
0bf4aa26 XL |
3858 | ObligationCause::new( |
3859 | obligation.cause.span, | |
3860 | obligation.cause.body_id, | |
3861 | derived_code, | |
3862 | ) | |
1a4d82fc JJ |
3863 | } else { |
3864 | obligation.cause.clone() | |
3865 | } | |
3866 | } | |
3867 | } | |
3868 | ||
1a4d82fc | 3869 | impl<'tcx> SelectionCache<'tcx> { |
0bf4aa26 | 3870 | /// Actually frees the underlying memory in contrast to what stdlib containers do on `clear` |
0531ce1d | 3871 | pub fn clear(&self) { |
0bf4aa26 | 3872 | *self.hashmap.borrow_mut() = Default::default(); |
0531ce1d | 3873 | } |
1a4d82fc JJ |
3874 | } |
3875 | ||
92a42be0 | 3876 | impl<'tcx> EvaluationCache<'tcx> { |
0bf4aa26 | 3877 | /// Actually frees the underlying memory in contrast to what stdlib containers do on `clear` |
0531ce1d | 3878 | pub fn clear(&self) { |
0bf4aa26 | 3879 | *self.hashmap.borrow_mut() = Default::default(); |
0531ce1d | 3880 | } |
92a42be0 SL |
3881 | } |
3882 | ||
0bf4aa26 XL |
3883 | impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> { |
3884 | fn list(&'o self) -> TraitObligationStackList<'o, 'tcx> { | |
c34b1796 AL |
3885 | TraitObligationStackList::with(self) |
3886 | } | |
3887 | ||
0bf4aa26 | 3888 | fn iter(&'o self) -> TraitObligationStackList<'o, 'tcx> { |
c34b1796 AL |
3889 | self.list() |
3890 | } | |
3891 | } | |
3892 | ||
3893 | #[derive(Copy, Clone)] | |
0bf4aa26 XL |
3894 | struct TraitObligationStackList<'o, 'tcx: 'o> { |
3895 | head: Option<&'o TraitObligationStack<'o, 'tcx>>, | |
c34b1796 AL |
3896 | } |
3897 | ||
0bf4aa26 XL |
3898 | impl<'o, 'tcx> TraitObligationStackList<'o, 'tcx> { |
3899 | fn empty() -> TraitObligationStackList<'o, 'tcx> { | |
c34b1796 AL |
3900 | TraitObligationStackList { head: None } |
3901 | } | |
3902 | ||
0bf4aa26 | 3903 | fn with(r: &'o TraitObligationStack<'o, 'tcx>) -> TraitObligationStackList<'o, 'tcx> { |
c34b1796 | 3904 | TraitObligationStackList { head: Some(r) } |
1a4d82fc | 3905 | } |
9fa01778 XL |
3906 | |
3907 | fn head(&self) -> Option<&'o TraitObligationStack<'o, 'tcx>> { | |
3908 | self.head | |
3909 | } | |
1a4d82fc JJ |
3910 | } |
3911 | ||
0bf4aa26 XL |
3912 | impl<'o, 'tcx> Iterator for TraitObligationStackList<'o, 'tcx> { |
3913 | type Item = &'o TraitObligationStack<'o, 'tcx>; | |
1a4d82fc | 3914 | |
0bf4aa26 | 3915 | fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> { |
c34b1796 | 3916 | match self.head { |
1a4d82fc JJ |
3917 | Some(o) => { |
3918 | *self = o.previous; | |
3919 | Some(o) | |
3920 | } | |
0bf4aa26 | 3921 | None => None, |
1a4d82fc JJ |
3922 | } |
3923 | } | |
3924 | } | |
3925 | ||
0bf4aa26 XL |
3926 | impl<'o, 'tcx> fmt::Debug for TraitObligationStack<'o, 'tcx> { |
3927 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
62682a34 | 3928 | write!(f, "TraitObligationStack({:?})", self.obligation) |
1a4d82fc JJ |
3929 | } |
3930 | } | |
3931 | ||
94b46f34 | 3932 | #[derive(Clone, Eq, PartialEq)] |
3b2f2976 XL |
3933 | pub struct WithDepNode<T> { |
3934 | dep_node: DepNodeIndex, | |
0bf4aa26 | 3935 | cached_value: T, |
3b2f2976 | 3936 | } |
c34b1796 | 3937 | |
3b2f2976 XL |
3938 | impl<T: Clone> WithDepNode<T> { |
3939 | pub fn new(dep_node: DepNodeIndex, cached_value: T) -> Self { | |
0bf4aa26 XL |
3940 | WithDepNode { |
3941 | dep_node, | |
3942 | cached_value, | |
3943 | } | |
3b2f2976 XL |
3944 | } |
3945 | ||
0bf4aa26 | 3946 | pub fn get(&self, tcx: TyCtxt<'_, '_, '_>) -> T { |
3b2f2976 XL |
3947 | tcx.dep_graph.read_index(self.dep_node); |
3948 | self.cached_value.clone() | |
1a4d82fc JJ |
3949 | } |
3950 | } |