Struct safe_gc::Heap

pub struct Heap { /* private fields */ }

A collection of GC-managed objects.

A Heap is a collection of GC-managed objects that can all reference each other, and garbage collection is performed at the Heap granularity. The smaller the Heap, the less overhead imposed by garbage collecting it. The larger the Heap, the more overhead is imposed.

There are no restrictions on the shape of references between GC-managed objects within a Heap: references may form arbitrary cycles and there is no imposed ownership hierarchy.

Allocating Objects

You can allocate objects with the Heap::alloc method.

You can allocate instances of any number of heterogeneous types of GC-managed objects within a Heap: they may, for example, contain both Cons objects and Tree objects. Heaps are not constrained to only instances of a single, uniform T type of GC objects.

All types allocated within a heap must, however, implement the Trace trait. See the Trace trait’s docs for more details.

use safe_gc::{Gc, Heap, Trace};

struct Tree<T: Trace> {
    value: Gc<T>,
    parent: Option<Gc<Tree<T>>>,
    left: Option<Gc<Tree<T>>>,
    right: Option<Gc<Tree<T>>>,
}

impl<T: Trace> Trace for Tree<T> {
    // See the docs for `Trace` for details...
}

struct Cat {
    cuteness: u32,
    cat_tree: Option<Gc<Tree<Cat>>>,
}

impl Trace for Cat {
    // See the docs for `Trace` for details...
}

let mut heap = Heap::new();

// Allocate a cat within the heap!
let goomba = heap.alloc(Cat {
    cuteness: u32::MAX,
    cat_tree: None,
});

// Also allocate a tree within the heap!
let tree = heap.alloc(Tree {
    value: goomba.unrooted(),
    parent: None,
    left: None,
    right: None,
});

// Create a cycle: the `tree` already references `goomba`, but now
// `goomba` references the `tree` as well.
heap[goomba].cat_tree = Some(tree.into());

Accessing Allocating Objects

Rather than dereferencing pointers to allocated GC objects directly, you must use one of two types (Gc<T> or Root<T>) to index into the Heap to access the referenced T object. This enables safe-gc’s lack of unsafe code and allows the implementation to follow Rust’s ownership and borrowing discipline.

Given a Gc<T> or Root<T>, you can use the Heap::get method to get an &T. Similarly, you can use the Heap::get_mut method to get an &mut T. As convenient syntactic sugar, Heap also implements std::ops::Index and std::ops::IndexMut as aliases for get and get_mut respectively.

The Gc<T> index type is an unrooted reference, suitable for defining references to other GC-managed types within a GC-managed type’s definition.

The Root<T> index type is a rooted reference, prevents its referent from being reclaimed during garbage collections, and is suitable for holding GC-managed objects alive from outside of the Heap.

See the docs for Gc<T> and Root<T> for more details, how to convert between them, and other examples.

use safe_gc::{Heap, Trace};

struct Point(u32, u32);

impl Trace for Point {
    // ...
}

let mut heap = Heap::new();

let p = heap.alloc(Point(42, 36));

// Read data from an object in the heap.
let p0 = heap[&p].0;
assert_eq!(p0, 42);

// Write data to an object in the heap.
heap[&p].1 = 5;

When Can Garbage Collections Happen?

There are two ways to trigger garbage collection:

1. When the Heap::gc method is explicitly invoked.

2. When allocating an object in the heap with Heap::alloc.

Note that both of those methods require an &mut self, so they cannot be invoked when there are shared &Heap borrows. Therefore, when there are shared &Heap borrows, you may freely use Gc<T> instead of Root<T> to hold references to objects in the heap without fear of the GC collecting the objects out from under your feet. Traversing deeply nested structures will have more overhead when using Root<T> than when using Gc<T> because Root<T> must maintain its associated entry in the heap’s root set.

Finalization and Drop

Unlike many GC libraries for Rust, it is perfectly safe and footgun-free to put Drop types in the GC heap, even if they have references to other GC objects. Finalization of and Drop implementations for GC objects is usually tricky because of the risks of accessing objects that have already been reclaimed by the collector or accidentally entrenching objects and making them live again.

The reason this is fine with safe-gc is because the Drop implementation doesn’t have access to a Heap, so it statically cannot suffer from those kinds of bugs.

Cross-Heap GC References

Typically, GC objects will only reference other GC objects that are within the same Heap. In fact, edges reported to the Collector must point to objects within the same Heap as the object being traced or else Collector::edge will raise a panic.

However, you can create cross-heap edges with Root<T>, but it requires some care. While a Root<T> pointing to an object in the same Heap will make all transitively referenced objects unreclaimable, a Root<T> pointing to an object in another heap will not indefinitely leak memory, provided you do not create cycles across Heaps. To fully collect all garbage across all Heaps, you will need to run GC on each Heap either

• in topological order of cross-Heap edges, if you statically know that order in your application, or

• in a fixed point loop, if you do not statically know that order.

