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