The past few weeks I've wanted to do a little post on subtyping and coercions in rust and how the difference between those two might make some type relations a bit confusing for many a novice rustacean coming from a language with less restrictive subtyping. With the exciting news of !, the never type, getting stabilised1 (go thank waffles and everyone else who has been involved with that!!) I have the perfect excuse to do so! Especially since I've already seen a bit of confusion around what the never type actually, technically is. This is a bit of a "I think you should know this stuff if you write rust" moreso than a coherent message or opinion i want to convince you of. Trying to strike a more educational tone than this blog usually does ... also I just want to ramble about this stuff cause it's cool.
What's this subtyping thing anyways?
Type theory jargon easily gets confusing for many, especially once we start bringing in the formal definitions of things. So sorry type nerds but I'll be giving a decently vibes based definition of subtyping and variance here ... and it's a bit of a speed run explanation. Go read up much more on this if it peaks your interest!, this is meant only as a small intro to get you far enough to understand the difference between subtyping and rusts type coercions!
Subtyping is a kind of relationship that two types can have to each other. As succinctly as i can: If a type U is a subtype of another type T then any value of type U is also a value of type T. This idea should be immediately familiar to most programmers! Especially if you've done any work in languages with a strong object oriented leaning. In many languages, especially OOP flavoured ones, you as a programmer have a lot of control over the subtyping relations that your types have. Typically you'll be able to define a class that extends another class or implements an interface, and by doing so that class will become a subtype of the other class or the interface. Any Cat is an Animal!
Variance is closely related to subtyping. Variance is a property of a generic type (a type constructor) with respect to it's type parameters. The variance of a type F<T> in it's parameter T tells us how the subtyping relations of T influence the subtyping relations of F<T>. If F is covariant in T that means that if T is a subtype of U then F<T> is a subtype of F<U>. Contravariance is the inverse. If F was contravariant in T then F<U> would be a subtype of F<T>. Invariance means that no subtyping relation can be given between F<T> and F<U> just from the subtyping relationship between of T and U.
Okay that's still very abstract let's look at an arbitrary List<T> type. In most languages the dynamic array type is covariant in it's type parameter. That is if I have a List<Cat> then that same list is also a List<Animal>! Crucially it's not that I can cheaply convert from a list of cats to a list of animals. If Cat is a subtype of Animal then a Cat is an Animal and, due to the it's variance, a List<Cat> is a List<Animal>2. The main reason most developers ever want to establish a subtyping relation is that it allows us to "use" a Cat or a List<Cat> anywhere an Animal or a List<Animal> is needed. Very useful!
The key thing to note in the rust context here is that most OOP languages give you as a developer the ability to designate a type as a subtype of another type. Many developers expect to be able to do this, even if mostly subconsciously, in rust and when they try out rust and deal with traits they sometimes get the impression that they can. However rust is a bit strange among modern languages in that you can't. Subtyping in rust is incredibly limited! It can only ever be implicitly done by the compiler and only ever happens in the context of lifetimes. Lifetimes are a can of worms on their own, I won't go into detail about them here. The point is that while implementing a trait for a type may feel like designating that type as a subtype of the trait (or at least a subtype of a trait object of said trait) that doesn't happen! And similarly a lot of primitive types that seem to be subtypes of other primitives are not, in fact, subtypes!
That doesn't make sense. I can literally give a &mut T to a function that wants a &T
Astute observation my dear reader! You can indeed do exactly that but in rust that's not because of subtyping. It's because of type coercions. The ergonomics of subtyping are really quite desirable in many places, but variance means that subtyping can spread, often times that's what you want out of a subtyping relation! But rust, as a language, is quite particular about the things it allows and does not allow, that's the rust magic after all. Thus rust instead, at the language level, defines a variety of so called type coercions. As far as I know this is a bit of a rust specific terminology but the concept is quite simple: If a type T can be coerced into a type U, then the compiler will implicitly in certain positions (like the arguments to a function!) perform a conversion from T to U for you. That is when you call a function that wants a &T with a &mut T you're not actually calling the function with a &mut T, the compile implicitly converted your &mut T into a &T and then passed that into the function.
Why does that difference matter? Well for one type coercions are allowed to be more than just relabel a value to have a different type, they can also perform cheap changes to the value such that it conforms to the target types layout and semantics. For example, since String implements Deref<Target = str> then a &String can be coerced to a &str through that implementation. Those two types have very different layouts! But the coercion handles that. Another big reason this matters is because of variance. Remember how subtyping implies various things about the subtyping of other types through variance. Type coercions do not! That means that while &mut T coerces to &T and you can thus use a &mut T wherever you're asked for a &T, Vec<&mut T> is not a subtype of, and does not coerce to Vec<&T>! The behaviour of type coercions are much more localised and that arguably makes them a lot easier to reason about. But this gives some people quite the head scratcher if they think that &mut T is a subtype of &T and thus expect to be able to rely on Vec<&mut T> being a subtype of Vec<&T>.
I mentioned traits and trait objects above and you may be thinking that surely a type T that implements a trait U must be a subtype of dyn U but nope! This too is a coercion, a special case called an unsizing coercion. At specific locations related to pointers, references and smart pointers3 the values being pointed to can undergo unsizing coercions and go from a sized type to something like a slice or a trait object which are unsized types.
That's cool and all but what does that have to do with never?
Many a person has explained ! as rusts "bottom type". I've done so in the past, other people who really care about this stuff like the venerable Logan Smith have too. But that's not actually true. A bottom type isn't what someone has if they like me4, it's a type that is a subtype of every other type in a type system. Subtype that's important. ! isn't a subtype of every other type in rust and thus it is not a subtype. What ! is is an empty type. An empty type is a type without any constructor, thus no way to make a value of that type and thus no valid values, thus a value of type ! can never exist. Then on top of that ! also has a defined type coercion to any other type. Since ! can never exist this coercion only has any meaning at the type level, but it's still important that it's a coercion and not a subtyping relation since that means it doesn't interact with variance. That is Option<!> is not a subtype of Option<i32> or any other Option<T> for that matter, but instead if an expression has type ! it can be coerced into an i32 at the type level and then stuck in a Some(!) that will never exist and be returned from a function with a return type of Option<!>. Maybe small but very important tid-bit about ! now that it will start proliferating throughout rust.
Ummm idk how to end this one well ... hope you liked my autistic rambling! If this kinda thing is interesting to you go read the rust reference5 and the rustonomicon6, maybe watch Jon Gjengsets "Crust of rust" episode on subtyping and variance. Lots and lots and lots of interesting things here. Reading the reference even taught me some tricks I didn't know rust had up it's syntatic sleeves like let .. else7 and @ patterns. And the nomicon has some really good explanations on exotically sized types, reprs, that kinda thing. Also go read about type theory in general. It's really interesting and rust is far from the only name in town, some might even say it's roots in a surprisingly (looking a how the community handles types today) ad-hoc approach to types is to it's detriment.