Rollup merge of #118822 - Nadrieril:librarify, r=compiler-errors

Extract exhaustiveness into its own crate

It now makes sense to extract exhaustiveness into its own crate! This was much-requested by rust-analyzer (they currently maintain by hand a copy of the algorithm), and I hope this can serve other projects e.g. clippy.

This is the churny PR: it exclusively moves code around. It's not yet useable outside of rustc but I wanted the churny parts to be out of the way.

r? `@compiler-errors`

17 files changed, 2588 insertions, 2460 deletions

diff --git a/compiler/rustc_driver_impl/Cargo.toml b/compiler/rustc_driver_impl/Cargo.toml
index f2a8c54b6d5..49042984553 100644
--- a/compiler/rustc_driver_impl/Cargo.toml
+++ b/compiler/rustc_driver_impl/Cargo.toml
@@ -38,6 +38,7 @@ rustc_mir_transform = { path = "../rustc_mir_transform" }
 rustc_monomorphize = { path = "../rustc_monomorphize" }
 rustc_parse = { path = "../rustc_parse" }
 rustc_passes = { path = "../rustc_passes" }
+rustc_pattern_analysis = { path = "../rustc_pattern_analysis" }
 rustc_privacy = { path = "../rustc_privacy" }
 rustc_query_system = { path = "../rustc_query_system" }
 rustc_resolve = { path = "../rustc_resolve" }
diff --git a/compiler/rustc_driver_impl/src/lib.rs b/compiler/rustc_driver_impl/src/lib.rs
index 1f60400b513..8b7a4dbff9d 100644
--- a/compiler/rustc_driver_impl/src/lib.rs
+++ b/compiler/rustc_driver_impl/src/lib.rs
@@ -128,6 +128,7 @@ pub static DEFAULT_LOCALE_RESOURCES: &[&str] = &[
     rustc_monomorphize::DEFAULT_LOCALE_RESOURCE,
     rustc_parse::DEFAULT_LOCALE_RESOURCE,
     rustc_passes::DEFAULT_LOCALE_RESOURCE,
+    rustc_pattern_analysis::DEFAULT_LOCALE_RESOURCE,
     rustc_privacy::DEFAULT_LOCALE_RESOURCE,
     rustc_query_system::DEFAULT_LOCALE_RESOURCE,
     rustc_resolve::DEFAULT_LOCALE_RESOURCE,
diff --git a/compiler/rustc_mir_build/Cargo.toml b/compiler/rustc_mir_build/Cargo.toml
index db542234052..6d681dc295e 100644
--- a/compiler/rustc_mir_build/Cargo.toml
+++ b/compiler/rustc_mir_build/Cargo.toml
@@ -17,6 +17,7 @@ rustc_index = { path = "../rustc_index" }
 rustc_infer = { path = "../rustc_infer" }
 rustc_macros = { path = "../rustc_macros" }
 rustc_middle = { path = "../rustc_middle" }
+rustc_pattern_analysis = { path = "../rustc_pattern_analysis" }
 rustc_session = { path = "../rustc_session" }
 rustc_span = { path = "../rustc_span" }
 rustc_target = { path = "../rustc_target" }
diff --git a/compiler/rustc_mir_build/messages.ftl b/compiler/rustc_mir_build/messages.ftl
index c8d6c2114e9..615b553434f 100644
--- a/compiler/rustc_mir_build/messages.ftl
+++ b/compiler/rustc_mir_build/messages.ftl
@@ -237,15 +237,6 @@ mir_build_non_const_path = runtime values cannot be referenced in patterns
 mir_build_non_exhaustive_match_all_arms_guarded =
     match arms with guards don't count towards exhaustivity
 
-mir_build_non_exhaustive_omitted_pattern = some variants are not matched explicitly
-    .help = ensure that all variants are matched explicitly by adding the suggested match arms
-    .note = the matched value is of type `{$scrut_ty}` and the `non_exhaustive_omitted_patterns` attribute was found
-
-mir_build_non_exhaustive_omitted_pattern_lint_on_arm = the lint level must be set on the whole match
-    .help = it no longer has any effect to set the lint level on an individual match arm
-    .label = remove this attribute
-    .suggestion = set the lint level on the whole match
-
 mir_build_non_exhaustive_patterns_type_not_empty = non-exhaustive patterns: type `{$ty}` is non-empty
     .def_note = `{$peeled_ty}` defined here
     .type_note = the matched value is of type `{$ty}`
@@ -260,10 +251,6 @@ mir_build_non_partial_eq_match =
 mir_build_nontrivial_structural_match =
     to use a constant of type `{$non_sm_ty}` in a pattern, the constant's initializer must be trivial or `{$non_sm_ty}` must be annotated with `#[derive(PartialEq, Eq)]`
 
-mir_build_overlapping_range_endpoints = multiple patterns overlap on their endpoints
-    .range = ... with this range
-    .note = you likely meant to write mutually exclusive ranges
-
 mir_build_pattern_not_covered = refutable pattern in {$origin}
     .pattern_ty = the matched value is of type `{$pattern_ty}`
 
@@ -317,13 +304,6 @@ mir_build_unconditional_recursion = function cannot return without recursing
 
 mir_build_unconditional_recursion_call_site_label = recursive call site
 
-mir_build_uncovered = {$count ->
-        [1] pattern `{$witness_1}`
-        [2] patterns `{$witness_1}` and `{$witness_2}`
-        [3] patterns `{$witness_1}`, `{$witness_2}` and `{$witness_3}`
-        *[other] patterns `{$witness_1}`, `{$witness_2}`, `{$witness_3}` and {$remainder} more
-    } not covered
-
 mir_build_union_field_requires_unsafe =
     access to union field is unsafe and requires unsafe block
     .note = the field may not be properly initialized: using uninitialized data will cause undefined behavior
diff --git a/compiler/rustc_mir_build/src/errors.rs b/compiler/rustc_mir_build/src/errors.rs
index 8d2a559e73c..9baae706dff 100644
--- a/compiler/rustc_mir_build/src/errors.rs
+++ b/compiler/rustc_mir_build/src/errors.rs
@@ -1,15 +1,12 @@
-use crate::{
-    fluent_generated as fluent,
-    thir::pattern::{deconstruct_pat::WitnessPat, MatchCheckCtxt},
-};
+use crate::fluent_generated as fluent;
 use rustc_errors::DiagnosticArgValue;
 use rustc_errors::{
     error_code, AddToDiagnostic, Applicability, Diagnostic, DiagnosticBuilder, ErrorGuaranteed,
     Handler, IntoDiagnostic, MultiSpan, SubdiagnosticMessage,
 };
 use rustc_macros::{Diagnostic, LintDiagnostic, Subdiagnostic};
-use rustc_middle::thir::Pat;
 use rustc_middle::ty::{self, Ty};
+use rustc_pattern_analysis::{cx::MatchCheckCtxt, errors::Uncovered};
 use rustc_span::symbol::Symbol;
 use rustc_span::Span;
 
@@ -812,94 +809,6 @@ pub struct NonPartialEqMatch<'tcx> {
     pub non_peq_ty: Ty<'tcx>,
 }
 
-#[derive(LintDiagnostic)]
-#[diag(mir_build_overlapping_range_endpoints)]
-#[note]
-pub struct OverlappingRangeEndpoints<'tcx> {
-    #[label(mir_build_range)]
-    pub range: Span,
-    #[subdiagnostic]
-    pub overlap: Vec<Overlap<'tcx>>,
-}
-
-pub struct Overlap<'tcx> {
-    pub span: Span,
-    pub range: Pat<'tcx>,
-}
-
-impl<'tcx> AddToDiagnostic for Overlap<'tcx> {
-    fn add_to_diagnostic_with<F>(self, diag: &mut Diagnostic, _: F)
-    where
-        F: Fn(&mut Diagnostic, SubdiagnosticMessage) -> SubdiagnosticMessage,
-    {
-        let Overlap { span, range } = self;
-
-        // FIXME(mejrs) unfortunately `#[derive(LintDiagnostic)]`
-        // does not support `#[subdiagnostic(eager)]`...
-        let message = format!("this range overlaps on `{range}`...");
-        diag.span_label(span, message);
-    }
-}
-
-#[derive(LintDiagnostic)]
-#[diag(mir_build_non_exhaustive_omitted_pattern)]
-#[help]
-#[note]
-pub(crate) struct NonExhaustiveOmittedPattern<'tcx> {
-    pub scrut_ty: Ty<'tcx>,
-    #[subdiagnostic]
-    pub uncovered: Uncovered<'tcx>,
-}
-
-#[derive(LintDiagnostic)]
-#[diag(mir_build_non_exhaustive_omitted_pattern_lint_on_arm)]
-#[help]
-pub(crate) struct NonExhaustiveOmittedPatternLintOnArm {
-    #[label]
-    pub lint_span: Span,
-    #[suggestion(code = "#[{lint_level}({lint_name})]\n", applicability = "maybe-incorrect")]
-    pub suggest_lint_on_match: Option<Span>,
-    pub lint_level: &'static str,
-    pub lint_name: &'static str,
-}
-
-#[derive(Subdiagnostic)]
-#[label(mir_build_uncovered)]
-pub(crate) struct Uncovered<'tcx> {
-    #[primary_span]
-    span: Span,
-    count: usize,
-    witness_1: Pat<'tcx>,
-    witness_2: Pat<'tcx>,
-    witness_3: Pat<'tcx>,
-    remainder: usize,
-}
-
-impl<'tcx> Uncovered<'tcx> {
-    pub fn new<'p>(
-        span: Span,
-        cx: &MatchCheckCtxt<'p, 'tcx>,
-        witnesses: Vec<WitnessPat<'tcx>>,
-    ) -> Self {
-        let witness_1 = witnesses.get(0).unwrap().to_diagnostic_pat(cx);
-        Self {
-            span,
-            count: witnesses.len(),
-            // Substitute dummy values if witnesses is smaller than 3. These will never be read.
-            witness_2: witnesses
-                .get(1)
-                .map(|w| w.to_diagnostic_pat(cx))
-                .unwrap_or_else(|| witness_1.clone()),
-            witness_3: witnesses
-                .get(2)
-                .map(|w| w.to_diagnostic_pat(cx))
-                .unwrap_or_else(|| witness_1.clone()),
-            witness_1,
-            remainder: witnesses.len().saturating_sub(3),
-        }
-    }
-}
-
 #[derive(Diagnostic)]
 #[diag(mir_build_pattern_not_covered, code = "E0005")]
 pub(crate) struct PatternNotCovered<'s, 'tcx> {
diff --git a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
index fcd548821f2..09e0b30a5c7 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -1,7 +1,9 @@
-use super::deconstruct_pat::{Constructor, DeconstructedPat, WitnessPat};
-use super::usefulness::{
-    compute_match_usefulness, MatchArm, MatchCheckCtxt, Usefulness, UsefulnessReport,
-};
+use rustc_pattern_analysis::constructor::Constructor;
+use rustc_pattern_analysis::cx::MatchCheckCtxt;
+use rustc_pattern_analysis::errors::Uncovered;
+use rustc_pattern_analysis::pat::{DeconstructedPat, WitnessPat};
+use rustc_pattern_analysis::usefulness::{Usefulness, UsefulnessReport};
+use rustc_pattern_analysis::{analyze_match, MatchArm};
 
 use crate::errors::*;
 
@@ -284,7 +286,7 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
                 check_borrow_conflicts_in_at_patterns(self, pat);
                 check_for_bindings_named_same_as_variants(self, pat, refutable);
             });
-            Ok(cx.pattern_arena.alloc(DeconstructedPat::from_pat(cx, pat)))
+            Ok(cx.pattern_arena.alloc(cx.lower_pat(pat)))
         }
     }
 
@@ -433,7 +435,7 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         }
 
         let scrut_ty = scrut.ty;
-        let report = compute_match_usefulness(&cx, &tarms, scrut_ty);
+        let report = analyze_match(&cx, &tarms, scrut_ty);
 
         match source {
             // Don't report arm reachability of desugared `match $iter.into_iter() { iter => .. }`
@@ -547,7 +549,7 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         let cx = self.new_cx(refutability, None, scrut, pat.span);
         let pat = self.lower_pattern(&cx, pat)?;
         let arms = [MatchArm { pat, hir_id: self.lint_level, has_guard: false }];
-        let report = compute_match_usefulness(&cx, &arms, pat.ty());
+        let report = analyze_match(&cx, &arms, pat.ty());
         Ok((cx, report))
     }
 
