rustc_type_ir/

binder.rs

use std::fmt;
use std::hash::Hash;
use std::marker::PhantomData;
use std::ops::{ControlFlow, Deref};

use derive_where::derive_where;
#[cfg(feature = "nightly")]
use rustc_macros::{Decodable_NoContext, Encodable_NoContext, StableHash, StableHash_NoContext};
use rustc_type_ir_macros::{
    GenericTypeVisitable, Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic,
};
use tracing::instrument;

use crate::data_structures::SsoHashSet;
use crate::fold::{FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable};
use crate::inherent::*;
use crate::lift::Lift;
use crate::visit::{Flags, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor};
use crate::{self as ty, DebruijnIndex, Interner, UniverseIndex, Unnormalized};

/// `Binder` is a binder for higher-ranked lifetimes or types. It is part of the
/// compiler's representation for things like `for<'a> Fn(&'a isize)`
/// (which would be represented by the type `PolyTraitRef == Binder<I, TraitRef>`).
///
/// See <https://rustc-dev-guide.rust-lang.org/ty_module/instantiating_binders.html>
/// for more details.
///
/// `Decodable` and `Encodable` are implemented for `Binder<T>` using the `impl_binder_encode_decode!` macro.
#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner, T)]
#[derive(GenericTypeVisitable)]
#[cfg_attr(feature = "nightly", derive(StableHash_NoContext))]
pub struct Binder<I: Interner, T> {
    value: T,
    bound_vars: I::BoundVarKinds,
}

impl<I: Interner, T: Eq> Eq for Binder<I, T> {}

// FIXME: We manually derive `Lift` because the `derive(Lift_Generic)` doesn't
// understand how to turn `T` to `T::Lifted` in the output `type Lifted`.
impl<I: Interner, U: Interner, T> Lift<U> for Binder<I, T>
where
    T: Lift<U>,
    I::BoundVarKinds: Lift<U, Lifted = U::BoundVarKinds>,
{
    type Lifted = Binder<U, T::Lifted>;

    fn lift_to_interner(self, cx: U) -> Self::Lifted {
        Binder {
            value: self.value.lift_to_interner(cx),
            bound_vars: self.bound_vars.lift_to_interner(cx),
        }
    }
}

#[cfg(feature = "nightly")]
macro_rules! impl_binder_encode_decode {
    ($($t:ty),+ $(,)?) => {
        $(
            impl<I: Interner, E: rustc_serialize::Encoder> rustc_serialize::Encodable<E> for ty::Binder<I, $t>
            where
                $t: rustc_serialize::Encodable<E>,
                I::BoundVarKinds: rustc_serialize::Encodable<E>,
            {
                fn encode(&self, e: &mut E) {
                    self.bound_vars().encode(e);
                    self.as_ref().skip_binder().encode(e);
                }
            }
            impl<I: Interner, D: rustc_serialize::Decoder> rustc_serialize::Decodable<D> for ty::Binder<I, $t>
            where
                $t: TypeVisitable<I> + rustc_serialize::Decodable<D>,
                I::BoundVarKinds: rustc_serialize::Decodable<D>,
            {
                fn decode(decoder: &mut D) -> Self {
                    let bound_vars = rustc_serialize::Decodable::decode(decoder);
                    ty::Binder::bind_with_vars(rustc_serialize::Decodable::decode(decoder), bound_vars)
                }
            }
        )*
    }
}

#[cfg(feature = "nightly")]
impl_binder_encode_decode! {
    ty::FnSig<I>,
    ty::FnSigTys<I>,
    ty::TraitPredicate<I>,
    ty::ExistentialPredicate<I>,
    ty::TraitRef<I>,
    ty::ExistentialTraitRef<I>,
    ty::HostEffectPredicate<I>,
}

impl<I: Interner, T> Binder<I, T>
where
    T: TypeVisitable<I>,
{
    /// Wraps `value` in a binder, asserting that `value` does not
    /// contain any bound vars that would be bound by the
    /// binder. This is commonly used to 'inject' a value T into a
    /// different binding level.
    #[track_caller]
    pub fn dummy(value: T) -> Binder<I, T> {
        assert!(
            !value.has_escaping_bound_vars(),
            "`{value:?}` has escaping bound vars, so it cannot be wrapped in a dummy binder."
        );
        Binder { value, bound_vars: Default::default() }
    }

    pub fn bind_with_vars(value: T, bound_vars: I::BoundVarKinds) -> Binder<I, T> {
        if cfg!(debug_assertions) {
            let mut validator = ValidateBoundVars::new(bound_vars);
            let _ = value.visit_with(&mut validator);
        }
        Binder { value, bound_vars }
    }
}

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Binder<I, T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        folder.try_fold_binder(self)
    }

    fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
        folder.fold_binder(self)
    }
}

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)
    }
}

impl<I: Interner, T: TypeFoldable<I>> TypeSuperFoldable<I> for Binder<I, T> {
    fn try_super_fold_with<F: FallibleTypeFolder<I>>(
        self,
        folder: &mut F,
    ) -> Result<Self, F::Error> {
        self.try_map_bound(|t| t.try_fold_with(folder))
    }

    fn super_fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
        self.map_bound(|t| t.fold_with(folder))
    }
}

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)
    }
}

