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