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