Understanding Rust Lifetimes

all right good afternoon everybody uh it's time for another wrestling stream today um i uh i think today's gonna be a little bit different and that it's coming from just some random code that i saw on the internet there was a question on uh one of the rust forums out there or on zulup i think it was somebody asking a question about how to do something that actually involved a somewhat um nuanced uh understanding of of lifetimes um and i'm constantly on the search out for good examples of of lifetime problems the the the fact of the matter is that in wrestling um uh lifetimes get a lot of attention because it's kind of it's a newer concept no other language really has the concept of lifetimes kind of baked into it like russ does um and so it's something that people struggle with um very understandably so because uh you know it does require um an understanding that you wouldn't necessarily get from uh other languages with the possible exception of c and c plus plus although there um you know because it's not baked in the language it's kind of more of a cursory uh understanding and and um when it's formalized and rust that might lead to uh you know some some gnashing of teeth um and with that i'm always kind of looking for good examples to to teach concepts about lifetimes but the you know the fact of the matter is that most of the time when you're writing rust you don't usually have to think too deeply about lifetimes especially about explicit lifetime annotations you do have to think about lifetimes and ownership and borrowing kind of at a high level but you're you're most of the time not annotating that in your code um but when sometimes you do have to annotate it and when that happens um you you usually end up with um you know end up with some code that's uh that maybe is not um super understandable if you're if you're coming at it with fresh eyes um and so i thought today we would uh we would basically go through some this example that i found um that i think is is is extremely simple in um and kind of what it's trying to achieve um but uh and and should be you know take very little time to explain what we're trying to do but uh requires kind of a deeper understanding of lifetimes and the hope with that is that we can kind of talk through some things um and get a better understanding and what i'm really hoping is maybe there's somebody um who has an extremely uh deep knowledge of lifetimes beyond what i even have um who can can explain some of these things in really formal terms um because uh some of it is a little bit of the compiler kind of helping us out and not necessarily magical ways but ways that are kind of a little bit might be a little bit difficult to understand when we first look at it okay i've been talking too much so let's switch on over here to to my screen we're just going to go ahead and create a new project as we normally do and i'm going to call it lifetimes and i'm going to make it a lib and then i'm just going to open it up in vs code so we can go ahead and get started all right so i mean i think we will write a few tests just so we can get a better understanding of of what exactly um is happening uh real quick um but uh but the code should be pretty straightforward to understand so what do we want to actually accomplish today well the code that um i uh that i saw on zulup was basically trying to create a an iterator i'm a an iterator over um a slice of some of elements of type t basically so basically you have a collection of things you're you're borrowing that collection and you want to iterate over that that collection and the key to this is that you want to iterate over that collection in an immutable way so you want to basically point to each element uh in that collection and give a mutable uh element and uh into it now most things in and russ already implement iterator um so this isn't this isn't really necessary to do um but basically what we want to do is if we say have something like our collection here and it is uh you know one two three four um and for simplicity let's go ahead and just make this a vector real quick um and then we want to do something like you know four i for lm in collection dot itter underscore mud and this iterates over the elements and gives a mutable reference to each element in turn so this is kind of what we want to implement but we want to write a wrapper around our type and basically implement the iterator trait for ourselves um does that make sense to everybody let me know um if that makes sense uh to all of you and uh but i think as we as we write the code this will become clear so basically um i thought instead of starting out with an immutable iterator which is uh you know going to be a little bit non-trivial um we should start with a non-mutable iterator and that might help us kind of get up to speed with with what we're doing so basically um i want to write a struct called um my itter wrapper and this struct is going to wrap a collection of some sort of slice of some sort so we can just call it slice of type t just like this all right so we have a struct it has one field called slice and that's like that field slice is a is of type slice of tea now of course this is not going to um actually compile here um let's see if i can go ahead and get it to so the first thing that it's saying is that it's missing a lifetime specifier this is purely kind of a syntactic thing and rust where when you have a field that is a borrow you need to specifically say what is the lifetime of that borrow how long will that borrow last for um and chad so you're essentially implementing another way that an itter mutt works behind the scenes yeah you're we're basically writing um a rapper and writing it or mutt ourselves um on top of it so here we need to specify a lifetime um and by convention usually lifetimes are for tick a uh and russ but we can call whatever we want and in fact today we're going to be taking advantage of that fact and it's saying i don't know what tick a is what are you talking about um that that lifetime has not been declared and that's true we have to say that our struct is generic over lifetime a and this is an important point that i think a lot of people don't think about essentially what we're doing here is tying the myetto wrapper struct how long that that struck can live for its lifetime because everything in rest has a lifetime we're tying it to whatever the lifetime of the inter inner slices all right i mean chad is asking him i'm wondering how this is going to work without unsafe it is possible to to do this without without unsafe so um i believe it's only possible in russ 2018 which i've recently found out 99.9 percent of people use russ 2018 so um yes it should be possible so we've tied the lifetime of our mayada wrapper struct to the lifetime of the the slice that's inside of it which makes sense right this struct can only live as long as we have a valid slice inside of it so we can't have a slice that that doesn't live as long as the struck that wraps around it why because if that were the case then we could have a maya wrapper struct with a slice that's not valid anymore and that's not possible in russ we don't want that that's what rust is designed to prevent us from having all right um cool it looks like uh we have a solution in chat so hopefully we uh can compare those solutions and see what they look like once we once we get to that point because i i believe there's multiple ways to do this the last error that we see here is that we can't find the type t so we need a way essentially of um of making this generic over some type t and that's that's quite easy right so maya wrapper struct is generic over some lifetime tick a and some type t so that's great um what is this complaining about oh this is complaining that's not mutable all right um so we want to be able to write this essentially um we have a collection here um and we want to say wrapper is my inner wrapper where the slice is a a slice on the entire vector collection uh what is it and we gotta bring my wrapper into uh into scope so we can actually refer to it by this use super here and then what we want to be able to do is iterate over it and say like this and we're going to get an error here saying that myer wrapper is not an iterator all right so this should be able to we should be able to compile this code here so we need to implement iterator on myer wrapper so impul iterator for maya wrapper and now we have to say okay mida wrapper is generic over some lifetime tick a here and some type t now this will complain here because it doesn't know what tick a is and it doesn't know what t is it's looking for a actual lifetime that it knows about called take a which there isn't one and it's looking for a type called t and there isn't one so we need to say that those are two generic things which is how we do that here say hey we've got two generic types tick a and t and we're going to use them in these positions all right and we're getting a complaint here saying that we're missing a whole bunch of stuff we're missing item and we're missing next which is what uh what iterator expects when we implement it so let's go ahead and do that real quick and say the type item which is the type of thing that we iterate so on each turn we iterate and provide a an element we provide a reference to type t and of course it's going to complain again here saying i don't know i need to know how long this reference lives for and so we can say that the reference is going to live for tick a so essentially now we've tied three things together we've said that maya wrapper lives for as long as the slice lives for and the element that we kind of yield out to people on iteration will live for as long as my a rapper does they're all living for the same lifetime ticket all right and it's still complaining because we're missing the next uh function which is how um iterator actually iterates and and yields new items so iterator each time we iterate we call this next function which yields out the the next item uh and we're getting uh we're getting a question in chat here that i think is a is a great question it's a question that comes up quite often like um they're asking the syntax uh differences between the generic parameters on structs and the generic parameters for um for an implementation here why is there a difference like why do we have to um why do we have to first declare take a and t here before using them here and the reason for that is because if we remove this this syntax also has meaning this is totally valid russ code it is simply looking for parameters type parameters here that already exists so it's looking for a lifetime parameter tick a that should already exist in scope which there is none that exists in scope there is no lifetime there is no concrete lifetime parameter tick a in fact there is only one lifetime parameter that actually exists that's not generic is tick static and also it's looking for an actual type type t but there is no type called t there is there is no type that exists called type t it is generic so we first have to say that tick a and type t are two generic parameters that we're declaring for this implementation here and we're going to use them here this is important because we could actually implement iterator we could if we comment that out we could say we're going to implement an iterator that only works for static lifetimes where the element is in i32 and of course this will complain because we're not gonna we're not actually implementing it but this is totally valid because there is a concrete lifetime tick static and there is a type i 32 here so i hope that that answers that question up instruct we this is just where you put the generic um uh parameters because it's impossible to make something generic over concrete types that doesn't really make sense so i hope that answers your question let me know if that's not if that's still not satisfying and i can um i can try and go at it from a different angle all right cool so let's go ahead and see if we can get further with this um the first thing that i usually like to do is get things compiling so um i put in the to do macro here which basically says like get the thing to compile and if i run this crash the program that's very helpful so everything is compiling here if we were running this it would simply just crash that's all but this is this is fine this works so let's go ahead and think about how we want to do this what we want to do is essentially every time we iterate we want to get the first element of the of the slice and then set slice to be equal to the other elements in the array all right so first get the first element then set the other elements as self.slice and then return first element all right so how do we get the first element well that should be pretty straightforward we can just do slice the self.slice get and zero index here of course so this returns back to us an option um which is great um it returns us to an option because the slice might be empty and the first element in the slice might not exist so that's why it's returning an option here now we want to set the other element like self.slice to the other elements let's write it that way set self.slice equal to the other elements this is essentially like popping off the first element and saying that self.slice is now equal to the tail of that of that thing so we can simply say self.slice is equal to self.slice 1 dot dot and we got to borrow that so this syntax is a little funky here but this is essentially saying take every element starting from the the one index element so the second element in in the list all the way to the end because we're doing one dot dot and not providing an end so that is assumed to be the actual the end of the list here all right and we're setting that equal to self.slice so now after this point self.slice is equal to whatever was at the end uh but it was ever equal to the second element in the list all the way to the end of the list um and good point that's not a spoiler that's what i was going to talk about just uh now chat so thanks for that um this will panic though if we have an element that uh we have a slice that's empty because when we index into a slice and we try to get the the element at um at position one and beyond if there is no element at that position it will panic so we need to have a shortcut here basically saying like um if self.slice dot is empty return and that should work and with that we can just return the first element and we already have to return um an option here so the types line up great here we should expect this to like if we want to be if we want to make sure that nothing weird is going on we can do something like this where we unwrap it and then rewrap it in some oops we wrap it in some because element here should always be set because we're guaranteeing that there's one element in the in the slice with this check up here but there's no need to do that that's just extra work so we'll just do this and this compiles just fine and i hope let's actually write in the test like um we can actually do this index this should work fine we can assert that lm is equal to collection index what is that complaining about ah assert equal sorry still complaining because we need to dereference the two so if we go ahead and do cargo test it passes great cool so we've we've successfully implemented a wrapper type that basically wraps our slice and provides an iterator over it not super exciting because we simply could have just called dot iter on our vec and done the same thing but now we know how iterator works we declare a type item that type is a a reference to an element of type t it has a lifetime of type a that lifetime ties however long the element lives for to however long my atta wrapper lives for which itself is tied to however long the slice inside of it lives for which again makes sense right we don't want to hand out it or we don't want to iterate over our collection hand out references to elements inside of the the slice without knowing if that element that that element might live longer than the slice itself does right if that were the case then we might end up in a situation where we have a reference out somewhere the slice is no longer valid and we have a dangling pointer and we can't have that in rest right so this has this works um this is uh you know probably what you understand if you're if you've come to good terms with uh rust borrowing kind of 101 um so we're going to stop here for just a second and see if anybody understands or anybody has any questions about what's going on here and apparently there is um another way which i didn't know about this there's another uh function that we can try to to do the exact same thing here but and and kind of uh um now it's actually the same amount of lines um it's actually more code um but let's let's do that uh real quick because that will help us figure out um some code that's coming up later there is a self.slice dot split split first and that gives us element and rest that's option okay um so we can do this actually oh this is great yeah so here we call split first on the slice um and split first uh take gives us the first element and the rest of the of the list and it will return an option if there is no first element which is really great and now since this is returning it's wrapping it all on an option we can use question mark to just say if it's none return it early with none and then all we have to do here is self.slice is equal to rest and we got a wrap so this does exactly the same thing um but uh you know you can you can pick which one you like uh better so and then we're getting a question why are we mutating self.slice in place does that make it so we can't iterate over a wrapper more than once that is true yes and that is what an iterator is iterators are you can notice here the iterator trait you pass in ampersand mut self here the reason for that is iterators are essentially meant to uh iterate only once um so we will what we iterate and then we'll eventually reach the end of the list and we can't reuse our iterator we'll have to reconstruct a new iterator and that's that's essentially how iterators work the reason for that is a lot of times if you want to do iteration you have to keep some internal state here which that's what we're doing here right we're keeping internal state here um but notice we're not we're not mutating the li the slice itself we're not changing the slice itself because it is only it's an immutable reference itself right so we're not changing what this is pointing to the where where those elements sit in memory they're they're not being changed at all we're simply changing what self.slice is pointing to we're essentially changing the pointer yeah and as chad is saying it's basically just kind of shifting a pointer forward and saying okay we were originally pointing to the beginning of the list here now we're pointing to the first element then the second element then third element and oh and on so when you set slice to the next elements can you give a first is this so there's a question about is this a costly operation um no it shouldn't be um the reason for that is when we call split dot first essentially what it's doing is giving us two pointers so references at the end of the day are usually just pointers right so we're getting a pointer to the first element in the list and we're getting a pointer to the second element in the list essentially which is obviously pointing to all the other elements and so when we do self.slice we're writing in a a number so setting a number in a field somewhere so this shouldn't be expensive at all and i mean this probably will be inlined and stuff like that and uh the you know the slice itself is probably stack allocated um you know what keeping track of where that slice is so there's a lot of optimization that can be do here we're essentially ending up with um a loop at the end of the day great okay so that's all well and fun um the question there's a question in chat the wrapper is an iterator yes exactly we're not iterating over the wrapper the wrapper is itself an iterator in fact look here we are implementing iterator for the wrapper so if it makes us uh feel better let's go ahead and do my iterator so the my iterator is now it is literally an iterator all right cool so this is all well and good here um but now is the real challenge the reason that we're we're actually here and that challenge is trying to do the same exact thing but instead of iterating over an immutable slice and getting immutable references to each element in the slice let us do the same thing but with mutable slices and mutable elements all right so now we're going to do the same thing struct my mutable iterator and it's going to essentially be exactly the same as before so it's going to be generic over tick a and t it's going to have a one field called slice and that slice is going to now to have a reference in it but importantly a mutable reference here oh and so this is just like our my iterator but now um a mutable iterator instead an important thing to keep in mind is that we you know this is called mutt or mute it's mutable but another way to think about it is that it is exclusive so when we have a immutable slice here it is non-exclusive meaning there might be other uh slices just like this pointing to the same exact um you know array of things painted to the same exact collection of things we can have as many immutable many non-exclusive uh references as we want and in fact same here like we have this uh immutable reference to t here and this the fact of the matter is is that we can have as many of these as we want at the same time and in russ the thing to remember is immutable references you can have as many as you want they are non-exclusive references or you can have one and only one mutable reference an exclusive reference all right so that's really the difference here we use the term mutable and immutable because that's usually what they allow us to do we can mutate when we have uh this this type of reference and we can't when we have this type of reference but the reason for that is because mutable references are exclusive so we can mutate because we are the only one pointing to that thing we are all alone all right so let's do the same thing here we're going to impul uh let's do take a and t iterator for my mutable iterator take a t yeah there's a a a note and chat about how this is kind of like a read write lock um yeah in a way what rust does is encapsulates the idea of a single writer multiple reader paradigm that you might be familiar with from locks or from databases where you only ever have either one reader sorry only one writer or you have or exclusive or you have as many uh readers as you want this is the exact same thing here but baked into the language all right so now we want our type here or type item to be just like before but an immutable immutable reference to an element t all right and just like before oops going to implement next here and put to do here so this is all compiling and let's go ahead down here and do the same thing and say um collection my immutable iterator let me bring all this up here and this needs to be immutable now and now what we want to do is uh first do lm equals llm lm plus one we won't be able to do this the reason for that is because we here are trying to read from collection while we're writing to it and what did we just say we can't do that we can't write to something and also read at the same time we can either read as much as we want or have one thing right to the thing at a time so we won't be able to um to assert here uh but then we can do four lm lm uh let's just do assert equal to let's do collection the first element of collection or is going should be equal to two now because in here uh what is it complaining about here um we're iterating over and adding one to each element and so the first element in our collection used to be one it should now be two all right and if we go ahead and run this it will fail miserably uh let me my my window has gotten too big oops it will fail miserably because uh we have not implemented next year right so it's panicking and we have not implemented next so that's now what we're gonna have to do so i have a question would you ever want to return an iterator type itself or do you always want to return a concrete implementation of one uh what do you mean by returning an iterator type um let's see here if i can bring over this docs docs.rs slash standard let's bring this up here go into vec here go to itter where is it where is it i think it's on slice actually bitter if you can look here when you call vec what do you call a dot iter on a vector it returns this iterator this iter struct and this inner struct is very similar to our my my iterator struct here it simply implements iterator so you can see here in the standard library they've implemented iterator for iter which is kind of confusing to think about but this iter is a struct type that implements iterator and it allows you to iterate over a a slice that it contains inside in fact see yeah so they uh for it since it implements double ended iterator they go ahead and use some unsafe in here but we don't have to do that so so theirs is going to be using a little bit of unsafe but we're going to try and do everything in in safe code and they do that because they implement double ended iterator which allows you to iterate from either the beginning or the end of the collection which is not as far as i'm aware possible to do in safe code because you have to basically always you have to uh ensure that when you're iterating from the front and the back they don't kind of cross over each other and there's no way to kind of encode that safely in the type system so there's a question i guess the core of what i mean is would you ever return a trait from a function um would you ever return a trait from a function so you can't return just a trait from a function like there's no way to have a function that just returns iterator here um you can return an a trait object um but that's uh that's not really it's not in scope for for today's uh for today's stream let's just put it that way um the there's no reason to return a trade object when you can just go ahead and return a concrete type that happens to uh return uh that happens to implement iterator chat is saying you you probably could uh implement double ended iterator in um yeah you're right using split last and yeah you probably can um uh yeah so it is probably safe to uh possible to do double iterator and uh safe code i don't think we'll we'll try that today um and the reason that they use on safe and center library is for an optimization um where you don't have to update pointer and length every single call um that's probably true yeah all right so let's uh let's get into this and actually implement our um our mutable iterator here and first i think the best thing to do is to try and go about it like we did before right so we want to first get the you know you know get the first element then we want to set self.slice to the rest of the list and return first element all right and as long as when we get the first element we're getting instead of a um instead of getting a immutable uh reference we get a mutable one then we should be good right so let's go ahead and try that we'll do it just like we did before self.slice dot get mute here so this gives us the first element but a a mutable pointer to it a mutable reference to it and then we can do self.slice equals [Applause] self dot slice oops oh come on all right so this is the same uh exact code as we had before um except with one two changes um before we were calling git now we're calling git underscore mute here to get a mutable uh reference instead of an immutable one and instead of just borrowing um when we try to get the rest of the of the slice uh borrowing it immutably we're trying to borrow it mutably here but this is now not compiling even though uh it was compiling with the same exact code above just with immutable references instead of mutable ones so let's let's kind of try and break down what's going on here um if we go ahead and run cargo check here we'll get some interesting and somewhat difficult to understand um errors here so it's saying i cannot infer an appropriate lifetime for auto ref due to conflicting requirements and when you see this conflicting requirements thing here you should say you should think to yourself okay i've written some code that doesn't necessarily make sense because the code that i've written says that two different things should happen at the same time which is not possible so let's take a look what that is so first the lifetime cannot outlive the anonymous lifetime number one defined on the method body okay what the heck does that mean well whenever you see this thing about anonymous lifetimes usually what that means is you have some reference here that you have not explicitly marked with a lifetime and in fact if we look at this here the next here uh function here we have a reference here to self but we've not marked that reference with any lifetime there's no tick you know whatever here right so that's what it's referring to when it says an anonymous lifetime there is a lifetime here all references have lifetimes but but it's anonymous we're not being explicit about it right so okay the lifetime cannot outlive the anonymous lifetime defined on the function body what this means is the amount of time that this borrow lives for when we're borrowing the the first element of our list cannot live longer than however long we're borrowing self for okay so let's look at the code real quick and think think this through think what that that means we are borrowing my mutable iterator for a certain amount of time and in fact we can go ahead and annotate that right here and say we are borrowing self here for some lifetime that we've called tick next which is basically however long the next function is called for so we're borrowing self for just however long next lasts for the the function next all right but when we borrow from self.slice um it's looking and saying okay self is borrowed for so for however long the next function lasts which means that slice is in turn borrowed for however long the next function lasts which means that when we reach in and get this first element here we can we can look at it for however long the next function lives for right but and in fact we can just copy this remove this code because that's that the reason that that is not compiling is a different reason we're returning that reference from next so what we've said doesn't make sense here we want to return an element here that we said should live for however long my mutable iterator lives for however long this struct lives for this element should live for but we can we are borrowing that element only for however long this next function actually lasts whoa and obviously the next function is going to be called multiple times and stuff like that that's this next function lasts for a much shorter amount of time than the mymutable iterator lives for and in fact when we look down at our code here here's my mutable iterator right here where we call you know it calls next every time it loops through right so it's calling it four or five times uh or four times here but the my mutable iterator struct itself lasts for all four of those calls to next right so we have conflicting goals here we wish to return an element that lives for as long as the mymutable iterator struct lives for but we're returning an element that only lives for as long as this next method lasts for which is a much shorter time does that make sense to everybody that's exactly what this this uh error message is saying here it's saying i don't know how to do this because i need to i need it the thing that i'm borrowing from self.slice to last just as long as this lifetime here which we've now called next and in fact let's run it again and we should get a little bit nicer of an error message so it's saying first the lifetime cannot outlive the lifetime next so however long i borrow this for cannot outlive the lifetime next this is so that the reference does not outlive borrowed content meaning i'm borrowing self.slice for tick next but the lifetime must be valid for lifetime a and that's however long my mutable iterator lives for let's go ahead and change this name here to be a bit clearer this is where giving actual meaningful lifetime names can be very helpful this right here we'll call ticketer this is the lifetime for how long our iterator actually lasts for and now it should become a little bit clearer what's going on so self dot item here or self item here is a reference that lives for however long the iterator lives for but what we're returning here is essentially this option tick next t and this needs to be mute this really really makes the thing angry we are returning an option of a reference that lives for however long the next function lasts for in a place where we need to return a reference that lives for however long my mutable iterator lives for all right and we can't do that right what would happen if we could do that well it's possible if we if we could do that that this uh mutable reference here might be invalidated um or in fact what what would happen here is we would hand out multiple um mutable we could potentially hand out multiple mutable references to the same element at the same time which we can't have right we can't have multiple readers at the same time all right let's go back one step here and please please please let me know if you have any questions about this this is why i'm doing the stream this is a very kind of like yeah if you get if you understand this then you're really starting to get uh lifetimes and rust all right okay so um let us also look at this error message here this should be a slightly different error message so cannot infer an appropriate lifetime for the lifetime parameter and the function call due to conflicting requirements again we're doing something that we should not be be doing we're trying to do two different things that don't really make sense together right so we're borrowing self.slice here for next for the lifetime next just like we were doing up above but then we're writing into self.slice here and self.slice here has to live for however long the iterator lives for so in a way it's exactly the same error that we had before just happening in a different kind of kind of way right we are trying to reborrow something for a shorter lifetime than what it needs to last for so the question becomes can we borrow um a an element or can we can we try and borrow this element for however long iter lasts for then if we could try and borrow this element for a time that matches the amount of time that iter lasts for then things will work out so we need some way of kind of uh disconnecting the first element from our our slice and saying i need this thing not to last just for i don't need to borrow this thing for however long the next function lasts for i need to borrow this thing for however long the the slice the inner slice itself is borrowed for now you might be wondering okay well why did this work up here and in fact let's go back to the old way that we wrote it before cell dot slice dot get zero and i'm going to ignore real quick that this will actually panic at runtime we talked about that before and then this is the element self dot self.slice is equal to the one there sorry and we return back so this compiles just fine even though it's effectively the same thing that we did before except with immutable um borrows instead of mutable ones why is why is this working well this is essentially working the same exact way um as down below but because we're working with immutable borrows here the immutable borrows can effectively be lengthened out um to the lifetime of of self itself because there's no problem in borrowing multiple times into the same uh the same thing because you can have as many immutable borrows as you want at one time this is the one place where i'm kind of lacking the the kind of formal um reasoning around why why this exactly works um so if anybody has any good kind of words for you know formally why this uh why this is sound here um then that would be really great to share right now but essentially um when we're when we're borrowing self.slice and borrowing the element inside of here the borrow checker is capable of noticing that we're borrowing it immutably and then it can lengthen out the borrow that it lasts for until the lifetime of the of the um of self itself all right there's some there's some people in chat saying i don't think it's possible to implement beautiful area without it let's say specifically your influence could hand out mutable references to the same element but the thai system doesn't have a way to prevent that um no there's a there should be a way around it so um that's what we're gonna get to here and this should prove to those who are kind of uh just trying to follow along um here that this is an this is a non-trivial uh piece of uh of lifetime code here so um there are some uh rust stations in the room who have probably been writing code for for quite a while and um are not exactly sure how we would go about doing this so um so this is this is great if we can come to an understanding here then we then we should be able to think about most uh lifetime code as it exists out there and in fact this caused me um when i first saw this on zoom uh or sorry on zulip uh to to pause and and really have to think through um why this works even though i write rust every single day so um so again if you can understand this code you're you're well on your way to understand almost any lifetime base code that you'll find in rest um and then chad is saying you don't it doesn't lengthen the bar well that's it's not really true and i don't want to i don't want to dive too much into uh like the pedantry around why this works um the nice thing about rust is when it works you can be you don't have to think too hard about why it works because the compiler is protecting you from doing anything too wrong right but self here is is not borrowed for tick a right self here is borrowed for some anonymous lifetime again we can call that we can make it non-anonymous call it next here so this is just like the code we have before um self self is borrowed for for next year slice therefore is is borrowed for for next year and therefore we should only like at first it might seem that we can only borrow the element inside of slice for next year but the compiler is able to uh understand that it can in a sense maybe lengthening is not the the right way to think about it but in a sense it can see through that and and see that it can last longer than uh than tick next year and and chad is saying why not declare tick static and be done well that's also possible but then your iterator is not very um not very useful then i mean chad is saying is does this mean that that the compiler deduced that tick next is equal to uh tick a um that is a possible possible theory yeah i'm not so sure i think that that that is probably right so then chad is saying uh tiknix exists as much as my iterator does so the the length of time that we're borrowing my iterator for is the same length of time that we that my iterator itself uh exists for that's that's that's another possible thing again i to be perfectly honest i'm not exactly 100 sure um why that what the formal reason is for why that code uh uh behaves that way but again the awesome part about it is you don't really have to be 100 formally sure about it um because the compiler is will protect us when it's doing something wrong and we can think through why this code should work right it's fine for us to have uh to look at an element um when we are already looking at the rest of the elements we can have as many of uh immutable views into uh a series of elements as we want at one time so kind of at a high level it makes sense all right there's a there's a little bit more discussion in chat but i think we'll we'll um stop with the the formal reasoning uh discussion for now and and get back to um how do we make this code uh actually work here and see if we can get it to to work um because there's some there there's a question about whether whether we can get this to work here um can we actually get my immutable iterator to to work properly uh without the use of unsafe and the way that we should be able to do it is by re-borrowing the slice so saying is we're going to get a borrow and this is where double pointers can be very confusing um when you're coming into uh languages that have pointers in the first place where we have a a reference to a reference to our slice here right so we're going to to re-borrow this and then essentially what we want to do is um convince the compiler that when we're when we're working on the element and splitting uh or sorry when we're working on the slice and splitting it apart that we're doing it in a way that is not messing with the is not leaving the slice in a temporary illegal state and that's an important thing to remember with with rust is that in rust we even if the if we could try to convince the the compiler um that uh from the beginning of our function to the end of the function that our code is sound uh the fact of the matter is is that for various reasons uh many of which are related to things like panicking and stuff like that we our code always has to be sound every single line of our code has to be sound it may not be always leaving our struct in a in a correct state from the point of view of our business logic but from a memory point of view we can never have any point in our code where our where our types are not in a correct state from a memory perspective and so we can pull a trick here and basically temporarily switch out our slice for another slice work on this the slice that originally was inside of my mutual iterator get it into a state and then once we get into a correct state then plop it back into um to my mutable iterator so let's let's take a look at the code real quick to see what i mean by that and i'm going to go ahead and plop down to do here so that the code should hopefully always continually compile so what we want to do is temporarily replace self.slice with something else so that we can work on what was originally in self-doubt slice and do something with it all while leaving self.slice kind of in a in a good state so we can do that with stud mem replace and pass in our slice here and replace it with an empty slice so what this code does here is replace self.slice with an empty slice so at this point after this line of code self.slice is empty and what was previously self.slice is now available to us inside of this slice variable here all right and now you know this slice variable here what lifetime does this have well this has the lifetime of tick hitter right so this slice here lasts for however long uh our my mutual iterator lasts for so now we can operate on what was previously self.slice in a way that allows us to do whatever we we want to uh as long as we operate in the bounds of the lifetime of ticket or here and chad is saying this is the thing that sort of unfortunately rarely occurs in the heat of the moment totally this takes a lot of time to kind of be able to reach back and into this uh bag of tricks and i i would say when you're when you're um you know trying to build up muscle memory for this stuff never forget about stud mem replace stiff mem swap things like that if you run into an issue that you can't fix start thinking can i use these uh these functions and stud mem to to actually solve this start thinking through that um and you know maybe you won't be able to come to a solution but if you if you ever run into a borrow checker issue and you've not thought at least about whether stood mem uh can can help you in that situation then then you're kind of doing yourself a disservice right all right so now that we have this this slice here and this slice is going to last for us however long um you know my mutable iterator is going to last for then we can then we're basically back into the situation that we want to be we can do what we did before we can use our you know our friend here split first for instance uh what is the complaint about here oh it's option of course um and we up sorry it should be split first mute here and now we can write self dot so now we're going to rewrite to self.slice and replace it with rest so sure at the between this line and this and this line here we were ending up in a in a place that wasn't right from the uh from a business logic point of view but from a memory point of view it was totally fine right so now self.slices is back to where it should be it's pointing to the rest of the list and we can use first here and say some first oops and this compiles so we were able to implement a mutable iterator and purely safe code and the way that we did that is in a way we kind of cheated we temporarily replaced self.slice with a with a dummy variable in order to get kind of full access to the the thing that cell slice was previously set to now any questions about this and if you if you understand this then congratulations like lifetime shouldn't be an issue for it for you if you somewhat understand this but don't feel like that you would be able to reproduce this on your own or be able to see when when to use this um in in your own code don't worry about that that too um we were having a discussion in chat before about whether this was even possible and so people were saying that it wouldn't be um that's because maybe they didn't think about this particular way of achieving it um which is i to be perfectly honest i mean i don't know if i would have seen this because i saw the code uh you know on zulu somebody had already written it uh then um not quite like this but but similar to it um so you know potentially um so that so we've ended up into a place uh where it works but it's not ex it's not completely obvious why it works um oh it looks like we have a raid welcome everybody unfortunately we're coming kind of to the end here but i'm going to wrap up and kind of uh go over this code again so if you want to stick around and see some rust then by all means welcome welcome but we are kind of coming to a to an ending point here um then chad is asking can you explain the two consecutive let slice lines um in rust uh shadowing variables is totally legal um if you if it makes you feel better um because you're not used to a language that allows you to shadow variables then you can you can do this this is essentially the same exact thing but you can you can overwrite variables um shadow them in a way um like this but this is also fine this is a exactly equivalent to what we wrote before hopefully that that makes sense if it doesn't let me know and i can try and explain it another way yeah and there's there's a note that's like uh i knew about stood memory play swap you know take all these kinds of things and stood men but i didn't understand that would allow me to um lengthen the lifetime um and and that's that's essentially um it's not it's not really allowing you to to lengthen the lifetime that's not that you said that but that's kind of how it came out of my mouth here what it's a what it's doing is writing in this value from source to where um your slice was pointing to before and giving you back that slice so it's just giving us this element here and this this slice here lives for for it so once we have access to this to this type then we have access to a slice that lives for for it or long and we can do whatever we need to do that's the key there is we really just want full access to we don't want to borrow self.slice we want to own self.slice and that's the that's the weird thing to think about because this is this is a reference right it's it is itself a borrow but the same thing where we where uh we can borrow owned values we can also borrow borrowed values right that's a double pointer right and so when we call self.slice here we are borrowing self.slice which itself is a borrow and that's not that's not what we want we want full access to this slice we want to be able to do with it whatever we want to and that's what stud memory place allows us to do is say hey set this thing to an empty list and let me have full access to it so i can do whatever i want with it does that make sense so does this replace the pointer and the value on the heap so first of all there is no heap involved here this is all kind of uh none of this is heat value okay i guess i guess the the elements themselves are heap allocated but everything else is stack allocated so when you think pointer you don't necessarily shouldn't necessarily think heap right you can have pointers to things on the stack um what it is doing here is replacing the pointer that lived at at the inside of this slice field with another pointer a pointer to an empty list so essentially like a null pointer a pointer where we just make a promise okay never use that pointer and then we get full access to the previous pointer which was pointing to all of our elements we can do whatever we want with it including breaking it apart which is exactly what we do at split first mud here all right so um i'm i'm taking this very slowly but it's probably for a lot of people still extremely fast so i want to go back through one last time to explain the full code that we looked at today to explain how things work um and i'm gonna post this to youtube as well so feel free obviously to watch it again let me know if you have any questions as well and i'm happy to answer them um and again this is kind of real tough stuff when it comes to lifetimes and rust so if you understand this you're really well on your way to understanding basically any rust lifetime code that you will see all right so the first thing that we did was we had a my iterator struct that simply racked a slice and of course we have to then tie the lifetime of my iterator struct to the lifetime of the slice inside so these two things however long the slice lives for my iterator will live for as well all right they're basically tied together then we're going to implement iterator for my iterator all right and it's going to when it iterates it's going to yield out um elements that are references to elements that live for however long my iterator lives for right so again we can't have an element that lives for longer than my iterary lips for they're tied together they have the same lifetime in fact we can see that tick a here tick a here all the way down and so for the immutable case it's pretty easy we can call self.slice.git to get the first element here then we can just set self.slice to be the rest of the slice and we return the element now there's some this will this will panic um if we were to run it at runtime if when the when we get to the point where self.slice is empty so this is actually a better way to write it uh whoops here where we call self.splice that's split first which simply splits the slice into the first element and the rest of the elements and this checks uh if the if the slice is empty and so it will return an option and we can simply use question mark here to say hey if it's none return early here and then we set self.slice to rest and return our element so these are equivalent to each other except we get a built in check for the empty slice here all right now when we go to do mutable iterators we have the same exact thing we're using nicer uh lifetime names and i encourage people to use lifetime names tick a is great when it's simple stuff when you when you don't really want people to care too much about the lifetimes when it's obvious but in this case where lifetimes might be a little bit tricky and you want to be explicit about them and how they relate to each other giving them nice names is very important here so we're giving this lifetime the lifetime of our inner slice the lifetime of our iterator ticketer that's however long the the iterator lasts for and then here when we implement it we know that the element that we're yielding when we iterate lasts for however long our iterator itself lasts for right and then we have to pull a little bit of a trick here because if we tried to implement it in the way that we did before where we borrow the inner element with self.slice.getmud here we were trying to we would try to borrow tick next uh sorry we would try to borrow the element for tick next lifetime because that's how long the borrow itself lasts for but we want to borrow it for tick itter and they're not the same lifetimes so instead we pull a little bit of a trick where we say okay i really need to operate fully on this slice right here what i'm going to do is replace it temporarily with an empty slice and then i get access to this slice and i can do whatever i want with it i have full access here in a sense i own this reference which is again a bit of a weird way to think about it because it's a reference we don't think typically about owning references but that's what we're doing here we're owning this reference we can do whatever we want with it because we own it and so we you know we can call split first here and do what we did up above and we can write to self.slice here with with the rest here right so yes it is it is true that on this line on line 28 right here self.slice is going to be empty but that's fine we we always keep self.slice uh correct from a memory standpoint even if it's not necessarily correct from a um from a business use case standpoint but it doesn't matter right it's fine all right any questions about this again go over the code try and try and see if you can understand why it's working and in fact we got into a discussion earlier about we weren't 100 sure we were sure why this code here doesn't compile but uh there was some discussion about why the code up here is allowed to compile what is the formal reason for it and and we didn't really come up with a and at least in my opinion chat may disagree with this we didn't come up with a really 100 satisfying answer for that um for why this uh is what is the formal reason for why it compiles now the high level reason it should be clear like we can borrow the first element for however long we want to as long as you know all the way up to however long the slice itself operates for and chad is saying without comments i kind of get this i wouldn't see a problem with doing it from a logic standpoint if it was commented okay yeah if this were production code and in this particular you you know when you're doing something to kind of get around a lifetime issue then it's probably a good idea to write some comments so i would definitely agree to write some comments here about why you're temporarily replacing self.slice so that you can operate on it all right that's uh that's it for today um i have one last uh request from everybody it would be super amazing if you could go ahead if you like uh the content that i'm doing on twitch i'm trying to do it every week it helps me a whole lot if you can go ahead and subscribe or follow me on twitch and it lets me know that people actually want to watch this stuff so please if you can i hear some people doing that already thank you very much please go ahead and do that for me that really helps me out because it lets me know that people actually want to see this so if you want to see more of this kind of stuff please give me a follow let me know you can see up above at the very top of the screen my my github handle my twitter handle and where you can find me on youtube as well if you're watching this on youtube later uh later on um i'm on twitch right now it's twitch.tv slash ryan levick all one word there so you can search for me um and watch me live and i tweet about it when i'm going to do it on on twitter so make sure to follow me there as well i know it's sounds like i'm just asking everybody to be my friend but really does help me um uh to uh you know stay motivated and and to produce more of this material so i really appreciate that um cool well then i think that's it for today um i'm gonna go start enjoying my weekend um and i hope that everybody else has a good weekend whenever that one arrives if you happen to be in the us unlike me or if you're a u.s citizen then remember the election is on tuesday so please go vote i just got word that my vote was counted so i'm very happy about that um i hope everybody who is not in the u.s um still has a lovely tuesday next tuesday and uh without further ado i hope everybody enjoys their weekend and i'll see you next week alright

