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         let paths = self.paths.borrow();
 187         paths.get().get(index.get()).loan_path
 188     }
 189
 190     fn path_parent(&self, index: MovePathIndex) -> MovePathIndex {
 191         let paths = self.paths.borrow();
 192         paths.get().get(index.get()).parent
 193     }
 194
 195     fn path_first_move(&self, index: MovePathIndex) -> MoveIndex {
 196         let paths = self.paths.borrow();
 197         paths.get().get(index.get()).first_move
 198     }
 199
 200     fn path_first_child(&self, index: MovePathIndex) -> MovePathIndex {
 201         let paths = self.paths.borrow();
 202         paths.get().get(index.get()).first_child
 203     }
 204
 205     fn path_next_sibling(&self, index: MovePathIndex) -> MovePathIndex {
 206         let paths = self.paths.borrow();
 207         paths.get().get(index.get()).next_sibling
 208     }
 209
 210     fn set_path_first_move(&self,
 211                            index: MovePathIndex,
 212                            first_move: MoveIndex) {
 213         let mut paths = self.paths.borrow_mut();
 214         paths.get().get_mut(index.get()).first_move = first_move
 215     }
 216
 217     fn set_path_first_child(&self,
 218                             index: MovePathIndex,
 219                             first_child: MovePathIndex) {
 220         let mut paths = self.paths.borrow_mut();
 221         paths.get().get_mut(index.get()).first_child = first_child
 222     }
 223
 224     fn move_next_move(&self, index: MoveIndex) -> MoveIndex {
 225         //! Type safe indexing operator
 226         let moves = self.moves.borrow();
 227         moves.get().get(index.get()).next_move
 228     }
 229
 230     fn is_var_path(&self, index: MovePathIndex) -> bool {
 231         //! True if `index` refers to a variable
 232         self.path_parent(index) == InvalidMovePathIndex
 233     }
 234
 235     pub fn move_path(&self,
 236                      tcx: &ty::ctxt,
 237                      lp: @LoanPath) -> MovePathIndex {
 238         /*!
 239          * Returns the existing move path index for `lp`, if any,
 240          * and otherwise adds a new index for `lp` and any of its
 241          * base paths that do not yet have an index.
 242          */
 243
 244         {
 245             let path_map = self.path_map.borrow();
 246             match path_map.get().find(&lp) {
 247                 Some(&index) => {
 248                     return index;
 249                 }
 250                 None => {}
 251             }
 252         }
 253
 254         let index = match *lp {
 255             LpVar(..) => {
 256                 let mut paths = self.paths.borrow_mut();
 257                 let index = MovePathIndex(paths.get().len());
 258
 259                 paths.get().push(MovePath {
 260                     loan_path: lp,
 261                     parent: InvalidMovePathIndex,
 262                     first_move: InvalidMoveIndex,
 263                     first_child: InvalidMovePathIndex,
 264                     next_sibling: InvalidMovePathIndex,
 265                 });
 266
 267                 index
 268             }
 269
 270             LpExtend(base, _, _) => {
 271                 let parent_index = self.move_path(tcx, base);
 272
 273                 let index = {
 274                     let paths = self.paths.borrow();
 275                     MovePathIndex(paths.get().len())
 276                 };
 277
 278                 let next_sibling = self.path_first_child(parent_index);
 279                 self.set_path_first_child(parent_index, index);
 280
 281                 {
 282                     let mut paths = self.paths.borrow_mut();
 283                     paths.get().push(MovePath {
 284                         loan_path: lp,
 285                         parent: parent_index,
 286                         first_move: InvalidMoveIndex,
 287                         first_child: InvalidMovePathIndex,
 288                         next_sibling: next_sibling,
 289                     });
 290                 }
 291
 292                 index
 293             }
 294         };
 295
 296         debug!("move_path(lp={}, index={:?})",
 297                lp.repr(tcx),
 298                index);
 299
 300         let paths = self.paths.borrow();
 301         assert_eq!(index.get(), paths.get().len() - 1);
 302
 303         let mut path_map = self.path_map.borrow_mut();
 304         path_map.get().insert(lp, index);
 305         return index;
 306     }
 307
 308     fn existing_move_path(&self,
 309                           lp: @LoanPath)
 310                           -> Option<MovePathIndex> {
 311         let path_map = self.path_map.borrow();
 312         path_map.get().find_copy(&lp)
 313     }
 314
 315     fn existing_base_paths(&self,
 316                            lp: @LoanPath)
 317                            -> Vec<MovePathIndex> {
 318         let mut result = vec!();
 319         self.add_existing_base_paths(lp, &mut result);
 320         result
 321     }
 322
 323     fn add_existing_base_paths(&self,
 324                                lp: @LoanPath,
 325                                result: &mut Vec<MovePathIndex>) {
 326         /*!
 327          * Adds any existing move path indices for `lp` and any base
 328          * paths of `lp` to `result`, but does not add new move paths
 329          */
 330
 331         let index_opt = {
 332             let path_map = self.path_map.borrow();
 333             path_map.get().find_copy(&lp)
 334         };
 335         match index_opt {
 336             Some(index) => {
 337                 self.each_base_path(index, |p| {
 338                     result.push(p);
 339                     true
 340                 });
 341             }
 342             None => {
 343                 match *lp {
 344                     LpVar(..) => { }
 345                     LpExtend(b, _, _) => {
 346                         self.add_existing_base_paths(b, result);
 347                     }
 348                 }
 349             }
 350         }
 351
 352     }
 353
 354     pub fn add_move(&self,
 355                     tcx: &ty::ctxt,
 356                     lp: @LoanPath,
 357                     id: ast::NodeId,
 358                     kind: MoveKind) {
 359         /*!
 360          * Adds a new move entry for a move of `lp` that occurs at
 361          * location `id` with kind `kind`.
 362          */
 363
 364         debug!("add_move(lp={}, id={:?}, kind={:?})",
 365                lp.repr(tcx),
 366                id,
 367                kind);
 368
 369         let path_index = self.move_path(tcx, lp);
 370         let move_index = {
 371             let moves = self.moves.borrow();
 372             MoveIndex(moves.get().len())
 373         };
 374
 375         let next_move = self.path_first_move(path_index);
 376         self.set_path_first_move(path_index, move_index);
 377
 378         {
 379             let mut moves = self.moves.borrow_mut();
 380             moves.get().push(Move {
 381                 path: path_index,
 382                 id: id,
 383                 kind: kind,
 384                 next_move: next_move
 385             });
 386         }
 387     }
 388
 389     pub fn add_assignment(&self,
 390                           tcx: &ty::ctxt,
 391                           lp: @LoanPath,
 392                           assign_id: ast::NodeId,
 393                           span: Span,
 394                           assignee_id: ast::NodeId,
 395                           is_also_move: bool) {
 396         /*!
 397          * Adds a new record for an assignment to `lp` that occurs at
 398          * location `id` with the given `span`.
 399          */
 400
 401         debug!("add_assignment(lp={}, assign_id={:?}, assignee_id={:?}",
 402                lp.repr(tcx), assign_id, assignee_id);
 403
 404         let path_index = self.move_path(tcx, lp);
 405
 406         if !is_also_move {
 407             let mut assignee_ids = self.assignee_ids.borrow_mut();
 408             assignee_ids.get().insert(assignee_id);
 409         }
 410
 411         let assignment = Assignment {
 412             path: path_index,
 413             id: assign_id,
 414             span: span,
 415         };
 416
 417         if self.is_var_path(path_index) {
 418             let mut var_assignments = self.var_assignments.borrow_mut();
 419             debug!("add_assignment[var](lp={}, assignment={}, path_index={:?})",
 420                    lp.repr(tcx), var_assignments.get().len(), path_index);
 421
 422             var_assignments.get().push(assignment);
 423         } else {
 424             debug!("add_assignment[path](lp={}, path_index={:?})",
 425                    lp.repr(tcx), path_index);
 426
 427             {
 428                 let mut path_assignments = self.path_assignments.borrow_mut();
 429                 path_assignments.get().push(assignment);
 430             }
 431         }
 432     }
 433
 434     fn add_gen_kills(&self,
 435                      tcx: &ty::ctxt,
 436                      dfcx_moves: &mut MoveDataFlow,
 437                      dfcx_assign: &mut AssignDataFlow) {
 438         /*!
 439          * Adds the gen/kills for the various moves and
 440          * assignments into the provided data flow contexts.
 441          * Moves are generated by moves and killed by assignments and
 442          * scoping. Assignments are generated by assignment to variables and
 443          * killed by scoping. See `doc.rs` for more details.
 444          */
 445
 446         {
 447             let moves = self.moves.borrow();
 448             for (i, move) in moves.get().iter().enumerate() {
 449                 dfcx_moves.add_gen(move.id, i);
 450             }
 451         }
 452
 453         {
 454             let var_assignments = self.var_assignments.borrow();
 455             for (i, assignment) in var_assignments.get().iter().enumerate() {
 456                 dfcx_assign.add_gen(assignment.id, i);
 457                 self.kill_moves(assignment.path, assignment.id, dfcx_moves);
 458             }
 459         }
 460
 461         {
 462             let path_assignments = self.path_assignments.borrow();
 463             for assignment in path_assignments.get().iter() {
 464                 self.kill_moves(assignment.path, assignment.id, dfcx_moves);
 465             }
 466         }
 467
 468         // Kill all moves related to a variable `x` when it goes out
 469         // of scope:
 470         {
 471             let paths = self.paths.borrow();
 472             for path in paths.get().iter() {
 473                 match *path.loan_path {
 474                     LpVar(id) => {
 475                         let kill_id = tcx.region_maps.var_scope(id);
 476                         let path = {
 477                             let path_map = self.path_map.borrow();
 478                             *path_map.get().get(&path.loan_path)
 479                         };
 480                         self.kill_moves(path, kill_id, dfcx_moves);
 481                     }
 482                     LpExtend(..) => {}
 483                 }
 484             }
 485         }
 486
 487         // Kill all assignments when the variable goes out of scope:
 488         {
 489             let var_assignments = self.var_assignments.borrow();
 490             for (assignment_index, assignment) in
 491                     var_assignments.get().iter().enumerate() {
 492                 match *self.path_loan_path(assignment.path) {
 493                     LpVar(id) => {
 494                         let kill_id = tcx.region_maps.var_scope(id);
 495                         dfcx_assign.add_kill(kill_id, assignment_index);
 496                     }
 497                     LpExtend(..) => {
 498                         tcx.sess.bug("var assignment for non var path");
 499                     }
 500                 }
 501             }
 502         }
 503     }
 504
 505     fn each_base_path(&self, index: MovePathIndex, f: |MovePathIndex| -> bool)
 506                       -> bool {
 507         let mut p = index;
 508         while p != InvalidMovePathIndex {
 509             if !f(p) {
 510                 return false;
 511             }
 512             p = self.path_parent(p);
 513         }
 514         return true;
 515     }
 516
 517     fn each_extending_path(&self,
 518                            index: MovePathIndex,
 519                            f: |MovePathIndex| -> bool)
 520                            -> bool {
 521         if !f(index) {
 522             return false;
 523         }
 524
 525         let mut p = self.path_first_child(index);
 526         while p != InvalidMovePathIndex {
 527             if !self.each_extending_path(p, |x| f(x)) {
 528                 return false;
 529             }
 530             p = self.path_next_sibling(p);
 531         }
 532
 533         return true;
 534     }
 535
 536     fn each_applicable_move(&self,
 537                             index0: MovePathIndex,
 538                             f: |MoveIndex| -> bool)
 539                             -> bool {
 540         let mut ret = true;
 541         self.each_extending_path(index0, |index| {
 542             let mut p = self.path_first_move(index);
 543             while p != InvalidMoveIndex {
 544                 if !f(p) {
 545                     ret = false;
 546                     break;
 547                 }
 548                 p = self.move_next_move(p);
 549             }
 550             ret
 551         });
 552         ret
 553     }
 554
 555     fn kill_moves(&self,
 556                   path: MovePathIndex,
 557                   kill_id: ast::NodeId,
 558                   dfcx_moves: &mut MoveDataFlow) {
 559         self.each_applicable_move(path, |move_index| {
 560             dfcx_moves.add_kill(kill_id, move_index.get());
 561             true
 562         });
 563     }
 564 }
 565
 566 impl<'a> FlowedMoveData<'a> {
 567     pub fn new(move_data: MoveData,
 568                tcx: &'a ty::ctxt,
 569                method_map: typeck::MethodMap,
 570                id_range: ast_util::IdRange,
 571                body: &ast::Block)
 572                -> FlowedMoveData<'a> {
 573         let mut dfcx_moves = {
 574             let moves = move_data.moves.borrow();
 575             DataFlowContext::new(tcx,
 576                                  method_map,
 577                                  MoveDataFlowOperator,
 578                                  id_range,
 579                                  moves.get().len())
 580         };
 581         let mut dfcx_assign = {
 582             let var_assignments = move_data.var_assignments.borrow();
 583             DataFlowContext::new(tcx,
 584                                  method_map,
 585                                  AssignDataFlowOperator,
 586                                  id_range,
 587                                  var_assignments.get().len())
 588         };
 589         move_data.add_gen_kills(tcx, &mut dfcx_moves, &mut dfcx_assign);
 590         dfcx_moves.propagate(body);
 591         dfcx_assign.propagate(body);
 592         FlowedMoveData {
 593             move_data: move_data,
 594             dfcx_moves: dfcx_moves,
 595             dfcx_assign: dfcx_assign,
 596         }
 597     }
 598
 599     pub fn each_path_moved_by(&self,
 600                               id: ast::NodeId,
 601                               f: |&Move, @LoanPath| -> bool)
 602                               -> bool {
 603         /*!
 604          * Iterates through each path moved by `id`
 605          */
 606
 607         self.dfcx_moves.each_gen_bit_frozen(id, |index| {
 608             let moves = self.move_data.moves.borrow();
 609             let move = moves.get().get(index);
 610             let moved_path = move.path;
 611             f(move, self.move_data.path_loan_path(moved_path))
 612         })
 613     }
 614
 615     pub fn each_move_of(&self,
 616                         id: ast::NodeId,
 617                         loan_path: @LoanPath,
 618                         f: |&Move, @LoanPath| -> bool)
 619                         -> bool {
 620         /*!
 621          * Iterates through each move of `loan_path` (or some base path
 622          * of `loan_path`) that *may* have occurred on entry to `id` without
 623          * an intervening assignment. In other words, any moves that
 624          * would invalidate a reference to `loan_path` at location `id`.
 625          */
 626
 627         // Bad scenarios:
 628         //
 629         // 1. Move of `a.b.c`, use of `a.b.c`
 630         // 2. Move of `a.b.c`, use of `a.b.c.d`
 631         // 3. Move of `a.b.c`, use of `a` or `a.b`
 632         //
 633         // OK scenario:
 634         //
 635         // 4. move of `a.b.c`, use of `a.b.d`
 636
 637         let base_indices = self.move_data.existing_base_paths(loan_path);
 638         if base_indices.is_empty() {
 639             return true;
 640         }
 641
 642         let opt_loan_path_index = self.move_data.existing_move_path(loan_path);
 643
 644         let mut ret = true;
 645
 646         self.dfcx_moves.each_bit_on_entry_frozen(id, |index| {
 647             let moves = self.move_data.moves.borrow();
 648             let move = moves.get().get(index);
 649             let moved_path = move.path;
 650             if base_indices.iter().any(|x| x == &moved_path) {
 651                 // Scenario 1 or 2: `loan_path` or some base path of
 652                 // `loan_path` was moved.
 653                 if !f(move, self.move_data.path_loan_path(moved_path)) {
 654                     ret = false;
 655                 }
 656             } else {
 657                 for &loan_path_index in opt_loan_path_index.iter() {
 658                     let cont = self.move_data.each_base_path(moved_path, |p| {
 659                         if p == loan_path_index {
 660                             // Scenario 3: some extension of `loan_path`
 661                             // was moved
 662                             f(move, self.move_data.path_loan_path(moved_path))
 663                         } else {
 664                             true
 665                         }
 666                     });
 667                     if !cont { ret = false; break }
 668                 }
 669             }
 670             ret
 671         })
 672     }
 673
 674     pub fn is_assignee(&self,
 675                        id: ast::NodeId)
 676                        -> bool {
 677         //! True if `id` is the id of the LHS of an assignment
 678
 679         let assignee_ids = self.move_data.assignee_ids.borrow();
 680         assignee_ids.get().iter().any(|x| x == &id)
 681     }
 682
 683     pub fn each_assignment_of(&self,
 684                               id: ast::NodeId,
 685                               loan_path: @LoanPath,
 686                               f: |&Assignment| -> bool)
 687                               -> bool {
 688         /*!
 689          * Iterates through every assignment to `loan_path` that
 690          * may have occurred on entry to `id`. `loan_path` must be
 691          * a single variable.
 692          */
 693
 694         let loan_path_index = {
 695             match self.move_data.existing_move_path(loan_path) {
 696                 Some(i) => i,
 697                 None => {
 698                     // if there were any assignments, it'd have an index
 699                     return true;
 700                 }
 701             }
 702         };
 703
 704         self.dfcx_assign.each_bit_on_entry_frozen(id, |index| {
 705             let var_assignments = self.move_data.var_assignments.borrow();
 706             let assignment = var_assignments.get().get(index);
 707             if assignment.path == loan_path_index && !f(assignment) {
 708                 false
 709             } else {
 710                 true
 711             }
 712         })
 713     }
 714 }
 715
 716 impl DataFlowOperator for MoveDataFlowOperator {
 717     #[inline]
 718     fn initial_value(&self) -> bool {
 719         false // no loans in scope by default
 720     }
 721
 722     #[inline]
 723     fn join(&self, succ: uint, pred: uint) -> uint {
 724         succ | pred // moves from both preds are in scope
 725     }
 726 }
 727
 728 impl DataFlowOperator for AssignDataFlowOperator {
 729     #[inline]
 730     fn initial_value(&self) -> bool {
 731         false // no assignments in scope by default
 732     }
 733
 734     #[inline]
 735     fn join(&self, succ: uint, pred: uint) -> uint {
 736         succ | pred // moves from both preds are in scope
 737     }
 738 }