Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
Nice blog post! I also wrote a concurrent reference counted cycle collector in Rust (https://github.com/chc4/samsara) though never published it to crates.io. It's neat to see the different choices that people made implementing similar goals, and dumpster works pretty differently from how I did it. I hit the same problems wrt concurrent mutation of the graph when trying to count in-degree of nodes, or adding references during a collection - I didn't even think of doing generational references and just have a RwLock...
This is really impressive work and I applaud the author for building something that I'm sure lots of folks will find interesting and possibly very useful, but I want to say that I think there's a reason reference semantics (using and sharing heap allocations) are hard in Rust: It's because references are just plain hard to use safely. Rust tries to make the gnarly things awkward, but what is the easy path?
If you look at the Hylo (formerly Val as of 3 days ago) language [0] that folks like Dave Abrahams have been working on, they're outright saying to just not use reference semantics if you can avoid it. In this talk at CppCon about Value Semantics, Dave argues that we should be decoupling object graphs from access to objects [1]. That's right folks, using `usize` indexes into collections, or adjacency lists, isn't just a hack to get around the borrow checker as people like Johnathan Blow have famously critiqued [2], it may just be the right way of doing things.
[0] https://www.hylo-lang.org
I'm going to point out one potential footgun with your library: circularly-linked Drops.
If you have values A and B, both instances of T that implement Drop and hold a Gc to one another, then either A sees a dropped B or B sees a dropped A, and you get UB. Technically this isn't a problem because you already marked it as an unsafe trait, but your documentation should also mention this problem.
You have a safe derive macro for Collectable, however, so it needs to reject Drop. This is possible with some weird macro magic[0].
For those wondering, while Python doesn't have UB, it used to enforce the same rules until PEP 442[1]. Circularly linked garbage that implemented __del__ would instead get stored in sys.gc.garbage and you'd have to go in there and break references on __del__ types. However, native code objects will actually still trigger this behavior[2] presumably to avoid UB.
I have no clue if Java finalizers need to worry about this.
[0] In Ruffle we use gc_arena as our garbage collector. It enforces no_drop in it's Collect derive macro. See: https://github.com/kyren/gc-arena/blob/master/src/gc-arena-d...
Actually, I lied: no_drop is one of two safe constraints you can use Collect with. The alternative is require_static, which only works because gc_arena treats the entire GC heap as a data structure that is owned and has a lifetime that all Gc pointers borrow. This doesn't work for dumpster, though, so ignore it.
[1] https://peps.python.org/pep-0442/
[2] https://docs.python.org/3/library/gc.html#gc.garbage