Auto merge of #117611 - Nadrieril:linear-pass-take-4, r=cjgillot

Rewrite exhaustiveness in one pass

This is at least my 4th attempt at this in as many years x) Previous attempts were all too complicated or too slow. But we're finally here!

The previous version of the exhaustiveness algorithm computed reachability for each arm then exhaustiveness of the whole match. Since each of these steps does roughly the same things, this rewrites the algorithm to do them all in one go. I also think this makes things much simpler.

I also rewrote the documentation of the algorithm in depth. Hopefully it's up-to-date and easier to follow now. Plz comment if anything's unclear.

r? `@oli-obk` I think you're one of the rare other people to understand the exhaustiveness algorithm?

cc `@varkor` I know you're not active anymore, but if you feel like having a look you might enjoy this :D

Fixes https://github.com/rust-lang/rust/issues/79307

18 files changed, 1294 insertions, 1002 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 4cc3bbfcf43..e402468f038 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -279,8 +279,10 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         } else {
             // Check the pattern for some things unrelated to exhaustiveness.
             let refutable = if cx.refutable { Refutable } else { Irrefutable };
-            pat.walk_always(|pat| check_borrow_conflicts_in_at_patterns(self, pat));
-            pat.walk_always(|pat| check_for_bindings_named_same_as_variants(self, pat, refutable));
+            pat.walk_always(|pat| {
+                check_borrow_conflicts_in_at_patterns(self, pat);
+                check_for_bindings_named_same_as_variants(self, pat, refutable);
+            });
             Ok(cx.pattern_arena.alloc(DeconstructedPat::from_pat(cx, pat)))
         }
     }
@@ -289,6 +291,7 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         &self,
         refutability: RefutableFlag,
         match_span: Option<Span>,
+        scrut_span: Span,
     ) -> MatchCheckCtxt<'p, 'tcx> {
         let refutable = match refutability {
             Irrefutable => false,
@@ -299,7 +302,9 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
             param_env: self.param_env,
             module: self.tcx.parent_module(self.lint_level).to_def_id(),
             pattern_arena: self.pattern_arena,
+            match_lint_level: self.lint_level,
             match_span,
+            scrut_span,
             refutable,
         }
     }
@@ -330,7 +335,8 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         source: hir::MatchSource,
         expr_span: Span,
     ) {
-        let cx = self.new_cx(Refutable, Some(expr_span));
+        let scrut = &self.thir[scrut];
+        let cx = self.new_cx(Refutable, Some(expr_span), scrut.span);
 
         let mut tarms = Vec::with_capacity(arms.len());
         for &arm in arms {
@@ -346,9 +352,8 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
             }
         }
 
-        let scrut = &self.thir[scrut];
         let scrut_ty = scrut.ty;
-        let report = compute_match_usefulness(&cx, &tarms, self.lint_level, scrut_ty, scrut.span);
+        let report = compute_match_usefulness(&cx, &tarms, scrut_ty);
 
         match source {
             // Don't report arm reachability of desugared `match $iter.into_iter() { iter => .. }`
@@ -453,10 +458,10 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> {
         pat: &Pat<'tcx>,
         refutability: RefutableFlag,
     ) -> Result<(MatchCheckCtxt<'p, 'tcx>, UsefulnessReport<'p, 'tcx>), ErrorGuaranteed> {
-        let cx = self.new_cx(refutability, None);
+        let cx = self.new_cx(refutability, None, pat.span);
         let pat = self.lower_pattern(&cx, pat)?;
         let arms = [MatchArm { pat, hir_id: self.lint_level, has_guard: false }];
-        let report = compute_match_usefulness(&cx, &arms, self.lint_level, pat.ty(), pat.span());
+        let report = compute_match_usefulness(&cx, &arms, pat.ty());
         Ok((cx, report))
     }
 
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 479f6c0a3ca..8ddc6c924e2 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
@@ -1,46 +1,88 @@
-//! [`super::usefulness`] explains most of what is happening in this file. As explained there,
-//! values and patterns are made from constructors applied to fields. This file defines a
-//! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert
-//! them from/to patterns.
+//! As explained in [`super::usefulness`], values and patterns are made from constructors applied to
+//! fields. This file defines a `Constructor` enum, a `Fields` struct, and various operations to
+//! manipulate them and convert them from/to patterns.
 //!
-//! There's one idea that is not detailed in [`super::usefulness`] because the details are not
-//! needed there: _constructor splitting_.
+//! There are two important bits of core logic in this file: constructor inclusion and constructor
+//! splitting. Constructor inclusion, i.e. whether a constructor is included in/covered by another,
+//! is straightforward and defined in [`Constructor::is_covered_by`].
 //!
-//! # Constructor splitting
+//! Constructor splitting is mentioned in [`super::usefulness`] but not detailed. We describe it
+//! precisely here.
 //!
-//! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn
-//! with all the value constructors that are covered by `c`, and compute usefulness for each.
-//! Instead of listing all those constructors (which is intractable), we group those value
-//! constructors together as much as possible. Example:
 //!
+//! # Constructor grouping and splitting
+//!
+//! As explained in the corresponding section in [`super::usefulness`], to make usefulness tractable
+//! we need to group together constructors that have the same effect when they are used to
+//! specialize the matrix.
+//!
+//! Example:
 //! ```compile_fail,E0004
 //! match (0, false) {
-//!     (0 ..=100, true) => {} // `p_1`
-//!     (50..=150, false) => {} // `p_2`
-//!     (0 ..=200, _) => {} // `q`
+//!     (0 ..=100, true) => {}
+//!     (50..=150, false) => {}
+//!     (0 ..=200, _) => {}
 //! }
 //! ```
 //!
-//! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more
-//! clever: `0` and `1` for example will match the exact same rows, and return equivalent
-//! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4
-//! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely
-//! more tractable.
+//! In this example we can restrict specialization to 5 cases: `0..50`, `50..=100`, `101..=150`,
+//! `151..=200` and `200..`.
+//!
+//! In [`super::usefulness`], we had said that `specialize` only takes value-only constructors. We
+//! now relax this restriction: we allow `specialize` to take constructors like `0..50` as long as
+//! we're careful to only do that with constructors that make sense. For example, `specialize(0..50,
+//! (0..=100, true))` is sensible, but `specialize(50..=200, (0..=100, true))` is not.
+//!
+//! Constructor splitting looks at the constructors in the first column of the matrix and constructs
+//! such a sensible set of constructors. Formally, we want to find a smallest disjoint set of
+//! constructors:
+//! - Whose union covers the whole type, and
+//! - That have no non-trivial intersection with any of the constructors in the column (i.e. they're
+//!     each either disjoint with or covered by any given column constructor).
+//!
+//! We compute this in two steps: first [`ConstructorSet::for_ty`] determines the set of all
+//! possible constructors for the type. Then [`ConstructorSet::split`] looks at the column of
+//! constructors and splits the set into groups accordingly. The precise invariants of
+//! [`ConstructorSet::split`] is described in [`SplitConstructorSet`].
+//!
+//! Constructor splitting has two interesting special cases: integer range splitting (see
+//! [`IntRange::split`]) and slice splitting (see [`Slice::split`]).
+//!
+//!
+//! # The `Missing` constructor
+//!
+//! We detail a special case of constructor splitting that is a bit subtle. Take the following:
+//!
+//! ```
+//! enum Direction { North, South, East, West }
+//! # let wind = (Direction::North, 0u8);
+//! match wind {
+//!     (Direction::North, 50..) => {}
+//!     (_, _) => {}
+//! }
+//! ```
+//!
+//! Here we expect constructor splitting to output two cases: `North`, and "everything else". This
+//! "everything else" is represented by [`Constructor::Missing`]. Unlike other constructors, it's a
+//! bit contextual: to know the exact list of constructors it represents we have to look at the
+//! column. In practice however we don't need to, because by construction it only matches rows that
+//! have wildcards. This is how this constructor is special: the only constructor that covers it is
+//! `Wildcard`.
+//!
+//! The only place where we care about which constructors `Missing` represents is in diagnostics
+//! (see `super::usefulness::WitnessMatrix::apply_constructor`).
 //!
-//! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors
-//! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'`
-//! return an equivalent set of witnesses after specializing and computing usefulness.
-//! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ
-//! in their first element.
+//! We choose whether to specialize with `Missing` in
+//! `super::usefulness::compute_exhaustiveness_and_reachability`.
 //!
-//! We usually also ask that the `c'` together cover all of the original `c`. However we allow
-//! skipping some constructors as long as it doesn't change whether the resulting list of witnesses
-//! is empty of not. We use this in the wildcard `_` case.
 //!
-//! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for
-//! or-patterns; instead we just try the alternatives one-by-one. For details on splitting
-//! wildcards, see [`Constructor::split`]; for integer ranges, see
-//! [`IntRange::split`]; for slices, see [`Slice::split`].
+//!
+//! ## Opaque patterns
+//!
+//! Some patterns, such as constants that are not allowed to be matched structurally, cannot be
+//! inspected, which we handle with `Constructor::Opaque`. Since we know nothing of these patterns,
+//! we assume they never cover each other. In order to respect the invariants of
+//! [`SplitConstructorSet`], we give each `Opaque` constructor a unique id so we can recognize it.
 
 use std::cell::Cell;
 use std::cmp::{self, max, min, Ordering};
@@ -617,6 +659,18 @@ impl Slice {
     }
 }
 
+/// A globally unique id to distinguish `Opaque` patterns.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(super) struct OpaqueId(u32);
+
+impl OpaqueId {
+    fn new() -> Self {
+        use std::sync::atomic::{AtomicU32, Ordering};
+        static OPAQUE_ID: AtomicU32 = AtomicU32::new(0);
+        OpaqueId(OPAQUE_ID.fetch_add(1, Ordering::SeqCst))
+    }
+}
+
 /// A value can be decomposed into a constructor applied to some fields. This struct represents
 /// the constructor. See also `Fields`.
 ///
