Auto merge of #142483 - workingjubilee:rollup-8qnhueh, r=workingjubilee

Rollup of 16 pull requests

Successful merges:

 - rust-lang/rust#140969 (Allow initializing logger with additional tracing Layer)
 - rust-lang/rust#141352 (builtin dyn impl no guide inference)
 - rust-lang/rust#142046 (add Vec::peek_mut)
 - rust-lang/rust#142273 (tests: Minicore `extern "gpu-kernel"` feature test)
 - rust-lang/rust#142302 (Rework how the disallowed qualifier in function type diagnostics are generated)
 - rust-lang/rust#142405 (Don't hardcode the intrinsic return types twice in the compiler)
 - rust-lang/rust#142434 ( Pre-install JS dependencies in tidy Dockerfile)
 - rust-lang/rust#142439 (doc: mention that intrinsics should not be called in user code)
 - rust-lang/rust#142441 (Delay replacing escaping bound vars in `FindParamInClause`)
 - rust-lang/rust#142449 (Require generic params for const generic params)
 - rust-lang/rust#142452 (Remove "intermittent" wording from `ReadDir`)
 - rust-lang/rust#142459 (Remove output helper bootstrap)
 - rust-lang/rust#142460 (cleanup search graph impl)
 - rust-lang/rust#142461 (compiletest: Clarify that `--no-capture` is needed with `--verbose`)
 - rust-lang/rust#142475 (Add platform support docs & maintainers for *-windows-msvc)
 - rust-lang/rust#142480 (tests: Convert two handwritten minicores to add-core-stubs)

r? `@ghost`
`@rustbot` modify labels: rollup

32 files changed, 595 insertions, 379 deletions

diff --git a/compiler/rustc_ast_lowering/src/lib.rs b/compiler/rustc_ast_lowering/src/lib.rs
index 4f0368bcb01..3b99a653417 100644
--- a/compiler/rustc_ast_lowering/src/lib.rs
+++ b/compiler/rustc_ast_lowering/src/lib.rs
@@ -2147,7 +2147,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
                 ty_id,
                 &None,
                 path,
-                ParamMode::Optional,
+                ParamMode::Explicit,
                 AllowReturnTypeNotation::No,
                 // FIXME(mgca): update for `fn foo() -> Bar<FOO<impl Trait>>` support
                 ImplTraitContext::Disallowed(ImplTraitPosition::Path),
@@ -2219,7 +2219,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
                 expr.id,
                 qself,
                 path,
-                ParamMode::Optional,
+                ParamMode::Explicit,
                 AllowReturnTypeNotation::No,
                 // FIXME(mgca): update for `fn foo() -> Bar<FOO<impl Trait>>` support
                 ImplTraitContext::Disallowed(ImplTraitPosition::Path),
