Never type initiative

initiative status: active

What is this?

This page tracks the work of the never type initiative! To learn more about what we are trying to do, and to find out the people who are doing it, take a look at the charter.

Current status

The following table lists of the stages of an initiative, along with links to the artifacts that will be produced during that stage.

StageStateArtifact(s)
Proposal✅Tracking issue
Experimental🦀Evaluation
RFC
Development💤Explainer
Feature complete💤Stabilization report
Stabilized💤

Key:

  • ✅ -- phase complete
  • 🦀 -- phase in progress
  • 💤 -- phase not started yet

How Can I Get Involved?

  • Check for 'help wanted' issues on this repository!
  • If you would like to help with development, please contact the owner to find out if there are things that need doing.
  • If you would like to help with the design, check the list of active design questions first.
  • If you have questions about the design, you can file an issue, but be sure to check the FAQ or the design-questions first to see if there is already something that covers your topic.
  • If you are using the feature and would like to provide feedback about your experiences, please [open a "experience report" issue].
  • If you are using the feature and would like to report a bug, please open a regular issue.

We also participate on Zulip, feel free to introduce yourself over there and ask us any questions you have.

Building Documentation

This repository is also an mdbook project. You can view and build it using the following command.

mdbook serve

✏️ Updates

Lang-team initiatives give monthly updates. This section collects the updates from this initiative for posterity.

To add a new update:

  • Create a new file updates/YYYY-mmm.md, e.g. updates/2021-nov.md
  • Link it from the SUMMARY.md

2022-01: Lang team update

Summary

  • Work has started on inlining problems/evaluations from issues, gists, etc. See no inference changes, PRs/issues; the no inference changes page is likely mostly complete. Some other pages are also available but in more draft status.

Goals for this month

  • Continue to fill out scenarios, particularly explanations of current feature-gated state and the effects (breakage, expectations for next steps).

Questions for discussion, meeting proposals

  • No particular all-lang questions yet. Current trajectory suggests that we will have a complete-ish set of documents for lang review in 1-2 months, depending on bandwidth. Current expectation is that we have a roughly ready nightly implementation, but more work is needed to document it and the tradeoffs it makes.

📜 {{INITIATIVE_NAME}} Charter

Proposal

Membership

RoleGithub
Ownerghost
Liaisonghost

🔬 Evaluation

The evaluation surveys the various design approaches that are under consideration. It is not required for all initiatives, only those that begin with a problem statement but without a clear picture of the best solution. Often the evaluation will refer to topics in the design-discussions for more detailed consideration.

PRs/Issues

This is intended to give a relatively quick link list to relevant issues/PRs or individual comments, for possible referencing/inclusion elsewhere.

Necessity of fallback changes

Canonical example of inference failure with no-inference-change scenario.


#![allow(unused)]
fn main() {
struct E;

impl From<!> for E {
    fn from(_: !) -> E {
        E
    }
}

#[allow(unreachable_code)]
fn foo(never: !) {
    <E as From<!>>::from(never);  // Ok
    <E as From<_>>::from(never);  // Inference fails here
}
}

Discussion in:

Conditional fallback

See v1 explainer for the details of the core algorithm.

Most of this code is implemented, gated on never_type_fallback, landed in #88149 (primarily refactoring) and #88804 (most of the changes).

Pain point / confusing behavior

  • Closure return types are () even if body !
  • Missing From<!> for T
    • Conflicts with From<T> for <T>
    • After stabilizing !, a crate can add From<!> for MyType preventing a std impl.
  • Uninhabited enums (e.g., for errors)

Miscellaneous

This discusses the impact of just stabilizing ! syntax and changing std::convert::Infallible to be an alias for !. (That is, no inference algorithm changes).

Regression: inference failures

This leads to the regression identified in rust-lang/rust#66757.


#![allow(unused)]
fn main() {
struct E;

impl From<!> for E {
    fn from(_: !) -> E {
        E
    }
}

#[allow(unreachable_code)]
fn foo(never: !) {
    <E as From<!>>::from(never);  // Ok
    <E as From<_>>::from(never);  // Inference fails here
}
}

Without changes to type inference fallback, code such as the above with explicit ! type now fails to compile. This happens because with !, unlike with std::convert::Infallible, ! can coerce to any variable. That means that the coercion from ! to _ succeeds, leading to the inference failure here, as there's no constraint placed on the argument.