@@ -626,8 +680,8 @@ impl Slice {
 /// `Fields`.
 #[derive(Clone, Debug, PartialEq)]
 pub(super) enum Constructor<'tcx> {
-    /// The constructor for patterns that have a single constructor, like tuples, struct patterns
-    /// and fixed-length arrays.
+    /// The constructor for patterns that have a single constructor, like tuples, struct patterns,
+    /// and references. Fixed-length arrays are treated separately with `Slice`.
     Single,
     /// Enum variants.
     Variant(VariantIdx),
@@ -642,10 +696,12 @@ pub(super) enum Constructor<'tcx> {
     Str(mir::Const<'tcx>),
     /// Array and slice patterns.
     Slice(Slice),
-    /// Constants that must not be matched structurally. They are treated as black
-    /// boxes for the purposes of exhaustiveness: we must not inspect them, and they
-    /// don't count towards making a match exhaustive.
-    Opaque,
+    /// Constants that must not be matched structurally. They are treated as black boxes for the
+    /// purposes of exhaustiveness: we must not inspect them, and they don't count towards making a
+    /// match exhaustive.
+    /// Carries an id that must be unique within a match. We need this to ensure the invariants of
+    /// [`SplitConstructorSet`].
+    Opaque(OpaqueId),
     /// Or-pattern.
     Or,
     /// Wildcard pattern.
@@ -657,12 +713,15 @@ pub(super) enum Constructor<'tcx> {
     /// We use this for variants behind an unstable gate as well as
     /// `#[doc(hidden)]` ones.
     Hidden,
-    /// Fake extra constructor for constructors that are not seen in the matrix, as explained in the
-    /// code for [`Constructor::split`].
+    /// Fake extra constructor for constructors that are not seen in the matrix, as explained at the
+    /// top of the file.
     Missing,
 }
 
 impl<'tcx> Constructor<'tcx> {
+    pub(super) fn is_wildcard(&self) -> bool {
+        matches!(self, Wildcard)
+    }
     pub(super) fn is_non_exhaustive(&self) -> bool {
         matches!(self, NonExhaustive)
     }
@@ -728,7 +787,7 @@ impl<'tcx> Constructor<'tcx> {
             | F32Range(..)
             | F64Range(..)
             | Str(..)
-            | Opaque
+            | Opaque(..)
             | NonExhaustive
             | Hidden
             | Missing { .. }
@@ -737,109 +796,23 @@ impl<'tcx> Constructor<'tcx> {
         }
     }
 
-    /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of
-    /// actual constructors (like variants, integers or fixed-sized slices). When specializing for
-    /// these constructors, we want to be specialising for the actual underlying constructors.
-    /// Naively, we would simply return the list of constructors they correspond to. We instead are
-    /// more clever: if there are constructors that we know will behave the same w.r.t. the current
-    /// matrix, we keep them grouped. For example, all slices of a sufficiently large length will
-    /// either be all useful or all non-useful with a given matrix.
-    ///
-    /// See the branches for details on how the splitting is done.
-    ///
-    /// This function may discard some irrelevant constructors if this preserves behavior. Eg. for
-    /// the `_` case, we ignore the constructors already present in the column, unless all of them
-    /// are.
-    pub(super) fn split<'a>(
-        &self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
-    ) -> SmallVec<[Self; 1]>
-    where
-        'tcx: 'a,
-    {
-        match self {
-            Wildcard => {
-                let split_set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, ctors);
-                if !split_set.missing.is_empty() {
-                    // We are splitting a wildcard in order to compute its usefulness. Some constructors are
-                    // not present in the column. The first thing we note is that specializing with any of
-                    // the missing constructors would select exactly the rows with wildcards. Moreover, they
-                    // would all return equivalent results. We can therefore group them all into a
-                    // fictitious `Missing` constructor.
-                    //
-                    // As an important optimization, this function will skip all the present constructors.
-                    // This is correct because specializing with any of the present constructors would
-                    // select a strict superset of the wildcard rows, and thus would only find witnesses
-                    // already found with the `Missing` constructor.
-                    // This does mean that diagnostics are incomplete: in
-                    // ```
-                    // match x {
-                    //   Some(true) => {}
-                    // }
-                    // ```
-                    // we report `None` as missing but not `Some(false)`.
-                    //
-                    // When all the constructors are missing we can equivalently return the `Wildcard`
-                    // constructor on its own. The difference between `Wildcard` and `Missing` will then
-                    // only be in diagnostics.
-
-                    // If some constructors are missing, we typically want to report those constructors,
-                    // e.g.:
-                    // ```
-                    //     enum Direction { N, S, E, W }
-                    //     let Direction::N = ...;
-                    // ```
-                    // we can report 3 witnesses: `S`, `E`, and `W`.
-                    //
-                    // However, if the user didn't actually specify a constructor
-                    // in this arm, e.g., in
-                    // ```
-                    //     let x: (Direction, Direction, bool) = ...;
-                    //     let (_, _, false) = x;
-                    // ```
-                    // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>,
-                    // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we
-                    // prefer to report just a wildcard `_`.
-                    //
-                    // The exception is: if we are at the top-level, for example in an empty match, we
-                    // usually prefer to report the full list of constructors.
-                    let all_missing = split_set.present.is_empty();
-                    let report_when_all_missing =
-                        pcx.is_top_level && !IntRange::is_integral(pcx.ty);
-                    let ctor =
-                        if all_missing && !report_when_all_missing { Wildcard } else { Missing };
-                    smallvec![ctor]
-                } else {
-                    split_set.present
-                }
-            }
-            // Fast-track if the range is trivial.
-            IntRange(this_range) if !this_range.is_singleton() => {
-                let column_ranges = ctors.filter_map(|ctor| ctor.as_int_range()).cloned();
-                this_range.split(column_ranges).map(|(_, range)| IntRange(range)).collect()
-            }
-            Slice(this_slice @ Slice { kind: VarLen(..), .. }) => {
-                let column_slices = ctors.filter_map(|c| c.as_slice());
-                this_slice.split(column_slices).map(|(_, slice)| Slice(slice)).collect()
-            }
-            // Any other constructor can be used unchanged.
-            _ => smallvec![self.clone()],
-        }
-    }
-
     /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
     /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
     /// this checks for inclusion.
     // We inline because this has a single call site in `Matrix::specialize_constructor`.
     #[inline]
     pub(super) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool {
-        // This must be kept in sync with `is_covered_by_any`.
         match (self, other) {
+            (Wildcard, _) => {
+                span_bug!(
+                    pcx.cx.scrut_span,
+                    "Constructor splitting should not have returned `Wildcard`"
+                )
+            }
             // Wildcards cover anything
             (_, Wildcard) => true,
             // Only a wildcard pattern can match these special constructors.
-            (Wildcard | Missing { .. } | NonExhaustive | Hidden, _) => false,
+            (Missing { .. } | NonExhaustive | Hidden, _) => false,
 
             (Single, Single) => true,
             (Variant(self_id), Variant(other_id)) => self_id == other_id,
@@ -869,11 +842,13 @@ impl<'tcx> Constructor<'tcx> {
             }
             (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
 
-            // We are trying to inspect an opaque constant. Thus we skip the row.
-            (Opaque, _) | (_, Opaque) => false,
+            // Opaque constructors don't interact with anything unless they come from the
+            // syntactically identical pattern.
+            (Opaque(self_id), Opaque(other_id)) => self_id == other_id,
+            (Opaque(..), _) | (_, Opaque(..)) => false,
 
             _ => span_bug!(
-                pcx.span,
+                pcx.cx.scrut_span,
                 "trying to compare incompatible constructors {:?} and {:?}",
                 self,
                 other
@@ -917,16 +892,20 @@ pub(super) enum ConstructorSet {
 /// `present` is morally the set of constructors present in the column, and `missing` is the set of
 /// constructors that exist in the type but are not present in the column.
 ///
-/// More formally, they respect the following constraints:
-/// - the union of `present` and `missing` covers the whole type
-/// - `present` and `missing` are disjoint
-/// - neither contains wildcards
-/// - each constructor in `present` is covered by some non-wildcard constructor in the column
-/// - together, the constructors in `present` cover all the non-wildcard constructor in the column
-/// - non-wildcards in the column do no cover anything in `missing`
-/// - constructors in `present` and `missing` are split for the column; in other words, they are
-///     either fully included in or disjoint from each constructor in the column. This avoids
-///     non-trivial intersections like between `0..10` and `5..15`.
+/// More formally, if we discard wildcards from the column, this respects the following constraints:
+/// 1. the union of `present` and `missing` covers the whole type
+/// 2. each constructor in `present` is covered by something in the column
+/// 3. no constructor in `missing` is covered by anything in the column
+/// 4. each constructor in the column is equal to the union of one or more constructors in `present`
+/// 5. `missing` does not contain empty constructors (see discussion about emptiness at the top of
+///    the file);
+/// 6. constructors in `present` and `missing` are split for the column; in other words, they are
+///    either fully included in or fully disjoint from each constructor in the column. In other
+///    words, there are no non-trivial intersections like between `0..10` and `5..15`.
+///
+/// We must be particularly careful with weird constructors like `Opaque`: they're not formally part
+/// of the `ConstructorSet` for the type, yet if we forgot to include them in `present` we would be
+/// ignoring any row with `Opaque`s in the algorithm. Hence the importance of point 4.
 #[derive(Debug)]
 pub(super) struct SplitConstructorSet<'tcx> {
     pub(super) present: SmallVec<[Constructor<'tcx>; 1]>,
@@ -934,6 +913,7 @@ pub(super) struct SplitConstructorSet<'tcx> {
 }
 
 impl ConstructorSet {
+    /// Creates a set that represents all the constructors of `ty`.
     #[instrument(level = "debug", skip(cx), ret)]
     pub(super) fn for_ty<'p, 'tcx>(cx: &MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
         let make_range = |start, end| {
@@ -1069,9 +1049,10 @@ impl ConstructorSet {
         }
     }
 
-    /// This is the core logical operation of exhaustiveness checking. This analyzes a column a
-    /// constructors to 1/ determine which constructors of the type (if any) are missing; 2/ split
-    /// constructors to handle non-trivial intersections e.g. on ranges or slices.
+    /// This analyzes a column of constructors to 1/ determine which constructors of the type (if
+    /// any) are missing; 2/ split constructors to handle non-trivial intersections e.g. on ranges
+    /// or slices. This can get subtle; see [`SplitConstructorSet`] for details of this operation
+    /// and its invariants.
     #[instrument(level = "debug", skip(self, pcx, ctors), ret)]
     pub(super) fn split<'a, 'tcx>(
         &self,
@@ -1083,18 +1064,26 @@ impl ConstructorSet {
     {
         let mut present: SmallVec<[_; 1]> = SmallVec::new();
         let mut missing = Vec::new();
-        // Constructors in `ctors`, except wildcards.
-        let mut seen = ctors.filter(|c| !(matches!(c, Opaque | Wildcard)));
+        // Constructors in `ctors`, except wildcards and opaques.
+        let mut seen = Vec::new();
+        for ctor in ctors.cloned() {
+            if let Constructor::Opaque(..) = ctor {
+                present.push(ctor);
+            } else if !ctor.is_wildcard() {
+                seen.push(ctor);
+            }
+        }
+
         match self {
             ConstructorSet::Single => {
-                if seen.next().is_none() {
+                if seen.is_empty() {
                     missing.push(Single);
                 } else {
                     present.push(Single);
                 }
             }
             ConstructorSet::Variants { visible_variants, hidden_variants, non_exhaustive } => {
-                let seen_set: FxHashSet<_> = seen.map(|c| c.as_variant().unwrap()).collect();
+                let seen_set: FxHashSet<_> = seen.iter().map(|c| c.as_variant().unwrap()).collect();
                 let mut skipped_a_hidden_variant = false;
 
                 for variant in visible_variants {
@@ -1125,7 +1114,7 @@ impl ConstructorSet {
             ConstructorSet::Bool => {
                 let mut seen_false = false;
                 let mut seen_true = false;
-                for b in seen.map(|ctor| ctor.as_bool().unwrap()) {
+                for b in seen.iter().map(|ctor| ctor.as_bool().unwrap()) {
                     if b {
                         seen_true = true;
                     } else {
@@ -1145,7 +1134,7 @@ impl ConstructorSet {
             }
             ConstructorSet::Integers { range_1, range_2 } => {
                 let seen_ranges: Vec<_> =
-                    seen.map(|ctor| ctor.as_int_range().unwrap().clone()).collect();
+                    seen.iter().map(|ctor| ctor.as_int_range().unwrap().clone()).collect();
                 for (seen, splitted_range) in range_1.split(seen_ranges.iter().cloned()) {
                     match seen {
                         Presence::Unseen => missing.push(IntRange(splitted_range)),
@@ -1162,7 +1151,7 @@ impl ConstructorSet {
                 }
             }
             &ConstructorSet::Slice(array_len) => {
-                let seen_slices = seen.map(|c| c.as_slice().unwrap());
+                let seen_slices = seen.iter().map(|c| c.as_slice().unwrap());
                 let base_slice = Slice::new(array_len, VarLen(0, 0));
                 for (seen, splitted_slice) in base_slice.split(seen_slices) {
                     let ctor = Slice(splitted_slice);
@@ -1178,7 +1167,7 @@ impl ConstructorSet {
                 // unreachable if length != 0.
                 // We still gather the seen constructors in `present`, but the only slice that can
                 // go in `missing` is `[]`.
-                let seen_slices = seen.map(|c| c.as_slice().unwrap());
+                let seen_slices = seen.iter().map(|c| c.as_slice().unwrap());
                 let base_slice = Slice::new(None, VarLen(0, 0));
                 for (seen, splitted_slice) in base_slice.split(seen_slices) {
                     let ctor = Slice(splitted_slice);
@@ -1194,7 +1183,7 @@ impl ConstructorSet {
             ConstructorSet::Unlistable => {
                 // Since we can't list constructors, we take the ones in the column. This might list
                 // some constructors several times but there's not much we can do.
-                present.extend(seen.cloned());
+                present.extend(seen);
                 missing.push(NonExhaustive);
             }
             // If `exhaustive_patterns` is disabled and our scrutinee is an empty type, we cannot
@@ -1210,19 +1199,6 @@ impl ConstructorSet {
 
         SplitConstructorSet { present, missing }
     }
-
-    /// Compute the set of constructors missing from this column.
-    /// This is only used for reporting to the user.
-    pub(super) fn compute_missing<'a, 'tcx>(
-        &self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
-    ) -> Vec<Constructor<'tcx>>
-    where
-        'tcx: 'a,
-    {
-        self.split(pcx, ctors).missing
-    }
 }
 
 /// A value can be decomposed into a constructor applied to some fields. This struct represents
@@ -1273,9 +1249,8 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
     fn wildcards_from_tys(
         cx: &MatchCheckCtxt<'p, 'tcx>,
         tys: impl IntoIterator<Item = Ty<'tcx>>,
-        span: Span,
     ) -> Self {
-        Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, span)))
+        Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, DUMMY_SP)))
     }
 
     // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide
@@ -1311,18 +1286,18 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
     pub(super) fn wildcards(pcx: &PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self {
         let ret = match constructor {
             Single | Variant(_) => match pcx.ty.kind() {
-                ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter(), pcx.span),
-                ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty), pcx.span),
+                ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter()),
+                ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty)),
                 ty::Adt(adt, args) => {
                     if adt.is_box() {
                         // The only legal patterns of type `Box` (outside `std`) are `_` and box
                         // patterns. If we're here we can assume this is a box pattern.
-                        Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0)), pcx.span)
+                        Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0)))
                     } else {
                         let variant = &adt.variant(constructor.variant_index_for_adt(*adt));
                         let tys = Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant)
                             .map(|(_, ty)| ty);
-                        Fields::wildcards_from_tys(pcx.cx, tys, pcx.span)
+                        Fields::wildcards_from_tys(pcx.cx, tys)
                     }
                 }
                 _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx),
@@ -1330,7 +1305,7 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
             Slice(slice) => match *pcx.ty.kind() {
                 ty::Slice(ty) | ty::Array(ty, _) => {
                     let arity = slice.arity();
-                    Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty), pcx.span)
+                    Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty))
                 }
                 _ => bug!("bad slice pattern {:?} {:?}", constructor, pcx),
             },
@@ -1339,7 +1314,7 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
             | F32Range(..)
             | F64Range(..)
             | Str(..)
-            | Opaque
+            | Opaque(..)
             | NonExhaustive
             | Hidden
             | Missing { .. }
@@ -1388,6 +1363,8 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) }
     }
 
+    /// Note: the input patterns must have been lowered through
+    /// `super::check_match::MatchVisitor::lower_pattern`.
     pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self {
         let mkpat = |pat| DeconstructedPat::from_pat(cx, pat);
         let ctor;
@@ -1470,14 +1447,14 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                     ty::Bool => {
                         ctor = match value.try_eval_bool(cx.tcx, cx.param_env) {
                             Some(b) => Bool(b),
-                            None => Opaque,
+                            None => Opaque(OpaqueId::new()),
                         };
                         fields = Fields::empty();
                     }
                     ty::Char | ty::Int(_) | ty::Uint(_) => {
                         ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
                             Some(bits) => IntRange(IntRange::from_bits(cx.tcx, pat.ty, bits)),
-                            None => Opaque,
+                            None => Opaque(OpaqueId::new()),
                         };
                         fields = Fields::empty();
                     }
@@ -1488,7 +1465,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                                 let value = rustc_apfloat::ieee::Single::from_bits(bits);
                                 F32Range(value, value, RangeEnd::Included)
                             }
-                            None => Opaque,
+                            None => Opaque(OpaqueId::new()),
                         };
                         fields = Fields::empty();
                     }
@@ -1499,7 +1476,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                                 let value = rustc_apfloat::ieee::Double::from_bits(bits);
                                 F64Range(value, value, RangeEnd::Included)
                             }
-                            None => Opaque,
+                            None => Opaque(OpaqueId::new()),
                         };
                         fields = Fields::empty();
                     }
@@ -1520,7 +1497,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                     // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are
                     // opaque.
                     _ => {
-                        ctor = Opaque;
+                        ctor = Opaque(OpaqueId::new());
                         fields = Fields::empty();
                     }
                 }
@@ -1581,7 +1558,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                 fields = Fields::from_iter(cx, pats.into_iter().map(mkpat));
             }
             PatKind::Error(_) => {
-                ctor = Opaque;
+                ctor = Opaque(OpaqueId::new());
                 fields = Fields::empty();
             }
         }
@@ -1591,6 +1568,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
     pub(super) fn is_or_pat(&self) -> bool {
         matches!(self.ctor, Or)
     }
