Self-referential structs (in Rust)

[@Kazyek]

Scoped threads were added in Rust 1.63.0, which could be used to cleanly solve your specific simple example without unsafe

[@m.sierra5258]

Just wanted to let you know that scoped threads now made it to Rust's Std library in 1.63.

[@yardez5990]

1.63*

[@dexio85]

Still, another patchup on the misguided idea that compiler will "catch all problems".

[@yardez5990]

​@@dexio85 why is it misguided? every language's compiler tries to find as many problems in your code as it can, and if it doesnt devs try to make some additional tools for that

[@m.sierra5258]

@@yardez5990 Exactly. And Rust does guarantee no undefined behavior without the unsafe keyword. This is not misguided, it is a guarantee. (and a compiler bug if not held)

[@m.sierra5258]

@@dexio85 If I learned one thing during my years of working as a programmer, then it is that developers are absolutely never reliable, so every bit that the compiler enforces is valuable. Look at it as built-in sanity checks. Why is this misguided?

[@Iifesteal]

Thanks for starting with a normal for loop and working your way up to idiomatic rust. Really appreciated by a starter like myself.

[@gomesroney]

Very nice video. It's hard to find examples online of memory corruption in Rust, so it was nice that you demonstrated how that could be possible. Also, as you iterated over the example I was getting high hopes that you would explore pinning but then the video ended, haha. I was ready for more 30 minutes just on Pin 🙂. I hope you can explore that in the future as your examples oriented approach makes everything much more comprehensible.

[@m.sierra5258]

Pin then definitely no longer counts as "simple example" :P

[@flyingsquirrel3271]

Awesome! Thanks for the video! Although I knew most of this before, watching videos like this feels like casually "strengthening" my inner understanding of rust which is always appreciated :)

[@kajacx]

18:00 The reason that move doesn't work is because rust compiler doesn't understand the difference between shallow and deep borrow. Since the "good_lines" vec borrows (points to) the heap where "input" points, it's actually safe to move input while good_lines exist. If good_lines pointed to the input's length, for example, then you couldn't move the input, because then good_lines would point to invalid memory. But the Rust compiler has no way of knowing that. There are no type annotations for it. The same problem is with shallow/deep mutability. Sometimes you have to declare a variable binding as mut even when you don't need shallow mutability.

[@alagaika8515]

Actually, it is mare subtle. If you move input into the thread and the thread assumes in has sole owner, it might mutate the data and cause a reallocation, at which point the borrow will became invalid. Moving immutably is not passible because if you move, you explicitly want the new owner to mutate the data - at the very least once it is finished with it and drops it.

[@daniellambert6207]

14:30 the worker thread will outlive main() {} if you decided to add a conditional panic!() before the join. 16:00 aah, so crossbeam's scope will be dropped at that diabolical panic, ensuring the threads join

[@neopalm2050]

I guess this illustrates why it's important that things are dropped in the event of a panic!()

[@jotch_7627]

​@@neopalm2050no, actually. rust does not allow memory unsafety just because a value wasnt dropped. thats why std::mem::forget is safe to call. the way it actually works is that the callback is run in a way that panics are caught and cleanup is performed before continuing the panic

[@Verrisin]

The more I learn about Rust (and what it makes explicit about how hard it used to be in C++) .... The more I appreciate simplicity of programming with GC.

[@squelchedotter]

Where is Cool Bear though 🐻 😞

[@asdfghyter]

4:19 was there any specific reason to wrap the filter function in a lambda instead of just writing .filter(starts_with_capital_letter) directly?

[@calisti9308]