The coercion to inference variables is in general desirable, because of code like this:


#![allow(unused)]
fn main() {
if foo {
    loop {}
}
}

if expressions without else currently desugar such that the "block" is typed at an inference variable (later eq'd with ()), so the coercion to an inference variable is necessary to make this work with the current compiler implementation. Further, changing the compiler to avoid this seems relatively hard (FIXME: just how hard?). This regression is prominent enough that it makes fully avoiding inference changes not possible.

Over-eager () fallback

This leads to the painpoint (amongst others) identified in rust-lang/rust#66738. This may also be a regression in some cases if users start more explicitly writing ! in some places, though is not directly one at just stabilization time.

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

fn main() {
    let f2 = magic(|| loop {}) as fn() -> !;
}

The (presumed) expected behavior is that loop {}, having type !, means that the closure above will have a return type of !. However, that's not what actually happens: the closure's return type is set to an inference variable, ?T. Since expressions in the return position are coerced to the return type, we end up with no requirement on the return type's inference variable. (The cast does not participate in inference, generally). This means that the inference variable is unconstrained and so falls back to ().

Note that this behavior is currently relied upon by some libraries. For example, code like this is relatively common, which requires that closures return () or u32. This means that if the fallback doesn't go to (), we will end up with an error.

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

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

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

Take a snippet from warp 0.1.11:


#![allow(unused)]
fn main() {
wr_rx.map_err(|()| {
    unreachable!("mpsc::Receiver doesn't error");
})
.forward(tx.sink_map_err(|_| ()))
.map(|_| ());
}

This code fails if the first closure is typed as impl Fn(()) -> !, because forward requires that !: From<()> (i.e., that the error types are compatible). That impl is not currently available, so this code doesn't work out.

This kind of interaction is relatively common, which makes changes to closure return types that "make sense" at an intuitive level actually commonly result in errors.

Unsizing fails due to eager fallback

See rust-lang/rust#49593.


#![allow(unused)]
fn main() {
fn foo(x: !) -> Box<dyn std::error::Error> {
    Box::new(x)
}
}

This is essentially the same as the previous case, where we have x generate a coercion at the function call site, meaning that we have Box::<?T>::new(...) with no constraints on ?T, which means ?T = () with no fallback changes. Since (): !Error, this fails to compile.

📚 Explainer

The "explainer" is "end-user readable" documentation that explains how to use the feature being deveoped by this initiative. If you want to experiment with the feature, you've come to the right place. Until the feature enters "feature complete" form, the explainer should be considered a work-in-progress.

Never type fallback proposal

This is a proposal for an alternative scheme for never type fallback. This scheme, while not fully backwards compatible, sidesteps the problems we've encountered so far in attempting to stabilize the ! type:

  • Unsound type inference changes from changing fallback, as described in #66173. These problems result from changing the fallback from () to ! for type variables wind up interacting with "live code", resulting in ! values being created.
  • Regressions from having no fallback at all, as described in #67225 and #66757.

Background

The current fallback scheme is based on the concept of "diverging" type variables. In short, a ! type can be coerced to any other type. But when it is inferred to an unknown type ?T (a type variable), the way that we handle it is to create a diverging type variable ?D and unify the two. Once type-checking is complete, we walk over any unbound type variables. If ?D has not yet been unified with any concrete type (it may have been unified or related to other general type variables, but none of those type variables have yet been assigned a type), then it will "fallback" to a specified type. In current Rust, that type is (). The ! type RFC proposed changing that fallback type to ! (as part of introducing the concept of ! as a standalone type). The idea behind this fallback is that since ?D represents the type of an expression that is known to diverge, what actual type it is assigned to doesn't matter, since it can never affect live code. Unfortunately, this premise is false.

Bug 66173: Unsoundness introduced by changing fallback from ! to ()

As described in #66173, we have found in practice that the fallback of diverging type variables can impact the types assigned to live code. The most common problem involves match patterns. Consider the following pattern:


#![allow(unused)]
fn main() {
let x = match something() {
    pattern1 => Default::default(),
    pattern2 => panic!("..."),
};
}

In a case like this, the type of the match is ultimately represented by a type variable ?M. The first arm is assigned a type variable ?T and the second arm (which panics) gets the type !. Both ?T and ! are coerced into ?M:

?T -> ?M
! -> ?M

The first coercion creates a subtyping relationship (?T <: ?M) because the two types are unknown. The second coercion creates a diverging type variable ?D and a subtyping relationship ?D <: ?M.

The problem now is that if ?D falls back to !, then this winds up causing ?M and ?T to both be assigned the type !. In this particular example the result is a compilation error, because Default is not implemented for !, but in other examples the result was unsound execution.

This example prompted us to hold off on changing the fallback from () to !. The result is in some way no less surprising: the type of Default::default winds up falling back to (), rather than (say) requiring an explicit type annotation. However, at least using () didn't produce unsound behavior in previously sound code.

Bug 66757: Regressions introduced by NOT changing fallback

Unfortunately, if we don't change the fallback to !, then we also trigger other sorts of regressions (at least if we want to also redefine the Infallible type in the stdlib). As described in #66757, the fundamental problem is that we have a From<!> impl for any type E, but we don't have a From<()> impl. So when we have code that requires From<?D> where ?D is a diverging type variable, falling back to ! is preferred.

This is related to the fact that ! is in many cases the right fallback! If you have code like Some(return), you would prefer that the type of this expression (if not otherwise constrained) is Option<!>, not Option<()>. In the case of #66757, we had similar code like From::from(never) where never: Infallible. If Infallible is an alias for !, this ought to "fallback" to !.

Proposal: fallback chooses between () and ! based on the coercion graph

So we've seen that changing the fallback from () causes unsoundness, but keeping the fallback as ! can cause failed compilations. The proposal in this PR is to cause the fallback to be more subtle: diverging type variables prefer to fallback to ! but sometimes fallback to () (in cases where they may leak out into live code, in particular).

The idea is based on a "coercion graph". Roughly speaking, each type that an unbound type variable ?A is coerced into another unbound type variable ?B, we create a Coercion(?A -> ?B) relation (instead of immediately falling back to subtyping). At the end of type-checking, we can take any such relations that remain (because neither ?A nor ?B was constrained to another type) and create a graph where an edge ?A -> B indicates that ?A is coerced into ?B. Similarly, we can identify those type variables ?X where we have a coercion ! -> ?X. We call those diverging type variables. Each diverging type variable will either fallback to ! or () depending on the coercion graph:

  • Let D* be the set of type variables that are reachable from a diverging type variable via edges in the coercion graph. These are therefore the variables where the ! type "flows into" them (or would, if it didn't represent the result of a diverging execution).
  • Let N be the set of type variables that are (a) unresolved and (b) not a member of D*.
  • Let N* be the set of type variables that are reachable from N.
  • Each diverging type variable in D will fallback to () if it can reach a variable in N* in the coercion graph, and otherwise fallback to !.

The intuition here is: if there is some group of unconstrained type variables ?X that are all dominated in the coercion graph by the type !, then they fallback to !. If there are type variables in the coercion graph that are the target of a ! coercion but also flow into variable that are the target of other coercions, they fallback to ().

Effect on #66173

Recall the example from #66173:


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

Here we have a coercion graph as follows:

?T -> ?M
! -> ?M
?M -> ?X

In this case, applying the rules above:

  • The set D of diverging variables is [?M]
  • The set D* of variables reachable from D is [?M, ?X]
  • The set N of non-diverging variables is [?T]
  • The set N* of variables reachable from N is [?X, ?X, ?T]
  • Since the diverging variable ?M can reach a variable in N*, it falls back to (), and the unsoundness is averted.

Effect on #66757

Recall this example much like #66757:


#![allow(unused)]
fn main() {
<?R as From<?F>>::from(return)
}

Here we have a coercion graph as follows:

! -> ?F

In particular, the type of the argument is ?F and it is the target of a coercion from ! (the type of the return expression). Since ?F is only reachable from a !, it falls back to ! as desired.

Weird cases

There are some "weird cases" where () fallback can result even in dead code.


#![allow(unused)]
fn main() {
let mut x;
x = return;
x = Default::default();
}

Here, the type ?X of x will have an "incoming edge" from the result of Default::default which will cause it to fallback to (). Seems ok.

Backwards incompatibilies

Changing the fallback from always preferring () to sometimes preferring ! can still cause regressions:

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

Here, the type argument of gimme(return) will fallback to ! and stop compiling.

It can also cause changes in behavior, though that is relatively difficult to engineer. An example might be:

match true {
    true => Cell::new(Default::default()),
    false => Cell::new(return),
}

In this case, the type variable for Default::default is never directly coerced into the type variable for return, so the latter would still fallback to !. In this example that would cause a compilation failure but one could imagine variants, similar to #66173, which would be unsound. (It's worth noting that the lint which @blitzerr and I were experimenting with would detect cases like this, though unfortunately it also detected its fair share of false warnings.)

Future extensions

I would like to deprecate the () fallback. I believe that these cases ought to be hand-annotated and are quite surprising. Consider Example 1 from this github comment:


#![allow(unused)]
fn main() {
parser.unexpected()?;
}

Here the ? desugaring winds up causing this to fall back to (), but I think it should require manual annotation, as removing the ? would require manual annotation. We can consider this separately but this branch should make it possible to do such a transition over an edition, perhaps.

To !

This discusses the semantics for coercion into ! from some expression. Currently, these rules largely come down to coercion to ! being possible "after" an expression with ! type is encountered, such as return or break.

FIXME: It seems like this may have subtle differences as the divergence checking is done on HIR(?) but MIR may end up lowered into a different order -- should write out the rules and check more thoroughly. Relevant code:

  • compiler/rustc_typeck/src/check/fn_ctxt/checks.rs:720 If we have definitely diverged, then a missing tail expression does not force the return type to be () (i.e., the implicit expression is not present).

    
#![allow(unused)]
fn main() {
fn foo() -> u32 {
    return 0;
    // would normally be an error as function returns u32, not (), but accepted.
}
}

FIXME: the above example does not feel obviously related to !, there's probably some more reading and digging to do here.

Examples pulled from src/test/ui/coercion/coerce-to-bang.rs and src/test/ui/coercion/coerce-to-bang-cast.rs.


#![allow(unused)]
fn main() {
fn foo(x: usize, y: !, z: usize) { }

fn call_foo_a() {
    foo(return, 22, 44);
    //~^ ERROR mismatched types
}

fn call_foo_b() {
    // Divergence happens in the argument itself, definitely ok.
    foo(22, return, 44);
}

fn call_foo_c() {
    // This test fails because the divergence happens **after** the
    // coercion to `!`:
    foo(22, 44, return); //~ ERROR mismatched types
}

fn call_foo_d() {
    // This test passes because `a` has type `!`:
    let a: ! = return;
    let b = 22;
    let c = 44;
    foo(a, b, c); // ... and hence a reference to `a` is expected to diverge.
    //~^ ERROR mismatched types
}

fn call_foo_e() {
    // This test probably could pass but we don't *know* that `a`
    // has type `!` so we don't let it work.
    let a = return;
    let b = 22;
    let c = 44;
    foo(a, b, c); //~ ERROR mismatched types
}

fn call_foo_f() {
    // This fn fails because `a` has type `usize`, and hence a
    // reference to is it **not** considered to diverge.
    let a: usize = return;
    let b = 22;
    let c = 44;
    foo(a, b, c); //~ ERROR mismatched types
}

fn array_a() {
    // Return is coerced to `!` just fine, but `22` cannot be.
    let x: [!; 2] = [return, 22]; //~ ERROR mismatched types
}

fn array_b() {
    // Error: divergence has not yet occurred.
    let x: [!; 2] = [22, return]; //~ ERROR mismatched types
}

fn tuple_a() {
    // No divergence at all.
    let x: (usize, !, usize) = (22, 44, 66); //~ ERROR mismatched types
}

fn tuple_b() {
    // Divergence happens before coercion: OK
    let x: (usize, !, usize) = (return, 44, 66);
    //~^ ERROR mismatched types
}

fn tuple_c() {
    // Divergence happens before coercion: OK
    let x: (usize, !, usize) = (22, return, 66);
}

fn tuple_d() {
    // Error: divergence happens too late
    let x: (usize, !, usize) = (22, 44, return); //~ ERROR mismatched types
}

fn cast_a() {
    let y = {return; 22} as !;
    //~^ ERROR non-primitive cast
}

fn cast_b() {
    let y = 22 as !; //~ ERROR non-primitive cast
}
}

See some background/discussion in rust-lang/rust#40800.

From !

Any coercion site with ! as the "from" type always succeeds, with the destination type being the new type. This includes inference variables.

✨ RFC

  • Feature Name: never_type, never_type_fallback
  • Start Date: TBD
  • RFC PR: Past rust-lang/rfcs#1216
  • Rust Issue: TBD

Summary

Promote ! to be a full-fledged type equivalent to an enum with no variants, and adjust default inference fallback to avoid breakage.

Guide level explanation

While empty types exist already in Rust today, for example in the form of enum Foo {}, most Rust users will not be directly familiar with them, so this RFC provides an explanation of the properties these types hold (and that ! will hold).

  • They never exist at runtime, because there is no way to create one.

  • Code that handles them cannot execute, because there is no value that it could execute with. Therefore, having an empty type in scope is a static guarantee that a piece of code will never be run.

  • They represent the return type of functions that don't return. For a function that never returns, such as std::process::exit, the set of all values it may return is the empty set. That is to say, the type of all values it may return is the type of no inhabitants, ie. Never or anything isomorphic to it. Similarly, they are the logical type for expressions that never return to their caller such as break, continue and return.

  • They can be converted to any other type. To specify a function A -> B we need to specify a return value in B for every possible argument in A. For example, an expression that converts bool -> T needs to specify a return value for both possible arguments true and false:

    
#![allow(unused)]
fn main() {
let foo: &'static str = match x {
  true  => "some_value",
  false => "some_other_value",
};
}

    Likewise, an expression to convert () -> T needs to specify one value, the value corresponding to ():

    
#![allow(unused)]
fn main() {
let foo: &'static str = match x {
  ()  => "some_value",
};
}

    And following this pattern, to convert Never -> T we need to specify a T for every possible Never. Of which there are none:

    
