Auto merge of #118842 - Nadrieril:librarify-further, r=compiler-errors

Make exhaustiveness usable outside of rustc

With this PR, `rustc_pattern_analysis` compiles on stable (with the `stable` feature)! `rust-analyzer` will be able to use it to provide match-related diagnostics and refactors.

Two questions:
- Should I name the feature `nightly` instead of `rustc` for consistency with other crates? `rustc` makes more sense imo.
- `typed-arena` is an optional dependency but tidy made me add it to the allow-list anyway. Can I avoid that somehow?

r? `@compiler-errors`

1 files changed, 127 insertions, 114 deletions

diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index f268a551547..6b1de807797 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 [`TypeCx::ctors_for_ty`]. See
 //! the following sections for more accurate versions of the algorithm and corresponding links.
 //!
 //!
@@ -555,37 +555,52 @@
 use smallvec::{smallvec, SmallVec};
 use std::fmt;
 
-use rustc_data_structures::{captures::Captures, stack::ensure_sufficient_stack};
-use rustc_middle::ty::{self, Ty};
-use rustc_span::{Span, DUMMY_SP};
-
 use crate::constructor::{Constructor, ConstructorSet};
-use crate::cx::MatchCheckCtxt;
 use crate::pat::{DeconstructedPat, WitnessPat};
-use crate::MatchArm;
+use crate::{Captures, MatchArm, MatchCtxt, TypeCx, TypedArena};
 
 use self::ValidityConstraint::*;
 
-#[derive(Copy, Clone)]
-pub(crate) struct PatCtxt<'a, 'p, 'tcx> {
-    pub(crate) cx: &'a MatchCheckCtxt<'p, 'tcx>,
-    /// Type of the current column under investigation.
-    pub(crate) ty: Ty<'tcx>,
-    /// 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,
+#[cfg(feature = "rustc")]
+use rustc_data_structures::stack::ensure_sufficient_stack;
+#[cfg(not(feature = "rustc"))]
+pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
+    f()
 }
 
-impl<'a, 'p, 'tcx> PatCtxt<'a, 'p, 'tcx> {
-    /// A `PatCtxt` when code other than `is_useful` needs one.
-    pub(crate) fn new_dummy(cx: &'a MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
-        PatCtxt { cx, ty, is_top_level: false }
+/// Context that provides information local to a place under investigation.
+#[derive(Clone)]
+pub(crate) struct PlaceCtxt<'a, 'p, Cx: TypeCx> {
+    pub(crate) mcx: MatchCtxt<'a, 'p, Cx>,
+    /// Type of the place under investigation.
+    pub(crate) ty: Cx::Ty,
+    /// Whether the place is the original scrutinee place, as opposed to a subplace of it.
+    pub(crate) is_scrutinee: bool,
+}
+
+impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> {
+    /// A `PlaceCtxt` when code other than `is_useful` needs one.
+    #[cfg_attr(not(feature = "rustc"), allow(dead_code))]
+    pub(crate) fn new_dummy(mcx: MatchCtxt<'a, 'p, Cx>, ty: Cx::Ty) -> Self {
+        PlaceCtxt { mcx, ty, is_scrutinee: false }
+    }
+
+    pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize {
+        self.mcx.tycx.ctor_arity(ctor, self.ty)
+    }
+    pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<Cx>) -> &[Cx::Ty] {
+        self.mcx.tycx.ctor_sub_tys(ctor, self.ty)
+    }
+    pub(crate) fn ctors_for_ty(&self) -> ConstructorSet<Cx> {
+        self.mcx.tycx.ctors_for_ty(self.ty)
     }
 }
 
-impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> Copy for PlaceCtxt<'a, 'p, Cx> {}
+
+impl<'a, 'p, Cx: TypeCx> fmt::Debug for PlaceCtxt<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_struct("PatCtxt").field("ty", &self.ty).finish()
+        f.debug_struct("PlaceCtxt").field("ty", &self.ty).finish()
     }
 }
 
