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