@@ -924,7 +926,7 @@ fn report_non_exhaustive_match<'p, 'tcx>(
         pattern = if witnesses.len() < 4 {
             witnesses
                 .iter()
-                .map(|witness| witness.to_diagnostic_pat(cx).to_string())
+                .map(|witness| cx.hoist_witness_pat(witness).to_string())
                 .collect::<Vec<String>>()
                 .join(" | ")
         } else {
@@ -948,7 +950,7 @@ fn report_non_exhaustive_match<'p, 'tcx>(
     if !is_empty_match {
         let mut non_exhaustive_tys = FxHashSet::default();
         // Look at the first witness.
-        collect_non_exhaustive_tys(cx.tcx, &witnesses[0], &mut non_exhaustive_tys);
+        collect_non_exhaustive_tys(cx, &witnesses[0], &mut non_exhaustive_tys);
 
         for ty in non_exhaustive_tys {
             if ty.is_ptr_sized_integral() {
@@ -1083,13 +1085,13 @@ fn joined_uncovered_patterns<'p, 'tcx>(
     witnesses: &[WitnessPat<'tcx>],
 ) -> String {
     const LIMIT: usize = 3;
-    let pat_to_str = |pat: &WitnessPat<'tcx>| pat.to_diagnostic_pat(cx).to_string();
+    let pat_to_str = |pat: &WitnessPat<'tcx>| cx.hoist_witness_pat(pat).to_string();
     match witnesses {
         [] => bug!(),
-        [witness] => format!("`{}`", witness.to_diagnostic_pat(cx)),
+        [witness] => format!("`{}`", cx.hoist_witness_pat(witness)),
         [head @ .., tail] if head.len() < LIMIT => {
             let head: Vec<_> = head.iter().map(pat_to_str).collect();
-            format!("`{}` and `{}`", head.join("`, `"), tail.to_diagnostic_pat(cx))
+            format!("`{}` and `{}`", head.join("`, `"), cx.hoist_witness_pat(tail))
         }
         _ => {
             let (head, tail) = witnesses.split_at(LIMIT);
@@ -1100,7 +1102,7 @@ fn joined_uncovered_patterns<'p, 'tcx>(
 }
 
 fn collect_non_exhaustive_tys<'tcx>(
-    tcx: TyCtxt<'tcx>,
+    cx: &MatchCheckCtxt<'_, 'tcx>,
     pat: &WitnessPat<'tcx>,
     non_exhaustive_tys: &mut FxHashSet<Ty<'tcx>>,
 ) {
@@ -1108,13 +1110,13 @@ fn collect_non_exhaustive_tys<'tcx>(
         non_exhaustive_tys.insert(pat.ty());
     }
     if let Constructor::IntRange(range) = pat.ctor() {
-        if range.is_beyond_boundaries(pat.ty(), tcx) {
+        if cx.is_range_beyond_boundaries(range, pat.ty()) {
             // The range denotes the values before `isize::MIN` or the values after `usize::MAX`/`isize::MAX`.
             non_exhaustive_tys.insert(pat.ty());
         }
     }
     pat.iter_fields()
-        .for_each(|field_pat| collect_non_exhaustive_tys(tcx, field_pat, non_exhaustive_tys))
+        .for_each(|field_pat| collect_non_exhaustive_tys(cx, field_pat, non_exhaustive_tys))
 }
 
 fn report_adt_defined_here<'tcx>(
diff --git a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
deleted file mode 100644
index ef20b0f039b..00000000000
--- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
+++ /dev/null
@@ -1,1964 +0,0 @@
-//! As explained in [`super::usefulness`], values and patterns are made from constructors applied to
-//! fields. This file defines a `Constructor` enum, a `Fields` struct, and various operations to
-//! manipulate them and convert them from/to patterns.
-//!
-//! There are two important bits of core logic in this file: constructor inclusion and constructor
-//! splitting. Constructor inclusion, i.e. whether a constructor is included in/covered by another,
-//! is straightforward and defined in [`Constructor::is_covered_by`].
-//!
-//! Constructor splitting is mentioned in [`super::usefulness`] but not detailed. We describe it
-//! precisely here.
-//!
-//!
-//!
-//! # Constructor grouping and splitting
-//!
-//! As explained in the corresponding section in [`super::usefulness`], to make usefulness tractable
-//! we need to group together constructors that have the same effect when they are used to
-//! specialize the matrix.
-//!
-//! Example:
-//! ```compile_fail,E0004
-//! match (0, false) {
-//!     (0 ..=100, true) => {}
-//!     (50..=150, false) => {}
-//!     (0 ..=200, _) => {}
-//! }
-//! ```
-//!
-//! In this example we can restrict specialization to 5 cases: `0..50`, `50..=100`, `101..=150`,
-//! `151..=200` and `200..`.
-//!
-//! In [`super::usefulness`], we had said that `specialize` only takes value-only constructors. We
-//! now relax this restriction: we allow `specialize` to take constructors like `0..50` as long as
-//! we're careful to only do that with constructors that make sense. For example, `specialize(0..50,
-//! (0..=100, true))` is sensible, but `specialize(50..=200, (0..=100, true))` is not.
-//!
-//! Constructor splitting looks at the constructors in the first column of the matrix and constructs
-//! such a sensible set of constructors. Formally, we want to find a smallest disjoint set of
-//! constructors:
-//! - Whose union covers the whole type, and
-//! - 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 [`ConstructorSet::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`].
-//!
-//! Constructor splitting has two interesting special cases: integer range splitting (see
-//! [`IntRange::split`]) and slice splitting (see [`Slice::split`]).
-//!
-//!
-//!
-//! # The `Missing` constructor
-//!
-//! We detail a special case of constructor splitting that is a bit subtle. Take the following:
-//!
-//! ```
-//! enum Direction { North, South, East, West }
-//! # let wind = (Direction::North, 0u8);
-//! match wind {
-//!     (Direction::North, 50..) => {}
-//!     (_, _) => {}
-//! }
-//! ```
-//!
-//! Here we expect constructor splitting to output two cases: `North`, and "everything else". This
-//! "everything else" is represented by [`Constructor::Missing`]. Unlike other constructors, it's a
-//! bit contextual: to know the exact list of constructors it represents we have to look at the
-//! column. In practice however we don't need to, because by construction it only matches rows that
-//! have wildcards. This is how this constructor is special: the only constructor that covers it is
-//! `Wildcard`.
-//!
-//! The only place where we care about which constructors `Missing` represents is in diagnostics
-//! (see `super::usefulness::WitnessMatrix::apply_constructor`).
-//!
-//! We choose whether to specialize with `Missing` in
-//! `super::usefulness::compute_exhaustiveness_and_reachability`.
-//!
-//!
-//!
-//! ## Empty types, empty constructors, and the `exhaustive_patterns` feature
-//!
-//! An empty type is a type that has no valid value, like `!`, `enum Void {}`, or `Result<!, !>`.
-//! They require careful handling.
-//!
-//! First, for soundness reasons related to the possible existence of invalid values, by default we
-//! don't treat empty types as empty. We force them to be matched with wildcards. Except if the
-//! `exhaustive_patterns` feature is turned on, in which case we do treat them as empty. And also
-//! except if the type has no constructors (like `enum Void {}` but not like `Result<!, !>`), we
-//! specifically allow `match void {}` to be exhaustive. There are additionally considerations of
-//! place validity that are handled in `super::usefulness`. Yes this is a bit tricky.
-//!
-//! The second thing is that regardless of the above, it is always allowed to use all the
-//! constructors of a type. For example, all the following is ok:
-//!
-//! ```rust,ignore(example)
-//! # #![feature(never_type)]
-//! # #![feature(exhaustive_patterns)]
-//! fn foo(x: Option<!>) {
-//!   match x {
-//!     None => {}
-//!     Some(_) => {}
-//!   }
-//! }
-//! fn bar(x: &[!]) -> u32 {
-//!   match x {
-//!     [] => 1,
-//!     [_] => 2,
-//!     [_, _] => 3,
-//!   }
-//! }
-//! ```
-//!
-//! Moreover, take the following:
-//!
-//! ```rust
-//! # #![feature(never_type)]
-//! # #![feature(exhaustive_patterns)]
-//! # let x = None::<!>;
-//! match x {
-//!   None => {}
-//! }
-//! ```
-//!
-//! On a normal type, we would identify `Some` as missing and tell the user. If `x: Option<!>`
-//! however (and `exhaustive_patterns` is on), it's ok to omit `Some`. When listing the constructors
-//! of a type, we must therefore track which can be omitted.
-//!
-//! Let's call "empty" a constructor that matches no valid value for the type, like `Some` for the
-//! type `Option<!>`. What this all means is that `ConstructorSet` must know which constructors are
-//! empty. The difference between empty and nonempty constructors is that empty constructors need
-//! not be present for the match to be exhaustive.
-//!
-//! A final remark: empty constructors of arity 0 break specialization, we must avoid them. The
-//! reason is that if we specialize by them, nothing remains to witness the emptiness; the rest of
-//! 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 [`ConstructorSet::for_ty`] and [`ConstructorSet::split`]. The invariants
-//! of [`SplitConstructorSet`] are also of interest.
-//!
-//!
-//!
-//! ## Opaque patterns
-//!
-//! Some patterns, such as constants that are not allowed to be matched structurally, cannot be
-//! inspected, which we handle with `Constructor::Opaque`. Since we know nothing of these patterns,
-//! we assume they never cover each other. In order to respect the invariants of
-//! [`SplitConstructorSet`], we give each `Opaque` constructor a unique id so we can recognize it.
-
-use std::cell::Cell;
-use std::cmp::{self, max, min, Ordering};
-use std::fmt;
-use std::iter::once;
-
-use smallvec::{smallvec, SmallVec};
-
-use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS};
-use rustc_data_structures::captures::Captures;
-use rustc_data_structures::fx::FxHashSet;
-use rustc_hir::RangeEnd;
-use rustc_index::{Idx, IndexVec};
-use rustc_middle::middle::stability::EvalResult;
-use rustc_middle::mir;
-use rustc_middle::mir::interpret::Scalar;
-use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
-use rustc_middle::ty::layout::IntegerExt;
-use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef};
-use rustc_span::{Span, DUMMY_SP};
-use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
-
-use self::Constructor::*;
-use self::MaybeInfiniteInt::*;
-use self::SliceKind::*;
-
-use super::usefulness::{MatchCheckCtxt, PatCtxt};
-
-/// 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>>) {
-        if let PatKind::Or { pats } = &pat.kind {
-            for pat in pats.iter() {
-                expand(pat, vec);
-            }
-        } else {
-            vec.push(pat)
-        }
-    }
-
-    let mut pats = Vec::new();
-    expand(pat, &mut pats);
-    pats
-}
-
-/// Whether we have seen a constructor in the column or not.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
-enum Presence {
-    Unseen,
-    Seen,
-}
-
-/// A possibly infinite integer. Values are encoded such that the ordering on `u128` matches the
-/// natural order on the original type. For example, `-128i8` is encoded as `0` and `127i8` as
-/// `255`. See `signed_bias` for details.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
-pub(crate) enum MaybeInfiniteInt {
-    NegInfinity,
-    /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`.
-    Finite(u128),
-    /// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range.
-    JustAfterMax,
-    PosInfinity,
-}
-
-impl MaybeInfiniteInt {
-    // The return value of `signed_bias` should be XORed with a value to encode/decode it.
-    fn signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> u128 {
-        match *ty.kind() {
-            ty::Int(ity) => {
-                let bits = Integer::from_int_ty(&tcx, ity).size().bits() as u128;
-                1u128 << (bits - 1)
-            }
-            _ => 0,
-        }
-    }
-
-    fn new_finite(tcx: TyCtxt<'_>, ty: Ty<'_>, bits: u128) -> Self {
-        let bias = Self::signed_bias(tcx, ty);
-        // Perform a shift if the underlying types are signed, which makes the interval arithmetic
-        // type-independent.
-        let x = bits ^ bias;
-        Finite(x)
-    }
-    fn from_pat_range_bdy<'tcx>(
-        bdy: PatRangeBoundary<'tcx>,
-        ty: Ty<'tcx>,
-        tcx: TyCtxt<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-    ) -> Self {
-        match bdy {
-            PatRangeBoundary::NegInfinity => NegInfinity,
-            PatRangeBoundary::Finite(value) => {
-                let bits = value.eval_bits(tcx, param_env);
-                Self::new_finite(tcx, ty, bits)
-            }
-            PatRangeBoundary::PosInfinity => PosInfinity,
-        }
-    }
-
-    /// Used only for diagnostics.
-    /// Note: it is possible to get `isize/usize::MAX+1` here, as explained in the doc for
-    /// [`IntRange::split`]. This cannot be represented as a `Const`, so we represent it with
-    /// `PosInfinity`.
-    fn to_diagnostic_pat_range_bdy<'tcx>(
-        self,
-        ty: Ty<'tcx>,
-        tcx: TyCtxt<'tcx>,
-    ) -> PatRangeBoundary<'tcx> {
-        match self {
-            NegInfinity => PatRangeBoundary::NegInfinity,
-            Finite(x) => {
-                let bias = Self::signed_bias(tcx, ty);
-                let bits = x ^ bias;
-                let size = ty.primitive_size(tcx);
-                match Scalar::try_from_uint(bits, size) {
-                    Some(scalar) => {
-                        let value = mir::Const::from_scalar(tcx, scalar, ty);
-                        PatRangeBoundary::Finite(value)
-                    }
-                    // The value doesn't fit. Since `x >= 0` and 0 always encodes the minimum value
-                    // for a type, the problem isn't that the value is too small. So it must be too
-                    // large.
-                    None => PatRangeBoundary::PosInfinity,
-                }
-            }
-            JustAfterMax | PosInfinity => PatRangeBoundary::PosInfinity,
-        }
-    }
-
-    /// Note: this will not turn a finite value into an infinite one or vice-versa.
-    pub(crate) fn minus_one(self) -> Self {
-        match self {
-            Finite(n) => match n.checked_sub(1) {
-                Some(m) => Finite(m),
-                None => bug!(),
-            },
-            JustAfterMax => Finite(u128::MAX),
-            x => x,
-        }
-    }
-    /// Note: this will not turn a finite value into an infinite one or vice-versa.
-    pub(crate) fn plus_one(self) -> Self {
-        match self {
-            Finite(n) => match n.checked_add(1) {
-                Some(m) => Finite(m),
-                None => JustAfterMax,
-            },
-            JustAfterMax => bug!(),
-            x => x,
-        }
-    }
-}
-
-/// An exclusive interval, used for precise integer exhaustiveness checking. `IntRange`s always
-/// store a contiguous range.
-///
-/// `IntRange` is never used to encode an empty range or a "range" that wraps around the (offset)
-/// space: i.e., `range.lo < range.hi`.
-#[derive(Clone, Copy, PartialEq, Eq)]
-pub(crate) struct IntRange {
-    pub(crate) lo: MaybeInfiniteInt, // Must not be `PosInfinity`.
-    pub(crate) hi: MaybeInfiniteInt, // Must not be `NegInfinity`.
-}
-
-impl IntRange {
-    #[inline]
-    pub(super) fn is_integral(ty: Ty<'_>) -> bool {
-        matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_))
-    }
-
-    /// Best effort; will not know that e.g. `255u8..` is a singleton.
-    pub(super) fn is_singleton(&self) -> bool {
-        // Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite
-        // to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`.
-        self.lo.plus_one() == self.hi
-    }
-
-    #[inline]
-    fn from_bits<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, bits: u128) -> IntRange {
-        let x = MaybeInfiniteInt::new_finite(tcx, ty, bits);
-        IntRange { lo: x, hi: x.plus_one() }
-    }
-
-    #[inline]
-    fn from_range(lo: MaybeInfiniteInt, mut hi: MaybeInfiniteInt, end: RangeEnd) -> IntRange {
-        if end == RangeEnd::Included {
-            hi = hi.plus_one();
-        }
-        if lo >= hi {
-            // This should have been caught earlier by E0030.
-            bug!("malformed range pattern: {lo:?}..{hi:?}");
-        }
-        IntRange { lo, hi }
-    }
-
-    fn is_subrange(&self, other: &Self) -> bool {
-        other.lo <= self.lo && self.hi <= other.hi
-    }
-
-    fn intersection(&self, other: &Self) -> Option<Self> {
-        if self.lo < other.hi && other.lo < self.hi {
-            Some(IntRange { lo: max(self.lo, other.lo), hi: min(self.hi, other.hi) })
-        } else {
-            None
-        }
-    }
-
-    /// Partition a range of integers into disjoint subranges. This does constructor splitting for
-    /// integer ranges as explained at the top of the file.
-    ///
-    /// This returns an output that covers `self`. The output is split so that the only
-    /// intersections between an output range and a column range are inclusions. No output range
-    /// straddles the boundary of one of the inputs.
-    ///
-    /// Additionally, we track for each output range whether it is covered by one of the column ranges or not.
-    ///
-    /// The following input:
-    /// ```text
-    ///   (--------------------------) // `self`
-    /// (------) (----------)    (-)
-    ///     (------) (--------)
-    /// ```
-    /// is first intersected with `self`:
-    /// ```text
-    ///   (--------------------------) // `self`
-    ///   (----) (----------)    (-)
-    ///     (------) (--------)
-    /// ```
-    /// and then iterated over as follows:
-    /// ```text
-    ///   (-(--)-(-)-(------)-)--(-)-
-    /// ```
-    /// where each sequence of dashes is an output range, and dashes outside parentheses are marked
-    /// as `Presence::Missing`.
-    ///
-    /// ## `isize`/`usize`
-    ///
-    /// Whereas a wildcard of type `i32` stands for the range `i32::MIN..=i32::MAX`, a `usize`
-    /// wildcard stands for `0..PosInfinity` and a `isize` wildcard stands for
-    /// `NegInfinity..PosInfinity`. In other words, as far as `IntRange` is concerned, there are
-    /// values before `isize::MIN` and after `usize::MAX`/`isize::MAX`.
-    /// This is to avoid e.g. `0..(u32::MAX as usize)` from being exhaustive on one architecture and
-    /// not others. This was decided in <https://github.com/rust-lang/rfcs/pull/2591>.
-    ///
-    /// These infinities affect splitting subtly: it is possible to get `NegInfinity..0` and
-    /// `usize::MAX+1..PosInfinity` in the output. Diagnostics must be careful to handle these
-    /// fictitious ranges sensibly.
-    fn split(
-        &self,
-        column_ranges: impl Iterator<Item = IntRange>,
-    ) -> impl Iterator<Item = (Presence, IntRange)> {
-        // The boundaries of ranges in `column_ranges` intersected with `self`.
-        // We do parenthesis matching for input ranges. A boundary counts as +1 if it starts
-        // a range and -1 if it ends it. When the count is > 0 between two boundaries, we
-        // are within an input range.
-        let mut boundaries: Vec<(MaybeInfiniteInt, isize)> = column_ranges
-            .filter_map(|r| self.intersection(&r))
-            .flat_map(|r| [(r.lo, 1), (r.hi, -1)])
-            .collect();
-        // We sort by boundary, and for each boundary we sort the "closing parentheses" first. The
-        // order of +1/-1 for a same boundary value is actually irrelevant, because we only look at
-        // the accumulated count between distinct boundary values.
-        boundaries.sort_unstable();
-
-        // Accumulate parenthesis counts.
-        let mut paren_counter = 0isize;
-        // Gather pairs of adjacent boundaries.
-        let mut prev_bdy = self.lo;
-        boundaries
-            .into_iter()
-            // End with the end of the range. The count is ignored.
-            .chain(once((self.hi, 0)))
-            // List pairs of adjacent boundaries and the count between them.
-            .map(move |(bdy, delta)| {
-                // `delta` affects the count as we cross `bdy`, so the relevant count between
-                // `prev_bdy` and `bdy` is untouched by `delta`.
-                let ret = (prev_bdy, paren_counter, bdy);
-                prev_bdy = bdy;
-                paren_counter += delta;
-                ret
-            })
-            // Skip empty ranges.
-            .filter(|&(prev_bdy, _, bdy)| prev_bdy != bdy)
-            // Convert back to ranges.
-            .map(move |(prev_bdy, paren_count, bdy)| {
-                use Presence::*;
-                let presence = if paren_count > 0 { Seen } else { Unseen };
-                let range = IntRange { lo: prev_bdy, hi: bdy };
-                (presence, range)
-            })
-    }
-
-    /// 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(crate) fn is_beyond_boundaries<'tcx>(&self, ty: Ty<'tcx>, tcx: TyCtxt<'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`. `to_diagnostic_pat_range_bdy`
-            // converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `self.lo`
-            // otherwise.
-            let lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
-            matches!(lo, PatRangeBoundary::PosInfinity)
-                || matches!(self.hi, MaybeInfiniteInt::Finite(0))
-        }
-    }
-    /// Only used for displaying the range.
-    pub(super) fn to_diagnostic_pat<'tcx>(&self, ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Pat<'tcx> {
-        let kind = if matches!((self.lo, self.hi), (NegInfinity, PosInfinity)) {
-            PatKind::Wild
-        } else if self.is_singleton() {
-            let lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
-            let value = lo.as_finite().unwrap();
-            PatKind::Constant { value }
-        } else {
-            // We convert to an inclusive range for diagnostics.
-            let mut end = RangeEnd::Included;
-            let mut lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
-            if matches!(lo, PatRangeBoundary::PosInfinity) {
-                // The only reason to get `PosInfinity` here is the special case where
-                // `to_diagnostic_pat_range_bdy` found `{u,i}size::MAX+1`. So the range denotes the
-                // fictitious values after `{u,i}size::MAX` (see [`IntRange::split`] for why we do
-                // this). We show this to the user as `usize::MAX..` which is slightly incorrect but
-                // probably clear enough.
-                let c = ty.numeric_max_val(tcx).unwrap();
-                let value = mir::Const::from_ty_const(c, tcx);
-                lo = PatRangeBoundary::Finite(value);
-            }
-            let hi = if matches!(self.hi, MaybeInfiniteInt::Finite(0)) {
-                // The range encodes `..ty::MIN`, so we can't convert it to an inclusive range.
-                end = RangeEnd::Excluded;
-                self.hi
-            } else {
-                self.hi.minus_one()
-            };
-            let hi = hi.to_diagnostic_pat_range_bdy(ty, tcx);
-            PatKind::Range(Box::new(PatRange { lo, hi, end, ty }))
-        };
-
-        Pat { ty, span: DUMMY_SP, kind }
-    }
-}
-
-/// Note: this will render signed ranges incorrectly. To render properly, convert to a pattern
-/// first.
-impl fmt::Debug for IntRange {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        if let Finite(lo) = self.lo {
-            write!(f, "{lo}")?;
-        }
-        write!(f, "{}", RangeEnd::Excluded)?;
-        if let Finite(hi) = self.hi {
-            write!(f, "{hi}")?;
-        }
-        Ok(())
-    }
-}
-
-#[derive(Copy, Clone, Debug, PartialEq, Eq)]
-enum SliceKind {
-    /// Patterns of length `n` (`[x, y]`).
-    FixedLen(usize),
-    /// Patterns using the `..` notation (`[x, .., y]`).
-    /// Captures any array constructor of `length >= i + j`.
-    /// In the case where `array_len` is `Some(_)`,
-    /// this indicates that we only care about the first `i` and the last `j` values of the array,
-    /// and everything in between is a wildcard `_`.
-    VarLen(usize, usize),
-}
-
-impl SliceKind {
-    fn arity(self) -> usize {
-        match self {
-            FixedLen(length) => length,
-            VarLen(prefix, suffix) => prefix + suffix,
-        }
-    }
-
-    /// Whether this pattern includes patterns of length `other_len`.
-    fn covers_length(self, other_len: usize) -> bool {
-        match self {
-            FixedLen(len) => len == other_len,
-            VarLen(prefix, suffix) => prefix + suffix <= other_len,
-        }
-    }
-}
-
-/// A constructor for array and slice patterns.
-#[derive(Copy, Clone, Debug, PartialEq, Eq)]
-pub(super) struct Slice {
-    /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`.
-    array_len: Option<usize>,
-    /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`.
-    kind: SliceKind,
-}
-
-impl Slice {
-    fn new(array_len: Option<usize>, kind: SliceKind) -> Self {
-        let kind = match (array_len, kind) {
-            // If the middle `..` has length 0, we effectively have a fixed-length pattern.
-            (Some(len), VarLen(prefix, suffix)) if prefix + suffix == len => FixedLen(len),
-            (Some(len), VarLen(prefix, suffix)) if prefix + suffix > len => bug!(
-                "Slice pattern of length {} longer than its array length {len}",
-                prefix + suffix
-            ),
-            _ => kind,
-        };
-        Slice { array_len, kind }
-    }
-
-    fn arity(self) -> usize {
-        self.kind.arity()
-    }
-
-    /// See `Constructor::is_covered_by`
-    fn is_covered_by(self, other: Self) -> bool {
-        other.kind.covers_length(self.arity())
-    }
-
-    /// This computes constructor splitting for variable-length slices, as explained at the top of
-    /// the file.
-    ///
-    /// A slice pattern `[x, .., y]` behaves like the infinite or-pattern `[x, y] | [x, _, y] | [x,
-    /// _, _, y] | etc`. The corresponding value constructors are fixed-length array constructors of
-    /// corresponding lengths. We obviously can't list this infinitude of constructors.
-    /// Thankfully, it turns out that for each finite set of slice patterns, all sufficiently large
-    /// array lengths are equivalent.
-    ///
-    /// Let's look at an example, where we are trying to split the last pattern:
-    /// ```
-    /// # fn foo(x: &[bool]) {
-    /// match x {
-    ///     [true, true, ..] => {}
-    ///     [.., false, false] => {}
-    ///     [..] => {}
-    /// }
-    /// # }
-    /// ```
-    /// Here are the results of specialization for the first few lengths:
-    /// ```
-    /// # fn foo(x: &[bool]) { match x {
-    /// // length 0
-    /// [] => {}
-    /// // length 1
-    /// [_] => {}
-    /// // length 2
-    /// [true, true] => {}
-    /// [false, false] => {}
-    /// [_, _] => {}
-    /// // length 3
-    /// [true, true,  _    ] => {}
-    /// [_,    false, false] => {}
-    /// [_,    _,     _    ] => {}
-    /// // length 4
-    /// [true, true, _,     _    ] => {}
-    /// [_,    _,    false, false] => {}
-    /// [_,    _,    _,     _    ] => {}
-    /// // length 5
-    /// [true, true, _, _,     _    ] => {}
-    /// [_,    _,    _, false, false] => {}
-    /// [_,    _,    _, _,     _    ] => {}
-    /// # _ => {}
-    /// # }}
-    /// ```
-    ///
-    /// We see that above length 4, we are simply inserting columns full of wildcards in the middle.
-    /// This means that specialization and witness computation with slices of length `l >= 4` will
-    /// give equivalent results regardless of `l`. This applies to any set of slice patterns: there
-    /// will be a length `L` above which all lengths behave the same. This is exactly what we need
-    /// for constructor splitting.
-    ///
-    /// A variable-length slice pattern covers all lengths from its arity up to infinity. As we just
-    /// saw, we can split this in two: lengths below `L` are treated individually with a
-    /// fixed-length slice each; lengths above `L` are grouped into a single variable-length slice
-    /// constructor.
-    ///
-    /// For each variable-length slice pattern `p` with a prefix of length `plₚ` and suffix of
-    /// length `slₚ`, only the first `plₚ` and the last `slₚ` elements are examined. Therefore, as
-    /// long as `L` is positive (to avoid concerns about empty types), all elements after the
-    /// maximum prefix length and before the maximum suffix length are not examined by any
-    /// variable-length pattern, and therefore can be ignored. This gives us a way to compute `L`.
-    ///
-    /// Additionally, if fixed-length patterns exist, we must pick an `L` large enough to miss them,
-    /// so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))`.
-    /// `max_slice` below will be made to have this arity `L`.
-    ///
-    /// If `self` is fixed-length, it is returned as-is.
-    ///
-    /// Additionally, we track for each output slice whether it is covered by one of the column slices or not.
-    fn split(
-        self,
-        column_slices: impl Iterator<Item = Slice>,
-    ) -> impl Iterator<Item = (Presence, Slice)> {
-        // Range of lengths below `L`.
-        let smaller_lengths;
-        let arity = self.arity();
-        let mut max_slice = self.kind;
-        // Tracks the smallest variable-length slice we've seen. Any slice arity above it is
-        // therefore `Presence::Seen` in the column.
-        let mut min_var_len = usize::MAX;
-        // Tracks the fixed-length slices we've seen, to mark them as `Presence::Seen`.
-        let mut seen_fixed_lens = FxHashSet::default();
-        match &mut max_slice {
-            VarLen(max_prefix_len, max_suffix_len) => {
-                // A length larger than any fixed-length slice encountered.
-                // We start at 1 in case the subtype is empty because in that case the zero-length
-                // slice must be treated separately from the rest.
-                let mut fixed_len_upper_bound = 1;
-                // We grow `max_slice` to be larger than all slices encountered, as described above.
-                // `L` is `max_slice.arity()`. For diagnostics, we keep the prefix and suffix
-                // lengths separate.
-                for slice in column_slices {
-                    match slice.kind {
-                        FixedLen(len) => {
-                            fixed_len_upper_bound = cmp::max(fixed_len_upper_bound, len + 1);
-                            seen_fixed_lens.insert(len);
-                        }
-                        VarLen(prefix, suffix) => {
-                            *max_prefix_len = cmp::max(*max_prefix_len, prefix);
-                            *max_suffix_len = cmp::max(*max_suffix_len, suffix);
-                            min_var_len = cmp::min(min_var_len, prefix + suffix);
-                        }
-                    }
-                }
-                // If `fixed_len_upper_bound >= L`, we set `L` to `fixed_len_upper_bound`.
-                if let Some(delta) =
-                    fixed_len_upper_bound.checked_sub(*max_prefix_len + *max_suffix_len)
-                {
-                    *max_prefix_len += delta
-                }
-
-                // We cap the arity of `max_slice` at the array size.
-                match self.array_len {
-                    Some(len) if max_slice.arity() >= len => max_slice = FixedLen(len),
-                    _ => {}
-                }
-
-                smaller_lengths = match self.array_len {
-                    // The only admissible fixed-length slice is one of the array size. Whether `max_slice`
-                    // is fixed-length or variable-length, it will be the only relevant slice to output
-                    // here.
-                    Some(_) => 0..0, // empty range
-                    // We need to cover all arities in the range `(arity..infinity)`. We split that
-                    // range into two: lengths smaller than `max_slice.arity()` are treated
-                    // independently as fixed-lengths slices, and lengths above are captured by
-                    // `max_slice`.
-                    None => self.arity()..max_slice.arity(),
-                };
-            }
-            FixedLen(_) => {
-                // No need to split here. We only track presence.
-                for slice in column_slices {
-                    match slice.kind {
-                        FixedLen(len) => {
-                            if len == arity {
-                                seen_fixed_lens.insert(len);
-                            }
-                        }
-                        VarLen(prefix, suffix) => {
-                            min_var_len = cmp::min(min_var_len, prefix + suffix);
-                        }
-                    }
-                }
-                smaller_lengths = 0..0;
-            }
-        };
-
-        smaller_lengths.map(FixedLen).chain(once(max_slice)).map(move |kind| {
-            let arity = kind.arity();
-            let seen = if min_var_len <= arity || seen_fixed_lens.contains(&arity) {
-                Presence::Seen
-            } else {
-                Presence::Unseen
-            };
-            (seen, Slice::new(self.array_len, kind))
-        })
-    }
-}
-
-/// A globally unique id to distinguish `Opaque` patterns.
-#[derive(Clone, Debug, PartialEq, Eq)]
-pub(super) struct OpaqueId(u32);
-
-impl OpaqueId {
-    fn new() -> Self {
-        use std::sync::atomic::{AtomicU32, Ordering};
-        static OPAQUE_ID: AtomicU32 = AtomicU32::new(0);
-        OpaqueId(OPAQUE_ID.fetch_add(1, Ordering::SeqCst))
-    }
-}
-
-/// A value can be decomposed into a constructor applied to some fields. This struct represents
-/// the constructor. See also `Fields`.
-///
-/// `pat_constructor` retrieves the constructor corresponding to a pattern.
-/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
-/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
-/// `Fields`.
-#[derive(Clone, Debug, PartialEq)]
-pub(super) enum Constructor<'tcx> {
-    /// The constructor for patterns that have a single constructor, like tuples, struct patterns,
-    /// and references. Fixed-length arrays are treated separately with `Slice`.
-    Single,
-    /// Enum variants.
-    Variant(VariantIdx),
-    /// Booleans
-    Bool(bool),
-    /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
-    IntRange(IntRange),
-    /// Ranges of floating-point literal values (`2.0..=5.2`).
-    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(mir::Const<'tcx>),
-    /// Array and slice patterns.
-    Slice(Slice),
-    /// 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.
-    /// Carries an id that must be unique within a match. We need this to ensure the invariants of
-    /// [`SplitConstructorSet`].
-    Opaque(OpaqueId),
-    /// Or-pattern.
-    Or,
-    /// Wildcard pattern.
-    Wildcard,
-    /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used
-    /// for those types for which we cannot list constructors explicitly, like `f64` and `str`.
-    NonExhaustive,
-    /// Fake extra constructor for variants that should not be mentioned in diagnostics.
-    /// We use this for variants behind an unstable gate as well as
-    /// `#[doc(hidden)]` ones.
-    Hidden,
-    /// Fake extra constructor for constructors that are not seen in the matrix, as explained at the
-    /// top of the file.
-    Missing,
-}
-
-impl<'tcx> Constructor<'tcx> {
-    pub(super) fn is_non_exhaustive(&self) -> bool {
-        matches!(self, NonExhaustive)
-    }
-
-    pub(super) fn as_variant(&self) -> Option<VariantIdx> {
-        match self {
-            Variant(i) => Some(*i),
-            _ => None,
-        }
-    }
-    fn as_bool(&self) -> Option<bool> {
-        match self {
-            Bool(b) => Some(*b),
-            _ => None,
-        }
-    }
-    pub(super) fn as_int_range(&self) -> Option<&IntRange> {
-        match self {
-            IntRange(range) => Some(range),
-            _ => None,
-        }
-    }
-    fn as_slice(&self) -> Option<Slice> {
-        match self {
-            Slice(slice) => Some(*slice),
-            _ => None,
-        }
-    }
-
-    fn variant_index_for_adt(&self, adt: ty::AdtDef<'tcx>) -> VariantIdx {
-        match *self {
-            Variant(idx) => idx,
-            Single => {
-                assert!(!adt.is_enum());
-                FIRST_VARIANT
-            }
-            _ => bug!("bad constructor {:?} for adt {:?}", self, adt),
-        }
-    }
-
-    /// The number of fields for this constructor. This must be kept in sync with
-    /// `Fields::wildcards`.
-    pub(super) fn arity(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> usize {
-        match self {
-            Single | Variant(_) => match pcx.ty.kind() {
-                ty::Tuple(fs) => fs.len(),
-                ty::Ref(..) => 1,
-                ty::Adt(adt, ..) => {
-                    if adt.is_box() {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        1
-                    } else {
-                        let variant = &adt.variant(self.variant_index_for_adt(*adt));
-                        Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant).count()
-                    }
-                }
-                _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx.ty),
-            },
-            Slice(slice) => slice.arity(),
-            Bool(..)
-            | IntRange(..)
-            | F32Range(..)
-            | F64Range(..)
-            | Str(..)
-            | Opaque(..)
-            | NonExhaustive
-            | Hidden
-            | Missing { .. }
-            | Wildcard => 0,
-            Or => bug!("The `Or` constructor doesn't have a fixed arity"),
-        }
-    }
-
-    /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
-    /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
-    /// this checks for inclusion.
-    // We inline because this has a single call site in `Matrix::specialize_constructor`.
-    #[inline]
-    pub(super) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool {
-        match (self, other) {
-            (Wildcard, _) => {
-                span_bug!(
-                    pcx.cx.scrut_span,
-                    "Constructor splitting should not have returned `Wildcard`"
-                )
-            }
-            // Wildcards cover anything
-            (_, Wildcard) => true,
-            // Only a wildcard pattern can match these special constructors.
-            (Missing { .. } | NonExhaustive | Hidden, _) => false,
-
-            (Single, Single) => true,
-            (Variant(self_id), Variant(other_id)) => self_id == other_id,
-            (Bool(self_b), Bool(other_b)) => self_b == other_b,
-
-            (IntRange(self_range), IntRange(other_range)) => self_range.is_subrange(other_range),
-            (F32Range(self_from, self_to, self_end), F32Range(other_from, other_to, other_end)) => {
-                self_from.ge(other_from)
-                    && match self_to.partial_cmp(other_to) {
-                        Some(Ordering::Less) => true,
-                        Some(Ordering::Equal) => other_end == self_end,
-                        _ => false,
-                    }
-            }
-            (F64Range(self_from, self_to, self_end), F64Range(other_from, other_to, other_end)) => {
-                self_from.ge(other_from)
-                    && match self_to.partial_cmp(other_to) {
-                        Some(Ordering::Less) => true,
-                        Some(Ordering::Equal) => other_end == self_end,
-                        _ => false,
-                    }
-            }
-            (Str(self_val), Str(other_val)) => {
-                // FIXME Once valtrees are available we can directly use the bytes
-                // in the `Str` variant of the valtree for the comparison here.
-                self_val == other_val
-            }
-            (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
-
-            // Opaque constructors don't interact with anything unless they come from the
-            // syntactically identical pattern.
-            (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
-            ),
-        }
-    }
-}
-
-#[derive(Debug, Clone, Copy)]
-pub(super) enum VariantVisibility {
-    /// Variant that doesn't fit the other cases, i.e. most variants.
-    Visible,
-    /// Variant behind an unstable gate or with the `#[doc(hidden)]` attribute. It will not be
-    /// mentioned in diagnostics unless the user mentioned it first.
-    Hidden,
-    /// Variant that matches no value. E.g. `Some::<Option<!>>` if the `exhaustive_patterns` feature
-    /// is enabled. Like `Hidden`, it will not be mentioned in diagnostics unless the user mentioned
-    /// it first.
-    Empty,
-}
-
-/// Describes the set of all constructors for a type. For details, in particular about the emptiness
-/// of constructors, see the top of the file.
-///
-/// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the
-/// `exhaustive_patterns` feature.
-#[derive(Debug)]
-pub(super) enum ConstructorSet {
-    /// The type has a single constructor, e.g. `&T` or a struct. `empty` tracks whether the
-    /// constructor is empty.
-    Single { 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 },
-    /// Booleans.
-    Bool,
-    /// The type is spanned by integer values. The range or ranges give the set of allowed values.
-    /// The second range is only useful for `char`.
-    Integers { range_1: IntRange, range_2: Option<IntRange> },
-    /// The type is matched by slices. `array_len` is the compile-time length of the array, if
-    /// known. If `subtype_is_empty`, all constructors are empty except possibly the zero-length
-    /// slice `[]`.
-    Slice { array_len: Option<usize>, subtype_is_empty: bool },
-    /// The constructors cannot be listed, and the type cannot be matched exhaustively. E.g. `str`,
-    /// floats.
-    Unlistable,
-    /// The type has no constructors (not even empty ones). This is `!` and empty enums.
-    NoConstructors,
-}
-
-/// Describes the result of analyzing the constructors in a column of a match.
-///
-/// `present` is morally the set of constructors present in the column, and `missing` is the set of
-/// constructors that exist in the type but are not present in the column.
-///
-/// More formally, if we discard wildcards from the column, this respects the following constraints:
-/// 1. the union of `present`, `missing` and `missing_empty` covers all the constructors of the type
-/// 2. each constructor in `present` is covered by something in the column
-/// 3. no constructor in `missing` or `missing_empty` is covered by anything in the column
-/// 4. each constructor in the column is equal to the union of one or more constructors in `present`
-/// 5. `missing` does not contain empty constructors (see discussion about emptiness at the top of
-///    the file);
-/// 6. `missing_empty` contains only empty constructors
-/// 7. constructors in `present`, `missing` and `missing_empty` are split for the column; in other
-///    words, they are either fully included in or fully disjoint from each constructor in the
-///    column. In yet other words, there are no non-trivial intersections like between `0..10` and
-///    `5..15`.
-///
-/// We must be particularly careful with weird constructors like `Opaque`: they're not formally part
-/// 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(super) struct SplitConstructorSet<'tcx> {
-    pub(super) present: SmallVec<[Constructor<'tcx>; 1]>,
-    pub(super) missing: Vec<Constructor<'tcx>>,
-    pub(super) missing_empty: Vec<Constructor<'tcx>>,
-}
-
-impl ConstructorSet {
-    /// Creates a set that represents all the constructors of `ty`.
-    ///
-    /// See at the top of the file for considerations of emptiness.
-    #[instrument(level = "debug", skip(cx), ret)]
-    pub(super) fn for_ty<'p, 'tcx>(cx: &MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
-        let make_range = |start, end| {
-            IntRange::from_range(
-                MaybeInfiniteInt::new_finite(cx.tcx, ty, start),
-                MaybeInfiniteInt::new_finite(cx.tcx, ty, end),
-                RangeEnd::Included,
-            )
-        };
-        // This determines the set of all possible constructors for the type `ty`. For numbers,
-        // arrays and slices we use ranges and variable-length slices when appropriate.
-        match ty.kind() {
-            ty::Bool => Self::Bool,
-            ty::Char => {
-                // The valid Unicode Scalar Value ranges.
-                Self::Integers {
-                    range_1: make_range('\u{0000}' as u128, '\u{D7FF}' as u128),
-                    range_2: Some(make_range('\u{E000}' as u128, '\u{10FFFF}' as u128)),
-                }
-            }
-            &ty::Int(ity) => {
-                let range = if ty.is_ptr_sized_integral() {
-                    // The min/max values of `isize` are not allowed to be observed.
-                    IntRange { lo: NegInfinity, hi: PosInfinity }
-                } else {
-                    let bits = Integer::from_int_ty(&cx.tcx, ity).size().bits() as u128;
-                    let min = 1u128 << (bits - 1);
-                    let max = min - 1;
-                    make_range(min, max)
-                };
-                Self::Integers { range_1: range, range_2: None }
-            }
-            &ty::Uint(uty) => {
-                let range = if ty.is_ptr_sized_integral() {
-                    // The max value of `usize` is not allowed to be observed.
-                    let lo = MaybeInfiniteInt::new_finite(cx.tcx, ty, 0);
-                    IntRange { lo, hi: PosInfinity }
-                } else {
-                    let size = Integer::from_uint_ty(&cx.tcx, uty).size();
-                    let max = size.truncate(u128::MAX);
-                    make_range(0, max)
-                };
-                Self::Integers { range_1: range, range_2: None }
-            }
-            ty::Slice(sub_ty) => {
-                Self::Slice { array_len: None, subtype_is_empty: cx.is_uninhabited(*sub_ty) }
-            }
-            ty::Array(sub_ty, len) => {
-                // We treat arrays of a constant but unknown length like slices.
-                Self::Slice {
-                    array_len: len.try_eval_target_usize(cx.tcx, cx.param_env).map(|l| l as usize),
-                    subtype_is_empty: cx.is_uninhabited(*sub_ty),
-                }
-            }
-            ty::Adt(def, args) if def.is_enum() => {
-                let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(ty);
-                if def.variants().is_empty() && !is_declared_nonexhaustive {
-                    Self::NoConstructors
-                } else {
-                    let mut variants =
-                        IndexVec::from_elem(VariantVisibility::Visible, def.variants());
-                    for (idx, v) in def.variants().iter_enumerated() {
-                        let variant_def_id = def.variant(idx).def_id;
-                        // Visibly uninhabited variants.
-                        let is_inhabited = v
-                            .inhabited_predicate(cx.tcx, *def)
-                            .instantiate(cx.tcx, args)
-                            .apply(cx.tcx, cx.param_env, cx.module);
-                        // Variants that depend on a disabled unstable feature.
-                        let is_unstable = matches!(
-                            cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None),
-                            EvalResult::Deny { .. }
-                        );
-                        // Foreign `#[doc(hidden)]` variants.
-                        let is_doc_hidden =
-                            cx.tcx.is_doc_hidden(variant_def_id) && !variant_def_id.is_local();
-                        let visibility = if !is_inhabited {
-                            // FIXME: handle empty+hidden
-                            VariantVisibility::Empty
-                        } else if is_unstable || is_doc_hidden {
-                            VariantVisibility::Hidden
-                        } else {
-                            VariantVisibility::Visible
-                        };
-                        variants[idx] = visibility;
-                    }
-
-                    Self::Variants { variants, non_exhaustive: is_declared_nonexhaustive }
-                }
-            }
-            ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => {
-                Self::Single { empty: cx.is_uninhabited(ty) }
-            }
-            ty::Never => Self::NoConstructors,
-            // This type is one for which we cannot list constructors, like `str` or `f64`.
-            // FIXME(Nadrieril): which of these are actually allowed?
-            ty::Float(_)
-            | ty::Str
-            | ty::Foreign(_)
-            | ty::RawPtr(_)
-            | ty::FnDef(_, _)
-            | ty::FnPtr(_)
-            | ty::Dynamic(_, _, _)
-            | ty::Closure(_, _)
-            | ty::Coroutine(_, _, _)
-            | ty::Alias(_, _)
-            | ty::Param(_)
-            | ty::Error(_) => Self::Unlistable,
-            ty::CoroutineWitness(_, _) | ty::Bound(_, _) | ty::Placeholder(_) | ty::Infer(_) => {
-                bug!("Encountered unexpected type in `ConstructorSet::for_ty`: {ty:?}")
-            }
-        }
-    }
-
-    /// 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(super) fn split<'a, 'tcx>(
-        &self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
-    ) -> SplitConstructorSet<'tcx>
-    where
-        'tcx: 'a,
-    {
-        let mut present: SmallVec<[_; 1]> = SmallVec::new();
-        // Empty constructors found missing.
-        let mut missing_empty = Vec::new();
-        // Nonempty constructors found missing.
-        let mut missing = Vec::new();
-        // Constructors in `ctors`, except wildcards and opaques.
-        let mut seen = Vec::new();
-        for ctor in ctors.cloned() {
-            match ctor {
-                Opaque(..) => present.push(ctor),
-                Wildcard => {} // discard wildcards
-                _ => seen.push(ctor),
-            }
-        }
-
-        match self {
-            ConstructorSet::Single { empty } => {
-                if !seen.is_empty() {
-                    present.push(Single);
-                } else if *empty {
-                    missing_empty.push(Single);
-                } else {
-                    missing.push(Single);
-                }
-            }
-            ConstructorSet::Variants { variants, non_exhaustive } => {
-                let seen_set: FxHashSet<_> = seen.iter().map(|c| c.as_variant().unwrap()).collect();
-                let mut skipped_a_hidden_variant = false;
-
-                for (idx, visibility) in variants.iter_enumerated() {
-                    let ctor = Variant(idx);
-                    if seen_set.contains(&idx) {
-                        present.push(ctor);
-                    } else {
-                        // We only put visible variants directly into `missing`.
-                        match visibility {
-                            VariantVisibility::Visible => missing.push(ctor),
-                            VariantVisibility::Hidden => skipped_a_hidden_variant = true,
-                            VariantVisibility::Empty => missing_empty.push(ctor),
-                        }
-                    }
-                }
-
-                if skipped_a_hidden_variant {
-                    missing.push(Hidden);
-                }
-                if *non_exhaustive {
-                    missing.push(NonExhaustive);
-                }
-            }
-            ConstructorSet::Bool => {
-                let mut seen_false = false;
-                let mut seen_true = false;
-                for b in seen.iter().map(|ctor| ctor.as_bool().unwrap()) {
-                    if b {
-                        seen_true = true;
-                    } else {
-                        seen_false = true;
-                    }
-                }
-                if seen_false {
-                    present.push(Bool(false));
-                } else {
-                    missing.push(Bool(false));
-                }
-                if seen_true {
-                    present.push(Bool(true));
-                } else {
-                    missing.push(Bool(true));
-                }
-            }
-            ConstructorSet::Integers { range_1, range_2 } => {
-                let seen_ranges: Vec<_> =
-                    seen.iter().map(|ctor| ctor.as_int_range().unwrap().clone()).collect();
-                for (seen, splitted_range) in range_1.split(seen_ranges.iter().cloned()) {
-                    match seen {
-                        Presence::Unseen => missing.push(IntRange(splitted_range)),
-                        Presence::Seen => present.push(IntRange(splitted_range)),
-                    }
-                }
-                if let Some(range_2) = range_2 {
-                    for (seen, splitted_range) in range_2.split(seen_ranges.into_iter()) {
-                        match seen {
-                            Presence::Unseen => missing.push(IntRange(splitted_range)),
-                            Presence::Seen => present.push(IntRange(splitted_range)),
-                        }
-                    }
-                }
-            }
-            ConstructorSet::Slice { array_len, subtype_is_empty } => {
-                let seen_slices = seen.iter().map(|c| c.as_slice().unwrap());
-                let base_slice = Slice::new(*array_len, VarLen(0, 0));
-                for (seen, splitted_slice) in base_slice.split(seen_slices) {
-                    let ctor = Slice(splitted_slice);
-                    match seen {
-                        Presence::Seen => present.push(ctor),
-                        Presence::Unseen => {
-                            if *subtype_is_empty && splitted_slice.arity() != 0 {
-                                // We have subpatterns of an empty type, so the constructor is
-                                // empty.
-                                missing_empty.push(ctor);
-                            } else {
-                                missing.push(ctor);
-                            }
-                        }
-                    }
-                }
-            }
-            ConstructorSet::Unlistable => {
-                // Since we can't list constructors, we take the ones in the column. This might list
-                // some constructors several times but there's not much we can do.
-                present.extend(seen);
-                missing.push(NonExhaustive);
-            }
-            ConstructorSet::NoConstructors => {
-                // In a `MaybeInvalid` place even an empty pattern may be reachable. We therefore
-                // add a dummy empty constructor here, which will be ignored if the place is
-                // `ValidOnly`.
-                missing_empty.push(NonExhaustive);
-            }
-        }
-
-        // 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
-            && !(pcx.is_top_level && matches!(self, Self::NoConstructors))
-        {
-            // Treat all missing constructors as nonempty.
-            missing.extend(missing_empty.drain(..));
-        }
-
-        SplitConstructorSet { present, missing, missing_empty }
-    }
-}
-
-/// A value can be decomposed into a constructor applied to some fields. This struct represents
-/// those fields, generalized to allow patterns in each field. See also `Constructor`.
-///
-/// This is constructed for a constructor using [`Fields::wildcards()`]. The idea is that
-/// [`Fields::wildcards()`] constructs a list of fields where all entries are wildcards, and then
-/// given a pattern we fill some of the fields with its subpatterns.
-/// In the following example `Fields::wildcards` returns `[_, _, _, _]`. Then in
-/// `extract_pattern_arguments` we fill some of the entries, and the result is
-/// `[Some(0), _, _, _]`.
-/// ```compile_fail,E0004
-/// # fn foo() -> [Option<u8>; 4] { [None; 4] }
-/// let x: [Option<u8>; 4] = foo();
-/// match x {
-///     [Some(0), ..] => {}
-/// }
-/// ```
-///
-/// Note that the number of fields of a constructor may not match the fields declared in the
-/// original struct/variant. 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`. For that reason, when you have a `FieldIdx` you must use
-/// `index_with_declared_idx`.
-#[derive(Debug, Clone, Copy)]
-pub(super) struct Fields<'p, 'tcx> {
-    fields: &'p [DeconstructedPat<'p, 'tcx>],
-}
-
-impl<'p, 'tcx> Fields<'p, 'tcx> {
-    fn empty() -> Self {
-        Fields { fields: &[] }
-    }
-
-    fn singleton(cx: &MatchCheckCtxt<'p, 'tcx>, field: DeconstructedPat<'p, 'tcx>) -> Self {
-        let field: &_ = cx.pattern_arena.alloc(field);
-        Fields { fields: std::slice::from_ref(field) }
-    }
-
-    pub(super) fn from_iter(
-        cx: &MatchCheckCtxt<'p, 'tcx>,
-        fields: impl IntoIterator<Item = DeconstructedPat<'p, 'tcx>>,
-    ) -> Self {
-        let fields: &[_] = cx.pattern_arena.alloc_from_iter(fields);
-        Fields { fields }
-    }
-
-    fn wildcards_from_tys(
-        cx: &MatchCheckCtxt<'p, 'tcx>,
-        tys: impl IntoIterator<Item = Ty<'tcx>>,
-    ) -> Self {
-        Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, DUMMY_SP)))
-    }
-
-    // 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.
-    fn list_variant_nonhidden_fields<'a>(
-        cx: &'a MatchCheckCtxt<'p, 'tcx>,
-        ty: Ty<'tcx>,
-        variant: &'a VariantDef,
-    ) -> impl Iterator<Item = (FieldIdx, Ty<'tcx>)> + Captures<'a> + Captures<'p> {
-        let ty::Adt(adt, args) = ty.kind() else { bug!() };
-        // Whether we must not match the fields of this variant exhaustively.
-        let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !adt.did().is_local();
-
-        variant.fields.iter().enumerate().filter_map(move |(i, field)| {
-            let ty = field.ty(cx.tcx, args);
-            // `field.ty()` doesn't normalize after substituting.
-            let ty = cx.tcx.normalize_erasing_regions(cx.param_env, ty);
-            let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx);
-            let is_uninhabited = cx.tcx.features().exhaustive_patterns && cx.is_uninhabited(ty);
-
-            if is_uninhabited && (!is_visible || is_non_exhaustive) {
-                None
-            } else {
-                Some((FieldIdx::new(i), ty))
-            }
-        })
-    }
-
-    /// Creates a new list of wildcard fields for a given constructor. The result must have a
-    /// length of `constructor.arity()`.
-    #[instrument(level = "trace")]
-    pub(super) fn wildcards(pcx: &PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self {
-        let ret = match constructor {
-            Single | Variant(_) => match pcx.ty.kind() {
-                ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter()),
-                ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty)),
-                ty::Adt(adt, args) => {
-                    if adt.is_box() {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0)))
-                    } else {
-                        let variant = &adt.variant(constructor.variant_index_for_adt(*adt));
-                        let tys = Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant)
-                            .map(|(_, ty)| ty);
-                        Fields::wildcards_from_tys(pcx.cx, tys)
-                    }
-                }
-                _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx),
-            },
-            Slice(slice) => match *pcx.ty.kind() {
-                ty::Slice(ty) | ty::Array(ty, _) => {
-                    let arity = slice.arity();
-                    Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty))
-                }
-                _ => bug!("bad slice pattern {:?} {:?}", constructor, pcx),
-            },
-            Bool(..)
-            | IntRange(..)
-            | F32Range(..)
-            | F64Range(..)
-            | Str(..)
-            | Opaque(..)
-            | NonExhaustive
-            | Hidden
-            | Missing { .. }
-            | Wildcard => Fields::empty(),
-            Or => {
-                bug!("called `Fields::wildcards` on an `Or` ctor")
-            }
-        };
-        debug!(?ret);
-        ret
-    }
-
-    /// Returns the list of patterns.
-    pub(super) fn iter_patterns<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
-        self.fields.iter()
-    }
-}
-
-/// Values and patterns can be represented as a constructor applied to some fields. This represents
-/// a pattern in this form.
-/// This also uses interior mutability to keep track of whether the pattern has been found reachable
-/// during analysis. For this reason they cannot be cloned.
-/// A `DeconstructedPat` will almost always come from user input; the only exception are some
-/// `Wildcard`s introduced during specialization.
-pub(crate) struct DeconstructedPat<'p, 'tcx> {
-    ctor: Constructor<'tcx>,
-    fields: Fields<'p, 'tcx>,
-    ty: Ty<'tcx>,
-    span: Span,
-    /// Whether removing this arm would change the behavior of the match expression.
-    useful: Cell<bool>,
-}
-
-impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
-    pub(super) fn wildcard(ty: Ty<'tcx>, span: Span) -> Self {
-        Self::new(Wildcard, Fields::empty(), ty, span)
-    }
-
-    pub(super) fn new(
-        ctor: Constructor<'tcx>,
-        fields: Fields<'p, 'tcx>,
-        ty: Ty<'tcx>,
-        span: Span,
-    ) -> Self {
-        DeconstructedPat { ctor, fields, ty, span, useful: Cell::new(false) }
-    }
-
-    /// Note: the input patterns must have been lowered through
-    /// `super::check_match::MatchVisitor::lower_pattern`.
-    pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self {
-        let mkpat = |pat| DeconstructedPat::from_pat(cx, pat);
-        let ctor;
-        let fields;
-        match &pat.kind {
-            PatKind::AscribeUserType { subpattern, .. }
-            | PatKind::InlineConstant { subpattern, .. } => return mkpat(subpattern),
-            PatKind::Binding { subpattern: Some(subpat), .. } => return mkpat(subpat),
-            PatKind::Binding { subpattern: None, .. } | PatKind::Wild => {
-                ctor = Wildcard;
-                fields = Fields::empty();
-            }
-            PatKind::Deref { subpattern } => {
-                ctor = Single;
-                fields = Fields::singleton(cx, mkpat(subpattern));
-            }
-            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
-                match pat.ty.kind() {
-                    ty::Tuple(fs) => {
-                        ctor = Single;
-                        let mut wilds: SmallVec<[_; 2]> =
-                            fs.iter().map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
-                        for pat in subpatterns {
-                            wilds[pat.field.index()] = mkpat(&pat.pattern);
-                        }
-                        fields = Fields::from_iter(cx, wilds);
-                    }
-                    ty::Adt(adt, args) if adt.is_box() => {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_,
-                        // _)` or a box pattern. As a hack to avoid an ICE with the former, we
-                        // ignore other fields than the first one. This will trigger an error later
-                        // anyway.
-                        // See https://github.com/rust-lang/rust/issues/82772 ,
-                        // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977
-                        // The problem is that we can't know from the type whether we'll match
-                        // normally or through box-patterns. We'll have to figure out a proper
-                        // solution when we introduce generalized deref patterns. Also need to
-                        // prevent mixing of those two options.
-                        let pattern = subpatterns.into_iter().find(|pat| pat.field.index() == 0);
-                        let pat = if let Some(pat) = pattern {
-                            mkpat(&pat.pattern)
-                        } else {
-                            DeconstructedPat::wildcard(args.type_at(0), pat.span)
-                        };
-                        ctor = Single;
-                        fields = Fields::singleton(cx, pat);
-                    }
-                    ty::Adt(adt, _) => {
-                        ctor = match pat.kind {
-                            PatKind::Leaf { .. } => Single,
-                            PatKind::Variant { variant_index, .. } => Variant(variant_index),
-                            _ => bug!(),
-                        };
-                        let variant = &adt.variant(ctor.variant_index_for_adt(*adt));
-                        // For each field in the variant, we store the relevant index into `self.fields` if any.
-                        let mut field_id_to_id: Vec<Option<usize>> =
-                            (0..variant.fields.len()).map(|_| None).collect();
-                        let tys = Fields::list_variant_nonhidden_fields(cx, pat.ty, variant)
-                            .enumerate()
-                            .map(|(i, (field, ty))| {
-                                field_id_to_id[field.index()] = Some(i);
-                                ty
-                            });
-                        let mut wilds: SmallVec<[_; 2]> =
-                            tys.map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
-                        for pat in subpatterns {
-                            if let Some(i) = field_id_to_id[pat.field.index()] {
-                                wilds[i] = mkpat(&pat.pattern);
-                            }
-                        }
-                        fields = Fields::from_iter(cx, wilds);
-                    }
-                    _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, pat.ty),
-                }
-            }
-            PatKind::Constant { value } => {
-                match pat.ty.kind() {
-                    ty::Bool => {
-                        ctor = match value.try_eval_bool(cx.tcx, cx.param_env) {
-                            Some(b) => Bool(b),
-                            None => Opaque(OpaqueId::new()),
-                        };
-                        fields = Fields::empty();
-                    }
-                    ty::Char | ty::Int(_) | ty::Uint(_) => {
-                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
-                            Some(bits) => IntRange(IntRange::from_bits(cx.tcx, pat.ty, bits)),
-                            None => Opaque(OpaqueId::new()),
-                        };
-                        fields = Fields::empty();
-                    }
-                    ty::Float(ty::FloatTy::F32) => {
-                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
-                            Some(bits) => {
-                                use rustc_apfloat::Float;
-                                let value = rustc_apfloat::ieee::Single::from_bits(bits);
-                                F32Range(value, value, RangeEnd::Included)
-                            }
-                            None => Opaque(OpaqueId::new()),
-                        };
-                        fields = Fields::empty();
-                    }
-                    ty::Float(ty::FloatTy::F64) => {
-                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
-                            Some(bits) => {
-                                use rustc_apfloat::Float;
-                                let value = rustc_apfloat::ieee::Double::from_bits(bits);
-                                F64Range(value, value, RangeEnd::Included)
-                            }
-                            None => Opaque(OpaqueId::new()),
-                        };
-                        fields = Fields::empty();
-                    }
-                    ty::Ref(_, t, _) if t.is_str() => {
-                        // We want a `&str` constant to behave like a `Deref` pattern, to be compatible
-                        // with other `Deref` patterns. This could have been done in `const_to_pat`,
-                        // but that causes issues with the rest of the matching code.
-                        // So here, the constructor for a `"foo"` pattern is `&` (represented by
-                        // `Single`), and has one field. That field has constructor `Str(value)` and no
-                        // fields.
-                        // Note: `t` is `str`, not `&str`.
-                        let subpattern =
-                            DeconstructedPat::new(Str(*value), Fields::empty(), *t, pat.span);
-                        ctor = Single;
-                        fields = Fields::singleton(cx, subpattern)
-                    }
-                    // All constants that can be structurally matched have already been expanded
-                    // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are
-                    // opaque.
-                    _ => {
-                        ctor = Opaque(OpaqueId::new());
-                        fields = Fields::empty();
-                    }
-                }
-            }
-            PatKind::Range(box PatRange { lo, hi, end, .. }) => {
-                let ty = pat.ty;
-                ctor = match ty.kind() {
-                    ty::Char | ty::Int(_) | ty::Uint(_) => {
-                        let lo =
-                            MaybeInfiniteInt::from_pat_range_bdy(*lo, ty, cx.tcx, cx.param_env);
-                        let hi =
-                            MaybeInfiniteInt::from_pat_range_bdy(*hi, ty, cx.tcx, cx.param_env);
-                        IntRange(IntRange::from_range(lo, hi, *end))
-                    }
-                    ty::Float(fty) => {
-                        use rustc_apfloat::Float;
-                        let lo = lo.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
-                        let hi = hi.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
-                        match fty {
-                            ty::FloatTy::F32 => {
-                                use rustc_apfloat::ieee::Single;
-                                let lo = lo.map(Single::from_bits).unwrap_or(-Single::INFINITY);
-                                let hi = hi.map(Single::from_bits).unwrap_or(Single::INFINITY);
-                                F32Range(lo, hi, *end)
-                            }
-                            ty::FloatTy::F64 => {
-                                use rustc_apfloat::ieee::Double;
-                                let lo = lo.map(Double::from_bits).unwrap_or(-Double::INFINITY);
-                                let hi = hi.map(Double::from_bits).unwrap_or(Double::INFINITY);
-                                F64Range(lo, hi, *end)
-                            }
-                        }
-                    }
-                    _ => bug!("invalid type for range pattern: {}", ty),
-                };
-                fields = Fields::empty();
-            }
-            PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => {
-                let array_len = match pat.ty.kind() {
-                    ty::Array(_, length) => {
-                        Some(length.eval_target_usize(cx.tcx, cx.param_env) as usize)
-                    }
-                    ty::Slice(_) => None,
-                    _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty),
-                };
-                let kind = if slice.is_some() {
-                    VarLen(prefix.len(), suffix.len())
-                } else {
-                    FixedLen(prefix.len() + suffix.len())
-                };
-                ctor = Slice(Slice::new(array_len, kind));
-                fields =
-                    Fields::from_iter(cx, prefix.iter().chain(suffix.iter()).map(|p| mkpat(&*p)));
-            }
-            PatKind::Or { .. } => {
-                ctor = Or;
-                let pats = expand_or_pat(pat);
-                fields = Fields::from_iter(cx, pats.into_iter().map(mkpat));
-            }
-            PatKind::Never => {
-                // FIXME(never_patterns): handle `!` in exhaustiveness. This is a sane default
-                // in the meantime.
-                ctor = Wildcard;
-                fields = Fields::empty();
-            }
-            PatKind::Error(_) => {
-                ctor = Opaque(OpaqueId::new());
-                fields = Fields::empty();
-            }
-        }
-        DeconstructedPat::new(ctor, fields, pat.ty, pat.span)
-    }
-
-    pub(super) fn is_or_pat(&self) -> bool {
-        matches!(self.ctor, Or)
-    }
-    /// Expand this (possibly-nested) or-pattern into its alternatives.
-    pub(super) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> {
-        if self.is_or_pat() {
-            self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect()
-        } else {
-            smallvec![self]
-        }
-    }
-
-    pub(super) fn ctor(&self) -> &Constructor<'tcx> {
-        &self.ctor
-    }
-    pub(super) fn ty(&self) -> Ty<'tcx> {
-        self.ty
-    }
-    pub(super) fn span(&self) -> Span {
-        self.span
-    }
-
-    pub(super) fn iter_fields<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
-        self.fields.iter_patterns()
-    }
-
-    /// Specialize this pattern with a constructor.
-    /// `other_ctor` can be different from `self.ctor`, but must be covered by it.
-    pub(super) fn specialize<'a>(
-        &'a self,
-        pcx: &PatCtxt<'_, 'p, 'tcx>,
-        other_ctor: &Constructor<'tcx>,
-    ) -> SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]> {
-        match (&self.ctor, other_ctor) {
-            (Wildcard, _) => {
-                // We return a wildcard for each field of `other_ctor`.
-                Fields::wildcards(pcx, other_ctor).iter_patterns().collect()
-            }
-            (Slice(self_slice), Slice(other_slice))
-                if self_slice.arity() != other_slice.arity() =>
-            {
-                // The only tricky case: two slices of different arity. Since `self_slice` covers
-                // `other_slice`, `self_slice` must be `VarLen`, i.e. of the form
-                // `[prefix, .., suffix]`. Moreover `other_slice` is guaranteed to have a larger
-                // arity. So we fill the middle part with enough wildcards to reach the length of
-                // the new, larger slice.
-                match self_slice.kind {
-                    FixedLen(_) => bug!("{:?} doesn't cover {:?}", self_slice, other_slice),
-                    VarLen(prefix, suffix) => {
-                        let (ty::Slice(inner_ty) | ty::Array(inner_ty, _)) = *self.ty.kind() else {
-                            bug!("bad slice pattern {:?} {:?}", self.ctor, self.ty);
-                        };
-                        let prefix = &self.fields.fields[..prefix];
-                        let suffix = &self.fields.fields[self_slice.arity() - suffix..];
-                        let wildcard: &_ = pcx
-                            .cx
-                            .pattern_arena
-                            .alloc(DeconstructedPat::wildcard(inner_ty, DUMMY_SP));
-                        let extra_wildcards = other_slice.arity() - self_slice.arity();
-                        let extra_wildcards = (0..extra_wildcards).map(|_| wildcard);
-                        prefix.iter().chain(extra_wildcards).chain(suffix).collect()
-                    }
-                }
-            }
-            _ => self.fields.iter_patterns().collect(),
-        }
-    }
-
-    /// We keep track for each pattern if it was ever useful during the analysis. This is used
-    /// with `redundant_spans` to report redundant subpatterns arising from or patterns.
-    pub(super) fn set_useful(&self) {
-        self.useful.set(true)
-    }
-    pub(super) fn is_useful(&self) -> bool {
-        if self.useful.get() {
-            true
-        } else if self.is_or_pat() && self.iter_fields().any(|f| f.is_useful()) {
-            // We always expand or patterns in the matrix, so we will never see the actual
-            // or-pattern (the one with constructor `Or`) in the column. As such, it will not be
-            // marked as useful itself, only its children will. We recover this information here.
-            self.set_useful();
-            true
-        } else {
-            false
-        }
-    }
-
-    /// Report the spans of subpatterns that were not useful, if any.
-    pub(super) fn redundant_spans(&self) -> Vec<Span> {
-        let mut spans = Vec::new();
-        self.collect_redundant_spans(&mut spans);
-        spans
-    }
-    fn collect_redundant_spans(&self, spans: &mut Vec<Span>) {
-        // We don't look at subpatterns if we already reported the whole pattern as redundant.
-        if !self.is_useful() {
-            spans.push(self.span);
-        } else {
-            for p in self.iter_fields() {
-                p.collect_redundant_spans(spans);
-            }
-        }
-    }
-}
-
-/// 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> {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        // Printing lists is a chore.
-        let mut first = true;
-        let mut start_or_continue = |s| {
-            if first {
-                first = false;
-                ""
-            } else {
-                s
-            }
-        };
-        let mut start_or_comma = || start_or_continue(", ");
-
-        match &self.ctor {
-            Single | Variant(_) => match self.ty.kind() {
-                ty::Adt(def, _) if def.is_box() => {
-                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
-                    // of `std`). So this branch is only reachable when the feature is enabled and
-                    // the pattern is a box pattern.
-                    let subpattern = self.iter_fields().next().unwrap();
-                    write!(f, "box {subpattern:?}")
-                }
-                ty::Adt(..) | ty::Tuple(..) => {
-                    let variant = match self.ty.kind() {
-                        ty::Adt(adt, _) => Some(adt.variant(self.ctor.variant_index_for_adt(*adt))),
-                        ty::Tuple(_) => None,
-                        _ => unreachable!(),
-                    };
-
-                    if let Some(variant) = variant {
-                        write!(f, "{}", variant.name)?;
-                    }
-
-                    // Without `cx`, we can't know which field corresponds to which, so we can't
-                    // get the names of the fields. Instead we just display everything as a tuple
-                    // struct, which should be good enough.
-                    write!(f, "(")?;
-                    for p in self.iter_fields() {
-                        write!(f, "{}", start_or_comma())?;
-                        write!(f, "{p:?}")?;
-                    }
-                    write!(f, ")")
-                }
-                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
-                // be careful to detect strings here. However a string literal pattern will never
-                // be reported as a non-exhaustiveness witness, so we can ignore this issue.
-                ty::Ref(_, _, mutbl) => {
-                    let subpattern = self.iter_fields().next().unwrap();
-                    write!(f, "&{}{:?}", mutbl.prefix_str(), subpattern)
-                }
-                _ => write!(f, "_"),
-            },
-            Slice(slice) => {
-                let mut subpatterns = self.fields.iter_patterns();
-                write!(f, "[")?;
-                match slice.kind {
-                    FixedLen(_) => {
-                        for p in subpatterns {
-                            write!(f, "{}{:?}", start_or_comma(), p)?;
-                        }
-                    }
-                    VarLen(prefix_len, _) => {
-                        for p in subpatterns.by_ref().take(prefix_len) {
-                            write!(f, "{}{:?}", start_or_comma(), p)?;
-                        }
-                        write!(f, "{}", start_or_comma())?;
-                        write!(f, "..")?;
-                        for p in subpatterns {
-                            write!(f, "{}{:?}", start_or_comma(), p)?;
-                        }
-                    }
-                }
-                write!(f, "]")
-            }
-            Bool(b) => write!(f, "{b}"),
-            // Best-effort, will render signed ranges incorrectly
-            IntRange(range) => write!(f, "{range:?}"),
-            F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
-            F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
-            Str(value) => write!(f, "{value}"),
-            Opaque(..) => write!(f, "<constant pattern>"),
-            Or => {
-                for pat in self.iter_fields() {
-                    write!(f, "{}{:?}", start_or_continue(" | "), pat)?;
-                }
-                Ok(())
-            }
-            Wildcard | Missing { .. } | NonExhaustive | Hidden => write!(f, "_ : {:?}", self.ty),
-        }
-    }
-}
-
-/// 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(crate) struct WitnessPat<'tcx> {
-    ctor: Constructor<'tcx>,
-    pub(crate) fields: Vec<WitnessPat<'tcx>>,
-    ty: Ty<'tcx>,
-}
-
-impl<'tcx> WitnessPat<'tcx> {
-    pub(super) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self {
-        Self { ctor, fields, ty }
-    }
-    pub(super) fn wildcard(ty: Ty<'tcx>) -> 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(super) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, 'tcx>, ctor: Constructor<'tcx>) -> Self {
-        // Reuse `Fields::wildcards` to get the types.
-        let fields = Fields::wildcards(pcx, &ctor)
-            .iter_patterns()
-            .map(|deco_pat| Self::wildcard(deco_pat.ty()))
-            .collect();
-        Self::new(ctor, fields, pcx.ty)
-    }
-
-    pub(super) fn ctor(&self) -> &Constructor<'tcx> {
-        &self.ctor
-    }
-    pub(super) fn ty(&self) -> Ty<'tcx> {
-        self.ty
-    }
-
-    /// Convert back to a `thir::Pat` for diagnostic purposes. This panics for patterns that don't
-    /// appear in diagnostics, like float ranges.
-    pub(crate) fn to_diagnostic_pat(&self, cx: &MatchCheckCtxt<'_, 'tcx>) -> Pat<'tcx> {
-        let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild);
-        let mut subpatterns = self.iter_fields().map(|p| Box::new(p.to_diagnostic_pat(cx)));
-        let kind = match &self.ctor {
-            Bool(b) => PatKind::Constant { value: mir::Const::from_bool(cx.tcx, *b) },
-            IntRange(range) => return range.to_diagnostic_pat(self.ty, cx.tcx),
-            Single | Variant(_) => match self.ty.kind() {
-                ty::Tuple(..) => PatKind::Leaf {
-                    subpatterns: subpatterns
-                        .enumerate()
-                        .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern })
-                        .collect(),
-                },
-                ty::Adt(adt_def, _) if adt_def.is_box() => {
-                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
-                    // of `std`). So this branch is only reachable when the feature is enabled and
-                    // the pattern is a box pattern.
-                    PatKind::Deref { subpattern: subpatterns.next().unwrap() }
-                }
-                ty::Adt(adt_def, args) => {
-                    let variant_index = self.ctor.variant_index_for_adt(*adt_def);
-                    let variant = &adt_def.variant(variant_index);
-                    let subpatterns = Fields::list_variant_nonhidden_fields(cx, self.ty, variant)
-                        .zip(subpatterns)
-                        .map(|((field, _ty), pattern)| FieldPat { field, pattern })
-                        .collect();
-
-                    if adt_def.is_enum() {
-                        PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns }
-                    } else {
-                        PatKind::Leaf { subpatterns }
-                    }
-                }
-                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
-                // be careful to reconstruct the correct constant pattern here. However a string
-                // literal pattern will never be reported as a non-exhaustiveness witness, so we
-                // ignore this issue.
-                ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
-                _ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty),
-            },
-            Slice(slice) => {
-                match slice.kind {
-                    FixedLen(_) => PatKind::Slice {
-                        prefix: subpatterns.collect(),
-                        slice: None,
-                        suffix: Box::new([]),
-                    },
-                    VarLen(prefix, _) => {
-                        let mut subpatterns = subpatterns.peekable();
-                        let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect();
-                        if slice.array_len.is_some() {
-                            // Improves diagnostics a bit: if the type is a known-size array, instead
-                            // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
-                            // This is incorrect if the size is not known, since `[_, ..]` captures
-                            // arrays of lengths `>= 1` whereas `[..]` captures any length.
-                            while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) {
-                                prefix.pop();
-                            }
-                            while subpatterns.peek().is_some()
-                                && is_wildcard(subpatterns.peek().unwrap())
-                            {
-                                subpatterns.next();
-                            }
-                        }
-                        let suffix: Box<[_]> = subpatterns.collect();
-                        let wild = Pat::wildcard_from_ty(self.ty);
-                        PatKind::Slice {
-                            prefix: prefix.into_boxed_slice(),
-                            slice: Some(Box::new(wild)),
-                            suffix,
-                        }
-                    }
-                }
-            }
-            &Str(value) => PatKind::Constant { value },
-            Wildcard | NonExhaustive | Hidden => PatKind::Wild,
-            Missing { .. } => bug!(
-                "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
-                `Missing` should have been processed in `apply_constructors`"
-            ),
-            F32Range(..) | F64Range(..) | Opaque(..) | Or => {
-                bug!("can't convert to pattern: {:?}", self)
-            }
-        };
-
-        Pat { ty: self.ty, span: DUMMY_SP, kind }
-    }
-
-    pub(super) fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> {
-        self.fields.iter()
-    }
-}
diff --git a/compiler/rustc_mir_build/src/thir/pattern/mod.rs b/compiler/rustc_mir_build/src/thir/pattern/mod.rs
index eb548ad29eb..af0dab4ebc7 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/mod.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/mod.rs
@@ -2,11 +2,8 @@
 
 mod check_match;
 mod const_to_pat;
