`Box<T>`: Simple Heap Allocation

The most straightforward smart pointer is Box<T>, which allows you to store data on the heap rather than the stack. When you box a value, ownership of that value moves into the box. When the box goes out of scope, the boxed value is dropped and the memory is freed.

Using `Box<T>` to Store Data on the Heap

In most cases, we know at compile time whether we need data on the stack or the heap. However, there are cases where storing data on the heap is advantageous:

1. When you have a large value and want to move it cheaply

When you have a large struct, moving it by value copies all the data. Using Box<T> instead moves just a pointer:

struct LargeData {
    public data: Vec<Int>,
}

fn main() {
    // Without Box: this copies the entire Vec
    let large = LargeData { data: vec![1, 2, 3] }

    // With Box: only the pointer is moved
    let boxed = Box { LargeData { data: vec![1, 2, 3] } }
    processLargeData(boxed)
}

fn processLargeData(data: Box<LargeData>) {
    println!("Processing data")
}

2. When you need trait objects

The most important use of Box<T> is creating trait objects for dynamic dispatch. We'll explore this more in the OOP chapter, but here's a simple example:

public trait Draw {
    fn draw(): Void
}

fn main() {
    let shapes: Vec<Box<dyn Draw>> = vec![
        Box { Circle {} } as Box<dyn Draw>,
        Box { Square {} } as Box<dyn Draw>,
    ]

    for shape in shapes {
        shape.draw()
    }
}

3. When you want to avoid stack overflow

Very large structs can overflow the stack. Boxing the data allocates it on the heap instead:

// This could overflow the stack
struct HugeArray {
    public data: [Int; 1000000],  // 4MB on the stack!
}

// This is safer - only stores a pointer
let huge = Box { HugeArray { data: [0; 1000000] } }

Deref Coercion

Box<T> implements the Deref trait, which means you can use a boxed value as if it were a regular reference. This is called deref coercion.

fn main() {
    let boxed = Box { 5 }
    println!("Boxed value: \(boxed)")  // Automatically deref'd
}

fn printInt(value: &Int) {
    println!("The value is: \(value)")
}

fn main() {
    let boxed = Box { 5 }
    printInt(&boxed)  // Deref coercion happens here
}

Because Box<T> implements Deref, the Oxide compiler automatically converts &Box<T> to &T when needed. This makes boxed values feel natural to work with.

Recursive Types

One of the classic uses for Box<T> is building recursive data structures, like a linked list or tree. Without Box<T>, recursive types would have infinite size because the compiler wouldn't know how to calculate the size.

Consider a simple linked list:

public enum List {
    case Cons(Int, Box<List>)
    case Nil
}

fn main() {
    let list = List.Cons(1,
        Box { List.Cons(2,
            Box { List.Cons(3,
                Box { List.Nil }
            )}
        )}
    )
}

Why does this work? Because Box<T> has a known size (the size of a pointer), the compiler can now calculate the size of List:

Cons(Int, Box<List>) is an Int plus a Box pointer, both known sizes
Nil is a zero-sized variant

Without the Box, Cons(Int, List) would be infinitely sized because List contains itself.

A Better Example: Binary Tree

Here's a practical example—a simple binary search tree:

public struct TreeNode<T> {
    public value: T,
    public left: Box<TreeNode<T>>?,
    public right: Box<TreeNode<T>>?,
}

extension TreeNode {
    public static fn new(value: T): TreeNode<T> {
        TreeNode {
            value: value,
            left: null,
            right: null,
        }
    }

    public mutating fn insertLeft(value: T) {
        self.left = Box { TreeNode.new(value) }
    }

    public mutating fn insertRight(value: T) {
        self.right = Box { TreeNode.new(value) }
    }
}

fn main() {
    var root = TreeNode.new(5)
    root.insertLeft(3)
    root.insertRight(7)

    println!("Root: \(root.value)")
    println!("Left: \(root.left?.value)")
    println!("Right: \(root.right?.value)")
}

When NOT to Use `Box<T>`

For small stack-allocated values: Boxing adds indirection (pointer dereferencing) without benefit
When you don't need trait objects: Just use references or ownership directly
When you need multiple ownership: Use Rc<T> instead

`Box<T>` vs Rust's `Box<T>`

In Oxide, Box<T> works identically to Rust's Box<T>. The syntax is the same, and the semantics are identical. The main difference is in how you construct boxes:

// Oxide - uses `Box { value }` syntax
let boxed = Box { String.from("hello") }

#![allow(unused)]
fn main() {
// Rust - uses Box::new(value)
let boxed = Box::new(String::from("hello"));
}

Both are equivalent. Oxide's syntax is more consistent with the struct literal syntax.

Summary

Box<T> is Oxide's simplest smart pointer. Use it when you:

Need to allocate something on the heap
Want cheap moves of large values
Need to create trait objects for dynamic dispatch
Want to build recursive data structures

In the next section, we'll explore Rc<T>, which allows multiple ownership of the same value.

The Oxide Programming Language