#![allow(unused)]
fn main() {
let foo: &'static str = match x { };
}

    Reading this, it may be tempting to ask the question "what is the value of foo then?". Remember that this depends on the value of x. As there are no possible values of x it's a meaningless question and besides, the fact that x has type Never gives us a static guarantee that the match block will never be executed.

Here's some example code that uses Never. This is legal rust code that you can run today.

use std::process::exit;

// Our empty type
enum Never {}

// A diverging function with an ordinary return type
fn wrap_exit() -> Never {
    exit(0);
}

// we can use a `Never` value to diverge without using unsafe code or calling
// any diverging intrinsics
fn diverge_from_never(n: Never) -> ! {
    match n {
    }
}

fn main() {
    let x: Never = wrap_exit();
    // `x` is in scope, everything below here is dead code.

    let y: String = match x {
        // no match cases as `!` is uninhabited
    };

    // we can still use `y` though
    println!("Our string is: {}", y);

    // we can use `x` to diverge
    diverge_from_never(x)
}

This RFC proposes that we allow ! to be used directly, as a type, rather than using Never (or equivalent) in its place. Under this RFC, the above code could more simply be written.

use std::process::exit;

fn main() {
    let x: ! = exit(0);
    // `x` is in scope, everything below here is dead code.

    let y: String = match x {
        // no match cases as `Never` has no variants
    };

    // we can still use `y` though
    println!("Our string is: {}", y);

    // we can use `x` to diverge
    x
}

