Rollup merge of #144171 - Nadrieril:exhaustive-witnesses, r=davidtwco

pattern_analysis: add option to get a full set of witnesses

This adds an option to the rustc_pattern_analysis machinery to have it report a complete set of patterns when a match is non-exhaustive (by default we only guarantee to report _some_ missing patterns). This is for use in rust-analyzer.

Leaving as draft until I'm sure this is what r-a needs.

r? ghost

7 files changed, 161 insertions, 21 deletions

diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index 09685640e50..9a9e0db964c 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -950,9 +950,7 @@ impl<Cx: PatCx> Constructor<Cx> {
                 }
             }
             Never => write!(f, "!")?,
-            Wildcard | Missing | NonExhaustive | Hidden | PrivateUninhabited => {
-                write!(f, "_ : {:?}", ty)?
-            }
+            Wildcard | Missing | NonExhaustive | Hidden | PrivateUninhabited => write!(f, "_")?,
         }
         Ok(())
     }
diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs
index 66df35f9ee4..d9bb93a829b 100644
--- a/compiler/rustc_pattern_analysis/src/lib.rs
+++ b/compiler/rustc_pattern_analysis/src/lib.rs
@@ -57,6 +57,13 @@ pub trait PatCx: Sized + fmt::Debug {
 
     fn is_exhaustive_patterns_feature_on(&self) -> bool;
 
+    /// Whether to ensure the non-exhaustiveness witnesses we report for a complete set. This is
+    /// `false` by default to avoid some exponential blowup cases such as
+    /// <https://github.com/rust-lang/rust/issues/118437>.
+    fn exhaustive_witnesses(&self) -> bool {
+        false
+    }
+
     /// The number of fields for this constructor.
     fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize;
 
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index b1c646e9884..19446a1efe9 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -994,7 +994,8 @@ impl<Cx: PatCx> PlaceInfo<Cx> {
         if !missing_ctors.is_empty() && !report_individual_missing_ctors {
             // Report `_` as missing.
             missing_ctors = vec![Constructor::Wildcard];
-        } else if missing_ctors.iter().any(|c| c.is_non_exhaustive()) {
+        } else if missing_ctors.iter().any(|c| c.is_non_exhaustive()) && !cx.exhaustive_witnesses()
+        {
             // 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.
@@ -1747,7 +1748,9 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>(
         // `ctor` is *irrelevant* if there's another constructor in `split_ctors` that matches
         // strictly fewer rows. In that case we can sometimes skip it. See the top of the file for
         // details.
-        let ctor_is_relevant = matches!(ctor, Constructor::Missing) || missing_ctors.is_empty();
+        let ctor_is_relevant = matches!(ctor, Constructor::Missing)
+            || missing_ctors.is_empty()
+            || mcx.tycx.exhaustive_witnesses();
         let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor, ctor_is_relevant)?;
         let mut witnesses = ensure_sufficient_stack(|| {
             compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix)
diff --git a/compiler/rustc_pattern_analysis/tests/common/mod.rs b/compiler/rustc_pattern_analysis/tests/common/mod.rs
index 0b939ef7816..94f2a127b9b 100644
--- a/compiler/rustc_pattern_analysis/tests/common/mod.rs
+++ b/compiler/rustc_pattern_analysis/tests/common/mod.rs
@@ -1,3 +1,4 @@
+#![allow(dead_code, unreachable_pub)]
 use rustc_pattern_analysis::constructor::{
     Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, RangeEnd, VariantVisibility,
 };
@@ -22,8 +23,10 @@ fn init_tracing() {
         .try_init();
 }
 
+pub(super) const UNIT: Ty = Ty::Tuple(&[]);
+pub(super) const NEVER: Ty = Ty::Enum(&[]);
+
 /// A simple set of types.
-#[allow(dead_code)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub(super) enum Ty {
     /// Booleans
@@ -38,6 +41,8 @@ pub(super) enum Ty {
     BigStruct { arity: usize, ty: &'static Ty },
     /// A enum with `arity` variants of type `ty`.
     BigEnum { arity: usize, ty: &'static Ty },
+    /// Like `Enum` but non-exhaustive.
+    NonExhaustiveEnum(&'static [Ty]),
 }
 
 /// The important logic.
@@ -47,7 +52,7 @@ impl Ty {
         match (ctor, *self) {
             (Struct, Ty::Tuple(tys)) => tys.iter().copied().collect(),
             (Struct, Ty::BigStruct { arity, ty }) => (0..arity).map(|_| *ty).collect(),
-            (Variant(i), Ty::Enum(tys)) => vec![tys[*i]],
+            (Variant(i), Ty::Enum(tys) | Ty::NonExhaustiveEnum(tys)) => vec![tys[*i]],
             (Variant(_), Ty::BigEnum { ty, .. }) => vec![*ty],
             (Bool(..) | IntRange(..) | NonExhaustive | Missing | Wildcard, _) => vec![],
             _ => panic!("Unexpected ctor {ctor:?} for type {self:?}"),
@@ -61,6 +66,7 @@ impl Ty {
             Ty::Enum(tys) => tys.iter().all(|ty| ty.is_empty()),
             Ty::BigStruct { arity, ty } => arity != 0 && ty.is_empty(),
             Ty::BigEnum { arity, ty } => arity == 0 || ty.is_empty(),
+            Ty::NonExhaustiveEnum(..) => false,
         }
     }
 
@@ -90,6 +96,19 @@ impl Ty {
                     .collect(),
                 non_exhaustive: false,
             },
+            Ty::NonExhaustiveEnum(tys) => ConstructorSet::Variants {
+                variants: tys
+                    .iter()
+                    .map(|ty| {
+                        if ty.is_empty() {
+                            VariantVisibility::Empty
+                        } else {
+                            VariantVisibility::Visible
+                        }
+                    })
+                    .collect(),
+                non_exhaustive: true,
+            },
             Ty::BigEnum { arity: 0, .. } => ConstructorSet::NoConstructors,
             Ty::BigEnum { arity, ty } => {
                 let vis = if ty.is_empty() {
@@ -113,7 +132,9 @@ impl Ty {
         match (*self, ctor) {
             (Ty::Tuple(..), _) => Ok(()),
             (Ty::BigStruct { .. }, _) => write!(f, "BigStruct"),
-            (Ty::Enum(..), Constructor::Variant(i)) => write!(f, "Enum::Variant{i}"),
+            (Ty::Enum(..) | Ty::NonExhaustiveEnum(..), Constructor::Variant(i)) => {
+                write!(f, "Enum::Variant{i}")
+            }
             (Ty::BigEnum { .. }, Constructor::Variant(i)) => write!(f, "BigEnum::Variant{i}"),
             _ => write!(f, "{:?}::{:?}", self, ctor),
         }
@@ -126,10 +147,11 @@ pub(super) fn compute_match_usefulness<'p>(
     ty: Ty,
     scrut_validity: PlaceValidity,
     complexity_limit: usize,
+    exhaustive_witnesses: bool,
 ) -> Result<UsefulnessReport<'p, Cx>, ()> {
     init_tracing();
     rustc_pattern_analysis::usefulness::compute_match_usefulness(
-        &Cx,
+        &Cx { exhaustive_witnesses },
         arms,
         ty,
         scrut_validity,
@@ -138,7 +160,9 @@ pub(super) fn compute_match_usefulness<'p>(
 }
 
 #[derive(Debug)]
-pub(super) struct Cx;
+pub(super) struct Cx {
+    exhaustive_witnesses: bool,
+}
 
 /// The context for pattern analysis. Forwards anything interesting to `Ty` methods.
 impl PatCx for Cx {
@@ -153,6 +177,10 @@ impl PatCx for Cx {
         false
     }
 
+    fn exhaustive_witnesses(&self) -> bool {
+        self.exhaustive_witnesses
+    }
+
     fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize {
         ty.sub_tys(ctor).len()
     }
@@ -219,16 +247,18 @@ macro_rules! pats {
     // Entrypoint
     // Parse `type; ..`
     ($ty:expr; $($rest:tt)*) => {{
-        #[allow(unused_imports)]
+        #[allow(unused)]
         use rustc_pattern_analysis::{
             constructor::{Constructor, IntRange, MaybeInfiniteInt, RangeEnd},
-            pat::DeconstructedPat,
+            pat::{DeconstructedPat, IndexedPat},
         };
         let ty = $ty;
         // The heart of the macro is designed to push `IndexedPat`s into a `Vec`, so we work around
         // that.
+        #[allow(unused)]
         let sub_tys = ::std::iter::repeat(&ty);
-        let mut vec = Vec::new();
+        #[allow(unused)]
+        let mut vec: Vec<IndexedPat<_>> = Vec::new();
         pats!(@ctor(vec:vec, sub_tys:sub_tys, idx:0) $($rest)*);
         vec.into_iter().map(|ipat| ipat.pat).collect::<Vec<_>>()
     }};
@@ -263,6 +293,8 @@ macro_rules! pats {
         let ctor = Constructor::Wildcard;
         pats!(@pat($($args)*, ctor:ctor) $($rest)*)
     }};
+    // Nothing
+    (@ctor($($args:tt)*)) => {};
 
     // Integers and int ranges
     (@ctor($($args:tt)*) $($start:literal)?..$end:literal $($rest:tt)*) => {{
diff --git a/compiler/rustc_pattern_analysis/tests/complexity.rs b/compiler/rustc_pattern_analysis/tests/complexity.rs
index 93aecafe48d..4754476f383 100644
--- a/compiler/rustc_pattern_analysis/tests/complexity.rs
+++ b/compiler/rustc_pattern_analysis/tests/complexity.rs
@@ -16,7 +16,7 @@ fn check(patterns: &[DeconstructedPat<Cx>], complexity_limit: usize) -> Result<(
     let ty = *patterns[0].ty();
     let arms: Vec<_> =
         patterns.iter().map(|pat| MatchArm { pat, has_guard: false, arm_data: () }).collect();
-    compute_match_usefulness(arms.as_slice(), ty, PlaceValidity::ValidOnly, complexity_limit)
+    compute_match_usefulness(arms.as_slice(), ty, PlaceValidity::ValidOnly, complexity_limit, false)
         .map(|_report| ())
 }
 
diff --git a/compiler/rustc_pattern_analysis/tests/exhaustiveness.rs b/compiler/rustc_pattern_analysis/tests/exhaustiveness.rs
index 3b8f346ef19..14ca0d057f0 100644
--- a/compiler/rustc_pattern_analysis/tests/exhaustiveness.rs
+++ b/compiler/rustc_pattern_analysis/tests/exhaustiveness.rs
@@ -11,16 +11,30 @@ use rustc_pattern_analysis::usefulness::PlaceValidity;
 mod common;
 
 /// Analyze a match made of these patterns.
-fn check(patterns: Vec<DeconstructedPat<Cx>>) -> Vec<WitnessPat<Cx>> {
-    let ty = *patterns[0].ty();
+fn run(
+    ty: Ty,
+    patterns: Vec<DeconstructedPat<Cx>>,
+    exhaustive_witnesses: bool,
+) -> Vec<WitnessPat<Cx>> {
     let arms: Vec<_> =
         patterns.iter().map(|pat| MatchArm { pat, has_guard: false, arm_data: () }).collect();
-    let report =
-        compute_match_usefulness(arms.as_slice(), ty, PlaceValidity::ValidOnly, usize::MAX)
-            .unwrap();
+    let report = compute_match_usefulness(
+        arms.as_slice(),
+        ty,
+        PlaceValidity::ValidOnly,
+        usize::MAX,
+        exhaustive_witnesses,
+    )
+    .unwrap();
     report.non_exhaustiveness_witnesses
 }
 
+/// Analyze a match made of these patterns. Panics if there are no patterns
+fn check(patterns: Vec<DeconstructedPat<Cx>>) -> Vec<WitnessPat<Cx>> {
+    let ty = *patterns[0].ty();
+    run(ty, patterns, true)
+}
+
 #[track_caller]
 fn assert_exhaustive(patterns: Vec<DeconstructedPat<Cx>>) {
     let witnesses = check(patterns);
@@ -35,6 +49,26 @@ fn assert_non_exhaustive(patterns: Vec<DeconstructedPat<Cx>>) {
     assert!(!witnesses.is_empty())
 }
 
+use WhichWitnesses::*;
+enum WhichWitnesses {
+    AllOfThem,
+    OnlySome,
+}
+
+#[track_caller]
+/// We take the type as input to support empty matches.
+fn assert_witnesses(
+    which: WhichWitnesses,
+    ty: Ty,
+    patterns: Vec<DeconstructedPat<Cx>>,
+    expected: Vec<&str>,
+) {
+    let exhaustive_wit = matches!(which, AllOfThem);
+    let witnesses = run(ty, patterns, exhaustive_wit);
+    let witnesses: Vec<_> = witnesses.iter().map(|w| format!("{w:?}")).collect();
+    assert_eq!(witnesses, expected)
+}
+
 #[test]
 fn test_int_ranges() {
     let ty = Ty::U8;
@@ -59,6 +93,8 @@ fn test_int_ranges() {
 
 #[test]
 fn test_nested() {
+    // enum E { A(bool), B(bool) }
+    // ty = (E, E)
     let ty = Ty::BigStruct { arity: 2, ty: &Ty::BigEnum { arity: 2, ty: &Ty::Bool } };
     assert_non_exhaustive(pats!(ty;
         Struct(Variant.0, _),
@@ -79,9 +115,73 @@ fn test_nested() {
 }
 
 #[test]
+fn test_witnesses() {
+    // TY = Option<bool>
+    const TY: Ty = Ty::Enum(&[Ty::Bool, UNIT]);
+    // ty = (Option<bool>, Option<bool>)
+    let ty = Ty::Tuple(&[TY, TY]);
+    assert_witnesses(AllOfThem, ty, vec![], vec!["(_, _)"]);
+    assert_witnesses(
+        OnlySome,
+        ty,
+        pats!(ty;
+            (Variant.0(false), Variant.0(false)),
+        ),
+        vec!["(Enum::Variant1(_), _)"],
+    );
+    assert_witnesses(
+        AllOfThem,
+        ty,
+        pats!(ty;
+            (Variant.0(false), Variant.0(false)),
+        ),
+        vec![
+            "(Enum::Variant0(false), Enum::Variant0(true))",
+            "(Enum::Variant0(false), Enum::Variant1(_))",
+            "(Enum::Variant0(true), _)",
+            "(Enum::Variant1(_), _)",
+        ],
+    );
+    assert_witnesses(
+        OnlySome,
+        ty,
+        pats!(ty;
+            (_, Variant.0(false)),
+        ),
+        vec!["(_, Enum::Variant1(_))"],
+    );
+    assert_witnesses(
+        AllOfThem,
+        ty,
+        pats!(ty;
+            (_, Variant.0(false)),
+        ),
+        vec!["(_, Enum::Variant0(true))", "(_, Enum::Variant1(_))"],
+    );
+
+    let ty = Ty::NonExhaustiveEnum(&[UNIT, UNIT, UNIT]);
+    assert_witnesses(
+        OnlySome,
+        ty,
+        pats!(ty;
+            Variant.0,
+        ),
+        vec!["_"],
+    );
+    assert_witnesses(
+        AllOfThem,
+        ty,
+        pats!(ty;
+            Variant.0,
+        ),
+        vec!["Enum::Variant1(_)", "Enum::Variant2(_)", "_"],
+    );
+}
+
+#[test]
 fn test_empty() {
     // `TY = Result<bool, !>`
-    const TY: Ty = Ty::Enum(&[Ty::Bool, Ty::Enum(&[])]);
+    const TY: Ty = Ty::Enum(&[Ty::Bool, NEVER]);
     assert_exhaustive(pats!(TY;
         Variant.0,
     ));
diff --git a/compiler/rustc_pattern_analysis/tests/intersection.rs b/compiler/rustc_pattern_analysis/tests/intersection.rs
index 8e6f84dcbc8..d4d390517e2 100644
--- a/compiler/rustc_pattern_analysis/tests/intersection.rs
+++ b/compiler/rustc_pattern_analysis/tests/intersection.rs
@@ -16,7 +16,7 @@ fn check(patterns: Vec<DeconstructedPat<Cx>>) -> Vec<Vec<usize>> {
     let arms: Vec<_> =
         patterns.iter().map(|pat| MatchArm { pat, has_guard: false, arm_data: () }).collect();
     let report =
-        compute_match_usefulness(arms.as_slice(), ty, PlaceValidity::ValidOnly, usize::MAX)
+        compute_match_usefulness(arms.as_slice(), ty, PlaceValidity::ValidOnly, usize::MAX, false)
             .unwrap();
     report.arm_intersections.into_iter().map(|bitset| bitset.iter().collect()).collect()
 }