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