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