Abstract `MatchCheckCtxt` into a trait

7 files changed, 294 insertions, 218 deletions

diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index 95ffece54f3..2082ecda44c 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -40,7 +40,7 @@
 //! - That have no non-trivial intersection with any of the constructors in the column (i.e. they're
 //!     each either disjoint with or covered by any given column constructor).
 //!
-//! We compute this in two steps: first [`crate::cx::MatchCheckCtxt::ctors_for_ty`] determines the
+//! We compute this in two steps: first [`MatchCx::ctors_for_ty`] determines the
 //! set of all possible constructors for the type. Then [`ConstructorSet::split`] looks at the
 //! column of constructors and splits the set into groups accordingly. The precise invariants of
 //! [`ConstructorSet::split`] is described in [`SplitConstructorSet`].
@@ -136,7 +136,7 @@
 //! the algorithm can't distinguish them from a nonempty constructor. The only known case where this
 //! could happen is the `[..]` pattern on `[!; N]` with `N > 0` so we must take care to not emit it.
 //!
-//! This is all handled by [`crate::cx::MatchCheckCtxt::ctors_for_ty`] and
+//! This is all handled by [`MatchCx::ctors_for_ty`] and
 //! [`ConstructorSet::split`]. The invariants of [`SplitConstructorSet`] are also of interest.
 //!
 //!
@@ -158,14 +158,13 @@ use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS};
 use rustc_data_structures::fx::FxHashSet;
 use rustc_hir::RangeEnd;
 use rustc_index::IndexVec;
-use rustc_middle::mir::Const;
-use rustc_target::abi::VariantIdx;
 
 use self::Constructor::*;
 use self::MaybeInfiniteInt::*;
 use self::SliceKind::*;
 
 use crate::usefulness::PatCtxt;
+use crate::MatchCx;
 
 /// Whether we have seen a constructor in the column or not.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
