4 ms·
Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust? It
by tptacek 2y ago
Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust? It feels like I mostly see people talking about building application-layer pointer systems with integers, which would be surprising if (in a single thread, perhaps) you could just Rc your way around the problem.
- cmrdporcupine 2y agoSure, Rc/Arc absolutely solves this problem. It's not super idiomatic to go crazy with using it like that, but it's possible/acceptable. Using SlotMap and integer ids, etc. doesn't I think offer any advantage.
- tptacek 2y agoI feel pretty comfortable with Rc and Arc, read the "too many lists" book, &c. and feel like it is not actually simple to model trees with Rc? What am I missing? I'd love to be convinced I'm wrong about this (I want to like Rust more than I do).
- cmrdporcupine 2y agoA tree of Rc/Arc<T> is a tree of references, and is really no different than a Java or Python reference value, except that you'll have to do explicit .clone()s Is it mutability that's tripping you up? Because that's the only gotcha I can think of. Yes, you won't get mutability of the content of those references unless you stick a RefCell or a Mutex inside them.
- tptacek 2y agoYes! Mutability is what's tripping me up! That is not a minor detail!
- cmrdporcupine 2y agoYou can get something like what you're used to a "traditional" language without compiler safeguards by using RefCell and .borrow_mut() on it. That will let you get past the compile-time borrow checks but will do runtime borrow checking and throw panic if more than one borrow happens at runtime. It's verbose, but it's explicit, at least. So: struct Node { parent: Rc<RefCell<Node>>, left: Option<Rc<RefCell<Node>>>, right Option<Rc<RefCell<Node>>>, } and just off the top of my head it'd be something like { let my_parent = my_node.parent.borrow_mut(); ... do stuff with my_parent ... } ... my_parent drops out of scope here, now others can borrow ... etc. Haven't tried this in compiler my memory might not be right here.
- tptacek 2y agoI do know that it's possible, but when people complain about this --- as with this tweet, from a PL theorist: https://x.com/LParreaux/status/1839706950688555086 https://x.com/LParreaux/status/1839706950688555086 ... this is what they're talking about. (I know the tweet is about the "idiomatic" answer to this problem, which is to replace references with indices into flat data structures).
- cmrdporcupine 2y agoI don't have a twitter account and don't read links to paywalled services there, so don't know what the complaint is. Ergonomics aren't great for this type of problem, but it's something I almost never run into. Feels like a cooked up example. I've written tree data structures, etc. and never had much issue. ASTs for compilers, no particular drama. Rust is just making you consider whether you really want to do this, is all.
- nine_k 2y agoDoesn't SlotMap save RAM and pointer dereferences?
- cmrdporcupine 2y agoWhat is a slotmap lookup... if not a pointer dereference, or at least a dereference out of a vector likely on heap... so probably a pointer...?
- School-Cotton 2y ago> Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust No, it doesn't. If you naively express graphs containing cycles with `Rc` you will leak memory, just like you would with `std::shared_ptr` in C++.
- hyperbrainer 2y agoConsidering that there exists a book about building linked lists in Rust[0], I am going to go ahead and say "Unclear" That does not matter though. It is easier (though verbose and often unidiomatic), and hence Rc has become really popular, especially with beginners. [0] https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
- ordu 2y ago> Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust? No, but Gc will not resolve the core problem either. The core problem is that rust forbids two mutable pointers into one chunk of memory. If your tree needs backlinks from child nodes to parents, then you are out of luck.
- tptacek 2y agoIn what way am I "out of luck"? It's trivial to express a tree, including one with backlinks, in Java.
- okanat 2y agoand then your gc will leak it. Rust programs are not only safe but CPU and memory efficient.
- truetraveller 2y agoI simple standard mark-and-sweep GC will not "leak it".
- guappa 2y agoThis has been a solved problem for decades.
- ordu 2y agoJava doesn't enforce the rule "mutable XOR shared". But if you have a link "child" in the parent node, and a link "parent" in the child node, then parent.child.parent == parent, and compiler cannot know it. So Rust as the language makes it impossible to do with &-pointers, while standard library of Rust allows it to do with combination of Option, Rc, RefCell but it is really ugly (people above says it is impossible, but I believe it is just ugly in all ways). Like this: type NodeRef = Rc<RefCell<NodeInner>>; struct Node { parent: Option<NodeRef>, left: Option<NodeRef>, right: Option<NodeRef> } So the real type of `parent` field is Option<Rc<RefCell<NodeInner>>>. I hate it when it comes to that. But the ugliness is not the only issue. Now any attempt to access parent or child node will go through 2 runtime checks: Option need to check that there is Some reference or just None, and RefCell needs to check that the invariant mut^shared will not be broken. And all this checks must be handled, so your code will probably have a lot of unwraps or ? which worsens the ugliness problem. And yeah, with Rc you need to watch for memory leaks. You need to break all cycles before you allow destructors to run. If I need to write a tree in rust, I'll use raw-pointers and unsafe, and let allergic to unsafe rustaceans say what they like, I just don't care.
- pcwalton 2y agoRc does solve the problem, but it often introduces interior mutability, which ends up causing usability problems. That's why at the end of the day adjacency representations (i.e. integers) are often preferred.