Motivation

There are several key motivators for adding !, despite the existence of empty types in the language already.

It creates a standard empty type for use throughout Rust code

Empty types are useful for more than just marking functions as diverging. When used in an enum variant they prevent the variant from ever being instantiated. One major use case for this is if a method needs to return a Result<T, E> to satisfy a trait but we know that the method will always succeed.

For example, here's a possible implementation of FromStr for String than currently exists in libstd.


#![allow(unused)]
fn main() {
impl FromStr for String {
    type Err = !;

    fn from_str(s: &str) -> Result<String, !> {
        Ok(String::from(s))
    }
}
}

This result can then be safely unwrapped to a String without using code-smelly things like unreachable!() which often mask bugs in code.


#![allow(unused)]
fn main() {
let r: Result<String, !> = FromStr::from_str("hello");
let s = match r {
    Ok(s)   => s,
    Err(e)  => match e {},
}
}

The Try trait family is written with never type in mind, and currently relies on the enum Infallible {} defined in libcore as a substitute.

Empty types can also be used when someone needs a dummy type to implement a trait. Because ! can be converted to any other type it has a trivial implementation of any trait whose only associated items are non-static methods. The impl simply matches on self for every method.

Example:


#![allow(unused)]
fn main() {
trait ToSocketAddr {
    fn to_socket_addr(&self) -> IoResult<SocketAddr>;
    fn to_socket_addr_all(&self) -> IoResult<Vec<SocketAddr>>;
}

impl ToSocketAddr for ! {
    fn to_socket_addr(&self) -> IoResult<SocketAddr> {
        match self {}
    }

    fn to_socket_addr_all(&self) -> IoResult<Vec<SocketAddr>> {
        match self {}
    }
}
}

