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