-pub(crate) mod deconstruct_pat;
-mod usefulness;
 
 pub(crate) use self::check_match::check_match;
-pub(crate) use self::usefulness::MatchCheckCtxt;
 
 use crate::errors::*;
 use crate::thir::util::UserAnnotatedTyHelpers;
diff --git a/compiler/rustc_pattern_analysis/Cargo.toml b/compiler/rustc_pattern_analysis/Cargo.toml
new file mode 100644
index 00000000000..0639944a45c
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+name = "rustc_pattern_analysis"
+version = "0.0.0"
+edition = "2021"
+
+[dependencies]
+# tidy-alphabetical-start
+rustc_apfloat = "0.2.0"
+rustc_arena = { path = "../rustc_arena" }
+rustc_data_structures = { path = "../rustc_data_structures" }
+rustc_errors = { path = "../rustc_errors" }
+rustc_fluent_macro = { path = "../rustc_fluent_macro" }
+rustc_hir = { path = "../rustc_hir" }
+rustc_index = { path = "../rustc_index" }
+rustc_macros = { path = "../rustc_macros" }
+rustc_middle = { path = "../rustc_middle" }
+rustc_session = { path = "../rustc_session" }
+rustc_span = { path = "../rustc_span" }
+rustc_target = { path = "../rustc_target" }
+smallvec = { version = "1.8.1", features = ["union", "may_dangle"] }
+tracing = "0.1"
+# tidy-alphabetical-end
diff --git a/compiler/rustc_pattern_analysis/messages.ftl b/compiler/rustc_pattern_analysis/messages.ftl
new file mode 100644
index 00000000000..827928f97d7
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/messages.ftl
@@ -0,0 +1,19 @@
+pattern_analysis_non_exhaustive_omitted_pattern = some variants are not matched explicitly
+    .help = ensure that all variants are matched explicitly by adding the suggested match arms
+    .note = the matched value is of type `{$scrut_ty}` and the `non_exhaustive_omitted_patterns` attribute was found
+
+pattern_analysis_non_exhaustive_omitted_pattern_lint_on_arm = the lint level must be set on the whole match
+    .help = it no longer has any effect to set the lint level on an individual match arm
+    .label = remove this attribute
+    .suggestion = set the lint level on the whole match
+
+pattern_analysis_overlapping_range_endpoints = multiple patterns overlap on their endpoints
+    .label = ... with this range
+    .note = you likely meant to write mutually exclusive ranges
+
+pattern_analysis_uncovered = {$count ->
+        [1] pattern `{$witness_1}`
+        [2] patterns `{$witness_1}` and `{$witness_2}`
+        [3] patterns `{$witness_1}`, `{$witness_2}` and `{$witness_3}`
+        *[other] patterns `{$witness_1}`, `{$witness_2}`, `{$witness_3}` and {$remainder} more
+    } not covered
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
new file mode 100644
index 00000000000..716ccdd4dcd
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -0,0 +1,987 @@
+//! As explained in [`crate::usefulness`], values and patterns are made from constructors applied to
+//! fields. This file defines a `Constructor` enum and various operations to manipulate them.
+//!
+//! There are two important bits of core logic in this file: constructor inclusion and constructor
+//! splitting. Constructor inclusion, i.e. whether a constructor is included in/covered by another,
+//! is straightforward and defined in [`Constructor::is_covered_by`].
+//!
+//! Constructor splitting is mentioned in [`crate::usefulness`] but not detailed. We describe it
+//! precisely here.
+//!
+//!
+//!
+//! # Constructor grouping and splitting
+//!
+//! As explained in the corresponding section in [`crate::usefulness`], to make usefulness tractable
+//! we need to group together constructors that have the same effect when they are used to
+//! specialize the matrix.
+//!
+//! Example:
+//! ```compile_fail,E0004
+//! match (0, false) {
+//!     (0 ..=100, true) => {}
+//!     (50..=150, false) => {}
+//!     (0 ..=200, _) => {}
+//! }
+//! ```
+//!
+//! In this example we can restrict specialization to 5 cases: `0..50`, `50..=100`, `101..=150`,
+//! `151..=200` and `200..`.
+//!
+//! In [`crate::usefulness`], we had said that `specialize` only takes value-only constructors. We
+//! now relax this restriction: we allow `specialize` to take constructors like `0..50` as long as
+//! we're careful to only do that with constructors that make sense. For example, `specialize(0..50,
+//! (0..=100, true))` is sensible, but `specialize(50..=200, (0..=100, true))` is not.
+//!
+//! Constructor splitting looks at the constructors in the first column of the matrix and constructs
+//! such a sensible set of constructors. Formally, we want to find a smallest disjoint set of
+//! constructors:
+//! - Whose union covers the whole type, and
+//! - 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
+//! 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`].
+//!
+//! Constructor splitting has two interesting special cases: integer range splitting (see
+//! [`IntRange::split`]) and slice splitting (see [`Slice::split`]).
+//!
+//!
+//!
+//! # The `Missing` constructor
+//!
+//! We detail a special case of constructor splitting that is a bit subtle. Take the following:
+//!
+//! ```
+//! enum Direction { North, South, East, West }
+//! # let wind = (Direction::North, 0u8);
+//! match wind {
+//!     (Direction::North, 50..) => {}
+//!     (_, _) => {}
+//! }
+//! ```
+//!
+//! Here we expect constructor splitting to output two cases: `North`, and "everything else". This
+//! "everything else" is represented by [`Constructor::Missing`]. Unlike other constructors, it's a
+//! bit contextual: to know the exact list of constructors it represents we have to look at the
+//! column. In practice however we don't need to, because by construction it only matches rows that
+//! have wildcards. This is how this constructor is special: the only constructor that covers it is
+//! `Wildcard`.
+//!
+//! The only place where we care about which constructors `Missing` represents is in diagnostics
+//! (see `crate::usefulness::WitnessMatrix::apply_constructor`).
+//!
+//! We choose whether to specialize with `Missing` in
+//! `crate::usefulness::compute_exhaustiveness_and_usefulness`.
+//!
+//!
+//!
+//! ## Empty types, empty constructors, and the `exhaustive_patterns` feature
+//!
+//! An empty type is a type that has no valid value, like `!`, `enum Void {}`, or `Result<!, !>`.
+//! They require careful handling.
+//!
+//! First, for soundness reasons related to the possible existence of invalid values, by default we
+//! don't treat empty types as empty. We force them to be matched with wildcards. Except if the
+//! `exhaustive_patterns` feature is turned on, in which case we do treat them as empty. And also
+//! except if the type has no constructors (like `enum Void {}` but not like `Result<!, !>`), we
+//! specifically allow `match void {}` to be exhaustive. There are additionally considerations of
+//! place validity that are handled in `crate::usefulness`. Yes this is a bit tricky.
+//!
+//! The second thing is that regardless of the above, it is always allowed to use all the
+//! constructors of a type. For example, all the following is ok:
+//!
+//! ```rust,ignore(example)
+//! # #![feature(never_type)]
+//! # #![feature(exhaustive_patterns)]
+//! fn foo(x: Option<!>) {
+//!   match x {
+//!     None => {}
+//!     Some(_) => {}
+//!   }
+//! }
+//! fn bar(x: &[!]) -> u32 {
+//!   match x {
+//!     [] => 1,
+//!     [_] => 2,
+//!     [_, _] => 3,
+//!   }
+//! }
+//! ```
+//!
+//! Moreover, take the following:
+//!
+//! ```rust
+//! # #![feature(never_type)]
+//! # #![feature(exhaustive_patterns)]
+//! # let x = None::<!>;
+//! match x {
+//!   None => {}
+//! }
+//! ```
+//!
+//! On a normal type, we would identify `Some` as missing and tell the user. If `x: Option<!>`
+//! however (and `exhaustive_patterns` is on), it's ok to omit `Some`. When listing the constructors
+//! of a type, we must therefore track which can be omitted.
+//!
+//! Let's call "empty" a constructor that matches no valid value for the type, like `Some` for the
+//! type `Option<!>`. What this all means is that `ConstructorSet` must know which constructors are
+//! empty. The difference between empty and nonempty constructors is that empty constructors need
+//! not be present for the match to be exhaustive.
+//!
+//! A final remark: empty constructors of arity 0 break specialization, we must avoid them. The
+//! reason is that if we specialize by them, nothing remains to witness the emptiness; the rest of
+//! 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
+//! [`ConstructorSet::split`]. The invariants of [`SplitConstructorSet`] are also of interest.
+//!
+//!
+//!
+//! ## Opaque patterns
+//!
+//! Some patterns, such as constants that are not allowed to be matched structurally, cannot be
+//! inspected, which we handle with `Constructor::Opaque`. Since we know nothing of these patterns,
+//! we assume they never cover each other. In order to respect the invariants of
+//! [`SplitConstructorSet`], we give each `Opaque` constructor a unique id so we can recognize it.
+
+use std::cmp::{self, max, min, Ordering};
+use std::fmt;
+use std::iter::once;
+
+use smallvec::SmallVec;
+
+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;
+
+/// Whether we have seen a constructor in the column or not.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+enum Presence {
+    Unseen,
+    Seen,
+}
+
+/// A possibly infinite integer. Values are encoded such that the ordering on `u128` matches the
+/// natural order on the original type. For example, `-128i8` is encoded as `0` and `127i8` as
+/// `255`. See `signed_bias` for details.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+pub enum MaybeInfiniteInt {
+    NegInfinity,
+    /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`.
+    #[non_exhaustive]
+    Finite(u128),
+    /// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range.
+    JustAfterMax,
+    PosInfinity,
+}
+
+impl MaybeInfiniteInt {
+    pub fn new_finite_uint(bits: u128) -> Self {
+        Finite(bits)
+    }
+    pub fn new_finite_int(bits: u128, size: u64) -> Self {
+        // Perform a shift if the underlying types are signed, which makes the interval arithmetic
+        // type-independent.
+        let bias = 1u128 << (size - 1);
+        Finite(bits ^ bias)
+    }
+
+    pub fn as_finite_uint(self) -> Option<u128> {
+        match self {
+            Finite(bits) => Some(bits),
+            _ => None,
+        }
+    }
+    pub fn as_finite_int(self, size: u64) -> Option<u128> {
+        // We decode the shift.
+        match self {
+            Finite(bits) => {
+                let bias = 1u128 << (size - 1);
+                Some(bits ^ bias)
+            }
+            _ => None,
+        }
+    }
+
+    /// Note: this will not turn a finite value into an infinite one or vice-versa.
+    pub fn minus_one(self) -> Self {
+        match self {
+            Finite(n) => match n.checked_sub(1) {
+                Some(m) => Finite(m),
+                None => bug!(),
+            },
+            JustAfterMax => Finite(u128::MAX),
+            x => x,
+        }
+    }
+    /// Note: this will not turn a finite value into an infinite one or vice-versa.
+    pub fn plus_one(self) -> Self {
+        match self {
+            Finite(n) => match n.checked_add(1) {
+                Some(m) => Finite(m),
+                None => JustAfterMax,
+            },
+            JustAfterMax => bug!(),
+            x => x,
+        }
+    }
+}
+
+/// An exclusive interval, used for precise integer exhaustiveness checking. `IntRange`s always
+/// store a contiguous range.
+///
+/// `IntRange` is never used to encode an empty range or a "range" that wraps around the (offset)
+/// space: i.e., `range.lo < range.hi`.
+#[derive(Clone, Copy, PartialEq, Eq)]
+pub struct IntRange {
+    pub lo: MaybeInfiniteInt, // Must not be `PosInfinity`.
+    pub hi: MaybeInfiniteInt, // Must not be `NegInfinity`.
+}
+
+impl IntRange {
+    /// Best effort; will not know that e.g. `255u8..` is a singleton.
+    pub(crate) fn is_singleton(&self) -> bool {
+        // Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite
+        // to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`.
+        self.lo.plus_one() == self.hi
+    }
+
+    #[inline]
+    pub fn from_singleton(x: MaybeInfiniteInt) -> IntRange {
+        IntRange { lo: x, hi: x.plus_one() }
+    }
+
+    #[inline]
+    pub fn from_range(lo: MaybeInfiniteInt, mut hi: MaybeInfiniteInt, end: RangeEnd) -> IntRange {
+        if end == RangeEnd::Included {
+            hi = hi.plus_one();
+        }
+        if lo >= hi {
+            // This should have been caught earlier by E0030.
+            bug!("malformed range pattern: {lo:?}..{hi:?}");
+        }
+        IntRange { lo, hi }
+    }
+
+    fn is_subrange(&self, other: &Self) -> bool {
+        other.lo <= self.lo && self.hi <= other.hi
+    }
+
+    fn intersection(&self, other: &Self) -> Option<Self> {
+        if self.lo < other.hi && other.lo < self.hi {
+            Some(IntRange { lo: max(self.lo, other.lo), hi: min(self.hi, other.hi) })
+        } else {
+            None
+        }
+    }
+
+    /// Partition a range of integers into disjoint subranges. This does constructor splitting for
+    /// integer ranges as explained at the top of the file.
+    ///
+    /// This returns an output that covers `self`. The output is split so that the only
+    /// intersections between an output range and a column range are inclusions. No output range
+    /// straddles the boundary of one of the inputs.
+    ///
+    /// Additionally, we track for each output range whether it is covered by one of the column ranges or not.
+    ///
+    /// The following input:
+    /// ```text
+    ///   (--------------------------) // `self`
+    /// (------) (----------)    (-)
+    ///     (------) (--------)
+    /// ```
+    /// is first intersected with `self`:
+    /// ```text
+    ///   (--------------------------) // `self`
+    ///   (----) (----------)    (-)
+    ///     (------) (--------)
+    /// ```
+    /// and then iterated over as follows:
+    /// ```text
+    ///   (-(--)-(-)-(------)-)--(-)-
+    /// ```
+    /// where each sequence of dashes is an output range, and dashes outside parentheses are marked
+    /// as `Presence::Missing`.
+    ///
+    /// ## `isize`/`usize`
+    ///
+    /// Whereas a wildcard of type `i32` stands for the range `i32::MIN..=i32::MAX`, a `usize`
+    /// wildcard stands for `0..PosInfinity` and a `isize` wildcard stands for
+    /// `NegInfinity..PosInfinity`. In other words, as far as `IntRange` is concerned, there are
+    /// values before `isize::MIN` and after `usize::MAX`/`isize::MAX`.
+    /// This is to avoid e.g. `0..(u32::MAX as usize)` from being exhaustive on one architecture and
+    /// not others. This was decided in <https://github.com/rust-lang/rfcs/pull/2591>.
+    ///
+    /// These infinities affect splitting subtly: it is possible to get `NegInfinity..0` and
+    /// `usize::MAX+1..PosInfinity` in the output. Diagnostics must be careful to handle these
+    /// fictitious ranges sensibly.
+    fn split(
+        &self,
+        column_ranges: impl Iterator<Item = IntRange>,
+    ) -> impl Iterator<Item = (Presence, IntRange)> {
+        // The boundaries of ranges in `column_ranges` intersected with `self`.
+        // We do parenthesis matching for input ranges. A boundary counts as +1 if it starts
+        // a range and -1 if it ends it. When the count is > 0 between two boundaries, we
+        // are within an input range.
+        let mut boundaries: Vec<(MaybeInfiniteInt, isize)> = column_ranges
+            .filter_map(|r| self.intersection(&r))
+            .flat_map(|r| [(r.lo, 1), (r.hi, -1)])
+            .collect();
+        // We sort by boundary, and for each boundary we sort the "closing parentheses" first. The
+        // order of +1/-1 for a same boundary value is actually irrelevant, because we only look at
+        // the accumulated count between distinct boundary values.
+        boundaries.sort_unstable();
+
+        // Accumulate parenthesis counts.
+        let mut paren_counter = 0isize;
+        // Gather pairs of adjacent boundaries.
+        let mut prev_bdy = self.lo;
+        boundaries
+            .into_iter()
+            // End with the end of the range. The count is ignored.
+            .chain(once((self.hi, 0)))
+            // List pairs of adjacent boundaries and the count between them.
+            .map(move |(bdy, delta)| {
+                // `delta` affects the count as we cross `bdy`, so the relevant count between
+                // `prev_bdy` and `bdy` is untouched by `delta`.
+                let ret = (prev_bdy, paren_counter, bdy);
+                prev_bdy = bdy;
+                paren_counter += delta;
+                ret
+            })
+            // Skip empty ranges.
+            .filter(|&(prev_bdy, _, bdy)| prev_bdy != bdy)
+            // Convert back to ranges.
+            .map(move |(prev_bdy, paren_count, bdy)| {
+                use Presence::*;
+                let presence = if paren_count > 0 { Seen } else { Unseen };
+                let range = IntRange { lo: prev_bdy, hi: bdy };
+                (presence, range)
+            })
+    }
+}
+
+/// Note: this will render signed ranges incorrectly. To render properly, convert to a pattern
+/// first.
+impl fmt::Debug for IntRange {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if let Finite(lo) = self.lo {
+            write!(f, "{lo}")?;
+        }
+        write!(f, "{}", RangeEnd::Excluded)?;
+        if let Finite(hi) = self.hi {
+            write!(f, "{hi}")?;
+        }
+        Ok(())
+    }
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum SliceKind {
+    /// Patterns of length `n` (`[x, y]`).
+    FixedLen(usize),
+    /// Patterns using the `..` notation (`[x, .., y]`).
+    /// Captures any array constructor of `length >= i + j`.
+    /// In the case where `array_len` is `Some(_)`,
+    /// this indicates that we only care about the first `i` and the last `j` values of the array,
+    /// and everything in between is a wildcard `_`.
+    VarLen(usize, usize),
+}
+
+impl SliceKind {
+    fn arity(self) -> usize {
+        match self {
+            FixedLen(length) => length,
+            VarLen(prefix, suffix) => prefix + suffix,
+        }
+    }
+
+    /// Whether this pattern includes patterns of length `other_len`.
+    fn covers_length(self, other_len: usize) -> bool {
+        match self {
+            FixedLen(len) => len == other_len,
+            VarLen(prefix, suffix) => prefix + suffix <= other_len,
+        }
+    }
+}
+
+/// A constructor for array and slice patterns.
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub struct Slice {
+    /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`.
+    pub(crate) array_len: Option<usize>,
+    /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`.
+    pub(crate) kind: SliceKind,
+}
+
+impl Slice {
+    pub fn new(array_len: Option<usize>, kind: SliceKind) -> Self {
+        let kind = match (array_len, kind) {
+            // If the middle `..` has length 0, we effectively have a fixed-length pattern.
+            (Some(len), VarLen(prefix, suffix)) if prefix + suffix == len => FixedLen(len),
+            (Some(len), VarLen(prefix, suffix)) if prefix + suffix > len => bug!(
+                "Slice pattern of length {} longer than its array length {len}",
+                prefix + suffix
+            ),
+            _ => kind,
+        };
+        Slice { array_len, kind }
+    }
+
+    pub(crate) fn arity(self) -> usize {
+        self.kind.arity()
+    }
+
+    /// See `Constructor::is_covered_by`
+    fn is_covered_by(self, other: Self) -> bool {
+        other.kind.covers_length(self.arity())
+    }
+
+    /// This computes constructor splitting for variable-length slices, as explained at the top of
+    /// the file.
+    ///
+    /// A slice pattern `[x, .., y]` behaves like the infinite or-pattern `[x, y] | [x, _, y] | [x,
+    /// _, _, y] | etc`. The corresponding value constructors are fixed-length array constructors of
+    /// corresponding lengths. We obviously can't list this infinitude of constructors.
+    /// Thankfully, it turns out that for each finite set of slice patterns, all sufficiently large
+    /// array lengths are equivalent.
+    ///
+    /// Let's look at an example, where we are trying to split the last pattern:
+    /// ```
+    /// # fn foo(x: &[bool]) {
+    /// match x {
+    ///     [true, true, ..] => {}
+    ///     [.., false, false] => {}
+    ///     [..] => {}
+    /// }
+    /// # }
+    /// ```
+    /// Here are the results of specialization for the first few lengths:
+    /// ```
+    /// # fn foo(x: &[bool]) { match x {
+    /// // length 0
+    /// [] => {}
+    /// // length 1
+    /// [_] => {}
+    /// // length 2
+    /// [true, true] => {}
+    /// [false, false] => {}
+    /// [_, _] => {}
+    /// // length 3
+    /// [true, true,  _    ] => {}
+    /// [_,    false, false] => {}
+    /// [_,    _,     _    ] => {}
+    /// // length 4
+    /// [true, true, _,     _    ] => {}
+    /// [_,    _,    false, false] => {}
+    /// [_,    _,    _,     _    ] => {}
+    /// // length 5
+    /// [true, true, _, _,     _    ] => {}
+    /// [_,    _,    _, false, false] => {}
+    /// [_,    _,    _, _,     _    ] => {}
+    /// # _ => {}
+    /// # }}
+    /// ```
+    ///
+    /// We see that above length 4, we are simply inserting columns full of wildcards in the middle.
+    /// This means that specialization and witness computation with slices of length `l >= 4` will
+    /// give equivalent results regardless of `l`. This applies to any set of slice patterns: there
+    /// will be a length `L` above which all lengths behave the same. This is exactly what we need
+    /// for constructor splitting.
+    ///
+    /// A variable-length slice pattern covers all lengths from its arity up to infinity. As we just
+    /// saw, we can split this in two: lengths below `L` are treated individually with a
+    /// fixed-length slice each; lengths above `L` are grouped into a single variable-length slice
+    /// constructor.
+    ///
+    /// For each variable-length slice pattern `p` with a prefix of length `plₚ` and suffix of
+    /// length `slₚ`, only the first `plₚ` and the last `slₚ` elements are examined. Therefore, as
+    /// long as `L` is positive (to avoid concerns about empty types), all elements after the
+    /// maximum prefix length and before the maximum suffix length are not examined by any
+    /// variable-length pattern, and therefore can be ignored. This gives us a way to compute `L`.
+    ///
+    /// Additionally, if fixed-length patterns exist, we must pick an `L` large enough to miss them,
+    /// so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))`.
+    /// `max_slice` below will be made to have this arity `L`.
+    ///
+    /// If `self` is fixed-length, it is returned as-is.
+    ///
+    /// Additionally, we track for each output slice whether it is covered by one of the column slices or not.
+    fn split(
+        self,
+        column_slices: impl Iterator<Item = Slice>,
+    ) -> impl Iterator<Item = (Presence, Slice)> {
+        // Range of lengths below `L`.
+        let smaller_lengths;
+        let arity = self.arity();
+        let mut max_slice = self.kind;
+        // Tracks the smallest variable-length slice we've seen. Any slice arity above it is
+        // therefore `Presence::Seen` in the column.
+        let mut min_var_len = usize::MAX;
+        // Tracks the fixed-length slices we've seen, to mark them as `Presence::Seen`.
+        let mut seen_fixed_lens = FxHashSet::default();
+        match &mut max_slice {
+            VarLen(max_prefix_len, max_suffix_len) => {
+                // A length larger than any fixed-length slice encountered.
+                // We start at 1 in case the subtype is empty because in that case the zero-length
+                // slice must be treated separately from the rest.
+                let mut fixed_len_upper_bound = 1;
+                // We grow `max_slice` to be larger than all slices encountered, as described above.
+                // `L` is `max_slice.arity()`. For diagnostics, we keep the prefix and suffix
+                // lengths separate.
+                for slice in column_slices {
+                    match slice.kind {
+                        FixedLen(len) => {
+                            fixed_len_upper_bound = cmp::max(fixed_len_upper_bound, len + 1);
+                            seen_fixed_lens.insert(len);
+                        }
+                        VarLen(prefix, suffix) => {
+                            *max_prefix_len = cmp::max(*max_prefix_len, prefix);
+                            *max_suffix_len = cmp::max(*max_suffix_len, suffix);
+                            min_var_len = cmp::min(min_var_len, prefix + suffix);
+                        }
+                    }
+                }
+                // If `fixed_len_upper_bound >= L`, we set `L` to `fixed_len_upper_bound`.
+                if let Some(delta) =
+                    fixed_len_upper_bound.checked_sub(*max_prefix_len + *max_suffix_len)
+                {
+                    *max_prefix_len += delta
+                }
+
+                // We cap the arity of `max_slice` at the array size.
+                match self.array_len {
+                    Some(len) if max_slice.arity() >= len => max_slice = FixedLen(len),
+                    _ => {}
+                }
+
+                smaller_lengths = match self.array_len {
+                    // The only admissible fixed-length slice is one of the array size. Whether `max_slice`
+                    // is fixed-length or variable-length, it will be the only relevant slice to output
+                    // here.
+                    Some(_) => 0..0, // empty range
+                    // We need to cover all arities in the range `(arity..infinity)`. We split that
+                    // range into two: lengths smaller than `max_slice.arity()` are treated
+                    // independently as fixed-lengths slices, and lengths above are captured by
+                    // `max_slice`.
+                    None => self.arity()..max_slice.arity(),
+                };
+            }
+            FixedLen(_) => {
+                // No need to split here. We only track presence.
+                for slice in column_slices {
+                    match slice.kind {
+                        FixedLen(len) => {
+                            if len == arity {
+                                seen_fixed_lens.insert(len);
+                            }
+                        }
+                        VarLen(prefix, suffix) => {
+                            min_var_len = cmp::min(min_var_len, prefix + suffix);
+                        }
+                    }
+                }
+                smaller_lengths = 0..0;
+            }
+        };
+
+        smaller_lengths.map(FixedLen).chain(once(max_slice)).map(move |kind| {
+            let arity = kind.arity();
+            let seen = if min_var_len <= arity || seen_fixed_lens.contains(&arity) {
+                Presence::Seen
+            } else {
+                Presence::Unseen
+            };
+            (seen, Slice::new(self.array_len, kind))
+        })
+    }
+}
+
+/// A globally unique id to distinguish `Opaque` patterns.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct OpaqueId(u32);
+
+impl OpaqueId {
+    pub fn new() -> Self {
+        use std::sync::atomic::{AtomicU32, Ordering};
+        static OPAQUE_ID: AtomicU32 = AtomicU32::new(0);
+        OpaqueId(OPAQUE_ID.fetch_add(1, Ordering::SeqCst))
+    }
+}
+
+/// A value can be decomposed into a constructor applied to some fields. This struct represents
+/// the constructor. See also `Fields`.
+///
+/// `pat_constructor` retrieves the constructor corresponding to a pattern.
+/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
+/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
+/// `Fields`.
+#[derive(Clone, Debug, PartialEq)]
+pub enum Constructor<'tcx> {
+    /// The constructor for patterns that have a single constructor, like tuples, struct patterns,
+    /// and references. Fixed-length arrays are treated separately with `Slice`.
+    Single,
+    /// Enum variants.
+    Variant(VariantIdx),
+    /// Booleans
+    Bool(bool),
+    /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
+    IntRange(IntRange),
+    /// Ranges of floating-point literal values (`2.0..=5.2`).
+    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>),
+    /// Array and slice patterns.
+    Slice(Slice),
+    /// 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.
+    /// Carries an id that must be unique within a match. We need this to ensure the invariants of
+    /// [`SplitConstructorSet`].
+    Opaque(OpaqueId),
+    /// Or-pattern.
+    Or,
+    /// Wildcard pattern.
+    Wildcard,
+    /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used
+    /// for those types for which we cannot list constructors explicitly, like `f64` and `str`.
+    NonExhaustive,
+    /// Fake extra constructor for variants that should not be mentioned in diagnostics.
+    /// We use this for variants behind an unstable gate as well as
+    /// `#[doc(hidden)]` ones.
+    Hidden,
+    /// Fake extra constructor for constructors that are not seen in the matrix, as explained at the
+    /// top of the file.
+    Missing,
+}
+
+impl<'tcx> Constructor<'tcx> {
+    pub(crate) fn is_non_exhaustive(&self) -> bool {
+        matches!(self, NonExhaustive)
+    }
+
+    pub(crate) fn as_variant(&self) -> Option<VariantIdx> {
+        match self {
+            Variant(i) => Some(*i),
+            _ => None,
+        }
+    }
+    fn as_bool(&self) -> Option<bool> {
+        match self {
+            Bool(b) => Some(*b),
+            _ => None,
+        }
+    }
+    pub(crate) fn as_int_range(&self) -> Option<&IntRange> {
+        match self {
+            IntRange(range) => Some(range),
+            _ => None,
+        }
+    }
+    fn as_slice(&self) -> Option<Slice> {
+        match self {
+            Slice(slice) => Some(*slice),
+            _ => None,
+        }
+    }
+
+    /// 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 {
+        pcx.cx.ctor_arity(self, pcx.ty)
+    }
+
+    /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
+    /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
+    /// 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 {
+        match (self, other) {
+            (Wildcard, _) => {
+                span_bug!(
+                    pcx.cx.scrut_span,
+                    "Constructor splitting should not have returned `Wildcard`"
+                )
+            }
+            // Wildcards cover anything
+            (_, Wildcard) => true,
+            // Only a wildcard pattern can match these special constructors.
+            (Missing { .. } | NonExhaustive | Hidden, _) => false,
+
+            (Single, Single) => true,
+            (Variant(self_id), Variant(other_id)) => self_id == other_id,
+            (Bool(self_b), Bool(other_b)) => self_b == other_b,
+
+            (IntRange(self_range), IntRange(other_range)) => self_range.is_subrange(other_range),
+            (F32Range(self_from, self_to, self_end), F32Range(other_from, other_to, other_end)) => {
+                self_from.ge(other_from)
+                    && match self_to.partial_cmp(other_to) {
+                        Some(Ordering::Less) => true,
+                        Some(Ordering::Equal) => other_end == self_end,
+                        _ => false,
+                    }
+            }
+            (F64Range(self_from, self_to, self_end), F64Range(other_from, other_to, other_end)) => {
+                self_from.ge(other_from)
+                    && match self_to.partial_cmp(other_to) {
+                        Some(Ordering::Less) => true,
+                        Some(Ordering::Equal) => other_end == self_end,
+                        _ => false,
+                    }
+            }
+            (Str(self_val), Str(other_val)) => {
+                // FIXME Once valtrees are available we can directly use the bytes
+                // in the `Str` variant of the valtree for the comparison here.
+                self_val == other_val
+            }
+            (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
+
+            // Opaque constructors don't interact with anything unless they come from the
+            // syntactically identical pattern.
+            (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
+            ),
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy)]
+pub enum VariantVisibility {
+    /// Variant that doesn't fit the other cases, i.e. most variants.
+    Visible,
+    /// Variant behind an unstable gate or with the `#[doc(hidden)]` attribute. It will not be
+    /// mentioned in diagnostics unless the user mentioned it first.
+    Hidden,
+    /// Variant that matches no value. E.g. `Some::<Option<!>>` if the `exhaustive_patterns` feature
+    /// is enabled. Like `Hidden`, it will not be mentioned in diagnostics unless the user mentioned
+    /// it first.
+    Empty,
+}
+
+/// Describes the set of all constructors for a type. For details, in particular about the emptiness
+/// of constructors, see the top of the file.
+///
+/// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the
+/// `exhaustive_patterns` feature.
+#[derive(Debug)]
+pub enum ConstructorSet {
+    /// The type has a single constructor, e.g. `&T` or a struct. `empty` tracks whether the
+    /// constructor is empty.
+    Single { 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 },
+    /// Booleans.
+    Bool,
+    /// The type is spanned by integer values. The range or ranges give the set of allowed values.
+    /// The second range is only useful for `char`.
+    Integers { range_1: IntRange, range_2: Option<IntRange> },
+    /// The type is matched by slices. `array_len` is the compile-time length of the array, if
+    /// known. If `subtype_is_empty`, all constructors are empty except possibly the zero-length
+    /// slice `[]`.
+    Slice { array_len: Option<usize>, subtype_is_empty: bool },
+    /// The constructors cannot be listed, and the type cannot be matched exhaustively. E.g. `str`,
+    /// floats.
+    Unlistable,
+    /// The type has no constructors (not even empty ones). This is `!` and empty enums.
+    NoConstructors,
+}
+
+/// Describes the result of analyzing the constructors in a column of a match.
+///
+/// `present` is morally the set of constructors present in the column, and `missing` is the set of
+/// constructors that exist in the type but are not present in the column.
+///
+/// More formally, if we discard wildcards from the column, this respects the following constraints:
+/// 1. the union of `present`, `missing` and `missing_empty` covers all the constructors of the type
+/// 2. each constructor in `present` is covered by something in the column
+/// 3. no constructor in `missing` or `missing_empty` is covered by anything in the column
+/// 4. each constructor in the column is equal to the union of one or more constructors in `present`
+/// 5. `missing` does not contain empty constructors (see discussion about emptiness at the top of
+///    the file);
+/// 6. `missing_empty` contains only empty constructors
+/// 7. constructors in `present`, `missing` and `missing_empty` are split for the column; in other
+///    words, they are either fully included in or fully disjoint from each constructor in the
+///    column. In yet other words, there are no non-trivial intersections like between `0..10` and
+///    `5..15`.
+///
+/// We must be particularly careful with weird constructors like `Opaque`: they're not formally part
+/// 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>>,
+}
+
+impl ConstructorSet {
+    /// 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>(
+        &self,
+        pcx: &PatCtxt<'_, '_, 'tcx>,
+        ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
+    ) -> SplitConstructorSet<'tcx>
+    where
+        'tcx: 'a,
+    {
+        let mut present: SmallVec<[_; 1]> = SmallVec::new();
+        // Empty constructors found missing.
+        let mut missing_empty = Vec::new();
+        // Nonempty constructors found missing.
+        let mut missing = Vec::new();
+        // Constructors in `ctors`, except wildcards and opaques.
+        let mut seen = Vec::new();
+        for ctor in ctors.cloned() {
+            match ctor {
+                Opaque(..) => present.push(ctor),
+                Wildcard => {} // discard wildcards
+                _ => seen.push(ctor),
+            }
+        }
+
+        match self {
+            ConstructorSet::Single { empty } => {
+                if !seen.is_empty() {
+                    present.push(Single);
+                } else if *empty {
+                    missing_empty.push(Single);
+                } else {
+                    missing.push(Single);
+                }
+            }
+            ConstructorSet::Variants { variants, non_exhaustive } => {
+                let seen_set: FxHashSet<_> = seen.iter().map(|c| c.as_variant().unwrap()).collect();
+                let mut skipped_a_hidden_variant = false;
+
+                for (idx, visibility) in variants.iter_enumerated() {
+                    let ctor = Variant(idx);
+                    if seen_set.contains(&idx) {
+                        present.push(ctor);
+                    } else {
+                        // We only put visible variants directly into `missing`.
+                        match visibility {
+                            VariantVisibility::Visible => missing.push(ctor),
+                            VariantVisibility::Hidden => skipped_a_hidden_variant = true,
+                            VariantVisibility::Empty => missing_empty.push(ctor),
+                        }
+                    }
+                }
+
+                if skipped_a_hidden_variant {
+                    missing.push(Hidden);
+                }
+                if *non_exhaustive {
+                    missing.push(NonExhaustive);
+                }
+            }
+            ConstructorSet::Bool => {
+                let mut seen_false = false;
+                let mut seen_true = false;
+                for b in seen.iter().map(|ctor| ctor.as_bool().unwrap()) {
+                    if b {
+                        seen_true = true;
+                    } else {
+                        seen_false = true;
+                    }
+                }
+                if seen_false {
+                    present.push(Bool(false));
+                } else {
+                    missing.push(Bool(false));
+                }
+                if seen_true {
+                    present.push(Bool(true));
+                } else {
+                    missing.push(Bool(true));
+                }
+            }
+            ConstructorSet::Integers { range_1, range_2 } => {
+                let seen_ranges: Vec<_> =
+                    seen.iter().map(|ctor| ctor.as_int_range().unwrap().clone()).collect();
+                for (seen, splitted_range) in range_1.split(seen_ranges.iter().cloned()) {
+                    match seen {
+                        Presence::Unseen => missing.push(IntRange(splitted_range)),
+                        Presence::Seen => present.push(IntRange(splitted_range)),
+                    }
+                }
+                if let Some(range_2) = range_2 {
+                    for (seen, splitted_range) in range_2.split(seen_ranges.into_iter()) {
+                        match seen {
+                            Presence::Unseen => missing.push(IntRange(splitted_range)),
+                            Presence::Seen => present.push(IntRange(splitted_range)),
+                        }
+                    }
+                }
+            }
+            ConstructorSet::Slice { array_len, subtype_is_empty } => {
+                let seen_slices = seen.iter().map(|c| c.as_slice().unwrap());
+                let base_slice = Slice::new(*array_len, VarLen(0, 0));
+                for (seen, splitted_slice) in base_slice.split(seen_slices) {
+                    let ctor = Slice(splitted_slice);
+                    match seen {
+                        Presence::Seen => present.push(ctor),
+                        Presence::Unseen => {
+                            if *subtype_is_empty && splitted_slice.arity() != 0 {
+                                // We have subpatterns of an empty type, so the constructor is
+                                // empty.
+                                missing_empty.push(ctor);
+                            } else {
+                                missing.push(ctor);
+                            }
+                        }
+                    }
+                }
+            }
+            ConstructorSet::Unlistable => {
+                // Since we can't list constructors, we take the ones in the column. This might list
+                // some constructors several times but there's not much we can do.
+                present.extend(seen);
+                missing.push(NonExhaustive);
+            }
+            ConstructorSet::NoConstructors => {
+                // In a `MaybeInvalid` place even an empty pattern may be reachable. We therefore
+                // add a dummy empty constructor here, which will be ignored if the place is
+                // `ValidOnly`.
+                missing_empty.push(NonExhaustive);
+            }
+        }
+
+        // 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
+            && !(pcx.is_top_level && matches!(self, Self::NoConstructors))
+        {
+            // Treat all missing constructors as nonempty.
+            missing.extend(missing_empty.drain(..));
+        }
+
+        SplitConstructorSet { present, missing, missing_empty }
+    }
+}
diff --git a/compiler/rustc_pattern_analysis/src/cx.rs b/compiler/rustc_pattern_analysis/src/cx.rs
new file mode 100644
index 00000000000..8a4f39a1f4a
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/cx.rs
@@ -0,0 +1,856 @@
+use std::fmt;
+use std::iter::once;
+
+use rustc_arena::TypedArena;
+use rustc_data_structures::captures::Captures;
+use rustc_hir::def_id::DefId;
+use rustc_hir::{HirId, RangeEnd};
+use rustc_index::Idx;
+use rustc_index::IndexVec;
+use rustc_middle::middle::stability::EvalResult;
+use rustc_middle::mir;
+use rustc_middle::mir::interpret::Scalar;
+use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
+use rustc_middle::ty::layout::IntegerExt;
+use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef};
+use rustc_span::{Span, DUMMY_SP};
+use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
+use smallvec::SmallVec;
+
+use crate::constructor::{
+    Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, OpaqueId, Slice, SliceKind,
+    VariantVisibility,
+};
+use crate::pat::{DeconstructedPat, WitnessPat};
+
+use Constructor::*;
+
+pub struct MatchCheckCtxt<'p, 'tcx> {
+    pub tcx: TyCtxt<'tcx>,
+    /// The module in which the match occurs. This is necessary for
+    /// checking inhabited-ness of types because whether a type is (visibly)
+    /// inhabited can depend on whether it was defined in the current module or
+    /// not. E.g., `struct Foo { _private: ! }` cannot be seen to be empty
+    /// outside its module and should not be matchable with an empty match statement.
+    pub module: DefId,
+    pub param_env: ty::ParamEnv<'tcx>,
+    pub pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
+    /// Lint level at the match.
+    pub match_lint_level: HirId,
+    /// The span of the whole match, if applicable.
+    pub whole_match_span: Option<Span>,
+    /// Span of the scrutinee.
+    pub scrut_span: Span,
+    /// Only produce `NON_EXHAUSTIVE_OMITTED_PATTERNS` lint on refutable patterns.
+    pub refutable: bool,
+    /// Whether the data at the scrutinee is known to be valid. This is false if the scrutinee comes
+    /// from a union field, a pointer deref, or a reference deref (pending opsem decisions).
+    pub known_valid_scrutinee: bool,
+}
+
+impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> {
+    pub(super) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
+        !ty.is_inhabited_from(self.tcx, self.module, self.param_env)
+    }
+
+    /// 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() {
+            ty::Adt(def, ..) => {
+                def.is_enum() && def.is_variant_list_non_exhaustive() && !def.did().is_local()
+            }
+            _ => false,
+        }
+    }
+
+    pub(crate) fn alloc_wildcard_slice(
+        &self,
+        tys: impl IntoIterator<Item = Ty<'tcx>>,
+    ) -> &'p [DeconstructedPat<'p, 'tcx>] {
+        self.pattern_arena
+            .alloc_from_iter(tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, DUMMY_SP)))
+    }
+
+    // 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.
+    pub(crate) fn list_variant_nonhidden_fields<'a>(
+        &'a self,
+        ty: Ty<'tcx>,
+        variant: &'a VariantDef,
+    ) -> impl Iterator<Item = (FieldIdx, Ty<'tcx>)> + Captures<'p> + Captures<'a> {
+        let cx = self;
+        let ty::Adt(adt, args) = ty.kind() else { bug!() };
+        // Whether we must not match the fields of this variant exhaustively.
+        let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !adt.did().is_local();
+
+        variant.fields.iter().enumerate().filter_map(move |(i, field)| {
+            let ty = field.ty(cx.tcx, args);
+            // `field.ty()` doesn't normalize after substituting.
+            let ty = cx.tcx.normalize_erasing_regions(cx.param_env, ty);
+            let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx);
+            let is_uninhabited = cx.tcx.features().exhaustive_patterns && cx.is_uninhabited(ty);
+
+            if is_uninhabited && (!is_visible || is_non_exhaustive) {
+                None
+            } else {
+                Some((FieldIdx::new(i), ty))
+            }
+        })
+    }
+
+    pub(crate) fn variant_index_for_adt(
+        ctor: &Constructor<'tcx>,
+        adt: ty::AdtDef<'tcx>,
+    ) -> VariantIdx {
+        match *ctor {
+            Variant(idx) => idx,
+            Single => {
+                assert!(!adt.is_enum());
+                FIRST_VARIANT
+            }
+            _ => bug!("bad constructor {:?} for adt {:?}", ctor, adt),
+        }
+    }
+
+    /// Creates a new list of wildcard fields for a given constructor. The result must have a length
+    /// of `ctor.arity()`.
+    #[instrument(level = "trace", skip(self))]
+    pub(crate) fn ctor_wildcard_fields(
+        &self,
+        ctor: &Constructor<'tcx>,
+        ty: Ty<'tcx>,
+    ) -> &'p [DeconstructedPat<'p, 'tcx>] {
+        let cx = self;
+        match ctor {
+            Single | Variant(_) => match ty.kind() {
+                ty::Tuple(fs) => cx.alloc_wildcard_slice(fs.iter()),
+                ty::Ref(_, rty, _) => cx.alloc_wildcard_slice(once(*rty)),
+                ty::Adt(adt, args) => {
+                    if adt.is_box() {
+                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
+                        // patterns. If we're here we can assume this is a box pattern.
+                        cx.alloc_wildcard_slice(once(args.type_at(0)))
+                    } else {
+                        let variant =
+                            &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt));
+                        let tys = cx.list_variant_nonhidden_fields(ty, variant).map(|(_, ty)| ty);
+                        cx.alloc_wildcard_slice(tys)
+                    }
+                }
+                _ => bug!("Unexpected type for `Single` constructor: {:?}", ty),
+            },
+            Slice(slice) => match *ty.kind() {
+                ty::Slice(ty) | ty::Array(ty, _) => {
+                    let arity = slice.arity();
+                    cx.alloc_wildcard_slice((0..arity).map(|_| ty))
+                }
+                _ => bug!("bad slice pattern {:?} {:?}", ctor, ty),
+            },
+            Bool(..)
+            | IntRange(..)
+            | F32Range(..)
+            | F64Range(..)
+            | Str(..)
+            | Opaque(..)
+            | NonExhaustive
+            | Hidden
+            | Missing { .. }
+            | Wildcard => &[],
+            Or => {
+                bug!("called `Fields::wildcards` on an `Or` ctor")
+            }
+        }
+    }
+
+    /// 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 {
+        match ctor {
+            Single | Variant(_) => match ty.kind() {
+                ty::Tuple(fs) => fs.len(),
+                ty::Ref(..) => 1,
+                ty::Adt(adt, ..) => {
+                    if adt.is_box() {
+                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
+                        // patterns. If we're here we can assume this is a box pattern.
+                        1
+                    } else {
+                        let variant =
+                            &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt));
+                        self.list_variant_nonhidden_fields(ty, variant).count()
+                    }
+                }
+                _ => bug!("Unexpected type for `Single` constructor: {:?}", ty),
+            },
+            Slice(slice) => slice.arity(),
+            Bool(..)
+            | IntRange(..)
+            | F32Range(..)
+            | F64Range(..)
+            | Str(..)
+            | Opaque(..)
+            | NonExhaustive
+            | Hidden
+            | Missing { .. }
+            | Wildcard => 0,
+            Or => bug!("The `Or` constructor doesn't have a fixed arity"),
+        }
+    }
+
+    /// Creates a set that represents all the constructors of `ty`.
+    ///
+    /// See [`crate::constructor`] for considerations of emptiness.
+    #[instrument(level = "debug", skip(self), ret)]
+    pub fn ctors_for_ty(&self, ty: Ty<'tcx>) -> ConstructorSet {
+        let cx = self;
+        let make_uint_range = |start, end| {
+            IntRange::from_range(
+                MaybeInfiniteInt::new_finite_uint(start),
+                MaybeInfiniteInt::new_finite_uint(end),
+                RangeEnd::Included,
+            )
+        };
+        // This determines the set of all possible constructors for the type `ty`. For numbers,
+        // arrays and slices we use ranges and variable-length slices when appropriate.
+        match ty.kind() {
+            ty::Bool => ConstructorSet::Bool,
+            ty::Char => {
+                // The valid Unicode Scalar Value ranges.
+                ConstructorSet::Integers {
+                    range_1: make_uint_range('\u{0000}' as u128, '\u{D7FF}' as u128),
+                    range_2: Some(make_uint_range('\u{E000}' as u128, '\u{10FFFF}' as u128)),
+                }
+            }
+            &ty::Int(ity) => {
+                let range = if ty.is_ptr_sized_integral() {
+                    // The min/max values of `isize` are not allowed to be observed.
+                    IntRange {
+                        lo: MaybeInfiniteInt::NegInfinity,
+                        hi: MaybeInfiniteInt::PosInfinity,
+                    }
+                } else {
+                    let size = Integer::from_int_ty(&cx.tcx, ity).size().bits();
+                    let min = 1u128 << (size - 1);
+                    let max = min - 1;
+                    let min = MaybeInfiniteInt::new_finite_int(min, size);
+                    let max = MaybeInfiniteInt::new_finite_int(max, size);
+                    IntRange::from_range(min, max, RangeEnd::Included)
+                };
+                ConstructorSet::Integers { range_1: range, range_2: None }
+            }
+            &ty::Uint(uty) => {
+                let range = if ty.is_ptr_sized_integral() {
+                    // The max value of `usize` is not allowed to be observed.
+                    let lo = MaybeInfiniteInt::new_finite_uint(0);
+                    IntRange { lo, hi: MaybeInfiniteInt::PosInfinity }
+                } else {
+                    let size = Integer::from_uint_ty(&cx.tcx, uty).size();
+                    let max = size.truncate(u128::MAX);
+                    make_uint_range(0, max)
+                };
+                ConstructorSet::Integers { range_1: range, range_2: None }
+            }
+            ty::Slice(sub_ty) => ConstructorSet::Slice {
+                array_len: None,
+                subtype_is_empty: cx.is_uninhabited(*sub_ty),
+            },
+            ty::Array(sub_ty, len) => {
+                // We treat arrays of a constant but unknown length like slices.
+                ConstructorSet::Slice {
+                    array_len: len.try_eval_target_usize(cx.tcx, cx.param_env).map(|l| l as usize),
+                    subtype_is_empty: cx.is_uninhabited(*sub_ty),
+                }
+            }
+            ty::Adt(def, args) if def.is_enum() => {
+                let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(ty);
+                if def.variants().is_empty() && !is_declared_nonexhaustive {
+                    ConstructorSet::NoConstructors
+                } else {
+                    let mut variants =
+                        IndexVec::from_elem(VariantVisibility::Visible, def.variants());
+                    for (idx, v) in def.variants().iter_enumerated() {
+                        let variant_def_id = def.variant(idx).def_id;
+                        // Visibly uninhabited variants.
+                        let is_inhabited = v
+                            .inhabited_predicate(cx.tcx, *def)
+                            .instantiate(cx.tcx, args)
+                            .apply(cx.tcx, cx.param_env, cx.module);
+                        // Variants that depend on a disabled unstable feature.
+                        let is_unstable = matches!(
+                            cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None),
+                            EvalResult::Deny { .. }
+                        );
+                        // Foreign `#[doc(hidden)]` variants.
+                        let is_doc_hidden =
+                            cx.tcx.is_doc_hidden(variant_def_id) && !variant_def_id.is_local();
+                        let visibility = if !is_inhabited {
+                            // FIXME: handle empty+hidden
+                            VariantVisibility::Empty
+                        } else if is_unstable || is_doc_hidden {
+                            VariantVisibility::Hidden
+                        } else {
+                            VariantVisibility::Visible
+                        };
+                        variants[idx] = visibility;
+                    }
+
+                    ConstructorSet::Variants { variants, non_exhaustive: is_declared_nonexhaustive }
+                }
+            }
+            ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => {
+                ConstructorSet::Single { empty: cx.is_uninhabited(ty) }
+            }
+            ty::Never => ConstructorSet::NoConstructors,
+            // This type is one for which we cannot list constructors, like `str` or `f64`.
+            // FIXME(Nadrieril): which of these are actually allowed?
+            ty::Float(_)
+            | ty::Str
+            | ty::Foreign(_)
+            | ty::RawPtr(_)
+            | ty::FnDef(_, _)
+            | ty::FnPtr(_)
+            | ty::Dynamic(_, _, _)
+            | ty::Closure(_, _)
+            | ty::Coroutine(_, _, _)
+            | ty::Alias(_, _)
+            | ty::Param(_)
+            | ty::Error(_) => ConstructorSet::Unlistable,
+            ty::CoroutineWitness(_, _) | ty::Bound(_, _) | ty::Placeholder(_) | ty::Infer(_) => {
+                bug!("Encountered unexpected type in `ConstructorSet::for_ty`: {ty:?}")
+            }
+        }
+    }
+
+    pub(crate) fn lower_pat_range_bdy(
+        &self,
+        bdy: PatRangeBoundary<'tcx>,
+        ty: Ty<'tcx>,
+    ) -> MaybeInfiniteInt {
+        match bdy {
+            PatRangeBoundary::NegInfinity => MaybeInfiniteInt::NegInfinity,
+            PatRangeBoundary::Finite(value) => {
+                let bits = value.eval_bits(self.tcx, self.param_env);
+                match *ty.kind() {
+                    ty::Int(ity) => {
+                        let size = Integer::from_int_ty(&self.tcx, ity).size().bits();
+                        MaybeInfiniteInt::new_finite_int(bits, size)
+                    }
+                    _ => MaybeInfiniteInt::new_finite_uint(bits),
+                }
+            }
+            PatRangeBoundary::PosInfinity => MaybeInfiniteInt::PosInfinity,
+        }
+    }
+
+    /// Note: the input patterns must have been lowered through
+    /// `rustc_mir_build::thir::pattern::check_match::MatchVisitor::lower_pattern`.
+    pub fn lower_pat(&self, pat: &Pat<'tcx>) -> DeconstructedPat<'p, 'tcx> {
+        let singleton = |pat| std::slice::from_ref(self.pattern_arena.alloc(pat));
+        let cx = self;
+        let ctor;
+        let fields: &[_];
+        match &pat.kind {
+            PatKind::AscribeUserType { subpattern, .. }
+            | PatKind::InlineConstant { subpattern, .. } => return self.lower_pat(subpattern),
+            PatKind::Binding { subpattern: Some(subpat), .. } => return self.lower_pat(subpat),
+            PatKind::Binding { subpattern: None, .. } | PatKind::Wild => {
+                ctor = Wildcard;
+                fields = &[];
+            }
+            PatKind::Deref { subpattern } => {
+                ctor = Single;
+                fields = singleton(self.lower_pat(subpattern));
+            }
+            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
+                match pat.ty.kind() {
+                    ty::Tuple(fs) => {
+                        ctor = Single;
+                        let mut wilds: SmallVec<[_; 2]> =
+                            fs.iter().map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
+                        for pat in subpatterns {
+                            wilds[pat.field.index()] = self.lower_pat(&pat.pattern);
+                        }
+                        fields = cx.pattern_arena.alloc_from_iter(wilds);
+                    }
+                    ty::Adt(adt, args) if adt.is_box() => {
+                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
+                        // patterns. If we're here we can assume this is a box pattern.
+                        // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_,
+                        // _)` or a box pattern. As a hack to avoid an ICE with the former, we
+                        // ignore other fields than the first one. This will trigger an error later
+                        // anyway.
+                        // See https://github.com/rust-lang/rust/issues/82772 ,
+                        // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977
+                        // The problem is that we can't know from the type whether we'll match
+                        // normally or through box-patterns. We'll have to figure out a proper
+                        // solution when we introduce generalized deref patterns. Also need to
+                        // prevent mixing of those two options.
+                        let pattern = subpatterns.into_iter().find(|pat| pat.field.index() == 0);
+                        let pat = if let Some(pat) = pattern {
+                            self.lower_pat(&pat.pattern)
+                        } else {
+                            DeconstructedPat::wildcard(args.type_at(0), pat.span)
+                        };
+                        ctor = Single;
+                        fields = singleton(pat);
+                    }
+                    ty::Adt(adt, _) => {
+                        ctor = match pat.kind {
+                            PatKind::Leaf { .. } => Single,
+                            PatKind::Variant { variant_index, .. } => Variant(variant_index),
+                            _ => bug!(),
+                        };
+                        let variant =
+                            &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt));
+                        // For each field in the variant, we store the relevant index into `self.fields` if any.
+                        let mut field_id_to_id: Vec<Option<usize>> =
+                            (0..variant.fields.len()).map(|_| None).collect();
+                        let tys = cx
+                            .list_variant_nonhidden_fields(pat.ty, variant)
+                            .enumerate()
+                            .map(|(i, (field, ty))| {
+                                field_id_to_id[field.index()] = Some(i);
+                                ty
+                            });
+                        let mut wilds: SmallVec<[_; 2]> =
+                            tys.map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
+                        for pat in subpatterns {
+                            if let Some(i) = field_id_to_id[pat.field.index()] {
+                                wilds[i] = self.lower_pat(&pat.pattern);
+                            }
+                        }
+                        fields = cx.pattern_arena.alloc_from_iter(wilds);
+                    }
+                    _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, pat.ty),
+                }
+            }
+            PatKind::Constant { value } => {
+                match pat.ty.kind() {
+                    ty::Bool => {
+                        ctor = match value.try_eval_bool(cx.tcx, cx.param_env) {
+                            Some(b) => Bool(b),
+                            None => Opaque(OpaqueId::new()),
+                        };
+                        fields = &[];
+                    }
+                    ty::Char | ty::Int(_) | ty::Uint(_) => {
+                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
+                            Some(bits) => {
+                                let x = match *pat.ty.kind() {
+                                    ty::Int(ity) => {
+                                        let size = Integer::from_int_ty(&cx.tcx, ity).size().bits();
+                                        MaybeInfiniteInt::new_finite_int(bits, size)
+                                    }
+                                    _ => MaybeInfiniteInt::new_finite_uint(bits),
+                                };
+                                IntRange(IntRange::from_singleton(x))
+                            }
+                            None => Opaque(OpaqueId::new()),
+                        };
+                        fields = &[];
+                    }
+                    ty::Float(ty::FloatTy::F32) => {
+                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
+                            Some(bits) => {
+                                use rustc_apfloat::Float;
+                                let value = rustc_apfloat::ieee::Single::from_bits(bits);
+                                F32Range(value, value, RangeEnd::Included)
+                            }
+                            None => Opaque(OpaqueId::new()),
+                        };
+                        fields = &[];
+                    }
+                    ty::Float(ty::FloatTy::F64) => {
+                        ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
+                            Some(bits) => {
+                                use rustc_apfloat::Float;
+                                let value = rustc_apfloat::ieee::Double::from_bits(bits);
+                                F64Range(value, value, RangeEnd::Included)
+                            }
+                            None => Opaque(OpaqueId::new()),
+                        };
+                        fields = &[];
+                    }
+                    ty::Ref(_, t, _) if t.is_str() => {
+                        // We want a `&str` constant to behave like a `Deref` pattern, to be compatible
+                        // with other `Deref` patterns. This could have been done in `const_to_pat`,
+                        // but that causes issues with the rest of the matching code.
+                        // So here, the constructor for a `"foo"` pattern is `&` (represented by
+                        // `Single`), and has one field. That field has constructor `Str(value)` and no
+                        // fields.
+                        // Note: `t` is `str`, not `&str`.
+                        let subpattern = DeconstructedPat::new(Str(*value), &[], *t, pat.span);
+                        ctor = Single;
+                        fields = singleton(subpattern)
+                    }
+                    // All constants that can be structurally matched have already been expanded
+                    // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are
+                    // opaque.
+                    _ => {
+                        ctor = Opaque(OpaqueId::new());
+                        fields = &[];
+                    }
+                }
+            }
+            PatKind::Range(patrange) => {
+                let PatRange { lo, hi, end, .. } = patrange.as_ref();
+                let ty = pat.ty;
+                ctor = match ty.kind() {
+                    ty::Char | ty::Int(_) | ty::Uint(_) => {
+                        let lo = cx.lower_pat_range_bdy(*lo, ty);
+                        let hi = cx.lower_pat_range_bdy(*hi, ty);
+                        IntRange(IntRange::from_range(lo, hi, *end))
+                    }
+                    ty::Float(fty) => {
+                        use rustc_apfloat::Float;
+                        let lo = lo.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
+                        let hi = hi.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
+                        match fty {
+                            ty::FloatTy::F32 => {
+                                use rustc_apfloat::ieee::Single;
+                                let lo = lo.map(Single::from_bits).unwrap_or(-Single::INFINITY);
+                                let hi = hi.map(Single::from_bits).unwrap_or(Single::INFINITY);
+                                F32Range(lo, hi, *end)
+                            }
+                            ty::FloatTy::F64 => {
+                                use rustc_apfloat::ieee::Double;
+                                let lo = lo.map(Double::from_bits).unwrap_or(-Double::INFINITY);
+                                let hi = hi.map(Double::from_bits).unwrap_or(Double::INFINITY);
+                                F64Range(lo, hi, *end)
+                            }
+                        }
+                    }
+                    _ => bug!("invalid type for range pattern: {}", ty),
+                };
+                fields = &[];
+            }
+            PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => {
+                let array_len = match pat.ty.kind() {
+                    ty::Array(_, length) => {
+                        Some(length.eval_target_usize(cx.tcx, cx.param_env) as usize)
+                    }
+                    ty::Slice(_) => None,
+                    _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty),
+                };
+                let kind = if slice.is_some() {
+                    SliceKind::VarLen(prefix.len(), suffix.len())
+                } else {
+                    SliceKind::FixedLen(prefix.len() + suffix.len())
+                };
+                ctor = Slice(Slice::new(array_len, kind));
+                fields = cx.pattern_arena.alloc_from_iter(
+                    prefix.iter().chain(suffix.iter()).map(|p| self.lower_pat(&*p)),
+                )
+            }
+            PatKind::Or { .. } => {
+                ctor = Or;
+                let pats = expand_or_pat(pat);
+                fields =
+                    cx.pattern_arena.alloc_from_iter(pats.into_iter().map(|p| self.lower_pat(p)))
+            }
+            PatKind::Never => {
+                // FIXME(never_patterns): handle `!` in exhaustiveness. This is a sane default
+                // in the meantime.
+                ctor = Wildcard;
+                fields = &[];
+            }
+            PatKind::Error(_) => {
+                ctor = Opaque(OpaqueId::new());
+                fields = &[];
+            }
+        }
+        DeconstructedPat::new(ctor, fields, pat.ty, pat.span)
+    }
+
+    /// Convert back to a `thir::PatRangeBoundary` for diagnostic purposes.
+    /// Note: it is possible to get `isize/usize::MAX+1` here, as explained in the doc for
+    /// [`IntRange::split`]. This cannot be represented as a `Const`, so we represent it with
+    /// `PosInfinity`.
+    pub(crate) fn hoist_pat_range_bdy(
+        &self,
+        miint: MaybeInfiniteInt,
+        ty: Ty<'tcx>,
+    ) -> PatRangeBoundary<'tcx> {
+        use MaybeInfiniteInt::*;
+        let tcx = self.tcx;
+        match miint {
+            NegInfinity => PatRangeBoundary::NegInfinity,
+            Finite(_) => {
+                let size = ty.primitive_size(tcx);
+                let bits = match *ty.kind() {
+                    ty::Int(_) => miint.as_finite_int(size.bits()).unwrap(),
+                    _ => miint.as_finite_uint().unwrap(),
+                };
+                match Scalar::try_from_uint(bits, size) {
+                    Some(scalar) => {
+                        let value = mir::Const::from_scalar(tcx, scalar, ty);
+                        PatRangeBoundary::Finite(value)
+                    }
+                    // The value doesn't fit. Since `x >= 0` and 0 always encodes the minimum value
+                    // for a type, the problem isn't that the value is too small. So it must be too
+                    // large.
+                    None => PatRangeBoundary::PosInfinity,
+                }
+            }
+            JustAfterMax | PosInfinity => PatRangeBoundary::PosInfinity,
+        }
+    }
+
+    /// 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::*;
+        let cx = self;
+        let kind = if matches!((range.lo, range.hi), (NegInfinity, PosInfinity)) {
+            PatKind::Wild
+        } else if range.is_singleton() {
+            let lo = cx.hoist_pat_range_bdy(range.lo, ty);
+            let value = lo.as_finite().unwrap();
+            PatKind::Constant { value }
+        } else {
+            // We convert to an inclusive range for diagnostics.
+            let mut end = RangeEnd::Included;
+            let mut lo = cx.hoist_pat_range_bdy(range.lo, ty);
+            if matches!(lo, PatRangeBoundary::PosInfinity) {
+                // The only reason to get `PosInfinity` here is the special case where
+                // `hoist_pat_range_bdy` found `{u,i}size::MAX+1`. So the range denotes the
+                // fictitious values after `{u,i}size::MAX` (see [`IntRange::split`] for why we do
+                // this). We show this to the user as `usize::MAX..` which is slightly incorrect but
+                // probably clear enough.
+                let c = ty.numeric_max_val(cx.tcx).unwrap();
+                let value = mir::Const::from_ty_const(c, cx.tcx);
+                lo = PatRangeBoundary::Finite(value);
+            }
+            let hi = if matches!(range.hi, Finite(0)) {
+                // The range encodes `..ty::MIN`, so we can't convert it to an inclusive range.
+                end = RangeEnd::Excluded;
+                range.hi
+            } else {
+                range.hi.minus_one()
+            };
+            let hi = cx.hoist_pat_range_bdy(hi, ty);
+            PatKind::Range(Box::new(PatRange { lo, hi, end, ty }))
+        };
+
+        Pat { ty, span: DUMMY_SP, kind }
+    }
+    /// 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> {
+        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)));
+        let kind = match pat.ctor() {
+            Bool(b) => PatKind::Constant { value: mir::Const::from_bool(cx.tcx, *b) },
+            IntRange(range) => return self.hoist_pat_range(range, pat.ty()),
+            Single | Variant(_) => match pat.ty().kind() {
+                ty::Tuple(..) => PatKind::Leaf {
+                    subpatterns: subpatterns
+                        .enumerate()
+                        .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern })
+                        .collect(),
+                },
+                ty::Adt(adt_def, _) if adt_def.is_box() => {
+                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
+                    // of `std`). So this branch is only reachable when the feature is enabled and
+                    // the pattern is a box pattern.
+                    PatKind::Deref { subpattern: subpatterns.next().unwrap() }
+                }
+                ty::Adt(adt_def, args) => {
+                    let variant_index =
+                        MatchCheckCtxt::variant_index_for_adt(&pat.ctor(), *adt_def);
+                    let variant = &adt_def.variant(variant_index);
+                    let subpatterns = cx
+                        .list_variant_nonhidden_fields(pat.ty(), variant)
+                        .zip(subpatterns)
+                        .map(|((field, _ty), pattern)| FieldPat { field, pattern })
+                        .collect();
+
+                    if adt_def.is_enum() {
+                        PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns }
+                    } else {
+                        PatKind::Leaf { subpatterns }
+                    }
+                }
+                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
+                // be careful to reconstruct the correct constant pattern here. However a string
+                // literal pattern will never be reported as a non-exhaustiveness witness, so we
+                // ignore this issue.
+                ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
+                _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), pat.ty()),
+            },
+            Slice(slice) => {
+                match slice.kind {
+                    SliceKind::FixedLen(_) => PatKind::Slice {
+                        prefix: subpatterns.collect(),
+                        slice: None,
+                        suffix: Box::new([]),
+                    },
+                    SliceKind::VarLen(prefix, _) => {
+                        let mut subpatterns = subpatterns.peekable();
+                        let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect();
+                        if slice.array_len.is_some() {
+                            // Improves diagnostics a bit: if the type is a known-size array, instead
+                            // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
+                            // This is incorrect if the size is not known, since `[_, ..]` captures
+                            // arrays of lengths `>= 1` whereas `[..]` captures any length.
+                            while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) {
+                                prefix.pop();
+                            }
+                            while subpatterns.peek().is_some()
+                                && is_wildcard(subpatterns.peek().unwrap())
+                            {
+                                subpatterns.next();
+                            }
+                        }
+                        let suffix: Box<[_]> = subpatterns.collect();
+                        let wild = Pat::wildcard_from_ty(pat.ty());
+                        PatKind::Slice {
+                            prefix: prefix.into_boxed_slice(),
+                            slice: Some(Box::new(wild)),
+                            suffix,
+                        }
+                    }
+                }
+            }
+            &Str(value) => PatKind::Constant { value },
+            Wildcard | NonExhaustive | Hidden => PatKind::Wild,
+            Missing { .. } => bug!(
+                "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
+                `Missing` should have been processed in `apply_constructors`"
+            ),
+            F32Range(..) | F64Range(..) | Opaque(..) | Or => {
+                bug!("can't convert to pattern: {:?}", pat)
+            }
+        };
+
+        Pat { ty: pat.ty(), span: DUMMY_SP, kind }
+    }
+
+    /// Best-effort `Debug` implementation.
+    pub(crate) fn debug_pat(
+        f: &mut fmt::Formatter<'_>,
+        pat: &DeconstructedPat<'p, 'tcx>,
+    ) -> fmt::Result {
+        let mut first = true;
+        let mut start_or_continue = |s| {
+            if first {
+                first = false;
+                ""
+            } else {
+                s
+            }
+        };
+        let mut start_or_comma = || start_or_continue(", ");
+
+        match pat.ctor() {
+            Single | Variant(_) => match pat.ty().kind() {
+                ty::Adt(def, _) if def.is_box() => {
+                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
+                    // of `std`). So this branch is only reachable when the feature is enabled and
+                    // the pattern is a box pattern.
+                    let subpattern = pat.iter_fields().next().unwrap();
+                    write!(f, "box {subpattern:?}")
+                }
+                ty::Adt(..) | ty::Tuple(..) => {
+                    let variant = match pat.ty().kind() {
+                        ty::Adt(adt, _) => Some(
+                            adt.variant(MatchCheckCtxt::variant_index_for_adt(pat.ctor(), *adt)),
+                        ),
+                        ty::Tuple(_) => None,
+                        _ => unreachable!(),
+                    };
+
+                    if let Some(variant) = variant {
+                        write!(f, "{}", variant.name)?;
+                    }
+
+                    // Without `cx`, we can't know which field corresponds to which, so we can't
+                    // get the names of the fields. Instead we just display everything as a tuple
+                    // struct, which should be good enough.
+                    write!(f, "(")?;
+                    for p in pat.iter_fields() {
+                        write!(f, "{}", start_or_comma())?;
+                        write!(f, "{p:?}")?;
+                    }
+                    write!(f, ")")
+                }
+                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
+                // be careful to detect strings here. However a string literal pattern will never
+                // be reported as a non-exhaustiveness witness, so we can ignore this issue.
+                ty::Ref(_, _, mutbl) => {
+                    let subpattern = pat.iter_fields().next().unwrap();
+                    write!(f, "&{}{:?}", mutbl.prefix_str(), subpattern)
+                }
+                _ => write!(f, "_"),
+            },
+            Slice(slice) => {
+                let mut subpatterns = pat.iter_fields();
+                write!(f, "[")?;
+                match slice.kind {
+                    SliceKind::FixedLen(_) => {
+                        for p in subpatterns {
+                            write!(f, "{}{:?}", start_or_comma(), p)?;
+                        }
+                    }
+                    SliceKind::VarLen(prefix_len, _) => {
+                        for p in subpatterns.by_ref().take(prefix_len) {
+                            write!(f, "{}{:?}", start_or_comma(), p)?;
+                        }
+                        write!(f, "{}", start_or_comma())?;
+                        write!(f, "..")?;
+                        for p in subpatterns {
+                            write!(f, "{}{:?}", start_or_comma(), p)?;
+                        }
+                    }
+                }
+                write!(f, "]")
+            }
+            Bool(b) => write!(f, "{b}"),
+            // Best-effort, will render signed ranges incorrectly
+            IntRange(range) => write!(f, "{range:?}"),
+            F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
+            F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
+            Str(value) => write!(f, "{value}"),
+            Opaque(..) => write!(f, "<constant pattern>"),
+            Or => {
+                for pat in pat.iter_fields() {
+                    write!(f, "{}{:?}", start_or_continue(" | "), pat)?;
+                }
+                Ok(())
+            }
+            Wildcard | Missing { .. } | NonExhaustive | Hidden => write!(f, "_ : {:?}", pat.ty()),
+        }
+    }
+}
+
+/// 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>>) {
+        if let PatKind::Or { pats } = &pat.kind {
+            for pat in pats.iter() {
+                expand(pat, vec);
+            }
+        } else {
+            vec.push(pat)
+        }
+    }
+
+    let mut pats = Vec::new();
+    expand(pat, &mut pats);
+    pats
+}
diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs
new file mode 100644
index 00000000000..0efa8a0ec08
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/errors.rs
@@ -0,0 +1,95 @@
+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;
+
+#[derive(Subdiagnostic)]
+#[label(pattern_analysis_uncovered)]
+pub struct Uncovered<'tcx> {
+    #[primary_span]
+    span: Span,
+    count: usize,
+    witness_1: Pat<'tcx>,
+    witness_2: Pat<'tcx>,
+    witness_3: Pat<'tcx>,
+    remainder: usize,
+}
+
+impl<'tcx> Uncovered<'tcx> {
+    pub fn new<'p>(
+        span: Span,
+        cx: &MatchCheckCtxt<'p, 'tcx>,
+        witnesses: Vec<WitnessPat<'tcx>>,
+    ) -> Self {
+        let witness_1 = cx.hoist_witness_pat(witnesses.get(0).unwrap());
+        Self {
+            span,
+            count: witnesses.len(),
+            // Substitute dummy values if witnesses is smaller than 3. These will never be read.
+            witness_2: witnesses
+                .get(1)
+                .map(|w| cx.hoist_witness_pat(w))
+                .unwrap_or_else(|| witness_1.clone()),
+            witness_3: witnesses
+                .get(2)
+                .map(|w| cx.hoist_witness_pat(w))
+                .unwrap_or_else(|| witness_1.clone()),
+            witness_1,
+            remainder: witnesses.len().saturating_sub(3),
+        }
+    }
+}
+
+#[derive(LintDiagnostic)]
+#[diag(pattern_analysis_overlapping_range_endpoints)]
+#[note]
+pub struct OverlappingRangeEndpoints<'tcx> {
+    #[label]
+    pub range: Span,
+    #[subdiagnostic]
+    pub overlap: Vec<Overlap<'tcx>>,
+}
+
+pub struct Overlap<'tcx> {
+    pub span: Span,
+    pub range: Pat<'tcx>,
+}
+
+impl<'tcx> AddToDiagnostic for Overlap<'tcx> {
+    fn add_to_diagnostic_with<F>(self, diag: &mut Diagnostic, _: F)
+    where
+        F: Fn(&mut Diagnostic, SubdiagnosticMessage) -> SubdiagnosticMessage,
+    {
+        let Overlap { span, range } = self;
+
+        // FIXME(mejrs) unfortunately `#[derive(LintDiagnostic)]`
+        // does not support `#[subdiagnostic(eager)]`...
+        let message = format!("this range overlaps on `{range}`...");
+        diag.span_label(span, message);
+    }
+}
+
+#[derive(LintDiagnostic)]
+#[diag(pattern_analysis_non_exhaustive_omitted_pattern)]
+#[help]
+#[note]
+pub(crate) struct NonExhaustiveOmittedPattern<'tcx> {
+    pub scrut_ty: Ty<'tcx>,
+    #[subdiagnostic]
+    pub uncovered: Uncovered<'tcx>,
+}
+
+#[derive(LintDiagnostic)]
+#[diag(pattern_analysis_non_exhaustive_omitted_pattern_lint_on_arm)]
+#[help]
+pub(crate) struct NonExhaustiveOmittedPatternLintOnArm {
+    #[label]
+    pub lint_span: Span,
+    #[suggestion(code = "#[{lint_level}({lint_name})]\n", applicability = "maybe-incorrect")]
+    pub suggest_lint_on_match: Option<Span>,
+    pub lint_level: &'static str,
+    pub lint_name: &'static str,
+}
diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs
new file mode 100644
index 00000000000..07730aa49d3
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/lib.rs
@@ -0,0 +1,56 @@
+//! Analysis of patterns, notably match exhaustiveness checking.
+
+pub mod constructor;
+pub mod cx;
+pub mod errors;
+pub(crate) mod lints;
+pub mod pat;
+pub mod usefulness;
+
+#[macro_use]
+extern crate tracing;
+#[macro_use]
+extern crate rustc_middle;
+
+rustc_fluent_macro::fluent_messages! { "../messages.ftl" }
+
+use lints::PatternColumn;
+use rustc_hir::HirId;
+use rustc_middle::ty::Ty;
+use usefulness::{compute_match_usefulness, UsefulnessReport};
+
+use crate::cx::MatchCheckCtxt;
+use crate::lints::{lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints};
+use crate::pat::DeconstructedPat;
+
+/// The arm of a match expression.
+#[derive(Clone, Copy, Debug)]
+pub struct MatchArm<'p, 'tcx> {
+    /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
+    pub pat: &'p DeconstructedPat<'p, 'tcx>,
+    pub hir_id: HirId,
+    pub has_guard: bool,
+}
+
+/// 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>],
+    scrut_ty: Ty<'tcx>,
+) -> UsefulnessReport<'p, 'tcx> {
+    let pat_column = PatternColumn::new(arms);
+
+    let report = compute_match_usefulness(cx, arms, scrut_ty);
+
+    // Lint on ranges that overlap on their endpoints, which is likely a mistake.
+    lint_overlapping_range_endpoints(cx, &pat_column);
+
+    // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting
+    // `if let`s. Only run if the match is exhaustive otherwise the error is redundant.
+    if cx.refutable && report.non_exhaustiveness_witnesses.is_empty() {
+        lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty)
+    }
+
+    report
+}
diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs
new file mode 100644
index 00000000000..8ab559c9e7a
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/lints.rs
@@ -0,0 +1,290 @@
+use smallvec::SmallVec;
+
+use rustc_data_structures::captures::Captures;
+use rustc_middle::ty::{self, Ty};
+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::errors::{
+    NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap,
+    OverlappingRangeEndpoints, Uncovered,
+};
+use crate::pat::{DeconstructedPat, WitnessPat};
+use crate::usefulness::PatCtxt;
+use crate::MatchArm;
+
+/// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that
+/// inspect the same subvalue/place".
+/// This is used to traverse patterns column-by-column for lints. Despite similarities with the
+/// algorithm in [`crate::usefulness`], this does a different traversal. Notably this is linear in
+/// the depth of patterns, whereas `compute_exhaustiveness_and_usefulness` is worst-case exponential
+/// (exhaustiveness is NP-complete). The core difference is that we treat sub-columns separately.
+///
+/// This must not contain an or-pattern. `specialize` takes care to expand them.
+///
+/// This is not used in the main algorithm; only in lints.
+#[derive(Debug)]
+pub(crate) struct PatternColumn<'p, 'tcx> {
+    patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>,
+}
+
+impl<'p, 'tcx> PatternColumn<'p, 'tcx> {
+    pub(crate) fn new(arms: &[MatchArm<'p, 'tcx>]) -> Self {
+        let mut patterns = Vec::with_capacity(arms.len());
+        for arm in arms {
+            if arm.pat.is_or_pat() {
+                patterns.extend(arm.pat.flatten_or_pat())
+            } else {
+                patterns.push(arm.pat)
+            }
+        }
+        Self { patterns }
+    }
+
+    fn is_empty(&self) -> bool {
+        self.patterns.is_empty()
+    }
+    fn head_ty(&self) -> Option<Ty<'tcx>> {
+        if self.patterns.len() == 0 {
+            return None;
+        }
+        // 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, ..));
+        let first_ty = self.patterns[0].ty();
+        if is_opaque(first_ty) {
+            for pat in &self.patterns {
+                let ty = pat.ty();
+                if !is_opaque(ty) {
+                    return Some(ty);
+                }
+            }
+        }
+        Some(first_ty)
+    }
+
+    /// Do constructor splitting on the constructors of the column.
+    fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> {
+        let column_ctors = self.patterns.iter().map(|p| p.ctor());
+        pcx.cx.ctors_for_ty(pcx.ty).split(pcx, column_ctors)
+    }
+
+    fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
+        self.patterns.iter().copied()
+    }
+
+    /// Does specialization: given a constructor, this takes the patterns from the column that match
+    /// the constructor, and outputs their fields.
+    /// This returns one column per field of the constructor. They usually all have the same length
+    /// (the number of patterns in `self` that matched `ctor`), except that we expand or-patterns
+    /// which may change the lengths.
+    fn specialize(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Vec<Self> {
+        let arity = ctor.arity(pcx);
+        if arity == 0 {
+            return Vec::new();
+        }
+
+        // We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These
+        // columns may have different lengths in the presence of or-patterns (this is why we can't
+        // reuse `Matrix`).
+        let mut specialized_columns: Vec<_> =
+            (0..arity).map(|_| Self { patterns: Vec::new() }).collect();
+        let relevant_patterns =
+            self.patterns.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor()));
+        for pat in relevant_patterns {
+            let specialized = pat.specialize(pcx, ctor);
+            for (subpat, column) in specialized.iter().zip(&mut specialized_columns) {
+                if subpat.is_or_pat() {
+                    column.patterns.extend(subpat.flatten_or_pat())
+                } else {
+                    column.patterns.push(subpat)
+                }
+            }
+        }
+
+        assert!(
+            !specialized_columns[0].is_empty(),
+            "ctor {ctor:?} was listed as present but isn't;
+            there is an inconsistency between `Constructor::is_covered_by` and `ConstructorSet::split`"
+        );
+        specialized_columns
+    }
+}
+
+/// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned
+/// in a given column.
+#[instrument(level = "debug", skip(cx), ret)]
+fn collect_nonexhaustive_missing_variants<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    column: &PatternColumn<'p, 'tcx>,
+) -> Vec<WitnessPat<'tcx>> {
+    let Some(ty) = column.head_ty() else {
+        return Vec::new();
+    };
+    let pcx = &PatCtxt::new_dummy(cx, ty);
+
+    let set = column.analyze_ctors(pcx);
+    if set.present.is_empty() {
+        // We can't consistently handle the case where no constructors are present (since this would
+        // require digging deep through any type in case there's a non_exhaustive enum somewhere),
+        // so for consistency we refuse to handle the top-level case, where we could handle it.
+        return vec![];
+    }
+
+    let mut witnesses = Vec::new();
+    if cx.is_foreign_non_exhaustive_enum(ty) {
+        witnesses.extend(
+            set.missing
+                .into_iter()
+                // This will list missing visible variants.
+                .filter(|c| !matches!(c, Constructor::Hidden | Constructor::NonExhaustive))
+                .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor)),
+        )
+    }
+
+    // Recurse into the fields.
+    for ctor in set.present {
+        let specialized_columns = column.specialize(pcx, &ctor);
+        let wild_pat = WitnessPat::wild_from_ctor(pcx, ctor);
+        for (i, col_i) in specialized_columns.iter().enumerate() {
+            // Compute witnesses for each column.
+            let wits_for_col_i = collect_nonexhaustive_missing_variants(cx, col_i);
+            // For each witness, we build a new pattern in the shape of `ctor(_, _, wit, _, _)`,
+            // adding enough wildcards to match `arity`.
+            for wit in wits_for_col_i {
+                let mut pat = wild_pat.clone();
+                pat.fields[i] = wit;
+                witnesses.push(pat);
+            }
+        }
+    }
+    witnesses
+}
+
+pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    arms: &[MatchArm<'p, 'tcx>],
+    pat_column: &PatternColumn<'p, 'tcx>,
+    scrut_ty: Ty<'tcx>,
+) {
+    if !matches!(
+        cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, cx.match_lint_level).0,
+        rustc_session::lint::Level::Allow
+    ) {
+        let witnesses = collect_nonexhaustive_missing_variants(cx, pat_column);
+        if !witnesses.is_empty() {
+            // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
+            // is not exhaustive enough.
+            //
+            // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`.
+            cx.tcx.emit_spanned_lint(
+                NON_EXHAUSTIVE_OMITTED_PATTERNS,
+                cx.match_lint_level,
+                cx.scrut_span,
+                NonExhaustiveOmittedPattern {
+                    scrut_ty,
+                    uncovered: Uncovered::new(cx.scrut_span, cx, witnesses),
+                },
+            );
+        }
+    } else {
+        // We used to allow putting the `#[allow(non_exhaustive_omitted_patterns)]` on a match
+        // arm. This no longer makes sense so we warn users, to avoid silently breaking their
+        // usage of the lint.
+        for arm in arms {
+            let (lint_level, lint_level_source) =
+                cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, arm.hir_id);
+            if !matches!(lint_level, rustc_session::lint::Level::Allow) {
+                let decorator = NonExhaustiveOmittedPatternLintOnArm {
+                    lint_span: lint_level_source.span(),
+                    suggest_lint_on_match: cx.whole_match_span.map(|span| span.shrink_to_lo()),
+                    lint_level: lint_level.as_str(),
+                    lint_name: "non_exhaustive_omitted_patterns",
+                };
+
+                use rustc_errors::DecorateLint;
+                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();
+            }
+        }
+    }
+}
+
+/// Traverse the patterns to warn the user about ranges that overlap on their endpoints.
+#[instrument(level = "debug", skip(cx))]
+pub(crate) fn lint_overlapping_range_endpoints<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    column: &PatternColumn<'p, 'tcx>,
+) {
+    let Some(ty) = column.head_ty() else {
+        return;
+    };
+    let pcx = &PatCtxt::new_dummy(cx, ty);
+
+    let set = column.analyze_ctors(pcx);
+
+    if matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_)) {
+        let emit_lint = |overlap: &IntRange, this_span: Span, overlapped_spans: &[Span]| {
+            let overlap_as_pat = cx.hoist_pat_range(overlap, ty);
+            let overlaps: Vec<_> = overlapped_spans
+                .iter()
+                .copied()
+                .map(|span| Overlap { range: overlap_as_pat.clone(), span })
+                .collect();
+            cx.tcx.emit_spanned_lint(
+                lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
+                cx.match_lint_level,
+                this_span,
+                OverlappingRangeEndpoints { overlap: overlaps, range: this_span },
+            );
+        };
+
+        // If two ranges overlapped, the split set will contain their intersection as a singleton.
+        let split_int_ranges = set.present.iter().filter_map(|c| c.as_int_range());
+        for overlap_range in split_int_ranges.clone() {
+            if overlap_range.is_singleton() {
+                let overlap: MaybeInfiniteInt = overlap_range.lo;
+                // Ranges that look like `lo..=overlap`.
+                let mut prefixes: SmallVec<[_; 1]> = Default::default();
+                // Ranges that look like `overlap..=hi`.
+                let mut suffixes: SmallVec<[_; 1]> = Default::default();
+                // Iterate on patterns that contained `overlap`.
+                for pat in column.iter() {
+                    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.
+                        continue;
+                    }
+                    if this_range.lo == overlap {
+                        // `this_range` looks like `overlap..=this_range.hi`; it overlaps with any
+                        // ranges that look like `lo..=overlap`.
+                        if !prefixes.is_empty() {
+                            emit_lint(overlap_range, this_span, &prefixes);
+                        }
+                        suffixes.push(this_span)
+                    } else if this_range.hi == overlap.plus_one() {
+                        // `this_range` looks like `this_range.lo..=overlap`; it overlaps with any
+                        // ranges that look like `overlap..=hi`.
+                        if !suffixes.is_empty() {
+                            emit_lint(overlap_range, this_span, &suffixes);
+                        }
+                        prefixes.push(this_span)
+                    }
+                }
+            }
+        }
+    } else {
+        // Recurse into the fields.
+        for ctor in set.present {
+            for col in column.specialize(pcx, &ctor) {
+                lint_overlapping_range_endpoints(cx, &col);
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs
new file mode 100644
index 00000000000..404651124ad
--- /dev/null
+++ b/compiler/rustc_pattern_analysis/src/pat.rs
@@ -0,0 +1,205 @@
+//! As explained in [`crate::usefulness`], values and patterns are made from constructors applied to
+//! fields. This file defines types that represent patterns in this way.
+use std::cell::Cell;
+use std::fmt;
+
+use smallvec::{smallvec, SmallVec};
+
+use rustc_data_structures::captures::Captures;
+use rustc_middle::ty::{self, Ty};
+use rustc_span::{Span, DUMMY_SP};
+
+use self::Constructor::*;
+use self::SliceKind::*;
+
+use crate::constructor::{Constructor, SliceKind};
+use crate::cx::MatchCheckCtxt;
+use crate::usefulness::PatCtxt;
+
+/// Values and patterns can be represented as a constructor applied to some fields. This represents
+/// a pattern in this form.
+/// This also uses interior mutability to keep track of whether the pattern has been found reachable
+/// during analysis. For this reason they cannot be cloned.
+/// A `DeconstructedPat` will almost always come from user input; the only exception are some
+/// `Wildcard`s introduced during specialization.
+///
+/// Note that the number of fields may not match the fields declared in the original struct/variant.
+/// 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,
+    /// 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 {
+        Self::new(Wildcard, &[], ty, span)
+    }
+
+    pub fn new(
+        ctor: Constructor<'tcx>,
+        fields: &'p [DeconstructedPat<'p, 'tcx>],
+        ty: Ty<'tcx>,
+        span: Span,
+    ) -> Self {
+        DeconstructedPat { ctor, fields, ty, span, useful: Cell::new(false) }
+    }
+
+    pub(crate) fn is_or_pat(&self) -> bool {
+        matches!(self.ctor, Or)
+    }
+    /// Expand this (possibly-nested) or-pattern into its alternatives.
+    pub(crate) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> {
+        if self.is_or_pat() {
+            self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect()
+        } else {
+            smallvec![self]
+        }
+    }
+
+    pub fn ctor(&self) -> &Constructor<'tcx> {
+        &self.ctor
+    }
+    pub fn ty(&self) -> Ty<'tcx> {
+        self.ty
+    }
+    pub fn span(&self) -> Span {
+        self.span
+    }
+
+    pub fn iter_fields<'a>(
+        &'a self,
+    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
+        self.fields.iter()
+    }
+
+    /// Specialize this pattern with a constructor.
+    /// `other_ctor` can be different from `self.ctor`, but must be covered by it.
+    pub(crate) fn specialize<'a>(
+        &'a self,
+        pcx: &PatCtxt<'_, 'p, 'tcx>,
+        other_ctor: &Constructor<'tcx>,
+    ) -> SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]> {
+        match (&self.ctor, other_ctor) {
+            (Wildcard, _) => {
+                // We return a wildcard for each field of `other_ctor`.
+                pcx.cx.ctor_wildcard_fields(other_ctor, pcx.ty).iter().collect()
+            }
+            (Slice(self_slice), Slice(other_slice))
+                if self_slice.arity() != other_slice.arity() =>
+            {
+                // The only tricky case: two slices of different arity. Since `self_slice` covers
+                // `other_slice`, `self_slice` must be `VarLen`, i.e. of the form
+                // `[prefix, .., suffix]`. Moreover `other_slice` is guaranteed to have a larger
+                // arity. So we fill the middle part with enough wildcards to reach the length of
+                // the new, larger slice.
+                match self_slice.kind {
+                    FixedLen(_) => bug!("{:?} doesn't cover {:?}", self_slice, other_slice),
+                    VarLen(prefix, suffix) => {
+                        let (ty::Slice(inner_ty) | ty::Array(inner_ty, _)) = *self.ty.kind() else {
+                            bug!("bad slice pattern {:?} {:?}", self.ctor, self.ty);
+                        };
+                        let prefix = &self.fields[..prefix];
+                        let suffix = &self.fields[self_slice.arity() - suffix..];
+                        let wildcard: &_ = pcx
+                            .cx
+                            .pattern_arena
+                            .alloc(DeconstructedPat::wildcard(inner_ty, DUMMY_SP));
+                        let extra_wildcards = other_slice.arity() - self_slice.arity();
+                        let extra_wildcards = (0..extra_wildcards).map(|_| wildcard);
+                        prefix.iter().chain(extra_wildcards).chain(suffix).collect()
+                    }
+                }
+            }
+            _ => self.fields.iter().collect(),
+        }
+    }
+
+    /// We keep track for each pattern if it was ever useful during the analysis. This is used
+    /// with `redundant_spans` to report redundant subpatterns arising from or patterns.
+    pub(crate) fn set_useful(&self) {
+        self.useful.set(true)
+    }
+    pub(crate) fn is_useful(&self) -> bool {
+        if self.useful.get() {
+            true
+        } else if self.is_or_pat() && self.iter_fields().any(|f| f.is_useful()) {
+            // We always expand or patterns in the matrix, so we will never see the actual
+            // or-pattern (the one with constructor `Or`) in the column. As such, it will not be
+            // marked as useful itself, only its children will. We recover this information here.
+            self.set_useful();
+            true
+        } else {
+            false
+        }
+    }
+
+    /// Report the spans of subpatterns that were not useful, if any.
+    pub(crate) fn redundant_spans(&self) -> Vec<Span> {
+        let mut spans = Vec::new();
+        self.collect_redundant_spans(&mut spans);
+        spans
+    }
+    fn collect_redundant_spans(&self, spans: &mut Vec<Span>) {
+        // We don't look at subpatterns if we already reported the whole pattern as redundant.
+        if !self.is_useful() {
+            spans.push(self.span);
+        } else {
+            for p in self.iter_fields() {
+                p.collect_redundant_spans(spans);
+            }
+        }
+    }
+}
+
+/// 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> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        MatchCheckCtxt::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>,
+}
+
+impl<'tcx> WitnessPat<'tcx> {
+    pub(crate) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self {
+        Self { ctor, fields, ty }
+    }
+    pub(crate) fn wildcard(ty: Ty<'tcx>) -> 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 {
+        let field_tys =
+            pcx.cx.ctor_wildcard_fields(&ctor, pcx.ty).iter().map(|deco_pat| deco_pat.ty());
+        let fields = field_tys.map(|ty| Self::wildcard(ty)).collect();
+        Self::new(ctor, fields, pcx.ty)
+    }
+
+    pub fn ctor(&self) -> &Constructor<'tcx> {
+        &self.ctor
+    }
+    pub fn ty(&self) -> Ty<'tcx> {
+        self.ty
+    }
+
+    pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> {
+        self.fields.iter()
+    }
+}
diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index 637cc38be2c..f268a551547 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -97,8 +97,9 @@
 //! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths)
 //! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)`
 //!
