Tracking issue for promoting `!` to a type (RFC 1216)

[nikomatsakis]

Tracking issue for rust-lang/rfcs#1216, which promotes ! to a type.

About tracking issues

Tracking issues are used to record the overall progress of implementation. They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions. A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature. Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Pending issues to resolve

• [ ] Regressions from fallback to () https://github.com/rust-lang/rust/issues/67225
• [ ] How to handle fallback of diverging expressions https://github.com/rust-lang/rust/issues/65992

Interesting events and links

• Initial PR #35162
• Stabilization PR https://github.com/rust-lang/rust/pull/65355
• Reverting stabilization https://github.com/rust-lang/rust/pull/67224 due to regressions https://github.com/rust-lang/rust/issues/66757

[canndrew]

Huzzah!

There's a WIP implementation of this here: https://github.com/canndrew/rust/tree/bang_type_coerced

It's current status is: it builds with old-trans and is usable but has a couple of failing tests. Some tests fail due to a bug that causes code like if (return) {} to crash during trans. The other tests are to do with link-time-optimization and have always been buggy for me, so I don't know if they have anything to do with my changes.

My current roadmap is:

• Get it working with MIR. This hopefully won't be too hard as this is how I started implementing it, but I've been having a problem where MIR builds segfault during compilation.
• Purge the obsolete divergence stuff from the compiler (FnOutput, FnDiverging and related).
• Hide the new type behind a feature gate. This would mean, when the feature is disabled:
  • ! can only be parsed as a type in the return position.
  • Diverging type variables default to ().
• Figure out how we can raise compatibility warnings when a defaulted () gets used to resolve a trait. One way to do this could be to add a new type to the AST called DefaultedUnit. This type behaves like () and will turn into () under some circumstances but raises a warning when it resolves a trait (as ()). The problem with this approach is I think it will be hard to catch and fix all the bugs with the implementation - we'd end up breaking people's code in order to save their code from being broken.

Is there anything that needs to be added to this list? Is it just going to be me working on this? And should this branch be moved onto the main repository?

[canndrew]

Figure out how we can raise compatibility warnings when a defaulted () gets used to resolve a trait. One way to do this could be to add a new type to the AST called DefaultedUnit. This type behaves like () and will turn into () under some circumstances but raises a warning when it resolves a trait (as ()). The problem with this approach is I think it will be hard to catch and fix all the bugs with the implementation - we'd end up breaking people's code in order to save their code from being broken.

@eddyb, @arielb1, @anyone_else: Thoughts on this approach? I'm pretty much up to this stage (sans a couple of failing tests that I'm (very slowly) trying to fix).

[tomaka]

What traits should we implement for !? The initial PR #35162 includes Ord and a few others.

Shouldn't ! automatically implement all traits?

This kind of code is fairly common:

trait Baz { ... }

trait Foo {
    type Bar: Baz;

    fn do_something(&self) -> Self::Bar;
}

I'd expect ! to be usable for Foo::Bar in order to indicate that a Bar can never actually exist:

impl Foo for MyStruct {
    type Bar = !;
    fn do_something(&self) -> ! { panic!() }
}

But this is only possible if ! implements all traits.

[suhr]

@tomaka There's RFC about it: https://github.com/rust-lang/rfcs/pull/1637

The problem is that if ! implements Trait it also should implement !Trait...

[tomaka]

The problem is that if ! implements Trait it also should implement !Trait...

Then special-case ! so that it ignores any trait requirement?

[canndrew]

@tomaka ! can't automatically implement all traits because traits can have static methods and associated types/consts. It can automatically implement traits that just have non-static methods though (ie. methods that take a Self).

As for !Trait, someone suggested that ! could auto-implement both Trait and !Trait. I'm not sure whether that's sound but I suspect that negative traits aren't sound at all.

[canndrew]

But yes, it might be nice if ! could auto-implement Baz in the example you gave for precisely these sorts of cases.

[canndrew]

When exactly do we default diverging type variables to ()/! and when do we throw an error about not being able to infer enough type information? Is this specified anywhere? I'd like to be able to compile the following code:

let Ok(x) = Ok("hello");

But the first error I get is "unable to infer enough type information about _". In this case I think it would make sense for _ to default to !. However when I was writing tests around defaulting behaviour I found it surprisingly difficult to make a type variable default. That's why these tests are so convoluted.

