Never-type fallback
===================

## Background:

The stabilization of the `!` ('never') type was recently attempted in https://github.com/rust-lang/rust/pull/65355, but reverted in https://github.com/rust-lang/rust/pull/67224. The reasons for the revert has to do with a relatively obscure feature of Rust known as "never-type fallback" (just "fallback" from here on out).

### What is the `!` type?

Rust allows the creation of 'empty enums' with no variants (e.g. `enum Void {}`). These types are unusual in that it is **impossible** to construct an instance of them - they are said to be 'uninhabited'.

The `!` type is a sort of 'canonical' empty enum, used to represent something which is statically impossible (e.g. `panic!()` or `abort!` returning). Unlike other empty enums, the `!` type has the ability to **coerce** to any other type. For example, consider this function:

fn match_it(val: Option<u8>) {
    let a: bool = match val {
        Some(_) => true,
        _ => panic!()
    };
}

Here, we `match` on an `Option<u8>`, producing a `bool`. Each arm of a `match` expression must produce the same type, so that the overall expression always produces the same type. The first arm produces `true` (a `bool`), while the second arm calls `panic!()`, which produces `!`.

Coercion works because any code that has a `!` type available/in-scope is known to be statically unreachable. In the case of the `match` expression, we know that anything after the call to `panic!()` is unreachable. So, it's fine to "pretend" that `panic!()` produced a `bool`, since no one will be able to observe the fact that no `bool` was ever produced.

### What is fallback?

In the previous example, we used a `!` type where a `bool` was expected. Inside the compiler, this is represented by replacing the `!` type with a new type variable: https://github.com/rust-lang/rust/blob/689fca01c5a1eac2d240bf08aa728171a28f2285/src/librustc_typeck/check/coercion.rs#L179

We will then unify this type variable with the expected type `bool`. Effectively, we're now pretending that `panic!()` returns a `bool`. Since `panic!()` never actually returns, this is perfectly fine.

This type variable was unified with `bool` because the `match_it` function required the `match` expression to produce a `bool`. However, what if we didn't impose any such restrictions:

let my_var = panic!() // What is the type of `my_var`?

Using some closure trickery, we can find out ([playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=dd70592fa0a5289a90887273222206a0)):

fn output_name<R, T: FnOnce() -> R>(_: T) -> &'static str {
    std::any::type_name::<R>()
}

fn main() {
    let some_closure = || {
        let _my_var = panic!();
        _my_var
    };
    println!("Type of _my_var: {}", output_name(some_closure));
}

Output:

Type of _my_var: ()

Surprisingly, the type of `_my_var` is not `!`, but `()` - despite the fact that `panic!()` has a return type of `!`.

This is the result of **fallback**. Earlier, we described how never-type coercion works by replacing instances of `!` with fresh type variables. If such a type variable never ends up unified with another type, we need to pick what type it should be. Currently, this is `()`: https://github.com/rust-lang/rust/blob/689fca01c5a1eac2d240bf08aa728171a28f2285/src/librustc/ty/context.rs#L2289

This behavior can be surprising, and somewhat undesirable. You would expect a `!` type to stay a `!` type, unless you try to coerce it into something else.

### Why can't never-type fallback produce a `!`, instead of `()`

This is exactly what the original stabilization of the `!` type tried to do. Unfortunately, this lead to undefined behavior being introduced in certain scenarios: https://github.com/rust-lang/rust/issues/66757#issuecomment-559136943

The core of the issue is code which looks like this:

fn unconstrained_return<T>() -> Result<T, String> {
    let ffi: fn() -> T = transmute(some_pointer);
    Ok(ffi())
}
fn foo() {
    match unconstrained_return::<_>() {
        Ok(x) => x,  // `x` has type `_`, which is unconstrained
        Err(s) => panic!(s),  // … except for unifying with the type of `panic!()`
        // so that both `match` arms have the same type.
        // Therefore `_` resolves to `!` and we "return" an `Ok(!)` value.
    };
}

There are several things going on here. The most significant is the use of an "unconstrained return type" - the function `unconstrained_return` claims to be able to produce an instance of *any* `T`. (In practive, such a function would need to `panic!()`, or be `unsafe` and require the caller to verify that the type can actually be produced somehow).

This return type ends up getting unified with the return value of a `panic!()` expression, which is similarly unconstrained. Previously, fallback would result in `panic!()` getting a type of `()`. However, with the never-type fallback change, `panic()!` will now 'correctly' evaluate to `!`. This means that the call to `unconstrained_return` will also end up with a return type of `!` - despite the fact that it actually returns!