The Rust Programming Language · Ch.15 Smart Pointers

1

Chapter 15 · Introduction

Pointers, references and smart pointers

A pointer is a general concept for a variable that contains an address in memory; the address refers to, or “points at,” some other data. The most common kind of pointer in Rust is a reference (Chapter 4): indicated by the & symbol, it borrows the value it points to. References have no special capabilities other than referring to data, and they have no overhead.

Smart pointers aren’t unique to Rust: they originated in C++ and exist in other languages as well. Rust’s standard library defines a variety of them, providing functionality beyond that of references. One example in this chapter is a reference counting smart pointer, which lets data have multiple owners by keeping track of the number of owners and cleaning up the data when no owners remain.

With Rust’s ownership and borrowing there is one more difference: while references only borrow data, in many cases smart pointers own the data they point to.

The Rust Programming Language · Ch.15 Smart Pointers

2

Chapter 15 · Introduction

Deref, Drop, and the smart pointers in this chapter

Smart pointers are usually implemented using structs. Unlike an ordinary struct, they implement the Deref and Drop traits. Deref lets an instance of the smart pointer struct behave like a reference, so you can write code that works with either references or smart pointers. Drop lets you customize the code that runs when an instance goes out of scope.

The smart pointer pattern is a general design pattern used frequently in Rust; many libraries have their own, and you can write your own. The chapter covers the most common ones in the standard library:

• Box<T>, for allocating values on the heap;
• Rc<T>, a reference counting type that enables multiple ownership;
• Ref<T> and RefMut<T>, accessed through RefCell<T>, a type that enforces the borrowing rules at runtime instead of compile time.

It also covers the interior mutability pattern, where an immutable type exposes an API for mutating an interior value, and reference cycles: how they can leak memory and how to prevent them.

The Rust Programming Language · Ch.15 Smart Pointers

3

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Boxes and when to use them

Boxes have no performance overhead other than storing their data on the heap instead of the stack — but they don’t have many extra capabilities either. You’ll use them most often in these situations:

1. When you have a type whose size can’t be known at compile time, and you want to use a value of that type in a context that requires an exact size.
2. When you have a large amount of data, and you want to transfer ownership but ensure that the data won’t be copied when you do so.
3. When you want to own a value, and you care only that it’s a type that implements a particular trait rather than being of a specific type.

The Rust Programming Language · Ch.15 Smart Pointers

4

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

The three use cases, in more detail

1. Unknown size. Demonstrated below in “Enabling Recursive Types with Boxes.”
2. Large data. Transferring ownership of a large amount of data can take a long time because the data is copied around on the stack. To improve performance, store the data on the heap in a box: then only the small amount of pointer data is copied around on the stack, while the data it references stays in one place on the heap.
3. Trait implemented. This case is known as a trait object; “Using Trait Objects to Abstract over Shared Behavior” in Chapter 18 is devoted to it — so what you learn here you’ll apply again there.

Storing data on the heap

Before discussing the heap storage use case for Box<T>, we cover the syntax and how to interact with values stored within a Box<T>.

The Rust Programming Language · Ch.15 Smart Pointers

5

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Storing an i32 on the heap

Listing 15.1: Storing an i32 value on the heap using a box — src/main.rs

The variable b has the value of a Box that points to the value 5, which is allocated on the heap. The program prints b = 5: we can access the data in the box similarly to how we would if it were on the stack. Just like any owned value, when a box goes out of scope, as b does at the end of main, it is deallocated — both the box (stored on the stack) and the data it points to (stored on the heap).

Putting a single value on the heap isn’t very useful, so you won’t use boxes by themselves this way very often; values like a single i32 are more appropriately stored on the stack, where they live by default. Next: a case where boxes let us define types we wouldn’t be allowed to define without them.

The Rust Programming Language · Ch.15 Smart Pointers

6

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Enabling recursive types with boxes

Recursive types pose an issue because Rust needs to know at compile time how much space a type takes up, yet the nesting of values could theoretically continue infinitely. Because boxes have a known size, we can enable recursive types by inserting a box in the recursive type definition.

The example is the cons list, a data type commonly found in functional programming languages. It is straightforward except for the recursion, so its concepts carry over to more complex recursive types.

The Rust Programming Language · Ch.15 Smart Pointers

7

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Understanding the cons list

A pseudocode representation of a cons list containing the list 1, 2, 3, with each pair in parentheses:

• Each item contains two elements: the value of the current item and the next item.
• The last item contains only a value called Nil, without a next item. A cons list is produced by recursively calling the cons function, and the canonical name for the base case of the recursion is Nil.
• This is not the same as the “null” or “nil” concept of Chapter 6, which is an invalid or absent value.

The cons list isn’t commonly used in Rust: most of the time, Vec<T> is a better choice for a list of items. Other, more complex recursive data types are useful in various situations, but starting with the cons list lets us explore how boxes enable a recursive data type without much distraction.

The Rust Programming Language · Ch.15 Smart Pointers

8

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

A first attempt at a cons list enum

Listing 15.2 contains an enum definition for a cons list. This code won’t compile yet, because the List type doesn’t have a known size, as we’ll demonstrate.

Listing 15.2: The first attempt at defining an enum to represent a cons list data structure of i32 values — src/main.rs

Using the List type to store the list 1, 2, 3 would look like the code in Listing 15.3 (next slide).

The Rust Programming Language · Ch.15 Smart Pointers

9

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Storing the list 1, 2, 3 in List

Listing 15.3: Using the List enum to store the list 1, 2, 3 — src/main.rs

• The first Cons value holds 1 and another List value.
• That List value is another Cons value that holds 2 and another List value.
• That one is one more Cons value that holds 3 and a List value, which is finally Nil, the non-recursive variant that signals the end of the list.

If we try to compile this code, we get the error shown in Listing 15.4.

The Rust Programming Language · Ch.15 Smart Pointers

10

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Error: recursive type List has infinite size

Listing 15.4: The error we get when attempting to define a recursive enum

The Rust Programming Language · Ch.15 Smart Pointers

11

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Computing the size of a non-recursive type

The type “has infinite size” because List has a variant that is recursive: it holds another value of itself directly, so Rust can’t figure out how much space a List needs. First, how does Rust size a non-recursive type? Recall the Message enum of Listing 6.2:

Rust goes through each variant to see which needs the most space: Message::Quit needs none, Message::Move needs enough for two i32 values, and so forth. Because only one variant will be used, the most space a Message value needs is the space of its largest variant.

