]>
Commit | Line | Data |
---|---|---|
54a0048b SL |
1 | // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | ||
7cac9316 | 12 | use rustc::ty::{self, TyCtxt}; |
c30ab7b3 | 13 | use rustc::mir::*; |
476ff2be | 14 | use rustc::util::nodemap::FxHashMap; |
9e0c209e | 15 | use rustc_data_structures::indexed_vec::{IndexVec}; |
a1dfa0c6 | 16 | use smallvec::SmallVec; |
ea8adc8c | 17 | use syntax_pos::{Span}; |
9e0c209e | 18 | |
54a0048b | 19 | use std::fmt; |
9e0c209e | 20 | use std::ops::{Index, IndexMut}; |
54a0048b | 21 | |
041b39d2 XL |
22 | use self::abs_domain::{AbstractElem, Lift}; |
23 | ||
24 | mod abs_domain; | |
54a0048b SL |
25 | |
26 | // This submodule holds some newtype'd Index wrappers that are using | |
27 | // NonZero to ensure that Option<Index> occupies only a single word. | |
28 | // They are in a submodule to impose privacy restrictions; namely, to | |
29 | // ensure that other code does not accidentally access `index.0` | |
30 | // (which is likely to yield a subtle off-by-one error). | |
041b39d2 | 31 | pub(crate) mod indexes { |
9e0c209e | 32 | use std::fmt; |
0531ce1d | 33 | use std::num::NonZeroUsize; |
3157f602 | 34 | use rustc_data_structures::indexed_vec::Idx; |
54a0048b SL |
35 | |
36 | macro_rules! new_index { | |
9e0c209e | 37 | ($Index:ident, $debug_name:expr) => { |
94b46f34 | 38 | #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] |
0531ce1d | 39 | pub struct $Index(NonZeroUsize); |
54a0048b | 40 | |
3157f602 XL |
41 | impl Idx for $Index { |
42 | fn new(idx: usize) -> Self { | |
0531ce1d | 43 | $Index(NonZeroUsize::new(idx + 1).unwrap()) |
54a0048b | 44 | } |
3157f602 | 45 | fn index(self) -> usize { |
7cac9316 | 46 | self.0.get() - 1 |
54a0048b SL |
47 | } |
48 | } | |
9e0c209e SL |
49 | |
50 | impl fmt::Debug for $Index { | |
51 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { | |
52 | write!(fmt, "{}{}", $debug_name, self.index()) | |
53 | } | |
54 | } | |
54a0048b SL |
55 | } |
56 | } | |
57 | ||
58 | /// Index into MovePathData.move_paths | |
9e0c209e | 59 | new_index!(MovePathIndex, "mp"); |
54a0048b SL |
60 | |
61 | /// Index into MoveData.moves. | |
9e0c209e | 62 | new_index!(MoveOutIndex, "mo"); |
3b2f2976 | 63 | |
ff7c6d11 XL |
64 | /// Index into MoveData.inits. |
65 | new_index!(InitIndex, "in"); | |
66 | ||
3b2f2976 XL |
67 | /// Index into Borrows.locations |
68 | new_index!(BorrowIndex, "bw"); | |
54a0048b SL |
69 | } |
70 | ||
71 | pub use self::indexes::MovePathIndex; | |
72 | pub use self::indexes::MoveOutIndex; | |
ff7c6d11 | 73 | pub use self::indexes::InitIndex; |
54a0048b | 74 | |
041b39d2 | 75 | impl MoveOutIndex { |
3157f602 | 76 | pub fn move_path_index(&self, move_data: &MoveData) -> MovePathIndex { |
9e0c209e | 77 | move_data.moves[*self].path |
3157f602 XL |
78 | } |
79 | } | |
80 | ||
54a0048b SL |
81 | /// `MovePath` is a canonicalized representation of a path that is |
82 | /// moved or assigned to. | |
83 | /// | |
84 | /// It follows a tree structure. | |
85 | /// | |
86 | /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;` | |
2c00a5a8 | 87 | /// move *out* of the place `x.m`. |
54a0048b SL |
88 | /// |
89 | /// The MovePaths representing `x.m` and `x.n` are siblings (that is, | |
90 | /// one of them will link to the other via the `next_sibling` field, | |
91 | /// and the other will have no entry in its `next_sibling` field), and | |
92 | /// they both have the MovePath representing `x` as their parent. | |
93 | #[derive(Clone)] | |
94 | pub struct MovePath<'tcx> { | |
95 | pub next_sibling: Option<MovePathIndex>, | |
96 | pub first_child: Option<MovePathIndex>, | |
97 | pub parent: Option<MovePathIndex>, | |
ff7c6d11 | 98 | pub place: Place<'tcx>, |
54a0048b SL |
99 | } |
100 | ||
0bf4aa26 XL |
101 | impl<'tcx> MovePath<'tcx> { |
102 | pub fn parents(&self, move_paths: &IndexVec<MovePathIndex, MovePath>) -> Vec<MovePathIndex> { | |
103 | let mut parents = Vec::new(); | |
104 | ||
105 | let mut curr_parent = self.parent; | |
106 | while let Some(parent_mpi) = curr_parent { | |
107 | parents.push(parent_mpi); | |
108 | curr_parent = move_paths[parent_mpi].parent; | |
109 | } | |
110 | ||
111 | parents | |
112 | } | |
113 | } | |
114 | ||
54a0048b SL |
115 | impl<'tcx> fmt::Debug for MovePath<'tcx> { |
116 | fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { | |
117 | write!(w, "MovePath {{")?; | |
118 | if let Some(parent) = self.parent { | |
119 | write!(w, " parent: {:?},", parent)?; | |
120 | } | |
121 | if let Some(first_child) = self.first_child { | |
122 | write!(w, " first_child: {:?},", first_child)?; | |
123 | } | |
124 | if let Some(next_sibling) = self.next_sibling { | |
125 | write!(w, " next_sibling: {:?}", next_sibling)?; | |
126 | } | |
ff7c6d11 | 127 | write!(w, " place: {:?} }}", self.place) |
54a0048b SL |
128 | } |
129 | } | |
130 | ||
3b2f2976 XL |
131 | impl<'tcx> fmt::Display for MovePath<'tcx> { |
132 | fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { | |
ff7c6d11 | 133 | write!(w, "{:?}", self.place) |
3b2f2976 XL |
134 | } |
135 | } | |
136 | ||
3157f602 | 137 | #[derive(Debug)] |
54a0048b | 138 | pub struct MoveData<'tcx> { |
9e0c209e SL |
139 | pub move_paths: IndexVec<MovePathIndex, MovePath<'tcx>>, |
140 | pub moves: IndexVec<MoveOutIndex, MoveOut>, | |
141 | /// Each Location `l` is mapped to the MoveOut's that are effects | |
142 | /// of executing the code at `l`. (There can be multiple MoveOut's | |
143 | /// for a given `l` because each MoveOut is associated with one | |
144 | /// particular path being moved.) | |
a1dfa0c6 XL |
145 | pub loc_map: LocationMap<SmallVec<[MoveOutIndex; 4]>>, |
146 | pub path_map: IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>, | |
54a0048b | 147 | pub rev_lookup: MovePathLookup<'tcx>, |
ff7c6d11 XL |
148 | pub inits: IndexVec<InitIndex, Init>, |
149 | /// Each Location `l` is mapped to the Inits that are effects | |
150 | /// of executing the code at `l`. | |
a1dfa0c6 XL |
151 | pub init_loc_map: LocationMap<SmallVec<[InitIndex; 4]>>, |
152 | pub init_path_map: IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>, | |
54a0048b SL |
153 | } |
154 | ||
32a655c1 SL |
155 | pub trait HasMoveData<'tcx> { |
156 | fn move_data(&self) -> &MoveData<'tcx>; | |
157 | } | |
158 | ||
3157f602 | 159 | #[derive(Debug)] |
9e0c209e | 160 | pub struct LocationMap<T> { |
54a0048b | 161 | /// Location-indexed (BasicBlock for outer index, index within BB |
9e0c209e | 162 | /// for inner index) map. |
041b39d2 | 163 | pub(crate) map: IndexVec<BasicBlock, Vec<T>>, |
54a0048b SL |
164 | } |
165 | ||
9e0c209e SL |
166 | impl<T> Index<Location> for LocationMap<T> { |
167 | type Output = T; | |
54a0048b | 168 | fn index(&self, index: Location) -> &Self::Output { |
9e0c209e | 169 | &self.map[index.block][index.statement_index] |
54a0048b SL |
170 | } |
171 | } | |
172 | ||
9e0c209e SL |
173 | impl<T> IndexMut<Location> for LocationMap<T> { |
174 | fn index_mut(&mut self, index: Location) -> &mut Self::Output { | |
175 | &mut self.map[index.block][index.statement_index] | |
176 | } | |
54a0048b SL |
177 | } |
178 | ||
9e0c209e SL |
179 | impl<T> LocationMap<T> where T: Default + Clone { |
180 | fn new(mir: &Mir) -> Self { | |
181 | LocationMap { | |
182 | map: mir.basic_blocks().iter().map(|block| { | |
183 | vec![T::default(); block.statements.len()+1] | |
184 | }).collect() | |
185 | } | |
54a0048b SL |
186 | } |
187 | } | |
188 | ||
189 | /// `MoveOut` represents a point in a program that moves out of some | |
190 | /// L-value; i.e., "creates" uninitialized memory. | |
191 | /// | |
192 | /// With respect to dataflow analysis: | |
193 | /// - Generated by moves and declaration of uninitialized variables. | |
194 | /// - Killed by assignments to the memory. | |
195 | #[derive(Copy, Clone)] | |
196 | pub struct MoveOut { | |
197 | /// path being moved | |
198 | pub path: MovePathIndex, | |
199 | /// location of move | |
200 | pub source: Location, | |
201 | } | |
202 | ||
203 | impl fmt::Debug for MoveOut { | |
204 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { | |
9e0c209e | 205 | write!(fmt, "{:?}@{:?}", self.path, self.source) |
54a0048b SL |
206 | } |
207 | } | |
208 | ||
ff7c6d11 XL |
209 | /// `Init` represents a point in a program that initializes some L-value; |
210 | #[derive(Copy, Clone)] | |
211 | pub struct Init { | |
212 | /// path being initialized | |
213 | pub path: MovePathIndex, | |
b7449926 XL |
214 | /// location of initialization |
215 | pub location: InitLocation, | |
ff7c6d11 XL |
216 | /// Extra information about this initialization |
217 | pub kind: InitKind, | |
218 | } | |
219 | ||
b7449926 XL |
220 | |
221 | /// Initializations can be from an argument or from a statement. Arguments | |
222 | /// do not have locations, in those cases the `Local` is kept.. | |
223 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
224 | pub enum InitLocation { | |
225 | Argument(Local), | |
226 | Statement(Location), | |
227 | } | |
228 | ||
ff7c6d11 XL |
229 | /// Additional information about the initialization. |
230 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
231 | pub enum InitKind { | |
232 | /// Deep init, even on panic | |
233 | Deep, | |
234 | /// Only does a shallow init | |
235 | Shallow, | |
8faf50e0 | 236 | /// This doesn't initialize the variable on panic (and a panic is possible). |
ff7c6d11 XL |
237 | NonPanicPathOnly, |
238 | } | |
239 | ||
240 | impl fmt::Debug for Init { | |
241 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { | |
b7449926 XL |
242 | write!(fmt, "{:?}@{:?} ({:?})", self.path, self.location, self.kind) |
243 | } | |
244 | } | |
245 | ||
246 | impl Init { | |
247 | crate fn span<'gcx>(&self, mir: &Mir<'gcx>) -> Span { | |
248 | match self.location { | |
249 | InitLocation::Argument(local) => mir.local_decls[local].source_info.span, | |
250 | InitLocation::Statement(location) => mir.source_info(location).span, | |
251 | } | |
ff7c6d11 XL |
252 | } |
253 | } | |
254 | ||
2c00a5a8 | 255 | /// Tables mapping from a place to its MovePathIndex. |
3157f602 | 256 | #[derive(Debug)] |
54a0048b | 257 | pub struct MovePathLookup<'tcx> { |
c30ab7b3 | 258 | locals: IndexVec<Local, MovePathIndex>, |
54a0048b | 259 | |
ff7c6d11 XL |
260 | /// projections are made from a base-place and a projection |
261 | /// elem. The base-place will have a unique MovePathIndex; we use | |
54a0048b SL |
262 | /// the latter as the index into the outer vector (narrowing |
263 | /// subsequent search so that it is solely relative to that | |
ff7c6d11 | 264 | /// base-place). For the remaining lookup, we map the projection |
54a0048b | 265 | /// elem to the associated MovePathIndex. |
476ff2be | 266 | projections: FxHashMap<(MovePathIndex, AbstractElem<'tcx>), MovePathIndex> |
9e0c209e SL |
267 | } |
268 | ||
3b2f2976 | 269 | mod builder; |
54a0048b | 270 | |
9e0c209e SL |
271 | #[derive(Copy, Clone, Debug)] |
272 | pub enum LookupResult { | |
273 | Exact(MovePathIndex), | |
274 | Parent(Option<MovePathIndex>) | |
54a0048b SL |
275 | } |
276 | ||
277 | impl<'tcx> MovePathLookup<'tcx> { | |
278 | // Unlike the builder `fn move_path_for` below, this lookup | |
279 | // alternative will *not* create a MovePath on the fly for an | |
2c00a5a8 | 280 | // unknown place, but will rather return the nearest available |
9e0c209e | 281 | // parent. |
ff7c6d11 XL |
282 | pub fn find(&self, place: &Place<'tcx>) -> LookupResult { |
283 | match *place { | |
284 | Place::Local(local) => LookupResult::Exact(self.locals[local]), | |
8faf50e0 | 285 | Place::Promoted(_) | |
ff7c6d11 XL |
286 | Place::Static(..) => LookupResult::Parent(None), |
287 | Place::Projection(ref proj) => { | |
9e0c209e SL |
288 | match self.find(&proj.base) { |
289 | LookupResult::Exact(base_path) => { | |
290 | match self.projections.get(&(base_path, proj.elem.lift())) { | |
291 | Some(&subpath) => LookupResult::Exact(subpath), | |
292 | None => LookupResult::Parent(Some(base_path)) | |
293 | } | |
294 | } | |
295 | inexact => inexact | |
296 | } | |
54a0048b SL |
297 | } |
298 | } | |
299 | } | |
ff7c6d11 XL |
300 | |
301 | pub fn find_local(&self, local: Local) -> MovePathIndex { | |
302 | self.locals[local] | |
303 | } | |
54a0048b SL |
304 | } |
305 | ||
ea8adc8c XL |
306 | #[derive(Debug)] |
307 | pub struct IllegalMoveOrigin<'tcx> { | |
8faf50e0 | 308 | pub(crate) location: Location, |
ea8adc8c XL |
309 | pub(crate) kind: IllegalMoveOriginKind<'tcx>, |
310 | } | |
311 | ||
312 | #[derive(Debug)] | |
313 | pub(crate) enum IllegalMoveOriginKind<'tcx> { | |
94b46f34 | 314 | /// Illegal move due to attempt to move from `static` variable. |
ea8adc8c | 315 | Static, |
94b46f34 XL |
316 | |
317 | /// Illegal move due to attempt to move from behind a reference. | |
318 | BorrowedContent { | |
8faf50e0 XL |
319 | /// The place the reference refers to: if erroneous code was trying to |
320 | /// move from `(*x).f` this will be `*x`. | |
321 | target_place: Place<'tcx>, | |
94b46f34 XL |
322 | }, |
323 | ||
324 | /// Illegal move due to attempt to move from field of an ADT that | |
325 | /// implements `Drop`. Rust maintains invariant that all `Drop` | |
326 | /// ADT's remain fully-initialized so that user-defined destructor | |
327 | /// can safely read from all of the ADT's fields. | |
ea8adc8c | 328 | InteriorOfTypeWithDestructor { container_ty: ty::Ty<'tcx> }, |
94b46f34 XL |
329 | |
330 | /// Illegal move due to attempt to move out of a slice or array. | |
abe05a73 | 331 | InteriorOfSliceOrArray { ty: ty::Ty<'tcx>, is_index: bool, }, |
ea8adc8c XL |
332 | } |
333 | ||
334 | #[derive(Debug)] | |
335 | pub enum MoveError<'tcx> { | |
336 | IllegalMove { cannot_move_out_of: IllegalMoveOrigin<'tcx> }, | |
337 | UnionMove { path: MovePathIndex }, | |
338 | } | |
339 | ||
340 | impl<'tcx> MoveError<'tcx> { | |
8faf50e0 XL |
341 | fn cannot_move_out_of(location: Location, kind: IllegalMoveOriginKind<'tcx>) -> Self { |
342 | let origin = IllegalMoveOrigin { location, kind }; | |
ea8adc8c XL |
343 | MoveError::IllegalMove { cannot_move_out_of: origin } |
344 | } | |
345 | } | |
346 | ||
abe05a73 | 347 | impl<'a, 'gcx, 'tcx> MoveData<'tcx> { |
ff7c6d11 | 348 | pub fn gather_moves(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'gcx, 'tcx>) |
b7449926 | 349 | -> Result<Self, (Self, Vec<(Place<'tcx>, MoveError<'tcx>)>)> { |
ff7c6d11 | 350 | builder::gather_moves(mir, tcx) |
54a0048b | 351 | } |
b7449926 XL |
352 | |
353 | /// For the move path `mpi`, returns the root local variable (if any) that starts the path. | |
354 | /// (e.g., for a path like `a.b.c` returns `Some(a)`) | |
355 | pub fn base_local(&self, mut mpi: MovePathIndex) -> Option<Local> { | |
356 | loop { | |
357 | let path = &self.move_paths[mpi]; | |
358 | if let Place::Local(l) = path.place { return Some(l); } | |
359 | if let Some(parent) = path.parent { mpi = parent; continue } else { return None } | |
360 | } | |
361 | } | |
54a0048b | 362 | } |