A pointer can own a value, not just borrow it. A reference such as &T
borrows a value whose owner must keep it alive. A Box<T> owns its value on the
heap, so you can move the box or return it from a function without borrowing a
local variable. Dropping the box drops the value and releases its allocation. No
separate free or delete is needed.
Most values need no box. Two situations make the extra indirection useful.
A recursive type cannot contain another whole value of itself inline. The
compiler would need an infinite amount of space for it. A Box<Expr> gives an
expression-tree node a fixed-size pointer to an owned child instead.
A collection of different command types needs a common element type.
Box<dyn Command> owns any concrete value that implements Command and calls
its methods through dynamic dispatch. By contrast, &dyn Command only borrows a
command owned elsewhere. Returning newly created commands is a reason to choose
the owned form.
You'll start with a small dereferencing warmup, then construct and evaluate a
tree, and finally build and borrow a command pipeline. The exercises focus on
Box; other smart pointers get a short recognition guide at the end.
Box::new(value)
moves a value into a heap allocation and returns its owner, a Box<T>. When the
box is dropped, Rust drops the inner value and frees the allocation.
The * operator dereferences a box. For a Copy type such as i32, reading
this way copies the inner value. Most method calls work through automatic
dereferencing instead.
let boxed: Box<i32> = Box::new(7);
let n: i32 = *boxed;
assert_eq!(n + 1, 8);
Implement boxed_sum to take ownership of two boxed integers and return their
sum as an i32. The tests supply the boxes. The function does not need to
allocate any new ones.
You usually wouldn't box a tiny integer. This warmup lets you practice reading through a box before using one to own recursive data or a trait object.
*a reads the i32 inside the first box.i32 is Copy, so you can read the two integers through their boxes and add
them.
/// Sums two boxed integers, taking ownership of both boxes.
///
/// The boxes are dropped when the function returns, freeing their allocations.
fn boxed_sum(a: Box<i32>, b: Box<i32>) -> i32 {
*a + *b
}
#[test]
fn test_boxed_sum() {
assert_eq!(boxed_sum(Box::new(2), Box::new(3)), 5);
assert_eq!(boxed_sum(Box::new(-10), Box::new(40)), 30);
assert_eq!(boxed_sum(Box::new(0), Box::new(0)), 0);
}
This enum cannot compile:
// Each recursive field would contain another whole Expr inline.
enum Expr {
Num(i32),
Add(Expr, Expr),
Mul(Expr, Expr),
}
The compiler must know how many bytes one Expr occupies. Each Add would
contain two complete Expr values, which could themselves contain more Expr
values with no fixed limit. There is no finite layout for this type.
Box<Expr> fixes the layout by owning each child through a pointer. A
Box<Expr> is one pointer wide, regardless of how large the child's tree
becomes. The enum also needs space to distinguish its variants.
enum Expr {
Num(i32),
Add(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
}
Each parent owns its children, rather than borrowing nodes kept alive elsewhere. Dropping the root drops the owned tree.
The supplied Expr represents a literal number, a sum, or a product. For
example, an interpreter might represent (1 + 2) * 4 as a multiplication node
with an addition node on the left and a number on the right.
Implement both methods:
Expr::add(left: Self, right: Self) -> Self takes ownership of two
expressions and returns an Add node containing them in the same left/right
order. Preserve the child trees rather than replacing them with evaluated
numbers.Expr::eval(&self) -> i32 returns the numeric value of the tree. It borrows
the tree, so the same tree can be evaluated again without rebuilding it.
Evaluation needs no new boxes.The construction test checks the shape without calling eval. The evaluation
tests build their own trees, so you can work on either method independently.
These trees are small; recursive evaluation and dropping are not a strategy for
arbitrarily deep input.
Compare the argument types with the fields of Add. Which operation turns an
owned expression into the field type? You already own both children, so cloning
or evaluating them isn't needed.
What is the smallest tree you can evaluate without visiting another node? For an operation node, think about what information you need from its children.
Matching on borrowed self borrows the fields too. If a branch returns a
reference when you need an integer, check the binding's type. Method calls can
auto-deref through a borrowed box; you don't need to move its contents out.
/// An expression tree whose recursive children are owned through boxes. Each
/// box gives the enum a fixed-size field instead of an inline child tree.
#[derive(Debug, PartialEq)]
enum Expr {
Num(i32),
Add(Box<Self>, Box<Self>),
Mul(Box<Self>, Box<Self>),
}
impl Expr {
/// Own both child expressions in an Add node, preserving their order and
/// shape.
fn add(left: Self, right: Self) -> Self {
Self::Add(Box::new(left), Box::new(right))
}
/// Compute the tree's numeric value without consuming or changing it.
fn eval(&self) -> i32 {
match self {
Self::Num(value) => *value,
Self::Add(left, right) => left.eval() + right.eval(),
Self::Mul(left, right) => left.eval() * right.eval(),
}
}
}
#[test]
fn add_preserves_child_order_and_structure() {
let left = Expr::Mul(Box::new(Expr::Num(2)), Box::new(Expr::Num(3)));
let right = Expr::Add(Box::new(Expr::Num(4)), Box::new(Expr::Num(5)));
let tree = Expr::add(left, right);
// Check construction without relying on evaluation, which would hide
// swapped children.
let expected = Expr::Add(
Box::new(Expr::Mul(Box::new(Expr::Num(2)), Box::new(Expr::Num(3)))),
Box::new(Expr::Add(Box::new(Expr::Num(4)), Box::new(Expr::Num(5)))),
);
assert_eq!(tree, expected);
}
#[test]
fn leaf_evaluates_to_its_value() {
assert_eq!(Expr::Num(7).eval(), 7);
assert_eq!(Expr::Num(-3).eval(), -3);
}
#[test]
fn add_two_leaves() {
let tree = Expr::Add(Box::new(Expr::Num(2)), Box::new(Expr::Num(3)));
assert_eq!(tree.eval(), 5);
}
#[test]
fn mul_two_leaves() {
let tree = Expr::Mul(Box::new(Expr::Num(4)), Box::new(Expr::Num(5)));
assert_eq!(tree.eval(), 20);
}
#[test]
fn nested_mixed_ops() {
// Evaluate (1 + 2) * 4, with the nested operation on the left.
let tree = Expr::Mul(
Box::new(Expr::Add(Box::new(Expr::Num(1)), Box::new(Expr::Num(2)))),
Box::new(Expr::Num(4)),
);
assert_eq!(tree.eval(), 12);
}
#[test]
fn asymmetric_tree_can_be_evaluated_again() {
// Evaluate 2 + (3 * (4 + 5)), with the deeper branch on the right.
let tree = Expr::Add(
Box::new(Expr::Num(2)),
Box::new(Expr::Mul(
Box::new(Expr::Num(3)),
Box::new(Expr::Add(Box::new(Expr::Num(4)), Box::new(Expr::Num(5)))),
)),
);
assert_eq!(tree.eval(), 29);
assert_eq!(tree.eval(), 29);
}
A factory cannot return references to commands it creates locally; those
commands would be dropped when the factory returns. Box<dyn Command> lets it
return ownership instead. Each box owns a concrete command, while the caller
uses the shared Command interface.
The supplied trait has one method:
trait Command {
fn run(&self, input: &str) -> String;
}
Three implementations are provided:
Uppercase uppercases the input.Reverse reverses Unicode scalar values, which can separate combining marks
from their letters.Append { suffix: String } appends its owned suffix.A Vec<C> with C: Command has just one concrete element type. A
Vec<Box<dyn Command>> can own different command types in the same collection.
Each element has the same size, holding a data pointer and a vtable pointer for
dispatching method calls to the concrete implementation. The unsized
dyn Command lives behind the pointer, not directly in the vector. Dropping the
vector drops its boxes and their commands, including any owned strings.
Implement both functions:
make_pipeline(suffix: String) -> Vec<Box<dyn Command>> returns exactly two
commands, first Uppercase, then Append with the supplied suffix. The
returned pipeline owns its commands and suffix, so it remains usable after the
factory returns.apply_pipeline(commands: &[Box<dyn Command>], input: &str) -> String passes
the input through every command in slice order and returns the final output.
An empty pipeline returns the input unchanged. It must work with any
implementation of Command, not just the three supplied types.For a suffix of "x", the factory's pipeline transforms "hi" into "HIx",
not "HIX". The factory tests call the returned commands directly,
independently of apply_pipeline. The runner tests supply their own pipelines.
Box<dyn Command> owns a command; &dyn Command borrows one whose owner lives
elsewhere. Here apply_pipeline borrows a slice of owned boxes rather than
taking the vector away from its caller. Command::run also borrows its command
through &self. The caller can therefore run the same pipeline again with
another input.
A box can take ownership of a command created inside the factory. Which command needs to own the supplied string?
If Rust infers a vector containing only one concrete command type, try an
explicit Vec<Box<dyn Command>> annotation. That gives the different boxes a
common destination type.
Check the types at each stage: run borrows its input and returns an owned
string. Which string should the next command receive? A loop is fine; consider
the empty pipeline when choosing your starting value.
Call through the Command interface rather than checking concrete types. Method
calls work through the borrowed boxes, so the caller can keep its pipeline.
/// A text transformation that borrows its command and returns an owned string.
trait Command {
fn run(&self, input: &str) -> String;
}
/// Uppercase the input.
struct Uppercase;
impl Command for Uppercase {
fn run(&self, input: &str) -> String {
input.to_uppercase()
}
}
/// Reverse the input by Unicode scalar value.
struct Reverse;
impl Command for Reverse {
fn run(&self, input: &str) -> String {
input.chars().rev().collect()
}
}
/// Append an owned suffix.
struct Append {
suffix: String,
}
impl Command for Append {
fn run(&self, input: &str) -> String {
format!("{input}{}", self.suffix)
}
}
/// Return exactly two owned commands: Uppercase, then Append with the supplied
/// suffix.
fn make_pipeline(suffix: String) -> Vec<Box<dyn Command>> {
vec![Box::new(Uppercase), Box::new(Append { suffix })]
}
/// Pass input through every command in slice order and return the final output.
/// An empty pipeline returns the input unchanged. Borrow the pipeline so it can
/// be reused, and support any Command implementation.
fn apply_pipeline(commands: &[Box<dyn Command>], input: &str) -> String {
let mut current = input.to_string();
for command in commands {
current = command.run(¤t);
}
current
}
#[test]
fn factory_returns_uppercase_then_append() {
let pipeline = make_pipeline(String::from("x"));
assert_eq!(pipeline.len(), 2);
// Inspect each stage independently of apply_pipeline.
assert_eq!(pipeline[0].run("hi"), "HI");
assert_eq!(pipeline[1].run("hi"), "hix");
assert_eq!(pipeline[1].run(&pipeline[0].run("hi")), "HIx");
}
#[test]
fn factory_owns_the_supplied_suffix() {
let pipeline = {
let suffix = String::from(" fin");
make_pipeline(suffix)
};
assert_eq!(pipeline.len(), 2);
assert_eq!(pipeline[1].run("one"), "one fin");
assert_eq!(pipeline[1].run("two"), "two fin");
let empty_suffix = make_pipeline(String::new());
assert_eq!(empty_suffix.len(), 2);
assert_eq!(empty_suffix[1].run("hi"), "hi");
}
#[test]
fn empty_pipeline_returns_input_unchanged() {
let pipeline: Vec<Box<dyn Command>> = Vec::new();
assert_eq!(apply_pipeline(&pipeline, "hello"), "hello");
assert_eq!(apply_pipeline(&pipeline, ""), "");
}
#[test]
fn single_command_uppercase() {
let pipeline: Vec<Box<dyn Command>> = vec![Box::new(Uppercase)];
assert_eq!(apply_pipeline(&pipeline, "hello"), "HELLO");
}
#[test]
fn single_command_reverse_unicode() {
let pipeline: Vec<Box<dyn Command>> = vec![Box::new(Reverse)];
assert_eq!(apply_pipeline(&pipeline, "aé🦀"), "🦀éa");
}
// This command exists only in tests, outside the supplied command set.
#[cfg(test)]
struct Bracket;
#[cfg(test)]
impl Command for Bracket {
fn run(&self, input: &str) -> String {
format!("[{input}]")
}
}
#[test]
fn order_matters() {
let bracket_then_reverse: Vec<Box<dyn Command>> = vec![Box::new(Bracket), Box::new(Reverse)];
let reverse_then_bracket: Vec<Box<dyn Command>> = vec![Box::new(Reverse), Box::new(Bracket)];
assert_eq!(apply_pipeline(&bracket_then_reverse, "hi"), "]ih[");
assert_eq!(apply_pipeline(&reverse_then_bracket, "hi"), "[ih]");
}
#[test]
fn mixed_pipeline_with_custom_command() {
let pipeline: Vec<Box<dyn Command>> =
vec![Box::new(Bracket), Box::new(Uppercase), Box::new(Reverse)];
assert_eq!(apply_pipeline(&pipeline, "hi"), "]IH[");
}
#[test]
fn borrowed_pipeline_supports_custom_commands_and_reuse() {
let pipeline: Vec<Box<dyn Command>> = vec![Box::new(Bracket)];
assert_eq!(apply_pipeline(&pipeline, "hi"), "[hi]");
assert_eq!(apply_pipeline(&pipeline, "bye"), "[bye]");
assert_eq!(apply_pipeline(&pipeline, "hi"), "[hi]");
}
Boxing an integer was practice. The tree and pipeline gave you reasons to own values through pointers.
What We Learned
Box<T>owns a heap value and drops it when the box is dropped.Box::newconstructs a box,*dereferences it, and method calls usually auto-deref.- Recursive types need indirection for a finite layout.
Expr::addmoves child expressions into boxes;evalborrows the resulting tree without consuming it.Box<dyn Command>lets a factory return ownership of different concrete command types behind one interface. A borrowed&dyn Commandinstead depends on an owner elsewhere.- Owning commands does not mean consuming them on every run.
apply_pipelineborrows the slice and dispatches through the trait, leaving the pipeline available for reuse.
These types are for recognition only here, not additional exercise requirements.
Rc<T> provides shared ownership on one thread through reference counting.
Cloning an Rc adds an owner without cloning the inner value; the value is
dropped when the last strong owner is gone. Strong Rc cycles keep their
values alive, so use non-owning Weak<T> links where a relationship should
not keep a value alive. Upgrading a Weak returns an Option because the
value may already have been dropped.Arc<T> uses atomic reference counting for shared ownership across threads.
It does not make an unsafe-to-share inner value thread-safe or provide
mutation by itself.RefCell<T> allows mutation through a shared reference by checking borrowing
rules at runtime. Conflicting calls to borrow or borrow_mut panic; the
try_borrow variants return errors instead. It can pair with Rc for shared
mutable data on one thread, but it does not prevent reference cycles.Extra practice to explore at your own pace. These chapters do not count toward course progress.