rustc_type_ir/

fold.rs

//! A folding traversal mechanism for complex data structures that contain type
//! information.
//!
//! This is a modifying traversal. It consumes the data structure, producing a
//! (possibly) modified version of it. Both fallible and infallible versions are
//! available. The name is potentially confusing, because this traversal is more
//! like `Iterator::map` than `Iterator::fold`.
//!
//! This traversal has limited flexibility. Only a small number of "types of
//! interest" within the complex data structures can receive custom
//! modification. These are the ones containing the most important type-related
//! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
//!
//! There are three traits involved in each traversal.
//! - `TypeFoldable`. This is implemented once for many types, including:
//!   - Types of interest, for which the methods delegate to the folder.
//!   - All other types, including generic containers like `Vec` and `Option`.
//!     It defines a "skeleton" of how they should be folded.
//! - `TypeSuperFoldable`. This is implemented only for recursive types of
//!   interest, and defines the folding "skeleton" for these types. (This
//!   excludes `Region` because it is non-recursive, i.e. it never contains
//!   other types of interest.)
//! - `TypeFolder`/`FallibleTypeFolder`. One of these is implemented for each
//!   folder. This defines how types of interest are folded.
//!
//! This means each fold is a mixture of (a) generic folding operations, and (b)
//! custom fold operations that are specific to the folder.
//! - The `TypeFoldable` impls handle most of the traversal, and call into
//!   `TypeFolder`/`FallibleTypeFolder` when they encounter a type of interest.
//! - A `TypeFolder`/`FallibleTypeFolder` may call into another `TypeFoldable`
//!   impl, because some of the types of interest are recursive and can contain
//!   other types of interest.
//! - A `TypeFolder`/`FallibleTypeFolder` may also call into a `TypeSuperFoldable`
//!   impl, because each folder might provide custom handling only for some types
//!   of interest, or only for some variants of each type of interest, and then
//!   use default traversal for the remaining cases.
//!
//! For example, if you have `struct S(Ty, U)` where `S: TypeFoldable` and `U:
//! TypeFoldable`, and an instance `s = S(ty, u)`, it would be folded like so:
//! ```text
//! s.fold_with(folder) calls
//! - ty.fold_with(folder) calls
//!   - folder.fold_ty(ty) may call
//!     - ty.super_fold_with(folder)
//! - u.fold_with(folder)
//! ```

use std::convert::Infallible;
use std::mem;
use std::sync::Arc;

use rustc_index::{Idx, IndexVec};
use smallvec::SmallVec;
use thin_vec::ThinVec;
use tracing::{debug, instrument};

use crate::data_structures::DelayedMap;
use crate::inherent::*;
use crate::visit::{TypeVisitable, TypeVisitableExt as _};
use crate::{
    self as ty, Binder, BoundVarIndexKind, ClauseKind, Const, Flags, Interner, ProjectionClause,
    Region, TypeSuperVisitable,
};

/// This trait is implemented for every type that can be folded,
/// providing the skeleton of the traversal.
///
/// To implement this conveniently, use the derive macro located in
/// `rustc_macros`.
///
/// This trait is a sub-trait of `TypeVisitable`. This is because many
/// `TypeFolder` instances use the methods in `TypeVisitableExt` while folding,
/// which means in practice almost every foldable type needs to also be
/// visitable. (However, there are some types that are visitable without being
/// foldable.)
pub trait TypeFoldable<I: Interner>: TypeVisitable<I> + Clone {
    /// The entry point for folding. To fold a value `t` with a folder `f`
    /// call: `t.try_fold_with(f)`.
    ///
    /// For most types, this just traverses the value, calling `try_fold_with`
    /// on each field/element.
    ///
    /// For types of interest (such as `Ty`), the implementation of this method
    /// calls a folder method specifically for that type (such as
    /// `F::try_fold_ty`). This is where control transfers from [`TypeFoldable`]
    /// to [`FallibleTypeFolder`].
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error>;

