1 use rustc::ty::{Ty, TyCtxt};
3 use rustc::util::nodemap::FxHashMap;
4 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
5 use smallvec::SmallVec;
6 use syntax_pos::{Span};
9 use std::ops::{Index, IndexMut};
11 use self::abs_domain::{AbstractElem, Lift};
16 pub struct MovePathIndex {
22 pub struct MoveOutIndex {
28 pub struct InitIndex {
34 pub fn move_path_index(&self, move_data: &MoveData<'_>) -> MovePathIndex {
35 move_data.moves[*self].path
39 /// `MovePath` is a canonicalized representation of a path that is
40 /// moved or assigned to.
42 /// It follows a tree structure.
44 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
45 /// move *out* of the place `x.m`.
47 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
48 /// one of them will link to the other via the `next_sibling` field,
49 /// and the other will have no entry in its `next_sibling` field), and
50 /// they both have the MovePath representing `x` as their parent.
52 pub struct MovePath<'tcx> {
53 pub next_sibling: Option<MovePathIndex>,
54 pub first_child: Option<MovePathIndex>,
55 pub parent: Option<MovePathIndex>,
56 pub place: Place<'tcx>,
59 impl<'tcx> MovePath<'tcx> {
62 move_paths: &IndexVec<MovePathIndex, MovePath<'_>>,
63 ) -> Vec<MovePathIndex> {
64 let mut parents = Vec::new();
66 let mut curr_parent = self.parent;
67 while let Some(parent_mpi) = curr_parent {
68 parents.push(parent_mpi);
69 curr_parent = move_paths[parent_mpi].parent;
76 impl<'tcx> fmt::Debug for MovePath<'tcx> {
77 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
78 write!(w, "MovePath {{")?;
79 if let Some(parent) = self.parent {
80 write!(w, " parent: {:?},", parent)?;
82 if let Some(first_child) = self.first_child {
83 write!(w, " first_child: {:?},", first_child)?;
85 if let Some(next_sibling) = self.next_sibling {
86 write!(w, " next_sibling: {:?}", next_sibling)?;
88 write!(w, " place: {:?} }}", self.place)
92 impl<'tcx> fmt::Display for MovePath<'tcx> {
93 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
94 write!(w, "{:?}", self.place)
99 pub struct MoveData<'tcx> {
100 pub move_paths: IndexVec<MovePathIndex, MovePath<'tcx>>,
101 pub moves: IndexVec<MoveOutIndex, MoveOut>,
102 /// Each Location `l` is mapped to the MoveOut's that are effects
103 /// of executing the code at `l`. (There can be multiple MoveOut's
104 /// for a given `l` because each MoveOut is associated with one
105 /// particular path being moved.)
106 pub loc_map: LocationMap<SmallVec<[MoveOutIndex; 4]>>,
107 pub path_map: IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>,
108 pub rev_lookup: MovePathLookup,
109 pub inits: IndexVec<InitIndex, Init>,
110 /// Each Location `l` is mapped to the Inits that are effects
111 /// of executing the code at `l`.
112 pub init_loc_map: LocationMap<SmallVec<[InitIndex; 4]>>,
113 pub init_path_map: IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>,
116 pub trait HasMoveData<'tcx> {
117 fn move_data(&self) -> &MoveData<'tcx>;
121 pub struct LocationMap<T> {
122 /// Location-indexed (BasicBlock for outer index, index within BB
123 /// for inner index) map.
124 pub(crate) map: IndexVec<BasicBlock, Vec<T>>,
127 impl<T> Index<Location> for LocationMap<T> {
129 fn index(&self, index: Location) -> &Self::Output {
130 &self.map[index.block][index.statement_index]
134 impl<T> IndexMut<Location> for LocationMap<T> {
135 fn index_mut(&mut self, index: Location) -> &mut Self::Output {
136 &mut self.map[index.block][index.statement_index]
140 impl<T> LocationMap<T> where T: Default + Clone {
141 fn new(mir: &Mir<'_>) -> Self {
143 map: mir.basic_blocks().iter().map(|block| {
144 vec![T::default(); block.statements.len()+1]
150 /// `MoveOut` represents a point in a program that moves out of some
151 /// L-value; i.e., "creates" uninitialized memory.
153 /// With respect to dataflow analysis:
154 /// - Generated by moves and declaration of uninitialized variables.
155 /// - Killed by assignments to the memory.
156 #[derive(Copy, Clone)]
159 pub path: MovePathIndex,
161 pub source: Location,
164 impl fmt::Debug for MoveOut {
165 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
166 write!(fmt, "{:?}@{:?}", self.path, self.source)
170 /// `Init` represents a point in a program that initializes some L-value;
171 #[derive(Copy, Clone)]
173 /// path being initialized
174 pub path: MovePathIndex,
175 /// location of initialization
176 pub location: InitLocation,
177 /// Extra information about this initialization
182 /// Initializations can be from an argument or from a statement. Arguments
183 /// do not have locations, in those cases the `Local` is kept..
184 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
185 pub enum InitLocation {
190 /// Additional information about the initialization.
191 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
193 /// Deep init, even on panic
195 /// Only does a shallow init
197 /// This doesn't initialize the variable on panic (and a panic is possible).
201 impl fmt::Debug for Init {
202 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
203 write!(fmt, "{:?}@{:?} ({:?})", self.path, self.location, self.kind)
208 crate fn span<'gcx>(&self, mir: &Mir<'gcx>) -> Span {
209 match self.location {
210 InitLocation::Argument(local) => mir.local_decls[local].source_info.span,
211 InitLocation::Statement(location) => mir.source_info(location).span,
216 /// Tables mapping from a place to its MovePathIndex.
218 pub struct MovePathLookup {
219 locals: IndexVec<Local, MovePathIndex>,
221 /// projections are made from a base-place and a projection
222 /// elem. The base-place will have a unique MovePathIndex; we use
223 /// the latter as the index into the outer vector (narrowing
224 /// subsequent search so that it is solely relative to that
225 /// base-place). For the remaining lookup, we map the projection
226 /// elem to the associated MovePathIndex.
227 projections: FxHashMap<(MovePathIndex, AbstractElem), MovePathIndex>
232 #[derive(Copy, Clone, Debug)]
233 pub enum LookupResult {
234 Exact(MovePathIndex),
235 Parent(Option<MovePathIndex>)
238 impl MovePathLookup {
239 // Unlike the builder `fn move_path_for` below, this lookup
240 // alternative will *not* create a MovePath on the fly for an
241 // unknown place, but will rather return the nearest available
243 pub fn find(&self, place: &Place<'tcx>) -> LookupResult {
245 Place::Base(PlaceBase::Local(local)) => LookupResult::Exact(self.locals[local]),
246 Place::Base(PlaceBase::Static(..)) => LookupResult::Parent(None),
247 Place::Projection(ref proj) => {
248 match self.find(&proj.base) {
249 LookupResult::Exact(base_path) => {
250 match self.projections.get(&(base_path, proj.elem.lift())) {
251 Some(&subpath) => LookupResult::Exact(subpath),
252 None => LookupResult::Parent(Some(base_path))
261 pub fn find_local(&self, local: Local) -> MovePathIndex {
267 pub struct IllegalMoveOrigin<'tcx> {
268 pub(crate) location: Location,
269 pub(crate) kind: IllegalMoveOriginKind<'tcx>,
273 pub(crate) enum IllegalMoveOriginKind<'tcx> {
274 /// Illegal move due to attempt to move from `static` variable.
277 /// Illegal move due to attempt to move from behind a reference.
279 /// The place the reference refers to: if erroneous code was trying to
280 /// move from `(*x).f` this will be `*x`.
281 target_place: Place<'tcx>,
284 /// Illegal move due to attempt to move from field of an ADT that
285 /// implements `Drop`. Rust maintains invariant that all `Drop`
286 /// ADT's remain fully-initialized so that user-defined destructor
287 /// can safely read from all of the ADT's fields.
288 InteriorOfTypeWithDestructor { container_ty: Ty<'tcx> },
290 /// Illegal move due to attempt to move out of a slice or array.
291 InteriorOfSliceOrArray { ty: Ty<'tcx>, is_index: bool, },
295 pub enum MoveError<'tcx> {
296 IllegalMove { cannot_move_out_of: IllegalMoveOrigin<'tcx> },
297 UnionMove { path: MovePathIndex },
300 impl<'tcx> MoveError<'tcx> {
301 fn cannot_move_out_of(location: Location, kind: IllegalMoveOriginKind<'tcx>) -> Self {
302 let origin = IllegalMoveOrigin { location, kind };
303 MoveError::IllegalMove { cannot_move_out_of: origin }
307 impl<'a, 'gcx, 'tcx> MoveData<'tcx> {
308 pub fn gather_moves(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'gcx, 'tcx>)
309 -> Result<Self, (Self, Vec<(Place<'tcx>, MoveError<'tcx>)>)> {
310 builder::gather_moves(mir, tcx)
313 /// For the move path `mpi`, returns the root local variable (if any) that starts the path.
314 /// (e.g., for a path like `a.b.c` returns `Some(a)`)
315 pub fn base_local(&self, mut mpi: MovePathIndex) -> Option<Local> {
317 let path = &self.move_paths[mpi];
318 if let Place::Base(PlaceBase::Local(l)) = path.place { return Some(l); }
319 if let Some(parent) = path.parent { mpi = parent; continue } else { return None }