I'd like to have a clear idea of exactly why we have this defaulting behaviour and when it's supposed to get invoked.

[tomaka]

But the first error I get is "unable to infer enough type information about ". In this case I think it would make sense for to default to !. However when I was writing tests around defaulting behaviour I found it surprisingly difficult to make a type variable default. That's why these tests are so convoluted.

That's a very good idea in my opinion. Same for None which would default to Option<!> for example.

[arielb1]

@carllerche

The unit_fallback test is certainly an odd way to demonstrate it. A less-macro-ey version is

trait Balls: Default {}
impl Balls for () {}

struct Flah;

impl Flah {
    fn flah<T: Balls>(&self) -> T {
        Default::default()
    }
}

fn doit(cond: bool) {
    let _ = if cond {
        Flah.flah()
    } else {
        return
    };
}

fn main() {
    let _ = doit(true);
}

Only the type variable created by return/break/panic!() defaults to anything.

[nikomatsakis]

When exactly do we default diverging type variables to ()/! and when do we throw an error about not being able to infer enough type information? Is this specified anywhere?

Define "specified". :) The answer is that certain operations, which are not afaik written down anywhere outside the code, require that the type is known at that point. The most common case is field access (.f) and method dispatch (.f()), but another example is deref (*x), and there is probably one or two more. There are mostly decent reasons for this being required -- generally speaking, there are multiple diverging ways to proceed, and we can't make progress without knowing which one to take. (It would be possible, potentially, to refactor the code so that this need can be registered as a kind of "pending obligation", but it's complicated to do so.)

If you make it all the way to the end of the fn, then we run all pending trait selection operations until a steady state is reached. This is the point where defaults (e.g., i32, etc) are applied. This last part is described in the RFC talking about user-specified default type parameters (though that RFC in general needs work).

[canndrew]

https://github.com/rust-lang/rust/issues/36011 https://github.com/rust-lang/rust/issues/36038 https://github.com/rust-lang/rust/issues/35940

Are some bugs to add to the list of pending issues.

[glaebhoerl]

@canndrew those look a bit similar to https://github.com/rust-lang/rust/issues/12609

[canndrew]

Boy, that's an old bug! But yes I'd say my #36038 is a dupe of that (I thought I'd seen it somewhere before). I don't think ! can really be considered for prime time until that's fixed.

[tikue]

Is it planned for ! to affect pattern matching exhaustiveness? Example of current, possibly-wrong behavior:

#![feature(never_type)]

fn main() {
    let result: Result<_, !> = Ok(1);
    match result {
//        ^^^^^^ pattern `Err(_)` not covered
        Ok(i) => println!("{}", i),
    }
}

[lambda-fairy]

@tikue yes, it's one of the bugs listed above.

[tikue]

@lfairy whoops, didn't see it because it wasn't listed in the checkboxes at the top. Thanks!

[cramertj]

Are there plans to implement From<!> for T and Add<T> for ! (with an output type of !)? I know that's a really oddly specific request-- I'm trying to use both in this PR.

[canndrew]

From<!> for T definitely. Add<T> for ! is probably up for the libs team to decide but I personally think ! should implement every trait that it has a logical, canonical implementation for.

[cramertj]

@canndrew Thanks! I'm used to scala's Nothing trait which is a subtype of every type, and can thus be used pretty much anywhere a value can appear. However, I definitely sympathize with the desire to understand the effects that impl All for ! or similar would have on rust's type system, especially concerning negative trait bounds and the like.

[glaebhoerl]

Per https://github.com/rust-lang/rfcs/issues/1723#issuecomment-241595070 From<!> for T has coherence issues.

[canndrew]

Ah right, yes. We need to do something about that.

It would be good if trait impls could explicitly state that they are overriden by other trait impls. Something like:

impl<T> From<T> for T
    overridden_by<T> From<!> for T
{ ... }

impl<T> From<!> for T { ... }

[cramertj]

Isn't this covered by specialization? Edit: I believe this is the lattice impl rule.

[petrochenkov]

Is it a viable alternative to avoid special support for uninhabited types as much as possible?

All these match (res: Res<A, !>) { Ok(a) /* No Err */ }, special methods for Result look very contrived, like features for the sake of features, and doesn't seem to worth the effort and complexity. I understand ! is a @canndrew's pet feature and he wants to develop it further, but maybe it's a wrong direction to go from the start and #12609 is not even a bug?

[cramertj]

