Stabilizing Rust's Never Type
lwn.net154 points by cjd8 4 days ago
154 points by cjd8 4 days ago
> For many years, the standard library has had an `Infallible` type to work around the unstable nature of the never type. It served the same semantic purpose as the never type, but did not have any special compiler support. Therefore, code using it would be technically correct but suboptimal (such as having an extra layer of tags in an enumeration or emitting dead code), because the optimizer would not always be able to remove references to `Infallible`.
This is incorrect. The compiler has always treated `Infallible` as uninhabited, and used that fact for optimizations. The downside of its lack of compiler support is losing out on the coercions. (The article is excellent otherwise)
Which makes sense because you could (and indeed still will be able to do) write your own uninhabited types very easily in Rust and indeed they're optimised accordingly. Because Rust has user-defined sum types you could simply write a sum of nothing:
enum MyNeverType {}
struct MyUnitType {}
Note, to be more clear, an enum with no variants has no values of that type (can't be constructed), and a struct with no fields has exactly one value of that type
My favourite never type ability is when you need to conform to a trait that returns Result but your specific implementation can never produce an error.
Return Result<T, !> and the compiler knows that callers never have to check the error case because by definition it can’t be constructed.
And if your callers are generic over the error type, and so they do have code for handling errors, the compiler won't emit this code for your result type because you've said its error type can't exist.
> After this change (and on the 2024 edition), the compiler assumes that T should be !, which doesn't implement Default, and therefore causes a compilation error.
If ! can coerce to every type, why not treat it as if it implemented every trait too?
The Default trait provides a function that actually constructs the type in question. But here the ! type can never be constructed, so the only way to implement Default would be to have it panic, loop infinitely, or otherwise fail at runtime.
So this would risk turning a compile-time error into a runtime error.
Moreover, Rust traits' associated constants/types get in the way of having a proper bottom type. What would <! as Iterator>::Item be? (In Scala I think it just doesn't compile?)
Not only that, if you have `trait Foo: Iterator<Item = u8>` and `trait Bar: Iterator<Item = i32>` how could `!` implement both of them? It would simply make the language incoherent.
> What would <! as Iterator>::Item be?
Another ! makes sense to me here. Are there any cases where it doesn't work to auto-assign ! to all associated types of a ! trait impl? Associated constants might require some mechanism similar to `compile_error!()`.
Ah, that makes sense. Rust noob here, so I wasn't aware traits can act on types directly without any instance of the type. Thanks for the info!
Yep, they can have static methods, as it were (in Rust lingo called "associated functions"; "methods" in Rust always take a `self` receiver). Traits can also have associated types and associated constants, which (naturally) also relate to the type, not any particular instance.
Is it obvious to rust developers that "!" would be the never type? I frequently use "never" in typescript. I could imagine using the never type frequently in rust too. I feel like a longer more human-understandable name would've been a good decision here. (feels like more rust jargon that makes the language harder to learn)
Even though the never type has been experimental for a while, I've seen `!` used in the docs,[0] so at this point, Rust developers are probably already aware of what it means even if they haven't used it before.
[0]: Example: std::process::exit returns `!` https://doc.rust-lang.org/1.0.0/std/process/fn.exit.html
You can even define your own functions that return `!` on stable Rust! The type has been stable in the return-type position since 1.0.
(There is a trick you can abuse to access the type everywhere: https://docs.rs/never-say-never/latest/never_say_never/)
Yeah I think just calling it 'Never' is much clearer, this isn't something that needs a dedicated single character, and ! is less readable imo
Yeah it really baffles me why a symbol like `!` was spent on this, which could be more useful for more a more commonly used feature.
I just checked, my main side project only has less than 10 things that return never. `-> Never` reads even better, imo.
The exclamation point is also used both as the C-style negation operator and as the identifier suffix that indicates macro invocations, so it was unlikely that it would have been used for any new feature. As my sibling comment notes, this syntax for divergence is very, very old (predating even 0.1), not something that anyone newly came up with.
And if you'd like to write `-> Never`, the nice thing about being a first-class type is that you can now just do that if you'd like, via a standard type alias: `type Never = !;`.
> Is it obvious to rust developers that "!" would be the never type?
Prior to this change most Rust developers would never have cause to ever use `!` for any reason. The only stable way to do so would be to specify the quote-unquote "return type" of divergent functions, which Rust has supported via this special-cased syntax since prehistoric days, before even Mozilla got involved. You can see it in the oldest capture of the tutorial from Jan 2012: https://web.archive.org/web/20120109041112/http://www.rust-l...
So when it came time to elevate `!` from being a special-cased return type to being a fully-fledged type, it was only natural to reuse this syntax. However, I tend to agree that, because we call it "the never type" in casual conversation, the most natural thing to do would be to just have a type alias called `Never` that we could encourage people to use instead. But that would be a perfectly backwards-compatible change that could be made at any point (as proven by the fact that the stopgap and long-stable `Infallible` type is becoming just such a type).
Is this so central, that it justifies the use of a single ascii char? Instead of, say, `Never`?
Relevant talk by Waffle at RustWeek earlier this year:
"When is never?"
The lesson here is that implicit conversions are bad. The never type itself having implicit conversions to other types is bad enough (even though such coercions are logically valid: “ex falso quodlibet” they should be explicit), but having a fallback type when type inference doesn’t have enough information to produce a type is even worse. Rust is famous for not even having implicit numeric coercions (say from i8 to i32) but it seems like a shortsighted decision to allow implicit coercions here.
Why is it bad? Implicit integer conversions are generally bad because they can produce unexpected behavior at runtime and obstruct what’s really happening, but that doesn’t seem to be what’s happening here.
Never is a standard type in many languages and is at the bottom of the type hierarchy because it’s a subtype of every type. Never isn’t implicitly converted any more than `&’a A` is “implicitly converted” into a `&’b B`, where `’a` subsumes `’b`. There’s no runtime conversion because there will never be an instance of never—it represents the value of a computation that never completes by definition.
I think what you mean to say is that implicit runtime conversions are bad, not that all subtyping is bad.
You’re using “subtype” in two distinct, but related, senses here, and I think this should be clarified.
From a more category-theoretic perspective, a type A is a “subtype” of a type B when there is an embedding of A inside B. In this sense, `!` is a subtype of every type (which is its universal property). But this definition also grants you that `String` is a subtype of `BigInt`, because strings can be coded as bit sequences which can be coded in `BigInt`, which may or may not be what you expect.
From a programming languages perspective – and this is the terminology generally used in Rust – a type A is a “subtype” of a type B when `a: A` implies that `a: B`. In this sense, `!` is only a subtype of itself; although it coerces to any other type, it’s not _literally_ of that type, the coercion is just invisible in syntax. Importantly, if A is a subtype of B then `Vec<A>` is a subtype of `Vec<B>` – but `Vec<!>` is definitely not a subtype of `Vec<T>`, since they may have totally different layouts in memory (the former not allocating at all, while the latter potentially allocating).
> A is a subtype of B then `Vec<A>` is a subtype of `Vec<B>`
That’s just not true. Java would permit it but then you get ArrayStoreException so this is unsound from a type system perspective. To make this sound, we need to classify each use of a type parameter to be covariant, contravariant, or invariant.
Java doesn’t permit that. You must specify covariant or contravariant type parameters with <? extends T> or <? super T>.
No I’m not talking about runtime conversions. I’m talking about conversions that happen at type inference time.
Rust is not a subtyping based language, except for traits and lifetimes. So statements like never being at the bottom of the type hierarchy is irrelevant here even though it is correct. If Rust had higher rank types the never type is also (forall a. a) but still it doesn’t matter. It is simply surprising for a type to be converted implicitly according to subtyping rules other than for traits and lifetimes.
Do you have an example of a piece of code that behaves in a surprising way because of this rule?
I don’t need to write examples because the article has plenty. All the fixes that Waffle needs to fix are precisely the code that behaves in a surprising way.
None of this has anything bad to say about coercion or fallback, it's a consequence of the fact that Rust is an expression-oriented language which had expressions (like `loop {}`) which logically evaluated to the never type when in return position, and yet did not have the machinery in place to support it as a proper concept anywhere outside of return position, and so they chose the unit type as a relatively benign alternative in those contexts, which caused no problems whatsoever until the day came when they decided to actually implement the never type.
Let's avoid using the term "subtyping", which as you say is irrelevant here. The reason you need diverging functions to satisfy arbitrary type obligations (i.e. to coerce to any other type) is because otherwise anything as simple as `let x = Some(42); x.unwrap();` just completely fails to compile, because `unwrap` is internally just:
fn unwrap<T>(t: Option<T>) -> T {
match t {
Some(foo) => foo,
None => panic!()
}
}
No you don’t need coercion. You only need polymorphism. The type of `panic!()` could be an arbitrary U, which unifies just fine with the type T here.
Generally languages with such polymorphism have a never type only because they don’t also support impredicative polymorphism.
And then once you have `fn foo<T>() -> T`, what do you write in the body that allows it to typecheck?
With ! the implicit conversion happens at compile time, never at runtime.
It cannot by definition happen at runtime because the never type has no values and thus cannot be constructed under any circumstances.
Any compile time coercions that occur would convert types (or generics args of types) to !
I find it difficult to imagine any situation where that would result in a working program - only if the coerced types or references to coerced generics were not even used would it compile.
We should be able to set at a crate level whether our code can compile with panics, implicit conversions, etc. And we should be able to blacklist dependencies and transitive dependencies that do these things. We should be able to advertise a crate's safety and attention to detail.
Higher level application code can benefit from this, but core libraries should forbid this statically and be prevented from even compiling or being imported should these things be enabled.
We should be able to filter crates.io by these properties, and force our own projects to abide by them.
I want nopanic, nocoerscion, maxdependencydepth, rustonly, nolinking, etc. flags.
Do you have some specific coercion in mind that you want to forbid? Unlike C, Rust is extremely tame when it comes to coercions. Forbidding coercions in general in Rust code doesn't really make sense, and I can't think of any that aren't either beneficial at best or benign at worst.
As a fan of the Curry-Howard correspondence, I approve of this decision.
You’re going to hate when you learn that the never type is inhabited
I'm unclear what this is implying, but in Rust the never type is uninhabited. https://doc.rust-lang.org/reference/items/enumerations.html#...
The never type seems very useful in various languages to either signal that a branch can never happen (the example of string -> bytestring never erroring) or to mark that a function will never return a value (and thus control) to the caller.
A simple TypeScript example:
const forever = (): never => { while (true) { // whatever } }
[dead]
Sounds serious. Armageddon serious.
Nobody should get ahold of this technology.
Shut down the schools!
Get rid of all small business (to mitigate the risk).
15 days to prevent Never from destabilizing!
We’re all in this together.