]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
c34b1796 | 11 | //! See `README.md` for high-level documentation |
1a4d82fc JJ |
12 | #![allow(dead_code)] // FIXME -- just temporarily |
13 | ||
14 | pub use self::MethodMatchResult::*; | |
15 | pub use self::MethodMatchedData::*; | |
16 | use self::SelectionCandidate::*; | |
17 | use self::BuiltinBoundConditions::*; | |
18 | use self::EvaluationResult::*; | |
19 | ||
c34b1796 AL |
20 | use super::coherence; |
21 | use super::DerivedObligationCause; | |
22 | use super::project; | |
23 | use super::project::{normalize_with_depth, Normalized}; | |
85aaf69f | 24 | use super::{PredicateObligation, TraitObligation, ObligationCause}; |
c34b1796 AL |
25 | use super::report_overflow_error; |
26 | use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation}; | |
27 | use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch}; | |
d9579d0f AL |
28 | use super::{ObjectCastObligation, Obligation}; |
29 | use super::TraitNotObjectSafe; | |
c34b1796 AL |
30 | use super::Selection; |
31 | use super::SelectionResult; | |
85aaf69f | 32 | use super::{VtableBuiltin, VtableImpl, VtableParam, VtableClosure, |
c34b1796 | 33 | VtableFnPointer, VtableObject, VtableDefaultImpl}; |
62682a34 SL |
34 | use super::{VtableImplData, VtableObjectData, VtableBuiltinData, |
35 | VtableClosureData, VtableDefaultImplData}; | |
1a4d82fc | 36 | use super::object_safety; |
c34b1796 | 37 | use super::util; |
1a4d82fc JJ |
38 | |
39 | use middle::fast_reject; | |
62682a34 | 40 | use middle::subst::{Subst, Substs, TypeSpace}; |
d9579d0f | 41 | use middle::ty::{self, AsPredicate, RegionEscape, ToPolyTraitRef, Ty}; |
1a4d82fc JJ |
42 | use middle::infer; |
43 | use middle::infer::{InferCtxt, TypeFreshener}; | |
44 | use middle::ty_fold::TypeFoldable; | |
c34b1796 AL |
45 | use middle::ty_match; |
46 | use middle::ty_relate::TypeRelation; | |
62682a34 | 47 | |
1a4d82fc | 48 | use std::cell::RefCell; |
62682a34 | 49 | use std::fmt; |
1a4d82fc JJ |
50 | use std::rc::Rc; |
51 | use syntax::{abi, ast}; | |
52 | use util::common::ErrorReported; | |
c34b1796 | 53 | use util::nodemap::FnvHashMap; |
1a4d82fc JJ |
54 | |
55 | pub struct SelectionContext<'cx, 'tcx:'cx> { | |
56 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
85aaf69f | 57 | closure_typer: &'cx (ty::ClosureTyper<'tcx>+'cx), |
1a4d82fc JJ |
58 | |
59 | /// Freshener used specifically for skolemizing entries on the | |
60 | /// obligation stack. This ensures that all entries on the stack | |
61 | /// at one time will have the same set of skolemized entries, | |
62 | /// which is important for checking for trait bounds that | |
63 | /// recursively require themselves. | |
64 | freshener: TypeFreshener<'cx, 'tcx>, | |
65 | ||
66 | /// If true, indicates that the evaluation should be conservative | |
67 | /// and consider the possibility of types outside this crate. | |
68 | /// This comes up primarily when resolving ambiguity. Imagine | |
69 | /// there is some trait reference `$0 : Bar` where `$0` is an | |
70 | /// inference variable. If `intercrate` is true, then we can never | |
71 | /// say for sure that this reference is not implemented, even if | |
72 | /// there are *no impls at all for `Bar`*, because `$0` could be | |
73 | /// bound to some type that in a downstream crate that implements | |
74 | /// `Bar`. This is the suitable mode for coherence. Elsewhere, | |
75 | /// though, we set this to false, because we are only interested | |
76 | /// in types that the user could actually have written --- in | |
77 | /// other words, we consider `$0 : Bar` to be unimplemented if | |
78 | /// there is no type that the user could *actually name* that | |
79 | /// would satisfy it. This avoids crippling inference, basically. | |
80 | intercrate: bool, | |
81 | } | |
82 | ||
83 | // A stack that walks back up the stack frame. | |
84 | struct TraitObligationStack<'prev, 'tcx: 'prev> { | |
85 | obligation: &'prev TraitObligation<'tcx>, | |
86 | ||
87 | /// Trait ref from `obligation` but skolemized with the | |
88 | /// selection-context's freshener. Used to check for recursion. | |
89 | fresh_trait_ref: ty::PolyTraitRef<'tcx>, | |
90 | ||
c34b1796 | 91 | previous: TraitObligationStackList<'prev, 'tcx>, |
1a4d82fc JJ |
92 | } |
93 | ||
94 | #[derive(Clone)] | |
95 | pub struct SelectionCache<'tcx> { | |
d9579d0f | 96 | hashmap: RefCell<FnvHashMap<ty::TraitRef<'tcx>, |
c34b1796 | 97 | SelectionResult<'tcx, SelectionCandidate<'tcx>>>>, |
1a4d82fc JJ |
98 | } |
99 | ||
100 | pub enum MethodMatchResult { | |
101 | MethodMatched(MethodMatchedData), | |
102 | MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>), | |
103 | MethodDidNotMatch, | |
104 | } | |
105 | ||
c34b1796 | 106 | #[derive(Copy, Clone, Debug)] |
1a4d82fc JJ |
107 | pub enum MethodMatchedData { |
108 | // In the case of a precise match, we don't really need to store | |
109 | // how the match was found. So don't. | |
110 | PreciseMethodMatch, | |
111 | ||
112 | // In the case of a coercion, we need to know the precise impl so | |
113 | // that we can determine the type to which things were coerced. | |
114 | CoerciveMethodMatch(/* impl we matched */ ast::DefId) | |
115 | } | |
116 | ||
117 | /// The selection process begins by considering all impls, where | |
118 | /// clauses, and so forth that might resolve an obligation. Sometimes | |
119 | /// we'll be able to say definitively that (e.g.) an impl does not | |
c34b1796 | 120 | /// apply to the obligation: perhaps it is defined for `usize` but the |
1a4d82fc JJ |
121 | /// obligation is for `int`. In that case, we drop the impl out of the |
122 | /// list. But the other cases are considered *candidates*. | |
123 | /// | |
d9579d0f AL |
124 | /// For selection to succeed, there must be exactly one matching |
125 | /// candidate. If the obligation is fully known, this is guaranteed | |
126 | /// by coherence. However, if the obligation contains type parameters | |
127 | /// or variables, there may be multiple such impls. | |
1a4d82fc | 128 | /// |
d9579d0f AL |
129 | /// It is not a real problem if multiple matching impls exist because |
130 | /// of type variables - it just means the obligation isn't sufficiently | |
131 | /// elaborated. In that case we report an ambiguity, and the caller can | |
132 | /// try again after more type information has been gathered or report a | |
133 | /// "type annotations required" error. | |
134 | /// | |
135 | /// However, with type parameters, this can be a real problem - type | |
136 | /// parameters don't unify with regular types, but they *can* unify | |
137 | /// with variables from blanket impls, and (unless we know its bounds | |
138 | /// will always be satisfied) picking the blanket impl will be wrong | |
139 | /// for at least *some* substitutions. To make this concrete, if we have | |
140 | /// | |
141 | /// trait AsDebug { type Out : fmt::Debug; fn debug(self) -> Self::Out; } | |
142 | /// impl<T: fmt::Debug> AsDebug for T { | |
143 | /// type Out = T; | |
144 | /// fn debug(self) -> fmt::Debug { self } | |
145 | /// } | |
146 | /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); } | |
147 | /// | |
148 | /// we can't just use the impl to resolve the <T as AsDebug> obligation | |
149 | /// - a type from another crate (that doesn't implement fmt::Debug) could | |
150 | /// implement AsDebug. | |
151 | /// | |
152 | /// Because where-clauses match the type exactly, multiple clauses can | |
153 | /// only match if there are unresolved variables, and we can mostly just | |
154 | /// report this ambiguity in that case. This is still a problem - we can't | |
155 | /// *do anything* with ambiguities that involve only regions. This is issue | |
156 | /// #21974. | |
157 | /// | |
158 | /// If a single where-clause matches and there are no inference | |
159 | /// variables left, then it definitely matches and we can just select | |
160 | /// it. | |
161 | /// | |
162 | /// In fact, we even select the where-clause when the obligation contains | |
163 | /// inference variables. The can lead to inference making "leaps of logic", | |
164 | /// for example in this situation: | |
165 | /// | |
166 | /// pub trait Foo<T> { fn foo(&self) -> T; } | |
167 | /// impl<T> Foo<()> for T { fn foo(&self) { } } | |
168 | /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } } | |
169 | /// | |
170 | /// pub fn foo<T>(t: T) where T: Foo<bool> { | |
171 | /// println!("{:?}", <T as Foo<_>>::foo(&t)); | |
172 | /// } | |
173 | /// fn main() { foo(false); } | |
174 | /// | |
175 | /// Here the obligation <T as Foo<$0>> can be matched by both the blanket | |
176 | /// impl and the where-clause. We select the where-clause and unify $0=bool, | |
177 | /// so the program prints "false". However, if the where-clause is omitted, | |
178 | /// the blanket impl is selected, we unify $0=(), and the program prints | |
179 | /// "()". | |
180 | /// | |
181 | /// Exactly the same issues apply to projection and object candidates, except | |
182 | /// that we can have both a projection candidate and a where-clause candidate | |
183 | /// for the same obligation. In that case either would do (except that | |
184 | /// different "leaps of logic" would occur if inference variables are | |
185 | /// present), and we just pick the projection. This is, for example, | |
186 | /// required for associated types to work in default impls, as the bounds | |
187 | /// are visible both as projection bounds and as where-clauses from the | |
188 | /// parameter environment. | |
85aaf69f | 189 | #[derive(PartialEq,Eq,Debug,Clone)] |
1a4d82fc | 190 | enum SelectionCandidate<'tcx> { |
85aaf69f | 191 | PhantomFnCandidate, |
1a4d82fc JJ |
192 | BuiltinCandidate(ty::BuiltinBound), |
193 | ParamCandidate(ty::PolyTraitRef<'tcx>), | |
194 | ImplCandidate(ast::DefId), | |
c34b1796 AL |
195 | DefaultImplCandidate(ast::DefId), |
196 | DefaultImplObjectCandidate(ast::DefId), | |
1a4d82fc JJ |
197 | |
198 | /// This is a trait matching with a projected type as `Self`, and | |
199 | /// we found an applicable bound in the trait definition. | |
200 | ProjectionCandidate, | |
201 | ||
202 | /// Implementation of a `Fn`-family trait by one of the | |
203 | /// anonymous types generated for a `||` expression. | |
85aaf69f | 204 | ClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>), |
1a4d82fc JJ |
205 | |
206 | /// Implementation of a `Fn`-family trait by one of the anonymous | |
207 | /// types generated for a fn pointer type (e.g., `fn(int)->int`) | |
208 | FnPointerCandidate, | |
209 | ||
210 | ObjectCandidate, | |
211 | ||
c34b1796 AL |
212 | BuiltinObjectCandidate, |
213 | ||
d9579d0f AL |
214 | BuiltinUnsizeCandidate, |
215 | ||
1a4d82fc JJ |
216 | ErrorCandidate, |
217 | } | |
218 | ||
219 | struct SelectionCandidateSet<'tcx> { | |
220 | // a list of candidates that definitely apply to the current | |
221 | // obligation (meaning: types unify). | |
222 | vec: Vec<SelectionCandidate<'tcx>>, | |
223 | ||
224 | // if this is true, then there were candidates that might or might | |
225 | // not have applied, but we couldn't tell. This occurs when some | |
226 | // of the input types are type variables, in which case there are | |
227 | // various "builtin" rules that might or might not trigger. | |
228 | ambiguous: bool, | |
229 | } | |
230 | ||
231 | enum BuiltinBoundConditions<'tcx> { | |
c34b1796 | 232 | If(ty::Binder<Vec<Ty<'tcx>>>), |
1a4d82fc JJ |
233 | ParameterBuiltin, |
234 | AmbiguousBuiltin | |
235 | } | |
236 | ||
85aaf69f | 237 | #[derive(Debug)] |
1a4d82fc JJ |
238 | enum EvaluationResult<'tcx> { |
239 | EvaluatedToOk, | |
240 | EvaluatedToAmbig, | |
241 | EvaluatedToErr(SelectionError<'tcx>), | |
242 | } | |
243 | ||
244 | impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | |
245 | pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>, | |
85aaf69f | 246 | closure_typer: &'cx ty::ClosureTyper<'tcx>) |
1a4d82fc JJ |
247 | -> SelectionContext<'cx, 'tcx> { |
248 | SelectionContext { | |
249 | infcx: infcx, | |
250 | closure_typer: closure_typer, | |
251 | freshener: infcx.freshener(), | |
252 | intercrate: false, | |
253 | } | |
254 | } | |
255 | ||
256 | pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>, | |
85aaf69f | 257 | closure_typer: &'cx ty::ClosureTyper<'tcx>) |
1a4d82fc JJ |
258 | -> SelectionContext<'cx, 'tcx> { |
259 | SelectionContext { | |
260 | infcx: infcx, | |
261 | closure_typer: closure_typer, | |
262 | freshener: infcx.freshener(), | |
263 | intercrate: true, | |
264 | } | |
265 | } | |
266 | ||
267 | pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> { | |
268 | self.infcx | |
269 | } | |
270 | ||
271 | pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> { | |
272 | self.infcx.tcx | |
273 | } | |
274 | ||
275 | pub fn param_env(&self) -> &'cx ty::ParameterEnvironment<'cx, 'tcx> { | |
276 | self.closure_typer.param_env() | |
277 | } | |
278 | ||
85aaf69f SL |
279 | pub fn closure_typer(&self) -> &'cx (ty::ClosureTyper<'tcx>+'cx) { |
280 | self.closure_typer | |
281 | } | |
282 | ||
1a4d82fc JJ |
283 | /////////////////////////////////////////////////////////////////////////// |
284 | // Selection | |
285 | // | |
286 | // The selection phase tries to identify *how* an obligation will | |
287 | // be resolved. For example, it will identify which impl or | |
288 | // parameter bound is to be used. The process can be inconclusive | |
289 | // if the self type in the obligation is not fully inferred. Selection | |
290 | // can result in an error in one of two ways: | |
291 | // | |
292 | // 1. If no applicable impl or parameter bound can be found. | |
293 | // 2. If the output type parameters in the obligation do not match | |
294 | // those specified by the impl/bound. For example, if the obligation | |
295 | // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies | |
296 | // `impl<T> Iterable<T> for Vec<T>`, than an error would result. | |
297 | ||
85aaf69f SL |
298 | /// Attempts to satisfy the obligation. If successful, this will affect the surrounding |
299 | /// type environment by performing unification. | |
1a4d82fc JJ |
300 | pub fn select(&mut self, obligation: &TraitObligation<'tcx>) |
301 | -> SelectionResult<'tcx, Selection<'tcx>> { | |
62682a34 | 302 | debug!("select({:?})", obligation); |
1a4d82fc JJ |
303 | assert!(!obligation.predicate.has_escaping_regions()); |
304 | ||
c34b1796 | 305 | let stack = self.push_stack(TraitObligationStackList::empty(), obligation); |
1a4d82fc | 306 | match try!(self.candidate_from_obligation(&stack)) { |
85aaf69f SL |
307 | None => { |
308 | self.consider_unification_despite_ambiguity(obligation); | |
309 | Ok(None) | |
310 | } | |
1a4d82fc JJ |
311 | Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))), |
312 | } | |
313 | } | |
314 | ||
85aaf69f SL |
315 | /// In the particular case of unboxed closure obligations, we can |
316 | /// sometimes do some amount of unification for the | |
317 | /// argument/return types even though we can't yet fully match obligation. | |
318 | /// The particular case we are interesting in is an obligation of the form: | |
319 | /// | |
320 | /// C : FnFoo<A> | |
321 | /// | |
322 | /// where `C` is an unboxed closure type and `FnFoo` is one of the | |
323 | /// `Fn` traits. Because we know that users cannot write impls for closure types | |
324 | /// themselves, the only way that `C : FnFoo` can fail to match is under two | |
325 | /// conditions: | |
326 | /// | |
327 | /// 1. The closure kind for `C` is not yet known, because inference isn't complete. | |
328 | /// 2. The closure kind for `C` *is* known, but doesn't match what is needed. | |
329 | /// For example, `C` may be a `FnOnce` closure, but a `Fn` closure is needed. | |
330 | /// | |
331 | /// In either case, we always know what argument types are | |
332 | /// expected by `C`, no matter what kind of `Fn` trait it | |
333 | /// eventually matches. So we can go ahead and unify the argument | |
334 | /// types, even though the end result is ambiguous. | |
335 | /// | |
336 | /// Note that this is safe *even if* the trait would never be | |
337 | /// matched (case 2 above). After all, in that case, an error will | |
338 | /// result, so it kind of doesn't matter what we do --- unifying | |
339 | /// the argument types can only be helpful to the user, because | |
340 | /// once they patch up the kind of closure that is expected, the | |
341 | /// argment types won't really change. | |
342 | fn consider_unification_despite_ambiguity(&mut self, obligation: &TraitObligation<'tcx>) { | |
343 | // Is this a `C : FnFoo(...)` trait reference for some trait binding `FnFoo`? | |
344 | match self.tcx().lang_items.fn_trait_kind(obligation.predicate.0.def_id()) { | |
345 | Some(_) => { } | |
346 | None => { return; } | |
347 | } | |
348 | ||
349 | // Is the self-type a closure type? We ignore bindings here | |
350 | // because if it is a closure type, it must be a closure type from | |
351 | // within this current fn, and hence none of the higher-ranked | |
352 | // lifetimes can appear inside the self-type. | |
c34b1796 | 353 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); |
85aaf69f | 354 | let (closure_def_id, substs) = match self_ty.sty { |
62682a34 | 355 | ty::TyClosure(id, ref substs) => (id, substs.clone()), |
85aaf69f SL |
356 | _ => { return; } |
357 | }; | |
358 | assert!(!substs.has_escaping_regions()); | |
359 | ||
62682a34 SL |
360 | // It is OK to call the unnormalized variant here - this is only |
361 | // reached for TyClosure: Fn inputs where the closure kind is | |
362 | // still unknown, which should only occur in typeck where the | |
363 | // closure type is already normalized. | |
364 | let closure_trait_ref = self.closure_trait_ref_unnormalized(obligation, | |
365 | closure_def_id, | |
366 | substs); | |
367 | ||
85aaf69f SL |
368 | match self.confirm_poly_trait_refs(obligation.cause.clone(), |
369 | obligation.predicate.to_poly_trait_ref(), | |
370 | closure_trait_ref) { | |
371 | Ok(()) => { } | |
372 | Err(_) => { /* Silently ignore errors. */ } | |
373 | } | |
374 | } | |
375 | ||
1a4d82fc JJ |
376 | /////////////////////////////////////////////////////////////////////////// |
377 | // EVALUATION | |
378 | // | |
379 | // Tests whether an obligation can be selected or whether an impl | |
380 | // can be applied to particular types. It skips the "confirmation" | |
381 | // step and hence completely ignores output type parameters. | |
382 | // | |
383 | // The result is "true" if the obligation *may* hold and "false" if | |
384 | // we can be sure it does not. | |
385 | ||
386 | /// Evaluates whether the obligation `obligation` can be satisfied (by any means). | |
387 | pub fn evaluate_obligation(&mut self, | |
388 | obligation: &PredicateObligation<'tcx>) | |
389 | -> bool | |
390 | { | |
62682a34 SL |
391 | debug!("evaluate_obligation({:?})", |
392 | obligation); | |
1a4d82fc | 393 | |
c34b1796 AL |
394 | self.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation) |
395 | .may_apply() | |
1a4d82fc JJ |
396 | } |
397 | ||
398 | fn evaluate_builtin_bound_recursively<'o>(&mut self, | |
399 | bound: ty::BuiltinBound, | |
400 | previous_stack: &TraitObligationStack<'o, 'tcx>, | |
401 | ty: Ty<'tcx>) | |
402 | -> EvaluationResult<'tcx> | |
403 | { | |
404 | let obligation = | |
405 | util::predicate_for_builtin_bound( | |
406 | self.tcx(), | |
407 | previous_stack.obligation.cause.clone(), | |
408 | bound, | |
409 | previous_stack.obligation.recursion_depth + 1, | |
410 | ty); | |
411 | ||
412 | match obligation { | |
413 | Ok(obligation) => { | |
c34b1796 | 414 | self.evaluate_predicate_recursively(previous_stack.list(), &obligation) |
1a4d82fc JJ |
415 | } |
416 | Err(ErrorReported) => { | |
417 | EvaluatedToOk | |
418 | } | |
419 | } | |
420 | } | |
421 | ||
422 | fn evaluate_predicates_recursively<'a,'o,I>(&mut self, | |
c34b1796 | 423 | stack: TraitObligationStackList<'o, 'tcx>, |
85aaf69f | 424 | predicates: I) |
1a4d82fc JJ |
425 | -> EvaluationResult<'tcx> |
426 | where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a | |
427 | { | |
428 | let mut result = EvaluatedToOk; | |
429 | for obligation in predicates { | |
430 | match self.evaluate_predicate_recursively(stack, obligation) { | |
431 | EvaluatedToErr(e) => { return EvaluatedToErr(e); } | |
432 | EvaluatedToAmbig => { result = EvaluatedToAmbig; } | |
433 | EvaluatedToOk => { } | |
434 | } | |
435 | } | |
436 | result | |
437 | } | |
438 | ||
439 | fn evaluate_predicate_recursively<'o>(&mut self, | |
c34b1796 | 440 | previous_stack: TraitObligationStackList<'o, 'tcx>, |
1a4d82fc JJ |
441 | obligation: &PredicateObligation<'tcx>) |
442 | -> EvaluationResult<'tcx> | |
443 | { | |
62682a34 SL |
444 | debug!("evaluate_predicate_recursively({:?})", |
445 | obligation); | |
446 | ||
447 | // Check the cache from the tcx of predicates that we know | |
448 | // have been proven elsewhere. This cache only contains | |
449 | // predicates that are global in scope and hence unaffected by | |
450 | // the current environment. | |
451 | if self.tcx().fulfilled_predicates.borrow().is_duplicate(&obligation.predicate) { | |
452 | return EvaluatedToOk; | |
453 | } | |
1a4d82fc JJ |
454 | |
455 | match obligation.predicate { | |
456 | ty::Predicate::Trait(ref t) => { | |
457 | assert!(!t.has_escaping_regions()); | |
458 | let obligation = obligation.with(t.clone()); | |
459 | self.evaluate_obligation_recursively(previous_stack, &obligation) | |
460 | } | |
461 | ||
462 | ty::Predicate::Equate(ref p) => { | |
463 | let result = self.infcx.probe(|_| { | |
464 | self.infcx.equality_predicate(obligation.cause.span, p) | |
465 | }); | |
466 | match result { | |
467 | Ok(()) => EvaluatedToOk, | |
468 | Err(_) => EvaluatedToErr(Unimplemented), | |
469 | } | |
470 | } | |
471 | ||
472 | ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => { | |
473 | // we do not consider region relationships when | |
474 | // evaluating trait matches | |
475 | EvaluatedToOk | |
476 | } | |
477 | ||
478 | ty::Predicate::Projection(ref data) => { | |
479 | self.infcx.probe(|_| { | |
480 | let project_obligation = obligation.with(data.clone()); | |
481 | match project::poly_project_and_unify_type(self, &project_obligation) { | |
482 | Ok(Some(subobligations)) => { | |
483 | self.evaluate_predicates_recursively(previous_stack, | |
484 | subobligations.iter()) | |
485 | } | |
486 | Ok(None) => { | |
487 | EvaluatedToAmbig | |
488 | } | |
489 | Err(_) => { | |
490 | EvaluatedToErr(Unimplemented) | |
491 | } | |
492 | } | |
493 | }) | |
494 | } | |
495 | } | |
496 | } | |
497 | ||
498 | fn evaluate_obligation_recursively<'o>(&mut self, | |
c34b1796 | 499 | previous_stack: TraitObligationStackList<'o, 'tcx>, |
1a4d82fc JJ |
500 | obligation: &TraitObligation<'tcx>) |
501 | -> EvaluationResult<'tcx> | |
502 | { | |
62682a34 SL |
503 | debug!("evaluate_obligation_recursively({:?})", |
504 | obligation); | |
1a4d82fc | 505 | |
c34b1796 | 506 | let stack = self.push_stack(previous_stack, obligation); |
1a4d82fc JJ |
507 | |
508 | let result = self.evaluate_stack(&stack); | |
509 | ||
510 | debug!("result: {:?}", result); | |
511 | result | |
512 | } | |
513 | ||
514 | fn evaluate_stack<'o>(&mut self, | |
515 | stack: &TraitObligationStack<'o, 'tcx>) | |
516 | -> EvaluationResult<'tcx> | |
517 | { | |
518 | // In intercrate mode, whenever any of the types are unbound, | |
519 | // there can always be an impl. Even if there are no impls in | |
520 | // this crate, perhaps the type would be unified with | |
521 | // something from another crate that does provide an impl. | |
522 | // | |
523 | // In intracrate mode, we must still be conservative. The reason is | |
524 | // that we want to avoid cycles. Imagine an impl like: | |
525 | // | |
526 | // impl<T:Eq> Eq for Vec<T> | |
527 | // | |
528 | // and a trait reference like `$0 : Eq` where `$0` is an | |
529 | // unbound variable. When we evaluate this trait-reference, we | |
530 | // will unify `$0` with `Vec<$1>` (for some fresh variable | |
531 | // `$1`), on the condition that `$1 : Eq`. We will then wind | |
532 | // up with many candidates (since that are other `Eq` impls | |
533 | // that apply) and try to winnow things down. This results in | |
534 | // a recursive evaluation that `$1 : Eq` -- as you can | |
535 | // imagine, this is just where we started. To avoid that, we | |
536 | // check for unbound variables and return an ambiguous (hence possible) | |
537 | // match if we've seen this trait before. | |
538 | // | |
539 | // This suffices to allow chains like `FnMut` implemented in | |
540 | // terms of `Fn` etc, but we could probably make this more | |
541 | // precise still. | |
542 | let input_types = stack.fresh_trait_ref.0.input_types(); | |
543 | let unbound_input_types = input_types.iter().any(|&t| ty::type_is_fresh(t)); | |
544 | if | |
545 | unbound_input_types && | |
546 | (self.intercrate || | |
547 | stack.iter().skip(1).any( | |
c34b1796 AL |
548 | |prev| self.match_fresh_trait_refs(&stack.fresh_trait_ref, |
549 | &prev.fresh_trait_ref))) | |
1a4d82fc | 550 | { |
62682a34 SL |
551 | debug!("evaluate_stack({:?}) --> unbound argument, recursion --> ambiguous", |
552 | stack.fresh_trait_ref); | |
1a4d82fc JJ |
553 | return EvaluatedToAmbig; |
554 | } | |
555 | ||
556 | // If there is any previous entry on the stack that precisely | |
557 | // matches this obligation, then we can assume that the | |
558 | // obligation is satisfied for now (still all other conditions | |
559 | // must be met of course). One obvious case this comes up is | |
560 | // marker traits like `Send`. Think of a linked list: | |
561 | // | |
562 | // struct List<T> { data: T, next: Option<Box<List<T>>> { | |
563 | // | |
564 | // `Box<List<T>>` will be `Send` if `T` is `Send` and | |
565 | // `Option<Box<List<T>>>` is `Send`, and in turn | |
566 | // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is | |
567 | // `Send`. | |
568 | // | |
569 | // Note that we do this comparison using the `fresh_trait_ref` | |
570 | // fields. Because these have all been skolemized using | |
571 | // `self.freshener`, we can be sure that (a) this will not | |
572 | // affect the inferencer state and (b) that if we see two | |
573 | // skolemized types with the same index, they refer to the | |
574 | // same unbound type variable. | |
575 | if | |
576 | stack.iter() | |
577 | .skip(1) // skip top-most frame | |
578 | .any(|prev| stack.fresh_trait_ref == prev.fresh_trait_ref) | |
579 | { | |
62682a34 SL |
580 | debug!("evaluate_stack({:?}) --> recursive", |
581 | stack.fresh_trait_ref); | |
1a4d82fc JJ |
582 | return EvaluatedToOk; |
583 | } | |
584 | ||
585 | match self.candidate_from_obligation(stack) { | |
586 | Ok(Some(c)) => self.winnow_candidate(stack, &c), | |
587 | Ok(None) => EvaluatedToAmbig, | |
588 | Err(e) => EvaluatedToErr(e), | |
589 | } | |
590 | } | |
591 | ||
592 | /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type | |
593 | /// `obligation_self_ty`. This can be used either for trait or inherent impls. | |
594 | pub fn evaluate_impl(&mut self, | |
595 | impl_def_id: ast::DefId, | |
596 | obligation: &TraitObligation<'tcx>) | |
597 | -> bool | |
598 | { | |
62682a34 SL |
599 | debug!("evaluate_impl(impl_def_id={:?}, obligation={:?})", |
600 | impl_def_id, | |
601 | obligation); | |
1a4d82fc JJ |
602 | |
603 | self.infcx.probe(|snapshot| { | |
d9579d0f AL |
604 | match self.match_impl(impl_def_id, obligation, snapshot) { |
605 | Ok((substs, skol_map)) => { | |
1a4d82fc JJ |
606 | let vtable_impl = self.vtable_impl(impl_def_id, |
607 | substs, | |
608 | obligation.cause.clone(), | |
609 | obligation.recursion_depth + 1, | |
610 | skol_map, | |
611 | snapshot); | |
c34b1796 AL |
612 | self.winnow_selection(TraitObligationStackList::empty(), |
613 | VtableImpl(vtable_impl)).may_apply() | |
1a4d82fc JJ |
614 | } |
615 | Err(()) => { | |
616 | false | |
617 | } | |
618 | } | |
619 | }) | |
620 | } | |
621 | ||
622 | /////////////////////////////////////////////////////////////////////////// | |
623 | // CANDIDATE ASSEMBLY | |
624 | // | |
625 | // The selection process begins by examining all in-scope impls, | |
626 | // caller obligations, and so forth and assembling a list of | |
c34b1796 AL |
627 | // candidates. See `README.md` and the `Candidate` type for more |
628 | // details. | |
1a4d82fc JJ |
629 | |
630 | fn candidate_from_obligation<'o>(&mut self, | |
631 | stack: &TraitObligationStack<'o, 'tcx>) | |
632 | -> SelectionResult<'tcx, SelectionCandidate<'tcx>> | |
633 | { | |
634 | // Watch out for overflow. This intentionally bypasses (and does | |
635 | // not update) the cache. | |
636 | let recursion_limit = self.infcx.tcx.sess.recursion_limit.get(); | |
637 | if stack.obligation.recursion_depth >= recursion_limit { | |
c34b1796 | 638 | report_overflow_error(self.infcx(), &stack.obligation); |
1a4d82fc JJ |
639 | } |
640 | ||
641 | // Check the cache. Note that we skolemize the trait-ref | |
642 | // separately rather than using `stack.fresh_trait_ref` -- this | |
643 | // is because we want the unbound variables to be replaced | |
644 | // with fresh skolemized types starting from index 0. | |
645 | let cache_fresh_trait_pred = | |
646 | self.infcx.freshen(stack.obligation.predicate.clone()); | |
62682a34 SL |
647 | debug!("candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})", |
648 | cache_fresh_trait_pred, | |
649 | stack); | |
1a4d82fc JJ |
650 | assert!(!stack.obligation.predicate.has_escaping_regions()); |
651 | ||
652 | match self.check_candidate_cache(&cache_fresh_trait_pred) { | |
653 | Some(c) => { | |
62682a34 SL |
654 | debug!("CACHE HIT: cache_fresh_trait_pred={:?}, candidate={:?}", |
655 | cache_fresh_trait_pred, | |
656 | c); | |
1a4d82fc JJ |
657 | return c; |
658 | } | |
659 | None => { } | |
660 | } | |
661 | ||
662 | // If no match, compute result and insert into cache. | |
663 | let candidate = self.candidate_from_obligation_no_cache(stack); | |
85aaf69f SL |
664 | |
665 | if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) { | |
62682a34 SL |
666 | debug!("CACHE MISS: cache_fresh_trait_pred={:?}, candidate={:?}", |
667 | cache_fresh_trait_pred, candidate); | |
85aaf69f SL |
668 | self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone()); |
669 | } | |
670 | ||
1a4d82fc JJ |
671 | candidate |
672 | } | |
673 | ||
674 | fn candidate_from_obligation_no_cache<'o>(&mut self, | |
675 | stack: &TraitObligationStack<'o, 'tcx>) | |
676 | -> SelectionResult<'tcx, SelectionCandidate<'tcx>> | |
677 | { | |
678 | if ty::type_is_error(stack.obligation.predicate.0.self_ty()) { | |
679 | return Ok(Some(ErrorCandidate)); | |
680 | } | |
681 | ||
c34b1796 AL |
682 | if !self.is_knowable(stack) { |
683 | debug!("intercrate not knowable"); | |
684 | return Ok(None); | |
685 | } | |
686 | ||
1a4d82fc JJ |
687 | let candidate_set = try!(self.assemble_candidates(stack)); |
688 | ||
689 | if candidate_set.ambiguous { | |
690 | debug!("candidate set contains ambig"); | |
691 | return Ok(None); | |
692 | } | |
693 | ||
694 | let mut candidates = candidate_set.vec; | |
695 | ||
62682a34 | 696 | debug!("assembled {} candidates for {:?}: {:?}", |
1a4d82fc | 697 | candidates.len(), |
62682a34 SL |
698 | stack, |
699 | candidates); | |
1a4d82fc JJ |
700 | |
701 | // At this point, we know that each of the entries in the | |
702 | // candidate set is *individually* applicable. Now we have to | |
703 | // figure out if they contain mutual incompatibilities. This | |
704 | // frequently arises if we have an unconstrained input type -- | |
705 | // for example, we are looking for $0:Eq where $0 is some | |
706 | // unconstrained type variable. In that case, we'll get a | |
707 | // candidate which assumes $0 == int, one that assumes $0 == | |
c34b1796 | 708 | // usize, etc. This spells an ambiguity. |
1a4d82fc JJ |
709 | |
710 | // If there is more than one candidate, first winnow them down | |
711 | // by considering extra conditions (nested obligations and so | |
712 | // forth). We don't winnow if there is exactly one | |
713 | // candidate. This is a relatively minor distinction but it | |
714 | // can lead to better inference and error-reporting. An | |
715 | // example would be if there was an impl: | |
716 | // | |
717 | // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } } | |
718 | // | |
719 | // and we were to see some code `foo.push_clone()` where `boo` | |
720 | // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If | |
721 | // we were to winnow, we'd wind up with zero candidates. | |
722 | // Instead, we select the right impl now but report `Bar does | |
723 | // not implement Clone`. | |
724 | if candidates.len() > 1 { | |
725 | candidates.retain(|c| self.winnow_candidate(stack, c).may_apply()) | |
726 | } | |
727 | ||
728 | // If there are STILL multiple candidate, we can further reduce | |
729 | // the list by dropping duplicates. | |
730 | if candidates.len() > 1 { | |
731 | let mut i = 0; | |
732 | while i < candidates.len() { | |
733 | let is_dup = | |
85aaf69f | 734 | (0..candidates.len()) |
1a4d82fc | 735 | .filter(|&j| i != j) |
85aaf69f | 736 | .any(|j| self.candidate_should_be_dropped_in_favor_of(&candidates[i], |
1a4d82fc JJ |
737 | &candidates[j])); |
738 | if is_dup { | |
62682a34 SL |
739 | debug!("Dropping candidate #{}/{}: {:?}", |
740 | i, candidates.len(), candidates[i]); | |
1a4d82fc JJ |
741 | candidates.swap_remove(i); |
742 | } else { | |
62682a34 SL |
743 | debug!("Retaining candidate #{}/{}: {:?}", |
744 | i, candidates.len(), candidates[i]); | |
1a4d82fc JJ |
745 | i += 1; |
746 | } | |
747 | } | |
748 | } | |
749 | ||
750 | // If there are *STILL* multiple candidates, give up and | |
751 | // report ambiguity. | |
752 | if candidates.len() > 1 { | |
753 | debug!("multiple matches, ambig"); | |
754 | return Ok(None); | |
755 | } | |
756 | ||
85aaf69f | 757 | |
1a4d82fc JJ |
758 | // If there are *NO* candidates, that there are no impls -- |
759 | // that we know of, anyway. Note that in the case where there | |
760 | // are unbound type variables within the obligation, it might | |
761 | // be the case that you could still satisfy the obligation | |
762 | // from another crate by instantiating the type variables with | |
763 | // a type from another crate that does have an impl. This case | |
764 | // is checked for in `evaluate_stack` (and hence users | |
765 | // who might care about this case, like coherence, should use | |
766 | // that function). | |
9346a6ac | 767 | if candidates.is_empty() { |
1a4d82fc JJ |
768 | return Err(Unimplemented); |
769 | } | |
770 | ||
771 | // Just one candidate left. | |
772 | let candidate = candidates.pop().unwrap(); | |
85aaf69f SL |
773 | |
774 | match candidate { | |
775 | ImplCandidate(def_id) => { | |
776 | match ty::trait_impl_polarity(self.tcx(), def_id) { | |
777 | Some(ast::ImplPolarity::Negative) => return Err(Unimplemented), | |
778 | _ => {} | |
779 | } | |
780 | } | |
781 | _ => {} | |
782 | } | |
783 | ||
1a4d82fc JJ |
784 | Ok(Some(candidate)) |
785 | } | |
786 | ||
c34b1796 AL |
787 | fn is_knowable<'o>(&mut self, |
788 | stack: &TraitObligationStack<'o, 'tcx>) | |
789 | -> bool | |
790 | { | |
791 | debug!("is_knowable(intercrate={})", self.intercrate); | |
792 | ||
793 | if !self.intercrate { | |
794 | return true; | |
795 | } | |
796 | ||
797 | let obligation = &stack.obligation; | |
798 | let predicate = self.infcx().resolve_type_vars_if_possible(&obligation.predicate); | |
799 | ||
800 | // ok to skip binder because of the nature of the | |
801 | // trait-ref-is-knowable check, which does not care about | |
802 | // bound regions | |
803 | let trait_ref = &predicate.skip_binder().trait_ref; | |
804 | ||
805 | coherence::trait_ref_is_knowable(self.tcx(), trait_ref) | |
806 | } | |
807 | ||
85aaf69f SL |
808 | fn pick_candidate_cache(&self) -> &SelectionCache<'tcx> { |
809 | // If there are any where-clauses in scope, then we always use | |
810 | // a cache local to this particular scope. Otherwise, we | |
811 | // switch to a global cache. We used to try and draw | |
812 | // finer-grained distinctions, but that led to a serious of | |
813 | // annoying and weird bugs like #22019 and #18290. This simple | |
814 | // rule seems to be pretty clearly safe and also still retains | |
815 | // a very high hit rate (~95% when compiling rustc). | |
816 | if !self.param_env().caller_bounds.is_empty() { | |
817 | return &self.param_env().selection_cache; | |
818 | } | |
1a4d82fc JJ |
819 | |
820 | // Avoid using the master cache during coherence and just rely | |
821 | // on the local cache. This effectively disables caching | |
822 | // during coherence. It is really just a simplification to | |
823 | // avoid us having to fear that coherence results "pollute" | |
824 | // the master cache. Since coherence executes pretty quickly, | |
825 | // it's not worth going to more trouble to increase the | |
826 | // hit-rate I don't think. | |
827 | if self.intercrate { | |
828 | return &self.param_env().selection_cache; | |
829 | } | |
830 | ||
1a4d82fc JJ |
831 | // Otherwise, we can use the global cache. |
832 | &self.tcx().selection_cache | |
833 | } | |
834 | ||
835 | fn check_candidate_cache(&mut self, | |
836 | cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>) | |
837 | -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>> | |
838 | { | |
85aaf69f | 839 | let cache = self.pick_candidate_cache(); |
1a4d82fc | 840 | let hashmap = cache.hashmap.borrow(); |
85aaf69f | 841 | hashmap.get(&cache_fresh_trait_pred.0.trait_ref).cloned() |
1a4d82fc JJ |
842 | } |
843 | ||
844 | fn insert_candidate_cache(&mut self, | |
845 | cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, | |
846 | candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>) | |
847 | { | |
85aaf69f | 848 | let cache = self.pick_candidate_cache(); |
1a4d82fc JJ |
849 | let mut hashmap = cache.hashmap.borrow_mut(); |
850 | hashmap.insert(cache_fresh_trait_pred.0.trait_ref.clone(), candidate); | |
851 | } | |
852 | ||
85aaf69f SL |
853 | fn should_update_candidate_cache(&mut self, |
854 | cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>, | |
855 | candidate: &SelectionResult<'tcx, SelectionCandidate<'tcx>>) | |
856 | -> bool | |
857 | { | |
858 | // In general, it's a good idea to cache results, even | |
859 | // ambiguous ones, to save us some trouble later. But we have | |
860 | // to be careful not to cache results that could be | |
861 | // invalidated later by advances in inference. Normally, this | |
862 | // is not an issue, because any inference variables whose | |
863 | // types are not yet bound are "freshened" in the cache key, | |
864 | // which means that if we later get the same request once that | |
865 | // type variable IS bound, we'll have a different cache key. | |
866 | // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is | |
867 | // not yet known, we may cache the result as `None`. But if | |
868 | // later `_#0t` is bound to `Bar`, then when we freshen we'll | |
869 | // have `Vec<Bar> : Foo` as the cache key. | |
870 | // | |
871 | // HOWEVER, it CAN happen that we get an ambiguity result in | |
872 | // one particular case around closures where the cache key | |
873 | // would not change. That is when the precise types of the | |
874 | // upvars that a closure references have not yet been figured | |
875 | // out (i.e., because it is not yet known if they are captured | |
876 | // by ref, and if by ref, what kind of ref). In these cases, | |
877 | // when matching a builtin bound, we will yield back an | |
878 | // ambiguous result. But the *cache key* is just the closure type, | |
879 | // it doesn't capture the state of the upvar computation. | |
880 | // | |
881 | // To avoid this trap, just don't cache ambiguous results if | |
882 | // the self-type contains no inference byproducts (that really | |
883 | // shouldn't happen in other circumstances anyway, given | |
884 | // coherence). | |
885 | ||
886 | match *candidate { | |
887 | Ok(Some(_)) | Err(_) => true, | |
888 | Ok(None) => { | |
889 | cache_fresh_trait_pred.0.input_types().iter().any(|&t| ty::type_has_ty_infer(t)) | |
890 | } | |
891 | } | |
892 | } | |
893 | ||
1a4d82fc JJ |
894 | fn assemble_candidates<'o>(&mut self, |
895 | stack: &TraitObligationStack<'o, 'tcx>) | |
896 | -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> | |
897 | { | |
1a4d82fc JJ |
898 | let TraitObligationStack { obligation, .. } = *stack; |
899 | ||
900 | let mut candidates = SelectionCandidateSet { | |
901 | vec: Vec::new(), | |
902 | ambiguous: false | |
903 | }; | |
904 | ||
905 | // Other bounds. Consider both in-scope bounds from fn decl | |
906 | // and applicable impls. There is a certain set of precedence rules here. | |
907 | ||
908 | match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) { | |
909 | Some(ty::BoundCopy) => { | |
62682a34 SL |
910 | debug!("obligation self ty is {:?}", |
911 | obligation.predicate.0.self_ty()); | |
1a4d82fc | 912 | |
c34b1796 AL |
913 | // User-defined copy impls are permitted, but only for |
914 | // structs and enums. | |
85aaf69f | 915 | try!(self.assemble_candidates_from_impls(obligation, &mut candidates)); |
1a4d82fc | 916 | |
c34b1796 | 917 | // For other types, we'll use the builtin rules. |
1a4d82fc JJ |
918 | try!(self.assemble_builtin_bound_candidates(ty::BoundCopy, |
919 | stack, | |
920 | &mut candidates)); | |
921 | } | |
1a4d82fc | 922 | Some(bound @ ty::BoundSized) => { |
c34b1796 AL |
923 | // Sized is never implementable by end-users, it is |
924 | // always automatically computed. | |
1a4d82fc JJ |
925 | try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates)); |
926 | } | |
927 | ||
d9579d0f AL |
928 | None if self.tcx().lang_items.unsize_trait() == |
929 | Some(obligation.predicate.def_id()) => { | |
930 | self.assemble_candidates_for_unsizing(obligation, &mut candidates); | |
931 | } | |
932 | ||
c34b1796 AL |
933 | Some(ty::BoundSend) | |
934 | Some(ty::BoundSync) | | |
1a4d82fc | 935 | None => { |
85aaf69f | 936 | try!(self.assemble_closure_candidates(obligation, &mut candidates)); |
1a4d82fc | 937 | try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates)); |
85aaf69f | 938 | try!(self.assemble_candidates_from_impls(obligation, &mut candidates)); |
1a4d82fc JJ |
939 | self.assemble_candidates_from_object_ty(obligation, &mut candidates); |
940 | } | |
941 | } | |
942 | ||
943 | self.assemble_candidates_from_projected_tys(obligation, &mut candidates); | |
85aaf69f | 944 | try!(self.assemble_candidates_from_caller_bounds(stack, &mut candidates)); |
c34b1796 AL |
945 | // Default implementations have lower priority, so we only |
946 | // consider triggering a default if there is no other impl that can apply. | |
9346a6ac | 947 | if candidates.vec.is_empty() { |
c34b1796 AL |
948 | try!(self.assemble_candidates_from_default_impls(obligation, &mut candidates)); |
949 | } | |
1a4d82fc JJ |
950 | debug!("candidate list size: {}", candidates.vec.len()); |
951 | Ok(candidates) | |
952 | } | |
953 | ||
954 | fn assemble_candidates_from_projected_tys(&mut self, | |
955 | obligation: &TraitObligation<'tcx>, | |
956 | candidates: &mut SelectionCandidateSet<'tcx>) | |
957 | { | |
958 | let poly_trait_predicate = | |
959 | self.infcx().resolve_type_vars_if_possible(&obligation.predicate); | |
960 | ||
62682a34 SL |
961 | debug!("assemble_candidates_for_projected_tys({:?},{:?})", |
962 | obligation, | |
963 | poly_trait_predicate); | |
1a4d82fc JJ |
964 | |
965 | // FIXME(#20297) -- just examining the self-type is very simplistic | |
966 | ||
967 | // before we go into the whole skolemization thing, just | |
968 | // quickly check if the self-type is a projection at all. | |
969 | let trait_def_id = match poly_trait_predicate.0.trait_ref.self_ty().sty { | |
62682a34 SL |
970 | ty::TyProjection(ref data) => data.trait_ref.def_id, |
971 | ty::TyInfer(ty::TyVar(_)) => { | |
1a4d82fc JJ |
972 | // If the self-type is an inference variable, then it MAY wind up |
973 | // being a projected type, so induce an ambiguity. | |
974 | // | |
975 | // FIXME(#20297) -- being strict about this can cause | |
976 | // inference failures with BorrowFrom, which is | |
977 | // unfortunate. Can we do better here? | |
85aaf69f | 978 | debug!("assemble_candidates_for_projected_tys: ambiguous self-type"); |
1a4d82fc JJ |
979 | candidates.ambiguous = true; |
980 | return; | |
981 | } | |
982 | _ => { return; } | |
983 | }; | |
984 | ||
62682a34 SL |
985 | debug!("assemble_candidates_for_projected_tys: trait_def_id={:?}", |
986 | trait_def_id); | |
1a4d82fc JJ |
987 | |
988 | let result = self.infcx.probe(|snapshot| { | |
989 | self.match_projection_obligation_against_bounds_from_trait(obligation, | |
990 | snapshot) | |
991 | }); | |
992 | ||
993 | if result { | |
994 | candidates.vec.push(ProjectionCandidate); | |
995 | } | |
996 | } | |
997 | ||
998 | fn match_projection_obligation_against_bounds_from_trait( | |
999 | &mut self, | |
1000 | obligation: &TraitObligation<'tcx>, | |
1001 | snapshot: &infer::CombinedSnapshot) | |
1002 | -> bool | |
1003 | { | |
1004 | let poly_trait_predicate = | |
1005 | self.infcx().resolve_type_vars_if_possible(&obligation.predicate); | |
1006 | let (skol_trait_predicate, skol_map) = | |
1007 | self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot); | |
1008 | debug!("match_projection_obligation_against_bounds_from_trait: \ | |
62682a34 SL |
1009 | skol_trait_predicate={:?} skol_map={:?}", |
1010 | skol_trait_predicate, | |
1011 | skol_map); | |
1a4d82fc JJ |
1012 | |
1013 | let projection_trait_ref = match skol_trait_predicate.trait_ref.self_ty().sty { | |
62682a34 | 1014 | ty::TyProjection(ref data) => &data.trait_ref, |
1a4d82fc JJ |
1015 | _ => { |
1016 | self.tcx().sess.span_bug( | |
1017 | obligation.cause.span, | |
85aaf69f | 1018 | &format!("match_projection_obligation_against_bounds_from_trait() called \ |
62682a34 SL |
1019 | but self-ty not a projection: {:?}", |
1020 | skol_trait_predicate.trait_ref.self_ty())); | |
1a4d82fc JJ |
1021 | } |
1022 | }; | |
1023 | debug!("match_projection_obligation_against_bounds_from_trait: \ | |
62682a34 SL |
1024 | projection_trait_ref={:?}", |
1025 | projection_trait_ref); | |
1a4d82fc | 1026 | |
85aaf69f SL |
1027 | let trait_predicates = ty::lookup_predicates(self.tcx(), projection_trait_ref.def_id); |
1028 | let bounds = trait_predicates.instantiate(self.tcx(), projection_trait_ref.substs); | |
1a4d82fc | 1029 | debug!("match_projection_obligation_against_bounds_from_trait: \ |
62682a34 SL |
1030 | bounds={:?}", |
1031 | bounds); | |
1a4d82fc JJ |
1032 | |
1033 | let matching_bound = | |
1034 | util::elaborate_predicates(self.tcx(), bounds.predicates.into_vec()) | |
1035 | .filter_to_traits() | |
1036 | .find( | |
1037 | |bound| self.infcx.probe( | |
1038 | |_| self.match_projection(obligation, | |
1039 | bound.clone(), | |
1040 | skol_trait_predicate.trait_ref.clone(), | |
1041 | &skol_map, | |
1042 | snapshot))); | |
1043 | ||
1044 | debug!("match_projection_obligation_against_bounds_from_trait: \ | |
62682a34 SL |
1045 | matching_bound={:?}", |
1046 | matching_bound); | |
1a4d82fc JJ |
1047 | match matching_bound { |
1048 | None => false, | |
1049 | Some(bound) => { | |
1050 | // Repeat the successful match, if any, this time outside of a probe. | |
1051 | let result = self.match_projection(obligation, | |
1052 | bound, | |
1053 | skol_trait_predicate.trait_ref.clone(), | |
1054 | &skol_map, | |
1055 | snapshot); | |
1056 | assert!(result); | |
1057 | true | |
1058 | } | |
1059 | } | |
1060 | } | |
1061 | ||
1062 | fn match_projection(&mut self, | |
1063 | obligation: &TraitObligation<'tcx>, | |
1064 | trait_bound: ty::PolyTraitRef<'tcx>, | |
d9579d0f | 1065 | skol_trait_ref: ty::TraitRef<'tcx>, |
1a4d82fc JJ |
1066 | skol_map: &infer::SkolemizationMap, |
1067 | snapshot: &infer::CombinedSnapshot) | |
1068 | -> bool | |
1069 | { | |
1070 | assert!(!skol_trait_ref.has_escaping_regions()); | |
1071 | let origin = infer::RelateOutputImplTypes(obligation.cause.span); | |
1072 | match self.infcx.sub_poly_trait_refs(false, | |
1073 | origin, | |
1074 | trait_bound.clone(), | |
1075 | ty::Binder(skol_trait_ref.clone())) { | |
1076 | Ok(()) => { } | |
1077 | Err(_) => { return false; } | |
1078 | } | |
1079 | ||
1080 | self.infcx.leak_check(skol_map, snapshot).is_ok() | |
1081 | } | |
1082 | ||
1083 | /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller | |
1084 | /// supplied to find out whether it is listed among them. | |
1085 | /// | |
1086 | /// Never affects inference environment. | |
85aaf69f SL |
1087 | fn assemble_candidates_from_caller_bounds<'o>(&mut self, |
1088 | stack: &TraitObligationStack<'o, 'tcx>, | |
1089 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1090 | -> Result<(),SelectionError<'tcx>> | |
1a4d82fc | 1091 | { |
62682a34 SL |
1092 | debug!("assemble_candidates_from_caller_bounds({:?})", |
1093 | stack.obligation); | |
1a4d82fc JJ |
1094 | |
1095 | let all_bounds = | |
62682a34 SL |
1096 | self.param_env().caller_bounds |
1097 | .iter() | |
1098 | .filter_map(|o| o.to_opt_poly_trait_ref()); | |
1a4d82fc JJ |
1099 | |
1100 | let matching_bounds = | |
1101 | all_bounds.filter( | |
85aaf69f | 1102 | |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply()); |
1a4d82fc JJ |
1103 | |
1104 | let param_candidates = | |
1105 | matching_bounds.map(|bound| ParamCandidate(bound)); | |
1106 | ||
1107 | candidates.vec.extend(param_candidates); | |
1108 | ||
1109 | Ok(()) | |
1110 | } | |
1111 | ||
85aaf69f SL |
1112 | fn evaluate_where_clause<'o>(&mut self, |
1113 | stack: &TraitObligationStack<'o, 'tcx>, | |
1114 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>) | |
1115 | -> EvaluationResult<'tcx> | |
1116 | { | |
1117 | self.infcx().probe(move |_| { | |
1118 | match self.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) { | |
1119 | Ok(obligations) => { | |
c34b1796 | 1120 | self.evaluate_predicates_recursively(stack.list(), obligations.iter()) |
85aaf69f SL |
1121 | } |
1122 | Err(()) => { | |
1123 | EvaluatedToErr(Unimplemented) | |
1124 | } | |
1125 | } | |
1126 | }) | |
1127 | } | |
1128 | ||
1a4d82fc | 1129 | /// Check for the artificial impl that the compiler will create for an obligation like `X : |
85aaf69f | 1130 | /// FnMut<..>` where `X` is a closure type. |
1a4d82fc | 1131 | /// |
85aaf69f | 1132 | /// Note: the type parameters on a closure candidate are modeled as *output* type |
1a4d82fc JJ |
1133 | /// parameters and hence do not affect whether this trait is a match or not. They will be |
1134 | /// unified during the confirmation step. | |
85aaf69f SL |
1135 | fn assemble_closure_candidates(&mut self, |
1136 | obligation: &TraitObligation<'tcx>, | |
1137 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1138 | -> Result<(),SelectionError<'tcx>> | |
1a4d82fc | 1139 | { |
85aaf69f | 1140 | let kind = match self.tcx().lang_items.fn_trait_kind(obligation.predicate.0.def_id()) { |
1a4d82fc JJ |
1141 | Some(k) => k, |
1142 | None => { return Ok(()); } | |
1143 | }; | |
1144 | ||
c34b1796 AL |
1145 | // ok to skip binder because the substs on closure types never |
1146 | // touch bound regions, they just capture the in-scope | |
1147 | // type/region parameters | |
1148 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); | |
1a4d82fc | 1149 | let (closure_def_id, substs) = match self_ty.sty { |
62682a34 SL |
1150 | ty::TyClosure(id, substs) => (id, substs), |
1151 | ty::TyInfer(ty::TyVar(_)) => { | |
85aaf69f | 1152 | debug!("assemble_unboxed_closure_candidates: ambiguous self-type"); |
1a4d82fc JJ |
1153 | candidates.ambiguous = true; |
1154 | return Ok(()); | |
1155 | } | |
1156 | _ => { return Ok(()); } | |
1157 | }; | |
1158 | ||
62682a34 SL |
1159 | debug!("assemble_unboxed_candidates: self_ty={:?} kind={:?} obligation={:?}", |
1160 | self_ty, | |
1a4d82fc | 1161 | kind, |
62682a34 | 1162 | obligation); |
1a4d82fc | 1163 | |
85aaf69f SL |
1164 | match self.closure_typer.closure_kind(closure_def_id) { |
1165 | Some(closure_kind) => { | |
1166 | debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind); | |
c34b1796 | 1167 | if closure_kind.extends(kind) { |
62682a34 SL |
1168 | candidates.vec.push(ClosureCandidate(closure_def_id, |
1169 | substs.clone())); | |
85aaf69f SL |
1170 | } |
1171 | } | |
1172 | None => { | |
1173 | debug!("assemble_unboxed_candidates: closure_kind not yet known"); | |
1174 | candidates.ambiguous = true; | |
1175 | } | |
1a4d82fc JJ |
1176 | } |
1177 | ||
1178 | Ok(()) | |
1179 | } | |
1180 | ||
1181 | /// Implement one of the `Fn()` family for a fn pointer. | |
1182 | fn assemble_fn_pointer_candidates(&mut self, | |
1183 | obligation: &TraitObligation<'tcx>, | |
1184 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1185 | -> Result<(),SelectionError<'tcx>> | |
1186 | { | |
c34b1796 AL |
1187 | // We provide impl of all fn traits for fn pointers. |
1188 | if self.tcx().lang_items.fn_trait_kind(obligation.predicate.def_id()).is_none() { | |
1a4d82fc JJ |
1189 | return Ok(()); |
1190 | } | |
1191 | ||
c34b1796 AL |
1192 | // ok to skip binder because what we are inspecting doesn't involve bound regions |
1193 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); | |
1a4d82fc | 1194 | match self_ty.sty { |
62682a34 | 1195 | ty::TyInfer(ty::TyVar(_)) => { |
85aaf69f | 1196 | debug!("assemble_fn_pointer_candidates: ambiguous self-type"); |
1a4d82fc JJ |
1197 | candidates.ambiguous = true; // could wind up being a fn() type |
1198 | } | |
1199 | ||
1200 | // provide an impl, but only for suitable `fn` pointers | |
62682a34 | 1201 | ty::TyBareFn(_, &ty::BareFnTy { |
1a4d82fc JJ |
1202 | unsafety: ast::Unsafety::Normal, |
1203 | abi: abi::Rust, | |
1204 | sig: ty::Binder(ty::FnSig { | |
1205 | inputs: _, | |
1206 | output: ty::FnConverging(_), | |
1207 | variadic: false | |
1208 | }) | |
1209 | }) => { | |
1210 | candidates.vec.push(FnPointerCandidate); | |
1211 | } | |
1212 | ||
1213 | _ => { } | |
1214 | } | |
1215 | ||
1216 | Ok(()) | |
1217 | } | |
1218 | ||
1219 | /// Search for impls that might apply to `obligation`. | |
1220 | fn assemble_candidates_from_impls(&mut self, | |
1221 | obligation: &TraitObligation<'tcx>, | |
85aaf69f | 1222 | candidates: &mut SelectionCandidateSet<'tcx>) |
1a4d82fc JJ |
1223 | -> Result<(), SelectionError<'tcx>> |
1224 | { | |
62682a34 | 1225 | debug!("assemble_candidates_from_impls(obligation={:?})", obligation); |
85aaf69f | 1226 | |
d9579d0f AL |
1227 | let def = ty::lookup_trait_def(self.tcx(), obligation.predicate.def_id()); |
1228 | ||
1229 | def.for_each_relevant_impl( | |
1230 | self.tcx(), | |
1231 | obligation.predicate.0.trait_ref.self_ty(), | |
1232 | |impl_def_id| { | |
1233 | self.infcx.probe(|snapshot| { | |
1234 | if let Ok(_) = self.match_impl(impl_def_id, obligation, snapshot) { | |
85aaf69f | 1235 | candidates.vec.push(ImplCandidate(impl_def_id)); |
1a4d82fc | 1236 | } |
d9579d0f AL |
1237 | }); |
1238 | } | |
1239 | ); | |
c34b1796 AL |
1240 | |
1241 | Ok(()) | |
1242 | } | |
1243 | ||
1244 | fn assemble_candidates_from_default_impls(&mut self, | |
1245 | obligation: &TraitObligation<'tcx>, | |
1246 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1247 | -> Result<(), SelectionError<'tcx>> | |
1248 | { | |
1249 | // OK to skip binder here because the tests we do below do not involve bound regions | |
1250 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); | |
62682a34 | 1251 | debug!("assemble_candidates_from_default_impls(self_ty={:?})", self_ty); |
c34b1796 AL |
1252 | |
1253 | let def_id = obligation.predicate.def_id(); | |
1254 | ||
1255 | if ty::trait_has_default_impl(self.tcx(), def_id) { | |
1256 | match self_ty.sty { | |
62682a34 | 1257 | ty::TyTrait(..) => { |
c34b1796 AL |
1258 | // For object types, we don't know what the closed |
1259 | // over types are. For most traits, this means we | |
1260 | // conservatively say nothing; a candidate may be | |
1261 | // added by `assemble_candidates_from_object_ty`. | |
1262 | // However, for the kind of magic reflect trait, | |
1263 | // we consider it to be implemented even for | |
1264 | // object types, because it just lets you reflect | |
1265 | // onto the object type, not into the object's | |
1266 | // interior. | |
1267 | if ty::has_attr(self.tcx(), def_id, "rustc_reflect_like") { | |
1268 | candidates.vec.push(DefaultImplObjectCandidate(def_id)); | |
1269 | } | |
1270 | } | |
62682a34 SL |
1271 | ty::TyParam(..) | |
1272 | ty::TyProjection(..) => { | |
c34b1796 AL |
1273 | // In these cases, we don't know what the actual |
1274 | // type is. Therefore, we cannot break it down | |
1275 | // into its constituent types. So we don't | |
1276 | // consider the `..` impl but instead just add no | |
1277 | // candidates: this means that typeck will only | |
1278 | // succeed if there is another reason to believe | |
1279 | // that this obligation holds. That could be a | |
1280 | // where-clause or, in the case of an object type, | |
1281 | // it could be that the object type lists the | |
1282 | // trait (e.g. `Foo+Send : Send`). See | |
1283 | // `compile-fail/typeck-default-trait-impl-send-param.rs` | |
1284 | // for an example of a test case that exercises | |
1285 | // this path. | |
1286 | } | |
62682a34 | 1287 | ty::TyInfer(ty::TyVar(_)) => { |
c34b1796 AL |
1288 | // the defaulted impl might apply, we don't know |
1289 | candidates.ambiguous = true; | |
1290 | } | |
1291 | _ => { | |
1292 | if self.constituent_types_for_ty(self_ty).is_some() { | |
1293 | candidates.vec.push(DefaultImplCandidate(def_id.clone())) | |
1294 | } else { | |
1295 | // We don't yet know what the constituent | |
1296 | // types are. So call it ambiguous for now, | |
1297 | // though this is a bit stronger than | |
1298 | // necessary: that is, we know that the | |
1299 | // defaulted impl applies, but we can't | |
1300 | // process the confirmation step without | |
1301 | // knowing the constituent types. (Anyway, in | |
1302 | // the particular case of defaulted impls, it | |
1303 | // doesn't really matter much either way, | |
1304 | // since we won't be aiding inference by | |
1305 | // processing the confirmation step.) | |
1306 | candidates.ambiguous = true; | |
1307 | } | |
1308 | } | |
1309 | } | |
1310 | } | |
1311 | ||
1a4d82fc JJ |
1312 | Ok(()) |
1313 | } | |
1314 | ||
1315 | /// Search for impls that might apply to `obligation`. | |
1316 | fn assemble_candidates_from_object_ty(&mut self, | |
1317 | obligation: &TraitObligation<'tcx>, | |
1318 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1319 | { | |
62682a34 SL |
1320 | debug!("assemble_candidates_from_object_ty(self_ty={:?})", |
1321 | self.infcx.shallow_resolve(*obligation.self_ty().skip_binder())); | |
1a4d82fc JJ |
1322 | |
1323 | // Object-safety candidates are only applicable to object-safe | |
1324 | // traits. Including this check is useful because it helps | |
1325 | // inference in cases of traits like `BorrowFrom`, which are | |
1326 | // not object-safe, and which rely on being able to infer the | |
1327 | // self-type from one of the other inputs. Without this check, | |
1328 | // these cases wind up being considered ambiguous due to a | |
1329 | // (spurious) ambiguity introduced here. | |
c34b1796 AL |
1330 | let predicate_trait_ref = obligation.predicate.to_poly_trait_ref(); |
1331 | if !object_safety::is_object_safe(self.tcx(), predicate_trait_ref.def_id()) { | |
1a4d82fc JJ |
1332 | return; |
1333 | } | |
1334 | ||
c34b1796 AL |
1335 | self.infcx.commit_if_ok(|snapshot| { |
1336 | let bound_self_ty = | |
1337 | self.infcx.resolve_type_vars_if_possible(&obligation.self_ty()); | |
1338 | let (self_ty, _) = | |
1339 | self.infcx().skolemize_late_bound_regions(&bound_self_ty, snapshot); | |
1340 | let poly_trait_ref = match self_ty.sty { | |
62682a34 | 1341 | ty::TyTrait(ref data) => { |
c34b1796 AL |
1342 | match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) { |
1343 | Some(bound @ ty::BoundSend) | Some(bound @ ty::BoundSync) => { | |
1344 | if data.bounds.builtin_bounds.contains(&bound) { | |
1345 | debug!("assemble_candidates_from_object_ty: matched builtin bound, \ | |
1346 | pushing candidate"); | |
1347 | candidates.vec.push(BuiltinObjectCandidate); | |
1348 | return Ok(()); | |
1349 | } | |
1350 | } | |
1351 | _ => {} | |
1352 | } | |
1a4d82fc | 1353 | |
c34b1796 AL |
1354 | data.principal_trait_ref_with_self_ty(self.tcx(), self_ty) |
1355 | } | |
62682a34 | 1356 | ty::TyInfer(ty::TyVar(_)) => { |
c34b1796 AL |
1357 | debug!("assemble_candidates_from_object_ty: ambiguous"); |
1358 | candidates.ambiguous = true; // could wind up being an object type | |
1359 | return Ok(()); | |
1360 | } | |
1361 | _ => { | |
1362 | return Ok(()); | |
1363 | } | |
1364 | }; | |
1a4d82fc | 1365 | |
62682a34 SL |
1366 | debug!("assemble_candidates_from_object_ty: poly_trait_ref={:?}", |
1367 | poly_trait_ref); | |
1a4d82fc | 1368 | |
c34b1796 AL |
1369 | // see whether the object trait can be upcast to the trait we are looking for |
1370 | let upcast_trait_refs = self.upcast(poly_trait_ref, obligation); | |
1371 | if upcast_trait_refs.len() > 1 { | |
1372 | // can be upcast in many ways; need more type information | |
1373 | candidates.ambiguous = true; | |
1374 | } else if upcast_trait_refs.len() == 1 { | |
1375 | candidates.vec.push(ObjectCandidate); | |
1376 | } | |
1a4d82fc | 1377 | |
c34b1796 AL |
1378 | Ok::<(),()>(()) |
1379 | }).unwrap(); | |
1a4d82fc JJ |
1380 | } |
1381 | ||
d9579d0f AL |
1382 | /// Search for unsizing that might apply to `obligation`. |
1383 | fn assemble_candidates_for_unsizing(&mut self, | |
1384 | obligation: &TraitObligation<'tcx>, | |
1385 | candidates: &mut SelectionCandidateSet<'tcx>) { | |
1386 | // We currently never consider higher-ranked obligations e.g. | |
1387 | // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not | |
1388 | // because they are a priori invalid, and we could potentially add support | |
1389 | // for them later, it's just that there isn't really a strong need for it. | |
1390 | // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>` | |
1391 | // impl, and those are generally applied to concrete types. | |
1392 | // | |
1393 | // That said, one might try to write a fn with a where clause like | |
1394 | // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>> | |
1395 | // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`. | |
1396 | // Still, you'd be more likely to write that where clause as | |
1397 | // T: Trait | |
1398 | // so it seems ok if we (conservatively) fail to accept that `Unsize` | |
1399 | // obligation above. Should be possible to extend this in the future. | |
1400 | let self_ty = match ty::no_late_bound_regions(self.tcx(), &obligation.self_ty()) { | |
1401 | Some(t) => t, | |
1402 | None => { | |
1403 | // Don't add any candidates if there are bound regions. | |
1404 | return; | |
1405 | } | |
1406 | }; | |
1407 | let source = self.infcx.shallow_resolve(self_ty); | |
1408 | let target = self.infcx.shallow_resolve(obligation.predicate.0.input_types()[0]); | |
1409 | ||
62682a34 SL |
1410 | debug!("assemble_candidates_for_unsizing(source={:?}, target={:?})", |
1411 | source, target); | |
d9579d0f AL |
1412 | |
1413 | let may_apply = match (&source.sty, &target.sty) { | |
1414 | // Trait+Kx+'a -> Trait+Ky+'b (upcasts). | |
62682a34 | 1415 | (&ty::TyTrait(ref data_a), &ty::TyTrait(ref data_b)) => { |
d9579d0f AL |
1416 | // Upcasts permit two things: |
1417 | // | |
1418 | // 1. Dropping builtin bounds, e.g. `Foo+Send` to `Foo` | |
1419 | // 2. Tightening the region bound, e.g. `Foo+'a` to `Foo+'b` if `'a : 'b` | |
1420 | // | |
1421 | // Note that neither of these changes requires any | |
1422 | // change at runtime. Eventually this will be | |
1423 | // generalized. | |
1424 | // | |
1425 | // We always upcast when we can because of reason | |
1426 | // #2 (region bounds). | |
1427 | data_a.principal.def_id() == data_a.principal.def_id() && | |
1428 | data_a.bounds.builtin_bounds.is_superset(&data_b.bounds.builtin_bounds) | |
1429 | } | |
1430 | ||
1431 | // T -> Trait. | |
62682a34 | 1432 | (_, &ty::TyTrait(_)) => true, |
d9579d0f AL |
1433 | |
1434 | // Ambiguous handling is below T -> Trait, because inference | |
1435 | // variables can still implement Unsize<Trait> and nested | |
1436 | // obligations will have the final say (likely deferred). | |
62682a34 SL |
1437 | (&ty::TyInfer(ty::TyVar(_)), _) | |
1438 | (_, &ty::TyInfer(ty::TyVar(_))) => { | |
d9579d0f AL |
1439 | debug!("assemble_candidates_for_unsizing: ambiguous"); |
1440 | candidates.ambiguous = true; | |
1441 | false | |
1442 | } | |
1443 | ||
1444 | // [T; n] -> [T]. | |
62682a34 | 1445 | (&ty::TyArray(_, _), &ty::TySlice(_)) => true, |
d9579d0f AL |
1446 | |
1447 | // Struct<T> -> Struct<U>. | |
62682a34 | 1448 | (&ty::TyStruct(def_id_a, _), &ty::TyStruct(def_id_b, _)) => { |
d9579d0f AL |
1449 | def_id_a == def_id_b |
1450 | } | |
1451 | ||
1452 | _ => false | |
1453 | }; | |
1454 | ||
1455 | if may_apply { | |
1456 | candidates.vec.push(BuiltinUnsizeCandidate); | |
1457 | } | |
1458 | } | |
1459 | ||
1a4d82fc JJ |
1460 | /////////////////////////////////////////////////////////////////////////// |
1461 | // WINNOW | |
1462 | // | |
1463 | // Winnowing is the process of attempting to resolve ambiguity by | |
1464 | // probing further. During the winnowing process, we unify all | |
1465 | // type variables (ignoring skolemization) and then we also | |
1466 | // attempt to evaluate recursive bounds to see if they are | |
1467 | // satisfied. | |
1468 | ||
1469 | /// Further evaluate `candidate` to decide whether all type parameters match and whether nested | |
1470 | /// obligations are met. Returns true if `candidate` remains viable after this further | |
1471 | /// scrutiny. | |
1472 | fn winnow_candidate<'o>(&mut self, | |
1473 | stack: &TraitObligationStack<'o, 'tcx>, | |
1474 | candidate: &SelectionCandidate<'tcx>) | |
1475 | -> EvaluationResult<'tcx> | |
1476 | { | |
62682a34 | 1477 | debug!("winnow_candidate: candidate={:?}", candidate); |
1a4d82fc JJ |
1478 | let result = self.infcx.probe(|_| { |
1479 | let candidate = (*candidate).clone(); | |
1480 | match self.confirm_candidate(stack.obligation, candidate) { | |
c34b1796 AL |
1481 | Ok(selection) => self.winnow_selection(stack.list(), |
1482 | selection), | |
1a4d82fc JJ |
1483 | Err(error) => EvaluatedToErr(error), |
1484 | } | |
1485 | }); | |
1486 | debug!("winnow_candidate depth={} result={:?}", | |
1487 | stack.obligation.recursion_depth, result); | |
1488 | result | |
1489 | } | |
1490 | ||
1491 | fn winnow_selection<'o>(&mut self, | |
c34b1796 | 1492 | stack: TraitObligationStackList<'o,'tcx>, |
1a4d82fc JJ |
1493 | selection: Selection<'tcx>) |
1494 | -> EvaluationResult<'tcx> | |
1495 | { | |
62682a34 SL |
1496 | self.evaluate_predicates_recursively(stack, |
1497 | selection.nested_obligations().iter()) | |
1a4d82fc JJ |
1498 | } |
1499 | ||
85aaf69f SL |
1500 | /// Returns true if `candidate_i` should be dropped in favor of |
1501 | /// `candidate_j`. Generally speaking we will drop duplicate | |
1502 | /// candidates and prefer where-clause candidates. | |
d9579d0f AL |
1503 | /// Returns true if `victim` should be dropped in favor of |
1504 | /// `other`. Generally speaking we will drop duplicate | |
1505 | /// candidates and prefer where-clause candidates. | |
1506 | /// | |
1507 | /// See the comment for "SelectionCandidate" for more details. | |
1a4d82fc | 1508 | fn candidate_should_be_dropped_in_favor_of<'o>(&mut self, |
d9579d0f AL |
1509 | victim: &SelectionCandidate<'tcx>, |
1510 | other: &SelectionCandidate<'tcx>) | |
1a4d82fc JJ |
1511 | -> bool |
1512 | { | |
d9579d0f | 1513 | if victim == other { |
85aaf69f SL |
1514 | return true; |
1515 | } | |
1516 | ||
d9579d0f AL |
1517 | match other { |
1518 | &ObjectCandidate(..) | | |
1519 | &ParamCandidate(_) | &ProjectionCandidate => match victim { | |
1520 | &DefaultImplCandidate(..) => { | |
1521 | self.tcx().sess.bug( | |
1522 | "default implementations shouldn't be recorded \ | |
1523 | when there are other valid candidates"); | |
1524 | } | |
1525 | &PhantomFnCandidate => { | |
1526 | self.tcx().sess.bug("PhantomFn didn't short-circuit selection"); | |
1527 | } | |
1528 | &ImplCandidate(..) | | |
1529 | &ClosureCandidate(..) | | |
1530 | &FnPointerCandidate(..) | | |
1531 | &BuiltinObjectCandidate(..) | | |
1532 | &BuiltinUnsizeCandidate(..) | | |
1533 | &DefaultImplObjectCandidate(..) | | |
1534 | &BuiltinCandidate(..) => { | |
1535 | // We have a where-clause so don't go around looking | |
1536 | // for impls. | |
1537 | true | |
1538 | } | |
1539 | &ObjectCandidate(..) | | |
1540 | &ProjectionCandidate => { | |
1541 | // Arbitrarily give param candidates priority | |
1542 | // over projection and object candidates. | |
1543 | true | |
1544 | }, | |
1545 | &ParamCandidate(..) => false, | |
1546 | &ErrorCandidate => false // propagate errors | |
1547 | }, | |
1548 | _ => false | |
1a4d82fc JJ |
1549 | } |
1550 | } | |
1551 | ||
1552 | /////////////////////////////////////////////////////////////////////////// | |
1553 | // BUILTIN BOUNDS | |
1554 | // | |
1555 | // These cover the traits that are built-in to the language | |
1556 | // itself. This includes `Copy` and `Sized` for sure. For the | |
1557 | // moment, it also includes `Send` / `Sync` and a few others, but | |
1558 | // those will hopefully change to library-defined traits in the | |
1559 | // future. | |
1560 | ||
1561 | fn assemble_builtin_bound_candidates<'o>(&mut self, | |
1562 | bound: ty::BuiltinBound, | |
1563 | stack: &TraitObligationStack<'o, 'tcx>, | |
1564 | candidates: &mut SelectionCandidateSet<'tcx>) | |
1565 | -> Result<(),SelectionError<'tcx>> | |
1566 | { | |
1567 | match self.builtin_bound(bound, stack.obligation) { | |
1568 | Ok(If(..)) => { | |
62682a34 SL |
1569 | debug!("builtin_bound: bound={:?}", |
1570 | bound); | |
1a4d82fc JJ |
1571 | candidates.vec.push(BuiltinCandidate(bound)); |
1572 | Ok(()) | |
1573 | } | |
1574 | Ok(ParameterBuiltin) => { Ok(()) } | |
85aaf69f SL |
1575 | Ok(AmbiguousBuiltin) => { |
1576 | debug!("assemble_builtin_bound_candidates: ambiguous builtin"); | |
1577 | Ok(candidates.ambiguous = true) | |
1578 | } | |
1a4d82fc JJ |
1579 | Err(e) => { Err(e) } |
1580 | } | |
1581 | } | |
1582 | ||
1583 | fn builtin_bound(&mut self, | |
1584 | bound: ty::BuiltinBound, | |
1585 | obligation: &TraitObligation<'tcx>) | |
1586 | -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>> | |
1587 | { | |
1588 | // Note: these tests operate on types that may contain bound | |
1589 | // regions. To be proper, we ought to skolemize here, but we | |
1590 | // forego the skolemization and defer it until the | |
1591 | // confirmation step. | |
1592 | ||
1593 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty()); | |
1594 | return match self_ty.sty { | |
62682a34 SL |
1595 | ty::TyInfer(ty::IntVar(_)) | |
1596 | ty::TyInfer(ty::FloatVar(_)) | | |
1597 | ty::TyUint(_) | | |
1598 | ty::TyInt(_) | | |
1599 | ty::TyBool | | |
1600 | ty::TyFloat(_) | | |
1601 | ty::TyBareFn(..) | | |
1602 | ty::TyChar => { | |
1a4d82fc | 1603 | // safe for everything |
c34b1796 | 1604 | ok_if(Vec::new()) |
1a4d82fc JJ |
1605 | } |
1606 | ||
62682a34 | 1607 | ty::TyBox(_) => { // Box<T> |
1a4d82fc | 1608 | match bound { |
c34b1796 | 1609 | ty::BoundCopy => Err(Unimplemented), |
1a4d82fc | 1610 | |
c34b1796 | 1611 | ty::BoundSized => ok_if(Vec::new()), |
1a4d82fc | 1612 | |
c34b1796 AL |
1613 | ty::BoundSync | ty::BoundSend => { |
1614 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1a4d82fc JJ |
1615 | } |
1616 | } | |
1617 | } | |
1618 | ||
62682a34 | 1619 | ty::TyRawPtr(..) => { // *const T, *mut T |
1a4d82fc | 1620 | match bound { |
c34b1796 | 1621 | ty::BoundCopy | ty::BoundSized => ok_if(Vec::new()), |
1a4d82fc | 1622 | |
c34b1796 AL |
1623 | ty::BoundSync | ty::BoundSend => { |
1624 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1a4d82fc JJ |
1625 | } |
1626 | } | |
1627 | } | |
1628 | ||
62682a34 | 1629 | ty::TyTrait(ref data) => { |
1a4d82fc | 1630 | match bound { |
c34b1796 AL |
1631 | ty::BoundSized => Err(Unimplemented), |
1632 | ty::BoundCopy => { | |
1a4d82fc | 1633 | if data.bounds.builtin_bounds.contains(&bound) { |
c34b1796 | 1634 | ok_if(Vec::new()) |
1a4d82fc JJ |
1635 | } else { |
1636 | // Recursively check all supertraits to find out if any further | |
1637 | // bounds are required and thus we must fulfill. | |
1638 | let principal = | |
1639 | data.principal_trait_ref_with_self_ty(self.tcx(), | |
1640 | self.tcx().types.err); | |
c34b1796 | 1641 | let desired_def_id = obligation.predicate.def_id(); |
1a4d82fc | 1642 | for tr in util::supertraits(self.tcx(), principal) { |
c34b1796 AL |
1643 | if tr.def_id() == desired_def_id { |
1644 | return ok_if(Vec::new()) | |
1a4d82fc JJ |
1645 | } |
1646 | } | |
1647 | ||
1648 | Err(Unimplemented) | |
1649 | } | |
1650 | } | |
c34b1796 AL |
1651 | ty::BoundSync | ty::BoundSend => { |
1652 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1653 | } | |
1a4d82fc JJ |
1654 | } |
1655 | } | |
1656 | ||
62682a34 | 1657 | ty::TyRef(_, ty::mt { ty: _, mutbl }) => { |
1a4d82fc JJ |
1658 | // &mut T or &T |
1659 | match bound { | |
1660 | ty::BoundCopy => { | |
1661 | match mutbl { | |
1662 | // &mut T is affine and hence never `Copy` | |
c34b1796 | 1663 | ast::MutMutable => Err(Unimplemented), |
1a4d82fc JJ |
1664 | |
1665 | // &T is always copyable | |
c34b1796 | 1666 | ast::MutImmutable => ok_if(Vec::new()), |
1a4d82fc JJ |
1667 | } |
1668 | } | |
1669 | ||
c34b1796 | 1670 | ty::BoundSized => ok_if(Vec::new()), |
1a4d82fc | 1671 | |
c34b1796 AL |
1672 | ty::BoundSync | ty::BoundSend => { |
1673 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1a4d82fc JJ |
1674 | } |
1675 | } | |
1676 | } | |
1677 | ||
62682a34 SL |
1678 | ty::TyArray(element_ty, _) => { |
1679 | // [T; n] | |
1a4d82fc | 1680 | match bound { |
62682a34 SL |
1681 | ty::BoundCopy => ok_if(vec![element_ty]), |
1682 | ty::BoundSized => ok_if(Vec::new()), | |
c34b1796 AL |
1683 | ty::BoundSync | ty::BoundSend => { |
1684 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1a4d82fc JJ |
1685 | } |
1686 | } | |
1687 | } | |
1688 | ||
62682a34 | 1689 | ty::TyStr | ty::TySlice(_) => { |
1a4d82fc | 1690 | match bound { |
c34b1796 AL |
1691 | ty::BoundSync | ty::BoundSend => { |
1692 | self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()"); | |
1a4d82fc JJ |
1693 | } |
1694 | ||
c34b1796 | 1695 | ty::BoundCopy | ty::BoundSized => Err(Unimplemented), |
1a4d82fc JJ |
1696 | } |
1697 | } | |
1698 | ||
c34b1796 | 1699 | // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet |
62682a34 | 1700 | ty::TyTuple(ref tys) => ok_if(tys.clone()), |
1a4d82fc | 1701 | |
62682a34 | 1702 | ty::TyClosure(def_id, substs) => { |
1a4d82fc JJ |
1703 | // FIXME -- This case is tricky. In the case of by-ref |
1704 | // closures particularly, we need the results of | |
1705 | // inference to decide how to reflect the type of each | |
1706 | // upvar (the upvar may have type `T`, but the runtime | |
1707 | // type could be `&mut`, `&`, or just `T`). For now, | |
1708 | // though, we'll do this unsoundly and assume that all | |
1709 | // captures are by value. Really what we ought to do | |
1710 | // is reserve judgement and then intertwine this | |
1711 | // analysis with closure inference. | |
1712 | assert_eq!(def_id.krate, ast::LOCAL_CRATE); | |
1713 | ||
1714 | // Unboxed closures shouldn't be | |
1715 | // implicitly copyable | |
1716 | if bound == ty::BoundCopy { | |
1717 | return Ok(ParameterBuiltin); | |
1718 | } | |
1719 | ||
85aaf69f SL |
1720 | // Upvars are always local variables or references to |
1721 | // local variables, and local variables cannot be | |
1722 | // unsized, so the closure struct as a whole must be | |
1723 | // Sized. | |
1724 | if bound == ty::BoundSized { | |
c34b1796 | 1725 | return ok_if(Vec::new()); |
85aaf69f SL |
1726 | } |
1727 | ||
1728 | match self.closure_typer.closure_upvars(def_id, substs) { | |
c34b1796 | 1729 | Some(upvars) => ok_if(upvars.iter().map(|c| c.ty).collect()), |
1a4d82fc | 1730 | None => { |
85aaf69f | 1731 | debug!("assemble_builtin_bound_candidates: no upvar types available yet"); |
1a4d82fc JJ |
1732 | Ok(AmbiguousBuiltin) |
1733 | } | |
1734 | } | |
1735 | } | |
1736 | ||
62682a34 | 1737 | ty::TyStruct(def_id, substs) => { |
1a4d82fc JJ |
1738 | let types: Vec<Ty> = |
1739 | ty::struct_fields(self.tcx(), def_id, substs).iter() | |
1740 | .map(|f| f.mt.ty) | |
1741 | .collect(); | |
c34b1796 | 1742 | nominal(bound, types) |
1a4d82fc JJ |
1743 | } |
1744 | ||
62682a34 | 1745 | ty::TyEnum(def_id, substs) => { |
1a4d82fc JJ |
1746 | let types: Vec<Ty> = |
1747 | ty::substd_enum_variants(self.tcx(), def_id, substs) | |
1748 | .iter() | |
62682a34 | 1749 | .flat_map(|variant| &variant.args) |
85aaf69f | 1750 | .cloned() |
1a4d82fc | 1751 | .collect(); |
c34b1796 | 1752 | nominal(bound, types) |
1a4d82fc JJ |
1753 | } |
1754 | ||
62682a34 | 1755 | ty::TyProjection(_) | ty::TyParam(_) => { |
1a4d82fc JJ |
1756 | // Note: A type parameter is only considered to meet a |
1757 | // particular bound if there is a where clause telling | |
1758 | // us that it does, and that case is handled by | |
1759 | // `assemble_candidates_from_caller_bounds()`. | |
1760 | Ok(ParameterBuiltin) | |
1761 | } | |
1762 | ||
62682a34 | 1763 | ty::TyInfer(ty::TyVar(_)) => { |
1a4d82fc JJ |
1764 | // Unbound type variable. Might or might not have |
1765 | // applicable impls and so forth, depending on what | |
1766 | // those type variables wind up being bound to. | |
85aaf69f | 1767 | debug!("assemble_builtin_bound_candidates: ambiguous builtin"); |
1a4d82fc JJ |
1768 | Ok(AmbiguousBuiltin) |
1769 | } | |
1770 | ||
62682a34 | 1771 | ty::TyError => ok_if(Vec::new()), |
1a4d82fc | 1772 | |
62682a34 SL |
1773 | ty::TyInfer(ty::FreshTy(_)) |
1774 | | ty::TyInfer(ty::FreshIntTy(_)) | |
1775 | | ty::TyInfer(ty::FreshFloatTy(_)) => { | |
1a4d82fc JJ |
1776 | self.tcx().sess.bug( |
1777 | &format!( | |
62682a34 SL |
1778 | "asked to assemble builtin bounds of unexpected type: {:?}", |
1779 | self_ty)); | |
1a4d82fc JJ |
1780 | } |
1781 | }; | |
1782 | ||
c34b1796 AL |
1783 | fn ok_if<'tcx>(v: Vec<Ty<'tcx>>) |
1784 | -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> { | |
1785 | Ok(If(ty::Binder(v))) | |
1786 | } | |
1787 | ||
1788 | fn nominal<'cx, 'tcx>(bound: ty::BuiltinBound, | |
1a4d82fc | 1789 | types: Vec<Ty<'tcx>>) |
c34b1796 | 1790 | -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> |
1a4d82fc JJ |
1791 | { |
1792 | // First check for markers and other nonsense. | |
1a4d82fc | 1793 | match bound { |
c34b1796 AL |
1794 | // Fallback to whatever user-defined impls exist in this case. |
1795 | ty::BoundCopy => Ok(ParameterBuiltin), | |
1a4d82fc | 1796 | |
c34b1796 AL |
1797 | // Sized if all the component types are sized. |
1798 | ty::BoundSized => ok_if(types), | |
1799 | ||
1800 | // Shouldn't be coming through here. | |
1801 | ty::BoundSend | ty::BoundSync => unreachable!(), | |
1802 | } | |
1803 | } | |
1804 | } | |
1805 | ||
1806 | /// For default impls, we need to break apart a type into its | |
1807 | /// "constituent types" -- meaning, the types that it contains. | |
1808 | /// | |
1809 | /// Here are some (simple) examples: | |
1810 | /// | |
1811 | /// ``` | |
1812 | /// (i32, u32) -> [i32, u32] | |
1813 | /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32] | |
1814 | /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32] | |
1815 | /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32] | |
1816 | /// ``` | |
1817 | fn constituent_types_for_ty(&self, t: Ty<'tcx>) -> Option<Vec<Ty<'tcx>>> { | |
1818 | match t.sty { | |
62682a34 SL |
1819 | ty::TyUint(_) | |
1820 | ty::TyInt(_) | | |
1821 | ty::TyBool | | |
1822 | ty::TyFloat(_) | | |
1823 | ty::TyBareFn(..) | | |
1824 | ty::TyStr | | |
1825 | ty::TyError | | |
1826 | ty::TyInfer(ty::IntVar(_)) | | |
1827 | ty::TyInfer(ty::FloatVar(_)) | | |
1828 | ty::TyChar => { | |
c34b1796 AL |
1829 | Some(Vec::new()) |
1830 | } | |
1831 | ||
62682a34 SL |
1832 | ty::TyTrait(..) | |
1833 | ty::TyParam(..) | | |
1834 | ty::TyProjection(..) | | |
1835 | ty::TyInfer(ty::TyVar(_)) | | |
1836 | ty::TyInfer(ty::FreshTy(_)) | | |
1837 | ty::TyInfer(ty::FreshIntTy(_)) | | |
1838 | ty::TyInfer(ty::FreshFloatTy(_)) => { | |
c34b1796 AL |
1839 | self.tcx().sess.bug( |
1840 | &format!( | |
62682a34 SL |
1841 | "asked to assemble constituent types of unexpected type: {:?}", |
1842 | t)); | |
c34b1796 AL |
1843 | } |
1844 | ||
62682a34 | 1845 | ty::TyBox(referent_ty) => { // Box<T> |
c34b1796 AL |
1846 | Some(vec![referent_ty]) |
1847 | } | |
1848 | ||
62682a34 SL |
1849 | ty::TyRawPtr(ty::mt { ty: element_ty, ..}) | |
1850 | ty::TyRef(_, ty::mt { ty: element_ty, ..}) => { | |
c34b1796 AL |
1851 | Some(vec![element_ty]) |
1852 | }, | |
1853 | ||
62682a34 | 1854 | ty::TyArray(element_ty, _) | ty::TySlice(element_ty) => { |
c34b1796 AL |
1855 | Some(vec![element_ty]) |
1856 | } | |
1a4d82fc | 1857 | |
62682a34 | 1858 | ty::TyTuple(ref tys) => { |
c34b1796 AL |
1859 | // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet |
1860 | Some(tys.clone()) | |
1861 | } | |
1862 | ||
62682a34 | 1863 | ty::TyClosure(def_id, substs) => { |
c34b1796 AL |
1864 | assert_eq!(def_id.krate, ast::LOCAL_CRATE); |
1865 | ||
1866 | match self.closure_typer.closure_upvars(def_id, substs) { | |
1867 | Some(upvars) => { | |
1868 | Some(upvars.iter().map(|c| c.ty).collect()) | |
1869 | } | |
1870 | None => { | |
1871 | None | |
1a4d82fc JJ |
1872 | } |
1873 | } | |
c34b1796 AL |
1874 | } |
1875 | ||
1876 | // for `PhantomData<T>`, we pass `T` | |
62682a34 | 1877 | ty::TyStruct(def_id, substs) |
c34b1796 AL |
1878 | if Some(def_id) == self.tcx().lang_items.phantom_data() => |
1879 | { | |
1880 | Some(substs.types.get_slice(TypeSpace).to_vec()) | |
1881 | } | |
1a4d82fc | 1882 | |
62682a34 | 1883 | ty::TyStruct(def_id, substs) => { |
c34b1796 AL |
1884 | Some(ty::struct_fields(self.tcx(), def_id, substs).iter() |
1885 | .map(|f| f.mt.ty) | |
1886 | .collect()) | |
1a4d82fc JJ |
1887 | } |
1888 | ||
62682a34 | 1889 | ty::TyEnum(def_id, substs) => { |
c34b1796 AL |
1890 | Some(ty::substd_enum_variants(self.tcx(), def_id, substs) |
1891 | .iter() | |
62682a34 | 1892 | .flat_map(|variant| &variant.args) |
c34b1796 AL |
1893 | .map(|&ty| ty) |
1894 | .collect()) | |
1895 | } | |
1896 | } | |
1897 | } | |
1898 | ||
1899 | fn collect_predicates_for_types(&mut self, | |
1900 | obligation: &TraitObligation<'tcx>, | |
1901 | trait_def_id: ast::DefId, | |
1902 | types: ty::Binder<Vec<Ty<'tcx>>>) | |
1903 | -> Vec<PredicateObligation<'tcx>> | |
1904 | { | |
1905 | let derived_cause = match self.tcx().lang_items.to_builtin_kind(trait_def_id) { | |
1906 | Some(_) => { | |
1907 | self.derived_cause(obligation, BuiltinDerivedObligation) | |
1908 | }, | |
1909 | None => { | |
1910 | self.derived_cause(obligation, ImplDerivedObligation) | |
1911 | } | |
1912 | }; | |
1913 | ||
1914 | // Because the types were potentially derived from | |
1915 | // higher-ranked obligations they may reference late-bound | |
1916 | // regions. For example, `for<'a> Foo<&'a int> : Copy` would | |
1917 | // yield a type like `for<'a> &'a int`. In general, we | |
1918 | // maintain the invariant that we never manipulate bound | |
1919 | // regions, so we have to process these bound regions somehow. | |
1920 | // | |
1921 | // The strategy is to: | |
1922 | // | |
1923 | // 1. Instantiate those regions to skolemized regions (e.g., | |
1924 | // `for<'a> &'a int` becomes `&0 int`. | |
1925 | // 2. Produce something like `&'0 int : Copy` | |
1926 | // 3. Re-bind the regions back to `for<'a> &'a int : Copy` | |
1927 | ||
1928 | // Move the binder into the individual types | |
1929 | let bound_types: Vec<ty::Binder<Ty<'tcx>>> = | |
1930 | types.skip_binder() | |
1931 | .iter() | |
1932 | .map(|&nested_ty| ty::Binder(nested_ty)) | |
1933 | .collect(); | |
1934 | ||
1935 | // For each type, produce a vector of resulting obligations | |
1936 | let obligations: Result<Vec<Vec<_>>, _> = bound_types.iter().map(|nested_ty| { | |
1937 | self.infcx.commit_if_ok(|snapshot| { | |
1938 | let (skol_ty, skol_map) = | |
1939 | self.infcx().skolemize_late_bound_regions(nested_ty, snapshot); | |
1940 | let Normalized { value: normalized_ty, mut obligations } = | |
1941 | project::normalize_with_depth(self, | |
1942 | obligation.cause.clone(), | |
1943 | obligation.recursion_depth + 1, | |
1944 | &skol_ty); | |
1945 | let skol_obligation = | |
d9579d0f AL |
1946 | util::predicate_for_trait_def(self.tcx(), |
1947 | derived_cause.clone(), | |
1948 | trait_def_id, | |
1949 | obligation.recursion_depth + 1, | |
1950 | normalized_ty, | |
1951 | vec![]); | |
c34b1796 AL |
1952 | obligations.push(skol_obligation); |
1953 | Ok(self.infcx().plug_leaks(skol_map, snapshot, &obligations)) | |
1954 | }) | |
1955 | }).collect(); | |
1956 | ||
1957 | // Flatten those vectors (couldn't do it above due `collect`) | |
1958 | match obligations { | |
62682a34 | 1959 | Ok(obligations) => obligations.into_iter().flat_map(|o| o).collect(), |
c34b1796 | 1960 | Err(ErrorReported) => Vec::new(), |
1a4d82fc JJ |
1961 | } |
1962 | } | |
1963 | ||
1964 | /////////////////////////////////////////////////////////////////////////// | |
1965 | // CONFIRMATION | |
1966 | // | |
1967 | // Confirmation unifies the output type parameters of the trait | |
1968 | // with the values found in the obligation, possibly yielding a | |
c34b1796 | 1969 | // type error. See `README.md` for more details. |
1a4d82fc JJ |
1970 | |
1971 | fn confirm_candidate(&mut self, | |
1972 | obligation: &TraitObligation<'tcx>, | |
1973 | candidate: SelectionCandidate<'tcx>) | |
1974 | -> Result<Selection<'tcx>,SelectionError<'tcx>> | |
1975 | { | |
62682a34 SL |
1976 | debug!("confirm_candidate({:?}, {:?})", |
1977 | obligation, | |
1978 | candidate); | |
1a4d82fc JJ |
1979 | |
1980 | match candidate { | |
1981 | BuiltinCandidate(builtin_bound) => { | |
1982 | Ok(VtableBuiltin( | |
1983 | try!(self.confirm_builtin_candidate(obligation, builtin_bound)))) | |
1984 | } | |
1985 | ||
85aaf69f | 1986 | PhantomFnCandidate | |
1a4d82fc | 1987 | ErrorCandidate => { |
62682a34 | 1988 | Ok(VtableBuiltin(VtableBuiltinData { nested: vec![] })) |
1a4d82fc JJ |
1989 | } |
1990 | ||
1991 | ParamCandidate(param) => { | |
85aaf69f SL |
1992 | let obligations = self.confirm_param_candidate(obligation, param); |
1993 | Ok(VtableParam(obligations)) | |
1a4d82fc JJ |
1994 | } |
1995 | ||
c34b1796 AL |
1996 | DefaultImplCandidate(trait_def_id) => { |
1997 | let data = self.confirm_default_impl_candidate(obligation, trait_def_id); | |
1998 | Ok(VtableDefaultImpl(data)) | |
1999 | } | |
2000 | ||
2001 | DefaultImplObjectCandidate(trait_def_id) => { | |
2002 | let data = self.confirm_default_impl_object_candidate(obligation, trait_def_id); | |
2003 | Ok(VtableDefaultImpl(data)) | |
2004 | } | |
2005 | ||
1a4d82fc JJ |
2006 | ImplCandidate(impl_def_id) => { |
2007 | let vtable_impl = | |
2008 | try!(self.confirm_impl_candidate(obligation, impl_def_id)); | |
2009 | Ok(VtableImpl(vtable_impl)) | |
2010 | } | |
2011 | ||
85aaf69f | 2012 | ClosureCandidate(closure_def_id, substs) => { |
62682a34 SL |
2013 | let vtable_closure = |
2014 | try!(self.confirm_closure_candidate(obligation, closure_def_id, &substs)); | |
2015 | Ok(VtableClosure(vtable_closure)) | |
1a4d82fc JJ |
2016 | } |
2017 | ||
c34b1796 AL |
2018 | BuiltinObjectCandidate => { |
2019 | // This indicates something like `(Trait+Send) : | |
2020 | // Send`. In this case, we know that this holds | |
2021 | // because that's what the object type is telling us, | |
2022 | // and there's really no additional obligations to | |
2023 | // prove and no types in particular to unify etc. | |
2024 | Ok(VtableParam(Vec::new())) | |
2025 | } | |
2026 | ||
1a4d82fc JJ |
2027 | ObjectCandidate => { |
2028 | let data = self.confirm_object_candidate(obligation); | |
2029 | Ok(VtableObject(data)) | |
2030 | } | |
2031 | ||
2032 | FnPointerCandidate => { | |
2033 | let fn_type = | |
2034 | try!(self.confirm_fn_pointer_candidate(obligation)); | |
2035 | Ok(VtableFnPointer(fn_type)) | |
2036 | } | |
2037 | ||
2038 | ProjectionCandidate => { | |
2039 | self.confirm_projection_candidate(obligation); | |
85aaf69f | 2040 | Ok(VtableParam(Vec::new())) |
1a4d82fc | 2041 | } |
d9579d0f AL |
2042 | |
2043 | BuiltinUnsizeCandidate => { | |
2044 | let data = try!(self.confirm_builtin_unsize_candidate(obligation)); | |
2045 | Ok(VtableBuiltin(data)) | |
2046 | } | |
1a4d82fc JJ |
2047 | } |
2048 | } | |
2049 | ||
2050 | fn confirm_projection_candidate(&mut self, | |
2051 | obligation: &TraitObligation<'tcx>) | |
2052 | { | |
2053 | let _: Result<(),()> = | |
c34b1796 | 2054 | self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc JJ |
2055 | let result = |
2056 | self.match_projection_obligation_against_bounds_from_trait(obligation, | |
2057 | snapshot); | |
2058 | assert!(result); | |
2059 | Ok(()) | |
2060 | }); | |
2061 | } | |
2062 | ||
2063 | fn confirm_param_candidate(&mut self, | |
2064 | obligation: &TraitObligation<'tcx>, | |
2065 | param: ty::PolyTraitRef<'tcx>) | |
85aaf69f | 2066 | -> Vec<PredicateObligation<'tcx>> |
1a4d82fc | 2067 | { |
62682a34 SL |
2068 | debug!("confirm_param_candidate({:?},{:?})", |
2069 | obligation, | |
2070 | param); | |
1a4d82fc JJ |
2071 | |
2072 | // During evaluation, we already checked that this | |
2073 | // where-clause trait-ref could be unified with the obligation | |
2074 | // trait-ref. Repeat that unification now without any | |
2075 | // transactional boundary; it should not fail. | |
85aaf69f SL |
2076 | match self.match_where_clause_trait_ref(obligation, param.clone()) { |
2077 | Ok(obligations) => obligations, | |
2078 | Err(()) => { | |
1a4d82fc | 2079 | self.tcx().sess.bug( |
62682a34 SL |
2080 | &format!("Where clause `{:?}` was applicable to `{:?}` but now is not", |
2081 | param, | |
2082 | obligation)); | |
1a4d82fc JJ |
2083 | } |
2084 | } | |
2085 | } | |
2086 | ||
2087 | fn confirm_builtin_candidate(&mut self, | |
2088 | obligation: &TraitObligation<'tcx>, | |
2089 | bound: ty::BuiltinBound) | |
2090 | -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, | |
2091 | SelectionError<'tcx>> | |
2092 | { | |
62682a34 SL |
2093 | debug!("confirm_builtin_candidate({:?})", |
2094 | obligation); | |
1a4d82fc JJ |
2095 | |
2096 | match try!(self.builtin_bound(bound, obligation)) { | |
2097 | If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)), | |
2098 | AmbiguousBuiltin | ParameterBuiltin => { | |
2099 | self.tcx().sess.span_bug( | |
2100 | obligation.cause.span, | |
62682a34 SL |
2101 | &format!("builtin bound for {:?} was ambig", |
2102 | obligation)); | |
1a4d82fc JJ |
2103 | } |
2104 | } | |
2105 | } | |
2106 | ||
2107 | fn vtable_builtin_data(&mut self, | |
2108 | obligation: &TraitObligation<'tcx>, | |
2109 | bound: ty::BuiltinBound, | |
c34b1796 | 2110 | nested: ty::Binder<Vec<Ty<'tcx>>>) |
1a4d82fc JJ |
2111 | -> VtableBuiltinData<PredicateObligation<'tcx>> |
2112 | { | |
c34b1796 AL |
2113 | let trait_def = match self.tcx().lang_items.from_builtin_kind(bound) { |
2114 | Ok(def_id) => def_id, | |
2115 | Err(_) => { | |
2116 | self.tcx().sess.bug("builtin trait definition not found"); | |
2117 | } | |
1a4d82fc JJ |
2118 | }; |
2119 | ||
c34b1796 AL |
2120 | let obligations = self.collect_predicates_for_types(obligation, trait_def, nested); |
2121 | ||
62682a34 SL |
2122 | debug!("vtable_builtin_data: obligations={:?}", |
2123 | obligations); | |
1a4d82fc JJ |
2124 | |
2125 | VtableBuiltinData { nested: obligations } | |
2126 | } | |
2127 | ||
c34b1796 AL |
2128 | /// This handles the case where a `impl Foo for ..` impl is being used. |
2129 | /// The idea is that the impl applies to `X : Foo` if the following conditions are met: | |
2130 | /// | |
2131 | /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds | |
2132 | /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds. | |
2133 | fn confirm_default_impl_candidate(&mut self, | |
2134 | obligation: &TraitObligation<'tcx>, | |
2135 | trait_def_id: ast::DefId) | |
2136 | -> VtableDefaultImplData<PredicateObligation<'tcx>> | |
2137 | { | |
62682a34 SL |
2138 | debug!("confirm_default_impl_candidate({:?}, {:?})", |
2139 | obligation, | |
2140 | trait_def_id); | |
c34b1796 AL |
2141 | |
2142 | // binder is moved below | |
2143 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
2144 | match self.constituent_types_for_ty(self_ty) { | |
2145 | Some(types) => self.vtable_default_impl(obligation, trait_def_id, ty::Binder(types)), | |
2146 | None => { | |
2147 | self.tcx().sess.bug( | |
2148 | &format!( | |
62682a34 SL |
2149 | "asked to confirm default implementation for ambiguous type: {:?}", |
2150 | self_ty)); | |
c34b1796 AL |
2151 | } |
2152 | } | |
2153 | } | |
2154 | ||
2155 | fn confirm_default_impl_object_candidate(&mut self, | |
2156 | obligation: &TraitObligation<'tcx>, | |
2157 | trait_def_id: ast::DefId) | |
2158 | -> VtableDefaultImplData<PredicateObligation<'tcx>> | |
2159 | { | |
62682a34 SL |
2160 | debug!("confirm_default_impl_object_candidate({:?}, {:?})", |
2161 | obligation, | |
2162 | trait_def_id); | |
c34b1796 AL |
2163 | |
2164 | assert!(ty::has_attr(self.tcx(), trait_def_id, "rustc_reflect_like")); | |
2165 | ||
2166 | // OK to skip binder, it is reintroduced below | |
2167 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
2168 | match self_ty.sty { | |
62682a34 | 2169 | ty::TyTrait(ref data) => { |
c34b1796 AL |
2170 | // OK to skip the binder, it is reintroduced below |
2171 | let input_types = data.principal.skip_binder().substs.types.get_slice(TypeSpace); | |
2172 | let assoc_types = data.bounds.projection_bounds | |
2173 | .iter() | |
2174 | .map(|pb| pb.skip_binder().ty); | |
2175 | let all_types: Vec<_> = input_types.iter().cloned() | |
2176 | .chain(assoc_types) | |
2177 | .collect(); | |
2178 | ||
2179 | // reintroduce the two binding levels we skipped, then flatten into one | |
2180 | let all_types = ty::Binder(ty::Binder(all_types)); | |
2181 | let all_types = ty::flatten_late_bound_regions(self.tcx(), &all_types); | |
2182 | ||
2183 | self.vtable_default_impl(obligation, trait_def_id, all_types) | |
2184 | } | |
2185 | _ => { | |
2186 | self.tcx().sess.bug( | |
2187 | &format!( | |
62682a34 SL |
2188 | "asked to confirm default object implementation for non-object type: {:?}", |
2189 | self_ty)); | |
c34b1796 AL |
2190 | } |
2191 | } | |
2192 | } | |
2193 | ||
2194 | /// See `confirm_default_impl_candidate` | |
2195 | fn vtable_default_impl(&mut self, | |
2196 | obligation: &TraitObligation<'tcx>, | |
2197 | trait_def_id: ast::DefId, | |
2198 | nested: ty::Binder<Vec<Ty<'tcx>>>) | |
2199 | -> VtableDefaultImplData<PredicateObligation<'tcx>> | |
2200 | { | |
62682a34 | 2201 | debug!("vtable_default_impl_data: nested={:?}", nested); |
c34b1796 AL |
2202 | |
2203 | let mut obligations = self.collect_predicates_for_types(obligation, | |
2204 | trait_def_id, | |
2205 | nested); | |
2206 | ||
62682a34 | 2207 | let trait_obligations: Result<Vec<_>,()> = self.infcx.commit_if_ok(|snapshot| { |
c34b1796 AL |
2208 | let poly_trait_ref = obligation.predicate.to_poly_trait_ref(); |
2209 | let (trait_ref, skol_map) = | |
2210 | self.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot); | |
2211 | Ok(self.impl_or_trait_obligations(obligation.cause.clone(), | |
2212 | obligation.recursion_depth + 1, | |
2213 | trait_def_id, | |
2214 | &trait_ref.substs, | |
2215 | skol_map, | |
2216 | snapshot)) | |
2217 | }); | |
2218 | ||
62682a34 SL |
2219 | // no Errors in that code above |
2220 | obligations.append(&mut trait_obligations.unwrap()); | |
c34b1796 | 2221 | |
62682a34 | 2222 | debug!("vtable_default_impl_data: obligations={:?}", obligations); |
c34b1796 AL |
2223 | |
2224 | VtableDefaultImplData { | |
2225 | trait_def_id: trait_def_id, | |
2226 | nested: obligations | |
2227 | } | |
2228 | } | |
2229 | ||
1a4d82fc JJ |
2230 | fn confirm_impl_candidate(&mut self, |
2231 | obligation: &TraitObligation<'tcx>, | |
2232 | impl_def_id: ast::DefId) | |
2233 | -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>, | |
2234 | SelectionError<'tcx>> | |
2235 | { | |
62682a34 SL |
2236 | debug!("confirm_impl_candidate({:?},{:?})", |
2237 | obligation, | |
2238 | impl_def_id); | |
1a4d82fc JJ |
2239 | |
2240 | // First, create the substitutions by matching the impl again, | |
2241 | // this time not in a probe. | |
c34b1796 | 2242 | self.infcx.commit_if_ok(|snapshot| { |
d9579d0f | 2243 | let (substs, skol_map) = |
1a4d82fc | 2244 | self.rematch_impl(impl_def_id, obligation, |
d9579d0f | 2245 | snapshot); |
62682a34 | 2246 | debug!("confirm_impl_candidate substs={:?}", substs); |
1a4d82fc JJ |
2247 | Ok(self.vtable_impl(impl_def_id, substs, obligation.cause.clone(), |
2248 | obligation.recursion_depth + 1, skol_map, snapshot)) | |
2249 | }) | |
2250 | } | |
2251 | ||
2252 | fn vtable_impl(&mut self, | |
2253 | impl_def_id: ast::DefId, | |
62682a34 | 2254 | mut substs: Normalized<'tcx, Substs<'tcx>>, |
1a4d82fc | 2255 | cause: ObligationCause<'tcx>, |
c34b1796 | 2256 | recursion_depth: usize, |
1a4d82fc JJ |
2257 | skol_map: infer::SkolemizationMap, |
2258 | snapshot: &infer::CombinedSnapshot) | |
2259 | -> VtableImplData<'tcx, PredicateObligation<'tcx>> | |
2260 | { | |
62682a34 SL |
2261 | debug!("vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={}, skol_map={:?})", |
2262 | impl_def_id, | |
2263 | substs, | |
1a4d82fc | 2264 | recursion_depth, |
62682a34 | 2265 | skol_map); |
1a4d82fc JJ |
2266 | |
2267 | let mut impl_obligations = | |
c34b1796 AL |
2268 | self.impl_or_trait_obligations(cause, |
2269 | recursion_depth, | |
2270 | impl_def_id, | |
2271 | &substs.value, | |
2272 | skol_map, | |
2273 | snapshot); | |
1a4d82fc | 2274 | |
62682a34 SL |
2275 | debug!("vtable_impl: impl_def_id={:?} impl_obligations={:?}", |
2276 | impl_def_id, | |
2277 | impl_obligations); | |
1a4d82fc | 2278 | |
62682a34 | 2279 | impl_obligations.append(&mut substs.obligations); |
1a4d82fc JJ |
2280 | |
2281 | VtableImplData { impl_def_id: impl_def_id, | |
2282 | substs: substs.value, | |
2283 | nested: impl_obligations } | |
2284 | } | |
2285 | ||
2286 | fn confirm_object_candidate(&mut self, | |
2287 | obligation: &TraitObligation<'tcx>) | |
2288 | -> VtableObjectData<'tcx> | |
2289 | { | |
62682a34 SL |
2290 | debug!("confirm_object_candidate({:?})", |
2291 | obligation); | |
1a4d82fc | 2292 | |
c34b1796 AL |
2293 | // FIXME skipping binder here seems wrong -- we should |
2294 | // probably flatten the binder from the obligation and the | |
2295 | // binder from the object. Have to try to make a broken test | |
2296 | // case that results. -nmatsakis | |
2297 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); | |
1a4d82fc | 2298 | let poly_trait_ref = match self_ty.sty { |
62682a34 | 2299 | ty::TyTrait(ref data) => { |
1a4d82fc JJ |
2300 | data.principal_trait_ref_with_self_ty(self.tcx(), self_ty) |
2301 | } | |
2302 | _ => { | |
2303 | self.tcx().sess.span_bug(obligation.cause.span, | |
2304 | "object candidate with non-object"); | |
2305 | } | |
2306 | }; | |
2307 | ||
c34b1796 AL |
2308 | // Upcast the object type to the obligation type. There must |
2309 | // be exactly one applicable trait-reference; if this were not | |
2310 | // the case, we would have reported an ambiguity error rather | |
2311 | // than successfully selecting one of the candidates. | |
2312 | let upcast_trait_refs = self.upcast(poly_trait_ref.clone(), obligation); | |
2313 | assert_eq!(upcast_trait_refs.len(), 1); | |
2314 | let upcast_trait_ref = upcast_trait_refs.into_iter().next().unwrap(); | |
1a4d82fc | 2315 | |
c34b1796 | 2316 | match self.match_poly_trait_ref(obligation, upcast_trait_ref.clone()) { |
1a4d82fc JJ |
2317 | Ok(()) => { } |
2318 | Err(()) => { | |
2319 | self.tcx().sess.span_bug(obligation.cause.span, | |
2320 | "failed to match trait refs"); | |
2321 | } | |
2322 | } | |
2323 | ||
c34b1796 AL |
2324 | VtableObjectData { object_ty: self_ty, |
2325 | upcast_trait_ref: upcast_trait_ref } | |
1a4d82fc JJ |
2326 | } |
2327 | ||
2328 | fn confirm_fn_pointer_candidate(&mut self, | |
2329 | obligation: &TraitObligation<'tcx>) | |
2330 | -> Result<ty::Ty<'tcx>,SelectionError<'tcx>> | |
2331 | { | |
62682a34 SL |
2332 | debug!("confirm_fn_pointer_candidate({:?})", |
2333 | obligation); | |
1a4d82fc | 2334 | |
c34b1796 AL |
2335 | // ok to skip binder; it is reintroduced below |
2336 | let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()); | |
85aaf69f | 2337 | let sig = ty::ty_fn_sig(self_ty); |
c34b1796 | 2338 | let trait_ref = |
85aaf69f SL |
2339 | util::closure_trait_ref_and_return_type(self.tcx(), |
2340 | obligation.predicate.def_id(), | |
2341 | self_ty, | |
2342 | sig, | |
c34b1796 AL |
2343 | util::TupleArgumentsFlag::Yes) |
2344 | .map_bound(|(trait_ref, _)| trait_ref); | |
1a4d82fc JJ |
2345 | |
2346 | try!(self.confirm_poly_trait_refs(obligation.cause.clone(), | |
2347 | obligation.predicate.to_poly_trait_ref(), | |
2348 | trait_ref)); | |
2349 | Ok(self_ty) | |
2350 | } | |
2351 | ||
85aaf69f SL |
2352 | fn confirm_closure_candidate(&mut self, |
2353 | obligation: &TraitObligation<'tcx>, | |
2354 | closure_def_id: ast::DefId, | |
2355 | substs: &Substs<'tcx>) | |
62682a34 SL |
2356 | -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>, |
2357 | SelectionError<'tcx>> | |
1a4d82fc | 2358 | { |
62682a34 SL |
2359 | debug!("confirm_closure_candidate({:?},{:?},{:?})", |
2360 | obligation, | |
2361 | closure_def_id, | |
2362 | substs); | |
1a4d82fc | 2363 | |
62682a34 SL |
2364 | let Normalized { |
2365 | value: trait_ref, | |
2366 | obligations | |
2367 | } = self.closure_trait_ref(obligation, closure_def_id, substs); | |
1a4d82fc | 2368 | |
62682a34 SL |
2369 | debug!("confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})", |
2370 | closure_def_id, | |
2371 | trait_ref, | |
2372 | obligations); | |
1a4d82fc | 2373 | |
62682a34 SL |
2374 | try!(self.confirm_poly_trait_refs(obligation.cause.clone(), |
2375 | obligation.predicate.to_poly_trait_ref(), | |
2376 | trait_ref)); | |
2377 | ||
2378 | Ok(VtableClosureData { | |
2379 | closure_def_id: closure_def_id, | |
2380 | substs: substs.clone(), | |
2381 | nested: obligations | |
2382 | }) | |
1a4d82fc JJ |
2383 | } |
2384 | ||
85aaf69f | 2385 | /// In the case of closure types and fn pointers, |
1a4d82fc JJ |
2386 | /// we currently treat the input type parameters on the trait as |
2387 | /// outputs. This means that when we have a match we have only | |
2388 | /// considered the self type, so we have to go back and make sure | |
2389 | /// to relate the argument types too. This is kind of wrong, but | |
2390 | /// since we control the full set of impls, also not that wrong, | |
2391 | /// and it DOES yield better error messages (since we don't report | |
2392 | /// errors as if there is no applicable impl, but rather report | |
2393 | /// errors are about mismatched argument types. | |
2394 | /// | |
85aaf69f | 2395 | /// Here is an example. Imagine we have an closure expression |
1a4d82fc JJ |
2396 | /// and we desugared it so that the type of the expression is |
2397 | /// `Closure`, and `Closure` expects an int as argument. Then it | |
2398 | /// is "as if" the compiler generated this impl: | |
2399 | /// | |
2400 | /// impl Fn(int) for Closure { ... } | |
2401 | /// | |
c34b1796 | 2402 | /// Now imagine our obligation is `Fn(usize) for Closure`. So far |
1a4d82fc | 2403 | /// we have matched the self-type `Closure`. At this point we'll |
c34b1796 | 2404 | /// compare the `int` to `usize` and generate an error. |
1a4d82fc JJ |
2405 | /// |
2406 | /// Note that this checking occurs *after* the impl has selected, | |
2407 | /// because these output type parameters should not affect the | |
2408 | /// selection of the impl. Therefore, if there is a mismatch, we | |
2409 | /// report an error to the user. | |
2410 | fn confirm_poly_trait_refs(&mut self, | |
2411 | obligation_cause: ObligationCause, | |
2412 | obligation_trait_ref: ty::PolyTraitRef<'tcx>, | |
2413 | expected_trait_ref: ty::PolyTraitRef<'tcx>) | |
2414 | -> Result<(), SelectionError<'tcx>> | |
2415 | { | |
2416 | let origin = infer::RelateOutputImplTypes(obligation_cause.span); | |
2417 | ||
2418 | let obligation_trait_ref = obligation_trait_ref.clone(); | |
2419 | match self.infcx.sub_poly_trait_refs(false, | |
2420 | origin, | |
2421 | expected_trait_ref.clone(), | |
2422 | obligation_trait_ref.clone()) { | |
2423 | Ok(()) => Ok(()), | |
2424 | Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e)) | |
2425 | } | |
2426 | } | |
2427 | ||
d9579d0f AL |
2428 | fn confirm_builtin_unsize_candidate(&mut self, |
2429 | obligation: &TraitObligation<'tcx>,) | |
2430 | -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, | |
2431 | SelectionError<'tcx>> { | |
2432 | let tcx = self.tcx(); | |
2433 | ||
2434 | // assemble_candidates_for_unsizing should ensure there are no late bound | |
2435 | // regions here. See the comment there for more details. | |
2436 | let source = self.infcx.shallow_resolve( | |
2437 | ty::no_late_bound_regions(tcx, &obligation.self_ty()).unwrap()); | |
2438 | let target = self.infcx.shallow_resolve(obligation.predicate.0.input_types()[0]); | |
2439 | ||
62682a34 SL |
2440 | debug!("confirm_builtin_unsize_candidate(source={:?}, target={:?})", |
2441 | source, target); | |
d9579d0f AL |
2442 | |
2443 | let mut nested = vec![]; | |
2444 | match (&source.sty, &target.sty) { | |
2445 | // Trait+Kx+'a -> Trait+Ky+'b (upcasts). | |
62682a34 | 2446 | (&ty::TyTrait(ref data_a), &ty::TyTrait(ref data_b)) => { |
d9579d0f AL |
2447 | // See assemble_candidates_for_unsizing for more info. |
2448 | let bounds = ty::ExistentialBounds { | |
2449 | region_bound: data_b.bounds.region_bound, | |
2450 | builtin_bounds: data_b.bounds.builtin_bounds, | |
2451 | projection_bounds: data_a.bounds.projection_bounds.clone(), | |
62682a34 | 2452 | region_bound_will_change: data_b.bounds.region_bound_will_change, |
d9579d0f AL |
2453 | }; |
2454 | ||
2455 | let new_trait = ty::mk_trait(tcx, data_a.principal.clone(), bounds); | |
2456 | let origin = infer::Misc(obligation.cause.span); | |
2457 | if self.infcx.sub_types(false, origin, new_trait, target).is_err() { | |
2458 | return Err(Unimplemented); | |
2459 | } | |
2460 | ||
2461 | // Register one obligation for 'a: 'b. | |
2462 | let cause = ObligationCause::new(obligation.cause.span, | |
2463 | obligation.cause.body_id, | |
2464 | ObjectCastObligation(target)); | |
2465 | let outlives = ty::OutlivesPredicate(data_a.bounds.region_bound, | |
2466 | data_b.bounds.region_bound); | |
2467 | nested.push(Obligation::with_depth(cause, | |
2468 | obligation.recursion_depth + 1, | |
2469 | ty::Binder(outlives).as_predicate())); | |
2470 | } | |
2471 | ||
2472 | // T -> Trait. | |
62682a34 | 2473 | (_, &ty::TyTrait(ref data)) => { |
d9579d0f AL |
2474 | let object_did = data.principal_def_id(); |
2475 | if !object_safety::is_object_safe(tcx, object_did) { | |
2476 | return Err(TraitNotObjectSafe(object_did)); | |
2477 | } | |
2478 | ||
2479 | let cause = ObligationCause::new(obligation.cause.span, | |
2480 | obligation.cause.body_id, | |
2481 | ObjectCastObligation(target)); | |
2482 | let mut push = |predicate| { | |
2483 | nested.push(Obligation::with_depth(cause.clone(), | |
2484 | obligation.recursion_depth + 1, | |
2485 | predicate)); | |
2486 | }; | |
2487 | ||
2488 | // Create the obligation for casting from T to Trait. | |
2489 | push(data.principal_trait_ref_with_self_ty(tcx, source).as_predicate()); | |
2490 | ||
2491 | // We can only make objects from sized types. | |
2492 | let mut builtin_bounds = data.bounds.builtin_bounds; | |
2493 | builtin_bounds.insert(ty::BoundSized); | |
2494 | ||
2495 | // Create additional obligations for all the various builtin | |
2496 | // bounds attached to the object cast. (In other words, if the | |
2497 | // object type is Foo+Send, this would create an obligation | |
2498 | // for the Send check.) | |
2499 | for bound in &builtin_bounds { | |
2500 | if let Ok(tr) = util::trait_ref_for_builtin_bound(tcx, bound, source) { | |
2501 | push(tr.as_predicate()); | |
2502 | } else { | |
2503 | return Err(Unimplemented); | |
2504 | } | |
2505 | } | |
2506 | ||
2507 | // Create obligations for the projection predicates. | |
2508 | for bound in data.projection_bounds_with_self_ty(tcx, source) { | |
2509 | push(bound.as_predicate()); | |
2510 | } | |
2511 | ||
2512 | // If the type is `Foo+'a`, ensures that the type | |
2513 | // being cast to `Foo+'a` outlives `'a`: | |
2514 | let outlives = ty::OutlivesPredicate(source, | |
2515 | data.bounds.region_bound); | |
2516 | push(ty::Binder(outlives).as_predicate()); | |
2517 | } | |
2518 | ||
2519 | // [T; n] -> [T]. | |
62682a34 | 2520 | (&ty::TyArray(a, _), &ty::TySlice(b)) => { |
d9579d0f AL |
2521 | let origin = infer::Misc(obligation.cause.span); |
2522 | if self.infcx.sub_types(false, origin, a, b).is_err() { | |
2523 | return Err(Unimplemented); | |
2524 | } | |
2525 | } | |
2526 | ||
2527 | // Struct<T> -> Struct<U>. | |
62682a34 | 2528 | (&ty::TyStruct(def_id, substs_a), &ty::TyStruct(_, substs_b)) => { |
d9579d0f AL |
2529 | let fields = ty::lookup_struct_fields(tcx, def_id).iter().map(|f| { |
2530 | ty::lookup_field_type_unsubstituted(tcx, def_id, f.id) | |
2531 | }).collect::<Vec<_>>(); | |
2532 | ||
62682a34 SL |
2533 | // The last field of the structure has to exist and contain type parameters. |
2534 | let field = if let Some(&field) = fields.last() { | |
2535 | field | |
d9579d0f AL |
2536 | } else { |
2537 | return Err(Unimplemented); | |
2538 | }; | |
62682a34 SL |
2539 | let mut ty_params = vec![]; |
2540 | ty::walk_ty(field, |ty| { | |
2541 | if let ty::TyParam(p) = ty.sty { | |
2542 | assert!(p.space == TypeSpace); | |
2543 | let idx = p.idx as usize; | |
2544 | if !ty_params.contains(&idx) { | |
2545 | ty_params.push(idx); | |
2546 | } | |
2547 | } | |
2548 | }); | |
2549 | if ty_params.is_empty() { | |
2550 | return Err(Unimplemented); | |
2551 | } | |
d9579d0f | 2552 | |
62682a34 SL |
2553 | // Replace type parameters used in unsizing with |
2554 | // TyError and ensure they do not affect any other fields. | |
d9579d0f AL |
2555 | // This could be checked after type collection for any struct |
2556 | // with a potentially unsized trailing field. | |
2557 | let mut new_substs = substs_a.clone(); | |
62682a34 SL |
2558 | for &i in &ty_params { |
2559 | new_substs.types.get_mut_slice(TypeSpace)[i] = tcx.types.err; | |
2560 | } | |
d9579d0f AL |
2561 | for &ty in fields.init() { |
2562 | if ty::type_is_error(ty.subst(tcx, &new_substs)) { | |
2563 | return Err(Unimplemented); | |
2564 | } | |
2565 | } | |
2566 | ||
62682a34 SL |
2567 | // Extract Field<T> and Field<U> from Struct<T> and Struct<U>. |
2568 | let inner_source = field.subst(tcx, substs_a); | |
2569 | let inner_target = field.subst(tcx, substs_b); | |
d9579d0f | 2570 | |
62682a34 SL |
2571 | // Check that the source structure with the target's |
2572 | // type parameters is a subtype of the target. | |
2573 | for &i in &ty_params { | |
2574 | let param_b = *substs_b.types.get(TypeSpace, i); | |
2575 | new_substs.types.get_mut_slice(TypeSpace)[i] = param_b; | |
2576 | } | |
d9579d0f AL |
2577 | let new_struct = ty::mk_struct(tcx, def_id, tcx.mk_substs(new_substs)); |
2578 | let origin = infer::Misc(obligation.cause.span); | |
2579 | if self.infcx.sub_types(false, origin, new_struct, target).is_err() { | |
2580 | return Err(Unimplemented); | |
2581 | } | |
2582 | ||
62682a34 | 2583 | // Construct the nested Field<T>: Unsize<Field<U>> predicate. |
d9579d0f AL |
2584 | nested.push(util::predicate_for_trait_def(tcx, |
2585 | obligation.cause.clone(), | |
2586 | obligation.predicate.def_id(), | |
2587 | obligation.recursion_depth + 1, | |
2588 | inner_source, | |
2589 | vec![inner_target])); | |
2590 | } | |
2591 | ||
2592 | _ => unreachable!() | |
2593 | }; | |
2594 | ||
62682a34 | 2595 | Ok(VtableBuiltinData { nested: nested }) |
d9579d0f AL |
2596 | } |
2597 | ||
1a4d82fc JJ |
2598 | /////////////////////////////////////////////////////////////////////////// |
2599 | // Matching | |
2600 | // | |
2601 | // Matching is a common path used for both evaluation and | |
2602 | // confirmation. It basically unifies types that appear in impls | |
2603 | // and traits. This does affect the surrounding environment; | |
2604 | // therefore, when used during evaluation, match routines must be | |
2605 | // run inside of a `probe()` so that their side-effects are | |
2606 | // contained. | |
2607 | ||
2608 | fn rematch_impl(&mut self, | |
2609 | impl_def_id: ast::DefId, | |
2610 | obligation: &TraitObligation<'tcx>, | |
d9579d0f AL |
2611 | snapshot: &infer::CombinedSnapshot) |
2612 | -> (Normalized<'tcx, Substs<'tcx>>, infer::SkolemizationMap) | |
1a4d82fc | 2613 | { |
d9579d0f AL |
2614 | match self.match_impl(impl_def_id, obligation, snapshot) { |
2615 | Ok((substs, skol_map)) => (substs, skol_map), | |
1a4d82fc JJ |
2616 | Err(()) => { |
2617 | self.tcx().sess.bug( | |
62682a34 SL |
2618 | &format!("Impl {:?} was matchable against {:?} but now is not", |
2619 | impl_def_id, | |
2620 | obligation)); | |
1a4d82fc JJ |
2621 | } |
2622 | } | |
2623 | } | |
2624 | ||
2625 | fn match_impl(&mut self, | |
2626 | impl_def_id: ast::DefId, | |
2627 | obligation: &TraitObligation<'tcx>, | |
d9579d0f AL |
2628 | snapshot: &infer::CombinedSnapshot) |
2629 | -> Result<(Normalized<'tcx, Substs<'tcx>>, | |
2630 | infer::SkolemizationMap), ()> | |
1a4d82fc JJ |
2631 | { |
2632 | let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap(); | |
2633 | ||
2634 | // Before we create the substitutions and everything, first | |
2635 | // consider a "quick reject". This avoids creating more types | |
2636 | // and so forth that we need to. | |
d9579d0f | 2637 | if self.fast_reject_trait_refs(obligation, &impl_trait_ref) { |
1a4d82fc JJ |
2638 | return Err(()); |
2639 | } | |
2640 | ||
d9579d0f AL |
2641 | let (skol_obligation, skol_map) = self.infcx().skolemize_late_bound_regions( |
2642 | &obligation.predicate, | |
2643 | snapshot); | |
2644 | let skol_obligation_trait_ref = skol_obligation.trait_ref; | |
2645 | ||
c34b1796 AL |
2646 | let impl_substs = util::fresh_type_vars_for_impl(self.infcx, |
2647 | obligation.cause.span, | |
2648 | impl_def_id); | |
1a4d82fc JJ |
2649 | |
2650 | let impl_trait_ref = impl_trait_ref.subst(self.tcx(), | |
2651 | &impl_substs); | |
2652 | ||
2653 | let impl_trait_ref = | |
2654 | project::normalize_with_depth(self, | |
2655 | obligation.cause.clone(), | |
2656 | obligation.recursion_depth + 1, | |
2657 | &impl_trait_ref); | |
2658 | ||
62682a34 SL |
2659 | debug!("match_impl(impl_def_id={:?}, obligation={:?}, \ |
2660 | impl_trait_ref={:?}, skol_obligation_trait_ref={:?})", | |
2661 | impl_def_id, | |
2662 | obligation, | |
2663 | impl_trait_ref, | |
2664 | skol_obligation_trait_ref); | |
1a4d82fc JJ |
2665 | |
2666 | let origin = infer::RelateOutputImplTypes(obligation.cause.span); | |
c34b1796 AL |
2667 | if let Err(e) = self.infcx.sub_trait_refs(false, |
2668 | origin, | |
2669 | impl_trait_ref.value.clone(), | |
2670 | skol_obligation_trait_ref) { | |
62682a34 | 2671 | debug!("match_impl: failed sub_trait_refs due to `{}`", e); |
c34b1796 | 2672 | return Err(()); |
1a4d82fc JJ |
2673 | } |
2674 | ||
d9579d0f | 2675 | if let Err(e) = self.infcx.leak_check(&skol_map, snapshot) { |
62682a34 | 2676 | debug!("match_impl: failed leak check due to `{}`", e); |
c34b1796 | 2677 | return Err(()); |
1a4d82fc JJ |
2678 | } |
2679 | ||
62682a34 | 2680 | debug!("match_impl: success impl_substs={:?}", impl_substs); |
d9579d0f | 2681 | Ok((Normalized { |
c34b1796 AL |
2682 | value: impl_substs, |
2683 | obligations: impl_trait_ref.obligations | |
d9579d0f | 2684 | }, skol_map)) |
1a4d82fc JJ |
2685 | } |
2686 | ||
2687 | fn fast_reject_trait_refs(&mut self, | |
2688 | obligation: &TraitObligation, | |
2689 | impl_trait_ref: &ty::TraitRef) | |
2690 | -> bool | |
2691 | { | |
2692 | // We can avoid creating type variables and doing the full | |
2693 | // substitution if we find that any of the input types, when | |
2694 | // simplified, do not match. | |
2695 | ||
2696 | obligation.predicate.0.input_types().iter() | |
62682a34 | 2697 | .zip(impl_trait_ref.input_types()) |
1a4d82fc JJ |
2698 | .any(|(&obligation_ty, &impl_ty)| { |
2699 | let simplified_obligation_ty = | |
2700 | fast_reject::simplify_type(self.tcx(), obligation_ty, true); | |
2701 | let simplified_impl_ty = | |
2702 | fast_reject::simplify_type(self.tcx(), impl_ty, false); | |
2703 | ||
2704 | simplified_obligation_ty.is_some() && | |
2705 | simplified_impl_ty.is_some() && | |
2706 | simplified_obligation_ty != simplified_impl_ty | |
2707 | }) | |
2708 | } | |
2709 | ||
85aaf69f SL |
2710 | /// Normalize `where_clause_trait_ref` and try to match it against |
2711 | /// `obligation`. If successful, return any predicates that | |
2712 | /// result from the normalization. Normalization is necessary | |
2713 | /// because where-clauses are stored in the parameter environment | |
2714 | /// unnormalized. | |
2715 | fn match_where_clause_trait_ref(&mut self, | |
2716 | obligation: &TraitObligation<'tcx>, | |
2717 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>) | |
2718 | -> Result<Vec<PredicateObligation<'tcx>>,()> | |
2719 | { | |
c34b1796 | 2720 | try!(self.match_poly_trait_ref(obligation, where_clause_trait_ref)); |
85aaf69f SL |
2721 | Ok(Vec::new()) |
2722 | } | |
2723 | ||
2724 | /// Returns `Ok` if `poly_trait_ref` being true implies that the | |
2725 | /// obligation is satisfied. | |
1a4d82fc JJ |
2726 | fn match_poly_trait_ref(&mut self, |
2727 | obligation: &TraitObligation<'tcx>, | |
85aaf69f | 2728 | poly_trait_ref: ty::PolyTraitRef<'tcx>) |
1a4d82fc JJ |
2729 | -> Result<(),()> |
2730 | { | |
62682a34 SL |
2731 | debug!("match_poly_trait_ref: obligation={:?} poly_trait_ref={:?}", |
2732 | obligation, | |
2733 | poly_trait_ref); | |
1a4d82fc JJ |
2734 | |
2735 | let origin = infer::RelateOutputImplTypes(obligation.cause.span); | |
2736 | match self.infcx.sub_poly_trait_refs(false, | |
2737 | origin, | |
85aaf69f | 2738 | poly_trait_ref, |
1a4d82fc JJ |
2739 | obligation.predicate.to_poly_trait_ref()) { |
2740 | Ok(()) => Ok(()), | |
2741 | Err(_) => Err(()), | |
2742 | } | |
2743 | } | |
2744 | ||
2745 | /// Determines whether the self type declared against | |
2746 | /// `impl_def_id` matches `obligation_self_ty`. If successful, | |
2747 | /// returns the substitutions used to make them match. See | |
2748 | /// `match_impl()`. For example, if `impl_def_id` is declared | |
2749 | /// as: | |
2750 | /// | |
d9579d0f | 2751 | /// impl<T:Copy> Foo for Box<T> { ... } |
1a4d82fc | 2752 | /// |
d9579d0f AL |
2753 | /// and `obligation_self_ty` is `int`, we'd get back an `Err(_)` |
2754 | /// result. But if `obligation_self_ty` were `Box<int>`, we'd get | |
1a4d82fc JJ |
2755 | /// back `Ok(T=int)`. |
2756 | fn match_inherent_impl(&mut self, | |
2757 | impl_def_id: ast::DefId, | |
2758 | obligation_cause: &ObligationCause, | |
2759 | obligation_self_ty: Ty<'tcx>) | |
2760 | -> Result<Substs<'tcx>,()> | |
2761 | { | |
2762 | // Create fresh type variables for each type parameter declared | |
2763 | // on the impl etc. | |
c34b1796 AL |
2764 | let impl_substs = util::fresh_type_vars_for_impl(self.infcx, |
2765 | obligation_cause.span, | |
2766 | impl_def_id); | |
1a4d82fc JJ |
2767 | |
2768 | // Find the self type for the impl. | |
2769 | let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty; | |
2770 | let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs); | |
2771 | ||
62682a34 SL |
2772 | debug!("match_impl_self_types(obligation_self_ty={:?}, impl_self_ty={:?})", |
2773 | obligation_self_ty, | |
2774 | impl_self_ty); | |
1a4d82fc JJ |
2775 | |
2776 | match self.match_self_types(obligation_cause, | |
2777 | impl_self_ty, | |
2778 | obligation_self_ty) { | |
2779 | Ok(()) => { | |
62682a34 | 2780 | debug!("Matched impl_substs={:?}", impl_substs); |
1a4d82fc JJ |
2781 | Ok(impl_substs) |
2782 | } | |
2783 | Err(()) => { | |
2784 | debug!("NoMatch"); | |
2785 | Err(()) | |
2786 | } | |
2787 | } | |
2788 | } | |
2789 | ||
2790 | fn match_self_types(&mut self, | |
2791 | cause: &ObligationCause, | |
2792 | ||
2793 | // The self type provided by the impl/caller-obligation: | |
2794 | provided_self_ty: Ty<'tcx>, | |
2795 | ||
2796 | // The self type the obligation is for: | |
2797 | required_self_ty: Ty<'tcx>) | |
2798 | -> Result<(),()> | |
2799 | { | |
2800 | // FIXME(#5781) -- equating the types is stronger than | |
2801 | // necessary. Should consider variance of trait w/r/t Self. | |
2802 | ||
2803 | let origin = infer::RelateSelfType(cause.span); | |
2804 | match self.infcx.eq_types(false, | |
2805 | origin, | |
2806 | provided_self_ty, | |
2807 | required_self_ty) { | |
2808 | Ok(()) => Ok(()), | |
2809 | Err(_) => Err(()), | |
2810 | } | |
2811 | } | |
2812 | ||
2813 | /////////////////////////////////////////////////////////////////////////// | |
2814 | // Miscellany | |
2815 | ||
c34b1796 AL |
2816 | fn match_fresh_trait_refs(&self, |
2817 | previous: &ty::PolyTraitRef<'tcx>, | |
2818 | current: &ty::PolyTraitRef<'tcx>) | |
2819 | -> bool | |
2820 | { | |
2821 | let mut matcher = ty_match::Match::new(self.tcx()); | |
2822 | matcher.relate(previous, current).is_ok() | |
2823 | } | |
2824 | ||
1a4d82fc | 2825 | fn push_stack<'o,'s:'o>(&mut self, |
c34b1796 | 2826 | previous_stack: TraitObligationStackList<'s, 'tcx>, |
1a4d82fc JJ |
2827 | obligation: &'o TraitObligation<'tcx>) |
2828 | -> TraitObligationStack<'o, 'tcx> | |
2829 | { | |
2830 | let fresh_trait_ref = | |
2831 | obligation.predicate.to_poly_trait_ref().fold_with(&mut self.freshener); | |
2832 | ||
2833 | TraitObligationStack { | |
2834 | obligation: obligation, | |
2835 | fresh_trait_ref: fresh_trait_ref, | |
c34b1796 | 2836 | previous: previous_stack, |
1a4d82fc JJ |
2837 | } |
2838 | } | |
2839 | ||
62682a34 SL |
2840 | fn closure_trait_ref_unnormalized(&mut self, |
2841 | obligation: &TraitObligation<'tcx>, | |
2842 | closure_def_id: ast::DefId, | |
2843 | substs: &Substs<'tcx>) | |
2844 | -> ty::PolyTraitRef<'tcx> | |
85aaf69f SL |
2845 | { |
2846 | let closure_type = self.closure_typer.closure_type(closure_def_id, substs); | |
2847 | let ty::Binder((trait_ref, _)) = | |
2848 | util::closure_trait_ref_and_return_type(self.tcx(), | |
2849 | obligation.predicate.def_id(), | |
2850 | obligation.predicate.0.self_ty(), // (1) | |
2851 | &closure_type.sig, | |
2852 | util::TupleArgumentsFlag::No); | |
85aaf69f SL |
2853 | // (1) Feels icky to skip the binder here, but OTOH we know |
2854 | // that the self-type is an unboxed closure type and hence is | |
2855 | // in fact unparameterized (or at least does not reference any | |
2856 | // regions bound in the obligation). Still probably some | |
2857 | // refactoring could make this nicer. | |
2858 | ||
2859 | ty::Binder(trait_ref) | |
2860 | } | |
2861 | ||
62682a34 SL |
2862 | fn closure_trait_ref(&mut self, |
2863 | obligation: &TraitObligation<'tcx>, | |
2864 | closure_def_id: ast::DefId, | |
2865 | substs: &Substs<'tcx>) | |
2866 | -> Normalized<'tcx, ty::PolyTraitRef<'tcx>> | |
2867 | { | |
2868 | let trait_ref = self.closure_trait_ref_unnormalized( | |
2869 | obligation, closure_def_id, substs); | |
2870 | ||
2871 | // A closure signature can contain associated types which | |
2872 | // must be normalized. | |
2873 | normalize_with_depth(self, | |
2874 | obligation.cause.clone(), | |
2875 | obligation.recursion_depth+1, | |
2876 | &trait_ref) | |
2877 | } | |
2878 | ||
c34b1796 AL |
2879 | /// Returns the obligations that are implied by instantiating an |
2880 | /// impl or trait. The obligations are substituted and fully | |
2881 | /// normalized. This is used when confirming an impl or default | |
2882 | /// impl. | |
2883 | fn impl_or_trait_obligations(&mut self, | |
2884 | cause: ObligationCause<'tcx>, | |
2885 | recursion_depth: usize, | |
2886 | def_id: ast::DefId, // of impl or trait | |
2887 | substs: &Substs<'tcx>, // for impl or trait | |
2888 | skol_map: infer::SkolemizationMap, | |
2889 | snapshot: &infer::CombinedSnapshot) | |
62682a34 | 2890 | -> Vec<PredicateObligation<'tcx>> |
1a4d82fc | 2891 | { |
62682a34 | 2892 | debug!("impl_or_trait_obligations(def_id={:?})", def_id); |
c34b1796 AL |
2893 | |
2894 | let predicates = ty::lookup_predicates(self.tcx(), def_id); | |
2895 | let predicates = predicates.instantiate(self.tcx(), substs); | |
2896 | let predicates = normalize_with_depth(self, cause.clone(), recursion_depth, &predicates); | |
62682a34 | 2897 | let mut predicates = self.infcx().plug_leaks(skol_map, snapshot, &predicates); |
c34b1796 | 2898 | let mut obligations = |
62682a34 | 2899 | util::predicates_for_generics(cause, |
1a4d82fc | 2900 | recursion_depth, |
c34b1796 | 2901 | &predicates.value); |
62682a34 | 2902 | obligations.append(&mut predicates.obligations); |
c34b1796 | 2903 | obligations |
1a4d82fc JJ |
2904 | } |
2905 | ||
1a4d82fc JJ |
2906 | #[allow(unused_comparisons)] |
2907 | fn derived_cause(&self, | |
2908 | obligation: &TraitObligation<'tcx>, | |
2909 | variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>) | |
2910 | -> ObligationCause<'tcx> | |
2911 | { | |
2912 | /*! | |
2913 | * Creates a cause for obligations that are derived from | |
2914 | * `obligation` by a recursive search (e.g., for a builtin | |
2915 | * bound, or eventually a `impl Foo for ..`). If `obligation` | |
2916 | * is itself a derived obligation, this is just a clone, but | |
2917 | * otherwise we create a "derived obligation" cause so as to | |
2918 | * keep track of the original root obligation for error | |
2919 | * reporting. | |
2920 | */ | |
2921 | ||
2922 | // NOTE(flaper87): As of now, it keeps track of the whole error | |
2923 | // chain. Ideally, we should have a way to configure this either | |
2924 | // by using -Z verbose or just a CLI argument. | |
2925 | if obligation.recursion_depth >= 0 { | |
2926 | let derived_cause = DerivedObligationCause { | |
2927 | parent_trait_ref: obligation.predicate.to_poly_trait_ref(), | |
2928 | parent_code: Rc::new(obligation.cause.code.clone()), | |
2929 | }; | |
2930 | ObligationCause::new(obligation.cause.span, | |
2931 | obligation.cause.body_id, | |
2932 | variant(derived_cause)) | |
2933 | } else { | |
2934 | obligation.cause.clone() | |
2935 | } | |
2936 | } | |
c34b1796 AL |
2937 | |
2938 | /// Upcasts an object trait-reference into those that match the obligation. | |
2939 | fn upcast(&mut self, obj_trait_ref: ty::PolyTraitRef<'tcx>, obligation: &TraitObligation<'tcx>) | |
2940 | -> Vec<ty::PolyTraitRef<'tcx>> | |
2941 | { | |
62682a34 SL |
2942 | debug!("upcast(obj_trait_ref={:?}, obligation={:?})", |
2943 | obj_trait_ref, | |
2944 | obligation); | |
c34b1796 AL |
2945 | |
2946 | let obligation_def_id = obligation.predicate.def_id(); | |
2947 | let mut upcast_trait_refs = util::upcast(self.tcx(), obj_trait_ref, obligation_def_id); | |
2948 | ||
2949 | // Retain only those upcast versions that match the trait-ref | |
2950 | // we are looking for. In particular, we know that all of | |
2951 | // `upcast_trait_refs` apply to the correct trait, but | |
2952 | // possibly with incorrect type parameters. For example, we | |
2953 | // may be trying to upcast `Foo` to `Bar<i32>`, but `Foo` is | |
2954 | // declared as `trait Foo : Bar<u32>`. | |
2955 | upcast_trait_refs.retain(|upcast_trait_ref| { | |
2956 | let upcast_trait_ref = upcast_trait_ref.clone(); | |
2957 | self.infcx.probe(|_| self.match_poly_trait_ref(obligation, upcast_trait_ref)).is_ok() | |
2958 | }); | |
2959 | ||
62682a34 | 2960 | debug!("upcast: upcast_trait_refs={:?}", upcast_trait_refs); |
c34b1796 AL |
2961 | upcast_trait_refs |
2962 | } | |
1a4d82fc JJ |
2963 | } |
2964 | ||
1a4d82fc JJ |
2965 | impl<'tcx> SelectionCache<'tcx> { |
2966 | pub fn new() -> SelectionCache<'tcx> { | |
2967 | SelectionCache { | |
c34b1796 | 2968 | hashmap: RefCell::new(FnvHashMap()) |
1a4d82fc JJ |
2969 | } |
2970 | } | |
2971 | } | |
2972 | ||
c34b1796 AL |
2973 | impl<'o,'tcx> TraitObligationStack<'o,'tcx> { |
2974 | fn list(&'o self) -> TraitObligationStackList<'o,'tcx> { | |
2975 | TraitObligationStackList::with(self) | |
2976 | } | |
2977 | ||
2978 | fn iter(&'o self) -> TraitObligationStackList<'o,'tcx> { | |
2979 | self.list() | |
2980 | } | |
2981 | } | |
2982 | ||
2983 | #[derive(Copy, Clone)] | |
2984 | struct TraitObligationStackList<'o,'tcx:'o> { | |
2985 | head: Option<&'o TraitObligationStack<'o,'tcx>> | |
2986 | } | |
2987 | ||
2988 | impl<'o,'tcx> TraitObligationStackList<'o,'tcx> { | |
2989 | fn empty() -> TraitObligationStackList<'o,'tcx> { | |
2990 | TraitObligationStackList { head: None } | |
2991 | } | |
2992 | ||
2993 | fn with(r: &'o TraitObligationStack<'o,'tcx>) -> TraitObligationStackList<'o,'tcx> { | |
2994 | TraitObligationStackList { head: Some(r) } | |
1a4d82fc JJ |
2995 | } |
2996 | } | |
2997 | ||
c34b1796 | 2998 | impl<'o,'tcx> Iterator for TraitObligationStackList<'o,'tcx>{ |
1a4d82fc JJ |
2999 | type Item = &'o TraitObligationStack<'o,'tcx>; |
3000 | ||
c34b1796 AL |
3001 | fn next(&mut self) -> Option<&'o TraitObligationStack<'o,'tcx>> { |
3002 | match self.head { | |
1a4d82fc JJ |
3003 | Some(o) => { |
3004 | *self = o.previous; | |
3005 | Some(o) | |
3006 | } | |
c34b1796 | 3007 | None => None |
1a4d82fc JJ |
3008 | } |
3009 | } | |
3010 | } | |
3011 | ||
62682a34 SL |
3012 | impl<'o,'tcx> fmt::Debug for TraitObligationStack<'o,'tcx> { |
3013 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
3014 | write!(f, "TraitObligationStack({:?})", self.obligation) | |
1a4d82fc JJ |
3015 | } |
3016 | } | |
3017 | ||
3018 | impl<'tcx> EvaluationResult<'tcx> { | |
3019 | fn may_apply(&self) -> bool { | |
3020 | match *self { | |
3021 | EvaluatedToOk | | |
3022 | EvaluatedToAmbig | | |
d9579d0f AL |
3023 | EvaluatedToErr(OutputTypeParameterMismatch(..)) | |
3024 | EvaluatedToErr(TraitNotObjectSafe(_)) => | |
c34b1796 AL |
3025 | true, |
3026 | ||
3027 | EvaluatedToErr(Unimplemented) => | |
3028 | false, | |
1a4d82fc JJ |
3029 | } |
3030 | } | |
3031 | } | |
3032 | ||
3033 | impl MethodMatchResult { | |
3034 | pub fn may_apply(&self) -> bool { | |
3035 | match *self { | |
3036 | MethodMatched(_) => true, | |
3037 | MethodAmbiguous(_) => true, | |
3038 | MethodDidNotMatch => false, | |
3039 | } | |
3040 | } | |
3041 | } |