-//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`]
-//! module. The question of whether a constructor is matched by another one is answered by
+//! Constructors and relevant operations are defined in the [`crate::constructor`] module. A
+//! representation of patterns that uses constructors is available in [`crate::pat`]. The question
+//! of whether a constructor is matched by another one is answered by
 //! [`Constructor::is_covered_by`].
 //!
 //! Note 1: variable bindings (like the `x` in `Some(x)`) match anything, so we treat them as wildcards.
@@ -241,8 +242,8 @@
 //! 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 [`ConstructorSet::for_ty`]. See the
-//! following sections for more accurate versions of the algorithm and corresponding links.
+//! Computing the set of constructors for a type is done in [`MatchCheckCtxt::ctors_for_ty`]. See
+//! the following sections for more accurate versions of the algorithm and corresponding links.
 //!
 //!
 //!
@@ -295,7 +296,7 @@
 //! the same reasoning, we only need to try two cases: `North`, and "everything else".
 //!
 //! We call _constructor splitting_ the operation that computes such a minimal set of cases to try.
-//! This is done in [`ConstructorSet::split`] and explained in [`super::deconstruct_pat`].
+//! This is done in [`ConstructorSet::split`] and explained in [`crate::constructor`].
 //!
 //!
 //!
@@ -551,82 +552,33 @@
 //! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
 //! reason not to, for example if they crucially depend on a particular feature like `or_patterns`.
 
