Move folding and visiting traits into type library

10 files changed, 805 insertions, 755 deletions

diff --git a/compiler/rustc_middle/src/lib.rs b/compiler/rustc_middle/src/lib.rs
index ea57f7079f9..e6cd38c0f15 100644
--- a/compiler/rustc_middle/src/lib.rs
+++ b/compiler/rustc_middle/src/lib.rs
@@ -48,12 +48,10 @@
 #![feature(associated_type_bounds)]
 #![feature(rustc_attrs)]
 #![feature(control_flow_enum)]
-#![feature(associated_type_defaults)]
 #![feature(trusted_step)]
 #![feature(try_blocks)]
 #![feature(try_reserve_kind)]
 #![feature(nonzero_ops)]
-#![feature(unwrap_infallible)]
 #![feature(decl_macro)]
 #![feature(drain_filter)]
 #![feature(intra_doc_pointers)]
diff --git a/compiler/rustc_middle/src/macros.rs b/compiler/rustc_middle/src/macros.rs
index e096be16677..57d66ac6a03 100644
--- a/compiler/rustc_middle/src/macros.rs
+++ b/compiler/rustc_middle/src/macros.rs
@@ -100,35 +100,11 @@ macro_rules! TrivialTypeTraversalImpls {
     };
 
     ($($ty:ty,)+) => {
-        $(
-            impl<I: $crate::ty::Interner> $crate::ty::fold::ir::TypeFoldable<I> for $ty {
-                fn try_fold_with<F: $crate::ty::fold::ir::FallibleTypeFolder<I>>(
-                    self,
-                    _: &mut F,
-                ) -> ::std::result::Result<Self, F::Error> {
-                    Ok(self)
-                }
-
-                #[inline]
-                fn fold_with<F: $crate::ty::fold::ir::TypeFolder<I>>(
-                    self,
-                    _: &mut F,
-                ) -> Self {
-                    self
-                }
-            }
-
-            impl<I: $crate::ty::Interner> $crate::ty::visit::ir::TypeVisitable<I> for $ty {
-                #[inline]
-                fn visit_with<F: $crate::ty::visit::ir::TypeVisitor<I>>(
-                    &self,
-                    _: &mut F)
-                    -> ::std::ops::ControlFlow<F::BreakTy>
-                {
-                    ::std::ops::ControlFlow::Continue(())
-                }
+        TrivialTypeTraversalImpls! {
+            for<'tcx> {
+                $($ty,)+
             }
-        )+
+        }
     };
 }
 
@@ -139,145 +115,3 @@ macro_rules! TrivialTypeTraversalAndLiftImpls {
         CloneLiftImpls! { $($t)* }
     }
 }
