compiler/rustc_mir_dataflow/src/move_paths/builder.rs

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