All possible implementations of this trait for ! are equivalent. This is because any two functions that take a ! argument and return the same type are equivalent - they return the same result for the same arguments and have the same effects (because they are uncallable).

Suppose someone wants to call fn foo<T: SomeTrait>(arg: Option<T>) with None. They need to choose a type for T so they can pass None::<T> as the argument. However there may be no sensible default type to use for T or, worse, they may not have any types at their disposal that implement SomeTrait. As the user in this case is only using None, a sensible choice for T would be a type such that Option<T> can ony be None, i.e. it would be nice to use !.

While the trait author or user could define their own empty type and implement the trait themselves, it is useful to avoid the hassle of needing to import the appropriate type in order to specify it in cases like this.

Better dead code detection

Consider the following code:


#![allow(unused)]
fn main() {
let t = std::thread::spawn(|| panic!("nope"));
t.join().unwrap();
println!("hello");
}

Under this RFC: the closure body gets typed ! instead of (), the unwrap() gets typed !, and the println! will raise a dead code warning. This requires a canonical empty type to fallback to for the type of expressions like panic!().

To be clear, ! has a meaning in any situation that any other type does. A ! function argument makes a function uncallable, a Vec<!> is a vector that can never contain an element, a ! enum variant makes the variant guaranteed never to occur and so forth. It might seem pointless to use a ! function argument or a Vec<!>, but that's no reason to disallow it. And generic code sometimes requires it.

