]>
Commit | Line | Data |
---|---|---|
a1dfa0c6 XL |
1 | # Move paths |
2 | ||
3 | In reality, it's not enough to track initialization at the granularity | |
4 | of local variables. Rust also allows us to do moves and initialization | |
5 | at the field granularity: | |
6 | ||
7 | ```rust,ignore | |
8 | fn foo() { | |
9 | let a: (Vec<u32>, Vec<u32>) = (vec![22], vec![44]); | |
10 | ||
11 | // a.0 and a.1 are both initialized | |
12 | ||
13 | let b = a.0; // moves a.0 | |
14 | ||
416331ca | 15 | // a.0 is not initialized, but a.1 still is |
a1dfa0c6 XL |
16 | |
17 | let c = a.0; // ERROR | |
18 | let d = a.1; // OK | |
19 | } | |
20 | ``` | |
21 | ||
22 | To handle this, we track initialization at the granularity of a **move | |
23 | path**. A [`MovePath`] represents some location that the user can | |
24 | initialize, move, etc. So e.g. there is a move-path representing the | |
25 | local variable `a`, and there is a move-path representing `a.0`. Move | |
26 | paths roughly correspond to the concept of a [`Place`] from MIR, but | |
27 | they are indexed in ways that enable us to do move analysis more | |
28 | efficiently. | |
29 | ||
30 | [`MovePath`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePath.html | |
416331ca | 31 | [`Place`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc/mir/struct.Place.html |
a1dfa0c6 XL |
32 | |
33 | ## Move path indices | |
34 | ||
48663c56 XL |
35 | Although there is a [`MovePath`] data structure, they are never referenced |
36 | directly. Instead, all the code passes around *indices* of type | |
37 | [`MovePathIndex`]. If you need to get information about a move path, you use | |
38 | this index with the [`move_paths` field of the `MoveData`][move_paths]. For | |
39 | example, to convert a [`MovePathIndex`] `mpi` into a MIR [`Place`], you might | |
a1dfa0c6 XL |
40 | access the [`MovePath::place`] field like so: |
41 | ||
42 | ```rust,ignore | |
43 | move_data.move_paths[mpi].place | |
44 | ``` | |
45 | ||
46 | [move_paths]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MoveData.html#structfield.move_paths | |
47 | [`MovePath::place`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePath.html#structfield.place | |
48663c56 | 48 | [`MovePathIndex`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathIndex.html |
a1dfa0c6 XL |
49 | |
50 | ## Building move paths | |
51 | ||
52 | One of the first things we do in the MIR borrow check is to construct | |
53 | the set of move paths. This is done as part of the | |
54 | [`MoveData::gather_moves`] function. This function uses a MIR visitor | |
55 | called [`Gatherer`] to walk the MIR and look at how each [`Place`] | |
56 | within is accessed. For each such [`Place`], it constructs a | |
57 | corresponding [`MovePathIndex`]. It also records when/where that | |
58 | particular move path is moved/initialized, but we'll get to that in a | |
59 | later section. | |
60 | ||
61 | [`Gatherer`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/builder/struct.Gatherer.html | |
62 | [`MoveData::gather_moves`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MoveData.html#method.gather_moves | |
63 | ||
64 | ### Illegal move paths | |
65 | ||
66 | We don't actually create a move-path for **every** [`Place`] that gets | |
67 | used. In particular, if it is illegal to move from a [`Place`], then | |
68 | there is no need for a [`MovePathIndex`]. Some examples: | |
69 | ||
70 | - You cannot move from a static variable, so we do not create a [`MovePathIndex`] | |
71 | for static variables. | |
72 | - You cannot move an individual element of an array, so if we have e.g. `foo: [String; 3]`, | |
73 | there would be no move-path for `foo[1]`. | |
74 | - You cannot move from inside of a borrowed reference, so if we have e.g. `foo: &String`, | |
75 | there would be no move-path for `*foo`. | |
76 | ||
77 | These rules are enforced by the [`move_path_for`] function, which | |
78 | converts a [`Place`] into a [`MovePathIndex`] -- in error cases like | |
79 | those just discussed, the function returns an `Err`. This in turn | |
80 | means we don't have to bother tracking whether those places are | |
81 | initialized (which lowers overhead). | |
82 | ||
83 | [`move_path_for`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/builder/struct.Gatherer.html#method.move_path_for | |
84 | ||
85 | ## Looking up a move-path | |
86 | ||
416331ca | 87 | If you have a [`Place`] and you would like to convert it to a [`MovePathIndex`], you |
a1dfa0c6 XL |
88 | can do that using the [`MovePathLookup`] structure found in the [`rev_lookup`] field |
89 | of [`MoveData`]. There are two different methods: | |
90 | ||
60c5eb7d | 91 | [`MoveData`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MoveData.html |
a1dfa0c6 XL |
92 | [`MovePathLookup`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathLookup.html |
93 | [`rev_lookup`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MoveData.html#structfield.rev_lookup | |
94 | ||
95 | - [`find_local`], which takes a [`mir::Local`] representing a local | |
96 | variable. This is the easier method, because we **always** create a | |
97 | [`MovePathIndex`] for every local variable. | |
98 | - [`find`], which takes an arbitrary [`Place`]. This method is a bit | |
99 | more annoying to use, precisely because we don't have a | |
100 | [`MovePathIndex`] for **every** [`Place`] (as we just discussed in | |
101 | the "illegal move paths" section). Therefore, [`find`] returns a | |
102 | [`LookupResult`] indicating the closest path it was able to find | |
103 | that exists (e.g., for `foo[1]`, it might return just the path for | |
104 | `foo`). | |
105 | ||
106 | [`find`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathLookup.html#method.find | |
107 | [`find_local`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathLookup.html#method.find_local | |
108 | [`mir::Local`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc/mir/struct.Local.html | |
109 | [`LookupResult`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/enum.LookupResult.html | |
110 | ||
111 | ## Cross-references | |
112 | ||
113 | As we noted above, move-paths are stored in a big vector and | |
114 | referenced via their [`MovePathIndex`]. However, within this vector, | |
115 | they are also structured into a tree. So for example if you have the | |
116 | [`MovePathIndex`] for `a.b.c`, you can go to its parent move-path | |
117 | `a.b`. You can also iterate over all children paths: so, from `a.b`, | |
118 | you might iterate to find the path `a.b.c` (here you are iterating | |
119 | just over the paths that are **actually referenced** in the source, | |
120 | not all **possible** paths that could have been referenced). These | |
121 | references are used for example in the [`has_any_child_of`] function, | |
122 | which checks whether the dataflow results contain a value for the | |
123 | given move-path (e.g., `a.b`) or any child of that move-path (e.g., | |
124 | `a.b.c`). | |
125 | ||
416331ca | 126 | [`Place`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc/mir/struct.Place.html |
a1dfa0c6 | 127 | [`has_any_child_of`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/at_location/struct.FlowAtLocation.html#method.has_any_child_of |