src/librustc_borrowck/borrowck/mir/gather_moves.rs

   1 // Copyright 2012-2016 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
  12 use rustc::ty::TyCtxt;
  13 use rustc::mir::repr::*;
  14 use rustc::util::nodemap::FnvHashMap;
  15 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  16
  17 use std::cell::{Cell};
  18 use std::collections::hash_map::Entry;
  19 use std::fmt;
  20 use std::iter;
  21 use std::ops::Index;
  22
  23 use super::abs_domain::{AbstractElem, Lift};
  24
  25 // This submodule holds some newtype'd Index wrappers that are using
  26 // NonZero to ensure that Option<Index> occupies only a single word.
  27 // They are in a submodule to impose privacy restrictions; namely, to
  28 // ensure that other code does not accidentally access `index.0`
  29 // (which is likely to yield a subtle off-by-one error).
  30 mod indexes {
  31     use core::nonzero::NonZero;
  32     use rustc_data_structures::indexed_vec::Idx;
  33
  34     macro_rules! new_index {
  35         ($Index:ident) => {
  36             #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  37             pub struct $Index(NonZero<usize>);
  38
  39             impl $Index {
  40             }
  41
  42             impl Idx for $Index {
  43                 fn new(idx: usize) -> Self {
  44                     unsafe { $Index(NonZero::new(idx + 1)) }
  45                 }
  46                 fn index(self) -> usize {
  47                     *self.0 - 1
  48                 }
  49             }
  50         }
  51     }
  52
  53     /// Index into MovePathData.move_paths
  54     new_index!(MovePathIndex);
  55
  56     /// Index into MoveData.moves.
  57     new_index!(MoveOutIndex);
  58 }
  59
  60 pub use self::indexes::MovePathIndex;
  61 pub use self::indexes::MoveOutIndex;
  62
  63 impl self::indexes::MoveOutIndex {
  64     pub fn move_path_index(&self, move_data: &MoveData) -> MovePathIndex {
  65         move_data.moves[self.index()].path
  66     }
  67 }
  68
  69 /// `MovePath` is a canonicalized representation of a path that is
  70 /// moved or assigned to.
  71 ///
  72 /// It follows a tree structure.
  73 ///
  74 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
  75 /// move *out* of the l-value `x.m`.
  76 ///
  77 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
  78 /// one of them will link to the other via the `next_sibling` field,
  79 /// and the other will have no entry in its `next_sibling` field), and
  80 /// they both have the MovePath representing `x` as their parent.
  81 #[derive(Clone)]
  82 pub struct MovePath<'tcx> {
  83     pub next_sibling: Option<MovePathIndex>,
  84     pub first_child: Option<MovePathIndex>,
  85     pub parent: Option<MovePathIndex>,
  86     pub content: MovePathContent<'tcx>,
  87 }
  88
  89 /// MovePaths usually represent a single l-value. The exceptions are
  90 /// forms that arise due to erroneous input code: static data holds
  91 /// l-values that we cannot actually move out of. Therefore we map
  92 /// statics to a special marker value (`MovePathContent::Static`)
  93 /// representing an invalid origin.
  94 #[derive(Clone, Debug)]
  95 pub enum MovePathContent<'tcx> {
  96     Lvalue(Lvalue<'tcx>),
  97     Static,
  98 }
  99
 100 /// During construction of the MovePath's, we use PreMovePath to
 101 /// represent accumulated state while we are gathering up all the
 102 /// children of each path.
 103 #[derive(Clone)]
 104 struct PreMovePath<'tcx> {
 105     pub next_sibling: Option<MovePathIndex>,
 106     pub first_child: Cell<Option<MovePathIndex>>,
 107     pub parent: Option<MovePathIndex>,
 108     pub content: MovePathContent<'tcx>,
 109 }
 110
 111 impl<'tcx> PreMovePath<'tcx> {
 112     fn into_move_path(self) -> MovePath<'tcx> {
 113         MovePath {
 114             next_sibling: self.next_sibling,
 115             parent: self.parent,
 116             content: self.content,
 117             first_child: self.first_child.get(),
 118         }
 119     }
 120 }
 121
 122 impl<'tcx> fmt::Debug for MovePath<'tcx> {
 123     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
 124         write!(w, "MovePath {{")?;
 125         if let Some(parent) = self.parent {
 126             write!(w, " parent: {:?},", parent)?;
 127         }
 128         if let Some(first_child) = self.first_child {
 129             write!(w, " first_child: {:?},", first_child)?;
 130         }
 131         if let Some(next_sibling) = self.next_sibling {
 132             write!(w, " next_sibling: {:?}", next_sibling)?;
 133         }
 134         write!(w, " content: {:?} }}", self.content)
 135     }
 136 }
 137
 138 #[derive(Debug)]
 139 pub struct MoveData<'tcx> {
 140     pub move_paths: MovePathData<'tcx>,
 141     pub moves: Vec<MoveOut>,
 142     pub loc_map: LocMap,
 143     pub path_map: PathMap,
 144     pub rev_lookup: MovePathLookup<'tcx>,
 145 }
 146
 147 #[derive(Debug)]
 148 pub struct LocMap {
 149     /// Location-indexed (BasicBlock for outer index, index within BB
 150     /// for inner index) map to list of MoveOutIndex's.
 151     ///
 152     /// Each Location `l` is mapped to the MoveOut's that are effects
 153     /// of executing the code at `l`. (There can be multiple MoveOut's
 154     /// for a given `l` because each MoveOut is associated with one
 155     /// particular path being moved.)
 156     map: Vec<Vec<Vec<MoveOutIndex>>>,
 157 }
 158
 159 impl Index<Location> for LocMap {
 160     type Output = [MoveOutIndex];
 161     fn index(&self, index: Location) -> &Self::Output {
 162         assert!(index.block.index() < self.map.len());
 163         assert!(index.index < self.map[index.block.index()].len());
 164         &self.map[index.block.index()][index.index]
 165     }
 166 }
 167
 168 #[derive(Debug)]
 169 pub struct PathMap {
 170     /// Path-indexed map to list of MoveOutIndex's.
 171     ///
 172     /// Each Path `p` is mapped to the MoveOut's that move out of `p`.
 173     map: Vec<Vec<MoveOutIndex>>,
 174 }
 175
 176 impl Index<MovePathIndex> for PathMap {
 177     type Output = [MoveOutIndex];
 178     fn index(&self, index: MovePathIndex) -> &Self::Output {
 179         &self.map[index.index()]
 180     }
 181 }
 182
 183 /// `MoveOut` represents a point in a program that moves out of some
 184 /// L-value; i.e., "creates" uninitialized memory.
 185 ///
 186 /// With respect to dataflow analysis:
 187 /// - Generated by moves and declaration of uninitialized variables.
 188 /// - Killed by assignments to the memory.
 189 #[derive(Copy, Clone)]
 190 pub struct MoveOut {
 191     /// path being moved
 192     pub path: MovePathIndex,
 193     /// location of move
 194     pub source: Location,
 195 }
 196
 197 impl fmt::Debug for MoveOut {
 198     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 199         write!(fmt, "p{}@{:?}", self.path.index(), self.source)
 200     }
 201 }
 202
 203 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 204 pub struct Location {
 205     /// block where action is located
 206     pub block: BasicBlock,
 207     /// index within above block; statement when < statments.len) or
 208     /// the terminator (when = statements.len).
 209     pub index: usize,
 210 }
 211
 212 impl fmt::Debug for Location {
 213     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 214         write!(fmt, "{:?}[{}]", self.block, self.index)
 215     }
 216 }
 217
 218 #[derive(Debug)]
 219 pub struct MovePathData<'tcx> {
 220     move_paths: Vec<MovePath<'tcx>>,
 221 }
 222
 223 impl<'tcx> MovePathData<'tcx> {
 224     pub fn len(&self) -> usize { self.move_paths.len() }
 225 }
 226
 227 impl<'tcx> Index<MovePathIndex> for MovePathData<'tcx> {
 228     type Output = MovePath<'tcx>;
 229     fn index(&self, i: MovePathIndex) -> &MovePath<'tcx> {
 230         &self.move_paths[i.index()]
 231     }
 232 }
 233
 234 struct MovePathDataBuilder<'tcx> {
 235     pre_move_paths: Vec<PreMovePath<'tcx>>,
 236     rev_lookup: MovePathLookup<'tcx>,
 237 }
 238
 239 /// Tables mapping from an l-value to its MovePathIndex.
 240 #[derive(Debug)]
 241 pub struct MovePathLookup<'tcx> {
 242     vars: IndexVec<Var, Option<MovePathIndex>>,
 243     temps: IndexVec<Temp, Option<MovePathIndex>>,
 244     args: IndexVec<Arg, Option<MovePathIndex>>,
 245
 246     /// The move path representing the return value is constructed
 247     /// lazily when we first encounter it in the input MIR.
 248     return_ptr: Option<MovePathIndex>,
 249
 250     /// A single move path (representing any static data referenced)
 251     /// is constructed lazily when we first encounter statics in the
 252     /// input MIR.
 253     statics: Option<MovePathIndex>,
 254
 255     /// projections are made from a base-lvalue and a projection
 256     /// elem. The base-lvalue will have a unique MovePathIndex; we use
 257     /// the latter as the index into the outer vector (narrowing
 258     /// subsequent search so that it is solely relative to that
 259     /// base-lvalue). For the remaining lookup, we map the projection
 260     /// elem to the associated MovePathIndex.
 261     projections: Vec<FnvHashMap<AbstractElem<'tcx>, MovePathIndex>>,
 262
 263     /// Tracks the next index to allocate during construction of the
 264     /// MovePathData. Unused after MovePathData is fully constructed.
 265     next_index: MovePathIndex,
 266 }
 267
 268 trait FillTo {
 269     type T;
 270     fn fill_to_with(&mut self, idx: usize, x: Self::T);
 271     fn fill_to(&mut self, idx: usize) where Self::T: Default {
 272         self.fill_to_with(idx, Default::default())
 273     }
 274 }
 275 impl<T:Clone> FillTo for Vec<T> {
 276     type T = T;
 277     fn fill_to_with(&mut self, idx: usize, x: T) {
 278         if idx >= self.len() {
 279             let delta = idx + 1 - self.len();
 280             assert_eq!(idx + 1, self.len() + delta);
 281             self.extend(iter::repeat(x).take(delta))
 282         }
 283         debug_assert!(idx < self.len());
 284     }
 285 }
 286
 287 #[derive(Clone, Debug)]
 288 enum LookupKind { Generate, Reuse }
 289 #[derive(Clone, Debug)]
 290 struct Lookup<T>(LookupKind, T);
 291
 292 impl Lookup<MovePathIndex> {
 293     fn index(&self) -> usize { (self.1).index() }
 294 }
 295
 296 impl<'tcx> MovePathLookup<'tcx> {
 297     fn new(mir: &Mir) -> Self {
 298         MovePathLookup {
 299             vars: IndexVec::from_elem(None, &mir.var_decls),
 300             temps: IndexVec::from_elem(None, &mir.temp_decls),
 301             args: IndexVec::from_elem(None, &mir.arg_decls),
 302             statics: None,
 303             return_ptr: None,
 304             projections: vec![],
 305             next_index: MovePathIndex::new(0),
 306         }
 307     }
 308
 309     fn next_index(next: &mut MovePathIndex) -> MovePathIndex {
 310         let i = *next;
 311         *next = MovePathIndex::new(i.index() + 1);
 312         i
 313     }
 314
 315     fn lookup_or_generate<I: Idx>(vec: &mut IndexVec<I, Option<MovePathIndex>>,
 316                                   idx: I,
 317                                   next_index: &mut MovePathIndex)
 318                                   -> Lookup<MovePathIndex> {
 319         let entry = &mut vec[idx];
 320         match *entry {
 321             None => {
 322                 let i = Self::next_index(next_index);
 323                 *entry = Some(i);
 324                 Lookup(LookupKind::Generate, i)
 325             }
 326             Some(entry_idx) => {
 327                 Lookup(LookupKind::Reuse, entry_idx)
 328             }
 329         }
 330     }
 331
 332     fn lookup_var(&mut self, var_idx: Var) -> Lookup<MovePathIndex> {
 333         Self::lookup_or_generate(&mut self.vars,
 334                                  var_idx,
 335                                  &mut self.next_index)
 336     }
 337
 338     fn lookup_temp(&mut self, temp_idx: Temp) -> Lookup<MovePathIndex> {
 339         Self::lookup_or_generate(&mut self.temps,
 340                                  temp_idx,
 341                                  &mut self.next_index)
 342     }
 343
 344     fn lookup_arg(&mut self, arg_idx: Arg) -> Lookup<MovePathIndex> {
 345         Self::lookup_or_generate(&mut self.args,
 346                                  arg_idx,
 347                                  &mut self.next_index)
 348     }
 349
 350     fn lookup_static(&mut self) -> Lookup<MovePathIndex> {
 351         match self.statics {
 352             Some(mpi) => {
 353                 Lookup(LookupKind::Reuse, mpi)
 354             }
 355             ref mut ret @ None => {
 356                 let mpi = Self::next_index(&mut self.next_index);
 357                 *ret = Some(mpi);
 358                 Lookup(LookupKind::Generate, mpi)
 359             }
 360         }
 361     }
 362
 363     fn lookup_return_pointer(&mut self) -> Lookup<MovePathIndex> {
 364         match self.return_ptr {
 365             Some(mpi) => {
 366                 Lookup(LookupKind::Reuse, mpi)
 367             }
 368             ref mut ret @ None => {
 369                 let mpi = Self::next_index(&mut self.next_index);
 370                 *ret = Some(mpi);
 371                 Lookup(LookupKind::Generate, mpi)
 372             }
 373         }
 374     }
 375
 376     fn lookup_proj(&mut self,
 377                    proj: &LvalueProjection<'tcx>,
 378                    base: MovePathIndex) -> Lookup<MovePathIndex> {
 379         let MovePathLookup { ref mut projections,
 380                              ref mut next_index, .. } = *self;
 381         projections.fill_to(base.index());
 382         match projections[base.index()].entry(proj.elem.lift()) {
 383             Entry::Occupied(ent) => {
 384                 Lookup(LookupKind::Reuse, *ent.get())
 385             }
 386             Entry::Vacant(ent) => {
 387                 let mpi = Self::next_index(next_index);
 388                 ent.insert(mpi);
 389                 Lookup(LookupKind::Generate, mpi)
 390             }
 391         }
 392     }
 393 }
 394
 395 impl<'tcx> MovePathLookup<'tcx> {
 396     // Unlike the builder `fn move_path_for` below, this lookup
 397     // alternative will *not* create a MovePath on the fly for an
 398     // unknown l-value; it will simply panic.
 399     pub fn find(&self, lval: &Lvalue<'tcx>) -> MovePathIndex {
 400         match *lval {
 401             Lvalue::Var(var) => self.vars[var].unwrap(),
 402             Lvalue::Temp(temp) => self.temps[temp].unwrap(),
 403             Lvalue::Arg(arg) => self.args[arg].unwrap(),
 404             Lvalue::Static(ref _def_id) => self.statics.unwrap(),
 405             Lvalue::ReturnPointer => self.return_ptr.unwrap(),
 406             Lvalue::Projection(ref proj) => {
 407                 let base_index = self.find(&proj.base);
 408                 self.projections[base_index.index()][&proj.elem.lift()]
 409             }
 410         }
 411     }
 412 }
 413
 414 impl<'tcx> MovePathDataBuilder<'tcx> {
 415     fn lookup(&mut self, lval: &Lvalue<'tcx>) -> Lookup<MovePathIndex> {
 416         let proj = match *lval {
 417             Lvalue::Var(var_idx) =>
 418                 return self.rev_lookup.lookup_var(var_idx),
 419             Lvalue::Temp(temp_idx) =>
 420                 return self.rev_lookup.lookup_temp(temp_idx),
 421             Lvalue::Arg(arg_idx) =>
 422                 return self.rev_lookup.lookup_arg(arg_idx),
 423             Lvalue::Static(_def_id) =>
 424                 return self.rev_lookup.lookup_static(),
 425             Lvalue::ReturnPointer =>
 426                 return self.rev_lookup.lookup_return_pointer(),
 427             Lvalue::Projection(ref proj) => {
 428                 proj
 429             }
 430         };
 431
 432         let base_index = self.move_path_for(&proj.base);
 433         self.rev_lookup.lookup_proj(proj, base_index)
 434     }
 435
 436     fn create_move_path(&mut self, lval: &Lvalue<'tcx>) {
 437         // Create MovePath for `lval`, discarding returned index.
 438         self.move_path_for(lval);
 439     }
 440
 441     fn move_path_for(&mut self, lval: &Lvalue<'tcx>) -> MovePathIndex {
 442         debug!("move_path_for({:?})", lval);
 443
 444         let lookup: Lookup<MovePathIndex> = self.lookup(lval);
 445
 446         // `lookup` is either the previously assigned index or a
 447         // newly-allocated one.
 448         debug_assert!(lookup.index() <= self.pre_move_paths.len());
 449
 450         if let Lookup(LookupKind::Generate, mpi) = lookup {
 451             let parent;
 452             let sibling;
 453             // tracks whether content is Some non-static; statics map to None.
 454             let content: Option<&Lvalue<'tcx>>;
 455
 456             match *lval {
 457                 Lvalue::Static(_) => {
 458                     content = None;
 459                     sibling = None;
 460                     parent = None;
 461                 }
 462
 463                 Lvalue::Var(_) | Lvalue::Temp(_) | Lvalue::Arg(_) |
 464                 Lvalue::ReturnPointer => {
 465                     content = Some(lval);
 466                     sibling = None;
 467                     parent = None;
 468                 }
 469                 Lvalue::Projection(ref proj) => {
 470                     content = Some(lval);
 471
 472                     // Here, install new MovePath as new first_child.
 473
 474                     // Note: `parent` previously allocated (Projection
 475                     // case of match above established this).
 476                     let idx = self.move_path_for(&proj.base);
 477                     parent = Some(idx);
 478
 479                     let parent_move_path = &mut self.pre_move_paths[idx.index()];
 480
 481                     // At last: Swap in the new first_child.
 482                     sibling = parent_move_path.first_child.get();
 483                     parent_move_path.first_child.set(Some(mpi));
 484                 }
 485             };
 486
 487             let content = match content {
 488                 Some(lval) => MovePathContent::Lvalue(lval.clone()),
 489                 None => MovePathContent::Static,
 490             };
 491
 492             let move_path = PreMovePath {
 493                 next_sibling: sibling,
 494                 parent: parent,
 495                 content: content,
 496                 first_child: Cell::new(None),
 497             };
 498
 499             self.pre_move_paths.push(move_path);
 500         }
 501
 502         return lookup.1;
 503     }
 504 }
 505
 506 impl<'a, 'tcx> MoveData<'tcx> {
 507     pub fn gather_moves(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
 508         gather_moves(mir, tcx)
 509     }
 510 }
 511
 512 #[derive(Debug)]
 513 enum StmtKind {
 514     Use, Repeat, Cast, BinaryOp, UnaryOp, Box,
 515     Aggregate, Drop, CallFn, CallArg, Return, If,
 516 }
 517
 518 fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveData<'tcx> {
 519     use self::StmtKind as SK;
 520
 521     let bb_count = mir.basic_blocks().len();
 522     let mut moves = vec![];
 523     let mut loc_map: Vec<_> = iter::repeat(Vec::new()).take(bb_count).collect();
 524     let mut path_map = Vec::new();
 525
 526     // this is mutable only because we will move it to and fro' the
 527     // BlockContexts constructed on each iteration. (Moving is more
 528     // straight-forward than mutable borrows in this instance.)
 529     let mut builder = MovePathDataBuilder {
 530         pre_move_paths: Vec::new(),
 531         rev_lookup: MovePathLookup::new(mir),
 532     };
 533
 534     // Before we analyze the program text, we create the MovePath's
 535     // for all of the vars, args, and temps. (This enforces a basic
 536     // property that even if the MIR body doesn't contain any
 537     // references to a var/arg/temp, it will still be a valid
 538     // operation to lookup the MovePath associated with it.)
 539     assert!(mir.var_decls.len() <= ::std::u32::MAX as usize);
 540     assert!(mir.arg_decls.len() <= ::std::u32::MAX as usize);
 541     assert!(mir.temp_decls.len() <= ::std::u32::MAX as usize);
 542     for var in mir.var_decls.indices() {
 543         let path_idx = builder.move_path_for(&Lvalue::Var(var));
 544         path_map.fill_to(path_idx.index());
 545     }
 546     for arg in mir.arg_decls.indices() {
 547         let path_idx = builder.move_path_for(&Lvalue::Arg(arg));
 548         path_map.fill_to(path_idx.index());
 549     }
 550     for temp in mir.temp_decls.indices() {
 551         let path_idx = builder.move_path_for(&Lvalue::Temp(temp));
 552         path_map.fill_to(path_idx.index());
 553     }
 554
 555     for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
 556         let loc_map_bb = &mut loc_map[bb.index()];
 557
 558         debug_assert!(loc_map_bb.len() == 0);
 559         let len = bb_data.statements.len();
 560         loc_map_bb.fill_to(len);
 561         debug_assert!(loc_map_bb.len() == len + 1);
 562
 563         let mut bb_ctxt = BlockContext {
 564             _tcx: tcx,
 565             moves: &mut moves,
 566             builder: builder,
 567             path_map: &mut path_map,
 568             loc_map_bb: loc_map_bb,
 569         };
 570
 571         for (i, stmt) in bb_data.statements.iter().enumerate() {
 572             let source = Location { block: bb, index: i };
 573             match stmt.kind {
 574                 StatementKind::Assign(ref lval, ref rval) => {
 575                     bb_ctxt.builder.create_move_path(lval);
 576
 577                     // Ensure that the path_map contains entries even
 578                     // if the lvalue is assigned and never read.
 579                     let assigned_path = bb_ctxt.builder.move_path_for(lval);
 580                     bb_ctxt.path_map.fill_to(assigned_path.index());
 581
 582                     match *rval {
 583                         Rvalue::Use(ref operand) => {
 584                             bb_ctxt.on_operand(SK::Use, operand, source)
 585                         }
 586                         Rvalue::Repeat(ref operand, ref _const) =>
 587                             bb_ctxt.on_operand(SK::Repeat, operand, source),
 588                         Rvalue::Cast(ref _kind, ref operand, ref _ty) =>
 589                             bb_ctxt.on_operand(SK::Cast, operand, source),
 590                         Rvalue::BinaryOp(ref _binop, ref operand1, ref operand2) |
 591                         Rvalue::CheckedBinaryOp(ref _binop, ref operand1, ref operand2) => {
 592                             bb_ctxt.on_operand(SK::BinaryOp, operand1, source);
 593                             bb_ctxt.on_operand(SK::BinaryOp, operand2, source);
 594                         }
 595                         Rvalue::UnaryOp(ref _unop, ref operand) => {
 596                             bb_ctxt.on_operand(SK::UnaryOp, operand, source);
 597                         }
 598                         Rvalue::Box(ref _ty) => {
 599                             // this is creating uninitialized
 600                             // memory that needs to be initialized.
 601                             let deref_lval = Lvalue::Projection(Box::new(Projection {
 602                                 base: lval.clone(),
 603                                 elem: ProjectionElem::Deref,
 604                             }));
 605                             bb_ctxt.on_move_out_lval(SK::Box, &deref_lval, source);
 606                         }
 607                         Rvalue::Aggregate(ref _kind, ref operands) => {
 608                             for operand in operands {
 609                                 bb_ctxt.on_operand(SK::Aggregate, operand, source);
 610                             }
 611                         }
 612                         Rvalue::Ref(..) |
 613                         Rvalue::Len(..) |
 614                         Rvalue::InlineAsm { .. } => {}
 615                     }
 616                 }
 617                 StatementKind::StorageLive(_) |
 618                 StatementKind::StorageDead(_) => {}
 619                 StatementKind::SetDiscriminant{ .. } => {
 620                     span_bug!(stmt.source_info.span,
 621                               "SetDiscriminant should not exist during borrowck");
 622                 }
 623             }
 624         }
 625
 626         debug!("gather_moves({:?})", bb_data.terminator());
 627         match bb_data.terminator().kind {
 628             TerminatorKind::Goto { target: _ } |
 629             TerminatorKind::Resume |
 630             TerminatorKind::Unreachable => { }
 631
 632             TerminatorKind::Return => {
 633                 let source = Location { block: bb,
 634                                         index: bb_data.statements.len() };
 635                 debug!("gather_moves Return on_move_out_lval return {:?}", source);
 636                 bb_ctxt.on_move_out_lval(SK::Return, &Lvalue::ReturnPointer, source);
 637             }
 638
 639             TerminatorKind::If { ref cond, targets: _ } => {
 640                 let source = Location { block: bb,
 641                                         index: bb_data.statements.len() };
 642                 bb_ctxt.on_operand(SK::If, cond, source);
 643             }
 644
 645             TerminatorKind::Assert {
 646                 ref cond, expected: _,
 647                 ref msg, target: _, cleanup: _
 648             } => {
 649                 // The `cond` is always of (copyable) type `bool`,
 650                 // so there will never be anything to move.
 651                 let _ = cond;
 652                 match *msg {
 653                     AssertMessage:: BoundsCheck { ref len, ref index } => {
 654                         // Same for the usize length and index in bounds-checking.
 655                         let _ = (len, index);
 656                     }
 657                     AssertMessage::Math(_) => {}
 658                 }
 659             }
 660
 661             TerminatorKind::SwitchInt { switch_ty: _, values: _, targets: _, ref discr } |
 662             TerminatorKind::Switch { adt_def: _, targets: _, ref discr } => {
 663                 // The `discr` is not consumed; that is instead
 664                 // encoded on specific match arms (and for
 665                 // SwitchInt`, it is always a copyable integer
 666                 // type anyway).
 667                 let _ = discr;
 668             }
 669
 670             TerminatorKind::Drop { ref location, target: _, unwind: _ } => {
 671                 let source = Location { block: bb,
 672                                         index: bb_data.statements.len() };
 673                 bb_ctxt.on_move_out_lval(SK::Drop, location, source);
 674             }
 675             TerminatorKind::DropAndReplace { ref location, ref value, .. } => {
 676                 let assigned_path = bb_ctxt.builder.move_path_for(location);
 677                 bb_ctxt.path_map.fill_to(assigned_path.index());
 678
 679                 let source = Location { block: bb,
 680                                         index: bb_data.statements.len() };
 681                 bb_ctxt.on_operand(SK::Use, value, source);
 682             }
 683             TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
 684                 let source = Location { block: bb,
 685                                         index: bb_data.statements.len() };
 686                 bb_ctxt.on_operand(SK::CallFn, func, source);
 687                 for arg in args {
 688                     debug!("gather_moves Call on_operand {:?} {:?}", arg, source);
 689                     bb_ctxt.on_operand(SK::CallArg, arg, source);
 690                 }
 691                 if let Some((ref destination, _bb)) = *destination {
 692                     debug!("gather_moves Call create_move_path {:?} {:?}", destination, source);
 693
 694                     // Ensure that the path_map contains entries even
 695                     // if the lvalue is assigned and never read.
 696                     let assigned_path = bb_ctxt.builder.move_path_for(destination);
 697                     bb_ctxt.path_map.fill_to(assigned_path.index());
 698
 699                     bb_ctxt.builder.create_move_path(destination);
 700                 }
 701             }
 702         }
 703
 704         builder = bb_ctxt.builder;
 705     }
 706
 707     // At this point, we may have created some MovePaths that do not
 708     // have corresponding entries in the path map.
 709     //
 710     // (For example, creating the path `a.b.c` may, as a side-effect,
 711     // create a path for the parent path `a.b`.)
 712     //
 713     // All such paths were not referenced ...
 714     //
 715     // well you know, lets actually try just asserting that the path map *is* complete.
 716     assert_eq!(path_map.len(), builder.pre_move_paths.len());
 717
 718     let pre_move_paths = builder.pre_move_paths;
 719     let move_paths: Vec<_> = pre_move_paths.into_iter()
 720         .map(|p| p.into_move_path())
 721         .collect();
 722
 723     debug!("{}", {
 724         let mut seen: Vec<_> = move_paths.iter().map(|_| false).collect();
 725         for (j, &MoveOut { ref path, ref source }) in moves.iter().enumerate() {
 726             debug!("MovePathData moves[{}]: MoveOut {{ path: {:?} = {:?}, source: {:?} }}",
 727                    j, path, move_paths[path.index()], source);
 728             seen[path.index()] = true;
 729         }
 730         for (j, path) in move_paths.iter().enumerate() {
 731             if !seen[j] {
 732                 debug!("MovePathData move_paths[{}]: {:?}", j, path);
 733             }
 734         }
 735         "done dumping MovePathData"
 736     });
 737
 738     MoveData {
 739         move_paths: MovePathData { move_paths: move_paths, },
 740         moves: moves,
 741         loc_map: LocMap { map: loc_map },
 742         path_map: PathMap { map: path_map },
 743         rev_lookup: builder.rev_lookup,
 744     }
 745 }
 746
 747 struct BlockContext<'b, 'tcx: 'b> {
 748     _tcx: TyCtxt<'b, 'tcx, 'tcx>,
 749     moves: &'b mut Vec<MoveOut>,
 750     builder: MovePathDataBuilder<'tcx>,
 751     path_map: &'b mut Vec<Vec<MoveOutIndex>>,
 752     loc_map_bb: &'b mut Vec<Vec<MoveOutIndex>>,
 753 }
 754
 755 impl<'b, 'tcx: 'b> BlockContext<'b, 'tcx> {
 756     fn on_move_out_lval(&mut self,
 757                         stmt_kind: StmtKind,
 758                         lval: &Lvalue<'tcx>,
 759                         source: Location) {
 760         let i = source.index;
 761         let index = MoveOutIndex::new(self.moves.len());
 762
 763         let path = self.builder.move_path_for(lval);
 764         self.moves.push(MoveOut { path: path, source: source.clone() });
 765         self.path_map.fill_to(path.index());
 766
 767         debug!("ctxt: {:?} add consume of lval: {:?} \
 768                 at index: {:?} \
 769                 to path_map for path: {:?} and \
 770                 to loc_map for loc: {:?}",
 771                stmt_kind, lval, index, path, source);
 772
 773         debug_assert!(path.index() < self.path_map.len());
 774         // this is actually a questionable assert; at the very
 775         // least, incorrect input code can probably cause it to
 776         // fire.
 777         assert!(self.path_map[path.index()].iter().find(|idx| **idx == index).is_none());
 778         self.path_map[path.index()].push(index);
 779
 780         debug_assert!(i < self.loc_map_bb.len());
 781         debug_assert!(self.loc_map_bb[i].iter().find(|idx| **idx == index).is_none());
 782         self.loc_map_bb[i].push(index);
 783     }
 784
 785     fn on_operand(&mut self, stmt_kind: StmtKind, operand: &Operand<'tcx>, source: Location) {
 786         match *operand {
 787             Operand::Constant(..) => {} // not-a-move
 788             Operand::Consume(ref lval) => { // a move
 789                 self.on_move_out_lval(stmt_kind, lval, source);
 790             }
 791         }
 792     }
 793 }