src/librustc/middle/traits/project.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Code for projecting associated types out of trait references.
  12
  13 use super::elaborate_predicates;
  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;
  22 use super::util;
  23
  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;
  30
  31 pub type PolyProjectionObligation<'tcx> =
  32     Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  33
  34 pub type ProjectionObligation<'tcx> =
  35     Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  36
  37 pub type ProjectionTyObligation<'tcx> =
  38     Obligation<'tcx, ty::ProjectionTy<'tcx>>;
  39
  40 /// When attempting to resolve `<T as TraitRef>::Name` ...
  41 #[derive(Debug)]
  42 pub enum ProjectionTyError<'tcx> {
  43     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  44     TooManyCandidates,
  45
  46     /// ...an error occurred matching `T : TraitRef`
  47     TraitSelectionError(SelectionError<'tcx>),
  48 }
  49
  50 #[derive(Clone)]
  51 pub struct MismatchedProjectionTypes<'tcx> {
  52     pub err: ty::error::TypeError<'tcx>
  53 }
  54
  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>),
  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
  64     Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
  65
  66     // closure return type
  67     Closure(VtableClosureData<'tcx, PredicateObligation<'tcx>>),
  68
  69     // fn pointer return type
  70     FnPointer(Ty<'tcx>),
  71 }
  72
  73 struct ProjectionTyCandidateSet<'tcx> {
  74     vec: Vec<ProjectionTyCandidate<'tcx>>,
  75     ambiguous: bool
  76 }
  77
  78 /// Evaluates constraints of the form:
  79 ///
  80 ///     for<...> <T as Trait>::U == V
  81 ///
  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>>
  87 {
  88     debug!("poly_project_and_unify_type(obligation={:?})",
  89            obligation);
  90
  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);
  95
  96         let skol_obligation = obligation.with(skol_predicate);
  97         match project_and_unify_type(selcx, &skol_obligation) {
  98             Ok(result) => {
  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 }),
 102                 }
 103             }
 104             Err(e) => {
 105                 Err(e)
 106             }
 107         }
 108     })
 109 }
 110
 111 /// Evaluates constraints of the form:
 112 ///
 113 ///     <T as Trait>::U == V
 114 ///
 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>>
 120 {
 121     debug!("project_and_unify_type(obligation={:?})",
 122            obligation);
 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,
 130             None => {
 131                 consider_unification_despite_ambiguity(selcx, obligation);
 132                 return Ok(None);
 133             }
 134         };
 135
 136     debug!("project_and_unify_type: normalized_ty={:?} obligations={:?}",
 137            normalized_ty,
 138            obligations);
 139
 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 }),
 145     }
 146 }
 147
 148 fn consider_unification_despite_ambiguity<'cx,'tcx>(selcx: &mut SelectionContext<'cx,'tcx>,
 149                                                     obligation: &ProjectionObligation<'tcx>) {
 150     debug!("consider_unification_despite_ambiguity(obligation={:?})",
 151            obligation);
 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 {
 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,
 170                                                         def_id,
 171                                                         self_ty,
 172                                                         &closure_type.sig,
 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.
 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));
 183
 184             debug!("consider_unification_despite_ambiguity: ret_type={:?}",
 185                    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) {
 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.
 201 pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
 202                                cause: ObligationCause<'tcx>,
 203                                value: &T)
 204                                -> Normalized<'tcx, T>
 205     where T : TypeFoldable<'tcx>
 206 {
 207     normalize_with_depth(selcx, cause, 0, value)
 208 }
 209
 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>,
 213                                           depth: usize,
 214                                           value: &T)
 215                                           -> Normalized<'tcx, T>
 216     where T : TypeFoldable<'tcx>
 217 {
 218     let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
 219     let result = normalizer.fold(value);
 220
 221     Normalized {
 222         value: result,
 223         obligations: normalizer.obligations,
 224     }
 225 }
 226
 227 struct AssociatedTypeNormalizer<'a,'b:'a,'tcx:'b> {
 228     selcx: &'a mut SelectionContext<'b,'tcx>,
 229     cause: ObligationCause<'tcx>,
 230     obligations: Vec<PredicateObligation<'tcx>>,
 231     depth: usize,
 232 }
 233
 234 impl<'a,'b,'tcx> AssociatedTypeNormalizer<'a,'b,'tcx> {
 235     fn new(selcx: &'a mut SelectionContext<'b,'tcx>,
 236            cause: ObligationCause<'tcx>,
 237            depth: usize)
 238            -> AssociatedTypeNormalizer<'a,'b,'tcx>
 239     {
 240         AssociatedTypeNormalizer {
 241             selcx: selcx,
 242             cause: cause,
 243             obligations: vec!(),
 244             depth: depth,
 245         }
 246     }
 247
 248     fn fold<T:TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
 249         let value = self.selcx.infcx().resolve_type_vars_if_possible(value);
 250
 251         if !value.has_projection_types() {
 252             value.clone()
 253         } else {
 254             value.fold_with(self)
 255         }
 256     }
 257 }
 258
 259 impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
 260     fn tcx(&self) -> &ty::ctxt<'tcx> {
 261         self.selcx.tcx()
 262     }
 263
 264     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 265         // We don't want to normalize associated types that occur inside of region
 266         // binders, because they may contain bound regions, and we can't cope with that.
 267         //
 268         // Example:
 269         //
 270         //     for<'a> fn(<T as Foo<&'a>>::A)
 271         //
 272         // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll
 273         // normalize it when we instantiate those bound regions (which
 274         // should occur eventually).
 275
 276         let ty = ty.super_fold_with(self);
 277         match ty.sty {
 278             ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*)
 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);
 297                 self.obligations.extend(obligations);
 298                 ty
 299             }
 300
 301             _ => {
 302                 ty
 303             }
 304         }
 305     }
 306 }
 307
 308 #[derive(Clone)]
 309 pub struct Normalized<'tcx,T> {
 310     pub value: T,
 311     pub obligations: Vec<PredicateObligation<'tcx>>,
 312 }
 313
 314 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
 315
 316 impl<'tcx,T> Normalized<'tcx,T> {
 317     pub fn with<U>(self, value: U) -> Normalized<'tcx,U> {
 318         Normalized { value: value, obligations: self.obligations }
 319     }
 320 }
 321
 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>,
 332     depth: usize)
 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             });
 346             let obligation = Obligation::with_depth(
 347                 cause, depth + 1, projection.to_predicate());
 348             Normalized {
 349                 value: ty_var,
 350                 obligations: vec!(obligation)
 351             }
 352         })
 353 }
 354
 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>,
 363     depth: usize)
 364     -> Option<NormalizedTy<'tcx>>
 365 {
 366     debug!("normalize_projection_type(\
 367            projection_ty={:?}, \
 368            depth={})",
 369            projection_ty,
 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
 380             debug!("normalize_projection_type: projected_ty={:?} depth={} obligations={:?}",
 381                    projected_ty,
 382                    depth,
 383                    obligations);
 384
 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);
 388
 389                 debug!("normalize_projection_type: normalized_ty={:?} depth={}",
 390                        normalized_ty,
 391                        depth);
 392
 393                 obligations.extend(normalizer.obligations);
 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)) => {
 406             debug!("normalize_projection_type: projected_ty={:?} no progress",
 407                    projected_ty);
 408             Some(Normalized {
 409                 value: projected_ty,
 410                 obligations: vec!()
 411             })
 412         }
 413         Err(ProjectionTyError::TooManyCandidates) => {
 414             debug!("normalize_projection_type: too many candidates");
 415             None
 416         }
 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
 422             // reported later
 423
 424             Some(normalize_to_error(selcx, projection_ty, cause, depth))
 425         }
 426     }
 427 }
 428
 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.
 434 ///
 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>,
 451                                depth: usize)
 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,
 457                                         predicate: trait_ref.to_predicate() };
 458     let new_value = selcx.infcx().next_ty_var();
 459     Normalized {
 460         value: new_value,
 461         obligations: vec!(trait_obligation)
 462     }
 463 }
 464
 465 enum ProjectedTy<'tcx> {
 466     Progress(Ty<'tcx>, Vec<PredicateObligation<'tcx>>),
 467     NoProgress(Ty<'tcx>),
 468 }
 469
 470 /// Compute the result of a projection type (if we can).
 471 fn project_type<'cx,'tcx>(
 472     selcx: &mut SelectionContext<'cx,'tcx>,
 473     obligation: &ProjectionTyObligation<'tcx>)
 474     -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>>
 475 {
 476     debug!("project(obligation={:?})",
 477            obligation);
 478
 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);
 483     }
 484
 485     let obligation_trait_ref =
 486         selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate.trait_ref);
 487
 488     debug!("project: obligation_trait_ref={:?}", obligation_trait_ref);
 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
 504     assemble_candidates_from_trait_def(selcx,
 505                                        obligation,
 506                                        &obligation_trait_ref,
 507                                        &mut candidates);
 508
 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
 520     // Inherent ambiguity that prevents us from even enumerating the
 521     // candidates.
 522     if candidates.ambiguous {
 523         return Err(ProjectionTyError::TooManyCandidates);
 524     }
 525
 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
 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         }
 565     }
 566
 567     assert!(candidates.vec.len() <= 1);
 568
 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 => {
 575             Ok(ProjectedTy::NoProgress(selcx.tcx().mk_projection(
 576                 obligation.predicate.trait_ref.clone(),
 577                 obligation.predicate.item_name)))
 578         }
 579     }
 580 }
 581
 582 /// The first thing we have to do is scan through the parameter
 583 /// environment to see whether there are any projection predicates
 584 /// there that can answer this question.
 585 fn assemble_candidates_from_param_env<'cx,'tcx>(
 586     selcx: &mut SelectionContext<'cx,'tcx>,
 587     obligation: &ProjectionTyObligation<'tcx>,
 588     obligation_trait_ref: &ty::TraitRef<'tcx>,
 589     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 590 {
 591     debug!("assemble_candidates_from_param_env(..)");
 592     let env_predicates = selcx.param_env().caller_bounds.iter().cloned();
 593     assemble_candidates_from_predicates(selcx,
 594                                         obligation,
 595                                         obligation_trait_ref,
 596                                         candidate_set,
 597                                         ProjectionTyCandidate::ParamEnv,
 598                                         env_predicates);
 599 }
 600
 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 ///
 604 /// ```
 605 /// trait Foo {
 606 ///     type FooT : Bar<BarT=i32>
 607 /// }
 608 /// ```
 609 ///
 610 /// Here, for example, we could conclude that the result is `i32`.
 611 fn assemble_candidates_from_trait_def<'cx,'tcx>(
 612     selcx: &mut SelectionContext<'cx,'tcx>,
 613     obligation: &ProjectionTyObligation<'tcx>,
 614     obligation_trait_ref: &ty::TraitRef<'tcx>,
 615     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 616 {
 617     debug!("assemble_candidates_from_trait_def(..)");
 618
 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;
 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.
 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,
 636                                         obligation,
 637                                         obligation_trait_ref,
 638                                         candidate_set,
 639                                         ProjectionTyCandidate::TraitDef,
 640                                         bounds)
 641 }
 642
 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>,
 649     env_predicates: I)
 650     where I: Iterator<Item=ty::Predicate<'tcx>>
 651 {
 652     debug!("assemble_candidates_from_predicates(obligation={:?})",
 653            obligation);
 654     let infcx = selcx.infcx();
 655     for predicate in env_predicates {
 656         debug!("assemble_candidates_from_predicates: predicate={:?}",
 657                predicate);
 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(|_| {
 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,
 669                                               origin,
 670                                               data_poly_trait_ref,
 671                                               obligation_poly_trait_ref).is_ok()
 672                 });
 673
 674                 debug!("assemble_candidates_from_predicates: candidate={:?} \
 675                                                              is_match={} same_name={}",
 676                        data, is_match, same_name);
 677
 678                 if is_match {
 679                     candidate_set.vec.push(ctor(data.clone()));
 680                 }
 681             }
 682             _ => { }
 683         }
 684     }
 685 }
 686
 687 fn assemble_candidates_from_object_type<'cx,'tcx>(
 688     selcx: &mut SelectionContext<'cx,'tcx>,
 689     obligation:  &ProjectionTyObligation<'tcx>,
 690     obligation_trait_ref: &ty::TraitRef<'tcx>,
 691     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 692 {
 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={:?})",
 696            object_ty);
 697     let data = match object_ty.sty {
 698         ty::TyTrait(ref data) => data,
 699         _ => {
 700             selcx.tcx().sess.span_bug(
 701                 obligation.cause.span,
 702                 &format!("assemble_candidates_from_object_type called with non-object: {:?}",
 703                          object_ty));
 704         }
 705     };
 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())
 709                                           .collect();
 710     let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
 711     assemble_candidates_from_predicates(selcx,
 712                                         obligation,
 713                                         obligation_trait_ref,
 714                                         candidate_set,
 715                                         ProjectionTyCandidate::ParamEnv,
 716                                         env_predicates)
 717 }
 718
 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>>
 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) => {
 737             debug!("assemble_candidates_from_impls: selection error {:?}",
 738                    e);
 739             return Err(e);
 740         }
 741     };
 742
 743     match vtable {
 744         super::VtableImpl(data) => {
 745             debug!("assemble_candidates_from_impls: impl candidate {:?}",
 746                    data);
 747
 748             candidate_set.vec.push(
 749                 ProjectionTyCandidate::Impl(data));
 750         }
 751         super::VtableObject(_) => {
 752             assemble_candidates_from_object_type(
 753                 selcx, obligation, obligation_trait_ref, candidate_set);
 754         }
 755         super::VtableClosure(data) => {
 756             candidate_set.vec.push(
 757                 ProjectionTyCandidate::Closure(data));
 758         }
 759         super::VtableFnPointer(fn_type) => {
 760             candidate_set.vec.push(
 761                 ProjectionTyCandidate::FnPointer(fn_type));
 762         }
 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             // ```
 780             // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
 781             // ```
 782             //
 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`.
 789         }
 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 `{:?}`",
 796                          vtable));
 797         }
 798     }
 799
 800     Ok(())
 801 }
 802
 803 fn confirm_candidate<'cx,'tcx>(
 804     selcx: &mut SelectionContext<'cx,'tcx>,
 805     obligation: &ProjectionTyObligation<'tcx>,
 806     candidate: ProjectionTyCandidate<'tcx>)
 807     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 808 {
 809     debug!("confirm_candidate(candidate={:?}, obligation={:?})",
 810            candidate,
 811            obligation);
 812
 813     match candidate {
 814         ProjectionTyCandidate::ParamEnv(poly_projection) |
 815         ProjectionTyCandidate::TraitDef(poly_projection) => {
 816             confirm_param_env_candidate(selcx, obligation, poly_projection)
 817         }
 818
 819         ProjectionTyCandidate::Impl(impl_vtable) => {
 820             confirm_impl_candidate(selcx, obligation, impl_vtable)
 821         }
 822
 823         ProjectionTyCandidate::Closure(closure_vtable) => {
 824             confirm_closure_candidate(selcx, obligation, closure_vtable)
 825         }
 826
 827         ProjectionTyCandidate::FnPointer(fn_type) => {
 828             confirm_fn_pointer_candidate(selcx, obligation, fn_type)
 829         }
 830     }
 831 }
 832
 833 fn confirm_fn_pointer_candidate<'cx,'tcx>(
 834     selcx: &mut SelectionContext<'cx,'tcx>,
 835     obligation: &ProjectionTyObligation<'tcx>,
 836     fn_type: Ty<'tcx>)
 837     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 838 {
 839     let fn_type = selcx.infcx().shallow_resolve(fn_type);
 840     let sig = fn_type.fn_sig();
 841     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
 842 }
 843
 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>>)
 849 {
 850     let closure_typer = selcx.closure_typer();
 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)
 865 }
 866
 867 fn confirm_callable_candidate<'cx,'tcx>(
 868     selcx: &mut SelectionContext<'cx,'tcx>,
 869     obligation: &ProjectionTyObligation<'tcx>,
 870     fn_sig: &ty::PolyFnSig<'tcx>,
 871     flag: util::TupleArgumentsFlag)
 872     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 873 {
 874     let tcx = selcx.tcx();
 875
 876     debug!("confirm_callable_candidate({:?},{:?})",
 877            obligation,
 878            fn_sig);
 879
 880     // the `Output` associated type is declared on `FnOnce`
 881     let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap();
 882
 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,
 886                                                 fn_once_def_id,
 887                                                 obligation.predicate.trait_ref.self_ty(),
 888                                                 fn_sig,
 889                                                 flag);
 890
 891     let predicate = ty::Binder(ty::ProjectionPredicate { // (1) recreate binder here
 892         projection_ty: ty::ProjectionTy {
 893             trait_ref: trait_ref,
 894             item_name: token::intern(FN_OUTPUT_NAME),
 895         },
 896         ty: ret_type
 897     });
 898
 899     confirm_param_env_candidate(selcx, obligation, predicate)
 900 }
 901
 902 fn confirm_param_env_candidate<'cx,'tcx>(
 903     selcx: &mut SelectionContext<'cx,'tcx>,
 904     obligation: &ProjectionTyObligation<'tcx>,
 905     poly_projection: ty::PolyProjectionPredicate<'tcx>)
 906     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 907 {
 908     let infcx = selcx.infcx();
 909
 910     let projection =
 911         infcx.replace_late_bound_regions_with_fresh_var(
 912             obligation.cause.span,
 913             infer::LateBoundRegionConversionTime::HigherRankedType,
 914             &poly_projection).0;
 915
 916     assert_eq!(projection.projection_ty.item_name,
 917                obligation.predicate.item_name);
 918
 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()) {
 924         Ok(()) => { }
 925         Err(e) => {
 926             selcx.tcx().sess.span_bug(
 927                 obligation.cause.span,
 928                 &format!("Failed to unify `{:?}` and `{:?}` in projection: {}",
 929                          obligation,
 930                          projection,
 931                          e));
 932         }
 933     }
 934
 935     (projection.ty, vec!())
 936 }
 937
 938 fn confirm_impl_candidate<'cx,'tcx>(
 939     selcx: &mut SelectionContext<'cx,'tcx>,
 940     obligation: &ProjectionTyObligation<'tcx>,
 941     impl_vtable: VtableImplData<'tcx, PredicateObligation<'tcx>>)
 942     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 943 {
 944     // there don't seem to be nicer accessors to these:
 945     let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow();
 946
 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             }
 954         }
 955     }
 956
 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),
 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.
 971                     debug!("confirm_impl_candidate: no associated type {:?} for {:?}",
 972                            assoc_ty.name,
 973                            trait_ref);
 974                     return (selcx.tcx().types.err, vec!());
 975                 }
 976             }
 977         }
 978     }
 979
 980     selcx.tcx().sess.span_bug(obligation.cause.span,
 981                               &format!("No associated type for {:?}",
 982                                        trait_ref));
 983 }