Rollup merge of #66967 - Nadrieril:remove-or-pat-hack, r=varkor

Remove hack for top-level or-patterns in match checking

Follow-up to #66612.

Or-patterns are now truly first-class in match checking. As a side-effect, redundant subpatterns are linted as such, making the `unreachable_patterns` lint a bit more general.

cc #54883

r? @varkor

2 files changed, 158 insertions, 167 deletions

diff --git a/src/librustc_mir/hair/pattern/_match.rs b/src/librustc_mir/hair/pattern/_match.rs
index f2c5bf1bf6d..37a9381271a 100644
--- a/src/librustc_mir/hair/pattern/_match.rs
+++ b/src/librustc_mir/hair/pattern/_match.rs
@@ -425,16 +425,12 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> {
     }
 
     /// This computes `S(constructor, self)`. See top of the file for explanations.
-    fn specialize_constructor<'a, 'q>(
+    fn specialize_constructor(
         &self,
-        cx: &mut MatchCheckCtxt<'a, 'tcx>,
+        cx: &mut MatchCheckCtxt<'p, 'tcx>,
         constructor: &Constructor<'tcx>,
-        ctor_wild_subpatterns: &[&'q Pat<'tcx>],
-    ) -> Option<PatStack<'q, 'tcx>>
-    where
-        'a: 'q,
-        'p: 'q,
-    {
+        ctor_wild_subpatterns: &'p [Pat<'tcx>],
+    ) -> Option<PatStack<'p, 'tcx>> {
         let new_heads = specialize_one_pattern(cx, self.head(), constructor, ctor_wild_subpatterns);
         new_heads.map(|mut new_head| {
             new_head.0.extend_from_slice(&self.0[1..]);
@@ -459,6 +455,7 @@ impl<'p, 'tcx> FromIterator<&'p Pat<'tcx>> for PatStack<'p, 'tcx> {
 }
 
 /// A 2D matrix.
+#[derive(Clone)]
 pub struct Matrix<'p, 'tcx>(Vec<PatStack<'p, 'tcx>>);
 
 impl<'p, 'tcx> Matrix<'p, 'tcx> {
@@ -486,16 +483,12 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
     }
 
     /// This computes `S(constructor, self)`. See top of the file for explanations.
-    fn specialize_constructor<'a, 'q>(
+    fn specialize_constructor(
         &self,
-        cx: &mut MatchCheckCtxt<'a, 'tcx>,
+        cx: &mut MatchCheckCtxt<'p, 'tcx>,
         constructor: &Constructor<'tcx>,
-        ctor_wild_subpatterns: &[&'q Pat<'tcx>],
-    ) -> Matrix<'q, 'tcx>
-    where
-        'a: 'q,
-        'p: 'q,
-    {
+        ctor_wild_subpatterns: &'p [Pat<'tcx>],
+    ) -> Matrix<'p, 'tcx> {
         self.0
             .iter()
             .filter_map(|r| r.specialize_constructor(cx, constructor, ctor_wild_subpatterns))
@@ -1033,17 +1026,19 @@ impl<'tcx> Constructor<'tcx> {
 }
 
 #[derive(Clone, Debug)]
-pub enum Usefulness<'tcx> {
-    Useful,
+pub enum Usefulness<'tcx, 'p> {
+    /// Carries a list of unreachable subpatterns. Used only in the presence of or-patterns.
+    Useful(Vec<&'p Pat<'tcx>>),
+    /// Carries a list of witnesses of non-exhaustiveness.
     UsefulWithWitness(Vec<Witness<'tcx>>),
     NotUseful,
 }
 
-impl<'tcx> Usefulness<'tcx> {
+impl<'tcx, 'p> Usefulness<'tcx, 'p> {
     fn new_useful(preference: WitnessPreference) -> Self {
         match preference {
             ConstructWitness => UsefulWithWitness(vec![Witness(vec![])]),
-            LeaveOutWitness => Useful,
+            LeaveOutWitness => Useful(vec![]),
         }
     }
 
@@ -1604,13 +1599,13 @@ impl<'tcx> fmt::Debug for MissingConstructors<'tcx> {
 /// 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).
-pub fn is_useful<'p, 'a, 'tcx>(
-    cx: &mut MatchCheckCtxt<'a, 'tcx>,
+pub fn is_useful<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
     matrix: &Matrix<'p, 'tcx>,
-    v: &PatStack<'_, 'tcx>,
+    v: &PatStack<'p, 'tcx>,
     witness_preference: WitnessPreference,
     hir_id: HirId,
-) -> Usefulness<'tcx> {
+) -> Usefulness<'tcx, 'p> {
     let &Matrix(ref rows) = matrix;
     debug!("is_useful({:#?}, {:#?})", matrix, v);
 
@@ -1631,11 +1626,26 @@ pub fn is_useful<'p, 'a, 'tcx>(
 
     // If the first pattern is an or-pattern, expand it.
     if let Some(vs) = v.expand_or_pat() {
-        return vs
-            .into_iter()
-            .map(|v| is_useful(cx, matrix, &v, witness_preference, hir_id))
-            .find(|result| result.is_useful())
-            .unwrap_or(NotUseful);
+        // We need to push the already-seen patterns into the matrix in order to detect redundant
+        // branches like `Some(_) | Some(0)`. We also keep track of the unreachable subpatterns.
+        let mut matrix = matrix.clone();
+        let mut unreachable_pats = Vec::new();
+        let mut any_is_useful = false;
+        for v in vs {
+            let res = is_useful(cx, &matrix, &v, witness_preference, hir_id);
+            match res {
+                Useful(pats) => {
+                    any_is_useful = true;
+                    unreachable_pats.extend(pats);
+                }
+                NotUseful => unreachable_pats.push(v.head()),
+                UsefulWithWitness(_) => {
+                    bug!("Encountered or-pat in `v` during exhaustiveness checking")
+                }
+            }
+            matrix.push(v);
+        }
+        return if any_is_useful { Useful(unreachable_pats) } else { NotUseful };
     }
 
     let (ty, span) = matrix
@@ -1768,21 +1778,21 @@ pub fn is_useful<'p, 'a, 'tcx>(
 
 /// A shorthand for the `U(S(c, P), S(c, q))` operation from the paper. I.e., `is_useful` applied
 /// to the specialised version of both the pattern matrix `P` and the new pattern `q`.
-fn is_useful_specialized<'p, 'a, 'tcx>(
-    cx: &mut MatchCheckCtxt<'a, 'tcx>,
+fn is_useful_specialized<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
     matrix: &Matrix<'p, 'tcx>,
-    v: &PatStack<'_, 'tcx>,
+    v: &PatStack<'p, 'tcx>,
     ctor: Constructor<'tcx>,
     lty: Ty<'tcx>,
     witness_preference: WitnessPreference,
     hir_id: HirId,
-) -> Usefulness<'tcx> {
+) -> Usefulness<'tcx, 'p> {
     debug!("is_useful_specialized({:#?}, {:#?}, {:?})", v, ctor, lty);
 
-    let ctor_wild_subpatterns_owned: Vec<_> = ctor.wildcard_subpatterns(cx, lty);
-    let ctor_wild_subpatterns: Vec<_> = ctor_wild_subpatterns_owned.iter().collect();
-    let matrix = matrix.specialize_constructor(cx, &ctor, &ctor_wild_subpatterns);
-    v.specialize_constructor(cx, &ctor, &ctor_wild_subpatterns)
+    let ctor_wild_subpatterns =
+        cx.pattern_arena.alloc_from_iter(ctor.wildcard_subpatterns(cx, lty));
+    let matrix = matrix.specialize_constructor(cx, &ctor, ctor_wild_subpatterns);
+    v.specialize_constructor(cx, &ctor, ctor_wild_subpatterns)
         .map(|v| is_useful(cx, &matrix, &v, witness_preference, hir_id))
         .map(|u| u.apply_constructor(cx, &ctor, lty))
         .unwrap_or(NotUseful)
@@ -2250,13 +2260,13 @@ fn constructor_covered_by_range<'tcx>(
     if intersects { Some(()) } else { None }
 }
 
-fn patterns_for_variant<'p, 'a: 'p, 'tcx>(
-    cx: &mut MatchCheckCtxt<'a, 'tcx>,
+fn patterns_for_variant<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
     subpatterns: &'p [FieldPat<'tcx>],
-    ctor_wild_subpatterns: &[&'p Pat<'tcx>],
+    ctor_wild_subpatterns: &'p [Pat<'tcx>],
     is_non_exhaustive: bool,
 ) -> PatStack<'p, 'tcx> {
-    let mut result = SmallVec::from_slice(ctor_wild_subpatterns);
+    let mut result: SmallVec<_> = ctor_wild_subpatterns.iter().collect();
 
     for subpat in subpatterns {
         if !is_non_exhaustive || !cx.is_uninhabited(subpat.pattern.ty) {
@@ -2280,11 +2290,11 @@ fn patterns_for_variant<'p, 'a: 'p, 'tcx>(
 /// different patterns.
 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
 /// fields filled with wild patterns.
-fn specialize_one_pattern<'p, 'a: 'p, 'q: 'p, 'tcx>(
-    cx: &mut MatchCheckCtxt<'a, 'tcx>,
-    pat: &'q Pat<'tcx>,
+fn specialize_one_pattern<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
+    pat: &'p Pat<'tcx>,
     constructor: &Constructor<'tcx>,
-    ctor_wild_subpatterns: &[&'p Pat<'tcx>],
+    ctor_wild_subpatterns: &'p [Pat<'tcx>],
 ) -> Option<PatStack<'p, 'tcx>> {
     if let NonExhaustive = constructor {
         // Only a wildcard pattern can match the special extra constructor
@@ -2294,9 +2304,7 @@ fn specialize_one_pattern<'p, 'a: 'p, 'q: 'p, 'tcx>(
     let result = match *pat.kind {
         PatKind::AscribeUserType { .. } => bug!(), // Handled by `expand_pattern`
 
-        PatKind::Binding { .. } | PatKind::Wild => {
-            Some(PatStack::from_slice(ctor_wild_subpatterns))
-        }
+        PatKind::Binding { .. } | PatKind::Wild => Some(ctor_wild_subpatterns.iter().collect()),
 
         PatKind::Variant { adt_def, variant_index, ref subpatterns, .. } => {
             let ref variant = adt_def.variants[variant_index];
@@ -2406,7 +2414,6 @@ fn specialize_one_pattern<'p, 'a: 'p, 'q: 'p, 'tcx>(
                                 .chain(
                                     ctor_wild_subpatterns
                                         .iter()
-                                        .map(|p| *p)
                                         .skip(prefix.len())
                                         .take(slice_count)
                                         .chain(suffix.iter()),
diff --git a/src/librustc_mir/hair/pattern/check_match.rs b/src/librustc_mir/hair/pattern/check_match.rs
index 30586e95acf..737af3e1358 100644
--- a/src/librustc_mir/hair/pattern/check_match.rs
+++ b/src/librustc_mir/hair/pattern/check_match.rs
@@ -139,39 +139,22 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
         MatchCheckCtxt::create_and_enter(self.tcx, self.param_env, module, |ref mut cx| {
             let mut have_errors = false;
 
-            let inlined_arms: Vec<(Vec<_>, _)> = arms
+            let inlined_arms: Vec<_> = arms
                 .iter()
                 .map(|arm| {
-                    (
-                        // HACK(or_patterns; Centril | dlrobertson): Remove this and
-                        // correctly handle exhaustiveness checking for nested or-patterns.
-                        match &arm.pat.kind {
-                            hir::PatKind::Or(pats) => pats,
-                            _ => std::slice::from_ref(&arm.pat),
-                        }
-                        .iter()
-                        .map(|pat| {
-                            let mut patcx = PatCtxt::new(
-                                self.tcx,
-                                self.param_env.and(self.identity_substs),
-                                self.tables,
-                            );
-                            patcx.include_lint_checks();
-                            let pattern = cx
-                                .pattern_arena
-                                .alloc(expand_pattern(cx, patcx.lower_pattern(&pat)))
-                                as &_;
-                            if !patcx.errors.is_empty() {
-                                patcx.report_inlining_errors(pat.span);
-                                have_errors = true;
-                            }
-                            (pattern, &**pat)
-                        })
-                        .collect(),
-                        arm.guard.as_ref().map(|g| match g {
-                            hir::Guard::If(ref e) => &**e,
-                        }),
-                    )
+                    let mut patcx = PatCtxt::new(
+                        self.tcx,
+                        self.param_env.and(self.identity_substs),
+                        self.tables,
+                    );
+                    patcx.include_lint_checks();
+                    let pattern: &_ =
+                        cx.pattern_arena.alloc(expand_pattern(cx, patcx.lower_pattern(&arm.pat)));
+                    if !patcx.errors.is_empty() {
+                        patcx.report_inlining_errors(arm.pat.span);
+                        have_errors = true;
+                    }
+                    (pattern, &*arm.pat, arm.guard.is_some())
                 })
                 .collect();
 
@@ -181,7 +164,7 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
             }
 
             // Fourth, check for unreachable arms.
-            check_arms(cx, &inlined_arms, source);
+            let matrix = check_arms(cx, &inlined_arms, source);
 
             // Then, if the match has no arms, check whether the scrutinee
             // is uninhabited.
@@ -248,12 +231,6 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
                 return;
             }
 
-            let matrix: Matrix<'_, '_> = inlined_arms
-                .iter()
-                .filter(|&&(_, guard)| guard.is_none())
-                .flat_map(|arm| &arm.0)
-                .map(|pat| PatStack::from_pattern(pat.0))
-                .collect();
             let scrut_ty = self.tables.node_type(scrut.hir_id);
             check_exhaustive(cx, scrut_ty, scrut.span, &matrix, scrut.hir_id);
         })
@@ -267,8 +244,8 @@ impl<'tcx> MatchVisitor<'_, 'tcx> {
             patcx.include_lint_checks();
             let pattern = patcx.lower_pattern(pat);
             let pattern_ty = pattern.ty;
-            let pattern = expand_pattern(cx, pattern);
-            let pats: Matrix<'_, '_> = vec![PatStack::from_pattern(&pattern)].into_iter().collect();
+            let pattern = cx.pattern_arena.alloc(expand_pattern(cx, pattern));
+            let pats: Matrix<'_, '_> = vec![PatStack::from_pattern(pattern)].into_iter().collect();
 
             let witnesses = match check_not_useful(cx, pattern_ty, &pats, pat.hir_id) {
                 Ok(_) => return,
@@ -403,113 +380,120 @@ fn pat_is_catchall(pat: &Pat) -> bool {
 }
 
 // Check for unreachable patterns
-fn check_arms<'tcx>(
-    cx: &mut MatchCheckCtxt<'_, 'tcx>,
-    arms: &[(Vec<(&super::Pat<'tcx>, &hir::Pat)>, Option<&hir::Expr>)],
+fn check_arms<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
+    arms: &[(&'p super::Pat<'tcx>, &hir::Pat, bool)],
     source: hir::MatchSource,
-) {
+) -> Matrix<'p, 'tcx> {
     let mut seen = Matrix::empty();
     let mut catchall = None;
-    for (arm_index, &(ref pats, guard)) in arms.iter().enumerate() {
-        for &(pat, hir_pat) in pats {
-            let v = PatStack::from_pattern(pat);
-
-            match is_useful(cx, &seen, &v, LeaveOutWitness, hir_pat.hir_id) {
-                NotUseful => {
-                    match source {
-                        hir::MatchSource::IfDesugar { .. } | hir::MatchSource::WhileDesugar => {
-                            bug!()
-                        }
-                        hir::MatchSource::IfLetDesugar { .. } => {
-                            cx.tcx.lint_hir(
-                                lint::builtin::IRREFUTABLE_LET_PATTERNS,
-                                hir_pat.hir_id,
-                                pat.span,
-                                "irrefutable if-let pattern",
-                            );
-                        }
-
-                        hir::MatchSource::WhileLetDesugar => {
-                            // check which arm we're on.
-                            match arm_index {
-                                // The arm with the user-specified pattern.
-                                0 => {
-                                    cx.tcx.lint_hir(
-                                        lint::builtin::UNREACHABLE_PATTERNS,
-                                        hir_pat.hir_id,
-                                        pat.span,
-                                        "unreachable pattern",
-                                    );
-                                }
-                                // The arm with the wildcard pattern.
-                                1 => {
-                                    cx.tcx.lint_hir(
-                                        lint::builtin::IRREFUTABLE_LET_PATTERNS,
-                                        hir_pat.hir_id,
-                                        pat.span,
-                                        "irrefutable while-let pattern",
-                                    );
-                                }
-                                _ => bug!(),
+    for (arm_index, (pat, hir_pat, has_guard)) in arms.iter().enumerate() {
+        let v = PatStack::from_pattern(pat);
+
+        match is_useful(cx, &seen, &v, LeaveOutWitness, hir_pat.hir_id) {
+            NotUseful => {
+                match source {
+                    hir::MatchSource::IfDesugar { .. } | hir::MatchSource::WhileDesugar => bug!(),
+
+                    hir::MatchSource::IfLetDesugar { .. } | hir::MatchSource::WhileLetDesugar => {
+                        // check which arm we're on.
+                        match arm_index {
+                            // The arm with the user-specified pattern.
+                            0 => {
+                                cx.tcx.lint_hir(
+                                    lint::builtin::UNREACHABLE_PATTERNS,
+                                    hir_pat.hir_id,
+                                    pat.span,
+                                    "unreachable pattern",
+                                );
                             }
-                        }
-
-                        hir::MatchSource::ForLoopDesugar | hir::MatchSource::Normal => {
-                            let mut err = cx.tcx.struct_span_lint_hir(
-                                lint::builtin::UNREACHABLE_PATTERNS,
-                                hir_pat.hir_id,
-                                pat.span,
-                                "unreachable pattern",
-                            );
-                            // if we had a catchall pattern, hint at that
-                            if let Some(catchall) = catchall {
-                                err.span_label(pat.span, "unreachable pattern");
-                                err.span_label(catchall, "matches any value");
+                            // The arm with the wildcard pattern.
+                            1 => {
+                                let msg = match source {
+                                    hir::MatchSource::IfLetDesugar { .. } => {
+                                        "irrefutable if-let pattern"
+                                    }
+                                    hir::MatchSource::WhileLetDesugar => {
+                                        "irrefutable while-let pattern"
+                                    }
+                                    _ => bug!(),
+                                };
+                                cx.tcx.lint_hir(
+                                    lint::builtin::IRREFUTABLE_LET_PATTERNS,
+                                    hir_pat.hir_id,
+                                    pat.span,
+                                    msg,
+                                );
                             }
-                            err.emit();
+                            _ => bug!(),
                         }
+                    }
 
-                        // Unreachable patterns in try and await expressions occur when one of
-                        // the arms are an uninhabited type. Which is OK.
-                        hir::MatchSource::AwaitDesugar | hir::MatchSource::TryDesugar => {}
+                    hir::MatchSource::ForLoopDesugar | hir::MatchSource::Normal => {
+                        let mut err = cx.tcx.struct_span_lint_hir(
+                            lint::builtin::UNREACHABLE_PATTERNS,
+                            hir_pat.hir_id,
+                            pat.span,
+                            "unreachable pattern",
+                        );
+                        // if we had a catchall pattern, hint at that
+                        if let Some(catchall) = catchall {
+                            err.span_label(pat.span, "unreachable pattern");
+                            err.span_label(catchall, "matches any value");
+                        }
+                        err.emit();
                     }
+
+                    // Unreachable patterns in try and await expressions occur when one of
+                    // the arms are an uninhabited type. Which is OK.
+                    hir::MatchSource::AwaitDesugar | hir::MatchSource::TryDesugar => {}
                 }
-                Useful => (),
-                UsefulWithWitness(_) => bug!(),
             }
-            if guard.is_none() {
-                seen.push(v);
-                if catchall.is_none() && pat_is_catchall(hir_pat) {
-                    catchall = Some(pat.span);
+            Useful(unreachable_subpatterns) => {
+                for pat in unreachable_subpatterns {
+                    cx.tcx.lint_hir(
+                        lint::builtin::UNREACHABLE_PATTERNS,
+                        hir_pat.hir_id,
+                        pat.span,
+                        "unreachable pattern",
+                    );
                 }
             }
+            UsefulWithWitness(_) => bug!(),
+        }
+        if !has_guard {
+            seen.push(v);
+            if catchall.is_none() && pat_is_catchall(hir_pat) {
+                catchall = Some(pat.span);
+            }
         }
     }
+    seen
 }
 
-fn check_not_useful(
-    cx: &mut MatchCheckCtxt<'_, 'tcx>,
+fn check_not_useful<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
     ty: Ty<'tcx>,
-    matrix: &Matrix<'_, 'tcx>,
+    matrix: &Matrix<'p, 'tcx>,
     hir_id: HirId,
 ) -> Result<(), Vec<super::Pat<'tcx>>> {
-    let wild_pattern = super::Pat::wildcard_from_ty(ty);
-    match is_useful(cx, matrix, &PatStack::from_pattern(&wild_pattern), ConstructWitness, hir_id) {
+    let wild_pattern = cx.pattern_arena.alloc(super::Pat::wildcard_from_ty(ty));
+    match is_useful(cx, matrix, &PatStack::from_pattern(wild_pattern), ConstructWitness, hir_id) {
         NotUseful => Ok(()), // This is good, wildcard pattern isn't reachable.
         UsefulWithWitness(pats) => Err(if pats.is_empty() {
-            vec![wild_pattern]
+            bug!("Exhaustiveness check returned no witnesses")
         } else {
             pats.into_iter().map(|w| w.single_pattern()).collect()
         }),
-        Useful => bug!(),
+        Useful(_) => bug!(),
     }
 }
 
-fn check_exhaustive<'tcx>(
-    cx: &mut MatchCheckCtxt<'_, 'tcx>,
+fn check_exhaustive<'p, 'tcx>(
+    cx: &mut MatchCheckCtxt<'p, 'tcx>,
     scrut_ty: Ty<'tcx>,
     sp: Span,
-    matrix: &Matrix<'_, 'tcx>,
+    matrix: &Matrix<'p, 'tcx>,
     hir_id: HirId,
 ) {
     let witnesses = match check_not_useful(cx, scrut_ty, matrix, hir_id) {