🎬 Rust Ownership in 30 seconds Visual walkthrough of ownership, moves, and automatic memory management.

📝 Text version (for readers / accessibility)

• Each value in Rust has exactly one owner — when the owner goes out of scope, the value is dropped

• Assignment moves ownership by default; the original binding becomes invalid

• Borrowing (&T / &mut T) lets you reference data without taking ownership

• The compiler enforces: many shared references OR one mutable reference, never both

• No garbage collector needed — memory is freed deterministically at scope exit

552: Arena with Lifetimes

Difficulty: 4 Level: Advanced Allocate many objects with a single lifetime and free them all at once.

The Problem This Solves

When you're building a compiler, game engine, or parser, you often create thousands of small objects (AST nodes, entities, tokens) that all live until a specific phase ends. Individually allocating and dropping each one is slow and complicates ownership. You'd also like to give out references to these objects that the compiler can verify are valid as long as the arena is alive. An arena allocator solves this: bump-allocate into a backing store, hand out references with the arena's lifetime, and drop everything at once when the arena goes out of scope. There's no individual deallocation. The lifetime of every object in the arena is tied to the lifetime of the arena itself. In Rust, the borrow checker makes this particularly elegant: references into the arena carry the arena's lifetime `'a`, so the compiler statically proves they can't outlive the arena. If you keep objects separate (e.g., store indices rather than references), you avoid the borrow-check complexity of mutating the arena while holding references into it.

The Intuition

Think of an arena like a scratch pad. You write things on it. You can hand out addresses of things you wrote. When you're done with the whole session, you throw the pad away — in one move. You never erase individual entries. The address is valid as long as the pad exists. The index-based approach (storing positions instead of raw references) sidesteps the Rust rule that you can't mutate a container while holding references into it. Allocate first, then read — or just use indices and never hold references across mutations.

How It Works in Rust

1. Index-based arena — `alloc(&mut self, value: T) -> usize` pushes into a `Vec`, returns the index; `get(&self, idx: usize) -> Option<&T>` returns a reference tied to `&self`. 2. Lifetime-tied references — `fn alloc_and_get(&mut self, value: T) -> &T` borrows `&mut self` and returns `&T` with the arena's lifetime; valid as long as `&self` is not mutably borrowed again. 3. AST slices from source — `AstNode<'src>` borrows `&'src str` from the source string; the arena (a `Vec`) and the source can have independent lifetimes, both tracked by the compiler. 4. Batch free — when the arena drops, all its allocations drop simultaneously; no individual `drop` calls needed. 5. Borrow discipline — to read many items simultaneously after allocation, finish all mutations first, then take references: the borrow checker enforces this ordering.

What This Unlocks

Build compilers and parsers where all AST nodes share a phase lifetime without per-node allocation.
Avoid the performance cost of many small heap allocations in tight inner loops.
Get static proof that no object outlives the phase that owns the arena.

Key Differences

Concept	OCaml	Rust
Object lifetimes	GC; individual objects freed lazily	Arenas: explicit phase lifetime; freed in bulk
References into collections	Safe; GC prevents dangling	Must borrow arena immutably to get refs; can't mutate while holding them
AST node lifetimes	GC-backed; no annotation	Lifetime parameter `'src` ties node slices to source string
Bump allocation	Libraries exist; GC still manages	Index-based arena avoids borrow conflicts; `typed-arena` crate for ref-based

//! # 552. Arena with Lifetimes
//! Bump allocator enabling batch allocation and deallocation.

/// Simple arena that bump-allocates into a Vec<Box<T>>
/// Returns indices instead of references to avoid borrow conflicts
struct Arena<T> {
    items: Vec<T>,
}

impl<T> Arena<T> {
    fn new() -> Self { Arena { items: Vec::new() } }

    /// Allocate value, return index for later retrieval
    fn alloc(&mut self, value: T) -> usize {
        self.items.push(value);
        self.items.len() - 1
    }

    fn get(&self, idx: usize) -> Option<&T> {
        self.items.get(idx)
    }

    fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
        self.items.get_mut(idx)
    }

    fn len(&self) -> usize { self.items.len() }
    fn is_empty(&self) -> bool { self.items.is_empty() }
}

/// Safe reference-returning arena using separate scope
struct BorrowArena<T>(Vec<Box<T>>);

