Auto merge of #88950 - Nadrieril:deconstruct-pat, r=oli-obk

Add an intermediate representation to exhaustiveness checking

The exhaustiveness checking algorithm keeps deconstructing patterns into a `Constructor` and some `Fields`, but does so a bit all over the place. This PR introduces a new representation for patterns that already has that information, so we only compute it once at the start.
I find this makes code easier to follow. In particular `DeconstructedPat::specialize` is a lot simpler than what happened before, and more closely matches the description of the algorithm. I'm also hoping this could help for the project of librarifying exhaustiveness for rust_analyzer since it decouples the algorithm from `rustc_middle::Pat`.

10 files changed, 893 insertions, 994 deletions

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 4c51b9207bb..08f8850e78e 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -1,6 +1,6 @@
+use super::deconstruct_pat::{Constructor, DeconstructedPat};
 use super::usefulness::{
-    compute_match_usefulness, expand_pattern, is_wildcard, MatchArm, MatchCheckCtxt, Reachability,
-    UsefulnessReport,
+    compute_match_usefulness, MatchArm, MatchCheckCtxt, Reachability, UsefulnessReport,
 };
 use super::{PatCtxt, PatternError};
 
@@ -12,14 +12,12 @@ use rustc_hir::def::*;
 use rustc_hir::def_id::DefId;
 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc_hir::{HirId, Pat};
-use rustc_middle::thir::PatKind;
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt};
 use rustc_session::lint::builtin::{
     BINDINGS_WITH_VARIANT_NAME, IRREFUTABLE_LET_PATTERNS, UNREACHABLE_PATTERNS,
 };
 use rustc_session::Session;
 use rustc_span::{DesugaringKind, ExpnKind, Span};
-use std::slice;
 
 crate fn check_match(tcx: TyCtxt<'_>, def_id: DefId) {
     let body_id = match def_id.as_local() {
@@ -27,11 +25,12 @@ crate fn check_match(tcx: TyCtxt<'_>, def_id: DefId) {
         Some(id) => tcx.hir().body_owned_by(tcx.hir().local_def_id_to_hir_id(id)),
     };
 
+    let pattern_arena = TypedArena::default();
     let mut visitor = MatchVisitor {
         tcx,
         typeck_results: tcx.typeck_body(body_id),
         param_env: tcx.param_env(def_id),
-        pattern_arena: TypedArena::default(),
+        pattern_arena: &pattern_arena,
     };
     visitor.visit_body(tcx.hir().body(body_id));
 }
@@ -40,14 +39,14 @@ fn create_e0004(sess: &Session, sp: Span, error_message: String) -> DiagnosticBu
     struct_span_err!(sess, sp, E0004, "{}", &error_message)
 }
 
-struct MatchVisitor<'a, 'tcx> {
+struct MatchVisitor<'a, 'p, 'tcx> {
     tcx: TyCtxt<'tcx>,
     typeck_results: &'a ty::TypeckResults<'tcx>,
     param_env: ty::ParamEnv<'tcx>,
-    pattern_arena: TypedArena<super::Pat<'tcx>>,
+    pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
 }
 
-impl<'tcx> Visitor<'tcx> for MatchVisitor<'_, 'tcx> {
+impl<'tcx> Visitor<'tcx> for MatchVisitor<'_, '_, 'tcx> {
     type Map = intravisit::ErasedMap<'tcx>;
 
     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
@@ -113,31 +112,30 @@ impl PatCtxt<'_, '_> {
     }
 }
 
-impl<'tcx> MatchVisitor<'_, 'tcx> {
+impl<'p, 'tcx> MatchVisitor<'_, 'p, 'tcx> {
     fn check_patterns(&self, pat: &Pat<'_>) {
         pat.walk_always(|pat| check_borrow_conflicts_in_at_patterns(self, pat));
         check_for_bindings_named_same_as_variants(self, pat);
     }
 
-    fn lower_pattern<'p>(
+    fn lower_pattern(
         &self,
         cx: &mut MatchCheckCtxt<'p, 'tcx>,
         pat: &'tcx hir::Pat<'tcx>,
         have_errors: &mut bool,
-    ) -> (&'p super::Pat<'tcx>, Ty<'tcx>) {
+    ) -> &'p DeconstructedPat<'p, 'tcx> {
         let mut patcx = PatCtxt::new(self.tcx, self.param_env, self.typeck_results);
         patcx.include_lint_checks();
         let pattern = patcx.lower_pattern(pat);
-        let pattern_ty = pattern.ty;
-        let pattern: &_ = cx.pattern_arena.alloc(expand_pattern(pattern));
+        let pattern: &_ = cx.pattern_arena.alloc(DeconstructedPat::from_pat(cx, &pattern));
         if !patcx.errors.is_empty() {
             *have_errors = true;
             patcx.report_inlining_errors();
         }
-        (pattern, pattern_ty)
+        pattern
     }
 
