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.kind };
 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::GeneratorWitnessMIR(..)
1609                         | ty::Never
1610                         | ty::Tuple(..)
1611                         // Integers and floats always have `u8` as their discriminant.
1612                         | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1613
1614                          // type parameters, opaques, and unnormalized projections have pointer
1615                         // metadata if they're known (e.g. by the param_env) to be sized
1616                         ty::Param(_)
1617                         | ty::Alias(..)
1618                         | ty::Bound(..)
1619                         | ty::Placeholder(..)
1620                         | ty::Infer(..)
1621                         | ty::Error(_) => false,
1622                     }
1623                 } else if lang_items.pointee_trait() == Some(poly_trait_ref.def_id()) {
1624                     let tail = selcx.tcx().struct_tail_with_normalize(
1625                         self_ty,
1626                         |ty| {
1627                             // We throw away any obligations we get from this, since we normalize
1628                             // and confirm these obligations once again during confirmation
1629                             normalize_with_depth(
1630                                 selcx,
1631                                 obligation.param_env,
1632                                 obligation.cause.clone(),
1633                                 obligation.recursion_depth + 1,
1634                                 ty,
1635                             )
1636                             .value
1637                         },
1638                         || {},
1639                     );
1640
1641                     match tail.kind() {
1642                         ty::Bool
1643                         | ty::Char
1644                         | ty::Int(_)
1645                         | ty::Uint(_)
1646                         | ty::Float(_)
1647                         | ty::Str
1648                         | ty::Array(..)
1649                         | ty::Slice(_)
1650                         | ty::RawPtr(..)
1651                         | ty::Ref(..)
1652                         | ty::FnDef(..)
1653                         | ty::FnPtr(..)
1654                         | ty::Dynamic(..)
1655                         | ty::Closure(..)
1656                         | ty::Generator(..)
1657                         | ty::GeneratorWitness(..)
1658                         | ty::GeneratorWitnessMIR(..)
1659                         | ty::Never
1660                         // Extern types have unit metadata, according to RFC 2850
1661                         | ty::Foreign(_)
1662                         // If returned by `struct_tail_without_normalization` this is a unit struct
1663                         // without any fields, or not a struct, and therefore is Sized.
1664                         | ty::Adt(..)
1665                         // If returned by `struct_tail_without_normalization` this is the empty tuple.
1666                         | ty::Tuple(..)
1667                         // Integers and floats are always Sized, and so have unit type metadata.
1668                         | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1669
1670                         // type parameters, opaques, and unnormalized projections have pointer
1671                         // metadata if they're known (e.g. by the param_env) to be sized
1672                         ty::Param(_) | ty::Alias(..)
1673                             if selcx.infcx.predicate_must_hold_modulo_regions(
1674                                 &obligation.with(
1675                                     selcx.tcx(),
1676                                     ty::Binder::dummy(
1677                                         selcx.tcx().at(obligation.cause.span()).mk_trait_ref(LangItem::Sized, [self_ty]),
1678                                     )
1679                                     .without_const(),
1680                                 ),
1681                             ) =>
1682                         {
1683                             true
1684                         }
1685
1686                         // FIXME(compiler-errors): are Bound and Placeholder types ever known sized?
1687                         ty::Param(_)
1688                         | ty::Alias(..)
1689                         | ty::Bound(..)
1690                         | ty::Placeholder(..)
1691                         | ty::Infer(..)
1692                         | ty::Error(_) => {
1693                             if tail.has_infer_types() {
1694                                 candidate_set.mark_ambiguous();
1695                             }
1696                             false
1697                         }
1698                     }
1699                 } else {
1700                     bug!("unexpected builtin trait with associated type: {poly_trait_ref:?}")
1701                 }
1702             }
1703             super::ImplSource::Param(..) => {
1704                 // This case tell us nothing about the value of an
1705                 // associated type. Consider:
1706                 //
1707                 // ```
1708                 // trait SomeTrait { type Foo; }
1709                 // fn foo<T:SomeTrait>(...) { }
1710                 // ```
1711                 //
1712                 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1713                 // : SomeTrait` binding does not help us decide what the
1714                 // type `Foo` is (at least, not more specifically than
1715                 // what we already knew).
1716                 //
1717                 // But wait, you say! What about an example like this:
1718                 //
1719                 // ```
1720                 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1721                 // ```
1722                 //
1723                 // Doesn't the `T : SomeTrait<Foo=usize>` predicate help
1724                 // resolve `T::Foo`? And of course it does, but in fact
1725                 // that single predicate is desugared into two predicates
1726                 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1727                 // projection. And the projection where clause is handled
1728                 // in `assemble_candidates_from_param_env`.
1729                 false
1730             }
1731             super::ImplSource::Object(_) => {
1732                 // Handled by the `Object` projection candidate. See
1733                 // `assemble_candidates_from_object_ty` for an explanation of
1734                 // why we special case object types.
1735                 false
1736             }
1737             super::ImplSource::AutoImpl(..)
1738             | super::ImplSource::TraitUpcasting(_)
1739             | super::ImplSource::ConstDestruct(_) => {
1740                 // These traits have no associated types.
1741                 selcx.tcx().sess.delay_span_bug(
1742                     obligation.cause.span,
1743                     &format!("Cannot project an associated type from `{:?}`", impl_source),
1744                 );
1745                 return Err(());
1746             }
1747         };
1748
1749         if eligible {
1750             if candidate_set.push_candidate(ProjectionCandidate::Select(impl_source)) {
1751                 Ok(())
1752             } else {
1753                 Err(())
1754             }
1755         } else {
1756             Err(())
1757         }
1758     });
1759 }
1760
1761 fn confirm_candidate<'cx, 'tcx>(
1762     selcx: &mut SelectionContext<'cx, 'tcx>,
1763     obligation: &ProjectionTyObligation<'tcx>,
1764     candidate: ProjectionCandidate<'tcx>,
1765 ) -> Progress<'tcx> {
1766     debug!(?obligation, ?candidate, "confirm_candidate");
1767     let mut progress = match candidate {
1768         ProjectionCandidate::ParamEnv(poly_projection)
1769         | ProjectionCandidate::Object(poly_projection) => {
1770             confirm_param_env_candidate(selcx, obligation, poly_projection, false)
1771         }
1772
1773         ProjectionCandidate::TraitDef(poly_projection) => {
1774             confirm_param_env_candidate(selcx, obligation, poly_projection, true)
1775         }
1776
1777         ProjectionCandidate::Select(impl_source) => {
1778             confirm_select_candidate(selcx, obligation, impl_source)
1779         }
1780         ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Impl(data)) => {
1781             confirm_impl_trait_in_trait_candidate(selcx, obligation, data)
1782         }
1783         // If we're projecting an RPITIT for a default trait body, that's just
1784         // the same def-id, but as an opaque type (with regular RPIT semantics).
1785         ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Trait) => Progress {
1786             term: selcx
1787                 .tcx()
1788                 .mk_opaque(obligation.predicate.def_id, obligation.predicate.substs)
1789                 .into(),
1790             obligations: vec![],
1791         },
1792     };
1793
1794     // When checking for cycle during evaluation, we compare predicates with
1795     // "syntactic" equality. Since normalization generally introduces a type
1796     // with new region variables, we need to resolve them to existing variables
1797     // when possible for this to work. See `auto-trait-projection-recursion.rs`
1798     // for a case where this matters.
1799     if progress.term.has_infer_regions() {
1800         progress.term = progress.term.fold_with(&mut OpportunisticRegionResolver::new(selcx.infcx));
1801     }
1802     progress
1803 }
1804
1805 fn confirm_select_candidate<'cx, 'tcx>(
1806     selcx: &mut SelectionContext<'cx, 'tcx>,
1807     obligation: &ProjectionTyObligation<'tcx>,
1808     impl_source: Selection<'tcx>,
1809 ) -> Progress<'tcx> {
1810     match impl_source {
1811         super::ImplSource::UserDefined(data) => confirm_impl_candidate(selcx, obligation, data),
1812         super::ImplSource::Generator(data) => confirm_generator_candidate(selcx, obligation, data),
1813         super::ImplSource::Future(data) => confirm_future_candidate(selcx, obligation, data),
1814         super::ImplSource::Closure(data) => confirm_closure_candidate(selcx, obligation, data),
1815         super::ImplSource::FnPointer(data) => confirm_fn_pointer_candidate(selcx, obligation, data),
1816         super::ImplSource::Builtin(data) => confirm_builtin_candidate(selcx, obligation, data),
1817         super::ImplSource::Object(_)
1818         | super::ImplSource::AutoImpl(..)
1819         | super::ImplSource::Param(..)
1820         | super::ImplSource::TraitUpcasting(_)
1821         | super::ImplSource::TraitAlias(..)
1822         | super::ImplSource::ConstDestruct(_) => {
1823             // we don't create Select candidates with this kind of resolution
1824             span_bug!(
1825                 obligation.cause.span,
1826                 "Cannot project an associated type from `{:?}`",
1827                 impl_source
1828             )
1829         }
1830     }
1831 }
1832
1833 fn confirm_generator_candidate<'cx, 'tcx>(
1834     selcx: &mut SelectionContext<'cx, 'tcx>,
1835     obligation: &ProjectionTyObligation<'tcx>,
1836     impl_source: ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>,
1837 ) -> Progress<'tcx> {
1838     let gen_sig = impl_source.substs.as_generator().poly_sig();
1839     let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1840         selcx,
1841         obligation.param_env,
1842         obligation.cause.clone(),
1843         obligation.recursion_depth + 1,
1844         gen_sig,
1845     );
1846
1847     debug!(?obligation, ?gen_sig, ?obligations, "confirm_generator_candidate");
1848
1849     let tcx = selcx.tcx();
1850
1851     let gen_def_id = tcx.require_lang_item(LangItem::Generator, None);
1852
1853     let predicate = super::util::generator_trait_ref_and_outputs(
1854         tcx,
1855         gen_def_id,
1856         obligation.predicate.self_ty(),
1857         gen_sig,
1858     )
1859     .map_bound(|(trait_ref, yield_ty, return_ty)| {
1860         let name = tcx.associated_item(obligation.predicate.def_id).name;
1861         let ty = if name == sym::Return {
1862             return_ty
1863         } else if name == sym::Yield {
1864             yield_ty
1865         } else {
1866             bug!()
1867         };
1868
1869         ty::ProjectionPredicate {
1870             projection_ty: tcx.mk_alias_ty(obligation.predicate.def_id, trait_ref.substs),
1871             term: ty.into(),
1872         }
1873     });
1874
1875     confirm_param_env_candidate(selcx, obligation, predicate, false)
1876         .with_addl_obligations(impl_source.nested)
1877         .with_addl_obligations(obligations)
1878 }
1879
1880 fn confirm_future_candidate<'cx, 'tcx>(
1881     selcx: &mut SelectionContext<'cx, 'tcx>,
1882     obligation: &ProjectionTyObligation<'tcx>,
1883     impl_source: ImplSourceFutureData<'tcx, PredicateObligation<'tcx>>,
1884 ) -> Progress<'tcx> {
1885     let gen_sig = impl_source.substs.as_generator().poly_sig();
1886     let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1887         selcx,
1888         obligation.param_env,
1889         obligation.cause.clone(),
1890         obligation.recursion_depth + 1,
1891         gen_sig,
1892     );
1893
1894     debug!(?obligation, ?gen_sig, ?obligations, "confirm_future_candidate");
1895
1896     let tcx = selcx.tcx();
1897     let fut_def_id = tcx.require_lang_item(LangItem::Future, None);
1898
1899     let predicate = super::util::future_trait_ref_and_outputs(
1900         tcx,
1901         fut_def_id,
1902         obligation.predicate.self_ty(),
1903         gen_sig,
1904     )
1905     .map_bound(|(trait_ref, return_ty)| {
1906         debug_assert_eq!(tcx.associated_item(obligation.predicate.def_id).name, sym::Output);
1907
1908         ty::ProjectionPredicate {
1909             projection_ty: tcx.mk_alias_ty(obligation.predicate.def_id, trait_ref.substs),
1910             term: return_ty.into(),
1911         }
1912     });
1913
1914     confirm_param_env_candidate(selcx, obligation, predicate, false)
1915         .with_addl_obligations(impl_source.nested)
1916         .with_addl_obligations(obligations)
1917 }
1918
1919 fn confirm_builtin_candidate<'cx, 'tcx>(
1920     selcx: &mut SelectionContext<'cx, 'tcx>,
1921     obligation: &ProjectionTyObligation<'tcx>,
1922     data: ImplSourceBuiltinData<PredicateObligation<'tcx>>,
1923 ) -> Progress<'tcx> {
1924     let tcx = selcx.tcx();
1925     let self_ty = obligation.predicate.self_ty();
1926     let substs = tcx.mk_substs([self_ty.into()].iter());
1927     let lang_items = tcx.lang_items();
1928     let item_def_id = obligation.predicate.def_id;
1929     let trait_def_id = tcx.trait_of_item(item_def_id).unwrap();
1930     let (term, obligations) = if lang_items.discriminant_kind_trait() == Some(trait_def_id) {
1931         let discriminant_def_id = tcx.require_lang_item(LangItem::Discriminant, None);
1932         assert_eq!(discriminant_def_id, item_def_id);
1933
1934         (self_ty.discriminant_ty(tcx).into(), Vec::new())
1935     } else if lang_items.pointee_trait() == Some(trait_def_id) {
1936         let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None);
1937         assert_eq!(metadata_def_id, item_def_id);
1938
1939         let mut obligations = Vec::new();
1940         let (metadata_ty, check_is_sized) = self_ty.ptr_metadata_ty(tcx, |ty| {
1941             normalize_with_depth_to(
1942                 selcx,
1943                 obligation.param_env,
1944                 obligation.cause.clone(),
1945                 obligation.recursion_depth + 1,
1946                 ty,
1947                 &mut obligations,
1948             )
1949         });
1950         if check_is_sized {
1951             let sized_predicate = ty::Binder::dummy(
1952                 tcx.at(obligation.cause.span()).mk_trait_ref(LangItem::Sized, [self_ty]),
1953             )
1954             .without_const();
1955             obligations.push(obligation.with(tcx, sized_predicate));
1956         }
1957         (metadata_ty.into(), obligations)
1958     } else {
1959         bug!("unexpected builtin trait with associated type: {:?}", obligation.predicate);
1960     };
1961
1962     let predicate =
1963         ty::ProjectionPredicate { projection_ty: tcx.mk_alias_ty(item_def_id, substs), term };
1964
1965     confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1966         .with_addl_obligations(obligations)
1967         .with_addl_obligations(data.nested)
1968 }
1969
1970 fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1971     selcx: &mut SelectionContext<'cx, 'tcx>,
1972     obligation: &ProjectionTyObligation<'tcx>,
1973     fn_pointer_impl_source: ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>,
1974 ) -> Progress<'tcx> {
1975     let fn_type = selcx.infcx.shallow_resolve(fn_pointer_impl_source.fn_ty);
1976     let sig = fn_type.fn_sig(selcx.tcx());
1977     let Normalized { value: sig, obligations } = normalize_with_depth(
1978         selcx,
1979         obligation.param_env,
1980         obligation.cause.clone(),
1981         obligation.recursion_depth + 1,
1982         sig,
1983     );
1984
1985     confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1986         .with_addl_obligations(fn_pointer_impl_source.nested)
1987         .with_addl_obligations(obligations)
1988 }
1989
1990 fn confirm_closure_candidate<'cx, 'tcx>(
1991     selcx: &mut SelectionContext<'cx, 'tcx>,
1992     obligation: &ProjectionTyObligation<'tcx>,
1993     impl_source: ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>,
1994 ) -> Progress<'tcx> {
1995     let closure_sig = impl_source.substs.as_closure().sig();
1996     let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1997         selcx,
1998         obligation.param_env,
1999         obligation.cause.clone(),
2000         obligation.recursion_depth + 1,
2001         closure_sig,
2002     );
2003
2004     debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate");
2005
2006     confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
2007         .with_addl_obligations(impl_source.nested)
2008         .with_addl_obligations(obligations)
2009 }
2010
2011 fn confirm_callable_candidate<'cx, 'tcx>(
2012     selcx: &mut SelectionContext<'cx, 'tcx>,
2013     obligation: &ProjectionTyObligation<'tcx>,
2014     fn_sig: ty::PolyFnSig<'tcx>,
2015     flag: util::TupleArgumentsFlag,
2016 ) -> Progress<'tcx> {
2017     let tcx = selcx.tcx();
2018
2019     debug!(?obligation, ?fn_sig, "confirm_callable_candidate");
2020
2021     let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, None);
2022     let fn_once_output_def_id = tcx.require_lang_item(LangItem::FnOnceOutput, None);
2023
2024     let predicate = super::util::closure_trait_ref_and_return_type(
2025         tcx,
2026         fn_once_def_id,
2027         obligation.predicate.self_ty(),
2028         fn_sig,
2029         flag,
2030     )
2031     .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
2032         projection_ty: tcx.mk_alias_ty(fn_once_output_def_id, trait_ref.substs),
2033         term: ret_type.into(),
2034     });
2035
2036     confirm_param_env_candidate(selcx, obligation, predicate, true)
2037 }
2038
2039 fn confirm_param_env_candidate<'cx, 'tcx>(
2040     selcx: &mut SelectionContext<'cx, 'tcx>,
2041     obligation: &ProjectionTyObligation<'tcx>,
2042     poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
2043     potentially_unnormalized_candidate: bool,
2044 ) -> Progress<'tcx> {
2045     let infcx = selcx.infcx;
2046     let cause = &obligation.cause;
2047     let param_env = obligation.param_env;
2048
2049     let cache_entry = infcx.replace_bound_vars_with_fresh_vars(
2050         cause.span,
2051         LateBoundRegionConversionTime::HigherRankedType,
2052         poly_cache_entry,
2053     );
2054
2055     let cache_projection = cache_entry.projection_ty;
2056     let mut nested_obligations = Vec::new();
2057     let obligation_projection = obligation.predicate;
2058     let obligation_projection = ensure_sufficient_stack(|| {
2059         normalize_with_depth_to(
2060             selcx,
2061             obligation.param_env,
2062             obligation.cause.clone(),
2063             obligation.recursion_depth + 1,
2064             obligation_projection,
2065             &mut nested_obligations,
2066         )
2067     });
2068     let cache_projection = if potentially_unnormalized_candidate {
2069         ensure_sufficient_stack(|| {
2070             normalize_with_depth_to(
2071                 selcx,
2072                 obligation.param_env,
2073                 obligation.cause.clone(),
2074                 obligation.recursion_depth + 1,
2075                 cache_projection,
2076                 &mut nested_obligations,
2077             )
2078         })
2079     } else {
2080         cache_projection
2081     };
2082
2083     debug!(?cache_projection, ?obligation_projection);
2084
2085     match infcx.at(cause, param_env).eq(cache_projection, obligation_projection) {
2086         Ok(InferOk { value: _, obligations }) => {
2087             nested_obligations.extend(obligations);
2088             assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations);
2089             // FIXME(associated_const_equality): Handle consts here as well? Maybe this progress type should just take
2090             // a term instead.
2091             Progress { term: cache_entry.term, obligations: nested_obligations }
2092         }
2093         Err(e) => {
2094             let msg = format!(
2095                 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
2096                 obligation, poly_cache_entry, e,
2097             );
2098             debug!("confirm_param_env_candidate: {}", msg);
2099             let err = infcx.tcx.ty_error_with_message(obligation.cause.span, &msg);
2100             Progress { term: err.into(), obligations: vec![] }
2101         }
2102     }
2103 }
2104
2105 fn confirm_impl_candidate<'cx, 'tcx>(
2106     selcx: &mut SelectionContext<'cx, 'tcx>,
2107     obligation: &ProjectionTyObligation<'tcx>,
2108     impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
2109 ) -> Progress<'tcx> {
2110     let tcx = selcx.tcx();
2111
2112     let ImplSourceUserDefinedData { impl_def_id, substs, mut nested } = impl_impl_source;
2113     let assoc_item_id = obligation.predicate.def_id;
2114     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
2115
2116     let param_env = obligation.param_env;
2117     let Ok(assoc_ty) = specialization_graph::assoc_def(tcx, impl_def_id, assoc_item_id) else {
2118         return Progress { term: tcx.ty_error().into(), obligations: nested };
2119     };
2120
2121     if !assoc_ty.item.defaultness(tcx).has_value() {
2122         // This means that the impl is missing a definition for the
2123         // associated type. This error will be reported by the type
2124         // checker method `check_impl_items_against_trait`, so here we
2125         // just return Error.
2126         debug!(
2127             "confirm_impl_candidate: no associated type {:?} for {:?}",
2128             assoc_ty.item.name, obligation.predicate
2129         );
2130         return Progress { term: tcx.ty_error().into(), obligations: nested };
2131     }
2132     // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
2133     //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
2134     //
2135     // * `obligation.predicate.substs` is `[Vec<u32>, S]`
2136     // * `substs` is `[u32]`
2137     // * `substs` ends up as `[u32, S]`
2138     let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs);
2139     let substs =
2140         translate_substs(selcx.infcx, param_env, impl_def_id, substs, assoc_ty.defining_node);
2141     let ty = tcx.bound_type_of(assoc_ty.item.def_id);
2142     let is_const = matches!(tcx.def_kind(assoc_ty.item.def_id), DefKind::AssocConst);
2143     let term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const {
2144         let identity_substs =
2145             crate::traits::InternalSubsts::identity_for_item(tcx, assoc_ty.item.def_id);
2146         let did = ty::WithOptConstParam::unknown(assoc_ty.item.def_id);
2147         let kind = ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs));
2148         ty.map_bound(|ty| tcx.mk_const(kind, ty).into())
2149     } else {
2150         ty.map_bound(|ty| ty.into())
2151     };
2152     if !check_substs_compatible(tcx, &assoc_ty.item, substs) {
2153         let err = tcx.ty_error_with_message(
2154             obligation.cause.span,
2155             "impl item and trait item have different parameters",
2156         );
2157         Progress { term: err.into(), obligations: nested }
2158     } else {
2159         assoc_ty_own_obligations(selcx, obligation, &mut nested);
2160         Progress { term: term.subst(tcx, substs), obligations: nested }
2161     }
2162 }
2163
2164 // Verify that the trait item and its implementation have compatible substs lists
2165 fn check_substs_compatible<'tcx>(
2166     tcx: TyCtxt<'tcx>,
2167     assoc_item: &ty::AssocItem,
2168     substs: ty::SubstsRef<'tcx>,
2169 ) -> bool {
2170     fn check_substs_compatible_inner<'tcx>(
2171         tcx: TyCtxt<'tcx>,
2172         generics: &'tcx ty::Generics,
2173         args: &'tcx [ty::GenericArg<'tcx>],
2174     ) -> bool {
2175         if generics.count() != args.len() {
2176             return false;
2177         }
2178
2179         let (parent_args, own_args) = args.split_at(generics.parent_count);
2180
2181         if let Some(parent) = generics.parent
2182             && let parent_generics = tcx.generics_of(parent)
2183             && !check_substs_compatible_inner(tcx, parent_generics, parent_args) {
2184             return false;
2185         }
2186
2187         for (param, arg) in std::iter::zip(&generics.params, own_args) {
2188             match (&param.kind, arg.unpack()) {
2189                 (ty::GenericParamDefKind::Type { .. }, ty::GenericArgKind::Type(_))
2190                 | (ty::GenericParamDefKind::Lifetime, ty::GenericArgKind::Lifetime(_))
2191                 | (ty::GenericParamDefKind::Const { .. }, ty::GenericArgKind::Const(_)) => {}
2192                 _ => return false,
2193             }
2194         }
2195
2196         true
2197     }
2198
2199     let generics = tcx.generics_of(assoc_item.def_id);
2200     // Chop off any additional substs (RPITIT) substs
2201     let substs = &substs[0..generics.count().min(substs.len())];
2202     check_substs_compatible_inner(tcx, generics, substs)
2203 }
2204
2205 fn confirm_impl_trait_in_trait_candidate<'tcx>(
2206     selcx: &mut SelectionContext<'_, 'tcx>,
2207     obligation: &ProjectionTyObligation<'tcx>,
2208     data: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
2209 ) -> Progress<'tcx> {
2210     let tcx = selcx.tcx();
2211     let mut obligations = data.nested;
2212
2213     let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id);
2214     let Ok(leaf_def) = specialization_graph::assoc_def(tcx, data.impl_def_id, trait_fn_def_id) else {
2215         return Progress { term: tcx.ty_error().into(), obligations };
2216     };
2217     if !leaf_def.item.defaultness(tcx).has_value() {
2218         return Progress { term: tcx.ty_error().into(), obligations };
2219     }
2220
2221     // Use the default `impl Trait` for the trait, e.g., for a default trait body
2222     if leaf_def.item.container == ty::AssocItemContainer::TraitContainer {
2223         return Progress {
2224             term: tcx.mk_opaque(obligation.predicate.def_id, obligation.predicate.substs).into(),
2225             obligations,
2226         };
2227     }
2228
2229     // Rebase from {trait}::{fn}::{opaque} to {impl}::{fn}::{opaque},
2230     // since `data.substs` are the impl substs.
2231     let impl_fn_substs =
2232         obligation.predicate.substs.rebase_onto(tcx, tcx.parent(trait_fn_def_id), data.substs);
2233     let impl_fn_substs = translate_substs(
2234         selcx.infcx,
2235         obligation.param_env,
2236         data.impl_def_id,
2237         impl_fn_substs,
2238         leaf_def.defining_node,
2239     );
2240
2241     if !check_substs_compatible(tcx, &leaf_def.item, impl_fn_substs) {
2242         let err = tcx.ty_error_with_message(
2243             obligation.cause.span,
2244             "impl method and trait method have different parameters",
2245         );
2246         return Progress { term: err.into(), obligations };
2247     }
2248
2249     let impl_fn_def_id = leaf_def.item.def_id;
2250
2251     let cause = ObligationCause::new(
2252         obligation.cause.span,
2253         obligation.cause.body_id,
2254         super::ItemObligation(impl_fn_def_id),
2255     );
2256     let predicates = normalize_with_depth_to(
2257         selcx,
2258         obligation.param_env,
2259         cause.clone(),
2260         obligation.recursion_depth + 1,
2261         tcx.predicates_of(impl_fn_def_id).instantiate(tcx, impl_fn_substs),
2262         &mut obligations,
2263     );
2264     obligations.extend(predicates.into_iter().map(|(pred, span)| {
2265         Obligation::with_depth(
2266             tcx,
2267             ObligationCause::new(
2268                 obligation.cause.span,
2269                 obligation.cause.body_id,
2270                 if span.is_dummy() {
2271                     super::ItemObligation(impl_fn_def_id)
2272                 } else {
2273                     super::BindingObligation(impl_fn_def_id, span)
2274                 },
2275             ),
2276             obligation.recursion_depth + 1,
2277             obligation.param_env,
2278             pred,
2279         )
2280     }));
2281
2282     let ty = normalize_with_depth_to(
2283         selcx,
2284         obligation.param_env,
2285         cause.clone(),
2286         obligation.recursion_depth + 1,
2287         tcx.bound_return_position_impl_trait_in_trait_tys(impl_fn_def_id)
2288             .map_bound(|tys| {
2289                 tys.map_or_else(|_| tcx.ty_error(), |tys| tys[&obligation.predicate.def_id])
2290             })
2291             .subst(tcx, impl_fn_substs),
2292         &mut obligations,
2293     );
2294
2295     Progress { term: ty.into(), obligations }
2296 }
2297
2298 // Get obligations corresponding to the predicates from the where-clause of the
2299 // associated type itself.
2300 fn assoc_ty_own_obligations<'cx, 'tcx>(
2301     selcx: &mut SelectionContext<'cx, 'tcx>,
2302     obligation: &ProjectionTyObligation<'tcx>,
2303     nested: &mut Vec<PredicateObligation<'tcx>>,
2304 ) {
2305     let tcx = selcx.tcx();
2306     let predicates = tcx
2307         .predicates_of(obligation.predicate.def_id)
2308         .instantiate_own(tcx, obligation.predicate.substs);
2309     for (predicate, span) in predicates {
2310         let normalized = normalize_with_depth_to(
2311             selcx,
2312             obligation.param_env,
2313             obligation.cause.clone(),
2314             obligation.recursion_depth + 1,
2315             predicate,
2316             nested,
2317         );
2318
2319         let nested_cause = if matches!(
2320             obligation.cause.code(),
2321             super::CompareImplItemObligation { .. }
2322                 | super::CheckAssociatedTypeBounds { .. }
2323                 | super::AscribeUserTypeProvePredicate(..)
2324         ) {
2325             obligation.cause.clone()
2326         } else if span.is_dummy() {
2327             ObligationCause::new(
2328                 obligation.cause.span,
2329                 obligation.cause.body_id,
2330                 super::ItemObligation(obligation.predicate.def_id),
2331             )
2332         } else {
2333             ObligationCause::new(
2334                 obligation.cause.span,
2335                 obligation.cause.body_id,
2336                 super::BindingObligation(obligation.predicate.def_id, span),
2337             )
2338         };
2339         nested.push(Obligation::with_depth(
2340             tcx,
2341             nested_cause,
2342             obligation.recursion_depth + 1,
2343             obligation.param_env,
2344             normalized,
2345         ));
2346     }
2347 }
2348
2349 pub(crate) trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized {
2350     fn from_poly_projection_predicate(
2351         selcx: &mut SelectionContext<'cx, 'tcx>,
2352         predicate: ty::PolyProjectionPredicate<'tcx>,
2353     ) -> Option<Self>;
2354 }
2355
2356 impl<'cx, 'tcx> ProjectionCacheKeyExt<'cx, 'tcx> for ProjectionCacheKey<'tcx> {
2357     fn from_poly_projection_predicate(
2358         selcx: &mut SelectionContext<'cx, 'tcx>,
2359         predicate: ty::PolyProjectionPredicate<'tcx>,
2360     ) -> Option<Self> {
2361         let infcx = selcx.infcx;
2362         // We don't do cross-snapshot caching of obligations with escaping regions,
2363         // so there's no cache key to use
2364         predicate.no_bound_vars().map(|predicate| {
2365             ProjectionCacheKey::new(
2366                 // We don't attempt to match up with a specific type-variable state
2367                 // from a specific call to `opt_normalize_projection_type` - if
2368                 // there's no precise match, the original cache entry is "stranded"
2369                 // anyway.
2370                 infcx.resolve_vars_if_possible(predicate.projection_ty),
2371             )
2372         })
2373     }
2374 }