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.
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.
11 //! Code for projecting associated types out of trait references.
13 use super::elaborate_predicates;
14 use super::report_overflow_error;
15 use super::Obligation;
16 use super::ObligationCause;
17 use super::PredicateObligation;
18 use super::SelectionContext;
19 use super::SelectionError;
20 use super::VtableClosureData;
21 use super::VtableImplData;
24 use middle::infer::{self, TypeOrigin};
25 use middle::subst::Subst;
26 use middle::ty::{self, ToPredicate, ToPolyTraitRef, Ty};
27 use middle::ty::fold::{TypeFoldable, TypeFolder};
28 use syntax::parse::token;
29 use util::common::FN_OUTPUT_NAME;
31 pub type PolyProjectionObligation<'tcx> =
32 Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
34 pub type ProjectionObligation<'tcx> =
35 Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
37 pub type ProjectionTyObligation<'tcx> =
38 Obligation<'tcx, ty::ProjectionTy<'tcx>>;
40 /// When attempting to resolve `<T as TraitRef>::Name` ...
42 pub enum ProjectionTyError<'tcx> {
43 /// ...we found multiple sources of information and couldn't resolve the ambiguity.
46 /// ...an error occurred matching `T : TraitRef`
47 TraitSelectionError(SelectionError<'tcx>),
51 pub struct MismatchedProjectionTypes<'tcx> {
52 pub err: ty::error::TypeError<'tcx>
55 #[derive(PartialEq, Eq, Debug)]
56 enum ProjectionTyCandidate<'tcx> {
57 // from a where-clause in the env or object type
58 ParamEnv(ty::PolyProjectionPredicate<'tcx>),
60 // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
61 TraitDef(ty::PolyProjectionPredicate<'tcx>),
64 Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
66 // closure return type
67 Closure(VtableClosureData<'tcx, PredicateObligation<'tcx>>),
69 // fn pointer return type
73 struct ProjectionTyCandidateSet<'tcx> {
74 vec: Vec<ProjectionTyCandidate<'tcx>>,
78 /// Evaluates constraints of the form:
80 /// for<...> <T as Trait>::U == V
82 /// If successful, this may result in additional obligations.
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>>
88 debug!("poly_project_and_unify_type(obligation={:?})",
91 let infcx = selcx.infcx();
92 infcx.commit_if_ok(|snapshot| {
93 let (skol_predicate, skol_map) =
94 infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
96 let skol_obligation = obligation.with(skol_predicate);
97 match project_and_unify_type(selcx, &skol_obligation) {
99 match infcx.leak_check(&skol_map, snapshot) {
100 Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, &result)),
101 Err(e) => Err(MismatchedProjectionTypes { err: e }),
111 /// Evaluates constraints of the form:
113 /// <T as Trait>::U == V
115 /// If successful, this may result in additional obligations.
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>>
121 debug!("project_and_unify_type(obligation={:?})",
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) {
131 consider_unification_despite_ambiguity(selcx, obligation);
136 debug!("project_and_unify_type: normalized_ty={:?} obligations={:?}",
140 let infcx = selcx.infcx();
141 let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
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 }),
148 fn consider_unification_despite_ambiguity<'cx,'tcx>(selcx: &mut SelectionContext<'cx,'tcx>,
149 obligation: &ProjectionObligation<'tcx>) {
150 debug!("consider_unification_despite_ambiguity(obligation={:?})",
153 let def_id = obligation.predicate.projection_ty.trait_ref.def_id;
154 match selcx.tcx().lang_items.fn_trait_kind(def_id) {
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={:?}",
165 ty::TyClosure(closure_def_id, ref substs) => {
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,
173 util::TupleArgumentsFlag::No);
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.
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));
184 debug!("consider_unification_despite_ambiguity: ret_type={:?}",
186 let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
187 let obligation_ty = obligation.predicate.ty;
188 match infer::mk_eqty(infcx, true, origin, obligation_ty, ret_type) {
190 Err(_) => { /* ignore errors */ }
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.
201 pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
202 cause: ObligationCause<'tcx>,
204 -> Normalized<'tcx, T>
205 where T : TypeFoldable<'tcx>
207 normalize_with_depth(selcx, cause, 0, value)
210 /// As `normalize`, but with a custom depth.
211 pub fn normalize_with_depth<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
212 cause: ObligationCause<'tcx>,
215 -> Normalized<'tcx, T>
216 where T : TypeFoldable<'tcx>
218 let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
219 let result = normalizer.fold(value);
223 obligations: normalizer.obligations,
227 struct AssociatedTypeNormalizer<'a,'b:'a,'tcx:'b> {
228 selcx: &'a mut SelectionContext<'b,'tcx>,
229 cause: ObligationCause<'tcx>,
230 obligations: Vec<PredicateObligation<'tcx>>,
234 impl<'a,'b,'tcx> AssociatedTypeNormalizer<'a,'b,'tcx> {
235 fn new(selcx: &'a mut SelectionContext<'b,'tcx>,
236 cause: ObligationCause<'tcx>,
238 -> AssociatedTypeNormalizer<'a,'b,'tcx>
240 AssociatedTypeNormalizer {
248 fn fold<T:TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
249 let value = self.selcx.infcx().resolve_type_vars_if_possible(value);
251 if !value.has_projection_types() {
254 value.fold_with(self)
259 impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
260 fn tcx(&self) -> &ty::ctxt<'tcx> {
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.
270 // for<'a> fn(<T as Foo<&'a>>::A)
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).
276 let ty = ty.super_fold_with(self);
278 ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*)
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.
292 let Normalized { value: ty, obligations } =
293 normalize_projection_type(self.selcx,
297 self.obligations.extend(obligations);
309 pub struct Normalized<'tcx,T> {
311 pub obligations: Vec<PredicateObligation<'tcx>>,
314 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
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 }
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.
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>,
333 -> NormalizedTy<'tcx>
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.
341 let ty_var = selcx.infcx().next_ty_var();
342 let projection = ty::Binder(ty::ProjectionPredicate {
343 projection_ty: projection_ty,
346 let obligation = Obligation::with_depth(
347 cause, depth + 1, projection.to_predicate());
350 obligations: vec!(obligation)
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.
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>,
364 -> Option<NormalizedTy<'tcx>>
366 debug!("normalize_projection_type(\
367 projection_ty={:?}, \
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
380 debug!("normalize_projection_type: projected_ty={:?} depth={} obligations={:?}",
385 if projected_ty.has_projection_types() {
386 let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth+1);
387 let normalized_ty = normalizer.fold(&projected_ty);
389 debug!("normalize_projection_type: normalized_ty={:?} depth={}",
393 obligations.extend(normalizer.obligations);
395 value: normalized_ty,
396 obligations: obligations,
401 obligations: obligations,
405 Ok(ProjectedTy::NoProgress(projected_ty)) => {
406 debug!("normalize_projection_type: projected_ty={:?} no progress",
413 Err(ProjectionTyError::TooManyCandidates) => {
414 debug!("normalize_projection_type: too many candidates");
417 Err(ProjectionTyError::TraitSelectionError(_)) => {
418 debug!("normalize_projection_type: ERROR");
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
424 Some(normalize_to_error(selcx, projection_ty, cause, depth))
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
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.)
448 fn normalize_to_error<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
449 projection_ty: ty::ProjectionTy<'tcx>,
450 cause: ObligationCause<'tcx>,
452 -> NormalizedTy<'tcx>
454 let trait_ref = projection_ty.trait_ref.to_poly_trait_ref();
455 let trait_obligation = Obligation { cause: cause,
456 recursion_depth: depth,
457 predicate: trait_ref.to_predicate() };
458 let new_value = selcx.infcx().next_ty_var();
461 obligations: vec!(trait_obligation)
465 enum ProjectedTy<'tcx> {
466 Progress(Ty<'tcx>, Vec<PredicateObligation<'tcx>>),
467 NoProgress(Ty<'tcx>),
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>>
476 debug!("project(obligation={:?})",
479 let recursion_limit = selcx.tcx().sess.recursion_limit.get();
480 if obligation.recursion_depth >= recursion_limit {
481 debug!("project: overflow!");
482 report_overflow_error(selcx.infcx(), &obligation, true);
485 let obligation_trait_ref =
486 selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate.trait_ref);
488 debug!("project: obligation_trait_ref={:?}", obligation_trait_ref);
490 if obligation_trait_ref.references_error() {
491 return Ok(ProjectedTy::Progress(selcx.tcx().types.err, vec!()));
494 let mut candidates = ProjectionTyCandidateSet {
499 assemble_candidates_from_param_env(selcx,
501 &obligation_trait_ref,
504 assemble_candidates_from_trait_def(selcx,
506 &obligation_trait_ref,
509 if let Err(e) = assemble_candidates_from_impls(selcx,
511 &obligation_trait_ref,
513 return Err(ProjectionTyError::TraitSelectionError(e));
516 debug!("{} candidates, ambiguous={}",
517 candidates.vec.len(),
518 candidates.ambiguous);
520 // Inherent ambiguity that prevents us from even enumerating the
522 if candidates.ambiguous {
523 return Err(ProjectionTyError::TooManyCandidates);
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 {
535 while i < candidates.vec.len() {
536 let has_dup = (0..i).any(|j| candidates.vec[i] == candidates.vec[j]);
538 candidates.vec.swap_remove(i);
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,
561 debug!("resulting candidate set: {:?}", candidates.vec);
562 if candidates.vec.len() != 1 {
563 return Err(ProjectionTyError::TooManyCandidates);
567 assert!(candidates.vec.len() <= 1);
569 match candidates.vec.pop() {
571 let (ty, obligations) = confirm_candidate(selcx, obligation, candidate);
572 Ok(ProjectedTy::Progress(ty, obligations))
575 Ok(ProjectedTy::NoProgress(selcx.tcx().mk_projection(
576 obligation.predicate.trait_ref.clone(),
577 obligation.predicate.item_name)))
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>,
588 obligation_trait_ref: &ty::TraitRef<'tcx>,
589 candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
591 debug!("assemble_candidates_from_param_env(..)");
592 let env_predicates = selcx.param_env().caller_bounds.iter().cloned();
593 assemble_candidates_from_predicates(selcx,
595 obligation_trait_ref,
597 ProjectionTyCandidate::ParamEnv,
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:
606 /// type FooT : Bar<BarT=i32>
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>,
614 obligation_trait_ref: &ty::TraitRef<'tcx>,
615 candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
617 debug!("assemble_candidates_from_trait_def(..)");
619 // Check whether the self-type is itself a projection.
620 let trait_ref = match obligation_trait_ref.self_ty().sty {
621 ty::TyProjection(ref data) => data.trait_ref.clone(),
622 ty::TyInfer(ty::TyVar(_)) => {
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;
631 // If so, extract what we know from the trait and try to come up with a good answer.
632 let trait_predicates = selcx.tcx().lookup_predicates(trait_ref.def_id);
633 let bounds = trait_predicates.instantiate(selcx.tcx(), trait_ref.substs);
634 let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates.into_vec());
635 assemble_candidates_from_predicates(selcx,
637 obligation_trait_ref,
639 ProjectionTyCandidate::TraitDef,
643 fn assemble_candidates_from_predicates<'cx,'tcx,I>(
644 selcx: &mut SelectionContext<'cx,'tcx>,
645 obligation: &ProjectionTyObligation<'tcx>,
646 obligation_trait_ref: &ty::TraitRef<'tcx>,
647 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
648 ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
650 where I: Iterator<Item=ty::Predicate<'tcx>>
652 debug!("assemble_candidates_from_predicates(obligation={:?})",
654 let infcx = selcx.infcx();
655 for predicate in env_predicates {
656 debug!("assemble_candidates_from_predicates: predicate={:?}",
659 ty::Predicate::Projection(ref data) => {
660 let same_name = data.item_name() == obligation.predicate.item_name;
662 let is_match = same_name && infcx.probe(|_| {
663 let origin = TypeOrigin::Misc(obligation.cause.span);
664 let data_poly_trait_ref =
665 data.to_poly_trait_ref();
666 let obligation_poly_trait_ref =
667 obligation_trait_ref.to_poly_trait_ref();
668 infcx.sub_poly_trait_refs(false,
671 obligation_poly_trait_ref).is_ok()
674 debug!("assemble_candidates_from_predicates: candidate={:?} \
675 is_match={} same_name={}",
676 data, is_match, same_name);
679 candidate_set.vec.push(ctor(data.clone()));
687 fn assemble_candidates_from_object_type<'cx,'tcx>(
688 selcx: &mut SelectionContext<'cx,'tcx>,
689 obligation: &ProjectionTyObligation<'tcx>,
690 obligation_trait_ref: &ty::TraitRef<'tcx>,
691 candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
693 let self_ty = obligation_trait_ref.self_ty();
694 let object_ty = selcx.infcx().shallow_resolve(self_ty);
695 debug!("assemble_candidates_from_object_type(object_ty={:?})",
697 let data = match object_ty.sty {
698 ty::TyTrait(ref data) => data,
700 selcx.tcx().sess.span_bug(
701 obligation.cause.span,
702 &format!("assemble_candidates_from_object_type called with non-object: {:?}",
706 let projection_bounds = data.projection_bounds_with_self_ty(selcx.tcx(), object_ty);
707 let env_predicates = projection_bounds.iter()
708 .map(|p| p.to_predicate())
710 let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
711 assemble_candidates_from_predicates(selcx,
713 obligation_trait_ref,
715 ProjectionTyCandidate::ParamEnv,
719 fn assemble_candidates_from_impls<'cx,'tcx>(
720 selcx: &mut SelectionContext<'cx,'tcx>,
721 obligation: &ProjectionTyObligation<'tcx>,
722 obligation_trait_ref: &ty::TraitRef<'tcx>,
723 candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
724 -> Result<(), SelectionError<'tcx>>
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,
733 candidate_set.ambiguous = true;
737 debug!("assemble_candidates_from_impls: selection error {:?}",
744 super::VtableImpl(data) => {
745 debug!("assemble_candidates_from_impls: impl candidate {:?}",
748 candidate_set.vec.push(
749 ProjectionTyCandidate::Impl(data));
751 super::VtableObject(_) => {
752 assemble_candidates_from_object_type(
753 selcx, obligation, obligation_trait_ref, candidate_set);
755 super::VtableClosure(data) => {
756 candidate_set.vec.push(
757 ProjectionTyCandidate::Closure(data));
759 super::VtableFnPointer(fn_type) => {
760 candidate_set.vec.push(
761 ProjectionTyCandidate::FnPointer(fn_type));
763 super::VtableParam(..) => {
764 // This case tell us nothing about the value of an
765 // associated type. Consider:
768 // trait SomeTrait { type Foo; }
769 // fn foo<T:SomeTrait>(...) { }
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).
777 // But wait, you say! What about an example like this:
780 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
783 // Doesn't the `T : Sometrait<Foo=usize>` predicate help
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`.
790 super::VtableDefaultImpl(..) |
791 super::VtableBuiltin(..) => {
792 // These traits have no associated types.
793 selcx.tcx().sess.span_bug(
794 obligation.cause.span,
795 &format!("Cannot project an associated type from `{:?}`",
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>>)
809 debug!("confirm_candidate(candidate={:?}, obligation={:?})",
814 ProjectionTyCandidate::ParamEnv(poly_projection) |
815 ProjectionTyCandidate::TraitDef(poly_projection) => {
816 confirm_param_env_candidate(selcx, obligation, poly_projection)
819 ProjectionTyCandidate::Impl(impl_vtable) => {
820 confirm_impl_candidate(selcx, obligation, impl_vtable)
823 ProjectionTyCandidate::Closure(closure_vtable) => {
824 confirm_closure_candidate(selcx, obligation, closure_vtable)
827 ProjectionTyCandidate::FnPointer(fn_type) => {
828 confirm_fn_pointer_candidate(selcx, obligation, fn_type)
833 fn confirm_fn_pointer_candidate<'cx,'tcx>(
834 selcx: &mut SelectionContext<'cx,'tcx>,
835 obligation: &ProjectionTyObligation<'tcx>,
837 -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
839 let fn_type = selcx.infcx().shallow_resolve(fn_type);
840 let sig = fn_type.fn_sig();
841 confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
844 fn confirm_closure_candidate<'cx,'tcx>(
845 selcx: &mut SelectionContext<'cx,'tcx>,
846 obligation: &ProjectionTyObligation<'tcx>,
847 vtable: VtableClosureData<'tcx, PredicateObligation<'tcx>>)
848 -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
850 let closure_typer = selcx.closure_typer();
851 let closure_type = closure_typer.closure_type(vtable.closure_def_id, &vtable.substs);
855 } = normalize_with_depth(selcx,
856 obligation.cause.clone(),
857 obligation.recursion_depth+1,
859 let (ty, mut cc_obligations) = confirm_callable_candidate(selcx,
862 util::TupleArgumentsFlag::No);
863 obligations.append(&mut cc_obligations);
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>>)
874 let tcx = selcx.tcx();
876 debug!("confirm_callable_candidate({:?},{:?})",
880 // the `Output` associated type is declared on `FnOnce`
881 let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap();
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,
887 obligation.predicate.trait_ref.self_ty(),
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),
899 confirm_param_env_candidate(selcx, obligation, predicate)
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>>)
908 let infcx = selcx.infcx();
911 infcx.replace_late_bound_regions_with_fresh_var(
912 obligation.cause.span,
913 infer::LateBoundRegionConversionTime::HigherRankedType,
916 assert_eq!(projection.projection_ty.item_name,
917 obligation.predicate.item_name);
919 let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
920 match infcx.eq_trait_refs(false,
922 obligation.predicate.trait_ref.clone(),
923 projection.projection_ty.trait_ref.clone()) {
926 selcx.tcx().sess.span_bug(
927 obligation.cause.span,
928 &format!("Failed to unify `{:?}` and `{:?}` in projection: {}",
935 (projection.ty, vec!())
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>>)
944 // there don't seem to be nicer accessors to these:
945 let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow();
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),
957 // It is not in the impl - get the default from the trait.
958 let trait_ref = obligation.predicate.trait_ref;
959 for trait_item in selcx.tcx().trait_items(trait_ref.def_id).iter() {
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),
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.
971 debug!("confirm_impl_candidate: no associated type {:?} for {:?}",
974 return (selcx.tcx().types.err, vec!());
980 selcx.tcx().sess.span_bug(obligation.cause.span,
981 &format!("No associated type for {:?}",