I used a lot of Rc in my code. Lucky I don't use interior mutability from Rc, so I can migrate to Gc by using #[derive(Trace, Finalize)] everywhere.
The following:
#[derive(Trace, Finalize)]
struct S {
y: Rc<usize>,
}
Outputs:
error[E0277]: the trait bound `Rc<usize>: Trace` is not satisfied
--> crates\as3_parser\src\location.rs:8:10
|
8 | #[derive(Trace, Finalize)]
| ^^^^^ the trait `Trace` is not implemented for `Rc<usize>`
|
= help: the trait `Trace` is implemented for `Rc<str>`
note: required by a bound in `_DERIVE_gc_Trace_FOR_S::<impl Trace for S>::trace::mark`
--> crates\as3_parser\src\location.rs:8:10
|
8 | #[derive(Trace, Finalize)]
| ^^^^^ required by this bound in `mark`
= note: this error originates in the derive macro `Trace` (in Nightly builds, run with -Z macro-backtrace for more info)
I don't know about the implementation details of Gc, but you make it sound like it doesn't work with interior mutability. If this is the case, then that's exactly why. (Rc must use interior mutability to increment and decrement the reference count.)
I didn't even notice you opened that issue on GitHub. But that's pretty funny. Sorry I don't have anything better to help you. It's just a limitation with the crate that they don't have a solution for right now.
Sorry to be answering a question you didn't ask, but I would be simply re-architecturing your program to not need this much reference counting in almost all cases. IMO mostly the only justified case of using GC in Rust is if implementing an interpreter for some other garbage-collected language.
I wrapped most nodes into a Rc in the AST so that I can attach types (or symbols) to the nodes. I do not know if this is the best pratice in compilers as I am not deep into type systems...
That might make sense. But it seems like this should still be do-able without "true" garbage collection (involving periodically pausing the program and doing graph searches to detect inaccessible objects). The way I'd think of it is:
If your data structures can be statically described strictly as a tree, then you can just use normal variables and structs and arrays and such, and Box if your data types form trees.
If your data structures can be statically described as a directed graph without cycles, or in other words like a tree where branched paths can merge back together but not loop around, you can use reference counters (Rc or Arc).
If your data structures can be described as such where "links back up the tree" sometimes do exist, thus forming cycles, but where you can statically divide variables and fields between "normal links going down the tree" and "backlinks going back up to their own parents," then you can use normal reference counters for the "down the tree" links and weak reference counters for the "back up the tree" links, and this prevents the cycles from causing memory links.
Only if your data model involves truly dynamically manipulating graphs and parts of the graphs becoming inaccessible in truly dynamic ways that cannot be statically reduced to these simpler things, do you need to use true garbage collection. These cases exist but they are rare.
I was almost about to use an Rc arena and use weak references obtained from it to resolve this issue and avoid using Gc, but the only disadvantage is that in my case I would have to use weak references inside structures frequently.
I suspect that trying to use the Gc crate will create more annoyances than simply dealing with using weak references. Even better if you can restructure your algorithms or data structures to avoid both altogether.
I'm not implementing the runtime though, just a SWF/ABC compiler from ActionScript 3 to enhance the language, for use with Adobe AIR, so maybe building an index-based graph like @H2CO3 said might work better for me, with some changes to what I have already experimented in my custom language's verifier before.
It looks like @gretchenfrage is right that Gc is not recommendable for my case. My migration to Gc was not successful
OP just said they are not implementing a runtime, but imagine they were actually writing an interpreter for a GC language. How else do you deal with that without using an actual GC?
I did this once for an interpreter as part of a weekend side project for a functional programming language whose only recursive data types were closures. I implemented two types of closures StrongClosure and WeakClosure in the interpreter, and then demoted closures to contain weak references to environments that bound them. A WeakClosure contained only Weak pointers to the captured environment, preventing loops. This was generally a pain - in practice, any interpreter written in language without a GC will have to implement a GC for languages with GC semantics.
The pain involved in even simple promotion/demotion semantics led me to write my own garbage collector. Due to the nature of the backing implementation of my garbage collector (since passing through an Rc violates the one-value-per-reference invariant), I also don't support Gc<Rc<...>>, though. Theoretically, a mark-sweep library like gc should be able to tolerate Rc, though Rc cycles would then result in the program hanging permanently instead of simply leaking memory (for most naive mark algorithms).
The main concern as others have alluded to is if this is a mutable graph you'll need to figure out when you can remove items, and that in general, this turns into reimplementing GC. I think it's generally the case that an explicit graph structure is better than abstracting it as a pointer type, but you should know what you're getting into either way.