Channel: Ryan Levick

Views: 15,107

Rating: 4.9698114 out of 5

Keywords:

Id: MSi3E5Z8oRw

Length: 81min 6sec (4866 seconds)

Published: Mon Nov 02 2020

Reddit Comments

[u/scoobybejesus]

This was great, but please help me crystallize the lesson in my brain because a couple things may not have actually been stated explicitly (or I missed it, so please forgive me). I have two questions:

1. Is it true that under no circumstances is there a way to pass a struct's lifetime parameter to a function in the struct's impl? (Seems like a nice feature.)
2. Is the solution to this problem always a std::mem::replace() (or possibly similar std::mem workarounds), or are there other examples of clever workarounds?

Thanks!

[u/theollyr]

EDIT: wrong godbolt link

(first time posting a comment on reddit after lurking here for many years, but I'm getting back to Rust and not understanding the detailed behind-the-scenes really bugs me)

I loved the video as it made me think more deeply about the lifetimes. What irks me here, though, is that to me this doesn't feel like a solution but more of a hack/workaround. Could there be a "more proper" way to communicate to the compiler that

• self.slice really has a lifetime of 'iter?
• we will return (move out) the only &'iter mut T in existence?

I don't mean this as a dig at Ryan (the stream author) but more of could we find/create a better way? Using std::mem::replace seems like hiding the unsafe (and possibly dangerous) operation of making the compiler forget the lifetime and assigning it our own behind a "safe" face. In that case I think using unsafe, e.g. like this:

pub struct MyMutableIterator<'iter, T> {
    slice: &'iter mut [T],
}

