src/librustc_mir/dataflow/move_paths/builder.rs

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