Lint `non_exhaustive_omitted_patterns` per column

3 files changed, 128 insertions, 78 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 f3568b682a4..162b6fde552 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs
@@ -269,7 +269,7 @@ impl<'p, 'tcx> MatchVisitor<'_, 'p, 'tcx> {
 
         let scrut = &self.thir[scrut];
         let scrut_ty = scrut.ty;
-        let report = compute_match_usefulness(&cx, &tarms, self.lint_level, scrut_ty);
+        let report = compute_match_usefulness(&cx, &tarms, self.lint_level, scrut_ty, scrut.span);
 
         match source {
             // Don't report arm reachability of desugared `match $iter.into_iter() { iter => .. }`
@@ -431,7 +431,8 @@ impl<'p, 'tcx> MatchVisitor<'_, 'p, 'tcx> {
         let pattern = self.lower_pattern(&mut cx, pat);
         let pattern_ty = pattern.ty();
         let arm = MatchArm { pat: pattern, hir_id: self.lint_level, has_guard: false };
-        let report = compute_match_usefulness(&cx, &[arm], self.lint_level, pattern_ty);
+        let report =
+            compute_match_usefulness(&cx, &[arm], self.lint_level, pattern_ty, pattern.span());
 
         // Note: we ignore whether the pattern is unreachable (i.e. whether the type is empty). We
         // only care about exhaustiveness here.
@@ -622,7 +623,7 @@ fn is_let_irrefutable<'p, 'tcx>(
     pat: &'p DeconstructedPat<'p, 'tcx>,
 ) -> bool {
     let arms = [MatchArm { pat, hir_id: pat_id, has_guard: false }];
-    let report = compute_match_usefulness(&cx, &arms, pat_id, pat.ty());
+    let report = compute_match_usefulness(&cx, &arms, pat_id, pat.ty(), pat.span());
 
     // Report if the pattern is unreachable, which can only occur when the type is uninhabited.
     // This also reports unreachable sub-patterns though, so we can't just replace it with an
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 818a8ff27c8..359e5333fb9 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs
@@ -629,18 +629,11 @@ pub(super) enum Constructor<'tcx> {
     /// `#[doc(hidden)]` ones.
     Hidden,
     /// Fake extra constructor for constructors that are not seen in the matrix, as explained in the
-    /// code for [`Constructor::split`]. The carried `bool` is used for the
-    /// `non_exhaustive_omitted_patterns` lint.
-    Missing {
-        nonexhaustive_enum_missing_visible_variants: bool,
-    },
+    /// code for [`Constructor::split`].
+    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)
     }
