Auto merge of #123332 - Nadrieril:testkind-never, r=matthewjasper

never patterns: lower never patterns to `Unreachable` in MIR

This lowers a `!` pattern to "goto Unreachable". Ideally I'd like to read from the place to make it clear that the UB is coming from an invalid value, but that's tricky so I'm leaving it for later.

r? `@compiler-errors` how do you feel about a lil bit of MIR lowering

16 files changed, 315 insertions, 21 deletions

diff --git a/compiler/rustc_ast_lowering/src/expr.rs b/compiler/rustc_ast_lowering/src/expr.rs
index 5cc05d7336e..443b596b917 100644
--- a/compiler/rustc_ast_lowering/src/expr.rs
+++ b/compiler/rustc_ast_lowering/src/expr.rs
@@ -581,8 +581,8 @@ impl<'hir> LoweringContext<'_, 'hir> {
                 self.dcx().emit_err(NeverPatternWithGuard { span: g.span });
             }
 
-            // We add a fake `loop {}` arm body so that it typecks to `!`.
-            // FIXME(never_patterns): Desugar into a call to `unreachable_unchecked`.
+            // We add a fake `loop {}` arm body so that it typecks to `!`. The mir lowering of never
+            // patterns ensures this loop is not reachable.
             let block = self.arena.alloc(hir::Block {
                 stmts: &[],
                 expr: None,
diff --git a/compiler/rustc_middle/src/thir.rs b/compiler/rustc_middle/src/thir.rs
index a7d8ead5677..c68b7a6c9eb 100644
--- a/compiler/rustc_middle/src/thir.rs
+++ b/compiler/rustc_middle/src/thir.rs
@@ -682,6 +682,23 @@ impl<'tcx> Pat<'tcx> {
             true
         })
     }
+
+    /// Whether this a never pattern.
+    pub fn is_never_pattern(&self) -> bool {
+        let mut is_never_pattern = false;
+        self.walk(|pat| match &pat.kind {
+            PatKind::Never => {
+                is_never_pattern = true;
+                false
+            }
+            PatKind::Or { pats } => {
+                is_never_pattern = pats.iter().all(|p| p.is_never_pattern());
+                false
+            }
+            _ => true,
+        });
+        is_never_pattern
+    }
 }
 
 impl<'tcx> IntoDiagArg for Pat<'tcx> {
diff --git a/compiler/rustc_mir_build/src/build/matches/mod.rs b/compiler/rustc_mir_build/src/build/matches/mod.rs
index bce15267759..30ebe7d547e 100644
--- a/compiler/rustc_mir_build/src/build/matches/mod.rs
+++ b/compiler/rustc_mir_build/src/build/matches/mod.rs
@@ -1016,6 +1016,9 @@ struct PatternExtraData<'tcx> {
 
     /// Types that must be asserted.
     ascriptions: Vec<Ascription<'tcx>>,
+
+    /// Whether this corresponds to a never pattern.
+    is_never: bool,
 }
 
 impl<'tcx> PatternExtraData<'tcx> {
@@ -1041,12 +1044,14 @@ impl<'tcx, 'pat> FlatPat<'pat, 'tcx> {
         pattern: &'pat Pat<'tcx>,
         cx: &mut Builder<'_, 'tcx>,
     ) -> Self {
+        let is_never = pattern.is_never_pattern();
         let mut flat_pat = FlatPat {
             match_pairs: vec![MatchPair::new(place, pattern, cx)],
             extra_data: PatternExtraData {
                 span: pattern.span,
                 bindings: Vec::new(),
                 ascriptions: Vec::new(),
+                is_never,
             },
         };
         cx.simplify_match_pairs(&mut flat_pat.match_pairs, &mut flat_pat.extra_data);
@@ -1062,6 +1067,8 @@ struct Candidate<'pat, 'tcx> {
     match_pairs: Vec<MatchPair<'pat, 'tcx>>,
 
     /// ...and if this is non-empty, one of these subcandidates also has to match...
+    // Invariant: at the end of the algorithm, this must never contain a `is_never` candidate
+    // because that would break binding consistency.
     subcandidates: Vec<Candidate<'pat, 'tcx>>,
 
     /// ...and the guard must be evaluated if there is one.
@@ -1172,6 +1179,7 @@ enum TestCase<'pat, 'tcx> {
     Range(&'pat PatRange<'tcx>),
     Slice { len: usize, variable_length: bool },
     Deref { temp: Place<'tcx>, mutability: Mutability },
+    Never,
     Or { pats: Box<[FlatPat<'pat, 'tcx>]> },
 }
 
@@ -1238,6 +1246,9 @@ enum TestKind<'tcx> {
         temp: Place<'tcx>,
         mutability: Mutability,
     },
+
+    /// Assert unreachability of never patterns.
+    Never,
 }
 
 /// A test to perform to determine which [`Candidate`] matches a value.
@@ -1662,6 +1673,27 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 self.cfg.goto(or_block, source_info, any_matches);
             }
             candidate.pre_binding_block = Some(any_matches);
+        } else {
+            // Never subcandidates may have a set of bindings inconsistent with their siblings,
+            // which would break later code. So we filter them out. Note that we can't filter out
+            // top-level candidates this way.
+            candidate.subcandidates.retain_mut(|candidate| {
+                if candidate.extra_data.is_never {
+                    candidate.visit_leaves(|subcandidate| {
+                        let block = subcandidate.pre_binding_block.unwrap();
+                        // That block is already unreachable but needs a terminator to make the MIR well-formed.
+                        let source_info = self.source_info(subcandidate.extra_data.span);
+                        self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
+                    });
+                    false
+                } else {
+                    true
+                }
+            });
+            if candidate.subcandidates.is_empty() {
+                // If `candidate` has become a leaf candidate, ensure it has a `pre_binding_block`.
+                candidate.pre_binding_block = Some(self.cfg.start_new_block());
+            }
         }
     }
 