-    fn new_cx(&self, hir_id: HirId) -> MatchCheckCtxt<'_, 'tcx> {
+    fn new_cx(&self, hir_id: HirId) -> MatchCheckCtxt<'p, 'tcx> {
         MatchCheckCtxt {
             tcx: self.tcx,
             param_env: self.param_env,
@@ -149,8 +147,8 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
     fn check_let(&mut self, pat: &'tcx hir::Pat<'tcx>, expr: &hir::Expr<'_>, span: Span) {
         self.check_patterns(pat);
         let mut cx = self.new_cx(expr.hir_id);
-        let tpat = self.lower_pattern(&mut cx, pat, &mut false).0;
-        check_let_reachability(&mut cx, pat.hir_id, &tpat, span);
+        let tpat = self.lower_pattern(&mut cx, pat, &mut false);
+        check_let_reachability(&mut cx, pat.hir_id, tpat, span);
     }
 
     fn check_match(
@@ -166,8 +164,8 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
             self.check_patterns(&arm.pat);
             if let Some(hir::Guard::IfLet(ref pat, _)) = arm.guard {
                 self.check_patterns(pat);
-                let tpat = self.lower_pattern(&mut cx, pat, &mut false).0;
-                check_let_reachability(&mut cx, pat.hir_id, &tpat, tpat.span);
+                let tpat = self.lower_pattern(&mut cx, pat, &mut false);
+                check_let_reachability(&mut cx, pat.hir_id, tpat, tpat.span());
             }
         }
 
@@ -176,7 +174,7 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
         let arms: Vec<_> = arms
             .iter()
             .map(|hir::Arm { pat, guard, .. }| MatchArm {
-                pat: self.lower_pattern(&mut cx, pat, &mut have_errors).0,
+                pat: self.lower_pattern(&mut cx, pat, &mut have_errors),
                 hir_id: pat.hir_id,
                 has_guard: guard.is_some(),
             })
@@ -190,20 +188,16 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
         let scrut_ty = self.typeck_results.expr_ty_adjusted(scrut);
         let report = compute_match_usefulness(&cx, &arms, scrut.hir_id, scrut_ty);
 
-        report_arm_reachability(&cx, &report, |_, arm_span, arm_hir_id, catchall| {
-            match source {
-                hir::MatchSource::ForLoopDesugar | hir::MatchSource::Normal => {
-                    unreachable_pattern(cx.tcx, arm_span, arm_hir_id, catchall);
-                }
-                // Unreachable patterns in try and await expressions occur when one of
-                // the arms are an uninhabited type. Which is OK.
-                hir::MatchSource::AwaitDesugar | hir::MatchSource::TryDesugar => {}
+        match source {
+            hir::MatchSource::ForLoopDesugar | hir::MatchSource::Normal => {
+                report_arm_reachability(&cx, &report)
             }
-        });
+            // Unreachable patterns in try and await expressions occur when one of
+            // the arms are an uninhabited type. Which is OK.
+            hir::MatchSource::AwaitDesugar | hir::MatchSource::TryDesugar => {}
+        }
 
         // Check if the match is exhaustive.
-        // Note: An empty match isn't the same as an empty matrix for diagnostics purposes,
-        // since an empty matrix can occur when there are arms, if those arms all have guards.
         let is_empty_match = arms.is_empty();
         let witnesses = report.non_exhaustiveness_witnesses;
         if !witnesses.is_empty() {
@@ -214,7 +208,8 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
     fn check_irrefutable(&self, pat: &'tcx Pat<'tcx>, origin: &str, sp: Option<Span>) {
         let mut cx = self.new_cx(pat.hir_id);
 
-        let (pattern, pattern_ty) = self.lower_pattern(&mut cx, pat, &mut false);
+        let pattern = self.lower_pattern(&mut cx, pat, &mut false);
+        let pattern_ty = pattern.ty();
         let arms = vec![MatchArm { pat: pattern, hir_id: pat.hir_id, has_guard: false }];
         let report = compute_match_usefulness(&cx, &arms, pat.hir_id, pattern_ty);
 
@@ -226,7 +221,7 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
             return;
         }
 
-        let joined_patterns = joined_uncovered_patterns(&witnesses);
+        let joined_patterns = joined_uncovered_patterns(&cx, &witnesses);
         let mut err = struct_span_err!(
             self.tcx.sess,
             pat.span,
@@ -302,7 +297,7 @@ fn const_not_var(
     }
 }
 
-fn check_for_bindings_named_same_as_variants(cx: &MatchVisitor<'_, '_>, pat: &Pat<'_>) {
+fn check_for_bindings_named_same_as_variants(cx: &MatchVisitor<'_, '_, '_>, pat: &Pat<'_>) {
     pat.walk_always(|p| {
         if let hir::PatKind::Binding(_, _, ident, None) = p.kind {
             if let Some(ty::BindByValue(hir::Mutability::Not)) =
@@ -344,12 +339,11 @@ fn check_for_bindings_named_same_as_variants(cx: &MatchVisitor<'_, '_>, pat: &Pa
 }
 
 /// Checks for common cases of "catchall" patterns that may not be intended as such.
-fn pat_is_catchall(pat: &super::Pat<'_>) -> bool {
-    use PatKind::*;
-    match &*pat.kind {
-        Binding { subpattern: None, .. } => true,
-        Binding { subpattern: Some(s), .. } | Deref { subpattern: s } => pat_is_catchall(s),
-        Leaf { subpatterns: s } => s.iter().all(|p| pat_is_catchall(&p.pattern)),
+fn pat_is_catchall(pat: &DeconstructedPat<'_, '_>) -> bool {
+    use Constructor::*;
+    match pat.ctor() {
+        Wildcard => true,
+        Single => pat.iter_fields().all(|pat| pat_is_catchall(pat)),
         _ => false,
     }
 }
@@ -428,29 +422,16 @@ fn irrefutable_let_pattern(tcx: TyCtxt<'_>, id: HirId, span: Span) {
 fn check_let_reachability<'p, 'tcx>(
     cx: &mut MatchCheckCtxt<'p, 'tcx>,
     pat_id: HirId,
-    pat: &'p super::Pat<'tcx>,
+    pat: &'p DeconstructedPat<'p, 'tcx>,
     span: Span,
 ) {
     let arms = [MatchArm { pat, hir_id: pat_id, has_guard: false }];
-    let report = compute_match_usefulness(&cx, &arms, pat_id, pat.ty);
-
-    report_arm_reachability(&cx, &report, |arm_index, arm_span, arm_hir_id, _| {
-        match let_source(cx.tcx, pat_id) {
-            LetSource::IfLet | LetSource::WhileLet => {
-                match arm_index {
-                    // The arm with the user-specified pattern.
-                    0 => unreachable_pattern(cx.tcx, arm_span, arm_hir_id, None),
-                    // The arm with the wildcard pattern.
-                    1 => irrefutable_let_pattern(cx.tcx, pat_id, arm_span),
-                    _ => bug!(),
-                }
-            }
-            LetSource::IfLetGuard if arm_index == 0 => {
-                unreachable_pattern(cx.tcx, arm_span, arm_hir_id, None);
-            }
-            _ => {}
-        }
-    });
+    let report = compute_match_usefulness(&cx, &arms, pat_id, pat.ty());
+
+    // Report if the pattern is unreachable, which can only occur when the type is uninhabited.
+    // This also reports unreachable sub-patterns though, so we can't just replace it with an
+    // `is_uninhabited` check.
+    report_arm_reachability(&cx, &report);
 
     if report.non_exhaustiveness_witnesses.is_empty() {
         // The match is exhaustive, i.e. the `if let` pattern is irrefutable.
@@ -459,18 +440,15 @@ fn check_let_reachability<'p, 'tcx>(
 }
 
 /// Report unreachable arms, if any.
-fn report_arm_reachability<'p, 'tcx, F>(
+fn report_arm_reachability<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     report: &UsefulnessReport<'p, 'tcx>,
-    unreachable: F,
-) where
-    F: Fn(usize, Span, HirId, Option<Span>),
-{
+) {
     use Reachability::*;
     let mut catchall = None;
-    for (arm_index, (arm, is_useful)) in report.arm_usefulness.iter().enumerate() {
+    for (arm, is_useful) in report.arm_usefulness.iter() {
         match is_useful {
-            Unreachable => unreachable(arm_index, arm.pat.span, arm.hir_id, catchall),
+            Unreachable => unreachable_pattern(cx.tcx, arm.pat.span(), arm.hir_id, catchall),
             Reachable(unreachables) if unreachables.is_empty() => {}
             // The arm is reachable, but contains unreachable subpatterns (from or-patterns).
             Reachable(unreachables) => {
@@ -483,7 +461,7 @@ fn report_arm_reachability<'p, 'tcx, F>(
             }
         }
         if !arm.has_guard && catchall.is_none() && pat_is_catchall(arm.pat) {
-            catchall = Some(arm.pat.span);
+            catchall = Some(arm.pat.span());
         }
     }
 }
@@ -493,7 +471,7 @@ fn non_exhaustive_match<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     scrut_ty: Ty<'tcx>,
     sp: Span,
-    witnesses: Vec<super::Pat<'tcx>>,
+    witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
     is_empty_match: bool,
 ) {
     let non_empty_enum = match scrut_ty.kind() {
@@ -510,7 +488,7 @@ fn non_exhaustive_match<'p, 'tcx>(
             format!("non-exhaustive patterns: type `{}` is non-empty", scrut_ty),
         );
     } else {
-        let joined_patterns = joined_uncovered_patterns(&witnesses);
+        let joined_patterns = joined_uncovered_patterns(cx, &witnesses);
         err = create_e0004(
             cx.tcx.sess,
             sp,
@@ -537,7 +515,7 @@ fn non_exhaustive_match<'p, 'tcx>(
     if (scrut_ty == cx.tcx.types.usize || scrut_ty == cx.tcx.types.isize)
         && !is_empty_match
         && witnesses.len() == 1
-        && is_wildcard(&witnesses[0])
+        && matches!(witnesses[0].ctor(), Constructor::NonExhaustive)
     {
         err.note(&format!(
             "`{}` does not have a fixed maximum value, \
@@ -560,33 +538,40 @@ fn non_exhaustive_match<'p, 'tcx>(
     err.emit();
 }
 
-crate fn joined_uncovered_patterns(witnesses: &[super::Pat<'_>]) -> String {
+crate fn joined_uncovered_patterns<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    witnesses: &[DeconstructedPat<'p, 'tcx>],
+) -> String {
     const LIMIT: usize = 3;
+    let pat_to_str = |pat: &DeconstructedPat<'p, 'tcx>| pat.to_pat(cx).to_string();
     match witnesses {
         [] => bug!(),
-        [witness] => format!("`{}`", witness),
+        [witness] => format!("`{}`", witness.to_pat(cx)),
         [head @ .., tail] if head.len() < LIMIT => {
-            let head: Vec<_> = head.iter().map(<_>::to_string).collect();
-            format!("`{}` and `{}`", head.join("`, `"), tail)
+            let head: Vec<_> = head.iter().map(pat_to_str).collect();
+            format!("`{}` and `{}`", head.join("`, `"), tail.to_pat(cx))
         }
         _ => {
             let (head, tail) = witnesses.split_at(LIMIT);
-            let head: Vec<_> = head.iter().map(<_>::to_string).collect();
+            let head: Vec<_> = head.iter().map(pat_to_str).collect();
             format!("`{}` and {} more", head.join("`, `"), tail.len())
         }
     }
 }
 
-crate fn pattern_not_covered_label(witnesses: &[super::Pat<'_>], joined_patterns: &str) -> String {
+crate fn pattern_not_covered_label(
+    witnesses: &[DeconstructedPat<'_, '_>],
+    joined_patterns: &str,
+) -> String {
     format!("pattern{} {} not covered", rustc_errors::pluralize!(witnesses.len()), joined_patterns)
 }
 
 /// Point at the definition of non-covered `enum` variants.
-fn adt_defined_here(
-    cx: &MatchCheckCtxt<'_, '_>,
+fn adt_defined_here<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
     err: &mut DiagnosticBuilder<'_>,
-    ty: Ty<'_>,
-    witnesses: &[super::Pat<'_>],
+    ty: Ty<'tcx>,
+    witnesses: &[DeconstructedPat<'p, 'tcx>],
 ) {
     let ty = ty.peel_refs();
     if let ty::Adt(def, _) = ty.kind() {
@@ -595,57 +580,42 @@ fn adt_defined_here(
         }
 
         if witnesses.len() < 4 {
-            for sp in maybe_point_at_variant(ty, &witnesses) {
+            for sp in maybe_point_at_variant(cx, def, witnesses.iter()) {
                 err.span_label(sp, "not covered");
             }
         }
     }
 }
 
-fn maybe_point_at_variant(ty: Ty<'_>, patterns: &[super::Pat<'_>]) -> Vec<Span> {
+fn maybe_point_at_variant<'a, 'p: 'a, 'tcx: 'a>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    def: &AdtDef,
+    patterns: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>,
+) -> Vec<Span> {
+    use Constructor::*;
     let mut covered = vec![];
-    if let ty::Adt(def, _) = ty.kind() {
-        // Don't point at variants that have already been covered due to other patterns to avoid
-        // visual clutter.
-        for pattern in patterns {
-            use PatKind::{AscribeUserType, Deref, Leaf, Or, Variant};
-            match &*pattern.kind {
-                AscribeUserType { subpattern, .. } | Deref { subpattern } => {
-                    covered.extend(maybe_point_at_variant(ty, slice::from_ref(&subpattern)));
-                }
-                Variant { adt_def, variant_index, subpatterns, .. } if adt_def.did == def.did => {
-                    let sp = def.variants[*variant_index].ident.span;
-                    if covered.contains(&sp) {
-                        continue;
-                    }
-                    covered.push(sp);
-
-                    let pats = subpatterns
-                        .iter()
-                        .map(|field_pattern| field_pattern.pattern.clone())
-                        .collect::<Box<[_]>>();
-                    covered.extend(maybe_point_at_variant(ty, &pats));
-                }
-                Leaf { subpatterns } => {
-                    let pats = subpatterns
-                        .iter()
-                        .map(|field_pattern| field_pattern.pattern.clone())
-                        .collect::<Box<[_]>>();
-                    covered.extend(maybe_point_at_variant(ty, &pats));
+    for pattern in patterns {
+        if let Variant(variant_index) = pattern.ctor() {
+            if let ty::Adt(this_def, _) = pattern.ty().kind() {
+                if this_def.did != def.did {
+                    continue;
                 }
-                Or { pats } => {
-                    let pats = pats.iter().cloned().collect::<Box<[_]>>();
-                    covered.extend(maybe_point_at_variant(ty, &pats));
-                }
-                _ => {}
             }
+            let sp = def.variants[*variant_index].ident.span;
+            if covered.contains(&sp) {
+                // Don't point at variants that have already been covered due to other patterns to avoid
+                // visual clutter.
+                continue;
+            }
+            covered.push(sp);
         }
+        covered.extend(maybe_point_at_variant(cx, def, pattern.iter_fields()));
     }
     covered
 }
 
 /// Check if a by-value binding is by-value. That is, check if the binding's type is not `Copy`.
-fn is_binding_by_move(cx: &MatchVisitor<'_, '_>, hir_id: HirId, span: Span) -> bool {
+fn is_binding_by_move(cx: &MatchVisitor<'_, '_, '_>, hir_id: HirId, span: Span) -> bool {
     !cx.typeck_results.node_type(hir_id).is_copy_modulo_regions(cx.tcx.at(span), cx.param_env)
 }
 
@@ -659,7 +629,7 @@ fn is_binding_by_move(cx: &MatchVisitor<'_, '_>, hir_id: HirId, span: Span) -> b
 /// - `x @ Some(ref mut? y)`.
 ///
 /// This analysis is *not* subsumed by NLL.
-fn check_borrow_conflicts_in_at_patterns(cx: &MatchVisitor<'_, '_>, pat: &Pat<'_>) {
+fn check_borrow_conflicts_in_at_patterns(cx: &MatchVisitor<'_, '_, '_>, pat: &Pat<'_>) {
     // Extract `sub` in `binding @ sub`.
     let (name, sub) = match &pat.kind {
         hir::PatKind::Binding(.., name, Some(sub)) => (*name, sub),
diff --git a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
index cee2a4db0a8..69a7d44ff39 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
@@ -46,7 +46,7 @@ use self::Constructor::*;
 use self::SliceKind::*;
 
 use super::compare_const_vals;
-use super::usefulness::{is_wildcard, MatchCheckCtxt, PatCtxt};
+use super::usefulness::{MatchCheckCtxt, PatCtxt};
 
 use rustc_data_structures::captures::Captures;
 use rustc_index::vec::Idx;
@@ -56,16 +56,35 @@ use rustc_middle::mir::interpret::ConstValue;
 use rustc_middle::mir::Field;
 use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange};
 use rustc_middle::ty::layout::IntegerExt;
-use rustc_middle::ty::{self, Const, Ty, TyCtxt};
+use rustc_middle::ty::{self, Const, Ty, TyCtxt, VariantDef};
 use rustc_session::lint;
 use rustc_span::{Span, DUMMY_SP};
 use rustc_target::abi::{Integer, Size, VariantIdx};
 
 use smallvec::{smallvec, SmallVec};
+use std::cell::Cell;
 use std::cmp::{self, max, min, Ordering};
+use std::fmt;
 use std::iter::{once, IntoIterator};
 use std::ops::RangeInclusive;
 
+/// 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.as_ref() {
+            for pat in pats {
+                expand(pat, vec);
+            }
+        } else {
+            vec.push(pat)
+        }
+    }
+
+    let mut pats = Vec::new();
+    expand(pat, &mut pats);
+    pats
+}
+
 /// An inclusive interval, used for precise integer exhaustiveness checking.
 /// `IntRange`s always store a contiguous range. This means that values are
 /// encoded such that `0` encodes the minimum value for the integer,
@@ -76,9 +95,13 @@ use std::ops::RangeInclusive;
 ///
 /// `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, Debug, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq)]
 pub(super) struct IntRange {
     range: RangeInclusive<u128>,
+    /// Keeps the bias used for encoding the range. It depends on the type of the range and
+    /// possibly the pointer size of the current architecture. The algorithm ensures we never
+    /// compare `IntRange`s with different types/architectures.
+    bias: u128,
 }
 
 impl IntRange {
@@ -131,7 +154,7 @@ impl IntRange {
                 value.try_eval_bits(tcx, param_env, ty)
             })()?;
             let val = val ^ bias;
-            Some(IntRange { range: val..=val })
+            Some(IntRange { range: val..=val, bias })
         } else {
             None
         }
@@ -155,7 +178,7 @@ impl IntRange {
                 // This should have been caught earlier by E0030.
                 bug!("malformed range pattern: {}..={}", lo, (hi - offset));
             }
-            Some(IntRange { range: lo..=(hi - offset) })
+            Some(IntRange { range: lo..=(hi - offset), bias })
         } else {
             None
         }
@@ -180,7 +203,7 @@ impl IntRange {
         let (lo, hi) = self.boundaries();
         let (other_lo, other_hi) = other.boundaries();
         if lo <= other_hi && other_lo <= hi {
-            Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi) })
+            Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi), bias: self.bias })
         } else {
             None
         }
@@ -203,10 +226,11 @@ impl IntRange {
         (lo == other_hi || hi == other_lo) && !self.is_singleton() && !other.is_singleton()
     }
 
+    /// Only used for displaying the range properly.
     fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> {
         let (lo, hi) = self.boundaries();
 
-        let bias = IntRange::signed_bias(tcx, ty);
+        let bias = self.bias;
         let (lo, hi) = (lo ^ bias, hi ^ bias);
 
         let env = ty::ParamEnv::empty().and(ty);
@@ -223,10 +247,10 @@ impl IntRange {
     }
 
     /// Lint on likely incorrect range patterns (#63987)
-    pub(super) fn lint_overlapping_range_endpoints<'a, 'tcx: 'a>(
+    pub(super) fn lint_overlapping_range_endpoints<'a, 'p: 'a, 'tcx: 'a>(
         &self,
-        pcx: PatCtxt<'_, '_, 'tcx>,
-        ctors: impl Iterator<Item = (&'a Constructor<'tcx>, Span)>,
+        pcx: PatCtxt<'_, 'p, 'tcx>,
+        pats: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>,
         column_count: usize,
         hir_id: HirId,
     ) {
@@ -248,8 +272,8 @@ impl IntRange {
             return;
         }
 
-        let overlaps: Vec<_> = ctors
-            .filter_map(|(ctor, span)| Some((ctor.as_int_range()?, span)))
+        let overlaps: Vec<_> = pats
+            .filter_map(|pat| Some((pat.ctor().as_int_range()?, pat.span())))
             .filter(|(range, _)| self.suspicious_intersection(range))
             .map(|(range, span)| (self.intersection(&range).unwrap(), span))
             .collect();
@@ -291,6 +315,19 @@ impl IntRange {
     }
 }
 
+/// Note: this is often not what we want: e.g. `false` is converted into the range `0..=0` and
+/// would be displayed as such. To render properly, convert to a pattern first.
+impl fmt::Debug for IntRange {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let (lo, hi) = self.boundaries();
+        let bias = self.bias;
+        let (lo, hi) = (lo ^ bias, hi ^ bias);
+        write!(f, "{}", lo)?;
+        write!(f, "{}", RangeEnd::Included)?;
+        write!(f, "{}", hi)
+    }
+}
+
 /// Represents a border between 2 integers. Because the intervals spanning borders must be able to
 /// cover every integer, we need to be able to represent 2^128 + 1 such borders.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
@@ -375,13 +412,13 @@ impl SplitIntRange {
             // Skip duplicates.
             .filter(|(prev_border, border)| prev_border != border)
             // Finally, convert to ranges.
-            .map(|(prev_border, border)| {
+            .map(move |(prev_border, border)| {
                 let range = match (prev_border, border) {
                     (JustBefore(n), JustBefore(m)) if n < m => n..=(m - 1),
                     (JustBefore(n), AfterMax) => n..=u128::MAX,
                     _ => unreachable!(), // Ruled out by the sorting and filtering we did
                 };
-                IntRange { range }
+                IntRange { range, bias: self.range.bias }
             })
     }
 }
@@ -389,17 +426,17 @@ impl SplitIntRange {
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 enum SliceKind {
     /// Patterns of length `n` (`[x, y]`).
-    FixedLen(u64),
+    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(u64, u64),
+    VarLen(usize, usize),
 }
 
 impl SliceKind {
-    fn arity(self) -> u64 {
+    fn arity(self) -> usize {
         match self {
             FixedLen(length) => length,
             VarLen(prefix, suffix) => prefix + suffix,
@@ -407,7 +444,7 @@ impl SliceKind {
     }
 
     /// Whether this pattern includes patterns of length `other_len`.
-    fn covers_length(self, other_len: u64) -> bool {
+    fn covers_length(self, other_len: usize) -> bool {
         match self {
             FixedLen(len) => len == other_len,
             VarLen(prefix, suffix) => prefix + suffix <= other_len,
@@ -419,13 +456,13 @@ impl SliceKind {
 #[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<u64>,
+    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<u64>, kind: SliceKind) -> Self {
+    fn new(array_len: Option<usize>, kind: SliceKind) -> Self {
         let kind = match (array_len, kind) {
             // If the middle `..` is empty, we effectively have a fixed-length pattern.
             (Some(len), VarLen(prefix, suffix)) if prefix + suffix >= len => FixedLen(len),
@@ -434,7 +471,7 @@ impl Slice {
         Slice { array_len, kind }
     }
 
-    fn arity(self) -> u64 {
+    fn arity(self) -> usize {
         self.kind.arity()
     }
 
@@ -508,16 +545,16 @@ impl Slice {
 #[derive(Debug)]
 struct SplitVarLenSlice {
     /// If the type is an array, this is its size.
-    array_len: Option<u64>,
+    array_len: Option<usize>,
     /// The arity of the input slice.
-    arity: u64,
+    arity: usize,
     /// The smallest slice bigger than any slice seen. `max_slice.arity()` is the length `L`
     /// described above.
     max_slice: SliceKind,
 }
 
 impl SplitVarLenSlice {
-    fn new(prefix: u64, suffix: u64, array_len: Option<u64>) -> Self {
+    fn new(prefix: usize, suffix: usize, array_len: Option<usize>) -> Self {
         SplitVarLenSlice { array_len, arity: prefix + suffix, max_slice: VarLen(prefix, suffix) }
     }
 
@@ -611,6 +648,8 @@ pub(super) enum Constructor<'tcx> {
     Missing { nonexhaustive_enum_missing_real_variants: bool },
     /// Wildcard pattern.
     Wildcard,
+    /// Or-pattern.
+    Or,
 }
 
 impl<'tcx> Constructor<'tcx> {
@@ -647,60 +686,34 @@ impl<'tcx> Constructor<'tcx> {
         }
     }
 
-    /// Determines the constructor that the given pattern can be specialized to.
-    pub(super) fn from_pat<'p>(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &'p Pat<'tcx>) -> Self {
-        match pat.kind.as_ref() {
-            PatKind::AscribeUserType { .. } => bug!(), // Handled by `expand_pattern`
-            PatKind::Binding { .. } | PatKind::Wild => Wildcard,
-            PatKind::Leaf { .. } | PatKind::Deref { .. } => Single,
-            &PatKind::Variant { variant_index, .. } => Variant(variant_index),
-            PatKind::Constant { value } => {
-                if let Some(int_range) = IntRange::from_const(cx.tcx, cx.param_env, value) {
-                    IntRange(int_range)
-                } else {
-                    match pat.ty.kind() {
-                        ty::Float(_) => FloatRange(value, value, RangeEnd::Included),
-                        // In `expand_pattern`, we convert string literals to `&CONST` patterns with
-                        // `CONST` a pattern of type `str`. In truth this contains a constant of type
-                        // `&str`.
-                        ty::Str => Str(value),
-                        // 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.
-                        _ => Opaque,
+    /// 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.variants[self.variant_index_for_adt(adt)];
+                        Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant).count()
                     }
                 }
-            }
-            &PatKind::Range(PatRange { lo, hi, end }) => {
-                let ty = lo.ty;
-                if let Some(int_range) = IntRange::from_range(
-                    cx.tcx,
-                    lo.eval_bits(cx.tcx, cx.param_env, lo.ty),
-                    hi.eval_bits(cx.tcx, cx.param_env, hi.ty),
-                    ty,
-                    &end,
-                ) {
-                    IntRange(int_range)
-                } else {
-                    FloatRange(lo, hi, end)
-                }
-            }
-            PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => {
-                let array_len = match pat.ty.kind() {
-                    ty::Array(_, length) => Some(length.eval_usize(cx.tcx, cx.param_env)),
-                    ty::Slice(_) => None,
-                    _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty),
-                };
-                let prefix = prefix.len() as u64;
-                let suffix = suffix.len() as u64;
-                let kind = if slice.is_some() {
-                    VarLen(prefix, suffix)
-                } else {
-                    FixedLen(prefix + suffix)
-                };
-                Slice(Slice::new(array_len, kind))
-            }
-            PatKind::Or { .. } => bug!("Or-pattern should have been expanded earlier on."),
+                _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx.ty),
+            },
+            Slice(slice) => slice.arity(),
+            Str(..)
+            | FloatRange(..)
+            | IntRange(..)
+            | NonExhaustive
+            | Opaque
+            | Missing { .. }
+            | Wildcard => 0,
+            Or => bug!("The `Or` constructor doesn't have a fixed arity"),
         }
     }
 
@@ -823,7 +836,7 @@ impl<'tcx> Constructor<'tcx> {
         match self {
             // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s.
             Single => !used_ctors.is_empty(),
-            Variant(_) => used_ctors.iter().any(|c| c == self),
+            Variant(vid) => used_ctors.iter().any(|c| matches!(c, Variant(i) if i == vid)),
             IntRange(range) => used_ctors
                 .iter()
                 .filter_map(|c| c.as_int_range())
@@ -834,7 +847,7 @@ impl<'tcx> Constructor<'tcx> {
                 .any(|other| slice.is_covered_by(other)),
             // This constructor is never covered by anything else
             NonExhaustive => false,
-            Str(..) | FloatRange(..) | Opaque | Missing { .. } | Wildcard => {
+            Str(..) | FloatRange(..) | Opaque | Missing { .. } | Wildcard | Or => {
                 span_bug!(pcx.span, "found unexpected ctor in all_ctors: {:?}", self)
             }
         }
@@ -885,7 +898,7 @@ impl<'tcx> SplitWildcard<'tcx> {
         let all_ctors = match pcx.ty.kind() {
             ty::Bool => smallvec![make_range(0, 1)],
             ty::Array(sub_ty, len) if len.try_eval_usize(cx.tcx, cx.param_env).is_some() => {
-                let len = len.eval_usize(cx.tcx, cx.param_env);
+                let len = len.eval_usize(cx.tcx, cx.param_env) as usize;
                 if len != 0 && cx.is_uninhabited(sub_ty) {
                     smallvec![]
                 } else {
@@ -1073,120 +1086,106 @@ impl<'tcx> SplitWildcard<'tcx> {
     }
 }
 
-/// Some fields need to be explicitly hidden away in certain cases; see the comment above the
-/// `Fields` struct. This struct represents such a potentially-hidden field.
-#[derive(Debug, Copy, Clone)]
-pub(super) enum FilteredField<'p, 'tcx> {
-    Kept(&'p Pat<'tcx>),
-    Hidden,
-}
-
-impl<'p, 'tcx> FilteredField<'p, 'tcx> {
-    fn kept(self) -> Option<&'p Pat<'tcx>> {
-        match self {
-            FilteredField::Kept(p) => Some(p),
-            FilteredField::Hidden => None,
-        }
-    }
-}
-
 /// 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 from a constructor using [`Fields::wildcards()`].
 ///
-/// If a private or `non_exhaustive` field is uninhabited, the code mustn't observe that it is
-/// uninhabited. For that, we filter these fields out of the matrix. This is handled automatically
-/// in `Fields`. This filtering is uncommon in practice, because uninhabited fields are rarely used,
-/// so we avoid it when possible to preserve performance.
-#[derive(Debug, Clone)]
-pub(super) enum Fields<'p, 'tcx> {
-    /// Lists of patterns that don't contain any filtered fields.
-    /// `Slice` and `Vec` behave the same; the difference is only to avoid allocating and
-    /// triple-dereferences when possible. Frankly this is premature optimization, I (Nadrieril)
-    /// have not measured if it really made a difference.
-    Slice(&'p [Pat<'tcx>]),
-    Vec(SmallVec<[&'p Pat<'tcx>; 2]>),
-    /// Patterns where some of the fields need to be hidden. For all intents and purposes we only
-    /// care about the non-hidden fields. We need to keep the real field index for those fields;
-    /// we're morally storing a `Vec<(usize, &Pat)>` but what we do is more convenient.
-    /// `len` counts the number of non-hidden fields
-    Filtered {
-        fields: SmallVec<[FilteredField<'p, 'tcx>; 2]>,
-        len: usize,
-    },
+/// 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), _, _, _]`.
+/// ```rust
+/// 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 `mir::Field` 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> {
-    /// Internal use. Use `Fields::wildcards()` instead.
-    /// Must not be used if the pattern is a field of a struct/tuple/variant.
-    fn from_single_pattern(pat: &'p Pat<'tcx>) -> Self {
-        Fields::Slice(std::slice::from_ref(pat))
+    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 }
     }
 
-    /// Convenience; internal use.
     fn wildcards_from_tys(
         cx: &MatchCheckCtxt<'p, 'tcx>,
         tys: impl IntoIterator<Item = Ty<'tcx>>,
     ) -> Self {
-        let wilds = tys.into_iter().map(Pat::wildcard_from_ty);
-        let pats = cx.pattern_arena.alloc_from_iter(wilds);
-        Fields::Slice(pats)
+        Fields::from_iter(cx, tys.into_iter().map(DeconstructedPat::wildcard))
     }
 
-    /// Creates a new list of wildcard fields for a given constructor.
-    pub(super) fn wildcards(pcx: PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self {
-        let ty = pcx.ty;
-        let cx = pcx.cx;
-        let wildcard_from_ty = |ty| &*cx.pattern_arena.alloc(Pat::wildcard_from_ty(ty));
+    // 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 = (Field, Ty<'tcx>)> + Captures<'a> + Captures<'p> {
+        let (adt, substs) = match ty.kind() {
+            ty::Adt(adt, substs) => (adt, substs),
+            _ => 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, substs);
+            let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx);
+            let is_uninhabited = cx.is_uninhabited(ty);
+
+            if is_uninhabited && (!is_visible || is_non_exhaustive) {
+                None
+            } else {
+                Some((Field::new(i), ty))
+            }
+        })
+    }
 
+    /// Creates a new list of wildcard fields for a given constructor. The result must have a
+    /// length of `constructor.arity()`.
+    pub(super) fn wildcards(
+        cx: &MatchCheckCtxt<'p, 'tcx>,
+        ty: Ty<'tcx>,
+        constructor: &Constructor<'tcx>,
+    ) -> Self {
         let ret = match constructor {
             Single | Variant(_) => match ty.kind() {
-                ty::Tuple(ref fs) => {
-                    Fields::wildcards_from_tys(cx, fs.into_iter().map(|ty| ty.expect_ty()))
-                }
-                ty::Ref(_, rty, _) => Fields::from_single_pattern(wildcard_from_ty(rty)),
+                ty::Tuple(fs) => Fields::wildcards_from_tys(cx, fs.iter().map(|ty| ty.expect_ty())),
+                ty::Ref(_, rty, _) => Fields::wildcards_from_tys(cx, once(*rty)),
                 ty::Adt(adt, substs) => {
                     if adt.is_box() {
-                        // Use T as the sub pattern type of Box<T>.
-                        Fields::from_single_pattern(wildcard_from_ty(substs.type_at(0)))
+                        // 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(cx, once(substs.type_at(0)))
                     } else {
                         let variant = &adt.variants[constructor.variant_index_for_adt(adt)];
-                        // 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();
-                        let field_tys = variant.fields.iter().map(|field| field.ty(cx.tcx, substs));
-                        // In the following cases, we don't need to filter out any fields. This is
-                        // the vast majority of real cases, since uninhabited fields are uncommon.
-                        let has_no_hidden_fields = (adt.is_enum() && !is_non_exhaustive)
-                            || !field_tys.clone().any(|ty| cx.is_uninhabited(ty));
-
-                        if has_no_hidden_fields {
-                            Fields::wildcards_from_tys(cx, field_tys)
-                        } else {
-                            let mut len = 0;
-                            let fields = variant
-                                .fields
-                                .iter()
-                                .map(|field| {
-                                    let ty = field.ty(cx.tcx, substs);
-                                    let is_visible = adt.is_enum()
-                                        || field.vis.is_accessible_from(cx.module, cx.tcx);
-                                    let is_uninhabited = cx.is_uninhabited(ty);
-
-                                    // 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.
-                                    if is_uninhabited && (!is_visible || is_non_exhaustive) {
-                                        FilteredField::Hidden
-                                    } else {
-                                        len += 1;
-                                        FilteredField::Kept(wildcard_from_ty(ty))
-                                    }
-                                })
-                                .collect();
-                            Fields::Filtered { fields, len }
-                        }
+                        let tys = Fields::list_variant_nonhidden_fields(cx, ty, variant)
+                            .map(|(_, ty)| ty);
+                        Fields::wildcards_from_tys(cx, tys)
                     }
                 }
                 _ => bug!("Unexpected type for `Single` constructor: {:?}", ty),
@@ -1204,54 +1203,243 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
             | NonExhaustive
             | Opaque
             | Missing { .. }
-            | Wildcard => Fields::Slice(&[]),
+            | Wildcard => Fields::empty(),
+            Or => {
+                bug!("called `Fields::wildcards` on an `Or` ctor")
+            }
         };
         debug!("Fields::wildcards({:?}, {:?}) = {:#?}", constructor, ty, ret);
         ret
     }
 
-    /// Apply a constructor to a list of patterns, yielding a new pattern. `self`
-    /// must have as many elements as this constructor's arity.
-    ///
-    /// This is roughly the inverse of `specialize_constructor`.
-    ///
-    /// Examples:
-    ///
-    /// ```text
-    /// ctor: `Constructor::Single`
-    /// ty: `Foo(u32, u32, u32)`
-    /// self: `[10, 20, _]`
-    /// returns `Foo(10, 20, _)`
-    ///
-    /// ctor: `Constructor::Variant(Option::Some)`
-    /// ty: `Option<bool>`
-    /// self: `[false]`
-    /// returns `Some(false)`
-    /// ```
-    pub(super) fn apply(self, pcx: PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Pat<'tcx> {
-        let subpatterns_and_indices = self.patterns_and_indices();
-        let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p).cloned();
-
-        let pat = match ctor {
-            Single | Variant(_) => match pcx.ty.kind() {
-                ty::Adt(..) | ty::Tuple(..) => {
-                    // We want the real indices here.
-                    let subpatterns = subpatterns_and_indices
-                        .iter()
-                        .map(|&(field, p)| FieldPat { field, pattern: p.clone() })
-                        .collect();
+    /// 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()
+    }
+}
 
-                    if let ty::Adt(adt, substs) = pcx.ty.kind() {
-                        if adt.is_enum() {
-                            PatKind::Variant {
-                                adt_def: adt,
-                                substs,
-                                variant_index: ctor.variant_index_for_adt(adt),
-                                subpatterns,
-                            }
+/// Values and patterns can be represented as a constructor applied to some fields. This represents
+/// a pattern in this form.
+/// This also keeps track of whether the pattern has been foundreachable during analysis. For this
+/// reason we should be careful not to clone patterns for which we care about that. Use
+/// `clone_and_forget_reachability` is you're sure.
+pub(crate) struct DeconstructedPat<'p, 'tcx> {
+    ctor: Constructor<'tcx>,
+    fields: Fields<'p, 'tcx>,
+    ty: Ty<'tcx>,
+    span: Span,
+    reachable: Cell<bool>,
+}
+
+impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
+    pub(super) fn wildcard(ty: Ty<'tcx>) -> Self {
+        Self::new(Wildcard, Fields::empty(), ty, DUMMY_SP)
+    }
+
+    pub(super) fn new(
+        ctor: Constructor<'tcx>,
+        fields: Fields<'p, 'tcx>,
+        ty: Ty<'tcx>,
+        span: Span,
+    ) -> Self {
+        DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) }
+    }
+
+    /// 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<'_, 'p, 'tcx>, ctor: Constructor<'tcx>) -> Self {
+        let fields = Fields::wildcards(pcx.cx, pcx.ty, &ctor);
+        DeconstructedPat::new(ctor, fields, pcx.ty, DUMMY_SP)
+    }
+
+    /// Clone this value. This method emphasizes that cloning loses reachability information and
+    /// should be done carefully.
+    pub(super) fn clone_and_forget_reachability(&self) -> Self {
+        DeconstructedPat::new(self.ctor.clone(), self.fields, self.ty, self.span)
+    }
+
+    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.as_ref() {
+            PatKind::AscribeUserType { 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| ty.expect_ty())
+                            .map(DeconstructedPat::wildcard)
+                            .collect();
+                        for pat in subpatterns {
+                            wilds[pat.field.index()] = mkpat(&pat.pattern);
+                        }
+                        fields = Fields::from_iter(cx, wilds);
+                    }
+                    ty::Adt(adt, substs) 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 pat = subpatterns.into_iter().find(|pat| pat.field.index() == 0);
+                        let pat = if let Some(pat) = pat {
+                            mkpat(&pat.pattern)
                         } else {
-                            PatKind::Leaf { subpatterns }
+                            DeconstructedPat::wildcard(substs.type_at(0))
+                        };
+                        ctor = Single;
+                        fields = Fields::singleton(cx, pat);
+                    }
+                    ty::Adt(adt, _) => {
+                        ctor = match pat.kind.as_ref() {
+                            PatKind::Leaf { .. } => Single,
+                            PatKind::Variant { variant_index, .. } => Variant(*variant_index),
+                            _ => bug!(),
+                        };
+                        let variant = &adt.variants[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(DeconstructedPat::wildcard).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 } => {
+                if let Some(int_range) = IntRange::from_const(cx.tcx, cx.param_env, value) {
+                    ctor = IntRange(int_range);
+                    fields = Fields::empty();
+                } else {
+                    match pat.ty.kind() {
+                        ty::Float(_) => {
+                            ctor = FloatRange(value, value, RangeEnd::Included);
+                            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;
+                            fields = Fields::empty();
                         }
+                    }
+                }
+            }
+            &PatKind::Range(PatRange { lo, hi, end }) => {
+                let ty = lo.ty;
+                ctor = if let Some(int_range) = IntRange::from_range(
+                    cx.tcx,
+                    lo.eval_bits(cx.tcx, cx.param_env, lo.ty),
+                    hi.eval_bits(cx.tcx, cx.param_env, hi.ty),
+                    ty,
+                    &end,
+                ) {
+                    IntRange(int_range)
+                } else {
+                    FloatRange(lo, hi, end)
+                };
+                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_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).map(mkpat));
+            }
+            PatKind::Or { .. } => {
+                ctor = Or;
+                let pats = expand_or_pat(pat);
+                fields = Fields::from_iter(cx, pats.into_iter().map(mkpat));
+            }
+        }
+        DeconstructedPat::new(ctor, fields, pat.ty, pat.span)
+    }
+
+    pub(crate) fn to_pat(&self, cx: &MatchCheckCtxt<'p, 'tcx>) -> Pat<'tcx> {
+        let is_wildcard = |pat: &Pat<'_>| {
+            matches!(*pat.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild)
+        };
+        let mut subpatterns = self.iter_fields().map(|p| p.to_pat(cx));
+        let pat = match &self.ctor {
+            Single | Variant(_) => match self.ty.kind() {
+                ty::Tuple(..) => PatKind::Leaf {
+                    subpatterns: subpatterns
+                        .enumerate()
+                        .map(|(i, p)| FieldPat { field: Field::new(i), pattern: p })
+                        .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, substs) => {
+                    let variant_index = self.ctor.variant_index_for_adt(adt_def);
+                    let variant = &adt_def.variants[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, substs, variant_index, subpatterns }
                     } else {
                         PatKind::Leaf { subpatterns }
                     }
@@ -1259,195 +1447,239 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
                 // 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
-                // can ignore this issue.
+                // ignore this issue.
                 ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
-                ty::Slice(_) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", ctor, pcx.ty),
-                _ => PatKind::Wild,
+                _ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty),
             },
-            Slice(slice) => match slice.kind {
-                FixedLen(_) => {
-                    PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] }
-                }
-                VarLen(prefix, _) => {
-                    let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix as usize).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();
+            Slice(slice) => {
+                match slice.kind {
+                    FixedLen(_) => PatKind::Slice {
+                        prefix: subpatterns.collect(),
+                        slice: None,
+                        suffix: vec![],
+                    },
+                    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: Vec<_> = subpatterns.collect();
+                        let wild = Pat::wildcard_from_ty(self.ty);
+                        PatKind::Slice { prefix, slice: Some(wild), suffix }
                     }
-                    let suffix: Vec<_> = if slice.array_len.is_some() {
-                        // Same as above.
-                        subpatterns.skip_while(is_wildcard).collect()
-                    } else {
-                        subpatterns.collect()
-                    };
-                    let wild = Pat::wildcard_from_ty(pcx.ty);
-                    PatKind::Slice { prefix, slice: Some(wild), suffix }
                 }
-            },
+            }
             &Str(value) => PatKind::Constant { value },
             &FloatRange(lo, hi, end) => PatKind::Range(PatRange { lo, hi, end }),
-            IntRange(range) => return range.to_pat(pcx.cx.tcx, pcx.ty),
-            NonExhaustive => PatKind::Wild,
-            Wildcard => return Pat::wildcard_from_ty(pcx.ty),
-            Opaque => bug!("we should not try to apply an opaque constructor"),
+            IntRange(range) => return range.to_pat(cx.tcx, self.ty),
+            Wildcard | NonExhaustive => PatKind::Wild,
             Missing { .. } => bug!(
-                "trying to apply the `Missing` constructor; this should have been done in `apply_constructors`"
+                "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
+                `Missing` should have been processed in `apply_constructors`"
             ),
+            Opaque | Or => {
+                bug!("can't convert to pattern: {:?}", self)
+            }
         };
 
-        Pat { ty: pcx.ty, span: DUMMY_SP, kind: Box::new(pat) }
+        Pat { ty: self.ty, span: DUMMY_SP, kind: Box::new(pat) }
     }
 
-    /// Returns the number of patterns. This is the same as the arity of the constructor used to
-    /// construct `self`.
-    pub(super) fn len(&self) -> usize {
-        match self {
-            Fields::Slice(pats) => pats.len(),
-            Fields::Vec(pats) => pats.len(),
-            Fields::Filtered { len, .. } => *len,
-        }
+    pub(super) fn is_or_pat(&self) -> bool {
+        matches!(self.ctor, Or)
     }
 
-    /// Returns the list of patterns along with the corresponding field indices.
-    fn patterns_and_indices(&self) -> SmallVec<[(Field, &'p Pat<'tcx>); 2]> {
-        match self {
-            Fields::Slice(pats) => {
-                pats.iter().enumerate().map(|(i, p)| (Field::new(i), p)).collect()
-            }
-            Fields::Vec(pats) => {
-                pats.iter().copied().enumerate().map(|(i, p)| (Field::new(i), p)).collect()
-            }
-            Fields::Filtered { fields, .. } => {
-                // Indices must be relative to the full list of patterns
-                fields
-                    .iter()
-                    .enumerate()
-                    .filter_map(|(i, p)| Some((Field::new(i), p.kept()?)))
-                    .collect()
-            }
-        }
+    pub(super) fn ctor(&self) -> &Constructor<'tcx> {
+        &self.ctor
     }
-
-    /// Returns the list of patterns.
-    pub(super) fn into_patterns(self) -> SmallVec<[&'p Pat<'tcx>; 2]> {
-        match self {
-            Fields::Slice(pats) => pats.iter().collect(),
-            Fields::Vec(pats) => pats,
-            Fields::Filtered { fields, .. } => fields.iter().filter_map(|p| p.kept()).collect(),
-        }
+    pub(super) fn ty(&self) -> Ty<'tcx> {
+        self.ty
     }
-
-    /// Overrides some of the fields with the provided patterns. Exactly like
-    /// `replace_fields_indexed`, except that it takes `FieldPat`s as input.
-    fn replace_with_fieldpats(
-        &self,
-        new_pats: impl IntoIterator<Item = &'p FieldPat<'tcx>>,
-    ) -> Self {
-        self.replace_fields_indexed(
-            new_pats.into_iter().map(|pat| (pat.field.index(), &pat.pattern)),
-        )
+    pub(super) fn span(&self) -> Span {
+        self.span
     }
 
-    /// Overrides some of the fields with the provided patterns. This is used when a pattern
-    /// defines some fields but not all, for example `Foo { field1: Some(_), .. }`: here we start
-    /// with a `Fields` that is just one wildcard per field of the `Foo` struct, and override the
-    /// entry corresponding to `field1` with the pattern `Some(_)`. This is also used for slice
-    /// patterns for the same reason.
-    fn replace_fields_indexed(
-        &self,
-        new_pats: impl IntoIterator<Item = (usize, &'p Pat<'tcx>)>,
-    ) -> Self {
-        let mut fields = self.clone();
-        if let Fields::Slice(pats) = fields {
-            fields = Fields::Vec(pats.iter().collect());
-        }
+    pub(super) fn iter_fields<'a>(
+        &'a self,
+    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
+        self.fields.iter_patterns()
+    }
 
-        match &mut fields {
-            Fields::Vec(pats) => {
-                for (i, pat) in new_pats {
-                    if let Some(p) = pats.get_mut(i) {
-                        *p = pat;
-                    }
-                }
+    /// 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,
+        cx: &MatchCheckCtxt<'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(cx, self.ty, other_ctor).iter_patterns().collect()
             }
-            Fields::Filtered { fields, .. } => {
-                for (i, pat) in new_pats {
-                    if let FilteredField::Kept(p) = &mut fields[i] {
-                        *p = pat
+            (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 inner_ty = match *self.ty.kind() {
+                            ty::Slice(ty) | ty::Array(ty, _) => ty,
+                            _ => 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: &_ =
+                            cx.pattern_arena.alloc(DeconstructedPat::wildcard(inner_ty));
+                        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()
                     }
                 }
             }
-            Fields::Slice(_) => unreachable!(),
+            _ => self.fields.iter_patterns().collect(),
         }
-        fields
     }
 
-    /// Replaces contained fields with the given list of patterns. There must be `len()` patterns
-    /// in `pats`.
-    pub(super) fn replace_fields(
-        &self,
-        cx: &MatchCheckCtxt<'p, 'tcx>,
-        pats: impl IntoIterator<Item = Pat<'tcx>>,
-    ) -> Self {
-        let pats: &[_] = cx.pattern_arena.alloc_from_iter(pats);
+    /// We keep track for each pattern if it was ever reachable during the analysis. This is used
+    /// with `unreachable_spans` to report unreachable subpatterns arising from or patterns.
+    pub(super) fn set_reachable(&self) {
+        self.reachable.set(true)
+    }
+    pub(super) fn is_reachable(&self) -> bool {
+        self.reachable.get()
+    }
 
-        match self {
-            Fields::Filtered { fields, len } => {
-                let mut pats = pats.iter();
-                let mut fields = fields.clone();
-                for f in &mut fields {
-                    if let FilteredField::Kept(p) = f {
-                        // We take one input pattern for each `Kept` field, in order.
-                        *p = pats.next().unwrap();
-                    }
-                }
-                Fields::Filtered { fields, len: *len }
+    /// Report the spans of subpatterns that were not reachable, if any.
+    pub(super) fn unreachable_spans(&self) -> Vec<Span> {
+        let mut spans = Vec::new();
+        self.collect_unreachable_spans(&mut spans);
+        spans
+    }
+
+    fn collect_unreachable_spans(&self, spans: &mut Vec<Span>) {
+        // We don't look at subpatterns if we already reported the whole pattern as unreachable.
+        if !self.is_reachable() {
+            spans.push(self.span);
+        } else {
+            for p in self.iter_fields() {
+                p.collect_unreachable_spans(spans);
             }
-            _ => Fields::Slice(pats),
         }
     }
+}
 
-    /// Replaces contained fields with the arguments of the given pattern. Only use on a pattern
-    /// that is compatible with the constructor used to build `self`.
-    /// This is meant to be used on the result of `Fields::wildcards()`. The idea is that
-    /// `wildcards` constructs a list of fields where all entries are wildcards, and the pattern
-    /// provided to this function fills some of the fields with non-wildcards.
-    /// In the following example `Fields::wildcards` would return `[_, _, _, _]`. If we call
-    /// `replace_with_pattern_arguments` on it with the pattern, the result will be `[Some(0), _,
-    /// _, _]`.
-    /// ```rust
-    /// let x: [Option<u8>; 4] = foo();
-    /// match x {
-    ///     [Some(0), ..] => {}
-    /// }
-    /// ```
-    /// This is guaranteed to preserve the number of patterns in `self`.
-    pub(super) fn replace_with_pattern_arguments(&self, pat: &'p Pat<'tcx>) -> Self {
-        match pat.kind.as_ref() {
-            PatKind::Deref { subpattern } => {
-                assert_eq!(self.len(), 1);
-                Fields::from_single_pattern(subpattern)
+/// 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
             }
-            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
-                self.replace_with_fieldpats(subpatterns)
+        };
+        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.variants[self.ctor.variant_index_for_adt(adt)])
+                        }
+                        ty::Tuple(_) => None,
+                        _ => unreachable!(),
+                    };
+
+                    if let Some(variant) = variant {
+                        write!(f, "{}", variant.ident)?;
+                    }
+
+                    // 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 suple
+                    // 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, "]")
+            }
+            &FloatRange(lo, hi, end) => {
+                write!(f, "{}", lo)?;
+                write!(f, "{}", end)?;
+                write!(f, "{}", hi)
             }
-            PatKind::Array { prefix, suffix, .. } | PatKind::Slice { prefix, suffix, .. } => {
-                // Number of subpatterns for the constructor
-                let ctor_arity = self.len();
-
-                // Replace the prefix and the suffix with the given patterns, leaving wildcards in
-                // the middle if there was a subslice pattern `..`.
-                let prefix = prefix.iter().enumerate();
-                let suffix =
-                    suffix.iter().enumerate().map(|(i, p)| (ctor_arity - suffix.len() + i, p));
-                self.replace_fields_indexed(prefix.chain(suffix))
+            IntRange(range) => write!(f, "{:?}", range), // Best-effort, will render e.g. `false` as `0..=0`
+            Wildcard | Missing { .. } | NonExhaustive => write!(f, "_"),
+            Or => {
+                for pat in self.iter_fields() {
+                    write!(f, "{}{:?}", start_or_continue(" | "), pat)?;
+                }
+                Ok(())
             }
-            _ => self.clone(),
+            Str(value) => write!(f, "{}", value),
+            Opaque => write!(f, "<constant pattern>"),
         }
     }
 }
diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
index f4255713e2a..650a87b2d88 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
@@ -284,27 +284,22 @@ use self::ArmType::*;
 use self::Usefulness::*;
 
 use super::check_match::{joined_uncovered_patterns, pattern_not_covered_label};
-use super::deconstruct_pat::{Constructor, Fields, SplitWildcard};
-use super::{PatternFoldable, PatternFolder};
+use super::deconstruct_pat::{Constructor, DeconstructedPat, Fields, SplitWildcard};
 
 use rustc_data_structures::captures::Captures;
-use rustc_data_structures::fx::FxHashMap;
 
-use hir::def_id::DefId;
-use hir::HirId;
 use rustc_arena::TypedArena;
-use rustc_hir as hir;
-use rustc_middle::thir::{Pat, PatKind};
+use rustc_hir::def_id::DefId;
+use rustc_hir::HirId;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS;
-use rustc_span::Span;
+use rustc_span::{Span, DUMMY_SP};
 
 use smallvec::{smallvec, SmallVec};
 use std::fmt;
-use std::iter::{FromIterator, IntoIterator};
-use std::lazy::OnceCell;
+use std::iter::once;
 
-crate struct MatchCheckCtxt<'a, 'tcx> {
+crate struct MatchCheckCtxt<'p, 'tcx> {
     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)
@@ -313,7 +308,7 @@ crate struct MatchCheckCtxt<'a, 'tcx> {
     /// outside its module and should not be matchable with an empty match statement.
     crate module: DefId,
     crate param_env: ty::ParamEnv<'tcx>,
-    crate pattern_arena: &'a TypedArena<Pat<'tcx>>,
+    crate pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
 }
 
 impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
@@ -356,78 +351,20 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
     }
 }
 
-crate fn expand_pattern<'tcx>(pat: Pat<'tcx>) -> Pat<'tcx> {
-    LiteralExpander.fold_pattern(&pat)
-}
-
-struct LiteralExpander;
-
-impl<'tcx> PatternFolder<'tcx> for LiteralExpander {
-    fn fold_pattern(&mut self, pat: &Pat<'tcx>) -> Pat<'tcx> {
-        debug!("fold_pattern {:?} {:?} {:?}", pat, pat.ty.kind(), pat.kind);
-        match (pat.ty.kind(), pat.kind.as_ref()) {
-            (_, PatKind::Binding { subpattern: Some(s), .. }) => s.fold_with(self),
-            (_, PatKind::AscribeUserType { subpattern: s, .. }) => s.fold_with(self),
-            (ty::Ref(_, t, _), PatKind::Constant { .. }) if t.is_str() => {
-                // Treat string literal patterns as deref patterns to a `str` constant, i.e.
-                // `&CONST`. This expands them like other const patterns. This could have been done
-                // in `const_to_pat`, but that causes issues with the rest of the matching code.
-                let mut new_pat = pat.super_fold_with(self);
-                // Make a fake const pattern of type `str` (instead of `&str`). That the carried
-                // constant value still knows it is of type `&str`.
-                new_pat.ty = t;
-                Pat {
-                    kind: Box::new(PatKind::Deref { subpattern: new_pat }),
-                    span: pat.span,
-                    ty: pat.ty,
-                }
-            }
-            _ => pat.super_fold_with(self),
-        }
-    }
-}
-
-pub(super) fn is_wildcard(pat: &Pat<'_>) -> bool {
-    matches!(*pat.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild)
-}
-
-fn is_or_pat(pat: &Pat<'_>) -> bool {
-    matches!(*pat.kind, PatKind::Or { .. })
-}
-
-/// 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.as_ref() {
-            for pat in pats {
-                expand(pat, vec);
-            }
-        } else {
-            vec.push(pat)
-        }
-    }
-
-    let mut pats = Vec::new();
-    expand(pat, &mut pats);
-    pats
-}
-
 /// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
 /// works well.
 #[derive(Clone)]
 struct PatStack<'p, 'tcx> {
-    pats: SmallVec<[&'p Pat<'tcx>; 2]>,
-    /// Cache for the constructor of the head
-    head_ctor: OnceCell<Constructor<'tcx>>,
+    pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>,
 }
 
 impl<'p, 'tcx> PatStack<'p, 'tcx> {
-    fn from_pattern(pat: &'p Pat<'tcx>) -> Self {
+    fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self {
         Self::from_vec(smallvec![pat])
     }
 
-    fn from_vec(vec: SmallVec<[&'p Pat<'tcx>; 2]>) -> Self {
-        PatStack { pats: vec, head_ctor: OnceCell::new() }
+    fn from_vec(vec: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>) -> Self {
+        PatStack { pats: vec }
     }
 
     fn is_empty(&self) -> bool {
@@ -438,79 +375,56 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'p Pat<'tcx> {
+    fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> {
         self.pats[0]
     }
 
-    #[inline]
-    fn head_ctor<'a>(&'a self, cx: &MatchCheckCtxt<'p, 'tcx>) -> &'a Constructor<'tcx> {
-        self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head()))
-    }
-
-    fn iter(&self) -> impl Iterator<Item = &Pat<'tcx>> {
+    fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> {
         self.pats.iter().copied()
     }
 
     // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
     // or-pattern. Panics if `self` is empty.
     fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = PatStack<'p, 'tcx>> + Captures<'a> {
-        expand_or_pat(self.head()).into_iter().map(move |pat| {
+        self.head().iter_fields().map(move |pat| {
             let mut new_patstack = PatStack::from_pattern(pat);
             new_patstack.pats.extend_from_slice(&self.pats[1..]);
             new_patstack
         })
     }
 
-    /// This computes `S(self.head_ctor(), self)`. See top of the file for explanations.
+    /// This computes `S(self.head().ctor(), self)`. See top of the file for explanations.
     ///
     /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
     /// fields filled with wild patterns.
     ///
     /// This is roughly the inverse of `Constructor::apply`.
-    fn pop_head_constructor(&self, ctor_wild_subpatterns: &Fields<'p, 'tcx>) -> PatStack<'p, 'tcx> {
+    fn pop_head_constructor(
+        &self,
+        cx: &MatchCheckCtxt<'p, 'tcx>,
+        ctor: &Constructor<'tcx>,
+    ) -> PatStack<'p, 'tcx> {
         // We pop the head pattern and push the new fields extracted from the arguments of
         // `self.head()`.
-        let mut new_fields =
-            ctor_wild_subpatterns.replace_with_pattern_arguments(self.head()).into_patterns();
+        let mut new_fields: SmallVec<[_; 2]> = self.head().specialize(cx, ctor);
         new_fields.extend_from_slice(&self.pats[1..]);
         PatStack::from_vec(new_fields)
     }
 }
 
-impl<'p, 'tcx> Default for PatStack<'p, 'tcx> {
-    fn default() -> Self {
-        Self::from_vec(smallvec![])
-    }
-}
-
-impl<'p, 'tcx> PartialEq for PatStack<'p, 'tcx> {
-    fn eq(&self, other: &Self) -> bool {
-        self.pats == other.pats
-    }
-}
-
-impl<'p, 'tcx> FromIterator<&'p Pat<'tcx>> for PatStack<'p, 'tcx> {
-    fn from_iter<T>(iter: T) -> Self
-    where
-        T: IntoIterator<Item = &'p Pat<'tcx>>,
-    {
-        Self::from_vec(iter.into_iter().collect())
-    }
-}
-
 /// Pretty-printing for matrix row.
 impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "+")?;
         for pat in self.iter() {
-            write!(f, " {} +", pat)?;
+            write!(f, " {:?} +", pat)?;
         }
         Ok(())
     }
 }
 
 /// A 2D matrix.
-#[derive(Clone, PartialEq)]
+#[derive(Clone)]
 pub(super) struct Matrix<'p, 'tcx> {
     patterns: Vec<PatStack<'p, 'tcx>>,
 }
@@ -528,7 +442,7 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
     /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
     /// expands it.
     fn push(&mut self, row: PatStack<'p, 'tcx>) {
-        if !row.is_empty() && is_or_pat(row.head()) {
+        if !row.is_empty() && row.head().is_or_pat() {
             for row in row.expand_or_pat() {
                 self.patterns.push(row);
             }
@@ -538,24 +452,10 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
     }
 
     /// Iterate over the first component of each row
-    fn heads<'a>(&'a self) -> impl Iterator<Item = &'a Pat<'tcx>> + Captures<'p> {
-        self.patterns.iter().map(|r| r.head())
-    }
-
-    /// Iterate over the first constructor of each row.
-    pub(super) fn head_ctors<'a>(
+    fn heads<'a>(
         &'a self,
-        cx: &'a MatchCheckCtxt<'p, 'tcx>,
-    ) -> impl Iterator<Item = &'a Constructor<'tcx>> + Captures<'p> + Clone {
-        self.patterns.iter().map(move |r| r.head_ctor(cx))
-    }
-
-    /// Iterate over the first constructor and the corresponding span of each row.
-    pub(super) fn head_ctors_and_spans<'a>(
-        &'a self,
-        cx: &'a MatchCheckCtxt<'p, 'tcx>,
-    ) -> impl Iterator<Item = (&'a Constructor<'tcx>, Span)> + Captures<'p> {
-        self.patterns.iter().map(move |r| (r.head_ctor(cx), r.head().span))
+    ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> {
+        self.patterns.iter().map(|r| r.head())
     }
 
     /// This computes `S(constructor, self)`. See top of the file for explanations.
@@ -563,13 +463,15 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
         &self,
         pcx: PatCtxt<'_, 'p, 'tcx>,
         ctor: &Constructor<'tcx>,
-        ctor_wild_subpatterns: &Fields<'p, 'tcx>,
     ) -> Matrix<'p, 'tcx> {
-        self.patterns
-            .iter()
-            .filter(|r| ctor.is_covered_by(pcx, r.head_ctor(pcx.cx)))
-            .map(|r| r.pop_head_constructor(ctor_wild_subpatterns))
-            .collect()
+        let mut matrix = Matrix::empty();
+        for row in &self.patterns {
+            if ctor.is_covered_by(pcx, row.head().ctor()) {
+                let new_row = row.pop_head_constructor(pcx.cx, ctor);
+                matrix.push(new_row);
+            }
+        }
+        matrix
     }
 }
 
@@ -588,7 +490,7 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
 
         let Matrix { patterns: m, .. } = self;
         let pretty_printed_matrix: Vec<Vec<String>> =
-            m.iter().map(|row| row.iter().map(|pat| format!("{}", pat)).collect()).collect();
+            m.iter().map(|row| row.iter().map(|pat| format!("{:?}", pat)).collect()).collect();
 
         let column_count = m.iter().map(|row| row.len()).next().unwrap_or(0);
         assert!(m.iter().all(|row| row.len() == column_count));
@@ -609,296 +511,40 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
     }
 }
 
-impl<'p, 'tcx> FromIterator<PatStack<'p, 'tcx>> for Matrix<'p, 'tcx> {
-    fn from_iter<T>(iter: T) -> Self
-    where
-        T: IntoIterator<Item = PatStack<'p, 'tcx>>,
-    {
-        let mut matrix = Matrix::empty();
-        for x in iter {
-            // Using `push` ensures we correctly expand or-patterns.
-            matrix.push(x);
-        }
-        matrix
-    }
-}
-
-/// Given a pattern or a pattern-stack, this struct captures a set of its subpatterns. We use that
-/// to track reachable sub-patterns arising from or-patterns. In the absence of or-patterns this
-/// will always be either `Empty` (the whole pattern is unreachable) or `Full` (the whole pattern
-/// is reachable). When there are or-patterns, some subpatterns may be reachable while others
-/// aren't. In this case the whole pattern still counts as reachable, but we will lint the
-/// unreachable subpatterns.
-///
-/// This supports a limited set of operations, so not all possible sets of subpatterns can be
-/// represented. That's ok, we only want the ones that make sense for our usage.
-///
-/// What we're doing is illustrated by this:
-/// ```
-/// match (true, 0) {
-///     (true, 0) => {}
-///     (_, 1) => {}
-///     (true | false, 0 | 1) => {}
-/// }
-/// ```
-/// When we try the alternatives of the `true | false` or-pattern, the last `0` is reachable in the
-/// `false` alternative but not the `true`. So overall it is reachable. By contrast, the last `1`
-/// is not reachable in either alternative, so we want to signal this to the user.
-/// Therefore we take the union of sets of reachable patterns coming from different alternatives in
-/// order to figure out which subpatterns are overall reachable.
-///
-/// Invariant: we try to construct the smallest representation we can. In particular if
-/// `self.is_empty()` we ensure that `self` is `Empty`, and same with `Full`. This is not important
-/// for correctness currently.
-#[derive(Debug, Clone)]
-enum SubPatSet<'p, 'tcx> {
-    /// The empty set. This means the pattern is unreachable.
-    Empty,
-    /// The set containing the full pattern.
-    Full,
-    /// If the pattern is a pattern with a constructor or a pattern-stack, we store a set for each
-    /// of its subpatterns. Missing entries in the map are implicitly full, because that's the
-    /// common case.
-    Seq { subpats: FxHashMap<usize, SubPatSet<'p, 'tcx>> },
-    /// If the pattern is an or-pattern, we store a set for each of its alternatives. Missing
-    /// entries in the map are implicitly empty. Note: we always flatten nested or-patterns.
-    Alt {
-        subpats: FxHashMap<usize, SubPatSet<'p, 'tcx>>,
-        /// Counts the total number of alternatives in the pattern
-        alt_count: usize,
-        /// We keep the pattern around to retrieve spans.
-        pat: &'p Pat<'tcx>,
-    },
-}
-
-impl<'p, 'tcx> SubPatSet<'p, 'tcx> {
-    fn full() -> Self {
-        SubPatSet::Full
-    }
-    fn empty() -> Self {
-        SubPatSet::Empty
-    }
-
-    fn is_empty(&self) -> bool {
-        match self {
-            SubPatSet::Empty => true,
-            SubPatSet::Full => false,
-            // If any subpattern in a sequence is unreachable, the whole pattern is unreachable.
-            SubPatSet::Seq { subpats } => subpats.values().any(|set| set.is_empty()),
-            // An or-pattern is reachable if any of its alternatives is.
-            SubPatSet::Alt { subpats, .. } => subpats.values().all(|set| set.is_empty()),
-        }
-    }
-
-    fn is_full(&self) -> bool {
-        match self {
-            SubPatSet::Empty => false,
-            SubPatSet::Full => true,
-            // The whole pattern is reachable only when all its alternatives are.
-            SubPatSet::Seq { subpats } => subpats.values().all(|sub_set| sub_set.is_full()),
-            // The whole or-pattern is reachable only when all its alternatives are.
-            SubPatSet::Alt { subpats, alt_count, .. } => {
-                subpats.len() == *alt_count && subpats.values().all(|set| set.is_full())
-            }
-        }
-    }
-
-    /// Union `self` with `other`, mutating `self`.
-    fn union(&mut self, other: Self) {
-        use SubPatSet::*;
-        // Union with full stays full; union with empty changes nothing.
-        if self.is_full() || other.is_empty() {
-            return;
-        } else if self.is_empty() {
-            *self = other;
-            return;
-        } else if other.is_full() {
-            *self = Full;
-            return;
-        }
-
-        match (&mut *self, other) {
-            (Seq { subpats: s_set }, Seq { subpats: mut o_set }) => {
-                s_set.retain(|i, s_sub_set| {
-                    // Missing entries count as full.
-                    let o_sub_set = o_set.remove(&i).unwrap_or(Full);
-                    s_sub_set.union(o_sub_set);
-                    // We drop full entries.
-                    !s_sub_set.is_full()
-                });
-                // Everything left in `o_set` is missing from `s_set`, i.e. counts as full. Since
-                // unioning with full returns full, we can drop those entries.
-            }
-            (Alt { subpats: s_set, .. }, Alt { subpats: mut o_set, .. }) => {
-                s_set.retain(|i, s_sub_set| {
-                    // Missing entries count as empty.
-                    let o_sub_set = o_set.remove(&i).unwrap_or(Empty);
-                    s_sub_set.union(o_sub_set);
-                    // We drop empty entries.
-                    !s_sub_set.is_empty()
-                });
-                // Everything left in `o_set` is missing from `s_set`, i.e. counts as empty. Since
-                // unioning with empty changes nothing, we can take those entries as is.
-                s_set.extend(o_set);
-            }
-            _ => bug!(),
-        }
-
-        if self.is_full() {
-            *self = Full;
-        }
-    }
-
-    /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the
-    /// whole pattern is unreachable) we return `None`.
-    fn list_unreachable_spans(&self) -> Option<Vec<Span>> {
-        /// Panics if `set.is_empty()`.
-        fn fill_spans(set: &SubPatSet<'_, '_>, spans: &mut Vec<Span>) {
-            match set {
-                SubPatSet::Empty => bug!(),
-                SubPatSet::Full => {}
-                SubPatSet::Seq { subpats } => {
-                    for (_, sub_set) in subpats {
-                        fill_spans(sub_set, spans);
-                    }
-                }
-                SubPatSet::Alt { subpats, pat, alt_count, .. } => {
-                    let expanded = expand_or_pat(pat);
-                    for i in 0..*alt_count {
-                        let sub_set = subpats.get(&i).unwrap_or(&SubPatSet::Empty);
-                        if sub_set.is_empty() {
-                            // Found an unreachable subpattern.
-                            spans.push(expanded[i].span);
-                        } else {
-                            fill_spans(sub_set, spans);
-                        }
-                    }
-                }
-            }
-        }
-
-        if self.is_empty() {
-            return None;
-        }
-        if self.is_full() {
-            // No subpatterns are unreachable.
-            return Some(Vec::new());
-        }
-        let mut spans = Vec::new();
-        fill_spans(self, &mut spans);
-        Some(spans)
-    }
-
-    /// When `self` refers to a patstack that was obtained from specialization, after running
-    /// `unspecialize` it will refer to the original patstack before specialization.
-    fn unspecialize(self, arity: usize) -> Self {
-        use SubPatSet::*;
-        match self {
-            Full => Full,
-            Empty => Empty,
-            Seq { subpats } => {
-                // We gather the first `arity` subpatterns together and shift the remaining ones.
-                let mut new_subpats = FxHashMap::default();
-                let mut new_subpats_first_col = FxHashMap::default();
-                for (i, sub_set) in subpats {
-                    if i < arity {
-                        // The first `arity` indices are now part of the pattern in the first
-                        // column.
-                        new_subpats_first_col.insert(i, sub_set);
-                    } else {
-                        // Indices after `arity` are simply shifted
-                        new_subpats.insert(i - arity + 1, sub_set);
-                    }
-                }
-                // If `new_subpats_first_col` has no entries it counts as full, so we can omit it.
-                if !new_subpats_first_col.is_empty() {
-                    new_subpats.insert(0, Seq { subpats: new_subpats_first_col });
-                }
-                Seq { subpats: new_subpats }
-            }
-            Alt { .. } => bug!(), // `self` is a patstack
-        }
-    }
-
-    /// When `self` refers to a patstack that was obtained from splitting an or-pattern, after
-    /// running `unspecialize` it will refer to the original patstack before splitting.
-    ///
-    /// For example:
-    /// ```
-    /// match Some(true) {
-    ///     Some(true) => {}
-    ///     None | Some(true | false) => {}
-    /// }
-    /// ```
-    /// Here `None` would return the full set and `Some(true | false)` would return the set
-    /// containing `false`. After `unsplit_or_pat`, we want the set to contain `None` and `false`.
-    /// This is what this function does.
-    fn unsplit_or_pat(mut self, alt_id: usize, alt_count: usize, pat: &'p Pat<'tcx>) -> Self {
-        use SubPatSet::*;
-        if self.is_empty() {
-            return Empty;
-        }
-
-        // Subpatterns coming from inside the or-pattern alternative itself, e.g. in `None | Some(0
-        // | 1)`.
-        let set_first_col = match &mut self {
-            Full => Full,
-            Seq { subpats } => subpats.remove(&0).unwrap_or(Full),
-            Empty => unreachable!(),
-            Alt { .. } => bug!(), // `self` is a patstack
-        };
-        let mut subpats_first_col = FxHashMap::default();
-        subpats_first_col.insert(alt_id, set_first_col);
-        let set_first_col = Alt { subpats: subpats_first_col, pat, alt_count };
-
-        let mut subpats = match self {
-            Full => FxHashMap::default(),
-            Seq { subpats } => subpats,
-            Empty => unreachable!(),
-            Alt { .. } => bug!(), // `self` is a patstack
-        };
-        subpats.insert(0, set_first_col);
-        Seq { subpats }
-    }
-}
-
 /// This carries the results of computing usefulness, as described at the top of the file. When
 /// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track
 /// of potential unreachable sub-patterns (in the presence of or-patterns). When checking
 /// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of
 /// witnesses of non-exhaustiveness when there are any.
 /// Which variant to use is dictated by `ArmType`.
-#[derive(Clone, Debug)]
+#[derive(Debug)]
 enum Usefulness<'p, 'tcx> {
-    /// Carries a set of subpatterns that have been found to be reachable. If empty, this indicates
-    /// the whole pattern is unreachable. If not, this indicates that the pattern is reachable but
-    /// that some sub-patterns may be unreachable (due to or-patterns). In the absence of
-    /// or-patterns this will always be either `Empty` (the whole pattern is unreachable) or `Full`
-    /// (the whole pattern is reachable).
-    NoWitnesses(SubPatSet<'p, 'tcx>),
+    /// If we don't care about witnesses, simply remember if the pattern was useful.
+    NoWitnesses { useful: bool },
     /// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole
     /// pattern is unreachable.
-    WithWitnesses(Vec<Witness<'tcx>>),
+    WithWitnesses(Vec<Witness<'p, 'tcx>>),
 }
 
 impl<'p, 'tcx> Usefulness<'p, 'tcx> {
     fn new_useful(preference: ArmType) -> Self {
         match preference {
+            // A single (empty) witness of reachability.
             FakeExtraWildcard => WithWitnesses(vec![Witness(vec![])]),
-            RealArm => NoWitnesses(SubPatSet::full()),
+            RealArm => NoWitnesses { useful: true },
         }
     }
 
     fn new_not_useful(preference: ArmType) -> Self {
         match preference {
             FakeExtraWildcard => WithWitnesses(vec![]),
-            RealArm => NoWitnesses(SubPatSet::empty()),
+            RealArm => NoWitnesses { useful: false },
         }
     }
 
     fn is_useful(&self) -> bool {
         match self {
-            Usefulness::NoWitnesses(set) => !set.is_empty(),
+            Usefulness::NoWitnesses { useful } => *useful,
             Usefulness::WithWitnesses(witnesses) => !witnesses.is_empty(),
         }
     }
@@ -909,33 +555,10 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
             (WithWitnesses(_), WithWitnesses(o)) if o.is_empty() => {}
             (WithWitnesses(s), WithWitnesses(o)) if s.is_empty() => *self = WithWitnesses(o),
             (WithWitnesses(s), WithWitnesses(o)) => s.extend(o),
-            (NoWitnesses(s), NoWitnesses(o)) => s.union(o),
-            _ => unreachable!(),
-        }
-    }
-
-    /// When trying several branches and each returns a `Usefulness`, we need to combine the
-    /// results together.
-    fn merge(pref: ArmType, usefulnesses: impl Iterator<Item = Self>) -> Self {
-        let mut ret = Self::new_not_useful(pref);
-        for u in usefulnesses {
-            ret.extend(u);
-            if let NoWitnesses(subpats) = &ret {
-                if subpats.is_full() {
-                    // Once we reach the full set, more unions won't change the result.
-                    return ret;
-                }
+            (NoWitnesses { useful: s_useful }, NoWitnesses { useful: o_useful }) => {
+                *s_useful = *s_useful || o_useful
             }
-        }
-        ret
-    }
-
-    /// After calculating the usefulness for a branch of an or-pattern, call this to make this
-    /// usefulness mergeable with those from the other branches.
-    fn unsplit_or_pat(self, alt_id: usize, alt_count: usize, pat: &'p Pat<'tcx>) -> Self {
-        match self {
-            NoWitnesses(subpats) => NoWitnesses(subpats.unsplit_or_pat(alt_id, alt_count, pat)),
-            WithWitnesses(_) => bug!(),
+            _ => unreachable!(),
         }
     }
 
@@ -947,10 +570,10 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
         pcx: PatCtxt<'_, 'p, 'tcx>,
         matrix: &Matrix<'p, 'tcx>, // used to compute missing ctors
         ctor: &Constructor<'tcx>,
-        ctor_wild_subpatterns: &Fields<'p, 'tcx>,
     ) -> Self {
         match self {
-            WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses),
+            NoWitnesses { .. } => self,
+            WithWitnesses(ref witnesses) if witnesses.is_empty() => self,
             WithWitnesses(witnesses) => {
                 let new_witnesses = if let Constructor::Missing { .. } = ctor {
                     // We got the special `Missing` constructor, so each of the missing constructors
@@ -958,22 +581,18 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
                     let new_patterns = if pcx.is_non_exhaustive {
                         // Here we don't want the user to try to list all variants, we want them to add
                         // a wildcard, so we only suggest that.
-                        vec![
-                            Fields::wildcards(pcx, &Constructor::NonExhaustive)
-                                .apply(pcx, &Constructor::NonExhaustive),
-                        ]
+                        vec![DeconstructedPat::wildcard(pcx.ty)]
                     } else {
                         let mut split_wildcard = SplitWildcard::new(pcx);
-                        split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
+                        split_wildcard.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
                         // Construct for each missing constructor a "wild" version of this
                         // constructor, that matches everything that can be built with
                         // it. For example, if `ctor` is a `Constructor::Variant` for
                         // `Option::Some`, we get the pattern `Some(_)`.
                         split_wildcard
                             .iter_missing(pcx)
-                            .map(|missing_ctor| {
-                                Fields::wildcards(pcx, missing_ctor).apply(pcx, missing_ctor)
-                            })
+                            .cloned()
+                            .map(|missing_ctor| DeconstructedPat::wild_from_ctor(pcx, missing_ctor))
                             .collect()
                     };
 
@@ -981,21 +600,25 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
                         .into_iter()
                         .flat_map(|witness| {
                             new_patterns.iter().map(move |pat| {
-                                let mut witness = witness.clone();
-                                witness.0.push(pat.clone());
-                                witness
+                                Witness(
+                                    witness
+                                        .0
+                                        .iter()
+                                        .chain(once(pat))
+                                        .map(DeconstructedPat::clone_and_forget_reachability)
+                                        .collect(),
+                                )
                             })
                         })
                         .collect()
                 } else {
                     witnesses
                         .into_iter()
-                        .map(|witness| witness.apply_constructor(pcx, &ctor, ctor_wild_subpatterns))
+                        .map(|witness| witness.apply_constructor(pcx, &ctor))
                         .collect()
                 };
                 WithWitnesses(new_witnesses)
             }
-            NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())),
         }
     }
 }
@@ -1039,12 +662,12 @@ enum ArmType {
 ///     `Witness(vec![Pair(Some(_), true)])`
 ///
 /// The final `Pair(Some(_), true)` is then the resulting witness.
-#[derive(Clone, Debug)]
-crate struct Witness<'tcx>(Vec<Pat<'tcx>>);
+#[derive(Debug)]
+crate struct Witness<'p, 'tcx>(Vec<DeconstructedPat<'p, 'tcx>>);
 
-impl<'tcx> Witness<'tcx> {
+impl<'p, 'tcx> Witness<'p, 'tcx> {
     /// Asserts that the witness contains a single pattern, and returns it.
-    fn single_pattern(self) -> Pat<'tcx> {
+    fn single_pattern(self) -> DeconstructedPat<'p, 'tcx> {
         assert_eq!(self.0.len(), 1);
         self.0.into_iter().next().unwrap()
     }
@@ -1062,17 +685,13 @@ impl<'tcx> Witness<'tcx> {
     ///
     /// left_ty: struct X { a: (bool, &'static str), b: usize}
     /// pats: [(false, "foo"), 42]  => X { a: (false, "foo"), b: 42 }
-    fn apply_constructor<'p>(
-        mut self,
-        pcx: PatCtxt<'_, 'p, 'tcx>,
-        ctor: &Constructor<'tcx>,
-        ctor_wild_subpatterns: &Fields<'p, 'tcx>,
-    ) -> Self {
+    fn apply_constructor(mut self, pcx: PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Self {
         let pat = {
             let len = self.0.len();
-            let arity = ctor_wild_subpatterns.len();
+            let arity = ctor.arity(pcx);
             let pats = self.0.drain((len - arity)..).rev();
-            ctor_wild_subpatterns.replace_fields(pcx.cx, pats).apply(pcx, ctor)
+            let fields = Fields::from_iter(pcx.cx, pats);
+            DeconstructedPat::new(ctor.clone(), fields, pcx.ty, DUMMY_SP)
         };
 
         self.0.push(pat);
@@ -1090,9 +709,9 @@ fn lint_non_exhaustive_omitted_patterns<'p, 'tcx>(
     scrut_ty: Ty<'tcx>,
     sp: Span,
     hir_id: HirId,
-    witnesses: Vec<Pat<'tcx>>,
+    witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
 ) {
-    let joined_patterns = joined_uncovered_patterns(&witnesses);
+    let joined_patterns = joined_uncovered_patterns(cx, &witnesses);
     cx.tcx.struct_span_lint_hir(NON_EXHAUSTIVE_OMITTED_PATTERNS, hir_id, sp, |build| {
         let mut lint = build.build("some variants are not matched explicitly");
         lint.span_label(sp, pattern_not_covered_label(&witnesses, &joined_patterns));
@@ -1163,56 +782,52 @@ fn is_useful<'p, 'tcx>(
     assert!(rows.iter().all(|r| r.len() == v.len()));
 
     // FIXME(Nadrieril): Hack to work around type normalization issues (see #72476).
-    let ty = matrix.heads().next().map_or(v.head().ty, |r| r.ty);
+    let ty = matrix.heads().next().map_or(v.head().ty(), |r| r.ty());
     let is_non_exhaustive = cx.is_foreign_non_exhaustive_enum(ty);
-    let pcx = PatCtxt { cx, ty, span: v.head().span, is_top_level, is_non_exhaustive };
+    let pcx = PatCtxt { cx, ty, span: v.head().span(), is_top_level, is_non_exhaustive };
 
     // If the first pattern is an or-pattern, expand it.
-    let ret = if is_or_pat(v.head()) {
+    let mut ret = Usefulness::new_not_useful(witness_preference);
+    if v.head().is_or_pat() {
         debug!("expanding or-pattern");
-        let v_head = v.head();
-        let vs: Vec<_> = v.expand_or_pat().collect();
-        let alt_count = vs.len();
         // We try each or-pattern branch in turn.
         let mut matrix = matrix.clone();
-        let usefulnesses = vs.into_iter().enumerate().map(|(i, v)| {
+        for v in v.expand_or_pat() {
             let usefulness =
                 is_useful(cx, &matrix, &v, witness_preference, hir_id, is_under_guard, false);
+            ret.extend(usefulness);
             // If pattern has a guard don't add it to the matrix.
             if !is_under_guard {
                 // We push the already-seen patterns into the matrix in order to detect redundant
                 // branches like `Some(_) | Some(0)`.
                 matrix.push(v);
             }
-            usefulness.unsplit_or_pat(i, alt_count, v_head)
-        });
-        Usefulness::merge(witness_preference, usefulnesses)
+        }
     } else {
-        let v_ctor = v.head_ctor(cx);
+        let v_ctor = v.head().ctor();
         if let Constructor::IntRange(ctor_range) = &v_ctor {
             // Lint on likely incorrect range patterns (#63987)
             ctor_range.lint_overlapping_range_endpoints(
                 pcx,
-                matrix.head_ctors_and_spans(cx),
+                matrix.heads(),
                 matrix.column_count().unwrap_or(0),
                 hir_id,
             )
         }
         // We split the head constructor of `v`.
-        let split_ctors = v_ctor.split(pcx, matrix.head_ctors(cx));
+        let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
         let is_non_exhaustive_and_wild = is_non_exhaustive && v_ctor.is_wildcard();
         // For each constructor, we compute whether there's a value that starts with it that would
         // witness the usefulness of `v`.
         let start_matrix = &matrix;
-        let usefulnesses = split_ctors.into_iter().map(|ctor| {
+        for ctor in split_ctors {
             debug!("specialize({:?})", ctor);
             // We cache the result of `Fields::wildcards` because it is used a lot.
-            let ctor_wild_subpatterns = Fields::wildcards(pcx, &ctor);
-            let spec_matrix =
-                start_matrix.specialize_constructor(pcx, &ctor, &ctor_wild_subpatterns);
-            let v = v.pop_head_constructor(&ctor_wild_subpatterns);
+            let spec_matrix = start_matrix.specialize_constructor(pcx, &ctor);
+            let v = v.pop_head_constructor(cx, &ctor);
             let usefulness =
                 is_useful(cx, &spec_matrix, &v, witness_preference, hir_id, is_under_guard, false);
+            let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor);
 
             // When all the conditions are met we have a match with a `non_exhaustive` enum
             // that has the potential to trigger the `non_exhaustive_omitted_patterns` lint.
@@ -1229,29 +844,31 @@ fn is_useful<'p, 'tcx>(
             {
                 let patterns = {
                     let mut split_wildcard = SplitWildcard::new(pcx);
-                    split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
+                    split_wildcard.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
                     // Construct for each missing constructor a "wild" version of this
                     // constructor, that matches everything that can be built with
                     // it. For example, if `ctor` is a `Constructor::Variant` for
                     // `Option::Some`, we get the pattern `Some(_)`.
                     split_wildcard
                         .iter_missing(pcx)
-                        // Filter out the `Constructor::NonExhaustive` variant it's meaningless
-                        // to our lint
+                        // Filter out the `NonExhaustive` because we want to list only real
+                        // variants.
                         .filter(|c| !c.is_non_exhaustive())
-                        .map(|missing_ctor| {
-                            Fields::wildcards(pcx, missing_ctor).apply(pcx, missing_ctor)
-                        })
+                        .cloned()
+                        .map(|missing_ctor| DeconstructedPat::wild_from_ctor(pcx, missing_ctor))
                         .collect::<Vec<_>>()
                 };
 
                 lint_non_exhaustive_omitted_patterns(pcx.cx, pcx.ty, pcx.span, hir_id, patterns);
             }
 
-            usefulness.apply_constructor(pcx, start_matrix, &ctor, &ctor_wild_subpatterns)
-        });
-        Usefulness::merge(witness_preference, usefulnesses)
-    };
+            ret.extend(usefulness);
+        }
+    }
+
+    if ret.is_useful() {
+        v.head().set_reachable();
+    }
 
     debug!(?ret);
     ret
@@ -1261,7 +878,7 @@ fn is_useful<'p, 'tcx>(
 #[derive(Clone, Copy)]
 crate struct MatchArm<'p, 'tcx> {
     /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
-    crate pat: &'p Pat<'tcx>,
+    crate pat: &'p DeconstructedPat<'p, 'tcx>,
     crate hir_id: HirId,
     crate has_guard: bool,
 }
@@ -1283,7 +900,7 @@ crate struct UsefulnessReport<'p, 'tcx> {
     crate arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Reachability)>,
     /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
     /// exhaustiveness.
-    crate non_exhaustiveness_witnesses: Vec<Pat<'tcx>>,
+    crate non_exhaustiveness_witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
 }
 
 /// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
@@ -1303,27 +920,25 @@ crate fn compute_match_usefulness<'p, 'tcx>(
         .copied()
         .map(|arm| {
             let v = PatStack::from_pattern(arm.pat);
-            let usefulness = is_useful(cx, &matrix, &v, RealArm, arm.hir_id, arm.has_guard, true);
+            is_useful(cx, &matrix, &v, RealArm, arm.hir_id, arm.has_guard, true);
             if !arm.has_guard {
                 matrix.push(v);
             }
-            let reachability = match usefulness {
-                NoWitnesses(subpats) if subpats.is_empty() => Reachability::Unreachable,
-                NoWitnesses(subpats) => {
-                    Reachability::Reachable(subpats.list_unreachable_spans().unwrap())
-                }
-                WithWitnesses(..) => bug!(),
+            let reachability = if arm.pat.is_reachable() {
+                Reachability::Reachable(arm.pat.unreachable_spans())
+            } else {
+                Reachability::Unreachable
             };
             (arm, reachability)
         })
         .collect();
 
-    let wild_pattern = cx.pattern_arena.alloc(Pat::wildcard_from_ty(scrut_ty));
+    let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty));
     let v = PatStack::from_pattern(wild_pattern);
     let usefulness = is_useful(cx, &matrix, &v, FakeExtraWildcard, scrut_hir_id, false, true);
     let non_exhaustiveness_witnesses = match usefulness {
         WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(),
-        NoWitnesses(_) => bug!(),
+        NoWitnesses { .. } => bug!(),
     };
     UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
 }
diff --git a/src/test/ui/consts/const_in_pattern/issue-78057.stderr b/src/test/ui/consts/const_in_pattern/issue-78057.stderr
index 0d49d0e96c8..35619594f75 100644
--- a/src/test/ui/consts/const_in_pattern/issue-78057.stderr
+++ b/src/test/ui/consts/const_in_pattern/issue-78057.stderr
@@ -7,8 +7,11 @@ LL |         FOO => {},
 error: unreachable pattern
   --> $DIR/issue-78057.rs:14:9
    |
+LL |         FOO => {},
+   |         --- matches any value
+LL |
 LL |         _ => {}
-   |         ^
+   |         ^ unreachable pattern
    |
 note: the lint level is defined here
   --> $DIR/issue-78057.rs:1:9
diff --git a/src/test/ui/pattern/usefulness/const-private-fields.rs b/src/test/ui/pattern/usefulness/const-private-fields.rs
new file mode 100644
index 00000000000..06c832ca46a
--- /dev/null
+++ b/src/test/ui/pattern/usefulness/const-private-fields.rs
@@ -0,0 +1,30 @@
+// check-pass
+//
+// Check that we don't ignore private fields in usefulness checking
+#![deny(unreachable_patterns)]
+
+mod inner {
+    #[derive(PartialEq, Eq)]
+    pub struct PrivateField {
+        pub x: bool,
+        y: bool,
+    }
+
+    pub const FOO: PrivateField = PrivateField { x: true, y: true };
+    pub const BAR: PrivateField = PrivateField { x: true, y: false };
+}
+use inner::*;
+
+fn main() {
+    match FOO {
+        FOO => {}
+        BAR => {}
+        _ => {}
+    }
+
+    match FOO {
+        FOO => {}
+        PrivateField { x: true, .. } => {}
+        _ => {}
+    }
+}
diff --git a/src/test/ui/pattern/usefulness/consts-opaque.stderr b/src/test/ui/pattern/usefulness/consts-opaque.stderr
index 68451043cf5..05c009a6f3f 100644
--- a/src/test/ui/pattern/usefulness/consts-opaque.stderr
+++ b/src/test/ui/pattern/usefulness/consts-opaque.stderr
@@ -7,8 +7,11 @@ LL |         FOO => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:32:9
    |
+LL |         FOO => {}
+   |         --- matches any value
+LL |
 LL |         _ => {} // should not be emitting unreachable warning
-   |         ^
+   |         ^ unreachable pattern
    |
 note: the lint level is defined here
   --> $DIR/consts-opaque.rs:6:9
@@ -25,8 +28,11 @@ LL |         FOO_REF => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:39:9
    |
+LL |         FOO_REF => {}
+   |         ------- matches any value
+LL |
 LL |         Foo(_) => {} // should not be emitting unreachable warning
-   |         ^^^^^^
+   |         ^^^^^^ unreachable pattern
 
 warning: to use a constant of type `Foo` in a pattern, `Foo` must be annotated with `#[derive(PartialEq, Eq)]`
   --> $DIR/consts-opaque.rs:45:9
@@ -70,15 +76,18 @@ LL |         BAR => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:63:9
    |
+LL |         BAR => {}
+   |         --- matches any value
+LL |
 LL |         Bar => {} // should not be emitting unreachable warning
-   |         ^^^
+   |         ^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:65:9
    |
-LL |         Bar => {} // should not be emitting unreachable warning
+LL |         BAR => {}
    |         --- matches any value
-LL |
+...
 LL |         _ => {}
    |         ^ unreachable pattern
 
@@ -97,14 +106,20 @@ LL |         BAR => {} // should not be emitting unreachable warning
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:72:9
    |
+LL |         BAR => {}
+   |         --- matches any value
+LL |
 LL |         BAR => {} // should not be emitting unreachable warning
-   |         ^^^
+   |         ^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:75:9
    |
+LL |         BAR => {}
+   |         --- matches any value
+...
 LL |         _ => {} // should not be emitting unreachable warning
-   |         ^
+   |         ^ unreachable pattern
 
 error: to use a constant of type `Baz` in a pattern, `Baz` must be annotated with `#[derive(PartialEq, Eq)]`
   --> $DIR/consts-opaque.rs:80:9
@@ -115,14 +130,20 @@ LL |         BAZ => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:82:9
    |
+LL |         BAZ => {}
+   |         --- matches any value
+LL |
 LL |         Baz::Baz1 => {} // should not be emitting unreachable warning
-   |         ^^^^^^^^^
+   |         ^^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:84:9
    |
+LL |         BAZ => {}
+   |         --- matches any value
+...
 LL |         _ => {}
-   |         ^
+   |         ^ unreachable pattern
 
 error: to use a constant of type `Baz` in a pattern, `Baz` must be annotated with `#[derive(PartialEq, Eq)]`
   --> $DIR/consts-opaque.rs:90:9
@@ -133,8 +154,11 @@ LL |         BAZ => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:92:9
    |
+LL |         BAZ => {}
+   |         --- matches any value
+LL |
 LL |         _ => {}
-   |         ^
+   |         ^ unreachable pattern
 
 error: to use a constant of type `Baz` in a pattern, `Baz` must be annotated with `#[derive(PartialEq, Eq)]`
   --> $DIR/consts-opaque.rs:97:9
@@ -145,20 +169,28 @@ LL |         BAZ => {}
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:99:9
    |
+LL |         BAZ => {}
+   |         --- matches any value
+LL |
 LL |         Baz::Baz2 => {} // should not be emitting unreachable warning
-   |         ^^^^^^^^^
+   |         ^^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:101:9
    |
+LL |         BAZ => {}
+   |         --- matches any value
+...
 LL |         _ => {} // should not be emitting unreachable warning
-   |         ^
+   |         ^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:127:9
    |
+LL |         Wrap(_) => {}
+   |         ------- matches any value
 LL |         WRAPQUUX => {} // detected unreachable because we do inspect the `Wrap` layer
-   |         ^^^^^^^^
+   |         ^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/consts-opaque.rs:141:9
diff --git a/src/test/ui/pattern/usefulness/integer-ranges/reachability.stderr b/src/test/ui/pattern/usefulness/integer-ranges/reachability.stderr
index 9a02fac6a75..0ffb0ffd82a 100644
--- a/src/test/ui/pattern/usefulness/integer-ranges/reachability.stderr
+++ b/src/test/ui/pattern/usefulness/integer-ranges/reachability.stderr
@@ -133,8 +133,10 @@ LL |         5..15 => {},
 error: unreachable pattern
   --> $DIR/reachability.rs:83:9
    |
+LL |         _ => {},
+   |         - matches any value
 LL |         '\u{D7FF}'..='\u{E000}' => {},
-   |         ^^^^^^^^^^^^^^^^^^^^^^^
+   |         ^^^^^^^^^^^^^^^^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
   --> $DIR/reachability.rs:104:9
diff --git a/src/test/ui/pattern/usefulness/issue-3601.stderr b/src/test/ui/pattern/usefulness/issue-3601.stderr
index c873c20cca8..48ed1491508 100644
--- a/src/test/ui/pattern/usefulness/issue-3601.stderr
+++ b/src/test/ui/pattern/usefulness/issue-3601.stderr
@@ -1,8 +1,8 @@
-error[E0004]: non-exhaustive patterns: `Box(_, _)` not covered
+error[E0004]: non-exhaustive patterns: `box _` not covered
   --> $DIR/issue-3601.rs:30:44
    |
 LL |         box NodeKind::Element(ed) => match ed.kind {
-   |                                            ^^^^^^^ pattern `Box(_, _)` not covered
+   |                                            ^^^^^^^ pattern `box _` not covered
    |
    = help: ensure that all possible cases are being handled, possibly by adding wildcards or more match arms
    = note: the matched value is of type `Box<ElementKind>`
diff --git a/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.rs b/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.rs
new file mode 100644
index 00000000000..c1bfcc73402
--- /dev/null
+++ b/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.rs
@@ -0,0 +1,6 @@
+// This used to ICE in exhaustiveness checking. Explanation here:
+// https://github.com/rust-lang/rust/issues/82772#issuecomment-905946768
+fn main() {
+    let Box { 1: _, .. }: Box<()>; //~ ERROR field `1` of
+    let Box { .. }: Box<()>;
+}
diff --git a/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.stderr b/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.stderr
new file mode 100644
index 00000000000..2c8c85bb1e0
--- /dev/null
+++ b/src/test/ui/pattern/usefulness/issue-82772-match-box-as-struct.stderr
@@ -0,0 +1,9 @@
+error[E0451]: field `1` of struct `Box` is private
+  --> $DIR/issue-82772-match-box-as-struct.rs:4:15
+   |
+LL |     let Box { 1: _, .. }: Box<()>;
+   |               ^^^^ private field
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0451`.