impl<I: Interner, T> Binder<I, T> {
    /// Returns the value contained inside of this `for<'a>`. Accessing generic args
    /// in the returned value is generally incorrect.
    ///
    /// Please read <https://rustc-dev-guide.rust-lang.org/ty_module/instantiating_binders.html>
    /// before using this function. It is usually better to discharge the binder using
    /// `no_bound_vars` or `instantiate_bound_regions` or something like that.
    ///
    /// `skip_binder` is only valid when you are either extracting data that does not reference
    /// any generic arguments, e.g. a `DefId`, or when you're making sure you only pass the
    /// value to things which can handle escaping bound vars.
    ///
    /// See existing uses of `.skip_binder()` in `rustc_trait_selection::traits::select`
    /// or `rustc_next_trait_solver` for examples.
    pub fn skip_binder(self) -> T {
        self.value
    }

    pub fn bound_vars(&self) -> I::BoundVarKinds {
        self.bound_vars
    }

    pub fn as_ref(&self) -> Binder<I, &T> {
        Binder { value: &self.value, bound_vars: self.bound_vars }
    }

    pub fn as_deref(&self) -> Binder<I, &T::Target>
    where
        T: Deref,
    {
        Binder { value: &self.value, bound_vars: self.bound_vars }
    }

    pub fn map_bound_ref<F, U: TypeVisitable<I>>(&self, f: F) -> Binder<I, U>
    where
        F: FnOnce(&T) -> U,
    {
        self.as_ref().map_bound(f)
    }

    pub fn map_bound<F, U: TypeVisitable<I>>(self, f: F) -> Binder<I, U>
    where
        F: FnOnce(T) -> U,
    {
        let Binder { value, bound_vars } = self;
        let value = f(value);
        if cfg!(debug_assertions) {
            let mut validator = ValidateBoundVars::new(bound_vars);
            let _ = value.visit_with(&mut validator);
        }
        Binder { value, bound_vars }
    }

    pub fn try_map_bound<F, U: TypeVisitable<I>, E>(self, f: F) -> Result<Binder<I, U>, E>
    where
        F: FnOnce(T) -> Result<U, E>,
    {
        let Binder { value, bound_vars } = self;
        let value = f(value)?;
        if cfg!(debug_assertions) {
            let mut validator = ValidateBoundVars::new(bound_vars);
            let _ = value.visit_with(&mut validator);
        }
        Ok(Binder { value, bound_vars })
    }

    /// Wraps a `value` in a binder, using the same bound variables as the
    /// current `Binder`. This should not be used if the new value *changes*
    /// the bound variables. Note: the (old or new) value itself does not
    /// necessarily need to *name* all the bound variables.
    ///
    /// This currently doesn't do anything different than `bind`, because we
    /// don't actually track bound vars. However, semantically, it is different
    /// because bound vars aren't allowed to change here, whereas they are
    /// in `bind`. This may be (debug) asserted in the future.
    pub fn rebind<U>(&self, value: U) -> Binder<I, U>
    where
        U: TypeVisitable<I>,
    {
        Binder::bind_with_vars(value, self.bound_vars)
    }

    /// Unwraps and returns the value within, but only if it contains
    /// no bound vars at all. (In other words, if this binder --
    /// and indeed any enclosing binder -- doesn't bind anything at
    /// all.) Otherwise, returns `None`.
    ///
    /// (One could imagine having a method that just unwraps a single
    /// binder, but permits late-bound vars bound by enclosing
    /// binders, but that would require adjusting the debruijn
    /// indices, and given the shallow binding structure we often use,
    /// would not be that useful.)
    pub fn no_bound_vars(self) -> Option<T>
    where
        T: TypeVisitable<I>,
    {
        // `self.value` is equivalent to `self.skip_binder()`
        if self.value.has_escaping_bound_vars() { None } else { Some(self.skip_binder()) }
    }
}

impl<I: Interner, T> Binder<I, Option<T>> {
    pub fn transpose(self) -> Option<Binder<I, T>> {
        let Binder { value, bound_vars } = self;
        value.map(|value| Binder { value, bound_vars })
    }
}

impl<I: Interner, T: IntoIterator> Binder<I, T> {
    pub fn iter(self) -> impl Iterator<Item = Binder<I, T::Item>> {
        let Binder { value, bound_vars } = self;
        value.into_iter().map(move |value| Binder { value, bound_vars })
    }
}

pub struct ValidateBoundVars<I: Interner> {
    bound_vars: I::BoundVarKinds,
    binder_index: ty::DebruijnIndex,
    // We only cache types because any complex const will have to step through
    // a type at some point anyways. We may encounter the same variable at
    // different levels of binding, so this can't just be `Ty`.
    visited: SsoHashSet<(ty::DebruijnIndex, I::Ty)>,
}

impl<I: Interner> ValidateBoundVars<I> {
    pub fn new(bound_vars: I::BoundVarKinds) -> Self {
        ValidateBoundVars {
            bound_vars,
            binder_index: ty::INNERMOST,
            visited: SsoHashSet::default(),
        }
    }
}