It's also worth noting that the ! proposed here is not the bottom type that used to exist in Rust in the very early days. Making ! a subtype of all types would greatly complicate things as it would require, for example, Vec<!> be a subtype of Vec<T>. This ! is simply an empty type (albeit one that can be cast to any other type).

Reference-level explanation

Add a new primitive type ! to Rust. ! behaves like an empty enum except that it can be implicitly cast to any other type. For example, code like the following is acceptable:


#![allow(unused)]
fn main() {
let r: Result<i32, !> = Ok(23);
let i = match r {
    Ok(i)   => i,
    Err(e)  => e, // e is cast to i32
}
}

We also adjust the type inference algorithm used by rustc to fallback to ! rather than () when an inference variable ends up unconstrained. This change is motivated by the desire to provide a better experience for Rust users since expressions typed at ! can be coerced into other types. If we avoid making this change, we have to specify that expressions like loop {} and panic!() continue to "return" (), which seems obviously wrong.

Adjusting type inference to fallback to ! also helps set us on a path towards removing some of the fallback and requiring explicit types in the future, as we can be more confident that the code involved is somewhat faulty.

Ensuring soundness

However, this change to fallback is not generally sound in the presence of unsafe code that is present in the wild today. The following is a piece of example code that was previously OK, but with the proposed change has undefined behavior. It's a stripped down example -- the code is already unsound in the sense that unconstrained_return must only be called with valid T, but in practice code like this exists and does not cause UB (as it never gets instantiated with an incorrect T) with today's compiler.


#![allow(unused)]
fn main() {
fn unconstrained_return<T>() -> Result<T, String> {
    let ffi: fn() -> T = std::mem::transmute(some_pointer);
    Ok(ffi())
}

fn foo() {
    let _a = match unconstrained_return::<_>() {
        Ok(a) => a,
        Err(s) => panic!("failed to run"),
    };
}
}

The match here has type ?M and the two arms have types ?T and !, as panic! has type ! with these changes. ?T here is effectively unconstrained, so it falls back to ! with the proposed change to type inference. As a result, unconstrained_return's call to ffi() has a return type of !, which means that the compiler is free to assume that the function does not return. Since ffi() in practice does return, this leads to UB.

So we cannot simply change fallback in all cases.

We propose an algorithm which indicates whether it is safe to fallback to !.