@@ -2008,6 +2040,14 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             block = fresh_block;
         }
 
+        if candidate.extra_data.is_never {
+            // This arm has a dummy body, we don't need to generate code for it. `block` is already
+            // unreachable (except via false edge).
+            let source_info = self.source_info(candidate.extra_data.span);
+            self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
+            return self.cfg.start_new_block();
+        }
+
         self.ascribe_types(
             block,
             parent_data
diff --git a/compiler/rustc_mir_build/src/build/matches/test.rs b/compiler/rustc_mir_build/src/build/matches/test.rs
index 5dd478aa422..7f65697fa4b 100644
--- a/compiler/rustc_mir_build/src/build/matches/test.rs
+++ b/compiler/rustc_mir_build/src/build/matches/test.rs
@@ -44,6 +44,8 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
 
             TestCase::Deref { temp, mutability } => TestKind::Deref { temp, mutability },
 
+            TestCase::Never => TestKind::Never,
+
             TestCase::Or { .. } => bug!("or-patterns should have already been handled"),
 
             TestCase::Irrefutable { .. } => span_bug!(
@@ -262,6 +264,20 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 let target = target_block(TestBranch::Success);
                 self.call_deref(block, target, place, mutability, ty, temp, test.span);
             }
+
+            TestKind::Never => {
+                // Check that the place is initialized.
+                // FIXME(never_patterns): Also assert validity of the data at `place`.
+                self.cfg.push_fake_read(
+                    block,
+                    source_info,
+                    FakeReadCause::ForMatchedPlace(None),
+                    place,
+                );
+                // A never pattern is only allowed on an uninhabited type, so validity of the data
+                // implies unreachability.
+                self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
+            }
         }
     }
 
@@ -710,6 +726,11 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 Some(TestBranch::Success)
             }
 
