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