> I predict that tracing garbage collectors will become popular in Rust eventually.
The use of Rc is already very widespread in projects when people don't want to deal with the borrow checker and only want to use the ML-like features of Rust (Sum types, Option, Error etc.)
> Rust has arrived at the complexity of Haskell and C++, each year requiring more knowledge to keep up with the latest and greatest.
I wonder when we will see the rise of Haskell like LanguageExtensions in Rust. AFAIK, pretty much everybody uses things like GADT, PolyKinds, OverloadedStrings etc. The most similar thing I can think of Rust right now for is python-like decorator application of things like builder macros using Bon.
> Async is highly problematic
Agreed. Tokyo is the only reason, I think, anybody is able to use Rust for this stuff.
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.
> 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++.
> 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.
Rust'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.
Java 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:
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.
Considering 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.
Rc 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.
I 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).
A 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.
You 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.
I 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.
> The use of Rc is already very widespread in projects when people don't want to deal with the borrow checker and only want to use the ML-like features of Rust (Sum types, Option, Error etc.)
And the fact that this hasn't caused alarm is kind of an issue.
The problem with that is Reference Counting is WAY slower than good Garbage Collectors on modern CPUs. Reference Counting breaks locality, hammers caches and is every bit as non-deterministic as a garbage collector.
> Agreed. Tokyo is the only reason, I think, anybody is able to use Rust for this stuff.
A lot of problems related to Tokyo can be avoided if you think your code as structured concurrency and avoid using Tokio::spawn. However, too often this is not possible.
I haven't, yet, run into building rust apps that require highly complex async implementations with lifetimes etc. however excluding those situations I've found it very straightforward and easy to use. I've built some applications with a lot of moving parts, mpsc has always been a life saver.
> I predict that tracing garbage collectors will become popular in Rust eventually.
The use of Rc is already very widespread in projects when people don't want to deal with the borrow checker and only want to use the ML-like features of Rust (Sum types, Option, Error etc.)
> Rust has arrived at the complexity of Haskell and C++, each year requiring more knowledge to keep up with the latest and greatest.
I wonder when we will see the rise of Haskell like LanguageExtensions in Rust. AFAIK, pretty much everybody uses things like GADT, PolyKinds, OverloadedStrings etc. The most similar thing I can think of Rust right now for is python-like decorator application of things like builder macros using Bon.
> Async is highly problematic
Agreed. Tokyo is the only reason, I think, anybody is able to use Rust for this stuff.