diff --git a/compiler/rustc_const_eval/src/interpret/intrinsics.rs b/compiler/rustc_const_eval/src/interpret/intrinsics.rs
index 754b2ba0d76..96c39c7bb32 100644
--- a/compiler/rustc_const_eval/src/interpret/intrinsics.rs
+++ b/compiler/rustc_const_eval/src/interpret/intrinsics.rs
@@ -139,13 +139,13 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
 
             sym::needs_drop | sym::type_id | sym::type_name | sym::variant_count => {
                 let gid = GlobalId { instance, promoted: None };
-                let ty = match intrinsic_name {
-                    sym::variant_count => self.tcx.types.usize,
-                    sym::needs_drop => self.tcx.types.bool,
-                    sym::type_id => self.tcx.types.u128,
-                    sym::type_name => Ty::new_static_str(self.tcx.tcx),
-                    _ => bug!(),
-                };
+                let ty = self
+                    .tcx
+                    .fn_sig(instance.def_id())
+                    .instantiate(self.tcx.tcx, instance.args)
+                    .output()
+                    .no_bound_vars()
+                    .unwrap();
                 let val = self
                     .ctfe_query(|tcx| tcx.const_eval_global_id(self.typing_env, gid, tcx.span))?;
                 let val = self.const_val_to_op(val, ty, Some(dest.layout))?;
diff --git a/compiler/rustc_driver_impl/src/lib.rs b/compiler/rustc_driver_impl/src/lib.rs
index 54a331a4904..0cd9e36a927 100644
--- a/compiler/rustc_driver_impl/src/lib.rs
+++ b/compiler/rustc_driver_impl/src/lib.rs
@@ -1500,13 +1500,31 @@ pub fn init_rustc_env_logger(early_dcx: &EarlyDiagCtxt) {
 
 /// This allows tools to enable rust logging without having to magically match rustc's
 /// tracing crate version. In contrast to `init_rustc_env_logger` it allows you to choose
-/// the values directly rather than having to set an environment variable.
+/// the logger config directly rather than having to set an environment variable.
 pub fn init_logger(early_dcx: &EarlyDiagCtxt, cfg: rustc_log::LoggerConfig) {
     if let Err(error) = rustc_log::init_logger(cfg) {
         early_dcx.early_fatal(error.to_string());
     }
 }
 
+/// This allows tools to enable rust logging without having to magically match rustc's
+/// tracing crate version. In contrast to `init_rustc_env_logger`, it allows you to
+/// choose the logger config directly rather than having to set an environment variable.
+/// Moreover, in contrast to `init_logger`, it allows you to add a custom tracing layer
+/// via `build_subscriber`, for example `|| Registry::default().with(custom_layer)`.
+pub fn init_logger_with_additional_layer<F, T>(
+    early_dcx: &EarlyDiagCtxt,
+    cfg: rustc_log::LoggerConfig,
+    build_subscriber: F,
+) where
+    F: FnOnce() -> T,
+    T: rustc_log::BuildSubscriberRet,
+{
+    if let Err(error) = rustc_log::init_logger_with_additional_layer(cfg, build_subscriber) {
+        early_dcx.early_fatal(error.to_string());
+    }
+}
+
 /// Install our usual `ctrlc` handler, which sets [`rustc_const_eval::CTRL_C_RECEIVED`].
 /// Making this handler optional lets tools can install a different handler, if they wish.
 pub fn install_ctrlc_handler() {
diff --git a/compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs b/compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs
index bdc42c7a2d9..106420faa4c 100644
--- a/compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs
+++ b/compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs
@@ -9,8 +9,8 @@ use rustc_hir::def::{DefKind, Res};
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_middle::bug;
 use rustc_middle::ty::{
-    self as ty, IsSuggestable, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable,
-    TypeVisitableExt, TypeVisitor, Upcast,
+    self as ty, IsSuggestable, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
+    TypeVisitor, Upcast,
 };
 use rustc_span::{ErrorGuaranteed, Ident, Span, Symbol, kw, sym};
 use rustc_trait_selection::traits;
@@ -927,7 +927,7 @@ struct GenericParamAndBoundVarCollector<'a, 'tcx> {
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for GenericParamAndBoundVarCollector<'_, 'tcx> {
     type Result = ControlFlow<ErrorGuaranteed>;
 
-    fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
         &mut self,
         binder: &ty::Binder<'tcx, T>,
     ) -> Self::Result {
diff --git a/compiler/rustc_lint/src/impl_trait_overcaptures.rs b/compiler/rustc_lint/src/impl_trait_overcaptures.rs
index 8124d7f7c86..aa6f36a67f0 100644
--- a/compiler/rustc_lint/src/impl_trait_overcaptures.rs
+++ b/compiler/rustc_lint/src/impl_trait_overcaptures.rs
@@ -15,8 +15,7 @@ use rustc_middle::ty::relate::{
     Relate, RelateResult, TypeRelation, structurally_relate_consts, structurally_relate_tys,
 };
 use rustc_middle::ty::{
-    self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
-    TypeVisitor,
+    self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor,
 };
 use rustc_middle::{bug, span_bug};
 use rustc_session::lint::FutureIncompatibilityReason;
@@ -210,7 +209,7 @@ where
     VarFn: FnOnce() -> FxHashMap<DefId, ty::Variance>,
     OutlivesFn: FnOnce() -> OutlivesEnvironment<'tcx>,
 {
-    fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
         // When we get into a binder, we need to add its own bound vars to the scope.
         let mut added = vec![];
         for arg in t.bound_vars() {
diff --git a/compiler/rustc_log/src/lib.rs b/compiler/rustc_log/src/lib.rs
index 1bb502ca3d0..df648bbd489 100644
--- a/compiler/rustc_log/src/lib.rs
+++ b/compiler/rustc_log/src/lib.rs
@@ -43,6 +43,7 @@ use tracing_subscriber::filter::{Directive, EnvFilter, LevelFilter};
 use tracing_subscriber::fmt::FmtContext;
 use tracing_subscriber::fmt::format::{self, FormatEvent, FormatFields};
 use tracing_subscriber::layer::SubscriberExt;
+use tracing_subscriber::{Layer, Registry};
 
 /// The values of all the environment variables that matter for configuring a logger.
 /// Errors are explicitly preserved so that we can share error handling.
@@ -72,6 +73,36 @@ impl LoggerConfig {
 
 /// Initialize the logger with the given values for the filter, coloring, and other options env variables.
 pub fn init_logger(cfg: LoggerConfig) -> Result<(), Error> {
+    init_logger_with_additional_layer(cfg, || Registry::default())
+}
+
+/// Trait alias for the complex return type of `build_subscriber` in
+/// [init_logger_with_additional_layer]. A [Registry] with any composition of [tracing::Subscriber]s
+/// (e.g. `Registry::default().with(custom_layer)`) should be compatible with this type.
+/// Having an alias is also useful so rustc_driver_impl does not need to explicitly depend on
+/// `tracing_subscriber`.
+pub trait BuildSubscriberRet:
+    tracing::Subscriber + for<'span> tracing_subscriber::registry::LookupSpan<'span> + Send + Sync
+{
+}
+
+impl<
+    T: tracing::Subscriber + for<'span> tracing_subscriber::registry::LookupSpan<'span> + Send + Sync,
+> BuildSubscriberRet for T
+{
+}
+
+/// Initialize the logger with the given values for the filter, coloring, and other options env variables.
+/// Additionally add a custom layer to collect logging and tracing events via `build_subscriber`,
+/// for example: `|| Registry::default().with(custom_layer)`.
+pub fn init_logger_with_additional_layer<F, T>(
+    cfg: LoggerConfig,
+    build_subscriber: F,
+) -> Result<(), Error>
+where
+    F: FnOnce() -> T,
+    T: BuildSubscriberRet,
+{
     let filter = match cfg.filter {
         Ok(env) => EnvFilter::new(env),
         _ => EnvFilter::default().add_directive(Directive::from(LevelFilter::WARN)),
@@ -124,7 +155,7 @@ pub fn init_logger(cfg: LoggerConfig) -> Result<(), Error> {
         Err(_) => {} // no wraptree
     }
 
-    let subscriber = tracing_subscriber::Registry::default().with(filter).with(layer);
+    let subscriber = build_subscriber().with(layer.with_filter(filter));
     match cfg.backtrace {
         Ok(backtrace_target) => {
             let fmt_layer = tracing_subscriber::fmt::layer()
diff --git a/compiler/rustc_middle/src/ty/consts.rs b/compiler/rustc_middle/src/ty/consts.rs
index 455ac660412..2fbaa2221a1 100644
--- a/compiler/rustc_middle/src/ty/consts.rs
+++ b/compiler/rustc_middle/src/ty/consts.rs
@@ -163,6 +163,10 @@ impl<'tcx> rustc_type_ir::inherent::Const<TyCtxt<'tcx>> for Const<'tcx> {
         Const::new_bound(tcx, debruijn, var)
     }
 
+    fn new_placeholder(tcx: TyCtxt<'tcx>, placeholder: ty::PlaceholderConst) -> Self {
+        Const::new_placeholder(tcx, placeholder)
+    }
+
     fn new_unevaluated(interner: TyCtxt<'tcx>, uv: ty::UnevaluatedConst<'tcx>) -> Self {
         Const::new_unevaluated(interner, uv)
     }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index dc3f2844e5a..0402d098822 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -933,7 +933,9 @@ impl Placeholder<BoundVar> {
 
 pub type PlaceholderRegion = Placeholder<BoundRegion>;
 
-impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderRegion {
+impl<'tcx> rustc_type_ir::inherent::PlaceholderLike<TyCtxt<'tcx>> for PlaceholderRegion {
+    type Bound = BoundRegion;
+
     fn universe(self) -> UniverseIndex {
         self.universe
     }
@@ -946,14 +948,20 @@ impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderRegion {
         Placeholder { universe: ui, ..self }
     }
 
-    fn new(ui: UniverseIndex, var: BoundVar) -> Self {
+    fn new(ui: UniverseIndex, bound: BoundRegion) -> Self {
+        Placeholder { universe: ui, bound }
+    }
+
+    fn new_anon(ui: UniverseIndex, var: BoundVar) -> Self {
         Placeholder { universe: ui, bound: BoundRegion { var, kind: BoundRegionKind::Anon } }
     }
 }
 
 pub type PlaceholderType = Placeholder<BoundTy>;
 
-impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderType {
+impl<'tcx> rustc_type_ir::inherent::PlaceholderLike<TyCtxt<'tcx>> for PlaceholderType {
+    type Bound = BoundTy;
+
     fn universe(self) -> UniverseIndex {
         self.universe
     }
@@ -966,7 +974,11 @@ impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderType {
         Placeholder { universe: ui, ..self }
     }
 
-    fn new(ui: UniverseIndex, var: BoundVar) -> Self {
+    fn new(ui: UniverseIndex, bound: BoundTy) -> Self {
+        Placeholder { universe: ui, bound }
+    }
+
+    fn new_anon(ui: UniverseIndex, var: BoundVar) -> Self {
         Placeholder { universe: ui, bound: BoundTy { var, kind: BoundTyKind::Anon } }
     }
 }
@@ -980,7 +992,9 @@ pub struct BoundConst<'tcx> {
 
 pub type PlaceholderConst = Placeholder<BoundVar>;
 
-impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderConst {
+impl<'tcx> rustc_type_ir::inherent::PlaceholderLike<TyCtxt<'tcx>> for PlaceholderConst {
+    type Bound = BoundVar;
+
     fn universe(self) -> UniverseIndex {
         self.universe
     }
@@ -993,7 +1007,11 @@ impl rustc_type_ir::inherent::PlaceholderLike for PlaceholderConst {
         Placeholder { universe: ui, ..self }
     }
 
-    fn new(ui: UniverseIndex, var: BoundVar) -> Self {
+    fn new(ui: UniverseIndex, bound: BoundVar) -> Self {
+        Placeholder { universe: ui, bound }
+    }
+
+    fn new_anon(ui: UniverseIndex, var: BoundVar) -> Self {
         Placeholder { universe: ui, bound: var }
     }
 }
diff --git a/compiler/rustc_middle/src/ty/region.rs b/compiler/rustc_middle/src/ty/region.rs
index 3e4f7a79d53..cc25cd16567 100644
--- a/compiler/rustc_middle/src/ty/region.rs
+++ b/compiler/rustc_middle/src/ty/region.rs
@@ -148,6 +148,10 @@ impl<'tcx> rustc_type_ir::inherent::Region<TyCtxt<'tcx>> for Region<'tcx> {
         Region::new_bound(tcx, debruijn, ty::BoundRegion { var, kind: ty::BoundRegionKind::Anon })
     }
 
+    fn new_placeholder(tcx: TyCtxt<'tcx>, placeholder: ty::PlaceholderRegion) -> Self {
+        Region::new_placeholder(tcx, placeholder)
+    }
+
     fn new_static(tcx: TyCtxt<'tcx>) -> Self {
         tcx.lifetimes.re_static
     }
diff --git a/compiler/rustc_middle/src/ty/visit.rs b/compiler/rustc_middle/src/ty/visit.rs
index f8042174599..3853a804a92 100644
--- a/compiler/rustc_middle/src/ty/visit.rs
+++ b/compiler/rustc_middle/src/ty/visit.rs
@@ -66,7 +66,7 @@ impl<'tcx> TyCtxt<'tcx> {
         {
             type Result = ControlFlow<()>;
 
-            fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
+            fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
                 &mut self,
                 t: &Binder<'tcx, T>,
             ) -> Self::Result {
@@ -168,7 +168,7 @@ impl LateBoundRegionsCollector {
 }
 
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for LateBoundRegionsCollector {
-    fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) {
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) {
         self.current_index.shift_in(1);
         t.super_visit_with(self);
         self.current_index.shift_out(1);
diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs
index cea77533178..47ed9e87244 100644
--- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs
+++ b/compiler/rustc_next_trait_solver/src/canonicalizer.rs
@@ -435,13 +435,13 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
             },
             ty::Placeholder(placeholder) => match self.canonicalize_mode {
                 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
-                    PlaceholderLike::new(placeholder.universe(), self.variables.len().into()),
+                    PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()),
                 ),
                 CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
             },
             ty::Param(_) => match self.canonicalize_mode {
                 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
-                    PlaceholderLike::new(ty::UniverseIndex::ROOT, self.variables.len().into()),
+                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
                 ),
                 CanonicalizeMode::Response { .. } => panic!("param ty in response: {t:?}"),
             },
@@ -594,7 +594,7 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz
             },
             ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
                 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
-                    PlaceholderLike::new(placeholder.universe(), self.variables.len().into()),
+                    PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()),
                 ),
                 CanonicalizeMode::Response { .. } => {
                     CanonicalVarKind::PlaceholderConst(placeholder)
@@ -602,7 +602,7 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz
             },
             ty::ConstKind::Param(_) => match self.canonicalize_mode {
                 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
-                    PlaceholderLike::new(ty::UniverseIndex::ROOT, self.variables.len().into()),
+                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
                 ),
                 CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"),
             },
diff --git a/compiler/rustc_next_trait_solver/src/lib.rs b/compiler/rustc_next_trait_solver/src/lib.rs
index 92cdc28a37b..77f098e6f26 100644
--- a/compiler/rustc_next_trait_solver/src/lib.rs
+++ b/compiler/rustc_next_trait_solver/src/lib.rs
@@ -12,5 +12,6 @@
 pub mod canonicalizer;
 pub mod coherence;
 pub mod delegate;
+pub mod placeholder;
 pub mod resolve;
 pub mod solve;
diff --git a/compiler/rustc_next_trait_solver/src/placeholder.rs b/compiler/rustc_next_trait_solver/src/placeholder.rs
new file mode 100644
index 00000000000..c88fb8defae
--- /dev/null
+++ b/compiler/rustc_next_trait_solver/src/placeholder.rs
@@ -0,0 +1,158 @@
+use core::panic;
+
+use rustc_type_ir::data_structures::IndexMap;
+use rustc_type_ir::inherent::*;
+use rustc_type_ir::{
+    self as ty, InferCtxtLike, Interner, TypeFoldable, TypeFolder, TypeSuperFoldable,
+    TypeVisitableExt,
+};
+
+pub struct BoundVarReplacer<'a, Infcx, I = <Infcx as InferCtxtLike>::Interner>
+where
+    Infcx: InferCtxtLike<Interner = I>,
+    I: Interner,
+{
+    infcx: &'a Infcx,
+    // These three maps track the bound variable that were replaced by placeholders. It might be
+    // nice to remove these since we already have the `kind` in the placeholder; we really just need
+    // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
+    mapped_regions: IndexMap<I::PlaceholderRegion, I::BoundRegion>,
+    mapped_types: IndexMap<I::PlaceholderTy, I::BoundTy>,
+    mapped_consts: IndexMap<I::PlaceholderConst, I::BoundConst>,
+    // The current depth relative to *this* folding, *not* the entire normalization. In other words,
+    // the depth of binders we've passed here.
+    current_index: ty::DebruijnIndex,
+    // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
+    // we don't actually create a universe until we see a bound var we have to replace.
+    universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
+}
+
+impl<'a, Infcx, I> BoundVarReplacer<'a, Infcx, I>
+where
+    Infcx: InferCtxtLike<Interner = I>,
+    I: Interner,
+{
+    /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
+    /// use a binding level above `universe_indices.len()`, we fail.
+    pub fn replace_bound_vars<T: TypeFoldable<I>>(
+        infcx: &'a Infcx,
+        universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
+        value: T,
+    ) -> (
+        T,
+        IndexMap<I::PlaceholderRegion, I::BoundRegion>,
+        IndexMap<I::PlaceholderTy, I::BoundTy>,
+        IndexMap<I::PlaceholderConst, I::BoundConst>,
+    ) {
+        let mut replacer = BoundVarReplacer {
+            infcx,
+            mapped_regions: Default::default(),
+            mapped_types: Default::default(),
+            mapped_consts: Default::default(),
+            current_index: ty::INNERMOST,
+            universe_indices,
+        };
+
+        let value = value.fold_with(&mut replacer);
+
+        (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
+    }
+
+    fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
+        let infcx = self.infcx;
+        let index =
+            self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
+        let universe = self.universe_indices[index].unwrap_or_else(|| {
+            for i in self.universe_indices.iter_mut().take(index + 1) {
+                *i = i.or_else(|| Some(infcx.create_next_universe()))
+            }
+            self.universe_indices[index].unwrap()
+        });
+        universe
+    }
+}
+
+impl<Infcx, I> TypeFolder<I> for BoundVarReplacer<'_, Infcx, I>
+where
+    Infcx: InferCtxtLike<Interner = I>,
+    I: Interner,
+{
+    fn cx(&self) -> I {
+        self.infcx.cx()
+    }
+
+    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
+        self.current_index.shift_in(1);
+        let t = t.super_fold_with(self);
+        self.current_index.shift_out(1);
+        t
+    }
+
+    fn fold_region(&mut self, r: I::Region) -> I::Region {
+        match r.kind() {
+            ty::ReBound(debruijn, _)
+                if debruijn.as_usize()
+                    >= self.current_index.as_usize() + self.universe_indices.len() =>
+            {
+                panic!(
+                    "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}",
+                    self.universe_indices
+                );
+            }
+            ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
+                let universe = self.universe_for(debruijn);
+                let p = PlaceholderLike::new(universe, br);
+                self.mapped_regions.insert(p, br);
+                Region::new_placeholder(self.cx(), p)
+            }
+            _ => r,
+        }
+    }
+
+    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
+        match t.kind() {
+            ty::Bound(debruijn, _)
+                if debruijn.as_usize() + 1
+                    > self.current_index.as_usize() + self.universe_indices.len() =>
+            {
+                panic!(
+                    "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}",
+                    self.universe_indices
+                );
+            }
+            ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
+                let universe = self.universe_for(debruijn);
+                let p = PlaceholderLike::new(universe, bound_ty);
+                self.mapped_types.insert(p, bound_ty);
+                Ty::new_placeholder(self.cx(), p)
+            }
+            _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
+            _ => t,
+        }
+    }
+
+    fn fold_const(&mut self, ct: I::Const) -> I::Const {
+        match ct.kind() {
+            ty::ConstKind::Bound(debruijn, _)
+                if debruijn.as_usize() + 1
+                    > self.current_index.as_usize() + self.universe_indices.len() =>
+            {
+                panic!(
+                    "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}",
+                    self.universe_indices
+                );
+            }
+            ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => {
+                let universe = self.universe_for(debruijn);
+                let p = PlaceholderLike::new(universe, bound_const);
+                self.mapped_consts.insert(p, bound_const);
+                Const::new_placeholder(self.cx(), p)
+            }
+            _ => ct.super_fold_with(self),
+        }
+    }
+
+    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
+        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
+    }
+}
diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
index 542e212e1bf..0c267feefbe 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
@@ -1014,7 +1014,11 @@ where
             return Ok(CandidateSource::ParamEnv(ParamEnvSource::NonGlobal));
         }
 
-        match assumption.visit_with(&mut FindParamInClause { ecx: self, param_env }) {
+        match assumption.visit_with(&mut FindParamInClause {
+            ecx: self,
+            param_env,
+            universes: vec![],
+        }) {
             ControlFlow::Break(Err(NoSolution)) => Err(NoSolution),
             ControlFlow::Break(Ok(())) => Ok(CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)),
             ControlFlow::Continue(()) => Ok(CandidateSource::ParamEnv(ParamEnvSource::Global)),
@@ -1025,6 +1029,7 @@ where
 struct FindParamInClause<'a, 'b, D: SolverDelegate<Interner = I>, I: Interner> {
     ecx: &'a mut EvalCtxt<'b, D>,
     param_env: I::ParamEnv,
+    universes: Vec<Option<ty::UniverseIndex>>,
 }
 
 impl<D, I> TypeVisitor<I> for FindParamInClause<'_, '_, D, I>
@@ -1034,31 +1039,42 @@ where
 {
     type Result = ControlFlow<Result<(), NoSolution>>;
 
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
-        self.ecx.enter_forall(t.clone(), |ecx, v| {
-            v.visit_with(&mut FindParamInClause { ecx, param_env: self.param_env })
-        })
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
+        self.universes.push(None);
+        t.super_visit_with(self)?;
+        self.universes.pop();
+        ControlFlow::Continue(())
     }
 
     fn visit_ty(&mut self, ty: I::Ty) -> Self::Result {
+        let ty = self.ecx.replace_bound_vars(ty, &mut self.universes);
         let Ok(ty) = self.ecx.structurally_normalize_ty(self.param_env, ty) else {
             return ControlFlow::Break(Err(NoSolution));
         };
 
-        if let ty::Placeholder(_) = ty.kind() {
-            ControlFlow::Break(Ok(()))
+        if let ty::Placeholder(p) = ty.kind() {
+            if p.universe() == ty::UniverseIndex::ROOT {
+                ControlFlow::Break(Ok(()))
+            } else {
+                ControlFlow::Continue(())
+            }
         } else {
             ty.super_visit_with(self)
         }
     }
 
     fn visit_const(&mut self, ct: I::Const) -> Self::Result {
+        let ct = self.ecx.replace_bound_vars(ct, &mut self.universes);
         let Ok(ct) = self.ecx.structurally_normalize_const(self.param_env, ct) else {
             return ControlFlow::Break(Err(NoSolution));
         };
 
-        if let ty::ConstKind::Placeholder(_) = ct.kind() {
-            ControlFlow::Break(Ok(()))
+        if let ty::ConstKind::Placeholder(p) = ct.kind() {
+            if p.universe() == ty::UniverseIndex::ROOT {
+                ControlFlow::Break(Ok(()))
+            } else {
+                ControlFlow::Continue(())
+            }
         } else {
             ct.super_visit_with(self)
         }
@@ -1066,10 +1082,17 @@ where
 
     fn visit_region(&mut self, r: I::Region) -> Self::Result {
         match self.ecx.eager_resolve_region(r).kind() {
-            ty::ReStatic | ty::ReError(_) => ControlFlow::Continue(()),
-            ty::ReVar(_) | ty::RePlaceholder(_) => ControlFlow::Break(Ok(())),
-            ty::ReErased | ty::ReEarlyParam(_) | ty::ReLateParam(_) | ty::ReBound(..) => {
-                unreachable!()
+            ty::ReStatic | ty::ReError(_) | ty::ReBound(..) => ControlFlow::Continue(()),
+            ty::RePlaceholder(p) => {
+                if p.universe() == ty::UniverseIndex::ROOT {
+                    ControlFlow::Break(Ok(()))
+                } else {
+                    ControlFlow::Continue(())
+                }
+            }
+            ty::ReVar(_) => ControlFlow::Break(Ok(())),
+            ty::ReErased | ty::ReEarlyParam(_) | ty::ReLateParam(_) => {
+                unreachable!("unexpected region in param-env clause")
             }
         }
     }
diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
index 345ece20b7e..7ead0a6d6b7 100644
--- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
@@ -19,6 +19,7 @@ use tracing::{debug, instrument, trace};
 use super::has_only_region_constraints;
 use crate::coherence;
 use crate::delegate::SolverDelegate;
+use crate::placeholder::BoundVarReplacer;
 use crate::solve::inspect::{self, ProofTreeBuilder};
 use crate::solve::search_graph::SearchGraph;
 use crate::solve::{
@@ -1232,6 +1233,14 @@ where
     ) -> Result<Certainty, NoSolution> {
         self.delegate.is_transmutable(dst, src, assume)
     }
+
+    pub(super) fn replace_bound_vars<T: TypeFoldable<I>>(
+        &self,
+        t: T,
+        universes: &mut Vec<Option<ty::UniverseIndex>>,
+    ) -> T {
+        BoundVarReplacer::replace_bound_vars(&**self.delegate, universes, t).0
+    }
 }
 
 /// Eagerly replace aliases with inference variables, emitting `AliasRelate`
diff --git a/compiler/rustc_parse/messages.ftl b/compiler/rustc_parse/messages.ftl
index 1f221b4bf78..f6e0b08b140 100644
--- a/compiler/rustc_parse/messages.ftl
+++ b/compiler/rustc_parse/messages.ftl
@@ -299,10 +299,12 @@ parse_float_literal_unsupported_base = {$base} float literal is not supported
 parse_fn_pointer_cannot_be_async = an `fn` pointer type cannot be `async`
     .label = `async` because of this
     .suggestion = remove the `async` qualifier
+    .note = allowed qualifiers are: `unsafe` and `extern`
 
 parse_fn_pointer_cannot_be_const = an `fn` pointer type cannot be `const`
     .label = `const` because of this
     .suggestion = remove the `const` qualifier
+    .note = allowed qualifiers are: `unsafe` and `extern`
 
 parse_fn_ptr_with_generics = function pointer types may not have generic parameters
     .suggestion = consider moving the lifetime {$arity ->
diff --git a/compiler/rustc_parse/src/errors.rs b/compiler/rustc_parse/src/errors.rs
index 2dba568a258..0f0c5434800 100644
--- a/compiler/rustc_parse/src/errors.rs
+++ b/compiler/rustc_parse/src/errors.rs
@@ -2938,22 +2938,22 @@ pub(crate) struct DynAfterMut {
 
 #[derive(Diagnostic)]
 #[diag(parse_fn_pointer_cannot_be_const)]
+#[note]
 pub(crate) struct FnPointerCannotBeConst {
     #[primary_span]
-    pub span: Span,
     #[label]
-    pub qualifier: Span,
+    pub span: Span,
     #[suggestion(code = "", applicability = "maybe-incorrect", style = "verbose")]
     pub suggestion: Span,
 }
 
 #[derive(Diagnostic)]
 #[diag(parse_fn_pointer_cannot_be_async)]
+#[note]
 pub(crate) struct FnPointerCannotBeAsync {
     #[primary_span]
-    pub span: Span,
     #[label]
-    pub qualifier: Span,
+    pub span: Span,
     #[suggestion(code = "", applicability = "maybe-incorrect", style = "verbose")]
     pub suggestion: Span,
 }
diff --git a/compiler/rustc_parse/src/parser/item.rs b/compiler/rustc_parse/src/parser/item.rs
index a325c2a57ab..658ed4bd41c 100644
--- a/compiler/rustc_parse/src/parser/item.rs
+++ b/compiler/rustc_parse/src/parser/item.rs
@@ -23,7 +23,7 @@ use super::{
     AttrWrapper, ExpKeywordPair, ExpTokenPair, FollowedByType, ForceCollect, Parser, PathStyle,
     Recovered, Trailing, UsePreAttrPos,
 };
-use crate::errors::{self, MacroExpandsToAdtField};
+use crate::errors::{self, FnPointerCannotBeAsync, FnPointerCannotBeConst, MacroExpandsToAdtField};
 use crate::{exp, fluent_generated as fluent};
 
 impl<'a> Parser<'a> {
@@ -2402,7 +2402,7 @@ impl<'a> Parser<'a> {
         case: Case,
     ) -> PResult<'a, (Ident, FnSig, Generics, Option<P<FnContract>>, Option<P<Block>>)> {
         let fn_span = self.token.span;
-        let header = self.parse_fn_front_matter(vis, case)?; // `const ... fn`
+        let header = self.parse_fn_front_matter(vis, case, FrontMatterParsingMode::Function)?; // `const ... fn`
         let ident = self.parse_ident()?; // `foo`
         let mut generics = self.parse_generics()?; // `<'a, T, ...>`
         let decl = match self.parse_fn_decl(
@@ -2658,16 +2658,37 @@ impl<'a> Parser<'a> {
     ///
     /// `vis` represents the visibility that was already parsed, if any. Use
     /// `Visibility::Inherited` when no visibility is known.
+    ///
+    /// If `parsing_mode` is `FrontMatterParsingMode::FunctionPtrType`, we error on `const` and `async` qualifiers,
+    /// which are not allowed in function pointer types.
     pub(super) fn parse_fn_front_matter(
         &mut self,
         orig_vis: &Visibility,
         case: Case,
+        parsing_mode: FrontMatterParsingMode,
     ) -> PResult<'a, FnHeader> {
         let sp_start = self.token.span;
         let constness = self.parse_constness(case);
+        if parsing_mode == FrontMatterParsingMode::FunctionPtrType
+            && let Const::Yes(const_span) = constness
+        {
+            self.dcx().emit_err(FnPointerCannotBeConst {
+                span: const_span,
+                suggestion: const_span.until(self.token.span),
+            });
+        }
 
         let async_start_sp = self.token.span;
         let coroutine_kind = self.parse_coroutine_kind(case);
+        if parsing_mode == FrontMatterParsingMode::FunctionPtrType
+            && let Some(ast::CoroutineKind::Async { span: async_span, .. }) = coroutine_kind
+        {
+            self.dcx().emit_err(FnPointerCannotBeAsync {
+                span: async_span,
+                suggestion: async_span.until(self.token.span),
+            });
+        }
+        // FIXME(gen_blocks): emit a similar error for `gen fn()`
 
         let unsafe_start_sp = self.token.span;
         let safety = self.parse_safety(case);
@@ -2703,6 +2724,11 @@ impl<'a> Parser<'a> {
                     enum WrongKw {
                         Duplicated(Span),
                         Misplaced(Span),
+                        /// `MisplacedDisallowedQualifier` is only used instead of `Misplaced`,
+                        /// when the misplaced keyword is disallowed by the current `FrontMatterParsingMode`.
+                        /// In this case, we avoid generating the suggestion to swap around the keywords,
+                        /// as we already generated a suggestion to remove the keyword earlier.
+                        MisplacedDisallowedQualifier,
                     }
 
                     // We may be able to recover
@@ -2716,7 +2742,21 @@ impl<'a> Parser<'a> {
                             Const::Yes(sp) => Some(WrongKw::Duplicated(sp)),
                             Const::No => {
                                 recover_constness = Const::Yes(self.token.span);
-                                Some(WrongKw::Misplaced(async_start_sp))
+                                match parsing_mode {
+                                    FrontMatterParsingMode::Function => {
+                                        Some(WrongKw::Misplaced(async_start_sp))
+                                    }
+                                    FrontMatterParsingMode::FunctionPtrType => {
+                                        self.dcx().emit_err(FnPointerCannotBeConst {
+                                            span: self.token.span,
+                                            suggestion: self
+                                                .token
+                                                .span
+                                                .with_lo(self.prev_token.span.hi()),
+                                        });
+                                        Some(WrongKw::MisplacedDisallowedQualifier)
+                                    }
+                                }
                             }
                         }
                     } else if self.check_keyword(exp!(Async)) {
@@ -2742,7 +2782,21 @@ impl<'a> Parser<'a> {
                                     closure_id: DUMMY_NODE_ID,
                                     return_impl_trait_id: DUMMY_NODE_ID,
                                 });
-                                Some(WrongKw::Misplaced(unsafe_start_sp))
+                                match parsing_mode {
+                                    FrontMatterParsingMode::Function => {
+                                        Some(WrongKw::Misplaced(async_start_sp))
+                                    }
+                                    FrontMatterParsingMode::FunctionPtrType => {
+                                        self.dcx().emit_err(FnPointerCannotBeAsync {
+                                            span: self.token.span,
+                                            suggestion: self
+                                                .token
+                                                .span
+                                                .with_lo(self.prev_token.span.hi()),
+                                        });
+                                        Some(WrongKw::MisplacedDisallowedQualifier)
+                                    }
+                                }
                             }
                         }
                     } else if self.check_keyword(exp!(Unsafe)) {
@@ -2840,14 +2894,20 @@ impl<'a> Parser<'a> {
 
                     // FIXME(gen_blocks): add keyword recovery logic for genness
 
-                    if wrong_kw.is_some()
+                    if let Some(wrong_kw) = wrong_kw
                         && self.may_recover()
                         && self.look_ahead(1, |tok| tok.is_keyword_case(kw::Fn, case))
                     {
                         // Advance past the misplaced keyword and `fn`
                         self.bump();
                         self.bump();
-                        err.emit();
+                        // When we recover from a `MisplacedDisallowedQualifier`, we already emitted an error for the disallowed qualifier
+                        // So we don't emit another error that the qualifier is unexpected.
+                        if matches!(wrong_kw, WrongKw::MisplacedDisallowedQualifier) {
+                            err.cancel();
+                        } else {
+                            err.emit();
+                        }
                         return Ok(FnHeader {
                             constness: recover_constness,
                             safety: recover_safety,
@@ -3194,3 +3254,12 @@ enum IsMacroRulesItem {
     Yes { has_bang: bool },
     No,
 }
+
+#[derive(Copy, Clone, PartialEq, Eq)]
+pub(super) enum FrontMatterParsingMode {
+    /// Parse the front matter of a function declaration
+    Function,
+    /// Parse the front matter of a function pointet type.
+    /// For function pointer types, the `const` and `async` keywords are not permitted.
+    FunctionPtrType,
+}
diff --git a/compiler/rustc_parse/src/parser/ty.rs b/compiler/rustc_parse/src/parser/ty.rs
index 9ddfc179e9b..620a34044d1 100644
--- a/compiler/rustc_parse/src/parser/ty.rs
+++ b/compiler/rustc_parse/src/parser/ty.rs
@@ -15,10 +15,11 @@ use thin_vec::{ThinVec, thin_vec};
 use super::{Parser, PathStyle, SeqSep, TokenType, Trailing};
 use crate::errors::{
     self, DynAfterMut, ExpectedFnPathFoundFnKeyword, ExpectedMutOrConstInRawPointerType,
-    FnPointerCannotBeAsync, FnPointerCannotBeConst, FnPtrWithGenerics, FnPtrWithGenericsSugg,
-    HelpUseLatestEdition, InvalidDynKeyword, LifetimeAfterMut, NeedPlusAfterTraitObjectLifetime,
-    NestedCVariadicType, ReturnTypesUseThinArrow,
+    FnPtrWithGenerics, FnPtrWithGenericsSugg, HelpUseLatestEdition, InvalidDynKeyword,
+    LifetimeAfterMut, NeedPlusAfterTraitObjectLifetime, NestedCVariadicType,
+    ReturnTypesUseThinArrow,
 };
+use crate::parser::item::FrontMatterParsingMode;
 use crate::{exp, maybe_recover_from_interpolated_ty_qpath};
 
 /// Signals whether parsing a type should allow `+`.
@@ -669,62 +670,16 @@ impl<'a> Parser<'a> {
             tokens: None,
         };
         let span_start = self.token.span;
-        let ast::FnHeader { ext, safety, constness, coroutine_kind } =
-            self.parse_fn_front_matter(&inherited_vis, Case::Sensitive)?;
-        let fn_start_lo = self.prev_token.span.lo();
+        let ast::FnHeader { ext, safety, .. } = self.parse_fn_front_matter(
+            &inherited_vis,
+            Case::Sensitive,
+            FrontMatterParsingMode::FunctionPtrType,
+        )?;
         if self.may_recover() && self.token == TokenKind::Lt {
             self.recover_fn_ptr_with_generics(lo, &mut params, param_insertion_point)?;
         }
         let decl = self.parse_fn_decl(|_| false, AllowPlus::No, recover_return_sign)?;
-        let whole_span = lo.to(self.prev_token.span);
-
-        // Order/parsing of "front matter" follows:
-        // `<constness> <coroutine_kind> <safety> <extern> fn()`
-        //  ^           ^                ^        ^        ^
-        //  |           |                |        |        fn_start_lo
-        //  |           |                |        ext_sp.lo
-        //  |           |                safety_sp.lo
-        //  |           coroutine_sp.lo
-        //  const_sp.lo
-        if let ast::Const::Yes(const_span) = constness {
-            let next_token_lo = if let Some(
-                ast::CoroutineKind::Async { span, .. }
-                | ast::CoroutineKind::Gen { span, .. }
-                | ast::CoroutineKind::AsyncGen { span, .. },
-            ) = coroutine_kind
-            {
-                span.lo()
-            } else if let ast::Safety::Unsafe(span) | ast::Safety::Safe(span) = safety {
-                span.lo()
-            } else if let ast::Extern::Implicit(span) | ast::Extern::Explicit(_, span) = ext {
-                span.lo()
-            } else {
-                fn_start_lo
-            };
-            let sugg_span = const_span.with_hi(next_token_lo);
-            self.dcx().emit_err(FnPointerCannotBeConst {
-                span: whole_span,
-                qualifier: const_span,
-                suggestion: sugg_span,
-            });
-        }
-        if let Some(ast::CoroutineKind::Async { span: async_span, .. }) = coroutine_kind {
-            let next_token_lo = if let ast::Safety::Unsafe(span) | ast::Safety::Safe(span) = safety
-            {
-                span.lo()
-            } else if let ast::Extern::Implicit(span) | ast::Extern::Explicit(_, span) = ext {
-                span.lo()
-            } else {
-                fn_start_lo
-            };
-            let sugg_span = async_span.with_hi(next_token_lo);
-            self.dcx().emit_err(FnPointerCannotBeAsync {
-                span: whole_span,
-                qualifier: async_span,
-                suggestion: sugg_span,
-            });
-        }
-        // FIXME(gen_blocks): emit a similar error for `gen fn()`
+
         let decl_span = span_start.to(self.prev_token.span);
         Ok(TyKind::BareFn(P(BareFnTy { ext, safety, generic_params: params, decl, decl_span })))
     }
diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
index eb34cb10c68..a54eb80fedc 100644
--- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
@@ -9,7 +9,7 @@ use rustc_macros::extension;
 pub use rustc_middle::traits::query::NormalizationResult;
 use rustc_middle::ty::{
     self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, TypeSuperVisitable,
-    TypeVisitableExt, TypeVisitor, TypingMode,
+    TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode,
 };
 use rustc_span::DUMMY_SP;
 use tracing::{debug, info, instrument};
@@ -127,7 +127,7 @@ struct MaxEscapingBoundVarVisitor {
 }
 
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
-    fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
         self.outer_index.shift_in(1);
         t.super_visit_with(self);
         self.outer_index.shift_out(1);
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 3a2f9e8ca17..1b9b68fa980 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -1919,12 +1919,23 @@ impl<'tcx> SelectionContext<'_, 'tcx> {
         // impl `impl<T: ?Sized> Any for T { .. }`. This really shouldn't exist but is
         // necessary due to #57893. We again arbitrarily prefer the applicable candidate
         // with the lowest index.
+        //
+        // We do not want to use these impls to guide inference in case a user-written impl
+        // may also apply.
         let object_bound = candidates
             .iter()
             .filter_map(|c| if let ObjectCandidate(i) = c.candidate { Some(i) } else { None })
             .try_reduce(|c1, c2| if has_non_region_infer { None } else { Some(c1.min(c2)) });
         match object_bound {
-            Some(Some(index)) => return Some(ObjectCandidate(index)),
+            Some(Some(index)) => {
+                return if has_non_region_infer
+                    && candidates.iter().any(|c| matches!(c.candidate, ImplCandidate(_)))
+                {
+                    None
+                } else {
+                    Some(ObjectCandidate(index))
+                };
+            }
             Some(None) => {}
             None => return None,
         }
diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs
index 035fd38c48a..0723aebd5d2 100644
--- a/compiler/rustc_trait_selection/src/traits/util.rs
+++ b/compiler/rustc_trait_selection/src/traits/util.rs
@@ -1,4 +1,4 @@
-use std::collections::{BTreeMap, VecDeque};
+use std::collections::VecDeque;
 
 use rustc_data_structures::fx::{FxHashSet, FxIndexMap};
 use rustc_hir::LangItem;
@@ -9,6 +9,7 @@ use rustc_middle::bug;
 use rustc_middle::ty::{
     self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
 };
+pub use rustc_next_trait_solver::placeholder::BoundVarReplacer;
 use rustc_span::Span;
 use smallvec::{SmallVec, smallvec};
 use tracing::debug;
@@ -212,158 +213,12 @@ pub fn with_replaced_escaping_bound_vars<
     }
 }
 
-pub struct BoundVarReplacer<'a, 'tcx> {
-    infcx: &'a InferCtxt<'tcx>,
-    // These three maps track the bound variable that were replaced by placeholders. It might be
-    // nice to remove these since we already have the `kind` in the placeholder; we really just need
-    // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
-    mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
-    mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
-    mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
-    // The current depth relative to *this* folding, *not* the entire normalization. In other words,
-    // the depth of binders we've passed here.
-    current_index: ty::DebruijnIndex,
-    // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
-    // we don't actually create a universe until we see a bound var we have to replace.
-    universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
-}
-
-impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> {
-    /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
-    /// use a binding level above `universe_indices.len()`, we fail.
-    pub fn replace_bound_vars<T: TypeFoldable<TyCtxt<'tcx>>>(
-        infcx: &'a InferCtxt<'tcx>,
-        universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
-        value: T,
-    ) -> (
-        T,
-        FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
-        FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
-        BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
-    ) {
-        let mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion> =
-            FxIndexMap::default();
-        let mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy> = FxIndexMap::default();
-        let mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar> = BTreeMap::new();
-
-        let mut replacer = BoundVarReplacer {
-            infcx,
-            mapped_regions,
-            mapped_types,
-            mapped_consts,
-            current_index: ty::INNERMOST,
-            universe_indices,
-        };
-
-        let value = value.fold_with(&mut replacer);
-
-        (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
-    }
-
-    fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
-        let infcx = self.infcx;
-        let index =
-            self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
-        let universe = self.universe_indices[index].unwrap_or_else(|| {
-            for i in self.universe_indices.iter_mut().take(index + 1) {
-                *i = i.or_else(|| Some(infcx.create_next_universe()))
-            }
-            self.universe_indices[index].unwrap()
-        });
-        universe
-    }
-}
-
-impl<'tcx> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'_, 'tcx> {
-    fn cx(&self) -> TyCtxt<'tcx> {
-        self.infcx.tcx
-    }
-
-    fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
-        &mut self,
-        t: ty::Binder<'tcx, T>,
-    ) -> ty::Binder<'tcx, T> {
-        self.current_index.shift_in(1);
-        let t = t.super_fold_with(self);
-        self.current_index.shift_out(1);
-        t
-    }
-
-    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
-        match r.kind() {
-            ty::ReBound(debruijn, _)
-                if debruijn.as_usize()
-                    >= self.current_index.as_usize() + self.universe_indices.len() =>
-            {
-                bug!(
-                    "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}",
-                    self.universe_indices
-                );
-            }
-            ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
-                let universe = self.universe_for(debruijn);
-                let p = ty::PlaceholderRegion { universe, bound: br };
-                self.mapped_regions.insert(p, br);
-                ty::Region::new_placeholder(self.infcx.tcx, p)
-            }
-            _ => r,
-        }
-    }
-
-    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
-        match *t.kind() {
-            ty::Bound(debruijn, _)
-                if debruijn.as_usize() + 1
-                    > self.current_index.as_usize() + self.universe_indices.len() =>
-            {
-                bug!(
-                    "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}",
-                    self.universe_indices
-                );
-            }
-            ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
-                let universe = self.universe_for(debruijn);
-                let p = ty::PlaceholderType { universe, bound: bound_ty };
-                self.mapped_types.insert(p, bound_ty);
-                Ty::new_placeholder(self.infcx.tcx, p)
-            }
-            _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
-            _ => t,
-        }
-    }
-
-    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
-        match ct.kind() {
-            ty::ConstKind::Bound(debruijn, _)
-                if debruijn.as_usize() + 1
-                    > self.current_index.as_usize() + self.universe_indices.len() =>
-            {
-                bug!(
-                    "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}",
-                    self.universe_indices
-                );
-            }
-            ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => {
-                let universe = self.universe_for(debruijn);
-                let p = ty::PlaceholderConst { universe, bound: bound_const };
-                self.mapped_consts.insert(p, bound_const);
-                ty::Const::new_placeholder(self.infcx.tcx, p)
-            }
-            _ => ct.super_fold_with(self),
-        }
-    }
-
-    fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
-        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
-    }
-}
-
 /// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
 pub struct PlaceholderReplacer<'a, 'tcx> {
     infcx: &'a InferCtxt<'tcx>,
     mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
     mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
-    mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
+    mapped_consts: FxIndexMap<ty::PlaceholderConst, ty::BoundVar>,
     universe_indices: &'a [Option<ty::UniverseIndex>],
     current_index: ty::DebruijnIndex,
 }
@@ -373,7 +228,7 @@ impl<'a, 'tcx> PlaceholderReplacer<'a, 'tcx> {
         infcx: &'a InferCtxt<'tcx>,
         mapped_regions: FxIndexMap<ty::PlaceholderRegion, ty::BoundRegion>,
         mapped_types: FxIndexMap<ty::PlaceholderType, ty::BoundTy>,
-        mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>,
+        mapped_consts: FxIndexMap<ty::PlaceholderConst, ty::BoundVar>,
         universe_indices: &'a [Option<ty::UniverseIndex>],
         value: T,
     ) -> T {
diff --git a/compiler/rustc_ty_utils/src/ty.rs b/compiler/rustc_ty_utils/src/ty.rs
index 79ac622df32..11becea998c 100644
--- a/compiler/rustc_ty_utils/src/ty.rs
+++ b/compiler/rustc_ty_utils/src/ty.rs
@@ -7,8 +7,7 @@ use rustc_infer::infer::TyCtxtInferExt;
 use rustc_middle::bug;
 use rustc_middle::query::Providers;
 use rustc_middle::ty::{
-    self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitor, Upcast,
-    fold_regions,
+    self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, Upcast, fold_regions,
 };
 use rustc_span::DUMMY_SP;
 use rustc_span::def_id::{CRATE_DEF_ID, DefId, LocalDefId};
@@ -186,7 +185,7 @@ struct ImplTraitInTraitFinder<'a, 'tcx> {
 }
 
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ImplTraitInTraitFinder<'_, 'tcx> {
-    fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, binder: &ty::Binder<'tcx, T>) {
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, binder: &ty::Binder<'tcx, T>) {
         self.depth.shift_in(1);
         binder.super_visit_with(self);
         self.depth.shift_out(1);
diff --git a/compiler/rustc_type_ir/Cargo.toml b/compiler/rustc_type_ir/Cargo.toml
index 83d3d78298e..4bd7bfe79be 100644
--- a/compiler/rustc_type_ir/Cargo.toml
+++ b/compiler/rustc_type_ir/Cargo.toml
@@ -9,7 +9,7 @@ bitflags = "2.4.1"
 derive-where = "1.2.7"
 ena = "0.14.3"
 indexmap = "2.0.0"
-rustc-hash = "1.1.0"
+rustc-hash = "2.0.0"
 rustc_ast_ir = { path = "../rustc_ast_ir", default-features = false }
 rustc_data_structures = { path = "../rustc_data_structures", optional = true }
 rustc_index = { path = "../rustc_index", default-features = false }
diff --git a/compiler/rustc_type_ir/src/binder.rs b/compiler/rustc_type_ir/src/binder.rs
index 55c0a3bba9f..927a2ce84ea 100644
--- a/compiler/rustc_type_ir/src/binder.rs
+++ b/compiler/rustc_type_ir/src/binder.rs
@@ -128,7 +128,7 @@ impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Binder<I, T> {
     }
 }
 
-impl<I: Interner, T: TypeFoldable<I>> TypeVisitable<I> for Binder<I, T> {
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Binder<I, T> {
     fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
         visitor.visit_binder(self)
     }
@@ -147,7 +147,7 @@ impl<I: Interner, T: TypeFoldable<I>> TypeSuperFoldable<I> for Binder<I, T> {
     }
 }
 
-impl<I: Interner, T: TypeFoldable<I>> TypeSuperVisitable<I> for Binder<I, T> {
+impl<I: Interner, T: TypeVisitable<I>> TypeSuperVisitable<I> for Binder<I, T> {
     fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
         self.as_ref().skip_binder().visit_with(visitor)
     }
@@ -292,7 +292,7 @@ impl<I: Interner> ValidateBoundVars<I> {
 impl<I: Interner> TypeVisitor<I> for ValidateBoundVars<I> {
     type Result = ControlFlow<()>;
 
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &Binder<I, T>) -> Self::Result {
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &Binder<I, T>) -> Self::Result {
         self.binder_index.shift_in(1);
         let result = t.super_visit_with(self);
         self.binder_index.shift_out(1);
diff --git a/compiler/rustc_type_ir/src/inherent.rs b/compiler/rustc_type_ir/src/inherent.rs
index fa88bcb891a..436ab9f80b6 100644
--- a/compiler/rustc_type_ir/src/inherent.rs
+++ b/compiler/rustc_type_ir/src/inherent.rs
@@ -228,6 +228,8 @@ pub trait Region<I: Interner<Region = Self>>:
 
     fn new_static(interner: I) -> Self;
 
+    fn new_placeholder(interner: I, var: I::PlaceholderRegion) -> Self;
+
     fn is_bound(self) -> bool {
         matches!(self.kind(), ty::ReBound(..))
     }
@@ -254,6 +256,8 @@ pub trait Const<I: Interner<Const = Self>>:
 
     fn new_anon_bound(interner: I, debruijn: ty::DebruijnIndex, var: ty::BoundVar) -> Self;
 
+    fn new_placeholder(interner: I, param: I::PlaceholderConst) -> Self;
+
     fn new_unevaluated(interner: I, uv: ty::UnevaluatedConst<I>) -> Self;
 
     fn new_expr(interner: I, expr: I::ExprConst) -> Self;
@@ -524,13 +528,14 @@ pub trait Clauses<I: Interner<Clauses = Self>>:
 }
 
 /// Common capabilities of placeholder kinds
-pub trait PlaceholderLike: Copy + Debug + Hash + Eq {
+pub trait PlaceholderLike<I: Interner>: Copy + Debug + Hash + Eq {
     fn universe(self) -> ty::UniverseIndex;
     fn var(self) -> ty::BoundVar;
 
+    type Bound: BoundVarLike<I>;
+    fn new(ui: ty::UniverseIndex, bound: Self::Bound) -> Self;
+    fn new_anon(ui: ty::UniverseIndex, var: ty::BoundVar) -> Self;
     fn with_updated_universe(self, ui: ty::UniverseIndex) -> Self;
-
-    fn new(ui: ty::UniverseIndex, var: ty::BoundVar) -> Self;
 }
 
 pub trait IntoKind {
@@ -539,13 +544,13 @@ pub trait IntoKind {
     fn kind(self) -> Self::Kind;
 }
 
-pub trait BoundVarLike<I: Interner> {
+pub trait BoundVarLike<I: Interner>: Copy + Debug + Hash + Eq {
     fn var(self) -> ty::BoundVar;
 
     fn assert_eq(self, var: I::BoundVarKind);
 }
 
-pub trait ParamLike {
+pub trait ParamLike: Copy + Debug + Hash + Eq {
     fn index(self) -> u32;
 }
 
diff --git a/compiler/rustc_type_ir/src/interner.rs b/compiler/rustc_type_ir/src/interner.rs
index cc0925b2c32..033d2579678 100644
--- a/compiler/rustc_type_ir/src/interner.rs
+++ b/compiler/rustc_type_ir/src/interner.rs
@@ -103,9 +103,9 @@ pub trait Interner:
     type Ty: Ty<Self>;
     type Tys: Tys<Self>;
     type FnInputTys: Copy + Debug + Hash + Eq + SliceLike<Item = Self::Ty> + TypeVisitable<Self>;
-    type ParamTy: Copy + Debug + Hash + Eq + ParamLike;
-    type BoundTy: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
-    type PlaceholderTy: PlaceholderLike;
+    type ParamTy: ParamLike;
+    type BoundTy: BoundVarLike<Self>;
+    type PlaceholderTy: PlaceholderLike<Self, Bound = Self::BoundTy>;
 
     // Things stored inside of tys
     type ErrorGuaranteed: Copy + Debug + Hash + Eq;
@@ -131,19 +131,19 @@ pub trait Interner:
 
     // Kinds of consts
     type Const: Const<Self>;
-    type PlaceholderConst: PlaceholderLike;
     type ParamConst: Copy + Debug + Hash + Eq + ParamLike;
-    type BoundConst: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
+    type BoundConst: BoundVarLike<Self>;
+    type PlaceholderConst: PlaceholderLike<Self, Bound = Self::BoundConst>;
     type ValueConst: ValueConst<Self>;
     type ExprConst: ExprConst<Self>;
     type ValTree: Copy + Debug + Hash + Eq;
 
     // Kinds of regions
     type Region: Region<Self>;
-    type EarlyParamRegion: Copy + Debug + Hash + Eq + ParamLike;
+    type EarlyParamRegion: ParamLike;
     type LateParamRegion: Copy + Debug + Hash + Eq;
-    type BoundRegion: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
-    type PlaceholderRegion: PlaceholderLike;
+    type BoundRegion: BoundVarLike<Self>;
+    type PlaceholderRegion: PlaceholderLike<Self, Bound = Self::BoundRegion>;
 
     // Predicates
     type ParamEnv: ParamEnv<Self>;
diff --git a/compiler/rustc_type_ir/src/search_graph/global_cache.rs b/compiler/rustc_type_ir/src/search_graph/global_cache.rs
index 0ce927b58bb..a2442660259 100644
--- a/compiler/rustc_type_ir/src/search_graph/global_cache.rs
+++ b/compiler/rustc_type_ir/src/search_graph/global_cache.rs
@@ -4,7 +4,7 @@ use super::{AvailableDepth, Cx, NestedGoals};
 use crate::data_structures::HashMap;
 
 struct Success<X: Cx> {
-    additional_depth: usize,
+    required_depth: usize,
     nested_goals: NestedGoals<X>,
     result: X::Tracked<X::Result>,
 }
@@ -28,7 +28,7 @@ struct CacheEntry<X: Cx> {
 #[derive_where(Debug; X: Cx)]
 pub(super) struct CacheData<'a, X: Cx> {
     pub(super) result: X::Result,
-    pub(super) additional_depth: usize,
+    pub(super) required_depth: usize,
     pub(super) encountered_overflow: bool,
     pub(super) nested_goals: &'a NestedGoals<X>,
 }
@@ -47,7 +47,7 @@ impl<X: Cx> GlobalCache<X> {
         origin_result: X::Result,
         dep_node: X::DepNodeIndex,
 
-        additional_depth: usize,
+        required_depth: usize,
         encountered_overflow: bool,
         nested_goals: NestedGoals<X>,
     ) {
@@ -55,13 +55,13 @@ impl<X: Cx> GlobalCache<X> {
         let entry = self.map.entry(input).or_default();
         if encountered_overflow {
             let with_overflow = WithOverflow { nested_goals, result };
-            let prev = entry.with_overflow.insert(additional_depth, with_overflow);
+            let prev = entry.with_overflow.insert(required_depth, with_overflow);
             if let Some(prev) = &prev {
                 assert!(cx.evaluation_is_concurrent());
                 assert_eq!(cx.get_tracked(&prev.result), origin_result);
             }
         } else {
-            let prev = entry.success.replace(Success { additional_depth, nested_goals, result });
+            let prev = entry.success.replace(Success { required_depth, nested_goals, result });
             if let Some(prev) = &prev {
                 assert!(cx.evaluation_is_concurrent());
                 assert_eq!(cx.get_tracked(&prev.result), origin_result);
@@ -81,13 +81,13 @@ impl<X: Cx> GlobalCache<X> {
         mut candidate_is_applicable: impl FnMut(&NestedGoals<X>) -> bool,
     ) -> Option<CacheData<'a, X>> {
         let entry = self.map.get(&input)?;
-        if let Some(Success { additional_depth, ref nested_goals, ref result }) = entry.success {
-            if available_depth.cache_entry_is_applicable(additional_depth)
+        if let Some(Success { required_depth, ref nested_goals, ref result }) = entry.success {
+            if available_depth.cache_entry_is_applicable(required_depth)
                 && candidate_is_applicable(nested_goals)
             {
                 return Some(CacheData {
                     result: cx.get_tracked(&result),
-                    additional_depth,
+                    required_depth,
                     encountered_overflow: false,
                     nested_goals,
                 });
@@ -101,7 +101,7 @@ impl<X: Cx> GlobalCache<X> {
             if candidate_is_applicable(nested_goals) {
                 return Some(CacheData {
                     result: cx.get_tracked(result),
-                    additional_depth,
+                    required_depth: additional_depth,
                     encountered_overflow: true,
                     nested_goals,
                 });
diff --git a/compiler/rustc_type_ir/src/search_graph/mod.rs b/compiler/rustc_type_ir/src/search_graph/mod.rs
index 1acd5d5c2af..f0eb96b47b1 100644
--- a/compiler/rustc_type_ir/src/search_graph/mod.rs
+++ b/compiler/rustc_type_ir/src/search_graph/mod.rs
@@ -19,13 +19,14 @@ use std::hash::Hash;
 use std::marker::PhantomData;
 
 use derive_where::derive_where;
-use rustc_index::{Idx, IndexVec};
 #[cfg(feature = "nightly")]
 use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
 use tracing::debug;
 
 use crate::data_structures::HashMap;
 
+mod stack;
+use stack::{Stack, StackDepth, StackEntry};
 mod global_cache;
 use global_cache::CacheData;
 pub use global_cache::GlobalCache;
@@ -225,9 +226,9 @@ impl AvailableDepth {
     /// in case there is exponential blowup.
     fn allowed_depth_for_nested<D: Delegate>(
         root_depth: AvailableDepth,
-        stack: &IndexVec<StackDepth, StackEntry<D::Cx>>,
+        stack: &Stack<D::Cx>,
     ) -> Option<AvailableDepth> {
-        if let Some(last) = stack.raw.last() {
+        if let Some(last) = stack.last() {
             if last.available_depth.0 == 0 {
                 return None;
             }
@@ -433,50 +434,6 @@ impl<X: Cx> NestedGoals<X> {
     }
 }
 
-rustc_index::newtype_index! {
-    #[orderable]
-    #[gate_rustc_only]
-    pub struct StackDepth {}
-}
-
-/// Stack entries of the evaluation stack. Its fields tend to be lazily
-/// when popping a child goal or completely immutable.
-#[derive_where(Debug; X: Cx)]
-struct StackEntry<X: Cx> {
-    input: X::Input,
-
-    /// Whether proving this goal is a coinductive step.
-    ///
-    /// This is used when encountering a trait solver cycle to
-    /// decide whether the initial provisional result of the cycle.
-    step_kind_from_parent: PathKind,
-
-    /// The available depth of a given goal, immutable.
-    available_depth: AvailableDepth,
-
-    /// The maximum depth reached by this stack entry, only up-to date
-    /// for the top of the stack and lazily updated for the rest.
-    reached_depth: StackDepth,
-
-    /// All cycle heads this goal depends on. Lazily updated and only
-    /// up-to date for the top of the stack.
-    heads: CycleHeads,
-
-    /// Whether evaluating this goal encountered overflow. Lazily updated.
-    encountered_overflow: bool,
-
-    /// Whether this goal has been used as the root of a cycle. This gets
-    /// eagerly updated when encountering a cycle.
-    has_been_used: Option<UsageKind>,
-
-    /// The nested goals of this goal, see the doc comment of the type.
-    nested_goals: NestedGoals<X>,
-
-    /// Starts out as `None` and gets set when rerunning this
-    /// goal in case we encounter a cycle.
-    provisional_result: Option<X::Result>,
-}
-
 /// A provisional result of an already computed goals which depends on other
 /// goals still on the stack.
 #[derive_where(Debug; X: Cx)]
@@ -498,7 +455,7 @@ pub struct SearchGraph<D: Delegate<Cx = X>, X: Cx = <D as Delegate>::Cx> {
     /// The stack of goals currently being computed.
     ///
     /// An element is *deeper* in the stack if its index is *lower*.
-    stack: IndexVec<StackDepth, StackEntry<X>>,
+    stack: Stack<X>,
     /// The provisional cache contains entries for already computed goals which
     /// still depend on goals higher-up in the stack. We don't move them to the
     /// global cache and track them locally instead. A provisional cache entry
@@ -537,16 +494,16 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
     /// and using existing global cache entries to make sure they
     /// have the same impact on the remaining evaluation.
     fn update_parent_goal(
-        stack: &mut IndexVec<StackDepth, StackEntry<X>>,
+        stack: &mut Stack<X>,
         step_kind_from_parent: PathKind,
-        reached_depth: StackDepth,
+        required_depth_for_nested: usize,
         heads: &CycleHeads,
         encountered_overflow: bool,
         context: UpdateParentGoalCtxt<'_, X>,
     ) {
         if let Some(parent_index) = stack.last_index() {
             let parent = &mut stack[parent_index];
-            parent.reached_depth = parent.reached_depth.max(reached_depth);
+            parent.required_depth = parent.required_depth.max(required_depth_for_nested + 1);
             parent.encountered_overflow |= encountered_overflow;
 
             parent.heads.extend_from_child(parent_index, step_kind_from_parent, heads);
@@ -588,13 +545,11 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
     /// the stack which completes the cycle. This given an inductive step AB which then cycles
     /// coinductively with A, we need to treat this cycle as coinductive.
     fn cycle_path_kind(
-        stack: &IndexVec<StackDepth, StackEntry<X>>,
+        stack: &Stack<X>,
         step_kind_to_head: PathKind,
         head: StackDepth,
     ) -> PathKind {
-        stack.raw[head.index() + 1..]
-            .iter()
-            .fold(step_kind_to_head, |curr, entry| curr.extend(entry.step_kind_from_parent))
+        stack.cycle_step_kinds(head).fold(step_kind_to_head, |curr, step| curr.extend(step))
     }
 
     /// Probably the most involved method of the whole solver.
@@ -656,20 +611,18 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
             return result;
         }
 
-        // Unfortunate, it looks like we actually have to compute this goalrar.
-        let depth = self.stack.next_index();
-        let entry = StackEntry {
+        // Unfortunate, it looks like we actually have to compute this goal.
+        self.stack.push(StackEntry {
             input,
             step_kind_from_parent,
             available_depth,
-            reached_depth: depth,
+            required_depth: 0,
             heads: Default::default(),
             encountered_overflow: false,
             has_been_used: None,
             nested_goals: Default::default(),
             provisional_result: None,
-        };
-        assert_eq!(self.stack.push(entry), depth);
+        });
 
         // This is for global caching, so we properly track query dependencies.
         // Everything that affects the `result` should be performed within this
@@ -686,7 +639,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
         Self::update_parent_goal(
             &mut self.stack,
             final_entry.step_kind_from_parent,
-            final_entry.reached_depth,
+            final_entry.required_depth,
             &final_entry.heads,
             final_entry.encountered_overflow,
             UpdateParentGoalCtxt::Ordinary(&final_entry.nested_goals),
@@ -700,7 +653,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
                 // the global cache.
                 assert_eq!(result, expected, "input={input:?}");
             } else if D::inspect_is_noop(inspect) {
-                self.insert_global_cache(cx, input, final_entry, result, dep_node)
+                self.insert_global_cache(cx, final_entry, result, dep_node)
             }
         } else if D::ENABLE_PROVISIONAL_CACHE {
             debug_assert!(validate_cache.is_none(), "unexpected non-root: {input:?}");
@@ -728,7 +681,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
         input: X::Input,
         inspect: &mut D::ProofTreeBuilder,
     ) -> X::Result {
-        if let Some(last) = self.stack.raw.last_mut() {
+        if let Some(last) = self.stack.last_mut() {
             last.encountered_overflow = true;
             // If computing a goal `B` depends on another goal `A` and
             // `A` has a nested goal which overflows, then computing `B`
@@ -859,7 +812,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
                 // apply provisional cache entries which encountered overflow once the
                 // current goal is already part of the same cycle. This check could be
                 // improved but seems to be good enough for now.
-                let last = self.stack.raw.last().unwrap();
+                let last = self.stack.last().unwrap();
                 if last.heads.opt_lowest_cycle_head().is_none_or(|lowest| lowest > head) {
                     continue;
                 }
@@ -868,14 +821,10 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
             // A provisional cache entry is only valid if the current path from its
             // highest cycle head to the goal is the same.
             if path_from_head == Self::cycle_path_kind(&self.stack, step_kind_from_parent, head) {
-                // While we don't have to track the full depth of the provisional cache entry,
-                // we do have to increment the required depth by one as we'd have already failed
-                // with overflow otherwise
-                let next_index = self.stack.next_index();
                 Self::update_parent_goal(
                     &mut self.stack,
                     step_kind_from_parent,
-                    next_index,
+                    0,
                     heads,
                     encountered_overflow,
                     UpdateParentGoalCtxt::ProvisionalCacheHit,
@@ -893,7 +842,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
     /// evaluating this entry would not have ended up depending on either a goal
     /// already on the stack or a provisional cache entry.
     fn candidate_is_applicable(
-        stack: &IndexVec<StackDepth, StackEntry<X>>,
+        stack: &Stack<X>,
         step_kind_from_parent: PathKind,
         provisional_cache: &HashMap<X::Input, Vec<ProvisionalCacheEntry<X>>>,
         nested_goals: &NestedGoals<X>,
@@ -991,7 +940,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
         available_depth: AvailableDepth,
     ) -> Option<X::Result> {
         cx.with_global_cache(|cache| {
-            let CacheData { result, additional_depth, encountered_overflow, nested_goals } = cache
+            let CacheData { result, required_depth, encountered_overflow, nested_goals } = cache
                 .get(cx, input, available_depth, |nested_goals| {
                     Self::candidate_is_applicable(
                         &self.stack,
@@ -1001,23 +950,19 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
                     )
                 })?;
 
-            // Update the reached depth of the current goal to make sure
-            // its state is the same regardless of whether we've used the
-            // global cache or not.
-            let reached_depth = self.stack.next_index().plus(additional_depth);
             // We don't move cycle participants to the global cache, so the
             // cycle heads are always empty.
             let heads = Default::default();
             Self::update_parent_goal(
                 &mut self.stack,
                 step_kind_from_parent,
-                reached_depth,
+                required_depth,
                 &heads,
                 encountered_overflow,
                 UpdateParentGoalCtxt::Ordinary(nested_goals),
             );
 
-            debug!(?additional_depth, "global cache hit");
+            debug!(?required_depth, "global cache hit");
             Some(result)
         })
     }
@@ -1028,7 +973,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
         input: X::Input,
         step_kind_from_parent: PathKind,
     ) -> Option<X::Result> {
-        let (head, _stack_entry) = self.stack.iter_enumerated().find(|(_, e)| e.input == input)?;
+        let head = self.stack.find(input)?;
         // We have a nested goal which directly relies on a goal deeper in the stack.
         //
         // We start by tagging all cycle participants, as that's necessary for caching.
@@ -1043,10 +988,9 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
 
         // Subtle: when encountering a cyclic goal, we still first checked for overflow,
         // so we have to update the reached depth.
-        let next_index = self.stack.next_index();
         let last_index = self.stack.last_index().unwrap();
         let last = &mut self.stack[last_index];
-        last.reached_depth = last.reached_depth.max(next_index);
+        last.required_depth = last.required_depth.max(1);
 
         last.nested_goals.insert(input, step_kind_from_parent.into());
         last.nested_goals.insert(last.input, PathsToNested::EMPTY);
@@ -1095,7 +1039,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
         let mut i = 0;
         loop {
             let result = evaluate_goal(self, inspect);
-            let stack_entry = self.stack.pop().unwrap();
+            let stack_entry = self.stack.pop();
             debug_assert_eq!(stack_entry.input, input);
 
             // If the current goal is not the root of a cycle, we are done.
@@ -1176,20 +1120,18 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
     fn insert_global_cache(
         &mut self,
         cx: X,
-        input: X::Input,
         final_entry: StackEntry<X>,
         result: X::Result,
         dep_node: X::DepNodeIndex,
     ) {
-        let additional_depth = final_entry.reached_depth.as_usize() - self.stack.len();
         debug!(?final_entry, ?result, "insert global cache");
         cx.with_global_cache(|cache| {
             cache.insert(
                 cx,
-                input,
+                final_entry.input,
                 result,
                 dep_node,
-                additional_depth,
+                final_entry.required_depth,
                 final_entry.encountered_overflow,
                 final_entry.nested_goals,
             )
diff --git a/compiler/rustc_type_ir/src/search_graph/stack.rs b/compiler/rustc_type_ir/src/search_graph/stack.rs
new file mode 100644
index 00000000000..8bb247bf055
--- /dev/null
+++ b/compiler/rustc_type_ir/src/search_graph/stack.rs
@@ -0,0 +1,113 @@
+use std::ops::{Index, IndexMut};
+
+use derive_where::derive_where;
+use rustc_index::IndexVec;
+
+use super::{AvailableDepth, Cx, CycleHeads, NestedGoals, PathKind, UsageKind};
+
+rustc_index::newtype_index! {
+    #[orderable]
+    #[gate_rustc_only]
+    pub(super) struct StackDepth {}
+}
+
+/// Stack entries of the evaluation stack. Its fields tend to be lazily
+/// when popping a child goal or completely immutable.
+#[derive_where(Debug; X: Cx)]
+pub(super) struct StackEntry<X: Cx> {
+    pub input: X::Input,
+
+    /// Whether proving this goal is a coinductive step.
+    ///
+    /// This is used when encountering a trait solver cycle to
+    /// decide whether the initial provisional result of the cycle.
+    pub step_kind_from_parent: PathKind,
+
+    /// The available depth of a given goal, immutable.
+    pub available_depth: AvailableDepth,
+
+    /// The maximum depth required while evaluating this goal.
+    pub required_depth: usize,
+
+    /// All cycle heads this goal depends on. Lazily updated and only
+    /// up-to date for the top of the stack.
+    pub heads: CycleHeads,
+
+    /// Whether evaluating this goal encountered overflow. Lazily updated.
+    pub encountered_overflow: bool,
+
+    /// Whether this goal has been used as the root of a cycle. This gets
+    /// eagerly updated when encountering a cycle.
+    pub has_been_used: Option<UsageKind>,
+
+    /// The nested goals of this goal, see the doc comment of the type.
+    pub nested_goals: NestedGoals<X>,
+
+    /// Starts out as `None` and gets set when rerunning this
+    /// goal in case we encounter a cycle.
+    pub provisional_result: Option<X::Result>,
+}
+
+#[derive_where(Default; X: Cx)]
+pub(super) struct Stack<X: Cx> {
+    entries: IndexVec<StackDepth, StackEntry<X>>,
+}
+
+impl<X: Cx> Stack<X> {
+    pub(super) fn is_empty(&self) -> bool {
+        self.entries.is_empty()
+    }
+
+    pub(super) fn len(&self) -> usize {
+        self.entries.len()
+    }
+
+    pub(super) fn last_index(&self) -> Option<StackDepth> {
+        self.entries.last_index()
+    }
+
+    pub(super) fn last(&self) -> Option<&StackEntry<X>> {
+        self.entries.raw.last()
+    }
+
+    pub(super) fn last_mut(&mut self) -> Option<&mut StackEntry<X>> {
+        self.entries.raw.last_mut()
+    }
+
+    pub(super) fn next_index(&self) -> StackDepth {
+        self.entries.next_index()
+    }
+
+    pub(super) fn push(&mut self, entry: StackEntry<X>) -> StackDepth {
+        self.entries.push(entry)
+    }
+
+    pub(super) fn pop(&mut self) -> StackEntry<X> {
+        self.entries.pop().unwrap()
+    }
+
+    pub(super) fn cycle_step_kinds(&self, head: StackDepth) -> impl Iterator<Item = PathKind> {
+        self.entries.raw[head.index() + 1..].iter().map(|entry| entry.step_kind_from_parent)
+    }
+
+    pub(super) fn iter(&self) -> impl Iterator<Item = &StackEntry<X>> {
+        self.entries.iter()
+    }
+
+    pub(super) fn find(&self, input: X::Input) -> Option<StackDepth> {
+        self.entries.iter_enumerated().find(|(_, e)| e.input == input).map(|(idx, _)| idx)
+    }
+}
+
+impl<X: Cx> Index<StackDepth> for Stack<X> {
+    type Output = StackEntry<X>;
+    fn index(&self, index: StackDepth) -> &StackEntry<X> {
+        &self.entries[index]
+    }
+}
+
+impl<X: Cx> IndexMut<StackDepth> for Stack<X> {
+    fn index_mut(&mut self, index: StackDepth) -> &mut Self::Output {
+        &mut self.entries[index]
+    }
+}
diff --git a/compiler/rustc_type_ir/src/ty_kind/closure.rs b/compiler/rustc_type_ir/src/ty_kind/closure.rs
index 8ba985d2d19..d1ca9bdb7fb 100644
--- a/compiler/rustc_type_ir/src/ty_kind/closure.rs
+++ b/compiler/rustc_type_ir/src/ty_kind/closure.rs
@@ -342,7 +342,7 @@ struct HasRegionsBoundAt {
 // FIXME: Could be optimized to not walk into components with no escaping bound vars.
 impl<I: Interner> TypeVisitor<I> for HasRegionsBoundAt {
     type Result = ControlFlow<()>;
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
         self.binder.shift_in(1);
         t.super_visit_with(self)?;
         self.binder.shift_out(1);
diff --git a/compiler/rustc_type_ir/src/visit.rs b/compiler/rustc_type_ir/src/visit.rs
index fc3864dd5ae..a96ac97f785 100644
--- a/compiler/rustc_type_ir/src/visit.rs
+++ b/compiler/rustc_type_ir/src/visit.rs
@@ -52,7 +52,7 @@ use smallvec::SmallVec;
 use thin_vec::ThinVec;
 
 use crate::inherent::*;
-use crate::{self as ty, Interner, TypeFlags, TypeFoldable};
+use crate::{self as ty, Interner, TypeFlags};
 
 /// This trait is implemented for every type that can be visited,
 /// providing the skeleton of the traversal.
@@ -94,7 +94,7 @@ pub trait TypeVisitor<I: Interner>: Sized {
     #[cfg(not(feature = "nightly"))]
     type Result: VisitorResult;
 
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
         t.super_visit_with(self)
     }
 
@@ -401,7 +401,7 @@ impl std::fmt::Debug for HasTypeFlagsVisitor {
 impl<I: Interner> TypeVisitor<I> for HasTypeFlagsVisitor {
     type Result = ControlFlow<FoundFlags>;
 
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
         // If we're looking for the HAS_BINDER_VARS flag, check if the
         // binder has vars. This won't be present in the binder's bound
         // value, so we need to check here too.
@@ -510,7 +510,7 @@ struct HasEscapingVarsVisitor {
 impl<I: Interner> TypeVisitor<I> for HasEscapingVarsVisitor {
     type Result = ControlFlow<FoundEscapingVars>;
 
-    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
         self.outer_index.shift_in(1);
         let result = t.super_visit_with(self);
         self.outer_index.shift_out(1);