src/librustc_mir/dataflow/move_paths/builder.rs

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