Item 9: 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 only be accessible 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, "normal" 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, whose type 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 which satisfies 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 constraints that a Rust reference must point to a valid, correctly-aligned item are shared by C++'s reference types. However, C++ has no concept of lifetimes and so allows footguns1 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:399:5
|
399 | &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
).
In the generated code, a Rust reference is a simple pointer, 8 bytes in size on a 64-bit platform (which this Item assumes throughout):
#![allow(unused)] fn main() { struct Point { x: u32, y: u32, } let pt = Point { x: 1, y: 2 }; let x = 0u64; let ref_x = &x; let ref_pt = &pt; }
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 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
. 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 behaviour 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 6).
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
behaviour in the compiler, but also 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:
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 withDeref
).
We saw above that a function that takes a reference can automatically take any type that implements Deref
, via the
Deref
coercion that the compiler performs. Such a function can be made even more general, by making it generic over one of the AsRef
/ AsMut
traits, and changing it to use .as_ref()
on the input. This
means it accepts the widest range of reference-like types:
fn show_as_ref<T: AsRef<Point>>(pt: T) {
let pt: &Point = 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:
#![allow(unused)] fn main() { 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:
#![allow(unused)] fn main() { let mut vec = Vec::<u64>::with_capacity(8); for i in 0..5 { vec.push(i); } let slice = &vec[1..3]; }
There's quite a lot going on under the covers for the expression &vec[1..3]
, so it's worth breaking down into its
components:
- The
1..3
part is a range expression; the compiler converts this into an instance of theRange<usize>
type, which holds an inclusive lower bound and an exclusive upper bound. - The
Range
type implements theSliceIndex<T>
trait, which describes indexing operations on slices of an arbitrary typeT
(so theOutput
type is[T]
). - The
vec[ ]
part is an indexing expression; the compiler converts this into an invocation of theIndex
trait'sindex
method onvec
, together with a dereference (i.e.*vec.index( )
).- The equivalent trait for mutable expressions is
IndexMut
.
- The equivalent trait for mutable expressions is
vec[1..3]
therefore invokesVec<T>
's implementation ofIndex<I>
, which requiresI
to be an instance ofSliceIndex<[u64]>
. This works becauseRange<usize>
implementsSliceIndex<[T]>
for anyT
, includingu64
.&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)2.
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
(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.
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 means that:
- 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, it's worth mentioning the
Cow
type 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 stay as borrowed data right up to the
point where it needs to be modified, but 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 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>
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. 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.
#![allow(unused)] fn main() { use std::rc::Rc; let rc1: Rc<u64> = Rc::new(42); let rc2 = rc1.clone(); let wk = Rc::downgrade(&rc1); }
An Rc
on its own gives you the ability to reach an item in different ways, but when you reach that item you can only
modify it (via get_mut
) 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 another smart pointer type…
The next smart pointer type RefCell<T>
relaxes the
rule (Item 15) 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.
#![allow(unused)] fn main() { use std::cell::RefCell; 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 fromtry_borrow[_mut]
- Use the allegedly-infallible borrowing methods
borrow[_mut]
, and accept the risk of apanic!
at runtime (Item 18) 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<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 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 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 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 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 borrow3 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