Factor out match usefulness computation in `check_match`

This make `_match` a lot more self-contained

2 files changed, 118 insertions, 78 deletions

diff --git a/compiler/rustc_mir_build/src/thir/pattern/_match.rs b/compiler/rustc_mir_build/src/thir/pattern/_match.rs
index f3fa0ec5fb7..bec9b099e38 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/_match.rs
@@ -364,14 +364,14 @@ impl<'tcx> Pat<'tcx> {
 /// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
 /// works well.
 #[derive(Debug, Clone)]
-crate struct PatStack<'p, 'tcx> {
+struct PatStack<'p, 'tcx> {
     pats: SmallVec<[&'p Pat<'tcx>; 2]>,
     /// Cache for the constructor of the head
     head_ctor: OnceCell<Constructor<'tcx>>,
 }
 
 impl<'p, 'tcx> PatStack<'p, 'tcx> {
-    crate fn from_pattern(pat: &'p Pat<'tcx>) -> Self {
+    fn from_pattern(pat: &'p Pat<'tcx>) -> Self {
         Self::from_vec(smallvec![pat])
     }
 
@@ -455,17 +455,17 @@ impl<'p, 'tcx> FromIterator<&'p Pat<'tcx>> for PatStack<'p, 'tcx> {
 
 /// A 2D matrix.
 #[derive(Clone, PartialEq)]
-crate struct Matrix<'p, 'tcx> {
+struct Matrix<'p, 'tcx> {
     patterns: Vec<PatStack<'p, 'tcx>>,
 }
 
 impl<'p, 'tcx> Matrix<'p, 'tcx> {
-    crate fn empty() -> Self {
+    fn empty() -> Self {
         Matrix { patterns: vec![] }
     }
 
     /// Pushes a new row to the matrix. If the row starts with an or-pattern, this expands it.
-    crate fn push(&mut self, row: PatStack<'p, 'tcx>) {
+    fn push(&mut self, row: PatStack<'p, 'tcx>) {
         if let Some(rows) = row.expand_or_pat() {
             for row in rows {
                 // We recursively expand the or-patterns of the new rows.
@@ -588,7 +588,7 @@ impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
     }
 
     /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
-    crate fn is_foreign_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool {
+    fn is_foreign_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool {
         match ty.kind() {
             ty::Adt(def, ..) => {
                 def.is_enum() && def.is_variant_list_non_exhaustive() && !def.did.is_local()
@@ -1439,7 +1439,7 @@ impl<'tcx> Usefulness<'tcx> {
 }
 
 #[derive(Copy, Clone, Debug)]
-crate enum WitnessPreference {
+enum WitnessPreference {
     ConstructWitness,
     LeaveOutWitness,
 }
@@ -1495,7 +1495,8 @@ struct PatCtxt<'a, 'p, 'tcx> {
 crate struct Witness<'tcx>(Vec<Pat<'tcx>>);
 
 impl<'tcx> Witness<'tcx> {
-    crate fn single_pattern(self) -> Pat<'tcx> {
+    /// Asserts that the witness contains a single pattern, and returns it.
+    fn single_pattern(self) -> Pat<'tcx> {
         assert_eq!(self.0.len(), 1);
         self.0.into_iter().next().unwrap()
     }
@@ -2092,7 +2093,7 @@ impl<'tcx> MissingConstructors<'tcx> {
 /// `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.
-crate fn is_useful<'p, 'tcx>(
+fn is_useful<'p, 'tcx>(
     cx: &MatchCheckCtxt<'p, 'tcx>,
     matrix: &Matrix<'p, 'tcx>,
     v: &PatStack<'p, 'tcx>,
@@ -2289,3 +2290,63 @@ fn pat_constructor<'p, 'tcx>(
         PatKind::Or { .. } => bug!("Or-pattern should have been expanded earlier on."),
     }
 }
+
+/// The arm of a match expression.
+#[derive(Clone, Copy)]
+crate struct MatchArm<'p, 'tcx> {
+    /// The pattern must have been lowered through `MatchVisitor::lower_pattern`.
+    crate pat: &'p super::Pat<'tcx>,
+    crate hir_id: HirId,
+    crate has_guard: bool,
+}
+
+/// The output of checking a match for exhaustiveness and arm reachability.
+crate struct UsefulnessReport<'p, 'tcx> {
+    /// For each arm of the input, whether that arm is reachable after the arms above it.
+    crate arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Usefulness<'tcx>)>,
+    /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
+    /// exhaustiveness.
+    crate non_exhaustiveness_witnesses: Vec<super::Pat<'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 `MatchVisitor::lower_pattern`.
+crate fn compute_match_usefulness<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    arms: &[MatchArm<'p, 'tcx>],
+    scrut_hir_id: HirId,
+    scrut_ty: Ty<'tcx>,
+) -> UsefulnessReport<'p, 'tcx> {
+    let mut matrix = Matrix::empty();
+    let arm_usefulness: Vec<_> = arms
+        .iter()
+        .copied()
+        .map(|arm| {
+            let v = PatStack::from_pattern(arm.pat);
+            let usefulness =
+                is_useful(cx, &matrix, &v, LeaveOutWitness, arm.hir_id, arm.has_guard, true);
+            if !arm.has_guard {
+                matrix.push(v);
+            }
+            (arm, usefulness)
+        })
+        .collect();
+
+    let wild_pattern = cx.pattern_arena.alloc(super::Pat::wildcard_from_ty(scrut_ty));
+    let v = PatStack::from_pattern(wild_pattern);
+    let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, scrut_hir_id, false, true);
+    let non_exhaustiveness_witnesses = match usefulness {
+        NotUseful => vec![], // Wildcard pattern isn't useful, so the match is exhaustive.
+        UsefulWithWitness(pats) => {
+            if pats.is_empty() {
+                bug!("Exhaustiveness check returned no witnesses")
+            } else {
+                pats.into_iter().map(|w| w.single_pattern()).collect()
+            }
+        }
+        Useful(_) => bug!(),
+    };
+    UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
+}
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 4766e7d178d..9a447d9a6ae 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -1,6 +1,7 @@
 use super::_match::Usefulness::*;
-use super::_match::WitnessPreference::*;
-use super::_match::{expand_pattern, is_useful, MatchCheckCtxt, Matrix, PatStack};
+use super::_match::{
+    compute_match_usefulness, expand_pattern, MatchArm, MatchCheckCtxt, UsefulnessReport,
+};
 use super::{PatCtxt, PatKind, PatternError};
 
 use rustc_arena::TypedArena;
@@ -169,39 +170,50 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
 
         let mut have_errors = false;
 
-        let inlined_arms: Vec<_> = arms
+        let arms: Vec<_> = arms
             .iter()
-            .map(|hir::Arm { pat, guard, .. }| {
-                (self.lower_pattern(&mut cx, pat, &mut have_errors).0, pat.hir_id, guard.is_some())
+            .map(|hir::Arm { pat, guard, .. }| MatchArm {
+                pat: self.lower_pattern(&mut cx, pat, &mut have_errors).0,
+                hir_id: pat.hir_id,
+                has_guard: guard.is_some(),
             })
             .collect();
 
-        // Bail out early if inlining failed.
+        // Bail out early if lowering failed.
         if have_errors {
             return;
         }
 
-        // Fourth, check for unreachable arms.
-        let matrix = check_arms(&mut cx, &inlined_arms, source);
+        let scrut_ty = self.typeck_results.expr_ty_adjusted(scrut);
+        let report = compute_match_usefulness(&cx, &arms, scrut.hir_id, scrut_ty);
+
+        // Report unreachable arms.
+        report_arm_reachability(&cx, &report, source);
 
-        // Fifth, check if the match is exhaustive.
+        // Check if the match is exhaustive.
         // Note: An empty match isn't the same as an empty matrix for diagnostics purposes,
         // since an empty matrix can occur when there are arms, if those arms all have guards.
-        let scrut_ty = self.typeck_results.expr_ty_adjusted(scrut);
-        let is_empty_match = inlined_arms.is_empty();
-        check_exhaustive(&mut cx, scrut_ty, scrut.span, &matrix, scrut.hir_id, is_empty_match);
+        let is_empty_match = arms.is_empty();
+        let witnesses = report.non_exhaustiveness_witnesses;
+        if !witnesses.is_empty() {
+            non_exhaustive_match(&cx, scrut_ty, scrut.span, witnesses, is_empty_match);
+        }
     }
 
     fn check_irrefutable(&self, pat: &'tcx Pat<'tcx>, origin: &str, sp: Option<Span>) {
         let mut cx = self.new_cx(pat.hir_id);
 
         let (pattern, pattern_ty) = self.lower_pattern(&mut cx, pat, &mut false);
-        let pats: Matrix<'_, '_> = vec![PatStack::from_pattern(pattern)].into_iter().collect();
-
-        let witnesses = match check_not_useful(&mut cx, pattern_ty, &pats, pat.hir_id) {
-            Ok(_) => return,
-            Err(err) => err,
-        };
+        let arms = vec![MatchArm { pat: pattern, hir_id: pat.hir_id, has_guard: false }];
+        let report = compute_match_usefulness(&cx, &arms, pat.hir_id, pattern_ty);
+
+        // Note: we ignore whether the pattern is unreachable (i.e. whether the type is empty). We
+        // only care about exhaustiveness here.
+        let witnesses = report.non_exhaustiveness_witnesses;
+        if witnesses.is_empty() {
+            // The pattern is irrefutable.
+            return;
+        }
 
         let joined_patterns = joined_uncovered_patterns(&witnesses);
         let mut err = struct_span_err!(
@@ -354,17 +366,15 @@ fn irrefutable_let_pattern(tcx: TyCtxt<'_>, span: Span, id: HirId, source: hir::
     });
 }
 
-/// Check for unreachable patterns.
-fn check_arms<'p, 'tcx>(
-    cx: &mut MatchCheckCtxt<'p, 'tcx>,
-    arms: &[(&'p super::Pat<'tcx>, HirId, bool)],
+/// Report unreachable arms, if any.
+fn report_arm_reachability<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    report: &UsefulnessReport<'p, 'tcx>,
     source: hir::MatchSource,
-) -> Matrix<'p, 'tcx> {
-    let mut seen = Matrix::empty();
+) {
     let mut catchall = None;
-    for (arm_index, (pat, id, has_guard)) in arms.iter().copied().enumerate() {
-        let v = PatStack::from_pattern(pat);
-        match is_useful(cx, &seen, &v, LeaveOutWitness, id, has_guard, true) {
+    for (arm_index, (arm, is_useful)) in report.arm_usefulness.iter().enumerate() {
+        match is_useful {
             NotUseful => {
                 match source {
                     hir::MatchSource::IfDesugar { .. } | hir::MatchSource::WhileDesugar => bug!(),
@@ -373,15 +383,15 @@ fn check_arms<'p, 'tcx>(
                         // Check which arm we're on.
                         match arm_index {
                             // The arm with the user-specified pattern.
-                            0 => unreachable_pattern(cx.tcx, pat.span, id, None),
+                            0 => unreachable_pattern(cx.tcx, arm.pat.span, arm.hir_id, None),
                             // The arm with the wildcard pattern.
-                            1 => irrefutable_let_pattern(cx.tcx, pat.span, id, source),
+                            1 => irrefutable_let_pattern(cx.tcx, arm.pat.span, arm.hir_id, source),
                             _ => bug!(),
                         }
                     }
 
                     hir::MatchSource::ForLoopDesugar | hir::MatchSource::Normal => {
-                        unreachable_pattern(cx.tcx, pat.span, id, catchall);
+                        unreachable_pattern(cx.tcx, arm.pat.span, arm.hir_id, catchall);
                     }
 
                     // Unreachable patterns in try and await expressions occur when one of
@@ -392,60 +402,29 @@ fn check_arms<'p, 'tcx>(
             Useful(unreachables) if unreachables.is_empty() => {}
             // The arm is reachable, but contains unreachable subpatterns (from or-patterns).
             Useful(unreachables) => {
-                let mut unreachables: Vec<_> = unreachables.into_iter().flatten().collect();
+                let mut unreachables: Vec<_> = unreachables.iter().flatten().copied().collect();
                 // Emit lints in the order in which they occur in the file.
                 unreachables.sort_unstable();
                 for span in unreachables {
-                    unreachable_pattern(cx.tcx, span, id, None);
+                    unreachable_pattern(cx.tcx, span, arm.hir_id, None);
                 }
             }
             UsefulWithWitness(_) => bug!(),
         }
-        if !has_guard {
-            seen.push(v);
-            if catchall.is_none() && pat_is_catchall(pat) {
-                catchall = Some(pat.span);
-            }
+        if !arm.has_guard && catchall.is_none() && pat_is_catchall(arm.pat) {
+            catchall = Some(arm.pat.span);
         }
     }
-    seen
 }
 
-fn check_not_useful<'p, 'tcx>(
-    cx: &mut MatchCheckCtxt<'p, 'tcx>,
-    ty: Ty<'tcx>,
-    matrix: &Matrix<'p, 'tcx>,
-    hir_id: HirId,
-) -> Result<(), Vec<super::Pat<'tcx>>> {
-    let wild_pattern = cx.pattern_arena.alloc(super::Pat::wildcard_from_ty(ty));
-    let v = PatStack::from_pattern(wild_pattern);
-
-    // false is given for `is_under_guard` argument due to the wildcard
-    // pattern not having a guard
-    match is_useful(cx, matrix, &v, ConstructWitness, hir_id, false, true) {
-        NotUseful => Ok(()), // This is good, wildcard pattern isn't reachable.
-        UsefulWithWitness(pats) => Err(if pats.is_empty() {
-            bug!("Exhaustiveness check returned no witnesses")
-        } else {
-            pats.into_iter().map(|w| w.single_pattern()).collect()
-        }),
-        Useful(_) => bug!(),
-    }
-}
-
-fn check_exhaustive<'p, 'tcx>(
-    cx: &mut MatchCheckCtxt<'p, 'tcx>,
+/// Report that a match is not exhaustive.
+fn non_exhaustive_match<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
     scrut_ty: Ty<'tcx>,
     sp: Span,
-    matrix: &Matrix<'p, 'tcx>,
-    hir_id: HirId,
+    witnesses: Vec<super::Pat<'tcx>>,
     is_empty_match: bool,
 ) {
-    let witnesses = match check_not_useful(cx, scrut_ty, matrix, hir_id) {
-        Ok(_) => return,
-        Err(err) => err,
-    };
-
     let non_empty_enum = match scrut_ty.kind() {
         ty::Adt(def, _) => def.is_enum() && !def.variants.is_empty(),
         _ => false,