    /// The entry point for folding. To fold a value `t` with a folder `f`
    /// call: `t.fold_with(f)`.
    ///
    /// For most types, this just traverses the value, calling `fold_with`
    /// on each field/element.
    ///
    /// For types of interest (such as `Ty`), the implementation of this method
    /// calls a folder method specifically for that type (such as
    /// `F::fold_ty`). This is where control transfers from `TypeFoldable`
    /// to `TypeFolder`.
    ///
    /// Same as [`TypeFoldable::try_fold_with`], but not fallible. Make sure to keep
    /// the behavior in sync across functions.
    fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self;
}

// This trait is implemented for types of interest.
pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
    /// Provides a default fold for a recursive type of interest. This should
    /// only be called within `TypeFolder` methods, when a non-custom traversal
    /// is desired for the value of the type of interest passed to that method.
    /// For example, in `MyFolder::try_fold_ty(ty)`, it is valid to call
    /// `ty.try_super_fold_with(self)`, but any other folding should be done
    /// with `xyz.try_fold_with(self)`.
    fn try_super_fold_with<F: FallibleTypeFolder<I>>(
        self,
        folder: &mut F,
    ) -> Result<Self, F::Error>;

    /// A convenient alternative to `try_super_fold_with` for use with
    /// infallible folders. Do not override this method, to ensure coherence
    /// with `try_super_fold_with`.
    fn super_fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self;
}

/// This trait is implemented for every infallible folding traversal. There is
/// a fold method defined for every type of interest. Each such method has a
/// default that does an "identity" fold. Implementations of these methods
/// often fall back to a `super_fold_with` method if the primary argument
/// doesn't satisfy a particular condition.
pub trait TypeFolder<I: Interner>: Sized {
    fn cx(&self) -> I;

    fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
    where
        T: TypeFoldable<I>,
    {
        t.super_fold_with(self)
    }

    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
        t.super_fold_with(self)
    }

    // The default region folder is a no-op because `Region` is non-recursive
    // and has no `super_fold_with` method to call.
    fn fold_region(&mut self, r: Region<I>) -> Region<I> {
        r
    }

    fn fold_const(&mut self, c: Const<I>) -> Const<I> {
        c.super_fold_with(self)
    }

    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
        p.super_fold_with(self)
    }

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

/// [Fold predicate](TypeFolder::fold_predicate) deliberately doesn't get access
/// to an actual predicate. This way, we can compress lists of predicates, and hide
/// this detail to folders. Instead, some type implementing this trait, [`PredicateProxy`]
/// is passed, with its limited API.
///
/// Most [`TypeFolder`]s only use `fold_predicate` to inspect type flags.
pub trait PredicateProxy<I: Interner>:
    TypeSuperFoldable<I> + TypeSuperVisitable<I> + Flags + Copy
{
    fn allow_normalization(&self) -> bool;

    /// Gets the underlying clause kind (if this predicate is a clause, otherwise `None`).
    /// The fact that it's `unchecked`, is because no attempt is made to hide implementation
    /// details. For example, in the future we may compress clauses together. Code calling
    /// `clause_kind_unchecked` will have to correctly deal with these implementation details,
    /// and have code handling any edgecase arising as a result.
    fn clause_kind_unchecked(&self) -> Option<Binder<I, ClauseKind<I>>>;

    /// If self is a projection clause, call `f` with it. The result will be rebound and returned as `Some`.
    /// Otherwise, when self is not a projection clause, `None` is returned.
    fn map_projection(
        self,
        cx: I,
        f: impl FnOnce(Binder<I, ProjectionClause<I>>) -> Binder<I, ProjectionClause<I>>,
    ) -> Option<Self>;
}

/// This trait is implemented for every folding traversal. There is a fold
/// method defined for every type of interest. Each such method has a default
/// that does an "identity" fold.
///
/// A blanket implementation of this trait (that defers to the relevant
/// method of [`TypeFolder`]) is provided for all infallible folders in
/// order to ensure the two APIs are coherent.
pub trait FallibleTypeFolder<I: Interner>: Sized {
    type Error;

    fn cx(&self) -> I;

    fn try_fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> Result<ty::Binder<I, T>, Self::Error>
    where
        T: TypeFoldable<I>,
    {
        t.try_super_fold_with(self)
    }

    fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Self::Error> {
        t.try_super_fold_with(self)
    }

    // The default region folder is a no-op because `Region` is non-recursive
    // and has no `super_fold_with` method to call.
    fn try_fold_region(&mut self, r: Region<I>) -> Result<Region<I>, Self::Error> {
        Ok(r)
    }

    fn try_fold_const(&mut self, c: Const<I>) -> Result<Const<I>, Self::Error> {
        c.try_super_fold_with(self)
    }

    fn try_fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> Result<P, Self::Error> {
        p.try_super_fold_with(self)
    }

    fn try_fold_clauses(&mut self, c: I::Clauses) -> Result<I::Clauses, Self::Error> {
        c.try_super_fold_with(self)
    }
}

///////////////////////////////////////////////////////////////////////////
// Traversal implementations.

impl<I: Interner, T: TypeFoldable<I>, U: TypeFoldable<I>> TypeFoldable<I> for (T, U) {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<(T, U), F::Error> {
        Ok((self.0.try_fold_with(folder)?, self.1.try_fold_with(folder)?))
    }

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

impl<I: Interner, A: TypeFoldable<I>, B: TypeFoldable<I>, C: TypeFoldable<I>> TypeFoldable<I>
    for (A, B, C)
{
    fn try_fold_with<F: FallibleTypeFolder<I>>(
        self,
        folder: &mut F,
    ) -> Result<(A, B, C), F::Error> {
        Ok((
            self.0.try_fold_with(folder)?,
            self.1.try_fold_with(folder)?,
            self.2.try_fold_with(folder)?,
        ))
    }

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

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Option<T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        Ok(match self {
            Some(v) => Some(v.try_fold_with(folder)?),
            None => None,
        })
    }

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

impl<I: Interner, T: TypeFoldable<I>, E: TypeFoldable<I>> TypeFoldable<I> for Result<T, E> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        Ok(match self {
            Ok(v) => Ok(v.try_fold_with(folder)?),
            Err(e) => Err(e.try_fold_with(folder)?),
        })
    }

    fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
        match self {
            Ok(v) => Ok(v.fold_with(folder)),
            Err(e) => Err(e.fold_with(folder)),
        }
    }
}

fn fold_arc<T: Clone, E>(
    mut arc: Arc<T>,
    fold: impl FnOnce(T) -> Result<T, E>,
) -> Result<Arc<T>, E> {
    // We merely want to replace the contained `T`, if at all possible,
    // so that we don't needlessly allocate a new `Arc` or indeed clone
    // the contained type.
    unsafe {
        // First step is to ensure that we have a unique reference to
        // the contained type, which `Arc::make_mut` will accomplish (by
        // allocating a new `Arc` and cloning the `T` only if required).
        // This is done *before* casting to `Arc<ManuallyDrop<T>>` so that
        // panicking during `make_mut` does not leak the `T`.
        Arc::make_mut(&mut arc);

        // Casting to `Arc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
        // is `repr(transparent)`.
        let ptr = Arc::into_raw(arc).cast::<mem::ManuallyDrop<T>>();
        let mut unique = Arc::from_raw(ptr);

        // Call to `Arc::make_mut` above guarantees that `unique` is the
        // sole reference to the contained value, so we can avoid doing
        // a checked `get_mut` here.
        let slot = Arc::get_mut(&mut unique).unwrap_unchecked();

        // Semantically move the contained type out from `unique`, fold
        // it, then move the folded value back into `unique`. Should
        // folding fail, `ManuallyDrop` ensures that the "moved-out"
        // value is not re-dropped.
        let owned = mem::ManuallyDrop::take(slot);
        let folded = fold(owned)?;
        *slot = mem::ManuallyDrop::new(folded);

        // Cast back to `Arc<T>`.
        Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
    }
}

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

    fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
        match fold_arc::<T, Infallible>(self, |t| Ok(t.fold_with(folder))) {
            Ok(t) => t,
        }
    }
}

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
        *self = (*self).try_fold_with(folder)?;
        Ok(self)
    }

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

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Vec<T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
    }

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

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for ThinVec<T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
    }

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

