# Fallback and never types

###### tags: `rustc`, `never-type`, `bug`

## Summary
- My work-item: Regression from fallback to `()` [67225](https://github.com/rust-lang/rust/issues/67225)
- [Mentoring notes](https://github.com/rust-lang/rust/issues/66173#issuecomment-606836855)
- The Umbrella tracking Issue: [35121](https://github.com/rust-lang/rust/issues/35121)

## Solution
- Step 1
- Add a lint. This is tracked by [66173](https://github.com/rust-lang/rust/issues/66173#issuecomment-606836855)

## Background

### [RFC 1216](https://github.com/rust-lang/rfcs/blob/master/text/1216-bang-type.md) - 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 _`return`s / `break`s / `panic`s_ leaving behind dead code.

In rustc, this is tracked using the enum [Diverges](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_typeck/check/enum.Diverges.html).
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](https://github.com/nikomatsakis/rust/blob/cacda2d7a0d43c6038329e980b8ab339dd0ab9af/src/librustc_typeck/check/mod.rs#L1060)
* [`fallback_if_possible`](https://github.com/nikomatsakis/rust/blob/cacda2d7a0d43c6038329e980b8ab339dd0ab9af/src/librustc_typeck/check/mod.rs#L3316)
* my [commit](https://github.com/nikomatsakis/rust/commit/e3a96450d501bc72f876945aadbd05307a9570c9) 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](https://github.com/nikomatsakis/rust/commit/e3a96450d501bc72f876945aadbd05307a9570c9) 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`](https://github.com/nikomatsakis/rust/blob/e3a96450d501bc72f876945aadbd05307a9570c9/src/librustc_typeck/check/mod.rs#L2779)
3. probably add the `hir_id` to some set [roughly on this line](https://github.com/nikomatsakis/rust/blob/e3a96450d501bc72f876945aadbd05307a9570c9/src/librustc_typeck/check/mod.rs#L2805) if `self.diverges()` is set to `WarnedAlways`
3. 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

- [Initial WIP PR](https://github.com/rust-lang/rust/pull/74535)
- [This UT](src/test/ui/never_type/never-value-fallback-issue-66757.rs) can be used as reference.
-