The Rust Programming Language · Ch.15 Smart Pointers

12

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Why a recursive List has infinite size

Contrast the recursive List of Listing 15.2. The compiler looks at the Cons variant, which holds an i32 and a List, so Cons needs the size of an i32 plus the size of a List. To find the size of List, it looks at the variants again, starting with Cons, which holds an i32 and a List — and this process continues infinitely, as Figure 15.1 shows.

Figure 15.1: An infinite List consisting of infinite Cons variants — each Cons box holds an i32 and another, nested Cons, forever.

The Rust Programming Language · Ch.15 Smart Pointers

13

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

Getting a recursive type with a known size

Because Rust can’t figure out how much space to allocate for recursively defined types, the compiler gives an error with this helpful suggestion:

Because a Box<T> is a pointer, Rust always knows how much space it needs: a pointer’s size doesn’t change based on the amount of data it points to. So we can put a Box<T> inside the Cons variant instead of another List value directly; the box points to the next List value, which will be on the heap rather than inside the Cons variant. Conceptually we still have lists holding other lists, but the implementation is now more like placing the items next to one another rather than inside one another.

The Rust Programming Language · Ch.15 Smart Pointers

14

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

A List that uses Box<T> compiles

We change the definition of List from Listing 15.2 and its usage from Listing 15.3 to the code in Listing 15.5, which will compile.

Listing 15.5: The definition of List that uses Box<T> in order to have a known size — src/main.rs

The Cons variant needs the size of an i32 plus the space to store the box’s pointer data; Nil stores no values, so it needs less space on the stack. Any List value now takes up the size of an i32 plus the size of a box’s pointer data. The box breaks the infinite, recursive chain, so the compiler can figure out the size it needs to store a List value.

The Rust Programming Language · Ch.15 Smart Pointers

15

Chapter 15 · 15.1 Using Box<T> to Point to Data on the Heap

A finite Cons, and why Box<T> is a smart pointer

Figure 15.2: A List that is not infinitely sized, because Cons holds a Box (its pointer is a usize-sized value)

Boxes provide only the indirection and heap allocation; they have no other special capabilities, like those of the other smart pointer types — and none of the performance overhead those capabilities incur. So they are useful in cases like the cons list, where indirection is the only feature we need. Chapter 18 shows more use cases for boxes.

Box<T> is a smart pointer because it implements the Deref trait, which allows Box<T> values to be treated like references. When a Box<T> goes out of scope, the heap data it points to is cleaned up as well, because of its Drop implementation. These two traits matter even more for the other smart pointers in this chapter.

The Rust Programming Language · Ch.15 Smart Pointers

16

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Customizing * with the Deref trait

Implementing the Deref trait lets you customize the behavior of the dereference operator. By implementing Deref so that a smart pointer can be treated like a regular reference, you can write code that operates on references and use that code with smart pointers too.

The plan for this section:

1. See how the dereference operator works with regular references.
2. Define a custom type that behaves like Box<T>, and see why the dereference operator doesn’t work like a reference on it.
3. Implement Deref so the smart pointer works in ways similar to references.
4. Look at Rust’s deref coercion feature and how it lets us work with either references or smart pointers.

The Rust Programming Language · Ch.15 Smart Pointers

17

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Following the reference to the value

A regular reference is a type of pointer; think of a pointer as an arrow to a value stored somewhere else. Listing 15.6 creates a reference to an i32 and uses the dereference operator to follow it to the value.

Listing 15.6: Using the dereference operator to follow a reference to an i32 value — src/main.rs

x holds the i32 value 5, and y is a reference to x. We can assert that x equals 5; but to make an assertion about the value in y, we must use *y to follow the reference to the value it points to (hence, dereference), so the compiler can compare the actual value with 5.

The Rust Programming Language · Ch.15 Smart Pointers

18

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Error: assert_eq!(5, y) compares a number with a reference

Writing assert_eq!(5, y); instead gives the error above (its list of types shortened). Comparing a number and a reference to a number isn’t allowed because they’re different types: we must use the dereference operator to follow the reference to the value.

The Rust Programming Language · Ch.15 Smart Pointers

19

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Using Box<T> like a reference

Rewriting Listing 15.6 to use a Box<T> instead of a reference: the dereference operator on the box works the same way as on the reference.

Listing 15.7: Using the dereference operator on a Box<i32> — src/main.rs

The main difference from Listing 15.6: y is now an instance of a box pointing to a copied value of x, rather than a reference pointing to the value of x. In the last assertion we use the dereference operator to follow the box’s pointer in the same way we did when y was a reference. Next: what is special about Box<T> that enables this, by defining our own box type.

The Rust Programming Language · Ch.15 Smart Pointers

20

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Defining our own smart pointer: MyBox<T>

We build a wrapper type similar to the standard library’s Box<T> to see how smart pointer types behave differently from references by default, then add the ability to use the dereference operator.

Box<T> is ultimately defined as a tuple struct with one element, so Listing 15.8 defines MyBox<T> the same way, with a new function to match Box::new.

The Rust Programming Language · Ch.15 Smart Pointers

21

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Trying to dereference MyBox<T>

We add the main function of Listing 15.7 to Listing 15.8 and change it to use MyBox<T> instead of Box<T>. The code in Listing 15.9 won’t compile, because Rust doesn’t know how to dereference MyBox.

Listing 15.9: Attempting to use MyBox<T> in the same way we used references and Box<T> — src/main.rs

The two panels are one file: the definitions (left) followed by main (right).

The Rust Programming Language · Ch.15 Smart Pointers

22

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Error: MyBox cannot be dereferenced

Here’s the resultant compilation error:

Our MyBox<T> type can’t be dereferenced because we haven’t implemented that ability on our type. To enable dereferencing with the * operator, we implement the Deref trait.

The Rust Programming Language · Ch.15 Smart Pointers

23

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Implementing the Deref trait

To implement a trait we provide implementations for its required methods (“Implementing a Trait on a Type,” Chapter 10). The standard library’s Deref trait requires one method named deref that borrows self and returns a reference to the inner data. Listing 15.10 adds an implementation of Deref to the definition of MyBox<T>.

The Rust Programming Language · Ch.15 Smart Pointers

24

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

What *y really runs

The body of deref is &self.0, so deref returns a reference to the value we want to access with the * operator (.0 accesses the first value in a tuple struct — “Creating Different Types with Tuple Structs,” Chapter 5). The main function of Listing 15.9 that calls * on the MyBox<T> value now compiles, and the assertions pass!

