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