+    /// Expand this (possibly-nested) or-pattern into its alternatives.
     pub(super) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> {
         if self.is_or_pat() {
             self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect()
@@ -1646,7 +1624,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
                         let wildcard: &_ = pcx
                             .cx
                             .pattern_arena
-                            .alloc(DeconstructedPat::wildcard(inner_ty, pcx.span));
+                            .alloc(DeconstructedPat::wildcard(inner_ty, DUMMY_SP));
                         let extra_wildcards = other_slice.arity() - self_slice.arity();
                         let extra_wildcards = (0..extra_wildcards).map(|_| wildcard);
                         prefix.iter().chain(extra_wildcards).chain(suffix).collect()
@@ -1663,7 +1641,17 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         self.reachable.set(true)
     }
     pub(super) fn is_reachable(&self) -> bool {
-        self.reachable.get()
+        if self.reachable.get() {
+            true
+        } else if self.is_or_pat() && self.iter_fields().any(|f| f.is_reachable()) {
+            // We always expand or patterns in the matrix, so we will never see the actual
+            // or-pattern (the one with constructor `Or`) in the column. As such, it will not be
+            // marked as reachable itself, only its children will. We recover this information here.
+            self.set_reachable();
+            true
+        } else {
+            false
+        }
     }
 
     /// Report the spans of subpatterns that were not reachable, if any.
@@ -1672,7 +1660,6 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         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() {
@@ -1768,7 +1755,7 @@ impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> {
             F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
             F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
             Str(value) => write!(f, "{value}"),
-            Opaque => write!(f, "<constant pattern>"),
+            Opaque(..) => write!(f, "<constant pattern>"),
             Or => {
                 for pat in self.iter_fields() {
                     write!(f, "{}{:?}", start_or_continue(" | "), pat)?;
@@ -1898,7 +1885,7 @@ impl<'tcx> WitnessPat<'tcx> {
                 "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
                 `Missing` should have been processed in `apply_constructors`"
             ),
-            F32Range(..) | F64Range(..) | Opaque | Or => {
+            F32Range(..) | F64Range(..) | Opaque(..) | Or => {
                 bug!("can't convert to pattern: {:?}", self)
             }
         };
diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
index 461c44a169c..8f017833531 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
@@ -1,46 +1,55 @@
-//! Note: tests specific to this file can be found in:
+//! # Match exhaustiveness and reachability algorithm
 //!
-//!   - `ui/pattern/usefulness`
-//!   - `ui/or-patterns`
-//!   - `ui/consts/const_in_pattern`
-//!   - `ui/rfc-2008-non-exhaustive`
-//!   - `ui/half-open-range-patterns`
-//!   - probably many others
+//! This file contains the logic for exhaustiveness and reachability checking for pattern-matching.
+//! Specifically, given a list of patterns in a match, we can tell whether:
+//! (a) a given pattern is reachable (reachability)
+//! (b) the patterns cover every possible value for the type (exhaustiveness)
 //!
-//! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
-//! reason not to, for example if they depend on a particular feature like `or_patterns`.
+//! The algorithm implemented here is inspired from the one described in [this
+//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however changed it in
+//! various ways to accommodate the variety of patterns that Rust supports. We thus explain our
+//! version here, without being as precise.
 //!
-//! -----
+//! Fun fact: computing exhaustiveness is NP-complete, because we can encode a SAT problem as an
+//! exhaustiveness problem. See [here](https://niedzejkob.p4.team/rust-np) for the fun details.
 //!
-//! This file includes the logic for exhaustiveness and reachability checking for pattern-matching.
-//! Specifically, given a list of patterns for a type, we can tell whether:
-//! (a) each pattern is reachable (reachability)
-//! (b) the patterns cover every possible value for the type (exhaustiveness)
 //!
-//! The algorithm implemented here is a modified version of the one described in [this
-//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized
-//! it to accommodate the variety of patterns that Rust supports. We thus explain our version here,
-//! without being as rigorous.
+//! # Summary
 //!
+//! The algorithm is given as input a list of patterns, one for each arm of a match, and computes
+//! the following:
+//! - a set of values that match none of the patterns (if any),
+//! - for each subpattern (taking into account or-patterns), whether it would catch any value that
+//!     isn't caught by a pattern before it, i.e. whether it is reachable.
 //!
-//! # Summary
+//! To a first approximation, the algorithm works by exploring all possible values for the type
+//! being matched on, and determining which arm(s) catch which value. To make this tractable we
+//! cleverly group together values, as we'll see below.
 //!
-//! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful*
-//! relative to another pattern `p` of the same type if there is a value that is matched by `q` and
-//! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns
-//! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write
-//! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this
-//! file is to compute it efficiently.
-//!
-//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it
-//! is useful w.r.t. the patterns above it:
-//! ```rust
-//! # fn foo(x: Option<i32>) {
-//! match x {
-//!     Some(_) => {},
-//!     None => {},    // reachable: `None` is matched by this but not the branch above
-//!     Some(0) => {}, // unreachable: all the values this matches are already matched by
-//!                    // `Some(_)` above
+//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes
+//! reachability for each subpattern and exhaustiveness for the whole match.
+//!
+//! In this page we explain the necessary concepts to understand how the algorithm works.
+//!
+//!
+//! # Usefulness
+//!
+//! The central concept of this file is the notion of "usefulness". Given some patterns `p_1 ..
+//! p_n`, a pattern `q` is said to be *useful* if there is a value that is matched by `q` and by
+//! none of the `p_i`. We write `usefulness(p_1 .. p_n, q)` for a function that returns a list of
+//! such values. The aim of this file is to compute it efficiently.
+//!
+//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it is
+//! useful w.r.t. the patterns above it:
+//! ```compile_fail,E0004
+//! # #![feature(exclusive_range_pattern)]
+//! # fn foo() {
+//! match Some(0u32) {
+//!     Some(0..100) => {},
+//!     Some(90..190) => {}, // reachable: `Some(150)` is matched by this but not the branch above
+//!     Some(50..150) => {}, // unreachable: all the values this matches are already matched by
+//!                          //   the branches above
+//!     None => {},          // reachable: `None` is matched by this but not the branches above
 //! }
 //! # }
 //! ```
@@ -49,48 +58,35 @@
 //! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness`
 //! are used to tell the user which values are missing.
 //! ```compile_fail,E0004
-//! # fn foo(x: Option<i32>) {
+//! # fn foo(x: Option<u32>) {
 //! match x {
-//!     Some(0) => {},
 //!     None => {},
+//!     Some(0) => {},
 //!     // not exhaustive: `_` is useful because it matches `Some(1)`
 //! }
 //! # }
 //! ```
 //!
-//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes
-//! reachability for each match branch and exhaustiveness for the whole match.
-//!
 //!
 //! # Constructors and fields
 //!
-//! Note: we will often abbreviate "constructor" as "ctor".
-//!
-//! The idea that powers everything that is done in this file is the following: a (matchable)
-//! value is made from a constructor applied to a number of subvalues. Examples of constructors are
-//! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct
-//! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of
-//! pattern-matching, and this is the basis for what follows.
-//!
-//! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments.
-//! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of
-//! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge
-//! `enum`, with one variant for each number. This allows us to see any matchable value as made up
-//! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None,
-//! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`.
-//!
-//! This idea can be extended to patterns: they are also made from constructors applied to fields.
-//! A pattern for a given type is allowed to use all the ctors for values of that type (which we
-//! call "value constructors"), but there are also pattern-only ctors. The most important one is
-//! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x,
-//! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo
-//! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the
-//! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards.
-//!
-//! From this deconstruction we can compute whether a given value matches a given pattern; we
-//! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute
-//! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match
-//! we compare their fields recursively. A few representative examples:
+//! In the value `Pair(Some(0), true)`, `Pair` is called the constructor of the value, and `Some(0)`
+//! and `true` are its fields. Every matcheable value can be decomposed in this way. Examples of
+//! constructors are: `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor
+//! for a struct `Foo`), and `2` (the constructor for the number `2`).
+//!
+//! Each constructor takes a fixed number of fields; this is called its arity. `Pair` and `(,)` have
+//! arity 2, `Some` has arity 1, `None` and `42` have arity 0. Each type has a known set of
+//! constructors. Some types have many constructors (like `u64`) or even an infinitely many (like
+//! `&str` and `&[T]`).
+//!
+//! Patterns are similar: `Pair(Some(_), _)` has constructor `Pair` and two fields. The difference
+//! is that we get some extra pattern-only constructors, namely: the wildcard `_`, variable
+//! bindings, integer ranges like `0..=10`, and variable-length slices like `[_, .., _]`. We treat
+//! or-patterns separately, see the dedicated section below.
+//!
+//! Now to check if a value `v` matches a pattern `p`, we check if `v`'s constructor matches `p`'s
+//! constructor, then recursively compare their fields if necessary. A few representative examples:
 //!
 //! - `matches!(v, _) := true`
 //! - `matches!((v0,  v1), (p0,  p1)) := matches!(v0, p0) && matches!(v1, p1)`
@@ -100,213 +96,398 @@
 //! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)`
 //! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths)
 //! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)`
-//! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)`
 //!
-//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module.
+//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`]
+//! module. The question of whether a constructor is matched by another one is answered by
+//! [`Constructor::is_covered_by`].
 //!
-//! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type.
-//! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an
-//! infinitude of constructors. There are also subtleties with visibility of fields and
-//! uninhabitedness and various other things. The constructors idea can be extended to handle most
-//! of these subtleties though; caveats are documented where relevant throughout the code.
+//! Note 1: variable bindings (like the `x` in `Some(x)`) match anything, so we treat them as wildcards.
+//! Note 2: this only applies to matcheable values. For example a value of type `Rc<u64>` can't be
+//! deconstructed that way.
 //!
-//! Whether constructors cover each other is computed by [`Constructor::is_covered_by`].
 //!
 //!
 //! # Specialization
 //!
-//! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 ..
-//! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called
-//! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just
-//! enumerate all possible values. From the discussion above we see that we can proceed
-//! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with
-//! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can
-//! say from knowing only the first constructor of our candidate value.
+//! The examples in the previous section motivate the operation at the heart of the algorithm:
+//! "specialization". It captures this idea of "removing one layer of constructor".
+//!
+//! `specialize(c, p)` takes a value-only constructor `c` and a pattern `p`, and returns a
+//! pattern-tuple or nothing. It works as follows:
+//!
+//! - Specializing for the wrong constructor returns nothing
+//!
+//!   - `specialize(None, Some(p0)) := <nothing>`
+//!   - `specialize([,,,], [p0]) := <nothing>`
+//!
+//! - Specializing for the correct constructor returns a tuple of the fields
+//!
+//!   - `specialize(Variant1, Variant1(p0, p1, p2)) := (p0, p1, p2)`
+//!   - `specialize(Foo{ bar, baz, quz }, Foo { bar: p0, baz: p1, .. }) := (p0, p1, _)`
+//!   - `specialize([,,,], [p0, .., p1]) := (p0, _, _, p1)`
+//!
+//! We get the following property: for any values `v_1, .., v_n` of appropriate types, we have:
+//! ```text
+//! matches!(c(v_1, .., v_n), p)
+//! <=> specialize(c, p) returns something
+//!     && matches!((v_1, .., v_n), specialize(c, p))
+//! ```
+//!
+//! We also extend specialization to pattern-tuples by applying it to the first pattern:
+//! `specialize(c, (p_0, .., p_n)) := specialize(c, p_0) ++ (p_1, .., p_m)`
+//! where `++` is concatenation of tuples.
+//!
+//!
+//! The previous property extends to pattern-tuples:
+//! ```text
+//! matches!((c(v_1, .., v_n), w_1, .., w_m), (p_0, p_1, .., p_m))
+//! <=> specialize(c, p_0) does not error
+//!     && matches!((v_1, .., v_n, w_1, .., w_m), specialize(c, (p_0, p_1, .., p_m)))
+//! ```
+//!
+//! Whether specialization returns something or not is given by [`Constructor::is_covered_by`].
+//! Specialization of a pattern is computed in [`DeconstructedPat::specialize`]. Specialization for
+//! a pattern-tuple is computed in [`PatStack::pop_head_constructor`]. Finally, specialization for a
+//! set of pattern-tuples is computed in [`Matrix::specialize_constructor`].
+//!
+//!
+//!
+//! # Undoing specialization
+//!
+//! To construct witnesses we will need an inverse of specialization. If `c` is a constructor of
+//! arity `n`, we define `unspecialize` as:
+//! `unspecialize(c, (p_1, .., p_n, q_1, .., q_m)) := (c(p_1, .., p_n), q_1, .., q_m)`.
+//!
+//! This is done for a single witness-tuple in [`WitnessStack::apply_constructor`], and for a set of
+//! witness-tuples in [`WitnessMatrix::apply_constructor`].
+//!
+//!
+//!
+//! # Computing usefulness
+//!
+//! We now present a naive version of the algorithm for computing usefulness. From now on we operate
+//! on pattern-tuples.
+//!
+//! Let `pt_1, .., pt_n` and `qt` be length-m tuples of patterns for the same type `(T_1, .., T_m)`.
+//! We compute `usefulness(tp_1, .., tp_n, tq)` as follows:
+//!
+//! - Base case: `m == 0`.
+//!     The pattern-tuples are all empty, i.e. they're all `()`. Thus `tq` is useful iff there are
+//!     no rows above it, i.e. if `n == 0`. In that case we return `()` as a witness-tuple of
+//!     usefulness of `tq`.
+//!
+//! - Inductive case: `m > 0`.
+//!     In this naive version, we list all the possible constructors for values of type `T1` (we
+//!     will be more clever in the next section).
+//!
+//!     - For each such constructor `c` for which `specialize(c, tq)` is not nothing:
+//!         - We recursively compute `usefulness(specialize(c, tp_1) ... specialize(c, tp_n), specialize(c, tq))`,
+//!             where we discard any `specialize(c, p_i)` that returns nothing.
+//!         - For each witness-tuple `w` found, we apply `unspecialize(c, w)` to it.
+//!
+//!     - We return the all the witnesses found, if any.
+//!
 //!
 //! Let's take the following example:
 //! ```compile_fail,E0004
 //! # enum Enum { Variant1(()), Variant2(Option<bool>, u32)}
+//! # use Enum::*;
 //! # fn foo(x: Enum) {
 //! match x {
-//!     Enum::Variant1(_) => {} // `p1`
-//!     Enum::Variant2(None, 0) => {} // `p2`
-//!     Enum::Variant2(Some(_), 0) => {} // `q`
+//!     Variant1(_) => {} // `p1`
+//!     Variant2(None, 0) => {} // `p2`
+//!     Variant2(Some(_), 0) => {} // `q`
 //! }
 //! # }
 //! ```
 //!
-//! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`.
-//! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0`
-//! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple
-//! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match:
-//!
-//! ```compile_fail,E0004
-//! # fn foo(x: (Option<bool>, u32)) {
-//! match x {
-//!     (None, 0) => {} // `p2'`
-//!     (Some(_), 0) => {} // `q'`
-//! }
-//! # }
+//! To compute the usefulness of `q`, we would proceed as follows:
+//! ```text
+//! Start:
+//!   `tp1 = [Variant1(_)]`
+//!   `tp2 = [Variant2(None, 0)]`
+//!   `tq  = [Variant2(Some(true), 0)]`
+//!
+//!   Constructors are `Variant1` and `Variant2`. Only `Variant2` can specialize `tq`.
+//!   Specialize with `Variant2`:
+//!     `tp2 = [None, 0]`
+//!     `tq  = [Some(true), 0]`
+//!
+//!     Constructors are `None` and `Some`. Only `Some` can specialize `tq`.
+//!     Specialize with `Some`:
+//!       `tq  = [true, 0]`
+//!
+//!       Constructors are `false` and `true`. Only `true` can specialize `tq`.
+//!       Specialize with `true`:
+//!         `tq  = [0]`
+//!
+//!         Constructors are `0`, `1`, .. up to infinity. Only `0` can specialize `tq`.
+//!         Specialize with `0`:
+//!           `tq  = []`
+//!
+//!           m == 0 and n == 0, so `tq` is useful with witness `[]`.
+//!             `witness  = []`
+//!
+//!         Unspecialize with `0`:
+//!           `witness  = [0]`
+//!       Unspecialize with `true`:
+//!         `witness  = [true, 0]`
+//!     Unspecialize with `Some`:
+//!       `witness  = [Some(true), 0]`
+//!   Unspecialize with `Variant2`:
+//!     `witness  = [Variant2(Some(true), 0)]`
 //! ```
 //!
-//! This motivates a new step in computing usefulness, that we call _specialization_.
-//! Specialization consist of filtering a list of patterns for those that match a constructor, and
-//! then looking into the constructor's fields. This enables usefulness to be computed recursively.
-//!
-//! Instead of acting on a single pattern in each row, we will consider a list of patterns for each
-//! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the
-//! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels
-//! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`.
-//! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's
-//! happening:
-//! ```ignore (illustrative)
-//! [Enum::Variant1(_)]
-//! [Enum::Variant2(None, 0)]
-//! [Enum::Variant2(Some(_), 0)]
-//! //==>> specialize with `Variant2`
-//! [None, 0]
-//! [Some(_), 0]
-//! //==>> specialize with `Some`
-//! [_, 0]
-//! //==>> specialize with `true` (say the type was `bool`)
-//! [0]
-//! //==>> specialize with `0`
-//! []
-//! ```
+//! Therefore `usefulness(tp_1, tp_2, tq)` returns the single witness-tuple `[Variant2(Some(true), 0)]`.
 //!
-//! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0
-//! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing;
-//! otherwise if returns the fields of the constructor. This only returns more than one
-//! pattern-stack if `p` has a pattern-only constructor.
 //!
-//! - Specializing for the wrong constructor returns nothing
+//! Computing the set of constructors for a type is done in [`ConstructorSet::for_ty`]. See the
+//! following sections for more accurate versions of the algorithm and corresponding links.
 //!
-//!   `specialize(None, Some(p0)) := []`
 //!
-//! - Specializing for the correct constructor returns a single row with the fields
 //!
-//!   `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]`
+//! # Computing reachability and exhaustiveness in one go
 //!
-//!   `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]`
+//! The algorithm we have described so far computes usefulness of each pattern in turn to check if
+//! it is reachable, and ends by checking if `_` is useful to determine exhaustiveness of the whole
+//! match. In practice, instead of doing "for each pattern { for each constructor { ... } }", we do
+//! "for each constructor { for each pattern { ... } }". This allows us to compute everything in one
+//! go.
 //!
-//! - For or-patterns, we specialize each branch and concatenate the results
+//! [`Matrix`] stores the set of pattern-tuples under consideration. We track reachability of each
+//! row mutably in the matrix as we go along. We ignore witnesses of usefulness of the match rows.
+//! We gather witnesses of the usefulness of `_` in [`WitnessMatrix`]. The algorithm that computes
+//! all this is in [`compute_exhaustiveness_and_reachability`].
 //!
-//!   `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)`
+//! See the full example at the bottom of this documentation.
 //!
-//! - We treat the other pattern constructors as if they were a large or-pattern of all the
-//!   possibilities:
 //!
-//!   `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)`
 //!
-//!   `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)`
+//! # Making usefulness tractable: constructor splitting
 //!
-//!   `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)`
+//! We're missing one last detail: which constructors do we list? Naively listing all value
+//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The final
+//! clever idea for this algorithm is that we can group together constructors that behave the same.
 //!
-//! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See
-//!   the discussion about constructor splitting in [`super::deconstruct_pat`].
+//! Examples:
+//! ```compile_fail,E0004
+//! match (0, false) {
+//!     (0 ..=100, true) => {}
+//!     (50..=150, false) => {}
+//!     (0 ..=200, _) => {}
+//! }
+//! ```
 //!
+//! In this example, trying any of `0`, `1`, .., `49` will give the same specialized matrix, and
+//! thus the same reachability/exhaustiveness results. We can thus accelerate the algorithm by
+//! trying them all at once. Here in fact, the only cases we need to consider are: `0..50`,
+//! `50..=100`, `101..=150`,`151..=200` and `201..`.
 //!
-//! We then extend this function to work with pattern-stacks as input, by acting on the first
-//! column and keeping the other columns untouched.
+//! ```
+//! enum Direction { North, South, East, West }
+//! # let wind = (Direction::North, 0u8);
+//! match wind {
+//!     (Direction::North, 50..) => {}
+//!     (_, _) => {}
+//! }
+//! ```
 //!
-//! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that
-//! or-patterns in the first column are expanded before being stored in the matrix. Specialization
-//! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and
-//! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the
-//! [`super::deconstruct_pat::Fields`] struct.
+//! In this example, trying any of `South`, `East`, `West` will give the same specialized matrix. By
+//! the same reasoning, we only need to try two cases: `North`, and "everything else".
 //!
+//! We call _constructor splitting_ the operation that computes such a minimal set of cases to try.
+//! This is done in [`ConstructorSet::split`] and explained in [`super::deconstruct_pat`].
 //!
-//! # Computing usefulness
 //!
-//! We now have all we need to compute usefulness. The inputs to usefulness are a list of
-//! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this
-//! file calls the list of patstacks a _matrix_. They must all have the same number of columns and
-//! the patterns in a given column must all have the same type. `usefulness` returns a (possibly
-//! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks.
-//!
-//! - base case: `n_columns == 0`.
-//!     Since a pattern-stack functions like a tuple of patterns, an empty one functions like the
-//!     unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`.
-//!
-//! - inductive case: `n_columns > 0`.
-//!     We need a way to list the constructors we want to try. We will be more clever in the next
-//!     section but for now assume we list all value constructors for the type of the first column.
-//!
-//!     - for each such ctor `c`:
-//!
-//!         - for each `q'` returned by `specialize(c, q)`:
-//!
-//!             - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')`
-//!
-//!         - for each witness found, we revert specialization by pushing the constructor `c` on top.
-//!
-//!     - We return the concatenation of all the witnesses found, if any.
-//!
-//! Example:
-//! ```ignore (illustrative)
-//! [Some(true)] // p_1
-//! [None] // p_2
-//! [Some(_)] // q
-//! //==>> try `None`: `specialize(None, q)` returns nothing
-//! //==>> try `Some`: `specialize(Some, q)` returns a single row
-//! [true] // p_1'
-//! [_] // q'
-//! //==>> try `true`: `specialize(true, q')` returns a single row
-//! [] // p_1''
-//! [] // q''
-//! //==>> base case; `n != 0` so `q''` is not useful.
-//! //==>> go back up a step
-//! [true] // p_1'
-//! [_] // q'
-//! //==>> try `false`: `specialize(false, q')` returns a single row
-//! [] // q''
-//! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]`
-//! witnesses:
-//! []
-//! //==>> undo the specialization with `false`
-//! witnesses:
-//! [false]
-//! //==>> undo the specialization with `Some`
-//! witnesses:
-//! [Some(false)]
-//! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`.
-//! ```
+//! # Or-patterns
 //!
-//! This computation is done in [`is_useful`]. In practice we don't care about the list of
-//! witnesses when computing reachability; we only need to know whether any exist. We do keep the
-//! witnesses when computing exhaustiveness to report them to the user.
+//! What we have described so far works well if there are no or-patterns. To handle them, if the
+//! first pattern of a row in the matrix is an or-pattern, we expand it by duplicating the rest of
+//! the row as necessary. This is handled automatically in [`Matrix`].
 //!
+//! This makes reachability tracking subtle, because we also want to compute whether an alternative
+//! of an or-pattern is unreachable, e.g. in `Some(_) | Some(0)`. We track reachability of each
+//! subpattern by interior mutability in [`DeconstructedPat`] with `set_reachable`/`is_reachable`.
 //!
-//! # Making usefulness tractable: constructor splitting
+//! It's unfortunate that we have to use interior mutability, but believe me (Nadrieril), I have
+//! tried [other](https://github.com/rust-lang/rust/pull/80104)
+//! [solutions](https://github.com/rust-lang/rust/pull/80632) and nothing is remotely as simple.
 //!
-//! We're missing one last detail: which constructors do we list? Naively listing all value
-//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The
-//! first obvious insight is that we only want to list constructors that are covered by the head
-//! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only
-//! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we
-//! group together constructors that behave the same.
 //!
-//! The details are not necessary to understand this file, so we explain them in
-//! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function.
 //!
-//! # Constants in patterns
+//! # Constants and opaques
 //!
 //! There are two kinds of constants in patterns:
 //!
 //! * literals (`1`, `true`, `"foo"`)
 //! * named or inline consts (`FOO`, `const { 5 + 6 }`)
 //!
-//! The latter are converted into other patterns with literals at the leaves. For example
+//! The latter are converted into the corresponding patterns by a previous phase. For example
 //! `const_to_pat(const { [1, 2, 3] })` becomes an `Array(vec![Const(1), Const(2), Const(3)])`
 //! pattern. This gets problematic when comparing the constant via `==` would behave differently
-//! from matching on the constant converted to a pattern. Situations like that can occur, when
-//! the user implements `PartialEq` manually, and thus could make `==` behave arbitrarily different.
-//! In order to honor the `==` implementation, constants of types that implement `PartialEq` manually
-//! stay as a full constant and become an `Opaque` pattern. These `Opaque` patterns do not participate
-//! in exhaustiveness, specialization or overlap checking.
-
-use self::ArmType::*;
-use self::Usefulness::*;
+//! from matching on the constant converted to a pattern. The situation around this is currently
+//! unclear and the lang team is working on clarifying what we want to do there. In any case, there
+//! are constants we will not turn into patterns. We capture these with `Constructor::Opaque`. These
+//! `Opaque` patterns do not participate in exhaustiveness, specialization or overlap checking.
+//!
+//!
+//!
+//! # Full example
+//!
+//! We illustrate a full run of the algorithm on the following match.
+//!
+//! ```compile_fail,E0004
+//! # struct Pair(Option<u32>, bool);
+//! # fn foo(x: Pair) -> u32 {
+//! match x {
+//!     Pair(Some(0), _) => 1,
+//!     Pair(_, false) => 2,
+//!     Pair(Some(0), false) => 3,
+//! }
+//! # }
+//! ```
+//!
+//! We keep track of the original row for illustration purposes, this is not what the algorithm
+//! actually does (it tracks reachability as a boolean on each row).
+//!
+//! ```text
+//!  ┐ Patterns:
+//!  │   1. `[Pair(Some(0), _)]`
+//!  │   2. `[Pair(_, false)]`
+//!  │   3. `[Pair(Some(0), false)]`
+//!  │
+//!  │ Specialize with `Pair`:
+//!  ├─┐ Patterns:
+//!  │ │   1. `[Some(0), _]`
+//!  │ │   2. `[_, false]`
+//!  │ │   3. `[Some(0), false]`
+//!  │ │
+//!  │ │ Specialize with `Some`:
+//!  │ ├─┐ Patterns:
+//!  │ │ │   1. `[0, _]`
+//!  │ │ │   2. `[_, false]`
+//!  │ │ │   3. `[0, false]`
+//!  │ │ │
+//!  │ │ │ Specialize with `0`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   1. `[_]`
+//!  │ │ │ │   3. `[false]`
+//!  │ │ │ │
+//!  │ │ │ │ Specialize with `true`:
+//!  │ │ │ ├─┐ Patterns:
+//!  │ │ │ │ │   1. `[]`
+//!  │ │ │ │ │
+//!  │ │ │ │ │ We note arm 1 is reachable (by `Pair(Some(0), true)`).
+//!  │ │ │ ├─┘
+//!  │ │ │ │
+//!  │ │ │ │ Specialize with `false`:
+//!  │ │ │ ├─┐ Patterns:
+//!  │ │ │ │ │   1. `[]`
+//!  │ │ │ │ │   3. `[]`
+//!  │ │ │ │ │
+//!  │ │ │ │ │ We note arm 1 is reachable (by `Pair(Some(0), false)`).
+//!  │ │ │ ├─┘
+//!  │ │ ├─┘
+//!  │ │ │
+//!  │ │ │ Specialize with `1..`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   2. `[false]`
+//!  │ │ │ │
+//!  │ │ │ │ Specialize with `true`:
+//!  │ │ │ ├─┐ Patterns:
+//!  │ │ │ │ │   // no rows left
+//!  │ │ │ │ │
+//!  │ │ │ │ │ We have found an unmatched value (`Pair(Some(1..), true)`)! This gives us a witness.
+//!  │ │ │ │ │ New witnesses:
+//!  │ │ │ │ │   `[]`
+//!  │ │ │ ├─┘
+//!  │ │ │ │ Unspecialize new witnesses with `true`:
+//!  │ │ │ │   `[true]`
+//!  │ │ │ │
+//!  │ │ │ │ Specialize with `false`:
+//!  │ │ │ ├─┐ Patterns:
+//!  │ │ │ │ │   2. `[]`
+//!  │ │ │ │ │
+//!  │ │ │ │ │ We note arm 2 is reachable (by `Pair(Some(1..), false)`).
+//!  │ │ │ ├─┘
+//!  │ │ │ │
+//!  │ │ │ │ Total witnesses for `1..`:
+//!  │ │ │ │   `[true]`
+//!  │ │ ├─┘
+//!  │ │ │ Unspecialize new witnesses with `1..`:
+//!  │ │ │   `[1.., true]`
+//!  │ │ │
+//!  │ │ │ Total witnesses for `Some`:
+//!  │ │ │   `[1.., true]`
+//!  │ ├─┘
+//!  │ │ Unspecialize new witnesses with `Some`:
+//!  │ │   `[Some(1..), true]`
+//!  │ │
+//!  │ │ Specialize with `None`:
+//!  │ ├─┐ Patterns:
+//!  │ │ │   2. `[false]`
+//!  │ │ │
+//!  │ │ │ Specialize with `true`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   // no rows left
+//!  │ │ │ │
+//!  │ │ │ │ We have found an unmatched value (`Pair(None, true)`)! This gives us a witness.
+//!  │ │ │ │ New witnesses:
+//!  │ │ │ │   `[]`
+//!  │ │ ├─┘
+//!  │ │ │ Unspecialize new witnesses with `true`:
+//!  │ │ │   `[true]`
+//!  │ │ │
+//!  │ │ │ Specialize with `false`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   2. `[]`
+//!  │ │ │ │
+//!  │ │ │ │ We note arm 2 is reachable (by `Pair(None, false)`).
+//!  │ │ ├─┘
+//!  │ │ │
+//!  │ │ │ Total witnesses for `None`:
+//!  │ │ │   `[true]`
+//!  │ ├─┘
+//!  │ │ Unspecialize new witnesses with `None`:
+//!  │ │   `[None, true]`
+//!  │ │
+//!  │ │ Total witnesses for `Pair`:
+//!  │ │   `[Some(1..), true]`
+//!  │ │   `[None, true]`
+//!  ├─┘
+//!  │ Unspecialize new witnesses with `Pair`:
+//!  │   `[Pair(Some(1..), true)]`
+//!  │   `[Pair(None, true)]`
+//!  │
+//!  │ Final witnesses:
+//!  │   `[Pair(Some(1..), true)]`
+//!  │   `[Pair(None, true)]`
+//!  ┘
+//! ```
+//!
+//! We conclude:
+//! - Arm 3 is unreachable (it was never marked as reachable);
+//! - The match is not exhaustive;
+//! - Adding arms with `Pair(Some(1..), true)` and `Pair(None, true)` would make the match exhaustive.
+//!
+//! Note that when we're deep in the algorithm, we don't know what specialization steps got us here.
+//! We can only figure out what our witnesses correspond to by unspecializing back up the stack.
+//!
+//!
+//! # Tests
+//!
+//! Note: tests specific to this file can be found in:
+//!
+//!   - `ui/pattern/usefulness`
+//!   - `ui/or-patterns`
+//!   - `ui/consts/const_in_pattern`
+//!   - `ui/rfc-2008-non-exhaustive`
+//!   - `ui/half-open-range-patterns`
+//!   - probably many others
+//!
+//! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
+//! reason not to, for example if they crucially depend on a particular feature like `or_patterns`.
+
 use super::deconstruct_pat::{
     Constructor, ConstructorSet, DeconstructedPat, IntRange, MaybeInfiniteInt, SplitConstructorSet,
     WitnessPat,
@@ -340,8 +521,12 @@ pub(crate) struct MatchCheckCtxt<'p, 'tcx> {
     pub(crate) module: DefId,
     pub(crate) param_env: ty::ParamEnv<'tcx>,
     pub(crate) pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
+    /// Lint level at the match.
+    pub(crate) match_lint_level: HirId,
     /// The span of the whole match, if applicable.
     pub(crate) match_span: Option<Span>,
+    /// Span of the scrutinee.
+    pub(crate) scrut_span: Span,
     /// Only produce `NON_EXHAUSTIVE_OMITTED_PATTERNS` lint on refutable patterns.
     pub(crate) refutable: bool,
 }
@@ -371,8 +556,6 @@ pub(super) struct PatCtxt<'a, 'p, 'tcx> {
     pub(super) cx: &'a MatchCheckCtxt<'p, 'tcx>,
     /// Type of the current column under investigation.
     pub(super) ty: Ty<'tcx>,
-    /// Span of the current pattern under investigation.
-    pub(super) span: Span,
     /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
     /// subpattern.
     pub(super) is_top_level: bool,
@@ -384,20 +567,16 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
     }
 }
 
-/// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
-/// works well.
+/// Represents a pattern-tuple under investigation.
 #[derive(Clone)]
-pub(crate) struct PatStack<'p, 'tcx> {
-    pub(crate) pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>,
+struct PatStack<'p, 'tcx> {
+    // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well.
+    pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>,
 }
 
 impl<'p, 'tcx> PatStack<'p, 'tcx> {
     fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self {
-        Self::from_vec(smallvec![pat])
-    }
-
-    fn from_vec(vec: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>) -> Self {
-        PatStack { pats: vec }
+        PatStack { pats: smallvec![pat] }
     }
 
     fn is_empty(&self) -> bool {
@@ -416,37 +595,18 @@ impl<'p, 'tcx> PatStack<'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.
+    // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is
+    // an or-pattern. Panics if `self` is empty.
     fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = PatStack<'p, 'tcx>> + Captures<'a> {
-        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
+        self.head().flatten_or_pat().into_iter().map(move |pat| {
+            let mut new_pats = smallvec![pat];
+            new_pats.extend_from_slice(&self.pats[1..]);
+            PatStack { pats: new_pats }
         })
     }
 
-    // Recursively expand all patterns into their subpatterns and push each `PatStack` to matrix.
-    fn expand_and_extend<'a>(&'a self, matrix: &mut Matrix<'p, 'tcx>) {
-        if !self.is_empty() && self.head().is_or_pat() {
-            for pat in self.head().iter_fields() {
-                let mut new_patstack = PatStack::from_pattern(pat);
-                new_patstack.pats.extend_from_slice(&self.pats[1..]);
-                if !new_patstack.is_empty() && new_patstack.head().is_or_pat() {
-                    new_patstack.expand_and_extend(matrix);
-                } else if !new_patstack.is_empty() {
-                    matrix.push(new_patstack);
-                }
-            }
-        }
-    }
-
-    /// 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`.
+    /// This computes `specialize(ctor, self)`. See top of the file for explanations.
+    /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
     fn pop_head_constructor(
         &self,
         pcx: &PatCtxt<'_, 'p, 'tcx>,
@@ -454,15 +614,15 @@ impl<'p, 'tcx> PatStack<'p, '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: SmallVec<[_; 2]> = self.head().specialize(pcx, ctor);
-        new_fields.extend_from_slice(&self.pats[1..]);
-        PatStack::from_vec(new_fields)
+        let mut new_pats = self.head().specialize(pcx, ctor);
+        new_pats.extend_from_slice(&self.pats[1..]);
+        PatStack { pats: new_pats }
     }
 }
 
-/// Pretty-printing for matrix row.
 impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        // We pretty-print similarly to the `Debug` impl of `Matrix`.
         write!(f, "+")?;
         for pat in self.iter() {
             write!(f, " {pat:?} +")?;
@@ -471,45 +631,186 @@ impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
     }
 }
 
-/// A 2D matrix.
+/// A row of the matrix.
 #[derive(Clone)]
-pub(super) struct Matrix<'p, 'tcx> {
-    pub patterns: Vec<PatStack<'p, 'tcx>>,
+struct MatrixRow<'p, 'tcx> {
+    // The patterns in the row.
+    pats: PatStack<'p, 'tcx>,
+    /// Whether the original arm had a guard. This is inherited when specializing.
+    is_under_guard: bool,
+    /// When we specialize, we remember which row of the original matrix produced a given row of the
+    /// specialized matrix. When we unspecialize, we use this to propagate reachability back up the
+    /// callstack.
+    parent_row: usize,
+    /// False when the matrix is just built. This is set to `true` by
+    /// [`compute_exhaustiveness_and_reachability`] if the arm is found to be reachable.
+    /// This is reset to `false` when specializing.
+    reachable: bool,
 }
 
-impl<'p, 'tcx> Matrix<'p, 'tcx> {
-    fn empty() -> Self {
-        Matrix { patterns: vec![] }
+impl<'p, 'tcx> MatrixRow<'p, 'tcx> {
+    fn is_empty(&self) -> bool {
+        self.pats.is_empty()
     }
 
+    fn len(&self) -> usize {
+        self.pats.len()
+    }
+
+    fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> {
+        self.pats.head()
+    }
+
+    fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> {
+        self.pats.iter()
+    }
+
+    // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is
+    // an or-pattern. Panics if `self` is empty.
+    fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = MatrixRow<'p, 'tcx>> + Captures<'a> {
+        self.pats.expand_or_pat().map(|patstack| MatrixRow {
+            pats: patstack,
+            parent_row: self.parent_row,
+            is_under_guard: self.is_under_guard,
+            reachable: false,
+        })
+    }
+
+    /// This computes `specialize(ctor, self)`. See top of the file for explanations.
+    /// Only call if `ctor.is_covered_by(self.head().ctor())` is true.
+    fn pop_head_constructor(
+        &self,
+        pcx: &PatCtxt<'_, 'p, 'tcx>,
+        ctor: &Constructor<'tcx>,
+        parent_row: usize,
+    ) -> MatrixRow<'p, 'tcx> {
+        MatrixRow {
+            pats: self.pats.pop_head_constructor(pcx, ctor),
+            parent_row,
+            is_under_guard: self.is_under_guard,
+            reachable: false,
+        }
+    }
+}
+
+impl<'p, 'tcx> fmt::Debug for MatrixRow<'p, 'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.pats.fmt(f)
+    }
+}
+
+/// A 2D matrix. Represents a list of pattern-tuples under investigation.
+///
+/// Invariant: each row must have the same length, and each column must have the same type.
+///
+/// Invariant: the first column must not contain or-patterns. This is handled by
+/// [`Matrix::expand_and_push`].
+///
+/// In fact each column corresponds to a place inside the scrutinee of the match. E.g. after
+/// specializing `(,)` and `Some` on a pattern of type `(Option<u32>, bool)`, the first column of
+/// the matrix will correspond to `scrutinee.0.Some.0` and the second column to `scrutinee.1`.
+#[derive(Clone)]
+struct Matrix<'p, 'tcx> {
+    rows: Vec<MatrixRow<'p, 'tcx>>,
+    /// Stores an extra fictitious row full of wildcards. Mostly used to keep track of the type of
+    /// each column. This must obey the same invariants as the real rows.
+    wildcard_row: PatStack<'p, 'tcx>,
+}
+
+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>) {
+    /// expands it. Internal method, prefer [`Matrix::new`].
+    fn expand_and_push(&mut self, row: MatrixRow<'p, 'tcx>) {
         if !row.is_empty() && row.head().is_or_pat() {
-            row.expand_and_extend(self);
+            // Expand nested or-patterns.
+            for new_row in row.expand_or_pat() {
+                self.rows.push(new_row);
+            }
         } else {
-            self.patterns.push(row);
+            self.rows.push(row);
+        }
+    }
+
+    /// Build a new matrix from an iterator of `MatchArm`s.
+    fn new<'a>(
+        cx: &MatchCheckCtxt<'p, 'tcx>,
+        iter: impl Iterator<Item = &'a MatchArm<'p, 'tcx>>,
+        scrut_ty: Ty<'tcx>,
+    ) -> Self
+    where
+        'p: 'a,
+    {
+        let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP));
+        let wildcard_row = PatStack::from_pattern(wild_pattern);
+        let mut matrix = Matrix { rows: vec![], wildcard_row };
+        for (row_id, arm) in iter.enumerate() {
+            let v = MatrixRow {
+                pats: PatStack::from_pattern(arm.pat),
+                parent_row: row_id, // dummy, we won't read it
+                is_under_guard: arm.has_guard,
+                reachable: false,
+            };
+            matrix.expand_and_push(v);
+        }
+        matrix
+    }
+
+    fn head_ty(&self) -> Option<Ty<'tcx>> {
+        if self.column_count() == 0 {
+            return None;
+        }
+
+        let mut ty = self.wildcard_row.head().ty();
+        // If the type is opaque and it is revealed anywhere in the column, we take the revealed
+        // version. Otherwise we could encounter constructors for the revealed type and crash.
+        let is_opaque = |ty: Ty<'tcx>| matches!(ty.kind(), ty::Alias(ty::Opaque, ..));
+        if is_opaque(ty) {
+            for pat in self.heads() {
+                let pat_ty = pat.ty();
+                if !is_opaque(pat_ty) {
+                    ty = pat_ty;
+                    break;
+                }
+            }
         }
