]>
Commit | Line | Data |
---|---|---|
13cf67c4 XL |
1 | ## Using `Box<T>` to Point to Data on the Heap |
2 | ||
3 | The most straightforward smart pointer is a *box*, whose type is written | |
4 | `Box<T>`. Boxes allow you to store data on the heap rather than the stack. What | |
5 | remains on the stack is the pointer to the heap data. Refer to Chapter 4 to | |
6 | review the difference between the stack and the heap. | |
7 | ||
8 | Boxes don’t have performance overhead, other than storing their data on the | |
9 | heap instead of on the stack. But they don’t have many extra capabilities | |
10 | either. You’ll use them most often in these situations: | |
11 | ||
12 | * When you have a type whose size can’t be known at compile time and you want | |
13 | to use a value of that type in a context that requires an exact size | |
14 | * When you have a large amount of data and you want to transfer ownership but | |
15 | ensure the data won’t be copied when you do so | |
16 | * When you want to own a value and you care only that it’s a type that | |
17 | implements a particular trait rather than being of a specific type | |
18 | ||
9fa01778 XL |
19 | We’ll demonstrate the first situation in the [“Enabling Recursive Types with |
20 | Boxes”](#enabling-recursive-types-with-boxes)<!-- ignore --> section. In the | |
21 | second case, transferring ownership of a large amount of data can take a long | |
22 | time because the data is copied around on the stack. To improve performance in | |
23 | this situation, we can store the large amount of data on the heap in a box. | |
24 | Then, only the small amount of pointer data is copied around on the stack, | |
25 | while the data it references stays in one place on the heap. The third case is | |
26 | known as a *trait object*, and Chapter 17 devotes an entire section, [“Using | |
27 | Trait Objects That Allow for Values of Different Types,”][trait-objects]<!-- | |
28 | ignore --> just to that topic. So what you learn here you’ll apply again in | |
29 | Chapter 17! | |
13cf67c4 XL |
30 | |
31 | ### Using a `Box<T>` to Store Data on the Heap | |
32 | ||
04454e1e FG |
33 | Before we discuss the heap storage use case for `Box<T>`, we’ll cover the |
34 | syntax and how to interact with values stored within a `Box<T>`. | |
13cf67c4 XL |
35 | |
36 | Listing 15-1 shows how to use a box to store an `i32` value on the heap: | |
37 | ||
38 | <span class="filename">Filename: src/main.rs</span> | |
39 | ||
40 | ```rust | |
74b04a01 | 41 | {{#rustdoc_include ../listings/ch15-smart-pointers/listing-15-01/src/main.rs}} |
13cf67c4 XL |
42 | ``` |
43 | ||
44 | <span class="caption">Listing 15-1: Storing an `i32` value on the heap using a | |
45 | box</span> | |
46 | ||
47 | We define the variable `b` to have the value of a `Box` that points to the | |
48 | value `5`, which is allocated on the heap. This program will print `b = 5`; in | |
49 | this case, we can access the data in the box similar to how we would if this | |
50 | data were on the stack. Just like any owned value, when a box goes out of | |
51 | scope, as `b` does at the end of `main`, it will be deallocated. The | |
04454e1e FG |
52 | deallocation happens both for the box (stored on the stack) and the data it |
53 | points to (stored on the heap). | |
13cf67c4 XL |
54 | |
55 | Putting a single value on the heap isn’t very useful, so you won’t use boxes by | |
56 | themselves in this way very often. Having values like a single `i32` on the | |
57 | stack, where they’re stored by default, is more appropriate in the majority of | |
58 | situations. Let’s look at a case where boxes allow us to define types that we | |
59 | wouldn’t be allowed to if we didn’t have boxes. | |
60 | ||
61 | ### Enabling Recursive Types with Boxes | |
62 | ||
04454e1e FG |
63 | A value of *recursive type* can have another value of the same type as part of |
64 | itself. Recursive types pose an issue because at compile time Rust needs to | |
65 | know how much space a type takes up. However, the nesting of values of | |
66 | recursive types could theoretically continue infinitely, so Rust can’t know how | |
67 | much space the value needs. Because boxes have a known size, we can enable | |
68 | recursive types by inserting a box in the recursive type definition. | |
13cf67c4 | 69 | |
04454e1e FG |
70 | As an example of a recursive type, let’s explore the *cons list*. This is a data |
71 | type commonly found in functional programming languages. The cons list type | |
13cf67c4 XL |
72 | we’ll define is straightforward except for the recursion; therefore, the |
73 | concepts in the example we’ll work with will be useful any time you get into | |
74 | more complex situations involving recursive types. | |
75 | ||
76 | #### More Information About the Cons List | |
77 | ||
78 | A *cons list* is a data structure that comes from the Lisp programming language | |
923072b8 FG |
79 | and its dialects and is made up of nested pairs, and is the Lisp version of a |
80 | linked list. Its name comes from the `cons` function (short for “construct | |
81 | function”) in Lisp that constructs a new pair from its two arguments. By | |
82 | calling `cons` on a pair consisting of a value and another pair, we can | |
83 | construct cons lists made up of recursive pairs. | |
13cf67c4 | 84 | |
04454e1e FG |
85 | For example, here's a pseudocode representation of a cons list containing the |
86 | list 1, 2, 3 with each pair in parentheses: | |
87 | ||
88 | ```text | |
89 | (1, (2, (3, Nil))) | |
90 | ``` | |
13cf67c4 XL |
91 | |
92 | Each item in a cons list contains two elements: the value of the current item | |
93 | and the next item. The last item in the list contains only a value called `Nil` | |
94 | without a next item. A cons list is produced by recursively calling the `cons` | |
95 | function. The canonical name to denote the base case of the recursion is `Nil`. | |
96 | Note that this is not the same as the “null” or “nil” concept in Chapter 6, | |
97 | which is an invalid or absent value. | |
98 | ||
04454e1e FG |
99 | The cons list isn’t a commonly used data structure in Rust. Most of the time |
100 | when you have a list of items in Rust, `Vec<T>` is a better choice to use. | |
101 | Other, more complex recursive data types *are* useful in various situations, | |
102 | but by starting with the cons list in this chapter, we can explore how boxes | |
103 | let us define a recursive data type without much distraction. | |
13cf67c4 XL |
104 | |
105 | Listing 15-2 contains an enum definition for a cons list. Note that this code | |
106 | won’t compile yet because the `List` type doesn’t have a known size, which | |
107 | we’ll demonstrate. | |
108 | ||
109 | <span class="filename">Filename: src/main.rs</span> | |
110 | ||
111 | ```rust,ignore,does_not_compile | |
74b04a01 | 112 | {{#rustdoc_include ../listings/ch15-smart-pointers/listing-15-02/src/main.rs:here}} |
13cf67c4 XL |
113 | ``` |
114 | ||
115 | <span class="caption">Listing 15-2: The first attempt at defining an enum to | |
116 | represent a cons list data structure of `i32` values</span> | |
117 | ||
118 | > Note: We’re implementing a cons list that holds only `i32` values for the | |
119 | > purposes of this example. We could have implemented it using generics, as we | |
120 | > discussed in Chapter 10, to define a cons list type that could store values of | |
121 | > any type. | |
122 | ||
123 | Using the `List` type to store the list `1, 2, 3` would look like the code in | |
124 | Listing 15-3: | |
125 | ||
126 | <span class="filename">Filename: src/main.rs</span> | |
127 | ||
48663c56 | 128 | ```rust,ignore,does_not_compile |
74b04a01 | 129 | {{#rustdoc_include ../listings/ch15-smart-pointers/listing-15-03/src/main.rs:here}} |
13cf67c4 XL |
130 | ``` |
131 | ||
132 | <span class="caption">Listing 15-3: Using the `List` enum to store the list `1, | |
133 | 2, 3`</span> | |
134 | ||
135 | The first `Cons` value holds `1` and another `List` value. This `List` value is | |
136 | another `Cons` value that holds `2` and another `List` value. This `List` value | |
137 | is one more `Cons` value that holds `3` and a `List` value, which is finally | |
138 | `Nil`, the non-recursive variant that signals the end of the list. | |
139 | ||
140 | If we try to compile the code in Listing 15-3, we get the error shown in | |
141 | Listing 15-4: | |
142 | ||
f035d41b | 143 | ```console |
74b04a01 | 144 | {{#include ../listings/ch15-smart-pointers/listing-15-03/output.txt}} |
13cf67c4 XL |
145 | ``` |
146 | ||
147 | <span class="caption">Listing 15-4: The error we get when attempting to define | |
148 | a recursive enum</span> | |
149 | ||
150 | The error shows this type “has infinite size.” The reason is that we’ve defined | |
151 | `List` with a variant that is recursive: it holds another value of itself | |
152 | directly. As a result, Rust can’t figure out how much space it needs to store a | |
04454e1e FG |
153 | `List` value. Let’s break down why we get this error. First, we'll look at how |
154 | Rust decides how much space it needs to store a value of a non-recursive type. | |
13cf67c4 XL |
155 | |
156 | #### Computing the Size of a Non-Recursive Type | |
157 | ||
158 | Recall the `Message` enum we defined in Listing 6-2 when we discussed enum | |
159 | definitions in Chapter 6: | |
160 | ||
161 | ```rust | |
74b04a01 | 162 | {{#rustdoc_include ../listings/ch06-enums-and-pattern-matching/listing-06-02/src/main.rs:here}} |
13cf67c4 XL |
163 | ``` |
164 | ||
165 | To determine how much space to allocate for a `Message` value, Rust goes | |
166 | through each of the variants to see which variant needs the most space. Rust | |
167 | sees that `Message::Quit` doesn’t need any space, `Message::Move` needs enough | |
168 | space to store two `i32` values, and so forth. Because only one variant will be | |
169 | used, the most space a `Message` value will need is the space it would take to | |
170 | store the largest of its variants. | |
171 | ||
172 | Contrast this with what happens when Rust tries to determine how much space a | |
173 | recursive type like the `List` enum in Listing 15-2 needs. The compiler starts | |
174 | by looking at the `Cons` variant, which holds a value of type `i32` and a value | |
175 | of type `List`. Therefore, `Cons` needs an amount of space equal to the size of | |
176 | an `i32` plus the size of a `List`. To figure out how much memory the `List` | |
177 | type needs, the compiler looks at the variants, starting with the `Cons` | |
178 | variant. The `Cons` variant holds a value of type `i32` and a value of type | |
179 | `List`, and this process continues infinitely, as shown in Figure 15-1. | |
180 | ||
181 | <img alt="An infinite Cons list" src="img/trpl15-01.svg" class="center" style="width: 50%;" /> | |
182 | ||
183 | <span class="caption">Figure 15-1: An infinite `List` consisting of infinite | |
184 | `Cons` variants</span> | |
185 | ||
186 | #### Using `Box<T>` to Get a Recursive Type with a Known Size | |
187 | ||
04454e1e FG |
188 | Because Rust can’t figure out how much space to allocate for recursively |
189 | defined types, the compiler gives an error with this helpful suggestion: | |
13cf67c4 | 190 | |
74b04a01 XL |
191 | <!-- manual-regeneration |
192 | after doing automatic regeneration, look at listings/ch15-smart-pointers/listing-15-03/output.txt and copy the relevant line | |
193 | --> | |
194 | ||
13cf67c4 | 195 | ```text |
fc512014 XL |
196 | help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable |
197 | | | |
198 | 2 | Cons(i32, Box<List>), | |
199 | | ^^^^ ^ | |
13cf67c4 XL |
200 | ``` |
201 | ||
202 | In this suggestion, “indirection” means that instead of storing a value | |
04454e1e | 203 | directly, we should change the data structure to store the value indirectly by |
13cf67c4 XL |
204 | storing a pointer to the value instead. |
205 | ||
206 | Because a `Box<T>` is a pointer, Rust always knows how much space a `Box<T>` | |
207 | needs: a pointer’s size doesn’t change based on the amount of data it’s | |
208 | pointing to. This means we can put a `Box<T>` inside the `Cons` variant instead | |
209 | of another `List` value directly. The `Box<T>` will point to the next `List` | |
210 | value that will be on the heap rather than inside the `Cons` variant. | |
04454e1e FG |
211 | Conceptually, we still have a list, created with lists holding other lists, but |
212 | this implementation is now more like placing the items next to one another | |
13cf67c4 XL |
213 | rather than inside one another. |
214 | ||
215 | We can change the definition of the `List` enum in Listing 15-2 and the usage | |
216 | of the `List` in Listing 15-3 to the code in Listing 15-5, which will compile: | |
217 | ||
218 | <span class="filename">Filename: src/main.rs</span> | |
219 | ||
220 | ```rust | |
74b04a01 | 221 | {{#rustdoc_include ../listings/ch15-smart-pointers/listing-15-05/src/main.rs}} |
13cf67c4 XL |
222 | ``` |
223 | ||
224 | <span class="caption">Listing 15-5: Definition of `List` that uses `Box<T>` in | |
225 | order to have a known size</span> | |
226 | ||
04454e1e | 227 | The `Cons` variant needs the size of an `i32` plus the space to store the |
13cf67c4 XL |
228 | box’s pointer data. The `Nil` variant stores no values, so it needs less space |
229 | than the `Cons` variant. We now know that any `List` value will take up the | |
230 | size of an `i32` plus the size of a box’s pointer data. By using a box, we’ve | |
231 | broken the infinite, recursive chain, so the compiler can figure out the size | |
232 | it needs to store a `List` value. Figure 15-2 shows what the `Cons` variant | |
233 | looks like now. | |
234 | ||
235 | <img alt="A finite Cons list" src="img/trpl15-02.svg" class="center" /> | |
236 | ||
237 | <span class="caption">Figure 15-2: A `List` that is not infinitely sized | |
238 | because `Cons` holds a `Box`</span> | |
239 | ||
240 | Boxes provide only the indirection and heap allocation; they don’t have any | |
241 | other special capabilities, like those we’ll see with the other smart pointer | |
04454e1e | 242 | types. They also don’t have the performance overhead that these special |
13cf67c4 XL |
243 | capabilities incur, so they can be useful in cases like the cons list where the |
244 | indirection is the only feature we need. We’ll look at more use cases for boxes | |
245 | in Chapter 17, too. | |
246 | ||
247 | The `Box<T>` type is a smart pointer because it implements the `Deref` trait, | |
248 | which allows `Box<T>` values to be treated like references. When a `Box<T>` | |
249 | value goes out of scope, the heap data that the box is pointing to is cleaned | |
04454e1e FG |
250 | up as well because of the `Drop` trait implementation. These two traits will be |
251 | even more important to the functionality provided by the other smart pointer | |
252 | types we’ll discuss in the rest of this chapter. Let’s explore these two traits | |
253 | in more detail. | |
9fa01778 XL |
254 | |
255 | [trait-objects]: ch17-02-trait-objects.html#using-trait-objects-that-allow-for-values-of-different-types |