23:03 Swapping the pointer, length and capacity of the two strings (input2 and s.input) does nothing to the references stored in S::good_lines. And I would imagine it also does nothing at all to each heap-stored string slice (pointed to by the pointer field of input2 and s.input - so the pointers on the stack are swapped, but the bytes in heap aren't.) But why does it then start failing when enclosed in a scope (curly braces)?!?

[@naitikmundra8511]

The feeling when you finally understand ownership! Great video.

[@linkernick5379]

I love your blog, learned from it so much.

[@wololo1657]

I did not understand *all* of the parts of this video, but I still managed to learn a lot by watching it. I will be coming back to this video, certainly.

[@sardobi]

Love your work! this video was pitched at the perfect level for me

[@gauravtatke4793]

Hi, At 22:00 to 22:15 time, why does return S not complain about returning a reference to local variable input_slice? good_lines hold a reference to input_slice which is a local variable. Can someone please explain?

[@calisti9308]

input_slice is a reference to memory on the heap, not a binding of a local stack value. good_lines reference sub-slices of the same heap string slice that input_slice points to. The reference's lifetime is made 'static by the unsafe block, even though the heap value is not actually 'static - which is why this is unsafe. (If the heap value is dropped, then both input_slice and the vec entries of good_lines point at garbage memory.

[@mattdavies6820]

Great video - what is the drawing tool you're using for doing the diagrams?

[@samuelhurel6402]

Have you found out ? I'd like to know too

[@cthutu]

@@samuelhurel6402 No, but it's the same tools that 3Blue1Brown uses in his Maths videos. Coincidentally, I literally asked the same question on one of his videos. It's blowing my mind that you should reply to my original ask from 6 months ago!

[@walterkrieg5396]

It’s a python extension called manim

[@1000percent1000]

i have been wondering for months why joining threads doesn't join lifetimes, you are a lifesaver for demonstrating crossbeam's scope. so useful, thank you so much :DDD

[@d3line]

Scoped threads are now in standard library btw

[@SophieJMore]

Joining threads doesn't join lifetimes because join() can be called at any time (including never), or it can be called in some conditions and not others. Also, the compiler is unable to reason about any complex control flow, it just relies on the lifetime system, and the lifetime of the closure you pass when you spawn the thread is 'static, which was chosen for the abovementioned reason. That 'static is literally everything the compiler sees, and it will reject any attempt to give it a closure that reference anything non-static

[@antonionatilla9848]

Very interesting demonstration and explanation! I dealt with the same situation a couple of weeks ago, but I didn't delve into the "unsafe territory" since I'm "still learning" Rust. Finding out about this video was a pleasant surprise, in the past days!

[@m.sierra5258]

It's hard to believe to me that many people still strongly advocate C/C++ where unsafe ist just normal

[@Hwyadylaw]

I think it's quite nice that writing unsafe code is so explicit that it makes you think "maybe I shouldn't", whereas in other languages you might write rust-unsafe code without even realising the potential issues

[@smidimir]

I'm currently new to rust but, I know C++ very well. In rust I tried to solve exactly this problem for about 3 hours using "safe" rust without success. Having my background, I had some assumptions about how certain things work in rust. - Unlike C++, rust "moves" are just memcpy's. - Moving the container (String or Vec) shoud not mean moving its data from one location to another. It's just a handle. I even checked if String in rust has short string optimization. And it doesn't. So, what's the problem, rust? Why don't you let me do this clearly safe thing? In your video you asked exactly the questions I had in my head while trying to make it work. I also started to think, that "unsafe" rust is the solution to the problem. Thank you for the thought process and the solution. Great video!

[@SviatoslavAlekseev]

Great video. How about Pin and Unpin. They should help with these problems (almost) without unsafe. Are there a any good guides on how to use it in self-referential structs?

[@abhishekshah11]

Yeah this was really insightful into subtle workings of rust safe code. Would like to see more of it. I'll try to write a "safe" fn woops this afternoon hopefully, now that I'm curious to make it work :P

[@connormcmk]

i don't think anyone has mentioned it but scoped threads were added rust's std 1.63.0, wish someone would have commented this earlier

[@SianaGearz]

Is it deep sarcasm or genuine? I can't tell.

[@connormcmk]

@@SianaGearz i saw it mentioned 3 times so wanted to make sure it got mentioned at least once

[@nikandfor]

What a good simple language!

[@luckystrike91]

you can use Pin to prevent move

[@MetalManiacBoy]

Insanely well explained, fasterthanlime ! Keep up the good work :D

[@CottidaeSEA]

Once you mentioned the second thread, all I could think was "you could just do the entire thing in the new thread".

[@AbelShields]

Hmmm... I wonder if this problem could be solved with a little language help - can we assume it's fine to hold a reference to a heap value, such as a T in `Box` while the box itself is moved?

[@d3line]

It's not really about the move, it's more about the drop. Box could be moved to a function that immediately drops it, so box is deallocated and references become invalid. So no.

[@AbelShields]

@@d3line huh, that makes a lot of sense. Thanks :)

[@MasterHigure]

