Rust Linz, August 2021 - Rainer Stropek - Rust iterators

so my session for today is about iterators i would like to spend an hour or so depending on the number of questions that you have an hour or so on this topic and tell you what's new in rust 153 which came out a few weeks ago and i would like to take this opportunity to dive deeper into iterators let me quickly shut down this one here so now it's good iterators are interesting iterators are very interesting i know them from various languages that i use typescript c sharp and so on and when i learned rust iterators were one of the first things that i was really interested in so i take i took a close look and for me it was rather surprising that it took rust so long to be able to just iterate over a bunch of for instance numbers in an array and this will be the main part of my talk today i would like to talk about iterators especially in conjunction with arrays and i would like to dive in some very important rust properties that are the reason why it took relatively long for us to learn these tricks for iterators and arrays if you want to ask any questions if uh something is new to you if i'm too fast or too slow give me feedback ask questions by using the chat window in youtube or you can also ask questions in discord i will take a look at questions on the discord server after my talk so now let me share my screen with you here um you see uh the the storybook it's just a quick gathering of notes what i would like to walk you through today so if you find some code snippets interesting you can take a look at this url and copy them out everything else will be done live okay with that let's dive right into it the first thing that i would like to show you is i would like to show you the old version of rust 1.52 and show you what we had what problems we had there so let me quickly oops sorry wrong one now we are ready uh let me quickly run a darker container with rust 152 okay okay here it is let's go into visual studio code and open up visual studio code within this docker container so now i am in visual studio code connected to this uh to this docker container and let me quickly here uh install the rust analyzer here yeah okay it's already installed in this docker container that's fine that's good ah i just broke that one so okay let's go here create a directory rust demo demo here we are and open this folder up here in my docker container so open a folder and here we are that's good ah this this demo broke so let's reopen this one here maybe it works at the second try again start ah now it looks much better i think yes much better here we are and now i can i think i can also yes check the language service installed everything is fine we are good to go sorry for the quick glitch i had some problem opening connecting visual studio to my docker container but now it seems to work let me quickly start a new demo here with cargo new here we are and open up the uh the code here looks good everything is fine okay so if we quickly type in some code here let me do that uh for instance let's define some numbers here and let's do them something like this this is just a numbers array nothing special so in the good old times prior to 153 i had a problem when trying to do the following we are and if i want to say for instance print line something like this and something like this print the numbers something like this i had a problem this doesn't work or this didn't work because an array with a fixed size of 5 did not implement the proper traits up to rust 152 this changed in 153 what you could do in rust 152 is i could change here that one to a reference and that brought me you see it here a reference to the number so i could already do an iteration through an array by reference this gives me a reference and i can prove to you that this is really a reference by for instance doing a print line here and for instance here saying let's print oh sorry let's print the pointer let's take the address of numbers zero something like this and then here let's print the address off n which is just a reference here and if i run this guy cargo run run cargo sorry cd and now to cargo run again you will see that the reference of the first element in numbers and the reference which the iterator gave me here are exactly the same they are referencing to the same address in memory so we are really iterating over uh over we are really iterating by reference that this is really a reference you could also do a mutable numbers here and for instance add another for loop something like n in uh this time let's take a mutable numbers something like this and then we can also say star n multiplied by two for instance something like this and if i run it again you will see that my values change so i can iterate by reference or by mutable reference over an array of numbers this has been possible for quite a while in rust and it has been possible in rust 152 also and in rust 153 a few months ago things changed a lot we can now iterate by value over a race so let me quickly demonstrate that by quitting my rust darker container 152 and go to my machine which runs a newer version of rust where i can do nearly exactly the demo as before i will copy the code and now a big difference occurs iterating by value so here i have uh opened my here it is i have opened my environment let me quickly exit from here and do a cargo uh new iter something like this go into the iter folder and open that one in visual studio code as i said this is a newer version of rust this is on my local machine and i will quickly paste in the code that we just wrote but this time the big difference is let me get rid of the mutables here we don't need that one i can now change the ampersand here and that in 153 gives me an iteration by value i can now simply iterate over the values in the fixed size array and if i cargo run this guy you will see that i get the proper values i don't even have to store that one in a variable i can put that one directly in the for loop nothing special here and it will still work so this is what really changed in 153 well you could ask yourself hmm are we done is that all is the talk now over no it's not oh it's just the beginning i wanted to demonstrate to you what's new and now based on that we will dive deeper into what's going on behind the scenes so we will take a look what these iterators really are we will take a look at the source code in rust we will try to re-implement some aspects of iterators on our own to learn more about the inner workings of iterators and then we will take a look at why it was so difficult for us to offer this seemingly simple functionality so we will check out so-called const generics and we will check out some breaking changes which the which the rust language team has to uh has to had to solve uh so that this great feature became possible in 153 okay so with that i think we can uh get started okay i see some first um questions coming in in um in discord i'm very sorry i have to discord quit this chord for now oh i just saw that you asked me to um increase the font size of course of course i will do that so here yep thank you very much for uh for pointing that out please give me feedback if the font is still too small uh the big chunks of code will start from now so i hope it is not too late okay there we go nice so let's dive into the the most core abstractions oh so good thank you very much the most core abstractions which are behind iterators the next part might already be known by those in the audience who already have a very good noah or a good know-how in rest and who have already written a decent amount of rust code but maybe we have some beginners in the audience who for whom this might be new so in every programming language if you want to build something like iterators and helper functions on top of iterators you need a basic abstraction you need an abstraction for an iterator what is an iterator an iterator allows your code to iterate over a collection of values read only forward only so you cannot change the content of the underlying data structure and you can only go forward we will see that read only is not 100 correct here in rust but let's say for the sake for for for now that this is what we understand of an iterator we iterate we go through we walk through in our code the elements of a data structure and by having an abstraction we can build helper functions like sum filter mapping minimum values maximum values and things like that over all data structures which fulfill these abstractions so it doesn't matter if you store your data in a vector or an array or anything else as long as this data structure fulfills the requirements or has the capabilities of the common abstraction the iterator abstraction you can always use this generic helper functions like summing filtering mapping and so on on your data structure so what are the most basic abstractions in rust for iteration now the first one is let me show you that one here let me go into my browser and fire up this link that i've prepared is this guy here this guy the one is the into iterator trait the into iterator trait is the most basic trait which allows us to ask an underlying type for an iterator it only has a single function which is called intuitor and it will return the iterator you see it here now the iterator is an implementation this is an implementation here um and as you can see here self intuitive and the iterator again has to fulfill a second trait which is the second basic abstraction for iteration in rust it is called iterator so if i follow this link this will bring us to the iterator trait here and this iterator iterates over elements of type item as you can see here and it has a lot of functions luckily if we implement our own iterators all these functions starting here are not interesting for us because as you can see here with the these three dots they have default implementation the only functionality in this iterator which is really important is the next function this is what we need to implement if we have a type which should be a we should we should participate in this whole infrastructure of iteration we need to have an iterator which implements the next function and this is what i meant with forward only iteration there is only a next function there is no previous function and all the rest like counting summing and many many other functionalities we get them for free because they sit on the shoulder of this giant here they are implemented based on the next method so remember that one into iterator is the capability of a type to be asked for an iterator and the iterator itself is a trait which offers a next function these are the two implementations if we want to take a look at the source code i have a deep link in my storybook which i mentioned at the beginning of my talk this is let me zoom in a little bit this is the into iterator trait in the rust uh github repository as you can see this guy is pretty old this abstraction has been there nearly forever and here you see exactly what we saw in the documentation we have the type of the items over which we enumerate in our case it wasn't an array of numbers integer 32 so this is the item type in our case integers 32 but it can be any type you want and here you see the implementation of the iterator you see of the iterated trait if i scroll down a little bit we see this into it function which returns the implementation of the iterator you see it here it is the functionality which which with which i can ask a type please give me an iterator for you for this specific type if you have a rust vector and you want to iterate over the elements in the vector you ask the vector by calling this into it a function and it will give you the implementation of the iterator for a vector that you can use to iterate over its value and the same is true for every every collection type that exists in the rost universe that implements and wants to play with um with iterators so let me quickly go back to our code sample here and change this a little bit okay so let me undo that one take the values here and get rid of that one let's put that one into a backdoor so that we don't no longer have an array here just to have something different and now we can say four number in numbers you see it and then we can print line the sorry number here this is possible this in numbers is possible because if we take a look this is the type vec so if i go to vac then i can look up in the documentation that the structure vec implements the into iterated trait and with that just because the vector implements into iterator the rust language compiler knows that in this for loop it has to call the into it functionality to get the iterator and then uses the calls to the next method to iterate through the elements and what we get through what we get back are elements of type integer 32 this is essentially what's going on behind the scenes to get a closer understand a deeper understanding of all this stuff let's implement a custom iterator to be more specific i would like in my next demo which will take a while i would like in the next demo i would like to implement a generator a generator is a special form of an iterator where there is no real underlying data structure but we are generating the values on the fly i've chosen this sample because i think it's a good way of looking behind the scenes of iterators and understanding what's really going on now for the next demo i will copy in line by line some prepared lines and again i copy these lines from the github page that i showed you at the beginning of my talk and i will also share this link in the discord server after my talk so you can take a look at it okay let's get started first here we need a use statement let's put that one because we need a random number generator next we need a structure and this structure will be called passwords why did i call it passwords i called it passwords because i will implement a password generator it will be a very naive password generator so it will not generate strong passwords here but hey bear with me it is just for the sake of demoing iterators it is not the world's best password generator now this password generator has one parameter which is the length the the the length that the user would like the password to generate its passwords to be now let's quickly implement this password generator structure some basic functionality we will implement a new method which will return by default a password generator which passed which generates passwords of length 10 okay and we also implement a helper function which is called with length there you can pass in the length and it will give you a password generator with the specified length you see that here okay so i think i can also get rid of exactly that one okay that looks uh more idiomatic let's put it that way this still has not really some functionality in it of course we could discuss whether it would be a great idea to implement the default trait here but that's out of scope for today we will jump right into the implementation of an iterator in order to make this password a generator a password generator we need to implement the into iterator trait that i introduced you to a few minutes ago so let's implement into iterator into iterator for our passwords struct the type the item will be string because we generate passwords and those passwords are of type string now the implementation of the iterator itself will be the passwords iterator which we'll we'll have to implement in a second for now just except the curly uh the the rats quickly is here they are fine we will need to implement this guy in a second and now we can implement the core method that we mentioned before we can implement into iter like this it gets a cell here and it will return the it to enter the iterator implementation okay here we can return the password integrator iterator which we will implement in a second and just for demo purposes we will path pass on the length that the user has chosen for our password generator just like that so this is the functionality with which the for loop of rust can ask our type passwords for an iterator it will call into itter and we have to return an implementation of the iterator which we will have to write now this was the first step implementing the into iterator trade now let's go on and implement the iterator itself so let's create the passwords iterator this one as a structure and here we again have our length of course we cannot as you can see here use passwords iterator already here because it does not implement the iterator trait it's not yet an iterator it doesn't have a next method so let's write the next method and implement the iterator trait import iterator for passwords iterator the item we can copy it from here is still a string of course our generated passwords will be strings and that's fine like that now we have to implement the next method let's just implement the missing method here that looks pretty good the only thing is this to do which is not a good idea we will have to write some code here now let's step back for a second now the rats quickly is here are gone because now our password iterator is really an iterator and offers a next method the next method will return the next item optionally optionally means that we can always return none if we have reached the end of the iteration now before the system calls the next method the first time the iterator stands kind of in front of the first element inside of our iteration and once we call next we will either get the first element in the iteration in the underlying data structure or generator or we will get none once we reached the end in our case we want to have an iterator which can generate an endless number of passwords so we will never return none we will always generate a random new password okay let's do that let's first let mute result create a string and we can already create it with capacity and say we can use the length because we already know how long the string will be because we know the length of the generated password now let's write a for loop to generate the letters of the password for in zero self length something like this this will give us a for loop uh which it which gives us which iterates through this whole for loop self don't length amount of times now we can push into some new letters and here bear with me it will not be the best random password generator as i mentioned before so let's quickly take um let's quickly take uh the byte value of the letter a and add the random thread random number generator generate range a random digit here and we do do that by saying give me zero to uh let's take this one the c value minus the a value so a a value between 0 and 25 including and this will be this one as char something like this so let's see what i did wrong here um this is that one that looks good and we have this one something like this and we have the random number generator and at the end we can return some results something like this so let me quickly see what we have here and declared i thought i used it up here oh of course of course i forgot something in the cargo tunnel i need to reference the uh the rand crate otherwise it will not work so let me give it a second and cargo builds and which do i have i think ah let me quickly i will not look for the typo that i did here so i will just copy in i see what i did i don't need to copy anything i just forgot to be here and now it looks good now it looks good now the code compiles let me quickly show you again what i do i allocate a string with a given length and then i have a for loop and here i just push in the letter a plus a random number between 0 and 25 uh get to 25 by subtracting c from a oh sorry a from c and convert it to a char that looks pretty awesome so now we have the into iterator trait and we have the iterator trait so we now have an iterator in this case a generator which can generate an endless amount of passwords and now we can really benefit from the functionality that we get in rust built on top of the iterator abstraction let me show you what i mean four pn passwords this one new into it see that one and now i say and this is the important one take three otherwise it would run forever but by specifying take 3 like this one of course i need a dot here not a not a colon here yeah by specifying the take 3 it is no longer a problem that we generate an endless amount of passwords the iterator function take which is built on top of the next function will stop after calling my next function for three times and here i can simply do a print line uh the next password oops sorry password is that one okay let's run it cargo run let's see what we get and get oh my god we got three different passwords three different passwords which we can generate through the iterator abstraction by calling into our into eater scroll up into it will generate the passwords iterator this is the guy here this implements the iterator method this implements the next method and the take 3 will make sure that the next method will only be called for three times this is what i wanted to show you this is what i wanted to show you so you get an idea of what the core abstractions for iterators in rust really are and of course we can also write it in a different way i will copy this one in because it is essentially the same just a little bit in a different notation you see again i can use the width length functionality that we have implemented above and say i want to have five lecture passwords into it again take three and then use the for each method to print the next password so if i run this guy now you will see we have the ten digit passwords and the five digit passwords exactly what we wanted to have so the last 10 or 15 minutes something like this where primarily for rust beginners or those who have just used functionalities like this or this or some or filter and things like that but i have never bothered to take a look into the details of how iterators really work now you've seen it and now we have implemented our own custom iterator so it's a good time to take a breath because now we are starting in a new sample and we will dive into dive deeper into some more advanced functionalities of iterators and maybe some surprising things especially for beginners in rust surprising things with iterators and the first topic will be consuming iterators let me show you what i mean with that let's get rid of this example don't need that one looks good and let's do the same thing that i did before let's create a vector off some numbers this time let's take some fibonacci stuff 3 5 8 13 something like this looks good now let's print the minimum number of this this vector okay print line nothing special here okay the minimum is curly braces and say numbers dot into eater this one dot minimum and we are sure that the element that there are elements in this array so this should be fine check it out let's run this guy and okay i don't need the use anymore let's get rid of that one near it and run it again and we'll see the minimum is one this is exactly what we expected what you might not expect if you are a beginner in rust is this problem let's print the minimum two times oh my god so many reds quickly just by displaying the minimum number two times well the reason for that is the way that into it really works so if i go back here and if we take a look here at into itter we will see that into it takes ownership of self it consumes the underlying data structure we cannot use numbers after line 3 anymore because it was moved it was moved into the iterator and therefore we cannot iterate twice like this of course there is an easy way to get around that if we say numbers is no longer the vector itself but if we just borrow a reference to the vector so numbers is now a reference to the vector everything goes away we have no longer a problem because now the type of into iter is no longer the vector but a reference to the vector and now i can run this guy and we will get the minimum successfully twice this is exactly what we need to do note that we did not have to change anything here unlike c plus there is no arrow operator like this if we have a pointer this is how the the dispatching of methods work in rust it's really a core piece of infrastructure for making ownership work in practice that even if we have a reference we can just type in a dot and everything is fine so again cargo run and it simply works as an alternative we could also let's put it that way use two other functions well i will demonstrate just one of them i can use the inter function here something like this and then everything is okay you might scratch your head and say what's utter we just had into it why now is it another trait no it's not the itter function it's not coming from a from an uh from a trait it's by convention returning a by reference iterator over the underlying data structure so this one this iter is automatically iterating by reference and therefore it doesn't take ownership of the underlying vector and you can call it two times but the behavior is just defined by convention and not by definition of a trait there is also an ita underscore mute function which you can use if you want to have a mutable reference okay this is maybe a little difficult so i would like to walk you through some additional lines of code another example a more elaborate example where we take a close look at this into itter and references and iter and intermute because i think at least it was for me when i started with all this this thing this when to use it and when to use into it and what's exactly the difference this really gave me a lot of headache and this headache i would like to spare you this headache okay by showing you um some some simple things let's define a struct because always using just hints is not funny so let's define a point struct and let's add some 64 floats here f64 it is just a very simple point here good now let's create a vector of points left points equals to vector and here let's say we want to have a point this one x should be 1.0 y should be 1.0 and then we add a second point this one this one and this will be i don't care it's it's really not important too so now we have a vector of points the first one has one one and the second one has the value to two so what we can do if we want to have the first point let um first point you can say points dot into inter this one drop next dot unwrap one and as you can see the type which we will get back is the point so in this case the rust compiler iterates or makes and calls the into iter with the type of the underlying data structure which is point as you can see it here it is a vector of point so this is what i get back i iterate over the points by value this is what i do here by value iteration that is kind of obvious now let's change that a little bit let's redefine the points here i'm just shadowing here so exactly the same points again but this time i'm going to do it a little bit differently let mute we want to have the iterator and now i will do the following i will say take the address of points and call into iter this one that will give me an iter which is the implementation of the iterator over point but now check out what what's happening let first point this one equals to it dot next dot unwrap see what's going on now i iterate by reference because here oops sorry here i have a reference to the the vector into itter immediately understands although it's the same call as up here above it immediately understands that it has to give me an iterator an iterator which iterates by reference so first point is now ampersand point the reference to point very important thing and this is the magic of intuitor it understands whether you call it directly on the vector or on the reference to the vector and will give you either the value or the reference which is inside of the vector and this is where the inter function comes in that i told you before so instead of writing this guy here i can say points.eater see that is a shortcut for this rather complex syntax here in the background here in the back here of this line so ether by convention what did i tell you ether by convention gives you a by reference iterator over the underlying data structure so if you definitely want to iterate by reference call iter and then everything is okay you don't need to write something like this which is smart but kind of different difficult to understand points that either is really simple and now you know what it does it gives you an iterator by reference iteration something like this now we can also do that uh by oh i don't need to that one i don't need to do that one of course yeah no no mutable here um yeah of course they correct i need to be mutable sorry sorry sorry it's fine a mutable thing that i want to demonstrate now sorry i just got distracted um comes down in the third demo let's redefine the points again here this one but this time let's make it mutable okay now we have them mutable now let's define again the iterator and this time i will not call points.eter which we did before immediately here but this time i will write it underscore mute and that will give me an iterator over mutable references of the underlying vector so that would be equivalent to writing on the ampersand mute points dot into it okay that is essentially the same just as here above we could write address of points dot into ether and now we can say mutable reference of points into it that would be exactly the same so now let's get a let first point equals to it dot next dot unwrap something like this and you see i now get a mutable reference to the point let's write it down okay just to make sure that we are absolutely sure what we are doing here and with that i can now say first point dot x equal 3.0 and first point dot y equals 4.0 and i can print line i can print line um something like this and say give me the first point and of course we need the derive debug up here otherwise it will not work let me give me let me give that a try and you see the point has changed so it worked we could retrieve by mutable reference iteration here we got the mutable reference and then we can change the values in the underlying vector and i can also maybe print the it's here maybe that one is also interesting and you see the values also changed inside the vector it was not just just changed here in first point because obviously this is a mutable reference pointing into the point of the vector okay okay um i have a question here the question is will next return second element or last next will if you call it for the first time it will give you the first element if there is one if the collection is empty or the generator cannot generate any values it will give you none it is an option okay that is important once you are at the end and you call next you will definitely get none because then it's over the behavior by the way if you call next again once you got none is not strictly defined an iterator could decide to start from scratch and start from the beginning and return you the first element in the uh in the iterator for instance or the iterator could decide to give you non again that is defined by the iterator there is no definite rule for that i hope i could answer the question with that okay nice so now i hope you got a better understanding what this into iter is you understood that intuitor will give you a by value iteration or a by reference iteration or a by mutable reference iteration depending on the context here we have the by value here we have the by reference here we have to the by uh mutable reference call the difference there is no difference in calling into ether okay there are multiple implementations of intuitor and the compiler will choose the correct one for you if you want to make your code a little bit easier to read then use the iter function if you want to iterate by reference or the intermute function if you want to iterate by mutable reference nice breathe in breathe out new topic let me go into the rust playground for the next demo here and the next demo that i would like to show you here is the topic of serial cost abstractions many people ask themselves oh sorry i have to copy it here i can copy it now i copied it and i of course i know i know i know i have to zoom in so this is a very very simple uh a very simple loop and many people ask themselves when working with iterators okay how much is the the runtime costs and if you take a look here we calculate the sum of all values between 0 and 9 so i'm just adding to the sum and at the end i print it let's run it and without any surprise it returns 45 that's okay but that's not what i'm really interested in let's do something else let's take a look at the assembler code here okay so if i scroll down and down and down and down and down and down and down at some point we will reach the main method where is it where is my main method if i will not find it immediately i will look it up and where is it where is it i have to look it up ah here it is uh without going into any details here um okay here we call the something like this and if we take a pool look if we take a look somewhere ah is that that's typical i can't find my here we see it okay here we see it here you see playground main i finally found it sorry it's not so easy for me to read uh assembler code while demonstrating so uh please don't be angry with me here you see that we are doing a bunch of move statements and so on but at the end of the day you see the call to intuitor everything is fine and at the end we will also see the call to the print functions nothing special so we have some runtime costs well not really if you take a look at what i did you see i selected debug and if you select debug and you compile your ros code we all know you get pretty slow code okay you get pretty slow codes and it can be optimized a lot so bear in mind this one with debug calls the interneter and does essentially all the things that i demonstrated to you a few minutes ago so bear in mind if we run this guy come on run it the result will be 45. so now let's switch to release and take a look at the assembler code again oh my god i have to scroll through assembler code again let's see whether i will find it yeah here is and see that one isn't that awesome there is no intuitor anymore the compiler understood that it can calculate the result during compile time and give me the complete result directly as a constant in the code and immediately called display trait in order to be able to print it on the screen so that is kind of obvious you see it really works it still works and it is it is oh sorry i wanted to run it here it still works it works pretty well and here you see 45 but now there is no intuit anymore so this is a kind of very simplified example i knew that okay granted it's very very simplified but it demonstrates the point zero cost abstractions in rust mean that when you use iterators you should not let rus let yourself be fooled by looking at assembler at generated assembler ll db or llvm code in debug mode because there you will see all the overhead of iterators but once you compile to release you will see a very different beast maybe you don't even see the iterators anymore it is optimized to a very large extent and i wanted to make it very clear to you by using this kind of naive example granted but still it demonstrates the point don't think that iterators when compiled to release mode will work as as it is in your mental model that you might have in your head the compiler will optimize it to a large extent and the assembly code will look very different compared to what you might be what you might have as i said as a mental model in your mind okay okay good nice good good good this was zero cost abstractions so with that breathe in breathe out new topic let me quickly take a look at the questions i think there is one um okay here we have a question let me quickly read it is there any convention how to write code let mute variable into iter or let mute variable vector into a vector iter mute i'm not 100 sure if there is a hard best practice here but i would use the second version yeah i would use the second version it's easier to read it's completely clear what is done it has for my personal uh experience less magic going on behind the scenes so i would definitely prefer the second version here okay good nice good as i said breathe in breathe out new topic the next topic and the final topic is why did it take so long for rust to enable this thing here by value iteration for arrays it is so obvious to write four number in array one two three four five that it wasn't clear when i started dealing with rust why this functionality isn't there so two things were pretty difficult when building this implementation and i would like to demonstrate both of them okay let's go back here and uh start another darker container run this one and run rust uh 1.50 okay let's run a darker container with rust 1.50 let's create again a ros demo folder this one ros demo and let's go back to visual studio fire up my remote development tools and fire up a new visual studio connected to my container which runs rust 150 okay oh i'm in the wrong folder here so let's go up oops up one here and go into ros demo and open that one here we are good uh here we are let's cargo new uh another demo here and go into the iterator and let's take that one good for the next demo i am going to write a few lines of code and also copy a few lines of code imagine the following situation we want to implement a trait that tells us whether an array is ordered it's just for demo purposes the code doesn't make very much sense but it's just for demo purposes so bear with me i want to demonstrate the problem and what has changed approximately in march this year okay so let's write this straight let's collect these orders and add a function is ordered which returns just a boolean nothing special as i said the code doesn't make very much sense there are other traits which which you can't use something like this but we want to implement that ease word for whatever reason just to understand what's going on behind the scenes now let's try to um to apply this now this is order trait to an array so down here we will say let ordered equals two or left numbers this is what i wanted to say um this one one two three four that's fine and then let's print weather sorry print weather numbers is ordered okay something like this obviously this doesn't work because the trait is ordered is not implemented on an array of four elements of type integer 32. so what we have to do is we have to implement we have to implement the is ordered trait for an array of t so we need uh here type here but the problem is that as you might already know that an array in rust has a fixed size so we have to specify the size let's do that so we want to implement it for an array of size two we have to specify the size it is necessary here and then in order to be able to implement it let's say this has to be ordered and copy okay something like this so the content has to implement the ord trait which gives us a nice compare function and it has to implement the copy trait in order to be able to copy the elements from the array so let's implement the is ordered functions something like this and let's quickly write a few lines of code to have this done it's it's pretty simple first let's say if this one if the self length this one is 0 or 1 by convention we say then return true then the collection is or that the array is ordered okay essentially we don't really need that one because we have the length here but bear with me we will need this code in a second for now just accept it it's okay then we iterate over the elements in our array not difficult let mute preferences prep previous is none and then say for item in self note that our item is a reference to t because this is how iteration in rust prior to 143 really works if some item is lower than previous and we can say return false otherwise we just advance the previous one by saying some item and at the end if we managed to go through all the elements we know that there is no item which is smaller than the previous so we know it's ordered ascending so this might be a naive implementation of check whether our array is ordered see it here okay good that looks uh pretty awesome and with that we should be able uh oh sorry here we should be able to call this orbit and yes as it happens it now works it works perfectly fine and you can try it cargo run uh sorry again cargo run yes it's ordered and if we mess up let's see cargo run false and that looks very nice but what happens if i add another digit here everything breaks because here as you can see this doesn't work this doesn't work because this has a constant size so i would need to copy this guy here and implement it again for the size 5. of course this doesn't make any sense but now at least the code compiles it works for five what would you do if you have an old version of rust you would probably write a macro this has been done for you so you don't need to write it yourself but you would write a macro in order to generate implementations for this nice little trait for arrays of different sizes that is not a good idea so what we essentially need is we need let's get rid of this guy here because it's so so so ugly what we essentially need is we need here this one as a parameter and this is what we call const generics so what we essentially would need we would need to be able to say this is when and when as you can see here is a constant number of type you size this is what we want to do and this came in rust 1.51 and was a very very important precondition for implementing by value iterations over a race so let me prove to you that this really works let's take that one and let's forget about this old stuff in uh in in uh in rust 150 or so and let's replace this one this guy here with a new version of rust and you see the error is gone it now works this feature is called const generics and it came with rust 151 in march 2021 2021 so this was an important step towards this simple feature of being able to write four number in array one two three four five we needed const generics and it came with rust 1.51 so now you also learned what const generics are and maybe you weren't you weren't looking at this rust feature before and now you got some additional knowledge of rust out of this demo not just about iterators okay very good um there i have a question the question is uh it's just back of t because the vect doesn't have a fixed amount of elements exactly correct that is exactly correct and that is why why you do not need const generics for vectors and that is why why iteration worked very early very much earlier for vectors than it did for a race because arrays have a fixed size okay good oh thank you uh thank you ono for pointing out that i missed uh us uh a bracket in the print line statement i i found it myself luckily but thank you for for pointing it out okay now why didn't this by value iterator over constant arrays come with rust 151 because we got const generics so why didn't we get it immediately why did we have to wait for another two versions until 153 to get this feature well for that we have to understand that that that building implementing into it into iterator for const generic arrays would have broken a lot of code and i would like to demonstrate to you so you understand what was the problem it is it's a kind of history lesson because now it just works but by learning this history lesson you hopefully get some deeper understanding in how method dispatching works in in rust and so on and yeah maybe it's just interesting i hope so so let's write and copy a little bit of code so let's get rid of that one and i see i already spent an hour and i announced that this talk will be an hour so i will copy a little bit more of the code and not write all this code so uh yeah this is just a history lesson but hopefully an interesting one let's define our own data structure let's call it my array obviously it's not an array it's a is a useless structure because it contains only a single element of type phantom data if you are not familiar with phantom data phantom data is what it says it is it is just a phantom data item it has size zero it goes away when you compile this code to release it doesn't exist it is just a placeholder any underlying data structure will be here and i call it my array because i implement the data structure my array please use your imagination my array is some fancy own array and it has some fancy inside data structure we really don't care this is not the point here we also do not want to use the into iterator trait that rust has built in we implement our own my into iterator this is exactly a copy of the inter iterator trait that i have demonstrated to you at the beginning of this talk so we'll not go into any further details because this is our old friend in twitter and you already know what this does same is true for the iterator trait that rust has built in i want to have my own one i want to have my own iterator and i called it my iterator again it's a copy of the iterator trait from rust just to be able to play with it okay so i'm fine with that one now in the early days of rust the iterator for a raise were implemented based on references let me show you that one this is an implementation of into iterator and then also the iterator itself by reference you see that one this is this exists for a pretty long time it is there since 1.0 yeah um and it was added with const generics in rust 1.51 so the into iterator trait for references to arrays worked for a pretty long time so we can add this implementation this implementation of the into iterator trait for references to my array in our all in our own simple example here so let's do that this is old code this is just a simulation of what was there before we had rust 153 so here you have the reference to the array and of course we also need the iterator let's do that iterator again just the phantom data we don't care about the implementation behind the scenes we just can't care about the data types and this is the implementation of the iterator in my case my iterator and in this case again it's about references to t so this is a reference iteration okay are we good so let's try this guy let's try this guy by creating this one here some instance of my array and then we call into itter this is not a reference my array is not a reference arr is not a reference but still because there is only a my into iterator based on references rust will automatically pick the by reference iterator and will give you an item of type reference to integer 32 so although we don't have reference here we get a reference iterator because this is how rust works this is how rust method dispatching works i could easily change that one sorry to a reference and everything will still be fine nothing changes but i can also leave that out and the system will automatically recognize okay there is only an implementation for the reference here so we are good remember this implementation has been here for quite a while so this code might exist people might have built code that relied on the fact that calling this into it gives me a reference and not a value so what happens what happens if we implement a by value implementation for into iterator and iterator let's do that i've prepared this code copy it should sorry not here should be here let's copy the my intuitor again this is by value and let's copy the iterator you see this is not a reference just like up here this is a value and guess what just by adding the capability of doing by value iteration we broke existing code because now the into eater thinks it should take the by value iterator up here because this year is not a reference but it is a value so if i add the reference here everything is fine again because now the system knows i want to iterate a by a reference but if it is like that just by adding implementations here by adding implementations for traits we break existing code and that was the big problem the rust team the rust compiler team would have broken a lot of existing code by just implementing a buy value iterator for a race and that obviously was not acceptable so there had to be a different solution and luckily there was there is now in rust a trick and i want to show you this trick in the last demo that i will do today okay let's get rid of this example you can find this example in my demo repository and i would like to copy let's see here this little bit of code and walk you through it it's nothing new it's just things which we this one it's just things that we have done before okay and i want to use the std uh there it was the std back into it now this is good this is nothing special it's just what we did before but i need to i need to have this few lines of code to demonstrate the point you see the first one is a vector we have that before and we use integer to iterate by value you see value here i have a reference to a vector we call it into iter and we get a reference to the elements inside the vector this is how vectors have been working since the dawn of time okay now let's try exactly the same with an array this one is as you can see it here no reference we call intuitor just like here no reference we call intuiter and for vector we got an i 32 ref a value not a reference but you see what's going on here in arrays we still get a reference and this is what rust what a trick of rust is in rust 153 the compiler recognizes exactly that scenario where you're called into it and changes the behavior to be backward compatible so in contrast to the vector we get a reference and not a value but we also get a warning that this will break in the upcoming version of rust in the ros 2021 this will break so it is okay to break this functionality in a major version of rust but it was not okay to break it in a minor version in a minor release of rust this was not okay so therefore they did this trick so if you do that one the array will behave differently from the vector of course if you want to explicitly call into ether you can do that by using this syntax here it's essentially exactly the same as we had before but only different syntax and for this syntax the rust compiler will not do the trick and you will get a value and not a reference so this already new behavior no warning this trick to be backward compatible in the future this will break and in the future this will give us an i32 and not a reference and because we finally got the implementation of into iterator and iterator by value all the fuss that i did and talked about in the last hour was done in order to enable exactly that one see for i in array and we do no longer for arrays get a reference we get a value and just this simplex is already it stays there for backwards compatibility this is what i wanted to show you i wanted to give you a closer understanding of what's going on behind the scenes and i hope it was interesting for you let me quickly summarize we started with this one i showed you what's new then we dive deeper into what iterators really are i showed you some interesting behaviors of iterators like consuming iterators like mutable references by value iteration and reference iteration and then we use this knowledge to understand why it took so long for us to learn this trick this trick that i showed you value iterations over race and with all this information i hope you had an interesting hour you

Channel: Rust

Views: 3,084

Keywords: rust-lang, rust, rustlang

Id: R0ufQe5DRaw

Length: 75min 43sec (4543 seconds)

Published: Mon Sep 06 2021