Auto merge of #16879 - Nadrieril:fuel, r=Veykril

Add fuel to match checking

Exhaustiveness checking is NP-hard hence can take extremely long to check some specific matches. This PR makes ehxaustiveness bail after a set number of steps. I chose a bound that takes ~100ms on my machine, which should be more than enough for normal matches.

I'd like someone with less recent hardware to run the test to see if that limit is low enough for them. Also curious if the r-a team thinks this is a good ballpark or if we should go lower/higher. I don't have much data on how complex real-life matches get, but we can definitely go lower than `500 000` steps.

The second commit is a drive-by soundness fix which doesn't matter much today but will matter once `min_exhaustive_patterns` is stabilized.

Fixes https://github.com/rust-lang/rust-analyzer/issues/9528 cc `@matklad`

3 files changed, 42 insertions, 16 deletions

diff --git a/crates/hir-ty/src/diagnostics/expr.rs b/crates/hir-ty/src/diagnostics/expr.rs
index b3128712dc4..20b0da441da 100644
--- a/crates/hir-ty/src/diagnostics/expr.rs
+++ b/crates/hir-ty/src/diagnostics/expr.rs
@@ -11,7 +11,6 @@ use hir_def::{ItemContainerId, Lookup};
 use hir_expand::name;
 use itertools::Itertools;
 use rustc_hash::FxHashSet;
-use rustc_pattern_analysis::usefulness::{compute_match_usefulness, PlaceValidity};
 use syntax::{ast, AstNode};
 use tracing::debug;
 use triomphe::Arc;
@@ -234,13 +233,7 @@ impl ExprValidator {
             return;
         }
 
-        let report = match compute_match_usefulness(
-            &cx,
-            m_arms.as_slice(),
-            scrut_ty.clone(),
-            PlaceValidity::ValidOnly,
-            None,
-        ) {
+        let report = match cx.compute_match_usefulness(m_arms.as_slice(), scrut_ty.clone()) {
             Ok(report) => report,
             Err(()) => return,
         };
@@ -282,13 +275,7 @@ impl ExprValidator {
                 continue;
             }
 
-            let report = match compute_match_usefulness(
-                &cx,
-                &[match_arm],
-                ty.clone(),
-                PlaceValidity::ValidOnly,
-                None,
-            ) {
+            let report = match cx.compute_match_usefulness(&[match_arm], ty.clone()) {
                 Ok(v) => v,
                 Err(e) => {
                     debug!(?e, "match usefulness error");
diff --git a/crates/hir-ty/src/diagnostics/match_check/pat_analysis.rs b/crates/hir-ty/src/diagnostics/match_check/pat_analysis.rs
index 81ce51429c5..f45beb4c92b 100644
--- a/crates/hir-ty/src/diagnostics/match_check/pat_analysis.rs
+++ b/crates/hir-ty/src/diagnostics/match_check/pat_analysis.rs
@@ -8,6 +8,7 @@ use rustc_hash::FxHashMap;
 use rustc_pattern_analysis::{
     constructor::{Constructor, ConstructorSet, VariantVisibility},
     index::IdxContainer,
+    usefulness::{compute_match_usefulness, PlaceValidity, UsefulnessReport},
     Captures, PatCx, PrivateUninhabitedField,
 };
 use smallvec::{smallvec, SmallVec};
@@ -59,6 +60,18 @@ impl<'p> MatchCheckCtx<'p> {
         Self { module, body, db, exhaustive_patterns, min_exhaustive_patterns }
     }
 
+    pub(crate) fn compute_match_usefulness(
+        &self,
+        arms: &[MatchArm<'p>],
+        scrut_ty: Ty,
+    ) -> Result<UsefulnessReport<'p, Self>, ()> {
+        // FIXME: Determine place validity correctly. For now, err on the safe side.
+        let place_validity = PlaceValidity::MaybeInvalid;
+        // Measured to take ~100ms on modern hardware.
+        let complexity_limit = Some(500000);
+        compute_match_usefulness(self, arms, scrut_ty, place_validity, complexity_limit)
+    }
+
     fn is_uninhabited(&self, ty: &Ty) -> bool {
         is_ty_uninhabited_from(ty, self.module, self.db)
     }
@@ -465,7 +478,6 @@ impl<'p> PatCx for MatchCheckCtx<'p> {
     }
 
     fn complexity_exceeded(&self) -> Result<(), Self::Error> {
-        // FIXME(Nadrieril): make use of the complexity counter.
         Err(())
     }
 }
diff --git a/crates/ide-diagnostics/src/handlers/missing_match_arms.rs b/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
index 67daa172b27..045154614f8 100644
--- a/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
+++ b/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
@@ -23,6 +23,7 @@ mod tests {
         },
         DiagnosticsConfig,
     };
+    use test_utils::skip_slow_tests;
 
     #[track_caller]
     fn check_diagnostics_no_bails(ra_fixture: &str) {
@@ -1004,6 +1005,32 @@ fn f() {
         );
     }
 
+    #[test]
+    fn exponential_match() {
+        if skip_slow_tests() {
+            return;
+        }
+        // Constructs a match where match checking takes exponential time. Ensures we bail early.
+        use std::fmt::Write;
+        let struct_arity = 50;
+        let mut code = String::new();
+        write!(code, "struct BigStruct {{").unwrap();
+        for i in 0..struct_arity {
+            write!(code, "  field{i}: bool,").unwrap();
+        }
+        write!(code, "}}").unwrap();
+        write!(code, "fn big_match(s: BigStruct) {{").unwrap();
+        write!(code, "  match s {{").unwrap();
+        for i in 0..struct_arity {
+            write!(code, "    BigStruct {{ field{i}: true, ..}} => {{}},").unwrap();
+            write!(code, "    BigStruct {{ field{i}: false, ..}} => {{}},").unwrap();
+        }
+        write!(code, "    _ => {{}},").unwrap();
+        write!(code, "  }}").unwrap();
+        write!(code, "}}").unwrap();
+        check_diagnostics_no_bails(&code);
+    }
+
     mod rust_unstable {
         use super::*;