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