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