Distinguish user patterns from reconstructed witnesses

4 files changed, 200 insertions, 167 deletions

diff --git a/compiler/rustc_mir_build/src/errors.rs b/compiler/rustc_mir_build/src/errors.rs
index 4f98932a88d..c09dd186418 100644
--- a/compiler/rustc_mir_build/src/errors.rs
+++ b/compiler/rustc_mir_build/src/errors.rs
@@ -1,6 +1,6 @@
 use crate::{
     fluent_generated as fluent,
-    thir::pattern::{deconstruct_pat::DeconstructedPat, MatchCheckCtxt},
+    thir::pattern::{deconstruct_pat::WitnessPat, MatchCheckCtxt},
 };
 use rustc_errors::{
     error_code, AddToDiagnostic, Applicability, Diagnostic, DiagnosticBuilder, ErrorGuaranteed,
@@ -810,7 +810,7 @@ impl<'tcx> Uncovered<'tcx> {
     pub fn new<'p>(
         span: Span,
         cx: &MatchCheckCtxt<'p, 'tcx>,
-        witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
+        witnesses: Vec<WitnessPat<'tcx>>,
     ) -> Self {
         let witness_1 = witnesses.get(0).unwrap().to_pat(cx);
         Self {
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 93434dd3cc2..f3568b682a4 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -1,4 +1,4 @@
-use super::deconstruct_pat::{Constructor, DeconstructedPat};
+use super::deconstruct_pat::{Constructor, DeconstructedPat, WitnessPat};
 use super::usefulness::{
     compute_match_usefulness, MatchArm, MatchCheckCtxt, Reachability, UsefulnessReport,
 };
@@ -661,8 +661,8 @@ fn report_arm_reachability<'p, 'tcx>(
     }
 }
 
-fn collect_non_exhaustive_tys<'p, 'tcx>(
-    pat: &DeconstructedPat<'p, 'tcx>,
+fn collect_non_exhaustive_tys<'tcx>(
+    pat: &WitnessPat<'tcx>,
     non_exhaustive_tys: &mut FxHashSet<Ty<'tcx>>,
 ) {
     if matches!(pat.ctor(), Constructor::NonExhaustive) {
@@ -678,7 +678,7 @@ fn non_exhaustive_match<'p, 'tcx>(
     thir: &Thir<'tcx>,
     scrut_ty: Ty<'tcx>,
     sp: Span,
-    witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
+    witnesses: Vec<WitnessPat<'tcx>>,
     arms: &[ArmId],
     expr_span: Span,
 ) -> ErrorGuaranteed {
@@ -860,10 +860,10 @@ fn non_exhaustive_match<'p, 'tcx>(
 
 pub(crate) fn joined_uncovered_patterns<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
-    witnesses: &[DeconstructedPat<'p, 'tcx>],
+    witnesses: &[WitnessPat<'tcx>],
 ) -> String {
     const LIMIT: usize = 3;
-    let pat_to_str = |pat: &DeconstructedPat<'p, 'tcx>| pat.to_pat(cx).to_string();
+    let pat_to_str = |pat: &WitnessPat<'tcx>| pat.to_pat(cx).to_string();
     match witnesses {
         [] => bug!(),
         [witness] => format!("`{}`", witness.to_pat(cx)),
@@ -880,7 +880,7 @@ pub(crate) fn joined_uncovered_patterns<'p, 'tcx>(
 }
 
 pub(crate) fn pattern_not_covered_label(
-    witnesses: &[DeconstructedPat<'_, '_>],
+    witnesses: &[WitnessPat<'_>],
     joined_patterns: &str,
 ) -> String {
     format!("pattern{} {} not covered", rustc_errors::pluralize!(witnesses.len()), joined_patterns)
@@ -891,7 +891,7 @@ fn adt_defined_here<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     err: &mut Diagnostic,
     ty: Ty<'tcx>,
-    witnesses: &[DeconstructedPat<'p, 'tcx>],
+    witnesses: &[WitnessPat<'tcx>],
 ) {
     let ty = ty.peel_refs();
     if let ty::Adt(def, _) = ty.kind() {
@@ -922,7 +922,7 @@ fn adt_defined_here<'p, 'tcx>(
 fn maybe_point_at_variant<'a, 'p: 'a, 'tcx: 'a>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     def: AdtDef<'tcx>,
-    patterns: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>,
+    patterns: impl Iterator<Item = &'a WitnessPat<'tcx>>,
 ) -> Vec<Span> {
     use Constructor::*;
     let mut covered = vec![];
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 a7a000ba31c..818a8ff27c8 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
@@ -1312,9 +1312,10 @@ impl<'p, 'tcx> Fields<'p, 'tcx> {
 
 /// Values and patterns can be represented as a constructor applied to some fields. This represents
 /// a pattern in this form.
-/// This also keeps track of whether the pattern has been found reachable during analysis. For this
-/// reason we should be careful not to clone patterns for which we care about that. Use
-/// `clone_and_forget_reachability` if you're sure.
+/// This also uses interior mutability to keep track of whether the pattern has been found reachable
+/// during analysis. For this reason they cannot be cloned.
+/// A `DeconstructedPat` will almost always come from user input; the only exception are some
+/// `Wildcard`s introduced during specialization.
 pub(crate) struct DeconstructedPat<'p, 'tcx> {
     ctor: Constructor<'tcx>,
     fields: Fields<'p, 'tcx>,
@@ -1337,20 +1338,6 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) }
     }
 
-    /// Construct a pattern that matches everything that starts with this constructor.
-    /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
-    /// `Some(_)`.
-    pub(super) fn wild_from_ctor(pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: Constructor<'tcx>) -> Self {
-        let fields = Fields::wildcards(pcx, &ctor);
-        DeconstructedPat::new(ctor, fields, pcx.ty, pcx.span)
-    }
-
-    /// Clone this value. This method emphasizes that cloning loses reachability information and
-    /// should be done carefully.
-    pub(super) fn clone_and_forget_reachability(&self) -> Self {
-        DeconstructedPat::new(self.ctor.clone(), self.fields, self.ty, self.span)
-    }
-
     pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self {
         let mkpat = |pat| DeconstructedPat::from_pat(cx, pat);
         let ctor;
@@ -1529,95 +1516,6 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
         DeconstructedPat::new(ctor, fields, pat.ty, pat.span)
     }
 
-    pub(crate) fn to_pat(&self, cx: &MatchCheckCtxt<'p, 'tcx>) -> Pat<'tcx> {
-        let is_wildcard = |pat: &Pat<'_>| {
-            matches!(pat.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild)
-        };
-        let mut subpatterns = self.iter_fields().map(|p| Box::new(p.to_pat(cx)));
-        let kind = match &self.ctor {
-            Single | Variant(_) => match self.ty.kind() {
-                ty::Tuple(..) => PatKind::Leaf {
-                    subpatterns: subpatterns
-                        .enumerate()
-                        .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern })
-                        .collect(),
-                },
-                ty::Adt(adt_def, _) if adt_def.is_box() => {
-                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
-                    // of `std`). So this branch is only reachable when the feature is enabled and
-                    // the pattern is a box pattern.
-                    PatKind::Deref { subpattern: subpatterns.next().unwrap() }
-                }
-                ty::Adt(adt_def, args) => {
-                    let variant_index = self.ctor.variant_index_for_adt(*adt_def);
-                    let variant = &adt_def.variant(variant_index);
-                    let subpatterns = Fields::list_variant_nonhidden_fields(cx, self.ty, variant)
-                        .zip(subpatterns)
-                        .map(|((field, _ty), pattern)| FieldPat { field, pattern })
-                        .collect();
-
-                    if adt_def.is_enum() {
-                        PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns }
-                    } else {
-                        PatKind::Leaf { subpatterns }
-                    }
-                }
-                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
-                // be careful to reconstruct the correct constant pattern here. However a string
-                // literal pattern will never be reported as a non-exhaustiveness witness, so we
-                // ignore this issue.
-                ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
-                _ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty),
-            },
-            Slice(slice) => {
-                match slice.kind {
-                    FixedLen(_) => PatKind::Slice {
-                        prefix: subpatterns.collect(),
-                        slice: None,
-                        suffix: Box::new([]),
-                    },
-                    VarLen(prefix, _) => {
-                        let mut subpatterns = subpatterns.peekable();
-                        let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect();
-                        if slice.array_len.is_some() {
-                            // Improves diagnostics a bit: if the type is a known-size array, instead
-                            // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
-                            // This is incorrect if the size is not known, since `[_, ..]` captures
-                            // arrays of lengths `>= 1` whereas `[..]` captures any length.
-                            while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) {
-                                prefix.pop();
-                            }
-                            while subpatterns.peek().is_some()
-                                && is_wildcard(subpatterns.peek().unwrap())
-                            {
-                                subpatterns.next();
-                            }
-                        }
-                        let suffix: Box<[_]> = subpatterns.collect();
-                        let wild = Pat::wildcard_from_ty(self.ty);
-                        PatKind::Slice {
-                            prefix: prefix.into_boxed_slice(),
-                            slice: Some(Box::new(wild)),
-                            suffix,
-                        }
-                    }
-                }
-            }
-            &Str(value) => PatKind::Constant { value },
-            IntRange(range) => return range.to_pat(cx.tcx, self.ty),
-            Wildcard | NonExhaustive | Hidden => PatKind::Wild,
-            Missing { .. } => bug!(
-                "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
-                `Missing` should have been processed in `apply_constructors`"
-            ),
-            F32Range(..) | F64Range(..) | Opaque | Or => {
-                bug!("can't convert to pattern: {:?}", self)
-            }
-        };
-
-        Pat { ty: self.ty, span: DUMMY_SP, kind }
-    }
-
     pub(super) fn is_or_pat(&self) -> bool {
         matches!(self.ctor, Or)
     }
@@ -1800,3 +1698,131 @@ impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> {
         }
     }
 }
+
+/// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics
+/// purposes. As such they don't use interning and can be cloned.
+#[derive(Debug, Clone)]
+pub(crate) struct WitnessPat<'tcx> {
+    ctor: Constructor<'tcx>,
+    fields: Vec<WitnessPat<'tcx>>,
+    ty: Ty<'tcx>,
+}
+
+impl<'tcx> WitnessPat<'tcx> {
+    pub(super) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self {
+        Self { ctor, fields, ty }
+    }
+    pub(super) fn wildcard(ty: Ty<'tcx>) -> Self {
+        Self::new(Wildcard, Vec::new(), ty)
+    }
+
+    /// Construct a pattern that matches everything that starts with this constructor.
+    /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
+    /// `Some(_)`.
+    pub(super) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, 'tcx>, ctor: Constructor<'tcx>) -> Self {
+        // Reuse `Fields::wildcards` to get the types.
+        let fields = Fields::wildcards(pcx, &ctor)
+            .iter_patterns()
+            .map(|deco_pat| Self::wildcard(deco_pat.ty()))
+            .collect();
+        Self::new(ctor, fields, pcx.ty)
+    }
+
+    pub(super) fn ctor(&self) -> &Constructor<'tcx> {
+        &self.ctor
+    }
+    pub(super) fn ty(&self) -> Ty<'tcx> {
+        self.ty
+    }
+
+    pub(crate) fn to_pat(&self, cx: &MatchCheckCtxt<'_, 'tcx>) -> Pat<'tcx> {
+        let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild);
+        let mut subpatterns = self.iter_fields().map(|p| Box::new(p.to_pat(cx)));
+        let kind = match &self.ctor {
+            Single | Variant(_) => match self.ty.kind() {
+                ty::Tuple(..) => PatKind::Leaf {
+                    subpatterns: subpatterns
+                        .enumerate()
+                        .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern })
+                        .collect(),
+                },
+                ty::Adt(adt_def, _) if adt_def.is_box() => {
+                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
+                    // of `std`). So this branch is only reachable when the feature is enabled and
+                    // the pattern is a box pattern.
+                    PatKind::Deref { subpattern: subpatterns.next().unwrap() }
+                }
+                ty::Adt(adt_def, args) => {
+                    let variant_index = self.ctor.variant_index_for_adt(*adt_def);
+                    let variant = &adt_def.variant(variant_index);
+                    let subpatterns = Fields::list_variant_nonhidden_fields(cx, self.ty, variant)
+                        .zip(subpatterns)
+                        .map(|((field, _ty), pattern)| FieldPat { field, pattern })
+                        .collect();
+
+                    if adt_def.is_enum() {
+                        PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns }
+                    } else {
+                        PatKind::Leaf { subpatterns }
+                    }
+                }
+                // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
+                // be careful to reconstruct the correct constant pattern here. However a string
+                // literal pattern will never be reported as a non-exhaustiveness witness, so we
+                // ignore this issue.
+                ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
+                _ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty),
+            },
+            Slice(slice) => {
+                match slice.kind {
+                    FixedLen(_) => PatKind::Slice {
+                        prefix: subpatterns.collect(),
+                        slice: None,
+                        suffix: Box::new([]),
+                    },
+                    VarLen(prefix, _) => {
+                        let mut subpatterns = subpatterns.peekable();
+                        let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect();
+                        if slice.array_len.is_some() {
+                            // Improves diagnostics a bit: if the type is a known-size array, instead
+                            // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
+                            // This is incorrect if the size is not known, since `[_, ..]` captures
+                            // arrays of lengths `>= 1` whereas `[..]` captures any length.
+                            while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) {
+                                prefix.pop();
+                            }
+                            while subpatterns.peek().is_some()
+                                && is_wildcard(subpatterns.peek().unwrap())
+                            {
+                                subpatterns.next();
+                            }
+                        }
+                        let suffix: Box<[_]> = subpatterns.collect();
+                        let wild = Pat::wildcard_from_ty(self.ty);
+                        PatKind::Slice {
+                            prefix: prefix.into_boxed_slice(),
+                            slice: Some(Box::new(wild)),
+                            suffix,
+                        }
+                    }
+                }
+            }
+            &Str(value) => PatKind::Constant { value },
+            IntRange(range) => return range.to_pat(cx.tcx, self.ty),
+            Wildcard | NonExhaustive | Hidden => PatKind::Wild,
+            Missing { .. } => bug!(
+                "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
+                `Missing` should have been processed in `apply_constructors`"
+            ),
+            F32Range(..) | F64Range(..) | Opaque | Or => {
+                bug!("can't convert to pattern: {:?}", self)
+            }
+        };
+
+        Pat { ty: self.ty, span: DUMMY_SP, kind }
+    }
+
+    pub(super) fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> {
+        self.fields.iter()
+    }
+}
diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
index 6cd73c7eaa9..e60349be3ba 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
@@ -213,7 +213,7 @@
 //! 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
