←back to thread

Stop making me memorize the borrow checker

(erikmcclure.com)
177 points signa11 | 4 comments | 16 Nov 24 23:29 UTC | HN request time: 0.001s | source
Show context
Animats ◴[17 Nov 24 06:10 UTC] No.42162317[source]▶
Rust's reference topology is too restrictive. You can't have back references. This is what drives many C++ programmers nuts. It's common in C++ to have A point to B, and for B to have a pointer back to A. This happens implicitly with class inheritance, too. As a result, common C++ idioms don't translate to Rust at all.

This is fixable. Because you can have back references. You just have to use Rc, Rc::Weak, .upgrade(), RefCell, .borrow, and .borrow_mut(). This works, but only if the upgrades and borrows never fail. A failed .borrow() is a panic. The implication is that if you use .borrow() or .borrow_mut(), there's some good reason to think it will never fail.

For Rc::Weak, the key constraint is that all weak pointers must drop before all strong pointers have dropped. If you can prove that, .upgrade() doesn't need a run-time check.

For RefCell, the key constraint is that no .borrow() or .borrow_mut() may be enclosed by the scope of a conflicting .borrow() or .borrow_mut(). This requires a transitive closure check on who borrows what. For many simple cases, this is statically checkable. It does require inter-function checking.

Can those checks be moved to compile time? Probably. There's already a compile-time static Rc.[1] Compile-time RefCell checking looks possible.[2] It's non-trivial to do this, but worth thinking about.

DARPA's TRACTOR project (Translating All C To Rust) is likely to generate vast amounts of Rc-heavy code, if it works. So that provides some motivation for doing something to check at compile time.

[1] https://github.com/matthieu-m/static-rc

[2] https://internals.rust-lang.org/t/zero-cost-interior-mutabil...

[3] https://www.darpa.mil/program/translating-all-c-to-rust

replies(1): >>42165075 #
1. oconnor663 ◴[17 Nov 24 16:37 UTC] No.42165075[source]▶
I don't love Rc as a cure for borrow checker woes. When Rust programs need cyclic, graph-y things like back references, I almost always suggest moving to indexes: https://jacko.io/object_soup.html. You can get fancy and reach for a SlotMap or a whole ECS, but a lot of simple cases can get away with just Vec. (And even complex cases can use HashMap if performance isn't critical.)
replies(1): >>42166098 #
2. Animats ◴[17 Nov 24 18:57 UTC] No.42166098[source]▶
> moving to indexes

Then you can have dangling pointers that point to the wrong place. Race conditions become possible. You need an allocator for the indices. I've had problems with a renderer that works that way. On rare occasions, it crashes with an invalid index. Even with Rust safe code.

replies(1): >>42169429 #
3. oconnor663 ◴[18 Nov 24 03:14 UTC] No.42169429[source]▶
> Then you can have dangling pointers that point to the wrong place.

Generational indexes in a SlotMap or similar should rule this out.

> Race conditions become possible.

How so?

> You need an allocator for the indices.

Yes, this usually becomes a central point of synchronization. (If you just have a SlotMap, you might not think of it as an "ID allocator", but that is half of what it is.) It doesn't have to be fully synchronous, though, and you can do fancy things with atomics.

> On rare occasions, it crashes with an invalid index.

Indexes become a sort of Weak pointer, and you get an Option when you dereference them, so you can certainly crash if you .unwrap() it or similar. You can use a Vec with "infallible" indexes if you don't want to support deletion, but if you do want to support deletion, the deleted case can bite you one way or another, no?

replies(1): >>42169534 #
4. Animats ◴[18 Nov 24 03:39 UTC] No.42169534{3}[source]▶
> deleted case can bite you one way or another, no?

Right. I use a renderer where, on rare occasions, that happens. I didn't write it, but now I have to fix it, because it's abandonware.