src/librustc/middle/traits/project.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Code for projecting associated types out of trait references.
  12
  13 use super::elaborate_predicates;
  14 use super::report_overflow_error;
  15 use super::specialization_graph;
  16 use super::translate_substs;
  17 use super::Obligation;
  18 use super::ObligationCause;
  19 use super::PredicateObligation;
  20 use super::SelectionContext;
  21 use super::SelectionError;
  22 use super::VtableClosureData;
  23 use super::VtableImplData;
  24 use super::util;
  25
  26 use middle::def_id::DefId;
  27 use middle::infer::{self, TypeOrigin};
  28 use middle::subst::Subst;
  29 use middle::ty::{self, ToPredicate, RegionEscape, HasTypeFlags, ToPolyTraitRef, Ty, TyCtxt};
  30 use middle::ty::fold::{TypeFoldable, TypeFolder};
  31 use rustc_front::hir;
  32 use syntax::parse::token;
  33 use syntax::ast;
  34 use util::common::FN_OUTPUT_NAME;
  35
  36 use std::rc::Rc;
  37
  38 pub type PolyProjectionObligation<'tcx> =
  39     Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  40
  41 pub type ProjectionObligation<'tcx> =
  42     Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  43
  44 pub type ProjectionTyObligation<'tcx> =
  45     Obligation<'tcx, ty::ProjectionTy<'tcx>>;
  46
  47 /// When attempting to resolve `<T as TraitRef>::Name` ...
  48 #[derive(Debug)]
  49 pub enum ProjectionTyError<'tcx> {
  50     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  51     TooManyCandidates,
  52
  53     /// ...an error occurred matching `T : TraitRef`
  54     TraitSelectionError(SelectionError<'tcx>),
  55 }
  56
  57 #[derive(Clone)]
  58 pub struct MismatchedProjectionTypes<'tcx> {
  59     pub err: ty::error::TypeError<'tcx>
  60 }
  61
  62 #[derive(PartialEq, Eq, Debug)]
  63 enum ProjectionTyCandidate<'tcx> {
  64     // from a where-clause in the env or object type
  65     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
  66
  67     // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
  68     TraitDef(ty::PolyProjectionPredicate<'tcx>),
  69
  70     // defined in an impl
  71     Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
  72
  73     // closure return type
  74     Closure(VtableClosureData<'tcx, PredicateObligation<'tcx>>),
  75
  76     // fn pointer return type
  77     FnPointer(Ty<'tcx>),
  78 }
  79
  80 struct ProjectionTyCandidateSet<'tcx> {
  81     vec: Vec<ProjectionTyCandidate<'tcx>>,
  82     ambiguous: bool
  83 }
  84
  85 /// Evaluates constraints of the form:
  86 ///
  87 ///     for<...> <T as Trait>::U == V
  88 ///
  89 /// If successful, this may result in additional obligations.
  90 pub fn poly_project_and_unify_type<'cx,'tcx>(
  91     selcx: &mut SelectionContext<'cx,'tcx>,
  92     obligation: &PolyProjectionObligation<'tcx>)
  93     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
  94 {
  95     debug!("poly_project_and_unify_type(obligation={:?})",
  96            obligation);
  97
  98     let infcx = selcx.infcx();
  99     infcx.commit_if_ok(|snapshot| {
 100         let (skol_predicate, skol_map) =
 101             infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
 102
 103         let skol_obligation = obligation.with(skol_predicate);
 104         match project_and_unify_type(selcx, &skol_obligation) {
 105             Ok(result) => {
 106                 match infcx.leak_check(&skol_map, snapshot) {
 107                     Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, &result)),
 108                     Err(e) => Err(MismatchedProjectionTypes { err: e }),
 109                 }
 110             }
 111             Err(e) => {
 112                 Err(e)
 113             }
 114         }
 115     })
 116 }
 117
 118 /// Evaluates constraints of the form:
 119 ///
 120 ///     <T as Trait>::U == V
 121 ///
 122 /// If successful, this may result in additional obligations.
 123 fn project_and_unify_type<'cx,'tcx>(
 124     selcx: &mut SelectionContext<'cx,'tcx>,
 125     obligation: &ProjectionObligation<'tcx>)
 126     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 127 {
 128     debug!("project_and_unify_type(obligation={:?})",
 129            obligation);
 130
 131     let Normalized { value: normalized_ty, obligations } =
 132         match opt_normalize_projection_type(selcx,
 133                                             obligation.predicate.projection_ty.clone(),
 134                                             obligation.cause.clone(),
 135                                             obligation.recursion_depth) {
 136             Some(n) => n,
 137             None => {
 138                 consider_unification_despite_ambiguity(selcx, obligation);
 139                 return Ok(None);
 140             }
 141         };
 142
 143     debug!("project_and_unify_type: normalized_ty={:?} obligations={:?}",
 144            normalized_ty,
 145            obligations);
 146
 147     let infcx = selcx.infcx();
 148     let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
 149     match infer::mk_eqty(infcx, true, origin, normalized_ty, obligation.predicate.ty) {
 150         Ok(()) => Ok(Some(obligations)),
 151         Err(err) => Err(MismatchedProjectionTypes { err: err }),
 152     }
 153 }
 154
 155 fn consider_unification_despite_ambiguity<'cx,'tcx>(selcx: &mut SelectionContext<'cx,'tcx>,
 156                                                     obligation: &ProjectionObligation<'tcx>) {
 157     debug!("consider_unification_despite_ambiguity(obligation={:?})",
 158            obligation);
 159
 160     let def_id = obligation.predicate.projection_ty.trait_ref.def_id;
 161     match selcx.tcx().lang_items.fn_trait_kind(def_id) {
 162         Some(_) => { }
 163         None => { return; }
 164     }
 165
 166     let infcx = selcx.infcx();
 167     let self_ty = obligation.predicate.projection_ty.trait_ref.self_ty();
 168     let self_ty = infcx.shallow_resolve(self_ty);
 169     debug!("consider_unification_despite_ambiguity: self_ty.sty={:?}",
 170            self_ty.sty);
 171     match self_ty.sty {
 172         ty::TyClosure(closure_def_id, ref substs) => {
 173             let closure_typer = selcx.closure_typer();
 174             let closure_type = closure_typer.closure_type(closure_def_id, substs);
 175             let ty::Binder((_, ret_type)) =
 176                 util::closure_trait_ref_and_return_type(infcx.tcx,
 177                                                         def_id,
 178                                                         self_ty,
 179                                                         &closure_type.sig,
 180                                                         util::TupleArgumentsFlag::No);
 181             // We don't have to normalize the return type here - this is only
 182             // reached for TyClosure: Fn inputs where the closure kind is
 183             // still unknown, which should only occur in typeck where the
 184             // closure type is already normalized.
 185             let (ret_type, _) =
 186                 infcx.replace_late_bound_regions_with_fresh_var(
 187                     obligation.cause.span,
 188                     infer::AssocTypeProjection(obligation.predicate.projection_ty.item_name),
 189                     &ty::Binder(ret_type));
 190
 191             debug!("consider_unification_despite_ambiguity: ret_type={:?}",
 192                    ret_type);
 193             let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
 194             let obligation_ty = obligation.predicate.ty;
 195             match infer::mk_eqty(infcx, true, origin, obligation_ty, ret_type) {
 196                 Ok(()) => { }
 197                 Err(_) => { /* ignore errors */ }
 198             }
 199         }
 200         _ => { }
 201     }
 202 }
 203
 204 /// Normalizes any associated type projections in `value`, replacing
 205 /// them with a fully resolved type where possible. The return value
 206 /// combines the normalized result and any additional obligations that
 207 /// were incurred as result.
 208 pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
 209                                cause: ObligationCause<'tcx>,
 210                                value: &T)
 211                                -> Normalized<'tcx, T>
 212     where T : TypeFoldable<'tcx>
 213 {
 214     normalize_with_depth(selcx, cause, 0, value)
 215 }
 216
 217 /// As `normalize`, but with a custom depth.
 218 pub fn normalize_with_depth<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
 219                                           cause: ObligationCause<'tcx>,
 220                                           depth: usize,
 221                                           value: &T)
 222                                           -> Normalized<'tcx, T>
 223     where T : TypeFoldable<'tcx>
 224 {
 225     let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth);
 226     let result = normalizer.fold(value);
 227
 228     Normalized {
 229         value: result,
 230         obligations: normalizer.obligations,
 231     }
 232 }
 233
 234 struct AssociatedTypeNormalizer<'a,'b:'a,'tcx:'b> {
 235     selcx: &'a mut SelectionContext<'b,'tcx>,
 236     cause: ObligationCause<'tcx>,
 237     obligations: Vec<PredicateObligation<'tcx>>,
 238     depth: usize,
 239 }
 240
 241 impl<'a,'b,'tcx> AssociatedTypeNormalizer<'a,'b,'tcx> {
 242     fn new(selcx: &'a mut SelectionContext<'b,'tcx>,
 243            cause: ObligationCause<'tcx>,
 244            depth: usize)
 245            -> AssociatedTypeNormalizer<'a,'b,'tcx>
 246     {
 247         AssociatedTypeNormalizer {
 248             selcx: selcx,
 249             cause: cause,
 250             obligations: vec!(),
 251             depth: depth,
 252         }
 253     }
 254
 255     fn fold<T:TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
 256         let value = self.selcx.infcx().resolve_type_vars_if_possible(value);
 257
 258         if !value.has_projection_types() {
 259             value.clone()
 260         } else {
 261             value.fold_with(self)
 262         }
 263     }
 264 }
 265
 266 impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
 267     fn tcx(&self) -> &TyCtxt<'tcx> {
 268         self.selcx.tcx()
 269     }
 270
 271     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 272         // We don't want to normalize associated types that occur inside of region
 273         // binders, because they may contain bound regions, and we can't cope with that.
 274         //
 275         // Example:
 276         //
 277         //     for<'a> fn(<T as Foo<&'a>>::A)
 278         //
 279         // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll
 280         // normalize it when we instantiate those bound regions (which
 281         // should occur eventually).
 282
 283         let ty = ty.super_fold_with(self);
 284         match ty.sty {
 285             ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*)
 286
 287                 // (*) This is kind of hacky -- we need to be able to
 288                 // handle normalization within binders because
 289                 // otherwise we wind up a need to normalize when doing
 290                 // trait matching (since you can have a trait
 291                 // obligation like `for<'a> T::B : Fn(&'a int)`), but
 292                 // we can't normalize with bound regions in scope. So
 293                 // far now we just ignore binders but only normalize
 294                 // if all bound regions are gone (and then we still
 295                 // have to renormalize whenever we instantiate a
 296                 // binder). It would be better to normalize in a
 297                 // binding-aware fashion.
 298
 299                 let Normalized { value: ty, obligations } =
 300                     normalize_projection_type(self.selcx,
 301                                               data.clone(),
 302                                               self.cause.clone(),
 303                                               self.depth);
 304                 self.obligations.extend(obligations);
 305                 ty
 306             }
 307
 308             _ => {
 309                 ty
 310             }
 311         }
 312     }
 313 }
 314
 315 #[derive(Clone)]
 316 pub struct Normalized<'tcx,T> {
 317     pub value: T,
 318     pub obligations: Vec<PredicateObligation<'tcx>>,
 319 }
 320
 321 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
 322
 323 impl<'tcx,T> Normalized<'tcx,T> {
 324     pub fn with<U>(self, value: U) -> Normalized<'tcx,U> {
 325         Normalized { value: value, obligations: self.obligations }
 326     }
 327 }
 328
 329 /// The guts of `normalize`: normalize a specific projection like `<T
 330 /// as Trait>::Item`. The result is always a type (and possibly
 331 /// additional obligations). If ambiguity arises, which implies that
 332 /// there are unresolved type variables in the projection, we will
 333 /// substitute a fresh type variable `$X` and generate a new
 334 /// obligation `<T as Trait>::Item == $X` for later.
 335 pub fn normalize_projection_type<'a,'b,'tcx>(
 336     selcx: &'a mut SelectionContext<'b,'tcx>,
 337     projection_ty: ty::ProjectionTy<'tcx>,
 338     cause: ObligationCause<'tcx>,
 339     depth: usize)
 340     -> NormalizedTy<'tcx>
 341 {
 342     opt_normalize_projection_type(selcx, projection_ty.clone(), cause.clone(), depth)
 343         .unwrap_or_else(move || {
 344             // if we bottom out in ambiguity, create a type variable
 345             // and a deferred predicate to resolve this when more type
 346             // information is available.
 347
 348             let ty_var = selcx.infcx().next_ty_var();
 349             let projection = ty::Binder(ty::ProjectionPredicate {
 350                 projection_ty: projection_ty,
 351                 ty: ty_var
 352             });
 353             let obligation = Obligation::with_depth(
 354                 cause, depth + 1, projection.to_predicate());
 355             Normalized {
 356                 value: ty_var,
 357                 obligations: vec!(obligation)
 358             }
 359         })
 360 }
 361
 362 /// The guts of `normalize`: normalize a specific projection like `<T
 363 /// as Trait>::Item`. The result is always a type (and possibly
 364 /// additional obligations). Returns `None` in the case of ambiguity,
 365 /// which indicates that there are unbound type variables.
 366 fn opt_normalize_projection_type<'a,'b,'tcx>(
 367     selcx: &'a mut SelectionContext<'b,'tcx>,
 368     projection_ty: ty::ProjectionTy<'tcx>,
 369     cause: ObligationCause<'tcx>,
 370     depth: usize)
 371     -> Option<NormalizedTy<'tcx>>
 372 {
 373     debug!("normalize_projection_type(\
 374            projection_ty={:?}, \
 375            depth={})",
 376            projection_ty,
 377            depth);
 378
 379     let obligation = Obligation::with_depth(cause.clone(), depth, projection_ty.clone());
 380     match project_type(selcx, &obligation) {
 381         Ok(ProjectedTy::Progress(projected_ty, mut obligations)) => {
 382             // if projection succeeded, then what we get out of this
 383             // is also non-normalized (consider: it was derived from
 384             // an impl, where-clause etc) and hence we must
 385             // re-normalize it
 386
 387             debug!("normalize_projection_type: projected_ty={:?} depth={} obligations={:?}",
 388                    projected_ty,
 389                    depth,
 390                    obligations);
 391
 392             if projected_ty.has_projection_types() {
 393                 let mut normalizer = AssociatedTypeNormalizer::new(selcx, cause, depth+1);
 394                 let normalized_ty = normalizer.fold(&projected_ty);
 395
 396                 debug!("normalize_projection_type: normalized_ty={:?} depth={}",
 397                        normalized_ty,
 398                        depth);
 399
 400                 obligations.extend(normalizer.obligations);
 401                 Some(Normalized {
 402                     value: normalized_ty,
 403                     obligations: obligations,
 404                 })
 405             } else {
 406                 Some(Normalized {
 407                     value: projected_ty,
 408                     obligations: obligations,
 409                 })
 410             }
 411         }
 412         Ok(ProjectedTy::NoProgress(projected_ty)) => {
 413             debug!("normalize_projection_type: projected_ty={:?} no progress",
 414                    projected_ty);
 415             Some(Normalized {
 416                 value: projected_ty,
 417                 obligations: vec!()
 418             })
 419         }
 420         Err(ProjectionTyError::TooManyCandidates) => {
 421             debug!("normalize_projection_type: too many candidates");
 422             None
 423         }
 424         Err(ProjectionTyError::TraitSelectionError(_)) => {
 425             debug!("normalize_projection_type: ERROR");
 426             // if we got an error processing the `T as Trait` part,
 427             // just return `ty::err` but add the obligation `T :
 428             // Trait`, which when processed will cause the error to be
 429             // reported later
 430
 431             Some(normalize_to_error(selcx, projection_ty, cause, depth))
 432         }
 433     }
 434 }
 435
 436 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
 437 /// hold. In various error cases, we cannot generate a valid
 438 /// normalized projection. Therefore, we create an inference variable
 439 /// return an associated obligation that, when fulfilled, will lead to
 440 /// an error.
 441 ///
 442 /// Note that we used to return `TyError` here, but that was quite
 443 /// dubious -- the premise was that an error would *eventually* be
 444 /// reported, when the obligation was processed. But in general once
 445 /// you see a `TyError` you are supposed to be able to assume that an
 446 /// error *has been* reported, so that you can take whatever heuristic
 447 /// paths you want to take. To make things worse, it was possible for
 448 /// cycles to arise, where you basically had a setup like `<MyType<$0>
 449 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
 450 /// Trait>::Foo> to `[type error]` would lead to an obligation of
 451 /// `<MyType<[type error]> as Trait>::Foo`.  We are supposed to report
 452 /// an error for this obligation, but we legitimately should not,
 453 /// because it contains `[type error]`. Yuck! (See issue #29857 for
 454 /// one case where this arose.)
 455 fn normalize_to_error<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
 456                                projection_ty: ty::ProjectionTy<'tcx>,
 457                                cause: ObligationCause<'tcx>,
 458                                depth: usize)
 459                                -> NormalizedTy<'tcx>
 460 {
 461     let trait_ref = projection_ty.trait_ref.to_poly_trait_ref();
 462     let trait_obligation = Obligation { cause: cause,
 463                                         recursion_depth: depth,
 464                                         predicate: trait_ref.to_predicate() };
 465     let new_value = selcx.infcx().next_ty_var();
 466     Normalized {
 467         value: new_value,
 468         obligations: vec!(trait_obligation)
 469     }
 470 }
 471
 472 enum ProjectedTy<'tcx> {
 473     Progress(Ty<'tcx>, Vec<PredicateObligation<'tcx>>),
 474     NoProgress(Ty<'tcx>),
 475 }
 476
 477 /// Compute the result of a projection type (if we can).
 478 fn project_type<'cx,'tcx>(
 479     selcx: &mut SelectionContext<'cx,'tcx>,
 480     obligation: &ProjectionTyObligation<'tcx>)
 481     -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>>
 482 {
 483     debug!("project(obligation={:?})",
 484            obligation);
 485
 486     let recursion_limit = selcx.tcx().sess.recursion_limit.get();
 487     if obligation.recursion_depth >= recursion_limit {
 488         debug!("project: overflow!");
 489         report_overflow_error(selcx.infcx(), &obligation, true);
 490     }
 491
 492     let obligation_trait_ref =
 493         selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate.trait_ref);
 494
 495     debug!("project: obligation_trait_ref={:?}", obligation_trait_ref);
 496
 497     if obligation_trait_ref.references_error() {
 498         return Ok(ProjectedTy::Progress(selcx.tcx().types.err, vec!()));
 499     }
 500
 501     let mut candidates = ProjectionTyCandidateSet {
 502         vec: Vec::new(),
 503         ambiguous: false,
 504     };
 505
 506     assemble_candidates_from_param_env(selcx,
 507                                        obligation,
 508                                        &obligation_trait_ref,
 509                                        &mut candidates);
 510
 511     assemble_candidates_from_trait_def(selcx,
 512                                        obligation,
 513                                        &obligation_trait_ref,
 514                                        &mut candidates);
 515
 516     if let Err(e) = assemble_candidates_from_impls(selcx,
 517                                                    obligation,
 518                                                    &obligation_trait_ref,
 519                                                    &mut candidates) {
 520         return Err(ProjectionTyError::TraitSelectionError(e));
 521     }
 522
 523     debug!("{} candidates, ambiguous={}",
 524            candidates.vec.len(),
 525            candidates.ambiguous);
 526
 527     // Inherent ambiguity that prevents us from even enumerating the
 528     // candidates.
 529     if candidates.ambiguous {
 530         return Err(ProjectionTyError::TooManyCandidates);
 531     }
 532
 533     // Drop duplicates.
 534     //
 535     // Note: `candidates.vec` seems to be on the critical path of the
 536     // compiler. Replacing it with an hash set was also tried, which would
 537     // render the following dedup unnecessary. It led to cleaner code but
 538     // prolonged compiling time of `librustc` from 5m30s to 6m in one test, or
 539     // ~9% performance lost.
 540     if candidates.vec.len() > 1 {
 541         let mut i = 0;
 542         while i < candidates.vec.len() {
 543             let has_dup = (0..i).any(|j| candidates.vec[i] == candidates.vec[j]);
 544             if has_dup {
 545                 candidates.vec.swap_remove(i);
 546             } else {
 547                 i += 1;
 548             }
 549         }
 550     }
 551
 552     // Prefer where-clauses. As in select, if there are multiple
 553     // candidates, we prefer where-clause candidates over impls.  This
 554     // may seem a bit surprising, since impls are the source of
 555     // "truth" in some sense, but in fact some of the impls that SEEM
 556     // applicable are not, because of nested obligations. Where
 557     // clauses are the safer choice. See the comment on
 558     // `select::SelectionCandidate` and #21974 for more details.
 559     if candidates.vec.len() > 1 {
 560         debug!("retaining param-env candidates only from {:?}", candidates.vec);
 561         candidates.vec.retain(|c| match *c {
 562             ProjectionTyCandidate::ParamEnv(..) => true,
 563             ProjectionTyCandidate::Impl(..) |
 564             ProjectionTyCandidate::Closure(..) |
 565             ProjectionTyCandidate::TraitDef(..) |
 566             ProjectionTyCandidate::FnPointer(..) => false,
 567         });
 568         debug!("resulting candidate set: {:?}", candidates.vec);
 569         if candidates.vec.len() != 1 {
 570             return Err(ProjectionTyError::TooManyCandidates);
 571         }
 572     }
 573
 574     assert!(candidates.vec.len() <= 1);
 575
 576     let possible_candidate = candidates.vec.pop().and_then(|candidate| {
 577         // In Any (i.e. trans) mode, all projections succeed;
 578         // otherwise, we need to be sensitive to `default` and
 579         // specialization.
 580         if !selcx.projection_mode().any() {
 581             if let ProjectionTyCandidate::Impl(ref impl_data) = candidate {
 582                 if let Some(node_item) = assoc_ty_def(selcx,
 583                                                       impl_data.impl_def_id,
 584                                                       obligation.predicate.item_name) {
 585                     if node_item.node.is_from_trait() {
 586                         if node_item.item.ty.is_some() {
 587                             // If the associated type has a default from the
 588                             // trait, that should be considered `default` and
 589                             // hence not projected.
 590                             //
 591                             // Note, however, that we allow a projection from
 592                             // the trait specifically in the case that the trait
 593                             // does *not* give a default. This is purely to
 594                             // avoid spurious errors: the situation can only
 595                             // arise when *no* impl in the specialization chain
 596                             // has provided a definition for the type. When we
 597                             // confirm the candidate, we'll turn the projection
 598                             // into a TyError, since the actual error will be
 599                             // reported in `check_impl_items_against_trait`.
 600                             return None;
 601                         }
 602                     } else if node_item.item.defaultness.is_default() {
 603                         return None;
 604                     }
 605                 } else {
 606                     // Normally this situation could only arise througha
 607                     // compiler bug, but at coherence-checking time we only look
 608                     // at the topmost impl (we don't even consider the trait
 609                     // itself) for the definition -- so we can fail to find a
 610                     // definition of the type even if it exists.
 611                     return None;
 612                 }
 613             }
 614         }
 615         Some(candidate)
 616     });
 617
 618     match possible_candidate {
 619         Some(candidate) => {
 620             let (ty, obligations) = confirm_candidate(selcx, obligation, candidate);
 621             Ok(ProjectedTy::Progress(ty, obligations))
 622         }
 623         None => {
 624             Ok(ProjectedTy::NoProgress(selcx.tcx().mk_projection(
 625                 obligation.predicate.trait_ref.clone(),
 626                 obligation.predicate.item_name)))
 627         }
 628     }
 629 }
 630
 631 /// The first thing we have to do is scan through the parameter
 632 /// environment to see whether there are any projection predicates
 633 /// there that can answer this question.
 634 fn assemble_candidates_from_param_env<'cx,'tcx>(
 635     selcx: &mut SelectionContext<'cx,'tcx>,
 636     obligation: &ProjectionTyObligation<'tcx>,
 637     obligation_trait_ref: &ty::TraitRef<'tcx>,
 638     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 639 {
 640     debug!("assemble_candidates_from_param_env(..)");
 641     let env_predicates = selcx.param_env().caller_bounds.iter().cloned();
 642     assemble_candidates_from_predicates(selcx,
 643                                         obligation,
 644                                         obligation_trait_ref,
 645                                         candidate_set,
 646                                         ProjectionTyCandidate::ParamEnv,
 647                                         env_predicates);
 648 }
 649
 650 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
 651 /// that the definition of `Foo` has some clues:
 652 ///
 653 /// ```
 654 /// trait Foo {
 655 ///     type FooT : Bar<BarT=i32>
 656 /// }
 657 /// ```
 658 ///
 659 /// Here, for example, we could conclude that the result is `i32`.
 660 fn assemble_candidates_from_trait_def<'cx,'tcx>(
 661     selcx: &mut SelectionContext<'cx,'tcx>,
 662     obligation: &ProjectionTyObligation<'tcx>,
 663     obligation_trait_ref: &ty::TraitRef<'tcx>,
 664     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 665 {
 666     debug!("assemble_candidates_from_trait_def(..)");
 667
 668     // Check whether the self-type is itself a projection.
 669     let trait_ref = match obligation_trait_ref.self_ty().sty {
 670         ty::TyProjection(ref data) => data.trait_ref.clone(),
 671         ty::TyInfer(ty::TyVar(_)) => {
 672             // If the self-type is an inference variable, then it MAY wind up
 673             // being a projected type, so induce an ambiguity.
 674             candidate_set.ambiguous = true;
 675             return;
 676         }
 677         _ => { return; }
 678     };
 679
 680     // If so, extract what we know from the trait and try to come up with a good answer.
 681     let trait_predicates = selcx.tcx().lookup_predicates(trait_ref.def_id);
 682     let bounds = trait_predicates.instantiate(selcx.tcx(), trait_ref.substs);
 683     let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates.into_vec());
 684     assemble_candidates_from_predicates(selcx,
 685                                         obligation,
 686                                         obligation_trait_ref,
 687                                         candidate_set,
 688                                         ProjectionTyCandidate::TraitDef,
 689                                         bounds)
 690 }
 691
 692 fn assemble_candidates_from_predicates<'cx,'tcx,I>(
 693     selcx: &mut SelectionContext<'cx,'tcx>,
 694     obligation: &ProjectionTyObligation<'tcx>,
 695     obligation_trait_ref: &ty::TraitRef<'tcx>,
 696     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 697     ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
 698     env_predicates: I)
 699     where I: Iterator<Item=ty::Predicate<'tcx>>
 700 {
 701     debug!("assemble_candidates_from_predicates(obligation={:?})",
 702            obligation);
 703     let infcx = selcx.infcx();
 704     for predicate in env_predicates {
 705         debug!("assemble_candidates_from_predicates: predicate={:?}",
 706                predicate);
 707         match predicate {
 708             ty::Predicate::Projection(ref data) => {
 709                 let same_name = data.item_name() == obligation.predicate.item_name;
 710
 711                 let is_match = same_name && infcx.probe(|_| {
 712                     let origin = TypeOrigin::Misc(obligation.cause.span);
 713                     let data_poly_trait_ref =
 714                         data.to_poly_trait_ref();
 715                     let obligation_poly_trait_ref =
 716                         obligation_trait_ref.to_poly_trait_ref();
 717                     infcx.sub_poly_trait_refs(false,
 718                                               origin,
 719                                               data_poly_trait_ref,
 720                                               obligation_poly_trait_ref).is_ok()
 721                 });
 722
 723                 debug!("assemble_candidates_from_predicates: candidate={:?} \
 724                                                              is_match={} same_name={}",
 725                        data, is_match, same_name);
 726
 727                 if is_match {
 728                     candidate_set.vec.push(ctor(data.clone()));
 729                 }
 730             }
 731             _ => { }
 732         }
 733     }
 734 }
 735
 736 fn assemble_candidates_from_object_type<'cx,'tcx>(
 737     selcx: &mut SelectionContext<'cx,'tcx>,
 738     obligation:  &ProjectionTyObligation<'tcx>,
 739     obligation_trait_ref: &ty::TraitRef<'tcx>,
 740     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 741 {
 742     let self_ty = obligation_trait_ref.self_ty();
 743     let object_ty = selcx.infcx().shallow_resolve(self_ty);
 744     debug!("assemble_candidates_from_object_type(object_ty={:?})",
 745            object_ty);
 746     let data = match object_ty.sty {
 747         ty::TyTrait(ref data) => data,
 748         _ => {
 749             selcx.tcx().sess.span_bug(
 750                 obligation.cause.span,
 751                 &format!("assemble_candidates_from_object_type called with non-object: {:?}",
 752                          object_ty));
 753         }
 754     };
 755     let projection_bounds = data.projection_bounds_with_self_ty(selcx.tcx(), object_ty);
 756     let env_predicates = projection_bounds.iter()
 757                                           .map(|p| p.to_predicate())
 758                                           .collect();
 759     let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
 760     assemble_candidates_from_predicates(selcx,
 761                                         obligation,
 762                                         obligation_trait_ref,
 763                                         candidate_set,
 764                                         ProjectionTyCandidate::ParamEnv,
 765                                         env_predicates)
 766 }
 767
 768 fn assemble_candidates_from_impls<'cx,'tcx>(
 769     selcx: &mut SelectionContext<'cx,'tcx>,
 770     obligation: &ProjectionTyObligation<'tcx>,
 771     obligation_trait_ref: &ty::TraitRef<'tcx>,
 772     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 773     -> Result<(), SelectionError<'tcx>>
 774 {
 775     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
 776     // start out by selecting the predicate `T as TraitRef<...>`:
 777     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
 778     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
 779     let vtable = match selcx.select(&trait_obligation) {
 780         Ok(Some(vtable)) => vtable,
 781         Ok(None) => {
 782             candidate_set.ambiguous = true;
 783             return Ok(());
 784         }
 785         Err(e) => {
 786             debug!("assemble_candidates_from_impls: selection error {:?}",
 787                    e);
 788             return Err(e);
 789         }
 790     };
 791
 792     match vtable {
 793         super::VtableImpl(data) => {
 794             debug!("assemble_candidates_from_impls: impl candidate {:?}",
 795                    data);
 796
 797             candidate_set.vec.push(
 798                 ProjectionTyCandidate::Impl(data));
 799         }
 800         super::VtableObject(_) => {
 801             assemble_candidates_from_object_type(
 802                 selcx, obligation, obligation_trait_ref, candidate_set);
 803         }
 804         super::VtableClosure(data) => {
 805             candidate_set.vec.push(
 806                 ProjectionTyCandidate::Closure(data));
 807         }
 808         super::VtableFnPointer(fn_type) => {
 809             candidate_set.vec.push(
 810                 ProjectionTyCandidate::FnPointer(fn_type));
 811         }
 812         super::VtableParam(..) => {
 813             // This case tell us nothing about the value of an
 814             // associated type. Consider:
 815             //
 816             // ```
 817             // trait SomeTrait { type Foo; }
 818             // fn foo<T:SomeTrait>(...) { }
 819             // ```
 820             //
 821             // If the user writes `<T as SomeTrait>::Foo`, then the `T
 822             // : SomeTrait` binding does not help us decide what the
 823             // type `Foo` is (at least, not more specifically than
 824             // what we already knew).
 825             //
 826             // But wait, you say! What about an example like this:
 827             //
 828             // ```
 829             // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
 830             // ```
 831             //
 832             // Doesn't the `T : Sometrait<Foo=usize>` predicate help
 833             // resolve `T::Foo`? And of course it does, but in fact
 834             // that single predicate is desugared into two predicates
 835             // in the compiler: a trait predicate (`T : SomeTrait`) and a
 836             // projection. And the projection where clause is handled
 837             // in `assemble_candidates_from_param_env`.
 838         }
 839         super::VtableDefaultImpl(..) |
 840         super::VtableBuiltin(..) => {
 841             // These traits have no associated types.
 842             selcx.tcx().sess.span_bug(
 843                 obligation.cause.span,
 844                 &format!("Cannot project an associated type from `{:?}`",
 845                          vtable));
 846         }
 847     }
 848
 849     Ok(())
 850 }
 851
 852 fn confirm_candidate<'cx,'tcx>(
 853     selcx: &mut SelectionContext<'cx,'tcx>,
 854     obligation: &ProjectionTyObligation<'tcx>,
 855     candidate: ProjectionTyCandidate<'tcx>)
 856     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 857 {
 858     debug!("confirm_candidate(candidate={:?}, obligation={:?})",
 859            candidate,
 860            obligation);
 861
 862     match candidate {
 863         ProjectionTyCandidate::ParamEnv(poly_projection) |
 864         ProjectionTyCandidate::TraitDef(poly_projection) => {
 865             confirm_param_env_candidate(selcx, obligation, poly_projection)
 866         }
 867
 868         ProjectionTyCandidate::Impl(impl_vtable) => {
 869             confirm_impl_candidate(selcx, obligation, impl_vtable)
 870         }
 871
 872         ProjectionTyCandidate::Closure(closure_vtable) => {
 873             confirm_closure_candidate(selcx, obligation, closure_vtable)
 874         }
 875
 876         ProjectionTyCandidate::FnPointer(fn_type) => {
 877             confirm_fn_pointer_candidate(selcx, obligation, fn_type)
 878         }
 879     }
 880 }
 881
 882 fn confirm_fn_pointer_candidate<'cx,'tcx>(
 883     selcx: &mut SelectionContext<'cx,'tcx>,
 884     obligation: &ProjectionTyObligation<'tcx>,
 885     fn_type: Ty<'tcx>)
 886     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 887 {
 888     let fn_type = selcx.infcx().shallow_resolve(fn_type);
 889     let sig = fn_type.fn_sig();
 890     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
 891 }
 892
 893 fn confirm_closure_candidate<'cx,'tcx>(
 894     selcx: &mut SelectionContext<'cx,'tcx>,
 895     obligation: &ProjectionTyObligation<'tcx>,
 896     vtable: VtableClosureData<'tcx, PredicateObligation<'tcx>>)
 897     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 898 {
 899     let closure_typer = selcx.closure_typer();
 900     let closure_type = closure_typer.closure_type(vtable.closure_def_id, &vtable.substs);
 901     let Normalized {
 902         value: closure_type,
 903         mut obligations
 904     } = normalize_with_depth(selcx,
 905                              obligation.cause.clone(),
 906                              obligation.recursion_depth+1,
 907                              &closure_type);
 908     let (ty, mut cc_obligations) = confirm_callable_candidate(selcx,
 909                                                               obligation,
 910                                                               &closure_type.sig,
 911                                                               util::TupleArgumentsFlag::No);
 912     obligations.append(&mut cc_obligations);
 913     (ty, obligations)
 914 }
 915
 916 fn confirm_callable_candidate<'cx,'tcx>(
 917     selcx: &mut SelectionContext<'cx,'tcx>,
 918     obligation: &ProjectionTyObligation<'tcx>,
 919     fn_sig: &ty::PolyFnSig<'tcx>,
 920     flag: util::TupleArgumentsFlag)
 921     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 922 {
 923     let tcx = selcx.tcx();
 924
 925     debug!("confirm_callable_candidate({:?},{:?})",
 926            obligation,
 927            fn_sig);
 928
 929     // the `Output` associated type is declared on `FnOnce`
 930     let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap();
 931
 932     // Note: we unwrap the binder here but re-create it below (1)
 933     let ty::Binder((trait_ref, ret_type)) =
 934         util::closure_trait_ref_and_return_type(tcx,
 935                                                 fn_once_def_id,
 936                                                 obligation.predicate.trait_ref.self_ty(),
 937                                                 fn_sig,
 938                                                 flag);
 939
 940     let predicate = ty::Binder(ty::ProjectionPredicate { // (1) recreate binder here
 941         projection_ty: ty::ProjectionTy {
 942             trait_ref: trait_ref,
 943             item_name: token::intern(FN_OUTPUT_NAME),
 944         },
 945         ty: ret_type
 946     });
 947
 948     confirm_param_env_candidate(selcx, obligation, predicate)
 949 }
 950
 951 fn confirm_param_env_candidate<'cx,'tcx>(
 952     selcx: &mut SelectionContext<'cx,'tcx>,
 953     obligation: &ProjectionTyObligation<'tcx>,
 954     poly_projection: ty::PolyProjectionPredicate<'tcx>)
 955     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 956 {
 957     let infcx = selcx.infcx();
 958
 959     let projection =
 960         infcx.replace_late_bound_regions_with_fresh_var(
 961             obligation.cause.span,
 962             infer::LateBoundRegionConversionTime::HigherRankedType,
 963             &poly_projection).0;
 964
 965     assert_eq!(projection.projection_ty.item_name,
 966                obligation.predicate.item_name);
 967
 968     let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
 969     match infcx.eq_trait_refs(false,
 970                               origin,
 971                               obligation.predicate.trait_ref.clone(),
 972                               projection.projection_ty.trait_ref.clone()) {
 973         Ok(()) => { }
 974         Err(e) => {
 975             selcx.tcx().sess.span_bug(
 976                 obligation.cause.span,
 977                 &format!("Failed to unify `{:?}` and `{:?}` in projection: {}",
 978                          obligation,
 979                          projection,
 980                          e));
 981         }
 982     }
 983
 984     (projection.ty, vec!())
 985 }
 986
 987 fn confirm_impl_candidate<'cx,'tcx>(
 988     selcx: &mut SelectionContext<'cx,'tcx>,
 989     obligation: &ProjectionTyObligation<'tcx>,
 990     impl_vtable: VtableImplData<'tcx, PredicateObligation<'tcx>>)
 991     -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
 992 {
 993     let VtableImplData { substs, nested, impl_def_id } = impl_vtable;
 994
 995     let tcx = selcx.tcx();
 996     let trait_ref = obligation.predicate.trait_ref;
 997     let assoc_ty = assoc_ty_def(selcx, impl_def_id, obligation.predicate.item_name);
 998
 999     match assoc_ty {
1000         Some(node_item) => {
1001             let ty = node_item.item.ty.unwrap_or_else(|| {
1002                 // This means that the impl is missing a definition for the
1003                 // associated type. This error will be reported by the type
1004                 // checker method `check_impl_items_against_trait`, so here we
1005                 // just return TyError.
1006                 debug!("confirm_impl_candidate: no associated type {:?} for {:?}",
1007                        node_item.item.name,
1008                        obligation.predicate.trait_ref);
1009                 tcx.types.err
1010             });
1011             let substs = translate_substs(tcx, impl_def_id, substs, node_item.node);
1012             (ty.subst(tcx, &substs), nested)
1013         }
1014         None => {
1015             tcx.sess.span_bug(obligation.cause.span,
1016                               &format!("No associated type for {:?}", trait_ref));
1017         }
1018     }
1019 }
1020
1021 /// Locate the definition of an associated type in the specialization hierarchy,
1022 /// starting from the given impl.
1023 ///
1024 /// Based on the "projection mode", this lookup may in fact only examine the
1025 /// topmost impl. See the comments for `ProjectionMode` for more details.
1026 fn assoc_ty_def<'cx, 'tcx>(selcx: &SelectionContext<'cx, 'tcx>, impl_def_id: DefId, assoc_ty_name: ast::Name)
1027                            -> Option<specialization_graph::NodeItem<Rc<ty::AssociatedType<'tcx>>>>
1028 {
1029     let trait_def_id = selcx.tcx().impl_trait_ref(impl_def_id).unwrap().def_id;
1030
1031     if selcx.projection_mode().topmost() {
1032         let impl_node = specialization_graph::Node::Impl(impl_def_id);
1033         for item in impl_node.items(selcx.tcx()) {
1034             if let ty::TypeTraitItem(assoc_ty) = item {
1035                 if assoc_ty.name == assoc_ty_name {
1036                     return Some(specialization_graph::NodeItem {
1037                         node: specialization_graph::Node::Impl(impl_def_id),
1038                         item: assoc_ty,
1039                     });
1040                 }
1041             }
1042         }
1043         None
1044     } else {
1045         selcx.tcx().lookup_trait_def(trait_def_id)
1046             .ancestors(impl_def_id)
1047             .type_defs(selcx.tcx(), assoc_ty_name)
1048             .next()
1049     }
1050 }