Moving GC Arena

This is a library for indexed regions supporting fast allocation, with efficient garbage collection, traversals, and deep cloning. In effect, it supplies an indexed Vec with a garbage collector and user-accessible marking/cloning.

It was created because there was no library at the time which provided the needs:

• The ability to create cyclic graphs
• Sound garbage collection without scanning the stack and there was no obvious partial benefit from trying to build on top of existing libraries.

You should use this library if you want to keep a safe cyclic graph data structure, with simple, performant garbage collection. Access to GC operations exposes efficient traversals and cloning. This library does not read the Rust stack, instead, roots are acquired resources, which can be used like any other resource and dropped as normal. It compiles on stable 2018 Rust and requires only minimal unsafe code for most operations. Dereferencing indices uses a reference to the region, giving strong safety guarantees.

You should not use this library if you have very hard real-time requirements and cannot pre-allocate. In the current version, only single-threaded use is possible. Because of the algorithms chosen, this library is well-suited for frequent allocations, much like arena allocation.

Details of features and limitations

• Members are a fixed type and size.
• Regions and most indices are not Send/Sync in the current version.
• Drop implementations are called as normal whenever an object is collected. There are no finalizers which can read the region state.
• Garbage collection may be performed both automatically and manually. Every buffer reallocation triggers a garbage collection for the best performance.
• Garbage collection is quick: It does not scan the stack, and requires no extra allocation.
• Size cannot yet be tuned: We always double the size at least. Calling a manual gc will shrink the allocation.
• An optional features allows indices to check region and generation information.

Example Usage

use moving_gc_arena as gc;

let mut r = gc::Region::new();

struct Adj(Vec<gc::Ix<Adj>>);
impl gc::HasIx<Adj> for Adj {
 fn foreach_ix<'b, 'a : 'b, F>(&'a mut self, mut f: F) where
     F: FnMut(&'b mut gc::Ix<T>)
 {
     self.0.foreach_ix(f);
 }
}
impl Adj {
    fn new() -> Self {
        Adj(Vec::new())
    }
}

let mut obj1 = r.alloc(|_|{Adj::new()}).root();
let mut obj2 = r.alloc(|_|{Adj::new()}).root();
let mut obj3 = r.alloc(|_|{Adj::new()}).root();

// mutual cycle
r[&obj1].0.push(obj2.ix());
r[&obj2].0.push(obj1.ix());

// self-cycle
r[&obj3].0.push(obj3.ix());

std::mem::drop(obj1);
std::mem::drop(obj3);

r.gc(); // optional manually-triggered collection
//obj3 now collected but obj1 and obj2 are live