Educated Guesswork

Understanding Memory Management, Part 4: Rust Ownership and Borrowing

Cover image

This is the fourth post in my planned multipart series on memory management. Part I covers the basics of memory allocation and how it works in C, and parts II and III covered the basics of C++ memory management, including RAII and smart pointers. These tools do a lot to simplify memory management but because they were added on to the older manual management core of C you're left with a system which is mostly safe if you hold it right but which can quickly become unsafe if you're not careful. Next I want to talk about a language which was designed to be safe from the ground up and won't let you be unsafe:[1] Rust. I'd originally planned to talk about garbage collected languages next, but after all that time spent on how C++ works, I decided it would work better to do Rust next and then close with garbage collection.

Single Ownership #

Unlike C and C++—or any other language we'll be looking at—the basic design concept of Rust is single ownership. I.e.,

Any given object can only have a single owner.

We've already seen how to implement this model in C++ using unique pointers, but in Rust single ownership is just how everything works. Just as we saw with C++ unique pointers, this makes life simple: when the owning variable goes out of scope, the object is destroyed.

In C/C++, when you assign one variable to another, the default is to do a copy. By contrast, Rust moves the variable. Consider the following code:

C #
#include <stdio.h>
#include <stdlib.h>

struct Hat {
uint8_t size;
};

int main(int argc, char **argv) {
struct Hat h1 = { .size = 5 };
struct Hat h2 = h1;

printf("%u %u\n", h1.size, h2.size);
}
Rust #
struct Hat {
size: u8,
}

pub fn main() {
let h1 = Hat { size: 5 };
let h2 = h1;

println!("{} {}", h1.size, h2.size);
}

This is a simple piece of code: we first create a Hat named h1 of size 5. We then create a new hat h2 and assign h1 to h2 and then print out h1 and h2. With C this works exactly like you would expect:

5 5

With Rust, however, the situation is totally different, and the compiler gets mad at us:

error[E0382]: borrow of moved value: `h1`
 --> assign-rs.rs:9:23
  |
6 |     let h1 = Hat { size: 5 };
  |         -- move occurs because `h1` has type `Hat`, which does not implement the `Copy` trait
7 |     let h2 = h1;
  |              -- value moved here
8 |
9 |     println!("{} {}", h1.size, h2.size);
  |                       ^^^^^^^ value borrowed here after move
  |
note: if `Hat` implemented `Clone`, you could clone the value
 --> assign-rs.rs:1:1
  |
