5 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?
by 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.
- jcranmer 2y agoRust's mutability rules specifically screw you over here (you can't have two mutable references to the same object, ever); most languages (including Java) don't have those rules. I sometimes wish I could have a mode of Rust where I had to satisfy the lifetime rules but not the at-most-one-mutable-reference-to-an-object rule.