compiler/rustc_trait_selection/src/traits/project.rs

   1 //! Code for projecting associated types out of trait references.
   2
   3 use super::specialization_graph;
   4 use super::translate_substs;
   5 use super::util;
   6 use super::MismatchedProjectionTypes;
   7 use super::Obligation;
   8 use super::ObligationCause;
   9 use super::PredicateObligation;
  10 use super::Selection;
  11 use super::SelectionContext;
  12 use super::SelectionError;
  13 use super::{
  14     ImplSourceClosureData, ImplSourceFnPointerData, ImplSourceFutureData, ImplSourceGeneratorData,
  15     ImplSourceUserDefinedData,
  16 };
  17 use super::{Normalized, NormalizedTy, ProjectionCacheEntry, ProjectionCacheKey};
  18
  19 use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  20 use crate::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
  21 use crate::traits::error_reporting::TypeErrCtxtExt as _;
  22 use crate::traits::query::evaluate_obligation::InferCtxtExt as _;
  23 use crate::traits::select::ProjectionMatchesProjection;
  24 use rustc_data_structures::sso::SsoHashSet;
  25 use rustc_data_structures::stack::ensure_sufficient_stack;
  26 use rustc_errors::ErrorGuaranteed;
  27 use rustc_hir::def::DefKind;
  28 use rustc_hir::lang_items::LangItem;
  29 use rustc_infer::infer::at::At;
  30 use rustc_infer::infer::resolve::OpportunisticRegionResolver;
  31 use rustc_infer::traits::ImplSourceBuiltinData;
  32 use rustc_middle::traits::select::OverflowError;
  33 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable};
  34 use rustc_middle::ty::visit::{MaxUniverse, TypeVisitable};
  35 use rustc_middle::ty::DefIdTree;
  36 use rustc_middle::ty::{self, Term, ToPredicate, Ty, TyCtxt};
  37 use rustc_span::symbol::sym;
  38
  39 use std::collections::BTreeMap;
  40
  41 pub use rustc_middle::traits::Reveal;
  42
  43 pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
  44
  45 pub type ProjectionObligation<'tcx> = Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
  46
  47 pub type ProjectionTyObligation<'tcx> = Obligation<'tcx, ty::AliasTy<'tcx>>;
  48
  49 pub(super) struct InProgress;
  50
  51 pub trait NormalizeExt<'tcx> {
  52     /// Normalize a value using the `AssocTypeNormalizer`.
  53     ///
  54     /// This normalization should be used when the type contains inference variables or the
  55     /// projection may be fallible.
  56     fn normalize<T: TypeFoldable<'tcx>>(&self, t: T) -> InferOk<'tcx, T>;
  57 }
  58
  59 impl<'tcx> NormalizeExt<'tcx> for At<'_, 'tcx> {
  60     fn normalize<T: TypeFoldable<'tcx>>(&self, value: T) -> InferOk<'tcx, T> {
  61         let mut selcx = SelectionContext::new(self.infcx);
  62         let Normalized { value, obligations } =
  63             normalize_with_depth(&mut selcx, self.param_env, self.cause.clone(), 0, value);
  64         InferOk { value, obligations }
  65     }
  66 }
  67
  68 /// When attempting to resolve `<T as TraitRef>::Name` ...
  69 #[derive(Debug)]
  70 pub enum ProjectionError<'tcx> {
  71     /// ...we found multiple sources of information and couldn't resolve the ambiguity.
  72     TooManyCandidates,
  73
  74     /// ...an error occurred matching `T : TraitRef`
  75     TraitSelectionError(SelectionError<'tcx>),
  76 }
  77
  78 #[derive(PartialEq, Eq, Debug)]
  79 enum ProjectionCandidate<'tcx> {
  80     /// From a where-clause in the env or object type
  81     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
  82
  83     /// From the definition of `Trait` when you have something like
  84     /// `<<A as Trait>::B as Trait2>::C`.
  85     TraitDef(ty::PolyProjectionPredicate<'tcx>),
  86
  87     /// Bounds specified on an object type
  88     Object(ty::PolyProjectionPredicate<'tcx>),
  89
  90     /// From an "impl" (or a "pseudo-impl" returned by select)
  91     Select(Selection<'tcx>),
  92
  93     ImplTraitInTrait(ImplTraitInTraitCandidate<'tcx>),
  94 }
  95
  96 #[derive(PartialEq, Eq, Debug)]
  97 enum ImplTraitInTraitCandidate<'tcx> {
  98     // The `impl Trait` from a trait function's default body
  99     Trait,
 100     // A concrete type provided from a trait's `impl Trait` from an impl
 101     Impl(ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>),
 102 }
 103
 104 enum ProjectionCandidateSet<'tcx> {
 105     None,
 106     Single(ProjectionCandidate<'tcx>),
 107     Ambiguous,
 108     Error(SelectionError<'tcx>),
 109 }
 110
 111 impl<'tcx> ProjectionCandidateSet<'tcx> {
 112     fn mark_ambiguous(&mut self) {
 113         *self = ProjectionCandidateSet::Ambiguous;
 114     }
 115
 116     fn mark_error(&mut self, err: SelectionError<'tcx>) {
 117         *self = ProjectionCandidateSet::Error(err);
 118     }
 119
 120     // Returns true if the push was successful, or false if the candidate
 121     // was discarded -- this could be because of ambiguity, or because
 122     // a higher-priority candidate is already there.
 123     fn push_candidate(&mut self, candidate: ProjectionCandidate<'tcx>) -> bool {
 124         use self::ProjectionCandidate::*;
 125         use self::ProjectionCandidateSet::*;
 126
 127         // This wacky variable is just used to try and
 128         // make code readable and avoid confusing paths.
 129         // It is assigned a "value" of `()` only on those
 130         // paths in which we wish to convert `*self` to
 131         // ambiguous (and return false, because the candidate
 132         // was not used). On other paths, it is not assigned,
 133         // and hence if those paths *could* reach the code that
 134         // comes after the match, this fn would not compile.
 135         let convert_to_ambiguous;
 136
 137         match self {
 138             None => {
 139                 *self = Single(candidate);
 140                 return true;
 141             }
 142
 143             Single(current) => {
 144                 // Duplicates can happen inside ParamEnv. In the case, we
 145                 // perform a lazy deduplication.
 146                 if current == &candidate {
 147                     return false;
 148                 }
 149
 150                 // Prefer where-clauses. As in select, if there are multiple
 151                 // candidates, we prefer where-clause candidates over impls. This
 152                 // may seem a bit surprising, since impls are the source of
 153                 // "truth" in some sense, but in fact some of the impls that SEEM
 154                 // applicable are not, because of nested obligations. Where
 155                 // clauses are the safer choice. See the comment on
 156                 // `select::SelectionCandidate` and #21974 for more details.
 157                 match (current, candidate) {
 158                     (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous = (),
 159                     (ParamEnv(..), _) => return false,
 160                     (_, ParamEnv(..)) => unreachable!(),
 161                     (_, _) => convert_to_ambiguous = (),
 162                 }
 163             }
 164
 165             Ambiguous | Error(..) => {
 166                 return false;
 167             }
 168         }
 169
 170         // We only ever get here when we moved from a single candidate
 171         // to ambiguous.
 172         let () = convert_to_ambiguous;
 173         *self = Ambiguous;
 174         false
 175     }
 176 }
 177
 178 /// States returned from `poly_project_and_unify_type`. Takes the place
 179 /// of the old return type, which was:
 180 /// ```ignore (not-rust)
 181 /// Result<
 182 ///     Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
 183 ///     MismatchedProjectionTypes<'tcx>,
 184 /// >
 185 /// ```
 186 pub(super) enum ProjectAndUnifyResult<'tcx> {
 187     /// The projection bound holds subject to the given obligations. If the
 188     /// projection cannot be normalized because the required trait bound does
 189     /// not hold, this is returned, with `obligations` being a predicate that
 190     /// cannot be proven.
 191     Holds(Vec<PredicateObligation<'tcx>>),
 192     /// The projection cannot be normalized due to ambiguity. Resolving some
 193     /// inference variables in the projection may fix this.
 194     FailedNormalization,
 195     /// The project cannot be normalized because `poly_project_and_unify_type`
 196     /// is called recursively while normalizing the same projection.
 197     Recursive,
 198     // the projection can be normalized, but is not equal to the expected type.
 199     // Returns the type error that arose from the mismatch.
 200     MismatchedProjectionTypes(MismatchedProjectionTypes<'tcx>),
 201 }
 202
 203 /// Evaluates constraints of the form:
 204 /// ```ignore (not-rust)
 205 /// for<...> <T as Trait>::U == V
 206 /// ```
 207 /// If successful, this may result in additional obligations. Also returns
 208 /// the projection cache key used to track these additional obligations.
 209 #[instrument(level = "debug", skip(selcx))]
 210 pub(super) fn poly_project_and_unify_type<'cx, 'tcx>(
 211     selcx: &mut SelectionContext<'cx, 'tcx>,
 212     obligation: &PolyProjectionObligation<'tcx>,
 213 ) -> ProjectAndUnifyResult<'tcx> {
 214     let infcx = selcx.infcx;
 215     let r = infcx.commit_if_ok(|_snapshot| {
 216         let old_universe = infcx.universe();
 217         let placeholder_predicate =
 218             infcx.replace_bound_vars_with_placeholders(obligation.predicate);
 219         let new_universe = infcx.universe();
 220
 221         let placeholder_obligation = obligation.with(infcx.tcx, placeholder_predicate);
 222         match project_and_unify_type(selcx, &placeholder_obligation) {
 223             ProjectAndUnifyResult::MismatchedProjectionTypes(e) => Err(e),
 224             ProjectAndUnifyResult::Holds(obligations)
 225                 if old_universe != new_universe
 226                     && selcx.tcx().features().generic_associated_types_extended =>
 227             {
 228                 // If the `generic_associated_types_extended` feature is active, then we ignore any
 229                 // obligations references lifetimes from any universe greater than or equal to the
 230                 // universe just created. Otherwise, we can end up with something like `for<'a> I: 'a`,
 231                 // which isn't quite what we want. Ideally, we want either an implied
 232                 // `for<'a where I: 'a> I: 'a` or we want to "lazily" check these hold when we
 233                 // substitute concrete regions. There is design work to be done here; until then,
 234                 // however, this allows experimenting potential GAT features without running into
 235                 // well-formedness issues.
 236                 let new_obligations = obligations
 237                     .into_iter()
 238                     .filter(|obligation| {
 239                         let mut visitor = MaxUniverse::new();
 240                         obligation.predicate.visit_with(&mut visitor);
 241                         visitor.max_universe() < new_universe
 242                     })
 243                     .collect();
 244                 Ok(ProjectAndUnifyResult::Holds(new_obligations))
 245             }
 246             other => Ok(other),
 247         }
 248     });
 249
 250     match r {
 251         Ok(inner) => inner,
 252         Err(err) => ProjectAndUnifyResult::MismatchedProjectionTypes(err),
 253     }
 254 }
 255
 256 /// Evaluates constraints of the form:
 257 /// ```ignore (not-rust)
 258 /// <T as Trait>::U == V
 259 /// ```
 260 /// If successful, this may result in additional obligations.
 261 ///
 262 /// See [poly_project_and_unify_type] for an explanation of the return value.
 263 #[instrument(level = "debug", skip(selcx))]
 264 fn project_and_unify_type<'cx, 'tcx>(
 265     selcx: &mut SelectionContext<'cx, 'tcx>,
 266     obligation: &ProjectionObligation<'tcx>,
 267 ) -> ProjectAndUnifyResult<'tcx> {
 268     let mut obligations = vec![];
 269
 270     let infcx = selcx.infcx;
 271     let normalized = match opt_normalize_projection_type(
 272         selcx,
 273         obligation.param_env,
 274         obligation.predicate.projection_ty,
 275         obligation.cause.clone(),
 276         obligation.recursion_depth,
 277         &mut obligations,
 278     ) {
 279         Ok(Some(n)) => n,
 280         Ok(None) => return ProjectAndUnifyResult::FailedNormalization,
 281         Err(InProgress) => return ProjectAndUnifyResult::Recursive,
 282     };
 283     debug!(?normalized, ?obligations, "project_and_unify_type result");
 284     let actual = obligation.predicate.term;
 285     // For an example where this is necessary see tests/ui/impl-trait/nested-return-type2.rs
 286     // This allows users to omit re-mentioning all bounds on an associated type and just use an
 287     // `impl Trait` for the assoc type to add more bounds.
 288     let InferOk { value: actual, obligations: new } =
 289         selcx.infcx.replace_opaque_types_with_inference_vars(
 290             actual,
 291             obligation.cause.body_id,
 292             obligation.cause.span,
 293             obligation.param_env,
 294         );
 295     obligations.extend(new);
 296
 297     match infcx.at(&obligation.cause, obligation.param_env).eq(normalized, actual) {
 298         Ok(InferOk { obligations: inferred_obligations, value: () }) => {
 299             obligations.extend(inferred_obligations);
 300             ProjectAndUnifyResult::Holds(obligations)
 301         }
 302         Err(err) => {
 303             debug!("equating types encountered error {:?}", err);
 304             ProjectAndUnifyResult::MismatchedProjectionTypes(MismatchedProjectionTypes { err })
 305         }
 306     }
 307 }
 308
 309 /// As `normalize`, but with a custom depth.
 310 pub(crate) fn normalize_with_depth<'a, 'b, 'tcx, T>(
 311     selcx: &'a mut SelectionContext<'b, 'tcx>,
 312     param_env: ty::ParamEnv<'tcx>,
 313     cause: ObligationCause<'tcx>,
 314     depth: usize,
 315     value: T,
 316 ) -> Normalized<'tcx, T>
 317 where
 318     T: TypeFoldable<'tcx>,
 319 {
 320     let mut obligations = Vec::new();
 321     let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations);
 322     Normalized { value, obligations }
 323 }
 324
 325 #[instrument(level = "info", skip(selcx, param_env, cause, obligations))]
 326 pub(crate) fn normalize_with_depth_to<'a, 'b, 'tcx, T>(
 327     selcx: &'a mut SelectionContext<'b, 'tcx>,
 328     param_env: ty::ParamEnv<'tcx>,
 329     cause: ObligationCause<'tcx>,
 330     depth: usize,
 331     value: T,
 332     obligations: &mut Vec<PredicateObligation<'tcx>>,
 333 ) -> T
 334 where
 335     T: TypeFoldable<'tcx>,
 336 {
 337     debug!(obligations.len = obligations.len());
 338     let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations);
 339     let result = ensure_sufficient_stack(|| normalizer.fold(value));
 340     debug!(?result, obligations.len = normalizer.obligations.len());
 341     debug!(?normalizer.obligations,);
 342     result
 343 }
 344
 345 #[instrument(level = "info", skip(selcx, param_env, cause, obligations))]
 346 pub(crate) fn try_normalize_with_depth_to<'a, 'b, 'tcx, T>(
 347     selcx: &'a mut SelectionContext<'b, 'tcx>,
 348     param_env: ty::ParamEnv<'tcx>,
 349     cause: ObligationCause<'tcx>,
 350     depth: usize,
 351     value: T,
 352     obligations: &mut Vec<PredicateObligation<'tcx>>,
 353 ) -> T
 354 where
 355     T: TypeFoldable<'tcx>,
 356 {
 357     debug!(obligations.len = obligations.len());
 358     let mut normalizer = AssocTypeNormalizer::new_without_eager_inference_replacement(
 359         selcx,
 360         param_env,
 361         cause,
 362         depth,
 363         obligations,
 364     );
 365     let result = ensure_sufficient_stack(|| normalizer.fold(value));
 366     debug!(?result, obligations.len = normalizer.obligations.len());
 367     debug!(?normalizer.obligations,);
 368     result
 369 }
 370
 371 pub(crate) fn needs_normalization<'tcx, T: TypeVisitable<'tcx>>(value: &T, reveal: Reveal) -> bool {
 372     match reveal {
 373         Reveal::UserFacing => value
 374             .has_type_flags(ty::TypeFlags::HAS_TY_PROJECTION | ty::TypeFlags::HAS_CT_PROJECTION),
 375         Reveal::All => value.has_type_flags(
 376             ty::TypeFlags::HAS_TY_PROJECTION
 377                 | ty::TypeFlags::HAS_TY_OPAQUE
 378                 | ty::TypeFlags::HAS_CT_PROJECTION,
 379         ),
 380     }
 381 }
 382
 383 struct AssocTypeNormalizer<'a, 'b, 'tcx> {
 384     selcx: &'a mut SelectionContext<'b, 'tcx>,
 385     param_env: ty::ParamEnv<'tcx>,
 386     cause: ObligationCause<'tcx>,
 387     obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 388     depth: usize,
 389     universes: Vec<Option<ty::UniverseIndex>>,
 390     /// If true, when a projection is unable to be completed, an inference
 391     /// variable will be created and an obligation registered to project to that
 392     /// inference variable. Also, constants will be eagerly evaluated.
 393     eager_inference_replacement: bool,
 394 }
 395
 396 impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> {
 397     fn new(
 398         selcx: &'a mut SelectionContext<'b, 'tcx>,
 399         param_env: ty::ParamEnv<'tcx>,
 400         cause: ObligationCause<'tcx>,
 401         depth: usize,
 402         obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 403     ) -> AssocTypeNormalizer<'a, 'b, 'tcx> {
 404         AssocTypeNormalizer {
 405             selcx,
 406             param_env,
 407             cause,
 408             obligations,
 409             depth,
 410             universes: vec![],
 411             eager_inference_replacement: true,
 412         }
 413     }
 414
 415     fn new_without_eager_inference_replacement(
 416         selcx: &'a mut SelectionContext<'b, 'tcx>,
 417         param_env: ty::ParamEnv<'tcx>,
 418         cause: ObligationCause<'tcx>,
 419         depth: usize,
 420         obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 421     ) -> AssocTypeNormalizer<'a, 'b, 'tcx> {
 422         AssocTypeNormalizer {
 423             selcx,
 424             param_env,
 425             cause,
 426             obligations,
 427             depth,
 428             universes: vec![],
 429             eager_inference_replacement: false,
 430         }
 431     }
 432
 433     fn fold<T: TypeFoldable<'tcx>>(&mut self, value: T) -> T {
 434         let value = self.selcx.infcx.resolve_vars_if_possible(value);
 435         debug!(?value);
 436
 437         assert!(
 438             !value.has_escaping_bound_vars(),
 439             "Normalizing {:?} without wrapping in a `Binder`",
 440             value
 441         );
 442
 443         if !needs_normalization(&value, self.param_env.reveal()) {
 444             value
 445         } else {
 446             value.fold_with(self)
 447         }
 448     }
 449 }
 450
 451 impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> {
 452     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
 453         self.selcx.tcx()
 454     }
 455
 456     fn fold_binder<T: TypeFoldable<'tcx>>(
 457         &mut self,
 458         t: ty::Binder<'tcx, T>,
 459     ) -> ty::Binder<'tcx, T> {
 460         self.universes.push(None);
 461         let t = t.super_fold_with(self);
 462         self.universes.pop();
 463         t
 464     }
 465
 466     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 467         if !needs_normalization(&ty, self.param_env.reveal()) {
 468             return ty;
 469         }
 470
 471         // We try to be a little clever here as a performance optimization in
 472         // cases where there are nested projections under binders.
 473         // For example:
 474         // ```
 475         // for<'a> fn(<T as Foo>::One<'a, Box<dyn Bar<'a, Item=<T as Foo>::Two<'a>>>>)
 476         // ```
 477         // We normalize the substs on the projection before the projecting, but
 478         // if we're naive, we'll
 479         //   replace bound vars on inner, project inner, replace placeholders on inner,
 480         //   replace bound vars on outer, project outer, replace placeholders on outer
 481         //
 482         // However, if we're a bit more clever, we can replace the bound vars
 483         // on the entire type before normalizing nested projections, meaning we
 484         //   replace bound vars on outer, project inner,
 485         //   project outer, replace placeholders on outer
 486         //
 487         // This is possible because the inner `'a` will already be a placeholder
 488         // when we need to normalize the inner projection
 489         //
 490         // On the other hand, this does add a bit of complexity, since we only
 491         // replace bound vars if the current type is a `Projection` and we need
 492         // to make sure we don't forget to fold the substs regardless.
 493
 494         match *ty.kind() {
 495             // This is really important. While we *can* handle this, this has
 496             // severe performance implications for large opaque types with
 497             // late-bound regions. See `issue-88862` benchmark.
 498             ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. })
 499                 if !substs.has_escaping_bound_vars() =>
 500             {
 501                 // Only normalize `impl Trait` outside of type inference, usually in codegen.
 502                 match self.param_env.reveal() {
 503                     Reveal::UserFacing => ty.super_fold_with(self),
 504
 505                     Reveal::All => {
 506                         let recursion_limit = self.tcx().recursion_limit();
 507                         if !recursion_limit.value_within_limit(self.depth) {
 508                             self.selcx.infcx.err_ctxt().report_overflow_error(
 509                                 &ty,
 510                                 self.cause.span,
 511                                 true,
 512                                 |_| {},
 513                             );
 514                         }
 515
 516                         let substs = substs.fold_with(self);
 517                         let generic_ty = self.tcx().bound_type_of(def_id);
 518                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 519                         self.depth += 1;
 520                         let folded_ty = self.fold_ty(concrete_ty);
 521                         self.depth -= 1;
 522                         folded_ty
 523                     }
 524                 }
 525             }
 526
 527             ty::Alias(ty::Projection, data) if !data.has_escaping_bound_vars() => {
 528                 // This branch is *mostly* just an optimization: when we don't
 529                 // have escaping bound vars, we don't need to replace them with
 530                 // placeholders (see branch below). *Also*, we know that we can
 531                 // register an obligation to *later* project, since we know
 532                 // there won't be bound vars there.
 533                 let data = data.fold_with(self);
 534                 let normalized_ty = if self.eager_inference_replacement {
 535                     normalize_projection_type(
 536                         self.selcx,
 537                         self.param_env,
 538                         data,
 539                         self.cause.clone(),
 540                         self.depth,
 541                         &mut self.obligations,
 542                     )
 543                 } else {
 544                     opt_normalize_projection_type(
 545                         self.selcx,
 546                         self.param_env,
 547                         data,
 548                         self.cause.clone(),
 549                         self.depth,
 550                         &mut self.obligations,
 551                     )
 552                     .ok()
 553                     .flatten()
 554                     .unwrap_or_else(|| ty.super_fold_with(self).into())
 555                 };
 556                 debug!(
 557                     ?self.depth,
 558                     ?ty,
 559                     ?normalized_ty,
 560                     obligations.len = ?self.obligations.len(),
 561                     "AssocTypeNormalizer: normalized type"
 562                 );
 563                 normalized_ty.ty().unwrap()
 564             }
 565
 566             ty::Alias(ty::Projection, data) => {
 567                 // If there are escaping bound vars, we temporarily replace the
 568                 // bound vars with placeholders. Note though, that in the case
 569                 // that we still can't project for whatever reason (e.g. self
 570                 // type isn't known enough), we *can't* register an obligation
 571                 // and return an inference variable (since then that obligation
 572                 // would have bound vars and that's a can of worms). Instead,
 573                 // we just give up and fall back to pretending like we never tried!
 574                 //
 575                 // Note: this isn't necessarily the final approach here; we may
 576                 // want to figure out how to register obligations with escaping vars
 577                 // or handle this some other way.
 578
 579                 let infcx = self.selcx.infcx;
 580                 let (data, mapped_regions, mapped_types, mapped_consts) =
 581                     BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
 582                 let data = data.fold_with(self);
 583                 let normalized_ty = opt_normalize_projection_type(
 584                     self.selcx,
 585                     self.param_env,
 586                     data,
 587                     self.cause.clone(),
 588                     self.depth,
 589                     &mut self.obligations,
 590                 )
 591                 .ok()
 592                 .flatten()
 593                 .map(|term| term.ty().unwrap())
 594                 .map(|normalized_ty| {
 595                     PlaceholderReplacer::replace_placeholders(
 596                         infcx,
 597                         mapped_regions,
 598                         mapped_types,
 599                         mapped_consts,
 600                         &self.universes,
 601                         normalized_ty,
 602                     )
 603                 })
 604                 .unwrap_or_else(|| ty.super_fold_with(self));
 605
 606                 debug!(
 607                     ?self.depth,
 608                     ?ty,
 609                     ?normalized_ty,
 610                     obligations.len = ?self.obligations.len(),
 611                     "AssocTypeNormalizer: normalized type"
 612                 );
 613                 normalized_ty
 614             }
 615
 616             _ => ty.super_fold_with(self),
 617         }
 618     }
 619
 620     #[instrument(skip(self), level = "debug")]
 621     fn fold_const(&mut self, constant: ty::Const<'tcx>) -> ty::Const<'tcx> {
 622         let tcx = self.selcx.tcx();
 623         if tcx.lazy_normalization() || !needs_normalization(&constant, self.param_env.reveal()) {
 624             constant
 625         } else {
 626             let constant = constant.super_fold_with(self);
 627             debug!(?constant, ?self.param_env);
 628             with_replaced_escaping_bound_vars(
 629                 self.selcx.infcx,
 630                 &mut self.universes,
 631                 constant,
 632                 |constant| constant.eval(tcx, self.param_env),
 633             )
 634         }
 635     }
 636
 637     #[inline]
 638     fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
 639         if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) {
 640             p.super_fold_with(self)
 641         } else {
 642             p
 643         }
 644     }
 645 }
 646
 647 pub struct BoundVarReplacer<'me, 'tcx> {
 648     infcx: &'me InferCtxt<'tcx>,
 649     // These three maps track the bound variable that were replaced by placeholders. It might be
 650     // nice to remove these since we already have the `kind` in the placeholder; we really just need
 651     // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
 652     mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
 653     mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
 654     mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
 655     // The current depth relative to *this* folding, *not* the entire normalization. In other words,
 656     // the depth of binders we've passed here.
 657     current_index: ty::DebruijnIndex,
 658     // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
 659     // we don't actually create a universe until we see a bound var we have to replace.
 660     universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>,
 661 }
 662
 663 /// Executes `f` on `value` after replacing all escaping bound variables with placeholders
 664 /// and then replaces these placeholders with the original bound variables in the result.
 665 ///
 666 /// In most places, bound variables should be replaced right when entering a binder, making
 667 /// this function unnecessary. However, normalization currently does not do that, so we have
 668 /// to do this lazily.
 669 ///
 670 /// You should not add any additional uses of this function, at least not without first
 671 /// discussing it with t-types.
 672 ///
 673 /// FIXME(@lcnr): We may even consider experimenting with eagerly replacing bound vars during
 674 /// normalization as well, at which point this function will be unnecessary and can be removed.
 675 pub fn with_replaced_escaping_bound_vars<'a, 'tcx, T: TypeFoldable<'tcx>, R: TypeFoldable<'tcx>>(
 676     infcx: &'a InferCtxt<'tcx>,
 677     universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
 678     value: T,
 679     f: impl FnOnce(T) -> R,
 680 ) -> R {
 681     if value.has_escaping_bound_vars() {
 682         let (value, mapped_regions, mapped_types, mapped_consts) =
 683             BoundVarReplacer::replace_bound_vars(infcx, universe_indices, value);
 684         let result = f(value);
 685         PlaceholderReplacer::replace_placeholders(
 686             infcx,
 687             mapped_regions,
 688             mapped_types,
 689             mapped_consts,
 690             universe_indices,
 691             result,
 692         )
 693     } else {
 694         f(value)
 695     }
 696 }
 697
 698 impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> {
 699     /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
 700     /// use a binding level above `universe_indices.len()`, we fail.
 701     pub fn replace_bound_vars<T: TypeFoldable<'tcx>>(
 702         infcx: &'me InferCtxt<'tcx>,
 703         universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>,
 704         value: T,
 705     ) -> (
 706         T,
 707         BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
 708         BTreeMap<ty::PlaceholderType, ty::BoundTy>,
 709         BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
 710     ) {
 711         let mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion> = BTreeMap::new();
 712         let mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy> = BTreeMap::new();
 713         let mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar> = BTreeMap::new();
 714
 715         let mut replacer = BoundVarReplacer {
 716             infcx,
 717             mapped_regions,
 718             mapped_types,
 719             mapped_consts,
 720             current_index: ty::INNERMOST,
 721             universe_indices,
 722         };
 723
 724         let value = value.fold_with(&mut replacer);
 725
 726         (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
 727     }
 728
 729     fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
 730         let infcx = self.infcx;
 731         let index =
 732             self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
 733         let universe = self.universe_indices[index].unwrap_or_else(|| {
 734             for i in self.universe_indices.iter_mut().take(index + 1) {
 735                 *i = i.or_else(|| Some(infcx.create_next_universe()))
 736             }
 737             self.universe_indices[index].unwrap()
 738         });
 739         universe
 740     }
 741 }
 742
 743 impl<'tcx> TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> {
 744     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 745         self.infcx.tcx
 746     }
 747
 748     fn fold_binder<T: TypeFoldable<'tcx>>(
 749         &mut self,
 750         t: ty::Binder<'tcx, T>,
 751     ) -> ty::Binder<'tcx, T> {
 752         self.current_index.shift_in(1);
 753         let t = t.super_fold_with(self);
 754         self.current_index.shift_out(1);
 755         t
 756     }
 757
 758     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 759         match *r {
 760             ty::ReLateBound(debruijn, _)
 761                 if debruijn.as_usize() + 1
 762                     > self.current_index.as_usize() + self.universe_indices.len() =>
 763             {
 764                 bug!("Bound vars outside of `self.universe_indices`");
 765             }
 766             ty::ReLateBound(debruijn, br) if debruijn >= self.current_index => {
 767                 let universe = self.universe_for(debruijn);
 768                 let p = ty::PlaceholderRegion { universe, name: br.kind };
 769                 self.mapped_regions.insert(p, br);
 770                 self.infcx.tcx.mk_region(ty::RePlaceholder(p))
 771             }
 772             _ => r,
 773         }
 774     }
 775
 776     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 777         match *t.kind() {
 778             ty::Bound(debruijn, _)
 779                 if debruijn.as_usize() + 1
 780                     > self.current_index.as_usize() + self.universe_indices.len() =>
 781             {
 782                 bug!("Bound vars outside of `self.universe_indices`");
 783             }
 784             ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
 785                 let universe = self.universe_for(debruijn);
 786                 let p = ty::PlaceholderType { universe, name: bound_ty.var };
 787                 self.mapped_types.insert(p, bound_ty);
 788                 self.infcx.tcx.mk_ty(ty::Placeholder(p))
 789             }
 790             _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
 791             _ => t,
 792         }
 793     }
 794
 795     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 796         match ct.kind() {
 797             ty::ConstKind::Bound(debruijn, _)
 798                 if debruijn.as_usize() + 1
 799                     > self.current_index.as_usize() + self.universe_indices.len() =>
 800             {
 801                 bug!("Bound vars outside of `self.universe_indices`");
 802             }
 803             ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => {
 804                 let universe = self.universe_for(debruijn);
 805                 let p = ty::PlaceholderConst { universe, name: bound_const };
 806                 self.mapped_consts.insert(p, bound_const);
 807                 self.infcx.tcx.mk_const(p, ct.ty())
 808             }
 809             _ => ct.super_fold_with(self),
 810         }
 811     }
 812
 813     fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
 814         if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
 815     }
 816 }
 817
 818 /// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
 819 pub struct PlaceholderReplacer<'me, 'tcx> {
 820     infcx: &'me InferCtxt<'tcx>,
 821     mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
 822     mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
 823     mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
 824     universe_indices: &'me [Option<ty::UniverseIndex>],
 825     current_index: ty::DebruijnIndex,
 826 }
 827
 828 impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> {
 829     pub fn replace_placeholders<T: TypeFoldable<'tcx>>(
 830         infcx: &'me InferCtxt<'tcx>,
 831         mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
 832         mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
 833         mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
 834         universe_indices: &'me [Option<ty::UniverseIndex>],
 835         value: T,
 836     ) -> T {
 837         let mut replacer = PlaceholderReplacer {
 838             infcx,
 839             mapped_regions,
 840             mapped_types,
 841             mapped_consts,
 842             universe_indices,
 843             current_index: ty::INNERMOST,
 844         };
 845         value.fold_with(&mut replacer)
 846     }
 847 }
 848
 849 impl<'tcx> TypeFolder<'tcx> for PlaceholderReplacer<'_, 'tcx> {
 850     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 851         self.infcx.tcx
 852     }
 853
 854     fn fold_binder<T: TypeFoldable<'tcx>>(
 855         &mut self,
 856         t: ty::Binder<'tcx, T>,
 857     ) -> ty::Binder<'tcx, T> {
 858         if !t.has_placeholders() && !t.has_infer_regions() {
 859             return t;
 860         }
 861         self.current_index.shift_in(1);
 862         let t = t.super_fold_with(self);
 863         self.current_index.shift_out(1);
 864         t
 865     }
 866
 867     fn fold_region(&mut self, r0: ty::Region<'tcx>) -> ty::Region<'tcx> {
 868         let r1 = match *r0 {
 869             ty::ReVar(_) => self
 870                 .infcx
 871                 .inner
 872                 .borrow_mut()
 873                 .unwrap_region_constraints()
 874                 .opportunistic_resolve_region(self.infcx.tcx, r0),
 875             _ => r0,
 876         };
 877
 878         let r2 = match *r1 {
 879             ty::RePlaceholder(p) => {
 880                 let replace_var = self.mapped_regions.get(&p);
 881                 match replace_var {
 882                     Some(replace_var) => {
 883                         let index = self
 884                             .universe_indices
 885                             .iter()
 886                             .position(|u| matches!(u, Some(pu) if *pu == p.universe))
 887                             .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
 888                         let db = ty::DebruijnIndex::from_usize(
 889                             self.universe_indices.len() - index + self.current_index.as_usize() - 1,
 890                         );
 891                         self.tcx().mk_region(ty::ReLateBound(db, *replace_var))
 892                     }
 893                     None => r1,
 894                 }
 895             }
 896             _ => r1,
 897         };
 898
 899         debug!(?r0, ?r1, ?r2, "fold_region");
 900
 901         r2
 902     }
 903
 904     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 905         match *ty.kind() {
 906             ty::Placeholder(p) => {
 907                 let replace_var = self.mapped_types.get(&p);
 908                 match replace_var {
 909                     Some(replace_var) => {
 910                         let index = self
 911                             .universe_indices
 912                             .iter()
 913                             .position(|u| matches!(u, Some(pu) if *pu == p.universe))
 914                             .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
 915                         let db = ty::DebruijnIndex::from_usize(
 916                             self.universe_indices.len() - index + self.current_index.as_usize() - 1,
 917                         );
 918                         self.tcx().mk_ty(ty::Bound(db, *replace_var))
 919                     }
 920                     None => ty,
 921                 }
 922             }
 923
 924             _ if ty.has_placeholders() || ty.has_infer_regions() => ty.super_fold_with(self),
 925             _ => ty,
 926         }
 927     }
 928
 929     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 930         if let ty::ConstKind::Placeholder(p) = ct.kind() {
 931             let replace_var = self.mapped_consts.get(&p);
 932             match replace_var {
 933                 Some(replace_var) => {
 934                     let index = self
 935                         .universe_indices
 936                         .iter()
 937                         .position(|u| matches!(u, Some(pu) if *pu == p.universe))
 938                         .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
 939                     let db = ty::DebruijnIndex::from_usize(
 940                         self.universe_indices.len() - index + self.current_index.as_usize() - 1,
 941                     );
 942                     self.tcx().mk_const(ty::ConstKind::Bound(db, *replace_var), ct.ty())
 943                 }
 944                 None => ct,
 945             }
 946         } else {
 947             ct.super_fold_with(self)
 948         }
 949     }
 950 }
 951
 952 /// The guts of `normalize`: normalize a specific projection like `<T
 953 /// as Trait>::Item`. The result is always a type (and possibly
 954 /// additional obligations). If ambiguity arises, which implies that
 955 /// there are unresolved type variables in the projection, we will
 956 /// substitute a fresh type variable `$X` and generate a new
 957 /// obligation `<T as Trait>::Item == $X` for later.
 958 pub fn normalize_projection_type<'a, 'b, 'tcx>(
 959     selcx: &'a mut SelectionContext<'b, 'tcx>,
 960     param_env: ty::ParamEnv<'tcx>,
 961     projection_ty: ty::AliasTy<'tcx>,
 962     cause: ObligationCause<'tcx>,
 963     depth: usize,
 964     obligations: &mut Vec<PredicateObligation<'tcx>>,
 965 ) -> Term<'tcx> {
 966     opt_normalize_projection_type(
 967         selcx,
 968         param_env,
 969         projection_ty,
 970         cause.clone(),
 971         depth,
 972         obligations,
 973     )
 974     .ok()
 975     .flatten()
 976     .unwrap_or_else(move || {
 977         // if we bottom out in ambiguity, create a type variable
 978         // and a deferred predicate to resolve this when more type
 979         // information is available.
 980
 981         selcx.infcx.infer_projection(param_env, projection_ty, cause, depth + 1, obligations).into()
 982     })
 983 }
 984
 985 /// The guts of `normalize`: normalize a specific projection like `<T
 986 /// as Trait>::Item`. The result is always a type (and possibly
 987 /// additional obligations). Returns `None` in the case of ambiguity,
 988 /// which indicates that there are unbound type variables.
 989 ///
 990 /// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a
 991 /// `Ty<'tcx>` and an obligations vector. But that obligation vector was very
 992 /// often immediately appended to another obligations vector. So now this
 993 /// function takes an obligations vector and appends to it directly, which is
 994 /// slightly uglier but avoids the need for an extra short-lived allocation.
 995 #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
 996 fn opt_normalize_projection_type<'a, 'b, 'tcx>(
 997     selcx: &'a mut SelectionContext<'b, 'tcx>,
 998     param_env: ty::ParamEnv<'tcx>,
 999     projection_ty: ty::AliasTy<'tcx>,
1000     cause: ObligationCause<'tcx>,
1001     depth: usize,
1002     obligations: &mut Vec<PredicateObligation<'tcx>>,
1003 ) -> Result<Option<Term<'tcx>>, InProgress> {
1004     let infcx = selcx.infcx;
1005     // Don't use the projection cache in intercrate mode -
1006     // the `infcx` may be re-used between intercrate in non-intercrate
1007     // mode, which could lead to using incorrect cache results.
1008     let use_cache = !selcx.is_intercrate();
1009
1010     let projection_ty = infcx.resolve_vars_if_possible(projection_ty);
1011     let cache_key = ProjectionCacheKey::new(projection_ty);
1012
1013     // FIXME(#20304) For now, I am caching here, which is good, but it
1014     // means we don't capture the type variables that are created in
1015     // the case of ambiguity. Which means we may create a large stream
1016     // of such variables. OTOH, if we move the caching up a level, we
1017     // would not benefit from caching when proving `T: Trait<U=Foo>`
1018     // bounds. It might be the case that we want two distinct caches,
1019     // or else another kind of cache entry.
1020
1021     let cache_result = if use_cache {
1022         infcx.inner.borrow_mut().projection_cache().try_start(cache_key)
1023     } else {
1024         Ok(())
1025     };
1026     match cache_result {
1027         Ok(()) => debug!("no cache"),
1028         Err(ProjectionCacheEntry::Ambiguous) => {
1029             // If we found ambiguity the last time, that means we will continue
1030             // to do so until some type in the key changes (and we know it
1031             // hasn't, because we just fully resolved it).
1032             debug!("found cache entry: ambiguous");
1033             return Ok(None);
1034         }
1035         Err(ProjectionCacheEntry::InProgress) => {
1036             // Under lazy normalization, this can arise when
1037             // bootstrapping. That is, imagine an environment with a
1038             // where-clause like `A::B == u32`. Now, if we are asked
1039             // to normalize `A::B`, we will want to check the
1040             // where-clauses in scope. So we will try to unify `A::B`
1041             // with `A::B`, which can trigger a recursive
1042             // normalization.
1043
1044             debug!("found cache entry: in-progress");
1045
1046             // Cache that normalizing this projection resulted in a cycle. This
1047             // should ensure that, unless this happens within a snapshot that's
1048             // rolled back, fulfillment or evaluation will notice the cycle.
1049
1050             if use_cache {
1051                 infcx.inner.borrow_mut().projection_cache().recur(cache_key);
1052             }
1053             return Err(InProgress);
1054         }
1055         Err(ProjectionCacheEntry::Recur) => {
1056             debug!("recur cache");
1057             return Err(InProgress);
1058         }
1059         Err(ProjectionCacheEntry::NormalizedTy { ty, complete: _ }) => {
1060             // This is the hottest path in this function.
1061             //
1062             // If we find the value in the cache, then return it along
1063             // with the obligations that went along with it. Note
1064             // that, when using a fulfillment context, these
1065             // obligations could in principle be ignored: they have
1066             // already been registered when the cache entry was
1067             // created (and hence the new ones will quickly be
1068             // discarded as duplicated). But when doing trait
1069             // evaluation this is not the case, and dropping the trait
1070             // evaluations can causes ICEs (e.g., #43132).
1071             debug!(?ty, "found normalized ty");
1072             obligations.extend(ty.obligations);
1073             return Ok(Some(ty.value));
1074         }
1075         Err(ProjectionCacheEntry::Error) => {
1076             debug!("opt_normalize_projection_type: found error");
1077             let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
1078             obligations.extend(result.obligations);
1079             return Ok(Some(result.value.into()));
1080         }
1081     }
1082
1083     let obligation =
1084         Obligation::with_depth(selcx.tcx(), cause.clone(), depth, param_env, projection_ty);
1085
1086     match project(selcx, &obligation) {
1087         Ok(Projected::Progress(Progress {
1088             term: projected_term,
1089             obligations: mut projected_obligations,
1090         })) => {
1091             // if projection succeeded, then what we get out of this
1092             // is also non-normalized (consider: it was derived from
1093             // an impl, where-clause etc) and hence we must
1094             // re-normalize it
1095
1096             let projected_term = selcx.infcx.resolve_vars_if_possible(projected_term);
1097
1098             let mut result = if projected_term.has_projections() {
1099                 let mut normalizer = AssocTypeNormalizer::new(
1100                     selcx,
1101                     param_env,
1102                     cause,
1103                     depth + 1,
1104                     &mut projected_obligations,
1105                 );
1106                 let normalized_ty = normalizer.fold(projected_term);
1107
1108                 Normalized { value: normalized_ty, obligations: projected_obligations }
1109             } else {
1110                 Normalized { value: projected_term, obligations: projected_obligations }
1111             };
1112
1113             let mut deduped: SsoHashSet<_> = Default::default();
1114             result.obligations.drain_filter(|projected_obligation| {
1115                 if !deduped.insert(projected_obligation.clone()) {
1116                     return true;
1117                 }
1118                 false
1119             });
1120
1121             if use_cache {
1122                 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
1123             }
1124             obligations.extend(result.obligations);
1125             Ok(Some(result.value))
1126         }
1127         Ok(Projected::NoProgress(projected_ty)) => {
1128             let result = Normalized { value: projected_ty, obligations: vec![] };
1129             if use_cache {
1130                 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
1131             }
1132             // No need to extend `obligations`.
1133             Ok(Some(result.value))
1134         }
1135         Err(ProjectionError::TooManyCandidates) => {
1136             debug!("opt_normalize_projection_type: too many candidates");
1137             if use_cache {
1138                 infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key);
1139             }
1140             Ok(None)
1141         }
1142         Err(ProjectionError::TraitSelectionError(_)) => {
1143             debug!("opt_normalize_projection_type: ERROR");
1144             // if we got an error processing the `T as Trait` part,
1145             // just return `ty::err` but add the obligation `T :
1146             // Trait`, which when processed will cause the error to be
1147             // reported later
1148
1149             if use_cache {
1150                 infcx.inner.borrow_mut().projection_cache().error(cache_key);
1151             }
1152             let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
1153             obligations.extend(result.obligations);
1154             Ok(Some(result.value.into()))
1155         }
1156     }
1157 }
1158
1159 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
1160 /// hold. In various error cases, we cannot generate a valid
1161 /// normalized projection. Therefore, we create an inference variable
1162 /// return an associated obligation that, when fulfilled, will lead to
1163 /// an error.
1164 ///
1165 /// Note that we used to return `Error` here, but that was quite
1166 /// dubious -- the premise was that an error would *eventually* be
1167 /// reported, when the obligation was processed. But in general once
1168 /// you see an `Error` you are supposed to be able to assume that an
1169 /// error *has been* reported, so that you can take whatever heuristic
1170 /// paths you want to take. To make things worse, it was possible for
1171 /// cycles to arise, where you basically had a setup like `<MyType<$0>
1172 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
1173 /// Trait>::Foo> to `[type error]` would lead to an obligation of
1174 /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
1175 /// an error for this obligation, but we legitimately should not,
1176 /// because it contains `[type error]`. Yuck! (See issue #29857 for
1177 /// one case where this arose.)
1178 fn normalize_to_error<'a, 'tcx>(
1179     selcx: &mut SelectionContext<'a, 'tcx>,
1180     param_env: ty::ParamEnv<'tcx>,
1181     projection_ty: ty::AliasTy<'tcx>,
1182     cause: ObligationCause<'tcx>,
1183     depth: usize,
1184 ) -> NormalizedTy<'tcx> {
1185     let trait_ref = ty::Binder::dummy(projection_ty.trait_ref(selcx.tcx()));
1186     let trait_obligation = Obligation {
1187         cause,
1188         recursion_depth: depth,
1189         param_env,
1190         predicate: trait_ref.without_const().to_predicate(selcx.tcx()),
1191     };
1192     let tcx = selcx.infcx.tcx;
1193     let new_value = selcx.infcx.next_ty_var(TypeVariableOrigin {
1194         kind: TypeVariableOriginKind::NormalizeProjectionType,
1195         span: tcx.def_span(projection_ty.def_id),
1196     });
1197     Normalized { value: new_value, obligations: vec![trait_obligation] }
1198 }
1199
1200 enum Projected<'tcx> {
1201     Progress(Progress<'tcx>),
1202     NoProgress(ty::Term<'tcx>),
1203 }
1204
1205 struct Progress<'tcx> {
1206     term: ty::Term<'tcx>,
1207     obligations: Vec<PredicateObligation<'tcx>>,
1208 }
1209
1210 impl<'tcx> Progress<'tcx> {
1211     fn error(tcx: TyCtxt<'tcx>) -> Self {
1212         Progress { term: tcx.ty_error().into(), obligations: vec![] }
1213     }
1214
1215     fn with_addl_obligations(mut self, mut obligations: Vec<PredicateObligation<'tcx>>) -> Self {
1216         self.obligations.append(&mut obligations);
1217         self
1218     }
1219 }
1220
1221 /// Computes the result of a projection type (if we can).
1222 ///
1223 /// IMPORTANT:
1224 /// - `obligation` must be fully normalized
1225 #[instrument(level = "info", skip(selcx))]
1226 fn project<'cx, 'tcx>(
1227     selcx: &mut SelectionContext<'cx, 'tcx>,
1228     obligation: &ProjectionTyObligation<'tcx>,
1229 ) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
1230     if !selcx.tcx().recursion_limit().value_within_limit(obligation.recursion_depth) {
1231         // This should really be an immediate error, but some existing code
1232         // relies on being able to recover from this.
1233         return Err(ProjectionError::TraitSelectionError(SelectionError::Overflow(
1234             OverflowError::Canonical,
1235         )));
1236     }
1237
1238     if obligation.predicate.references_error() {
1239         return Ok(Projected::Progress(Progress::error(selcx.tcx())));
1240     }
1241
1242     let mut candidates = ProjectionCandidateSet::None;
1243
1244     assemble_candidate_for_impl_trait_in_trait(selcx, obligation, &mut candidates);
1245
1246     // Make sure that the following procedures are kept in order. ParamEnv
1247     // needs to be first because it has highest priority, and Select checks
1248     // the return value of push_candidate which assumes it's ran at last.
1249     assemble_candidates_from_param_env(selcx, obligation, &mut candidates);
1250
1251     assemble_candidates_from_trait_def(selcx, obligation, &mut candidates);
1252
1253     assemble_candidates_from_object_ty(selcx, obligation, &mut candidates);
1254
1255     if let ProjectionCandidateSet::Single(ProjectionCandidate::Object(_)) = candidates {
1256         // Avoid normalization cycle from selection (see
1257         // `assemble_candidates_from_object_ty`).
1258         // FIXME(lazy_normalization): Lazy normalization should save us from
1259         // having to special case this.
1260     } else {
1261         assemble_candidates_from_impls(selcx, obligation, &mut candidates);
1262     };
1263
1264     match candidates {
1265         ProjectionCandidateSet::Single(candidate) => {
1266             Ok(Projected::Progress(confirm_candidate(selcx, obligation, candidate)))
1267         }
1268         ProjectionCandidateSet::None => Ok(Projected::NoProgress(
1269             // FIXME(associated_const_generics): this may need to change in the future?
1270             // need to investigate whether or not this is fine.
1271             selcx
1272                 .tcx()
1273                 .mk_projection(obligation.predicate.def_id, obligation.predicate.substs)
1274                 .into(),
1275         )),
1276         // Error occurred while trying to processing impls.
1277         ProjectionCandidateSet::Error(e) => Err(ProjectionError::TraitSelectionError(e)),
1278         // Inherent ambiguity that prevents us from even enumerating the
1279         // candidates.
1280         ProjectionCandidateSet::Ambiguous => Err(ProjectionError::TooManyCandidates),
1281     }
1282 }
1283
1284 /// If the predicate's item is an `ImplTraitPlaceholder`, we do a select on the
1285 /// corresponding trait ref. If this yields an `impl`, then we're able to project
1286 /// to a concrete type, since we have an `impl`'s method  to provide the RPITIT.
1287 fn assemble_candidate_for_impl_trait_in_trait<'cx, 'tcx>(
1288     selcx: &mut SelectionContext<'cx, 'tcx>,
1289     obligation: &ProjectionTyObligation<'tcx>,
1290     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1291 ) {
1292     let tcx = selcx.tcx();
1293     if tcx.def_kind(obligation.predicate.def_id) == DefKind::ImplTraitPlaceholder {
1294         let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id);
1295         // If we are trying to project an RPITIT with trait's default `Self` parameter,
1296         // then we must be within a default trait body.
1297         if obligation.predicate.self_ty()
1298             == ty::InternalSubsts::identity_for_item(tcx, obligation.predicate.def_id).type_at(0)
1299             && tcx.associated_item(trait_fn_def_id).defaultness(tcx).has_value()
1300         {
1301             candidate_set.push_candidate(ProjectionCandidate::ImplTraitInTrait(
1302                 ImplTraitInTraitCandidate::Trait,
1303             ));
1304             return;
1305         }
1306
1307         let trait_def_id = tcx.parent(trait_fn_def_id);
1308         let trait_substs =
1309             obligation.predicate.substs.truncate_to(tcx, tcx.generics_of(trait_def_id));
1310         // FIXME(named-returns): Binders
1311         let trait_predicate = ty::Binder::dummy(tcx.mk_trait_ref(trait_def_id, trait_substs));
1312
1313         let _ = selcx.infcx.commit_if_ok(|_| {
1314             match selcx.select(&obligation.with(tcx, trait_predicate)) {
1315                 Ok(Some(super::ImplSource::UserDefined(data))) => {
1316                     candidate_set.push_candidate(ProjectionCandidate::ImplTraitInTrait(
1317                         ImplTraitInTraitCandidate::Impl(data),
1318                     ));
1319                     Ok(())
1320                 }
1321                 Ok(None) => {
1322                     candidate_set.mark_ambiguous();
1323                     return Err(());
1324                 }
1325                 Ok(Some(_)) => {
1326                     // Don't know enough about the impl to provide a useful signature
1327                     return Err(());
1328                 }
1329                 Err(e) => {
1330                     debug!(error = ?e, "selection error");
1331                     candidate_set.mark_error(e);
1332                     return Err(());
1333                 }
1334             }
1335         });
1336     }
1337 }
1338
1339 /// The first thing we have to do is scan through the parameter
1340 /// environment to see whether there are any projection predicates
1341 /// there that can answer this question.
1342 fn assemble_candidates_from_param_env<'cx, 'tcx>(
1343     selcx: &mut SelectionContext<'cx, 'tcx>,
1344     obligation: &ProjectionTyObligation<'tcx>,
1345     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1346 ) {
1347     assemble_candidates_from_predicates(
1348         selcx,
1349         obligation,
1350         candidate_set,
1351         ProjectionCandidate::ParamEnv,
1352         obligation.param_env.caller_bounds().iter(),
1353         false,
1354     );
1355 }
1356
1357 /// In the case of a nested projection like `<<A as Foo>::FooT as Bar>::BarT`, we may find
1358 /// that the definition of `Foo` has some clues:
1359 ///
1360 /// ```ignore (illustrative)
1361 /// trait Foo {
1362 ///     type FooT : Bar<BarT=i32>
1363 /// }
1364 /// ```
1365 ///
1366 /// Here, for example, we could conclude that the result is `i32`.
1367 fn assemble_candidates_from_trait_def<'cx, 'tcx>(
1368     selcx: &mut SelectionContext<'cx, 'tcx>,
1369     obligation: &ProjectionTyObligation<'tcx>,
1370     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1371 ) {
1372     debug!("assemble_candidates_from_trait_def(..)");
1373
1374     let tcx = selcx.tcx();
1375     // Check whether the self-type is itself a projection.
1376     // If so, extract what we know from the trait and try to come up with a good answer.
1377     let bounds = match *obligation.predicate.self_ty().kind() {
1378         ty::Alias(_, ref data) => tcx.item_bounds(data.def_id).subst(tcx, data.substs),
1379         ty::Infer(ty::TyVar(_)) => {
1380             // If the self-type is an inference variable, then it MAY wind up
1381             // being a projected type, so induce an ambiguity.
1382             candidate_set.mark_ambiguous();
1383             return;
1384         }
1385         _ => return,
1386     };
1387
1388     assemble_candidates_from_predicates(
1389         selcx,
1390         obligation,
1391         candidate_set,
1392         ProjectionCandidate::TraitDef,
1393         bounds.iter(),
1394         true,
1395     );
1396 }
1397
1398 /// In the case of a trait object like
1399 /// `<dyn Iterator<Item = ()> as Iterator>::Item` we can use the existential
1400 /// predicate in the trait object.
1401 ///
1402 /// We don't go through the select candidate for these bounds to avoid cycles:
1403 /// In the above case, `dyn Iterator<Item = ()>: Iterator` would create a
1404 /// nested obligation of `<dyn Iterator<Item = ()> as Iterator>::Item: Sized`,
1405 /// this then has to be normalized without having to prove
1406 /// `dyn Iterator<Item = ()>: Iterator` again.
1407 fn assemble_candidates_from_object_ty<'cx, 'tcx>(
1408     selcx: &mut SelectionContext<'cx, 'tcx>,
1409     obligation: &ProjectionTyObligation<'tcx>,
1410     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1411 ) {
1412     debug!("assemble_candidates_from_object_ty(..)");
1413
1414     let tcx = selcx.tcx();
1415
1416     let self_ty = obligation.predicate.self_ty();
1417     let object_ty = selcx.infcx.shallow_resolve(self_ty);
1418     let data = match object_ty.kind() {
1419         ty::Dynamic(data, ..) => data,
1420         ty::Infer(ty::TyVar(_)) => {
1421             // If the self-type is an inference variable, then it MAY wind up
1422             // being an object type, so induce an ambiguity.
1423             candidate_set.mark_ambiguous();
1424             return;
1425         }
1426         _ => return,
1427     };
1428     let env_predicates = data
1429         .projection_bounds()
1430         .filter(|bound| bound.item_def_id() == obligation.predicate.def_id)
1431         .map(|p| p.with_self_ty(tcx, object_ty).to_predicate(tcx));
1432
1433     assemble_candidates_from_predicates(
1434         selcx,
1435         obligation,
1436         candidate_set,
1437         ProjectionCandidate::Object,
1438         env_predicates,
1439         false,
1440     );
1441 }
1442
1443 #[instrument(
1444     level = "debug",
1445     skip(selcx, candidate_set, ctor, env_predicates, potentially_unnormalized_candidates)
1446 )]
1447 fn assemble_candidates_from_predicates<'cx, 'tcx>(
1448     selcx: &mut SelectionContext<'cx, 'tcx>,
1449     obligation: &ProjectionTyObligation<'tcx>,
1450     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1451     ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionCandidate<'tcx>,
1452     env_predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
1453     potentially_unnormalized_candidates: bool,
1454 ) {
1455     let infcx = selcx.infcx;
1456     for predicate in env_predicates {
1457         let bound_predicate = predicate.kind();
1458         if let ty::PredicateKind::Clause(ty::Clause::Projection(data)) =
1459             predicate.kind().skip_binder()
1460         {
1461             let data = bound_predicate.rebind(data);
1462             if data.projection_def_id() != obligation.predicate.def_id {
1463                 continue;
1464             }
1465
1466             let is_match = infcx.probe(|_| {
1467                 selcx.match_projection_projections(
1468                     obligation,
1469                     data,
1470                     potentially_unnormalized_candidates,
1471                 )
1472             });
1473
1474             match is_match {
1475                 ProjectionMatchesProjection::Yes => {
1476                     candidate_set.push_candidate(ctor(data));
1477
1478                     if potentially_unnormalized_candidates
1479                         && !obligation.predicate.has_non_region_infer()
1480                     {
1481                         // HACK: Pick the first trait def candidate for a fully
1482                         // inferred predicate. This is to allow duplicates that
1483                         // differ only in normalization.
1484                         return;
1485                     }
1486                 }
1487                 ProjectionMatchesProjection::Ambiguous => {
1488                     candidate_set.mark_ambiguous();
1489                 }
1490                 ProjectionMatchesProjection::No => {}
1491             }
1492         }
1493     }
1494 }
1495
1496 #[instrument(level = "debug", skip(selcx, obligation, candidate_set))]
1497 fn assemble_candidates_from_impls<'cx, 'tcx>(
1498     selcx: &mut SelectionContext<'cx, 'tcx>,
1499     obligation: &ProjectionTyObligation<'tcx>,
1500     candidate_set: &mut ProjectionCandidateSet<'tcx>,
1501 ) {
1502     // Can't assemble candidate from impl for RPITIT
1503     if selcx.tcx().def_kind(obligation.predicate.def_id) == DefKind::ImplTraitPlaceholder {
1504         return;
1505     }
1506
1507     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
1508     // start out by selecting the predicate `T as TraitRef<...>`:
1509     let poly_trait_ref = ty::Binder::dummy(obligation.predicate.trait_ref(selcx.tcx()));
1510     let trait_obligation = obligation.with(selcx.tcx(), poly_trait_ref);
1511     let _ = selcx.infcx.commit_if_ok(|_| {
1512         let impl_source = match selcx.select(&trait_obligation) {
1513             Ok(Some(impl_source)) => impl_source,
1514             Ok(None) => {
1515                 candidate_set.mark_ambiguous();
1516                 return Err(());
1517             }
1518             Err(e) => {
1519                 debug!(error = ?e, "selection error");
1520                 candidate_set.mark_error(e);
1521                 return Err(());
1522             }
1523         };
1524
1525         let eligible = match &impl_source {
1526             super::ImplSource::Closure(_)
1527             | super::ImplSource::Generator(_)
1528             | super::ImplSource::Future(_)
1529             | super::ImplSource::FnPointer(_)
1530             | super::ImplSource::TraitAlias(_) => true,
1531             super::ImplSource::UserDefined(impl_data) => {
1532                 // We have to be careful when projecting out of an
1533                 // impl because of specialization. If we are not in
1534                 // codegen (i.e., projection mode is not "any"), and the
1535                 // impl's type is declared as default, then we disable
1536                 // projection (even if the trait ref is fully
1537                 // monomorphic). In the case where trait ref is not
1538                 // fully monomorphic (i.e., includes type parameters),
1539                 // this is because those type parameters may
1540                 // ultimately be bound to types from other crates that
1541                 // may have specialized impls we can't see. In the
1542                 // case where the trait ref IS fully monomorphic, this
1543                 // is a policy decision that we made in the RFC in
1544                 // order to preserve flexibility for the crate that
1545                 // defined the specializable impl to specialize later
1546                 // for existing types.
1547                 //
1548                 // In either case, we handle this by not adding a
1549                 // candidate for an impl if it contains a `default`
1550                 // type.
1551                 //
1552                 // NOTE: This should be kept in sync with the similar code in
1553                 // `rustc_ty_utils::instance::resolve_associated_item()`.
1554                 let node_item =
1555                     specialization_graph::assoc_def(selcx.tcx(), impl_data.impl_def_id, obligation.predicate.def_id)
1556                         .map_err(|ErrorGuaranteed { .. }| ())?;
1557
1558                 if node_item.is_final() {
1559                     // Non-specializable items are always projectable.
1560                     true
1561                 } else {
1562                     // Only reveal a specializable default if we're past type-checking
1563                     // and the obligation is monomorphic, otherwise passes such as
1564                     // transmute checking and polymorphic MIR optimizations could
1565                     // get a result which isn't correct for all monomorphizations.
1566                     if obligation.param_env.reveal() == Reveal::All {
1567                         // NOTE(eddyb) inference variables can resolve to parameters, so
1568                         // assume `poly_trait_ref` isn't monomorphic, if it contains any.
1569                         let poly_trait_ref = selcx.infcx.resolve_vars_if_possible(poly_trait_ref);
1570                         !poly_trait_ref.still_further_specializable()
1571                     } else {
1572                         debug!(
1573                             assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id),
1574                             ?obligation.predicate,
1575                             "assemble_candidates_from_impls: not eligible due to default",
1576                         );
1577                         false
1578                     }
1579                 }
1580             }
1581             super::ImplSource::Builtin(..) => {
1582                 // While a builtin impl may be known to exist, the associated type may not yet
1583                 // be known. Any type with multiple potential associated types is therefore
1584                 // not eligible.
1585                 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1586
1587                 let lang_items = selcx.tcx().lang_items();
1588                 if lang_items.discriminant_kind_trait() == Some(poly_trait_ref.def_id()) {
1589                     match self_ty.kind() {
1590                         ty::Bool
1591                         | ty::Char
1592                         | ty::Int(_)
1593                         | ty::Uint(_)
1594                         | ty::Float(_)
1595                         | ty::Adt(..)
1596                         | ty::Foreign(_)
1597                         | ty::Str
1598                         | ty::Array(..)
1599                         | ty::Slice(_)
1600                         | ty::RawPtr(..)
1601                         | ty::Ref(..)
1602                         | ty::FnDef(..)
1603                         | ty::FnPtr(..)
1604                         | ty::Dynamic(..)
1605                         | ty::Closure(..)
1606                         | ty::Generator(..)
1607                         | ty::GeneratorWitness(..)
1608                         | ty::Never
1609                         | ty::Tuple(..)
1610                         // Integers and floats always have `u8` as their discriminant.
1611                         | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1612
1613                          // type parameters, opaques, and unnormalized projections have pointer
1614                         // metadata if they're known (e.g. by the param_env) to be sized
1615                         ty::Param(_)
1616                         | ty::Alias(..)
1617                         | ty::Bound(..)
1618                         | ty::Placeholder(..)
1619                         | ty::Infer(..)
1620                         | ty::Error(_) => false,
1621                     }
1622                 } else if lang_items.pointee_trait() == Some(poly_trait_ref.def_id()) {
1623                     let tail = selcx.tcx().struct_tail_with_normalize(
1624                         self_ty,
1625                         |ty| {
1626                             // We throw away any obligations we get from this, since we normalize
1627                             // and confirm these obligations once again during confirmation
1628                             normalize_with_depth(
1629                                 selcx,
1630                                 obligation.param_env,
1631                                 obligation.cause.clone(),
1632                                 obligation.recursion_depth + 1,
1633                                 ty,
1634                             )
1635                             .value
1636                         },
1637                         || {},
1638                     );
1639
1640                     match tail.kind() {
1641                         ty::Bool
1642                         | ty::Char
1643                         | ty::Int(_)
1644                         | ty::Uint(_)
1645                         | ty::Float(_)
1646                         | ty::Str
1647                         | ty::Array(..)
1648                         | ty::Slice(_)
1649                         | ty::RawPtr(..)
1650                         | ty::Ref(..)
1651                         | ty::FnDef(..)
1652                         | ty::FnPtr(..)
1653                         | ty::Dynamic(..)
1654                         | ty::Closure(..)
1655                         | ty::Generator(..)
1656                         | ty::GeneratorWitness(..)
1657                         | ty::Never
1658                         // Extern types have unit metadata, according to RFC 2850
1659                         | ty::Foreign(_)
1660                         // If returned by `struct_tail_without_normalization` this is a unit struct
1661                         // without any fields, or not a struct, and therefore is Sized.
1662                         | ty::Adt(..)
1663                         // If returned by `struct_tail_without_normalization` this is the empty tuple.
1664                         | ty::Tuple(..)
1665                         // Integers and floats are always Sized, and so have unit type metadata.
1666                         | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1667
1668                         // type parameters, opaques, and unnormalized projections have pointer
1669                         // metadata if they're known (e.g. by the param_env) to be sized
1670                         ty::Param(_) | ty::Alias(..)
1671                             if selcx.infcx.predicate_must_hold_modulo_regions(
1672                                 &obligation.with(
1673                                     selcx.tcx(),
1674                                     ty::Binder::dummy(
1675                                         selcx.tcx().at(obligation.cause.span()).mk_trait_ref(LangItem::Sized, [self_ty]),
1676                                     )
1677                                     .without_const(),
1678                                 ),
1679                             ) =>
1680                         {
1681                             true
1682                         }
1683
1684                         // FIXME(compiler-errors): are Bound and Placeholder types ever known sized?
1685                         ty::Param(_)
1686                         | ty::Alias(..)
1687                         | ty::Bound(..)
1688                         | ty::Placeholder(..)
1689                         | ty::Infer(..)
1690                         | ty::Error(_) => {
1691                             if tail.has_infer_types() {
1692                                 candidate_set.mark_ambiguous();
1693                             }
1694                             false
1695                         }
1696                     }
1697                 } else {
1698                     bug!("unexpected builtin trait with associated type: {poly_trait_ref:?}")
1699                 }
1700             }
1701             super::ImplSource::Param(..) => {
1702                 // This case tell us nothing about the value of an
1703                 // associated type. Consider:
1704                 //
1705                 // ```
1706                 // trait SomeTrait { type Foo; }
1707                 // fn foo<T:SomeTrait>(...) { }
1708                 // ```
1709                 //
1710                 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1711                 // : SomeTrait` binding does not help us decide what the
1712                 // type `Foo` is (at least, not more specifically than
1713                 // what we already knew).
1714                 //
1715                 // But wait, you say! What about an example like this:
1716                 //
1717                 // ```
1718                 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1719                 // ```
1720                 //
1721                 // Doesn't the `T : SomeTrait<Foo=usize>` predicate help
1722                 // resolve `T::Foo`? And of course it does, but in fact
1723                 // that single predicate is desugared into two predicates
1724                 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1725                 // projection. And the projection where clause is handled
1726                 // in `assemble_candidates_from_param_env`.
1727                 false
1728             }
1729             super::ImplSource::Object(_) => {
1730                 // Handled by the `Object` projection candidate. See
1731                 // `assemble_candidates_from_object_ty` for an explanation of
1732                 // why we special case object types.
1733                 false
1734             }
1735             super::ImplSource::AutoImpl(..)
1736             | super::ImplSource::TraitUpcasting(_)
1737             | super::ImplSource::ConstDestruct(_) => {
1738                 // These traits have no associated types.
1739                 selcx.tcx().sess.delay_span_bug(
1740                     obligation.cause.span,
1741                     &format!("Cannot project an associated type from `{:?}`", impl_source),
1742                 );
1743                 return Err(());
1744             }
1745         };
1746
1747         if eligible {
1748             if candidate_set.push_candidate(ProjectionCandidate::Select(impl_source)) {
1749                 Ok(())
1750             } else {
1751                 Err(())
1752             }
1753         } else {
1754             Err(())
1755         }
1756     });
1757 }
1758
1759 fn confirm_candidate<'cx, 'tcx>(
1760     selcx: &mut SelectionContext<'cx, 'tcx>,
1761     obligation: &ProjectionTyObligation<'tcx>,
1762     candidate: ProjectionCandidate<'tcx>,
1763 ) -> Progress<'tcx> {
1764     debug!(?obligation, ?candidate, "confirm_candidate");
1765     let mut progress = match candidate {
1766         ProjectionCandidate::ParamEnv(poly_projection)
1767         | ProjectionCandidate::Object(poly_projection) => {
1768             confirm_param_env_candidate(selcx, obligation, poly_projection, false)
1769         }
1770
1771         ProjectionCandidate::TraitDef(poly_projection) => {
1772             confirm_param_env_candidate(selcx, obligation, poly_projection, true)
1773         }
1774
1775         ProjectionCandidate::Select(impl_source) => {
1776             confirm_select_candidate(selcx, obligation, impl_source)
1777         }
1778         ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Impl(data)) => {
1779             confirm_impl_trait_in_trait_candidate(selcx, obligation, data)
1780         }
1781         // If we're projecting an RPITIT for a default trait body, that's just
1782         // the same def-id, but as an opaque type (with regular RPIT semantics).
1783         ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Trait) => Progress {
1784             term: selcx
1785                 .tcx()
1786                 .mk_opaque(obligation.predicate.def_id, obligation.predicate.substs)
1787                 .into(),
1788             obligations: vec![],
1789         },
1790     };
1791
1792     // When checking for cycle during evaluation, we compare predicates with
1793     // "syntactic" equality. Since normalization generally introduces a type
1794     // with new region variables, we need to resolve them to existing variables
1795     // when possible for this to work. See `auto-trait-projection-recursion.rs`
1796     // for a case where this matters.
1797     if progress.term.has_infer_regions() {
1798         progress.term = progress.term.fold_with(&mut OpportunisticRegionResolver::new(selcx.infcx));
1799     }
1800     progress
1801 }
1802
1803 fn confirm_select_candidate<'cx, 'tcx>(
1804     selcx: &mut SelectionContext<'cx, 'tcx>,
1805     obligation: &ProjectionTyObligation<'tcx>,
1806     impl_source: Selection<'tcx>,
1807 ) -> Progress<'tcx> {
1808     match impl_source {
1809         super::ImplSource::UserDefined(data) => confirm_impl_candidate(selcx, obligation, data),
1810         super::ImplSource::Generator(data) => confirm_generator_candidate(selcx, obligation, data),
1811         super::ImplSource::Future(data) => confirm_future_candidate(selcx, obligation, data),
1812         super::ImplSource::Closure(data) => confirm_closure_candidate(selcx, obligation, data),
1813         super::ImplSource::FnPointer(data) => confirm_fn_pointer_candidate(selcx, obligation, data),
1814         super::ImplSource::Builtin(data) => confirm_builtin_candidate(selcx, obligation, data),
1815         super::ImplSource::Object(_)
1816         | super::ImplSource::AutoImpl(..)
1817         | super::ImplSource::Param(..)
1818         | super::ImplSource::TraitUpcasting(_)
1819         | super::ImplSource::TraitAlias(..)
1820         | super::ImplSource::ConstDestruct(_) => {
1821             // we don't create Select candidates with this kind of resolution
1822             span_bug!(
1823                 obligation.cause.span,
1824                 "Cannot project an associated type from `{:?}`",
1825                 impl_source
1826             )
1827         }
1828     }
1829 }
1830
1831 fn confirm_generator_candidate<'cx, 'tcx>(
1832     selcx: &mut SelectionContext<'cx, 'tcx>,
1833     obligation: &ProjectionTyObligation<'tcx>,
1834     impl_source: ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>,
1835 ) -> Progress<'tcx> {
1836     let gen_sig = impl_source.substs.as_generator().poly_sig();
1837     let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1838         selcx,
1839         obligation.param_env,
1840         obligation.cause.clone(),
1841         obligation.recursion_depth + 1,
1842         gen_sig,
1843     );
1844
1845     debug!(?obligation, ?gen_sig, ?obligations, "confirm_generator_candidate");
1846
1847     let tcx = selcx.tcx();
1848
1849     let gen_def_id = tcx.require_lang_item(LangItem::Generator, None);
1850
1851     let predicate = super::util::generator_trait_ref_and_outputs(
1852         tcx,
1853         gen_def_id,
1854         obligation.predicate.self_ty(),
1855         gen_sig,
1856     )
1857     .map_bound(|(trait_ref, yield_ty, return_ty)| {
1858         let name = tcx.associated_item(obligation.predicate.def_id).name;
1859         let ty = if name == sym::Return {
1860             return_ty
1861         } else if name == sym::Yield {
1862             yield_ty
1863         } else {
1864             bug!()
1865         };
1866
1867         ty::ProjectionPredicate {
1868             projection_ty: tcx.mk_alias_ty(obligation.predicate.def_id, trait_ref.substs),
1869             term: ty.into(),
1870         }
1871     });
1872
1873     confirm_param_env_candidate(selcx, obligation, predicate, false)
1874         .with_addl_obligations(impl_source.nested)
1875         .with_addl_obligations(obligations)
1876 }
1877
1878 fn confirm_future_candidate<'cx, 'tcx>(
1879     selcx: &mut SelectionContext<'cx, 'tcx>,
1880     obligation: &ProjectionTyObligation<'tcx>,
1881     impl_source: ImplSourceFutureData<'tcx, PredicateObligation<'tcx>>,
1882 ) -> Progress<'tcx> {
1883     let gen_sig = impl_source.substs.as_generator().poly_sig();
1884     let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1885         selcx,
1886         obligation.param_env,
1887         obligation.cause.clone(),
1888         obligation.recursion_depth + 1,
1889         gen_sig,
1890     );
1891
1892     debug!(?obligation, ?gen_sig, ?obligations, "confirm_future_candidate");
1893
1894     let tcx = selcx.tcx();
1895     let fut_def_id = tcx.require_lang_item(LangItem::Future, None);
1896
1897     let predicate = super::util::future_trait_ref_and_outputs(
1898         tcx,
1899         fut_def_id,
1900         obligation.predicate.self_ty(),
1901         gen_sig,
1902     )
1903     .map_bound(|(trait_ref, return_ty)| {
1904         debug_assert_eq!(tcx.associated_item(obligation.predicate.def_id).name, sym::Output);
1905
1906         ty::ProjectionPredicate {
1907             projection_ty: tcx.mk_alias_ty(obligation.predicate.def_id, trait_ref.substs),
1908             term: return_ty.into(),
1909         }
1910     });
1911
1912     confirm_param_env_candidate(selcx, obligation, predicate, false)
1913         .with_addl_obligations(impl_source.nested)
1914         .with_addl_obligations(obligations)
1915 }
1916
1917 fn confirm_builtin_candidate<'cx, 'tcx>(
1918     selcx: &mut SelectionContext<'cx, 'tcx>,
1919     obligation: &ProjectionTyObligation<'tcx>,
1920     data: ImplSourceBuiltinData<PredicateObligation<'tcx>>,
1921 ) -> Progress<'tcx> {
1922     let tcx = selcx.tcx();
1923     let self_ty = obligation.predicate.self_ty();
1924     let substs = tcx.mk_substs([self_ty.into()].iter());
1925     let lang_items = tcx.lang_items();
1926     let item_def_id = obligation.predicate.def_id;
1927     let trait_def_id = tcx.trait_of_item(item_def_id).unwrap();
1928     let (term, obligations) = if lang_items.discriminant_kind_trait() == Some(trait_def_id) {
1929         let discriminant_def_id = tcx.require_lang_item(LangItem::Discriminant, None);
1930         assert_eq!(discriminant_def_id, item_def_id);
1931
1932         (self_ty.discriminant_ty(tcx).into(), Vec::new())
1933     } else if lang_items.pointee_trait() == Some(trait_def_id) {
1934         let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None);
1935         assert_eq!(metadata_def_id, item_def_id);
1936
1937         let mut obligations = Vec::new();
1938         let (metadata_ty, check_is_sized) = self_ty.ptr_metadata_ty(tcx, |ty| {
1939             normalize_with_depth_to(
1940                 selcx,
1941                 obligation.param_env,
1942                 obligation.cause.clone(),
1943                 obligation.recursion_depth + 1,
1944                 ty,
1945                 &mut obligations,
1946             )
1947         });
1948         if check_is_sized {
1949             let sized_predicate = ty::Binder::dummy(
1950                 tcx.at(obligation.cause.span()).mk_trait_ref(LangItem::Sized, [self_ty]),
1951             )
1952             .without_const();
1953             obligations.push(obligation.with(tcx, sized_predicate));
1954         }
1955         (metadata_ty.into(), obligations)
1956     } else {
1957         bug!("unexpected builtin trait with associated type: {:?}", obligation.predicate);
1958     };
1959
1960     let predicate =
1961         ty::ProjectionPredicate { projection_ty: tcx.mk_alias_ty(item_def_id, substs), term };
1962
1963     confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1964         .with_addl_obligations(obligations)
1965         .with_addl_obligations(data.nested)
1966 }
1967
1968 fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1969     selcx: &mut SelectionContext<'cx, 'tcx>,
1970     obligation: &ProjectionTyObligation<'tcx>,
1971     fn_pointer_impl_source: ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>,
1972 ) -> Progress<'tcx> {
1973     let fn_type = selcx.infcx.shallow_resolve(fn_pointer_impl_source.fn_ty);
1974     let sig = fn_type.fn_sig(selcx.tcx());
1975     let Normalized { value: sig, obligations } = normalize_with_depth(
1976         selcx,
1977         obligation.param_env,
1978         obligation.cause.clone(),
1979         obligation.recursion_depth + 1,
1980         sig,
1981     );
1982
1983     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1984         .with_addl_obligations(fn_pointer_impl_source.nested)
1985         .with_addl_obligations(obligations)
1986 }
1987
1988 fn confirm_closure_candidate<'cx, 'tcx>(
1989     selcx: &mut SelectionContext<'cx, 'tcx>,
1990     obligation: &ProjectionTyObligation<'tcx>,
1991     impl_source: ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>,
1992 ) -> Progress<'tcx> {
1993     let closure_sig = impl_source.substs.as_closure().sig();
1994     let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1995         selcx,
1996         obligation.param_env,
1997         obligation.cause.clone(),
1998         obligation.recursion_depth + 1,
1999         closure_sig,
2000     );
2001
2002     debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate");
2003
2004     confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
2005         .with_addl_obligations(impl_source.nested)
2006         .with_addl_obligations(obligations)
2007 }
2008
2009 fn confirm_callable_candidate<'cx, 'tcx>(
2010     selcx: &mut SelectionContext<'cx, 'tcx>,
2011     obligation: &ProjectionTyObligation<'tcx>,
2012     fn_sig: ty::PolyFnSig<'tcx>,
2013     flag: util::TupleArgumentsFlag,
2014 ) -> Progress<'tcx> {
2015     let tcx = selcx.tcx();
2016
2017     debug!(?obligation, ?fn_sig, "confirm_callable_candidate");
2018
2019     let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, None);
2020     let fn_once_output_def_id = tcx.require_lang_item(LangItem::FnOnceOutput, None);
2021
2022     let predicate = super::util::closure_trait_ref_and_return_type(
2023         tcx,
2024         fn_once_def_id,
2025         obligation.predicate.self_ty(),
2026         fn_sig,
2027         flag,
2028     )
2029     .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
2030         projection_ty: tcx.mk_alias_ty(fn_once_output_def_id, trait_ref.substs),
2031         term: ret_type.into(),
2032     });
2033
2034     confirm_param_env_candidate(selcx, obligation, predicate, true)
2035 }
2036
2037 fn confirm_param_env_candidate<'cx, 'tcx>(
2038     selcx: &mut SelectionContext<'cx, 'tcx>,
2039     obligation: &ProjectionTyObligation<'tcx>,
2040     poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
2041     potentially_unnormalized_candidate: bool,
2042 ) -> Progress<'tcx> {
2043     let infcx = selcx.infcx;
2044     let cause = &obligation.cause;
2045     let param_env = obligation.param_env;
2046
2047     let cache_entry = infcx.replace_bound_vars_with_fresh_vars(
2048         cause.span,
2049         LateBoundRegionConversionTime::HigherRankedType,
2050         poly_cache_entry,
2051     );
2052
2053     let cache_projection = cache_entry.projection_ty;
2054     let mut nested_obligations = Vec::new();
2055     let obligation_projection = obligation.predicate;
2056     let obligation_projection = ensure_sufficient_stack(|| {
2057         normalize_with_depth_to(
2058             selcx,
2059             obligation.param_env,
2060             obligation.cause.clone(),
2061             obligation.recursion_depth + 1,
2062             obligation_projection,
2063             &mut nested_obligations,
2064         )
2065     });
2066     let cache_projection = if potentially_unnormalized_candidate {
2067         ensure_sufficient_stack(|| {
2068             normalize_with_depth_to(
2069                 selcx,
2070                 obligation.param_env,
2071                 obligation.cause.clone(),
2072                 obligation.recursion_depth + 1,
2073                 cache_projection,
2074                 &mut nested_obligations,
2075             )
2076         })
2077     } else {
2078         cache_projection
2079     };
2080
2081     debug!(?cache_projection, ?obligation_projection);
2082
2083     match infcx.at(cause, param_env).eq(cache_projection, obligation_projection) {
2084         Ok(InferOk { value: _, obligations }) => {
2085             nested_obligations.extend(obligations);
2086             assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations);
2087             // FIXME(associated_const_equality): Handle consts here as well? Maybe this progress type should just take
2088             // a term instead.
2089             Progress { term: cache_entry.term, obligations: nested_obligations }
2090         }
2091         Err(e) => {
2092             let msg = format!(
2093                 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
2094                 obligation, poly_cache_entry, e,
2095             );
2096             debug!("confirm_param_env_candidate: {}", msg);
2097             let err = infcx.tcx.ty_error_with_message(obligation.cause.span, &msg);
2098             Progress { term: err.into(), obligations: vec![] }
2099         }
2100     }
2101 }
2102
2103 fn confirm_impl_candidate<'cx, 'tcx>(
2104     selcx: &mut SelectionContext<'cx, 'tcx>,
2105     obligation: &ProjectionTyObligation<'tcx>,
2106     impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
2107 ) -> Progress<'tcx> {
2108     let tcx = selcx.tcx();
2109
2110     let ImplSourceUserDefinedData { impl_def_id, substs, mut nested } = impl_impl_source;
2111     let assoc_item_id = obligation.predicate.def_id;
2112     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
2113
2114     let param_env = obligation.param_env;
2115     let Ok(assoc_ty) = specialization_graph::assoc_def(tcx, impl_def_id, assoc_item_id) else {
2116         return Progress { term: tcx.ty_error().into(), obligations: nested };
2117     };
2118
2119     if !assoc_ty.item.defaultness(tcx).has_value() {
2120         // This means that the impl is missing a definition for the
2121         // associated type. This error will be reported by the type
2122         // checker method `check_impl_items_against_trait`, so here we
2123         // just return Error.
2124         debug!(
2125             "confirm_impl_candidate: no associated type {:?} for {:?}",
2126             assoc_ty.item.name, obligation.predicate
2127         );
2128         return Progress { term: tcx.ty_error().into(), obligations: nested };
2129     }
2130     // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
2131     //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
2132     //
2133     // * `obligation.predicate.substs` is `[Vec<u32>, S]`
2134     // * `substs` is `[u32]`
2135     // * `substs` ends up as `[u32, S]`
2136     let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs);
2137     let substs =
2138         translate_substs(selcx.infcx, param_env, impl_def_id, substs, assoc_ty.defining_node);
2139     let ty = tcx.bound_type_of(assoc_ty.item.def_id);
2140     let is_const = matches!(tcx.def_kind(assoc_ty.item.def_id), DefKind::AssocConst);
2141     let term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const {
2142         let identity_substs =
2143             crate::traits::InternalSubsts::identity_for_item(tcx, assoc_ty.item.def_id);
2144         let did = ty::WithOptConstParam::unknown(assoc_ty.item.def_id);
2145         let kind = ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs));
2146         ty.map_bound(|ty| tcx.mk_const(kind, ty).into())
2147     } else {
2148         ty.map_bound(|ty| ty.into())
2149     };
2150     if !check_substs_compatible(tcx, &assoc_ty.item, substs) {
2151         let err = tcx.ty_error_with_message(
2152             obligation.cause.span,
2153             "impl item and trait item have different parameters",
2154         );
2155         Progress { term: err.into(), obligations: nested }
2156     } else {
2157         assoc_ty_own_obligations(selcx, obligation, &mut nested);
2158         Progress { term: term.subst(tcx, substs), obligations: nested }
2159     }
2160 }
2161
2162 // Verify that the trait item and its implementation have compatible substs lists
2163 fn check_substs_compatible<'tcx>(
2164     tcx: TyCtxt<'tcx>,
2165     assoc_item: &ty::AssocItem,
2166     substs: ty::SubstsRef<'tcx>,
2167 ) -> bool {
2168     fn check_substs_compatible_inner<'tcx>(
2169         tcx: TyCtxt<'tcx>,
2170         generics: &'tcx ty::Generics,
2171         args: &'tcx [ty::GenericArg<'tcx>],
2172     ) -> bool {
2173         if generics.count() != args.len() {
2174             return false;
2175         }
2176
2177         let (parent_args, own_args) = args.split_at(generics.parent_count);
2178
2179         if let Some(parent) = generics.parent
2180             && let parent_generics = tcx.generics_of(parent)
2181             && !check_substs_compatible_inner(tcx, parent_generics, parent_args) {
2182             return false;
2183         }
2184
2185         for (param, arg) in std::iter::zip(&generics.params, own_args) {
2186             match (&param.kind, arg.unpack()) {
2187                 (ty::GenericParamDefKind::Type { .. }, ty::GenericArgKind::Type(_))
2188                 | (ty::GenericParamDefKind::Lifetime, ty::GenericArgKind::Lifetime(_))
2189                 | (ty::GenericParamDefKind::Const { .. }, ty::GenericArgKind::Const(_)) => {}
2190                 _ => return false,
2191             }
2192         }
2193
2194         true
2195     }
2196
2197     let generics = tcx.generics_of(assoc_item.def_id);
2198     // Chop off any additional substs (RPITIT) substs
2199     let substs = &substs[0..generics.count().min(substs.len())];
2200     check_substs_compatible_inner(tcx, generics, substs)
2201 }
2202
2203 fn confirm_impl_trait_in_trait_candidate<'tcx>(
2204     selcx: &mut SelectionContext<'_, 'tcx>,
2205     obligation: &ProjectionTyObligation<'tcx>,
2206     data: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
2207 ) -> Progress<'tcx> {
2208     let tcx = selcx.tcx();
2209     let mut obligations = data.nested;
2210
2211     let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id);
2212     let Ok(leaf_def) = specialization_graph::assoc_def(tcx, data.impl_def_id, trait_fn_def_id) else {
2213         return Progress { term: tcx.ty_error().into(), obligations };
2214     };
2215     if !leaf_def.item.defaultness(tcx).has_value() {
2216         return Progress { term: tcx.ty_error().into(), obligations };
2217     }
2218
2219     // Use the default `impl Trait` for the trait, e.g., for a default trait body
2220     if leaf_def.item.container == ty::AssocItemContainer::TraitContainer {
2221         return Progress {
2222             term: tcx.mk_opaque(obligation.predicate.def_id, obligation.predicate.substs).into(),
2223             obligations,
2224         };
2225     }
2226
2227     // Rebase from {trait}::{fn}::{opaque} to {impl}::{fn}::{opaque},
2228     // since `data.substs` are the impl substs.
2229     let impl_fn_substs =
2230         obligation.predicate.substs.rebase_onto(tcx, tcx.parent(trait_fn_def_id), data.substs);
2231     let impl_fn_substs = translate_substs(
2232         selcx.infcx,
2233         obligation.param_env,
2234         data.impl_def_id,
2235         impl_fn_substs,
2236         leaf_def.defining_node,
2237     );
2238
2239     if !check_substs_compatible(tcx, &leaf_def.item, impl_fn_substs) {
2240         let err = tcx.ty_error_with_message(
2241             obligation.cause.span,
2242             "impl method and trait method have different parameters",
2243         );
2244         return Progress { term: err.into(), obligations };
2245     }
2246
2247     let impl_fn_def_id = leaf_def.item.def_id;
2248
2249     let cause = ObligationCause::new(
2250         obligation.cause.span,
2251         obligation.cause.body_id,
2252         super::ItemObligation(impl_fn_def_id),
2253     );
2254     let predicates = normalize_with_depth_to(
2255         selcx,
2256         obligation.param_env,
2257         cause.clone(),
2258         obligation.recursion_depth + 1,
2259         tcx.predicates_of(impl_fn_def_id).instantiate(tcx, impl_fn_substs),
2260         &mut obligations,
2261     );
2262     obligations.extend(predicates.into_iter().map(|(pred, span)| {
2263         Obligation::with_depth(
2264             tcx,
2265             ObligationCause::new(
2266                 obligation.cause.span,
2267                 obligation.cause.body_id,
2268                 if span.is_dummy() {
2269                     super::ItemObligation(impl_fn_def_id)
2270                 } else {
2271                     super::BindingObligation(impl_fn_def_id, span)
2272                 },
2273             ),
2274             obligation.recursion_depth + 1,
2275             obligation.param_env,
2276             pred,
2277         )
2278     }));
2279
2280     let ty = normalize_with_depth_to(
2281         selcx,
2282         obligation.param_env,
2283         cause.clone(),
2284         obligation.recursion_depth + 1,
2285         tcx.bound_return_position_impl_trait_in_trait_tys(impl_fn_def_id)
2286             .map_bound(|tys| {
2287                 tys.map_or_else(|_| tcx.ty_error(), |tys| tys[&obligation.predicate.def_id])
2288             })
2289             .subst(tcx, impl_fn_substs),
2290         &mut obligations,
2291     );
2292
2293     Progress { term: ty.into(), obligations }
2294 }
2295
2296 // Get obligations corresponding to the predicates from the where-clause of the
2297 // associated type itself.
2298 fn assoc_ty_own_obligations<'cx, 'tcx>(
2299     selcx: &mut SelectionContext<'cx, 'tcx>,
2300     obligation: &ProjectionTyObligation<'tcx>,
2301     nested: &mut Vec<PredicateObligation<'tcx>>,
2302 ) {
2303     let tcx = selcx.tcx();
2304     let predicates = tcx
2305         .predicates_of(obligation.predicate.def_id)
2306         .instantiate_own(tcx, obligation.predicate.substs);
2307     for (predicate, span) in predicates {
2308         let normalized = normalize_with_depth_to(
2309             selcx,
2310             obligation.param_env,
2311             obligation.cause.clone(),
2312             obligation.recursion_depth + 1,
2313             predicate,
2314             nested,
2315         );
2316
2317         let nested_cause = if matches!(
2318             obligation.cause.code(),
2319             super::CompareImplItemObligation { .. }
2320                 | super::CheckAssociatedTypeBounds { .. }
2321                 | super::AscribeUserTypeProvePredicate(..)
2322         ) {
2323             obligation.cause.clone()
2324         } else if span.is_dummy() {
2325             ObligationCause::new(
2326                 obligation.cause.span,
2327                 obligation.cause.body_id,
2328                 super::ItemObligation(obligation.predicate.def_id),
2329             )
2330         } else {
2331             ObligationCause::new(
2332                 obligation.cause.span,
2333                 obligation.cause.body_id,
2334                 super::BindingObligation(obligation.predicate.def_id, span),
2335             )
2336         };
2337         nested.push(Obligation::with_depth(
2338             tcx,
2339             nested_cause,
2340             obligation.recursion_depth + 1,
2341             obligation.param_env,
2342             normalized,
2343         ));
2344     }
2345 }
2346
2347 pub(crate) trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized {
2348     fn from_poly_projection_predicate(
2349         selcx: &mut SelectionContext<'cx, 'tcx>,
2350         predicate: ty::PolyProjectionPredicate<'tcx>,
2351     ) -> Option<Self>;
2352 }
2353
2354 impl<'cx, 'tcx> ProjectionCacheKeyExt<'cx, 'tcx> for ProjectionCacheKey<'tcx> {
2355     fn from_poly_projection_predicate(
2356         selcx: &mut SelectionContext<'cx, 'tcx>,
2357         predicate: ty::PolyProjectionPredicate<'tcx>,
2358     ) -> Option<Self> {
2359         let infcx = selcx.infcx;
2360         // We don't do cross-snapshot caching of obligations with escaping regions,
2361         // so there's no cache key to use
2362         predicate.no_bound_vars().map(|predicate| {
2363             ProjectionCacheKey::new(
2364                 // We don't attempt to match up with a specific type-variable state
2365                 // from a specific call to `opt_normalize_projection_type` - if
2366                 // there's no precise match, the original cache entry is "stranded"
2367                 // anyway.
2368                 infcx.resolve_vars_if_possible(predicate.projection_ty),
2369             )
2370         })
2371     }
2372 }