-
-#[macro_export]
-macro_rules! EnumTypeTraversalImpl {
-    (impl<$($p:tt),*> TypeFoldable<$tcx:tt> for $s:path {
-        $($variants:tt)*
-    } $(where $($wc:tt)*)*) => {
-        impl<$($p),*> $crate::ty::fold::ir::TypeFoldable<$tcx> for $s
-            $(where $($wc)*)*
-        {
-            fn try_fold_with<V: $crate::ty::fold::ir::FallibleTypeFolder<$tcx>>(
-                self,
-                folder: &mut V,
-            ) -> ::std::result::Result<Self, V::Error> {
-                EnumTypeTraversalImpl!(@FoldVariants(self, folder) input($($variants)*) output())
-            }
-        }
-    };
-
-    (impl<$($p:tt),*> TypeVisitable<$tcx:tt> for $s:path {
-        $($variants:tt)*
-    } $(where $($wc:tt)*)*) => {
-        impl<$($p),*> $crate::ty::visit::ir::TypeVisitable<$tcx> for $s
-            $(where $($wc)*)*
-        {
-            fn visit_with<V: $crate::ty::visit::ir::TypeVisitor<$tcx>>(
-                &self,
-                visitor: &mut V,
-            ) -> ::std::ops::ControlFlow<V::BreakTy> {
-                EnumTypeTraversalImpl!(@VisitVariants(self, visitor) input($($variants)*) output())
-            }
-        }
-    };
-
-    (@FoldVariants($this:expr, $folder:expr) input() output($($output:tt)*)) => {
-        Ok(match $this {
-            $($output)*
-        })
-    };
-
-    (@FoldVariants($this:expr, $folder:expr)
-     input( ($variant:path) ( $($variant_arg:ident),* ) , $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @FoldVariants($this, $folder)
-                input($($input)*)
-                output(
-                    $variant ( $($variant_arg),* ) => {
-                        $variant (
-                            $($crate::ty::fold::ir::TypeFoldable::try_fold_with($variant_arg, $folder)?),*
-                        )
-                    }
-                    $($output)*
-                )
-        )
-    };
-
-    (@FoldVariants($this:expr, $folder:expr)
-     input( ($variant:path) { $($variant_arg:ident),* $(,)? } , $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @FoldVariants($this, $folder)
-                input($($input)*)
-                output(
-                    $variant { $($variant_arg),* } => {
-                        $variant {
-                            $($variant_arg: $crate::ty::fold::ir::TypeFoldable::fold_with(
-                                $variant_arg, $folder
-                            )?),* }
-                    }
-                    $($output)*
-                )
-        )
-    };
-
-    (@FoldVariants($this:expr, $folder:expr)
-     input( ($variant:path), $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @FoldVariants($this, $folder)
-                input($($input)*)
-                output(
-                    $variant => { $variant }
-                    $($output)*
-                )
-        )
-    };
-
-    (@VisitVariants($this:expr, $visitor:expr) input() output($($output:tt)*)) => {
-        match $this {
-            $($output)*
-        }
-    };
-
-    (@VisitVariants($this:expr, $visitor:expr)
-     input( ($variant:path) ( $($variant_arg:ident),* ) , $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @VisitVariants($this, $visitor)
-                input($($input)*)
-                output(
-                    $variant ( $($variant_arg),* ) => {
-                        $($crate::ty::visit::ir::TypeVisitable::visit_with(
-                            $variant_arg, $visitor
-                        )?;)*
-                        ::std::ops::ControlFlow::Continue(())
-                    }
-                    $($output)*
-                )
-        )
-    };
-
-    (@VisitVariants($this:expr, $visitor:expr)
-     input( ($variant:path) { $($variant_arg:ident),* $(,)? } , $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @VisitVariants($this, $visitor)
-                input($($input)*)
-                output(
-                    $variant { $($variant_arg),* } => {
-                        $($crate::ty::visit::ir::TypeVisitable::visit_with(
-                            $variant_arg, $visitor
-                        )?;)*
-                        ::std::ops::ControlFlow::Continue(())
-                    }
-                    $($output)*
-                )
-        )
-    };
-
-    (@VisitVariants($this:expr, $visitor:expr)
-     input( ($variant:path), $($input:tt)*)
-     output( $($output:tt)*) ) => {
-        EnumTypeTraversalImpl!(
-            @VisitVariants($this, $visitor)
-                input($($input)*)
-                output(
-                    $variant => { ::std::ops::ControlFlow::Continue(()) }
-                    $($output)*
-                )
-        )
-    };
-}
diff --git a/compiler/rustc_middle/src/ty/fold.rs b/compiler/rustc_middle/src/ty/fold.rs
index f973c91f10d..84bd3de0f14 100644
--- a/compiler/rustc_middle/src/ty/fold.rs
+++ b/compiler/rustc_middle/src/ty/fold.rs
@@ -1,47 +1,3 @@
-//! 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 groups of 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 each type of interest,
-//!   and defines the folding "skeleton" for these types.
-//! - `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 crate::ty::{self, Binder, BoundTy, Ty, TyCtxt, TypeVisitable};
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_hir::def_id::DefId;
@@ -54,201 +10,9 @@ pub trait TypeFolder<'tcx> = ir::TypeFolder<TyCtxt<'tcx>>;
 pub trait FallibleTypeFolder<'tcx> = ir::FallibleTypeFolder<TyCtxt<'tcx>>;
 
 pub mod ir {
-    use crate::ty::{ir::TypeVisitable, Interner};
-
-    /// 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`.
-    pub trait TypeFoldable<I: Interner>: TypeVisitable<I> {
-        /// 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 method
-        /// calls a folder method specifically for that type (such as
-        /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable`
-        /// to `TypeFolder`.
-        fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error>;
-
-        /// 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<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
-            self.try_fold_with(folder).into_ok()
-        }
-    }
-
-    // This trait is implemented for types of interest.
-    pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
-        /// Provides a default fold for a 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 {
-            self.try_super_fold_with(folder).into_ok()
-        }
-    }
-
-    /// 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.
-    ///
-    /// A blanket implementation of [`FallibleTypeFolder`] will defer to
-    /// the infallible methods of this trait to ensure that the two APIs
-    /// are coherent.
-    pub trait TypeFolder<I: Interner>: FallibleTypeFolder<I, Error = !> {
-        fn tcx(&self) -> I;
-
-        fn fold_binder<T>(&mut self, t: I::Binder<T>) -> I::Binder<T>
-        where
-            T: TypeFoldable<I>,
-            I::Binder<T>: TypeSuperFoldable<I>,
-        {
-            t.super_fold_with(self)
-        }
-
-        fn fold_ty(&mut self, t: I::Ty) -> I::Ty
-        where
-            I::Ty: TypeSuperFoldable<I>,
-        {
-            t.super_fold_with(self)
-        }
-
-        fn fold_region(&mut self, r: I::Region) -> I::Region
-        where
-            I::Region: TypeSuperFoldable<I>,
-        {
-            r.super_fold_with(self)
-        }
-
-        fn fold_const(&mut self, c: I::Const) -> I::Const
-        where
-            I::Const: TypeSuperFoldable<I>,
-        {
-            c.super_fold_with(self)
-        }
-
-        fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate
-        where
-            I::Predicate: TypeSuperFoldable<I>,
-        {
-            p.super_fold_with(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 tcx<'a>(&'a self) -> I;
-
-        fn try_fold_binder<T>(&mut self, t: I::Binder<T>) -> Result<I::Binder<T>, Self::Error>
-        where
-            T: TypeFoldable<I>,
-            I::Binder<T>: TypeSuperFoldable<I>,
-        {
-            t.try_super_fold_with(self)
-        }
-
-        fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Self::Error>
-        where
-            I::Ty: TypeSuperFoldable<I>,
-        {
-            t.try_super_fold_with(self)
-        }
-
-        fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, Self::Error>
-        where
-            I::Region: TypeSuperFoldable<I>,
-        {
-            r.try_super_fold_with(self)
-        }
-
-        fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, Self::Error>
-        where
-            I::Const: TypeSuperFoldable<I>,
-        {
-            c.try_super_fold_with(self)
-        }
-
-        fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, Self::Error>
-        where
-            I::Predicate: TypeSuperFoldable<I>,
-        {
-            p.try_super_fold_with(self)
-        }
-    }
-
-    // This blanket implementation of the fallible trait for infallible folders
-    // delegates to infallible methods to ensure coherence.
-    impl<I: Interner, F> FallibleTypeFolder<I> for F
-    where
-        F: TypeFolder<I>,
-    {
-        type Error = !;
-
-        fn tcx<'a>(&'a self) -> I {
-            TypeFolder::tcx(self)
-        }
-
-        fn try_fold_binder<T>(&mut self, t: I::Binder<T>) -> Result<I::Binder<T>, !>
-        where
-            T: TypeFoldable<I>,
-            I::Binder<T>: TypeSuperFoldable<I>,
-        {
-            Ok(self.fold_binder(t))
-        }
-
-        fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, !>
-        where
-            I::Ty: TypeSuperFoldable<I>,
-        {
-            Ok(self.fold_ty(t))
-        }
-
-        fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, !>
-        where
-            I::Region: TypeSuperFoldable<I>,
-        {
-            Ok(self.fold_region(r))
-        }
-
-        fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, !>
-        where
-            I::Const: TypeSuperFoldable<I>,
-        {
-            Ok(self.fold_const(c))
-        }
-
-        fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, !>
-        where
-            I::Predicate: TypeSuperFoldable<I>,
-        {
-            Ok(self.fold_predicate(p))
-        }
-    }
+    pub use rustc_type_ir::fold::{
+        FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable,
+    };
 }
 
 ///////////////////////////////////////////////////////////////////////////
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 351753911e5..cb5f40170ff 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -1,20 +1,19 @@
-//! This module contains implements of the `Lift` and `TypeFoldable`
-//! traits for various types in the Rust compiler. Most are written by
-//! hand, though we've recently added some macros and proc-macros to help with the tedium.
+//! This module contains implementations of the `Lift`, `TypeFoldable` and
+//! `TypeVisitable` traits for various types in the Rust compiler. Most are
+//! written by hand, though we've recently added some macros and proc-macros
+//! to help with the tedium.
 
 use crate::mir::interpret;
 use crate::mir::{Field, ProjectionKind};
 use crate::ty::fold::{ir::TypeSuperFoldable, FallibleTypeFolder, TypeFoldable};
 use crate::ty::print::{with_no_trimmed_paths, FmtPrinter, Printer};
 use crate::ty::visit::{ir::TypeSuperVisitable, TypeVisitable, TypeVisitor};
-use crate::ty::{self, ir, AliasTy, InferConst, Interner, Lift, Term, TermKind, Ty, TyCtxt};
-use rustc_data_structures::functor::IdFunctor;
+use crate::ty::{self, ir, AliasTy, InferConst, Lift, Term, TermKind, Ty, TyCtxt};
 use rustc_hir::def::Namespace;
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_target::abi::TyAndLayout;
 
 use std::fmt;
-use std::mem::ManuallyDrop;
 use std::ops::ControlFlow;
 use std::rc::Rc;
 use std::sync::Arc;
@@ -195,17 +194,27 @@ impl<'tcx> fmt::Debug for AliasTy<'tcx> {
 // Atomic structs
 //
 // For things that don't carry any arena-allocated data (and are
-// copy...), just add them to this list.
+// copy...), just add them to one of these lists as appropriat.
 
-TrivialTypeTraversalAndLiftImpls! {
+// For things for which the type library provides traversal implementations
+// for all Interners, we only need to provide a Lift implementation:
+CloneLiftImpls! {
     (),
     bool,
     usize,
-    ::rustc_target::abi::VariantIdx,
     u16,
     u32,
     u64,
     String,
+    rustc_type_ir::DebruijnIndex,
+}
+
+// For things about which the type library does not know, or does not
+// provide any traversal implementations, we need to provide both a Lift
+// implementation and traversal implementations (the latter only for
+// TyCtxt<'_> interners).
+TrivialTypeTraversalAndLiftImpls! {
+    ::rustc_target::abi::VariantIdx,
     crate::middle::region::Scope,
     crate::ty::FloatTy,
     ::rustc_ast::InlineAsmOptions,
@@ -257,7 +266,6 @@ TrivialTypeTraversalAndLiftImpls! {
     Field,
     interpret::Scalar,
     rustc_target::abi::Size,
-    rustc_type_ir::DebruijnIndex,
     ty::BoundVar,
     ty::Placeholder<ty::BoundVar>,
 }
@@ -360,7 +368,7 @@ impl<'a, 'tcx> Lift<'tcx> for ty::ParamEnv<'a> {
 }
 
 ///////////////////////////////////////////////////////////////////////////
-// TypeFoldable implementations.
+// Traversal implementations.
 
 /// AdtDefs are basically the same as a DefId.
 impl<'tcx> ir::TypeFoldable<TyCtxt<'tcx>> for ty::AdtDef<'tcx> {
@@ -375,209 +383,6 @@ impl<'tcx> ir::TypeVisitable<TyCtxt<'tcx>> for ty::AdtDef<'tcx> {
     }
 }
 
-impl<I: Interner, T: ir::TypeFoldable<I>, U: ir::TypeFoldable<I>> ir::TypeFoldable<I> for (T, U) {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(
-        self,
-        folder: &mut F,
-    ) -> Result<(T, U), F::Error> {
-        Ok((self.0.try_fold_with(folder)?, self.1.try_fold_with(folder)?))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>, U: ir::TypeVisitable<I>> ir::TypeVisitable<I>
-    for (T, U)
-{
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.0.visit_with(visitor)?;
-        self.1.visit_with(visitor)
-    }
-}
-
-impl<I: Interner, A: ir::TypeFoldable<I>, B: ir::TypeFoldable<I>, C: ir::TypeFoldable<I>>
-    ir::TypeFoldable<I> for (A, B, C)
-{
-    fn try_fold_with<F: ir::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)?,
-        ))
-    }
-}
-
-impl<I: Interner, A: ir::TypeVisitable<I>, B: ir::TypeVisitable<I>, C: ir::TypeVisitable<I>>
-    ir::TypeVisitable<I> for (A, B, C)
-{
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.0.visit_with(visitor)?;
-        self.1.visit_with(visitor)?;
-        self.2.visit_with(visitor)
-    }
-}
-
-EnumTypeTraversalImpl! {
-    impl<I, T> TypeFoldable<I> for Option<T> {
-        (Some)(a),
-        (None),
-    } where I: Interner, T: ir::TypeFoldable<I>
-}
-EnumTypeTraversalImpl! {
-    impl<I, T> TypeVisitable<I> for Option<T> {
-        (Some)(a),
-        (None),
-    } where I: Interner, T: ir::TypeVisitable<I>
-}
-
-EnumTypeTraversalImpl! {
-    impl<I, T, E> TypeFoldable<I> for Result<T, E> {
-        (Ok)(a),
-        (Err)(a),
-    } where I: Interner, T: ir::TypeFoldable<I>, E: ir::TypeFoldable<I>,
-}
-EnumTypeTraversalImpl! {
-    impl<I, T, E> TypeVisitable<I> for Result<T, E> {
-        (Ok)(a),
-        (Err)(a),
-    } where I: Interner, T: ir::TypeVisitable<I>, E: ir::TypeVisitable<I>,
-}
-
-impl<I: Interner, T: ir::TypeFoldable<I>> ir::TypeFoldable<I> for Rc<T> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(
-        mut self,
-        folder: &mut F,
-    ) -> Result<Self, F::Error> {
-        // We merely want to replace the contained `T`, if at all possible,
-        // so that we don't needlessly allocate a new `Rc` or indeed clone
-        // the contained type.
-        unsafe {
-            // First step is to ensure that we have a unique reference to
-            // the contained type, which `Rc::make_mut` will accomplish (by
-            // allocating a new `Rc` and cloning the `T` only if required).
-            // This is done *before* casting to `Rc<ManuallyDrop<T>>` so that
-            // panicking during `make_mut` does not leak the `T`.
-            Rc::make_mut(&mut self);
-
-            // Casting to `Rc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
-            // is `repr(transparent)`.
-            let ptr = Rc::into_raw(self).cast::<ManuallyDrop<T>>();
-            let mut unique = Rc::from_raw(ptr);
-
-            // Call to `Rc::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 = Rc::get_mut_unchecked(&mut unique);
-
-            // 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 = ManuallyDrop::take(slot);
-            let folded = owned.try_fold_with(folder)?;
-            *slot = ManuallyDrop::new(folded);
-
-            // Cast back to `Rc<T>`.
-            Ok(Rc::from_raw(Rc::into_raw(unique).cast()))
-        }
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for Rc<T> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        (**self).visit_with(visitor)
-    }
-}
-
-impl<I: Interner, T: ir::TypeFoldable<I>> ir::TypeFoldable<I> for Arc<T> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(
-        mut self,
-        folder: &mut F,
-    ) -> Result<Self, F::Error> {
-        // 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 self);
-
-            // Casting to `Arc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
-            // is `repr(transparent)`.
-            let ptr = Arc::into_raw(self).cast::<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_unchecked(&mut unique);
-
-            // 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 = ManuallyDrop::take(slot);
-            let folded = owned.try_fold_with(folder)?;
-            *slot = ManuallyDrop::new(folded);
-
-            // Cast back to `Arc<T>`.
-            Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
-        }
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for Arc<T> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        (**self).visit_with(visitor)
-    }
-}
-
-impl<I: Interner, T: ir::TypeFoldable<I>> ir::TypeFoldable<I> for Box<T> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
-        self.try_map_id(|value| value.try_fold_with(folder))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for Box<T> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        (**self).visit_with(visitor)
-    }
-}
-
-impl<I: Interner, T: ir::TypeFoldable<I>> ir::TypeFoldable<I> for Vec<T> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
-        self.try_map_id(|t| t.try_fold_with(folder))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for Vec<T> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.iter().try_for_each(|t| t.visit_with(visitor))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for &[T] {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.iter().try_for_each(|t| t.visit_with(visitor))
-    }
-}
-
-impl<I: Interner, T: ir::TypeFoldable<I>> ir::TypeFoldable<I> for Box<[T]> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
-        self.try_map_id(|t| t.try_fold_with(folder))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>> ir::TypeVisitable<I> for Box<[T]> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.iter().try_for_each(|t| t.visit_with(visitor))
-    }
-}
-
 impl<'tcx, T: TypeFoldable<'tcx>> ir::TypeFoldable<TyCtxt<'tcx>> for ty::Binder<'tcx, T> {
     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
         folder.try_fold_binder(self)
@@ -790,18 +595,6 @@ impl<'tcx> ir::TypeFoldable<TyCtxt<'tcx>> for &'tcx ty::List<ty::Predicate<'tcx>
     }
 }
 
