Fallback and never types

tags: rustc, never-type, bug

Summary

Solution

  • Step 1
    • Add a lint. This is tracked by 66173

Background

RFC 1216 - Introduces the bang type or empty type.

An empty type is something that never exists in the runtime as there is no way to create one and therefore, such type in code gives us a static gurantee that a piece of code will never be executed.



















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
}

Why a new type.

  • Gives us a way to use diverging functions in generic types.

What is a divergent type

An HIR node is divergent if it does not exit normally, instead it returns / breaks / panics leaving behind dead code.

In rustc, this is tracked using the enum Diverges.
There are different variants of it:

  1. Maybe - Some of the cases diverge, while others require further analysis to determine.
  2. Always - Certainly known to diverge, so next sibling and parent are unreachable.
  3. WarnedAlways - Same as Always with a reachability warning always emitted.

Further explanations given by Niko:

So, what would a never returning node result in ?
Ans: ! type.

Similarly, ! is also a type that can be assigned. Therefore, sometimes the compiler creates an inference variable ?X to represent the type to which ! is being coersed.

e.g.

let x: u32 = return ...

will type-check, because the type of return will be ?X
and ?X = u32 is a valid result.

The problem

The problem is that we generally require all inference variables to have a defined value.

Which is why let x = None won't type-check on its own and would require Option<?T>.
What is ?T ?
Ans: Its a constraint.

But it would be annoying if we required to constrain the divergent variables as it should not matter what ! is coersed to.

Therefore,

let x = return 22;

shouldn't fail compilation if we can't figure out the type of x. Therefore, today, we assign ?X as the type of x and at the end of type-checking, when we still couldn't resolve ?X, we fallback to () as the type of x.

The solution

The fallback type in this case should be ! instead of ().
We start out by detecting cases where that's a problem.

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.
    };
}

Walk through what goes wrong:

  • the type parameter T gets specified as _ – _ means "make fresh inference variable", let's call it ?X
  • type of unconstrained_return::<?X>() is Result<?X, String>
  • type of x in Ok(x) is ?X
    • type of the match arm Ok(x) => x is ?X
  • type of s in Err(s) is String
    • type of the match arm Err(s) => panic!(s) is !
    • because the type of the expression is ! we create a fresh variable ?V
      • and we mark ?V as diverging
  • the two match arms have to have the same type
    • more specifically, there must be some type M such that both match arms can be coerced to that type M
      • create a inference variable ?M where ?X can be coerced to ?M
      • and ?V can be coerced to ?M
    • effectively we unify ?X = ?V = ?M
  • at the end, ?X and ?V are both unconstrained
    • no fallback for ?X
    • ?V falls back to !, so effectively ?V becomes !
    • because ?X is unified, it becomes !

Where is this implemented?

  • link
  • fallback_if_possible
  • my commit tweaks this to compute "tainted" types by
    • save the variables before we apply fallback
    • apply fallback, solve trait obligations
    • then check those variables again to see which became !

Slightly bigger than the set of unified variables

fn foo<T, U>() where T: Eq<U> { }
trait Eq<A> { }
impl Eq<!> for ! { }

Path to solution

  • Niko's initial PR to add a lint
    • Key Idea in the PR: warn whenever the type of any expression is changed as a result of diverging fallback.
      • identify type variables that that got their value as a result of diverging fallback
      • warn when we find those type of variables in "certain contexts"
    • What we actually want ?
      • warn whenever the type of a live expression is changed as the result of diverging fallback.

Niko's suggestion for solution

  1. mark dead nodes: HIR_ID for expressions where flag was set to warnedAlways on entry.
    2. warn_if_unreachable
    3. probably add the hir_id to some set roughly on this line if self.diverges() is set to WarnedAlways
  2. Issues a warning if:
    1. the type of a HIR_ID contains a type variable whose value is set by divergent fallback
      AND
    2. The expression is not in the set of dead nodes (i.e. it maybe live).

Example of case where we would NOT issue a warning but is still UB:

// the bet is that an unconstrained return value like `T` here signals data
// that is never used, e.g. this fn could return `Ok(())`, but in this case
// that is not true:
fn unconstrained_return<T>() -> Result<(), T> {
    let ffi: fn() -> T = transmute(some_pointer);
    ffi(); // produces a value of type T
}

fn foo() {
    match unconstrained_return::<_>() { // _ is ?X
        Ok(_) => Ok(()), // type of `Ok` is `Result<(), ?A>`
        Err(s) => Err(panic!(s)), // type of `Err(_)` is `Result<?B, ?V>` where `?V` is diverging
    }; // type of expression is `Result<(), ?V>`
}

Progress

Select a repo