Auto merge of #117611 - Nadrieril:linear-pass-take-4, r=cjgillot

Rewrite exhaustiveness in one pass

This is at least my 4th attempt at this in as many years x) Previous attempts were all too complicated or too slow. But we're finally here!

The previous version of the exhaustiveness algorithm computed reachability for each arm then exhaustiveness of the whole match. Since each of these steps does roughly the same things, this rewrites the algorithm to do them all in one go. I also think this makes things much simpler.

I also rewrote the documentation of the algorithm in depth. Hopefully it's up-to-date and easier to follow now. Plz comment if anything's unclear.

r? `@oli-obk` I think you're one of the rare other people to understand the exhaustiveness algorithm?

cc `@varkor` I know you're not active anymore, but if you feel like having a look you might enjoy this :D

Fixes https://github.com/rust-lang/rust/issues/79307

5 files changed, 79 insertions, 68 deletions

diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
index 9e35960bcda..ebbbccc5d58 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.allow.stderr
@@ -1,5 +1,5 @@
 error[E0004]: non-exhaustive patterns: type `usize` is non-empty
-  --> $DIR/pointer-sized-int.rs:54:11
+  --> $DIR/pointer-sized-int.rs:59:11
    |
 LL |     match 7usize {}
    |           ^^^^^^
diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
index d16ec5412db..2949081039a 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.deny.stderr
@@ -9,7 +9,7 @@ LL |     match 0usize {
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `usize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern or an explicit pattern as shown
    |
-LL ~         0 ..= usize::MAX => {},
+LL ~         0..=usize::MAX => {},
 LL +         usize::MAX.. => todo!()
    |
 
@@ -24,12 +24,12 @@ LL |     match 0isize {
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL ~         isize::MIN ..= isize::MAX => {},
+LL ~         isize::MIN..=isize::MAX => {},
 LL +         ..isize::MIN | isize::MAX.. => todo!()
    |
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:25:8
+  --> $DIR/pointer-sized-int.rs:24:8
    |
 LL |     m!(0usize, 0..=usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -43,7 +43,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:27:8
+  --> $DIR/pointer-sized-int.rs:26:8
    |
 LL |     m!(0usize, 0..5 | 5..=usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -57,7 +57,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `usize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:29:8
+  --> $DIR/pointer-sized-int.rs:28:8
    |
 LL |     m!(0usize, 0..usize::MAX | usize::MAX);
    |        ^^^^^^ pattern `usize::MAX..` not covered
@@ -71,7 +71,7 @@ LL |         match $s { $($t)+ => {}, usize::MAX.. => todo!() }
    |                                +++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `(usize::MAX.., _)` not covered
-  --> $DIR/pointer-sized-int.rs:31:8
+  --> $DIR/pointer-sized-int.rs:30:8
    |
 LL |     m!((0usize, true), (0..5, true) | (5..=usize::MAX, true) | (0..=usize::MAX, false));
    |        ^^^^^^^^^^^^^^ pattern `(usize::MAX.., _)` not covered
@@ -85,7 +85,7 @@ LL |         match $s { $($t)+ => {}, (usize::MAX.., _) => todo!() }
    |                                ++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:36:8
+  --> $DIR/pointer-sized-int.rs:39:8
    |
 LL |     m!(0isize, isize::MIN..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
@@ -99,7 +99,7 @@ LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:38:8
+  --> $DIR/pointer-sized-int.rs:41:8
    |
 LL |     m!(0isize, isize::MIN..5 | 5..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
@@ -113,9 +113,9 @@ LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:40:8
+  --> $DIR/pointer-sized-int.rs:43:8
    |
-LL |     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
+LL |     m!(0isize, isize::MIN..=-1 | 0 | 1..=isize::MAX);
    |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
    |
    = note: the matched value is of type `isize`
@@ -126,37 +126,36 @@ help: ensure that all possible cases are being handled by adding a match arm wit
 LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
    |                                ++++++++++++++++++++++++++++++++++++++++
 
-error[E0004]: non-exhaustive patterns: `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
-  --> $DIR/pointer-sized-int.rs:42:8
+error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
+  --> $DIR/pointer-sized-int.rs:45:8
    |
-LL |     m!((0isize, true), (isize::MIN..5, true)
-   |        ^^^^^^^^^^^^^^ patterns `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
+LL |     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
+   |        ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
    |
-   = note: the matched value is of type `(isize, bool)`
+   = note: the matched value is of type `isize`
    = note: `isize` does not have fixed minimum and maximum values, so half-open ranges are necessary to match exhaustively
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL |         match $s { $($t)+ => {}, (..isize::MIN, _) | (isize::MAX.., _) => todo!() }
-   |                                ++++++++++++++++++++++++++++++++++++++++++++++++++
+LL |         match $s { $($t)+ => {}, ..isize::MIN | isize::MAX.. => todo!() }
+   |                                ++++++++++++++++++++++++++++++++++++++++
 
-error[E0004]: non-exhaustive patterns: `..isize::MIN` and `isize::MAX..` not covered
-  --> $DIR/pointer-sized-int.rs:47:11
+error[E0004]: non-exhaustive patterns: `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
+  --> $DIR/pointer-sized-int.rs:48:9
    |
-LL |     match 0isize {
-   |           ^^^^^^ patterns `..isize::MIN` and `isize::MAX..` not covered
+LL |         (0isize, true),
+   |         ^^^^^^^^^^^^^^ patterns `(..isize::MIN, _)` and `(isize::MAX.., _)` not covered
    |
-   = note: the matched value is of type `isize`
+   = note: the matched value is of type `(isize, bool)`
    = note: `isize` does not have fixed minimum and maximum values, so half-open ranges are necessary to match exhaustively
    = help: add `#![feature(precise_pointer_size_matching)]` to the crate attributes to enable precise `isize` matching
 help: ensure that all possible cases are being handled by adding a match arm with a wildcard pattern, a match arm with multiple or-patterns as shown, or multiple match arms
    |
-LL ~         1 ..= isize::MAX => {},
-LL +         ..isize::MIN | isize::MAX.. => todo!()
-   |
+LL |         match $s { $($t)+ => {}, (..isize::MIN, _) | (isize::MAX.., _) => todo!() }
+   |                                ++++++++++++++++++++++++++++++++++++++++++++++++++
 
 error[E0004]: non-exhaustive patterns: type `usize` is non-empty
-  --> $DIR/pointer-sized-int.rs:54:11
+  --> $DIR/pointer-sized-int.rs:59:11
    |
 LL |     match 7usize {}
    |           ^^^^^^
diff --git a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
index 20a3cbe127f..cf137dca5aa 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
+++ b/tests/ui/pattern/usefulness/integer-ranges/pointer-sized-int.rs
@@ -13,15 +13,14 @@ macro_rules! m {
 fn main() {
     match 0usize {
         //[deny]~^ ERROR non-exhaustive patterns
-        0 ..= usize::MAX => {}
+        0..=usize::MAX => {}
     }
 
     match 0isize {
         //[deny]~^ ERROR non-exhaustive patterns
-        isize::MIN ..= isize::MAX => {}
+        isize::MIN..=isize::MAX => {}
     }
 
-    m!(0usize, 0..);
     m!(0usize, 0..=usize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
     m!(0usize, 0..5 | 5..=usize::MAX);
@@ -30,26 +29,32 @@ fn main() {
     //[deny]~^ ERROR non-exhaustive patterns
     m!((0usize, true), (0..5, true) | (5..=usize::MAX, true) | (0..=usize::MAX, false));
     //[deny]~^ ERROR non-exhaustive patterns
+
+    m!(0usize, 0..);
+    m!(0usize, 0..5 | 5..);
+    m!(0usize, ..5 | 5..);
+    m!((0usize, true), (0..5, true) | (5.., true) | (0.., false));
     m!(0usize, 0..=usize::MAX | usize::MAX..);
 
-    m!(0isize, ..0 | 0..);
     m!(0isize, isize::MIN..=isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
     m!(0isize, isize::MIN..5 | 5..=isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
+    m!(0isize, isize::MIN..=-1 | 0 | 1..=isize::MAX);
+    //[deny]~^ ERROR non-exhaustive patterns
     m!(0isize, isize::MIN..isize::MAX | isize::MAX);
     //[deny]~^ ERROR non-exhaustive patterns
-    m!((0isize, true), (isize::MIN..5, true)
-        | (5..=isize::MAX, true) | (isize::MIN..=isize::MAX, false));
-    //[deny]~^^ ERROR non-exhaustive patterns
-    m!(0isize, ..=isize::MIN | isize::MIN..=isize::MAX | isize::MAX..);
+    m!(
+        (0isize, true),
+        (isize::MIN..5, true) | (5..=isize::MAX, true) | (isize::MIN..=isize::MAX, false)
+    );
+    //[deny]~^^^ ERROR non-exhaustive patterns
 
-    match 0isize {
-        //[deny]~^ ERROR non-exhaustive patterns
-        isize::MIN ..= -1 => {}
-        0 => {}
-        1 ..= isize::MAX => {}
-    }
+    m!(0isize, ..0 | 0..);
+    m!(0isize, ..5 | 5..);
+    m!((0isize, true), (..5, true)
+        | (5.., true) | (..0 | 0.., false));
+    m!(0isize, ..=isize::MIN | isize::MIN..=isize::MAX | isize::MAX..);
 
     match 7usize {}
     //~^ ERROR non-exhaustive patterns
diff --git a/tests/ui/pattern/usefulness/integer-ranges/reachability.rs b/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
index fb4d59b0578..247fdd91572 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
+++ b/tests/ui/pattern/usefulness/integer-ranges/reachability.rs
@@ -9,9 +9,10 @@ macro_rules! m {
             $t2 => {}
             _ => {}
         }
-    }
+    };
 }
 
+#[rustfmt::skip]
 fn main() {
     m!(0u8, 42, 41);
     m!(0u8, 42, 42); //~ ERROR unreachable pattern
@@ -85,7 +86,7 @@ fn main() {
     match 'a' {
         '\u{0}'..='\u{D7FF}' => {},
         '\u{E000}'..='\u{10_FFFF}' => {},
-        '\u{D7FF}'..='\u{E000}' => {}, // FIXME should be unreachable
+        '\u{D7FF}'..='\u{E000}' => {}, //~ ERROR unreachable pattern
     }
 
     match (0u8, true) {
diff --git a/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr b/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
index 0ffb0ffd82a..c5b028d2038 100644
--- a/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
+++ b/tests/ui/pattern/usefulness/integer-ranges/reachability.stderr
@@ -1,5 +1,5 @@
 error: unreachable pattern
-  --> $DIR/reachability.rs:17:17
+  --> $DIR/reachability.rs:18:17
    |
 LL |     m!(0u8, 42, 42);
    |                 ^^
@@ -11,127 +11,127 @@ LL | #![deny(unreachable_patterns)]
    |         ^^^^^^^^^^^^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:21:22
+  --> $DIR/reachability.rs:22:22
    |
 LL |     m!(0u8, 20..=30, 20);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:22:22
+  --> $DIR/reachability.rs:23:22
    |
 LL |     m!(0u8, 20..=30, 21);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:23:22
+  --> $DIR/reachability.rs:24:22
    |
 LL |     m!(0u8, 20..=30, 25);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:24:22
+  --> $DIR/reachability.rs:25:22
    |
 LL |     m!(0u8, 20..=30, 29);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:25:22
+  --> $DIR/reachability.rs:26:22
    |
 LL |     m!(0u8, 20..=30, 30);
    |                      ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:28:21
+  --> $DIR/reachability.rs:29:21
    |
 LL |     m!(0u8, 20..30, 20);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:29:21
+  --> $DIR/reachability.rs:30:21
    |
 LL |     m!(0u8, 20..30, 21);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:30:21
+  --> $DIR/reachability.rs:31:21
    |
 LL |     m!(0u8, 20..30, 25);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:31:21
+  --> $DIR/reachability.rs:32:21
    |
 LL |     m!(0u8, 20..30, 29);
    |                     ^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:35:22
+  --> $DIR/reachability.rs:36:22
    |
 LL |     m!(0u8, 20..=30, 20..=30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:36:22
+  --> $DIR/reachability.rs:37:22
    |
 LL |     m!(0u8, 20.. 30, 20.. 30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:37:22
+  --> $DIR/reachability.rs:38:22
    |
 LL |     m!(0u8, 20..=30, 20.. 30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:39:22
+  --> $DIR/reachability.rs:40:22
    |
 LL |     m!(0u8, 20..=30, 21..=30);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:40:22
+  --> $DIR/reachability.rs:41:22
    |
 LL |     m!(0u8, 20..=30, 20..=29);
    |                      ^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:42:24
+  --> $DIR/reachability.rs:43:24
    |
 LL |     m!('a', 'A'..='z', 'a'..='z');
    |                        ^^^^^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:49:9
+  --> $DIR/reachability.rs:50:9
    |
 LL |         5..=8 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:55:9
+  --> $DIR/reachability.rs:56:9
    |
 LL |         5..15 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:62:9
+  --> $DIR/reachability.rs:63:9
    |
 LL |         5..25 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:70:9
+  --> $DIR/reachability.rs:71:9
    |
 LL |         5..25 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:76:9
+  --> $DIR/reachability.rs:77:9
    |
 LL |         5..15 => {},
    |         ^^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:83:9
+  --> $DIR/reachability.rs:84:9
    |
 LL |         _ => {},
    |         - matches any value
@@ -139,16 +139,22 @@ LL |         '\u{D7FF}'..='\u{E000}' => {},
    |         ^^^^^^^^^^^^^^^^^^^^^^^ unreachable pattern
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:104:9
+  --> $DIR/reachability.rs:89:9
+   |
+LL |         '\u{D7FF}'..='\u{E000}' => {},
+   |         ^^^^^^^^^^^^^^^^^^^^^^^
+
+error: unreachable pattern
+  --> $DIR/reachability.rs:105:9
    |
 LL |         &FOO => {}
    |         ^^^^
 
 error: unreachable pattern
-  --> $DIR/reachability.rs:105:9
+  --> $DIR/reachability.rs:106:9
    |
 LL |         BAR => {}
    |         ^^^
 
-error: aborting due to 24 previous errors
+error: aborting due to 25 previous errors