However, if you don’t statically know that topological order, it is recommended that you don’t create cross-Heap edges; you will likely accidentally create cycles and leak memory. Instead, simply put everything in the same Heap.

Collecting cycles across Heaps would require a global, cross-Heap collector, and is not a goal of this crate. If you do choose to create cross-Heap references, the responsibility of avoiding cross-Heap cycles is yours.

Implementations

impl Heap

pub fn new() -> Self

Construct a new Heap.

Example

use safe_gc::Heap;

let heap = Heap::new();

pub fn alloc<T>(&mut self, value: T) -> Root<T>

where T: Trace,

Allocate an object in the heap.

Example

use safe_gc::{Gc, Heap, Trace};

struct List {
    value: u32,
    prev: Option<Gc<List>>,
    next: Option<Gc<List>>,
}

impl Trace for List {
    // See the docs for `Trace` for details...
}

let mut heap = Heap::new();

// Allocate an object in the heap.
let list = heap.alloc(List {
    value: 10,
    prev: None,
    next: None,
});

pub fn get<T>(&self, gc: impl Into<Gc<T>>) -> &T

where T: Trace,

Get a shared reference to an allocated object in the heap.

You can also use std::ops::Index to access objects in the heap.

Example

use safe_gc::{Gc, Heap, Trace};

struct List {
    value: u32,
    prev: Option<Gc<List>>,
    next: Option<Gc<List>>,
}

impl Trace for List {
    // See the docs for `Trace` for details...
}

let mut heap = Heap::new();

// Allocate an object in the heap.
let list = heap.alloc(List {
    value: 10,
    prev: None,
    next: None,
});

// Access an allocated object in the heap.
let value = heap.get(list).value;
assert_eq!(value, 10);

pub fn get_mut<T>(&mut self, gc: impl Into<Gc<T>>) -> &mut T

where T: Trace,

Get a shared reference to an allocated object in the heap.

You can also use std::ops::Index to access objects in the heap.

Example

use safe_gc::{Gc, Heap, Trace};

struct List {
    value: u32,
    prev: Option<Gc<List>>,
    next: Option<Gc<List>>,
}

impl Trace for List {
    // See the docs for `Trace` for details...
}

let mut heap = Heap::new();

// Allocate an object in the heap.
let list = heap.alloc(List {
    value: 10,
    prev: None,
    next: None,
});

// Mutate an allocated object in the heap.
heap.get_mut(&list).value += 1;
assert_eq!(heap[list].value, 11);

pub fn root<T>(&self, gc: Gc<T>) -> Root<T>

where T: Trace,

Root a reference to a GC object.

This method upgrades a Gc<T> into a Root<T>. This is useful for holding references to GC-managed objects across operations that can potentially trigger garbage collections, making sure that the collector doesn’t reclaim them from under your feed.

Example

use safe_gc::{Gc, Heap, Root, Trace};

struct Node {
    value: u32,
    tail: Option<Gc<Node>>,
}

impl Trace for Node {
    // See the docs for `Trace` for details...
}

let mut heap = Heap::new();

let a = heap.alloc(Node { value: 0, tail: None });
let b = heap.alloc(Node { value: 1, tail: Some(a.into()) });

// Get a reference to a `Gc<T>` from the heap.
let b_tail: Gc<Node> = heap[b].tail.unwrap();

// Upgrade the `Gc<T>` to a `Root<T>` via the `Heap::root` method so it is
// suitable for holding across garbage collections.
let b_tail: Root<Node> = heap.root(b_tail);

// Now we can perform operations, like heap allocation, that might GC
// without worrying about `b_tail`'s referenced GC object from being
// collected out from under us.
heap.alloc(Node { value: 123, tail: None });

// And we can access `b_tail`'s referenced GC object again, after GC may
// have happened.
let b_tail_value = heap[&b_tail].value;
assert_eq!(b_tail_value, 0);

pub fn gc(&mut self)

Collect garbage.

Any object in the heap that is not transitively referenced by a Root<T> will be reclaimed.

Example

use safe_gc::Heap;

let mut heap = Heap::new();

allocate_a_bunch_of_stuff(&mut heap);

// Collect garbage!
heap.gc();

Trait Implementations

impl Default for Heap

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T> Index<&'a Root<T>> for Heap

where T: Trace,

type Output = T

The returned type after indexing.

fn index(&self, root: &'a Root<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> Index<Gc<T>> for Heap

where T: Trace,

type Output = T

The returned type after indexing.

fn index(&self, index: Gc<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> Index<Root<T>> for Heap

where T: Trace,

type Output = T

The returned type after indexing.

fn index(&self, root: Root<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, T> IndexMut<&'a Root<T>> for Heap

where T: Trace,

fn index_mut(&mut self, root: &'a Root<T>) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<T> IndexMut<Gc<T>> for Heap

where T: Trace,

fn index_mut(&mut self, gc: Gc<T>) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<T> IndexMut<Root<T>> for Heap

where T: Trace,

fn index_mut(&mut self, root: Root<T>) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.