Move FlagComputation, PatternKind, and TypeWalker to rustc_type_ir

16 files changed, 531 insertions, 468 deletions

diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs
index 98273a05446..d1bbb0598fe 100644
--- a/compiler/rustc_middle/src/arena.rs
+++ b/compiler/rustc_middle/src/arena.rs
@@ -89,7 +89,6 @@ macro_rules! arena_types {
             [] name_set: rustc_data_structures::unord::UnordSet<rustc_span::Symbol>,
             [] autodiff_item: rustc_ast::expand::autodiff_attrs::AutoDiffItem,
             [] ordered_name_set: rustc_data_structures::fx::FxIndexSet<rustc_span::Symbol>,
-            [] pats: rustc_middle::ty::PatternKind<'tcx>,
             [] valtree: rustc_middle::ty::ValTreeKind<'tcx>,
 
             // Note that this deliberately duplicates items in the `rustc_hir::arena`,
diff --git a/compiler/rustc_middle/src/ty/consts.rs b/compiler/rustc_middle/src/ty/consts.rs
index ae1c6c670cb..dc5fe2d8f8b 100644
--- a/compiler/rustc_middle/src/ty/consts.rs
+++ b/compiler/rustc_middle/src/ty/consts.rs
@@ -3,6 +3,7 @@ use std::borrow::Cow;
 use rustc_data_structures::intern::Interned;
 use rustc_error_messages::MultiSpan;
 use rustc_macros::HashStable;
+use rustc_type_ir::walk::TypeWalker;
 use rustc_type_ir::{self as ir, TypeFlags, WithCachedTypeInfo};
 
 use crate::ty::{self, Ty, TyCtxt};
@@ -243,4 +244,18 @@ impl<'tcx> Const<'tcx> {
     pub fn is_ct_infer(self) -> bool {
         matches!(self.kind(), ty::ConstKind::Infer(_))
     }
+
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```text
+    /// isize => { isize }
+    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
+    /// [isize] => { [isize], isize }
+    /// ```
+    pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> {
+        TypeWalker::new(self.into())
+    }
 }
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index abf6cbbcd87..6e5ac13bd2c 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -870,7 +870,7 @@ impl<'tcx> CtxtInterners<'tcx> {
         Ty(Interned::new_unchecked(
             self.type_
                 .intern(kind, |kind| {
-                    let flags = super::flags::FlagComputation::for_kind(&kind);
+                    let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_kind(&kind);
                     let stable_hash = self.stable_hash(&flags, sess, untracked, &kind);
 
                     InternedInSet(self.arena.alloc(WithCachedTypeInfo {
@@ -896,7 +896,7 @@ impl<'tcx> CtxtInterners<'tcx> {
         Const(Interned::new_unchecked(
             self.const_
                 .intern(kind, |kind: ty::ConstKind<'_>| {
-                    let flags = super::flags::FlagComputation::for_const_kind(&kind);
+                    let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_const_kind(&kind);
                     let stable_hash = self.stable_hash(&flags, sess, untracked, &kind);
 
                     InternedInSet(self.arena.alloc(WithCachedTypeInfo {
@@ -912,7 +912,7 @@ impl<'tcx> CtxtInterners<'tcx> {
 
     fn stable_hash<'a, T: HashStable<StableHashingContext<'a>>>(
         &self,
-        flags: &ty::flags::FlagComputation,
+        flags: &ty::FlagComputation<TyCtxt<'tcx>>,
         sess: &'a Session,
         untracked: &'a Untracked,
         val: &T,
@@ -940,7 +940,7 @@ impl<'tcx> CtxtInterners<'tcx> {
         Predicate(Interned::new_unchecked(
             self.predicate
                 .intern(kind, |kind| {
-                    let flags = super::flags::FlagComputation::for_predicate(kind);
+                    let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_predicate(kind);
 
                     let stable_hash = self.stable_hash(&flags, sess, untracked, &kind);
 
@@ -961,7 +961,7 @@ impl<'tcx> CtxtInterners<'tcx> {
         } else {
             self.clauses
                 .intern_ref(clauses, || {
-                    let flags = super::flags::FlagComputation::for_clauses(clauses);
+                    let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_clauses(clauses);
 
                     InternedInSet(ListWithCachedTypeInfo::from_arena(
                         &*self.arena,
diff --git a/compiler/rustc_middle/src/ty/flags.rs b/compiler/rustc_middle/src/ty/flags.rs
deleted file mode 100644
index 2424923fb78..00000000000
--- a/compiler/rustc_middle/src/ty/flags.rs
+++ /dev/null
@@ -1,359 +0,0 @@
-use std::slice;
-
-use crate::ty::{self, GenericArg, GenericArgKind, InferConst, Ty, TypeFlags};
-
-#[derive(Debug)]
-pub struct FlagComputation {
-    pub flags: TypeFlags,
-
-    /// see `Ty::outer_exclusive_binder` for details
-    pub outer_exclusive_binder: ty::DebruijnIndex,
-}
-
-impl FlagComputation {
-    fn new() -> FlagComputation {
-        FlagComputation { flags: TypeFlags::empty(), outer_exclusive_binder: ty::INNERMOST }
-    }
-
-    #[allow(rustc::usage_of_ty_tykind)]
-    pub fn for_kind(kind: &ty::TyKind<'_>) -> FlagComputation {
-        let mut result = FlagComputation::new();
-        result.add_kind(kind);
-        result
-    }
-
-    pub fn for_predicate(binder: ty::Binder<'_, ty::PredicateKind<'_>>) -> FlagComputation {
-        let mut result = FlagComputation::new();
-        result.add_predicate(binder);
-        result
-    }
-
-    pub fn for_const_kind(kind: &ty::ConstKind<'_>) -> FlagComputation {
-        let mut result = FlagComputation::new();
-        result.add_const_kind(kind);
-        result
-    }
-
-    pub fn for_clauses(clauses: &[ty::Clause<'_>]) -> FlagComputation {
-        let mut result = FlagComputation::new();
-        for c in clauses {
-            result.add_flags(c.as_predicate().flags());
-            result.add_exclusive_binder(c.as_predicate().outer_exclusive_binder());
-        }
-        result
-    }
-
-    fn add_flags(&mut self, flags: TypeFlags) {
-        self.flags = self.flags | flags;
-    }
-
-    /// indicates that `self` refers to something at binding level `binder`
-    fn add_bound_var(&mut self, binder: ty::DebruijnIndex) {
-        let exclusive_binder = binder.shifted_in(1);
-        self.add_exclusive_binder(exclusive_binder);
-    }
-
-    /// indicates that `self` refers to something *inside* binding
-    /// level `binder` -- not bound by `binder`, but bound by the next
-    /// binder internal to it
-    fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) {
-        self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder);
-    }
-
-    /// Adds the flags/depth from a set of types that appear within the current type, but within a
-    /// region binder.
-    fn bound_computation<T, F>(&mut self, value: ty::Binder<'_, T>, f: F)
-    where
-        F: FnOnce(&mut Self, T),
-    {
-        let mut computation = FlagComputation::new();
-
-        if !value.bound_vars().is_empty() {
-            computation.add_flags(TypeFlags::HAS_BINDER_VARS);
-        }
-
-        f(&mut computation, value.skip_binder());
-
-        self.add_flags(computation.flags);
-
-        // The types that contributed to `computation` occurred within
-        // a region binder, so subtract one from the region depth
-        // within when adding the depth to `self`.
-        let outer_exclusive_binder = computation.outer_exclusive_binder;
-        if outer_exclusive_binder > ty::INNERMOST {
-            self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1));
-        } // otherwise, this binder captures nothing
-    }
-
-    #[allow(rustc::usage_of_ty_tykind)]
-    fn add_kind(&mut self, kind: &ty::TyKind<'_>) {
-        match kind {
-            &ty::Bool
-            | &ty::Char
-            | &ty::Int(_)
-            | &ty::Float(_)
-            | &ty::Uint(_)
-            | &ty::Never
-            | &ty::Str
-            | &ty::Foreign(..) => {}
-
-            &ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
-
-            &ty::Param(_) => {
-                self.add_flags(TypeFlags::HAS_TY_PARAM);
-            }
-
-            &ty::Closure(_, args)
-            | &ty::Coroutine(_, args)
-            | &ty::CoroutineClosure(_, args)
-            | &ty::CoroutineWitness(_, args) => {
-                self.add_args(args);
-            }
-
-            &ty::Bound(debruijn, _) => {
-                self.add_bound_var(debruijn);
-                self.add_flags(TypeFlags::HAS_TY_BOUND);
-            }
-
-            &ty::Placeholder(..) => {
-                self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER);
-            }
-
-            &ty::Infer(infer) => match infer {
-                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
-                    self.add_flags(TypeFlags::HAS_TY_FRESH)
-                }
-
-                ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => {
-                    self.add_flags(TypeFlags::HAS_TY_INFER)
-                }
-            },
-
-            &ty::Adt(_, args) => {
-                self.add_args(args);
-            }
-
-            &ty::Alias(kind, data) => {
-                self.add_flags(match kind {
-                    ty::Projection => TypeFlags::HAS_TY_PROJECTION,
-                    ty::Weak => TypeFlags::HAS_TY_WEAK,
-                    ty::Opaque => TypeFlags::HAS_TY_OPAQUE,
-                    ty::Inherent => TypeFlags::HAS_TY_INHERENT,
-                });
-
-                self.add_alias_ty(data);
-            }
-
-            &ty::Dynamic(obj, r, _) => {
-                for predicate in obj.iter() {
-                    self.bound_computation(predicate, |computation, predicate| match predicate {
-                        ty::ExistentialPredicate::Trait(tr) => computation.add_args(tr.args),
-                        ty::ExistentialPredicate::Projection(p) => {
-                            computation.add_existential_projection(&p);
-                        }
-                        ty::ExistentialPredicate::AutoTrait(_) => {}
-                    });
-                }
-
-                self.add_region(r);
-            }
-
-            &ty::Array(tt, len) => {
-                self.add_ty(tt);
-                self.add_const(len);
-            }
-
-            &ty::Pat(ty, pat) => {
-                self.add_ty(ty);
-                match *pat {
-                    ty::PatternKind::Range { start, end } => {
-                        self.add_const(start);
-                        self.add_const(end);
-                    }
-                }
-            }
-
-            &ty::Slice(tt) => self.add_ty(tt),
-
-            &ty::RawPtr(ty, _) => {
-                self.add_ty(ty);
-            }
-
-            &ty::Ref(r, ty, _) => {
-                self.add_region(r);
-                self.add_ty(ty);
-            }
-
-            &ty::Tuple(types) => {
-                self.add_tys(types);
-            }
-
-            &ty::FnDef(_, args) => {
-                self.add_args(args);
-            }
-
-            &ty::FnPtr(sig_tys, _) => self.bound_computation(sig_tys, |computation, sig_tys| {
-                computation.add_tys(sig_tys.inputs_and_output);
-            }),
-
-            &ty::UnsafeBinder(bound_ty) => {
-                self.bound_computation(bound_ty.into(), |computation, ty| {
-                    computation.add_ty(ty);
-                })
-            }
-        }
-    }
-
-    fn add_predicate(&mut self, binder: ty::Binder<'_, ty::PredicateKind<'_>>) {
-        self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom));
-    }
-
-    fn add_predicate_atom(&mut self, atom: ty::PredicateKind<'_>) {
-        match atom {
-            ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => {
-                self.add_args(trait_pred.trait_ref.args);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(ty::HostEffectPredicate {
-                trait_ref,
-                constness: _,
-            })) => {
-                self.add_args(trait_ref.args);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(
-                a,
-                b,
-            ))) => {
-                self.add_region(a);
-                self.add_region(b);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
-                ty,
-                region,
-            ))) => {
-                self.add_ty(ty);
-                self.add_region(region);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
-                self.add_const(ct);
-                self.add_ty(ty);
-            }
-            ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => {
-                self.add_ty(a);
-                self.add_ty(b);
-            }
-            ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => {
-                self.add_ty(a);
-                self.add_ty(b);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate {
-                projection_term,
-                term,
-            })) => {
-                self.add_alias_term(projection_term);
-                self.add_term(term);
-            }
-            ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => {
-                self.add_args(slice::from_ref(&arg));
-            }
-            ty::PredicateKind::DynCompatible(_def_id) => {}
-            ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
-                self.add_const(uv);
-            }
-            ty::PredicateKind::ConstEquate(expected, found) => {
-                self.add_const(expected);
-                self.add_const(found);
-            }
-            ty::PredicateKind::Ambiguous => {}
-            ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term }) => {
-                self.add_alias_term(alias);
-                self.add_term(term);
-            }
-            ty::PredicateKind::AliasRelate(t1, t2, _) => {
-                self.add_term(t1);
-                self.add_term(t2);
-            }
-        }
-    }
-
-    fn add_ty(&mut self, ty: Ty<'_>) {
-        self.add_flags(ty.flags());
-        self.add_exclusive_binder(ty.outer_exclusive_binder());
-    }
-
-    fn add_tys(&mut self, tys: &[Ty<'_>]) {
-        for &ty in tys {
-            self.add_ty(ty);
-        }
-    }
-
-    fn add_region(&mut self, r: ty::Region<'_>) {
-        self.add_flags(r.type_flags());
-        if let ty::ReBound(debruijn, _) = r.kind() {
-            self.add_bound_var(debruijn);
-        }
-    }
-
-    fn add_const(&mut self, c: ty::Const<'_>) {
-        self.add_flags(c.flags());
-        self.add_exclusive_binder(c.outer_exclusive_binder());
-    }
-
-    fn add_const_kind(&mut self, c: &ty::ConstKind<'_>) {
-        match *c {
-            ty::ConstKind::Unevaluated(uv) => {
-                self.add_args(uv.args);
-                self.add_flags(TypeFlags::HAS_CT_PROJECTION);
-            }
-            ty::ConstKind::Infer(infer) => match infer {
-                InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH),
-                InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER),
-            },
-            ty::ConstKind::Bound(debruijn, _) => {
-                self.add_bound_var(debruijn);
-                self.add_flags(TypeFlags::HAS_CT_BOUND);
-            }
-            ty::ConstKind::Param(_) => {
-                self.add_flags(TypeFlags::HAS_CT_PARAM);
-            }
-            ty::ConstKind::Placeholder(_) => {
-                self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER);
-            }
-            ty::ConstKind::Value(cv) => self.add_ty(cv.ty),
-            ty::ConstKind::Expr(e) => self.add_args(e.args()),
-            ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
-        }
-    }
-
-    fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<'_>) {
-        self.add_args(projection.args);
-        match projection.term.unpack() {
-            ty::TermKind::Ty(ty) => self.add_ty(ty),
-            ty::TermKind::Const(ct) => self.add_const(ct),
-        }
-    }
-
-    fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<'_>) {
-        self.add_args(alias_ty.args);
-    }
-
-    fn add_alias_term(&mut self, alias_term: ty::AliasTerm<'_>) {
-        self.add_args(alias_term.args);
-    }
-
-    fn add_args(&mut self, args: &[GenericArg<'_>]) {
-        for kind in args {
-            match kind.unpack() {
-                GenericArgKind::Type(ty) => self.add_ty(ty),
-                GenericArgKind::Lifetime(lt) => self.add_region(lt),
-                GenericArgKind::Const(ct) => self.add_const(ct),
-            }
-        }
-    }
-
-    fn add_term(&mut self, term: ty::Term<'_>) {
-        match term.unpack() {
-            ty::TermKind::Ty(ty) => self.add_ty(ty),
-            ty::TermKind::Const(ct) => self.add_const(ct),
-        }
-    }
-}
diff --git a/compiler/rustc_middle/src/ty/generic_args.rs b/compiler/rustc_middle/src/ty/generic_args.rs
index 9c1ff134f0f..1f04937232d 100644
--- a/compiler/rustc_middle/src/ty/generic_args.rs
+++ b/compiler/rustc_middle/src/ty/generic_args.rs
@@ -11,6 +11,7 @@ use rustc_hir::def_id::DefId;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, extension};
 use rustc_serialize::{Decodable, Encodable};
 use rustc_type_ir::WithCachedTypeInfo;
+use rustc_type_ir::walk::TypeWalker;
 use smallvec::SmallVec;
 
 use crate::ty::codec::{TyDecoder, TyEncoder};
@@ -297,6 +298,20 @@ impl<'tcx> GenericArg<'tcx> {
             GenericArgKind::Const(ct) => ct.is_ct_infer(),
         }
     }
+
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```text
+    /// isize => { isize }
+    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
+    /// [isize] => { [isize], isize }
+    /// ```
+    pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> {
+        TypeWalker::new(self)
+    }
 }
 
 impl<'a, 'tcx> Lift<TyCtxt<'tcx>> for GenericArg<'a> {
diff --git a/compiler/rustc_middle/src/ty/list.rs b/compiler/rustc_middle/src/ty/list.rs
index 0fd370a5619..0cf5820959e 100644
--- a/compiler/rustc_middle/src/ty/list.rs
+++ b/compiler/rustc_middle/src/ty/list.rs
@@ -7,9 +7,9 @@ use std::{fmt, iter, mem, ptr, slice};
 use rustc_data_structures::aligned::{Aligned, align_of};
 use rustc_data_structures::sync::DynSync;
 use rustc_serialize::{Encodable, Encoder};
+use rustc_type_ir::FlagComputation;
 
-use super::flags::FlagComputation;
-use super::{DebruijnIndex, TypeFlags};
+use super::{DebruijnIndex, TyCtxt, TypeFlags};
 use crate::arena::Arena;
 
 /// `List<T>` is a bit like `&[T]`, but with some critical differences.
@@ -299,8 +299,8 @@ impl TypeInfo {
     }
 }
 
-impl From<FlagComputation> for TypeInfo {
-    fn from(computation: FlagComputation) -> TypeInfo {
+impl<'tcx> From<FlagComputation<TyCtxt<'tcx>>> for TypeInfo {
+    fn from(computation: FlagComputation<TyCtxt<'tcx>>) -> TypeInfo {
         TypeInfo {
             flags: computation.flags,
             outer_exclusive_binder: computation.outer_exclusive_binder,
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index a2b3acac3f2..61e869f5de4 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -117,7 +117,6 @@ pub mod cast;
 pub mod codec;
 pub mod error;
 pub mod fast_reject;
-pub mod flags;
 pub mod inhabitedness;
 pub mod layout;
 pub mod normalize_erasing_regions;
@@ -128,7 +127,6 @@ pub mod significant_drop_order;
 pub mod trait_def;
 pub mod util;
 pub mod vtable;
-pub mod walk;
 
 mod adt;
 mod assoc;
diff --git a/compiler/rustc_middle/src/ty/pattern.rs b/compiler/rustc_middle/src/ty/pattern.rs
index 4cad1ab2099..758adc42e3e 100644
--- a/compiler/rustc_middle/src/ty/pattern.rs
+++ b/compiler/rustc_middle/src/ty/pattern.rs
@@ -1,14 +1,40 @@
 use std::fmt;
 
 use rustc_data_structures::intern::Interned;
-use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
+use rustc_macros::HashStable;
+use rustc_type_ir::ir_print::IrPrint;
+use rustc_type_ir::{
+    FlagComputation, Flags, {self as ir},
+};
 
+use super::TyCtxt;
 use crate::ty;
 
+pub type PatternKind<'tcx> = ir::PatternKind<TyCtxt<'tcx>>;
+
 #[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable)]
 #[rustc_pass_by_value]
 pub struct Pattern<'tcx>(pub Interned<'tcx, PatternKind<'tcx>>);
 
+impl<'tcx> Flags for Pattern<'tcx> {
+    fn flags(&self) -> rustc_type_ir::TypeFlags {
+        match &**self {
+            ty::PatternKind::Range { start, end } => {
+                FlagComputation::for_const_kind(&start.kind()).flags
+                    | FlagComputation::for_const_kind(&end.kind()).flags
+            }
+        }
+    }
+
+    fn outer_exclusive_binder(&self) -> rustc_type_ir::DebruijnIndex {
+        match &**self {
+            ty::PatternKind::Range { start, end } => {
+                start.outer_exclusive_binder().max(end.outer_exclusive_binder())
+            }
+        }
+    }
+}
+
 impl<'tcx> std::ops::Deref for Pattern<'tcx> {
     type Target = PatternKind<'tcx>;
 
@@ -23,9 +49,9 @@ impl<'tcx> fmt::Debug for Pattern<'tcx> {
     }
 }
 
-impl<'tcx> fmt::Debug for PatternKind<'tcx> {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match *self {
+impl<'tcx> IrPrint<PatternKind<'tcx>> for TyCtxt<'tcx> {
+    fn print(t: &PatternKind<'tcx>, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match *t {
             PatternKind::Range { start, end } => {
                 write!(f, "{start}")?;
 
@@ -53,10 +79,15 @@ impl<'tcx> fmt::Debug for PatternKind<'tcx> {
             }
         }
     }
+
+    fn print_debug(t: &PatternKind<'tcx>, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        Self::print(t, fmt)
+    }
 }
 
-#[derive(Clone, PartialEq, Eq, Hash)]
-#[derive(HashStable, TyEncodable, TyDecodable, TypeVisitable, TypeFoldable)]
-pub enum PatternKind<'tcx> {
-    Range { start: ty::Const<'tcx>, end: ty::Const<'tcx> },
+impl<'tcx> rustc_type_ir::inherent::IntoKind for Pattern<'tcx> {
+    type Kind = PatternKind<'tcx>;
+    fn kind(self) -> Self::Kind {
+        *self
+    }
 }
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index 27ee363f1c1..d9a65ae57a0 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -16,6 +16,7 @@ use rustc_hir::def_id::DefId;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, extension};
 use rustc_span::{DUMMY_SP, Span, Symbol, sym};
 use rustc_type_ir::TyKind::*;
+use rustc_type_ir::walk::TypeWalker;
 use rustc_type_ir::{self as ir, BoundVar, CollectAndApply, DynKind, TypeVisitableExt, elaborate};
 use tracing::instrument;
 use ty::util::{AsyncDropGlueMorphology, IntTypeExt};
@@ -2029,6 +2030,20 @@ impl<'tcx> Ty<'tcx> {
     pub fn is_known_rigid(self) -> bool {
         self.kind().is_known_rigid()
     }
+
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```text
+    /// isize => { isize }
+    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
+    /// [isize] => { [isize], isize }
+    /// ```
+    pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> {
+        TypeWalker::new(self.into())
+    }
 }
 
 impl<'tcx> rustc_type_ir::inherent::Tys<TyCtxt<'tcx>> for &'tcx ty::List<Ty<'tcx>> {
diff --git a/compiler/rustc_type_ir/src/flags.rs b/compiler/rustc_type_ir/src/flags.rs
index 6a2498242fe..e9d3a149a73 100644
--- a/compiler/rustc_type_ir/src/flags.rs
+++ b/compiler/rustc_type_ir/src/flags.rs
@@ -1,3 +1,9 @@
+use std::slice;
+
+use crate::inherent::*;
+use crate::visit::Flags;
+use crate::{self as ty, Interner};
+
 bitflags::bitflags! {
     /// Flags that we track on types. These flags are propagated upwards
     /// through the type during type construction, so that we can quickly check
@@ -128,3 +134,362 @@ bitflags::bitflags! {
         const HAS_BINDER_VARS             = 1 << 23;
     }
 }
+
+#[derive(Debug)]
+pub struct FlagComputation<I> {
+    pub flags: TypeFlags,
+
+    /// see `Ty::outer_exclusive_binder` for details
+    pub outer_exclusive_binder: ty::DebruijnIndex,
+
+    interner: std::marker::PhantomData<I>,
+}
+
+impl<I: Interner> FlagComputation<I> {
+    fn new() -> FlagComputation<I> {
+        FlagComputation {
+            flags: TypeFlags::empty(),
+            outer_exclusive_binder: ty::INNERMOST,
+            interner: std::marker::PhantomData,
+        }
+    }
+
+    #[allow(rustc::usage_of_ty_tykind)]
+    pub fn for_kind(kind: &ty::TyKind<I>) -> FlagComputation<I> {
+        let mut result = FlagComputation::new();
+        result.add_kind(kind);
+        result
+    }
+
+    pub fn for_predicate(binder: ty::Binder<I, ty::PredicateKind<I>>) -> FlagComputation<I> {
+        let mut result = FlagComputation::new();
+        result.add_predicate(binder);
+        result
+    }
+
+    pub fn for_const_kind(kind: &ty::ConstKind<I>) -> FlagComputation<I> {
+        let mut result = FlagComputation::new();
+        result.add_const_kind(kind);
+        result
+    }
+
+    pub fn for_clauses(clauses: &[I::Clause]) -> FlagComputation<I> {
+        let mut result = FlagComputation::new();
+        for c in clauses {
+            result.add_flags(c.as_predicate().flags());
+            result.add_exclusive_binder(c.as_predicate().outer_exclusive_binder());
+        }
+        result
+    }
+
+    fn add_flags(&mut self, flags: TypeFlags) {
+        self.flags = self.flags | flags;
+    }
+
+    /// indicates that `self` refers to something at binding level `binder`
+    fn add_bound_var(&mut self, binder: ty::DebruijnIndex) {
+        let exclusive_binder = binder.shifted_in(1);
+        self.add_exclusive_binder(exclusive_binder);
+    }
+
+    /// indicates that `self` refers to something *inside* binding
+    /// level `binder` -- not bound by `binder`, but bound by the next
+    /// binder internal to it
+    fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) {
+        self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder);
+    }
+
+    /// Adds the flags/depth from a set of types that appear within the current type, but within a
+    /// region binder.
+    fn bound_computation<T, F>(&mut self, value: ty::Binder<I, T>, f: F)
+    where
+        F: FnOnce(&mut Self, T),
+    {
+        let mut computation = FlagComputation::new();
+
+        if !value.bound_vars().is_empty() {
+            computation.add_flags(TypeFlags::HAS_BINDER_VARS);
+        }
+
+        f(&mut computation, value.skip_binder());
+
+        self.add_flags(computation.flags);
+
+        // The types that contributed to `computation` occurred within
+        // a region binder, so subtract one from the region depth
+        // within when adding the depth to `self`.
+        let outer_exclusive_binder = computation.outer_exclusive_binder;
+        if outer_exclusive_binder > ty::INNERMOST {
+            self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1));
+        } // otherwise, this binder captures nothing
+    }
+
+    #[allow(rustc::usage_of_ty_tykind)]
+    fn add_kind(&mut self, kind: &ty::TyKind<I>) {
+        match *kind {
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Float(_)
+            | ty::Uint(_)
+            | ty::Never
+            | ty::Str
+            | ty::Foreign(..) => {}
+
+            ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
+
+            ty::Param(_) => {
+                self.add_flags(TypeFlags::HAS_TY_PARAM);
+            }
+
+            ty::Closure(_, args)
+            | ty::Coroutine(_, args)
+            | ty::CoroutineClosure(_, args)
+            | ty::CoroutineWitness(_, args) => {
+                self.add_args(args.as_slice());
+            }
+
+            ty::Bound(debruijn, _) => {
+                self.add_bound_var(debruijn);
+                self.add_flags(TypeFlags::HAS_TY_BOUND);
+            }
+
+            ty::Placeholder(..) => {
+                self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER);
+            }
+
+            ty::Infer(infer) => match infer {
+                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
+                    self.add_flags(TypeFlags::HAS_TY_FRESH)
+                }
+
+                ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => {
+                    self.add_flags(TypeFlags::HAS_TY_INFER)
+                }
+            },
+
+            ty::Adt(_, args) => {
+                self.add_args(args.as_slice());
+            }
+
+            ty::Alias(kind, data) => {
+                self.add_flags(match kind {
+                    ty::Projection => TypeFlags::HAS_TY_PROJECTION,
+                    ty::Weak => TypeFlags::HAS_TY_WEAK,
+                    ty::Opaque => TypeFlags::HAS_TY_OPAQUE,
+                    ty::Inherent => TypeFlags::HAS_TY_INHERENT,
+                });
+
+                self.add_alias_ty(data);
+            }
+
+            ty::Dynamic(obj, r, _) => {
+                for predicate in obj.iter() {
+                    self.bound_computation(predicate, |computation, predicate| match predicate {
+                        ty::ExistentialPredicate::Trait(tr) => {
+                            computation.add_args(tr.args.as_slice())
+                        }
+                        ty::ExistentialPredicate::Projection(p) => {
+                            computation.add_existential_projection(&p);
+                        }
+                        ty::ExistentialPredicate::AutoTrait(_) => {}
+                    });
+                }
+
+                self.add_region(r);
+            }
+
+            ty::Array(tt, len) => {
+                self.add_ty(tt);
+                self.add_const(len);
+            }
+
+            ty::Pat(ty, pat) => {
+                self.add_ty(ty);
+                self.add_flags(pat.flags());
+            }
+
+            ty::Slice(tt) => self.add_ty(tt),
+
+            ty::RawPtr(ty, _) => {
+                self.add_ty(ty);
+            }
+
+            ty::Ref(r, ty, _) => {
+                self.add_region(r);
+                self.add_ty(ty);
+            }
+
+            ty::Tuple(types) => {
+                self.add_tys(types);
+            }
+
+            ty::FnDef(_, args) => {
+                self.add_args(args.as_slice());
+            }
+
+            ty::FnPtr(sig_tys, _) => self.bound_computation(sig_tys, |computation, sig_tys| {
+                computation.add_tys(sig_tys.inputs_and_output);
+            }),
+
+            ty::UnsafeBinder(bound_ty) => {
+                self.bound_computation(bound_ty.into(), |computation, ty| {
+                    computation.add_ty(ty);
+                })
+            }
+        }
+    }
+
+    fn add_predicate(&mut self, binder: ty::Binder<I, ty::PredicateKind<I>>) {
+        self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom));
+    }
+
+    fn add_predicate_atom(&mut self, atom: ty::PredicateKind<I>) {
+        match atom {
+            ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => {
+                self.add_args(trait_pred.trait_ref.args.as_slice());
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(ty::HostEffectPredicate {
+                trait_ref,
+                constness: _,
+            })) => {
+                self.add_args(trait_ref.args.as_slice());
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(
+                a,
+                b,
+            ))) => {
+                self.add_region(a);
+                self.add_region(b);
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
+                ty,
+                region,
+            ))) => {
+                self.add_ty(ty);
+                self.add_region(region);
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
+                self.add_const(ct);
+                self.add_ty(ty);
+            }
+            ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => {
+                self.add_ty(a);
+                self.add_ty(b);
+            }
+            ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => {
+                self.add_ty(a);
+                self.add_ty(b);
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate {
+                projection_term,
+                term,
+            })) => {
+                self.add_alias_term(projection_term);
+                self.add_term(term);
+            }
+            ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => {
+                self.add_args(slice::from_ref(&arg));
+            }
+            ty::PredicateKind::DynCompatible(_def_id) => {}
+            ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
+                self.add_const(uv);
+            }
+            ty::PredicateKind::ConstEquate(expected, found) => {
+                self.add_const(expected);
+                self.add_const(found);
+            }
+            ty::PredicateKind::Ambiguous => {}
+            ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term }) => {
+                self.add_alias_term(alias);
+                self.add_term(term);
+            }
+            ty::PredicateKind::AliasRelate(t1, t2, _) => {
+                self.add_term(t1);
+                self.add_term(t2);
+            }
+        }
+    }
+
+    fn add_ty(&mut self, ty: I::Ty) {
+        self.add_flags(ty.flags());
+        self.add_exclusive_binder(ty.outer_exclusive_binder());
+    }
+
+    fn add_tys(&mut self, tys: I::Tys) {
+        for ty in tys.iter() {
+            self.add_ty(ty);
+        }
+    }
+
+    fn add_region(&mut self, r: I::Region) {
+        self.add_flags(r.flags());
+        if let ty::ReBound(debruijn, _) = r.kind() {
+            self.add_bound_var(debruijn);
+        }
+    }
+
+    fn add_const(&mut self, c: I::Const) {
+        self.add_flags(c.flags());
+        self.add_exclusive_binder(c.outer_exclusive_binder());
+    }
+
+    fn add_const_kind(&mut self, c: &ty::ConstKind<I>) {
+        match *c {
+            ty::ConstKind::Unevaluated(uv) => {
+                self.add_args(uv.args.as_slice());
+                self.add_flags(TypeFlags::HAS_CT_PROJECTION);
+            }
+            ty::ConstKind::Infer(infer) => match infer {
+                ty::InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH),
+                ty::InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER),
+            },
+            ty::ConstKind::Bound(debruijn, _) => {
+                self.add_bound_var(debruijn);
+                self.add_flags(TypeFlags::HAS_CT_BOUND);
+            }
+            ty::ConstKind::Param(_) => {
+                self.add_flags(TypeFlags::HAS_CT_PARAM);
+            }
+            ty::ConstKind::Placeholder(_) => {
+                self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER);
+            }
+            ty::ConstKind::Value(cv) => self.add_ty(cv.ty()),
+            ty::ConstKind::Expr(e) => self.add_args(e.args().as_slice()),
+            ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
+        }
+    }
+
+    fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<I>) {
+        self.add_args(projection.args.as_slice());
+        match projection.term.kind() {
+            ty::TermKind::Ty(ty) => self.add_ty(ty),
+            ty::TermKind::Const(ct) => self.add_const(ct),
+        }
+    }
+
+    fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<I>) {
+        self.add_args(alias_ty.args.as_slice());
+    }
+
+    fn add_alias_term(&mut self, alias_term: ty::AliasTerm<I>) {
+        self.add_args(alias_term.args.as_slice());
+    }
+
+    fn add_args(&mut self, args: &[I::GenericArg]) {
+        for kind in args {
+            match kind.kind() {
+                ty::GenericArgKind::Type(ty) => self.add_ty(ty),
+                ty::GenericArgKind::Lifetime(lt) => self.add_region(lt),
+                ty::GenericArgKind::Const(ct) => self.add_const(ct),
+            }
+        }
+    }
+
+    fn add_term(&mut self, term: I::Term) {
+        match term.kind() {
+            ty::TermKind::Ty(ty) => self.add_ty(ty),
+            ty::TermKind::Const(ct) => self.add_const(ct),
+        }
+    }
+}
diff --git a/compiler/rustc_type_ir/src/inherent.rs b/compiler/rustc_type_ir/src/inherent.rs
index 6e6c40580d8..417803e75ea 100644
--- a/compiler/rustc_type_ir/src/inherent.rs
+++ b/compiler/rustc_type_ir/src/inherent.rs
@@ -583,7 +583,7 @@ pub trait Span<I: Interner>: Copy + Debug + Hash + Eq + TypeFoldable<I> {
 
 pub trait SliceLike: Sized + Copy {
     type Item: Copy;
-    type IntoIter: Iterator<Item = Self::Item>;
+    type IntoIter: Iterator<Item = Self::Item> + DoubleEndedIterator;
 
     fn iter(self) -> Self::IntoIter;
 
diff --git a/compiler/rustc_type_ir/src/interner.rs b/compiler/rustc_type_ir/src/interner.rs
index a9e6764e218..71bfeabfda8 100644
--- a/compiler/rustc_type_ir/src/interner.rs
+++ b/compiler/rustc_type_ir/src/interner.rs
@@ -31,6 +31,7 @@ pub trait Interner:
     + IrPrint<ty::SubtypePredicate<Self>>
     + IrPrint<ty::CoercePredicate<Self>>
     + IrPrint<ty::FnSig<Self>>
+    + IrPrint<ty::PatternKind<Self>>
 {
     type DefId: DefId<Self>;
     type LocalDefId: Copy + Debug + Hash + Eq + Into<Self::DefId> + TypeFoldable<Self>;
@@ -104,7 +105,14 @@ pub trait Interner:
     type ErrorGuaranteed: Copy + Debug + Hash + Eq;
     type BoundExistentialPredicates: BoundExistentialPredicates<Self>;
     type AllocId: Copy + Debug + Hash + Eq;
-    type Pat: Copy + Debug + Hash + Eq + Debug + Relate<Self>;
+    type Pat: Copy
+        + Debug
+        + Hash
+        + Eq
+        + Debug
+        + Relate<Self>
+        + Flags
+        + IntoKind<Kind = ty::PatternKind<Self>>;
     type Safety: Safety<Self>;
     type Abi: Abi<Self>;
 
diff --git a/compiler/rustc_type_ir/src/ir_print.rs b/compiler/rustc_type_ir/src/ir_print.rs
index 0c71f3a3df2..c259a9747f0 100644
--- a/compiler/rustc_type_ir/src/ir_print.rs
+++ b/compiler/rustc_type_ir/src/ir_print.rs
@@ -2,8 +2,8 @@ use std::fmt;
 
 use crate::{
     AliasTerm, AliasTy, Binder, CoercePredicate, ExistentialProjection, ExistentialTraitRef, FnSig,
-    HostEffectPredicate, Interner, NormalizesTo, OutlivesPredicate, ProjectionPredicate,
-    SubtypePredicate, TraitPredicate, TraitRef,
+    HostEffectPredicate, Interner, NormalizesTo, OutlivesPredicate, PatternKind,
+    ProjectionPredicate, SubtypePredicate, TraitPredicate, TraitRef,
 };
 
 pub trait IrPrint<T> {
@@ -57,9 +57,10 @@ define_display_via_print!(
     AliasTy,
     AliasTerm,
     FnSig,
+    PatternKind,
 );
 
-define_debug_via_print!(TraitRef, ExistentialTraitRef, ExistentialProjection);
+define_debug_via_print!(TraitRef, ExistentialTraitRef, ExistentialProjection, PatternKind);
 
 impl<I: Interner, T> fmt::Display for OutlivesPredicate<I, T>
 where
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index bdc61e956f8..792090effcf 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -31,6 +31,7 @@ pub mod outlives;
 pub mod relate;
 pub mod search_graph;
 pub mod solve;
+pub mod walk;
 
 // These modules are not `pub` since they are glob-imported.
 #[macro_use]
@@ -44,6 +45,7 @@ mod generic_arg;
 mod infer_ctxt;
 mod interner;
 mod opaque_ty;
+mod pattern;
 mod predicate;
 mod predicate_kind;
 mod region_kind;
@@ -67,6 +69,7 @@ pub use generic_arg::*;
 pub use infer_ctxt::*;
 pub use interner::*;
 pub use opaque_ty::*;
+pub use pattern::*;
 pub use predicate::*;
 pub use predicate_kind::*;
 pub use region_kind::*;
diff --git a/compiler/rustc_type_ir/src/pattern.rs b/compiler/rustc_type_ir/src/pattern.rs
new file mode 100644
index 00000000000..d74a82da1f9
--- /dev/null
+++ b/compiler/rustc_type_ir/src/pattern.rs
@@ -0,0 +1,16 @@
+use derive_where::derive_where;
+#[cfg(feature = "nightly")]
+use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
+use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
+
+use crate::Interner;
+
+#[derive_where(Clone, Copy, Hash, PartialEq, Eq; I: Interner)]
+#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
+#[cfg_attr(
+    feature = "nightly",
+    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
+)]
+pub enum PatternKind<I: Interner> {
+    Range { start: I::Const, end: I::Const },
+}
diff --git a/compiler/rustc_middle/src/ty/walk.rs b/compiler/rustc_type_ir/src/walk.rs
index a23316ae6fc..5683e1f1712 100644
--- a/compiler/rustc_middle/src/ty/walk.rs
+++ b/compiler/rustc_type_ir/src/walk.rs
@@ -1,20 +1,21 @@
 //! An iterator over the type substructure.
 //! WARNING: this does not keep track of the region depth.
 
-use rustc_data_structures::sso::SsoHashSet;
 use smallvec::{SmallVec, smallvec};
 use tracing::debug;
 
-use crate::ty::{self, GenericArg, GenericArgKind, Ty};
+use crate::data_structures::SsoHashSet;
+use crate::inherent::*;
+use crate::{self as ty, Interner};
 
 // The TypeWalker's stack is hot enough that it's worth going to some effort to
 // avoid heap allocations.
-type TypeWalkerStack<'tcx> = SmallVec<[GenericArg<'tcx>; 8]>;
+type TypeWalkerStack<I> = SmallVec<[<I as Interner>::GenericArg; 8]>;
 
-pub struct TypeWalker<'tcx> {
-    stack: TypeWalkerStack<'tcx>,
+pub struct TypeWalker<I: Interner> {
+    stack: TypeWalkerStack<I>,
     last_subtree: usize,
-    pub visited: SsoHashSet<GenericArg<'tcx>>,
+    pub visited: SsoHashSet<I::GenericArg>,
 }
 
 /// An iterator for walking the type tree.
@@ -25,8 +26,8 @@ pub struct TypeWalker<'tcx> {
 /// in this situation walker only visits each type once.
 /// It maintains a set of visited types and
 /// skips any types that are already there.
-impl<'tcx> TypeWalker<'tcx> {
-    pub fn new(root: GenericArg<'tcx>) -> Self {
+impl<I: Interner> TypeWalker<I> {
+    pub fn new(root: I::GenericArg) -> Self {
         Self { stack: smallvec![root], last_subtree: 1, visited: SsoHashSet::new() }
     }
 
@@ -47,16 +48,16 @@ impl<'tcx> TypeWalker<'tcx> {
     }
 }
 
-impl<'tcx> Iterator for TypeWalker<'tcx> {
-    type Item = GenericArg<'tcx>;
+impl<I: Interner> Iterator for TypeWalker<I> {
+    type Item = I::GenericArg;
 
-    fn next(&mut self) -> Option<GenericArg<'tcx>> {
+    fn next(&mut self) -> Option<I::GenericArg> {
         debug!("next(): stack={:?}", self.stack);
         loop {
             let next = self.stack.pop()?;
             self.last_subtree = self.stack.len();
             if self.visited.insert(next) {
-                push_inner(&mut self.stack, next);
+                push_inner::<I>(&mut self.stack, next);
                 debug!("next: stack={:?}", self.stack);
                 return Some(next);
             }
@@ -64,63 +65,15 @@ impl<'tcx> Iterator for TypeWalker<'tcx> {
     }
 }
 
-impl<'tcx> GenericArg<'tcx> {
-    /// Iterator that walks `self` and any types reachable from
-    /// `self`, in depth-first order. Note that just walks the types
-    /// that appear in `self`, it does not descend into the fields of
-    /// structs or variants. For example:
-    ///
-    /// ```text
-    /// isize => { isize }
-    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
-    /// [isize] => { [isize], isize }
-    /// ```
-    pub fn walk(self) -> TypeWalker<'tcx> {
-        TypeWalker::new(self)
-    }
-}
-
-impl<'tcx> Ty<'tcx> {
-    /// Iterator that walks `self` and any types reachable from
-    /// `self`, in depth-first order. Note that just walks the types
-    /// that appear in `self`, it does not descend into the fields of
-    /// structs or variants. For example:
-    ///
-    /// ```text
-    /// isize => { isize }
-    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
-    /// [isize] => { [isize], isize }
-    /// ```
-    pub fn walk(self) -> TypeWalker<'tcx> {
-        TypeWalker::new(self.into())
-    }
-}
-
-impl<'tcx> ty::Const<'tcx> {
-    /// Iterator that walks `self` and any types reachable from
-    /// `self`, in depth-first order. Note that just walks the types
-    /// that appear in `self`, it does not descend into the fields of
-    /// structs or variants. For example:
-    ///
-    /// ```text
-    /// isize => { isize }
-    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
-    /// [isize] => { [isize], isize }
-    /// ```
-    pub fn walk(self) -> TypeWalker<'tcx> {
-        TypeWalker::new(self.into())
-    }
-}
-
 /// We push `GenericArg`s on the stack in reverse order so as to
 /// maintain a pre-order traversal. As of the time of this
 /// writing, the fact that the traversal is pre-order is not
 /// known to be significant to any code, but it seems like the
 /// natural order one would expect (basically, the order of the
 /// types as they are written).
-fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) {
-    match parent.unpack() {
-        GenericArgKind::Type(parent_ty) => match *parent_ty.kind() {
+fn push_inner<I: Interner>(stack: &mut TypeWalkerStack<I>, parent: I::GenericArg) {
+    match parent.kind() {
+        ty::GenericArgKind::Type(parent_ty) => match parent_ty.kind() {
             ty::Bool
             | ty::Char
             | ty::Int(_)
@@ -136,7 +89,7 @@ fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>)
             | ty::Foreign(..) => {}
 
             ty::Pat(ty, pat) => {
-                match *pat {
+                match pat.kind() {
                     ty::PatternKind::Range { start, end } => {
                         stack.push(end.into());
                         stack.push(start.into());
@@ -163,22 +116,25 @@ fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>)
             }
             ty::Dynamic(obj, lt, _) => {
                 stack.push(lt.into());
-                stack.extend(obj.iter().rev().flat_map(|predicate| {
-                    let (args, opt_ty) = match predicate.skip_binder() {
-                        ty::ExistentialPredicate::Trait(tr) => (tr.args, None),
-                        ty::ExistentialPredicate::Projection(p) => (p.args, Some(p.term)),
-                        ty::ExistentialPredicate::AutoTrait(_) =>
-                        // Empty iterator
-                        {
-                            (ty::GenericArgs::empty(), None)
-                        }
-                    };
-
-                    args.iter().rev().chain(opt_ty.map(|term| match term.unpack() {
-                        ty::TermKind::Ty(ty) => ty.into(),
-                        ty::TermKind::Const(ct) => ct.into(),
-                    }))
-                }));
+                stack.extend(
+                    obj.iter()
+                        .rev()
+                        .filter_map(|predicate| {
+                            let (args, opt_ty) = match predicate.skip_binder() {
+                                ty::ExistentialPredicate::Trait(tr) => (tr.args, None),
+                                ty::ExistentialPredicate::Projection(p) => (p.args, Some(p.term)),
+                                ty::ExistentialPredicate::AutoTrait(_) => {
+                                    return None;
+                                }
+                            };
+
+                            Some(args.iter().rev().chain(opt_ty.map(|term| match term.kind() {
+                                ty::TermKind::Ty(ty) => ty.into(),
+                                ty::TermKind::Const(ct) => ct.into(),
+                            })))
+                        })
+                        .flatten(),
+                );
             }
             ty::Adt(_, args)
             | ty::Closure(_, args)
@@ -188,7 +144,7 @@ fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>)
             | ty::FnDef(_, args) => {
                 stack.extend(args.iter().rev());
             }
-            ty::Tuple(ts) => stack.extend(ts.iter().rev().map(GenericArg::from)),
+            ty::Tuple(ts) => stack.extend(ts.iter().rev().map(|ty| ty.into())),
             ty::FnPtr(sig_tys, _hdr) => {
                 stack.extend(
                     sig_tys.skip_binder().inputs_and_output.iter().rev().map(|ty| ty.into()),
@@ -198,15 +154,15 @@ fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>)
                 stack.push(bound_ty.skip_binder().into());
             }
         },
-        GenericArgKind::Lifetime(_) => {}
-        GenericArgKind::Const(parent_ct) => match parent_ct.kind() {
+        ty::GenericArgKind::Lifetime(_) => {}
+        ty::GenericArgKind::Const(parent_ct) => match parent_ct.kind() {
             ty::ConstKind::Infer(_)
             | ty::ConstKind::Param(_)
             | ty::ConstKind::Placeholder(_)
             | ty::ConstKind::Bound(..)
             | ty::ConstKind::Error(_) => {}
 
-            ty::ConstKind::Value(cv) => stack.push(cv.ty.into()),
+            ty::ConstKind::Value(cv) => stack.push(cv.ty().into()),
 
             ty::ConstKind::Expr(expr) => stack.extend(expr.args().iter().rev()),
             ty::ConstKind::Unevaluated(ct) => {