src/librustc/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::specialization_graph;
  15 use super::translate_substs;
  16 use super::Obligation;
  17 use super::ObligationCause;
  18 use super::PredicateObligation;
  19 use super::SelectionContext;
  20 use super::SelectionError;
  21 use super::VtableClosureData;
  22 use super::VtableFnPointerData;
  23 use super::VtableImplData;
  24 use super::util;
  25
  26 use hir::def_id::DefId;
  27 use infer::InferOk;
  28 use infer::type_variable::TypeVariableOrigin;
  29 use rustc_data_structures::snapshot_map::{Snapshot, SnapshotMap};
  30 use syntax::ast;
  31 use syntax::symbol::Symbol;
  32 use ty::subst::Subst;
  33 use ty::{self, ToPredicate, ToPolyTraitRef, Ty, TyCtxt};
  34 use ty::fold::{TypeFoldable, TypeFolder};
  35 use util::common::FN_OUTPUT_NAME;
  36
  37 /// Depending on the stage of compilation, we want projection to be
  38 /// more or less conservative.
  39 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  40 pub enum Reveal {
  41     /// At type-checking time, we refuse to project any associated
  42     /// type that is marked `default`. Non-`default` ("final") types
  43     /// are always projected. This is necessary in general for
  44     /// soundness of specialization. However, we *could* allow
  45     /// projections in fully-monomorphic cases. We choose not to,
  46     /// because we prefer for `default type` to force the type
  47     /// definition to be treated abstractly by any consumers of the
  48     /// impl. Concretely, that means that the following example will
  49     /// fail to compile:
  50     ///
  51     /// ```
  52     /// trait Assoc {
  53     ///     type Output;
  54     /// }
  55     ///
  56     /// impl<T> Assoc for T {
  57     ///     default type Output = bool;
  58     /// }
  59     ///
  60     /// fn main() {
  61     ///     let <() as Assoc>::Output = true;
  62     /// }
  63     UserFacing,
  64
  65     /// At trans time, all monomorphic projections will succeed.
  66     /// Also, `impl Trait` is normalized to the concrete type,
  67     /// which has to be already collected by type-checking.
  68     ///
  69     /// NOTE: As `impl Trait`'s concrete type should *never*
  70     /// be observable directly by the user, `Reveal::All`
  71     /// should not be used by checks which may expose
  72     /// type equality or type contents to the user.
  73     /// There are some exceptions, e.g. around OIBITS and
  74     /// transmute-checking, which expose some details, but
  75     /// not the whole concrete type of the `impl Trait`.
  76     All,
  77 }
  78
  79 pub type PolyProjectionObligation<'tcx> =
  80     Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  81
  82 pub type ProjectionObligation<'tcx> =
  83     Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  84
  85 pub type ProjectionTyObligation<'tcx> =
  86     Obligation<'tcx, ty::ProjectionTy<'tcx>>;
  87
  88 /// When attempting to resolve `<T as TraitRef>::Name` ...
  89 #[derive(Debug)]
  90 pub enum ProjectionTyError<'tcx> {
  91     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  92     TooManyCandidates,
  93
  94     /// ...an error occurred matching `T : TraitRef`
  95     TraitSelectionError(SelectionError<'tcx>),
  96 }
  97
  98 #[derive(Clone)]
  99 pub struct MismatchedProjectionTypes<'tcx> {
 100     pub err: ty::error::TypeError<'tcx>
 101 }
 102
 103 #[derive(PartialEq, Eq, Debug)]
 104 enum ProjectionTyCandidate<'tcx> {
 105     // from a where-clause in the env or object type
 106     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
 107
 108     // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
 109     TraitDef(ty::PolyProjectionPredicate<'tcx>),
 110
 111     // from a "impl" (or a "pseudo-impl" returned by select)
 112     Select,
 113 }
 114
 115 struct ProjectionTyCandidateSet<'tcx> {
 116     vec: Vec<ProjectionTyCandidate<'tcx>>,
 117     ambiguous: bool
 118 }
 119
 120 /// Evaluates constraints of the form:
 121 ///
 122 ///     for<...> <T as Trait>::U == V
 123 ///
 124 /// If successful, this may result in additional obligations.
 125 pub fn poly_project_and_unify_type<'cx, 'gcx, 'tcx>(
 126     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 127     obligation: &PolyProjectionObligation<'tcx>)
 128     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 129 {
 130     debug!("poly_project_and_unify_type(obligation={:?})",
 131            obligation);
 132
 133     let infcx = selcx.infcx();
 134     infcx.commit_if_ok(|snapshot| {
 135         let (skol_predicate, skol_map) =
 136             infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
 137
 138         let skol_obligation = obligation.with(skol_predicate);
 139         let r = match project_and_unify_type(selcx, &skol_obligation) {
 140             Ok(result) => {
 141                 let span = obligation.cause.span;
 142                 match infcx.leak_check(false, span, &skol_map, snapshot) {
 143                     Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, result)),
 144                     Err(e) => Err(MismatchedProjectionTypes { err: e }),
 145                 }
 146             }
 147             Err(e) => {
 148                 Err(e)
 149             }
 150         };
 151
 152         r
 153     })
 154 }
 155
 156 /// Evaluates constraints of the form:
 157 ///
 158 ///     <T as Trait>::U == V
 159 ///
 160 /// If successful, this may result in additional obligations.
 161 fn project_and_unify_type<'cx, 'gcx, 'tcx>(
 162     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 163     obligation: &ProjectionObligation<'tcx>)
 164     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 165 {
 166     debug!("project_and_unify_type(obligation={:?})",
 167            obligation);
 168
 169     let Normalized { value: normalized_ty, mut obligations } =
 170         match opt_normalize_projection_type(selcx,
 171                                             obligation.predicate.projection_ty.clone(),
 172                                             obligation.cause.clone(),
 173                                             obligation.recursion_depth) {
 174             Some(n) => n,
 175             None => return Ok(None),
 176         };
 177
 178     debug!("project_and_unify_type: normalized_ty={:?} obligations={:?}",
 179            normalized_ty,
 180            obligations);
 181
 182     let infcx = selcx.infcx();
 183     match infcx.eq_types(true, &obligation.cause, normalized_ty, obligation.predicate.ty) {
 184         Ok(InferOk { obligations: inferred_obligations, value: () }) => {
 185             obligations.extend(inferred_obligations);
 186             Ok(Some(obligations))
 187         },
 188         Err(err) => Err(MismatchedProjectionTypes { err: err }),
 189     }
 190 }
 191
 192 /// Normalizes any associated type projections in `value`, replacing
 193 /// them with a fully resolved type where possible. The return value
 194 /// combines the normalized result and any additional obligations that
 195 /// were incurred as result.
 196 pub fn normalize<'a, 'b, 'gcx, 'tcx, T>(selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 197                                         cause: ObligationCause<'tcx>,
 198                                         value: &T)
 199                                         -> Normalized<'tcx, T>
 200     where T : TypeFoldable<'tcx>
 201 {
 202     normalize_with_depth(selcx, cause, 0, value)
 203 }
 204
 205 /// As `normalize`, but with a custom depth.
 206 pub fn normalize_with_depth<'a, 'b, 'gcx, 'tcx, T>(
 207     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 208     cause: ObligationCause<'tcx>,
 209     depth: usize,
 210     value: &T)
 211     -> Normalized<'tcx, T>
 212
 213     where T : TypeFoldable<'tcx>
 214 {
 215     debug!("normalize_with_depth(depth={}, value={:?})", depth, value);
 216     let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
 217     let result = normalizer.fold(value);
 218     debug!("normalize_with_depth: depth={} result={:?} with {} obligations",
 219            depth, result, normalizer.obligations.len());
 220     debug!("normalize_with_depth: depth={} obligations={:?}",
 221            depth, normalizer.obligations);
 222     Normalized {
 223         value: result,
 224         obligations: normalizer.obligations,
 225     }
 226 }
 227
 228 struct AssociatedTypeNormalizer<'a, 'b: 'a, 'gcx: 'b+'tcx, 'tcx: 'b> {
 229     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 230     cause: ObligationCause<'tcx>,
 231     obligations: Vec<PredicateObligation<'tcx>>,
 232     depth: usize,
 233 }
 234
 235 impl<'a, 'b, 'gcx, 'tcx> AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> {
 236     fn new(selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 237            cause: ObligationCause<'tcx>,
 238            depth: usize)
 239            -> AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx>
 240     {
 241         AssociatedTypeNormalizer {
 242             selcx: selcx,
 243             cause: cause,
 244             obligations: vec![],
 245             depth: depth,
 246         }
 247     }
 248
 249     fn fold<T:TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
 250         let value = self.selcx.infcx().resolve_type_vars_if_possible(value);
 251
 252         if !value.has_projection_types() {
 253             value.clone()
 254         } else {
 255             value.fold_with(self)
 256         }
 257     }
 258 }
 259
 260 impl<'a, 'b, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> {
 261     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
 262         self.selcx.tcx()
 263     }
 264
 265     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 266         // We don't want to normalize associated types that occur inside of region
 267         // binders, because they may contain bound regions, and we can't cope with that.
 268         //
 269         // Example:
 270         //
 271         //     for<'a> fn(<T as Foo<&'a>>::A)
 272         //
 273         // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll
 274         // normalize it when we instantiate those bound regions (which
 275         // should occur eventually).
 276
 277         let ty = ty.super_fold_with(self);
 278         match ty.sty {
 279             ty::TyAnon(def_id, substs) if !substs.has_escaping_regions() => { // (*)
 280                 // Only normalize `impl Trait` after type-checking, usually in trans.
 281                 if self.selcx.projection_mode() == Reveal::All {
 282                     let generic_ty = self.tcx().type_of(def_id);
 283                     let concrete_ty = generic_ty.subst(self.tcx(), substs);
 284                     self.fold_ty(concrete_ty)
 285                 } else {
 286                     ty
 287                 }
 288             }
 289
 290             ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*)
 291
 292                 // (*) This is kind of hacky -- we need to be able to
 293                 // handle normalization within binders because
 294                 // otherwise we wind up a need to normalize when doing
 295                 // trait matching (since you can have a trait
 296                 // obligation like `for<'a> T::B : Fn(&'a int)`), but
 297                 // we can't normalize with bound regions in scope. So
 298                 // far now we just ignore binders but only normalize
 299                 // if all bound regions are gone (and then we still
 300                 // have to renormalize whenever we instantiate a
 301                 // binder). It would be better to normalize in a
 302                 // binding-aware fashion.
 303
 304                 let Normalized { value: normalized_ty, obligations } =
 305                     normalize_projection_type(self.selcx,
 306                                               data.clone(),
 307                                               self.cause.clone(),
 308                                               self.depth);
 309                 debug!("AssociatedTypeNormalizer: depth={} normalized {:?} to {:?} \
 310                         with {} add'l obligations",
 311                        self.depth, ty, normalized_ty, obligations.len());
 312                 self.obligations.extend(obligations);
 313                 normalized_ty
 314             }
 315
 316             _ => {
 317                 ty
 318             }
 319         }
 320     }
 321 }
 322
 323 #[derive(Clone)]
 324 pub struct Normalized<'tcx,T> {
 325     pub value: T,
 326     pub obligations: Vec<PredicateObligation<'tcx>>,
 327 }
 328
 329 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
 330
 331 impl<'tcx,T> Normalized<'tcx,T> {
 332     pub fn with<U>(self, value: U) -> Normalized<'tcx,U> {
 333         Normalized { value: value, obligations: self.obligations }
 334     }
 335 }
 336
 337 /// The guts of `normalize`: normalize a specific projection like `<T
 338 /// as Trait>::Item`. The result is always a type (and possibly
 339 /// additional obligations). If ambiguity arises, which implies that
 340 /// there are unresolved type variables in the projection, we will
 341 /// substitute a fresh type variable `$X` and generate a new
 342 /// obligation `<T as Trait>::Item == $X` for later.
 343 pub fn normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
 344     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 345     projection_ty: ty::ProjectionTy<'tcx>,
 346     cause: ObligationCause<'tcx>,
 347     depth: usize)
 348     -> NormalizedTy<'tcx>
 349 {
 350     opt_normalize_projection_type(selcx, projection_ty.clone(), cause.clone(), depth)
 351         .unwrap_or_else(move || {
 352             // if we bottom out in ambiguity, create a type variable
 353             // and a deferred predicate to resolve this when more type
 354             // information is available.
 355
 356             let tcx = selcx.infcx().tcx;
 357             let def_id = tcx.associated_items(projection_ty.trait_ref.def_id).find(|i|
 358                 i.name == projection_ty.item_name && i.kind == ty::AssociatedKind::Type
 359             ).map(|i| i.def_id).unwrap();
 360             let ty_var = selcx.infcx().next_ty_var(
 361                 TypeVariableOrigin::NormalizeProjectionType(tcx.def_span(def_id)));
 362             let projection = ty::Binder(ty::ProjectionPredicate {
 363                 projection_ty: projection_ty,
 364                 ty: ty_var
 365             });
 366             let obligation = Obligation::with_depth(
 367                 cause, depth + 1, projection.to_predicate());
 368             Normalized {
 369                 value: ty_var,
 370                 obligations: vec![obligation]
 371             }
 372         })
 373 }
 374
 375 /// The guts of `normalize`: normalize a specific projection like `<T
 376 /// as Trait>::Item`. The result is always a type (and possibly
 377 /// additional obligations). Returns `None` in the case of ambiguity,
 378 /// which indicates that there are unbound type variables.
 379 fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
 380     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
 381     projection_ty: ty::ProjectionTy<'tcx>,
 382     cause: ObligationCause<'tcx>,
 383     depth: usize)
 384     -> Option<NormalizedTy<'tcx>>
 385 {
 386     let infcx = selcx.infcx();
 387
 388     let projection_ty = infcx.resolve_type_vars_if_possible(&projection_ty);
 389
 390     debug!("opt_normalize_projection_type(\
 391            projection_ty={:?}, \
 392            depth={})",
 393            projection_ty,
 394            depth);
 395
 396     // FIXME(#20304) For now, I am caching here, which is good, but it
 397     // means we don't capture the type variables that are created in
 398     // the case of ambiguity. Which means we may create a large stream
 399     // of such variables. OTOH, if we move the caching up a level, we
 400     // would not benefit from caching when proving `T: Trait<U=Foo>`
 401     // bounds. It might be the case that we want two distinct caches,
 402     // or else another kind of cache entry.
 403
 404     match infcx.projection_cache.borrow_mut().try_start(projection_ty) {
 405         Ok(()) => { }
 406         Err(ProjectionCacheEntry::Ambiguous) => {
 407             // If we found ambiguity the last time, that generally
 408             // means we will continue to do so until some type in the
 409             // key changes (and we know it hasn't, because we just
 410             // fully resolved it). One exception though is closure
 411             // types, which can transition from having a fixed kind to
 412             // no kind with no visible change in the key.
 413             //
 414             // FIXME(#32286) refactor this so that closure type
 415             // changes
 416             debug!("opt_normalize_projection_type: \
 417                     found cache entry: ambiguous");
 418             if !projection_ty.has_closure_types() {
 419                 return None;
 420             }
 421         }
 422         Err(ProjectionCacheEntry::InProgress) => {
 423             // If while normalized A::B, we are asked to normalize
 424             // A::B, just return A::B itself. This is a conservative
 425             // answer, in the sense that A::B *is* clearly equivalent
 426             // to A::B, though there may be a better value we can
 427             // find.
 428
 429             // Under lazy normalization, this can arise when
 430             // bootstrapping.  That is, imagine an environment with a
 431             // where-clause like `A::B == u32`. Now, if we are asked
 432             // to normalize `A::B`, we will want to check the
 433             // where-clauses in scope. So we will try to unify `A::B`
 434             // with `A::B`, which can trigger a recursive
 435             // normalization. In that case, I think we will want this code:
 436             //
 437             // ```
 438             // let ty = selcx.tcx().mk_projection(projection_ty.trait_ref,
 439             //                                    projection_ty.item_name);
 440             // return Some(NormalizedTy { value: v, obligations: vec![] });
 441             // ```
 442
 443             debug!("opt_normalize_projection_type: \
 444                     found cache entry: in-progress");
 445
 446             // But for now, let's classify this as an overflow:
 447             let recursion_limit = selcx.tcx().sess.recursion_limit.get();
 448             let obligation = Obligation::with_depth(cause.clone(),
 449                                                     recursion_limit,
 450                                                     projection_ty);
 451             selcx.infcx().report_overflow_error(&obligation, false);
 452         }
 453         Err(ProjectionCacheEntry::NormalizedTy(ty)) => {
 454             // If we find the value in the cache, then the obligations
 455             // have already been returned from the previous entry (and
 456             // should therefore have been honored).
 457             debug!("opt_normalize_projection_type: \
 458                     found normalized ty `{:?}`",
 459                    ty);
 460             return Some(NormalizedTy { value: ty, obligations: vec![] });
 461         }
 462         Err(ProjectionCacheEntry::Error) => {
 463             debug!("opt_normalize_projection_type: \
 464                     found error");
 465             return Some(normalize_to_error(selcx, projection_ty, cause, depth));
 466         }
 467     }
 468
 469     let obligation = Obligation::with_depth(cause.clone(), depth, projection_ty.clone());
 470     match project_type(selcx, &obligation) {
 471         Ok(ProjectedTy::Progress(Progress { ty: projected_ty,
 472                                             mut obligations,
 473                                             cacheable })) => {
 474             // if projection succeeded, then what we get out of this
 475             // is also non-normalized (consider: it was derived from
 476             // an impl, where-clause etc) and hence we must
 477             // re-normalize it
 478
 479             debug!("opt_normalize_projection_type: \
 480                     projected_ty={:?} \
 481                     depth={} \
 482                     obligations={:?} \
 483                     cacheable={:?}",
 484                    projected_ty,
 485                    depth,
 486                    obligations,
 487                    cacheable);
 488
 489             let result = if projected_ty.has_projection_types() {
 490                 let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth+1);
 491                 let normalized_ty = normalizer.fold(&projected_ty);
 492
 493                 debug!("opt_normalize_projection_type: \
 494                         normalized_ty={:?} depth={}",
 495                        normalized_ty,
 496                        depth);
 497
 498                 obligations.extend(normalizer.obligations);
 499                 Normalized {
 500                     value: normalized_ty,
 501                     obligations: obligations,
 502                 }
 503             } else {
 504                 Normalized {
 505                     value: projected_ty,
 506                     obligations: obligations,
 507                 }
 508             };
 509             infcx.projection_cache.borrow_mut()
 510                                   .complete(projection_ty, &result, cacheable);
 511             Some(result)
 512         }
 513         Ok(ProjectedTy::NoProgress(projected_ty)) => {
 514             debug!("opt_normalize_projection_type: \
 515                     projected_ty={:?} no progress",
 516                    projected_ty);
 517             let result = Normalized {
 518                 value: projected_ty,
 519                 obligations: vec![]
 520             };
 521             infcx.projection_cache.borrow_mut()
 522                                   .complete(projection_ty, &result, true);
 523             Some(result)
 524         }
 525         Err(ProjectionTyError::TooManyCandidates) => {
 526             debug!("opt_normalize_projection_type: \
 527                     too many candidates");
 528             infcx.projection_cache.borrow_mut()
 529                                   .ambiguous(projection_ty);
 530             None
 531         }
 532         Err(ProjectionTyError::TraitSelectionError(_)) => {
 533             debug!("opt_normalize_projection_type: ERROR");
 534             // if we got an error processing the `T as Trait` part,
 535             // just return `ty::err` but add the obligation `T :
 536             // Trait`, which when processed will cause the error to be
 537             // reported later
 538
 539             infcx.projection_cache.borrow_mut()
 540                                   .error(projection_ty);
 541             Some(normalize_to_error(selcx, projection_ty, cause, depth))
 542         }
 543     }
 544 }
 545
 546 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
 547 /// hold. In various error cases, we cannot generate a valid
 548 /// normalized projection. Therefore, we create an inference variable
 549 /// return an associated obligation that, when fulfilled, will lead to
 550 /// an error.
 551 ///
 552 /// Note that we used to return `TyError` here, but that was quite
 553 /// dubious -- the premise was that an error would *eventually* be
 554 /// reported, when the obligation was processed. But in general once
 555 /// you see a `TyError` you are supposed to be able to assume that an
 556 /// error *has been* reported, so that you can take whatever heuristic
 557 /// paths you want to take. To make things worse, it was possible for
 558 /// cycles to arise, where you basically had a setup like `<MyType<$0>
 559 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
 560 /// Trait>::Foo> to `[type error]` would lead to an obligation of
 561 /// `<MyType<[type error]> as Trait>::Foo`.  We are supposed to report
 562 /// an error for this obligation, but we legitimately should not,
 563 /// because it contains `[type error]`. Yuck! (See issue #29857 for
 564 /// one case where this arose.)
 565 fn normalize_to_error<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
 566                                       projection_ty: ty::ProjectionTy<'tcx>,
 567                                       cause: ObligationCause<'tcx>,
 568                                       depth: usize)
 569                                       -> NormalizedTy<'tcx>
 570 {
 571     let trait_ref = projection_ty.trait_ref.to_poly_trait_ref();
 572     let trait_obligation = Obligation { cause: cause,
 573                                         recursion_depth: depth,
 574                                         predicate: trait_ref.to_predicate() };
 575     let tcx = selcx.infcx().tcx;
 576     let def_id = tcx.associated_items(projection_ty.trait_ref.def_id).find(|i|
 577         i.name == projection_ty.item_name && i.kind == ty::AssociatedKind::Type
 578     ).map(|i| i.def_id).unwrap();
 579     let new_value = selcx.infcx().next_ty_var(
 580         TypeVariableOrigin::NormalizeProjectionType(tcx.def_span(def_id)));
 581     Normalized {
 582         value: new_value,
 583         obligations: vec![trait_obligation]
 584     }
 585 }
 586
 587 enum ProjectedTy<'tcx> {
 588     Progress(Progress<'tcx>),
 589     NoProgress(Ty<'tcx>),
 590 }
 591
 592 struct Progress<'tcx> {
 593     ty: Ty<'tcx>,
 594     obligations: Vec<PredicateObligation<'tcx>>,
 595     cacheable: bool,
 596 }
 597
 598 impl<'tcx> Progress<'tcx> {
 599     fn error<'a,'gcx>(tcx: TyCtxt<'a,'gcx,'tcx>) -> Self {
 600         Progress {
 601             ty: tcx.types.err,
 602             obligations: vec![],
 603             cacheable: true
 604         }
 605     }
 606
 607     fn with_addl_obligations(mut self,
 608                              mut obligations: Vec<PredicateObligation<'tcx>>)
 609                              -> Self {
 610         debug!("with_addl_obligations: self.obligations.len={} obligations.len={}",
 611                self.obligations.len(), obligations.len());
 612
 613         debug!("with_addl_obligations: self.obligations={:?} obligations={:?}",
 614                self.obligations, obligations);
 615
 616         self.obligations.append(&mut obligations);
 617         self
 618     }
 619 }
 620
 621 /// Compute the result of a projection type (if we can).
 622 ///
 623 /// IMPORTANT:
 624 /// - `obligation` must be fully normalized
 625 fn project_type<'cx, 'gcx, 'tcx>(
 626     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 627     obligation: &ProjectionTyObligation<'tcx>)
 628     -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>>
 629 {
 630     debug!("project(obligation={:?})",
 631            obligation);
 632
 633     let recursion_limit = selcx.tcx().sess.recursion_limit.get();
 634     if obligation.recursion_depth >= recursion_limit {
 635         debug!("project: overflow!");
 636         selcx.infcx().report_overflow_error(&obligation, true);
 637     }
 638
 639     let obligation_trait_ref = &obligation.predicate.trait_ref;
 640
 641     debug!("project: obligation_trait_ref={:?}", obligation_trait_ref);
 642
 643     if obligation_trait_ref.references_error() {
 644         return Ok(ProjectedTy::Progress(Progress::error(selcx.tcx())));
 645     }
 646
 647     let mut candidates = ProjectionTyCandidateSet {
 648         vec: Vec::new(),
 649         ambiguous: false,
 650     };
 651
 652     assemble_candidates_from_param_env(selcx,
 653                                        obligation,
 654                                        &obligation_trait_ref,
 655                                        &mut candidates);
 656
 657     assemble_candidates_from_trait_def(selcx,
 658                                        obligation,
 659                                        &obligation_trait_ref,
 660                                        &mut candidates);
 661
 662     if let Err(e) = assemble_candidates_from_impls(selcx,
 663                                                    obligation,
 664                                                    &obligation_trait_ref,
 665                                                    &mut candidates) {
 666         return Err(ProjectionTyError::TraitSelectionError(e));
 667     }
 668
 669     debug!("{} candidates, ambiguous={}",
 670            candidates.vec.len(),
 671            candidates.ambiguous);
 672
 673     // Inherent ambiguity that prevents us from even enumerating the
 674     // candidates.
 675     if candidates.ambiguous {
 676         return Err(ProjectionTyError::TooManyCandidates);
 677     }
 678
 679     // Drop duplicates.
 680     //
 681     // Note: `candidates.vec` seems to be on the critical path of the
 682     // compiler. Replacing it with an hash set was also tried, which would
 683     // render the following dedup unnecessary. It led to cleaner code but
 684     // prolonged compiling time of `librustc` from 5m30s to 6m in one test, or
 685     // ~9% performance lost.
 686     if candidates.vec.len() > 1 {
 687         let mut i = 0;
 688         while i < candidates.vec.len() {
 689             let has_dup = (0..i).any(|j| candidates.vec[i] == candidates.vec[j]);
 690             if has_dup {
 691                 candidates.vec.swap_remove(i);
 692             } else {
 693                 i += 1;
 694             }
 695         }
 696     }
 697
 698     // Prefer where-clauses. As in select, if there are multiple
 699     // candidates, we prefer where-clause candidates over impls.  This
 700     // may seem a bit surprising, since impls are the source of
 701     // "truth" in some sense, but in fact some of the impls that SEEM
 702     // applicable are not, because of nested obligations. Where
 703     // clauses are the safer choice. See the comment on
 704     // `select::SelectionCandidate` and #21974 for more details.
 705     if candidates.vec.len() > 1 {
 706         debug!("retaining param-env candidates only from {:?}", candidates.vec);
 707         candidates.vec.retain(|c| match *c {
 708             ProjectionTyCandidate::ParamEnv(..) => true,
 709             ProjectionTyCandidate::TraitDef(..) |
 710             ProjectionTyCandidate::Select => false,
 711         });
 712         debug!("resulting candidate set: {:?}", candidates.vec);
 713         if candidates.vec.len() != 1 {
 714             return Err(ProjectionTyError::TooManyCandidates);
 715         }
 716     }
 717
 718     assert!(candidates.vec.len() <= 1);
 719
 720     match candidates.vec.pop() {
 721         Some(candidate) => {
 722             Ok(ProjectedTy::Progress(
 723                 confirm_candidate(selcx,
 724                                   obligation,
 725                                   &obligation_trait_ref,
 726                                   candidate)))
 727         }
 728         None => {
 729             Ok(ProjectedTy::NoProgress(
 730                 selcx.tcx().mk_projection(
 731                     obligation.predicate.trait_ref.clone(),
 732                     obligation.predicate.item_name)))
 733         }
 734     }
 735 }
 736
 737 /// The first thing we have to do is scan through the parameter
 738 /// environment to see whether there are any projection predicates
 739 /// there that can answer this question.
 740 fn assemble_candidates_from_param_env<'cx, 'gcx, 'tcx>(
 741     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 742     obligation: &ProjectionTyObligation<'tcx>,
 743     obligation_trait_ref: &ty::TraitRef<'tcx>,
 744     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 745 {
 746     debug!("assemble_candidates_from_param_env(..)");
 747     let env_predicates = selcx.param_env().caller_bounds.iter().cloned();
 748     assemble_candidates_from_predicates(selcx,
 749                                         obligation,
 750                                         obligation_trait_ref,
 751                                         candidate_set,
 752                                         ProjectionTyCandidate::ParamEnv,
 753                                         env_predicates);
 754 }
 755
 756 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
 757 /// that the definition of `Foo` has some clues:
 758 ///
 759 /// ```
 760 /// trait Foo {
 761 ///     type FooT : Bar<BarT=i32>
 762 /// }
 763 /// ```
 764 ///
 765 /// Here, for example, we could conclude that the result is `i32`.
 766 fn assemble_candidates_from_trait_def<'cx, 'gcx, 'tcx>(
 767     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 768     obligation: &ProjectionTyObligation<'tcx>,
 769     obligation_trait_ref: &ty::TraitRef<'tcx>,
 770     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 771 {
 772     debug!("assemble_candidates_from_trait_def(..)");
 773
 774     // Check whether the self-type is itself a projection.
 775     let (def_id, substs) = match obligation_trait_ref.self_ty().sty {
 776         ty::TyProjection(ref data) => {
 777             (data.trait_ref.def_id, data.trait_ref.substs)
 778         }
 779         ty::TyAnon(def_id, substs) => (def_id, substs),
 780         ty::TyInfer(ty::TyVar(_)) => {
 781             // If the self-type is an inference variable, then it MAY wind up
 782             // being a projected type, so induce an ambiguity.
 783             candidate_set.ambiguous = true;
 784             return;
 785         }
 786         _ => { return; }
 787     };
 788
 789     // If so, extract what we know from the trait and try to come up with a good answer.
 790     let trait_predicates = selcx.tcx().predicates_of(def_id);
 791     let bounds = trait_predicates.instantiate(selcx.tcx(), substs);
 792     let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates);
 793     assemble_candidates_from_predicates(selcx,
 794                                         obligation,
 795                                         obligation_trait_ref,
 796                                         candidate_set,
 797                                         ProjectionTyCandidate::TraitDef,
 798                                         bounds)
 799 }
 800
 801 fn assemble_candidates_from_predicates<'cx, 'gcx, 'tcx, I>(
 802     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 803     obligation: &ProjectionTyObligation<'tcx>,
 804     obligation_trait_ref: &ty::TraitRef<'tcx>,
 805     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 806     ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
 807     env_predicates: I)
 808     where I: Iterator<Item=ty::Predicate<'tcx>>
 809 {
 810     debug!("assemble_candidates_from_predicates(obligation={:?})",
 811            obligation);
 812     let infcx = selcx.infcx();
 813     for predicate in env_predicates {
 814         debug!("assemble_candidates_from_predicates: predicate={:?}",
 815                predicate);
 816         match predicate {
 817             ty::Predicate::Projection(ref data) => {
 818                 let same_name = data.item_name() == obligation.predicate.item_name;
 819
 820                 let is_match = same_name && infcx.probe(|_| {
 821                     let data_poly_trait_ref =
 822                         data.to_poly_trait_ref();
 823                     let obligation_poly_trait_ref =
 824                         obligation_trait_ref.to_poly_trait_ref();
 825                     infcx.sub_poly_trait_refs(false,
 826                                               obligation.cause.clone(),
 827                                               data_poly_trait_ref,
 828                                               obligation_poly_trait_ref)
 829                         .map(|InferOk { obligations: _, value: () }| {
 830                             // FIXME(#32730) -- do we need to take obligations
 831                             // into account in any way? At the moment, no.
 832                         })
 833                         .is_ok()
 834                 });
 835
 836                 debug!("assemble_candidates_from_predicates: candidate={:?} \
 837                                                              is_match={} same_name={}",
 838                        data, is_match, same_name);
 839
 840                 if is_match {
 841                     candidate_set.vec.push(ctor(data.clone()));
 842                 }
 843             }
 844             _ => { }
 845         }
 846     }
 847 }
 848
 849 fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
 850     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 851     obligation: &ProjectionTyObligation<'tcx>,
 852     obligation_trait_ref: &ty::TraitRef<'tcx>,
 853     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 854     -> Result<(), SelectionError<'tcx>>
 855 {
 856     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
 857     // start out by selecting the predicate `T as TraitRef<...>`:
 858     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
 859     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
 860     selcx.infcx().probe(|_| {
 861         let vtable = match selcx.select(&trait_obligation) {
 862             Ok(Some(vtable)) => vtable,
 863             Ok(None) => {
 864                 candidate_set.ambiguous = true;
 865                 return Ok(());
 866             }
 867             Err(e) => {
 868                 debug!("assemble_candidates_from_impls: selection error {:?}",
 869                        e);
 870                 return Err(e);
 871             }
 872         };
 873
 874         match vtable {
 875             super::VtableClosure(_) |
 876             super::VtableFnPointer(_) |
 877             super::VtableObject(_) => {
 878                 debug!("assemble_candidates_from_impls: vtable={:?}",
 879                        vtable);
 880
 881                 candidate_set.vec.push(ProjectionTyCandidate::Select);
 882             }
 883             super::VtableImpl(ref impl_data) => {
 884                 // We have to be careful when projecting out of an
 885                 // impl because of specialization. If we are not in
 886                 // trans (i.e., projection mode is not "any"), and the
 887                 // impl's type is declared as default, then we disable
 888                 // projection (even if the trait ref is fully
 889                 // monomorphic). In the case where trait ref is not
 890                 // fully monomorphic (i.e., includes type parameters),
 891                 // this is because those type parameters may
 892                 // ultimately be bound to types from other crates that
 893                 // may have specialized impls we can't see. In the
 894                 // case where the trait ref IS fully monomorphic, this
 895                 // is a policy decision that we made in the RFC in
 896                 // order to preserve flexibility for the crate that
 897                 // defined the specializable impl to specialize later
 898                 // for existing types.
 899                 //
 900                 // In either case, we handle this by not adding a
 901                 // candidate for an impl if it contains a `default`
 902                 // type.
 903                 let opt_node_item = assoc_ty_def(selcx,
 904                                                  impl_data.impl_def_id,
 905                                                  obligation.predicate.item_name);
 906                 let new_candidate = if let Some(node_item) = opt_node_item {
 907                     let is_default = if node_item.node.is_from_trait() {
 908                         // If true, the impl inherited a `type Foo = Bar`
 909                         // given in the trait, which is implicitly default.
 910                         // Otherwise, the impl did not specify `type` and
 911                         // neither did the trait:
 912                         //
 913                         // ```rust
 914                         // trait Foo { type T; }
 915                         // impl Foo for Bar { }
 916                         // ```
 917                         //
 918                         // This is an error, but it will be
 919                         // reported in `check_impl_items_against_trait`.
 920                         // We accept it here but will flag it as
 921                         // an error when we confirm the candidate
 922                         // (which will ultimately lead to `normalize_to_error`
 923                         // being invoked).
 924                         node_item.item.defaultness.has_value()
 925                     } else {
 926                         node_item.item.defaultness.is_default() ||
 927                         selcx.tcx().impl_is_default(node_item.node.def_id())
 928                     };
 929
 930                     // Only reveal a specializable default if we're past type-checking
 931                     // and the obligations is monomorphic, otherwise passes such as
 932                     // transmute checking and polymorphic MIR optimizations could
 933                     // get a result which isn't correct for all monomorphizations.
 934                     if !is_default {
 935                         Some(ProjectionTyCandidate::Select)
 936                     } else if selcx.projection_mode() == Reveal::All {
 937                         assert!(!poly_trait_ref.needs_infer());
 938                         if !poly_trait_ref.needs_subst() {
 939                             Some(ProjectionTyCandidate::Select)
 940                         } else {
 941                             None
 942                         }
 943                     } else {
 944                         None
 945                     }
 946                 } else {
 947                     // This is saying that neither the trait nor
 948                     // the impl contain a definition for this
 949                     // associated type.  Normally this situation
 950                     // could only arise through a compiler bug --
 951                     // if the user wrote a bad item name, it
 952                     // should have failed in astconv. **However**,
 953                     // at coherence-checking time, we only look at
 954                     // the topmost impl (we don't even consider
 955                     // the trait itself) for the definition -- and
 956                     // so in that case it may be that the trait
 957                     // *DOES* have a declaration, but we don't see
 958                     // it, and we end up in this branch.
 959                     //
 960                     // This is kind of tricky to handle actually.
 961                     // For now, we just unconditionally ICE,
 962                     // because otherwise, examples like the
 963                     // following will succeed:
 964                     //
 965                     // ```
 966                     // trait Assoc {
 967                     //     type Output;
 968                     // }
 969                     //
 970                     // impl<T> Assoc for T {
 971                     //     default type Output = bool;
 972                     // }
 973                     //
 974                     // impl Assoc for u8 {}
 975                     // impl Assoc for u16 {}
 976                     //
 977                     // trait Foo {}
 978                     // impl Foo for <u8 as Assoc>::Output {}
 979                     // impl Foo for <u16 as Assoc>::Output {}
 980                     //     return None;
 981                     // }
 982                     // ```
 983                     //
 984                     // The essential problem here is that the
 985                     // projection fails, leaving two unnormalized
 986                     // types, which appear not to unify -- so the
 987                     // overlap check succeeds, when it should
 988                     // fail.
 989                     span_bug!(obligation.cause.span,
 990                               "Tried to project an inherited associated type during \
 991                                coherence checking, which is currently not supported.");
 992                 };
 993                 candidate_set.vec.extend(new_candidate);
 994             }
 995             super::VtableParam(..) => {
 996                 // This case tell us nothing about the value of an
 997                 // associated type. Consider:
 998                 //
 999                 // ```
1000                 // trait SomeTrait { type Foo; }
1001                 // fn foo<T:SomeTrait>(...) { }
1002                 // ```
1003                 //
1004                 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1005                 // : SomeTrait` binding does not help us decide what the
1006                 // type `Foo` is (at least, not more specifically than
1007                 // what we already knew).
1008                 //
1009                 // But wait, you say! What about an example like this:
1010                 //
1011                 // ```
1012                 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1013                 // ```
1014                 //
1015                 // Doesn't the `T : Sometrait<Foo=usize>` predicate help
1016                 // resolve `T::Foo`? And of course it does, but in fact
1017                 // that single predicate is desugared into two predicates
1018                 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1019                 // projection. And the projection where clause is handled
1020                 // in `assemble_candidates_from_param_env`.
1021             }
1022             super::VtableDefaultImpl(..) |
1023             super::VtableBuiltin(..) => {
1024                 // These traits have no associated types.
1025                 span_bug!(
1026                     obligation.cause.span,
1027                     "Cannot project an associated type from `{:?}`",
1028                     vtable);
1029             }
1030         }
1031
1032         Ok(())
1033     })
1034 }
1035
1036 fn confirm_candidate<'cx, 'gcx, 'tcx>(
1037     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1038     obligation: &ProjectionTyObligation<'tcx>,
1039     obligation_trait_ref: &ty::TraitRef<'tcx>,
1040     candidate: ProjectionTyCandidate<'tcx>)
1041     -> Progress<'tcx>
1042 {
1043     debug!("confirm_candidate(candidate={:?}, obligation={:?})",
1044            candidate,
1045            obligation);
1046
1047     match candidate {
1048         ProjectionTyCandidate::ParamEnv(poly_projection) |
1049         ProjectionTyCandidate::TraitDef(poly_projection) => {
1050             confirm_param_env_candidate(selcx, obligation, poly_projection)
1051         }
1052
1053         ProjectionTyCandidate::Select => {
1054             confirm_select_candidate(selcx, obligation, obligation_trait_ref)
1055         }
1056     }
1057 }
1058
1059 fn confirm_select_candidate<'cx, 'gcx, 'tcx>(
1060     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1061     obligation: &ProjectionTyObligation<'tcx>,
1062     obligation_trait_ref: &ty::TraitRef<'tcx>)
1063     -> Progress<'tcx>
1064 {
1065     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
1066     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
1067     let vtable = match selcx.select(&trait_obligation) {
1068         Ok(Some(vtable)) => vtable,
1069         _ => {
1070             span_bug!(
1071                 obligation.cause.span,
1072                 "Failed to select `{:?}`",
1073                 trait_obligation);
1074         }
1075     };
1076
1077     match vtable {
1078         super::VtableImpl(data) =>
1079             confirm_impl_candidate(selcx, obligation, data),
1080         super::VtableClosure(data) =>
1081             confirm_closure_candidate(selcx, obligation, data),
1082         super::VtableFnPointer(data) =>
1083             confirm_fn_pointer_candidate(selcx, obligation, data),
1084         super::VtableObject(_) =>
1085             confirm_object_candidate(selcx, obligation, obligation_trait_ref),
1086         super::VtableDefaultImpl(..) |
1087         super::VtableParam(..) |
1088         super::VtableBuiltin(..) =>
1089             // we don't create Select candidates with this kind of resolution
1090             span_bug!(
1091                 obligation.cause.span,
1092                 "Cannot project an associated type from `{:?}`",
1093                 vtable),
1094     }
1095 }
1096
1097 fn confirm_object_candidate<'cx, 'gcx, 'tcx>(
1098     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1099     obligation:  &ProjectionTyObligation<'tcx>,
1100     obligation_trait_ref: &ty::TraitRef<'tcx>)
1101     -> Progress<'tcx>
1102 {
1103     let self_ty = obligation_trait_ref.self_ty();
1104     let object_ty = selcx.infcx().shallow_resolve(self_ty);
1105     debug!("confirm_object_candidate(object_ty={:?})",
1106            object_ty);
1107     let data = match object_ty.sty {
1108         ty::TyDynamic(ref data, ..) => data,
1109         _ => {
1110             span_bug!(
1111                 obligation.cause.span,
1112                 "confirm_object_candidate called with non-object: {:?}",
1113                 object_ty)
1114         }
1115     };
1116     let env_predicates = data.projection_bounds().map(|p| {
1117         p.with_self_ty(selcx.tcx(), object_ty).to_predicate()
1118     }).collect();
1119     let env_predicate = {
1120         let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
1121
1122         // select only those projections that are actually projecting an
1123         // item with the correct name
1124         let env_predicates = env_predicates.filter_map(|p| match p {
1125             ty::Predicate::Projection(data) =>
1126                 if data.item_name() == obligation.predicate.item_name {
1127                     Some(data)
1128                 } else {
1129                     None
1130                 },
1131             _ => None
1132         });
1133
1134         // select those with a relevant trait-ref
1135         let mut env_predicates = env_predicates.filter(|data| {
1136             let data_poly_trait_ref = data.to_poly_trait_ref();
1137             let obligation_poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
1138             selcx.infcx().probe(|_| {
1139                 selcx.infcx().sub_poly_trait_refs(false,
1140                                                   obligation.cause.clone(),
1141                                                   data_poly_trait_ref,
1142                                                   obligation_poly_trait_ref).is_ok()
1143             })
1144         });
1145
1146         // select the first matching one; there really ought to be one or
1147         // else the object type is not WF, since an object type should
1148         // include all of its projections explicitly
1149         match env_predicates.next() {
1150             Some(env_predicate) => env_predicate,
1151             None => {
1152                 debug!("confirm_object_candidate: no env-predicate \
1153                         found in object type `{:?}`; ill-formed",
1154                        object_ty);
1155                 return Progress::error(selcx.tcx());
1156             }
1157         }
1158     };
1159
1160     confirm_param_env_candidate(selcx, obligation, env_predicate)
1161 }
1162
1163 fn confirm_fn_pointer_candidate<'cx, 'gcx, 'tcx>(
1164     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1165     obligation: &ProjectionTyObligation<'tcx>,
1166     fn_pointer_vtable: VtableFnPointerData<'tcx, PredicateObligation<'tcx>>)
1167     -> Progress<'tcx>
1168 {
1169     let fn_type = selcx.infcx().shallow_resolve(fn_pointer_vtable.fn_ty);
1170     let sig = fn_type.fn_sig();
1171     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1172         .with_addl_obligations(fn_pointer_vtable.nested)
1173 }
1174
1175 fn confirm_closure_candidate<'cx, 'gcx, 'tcx>(
1176     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1177     obligation: &ProjectionTyObligation<'tcx>,
1178     vtable: VtableClosureData<'tcx, PredicateObligation<'tcx>>)
1179     -> Progress<'tcx>
1180 {
1181     let closure_typer = selcx.closure_typer();
1182     let closure_type = closure_typer.closure_type(vtable.closure_def_id)
1183         .subst(selcx.tcx(), vtable.substs.substs);
1184     let Normalized {
1185         value: closure_type,
1186         obligations
1187     } = normalize_with_depth(selcx,
1188                              obligation.cause.clone(),
1189                              obligation.recursion_depth+1,
1190                              &closure_type);
1191
1192     debug!("confirm_closure_candidate: obligation={:?},closure_type={:?},obligations={:?}",
1193            obligation,
1194            closure_type,
1195            obligations);
1196
1197     confirm_callable_candidate(selcx,
1198                                obligation,
1199                                closure_type,
1200                                util::TupleArgumentsFlag::No)
1201         .with_addl_obligations(vtable.nested)
1202         .with_addl_obligations(obligations)
1203 }
1204
1205 fn confirm_callable_candidate<'cx, 'gcx, 'tcx>(
1206     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1207     obligation: &ProjectionTyObligation<'tcx>,
1208     fn_sig: ty::PolyFnSig<'tcx>,
1209     flag: util::TupleArgumentsFlag)
1210     -> Progress<'tcx>
1211 {
1212     let tcx = selcx.tcx();
1213
1214     debug!("confirm_callable_candidate({:?},{:?})",
1215            obligation,
1216            fn_sig);
1217
1218     // the `Output` associated type is declared on `FnOnce`
1219     let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap();
1220
1221     // Note: we unwrap the binder here but re-create it below (1)
1222     let ty::Binder((trait_ref, ret_type)) =
1223         tcx.closure_trait_ref_and_return_type(fn_once_def_id,
1224                                               obligation.predicate.trait_ref.self_ty(),
1225                                               fn_sig,
1226                                               flag);
1227
1228     let predicate = ty::Binder(ty::ProjectionPredicate { // (1) recreate binder here
1229         projection_ty: ty::ProjectionTy {
1230             trait_ref: trait_ref,
1231             item_name: Symbol::intern(FN_OUTPUT_NAME),
1232         },
1233         ty: ret_type
1234     });
1235
1236     confirm_param_env_candidate(selcx, obligation, predicate)
1237 }
1238
1239 fn confirm_param_env_candidate<'cx, 'gcx, 'tcx>(
1240     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1241     obligation: &ProjectionTyObligation<'tcx>,
1242     poly_projection: ty::PolyProjectionPredicate<'tcx>)
1243     -> Progress<'tcx>
1244 {
1245     let infcx = selcx.infcx();
1246     let cause = obligation.cause.clone();
1247     let trait_ref = obligation.predicate.trait_ref;
1248     match infcx.match_poly_projection_predicate(cause, poly_projection, trait_ref) {
1249         Ok(InferOk { value: ty_match, obligations }) => {
1250             Progress {
1251                 ty: ty_match.value,
1252                 obligations: obligations,
1253                 cacheable: ty_match.unconstrained_regions.is_empty(),
1254             }
1255         }
1256         Err(e) => {
1257             span_bug!(
1258                 obligation.cause.span,
1259                 "Failed to unify obligation `{:?}` \
1260                  with poly_projection `{:?}`: {:?}",
1261                 obligation,
1262                 poly_projection,
1263                 e);
1264         }
1265     }
1266 }
1267
1268 fn confirm_impl_candidate<'cx, 'gcx, 'tcx>(
1269     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
1270     obligation: &ProjectionTyObligation<'tcx>,
1271     impl_vtable: VtableImplData<'tcx, PredicateObligation<'tcx>>)
1272     -> Progress<'tcx>
1273 {
1274     let VtableImplData { substs, nested, impl_def_id } = impl_vtable;
1275
1276     let tcx = selcx.tcx();
1277     let trait_ref = obligation.predicate.trait_ref;
1278     let assoc_ty = assoc_ty_def(selcx, impl_def_id, obligation.predicate.item_name);
1279
1280     match assoc_ty {
1281         Some(node_item) => {
1282             let ty = if !node_item.item.defaultness.has_value() {
1283                 // This means that the impl is missing a definition for the
1284                 // associated type. This error will be reported by the type
1285                 // checker method `check_impl_items_against_trait`, so here we
1286                 // just return TyError.
1287                 debug!("confirm_impl_candidate: no associated type {:?} for {:?}",
1288                        node_item.item.name,
1289                        obligation.predicate.trait_ref);
1290                 tcx.types.err
1291             } else {
1292                 tcx.type_of(node_item.item.def_id)
1293             };
1294             let substs = translate_substs(selcx.infcx(), impl_def_id, substs, node_item.node);
1295             Progress {
1296                 ty: ty.subst(tcx, substs),
1297                 obligations: nested,
1298                 cacheable: true
1299             }
1300         }
1301         None => {
1302             span_bug!(obligation.cause.span,
1303                       "No associated type for {:?}",
1304                       trait_ref);
1305         }
1306     }
1307 }
1308
1309 /// Locate the definition of an associated type in the specialization hierarchy,
1310 /// starting from the given impl.
1311 ///
1312 /// Based on the "projection mode", this lookup may in fact only examine the
1313 /// topmost impl. See the comments for `Reveal` for more details.
1314 fn assoc_ty_def<'cx, 'gcx, 'tcx>(
1315     selcx: &SelectionContext<'cx, 'gcx, 'tcx>,
1316     impl_def_id: DefId,
1317     assoc_ty_name: ast::Name)
1318     -> Option<specialization_graph::NodeItem<ty::AssociatedItem>>
1319 {
1320     let trait_def_id = selcx.tcx().impl_trait_ref(impl_def_id).unwrap().def_id;
1321     let trait_def = selcx.tcx().trait_def(trait_def_id);
1322
1323     if !trait_def.is_complete(selcx.tcx()) {
1324         let impl_node = specialization_graph::Node::Impl(impl_def_id);
1325         for item in impl_node.items(selcx.tcx()) {
1326             if item.kind == ty::AssociatedKind::Type && item.name == assoc_ty_name {
1327                 return Some(specialization_graph::NodeItem {
1328                     node: specialization_graph::Node::Impl(impl_def_id),
1329                     item: item,
1330                 });
1331             }
1332         }
1333         None
1334     } else {
1335         trait_def
1336             .ancestors(impl_def_id)
1337             .defs(selcx.tcx(), assoc_ty_name, ty::AssociatedKind::Type)
1338             .next()
1339     }
1340 }
1341
1342 // # Cache
1343
1344 pub struct ProjectionCache<'tcx> {
1345     map: SnapshotMap<ty::ProjectionTy<'tcx>, ProjectionCacheEntry<'tcx>>,
1346 }
1347
1348 #[derive(Clone, Debug)]
1349 enum ProjectionCacheEntry<'tcx> {
1350     InProgress,
1351     Ambiguous,
1352     Error,
1353     NormalizedTy(Ty<'tcx>),
1354 }
1355
1356 // NB: intentionally not Clone
1357 pub struct ProjectionCacheSnapshot {
1358     snapshot: Snapshot
1359 }
1360
1361 impl<'tcx> ProjectionCache<'tcx> {
1362     pub fn new() -> Self {
1363         ProjectionCache {
1364             map: SnapshotMap::new()
1365         }
1366     }
1367
1368     pub fn snapshot(&mut self) -> ProjectionCacheSnapshot {
1369         ProjectionCacheSnapshot { snapshot: self.map.snapshot() }
1370     }
1371
1372     pub fn rollback_to(&mut self, snapshot: ProjectionCacheSnapshot) {
1373         self.map.rollback_to(snapshot.snapshot);
1374     }
1375
1376     pub fn rollback_skolemized(&mut self, snapshot: &ProjectionCacheSnapshot) {
1377         self.map.partial_rollback(&snapshot.snapshot, &|k| k.has_re_skol());
1378     }
1379
1380     pub fn commit(&mut self, snapshot: ProjectionCacheSnapshot) {
1381         self.map.commit(snapshot.snapshot);
1382     }
1383
1384     /// Try to start normalize `key`; returns an error if
1385     /// normalization already occured (this error corresponds to a
1386     /// cache hit, so it's actually a good thing).
1387     fn try_start(&mut self, key: ty::ProjectionTy<'tcx>)
1388                  -> Result<(), ProjectionCacheEntry<'tcx>> {
1389         if let Some(entry) = self.map.get(&key) {
1390             return Err(entry.clone());
1391         }
1392
1393         self.map.insert(key, ProjectionCacheEntry::InProgress);
1394         Ok(())
1395     }
1396
1397     /// Indicates that `key` was normalized to `value`. If `cacheable` is false,
1398     /// then this result is sadly not cacheable.
1399     fn complete(&mut self,
1400                 key: ty::ProjectionTy<'tcx>,
1401                 value: &NormalizedTy<'tcx>,
1402                 cacheable: bool) {
1403         let fresh_key = if cacheable {
1404             debug!("ProjectionCacheEntry::complete: adding cache entry: key={:?}, value={:?}",
1405                    key, value);
1406             self.map.insert(key, ProjectionCacheEntry::NormalizedTy(value.value))
1407         } else {
1408             debug!("ProjectionCacheEntry::complete: cannot cache: key={:?}, value={:?}",
1409                    key, value);
1410             !self.map.remove(key)
1411         };
1412
1413         assert!(!fresh_key, "never started projecting `{:?}`", key);
1414     }
1415
1416     /// Indicates that trying to normalize `key` resulted in
1417     /// ambiguity. No point in trying it again then until we gain more
1418     /// type information (in which case, the "fully resolved" key will
1419     /// be different).
1420     fn ambiguous(&mut self, key: ty::ProjectionTy<'tcx>) {
1421         let fresh = self.map.insert(key, ProjectionCacheEntry::Ambiguous);
1422         assert!(!fresh, "never started projecting `{:?}`", key);
1423     }
1424
1425     /// Indicates that trying to normalize `key` resulted in
1426     /// error.
1427     fn error(&mut self, key: ty::ProjectionTy<'tcx>) {
1428         let fresh = self.map.insert(key, ProjectionCacheEntry::Error);
1429         assert!(!fresh, "never started projecting `{:?}`", key);
1430     }
1431 }