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