@petrochenkov #12609 isn't a special feature for the Never type. It's just a bug fix to detect some clearly unreachable code.

[canndrew]

@petrochenkov Forget ! and just look at enums.

If I have an enum with two variants I can match on it with two cases:

enum Foo {
    Flim,
    Flam,
}

let foo: Foo = ...;
match foo {
    Foo::Flim => ...,
    Foo::Flam => ...,
}

This works for any n, not just two. So if I have an enum with zero variants I can match on it with zero cases.

enum Void {
}

let void: Void = ...;
match void {
}

So far so good. But look what happens we try to match on nested patterns. Here's matching on a two-variant enum inside a Result.

enum Foo {
    Flim,
    Flam,
}

let result_foo: Result<T, Foo> = ...;
match result_foo {
    Ok(t) => ...,
    Err(Flim) => ...,
    Err(Flam) => ...,
}

We can expand the inner pattern inside the outer one. There are two Foo variants, so there are two cases for Err. We don't need separate match statements to match on the Result and on the Foo. This works for enums with any number of variants... except zero.

enum Void {
}

let result_void: Result<T, Void> = ...;
match result_void {
    Ok(t) => ...,
    // ERROR!
}

Why shouldn't this work? I wouldn't call fixing this adding "special support" for uninhabited types, I'd call it fixing an inconsistency.

[canndrew]

@petrochenkov Maybe I misunderstood what you were saying. There's two questions discussed in the #12609 thread:

(0) Should this code be allowed to compile?

let res: Result<u32, !> = ...;
match res {
    Ok(x) => ...,
}

(1) Should this code be allowed to compile?

let res: Result<u32, !> = ...;
match res {
    Ok(x) => ...,
    Err(_) => ...,
}

As currently implemented, the answers are "no" and "yes" respectively. #12609 talks about (1) specifically in the issue itself but I was thinking of (0) when I replied. As for what the answers should be, I think (0) should definitely be "yes" but for (1) I'm not sure either.

[petrochenkov]

@canndrew It may be reasonable to make (1), i.e. unreachable patterns, a lint and not a hard error regardless of uninhabited types, RFC 1445 contains more examples of why this can be useful.

Regarding (0) I'm more or less convinced by your explanation. I'll be totally happy if this scheme lies naturally on the pattern checking implementation in the compiler and removes more special code than adds.

[canndrew]

By the way, I've done a PR to try and fix (0) here: https://github.com/rust-lang/rust/pull/36476

I'll be totally happy if this scheme lies naturally on the pattern checking implementation in the compiler and removes more special code than adds.

It doesn't, wierdly. But that's probably more an artefact of the way I hacked it into the existing code rather than there not being an elegant way to do it.

[tikue]

I think for macros it's useful for (1) to not be a hard error.

[SimonSapin]

I think (1) should compile by default but give a warning from the same lint as here:

fn a() -> u32 {
    return 4;
    5
}

warning: unreachable expression, #[warn(unreachable_code)] on by default

[taralx]

While we're at it, does it make sense to make some patterns irrefutable in the face of !?

let res: Result<u32, !> = ...;
let Ok(value) = res;

[glaebhoerl]

I agree that making non-exhaustive matches an error, but unreachable i.e. redundant patterns just a warning seems to make sense.

[canndrew]

I've had some PRs sitting around for a while gathering rot. Is there anything I can do to help get these reviewed? There probably needs to be some discussion on them. I'm talking about #36476, #36449 and #36489.

[earthengine]

I against the idea of thinking the divergent type (or "bottom" type in type theory) is the same as the empty enum type (or "zero" type in type theory). They are different creatures, although both cannot have any value or instance.

In my opinion, a bottom type can only appear in any context that represents a return type. For example,

fn(A,B)->!
fn(A,fn(B,C)->!)->!

But you should not say

let g:! = panic!("whatever");

or

fn(x:!) -> !{
     x
}

or even

type ID=fn(!)->!;

as no variables should have type !, and so no input variables should have type !.

Empty enum is different in this case, you can say

enum Empty {}

impl Empty {
    fn new() -> Empty {
         panic!("empty");
    }
}

then

 match Empty::new() {}

This is to say, there is a fundamental difference between ! and Empty: you cannot declare any variable to have type ! but can do so for Empty.

[RalfJung]

@earthengine What is the advantage of introducing this (in my eyes completely artificial) distinction between two kinds of uninhabitable types?

