Understanding Memory Management, Part 4: Rust Ownership and Borrowing
Posted by ekr on 31 Mar 2025
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 allShape
objects implement anarea()
method. -
Rectangle
is a concrete type that implementsShape
and provides its own definition forarea()
.
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:
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:
- Adds the value
5
to the end of the vector. - 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()
:
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 inmain
).sum
which is a reference to the first number in the vector (currently the value1
), thoughdo_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:
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 ofnumbers
. .push_back()
potentially causes a reallocation, invalidating any pointer to an inner value ofnumbers
.
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()
modifiednumbers
and*sum
and so these references need to bemut
.do_something()
takesmut
arguments and so when you call it inmain()
you need to takemut
references.&mut numbers
and&mut numbers[0]
both borrownumbers
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 calledRc::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 Rc
s 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 implementCopy
so when we assignh2 = h1
on line7
Rust does a move.- We then try to use
h1
on line9
which is illegal because it has been moved. - The Rust compiler suggests that we should implement
Clone
, which is reasonable, but really we should implementCopy
(which, recall, also requiresClone
).
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.
Unless you explicitly tell it that's what you want in which case you better know what you're doing. ↩︎
i.e., just copying the memory ↩︎
Interestingly, when optimization is off
rustc
doesn't copyh1
toh2
but rather just initializesh1
andh2
with the same value. However, if you changeh1
before doing the assignment (after makingh1
mut, of course), then the assignment copies the fields as you would expect). ↩︎Technical note for Rust nerds: this is actually a generic function and
impl Shape + Circular
stuff is syntactic sugar forfn print_circumference<T: Shape + Circular>(shape: T)
. ↩︎Though cool people use
make_unique()
and friends. ↩︎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. ↩︎
Though this is undercut a little bit by Rust allowing you to redefine (shadow) variable names. ↩︎
Recall that
malloc()
will also over-allocate, so this reallocation might actually return the same region. ↩︎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. ↩︎
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. ↩︎We'd also need a
mut
reference tonumbers
because we want to modify the elements of the array and thelen_
field. ↩︎Specifically it implements
Deref
and notDerefMut
↩︎There are also
try_borrow()
andtry_borrow_mut()
which will fail if you try to break the rules. ↩︎