For each inference variable still present during fallback (i.e. those which are unconstrained), we look at the relationships between these inference variables to determine whether to keep the fallback to () or fallback to !.

We construct a directed graph where the vertices are inference variables, and add edges ?A -> ?B if ?A is coerced into ?B.

Let D be the set of type variables ?X which were created as a result of the coercion of ! -> ?X being proposed. These can arise from functions returning ! or loop {} expressions, which can coerce into any type.

For each type variable ?T, we fallback to:

  • ! if the variable is dominated in the graph by the set D (that is, there is no path from a non-diverging type variable to it).
  • () otherwise.

The intuition here is that variables reachable only from diverging type variables must be in dead code, but if they are also reachable from some non-diverging type variable, they may be in live code, and so fallback to ! is unsound.

Avoiding regressions

The proposed graph is sufficient for soundness, but unfortunately is insufficient to avoid a good number of regressions. We add an additional heuristic that mitigates most of the remaining breakage (~100 crates per Crater), leaving ~25 regressions.

This heuristic adds another case of fallback of ?T to () when we encounter the following:

  • ?T: Foo and
  • Bar::Baz = ?T and
  • (): Foo

This pattern is commonly encountered in code which constrains the return type of some closure, and where closure instances frequently contain panic!(). With the previously proposed fallback, there is no additional constraint on ?T (it's not flowing into any other inference variables), so it is reasonable for it to fallback to !. However, in practice, that causes breakage, as the closure's return type is restricted to Bar, which is only implemented for () (and u32).

// Crate A:
pub trait Bar { }
impl Bar for () {  }
impl Bar for u32 {  }

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

// Crate B:
fn main() {
    foo(|| panic!());
}

Alternatives

Leave Infallible as the standard empty type

We could abandon the effort to stabilize ! as a dedicated return type, instead leaving the currently existing Infallible as the standard empty type. There are several downsides to this:

  • Users need to learn two different canonical names (! if standalone in a function return types and Infallible for other places)
  • Infallible is either special-cased to coerce to other types or users need to write match foo {} to get that behavior.

Edition-based fallback?

We considered whether the fallback algorithm could be adjusted over an edition boundary to permit stabilizing never type. In practice, this doesn't work because the never type is a vocabulary type and so is present in the public API of various crates (including core/std, after stabilization).

This means that while the fallback within a library might be edition-dependent, we'd still need to stabilize full use of ! across all editions. That basically puts prior editions on the same grounds as just stabilizing !, which is known to introduce regressions.

Generally it seems pretty clear that stabilizing never type (or fallback changes) only on a subset of editions would lead to a more challenging landscape for Rust users. For example, as we've seen, fallback has implications for soundness, so we'd still need all of the complexity in the fallback algorithm in order to prevent cases like the one described above -- this seems to just make things more complicated, rather than improving them.

Future work

Removing (parts of) fallback

We can consider removing some of the cases of fallback, particularly those which cause problems for this RFC, in the future. There were several examples encountered in Crater and elsewhere that required effort to deduce the inferred type. Additionally, we believe that it's likely that cases of fallback to () in new code are likely better written in other ways and we may wish to force the user to indicate a type rather than silently providing one that may cause trouble or hurt diagnostic quality.

We can leverage editions to remove parts of fallback. Unlike the phase-in of never type fallback, removing fallback only prevents code from compiling and does not change the behavior of existing code. This is fairly standard for cross-edition changes, and so is much more straightforward to design.

However, this RFC does not propose a particular path towards removing/improving our fallback algorithms, beyond noting that it may be advantageous to do so. If we do so, we can likely end up avoiding the more complex fallback algorithm proposed by this RFC being a permanent feature of future Rust editions.

Special casing trait impls for !

! is useful as a standard marker inside types which may derive various traits. Implementing a trait for ! is frequently fairly annoying, as you need to write out many functions which are largely inconsequential as they can never run (if they have a self parameter).

For now, the expectation is that library authors will want to add manual impls for standard traits (including in the standard library), but a future extension could let users write (potentially) overlapping trait impls for ! so long as the body of the trait is "obviously equivalent" as the methods can't be called.

Unresolved questions

  • Pending (needs review of the above)

😕 Frequently asked questions

This page lists frequently asked questions about the design. It often redirects to the other pages on the site.

What is the goal of this initiative?

See the Charter.

Who is working on it!

See the Charter.