# safe-gc

A Rust crate providing a garbage-collected heap with zero `unsafe` code — neither in the public API nor internally. Written by Nick Fitzgerald (Wasmtime, Cranelift) as a demonstration that careful API design can replace `unsafe` even in a domain that is historically one of its last refuges.

## How it works

The heap is a `HashMap<TypeId, Box<dyn ArenaObject>>`, one arena per concrete type. Each arena is a `Vec` of slots plus a free list. References come in two forms:

- `Gc<T>` — `Copy`, cheap, does not root. Safe across code that won't trigger collection.
- `Root<T>` — rooted, not `Copy`, `Drop` unroots. Required for references held across allocations.

You can't `deref` either type. To read an object you index into the heap:

```rust
let h: Heap = Heap::new();
let r: Root<Foo> = h.alloc(Foo { ... });
let v: &Foo = &h[&r];
```

This is the whole safety story. Because access goes through `Index`/`IndexMut` on the heap, the returned reference's lifetime is tied to the borrow of the heap — Rust's normal rules apply, no `unsafe` required to express it.

The collector is mark-and-sweep. Fitzgerald tried copying first and abandoned it — forwarding-pointer updates couldn't be expressed without either `unsafe` or borrowing conflicts he couldn't resolve in a heterogeneous heap. Mark-and-sweep fell out in about half an hour because nothing has to move.

## Basic usage

```rust
use safe_gc::{Heap, Trace, Collector, Gc, Root};

struct Node {
    value: i32,
    next: Option<Gc<Node>>,
}

impl Trace for Node {
    fn trace(&self, collector: &mut Collector) {
        if let Some(next) = &self.next {
            collector.edge(next);
        }
    }
}

let mut heap = Heap::new();
let tail: Root<Node> = heap.alloc(Node { value: 2, next: None });
let head: Root<Node> = heap.alloc(Node {
    value: 1,
    next: Some(tail.unrooted()),
});
```

`Trace` is a safe trait — getting it wrong produces logical bugs (objects freed prematurely) but not memory unsafety, because dangling `Gc<T>` accesses either hit a still-alive slot, panic, or observe ABA reuse.

## Limitations

- Not a high-performance collector. Arenas, free lists, stop-the-world mark-and-sweep.
- Per-type arenas mean heterogeneous graphs pay a dispatch cost per edge.
- No generational or incremental collection.
- The indexing API is more verbose than `*gc_ptr` — every read passes through the heap.

## When to reach for it

Interpreters, DSL runtimes, or embedded scripting where you want garbage collection semantics, want to run in `#![forbid(unsafe_code)]` environments, and don't need production-JVM throughput. The write-up is also worth reading as a general exercise in API-design-as-safety-proof, independent of whether you ever use the crate.

## Repo

[github.com/fitzgen/safe-gc](https://github.com/fitzgen/safe-gc) — Apache-2.0 OR MIT. See [[safe-gc|the write-up summary]] for the design rationale.