4:30 filter(|x| f(x)) is the same as just filter(f).

[@qm3ster]

Nope. `f` is `Fn(&str)` `|x| f(x)` is `Fn(&&str)` There is a dereferencing happening. The closure is unavoidable.

[@asdfghyter]

I wonder if it would be possible for Rust to be aware of the distinct lifetimes of the String struct and the string data it points to? when moving something, you invalidate anything that points to it directly, but it shouldn't invalidate pointers to things it points to. it doesn't seem like a super difficult rule to get right and it should be a fairly common case: if i borrow a pointer from a struct, you can move the struct, but you can't drop it nor mutate the pointer part of the struct. the last part is similar to rules that already exist, since you can partially borrow a struct and then the rest of the struct is still available *edit:* there seems to be a crate that attempts to solve this, called owning_ref. unfortunately it (and the example in the video) seems to be unsound/UB for some technical reasons, which is proposed to be fixed by the "maybe_dangling" rfc. *edit2:* another crate called _self_cell_ claims to be sound, so maybe that's the way to go. it uses a macro to define the struct and the allowed operations

[@zperk13]

7:00 How in the world did you get rust analyzer to highlight line 17 too?

[@zperk13]

Figured it out. You need to set Error Lens to also highlight hints

[@ゾカリクゾ]

So... what approach would you use if you were to avoid unsafe?

Hi bro, thanks for all of your hard work. I would like you know, which plug-in are using, to show the errors on the line in Vs Code

[@tuesss]

I have only used VSCode very briefly, but I think it's Error Lens.

[@syncpoint]

Hopefully there are more in que regarding rust.

[@alexzander__6334]

loved that part with the diagram

[@jeffg4686]

The comment about a move being a memcpy, is that only true in the context of moving across a thread boundary? I always think of it as more of "compile-time rules enforcement" (playing the game of the language so to speak) than an actual memory operation at runtime, but I don't really know ... Was just the way I had envisioned. Maybe it's a runtime thing for thread boundary, but compile time thing otherwise. Something to ponder. I would think for a thread boundary, it would have to be an actual runtime consideration (move to stack of other thread), but otherwise I envision compiler enforcement only, and no memory op. I guess the bigger point is that a move may or may not be a memory op (i think...)

[@AyoDamilareMichael-g3y]

What font are you using in the video ?

[@thepuzzlemaker2159]

Nice video! Just curious, what's that program around 8:18?

[@fasterthanlime]

That's draw.io, now called diagrams.net

[@kajacx]

This is about deep references. Still interesting, but I was hoping it would be about shallow self-referencing. Much more fun, since you cannot even move the struct then. Does "Pin" help there?

[@Laura-hl3hg]

Hey, I love this video, you're amazing at explaining! Could you tell me what software you're using to make those diagrams? I feel like it could be insanely helpful for sketching out the logic flow of programs.

[@fasterthanlime]

I'm using draw.io, now named diagrams.net

[@lucasemanuelgenova9179]

Which drawing program is that?

[@miniappletheapple]

Which application are you using?

[@jx6773]

what vscodes extensions are you using???? those seems useful

[@dj-maxus]

Currently, `std::thread` also have `scope()` which is pretty nice

[@newclarity4228]

What software do you use for your diagrams?

[@fasterthanlime]

In this video, draw.io / diagrams.net

[@fasterthanlime]

In this video, draw.io / diagrams.net

[@JimmyZeng]

I think there's some serious misunderstanding about "move" in rust, "move" here does not mean the memory address is _moved_, it's just the ownership of a value been moved.

[@micycle8778]

but when a closure in rust has the move keyword, would it not copy stack allocated memory into that closure's stack, therefore changing the memory address?

[@JimmyZeng]

@@micycle8778 ​ I think the point is: when we are talking about move, we are talking about ownership, not address.

[@calisti9308]

@@JimmyZeng Ownership definitely moves, while the address *might* move, or be optimized away.

[@baggern]

"load bearing keyword" lol

[@joshuahab]

What if you created an ImmutableString type that can be built from String? In that case it seems like self-reference to the ImmutableString could be made safe.

[@DeviRuto]

You can always leak() the string. Makes anything 'static

[@SophieJMore]

