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