Without Deref, the compiler can only dereference & references. The deref method gives it the ability to take a value of any type that implements Deref and call deref to get a reference it knows how to dereference. When we entered *y in Listing 15.9, behind the scenes Rust actually ran this code:

Rust substitutes the * operator with a call to the deref method and then a plain dereference, so we don’t have to think about whether or not to call deref. This lets us write code that functions identically whether we have a regular reference or a type that implements Deref.

The Rust Programming Language · Ch.15 Smart Pointers

25

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Why deref returns a reference, and substitutes only once

A reference, because of ownership

The reason deref returns a reference to a value — and that the plain dereference outside the parentheses in *(y.deref()) is still necessary — has to do with the ownership system. If deref returned the value directly instead of a reference to it, the value would be moved out of self. We don’t want to take ownership of the inner value inside MyBox<T> in this case, or in most cases where we use the dereference operator.

One substitution per *

Each time we use a * in our code, it is replaced with a call to deref and then a call to the * operator just once. Because the substitution does not recurse infinitely, we end up with data of type i32, which matches the 5 in assert_eq! in Listing 15.9.

The Rust Programming Language · Ch.15 Smart Pointers

26

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Deref coercion in functions and methods

• It is a convenience Rust performs on arguments to functions and methods, and works only on types that implement Deref.
• It happens automatically when we pass a reference to a particular type’s value as an argument to a function or method whose parameter type doesn’t match it.
• A sequence of calls to the deref method converts the type we provided into the type the parameter needs.

Deref coercion was added to Rust so that programmers writing function and method calls don’t need to add as many explicit references and dereferences with & and *. It also lets us write more code that can work for either references or smart pointers.

The Rust Programming Language · Ch.15 Smart Pointers

27

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Deref coercion in action

We use MyBox<T> from Listing 15.8 and its Deref implementation from Listing 15.10. Listing 15.11 defines a function that has a string slice parameter.

Listing 15.11: A hello function that has the parameter name of type &str — src/main.rs

We can call hello with a string slice, such as hello("Rust");. Deref coercion makes it possible to call it with a reference to a value of type MyBox<String>, too:

Listing 15.12: Calling hello with a reference to a MyBox<String> value, which works because of deref coercion — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

28

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

What deref coercion saves us from writing

In Listing 15.12, &m is a reference to a MyBox<String>. Because MyBox<T> implements Deref (Listing 15.10), Rust can turn &MyBox<String> into &String by calling deref. The standard library implements Deref on String to return a string slice (see the API documentation for Deref), so Rust calls deref again to turn &String into &str, which matches the definition of hello.

Without deref coercion, we would have to write the code in Listing 15.13 to call hello with a value of type &MyBox<String>.

Listing 15.13: The code we would have to write if Rust didn’t have deref coercion — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

29

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Reading Listing 15.13, and the cost of coercion

• (*m) dereferences the MyBox<String> into a String.
• The & and [..] then take a string slice of the String that is equal to the whole string, to match the signature of hello.

This code without deref coercions is harder to read, write, and understand with all of these symbols involved. Deref coercion lets Rust handle these conversions for us automatically.

When the Deref trait is defined for the types involved, Rust analyzes the types and uses Deref::deref as many times as necessary to get a reference that matches the parameter’s type. The number of insertions is resolved at compile time, so there is no runtime penalty for taking advantage of deref coercion!

The Rust Programming Language · Ch.15 Smart Pointers

30

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Deref coercion with mutable references

Just as the Deref trait overrides the * operator on immutable references, the DerefMut trait overrides the * operator on mutable references. Rust does deref coercion when it finds types and trait implementations in three cases:

Table 15.1: The three cases of deref coercion

The first two cases are the same except that the second implements mutability. The first says that if you have a &T, and T implements Deref to some type U, you can get a &U transparently. The second says the same deref coercion happens for mutable references.

The Rust Programming Language · Ch.15 Smart Pointers

31

Chapter 15 · 15.2 Treating Smart Pointers Like Regular References

Mutable to immutable, never the reverse

The third case is trickier: Rust will also coerce a mutable reference to an immutable one. But the reverse is not possible: immutable references will never coerce to mutable references.

• Because of the borrowing rules, if you have a mutable reference, that mutable reference must be the only reference to that data (otherwise, the program wouldn’t compile).
• So converting one mutable reference to one immutable reference will never break the borrowing rules.
• Converting an immutable reference to a mutable reference would require that the initial immutable reference is the only immutable reference to that data — but the borrowing rules don’t guarantee that.
• Therefore, Rust can’t assume that converting an immutable reference to a mutable reference is possible.

The Rust Programming Language · Ch.15 Smart Pointers

32

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

The Drop trait

The second trait important to the smart pointer pattern is Drop, which lets you customize what happens when a value is about to go out of scope. You can implement Drop on any type, and that code can be used to release resources like files or network connections.

Drop is introduced with smart pointers because its functionality is almost always used when implementing one. For example, when a Box<T> is dropped, it deallocates the space on the heap that the box points to.

In some languages, for some types, the programmer must call code to free memory or resources every time they finish using an instance — for example file handles, sockets, and locks. If they forget, the system might become overloaded and crash. In Rust, you can specify that a particular bit of code be run whenever a value goes out of scope, and the compiler inserts this code automatically. So you don’t need to place cleanup code everywhere an instance of a particular type is finished with — and you still won’t leak resources!

The Rust Programming Language · Ch.15 Smart Pointers

33

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Implementing Drop on CustomSmartPointer

You specify the code to run when a value goes out of scope by implementing Drop, which requires one method named drop that takes a mutable reference to self. To see when Rust calls drop, we implement it with println! statements for now.

Listing 15.14’s CustomSmartPointer struct has only one custom functionality: it prints Dropping CustomSmartPointer! when the instance goes out of scope, showing when Rust runs drop.

Listing 15.14: A CustomSmartPointer struct that implements the Drop trait where we would put our cleanup code — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

34

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Creating two CustomSmartPointers

Listing 15.14 (continued): main — src/main.rs

The Drop trait is included in the prelude, so we don’t need to bring it into scope. We implement Drop on CustomSmartPointer with a drop method that calls println!. The body of drop is where you would place any logic you want to run when an instance of your type goes out of scope; here we print text to demonstrate visually when Rust calls drop.

The Rust Programming Language · Ch.15 Smart Pointers

35

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Drop runs automatically, in reverse order

