Rust's Lifetime Branding using the 'Arena Pattern'

Exploring how Rust uses Lifetime Branding to achieve Compile-Time Ownership Boundries using the 'Arena Pattern'

Introduction

The concept of PhantomData is a relatively difficult Rust concept for beginners (I think). Let's demystify it!

At its core PhantomData is just a type. Specifically, its a zero-sized type that comunicates to the compiler that some struct is associated with some type T, even though T is not actually present in any of the fields found in the struct. Its a sort of "trust me bro" for the compiler.

The simplest PhantomData application (and the most prevelent in Rust code in the wild) is its use in Ownership Simulation. We have probably all seen code like this:

struct Foo {
    data: Vec,
    _marker: PhantomData
}

This is essentially equivalent to:

struct Foo {
    data: Vec,
}

However, using the PhantomData version allows us to create subtypes using other zero-types like so:

use std::marker::PhantomData;

// type-states (zero-type):
struct Bar;
struct Baz;

// the "main" type:
struct Foo {
    data: Vec,
    _marker: PhantomData
}

// now this is possible:
type FooBar = Foo;
type FooBaz = Foo;

// functions that can ONLY take certain subtypes:
fn take_foobar(foo_bar: FooBar) {}
fn take_foobaz(foo_baz: FooBaz) {}

fn main() {
    let my_foo_bar: FooBar = Foo { data: vec![1, 2, 3, 4], _marker: PhantomData };
    let my_foo_baz: FooBaz = Foo { data: vec![1, 2, 3, 4], _marker: PhantomData };

    // works:
    take_foobar(my_foo_bar);
    take_foobaz(my_foo_baz);

    // FAILS:
    // - compiler error: "expected Foo, found Foo"
    // take_foobar(my_foo_baz);
}

But we are not here to talk about ownership simulation. There's no point, its too simple. We are here to discuss Lifetime Branding using the "Arena Pattern" (and perhaps a bit of Variance Control).

Exciting stuff!

The "Arena Pattern" and Lifetime Branding

An Arena is a programming concept in the realm of memory allocation. In its most layman terms, the pattern goes like this: 1) you allocate some big chunk of memory up front 2) you freely hand out chunks of memory as needed (mister Johnny Memoryseed over here!) 3) at the end you release all of the originally-allocated memory all at once when the whole execution ends.

A Handle is a concept tied to the arena pattern. Its a structured way to refer to data without holding a direct memory reference. Its called a "handle" because you access the data indirectly through a wrapper, instead of using direct references or raw pointers.

Think of it as a "Coat-Check Ticket" at some restaurant. You drop off your coat (data) to the restaurant's coat-check place (arena) and receive a ticket (handle). You no longer "control" the coat, but because you hold the ticket (handle), at any time you can return to the coat-check place (arena) and "access" your coat (data).

Continuing with this metaphor, the concept of Lifetime Branding comes into play here - you have to return to the correct arena (the same coat-check place) to use your handle. If you checked your coat at some Italian restaurant and later tried to retrieve it at the new sushi place down the street, you will be coatless and confussed.

In other words, lifetime branding prevents you from using 'Handle X' with 'Arena Y'.

The Used Car Dealership

Let's put all these hypotheticals into practice. For this example, let's simulate a Used Car Dealership. I find that using relatable examples is much more digestible then the typical "graph and node" examples you most commonly find when searching for this topic.

And digestability is key here because we are going to learn some neat stuff!

We are going to learn how PhantomData<&'a ()> signals covariance of &'a over 'a. How Lifetime Branding enforces compile-time ownership boundries. How HRTBs (ex: for<'a>) quantify over all lifetimes to prevent escape. And even how RefCell handles runtime mutability while PhantomData handles compile-time tracking.

Code Time

Ok enough chit-chat. Time to put hands to keyboard (no vibes here).

We are only using Rust standard library here so let's first import our std friends:

use std::{
    cell::{
        RefCell,        // only really need this from `std::cell::`
        Ref, RefMut     // these are only here b/c I am OCD about typing everything in my code :D
    },
    marker::PhantomData,
};

Now, let's define our Car type along with some implementations.

I like using the newtype pattern wherever I can to prevent passing the wrong type to functions (see also my OCD about static typing everything). Our Car type is just a fancy String, but I want the compiler to catch me if I try to pass a normal String to a function that requires Car:

