src/librustc_trait_selection/traits/project.rs

   1 //! Code for projecting associated types out of trait references.
   2
   3 use super::elaborate_predicates;
   4 use super::specialization_graph;
   5 use super::translate_substs;
   6 use super::util;
   7 use super::MismatchedProjectionTypes;
   8 use super::Obligation;
   9 use super::ObligationCause;
  10 use super::PredicateObligation;
  11 use super::Selection;
  12 use super::SelectionContext;
  13 use super::SelectionError;
  14 use super::{
  15     ImplSourceClosureData, ImplSourceDiscriminantKindData, ImplSourceFnPointerData,
  16     ImplSourceGeneratorData, ImplSourceUserDefinedData,
  17 };
  18 use super::{Normalized, NormalizedTy, ProjectionCacheEntry, ProjectionCacheKey};
  19
  20 use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  21 use crate::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
  22 use crate::traits::error_reporting::InferCtxtExt;
  23 use rustc_data_structures::stack::ensure_sufficient_stack;
  24 use rustc_errors::ErrorReported;
  25 use rustc_hir::def_id::DefId;
  26 use rustc_hir::lang_items::{
  27     DiscriminantTypeLangItem, FnOnceOutputLangItem, FnOnceTraitLangItem, GeneratorTraitLangItem,
  28 };
  29 use rustc_infer::infer::resolve::OpportunisticRegionResolver;
  30 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
  31 use rustc_middle::ty::subst::Subst;
  32 use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, WithConstness};
  33 use rustc_span::symbol::sym;
  34 use rustc_span::DUMMY_SP;
  35
  36 pub use rustc_middle::traits::Reveal;
  37
  38 pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  39
  40 pub type ProjectionObligation<'tcx> = Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  41
  42 pub type ProjectionTyObligation<'tcx> = Obligation<'tcx, ty::ProjectionTy<'tcx>>;
  43
  44 pub(super) struct InProgress;
  45
  46 /// When attempting to resolve `<T as TraitRef>::Name` ...
  47 #[derive(Debug)]
  48 pub enum ProjectionTyError<'tcx> {
  49     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  50     TooManyCandidates,
  51
  52     /// ...an error occurred matching `T : TraitRef`
  53     TraitSelectionError(SelectionError<'tcx>),
  54 }
  55
  56 #[derive(PartialEq, Eq, Debug)]
  57 enum ProjectionTyCandidate<'tcx> {
  58     // from a where-clause in the env or object type
  59     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
  60
  61     // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
  62     TraitDef(ty::PolyProjectionPredicate<'tcx>),
  63
  64     // from a "impl" (or a "pseudo-impl" returned by select)
  65     Select(Selection<'tcx>),
  66 }
  67
  68 enum ProjectionTyCandidateSet<'tcx> {
  69     None,
  70     Single(ProjectionTyCandidate<'tcx>),
  71     Ambiguous,
  72     Error(SelectionError<'tcx>),
  73 }
  74
  75 impl<'tcx> ProjectionTyCandidateSet<'tcx> {
  76     fn mark_ambiguous(&mut self) {
  77         *self = ProjectionTyCandidateSet::Ambiguous;
  78     }
  79
  80     fn mark_error(&mut self, err: SelectionError<'tcx>) {
  81         *self = ProjectionTyCandidateSet::Error(err);
  82     }
  83
  84     // Returns true if the push was successful, or false if the candidate
  85     // was discarded -- this could be because of ambiguity, or because
  86     // a higher-priority candidate is already there.
  87     fn push_candidate(&mut self, candidate: ProjectionTyCandidate<'tcx>) -> bool {
  88         use self::ProjectionTyCandidate::*;
  89         use self::ProjectionTyCandidateSet::*;
  90
  91         // This wacky variable is just used to try and
  92         // make code readable and avoid confusing paths.
  93         // It is assigned a "value" of `()` only on those
  94         // paths in which we wish to convert `*self` to
  95         // ambiguous (and return false, because the candidate
  96         // was not used). On other paths, it is not assigned,
  97         // and hence if those paths *could* reach the code that
  98         // comes after the match, this fn would not compile.
  99         let convert_to_ambiguous;
 100
 101         match self {
 102             None => {
 103                 *self = Single(candidate);
 104                 return true;
 105             }
 106
 107             Single(current) => {
 108                 // Duplicates can happen inside ParamEnv. In the case, we
 109                 // perform a lazy deduplication.
 110                 if current == &candidate {
 111                     return false;
 112                 }
 113
 114                 // Prefer where-clauses. As in select, if there are multiple
 115                 // candidates, we prefer where-clause candidates over impls.  This
 116                 // may seem a bit surprising, since impls are the source of
 117                 // "truth" in some sense, but in fact some of the impls that SEEM
 118                 // applicable are not, because of nested obligations. Where
 119                 // clauses are the safer choice. See the comment on
 120                 // `select::SelectionCandidate` and #21974 for more details.
 121                 match (current, candidate) {
 122                     (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous = (),
 123                     (ParamEnv(..), _) => return false,
 124                     (_, ParamEnv(..)) => unreachable!(),
 125                     (_, _) => convert_to_ambiguous = (),
 126                 }
 127             }
 128
 129             Ambiguous | Error(..) => {
 130                 return false;
 131             }
 132         }
 133
 134         // We only ever get here when we moved from a single candidate
 135         // to ambiguous.
 136         let () = convert_to_ambiguous;
 137         *self = Ambiguous;
 138         false
 139     }
 140 }
 141
 142 /// Evaluates constraints of the form:
 143 ///
 144 ///     for<...> <T as Trait>::U == V
 145 ///
 146 /// If successful, this may result in additional obligations. Also returns
 147 /// the projection cache key used to track these additional obligations.
 148 ///
 149 /// ## Returns
 150 ///
 151 /// - `Err(_)`: the projection can be normalized, but is not equal to the
 152 ///   expected type.
 153 /// - `Ok(Err(InProgress))`: this is called recursively while normalizing
 154 ///   the same projection.
 155 /// - `Ok(Ok(None))`: The projection cannot be normalized due to ambiguity
 156 ///   (resolving some inference variables in the projection may fix this).
 157 /// - `Ok(Ok(Some(obligations)))`: The projection bound holds subject to
 158 ///    the given obligations. If the projection cannot be normalized because
 159 ///    the required trait bound doesn't hold this returned with `obligations`
 160 ///    being a predicate that cannot be proven.
 161 pub(super) fn poly_project_and_unify_type<'cx, 'tcx>(
 162     selcx: &mut SelectionContext<'cx, 'tcx>,
 163     obligation: &PolyProjectionObligation<'tcx>,
 164 ) -> Result<
 165     Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
 166     MismatchedProjectionTypes<'tcx>,
 167 > {
 168     debug!("poly_project_and_unify_type(obligation={:?})", obligation);
 169
 170     let infcx = selcx.infcx();
 171     infcx.commit_if_ok(|_snapshot| {
 172         let (placeholder_predicate, _) =
 173             infcx.replace_bound_vars_with_placeholders(&obligation.predicate);
 174
 175         let placeholder_obligation = obligation.with(placeholder_predicate);
 176         let result = project_and_unify_type(selcx, &placeholder_obligation)?;
 177         Ok(result)
 178     })
 179 }
 180
 181 /// Evaluates constraints of the form:
 182 ///
 183 ///     <T as Trait>::U == V
 184 ///
 185 /// If successful, this may result in additional obligations.
 186 ///
 187 /// See [poly_project_and_unify_type] for an explanation of the return value.
 188 fn project_and_unify_type<'cx, 'tcx>(
 189     selcx: &mut SelectionContext<'cx, 'tcx>,
 190     obligation: &ProjectionObligation<'tcx>,
 191 ) -> Result<
 192     Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
 193     MismatchedProjectionTypes<'tcx>,
 194 > {
 195     debug!("project_and_unify_type(obligation={:?})", obligation);
 196
 197     let mut obligations = vec![];
 198     let normalized_ty = match opt_normalize_projection_type(
 199         selcx,
 200         obligation.param_env,
 201         obligation.predicate.projection_ty,
 202         obligation.cause.clone(),
 203         obligation.recursion_depth,
 204         &mut obligations,
 205     ) {
 206         Ok(Some(n)) => n,
 207         Ok(None) => return Ok(Ok(None)),
 208         Err(InProgress) => return Ok(Err(InProgress)),
 209     };
 210
 211     debug!(
 212         "project_and_unify_type: normalized_ty={:?} obligations={:?}",
 213         normalized_ty, obligations
 214     );
 215
 216     let infcx = selcx.infcx();
 217     match infcx
 218         .at(&obligation.cause, obligation.param_env)
 219         .eq(normalized_ty, obligation.predicate.ty)
 220     {
 221         Ok(InferOk { obligations: inferred_obligations, value: () }) => {
 222             obligations.extend(inferred_obligations);
 223             Ok(Ok(Some(obligations)))
 224         }
 225         Err(err) => {
 226             debug!("project_and_unify_type: equating types encountered error {:?}", err);
 227             Err(MismatchedProjectionTypes { err })
 228         }
 229     }
 230 }
 231
 232 /// Normalizes any associated type projections in `value`, replacing
 233 /// them with a fully resolved type where possible. The return value
 234 /// combines the normalized result and any additional obligations that
 235 /// were incurred as result.
 236 pub fn normalize<'a, 'b, 'tcx, T>(
 237     selcx: &'a mut SelectionContext<'b, 'tcx>,
 238     param_env: ty::ParamEnv<'tcx>,
 239     cause: ObligationCause<'tcx>,
 240     value: &T,
 241 ) -> Normalized<'tcx, T>
 242 where
 243     T: TypeFoldable<'tcx>,
 244 {
 245     let mut obligations = Vec::new();
 246     let value = normalize_to(selcx, param_env, cause, value, &mut obligations);
 247     Normalized { value, obligations }
 248 }
 249
 250 pub fn normalize_to<'a, 'b, 'tcx, T>(
 251     selcx: &'a mut SelectionContext<'b, 'tcx>,
 252     param_env: ty::ParamEnv<'tcx>,
 253     cause: ObligationCause<'tcx>,
 254     value: &T,
 255     obligations: &mut Vec<PredicateObligation<'tcx>>,
 256 ) -> T
 257 where
 258     T: TypeFoldable<'tcx>,
 259 {
 260     normalize_with_depth_to(selcx, param_env, cause, 0, value, obligations)
 261 }
 262
 263 /// As `normalize`, but with a custom depth.
 264 pub fn normalize_with_depth<'a, 'b, 'tcx, T>(
 265     selcx: &'a mut SelectionContext<'b, 'tcx>,
 266     param_env: ty::ParamEnv<'tcx>,
 267     cause: ObligationCause<'tcx>,
 268     depth: usize,
 269     value: &T,
 270 ) -> Normalized<'tcx, T>
 271 where
 272     T: TypeFoldable<'tcx>,
 273 {
 274     let mut obligations = Vec::new();
 275     let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations);
 276     Normalized { value, obligations }
 277 }
 278
 279 pub fn normalize_with_depth_to<'a, 'b, 'tcx, T>(
 280     selcx: &'a mut SelectionContext<'b, 'tcx>,
 281     param_env: ty::ParamEnv<'tcx>,
 282     cause: ObligationCause<'tcx>,
 283     depth: usize,
 284     value: &T,
 285     obligations: &mut Vec<PredicateObligation<'tcx>>,
 286 ) -> T
 287 where
 288     T: TypeFoldable<'tcx>,
 289 {
 290     debug!("normalize_with_depth(depth={}, value={:?})", depth, value);
 291     let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations);
 292     let result = ensure_sufficient_stack(|| normalizer.fold(value));
 293     debug!(
 294         "normalize_with_depth: depth={} result={:?} with {} obligations",
 295         depth,
 296         result,
 297         normalizer.obligations.len()
 298     );
 299     debug!("normalize_with_depth: depth={} obligations={:?}", depth, normalizer.obligations);
 300     result
 301 }
 302
 303 struct AssocTypeNormalizer<'a, 'b, 'tcx> {
 304     selcx: &'a mut SelectionContext<'b, 'tcx>,
 305     param_env: ty::ParamEnv<'tcx>,
 306     cause: ObligationCause<'tcx>,
 307     obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 308     depth: usize,
 309 }
 310
 311 impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> {
 312     fn new(
 313         selcx: &'a mut SelectionContext<'b, 'tcx>,
 314         param_env: ty::ParamEnv<'tcx>,
 315         cause: ObligationCause<'tcx>,
 316         depth: usize,
 317         obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 318     ) -> AssocTypeNormalizer<'a, 'b, 'tcx> {
 319         AssocTypeNormalizer { selcx, param_env, cause, obligations, depth }
 320     }
 321
 322     fn fold<T: TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
 323         let value = self.selcx.infcx().resolve_vars_if_possible(value);
 324
 325         if !value.has_projections() { value } else { value.fold_with(self) }
 326     }
 327 }
 328
 329 impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> {
 330     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
 331         self.selcx.tcx()
 332     }
 333
 334     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 335         if !ty.has_projections() {
 336             return ty;
 337         }
 338         // We don't want to normalize associated types that occur inside of region
 339         // binders, because they may contain bound regions, and we can't cope with that.
 340         //
 341         // Example:
 342         //
 343         //     for<'a> fn(<T as Foo<&'a>>::A)
 344         //
 345         // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll
 346         // normalize it when we instantiate those bound regions (which
 347         // should occur eventually).
 348
 349         let ty = ty.super_fold_with(self);
 350         match ty.kind {
 351             ty::Opaque(def_id, substs) => {
 352                 // Only normalize `impl Trait` after type-checking, usually in codegen.
 353                 match self.param_env.reveal() {
 354                     Reveal::UserFacing => ty,
 355
 356                     Reveal::All => {
 357                         let recursion_limit = self.tcx().sess.recursion_limit();
 358                         if !recursion_limit.value_within_limit(self.depth) {
 359                             let obligation = Obligation::with_depth(
 360                                 self.cause.clone(),
 361                                 recursion_limit.0,
 362                                 self.param_env,
 363                                 ty,
 364                             );
 365                             self.selcx.infcx().report_overflow_error(&obligation, true);
 366                         }
 367
 368                         let generic_ty = self.tcx().type_of(def_id);
 369                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 370                         self.depth += 1;
 371                         let folded_ty = self.fold_ty(concrete_ty);
 372                         self.depth -= 1;
 373                         folded_ty
 374                     }
 375                 }
 376             }
 377
 378             ty::Projection(ref data) if !data.has_escaping_bound_vars() => {
 379                 // This is kind of hacky -- we need to be able to
 380                 // handle normalization within binders because
 381                 // otherwise we wind up a need to normalize when doing
 382                 // trait matching (since you can have a trait
 383                 // obligation like `for<'a> T::B: Fn(&'a i32)`), but
 384                 // we can't normalize with bound regions in scope. So
 385                 // far now we just ignore binders but only normalize
 386                 // if all bound regions are gone (and then we still
 387                 // have to renormalize whenever we instantiate a
 388                 // binder). It would be better to normalize in a
 389                 // binding-aware fashion.
 390
 391                 let normalized_ty = normalize_projection_type(
 392                     self.selcx,
 393                     self.param_env,
 394                     *data,
 395                     self.cause.clone(),
 396                     self.depth,
 397                     &mut self.obligations,
 398                 );
 399                 debug!(
 400                     "AssocTypeNormalizer: depth={} normalized {:?} to {:?}, \
 401                      now with {} obligations",
 402                     self.depth,
 403                     ty,
 404                     normalized_ty,
 405                     self.obligations.len()
 406                 );
 407                 normalized_ty
 408             }
 409
 410             _ => ty,
 411         }
 412     }
 413
 414     fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 415         if self.selcx.tcx().lazy_normalization() {
 416             constant
 417         } else {
 418             let constant = constant.super_fold_with(self);
 419             constant.eval(self.selcx.tcx(), self.param_env)
 420         }
 421     }
 422 }
 423
 424 /// The guts of `normalize`: normalize a specific projection like `<T
 425 /// as Trait>::Item`. The result is always a type (and possibly
 426 /// additional obligations). If ambiguity arises, which implies that
 427 /// there are unresolved type variables in the projection, we will
 428 /// substitute a fresh type variable `$X` and generate a new
 429 /// obligation `<T as Trait>::Item == $X` for later.
 430 pub fn normalize_projection_type<'a, 'b, 'tcx>(
 431     selcx: &'a mut SelectionContext<'b, 'tcx>,
 432     param_env: ty::ParamEnv<'tcx>,
 433     projection_ty: ty::ProjectionTy<'tcx>,
 434     cause: ObligationCause<'tcx>,
 435     depth: usize,
 436     obligations: &mut Vec<PredicateObligation<'tcx>>,
 437 ) -> Ty<'tcx> {
 438     opt_normalize_projection_type(
 439         selcx,
 440         param_env,
 441         projection_ty,
 442         cause.clone(),
 443         depth,
 444         obligations,
 445     )
 446     .ok()
 447     .flatten()
 448     .unwrap_or_else(move || {
 449         // if we bottom out in ambiguity, create a type variable
 450         // and a deferred predicate to resolve this when more type
 451         // information is available.
 452
 453         let tcx = selcx.infcx().tcx;
 454         let def_id = projection_ty.item_def_id;
 455         let ty_var = selcx.infcx().next_ty_var(TypeVariableOrigin {
 456             kind: TypeVariableOriginKind::NormalizeProjectionType,
 457             span: tcx.def_span(def_id),
 458         });
 459         let projection = ty::Binder::dummy(ty::ProjectionPredicate { projection_ty, ty: ty_var });
 460         let obligation =
 461             Obligation::with_depth(cause, depth + 1, param_env, projection.to_predicate(tcx));
 462         obligations.push(obligation);
 463         ty_var
 464     })
 465 }
 466
 467 /// The guts of `normalize`: normalize a specific projection like `<T
 468 /// as Trait>::Item`. The result is always a type (and possibly
 469 /// additional obligations). Returns `None` in the case of ambiguity,
 470 /// which indicates that there are unbound type variables.
 471 ///
 472 /// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a
 473 /// `Ty<'tcx>` and an obligations vector. But that obligation vector was very
 474 /// often immediately appended to another obligations vector. So now this
 475 /// function takes an obligations vector and appends to it directly, which is
 476 /// slightly uglier but avoids the need for an extra short-lived allocation.
 477 fn opt_normalize_projection_type<'a, 'b, 'tcx>(
 478     selcx: &'a mut SelectionContext<'b, 'tcx>,
 479     param_env: ty::ParamEnv<'tcx>,
 480     projection_ty: ty::ProjectionTy<'tcx>,
 481     cause: ObligationCause<'tcx>,
 482     depth: usize,
 483     obligations: &mut Vec<PredicateObligation<'tcx>>,
 484 ) -> Result<Option<Ty<'tcx>>, InProgress> {
 485     let infcx = selcx.infcx();
 486
 487     let projection_ty = infcx.resolve_vars_if_possible(&projection_ty);
 488     let cache_key = ProjectionCacheKey::new(projection_ty);
 489
 490     debug!(
 491         "opt_normalize_projection_type(\
 492          projection_ty={:?}, \
 493          depth={})",
 494         projection_ty, depth
 495     );
 496
 497     // FIXME(#20304) For now, I am caching here, which is good, but it
 498     // means we don't capture the type variables that are created in
 499     // the case of ambiguity. Which means we may create a large stream
 500     // of such variables. OTOH, if we move the caching up a level, we
 501     // would not benefit from caching when proving `T: Trait<U=Foo>`
 502     // bounds. It might be the case that we want two distinct caches,
 503     // or else another kind of cache entry.
 504
 505     let cache_result = infcx.inner.borrow_mut().projection_cache().try_start(cache_key);
 506     match cache_result {
 507         Ok(()) => {}
 508         Err(ProjectionCacheEntry::Ambiguous) => {
 509             // If we found ambiguity the last time, that means we will continue
 510             // to do so until some type in the key changes (and we know it
 511             // hasn't, because we just fully resolved it).
 512             debug!(
 513                 "opt_normalize_projection_type: \
 514                  found cache entry: ambiguous"
 515             );
 516             return Ok(None);
 517         }
 518         Err(ProjectionCacheEntry::InProgress) => {
 519             // If while normalized A::B, we are asked to normalize
 520             // A::B, just return A::B itself. This is a conservative
 521             // answer, in the sense that A::B *is* clearly equivalent
 522             // to A::B, though there may be a better value we can
 523             // find.
 524
 525             // Under lazy normalization, this can arise when
 526             // bootstrapping.  That is, imagine an environment with a
 527             // where-clause like `A::B == u32`. Now, if we are asked
 528             // to normalize `A::B`, we will want to check the
 529             // where-clauses in scope. So we will try to unify `A::B`
 530             // with `A::B`, which can trigger a recursive
 531             // normalization.
 532
 533             debug!(
 534                 "opt_normalize_projection_type: \
 535                  found cache entry: in-progress"
 536             );
 537
 538             return Err(InProgress);
 539         }
 540         Err(ProjectionCacheEntry::NormalizedTy(ty)) => {
 541             // This is the hottest path in this function.
 542             //
 543             // If we find the value in the cache, then return it along
 544             // with the obligations that went along with it. Note
 545             // that, when using a fulfillment context, these
 546             // obligations could in principle be ignored: they have
 547             // already been registered when the cache entry was
 548             // created (and hence the new ones will quickly be
 549             // discarded as duplicated). But when doing trait
 550             // evaluation this is not the case, and dropping the trait
 551             // evaluations can causes ICEs (e.g., #43132).
 552             debug!(
 553                 "opt_normalize_projection_type: \
 554                  found normalized ty `{:?}`",
 555                 ty
 556             );
 557
 558             // Once we have inferred everything we need to know, we
 559             // can ignore the `obligations` from that point on.
 560             if infcx.unresolved_type_vars(&ty.value).is_none() {
 561                 infcx.inner.borrow_mut().projection_cache().complete_normalized(cache_key, &ty);
 562             // No need to extend `obligations`.
 563             } else {
 564                 obligations.extend(ty.obligations);
 565             }
 566
 567             obligations.push(get_paranoid_cache_value_obligation(
 568                 infcx,
 569                 param_env,
 570                 projection_ty,
 571                 cause,
 572                 depth,
 573             ));
 574             return Ok(Some(ty.value));
 575         }
 576         Err(ProjectionCacheEntry::Error) => {
 577             debug!(
 578                 "opt_normalize_projection_type: \
 579                  found error"
 580             );
 581             let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
 582             obligations.extend(result.obligations);
 583             return Ok(Some(result.value));
 584         }
 585     }
 586
 587     let obligation = Obligation::with_depth(cause.clone(), depth, param_env, projection_ty);
 588     match project_type(selcx, &obligation) {
 589         Ok(ProjectedTy::Progress(Progress {
 590             ty: projected_ty,
 591             obligations: mut projected_obligations,
 592         })) => {
 593             // if projection succeeded, then what we get out of this
 594             // is also non-normalized (consider: it was derived from
 595             // an impl, where-clause etc) and hence we must
 596             // re-normalize it
 597
 598             debug!(
 599                 "opt_normalize_projection_type: \
 600                  projected_ty={:?} \
 601                  depth={} \
 602                  projected_obligations={:?}",
 603                 projected_ty, depth, projected_obligations
 604             );
 605
 606             let result = if projected_ty.has_projections() {
 607                 let mut normalizer = AssocTypeNormalizer::new(
 608                     selcx,
 609                     param_env,
 610                     cause,
 611                     depth + 1,
 612                     &mut projected_obligations,
 613                 );
 614                 let normalized_ty = normalizer.fold(&projected_ty);
 615
 616                 debug!(
 617                     "opt_normalize_projection_type: \
 618                      normalized_ty={:?} depth={}",
 619                     normalized_ty, depth
 620                 );
 621
 622                 Normalized { value: normalized_ty, obligations: projected_obligations }
 623             } else {
 624                 Normalized { value: projected_ty, obligations: projected_obligations }
 625             };
 626
 627             let cache_value = prune_cache_value_obligations(infcx, &result);
 628             infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, cache_value);
 629             obligations.extend(result.obligations);
 630             Ok(Some(result.value))
 631         }
 632         Ok(ProjectedTy::NoProgress(projected_ty)) => {
 633             debug!(
 634                 "opt_normalize_projection_type: \
 635                  projected_ty={:?} no progress",
 636                 projected_ty
 637             );
 638             let result = Normalized { value: projected_ty, obligations: vec![] };
 639             infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, result.clone());
 640             // No need to extend `obligations`.
 641             Ok(Some(result.value))
 642         }
 643         Err(ProjectionTyError::TooManyCandidates) => {
 644             debug!(
 645                 "opt_normalize_projection_type: \
 646                  too many candidates"
 647             );
 648             infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key);
 649             Ok(None)
 650         }
 651         Err(ProjectionTyError::TraitSelectionError(_)) => {
 652             debug!("opt_normalize_projection_type: ERROR");
 653             // if we got an error processing the `T as Trait` part,
 654             // just return `ty::err` but add the obligation `T :
 655             // Trait`, which when processed will cause the error to be
 656             // reported later
 657
 658             infcx.inner.borrow_mut().projection_cache().error(cache_key);
 659             let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
 660             obligations.extend(result.obligations);
 661             Ok(Some(result.value))
 662         }
 663     }
 664 }
 665
 666 /// If there are unresolved type variables, then we need to include
 667 /// any subobligations that bind them, at least until those type
 668 /// variables are fully resolved.
 669 fn prune_cache_value_obligations<'a, 'tcx>(
 670     infcx: &'a InferCtxt<'a, 'tcx>,
 671     result: &NormalizedTy<'tcx>,
 672 ) -> NormalizedTy<'tcx> {
 673     if infcx.unresolved_type_vars(&result.value).is_none() {
 674         return NormalizedTy { value: result.value, obligations: vec![] };
 675     }
 676
 677     let mut obligations: Vec<_> = result
 678         .obligations
 679         .iter()
 680         .filter(|obligation| {
 681             match obligation.predicate.skip_binders() {
 682                 // We found a `T: Foo<X = U>` predicate, let's check
 683                 // if `U` references any unresolved type
 684                 // variables. In principle, we only care if this
 685                 // projection can help resolve any of the type
 686                 // variables found in `result.value` -- but we just
 687                 // check for any type variables here, for fear of
 688                 // indirect obligations (e.g., we project to `?0`,
 689                 // but we have `T: Foo<X = ?1>` and `?1: Bar<X =
 690                 // ?0>`).
 691                 ty::PredicateAtom::Projection(data) => {
 692                     infcx.unresolved_type_vars(&ty::Binder::bind(data.ty)).is_some()
 693                 }
 694
 695                 // We are only interested in `T: Foo<X = U>` predicates, whre
 696                 // `U` references one of `unresolved_type_vars`. =)
 697                 _ => false,
 698             }
 699         })
 700         .cloned()
 701         .collect();
 702
 703     obligations.shrink_to_fit();
 704
 705     NormalizedTy { value: result.value, obligations }
 706 }
 707
 708 /// Whenever we give back a cache result for a projection like `<T as
 709 /// Trait>::Item ==> X`, we *always* include the obligation to prove
 710 /// that `T: Trait` (we may also include some other obligations). This
 711 /// may or may not be necessary -- in principle, all the obligations
 712 /// that must be proven to show that `T: Trait` were also returned
 713 /// when the cache was first populated. But there are some vague concerns,
 714 /// and so we take the precautionary measure of including `T: Trait` in
 715 /// the result:
 716 ///
 717 /// Concern #1. The current setup is fragile. Perhaps someone could
 718 /// have failed to prove the concerns from when the cache was
 719 /// populated, but also not have used a snapshot, in which case the
 720 /// cache could remain populated even though `T: Trait` has not been
 721 /// shown. In this case, the "other code" is at fault -- when you
 722 /// project something, you are supposed to either have a snapshot or
 723 /// else prove all the resulting obligations -- but it's still easy to
 724 /// get wrong.
 725 ///
 726 /// Concern #2. Even within the snapshot, if those original
 727 /// obligations are not yet proven, then we are able to do projections
 728 /// that may yet turn out to be wrong. This *may* lead to some sort
 729 /// of trouble, though we don't have a concrete example of how that
 730 /// can occur yet. But it seems risky at best.
 731 fn get_paranoid_cache_value_obligation<'a, 'tcx>(
 732     infcx: &'a InferCtxt<'a, 'tcx>,
 733     param_env: ty::ParamEnv<'tcx>,
 734     projection_ty: ty::ProjectionTy<'tcx>,
 735     cause: ObligationCause<'tcx>,
 736     depth: usize,
 737 ) -> PredicateObligation<'tcx> {
 738     let trait_ref = projection_ty.trait_ref(infcx.tcx).to_poly_trait_ref();
 739     Obligation {
 740         cause,
 741         recursion_depth: depth,
 742         param_env,
 743         predicate: trait_ref.without_const().to_predicate(infcx.tcx),
 744     }
 745 }
 746
 747 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
 748 /// hold. In various error cases, we cannot generate a valid
 749 /// normalized projection. Therefore, we create an inference variable
 750 /// return an associated obligation that, when fulfilled, will lead to
 751 /// an error.
 752 ///
 753 /// Note that we used to return `Error` here, but that was quite
 754 /// dubious -- the premise was that an error would *eventually* be
 755 /// reported, when the obligation was processed. But in general once
 756 /// you see a `Error` you are supposed to be able to assume that an
 757 /// error *has been* reported, so that you can take whatever heuristic
 758 /// paths you want to take. To make things worse, it was possible for
 759 /// cycles to arise, where you basically had a setup like `<MyType<$0>
 760 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
 761 /// Trait>::Foo> to `[type error]` would lead to an obligation of
 762 /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
 763 /// an error for this obligation, but we legitimately should not,
 764 /// because it contains `[type error]`. Yuck! (See issue #29857 for
 765 /// one case where this arose.)
 766 fn normalize_to_error<'a, 'tcx>(
 767     selcx: &mut SelectionContext<'a, 'tcx>,
 768     param_env: ty::ParamEnv<'tcx>,
 769     projection_ty: ty::ProjectionTy<'tcx>,
 770     cause: ObligationCause<'tcx>,
 771     depth: usize,
 772 ) -> NormalizedTy<'tcx> {
 773     let trait_ref = projection_ty.trait_ref(selcx.tcx()).to_poly_trait_ref();
 774     let trait_obligation = Obligation {
 775         cause,
 776         recursion_depth: depth,
 777         param_env,
 778         predicate: trait_ref.without_const().to_predicate(selcx.tcx()),
 779     };
 780     let tcx = selcx.infcx().tcx;
 781     let def_id = projection_ty.item_def_id;
 782     let new_value = selcx.infcx().next_ty_var(TypeVariableOrigin {
 783         kind: TypeVariableOriginKind::NormalizeProjectionType,
 784         span: tcx.def_span(def_id),
 785     });
 786     Normalized { value: new_value, obligations: vec![trait_obligation] }
 787 }
 788
 789 enum ProjectedTy<'tcx> {
 790     Progress(Progress<'tcx>),
 791     NoProgress(Ty<'tcx>),
 792 }
 793
 794 struct Progress<'tcx> {
 795     ty: Ty<'tcx>,
 796     obligations: Vec<PredicateObligation<'tcx>>,
 797 }
 798
 799 impl<'tcx> Progress<'tcx> {
 800     fn error(tcx: TyCtxt<'tcx>) -> Self {
 801         Progress { ty: tcx.ty_error(), obligations: vec![] }
 802     }
 803
 804     fn with_addl_obligations(mut self, mut obligations: Vec<PredicateObligation<'tcx>>) -> Self {
 805         debug!(
 806             "with_addl_obligations: self.obligations.len={} obligations.len={}",
 807             self.obligations.len(),
 808             obligations.len()
 809         );
 810
 811         debug!(
 812             "with_addl_obligations: self.obligations={:?} obligations={:?}",
 813             self.obligations, obligations
 814         );
 815
 816         self.obligations.append(&mut obligations);
 817         self
 818     }
 819 }
 820
 821 /// Computes the result of a projection type (if we can).
 822 ///
 823 /// IMPORTANT:
 824 /// - `obligation` must be fully normalized
 825 fn project_type<'cx, 'tcx>(
 826     selcx: &mut SelectionContext<'cx, 'tcx>,
 827     obligation: &ProjectionTyObligation<'tcx>,
 828 ) -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>> {
 829     debug!("project(obligation={:?})", obligation);
 830
 831     if !selcx.tcx().sess.recursion_limit().value_within_limit(obligation.recursion_depth) {
 832         debug!("project: overflow!");
 833         return Err(ProjectionTyError::TraitSelectionError(SelectionError::Overflow));
 834     }
 835
 836     let obligation_trait_ref = &obligation.predicate.trait_ref(selcx.tcx());
 837
 838     debug!("project: obligation_trait_ref={:?}", obligation_trait_ref);
 839
 840     if obligation_trait_ref.references_error() {
 841         return Ok(ProjectedTy::Progress(Progress::error(selcx.tcx())));
 842     }
 843
 844     let mut candidates = ProjectionTyCandidateSet::None;
 845
 846     // Make sure that the following procedures are kept in order. ParamEnv
 847     // needs to be first because it has highest priority, and Select checks
 848     // the return value of push_candidate which assumes it's ran at last.
 849     assemble_candidates_from_param_env(selcx, obligation, &obligation_trait_ref, &mut candidates);
 850
 851     assemble_candidates_from_trait_def(selcx, obligation, &obligation_trait_ref, &mut candidates);
 852
 853     assemble_candidates_from_impls(selcx, obligation, &obligation_trait_ref, &mut candidates);
 854
 855     match candidates {
 856         ProjectionTyCandidateSet::Single(candidate) => Ok(ProjectedTy::Progress(
 857             confirm_candidate(selcx, obligation, &obligation_trait_ref, candidate),
 858         )),
 859         ProjectionTyCandidateSet::None => Ok(ProjectedTy::NoProgress(
 860             selcx
 861                 .tcx()
 862                 .mk_projection(obligation.predicate.item_def_id, obligation.predicate.substs),
 863         )),
 864         // Error occurred while trying to processing impls.
 865         ProjectionTyCandidateSet::Error(e) => Err(ProjectionTyError::TraitSelectionError(e)),
 866         // Inherent ambiguity that prevents us from even enumerating the
 867         // candidates.
 868         ProjectionTyCandidateSet::Ambiguous => Err(ProjectionTyError::TooManyCandidates),
 869     }
 870 }
 871
 872 /// The first thing we have to do is scan through the parameter
 873 /// environment to see whether there are any projection predicates
 874 /// there that can answer this question.
 875 fn assemble_candidates_from_param_env<'cx, 'tcx>(
 876     selcx: &mut SelectionContext<'cx, 'tcx>,
 877     obligation: &ProjectionTyObligation<'tcx>,
 878     obligation_trait_ref: &ty::TraitRef<'tcx>,
 879     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 880 ) {
 881     debug!("assemble_candidates_from_param_env(..)");
 882     assemble_candidates_from_predicates(
 883         selcx,
 884         obligation,
 885         obligation_trait_ref,
 886         candidate_set,
 887         ProjectionTyCandidate::ParamEnv,
 888         obligation.param_env.caller_bounds().iter(),
 889     );
 890 }
 891
 892 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
 893 /// that the definition of `Foo` has some clues:
 894 ///
 895 /// ```
 896 /// trait Foo {
 897 ///     type FooT : Bar<BarT=i32>
 898 /// }
 899 /// ```
 900 ///
 901 /// Here, for example, we could conclude that the result is `i32`.
 902 fn assemble_candidates_from_trait_def<'cx, 'tcx>(
 903     selcx: &mut SelectionContext<'cx, 'tcx>,
 904     obligation: &ProjectionTyObligation<'tcx>,
 905     obligation_trait_ref: &ty::TraitRef<'tcx>,
 906     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 907 ) {
 908     debug!("assemble_candidates_from_trait_def(..)");
 909
 910     let tcx = selcx.tcx();
 911     // Check whether the self-type is itself a projection.
 912     // If so, extract what we know from the trait and try to come up with a good answer.
 913     let bounds = match obligation_trait_ref.self_ty().kind {
 914         ty::Projection(ref data) => {
 915             tcx.projection_predicates(data.item_def_id).subst(tcx, data.substs)
 916         }
 917         ty::Opaque(def_id, substs) => tcx.projection_predicates(def_id).subst(tcx, substs),
 918         ty::Infer(ty::TyVar(_)) => {
 919             // If the self-type is an inference variable, then it MAY wind up
 920             // being a projected type, so induce an ambiguity.
 921             candidate_set.mark_ambiguous();
 922             return;
 923         }
 924         _ => return,
 925     };
 926
 927     assemble_candidates_from_predicates(
 928         selcx,
 929         obligation,
 930         obligation_trait_ref,
 931         candidate_set,
 932         ProjectionTyCandidate::TraitDef,
 933         bounds.iter(),
 934     )
 935 }
 936
 937 fn assemble_candidates_from_predicates<'cx, 'tcx>(
 938     selcx: &mut SelectionContext<'cx, 'tcx>,
 939     obligation: &ProjectionTyObligation<'tcx>,
 940     obligation_trait_ref: &ty::TraitRef<'tcx>,
 941     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 942     ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
 943     env_predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
 944 ) {
 945     debug!("assemble_candidates_from_predicates(obligation={:?})", obligation);
 946     let infcx = selcx.infcx();
 947     for predicate in env_predicates {
 948         debug!("assemble_candidates_from_predicates: predicate={:?}", predicate);
 949         if let ty::PredicateAtom::Projection(data) = predicate.skip_binders() {
 950             let data = ty::Binder::bind(data);
 951             let same_def_id = data.projection_def_id() == obligation.predicate.item_def_id;
 952
 953             let is_match = same_def_id
 954                 && infcx.probe(|_| {
 955                     let data_poly_trait_ref = data.to_poly_trait_ref(infcx.tcx);
 956                     let obligation_poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
 957                     infcx
 958                         .at(&obligation.cause, obligation.param_env)
 959                         .sup(obligation_poly_trait_ref, data_poly_trait_ref)
 960                         .map(|InferOk { obligations: _, value: () }| {
 961                             // FIXME(#32730) -- do we need to take obligations
 962                             // into account in any way? At the moment, no.
 963                         })
 964                         .is_ok()
 965                 });
 966
 967             debug!(
 968                 "assemble_candidates_from_predicates: candidate={:?} \
 969                  is_match={} same_def_id={}",
 970                 data, is_match, same_def_id
 971             );
 972
 973             if is_match {
 974                 candidate_set.push_candidate(ctor(data));
 975             }
 976         }
 977     }
 978 }
 979
 980 fn assemble_candidates_from_impls<'cx, 'tcx>(
 981     selcx: &mut SelectionContext<'cx, 'tcx>,
 982     obligation: &ProjectionTyObligation<'tcx>,
 983     obligation_trait_ref: &ty::TraitRef<'tcx>,
 984     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
 985 ) {
 986     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
 987     // start out by selecting the predicate `T as TraitRef<...>`:
 988     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
 989     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
 990     let _ = selcx.infcx().commit_if_ok(|_| {
 991         let impl_source = match selcx.select(&trait_obligation) {
 992             Ok(Some(impl_source)) => impl_source,
 993             Ok(None) => {
 994                 candidate_set.mark_ambiguous();
 995                 return Err(());
 996             }
 997             Err(e) => {
 998                 debug!("assemble_candidates_from_impls: selection error {:?}", e);
 999                 candidate_set.mark_error(e);
1000                 return Err(());
1001             }
1002         };
1003
1004         let eligible = match &impl_source {
1005             super::ImplSourceClosure(_)
1006             | super::ImplSourceGenerator(_)
1007             | super::ImplSourceFnPointer(_)
1008             | super::ImplSourceObject(_)
1009             | super::ImplSourceTraitAlias(_) => {
1010                 debug!("assemble_candidates_from_impls: impl_source={:?}", impl_source);
1011                 true
1012             }
1013             super::ImplSourceUserDefined(impl_data) => {
1014                 // We have to be careful when projecting out of an
1015                 // impl because of specialization. If we are not in
1016                 // codegen (i.e., projection mode is not "any"), and the
1017                 // impl's type is declared as default, then we disable
1018                 // projection (even if the trait ref is fully
1019                 // monomorphic). In the case where trait ref is not
1020                 // fully monomorphic (i.e., includes type parameters),
1021                 // this is because those type parameters may
1022                 // ultimately be bound to types from other crates that
1023                 // may have specialized impls we can't see. In the
1024                 // case where the trait ref IS fully monomorphic, this
1025                 // is a policy decision that we made in the RFC in
1026                 // order to preserve flexibility for the crate that
1027                 // defined the specializable impl to specialize later
1028                 // for existing types.
1029                 //
1030                 // In either case, we handle this by not adding a
1031                 // candidate for an impl if it contains a `default`
1032                 // type.
1033                 //
1034                 // NOTE: This should be kept in sync with the similar code in
1035                 // `rustc_ty::instance::resolve_associated_item()`.
1036                 let node_item =
1037                     assoc_ty_def(selcx, impl_data.impl_def_id, obligation.predicate.item_def_id)
1038                         .map_err(|ErrorReported| ())?;
1039
1040                 if node_item.is_final() {
1041                     // Non-specializable items are always projectable.
1042                     true
1043                 } else {
1044                     // Only reveal a specializable default if we're past type-checking
1045                     // and the obligation is monomorphic, otherwise passes such as
1046                     // transmute checking and polymorphic MIR optimizations could
1047                     // get a result which isn't correct for all monomorphizations.
1048                     if obligation.param_env.reveal() == Reveal::All {
1049                         // NOTE(eddyb) inference variables can resolve to parameters, so
1050                         // assume `poly_trait_ref` isn't monomorphic, if it contains any.
1051                         let poly_trait_ref =
1052                             selcx.infcx().resolve_vars_if_possible(&poly_trait_ref);
1053                         !poly_trait_ref.still_further_specializable()
1054                     } else {
1055                         debug!(
1056                             "assemble_candidates_from_impls: not eligible due to default: \
1057                              assoc_ty={} predicate={}",
1058                             selcx.tcx().def_path_str(node_item.item.def_id),
1059                             obligation.predicate,
1060                         );
1061                         false
1062                     }
1063                 }
1064             }
1065             super::ImplSourceDiscriminantKind(..) => {
1066                 // While `DiscriminantKind` is automatically implemented for every type,
1067                 // the concrete discriminant may not be known yet.
1068                 //
1069                 // Any type with multiple potential discriminant types is therefore not eligible.
1070                 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1071
1072                 match self_ty.kind {
1073                     ty::Bool
1074                     | ty::Char
1075                     | ty::Int(_)
1076                     | ty::Uint(_)
1077                     | ty::Float(_)
1078                     | ty::Adt(..)
1079                     | ty::Foreign(_)
1080                     | ty::Str
1081                     | ty::Array(..)
1082                     | ty::Slice(_)
1083                     | ty::RawPtr(..)
1084                     | ty::Ref(..)
1085                     | ty::FnDef(..)
1086                     | ty::FnPtr(..)
1087                     | ty::Dynamic(..)
1088                     | ty::Closure(..)
1089                     | ty::Generator(..)
1090                     | ty::GeneratorWitness(..)
1091                     | ty::Never
1092                     | ty::Tuple(..)
1093                     // Integers and floats always have `u8` as their discriminant.
1094                     | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1095
1096                     ty::Projection(..)
1097                     | ty::Opaque(..)
1098                     | ty::Param(..)
1099                     | ty::Bound(..)
1100                     | ty::Placeholder(..)
1101                     | ty::Infer(..)
1102                     | ty::Error(_) => false,
1103                 }
1104             }
1105             super::ImplSourceParam(..) => {
1106                 // This case tell us nothing about the value of an
1107                 // associated type. Consider:
1108                 //
1109                 // ```
1110                 // trait SomeTrait { type Foo; }
1111                 // fn foo<T:SomeTrait>(...) { }
1112                 // ```
1113                 //
1114                 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1115                 // : SomeTrait` binding does not help us decide what the
1116                 // type `Foo` is (at least, not more specifically than
1117                 // what we already knew).
1118                 //
1119                 // But wait, you say! What about an example like this:
1120                 //
1121                 // ```
1122                 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1123                 // ```
1124                 //
1125                 // Doesn't the `T : Sometrait<Foo=usize>` predicate help
1126                 // resolve `T::Foo`? And of course it does, but in fact
1127                 // that single predicate is desugared into two predicates
1128                 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1129                 // projection. And the projection where clause is handled
1130                 // in `assemble_candidates_from_param_env`.
1131                 false
1132             }
1133             super::ImplSourceAutoImpl(..) | super::ImplSourceBuiltin(..) => {
1134                 // These traits have no associated types.
1135                 selcx.tcx().sess.delay_span_bug(
1136                     obligation.cause.span,
1137                     &format!("Cannot project an associated type from `{:?}`", impl_source),
1138                 );
1139                 return Err(());
1140             }
1141         };
1142
1143         if eligible {
1144             if candidate_set.push_candidate(ProjectionTyCandidate::Select(impl_source)) {
1145                 Ok(())
1146             } else {
1147                 Err(())
1148             }
1149         } else {
1150             Err(())
1151         }
1152     });
1153 }
1154
1155 fn confirm_candidate<'cx, 'tcx>(
1156     selcx: &mut SelectionContext<'cx, 'tcx>,
1157     obligation: &ProjectionTyObligation<'tcx>,
1158     obligation_trait_ref: &ty::TraitRef<'tcx>,
1159     candidate: ProjectionTyCandidate<'tcx>,
1160 ) -> Progress<'tcx> {
1161     debug!("confirm_candidate(candidate={:?}, obligation={:?})", candidate, obligation);
1162
1163     let mut progress = match candidate {
1164         ProjectionTyCandidate::ParamEnv(poly_projection)
1165         | ProjectionTyCandidate::TraitDef(poly_projection) => {
1166             confirm_param_env_candidate(selcx, obligation, poly_projection)
1167         }
1168
1169         ProjectionTyCandidate::Select(impl_source) => {
1170             confirm_select_candidate(selcx, obligation, obligation_trait_ref, impl_source)
1171         }
1172     };
1173     // When checking for cycle during evaluation, we compare predicates with
1174     // "syntactic" equality. Since normalization generally introduces a type
1175     // with new region variables, we need to resolve them to existing variables
1176     // when possible for this to work. See `auto-trait-projection-recursion.rs`
1177     // for a case where this matters.
1178     if progress.ty.has_infer_regions() {
1179         progress.ty = OpportunisticRegionResolver::new(selcx.infcx()).fold_ty(progress.ty);
1180     }
1181     progress
1182 }
1183
1184 fn confirm_select_candidate<'cx, 'tcx>(
1185     selcx: &mut SelectionContext<'cx, 'tcx>,
1186     obligation: &ProjectionTyObligation<'tcx>,
1187     obligation_trait_ref: &ty::TraitRef<'tcx>,
1188     impl_source: Selection<'tcx>,
1189 ) -> Progress<'tcx> {
1190     match impl_source {
1191         super::ImplSourceUserDefined(data) => confirm_impl_candidate(selcx, obligation, data),
1192         super::ImplSourceGenerator(data) => confirm_generator_candidate(selcx, obligation, data),
1193         super::ImplSourceClosure(data) => confirm_closure_candidate(selcx, obligation, data),
1194         super::ImplSourceFnPointer(data) => confirm_fn_pointer_candidate(selcx, obligation, data),
1195         super::ImplSourceDiscriminantKind(data) => {
1196             confirm_discriminant_kind_candidate(selcx, obligation, data)
1197         }
1198         super::ImplSourceObject(_) => {
1199             confirm_object_candidate(selcx, obligation, obligation_trait_ref)
1200         }
1201         super::ImplSourceAutoImpl(..)
1202         | super::ImplSourceParam(..)
1203         | super::ImplSourceBuiltin(..)
1204         | super::ImplSourceTraitAlias(..) =>
1205         // we don't create Select candidates with this kind of resolution
1206         {
1207             span_bug!(
1208                 obligation.cause.span,
1209                 "Cannot project an associated type from `{:?}`",
1210                 impl_source
1211             )
1212         }
1213     }
1214 }
1215
1216 fn confirm_object_candidate<'cx, 'tcx>(
1217     selcx: &mut SelectionContext<'cx, 'tcx>,
1218     obligation: &ProjectionTyObligation<'tcx>,
1219     obligation_trait_ref: &ty::TraitRef<'tcx>,
1220 ) -> Progress<'tcx> {
1221     let self_ty = obligation_trait_ref.self_ty();
1222     let object_ty = selcx.infcx().shallow_resolve(self_ty);
1223     debug!("confirm_object_candidate(object_ty={:?})", object_ty);
1224     let data = match object_ty.kind {
1225         ty::Dynamic(ref data, ..) => data,
1226         _ => span_bug!(
1227             obligation.cause.span,
1228             "confirm_object_candidate called with non-object: {:?}",
1229             object_ty
1230         ),
1231     };
1232     let env_predicates = data
1233         .projection_bounds()
1234         .map(|p| p.with_self_ty(selcx.tcx(), object_ty).to_predicate(selcx.tcx()));
1235     let env_predicate = {
1236         let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
1237
1238         // select only those projections that are actually projecting an
1239         // item with the correct name
1240
1241         let env_predicates = env_predicates.filter_map(|o| match o.predicate.skip_binders() {
1242             ty::PredicateAtom::Projection(data)
1243                 if data.projection_ty.item_def_id == obligation.predicate.item_def_id =>
1244             {
1245                 Some(ty::Binder::bind(data))
1246             }
1247             _ => None,
1248         });
1249
1250         // select those with a relevant trait-ref
1251         let mut env_predicates = env_predicates.filter(|data| {
1252             let data_poly_trait_ref = data.to_poly_trait_ref(selcx.tcx());
1253             let obligation_poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
1254             selcx.infcx().probe(|_| {
1255                 selcx
1256                     .infcx()
1257                     .at(&obligation.cause, obligation.param_env)
1258                     .sup(obligation_poly_trait_ref, data_poly_trait_ref)
1259                     .is_ok()
1260             })
1261         });
1262
1263         // select the first matching one; there really ought to be one or
1264         // else the object type is not WF, since an object type should
1265         // include all of its projections explicitly
1266         match env_predicates.next() {
1267             Some(env_predicate) => env_predicate,
1268             None => {
1269                 debug!(
1270                     "confirm_object_candidate: no env-predicate \
1271                      found in object type `{:?}`; ill-formed",
1272                     object_ty
1273                 );
1274                 return Progress::error(selcx.tcx());
1275             }
1276         }
1277     };
1278
1279     confirm_param_env_candidate(selcx, obligation, env_predicate)
1280 }
1281
1282 fn confirm_generator_candidate<'cx, 'tcx>(
1283     selcx: &mut SelectionContext<'cx, 'tcx>,
1284     obligation: &ProjectionTyObligation<'tcx>,
1285     impl_source: ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>,
1286 ) -> Progress<'tcx> {
1287     let gen_sig = impl_source.substs.as_generator().poly_sig();
1288     let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1289         selcx,
1290         obligation.param_env,
1291         obligation.cause.clone(),
1292         obligation.recursion_depth + 1,
1293         &gen_sig,
1294     );
1295
1296     debug!(
1297         "confirm_generator_candidate: obligation={:?},gen_sig={:?},obligations={:?}",
1298         obligation, gen_sig, obligations
1299     );
1300
1301     let tcx = selcx.tcx();
1302
1303     let gen_def_id = tcx.require_lang_item(GeneratorTraitLangItem, None);
1304
1305     let predicate = super::util::generator_trait_ref_and_outputs(
1306         tcx,
1307         gen_def_id,
1308         obligation.predicate.self_ty(),
1309         gen_sig,
1310     )
1311     .map_bound(|(trait_ref, yield_ty, return_ty)| {
1312         let name = tcx.associated_item(obligation.predicate.item_def_id).ident.name;
1313         let ty = if name == sym::Return {
1314             return_ty
1315         } else if name == sym::Yield {
1316             yield_ty
1317         } else {
1318             bug!()
1319         };
1320
1321         ty::ProjectionPredicate {
1322             projection_ty: ty::ProjectionTy {
1323                 substs: trait_ref.substs,
1324                 item_def_id: obligation.predicate.item_def_id,
1325             },
1326             ty,
1327         }
1328     });
1329
1330     confirm_param_env_candidate(selcx, obligation, predicate)
1331         .with_addl_obligations(impl_source.nested)
1332         .with_addl_obligations(obligations)
1333 }
1334
1335 fn confirm_discriminant_kind_candidate<'cx, 'tcx>(
1336     selcx: &mut SelectionContext<'cx, 'tcx>,
1337     obligation: &ProjectionTyObligation<'tcx>,
1338     _: ImplSourceDiscriminantKindData,
1339 ) -> Progress<'tcx> {
1340     let tcx = selcx.tcx();
1341
1342     let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1343     let substs = tcx.mk_substs([self_ty.into()].iter());
1344
1345     let discriminant_def_id = tcx.require_lang_item(DiscriminantTypeLangItem, None);
1346
1347     let predicate = ty::ProjectionPredicate {
1348         projection_ty: ty::ProjectionTy { substs, item_def_id: discriminant_def_id },
1349         ty: self_ty.discriminant_ty(tcx),
1350     };
1351
1352     confirm_param_env_candidate(selcx, obligation, ty::Binder::bind(predicate))
1353 }
1354
1355 fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1356     selcx: &mut SelectionContext<'cx, 'tcx>,
1357     obligation: &ProjectionTyObligation<'tcx>,
1358     fn_pointer_impl_source: ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>,
1359 ) -> Progress<'tcx> {
1360     let fn_type = selcx.infcx().shallow_resolve(fn_pointer_impl_source.fn_ty);
1361     let sig = fn_type.fn_sig(selcx.tcx());
1362     let Normalized { value: sig, obligations } = normalize_with_depth(
1363         selcx,
1364         obligation.param_env,
1365         obligation.cause.clone(),
1366         obligation.recursion_depth + 1,
1367         &sig,
1368     );
1369
1370     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1371         .with_addl_obligations(fn_pointer_impl_source.nested)
1372         .with_addl_obligations(obligations)
1373 }
1374
1375 fn confirm_closure_candidate<'cx, 'tcx>(
1376     selcx: &mut SelectionContext<'cx, 'tcx>,
1377     obligation: &ProjectionTyObligation<'tcx>,
1378     impl_source: ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>,
1379 ) -> Progress<'tcx> {
1380     let closure_sig = impl_source.substs.as_closure().sig();
1381     let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1382         selcx,
1383         obligation.param_env,
1384         obligation.cause.clone(),
1385         obligation.recursion_depth + 1,
1386         &closure_sig,
1387     );
1388
1389     debug!(
1390         "confirm_closure_candidate: obligation={:?},closure_sig={:?},obligations={:?}",
1391         obligation, closure_sig, obligations
1392     );
1393
1394     confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
1395         .with_addl_obligations(impl_source.nested)
1396         .with_addl_obligations(obligations)
1397 }
1398
1399 fn confirm_callable_candidate<'cx, 'tcx>(
1400     selcx: &mut SelectionContext<'cx, 'tcx>,
1401     obligation: &ProjectionTyObligation<'tcx>,
1402     fn_sig: ty::PolyFnSig<'tcx>,
1403     flag: util::TupleArgumentsFlag,
1404 ) -> Progress<'tcx> {
1405     let tcx = selcx.tcx();
1406
1407     debug!("confirm_callable_candidate({:?},{:?})", obligation, fn_sig);
1408
1409     let fn_once_def_id = tcx.require_lang_item(FnOnceTraitLangItem, None);
1410     let fn_once_output_def_id = tcx.require_lang_item(FnOnceOutputLangItem, None);
1411
1412     let predicate = super::util::closure_trait_ref_and_return_type(
1413         tcx,
1414         fn_once_def_id,
1415         obligation.predicate.self_ty(),
1416         fn_sig,
1417         flag,
1418     )
1419     .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
1420         projection_ty: ty::ProjectionTy {
1421             substs: trait_ref.substs,
1422             item_def_id: fn_once_output_def_id,
1423         },
1424         ty: ret_type,
1425     });
1426
1427     confirm_param_env_candidate(selcx, obligation, predicate)
1428 }
1429
1430 fn confirm_param_env_candidate<'cx, 'tcx>(
1431     selcx: &mut SelectionContext<'cx, 'tcx>,
1432     obligation: &ProjectionTyObligation<'tcx>,
1433     poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
1434 ) -> Progress<'tcx> {
1435     let infcx = selcx.infcx();
1436     let cause = &obligation.cause;
1437     let param_env = obligation.param_env;
1438
1439     let (cache_entry, _) = infcx.replace_bound_vars_with_fresh_vars(
1440         cause.span,
1441         LateBoundRegionConversionTime::HigherRankedType,
1442         &poly_cache_entry,
1443     );
1444
1445     let cache_trait_ref = cache_entry.projection_ty.trait_ref(infcx.tcx);
1446     let obligation_trait_ref = obligation.predicate.trait_ref(infcx.tcx);
1447     match infcx.at(cause, param_env).eq(cache_trait_ref, obligation_trait_ref) {
1448         Ok(InferOk { value: _, obligations }) => Progress { ty: cache_entry.ty, obligations },
1449         Err(e) => {
1450             let msg = format!(
1451                 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
1452                 obligation, poly_cache_entry, e,
1453             );
1454             debug!("confirm_param_env_candidate: {}", msg);
1455             let err = infcx.tcx.ty_error_with_message(obligation.cause.span, &msg);
1456             Progress { ty: err, obligations: vec![] }
1457         }
1458     }
1459 }
1460
1461 fn confirm_impl_candidate<'cx, 'tcx>(
1462     selcx: &mut SelectionContext<'cx, 'tcx>,
1463     obligation: &ProjectionTyObligation<'tcx>,
1464     impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
1465 ) -> Progress<'tcx> {
1466     let tcx = selcx.tcx();
1467
1468     let ImplSourceUserDefinedData { impl_def_id, substs, nested } = impl_impl_source;
1469     let assoc_item_id = obligation.predicate.item_def_id;
1470     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
1471
1472     let param_env = obligation.param_env;
1473     let assoc_ty = match assoc_ty_def(selcx, impl_def_id, assoc_item_id) {
1474         Ok(assoc_ty) => assoc_ty,
1475         Err(ErrorReported) => return Progress { ty: tcx.ty_error(), obligations: nested },
1476     };
1477
1478     if !assoc_ty.item.defaultness.has_value() {
1479         // This means that the impl is missing a definition for the
1480         // associated type. This error will be reported by the type
1481         // checker method `check_impl_items_against_trait`, so here we
1482         // just return Error.
1483         debug!(
1484             "confirm_impl_candidate: no associated type {:?} for {:?}",
1485             assoc_ty.item.ident, obligation.predicate
1486         );
1487         return Progress { ty: tcx.ty_error(), obligations: nested };
1488     }
1489     // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
1490     //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
1491     //
1492     // * `obligation.predicate.substs` is `[Vec<u32>, S]`
1493     // * `substs` is `[u32]`
1494     // * `substs` ends up as `[u32, S]`
1495     let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs);
1496     let substs =
1497         translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.defining_node);
1498     let ty = tcx.type_of(assoc_ty.item.def_id);
1499     if substs.len() != tcx.generics_of(assoc_ty.item.def_id).count() {
1500         let err = tcx.ty_error_with_message(
1501             DUMMY_SP,
1502             "impl item and trait item have different parameter counts",
1503         );
1504         Progress { ty: err, obligations: nested }
1505     } else {
1506         Progress { ty: ty.subst(tcx, substs), obligations: nested }
1507     }
1508 }
1509
1510 /// Locate the definition of an associated type in the specialization hierarchy,
1511 /// starting from the given impl.
1512 ///
1513 /// Based on the "projection mode", this lookup may in fact only examine the
1514 /// topmost impl. See the comments for `Reveal` for more details.
1515 fn assoc_ty_def(
1516     selcx: &SelectionContext<'_, '_>,
1517     impl_def_id: DefId,
1518     assoc_ty_def_id: DefId,
1519 ) -> Result<specialization_graph::LeafDef, ErrorReported> {
1520     let tcx = selcx.tcx();
1521     let assoc_ty_name = tcx.associated_item(assoc_ty_def_id).ident;
1522     let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id;
1523     let trait_def = tcx.trait_def(trait_def_id);
1524
1525     // This function may be called while we are still building the
1526     // specialization graph that is queried below (via TraitDef::ancestors()),
1527     // so, in order to avoid unnecessary infinite recursion, we manually look
1528     // for the associated item at the given impl.
1529     // If there is no such item in that impl, this function will fail with a
1530     // cycle error if the specialization graph is currently being built.
1531     let impl_node = specialization_graph::Node::Impl(impl_def_id);
1532     for item in impl_node.items(tcx) {
1533         if matches!(item.kind, ty::AssocKind::Type)
1534             && tcx.hygienic_eq(item.ident, assoc_ty_name, trait_def_id)
1535         {
1536             return Ok(specialization_graph::LeafDef {
1537                 item: *item,
1538                 defining_node: impl_node,
1539                 finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) },
1540             });
1541         }
1542     }
1543
1544     let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
1545     if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_ty_name, ty::AssocKind::Type) {
1546         Ok(assoc_item)
1547     } else {
1548         // This is saying that neither the trait nor
1549         // the impl contain a definition for this
1550         // associated type.  Normally this situation
1551         // could only arise through a compiler bug --
1552         // if the user wrote a bad item name, it
1553         // should have failed in astconv.
1554         bug!("No associated type `{}` for {}", assoc_ty_name, tcx.def_path_str(impl_def_id))
1555     }
1556 }
1557
1558 crate trait ProjectionCacheKeyExt<'tcx>: Sized {
1559     fn from_poly_projection_predicate(
1560         selcx: &mut SelectionContext<'cx, 'tcx>,
1561         predicate: ty::PolyProjectionPredicate<'tcx>,
1562     ) -> Option<Self>;
1563 }
1564
1565 impl<'tcx> ProjectionCacheKeyExt<'tcx> for ProjectionCacheKey<'tcx> {
1566     fn from_poly_projection_predicate(
1567         selcx: &mut SelectionContext<'cx, 'tcx>,
1568         predicate: ty::PolyProjectionPredicate<'tcx>,
1569     ) -> Option<Self> {
1570         let infcx = selcx.infcx();
1571         // We don't do cross-snapshot caching of obligations with escaping regions,
1572         // so there's no cache key to use
1573         predicate.no_bound_vars().map(|predicate| {
1574             ProjectionCacheKey::new(
1575                 // We don't attempt to match up with a specific type-variable state
1576                 // from a specific call to `opt_normalize_projection_type` - if
1577                 // there's no precise match, the original cache entry is "stranded"
1578                 // anyway.
1579                 infcx.resolve_vars_if_possible(&predicate.projection_ty),
1580             )
1581         })
1582     }
1583 }