In main, we create two instances of CustomSmartPointer and print CustomSmartPointers created. At the end of main the instances go out of scope, and Rust calls the code in drop, printing our final messages — we didn’t need to call drop explicitly. Running the program prints:

Rust automatically called drop when our instances went out of scope. Variables are dropped in the reverse order of their creation, so d was dropped before c. The print message is only a visual guide to how drop works; usually you would specify the cleanup code your type needs to run.

The Rust Programming Language · Ch.15 Smart Pointers

36

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Cleaning up early: calling drop manually fails

It’s not straightforward to disable the automatic drop, and usually unnecessary: the whole point of Drop is that it’s taken care of automatically. Occasionally you might want to clean up a value early — e.g., with smart pointers that manage locks, forcing the drop that releases the lock so other code in the same scope can acquire it. Rust doesn’t let you call Drop’s drop method manually; you call the standard library’s std::mem::drop function instead.

Listing 15.15: Attempting to call the drop method from the Drop trait manually to clean up early — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

37

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Error: explicit use of destructor method

Compiling Listing 15.15 gives this error:

The Rust Programming Language · Ch.15 Smart Pointers

38

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Destructors, double frees, and std::mem::drop

The error states that we’re not allowed to explicitly call drop. It uses the term destructor:

• Rust doesn’t let us call drop explicitly because it would still automatically call drop on the value at the end of main. That would be a double free error: Rust trying to clean up the same value twice.
• We can’t disable the automatic insertion of drop, and we can’t call the drop method explicitly. So, to force a value to be cleaned up early, we use the std::mem::drop function.
• std::mem::drop is different from the drop method in the Drop trait: we call it passing as an argument the value we want to force-drop. It is in the prelude, so main can call it directly, as in Listing 15.16.

The Rust Programming Language · Ch.15 Smart Pointers

39

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

Forcing an early drop with std::mem::drop

Listing 15.16: Calling std::mem::drop to explicitly drop a value before it goes out of scope — src/main.rs

Running this code prints:

The Rust Programming Language · Ch.15 Smart Pointers

40

Chapter 15 · 15.3 Running Code on Cleanup with the Drop Trait

What the early drop shows, and what Drop gives us

The text Dropping CustomSmartPointer with data `some data`! is printed between CustomSmartPointer created and CustomSmartPointer dropped before the end of main, showing that the drop method code is called to drop c at that point.

• Code in a Drop implementation can make cleanup convenient and safe in many ways: for instance, you could use it to create your own memory allocator!
• With the Drop trait and Rust’s ownership system, you don’t have to remember to clean up, because Rust does it automatically.
• You also don’t have to worry about accidentally cleaning up values still in use: the ownership system that makes sure references are always valid also ensures that drop gets called only once, when the value is no longer being used.

Having examined Box<T> and some characteristics of smart pointers, we turn to a few other smart pointers defined in the standard library.

The Rust Programming Language · Ch.15 Smart Pointers

41

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Multiple owners and reference counting

In the majority of cases, ownership is clear: you know exactly which variable owns a given value. But a single value might have multiple owners. In graph data structures, for example, multiple edges might point to the same node, and that node is conceptually owned by all of the edges pointing to it; it shouldn’t be cleaned up unless no edges point to it, so it has no owners.

The Rust Programming Language · Ch.15 Smart Pointers

42

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

When to use Rc<T>

We use Rc<T> when we want to allocate some data on the heap for multiple parts of our program to read, and we can’t determine at compile time which part will finish using the data last. If we knew which part would finish last, we could just make that part the data’s owner, and the normal ownership rules enforced at compile time would take effect.

Sharing data

Back to the cons list of Listing 15.5, defined with Box<T>. This time we create two lists that both share ownership of a third list, conceptually as in Figure 15.3 (next slide).

The Rust Programming Language · Ch.15 Smart Pointers

43

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Two lists sharing a third

Figure 15.3: Two lists, b and c, sharing ownership of a third list, a

We create list a that contains 5 and then 10. Then we make two more lists: b that starts with 3 and c that starts with 4. Both b and c then continue on to the first list a, containing 5 and 10: both lists share it. Implementing this with our Box<T>-based List won’t work, as Listing 15.17 shows.

The Rust Programming Language · Ch.15 Smart Pointers

44

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Trying to share a list with Box<T>

Listing 15.17: Demonstrating that we’re not allowed to have two lists using Box<T> that try to share ownership of a third list — src/main.rs

When we compile this code, we get the error on the next slide.

The Rust Programming Language · Ch.15 Smart Pointers

45

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Error: use of moved value a

The note: block that suggests implementing Clone for List is shortened here.

The Rust Programming Language · Ch.15 Smart Pointers

46

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Why it fails, and the Rc<T> fix

The Cons variants own the data they hold, so when we create the b list, a is moved into b and b owns a. Then, when we try to use a again to create c, we’re not allowed to, because a has been moved.

We could change Cons to hold references instead, but then we would have to specify lifetime parameters — specifying that every element in the list lives at least as long as the entire list. That is the case for the elements and lists in Listing 15.17, but not in every scenario.

Instead, we change List to use Rc<T> in place of Box<T> (Listing 15.18). Each Cons variant now holds a value and an Rc<T> pointing to a List. When we create b, instead of taking ownership of a, we clone the Rc<List> that a holds, increasing the number of references from one to two and letting a and b share ownership of the data in that Rc<List>. Cloning a again when creating c increases it from two to three. Every Rc::clone increases the reference count, and the data won’t be cleaned up unless there are zero references to it.

The Rust Programming Language · Ch.15 Smart Pointers

47

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

A List that uses Rc<T>

Listing 15.18: A definition of List that uses Rc<T> — src/main.rs

A use statement brings Rc<T> into scope, because it’s not in the prelude. In main, we store the list holding 5 and 10 in a new Rc<List> in a. To create b and c, we call Rc::clone, passing a reference to the Rc<List> in a.

The Rust Programming Language · Ch.15 Smart Pointers

48

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Rc::clone versus a deep clone

We could have called a.clone() rather than Rc::clone(&a), but Rust’s convention is to use Rc::clone in this case:

• The implementation of Rc::clone doesn’t make a deep copy of all the data, as most types’ clone implementations do. It only increments the reference count, which doesn’t take much time; deep copies of data can take a lot of time.
• Using Rc::clone for reference counting visually distinguishes the deep-copy kinds of clones from the kinds that increase the reference count. When looking for performance problems, we only need to consider the deep-copy clones and can disregard calls to Rc::clone.

Cloning to increase the reference count

