compiler/rustc_mir_dataflow/src/move_paths/mod.rs

   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 }