#[derive(Clone, Debug)]
struct Car(String);

// - impl `.new()`:
impl Car {
    fn new(make_model: &str) -> Self {
        Self( make_model.to_string() )
    }
}

// - impl `Display` for printing:
impl std::fmt::Display for Car {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

Ok let's get down to the juicy parts. We will now define our Arena, the "Dealership". The important concept here is the Lifetime Branding ('arena) that we will give our Arena. We do this by giving it a PhantomData field with the 'arena lifetime. It will also have an inventory field that holds all our Cars as a vector in a RefCell for mutability:

#[derive(Debug)]
struct Dealership<'arena> {
    inventory: RefCell<Vec<Car>>,
    _phantom: PhantomData<&'arena ()>
}

Next, let's define our Handle. We will use the same Lifetime Branding ('arena) here for pretty obvious reasons. We also include an index field, which will be how we can access an individual Car from the inventory:

struct CarHandle<'arena> {
    car_index: usize,
    _brand: PhantomData<&'arena ()>
}

Now, let's go back to our Dealership for some implementations. We only need two methods here, but the important thing is to see that in both we set our bounds to the same 'arena lifetime.

impl<'arena> Dealership<'arena> {
    fn add_car(&self, car: Car) -> CarHandle<'arena> {
        // - Grab `inventory`:
        let mut inventory: RefMut<'_, Vec<Car>> = self
            .inventory
            .borrow_mut();
        // - Extract index:
        let current_car_index: usize = inventory.len();
        // - Add `Car` to `inventory`:
        inventory.push( car );
        // - Return 'Handle'
        // - NOTE: this also sets the `car_index` to the one we just extracted above
        CarHandle {
            car_index: current_car_index,
            _brand: PhantomData
        }
    }

    fn get_car(&self, handle: &CarHandle<'arena>) -> Car {
        // - Grab `inventory`:
        let inventory: Ref<'_, Vec<Car>> = self
            .inventory
            .borrow();
        // - Extract `Car` by index:
        inventory[handle.car_index].clone()
    }
}

Last, but certainly not least, let's define our with_dealership() function. There's a bit to unpack here (hello, fellow Millenials!).

fn with_dealership<R>(f: impl for<'arena> FnOnce(&Dealership<'arena>) -> R) -> R {
    // Init a `Dealership` Arena:
    let dealership: Dealership<'_> = Dealership {
        inventory: RefCell::new( Vec::new() ),
        _phantom: PhantomData
    };
    // Pass the Arena to the closure, eval, return:
    f(&dealership)
}

// - For "Cool Guy's Used Cars":
let camry: Car = Car::new("1995 Toyota Camry");
let civic: Car = Car::new("2010 Honda Civic Si");
// - For "Crazy Gary's Car Emporium":
let ford: Car = Car::new("2002 Ford F-150");

// "Cool Guy's Used Cars"
// - 2 cars
with_dealership(|cool_guys| {
    // - Create Car Handles with `.add_car()`:
    let camry_handle: CarHandle<'_> = cool_guys.add_car(camry);
    let civic_handle: CarHandle<'_> = cool_guys.add_car(civic);

    // - Each `Car` and its index can be accessed via `get_car()`:
    println!("Car #{}: {}", camry_handle.car_index, cool_guys.get_car(&camry_handle));
    // Car #0: 1995 Toyota Camry
    println!("Car #{}: {}", civic_handle.car_index, cool_guys.get_car(&civic_handle));
    // Car #1: 2010 Honda Civic Si
});

// "Crazy Gary's Car Emporium"
// - 1 car
with_dealership(|crazy_gary| {
    // - Create Car Handles with `.add_car()`:
    let ford_handle: CarHandle<'_> = crazy_gary.add_car(ford);

    // - Each `Car` and its index can be accessed via `get_car()`:
    println!("Car #{}: {}", ford_handle.car_index, crazy_gary.get_car(&ford_handle));
    // Car #0: 2002 Ford F-150

    // // *VIP CONCEPT - FAILURE*
    // - Trying to access a "Cool Guy's" car here WILL NOT WORK:
    // println!("Car #{}: {}", camry_handle.car_index, cool_guys.get_car(&camry_handle));
    // - The compiler errors:
    // "cannot find value `cool_guys` in this scope"
    // "cannot find value `civic_handle` in this scope"
});