Ownership and the pointer types

In chapter 7 every value had exactly one owner. That is the normal case in Rust, and most code needs nothing more. But some structures cannot be described with one owner per value. A tree node wants to point back to its parent. A counter must be updated by several threads. An expression contains smaller expressions of its own type.

For each of these, the standard library has a pointer type. A pointer type holds the address of a value and adds a rule about who owns it. This chapter covers the main ones, one at a time. For each, I show where its data sits in memory and which problem it solves. The next four chapters, on linked lists, trees, and graphs, use every one of them.

I start by reviewing ownership itself, because each pointer type is a change to its rules.

8.1 Ownership and moves

Every value in Rust has one owner, the variable or structure that holds it. When the owner goes away, at the end of its scope, the value is dropped and its memory is freed.

Assigning a value to another variable moves it: ownership passes to the new variable, and the old one can no longer be used. Figure 8.1 shows a move of a String.

A move copies only the header on the stack, the pointer, length, and capacity. The text on the heap stays where it is. If both a and b were usable, both would try to free the same text when they went out of scope. The compiler prevents that by making a unusable after the move.

Instead of moving a value, you can borrow it with a reference. A shared reference &T lets you read. A mutable reference &mut T lets you change. The borrow rules say you may have either any number of &T or exactly one &mut T, but not both at once. And no reference may outlive its value.

These rules cover most programs. The pointer types in this chapter handle the cases they cannot.

The module for this chapter starts with a table that summarizes them:

Listing 8.1 The module comment and imports (lines 1 to 27). src/problems/smart_pointers.rs

//! Smart pointers and interior mutability.
//!
//! Each pointer type answers a different ownership question, and picking the
//! wrong one shows up as either a compile error or a runtime bug.
//!
//! | Type | Ownership | Mutation | Across threads |
//! |---|---|---|---|
//! | `Box<T>` | single | through `&mut` | if `T: Send` |
//! | `Rc<T>` | shared, non-atomic count | no | no |
//! | `Arc<T>` | shared, atomic count | no | if `T: Send + Sync` |
//! | `RefCell<T>` | single | runtime checked | no |
//! | `Mutex<T>` | single | blocking lock | yes |
//! | `Weak<T>` | non-owning | no | as `Arc` |
//! | `Cow<'a, T>` | borrow or own | no | as the borrow |
//!
//! Two rules cover most decisions. `Rc`/`RefCell` is for graphs and caches inside
//! one thread; `Arc`/`Mutex` is for state shared between threads. `Weak` exists to
//! break reference cycles, because two strong references in a cycle never reach a
//! count of zero and the memory is never freed.

use std::{
    borrow::Cow,
    cell::RefCell,
    rc::{Rc, Weak},
    sync::{Arc, Mutex},
    thread,
};

Do not try to memorize the table yet. Each section below covers one row.

8.2 Box: one owner, on the heap

A Box<T> puts a value of type T on the heap and owns it. The Box itself is one pointer, 8 bytes on a 64-bit machine. When the Box is dropped, it drops the value and frees the heap memory. So a Box behaves like an owned value that happens to live on the heap.

You need a Box most often for a type that contains itself. Consider an arithmetic expression: it is either a number, or the sum of two smaller expressions. Written directly, that type would have no size (figure 8.2).

To lay out a type, the compiler must know its size. An Add(Expr, Expr) contains two Expr values, each of which may be another Add. The size has no end, so the compiler rejects the type. Box<Expr> is always 8 bytes, whatever it points to, so Add(Box<Expr>, Box<Expr>) has a fixed size.

Listing 8.2 An expression tree (lines 29 to 43).

/// A recursive type needs indirection, because `Expr` cannot contain itself by
/// value. `Box` provides the fixed-size indirection.
#[derive(Debug, PartialEq, Eq)]
pub enum Expr {
    Lit(i64),
    Add(Box<Expr>, Box<Expr>),
}

/// Evaluate an expression tree.
pub fn eval(expr: &Expr) -> i64 {
    match expr {
        Expr::Lit(value) => *value,
        Expr::Add(left, right) => eval(left) + eval(right),
    }
}

eval computes the value of an expression. For a number, the value is the number. For a sum, it evaluates both sides and adds them. The call eval(left) passes a &Box<Expr> where the function expects &Expr. Rust converts it automatically, following the box to the value inside. This automatic conversion is called deref coercion.

To build 1 + 2, you write Expr::Add(Box::new(Expr::Lit(1)), Box::new(Expr::Lit(2))). Box::new allocates on the heap and moves the value there.

8.3 Rc: several owners, counted