unsafe fn forget_lifetime<'a, T: ?Sized>(t: *mut T) -> &'a mut T {
    &mut *t
}

impl<'iter, T> Iterator for MyMutableIterator<'iter, T> {
    type Item = &'iter mut T;

    fn next<'next>(&'next mut self) -> Option<Self::Item> {
        let slice: &'iter mut [T] = unsafe { forget_lifetime(self.slice) };
        let (first, rest) = slice.split_first_mut()?;
        self.slice = rest;
        Some(first)
    }
}

would be much more clear on what is actually going on without hiding it behind the jargon of std::mem::replace.

Also looking at the assembly (https://godbolt.org/z/M4oa3f), the std::mem::replace seems to be doing unnecessary work when all we want is to just adjust the semantics of the compiler.

Btw, maybe a dumb question, as I read it it seems that generic types do not include lifetimes? Looking at the signature:

pub fn replace<U>(dest: &mut U, src: U) -> U

(I changed the T for U as we use T in MyMutableIterator). When we do std::mem::replace(&mut self.slice, &mut []), the type of self.slice is &'next mut [T], the &mut self.slice should be &'next mut &'next mut [T], therefore U = &'next mut [T], shouldn't it? And in that case the std::mem::replace shouldn't solve anything.

Maybe I'm just overthinking everything here :D Thanks.