impl<I: Interner> TypeVisitor<I> for ValidateBoundVars<I> {
    type Result = ControlFlow<()>;

    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);
        result
    }

    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
        if t.outer_exclusive_binder() < self.binder_index
            || !self.visited.insert((self.binder_index, t))
        {
            return ControlFlow::Break(());
        }
        match t.kind() {
            ty::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_ty)
                if debruijn == self.binder_index =>
            {
                let idx = bound_ty.var().as_usize();
                if self.bound_vars.len() <= idx {
                    panic!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
                }
                bound_ty.assert_eq(self.bound_vars.get(idx).unwrap());
            }
            _ => {}
        };

        t.super_visit_with(self)
    }

    fn visit_const(&mut self, c: I::Const) -> Self::Result {
        if c.outer_exclusive_binder() < self.binder_index {
            return ControlFlow::Break(());
        }
        match c.kind() {
            ty::ConstKind::Bound(debruijn, bound_const)
                if debruijn == ty::BoundVarIndexKind::Bound(self.binder_index) =>
            {
                let idx = bound_const.var().as_usize();
                if self.bound_vars.len() <= idx {
                    panic!("Not enough bound vars: {:?} not found in {:?}", c, self.bound_vars);
                }
                bound_const.assert_eq(self.bound_vars.get(idx).unwrap());
            }
            _ => {}
        };

        c.super_visit_with(self)
    }

    fn visit_region(&mut self, r: I::Region) -> Self::Result {
        match r.kind() {
            ty::ReBound(index, br) if index == ty::BoundVarIndexKind::Bound(self.binder_index) => {
                let idx = br.var().as_usize();
                if self.bound_vars.len() <= idx {
                    panic!("Not enough bound vars: {:?} not found in {:?}", r, self.bound_vars);
                }
                br.assert_eq(self.bound_vars.get(idx).unwrap());
            }

            _ => (),
        };

        ControlFlow::Continue(())
    }
}

/// Similar to [`Binder`] except that it tracks early bound generics, i.e. `struct Foo<T>(T)`
/// needs `T` instantiated immediately. This type primarily exists to avoid forgetting to call
/// `instantiate`.
///
/// See <https://rustc-dev-guide.rust-lang.org/ty_module/early_binder.html> for more details.
#[derive_where(Clone, Copy, PartialOrd, Ord, PartialEq, Hash, Debug; I: Interner, T)]
#[derive(GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub struct EarlyBinder<I: Interner, T> {
    value: T,
    #[derive_where(skip(Debug))]
    _tcx: PhantomData<fn() -> I>,
}

impl<I: Interner, T: Eq> Eq for EarlyBinder<I, T> {}

// FIXME(154045): Recommended as per https://github.com/rust-lang/rust/issues/154045, this is so sad :((
#[cfg(feature = "nightly")]
macro_rules! generate { ($( $tt:tt )*) => { $( $tt )* } }

#[cfg(feature = "nightly")]
generate!(
    /// For early binders, you should first call `instantiate` before using any visitors.
    impl<I: Interner, T> !TypeFoldable<I> for ty::EarlyBinder<I, T> {}
    /// For early binders, you should first call `instantiate` before using any visitors.
    impl<I: Interner, T> !TypeVisitable<I> for ty::EarlyBinder<I, T> {}
);

impl<I: Interner, T> EarlyBinder<I, T> {
    pub fn bind(value: T) -> EarlyBinder<I, T> {
        EarlyBinder { value, _tcx: PhantomData }
    }

    pub fn as_ref(&self) -> EarlyBinder<I, &T> {
        EarlyBinder { value: &self.value, _tcx: PhantomData }
    }

    pub fn map_bound_ref<F, U>(&self, f: F) -> EarlyBinder<I, U>
    where
        F: FnOnce(&T) -> U,
    {
        self.as_ref().map_bound(f)
    }

    pub fn map_bound<F, U>(self, f: F) -> EarlyBinder<I, U>
    where
        F: FnOnce(T) -> U,
    {
        let value = f(self.value);
        EarlyBinder { value, _tcx: PhantomData }
    }

    pub fn try_map_bound<F, U, E>(self, f: F) -> Result<EarlyBinder<I, U>, E>
    where
        F: FnOnce(T) -> Result<U, E>,
    {
        let value = f(self.value)?;
        Ok(EarlyBinder { value, _tcx: PhantomData })
    }

    pub fn rebind<U>(&self, value: U) -> EarlyBinder<I, U> {
        EarlyBinder { value, _tcx: PhantomData }
    }

    /// Skips the binder and returns the "bound" value. Accessing generic args
    /// in the returned value is generally incorrect.
    ///
    /// Please read <https://rustc-dev-guide.rust-lang.org/ty_module/early_binder.html>
    /// before using this function.
    ///
    /// Only use this to extract data that does not depend on generic parameters, e.g.
    /// to get the `DefId` of the inner value or the number of arguments ofan `FnSig`,
    /// or while making sure to only pass the value to functions which are explicitly
    /// set up to handle these uninstantiated generic parameters.
    ///
    /// To skip the binder on `x: &EarlyBinder<I, T>` to obtain `&T`, leverage
    /// [`EarlyBinder::as_ref`](EarlyBinder::as_ref): `x.as_ref().skip_binder()`.
    ///
    /// See also [`Binder::skip_binder`](Binder::skip_binder), which is
    /// the analogous operation on [`Binder`].
    pub fn skip_binder(self) -> T {
        self.value
    }
}

impl<I: Interner, T> EarlyBinder<I, Option<T>> {
    pub fn transpose(self) -> Option<EarlyBinder<I, T>> {
        self.value.map(|value| EarlyBinder { value, _tcx: PhantomData })
    }
}

impl<I: Interner, Iter: IntoIterator> EarlyBinder<I, Iter>
where
    Iter::Item: TypeFoldable<I>,
{
    pub fn iter_instantiated<A>(self, cx: I, args: A) -> IterInstantiated<I, Iter, A>
    where
        A: SliceLike<Item = I::GenericArg>,
    {
        IterInstantiated { it: self.value.into_iter(), cx, args }
    }

    /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
    /// but on an iterator of `TypeFoldable` values.
    pub fn iter_identity(self) -> impl Iterator<Item = Unnormalized<I, Iter::Item>> {
        self.value.into_iter().map(Unnormalized::new)
    }
}

