gc-lang 1.0.0

Overview

gc-lang gives an interpreted-language runtime one thing, done carefully: a heap it can allocate objects into and periodically sweep, reclaiming everything no longer reachable — cycles included. Allocate a value into a Heap<T> and hold the returned Gc<T> handle; objects store handles to point at one another; when the runtime hands its roots to collect, the collector traces the reachable graph and frees the rest.

It is a tracing mark-and-sweep collector, and it is entirely safe — the crate is #![forbid(unsafe_code)]. Two design choices carry that:

• Reachability, not reference counting. What lives is decided by tracing from roots, so unreachable cycles are reclaimed. A runtime can build arbitrary object graphs — back-edges, doubly-linked structures, self-references — without leaking.
• Handles, not pointers. A Gc<T> is a slot index plus a generation stamp, not an address. Objects wire to each other by handle, so the graph never fights the borrow checker, and a handle to a collected object resolves to None instead of dangling. There is no use-after-free to have.

It owns object storage and reclamation only — no value representation, no interpreter, no policy on when to collect. The runtime keeps that control.

Features

• Cycle-collecting — tracing reachability reclaims what reference counting cannot.
• Safe by construction — #![forbid(unsafe_code)]; a stale handle reads as absent, never dangles.
• Generational handles — Gc<T> is Copy, eight bytes, and Eq/Ord/Hash for any T.
• Slot reuse — sweeping returns slots to a free list; steady-state loops never grow the store.
• Allocation-free collection — the mark queue and mark bitset are pooled across passes.
• no_std — needs only alloc; the default std feature changes nothing in the public surface.
• Zero runtime dependencies — the collector is self-contained.

Installation

[dependencies]
gc-lang = "1.0"

Or from the terminal:

cargo add gc-lang

no_std (needs a global allocator in your target):

[dependencies]
gc-lang = { version = "1.0", default-features = false }

Quick Start

use gc_lang::{Gc, Heap, Trace, Tracer};

// The runtime's value type. Compound variants own handles to other values;
// `trace` reports them so the collector can follow them.
enum Value {
    Number(f64),
    Pair(Gc<Value>, Gc<Value>),
}

impl Trace for Value {
    fn trace(&self, tracer: &mut Tracer<'_>) {
        if let Value::Pair(a, b) = self {
            tracer.mark(*a);
            tracer.mark(*b);
        }
    }
}

let mut heap = Heap::new();
let one = heap.alloc(Value::Number(1.0));
let two = heap.alloc(Value::Number(2.0));
let pair = heap.alloc(Value::Pair(one, two));
let unused = heap.alloc(Value::Number(3.0));

// Collect with `pair` as the only root: `pair`, `one`, `two` survive; `unused` does not.
let stats = heap.collect([pair]);
assert_eq!(stats.freed, 1);
assert!(heap.get(unused).is_none());
assert!(heap.get(one).is_some());

How It Works

A collection is two phases:

1. Mark. Starting from each root handle, the collector calls Trace::trace on every object it reaches and follows the handles that object reports. Each object is visited once, so cycles terminate and shared subgraphs are not re-scanned. Marks live in a packed bitset, one bit per slot.
2. Sweep. Every object not marked is dropped, its slot's generation is advanced — which invalidates any outstanding handle to it — and the slot is returned to a free list for the next allocation to reuse.

The generation stamp is the safety mechanism: because a reused slot carries a new generation, a handle to a collected object no longer matches whatever now lives there. It resolves to None, never to an unrelated value.

The cost is O(reachable) to mark plus O(slots) to sweep. The mark queue and the mark bitset are retained between calls, so a steady-state collection allocates nothing.

Examples

Runnable examples live in examples/:

cargo run --example cycle_collection   # reclaim a reference cycle reference-counting can't
cargo run --example mini_interpreter   # a GC'd value heap rooted at an operand stack
cargo run --example object_graph       # shared subgraphs and a shrinking root set

Performance

Latest local Criterion means (release build, WSL2 Ubuntu on Windows x86_64). Numbers vary by CPU and environment; reproduce with cargo bench.

Collection scales linearly with heap size: ~10.8 µs for 1,000 reachable nodes, ~1.24 ms for 100,000.

Cross-Platform

Pure safe Rust on alloc, with no platform-specific code paths. The full suite runs on Linux, macOS, and Windows (x86_64 and ARM64) across the CI matrix on stable and the 1.85 MSRV.

Testing

cargo test --all-features          # unit + property + doc tests
cargo test --no-default-features   # no_std build
cargo bench                        # Criterion benchmarks

The property suite checks the collector's core invariant — an object is live after a collection if and only if it was reachable from a root — against an independent breadth-first walk over arbitrary generated graphs, cycles and shared subgraphs included.

Status

Stable — 1.0.0 is the API freeze. The public surface is frozen and will not break until 2.0; 1.x releases are additive only. See the SemVer promise, docs/API.md, the ROADMAP, and CHANGELOG.md.

Contributing

Engineering standards live in REPS.md; the phase plan is in dev/ROADMAP.md. Before a PR, all of the following must be clean:

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test --all-features