rust-typed-arena

typed-arena is a minimal Rust crate implementing an allocation arena for values of a single type. Instead of allocating and freeing each value individually, values are pushed into growable internal chunks and the entire arena is torn down at once when it goes out of scope — allocation is typically just a vector push, making it dramatically cheaper than per-value heap allocation for workloads that build up many short-lived, same-typed objects.

Because every value allocated in an arena shares the same lifetime, the crate makes it safe to build self-referential and cyclic structures — graphs, trees with parent pointers, interpreter ASTs — without reference counting or unsafe lifetime tricks in user code. The crate itself is no_std-compatible (via the alloc crate), has zero runtime dependencies, and exposes a deliberately small API surface: Arena::new, alloc, alloc_extend, and into_vec cover the vast majority of use cases.

What You Get

• Arena<T> — a single-type allocation arena backed by internally chunked, growable Vec<T> storage
• alloc(value) -> &mut T — near-constant-time allocation via a fast-path vector push, falling back to chunk growth only when the current chunk is full
• alloc_extend(iterator) -> &mut [T] — bulk allocation of an iterator’s items into a single contiguous mutable slice
• alloc_str on Arena<u8> for allocating string slices backed by the arena’s byte storage
• into_vec() to reclaim ownership of every allocated value as a Vec<T> when the arena is no longer needed
• iter_mut() for mutating every value allocated so far, in allocation order
• no_std support via the alloc crate, with a std feature enabled by default

Common Use Cases

• Building ASTs or intermediate representations in a compiler or interpreter, where nodes reference sibling and parent nodes for the lifetime of a single compilation pass
• Constructing graphs or trees with cyclic or parent-pointer references that would otherwise require Rc<RefCell<>> and runtime borrow checks
• Bulk-allocating many short-lived, same-typed objects in a hot loop (e.g. game entities per frame, parser tokens) where per-value heap churn would dominate
• Any algorithm that allocates a large, unknown-in-advance number of values of one type and frees them together, rather than individually, once processing finishes

Under The Hood

Architecture The crate centers on a single Arena<T> struct wrapping a RefCell<ChunkList<T>>, where ChunkList holds a current growable Vec<T> plus a rest: Vec<Vec<T>> of previously filled chunks. alloc first tries a fast path that pushes directly into current when capacity allows (alloc_fast_path), falling back to alloc_slow_path → alloc_extend, which reserves a new, larger chunk (ChunkList::reserve, doubling capacity or fitting the requested size, whichever is larger) and moves the old current into rest. Returned references are extended via raw pointers to the arena’s own lifetime, an unsafe operation whose soundness rests on the documented invariant that items are never moved once pushed within a chunk’s initial capacity — the crate is exercised under Miri in CI specifically to validate this. IterMut implements a small state machine (IterMutState::ChunkListRest / ChunkListCurrent) to walk rest chunks followed by the live current chunk in allocation order.

Tech Stack Pure Rust with zero runtime dependencies (the Cargo.toml [package] section declares no [dependencies] entries at all); a separate benches/ workspace member pulls in criterion for benchmarking only. The crate is #![no_std]-compatible when the default std feature is disabled, switching between alloc::vec::Vec and core-only primitives (RefCell, MaybeUninit, ptr, slice) accordingly. CI (.github/workflows/ci.yml) exercises stable, beta, nightly, and a pinned MSRV of Rust 1.42 across Linux, macOS, and both 32- and 64-bit Windows targets, plus a --no-default-features build to verify the no_std path independently.

Code Quality src/test.rs (nearly 400 lines) exercises allocation ordering, drop semantics via a DropTracker helper, panic-unwind safety (AssertUnwindSafe), and iterator correctness against the internal chunk-boundary edge cases. CI additionally runs cargo fmt --all -- --check for formatting, cargo doc --all-features with -Dwarnings to catch broken doc links, and — notably for a crate built on unsafe raw-pointer lifetime extension — cargo miri test --all-features to catch undefined behavior and provenance violations that ordinary tests can’t detect. No unsafe block goes unexplained; each carries a comment justifying the invariant it relies on.

API Design The public surface is intentionally tiny: construct with Arena::new() or Arena::with_capacity(n), call .alloc(value), and optionally .into_vec() at the end — most examples in the docs are two or three lines. Every public method carries a runnable doctest demonstrating its exact usage, and the README explicitly points readers toward bumpalo, id-arena, or generational-arena when their needs (heterogeneous types, identifier-based access, or individual deallocation) fall outside this crate’s narrow scope — an unusually candid piece of API-boundary documentation for a small crate.