pub struct IterInstantiated<I: Interner, Iter: IntoIterator, A> {
    it: Iter::IntoIter,
    cx: I,
    args: A,
}

impl<I: Interner, Iter: IntoIterator, A> Iterator for IterInstantiated<I, Iter, A>
where
    Iter::Item: TypeFoldable<I>,
    A: SliceLike<Item = I::GenericArg>,
{
    type Item = Unnormalized<I, Iter::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        Some(
            EarlyBinder { value: self.it.next()?, _tcx: PhantomData }
                .instantiate(self.cx, self.args),
        )
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<I: Interner, Iter: IntoIterator, A> DoubleEndedIterator for IterInstantiated<I, Iter, A>
where
    Iter::IntoIter: DoubleEndedIterator,
    Iter::Item: TypeFoldable<I>,
    A: SliceLike<Item = I::GenericArg>,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        Some(
            EarlyBinder { value: self.it.next_back()?, _tcx: PhantomData }
                .instantiate(self.cx, self.args),
        )
    }
}

impl<I: Interner, Iter: IntoIterator, A> ExactSizeIterator for IterInstantiated<I, Iter, A>
where
    Iter::IntoIter: ExactSizeIterator,
    Iter::Item: TypeFoldable<I>,
    A: SliceLike<Item = I::GenericArg>,
{
}

impl<'s, I: Interner, Iter: IntoIterator> EarlyBinder<I, Iter>
where
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
{
    pub fn iter_instantiated_copied(
        self,
        cx: I,
        args: &'s [I::GenericArg],
    ) -> IterInstantiatedCopied<'s, I, Iter> {
        IterInstantiatedCopied { it: self.value.into_iter(), cx, args }
    }

    /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
    /// but on an iterator of values that deref to a `TypeFoldable`.
    pub fn iter_identity_copied(self) -> IterIdentityCopied<I, Iter> {
        IterIdentityCopied { it: self.value.into_iter(), _tcx: PhantomData }
    }
}

pub struct IterInstantiatedCopied<'a, I: Interner, Iter: IntoIterator> {
    it: Iter::IntoIter,
    cx: I,
    args: &'a [I::GenericArg],
}

impl<I: Interner, Iter: IntoIterator> Iterator for IterInstantiatedCopied<'_, I, Iter>
where
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
{
    type Item = Unnormalized<I, <Iter::Item as Deref>::Target>;

    fn next(&mut self) -> Option<Self::Item> {
        self.it.next().map(|value| {
            EarlyBinder { value: *value, _tcx: PhantomData }.instantiate(self.cx, self.args)
        })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<I: Interner, Iter: IntoIterator> DoubleEndedIterator for IterInstantiatedCopied<'_, I, Iter>
where
    Iter::IntoIter: DoubleEndedIterator,
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        self.it.next_back().map(|value| {
            EarlyBinder { value: *value, _tcx: PhantomData }.instantiate(self.cx, self.args)
        })
    }
}

impl<I: Interner, Iter: IntoIterator> ExactSizeIterator for IterInstantiatedCopied<'_, I, Iter>
where
    Iter::IntoIter: ExactSizeIterator,
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
{
}

pub struct IterIdentityCopied<I: Interner, Iter: IntoIterator> {
    it: Iter::IntoIter,
    _tcx: PhantomData<fn() -> I>,
}

impl<I: Interner, Iter: IntoIterator> Iterator for IterIdentityCopied<I, Iter>
where
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy,
{
    type Item = Unnormalized<I, <Iter::Item as Deref>::Target>;

    fn next(&mut self) -> Option<Self::Item> {
        self.it.next().map(|i| Unnormalized::new(*i))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.it.size_hint()
    }
}

impl<I: Interner, Iter: IntoIterator> DoubleEndedIterator for IterIdentityCopied<I, Iter>
where
    Iter::IntoIter: DoubleEndedIterator,
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        self.it.next_back().map(|i| Unnormalized::new(*i))
    }
}

impl<I: Interner, Iter: IntoIterator> ExactSizeIterator for IterIdentityCopied<I, Iter>
where
    Iter::IntoIter: ExactSizeIterator,
    Iter::Item: Deref,
    <Iter::Item as Deref>::Target: Copy,
{
}
pub struct EarlyBinderIter<I, T> {
    t: T,
    _tcx: PhantomData<I>,
}

impl<I: Interner, T: IntoIterator> EarlyBinder<I, T> {
    pub fn transpose_iter(self) -> EarlyBinderIter<I, T::IntoIter> {
        EarlyBinderIter { t: self.value.into_iter(), _tcx: PhantomData }
    }
}

impl<I: Interner, T: Iterator> Iterator for EarlyBinderIter<I, T> {
    type Item = EarlyBinder<I, T::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        self.t.next().map(|value| EarlyBinder { value, _tcx: PhantomData })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.t.size_hint()
    }
}

impl<I: Interner, T: TypeFoldable<I>> ty::EarlyBinder<I, T> {
    pub fn instantiate<A>(self, cx: I, args: A) -> Unnormalized<I, T>
    where
        A: SliceLike<Item = I::GenericArg>,
    {
        // Nothing to fold, so let's avoid visiting things and possibly re-hashing/equating
        // them when interning. Perf testing found this to be a modest improvement.
        // See: <https://github.com/rust-lang/rust/pull/142317>
        if args.is_empty() {
            assert!(
                !self.value.has_param(),
                "{:?} has parameters, but no args were provided in instantiate",
                self.value,
            );
            return Unnormalized::new(self.value);
        }
        let mut folder = ArgFolder { cx, args: args.as_slice(), binders_passed: 0 };
        Unnormalized::new(self.value.fold_with(&mut folder))
    }