-use self::ValidityConstraint::*;
-use super::deconstruct_pat::{
-    Constructor, ConstructorSet, DeconstructedPat, IntRange, MaybeInfiniteInt, SplitConstructorSet,
-    WitnessPat,
-};
-use crate::errors::{
-    NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap,
-    OverlappingRangeEndpoints, Uncovered,
-};
-
-use rustc_data_structures::captures::Captures;
-
-use rustc_arena::TypedArena;
-use rustc_data_structures::stack::ensure_sufficient_stack;
-use rustc_hir::def_id::DefId;
-use rustc_hir::HirId;
-use rustc_middle::ty::{self, Ty, TyCtxt};
-use rustc_session::lint;
-use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS;
-use rustc_span::{Span, DUMMY_SP};
-
 use smallvec::{smallvec, SmallVec};
 use std::fmt;
 
-pub(crate) struct MatchCheckCtxt<'p, 'tcx> {
-    pub(crate) tcx: TyCtxt<'tcx>,
-    /// The module in which the match occurs. This is necessary for
-    /// checking inhabited-ness of types because whether a type is (visibly)
-    /// inhabited can depend on whether it was defined in the current module or
-    /// not. E.g., `struct Foo { _private: ! }` cannot be seen to be empty
-    /// outside its module and should not be matchable with an empty match statement.
-    pub(crate) module: DefId,
-    pub(crate) param_env: ty::ParamEnv<'tcx>,
-    pub(crate) pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
-    /// Lint level at the match.
-    pub(crate) match_lint_level: HirId,
-    /// The span of the whole match, if applicable.
-    pub(crate) whole_match_span: Option<Span>,
-    /// Span of the scrutinee.
-    pub(crate) scrut_span: Span,
-    /// Only produce `NON_EXHAUSTIVE_OMITTED_PATTERNS` lint on refutable patterns.
-    pub(crate) refutable: bool,
-    /// Whether the data at the scrutinee is known to be valid. This is false if the scrutinee comes
-    /// from a union field, a pointer deref, or a reference deref (pending opsem decisions).
-    pub(crate) known_valid_scrutinee: bool,
-}
+use rustc_data_structures::{captures::Captures, stack::ensure_sufficient_stack};
+use rustc_middle::ty::{self, Ty};
+use rustc_span::{Span, DUMMY_SP};
 
-impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
-    pub(super) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
-        !ty.is_inhabited_from(self.tcx, self.module, self.param_env)
-    }
+use crate::constructor::{Constructor, ConstructorSet};
+use crate::cx::MatchCheckCtxt;
+use crate::pat::{DeconstructedPat, WitnessPat};
+use crate::MatchArm;
 
-    /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
-    pub(super) fn is_foreign_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool {
-        match ty.kind() {
-            ty::Adt(def, ..) => {
-                def.is_enum() && def.is_variant_list_non_exhaustive() && !def.did().is_local()
-            }
-            _ => false,
-        }
-    }
-}
+use self::ValidityConstraint::*;
 
 #[derive(Copy, Clone)]
-pub(super) struct PatCtxt<'a, 'p, 'tcx> {
-    pub(super) cx: &'a MatchCheckCtxt<'p, 'tcx>,
+pub(crate) struct PatCtxt<'a, 'p, 'tcx> {
+    pub(crate) cx: &'a MatchCheckCtxt<'p, 'tcx>,
     /// Type of the current column under investigation.
-    pub(super) ty: Ty<'tcx>,
+    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(super) is_top_level: bool,
+    pub(crate) is_top_level: bool,
 }
 
 impl<'a, 'p, 'tcx> PatCtxt<'a, 'p, 'tcx> {
     /// A `PatCtxt` when code other than `is_useful` needs one.
-    fn new_dummy(cx: &'a MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
+    pub(crate) fn new_dummy(cx: &'a MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
         PatCtxt { cx, ty, is_top_level: false }
     }
 }
@@ -643,7 +595,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)]
-pub(super) enum ValidityConstraint {
+enum ValidityConstraint {
     ValidOnly,
     MaybeInvalid,
     /// Option for backwards compatibility: the place is not known to be valid but we allow omitting
@@ -652,7 +604,7 @@ pub(super) enum ValidityConstraint {
 }
 
 impl ValidityConstraint {
-    pub(super) fn from_bool(is_valid_only: bool) -> Self {
+    fn from_bool(is_valid_only: bool) -> Self {
         if is_valid_only { ValidOnly } else { MaybeInvalid }
     }
 
@@ -664,10 +616,10 @@ impl ValidityConstraint {
         }
     }
 
-    pub(super) fn is_known_valid(self) -> bool {
+    fn is_known_valid(self) -> bool {
         matches!(self, ValidOnly)
     }
-    pub(super) fn allows_omitting_empty_arms(self) -> bool {
+    fn allows_omitting_empty_arms(self) -> bool {
         matches!(self, ValidOnly | MaybeInvalidButAllowOmittingArms)
     }
 
@@ -677,11 +629,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`.
-    pub(super) fn specialize<'tcx>(
-        self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        ctor: &Constructor<'tcx>,
-    ) -> Self {
+    fn specialize<'tcx>(self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) -> 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(..))
@@ -1072,7 +1020,7 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
 ///
 /// See the top of the file for more detailed explanations and examples.
 #[derive(Debug, Clone)]
-pub(crate) struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>);
+struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>);
 
 impl<'tcx> WitnessStack<'tcx> {
     /// Asserts that the witness contains a single pattern, and returns it.
@@ -1119,7 +1067,7 @@ 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)]
-pub struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>);
+struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>);
 
 impl<'tcx> WitnessMatrix<'tcx> {
     /// New matrix with no witnesses.
@@ -1246,7 +1194,9 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
 
     // Analyze the constructors present in this column.
     let ctors = matrix.heads().map(|p| p.ctor());
-    let split_set = ConstructorSet::for_ty(cx, ty).split(pcx, ctors);
+    let ctors_for_ty = &cx.ctors_for_ty(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();
 
     // Build the set of constructors we will specialize with. It must cover the whole type.
@@ -1261,7 +1211,7 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
     }
 
     // Decide what constructors to report.
-    let always_report_all = is_top_level && !IntRange::is_integral(pcx.ty);
+    let always_report_all = is_top_level && !is_integers;
     // Whether we should report "Enum::A and Enum::C are missing" or "_ is missing".
     let report_individual_missing_ctors = always_report_all || !all_missing;
     // Which constructors are considered missing. We ensure that `!missing_ctors.is_empty() =>
@@ -1318,233 +1268,9 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>(
     ret
 }
 
-/// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that
-/// inspect the same subvalue/place".
-/// This is used to traverse patterns column-by-column for lints. Despite similarities with
-/// [`compute_exhaustiveness_and_usefulness`], this does a different traversal. Notably this is
-/// linear in the depth of patterns, whereas `compute_exhaustiveness_and_usefulness` is worst-case
-/// exponential (exhaustiveness is NP-complete). The core difference is that we treat sub-columns
-/// separately.
-///
-/// This must not contain an or-pattern. `specialize` takes care to expand them.
-///
-/// This is not used in the main algorithm; only in lints.
-#[derive(Debug)]
-struct PatternColumn<'p, 'tcx> {
-    patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>,
-}
-
-impl<'p, 'tcx> PatternColumn<'p, 'tcx> {
-    fn new(patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>) -> Self {
-        Self { patterns }
-    }
-
-    fn is_empty(&self) -> bool {
-        self.patterns.is_empty()
-    }
-    fn head_ty(&self) -> Option<Ty<'tcx>> {
-        if self.patterns.len() == 0 {
-            return None;
-        }
-        // 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, ..));
-        let first_ty = self.patterns[0].ty();
-        if is_opaque(first_ty) {
-            for pat in &self.patterns {
-                let ty = pat.ty();
-                if !is_opaque(ty) {
-                    return Some(ty);
-                }
-            }
-        }
-        Some(first_ty)
-    }
-
-    /// Do constructor splitting on the constructors of the column.
-    fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> {
-        let column_ctors = self.patterns.iter().map(|p| p.ctor());
-        ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, column_ctors)
-    }
-
-    fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
-        self.patterns.iter().copied()
-    }
-
-    /// Does specialization: given a constructor, this takes the patterns from the column that match
-    /// the constructor, and outputs their fields.
-    /// This returns one column per field of the constructor. They usually all have the same length
-    /// (the number of patterns in `self` that matched `ctor`), except that we expand or-patterns
-    /// which may change the lengths.
-    fn specialize(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Vec<Self> {
-        let arity = ctor.arity(pcx);
-        if arity == 0 {
-            return Vec::new();
-        }
-
-        // We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These
-        // columns may have different lengths in the presence of or-patterns (this is why we can't
-        // reuse `Matrix`).
-        let mut specialized_columns: Vec<_> =
-            (0..arity).map(|_| Self { patterns: Vec::new() }).collect();
-        let relevant_patterns =
-            self.patterns.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor()));
-        for pat in relevant_patterns {
-            let specialized = pat.specialize(pcx, ctor);
-            for (subpat, column) in specialized.iter().zip(&mut specialized_columns) {
-                if subpat.is_or_pat() {
-                    column.patterns.extend(subpat.flatten_or_pat())
-                } else {
-                    column.patterns.push(subpat)
-                }
-            }
-        }
-
-        assert!(
-            !specialized_columns[0].is_empty(),
-            "ctor {ctor:?} was listed as present but isn't;
-            there is an inconsistency between `Constructor::is_covered_by` and `ConstructorSet::split`"
-        );
-        specialized_columns
-    }
-}
-
-/// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned
-/// in a given column.
-#[instrument(level = "debug", skip(cx), ret)]
-fn collect_nonexhaustive_missing_variants<'p, 'tcx>(
-    cx: &MatchCheckCtxt<'p, 'tcx>,
-    column: &PatternColumn<'p, 'tcx>,
-) -> Vec<WitnessPat<'tcx>> {
-    let Some(ty) = column.head_ty() else {
-        return Vec::new();
-    };
-    let pcx = &PatCtxt::new_dummy(cx, ty);
-
-    let set = column.analyze_ctors(pcx);
-    if set.present.is_empty() {
-        // We can't consistently handle the case where no constructors are present (since this would
-        // require digging deep through any type in case there's a non_exhaustive enum somewhere),
-        // so for consistency we refuse to handle the top-level case, where we could handle it.
-        return vec![];
-    }
-
-    let mut witnesses = Vec::new();
-    if cx.is_foreign_non_exhaustive_enum(ty) {
-        witnesses.extend(
-            set.missing
-                .into_iter()
-                // This will list missing visible variants.
-                .filter(|c| !matches!(c, Constructor::Hidden | Constructor::NonExhaustive))
-                .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor)),
-        )
-    }
-
-    // Recurse into the fields.
-    for ctor in set.present {
-        let specialized_columns = column.specialize(pcx, &ctor);
-        let wild_pat = WitnessPat::wild_from_ctor(pcx, ctor);
-        for (i, col_i) in specialized_columns.iter().enumerate() {
-            // Compute witnesses for each column.
-            let wits_for_col_i = collect_nonexhaustive_missing_variants(cx, col_i);
-            // For each witness, we build a new pattern in the shape of `ctor(_, _, wit, _, _)`,
-            // adding enough wildcards to match `arity`.
-            for wit in wits_for_col_i {
-                let mut pat = wild_pat.clone();
-                pat.fields[i] = wit;
-                witnesses.push(pat);
-            }
-        }
-    }
-    witnesses
-}
-
-/// Traverse the patterns to warn the user about ranges that overlap on their endpoints.
-#[instrument(level = "debug", skip(cx))]
-fn lint_overlapping_range_endpoints<'p, 'tcx>(
-    cx: &MatchCheckCtxt<'p, 'tcx>,
-    column: &PatternColumn<'p, 'tcx>,
-) {
-    let Some(ty) = column.head_ty() else {
-        return;
-    };
-    let pcx = &PatCtxt::new_dummy(cx, ty);
-
-    let set = column.analyze_ctors(pcx);
-
-    if IntRange::is_integral(ty) {
-        let emit_lint = |overlap: &IntRange, this_span: Span, overlapped_spans: &[Span]| {
-            let overlap_as_pat = overlap.to_diagnostic_pat(ty, cx.tcx);
-            let overlaps: Vec<_> = overlapped_spans
-                .iter()
-                .copied()
-                .map(|span| Overlap { range: overlap_as_pat.clone(), span })
-                .collect();
-            cx.tcx.emit_spanned_lint(
-                lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
-                cx.match_lint_level,
-                this_span,
-                OverlappingRangeEndpoints { overlap: overlaps, range: this_span },
-            );
-        };
-
-        // If two ranges overlapped, the split set will contain their intersection as a singleton.
-        let split_int_ranges = set.present.iter().filter_map(|c| c.as_int_range());
-        for overlap_range in split_int_ranges.clone() {
-            if overlap_range.is_singleton() {
-                let overlap: MaybeInfiniteInt = overlap_range.lo;
-                // Ranges that look like `lo..=overlap`.
-                let mut prefixes: SmallVec<[_; 1]> = Default::default();
-                // Ranges that look like `overlap..=hi`.
-                let mut suffixes: SmallVec<[_; 1]> = Default::default();
-                // Iterate on patterns that contained `overlap`.
-                for pat in column.iter() {
-                    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.
-                        continue;
-                    }
-                    if this_range.lo == overlap {
-                        // `this_range` looks like `overlap..=this_range.hi`; it overlaps with any
-                        // ranges that look like `lo..=overlap`.
-                        if !prefixes.is_empty() {
-                            emit_lint(overlap_range, this_span, &prefixes);
-                        }
-                        suffixes.push(this_span)
-                    } else if this_range.hi == overlap.plus_one() {
-                        // `this_range` looks like `this_range.lo..=overlap`; it overlaps with any
-                        // ranges that look like `overlap..=hi`.
-                        if !suffixes.is_empty() {
-                            emit_lint(overlap_range, this_span, &suffixes);
-                        }
-                        prefixes.push(this_span)
-                    }
-                }
-            }
-        }
-    } else {
-        // Recurse into the fields.
-        for ctor in set.present {
-            for col in column.specialize(pcx, &ctor) {
-                lint_overlapping_range_endpoints(cx, &col);
-            }
-        }
-    }
-}
-
-/// The arm of a match expression.
-#[derive(Clone, Copy, Debug)]
-pub(crate) struct MatchArm<'p, 'tcx> {
-    /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
-    pub(crate) pat: &'p DeconstructedPat<'p, 'tcx>,
-    pub(crate) hir_id: HirId,
-    pub(crate) has_guard: bool,
-}
-
 /// Indicates whether or not a given arm is useful.
 #[derive(Clone, Debug)]
