# T-lang design meeting: Never type 2022-02-23

## High level overview

There are three main components to the general never type feature:

* Coercion to arbitrary types (`!` can become something else)
* Changes to inference fallback (unconstrained variables become `!`)
* `std::convert::Infallible` aliasing

## Coercion to arbitrary types

**Stable behavior**: functions with `!` return type, abrupt expressions (return, loop, etc.).

This is what allows expressions like panic!() in contexts that expect some other type, and is generally fairly widely used.

The main stability implication from this is that `!` is easy to 'lose': any coercion site which does not constrain to specifically `!` will end up using the inference fallback (see next section), which may result in a different type from `!`.

## Changes to inference fallback

**Unstable behavior**: gated on `never_type_fallback`.

Rust's current inference rules have a default fallback of `()` for unknown inference variables (that are not from integer/floating point literals, which are separately treated) which aren't constrained to any specific type.

This means that any `?T` which has no direct constraints placed on it will become `()` on stable today. This is typically not noticeable, since unconstrained inference variables are somewhat rare in live code.

The principle behind changing fallback from `()` to `!` is that since the variable is constrained, the type is 'unobserved' and so the expression must be dead. In practice, there are several cases where this is not true; some examples follow.

Note that changing a variable with type `()` to `!` can lead to UB, as the latter is uninhabited.

A sample of code where today we fallback to `()` in live code:

let x: /*?X*/ = match something() {
    pattern1 => Default::default(), // has type `?T`
    pattern2 => panic!("..."), // has type `!`
}; // the match has type `?M`

[playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f74310b43955cdf58067f656bfcc53dd) -- Use "Show MIR".

`?T` is not constrained, so it falls back to `()` on stable today.