+        Some(ty)
+    }
+    fn column_count(&self) -> usize {
+        self.wildcard_row.len()
     }
 
-    /// Iterate over the first component of each row
+    fn rows<'a>(
+        &'a self,
+    ) -> impl Iterator<Item = &'a MatrixRow<'p, 'tcx>> + Clone + DoubleEndedIterator + ExactSizeIterator
+    {
+        self.rows.iter()
+    }
+    fn rows_mut<'a>(
+        &'a mut self,
+    ) -> impl Iterator<Item = &'a mut MatrixRow<'p, 'tcx>> + DoubleEndedIterator + ExactSizeIterator
+    {
+        self.rows.iter_mut()
+    }
+
+    /// Iterate over the first pattern of each row.
     fn heads<'a>(
         &'a self,
     ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> {
-        self.patterns.iter().map(|r| r.head())
+        self.rows().map(|r| r.head())
     }
 
-    /// This computes `S(constructor, self)`. See top of the file for explanations.
+    /// This computes `specialize(ctor, self)`. See top of the file for explanations.
     fn specialize_constructor(
         &self,
         pcx: &PatCtxt<'_, 'p, 'tcx>,
         ctor: &Constructor<'tcx>,
     ) -> Matrix<'p, 'tcx> {
-        let mut matrix = Matrix::empty();
-        for row in &self.patterns {
+        let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor);
+        let mut matrix = Matrix { rows: vec![], wildcard_row };
+        for (i, row) in self.rows().enumerate() {
             if ctor.is_covered_by(pcx, row.head().ctor()) {
-                let new_row = row.pop_head_constructor(pcx, ctor);
-                matrix.push(new_row);
+                let new_row = row.pop_head_constructor(pcx, ctor, i);
+                matrix.expand_and_push(new_row);
             }
         }
         matrix
@@ -529,12 +830,12 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "\n")?;
 