impl<I: Interner, T: TypeFoldable<I>, const N: usize> TypeFoldable<I> for SmallVec<[T; N]> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
    }

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

impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<[T]> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        Vec::from(self).try_fold_with(folder).map(Vec::into_boxed_slice)
    }

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

impl<I: Interner, T: TypeFoldable<I>, Ix: Idx> TypeFoldable<I> for IndexVec<Ix, T> {
    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
        self.raw.try_fold_with(folder).map(IndexVec::from_raw)
    }

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

///////////////////////////////////////////////////////////////////////////
// Shifter
//
// Shifts the De Bruijn indices on all escaping bound vars by a
// fixed amount. Useful in instantiation or when otherwise introducing
// a binding level that is not intended to capture the existing bound
// vars. See comment on `shift_vars_through_binders` method in
// `rustc_middle/src/ty/generic_args.rs` for more details.

struct Shifter<I: Interner> {
    cx: I,
    current_index: ty::DebruijnIndex,
    amount: u32,
}

impl<I: Interner> Shifter<I> {
    fn new(cx: I, amount: u32) -> Self {
        Shifter { cx, current_index: ty::INNERMOST, amount }
    }
}

impl<I: Interner> TypeFolder<I> for Shifter<I> {
    fn cx(&self) -> I {
        self.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: Region<I>) -> Region<I> {
        match r.kind() {
            ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), br)
                if debruijn >= self.current_index =>
            {
                let debruijn = debruijn.shifted_in(self.amount);
                Region::new_bound(self.cx, debruijn, br)
            }
            _ => r,
        }
    }

    fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
        match ty.kind() {
            ty::Bound(BoundVarIndexKind::Bound(debruijn), bound_ty)
                if debruijn >= self.current_index =>
            {
                let debruijn = debruijn.shifted_in(self.amount);
                Ty::new_bound(self.cx, debruijn, bound_ty)
            }

            _ if ty.has_vars_bound_at_or_above(self.current_index) => ty.super_fold_with(self),
            _ => ty,
        }
    }

    fn fold_const(&mut self, ct: Const<I>) -> Const<I> {
        match ct.kind() {
            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_ct)
                if debruijn >= self.current_index =>
            {
                let debruijn = debruijn.shifted_in(self.amount);
                Const::new_bound(self.cx, debruijn, bound_ct)
            }
            _ => ct.super_fold_with(self),
        }
    }

    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
    }

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

pub fn shift_region<I: Interner>(cx: I, region: Region<I>, amount: u32) -> Region<I> {
    match region.kind() {
        ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), br) if amount > 0 => {
            Region::new_bound(cx, debruijn.shifted_in(amount), br)
        }
        _ => region,
    }
}

#[instrument(level = "trace", skip(cx), ret)]
pub fn shift_vars<I: Interner, T>(cx: I, value: T, amount: u32) -> T
where
    T: TypeFoldable<I>,
{
    if amount == 0 || !value.has_escaping_bound_vars() {
        value
    } else {
        value.fold_with(&mut Shifter::new(cx, amount))
    }
}

///////////////////////////////////////////////////////////////////////////
// Bound variable replacer

/// A delegate used when instantiating bound vars.
///
/// Each bound variable must always map to the same result. `BoundVarReplacer`
/// caches folded types and may not call the delegate on every visit.
pub trait BoundVarReplacerDelegate<I: Interner> {
    fn replace_region(&mut self, br: ty::BoundRegion<I>) -> Region<I>;
    fn replace_ty(&mut self, bt: ty::BoundTy<I>) -> I::Ty;
    fn replace_const(&mut self, bc: ty::BoundConst<I>) -> Const<I>;
}

/// A simple delegate taking three mutable functions.
pub struct FnMutDelegate<'a, I: Interner> {
    pub regions: &'a mut (dyn FnMut(ty::BoundRegion<I>) -> Region<I> + 'a),
    pub types: &'a mut (dyn FnMut(ty::BoundTy<I>) -> I::Ty + 'a),
    pub consts: &'a mut (dyn FnMut(ty::BoundConst<I>) -> Const<I> + 'a),
}

