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::Obligation;
  15 use super::ObligationCause;
  16 use super::Overflow;
  17 use super::PredicateObligation;
  18 use super::SelectionContext;
  19 use super::SelectionError;
  20 use super::VtableImplData;
  21
  22 use middle::infer;
  23 use middle::subst::Subst;
  24 use middle::ty::{self, AsPredicate, ReferencesError, RegionEscape,
  25                  HasProjectionTypes, ToPolyTraitRef, Ty};
  26 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
  27 use std::rc::Rc;
  28 use util::ppaux::Repr;
  29
  30 pub type PolyProjectionObligation<'tcx> =
  31     Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  32
  33 pub type ProjectionObligation<'tcx> =
  34     Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  35
  36 pub type ProjectionTyObligation<'tcx> =
  37     Obligation<'tcx, ty::ProjectionTy<'tcx>>;
  38
  39 /// When attempting to resolve `<T as TraitRef>::Name` ...
  40 pub enum ProjectionTyError<'tcx> {
  41     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  42     TooManyCandidates,
  43
  44     /// ...an error occurred matching `T : TraitRef`
  45     TraitSelectionError(SelectionError<'tcx>),
  46 }
  47
  48 #[derive(Clone)]
  49 pub struct MismatchedProjectionTypes<'tcx> {
  50     pub err: ty::type_err<'tcx>
  51 }
  52
  53 enum ProjectionTyCandidate<'tcx> {
  54     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
  55     Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
  56 }
  57
  58 struct ProjectionTyCandidateSet<'tcx> {
  59     vec: Vec<ProjectionTyCandidate<'tcx>>,
  60     ambiguous: bool
  61 }
  62
  63 pub fn poly_project_and_unify_type<'cx,'tcx>(
  64     selcx: &mut SelectionContext<'cx,'tcx>,
  65     obligation: &PolyProjectionObligation<'tcx>)
  66     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
  67 {
  68     debug!("poly_project(obligation={})",
  69            obligation.repr(selcx.tcx()));
  70
  71     let infcx = selcx.infcx();
  72     let result = infcx.try(|snapshot| {
  73         let (skol_predicate, skol_map) =
  74             infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
  75
  76         let skol_obligation = obligation.with(skol_predicate);
  77         match project_and_unify_type(selcx, &skol_obligation) {
  78             Ok(Some(obligations)) => {
  79                 match infcx.leak_check(&skol_map, snapshot) {
  80                     Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, &obligations)),
  81                     Err(e) => Err(Some(MismatchedProjectionTypes { err: e })),
  82                 }
  83             }
  84             Ok(None) => {
  85                 // Signal ambiguity using Err just so that infcx.try()
  86                 // rolls back the snapshot. We adapt below.
  87                 Err(None)
  88             }
  89             Err(e) => {
  90                 Err(Some(e))
  91             }
  92         }
  93     });
  94
  95     // Above, we use Err(None) to signal ambiguity so that the
  96     // snapshot will be rolled back. But here, we want to translate to
  97     // Ok(None). Kind of weird.
  98     match result {
  99         Ok(obligations) => Ok(Some(obligations)),
 100         Err(None) => Ok(None),
 101         Err(Some(e)) => Err(e),
 102     }
 103 }
 104
 105 /// Compute result of projecting an associated type and unify it with
 106 /// `obligation.predicate.ty` (if we can).
 107 fn project_and_unify_type<'cx,'tcx>(
 108     selcx: &mut SelectionContext<'cx,'tcx>,
 109     obligation: &ProjectionObligation<'tcx>)
 110     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 111 {
 112     debug!("project_and_unify(obligation={})",
 113            obligation.repr(selcx.tcx()));
 114
 115     let Normalized { value: normalized_ty, obligations } =
 116         match opt_normalize_projection_type(selcx,
 117                                             obligation.predicate.projection_ty.clone(),
 118                                             obligation.cause.clone(),
 119                                             obligation.recursion_depth) {
 120             Some(n) => n,
 121             None => { return Ok(None); }
 122         };
 123
 124     debug!("project_and_unify_type: normalized_ty={} obligations={}",
 125            normalized_ty.repr(selcx.tcx()),
 126            obligations.repr(selcx.tcx()));
 127
 128     let infcx = selcx.infcx();
 129     let origin = infer::RelateOutputImplTypes(obligation.cause.span);
 130     match infer::mk_eqty(infcx, true, origin, normalized_ty, obligation.predicate.ty) {
 131         Ok(()) => Ok(Some(obligations)),
 132         Err(err) => Err(MismatchedProjectionTypes { err: err }),
 133     }
 134 }
 135
 136 pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
 137                                cause: ObligationCause<'tcx>,
 138                                value: &T)
 139                                -> Normalized<'tcx, T>
 140     where T : TypeFoldable<'tcx> + HasProjectionTypes + Clone + Repr<'tcx>
 141 {
 142     normalize_with_depth(selcx, cause, 0, value)
 143 }
 144
 145 pub fn normalize_with_depth<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
 146                                           cause: ObligationCause<'tcx>,
 147                                           depth: uint,
 148                                           value: &T)
 149                                           -> Normalized<'tcx, T>
 150     where T : TypeFoldable<'tcx> + HasProjectionTypes + Clone + Repr<'tcx>
 151 {
 152     let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
 153     let result = normalizer.fold(value);
 154     Normalized {
 155         value: result,
 156         obligations: normalizer.obligations,
 157     }
 158 }
 159
 160 struct AssociatedTypeNormalizer<'a,'b:'a,'tcx:'b> {
 161     selcx: &'a mut SelectionContext<'b,'tcx>,
 162     cause: ObligationCause<'tcx>,
 163     obligations: Vec<PredicateObligation<'tcx>>,
 164     depth: uint,
 165 }
 166
 167 impl<'a,'b,'tcx> AssociatedTypeNormalizer<'a,'b,'tcx> {
 168     fn new(selcx: &'a mut SelectionContext<'b,'tcx>,
 169            cause: ObligationCause<'tcx>,
 170            depth: uint)
 171            -> AssociatedTypeNormalizer<'a,'b,'tcx>
 172     {
 173         AssociatedTypeNormalizer {
 174             selcx: selcx,
 175             cause: cause,
 176             obligations: vec!(),
 177             depth: depth,
 178         }
 179     }
 180
 181     fn fold<T:TypeFoldable<'tcx> + HasProjectionTypes + Clone>(&mut self, value: &T) -> T {
 182         let value = self.selcx.infcx().resolve_type_vars_if_possible(value);
 183
 184         if !value.has_projection_types() {
 185             value.clone()
 186         } else {
 187             value.fold_with(self)
 188         }
 189     }
 190 }
 191
 192 impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
 193     fn tcx(&self) -> &ty::ctxt<'tcx> {
 194         self.selcx.tcx()
 195     }
 196
 197     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 198         // We don't want to normalize associated types that occur inside of region
 199         // binders, because they may contain bound regions, and we can't cope with that.
 200         //
 201         // Example:
 202         //
 203         //     for<'a> fn(<T as Foo<&'a>>::A)
 204         //
 205         // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll
 206         // normalize it when we instantiate those bound regions (which
 207         // should occur eventually).
 208
 209         match ty.sty {
 210             ty::ty_projection(ref data) if !data.has_escaping_regions() => { // (*)
 211
 212                 // (*) This is kind of hacky -- we need to be able to
 213                 // handle normalization within binders because
 214                 // otherwise we wind up a need to normalize when doing
 215                 // trait matching (since you can have a trait
 216                 // obligation like `for<'a> T::B : Fn(&'a int)`), but
 217                 // we can't normalize with bound regions in scope. So
 218                 // far now we just ignore binders but only normalize
 219                 // if all bound regions are gone (and then we still
 220                 // have to renormalize whenever we instantiate a
 221                 // binder). It would be better to normalize in a
 222                 // binding-aware fashion.
 223
 224                 let Normalized { value: ty, obligations } =
 225                     normalize_projection_type(self.selcx,
 226                                               data.clone(),
 227                                               self.cause.clone(),
 228                                               self.depth);
 229                 self.obligations.extend(obligations.into_iter());
 230                 ty
 231             }
 232             _ => {
 233                 ty_fold::super_fold_ty(self, ty)
 234             }
 235         }
 236     }
 237 }
 238
 239 pub struct Normalized<'tcx,T> {
 240     pub value: T,
 241     pub obligations: Vec<PredicateObligation<'tcx>>,
 242 }
 243
 244 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
 245
 246 pub fn normalize_projection_type<'a,'b,'tcx>(
 247     selcx: &'a mut SelectionContext<'b,'tcx>,
 248     projection_ty: ty::ProjectionTy<'tcx>,
 249     cause: ObligationCause<'tcx>,
 250     depth: uint)
 251     -> NormalizedTy<'tcx>
 252 {
 253     opt_normalize_projection_type(selcx, projection_ty.clone(), cause.clone(), depth)
 254         .unwrap_or_else(move || {
 255             // if we bottom out in ambiguity, create a type variable
 256             // and a deferred predicate to resolve this when more type
 257             // information is available.
 258
 259             let ty_var = selcx.infcx().next_ty_var();
 260             let projection = ty::Binder(ty::ProjectionPredicate {
 261                 projection_ty: projection_ty,
 262                 ty: ty_var
 263             });
 264             let obligation = Obligation::with_depth(cause, depth+1, projection.as_predicate());
 265             Normalized {
 266                 value: ty_var,
 267                 obligations: vec!(obligation)
 268             }
 269         })
 270 }
 271
 272 fn opt_normalize_projection_type<'a,'b,'tcx>(
 273     selcx: &'a mut SelectionContext<'b,'tcx>,
 274     projection_ty: ty::ProjectionTy<'tcx>,
 275     cause: ObligationCause<'tcx>,
 276     depth: uint)
 277     -> Option<NormalizedTy<'tcx>>
 278 {
 279     debug!("normalize_projection_type(\
 280            projection_ty={}, \
 281            depth={})",
 282            projection_ty.repr(selcx.tcx()),
 283            depth);
 284
 285     let obligation = Obligation::with_depth(cause.clone(), depth, projection_ty.clone());
 286     match project_type(selcx, &obligation) {
 287         Ok(ProjectedTy::Progress(projected_ty, mut obligations)) => {
 288             // if projection succeeded, then what we get out of this
 289             // is also non-normalized (consider: it was derived from
 290             // an impl, where-clause etc) and hence we must
 291             // re-normalize it
 292
 293             debug!("normalize_projection_type: projected_ty={} depth={} obligations={}",
 294                    projected_ty.repr(selcx.tcx()),
 295                    depth,
 296                    obligations.repr(selcx.tcx()));
 297
 298             if ty::type_has_projection(projected_ty) {
 299                 let tcx = selcx.tcx();
 300                 let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
 301                 let normalized_ty = normalizer.fold(&projected_ty);
 302
 303                 debug!("normalize_projection_type: normalized_ty={} depth={}",
 304                        normalized_ty.repr(tcx),
 305                        depth);
 306
 307                 obligations.extend(normalizer.obligations.into_iter());
 308                 Some(Normalized {
 309                     value: normalized_ty,
 310                     obligations: obligations,
 311                 })
 312             } else {
 313                 Some(Normalized {
 314                     value: projected_ty,
 315                     obligations: obligations,
 316                 })
 317             }
 318         }
 319         Ok(ProjectedTy::NoProgress(projected_ty)) => {
 320             Some(Normalized {
 321                 value: projected_ty,
 322                 obligations: vec!()
 323             })
 324         }
 325         Err(ProjectionTyError::TooManyCandidates) => {
 326             None
 327         }
 328         Err(ProjectionTyError::TraitSelectionError(_)) => {
 329             // if we got an error processing the `T as Trait` part,
 330             // just return `ty::err` but add the obligation `T :
 331             // Trait`, which when processed will cause the error to be
 332             // reported later
 333
 334             Some(normalize_to_error(selcx, projection_ty, cause, depth))
 335         }
 336     }
 337 }
 338
 339 /// in various error cases, we just set ty_err and return an obligation
 340 /// that, when fulfilled, will lead to an error
 341 fn normalize_to_error<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
 342                                projection_ty: ty::ProjectionTy<'tcx>,
 343                                cause: ObligationCause<'tcx>,
 344                                depth: uint)
 345                                -> NormalizedTy<'tcx>
 346 {
 347     let trait_ref = projection_ty.trait_ref.to_poly_trait_ref();
 348     let trait_obligation = Obligation { cause: cause,
 349                                         recursion_depth: depth,
 350                                         predicate: trait_ref.as_predicate() };
 351     Normalized {
 352         value: selcx.tcx().types.err,
 353         obligations: vec!(trait_obligation)
 354     }
 355 }
 356
 357 enum ProjectedTy<'tcx> {
 358     Progress(Ty<'tcx>, Vec<PredicateObligation<'tcx>>),
 359     NoProgress(Ty<'tcx>),
 360 }
 361
 362 /// Compute the result of a projection type (if we can).
 363 fn project_type<'cx,'tcx>(
 364     selcx: &mut SelectionContext<'cx,'tcx>,
 365     obligation: &ProjectionTyObligation<'tcx>)
 366     -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>>
 367 {
 368     debug!("project(obligation={})",
 369            obligation.repr(selcx.tcx()));
 370
 371     let recursion_limit = selcx.tcx().sess.recursion_limit.get();
 372     if obligation.recursion_depth >= recursion_limit {
 373         debug!("project: overflow!");
 374         return Err(ProjectionTyError::TraitSelectionError(Overflow));
 375     }
 376
 377     let obligation_trait_ref =
 378         selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate.trait_ref);
 379
 380     debug!("project: obligation_trait_ref={}", obligation_trait_ref.repr(selcx.tcx()));
 381
 382     if obligation_trait_ref.references_error() {
 383         return Ok(ProjectedTy::Progress(selcx.tcx().types.err, vec!()));
 384     }
 385
 386     let mut candidates = ProjectionTyCandidateSet {
 387         vec: Vec::new(),
 388         ambiguous: false,
 389     };
 390
 391     assemble_candidates_from_param_env(selcx,
 392                                        obligation,
 393                                        &obligation_trait_ref,
 394                                        &mut candidates);
 395
 396     if let Err(e) = assemble_candidates_from_impls(selcx,
 397                                                    obligation,
 398                                                    &obligation_trait_ref,
 399                                                    &mut candidates) {
 400         return Err(ProjectionTyError::TraitSelectionError(e));
 401     }
 402
 403     debug!("{} candidates, ambiguous={}",
 404            candidates.vec.len(),
 405            candidates.ambiguous);
 406
 407     // We probably need some winnowing logic similar to select here.
 408
 409     if candidates.ambiguous || candidates.vec.len() > 1 {
 410         return Err(ProjectionTyError::TooManyCandidates);
 411     }
 412
 413     match candidates.vec.pop() {
 414         Some(candidate) => {
 415             let (ty, obligations) = confirm_candidate(selcx, obligation, candidate);
 416             Ok(ProjectedTy::Progress(ty, obligations))
 417         }
 418         None => {
 419             Ok(ProjectedTy::NoProgress(ty::mk_projection(selcx.tcx(),
 420                                                          obligation.predicate.trait_ref.clone(),
 421                                                          obligation.predicate.item_name)))
 422         }
 423     }
 424 }
 425
 426 /// The first thing we have to do is scan through the parameter
 427 /// environment to see whether there are any projection predicates
 428 /// there that can answer this question.
 429 fn assemble_candidates_from_param_env<'cx,'tcx>(
 430     selcx: &mut SelectionContext<'cx,'tcx>,
 431     obligation: &ProjectionTyObligation<'tcx>,
 432     obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>,
 433     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 434 {
 435     let env_predicates = selcx.param_env().caller_bounds.predicates.clone();
 436     let env_predicates = env_predicates.iter().cloned().collect();
 437     assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
 438                                         candidate_set, env_predicates);
 439 }
 440
 441 fn assemble_candidates_from_predicates<'cx,'tcx>(
 442     selcx: &mut SelectionContext<'cx,'tcx>,
 443     obligation: &ProjectionTyObligation<'tcx>,
 444     obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>,
 445     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 446     env_predicates: Vec<ty::Predicate<'tcx>>)
 447 {
 448     debug!("assemble_candidates_from_predicates(obligation={}, env_predicates={})",
 449            obligation.repr(selcx.tcx()),
 450            env_predicates.repr(selcx.tcx()));
 451     let infcx = selcx.infcx();
 452     for predicate in elaborate_predicates(selcx.tcx(), env_predicates) {
 453         match predicate {
 454             ty::Predicate::Projection(ref data) => {
 455                 let is_match = infcx.probe(|_| {
 456                     let origin = infer::Misc(obligation.cause.span);
 457                     let obligation_poly_trait_ref =
 458                         obligation_trait_ref.to_poly_trait_ref();
 459                     let data_poly_trait_ref =
 460                         data.to_poly_trait_ref();
 461                     infcx.sub_poly_trait_refs(false,
 462                                               origin,
 463                                               obligation_poly_trait_ref,
 464                                               data_poly_trait_ref).is_ok()
 465                 });
 466
 467                 if is_match {
 468                     candidate_set.vec.push(
 469                         ProjectionTyCandidate::ParamEnv(data.clone()));
 470                 }
 471             }
 472             _ => { }
 473         }
 474     }
 475 }
 476
 477 fn assemble_candidates_from_object_type<'cx,'tcx>(
 478     selcx: &mut SelectionContext<'cx,'tcx>,
 479     obligation:  &ProjectionTyObligation<'tcx>,
 480     obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>,
 481     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 482     object_ty: Ty<'tcx>)
 483 {
 484     let infcx = selcx.infcx();
 485     debug!("assemble_candidates_from_object_type(object_ty={})",
 486            object_ty.repr(infcx.tcx));
 487     let data = match object_ty.sty {
 488         ty::ty_trait(ref data) => data,
 489         _ => {
 490             selcx.tcx().sess.span_bug(
 491                 obligation.cause.span,
 492                 format!("assemble_candidates_from_object_type called with non-object: {}",
 493                         object_ty.repr(selcx.tcx())).as_slice());
 494         }
 495     };
 496     let projection_bounds = data.projection_bounds_with_self_ty(selcx.tcx(), object_ty);
 497     let env_predicates = projection_bounds.iter()
 498                                           .map(|p| p.as_predicate())
 499                                           .collect();
 500     assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
 501                                         candidate_set, env_predicates)
 502 }
 503
 504 fn assemble_candidates_from_impls<'cx,'tcx>(
 505     selcx: &mut SelectionContext<'cx,'tcx>,
 506     obligation: &ProjectionTyObligation<'tcx>,
 507     obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>,
 508     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 509     -> Result<(), SelectionError<'tcx>>
 510 {
 511     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
 512     // start out by selecting the predicate `T as TraitRef<...>`:
 513     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
 514     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
 515     let vtable = match selcx.select(&trait_obligation) {
 516         Ok(Some(vtable)) => vtable,
 517         Ok(None) => {
 518             candidate_set.ambiguous = true;
 519             return Ok(());
 520         }
 521         Err(e) => {
 522             debug!("assemble_candidates_from_impls: selection error {}",
 523                    e.repr(selcx.tcx()));
 524             return Err(e);
 525         }
 526     };
 527
 528     match vtable {
 529         super::VtableImpl(data) => {
 530             candidate_set.vec.push(
 531                 ProjectionTyCandidate::Impl(data));
 532         }
 533         super::VtableObject(data) => {
 534             assemble_candidates_from_object_type(
 535                 selcx, obligation, obligation_trait_ref, candidate_set,
 536                 data.object_ty);
 537         }
 538         super::VtableParam(..) => {
 539             // This case tell us nothing about the value of an
 540             // associated type. Consider:
 541             //
 542             // ```
 543             // trait SomeTrait { type Foo; }
 544             // fn foo<T:SomeTrait>(...) { }
 545             // ```
 546             //
 547             // If the user writes `<T as SomeTrait>::Foo`, then the `T
 548             // : SomeTrait` binding does not help us decide what the
 549             // type `Foo` is (at least, not more specifically than
 550             // what we already knew).
 551             //
 552             // But wait, you say! What about an example like this:
 553             //
 554             // ```
 555             // fn bar<T:SomeTrait<Foo=uint>>(...) { ... }
 556             // ```
 557             //
 558             // Doesn't the `T : Sometrait<Foo=uint>` predicate help
 559             // resolve `T::Foo`? And of course it does, but in fact
 560             // that single predicate is desugared into two predicates
 561             // in the compiler: a trait predicate (`T : SomeTrait`) and a
 562             // projection. And the projection where clause is handled
 563             // in `assemble_candidates_from_param_env`.
 564         }
 565         super::VtableBuiltin(..) |
 566         super::VtableUnboxedClosure(..) |
 567         super::VtableFnPointer(..) => {
 568             // These traits have no associated types.
 569             selcx.tcx().sess.span_bug(
 570                 obligation.cause.span,
 571                 format!("Cannot project an associated type from `{}`",
 572                         vtable.repr(selcx.tcx())).as_slice());
 573         }
 574     }
 575
 576     Ok(())
 577 }
 578
 579 fn confirm_candidate<'cx,'tcx>(
 580     selcx: &mut SelectionContext<'cx,'tcx>,
 581     obligation: &ProjectionTyObligation<'tcx>,
 582     candidate: ProjectionTyCandidate<'tcx>)
 583     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 584 {
 585     let infcx = selcx.infcx();
 586
 587     debug!("confirm_candidate(candidate={}, obligation={})",
 588            candidate.repr(infcx.tcx),
 589            obligation.repr(infcx.tcx));
 590
 591     match candidate {
 592         ProjectionTyCandidate::ParamEnv(poly_projection) => {
 593             let projection =
 594                 infcx.replace_late_bound_regions_with_fresh_var(
 595                     obligation.cause.span,
 596                     infer::LateBoundRegionConversionTime::HigherRankedType,
 597                     &poly_projection).0;
 598
 599             assert_eq!(projection.projection_ty.item_name,
 600                        obligation.predicate.item_name);
 601
 602             let origin = infer::RelateOutputImplTypes(obligation.cause.span);
 603             match infcx.sub_trait_refs(false,
 604                                        origin,
 605                                        obligation.predicate.trait_ref.clone(),
 606                                        projection.projection_ty.trait_ref.clone()) {
 607                 Ok(()) => { }
 608                 Err(e) => {
 609                     selcx.tcx().sess.span_bug(
 610                         obligation.cause.span,
 611                         format!("Failed to unify `{}` and `{}` in projection: {}",
 612                                 obligation.repr(selcx.tcx()),
 613                                 projection.repr(selcx.tcx()),
 614                                 ty::type_err_to_str(selcx.tcx(), &e)).as_slice());
 615                 }
 616             }
 617
 618             (projection.ty, vec!())
 619         }
 620
 621         ProjectionTyCandidate::Impl(impl_vtable) => {
 622             // there don't seem to be nicer accessors to these:
 623             let impl_items_map = selcx.tcx().impl_items.borrow();
 624             let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow();
 625
 626             let impl_items = &impl_items_map[impl_vtable.impl_def_id];
 627             let mut impl_ty = None;
 628             for impl_item in impl_items.iter() {
 629                 let assoc_type = match impl_or_trait_items_map[impl_item.def_id()] {
 630                     ty::TypeTraitItem(ref assoc_type) => assoc_type.clone(),
 631                     ty::MethodTraitItem(..) => { continue; }
 632                 };
 633
 634                 if assoc_type.name != obligation.predicate.item_name {
 635                     continue;
 636                 }
 637
 638                 let impl_poly_ty = ty::lookup_item_type(selcx.tcx(), assoc_type.def_id);
 639                 impl_ty = Some(impl_poly_ty.ty.subst(selcx.tcx(), &impl_vtable.substs));
 640                 break;
 641             }
 642
 643             match impl_ty {
 644                 Some(ty) => (ty, impl_vtable.nested.to_vec()),
 645                 None => {
 646                     // This means that the impl is missing a
 647                     // definition for the associated type. This error
 648                     // ought to be reported by the type checker method
 649                     // `check_impl_items_against_trait`, so here we
 650                     // just return ty_err.
 651                     (selcx.tcx().types.err, vec!())
 652                 }
 653             }
 654         }
 655     }
 656 }
 657
 658 impl<'tcx> Repr<'tcx> for ProjectionTyError<'tcx> {
 659     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 660         match *self {
 661             ProjectionTyError::TooManyCandidates =>
 662                 format!("NoCandidate"),
 663             ProjectionTyError::TraitSelectionError(ref e) =>
 664                 format!("TraitSelectionError({})", e.repr(tcx)),
 665         }
 666     }
 667 }
 668
 669 impl<'tcx> Repr<'tcx> for ProjectionTyCandidate<'tcx> {
 670     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 671         match *self {
 672             ProjectionTyCandidate::ParamEnv(ref data) =>
 673                 format!("ParamEnv({})", data.repr(tcx)),
 674             ProjectionTyCandidate::Impl(ref data) =>
 675                 format!("Impl({})", data.repr(tcx))
 676         }
 677     }
 678 }
 679
 680 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Normalized<'tcx, T> {
 681     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Normalized<'tcx, T> {
 682         Normalized {
 683             value: self.value.fold_with(folder),
 684             obligations: self.obligations.fold_with(folder),
 685         }
 686     }
 687 }
 688
 689 impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for Normalized<'tcx, T> {
 690     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
 691         format!("Normalized({},{})",
 692                 self.value.repr(tcx),
 693                 self.obligations.repr(tcx))
 694     }
 695 }