Crust of Rust: Subtyping and Variance

In this episode of Crust of Rust, we go over subtyping and variance — a niche part of Rust that most people don't have to think about, but which is deeply ingrained in some of Rust's borrow ergonomics, and occasionally manifests in confusing ways. In particular, we explore how trying to implement the relatively straightforward `strtok` function from C/C++ in Rust quickly lands us in a place where the function is more or less impossible to call due to variance!

0:00:00 Introduction
0:02:30 Practical variance in strtok
0:07:41 A simple strtok test
0:09:45 Implementing strtok
0:13:00 Why can't we call strtok?
0:17:26 Pretending to be the compiler
0:19:03 Shortening lifetimes
0:25:40 Subtypes
0:29:12 Covariance
0:33:15 Contravariance
0:42:14 Invariance
0:50:00 &'a mut T covariance in 'a
0:57:57 What went wrong in our strtok test?
1:02:24 Fixing strtok
1:07:34 Why is 'b: 'a not needed?
1:09:08 Shortening &'a mut and NLL
1:10:11 Is 'b: 'a implied for &'a &'b?
1:12:54 Variance, PhantomData, and drop check
1:28:06 Reasons for changing variance
1:30:47 for{'a} and variance
1:31:51 Mutating through *const T
1:33:29 NonNull{T}
1:35:26 How we got here

[valthorhalldorsson]

This was a great walkthrough. Pronouncing T: U as “T is at least as useful as U” made a lot of the other concepts click into place for me.

[lucasa]

having just a tiny bit of understanding of how types works in functional languages help understand this SO MUCH

[TheMisterSpok]

Oh my God, thank you! The logic behind contravariance has been avoiding my grasp for too long. You explained it in a way I could wrap my head around, and expand it to meet the mental model of type parameters I had.

[sufyanfaris]

I'm putting this as an analogy in my notes to explain covariance vs contravariance:
(please tell me if it's wrong)

In a world where some people are immortal, the immortal people are more useful over people that are not. ( 'static > 'a )
But, if there's a place that only requires people to be immortal to get in, then it's less useful as in less people can go there. ( Fn(&'static) < Fn(&'a) )

[Codeaholic]

Nice talk. I studied variance when learning Scala and for some reason it seemed easier to grasp there, but you did a great job explaining it here in Rust.

[calaphos]

I think this explanation about Co and Contra variance made me finally understand Javas Generics.

[leu]

Every time I stuck on some hard to understand concept in rust, I know Jon already should have good stream about it :D . Thank you so much. Without your support learning rust was much harder.

[VivekYadav-dsoz]

Finally after a 2nd, fully attentive watch, I grasped the whole video and now Rust's inner "thinking" makes a lot more sense to me.

[digama]

Great stream as ever, Jon. A small correction regarding "1:10:11​ Is 'b: 'a implied for &'a &'b?": In fact, the compiler does "reverse engineer" a "where 'b: 'a" bound from the mere existence of the type &'a &'b T. Here's an example to demonstrate this:

fn foo<'a, 'b>(_: &mut &'a &'b bool) where 'b: 'a {}
fn bar<'a, 'b>(x: &mut &'a &'b bool) { foo(x) }

In order for bar to call foo, it needs to establish that 'b: 'a, which it deduces because of the well formedness of its input arguments. (The extra &mut reference is there to ensure no additional subtyping happens, so we really need the lifetimes 'a and 'b to be related rather than some weakening of them. Double check that this doesn't work if you use 'a: 'b in bar instead.)

This is actually a useful fact to know if you ever want to (or have the misfortune to need to) write lifetime constraints in higher order types: for<'a, 'b> fn(&'a bool, &'b bool) is the type of a function pointer with no constraints on 'a and 'b, and if you wanted to have a constraint anyway, "for<'a, 'b: 'a> fn(&'a bool, &'b bool)" doesn't work (this syntax doesn't exist, and "where" doesn't work either), but "for<'a, 'b> fn(&'a bool, &'b bool, &'a &'b ())" does.

[aqua]

I was reading the nomicon article on subtyping and variance, and it kinda clicked for me. I wrote a comment on the Rust discord, this may be useful for others:

```
F is covariant if F<Sub> is a subtype of F<Super> (subtyping "passes through")
F is contravariant if F<Super> is a subtype of F<Sub> (subtyping is "inverted")
```
This is essentially saying that
- For covariant, the most useful type is `<sub>` (the longest lifetime)
- For contravariant, the most useful type is `<super>` (the shortest lifetime)

So, contravariant and covariant have a nice interplay together between them. For example in `&'a T` we can see `'a` is covariant, hence the most useful type is the longest lifetime, whereas in `fn(T) -> U`, we can see that for `T`, the most useful type is the shortest lifetime (contravariant; so the function can accept any argument since it is asking for the shortest one), hence the covariant's lifetime can be shortened down to whatever needed.

This makes calling function arguments easy since covariants have a longer lifetime, and the function expects a shorter lifetime, so we can shorten to whatever is needed (which is the entire point of it; so we can pass any longer lived item to a function; the function shouldn't care if the reference lives for a shorter time; it can forget those details since intuitively the concept holds; 'short is always valid for any 'long). I also liked picturing contravariance as `how strict the requirements it places are on the caller` (and clearly, contravariance is the least strict on the caller since it's asking for the smallest lifetime)

[nicholasmontano]

Yessss, so excited for this! When people talked about this stuff in Rust discord it went *woosh* over my head. Thank you so much for covering it!!! I'll be sure to always link this video when questions around this topic come up <3

[darklajid]

I loved this (going back in time and watching all your recordings).

The main content was excellent and I'm glad you did this for the world at large. My OCD is complaining that the strtok isn't even remotely doing what the C docs said and I wouldn't know how to do that well in the first place ("call once with an argument, then call with null until we're done") with lifetimes..

[nicolaslevy]

I think Curry-Howard correspondance helps understanding variance. For example
Covariance in Curry-Howard terms becomes
If you have a proof A=>B you can get a proof of B by providing a proof of A' where A'=>A
contravariance in Curry-Howard terms would be:
If you have a proof (A=>B) =>C you can prove C by proving any statement of the form A'=>B where A=>A'

[isaactfa]

Hi Jon, I requested this topic on the last Crust of Rust stream, so thank you very much for doing a video on it! It really helped a ton.

[OSSMaxB]

Thank you. I now understand what variance means. I had some intuitive understanding of parts of it, but this made it concrete.

[samroelants]

A little late to the party, but the way I usually think about it is:
- Anything that "contains"/"yields" some type T is *covariant* in that type (whether it's Java classes or rust lifetimes),
- Anything that "consumes"/"requires" a type T is *contravariant* in that type.

For example, Box<&'a T>, Iterator<Item=&'a T> and HashMap<K, &'a T> are all _covariant_ in &'a T: if &'a is a subtype of &'b, then Box<&'a T> is a subtype of Box<&'b T>

Functions are the obvious example of things that "consume" &'a T, but there's another obvious one: HashMap consumes/requires its key type! So, HashMap<K, V> is actually _contravariant_ in K!
(For example, a HashMap<&'static str, V> is less useful than some HashMap<&'a str, V>)

It kinda makes sense in a hand-wavy way. Philosophically, there's very little difference between a hashmap that maps K's to V's and a function that maps K's to V's...

[TrustifierTubes]

This is such a nice explanation of contravariance!!! It could not be more well phrased!

[theopantamis]

Thanks ! I like the small details on dropcheck you added in the video 👍

I think the moment people are more used to covariance and contravariance is really when writing function signature: you want the "less useful" types in argument and return the "more useful" in output. The most common case is when you use ref of slice in arguments because you know all smart pointer can deref into slices, that's a feature trait and not contravariance but it really feel the same.

[АлександрЧепурнов-эя]

A great explanation of contravariance. That concept didn't let me sleep a couple of nights, but you made it clear, thanks a lot. Great vid and great series, you're cool!

[infphreak]

For a more theoretical approach to subtyping (mostly as it applies to inheritance), you can read up on the Liskov Substitution Principle.