impl<I: Interner> BoundVarReplacerDelegate<I> for FnMutDelegate<'_, I> {
    fn replace_region(&mut self, br: ty::BoundRegion<I>) -> Region<I> {
        (self.regions)(br)
    }

    fn replace_ty(&mut self, bt: ty::BoundTy<I>) -> I::Ty {
        (self.types)(bt)
    }

    fn replace_const(&mut self, bc: ty::BoundConst<I>) -> Const<I> {
        (self.consts)(bc)
    }
}

/// Replaces escaping bound vars in a value.
pub struct BoundVarReplacer<I: Interner, D> {
    cx: I,
    /// As with `RegionFolder`, represents the index of a binder *just outside*
    /// the ones we have visited.
    current_index: ty::DebruijnIndex,
    delegate: D,
    // Types can appear at different binder depths, so include the depth
    // in the cache key.
    cache: DelayedMap<(ty::DebruijnIndex, I::Ty), I::Ty>,
}

impl<I: Interner, D: BoundVarReplacerDelegate<I>> BoundVarReplacer<I, D> {
    pub fn new(cx: I, delegate: D) -> Self {
        Self { cx, current_index: ty::INNERMOST, delegate, cache: Default::default() }
    }
}

impl<I: Interner, D: BoundVarReplacerDelegate<I>> TypeFolder<I> for BoundVarReplacer<I, D> {
    fn cx(&self) -> I {
        self.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_ty(&mut self, t: I::Ty) -> I::Ty {
        match t.kind() {
            ty::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_ty)
                if debruijn == self.current_index =>
            {
                let ty = self.delegate.replace_ty(bound_ty);
                debug_assert!(!ty.has_vars_bound_above(ty::INNERMOST));
                shift_vars(self.cx, ty, self.current_index.as_u32())
            }
            _ => {
                if !t.has_vars_bound_at_or_above(self.current_index) {
                    t
                } else if let Some(&t) = self.cache.get(&(self.current_index, t)) {
                    t
                } else {
                    let res = t.super_fold_with(self);
                    assert!(self.cache.insert((self.current_index, t), res));
                    res
                }
            }
        }
    }

    fn fold_region(&mut self, r: Region<I>) -> Region<I> {
        match r.kind() {
            ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), br)
                if debruijn == self.current_index =>
            {
                let region = self.delegate.replace_region(br);
                if let ty::ReBound(ty::BoundVarIndexKind::Bound(inner), br) = region.kind() {
                    // Bound regions returned by the delegate use INNERMOST.
                    // Adjust them to the current binder depth.
                    assert_eq!(inner, ty::INNERMOST);
                    Region::new_bound(self.cx, debruijn, br)
                } else {
                    region
                }
            }
            _ => r,
        }
    }

    fn fold_const(&mut self, ct: Const<I>) -> Const<I> {
        match ct.kind() {
            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_const)
                if debruijn == self.current_index =>
            {
                let ct = self.delegate.replace_const(bound_const);
                debug_assert!(!ct.has_vars_bound_above(ty::INNERMOST));
                shift_vars(self.cx, ct, self.current_index.as_u32())
            }
            _ => ct.super_fold_with(self),
        }
    }

    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
    }

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

/// Replaces escaping bound vars using `delegate`.
pub fn replace_escaping_bound_vars_uncached<I: Interner, T: TypeFoldable<I>>(
    cx: I,
    value: T,
    delegate: impl BoundVarReplacerDelegate<I>,
) -> T {
    if !value.has_escaping_bound_vars() {
        value
    } else {
        value.fold_with(&mut BoundVarReplacer::new(cx, delegate))
    }
}