1 | struct Hat {
  | ^^^^^^^^^^ consider implementing `Clone` for this type
...
7 |     let h2 = h1;
  |              -- you could clone this value
  = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0382`.
make: *** [assign-rs.out] Error 1

This rather long error message is trying to be helpful, but it can be a bit confusing unless you're familiar with Rust. For instance, what does it mean for something to be a "borrow of moved value"? By the end of this post, you should be able to understand pretty much everything in this message.

Moving Variables #

As I said above, in Rust assigning variable A to variable B moves the object from A to B. In C++ this just means that it executes the move assignment operator and leaves the source object in a "valid but unspecified" state, but in Rust it means something different and much stronger: it makes B the new reference for the object and then renders A totally invalid. Unlike in C++, this invariant is enforced by the compiler, so when we later try to use h1 in the println!() statement, the compiler refuses and throws an error. This would happen with any use of h1 after it was assigned to h2.

All of this works because—unlike in C++—move semantics were baked into Rust from the start, and the compiler is easily able to enforce them (as well as produce a less confusing error message than you might get with some C++ template). Similarly, Rust doesn't need you to implement a move assignment operator because in Rust all moves are implemented the same way—at least conceptually—as a bitwise copy[2] of the object. I say "at least conceptually" because in this case you don't need to do a copy at all: the compiler can internally note that h1 is now defunct and it is now named h2 and move forward without doing any copying. Some playing around with Compiler Explorer reveals that that's what rustc does when optimization is on.[3]

Copying Integers #

Now consider some very similar Rust code, but using a bare integer in place of the struct containing just one integer:

pub fn main() {
let h1: u8 = 5;
let h2 = h1;

println!("{} {}", h1, h2);
}

This code compiles and runs perfectly well, exactly like our original C code.

5 5

Why does this code work and the other code not? The answer is instead of moving h1, the compiler has copied it. But that just requires us to ask why it copied it when I already said that Rust did moves on assignment? The answer to that question is that Rust knows that integers are simple objects which can be safely copied. As a practical matter, this mostly means that they don't contain pointers to anything, so that you don't have to worry about having two pointers to the same object (thus violating the single ownership rule). In this case, when you assignA to B it automatically makes a copy rather than invalidating B. This saves you the trouble of asking Rust to copy the variable rather than moving it.

Note that we're talking here about language semantics here, not the output binary. The net effect here is that the compiler knows that h1 and h2 can be used simultaneously, but it's free to make a copy or just note that h1 and h2 have the same contents and use them interchangeably in the println!() statement.

Copying Structs #

Of course, there's no real difference between an integer variable and a struct with only a single integer in it, so it's actually just safe to copy Hat as it is to copy u8, and we can tell Rust that by decorating the Hat definition like so:

#[derive(Copy, Clone)]
struct Hat {
size: u8,
}

With this slight change, our original Rust program will work, just like the C version or the bare integer Rust version. To understand why this works, we need to take a detour into the Rust type system.

Traits #

Although not a fully object-oriented language like C++, Rust includes some object-oriented features and in particular a feature called traits. Like a class, the idea behind a trait is to define a set of behaviors (in some other languages this is called an "interface") that types can implement. You may recall our shapes example from part II where we had a class called Shape and then derived classes for Rectangle and Circle. Here's the C++ code and the corresponding Rust code:

C++ #
class Shape {
virtual int area() = 0;
};

class Rectangle : public Shape {
public:
int width;
int height;

...

virtual int area() {
return width * height;
}
};
Rust #
trait Shape {
fn area(&self) -> usize;
}

struct Rectangle {
width: usize,
height: usize,
}

impl Shape for Rectangle {
fn area(&self) -> usize {
self.width * self.height
}
}

These two snippets have the same basic structure:

  • Shape defines the interface and says that all Shape objects implement an area() method.

  • Rectangle is a concrete type that implements Shape and provides its own definition for area().

Just like with C++, we can now write code that expects a Shape and use any struct that implements Shape. For instance, we can write:

fn print_area(shape: impl Shape) {
println!("Area is {}", shape.area());
}

pub fn main() {
let rect = Rectangle {
width: 10,
height: 5,
};

print_area(rect);
}

There are a number of important differences between class inheritance and trait implementation that aren't apparent here. For example, Rust traits can't have any data whereas C++ classes do; it just so happens that Shape doesn't have any data, but if we wanted to add (say) a name field to Shape we could do that in C++ and all classes that inherited from Shape would inherit that field; you can't do that in Rust. However, for the moment we can ignore these differences.

Marker Traits #

Our Shape trait just defines a single method, area() but there's actually nothing that requires us to define any methods at all; you can just have an empty trait like so:

trait Circular {}
impl Circular for Circle {}

It may not be immediately obvious why this would be useful, but here's an example. Unlike other shapes, you can compute the circumference of a circle from the area. So, we can write a function like this:

fn print_circumference(shape: impl Shape + Circular) {
let radius = (shape.area() / std::f64::consts::PI).sqrt();
let circumference = radius * 2.0 * std::f64::consts::PI;
println!("Circumference is {}", circumference);
}

The impl Shape + Circular type in the function signature says that the shape argument has to not only be a Shape but also implement Circular.[4] Note that we don't use any functions from Circular (there aren't any!), we just use it to restrict which shapes can be provided to print_circumference(). Consider the following function signature:

fn print_circumference(shape: impl Shape) {
...

This would compile and run, but would let you try to compute circumference from rectangles, even though that will give the right answer. The trait restriction for Circular (technical term: "trait bound") ensures that only circular objects can be used with print_circumference(). This particular example may feel a little contrived because we could just require print_circumference() to take a circle, but this design also lets us handle cylinders, which are also circular; all we have to do is implement Circular for Cylinder.

Circular is what's called a "marker trait"; it doesn't have any functionality of its own, it's just used to indicate that a type has a specific property.

The Copy Trait #

At this point, it should be obvious where this is going: Rust has a marker trait called Copy, which tells the compiler that an object is safe to copy. You can implement the Copy trait on a struct using the Rust derive macro, like so:

#[derive(Copy, Clone)]
struct Hat {
size: u8,
}

This code tells the Rust compiler to implement both the Copy and Clone traits on Hat. We'll get to the Clone trait in a little bit, but the Clone part is just syntactic sugar for impl Copy for {} (Rust has a lot of this kind of syntactic sugar). Again, Copy doesn't have any methods, it just tells the compiler that it's OK to make a shallow copy.

Of course, not all structs are safe to copy. For instance, if you have a struct that contains a pointer to some data on the heap, then copying it would violate the single owner rule—indicating which data is safe to copy is why we need to have the Copy trait in the first place—so what happens if we try to apply the trait to a non-copyable object, as below:

struct Inner {}

#[derive(Copy, Clone)]
struct Outer {
inner: Inner,
}

rustc will refuse to compile this, producing the following error:

error[E0204]: the trait `Copy` cannot be implemented for this type
 --> uncopyable.rs:3:10
  |
3 | #[derive(Copy, Clone)]
  |          ^^^^
4 | struct Outer {
5 |     inner: Inner,
  |     ------------ this field does not implement `Copy`
  |

The problem here—from the compiler's perspective—is that we asked Rust to implement Copy on Outer, but outer includes Inner, which doesn't implement Copy; and since copying Outer requires copying Inner and Inner doesn't implement Copy, then you can't copy Outer either. Because Rust knows which structs are safe to copy and will refuse to let you implement the Copy trait on them, it's not possible to incorrectly label an unsafe to copy object with Copy.

The second thing to notice is that Inner is actually perfectly safe to copy, seeing as it's empty. We've already seen that Rust knows when it's safe to implement Copy, so you might ask why it doesn't just automatically let you Copy whenever it's safe to do so (recall that the trait is empty, so it would be trivial to do so automatically). This is actually a common feature of Rust: there are any number of situations where you try to do something that requires trait X and Rust knows it's safe to implement, but forces you to explicitly derive traits even though it could do so automatically. As a friend said to me, writing Rust means resigning yourself to writing a lot of boilerplate; fortunately, the compiler will mostly tell you what boilerplate you need to add, and if you have a good IDE it will probably have affordances to let you automatically add it.

Clone #

Above, we told the compiler to derive both Copy and Clone. Above we went through Copy, which is approximately a shallow copy. By contrast, Clone allows for copying objects which can't be safely shallow copied. Here's the definition of the Clone trait:

pub trait Clone: Sized {
// Required method
fn clone(&self) -> Self;

...
}

Note how this is signature is reminiscent of C++'s copy assignment operator:

C++ #
  T& operator=(const T& other);
Rust #
fn clone(&self) -> Self;

Unlike C++, where assignment causes the copy assignment operator to be invoked (and where you have to explicitly invoke move semantics, in Rust you need to clone an object explicitly, in the obvious way using the .clone() method, as in:

    let h1 = Hat { size: 5 };
let h2 = h1.clone();

Like C++, Rust will provide a default implementation (in this case, if you do #[derive(Clone)]. As you would expect, the default implementation recursively clones all of the members of the struct, so it will work as long as all of those members also implement Clone (which of course means that all of their members need to implement Clone, etc.). However, again as with C++, when you implement Clone you can supply any method clone() that you want as long as it returns an instance of the object (that's what the -> Self means). For example, as we'll see later, this is how Rust implements reference counted pointers, with .clone() implementing the reference count. By contrast, you can't override the behavior of Copy because it has no methods; it's just a marker.

As shown above, if you want to implement Copy Rust also requires you to implement Clone. As far as I can tell, this isn't logically necessary, but it's obviously the case that if you can safely shallow copy a struct, you can implement clone() by just doing a shallow copy, so it's somewhat silly to allow people to implement Copy but not Clone.

Heap Allocation and Box #

So far we've just looked at ordinary stack variables, but in Rust, just like in C++, you frequently need to allocate memory on the heap, but as we saw, giving the programmer to have direct access to pointers results in all kinds of shenanigans. Rust addresses this by requiring that all pointers be boxed and forbidding you from unboxing them (again, except in special code).

The basic smart pointer in Rust is called Box, which is the rough equivalent to C++ unique_ptr. For example, the following code allocates space containing the integer (10) and then prints it out:

use std::boxed::Box;

fn main() {
let b = Box::new(10);

println!("tmp = {}", *b);
}

Unlike the way we've used C++ smart pointers, where we first called new and then passed the result to the smart pointer (shared_ptr<Obj> s(new Obj())), Box::new() does the memory allocation itself, and what you pass it is actually a created object, which it then moves into the box.[5] You can in fact break these up, as in the following code where we make a Hat named h1 and then move it into hbox. As usual, h1 will be unusable after we've done that, so we're still following the single ownership rule.

use std::boxed::Box;
struct Hat {
size: u8,
}

pub fn main() {
let h1 = Hat { size: 5 };
let hbox = Box::new(h1);
println!("{}", hbox.size);
}

Conventionally, you'd do this in one operation, as in Box::new(Hat { size: 5 }) but there's no real difference between these two pieces of code.

Like all the Rust pointer types, Box is actually a generic, so it can contain a pointer of any type. In this particular case, this is a 32 bit signed integer (i32), so b is actually of type Box<i32>.

Box behaves like any other Rust struct, so you can pass it around, assign a Box to other variables, etc. You can even make a Box of a Box if you want to.

Mutability and Immutability #

By default, variables in rust are immutable, which is to say that once you have assigned their values. For instance, the following code will not compile:

let x = 10;
x = 20;

The error looks like this:

   |
9  |     let x = 10;
   |         - first assignment to `x`
10 |     x = 20;
   |     ^^^^^^ cannot assign twice to immutable variable
   |
help: consider making this binding mutable
   |
9  |     let mut x = 10;
   |         +++

Characteristically, the compilation error tells us exactly what we need to do, which is to make x mutable using the mut keyword:

    let mut x = 10;

This is another case where Rust is the opposite of C/C++, in which variables are mutable by default but can be labeled immutable with the const keyword:

    const uint8_t x = 10;

You can get along OK programming with just mutable variables—or, for that matter, with just immutable variables[6]—but it's a lot more convenient to have both because it forces you to be intentional about which variables will change and which will not.[7] Generally good practice is to have as many variables be immutable as possible and then make them mutable only when necessary. The Rust compiler will stop you from modifying immutable variables and complain—though not generate a hard error—if you make a variable mutable unncessarily.

References and Borrowing #

Consider the following trivial piece of Rust code:

struct Hat {
size: u8,
}

fn print_hat_size(h: Hat) {
println!("{}", h.size);
}

fn main() {
let h1 = Hat { size: 5 };

print_hat_size(h1);
print_hat_size(h1);
}

This won't compile because we moved h1 into print_hat_size() the first time we called it and so we can't pass it into print_hat_size() again because it's now been invalidated. This is obviously really unhelpful: we know that once print_hat_size() has returned it's not doing anything with the Hat, so it's available to use again, but the compiler won't let us.

One option here would be to have print_hat_size() pass Hat back by returning it and then we could call it again, like so:

struct Hat {
size: u8,
}

fn print_hat_size(h: Hat) -> Hat {
println!("{}", h.size);
h
}

fn main() {
let h1 = Hat { size: 5 };
let h1 = print_hat_size(h1);
print_hat_size(h1);
}

This will obviously work, but it's really clunky, and what if we wanted print_hat_size() to return something else? Then we'd need to deal with the actual return value. Instead, what we want to do is let print_hat_size() temporarily use its argument without actually taking ownership. In Rust this is called borrowing and the resulting borrowed item is called a reference.

We've already seen this kind of operation in C and C++ where we we passed a pointer or a reference (C++) to an object to a function, like so:

Passing a Pointer #
void foo(Hat* hat) {...}

struct Hat h1 = { .size = 5 };
foo(&h1);
Passing a Reference #
void foo(Hat& hat) {...}

struct Hat h1 = { .size = 5 };
foo(h1);

Borrowing in Rust is conceptually more like passing a reference in C++ in that in C++ references the callee has access to the object in the calling function but it's not a pointer and so you can't do pointer-like things like free(); this shouldn't be surprising because Rust doesn't let us access raw pointers at all. And just as with C++ references, you use . notation to reference inner values of the struct rather than -> as you would with a pointer.

Mutable and Immutable References #

Just as Rust supports both mutable and immutable objects, it also supports mutable and immutable references, which have the semantics you would expect:

fn addone(input: &mut i32) {
*input += 1;
}

fn print_value(input: &i32) {
println!("Value {}", input);
}

pub fn main() {
let mut i = 10;

print_value(&i);
addone(&mut i);
print_value(&i);
}

Which produces the following output when run:

Value 10
Value 11

The basic way to take a reference to i is to do &i, which is what we do with print_value(), which does not need to modify its input. By contrast, addone() does need to modify its input, so it needs to take a &mut reference. Note that we need mut in three places:

  • Labeling i as mutable
  • In the signature for addone()
  • At the call site to addone()

Note that addone() is modifying i in place, which is why when we call print_value() in main() we see it modified. This is just the same call by reference semantics we've seen before.

References are a critical tool but the way I've just described them creates an opportunity for people to really screw things up. Consider the following C++ code (I'm using C++ here for a reason which will will be apparent soon):

#include <vector>
#include "./print-array.h"

void do_something(std::vector<size_t> &numbers, size_t &sum) {
numbers.push_back(5);
for (auto i : numbers) {
sum += i;
}
}

int main(int argc, char **argv) {
std::vector<size_t> numbers = {1,2,3};
size_t sum;

do_something(numbers, sum);
std::cout << "Numbers = " << numbers << " Sum=" << sum << std::endl;
}

Just to orient yourself, what this code does is to allocate a vector of length 3 containing the values 1, 2, 3 and then passes it to a function do_something() along with a reference to an integer of type usize that will hold the sum of the values. do_something() then does the following:

  1. Adds the value 5 to the end of the vector.
  2. Sets the value of sum to the sum of the values

And then finally main prints out the list of numbers and the sum:

Numbers = [1, 2, 3, 5] Sum=11

This code is fine (though kind of pointless), but now let's consider a very slight modification of this code where instead of passing a reference to a separate local variable in the sum argument, we instead pass a reference to the first element in the numbers vector:

#include <vector>
#include "./print-array.h"

void do_something(std::vector<size_t> &numbers, size_t &sum) {
numbers.push_back(5);
for (auto i : numbers) {
sum += i;
}
}

int main(int argc, char **argv) {
std::vector<size_t> numbers = {1,2,3};

do_something(numbers, numbers[0]);
std::cout << "Numbers = " << numbers << " Sum=" << sum << std::endl;
}

Note that we just changed the line labeled Changed code. Everything else is the same. Naively, the expected outcome of this program would be the following:

Numbers=[11, 2, 3, 5], Sum=11

This is certainly one possible outcome, but it's not the only one, and the others are bad. To see why, we need to take a closer look at what's actually going on in memory. The figure below shows the situation at the start of do_something():

Memory layout at the start of

Memory layout at the start of `do_something()`

On the left, we see the two arguments to do_something():

  • numbers which is a reference to the vector of numbers (itself a local variable in main).
  • sum which is a reference to the first number in the vector (currently the value 1), though do_something() doesn't know that; it's just the same code as before.

Recall from part II, that a minimal container structure like a vector will look something like this:

class<typename T> Vector {
T* data_; // The elements of the vector
size_t len_; // The length of the vector
size_t size_; // The total size of the vector
}

data_ contains the address of the memory region allocated for the elements of the vector and len_ contains the number of elements in the vector, and size_ contains the total size of the data_ region.

The reason we need separate size_ and len_ fields is to make it cheap to grow and shrink the vector. Typically with a container structure like this, you wouldn't just allocate enough space for the initial number of elements requested, but instead allocate more space (maybe twice as much). When you want to add another element, you just add it to the end of the region and increment size_ but you don't need to allocate more memory until you've exhausted the initial allocation. Similarly, if someone wants to remove the last element in the buffer, you can just decrement len_, leaving one more slot for a future insertion. The idea here is to avoid unnecessary allocation and copying of the memory region.

Of course, no matter how much you overallocate you'll eventually reach the end of the pre-allocated buffer, at which point you'll need to do a new allocation.[8] That's the situation here because len_ and size_ are the same, so the next insertion will require reallocating, with the result shown below:

Memory layout after inserting

Memory layout after inserting `5`

As you can see, we've allocated a new region to hold the expanded vector and inserted the new element 5 at the end. This is all totally fine as for as numbers is concerned; the problem is with sum, which is now pointing to the old (free()ed) region of memory which used to contain the contents of the vector but could now contain anything at all or even be in use for something (e.g., for allocator bookkeeping). When we now go and attempt to write into *sum, this is a classic use-after-free issue and can have pretty much any result (in C/C++ this would be undefined behavior), and could easily lead to a crash or a vulnerability.[9]

I want to emphasize that this is would be totally legal C++ code and the compiler will be perfectly happy to compile it: the only think that causes the problem is that we know that .push() might cause a reallocation, but you could easily have a fixed-size container which refused to reallocate, in which case this code would be safe; the fact that it's not depends on information which the compiler doesn't have. This code is not, however, legal Rust.

The Rules of Borrowing #

The way that Rust avoids the kind of issues we just saw is by restricting borrowing. Specifically: any given object can have either:

  • One mutable reference
  • An arbitrary number of immutable references

The compiler enforces these rules for you via the "borrow checker" and will throw an error if you try to violate them.

The code above violates these rules because we are taking two mutable references to numbers. This might not be apparently obvious because the second reference is actually to one of the elements of numbers, but the reference to numbers also transitively covers every element in numbers, the effect is the same.[10]

Now let's try to write the corresponding Rust code, which looks like this:

fn do_something(numbers: &mut Vec<usize>, sum: &mut usize) {
numbers.push(5);
for i in numbers {
*sum = *sum + *i;
}
}

pub fn main() {
let mut numbers = vec![1, 2, 3];

do_something(&mut numbers, &mut numbers[0]); // Changed code
println!("Numbers={:?}, Sum={}", numbers, &numbers[0]);
}

[Updated 2025-03-31 with the right code. Thanks to Dave Cridland.]

When we try to compile this code, we get the following error:

error[E0499]: cannot borrow `numbers` as mutable more than once at a time
 --> double-borrow-bad.rs:8:37
  |
8 |     do_something(&mut numbers, &mut numbers[0]);
  |     ------------ ------------       ^^^^^^^ second mutable borrow occurs here
  |     |            |
  |     |            first mutable borrow occurs here
  |     first borrow later used by call

It should be obvious, but you can't fix this just by changing these to immutable references: the compiler knows that do_something() takes mutable references and so will refuse to compile that code too:

error[E0308]: arguments to this function are incorrect
  --> double-borrow-bad.rs:11:5
   |
11 |     do_something(&numbers, &numbers[0]); // Changed code
   |     ^^^^^^^^^^^^           ----------- types differ in mutability
   |
note: types differ in mutability
  --> double-borrow-bad.rs:11:18
   |
11 |     do_something(&numbers, &numbers[0]); // Changed code
   |                  ^^^^^^^^
   = note: expected mutable reference `&mut Vec<usize>`
                      found reference `&Vec<{integer}>`
   = note: expected mutable reference `&mut usize`
                      found reference `&{integer}`

Similarly, even if we were to change the signature of do_something() to take immutable references, then do_something() wouldn't compile because the compiler knows that .push_back() modifies the vector, and assignment to *sum changes the object being referred to (whatever it is), so it won't compile do_something()

Global Safety via Local Reasoning #

I want to step back for a moment to pull out the larger point that this example shows, which is that the way Rust delivers global safety is by enforcing local properties. Recall from above that the original code was unsafe as the result of two different properties:

  • When we called do_something() we took a pointer to an inner value of numbers.
  • .push_back() potentially causes a reallocation, invalidating any pointer to an inner value of numbers.

These two properties are very distant in the code and so you need global analysis to determine that it's unsafe. This analysis is difficult and may not even be possible (in fact the source code of .push_back() may not be available to the compiler at the time it is compiling do_something()), so the C++ compiler cannot detect the error at compile time, leaving you with a run time problem. Rust's conservative borrowing rules prevent this via enforcing the following properties:

  • do_something() modified numbers and *sum and so these references need to be mut.
  • do_something() takes mut arguments and so when you call it in main() you need to take mut references.
  • &mut numbers and &mut numbers[0] both borrow numbers and so the compiler forbids the double borrow.

The important thing to realize is that each of these properties is enforced purely locally; when the compiler forbids the double borrow in do_something() it doesn't need to know anything about the behavior of do_something(), just that it needs to take two mut references. However, the result of applying the rules locally is to provide global safety.

Unfortunately, this safety doesn't come for free because these rules are conservative and therefore forbid code which would actually be safe but which the compiler cannot locally verify is safe. For example, suppose that as hypothesized above .push() never allocated new memory but just allocated out of a fixed-size buffer and returned an error when you tried to exceed the size of that buffer. In that case, what we're doing here would be fine—though odd—but Rust still wouldn't allow it, as we'd still need to take a mut reference to &numbers[0].[11] Much of the experience of programming in Rust is about trying to structure your code in such a way that the compiler can determine that what you are trying to do is safe—or, as is often the case, determining that the reason it can't determine it's safe is that it actually isn't.

In the rest of this post and the next, I want to talk about some of the gymnastics you have to do when writing Rust code in order to satisfy the borrow checker; this will also come up in the next post.

Shared Ownership #

As mentioned in part III while single ownership is easier to reason about there are situations where you really need to have some kind of shared ownership. C++ provides the shared_ptr class for this, and Rust has a similar affordance called Rc (for "reference counted"), as well as a weak pointer type called Weak. These are implemented (mostly) the same as C++ smart pointers but with some important differences.

Just to orient you, here is the Rc-ized version of the code we started with:

Code #

use std::rc::Rc;

struct Hat {
size: u8,
}

pub fn main() {
let h1 = Rc::new(Hat { size: 5 }); // Reference count 1
let h2 = Rc::clone(&h1);
println!("{} {}", h1.size, h2.size);
}

Output #

5 5

As you can see this works perfectly fine.

Note that unlike with C++, you can't just assign one Rc to another but instead you call Rc::clone, which invoked the "associated function" clone of the struct Rc, which increments the reference count and returns a new copy of the Rc object which can then be assigned to h2. If you were to instead just assign h1 to h2 it would move it and you would get the same type of use-after-move compilation error we got in our original code.

The question you should immediately be asking here is why Rc doesn't violate Rust's single ownership rule, given that we now have both h1 and h2 pointing to the same Hat instance. The reason is that Rc mediates access to the owned object in order to ensure safety. Specifically:

  • Ordinary access to the object through Rc only allows immutable operations[12] so that if you try to modify it (e.g., h2.size = 1) it will fail.

  • It is possible to get a mutable reference to the owned object via the Rc::get_mut() function, but this will only succeed if the reference count is equal to one. You also can't get a reference of either type to the owned object once you called Rc::get_mut() because the compiler detects that this would be a double borrow (the rules that make this work are a bit advanced to go into right now).

The result of these two rules is that you can have as many immutable references as you want but that you can't combine a mutable reference with either another mutable reference or another immutable reference, just like with the ordinary borrowing rules; unlike with the borrowing rules, Rc enforces its rules at runtime, so attempting to call Rc::get_mut() at the wrong time will fail.

Interior Mutability #

I said we weren't going to implement Rc but ask yourself this:

How does Rc maintain the reference count?

Presumably there is some internal reference count value in Rc just like there is in C++ shared_ptr, but that's only half the story because we can call Rc::clone() with an immutable reference to the Rc object, like so:

    let h2 = Rc::clone(&h1);

Rc::clone() obviously has to increment the reference count, but the whole point of an immutable reference is that you can't change the referenced object, so what's going on here? The answer is that Rust has a set of special smart pointers that allow you mutate an object—under controlled conditions—even when you only have an immutable reference: Cell and RefCell. Rc actually uses Cell, but in this post I'll be talking about RefCell, which is the one I have used more often.

Like Rc, we make a RefCell with RefCell::new(T) where T is an instance of the relevant type. Unlike Rc, you can't use the RefCell directly but have to explicitly call .borrow() to get an immutable reference and .borrow_mut() to get a mutable reference, as shown in the code below.

Code #

use std::cell::RefCell;

struct Hat {
size: u8,
}

pub fn main() {
let h1 = RefCell::new(Hat { size: 5 });
println!("{} {}", h1.borrow().size, h1.borrow().size);

let mut borrowed = h1.borrow_mut();
borrowed.size = 10;
println!("{}", borrowed.size);
}

Output #

5 5
10

RefCell enforces the usual rules about references, namely that you can have as many immutable references outstanding as you want as long as there aren't any mutable references, and if there is a mutable reference then there can't be any other references. If you try to violate these rules, Rust will call panic!(), which terminates the program (unless caught).[13]

This tells us how to implement the reference count in Rc: put the reference count object in a RefCell (as I said, it's actually a Cell, which has a different syntax but can be used to the same effect). Then we can hold an immutable reference to Rc<Hat> but still call Rc::clone(). It's Rc's job to ensure that it follows the borrowing rules—or risk a program crash—but note that even if you mess up with RefCell you still can't cause a memory error or another unsafe condition; all that will happen is that the program crashes.

It's quite common to combine Rc with RefCell to get functionality that is sort of like C++'s shared_ptr: once you have two Rcs pointing to the same object you can't use either one to mutate it, but there are a lot of settings in which you want to have shared ownership of an object but allow it to be mutated in one place or the other. In C++ you can just do this, but in Rust you have to do something like Rc<RefCell<Hat>>, with Rc providing the reference counted pointer to the immutable RefCell object which itself lets you mutate the internal Hat object.

Enforcing the Reference Count #

There's one more interesting point to make about RefCell. If the compiler isn't enforcing the rules about the number of mutable and immutable references, and they're enforced by RefCell at runtime, how does that work? Obviously, it maintains a count of the number of references it has given out, but how does it know when they go away? This involves a little bit of cleverness but you should be able to work it out for yourself given what we've seen so far. I'll wait.


Figure it out?

Instead of returning &T and &mut T, borrow() and borrow_mut() instead return some new smart pointers named Ref and RefMut. These smart pointers act (mostly) as if they were actually references to the owned object, so you can (mostly) use them that way without thinking too hard about it. They are attached to the underlying RefCell and when Ref and RefMut go out of scope, their destructors fire (Rust calls this the Drop trait, and this decrements the RefCell's count of the number of outstanding references.

We can see this in the following code snippet:

use std::cell::RefCell;

struct Hat {
size: u8,
}

pub fn main() {
let h1 = RefCell::new(Hat { size: 5 });
println!("{} {}", h1.borrow().size, h1.borrow().size);
{
let mut borrowed = h1.borrow_mut();
borrowed.size = 10;
println!("{}", borrowed.size);
// borrowed is dropped here.
}
println!("{} {}", h1.borrow().size, h1.borrow().size);
}

In the the first call to println!() we borrow h1 twice immutably (which is safe) but these borrows go out of scope after println!() returns. We then call borrow_mut() and assign it to borrowed, at which point no other borrows are permitted; if we were to try to do another borrow right before the next println!() the program would panic. However, once the braced block {...} is closed, then borrowed goes out of scope, it's drop callback fires, and so there are no more borrows of any kind and the immutable borrows in the final println!() are permitted.

Decoding our Original Error #

We are now in a position to understand our original error, which I've reproduced for your convenience.

Code #

struct Hat {
size: u8,
}

pub fn main() {
let h1 = Hat { size: 5 };
let h2 = h1;

println!("{} {}", h1.size, h2.size);
}

Output #

error[E0382]: borrow of moved value: `h1`
 --> assign-rs.rs:9:23
  |
6 |     let h1 = Hat { size: 5 };
  |         -- move occurs because `h1` has type `Hat`, which does not implement the `Copy` trait
7 |     let h2 = h1;
  |              -- value moved here
8 |
9 |     println!("{} {}", h1.size, h2.size);
  |                       ^^^^^^^ value borrowed here after move
  |
note: if `Hat` implemented `Clone`, you could clone the value
 --> assign-rs.rs:1:1
  |
1 | struct Hat {
  | ^^^^^^^^^^ consider implementing `Clone` for this type
...
7 |     let h2 = h1;
  |              -- you could clone this value
  = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0382`.
make: *** [assign-rs.out] Error 1

Most of this should now be straightforward:

  • Hat doesn't implement Copy so when we assign h2 = h1 on line 7 Rust does a move.
  • We then try to use h1 on line 9 which is illegal because it has been moved.
  • The Rust compiler suggests that we should implement Clone, which is reasonable, but really we should implement Copy (which, recall, also requires Clone).

One thing might be confusing, though, which is that the error is "borrow of moved value: h1" even though there's no explicit borrow here: we're passing h1.size not &h1.size to println!(). The clue here is the !, which denotes that println! is a Rust macro; inside that macro, println!() is taking a reference to its arguments to avoid consuming them, hence this is a borrow, not just a use.

Next Up: More Rust #

As you may have gathered, one of the main experiences of learning Rust is figuring out how to architect your code in a way that is consistent with Rust's ownership and borrowing rules. A lot of that is building a mental model of how Rust works, which is what this post is about, but at the end of the day, there's also a fair amount of gymnastics required. I'll be going into that more in the next post.

Appendix: C++ vs. Rust smart pointers #

As a reference, here is a comparison table between C++ and Rust smart pointers.

Type C++ Rust
Single ownership unique_ptr Box
Shared ownership (strong) shared_ptr Rc
Shared ownership (weak) weak_ptr Weak
Atomic shared pointers atomic<ptr-type> arc::Arc/arc::Weak
Internal ref counting boost::intrusive_ptr* intrusive_collections*
Interior mutability N/A Cell, RefCell
  • Non-standard feature.

  1. Unless you explicitly tell it that's what you want in which case you better know what you're doing. ↩︎

  2. i.e., just copying the memory ↩︎

  3. Interestingly, when optimization is off rustc doesn't copy h1 to h2 but rather just initializes h1 and h2 with the same value. However, if you change h1 before doing the assignment (after making h1 mut, of course), then the assignment copies the fields as you would expect). ↩︎

  4. Technical note for Rust nerds: this is actually a generic function and impl Shape + Circular stuff is syntactic sugar for fn print_circumference<T: Shape + Circular>(shape: T). ↩︎

  5. Though cool people use make_unique() and friends. ↩︎

  6. All mutable is a pretty common design pattern in languages ranging from C and C++ to Python and JavaScript. A number of functional languages (e.g., Erlang) are all immutable, which requires a somewhat different set of programming idioms, typically involving explicitly maintaining state by passing around the result of computations. ↩︎

  7. Though this is undercut a little bit by Rust allowing you to redefine (shadow) variable names. ↩︎

  8. Recall that malloc() will also over-allocate, so this reallocation might actually return the same region. ↩︎

  9. NGL, this contrived example is probably not going to do anything bad, but that kind of thinking is a big part of why memory errors in C/C++ are so dangerous, because they often don't cause problems during testing but can then be exploited in bigger systems. ↩︎

  10. I wrote the example this way rather than double borrowing numbers directly because it's a bit hard to create a dangerous example that way without using some kind of concurrency (parallelism) mechanism. In multithreaded programs, concurrent access to exactly the same data structure routinely causes problems. ↩︎

  11. We'd also need a mut reference to numbers because we want to modify the elements of the array and the len_ field. ↩︎

  12. Specifically it implements Deref and not DerefMut ↩︎

  13. There are also try_borrow() and try_borrow_mut() which will fail if you try to break the rules. ↩︎