+            (TestKind::Never, _) => {
+                fully_matched = true;
+                Some(TestBranch::Success)
+            }
+
             (
                 TestKind::Switch { .. }
                 | TestKind::SwitchInt { .. }
diff --git a/compiler/rustc_mir_build/src/build/matches/util.rs b/compiler/rustc_mir_build/src/build/matches/util.rs
index 2f9390c22a8..02bea6f8e9e 100644
--- a/compiler/rustc_mir_build/src/build/matches/util.rs
+++ b/compiler/rustc_mir_build/src/build/matches/util.rs
@@ -124,7 +124,8 @@ impl<'pat, 'tcx> MatchPair<'pat, 'tcx> {
         let default_irrefutable = || TestCase::Irrefutable { binding: None, ascription: None };
         let mut subpairs = Vec::new();
         let test_case = match pattern.kind {
-            PatKind::Never | PatKind::Wild | PatKind::Error(_) => default_irrefutable(),
+            PatKind::Wild | PatKind::Error(_) => default_irrefutable(),
+
             PatKind::Or { ref pats } => TestCase::Or {
                 pats: pats.iter().map(|pat| FlatPat::new(place_builder.clone(), pat, cx)).collect(),
             },
@@ -260,6 +261,8 @@ impl<'pat, 'tcx> MatchPair<'pat, 'tcx> {
                 subpairs.push(MatchPair::new(PlaceBuilder::from(temp).deref(), subpattern, cx));
                 TestCase::Deref { temp, mutability }
             }
+
+            PatKind::Never => TestCase::Never,
         };
 
         MatchPair { place, test_case, subpairs, pattern }
diff --git a/tests/crashes/120421.rs b/tests/crashes/120421.rs
deleted file mode 100644
index b6059f3ace4..00000000000
--- a/tests/crashes/120421.rs
+++ /dev/null
@@ -1,12 +0,0 @@
-//@ known-bug: #120421
-//@ compile-flags: -Zlint-mir
-
-#![feature(never_patterns)]
-
-enum Void {}
-
-fn main() {
-    let res_void: Result<bool, Void> = Ok(true);
-
-    for (Ok(mut _x) | Err(!)) in [res_void] {}
-}
diff --git a/tests/mir-opt/building/match/never_patterns.opt1.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/never_patterns.opt1.SimplifyCfg-initial.after.mir
new file mode 100644
index 00000000000..78356a90743
--- /dev/null
+++ b/tests/mir-opt/building/match/never_patterns.opt1.SimplifyCfg-initial.after.mir
@@ -0,0 +1,41 @@
+// MIR for `opt1` after SimplifyCfg-initial
+
+fn opt1(_1: &Result<u32, Void>) -> &u32 {
+    debug res => _1;
+    let mut _0: &u32;
+    let mut _2: isize;
+    let _3: &u32;
+    let mut _4: !;
+    let mut _5: ();
+    scope 1 {
+        debug x => _3;
+    }
+
+    bb0: {
+        PlaceMention(_1);
+        _2 = discriminant((*_1));
+        switchInt(move _2) -> [0: bb2, 1: bb3, otherwise: bb1];
+    }
+
+    bb1: {
+        FakeRead(ForMatchedPlace(None), _1);
+        unreachable;
+    }
+
+    bb2: {
+        falseEdge -> [real: bb4, imaginary: bb3];
+    }
+
+    bb3: {
+        FakeRead(ForMatchedPlace(None), (((*_1) as Err).0: Void));
+        unreachable;
+    }
+
+    bb4: {
+        StorageLive(_3);
+        _3 = &(((*_1) as Ok).0: u32);
+        _0 = &(*_3);
+        StorageDead(_3);
+        return;
+    }
+}
diff --git a/tests/mir-opt/building/match/never_patterns.opt2.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/never_patterns.opt2.SimplifyCfg-initial.after.mir
new file mode 100644
index 00000000000..979fbb2860d
--- /dev/null
+++ b/tests/mir-opt/building/match/never_patterns.opt2.SimplifyCfg-initial.after.mir
@@ -0,0 +1,35 @@
+// MIR for `opt2` after SimplifyCfg-initial
+
+fn opt2(_1: &Result<u32, Void>) -> &u32 {
+    debug res => _1;
+    let mut _0: &u32;
+    let mut _2: isize;
+    let _3: &u32;
+    scope 1 {
+        debug x => _3;
+    }
+
+    bb0: {
+        PlaceMention(_1);
+        _2 = discriminant((*_1));
+        switchInt(move _2) -> [0: bb2, 1: bb3, otherwise: bb1];
+    }
+
+    bb1: {
+        FakeRead(ForMatchedPlace(None), _1);
+        unreachable;
+    }
+
+    bb2: {
+        StorageLive(_3);
+        _3 = &(((*_1) as Ok).0: u32);
+        _0 = &(*_3);
+        StorageDead(_3);
+        return;
+    }
+
+    bb3: {
+        FakeRead(ForMatchedPlace(None), (((*_1) as Err).0: Void));
+        unreachable;
+    }
+}
diff --git a/tests/mir-opt/building/match/never_patterns.opt3.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/never_patterns.opt3.SimplifyCfg-initial.after.mir
new file mode 100644
index 00000000000..93ebe600b3f
--- /dev/null
+++ b/tests/mir-opt/building/match/never_patterns.opt3.SimplifyCfg-initial.after.mir
@@ -0,0 +1,35 @@
+// MIR for `opt3` after SimplifyCfg-initial
+
+fn opt3(_1: &Result<u32, Void>) -> &u32 {
+    debug res => _1;
+    let mut _0: &u32;
+    let mut _2: isize;
+    let _3: &u32;
+    scope 1 {
+        debug x => _3;
+    }
+
+    bb0: {
+        PlaceMention(_1);
+        _2 = discriminant((*_1));
+        switchInt(move _2) -> [0: bb3, 1: bb2, otherwise: bb1];
+    }
+
+    bb1: {
+        FakeRead(ForMatchedPlace(None), _1);
+        unreachable;
+    }
+
+    bb2: {
+        FakeRead(ForMatchedPlace(None), (((*_1) as Err).0: Void));
+        unreachable;
+    }
+
+    bb3: {
+        StorageLive(_3);
+        _3 = &(((*_1) as Ok).0: u32);
+        _0 = &(*_3);
+        StorageDead(_3);
+        return;
+    }
+}
diff --git a/tests/mir-opt/building/match/never_patterns.rs b/tests/mir-opt/building/match/never_patterns.rs
new file mode 100644
index 00000000000..8b52440da4c
--- /dev/null
+++ b/tests/mir-opt/building/match/never_patterns.rs
@@ -0,0 +1,44 @@
+#![feature(never_patterns)]
+#![allow(incomplete_features)]
+
+enum Void {}
+
+// EMIT_MIR never_patterns.opt1.SimplifyCfg-initial.after.mir
+fn opt1(res: &Result<u32, Void>) -> &u32 {
+    // CHECK-LABEL: fn opt1(
+    // CHECK: bb0: {
+    // CHECK-NOT: {{bb.*}}: {
+    // CHECK: return;
+    match res {
+        Ok(x) => x,
+        Err(!),
+    }
+}
+
+// EMIT_MIR never_patterns.opt2.SimplifyCfg-initial.after.mir
+fn opt2(res: &Result<u32, Void>) -> &u32 {
+    // CHECK-LABEL: fn opt2(
+    // CHECK: bb0: {
+    // CHECK-NOT: {{bb.*}}: {
+    // CHECK: return;
+    match res {
+        Ok(x) | Err(!) => x,
+    }
+}
+
+// EMIT_MIR never_patterns.opt3.SimplifyCfg-initial.after.mir
+fn opt3(res: &Result<u32, Void>) -> &u32 {
+    // CHECK-LABEL: fn opt3(
+    // CHECK: bb0: {
+    // CHECK-NOT: {{bb.*}}: {
+    // CHECK: return;
+    match res {
+        Err(!) | Ok(x) => x,
+    }
+}
+
+fn main() {
+    assert_eq!(opt1(&Ok(0)), &0);
+    assert_eq!(opt2(&Ok(0)), &0);
+    assert_eq!(opt3(&Ok(0)), &0);
+}
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/check.rs b/tests/ui/rfcs/rfc-0000-never_patterns/check.rs
index 0831477e749..dc13dd05fa6 100644
--- a/tests/ui/rfcs/rfc-0000-never_patterns/check.rs
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/check.rs
@@ -1,3 +1,4 @@
+// Check that never patterns can't have bodies or guards.
 #![feature(never_patterns)]
 #![allow(incomplete_features)]
 
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/check.stderr b/tests/ui/rfcs/rfc-0000-never_patterns/check.stderr
index 25f7343a8a8..fbf7aa02ac2 100644
--- a/tests/ui/rfcs/rfc-0000-never_patterns/check.stderr
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/check.stderr
@@ -1,5 +1,5 @@
 error: a never pattern is always unreachable
-  --> $DIR/check.rs:14:20
+  --> $DIR/check.rs:15:20
    |
 LL |         Some(!) => {}
    |                    ^^
@@ -8,13 +8,13 @@ LL |         Some(!) => {}
    |                    help: remove this expression
 
 error: a guard on a never pattern will never be run
-  --> $DIR/check.rs:19:20
+  --> $DIR/check.rs:20:20
    |
 LL |         Some(!) if true,
    |                    ^^^^ help: remove this guard
 
 error: a never pattern is always unreachable
-  --> $DIR/check.rs:24:28
+  --> $DIR/check.rs:25:28
    |
 LL |         Some(!) if true => {}
    |                            ^^
@@ -23,7 +23,7 @@ LL |         Some(!) if true => {}
    |                            help: remove this expression
 
 error: a never pattern is always unreachable
-  --> $DIR/check.rs:29:27
+  --> $DIR/check.rs:30:27
    |
 LL |         Some(never!()) => {}
    |                           ^^
@@ -32,7 +32,7 @@ LL |         Some(never!()) => {}
    |                           help: remove this expression
 
 error[E0004]: non-exhaustive patterns: `Some(!)` not covered
-  --> $DIR/check.rs:18:11
+  --> $DIR/check.rs:19:11
    |
 LL |     match None::<Void> {
    |           ^^^^^^^^^^^^ pattern `Some(!)` not covered
@@ -50,7 +50,7 @@ LL +         Some(!)
    |
 
 error[E0004]: non-exhaustive patterns: `Some(!)` not covered
-  --> $DIR/check.rs:23:11
+  --> $DIR/check.rs:24:11
    |
 LL |     match None::<Void> {
    |           ^^^^^^^^^^^^ pattern `Some(!)` not covered
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.rs b/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.rs
new file mode 100644
index 00000000000..f8f9d7a9aa6
--- /dev/null
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.rs
@@ -0,0 +1,12 @@
+#![feature(never_patterns)]
+#![allow(incomplete_features)]
+
+enum Void {}
+
+fn main() {}
+
+fn anything<T>() -> T {
+    let x: Void;
+    match x { ! }
+    //~^ ERROR used binding `x` isn't initialized
+}
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.stderr b/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.stderr
new file mode 100644
index 00000000000..1a6c4127085
--- /dev/null
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/check_place_is_initialized.stderr
@@ -0,0 +1,16 @@
+error[E0381]: used binding `x` isn't initialized
+  --> $DIR/check_place_is_initialized.rs:10:15
+   |
+LL |     let x: Void;
+   |         - binding declared here but left uninitialized
+LL |     match x { ! }
+   |               ^ `x` used here but it isn't initialized
+   |
+help: consider assigning a value
+   |
+LL |     let x: Void = /* value */;
+   |                 +++++++++++++
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0381`.
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/typeck.rs b/tests/ui/rfcs/rfc-0000-never_patterns/typeck.rs
index e8bfa9245f5..8300f953dc1 100644
--- a/tests/ui/rfcs/rfc-0000-never_patterns/typeck.rs
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/typeck.rs
@@ -123,3 +123,15 @@ fn never_pattern_typeck_pass(void: Void) {
         Some(!),
     }
 }
+
+struct Unsized {
+    void: Void,
+    slice: [u8],
+}
+
+#[cfg(pass)]
+fn not_sized(x: &Unsized) {
+    match *x {
+        !,
+    }
+}
diff --git a/tests/ui/rfcs/rfc-0000-never_patterns/use-bindings.rs b/tests/ui/rfcs/rfc-0000-never_patterns/use-bindings.rs
new file mode 100644
index 00000000000..33da6f02ce2
--- /dev/null
+++ b/tests/ui/rfcs/rfc-0000-never_patterns/use-bindings.rs
@@ -0,0 +1,29 @@
+//@ check-pass
+#![feature(never_patterns)]
+#![allow(incomplete_features)]
+
+#[derive(Copy, Clone)]
+enum Void {}
+
+fn main() {
+    let res_void: Result<bool, Void> = Ok(true);
+
+    let (Ok(x) | Err(!)) = res_void;
+    println!("{x}");
+    let (Ok(x) | Err(!)) = &res_void;
+    println!("{x}");
+    let (Err(!) | Ok(x)) = res_void;
+    println!("{x}");
+
+    match res_void {
+        Ok(x) | Err(!) => println!("{x}"),
+    }
+    match res_void {
+        Err(!) | Ok(x) => println!("{x}"),
+    }
+
+    let res_res_void: Result<Result<bool, Void>, Void> = Ok(Ok(true));
+    match res_res_void {
+        Ok(Ok(x) | Err(!)) | Err(!) => println!("{x}"),
+    }
+}