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
;
25 use middle
::subst
::Subst
;
26 use middle
::ty
::{self, ToPredicate, RegionEscape, HasTypeFlags, 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
= infer
::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
= infer
::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
> + HasTypeFlags
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
> + HasTypeFlags
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
> + HasTypeFlags
>(&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
::fold
::super_fold_ty(self, ty
);
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(cause
, depth
+1, projection
.to_predicate());
349 obligations
: vec
!(obligation
)
354 /// The guts of `normalize`: normalize a specific projection like `<T
355 /// as Trait>::Item`. The result is always a type (and possibly
356 /// additional obligations). Returns `None` in the case of ambiguity,
357 /// which indicates that there are unbound type variables.
358 fn opt_normalize_projection_type
<'a
,'b
,'tcx
>(
359 selcx
: &'a
mut SelectionContext
<'b
,'tcx
>,
360 projection_ty
: ty
::ProjectionTy
<'tcx
>,
361 cause
: ObligationCause
<'tcx
>,
363 -> Option
<NormalizedTy
<'tcx
>>
365 debug
!("normalize_projection_type(\
366 projection_ty={:?}, \
371 let obligation
= Obligation
::with_depth(cause
.clone(), depth
, projection_ty
.clone());
372 match project_type(selcx
, &obligation
) {
373 Ok(ProjectedTy
::Progress(projected_ty
, mut obligations
)) => {
374 // if projection succeeded, then what we get out of this
375 // is also non-normalized (consider: it was derived from
376 // an impl, where-clause etc) and hence we must
379 debug
!("normalize_projection_type: projected_ty={:?} depth={} obligations={:?}",
384 if projected_ty
.has_projection_types() {
385 let mut normalizer
= AssociatedTypeNormalizer
::new(selcx
, cause
, depth
);
386 let normalized_ty
= normalizer
.fold(&projected_ty
);
388 debug
!("normalize_projection_type: normalized_ty={:?} depth={}",
392 obligations
.extend(normalizer
.obligations
);
394 value
: normalized_ty
,
395 obligations
: obligations
,
400 obligations
: obligations
,
404 Ok(ProjectedTy
::NoProgress(projected_ty
)) => {
405 debug
!("normalize_projection_type: projected_ty={:?} no progress",
412 Err(ProjectionTyError
::TooManyCandidates
) => {
413 debug
!("normalize_projection_type: too many candidates");
416 Err(ProjectionTyError
::TraitSelectionError(_
)) => {
417 debug
!("normalize_projection_type: ERROR");
418 // if we got an error processing the `T as Trait` part,
419 // just return `ty::err` but add the obligation `T :
420 // Trait`, which when processed will cause the error to be
423 Some(normalize_to_error(selcx
, projection_ty
, cause
, depth
))
428 /// in various error cases, we just set TyError and return an obligation
429 /// that, when fulfilled, will lead to an error.
431 /// FIXME: the TyError created here can enter the obligation we create,
432 /// leading to error messages involving TyError.
433 fn normalize_to_error
<'a
,'tcx
>(selcx
: &mut SelectionContext
<'a
,'tcx
>,
434 projection_ty
: ty
::ProjectionTy
<'tcx
>,
435 cause
: ObligationCause
<'tcx
>,
437 -> NormalizedTy
<'tcx
>
439 let trait_ref
= projection_ty
.trait_ref
.to_poly_trait_ref();
440 let trait_obligation
= Obligation
{ cause
: cause
,
441 recursion_depth
: depth
,
442 predicate
: trait_ref
.to_predicate() };
444 value
: selcx
.tcx().types
.err
,
445 obligations
: vec
!(trait_obligation
)
449 enum ProjectedTy
<'tcx
> {
450 Progress(Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>),
451 NoProgress(Ty
<'tcx
>),
454 /// Compute the result of a projection type (if we can).
455 fn project_type
<'cx
,'tcx
>(
456 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
457 obligation
: &ProjectionTyObligation
<'tcx
>)
458 -> Result
<ProjectedTy
<'tcx
>, ProjectionTyError
<'tcx
>>
460 debug
!("project(obligation={:?})",
463 let recursion_limit
= selcx
.tcx().sess
.recursion_limit
.get();
464 if obligation
.recursion_depth
>= recursion_limit
{
465 debug
!("project: overflow!");
466 report_overflow_error(selcx
.infcx(), &obligation
);
469 let obligation_trait_ref
=
470 selcx
.infcx().resolve_type_vars_if_possible(&obligation
.predicate
.trait_ref
);
472 debug
!("project: obligation_trait_ref={:?}", obligation_trait_ref
);
474 if obligation_trait_ref
.references_error() {
475 return Ok(ProjectedTy
::Progress(selcx
.tcx().types
.err
, vec
!()));
478 let mut candidates
= ProjectionTyCandidateSet
{
483 assemble_candidates_from_param_env(selcx
,
485 &obligation_trait_ref
,
488 assemble_candidates_from_trait_def(selcx
,
490 &obligation_trait_ref
,
493 if let Err(e
) = assemble_candidates_from_impls(selcx
,
495 &obligation_trait_ref
,
497 return Err(ProjectionTyError
::TraitSelectionError(e
));
500 debug
!("{} candidates, ambiguous={}",
501 candidates
.vec
.len(),
502 candidates
.ambiguous
);
504 // Inherent ambiguity that prevents us from even enumerating the
506 if candidates
.ambiguous
{
507 return Err(ProjectionTyError
::TooManyCandidates
);
512 // Note: `candidates.vec` seems to be on the critical path of the
513 // compiler. Replacing it with an hash set was also tried, which would
514 // render the following dedup unnecessary. It led to cleaner code but
515 // prolonged compiling time of `librustc` from 5m30s to 6m in one test, or
516 // ~9% performance lost.
517 if candidates
.vec
.len() > 1 {
519 while i
< candidates
.vec
.len() {
520 let has_dup
= (0..i
).any(|j
| candidates
.vec
[i
] == candidates
.vec
[j
]);
522 candidates
.vec
.swap_remove(i
);
529 // Prefer where-clauses. As in select, if there are multiple
530 // candidates, we prefer where-clause candidates over impls. This
531 // may seem a bit surprising, since impls are the source of
532 // "truth" in some sense, but in fact some of the impls that SEEM
533 // applicable are not, because of nested obligations. Where
534 // clauses are the safer choice. See the comment on
535 // `select::SelectionCandidate` and #21974 for more details.
536 if candidates
.vec
.len() > 1 {
537 debug
!("retaining param-env candidates only from {:?}", candidates
.vec
);
538 candidates
.vec
.retain(|c
| match *c
{
539 ProjectionTyCandidate
::ParamEnv(..) => true,
540 ProjectionTyCandidate
::Impl(..) |
541 ProjectionTyCandidate
::Closure(..) |
542 ProjectionTyCandidate
::TraitDef(..) |
543 ProjectionTyCandidate
::FnPointer(..) => false,
545 debug
!("resulting candidate set: {:?}", candidates
.vec
);
546 if candidates
.vec
.len() != 1 {
547 return Err(ProjectionTyError
::TooManyCandidates
);
551 assert
!(candidates
.vec
.len() <= 1);
553 match candidates
.vec
.pop() {
555 let (ty
, obligations
) = confirm_candidate(selcx
, obligation
, candidate
);
556 Ok(ProjectedTy
::Progress(ty
, obligations
))
559 Ok(ProjectedTy
::NoProgress(selcx
.tcx().mk_projection(
560 obligation
.predicate
.trait_ref
.clone(),
561 obligation
.predicate
.item_name
)))
566 /// The first thing we have to do is scan through the parameter
567 /// environment to see whether there are any projection predicates
568 /// there that can answer this question.
569 fn assemble_candidates_from_param_env
<'cx
,'tcx
>(
570 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
571 obligation
: &ProjectionTyObligation
<'tcx
>,
572 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
573 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>)
575 debug
!("assemble_candidates_from_param_env(..)");
576 let env_predicates
= selcx
.param_env().caller_bounds
.iter().cloned();
577 assemble_candidates_from_predicates(selcx
,
579 obligation_trait_ref
,
581 ProjectionTyCandidate
::ParamEnv
,
585 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
586 /// that the definition of `Foo` has some clues:
590 /// type FooT : Bar<BarT=i32>
594 /// Here, for example, we could conclude that the result is `i32`.
595 fn assemble_candidates_from_trait_def
<'cx
,'tcx
>(
596 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
597 obligation
: &ProjectionTyObligation
<'tcx
>,
598 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
599 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>)
601 debug
!("assemble_candidates_from_trait_def(..)");
603 // Check whether the self-type is itself a projection.
604 let trait_ref
= match obligation_trait_ref
.self_ty().sty
{
605 ty
::TyProjection(ref data
) => data
.trait_ref
.clone(),
606 ty
::TyInfer(ty
::TyVar(_
)) => {
607 // If the self-type is an inference variable, then it MAY wind up
608 // being a projected type, so induce an ambiguity.
609 candidate_set
.ambiguous
= true;
615 // If so, extract what we know from the trait and try to come up with a good answer.
616 let trait_predicates
= selcx
.tcx().lookup_predicates(trait_ref
.def_id
);
617 let bounds
= trait_predicates
.instantiate(selcx
.tcx(), trait_ref
.substs
);
618 let bounds
= elaborate_predicates(selcx
.tcx(), bounds
.predicates
.into_vec());
619 assemble_candidates_from_predicates(selcx
,
621 obligation_trait_ref
,
623 ProjectionTyCandidate
::TraitDef
,
627 fn assemble_candidates_from_predicates
<'cx
,'tcx
,I
>(
628 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
629 obligation
: &ProjectionTyObligation
<'tcx
>,
630 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
631 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>,
632 ctor
: fn(ty
::PolyProjectionPredicate
<'tcx
>) -> ProjectionTyCandidate
<'tcx
>,
634 where I
: Iterator
<Item
=ty
::Predicate
<'tcx
>>
636 debug
!("assemble_candidates_from_predicates(obligation={:?})",
638 let infcx
= selcx
.infcx();
639 for predicate
in env_predicates
{
640 debug
!("assemble_candidates_from_predicates: predicate={:?}",
643 ty
::Predicate
::Projection(ref data
) => {
644 let same_name
= data
.item_name() == obligation
.predicate
.item_name
;
646 let is_match
= same_name
&& infcx
.probe(|_
| {
647 let origin
= infer
::Misc(obligation
.cause
.span
);
648 let data_poly_trait_ref
=
649 data
.to_poly_trait_ref();
650 let obligation_poly_trait_ref
=
651 obligation_trait_ref
.to_poly_trait_ref();
652 infcx
.sub_poly_trait_refs(false,
655 obligation_poly_trait_ref
).is_ok()
658 debug
!("assemble_candidates_from_predicates: candidate={:?} \
659 is_match={} same_name={}",
660 data
, is_match
, same_name
);
663 candidate_set
.vec
.push(ctor(data
.clone()));
671 fn assemble_candidates_from_object_type
<'cx
,'tcx
>(
672 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
673 obligation
: &ProjectionTyObligation
<'tcx
>,
674 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
675 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>)
677 let self_ty
= obligation_trait_ref
.self_ty();
678 let object_ty
= selcx
.infcx().shallow_resolve(self_ty
);
679 debug
!("assemble_candidates_from_object_type(object_ty={:?})",
681 let data
= match object_ty
.sty
{
682 ty
::TyTrait(ref data
) => data
,
684 selcx
.tcx().sess
.span_bug(
685 obligation
.cause
.span
,
686 &format
!("assemble_candidates_from_object_type called with non-object: {:?}",
690 let projection_bounds
= data
.projection_bounds_with_self_ty(selcx
.tcx(), object_ty
);
691 let env_predicates
= projection_bounds
.iter()
692 .map(|p
| p
.to_predicate())
694 let env_predicates
= elaborate_predicates(selcx
.tcx(), env_predicates
);
695 assemble_candidates_from_predicates(selcx
,
697 obligation_trait_ref
,
699 ProjectionTyCandidate
::ParamEnv
,
703 fn assemble_candidates_from_impls
<'cx
,'tcx
>(
704 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
705 obligation
: &ProjectionTyObligation
<'tcx
>,
706 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
707 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>)
708 -> Result
<(), SelectionError
<'tcx
>>
710 // If we are resolving `<T as TraitRef<...>>::Item == Type`,
711 // start out by selecting the predicate `T as TraitRef<...>`:
712 let poly_trait_ref
= obligation_trait_ref
.to_poly_trait_ref();
713 let trait_obligation
= obligation
.with(poly_trait_ref
.to_poly_trait_predicate());
714 let vtable
= match selcx
.select(&trait_obligation
) {
715 Ok(Some(vtable
)) => vtable
,
717 candidate_set
.ambiguous
= true;
721 debug
!("assemble_candidates_from_impls: selection error {:?}",
728 super::VtableImpl(data
) => {
729 debug
!("assemble_candidates_from_impls: impl candidate {:?}",
732 candidate_set
.vec
.push(
733 ProjectionTyCandidate
::Impl(data
));
735 super::VtableObject(_
) => {
736 assemble_candidates_from_object_type(
737 selcx
, obligation
, obligation_trait_ref
, candidate_set
);
739 super::VtableClosure(data
) => {
740 candidate_set
.vec
.push(
741 ProjectionTyCandidate
::Closure(data
));
743 super::VtableFnPointer(fn_type
) => {
744 candidate_set
.vec
.push(
745 ProjectionTyCandidate
::FnPointer(fn_type
));
747 super::VtableParam(..) => {
748 // This case tell us nothing about the value of an
749 // associated type. Consider:
752 // trait SomeTrait { type Foo; }
753 // fn foo<T:SomeTrait>(...) { }
756 // If the user writes `<T as SomeTrait>::Foo`, then the `T
757 // : SomeTrait` binding does not help us decide what the
758 // type `Foo` is (at least, not more specifically than
759 // what we already knew).
761 // But wait, you say! What about an example like this:
764 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
767 // Doesn't the `T : Sometrait<Foo=usize>` predicate help
768 // resolve `T::Foo`? And of course it does, but in fact
769 // that single predicate is desugared into two predicates
770 // in the compiler: a trait predicate (`T : SomeTrait`) and a
771 // projection. And the projection where clause is handled
772 // in `assemble_candidates_from_param_env`.
774 super::VtableDefaultImpl(..) |
775 super::VtableBuiltin(..) => {
776 // These traits have no associated types.
777 selcx
.tcx().sess
.span_bug(
778 obligation
.cause
.span
,
779 &format
!("Cannot project an associated type from `{:?}`",
787 fn confirm_candidate
<'cx
,'tcx
>(
788 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
789 obligation
: &ProjectionTyObligation
<'tcx
>,
790 candidate
: ProjectionTyCandidate
<'tcx
>)
791 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
793 debug
!("confirm_candidate(candidate={:?}, obligation={:?})",
798 ProjectionTyCandidate
::ParamEnv(poly_projection
) |
799 ProjectionTyCandidate
::TraitDef(poly_projection
) => {
800 confirm_param_env_candidate(selcx
, obligation
, poly_projection
)
803 ProjectionTyCandidate
::Impl(impl_vtable
) => {
804 confirm_impl_candidate(selcx
, obligation
, impl_vtable
)
807 ProjectionTyCandidate
::Closure(closure_vtable
) => {
808 confirm_closure_candidate(selcx
, obligation
, closure_vtable
)
811 ProjectionTyCandidate
::FnPointer(fn_type
) => {
812 confirm_fn_pointer_candidate(selcx
, obligation
, fn_type
)
817 fn confirm_fn_pointer_candidate
<'cx
,'tcx
>(
818 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
819 obligation
: &ProjectionTyObligation
<'tcx
>,
821 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
823 let fn_type
= selcx
.infcx().shallow_resolve(fn_type
);
824 let sig
= fn_type
.fn_sig();
825 confirm_callable_candidate(selcx
, obligation
, sig
, util
::TupleArgumentsFlag
::Yes
)
828 fn confirm_closure_candidate
<'cx
,'tcx
>(
829 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
830 obligation
: &ProjectionTyObligation
<'tcx
>,
831 vtable
: VtableClosureData
<'tcx
, PredicateObligation
<'tcx
>>)
832 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
834 let closure_typer
= selcx
.closure_typer();
835 let closure_type
= closure_typer
.closure_type(vtable
.closure_def_id
, &vtable
.substs
);
839 } = normalize_with_depth(selcx
,
840 obligation
.cause
.clone(),
841 obligation
.recursion_depth
+1,
843 let (ty
, mut cc_obligations
) = confirm_callable_candidate(selcx
,
846 util
::TupleArgumentsFlag
::No
);
847 obligations
.append(&mut cc_obligations
);
851 fn confirm_callable_candidate
<'cx
,'tcx
>(
852 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
853 obligation
: &ProjectionTyObligation
<'tcx
>,
854 fn_sig
: &ty
::PolyFnSig
<'tcx
>,
855 flag
: util
::TupleArgumentsFlag
)
856 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
858 let tcx
= selcx
.tcx();
860 debug
!("confirm_callable_candidate({:?},{:?})",
864 // the `Output` associated type is declared on `FnOnce`
865 let fn_once_def_id
= tcx
.lang_items
.fn_once_trait().unwrap();
867 // Note: we unwrap the binder here but re-create it below (1)
868 let ty
::Binder((trait_ref
, ret_type
)) =
869 util
::closure_trait_ref_and_return_type(tcx
,
871 obligation
.predicate
.trait_ref
.self_ty(),
875 let predicate
= ty
::Binder(ty
::ProjectionPredicate
{ // (1) recreate binder here
876 projection_ty
: ty
::ProjectionTy
{
877 trait_ref
: trait_ref
,
878 item_name
: token
::intern(FN_OUTPUT_NAME
),
883 confirm_param_env_candidate(selcx
, obligation
, predicate
)
886 fn confirm_param_env_candidate
<'cx
,'tcx
>(
887 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
888 obligation
: &ProjectionTyObligation
<'tcx
>,
889 poly_projection
: ty
::PolyProjectionPredicate
<'tcx
>)
890 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
892 let infcx
= selcx
.infcx();
895 infcx
.replace_late_bound_regions_with_fresh_var(
896 obligation
.cause
.span
,
897 infer
::LateBoundRegionConversionTime
::HigherRankedType
,
900 assert_eq
!(projection
.projection_ty
.item_name
,
901 obligation
.predicate
.item_name
);
903 let origin
= infer
::RelateOutputImplTypes(obligation
.cause
.span
);
904 match infcx
.sub_trait_refs(false,
906 obligation
.predicate
.trait_ref
.clone(),
907 projection
.projection_ty
.trait_ref
.clone()) {
910 selcx
.tcx().sess
.span_bug(
911 obligation
.cause
.span
,
912 &format
!("Failed to unify `{:?}` and `{:?}` in projection: {}",
919 (projection
.ty
, vec
!())
922 fn confirm_impl_candidate
<'cx
,'tcx
>(
923 selcx
: &mut SelectionContext
<'cx
,'tcx
>,
924 obligation
: &ProjectionTyObligation
<'tcx
>,
925 impl_vtable
: VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>)
926 -> (Ty
<'tcx
>, Vec
<PredicateObligation
<'tcx
>>)
928 // there don't seem to be nicer accessors to these:
929 let impl_or_trait_items_map
= selcx
.tcx().impl_or_trait_items
.borrow();
931 // Look for the associated type in the impl
932 for impl_item
in &selcx
.tcx().impl_items
.borrow()[&impl_vtable
.impl_def_id
] {
933 if let ty
::TypeTraitItem(ref assoc_ty
) = impl_or_trait_items_map
[&impl_item
.def_id()] {
934 if assoc_ty
.name
== obligation
.predicate
.item_name
{
935 return (assoc_ty
.ty
.unwrap().subst(selcx
.tcx(), &impl_vtable
.substs
),
941 // It is not in the impl - get the default from the trait.
942 let trait_ref
= obligation
.predicate
.trait_ref
;
943 for trait_item
in selcx
.tcx().trait_items(trait_ref
.def_id
).iter() {
944 if let &ty
::TypeTraitItem(ref assoc_ty
) = trait_item
{
945 if assoc_ty
.name
== obligation
.predicate
.item_name
{
946 if let Some(ty
) = assoc_ty
.ty
{
947 return (ty
.subst(selcx
.tcx(), trait_ref
.substs
),
950 // This means that the impl is missing a
951 // definition for the associated type. This error
952 // ought to be reported by the type checker method
953 // `check_impl_items_against_trait`, so here we
954 // just return TyError.
955 debug
!("confirm_impl_candidate: no associated type {:?} for {:?}",
958 return (selcx
.tcx().types
.err
, vec
!());
964 selcx
.tcx().sess
.span_bug(obligation
.cause
.span
,
965 &format
!("No associated type for {:?}",