Auto merge of #88804 - Mark-Simulacrum:never-algo-v2, r=nikomatsakis,jackh726

Revise never type fallback algorithm

This is a rebase of https://github.com/rust-lang/rust/pull/84573, but dropping the stabilization of never type (and the accompanying large test diff).

Each commit builds & has tests updated alongside it, and could be reviewed in a more or less standalone fashion. But it may make more sense to review the PR as a whole, I'm not sure. It should be noted that tests being updated isn't really a good indicator of final behavior -- never_type_fallback is not enabled by default in this PR, so we can't really see the full effects of the commits here.

This combines the work by Niko, which is [documented in this gist](https://gist.github.com/nikomatsakis/7a07b265dc12f5c3b3bd0422018fa660), with some additional rules largely derived to target specific known patterns that regress with the algorithm solely derived by Niko. We build these from an intuition that:

* In general, fallback to `()` is *sound* in all cases
* But, in general, we *prefer* fallback to `!` as it accepts more code, particularly that written to intentionally use `!` (e.g., Result's with a Infallible/! variant).

When evaluating Niko's proposed algorithm, we find that there are certain cases where fallback to `!` leads to compilation failures in real-world code, and fallback to `()` fixes those errors. In order to allow for stabilization, we need to fix a good portion of these patterns.

The final rule set this PR proposes is that, by default, we fallback from `?T` to `!`, with the following exceptions:

1. `?T: Foo` and `Bar::Baz = ?T` and `(): Foo`, then fallback to `()`
2. Per [Niko's algorithm](https://gist.github.com/nikomatsakis/7a07b265dc12f5c3b3bd0422018fa660#proposal-fallback-chooses-between--and--based-on-the-coercion-graph), the "live" `?T` also fallback to `()`.

The first rule is necessary to address a fairly common pattern which boils down to something like the snippet below. Without rule 1, we do not see the closure's return type as needing a () fallback, which leads to compilation failure.

```rust
#![feature(never_type_fallback)]

trait Bar { }
impl Bar for () {  }
impl Bar for u32 {  }

fn foo<R: Bar>(_: impl Fn() -> R) {}

fn main() {
    foo(|| panic!());
}
```

r? `@jackh726`

13 files changed, 225 insertions, 36 deletions

diff --git a/src/test/ui/coercion/coerce-issue-49593-box-never.nofallback.stderr b/src/test/ui/coercion/coerce-issue-49593-box-never.nofallback.stderr
new file mode 100644
index 00000000000..fbaa874792a
--- /dev/null
+++ b/src/test/ui/coercion/coerce-issue-49593-box-never.nofallback.stderr
@@ -0,0 +1,19 @@
+error[E0277]: the trait bound `(): std::error::Error` is not satisfied
+  --> $DIR/coerce-issue-49593-box-never.rs:17:53
+   |
+LL |     /* *mut $0 is coerced to Box<dyn Error> here */ Box::<_ /* ! */>::new(x)
+   |                                                     ^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::error::Error` is not implemented for `()`
+   |
+   = note: required for the cast to the object type `dyn std::error::Error`
+
+error[E0277]: the trait bound `(): std::error::Error` is not satisfied
+  --> $DIR/coerce-issue-49593-box-never.rs:22:49
+   |
+LL |     /* *mut $0 is coerced to *mut Error here */ raw_ptr_box::<_ /* ! */>(x)
+   |                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::error::Error` is not implemented for `()`
+   |
+   = note: required for the cast to the object type `(dyn std::error::Error + 'static)`
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/src/test/ui/coercion/coerce-issue-49593-box-never.rs b/src/test/ui/coercion/coerce-issue-49593-box-never.rs
index 0824ce8cd58..7a4324bd5ad 100644
--- a/src/test/ui/coercion/coerce-issue-49593-box-never.rs
+++ b/src/test/ui/coercion/coerce-issue-49593-box-never.rs
@@ -1,5 +1,9 @@
-// check-pass
-#![feature(never_type, never_type_fallback)]
+// revisions: nofallback fallback
+//[fallback] check-pass
+//[nofallback] check-fail
+
+#![feature(never_type)]
+#![cfg_attr(fallback, feature(never_type_fallback))]
 #![allow(unreachable_code)]
 
 use std::error::Error;
@@ -11,10 +15,12 @@ fn raw_ptr_box<T>(t: T) -> *mut T {
 
 fn foo(x: !) -> Box<dyn Error> {
     /* *mut $0 is coerced to Box<dyn Error> here */ Box::<_ /* ! */>::new(x)
+    //[nofallback]~^ ERROR trait bound `(): std::error::Error` is not satisfied
 }
 
 fn foo_raw_ptr(x: !) -> *mut dyn Error {
     /* *mut $0 is coerced to *mut Error here */ raw_ptr_box::<_ /* ! */>(x)
+    //[nofallback]~^ ERROR trait bound `(): std::error::Error` is not satisfied
 }
 
 fn no_coercion(d: *mut dyn Error) -> *mut dyn Error {
diff --git a/src/test/ui/never_type/defaulted-never-note.stderr b/src/test/ui/never_type/defaulted-never-note.fallback.stderr
index 109a81a5ca0..588d644c77b 100644
--- a/src/test/ui/never_type/defaulted-never-note.stderr
+++ b/src/test/ui/never_type/defaulted-never-note.fallback.stderr
@@ -1,5 +1,5 @@
 error[E0277]: the trait bound `!: ImplementedForUnitButNotNever` is not satisfied
-  --> $DIR/defaulted-never-note.rs:26:5
+  --> $DIR/defaulted-never-note.rs:30:5
    |
 LL |     foo(_x);
    |     ^^^ the trait `ImplementedForUnitButNotNever` is not implemented for `!`
@@ -8,7 +8,7 @@ LL |     foo(_x);
    = note: this error might have been caused by changes to Rust's type-inference algorithm (see issue #48950 <https://github.com/rust-lang/rust/issues/48950> for more information).
    = help: did you intend to use the type `()` here instead?
 note: required by a bound in `foo`
-  --> $DIR/defaulted-never-note.rs:21:11
+  --> $DIR/defaulted-never-note.rs:25:11
    |
 LL | fn foo<T: ImplementedForUnitButNotNever>(_t: T) {}
    |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `foo`
diff --git a/src/test/ui/never_type/defaulted-never-note.rs b/src/test/ui/never_type/defaulted-never-note.rs
index 70333c5f324..54f551759cb 100644
--- a/src/test/ui/never_type/defaulted-never-note.rs
+++ b/src/test/ui/never_type/defaulted-never-note.rs
@@ -1,6 +1,10 @@
+// revisions: nofallback fallback
+//[nofallback] run-pass
+//[fallback] check-fail
+
 // We need to opt into the `never_type_fallback` feature
 // to trigger the requirement that this is testing.
-#![feature(never_type, never_type_fallback)]
+#![cfg_attr(fallback, feature(never_type, never_type_fallback))]
 
 #![allow(unused)]
 
@@ -19,16 +23,16 @@ trait ImplementedForUnitButNotNever {}
 impl ImplementedForUnitButNotNever for () {}
 
 fn foo<T: ImplementedForUnitButNotNever>(_t: T) {}
-//~^ NOTE required by this bound in `foo`
-//~| NOTE required by a bound in `foo`
+//[fallback]~^ NOTE required by this bound in `foo`
+//[fallback]~| NOTE required by a bound in `foo`
 fn smeg() {
     let _x = return;
     foo(_x);
-    //~^ ERROR the trait bound
-    //~| NOTE the trait `ImplementedForUnitButNotNever` is not implemented
-    //~| NOTE this trait is implemented for `()`
-    //~| NOTE this error might have been caused
-    //~| HELP did you intend
+    //[fallback]~^ ERROR the trait bound
+    //[fallback]~| NOTE the trait `ImplementedForUnitButNotNever` is not implemented
+    //[fallback]~| NOTE this trait is implemented for `()`
+    //[fallback]~| NOTE this error might have been caused
+    //[fallback]~| HELP did you intend
 }
 
 fn main() {
diff --git a/src/test/ui/never_type/diverging-fallback-control-flow.rs b/src/test/ui/never_type/diverging-fallback-control-flow.rs
index ea4881049d7..45a3362fa6d 100644
--- a/src/test/ui/never_type/diverging-fallback-control-flow.rs
+++ b/src/test/ui/never_type/diverging-fallback-control-flow.rs
@@ -1,30 +1,28 @@
+// revisions: nofallback fallback
 // run-pass
 
 #![allow(dead_code)]
 #![allow(unused_assignments)]
 #![allow(unused_variables)]
 #![allow(unreachable_code)]
-
 // Test various cases where we permit an unconstrained variable
-// to fallback based on control-flow.
-//
-// These represent current behavior, but are pretty dubious.  I would
-// like to revisit these and potentially change them. --nmatsakis
-
-#![feature(never_type, never_type_fallback)]
+// to fallback based on control-flow. In all of these cases,
+// the type variable winds up being the target of both a `!` coercion
+// and a coercion from a non-`!` variable, and hence falls back to `()`.
+#![cfg_attr(fallback, feature(never_type, never_type_fallback))]
 
-trait BadDefault {
+trait UnitDefault {
     fn default() -> Self;
 }
 
-impl BadDefault for u32 {
+impl UnitDefault for u32 {
     fn default() -> Self {
         0
     }
 }
 
-impl BadDefault for ! {
-    fn default() -> ! {
+impl UnitDefault for () {
+    fn default() -> () {
         panic!()
     }
 }
@@ -33,7 +31,7 @@ fn assignment() {
     let x;
 
     if true {
-        x = BadDefault::default();
+        x = UnitDefault::default();
     } else {
         x = return;
     }
@@ -45,13 +43,13 @@ fn assignment_rev() {
     if true {
         x = return;
     } else {
-        x = BadDefault::default();
+        x = UnitDefault::default();
     }
 }
 
 fn if_then_else() {
     let _x = if true {
-        BadDefault::default()
+        UnitDefault::default()
     } else {
         return;
     };
@@ -61,19 +59,19 @@ fn if_then_else_rev() {
     let _x = if true {
         return;
     } else {
-        BadDefault::default()
+        UnitDefault::default()
     };
 }
 
 fn match_arm() {
-    let _x = match Ok(BadDefault::default()) {
+    let _x = match Ok(UnitDefault::default()) {
         Ok(v) => v,
         Err(()) => return,
     };
 }
 
 fn match_arm_rev() {
-    let _x = match Ok(BadDefault::default()) {
+    let _x = match Ok(UnitDefault::default()) {
         Err(()) => return,
         Ok(v) => v,
     };
@@ -84,7 +82,7 @@ fn loop_break() {
         if false {
             break return;
         } else {
-            break BadDefault::default();
+            break UnitDefault::default();
         }
     };
 }
@@ -94,9 +92,9 @@ fn loop_break_rev() {
         if false {
             break return;
         } else {
-            break BadDefault::default();
+            break UnitDefault::default();
         }
     };
 }
 
-fn main() { }
+fn main() {}
diff --git a/src/test/ui/never_type/diverging-fallback-no-leak.fallback.stderr b/src/test/ui/never_type/diverging-fallback-no-leak.fallback.stderr
new file mode 100644
index 00000000000..3a5b602f111
--- /dev/null
+++ b/src/test/ui/never_type/diverging-fallback-no-leak.fallback.stderr
@@ -0,0 +1,18 @@
+error[E0277]: the trait bound `!: Test` is not satisfied
+  --> $DIR/diverging-fallback-no-leak.rs:17:5
+   |
+LL |     unconstrained_arg(return);
+   |     ^^^^^^^^^^^^^^^^^ the trait `Test` is not implemented for `!`
+   |
+   = note: this trait is implemented for `()`.
+   = note: this error might have been caused by changes to Rust's type-inference algorithm (see issue #48950 <https://github.com/rust-lang/rust/issues/48950> for more information).
+   = help: did you intend to use the type `()` here instead?
+note: required by a bound in `unconstrained_arg`
+  --> $DIR/diverging-fallback-no-leak.rs:12:25
+   |
+LL | fn unconstrained_arg<T: Test>(_: T) {}
+   |                         ^^^^ required by this bound in `unconstrained_arg`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/src/test/ui/never_type/diverging-fallback-no-leak.rs b/src/test/ui/never_type/diverging-fallback-no-leak.rs
new file mode 100644
index 00000000000..03478e19ddc
--- /dev/null
+++ b/src/test/ui/never_type/diverging-fallback-no-leak.rs
@@ -0,0 +1,19 @@
+// revisions: nofallback fallback
+//[nofallback] check-pass
+
+#![cfg_attr(fallback, feature(never_type, never_type_fallback))]
+
+fn make_unit() {}
+
+trait Test {}
+impl Test for i32 {}
+impl Test for () {}
+
+fn unconstrained_arg<T: Test>(_: T) {}
+
+fn main() {
+    // Here the type variable falls back to `!`,
+    // and hence we get a type error.
+    unconstrained_arg(return);
+    //[fallback]~^ ERROR trait bound `!: Test` is not satisfied
+}
diff --git a/src/test/ui/never_type/diverging-fallback-unconstrained-return.rs b/src/test/ui/never_type/diverging-fallback-unconstrained-return.rs
new file mode 100644
index 00000000000..7ea97126f89
--- /dev/null
+++ b/src/test/ui/never_type/diverging-fallback-unconstrained-return.rs
@@ -0,0 +1,37 @@
+// Variant of diverging-falllback-control-flow that tests
+// the specific case of a free function with an unconstrained
+// return type. This captures the pattern we saw in the wild
+// in the objc crate, where changing the fallback from `!` to `()`
+// resulted in unsoundness.
+//
+// check-pass
+
+// revisions: nofallback fallback
+
+#![cfg_attr(fallback, feature(never_type, never_type_fallback))]
+
+
+fn make_unit() {}
+
+trait UnitReturn {}
+impl UnitReturn for i32 {}
+impl UnitReturn for () {}
+
+fn unconstrained_return<T: UnitReturn>() -> T {
+    unsafe {
+        let make_unit_fn: fn() = make_unit;
+        let ffi: fn() -> T = std::mem::transmute(make_unit_fn);
+        ffi()
+    }
+}
+
+fn main() {
+    // In Ye Olde Days, the `T` parameter of `unconstrained_return`
+    // winds up "entangled" with the `!` type that results from
+    // `panic!`, and hence falls back to `()`. This is kind of unfortunate
+    // and unexpected. When we introduced the `!` type, the original
+    // idea was to change that fallback to `!`, but that would have resulted
+    // in this code no longer compiling (or worse, in some cases it injected
+    // unsound results).
+    let _ = if true { unconstrained_return() } else { panic!() };
+}
diff --git a/src/test/ui/never_type/fallback-closure-ret.rs b/src/test/ui/never_type/fallback-closure-ret.rs
new file mode 100644
index 00000000000..5c8ce48cbb0
--- /dev/null
+++ b/src/test/ui/never_type/fallback-closure-ret.rs
@@ -0,0 +1,23 @@
+// This test verifies that never type fallback preserves the following code in a
+// compiling state. This pattern is fairly common in the wild, notably seen in
+// wasmtime v0.16. Typically this is some closure wrapper that expects a
+// collection of 'known' signatures, and -> ! is not included in that set.
+//
+// This test is specifically targeted by the unit type fallback when
+// encountering a set of obligations like `?T: Foo` and `Trait::Projection =
+// ?T`. In the code below, these are `R: Bar` and `Fn::Output = R`.
+//
+// revisions: nofallback fallback
+// check-pass
+
+#![cfg_attr(fallback, feature(never_type_fallback))]
+
+trait Bar { }
+impl Bar for () {  }
+impl Bar for u32 {  }
+
+fn foo<R: Bar>(_: impl Fn() -> R) {}
+
+fn main() {
+    foo(|| panic!());
+}
diff --git a/src/test/ui/never_type/fallback-closure-wrap.fallback.stderr b/src/test/ui/never_type/fallback-closure-wrap.fallback.stderr
new file mode 100644
index 00000000000..78d1a3caf4a
--- /dev/null
+++ b/src/test/ui/never_type/fallback-closure-wrap.fallback.stderr
@@ -0,0 +1,17 @@
+error[E0271]: type mismatch resolving `<[closure@$DIR/fallback-closure-wrap.rs:18:40: 21:6] as FnOnce<()>>::Output == ()`
+  --> $DIR/fallback-closure-wrap.rs:18:31
+   |
+LL |       let error = Closure::wrap(Box::new(move || {
+   |  _______________________________^
+LL | |
+LL | |         panic!("Can't connect to server.");
+LL | |     }) as Box<dyn FnMut()>);
+   | |______^ expected `()`, found `!`
+   |
+   = note: expected unit type `()`
+                   found type `!`
+   = note: required for the cast to the object type `dyn FnMut()`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0271`.
diff --git a/src/test/ui/never_type/fallback-closure-wrap.rs b/src/test/ui/never_type/fallback-closure-wrap.rs
new file mode 100644
index 00000000000..af0577ac060
--- /dev/null
+++ b/src/test/ui/never_type/fallback-closure-wrap.rs
@@ -0,0 +1,30 @@
+// This is a minified example from Crater breakage observed when attempting to
+// stabilize never type, nstoddard/webgl-gui @ 22f0169f.
+//
+// This particular test case currently fails as the inference to `()` rather
+// than `!` happens as a result of an `as` cast, which is not currently tracked.
+// Crater did not find many cases of this occuring, but it is included for
+// awareness.
+//
+// revisions: nofallback fallback
+//[nofallback] check-pass
+//[fallback] check-fail
+
+#![cfg_attr(fallback, feature(never_type_fallback))]
+
+use std::marker::PhantomData;
+
+fn main() {
+    let error = Closure::wrap(Box::new(move || {
+        //[fallback]~^ ERROR type mismatch resolving
+        panic!("Can't connect to server.");
+    }) as Box<dyn FnMut()>);
+}
+
+struct Closure<T: ?Sized>(PhantomData<T>);
+
+impl<T: ?Sized> Closure<T> {
+    fn wrap(data: Box<T>) -> Closure<T> {
+        todo!()
+    }
+}
diff --git a/src/test/ui/never_type/never-value-fallback-issue-66757.nofallback.stderr b/src/test/ui/never_type/never-value-fallback-issue-66757.nofallback.stderr
new file mode 100644
index 00000000000..f374266626b
--- /dev/null
+++ b/src/test/ui/never_type/never-value-fallback-issue-66757.nofallback.stderr
@@ -0,0 +1,17 @@
+error[E0277]: the trait bound `E: From<()>` is not satisfied
+  --> $DIR/never-value-fallback-issue-66757.rs:27:5
+   |
+LL |     <E as From<_>>::from(never);
+   |     ^^^^^^^^^^^^^^^^^^^^ the trait `From<()>` is not implemented for `E`
+   |
+   = help: the following implementations were found:
+             <E as From<!>>
+note: required by `from`
+  --> $SRC_DIR/core/src/convert/mod.rs:LL:COL
+   |
+LL |     fn from(_: T) -> Self;
+   |     ^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/src/test/ui/never_type/never-value-fallback-issue-66757.rs b/src/test/ui/never_type/never-value-fallback-issue-66757.rs
index f2e9e087307..6dc7e6ad2d9 100644
--- a/src/test/ui/never_type/never-value-fallback-issue-66757.rs
+++ b/src/test/ui/never_type/never-value-fallback-issue-66757.rs
@@ -4,12 +4,13 @@
 // never) and an uninferred variable (here the argument to `From`) it
 // doesn't fallback to `()` but rather `!`.
 //
-// run-pass
+// revisions: nofallback fallback
+//[fallback] run-pass
+//[nofallback] check-fail
 
 #![feature(never_type)]
 
-// FIXME(#67225) -- this should be true even without the fallback gate.
-#![feature(never_type_fallback)]
+#![cfg_attr(fallback, feature(never_type_fallback))]
 
 struct E;
 
@@ -23,7 +24,7 @@ impl From<!> for E {
 #[allow(dead_code)]
 fn foo(never: !) {
     <E as From<!>>::from(never);  // Ok
-    <E as From<_>>::from(never);  // Inference fails here
+    <E as From<_>>::from(never);  //[nofallback]~ ERROR trait bound `E: From<()>` is not satisfied
 }
 
 fn main() { }