src/doc/rustc-guide/src/borrow_check/moves_and_initialization/move_paths.md

   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
  15     // a.0 is not initialized, but a.1 still is
  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
  31 [`Place`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc/mir/struct.Place.html
  32
  33 ## Move path indices
  34
  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
  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
  48 [`MovePathIndex`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathIndex.html
  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
  87 If you have a [`Place`] and you would like to convert it to a [`MovePathIndex`], you
  88 can do that using the [`MovePathLookup`] structure found in the [`rev_lookup`] field
  89 of [`MoveData`]. There are two different methods:
  90
  91 [`MoveData`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MoveData.html
  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
 126 [`Place`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc/mir/struct.Place.html
 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