Step 1 of 7

Box: a value on the heap

A smart pointer is a value that points at data stored somewhere else (like a reference does) but also has extra powers, such as owning that data and cleaning it up. You've used two already without the name: String and Vec<T> each own a buffer on the heap. This module covers the smart pointers you reach for on purpose: Box<T>, Rc<T>, RefCell<T>, Cell<T> and Weak<T>.

Box

Box::new(value) moves the value onto the heap. The Box itself is just a pointer (8 bytes on a 64-bit machine) that can live on the stack, in a struct, anywhere. The Box owns the value: when the Box goes out of scope, the value is dropped and the heap memory is freed. No manual free, no garbage collector.

fn main() {
    let score = Box::new(41);
    let next = *score + 1; // * follows the pointer to the value inside
    println!("score = {score}, next = {next}");

    let names = Box::new(vec!["Ferris", "Corro"]);
    println!("{} names, first is {}", names.len(), names[0]);
}

score = 41, next = 42
2 names, first is Ferris

*score dereferences the Box: it gives you the i32 it points to.
Printing a Box prints the value inside, and methods like .len() and indexing work straight through the Box. You'll see how in step 3.

When do you need a Box? Mostly in three situations:

A type that contains itself (a recursive type), like a list or a tree. This step and the next.
A trait object, Box<dyn Trait>, which you met in the trait objects module.
A very large value you want to move around cheaply (moving a Box copies only the pointer). This one is rare.

Recursive types need a pointer

Here's a linked list: each node holds a number and the rest of the list.

enum List {
    Cons(i32, List),
    Nil,
}

fn main() {
    let _empty = List::Nil;
}

error[E0072]: recursive type `List` has infinite size

Rust stores an enum value in one block of memory big enough for its largest variant. Cons contains a whole List, which could be a Cons containing a whole List, and so on: the size would be infinite. The compiler's help line says it all: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle. A Box<List> is a pointer, and a pointer has the same size whatever it points to:

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

fn sum(list: &List) -> i32 {
    match list {
        Cons(value, rest) => value + sum(rest),
        Nil => 0,
    }
}

fn main() {
    // 3 -> 5 -> 8 -> end
    let list = Cons(3, Box::new(Cons(5, Box::new(Cons(8, Box::new(Nil))))));
    println!("sum = {}", sum(&list));
}

sum = 16

Piece by piece:

use List::{Cons, Nil}; lets you write Cons instead of List::Cons.
Each Box::new(...) puts the next node on the heap. Nil (the empty list) ends the chain.
In sum, matching on &List gives value: &i32 and rest: &Box<List>. Passing rest to sum, which wants a &List, just works: Rust turns &Box<List> into &List for you. This is called deref coercion, and step 3 explains it.
When list goes out of scope, the first node is dropped, which drops its Box, which drops the next node, and so on down the chain.

Common mistakes

Forgetting Box::new when building: Cons(5, Nil) is error[E0308]: mismatched types, expected Box<List>, found List. Wrap the inner list: Cons(5, Box::new(Nil)).
Boxing everything. Most values belong on the stack or inside a Vec. Box is for the cases above. A real program would store these numbers in a Vec<i32>, which is faster than a linked list; the list is here because it shows recursion so clearly.

Your task

Fill the blanks. The Item variant needs a boxed rest-of-the-shelf, and building the shelf needs to box the inner value. The program prints total stock: 12.

Challenge 2

The list type and a helper that builds a list from a slice are written for you. Write two recursive functions:

len(list: &List) -> usize: how many numbers are in the list.
largest(list: &List) -> Option<i32>: the biggest number, or None for an empty list.

Challenge 3

A delivery route is a chain of stops. Using the Route enum below, write:

build(stops: &[&str]) -> Route: the route visiting the stops in order (an empty slice gives Route::End).
describe(route: &Route) -> String: the stops joined with ->, for example Docks -> Market -> Arena. An empty route describes as (no stops).

Use recursion for both (no Vec inside the route).

Next: Trees with Box