Sometimes one value really has several owners, and none of them can be picked as the one that frees it. A node in a graph with several incoming edges is an example. For this, Rust has Rc<T>, short for reference counted.

Rc::new(value) puts the value on the heap together with a count of how many Rc handles point to it. Rc::clone(&rc) does not copy the value. It adds 1 to the count and returns another handle to the same value. Dropping a handle subtracts 1. When the count reaches zero, the value is dropped. Figure 8.3 shows two handles.

An Rc hands out only shared references to its value. With several owners, a &mut through one of them would break the rule that a &mut is the only reference. So by itself, a value inside an Rc cannot be changed. The next section adds that ability.

8.4 RefCell: changing a shared value, checked at run time

RefCell<T> holds a value and allows it to be changed through a shared reference. It keeps the borrow rules, but checks them while the program runs instead of at compile time. Figure 8.4 shows what it tracks.

• cell.borrow() returns a guard that acts like &T. Many can exist at once.
• cell.borrow_mut() returns a guard that acts like &mut T. It panics if any other borrow is active.
• When a guard is dropped, its borrow ends.

Rc and RefCell are used together: Rc<RefCell<T>> gives several owners who can each change the value.

Listing 8.3 Two handles to one counter (lines 45 to 55).

/// Shared mutation inside one thread, with `Rc` for aliasing and `RefCell` for
/// the runtime borrow check.
pub fn shared_counter_with_rc_refcell() -> i32 {
    let counter = Rc::new(RefCell::new(0));
    let alias = Rc::clone(&counter);

    *alias.borrow_mut() += 1;
    *counter.borrow_mut() += 10;

    *counter.borrow()
}

Step through it:

1. Rc::new(RefCell::new(0)) creates a counter holding 0, with a strong count of 1.
2. Rc::clone(&counter) makes a second handle, alias. The strong count is now 2. There is still one counter.
3. *alias.borrow_mut() += 1; borrows mutably through alias and adds 1. The guard is dropped at the end of the statement, so the borrow ends there.
4. *counter.borrow_mut() += 10; does the same through the other handle.
5. *counter.borrow() reads 11.

Animation 8.1 runs these steps, with the strong count and the RefCell flag drawn on the heap block.

Each borrow_mut ends before the next starts, so no panic occurs. If you stored the first guard in a variable and then called borrow_mut again while it was still alive, the program would panic.

8.5 Weak: a pointer that does not own

Counting has a weakness. If two values hold Rc handles to each other, each keeps the other’s count above zero. When you drop your own handles, both counts stay at 1, and neither value is ever freed. This is a reference cycle, and it leaks memory (figure 8.5, left).

The fix is a pointer that does not count as an owner. Weak<T> is made from an Rc with Rc::downgrade. It increases only the weak count, which does not keep the value alive. To use the value, you call upgrade(), which returns Some(Rc) if the value still exists and None if it has been dropped.

The usual pattern is that parents own children with Rc, and children point back to their parents with Weak.

Listing 8.4 A tree node with a weak parent pointer (lines 57 to 87).

/// A node whose parent link is weak, so a child does not keep its parent alive.
pub struct TreeNode {
    pub value: i32,
    parent: RefCell<Weak<TreeNode>>,
}

impl TreeNode {
    /// A node with no parent.
    pub fn root(value: i32) -> Rc<Self> {
        Rc::new(Self {
            value,
            parent: RefCell::new(Weak::new()),
        })
    }

    /// A node that points back weakly at `parent`.
    pub fn child_of(parent: &Rc<Self>, value: i32) -> Rc<Self> {
        Rc::new(Self {
            value,
            parent: RefCell::new(Rc::downgrade(parent)),
        })
    }

    /// The parent's value, or `None` once the parent has been dropped.
    pub fn parent_value(&self) -> Option<i32> {
        self.parent
            .borrow()
            .upgrade()
            .map(|parent| parent.value)
    }
}

• parent: RefCell<Weak<TreeNode>> stores the link to the parent. The RefCell allows the link to be changed after the node exists.
• root creates a node with Weak::new(), an empty weak pointer whose upgrade always returns None.
• child_of creates a node whose parent link is Rc::downgrade(parent).
• parent_value borrows the link, calls upgrade(), and reads the parent’s value if the parent still exists. Option::map applies the closure only when there is a value.

The test weak_parent_link_does_not_keep_the_parent_alive in listing 8.7 checks the behavior.

Animation 8.2 follows that test, then shows the cycle that Weak prevents.

The test creates a root and a child, drops the root, and then checks that the child’s parent_value() is None.

8.6 Arc and Mutex: sharing across threads

