Item 8: Familiarize yourself with reference and pointer types

For programming in general, a reference is a way to indirectly access some data structure, separately from whatever variable owns that data structure. In practice, this is usually implemented as a pointer: a number whose value is the address in memory of the data structure.

A modern CPU will typically police a few constraints on pointers—the memory address should be in a valid range of memory (whether virtual or physical) and may need to be aligned (e.g., a 4-byte integer value might be accessible only if its address is a multiple of 4).

However, higher-level programming languages usually encode more information about pointers in their type systems. In C-derived languages, including Rust, pointers have a type that indicates what kind of data structure is expected to be present at the pointed-to memory address. This allows the code to interpret the contents of memory at that address and in the memory following that address.

This basic level of pointer information—putative memory location and expected data structure layout—is represented in Rust as a raw pointer. However, safe Rust code does not use raw pointers, because Rust provides richer reference and pointer types that provide additional safety guarantees and constraints. These reference and pointer types are the subject of this Item; raw pointers are relegated to Item 16 (which discusses unsafe code).

Rust References

The most ubiquitous pointer-like type in Rust is the reference, with a type that is written as &T for some type T. Although this is a pointer value under the covers, the compiler ensures that various rules around its use are observed: it must always point to a valid, correctly aligned instance of the relevant type T, whose lifetime (Item 14) extends beyond its use, and it must satisfy the borrow checking rules (Item 15). These additional constraints are always implied by the term reference in Rust, and so the bare term pointer is generally rare.

The constraint that a Rust reference must point to a valid, correctly aligned item is shared by C++'s reference types. However, C++ has no concept of lifetimes and so allows footguns with dangling references:1

// C++
const int& dangle() {
  int x = 32; // on the stack, overwritten later
  return x; // return reference to stack variable!
}

Rust's borrowing and lifetime checks mean that the equivalent code doesn't even compile:

fn dangle() -> &'static i64 {
    let x: i64 = 32; // on the stack
    &x
}
error[E0515]: cannot return reference to local variable `x`
   --> src/main.rs:477:5
    |
477 |     &x
    |     ^^ returns a reference to data owned by the current function

A Rust reference &T allows read-only access to the underlying item (roughly equivalent to C++'s const T&). A mutable reference that also allows the underlying item to be modified is written as &mut T and is also subject to the borrow checking rules discussed in Item 15. This naming pattern reflects a slightly different mindset between Rust and C++:

  • In Rust, the default variant is read-only, and writable types are marked specially (with mut).
  • In C++, the default variant is writable, and read-only types are marked specially (with const).

The compiler converts Rust code that uses references into machine code that uses simple pointers, which are eight bytes in size on a 64-bit platform (which this Item assumes throughout). For example, a pair of local variables together with references to them:

#![allow(unused)]
fn main() {
pub struct Point {
    pub x: u32,
    pub y: u32,
}

let pt = Point { x: 1, y: 2 };
let x = 0u64;
let ref_x = &x;
let ref_pt = &pt;
}

might end up laid out on the stack as shown in Figure 1-2.

Representation of a stack with 4 entries, each shown as a rectangle representing 8 bytes. Starting from the bottom, the first entry is labelled pt, and the 8 bytes it represents is split into two 4-byte values, 1 and 2. Above that, the next entry is labelled x and holds the value 0. Above that is an entry labelled ref_x, whose contents are just an arrow that points to the x entry below it on the stack. At the top is a ref_pt entry, whose contents are an arrow that points to the pt entry at the bottom of the stack.

Figure 1-2. Stack layout with pointers to local variables

A Rust reference can refer to items that are located either on the stack or on the heap. Rust allocates items on the stack by default, but the Box<T> pointer type (roughly equivalent to C++'s std::unique_ptr<T>) forces allocation to occur on the heap, which in turn means that the allocated item can outlive the scope of the current block. Under the covers, Box<T> is also a simple eight-byte pointer value:

let box_pt = Box::new(Point { x: 10, y: 20 });

This is depicted in Figure 1-3.

The figure shows a representation of the stack on the left, with a single entry labelled box_pt. The contents of this entry is the start of an arrow that points to a rectangle on the right hand side, inside a cloud labelled 'Heap'. The rectangle on the right hand side is split into two 4-byte components, holding the values 10 and 20.

Figure 1-3. Stack Box pointer to struct on heap

Pointer Traits

A method that expects a reference argument like &Point can also be fed a &Box<Point>:

fn show(pt: &Point) {
    println!("({}, {})", pt.x, pt.y);
}
show(ref_pt);
show(&box_pt);
(1, 2)
(10, 20)

This is possible because Box<T> implements the Deref trait, with Target = T. An implementation of this trait for some type means that the trait's deref() method can be used to create a reference to the Target type. There's also an equivalent DerefMut trait, which emits a mutable reference to the Target type.

The Deref/DerefMut traits are somewhat special, because the Rust compiler has specific behavior when dealing with types that implement them. When the compiler encounters a dereferencing expression (e.g., *x), it looks for and uses an implementation of one of these traits, depending on whether the dereference requires mutable access or not. This Deref coercion allows various smart pointer types to behave like normal references and is one of the few mechanisms that allow implicit type conversion in Rust (as described in Item 5).

As a technical aside, it's worth understanding why the Deref traits can't be generic (Deref<Target>) for the destination type. If they were, then it would be possible for some type ConfusedPtr to implement both Deref<TypeA> and Deref<TypeB>, and that would leave the compiler unable to deduce a single unique type for an expression like *x. So instead, the destination type is encoded as the associated type named Target.

This technical aside provides a contrast to two other standard pointer traits, the AsRef and AsMut traits. These traits don't induce special behavior in the compiler but allow conversions to a reference or mutable reference via an explicit call to their trait functions (as_ref() and as_mut(), respectively). The destination type for these conversions is encoded as a type parameter (e.g., AsRef<Point>), which means that a single container type can support multiple destinations.

For example, the standard String type implements the Deref trait with Target = str, meaning that an expression like &my_string can be coerced to type &str. But it also implements the following:

  • AsRef<[u8]>, allowing conversion to a byte slice &[u8]
  • AsRef<OsStr>, allowing conversion to an OS string
  • AsRef<Path>, allowing conversion to a filesystem path
  • AsRef<str>, allowing conversion to a string slice &str (as with Deref)

Fat Pointer Types

Rust has two built-in fat pointer types: slices and trait objects. These are types that act as pointers but hold additional information about the thing they are pointing to.

Slices

The first fat pointer type is the slice: a reference to a subset of some contiguous collection of values. It's built from a (non-owning) simple pointer, together with a length field, making it twice the size of a simple pointer (16 bytes on a 64-bit platform). The type of a slice is written as &[T]—a reference to [T], which is the notional type for a contiguous collection of values of type T.

The notional type [T] can't be instantiated, but there are two common containers that embody it. The first is the array: a contiguous collection of values having a size that is known at compile time—an array with five values will always have five values. A slice can therefore refer to a subset of an array (as depicted in Figure 1-4):

#![allow(unused)]
fn main() {
let array: [u64; 5] = [0, 1, 2, 3, 4];
let slice = &array[1..3];
}
Representation of a stack holding seven 8-byte quantities, divided into two groups. The bottom group is labelled array and covers the top 5 entries in the stack, which hold the values 0 to 4. The top group is labelled slice and covers the bottom 2 entries in the stack. Of these 2 entries, the top one holds an arrow that points to the second element in the array chunk, counting from the bottom; the bottom entry holds a value labelled len=2.

Figure 1-4. Stack slice pointing into a stack array

The other common container for contiguous values is a Vec<T>. This holds a contiguous collection of values like an array, but unlike an array, the number of values in the Vec can grow (e.g., with push(value)) or shrink (e.g., with pop()).

The contents of the Vec are kept on the heap (which allows for this variation in size) but are always contiguous, and so a slice can refer to a subset of a vector, as shown in Figure 1-5:

#![allow(unused)]
fn main() {
let mut vector = Vec::<u64>::with_capacity(8);
for i in 0..5 {
    vector.push(i);
}
let vslice = &vector[1..3];
}
The diagram shows a stack on the left, and a heap on the right, both arranged as vertically stacked rectangles where each rectangle represents an 8-byte quantity. The heap on the right has 8 entries within it: from bottom to top the first 5 contain values from 0 to 4 consecutively; the top 3 entries are all labelled (uninit). The stack holds five 8-byte quantities, divided into two groups. The top group is labelled slice and holds two entries. Of these 2 entries, the top one holds an arrow that points to the second element in the heap chunk, counting from the bottom; the bottom entry holds a value labelled len=2. The bottom group of the stack is labelled vec and hols three entries. The top entry holds an arrow that points to the bottom element of the heap chunk; the middle entry has a value capacity=8; the bottom entry has a value len=5.

Figure 1-5. Stack slice pointing into Vec contents on the heap

There's quite a lot going on under the covers for the expression &vector[1..3], so it's worth breaking it down into its components:

  • The 1..3 part is a range expression; the compiler converts this into an instance of the Range<usize> type, which holds an inclusive lower bound and an exclusive upper bound.
  • The Range type implements the SliceIndex<T> trait, which describes indexing operations on slices of an arbitrary type T (so the Output type is [T]).
  • The vector[ ] part is an indexing expression; the compiler converts this into an invocation of the Index trait's index method on vector, together with a dereference (i.e., *vector.index( )).2
  • vector[1..3] therefore invokes Vec<T>'s implementation of Index<I>, which requires I to be an instance of SliceIndex<[u64]>. This works because Range<usize> implements SliceIndex<[T]> for any T, including u64.
  • &vector[1..3] undoes the dereference, resulting in a final expression type of &[u64].

Trait objects

The second built-in fat pointer type is a trait object: a reference to some item that implements a particular trait. It's built from a simple pointer to the item, together with an internal pointer to the type's vtable, giving a size of 16 bytes (on a 64-bit platform). The vtable for a type's implementation of a trait holds function pointers for each of the method implementations, allowing dynamic dispatch at runtime (Item 12).3

So a simple trait:

#![allow(unused)]
fn main() {
trait Calculate {
    fn add(&self, l: u64, r: u64) -> u64;
    fn mul(&self, l: u64, r: u64) -> u64;
}
}

with a struct that implements it:

struct Modulo(pub u64);

impl Calculate for Modulo {
    fn add(&self, l: u64, r: u64) -> u64 {
        (l + r) % self.0
    }
    fn mul(&self, l: u64, r: u64) -> u64 {
        (l * r) % self.0
    }
}

let mod3 = Modulo(3);

can be converted to a trait object of type &dyn Trait. The dyn keyword highlights the fact that dynamic dispatch is involved:

// Need an explicit type to force dynamic dispatch.
let tobj: &dyn Calculate = &mod3;
let result = tobj.add(2, 2);
assert_eq!(result, 1);

The equivalent memory layout is shown in Figure 1-6.

The diagram shows a stack layout on the left, with a single entry labelled mod3 with value 3 at the top, and below that a pair of entries jointly labelled tobj. The top entry in tobj holds an arrow that points to the mod3 entry on the stack; the bottom entry in tobj points to a composite rectangle on the right hand side of the diagram labelled Calculate for Modulo vtable. This representable of a vtable contains two entries, labelled add and mul. The first of these holds an arrow that leads to a box representing the code of Modulo::add(); the second holds an arrow that leads to a box representing the code of Modulo::mul().

Figure 1-6. Trait object with pointers to concrete item and vtable

Code that holds a trait object can invoke the methods of the trait via the function pointers in the vtable, passing in the item pointer as the &self parameter; see Item 12 for more information and advice.

More Pointer Traits

A previous section described two pairs of traits (Deref/DerefMut, AsRef/AsMut) that are used when dealing with types that can be easily converted into references. There are a few more standard traits that can also come into play when working with pointer-like types, whether from the standard library or user defined.

The simplest of these is the Pointer trait, which formats a pointer value for output. This can be helpful for low-level debugging, and the compiler will reach for this trait automatically when it encounters the {:p} format specifier.

More intriguing are the Borrow and BorrowMut traits, which each have a single method (borrow and borrow_mut, respectively). This method has the same signature as the equivalent AsRef/AsMut trait methods.

The key difference in intents between these traits is visible via the blanket implementations that the standard library provides. Given an arbitrary Rust reference &T, there is a blanket implementation of both AsRef and Borrow; likewise, for a mutable reference &mut T, there's a blanket implementation of both AsMut and BorrowMut.

However, Borrow also has a blanket implementation for (non-reference) types: impl<T> Borrow<T> for T.

This means that a method accepting the Borrow trait can cope equally with instances of T as well as references-to-T:

#![allow(unused)]
fn main() {
fn add_four<T: std::borrow::Borrow<i32>>(v: T) -> i32 {
    v.borrow() + 4
}
assert_eq!(add_four(&2), 6);
assert_eq!(add_four(2), 6);
}

The standard library's container types have more realistic uses of Borrow. For example, HashMap::get uses Borrow to allow convenient retrieval of entries whether keyed by value or by reference.

The ToOwned trait builds on the Borrow trait, adding a to_owned() method that produces a new owned item of the underlying type. This is a generalization of the Clone trait: where Clone specifically requires a Rust reference &T, ToOwned instead copes with things that implement Borrow.

This gives a couple of possibilities for handling both references and moved items in a unified way:

  • A function that operates on references to some type can accept Borrow so that it can also be called with moved items as well as references.
  • A function that operates on owned items of some type can accept ToOwned so that it can also be called with references to items as well as moved items; any references passed to it will be replicated into a locally owned item.

Although it's not a pointer type, the Cow type is worth mentioning at this point, because it provides an alternative way of dealing with the same kind of situation. Cow is an enum that can hold either owned data or a reference to borrowed data. The peculiar name stands for "clone-on-write": a Cow input can remain as borrowed data right up to the point where it needs to be modified, but it becomes an owned copy at the point where the data needs to be altered.

Smart Pointer Types

The Rust standard library includes a variety of types that act like pointers to some degree or another, mediated by the standard library traits previously described. These smart pointer types each come with some particular semantics and guarantees, which has the advantage that the right combination of them can give fine-grained control over the pointer's behavior, but has the disadvantage that the resulting types can seem overwhelming at first (Rc<RefCell<Vec<T>>>, anyone?).

The first smart pointer type is Rc<T>, which is a reference-counted pointer to an item (roughly analogous to C++'s std::shared_ptr<T>). It implements all of the pointer-related traits and so acts like a Box<T> in many ways.

This is useful for data structures where the same item can be reached in different ways, but it removes one of Rust's core rules around ownership—that each item has only one owner. Relaxing this rule means that it is now possible to leak data: if item A has an Rc pointer to item B, and item B has an Rc pointer to A, then the pair will never be dropped.4 To put it another way: you need Rc to support cyclical data structures, but the downside is that there are now cycles in your data structures.

The risk of leaks can be ameliorated in some cases by the related Weak<T> type, which holds a non-owning reference to the underlying item (roughly analogous to C++'s std::weak_ptr<T>). Holding a weak reference doesn't prevent the underlying item from being dropped (when all strong references are removed), so making use of the Weak<T> involves an upgrade to an Rc<T>—which can fail.

Under the hood, Rc is (currently) implemented as a pair of reference counts together with the referenced item, all stored on the heap (as depicted in Figure 1-7):

#![allow(unused)]
fn main() {
use std::rc::Rc;
let rc1: Rc<u64> = Rc::new(42);
let rc2 = rc1.clone();
let wk = Rc::downgrade(&rc1);
}
The diagram shows a stack on the left and a heap on the right. The stack holds three entries, labelled rc1, rc2 and wk. All three of these entries hold arrows that point to an object in the heap, however the arrow from the wk entry is dashed rather than solid. The object on the heap is a composite rectangle holding three component values: an entry labelled strong=2, and entry labelled weak=1 and an entry labelled 42.

Figure 1-7. Rc and Weak pointers all referring to the same heap item

The underlying item is dropped when the strong reference count drops to zero, but the bookkeeping structure is dropped only when the weak reference count also drops to zero.

An Rc on its own gives you the ability to reach an item in different ways, but when you reach that item, you can modify it (via get_mut) only if there are no other ways to reach the item—i.e., there are no other extant Rc or Weak references to the same item. That's hard to arrange, so Rc is often combined with RefCell.

The next smart pointer type, RefCell<T>, relaxes the rule (Item 15) that an item can be mutated only by its owner or by code that holds the (only) mutable reference to the item. This interior mutability allows for greater flexibility—for example, allowing trait implementations that mutate internals even when the method signature allows only &self. However, it also incurs costs: as well as the extra storage overhead (an extra isize to track current borrows, as shown in Figure 1-8), the normal borrow checks are moved from compile time to runtime:

#![allow(unused)]
fn main() {
use std::cell::RefCell;
let rc: RefCell<u64> = RefCell::new(42);
let b1 = rc.borrow();
let b2 = rc.borrow();
}
The diagram shows a representation of a stack, with three entries in it, each containing two 8-byte values. The top entry is labelled rc, and holds the value borrow=2 above a value 42. The middle entry is labelled b1, and holds two values with arrows: the top arrow leads to the 42 value in rc, the bottom arrow leads to the rc entry as a whole. The bottom entry is labelled b2 and holds the same contents as b1: a top arrow to 42 and a bottom arrow to rc.

Figure 1-8. Ref borrows referring to a RefCell container

The runtime nature of these checks means that the RefCell user has to choose between two options, neither pleasant:

  • Accept that borrowing is an operation that might fail, and cope with Result values from try_borrow[_mut]
  • Use the allegedly infallible borrowing methods borrow[_mut], and accept the risk of a panic! at runtime (Item 18) if the borrow rules have not been complied with

In either case, this runtime checking means that RefCell itself implements none of the standard pointer traits; instead, its access operations return a Ref<T> or RefMut<T> smart pointer type that does implement those traits.

If the underlying type T implements the Copy trait (indicating that a fast bit-for-bit copy produces a valid item; see Item 10), then the Cell<T> type allows interior mutation with less overhead—the get(&self) method copies out the current value, and the set(&self, val) method copies in a new value. The Cell type is used internally by both the Rc and RefCell implementations, for shared tracking of counters that can be mutated without a &mut self.

The smart pointer types described so far are suitable only for single-threaded use; their implementations assume that there is no concurrent access to their internals. If this is not the case, then smart pointers that include additional synchronization overhead are needed.

The thread-safe equivalent of Rc<T> is Arc<T>, which uses atomic counters to ensure that the reference counts remain accurate. Like Rc, Arc implements all of the various pointer-related traits.

However, Arc on its own does not allow any kind of mutable access to the underlying item. This is covered by the Mutex type, which ensures that only one thread has access—whether mutably or immutably—to the underlying item. As with RefCell, Mutex itself does not implement any pointer traits, but its lock() operation returns a value of a type that does: MutexGuard, which implements Deref[Mut].

If there are likely to be more readers than writers, the RwLock type is preferable, as it allows multiple readers access to the underlying item in parallel, provided that there isn't currently a (single) writer.

In either case, Rust's borrowing and threading rules force the use of one of these synchronization containers in multithreaded code (but this guards against only some of the problems of shared-state concurrency; see Item 17).

The same strategy—see what the compiler rejects and what it suggests instead—can sometimes be applied with the other smart pointer types. However, it's faster and less frustrating to understand what the behavior of the different smart pointers implies. To borrow (pun intended) an example from the first edition of the Rust book:

  • Rc<RefCell<Vec<T>>> holds a vector (Vec) with shared ownership (Rc), where the vector can be mutated—but only as a whole vector.
  • Rc<Vec<RefCell<T>>> also holds a vector with shared ownership, but here each individual entry in the vector can be mutated independently of the others.

The types involved precisely describe these behaviors.

1

Albeit with a warning from modern compilers.

2

The equivalent trait for mutable expressions is IndexMut.

3

This is somewhat simplified; a full vtable also includes information about the size and alignment of the type, together with a drop() function pointer so that the underlying object can be safely dropped.

4

Note that this doesn't affect Rust's memory safety guarantees: the items are still safe, just inaccessible.