Let’s change Listing 15.18 so we can see the reference counts change as we create and drop references to the Rc<List> in a. In Listing 15.19, main gets an inner scope around list c, so we can see how the count changes when c goes out of scope.

The Rust Programming Language · Ch.15 Smart Pointers

49

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Printing the reference count

Listing 15.19: Printing the reference count — src/main.rs

At each point where the count changes, we print it with Rc::strong_count. It is named strong_count rather than count because Rc<T> also has a weak_count, explained in “Preventing Reference Cycles Using Weak<T>” (15.6).

The Rust Programming Language · Ch.15 Smart Pointers

50

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Watching the count go up and down

Listing 15.19 prints the following:

• The Rc<List> in a has an initial reference count of 1; each time we call clone, the count goes up by 1.
• When c goes out of scope, the count goes down by 1. No function call is needed to decrease it, unlike the Rc::clone call that increases it: the Drop implementation decreases the reference count automatically when an Rc<T> value goes out of scope.

The Rust Programming Language · Ch.15 Smart Pointers

51

Chapter 15 · 15.4 Rc<T>, the Reference-Counted Smart Pointer

Shared ownership, read-only

What we can’t see in this example: when b and then a go out of scope at the end of main, the count is 0, and the Rc<List> is cleaned up completely. Rc<T> allows a single value to have multiple owners, and the count ensures that the value remains valid as long as any of the owners still exist.

Via immutable references, Rc<T> lets you share data between multiple parts of your program for reading only. If it allowed multiple mutable references too, you might violate one of the borrowing rules of Chapter 4: multiple mutable borrows to the same place can cause data races and inconsistencies.

But being able to mutate data is very useful! The next section discusses the interior mutability pattern and the RefCell<T> type, which you can use together with an Rc<T> to work with this immutability restriction.

The Rust Programming Language · Ch.15 Smart Pointers

52

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

The interior mutability pattern

To mutate data, the pattern uses unsafe code inside a data structure to bend Rust’s usual rules that govern mutation and borrowing. Unsafe code indicates to the compiler that we’re checking the rules manually instead of relying on the compiler to check them for us (Chapter 20 discusses unsafe code).

We can use types that follow the interior mutability pattern only when we can ensure that the borrowing rules will be followed at runtime, even though the compiler can’t guarantee that. The unsafe code involved is then wrapped in a safe API, and the outer type is still immutable.

We explore this concept through the RefCell<T> type, which follows the interior mutability pattern.

The Rust Programming Language · Ch.15 Smart Pointers

53

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Enforcing borrowing rules at runtime

Unlike Rc<T>, the RefCell<T> type represents single ownership over the data it holds. So what makes it different from a type like Box<T>? Recall the borrowing rules of Chapter 4:

• At any given time, you can have either one mutable reference or any number of immutable references (but not both).
• References must always be valid.

With references and Box<T>, these invariants are enforced at compile time; break them and you get a compiler error. With RefCell<T>, they are enforced at runtime; break them and your program will panic and exit.

Checking at compile time catches errors sooner in the development process, with no impact on runtime performance, because all the analysis is completed beforehand. That makes it the best choice in the majority of cases, which is why it is Rust’s default.

The Rust Programming Language · Ch.15 Smart Pointers

54

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Why check at runtime: a conservative compiler

Checking the borrowing rules at runtime instead allows certain memory-safe scenarios that the compile-time checks would have disallowed. Static analysis, like the Rust compiler, is inherently conservative: some properties of code are impossible to detect by analyzing the code. The most famous example is the Halting Problem, which is beyond the scope of the book but an interesting topic to research.

Because some analysis is impossible, if the compiler can’t be sure the code complies with the ownership rules, it might reject a correct program. If Rust accepted an incorrect program, users couldn’t trust its guarantees; if it rejects a correct program, the programmer is inconvenienced, but nothing catastrophic can occur. RefCell<T> is useful when you’re sure your code follows the borrowing rules but the compiler is unable to understand and guarantee that.

The Rust Programming Language · Ch.15 Smart Pointers

55

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Choosing Box<T>, Rc<T>, or RefCell<T>

A recap of the reasons to choose each type:

Table 15.2: Ownership and borrowing of the three smart pointers

Because RefCell<T> allows mutable borrows checked at runtime, you can mutate the value inside the RefCell<T> even when the RefCell<T> is immutable. Mutating the value inside an immutable value is the interior mutability pattern. Next: a situation where it is useful, and how it’s possible.

The Rust Programming Language · Ch.15 Smart Pointers

56

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Using interior mutability

A consequence of the borrowing rules is that when you have an immutable value, you can’t borrow it mutably. For example, this code won’t compile:

Compiling it gives the error on the next slide.

Yet sometimes it would be useful for a value to mutate itself in its methods but appear immutable to other code: code outside the value’s methods could not mutate it. RefCell<T> is one way to get this interior mutability — but it doesn’t get around the borrowing rules completely. The borrow checker allows the interior mutability, and the borrowing rules are checked at runtime instead: violate them and you get a panic! instead of a compiler error.

The Rust Programming Language · Ch.15 Smart Pointers

57

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Error: cannot borrow x as mutable

Borrowing the immutable x mutably gives this error:

The Rust Programming Language · Ch.15 Smart Pointers

58

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Testing with mock objects

A practical example where RefCell<T> mutates an immutable value, and why that is useful. Sometimes during testing a programmer uses a type in place of another type, to observe particular behavior and assert that it’s implemented correctly.

Rust doesn’t have objects in the same sense as other languages, and its standard library has no built-in mock object functionality as some other languages do. However, you can definitely create a struct that serves the same purposes as a mock object.

The Rust Programming Language · Ch.15 Smart Pointers

59

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

The scenario: a quota-tracking library

We’ll create a library that tracks a value against a maximum value and sends messages based on how close to the maximum the current value is. It could be used, for example, to keep track of a user’s quota for the number of API calls they’re allowed to make.

• The library only provides the functionality of tracking how close to the maximum a value is, and what the messages should be at what times.
• Applications that use it are expected to provide the mechanism for sending the messages: show the message to the user directly, send an email, send a text message, or something else. The library doesn’t need to know that detail.
• All it needs is something that implements a trait we provide, called Messenger.

Listing 15.20 (next three slides) shows the library code.

The Rust Programming Language · Ch.15 Smart Pointers

60

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

The Messenger trait and LimitTracker struct

Listing 15.20: A library to keep track of how close a value is to a maximum value and warn when the value is at certain levels — src/lib.rs

