rustc_mir_dataflow/move_paths/
mod.rs

1//! The move-analysis portion of borrowck needs to work in an abstract domain of lifted `Place`s.
2//! Most of the `Place` variants fall into a one-to-one mapping between the concrete and abstract
3//! (e.g., a field projection on a local variable, `x.field`, has the same meaning in both
4//! domains). In other words, all field projections for the same field on the same local do not
5//! have meaningfully different types if ever. Indexed projections are the exception: `a[x]` needs
6//! to be treated as mapping to the same move path as `a[y]` as well as `a[13]`, etc. So we map
7//! these `x`/`y` values to `()`.
8//!
9//! (In theory, the analysis could be extended to work with sets of paths, so that `a[0]` and
10//! `a[13]` could be kept distinct, while `a[x]` would still overlap them both. But that is not
11//! what this representation does today.)
12
13use std::fmt;
14use std::ops::{Index, IndexMut};
15
16use rustc_data_structures::fx::FxHashMap;
17use rustc_index::{IndexSlice, IndexVec};
18use rustc_middle::mir::*;
19use rustc_middle::ty::{Ty, TyCtxt};
20use rustc_span::Span;
21use smallvec::SmallVec;
22
23use crate::un_derefer::UnDerefer;
24
25rustc_index::newtype_index! {
26    #[orderable]
27    #[debug_format = "mp{}"]
28    pub struct MovePathIndex {}
29}
30
31impl polonius_engine::Atom for MovePathIndex {
32    fn index(self) -> usize {
33        rustc_index::Idx::index(self)
34    }
35}
36
37rustc_index::newtype_index! {
38    #[orderable]
39    #[debug_format = "mo{}"]
40    pub struct MoveOutIndex {}
41}
42
43rustc_index::newtype_index! {
44    #[debug_format = "in{}"]
45    pub struct InitIndex {}
46}
47
48impl MoveOutIndex {
49    pub fn move_path_index(self, move_data: &MoveData<'_>) -> MovePathIndex {
50        move_data.moves[self].path
51    }
52}
53
54/// `MovePath` is a canonicalized representation of a path that is
55/// moved or assigned to.
56///
57/// It follows a tree structure.
58///
59/// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
60/// move *out* of the place `x.m`.
61///
62/// The MovePaths representing `x.m` and `x.n` are siblings (that is,
63/// one of them will link to the other via the `next_sibling` field,
64/// and the other will have no entry in its `next_sibling` field), and
65/// they both have the MovePath representing `x` as their parent.
66#[derive(Clone)]
67pub struct MovePath<'tcx> {
68    pub next_sibling: Option<MovePathIndex>,
69    pub first_child: Option<MovePathIndex>,
70    pub parent: Option<MovePathIndex>,
71    pub place: Place<'tcx>,
72}
73
74impl<'tcx> MovePath<'tcx> {
75    /// Returns an iterator over the parents of `self`.
76    pub fn parents<'a>(
77        &self,
78        move_paths: &'a IndexSlice<MovePathIndex, MovePath<'tcx>>,
79    ) -> impl 'a + Iterator<Item = (MovePathIndex, &'a MovePath<'tcx>)> {
80        let first = self.parent.map(|mpi| (mpi, &move_paths[mpi]));
81        MovePathLinearIter {
82            next: first,
83            fetch_next: move |_, parent: &MovePath<'_>| {
84                parent.parent.map(|mpi| (mpi, &move_paths[mpi]))
85            },
86        }
87    }
88
89    /// Returns an iterator over the immediate children of `self`.
90    pub fn children<'a>(
91        &self,
92        move_paths: &'a IndexSlice<MovePathIndex, MovePath<'tcx>>,
93    ) -> impl 'a + Iterator<Item = (MovePathIndex, &'a MovePath<'tcx>)> {
94        let first = self.first_child.map(|mpi| (mpi, &move_paths[mpi]));
95        MovePathLinearIter {
96            next: first,
97            fetch_next: move |_, child: &MovePath<'_>| {
98                child.next_sibling.map(|mpi| (mpi, &move_paths[mpi]))
99            },
100        }
101    }
102
103    /// Finds the closest descendant of `self` for which `f` returns `true` using a breadth-first
104    /// search.
105    ///
106    /// `f` will **not** be called on `self`.
107    pub fn find_descendant(
108        &self,
109        move_paths: &IndexSlice<MovePathIndex, MovePath<'_>>,
110        f: impl Fn(MovePathIndex) -> bool,
111    ) -> Option<MovePathIndex> {
112        let mut todo = if let Some(child) = self.first_child {
113            vec![child]
114        } else {
115            return None;
116        };
117
118        while let Some(mpi) = todo.pop() {
119            if f(mpi) {
120                return Some(mpi);
121            }
122
123            let move_path = &move_paths[mpi];
124            if let Some(child) = move_path.first_child {
125                todo.push(child);
126            }
127
128            // After we've processed the original `mpi`, we should always
129            // traverse the siblings of any of its children.
130            if let Some(sibling) = move_path.next_sibling {
131                todo.push(sibling);
132            }
133        }
134
135        None
136    }
137}
138
139impl<'tcx> fmt::Debug for MovePath<'tcx> {
140    fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
141        write!(w, "MovePath {{")?;
142        if let Some(parent) = self.parent {
143            write!(w, " parent: {parent:?},")?;
144        }
145        if let Some(first_child) = self.first_child {
146            write!(w, " first_child: {first_child:?},")?;
147        }
148        if let Some(next_sibling) = self.next_sibling {
149            write!(w, " next_sibling: {next_sibling:?}")?;
150        }
151        write!(w, " place: {:?} }}", self.place)
152    }
153}
154
155impl<'tcx> fmt::Display for MovePath<'tcx> {
156    fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
157        write!(w, "{:?}", self.place)
158    }
159}
160
161struct MovePathLinearIter<'a, 'tcx, F> {
162    next: Option<(MovePathIndex, &'a MovePath<'tcx>)>,
163    fetch_next: F,
164}
165
166impl<'a, 'tcx, F> Iterator for MovePathLinearIter<'a, 'tcx, F>
167where
168    F: FnMut(MovePathIndex, &'a MovePath<'tcx>) -> Option<(MovePathIndex, &'a MovePath<'tcx>)>,
169{
170    type Item = (MovePathIndex, &'a MovePath<'tcx>);
171
172    fn next(&mut self) -> Option<Self::Item> {
173        let ret = self.next.take()?;
174        self.next = (self.fetch_next)(ret.0, ret.1);
175        Some(ret)
176    }
177}
178
179#[derive(Debug)]
180pub struct MoveData<'tcx> {
181    pub move_paths: IndexVec<MovePathIndex, MovePath<'tcx>>,
182    pub moves: IndexVec<MoveOutIndex, MoveOut>,
183    /// Each Location `l` is mapped to the MoveOut's that are effects
184    /// of executing the code at `l`. (There can be multiple MoveOut's
185    /// for a given `l` because each MoveOut is associated with one
186    /// particular path being moved.)
187    pub loc_map: LocationMap<SmallVec<[MoveOutIndex; 4]>>,
188    pub path_map: IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>,
189    pub rev_lookup: MovePathLookup<'tcx>,
190    pub inits: IndexVec<InitIndex, Init>,
191    /// Each Location `l` is mapped to the Inits that are effects
192    /// of executing the code at `l`.
193    pub init_loc_map: LocationMap<SmallVec<[InitIndex; 4]>>,
194    pub init_path_map: IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>,
195}
196
197pub trait HasMoveData<'tcx> {
198    fn move_data(&self) -> &MoveData<'tcx>;
199}
200
201#[derive(Debug)]
202pub struct LocationMap<T> {
203    /// Location-indexed (BasicBlock for outer index, index within BB
204    /// for inner index) map.
205    pub(crate) map: IndexVec<BasicBlock, Vec<T>>,
206}
207
208impl<T> Index<Location> for LocationMap<T> {
209    type Output = T;
210    fn index(&self, index: Location) -> &Self::Output {
211        &self.map[index.block][index.statement_index]
212    }
213}
214
215impl<T> IndexMut<Location> for LocationMap<T> {
216    fn index_mut(&mut self, index: Location) -> &mut Self::Output {
217        &mut self.map[index.block][index.statement_index]
218    }
219}
220
221impl<T> LocationMap<T>
222where
223    T: Default + Clone,
224{
225    fn new(body: &Body<'_>) -> Self {
226        LocationMap {
227            map: body
228                .basic_blocks
229                .iter()
230                .map(|block| vec![T::default(); block.statements.len() + 1])
231                .collect(),
232        }
233    }
234}
235
236/// `MoveOut` represents a point in a program that moves out of some
237/// L-value; i.e., "creates" uninitialized memory.
238///
239/// With respect to dataflow analysis:
240/// - Generated by moves and declaration of uninitialized variables.
241/// - Killed by assignments to the memory.
242#[derive(Copy, Clone)]
243pub struct MoveOut {
244    /// path being moved
245    pub path: MovePathIndex,
246    /// location of move
247    pub source: Location,
248}
249
250impl fmt::Debug for MoveOut {
251    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
252        write!(fmt, "{:?}@{:?}", self.path, self.source)
253    }
254}
255
256/// `Init` represents a point in a program that initializes some L-value;
257#[derive(Copy, Clone)]
258pub struct Init {
259    /// path being initialized
260    pub path: MovePathIndex,
261    /// location of initialization
262    pub location: InitLocation,
263    /// Extra information about this initialization
264    pub kind: InitKind,
265}
266
267/// Initializations can be from an argument or from a statement. Arguments
268/// do not have locations, in those cases the `Local` is kept..
269#[derive(Copy, Clone, Debug, PartialEq, Eq)]
270pub enum InitLocation {
271    Argument(Local),
272    Statement(Location),
273}
274
275/// Additional information about the initialization.
276#[derive(Copy, Clone, Debug, PartialEq, Eq)]
277pub enum InitKind {
278    /// Deep init, even on panic
279    Deep,
280    /// Only does a shallow init
281    Shallow,
282    /// This doesn't initialize the variable on panic (and a panic is possible).
283    NonPanicPathOnly,
284}
285
286impl fmt::Debug for Init {
287    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
288        write!(fmt, "{:?}@{:?} ({:?})", self.path, self.location, self.kind)
289    }
290}
291
292impl Init {
293    pub fn span<'tcx>(&self, body: &Body<'tcx>) -> Span {
294        match self.location {
295            InitLocation::Argument(local) => body.local_decls[local].source_info.span,
296            InitLocation::Statement(location) => body.source_info(location).span,
297        }
298    }
299}
300
301/// Tables mapping from a place to its MovePathIndex.
302#[derive(Debug)]
303pub struct MovePathLookup<'tcx> {
304    locals: IndexVec<Local, Option<MovePathIndex>>,
305
306    /// projections are made from a base-place and a projection
307    /// elem. The base-place will have a unique MovePathIndex; we use
308    /// the latter as the index into the outer vector (narrowing
309    /// subsequent search so that it is solely relative to that
310    /// base-place). For the remaining lookup, we map the projection
311    /// elem to the associated MovePathIndex.
312    projections: FxHashMap<(MovePathIndex, ProjectionKind), MovePathIndex>,
313
314    un_derefer: UnDerefer<'tcx>,
315}
316
317mod builder;
318
319#[derive(Copy, Clone, Debug)]
320pub enum LookupResult {
321    Exact(MovePathIndex),
322    Parent(Option<MovePathIndex>),
323}
324
325impl<'tcx> MovePathLookup<'tcx> {
326    // Unlike the builder `fn move_path_for` below, this lookup
327    // alternative will *not* create a MovePath on the fly for an
328    // unknown place, but will rather return the nearest available
329    // parent.
330    pub fn find(&self, place: PlaceRef<'tcx>) -> LookupResult {
331        let Some(mut result) = self.find_local(place.local) else {
332            return LookupResult::Parent(None);
333        };
334
335        for (_, elem) in self.un_derefer.iter_projections(place) {
336            if let Some(&subpath) = self.projections.get(&(result, elem.kind())) {
337                result = subpath;
338            } else {
339                return LookupResult::Parent(Some(result));
340            }
341        }
342
343        LookupResult::Exact(result)
344    }
345
346    #[inline]
347    pub fn find_local(&self, local: Local) -> Option<MovePathIndex> {
348        self.locals[local]
349    }
350
351    /// An enumerated iterator of `local`s and their associated
352    /// `MovePathIndex`es.
353    pub fn iter_locals_enumerated(
354        &self,
355    ) -> impl DoubleEndedIterator<Item = (Local, MovePathIndex)> {
356        self.locals.iter_enumerated().filter_map(|(l, &idx)| Some((l, idx?)))
357    }
358}
359
360impl<'tcx> MoveData<'tcx> {
361    pub fn gather_moves(
362        body: &Body<'tcx>,
363        tcx: TyCtxt<'tcx>,
364        filter: impl Fn(Ty<'tcx>) -> bool,
365    ) -> MoveData<'tcx> {
366        builder::gather_moves(body, tcx, filter)
367    }
368
369    /// For the move path `mpi`, returns the root local variable that starts the path.
370    /// (e.g., for a path like `a.b.c` returns `a`)
371    pub fn base_local(&self, mut mpi: MovePathIndex) -> Local {
372        loop {
373            let path = &self.move_paths[mpi];
374            if let Some(l) = path.place.as_local() {
375                return l;
376            }
377            mpi = path.parent.expect("root move paths should be locals");
378        }
379    }
380
381    pub fn find_in_move_path_or_its_descendants(
382        &self,
383        root: MovePathIndex,
384        pred: impl Fn(MovePathIndex) -> bool,
385    ) -> Option<MovePathIndex> {
386        if pred(root) {
387            return Some(root);
388        }
389
390        self.move_paths[root].find_descendant(&self.move_paths, pred)
391    }
392}
rustc_mir_dataflow/move_paths/mod.rs

rustc_mir_dataflow/move_paths/
mod.rs