impl<T> BorrowArena<T> {
    fn new() -> Self { BorrowArena(Vec::new()) }

    /// SAFETY: The lifetime of the returned reference is tied to &self
    /// This pattern requires that allocations happen before reads
    fn alloc_and_get(&mut self, value: T) -> &T {
        self.0.push(Box::new(value));
        self.0.last().unwrap()
    }

    fn get_all(&self) -> Vec<&T> {
        self.0.iter().map(|b| b.as_ref()).collect()
    }
}

/// AST node that borrows from source string with arena lifetime
#[derive(Debug)]
enum AstNode<'src> {
    Literal(&'src str),
    Ident(&'src str),
    BinOp {
        op: &'src str,
        left: usize,
        right: usize,
    },
}

fn main() {
    // Index-based arena (avoids borrow conflicts)
    let mut arena: Arena<i32> = Arena::new();
    let idx1 = arena.alloc(42);
    let idx2 = arena.alloc(100);
    let idx3 = arena.alloc(200);
    println!("arena has {} items", arena.len());
    println!("r1={:?}, r2={:?}", arena.get(idx1), arena.get(idx2));
    println!("r3={:?}", arena.get(idx3));

    // All allocations done — now safe to get references simultaneously
    let all: Vec<_> = (0..arena.len()).filter_map(|i| arena.get(i)).collect();
    println!("all: {:?}", all);

    // String arena
    let mut string_arena: Arena<String> = Arena::new();
    let nodes = ["start", "middle", "end", "branch"];
    let indices: Vec<usize> = nodes.iter().map(|&n| string_arena.alloc(n.to_string())).collect();
    println!("\nString arena nodes:");
    for (name, &idx) in nodes.iter().zip(indices.iter()) {
        println!("  {} -> idx={}, stored={:?}", name, idx, string_arena.get(idx));
    }

    // AST arena — nodes borrow from source string
    let source = "x + y * 42";
    let mut ast_arena: Vec<AstNode<'_>> = Vec::new();
    ast_arena.push(AstNode::Ident(&source[0..1]));
    ast_arena.push(AstNode::Ident(&source[4..5]));
    ast_arena.push(AstNode::Literal(&source[8..10]));
    ast_arena.push(AstNode::BinOp { op: "*", left: 1, right: 2 });
    ast_arena.push(AstNode::BinOp { op: "+", left: 0, right: 3 });

    println!("\nAST:");
    for (i, node) in ast_arena.iter().enumerate() {
        println!("  [{}] {:?}", i, node);
    }
    // All AST nodes freed when ast_arena drops
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_arena_alloc() {
        let mut arena: Arena<i32> = Arena::new();
        let i1 = arena.alloc(42);
        let i2 = arena.alloc(100);
        assert_eq!(arena.get(i1), Some(&42));
        assert_eq!(arena.get(i2), Some(&100));
        assert_eq!(arena.len(), 2);
    }

    #[test]
    fn test_arena_sequential_alloc() {
        let mut arena: Arena<String> = Arena::new();
        for i in 0..5 {
            arena.alloc(format!("item_{}", i));
        }
        assert_eq!(arena.len(), 5);
        assert_eq!(arena.get(2), Some(&"item_2".to_string()));
    }

    #[test]
    fn test_arena_get_oob() {
        let arena: Arena<i32> = Arena::new();
        assert_eq!(arena.get(0), None);
    }
}

(* Arena allocation in OCaml *)
(* OCaml's GC is essentially a generational arena *)
(* Simulating with a list that holds all allocated nodes *)

type 'a arena = 'a list ref

let make_arena () = ref []

let alloc arena value =
  arena := value :: !arena;
  value  (* returns the value -- in real arena, returns pointer *)

type node = {
  id: int;
  label: string;
  mutable edges: node list;
}

let make_node arena id label =
  alloc arena { id; label; edges = [] }

let add_edge from_node to_node =
  from_node.edges <- to_node :: from_node.edges

let () =
  let arena = make_arena () in
  let n1 = make_node arena 1 "start" in
  let n2 = make_node arena 2 "middle" in
  let n3 = make_node arena 3 "end" in
  add_edge n1 n2; add_edge n2 n3; add_edge n1 n3;
  Printf.printf "n1 edges: %d\n" (List.length n1.edges);
  Printf.printf "total nodes: %d\n" (List.length !arena);
  (* "Free" the arena: *)
  arena := []