I think the main problem here is that you can't move values that are being borrowed, even immutably. Generally, it's unsound to do so, because it might invalidate the data that's being pointed to. Here it's not unsound, since the data that's being pointed to is actually on the heap. However, the compiler can't really meaningfully differentiate between the two cases. To it, &String and &str both borrow from String, so it would prevent the String from being moved. Even if you wrap a String to make it immutable (psst, better use a Box instead in this case), you still don't be and to make a self referential struct with it (without unsafe). So, if by "could be made safe", you mean not using unsafe blocks, then I don't think it's possible. Otherwise, you can always make a safe API around unsafe code, just be careful.

[@gabrielnuetzi]

In 2023 is there an safe way of achieving self referencial structs? ❤??

[@zerker2000]

OwningRef seems like it would be useful here, if generally limited.

[@buzdxkysguge2334]

Good work! May I ask what's the software you used to draw those diagrams.

[@meain_]

Kinda looks like app.diagrams.net/

[@numtostr]

This was indeed fun. Thanks!

[@kh0kh0]

More please!

[@maxwellclarke1862]

I think RcString is the best solution here

[@manawa3832]

Great video also keep in mind aliasing could still screw things up.

[@contactron]

So you are saying std::thread::spawn never drops any resource moved into it? That seems like a major source of memory leaks. Good to know.

[@fasterthanlime]

It definitely drops resources at the end of the thread, but the compiler cannot statically tell *when* unless you use something like crossbeam's scoped threads (which is not always what you want either). But it's easy to check that it does in fact drop stuff when they fall out of scope: play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2968a70cb054657ff7134dce01679c49

[@contactron]

@@fasterthanlime OK, good, that's what I would expect. I originally misunderstood what you were saying at 14:00, I thought you were asking why it wasn't safe to drop input, which seemed odd to me because you had moved input into the new thread. But really you were asking *why* you had to move it into the thread. Anyways nice video.

[@timo7964]

Amazing video! thank you!

[@joaoalves1359]

Excellent video

[@bozhidaratanasov7800]

Can anyone point me to good material on the topic of building your own LinkedList/ Graph type structures in Rust? This is what I understand by "self-referential".

[@bozhidaratanasov7800]

To answer my own question, there is a reading online called "Learning Rust with entirely too many linked lists". It's dence with useful Rust examples.

[@JihChiLee]

Love you videos! keep it up!

[@ibrozdemir]

relatable intro xD even tho i never coded in rust, i understand the pain you are having.. why would anyone make another language as fast as c++ but puts tonns of restriction so no one can use it as free as they want

[@TheMrKeksLp]

Because having the compiler check the code for you is better than you checking the code and failing

[@ibrozdemir]

@@TheMrKeksLp thats not checking thats restricting.. and yes you are right, with c++ you will get more crashes and bugs, however thats (in time) fixable.. since %99.9 of programmers not writing codes for spaceships, its allright

[@thirdreplicator]

Very nice!

[@pepoviola]

Awesome video!! thanks!! :)

[@kibar9155]

awesome! thanks

[@Hector-bj3ls]

Why did we get Pin instead of relative pointers? The issue is that references and pointers have absolute addresses. So &a returns the absolute address of a. If we had some way to do relative pointers/references we could have a pointer that is more of a "take my address and sub/add x to get to the thing I point to" instead of "I contain the address of the thing I point to".

[@LeandroCoutinho]

Amazing!!!

[@mattdavies6820]

`scoped_threadpool` may be lighter weight than crossbeam

[@WolvericCatkin]

_`starts_with_capital_letter`..._ 🤦‍♀️ Or just `.starts_with(|&x| x.is_uppercase())`...

[@Dorumin]

Yeah that function was really awkwardly written, but it did the trick I guess. Is &x necessary? Shouldn't the dot operator auto deref?

[@TheMrKeksLp]

Many roads lead to rome 🤷‍♂

[@MykolaTheVaultDweller]

good video. but where is self referential structs? looks like clickbait title

[@theLowestPointInMyLife]

GUI in rust lol

[@qaqkirby9781]

😂😂😂

[@alekxcrafter]

rust is cringe

[@happygofishing]

Language for transsexuals that failed to use makefiles and pointers

[@jonathanmoore5619]

Contrived. "Main" is the program. Join the thread and end, else send the changed input to another file. You're creating an unnecessary problem.

[@Iogoslavia]

Oh man, I thought there was going to be some neat trick to create self referential structures without the unsafe keyword 🥲