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