    /// Makes the identity replacement `T0 => T0, ..., TN => TN`.
    /// Conceptually, this converts universally bound variables into placeholders
    /// when inside of a given item.
    ///
    /// For example, consider `for<T> fn foo<T>(){ .. }`:
    /// - Outside of `foo`, `T` is bound (represented by the presence of `EarlyBinder`).
    /// - Inside of the body of `foo`, we treat `T` as a placeholder by calling
    /// `instantiate_identity` to discharge the `EarlyBinder`.
    pub fn instantiate_identity(self) -> Unnormalized<I, T> {
        // FIXME(#155345): In case the bound value was already normalized, this
        // is unnecessary. We may want to track explicitly whether `EarlyBinder`
        // contains something that has been normalized already.
        // Also do that for other types who have `instantiate_identity` method,
        // e.g., `GenericPredicates` and `ConstConditions`.
        //
        // This is annoying, as e.g. `type_of` for opaque types is normalized,
        // while `type_of` for free type aliases is not.
        Unnormalized::new(self.value)
    }

    /// Returns the inner value, but only if it contains no bound vars.
    pub fn no_bound_vars(self) -> Option<T> {
        if !self.value.has_param() { Some(self.value) } else { None }
    }
}

///////////////////////////////////////////////////////////////////////////
// The actual instantiation engine itself is a type folder.

struct ArgFolder<'a, I: Interner> {
    cx: I,
    args: &'a [I::GenericArg],

    /// Number of region binders we have passed through while doing the instantiation
    binders_passed: u32,
}

impl<'a, I: Interner> TypeFolder<I> for ArgFolder<'a, I> {
    #[inline]
    fn cx(&self) -> I {
        self.cx
    }

    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
        self.binders_passed += 1;
        let t = t.super_fold_with(self);
        self.binders_passed -= 1;
        t
    }

    fn fold_region(&mut self, r: I::Region) -> I::Region {
        // Note: This routine only handles regions that are bound on
        // type declarations and other outer declarations, not those
        // bound in *fn types*. Region instantiation of the bound
        // regions that appear in a function signature is done using
        // the specialized routine `ty::replace_late_regions()`.
        match r.kind() {
            ty::ReEarlyParam(data) => {
                let rk = self.args.get(data.index() as usize).map(|arg| arg.kind());
                match rk {
                    Some(ty::GenericArgKind::Lifetime(lt)) => self.shift_region_through_binders(lt),
                    Some(other) => self.region_param_expected(data, r, other),
                    None => self.region_param_out_of_range(data, r),
                }
            }
            ty::ReBound(..)
            | ty::ReLateParam(_)
            | ty::ReStatic
            | ty::RePlaceholder(_)
            | ty::ReErased
            | ty::ReError(_) => r,
            ty::ReVar(_) => panic!("unexpected region: {r:?}"),
        }
    }

    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
        if !t.has_param() {
            return t;
        }

        match t.kind() {
            ty::Param(p) => self.ty_for_param(p, t),
            _ => t.super_fold_with(self),
        }
    }

    fn fold_const(&mut self, c: I::Const) -> I::Const {
        if let ty::ConstKind::Param(p) = c.kind() {
            self.const_for_param(p, c)
        } else {
            c.super_fold_with(self)
        }
    }

    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
        if p.has_param() { p.super_fold_with(self) } else { p }
    }

    fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses {
        if c.has_param() { c.super_fold_with(self) } else { c }
    }
}

impl<'a, I: Interner> ArgFolder<'a, I> {
    fn ty_for_param(&self, p: I::ParamTy, source_ty: I::Ty) -> I::Ty {
        // Look up the type in the args. It really should be in there.
        let opt_ty = self.args.get(p.index() as usize).map(|arg| arg.kind());
        let ty = match opt_ty {
            Some(ty::GenericArgKind::Type(ty)) => ty,
            Some(kind) => self.type_param_expected(p, source_ty, kind),
            None => self.type_param_out_of_range(p, source_ty),
        };

        self.shift_vars_through_binders(ty)
    }

    #[cold]
    #[inline(never)]
    fn type_param_expected(&self, p: I::ParamTy, ty: I::Ty, kind: ty::GenericArgKind<I>) -> ! {
        panic!(
            "expected type for `{:?}` ({:?}/{}) but found {:?} when instantiating, args={:?}",
            p,
            ty,
            p.index(),
            kind,
            self.args,
        )
    }

    #[cold]
    #[inline(never)]
    fn type_param_out_of_range(&self, p: I::ParamTy, ty: I::Ty) -> ! {
        panic!(
            "type parameter `{:?}` ({:?}/{}) out of range when instantiating, args={:?}",
            p,
            ty,
            p.index(),
            self.args,
        )
    }

    fn const_for_param(&self, p: I::ParamConst, source_ct: I::Const) -> I::Const {
        // Look up the const in the args. It really should be in there.
        let opt_ct = self.args.get(p.index() as usize).map(|arg| arg.kind());
        let ct = match opt_ct {
            Some(ty::GenericArgKind::Const(ct)) => ct,
            Some(kind) => self.const_param_expected(p, source_ct, kind),
            None => self.const_param_out_of_range(p, source_ct),
        };

        self.shift_vars_through_binders(ct)
    }