There are an assortment of similar cases (in spirit if not in exact syntax in [this issue](https://github.com/rust-lang/rust/issues/66173)). It is perhaps worthwhile to note that at least in Mark's opinion the code here likely should never have compiled, instead demanding an explicit type be provided.

## `std::convert::Infallible` aliasing

`enum Infallible {}` was stabilized in order to permit moving forward with `TryFrom` alongside a blanket impl for infallibly convertible types (i.e., those with a `From` impl). The original intent was to move `Infallible` to be an alias for `!`, rather than just an empty enum. There is no intrinsic benefit to doing so, though, beyond slightly easier compatibility with APIs returning `!` (mostly by avoiding the need for explicit coercion sites) and shorter typing for APIs dealing with infallibility.

# Interactions & Problems

## Coercion to arbitrary types

The ability for `!` to coerce to arbitrary types can lead to confusing/unexpected behavior for users. This is partially mitigated by the inference fallback change to `!`, which means that there are fewer cases where an API expecting `!` happens to see `()`.

fn magic<R, F: FnOnce() -> R>(f: F) -> F { f }

fn main() {
    let f1 = magic(|| {}) as fn() -> (); // works fine
    let f2 = magic(|| loop {}) as fn() -> !; // errors
}

This [example](https://github.com/rust-lang/rust/issues/66738#issuecomment-1004381083) will compile with never_type_fallback enabled, but otherwise fails, even though it *seems* like everything should work since `loop {}` has type `!`. However, the return type of a closure here is unconstrained during inference, so it falls back to `()` on stable today.

## Changes to inference fallback

In order to backwards compatibly land `type Infallible = !`, we need to change inference fallback to coerce to `!`, as otherwise stable code which tries to produce `Infallible` will instead result in `()` (similar to the above case with coercions), resulting in breakage.

A few standard examples are found on [this page](https://rust-lang.github.io/never-type-initiative/evaluation/no-inference-changes.html).

However, due to soundness concerns (`!` appearing in live code means UB), we need to be careful about enabling fallback to `()` in all code. This leads to a relatively complicated design for the fallback algorithm: soundness along is *probably* (relatively high confidence, but no certainty I believe) is achieved with [v1](https://rust-lang.github.io/never-type-initiative/explainer/conditional-fallback-v1.html) design. This design constructs a coercion graph to try and detect which inference variables interact with live code and selects whether to fallback to `!` or `()` based on that.

As noted there, this is insufficient to avoid breaking changes. Crater finds roughly ~100 crates broken by v1 design, including some notable regressions in wasm-related crates.

[v2](https://github.com/rust-lang/rust/pull/88804) of the fallback algorithm slightly expands v1 to put a few extra cases to `()` fallback, preventing ~70 of those crates from regressing, including the notable crates. This version adds to v1 one more rule:

* `?T: Foo` and `Bar::Baz = ?T` and `(): Foo`, then fallback to `()`

Obviously, this is pretty ad-hoc, but is sufficient to fix code like this:

trait Foo { }
impl Foo for () { }
impl Foo for i32 { }
fn gimme<F: Foo>(f: impl Fn() -> F) { }
fn main() {
    gimme(|| panic!());
}

We don't fix a case like this, though; this occurs more rarely in the ecosystem and fixing it has some unfortunate implications for actually using `!` (many functions bound type variables with *some* trait which is implemented for `()`, so falling back in all of those cases removes some of the benefits and can lead to confusing behavior).

trait Foo { }
impl Foo for () { }
impl Foo for i32 { }
fn gimme<F: Foo>(f: F) { }
fn main() {
    gimme(panic!());
}

## Edition-boundary stabilization?

One of the common thoughts to stabilizing `!` is a question of whether we can make inference behave differently depending on the edition of the code. Largely, it seems like the answer here is no:

* If `std::convert::Infallible = !`, then inference fallback changes must be enabled (so Infallible would be different types on different editions, seems bad/impractical).
* Not clear how to cope with macros -- `?T` is not obviously tied to a particular token in many cases.

## uninhabited match

`match x: ! {}` or `match x: Result<T, !> { Ok(a) => a }` being permitted -- that is, making patterns respect inhabitedness -- is a separate feature, tracked in [#51085](https://github.com/rust-lang/rust/issues/51085). It currently has no real tie to `!` (any uninhabited type works equivalently).

# Pre-Meeting Conclusions

* v1/v2 Inference algorithm is too complex for viable stabilization
* Complexity likely necessary for sound changes to inference
* Users are at least partially exposed to complexity (some code just doesn't work as expected for hard to explain reasons)
* Ability to scale back complexity (e.g., by removing fallback from some or all code) is likely to be hard/impossible, even across edition boundaries (for the same reasons this is hard)
* Motivation for `!` having special coercion behavior seems weak
* Clearest rationale seems to be "obviously in unreachable code this is fine"
* Avoiding this coercion behavior would permit stabilizing `Infallible = !` (without inference fallback changes), except that we can't avoid it due to `!` already being exposed on stable (including in arbitrary user code via `fn() -> !`)
* In general, motivation for `!` feels relatively weak compared to complexity of moving forward with the changes
* [Draft RFC](https://rust-lang.github.io/never-type-initiative/RFC.html) attempts to propose a couple motivators, is drawn from original discussion
* Primary motivators around e.g. `Result<!, T>` having same size as `T` don't require `!`, `Infallible` works fine for that.

Possible paths forward:

* Remove support for `!` (aside from stable support) from the compiler (essentially, terminate never type initiative)
* Edition-dependent migration away from special coercion behavior for `!`, letting us avoid inference algorithm changes while changing `Infallible = !` aliasing.
* Leave never type in limbo -- current implementation *could* be stabilized as-is (largely regression free), modulo complexity and lack of known strong motivation. May also introduce soundness holes due to inference changes.

Key question for the meeting:

* What are the key goals for `!`? (i.e., motivation section, in some sense)

## Meeting

Attendance:
Team: Josh, Felix, Scott
Others: Mark, Michael Goulet (compiler-errors), Gary, Jane, David Barsky

## Questions / Discussion

# Question 1

Josh: "unconstrained variables become !" or "unconstrained variables *can* become !"?

# Question 2

Josh: Trying to understand the problem better: shouldn't the `match` example fail because `!` doesn't implement `Default`? Because it shouldn't be possible to "materialize" a `!` by any means other than a diverging computation.

* Mark: The match example is a simplified version; it illustrates breaking change w/o fancy fallback. You get UB when Default::default is replaced with `unconstrained_return()`, like in Servo code where the function returned an arbitrary T (transmuting function pointers to materialize a fn() -> T).
* josh: It *seems* like that case should become an error as well (because it tries to materialize a `!`), but for a different reason than the match (which should fail because `!` doesn't impl `Default`).
* Mark: It's not really possible for us to *know* that you're materializing a `!` -- you might genuinely expect that the function never returns, after all.

* Gary: It'll be a post-mono error in that case.
* Josh: I'd love to understand why we're so allergic to those. "so?". But that may be too much of a tangent.
* Gary: I think it's just that we currently don't have many of those. I personally prefer a post-mono error to runtime panic like we have for `assert_inhabited`.
* Josh: :+1:

let x: /*?X*/ = match something() {
    pattern1 => unconstrained(), // has type `?T`
    pattern2 => panic!("..."), // has type `!`
}; // the match has type `?M`

# Question 3

Scott: I think it's critical that we have *a* canonical uninhabited type. The ecosystem wants to be able to implement their traits for it, the same way [we implement a whole bunch of traits on it](https://doc.rust-lang.org/std/primitive.never.html#trait-implementations) (and [on `Infallible` too](https://doc.rust-lang.org/std/convert/enum.Infallible.html#trait-implementations)).

Michael: Does that need to be a language-level type though? Can we not just move those implementations to a standard uninhabited enum? (yeah, ^ I guess we impl those on Infallible too.)

Gary: We already have `!` as a return type so it is kinda already a language-level uninhabited type. It'll be unfortunate if we have a language-level one *and* a library-level one.

# Question 4

Josh: For the case involving closure return type inference (`|| loop {}`), is it that it's *harder* to do the inference in that case, or have we tried it and found it not feasible? Could we propagate the `!` to the closure return type, and handle that case the way people looking at it roughly expect it to work?

Scott: Hmm, from an inference perspective, isn't that the same case as `let x = panic!();`, though?

Michael: The specific fallback issues with `|| loop {}` have to do with the fact it's a closure, right? It's because we typecheck those bodies separately?

Gary: Closures are typechecked together with the containing item.

# Question 5

Scott: I'm sad that `Err(x)` being `Err::<!, _>(x)` is turning out to be impractical.
Michael: Same with None _not_ being `Option<!>`
Josh: :+1: Why *doesn't* this work? I'm not seeing that discussed in the doc. This seems like a primary motivation.
Gary: This is the consequence of `!` not really being a bottom type, isn't it?
Michael: Yeah, I think the fallback to `Option<()>` messes with that. I recall some discussions about relaxing the `PartialEq` on `Option<T>` for `Option<U>` where `T: PartialEq<U>` having inference issues and one of the solutions being making `!`/`None` smarter about this. But that's a tangent.

# Question 6

Josh: Is there research in this area, or *anything* we can draw on, or any expertise we could consult to come up with an inference algorithm here?

# Observation 7

> There is no intrinsic benefit to doing so

Scott: There is, in an ecosystem evolution sense. Because if people are implementing it for `Infallible` today making everything add the new impls -- with the MSRV complications -- is a bit of a mess.

# ~~Example 8~~

Scott: This doesn't work today, right?

fn foo() -> !;

fn bar() -> !{
    let x = foo();
    x // type error because `x` fell back to `()`, right?
}

Never mind, it does work: <https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=82518dbebfcd3e6aa3fdf076c6676e7a>

# Example 9

fn foo() -> Result<!, E>;
fn unconstrained_return<T>() -> T;

match asdf {
    A => foo()?, // <-- won't work without coercion or something
    B => unconstrained_return(),
}

fn foo() -> Result<!, E>;
fn unconstrained_return<T>() -> T;

match asdf {
    A => foo()?,
    B => unreachable!(),
}

This compiles today:

fn foo() -> Result<Infallible, E>;

match asdf {
    A => foo()?,
    B => unreachable!(),
}

This compiles today:

match asdf {
    A => unreachable!(),
    B => 3,
}

This doesn't compile today:

fn foo() -> Infallible;

match asdf {
    A => foo(),
    B => 3,
}

And if you want to "raise" `Infallible` to `!`, you make an empty match, like

match infallible {}

so this compiles:

fn foo() -> Infallible;

match asdf {
    A => match foo() {},
    B => 3,
}

Motivations:

* Canonical uninhabited type (that Infallible is an alias for)
*