Crust of Rust: Subtyping and Variance
Вставка
- Опубліковано 28 лип 2024
- 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
You can read more about subtyping and variance in the Rust reference @ doc.rust-lang.org/nightly/ref... or in the Nomicon @ doc.rust-lang.org/nomicon/sub....
Live version with chat: • Crust of Rust: Subtypi... - Наука та технологія
![Lp. Последняя Реальность #107 РОДНОЙ ДОМ [Финал] • Майнкрафт](http://i.ytimg.com/vi/IK3QKzKUlHM/mqdefault.jpg)
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.
The borrow checker doesn’t really understand the concept of “usefulness”. Subtyping in rust is determined solely by the “outlives” relation. The lifetime ‘static outlives all ‘a, therefore it is a subtype of all ‘a.
I like to think of things in the way the Nomicon lays out: T is a U AND MORE. Same with lifetimes: You can pronounce 'a: 'b as "Lifetime a is lifetime b AND MORE" (i.e. a is ~longer than b).
Another useful reading might be "implements": T implements U. 'a implements 'b (meaning 'a is ~longer than 'b).
Something that really made it click for me was to think of `T: impl TraitFoo` and " 'a: 'b " as the same syntax and then realizing that saying 'a outlives 'b is the same as saying 'b is a subclass of 'a or 'a upcasts to 'b
@@interuptingcactus I think you mean, 'b upcasts to 'a (if 'b is a subclass, 'b would be the one upcasting to 'a, which is the superclass)
This also works with traits (kind of). BorrowMut is at least as useful as Borrow, and look at the definition: BorrowMut: Borrow.
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.
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) )
Ah, that's what was going on with the PhantomData
Thank you
I think this explanation about Co and Contra variance made me finally understand Javas Generics.
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.
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.
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(_: &mut &'a &'b bool) where 'b: 'a {}
fn bar(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 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
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
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.
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.
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 is a subtype of F (subtyping "passes through")
F is contravariant if F is a subtype of F (subtyping is "inverted")
```
This is essentially saying that
- For covariant, the most useful type is `` (the longest lifetime)
- For contravariant, the most useful type is `` (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)
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..
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!
This is such a nice explanation of contravariance!!! It could not be more well phrased!
I was just looking this up recently, I'm so happy that there are new videos on the subject.
Thanks you so much for this! I have run into this multiple times and never truly understood it.
I went into this video not expecting to get much out of it because frankly Variance is something I have not read about and the error message doesn't communicate that I should look at it (or at least has not communicated it when I encountered it before) so it was an enlightening experience actually getting an understanding of what the issue is and why the solution is what it is.
Thanks so much for taking the time to explain this in detail, I think it's a fairly common problem people run into and makes people scared of lifetimes.
This was enlightening for the issues I actually had with OCaml :-D. Thanks for explaining the concept of Co-, Contra-, and Invariance like no other material I read/saw. Good job!!!
For a more theoretical approach to subtyping (mostly as it applies to inheritance), you can read up on the Liskov Substitution Principle.
Man, this is such a wonderful explanation, seriously. I'm trully amazed. Much love man!
These videos are a gold mine, literally. Thank you for your efforts!
Thanks Jon, as always amazingly scrupulous and detailed explanation!
Thank you so much!! These explanations are very clear. Now it almost seems obvious to me that this concept exists and that we need terminology for it.
Hey, thanks for the stream, it was a very useful recap about variance for me.
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.
This video really helped me understand variance in rust better! Thank you!
Really awesome explanation of contravariance!
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'
I think that helps for those already familiar with the theory, but not so much for people who are "just programmers", for the lack of a better term (and I count myself in that category).
when I encounter those kinds of problems, it feels like the new " find the missing '}' "
Best explanation about variance! Thanks!
The way this made sense to me was: If a variable is provided to me (I'm reading it), it must be at least as useful as I expect. If I'm providing a varaible (passing into a fn), I can only meet requirements for less useful things. If something is both provided to me and I'm providing it (mutable value), I can't meet a requirement to provide something more useful and I also can't work with something less useful.
mind-blowing presentation ❤
Thank you for teaching and sharing 👍👍👍
great video as always
50:10 Looking at that table after your explanation, I now notice the lack of a contravariant, write-only reference type.
I just thought of the following regarding invariance in T of &mut T:
for references we can distinguish the operations of reading and writing:
1) a reference &onlyread T is covariant in T but not contravariant
- if U
Thanks! These videos are a constant stream of "Aha!" moments.
thank you for your time
Thanks for the great material!One question though, even after re-watching I can’t seem to find the place where the second part of the &mut T invarience in T is discussed. You explained why it’s not covariant (you can’t shove that less useful type in) but didn’t mention why wouldn’t you able to assign a more useful type (e.g. &’static str) to a less useful reference (&’a str).
What does my head in with Rust is that I seem to be stuck thinking of subtyping in terms of sets. There's the set of all animals, of which cats are a subset that are special in some way. Subset, thus a subtype. What does my head in is that 'static is a subtype of everything, but I think thinking, 'static is the bigger thing.
I suppose the correct way to think about this is to imagine the set of all lifetimes, and say to myself that 'static is a very small subset as it's only one very specific element. Not only is it a cat, it's a one specific cat. The set that 'static is in is very small (one element) and thus it's the subtype. I wonder if I can persuade my brain to think about it that way.
I used to do the same! What helped me was to think of parameters (i.e. lifetimes/sub-lifetimes and types/subtypes) in terms of the *properties they exhibit* instead. For example, a "cat" is a subtype of "animal", because it exhibits all the properties of an animal: Movement, procreation, etc. But it also exhibits cat-specific behaviors: It can hunt, meow, see well in the dark etc. So what is a cat? A cat is an animal AND MORE, despite being (technically) a subset of "animal".
Incidentally, this reading translates to lifetimes as well: If lifetime 'a is a "subtype" of lifetime 'b, that means 'a is valid for 'b OR LONGER (i.e .OR MORE). Or, to be concrete: You have the relationship 'a: 'b. Now imagine that 'a is 'static, so you have 'static: 'b. So your internal monologue could be "the lifetime 'static is 'b OR LONGER". Is that correct? Yep, that's correct, since 'static is the longest lifetime. So it all checks out.
It's probably for the best if you try not to get too hung up on the "sub" bit in "subtype". While it is correct (not all animals are cats, so therefore the set of cats is a subset of the set of animals), it's just… not really all that useful here.
I guess this is the one bit where non-native speakers have an easier time than native speakers, because it's easier for them to disassociate the word from the meaning of its constituent parts. :)
Really great video! I feel like I almost understand things now. I'm still confused about one point though. At 1:06:25, it is explained that the compiler is able to shorten the borrow of x because mutable references are covariant in their lifetimes. But previously in the video covariance was used in the opposite direction to justify substituting a *longer* lifetime to a lifetime parameter. Why does covariance now allow substituting a *shorter* lifetime to the borrow?
This feels very similar to the LSP. Would that be a good model for it?
Do you use VIM or NVIM? How do we get Rust to autocomplete like that on your setup? I want to run away from VSCODE.
If you have it documented somewhere it'd be great. Thanks in advance!
at 1:17:22 why does the compiler allow that code? since the implicit drop will be called on `z` and it runs the Drop code for type Vec? which may access `x`? Can anyone explain?
If there's a Rust reference, is there also an Owned Rust or a Rust Box?
i lol'd when he saved and the test he moved below went back to the top
No wonder it's taken years to get this into the compiler. It's so hard to think about.
Great video, much appreciated! Also I’m really sorry for the annoying question which you probably get a lot, but what is the programming font that you’re using?
Glad to hear it! The font is Noto Sans Mono :)
For `&'a &'b T`, could you use the `&'a` after `'b` ends as long as you don't _dereference_ the inner one? Like the stuff in the drop check video
another awesome video :8
any chance you could tell us what your keyboard is?
Thanks! My keyboard is a Mistel Barocco MD600 v2 split mechanical keyboard with Cherry MX Clear Switches :)
Thanks!
Basic question I guess, but what’s the diferrence between `&mut &'a str` and `&'a mut str`?
are you using neovim or just vim? What plugins do you have?
Hello! I have a small question about the drop check at around 1:20. Why doesn't the compiler move the drop to the end of the shortened lifetime instead of just ending the lifetime and dropping at the end of the scope?
Because Rust's semantics are to drop at the end of scope, and that's something programmers can easily reason about. If the borrow checker determined when exactly something is dropped, it'd be very hard for a programmer to know exactly when the destructor runs, which may be unfortunate for drop implementations that, say, release a lock.
thanks!
Does droping a reference does anything ?
Since i think it implement the Copy trait and it will give an error ..
Edit : droping a mutable refrence is possible since it doesn't implement the Copy trait .
I ran his first example with cargo 1.50.0-nightly (a3c2627fb 2020-12-14) and no error for me ... it worked.
Actually I have one thing different in the function declaration:
pub fn strtok &'a str {
I have no excuses for allocating strings everywhere now :(
Now I understand it a little bit better 🤣
Port tmux :V
I'm quite interested in how it actually works, but usually don't have the energy to try and understand it from the source myself.
So you porting it might help me a lot since you explain things really well. But it's may be too complex if you want to stick to a 6h stream. I dunno
I'm 40-ish minutes in, and im curious if it would be helpful to teach this purely with the operations you could perform with ordinals? It seems like that's all this is, the wording might be specific to types here, but the concepts come from ordinals.
I still don't understand contravariance properly. Why is it okay to pass a 'short lifetime to 'static in a Fn(&'static _)?
No, that's not possible. who said that? This would break the covariance. It is ok to pass a Fn(&'a T) where Fn(&'static T) is expected, which is contravariance. &'static < &'a T and Fn(&'a T) < Fn(&'static T).
@@vikramfugro3886 this code is valid:
fn a(_: &str) { }
let func: fn(&'static str) = a;
I spent some time to think about it and it makes sense now or at least I can reason about it.
@@Lexikon00 Yes, it's valid. But that's not what you said in your first comment.
I'd describe the variances in turn of some java method.
With cat and animal class
If you can take any animal as parameter, a cat will do as it is an animal (covariance)
If it returns a cat, you cant replace it with animal as not any animal is a cat(contravariance)
If it cannot be changed at all its invariant
(correct me if i messed up, thats from somewhere at the back of my head)
Therefore in java parameter covariance is allowed, contravariance isnt, but for return types its the other way around. Kind od you are allowed to specify, but are not allowed to return something more general.
Think of it as: it requires more conditions is a subtype
What helps me remember is vim:vi
i wish your next videos being large font-size . 3 times :)
Have you described somewhere your vim configuration?
TIL ddg has a !rust bang
80% of that went over my head oof
I'm pronouncing it like "car", because in my understanding it is from "character" so it should be "k" but often in my head when I see "char" I hear "ch" like in "cherry" XD
Great video, thanks!
In the last part you didn't mention, that one can also play with a phantom lifetime variance using, say, `PhantomData` to enforce invariance.
Side note: here is one interesting application of invariant lifetimes: www.reddit.com/r/rust/comments/2s2etw/leveraging_the_type_system_to_elide_bounds_checks
I watched this yesterday, and something was off to me intuitively about the strtok function. I was thinking "why is he using 'a and 'b here? Because the returned string reference, will have it's lifetime be bound by the parameter string reference that's passed in", and so I removed the 'a entirely, and surely I was right.
It was utterly confusing to see strtok(s: &'a mut &'b str, delim: char) -> &'b str because the 'a is saying nothing here really, especially to novices who just want to use the programming language and get real gritty with these details later on. What you should write, in order to not confuse people is:
strtok &'a str
Or is this just new rust where that works in? Because that's the way I was taught Rust and understood it from the book "Programming Rust". Or is it something about the video that I have misunderstood?
I cover how you would actually write this towards the end. I agree you wouldn't normally write in both lifetimes, but that's not really the point of the video. Rather, I'm trying to explain why it's important that the lifetimes are *different*, which is easiest to explain if they're named. Even if you elide some lifetimes, there are still lifetimes associated with those references :)
Hi, Can you send me userChrome.css for placing tabs at the bottom instead of the top in firefox. Thanks in advance.
My entire configuration is already on GitHub:github.com/jonhoo/configs :)
@@jonhoo Thank you. Can you once make a video on some of your configurations in spare time. It will helpful for people like me to know new tools and customization.
You mean like this one? ua-cam.com/video/ycMiMDHopNc/v-deo.html :)
Reading through the page on variance again, I’m fairly certain at this point that your explanation of what “&muts being invariant in T” means was incorrect. Invariance in T only applies to types with higher-rank trait bounds. And since you didn’t actually introduce any types with HRTBs, your explanation must have been incorrect. Or at least incomplete. Either way I think I am now more confused than before I watched. 😀
I don't think that's true? &'a mut T is covariant in 'a, but invariant in T, which is exactly what we explore in the example we go through that covers &'a mut &'b str.
@@jonhoo ohhhhh I see. Thanks.
@@lewdwig Oops, sorry, got that backwards. It's covariant in 'a and invariant in T. Edited. The point still stands :)
Why just not add a second lifetime? It's hard to watch the stream when you know how to fix all the problems.
fn strtok(s: &'a mut &'b str, delimeter: char) -> Option
Yes, but the whole point of the video is to explain why the second lifetime is needed.
1:02:44 addresses this comment
@@jonhoo IMO it still doesn't quite work as a motivating example. There doesn't seem to be a reason why the lifetimes should be the same in the first place and why that would work even if we didn't know anything about variance and lifetime subtyping. It's kind of obvious that this would lead to issues if we want to strtok a 'static str because it forces the mutable reference to be 'static as well. I feel like you'd first have to know about variance and lifetime subtyping already in order to assume it might work in the first place and then you learn about invariance as the reason why it actually doesn't. But without that knowledge, you'd already assume it doesn't work. And intuitively, the lifetimes are completely unrelated so it only makes sense to separate them.
Was thinking the same thing as Чарльз Дарвин
. Even if it compiled an ran with only 1 lifetime, it would still be wrong.
fn it_works() {
let mut x = "Hello World.";
let token1 = strtok(&mut x, ' ');
assert_eq!(token1, "Hello");
assert_eq!(x, "World.");
}
This code is working fine with rust 1.60 compiler.
What's the signature of your `strtok` function?