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):

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!