/// Shifts escaping bound-variable indices by `bound_vars` without changing
/// their De Bruijn depth.
pub fn shift_bound_var_indices<I: Interner, T: TypeFoldable<I>>(
    cx: I,
    bound_vars: usize,
    value: T,
) -> T {
    if bound_vars == 0 || !value.has_escaping_bound_vars() {
        return value;
    }

    let shift_bv = |bv: ty::BoundVar| bv + bound_vars;
    replace_escaping_bound_vars_uncached(
        cx,
        value,
        FnMutDelegate {
            regions: &mut |r: ty::BoundRegion<I>| {
                Region::new_bound(
                    cx,
                    ty::INNERMOST,
                    ty::BoundRegion { var: shift_bv(r.var), kind: r.kind },
                )
            },
            types: &mut |t: ty::BoundTy<I>| {
                Ty::new_bound(cx, ty::INNERMOST, ty::BoundTy { var: shift_bv(t.var), kind: t.kind })
            },
            consts: &mut |c: ty::BoundConst<I>| {
                Const::new_bound(cx, ty::INNERMOST, ty::BoundConst::new(shift_bv(c.var)))
            },
        },
    )
}

///////////////////////////////////////////////////////////////////////////
// Region folder

pub fn fold_regions<I: Interner, T>(
    cx: I,
    value: T,
    f: impl FnMut(Region<I>, ty::DebruijnIndex) -> Region<I>,
) -> T
where
    T: TypeFoldable<I>,
{
    value.fold_with(&mut RegionFolder::new(cx, f))
}

/// Folds over the substructure of a type, visiting its component
/// types and all regions that occur *free* within it.
///
/// That is, function pointer types and trait objects can introduce
/// new bound regions which are not visited by this visitor as
/// they are not free; only regions that occur free will be
/// visited by `fold_region_fn`.
pub struct RegionFolder<I, F> {
    cx: I,

    /// Stores the index of a binder *just outside* the stuff we have
    /// visited. So this begins as INNERMOST; when we pass through a
    /// binder, it is incremented (via `shift_in`).
    current_index: ty::DebruijnIndex,

    /// Callback invoked for each free region. The `DebruijnIndex`
    /// points to the binder *just outside* the ones we have passed
    /// through.
    fold_region_fn: F,
}

impl<I, F> RegionFolder<I, F> {
    #[inline]
    pub fn new(cx: I, fold_region_fn: F) -> RegionFolder<I, F> {
        RegionFolder { cx, current_index: ty::INNERMOST, fold_region_fn }
    }
}

impl<I, F> TypeFolder<I> for RegionFolder<I, F>
where
    I: Interner,
    F: FnMut(Region<I>, ty::DebruijnIndex) -> Region<I>,
{
    fn cx(&self) -> I {
        self.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
    }

    #[instrument(skip(self), level = "debug", ret)]
    fn fold_region(&mut self, r: Region<I>) -> Region<I> {
        match r.kind() {
            ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), _)
                if debruijn < self.current_index =>
            {
                debug!(?self.current_index, "skipped bound region");
                r
            }
            ty::ReBound(ty::BoundVarIndexKind::Canonical, _) => {
                debug!(?self.current_index, "skipped bound region");
                r
            }
            _ => {
                debug!(?self.current_index, "folding free region");
                (self.fold_region_fn)(r, self.current_index)
            }
        }
    }

    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
        if t.has_regions() { t.super_fold_with(self) } else { t }
    }

    fn fold_const(&mut self, ct: Const<I>) -> Const<I> {
        if ct.has_regions() { ct.super_fold_with(self) } else { ct }
    }

    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
        if p.has_regions() { p.super_fold_with(self) } else { p }
    }

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

/// This function should ideally only be used if either the `TypingMode`
/// or the `ParamEnv` differs from the environment the aliases were normalized
/// in.
///
/// Cases outside these two should consider whether the problem can be
/// fixed at the root instead.
pub fn set_aliases_to_non_rigid<I: Interner, T>(cx: I, value: T) -> ty::Unnormalized<I, T>
where
    T: TypeFoldable<I>,
{
    let folded = set_aliases_rigidness_with_mode(cx, value, RigidnessFoldMode::AllToNonRigid);
    ty::Unnormalized::new(folded)
}

pub fn set_opaques_to_non_rigid<I: Interner, T>(cx: I, value: T) -> ty::Unnormalized<I, T>
where
    T: TypeFoldable<I>,
{
    let folded = set_aliases_rigidness_with_mode(cx, value, RigidnessFoldMode::OpaqueToNonRigid);
    ty::Unnormalized::new(folded)
}

