src/librustc_mir/dataflow/move_paths/builder.rs

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