    #[cold]
    #[inline(never)]
    fn const_param_expected(
        &self,
        p: I::ParamConst,
        ct: I::Const,
        kind: ty::GenericArgKind<I>,
    ) -> ! {
        panic!(
            "expected const for `{:?}` ({:?}/{}) but found {:?} when instantiating args={:?}",
            p,
            ct,
            p.index(),
            kind,
            self.args,
        )
    }

    #[cold]
    #[inline(never)]
    fn const_param_out_of_range(&self, p: I::ParamConst, ct: I::Const) -> ! {
        panic!(
            "const parameter `{:?}` ({:?}/{}) out of range when instantiating args={:?}",
            p,
            ct,
            p.index(),
            self.args,
        )
    }

    #[cold]
    #[inline(never)]
    fn region_param_expected(
        &self,
        ebr: I::EarlyParamRegion,
        r: I::Region,
        kind: ty::GenericArgKind<I>,
    ) -> ! {
        panic!(
            "expected region for `{:?}` ({:?}/{}) but found {:?} when instantiating args={:?}",
            ebr,
            r,
            ebr.index(),
            kind,
            self.args,
        )
    }

    #[cold]
    #[inline(never)]
    fn region_param_out_of_range(&self, ebr: I::EarlyParamRegion, r: I::Region) -> ! {
        panic!(
            "region parameter `{:?}` ({:?}/{}) out of range when instantiating args={:?}",
            ebr,
            r,
            ebr.index(),
            self.args,
        )
    }

    /// It is sometimes necessary to adjust the De Bruijn indices during instantiation. This occurs
    /// when we are instantiating a type with escaping bound vars into a context where we have
    /// passed through binders. That's quite a mouthful. Let's see an example:
    ///
    /// ```
    /// type Func<A> = fn(A);
    /// type MetaFunc = for<'a> fn(Func<&'a i32>);
    /// ```
    ///
    /// The type `MetaFunc`, when fully expanded, will be
    /// ```ignore (illustrative)
    /// for<'a> fn(fn(&'a i32))
    /// //      ^~ ^~ ^~~
    /// //      |  |  |
    /// //      |  |  DebruijnIndex of 2
    /// //      Binders
    /// ```
    /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
    /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
    /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the
    /// definition of `MetaFunc`, the binder is not visible, so the type `&'a i32` will have a
    /// De Bruijn index of 1. It's only during the instantiation that we can see we must increase the
    /// depth by 1 to account for the binder that we passed through.
    ///
    /// As a second example, consider this twist:
    ///
    /// ```
    /// type FuncTuple<A> = (A,fn(A));
    /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a i32>);
    /// ```
    ///
    /// Here the final type will be:
    /// ```ignore (illustrative)
    /// for<'a> fn((&'a i32, fn(&'a i32)))
    /// //          ^~~         ^~~
    /// //          |           |
    /// //   DebruijnIndex of 1 |
    /// //               DebruijnIndex of 2
    /// ```
    /// As indicated in the diagram, here the same type `&'a i32` is instantiated once, but in the
    /// first case we do not increase the De Bruijn index and in the second case we do. The reason
    /// is that only in the second case have we passed through a fn binder.
    #[instrument(level = "trace", skip(self), fields(binders_passed = self.binders_passed), ret)]
    fn shift_vars_through_binders<T: TypeFoldable<I>>(&self, val: T) -> T {
        if self.binders_passed == 0 || !val.has_escaping_bound_vars() {
            val
        } else {
            ty::shift_vars(self.cx, val, self.binders_passed)
        }
    }

    fn shift_region_through_binders(&self, region: I::Region) -> I::Region {
        if self.binders_passed == 0 || !region.has_escaping_bound_vars() {
            region
        } else {
            ty::shift_region(self.cx, region, self.binders_passed)
        }
    }
}

/// Okay, we do something fun for `Bound` types/regions/consts:
/// Specifically, we distinguish between *canonically* bound things and
/// `for<>` bound things. And, really, it comes down to caching during
/// canonicalization and instantiation.
///
/// To understand why we do this, imagine we have a type `(T, for<> fn(T))`.
/// If we just tracked canonically bound types with a `DebruijnIndex` (as we
/// used to), then the canonicalized type would be something like
/// `for<0> (^0.0, for<> fn(^1.0))` and so we can't cache `T -> ^0.0`,
/// we have to also factor in binder level. (Of course, we don't cache that
/// exactly, but rather the entire enclosing type, but the point stands.)
///
/// Of course, this is okay because we don't ever nest canonicalization, so
/// `BoundVarIndexKind::Canonical` is unambiguous. We, alternatively, could
/// have some sentinel `DebruijinIndex`, but that just seems too scary.
///
/// This doesn't seem to have a huge perf swing either way, but in the next
/// solver, canonicalization is hot and there are some pathological cases where
/// this is needed (`post-mono-higher-ranked-hang`).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "nightly", derive(Encodable_NoContext, Decodable_NoContext, StableHash))]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic)]
pub enum BoundVarIndexKind {
    Bound(DebruijnIndex),
    Canonical,
}

