Should ! be a type?


#1

The issue that ! is not a type comes up in the new closure traits: Fn() -> ! is not valid.

I believe that ! should be treated like an enum Void {} (which cannot be constructed). We should also add coercions Void -> T that defaults to ().


#2

Possibly, but to prevent weirdness, it should probably be done using something like:

trait Fn<Result: ?NotBottom, Args> {
    fn call(&self, args: Args) -> Result;
}

Like with Sized, every generic parameter gets an implicit NotBottom bound that has to be explicitly switched off. This prevents situations like Vec<!> which what is that I don’t even.

One possible problem would be in generic code like-a so:

fn trace<F, R: ?NotBottom>(blk: F) -> R where F: FnOnce() -> R {
    println!("before");
    let r = blk();
    println!("after");
    r
}

Now, what should happen if R is !? Should this be forbidden? Should variables of type ! be allowed on the basis that it’s impossible to create them anyway, and any assignment to one represents a dead code path?


#3

Conceptually ! is for<T> T (or forall a. a in Haskellese). I don’t know if Rust’s type system / rustc would be up to the challenge of representing it that way. (Impredicative types and so on… we do already have higher-rank lifetimes.)

I think size_of::<!>() could just be 0 on the “it cannot exist” basis. (In fact, it could even be “infectious” and cause structures it’s contained in (in positive position, at least) to also be that way - e.g. size_of::<(i32, i32, !)>() == 0 as well. And size_of::<Result<T, !>>() == size_of::<T>(). I’m not sure what the ramifications and complications would be of pursuing this idea.)


#4

The difference is that ! coerces to () by default, but something similar to for<T> T doesn’t. (such as calling a fn foo<T>() -> T)

In haskell, the fact that there is no distinction between a value and a function without parameters somewhat simplifies matters.


#5

I like your approach with NotBottom.

As for variables, we can have a lint for ones that are unconditionally bottom.


#6

What’s the problem with that today?

You can pass a closure that doesn’t return: E.g. let || -> () { panic!() }


#7

! doesn’t coerce, it defaults to (). And so would fn foo<T = ()>() -> T whenever the accepted fallback rules are implemented (@nikomatsakis knows more).


#8

The problem is that ! and () mean different things. Specifically, a ! function never returns at all. Even if it unconditionally panics, a closure whose type says that it returns () will be assumed to return at least some of the time by the compiler. As such, you’d need to do something like {never_returns(); panic!("boom!")} to get the same behaviour in the caller.

I don’t think it’s a huge hole, but it’s a hole none the less.

I’ve also decided that if you have blk: F where F: FnOnce() -> R, R: ?NotBottom, the compiler should assume that blk never returns, and it must be at the end of control flow. You also shouldn’t be able to have variables or fields of type ! because that would imply that code after a diverging call is valid, which it shouldn’t be.

Edit: I’d like to see negative trait bounds added at some point, so what if every generic type parameter gets an implicit !Bottom bound, which can be overridden with ?Bottom. Bottom by itself would be possible, but relatively useless (the only type that implements Bottom would be !). So, the full defaults would be Sized + !Bottom.


#9

@eddyb

  • By “coerce”, I meant that ! can be coerced to T for any type T, but it is () if type inference cannot determine the exact type of T
  • What are the “accepted fallback rules”? Is there an RFC?

#10

I think that R: ?NotBottom should mean that R might either be ! or not be !, meaning that F: FnOnce() -> R, R: ?NotBottom might possibly not return.

If you want to state that a closure never returns, you would have to write F: FnOnce() -> !, which is currently invalid.


#11

Yes, that’s the idea. ! doesn’t make sense in most contexts, so you have to specify that you want to allow ! in that position. However, for a generic type R: ?NotBottom, the compiler can’t know whether or not R will be !, thus it must assume that it is, since that’s the common denominator. Remember that Fn* are traits, thus whatever is done to enable ! for closures has to be something that can be written in user code.


#12

FYI, I’ve filed an issue about ! a while ago:


#13

Why does the empty type need special syntax and semantics? Can’t we just add enum Empty {} to the standard library (calling it Void will confuse C programmers)? The following code compiles fine:

fn foo() -> Empty {
    panic!("aah!")
}

As does the following code if you need a way to convert Emptys to another type:

impl Empty {
    fn convert_to<T>(self) -> T {
        match self {
        }
    }
}

Empty can be used in closure traits the same as any other type. I don’t understand the need for the NotBottom trait.

This prevents situations like Vec<!> which what is that I don’t even.

It’s a Vec<Empty>, ie. a Vec that guaranteed to contain zero elements. Code using Vec<Empty> compiles fine and does what it should.

Should variables of type ! be allowed on the basis that it’s impossible to create them anyway, and any assignment to one represents a dead code path?

Yes.

I think size_of::<!>() could just be 0 on the “it cannot exist” basis. (In fact, it could even be “infectious” and cause structures it’s contained in (in positive position, at least) to also be that way - e.g. size_of::<(i32, i32, !)>() == 0 as well.

Conceptually, sizeof(Empty) is negative infinity. As negative infinity isn’t a valid usize, Empty shouldn’t implement Sized nor should any struct containing Empty. Edit: On second thought, not having empty types implement Sized means they can’t be used as function arguments or in the middle of structs. Really we need to split Sized into two traits: one that means “size known at compile time” and another, stricter trait that means “size known at compile time and isn’t negative infinity”. Perhaps NotBottom is useful. You’d have NotBottom : Sized and size_of<T: NotBottom>. Function argument types, function return types and struct member types would only be restricted to being Sized. structs would implement NotBottom if all their members do and enums if any of their members do.


#14

Your idea has a few problems

  • .convert_to() is unergonomic. You also have to use it as .convert_to<Foo>() every time.
  • A function cannot return a non-Sized type.

#15

.convert_to() is unergonomic. You also have to use it as .convert_to<Foo>() every time.

Call it something smaller like elim. And you don’t need to put the type in if it can be inferred. This program compiles and runs:

enum Empty {}

impl Empty {
  fn elim<T>(self) -> T {
    match self {
    }
  }
}

fn do_panic() -> Empty {
  panic!("aah!")
}

fn return_an_int_or_panic(b: bool) -> i32 {
  if b {
    123i32
  }
  else {
    do_panic().elim()
  }
}

fn main() {
  println!("{}", return_an_int_or_panic(true));
  println!("{}", return_an_int_or_panic(false));
}

A function cannot return a non-Sized type.

True, I edited my idea to suggest that Empty should in fact be Sized.


#16

I would really like a standard Empty type. I’ve opened an issue on rfcs about this.

https://github.com/rust-lang/rfcs/issues/1001


#17

! currently only represents an unreachable point in control flow, but if it were a proper type it could potentially represent an unreachable enum variant as well. A small tweak could be made to the language to make enum literals for generic enums where not all generics can be inferred to have the type ! for all un-inferrable generics (e.g., an expression such as Ok(1) would have the type Result<i32, !> by default, which could then be coerced into Result<i32, T> for any T). As an example of what this would allow, the following code would be valid:

let x: Result<i32, !> = Ok(1);
let y: Result<i32, i32> = x;

The existing coercion forall T. ! => T would have to be transitively extended through enums and structs for this to work, which could be a little difficult to define and might make it too easy to create breaking changes in libraries.

This coercion can be modeled today in @canndrew’s system:

// ...insert code defining Empty from above here...

// this code hasn't been tested so might not be quite right

let x: Result<i32, Empty> = Ok (1);
let y: Result<i32, i32> = x.map_err(|x| x.elim());

Although that is pretty unergonomic.

The more I think about this, the more I realise how much of this applies to all uninhabited types; e.g., @glaebhoerl’s comment about the infectious sizing of ! could apply to all uninhabited types. Maybe we should remove ! like @canndrew proposes, but instead of adding elim, just add a new coercion from any uninhabited type to any other type (effectively letting any uninhabited type behave like today’s !).


#18

@P1start fwiw you can already do all of this today with std::intrinsics::unreachable(), cf. rust-void. (Also posted void on the RFC as an existing related crates.io lib.)


#19

FYI: Here was the PR that made ! not a type: https://github.com/rust-lang/rust/pull/17603

BTW I have changed my mind about this because I have previously underestimated the complexity of this change. I now think that the complexity of this change is not worth it.

Example of edge cases:

  • &! must be a subtype of &T
  • Fn() -> ! must be a subtype of Fn() -> T
  • Fn(T) must be a subtype of Fn(!)