-        let Matrix { patterns: m, .. } = self;
+        let Matrix { rows, .. } = self;
         let pretty_printed_matrix: Vec<Vec<String>> =
-            m.iter().map(|row| row.iter().map(|pat| format!("{pat:?}")).collect()).collect();
+            rows.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));
+        let column_count = rows.iter().map(|row| row.len()).next().unwrap_or(0);
+        assert!(rows.iter().all(|row| row.len() == column_count));
         let column_widths: Vec<usize> = (0..column_count)
             .map(|col| pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0))
             .collect();
@@ -552,129 +853,17 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
     }
 }
 
-/// 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(Debug, Clone)]
-enum Usefulness<'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<WitnessStack<'tcx>>),
-}
-
-impl<'tcx> Usefulness<'tcx> {
-    fn new_useful(preference: ArmType) -> Self {
-        match preference {
-            // A single (empty) witness of reachability.
-            FakeExtraWildcard => WithWitnesses(vec![WitnessStack(vec![])]),
-            RealArm => NoWitnesses { useful: true },
-        }
-    }
-
-    fn new_not_useful(preference: ArmType) -> Self {
-        match preference {
-            FakeExtraWildcard => WithWitnesses(vec![]),
-            RealArm => NoWitnesses { useful: false },
-        }
-    }
-
-    fn is_useful(&self) -> bool {
-        match self {
-            Usefulness::NoWitnesses { useful } => *useful,
-            Usefulness::WithWitnesses(witnesses) => !witnesses.is_empty(),
-        }
-    }
-
-    /// Combine usefulnesses from two branches. This is an associative operation.
-    fn extend(&mut self, other: Self) {
-        match (&mut *self, other) {
-            (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 { useful: s_useful }, NoWitnesses { useful: o_useful }) => {
-                *s_useful = *s_useful || o_useful
-            }
-            _ => unreachable!(),
-        }
-    }
-
-    /// After calculating usefulness after a specialization, call this to reconstruct a usefulness
-    /// that makes sense for the matrix pre-specialization. This new usefulness can then be merged
-    /// with the results of specializing with the other constructors.
-    fn apply_constructor(
-        self,
-        pcx: &PatCtxt<'_, '_, 'tcx>,
-        matrix: &Matrix<'_, 'tcx>, // used to compute missing ctors
-        ctor: &Constructor<'tcx>,
-    ) -> Self {
-        match self {
-            NoWitnesses { .. } => self,
-            WithWitnesses(ref witnesses) if witnesses.is_empty() => self,
-            WithWitnesses(witnesses) => {
-                let new_witnesses = if let Constructor::Missing { .. } = ctor {
-                    let mut missing = ConstructorSet::for_ty(pcx.cx, pcx.ty)
-                        .compute_missing(pcx, matrix.heads().map(DeconstructedPat::ctor));
-                    if missing.iter().any(|c| c.is_non_exhaustive()) {
-                        // We only report `_` here; listing other constructors would be redundant.
-                        missing = vec![Constructor::NonExhaustive];
-                    }
-
-                    // We got the special `Missing` constructor, so each of the missing constructors
-                    // gives a new pattern that is not caught by the match.
-                    // We construct for each missing constructor a version of this constructor with
-                    // wildcards for fields, i.e. 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(_)`.
-                    let new_patterns: Vec<WitnessPat<'_>> = missing
-                        .into_iter()
-                        .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor.clone()))
-                        .collect();
-
-                    witnesses
-                        .into_iter()
-                        .flat_map(|witness| {
-                            new_patterns.iter().map(move |pat| {
-                                let mut stack = witness.clone();
-                                stack.0.push(pat.clone());
-                                stack
-                            })
-                        })
-                        .collect()
-                } else {
-                    witnesses
-                        .into_iter()
-                        .map(|witness| witness.apply_constructor(pcx, ctor))
-                        .collect()
-                };
-                WithWitnesses(new_witnesses)
-            }
-        }
-    }
-}
-
-#[derive(Copy, Clone, Debug)]
-enum ArmType {
-    FakeExtraWildcard,
-    RealArm,
-}
-
 /// A witness-tuple of non-exhaustiveness for error reporting, represented as a list of patterns (in
-/// reverse order of construction) with wildcards inside to represent elements that can take any
-/// inhabitant of the type as a value.
+/// reverse order of construction).
 ///
 /// This mirrors `PatStack`: they function similarly, except `PatStack` contains user patterns we
 /// are inspecting, and `WitnessStack` contains witnesses we are constructing.
-/// FIXME(Nadrieril): use the same order of patterns for both
+/// FIXME(Nadrieril): use the same order of patterns for both.
 ///
-/// A `WitnessStack` should have the same types and length as the `PatStacks` we are inspecting
-/// (except we store the patterns in reverse order). Because Rust `match` is always against a single
-/// pattern, at the end the stack will have length 1. In the middle of the algorithm, it can contain
-/// multiple patterns.
+/// A `WitnessStack` should have the same types and length as the `PatStack`s we are inspecting
+/// (except we store the patterns in reverse order). The same way `PatStack` starts with length 1,
+/// at the end of the algorithm this will have length 1. In the middle of the algorithm, it can
+/// contain multiple patterns.
 ///
 /// For example, if we are constructing a witness for the match against
 ///
@@ -689,6 +878,7 @@ enum ArmType {
 /// ```
 ///
 /// We'll perform the following steps (among others):
+/// ```text
 /// - Start with a matrix representing the match
 ///     `PatStack(vec![Pair(None, _)])`
 ///     `PatStack(vec![Pair(_, false)])`
@@ -711,8 +901,11 @@ enum ArmType {
 ///     `WitnessStack(vec![true, Some(_)])`
 /// - Apply `Pair`
 ///     `WitnessStack(vec![Pair(Some(_), true)])`
+/// ```
 ///
 /// The final `Pair(Some(_), true)` is then the resulting witness.
+///
+/// See the top of the file for more detailed explanations and examples.
 #[derive(Debug, Clone)]
 pub(crate) struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>);
 
@@ -723,158 +916,235 @@ impl<'tcx> WitnessStack<'tcx> {
         self.0.into_iter().next().unwrap()
     }
 
-    /// Constructs a partial witness for a pattern given a list of
-    /// patterns expanded by the specialization step.
-    ///
-    /// When a pattern P is discovered to be useful, this function is used bottom-up
-    /// to reconstruct a complete witness, e.g., a pattern P' that covers a subset
-    /// of values, V, where each value in that set is not covered by any previously
-    /// used patterns and is covered by the pattern P'. Examples:
+    /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern.
+    fn push_pattern(&mut self, pat: WitnessPat<'tcx>) {
+        self.0.push(pat);
+    }
+
+    /// Reverses specialization. Given a witness obtained after specialization, this constructs a
+    /// new witness valid for before specialization. See the section on `unspecialize` at the top of
+    /// the file.
     ///
-    /// left_ty: tuple of 3 elements
-    /// pats: [10, 20, _]           => (10, 20, _)
+    /// Examples:
+    /// ```text
+    /// ctor: tuple of 2 elements
+    /// pats: [false, "foo", _, true]
+    /// result: [(false, "foo"), _, true]
     ///
-    /// left_ty: struct X { a: (bool, &'static str), b: usize}
-    /// pats: [(false, "foo"), 42]  => X { a: (false, "foo"), b: 42 }
-    fn apply_constructor(mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) -> Self {
-        let pat = {
-            let len = self.0.len();
-            let arity = ctor.arity(pcx);
-            let fields = self.0.drain((len - arity)..).rev().collect();
-            WitnessPat::new(ctor.clone(), fields, pcx.ty)
-        };
-
+    /// ctor: Enum::Variant { a: (bool, &'static str), b: usize}
+    /// pats: [(false, "foo"), _, true]
+    /// result: [Enum::Variant { a: (false, "foo"), b: _ }, true]
+    /// ```
+    fn apply_constructor(&mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) {
+        let len = self.0.len();
+        let arity = ctor.arity(pcx);
+        let fields = self.0.drain((len - arity)..).rev().collect();
+        let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty);
         self.0.push(pat);
-
-        self
     }
 }
 
-/// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
-/// The algorithm from the paper has been modified to correctly handle empty
-/// types. The changes are:
-///   (0) We don't exit early if the pattern matrix has zero rows. We just
-///       continue to recurse over columns.
-///   (1) all_constructors will only return constructors that are statically
-///       possible. E.g., it will only return `Ok` for `Result<T, !>`.
+/// Represents a set of pattern-tuples that are witnesses of non-exhaustiveness for error
+/// reporting. This has similar invariants as `Matrix` does.
+///
+/// The `WitnessMatrix` returned by [`compute_exhaustiveness_and_reachability`] obeys the invariant
+/// that the union of the input `Matrix` and the output `WitnessMatrix` together matches the type
+/// exhaustively.
 ///
-/// This finds whether a (row) vector `v` of patterns is 'useful' in relation
-/// to a set of such vectors `m` - this is defined as there being a set of
-/// inputs that will match `v` but not any of the sets in `m`.
+/// Just as the `Matrix` starts with a single column, by the end of the algorithm, this has a single
+/// column, which contains the patterns that are missing for the match to be exhaustive.
+#[derive(Debug, Clone)]
+pub struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>);
+
+impl<'tcx> WitnessMatrix<'tcx> {
+    /// New matrix with no witnesses.
+    fn empty() -> Self {
+        WitnessMatrix(vec![])
+    }
+    /// New matrix with one `()` witness, i.e. with no columns.
+    fn unit_witness() -> Self {
+        WitnessMatrix(vec![WitnessStack(vec![])])
+    }
+
+    /// Whether this has any witnesses.
+    fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+    /// Asserts that there is a single column and returns the patterns in it.
+    fn single_column(self) -> Vec<WitnessPat<'tcx>> {
+        self.0.into_iter().map(|w| w.single_pattern()).collect()
+    }
+
+    /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern.
+    fn push_pattern(&mut self, pat: WitnessPat<'tcx>) {
+        for witness in self.0.iter_mut() {
+            witness.push_pattern(pat.clone())
+        }
+    }
+
+    /// Reverses specialization by `ctor`. See the section on `unspecialize` at the top of the file.
+    fn apply_constructor(
+        &mut self,
+        pcx: &PatCtxt<'_, '_, 'tcx>,
+        missing_ctors: &[Constructor<'tcx>],
+        ctor: &Constructor<'tcx>,
+        report_individual_missing_ctors: bool,
+    ) {
+        if self.is_empty() {
+            return;
+        }
+        if matches!(ctor, Constructor::Missing) {
+            // We got the special `Missing` constructor that stands for the constructors not present
+            // in the match.
+            if !report_individual_missing_ctors {
+                // Report `_` as missing.
+                let pat = WitnessPat::wild_from_ctor(pcx, Constructor::Wildcard);
+                self.push_pattern(pat);
+            } else if missing_ctors.iter().any(|c| c.is_non_exhaustive()) {
+                // We need to report a `_` anyway, so listing other constructors would be redundant.
+                // `NonExhaustive` is displayed as `_` just like `Wildcard`, but it will be picked
+                // up by diagnostics to add a note about why `_` is required here.
+                let pat = WitnessPat::wild_from_ctor(pcx, Constructor::NonExhaustive);
+                self.push_pattern(pat);
+            } else {
+                // For each missing constructor `c`, we add a `c(_, _, _)` witness appropriately
+                // filled with wildcards.
+                let mut ret = Self::empty();
+                for ctor in missing_ctors {
+                    let pat = WitnessPat::wild_from_ctor(pcx, ctor.clone());
+                    // Clone `self` and add `c(_, _, _)` to each of its witnesses.
+                    let mut wit_matrix = self.clone();
+                    wit_matrix.push_pattern(pat);
+                    ret.extend(wit_matrix);
+                }
+                *self = ret;
+            }
+        } else {
+            // Any other constructor we unspecialize as expected.
+            for witness in self.0.iter_mut() {
+                witness.apply_constructor(pcx, ctor)
+            }
+        }
+    }
+
+    /// Merges the witnesses of two matrices. Their column types must match.
+    fn extend(&mut self, other: Self) {
+        self.0.extend(other.0)
+    }
+}
+
+/// The core of the algorithm.
 ///
-/// All the patterns at each column of the `matrix ++ v` matrix must have the same type.
+/// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks
+/// usefulness of each row in the matrix (in `row.reachable`). We track reachability of each
+/// subpattern using interior mutability in `DeconstructedPat`.
 ///
-/// This is used both for reachability checking (if a pattern isn't useful in
-/// relation to preceding patterns, it is not reachable) and exhaustiveness
-/// checking (if a wildcard pattern is useful in relation to a matrix, the
-/// matrix isn't exhaustive).
+/// The input `Matrix` and the output `WitnessMatrix` together match the type exhaustively.
 ///
-/// `is_under_guard` is used to inform if the pattern has a guard. If it
-/// has one it must not be inserted into the matrix. This shouldn't be
-/// relied on for soundness.
-#[instrument(level = "debug", skip(cx, matrix, lint_root), ret)]
-fn is_useful<'p, 'tcx>(
+/// The key steps are:
+/// - specialization, where we dig into the rows that have a specific constructor and call ourselves
+///     recursively;
+/// - unspecialization, where we lift the results from the previous step into results for this step
+///     (using `apply_constructor` and by updating `row.reachable` for each parent row).
+/// This is all explained at the top of the file.
+#[instrument(level = "debug", skip(cx, is_top_level), ret)]
+fn compute_exhaustiveness_and_reachability<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
-    matrix: &Matrix<'p, 'tcx>,
-    v: &PatStack<'p, 'tcx>,
-    witness_preference: ArmType,
-    lint_root: HirId,
-    is_under_guard: bool,
+    matrix: &mut Matrix<'p, 'tcx>,
     is_top_level: bool,
-) -> Usefulness<'tcx> {
-    debug!(?matrix, ?v);
-    let Matrix { patterns: rows, .. } = matrix;
-
-    // The base case. We are pattern-matching on () and the return value is
-    // based on whether our matrix has a row or not.
-    // NOTE: This could potentially be optimized by checking rows.is_empty()
-    // first and then, if v is non-empty, the return value is based on whether
-    // the type of the tuple we're checking is inhabited or not.
-    if v.is_empty() {
-        let ret = if rows.is_empty() {
-            Usefulness::new_useful(witness_preference)
-        } else {
-            Usefulness::new_not_useful(witness_preference)
-        };
-        debug!(?ret);
-        return ret;
-    }
-
-    debug_assert!(rows.iter().all(|r| r.len() == v.len()));
-
-    // If the first pattern is an or-pattern, expand it.
-    let mut ret = Usefulness::new_not_useful(witness_preference);
-    if v.head().is_or_pat() {
-        debug!("expanding or-pattern");
-        // We try each or-pattern branch in turn.
-        let mut matrix = matrix.clone();
-        for v in v.expand_or_pat() {
-            debug!(?v);
-            let usefulness = ensure_sufficient_stack(|| {
-                is_useful(cx, &matrix, &v, witness_preference, lint_root, is_under_guard, false)
-            });
-            debug!(?usefulness);
-            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);
+) -> WitnessMatrix<'tcx> {
+    debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count()));
+
+    let Some(ty) = matrix.head_ty() else {
+        // The base case: there are no columns in the matrix. We are morally pattern-matching on ().
+        // A row is reachable iff it has no (unguarded) rows above it.
+        for row in matrix.rows_mut() {
+            // All rows are reachable until we find one without a guard.
+            row.reachable = true;
+            if !row.is_under_guard {
+                // There's an unguarded row, so the match is exhaustive, and any subsequent row is
+                // unreachable.
+                return WitnessMatrix::empty();
             }
         }
-    } else {
-        let mut ty = v.head().ty();
+        // No (unguarded) rows, so the match is not exhaustive. We return a new witness.
+        return WitnessMatrix::unit_witness();
+    };
 
