compiler/rustc_mir/src/dataflow/move_paths/builder.rs

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