pub fn set_aliases_to_rigid<I: Interner, T>(cx: I, value: T) -> T
where
    T: TypeFoldable<I>,
{
    set_aliases_rigidness_with_mode(cx, value, RigidnessFoldMode::AllToRigid)
}

pub fn set_type_aliases_to_rigid<I: Interner, T>(cx: I, value: T) -> T
where
    T: TypeFoldable<I>,
{
    set_aliases_rigidness_with_mode(cx, value, RigidnessFoldMode::TypeToRigid)
}

fn set_aliases_rigidness_with_mode<I: Interner, T>(cx: I, value: T, mode: RigidnessFoldMode) -> T
where
    T: TypeFoldable<I>,
{
    if !mode.needs_change(&value) {
        return value;
    }

    let mut folder = RigidnessFolder { cx, mode };
    value.fold_with(&mut folder)
}

enum RigidnessFoldMode {
    AllToRigid,
    AllToNonRigid,
    TypeToRigid,
    OpaqueToNonRigid,
}

impl RigidnessFoldMode {
    fn needs_change<I: Interner, T: TypeVisitable<I>>(&self, v: &T) -> bool {
        match self {
            RigidnessFoldMode::AllToRigid => v.has_non_rigid_aliases(),
            RigidnessFoldMode::AllToNonRigid => v.has_rigid_aliases(),
            RigidnessFoldMode::TypeToRigid => {
                v.has_non_rigid_aliases()
                    && v.has_type_flags(ty::TypeFlags::HAS_ALIAS - ty::TypeFlags::HAS_CONST_ALIAS)
            }
            RigidnessFoldMode::OpaqueToNonRigid => v.has_rigid_aliases() && v.has_opaque_types(),
        }
    }
}

// Set aliases to be rigid or non-rigid according to the mode.
struct RigidnessFolder<I: Interner> {
    cx: I,
    mode: RigidnessFoldMode,
}

impl<I: Interner> TypeFolder<I> for RigidnessFolder<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> {
        if self.mode.needs_change(&t) { t.super_fold_with(self) } else { t }
    }

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

        match t.kind() {
            ty::Alias(is_rigid, alias_ty) => {
                let alias_ty = alias_ty.fold_with(self);
                match self.mode {
                    RigidnessFoldMode::AllToRigid | RigidnessFoldMode::TypeToRigid => {
                        I::Ty::new_alias(self.cx(), ty::IsRigid::Yes, alias_ty)
                    }
                    RigidnessFoldMode::AllToNonRigid => {
                        I::Ty::new_alias(self.cx(), ty::IsRigid::No, alias_ty)
                    }
                    RigidnessFoldMode::OpaqueToNonRigid => {
                        if let ty::AliasTyKind::Opaque { .. } = alias_ty.kind {
                            I::Ty::new_alias(self.cx(), ty::IsRigid::No, alias_ty)
                        } else {
                            I::Ty::new_alias(self.cx(), is_rigid, alias_ty)
                        }
                    }
                }
            }
            _ => t.super_fold_with(self),
        }
    }

    fn fold_const(&mut self, c: Const<I>) -> Const<I> {
        if !self.mode.needs_change(&c) {
            return c;
        }

        match c.kind() {
            ty::ConstKind::Alias(is_rigid, alias_const) => {
                let alias_const = alias_const.fold_with(self);
                match self.mode {
                    RigidnessFoldMode::AllToRigid => {
                        Const::new_alias(self.cx, ty::IsRigid::Yes, alias_const)
                    }
                    RigidnessFoldMode::AllToNonRigid => {
                        Const::new_alias(self.cx(), ty::IsRigid::No, alias_const)
                    }
                    RigidnessFoldMode::OpaqueToNonRigid | RigidnessFoldMode::TypeToRigid => {
                        Const::new_alias(self.cx(), is_rigid, alias_const)
                    }
                }
            }
            _ => c.super_fold_with(self),
        }
    }

    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
        if self.mode.needs_change(&p) { p.super_fold_with(self) } else { p }
    }

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