]>
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 | ||
11 | //! Code for projecting associated types out of trait references. | |
12 | ||
13 | use super::elaborate_predicates; | |
c34b1796 | 14 | use super::report_overflow_error; |
1a4d82fc JJ |
15 | use super::Obligation; |
16 | use super::ObligationCause; | |
1a4d82fc JJ |
17 | use super::PredicateObligation; |
18 | use super::SelectionContext; | |
19 | use super::SelectionError; | |
62682a34 | 20 | use super::VtableClosureData; |
1a4d82fc | 21 | use super::VtableImplData; |
85aaf69f | 22 | use super::util; |
1a4d82fc | 23 | |
92a42be0 | 24 | use middle::infer::{self, TypeOrigin}; |
62682a34 | 25 | use middle::subst::Subst; |
9cc50fc6 | 26 | use middle::ty::{self, ToPredicate, ToPolyTraitRef, Ty}; |
e9174d1e | 27 | use middle::ty::fold::{TypeFoldable, TypeFolder}; |
85aaf69f SL |
28 | use syntax::parse::token; |
29 | use util::common::FN_OUTPUT_NAME; | |
62682a34 | 30 | |
1a4d82fc JJ |
31 | pub type PolyProjectionObligation<'tcx> = |
32 | Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>; | |
33 | ||
34 | pub type ProjectionObligation<'tcx> = | |
35 | Obligation<'tcx, ty::ProjectionPredicate<'tcx>>; | |
36 | ||
37 | pub type ProjectionTyObligation<'tcx> = | |
38 | Obligation<'tcx, ty::ProjectionTy<'tcx>>; | |
39 | ||
40 | /// When attempting to resolve `<T as TraitRef>::Name` ... | |
62682a34 | 41 | #[derive(Debug)] |
1a4d82fc JJ |
42 | pub enum ProjectionTyError<'tcx> { |
43 | /// ...we found multiple sources of information and couldn't resolve the ambiguity. | |
44 | TooManyCandidates, | |
45 | ||
46 | /// ...an error occurred matching `T : TraitRef` | |
47 | TraitSelectionError(SelectionError<'tcx>), | |
48 | } | |
49 | ||
50 | #[derive(Clone)] | |
51 | pub struct MismatchedProjectionTypes<'tcx> { | |
e9174d1e | 52 | pub err: ty::error::TypeError<'tcx> |
1a4d82fc JJ |
53 | } |
54 | ||
62682a34 | 55 | #[derive(PartialEq, Eq, Debug)] |
1a4d82fc | 56 | enum ProjectionTyCandidate<'tcx> { |
e9174d1e | 57 | // from a where-clause in the env or object type |
1a4d82fc | 58 | ParamEnv(ty::PolyProjectionPredicate<'tcx>), |
e9174d1e SL |
59 | |
60 | // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C | |
61 | TraitDef(ty::PolyProjectionPredicate<'tcx>), | |
62 | ||
63 | // defined in an impl | |
1a4d82fc | 64 | Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>), |
e9174d1e SL |
65 | |
66 | // closure return type | |
62682a34 | 67 | Closure(VtableClosureData<'tcx, PredicateObligation<'tcx>>), |
e9174d1e SL |
68 | |
69 | // fn pointer return type | |
85aaf69f | 70 | FnPointer(Ty<'tcx>), |
1a4d82fc JJ |
71 | } |
72 | ||
73 | struct ProjectionTyCandidateSet<'tcx> { | |
74 | vec: Vec<ProjectionTyCandidate<'tcx>>, | |
75 | ambiguous: bool | |
76 | } | |
77 | ||
85aaf69f SL |
78 | /// Evaluates constraints of the form: |
79 | /// | |
80 | /// for<...> <T as Trait>::U == V | |
81 | /// | |
82 | /// If successful, this may result in additional obligations. | |
1a4d82fc JJ |
83 | pub fn poly_project_and_unify_type<'cx,'tcx>( |
84 | selcx: &mut SelectionContext<'cx,'tcx>, | |
85 | obligation: &PolyProjectionObligation<'tcx>) | |
86 | -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>> | |
87 | { | |
62682a34 SL |
88 | debug!("poly_project_and_unify_type(obligation={:?})", |
89 | obligation); | |
1a4d82fc JJ |
90 | |
91 | let infcx = selcx.infcx(); | |
c34b1796 | 92 | infcx.commit_if_ok(|snapshot| { |
1a4d82fc JJ |
93 | let (skol_predicate, skol_map) = |
94 | infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot); | |
95 | ||
96 | let skol_obligation = obligation.with(skol_predicate); | |
97 | match project_and_unify_type(selcx, &skol_obligation) { | |
85aaf69f | 98 | Ok(result) => { |
1a4d82fc | 99 | match infcx.leak_check(&skol_map, snapshot) { |
85aaf69f SL |
100 | Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, &result)), |
101 | Err(e) => Err(MismatchedProjectionTypes { err: e }), | |
1a4d82fc JJ |
102 | } |
103 | } | |
1a4d82fc | 104 | Err(e) => { |
85aaf69f | 105 | Err(e) |
1a4d82fc JJ |
106 | } |
107 | } | |
85aaf69f | 108 | }) |
1a4d82fc JJ |
109 | } |
110 | ||
85aaf69f SL |
111 | /// Evaluates constraints of the form: |
112 | /// | |
113 | /// <T as Trait>::U == V | |
114 | /// | |
115 | /// If successful, this may result in additional obligations. | |
1a4d82fc JJ |
116 | fn project_and_unify_type<'cx,'tcx>( |
117 | selcx: &mut SelectionContext<'cx,'tcx>, | |
118 | obligation: &ProjectionObligation<'tcx>) | |
119 | -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>> | |
120 | { | |
62682a34 SL |
121 | debug!("project_and_unify_type(obligation={:?})", |
122 | obligation); | |
1a4d82fc JJ |
123 | |
124 | let Normalized { value: normalized_ty, obligations } = | |
125 | match opt_normalize_projection_type(selcx, | |
126 | obligation.predicate.projection_ty.clone(), | |
127 | obligation.cause.clone(), | |
128 | obligation.recursion_depth) { | |
129 | Some(n) => n, | |
85aaf69f SL |
130 | None => { |
131 | consider_unification_despite_ambiguity(selcx, obligation); | |
132 | return Ok(None); | |
133 | } | |
1a4d82fc JJ |
134 | }; |
135 | ||
62682a34 SL |
136 | debug!("project_and_unify_type: normalized_ty={:?} obligations={:?}", |
137 | normalized_ty, | |
138 | obligations); | |
1a4d82fc JJ |
139 | |
140 | let infcx = selcx.infcx(); | |
92a42be0 | 141 | let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span); |
1a4d82fc JJ |
142 | match infer::mk_eqty(infcx, true, origin, normalized_ty, obligation.predicate.ty) { |
143 | Ok(()) => Ok(Some(obligations)), | |
144 | Err(err) => Err(MismatchedProjectionTypes { err: err }), | |
145 | } | |
146 | } | |
147 | ||
85aaf69f SL |
148 | fn consider_unification_despite_ambiguity<'cx,'tcx>(selcx: &mut SelectionContext<'cx,'tcx>, |
149 | obligation: &ProjectionObligation<'tcx>) { | |
62682a34 SL |
150 | debug!("consider_unification_despite_ambiguity(obligation={:?})", |
151 | obligation); | |
85aaf69f SL |
152 | |
153 | let def_id = obligation.predicate.projection_ty.trait_ref.def_id; | |
154 | match selcx.tcx().lang_items.fn_trait_kind(def_id) { | |
155 | Some(_) => { } | |
156 | None => { return; } | |
157 | } | |
158 | ||
159 | let infcx = selcx.infcx(); | |
160 | let self_ty = obligation.predicate.projection_ty.trait_ref.self_ty(); | |
161 | let self_ty = infcx.shallow_resolve(self_ty); | |
162 | debug!("consider_unification_despite_ambiguity: self_ty.sty={:?}", | |
163 | self_ty.sty); | |
164 | match self_ty.sty { | |
c1a9b12d | 165 | ty::TyClosure(closure_def_id, ref substs) => { |
85aaf69f SL |
166 | let closure_typer = selcx.closure_typer(); |
167 | let closure_type = closure_typer.closure_type(closure_def_id, substs); | |
168 | let ty::Binder((_, ret_type)) = | |
169 | util::closure_trait_ref_and_return_type(infcx.tcx, | |
170 | def_id, | |
171 | self_ty, | |
172 | &closure_type.sig, | |
173 | util::TupleArgumentsFlag::No); | |
62682a34 SL |
174 | // We don't have to normalize the return type here - this is only |
175 | // reached for TyClosure: Fn inputs where the closure kind is | |
176 | // still unknown, which should only occur in typeck where the | |
177 | // closure type is already normalized. | |
85aaf69f SL |
178 | let (ret_type, _) = |
179 | infcx.replace_late_bound_regions_with_fresh_var( | |
180 | obligation.cause.span, | |
181 | infer::AssocTypeProjection(obligation.predicate.projection_ty.item_name), | |
182 | &ty::Binder(ret_type)); | |
62682a34 | 183 | |
85aaf69f | 184 | debug!("consider_unification_despite_ambiguity: ret_type={:?}", |
62682a34 | 185 | ret_type); |
92a42be0 | 186 | let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span); |
85aaf69f SL |
187 | let obligation_ty = obligation.predicate.ty; |
188 | match infer::mk_eqty(infcx, true, origin, obligation_ty, ret_type) { | |
189 | Ok(()) => { } | |
190 | Err(_) => { /* ignore errors */ } | |
191 | } | |
192 | } | |
193 | _ => { } | |
194 | } | |
195 | } | |
196 | ||
197 | /// Normalizes any associated type projections in `value`, replacing | |
198 | /// them with a fully resolved type where possible. The return value | |
199 | /// combines the normalized result and any additional obligations that | |
200 | /// were incurred as result. | |
1a4d82fc JJ |
201 | pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>, |
202 | cause: ObligationCause<'tcx>, | |
203 | value: &T) | |
204 | -> Normalized<'tcx, T> | |
9cc50fc6 | 205 | where T : TypeFoldable<'tcx> |
1a4d82fc JJ |
206 | { |
207 | normalize_with_depth(selcx, cause, 0, value) | |
208 | } | |
209 | ||
85aaf69f | 210 | /// As `normalize`, but with a custom depth. |
1a4d82fc JJ |
211 | pub fn normalize_with_depth<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>, |
212 | cause: ObligationCause<'tcx>, | |
c34b1796 | 213 | depth: usize, |
1a4d82fc JJ |
214 | value: &T) |
215 | -> Normalized<'tcx, T> | |
9cc50fc6 | 216 | where T : TypeFoldable<'tcx> |
1a4d82fc JJ |
217 | { |
218 | let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth); | |
219 | let result = normalizer.fold(value); | |
62682a34 | 220 | |
1a4d82fc JJ |
221 | Normalized { |
222 | value: result, | |
223 | obligations: normalizer.obligations, | |
224 | } | |
225 | } | |
226 | ||
227 | struct AssociatedTypeNormalizer<'a,'b:'a,'tcx:'b> { | |
228 | selcx: &'a mut SelectionContext<'b,'tcx>, | |
229 | cause: ObligationCause<'tcx>, | |
230 | obligations: Vec<PredicateObligation<'tcx>>, | |
c34b1796 | 231 | depth: usize, |
1a4d82fc JJ |
232 | } |
233 | ||
234 | impl<'a,'b,'tcx> AssociatedTypeNormalizer<'a,'b,'tcx> { | |
235 | fn new(selcx: &'a mut SelectionContext<'b,'tcx>, | |
236 | cause: ObligationCause<'tcx>, | |
c34b1796 | 237 | depth: usize) |
1a4d82fc JJ |
238 | -> AssociatedTypeNormalizer<'a,'b,'tcx> |
239 | { | |
240 | AssociatedTypeNormalizer { | |
241 | selcx: selcx, | |
242 | cause: cause, | |
243 | obligations: vec!(), | |
244 | depth: depth, | |
245 | } | |
246 | } | |
247 | ||
9cc50fc6 | 248 | fn fold<T:TypeFoldable<'tcx>>(&mut self, value: &T) -> T { |
1a4d82fc JJ |
249 | let value = self.selcx.infcx().resolve_type_vars_if_possible(value); |
250 | ||
251 | if !value.has_projection_types() { | |
252 | value.clone() | |
253 | } else { | |
254 | value.fold_with(self) | |
255 | } | |
256 | } | |
257 | } | |
258 | ||
259 | impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> { | |
260 | fn tcx(&self) -> &ty::ctxt<'tcx> { | |
261 | self.selcx.tcx() | |
262 | } | |
263 | ||
264 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
265 | // We don't want to normalize associated types that occur inside of region | |
266 | // binders, because they may contain bound regions, and we can't cope with that. | |
267 | // | |
268 | // Example: | |
269 | // | |
270 | // for<'a> fn(<T as Foo<&'a>>::A) | |
271 | // | |
272 | // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll | |
273 | // normalize it when we instantiate those bound regions (which | |
274 | // should occur eventually). | |
275 | ||
9cc50fc6 | 276 | let ty = ty.super_fold_with(self); |
1a4d82fc | 277 | match ty.sty { |
62682a34 | 278 | ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*) |
1a4d82fc JJ |
279 | |
280 | // (*) This is kind of hacky -- we need to be able to | |
281 | // handle normalization within binders because | |
282 | // otherwise we wind up a need to normalize when doing | |
283 | // trait matching (since you can have a trait | |
284 | // obligation like `for<'a> T::B : Fn(&'a int)`), but | |
285 | // we can't normalize with bound regions in scope. So | |
286 | // far now we just ignore binders but only normalize | |
287 | // if all bound regions are gone (and then we still | |
288 | // have to renormalize whenever we instantiate a | |
289 | // binder). It would be better to normalize in a | |
290 | // binding-aware fashion. | |
291 | ||
292 | let Normalized { value: ty, obligations } = | |
293 | normalize_projection_type(self.selcx, | |
294 | data.clone(), | |
295 | self.cause.clone(), | |
296 | self.depth); | |
62682a34 | 297 | self.obligations.extend(obligations); |
1a4d82fc JJ |
298 | ty |
299 | } | |
300 | ||
301 | _ => { | |
302 | ty | |
303 | } | |
304 | } | |
305 | } | |
306 | } | |
307 | ||
c34b1796 | 308 | #[derive(Clone)] |
1a4d82fc JJ |
309 | pub struct Normalized<'tcx,T> { |
310 | pub value: T, | |
311 | pub obligations: Vec<PredicateObligation<'tcx>>, | |
312 | } | |
313 | ||
314 | pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>; | |
315 | ||
316 | impl<'tcx,T> Normalized<'tcx,T> { | |
317 | pub fn with<U>(self, value: U) -> Normalized<'tcx,U> { | |
318 | Normalized { value: value, obligations: self.obligations } | |
319 | } | |
320 | } | |
321 | ||
85aaf69f SL |
322 | /// The guts of `normalize`: normalize a specific projection like `<T |
323 | /// as Trait>::Item`. The result is always a type (and possibly | |
324 | /// additional obligations). If ambiguity arises, which implies that | |
325 | /// there are unresolved type variables in the projection, we will | |
326 | /// substitute a fresh type variable `$X` and generate a new | |
327 | /// obligation `<T as Trait>::Item == $X` for later. | |
1a4d82fc JJ |
328 | pub fn normalize_projection_type<'a,'b,'tcx>( |
329 | selcx: &'a mut SelectionContext<'b,'tcx>, | |
330 | projection_ty: ty::ProjectionTy<'tcx>, | |
331 | cause: ObligationCause<'tcx>, | |
c34b1796 | 332 | depth: usize) |
1a4d82fc JJ |
333 | -> NormalizedTy<'tcx> |
334 | { | |
335 | opt_normalize_projection_type(selcx, projection_ty.clone(), cause.clone(), depth) | |
336 | .unwrap_or_else(move || { | |
337 | // if we bottom out in ambiguity, create a type variable | |
338 | // and a deferred predicate to resolve this when more type | |
339 | // information is available. | |
340 | ||
341 | let ty_var = selcx.infcx().next_ty_var(); | |
342 | let projection = ty::Binder(ty::ProjectionPredicate { | |
343 | projection_ty: projection_ty, | |
344 | ty: ty_var | |
345 | }); | |
92a42be0 SL |
346 | let obligation = Obligation::with_depth( |
347 | cause, depth + 1, projection.to_predicate()); | |
1a4d82fc JJ |
348 | Normalized { |
349 | value: ty_var, | |
350 | obligations: vec!(obligation) | |
351 | } | |
352 | }) | |
353 | } | |
354 | ||
85aaf69f SL |
355 | /// The guts of `normalize`: normalize a specific projection like `<T |
356 | /// as Trait>::Item`. The result is always a type (and possibly | |
357 | /// additional obligations). Returns `None` in the case of ambiguity, | |
358 | /// which indicates that there are unbound type variables. | |
1a4d82fc JJ |
359 | fn opt_normalize_projection_type<'a,'b,'tcx>( |
360 | selcx: &'a mut SelectionContext<'b,'tcx>, | |
361 | projection_ty: ty::ProjectionTy<'tcx>, | |
362 | cause: ObligationCause<'tcx>, | |
c34b1796 | 363 | depth: usize) |
1a4d82fc JJ |
364 | -> Option<NormalizedTy<'tcx>> |
365 | { | |
366 | debug!("normalize_projection_type(\ | |
62682a34 | 367 | projection_ty={:?}, \ |
1a4d82fc | 368 | depth={})", |
62682a34 | 369 | projection_ty, |
1a4d82fc JJ |
370 | depth); |
371 | ||
372 | let obligation = Obligation::with_depth(cause.clone(), depth, projection_ty.clone()); | |
373 | match project_type(selcx, &obligation) { | |
374 | Ok(ProjectedTy::Progress(projected_ty, mut obligations)) => { | |
375 | // if projection succeeded, then what we get out of this | |
376 | // is also non-normalized (consider: it was derived from | |
377 | // an impl, where-clause etc) and hence we must | |
378 | // re-normalize it | |
379 | ||
62682a34 SL |
380 | debug!("normalize_projection_type: projected_ty={:?} depth={} obligations={:?}", |
381 | projected_ty, | |
1a4d82fc | 382 | depth, |
62682a34 | 383 | obligations); |
1a4d82fc | 384 | |
c1a9b12d | 385 | if projected_ty.has_projection_types() { |
92a42be0 | 386 | let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth+1); |
1a4d82fc JJ |
387 | let normalized_ty = normalizer.fold(&projected_ty); |
388 | ||
62682a34 SL |
389 | debug!("normalize_projection_type: normalized_ty={:?} depth={}", |
390 | normalized_ty, | |
1a4d82fc JJ |
391 | depth); |
392 | ||
62682a34 | 393 | obligations.extend(normalizer.obligations); |
1a4d82fc JJ |
394 | Some(Normalized { |
395 | value: normalized_ty, | |
396 | obligations: obligations, | |
397 | }) | |
398 | } else { | |
399 | Some(Normalized { | |
400 | value: projected_ty, | |
401 | obligations: obligations, | |
402 | }) | |
403 | } | |
404 | } | |
405 | Ok(ProjectedTy::NoProgress(projected_ty)) => { | |
62682a34 SL |
406 | debug!("normalize_projection_type: projected_ty={:?} no progress", |
407 | projected_ty); | |
1a4d82fc JJ |
408 | Some(Normalized { |
409 | value: projected_ty, | |
410 | obligations: vec!() | |
411 | }) | |
412 | } | |
413 | Err(ProjectionTyError::TooManyCandidates) => { | |
62682a34 | 414 | debug!("normalize_projection_type: too many candidates"); |
1a4d82fc JJ |
415 | None |
416 | } | |
417 | Err(ProjectionTyError::TraitSelectionError(_)) => { | |
62682a34 | 418 | debug!("normalize_projection_type: ERROR"); |
1a4d82fc JJ |
419 | // if we got an error processing the `T as Trait` part, |
420 | // just return `ty::err` but add the obligation `T : | |
421 | // Trait`, which when processed will cause the error to be | |
422 | // reported later | |
423 | ||
424 | Some(normalize_to_error(selcx, projection_ty, cause, depth)) | |
425 | } | |
426 | } | |
427 | } | |
428 | ||
92a42be0 SL |
429 | /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not |
430 | /// hold. In various error cases, we cannot generate a valid | |
431 | /// normalized projection. Therefore, we create an inference variable | |
432 | /// return an associated obligation that, when fulfilled, will lead to | |
433 | /// an error. | |
d9579d0f | 434 | /// |
92a42be0 SL |
435 | /// Note that we used to return `TyError` here, but that was quite |
436 | /// dubious -- the premise was that an error would *eventually* be | |
437 | /// reported, when the obligation was processed. But in general once | |
438 | /// you see a `TyError` you are supposed to be able to assume that an | |
439 | /// error *has been* reported, so that you can take whatever heuristic | |
440 | /// paths you want to take. To make things worse, it was possible for | |
441 | /// cycles to arise, where you basically had a setup like `<MyType<$0> | |
442 | /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as | |
443 | /// Trait>::Foo> to `[type error]` would lead to an obligation of | |
444 | /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report | |
445 | /// an error for this obligation, but we legitimately should not, | |
446 | /// because it contains `[type error]`. Yuck! (See issue #29857 for | |
447 | /// one case where this arose.) | |
1a4d82fc JJ |
448 | fn normalize_to_error<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>, |
449 | projection_ty: ty::ProjectionTy<'tcx>, | |
450 | cause: ObligationCause<'tcx>, | |
c34b1796 | 451 | depth: usize) |
1a4d82fc JJ |
452 | -> NormalizedTy<'tcx> |
453 | { | |
454 | let trait_ref = projection_ty.trait_ref.to_poly_trait_ref(); | |
455 | let trait_obligation = Obligation { cause: cause, | |
456 | recursion_depth: depth, | |
c1a9b12d | 457 | predicate: trait_ref.to_predicate() }; |
92a42be0 | 458 | let new_value = selcx.infcx().next_ty_var(); |
1a4d82fc | 459 | Normalized { |
92a42be0 | 460 | value: new_value, |
1a4d82fc JJ |
461 | obligations: vec!(trait_obligation) |
462 | } | |
463 | } | |
464 | ||
465 | enum ProjectedTy<'tcx> { | |
466 | Progress(Ty<'tcx>, Vec<PredicateObligation<'tcx>>), | |
467 | NoProgress(Ty<'tcx>), | |
468 | } | |
469 | ||
470 | /// Compute the result of a projection type (if we can). | |
471 | fn project_type<'cx,'tcx>( | |
472 | selcx: &mut SelectionContext<'cx,'tcx>, | |
473 | obligation: &ProjectionTyObligation<'tcx>) | |
474 | -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>> | |
475 | { | |
62682a34 SL |
476 | debug!("project(obligation={:?})", |
477 | obligation); | |
1a4d82fc JJ |
478 | |
479 | let recursion_limit = selcx.tcx().sess.recursion_limit.get(); | |
480 | if obligation.recursion_depth >= recursion_limit { | |
481 | debug!("project: overflow!"); | |
7453a54e | 482 | report_overflow_error(selcx.infcx(), &obligation, true); |
1a4d82fc JJ |
483 | } |
484 | ||
485 | let obligation_trait_ref = | |
486 | selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate.trait_ref); | |
487 | ||
62682a34 | 488 | debug!("project: obligation_trait_ref={:?}", obligation_trait_ref); |
1a4d82fc JJ |
489 | |
490 | if obligation_trait_ref.references_error() { | |
491 | return Ok(ProjectedTy::Progress(selcx.tcx().types.err, vec!())); | |
492 | } | |
493 | ||
494 | let mut candidates = ProjectionTyCandidateSet { | |
495 | vec: Vec::new(), | |
496 | ambiguous: false, | |
497 | }; | |
498 | ||
499 | assemble_candidates_from_param_env(selcx, | |
500 | obligation, | |
501 | &obligation_trait_ref, | |
502 | &mut candidates); | |
503 | ||
85aaf69f SL |
504 | assemble_candidates_from_trait_def(selcx, |
505 | obligation, | |
506 | &obligation_trait_ref, | |
507 | &mut candidates); | |
508 | ||
1a4d82fc JJ |
509 | if let Err(e) = assemble_candidates_from_impls(selcx, |
510 | obligation, | |
511 | &obligation_trait_ref, | |
512 | &mut candidates) { | |
513 | return Err(ProjectionTyError::TraitSelectionError(e)); | |
514 | } | |
515 | ||
516 | debug!("{} candidates, ambiguous={}", | |
517 | candidates.vec.len(), | |
518 | candidates.ambiguous); | |
519 | ||
e9174d1e SL |
520 | // Inherent ambiguity that prevents us from even enumerating the |
521 | // candidates. | |
522 | if candidates.ambiguous { | |
523 | return Err(ProjectionTyError::TooManyCandidates); | |
524 | } | |
1a4d82fc | 525 | |
85aaf69f SL |
526 | // Drop duplicates. |
527 | // | |
528 | // Note: `candidates.vec` seems to be on the critical path of the | |
529 | // compiler. Replacing it with an hash set was also tried, which would | |
530 | // render the following dedup unnecessary. It led to cleaner code but | |
531 | // prolonged compiling time of `librustc` from 5m30s to 6m in one test, or | |
532 | // ~9% performance lost. | |
533 | if candidates.vec.len() > 1 { | |
534 | let mut i = 0; | |
535 | while i < candidates.vec.len() { | |
536 | let has_dup = (0..i).any(|j| candidates.vec[i] == candidates.vec[j]); | |
537 | if has_dup { | |
538 | candidates.vec.swap_remove(i); | |
539 | } else { | |
540 | i += 1; | |
541 | } | |
542 | } | |
543 | } | |
544 | ||
e9174d1e SL |
545 | // Prefer where-clauses. As in select, if there are multiple |
546 | // candidates, we prefer where-clause candidates over impls. This | |
547 | // may seem a bit surprising, since impls are the source of | |
548 | // "truth" in some sense, but in fact some of the impls that SEEM | |
549 | // applicable are not, because of nested obligations. Where | |
550 | // clauses are the safer choice. See the comment on | |
551 | // `select::SelectionCandidate` and #21974 for more details. | |
552 | if candidates.vec.len() > 1 { | |
553 | debug!("retaining param-env candidates only from {:?}", candidates.vec); | |
554 | candidates.vec.retain(|c| match *c { | |
555 | ProjectionTyCandidate::ParamEnv(..) => true, | |
556 | ProjectionTyCandidate::Impl(..) | | |
557 | ProjectionTyCandidate::Closure(..) | | |
558 | ProjectionTyCandidate::TraitDef(..) | | |
559 | ProjectionTyCandidate::FnPointer(..) => false, | |
560 | }); | |
561 | debug!("resulting candidate set: {:?}", candidates.vec); | |
562 | if candidates.vec.len() != 1 { | |
563 | return Err(ProjectionTyError::TooManyCandidates); | |
564 | } | |
1a4d82fc JJ |
565 | } |
566 | ||
e9174d1e SL |
567 | assert!(candidates.vec.len() <= 1); |
568 | ||
1a4d82fc JJ |
569 | match candidates.vec.pop() { |
570 | Some(candidate) => { | |
571 | let (ty, obligations) = confirm_candidate(selcx, obligation, candidate); | |
572 | Ok(ProjectedTy::Progress(ty, obligations)) | |
573 | } | |
574 | None => { | |
c1a9b12d SL |
575 | Ok(ProjectedTy::NoProgress(selcx.tcx().mk_projection( |
576 | obligation.predicate.trait_ref.clone(), | |
577 | obligation.predicate.item_name))) | |
1a4d82fc JJ |
578 | } |
579 | } | |
580 | } | |
581 | ||
582 | /// The first thing we have to do is scan through the parameter | |
583 | /// environment to see whether there are any projection predicates | |
584 | /// there that can answer this question. | |
585 | fn assemble_candidates_from_param_env<'cx,'tcx>( | |
586 | selcx: &mut SelectionContext<'cx,'tcx>, | |
587 | obligation: &ProjectionTyObligation<'tcx>, | |
d9579d0f | 588 | obligation_trait_ref: &ty::TraitRef<'tcx>, |
1a4d82fc JJ |
589 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>) |
590 | { | |
e9174d1e | 591 | debug!("assemble_candidates_from_param_env(..)"); |
62682a34 | 592 | let env_predicates = selcx.param_env().caller_bounds.iter().cloned(); |
e9174d1e SL |
593 | assemble_candidates_from_predicates(selcx, |
594 | obligation, | |
595 | obligation_trait_ref, | |
596 | candidate_set, | |
597 | ProjectionTyCandidate::ParamEnv, | |
598 | env_predicates); | |
1a4d82fc JJ |
599 | } |
600 | ||
85aaf69f SL |
601 | /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find |
602 | /// that the definition of `Foo` has some clues: | |
603 | /// | |
c34b1796 | 604 | /// ``` |
85aaf69f SL |
605 | /// trait Foo { |
606 | /// type FooT : Bar<BarT=i32> | |
607 | /// } | |
608 | /// ``` | |
609 | /// | |
610 | /// Here, for example, we could conclude that the result is `i32`. | |
611 | fn assemble_candidates_from_trait_def<'cx,'tcx>( | |
612 | selcx: &mut SelectionContext<'cx,'tcx>, | |
613 | obligation: &ProjectionTyObligation<'tcx>, | |
d9579d0f | 614 | obligation_trait_ref: &ty::TraitRef<'tcx>, |
85aaf69f SL |
615 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>) |
616 | { | |
e9174d1e SL |
617 | debug!("assemble_candidates_from_trait_def(..)"); |
618 | ||
85aaf69f SL |
619 | // Check whether the self-type is itself a projection. |
620 | let trait_ref = match obligation_trait_ref.self_ty().sty { | |
62682a34 SL |
621 | ty::TyProjection(ref data) => data.trait_ref.clone(), |
622 | ty::TyInfer(ty::TyVar(_)) => { | |
85aaf69f SL |
623 | // If the self-type is an inference variable, then it MAY wind up |
624 | // being a projected type, so induce an ambiguity. | |
625 | candidate_set.ambiguous = true; | |
626 | return; | |
627 | } | |
628 | _ => { return; } | |
629 | }; | |
630 | ||
631 | // If so, extract what we know from the trait and try to come up with a good answer. | |
c1a9b12d | 632 | let trait_predicates = selcx.tcx().lookup_predicates(trait_ref.def_id); |
85aaf69f | 633 | let bounds = trait_predicates.instantiate(selcx.tcx(), trait_ref.substs); |
62682a34 | 634 | let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates.into_vec()); |
e9174d1e SL |
635 | assemble_candidates_from_predicates(selcx, |
636 | obligation, | |
637 | obligation_trait_ref, | |
638 | candidate_set, | |
639 | ProjectionTyCandidate::TraitDef, | |
640 | bounds) | |
85aaf69f SL |
641 | } |
642 | ||
62682a34 | 643 | fn assemble_candidates_from_predicates<'cx,'tcx,I>( |
1a4d82fc JJ |
644 | selcx: &mut SelectionContext<'cx,'tcx>, |
645 | obligation: &ProjectionTyObligation<'tcx>, | |
d9579d0f | 646 | obligation_trait_ref: &ty::TraitRef<'tcx>, |
1a4d82fc | 647 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
e9174d1e | 648 | ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>, |
62682a34 SL |
649 | env_predicates: I) |
650 | where I: Iterator<Item=ty::Predicate<'tcx>> | |
1a4d82fc | 651 | { |
62682a34 SL |
652 | debug!("assemble_candidates_from_predicates(obligation={:?})", |
653 | obligation); | |
1a4d82fc | 654 | let infcx = selcx.infcx(); |
62682a34 SL |
655 | for predicate in env_predicates { |
656 | debug!("assemble_candidates_from_predicates: predicate={:?}", | |
657 | predicate); | |
1a4d82fc JJ |
658 | match predicate { |
659 | ty::Predicate::Projection(ref data) => { | |
660 | let same_name = data.item_name() == obligation.predicate.item_name; | |
661 | ||
662 | let is_match = same_name && infcx.probe(|_| { | |
92a42be0 | 663 | let origin = TypeOrigin::Misc(obligation.cause.span); |
1a4d82fc JJ |
664 | let data_poly_trait_ref = |
665 | data.to_poly_trait_ref(); | |
85aaf69f SL |
666 | let obligation_poly_trait_ref = |
667 | obligation_trait_ref.to_poly_trait_ref(); | |
1a4d82fc JJ |
668 | infcx.sub_poly_trait_refs(false, |
669 | origin, | |
85aaf69f SL |
670 | data_poly_trait_ref, |
671 | obligation_poly_trait_ref).is_ok() | |
1a4d82fc JJ |
672 | }); |
673 | ||
62682a34 SL |
674 | debug!("assemble_candidates_from_predicates: candidate={:?} \ |
675 | is_match={} same_name={}", | |
676 | data, is_match, same_name); | |
1a4d82fc | 677 | |
85aaf69f | 678 | if is_match { |
e9174d1e | 679 | candidate_set.vec.push(ctor(data.clone())); |
1a4d82fc JJ |
680 | } |
681 | } | |
682 | _ => { } | |
683 | } | |
684 | } | |
685 | } | |
686 | ||
687 | fn assemble_candidates_from_object_type<'cx,'tcx>( | |
688 | selcx: &mut SelectionContext<'cx,'tcx>, | |
689 | obligation: &ProjectionTyObligation<'tcx>, | |
d9579d0f | 690 | obligation_trait_ref: &ty::TraitRef<'tcx>, |
c1a9b12d | 691 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>) |
1a4d82fc | 692 | { |
c1a9b12d SL |
693 | let self_ty = obligation_trait_ref.self_ty(); |
694 | let object_ty = selcx.infcx().shallow_resolve(self_ty); | |
62682a34 SL |
695 | debug!("assemble_candidates_from_object_type(object_ty={:?})", |
696 | object_ty); | |
1a4d82fc | 697 | let data = match object_ty.sty { |
62682a34 | 698 | ty::TyTrait(ref data) => data, |
1a4d82fc JJ |
699 | _ => { |
700 | selcx.tcx().sess.span_bug( | |
701 | obligation.cause.span, | |
62682a34 SL |
702 | &format!("assemble_candidates_from_object_type called with non-object: {:?}", |
703 | object_ty)); | |
1a4d82fc JJ |
704 | } |
705 | }; | |
706 | let projection_bounds = data.projection_bounds_with_self_ty(selcx.tcx(), object_ty); | |
707 | let env_predicates = projection_bounds.iter() | |
c1a9b12d | 708 | .map(|p| p.to_predicate()) |
1a4d82fc | 709 | .collect(); |
62682a34 | 710 | let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates); |
e9174d1e SL |
711 | assemble_candidates_from_predicates(selcx, |
712 | obligation, | |
713 | obligation_trait_ref, | |
714 | candidate_set, | |
715 | ProjectionTyCandidate::ParamEnv, | |
716 | env_predicates) | |
1a4d82fc JJ |
717 | } |
718 | ||
719 | fn assemble_candidates_from_impls<'cx,'tcx>( | |
720 | selcx: &mut SelectionContext<'cx,'tcx>, | |
721 | obligation: &ProjectionTyObligation<'tcx>, | |
d9579d0f | 722 | obligation_trait_ref: &ty::TraitRef<'tcx>, |
1a4d82fc JJ |
723 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>) |
724 | -> Result<(), SelectionError<'tcx>> | |
725 | { | |
726 | // If we are resolving `<T as TraitRef<...>>::Item == Type`, | |
727 | // start out by selecting the predicate `T as TraitRef<...>`: | |
728 | let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref(); | |
729 | let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate()); | |
730 | let vtable = match selcx.select(&trait_obligation) { | |
731 | Ok(Some(vtable)) => vtable, | |
732 | Ok(None) => { | |
733 | candidate_set.ambiguous = true; | |
734 | return Ok(()); | |
735 | } | |
736 | Err(e) => { | |
62682a34 SL |
737 | debug!("assemble_candidates_from_impls: selection error {:?}", |
738 | e); | |
1a4d82fc JJ |
739 | return Err(e); |
740 | } | |
741 | }; | |
742 | ||
743 | match vtable { | |
744 | super::VtableImpl(data) => { | |
62682a34 SL |
745 | debug!("assemble_candidates_from_impls: impl candidate {:?}", |
746 | data); | |
1a4d82fc JJ |
747 | |
748 | candidate_set.vec.push( | |
749 | ProjectionTyCandidate::Impl(data)); | |
750 | } | |
c1a9b12d | 751 | super::VtableObject(_) => { |
1a4d82fc | 752 | assemble_candidates_from_object_type( |
c1a9b12d | 753 | selcx, obligation, obligation_trait_ref, candidate_set); |
1a4d82fc | 754 | } |
62682a34 | 755 | super::VtableClosure(data) => { |
85aaf69f | 756 | candidate_set.vec.push( |
62682a34 | 757 | ProjectionTyCandidate::Closure(data)); |
85aaf69f SL |
758 | } |
759 | super::VtableFnPointer(fn_type) => { | |
760 | candidate_set.vec.push( | |
761 | ProjectionTyCandidate::FnPointer(fn_type)); | |
762 | } | |
1a4d82fc JJ |
763 | super::VtableParam(..) => { |
764 | // This case tell us nothing about the value of an | |
765 | // associated type. Consider: | |
766 | // | |
767 | // ``` | |
768 | // trait SomeTrait { type Foo; } | |
769 | // fn foo<T:SomeTrait>(...) { } | |
770 | // ``` | |
771 | // | |
772 | // If the user writes `<T as SomeTrait>::Foo`, then the `T | |
773 | // : SomeTrait` binding does not help us decide what the | |
774 | // type `Foo` is (at least, not more specifically than | |
775 | // what we already knew). | |
776 | // | |
777 | // But wait, you say! What about an example like this: | |
778 | // | |
779 | // ``` | |
c34b1796 | 780 | // fn bar<T:SomeTrait<Foo=usize>>(...) { ... } |
1a4d82fc JJ |
781 | // ``` |
782 | // | |
c34b1796 | 783 | // Doesn't the `T : Sometrait<Foo=usize>` predicate help |
1a4d82fc JJ |
784 | // resolve `T::Foo`? And of course it does, but in fact |
785 | // that single predicate is desugared into two predicates | |
786 | // in the compiler: a trait predicate (`T : SomeTrait`) and a | |
787 | // projection. And the projection where clause is handled | |
788 | // in `assemble_candidates_from_param_env`. | |
789 | } | |
c34b1796 | 790 | super::VtableDefaultImpl(..) | |
85aaf69f | 791 | super::VtableBuiltin(..) => { |
1a4d82fc JJ |
792 | // These traits have no associated types. |
793 | selcx.tcx().sess.span_bug( | |
794 | obligation.cause.span, | |
62682a34 SL |
795 | &format!("Cannot project an associated type from `{:?}`", |
796 | vtable)); | |
1a4d82fc JJ |
797 | } |
798 | } | |
799 | ||
800 | Ok(()) | |
801 | } | |
802 | ||
803 | fn confirm_candidate<'cx,'tcx>( | |
804 | selcx: &mut SelectionContext<'cx,'tcx>, | |
805 | obligation: &ProjectionTyObligation<'tcx>, | |
806 | candidate: ProjectionTyCandidate<'tcx>) | |
807 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) | |
808 | { | |
62682a34 SL |
809 | debug!("confirm_candidate(candidate={:?}, obligation={:?})", |
810 | candidate, | |
811 | obligation); | |
1a4d82fc JJ |
812 | |
813 | match candidate { | |
e9174d1e SL |
814 | ProjectionTyCandidate::ParamEnv(poly_projection) | |
815 | ProjectionTyCandidate::TraitDef(poly_projection) => { | |
85aaf69f SL |
816 | confirm_param_env_candidate(selcx, obligation, poly_projection) |
817 | } | |
1a4d82fc | 818 | |
85aaf69f SL |
819 | ProjectionTyCandidate::Impl(impl_vtable) => { |
820 | confirm_impl_candidate(selcx, obligation, impl_vtable) | |
821 | } | |
1a4d82fc | 822 | |
62682a34 SL |
823 | ProjectionTyCandidate::Closure(closure_vtable) => { |
824 | confirm_closure_candidate(selcx, obligation, closure_vtable) | |
85aaf69f | 825 | } |
1a4d82fc | 826 | |
85aaf69f SL |
827 | ProjectionTyCandidate::FnPointer(fn_type) => { |
828 | confirm_fn_pointer_candidate(selcx, obligation, fn_type) | |
1a4d82fc | 829 | } |
85aaf69f SL |
830 | } |
831 | } | |
1a4d82fc | 832 | |
85aaf69f SL |
833 | fn confirm_fn_pointer_candidate<'cx,'tcx>( |
834 | selcx: &mut SelectionContext<'cx,'tcx>, | |
835 | obligation: &ProjectionTyObligation<'tcx>, | |
836 | fn_type: Ty<'tcx>) | |
837 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) | |
838 | { | |
839 | let fn_type = selcx.infcx().shallow_resolve(fn_type); | |
c1a9b12d | 840 | let sig = fn_type.fn_sig(); |
85aaf69f SL |
841 | confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes) |
842 | } | |
1a4d82fc | 843 | |
85aaf69f SL |
844 | fn confirm_closure_candidate<'cx,'tcx>( |
845 | selcx: &mut SelectionContext<'cx,'tcx>, | |
846 | obligation: &ProjectionTyObligation<'tcx>, | |
62682a34 | 847 | vtable: VtableClosureData<'tcx, PredicateObligation<'tcx>>) |
85aaf69f SL |
848 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) |
849 | { | |
850 | let closure_typer = selcx.closure_typer(); | |
62682a34 SL |
851 | let closure_type = closure_typer.closure_type(vtable.closure_def_id, &vtable.substs); |
852 | let Normalized { | |
853 | value: closure_type, | |
854 | mut obligations | |
855 | } = normalize_with_depth(selcx, | |
856 | obligation.cause.clone(), | |
857 | obligation.recursion_depth+1, | |
858 | &closure_type); | |
859 | let (ty, mut cc_obligations) = confirm_callable_candidate(selcx, | |
860 | obligation, | |
861 | &closure_type.sig, | |
862 | util::TupleArgumentsFlag::No); | |
863 | obligations.append(&mut cc_obligations); | |
864 | (ty, obligations) | |
85aaf69f | 865 | } |
1a4d82fc | 866 | |
85aaf69f SL |
867 | fn confirm_callable_candidate<'cx,'tcx>( |
868 | selcx: &mut SelectionContext<'cx,'tcx>, | |
869 | obligation: &ProjectionTyObligation<'tcx>, | |
870 | fn_sig: &ty::PolyFnSig<'tcx>, | |
871 | flag: util::TupleArgumentsFlag) | |
872 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) | |
873 | { | |
874 | let tcx = selcx.tcx(); | |
875 | ||
62682a34 SL |
876 | debug!("confirm_callable_candidate({:?},{:?})", |
877 | obligation, | |
878 | fn_sig); | |
85aaf69f | 879 | |
c34b1796 AL |
880 | // the `Output` associated type is declared on `FnOnce` |
881 | let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap(); | |
882 | ||
85aaf69f SL |
883 | // Note: we unwrap the binder here but re-create it below (1) |
884 | let ty::Binder((trait_ref, ret_type)) = | |
885 | util::closure_trait_ref_and_return_type(tcx, | |
c34b1796 | 886 | fn_once_def_id, |
85aaf69f SL |
887 | obligation.predicate.trait_ref.self_ty(), |
888 | fn_sig, | |
889 | flag); | |
890 | ||
891 | let predicate = ty::Binder(ty::ProjectionPredicate { // (1) recreate binder here | |
892 | projection_ty: ty::ProjectionTy { | |
893 | trait_ref: trait_ref, | |
894 | item_name: token::intern(FN_OUTPUT_NAME), | |
895 | }, | |
896 | ty: ret_type | |
897 | }); | |
898 | ||
899 | confirm_param_env_candidate(selcx, obligation, predicate) | |
900 | } | |
901 | ||
902 | fn confirm_param_env_candidate<'cx,'tcx>( | |
903 | selcx: &mut SelectionContext<'cx,'tcx>, | |
904 | obligation: &ProjectionTyObligation<'tcx>, | |
905 | poly_projection: ty::PolyProjectionPredicate<'tcx>) | |
906 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) | |
907 | { | |
908 | let infcx = selcx.infcx(); | |
909 | ||
910 | let projection = | |
911 | infcx.replace_late_bound_regions_with_fresh_var( | |
912 | obligation.cause.span, | |
913 | infer::LateBoundRegionConversionTime::HigherRankedType, | |
914 | &poly_projection).0; | |
915 | ||
916 | assert_eq!(projection.projection_ty.item_name, | |
917 | obligation.predicate.item_name); | |
918 | ||
92a42be0 SL |
919 | let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span); |
920 | match infcx.eq_trait_refs(false, | |
921 | origin, | |
922 | obligation.predicate.trait_ref.clone(), | |
923 | projection.projection_ty.trait_ref.clone()) { | |
85aaf69f SL |
924 | Ok(()) => { } |
925 | Err(e) => { | |
926 | selcx.tcx().sess.span_bug( | |
927 | obligation.cause.span, | |
62682a34 SL |
928 | &format!("Failed to unify `{:?}` and `{:?}` in projection: {}", |
929 | obligation, | |
930 | projection, | |
931 | e)); | |
85aaf69f SL |
932 | } |
933 | } | |
934 | ||
935 | (projection.ty, vec!()) | |
936 | } | |
937 | ||
938 | fn confirm_impl_candidate<'cx,'tcx>( | |
939 | selcx: &mut SelectionContext<'cx,'tcx>, | |
940 | obligation: &ProjectionTyObligation<'tcx>, | |
941 | impl_vtable: VtableImplData<'tcx, PredicateObligation<'tcx>>) | |
942 | -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>) | |
943 | { | |
944 | // there don't seem to be nicer accessors to these: | |
85aaf69f SL |
945 | let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow(); |
946 | ||
62682a34 SL |
947 | // Look for the associated type in the impl |
948 | for impl_item in &selcx.tcx().impl_items.borrow()[&impl_vtable.impl_def_id] { | |
949 | if let ty::TypeTraitItem(ref assoc_ty) = impl_or_trait_items_map[&impl_item.def_id()] { | |
950 | if assoc_ty.name == obligation.predicate.item_name { | |
951 | return (assoc_ty.ty.unwrap().subst(selcx.tcx(), &impl_vtable.substs), | |
952 | impl_vtable.nested); | |
953 | } | |
1a4d82fc JJ |
954 | } |
955 | } | |
1a4d82fc | 956 | |
62682a34 SL |
957 | // It is not in the impl - get the default from the trait. |
958 | let trait_ref = obligation.predicate.trait_ref; | |
c1a9b12d | 959 | for trait_item in selcx.tcx().trait_items(trait_ref.def_id).iter() { |
62682a34 SL |
960 | if let &ty::TypeTraitItem(ref assoc_ty) = trait_item { |
961 | if assoc_ty.name == obligation.predicate.item_name { | |
962 | if let Some(ty) = assoc_ty.ty { | |
963 | return (ty.subst(selcx.tcx(), trait_ref.substs), | |
964 | impl_vtable.nested); | |
965 | } else { | |
966 | // This means that the impl is missing a | |
967 | // definition for the associated type. This error | |
968 | // ought to be reported by the type checker method | |
969 | // `check_impl_items_against_trait`, so here we | |
970 | // just return TyError. | |
c1a9b12d SL |
971 | debug!("confirm_impl_candidate: no associated type {:?} for {:?}", |
972 | assoc_ty.name, | |
973 | trait_ref); | |
62682a34 SL |
974 | return (selcx.tcx().types.err, vec!()); |
975 | } | |
976 | } | |
1a4d82fc JJ |
977 | } |
978 | } | |
1a4d82fc | 979 | |
62682a34 SL |
980 | selcx.tcx().sess.span_bug(obligation.cause.span, |
981 | &format!("No associated type for {:?}", | |
982 | trait_ref)); | |
1a4d82fc | 983 | } |