Numerous reasons for not having such a distinction have been brought up - for example, being able to write Result<!, E>, have this interact nicely with divergent functions, while still being able to use the monadic operations on Result, like map and map_err.

In functional programming, the empty type (zero) is frequently used to encode the fact that a function does not return or that a value does not exist. When you say bottom type, it's not clear to me which concept of type theory you are referring to; usually bottom is the name for a type that's a subtype of all types -- but in that sense, neither ! not an empty enum are bottom in Rust. But again, zero not being a bottom type is not uncommon in type theory.

[canndrew]

This is to say, there is a fundamental difference between ! and Empty: you cannot declare any variable to have type ! but can do so for Empty.

That's what this RFC is fixing. ! is not really a "type" if you can't use it like a type.

[earthengine]

@RalfJung Those concepts are from linear logic https://en.wikipedia.org/wiki/Linear_logic

As there is some mistakes in the previous text in this post, I removed them. Once I get it right will update this.

[eddyb]

top is a value can be used in any possible ways

What does this mean in subtyping? That it can become any type? Because that's bottom then.

[earthengine]

@eddyb I made some mistakes, please wait for my new updates.

[canndrew]

This PR - which got merged in a day - conflicts pretty badly with my pattern matching PR which has been sitting in review for over a month. Sorry, my second pattern matching PR since the first one became unmergeable and had to be rewritten after it sat in review for two months.

ffs guys

[nikomatsakis]

@canndrew argh, I'm sorry about that. =( I was planning on r+'ing your PR today, too...

[canndrew]

Sorry, I don't want to whine but this has hella been dragging on. I gave up on trying to maintain multiple PRs at once and now I've been trying to get this one change in since September. I think part of the problem is the timezone difference - you lot are all online while I'm in bed so it's hard to chat about this stuff.

[tupshin]

Given that exceptions are a logical and necessary hole in the type system, I was wondering if anybody has given serious thoughts to moving towards more formally handling them with !.

Using https://is.gd/4EC1Dk as an example and reference point, what if we went past that, and.

1) Treat any function that can panic but doesn't return an error or result have it's type signature implicitly change from -> Foo to -> Result<Foo,!> 2) anyResult<Foo,MyErr>types would have their Error types implicitly be converted toenum AnonMyErrWrapper { Die(!),Error}``` 3) Since ! is zero sized ad unhinhabitable, There would be zero cost to converting between the types, and implicit conversion could be added to make it backwards compatible.

The benefit, of course, being that exceptions are effectively lifted into the type system, and it would be possible to reason about them, perform static analysis on them, etc.

I realize that this would be ...non-trivial from a community point of view, if not from a technical one. :)

Also, this probably overlaps with a possible future effects system.

[Ericson2314]

@tupshin that's a breaking change, at least without a lot of gymnastics. I recommend disabling unwinding and using "Result" manually if you want that clarity. [And btw, this issue isn't really the place to bring up such a thing---the design of ! is not something you are calling into question so this is purely future work.]

[tupshin]

I realize how breaking it would be, at least without significant gymnastics, and fair point about it being totally future work. And yes, I'm quite happy with what is planned for ! so far, as far as it goes. :)

[canndrew]

@nikomatsakis Regarding the pending issues, these two can be ticked off

• Code cleanup from #35162, re-organize typeck a bit to thread types through return position instead of calling expr_ty
• Resolve treatment of uninhabited types in matches

I'm going to start another crack at this one:

• How to implement warnings for people relying on (): Trait fallback where that behavior might change in the future?

I'm planning on adding a flag to TyTuple to indicate that it was created by defaulting a diverging type variable, then checking for that flag in trait selection.

[nikomatsakis]

@canndrew

I'm planning on adding a flag to TyTuple to indicate that it was created by defaulting a diverging type variable, then checking for that flag in trait selection.

OK, great!

[nikomatsakis]

Well, maybe great. =) Sounds a bit complex to have two semantically equivalent types (() vs ()) that are distinct in that way, but I can't think of a better way. =( And a lot of the code ought to be prepared for it anyhow thanks to regions.

[canndrew]

What I mean is I'm adding a bool to TyTuple

TyTuple(&'tcx Slice<Ty<'tcx>>, bool),

which indicates that we should raise warnings on this (unit) tuple if we try to select certain traits on it. This is safer than my original approach of adding another TyDefaultedUnit.

Hopefully we only need to keep that bool around for one warning cycle.