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