-//! [`Fields`] struct.
+//! [`super::deconstruct_pat::Fields`] struct.
 //!
 //!
 //! # Computing usefulness
@@ -307,7 +307,7 @@
 
 use self::ArmType::*;
 use self::Usefulness::*;
-use super::deconstruct_pat::{Constructor, ConstructorSet, DeconstructedPat, Fields};
+use super::deconstruct_pat::{Constructor, ConstructorSet, DeconstructedPat, WitnessPat};
 use crate::errors::{NonExhaustiveOmittedPattern, Uncovered};
 
 use rustc_data_structures::captures::Captures;
@@ -322,7 +322,6 @@ use rustc_span::{Span, DUMMY_SP};
 
 use smallvec::{smallvec, SmallVec};
 use std::fmt;
-use std::iter::once;
 
 pub(crate) struct MatchCheckCtxt<'p, 'tcx> {
     pub(crate) tcx: TyCtxt<'tcx>,
@@ -555,20 +554,20 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
 /// 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)]
-enum Usefulness<'p, 'tcx> {
+#[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<Witness<'p, 'tcx>>),
+    WithWitnesses(Vec<WitnessStack<'tcx>>),
 }
 
-impl<'p, 'tcx> Usefulness<'p, 'tcx> {
+impl<'tcx> Usefulness<'tcx> {
     fn new_useful(preference: ArmType) -> Self {
         match preference {
             // A single (empty) witness of reachability.
-            FakeExtraWildcard => WithWitnesses(vec![Witness(vec![])]),
+            FakeExtraWildcard => WithWitnesses(vec![WitnessStack(vec![])]),
             RealArm => NoWitnesses { useful: true },
         }
     }
@@ -605,8 +604,8 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
     /// with the results of specializing with the other constructors.
     fn apply_constructor(
         self,
-        pcx: &PatCtxt<'_, 'p, 'tcx>,
-        matrix: &Matrix<'p, 'tcx>, // used to compute missing ctors
+        pcx: &PatCtxt<'_, '_, 'tcx>,
+        matrix: &Matrix<'_, 'tcx>, // used to compute missing ctors
         ctor: &Constructor<'tcx>,
     ) -> Self {
         match self {
@@ -627,25 +626,18 @@ impl<'p, 'tcx> Usefulness<'p, 'tcx> {
                     // 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<DeconstructedPat<'_, '_>> = missing
+                    let new_patterns: Vec<WitnessPat<'_>> = missing
                         .into_iter()
-                        .map(|missing_ctor| {
-                            DeconstructedPat::wild_from_ctor(pcx, missing_ctor.clone())
-                        })
+                        .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor.clone()))
                         .collect();
 
                     witnesses
                         .into_iter()
                         .flat_map(|witness| {
                             new_patterns.iter().map(move |pat| {
-                                Witness(
-                                    witness
-                                        .0
-                                        .iter()
-                                        .chain(once(pat))
-                                        .map(DeconstructedPat::clone_and_forget_reachability)
-                                        .collect(),
-                                )
+                                let mut stack = witness.clone();
+                                stack.0.push(pat.clone());
+                                stack
                             })
                         })
                         .collect()
@@ -667,15 +659,17 @@ enum ArmType {
     RealArm,
 }
 
-/// A witness 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.
+/// 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.
+///
+/// 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
 ///
-/// A witness against a list of patterns should have the same types
-/// and length as the pattern matched against. Because Rust `match`
-/// is always against a single pattern, at the end the witness will
-/// have length 1, but in the middle of the algorithm, it can contain
+/// 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.
 ///
 /// For example, if we are constructing a witness for the match against
@@ -690,23 +684,37 @@ enum ArmType {
 /// # }
 /// ```
 ///
-/// We'll perform the following steps:
-/// 1. Start with an empty witness
-///     `Witness(vec![])`
-/// 2. Push a witness `true` against the `false`
-///     `Witness(vec![true])`
-/// 3. Push a witness `Some(_)` against the `None`
-///     `Witness(vec![true, Some(_)])`
-/// 4. Apply the `Pair` constructor to the witnesses
-///     `Witness(vec![Pair(Some(_), true)])`
+/// We'll perform the following steps (among others):
+/// - Start with a matrix representing the match
+///     `PatStack(vec![Pair(None, _)])`
+///     `PatStack(vec![Pair(_, false)])`
+/// - Specialize with `Pair`
+///     `PatStack(vec![None, _])`
+///     `PatStack(vec![_, false])`
+/// - Specialize with `Some`
+///     `PatStack(vec![_, false])`
+/// - Specialize with `_`
+///     `PatStack(vec![false])`
+/// - Specialize with `true`
+///     // no patstacks left
+/// - This is a non-exhaustive match: we have the empty witness stack as a witness.
+///     `WitnessStack(vec![])`
+/// - Apply `true`
+///     `WitnessStack(vec![true])`
+/// - Apply `_`
+///     `WitnessStack(vec![true, _])`
+/// - Apply `Some`
+///     `WitnessStack(vec![true, Some(_)])`
+/// - Apply `Pair`
+///     `WitnessStack(vec![Pair(Some(_), true)])`
 ///
 /// The final `Pair(Some(_), true)` is then the resulting witness.
-#[derive(Debug)]
-pub(crate) struct Witness<'p, 'tcx>(Vec<DeconstructedPat<'p, 'tcx>>);
+#[derive(Debug, Clone)]
+pub(crate) struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>);
 
-impl<'p, 'tcx> Witness<'p, 'tcx> {
+impl<'tcx> WitnessStack<'tcx> {
     /// Asserts that the witness contains a single pattern, and returns it.
-    fn single_pattern(self) -> DeconstructedPat<'p, 'tcx> {
+    fn single_pattern(self) -> WitnessPat<'tcx> {
         assert_eq!(self.0.len(), 1);
         self.0.into_iter().next().unwrap()
     }
@@ -724,13 +732,12 @@ impl<'p, 'tcx> Witness<'p, 'tcx> {
     ///
     /// 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<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Self {
+    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 pats = self.0.drain((len - arity)..).rev();
-            let fields = Fields::from_iter(pcx.cx, pats);
-            DeconstructedPat::new(ctor.clone(), fields, pcx.ty, pcx.span)
+            let fields = self.0.drain((len - arity)..).rev().collect();
+            WitnessPat::new(ctor.clone(), fields, pcx.ty)
         };
 
         self.0.push(pat);
@@ -770,7 +777,7 @@ fn is_useful<'p, 'tcx>(
     lint_root: HirId,
     is_under_guard: bool,
     is_top_level: bool,
-) -> Usefulness<'p, 'tcx> {
+) -> Usefulness<'tcx> {
     debug!(?matrix, ?v);
     let Matrix { patterns: rows, .. } = matrix;
 
@@ -885,7 +892,7 @@ fn is_useful<'p, 'tcx>(
                     // Because of how we computed `nonexhaustive_enum_missing_visible_variants`,
                     // this will not return an empty `Vec`.
                     .filter(|c| !(matches!(c, Constructor::NonExhaustive | Constructor::Hidden)))
-                    .map(|missing_ctor| DeconstructedPat::wild_from_ctor(pcx, missing_ctor))
+                    .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor))
                     .collect::<Vec<_>>();
 
                 // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
@@ -940,7 +947,7 @@ pub(crate) struct UsefulnessReport<'p, 'tcx> {
     pub(crate) arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Reachability)>,
     /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
     /// exhaustiveness.
-    pub(crate) non_exhaustiveness_witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
+    pub(crate) non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>,
 }
 
 /// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which