@@ -595,7 +610,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 enum ValidityConstraint {
     ValidOnly,
     MaybeInvalid,
     /// Option for backwards compatibility: the place is not known to be valid but we allow omitting
@@ -604,7 +619,7 @@ enum ValidityConstraint {
 }
 
 impl ValidityConstraint {
-    fn from_bool(is_valid_only: bool) -> Self {
+    pub fn from_bool(is_valid_only: bool) -> Self {
         if is_valid_only { ValidOnly } else { MaybeInvalid }
     }
 
@@ -629,12 +644,9 @@ 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<'tcx>(self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) -> Self {
+    fn specialize<Cx: TypeCx>(self, ctor: &Constructor<Cx>) -> Self {
         // We preserve validity except when we go inside a reference or a union field.
-        if matches!(ctor, Constructor::Single)
-            && (matches!(pcx.ty.kind(), ty::Ref(..))
-                || matches!(pcx.ty.kind(), ty::Adt(def, ..) if def.is_union()))
-        {
+        if matches!(ctor, Constructor::Ref | Constructor::UnionField) {
             // Validity of `x: &T` does not imply validity of `*x: T`.
             MaybeInvalid
         } else {
@@ -654,14 +666,18 @@ impl fmt::Display for ValidityConstraint {
 }
 
 /// Represents a pattern-tuple under investigation.
+// The three lifetimes are:
+// - 'a allocated by us
+// - 'p coming from the input
+// - Cx global compilation context
 #[derive(Clone)]
-struct PatStack<'p, 'tcx> {
+struct PatStack<'a, 'p, Cx: TypeCx> {
     // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well.
-    pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>,
+    pats: SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]>,
 }
 
-impl<'p, 'tcx> PatStack<'p, 'tcx> {
-    fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self {
+impl<'a, 'p, Cx: TypeCx> PatStack<'a, 'p, Cx> {
+    fn from_pattern(pat: &'a DeconstructedPat<'p, Cx>) -> Self {
         PatStack { pats: smallvec![pat] }
     }
 
@@ -673,17 +689,17 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> {
+    fn head(&self) -> &'a DeconstructedPat<'p, Cx> {
         self.pats[0]
     }
 
-    fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> {
+    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<'a>(&'a self) -> impl Iterator<Item = PatStack<'p, 'tcx>> + Captures<'a> {
+    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;
@@ -695,9 +711,9 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> {
     /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
     fn pop_head_constructor(
         &self,
-        pcx: &PatCtxt<'_, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
-    ) -> PatStack<'p, 'tcx> {
+        pcx: &PlaceCtxt<'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);
@@ -706,7 +722,7 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> {
     }
 }
 
-impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> 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, "+")?;
@@ -719,9 +735,9 @@ impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
 
 /// A row of the matrix.
 #[derive(Clone)]
-struct MatrixRow<'p, 'tcx> {
+struct MatrixRow<'a, 'p, Cx: TypeCx> {
     // The patterns in the row.
-    pats: PatStack<'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
@@ -734,7 +750,7 @@ struct MatrixRow<'p, 'tcx> {
     useful: bool,
 }
 
-impl<'p, 'tcx> MatrixRow<'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> MatrixRow<'a, 'p, Cx> {
     fn is_empty(&self) -> bool {
         self.pats.is_empty()
     }
@@ -743,17 +759,17 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> {
+    fn head(&self) -> &'a DeconstructedPat<'p, Cx> {
         self.pats.head()
     }
 
-    fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> {
+    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<'a>(&'a self) -> impl Iterator<Item = MatrixRow<'p, 'tcx>> + Captures<'a> {
+    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,
@@ -766,10 +782,10 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> {
     /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
     fn pop_head_constructor(
         &self,
-        pcx: &PatCtxt<'_, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
+        pcx: &PlaceCtxt<'a, 'p, Cx>,
+        ctor: &Constructor<Cx>,
         parent_row: usize,
-    ) -> MatrixRow<'p, 'tcx> {
+    ) -> MatrixRow<'a, 'p, Cx> {
         MatrixRow {
             pats: self.pats.pop_head_constructor(pcx, ctor),
             parent_row,
@@ -779,7 +795,7 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> {
     }
 }
 
-impl<'p, 'tcx> fmt::Debug for MatrixRow<'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> fmt::Debug for MatrixRow<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         self.pats.fmt(f)
     }
@@ -796,22 +812,22 @@ impl<'p, 'tcx> fmt::Debug for MatrixRow<'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<'p, 'tcx> {
+struct Matrix<'a, 'p, Cx: TypeCx> {
     /// 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<'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<'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<'p, 'tcx> Matrix<'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> 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<'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() {
@@ -823,16 +839,14 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
     }
 
     /// Build a new matrix from an iterator of `MatchArm`s.
-    fn new<'a>(
-        cx: &MatchCheckCtxt<'p, 'tcx>,
-        arms: &[MatchArm<'p, 'tcx>],
-        scrut_ty: Ty<'tcx>,
+    fn new(
+        wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
+        arms: &'a [MatchArm<'p, Cx>],
+        scrut_ty: Cx::Ty,
         scrut_validity: ValidityConstraint,
-    ) -> Self
-    where
-        'p: 'a,
-    {
-        let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP));
+    ) -> Self {
+        let wild_pattern =
+            wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty, Default::default()));
         let wildcard_row = PatStack::from_pattern(wild_pattern);
         let mut matrix = Matrix {
             rows: Vec::with_capacity(arms.len()),
@@ -851,7 +865,7 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
         matrix
     }
 
-    fn head_ty(&self) -> Option<Ty<'tcx>> {
+    fn head_ty(&self) -> Option<Cx::Ty> {
         if self.column_count() == 0 {
             return None;
         }
@@ -859,11 +873,10 @@ impl<'p, 'tcx> Matrix<'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.
-        let is_opaque = |ty: Ty<'tcx>| matches!(ty.kind(), ty::Alias(ty::Opaque, ..));
-        if is_opaque(ty) {
+        if Cx::is_opaque_ty(ty) {
             for pat in self.heads() {
                 let pat_ty = pat.ty();
-                if !is_opaque(pat_ty) {
+                if !Cx::is_opaque_ty(pat_ty) {
                     ty = pat_ty;
                     break;
                 }
@@ -875,34 +888,34 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
         self.wildcard_row.len()
     }
 
-    fn rows<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = &'a MatrixRow<'p, 'tcx>> + Clone + DoubleEndedIterator + ExactSizeIterator
+    fn rows<'b>(
+        &'b self,
+    ) -> impl Iterator<Item = &'b MatrixRow<'a, 'p, Cx>> + Clone + DoubleEndedIterator + ExactSizeIterator
     {
         self.rows.iter()
     }
-    fn rows_mut<'a>(
-        &'a mut self,
-    ) -> impl Iterator<Item = &'a mut MatrixRow<'p, 'tcx>> + DoubleEndedIterator + ExactSizeIterator
+    fn rows_mut<'b>(
+        &'b mut self,
+    ) -> impl Iterator<Item = &'b mut MatrixRow<'a, 'p, Cx>> + DoubleEndedIterator + ExactSizeIterator
     {
         self.rows.iter_mut()
     }
 
     /// Iterate over the first pattern of each row.
-    fn heads<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> {
+    fn heads<'b>(
+        &'b self,
+    ) -> 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<'_, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
-    ) -> Matrix<'p, 'tcx> {
+        pcx: &PlaceCtxt<'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(pcx, ctor);
+        let new_validity = self.place_validity[0].specialize(ctor);
         let new_place_validity = std::iter::repeat(new_validity)
             .take(ctor.arity(pcx))
             .chain(self.place_validity[1..].iter().copied())
@@ -929,7 +942,7 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
 /// + _     + [_, _, tail @ ..] +
 /// | ✓     | ?                 | // column validity
 /// ```
-impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
+impl<'a, 'p, Cx: TypeCx> fmt::Debug for Matrix<'a, 'p, Cx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "\n")?;
 
@@ -1020,17 +1033,17 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'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: TypeCx>(Vec<WitnessPat<Cx>>);
 
-impl<'tcx> WitnessStack<'tcx> {
+impl<Cx: TypeCx> 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);
     }
 
@@ -1048,7 +1061,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: &PlaceCtxt<'_, '_, Cx>, ctor: &Constructor<Cx>) {
         let len = self.0.len();
         let arity = ctor.arity(pcx);
         let fields = self.0.drain((len - arity)..).rev().collect();
@@ -1067,9 +1080,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: TypeCx>(Vec<WitnessStack<Cx>>);
 
-impl<'tcx> WitnessMatrix<'tcx> {
+impl<Cx: TypeCx> WitnessMatrix<Cx> {
     /// New matrix with no witnesses.
     fn empty() -> Self {
         WitnessMatrix(vec![])
@@ -1084,12 +1097,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())
         }
@@ -1098,9 +1111,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: &PlaceCtxt<'_, '_, Cx>,
+        missing_ctors: &[Constructor<Cx>],
+        ctor: &Constructor<Cx>,
         report_individual_missing_ctors: bool,
     ) {
         if self.is_empty() {
@@ -1160,12 +1173,12 @@ impl<'tcx> WitnessMatrix<'tcx> {
 /// - unspecialization, where we lift the results from the previous step into results for this step
 ///     (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), ret)]
-fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
-    cx: &MatchCheckCtxt<'p, 'tcx>,
-    matrix: &mut Matrix<'p, 'tcx>,
+#[instrument(level = "debug", skip(mcx, is_top_level), ret)]
+fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
+    mcx: MatchCtxt<'a, 'p, Cx>,
+    matrix: &mut Matrix<'a, '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 {
@@ -1185,7 +1198,7 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
     };
 
     debug!("ty: {ty:?}");
-    let pcx = &PatCtxt { cx, ty, is_top_level };
+    let pcx = &PlaceCtxt { mcx, ty, is_scrutinee: is_top_level };
 
     // Whether the place/column we are inspecting is known to contain valid data.
     let place_validity = matrix.place_validity[0];
@@ -1194,7 +1207,7 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
 
     // Analyze the constructors present in this column.
     let ctors = matrix.heads().map(|p| p.ctor());
-    let ctors_for_ty = &cx.ctors_for_ty(ty);
+    let ctors_for_ty = pcx.ctors_for_ty();
     let is_integers = matches!(ctors_for_ty, ConstructorSet::Integers { .. }); // For diagnostics.
     let split_set = ctors_for_ty.split(pcx, ctors);
     let all_missing = split_set.present.is_empty();
@@ -1228,7 +1241,7 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
         // Dig into rows that match `ctor`.
         let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor);
         let mut witnesses = ensure_sufficient_stack(|| {
-            compute_exhaustiveness_and_usefulness(cx, &mut spec_matrix, false)
+            compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix, false)
         });
 
         let counts_for_exhaustiveness = match ctor {
@@ -1270,34 +1283,34 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
 
 /// Indicates whether or not a given arm is useful.
 #[derive(Clone, Debug)]
-pub enum Usefulness {
+pub enum Usefulness<'p, Cx: TypeCx> {
     /// 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.
-    Useful(Vec<Span>),
+    Useful(Vec<&'p DeconstructedPat<'p, Cx>>),
     /// The arm is redundant and can be removed without changing the behavior of the match
     /// expression.
     Redundant,
 }
 
 /// The output of checking a match for exhaustiveness and arm usefulness.
-pub struct UsefulnessReport<'p, 'tcx> {
+pub struct UsefulnessReport<'p, Cx: TypeCx> {
     /// 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<'p, Cx>)>,
     /// 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), level = "debug")]
-pub(crate) fn compute_match_usefulness<'p, 'tcx>(
-    cx: &MatchCheckCtxt<'p, 'tcx>,
-    arms: &[MatchArm<'p, 'tcx>],
-    scrut_ty: Ty<'tcx>,
-) -> UsefulnessReport<'p, 'tcx> {
-    let scrut_validity = ValidityConstraint::from_bool(cx.known_valid_scrutinee);
-    let mut matrix = Matrix::new(cx, arms, scrut_ty, scrut_validity);
+pub fn compute_match_usefulness<'p, Cx: TypeCx>(
+    cx: MatchCtxt<'_, 'p, Cx>,
+    arms: &[MatchArm<'p, Cx>],
+    scrut_ty: Cx::Ty,
+    scrut_validity: ValidityConstraint,
+) -> UsefulnessReport<'p, Cx> {
+    let mut matrix = Matrix::new(cx.wildcard_arena, arms, scrut_ty, scrut_validity);
     let non_exhaustiveness_witnesses = compute_exhaustiveness_and_usefulness(cx, &mut matrix, true);
 
     let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column();
@@ -1308,7 +1321,7 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
             debug!(?arm);
             // We warn when a pattern is not useful.
             let usefulness = if arm.pat.is_useful() {
-                Usefulness::Useful(arm.pat.redundant_spans())
+                Usefulness::Useful(arm.pat.redundant_subpatterns())
             } else {
                 Usefulness::Redundant
             };