-pub(crate) enum Usefulness {
+pub enum Usefulness {
     /// 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.
@@ -1555,16 +1281,15 @@ pub(crate) enum Usefulness {
 }
 
 /// The output of checking a match for exhaustiveness and arm usefulness.
-pub(crate) struct UsefulnessReport<'p, 'tcx> {
+pub struct UsefulnessReport<'p, 'tcx> {
     /// For each arm of the input, whether that arm is useful after the arms above it.
-    pub(crate) arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Usefulness)>,
+    pub arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Usefulness)>,
     /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
     /// exhaustiveness.
-    pub(crate) non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>,
+    pub non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>,
 }
 
-/// The entrypoint for this file. Computes whether a match is exhaustive and which of its arms are
-/// useful.
+/// 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>,
@@ -1590,59 +1315,5 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
             (arm, usefulness)
         })
         .collect();
-    let report = UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses };
-
-    let pat_column = PatternColumn::new(matrix.heads().collect());
-    // Lint on ranges that overlap on their endpoints, which is likely a mistake.
-    lint_overlapping_range_endpoints(cx, &pat_column);
-
-    // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting
-    // `if let`s. Only run if the match is exhaustive otherwise the error is redundant.
-    if cx.refutable && report.non_exhaustiveness_witnesses.is_empty() {
-        if !matches!(
-            cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, cx.match_lint_level).0,
-            rustc_session::lint::Level::Allow
-        ) {
-            let witnesses = collect_nonexhaustive_missing_variants(cx, &pat_column);
-            if !witnesses.is_empty() {
-                // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
-                // is not exhaustive enough.
-                //
-                // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`.
-                cx.tcx.emit_spanned_lint(
-                    NON_EXHAUSTIVE_OMITTED_PATTERNS,
-                    cx.match_lint_level,
-                    cx.scrut_span,
-                    NonExhaustiveOmittedPattern {
-                        scrut_ty,
-                        uncovered: Uncovered::new(cx.scrut_span, cx, witnesses),
-                    },
-                );
-            }
-        } else {
-            // We used to allow putting the `#[allow(non_exhaustive_omitted_patterns)]` on a match
-            // arm. This no longer makes sense so we warn users, to avoid silently breaking their
-            // usage of the lint.
-            for arm in arms {
-                let (lint_level, lint_level_source) =
-                    cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, arm.hir_id);
-                if !matches!(lint_level, rustc_session::lint::Level::Allow) {
-                    let decorator = NonExhaustiveOmittedPatternLintOnArm {
-                        lint_span: lint_level_source.span(),
-                        suggest_lint_on_match: cx.whole_match_span.map(|span| span.shrink_to_lo()),
-                        lint_level: lint_level.as_str(),
-                        lint_name: "non_exhaustive_omitted_patterns",
-                    };
-
-                    use rustc_errors::DecorateLint;
-                    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();
-                }
-            }
-        }
-    }
-
-    report
+    UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
 }