Arc<T> is Rc<T> with an atomic count. An atomic operation is one the processor completes as a single step. That stays true even when several cores run it on the same memory at the same moment. So Arc handles can be sent to other threads. Chapter 16 explains atomic operations in detail.

Mutex<T> is the thread-safe counterpart of RefCell. lock() returns a guard that gives access to the value. If another thread holds the lock, lock() waits until it is released, instead of panicking.

Listing 8.5 Several threads adding to one total (lines 89 to 110).

/// Shared mutation across threads, with `Arc` for ownership and `Mutex` for
/// exclusive access.
pub fn total_with_arc_mutex(threads: usize, per_thread: usize) -> usize {
    let total = Arc::new(Mutex::new(0usize));
    let mut handles = Vec::with_capacity(threads);

    for _ in 0..threads {
        let total = Arc::clone(&total);
        handles.push(thread::spawn(move || {
            for _ in 0..per_thread {
                let mut guard = total.lock().expect("mutex poisoned");
                *guard += 1;
            }
        }));
    }

    for handle in handles {
        handle.join().expect("worker panicked");
    }

    *total.lock().expect("mutex poisoned")
}

Step through it:

1. Arc::new(Mutex::new(0usize)) creates the shared total.
2. For each thread, Arc::clone(&total) makes a new handle, and thread::spawn(move || ...) moves that handle into the new thread. move means the closure takes ownership of what it uses.
3. Each thread locks the mutex, adds 1, and drops the guard, per_thread times.
4. handle.join() waits for each thread to finish.
5. The last line locks once more and reads the result.

lock() returns a Result, because a thread that panics while holding the lock leaves the mutex marked as poisoned. .expect("mutex poisoned") stops the program with that message in that case. Chapter 16 covers poisoning.

This function locks once for every single increment, so the threads spend most of their time waiting for each other. It is correct but slow. Chapter 16 measures faster ways to count across threads.

8.7 Cow: borrow when you can

Cow<'a, str> holds either a borrowed &'a str or an owned String. Its name stands for “clone on write”. It fits functions that usually return their input unchanged but sometimes need to change it.

Listing 8.6 Uppercase only when needed (lines 112 to 126).

/// Borrow when no change is needed, allocate only when there is one.
///
/// `Cow` is the idiomatic return type for a function that usually passes its
/// input through unchanged.
pub fn normalize(input: &str, uppercase: bool) -> Cow<'_, str> {
    if uppercase
        && input
            .bytes()
            .any(|byte| byte.is_ascii_lowercase())
    {
        Cow::Owned(input.to_uppercase())
    } else {
        Cow::Borrowed(input)
    }
}

normalize checks whether any byte is a lowercase letter. If there is nothing to change, it returns Cow::Borrowed(input), which costs nothing. Only when a change is needed does it allocate a new uppercase String and return Cow::Owned. The caller can use either variant as a &str.

8.8 The complete file

Listing 8.7 The complete file, with its tests. src/problems/smart_pointers.rs

//! Smart pointers and interior mutability.
//!
//! Each pointer type answers a different ownership question, and picking the
//! wrong one shows up as either a compile error or a runtime bug.
//!
//! | Type | Ownership | Mutation | Across threads |
//! |---|---|---|---|
//! | `Box<T>` | single | through `&mut` | if `T: Send` |
//! | `Rc<T>` | shared, non-atomic count | no | no |
//! | `Arc<T>` | shared, atomic count | no | if `T: Send + Sync` |
//! | `RefCell<T>` | single | runtime checked | no |
//! | `Mutex<T>` | single | blocking lock | yes |
//! | `Weak<T>` | non-owning | no | as `Arc` |
//! | `Cow<'a, T>` | borrow or own | no | as the borrow |
//!
//! Two rules cover most decisions. `Rc`/`RefCell` is for graphs and caches inside
//! one thread; `Arc`/`Mutex` is for state shared between threads. `Weak` exists to
//! break reference cycles, because two strong references in a cycle never reach a
//! count of zero and the memory is never freed.

use std::{
    borrow::Cow,
    cell::RefCell,
    rc::{Rc, Weak},
    sync::{Arc, Mutex},
    thread,
};

/// A recursive type needs indirection, because `Expr` cannot contain itself by
/// value. `Box` provides the fixed-size indirection.
#[derive(Debug, PartialEq, Eq)]
pub enum Expr {
    Lit(i64),
    Add(Box<Expr>, Box<Expr>),
}

/// Evaluate an expression tree.
pub fn eval(expr: &Expr) -> i64 {
    match expr {
        Expr::Lit(value) => *value,
        Expr::Add(left, right) => eval(left) + eval(right),
    }
}

