src/librustc/middle/borrowck/move_data.rs

   1 // Copyright 2012-2014 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 //! Data structures used for tracking moves. Please see the extensive
  12 //! comments in the section "Moves and initialization" in `doc.rs`.
  13
  14 pub use self::MoveKind::*;
  15
  16 use std::cell::RefCell;
  17 use std::rc::Rc;
  18 use std::uint;
  19 use middle::borrowck::*;
  20 use middle::borrowck::LoanPathKind::{LpVar, LpUpvar, LpDowncast, LpExtend};
  21 use middle::borrowck::LoanPathElem::{LpInterior};
  22 use middle::cfg;
  23 use middle::dataflow::DataFlowContext;
  24 use middle::dataflow::BitwiseOperator;
  25 use middle::dataflow::DataFlowOperator;
  26 use middle::expr_use_visitor as euv;
  27 use middle::mem_categorization as mc;
  28 use middle::ty;
  29 use syntax::ast;
  30 use syntax::ast_util;
  31 use syntax::codemap::Span;
  32 use util::nodemap::{FnvHashMap, NodeSet};
  33 use util::ppaux::Repr;
  34
  35 #[path="fragments.rs"]
  36 pub mod fragments;
  37
  38 pub struct MoveData<'tcx> {
  39     /// Move paths. See section "Move paths" in `doc.rs`.
  40     pub paths: RefCell<Vec<MovePath<'tcx>>>,
  41
  42     /// Cache of loan path to move path index, for easy lookup.
  43     pub path_map: RefCell<FnvHashMap<Rc<LoanPath<'tcx>>, MovePathIndex>>,
  44
  45     /// Each move or uninitialized variable gets an entry here.
  46     pub moves: RefCell<Vec<Move>>,
  47
  48     /// Assignments to a variable, like `x = foo`. These are assigned
  49     /// bits for dataflow, since we must track them to ensure that
  50     /// immutable variables are assigned at most once along each path.
  51     pub var_assignments: RefCell<Vec<Assignment>>,
  52
  53     /// Assignments to a path, like `x.f = foo`. These are not
  54     /// assigned dataflow bits, but we track them because they still
  55     /// kill move bits.
  56     pub path_assignments: RefCell<Vec<Assignment>>,
  57
  58     /// Enum variant matched within a pattern on some match arm, like
  59     /// `SomeStruct{ f: Variant1(x, y) } => ...`
  60     pub variant_matches: RefCell<Vec<VariantMatch>>,
  61
  62     /// Assignments to a variable or path, like `x = foo`, but not `x += foo`.
  63     pub assignee_ids: RefCell<NodeSet>,
  64
  65     /// Path-fragments from moves in to or out of parts of structured data.
  66     pub fragments: RefCell<fragments::FragmentSets>,
  67 }
  68
  69 pub struct FlowedMoveData<'a, 'tcx: 'a> {
  70     pub move_data: MoveData<'tcx>,
  71
  72     pub dfcx_moves: MoveDataFlow<'a, 'tcx>,
  73
  74     // We could (and maybe should, for efficiency) combine both move
  75     // and assign data flow into one, but this way it's easier to
  76     // distinguish the bits that correspond to moves and assignments.
  77     pub dfcx_assign: AssignDataFlow<'a, 'tcx>
  78 }
  79
  80 /// Index into `MoveData.paths`, used like a pointer
  81 #[deriving(PartialEq, Eq, PartialOrd, Ord, Show)]
  82 pub struct MovePathIndex(uint);
  83
  84 impl MovePathIndex {
  85     fn get(&self) -> uint {
  86         let MovePathIndex(v) = *self; v
  87     }
  88 }
  89
  90 impl Clone for MovePathIndex {
  91     fn clone(&self) -> MovePathIndex {
  92         MovePathIndex(self.get())
  93     }
  94 }
  95
  96 #[allow(non_upper_case_globals)]
  97 static InvalidMovePathIndex: MovePathIndex =
  98     MovePathIndex(uint::MAX);
  99
 100 /// Index into `MoveData.moves`, used like a pointer
 101 #[deriving(PartialEq)]
 102 pub struct MoveIndex(uint);
 103
 104 impl MoveIndex {
 105     fn get(&self) -> uint {
 106         let MoveIndex(v) = *self; v
 107     }
 108 }
 109
 110 #[allow(non_upper_case_globals)]
 111 static InvalidMoveIndex: MoveIndex =
 112     MoveIndex(uint::MAX);
 113
 114 pub struct MovePath<'tcx> {
 115     /// Loan path corresponding to this move path
 116     pub loan_path: Rc<LoanPath<'tcx>>,
 117
 118     /// Parent pointer, `InvalidMovePathIndex` if root
 119     pub parent: MovePathIndex,
 120
 121     /// Head of linked list of moves to this path,
 122     /// `InvalidMoveIndex` if not moved
 123     pub first_move: MoveIndex,
 124
 125     /// First node in linked list of children, `InvalidMovePathIndex` if leaf
 126     pub first_child: MovePathIndex,
 127
 128     /// Next node in linked list of parent's children (siblings),
 129     /// `InvalidMovePathIndex` if none.
 130     pub next_sibling: MovePathIndex,
 131 }
 132
 133 #[deriving(PartialEq, Show)]
 134 pub enum MoveKind {
 135     Declared,   // When declared, variables start out "moved".
 136     MoveExpr,   // Expression or binding that moves a variable
 137     MovePat,    // By-move binding
 138     Captured    // Closure creation that moves a value
 139 }
 140
 141 pub struct Move {
 142     /// Path being moved.
 143     pub path: MovePathIndex,
 144
 145     /// id of node that is doing the move.
 146     pub id: ast::NodeId,
 147
 148     /// Kind of move, for error messages.
 149     pub kind: MoveKind,
 150
 151     /// Next node in linked list of moves from `path`, or `InvalidMoveIndex`
 152     pub next_move: MoveIndex
 153 }
 154
 155 pub struct Assignment {
 156     /// Path being assigned.
 157     pub path: MovePathIndex,
 158
 159     /// id where assignment occurs
 160     pub id: ast::NodeId,
 161
 162     /// span of node where assignment occurs
 163     pub span: Span,
 164 }
 165
 166 pub struct VariantMatch {
 167     /// downcast to the variant.
 168     pub path: MovePathIndex,
 169
 170     /// path being downcast to the variant.
 171     pub base_path: MovePathIndex,
 172
 173     /// id where variant's pattern occurs
 174     pub id: ast::NodeId,
 175
 176     /// says if variant established by move (and why), by copy, or by borrow.
 177     pub mode: euv::MatchMode
 178 }
 179
 180 #[deriving(Clone)]
 181 pub struct MoveDataFlowOperator;
 182
 183 pub type MoveDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, MoveDataFlowOperator>;
 184
 185 #[deriving(Clone)]
 186 pub struct AssignDataFlowOperator;
 187
 188 pub type AssignDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, AssignDataFlowOperator>;
 189
 190 fn loan_path_is_precise(loan_path: &LoanPath) -> bool {
 191     match loan_path.kind {
 192         LpVar(_) | LpUpvar(_) => {
 193             true
 194         }
 195         LpExtend(_, _, LpInterior(mc::InteriorElement(_))) => {
 196             // Paths involving element accesses do not refer to a unique
 197             // location, as there is no accurate tracking of the indices.
 198             false
 199         }
 200         LpDowncast(ref lp_base, _) |
 201         LpExtend(ref lp_base, _, _) => {
 202             loan_path_is_precise(&**lp_base)
 203         }
 204     }
 205 }
 206
 207 impl Move {
 208     pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
 209         format!("Move{} path: {}, id: {}, kind: {} {}",
 210                 "{",
 211                 move_data.path_loan_path(self.path).repr(tcx),
 212                 self.id,
 213                 self.kind,
 214                 "}")
 215     }
 216 }
 217
 218 impl Assignment {
 219     pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
 220         format!("Assignment{} path: {}, id: {} {}",
 221                 "{",
 222                 move_data.path_loan_path(self.path).repr(tcx),
 223                 self.id,
 224                 "}")
 225     }
 226 }
 227
 228 impl VariantMatch {
 229     pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
 230         format!("VariantMatch{} path: {}, id: {} {}",
 231                 "{",
 232                 move_data.path_loan_path(self.path).repr(tcx),
 233                 self.id,
 234                 "}")
 235     }
 236 }
 237
 238 impl<'tcx> MoveData<'tcx> {
 239     pub fn new() -> MoveData<'tcx> {
 240         MoveData {
 241             paths: RefCell::new(Vec::new()),
 242             path_map: RefCell::new(FnvHashMap::new()),
 243             moves: RefCell::new(Vec::new()),
 244             path_assignments: RefCell::new(Vec::new()),
 245             var_assignments: RefCell::new(Vec::new()),
 246             variant_matches: RefCell::new(Vec::new()),
 247             assignee_ids: RefCell::new(NodeSet::new()),
 248             fragments: RefCell::new(fragments::FragmentSets::new()),
 249         }
 250     }
 251
 252     pub fn path_loan_path(&self, index: MovePathIndex) -> Rc<LoanPath<'tcx>> {
 253         (*self.paths.borrow())[index.get()].loan_path.clone()
 254     }
 255
 256     fn path_parent(&self, index: MovePathIndex) -> MovePathIndex {
 257         (*self.paths.borrow())[index.get()].parent
 258     }
 259
 260     fn path_first_move(&self, index: MovePathIndex) -> MoveIndex {
 261         (*self.paths.borrow())[index.get()].first_move
 262     }
 263
 264     /// Returns the index of first child, or `InvalidMovePathIndex` if
 265     /// `index` is leaf.
 266     fn path_first_child(&self, index: MovePathIndex) -> MovePathIndex {
 267         (*self.paths.borrow())[index.get()].first_child
 268     }
 269
 270     fn path_next_sibling(&self, index: MovePathIndex) -> MovePathIndex {
 271         (*self.paths.borrow())[index.get()].next_sibling
 272     }
 273
 274     fn set_path_first_move(&self,
 275                            index: MovePathIndex,
 276                            first_move: MoveIndex) {
 277         (*self.paths.borrow_mut())[index.get()].first_move = first_move
 278     }
 279
 280     fn set_path_first_child(&self,
 281                             index: MovePathIndex,
 282                             first_child: MovePathIndex) {
 283         (*self.paths.borrow_mut())[index.get()].first_child = first_child
 284     }
 285
 286     fn move_next_move(&self, index: MoveIndex) -> MoveIndex {
 287         //! Type safe indexing operator
 288         (*self.moves.borrow())[index.get()].next_move
 289     }
 290
 291     fn is_var_path(&self, index: MovePathIndex) -> bool {
 292         //! True if `index` refers to a variable
 293         self.path_parent(index) == InvalidMovePathIndex
 294     }
 295
 296     /// Returns the existing move path index for `lp`, if any, and otherwise adds a new index for
 297     /// `lp` and any of its base paths that do not yet have an index.
 298     pub fn move_path(&self,
 299                      tcx: &ty::ctxt<'tcx>,
 300                      lp: Rc<LoanPath<'tcx>>) -> MovePathIndex {
 301         match self.path_map.borrow().get(&lp) {
 302             Some(&index) => {
 303                 return index;
 304             }
 305             None => {}
 306         }
 307
 308         let index = match lp.kind {
 309             LpVar(..) | LpUpvar(..) => {
 310                 let index = MovePathIndex(self.paths.borrow().len());
 311
 312                 self.paths.borrow_mut().push(MovePath {
 313                     loan_path: lp.clone(),
 314                     parent: InvalidMovePathIndex,
 315                     first_move: InvalidMoveIndex,
 316                     first_child: InvalidMovePathIndex,
 317                     next_sibling: InvalidMovePathIndex,
 318                 });
 319
 320                 index
 321             }
 322
 323             LpDowncast(ref base, _) |
 324             LpExtend(ref base, _, _) => {
 325                 let parent_index = self.move_path(tcx, base.clone());
 326
 327                 let index = MovePathIndex(self.paths.borrow().len());
 328
 329                 let next_sibling = self.path_first_child(parent_index);
 330                 self.set_path_first_child(parent_index, index);
 331
 332                 self.paths.borrow_mut().push(MovePath {
 333                     loan_path: lp.clone(),
 334                     parent: parent_index,
 335                     first_move: InvalidMoveIndex,
 336                     first_child: InvalidMovePathIndex,
 337                     next_sibling: next_sibling,
 338                 });
 339
 340                 index
 341             }
 342         };
 343
 344         debug!("move_path(lp={}, index={})",
 345                lp.repr(tcx),
 346                index);
 347
 348         assert_eq!(index.get(), self.paths.borrow().len() - 1);
 349         self.path_map.borrow_mut().insert(lp, index);
 350         return index;
 351     }
 352
 353     fn existing_move_path(&self, lp: &Rc<LoanPath<'tcx>>)
 354                           -> Option<MovePathIndex> {
 355         self.path_map.borrow().get(lp).cloned()
 356     }
 357
 358     fn existing_base_paths(&self, lp: &Rc<LoanPath<'tcx>>)
 359                            -> Vec<MovePathIndex> {
 360         let mut result = vec!();
 361         self.add_existing_base_paths(lp, &mut result);
 362         result
 363     }
 364
 365     /// Adds any existing move path indices for `lp` and any base paths of `lp` to `result`, but
 366     /// does not add new move paths
 367     fn add_existing_base_paths(&self, lp: &Rc<LoanPath<'tcx>>,
 368                                result: &mut Vec<MovePathIndex>) {
 369         match self.path_map.borrow().get(lp).cloned() {
 370             Some(index) => {
 371                 self.each_base_path(index, |p| {
 372                     result.push(p);
 373                     true
 374                 });
 375             }
 376             None => {
 377                 match lp.kind {
 378                     LpVar(..) | LpUpvar(..) => { }
 379                     LpDowncast(ref b, _) |
 380                     LpExtend(ref b, _, _) => {
 381                         self.add_existing_base_paths(b, result);
 382                     }
 383                 }
 384             }
 385         }
 386
 387     }
 388
 389     /// Adds a new move entry for a move of `lp` that occurs at location `id` with kind `kind`.
 390     pub fn add_move(&self,
 391                     tcx: &ty::ctxt<'tcx>,
 392                     lp: Rc<LoanPath<'tcx>>,
 393                     id: ast::NodeId,
 394                     kind: MoveKind) {
 395         debug!("add_move(lp={}, id={}, kind={})",
 396                lp.repr(tcx),
 397                id,
 398                kind);
 399
 400         let path_index = self.move_path(tcx, lp.clone());
 401         let move_index = MoveIndex(self.moves.borrow().len());
 402
 403         self.fragments.borrow_mut().add_move(path_index);
 404
 405         let next_move = self.path_first_move(path_index);
 406         self.set_path_first_move(path_index, move_index);
 407
 408         self.moves.borrow_mut().push(Move {
 409             path: path_index,
 410             id: id,
 411             kind: kind,
 412             next_move: next_move
 413         });
 414     }
 415
 416     /// Adds a new record for an assignment to `lp` that occurs at location `id` with the given
 417     /// `span`.
 418     pub fn add_assignment(&self,
 419                           tcx: &ty::ctxt<'tcx>,
 420                           lp: Rc<LoanPath<'tcx>>,
 421                           assign_id: ast::NodeId,
 422                           span: Span,
 423                           assignee_id: ast::NodeId,
 424                           mode: euv::MutateMode) {
 425         debug!("add_assignment(lp={}, assign_id={}, assignee_id={}",
 426                lp.repr(tcx), assign_id, assignee_id);
 427
 428         let path_index = self.move_path(tcx, lp.clone());
 429
 430         self.fragments.borrow_mut().add_assignment(path_index);
 431
 432         match mode {
 433             euv::Init | euv::JustWrite => {
 434                 self.assignee_ids.borrow_mut().insert(assignee_id);
 435             }
 436             euv::WriteAndRead => { }
 437         }
 438
 439         let assignment = Assignment {
 440             path: path_index,
 441             id: assign_id,
 442             span: span,
 443         };
 444
 445         if self.is_var_path(path_index) {
 446             debug!("add_assignment[var](lp={}, assignment={}, path_index={})",
 447                    lp.repr(tcx), self.var_assignments.borrow().len(), path_index);
 448
 449             self.var_assignments.borrow_mut().push(assignment);
 450         } else {
 451             debug!("add_assignment[path](lp={}, path_index={})",
 452                    lp.repr(tcx), path_index);
 453
 454             self.path_assignments.borrow_mut().push(assignment);
 455         }
 456     }
 457
 458     /// Adds a new record for a match of `base_lp`, downcast to
 459     /// variant `lp`, that occurs at location `pattern_id`.  (One
 460     /// should be able to recover the span info from the
 461     /// `pattern_id` and the ast_map, I think.)
 462     pub fn add_variant_match(&self,
 463                              tcx: &ty::ctxt<'tcx>,
 464                              lp: Rc<LoanPath<'tcx>>,
 465                              pattern_id: ast::NodeId,
 466                              base_lp: Rc<LoanPath<'tcx>>,
 467                              mode: euv::MatchMode) {
 468         debug!("add_variant_match(lp={}, pattern_id={})",
 469                lp.repr(tcx), pattern_id);
 470
 471         let path_index = self.move_path(tcx, lp.clone());
 472         let base_path_index = self.move_path(tcx, base_lp.clone());
 473
 474         self.fragments.borrow_mut().add_assignment(path_index);
 475
 476         let variant_match = VariantMatch {
 477             path: path_index,
 478             base_path: base_path_index,
 479             id: pattern_id,
 480             mode: mode,
 481         };
 482
 483         self.variant_matches.borrow_mut().push(variant_match);
 484     }
 485
 486     fn fixup_fragment_sets(&self, tcx: &ty::ctxt<'tcx>) {
 487         fragments::fixup_fragment_sets(self, tcx)
 488     }
 489
 490     /// Adds the gen/kills for the various moves and
 491     /// assignments into the provided data flow contexts.
 492     /// Moves are generated by moves and killed by assignments and
 493     /// scoping. Assignments are generated by assignment to variables and
 494     /// killed by scoping. See `doc.rs` for more details.
 495     fn add_gen_kills(&self,
 496                      tcx: &ty::ctxt<'tcx>,
 497                      dfcx_moves: &mut MoveDataFlow,
 498                      dfcx_assign: &mut AssignDataFlow) {
 499         for (i, the_move) in self.moves.borrow().iter().enumerate() {
 500             dfcx_moves.add_gen(the_move.id, i);
 501         }
 502
 503         for (i, assignment) in self.var_assignments.borrow().iter().enumerate() {
 504             dfcx_assign.add_gen(assignment.id, i);
 505             self.kill_moves(assignment.path, assignment.id, dfcx_moves);
 506         }
 507
 508         for assignment in self.path_assignments.borrow().iter() {
 509             self.kill_moves(assignment.path, assignment.id, dfcx_moves);
 510         }
 511
 512         // Kill all moves related to a variable `x` when
 513         // it goes out of scope:
 514         for path in self.paths.borrow().iter() {
 515             match path.loan_path.kind {
 516                 LpVar(..) | LpUpvar(..) | LpDowncast(..) => {
 517                     let kill_scope = path.loan_path.kill_scope(tcx);
 518                     let path = self.path_map.borrow()[path.loan_path];
 519                     self.kill_moves(path, kill_scope.node_id(), dfcx_moves);
 520                 }
 521                 LpExtend(..) => {}
 522             }
 523         }
 524
 525         // Kill all assignments when the variable goes out of scope:
 526         for (assignment_index, assignment) in
 527                 self.var_assignments.borrow().iter().enumerate() {
 528             let lp = self.path_loan_path(assignment.path);
 529             match lp.kind {
 530                 LpVar(..) | LpUpvar(..) | LpDowncast(..) => {
 531                     let kill_scope = lp.kill_scope(tcx);
 532                     dfcx_assign.add_kill(kill_scope.node_id(), assignment_index);
 533                 }
 534                 LpExtend(..) => {
 535                     tcx.sess.bug("var assignment for non var path");
 536                 }
 537             }
 538         }
 539     }
 540
 541     fn each_base_path(&self, index: MovePathIndex, f: |MovePathIndex| -> bool)
 542                       -> bool {
 543         let mut p = index;
 544         while p != InvalidMovePathIndex {
 545             if !f(p) {
 546                 return false;
 547             }
 548             p = self.path_parent(p);
 549         }
 550         return true;
 551     }
 552
 553     fn each_extending_path(&self,
 554                            index: MovePathIndex,
 555                            f: |MovePathIndex| -> bool)
 556                            -> bool {
 557         if !f(index) {
 558             return false;
 559         }
 560
 561         let mut p = self.path_first_child(index);
 562         while p != InvalidMovePathIndex {
 563             if !self.each_extending_path(p, |x| f(x)) {
 564                 return false;
 565             }
 566             p = self.path_next_sibling(p);
 567         }
 568
 569         return true;
 570     }
 571
 572     fn each_applicable_move(&self,
 573                             index0: MovePathIndex,
 574                             f: |MoveIndex| -> bool)
 575                             -> bool {
 576         let mut ret = true;
 577         self.each_extending_path(index0, |index| {
 578             let mut p = self.path_first_move(index);
 579             while p != InvalidMoveIndex {
 580                 if !f(p) {
 581                     ret = false;
 582                     break;
 583                 }
 584                 p = self.move_next_move(p);
 585             }
 586             ret
 587         });
 588         ret
 589     }
 590
 591     fn kill_moves(&self,
 592                   path: MovePathIndex,
 593                   kill_id: ast::NodeId,
 594                   dfcx_moves: &mut MoveDataFlow) {
 595         // We can only perform kills for paths that refer to a unique location,
 596         // since otherwise we may kill a move from one location with an
 597         // assignment referring to another location.
 598
 599         let loan_path = self.path_loan_path(path);
 600         if loan_path_is_precise(&*loan_path) {
 601             self.each_applicable_move(path, |move_index| {
 602                 dfcx_moves.add_kill(kill_id, move_index.get());
 603                 true
 604             });
 605         }
 606     }
 607 }
 608
 609 impl<'a, 'tcx> FlowedMoveData<'a, 'tcx> {
 610     pub fn new(move_data: MoveData<'tcx>,
 611                tcx: &'a ty::ctxt<'tcx>,
 612                cfg: &cfg::CFG,
 613                id_range: ast_util::IdRange,
 614                decl: &ast::FnDecl,
 615                body: &ast::Block)
 616                -> FlowedMoveData<'a, 'tcx> {
 617         let mut dfcx_moves =
 618             DataFlowContext::new(tcx,
 619                                  "flowed_move_data_moves",
 620                                  Some(decl),
 621                                  cfg,
 622                                  MoveDataFlowOperator,
 623                                  id_range,
 624                                  move_data.moves.borrow().len());
 625         let mut dfcx_assign =
 626             DataFlowContext::new(tcx,
 627                                  "flowed_move_data_assigns",
 628                                  Some(decl),
 629                                  cfg,
 630                                  AssignDataFlowOperator,
 631                                  id_range,
 632                                  move_data.var_assignments.borrow().len());
 633
 634         move_data.fixup_fragment_sets(tcx);
 635
 636         move_data.add_gen_kills(tcx,
 637                                 &mut dfcx_moves,
 638                                 &mut dfcx_assign);
 639
 640         dfcx_moves.add_kills_from_flow_exits(cfg);
 641         dfcx_assign.add_kills_from_flow_exits(cfg);
 642
 643         dfcx_moves.propagate(cfg, body);
 644         dfcx_assign.propagate(cfg, body);
 645
 646         FlowedMoveData {
 647             move_data: move_data,
 648             dfcx_moves: dfcx_moves,
 649             dfcx_assign: dfcx_assign,
 650         }
 651     }
 652
 653     pub fn kind_of_move_of_path(&self,
 654                                 id: ast::NodeId,
 655                                 loan_path: &Rc<LoanPath<'tcx>>)
 656                                 -> Option<MoveKind> {
 657         //! Returns the kind of a move of `loan_path` by `id`, if one exists.
 658
 659         let mut ret = None;
 660         for loan_path_index in self.move_data.path_map.borrow().get(&*loan_path).iter() {
 661             self.dfcx_moves.each_gen_bit(id, |move_index| {
 662                 let the_move = self.move_data.moves.borrow();
 663                 let the_move = (*the_move)[move_index];
 664                 if the_move.path == **loan_path_index {
 665                     ret = Some(the_move.kind);
 666                     false
 667                 } else {
 668                     true
 669                 }
 670             });
 671         }
 672         ret
 673     }
 674
 675     /// Iterates through each move of `loan_path` (or some base path of `loan_path`) that *may*
 676     /// have occurred on entry to `id` without an intervening assignment. In other words, any moves
 677     /// that would invalidate a reference to `loan_path` at location `id`.
 678     pub fn each_move_of(&self,
 679                         id: ast::NodeId,
 680                         loan_path: &Rc<LoanPath<'tcx>>,
 681                         f: |&Move, &LoanPath<'tcx>| -> bool)
 682                         -> bool {
 683         // Bad scenarios:
 684         //
 685         // 1. Move of `a.b.c`, use of `a.b.c`
 686         // 2. Move of `a.b.c`, use of `a.b.c.d`
 687         // 3. Move of `a.b.c`, use of `a` or `a.b`
 688         //
 689         // OK scenario:
 690         //
 691         // 4. move of `a.b.c`, use of `a.b.d`
 692
 693         let base_indices = self.move_data.existing_base_paths(loan_path);
 694         if base_indices.is_empty() {
 695             return true;
 696         }
 697
 698         let opt_loan_path_index = self.move_data.existing_move_path(loan_path);
 699
 700         let mut ret = true;
 701
 702         self.dfcx_moves.each_bit_on_entry(id, |index| {
 703             let the_move = self.move_data.moves.borrow();
 704             let the_move = &(*the_move)[index];
 705             let moved_path = the_move.path;
 706             if base_indices.iter().any(|x| x == &moved_path) {
 707                 // Scenario 1 or 2: `loan_path` or some base path of
 708                 // `loan_path` was moved.
 709                 if !f(the_move, &*self.move_data.path_loan_path(moved_path)) {
 710                     ret = false;
 711                 }
 712             } else {
 713                 for &loan_path_index in opt_loan_path_index.iter() {
 714                     let cont = self.move_data.each_base_path(moved_path, |p| {
 715                         if p == loan_path_index {
 716                             // Scenario 3: some extension of `loan_path`
 717                             // was moved
 718                             f(the_move,
 719                               &*self.move_data.path_loan_path(moved_path))
 720                         } else {
 721                             true
 722                         }
 723                     });
 724                     if !cont { ret = false; break }
 725                 }
 726             }
 727             ret
 728         })
 729     }
 730
 731     /// Iterates through every assignment to `loan_path` that may have occurred on entry to `id`.
 732     /// `loan_path` must be a single variable.
 733     pub fn each_assignment_of(&self,
 734                               id: ast::NodeId,
 735                               loan_path: &Rc<LoanPath<'tcx>>,
 736                               f: |&Assignment| -> bool)
 737                               -> bool {
 738         let loan_path_index = {
 739             match self.move_data.existing_move_path(loan_path) {
 740                 Some(i) => i,
 741                 None => {
 742                     // if there were any assignments, it'd have an index
 743                     return true;
 744                 }
 745             }
 746         };
 747
 748         self.dfcx_assign.each_bit_on_entry(id, |index| {
 749             let assignment = self.move_data.var_assignments.borrow();
 750             let assignment = &(*assignment)[index];
 751             if assignment.path == loan_path_index && !f(assignment) {
 752                 false
 753             } else {
 754                 true
 755             }
 756         })
 757     }
 758 }
 759
 760 impl BitwiseOperator for MoveDataFlowOperator {
 761     #[inline]
 762     fn join(&self, succ: uint, pred: uint) -> uint {
 763         succ | pred // moves from both preds are in scope
 764     }
 765 }
 766
 767 impl DataFlowOperator for MoveDataFlowOperator {
 768     #[inline]
 769     fn initial_value(&self) -> bool {
 770         false // no loans in scope by default
 771     }
 772 }
 773
 774 impl BitwiseOperator for AssignDataFlowOperator {
 775     #[inline]
 776     fn join(&self, succ: uint, pred: uint) -> uint {
 777         succ | pred // moves from both preds are in scope
 778     }
 779 }
 780
 781 impl DataFlowOperator for AssignDataFlowOperator {
 782     #[inline]
 783     fn initial_value(&self) -> bool {
 784         false // no assignments in scope by default
 785     }
 786 }