2 ms·
Sure, 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 inte
by cmrdporcupine 2y ago
Sure, 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...?