Merging upstream version 1.68.2+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 920 insertions, 0 deletions

diff --git a/vendor/chalk-ir-0.87.0/src/fold.rs b/vendor/chalk-ir-0.87.0/src/fold.rs
new file mode 100644
index 000000000..b15cbff7a
--- /dev/null
+++ b/vendor/chalk-ir-0.87.0/src/fold.rs
@@ -0,0 +1,920 @@
+//! Traits for transforming bits of IR.
+
+use crate::*;
+use std::convert::Infallible;
+use std::fmt::Debug;
+
+mod binder_impls;
+mod boring_impls;
+mod in_place;
+pub mod shift;
+mod subst;
+
+pub use self::shift::Shift;
+pub use self::subst::Subst;
+
+/// A "folder" is a transformer that can be used to make a copy of
+/// some term -- that is, some bit of IR, such as a `Goal` -- with
+/// certain changes applied. The idea is that it contains methods that
+/// let you swap types/lifetimes for new types/lifetimes; meanwhile,
+/// each bit of IR implements the `TypeFoldable` trait which, given a
+/// `FallibleTypeFolder`, will reconstruct itself, invoking the folder's
+/// methods to transform each of the types/lifetimes embedded within.
+///
+/// As the name suggests, folds performed by `FallibleTypeFolder` can
+/// fail (with type `Error`); if the folder cannot fail, consider
+/// implementing `TypeFolder` instead (which is an infallible, but
+/// otherwise equivalent, trait).
+///
+/// # Usage patterns
+///
+/// ## Substituting for free variables
+///
+/// Most of the time, though, we are not interested in adjust
+/// arbitrary types/lifetimes, but rather just free variables (even
+/// more often, just free existential variables) that appear within
+/// the term.
+///
+/// For this reason, the `FallibleTypeFolder` trait extends two other
+/// traits that contain methods that are invoked when just those particular
+///
+/// In particular, folders can intercept references to free variables
+/// (either existentially or universally quantified) and replace them
+/// with other types/lifetimes as appropriate.
+///
+/// To create a folder `F`, one never implements `FallibleTypeFolder`
+/// directly, but instead implements one of each of these three sub-traits:
+///
+/// - `FreeVarFolder` -- folds `BoundVar` instances that appear free
+///   in the term being folded (use `DefaultFreeVarFolder` to
+///   ignore/forbid these altogether)
+/// - `InferenceFolder` -- folds existential `InferenceVar` instances
+///   that appear in the term being folded (use
+///   `DefaultInferenceFolder` to ignore/forbid these altogether)
+/// - `PlaceholderFolder` -- folds universal `Placeholder` instances
+///   that appear in the term being folded (use
+///   `DefaultPlaceholderFolder` to ignore/forbid these altogether)
+///
+/// To **apply** a folder, use the `TypeFoldable::try_fold_with` method,
+/// like so
+///
+/// ```rust,ignore
+/// let x = x.try_fold_with(&mut folder, 0);
+/// ```
+pub trait FallibleTypeFolder<I: Interner> {
+    /// The type this folder returns when folding fails. This is
+    /// commonly [`NoSolution`].
+    type Error;
+
+    /// Creates a `dyn` value from this folder. Unfortunately, this
+    /// must be added manually to each impl of FallibleTypeFolder; it
+    /// permits the default implements below to create a
+    /// `&mut dyn FallibleTypeFolder` from `Self` without knowing what
+    /// `Self` is (by invoking this method). Effectively, this limits
+    /// impls of `FallibleTypeFolder` to types for which we are able to
+    /// create a dyn value (i.e., not `[T]` types).
+    fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<I, Error = Self::Error>;
+
+    /// Top-level callback: invoked for each `Ty<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `try_super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `try_fold_free_var_ty`.
+    fn try_fold_ty(
+        &mut self,
+        ty: Ty<I>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Ty<I>, Self::Error> {
+        ty.try_super_fold_with(self.as_dyn(), outer_binder)
+    }
+
+    /// Top-level callback: invoked for each `Lifetime<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `try_super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `try_fold_free_var_lifetime`.
+    fn try_fold_lifetime(
+        &mut self,
+        lifetime: Lifetime<I>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Lifetime<I>, Self::Error> {
+        lifetime.try_super_fold_with(self.as_dyn(), outer_binder)
+    }
+
+    /// Top-level callback: invoked for each `Const<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `try_super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `try_fold_free_var_const`.
+    fn try_fold_const(
+        &mut self,
+        constant: Const<I>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Const<I>, Self::Error> {
+        constant.try_super_fold_with(self.as_dyn(), outer_binder)
+    }
+
+    /// Invoked for every program clause. By default, recursively folds the goals contents.
+    fn try_fold_program_clause(
+        &mut self,
+        clause: ProgramClause<I>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<ProgramClause<I>, Self::Error> {
+        clause.try_super_fold_with(self.as_dyn(), outer_binder)
+    }
+
+    /// Invoked for every goal. By default, recursively folds the goals contents.
+    fn try_fold_goal(
+        &mut self,
+        goal: Goal<I>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Goal<I>, Self::Error> {
+        goal.try_super_fold_with(self.as_dyn(), outer_binder)
+    }
+
+    /// If overridden to return true, then folding will panic if a
+    /// free variable is encountered. This should be done if free
+    /// type/lifetime variables are not expected.
+    fn forbid_free_vars(&self) -> bool {
+        false
+    }
+
+    /// Invoked for `TyKind::BoundVar` instances that are not bound
+    /// within the type being folded over:
+    ///
+    /// - `depth` is the depth of the `TyKind::BoundVar`; this has
+    ///   been adjusted to account for binders in scope.
+    /// - `binders` is the number of binders in scope.
+    ///
+    /// This should return a type suitable for a context with
+    /// `binders` in scope.
+    fn try_fold_free_var_ty(
+        &mut self,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Ty<I>, Self::Error> {
+        if self.forbid_free_vars() {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            Ok(TyKind::<I>::BoundVar(bound_var).intern(self.interner()))
+        }
+    }
+
+    /// As `try_fold_free_var_ty`, but for lifetimes.
+    fn try_fold_free_var_lifetime(
+        &mut self,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Lifetime<I>, Self::Error> {
+        if self.forbid_free_vars() {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            Ok(LifetimeData::<I>::BoundVar(bound_var).intern(self.interner()))
+        }
+    }
+
+    /// As `try_fold_free_var_ty`, but for constants.
+    fn try_fold_free_var_const(
+        &mut self,
+        ty: Ty<I>,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Const<I>, Self::Error> {
+        if self.forbid_free_vars() {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            Ok(ConstData {
+                ty: ty.try_fold_with(self.as_dyn(), outer_binder)?,
+                value: ConstValue::<I>::BoundVar(bound_var),
+            }
+            .intern(self.interner()))
+        }
+    }
+
+    /// If overridden to return true, we will panic when a free
+    /// placeholder type/lifetime/const is encountered.
+    fn forbid_free_placeholders(&self) -> bool {
+        false
+    }
+
+    /// Invoked for each occurrence of a placeholder type; these are
+    /// used when we instantiate binders universally. Returns a type
+    /// to use instead, which should be suitably shifted to account
+    /// for `binders`.
+    ///
+    /// - `universe` is the universe of the `TypeName::ForAll` that was found
+    /// - `binders` is the number of binders in scope
+    #[allow(unused_variables)]
+    fn try_fold_free_placeholder_ty(
+        &mut self,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Ty<I>, Self::Error> {
+        if self.forbid_free_placeholders() {
+            panic!("unexpected placeholder type `{:?}`", universe)
+        } else {
+            Ok(universe.to_ty::<I>(self.interner()))
+        }
+    }
+
+    /// As with `try_fold_free_placeholder_ty`, but for lifetimes.
+    #[allow(unused_variables)]
+    fn try_fold_free_placeholder_lifetime(
+        &mut self,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Lifetime<I>, Self::Error> {
+        if self.forbid_free_placeholders() {
+            panic!("unexpected placeholder lifetime `{:?}`", universe)
+        } else {
+            Ok(universe.to_lifetime(self.interner()))
+        }
+    }
+
+    /// As with `try_fold_free_placeholder_ty`, but for constants.
+    #[allow(unused_variables)]
+    fn try_fold_free_placeholder_const(
+        &mut self,
+        ty: Ty<I>,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Const<I>, Self::Error> {
+        if self.forbid_free_placeholders() {
+            panic!("unexpected placeholder const `{:?}`", universe)
+        } else {
+            Ok(universe.to_const(
+                self.interner(),
+                ty.try_fold_with(self.as_dyn(), outer_binder)?,
+            ))
+        }
+    }
+
+    /// If overridden to return true, inference variables will trigger
+    /// panics when folded. Used when inference variables are
+    /// unexpected.
+    fn forbid_inference_vars(&self) -> bool {
+        false
+    }
+
+    /// Invoked for each occurrence of a inference type; these are
+    /// used when we instantiate binders universally. Returns a type
+    /// to use instead, which should be suitably shifted to account
+    /// for `binders`.
+    ///
+    /// - `universe` is the universe of the `TypeName::ForAll` that was found
+    /// - `binders` is the number of binders in scope
+    #[allow(unused_variables)]
+    fn try_fold_inference_ty(
+        &mut self,
+        var: InferenceVar,
+        kind: TyVariableKind,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Ty<I>, Self::Error> {
+        if self.forbid_inference_vars() {
+            panic!("unexpected inference type `{:?}`", var)
+        } else {
+            Ok(var.to_ty(self.interner(), kind))
+        }
+    }
+
+    /// As with `try_fold_inference_ty`, but for lifetimes.
+    #[allow(unused_variables)]
+    fn try_fold_inference_lifetime(
+        &mut self,
+        var: InferenceVar,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Lifetime<I>, Self::Error> {
+        if self.forbid_inference_vars() {
+            panic!("unexpected inference lifetime `'{:?}`", var)
+        } else {
+            Ok(var.to_lifetime(self.interner()))
+        }
+    }
+
+    /// As with `try_fold_inference_ty`, but for constants.
+    #[allow(unused_variables)]
+    fn try_fold_inference_const(
+        &mut self,
+        ty: Ty<I>,
+        var: InferenceVar,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Const<I>, Self::Error> {
+        if self.forbid_inference_vars() {
+            panic!("unexpected inference const `{:?}`", var)
+        } else {
+            Ok(var.to_const(
+                self.interner(),
+                ty.try_fold_with(self.as_dyn(), outer_binder)?,
+            ))
+        }
+    }
+
+    /// Gets the interner that is being folded from.
+    fn interner(&self) -> I;
+}
+
+/// A "folder" is a transformer that can be used to make a copy of
+/// some term -- that is, some bit of IR, such as a `Goal` -- with
+/// certain changes applied. The idea is that it contains methods that
+/// let you swap types/lifetimes for new types/lifetimes; meanwhile,
+/// each bit of IR implements the `TypeFoldable` trait which, given a
+/// `TypeFolder`, will reconstruct itself, invoking the folder's methods
+/// to transform each of the types/lifetimes embedded within.
+///
+/// Folds performed by `TypeFolder` cannot fail.  If folds might fail,
+/// consider implementing `FallibleTypeFolder` instead (which is a
+/// fallible, but otherwise equivalent, trait).
+///
+/// # Usage patterns
+///
+/// ## Substituting for free variables
+///
+/// Most of the time, though, we are not interested in adjust
+/// arbitrary types/lifetimes, but rather just free variables (even
+/// more often, just free existential variables) that appear within
+/// the term.
+///
+/// For this reason, the `TypeFolder` trait extends two other traits that
+/// contain methods that are invoked when just those particular
+///
+/// In particular, folders can intercept references to free variables
+/// (either existentially or universally quantified) and replace them
+/// with other types/lifetimes as appropriate.
+///
+/// To create a folder `F`, one never implements `TypeFolder` directly, but instead
+/// implements one of each of these three sub-traits:
+///
+/// - `FreeVarFolder` -- folds `BoundVar` instances that appear free
+///   in the term being folded (use `DefaultFreeVarFolder` to
+///   ignore/forbid these altogether)
+/// - `InferenceFolder` -- folds existential `InferenceVar` instances
+///   that appear in the term being folded (use
+///   `DefaultInferenceFolder` to ignore/forbid these altogether)
+/// - `PlaceholderFolder` -- folds universal `Placeholder` instances
+///   that appear in the term being folded (use
+///   `DefaultPlaceholderFolder` to ignore/forbid these altogether)
+///
+/// To **apply** a folder, use the `TypeFoldable::fold_with` method, like so
+///
+/// ```rust,ignore
+/// let x = x.fold_with(&mut folder, 0);
+/// ```
+pub trait TypeFolder<I: Interner>: FallibleTypeFolder<I, Error = Infallible> {
+    /// Creates a `dyn` value from this folder. Unfortunately, this
+    /// must be added manually to each impl of TypeFolder; it permits the
+    /// default implements below to create a `&mut dyn TypeFolder` from
+    /// `Self` without knowing what `Self` is (by invoking this
+    /// method). Effectively, this limits impls of `TypeFolder` to types
+    /// for which we are able to create a dyn value (i.e., not `[T]`
+    /// types).
+    fn as_dyn(&mut self) -> &mut dyn TypeFolder<I>;
+
+    /// Top-level callback: invoked for each `Ty<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `fold_free_var_ty`.
+    fn fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Ty<I> {
+        ty.super_fold_with(TypeFolder::as_dyn(self), outer_binder)
+    }
+
+    /// Top-level callback: invoked for each `Lifetime<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `fold_free_var_lifetime`.
+    fn fold_lifetime(&mut self, lifetime: Lifetime<I>, outer_binder: DebruijnIndex) -> Lifetime<I> {
+        lifetime.super_fold_with(TypeFolder::as_dyn(self), outer_binder)
+    }
+
+    /// Top-level callback: invoked for each `Const<I>` that is
+    /// encountered when folding. By default, invokes
+    /// `super_fold_with`, which will in turn invoke the more
+    /// specialized folding methods below, like `fold_free_var_const`.
+    fn fold_const(&mut self, constant: Const<I>, outer_binder: DebruijnIndex) -> Const<I> {
+        constant.super_fold_with(TypeFolder::as_dyn(self), outer_binder)
+    }
+
+    /// Invoked for every program clause. By default, recursively folds the goals contents.
+    fn fold_program_clause(
+        &mut self,
+        clause: ProgramClause<I>,
+        outer_binder: DebruijnIndex,
+    ) -> ProgramClause<I> {
+        clause.super_fold_with(TypeFolder::as_dyn(self), outer_binder)
+    }
+
+    /// Invoked for every goal. By default, recursively folds the goals contents.
+    fn fold_goal(&mut self, goal: Goal<I>, outer_binder: DebruijnIndex) -> Goal<I> {
+        goal.super_fold_with(TypeFolder::as_dyn(self), outer_binder)
+    }
+
+    /// If overridden to return true, then folding will panic if a
+    /// free variable is encountered. This should be done if free
+    /// type/lifetime variables are not expected.
+    fn forbid_free_vars(&self) -> bool {
+        false
+    }
+
+    /// Invoked for `TyKind::BoundVar` instances that are not bound
+    /// within the type being folded over:
+    ///
+    /// - `depth` is the depth of the `TyKind::BoundVar`; this has
+    ///   been adjusted to account for binders in scope.
+    /// - `binders` is the number of binders in scope.
+    ///
+    /// This should return a type suitable for a context with
+    /// `binders` in scope.
+    fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> {
+        if TypeFolder::forbid_free_vars(self) {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            TyKind::<I>::BoundVar(bound_var).intern(TypeFolder::interner(self))
+        }
+    }
+
+    /// As `fold_free_var_ty`, but for lifetimes.
+    fn fold_free_var_lifetime(
+        &mut self,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Lifetime<I> {
+        if TypeFolder::forbid_free_vars(self) {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            LifetimeData::<I>::BoundVar(bound_var).intern(TypeFolder::interner(self))
+        }
+    }
+
+    /// As `fold_free_var_ty`, but for constants.
+    fn fold_free_var_const(
+        &mut self,
+        ty: Ty<I>,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Const<I> {
+        if TypeFolder::forbid_free_vars(self) {
+            panic!(
+                "unexpected free variable with depth `{:?}` with outer binder {:?}",
+                bound_var, outer_binder
+            )
+        } else {
+            let bound_var = bound_var.shifted_in_from(outer_binder);
+            ConstData {
+                ty: ty.fold_with(TypeFolder::as_dyn(self), outer_binder),
+                value: ConstValue::<I>::BoundVar(bound_var),
+            }
+            .intern(TypeFolder::interner(self))
+        }
+    }
+
+    /// If overridden to return true, we will panic when a free
+    /// placeholder type/lifetime/const is encountered.
+    fn forbid_free_placeholders(&self) -> bool {
+        false
+    }
+
+    /// Invoked for each occurrence of a placeholder type; these are
+    /// used when we instantiate binders universally. Returns a type
+    /// to use instead, which should be suitably shifted to account
+    /// for `binders`.
+    ///
+    /// - `universe` is the universe of the `TypeName::ForAll` that was found
+    /// - `binders` is the number of binders in scope
+    #[allow(unused_variables)]
+    fn fold_free_placeholder_ty(
+        &mut self,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Ty<I> {
+        if TypeFolder::forbid_free_placeholders(self) {
+            panic!("unexpected placeholder type `{:?}`", universe)
+        } else {
+            universe.to_ty::<I>(TypeFolder::interner(self))
+        }
+    }
+
+    /// As with `fold_free_placeholder_ty`, but for lifetimes.
+    #[allow(unused_variables)]
+    fn fold_free_placeholder_lifetime(
+        &mut self,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Lifetime<I> {
+        if TypeFolder::forbid_free_placeholders(self) {
+            panic!("unexpected placeholder lifetime `{:?}`", universe)
+        } else {
+            universe.to_lifetime(TypeFolder::interner(self))
+        }
+    }
+
+    /// As with `fold_free_placeholder_ty`, but for constants.
+    #[allow(unused_variables)]
+    fn fold_free_placeholder_const(
+        &mut self,
+        ty: Ty<I>,
+        universe: PlaceholderIndex,
+        outer_binder: DebruijnIndex,
+    ) -> Const<I> {
+        if TypeFolder::forbid_free_placeholders(self) {
+            panic!("unexpected placeholder const `{:?}`", universe)
+        } else {
+            universe.to_const(
+                TypeFolder::interner(self),
+                ty.fold_with(TypeFolder::as_dyn(self), outer_binder),
+            )
+        }
+    }
+
+    /// If overridden to return true, inference variables will trigger
+    /// panics when folded. Used when inference variables are
+    /// unexpected.
+    fn forbid_inference_vars(&self) -> bool {
+        false
+    }
+
+    /// Invoked for each occurrence of a inference type; these are
+    /// used when we instantiate binders universally. Returns a type
+    /// to use instead, which should be suitably shifted to account
+    /// for `binders`.
+    ///
+    /// - `universe` is the universe of the `TypeName::ForAll` that was found
+    /// - `binders` is the number of binders in scope
+    #[allow(unused_variables)]
+    fn fold_inference_ty(
+        &mut self,
+        var: InferenceVar,
+        kind: TyVariableKind,
+        outer_binder: DebruijnIndex,
+    ) -> Ty<I> {
+        if TypeFolder::forbid_inference_vars(self) {
+            panic!("unexpected inference type `{:?}`", var)
+        } else {
+            var.to_ty(TypeFolder::interner(self), kind)
+        }
+    }
+
+    /// As with `fold_inference_ty`, but for lifetimes.
+    #[allow(unused_variables)]
+    fn fold_inference_lifetime(
+        &mut self,
+        var: InferenceVar,
+        outer_binder: DebruijnIndex,
+    ) -> Lifetime<I> {
+        if TypeFolder::forbid_inference_vars(self) {
+            panic!("unexpected inference lifetime `'{:?}`", var)
+        } else {
+            var.to_lifetime(TypeFolder::interner(self))
+        }
+    }
+
+    /// As with `fold_inference_ty`, but for constants.
+    #[allow(unused_variables)]
+    fn fold_inference_const(
+        &mut self,
+        ty: Ty<I>,
+        var: InferenceVar,
+        outer_binder: DebruijnIndex,
+    ) -> Const<I> {
+        if TypeFolder::forbid_inference_vars(self) {
+            panic!("unexpected inference const `{:?}`", var)
+        } else {
+            var.to_const(
+                TypeFolder::interner(self),
+                ty.fold_with(TypeFolder::as_dyn(self), outer_binder),
+            )
+        }
+    }
+
+    /// Gets the interner that is being folded from.
+    fn interner(&self) -> I;
+}
+
+/// Applies the given `TypeFolder` to a value, producing a folded result
+/// of type `Self::Result`. The result type is typically the same as
+/// the source type, but in some cases we convert from borrowed
+/// to owned as well (e.g., the folder for `&T` will fold to a fresh
+/// `T`; well, actually `T::Result`).
+pub trait TypeFoldable<I: Interner>: Debug + Sized {
+    /// Apply the given folder `folder` to `self`; `binders` is the
+    /// number of binders that are in scope when beginning the
+    /// folder. Typically `binders` starts as 0, but is adjusted when
+    /// we encounter `Binders<T>` in the IR or other similar
+    /// constructs.
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E>;
+
+    /// A convenient alternative to `try_fold_with` for use with infallible
+    /// folders. Do not override this method, to ensure coherence with
+    /// `try_fold_with`.
+    fn fold_with(self, folder: &mut dyn TypeFolder<I>, outer_binder: DebruijnIndex) -> Self {
+        self.try_fold_with(FallibleTypeFolder::as_dyn(folder), outer_binder)
+            .unwrap()
+    }
+}
+
+/// For types where "fold" invokes a callback on the `TypeFolder`, the
+/// `TypeSuperFoldable` trait captures the recursive behavior that folds all
+/// the contents of the type.
+pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
+    /// Recursively folds the value.
+    fn try_super_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E>;
+
+    /// 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(self, folder: &mut dyn TypeFolder<I>, outer_binder: DebruijnIndex) -> Self {
+        self.try_super_fold_with(FallibleTypeFolder::as_dyn(folder), outer_binder)
+            .unwrap()
+    }
+}
+
+/// "Folding" a type invokes the `try_fold_ty` method on the folder; this
+/// usually (in turn) invokes `try_super_fold_ty` to fold the individual
+/// parts.
+impl<I: Interner> TypeFoldable<I> for Ty<I> {
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        folder.try_fold_ty(self, outer_binder)
+    }
+}
+
+/// "Super fold" for a type invokes te more detailed callbacks on the type
+impl<I> TypeSuperFoldable<I> for Ty<I>
+where
+    I: Interner,
+{
+    fn try_super_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Ty<I>, E> {
+        let interner = folder.interner();
+        Ok(match self.kind(interner) {
+            TyKind::BoundVar(bound_var) => {
+                if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
+                    // This variable was bound outside of the binders
+                    // that we have traversed during folding;
+                    // therefore, it is free. Let the folder have a
+                    // crack at it.
+                    folder.try_fold_free_var_ty(bound_var1, outer_binder)?
+                } else {
+                    // This variable was bound within the binders that
+                    // we folded over, so just return a bound
+                    // variable.
+                    self
+                }
+            }
+            TyKind::Dyn(clauses) => {
+                TyKind::Dyn(clauses.clone().try_fold_with(folder, outer_binder)?)
+                    .intern(folder.interner())
+            }
+            TyKind::InferenceVar(var, kind) => {
+                folder.try_fold_inference_ty(*var, *kind, outer_binder)?
+            }
+            TyKind::Placeholder(ui) => folder.try_fold_free_placeholder_ty(*ui, outer_binder)?,
+            TyKind::Alias(proj) => TyKind::Alias(proj.clone().try_fold_with(folder, outer_binder)?)
+                .intern(folder.interner()),
+            TyKind::Function(fun) => {
+                TyKind::Function(fun.clone().try_fold_with(folder, outer_binder)?)
+                    .intern(folder.interner())
+            }
+            TyKind::Adt(id, substitution) => TyKind::Adt(
+                id.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::AssociatedType(assoc_ty, substitution) => TyKind::AssociatedType(
+                assoc_ty.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Scalar(scalar) => TyKind::Scalar(scalar.try_fold_with(folder, outer_binder)?)
+                .intern(folder.interner()),
+            TyKind::Str => TyKind::Str.intern(folder.interner()),
+            TyKind::Tuple(arity, substitution) => TyKind::Tuple(
+                *arity,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::OpaqueType(opaque_ty, substitution) => TyKind::OpaqueType(
+                opaque_ty.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Slice(substitution) => {
+                TyKind::Slice(substitution.clone().try_fold_with(folder, outer_binder)?)
+                    .intern(folder.interner())
+            }
+            TyKind::FnDef(fn_def, substitution) => TyKind::FnDef(
+                fn_def.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Ref(mutability, lifetime, ty) => TyKind::Ref(
+                mutability.try_fold_with(folder, outer_binder)?,
+                lifetime.clone().try_fold_with(folder, outer_binder)?,
+                ty.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Raw(mutability, ty) => TyKind::Raw(
+                mutability.try_fold_with(folder, outer_binder)?,
+                ty.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Never => TyKind::Never.intern(folder.interner()),
+            TyKind::Array(ty, const_) => TyKind::Array(
+                ty.clone().try_fold_with(folder, outer_binder)?,
+                const_.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Closure(id, substitution) => TyKind::Closure(
+                id.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Generator(id, substitution) => TyKind::Generator(
+                id.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness(
+                id.try_fold_with(folder, outer_binder)?,
+                substitution.clone().try_fold_with(folder, outer_binder)?,
+            )
+            .intern(folder.interner()),
+            TyKind::Foreign(id) => {
+                TyKind::Foreign(id.try_fold_with(folder, outer_binder)?).intern(folder.interner())
+            }
+            TyKind::Error => TyKind::Error.intern(folder.interner()),
+        })
+    }
+}
+
+/// "Folding" a lifetime invokes the `fold_lifetime` method on the folder; this
+/// usually (in turn) invokes `super_fold_lifetime` to fold the individual
+/// parts.
+impl<I: Interner> TypeFoldable<I> for Lifetime<I> {
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        folder.try_fold_lifetime(self, outer_binder)
+    }
+}
+
+impl<I> TypeSuperFoldable<I> for Lifetime<I>
+where
+    I: Interner,
+{
+    fn try_super_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Lifetime<I>, E> {
+        let interner = folder.interner();
+        match self.data(interner) {
+            LifetimeData::BoundVar(bound_var) => {
+                if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
+                    // This variable was bound outside of the binders
+                    // that we have traversed during folding;
+                    // therefore, it is free. Let the folder have a
+                    // crack at it.
+                    folder.try_fold_free_var_lifetime(bound_var1, outer_binder)
+                } else {
+                    // This variable was bound within the binders that
+                    // we folded over, so just return a bound
+                    // variable.
+                    Ok(self)
+                }
+            }
+            LifetimeData::InferenceVar(var) => {
+                folder.try_fold_inference_lifetime(*var, outer_binder)
+            }
+            LifetimeData::Placeholder(universe) => {
+                folder.try_fold_free_placeholder_lifetime(*universe, outer_binder)
+            }
+            LifetimeData::Static => Ok(LifetimeData::<I>::Static.intern(folder.interner())),
+            LifetimeData::Erased => Ok(LifetimeData::<I>::Erased.intern(folder.interner())),
+            LifetimeData::Phantom(void, ..) => match *void {},
+        }
+    }
+}
+
+/// "Folding" a const invokes the `fold_const` method on the folder; this
+/// usually (in turn) invokes `super_fold_const` to fold the individual
+/// parts.
+impl<I: Interner> TypeFoldable<I> for Const<I> {
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        folder.try_fold_const(self, outer_binder)
+    }
+}
+
+impl<I> TypeSuperFoldable<I> for Const<I>
+where
+    I: Interner,
+{
+    fn try_super_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Const<I>, E> {
+        let interner = folder.interner();
+        let ConstData { ref ty, ref value } = self.data(interner);
+        let mut fold_ty = || ty.clone().try_fold_with(folder, outer_binder);
+        match value {
+            ConstValue::BoundVar(bound_var) => {
+                if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
+                    folder.try_fold_free_var_const(ty.clone(), bound_var1, outer_binder)
+                } else {
+                    Ok(self)
+                }
+            }
+            ConstValue::InferenceVar(var) => {
+                folder.try_fold_inference_const(ty.clone(), *var, outer_binder)
+            }
+            ConstValue::Placeholder(universe) => {
+                folder.try_fold_free_placeholder_const(ty.clone(), *universe, outer_binder)
+            }
+            ConstValue::Concrete(ev) => Ok(ConstData {
+                ty: fold_ty()?,
+                value: ConstValue::Concrete(ConcreteConst {
+                    interned: ev.interned.clone(),
+                }),
+            }
+            .intern(folder.interner())),
+        }
+    }
+}
+
+/// Folding a goal invokes the `fold_goal` callback (which will, by
+/// default, invoke super-fold).
+impl<I: Interner> TypeFoldable<I> for Goal<I> {
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        folder.try_fold_goal(self, outer_binder)
+    }
+}
+
+/// Superfold folds recursively.
+impl<I: Interner> TypeSuperFoldable<I> for Goal<I> {
+    fn try_super_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        let interner = folder.interner();
+        Ok(Goal::new(
+            interner,
+            self.data(interner)
+                .clone()
+                .try_fold_with(folder, outer_binder)?,
+        ))
+    }
+}
+
+/// Folding a program clause invokes the `fold_program_clause`
+/// callback on the folder (which will, by default, invoke the
+/// `super_fold_with` method on the program clause).
+impl<I: Interner> TypeFoldable<I> for ProgramClause<I> {
+    fn try_fold_with<E>(
+        self,
+        folder: &mut dyn FallibleTypeFolder<I, Error = E>,
+        outer_binder: DebruijnIndex,
+    ) -> Result<Self, E> {
+        folder.try_fold_program_clause(self, outer_binder)
+    }
+}