-        // Opaque types can't get destructured/split, but the patterns can
-        // actually hint at hidden types, so we use the patterns' types instead.
-        if let ty::Alias(ty::Opaque, ..) = ty.kind() {
-            if let Some(row) = rows.first() {
-                ty = row.head().ty();
-            }
+    debug!("ty: {ty:?}");
+    let pcx = &PatCtxt { cx, ty, is_top_level };
+
+    // Analyze the constructors present in this column.
+    let ctors = matrix.heads().map(|p| p.ctor());
+    let split_set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, ctors);
+
+    let all_missing = split_set.present.is_empty();
+    let always_report_all = is_top_level && !IntRange::is_integral(pcx.ty);
+    // Whether we should report "Enum::A and Enum::C are missing" or "_ is missing".
+    let report_individual_missing_ctors = always_report_all || !all_missing;
+
+    let mut split_ctors = split_set.present;
+    let mut only_report_missing = false;
+    if !split_set.missing.is_empty() {
+        // We need to iterate over a full set of constructors, so we add `Missing` to represent the
+        // missing ones. This is explained under "Constructor Splitting" at the top of this file.
+        split_ctors.push(Constructor::Missing);
+        // For diagnostic purposes we choose to only report the constructors that are missing. Since
+        // `Missing` matches only the wildcard rows, it matches fewer rows than any normal
+        // constructor and is therefore guaranteed to result in more witnesses. So skipping the
+        // other constructors does not jeopardize correctness.
+        only_report_missing = true;
+    }
+
+    let mut ret = WitnessMatrix::empty();
+    for ctor in split_ctors {
+        debug!("specialize({:?})", ctor);
+        // Dig into rows that match `ctor`.
+        let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor);
+        let mut witnesses = ensure_sufficient_stack(|| {
+            compute_exhaustiveness_and_reachability(cx, &mut spec_matrix, false)
+        });
+
+        if !only_report_missing || matches!(ctor, Constructor::Missing) {
+            // Transform witnesses for `spec_matrix` into witnesses for `matrix`.
+            witnesses.apply_constructor(
+                pcx,
+                &split_set.missing,
+                &ctor,
+                report_individual_missing_ctors,
+            );
+            // Accumulate the found witnesses.
+            ret.extend(witnesses);
         }
-        debug!("v.head: {:?}, v.span: {:?}", v.head(), v.head().span());
-        let pcx = &PatCtxt { cx, ty, span: v.head().span(), is_top_level };
-
-        let v_ctor = v.head().ctor();
-        debug!(?v_ctor);
-        // We split the head constructor of `v`.
-        let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
-        // 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;
-        for ctor in split_ctors {
-            debug!("specialize({:?})", ctor);
-            // We cache the result of `Fields::wildcards` because it is used a lot.
-            let spec_matrix = start_matrix.specialize_constructor(pcx, &ctor);
-            let v = v.pop_head_constructor(pcx, &ctor);
-            let usefulness = ensure_sufficient_stack(|| {
-                is_useful(
-                    cx,
-                    &spec_matrix,
-                    &v,
-                    witness_preference,
-                    lint_root,
-                    is_under_guard,
-                    false,
-                )
-            });
-            let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor);
-            ret.extend(usefulness);
+
+        // A parent row is useful if any of its children is.
+        for child_row in spec_matrix.rows() {
+            let parent_row = &mut matrix.rows[child_row.parent_row];
+            parent_row.reachable = parent_row.reachable || child_row.reachable;
         }
     }
 
-    if ret.is_useful() {
-        v.head().set_reachable();
+    // Record that the subpattern is reachable.
+    for row in matrix.rows() {
+        if row.reachable {
+            row.head().set_reachable();
+        }
     }
 
     ret
 }
 
 /// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that
-/// inspect the same subvalue".
+/// inspect the same subvalue/place".
 /// This is used to traverse patterns column-by-column for lints. Despite similarities with
-/// `is_useful`, this is a different traversal. Notably this is linear in the depth of patterns,
-/// whereas `is_useful` is worst-case exponential (exhaustiveness is NP-complete).
+/// [`compute_exhaustiveness_and_reachability`], this does a different traversal. Notably this is
+/// linear in the depth of patterns, whereas `compute_exhaustiveness_and_reachability` is worst-case
+/// exponential (exhaustiveness is NP-complete). The core difference is that we treat sub-columns
+/// separately.
+///
+/// This must not contain an or-pattern. `specialize` takes care to expand them.
+///
+/// This is not used in the main algorithm; only in lints.
 #[derive(Debug)]
 struct PatternColumn<'p, 'tcx> {
     patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>,
@@ -907,17 +1177,19 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> {
         Some(first_ty)
     }
 
+    /// Do constructor splitting on the constructors of the column.
     fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> {
         let column_ctors = self.patterns.iter().map(|p| p.ctor());
         ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, column_ctors)
     }
+
     fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
         self.patterns.iter().copied()
     }
 
     /// Does specialization: given a constructor, this takes the patterns from the column that match
     /// the constructor, and outputs their fields.
-    /// This returns one column per field of the constructor. The normally all have the same length
+    /// This returns one column per field of the constructor. They usually all have the same length
     /// (the number of patterns in `self` that matched `ctor`), except that we expand or-patterns
     /// which may change the lengths.
     fn specialize(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Vec<Self> {
@@ -963,7 +1235,7 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>(
     let Some(ty) = column.head_ty() else {
         return Vec::new();
     };
-    let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false };
+    let pcx = &PatCtxt { cx, ty, is_top_level: false };
 
     let set = column.analyze_ctors(pcx);
     if set.present.is_empty() {
@@ -1004,16 +1276,15 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>(
 }
 
 /// Traverse the patterns to warn the user about ranges that overlap on their endpoints.
-#[instrument(level = "debug", skip(cx, lint_root))]
+#[instrument(level = "debug", skip(cx))]
 fn lint_overlapping_range_endpoints<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     column: &PatternColumn<'p, 'tcx>,
-    lint_root: HirId,
 ) {
     let Some(ty) = column.head_ty() else {
         return;
     };
-    let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false };
+    let pcx = &PatCtxt { cx, ty, is_top_level: false };
 
     let set = column.analyze_ctors(pcx);
 
@@ -1027,7 +1298,7 @@ fn lint_overlapping_range_endpoints<'p, 'tcx>(
                 .collect();
             cx.tcx.emit_spanned_lint(
                 lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
-                lint_root,
+                cx.match_lint_level,
                 this_span,
                 OverlappingRangeEndpoints { overlap: overlaps, range: this_span },
             );
@@ -1072,7 +1343,7 @@ fn lint_overlapping_range_endpoints<'p, 'tcx>(
         // Recurse into the fields.
         for ctor in set.present {
             for col in column.specialize(pcx, &ctor) {
-                lint_overlapping_range_endpoints(cx, &col, lint_root);
+                lint_overlapping_range_endpoints(cx, &col);
             }
         }
     }
@@ -1107,30 +1378,24 @@ pub(crate) struct UsefulnessReport<'p, 'tcx> {
     pub(crate) non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>,
 }
 
-/// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
-/// of its arms are reachable.
-///
-/// Note: the input patterns must have been lowered through
-/// `check_match::MatchVisitor::lower_pattern`.
+/// The entrypoint for this file. Computes whether a match is exhaustive and which of its arms are
+/// reachable.
 #[instrument(skip(cx, arms), level = "debug")]
 pub(crate) fn compute_match_usefulness<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     arms: &[MatchArm<'p, 'tcx>],
-    lint_root: HirId,
     scrut_ty: Ty<'tcx>,
-    scrut_span: Span,
 ) -> UsefulnessReport<'p, 'tcx> {
-    let mut matrix = Matrix::empty();
+    let mut matrix = Matrix::new(cx, arms.iter(), scrut_ty);
+    let non_exhaustiveness_witnesses =
+        compute_exhaustiveness_and_reachability(cx, &mut matrix, true);
+
+    let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column();
     let arm_usefulness: Vec<_> = arms
         .iter()
         .copied()
         .map(|arm| {
             debug!(?arm);
-            let v = PatStack::from_pattern(arm.pat);
-            is_useful(cx, &matrix, &v, RealArm, arm.hir_id, arm.has_guard, true);
-            if !arm.has_guard {
-                matrix.push(v);
-            }
             let reachability = if arm.pat.is_reachable() {
                 Reachability::Reachable(arm.pat.unreachable_spans())
             } else {
@@ -1139,28 +1404,20 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
             (arm, reachability)
         })
         .collect();
+    let report = UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses };
 
-    let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP));
-    let v = PatStack::from_pattern(wild_pattern);
-    let usefulness = is_useful(cx, &matrix, &v, FakeExtraWildcard, lint_root, false, true);
-    let non_exhaustiveness_witnesses: Vec<_> = match usefulness {
-        WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(),
-        NoWitnesses { .. } => bug!(),
-    };
-
-    let pat_column = arms.iter().flat_map(|arm| arm.pat.flatten_or_pat()).collect::<Vec<_>>();
-    let pat_column = PatternColumn::new(pat_column);
-    lint_overlapping_range_endpoints(cx, &pat_column, lint_root);
+    let pat_column = PatternColumn::new(matrix.heads().collect());
+    // Lint on ranges that overlap on their endpoints, which is likely a mistake.
+    lint_overlapping_range_endpoints(cx, &pat_column);
 
     // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting
     // `if let`s. Only run if the match is exhaustive otherwise the error is redundant.
-    if cx.refutable && non_exhaustiveness_witnesses.is_empty() {
+    if cx.refutable && report.non_exhaustiveness_witnesses.is_empty() {
         if !matches!(
-            cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, lint_root).0,
+            cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, cx.match_lint_level).0,
             rustc_session::lint::Level::Allow
         ) {
             let witnesses = collect_nonexhaustive_missing_variants(cx, &pat_column);
-
             if !witnesses.is_empty() {
                 // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
                 // is not exhaustive enough.
@@ -1168,11 +1425,11 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
                 // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`.
                 cx.tcx.emit_spanned_lint(
                     NON_EXHAUSTIVE_OMITTED_PATTERNS,
-                    lint_root,
-                    scrut_span,
+                    cx.match_lint_level,
+                    cx.scrut_span,
                     NonExhaustiveOmittedPattern {
                         scrut_ty,
-                        uncovered: Uncovered::new(scrut_span, cx, witnesses),
+                        uncovered: Uncovered::new(cx.scrut_span, cx, witnesses),
                     },
                 );
             }
@@ -1201,5 +1458,5 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
         }
     }
 
-    UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
+    report
 }
diff --git a/tests/ui/or-patterns/exhaustiveness-pass.rs b/tests/ui/or-patterns/exhaustiveness-pass.rs
index 428b9a19fe6..a52e08c507d 100644
--- a/tests/ui/or-patterns/exhaustiveness-pass.rs
+++ b/tests/ui/or-patterns/exhaustiveness-pass.rs
@@ -35,6 +35,17 @@ fn main() {
         ((0, 0) | (1, 0),) => {}
         _ => {}
     }