-impl<I: Interner, T: ir::TypeFoldable<I>, Ix: Idx> ir::TypeFoldable<I> for IndexVec<Ix, T> {
-    fn try_fold_with<F: ir::FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
-        self.try_map_id(|x| x.try_fold_with(folder))
-    }
-}
-
-impl<I: Interner, T: ir::TypeVisitable<I>, Ix: Idx> ir::TypeVisitable<I> for IndexVec<Ix, T> {
-    fn visit_with<V: ir::TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
-        self.iter().try_for_each(|t| t.visit_with(visitor))
-    }
-}
-
 impl<'tcx> ir::TypeFoldable<TyCtxt<'tcx>> for ty::Const<'tcx> {
     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
         folder.try_fold_const(self)
diff --git a/compiler/rustc_middle/src/ty/visit.rs b/compiler/rustc_middle/src/ty/visit.rs
index 714d28e3806..8a93b59900e 100644
--- a/compiler/rustc_middle/src/ty/visit.rs
+++ b/compiler/rustc_middle/src/ty/visit.rs
@@ -1,43 +1,3 @@
-//! A visiting traversal mechanism for complex data structures that contain type
-//! information.
-//!
-//! This is a read-only traversal of the data structure.
-//!
-//! This traversal has limited flexibility. Only a small number of "types of
-//! interest" within the complex data structures can receive custom
-//! visitation. These are the ones containing the most important type-related
-//! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
-//!
-//! There are three groups of traits involved in each traversal.
-//! - `TypeVisitable`. This is implemented once for many types, including:
-//!   - Types of interest, for which the methods delegate to the visitor.
-//!   - All other types, including generic containers like `Vec` and `Option`.
-//!     It defines a "skeleton" of how they should be visited.
-//! - `TypeSuperVisitable`. This is implemented only for each type of interest,
-//!   and defines the visiting "skeleton" for these types.
-//! - `TypeVisitor`. This is implemented for each visitor. This defines how
-//!   types of interest are visited.
-//!
-//! This means each visit is a mixture of (a) generic visiting operations, and (b)
-//! custom visit operations that are specific to the visitor.
-//! - The `TypeVisitable` impls handle most of the traversal, and call into
-//!   `TypeVisitor` when they encounter a type of interest.
-//! - A `TypeVisitor` may call into another `TypeVisitable` impl, because some of
-//!   the types of interest are recursive and can contain other types of interest.
-//! - A `TypeVisitor` may also call into a `TypeSuperVisitable` impl, because each
-//!   visitor 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: TypeVisitable` and `U:
-//! TypeVisitable`, and an instance `s = S(ty, u)`, it would be visited like so:
-//! ```text
-//! s.visit_with(visitor) calls
-//! - ty.visit_with(visitor) calls
-//!   - visitor.visit_ty(ty) may call
-//!     - ty.super_visit_with(visitor)
-//! - u.visit_with(visitor)
-//! ```
 use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags};
 use rustc_errors::ErrorGuaranteed;
 