/// The "placeholder index" fully defines a placeholder region, type, or const. Placeholders are
/// identified by both a universe, as well as a name residing within that universe. Distinct bound
/// regions/types/consts within the same universe simply have an unknown relationship to one
#[derive_where(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash; I: Interner, T)]
#[derive(TypeVisitable_Generic, TypeFoldable_Generic, GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub struct Placeholder<I: Interner, T> {
    pub universe: UniverseIndex,
    pub bound: T,
    #[type_foldable(identity)]
    #[type_visitable(ignore)]
    _tcx: PhantomData<fn() -> I>,
}

impl<I: Interner, T: fmt::Debug> fmt::Debug for ty::Placeholder<I, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.universe == ty::UniverseIndex::ROOT {
            write!(f, "!{:?}", self.bound)
        } else {
            write!(f, "!{}_{:?}", self.universe.index(), self.bound)
        }
    }
}

impl<I: Interner, U: Interner, T> Lift<U> for Placeholder<I, T>
where
    T: Lift<U>,
{
    type Lifted = Placeholder<U, T::Lifted>;

    fn lift_to_interner(self, cx: U) -> Self::Lifted {
        Placeholder {
            universe: self.universe,
            bound: self.bound.lift_to_interner(cx),
            _tcx: PhantomData,
        }
    }
}

#[derive_where(Clone, Copy, PartialEq, Eq, Hash; I: Interner)]
#[derive(Lift_Generic, GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub enum BoundRegionKind<I: Interner> {
    /// An anonymous region parameter for a given fn (&T)
    Anon,

    /// An anonymous region parameter with a `Symbol` name.
    ///
    /// Used to give late-bound regions names for things like pretty printing.
    NamedForPrinting(I::Symbol),

    /// Late-bound regions that appear in the AST.
    Named(I::DefId),

    /// Anonymous region for the implicit env pointer parameter
    /// to a closure
    ClosureEnv,
}

impl<I: Interner> fmt::Debug for ty::BoundRegionKind<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            ty::BoundRegionKind::Anon => write!(f, "BrAnon"),
            ty::BoundRegionKind::NamedForPrinting(name) => {
                write!(f, "BrNamedForPrinting({:?})", name)
            }
            ty::BoundRegionKind::Named(did) => {
                write!(f, "BrNamed({did:?})")
            }
            ty::BoundRegionKind::ClosureEnv => write!(f, "BrEnv"),
        }
    }
}

impl<I: Interner> BoundRegionKind<I> {
    pub fn is_named(&self, tcx: I) -> bool {
        self.get_name(tcx).is_some()
    }

    pub fn get_name(&self, tcx: I) -> Option<I::Symbol> {
        match *self {
            ty::BoundRegionKind::Named(def_id) => {
                let name = tcx.item_name(def_id);
                if name.is_kw_underscore_lifetime() { None } else { Some(name) }
            }
            ty::BoundRegionKind::NamedForPrinting(name) => Some(name),
            _ => None,
        }
    }

    pub fn get_id(&self) -> Option<I::DefId> {
        match *self {
            ty::BoundRegionKind::Named(id) => Some(id),
            _ => None,
        }
    }
}

#[derive_where(Clone, Copy, PartialEq, Eq, Debug, Hash; I: Interner)]
#[derive(Lift_Generic, GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub enum BoundTyKind<I: Interner> {
    Anon,
    Param(I::DefId),
}

#[derive_where(Clone, Copy, PartialEq, Eq, Debug, Hash; I: Interner)]
#[derive(Lift_Generic, GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub enum BoundVariableKind<I: Interner> {
    Ty(BoundTyKind<I>),
    Region(BoundRegionKind<I>),
    Const,
}

impl<I: Interner> BoundVariableKind<I> {
    pub fn expect_region(self) -> BoundRegionKind<I> {
        match self {
            BoundVariableKind::Region(lt) => lt,
            _ => panic!("expected a region, but found another kind"),
        }
    }

    pub fn expect_ty(self) -> BoundTyKind<I> {
        match self {
            BoundVariableKind::Ty(ty) => ty,
            _ => panic!("expected a type, but found another kind"),
        }
    }

    pub fn expect_const(self) {
        match self {
            BoundVariableKind::Const => (),
            _ => panic!("expected a const, but found another kind"),
        }
    }
}

#[derive_where(Clone, Copy, PartialEq, Eq, Hash; I: Interner)]
#[derive(GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, StableHash_NoContext, Decodable_NoContext)
)]
pub struct BoundRegion<I: Interner> {
    pub var: ty::BoundVar,
    pub kind: BoundRegionKind<I>,
}

impl<I: Interner> core::fmt::Debug for BoundRegion<I> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.kind {
            BoundRegionKind::Anon => write!(f, "{:?}", self.var),
            BoundRegionKind::ClosureEnv => write!(f, "{:?}.Env", self.var),
            BoundRegionKind::Named(def) => {
                write!(f, "{:?}.Named({:?})", self.var, def)
            }
            BoundRegionKind::NamedForPrinting(symbol) => {
                write!(f, "{:?}.NamedAnon({:?})", self.var, symbol)
            }
        }
    }
}

impl<I: Interner> BoundRegion<I> {
    pub fn var(self) -> ty::BoundVar {
        self.var
    }

    pub fn assert_eq(self, var: BoundVariableKind<I>) {
        assert_eq!(self.kind, var.expect_region())
    }
}

pub type PlaceholderRegion<I> = ty::Placeholder<I, BoundRegion<I>>;

impl<I: Interner> PlaceholderRegion<I> {
    pub fn universe(self) -> UniverseIndex {
        self.universe
    }

    pub fn var(self) -> ty::BoundVar {
        self.bound.var()
    }