@@ -630,11 +629,11 @@ impl OpaqueId {
 /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
 /// `Fields`.
 #[derive(Clone, Debug, PartialEq)]
-pub enum Constructor<'tcx> {
+pub enum Constructor<Cx: MatchCx> {
     /// Tuples and structs.
     Struct,
     /// Enum variants.
-    Variant(VariantIdx),
+    Variant(Cx::VariantIdx),
     /// References
     Ref,
     /// Array and slice patterns.
@@ -649,7 +648,7 @@ pub enum Constructor<'tcx> {
     F32Range(IeeeFloat<SingleS>, IeeeFloat<SingleS>, RangeEnd),
     F64Range(IeeeFloat<DoubleS>, IeeeFloat<DoubleS>, RangeEnd),
     /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately.
-    Str(Const<'tcx>),
+    Str(Cx::StrLit),
     /// Constants that must not be matched structurally. They are treated as black boxes for the
     /// purposes of exhaustiveness: we must not inspect them, and they don't count towards making a
     /// match exhaustive.
@@ -672,12 +671,12 @@ pub enum Constructor<'tcx> {
     Missing,
 }
 
-impl<'tcx> Constructor<'tcx> {
+impl<Cx: MatchCx> Constructor<Cx> {
     pub(crate) fn is_non_exhaustive(&self) -> bool {
         matches!(self, NonExhaustive)
     }
 
-    pub(crate) fn as_variant(&self) -> Option<VariantIdx> {
+    pub(crate) fn as_variant(&self) -> Option<Cx::VariantIdx> {
         match self {
             Variant(i) => Some(*i),
             _ => None,
@@ -704,7 +703,7 @@ impl<'tcx> Constructor<'tcx> {
 
     /// The number of fields for this constructor. This must be kept in sync with
     /// `Fields::wildcards`.
-    pub(crate) fn arity(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> usize {
+    pub(crate) fn arity(&self, pcx: &PatCtxt<'_, '_, Cx>) -> usize {
         pcx.cx.ctor_arity(self, pcx.ty)
     }
 
@@ -713,14 +712,11 @@ impl<'tcx> Constructor<'tcx> {
     /// this checks for inclusion.
     // We inline because this has a single call site in `Matrix::specialize_constructor`.
     #[inline]
-    pub(crate) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool {
+    pub(crate) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, Cx>, other: &Self) -> bool {
         match (self, other) {
-            (Wildcard, _) => {
-                span_bug!(
-                    pcx.cx.scrut_span,
-                    "Constructor splitting should not have returned `Wildcard`"
-                )
-            }
+            (Wildcard, _) => pcx
+                .cx
+                .bug(format_args!("Constructor splitting should not have returned `Wildcard`")),
             // Wildcards cover anything
             (_, Wildcard) => true,
             // Only a wildcard pattern can match these special constructors.
@@ -761,12 +757,9 @@ impl<'tcx> Constructor<'tcx> {
             (Opaque(self_id), Opaque(other_id)) => self_id == other_id,
             (Opaque(..), _) | (_, Opaque(..)) => false,
 
-            _ => span_bug!(
-                pcx.cx.scrut_span,
-                "trying to compare incompatible constructors {:?} and {:?}",
-                self,
-                other
-            ),
+            _ => pcx.cx.bug(format_args!(
+                "trying to compare incompatible constructors {self:?} and {other:?}"
+            )),
         }
     }
 }
@@ -790,12 +783,12 @@ pub enum VariantVisibility {
 /// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the
 /// `exhaustive_patterns` feature.
 #[derive(Debug)]
-pub enum ConstructorSet {
+pub enum ConstructorSet<Cx: MatchCx> {
     /// The type is a tuple or struct. `empty` tracks whether the type is empty.
     Struct { empty: bool },
     /// This type has the following list of constructors. If `variants` is empty and
     /// `non_exhaustive` is false, don't use this; use `NoConstructors` instead.
-    Variants { variants: IndexVec<VariantIdx, VariantVisibility>, non_exhaustive: bool },
+    Variants { variants: IndexVec<Cx::VariantIdx, VariantVisibility>, non_exhaustive: bool },
     /// The type is `&T`.
     Ref,
     /// The type is a union.
@@ -838,25 +831,25 @@ pub enum ConstructorSet {
 /// of the `ConstructorSet` for the type, yet if we forgot to include them in `present` we would be
 /// ignoring any row with `Opaque`s in the algorithm. Hence the importance of point 4.
 #[derive(Debug)]
-pub(crate) struct SplitConstructorSet<'tcx> {
-    pub(crate) present: SmallVec<[Constructor<'tcx>; 1]>,
-    pub(crate) missing: Vec<Constructor<'tcx>>,
-    pub(crate) missing_empty: Vec<Constructor<'tcx>>,
+pub(crate) struct SplitConstructorSet<Cx: MatchCx> {
+    pub(crate) present: SmallVec<[Constructor<Cx>; 1]>,
+    pub(crate) missing: Vec<Constructor<Cx>>,
+    pub(crate) missing_empty: Vec<Constructor<Cx>>,
 }
 
-impl ConstructorSet {
+impl<Cx: MatchCx> ConstructorSet<Cx> {
     /// This analyzes a column of constructors to 1/ determine which constructors of the type (if
     /// any) are missing; 2/ split constructors to handle non-trivial intersections e.g. on ranges
     /// or slices. This can get subtle; see [`SplitConstructorSet`] for details of this operation
     /// and its invariants.
     #[instrument(level = "debug", skip(self, pcx, ctors), ret)]
-    pub(crate) fn split<'a, 'tcx>(
+    pub(crate) fn split<'a>(
         &self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
-    ) -> SplitConstructorSet<'tcx>
+        pcx: &PatCtxt<'_, '_, Cx>,
+        ctors: impl Iterator<Item = &'a Constructor<Cx>> + Clone,
+    ) -> SplitConstructorSet<Cx>
     where
-        'tcx: 'a,
+        Cx: 'a,
     {
         let mut present: SmallVec<[_; 1]> = SmallVec::new();
         // Empty constructors found missing.
@@ -997,7 +990,7 @@ impl ConstructorSet {
         // We have now grouped all the constructors into 3 buckets: present, missing, missing_empty.
         // In the absence of the `exhaustive_patterns` feature however, we don't count nested empty
         // types as empty. Only non-nested `!` or `enum Foo {}` are considered empty.
-        if !pcx.cx.tcx.features().exhaustive_patterns
+        if !pcx.cx.is_exhaustive_patterns_feature_on()
             && !(pcx.is_top_level && matches!(self, Self::NoConstructors))
         {
             // Treat all missing constructors as nonempty.
diff --git a/compiler/rustc_pattern_analysis/src/cx.rs b/compiler/rustc_pattern_analysis/src/cx.rs
index a4bc99c8013..de42764c9bc 100644
--- a/compiler/rustc_pattern_analysis/src/cx.rs
+++ b/compiler/rustc_pattern_analysis/src/cx.rs
@@ -9,7 +9,7 @@ use rustc_index::Idx;
 use rustc_index::IndexVec;
 use rustc_middle::middle::stability::EvalResult;
 use rustc_middle::mir::interpret::Scalar;
-use rustc_middle::mir::{self};
+use rustc_middle::mir::{self, Const};
 use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
 use rustc_middle::ty::layout::IntegerExt;
 use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef};
@@ -18,13 +18,26 @@ use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
 use smallvec::SmallVec;
 
 use crate::constructor::{
-    Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, OpaqueId, Slice, SliceKind,
-    VariantVisibility,
+    IntRange, MaybeInfiniteInt, OpaqueId, Slice, SliceKind, VariantVisibility,
 };
-use crate::pat::{DeconstructedPat, WitnessPat};
+use crate::MatchCx;
 
-use Constructor::*;
+use crate::constructor::Constructor::*;
 
+pub type Constructor<'p, 'tcx> = crate::constructor::Constructor<MatchCheckCtxt<'p, 'tcx>>;
+pub type ConstructorSet<'p, 'tcx> = crate::constructor::ConstructorSet<MatchCheckCtxt<'p, 'tcx>>;
+pub type DeconstructedPat<'p, 'tcx> = crate::pat::DeconstructedPat<'p, MatchCheckCtxt<'p, 'tcx>>;
+pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, MatchCheckCtxt<'p, 'tcx>>;
+pub(crate) type PatCtxt<'a, 'p, 'tcx> =
+    crate::usefulness::PatCtxt<'a, 'p, MatchCheckCtxt<'p, 'tcx>>;
+pub(crate) type SplitConstructorSet<'p, 'tcx> =
+    crate::constructor::SplitConstructorSet<MatchCheckCtxt<'p, 'tcx>>;
+pub type Usefulness = crate::usefulness::Usefulness<Span>;
+pub type UsefulnessReport<'p, 'tcx> =
+    crate::usefulness::UsefulnessReport<'p, MatchCheckCtxt<'p, 'tcx>>;
+pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<MatchCheckCtxt<'p, 'tcx>>;
+
+#[derive(Clone)]
 pub struct MatchCheckCtxt<'p, 'tcx> {
     pub tcx: TyCtxt<'tcx>,
     /// The module in which the match occurs. This is necessary for
@@ -49,15 +62,17 @@ pub struct MatchCheckCtxt<'p, 'tcx> {
     pub known_valid_scrutinee: bool,
 }
 
+impl<'p, 'tcx> fmt::Debug for MatchCheckCtxt<'p, 'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("MatchCheckCtxt").finish()
+    }
+}
+
 impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     pub(crate) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
         !ty.is_inhabited_from(self.tcx, self.module, self.param_env)
     }
 
-    pub(crate) fn is_opaque(ty: Ty<'tcx>) -> bool {
-        matches!(ty.kind(), ty::Alias(ty::Opaque, ..))
-    }
-
     /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
     pub fn is_foreign_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool {
         match ty.kind() {
@@ -68,6 +83,20 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
         }
     }
 
+    /// Whether the range denotes the fictitious values before `isize::MIN` or after
+    /// `usize::MAX`/`isize::MAX` (see doc of [`IntRange::split`] for why these exist).
+    pub fn is_range_beyond_boundaries(&self, range: &IntRange, ty: Ty<'tcx>) -> bool {
+        ty.is_ptr_sized_integral() && {
+            // The two invalid ranges are `NegInfinity..isize::MIN` (represented as
+            // `NegInfinity..0`), and `{u,i}size::MAX+1..PosInfinity`. `hoist_pat_range_bdy`
+            // converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `range.lo`
+            // otherwise.
+            let lo = self.hoist_pat_range_bdy(range.lo, ty);
+            matches!(lo, PatRangeBoundary::PosInfinity)
+                || matches!(range.hi, MaybeInfiniteInt::Finite(0))
+        }
+    }
+
     // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide
     // uninhabited fields in order not to reveal the uninhabitedness of the whole variant.
     // This lists the fields we keep along with their types.
@@ -97,7 +126,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     }
 
     pub(crate) fn variant_index_for_adt(
-        ctor: &Constructor<'tcx>,
+        ctor: &Constructor<'p, 'tcx>,
         adt: ty::AdtDef<'tcx>,
     ) -> VariantIdx {
         match *ctor {
@@ -113,7 +142,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     /// Returns the types of the fields for a given constructor. The result must have a length of
     /// `ctor.arity()`.
     #[instrument(level = "trace", skip(self))]
-    pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<'tcx>, ty: Ty<'tcx>) -> &[Ty<'tcx>] {
+    pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<'p, 'tcx>, ty: Ty<'tcx>) -> &[Ty<'tcx>] {
         let cx = self;
         match ctor {
             Struct | Variant(_) | UnionField => match ty.kind() {
@@ -159,9 +188,8 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
         }
     }
 
-    /// The number of fields for this constructor. This must be kept in sync with
-    /// `Fields::wildcards`.
-    pub(crate) fn ctor_arity(&self, ctor: &Constructor<'tcx>, ty: Ty<'tcx>) -> usize {
+    /// The number of fields for this constructor.
+    pub(crate) fn ctor_arity(&self, ctor: &Constructor<'p, 'tcx>, ty: Ty<'tcx>) -> usize {
         match ctor {
             Struct | Variant(_) | UnionField => match ty.kind() {
                 ty::Tuple(fs) => fs.len(),
@@ -198,7 +226,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     ///
     /// See [`crate::constructor`] for considerations of emptiness.
     #[instrument(level = "debug", skip(self), ret)]
-    pub fn ctors_for_ty(&self, ty: Ty<'tcx>) -> ConstructorSet {
+    pub fn ctors_for_ty(&self, ty: Ty<'tcx>) -> ConstructorSet<'p, 'tcx> {
         let cx = self;
         let make_uint_range = |start, end| {
             IntRange::from_range(
@@ -599,20 +627,6 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
         }
     }
 
-    /// Whether the range denotes the fictitious values before `isize::MIN` or after
-    /// `usize::MAX`/`isize::MAX` (see doc of [`IntRange::split`] for why these exist).
-    pub fn is_range_beyond_boundaries(&self, range: &IntRange, ty: Ty<'tcx>) -> bool {
-        ty.is_ptr_sized_integral() && {
-            // The two invalid ranges are `NegInfinity..isize::MIN` (represented as
-            // `NegInfinity..0`), and `{u,i}size::MAX+1..PosInfinity`. `hoist_pat_range_bdy`
-            // converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `range.lo`
-            // otherwise.
-            let lo = self.hoist_pat_range_bdy(range.lo, ty);
-            matches!(lo, PatRangeBoundary::PosInfinity)
-                || matches!(range.hi, MaybeInfiniteInt::Finite(0))
-        }
-    }
-
     /// Convert back to a `thir::Pat` for diagnostic purposes.
     pub(crate) fn hoist_pat_range(&self, range: &IntRange, ty: Ty<'tcx>) -> Pat<'tcx> {
         use MaybeInfiniteInt::*;
@@ -652,7 +666,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     }
     /// Convert back to a `thir::Pat` for diagnostic purposes. This panics for patterns that don't
     /// appear in diagnostics, like float ranges.
-    pub fn hoist_witness_pat(&self, pat: &WitnessPat<'tcx>) -> Pat<'tcx> {
+    pub fn hoist_witness_pat(&self, pat: &WitnessPat<'p, 'tcx>) -> Pat<'tcx> {
         let cx = self;
         let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild);
         let mut subpatterns = pat.iter_fields().map(|p| Box::new(cx.hoist_witness_pat(p)));
@@ -746,7 +760,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     /// Best-effort `Debug` implementation.
     pub(crate) fn debug_pat(
         f: &mut fmt::Formatter<'_>,
-        pat: &DeconstructedPat<'p, 'tcx>,
+        pat: &crate::pat::DeconstructedPat<'_, Self>,
     ) -> fmt::Result {
         let mut first = true;
         let mut start_or_continue = |s| {
@@ -840,6 +854,44 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
     }
 }
 
+impl<'p, 'tcx> MatchCx for MatchCheckCtxt<'p, 'tcx> {
+    type Ty = Ty<'tcx>;
+    type Span = Span;
+    type VariantIdx = VariantIdx;
+    type StrLit = Const<'tcx>;
+
+    fn is_exhaustive_patterns_feature_on(&self) -> bool {
+        self.tcx.features().exhaustive_patterns
+    }
+    fn is_opaque_ty(ty: Self::Ty) -> bool {
+        matches!(ty.kind(), ty::Alias(ty::Opaque, ..))
+    }
+
+    fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: Self::Ty) -> usize {
+        self.ctor_arity(ctor, ty)
+    }
+    fn ctor_sub_tys(
+        &self,
+        ctor: &crate::constructor::Constructor<Self>,
+        ty: Self::Ty,
+    ) -> &[Self::Ty] {
+        self.ctor_sub_tys(ctor, ty)
+    }
+    fn ctors_for_ty(&self, ty: Self::Ty) -> crate::constructor::ConstructorSet<Self> {
+        self.ctors_for_ty(ty)
+    }
+
+    fn debug_pat(
+        f: &mut fmt::Formatter<'_>,
+        pat: &crate::pat::DeconstructedPat<'_, Self>,
+    ) -> fmt::Result {
+        Self::debug_pat(f, pat)
+    }
+    fn bug(&self, fmt: fmt::Arguments<'_>) -> ! {
+        span_bug!(self.scrut_span, "{}", fmt)
+    }
+}
+
 /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
 fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> {
     fn expand<'p, 'tcx>(pat: &'p Pat<'tcx>, vec: &mut Vec<&'p Pat<'tcx>>) {
diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs
index 0efa8a0ec08..3483a2710d4 100644
--- a/compiler/rustc_pattern_analysis/src/errors.rs
+++ b/compiler/rustc_pattern_analysis/src/errors.rs
@@ -1,11 +1,11 @@
-use crate::{cx::MatchCheckCtxt, pat::WitnessPat};
-
 use rustc_errors::{AddToDiagnostic, Diagnostic, SubdiagnosticMessage};
 use rustc_macros::{LintDiagnostic, Subdiagnostic};
 use rustc_middle::thir::Pat;
 use rustc_middle::ty::Ty;
 use rustc_span::Span;
 
+use crate::cx::{MatchCheckCtxt, WitnessPat};
+
 #[derive(Subdiagnostic)]
 #[label(pattern_analysis_uncovered)]
 pub struct Uncovered<'tcx> {
@@ -22,7 +22,7 @@ impl<'tcx> Uncovered<'tcx> {
     pub fn new<'p>(
         span: Span,
         cx: &MatchCheckCtxt<'p, 'tcx>,
-        witnesses: Vec<WitnessPat<'tcx>>,
+        witnesses: Vec<WitnessPat<'p, 'tcx>>,
     ) -> Self {
         let witness_1 = cx.hoist_witness_pat(witnesses.get(0).unwrap());
         Self {
diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs
index f19dc7345fc..79c8eb394ad 100644
--- a/compiler/rustc_pattern_analysis/src/lib.rs
+++ b/compiler/rustc_pattern_analysis/src/lib.rs
@@ -14,36 +14,71 @@ extern crate rustc_middle;
 
 rustc_fluent_macro::fluent_messages! { "../messages.ftl" }
 
+use std::fmt;
+
+use constructor::{Constructor, ConstructorSet};
 use lints::PatternColumn;
 use rustc_hir::HirId;
+use rustc_index::Idx;
 use rustc_middle::ty::Ty;
-use usefulness::{compute_match_usefulness, UsefulnessReport};
+use usefulness::{compute_match_usefulness, UsefulnessReport, ValidityConstraint};
 
 use crate::cx::MatchCheckCtxt;
 use crate::lints::{lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints};
 use crate::pat::DeconstructedPat;
 
+pub trait MatchCx: Sized + Clone + fmt::Debug {
+    type Ty: Copy + Clone + fmt::Debug; // FIXME: remove Copy
+    type Span: Clone + Default;
+    type VariantIdx: Clone + Idx;
+    type StrLit: Clone + PartialEq + fmt::Debug;
+
+    fn is_opaque_ty(ty: Self::Ty) -> bool;
+    fn is_exhaustive_patterns_feature_on(&self) -> bool;
+
+    /// The number of fields for this constructor.
+    fn ctor_arity(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> usize;
+
+    /// The types of the fields for this constructor. The result must have a length of
+    /// `ctor_arity()`.
+    fn ctor_sub_tys(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> &[Self::Ty];
+
+    /// The set of all the constructors for `ty`.
+    ///
+    /// This must follow the invariants of `ConstructorSet`
+    fn ctors_for_ty(&self, ty: Self::Ty) -> ConstructorSet<Self>;
+
+    /// Best-effort `Debug` implementation.
+    fn debug_pat(f: &mut fmt::Formatter<'_>, pat: &DeconstructedPat<'_, Self>) -> fmt::Result;
+
+    /// Raise a bug.
+    fn bug(&self, fmt: fmt::Arguments<'_>) -> !;
+}
+
 /// The arm of a match expression.
-#[derive(Clone, Copy, Debug)]
-pub struct MatchArm<'p, 'tcx> {
+#[derive(Clone, Debug)]
+pub struct MatchArm<'p, Cx: MatchCx> {
     /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
-    pub pat: &'p DeconstructedPat<'p, 'tcx>,
+    pub pat: &'p DeconstructedPat<'p, Cx>,
     pub hir_id: HirId,
     pub has_guard: bool,
 }
 
+impl<'p, Cx: MatchCx> Copy for MatchArm<'p, Cx> {}
+
 /// The entrypoint for this crate. Computes whether a match is exhaustive and which of its arms are
 /// useful, and runs some lints.
 pub fn analyze_match<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
-    arms: &[MatchArm<'p, 'tcx>],
+    arms: &[MatchArm<'p, MatchCheckCtxt<'p, 'tcx>>],
     scrut_ty: Ty<'tcx>,
-) -> UsefulnessReport<'p, 'tcx> {
+) -> UsefulnessReport<'p, MatchCheckCtxt<'p, 'tcx>> {
     // Arena to store the extra wildcards we construct during analysis.
     let wildcard_arena = cx.pattern_arena;
     let pat_column = PatternColumn::new(arms);
 
-    let report = compute_match_usefulness(cx, arms, scrut_ty, wildcard_arena);
+    let scrut_validity = ValidityConstraint::from_bool(cx.known_valid_scrutinee);
+    let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity, wildcard_arena);
 
     // Lint on ranges that overlap on their endpoints, which is likely a mistake.
     lint_overlapping_range_endpoints(cx, &pat_column, wildcard_arena);
diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs
index 858e28ce897..88967ab9010 100644
--- a/compiler/rustc_pattern_analysis/src/lints.rs
+++ b/compiler/rustc_pattern_analysis/src/lints.rs
@@ -7,15 +7,16 @@ use rustc_session::lint;
 use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS;
 use rustc_span::Span;
 
-use crate::constructor::{Constructor, IntRange, MaybeInfiniteInt, SplitConstructorSet};
-use crate::cx::MatchCheckCtxt;
+use crate::constructor::{IntRange, MaybeInfiniteInt};
+use crate::cx::{
+    Constructor, DeconstructedPat, MatchArm, MatchCheckCtxt, PatCtxt, SplitConstructorSet,
+    WitnessPat,
+};
 use crate::errors::{
     NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap,
     OverlappingRangeEndpoints, Uncovered,
 };
-use crate::pat::{DeconstructedPat, WitnessPat};
-use crate::usefulness::PatCtxt;
-use crate::MatchArm;
+use crate::MatchCx;
 
 /// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that
 /// inspect the same subvalue/place".
@@ -55,10 +56,10 @@ impl<'a, 'p, 'tcx> PatternColumn<'a, 'p, 'tcx> {
         // If the type is opaque and it is revealed anywhere in the column, we take the revealed
         // version. Otherwise we could encounter constructors for the revealed type and crash.
         let first_ty = self.patterns[0].ty();
-        if MatchCheckCtxt::is_opaque(first_ty) {
+        if MatchCheckCtxt::is_opaque_ty(first_ty) {
             for pat in &self.patterns {
                 let ty = pat.ty();
-                if !MatchCheckCtxt::is_opaque(ty) {
+                if !MatchCheckCtxt::is_opaque_ty(ty) {
                     return Some(ty);
                 }
             }
@@ -67,7 +68,7 @@ impl<'a, 'p, 'tcx> PatternColumn<'a, 'p, 'tcx> {
     }
 
     /// Do constructor splitting on the constructors of the column.
-    fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> {
+    fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'p, 'tcx> {
         let column_ctors = self.patterns.iter().map(|p| p.ctor());
         pcx.cx.ctors_for_ty(pcx.ty).split(pcx, column_ctors)
     }
@@ -84,7 +85,7 @@ impl<'a, 'p, 'tcx> PatternColumn<'a, 'p, 'tcx> {
     fn specialize<'b>(
         &self,
         pcx: &'b PatCtxt<'_, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
+        ctor: &Constructor<'p, 'tcx>,
     ) -> Vec<PatternColumn<'b, 'p, 'tcx>>
     where
         'a: 'b,
@@ -128,7 +129,7 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     column: &PatternColumn<'a, 'p, 'tcx>,
     wildcard_arena: &TypedArena<DeconstructedPat<'p, 'tcx>>,
-) -> Vec<WitnessPat<'tcx>> {
+) -> Vec<WitnessPat<'p, 'tcx>> {
     let Some(ty) = column.head_ty() else {
         return Vec::new();
     };
@@ -215,7 +216,7 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>(
                 };
 
                 use rustc_errors::DecorateLint;
-                let mut err = cx.tcx.sess.struct_span_warn(arm.pat.span(), "");
+                let mut err = cx.tcx.sess.struct_span_warn(*arm.pat.span(), "");
                 err.set_primary_message(decorator.msg());
                 decorator.decorate_lint(&mut err);
                 err.emit();
@@ -265,7 +266,7 @@ pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>(
                 let mut suffixes: SmallVec<[_; 1]> = Default::default();
                 // Iterate on patterns that contained `overlap`.
                 for pat in column.iter() {
-                    let this_span = pat.span();
+                    let this_span = *pat.span();
                     let Constructor::IntRange(this_range) = pat.ctor() else { continue };
                     if this_range.is_singleton() {
                         // Don't lint when one of the ranges is a singleton.
diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs
index 29230c390ef..c1052c88514 100644
--- a/compiler/rustc_pattern_analysis/src/pat.rs
+++ b/compiler/rustc_pattern_analysis/src/pat.rs
@@ -6,14 +6,12 @@ use std::fmt;
 use smallvec::{smallvec, SmallVec};
 
 use rustc_data_structures::captures::Captures;
-use rustc_middle::ty::Ty;
-use rustc_span::Span;
 
 use self::Constructor::*;
 
 use crate::constructor::{Constructor, Slice, SliceKind};
-use crate::cx::MatchCheckCtxt;
 use crate::usefulness::PatCtxt;
+use crate::MatchCx;
 
 /// Values and patterns can be represented as a constructor applied to some fields. This represents
 /// a pattern in this form.
@@ -26,25 +24,25 @@ use crate::usefulness::PatCtxt;
 /// This happens if a private or `non_exhaustive` field is uninhabited, because the code mustn't
 /// observe that it is uninhabited. In that case that field is not included in `fields`. Care must
 /// be taken when converting to/from `thir::Pat`.
-pub struct DeconstructedPat<'p, 'tcx> {
-    ctor: Constructor<'tcx>,
-    fields: &'p [DeconstructedPat<'p, 'tcx>],
-    ty: Ty<'tcx>,
-    span: Span,
+pub struct DeconstructedPat<'p, Cx: MatchCx> {
+    ctor: Constructor<Cx>,
+    fields: &'p [DeconstructedPat<'p, Cx>],
+    ty: Cx::Ty,
+    span: Cx::Span,
     /// Whether removing this arm would change the behavior of the match expression.
     useful: Cell<bool>,
 }
 
-impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
-    pub fn wildcard(ty: Ty<'tcx>, span: Span) -> Self {
+impl<'p, Cx: MatchCx> DeconstructedPat<'p, Cx> {
+    pub fn wildcard(ty: Cx::Ty, span: Cx::Span) -> Self {
         Self::new(Wildcard, &[], ty, span)
     }
 
     pub fn new(
-        ctor: Constructor<'tcx>,
-        fields: &'p [DeconstructedPat<'p, 'tcx>],
-        ty: Ty<'tcx>,
-        span: Span,
+        ctor: Constructor<Cx>,
+        fields: &'p [DeconstructedPat<'p, Cx>],
+        ty: Cx::Ty,
+        span: Cx::Span,
     ) -> Self {
         DeconstructedPat { ctor, fields, ty, span, useful: Cell::new(false) }
     }
@@ -61,19 +59,19 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         }
     }
 
-    pub fn ctor(&self) -> &Constructor<'tcx> {
+    pub fn ctor(&self) -> &Constructor<Cx> {
         &self.ctor
     }
-    pub fn ty(&self) -> Ty<'tcx> {
+    pub fn ty(&self) -> Cx::Ty {
         self.ty
     }
-    pub fn span(&self) -> Span {
-        self.span
+    pub fn span(&self) -> &Cx::Span {
+        &self.span
     }
 
     pub fn iter_fields<'a>(
         &'a self,
-    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
+    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Captures<'a> {
         self.fields.iter()
     }
 
@@ -81,13 +79,13 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
     /// `other_ctor` can be different from `self.ctor`, but must be covered by it.
     pub(crate) fn specialize<'a>(
         &self,
-        pcx: &PatCtxt<'a, 'p, 'tcx>,
-        other_ctor: &Constructor<'tcx>,
-    ) -> SmallVec<[&'a DeconstructedPat<'p, 'tcx>; 2]> {
+        pcx: &PatCtxt<'a, 'p, Cx>,
+        other_ctor: &Constructor<Cx>,
+    ) -> SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]> {
         let wildcard_sub_tys = || {
             let tys = pcx.cx.ctor_sub_tys(other_ctor, pcx.ty);
             tys.iter()
-                .map(|ty| DeconstructedPat::wildcard(*ty, Span::default()))
+                .map(|ty| DeconstructedPat::wildcard(*ty, Cx::Span::default()))
                 .map(|pat| pcx.wildcard_arena.alloc(pat) as &_)
                 .collect()
         };
@@ -137,15 +135,15 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
     }
 
     /// Report the spans of subpatterns that were not useful, if any.
-    pub(crate) fn redundant_spans(&self) -> Vec<Span> {
+    pub(crate) fn redundant_spans(&self) -> Vec<Cx::Span> {
         let mut spans = Vec::new();
         self.collect_redundant_spans(&mut spans);
         spans
     }
-    fn collect_redundant_spans(&self, spans: &mut Vec<Span>) {
+    fn collect_redundant_spans(&self, spans: &mut Vec<Cx::Span>) {
         // We don't look at subpatterns if we already reported the whole pattern as redundant.
         if !self.is_useful() {
-            spans.push(self.span);
+            spans.push(self.span.clone());
         } else {
             for p in self.iter_fields() {
                 p.collect_redundant_spans(spans);
@@ -156,46 +154,46 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
 
 /// This is mostly copied from the `Pat` impl. This is best effort and not good enough for a
 /// `Display` impl.
-impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> {
+impl<'p, Cx: MatchCx> fmt::Debug for DeconstructedPat<'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        MatchCheckCtxt::debug_pat(f, self)
+        Cx::debug_pat(f, self)
     }
 }
 
 /// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics
 /// purposes. As such they don't use interning and can be cloned.
 #[derive(Debug, Clone)]
-pub struct WitnessPat<'tcx> {
-    ctor: Constructor<'tcx>,
-    pub(crate) fields: Vec<WitnessPat<'tcx>>,
-    ty: Ty<'tcx>,
+pub struct WitnessPat<Cx: MatchCx> {
+    ctor: Constructor<Cx>,
+    pub(crate) fields: Vec<WitnessPat<Cx>>,
+    ty: Cx::Ty,
 }
 
-impl<'tcx> WitnessPat<'tcx> {
-    pub(crate) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self {
+impl<Cx: MatchCx> WitnessPat<Cx> {
+    pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self {
         Self { ctor, fields, ty }
     }
-    pub(crate) fn wildcard(ty: Ty<'tcx>) -> Self {
+    pub(crate) fn wildcard(ty: Cx::Ty) -> Self {
         Self::new(Wildcard, Vec::new(), ty)
     }
 
     /// Construct a pattern that matches everything that starts with this constructor.
     /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
     /// `Some(_)`.
-    pub(crate) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, 'tcx>, ctor: Constructor<'tcx>) -> Self {
+    pub(crate) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, Cx>, ctor: Constructor<Cx>) -> Self {
         let field_tys = pcx.cx.ctor_sub_tys(&ctor, pcx.ty);
         let fields = field_tys.iter().map(|ty| Self::wildcard(*ty)).collect();
         Self::new(ctor, fields, pcx.ty)
     }
 
-    pub fn ctor(&self) -> &Constructor<'tcx> {
+    pub fn ctor(&self) -> &Constructor<Cx> {
         &self.ctor
     }
-    pub fn ty(&self) -> Ty<'tcx> {
+    pub fn ty(&self) -> Cx::Ty {
         self.ty
     }
 
-    pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> {
+    pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<Cx>> {
         self.fields.iter()
     }
 }
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index 3300013805d..d52d9358b94 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -242,7 +242,7 @@
 //! Therefore `usefulness(tp_1, tp_2, tq)` returns the single witness-tuple `[Variant2(Some(true), 0)]`.
 //!
 //!
-//! Computing the set of constructors for a type is done in [`MatchCheckCtxt::ctors_for_ty`]. See
+//! Computing the set of constructors for a type is done in [`MatchCx::ctors_for_ty`]. See
 //! the following sections for more accurate versions of the algorithm and corresponding links.
 //!
 //!
@@ -557,40 +557,39 @@ use std::fmt;
 
 use rustc_arena::TypedArena;
 use rustc_data_structures::{captures::Captures, stack::ensure_sufficient_stack};
-use rustc_middle::ty::Ty;
-use rustc_span::Span;
 
 use crate::constructor::{Constructor, ConstructorSet};
-use crate::cx::MatchCheckCtxt;
 use crate::pat::{DeconstructedPat, WitnessPat};
-use crate::MatchArm;
+use crate::{MatchArm, MatchCx};
 
 use self::ValidityConstraint::*;
 
-#[derive(Copy, Clone)]
-pub(crate) struct PatCtxt<'a, 'p, 'tcx> {
-    pub(crate) cx: &'a MatchCheckCtxt<'p, 'tcx>,
+#[derive(Clone)]
+pub(crate) struct PatCtxt<'a, 'p, Cx: MatchCx> {
+    pub(crate) cx: &'a Cx,
     /// Type of the current column under investigation.
-    pub(crate) ty: Ty<'tcx>,
+    pub(crate) ty: Cx::Ty,
     /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
     /// subpattern.
     pub(crate) is_top_level: bool,
     /// An arena to store the wildcards we produce during analysis.
-    pub(crate) wildcard_arena: &'a TypedArena<DeconstructedPat<'p, 'tcx>>,
+    pub(crate) wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
 }
 
-impl<'a, 'p, 'tcx> PatCtxt<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> PatCtxt<'a, 'p, Cx> {
     /// A `PatCtxt` when code other than `is_useful` needs one.
     pub(crate) fn new_dummy(
-        cx: &'a MatchCheckCtxt<'p, 'tcx>,
-        ty: Ty<'tcx>,
-        wildcard_arena: &'a TypedArena<DeconstructedPat<'p, 'tcx>>,
+        cx: &'a Cx,
+        ty: Cx::Ty,
+        wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
     ) -> Self {
         PatCtxt { cx, ty, is_top_level: false, wildcard_arena }
     }
 }
 
-impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> Copy for PatCtxt<'a, 'p, Cx> {}
+
+impl<'a, 'p, Cx: MatchCx> fmt::Debug for PatCtxt<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         f.debug_struct("PatCtxt").field("ty", &self.ty).finish()
     }
@@ -602,7 +601,7 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
 /// - in the matrix, track whether a given place (aka column) is known to contain a valid value or
 ///     not.
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
-enum ValidityConstraint {
+pub(crate) enum ValidityConstraint {
     ValidOnly,
     MaybeInvalid,
     /// Option for backwards compatibility: the place is not known to be valid but we allow omitting
@@ -611,7 +610,7 @@ enum ValidityConstraint {
 }
 
 impl ValidityConstraint {
-    fn from_bool(is_valid_only: bool) -> Self {
+    pub(crate) fn from_bool(is_valid_only: bool) -> Self {
         if is_valid_only { ValidOnly } else { MaybeInvalid }
     }
 
@@ -636,7 +635,7 @@ impl ValidityConstraint {
     ///
     /// Pending further opsem decisions, the current behavior is: validity is preserved, except
     /// inside `&` and union fields where validity is reset to `MaybeInvalid`.
-    fn specialize(self, ctor: &Constructor<'_>) -> Self {
+    fn specialize<Cx: MatchCx>(self, ctor: &Constructor<Cx>) -> Self {
         // We preserve validity except when we go inside a reference or a union field.
         if matches!(ctor, Constructor::Ref | Constructor::UnionField) {
             // Validity of `x: &T` does not imply validity of `*x: T`.
@@ -661,15 +660,15 @@ impl fmt::Display for ValidityConstraint {
 // The three lifetimes are:
 // - 'a allocated by us
 // - 'p coming from the input
-// - 'tcx global compilation context
+// - Cx global compilation context
 #[derive(Clone)]
-struct PatStack<'a, 'p, 'tcx> {
+struct PatStack<'a, 'p, Cx: MatchCx> {
     // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well.
-    pats: SmallVec<[&'a DeconstructedPat<'p, 'tcx>; 2]>,
+    pats: SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]>,
 }
 
-impl<'a, 'p, 'tcx> PatStack<'a, 'p, 'tcx> {
-    fn from_pattern(pat: &'a DeconstructedPat<'p, 'tcx>) -> Self {
+impl<'a, 'p, Cx: MatchCx> PatStack<'a, 'p, Cx> {
+    fn from_pattern(pat: &'a DeconstructedPat<'p, Cx>) -> Self {
         PatStack { pats: smallvec![pat] }
     }
 
@@ -681,17 +680,17 @@ impl<'a, 'p, 'tcx> PatStack<'a, 'p, 'tcx> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'a DeconstructedPat<'p, 'tcx> {
+    fn head(&self) -> &'a DeconstructedPat<'p, Cx> {
         self.pats[0]
     }
 
-    fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>> + Captures<'b> {
+    fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, Cx>> + Captures<'b> {
         self.pats.iter().copied()
     }
 
     // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is
     // an or-pattern. Panics if `self` is empty.
-    fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = PatStack<'a, 'p, 'tcx>> + Captures<'b> {
+    fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = PatStack<'a, 'p, Cx>> + Captures<'b> {
         self.head().flatten_or_pat().into_iter().map(move |pat| {
             let mut new = self.clone();
             new.pats[0] = pat;
@@ -703,9 +702,9 @@ impl<'a, 'p, 'tcx> PatStack<'a, 'p, 'tcx> {
     /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
     fn pop_head_constructor(
         &self,
-        pcx: &PatCtxt<'a, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
-    ) -> PatStack<'a, 'p, 'tcx> {
+        pcx: &PatCtxt<'a, 'p, Cx>,
+        ctor: &Constructor<Cx>,
+    ) -> PatStack<'a, 'p, Cx> {
         // We pop the head pattern and push the new fields extracted from the arguments of
         // `self.head()`.
         let mut new_pats = self.head().specialize(pcx, ctor);
@@ -714,7 +713,7 @@ impl<'a, 'p, 'tcx> PatStack<'a, 'p, 'tcx> {
     }
 }
 
-impl<'a, 'p, 'tcx> fmt::Debug for PatStack<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> fmt::Debug for PatStack<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         // We pretty-print similarly to the `Debug` impl of `Matrix`.
         write!(f, "+")?;
@@ -727,9 +726,9 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatStack<'a, 'p, 'tcx> {
 
 /// A row of the matrix.
 #[derive(Clone)]
-struct MatrixRow<'a, 'p, 'tcx> {
+struct MatrixRow<'a, 'p, Cx: MatchCx> {
     // The patterns in the row.
-    pats: PatStack<'a, 'p, 'tcx>,
+    pats: PatStack<'a, 'p, Cx>,
     /// Whether the original arm had a guard. This is inherited when specializing.
     is_under_guard: bool,
     /// When we specialize, we remember which row of the original matrix produced a given row of the
@@ -742,7 +741,7 @@ struct MatrixRow<'a, 'p, 'tcx> {
     useful: bool,
 }
 
-impl<'a, 'p, 'tcx> MatrixRow<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> MatrixRow<'a, 'p, Cx> {
     fn is_empty(&self) -> bool {
         self.pats.is_empty()
     }
@@ -751,17 +750,17 @@ impl<'a, 'p, 'tcx> MatrixRow<'a, 'p, 'tcx> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'a DeconstructedPat<'p, 'tcx> {
+    fn head(&self) -> &'a DeconstructedPat<'p, Cx> {
         self.pats.head()
     }
 
-    fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>> + Captures<'b> {
+    fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, Cx>> + Captures<'b> {
         self.pats.iter()
     }
 
     // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is
     // an or-pattern. Panics if `self` is empty.
-    fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = MatrixRow<'a, 'p, 'tcx>> + Captures<'b> {
+    fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = MatrixRow<'a, 'p, Cx>> + Captures<'b> {
         self.pats.expand_or_pat().map(|patstack| MatrixRow {
             pats: patstack,
             parent_row: self.parent_row,
@@ -774,10 +773,10 @@ impl<'a, 'p, 'tcx> MatrixRow<'a, 'p, 'tcx> {
     /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
     fn pop_head_constructor(
         &self,
-        pcx: &PatCtxt<'a, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
+        pcx: &PatCtxt<'a, 'p, Cx>,
+        ctor: &Constructor<Cx>,
         parent_row: usize,
-    ) -> MatrixRow<'a, 'p, 'tcx> {
+    ) -> MatrixRow<'a, 'p, Cx> {
         MatrixRow {
             pats: self.pats.pop_head_constructor(pcx, ctor),
             parent_row,
@@ -787,7 +786,7 @@ impl<'a, 'p, 'tcx> MatrixRow<'a, 'p, 'tcx> {
     }
 }
 
-impl<'a, 'p, 'tcx> fmt::Debug for MatrixRow<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> fmt::Debug for MatrixRow<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         self.pats.fmt(f)
     }
@@ -804,22 +803,22 @@ impl<'a, 'p, 'tcx> fmt::Debug for MatrixRow<'a, 'p, 'tcx> {
 /// specializing `(,)` and `Some` on a pattern of type `(Option<u32>, bool)`, the first column of
 /// the matrix will correspond to `scrutinee.0.Some.0` and the second column to `scrutinee.1`.
 #[derive(Clone)]
-struct Matrix<'a, 'p, 'tcx> {
+struct Matrix<'a, 'p, Cx: MatchCx> {
     /// Vector of rows. The rows must form a rectangular 2D array. Moreover, all the patterns of
     /// each column must have the same type. Each column corresponds to a place within the
     /// scrutinee.
-    rows: Vec<MatrixRow<'a, 'p, 'tcx>>,
+    rows: Vec<MatrixRow<'a, 'p, Cx>>,
     /// Stores an extra fictitious row full of wildcards. Mostly used to keep track of the type of
     /// each column. This must obey the same invariants as the real rows.
-    wildcard_row: PatStack<'a, 'p, 'tcx>,
+    wildcard_row: PatStack<'a, 'p, Cx>,
     /// Track for each column/place whether it contains a known valid value.
     place_validity: SmallVec<[ValidityConstraint; 2]>,
 }
 
-impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> Matrix<'a, 'p, Cx> {
     /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
     /// expands it. Internal method, prefer [`Matrix::new`].
-    fn expand_and_push(&mut self, row: MatrixRow<'a, 'p, 'tcx>) {
+    fn expand_and_push(&mut self, row: MatrixRow<'a, 'p, Cx>) {
         if !row.is_empty() && row.head().is_or_pat() {
             // Expand nested or-patterns.
             for new_row in row.expand_or_pat() {
@@ -832,13 +831,13 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
 
     /// Build a new matrix from an iterator of `MatchArm`s.
     fn new(
-        wildcard_arena: &'a TypedArena<DeconstructedPat<'p, 'tcx>>,
-        arms: &'a [MatchArm<'p, 'tcx>],
-        scrut_ty: Ty<'tcx>,
+        wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
+        arms: &'a [MatchArm<'p, Cx>],
+        scrut_ty: Cx::Ty,
         scrut_validity: ValidityConstraint,
     ) -> Self {
         let wild_pattern =
-            wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty, Span::default()));
+            wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty, Cx::Span::default()));
         let wildcard_row = PatStack::from_pattern(wild_pattern);
         let mut matrix = Matrix {
             rows: Vec::with_capacity(arms.len()),
@@ -857,7 +856,7 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
         matrix
     }
 
-    fn head_ty(&self) -> Option<Ty<'tcx>> {
+    fn head_ty(&self) -> Option<Cx::Ty> {
         if self.column_count() == 0 {
             return None;
         }
@@ -865,10 +864,10 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
         let mut ty = self.wildcard_row.head().ty();
         // If the type is opaque and it is revealed anywhere in the column, we take the revealed
         // version. Otherwise we could encounter constructors for the revealed type and crash.
-        if MatchCheckCtxt::is_opaque(ty) {
+        if Cx::is_opaque_ty(ty) {
             for pat in self.heads() {
                 let pat_ty = pat.ty();
-                if !MatchCheckCtxt::is_opaque(pat_ty) {
+                if !Cx::is_opaque_ty(pat_ty) {
                     ty = pat_ty;
                     break;
                 }
@@ -882,15 +881,13 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
 
     fn rows<'b>(
         &'b self,
-    ) -> impl Iterator<Item = &'b MatrixRow<'a, 'p, 'tcx>>
-    + Clone
-    + DoubleEndedIterator
-    + ExactSizeIterator {
+    ) -> impl Iterator<Item = &'b MatrixRow<'a, 'p, Cx>> + Clone + DoubleEndedIterator + ExactSizeIterator
+    {
         self.rows.iter()
     }
     fn rows_mut<'b>(
         &'b mut self,
-    ) -> impl Iterator<Item = &'b mut MatrixRow<'a, 'p, 'tcx>> + DoubleEndedIterator + ExactSizeIterator
+    ) -> impl Iterator<Item = &'b mut MatrixRow<'a, 'p, Cx>> + DoubleEndedIterator + ExactSizeIterator
     {
         self.rows.iter_mut()
     }
@@ -898,16 +895,16 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
     /// Iterate over the first pattern of each row.
     fn heads<'b>(
         &'b self,
-    ) -> impl Iterator<Item = &'b DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> {
+    ) -> impl Iterator<Item = &'b DeconstructedPat<'p, Cx>> + Clone + Captures<'a> {
         self.rows().map(|r| r.head())
     }
 
     /// This computes `specialize(ctor, self)`. See top of the file for explanations.
     fn specialize_constructor(
         &self,
-        pcx: &PatCtxt<'a, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
-    ) -> Matrix<'a, 'p, 'tcx> {
+        pcx: &PatCtxt<'a, 'p, Cx>,
+        ctor: &Constructor<Cx>,
+    ) -> Matrix<'a, 'p, Cx> {
         let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor);
         let new_validity = self.place_validity[0].specialize(ctor);
         let new_place_validity = std::iter::repeat(new_validity)
@@ -936,7 +933,7 @@ impl<'a, 'p, 'tcx> Matrix<'a, 'p, 'tcx> {
 /// + _     + [_, _, tail @ ..] +
 /// | ✓     | ?                 | // column validity
 /// ```
-impl<'a, 'p, 'tcx> fmt::Debug for Matrix<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: MatchCx> fmt::Debug for Matrix<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "\n")?;
 
@@ -1027,17 +1024,17 @@ impl<'a, 'p, 'tcx> fmt::Debug for Matrix<'a, 'p, 'tcx> {
 ///
 /// See the top of the file for more detailed explanations and examples.
 #[derive(Debug, Clone)]
-struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>);
+struct WitnessStack<Cx: MatchCx>(Vec<WitnessPat<Cx>>);
 
-impl<'tcx> WitnessStack<'tcx> {
+impl<Cx: MatchCx> WitnessStack<Cx> {
     /// Asserts that the witness contains a single pattern, and returns it.
-    fn single_pattern(self) -> WitnessPat<'tcx> {
+    fn single_pattern(self) -> WitnessPat<Cx> {
         assert_eq!(self.0.len(), 1);
         self.0.into_iter().next().unwrap()
     }
 
     /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern.
-    fn push_pattern(&mut self, pat: WitnessPat<'tcx>) {
+    fn push_pattern(&mut self, pat: WitnessPat<Cx>) {
         self.0.push(pat);
     }
 
@@ -1055,7 +1052,7 @@ impl<'tcx> WitnessStack<'tcx> {
     /// pats: [(false, "foo"), _, true]
     /// result: [Enum::Variant { a: (false, "foo"), b: _ }, true]
     /// ```
-    fn apply_constructor(&mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) {
+    fn apply_constructor(&mut self, pcx: &PatCtxt<'_, '_, Cx>, ctor: &Constructor<Cx>) {
         let len = self.0.len();
         let arity = ctor.arity(pcx);
         let fields = self.0.drain((len - arity)..).rev().collect();
@@ -1074,9 +1071,9 @@ impl<'tcx> WitnessStack<'tcx> {
 /// Just as the `Matrix` starts with a single column, by the end of the algorithm, this has a single
 /// column, which contains the patterns that are missing for the match to be exhaustive.
 #[derive(Debug, Clone)]
-struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>);
+struct WitnessMatrix<Cx: MatchCx>(Vec<WitnessStack<Cx>>);
 
-impl<'tcx> WitnessMatrix<'tcx> {
+impl<Cx: MatchCx> WitnessMatrix<Cx> {
     /// New matrix with no witnesses.
     fn empty() -> Self {
         WitnessMatrix(vec![])
@@ -1091,12 +1088,12 @@ impl<'tcx> WitnessMatrix<'tcx> {
         self.0.is_empty()
     }
     /// Asserts that there is a single column and returns the patterns in it.
-    fn single_column(self) -> Vec<WitnessPat<'tcx>> {
+    fn single_column(self) -> Vec<WitnessPat<Cx>> {
         self.0.into_iter().map(|w| w.single_pattern()).collect()
     }
 
     /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern.
-    fn push_pattern(&mut self, pat: WitnessPat<'tcx>) {
+    fn push_pattern(&mut self, pat: WitnessPat<Cx>) {
         for witness in self.0.iter_mut() {
             witness.push_pattern(pat.clone())
         }
@@ -1105,9 +1102,9 @@ impl<'tcx> WitnessMatrix<'tcx> {
     /// Reverses specialization by `ctor`. See the section on `unspecialize` at the top of the file.
     fn apply_constructor(
         &mut self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        missing_ctors: &[Constructor<'tcx>],
-        ctor: &Constructor<'tcx>,
+        pcx: &PatCtxt<'_, '_, Cx>,
+        missing_ctors: &[Constructor<Cx>],
+        ctor: &Constructor<Cx>,
         report_individual_missing_ctors: bool,
     ) {
         if self.is_empty() {
@@ -1168,12 +1165,12 @@ impl<'tcx> WitnessMatrix<'tcx> {
 ///     (using `apply_constructor` and by updating `row.useful` for each parent row).
 /// This is all explained at the top of the file.
 #[instrument(level = "debug", skip(cx, is_top_level, wildcard_arena), ret)]
-fn compute_exhaustiveness_and_usefulness<'a, 'p, 'tcx>(
-    cx: &'a MatchCheckCtxt<'p, 'tcx>,
-    matrix: &mut Matrix<'a, 'p, 'tcx>,
-    wildcard_arena: &'a TypedArena<DeconstructedPat<'p, 'tcx>>,
+fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: MatchCx>(
+    cx: &'a Cx,
+    matrix: &mut Matrix<'a, 'p, Cx>,
+    wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
     is_top_level: bool,
-) -> WitnessMatrix<'tcx> {
+) -> WitnessMatrix<Cx> {
     debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count()));
 
     let Some(ty) = matrix.head_ty() else {
@@ -1278,7 +1275,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, 'tcx>(
 
 /// Indicates whether or not a given arm is useful.
 #[derive(Clone, Debug)]
-pub enum Usefulness {
+pub enum Usefulness<Span> {
     /// The arm is useful. This additionally carries a set of or-pattern branches that have been
     /// found to be redundant despite the overall arm being useful. Used only in the presence of
     /// or-patterns, otherwise it stays empty.
@@ -1289,23 +1286,23 @@ pub enum Usefulness {
 }
 
 /// The output of checking a match for exhaustiveness and arm usefulness.
-pub struct UsefulnessReport<'p, 'tcx> {
+pub struct UsefulnessReport<'p, Cx: MatchCx> {
     /// For each arm of the input, whether that arm is useful after the arms above it.
-    pub arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Usefulness)>,
+    pub arm_usefulness: Vec<(MatchArm<'p, Cx>, Usefulness<Cx::Span>)>,
     /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
     /// exhaustiveness.
-    pub non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>,
+    pub non_exhaustiveness_witnesses: Vec<WitnessPat<Cx>>,
 }
 
 /// Computes whether a match is exhaustive and which of its arms are useful.
 #[instrument(skip(cx, arms, wildcard_arena), level = "debug")]
-pub(crate) fn compute_match_usefulness<'p, 'tcx>(
-    cx: &MatchCheckCtxt<'p, 'tcx>,
-    arms: &[MatchArm<'p, 'tcx>],
-    scrut_ty: Ty<'tcx>,
-    wildcard_arena: &TypedArena<DeconstructedPat<'p, 'tcx>>,
-) -> UsefulnessReport<'p, 'tcx> {
-    let scrut_validity = ValidityConstraint::from_bool(cx.known_valid_scrutinee);
+pub(crate) fn compute_match_usefulness<'p, Cx: MatchCx>(
+    cx: &Cx,
+    arms: &[MatchArm<'p, Cx>],
+    scrut_ty: Cx::Ty,
+    scrut_validity: ValidityConstraint,
+    wildcard_arena: &TypedArena<DeconstructedPat<'p, Cx>>,
+) -> UsefulnessReport<'p, Cx> {
     let mut matrix = Matrix::new(wildcard_arena, arms, scrut_ty, scrut_validity);
     let non_exhaustiveness_witnesses =
         compute_exhaustiveness_and_usefulness(cx, &mut matrix, wildcard_arena, true);