src/librustc_borrowck/borrowck/mir/gather_moves.rs

   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
  12 use rustc::ty::{self, TyCtxt, ParameterEnvironment};
  13 use rustc::mir::*;
  14 use rustc::util::nodemap::FxHashMap;
  15 use rustc_data_structures::indexed_vec::{IndexVec};
  16
  17 use syntax::codemap::DUMMY_SP;
  18
  19 use std::collections::hash_map::Entry;
  20 use std::fmt;
  21 use std::mem;
  22 use std::ops::{Index, IndexMut};
  23
  24 use super::abs_domain::{AbstractElem, Lift};
  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).
  31 mod indexes {
  32     use std::fmt;
  33     use core::nonzero::NonZero;
  34     use rustc_data_structures::indexed_vec::Idx;
  35
  36     macro_rules! new_index {
  37         ($Index:ident, $debug_name:expr) => {
  38             #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  39             pub struct $Index(NonZero<usize>);
  40
  41             impl Idx for $Index {
  42                 fn new(idx: usize) -> Self {
  43                     unsafe { $Index(NonZero::new(idx + 1)) }
  44                 }
  45                 fn index(self) -> usize {
  46                     self.0.get() - 1
  47                 }
  48             }
  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             }
  55         }
  56     }
  57
  58     /// Index into MovePathData.move_paths
  59     new_index!(MovePathIndex, "mp");
  60
  61     /// Index into MoveData.moves.
  62     new_index!(MoveOutIndex, "mo");
  63 }
  64
  65 pub use self::indexes::MovePathIndex;
  66 pub use self::indexes::MoveOutIndex;
  67
  68 impl self::indexes::MoveOutIndex {
  69     pub fn move_path_index(&self, move_data: &MoveData) -> MovePathIndex {
  70         move_data.moves[*self].path
  71     }
  72 }
  73
  74 /// `MovePath` is a canonicalized representation of a path that is
  75 /// moved or assigned to.
  76 ///
  77 /// It follows a tree structure.
  78 ///
  79 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
  80 /// move *out* of the l-value `x.m`.
  81 ///
  82 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
  83 /// one of them will link to the other via the `next_sibling` field,
  84 /// and the other will have no entry in its `next_sibling` field), and
  85 /// they both have the MovePath representing `x` as their parent.
  86 #[derive(Clone)]
  87 pub struct MovePath<'tcx> {
  88     pub next_sibling: Option<MovePathIndex>,
  89     pub first_child: Option<MovePathIndex>,
  90     pub parent: Option<MovePathIndex>,
  91     pub lvalue: Lvalue<'tcx>,
  92 }
  93
  94 impl<'tcx> fmt::Debug for MovePath<'tcx> {
  95     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
  96         write!(w, "MovePath {{")?;
  97         if let Some(parent) = self.parent {
  98             write!(w, " parent: {:?},", parent)?;
  99         }
 100         if let Some(first_child) = self.first_child {
 101             write!(w, " first_child: {:?},", first_child)?;
 102         }
 103         if let Some(next_sibling) = self.next_sibling {
 104             write!(w, " next_sibling: {:?}", next_sibling)?;
 105         }
 106         write!(w, " lvalue: {:?} }}", self.lvalue)
 107     }
 108 }
 109
 110 #[derive(Debug)]
 111 pub struct MoveData<'tcx> {
 112     pub move_paths: IndexVec<MovePathIndex, MovePath<'tcx>>,
 113     pub moves: IndexVec<MoveOutIndex, MoveOut>,
 114     /// Each Location `l` is mapped to the MoveOut's that are effects
 115     /// of executing the code at `l`. (There can be multiple MoveOut's
 116     /// for a given `l` because each MoveOut is associated with one
 117     /// particular path being moved.)
 118     pub loc_map: LocationMap<Vec<MoveOutIndex>>,
 119     pub path_map: IndexVec<MovePathIndex, Vec<MoveOutIndex>>,
 120     pub rev_lookup: MovePathLookup<'tcx>,
 121 }
 122
 123 pub trait HasMoveData<'tcx> {
 124     fn move_data(&self) -> &MoveData<'tcx>;
 125 }
 126
 127 #[derive(Debug)]
 128 pub struct LocationMap<T> {
 129     /// Location-indexed (BasicBlock for outer index, index within BB
 130     /// for inner index) map.
 131     map: IndexVec<BasicBlock, Vec<T>>,
 132 }
 133
 134 impl<T> Index<Location> for LocationMap<T> {
 135     type Output = T;
 136     fn index(&self, index: Location) -> &Self::Output {
 137         &self.map[index.block][index.statement_index]
 138     }
 139 }
 140
 141 impl<T> IndexMut<Location> for LocationMap<T> {
 142     fn index_mut(&mut self, index: Location) -> &mut Self::Output {
 143         &mut self.map[index.block][index.statement_index]
 144     }
 145 }
 146
 147 impl<T> LocationMap<T> where T: Default + Clone {
 148     fn new(mir: &Mir) -> Self {
 149         LocationMap {
 150             map: mir.basic_blocks().iter().map(|block| {
 151                 vec![T::default(); block.statements.len()+1]
 152             }).collect()
 153         }
 154     }
 155 }
 156
 157 /// `MoveOut` represents a point in a program that moves out of some
 158 /// L-value; i.e., "creates" uninitialized memory.
 159 ///
 160 /// With respect to dataflow analysis:
 161 /// - Generated by moves and declaration of uninitialized variables.
 162 /// - Killed by assignments to the memory.
 163 #[derive(Copy, Clone)]
 164 pub struct MoveOut {
 165     /// path being moved
 166     pub path: MovePathIndex,
 167     /// location of move
 168     pub source: Location,
 169 }
 170
 171 impl fmt::Debug for MoveOut {
 172     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 173         write!(fmt, "{:?}@{:?}", self.path, self.source)
 174     }
 175 }
 176
 177 /// Tables mapping from an l-value to its MovePathIndex.
 178 #[derive(Debug)]
 179 pub struct MovePathLookup<'tcx> {
 180     locals: IndexVec<Local, MovePathIndex>,
 181
 182     /// projections are made from a base-lvalue and a projection
 183     /// elem. The base-lvalue will have a unique MovePathIndex; we use
 184     /// the latter as the index into the outer vector (narrowing
 185     /// subsequent search so that it is solely relative to that
 186     /// base-lvalue). For the remaining lookup, we map the projection
 187     /// elem to the associated MovePathIndex.
 188     projections: FxHashMap<(MovePathIndex, AbstractElem<'tcx>), MovePathIndex>
 189 }
 190
 191 struct MoveDataBuilder<'a, 'tcx: 'a> {
 192     mir: &'a Mir<'tcx>,
 193     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 194     param_env: &'a ParameterEnvironment<'tcx>,
 195     data: MoveData<'tcx>,
 196 }
 197
 198 pub enum MovePathError {
 199     IllegalMove,
 200     UnionMove { path: MovePathIndex },
 201 }
 202
 203 impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> {
 204     fn new(mir: &'a Mir<'tcx>,
 205            tcx: TyCtxt<'a, 'tcx, 'tcx>,
 206            param_env: &'a ParameterEnvironment<'tcx>)
 207            -> Self {
 208         let mut move_paths = IndexVec::new();
 209         let mut path_map = IndexVec::new();
 210
 211         MoveDataBuilder {
 212             mir: mir,
 213             tcx: tcx,
 214             param_env: param_env,
 215             data: MoveData {
 216                 moves: IndexVec::new(),
 217                 loc_map: LocationMap::new(mir),
 218                 rev_lookup: MovePathLookup {
 219                     locals: mir.local_decls.indices().map(Lvalue::Local).map(|v| {
 220                         Self::new_move_path(&mut move_paths, &mut path_map, None, v)
 221                     }).collect(),
 222                     projections: FxHashMap(),
 223                 },
 224                 move_paths: move_paths,
 225                 path_map: path_map,
 226             }
 227         }
 228     }
 229
 230     fn new_move_path(move_paths: &mut IndexVec<MovePathIndex, MovePath<'tcx>>,
 231                      path_map: &mut IndexVec<MovePathIndex, Vec<MoveOutIndex>>,
 232                      parent: Option<MovePathIndex>,
 233                      lvalue: Lvalue<'tcx>)
 234                      -> MovePathIndex
 235     {
 236         let move_path = move_paths.push(MovePath {
 237             next_sibling: None,
 238             first_child: None,
 239             parent: parent,
 240             lvalue: lvalue
 241         });
 242
 243         if let Some(parent) = parent {
 244             let next_sibling =
 245                 mem::replace(&mut move_paths[parent].first_child, Some(move_path));
 246             move_paths[move_path].next_sibling = next_sibling;
 247         }
 248
 249         let path_map_ent = path_map.push(vec![]);
 250         assert_eq!(path_map_ent, move_path);
 251         move_path
 252     }
 253
 254     /// This creates a MovePath for a given lvalue, returning an `MovePathError`
 255     /// if that lvalue can't be moved from.
 256     ///
 257     /// NOTE: lvalues behind references *do not* get a move path, which is
 258     /// problematic for borrowck.
 259     ///
 260     /// Maybe we should have seperate "borrowck" and "moveck" modes.
 261     fn move_path_for(&mut self, lval: &Lvalue<'tcx>)
 262                      -> Result<MovePathIndex, MovePathError>
 263     {
 264         debug!("lookup({:?})", lval);
 265         match *lval {
 266             Lvalue::Local(local) => Ok(self.data.rev_lookup.locals[local]),
 267             // error: can't move out of a static
 268             Lvalue::Static(..) => Err(MovePathError::IllegalMove),
 269             Lvalue::Projection(ref proj) => {
 270                 self.move_path_for_projection(lval, proj)
 271             }
 272         }
 273     }
 274
 275     fn create_move_path(&mut self, lval: &Lvalue<'tcx>) {
 276         // This is an assignment, not a move, so this not being a valid
 277         // move path is OK.
 278         let _ = self.move_path_for(lval);
 279     }
 280
 281     fn move_path_for_projection(&mut self,
 282                                 lval: &Lvalue<'tcx>,
 283                                 proj: &LvalueProjection<'tcx>)
 284                                 -> Result<MovePathIndex, MovePathError>
 285     {
 286         let base = try!(self.move_path_for(&proj.base));
 287         let lv_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 288         match lv_ty.sty {
 289             // error: can't move out of borrowed content
 290             ty::TyRef(..) | ty::TyRawPtr(..) => return Err(MovePathError::IllegalMove),
 291             // error: can't move out of struct with destructor
 292             ty::TyAdt(adt, _) if adt.has_dtor(self.tcx) && !adt.is_box() =>
 293                 return Err(MovePathError::IllegalMove),
 294             // move out of union - always move the entire union
 295             ty::TyAdt(adt, _) if adt.is_union() =>
 296                 return Err(MovePathError::UnionMove { path: base }),
 297             // error: can't move out of a slice
 298             ty::TySlice(..) =>
 299                 return Err(MovePathError::IllegalMove),
 300             ty::TyArray(..) => match proj.elem {
 301                 // error: can't move out of an array
 302                 ProjectionElem::Index(..) => return Err(MovePathError::IllegalMove),
 303                 _ => {
 304                     // FIXME: still badly broken
 305                 }
 306             },
 307             _ => {}
 308         };
 309         match self.data.rev_lookup.projections.entry((base, proj.elem.lift())) {
 310             Entry::Occupied(ent) => Ok(*ent.get()),
 311             Entry::Vacant(ent) => {
 312                 let path = Self::new_move_path(
 313                     &mut self.data.move_paths,
 314                     &mut self.data.path_map,
 315                     Some(base),
 316                     lval.clone()
 317                 );
 318                 ent.insert(path);
 319                 Ok(path)
 320             }
 321         }
 322     }
 323
 324     fn finalize(self) -> MoveData<'tcx> {
 325         debug!("{}", {
 326             debug!("moves for {:?}:", self.mir.span);
 327             for (j, mo) in self.data.moves.iter_enumerated() {
 328                 debug!("    {:?} = {:?}", j, mo);
 329             }
 330             debug!("move paths for {:?}:", self.mir.span);
 331             for (j, path) in self.data.move_paths.iter_enumerated() {
 332                 debug!("    {:?} = {:?}", j, path);
 333             }
 334             "done dumping moves"
 335         });
 336         self.data
 337     }
 338 }
 339
 340 #[derive(Copy, Clone, Debug)]
 341 pub enum LookupResult {
 342     Exact(MovePathIndex),
 343     Parent(Option<MovePathIndex>)
 344 }
 345
 346 impl<'tcx> MovePathLookup<'tcx> {
 347     // Unlike the builder `fn move_path_for` below, this lookup
 348     // alternative will *not* create a MovePath on the fly for an
 349     // unknown l-value, but will rather return the nearest available
 350     // parent.
 351     pub fn find(&self, lval: &Lvalue<'tcx>) -> LookupResult {
 352         match *lval {
 353             Lvalue::Local(local) => LookupResult::Exact(self.locals[local]),
 354             Lvalue::Static(..) => LookupResult::Parent(None),
 355             Lvalue::Projection(ref proj) => {
 356                 match self.find(&proj.base) {
 357                     LookupResult::Exact(base_path) => {
 358                         match self.projections.get(&(base_path, proj.elem.lift())) {
 359                             Some(&subpath) => LookupResult::Exact(subpath),
 360                             None => LookupResult::Parent(Some(base_path))
 361                         }
 362                     }
 363                     inexact => inexact
 364                 }
 365             }
 366         }
 367     }
 368 }
 369
 370 impl<'a, 'tcx> MoveData<'tcx> {
 371     pub fn gather_moves(mir: &Mir<'tcx>,
 372                         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 373                         param_env: &ParameterEnvironment<'tcx>)
 374                         -> Self {
 375         gather_moves(mir, tcx, param_env)
 376     }
 377 }
 378
 379 fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>,
 380                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
 381                           param_env: &ParameterEnvironment<'tcx>)
 382                           -> MoveData<'tcx> {
 383     let mut builder = MoveDataBuilder::new(mir, tcx, param_env);
 384
 385     for (bb, block) in mir.basic_blocks().iter_enumerated() {
 386         for (i, stmt) in block.statements.iter().enumerate() {
 387             let source = Location { block: bb, statement_index: i };
 388             builder.gather_statement(source, stmt);
 389         }
 390
 391         let terminator_loc = Location {
 392             block: bb,
 393             statement_index: block.statements.len()
 394         };
 395         builder.gather_terminator(terminator_loc, block.terminator());
 396     }
 397
 398     builder.finalize()
 399 }
 400
 401 impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> {
 402     fn gather_statement(&mut self, loc: Location, stmt: &Statement<'tcx>) {
 403         debug!("gather_statement({:?}, {:?})", loc, stmt);
 404         match stmt.kind {
 405             StatementKind::Assign(ref lval, ref rval) => {
 406                 self.create_move_path(lval);
 407                 self.gather_rvalue(loc, rval);
 408             }
 409             StatementKind::StorageLive(_) |
 410             StatementKind::StorageDead(_) => {}
 411             StatementKind::SetDiscriminant{ .. } => {
 412                 span_bug!(stmt.source_info.span,
 413                           "SetDiscriminant should not exist during borrowck");
 414             }
 415             StatementKind::InlineAsm { .. } |
 416             StatementKind::Nop => {}
 417         }
 418     }
 419
 420     fn gather_rvalue(&mut self, loc: Location, rvalue: &Rvalue<'tcx>) {
 421         match *rvalue {
 422             Rvalue::Use(ref operand) |
 423             Rvalue::Repeat(ref operand, _) |
 424             Rvalue::Cast(_, ref operand, _) |
 425             Rvalue::UnaryOp(_, ref operand) => {
 426                 self.gather_operand(loc, operand)
 427             }
 428             Rvalue::BinaryOp(ref _binop, ref lhs, ref rhs) |
 429             Rvalue::CheckedBinaryOp(ref _binop, ref lhs, ref rhs) => {
 430                 self.gather_operand(loc, lhs);
 431                 self.gather_operand(loc, rhs);
 432             }
 433             Rvalue::Aggregate(ref _kind, ref operands) => {
 434                 for operand in operands {
 435                     self.gather_operand(loc, operand);
 436                 }
 437             }
 438             Rvalue::Ref(..) |
 439             Rvalue::Discriminant(..) |
 440             Rvalue::Len(..) |
 441             Rvalue::Box(..) => {
 442                 // This returns an rvalue with uninitialized contents. We can't
 443                 // move out of it here because it is an rvalue - assignments always
 444                 // completely initialize their lvalue.
 445                 //
 446                 // However, this does not matter - MIR building is careful to
 447                 // only emit a shallow free for the partially-initialized
 448                 // temporary.
 449                 //
 450                 // In any case, if we want to fix this, we have to register a
 451                 // special move and change the `statement_effect` functions.
 452             }
 453         }
 454     }
 455
 456     fn gather_terminator(&mut self, loc: Location, term: &Terminator<'tcx>) {
 457         debug!("gather_terminator({:?}, {:?})", loc, term);
 458         match term.kind {
 459             TerminatorKind::Goto { target: _ } |
 460             TerminatorKind::Resume |
 461             TerminatorKind::Unreachable => { }
 462
 463             TerminatorKind::Return => {
 464                 self.gather_move(loc, &Lvalue::Local(RETURN_POINTER));
 465             }
 466
 467             TerminatorKind::Assert { .. } |
 468             TerminatorKind::SwitchInt { .. } => {
 469                 // branching terminators - these don't move anything
 470             }
 471
 472             TerminatorKind::Drop { ref location, target: _, unwind: _ } => {
 473                 self.gather_move(loc, location);
 474             }
 475             TerminatorKind::DropAndReplace { ref location, ref value, .. } => {
 476                 self.create_move_path(location);
 477                 self.gather_operand(loc, value);
 478             }
 479             TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
 480                 self.gather_operand(loc, func);
 481                 for arg in args {
 482                     self.gather_operand(loc, arg);
 483                 }
 484                 if let Some((ref destination, _bb)) = *destination {
 485                     self.create_move_path(destination);
 486                 }
 487             }
 488         }
 489     }
 490
 491     fn gather_operand(&mut self, loc: Location, operand: &Operand<'tcx>) {
 492         match *operand {
 493             Operand::Constant(..) => {} // not-a-move
 494             Operand::Consume(ref lval) => { // a move
 495                 self.gather_move(loc, lval);
 496             }
 497         }
 498     }
 499
 500     fn gather_move(&mut self, loc: Location, lval: &Lvalue<'tcx>) {
 501         debug!("gather_move({:?}, {:?})", loc, lval);
 502
 503         let lv_ty = lval.ty(self.mir, self.tcx).to_ty(self.tcx);
 504         if !lv_ty.moves_by_default(self.tcx, self.param_env, DUMMY_SP) {
 505             debug!("gather_move({:?}, {:?}) - {:?} is Copy. skipping", loc, lval, lv_ty);
 506             return
 507         }
 508
 509         let path = match self.move_path_for(lval) {
 510             Ok(path) | Err(MovePathError::UnionMove { path }) => path,
 511             Err(MovePathError::IllegalMove) => {
 512                 // Moving out of a bad path. Eventually, this should be a MIR
 513                 // borrowck error instead of a bug.
 514                 span_bug!(self.mir.span,
 515                           "Broken MIR: moving out of lvalue {:?}: {:?} at {:?}",
 516                           lval, lv_ty, loc);
 517             }
 518         };
 519         let move_out = self.data.moves.push(MoveOut { path: path, source: loc });
 520
 521         debug!("gather_move({:?}, {:?}): adding move {:?} of {:?}",
 522                loc, lval, move_out, path);
 523
 524         self.data.path_map[path].push(move_out);
 525         self.data.loc_map[loc].push(move_out);
 526     }
 527 }