One important part of this code is that the Messenger trait has one method, send, that takes an immutable reference to self and the text of the message. This trait is the interface our mock object needs to implement so that the mock can be used in the same way a real object is.

The Rust Programming Language · Ch.15 Smart Pointers

61

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

LimitTracker::new

Listing 15.20 (continued): the impl block and its constructor — src/lib.rs

A new LimitTracker holds a reference to some Messenger, a max, and a value starting at 0. The impl block continues with set_value on the next slide.

The Rust Programming Language · Ch.15 Smart Pointers

62

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

LimitTracker::set_value

Listing 15.20 (continued): set_value, the end of the impl block — src/lib.rs

The Rust Programming Language · Ch.15 Smart Pointers

63

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

What we want to test, and the mock we need

The other important part: we want to test the behavior of set_value on LimitTracker. We can change what we pass in for the value parameter, but set_value doesn’t return anything for us to make assertions on. We want to be able to say: if we create a LimitTracker with something that implements Messenger and a particular value for max, the messenger is told to send the appropriate messages when we pass different numbers for value.

We need a mock object that, instead of sending an email or text message when we call send, only keeps track of the messages it’s told to send. Then we can create a new mock object, create a LimitTracker that uses it, call set_value on the LimitTracker, and check that the mock object has the messages we expect.

Listing 15.21 attempts to implement such a mock object — but the borrow checker won’t allow it.

The Rust Programming Language · Ch.15 Smart Pointers

64

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

A first MockMessenger

Listing 15.21: An attempt to implement a MockMessenger that isn’t allowed by the borrow checker — src/lib.rs

The Rust Programming Language · Ch.15 Smart Pointers

65

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Implementing Messenger and the test

Listing 15.21 (continued) — src/lib.rs

The Rust Programming Language · Ch.15 Smart Pointers

66

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

How the mock and the test work

• MockMessenger has a sent_messages field, a Vec of String values, to keep track of the messages it’s told to send.
• The associated function new conveniently creates MockMessenger values that start with an empty list of messages.
• We implement Messenger for MockMessenger so we can give one to a LimitTracker. Its send takes the message passed in and stores it in sent_messages.

The test checks what happens when the LimitTracker is told to set value to more than 75 percent of max. We create a new MockMessenger (empty list of messages), then a new LimitTracker given a reference to it and a max of 100. We call set_value with 80, more than 75 percent of 100, then assert that the mock’s list of messages now has one message in it.

However, there’s one problem with this test, shown on the next slide.

The Rust Programming Language · Ch.15 Smart Pointers

67

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Error: self.sent_messages is behind a & reference

The Rust Programming Language · Ch.15 Smart Pointers

68

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Interior mutability to the rescue

We can’t modify the MockMessenger to keep track of the messages, because the send method takes an immutable reference to self.

We also can’t take the error text’s suggestion to use &mut self in both the impl method and the trait definition: we do not want to change the Messenger trait solely for the sake of testing. Instead, we need a way to make our test code work correctly with our existing design.

The Rust Programming Language · Ch.15 Smart Pointers

69

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

MockMessenger with a RefCell

Listing 15.22: Using RefCell<T> to mutate an inner value while the outer value is considered immutable — src/lib.rs

The Rust Programming Language · Ch.15 Smart Pointers

70

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

borrow_mut in send, borrow in the assertion

Listing 15.22 (continued) — src/lib.rs

The Rust Programming Language · Ch.15 Smart Pointers

71

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

What changed in Listing 15.22

1. The sent_messages field is now of type RefCell<Vec<String>> instead of Vec<String>. The new function creates a new RefCell<Vec<String>> instance around the empty vector.
2. In send, the first parameter is still an immutable borrow of self, which matches the trait definition. We call borrow_mut on the RefCell<Vec<String>> in self.sent_messages to get a mutable reference to the value inside it, the vector. Then we call push on that mutable reference to keep track of the messages sent during the test.
3. In the assertion, to see how many items are in the inner vector, we call borrow on the RefCell<Vec<String>> to get an immutable reference to the vector.

Now that you’ve seen how to use RefCell<T>, let’s dig into how it works!

The Rust Programming Language · Ch.15 Smart Pointers

72

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Tracking borrows at runtime

To create immutable and mutable references we use the & and &mut syntax. With RefCell<T>, we use the borrow and borrow_mut methods, part of its safe API.

The RefCell<T> keeps track of how many Ref<T> and RefMut<T> smart pointers are currently active. Every call to borrow increases its count of active immutable borrows; when a Ref<T> goes out of scope, the count goes down by 1. Just like the compile-time borrowing rules, RefCell<T> lets us have many immutable borrows or one mutable borrow at any point in time.

If we violate these rules, rather than a compiler error, the implementation of RefCell<T> panics at runtime. Listing 15.23 modifies send from Listing 15.22 to deliberately create two mutable borrows active for the same scope.

The Rust Programming Language · Ch.15 Smart Pointers

73

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Two mutable borrows in the same scope

Listing 15.23: Creating two mutable references in the same scope to see that RefCell<T> will panic — src/lib.rs

We create a variable one_borrow for the RefMut<T> smart pointer returned from borrow_mut, then another mutable borrow the same way in two_borrow. This makes two mutable references in the same scope, which isn’t allowed. When we run the tests for our library, the code in Listing 15.23 compiles without any errors, but the test fails (next slides).

The Rust Programming Language · Ch.15 Smart Pointers

74

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

The test panics at runtime

Output of cargo test for Listing 15.23 (part 1 of 2):

The Rust Programming Language · Ch.15 Smart Pointers

75

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

The trade-offs of runtime borrow checking

Output of cargo test (part 2 of 2):

The code panicked with the message already borrowed: BorrowMutError: this is how RefCell<T> handles violations of the borrowing rules at runtime.

Catching borrowing errors at runtime means finding mistakes later — possibly not until production — plus a small runtime performance penalty for tracking borrows. But RefCell<T> let us write a mock that records the messages it sees while used where only immutable values are allowed: despite its trade-offs, more functionality than regular references provide.

The Rust Programming Language · Ch.15 Smart Pointers

76

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Multiple owners of mutable data: Rc<RefCell<T>>

A common way to use RefCell<T> is in combination with Rc<T>. Rc<T> lets data have multiple owners but gives only immutable access; an Rc<T> that holds a RefCell<T> gives a value that can have multiple owners and that you can mutate! In Listing 15.18’s cons list, Rc<T> holds only immutable values, so we can’t change any list value once created. Adding RefCell<T> to the Cons definition lets us modify the value stored in all the lists:

Listing 15.24: Using Rc<RefCell<i32>> to create a List that we can mutate — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

77

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

Mutating a value shared by three lists

Listing 15.24 (continued): main — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

78

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

How Listing 15.24 works

• We create a value that is an instance of Rc<RefCell<i32>> and store it in a variable named value, so we can access it directly later.
• We create a List in a with a Cons variant that holds value. We clone value so that both a and value own the inner 5, rather than transferring ownership from value to a or having a borrow from value.
• We wrap the list a in an Rc<T> so that lists b and c can both refer to a, as in Listing 15.18.
• To add 10 to the value in value, we call borrow_mut on it. This uses automatic dereferencing (“Where’s the -> Operator?”, Chapter 5) to dereference the Rc<T> to the inner RefCell<T>. borrow_mut returns a RefMut<T> smart pointer; we use the dereference operator on it and change the inner value.

The Rust Programming Language · Ch.15 Smart Pointers

79

Chapter 15 · 15.5 RefCell<T> and the Interior Mutability Pattern

All three lists see 15

When we print a, b, and c, they all have the modified value of 15 rather than 5:

This technique is pretty neat! With RefCell<T> we have an outwardly immutable List value, yet we can use the methods on RefCell<T> that provide access to its interior mutability to modify our data when we need to. The runtime checks of the borrowing rules protect us from data races, and it’s sometimes worth trading a bit of speed for this flexibility in our data structures.

The Rust Programming Language · Ch.15 Smart Pointers

80

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Memory leaks are memory safe

Rust’s memory safety guarantees make it difficult, but not impossible, to accidentally create a memory leak. Preventing memory leaks entirely is not one of Rust’s guarantees, meaning memory leaks are memory safe in Rust. Using Rc<T> and RefCell<T>, it’s possible to create references where items refer to each other in a cycle. This creates memory leaks, because the reference count of each item in the cycle will never reach 0, and the values will never be dropped.

Creating a reference cycle

To see how a reference cycle might happen and how to prevent it, we start with the definition of the List enum and a tail method in Listing 15.25.

The Rust Programming Language · Ch.15 Smart Pointers

81

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

A List whose tail can be changed

Listing 15.25: A cons list definition that holds a RefCell<T> so that we can modify what a Cons variant is referring to — src/main.rs

Another variation of the List definition from Listing 15.5: the second element in Cons is now RefCell<Rc<List>>. Instead of modifying the i32 value as in Listing 15.24, we want to modify the List value a Cons variant is pointing to. The tail method makes it convenient to access the second item if we have a Cons variant.

The Rust Programming Language · Ch.15 Smart Pointers

82

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Building lists a and b

Listing 15.26 adds a main function that uses the definitions in Listing 15.25. It creates a list in a and a list in b that points to the list in a. Then it modifies the list in a to point to b, creating a reference cycle. println! statements along the way show the reference counts at various points.

Listing 15.26: Creating a reference cycle of two List values pointing to each other — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

83

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Pointing a back at b

Listing 15.26 (continued) — src/main.rs

We create an Rc<List> instance holding a List value in a, with an initial list of 5, Nil. We then create an Rc<List> instance holding another List value in b that contains the value 10 and points to the list in a.

The Rust Programming Language · Ch.15 Smart Pointers

84

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Creating the cycle, and the counts it leaves

We modify a so that it points to b instead of Nil, creating a cycle: the tail method gets a reference to the RefCell<Rc<List>> in a, which we put in link. Then borrow_mut on the RefCell<Rc<List>> changes the value inside from an Rc<List> that holds Nil to the Rc<List> in b.

Running this code, with the last println! commented out for the moment, gives:

The Rust Programming Language · Ch.15 Smart Pointers

85

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Why the cycle is never cleaned up

After we change the list in a to point to b, the reference count of the Rc<List> instances in both a and b is 2. At the end of main, Rust drops b, decreasing the count of the b Rc<List> from 2 to 1; its heap memory isn’t dropped, because the count is 1, not 0. Then Rust drops a, decreasing the count of the a Rc<List> from 2 to 1 as well; it can’t be dropped either, because the other Rc<List> instance still refers to it. The memory allocated to the list remains uncollected forever (Figure 15.4).

Figure 15.4: A reference cycle of lists a and b pointing to each other: 5 points to 10, and 10 points back to 5

The Rust Programming Language · Ch.15 Smart Pointers

86

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Consequences, and how to avoid cycles

If you uncomment the last println! and run the program, Rust tries to print the cycle — a pointing to b pointing to a, and so forth — until it overflows the stack.

Here the consequences aren’t very dire: right after we create the cycle, the program ends. But a more complex program that allocated lots of memory in a cycle and held onto it for a long time would use more memory than it needed, and might overwhelm the system, running out of available memory.

Creating reference cycles is not easily done, but not impossible. If you have RefCell<T> values containing Rc<T> values, or similar nested combinations of interior mutability and reference counting, you must ensure you don’t create cycles; you can’t rely on Rust to catch them. A cycle is a logic bug, to minimize with automated tests, code reviews, and other software development practices.

Another solution is reorganizing data structures so that some references express ownership and some don’t: cycles can then mix ownership and non-ownership relationships, and only ownership relationships affect whether a value can be dropped. In Listing 15.25, Cons variants must always own their list, so that isn’t possible; a graph of parent and child nodes shows when non-ownership relationships are appropriate.

The Rust Programming Language · Ch.15 Smart Pointers

87

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Preventing reference cycles using Weak<T>

So far, calling Rc::clone increases the strong_count of an Rc<T> instance, and an Rc<T> instance is only cleaned up if its strong_count is 0. You can also create a weak reference to the value within an Rc<T> instance by calling Rc::downgrade and passing a reference to the Rc<T>.

Weak references won’t cause a reference cycle, because any cycle involving some weak references will be broken once the strong reference count of the values involved is 0.

The Rust Programming Language · Ch.15 Smart Pointers

88

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Weak<T>, weak_count, and upgrade

Calling Rc::downgrade gives a smart pointer of type Weak<T>. Instead of increasing the strong_count of the Rc<T> instance by 1, it increases the weak_count by 1. Rc<T> uses weak_count to keep track of how many Weak<T> references exist, similar to strong_count. The difference: weak_count doesn’t need to be 0 for the Rc<T> instance to be cleaned up.

