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