+    match ((0, 0),) {
+        // Note how the second one would be redundant without the guard.
+        ((x, y) | (y, x),) if x == 0 => {}
+        _ => {}
+    }
+    match 0 {
+        // We don't warn the second one as redundant in general because of cases like the one above.
+        // We could technically do it if there are no bindings.
+        0 | 0 if 0 == 0 => {}
+        _ => {}
+    }
 
     // This one caused ICE https://github.com/rust-lang/rust/issues/117378
     match (0u8, 0) {
diff --git a/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.rs b/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.rs
index 8429799cabf..20a8d754996 100644
--- a/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.rs
+++ b/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.rs
@@ -1,6 +1,7 @@
 #![deny(unreachable_patterns)]
 
 // We wrap patterns in a tuple because top-level or-patterns were special-cased.
+#[rustfmt::skip]
 fn main() {
     match (0u8,) {
         (1 | 2,) => {}
@@ -73,6 +74,11 @@ fn main() {
             | 0] => {} //~ ERROR unreachable
         _ => {}
     }
+    match (true, 0) {
+        (true, 0 | 0) => {} //~ ERROR unreachable
+        (_, 0 | 0) => {} //~ ERROR unreachable
+        _ => {}
+    }
     match &[][..] {
         [0] => {}
         [0, _] => {}
@@ -149,4 +155,8 @@ fn main() {
             | true, //~ ERROR unreachable
             false | true) => {}
     }
+    match (true, true) {
+        (x, y)
+            | (y, x) => {} //~ ERROR unreachable
+    }
 }
diff --git a/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.stderr b/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.stderr
index 3f7d47dcb8c..3616dda9981 100644
--- a/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.stderr
+++ b/tests/ui/or-patterns/exhaustiveness-unreachable-pattern.stderr
@@ -1,5 +1,5 @@
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:7:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:8:9
    |
 LL |         (1,) => {}
    |         ^^^^
@@ -11,128 +11,140 @@ LL | #![deny(unreachable_patterns)]
    |         ^^^^^^^^^^^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:12:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:13:9
    |
 LL |         (2,) => {}
    |         ^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:18:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:19:9
    |
 LL |         (1 | 2,) => {}
    |         ^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:23:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:24:9
    |
 LL |         (1, 3) => {}
    |         ^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:24:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:25:9
    |
 LL |         (1, 4) => {}
    |         ^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:25:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:26:9
    |
 LL |         (2, 4) => {}
    |         ^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:26:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:27:9
    |
 LL |         (2 | 1, 4) => {}
    |         ^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:28:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:29:9
    |
 LL |         (1, 4 | 5) => {}
    |         ^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:36:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:37:9
    |
 LL |         (Some(1),) => {}
    |         ^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:37:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:38:9
    |
 LL |         (None,) => {}
    |         ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:42:9
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:43:9
    |
 LL |         ((1..=4,),) => {}
    |         ^^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:47:14
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:48:14
    |
 LL |         (1 | 1,) => {}
    |              ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:51:19
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:52:19
    |
 LL |         (0 | 1) | 1 => {}
    |                   ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:57:14
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:58:14
    |
 LL |         0 | (0 | 0) => {}
    |              ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:57:18
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:58:18
    |
 LL |         0 | (0 | 0) => {}
    |                  ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:65:13
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:66:13
    |
 LL | /             Some(
 LL | |                 0 | 0) => {}
    | |______________________^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:71:15
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:72:15
    |
 LL |             | 0
    |               ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:73:15
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:74:15
    |
 LL |             | 0] => {}
    |               ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:81:10
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:78:20
+   |
+LL |         (true, 0 | 0) => {}
+   |                    ^
+
+error: unreachable pattern
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:79:17
+   |
+LL |         (_, 0 | 0) => {}
+   |                 ^
+
+error: unreachable pattern
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:87:10
    |
 LL |         [1
    |          ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:93:10
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:99:10
    |
 LL |         [true
    |          ^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:100:36
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:106:36
    |
 LL |         (true | false, None | Some(true
    |                                    ^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:105:14
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:111:14
    |
 LL |             (true
    |              ^^^^
@@ -143,28 +155,34 @@ LL |         (true | false, None | Some(t_or_f!())) => {}
    = note: this error originates in the macro `t_or_f` (in Nightly builds, run with -Z macro-backtrace for more info)
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:116:14
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:122:14
    |
 LL |         Some(0
    |              ^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:135:19
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:141:19
    |
 LL |                 | false) => {}
    |                   ^^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:143:15
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:149:15
    |
 LL |             | true) => {}
    |               ^^^^
 
 error: unreachable pattern
-  --> $DIR/exhaustiveness-unreachable-pattern.rs:149:15
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:155:15
    |
 LL |             | true,
    |               ^^^^
 
-error: aborting due to 26 previous errors
+error: unreachable pattern
+  --> $DIR/exhaustiveness-unreachable-pattern.rs:160:15
+   |
+LL |             | (y, x) => {}
+   |               ^^^^^^
+
+error: aborting due to 29 previous errors
 
diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
index 9e35960bcda..ebbbccc5d58 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
@@ -1,5 +1,5 @@
 error[E0004]: non-exhaustive patterns: type `usize` is non-empty
-  --> $DIR/pointer-sized-int.rs:54:11
+  --> $DIR/pointer-sized-int.rs:59:11
    |
 LL |     match 7usize {}
    |           ^^^^^^
diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
index d16ec5412db..2949081039a 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
@@ -9,7 +9,7 @@ LL |     match 0usize {
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `usize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern or an explicit pattern as shown
    |
-LL ~         0 ..= usize::MAX => {},
+LL ~         0..=usize::MAX => {},
 LL +         usize::MAX.. => todo!()
    |
 
@@ -24,12 +24,12 @@ LL |     match 0isize {
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL ~         isize::MIN ..= isize::MAX => {},
+LL ~         isize::MIN..=isize::MAX => {},
 LL +         ..isize::MIN | isize::MAX.. => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:25:8
+  --> $DIR/pointer-sized-int.rs:24:8
    |
 LL |     m!(0usize, 0..=usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -43,7 +43,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:27:8
+  --> $DIR/pointer-sized-int.rs:26:8
    |
 LL |     m!(0usize, 0..5 | 5..=usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -57,7 +57,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:29:8
+  --> $DIR/pointer-sized-int.rs:28:8
    |
 LL |     m!(0usize, 0..usize::MAX | usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -71,7 +71,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `(usize::MAX.., _)` not covered
-  --> $DIR/pointer-sized-int.rs:31:8
+  --> $DIR/pointer-sized-int.rs:30:8
    |
 LL |     m!((0usize, true), (0..5, true) | (5..=usize::MAX, true) | (0..=usize::MAX, false));
    |        ^^^^^^^^^^^^^^ pattern `(usize::MAX.., _)` not covered
@@ -85,7 +85,7 @@ LL |         match $s { $($t)+ => {}, (usize::MAX.., _) => todo!() }
    |                                ++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:36:8
+  --> $DIR/pointer-sized-int.rs:39:8
    |
 LL |     m!(0isize, isize::MIN..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
@@ -99,7 +99,7 @@ LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:38:8
+  --> $DIR/pointer-sized-int.rs:41:8
    |
 LL |     m!(0isize, isize::MIN..5 | 5..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
@@ -113,9 +113,9 @@ LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:40:8
+  --> $DIR/pointer-sized-int.rs:43:8
    |
-LL |     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
+LL |     m!(0isize, isize::MIN..=-1 | 0 | 1..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
    |
    = note: the matched value is of type `isize`
@@ -126,37 +126,36 @@ help: ensure that all possible cases are being handled by adding a match arm wit
 LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
-error[E0004]: non-exhaustive patterns: `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
-  --> $DIR/pointer-sized-int.rs:42:8
+error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
+  --> $DIR/pointer-sized-int.rs:45:8
    |
-LL |     m!((0isize, true), (isize::MIN..5, true)
-   |        ^^^^^^^^^^^^^^ patterns `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
+LL |     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
+   |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
    |
-   = note: the matched value is of type `(isize, bool)`
+   = note: the matched value is of type `isize`
    = note: `isize` does not have fixed minimum and maximum values, so half-open ranges are necessary to match exhaustively
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL |         match $s { $($t)+ => {}, (..isize::MIN, _) | (isize::MAX.., _) => todo!() }
-   |                                ++++++++++++++++++++++++++++++++++++++++++++++++++
+LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
+   |                                ++++++++++++++++++++++++++++++++++++++++
 
-error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:47:11
+error[E0004]: non-exhaustive patterns: `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
+  --> $DIR/pointer-sized-int.rs:48:9
    |
-LL |     match 0isize {
-   |           ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
+LL |         (0isize, true),
+   |         ^^^^^^^^^^^^^^ patterns `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
    |
-   = note: the matched value is of type `isize`
+   = note: the matched value is of type `(isize, bool)`
    = note: `isize` does not have fixed minimum and maximum values, so half-open ranges are necessary to match exhaustively
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL ~         1 ..= isize::MAX => {},
-LL +         ..isize::MIN | isize::MAX.. => todo!()
-   |
+LL |         match $s { $($t)+ => {}, (..isize::MIN, _) | (isize::MAX.., _) => todo!() }
+   |                                ++++++++++++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: type `usize` is non-empty
-  --> $DIR/pointer-sized-int.rs:54:11
+  --> $DIR/pointer-sized-int.rs:59:11
    |
 LL |     match 7usize {}
    |           ^^^^^^
diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
index 20a3cbe127f..cf137dca5aa 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
@@ -13,15 +13,14 @@ macro_rules! m {
 fn main() {
     match 0usize {
         //[deny]~^ ERROR non-exhaustive patterns
-        0 ..= usize::MAX => {}
+        0..=usize::MAX => {}
     }
 
     match 0isize {
         //[deny]~^ ERROR non-exhaustive patterns
-        isize::MIN ..= isize::MAX => {}
+        isize::MIN..=isize::MAX => {}
     }
 
-    m!(0usize, 0..);
     m!(0usize, 0..=usize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
     m!(0usize, 0..5 | 5..=usize::MAX);
@@ -30,26 +29,32 @@ fn main() {
     //[deny]~^ ERROR non-exhaustive patterns
     m!((0usize, true), (0..5, true) | (5..=usize::MAX, true) | (0..=usize::MAX, false));
     //[deny]~^ ERROR non-exhaustive patterns
+
+    m!(0usize, 0..);
+    m!(0usize, 0..5 | 5..);
+    m!(0usize, ..5 | 5..);
+    m!((0usize, true), (0..5, true) | (5.., true) | (0.., false));
     m!(0usize, 0..=usize::MAX | usize::MAX..);
 
-    m!(0isize, ..0 | 0..);
     m!(0isize, isize::MIN..=isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
     m!(0isize, isize::MIN..5 | 5..=isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
+    m!(0isize, isize::MIN..=-1 | 0 | 1..=isize::MAX);
+    //[deny]~^ ERROR non-exhaustive patterns
     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
-    m!((0isize, true), (isize::MIN..5, true)
-        | (5..=isize::MAX, true) | (isize::MIN..=isize::MAX, false));
-    //[deny]~^^ ERROR non-exhaustive patterns
-    m!(0isize, ..=isize::MIN | isize::MIN..=isize::MAX | isize::MAX..);
+    m!(
+        (0isize, true),
+        (isize::MIN..5, true) | (5..=isize::MAX, true) | (isize::MIN..=isize::MAX, false)
+    );
+    //[deny]~^^^ ERROR non-exhaustive patterns
 
-    match 0isize {
-        //[deny]~^ ERROR non-exhaustive patterns
-        isize::MIN ..= -1 => {}
-        0 => {}
-        1 ..= isize::MAX => {}
-    }
+    m!(0isize, ..0 | 0..);
+    m!(0isize, ..5 | 5..);
+    m!((0isize, true), (..5, true)
+        | (5.., true) | (..0 | 0.., false));
+    m!(0isize, ..=isize::MIN | isize::MIN..=isize::MAX | isize::MAX..);
 
     match 7usize {}
     //~^ ERROR non-exhaustive patterns
diff --git a/tests/ui/pattern/usefulness/integer-ranges/reachability.rs b/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
index fb4d59b0578..247fdd91572 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
+++ b/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
@@ -9,9 +9,10 @@ macro_rules! m {
             $t2 => {}
             _ => {}
         }
-    }
+    };
 }
 
+#[rustfmt::skip]
 fn main() {
     m!(0u8, 42, 41);
     m!(0u8, 42, 42); //~ ERROR unreachable pattern
@@ -85,7 +86,7 @@ fn main() {
     match 'a' {
         '\u{0}'..='\u{D7FF}' => {},
         '\u{E000}'..='\u{10_FFFF}' => {},
-        '\u{D7FF}'..='\u{E000}' => {}, // FIXME should be unreachable
+        '\u{D7FF}'..='\u{E000}' => {}, //~ ERROR unreachable pattern
     }
 
     match (0u8, true) {
diff --git a/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr b/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
index 0ffb0ffd82a..c5b028d2038 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
@@ -1,5 +1,5 @@
 error: unreachable pattern
-  --> $DIR/reachability.rs:17:17
+  --> $DIR/reachability.rs:18:17
    |
 LL |     m!(0u8, 42, 42);
    |                 ^^
@@ -11,127 +11,127 @@ LL | #![deny(unreachable_patterns)]
    |         ^^^^^^^^^^^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:21:22
+  --> $DIR/reachability.rs:22:22
    |
 LL |     m!(0u8, 20..=30, 20);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:22:22
+  --> $DIR/reachability.rs:23:22
    |
 LL |     m!(0u8, 20..=30, 21);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:23:22
+  --> $DIR/reachability.rs:24:22
    |
 LL |     m!(0u8, 20..=30, 25);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:24:22
+  --> $DIR/reachability.rs:25:22
    |
 LL |     m!(0u8, 20..=30, 29);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:25:22
+  --> $DIR/reachability.rs:26:22
    |
 LL |     m!(0u8, 20..=30, 30);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:28:21
+  --> $DIR/reachability.rs:29:21
    |
 LL |     m!(0u8, 20..30, 20);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:29:21
+  --> $DIR/reachability.rs:30:21
    |
 LL |     m!(0u8, 20..30, 21);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:30:21
+  --> $DIR/reachability.rs:31:21
    |
 LL |     m!(0u8, 20..30, 25);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:31:21
+  --> $DIR/reachability.rs:32:21
    |
 LL |     m!(0u8, 20..30, 29);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:35:22
+  --> $DIR/reachability.rs:36:22
    |
 LL |     m!(0u8, 20..=30, 20..=30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:36:22
+  --> $DIR/reachability.rs:37:22
    |
 LL |     m!(0u8, 20.. 30, 20.. 30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:37:22
+  --> $DIR/reachability.rs:38:22
    |
 LL |     m!(0u8, 20..=30, 20.. 30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:39:22
+  --> $DIR/reachability.rs:40:22
    |
 LL |     m!(0u8, 20..=30, 21..=30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:40:22
+  --> $DIR/reachability.rs:41:22
    |
 LL |     m!(0u8, 20..=30, 20..=29);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:42:24
+  --> $DIR/reachability.rs:43:24
    |
 LL |     m!('a', 'A'..='z', 'a'..='z');
    |                        ^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:49:9
+  --> $DIR/reachability.rs:50:9
    |
 LL |         5..=8 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:55:9
+  --> $DIR/reachability.rs:56:9
    |
 LL |         5..15 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:62:9
+  --> $DIR/reachability.rs:63:9
    |
 LL |         5..25 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:70:9
+  --> $DIR/reachability.rs:71:9
    |
 LL |         5..25 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:76:9
+  --> $DIR/reachability.rs:77:9
    |
 LL |         5..15 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:83:9
+  --> $DIR/reachability.rs:84:9
    |
 LL |         _ => {},
    |         - matches any value
@@ -139,16 +139,22 @@ LL |         '\u{D7FF}'..='\u{E000}' => {},
    |         ^^^^^^^^^^^^^^^^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:104:9
+  --> $DIR/reachability.rs:89:9
+   |
+LL |         '\u{D7FF}'..='\u{E000}' => {},
+   |         ^^^^^^^^^^^^^^^^^^^^^^^
+
+error: unreachable pattern
+  --> $DIR/reachability.rs:105:9
    |
 LL |         &FOO => {}
    |         ^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:105:9
+  --> $DIR/reachability.rs:106:9
    |
 LL |         BAR => {}
    |         ^^^
 
-error: aborting due to 24 previous errors
+error: aborting due to 25 previous errors
 
diff --git a/tests/ui/pattern/usefulness/issue-3601.rs b/tests/ui/pattern/usefulness/issue-3601.rs
index a6d2b11f4ee..868e8c71027 100644
--- a/tests/ui/pattern/usefulness/issue-3601.rs
+++ b/tests/ui/pattern/usefulness/issue-3601.rs
@@ -31,7 +31,7 @@ fn main() {
             //~^ ERROR non-exhaustive patterns
             //~| NOTE the matched value is of type
             //~| NOTE match arms with guards don't count towards exhaustivity
-            //~| NOTE pattern `box _` not covered
+            //~| NOTE pattern `box ElementKind::HTMLImageElement(_)` not covered
             //~| NOTE `Box<ElementKind>` defined here
             box ElementKind::HTMLImageElement(ref d) if d.image.is_some() => true,
         },
diff --git a/tests/ui/pattern/usefulness/issue-3601.stderr b/tests/ui/pattern/usefulness/issue-3601.stderr
index ce18b736c10..a3fcaa79b06 100644
--- a/tests/ui/pattern/usefulness/issue-3601.stderr
+++ b/tests/ui/pattern/usefulness/issue-3601.stderr
@@ -1,8 +1,8 @@
-error[E0004]: non-exhaustive patterns: `box _` not covered
+error[E0004]: non-exhaustive patterns: `box ElementKind::HTMLImageElement(_)` not covered
   --> $DIR/issue-3601.rs:30:44
    |
 LL |         box NodeKind::Element(ed) => match ed.kind {
-   |                                            ^^^^^^^ pattern `box _` not covered
+   |                                            ^^^^^^^ pattern `box ElementKind::HTMLImageElement(_)` not covered
    |
 note: `Box<ElementKind>` defined here
   --> $SRC_DIR/alloc/src/boxed.rs:LL:COL
@@ -11,7 +11,7 @@ note: `Box<ElementKind>` defined here
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern or an explicit pattern as shown
    |
 LL ~             box ElementKind::HTMLImageElement(ref d) if d.image.is_some() => true,
-LL ~             box _ => todo!(),
+LL ~             box ElementKind::HTMLImageElement(_) => todo!(),
    |
 
 error: aborting due to 1 previous error
diff --git a/tests/ui/pattern/usefulness/match-non-exhaustive.stderr b/tests/ui/pattern/usefulness/match-non-exhaustive.stderr
index 4fa3a729212..1a0cc58f35d 100644
--- a/tests/ui/pattern/usefulness/match-non-exhaustive.stderr
+++ b/tests/ui/pattern/usefulness/match-non-exhaustive.stderr
@@ -10,18 +10,18 @@ help: ensure that all possible cases are being handled by adding a match arm wit
 LL |     match 0 { 1 => (), i32::MIN..=0_i32 | 2_i32..=i32::MAX => todo!() }
    |                      ++++++++++++++++++++++++++++++++++++++++++++++++
 
-error[E0004]: non-exhaustive patterns: `_` not covered
+error[E0004]: non-exhaustive patterns: `i32::MIN..=-1_i32` and `1_i32..=i32::MAX` not covered
   --> $DIR/match-non-exhaustive.rs:3:11
    |
 LL |     match 0 { 0 if false => () }
-   |           ^ pattern `_` not covered
+   |           ^ patterns `i32::MIN..=-1_i32` and `1_i32..=i32::MAX` not covered
    |
    = note: the matched value is of type `i32`
    = note: match arms with guards don't count towards exhaustivity
-help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern or an explicit pattern as shown
+help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL |     match 0 { 0 if false => (), _ => todo!() }
-   |                               ++++++++++++++
+LL |     match 0 { 0 if false => (), i32::MIN..=-1_i32 | 1_i32..=i32::MAX => todo!() }
+   |                               +++++++++++++++++++++++++++++++++++++++++++++++++
 
 error: aborting due to 2 previous errors
 
diff --git a/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.rs b/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.rs
index 46e0da5be9b..97ded70fc92 100644
--- a/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.rs
+++ b/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.rs
@@ -44,6 +44,10 @@ fn main() {
         [] => {}
     }
     match s {
+        //~^ ERROR `&[]` and `&[_, ..]` not covered
+        [..] if false => {}
+    }
+    match s {
         //~^ ERROR `&[_, _, ..]` not covered
         [] => {}
         [_] => {}
diff --git a/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.stderr b/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.stderr
index fb6ecda3c4d..a8786d02414 100644
--- a/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.stderr
+++ b/tests/ui/pattern/usefulness/slice-patterns-exhaustiveness.stderr
@@ -89,10 +89,24 @@ LL ~         [] => {},
 LL +         &[_, ..] => todo!()
    |
 
-error[E0004]: non-exhaustive patterns: `&[_, _, ..]` not covered
+error[E0004]: non-exhaustive patterns: `&[]` and `&[_, ..]` not covered
   --> $DIR/slice-patterns-exhaustiveness.rs:46:11
    |
 LL |     match s {
+   |           ^ patterns `&[]` and `&[_, ..]` not covered
+   |
+   = note: the matched value is of type `&[bool]`
+   = note: match arms with guards don't count towards exhaustivity
+help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
+   |
+LL ~         [..] if false => {},
+LL +         &[] | &[_, ..] => todo!()
+   |
+
+error[E0004]: non-exhaustive patterns: `&[_, _, ..]` not covered
+  --> $DIR/slice-patterns-exhaustiveness.rs:50:11
+   |
+LL |     match s {
    |           ^ pattern `&[_, _, ..]` not covered
    |
    = note: the matched value is of type `&[bool]`
@@ -103,7 +117,7 @@ LL +         &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[false, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:51:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:55:11
    |
 LL |     match s {
    |           ^ pattern `&[false, ..]` not covered
@@ -116,7 +130,7 @@ LL +         &[false, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[false, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:56:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:60:11
    |
 LL |     match s {
    |           ^ pattern `&[false, _, ..]` not covered
@@ -129,7 +143,7 @@ LL +         &[false, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[_, .., false]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:62:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:66:11
    |
 LL |     match s {
    |           ^ pattern `&[_, .., false]` not covered
@@ -142,7 +156,7 @@ LL +         &[_, .., false] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[_, _, .., true]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:69:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:73:11
    |
 LL |     match s {
    |           ^ pattern `&[_, _, .., true]` not covered
@@ -155,7 +169,7 @@ LL +         &[_, _, .., true] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[true, _, .., _]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:76:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:80:11
    |
 LL |     match s {
    |           ^ pattern `&[true, _, .., _]` not covered
@@ -168,7 +182,7 @@ LL +         &[true, _, .., _] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[]` and `&[_, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:85:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:89:11
    |
 LL |     match s {
    |           ^ patterns `&[]` and `&[_, _, ..]` not covered
@@ -181,7 +195,7 @@ LL +         &[] | &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[]` and `&[_, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:89:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:93:11
    |
 LL |     match s {
    |           ^ patterns `&[]` and `&[_, _, ..]` not covered
@@ -194,7 +208,7 @@ LL +         &[] | &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[]` and `&[_, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:93:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:97:11
    |
 LL |     match s {
    |           ^ patterns `&[]` and `&[_, _, ..]` not covered
@@ -207,7 +221,7 @@ LL +         &[] | &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[]` and `&[_, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:98:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:102:11
    |
 LL |     match s {
    |           ^ patterns `&[]` and `&[_, _, ..]` not covered
@@ -220,7 +234,7 @@ LL +         &[] | &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[_, _, ..]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:103:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:107:11
    |
 LL |     match s {
    |           ^ pattern `&[_, _, ..]` not covered
@@ -233,7 +247,7 @@ LL +         &[_, _, ..] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[false]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:108:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:112:11
    |
 LL |     match s {
    |           ^ pattern `&[false]` not covered
@@ -246,7 +260,7 @@ LL +         &[false] => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `&[false]` not covered
-  --> $DIR/slice-patterns-exhaustiveness.rs:121:11
+  --> $DIR/slice-patterns-exhaustiveness.rs:125:11
    |
 LL |     match s1 {
    |           ^^ pattern `&[false]` not covered
@@ -258,6 +272,6 @@ LL ~         CONST1 => {},
 LL +         &[false] => todo!()
    |
 
-error: aborting due to 20 previous errors
+error: aborting due to 21 previous errors
 
 For more information about this error, try `rustc --explain E0004`.
diff --git a/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.rs b/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.rs
index e0a6051a81f..a6c1dc53f8b 100644
--- a/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.rs
+++ b/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.rs
@@ -1,6 +1,7 @@
 // Test that the `non_exhaustive_omitted_patterns` lint is triggered correctly.
 
 #![feature(non_exhaustive_omitted_patterns_lint, unstable_test_feature)]
+#![deny(unreachable_patterns)]
 
 // aux-build:enums.rs
 extern crate enums;
@@ -31,11 +32,21 @@ pub enum Bar {
     C,
 }
 
+fn no_lint() {
+    let non_enum = NonExhaustiveEnum::Unit;
+    // Ok: without the attribute
+    match non_enum {
+        NonExhaustiveEnum::Unit => {}
+        NonExhaustiveEnum::Tuple(_) => {}
+        _ => {}
+    }
+}
+
+#[deny(non_exhaustive_omitted_patterns)]
 fn main() {
     let enumeration = Bar::A;
 
     // Ok: this is a crate local non_exhaustive enum
-    #[deny(non_exhaustive_omitted_patterns)]
     match enumeration {
         Bar::A => {}
         Bar::B => {}
@@ -44,14 +55,13 @@ fn main() {
 
     let non_enum = NonExhaustiveEnum::Unit;
 
-    // Ok: without the attribute
+    #[allow(non_exhaustive_omitted_patterns)]
     match non_enum {
         NonExhaustiveEnum::Unit => {}
         NonExhaustiveEnum::Tuple(_) => {}
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match non_enum {
         //~^ some variants are not matched explicitly
         NonExhaustiveEnum::Unit => {}
@@ -59,7 +69,6 @@ fn main() {
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match non_enum {
         //~^ some variants are not matched explicitly
         NonExhaustiveEnum::Unit | NonExhaustiveEnum::Struct { .. } => {}
@@ -68,7 +77,6 @@ fn main() {
 
     let x = 5;
     // We ignore the guard.
-    #[deny(non_exhaustive_omitted_patterns)]
     match non_enum {
         NonExhaustiveEnum::Unit if x > 10 => {}
         NonExhaustiveEnum::Tuple(_) => {}
@@ -76,14 +84,12 @@ fn main() {
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match (non_enum, true) {
         (NonExhaustiveEnum::Unit, true) => {}
         (NonExhaustiveEnum::Tuple(_), false) => {}
         (NonExhaustiveEnum::Struct { .. }, false) => {}
         _ => {}
     }
-    #[deny(non_exhaustive_omitted_patterns)]
     match (non_enum, true) {
         //~^ some variants are not matched explicitly
         (NonExhaustiveEnum::Unit, true) => {}
@@ -91,14 +97,12 @@ fn main() {
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match (true, non_enum) {
         (true, NonExhaustiveEnum::Unit) => {}
         (false, NonExhaustiveEnum::Tuple(_)) => {}
         (false, NonExhaustiveEnum::Struct { .. }) => {}
         _ => {}
     }
-    #[deny(non_exhaustive_omitted_patterns)]
     match (true, non_enum) {
         //~^ some variants are not matched explicitly
         (true, NonExhaustiveEnum::Unit) => {}
@@ -106,7 +110,6 @@ fn main() {
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match Some(non_enum) {
         //~^ some variants are not matched explicitly
         Some(NonExhaustiveEnum::Unit) => {}
@@ -116,7 +119,6 @@ fn main() {
 
     // Ok: all covered and not `unreachable-patterns`
     #[deny(unreachable_patterns)]
-    #[deny(non_exhaustive_omitted_patterns)]
     match non_enum {
         NonExhaustiveEnum::Unit => {}
         NonExhaustiveEnum::Tuple(_) => {}
@@ -124,7 +126,6 @@ fn main() {
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match NestedNonExhaustive::B {
         //~^ some variants are not matched explicitly
         NestedNonExhaustive::A(NonExhaustiveEnum::Unit) => {}
@@ -133,54 +134,53 @@ fn main() {
         _ => {}
     }
 
-    #[warn(non_exhaustive_omitted_patterns)]
     match VariantNonExhaustive::Baz(1, 2) {
         VariantNonExhaustive::Baz(_, _) => {}
         VariantNonExhaustive::Bar { x, .. } => {}
     }
     //~^^ some fields are not explicitly listed
 
-    #[warn(non_exhaustive_omitted_patterns)]
     let FunctionalRecord { first_field, second_field, .. } = FunctionalRecord::default();
     //~^ some fields are not explicitly listed
 
     // Ok: this is local
-    #[warn(non_exhaustive_omitted_patterns)]
     let Foo { a, b, .. } = Foo::default();
 
-    #[warn(non_exhaustive_omitted_patterns)]
     let NestedStruct { bar: NormalStruct { first_field, .. }, .. } = NestedStruct::default();
     //~^ some fields are not explicitly listed
     //~^^ some fields are not explicitly listed
 
     // Ok: this tests https://github.com/rust-lang/rust/issues/89382
-    #[warn(non_exhaustive_omitted_patterns)]
     let MixedVisFields { a, b, .. } = MixedVisFields::default();
 
     // Ok: this only has 1 variant
-    #[deny(non_exhaustive_omitted_patterns)]
     match NonExhaustiveSingleVariant::A(true) {
         NonExhaustiveSingleVariant::A(true) => {}
         _ => {}
     }
 
     // We can't catch the case below, so for consistency we don't catch this one either.
-    #[deny(non_exhaustive_omitted_patterns)]
     match NonExhaustiveSingleVariant::A(true) {
         _ => {}
     }
     // We can't catch this case, because this would require digging fully through all the values of
     // any type we encounter. We need to be able to only consider present constructors.
-    #[deny(non_exhaustive_omitted_patterns)]
     match &NonExhaustiveSingleVariant::A(true) {
         _ => {}
     }
 
+    match Some(NonExhaustiveSingleVariant::A(true)) {
+        Some(_) => {}
+        None => {}
+    }
+    match Some(&NonExhaustiveSingleVariant::A(true)) {
+        Some(_) => {}
+        None => {}
+    }
+
     // Ok: we don't lint on `if let` expressions
-    #[deny(non_exhaustive_omitted_patterns)]
     if let NonExhaustiveEnum::Tuple(_) = non_enum {}
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match UnstableEnum::Stable {
         //~^ some variants are not matched explicitly
         UnstableEnum::Stable => {}
@@ -189,7 +189,6 @@ fn main() {
     }
 
     // Ok: the feature is on and all variants are matched
-    #[deny(non_exhaustive_omitted_patterns)]
     match UnstableEnum::Stable {
         UnstableEnum::Stable => {}
         UnstableEnum::Stable2 => {}
@@ -198,52 +197,66 @@ fn main() {
     }
 
     // Ok: the feature is on and both variants are matched
-    #[deny(non_exhaustive_omitted_patterns)]
     match OnlyUnstableEnum::Unstable {
         OnlyUnstableEnum::Unstable => {}
         OnlyUnstableEnum::Unstable2 => {}
         _ => {}
     }
 
-    #[deny(non_exhaustive_omitted_patterns)]
     match OnlyUnstableEnum::Unstable {
         //~^ some variants are not matched explicitly
         OnlyUnstableEnum::Unstable => {}
         _ => {}
     }
 
-    #[warn(non_exhaustive_omitted_patterns)]
     let OnlyUnstableStruct { unstable, .. } = OnlyUnstableStruct::new();
     //~^ some fields are not explicitly listed
 
     // OK: both unstable fields are matched with feature on
-    #[warn(non_exhaustive_omitted_patterns)]
     let OnlyUnstableStruct { unstable, unstable2, .. } = OnlyUnstableStruct::new();
 
-    #[warn(non_exhaustive_omitted_patterns)]
     let UnstableStruct { stable, stable2, .. } = UnstableStruct::default();
     //~^ some fields are not explicitly listed
 
     // OK: both unstable and stable fields are matched with feature on
-    #[warn(non_exhaustive_omitted_patterns)]
     let UnstableStruct { stable, stable2, unstable, .. } = UnstableStruct::default();
 
     // Ok: local bindings are allowed
-    #[deny(non_exhaustive_omitted_patterns)]
     let local = NonExhaustiveEnum::Unit;
 
     // Ok: missing patterns will be blocked by the pattern being refutable
-    #[deny(non_exhaustive_omitted_patterns)]
     let local_refutable @ NonExhaustiveEnum::Unit = NonExhaustiveEnum::Unit;
     //~^ refutable pattern in local binding
 
-    #[deny(non_exhaustive_omitted_patterns)]
+    // Check that matching on a reference results in a correct diagnostic
     match &non_enum {
         //~^ some variants are not matched explicitly
+        //~| pattern `&NonExhaustiveEnum::Struct { .. }` not covered
         NonExhaustiveEnum::Unit => {}
         NonExhaustiveEnum::Tuple(_) => {}
         _ => {}
     }
+
+    match (true, &non_enum) {
+        //~^ some variants are not matched explicitly
+        //~| patterns `(_, &NonExhaustiveEnum::Tuple(_))` and `(_, &NonExhaustiveEnum::Struct { .. })` not covered
+        (true, NonExhaustiveEnum::Unit) => {}
+        _ => {}
+    }
+
+    match (&non_enum, true) {
+        //~^ some variants are not matched explicitly
+        //~| patterns `(&NonExhaustiveEnum::Tuple(_), _)` and `(&NonExhaustiveEnum::Struct { .. }, _)` not covered
+        (NonExhaustiveEnum::Unit, true) => {}
+        _ => {}
+    }
+
+    match Some(&non_enum) {
+        //~^ some variants are not matched explicitly
+        //~| pattern `Some(&NonExhaustiveEnum::Struct { .. })` not covered
+        Some(NonExhaustiveEnum::Unit | NonExhaustiveEnum::Tuple(_)) => {}
+        _ => {}
+    }
 }
 
 #[deny(non_exhaustive_omitted_patterns)]
diff --git a/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.stderr b/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.stderr
index 7db61f1241e..1037033c4b7 100644
--- a/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.stderr
+++ b/tests/ui/rfcs/rfc-2008-non-exhaustive/omitted-patterns.stderr
@@ -1,4 +1,4 @@
-warning: some fields are not explicitly listed
+error: some fields are not explicitly listed
   --> $DIR/omitted-patterns.rs:139:9
    |
 LL |         VariantNonExhaustive::Bar { x, .. } => {}
@@ -7,41 +7,31 @@ LL |         VariantNonExhaustive::Bar { x, .. } => {}
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `VariantNonExhaustive` and the `non_exhaustive_omitted_patterns` attribute was found
 note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:136:12
+  --> $DIR/omitted-patterns.rs:45:8
    |
-LL |     #[warn(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+LL | #[deny(non_exhaustive_omitted_patterns)]
+   |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-warning: some fields are not explicitly listed
-  --> $DIR/omitted-patterns.rs:144:9
+error: some fields are not explicitly listed
+  --> $DIR/omitted-patterns.rs:143:9
    |
 LL |     let FunctionalRecord { first_field, second_field, .. } = FunctionalRecord::default();
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ field `third_field` not listed
    |
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `FunctionalRecord` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:143:12
-   |
-LL |     #[warn(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-warning: some fields are not explicitly listed
-  --> $DIR/omitted-patterns.rs:152:29
+error: some fields are not explicitly listed
+  --> $DIR/omitted-patterns.rs:149:29
    |
 LL |     let NestedStruct { bar: NormalStruct { first_field, .. }, .. } = NestedStruct::default();
    |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ field `second_field` not listed
    |
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `NormalStruct` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:151:12
-   |
-LL |     #[warn(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-warning: some fields are not explicitly listed
-  --> $DIR/omitted-patterns.rs:152:9
+error: some fields are not explicitly listed
+  --> $DIR/omitted-patterns.rs:149:9
    |
 LL |     let NestedStruct { bar: NormalStruct { first_field, .. }, .. } = NestedStruct::default();
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ field `foo` not listed
@@ -49,117 +39,77 @@ LL |     let NestedStruct { bar: NormalStruct { first_field, .. }, .. } = Nested
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `NestedStruct` and the `non_exhaustive_omitted_patterns` attribute was found
 
-warning: some fields are not explicitly listed
-  --> $DIR/omitted-patterns.rs:216:9
+error: some fields are not explicitly listed
+  --> $DIR/omitted-patterns.rs:212:9
    |
 LL |     let OnlyUnstableStruct { unstable, .. } = OnlyUnstableStruct::new();
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ field `unstable2` not listed
    |
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `OnlyUnstableStruct` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:215:12
-   |
-LL |     #[warn(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-warning: some fields are not explicitly listed
-  --> $DIR/omitted-patterns.rs:224:9
+error: some fields are not explicitly listed
+  --> $DIR/omitted-patterns.rs:218:9
    |
 LL |     let UnstableStruct { stable, stable2, .. } = UnstableStruct::default();
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ field `unstable` not listed
    |
    = help: ensure that all fields are mentioned explicitly by adding the suggested fields
    = note: the pattern is of type `UnstableStruct` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:223:12
-   |
-LL |     #[warn(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:55:11
+  --> $DIR/omitted-patterns.rs:65:11
    |
 LL |     match non_enum {
    |           ^^^^^^^^ pattern `NonExhaustiveEnum::Struct { .. }` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `NonExhaustiveEnum` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:54:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:63:11
+  --> $DIR/omitted-patterns.rs:72:11
    |
 LL |     match non_enum {
    |           ^^^^^^^^ pattern `NonExhaustiveEnum::Tuple(_)` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `NonExhaustiveEnum` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:62:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:87:11
+  --> $DIR/omitted-patterns.rs:93:11
    |
 LL |     match (non_enum, true) {
    |           ^^^^^^^^^^^^^^^^ pattern `(NonExhaustiveEnum::Struct { .. }, _)` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `(NonExhaustiveEnum, bool)` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:86:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:102:11
+  --> $DIR/omitted-patterns.rs:106:11
    |
 LL |     match (true, non_enum) {
    |           ^^^^^^^^^^^^^^^^ pattern `(_, NonExhaustiveEnum::Struct { .. })` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `(bool, NonExhaustiveEnum)` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:101:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:110:11
+  --> $DIR/omitted-patterns.rs:113:11
    |
 LL |     match Some(non_enum) {
    |           ^^^^^^^^^^^^^^ pattern `Some(NonExhaustiveEnum::Struct { .. })` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `Option<NonExhaustiveEnum>` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:109:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:128:11
+  --> $DIR/omitted-patterns.rs:129:11
    |
 LL |     match NestedNonExhaustive::B {
    |           ^^^^^^^^^^^^^^^^^^^^^^ patterns `NestedNonExhaustive::C`, `NestedNonExhaustive::A(NonExhaustiveEnum::Tuple(_))` and `NestedNonExhaustive::A(NonExhaustiveEnum::Struct { .. })` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `NestedNonExhaustive` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:127:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
   --> $DIR/omitted-patterns.rs:184:11
@@ -169,28 +119,18 @@ LL |     match UnstableEnum::Stable {
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `UnstableEnum` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:183:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:209:11
+  --> $DIR/omitted-patterns.rs:206:11
    |
 LL |     match OnlyUnstableEnum::Unstable {
    |           ^^^^^^^^^^^^^^^^^^^^^^^^^^ pattern `OnlyUnstableEnum::Unstable2` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `OnlyUnstableEnum` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:208:12
-   |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error[E0005]: refutable pattern in local binding
-  --> $DIR/omitted-patterns.rs:237:9
+  --> $DIR/omitted-patterns.rs:228:9
    |
 LL |     let local_refutable @ NonExhaustiveEnum::Unit = NonExhaustiveEnum::Unit;
    |         ^^^^^^^^^^^^^^^ pattern `_` not covered
@@ -204,19 +144,41 @@ LL |     let local_refutable @ NonExhaustiveEnum::Unit = NonExhaustiveEnum::Unit
    |                                                                             ++++++++++++++++
 
 error: some variants are not matched explicitly
-  --> $DIR/omitted-patterns.rs:241:11
+  --> $DIR/omitted-patterns.rs:232:11
    |
 LL |     match &non_enum {
    |           ^^^^^^^^^ pattern `&NonExhaustiveEnum::Struct { .. }` not covered
    |
    = help: ensure that all variants are matched explicitly by adding the suggested match arms
    = note: the matched value is of type `&NonExhaustiveEnum` and the `non_exhaustive_omitted_patterns` attribute was found
-note: the lint level is defined here
-  --> $DIR/omitted-patterns.rs:240:12
+
+error: some variants are not matched explicitly
+  --> $DIR/omitted-patterns.rs:240:11
+   |
+LL |     match (true, &non_enum) {
+   |           ^^^^^^^^^^^^^^^^^ patterns `(_, &NonExhaustiveEnum::Tuple(_))` and `(_, &NonExhaustiveEnum::Struct { .. })` not covered
    |
-LL |     #[deny(non_exhaustive_omitted_patterns)]
-   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   = help: ensure that all variants are matched explicitly by adding the suggested match arms
+   = note: the matched value is of type `(bool, &NonExhaustiveEnum)` and the `non_exhaustive_omitted_patterns` attribute was found
+
+error: some variants are not matched explicitly
+  --> $DIR/omitted-patterns.rs:247:11
+   |
+LL |     match (&non_enum, true) {
+   |           ^^^^^^^^^^^^^^^^^ patterns `(&NonExhaustiveEnum::Tuple(_), _)` and `(&NonExhaustiveEnum::Struct { .. }, _)` not covered
+   |
+   = help: ensure that all variants are matched explicitly by adding the suggested match arms
+   = note: the matched value is of type `(&NonExhaustiveEnum, bool)` and the `non_exhaustive_omitted_patterns` attribute was found
+
+error: some variants are not matched explicitly
+  --> $DIR/omitted-patterns.rs:254:11
+   |
+LL |     match Some(&non_enum) {
+   |           ^^^^^^^^^^^^^^^ pattern `Some(&NonExhaustiveEnum::Struct { .. })` not covered
+   |
+   = help: ensure that all variants are matched explicitly by adding the suggested match arms
+   = note: the matched value is of type `Option<&NonExhaustiveEnum>` and the `non_exhaustive_omitted_patterns` attribute was found
 
-error: aborting due to 10 previous errors; 6 warnings emitted
+error: aborting due to 19 previous errors
 
 For more information about this error, try `rustc --explain E0005`.