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