@@ -50,84 +10,7 @@ pub trait TypeSuperVisitable<'tcx> = ir::TypeSuperVisitable<TyCtxt<'tcx>>;
 pub trait TypeVisitor<'tcx> = ir::TypeVisitor<TyCtxt<'tcx>>;
 
 pub mod ir {
-    use crate::ty::Interner;
-
-    use std::fmt;
-    use std::ops::ControlFlow;
-
-    /// This trait is implemented for every type that can be visited,
-    /// providing the skeleton of the traversal.
-    ///
-    /// To implement this conveniently, use the derive macro located in
-    /// `rustc_macros`.
-    pub trait TypeVisitable<I: Interner>: fmt::Debug + Clone {
-        /// The entry point for visiting. To visit a value `t` with a visitor `v`
-        /// call: `t.visit_with(v)`.
-        ///
-        /// For most types, this just traverses the value, calling `visit_with` on
-        /// each field/element.
-        ///
-        /// For types of interest (such as `Ty`), the implementation of this method
-        /// that calls a visitor method specifically for that type (such as
-        /// `V::visit_ty`). This is where control transfers from `TypeFoldable` to
-        /// `TypeVisitor`.
-        fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
-    }
-
-    pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> {
-        /// Provides a default visit for a type of interest. This should only be
-        /// called within `TypeVisitor` methods, when a non-custom traversal is
-        /// desired for the value of the type of interest passed to that method.
-        /// For example, in `MyVisitor::visit_ty(ty)`, it is valid to call
-        /// `ty.super_visit_with(self)`, but any other visiting should be done
-        /// with `xyz.visit_with(self)`.
-        fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
-    }
-
-    /// This trait is implemented for every visiting traversal. There is a visit
-    /// method defined for every type of interest. Each such method has a default
-    /// that recurses into the type's fields in a non-custom fashion.
-    pub trait TypeVisitor<I: Interner>: Sized {
-        type BreakTy = !;
-
-        fn visit_binder<T: TypeVisitable<I>>(
-            &mut self,
-            t: &I::Binder<T>,
-        ) -> ControlFlow<Self::BreakTy>
-        where
-            I::Binder<T>: TypeSuperVisitable<I>,
-        {
-            t.super_visit_with(self)
-        }
-
-        fn visit_ty(&mut self, t: I::Ty) -> ControlFlow<Self::BreakTy>
-        where
-            I::Ty: TypeSuperVisitable<I>,
-        {
-            t.super_visit_with(self)
-        }
-
-        fn visit_region(&mut self, r: I::Region) -> ControlFlow<Self::BreakTy>
-        where
-            I::Region: TypeSuperVisitable<I>,
-        {
-            r.super_visit_with(self)
-        }
-
-        fn visit_const(&mut self, c: I::Const) -> ControlFlow<Self::BreakTy>
-        where
-            I::Const: TypeSuperVisitable<I>,
-        {
-            c.super_visit_with(self)
-        }
-
-        fn visit_predicate(&mut self, p: I::Predicate) -> ControlFlow<Self::BreakTy>
-        where
-            I::Predicate: TypeSuperVisitable<I>,
-        {
-            p.super_visit_with(self)
-        }
-    }
+    pub use rustc_type_ir::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor};
 }
 
 pub trait TypeVisitableExt<'tcx>: ir::TypeVisitable<TyCtxt<'tcx>> {
diff --git a/compiler/rustc_type_ir/src/fold.rs b/compiler/rustc_type_ir/src/fold.rs
new file mode 100644
index 00000000000..113ab36ccf1
--- /dev/null
+++ b/compiler/rustc_type_ir/src/fold.rs
@@ -0,0 +1,239 @@
+//! 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 groups of 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 each type of interest,
+//!   and defines the folding "skeleton" for these types.
+//! - `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 crate::{visit::TypeVisitable, Interner};
+
+/// 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`.
+pub trait TypeFoldable<I: Interner>: TypeVisitable<I> {
+    /// 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 method
+    /// calls a folder method specifically for that type (such as
+    /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable`
+    /// to `TypeFolder`.
+    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error>;
+
+    /// 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<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
+        self.try_fold_with(folder).into_ok()
+    }
+}
+
+// This trait is implemented for types of interest.
+pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
+    /// Provides a default fold for a 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 {
+        self.try_super_fold_with(folder).into_ok()
+    }
+}
+
+/// 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.
+///
+/// A blanket implementation of [`FallibleTypeFolder`] will defer to
+/// the infallible methods of this trait to ensure that the two APIs
+/// are coherent.
+pub trait TypeFolder<I: Interner>: FallibleTypeFolder<I, Error = !> {
+    fn tcx(&self) -> I;
+
+    fn fold_binder<T>(&mut self, t: I::Binder<T>) -> I::Binder<T>
+    where
+        T: TypeFoldable<I>,
+        I::Binder<T>: TypeSuperFoldable<I>,
+    {
+        t.super_fold_with(self)
+    }
+
+    fn fold_ty(&mut self, t: I::Ty) -> I::Ty
+    where
+        I::Ty: TypeSuperFoldable<I>,
+    {
+        t.super_fold_with(self)
+    }
+
+    fn fold_region(&mut self, r: I::Region) -> I::Region
+    where
+        I::Region: TypeSuperFoldable<I>,
+    {
+        r.super_fold_with(self)
+    }
+
+    fn fold_const(&mut self, c: I::Const) -> I::Const
+    where
+        I::Const: TypeSuperFoldable<I>,
+    {
+        c.super_fold_with(self)
+    }
+
+    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate
+    where
+        I::Predicate: TypeSuperFoldable<I>,
+    {
+        p.super_fold_with(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 tcx<'a>(&'a self) -> I;
+
+    fn try_fold_binder<T>(&mut self, t: I::Binder<T>) -> Result<I::Binder<T>, Self::Error>
+    where
+        T: TypeFoldable<I>,
+        I::Binder<T>: TypeSuperFoldable<I>,
+    {
+        t.try_super_fold_with(self)
+    }
+
+    fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Self::Error>
+    where
+        I::Ty: TypeSuperFoldable<I>,
+    {
+        t.try_super_fold_with(self)
+    }
+
+    fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, Self::Error>
+    where
+        I::Region: TypeSuperFoldable<I>,
+    {
+        r.try_super_fold_with(self)
+    }
+
+    fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, Self::Error>
+    where
+        I::Const: TypeSuperFoldable<I>,
+    {
+        c.try_super_fold_with(self)
+    }
+
+    fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, Self::Error>
+    where
+        I::Predicate: TypeSuperFoldable<I>,
+    {
+        p.try_super_fold_with(self)
+    }
+}
+
+// This blanket implementation of the fallible trait for infallible folders
+// delegates to infallible methods to ensure coherence.
+impl<I: Interner, F> FallibleTypeFolder<I> for F
+where
+    F: TypeFolder<I>,
+{
+    type Error = !;
+
+    fn tcx<'a>(&'a self) -> I {
+        TypeFolder::tcx(self)
+    }
+
+    fn try_fold_binder<T>(&mut self, t: I::Binder<T>) -> Result<I::Binder<T>, !>
+    where
+        T: TypeFoldable<I>,
+        I::Binder<T>: TypeSuperFoldable<I>,
+    {
+        Ok(self.fold_binder(t))
+    }
+
+    fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, !>
+    where
+        I::Ty: TypeSuperFoldable<I>,
+    {
+        Ok(self.fold_ty(t))
+    }
+
+    fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, !>
+    where
+        I::Region: TypeSuperFoldable<I>,
+    {
+        Ok(self.fold_region(r))
+    }
+
+    fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, !>
+    where
+        I::Const: TypeSuperFoldable<I>,
+    {
+        Ok(self.fold_const(c))
+    }
+
+    fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, !>
+    where
+        I::Predicate: TypeSuperFoldable<I>,
+    {
+        Ok(self.fold_predicate(p))
+    }
+}
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 0dc813b75f6..29d261fda8d 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -1,6 +1,10 @@
+#![feature(associated_type_defaults)]
 #![feature(fmt_helpers_for_derive)]
+#![feature(get_mut_unchecked)]
 #![feature(min_specialization)]
+#![feature(never_type)]
 #![feature(rustc_attrs)]
+#![feature(unwrap_infallible)]
 #![deny(rustc::untranslatable_diagnostic)]
 #![deny(rustc::diagnostic_outside_of_impl)]
 
@@ -18,8 +22,14 @@ use std::hash::Hash;
 use std::mem::discriminant;
 
 pub mod codec;
+pub mod fold;
 pub mod sty;
 pub mod ty_info;
+pub mod visit;
+
+#[macro_use]
+mod macros;
+mod structural_impls;
 
 pub use codec::*;
 pub use sty::*;
diff --git a/compiler/rustc_type_ir/src/macros.rs b/compiler/rustc_type_ir/src/macros.rs
new file mode 100644
index 00000000000..6c181039730
--- /dev/null
+++ b/compiler/rustc_type_ir/src/macros.rs
@@ -0,0 +1,176 @@
+/// Used for types that are `Copy` and which **do not care arena
+/// allocated data** (i.e., don't need to be folded).
+macro_rules! TrivialTypeTraversalImpls {
+    ($($ty:ty,)+) => {
+        $(
+            impl<I: $crate::Interner> $crate::fold::TypeFoldable<I> for $ty {
+                fn try_fold_with<F: $crate::fold::FallibleTypeFolder<I>>(
+                    self,
+                    _: &mut F,
+                ) -> ::std::result::Result<Self, F::Error> {
+                    Ok(self)
+                }
+
+                #[inline]
+                fn fold_with<F: $crate::fold::TypeFolder<I>>(
+                    self,
+                    _: &mut F,
+                ) -> Self {
+                    self
+                }
+            }
+
+            impl<I: $crate::Interner> $crate::visit::TypeVisitable<I> for $ty {
+                #[inline]
+                fn visit_with<F: $crate::visit::TypeVisitor<I>>(
+                    &self,
+                    _: &mut F)
+                    -> ::std::ops::ControlFlow<F::BreakTy>
+                {
+                    ::std::ops::ControlFlow::Continue(())
+                }
+            }
+        )+
+    };
+}
+
+macro_rules! EnumTypeTraversalImpl {
+    (impl<$($p:tt),*> TypeFoldable<$tcx:tt> for $s:path {
+        $($variants:tt)*
+    } $(where $($wc:tt)*)*) => {
+        impl<$($p),*> $crate::fold::TypeFoldable<$tcx> for $s
+            $(where $($wc)*)*
+        {
+            fn try_fold_with<V: $crate::fold::FallibleTypeFolder<$tcx>>(
+                self,
+                folder: &mut V,
+            ) -> ::std::result::Result<Self, V::Error> {
+                EnumTypeTraversalImpl!(@FoldVariants(self, folder) input($($variants)*) output())
+            }
+        }
+    };
+
+    (impl<$($p:tt),*> TypeVisitable<$tcx:tt> for $s:path {
+        $($variants:tt)*
+    } $(where $($wc:tt)*)*) => {
+        impl<$($p),*> $crate::visit::TypeVisitable<$tcx> for $s
+            $(where $($wc)*)*
+        {
+            fn visit_with<V: $crate::visit::TypeVisitor<$tcx>>(
+                &self,
+                visitor: &mut V,
+            ) -> ::std::ops::ControlFlow<V::BreakTy> {
+                EnumTypeTraversalImpl!(@VisitVariants(self, visitor) input($($variants)*) output())
+            }
+        }
+    };
+
+    (@FoldVariants($this:expr, $folder:expr) input() output($($output:tt)*)) => {
+        Ok(match $this {
+            $($output)*
+        })
+    };
+
+    (@FoldVariants($this:expr, $folder:expr)
+     input( ($variant:path) ( $($variant_arg:ident),* ) , $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @FoldVariants($this, $folder)
+                input($($input)*)
+                output(
+                    $variant ( $($variant_arg),* ) => {
+                        $variant (
+                            $($crate::fold::TypeFoldable::try_fold_with($variant_arg, $folder)?),*
+                        )
+                    }
+                    $($output)*
+                )
+        )
+    };
+
+    (@FoldVariants($this:expr, $folder:expr)
+     input( ($variant:path) { $($variant_arg:ident),* $(,)? } , $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @FoldVariants($this, $folder)
+                input($($input)*)
+                output(
+                    $variant { $($variant_arg),* } => {
+                        $variant {
+                            $($variant_arg: $crate::fold::TypeFoldable::fold_with(
+                                $variant_arg, $folder
+                            )?),* }
+                    }
+                    $($output)*
+                )
+        )
+    };
+
+    (@FoldVariants($this:expr, $folder:expr)
+     input( ($variant:path), $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @FoldVariants($this, $folder)
+                input($($input)*)
+                output(
+                    $variant => { $variant }
+                    $($output)*
+                )
+        )
+    };
+
+    (@VisitVariants($this:expr, $visitor:expr) input() output($($output:tt)*)) => {
+        match $this {
+            $($output)*
+        }
+    };
+
+    (@VisitVariants($this:expr, $visitor:expr)
+     input( ($variant:path) ( $($variant_arg:ident),* ) , $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @VisitVariants($this, $visitor)
+                input($($input)*)
+                output(
+                    $variant ( $($variant_arg),* ) => {
+                        $($crate::visit::TypeVisitable::visit_with(
+                            $variant_arg, $visitor
+                        )?;)*
+                        ::std::ops::ControlFlow::Continue(())
+                    }
+                    $($output)*
+                )
+        )
+    };
+
+    (@VisitVariants($this:expr, $visitor:expr)
+     input( ($variant:path) { $($variant_arg:ident),* $(,)? } , $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @VisitVariants($this, $visitor)
+                input($($input)*)
+                output(
+                    $variant { $($variant_arg),* } => {
+                        $($crate::visit::TypeVisitable::visit_with(
+                            $variant_arg, $visitor
+                        )?;)*
+                        ::std::ops::ControlFlow::Continue(())
+                    }
+                    $($output)*
+                )
+        )
+    };
+
+    (@VisitVariants($this:expr, $visitor:expr)
+     input( ($variant:path), $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumTypeTraversalImpl!(
+            @VisitVariants($this, $visitor)
+                input($($input)*)
+                output(
+                    $variant => { ::std::ops::ControlFlow::Continue(()) }
+                    $($output)*
+                )
+        )
+    };
+}
diff --git a/compiler/rustc_type_ir/src/structural_impls.rs b/compiler/rustc_type_ir/src/structural_impls.rs
new file mode 100644
index 00000000000..b6abe9a7357
--- /dev/null
+++ b/compiler/rustc_type_ir/src/structural_impls.rs
@@ -0,0 +1,238 @@
+//! This module contains implementations of the `TypeFoldable` and `TypeVisitable`
+//! traits for various types in the Rust compiler. Most are written by hand, though
+//! we've recently added some macros and proc-macros to help with the tedium.
+
+use crate::fold::{FallibleTypeFolder, TypeFoldable};
+use crate::visit::{TypeVisitable, TypeVisitor};
+use crate::Interner;
+use rustc_data_structures::functor::IdFunctor;
+use rustc_index::vec::{Idx, IndexVec};
+
+use std::mem::ManuallyDrop;
+use std::ops::ControlFlow;
+use std::rc::Rc;
+use std::sync::Arc;
+
+///////////////////////////////////////////////////////////////////////////
+// Atomic structs
+//
+// For things that don't carry any arena-allocated data (and are
+// copy...), just add them to this list.
+
+TrivialTypeTraversalImpls! {
+    (),
+    bool,
+    usize,
+    u16,
+    u32,
+    u64,
+    String,
+    crate::DebruijnIndex,
+}
+
+///////////////////////////////////////////////////////////////////////////
+// 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)?))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>, U: TypeVisitable<I>> TypeVisitable<I> for (T, U) {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.0.visit_with(visitor)?;
+        self.1.visit_with(visitor)
+    }
+}
+
+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)?,
+        ))
+    }
+}
+
+impl<I: Interner, A: TypeVisitable<I>, B: TypeVisitable<I>, C: TypeVisitable<I>> TypeVisitable<I>
+    for (A, B, C)
+{
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.0.visit_with(visitor)?;
+        self.1.visit_with(visitor)?;
+        self.2.visit_with(visitor)
+    }
+}
+
+EnumTypeTraversalImpl! {
+    impl<I, T> TypeFoldable<I> for Option<T> {
+        (Some)(a),
+        (None),
+    } where I: Interner, T: TypeFoldable<I>
+}
+EnumTypeTraversalImpl! {
+    impl<I, T> TypeVisitable<I> for Option<T> {
+        (Some)(a),
+        (None),
+    } where I: Interner, T: TypeVisitable<I>
+}
+
+EnumTypeTraversalImpl! {
+    impl<I, T, E> TypeFoldable<I> for Result<T, E> {
+        (Ok)(a),
+        (Err)(a),
+    } where I: Interner, T: TypeFoldable<I>, E: TypeFoldable<I>,
+}
+EnumTypeTraversalImpl! {
+    impl<I, T, E> TypeVisitable<I> for Result<T, E> {
+        (Ok)(a),
+        (Err)(a),
+    } where I: Interner, T: TypeVisitable<I>, E: TypeVisitable<I>,
+}
+
+impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Rc<T> {
+    fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
+        // We merely want to replace the contained `T`, if at all possible,
+        // so that we don't needlessly allocate a new `Rc` or indeed clone
+        // the contained type.
+        unsafe {
+            // First step is to ensure that we have a unique reference to
+            // the contained type, which `Rc::make_mut` will accomplish (by
+            // allocating a new `Rc` and cloning the `T` only if required).
+            // This is done *before* casting to `Rc<ManuallyDrop<T>>` so that
+            // panicking during `make_mut` does not leak the `T`.
+            Rc::make_mut(&mut self);
+
+            // Casting to `Rc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
+            // is `repr(transparent)`.
+            let ptr = Rc::into_raw(self).cast::<ManuallyDrop<T>>();
+            let mut unique = Rc::from_raw(ptr);
+
+            // Call to `Rc::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 = Rc::get_mut_unchecked(&mut unique);
+
+            // 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 = ManuallyDrop::take(slot);
+            let folded = owned.try_fold_with(folder)?;
+            *slot = ManuallyDrop::new(folded);
+
+            // Cast back to `Rc<T>`.
+            Ok(Rc::from_raw(Rc::into_raw(unique).cast()))
+        }
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Rc<T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        (**self).visit_with(visitor)
+    }
+}
+
+impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Arc<T> {
+    fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
+        // 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 self);
+
+            // Casting to `Arc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
+            // is `repr(transparent)`.
+            let ptr = Arc::into_raw(self).cast::<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_unchecked(&mut unique);
+
+            // 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 = ManuallyDrop::take(slot);
+            let folded = owned.try_fold_with(folder)?;
+            *slot = ManuallyDrop::new(folded);
+
+            // Cast back to `Arc<T>`.
+            Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
+        }
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Arc<T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        (**self).visit_with(visitor)
+    }
+}
+
+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> {
+        self.try_map_id(|value| value.try_fold_with(folder))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        (**self).visit_with(visitor)
+    }
+}
+
+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.try_map_id(|t| t.try_fold_with(folder))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Vec<T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.iter().try_for_each(|t| t.visit_with(visitor))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for &[T] {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.iter().try_for_each(|t| t.visit_with(visitor))
+    }
+}
+
+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> {
+        self.try_map_id(|t| t.try_fold_with(folder))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<[T]> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.iter().try_for_each(|t| t.visit_with(visitor))
+    }
+}
+
+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.try_map_id(|x| x.try_fold_with(folder))
+    }
+}
+
+impl<I: Interner, T: TypeVisitable<I>, Ix: Idx> TypeVisitable<I> for IndexVec<Ix, T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
+        self.iter().try_for_each(|t| t.visit_with(visitor))
+    }
+}
diff --git a/compiler/rustc_type_ir/src/visit.rs b/compiler/rustc_type_ir/src/visit.rs
new file mode 100644
index 00000000000..62239fd2006
--- /dev/null
+++ b/compiler/rustc_type_ir/src/visit.rs
@@ -0,0 +1,115 @@
+//! A visiting traversal mechanism for complex data structures that contain type
+//! information.
+//!
+//! This is a read-only traversal of the data structure.
+//!
+//! This traversal has limited flexibility. Only a small number of "types of
+//! interest" within the complex data structures can receive custom
+//! visitation. These are the ones containing the most important type-related
+//! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
+//!
+//! There are three groups of traits involved in each traversal.
+//! - `TypeVisitable`. This is implemented once for many types, including:
+//!   - Types of interest, for which the methods delegate to the visitor.
+//!   - All other types, including generic containers like `Vec` and `Option`.
+//!     It defines a "skeleton" of how they should be visited.
+//! - `TypeSuperVisitable`. This is implemented only for each type of interest,
+//!   and defines the visiting "skeleton" for these types.
+//! - `TypeVisitor`. This is implemented for each visitor. This defines how
+//!   types of interest are visited.
+//!
+//! This means each visit is a mixture of (a) generic visiting operations, and (b)
+//! custom visit operations that are specific to the visitor.
+//! - The `TypeVisitable` impls handle most of the traversal, and call into
+//!   `TypeVisitor` when they encounter a type of interest.
+//! - A `TypeVisitor` may call into another `TypeVisitable` impl, because some of
+//!   the types of interest are recursive and can contain other types of interest.
+//! - A `TypeVisitor` may also call into a `TypeSuperVisitable` impl, because each
+//!   visitor 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: TypeVisitable` and `U:
+//! TypeVisitable`, and an instance `s = S(ty, u)`, it would be visited like so:
+//! ```text
+//! s.visit_with(visitor) calls
+//! - ty.visit_with(visitor) calls
+//!   - visitor.visit_ty(ty) may call
+//!     - ty.super_visit_with(visitor)
+//! - u.visit_with(visitor)
+//! ```
+use crate::Interner;
+
+use std::fmt;
+use std::ops::ControlFlow;
+
+/// This trait is implemented for every type that can be visited,
+/// providing the skeleton of the traversal.
+///
+/// To implement this conveniently, use the derive macro located in
+/// `rustc_macros`.
+pub trait TypeVisitable<I: Interner>: fmt::Debug + Clone {
+    /// The entry point for visiting. To visit a value `t` with a visitor `v`
+    /// call: `t.visit_with(v)`.
+    ///
+    /// For most types, this just traverses the value, calling `visit_with` on
+    /// each field/element.
+    ///
+    /// For types of interest (such as `Ty`), the implementation of this method
+    /// that calls a visitor method specifically for that type (such as
+    /// `V::visit_ty`). This is where control transfers from `TypeFoldable` to
+    /// `TypeVisitor`.
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
+}
+
+pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> {
+    /// Provides a default visit for a type of interest. This should only be
+    /// called within `TypeVisitor` methods, when a non-custom traversal is
+    /// desired for the value of the type of interest passed to that method.
+    /// For example, in `MyVisitor::visit_ty(ty)`, it is valid to call
+    /// `ty.super_visit_with(self)`, but any other visiting should be done
+    /// with `xyz.visit_with(self)`.
+    fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
+}
+
+/// This trait is implemented for every visiting traversal. There is a visit
+/// method defined for every type of interest. Each such method has a default
+/// that recurses into the type's fields in a non-custom fashion.
+pub trait TypeVisitor<I: Interner>: Sized {
+    type BreakTy = !;
+
+    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &I::Binder<T>) -> ControlFlow<Self::BreakTy>
+    where
+        I::Binder<T>: TypeSuperVisitable<I>,
+    {
+        t.super_visit_with(self)
+    }
+
+    fn visit_ty(&mut self, t: I::Ty) -> ControlFlow<Self::BreakTy>
+    where
+        I::Ty: TypeSuperVisitable<I>,
+    {
+        t.super_visit_with(self)
+    }
+
+    fn visit_region(&mut self, r: I::Region) -> ControlFlow<Self::BreakTy>
+    where
+        I::Region: TypeSuperVisitable<I>,
+    {
+        r.super_visit_with(self)
+    }
+
+    fn visit_const(&mut self, c: I::Const) -> ControlFlow<Self::BreakTy>
+    where
+        I::Const: TypeSuperVisitable<I>,
+    {
+        c.super_visit_with(self)
+    }
+
+    fn visit_predicate(&mut self, p: I::Predicate) -> ControlFlow<Self::BreakTy>
+    where
+        I::Predicate: TypeSuperVisitable<I>,
+    {
+        p.super_visit_with(self)
+    }
+}