Because the value a Weak<T> references might have been dropped, to do anything with it you must make sure the value still exists. Call the upgrade method on a Weak<T> instance, which returns an Option<Rc<T>>: Some if the Rc<T> value has not been dropped yet, and None if it has. Because upgrade returns an Option<Rc<T>>, Rust ensures that both the Some and None cases are handled, and there won’t be an invalid pointer.

As an example, rather than a list whose items know only about the next item, we create a tree whose items know about their child items and their parent items.

The Rust Programming Language · Ch.15 Smart Pointers

89

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Creating a tree data structure

To start, we build a tree with nodes that know about their child nodes: a struct named Node that holds its own i32 value as well as references to its child Node values.

src/main.rs

We want a Node to own its children, and to share that ownership with variables so we can access each Node in the tree directly. So the Vec<T> items are values of type Rc<Node>. We also want to modify which nodes are children of another node, so children has a RefCell<T> around the Vec<Rc<Node>>.

The Rust Programming Language · Ch.15 Smart Pointers

90

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

A leaf and a branch

Using this struct definition, we create one Node instance named leaf with the value 3 and no children, and another named branch with the value 5 and leaf as one of its children.

Listing 15.27: Creating a leaf node with no children and a branch node with leaf as one of its children — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

91

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Adding a reference from a child to its parent

In Listing 15.27 we clone the Rc<Node> in leaf and store it in branch, so the Node in leaf now has two owners: leaf and branch. We can get from branch to leaf through branch.children, but there’s no way to get from leaf to branch: leaf has no reference to branch and doesn’t know they’re related. We want leaf to know that branch is its parent.

So we add a parent field to Node. The trouble is deciding its type. It can’t contain an Rc<T>: that would create a reference cycle, with leaf.parent pointing to branch and branch.children pointing to leaf, and their strong_count values would never be 0.

Thinking about the relationships another way: a parent node should own its children — if a parent is dropped, its child nodes should be dropped as well. But a child should not own its parent — if we drop a child node, the parent should still exist. This is a case for weak references!

The Rust Programming Language · Ch.15 Smart Pointers

92

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

A parent field of type RefCell<Weak<Node>>

Instead of Rc<T>, the type of parent uses Weak<T>, specifically a RefCell<Weak<Node>>. The Node struct definition now looks like this:

src/main.rs

A node can now refer to its parent node but doesn’t own its parent. Listing 15.28 updates main to use this new definition, so the leaf node has a way to refer to its parent, branch.

The Rust Programming Language · Ch.15 Smart Pointers

93

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

leaf gets a weak reference to branch

Listing 15.28: A leaf node with a weak reference to its parent node, branch — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

94

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Before the link: leaf parent = None

Listing 15.28 (continued) — src/main.rs

Creating the leaf node looks like Listing 15.27 except for the parent field: leaf starts out without a parent, so we create a new, empty Weak<Node> reference instance.

At this point, trying to get a reference to the parent of leaf with the upgrade method gives a None value, as the output of the first println! shows:

The Rust Programming Language · Ch.15 Smart Pointers

95

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

After the link: leaf can reach its parent

The branch node also gets a new Weak<Node> reference in its parent field, because branch doesn’t have a parent node; leaf is still one of its children. With the Node instance in branch, we give leaf a Weak<Node> reference to its parent: borrow_mut on the RefCell<Weak<Node>> in leaf.parent, then Rc::downgrade to create a Weak<Node> reference to branch from the Rc<Node> in branch.

Printing the parent of leaf again now gives a Some variant holding branch: leaf can access its parent! Printing leaf also avoids the cycle that ended in a stack overflow in Listing 15.26; the Weak<Node> references are printed as (Weak):

The lack of infinite output indicates that this code didn’t create a reference cycle. We can also tell this from the values of Rc::strong_count and Rc::weak_count.

The Rust Programming Language · Ch.15 Smart Pointers

96

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Visualizing strong_count and weak_count

To see how strong_count and weak_count of the Rc<Node> instances change, Listing 15.29 moves the creation of branch into a new inner scope, so we see what happens when branch is created and then dropped when it goes out of scope.

Listing 15.29: Creating branch in an inner scope and examining strong and weak reference counts — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

97

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

branch lives in an inner scope

Listing 15.29 (continued) — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

98

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Counts inside and after the scope

Listing 15.29 (continued) — src/main.rs

The Rust Programming Language · Ch.15 Smart Pointers

99

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

Reading the counts

• After leaf is created, its Rc<Node> has a strong count of 1 and a weak count of 0.
• In the inner scope, we create branch and associate it with leaf. The Rc<Node> in branch then has a strong count of 1 and a weak count of 1 (for leaf.parent pointing to branch with a Weak<Node>).
• The counts in leaf show a strong count of 2, because branch now has a clone of the Rc<Node> of leaf stored in branch.children, but still a weak count of 0.
• When the inner scope ends, branch goes out of scope and the strong count of its Rc<Node> decreases to 0, so its Node is dropped. The weak count of 1 from leaf.parent has no bearing on whether or not Node is dropped, so we don’t get any memory leaks!

The Rust Programming Language · Ch.15 Smart Pointers

100

Chapter 15 · 15.6 Reference Cycles Can Leak Memory

After the scope: back to one owner

Table 15.3: Reference counts printed by Listing 15.29

Accessing the parent of leaf after the end of the scope gives None again. At the end of the program, the Rc<Node> in leaf has a strong count of 1 and a weak count of 0, because the variable leaf is again the only reference to the Rc<Node>.

All of the logic that manages the counts and value dropping is built into Rc<T> and Weak<T> and their implementations of the Drop trait. By specifying in the definition of Node that the relationship from a child to its parent should be a Weak<T> reference, parent nodes can point to child nodes and vice versa without creating a reference cycle and memory leaks.

The Rust Programming Language · Ch.15 Smart Pointers

101

Chapter 15 · Summary

Chapter summary

Smart pointers make different guarantees and trade-offs from those Rust makes by default with regular references:

• Box<T> has a known size and points to data allocated on the heap.
• Rc<T> keeps track of the number of references to data on the heap, so that the data can have multiple owners.
• RefCell<T>, with its interior mutability, gives a type to use when we need an immutable type but must change an inner value of it; it enforces the borrowing rules at runtime instead of at compile time.
• The Deref and Drop traits enable a lot of the functionality of smart pointers.
• Reference cycles can cause memory leaks; Weak<T> prevents them.

To implement your own smart pointers, “The Rustonomicon” has more useful information.

The Rust Programming Language · Ch.15 Smart Pointers

102