A deep technical exploration of implementing safe tracing garbage collection and cyclic pointer handling in safe (no unsafe{}) idiomatic code. The post covers why cyclic references are fundamentally hard in safe due to its ownership-based memory model, then walks through progressively better solutions: Vec-based indexing with generational indexes, the ABA problem and arena IDs, and finally a compile-time-safe GC using generativity (invariant lifetimes via PhantomData and for<'a> HRTBs). The author draws on real-world experience building gc-arena, used in the Flash emulator and a GameMaker replacement runtime, to motivate the problem and demonstrate that these advanced techniques are viable in production code.
Table of contents
IntroductionBackgroundPointers in Rust without clear ownership is Very HardRust is actually just really good at VecBut Rust is pretty bad at safe circular referencesGenerativity, or for<'a> is the coolest feature in RustDealing with "reachability" via tracingA sketch of a real, raw-pointer based GCWrapping up -- The Bigger PictureSort: