Item 9: Familiarize yourself with reference and pointer types

A pointer is just a number, whose value is the address in memory of some other object. In source code, the type of the pointer encodes information about the type of the object being pointed to, so a program knows how to interpret the contents of memory at that address. It's possible to play fast and loose with these constraints with raw pointers, but they are very unsafe (Item 16) and beyond the scope of this book.

Simple Pointer Types

The most ubiquitous pointer type in Rust is the reference &T. Although this is a pointer value, the compiler ensures that various rules are observed: it must always point to a valid, correctly-aligned instance of the relevant type, and the borrow checking rules must be followed (Item 14). These additional constraints are roughly similar to the constraints that C++ has when dealing with references rather than pointers; however, C++ allows footguns¹ with dangling references:

// 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 make the equivalent code broken at compile time:

fn dangle() -> &'static i64 {
    let x: i64 = 32; // on the stack
    &x
}

error[E0515]: cannot return reference to local variable `x`
   --> references/src/main.rs:384:5
    |
384 |     &x
    |     ^^ returns a reference to data owned by the current function

A Rust reference is a simple pointer, 8 bytes in size on a 64-bit platform (which this Item assumes throughout):

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

Rust allocates items on the stack by default; 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 8 byte pointer value.

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

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. The Rust compiler looks for and uses implementations of this trait when it's dealing with dereferences (*x), allowing coercion of types (Item 6). There's also an equivalent DerefMut for when a mutable reference is involved.

The compiler has to deduce a unique type for an expression like *x, which means that the Deref traits can't be generic (Deref<T>): that would open up the possibility that a user-defined type could implement both Deref<TypeA> and Deref<TypeB>, leaving the compiler with a choice of TypeA or TypeB. Instead, the underlying type is an associated type named Target instead.

In contrast, the AsRef and AsMut traits encode their destination type as a type parameter, such as AsRef<Point>, allowing a single container type to support multiple destinations. For example, the String type implements

Deref with Target = str, meaning that an expression like &my_string can be coerced to type &str.
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>, as for Deref

A function that takes a reference can therefore be made even more general, by making the function generic over one of these traits. This means it accepts the widest range of reference-like types:

    fn show_as_ref<T: AsRef<Point>>(pt: T) {
        let pt = pt.as_ref();
        println!("({}, {})", pt.x, pt.y);
    }

Fat Pointer Types

Rust has two built-in fat pointer types: types that act as pointers, but which hold additional information about the thing they are pointing to.

The first such 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 whose size is known at compile time. A slice can therefore refer to a subset of an array:

    let array = [0u64; 5];
    let slice = &array[1..3];

The other common container for contiguous values is a Vec<T>. This holds a contiguous collection of values whose size can vary, and whose contents are held on the heap. A slice can therefore refer to a subset of a vector:

    let mut vec = Vec::<u64>::with_capacity(8);
    for i in 0..5 {
        vec.push(i);
    }
    let slice = &vec[1..3];

Stack slice into vector contents on heap

There's quite a lot going on under the covers for the expression &vec[1..3]:

The 1..3 part is a range expression; the compiler converts this into an instance of the Range<usize> type.
- 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 vec[ ] part is an indexing expression; the compiler converts this into an invocation of the Index trait's index method on vec, together with a dereference (i.e. *vec.index( )). (The equivalent trait for mutable expressions is IndexMut).
vec[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.
&vec[1..3] un-does the dereference, resulting in a final expression type of &[u64].

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)².

So a simple trait:

    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 (where 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);

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.

Other Pointer Traits

A previous section described several traits (Deref[Mut], AsRef[Mut] and Index) that are used when dealing with reference and slice types. There are a few more that can also come into play when working with various pointer types, whether from the standard library or user defined.

The simplest 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.

The Borrow and BorrowMut traits each have a single method (borrow and borrow_mut respectively) that has the same signature as the equivalent AsRef / AsMut trait methods.

However, the difference between them is still visible in the type system, because they have different blanket implementations for references to arbitrary types:

For &T:
- impl<'_, T, U> AsRef<U> for &'_ T
- impl<'_, T> Borrow<T> for &'_ T
For &mut T:
- impl<'_, T, U> AsRef<U> for &'_ mut T
- impl<'_, T> Borrow<T> for &'_ mut T

but 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:

    fn add_four<T: 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.

Finally, the ToOwned trait builds on the Borrow trait, adding a to_owned() method that produces a new owned item of the underlying type, like Clone. This means that:

A function that accepts Borrow can receive either items or references-to-items, and can work with references in either case.
A function that accepts ToOwned can receive either items or references-to-items, and can build its own personal copies of those items in either case.

Smart Pointer Types

The Rust standard library includes a variety of types that act like pointers to some degree or another, mediated (as usual, Item 5) by the standard traits described above. 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 behaviour, 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, so acts like a Box<T> is 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. 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 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 pair of reference counts together with the referenced items, all stored on the heap.

    let rc1: Rc<u64> = Rc::new(42);
    let rc2 = rc1.clone();
    let wk = Rc::downgrade(&rc1);

The next smart pointer type RefCell<T> relaxes the rule (Item 14) that an item can only be mutated 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 only allows &self. However, it also incurs costs: as well as the extra storage overhead (an extra isize to track current borrows), the normal borrow checks are moved from compile-time to run-time.

    let rc: RefCell<u64> = RefCell::new(42);
    let b1 = rc.borrow();
    let b2 = rc.borrow();

The run-time 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 if the borrow rules have not been complied with.

In either case, this run-time checking means that RefCell itself implements none of the standard pointer traits; instead, its access operations return a Ref<T> or RefMut 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 5), 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 only suitable for single threaded use; their implementations assume that there is no concurrent access to their internals. If this is not the case, then different smart pointers are needed, which include the additional synchronization overhead.

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 an value 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 multi-threaded code (but this only guards against 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 be sometimes be applied with the other smart pointer types; however, it's faster and less frustrating to understand what the behaviour of the different smart pointers implies. To borrow³ 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 behaviours.

1: Albeit with a warning from modern compilers.

2: 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.

3: Pun intended

Effective Rust