src/librustc_mir/dataflow/move_paths/builder.rs

   1 // Copyright 2017 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 use rustc::ty::{self, TyCtxt};
  12 use rustc::mir::*;
  13 use rustc::mir::tcx::RvalueInitializationState;
  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::mem;
  21
  22 use super::abs_domain::Lift;
  23
  24 use super::{LocationMap, MoveData, MovePath, MovePathLookup, MovePathIndex, MoveOut, MoveOutIndex};
  25
  26 pub(super) struct MoveDataBuilder<'a, 'tcx: 'a> {
  27     mir: &'a Mir<'tcx>,
  28     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  29     param_env: ty::ParamEnv<'tcx>,
  30     data: MoveData<'tcx>,
  31 }
  32
  33 pub enum MovePathError {
  34     IllegalMove,
  35     UnionMove { path: MovePathIndex },
  36 }
  37
  38 impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> {
  39     fn new(mir: &'a Mir<'tcx>,
  40            tcx: TyCtxt<'a, 'tcx, 'tcx>,
  41            param_env: ty::ParamEnv<'tcx>)
  42            -> Self {
  43         let mut move_paths = IndexVec::new();
  44         let mut path_map = IndexVec::new();
  45
  46         MoveDataBuilder {
  47             mir,
  48             tcx,
  49             param_env,
  50             data: MoveData {
  51                 moves: IndexVec::new(),
  52                 loc_map: LocationMap::new(mir),
  53                 rev_lookup: MovePathLookup {
  54                     locals: mir.local_decls.indices().map(Lvalue::Local).map(|v| {
  55                         Self::new_move_path(&mut move_paths, &mut path_map, None, v)
  56                     }).collect(),
  57                     projections: FxHashMap(),
  58                 },
  59                 move_paths,
  60                 path_map,
  61             }
  62         }
  63     }
  64
  65     fn new_move_path(move_paths: &mut IndexVec<MovePathIndex, MovePath<'tcx>>,
  66                      path_map: &mut IndexVec<MovePathIndex, Vec<MoveOutIndex>>,
  67                      parent: Option<MovePathIndex>,
  68                      lvalue: Lvalue<'tcx>)
  69                      -> MovePathIndex
  70     {
  71         let move_path = move_paths.push(MovePath {
  72             next_sibling: None,
  73             first_child: None,
  74             parent,
  75             lvalue,
  76         });
  77
  78         if let Some(parent) = parent {
  79             let next_sibling =
  80                 mem::replace(&mut move_paths[parent].first_child, Some(move_path));
  81             move_paths[move_path].next_sibling = next_sibling;
  82         }
  83
  84         let path_map_ent = path_map.push(vec![]);
  85         assert_eq!(path_map_ent, move_path);
  86         move_path
  87     }
  88
  89     /// This creates a MovePath for a given lvalue, returning an `MovePathError`
  90     /// if that lvalue can't be moved from.
  91     ///
  92     /// NOTE: lvalues behind references *do not* get a move path, which is
  93     /// problematic for borrowck.
  94     ///
  95     /// Maybe we should have separate "borrowck" and "moveck" modes.
  96     fn move_path_for(&mut self, lval: &Lvalue<'tcx>)
  97                      -> Result<MovePathIndex, MovePathError>
  98     {
  99         debug!("lookup({:?})", lval);
 100         match *lval {
 101             Lvalue::Local(local) => Ok(self.data.rev_lookup.locals[local]),
 102             // error: can't move out of a static
 103             Lvalue::Static(..) => Err(MovePathError::IllegalMove),
 104             Lvalue::Projection(ref proj) => {
 105                 self.move_path_for_projection(lval, proj)
 106             }
 107         }
 108     }
 109
 110     fn create_move_path(&mut self, lval: &Lvalue<'tcx>) {
 111         // This is an assignment, not a move, so this not being a valid
 112         // move path is OK.
 113         let _ = self.move_path_for(lval);
 114     }
 115
 116     fn move_path_for_projection(&mut self,
 117                                 lval: &Lvalue<'tcx>,
 118                                 proj: &LvalueProjection<'tcx>)
 119                                 -> Result<MovePathIndex, MovePathError>
 120     {
 121         let base = try!(self.move_path_for(&proj.base));
 122         let lv_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 123         match lv_ty.sty {
 124             // error: can't move out of borrowed content
 125             ty::TyRef(..) | ty::TyRawPtr(..) => return Err(MovePathError::IllegalMove),
 126             // error: can't move out of struct with destructor
 127             ty::TyAdt(adt, _) if adt.has_dtor(self.tcx) && !adt.is_box() =>
 128                 return Err(MovePathError::IllegalMove),
 129             // move out of union - always move the entire union
 130             ty::TyAdt(adt, _) if adt.is_union() =>
 131                 return Err(MovePathError::UnionMove { path: base }),
 132             // error: can't move out of a slice
 133             ty::TySlice(..) =>
 134                 return Err(MovePathError::IllegalMove),
 135             ty::TyArray(..) => match proj.elem {
 136                 // error: can't move out of an array
 137                 ProjectionElem::Index(..) => return Err(MovePathError::IllegalMove),
 138                 _ => {
 139                     // FIXME: still badly broken
 140                 }
 141             },
 142             _ => {}
 143         };
 144         match self.data.rev_lookup.projections.entry((base, proj.elem.lift())) {
 145             Entry::Occupied(ent) => Ok(*ent.get()),
 146             Entry::Vacant(ent) => {
 147                 let path = Self::new_move_path(
 148                     &mut self.data.move_paths,
 149                     &mut self.data.path_map,
 150                     Some(base),
 151                     lval.clone()
 152                 );
 153                 ent.insert(path);
 154                 Ok(path)
 155             }
 156         }
 157     }
 158
 159     fn finalize(self) -> MoveData<'tcx> {
 160         debug!("{}", {
 161             debug!("moves for {:?}:", self.mir.span);
 162             for (j, mo) in self.data.moves.iter_enumerated() {
 163                 debug!("    {:?} = {:?}", j, mo);
 164             }
 165             debug!("move paths for {:?}:", self.mir.span);
 166             for (j, path) in self.data.move_paths.iter_enumerated() {
 167                 debug!("    {:?} = {:?}", j, path);
 168             }
 169             "done dumping moves"
 170         });
 171         self.data
 172     }
 173 }
 174
 175 pub(super) fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>,
 176                                      tcx: TyCtxt<'a, 'tcx, 'tcx>,
 177                                      param_env: ty::ParamEnv<'tcx>)
 178                                      -> MoveData<'tcx> {
 179     let mut builder = MoveDataBuilder::new(mir, tcx, param_env);
 180
 181     for (bb, block) in mir.basic_blocks().iter_enumerated() {
 182         for (i, stmt) in block.statements.iter().enumerate() {
 183             let source = Location { block: bb, statement_index: i };
 184             builder.gather_statement(source, stmt);
 185         }
 186
 187         let terminator_loc = Location {
 188             block: bb,
 189             statement_index: block.statements.len()
 190         };
 191         builder.gather_terminator(terminator_loc, block.terminator());
 192     }
 193
 194     builder.finalize()
 195 }
 196
 197 impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> {
 198     fn gather_statement(&mut self, loc: Location, stmt: &Statement<'tcx>) {
 199         debug!("gather_statement({:?}, {:?})", loc, stmt);
 200         match stmt.kind {
 201             StatementKind::Assign(ref lval, ref rval) => {
 202                 self.create_move_path(lval);
 203                 if let RvalueInitializationState::Shallow = rval.initialization_state() {
 204                     // Box starts out uninitialized - need to create a separate
 205                     // move-path for the interior so it will be separate from
 206                     // the exterior.
 207                     self.create_move_path(&lval.clone().deref());
 208                 }
 209                 self.gather_rvalue(loc, rval);
 210             }
 211             StatementKind::StorageLive(_) |
 212             StatementKind::StorageDead(_) => {}
 213             StatementKind::SetDiscriminant{ .. } => {
 214                 span_bug!(stmt.source_info.span,
 215                           "SetDiscriminant should not exist during borrowck");
 216             }
 217             StatementKind::InlineAsm { .. } |
 218             StatementKind::EndRegion(_) |
 219             StatementKind::Validate(..) |
 220             StatementKind::Nop => {}
 221         }
 222     }
 223
 224     fn gather_rvalue(&mut self, loc: Location, rvalue: &Rvalue<'tcx>) {
 225         match *rvalue {
 226             Rvalue::Use(ref operand) |
 227             Rvalue::Repeat(ref operand, _) |
 228             Rvalue::Cast(_, ref operand, _) |
 229             Rvalue::UnaryOp(_, ref operand) => {
 230                 self.gather_operand(loc, operand)
 231             }
 232             Rvalue::BinaryOp(ref _binop, ref lhs, ref rhs) |
 233             Rvalue::CheckedBinaryOp(ref _binop, ref lhs, ref rhs) => {
 234                 self.gather_operand(loc, lhs);
 235                 self.gather_operand(loc, rhs);
 236             }
 237             Rvalue::Aggregate(ref _kind, ref operands) => {
 238                 for operand in operands {
 239                     self.gather_operand(loc, operand);
 240                 }
 241             }
 242             Rvalue::Ref(..) |
 243             Rvalue::Discriminant(..) |
 244             Rvalue::Len(..) |
 245             Rvalue::NullaryOp(NullOp::SizeOf, _) |
 246             Rvalue::NullaryOp(NullOp::Box, _) => {
 247                 // This returns an rvalue with uninitialized contents. We can't
 248                 // move out of it here because it is an rvalue - assignments always
 249                 // completely initialize their lvalue.
 250                 //
 251                 // However, this does not matter - MIR building is careful to
 252                 // only emit a shallow free for the partially-initialized
 253                 // temporary.
 254                 //
 255                 // In any case, if we want to fix this, we have to register a
 256                 // special move and change the `statement_effect` functions.
 257             }
 258         }
 259     }
 260
 261     fn gather_terminator(&mut self, loc: Location, term: &Terminator<'tcx>) {
 262         debug!("gather_terminator({:?}, {:?})", loc, term);
 263         match term.kind {
 264             TerminatorKind::Goto { target: _ } |
 265             TerminatorKind::Resume |
 266             TerminatorKind::Unreachable => { }
 267
 268             TerminatorKind::Return => {
 269                 self.gather_move(loc, &Lvalue::Local(RETURN_POINTER));
 270             }
 271
 272             TerminatorKind::Assert { .. } |
 273             TerminatorKind::SwitchInt { .. } => {
 274                 // branching terminators - these don't move anything
 275             }
 276
 277             TerminatorKind::Drop { ref location, target: _, unwind: _ } => {
 278                 self.gather_move(loc, location);
 279             }
 280             TerminatorKind::DropAndReplace { ref location, ref value, .. } => {
 281                 self.create_move_path(location);
 282                 self.gather_operand(loc, value);
 283             }
 284             TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
 285                 self.gather_operand(loc, func);
 286                 for arg in args {
 287                     self.gather_operand(loc, arg);
 288                 }
 289                 if let Some((ref destination, _bb)) = *destination {
 290                     self.create_move_path(destination);
 291                 }
 292             }
 293         }
 294     }
 295
 296     fn gather_operand(&mut self, loc: Location, operand: &Operand<'tcx>) {
 297         match *operand {
 298             Operand::Constant(..) => {} // not-a-move
 299             Operand::Consume(ref lval) => { // a move
 300                 self.gather_move(loc, lval);
 301             }
 302         }
 303     }
 304
 305     fn gather_move(&mut self, loc: Location, lval: &Lvalue<'tcx>) {
 306         debug!("gather_move({:?}, {:?})", loc, lval);
 307
 308         let lv_ty = lval.ty(self.mir, self.tcx).to_ty(self.tcx);
 309         if !lv_ty.moves_by_default(self.tcx, self.param_env, DUMMY_SP) {
 310             debug!("gather_move({:?}, {:?}) - {:?} is Copy. skipping", loc, lval, lv_ty);
 311             return
 312         }
 313
 314         let path = match self.move_path_for(lval) {
 315             Ok(path) | Err(MovePathError::UnionMove { path }) => path,
 316             Err(MovePathError::IllegalMove) => {
 317                 // Moving out of a bad path. Eventually, this should be a MIR
 318                 // borrowck error instead of a bug.
 319                 span_bug!(self.mir.span,
 320                           "Broken MIR: moving out of lvalue {:?}: {:?} at {:?}",
 321                           lval, lv_ty, loc);
 322             }
 323         };
 324         let move_out = self.data.moves.push(MoveOut { path: path, source: loc });
 325
 326         debug!("gather_move({:?}, {:?}): adding move {:?} of {:?}",
 327                loc, lval, move_out, path);
 328
 329         self.data.path_map[path].push(move_out);
 330         self.data.loc_map[loc].push(move_out);
 331     }
 332 }