]> git.proxmox.com Git - rustc.git/blame - src/librustc/middle/traits/project.rs
Imported Upstream version 1.8.0+dfsg1
[rustc.git] / src / librustc / middle / traits / project.rs
CommitLineData
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
13use super::elaborate_predicates;
c34b1796 14use super::report_overflow_error;
1a4d82fc
JJ
15use super::Obligation;
16use super::ObligationCause;
1a4d82fc
JJ
17use super::PredicateObligation;
18use super::SelectionContext;
19use super::SelectionError;
62682a34 20use super::VtableClosureData;
1a4d82fc 21use super::VtableImplData;
85aaf69f 22use super::util;
1a4d82fc 23
92a42be0 24use middle::infer::{self, TypeOrigin};
62682a34 25use middle::subst::Subst;
9cc50fc6 26use middle::ty::{self, ToPredicate, ToPolyTraitRef, Ty};
e9174d1e 27use middle::ty::fold::{TypeFoldable, TypeFolder};
85aaf69f
SL
28use syntax::parse::token;
29use util::common::FN_OUTPUT_NAME;
62682a34 30
1a4d82fc
JJ
31pub type PolyProjectionObligation<'tcx> =
32 Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
33
34pub type ProjectionObligation<'tcx> =
35 Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
36
37pub 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
42pub 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)]
51pub struct MismatchedProjectionTypes<'tcx> {
e9174d1e 52 pub err: ty::error::TypeError<'tcx>
1a4d82fc
JJ
53}
54
62682a34 55#[derive(PartialEq, Eq, Debug)]
1a4d82fc 56enum 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
73struct 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
83pub 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
116fn 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
148fn 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
201pub 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
211pub 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
227struct 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
234impl<'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
259impl<'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
309pub struct Normalized<'tcx,T> {
310 pub value: T,
311 pub obligations: Vec<PredicateObligation<'tcx>>,
312}
313
314pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
315
316impl<'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
328pub 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
359fn 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
448fn 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
465enum 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).
471fn 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.
585fn 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`.
611fn 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 643fn 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
687fn 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
719fn 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
803fn 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
833fn 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
844fn 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
867fn 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
902fn 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
938fn 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}