/// Shared mutation inside one thread, with `Rc` for aliasing and `RefCell` for
/// the runtime borrow check.
pub fn shared_counter_with_rc_refcell() -> i32 {
    let counter = Rc::new(RefCell::new(0));
    let alias = Rc::clone(&counter);

    *alias.borrow_mut() += 1;
    *counter.borrow_mut() += 10;

    *counter.borrow()
}

/// A node whose parent link is weak, so a child does not keep its parent alive.
pub struct TreeNode {
    pub value: i32,
    parent: RefCell<Weak<TreeNode>>,
}

impl TreeNode {
    /// A node with no parent.
    pub fn root(value: i32) -> Rc<Self> {
        Rc::new(Self {
            value,
            parent: RefCell::new(Weak::new()),
        })
    }

    /// A node that points back weakly at `parent`.
    pub fn child_of(parent: &Rc<Self>, value: i32) -> Rc<Self> {
        Rc::new(Self {
            value,
            parent: RefCell::new(Rc::downgrade(parent)),
        })
    }

    /// The parent's value, or `None` once the parent has been dropped.
    pub fn parent_value(&self) -> Option<i32> {
        self.parent
            .borrow()
            .upgrade()
            .map(|parent| parent.value)
    }
}

/// Shared mutation across threads, with `Arc` for ownership and `Mutex` for
/// exclusive access.
pub fn total_with_arc_mutex(threads: usize, per_thread: usize) -> usize {
    let total = Arc::new(Mutex::new(0usize));
    let mut handles = Vec::with_capacity(threads);

    for _ in 0..threads {
        let total = Arc::clone(&total);
        handles.push(thread::spawn(move || {
            for _ in 0..per_thread {
                let mut guard = total.lock().expect("mutex poisoned");
                *guard += 1;
            }
        }));
    }

    for handle in handles {
        handle.join().expect("worker panicked");
    }

    *total.lock().expect("mutex poisoned")
}

/// Borrow when no change is needed, allocate only when there is one.
///
/// `Cow` is the idiomatic return type for a function that usually passes its
/// input through unchanged.
pub fn normalize(input: &str, uppercase: bool) -> Cow<'_, str> {
    if uppercase
        && input
            .bytes()
            .any(|byte| byte.is_ascii_lowercase())
    {
        Cow::Owned(input.to_uppercase())
    } else {
        Cow::Borrowed(input)
    }
}

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

    #[test]
    fn boxed_expression_evaluates() {
        let expr = Expr::Add(Box::new(Expr::Lit(1)), Box::new(Expr::Lit(2)));
        assert_eq!(eval(&expr), 3);
    }

    #[test]
    fn rc_refcell_shares_mutation_within_a_thread() {
        assert_eq!(shared_counter_with_rc_refcell(), 11);
    }

    #[test]
    fn weak_parent_link_does_not_keep_the_parent_alive() {
        let root = TreeNode::root(1);
        let child = TreeNode::child_of(&root, 2);

        assert_eq!(child.parent_value(), Some(1));
        drop(root);
        assert_eq!(child.parent_value(), None);
    }

    #[test]
    fn arc_mutex_sums_concurrent_updates() {
        assert_eq!(total_with_arc_mutex(8, 250), 2_000);
    }

    #[test]
    fn cow_borrows_and_owns_as_needed() {
        assert!(matches!(normalize("A100", true), Cow::Borrowed(_)));
        assert!(matches!(normalize("a100", true), Cow::Owned(_)));
        assert_eq!(normalize("a100", true), "A100");
        assert_eq!(normalize("a100", false), "a100");
    }
}

The tests check one behavior per pointer type. cow_borrows_and_owns_as_needed uses matches! to check which variant came back, not only the text. That is how a test shows that the unchanged case did not allocate. Run them with cargo test --lib smart_pointers.

Figure 8.6 turns the chapter into three questions you can ask when choosing a pointer type.

Chapter 9 puts these types to work. You will build linked lists with Box and see how dropping a very long one can crash. Then you will build a doubly linked list with Rc, RefCell, and Weak.

Exercises

1. Build the expression (1 + 2) + 3 with Expr and check that eval returns 6.
2. In shared_counter_with_rc_refcell, keep the first borrow_mut guard in a variable and call borrow_mut again. Run it and read the panic message.
3. Build a parent with two children that point back with Weak. Print Rc::strong_count and Rc::weak_count for the parent before and after creating the children.
4. Change total_with_arc_mutex so each thread counts in a local variable and adds its total to the mutex once. Compare the running time for 8 threads and one million increments each.