@@ -778,14 +771,8 @@ impl<'tcx> Constructor<'tcx> {
                     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 {
-                            nonexhaustive_enum_missing_visible_variants: split_set
-                                .nonexhaustive_enum_missing_visible_variants,
-                        }
-                    };
+                    let ctor =
+                        if all_missing && !report_when_all_missing { Wildcard } else { Missing };
                     smallvec![ctor]
                 } else {
                     split_set.present
@@ -905,11 +892,9 @@ pub(super) enum ConstructorSet {
 ///     either fully included in or disjoint from each constructor in the column. This avoids
 ///     non-trivial intersections like between `0..10` and `5..15`.
 #[derive(Debug)]
-struct SplitConstructorSet<'tcx> {
-    present: SmallVec<[Constructor<'tcx>; 1]>,
-    missing: Vec<Constructor<'tcx>>,
-    /// For the `non_exhaustive_omitted_patterns` lint.
-    nonexhaustive_enum_missing_visible_variants: bool,
+pub(super) struct SplitConstructorSet<'tcx> {
+    pub(super) present: SmallVec<[Constructor<'tcx>; 1]>,
+    pub(super) missing: Vec<Constructor<'tcx>>,
 }
 
 impl ConstructorSet {
@@ -1039,7 +1024,7 @@ impl ConstructorSet {
     /// 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.
     #[instrument(level = "debug", skip(self, pcx, ctors), ret)]
-    fn split<'a, 'tcx>(
+    pub(super) fn split<'a, 'tcx>(
         &self,
         pcx: &PatCtxt<'_, '_, 'tcx>,
         ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
@@ -1051,7 +1036,6 @@ impl ConstructorSet {
         let mut missing = Vec::new();
         // Constructors in `ctors`, except wildcards.
         let mut seen = ctors.filter(|c| !(matches!(c, Opaque | Wildcard)));
-        let mut nonexhaustive_enum_missing_visible_variants = false;
         match self {
             ConstructorSet::Single => {
                 if seen.next().is_none() {
@@ -1063,6 +1047,7 @@ impl ConstructorSet {
             ConstructorSet::Variants { visible_variants, hidden_variants, non_exhaustive } => {
                 let seen_set: FxHashSet<_> = seen.map(|c| c.as_variant().unwrap()).collect();
                 let mut skipped_a_hidden_variant = false;
+
                 for variant in visible_variants {
                     let ctor = Variant(*variant);
                     if seen_set.contains(&variant) {
@@ -1071,8 +1056,6 @@ impl ConstructorSet {
                         missing.push(ctor);
                     }
                 }
-                nonexhaustive_enum_missing_visible_variants =
-                    *non_exhaustive && !missing.is_empty();
 
                 for variant in hidden_variants {
                     let ctor = Variant(*variant);
@@ -1159,7 +1142,7 @@ impl ConstructorSet {
             ConstructorSet::Uninhabited => {}
         }
 
-        SplitConstructorSet { present, missing, nonexhaustive_enum_missing_visible_variants }
+        SplitConstructorSet { present, missing }
     }
 
     /// Compute the set of constructors missing from this column.
@@ -1519,6 +1502,13 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
     pub(super) fn is_or_pat(&self) -> bool {
         matches!(self.ctor, Or)
     }
+    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()
+        } else {
+            smallvec![self]
+        }
+    }
 
     pub(super) fn ctor(&self) -> &Constructor<'tcx> {
         &self.ctor
@@ -1704,7 +1694,7 @@ impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> {
 #[derive(Debug, Clone)]
 pub(crate) struct WitnessPat<'tcx> {
     ctor: Constructor<'tcx>,
-    fields: Vec<WitnessPat<'tcx>>,
+    pub(crate) fields: Vec<WitnessPat<'tcx>>,
     ty: Ty<'tcx>,
 }
 
diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
index e60349be3ba..a8cee5a61ed 100644
--- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+++ b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
@@ -844,8 +844,6 @@ fn is_useful<'p, 'tcx>(
         }
         // We split the head constructor of `v`.
         let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
-        let is_non_exhaustive_and_wild =
-            cx.is_foreign_non_exhaustive_enum(ty) && v_ctor.is_wildcard();
         // For each constructor, we compute whether there's a value that starts with it that would
         // witness the usefulness of `v`.
         let start_matrix = &matrix;
@@ -866,50 +864,6 @@ fn is_useful<'p, 'tcx>(
                 )
             });
             let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor);
-
-            // When all the conditions are met we have a match with a `non_exhaustive` enum
-            // that has the potential to trigger the `non_exhaustive_omitted_patterns` lint.
-            // To understand the workings checkout `Constructor::split` and `SplitWildcard::new/into_ctors`
-            if is_non_exhaustive_and_wild
-                // Only emit a lint on refutable patterns.
-                && cx.refutable
-                // We check that the match has a wildcard pattern and that wildcard is useful,
-                // meaning there are variants that are covered by the wildcard. Without the check
-                // for `witness_preference` the lint would trigger on `if let NonExhaustiveEnum::A = foo {}`
-                && usefulness.is_useful() && matches!(witness_preference, RealArm)
-                && matches!(
-                    &ctor,
-                    Constructor::Missing { nonexhaustive_enum_missing_visible_variants: true }
-                )
-            {
-                let missing = ConstructorSet::for_ty(pcx.cx, pcx.ty)
-                    .compute_missing(pcx, matrix.heads().map(DeconstructedPat::ctor));
-                // Construct for each missing constructor a "wild" version of this constructor, that
-                // matches everything that can be built with it. For example, if `ctor` is a
-                // `Constructor::Variant` for `Option::Some`, we get the pattern `Some(_)`.
-                let patterns = missing
-                    .into_iter()
-                    // 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| WitnessPat::wild_from_ctor(pcx, missing_ctor))
-                    .collect::<Vec<_>>();
-
-                // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
-                // is not exhaustive enough.
-                //
-                // 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,
-                    pcx.span,
-                    NonExhaustiveOmittedPattern {
-                        scrut_ty: pcx.ty,
-                        uncovered: Uncovered::new(pcx.span, pcx.cx, patterns),
-                    },
-                );
-            }
-
             ret.extend(usefulness);
         }
     }
@@ -921,6 +875,80 @@ fn is_useful<'p, 'tcx>(
     ret
 }
 
+/// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned
+/// in a given column. This traverses patterns column-by-column, where a column is the intuitive
+/// notion of "subpatterns that inspect the same subvalue".
+/// Despite similarities with `is_useful`, this traversal is different. Notably this is linear in the
+/// depth of patterns, whereas `is_useful` is worst-case exponential (exhaustiveness is NP-complete).
+fn collect_nonexhaustive_missing_variants<'p, 'tcx>(
+    cx: &MatchCheckCtxt<'p, 'tcx>,
+    column: &[&DeconstructedPat<'p, 'tcx>],
+) -> Vec<WitnessPat<'tcx>> {
+    let ty = column[0].ty();
+    let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false };
+
+    let set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, column.iter().map(|p| p.ctor()));
+    if set.present.is_empty() {
+        // We can't consistently handle the case where no constructors are present (since this would
+        // require digging deep through any type in case there's a non_exhaustive enum somewhere),
+        // so for consistency we refuse to handle the top-level case, where we could handle it.
+        return vec![];
+    }
+
+    let mut witnesses = Vec::new();
+    if cx.is_foreign_non_exhaustive_enum(ty) {
+        witnesses.extend(
+            set.missing
+                .into_iter()
+                // This will list missing visible variants.
+                .filter(|c| !matches!(c, Constructor::Hidden | Constructor::NonExhaustive))
+                .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor)),
+        )
+    }
+
+    // Recurse into the fields.
+    for ctor in set.present {
+        let arity = ctor.arity(pcx);
+        if arity == 0 {
+            continue;
+        }
+
+        // We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These
+        // columns may have different lengths in the presence of or-patterns (this is why we can't
+        // reuse `Matrix`).
+        let mut specialized_columns: Vec<Vec<_>> = (0..arity).map(|_| Vec::new()).collect();
+        let relevant_patterns = column.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor()));
+        for pat in relevant_patterns {
+            let specialized = pat.specialize(pcx, &ctor);
+            for (subpat, sub_column) in specialized.iter().zip(&mut specialized_columns) {
+                if subpat.is_or_pat() {
+                    sub_column.extend(subpat.iter_fields())
+                } else {
+                    sub_column.push(subpat)
+                }
+            }
+        }
+        debug_assert!(
+            !specialized_columns[0].is_empty(),
+            "ctor {ctor:?} was listed as present but isn't"
+        );
+
+        let wild_pat = WitnessPat::wild_from_ctor(pcx, ctor);
+        for (i, col_i) in specialized_columns.iter().enumerate() {
+            // Compute witnesses for each column.
+            let wits_for_col_i = collect_nonexhaustive_missing_variants(cx, col_i.as_slice());
+            // For each witness, we build a new pattern in the shape of `ctor(_, _, wit, _, _)`,
+            // adding enough wildcards to match `arity`.
+            for wit in wits_for_col_i {
+                let mut pat = wild_pat.clone();
+                pat.fields[i] = wit;
+                witnesses.push(pat);
+            }
+        }
+    }
+    witnesses
+}
+
 /// The arm of a match expression.
 #[derive(Clone, Copy, Debug)]
 pub(crate) struct MatchArm<'p, 'tcx> {
@@ -961,6 +989,7 @@ pub(crate) fn compute_match_usefulness<'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 arm_usefulness: Vec<_> = arms
@@ -985,9 +1014,39 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
     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 = match usefulness {
+    let non_exhaustiveness_witnesses: Vec<_> = match usefulness {
         WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(),
         NoWitnesses { .. } => bug!(),
     };
+
+    // 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()
+        && !matches!(
+            cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, lint_root).0,
+            rustc_session::lint::Level::Allow
+        )
+    {
+        let pat_column = arms.iter().flat_map(|arm| arm.pat.flatten_or_pat()).collect::<Vec<_>>();
+        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.
+            //
+            // 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,
+                NonExhaustiveOmittedPattern {
+                    scrut_ty,
+                    uncovered: Uncovered::new(scrut_span, cx, witnesses),
+                },
+            );
+        }
+    }
+
     UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
 }