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