The Rust Borrow Checker – A Deep Dive
infoq.com
infoq.com
I wrote a trading system in rust recently, it was a breeze. I was never stuck with strange issues or crashes, everything that went wrong was reasonably clear. With c++, once you get a segfault you never really know if you've actually fixed it or just gotten lucky. Mysterious crashes are also a huge timesink, because you tend to have to stop what you're doing on look at what happened, and then when you fix it it's quite possible you're just relocating the problem. Even if you avoid those issues, you will have to periodically run through your code with some valgrind or similar tools, and then you have the awkward "should I do something about this warning".
I don't think this dive was terribly deep though. It was good to look at the IR representations, but what often trips people up isn't that textbook use-after-move example. I'm sure there's a menagerie of strange "why does the borrow checker complain" examples where it's a little less obvious why the lifetimes are wrong. In particular, when you have to annotate the lifetime yourself, things get weird and it's not always obvious what to do.
The thing is, you can get away with a reasonable sloppy and half-hearted knowledge of those things in modern C++, unlike in Rust, which is of course strict
With the dynamism you have the freedom to make whatever ad-hoc memory management constructs you like without formally explaining them to the compiler, but also you don't get compile-time guarantees that they are correct.
This only applies if one is randomly changing things instead of actually fixing the problem. :-)
- I tend to store references to other objects using indices instead of pointers/references anyway, so the borrow checker isn't really that important for me. Memory errors that comes from indexing can be caught with runtime assertions, or if you can't use assertions because of performance constraints you can still use sanitizers to debug these issues. (You're probably going to run sanitizers even in Rust anyway if you are using unchecked array indexing...) Further use-after-free errors that come up with reusing indices in an object pool can be caught at runtime using the generational index trick. (See https://kyren.github.io/2018/09/14/rustconf-talk.html for the gist of what I'm talking about. The presenter listed this as a reason why Rust is good because the compiler nudges you circumvent the borrow checker to design better code, but for me this was actually a reason why Rust doesn't actually help that much at all: I don't need the guidance of the borrow checker to have this decision in the first place! She's actually giving a reason for why the borrow checker is useless!)
- Also, Rust's compile-time facilities are still not as powerful as C++'s. For example in Rust you can't still do operations with integers in generics in compile time, you need to wait that until the full version of const generics. (This is important if you want to make a convenient math/linear algebra library) SFINAE is dirty but still more powerful than what you could do in Rust with trait bounds, template specialization is also absent in Rust. C++ also has 'constexpr if' which makes type-level programming much simpler than what you need to wrangle in Rust. At least Rust has hygienic macros, but to be honest it's a bit cumbersome to use and seems to be designed as an afterthought. (Overall C++'s templates are 'dirtier' than Rust's traits but are far more powerful. But I really like how languages like Zig and Jai approach compile-time programming though... these are the languages I'm more excited about than Rust or C++)
- Unsafe Rust is still much limited than what you could do in C/C++, but still really hard to write. Even when I have a rough picture about how I would exactly implement a system in low level terms, Rust's complicated semantics around safe/unsafe severely distracts me from actually implementing some actual shit. (Arguably this is the same for modern C++ where you need to know all these weird move/copy semantics to implement even simple generic containers like vector<T>, but the best solution for that is to use simple POD structs as much as possible and suddenly your worries tend to disappear.)
- This is probably a bit too unfair, but I would actually like to use some battle-tested C/C++ libraries right away rather than wait for someone to do the gnarly FFI binding work or even "reimplement in Rust(TM)".
Still, Rust has some nice features like ADTs, pattern matching, and syntax sugar for Error types, so maybe the tradeoffs can be worth it if some of these pain points are solved. Around the time when the full version of const generics is finished I might start exploring Rust again.
FTR since 1.46.0, Rust also has if inside const contexts (as well as loop and match, but no for loops as they are trait based and traits in const are still being developed): https://github.com/rust-lang/rust/blob/master/RELEASES.md#ve...
template<class T>
auto foo()
{
if constexpr(compile_time_compute_value_changing_depending_on_T<T>()) {
return Type1();
else {
return Type2();
}
}
C++ references only help you with null pointers and they are a pain in the ass to try to store as a member in a struct with all the weirdness regarding operator=.
C++ references do not help you with use-after-free, accidental concurrent modification or container/iterator invalidation.
E.g. consider the following C++ application:
std::vector<int> v = { 1, 2, 3 };
int& ref = &v[2];
v.push_back(4);
ref = 123; // this will crash if vector is resized by push_back
As individuals we can deal with these invisible contracts that are everywhere in C++ (and C) programming. But this kind of discipline does not scale to bigger teams.
I kinda agree with you about the "power" of C++ templates vs. Rust generics when it comes to compile time metaprogramming. But for generic programming Rust's traits are very practical and powerful, and with C++ still lacking concepts it's really no match.
You mention one of Rust's generics' biggest pain points: it does not work at all when trying to implement functions that work with i32 and i64, or f32 vs f64, let alone f32x4 vs. f64x4 SIMD vectors. For comparison: Haskell has "Integral" and "Floating" type classes (traits) for this, but Rust for some reason does not.
FFI is painful with every language, including C++ (for C libraries that don't work well w/ C++ idioms). My experience with Rust FFI and bindgen has been excellent. It auto-generates Rust modules from C headers and even converts doxygen comments to Rustdoc. It was about as easy to build a Rust project with some in-house C libraries than it would've been to write a C or C++ program using them with all the CFLAGS+=-Ipath/to/headers and Makefiles I would've had to deal with.
Finally, from a seasoned professional C++ programmer... Rust's tooling blows C++ out of the water. A reasonable build system, linters, API docs, LSP, autoformatting, modules (no more header files). And especially C++'s dysfunctional dependency management is just plain awful (single header libraries or apt-get or whatever aren't a substitute).
With a few decades of C++ experience under my belt, I've found Rust to be a huge leap forward on almost all aspects (but not without its pain points).
Maybe I didn't express this clearly enough, but I don't use C++ pointers or references to store something that is more than just temporary, I usually go for indices instead. You should read the "Handles are the better pointers" article (https://floooh.github.io/2018/06/17/handles-vs-pointers.html) to understand a bit more of what I'm saying.
> with C++ still lacking concepts it's really no match.
I thought C++ already had concepts in C++20? (Though I honestly haven't got that much use for it, and I still use C++17 since I want to wait a bit until compiler implementations get mature).
> Rust's tooling blows C++ out of the water.
Agree with Rust's toolings being more polished than its C++ counterparts. I like that Rust has Cargo and also its own build.rs which you can code your custom build scripts in the same language. I also agree that Rust modules are much better than C++ headers (although modules are in C++20, I feel it's already a bit too late when so much existing code hasn't been written for it) The last time I looked at IDE support with Rust it wasn't that great, but that was quite some years ago so things might have changed a lot.
The story around promoting Rust over C++ has aged badly. Parroting arguments that seemed persuasive in 2015, when most people had not even got C++11, taints your argument. People coding modern C++ don't spend time on memory errors, so promoting that detail of Rust makes you seem out of touch, and other statements doubtful. C++ has got markedly more powerful of late, in ways not matched in Rust.
This remark, "FFI is painful with ... C++" is frankly nothing short of bizarre.
To win over people coding modern C++, you will need to explain how giving up the powerful features C++ programmers are accustomed to using, but cannot in Rust, will make a better experience anyway. You might need to learn something about those features to have something to say.
Also, modern C++’s move/copy semantics are exactly what Rust enforces at a language level, instead of only making it a “suggestion”.
FWIW, while I totally agree with the argument that I would prefer to be able to prove my code doesn't have this kind of bug, this statement goes too far: if you don't know what was wrong with your code before and you merely whacked at it randomly until it stopped crashing your work isn't done... you should know exactly why your code crashed before and know for sure that your new code doesn't exhibit that same issue--as well as think about how to avoid ever making the same mistake again, potentially doing drills with the concept so it becomes a bit more intuitive or adding new compile time lint behaviors--before you move on to your next task (and this is how you should be treating bugs of all forms, not merely segment faults).
Regardless, my issues--as a long-time C++ developer--are that I am pretty firmly addicted to all of the compile time programming benefits of C++ (which sometimes let me pull of safety tricks that are more indicative of a dependently-typed language) that other people have already mentioned... but I am also pretty addicted to unchecked exceptions, and see absolutely no reason why Rust decided to re-tread error handling mistakes I've seen in prior programming languages (awkwardly including Java, which has checked exceptions, and feels more similar in spirit to Rust than C++).
(That said, I do appreciate that the syntax sugar for papering over this has gotten better with time, but I still think the people who don't appreciate that exception-safe code is actually important to write in all situations and if you can't do it your code probably can't be correct even in the case of a language without exceptions are missing something important about the nature of errors.)
Me: Let's code this little vector computations
BorrowChecker: "Not like that"
Me: "What do you mean I have borrowed a mutable ? Let's try something else purely out of random"
BC: "No"
Me: "Let's rename things to cheat"
BC: "No"
Me: "Ah yeah, it's because I try to use two indices in the same vector"
BC: "No"
Me: "G*mn at random, let's shuffle things"
BC: "No"
ME: Ok, let's do it in python
(but believe me, once, you understand it and it becomes a really good friend, it just takes months :-) )
Same for Haskell. It seems that some great languages take some investment in order to become productive with them.
Writing assembly also needs a big up-front investment, but I'm not sure how many have every considered it to be a good friendship. :)
you cracked me up. tnx.
So does learning a language enough to claim to know it.
As Bruce Eckel once said, programming is like learning to navigate a room blind. You won't learn till you've bumped into every wall and piece of furniture.
True, but many languages let you do a lot of useful things while you are still learning, without requiring you to truly understanding what you are doing. Some people manage to spend their entire career writing useful little python scripts without really "knowing" most of python.
Languages like Rust and Haskell make you learn a lot more of the language up front before you can become useful.
This should not be taken as a critique of the language however.
Well same can be done in Rust. Hate the borrow checker? Just Box/RefCell all the things. However learning that habit can be pricey from execution POV, so most Rust books don't teach it.
I guess another way could be by using Copy-able structs is anohther way.
I haven't found that the on-ramp for productivity is higher than any other language tbh, I'd say that my experience with Python was similar, for example.
Can someone who struggled with the language explain what the hard part was? My first language was C++ so I think that's probably biasing, everything looks sane after that.
No one is saying it's super hard (assuming you are an OK programmer) just that it takes a month or three of actively working with it to wrap your brain around it, which you seem to agree with.
I'd say that my experience with Python was similar
I've had colleagues (that aren't programmers) who taught themselves just enough python to be productive with writing Python scripts that solved real problems while knowing maybe 20% of the language. Rust will not let you get away with learning only the very basics like that.
They have no idea what a list comprehension or function decorator is, hell most of them have probably never typed the word "class" into a script. In Python that doesn't matter, you can get very far with just basic data types, functions, for loops and cutting and pasting from random web sites.
It is. Anyone coming from anything else than C or C++ will struggle for a while. A lot of things make sense now for me in Rust after days / weeks of playing around with small apps. But the 2 types of String is still one of these thing which anytime I read about it makes (sort of) sense, but then ... Well, I know that using a string literal (with possibly a lifetime) instead of a string, or adding `to_string()` will probably solve my problem. Thankfully the borrow checker along rust analyzer are extremely smart and 2 things which are built to the (close) perfection - the dev experience for beginners would be a total nightmare if it was as messy as the typescript linter
However, sometimes (and for an experienced Rust developer this might start to happen more often than "Oh, actually that was dumb" type situations) the problem is that the Borrow Checker doesn't understand why it's fine. The diagnostic points you at something, and you say "Er, yeah, what's the problem?" and, sometimes, there wasn't really a problem.
Non-lexical lifetimes were a big improvement in Rust, improving the borrow checking analysis so that more cases which are correct were allowed by the checker.
Polonius is one thing intended to further improve upon this: https://github.com/rust-lang/polonius
I'm looking forward to see how the language develops further.
It might be that I would have to add extra safety mechanisms - such as Arcs or Mutexes. But it's all possible.
Some Rust developers might see such code as less idiomatic and look for a different solution, but if a different solution doesn't exist, there's always the fallback.
Less experienced Rust developers, however, are more used to seeing only the easier patterns and may not appreciate how to achieve some of the more difficult ones.
It's not that these patterns are harder in Rust than another language, per se. But more typing is needed to convince the compiler that you have everything lined up. Other languages will just let you introduce data races / crashes.
I think it still can't handle arbitrary reference graphs without a garbage collector. If I'm wrong, please correct me, and provide proof. I'm very interested in the problem of non-GC arbitrary reference graph cleanups.
On the other hand, one could ask the question of do we really need the arbitrary reference graphs? Or are they just a crutch that we use to make things easier for us? Perhaps every algorithm that requires a complex reference graph can be also expressed in Rust's safe mechanisms.
Note that I don't have any deep knowledge about Rust, only stuff that I've read on various blogs.
a) Good ol' `Arc<Mutex>`, messy and has overhead, but easy to slap in and recreate the Java sea of objects.
b) Arena allocators -- often if the graph is used for an uppercase Algorithm like spring layout or something, the graph has a singular lifetime, so not being able to individually free the nodes is fine. Then you just have `struct Node<'a> { others: Vec<&'a Node<'a>> }` and all is good, the nodes all have the same lifetime and the borrow checker doesn't care about the mutual reference recursion.
c) Generational indices into a `Vec`. This gets used a lot for ECS systems like in Bevy, but they're very neat -- you can reassign a spot by just bumping the generation, so you don't need to worry about leaving holes or use-after-free. If you squint at it, a generational index is basically a pointer with provenance.
There are other techniques too, such as https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/
You can also use Rc/RefCell rather than Arc/Mutex if you don't need a multi-thread capable structure. You can always wrap a Mutex round the tree as a whole instead.
[1]: Except the errors about partial (non-aliasing) borrows of struct fields. That was annoying, although circumventable with some boilerplate. Luckily, it's solved now in the compiler.
[2]: Although it may be to a large degree thanks to using arenas for allocation, which simplify lifetimes a lot by grouping them into large buckets instead of tracking each little object separately with its own little lifetime.
If you're going to do that, would you not be better saving all that time and code bloat (it's code you wrote that doesn't contribute to solving your problem) by just using a garbage collector from the outset?
This propensity to fall back to arenas and the other puzzling behaviour i observe is liberal use of "#[derive(Copy, Clone)]" - these seem counter productive. Why are people wasting time only to reinvent solved problems?
Or to frame it more charitably, rust is allegedly a super-power for developers. Why are rust devs not pushing the boundaries of what it means to be a developer? We do we not see very large code bases on github maintained by a small number of devs? Allegedly the combination of static typing + borrow checker makes code maintainability a breeze. So where's the evidence?
I suspect a garbage collector would be pretty nice. However, I can't just list the features I want and get a language (unless I make it myself, which would take a lot of time). Currently, my imaginary perfect language would actually have a garbage collector, would be pretty similar to Standard ML, but would be more focused on arrays than lists, and would have value types --- in Standard ML I can't have a value array of records (structs in Rust/C++ parlance) --- they will be behind a pointer. And if I were to stick to the standard or make sure that my code compiles with other compilers than MLTon, then I can't even have a value array of 64-bit words, although I can have a value array of 63-bit words. This one bit may seem insignificant, but for certain algorithms it's a big complication. Powers of 2 simplify a lot of algorithms (and are "faster" to be a bit loose with the language). There are other features I'd like, but already this short list makes for a currently-non-existent language. OCaml and Haskell have similar problems to Standard ML.
At the same time Rust has great support for arrays, is expression-oriented, has sum types. Value types are the default. It generally ticks a lot of boxes I care about. I can't just go and say "now give me all that but with a GC" and have it appear before me.
Also, arenas I use are linked to logical portions of my programs. They are not contrivances that I had to think long and hard about. They don't waste my time really. I've spent 0 time thinking about how they should be organized.
Now the part where a GC would be helpful is a bit of a more liberal use of closures, and eliminating code noise coming from lifetime annotations such as "for<'a>". But I can live with the current state of affairs, if I get all the other benefits.
> If you're going to do that, would you not be better saving all that time and code bloat (it's code you wrote that doesn't contribute to solving your problem) by just using a garbage collector from the outset?
If anything, Rust is an asset for large teams of devs. Even though you may sometimes argue that a handful of C/C++ devs can keep their whole project in their heads and not make mistakes (although I think that's a stretch), the moment you get a large C/C++ team, weird hard-to-debug bugs coming from memory- and thread-safety issues start to creep in. There are other high-level languages, but Rust is the one with a combination of performance competitive with C++ and large ecosystem of libraries you can use. Examples of Rust projects with a large number of contributors facilitated by the language taking the fear of intractable bugs away:
- <https://github.com/BurntSushi/ripgrep>
- <https://github.com/clap-rs/clap>
- <https://github.com/rayon-rs/rayon>
None of us are getting a pony but that's not the point. The point is about selecting the right tool for the job.
For example, I see projects like axum[1] and wonder what people are using it for. In a PHP or Rails or Django stack, this is your nginx / apache layer. It's not business value code, it's the fast plumbing under your stack. What are people adding to the fast underlying plumbing layer that's giving them a competitive advantage? Or is it just cargo culting?
>> If anything, Rust is an asset for large teams of devs
I mean i only asked for an example of a small team performing magic thanks to rust so if there's no examples of that, i can be certain there's no examples of a large team performing magic thanks to rust!
> I mean i only asked for an example of a small team performing magic thanks to rust so if there's no examples of that, i can be certain there's no examples of a large team performing magic thanks to rust!
Well then, my examples of large teams should be sufficient. :)
Oh, and I've just remembered about this nice project: <https://github.com/firecracker-microvm/firecracker/>
An arena-based allocator will run circles round GC and malloc: no need for tracing or bookkeeping, just one allocation and one deallocation for any number of objects created (or, at least, the ratio of created objects to memory allocations is very high). And with Rust, the compiler will give you an error message if you try to hold on to an object in an arena you're trying to deallocate.
Where does the overhead of copying the surviving objects over to the new arena as you drop the old one factor into this? Or maybe you could own more non-problem-solving code and permit cycling of one arena? Could get tricky if you want to rely on destructors?
The ratio of lines of code written to solve the problem vs written to shave yaks is getting lower still here.
> Or maybe you could own more non-problem-solving code [...]
You know, sometimes performance is the problem, and code which improves performance does solve that problem.
Only within a function. You still can't partially borrow a struct across function boundaries.
Anyway I don't believe you that you only got "a couple of lifetime errors at the start, but I understood the reason behind them all". Either you're bullshitting or you have restricted yourself to extremely simple Rust code and haven't really realised how complex them can be (e.g. what does `for<'a>` and `+ '_` mean?)
> In C++ you need to think about the lifetimes anyway or your code will break at runtime, so then coming to Rust it's not that much of a problem IMO.
C++ definitely gives you a head start when thinking about lifetimes, but there's still a huge difference between thinking about lifetimes, and writing them down to prove to a not-especially-smart borrow checker that they're ok. Obviously the latter is better, because it gives you guarantees. But it's still way way harder.
How kind.
> what does `for<'a>` and `+ '_` mean?
`for<'a>` allows you to introduce a new lifetime parameter which parametrizes an Fn argument independent of the lifetime parameters of the enclosing function/struct. Sounds complicated when you try to explain it in programming terms, but actually when you think about it in terms of logical quantifiers from maths (for<'a> being the universal quantifier introducing the 'a "variable", "for" -> "for all"), it's pretty simple. The idea is simple, the syntax is noisy. I've already complained about the noise in another comment: <https://news.ycombinator.com/item?id=31433427>
"+" in type constraints is just conjunction.
> C++ definitely gives you a head start when thinking about lifetimes, but there's still a huge difference between thinking about lifetimes, and writing them down to prove to a not-especially-smart borrow checker that they're ok. Obviously the latter is better, because it gives you guarantees. But it's still way way harder.
Getting a program to compile may be harder. But the whole task of writing a program long-term gets easier. Most of the complaints about borrow-checking I see online can be split into two categories:
1. syntax noise --- I agree
2. this program would work, if not for the borrow checker --- in almost all cases here people do not think about API boundaries at all. They look at the body of the functions they wrote and conclude that it should work. But they forget about one important thing: the compiler needs to ensure that changing the body of function f() without changing its signature should not break compilation of function g() which calls f(). That leads to examples where it seems as if something should compile, but doesn't, because of function boundaries which mandate that lifetimes should be correct regardless of function implementations. And there is a good reason for that: if I use a library, this library pushes out an update which doesn't change the types of anything, I don't want to be forced to update my code for it just to compile. So the work that ensures that everything stays composable throughout implementation detail changes is moved upfront.
The alternatives to "fighting the borrow-checker" are GC or difficult to debug (sometimes even to reproduce) bugs. Fixing the compilation is a lot easier for me than tracking down memory-corruption bugs I face in large C++ codebases with hundreds of contributors, so I disagree with the claim that making things work in Rust is harder.
It really took a while for it to "click" in my head about how it wanted me to structure things. Once that occurred it was smoother sailing, though still difficult. Then I never touched it again. I should give it another try to see if anything stuck with me.
As a Python expert, this hits home, unfortunatly.
Python packaging is fine now, but the sets of rules to follow to stay on the happy path is the opposite of intuitive, and definitly advertised.