    pub fn with_updated_universe(self, ui: UniverseIndex) -> Self {
        Self { universe: ui, bound: self.bound, _tcx: PhantomData }
    }

    pub fn new(ui: UniverseIndex, bound: BoundRegion<I>) -> Self {
        Self { universe: ui, bound, _tcx: PhantomData }
    }

    pub fn new_anon(ui: UniverseIndex, var: ty::BoundVar) -> Self {
        let bound = BoundRegion { var, kind: BoundRegionKind::Anon };
        Self { universe: ui, bound, _tcx: PhantomData }
    }
}

#[derive_where(Clone, Copy, PartialEq, Eq, Hash; I: Interner)]
#[derive(GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub struct BoundTy<I: Interner> {
    pub var: ty::BoundVar,
    pub kind: BoundTyKind<I>,
}

impl<I: Interner, U: Interner> Lift<U> for BoundTy<I>
where
    BoundTyKind<I>: Lift<U, Lifted = BoundTyKind<U>>,
{
    type Lifted = BoundTy<U>;

    fn lift_to_interner(self, cx: U) -> Self::Lifted {
        BoundTy { var: self.var, kind: self.kind.lift_to_interner(cx) }
    }
}

impl<I: Interner> fmt::Debug for ty::BoundTy<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self.kind {
            ty::BoundTyKind::Anon => write!(f, "{:?}", self.var),
            ty::BoundTyKind::Param(def_id) => write!(f, "{def_id:?}"),
        }
    }
}

impl<I: Interner> BoundTy<I> {
    pub fn var(self) -> ty::BoundVar {
        self.var
    }

    pub fn assert_eq(self, var: BoundVariableKind<I>) {
        assert_eq!(self.kind, var.expect_ty())
    }
}

pub type PlaceholderType<I> = ty::Placeholder<I, BoundTy<I>>;

impl<I: Interner> PlaceholderType<I> {
    pub fn universe(self) -> UniverseIndex {
        self.universe
    }

    pub fn var(self) -> ty::BoundVar {
        self.bound.var
    }

    pub fn with_updated_universe(self, ui: UniverseIndex) -> Self {
        Self { universe: ui, bound: self.bound, _tcx: PhantomData }
    }

    pub fn new(ui: UniverseIndex, bound: BoundTy<I>) -> Self {
        Self { universe: ui, bound, _tcx: PhantomData }
    }

    pub fn new_anon(ui: UniverseIndex, var: ty::BoundVar) -> Self {
        let bound = BoundTy { var, kind: BoundTyKind::Anon };
        Self { universe: ui, bound, _tcx: PhantomData }
    }
}

#[derive_where(Clone, Copy, PartialEq, Debug, Eq, Hash; I: Interner)]
#[derive(GenericTypeVisitable)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, StableHash_NoContext)
)]
pub struct BoundConst<I: Interner> {
    pub var: ty::BoundVar,
    #[derive_where(skip(Debug))]
    pub _tcx: PhantomData<fn() -> I>,
}

impl<I: Interner> BoundConst<I> {
    pub fn var(self) -> ty::BoundVar {
        self.var
    }

    pub fn assert_eq(self, var: BoundVariableKind<I>) {
        var.expect_const()
    }

    pub fn new(var: ty::BoundVar) -> Self {
        Self { var, _tcx: PhantomData }
    }
}

pub type PlaceholderConst<I> = ty::Placeholder<I, BoundConst<I>>;

impl<I: Interner> PlaceholderConst<I> {
    pub fn universe(self) -> UniverseIndex {
        self.universe
    }

    pub fn var(self) -> ty::BoundVar {
        self.bound.var
    }

    pub fn with_updated_universe(self, ui: UniverseIndex) -> Self {
        Self { universe: ui, bound: self.bound, _tcx: PhantomData }
    }

    pub fn new(ui: UniverseIndex, bound: BoundConst<I>) -> Self {
        Self { universe: ui, bound, _tcx: PhantomData }
    }

    pub fn new_anon(ui: UniverseIndex, var: ty::BoundVar) -> Self {
        let bound = BoundConst::new(var);
        Self { universe: ui, bound, _tcx: PhantomData }
    }

    pub fn find_const_ty_from_env(self, env: I::ParamEnv) -> I::Ty {
        let mut candidates = env.caller_bounds().iter().filter_map(|clause| {
            // `ConstArgHasType` are never desugared to be higher ranked.
            match clause.kind().skip_binder() {
                ty::ClauseKind::ConstArgHasType(placeholder_ct, ty) => {
                    assert!(!(placeholder_ct, ty).has_escaping_bound_vars());

                    match placeholder_ct.kind() {
                        ty::ConstKind::Placeholder(placeholder_ct) if placeholder_ct == self => {
                            Some(ty)
                        }
                        _ => None,
                    }
                }
                _ => None,
            }
        });

        // N.B. it may be tempting to fix ICEs by making this function return
        // `Option<Ty<'tcx>>` instead of `Ty<'tcx>`; however, this is generally
        // considered to be a bandaid solution, since it hides more important
        // underlying issues with how we construct generics and predicates of
        // items. It's advised to fix the underlying issue rather than trying
        // to modify this function.
        let ty = candidates.next().unwrap_or_else(|| {
            panic!("cannot find `{self:?}` in param-env: {env:#?}");
        });
        assert!(
            candidates.next().is_none(),
            "did not expect duplicate `ConstParamHasTy` for `{self:?}` in param-env: {env:#?}"
        );
        ty
    }
}