src/librustc_borrowck/borrowck/gather_loans/mod.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 // Gathering loans
  13 //
  14 // The borrow check proceeds in two phases. In phase one, we gather the full
  15 // set of loans that are required at any point.  These are sorted according to
  16 // their associated scopes.  In phase two, checking loans, we will then make
  17 // sure that all of these loans are honored.
  18
  19 use borrowck::*;
  20 use borrowck::move_data::MoveData;
  21 use rustc::middle::expr_use_visitor as euv;
  22 use rustc::middle::mem_categorization as mc;
  23 use rustc::middle::mem_categorization::Categorization;
  24 use rustc::middle::region;
  25 use rustc::ty::{self, TyCtxt};
  26
  27 use syntax::ast;
  28 use syntax_pos::Span;
  29 use rustc::hir;
  30
  31 use self::restrictions::RestrictionResult;
  32
  33 mod lifetime;
  34 mod restrictions;
  35 mod gather_moves;
  36 mod move_error;
  37
  38 pub fn gather_loans_in_fn<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
  39                                     body: hir::BodyId)
  40                                     -> (Vec<Loan<'tcx>>, move_data::MoveData<'tcx>) {
  41     let def_id = bccx.tcx.hir.body_owner_def_id(body);
  42     let param_env = bccx.tcx.param_env(def_id);
  43     let mut glcx = GatherLoanCtxt {
  44         bccx,
  45         all_loans: Vec::new(),
  46         item_ub: region::Scope::Node(bccx.tcx.hir.body(body).value.hir_id.local_id),
  47         move_data: MoveData::default(),
  48         move_error_collector: move_error::MoveErrorCollector::new(),
  49     };
  50
  51     let rvalue_promotable_map = bccx.tcx.rvalue_promotable_map(def_id);
  52     euv::ExprUseVisitor::new(&mut glcx,
  53                              bccx.tcx,
  54                              param_env,
  55                              &bccx.region_scope_tree,
  56                              bccx.tables,
  57                              Some(rvalue_promotable_map))
  58         .consume_body(bccx.body);
  59
  60     glcx.report_potential_errors();
  61     let GatherLoanCtxt { all_loans, move_data, .. } = glcx;
  62     (all_loans, move_data)
  63 }
  64
  65 struct GatherLoanCtxt<'a, 'tcx: 'a> {
  66     bccx: &'a BorrowckCtxt<'a, 'tcx>,
  67     move_data: move_data::MoveData<'tcx>,
  68     move_error_collector: move_error::MoveErrorCollector<'tcx>,
  69     all_loans: Vec<Loan<'tcx>>,
  70     /// `item_ub` is used as an upper-bound on the lifetime whenever we
  71     /// ask for the scope of an expression categorized as an upvar.
  72     item_ub: region::Scope,
  73 }
  74
  75 impl<'a, 'tcx> euv::Delegate<'tcx> for GatherLoanCtxt<'a, 'tcx> {
  76     fn consume(&mut self,
  77                consume_id: ast::NodeId,
  78                _consume_span: Span,
  79                cmt: &mc::cmt_<'tcx>,
  80                mode: euv::ConsumeMode) {
  81         debug!("consume(consume_id={}, cmt={:?}, mode={:?})",
  82                consume_id, cmt, mode);
  83
  84         match mode {
  85             euv::Move(move_reason) => {
  86                 gather_moves::gather_move_from_expr(
  87                     self.bccx, &self.move_data, &mut self.move_error_collector,
  88                     self.bccx.tcx.hir.node_to_hir_id(consume_id).local_id, cmt, move_reason);
  89             }
  90             euv::Copy => { }
  91         }
  92     }
  93
  94     fn matched_pat(&mut self,
  95                    matched_pat: &hir::Pat,
  96                    cmt: &mc::cmt_<'tcx>,
  97                    mode: euv::MatchMode) {
  98         debug!("matched_pat(matched_pat={:?}, cmt={:?}, mode={:?})",
  99                matched_pat,
 100                cmt,
 101                mode);
 102     }
 103
 104     fn consume_pat(&mut self,
 105                    consume_pat: &hir::Pat,
 106                    cmt: &mc::cmt_<'tcx>,
 107                    mode: euv::ConsumeMode) {
 108         debug!("consume_pat(consume_pat={:?}, cmt={:?}, mode={:?})",
 109                consume_pat,
 110                cmt,
 111                mode);
 112
 113         match mode {
 114             euv::Copy => { return; }
 115             euv::Move(_) => { }
 116         }
 117
 118         gather_moves::gather_move_from_pat(
 119             self.bccx, &self.move_data, &mut self.move_error_collector,
 120             consume_pat, cmt);
 121     }
 122
 123     fn borrow(&mut self,
 124               borrow_id: ast::NodeId,
 125               borrow_span: Span,
 126               cmt: &mc::cmt_<'tcx>,
 127               loan_region: ty::Region<'tcx>,
 128               bk: ty::BorrowKind,
 129               loan_cause: euv::LoanCause)
 130     {
 131         debug!("borrow(borrow_id={}, cmt={:?}, loan_region={:?}, \
 132                bk={:?}, loan_cause={:?})",
 133                borrow_id, cmt, loan_region,
 134                bk, loan_cause);
 135         let hir_id = self.bccx.tcx.hir.node_to_hir_id(borrow_id);
 136         self.guarantee_valid(hir_id.local_id,
 137                              borrow_span,
 138                              cmt,
 139                              bk,
 140                              loan_region,
 141                              loan_cause);
 142     }
 143
 144     fn mutate(&mut self,
 145               assignment_id: ast::NodeId,
 146               assignment_span: Span,
 147               assignee_cmt: &mc::cmt_<'tcx>,
 148               mode: euv::MutateMode)
 149     {
 150         self.guarantee_assignment_valid(assignment_id,
 151                                         assignment_span,
 152                                         assignee_cmt,
 153                                         mode);
 154     }
 155
 156     fn decl_without_init(&mut self, id: ast::NodeId, _span: Span) {
 157         let ty = self.bccx
 158                      .tables
 159                      .node_id_to_type(self.bccx.tcx.hir.node_to_hir_id(id));
 160         gather_moves::gather_decl(self.bccx, &self.move_data, id, ty);
 161     }
 162 }
 163
 164 /// Implements the A-* rules in README.md.
 165 fn check_aliasability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
 166                                 borrow_span: Span,
 167                                 loan_cause: AliasableViolationKind,
 168                                 cmt: &mc::cmt_<'tcx>,
 169                                 req_kind: ty::BorrowKind)
 170                                 -> Result<(),()> {
 171
 172     let aliasability = cmt.freely_aliasable();
 173     debug!("check_aliasability aliasability={:?} req_kind={:?}",
 174            aliasability, req_kind);
 175
 176     match (aliasability, req_kind) {
 177         (mc::Aliasability::NonAliasable, _) => {
 178             /* Uniquely accessible path -- OK for `&` and `&mut` */
 179             Ok(())
 180         }
 181         (mc::Aliasability::FreelyAliasable(mc::AliasableStatic), ty::ImmBorrow) => {
 182             // Borrow of an immutable static item.
 183             Ok(())
 184         }
 185         (mc::Aliasability::FreelyAliasable(mc::AliasableStaticMut), _) => {
 186             // Even touching a static mut is considered unsafe. We assume the
 187             // user knows what they're doing in these cases.
 188             Ok(())
 189         }
 190         (mc::Aliasability::FreelyAliasable(alias_cause), ty::UniqueImmBorrow) |
 191         (mc::Aliasability::FreelyAliasable(alias_cause), ty::MutBorrow) => {
 192             bccx.report_aliasability_violation(
 193                         borrow_span,
 194                         loan_cause,
 195                         alias_cause,
 196                         cmt);
 197             Err(())
 198         }
 199         (..) => {
 200             Ok(())
 201         }
 202     }
 203 }
 204
 205 /// Implements the M-* rules in README.md.
 206 fn check_mutability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
 207                               borrow_span: Span,
 208                               cause: AliasableViolationKind,
 209                               cmt: &mc::cmt_<'tcx>,
 210                               req_kind: ty::BorrowKind)
 211                               -> Result<(),()> {
 212     debug!("check_mutability(cause={:?} cmt={:?} req_kind={:?}",
 213            cause, cmt, req_kind);
 214     match req_kind {
 215         ty::UniqueImmBorrow | ty::ImmBorrow => {
 216             match cmt.mutbl {
 217                 // I am intentionally leaving this here to help
 218                 // refactoring if, in the future, we should add new
 219                 // kinds of mutability.
 220                 mc::McImmutable | mc::McDeclared | mc::McInherited => {
 221                     // both imm and mut data can be lent as imm;
 222                     // for mutable data, this is a freeze
 223                     Ok(())
 224                 }
 225             }
 226         }
 227
 228         ty::MutBorrow => {
 229             // Only mutable data can be lent as mutable.
 230             if !cmt.mutbl.is_mutable() {
 231                 Err(bccx.report(BckError { span: borrow_span,
 232                                            cause,
 233                                            cmt,
 234                                            code: err_mutbl }))
 235             } else {
 236                 Ok(())
 237             }
 238         }
 239     }
 240 }
 241
 242 impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
 243     pub fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> { self.bccx.tcx }
 244
 245     /// Guarantees that `cmt` is assignable, or reports an error.
 246     fn guarantee_assignment_valid(&mut self,
 247                                   assignment_id: ast::NodeId,
 248                                   assignment_span: Span,
 249                                   cmt: &mc::cmt_<'tcx>,
 250                                   mode: euv::MutateMode) {
 251
 252         let opt_lp = opt_loan_path(cmt);
 253         debug!("guarantee_assignment_valid(assignment_id={}, cmt={:?}) opt_lp={:?}",
 254                assignment_id, cmt, opt_lp);
 255
 256         if let Categorization::Local(..) = cmt.cat {
 257             // Only re-assignments to locals require it to be
 258             // mutable - this is checked in check_loans.
 259         } else {
 260             // Check that we don't allow assignments to non-mutable data.
 261             if check_mutability(self.bccx, assignment_span, MutabilityViolation,
 262                                 cmt, ty::MutBorrow).is_err() {
 263                 return; // reported an error, no sense in reporting more.
 264             }
 265         }
 266
 267         // Check that we don't allow assignments to aliasable data
 268         if check_aliasability(self.bccx, assignment_span, MutabilityViolation,
 269                               cmt, ty::MutBorrow).is_err() {
 270             return; // reported an error, no sense in reporting more.
 271         }
 272
 273         match opt_lp {
 274             Some(lp) => {
 275                 if let Categorization::Local(..) = cmt.cat {
 276                     // Only re-assignments to locals require it to be
 277                     // mutable - this is checked in check_loans.
 278                 } else {
 279                     self.mark_loan_path_as_mutated(&lp);
 280                 }
 281                 gather_moves::gather_assignment(self.bccx, &self.move_data,
 282                                                 self.bccx.tcx.hir.node_to_hir_id(assignment_id)
 283                                                     .local_id,
 284                                                 assignment_span,
 285                                                 lp,
 286                                                 self.bccx.tcx.hir.node_to_hir_id(cmt.id).local_id,
 287                                                 mode);
 288             }
 289             None => {
 290                 // This can occur with e.g. `*foo() = 5`.  In such
 291                 // cases, there is no need to check for conflicts
 292                 // with moves etc, just ignore.
 293             }
 294         }
 295     }
 296
 297     /// Guarantees that `addr_of(cmt)` will be valid for the duration of `static_scope_r`, or
 298     /// reports an error.  This may entail taking out loans, which will be added to the
 299     /// `req_loan_map`.
 300     fn guarantee_valid(&mut self,
 301                        borrow_id: hir::ItemLocalId,
 302                        borrow_span: Span,
 303                        cmt: &mc::cmt_<'tcx>,
 304                        req_kind: ty::BorrowKind,
 305                        loan_region: ty::Region<'tcx>,
 306                        cause: euv::LoanCause) {
 307         debug!("guarantee_valid(borrow_id={:?}, cmt={:?}, \
 308                 req_mutbl={:?}, loan_region={:?})",
 309                borrow_id,
 310                cmt,
 311                req_kind,
 312                loan_region);
 313
 314         // a loan for the empty region can never be dereferenced, so
 315         // it is always safe
 316         if *loan_region == ty::ReEmpty {
 317             return;
 318         }
 319
 320         // Check that the lifetime of the borrow does not exceed
 321         // the lifetime of the data being borrowed.
 322         if lifetime::guarantee_lifetime(self.bccx, self.item_ub,
 323                                         borrow_span, cause, cmt, loan_region, req_kind).is_err() {
 324             return; // reported an error, no sense in reporting more.
 325         }
 326
 327         // Check that we don't allow mutable borrows of non-mutable data.
 328         if check_mutability(self.bccx, borrow_span, BorrowViolation(cause),
 329                             cmt, req_kind).is_err() {
 330             return; // reported an error, no sense in reporting more.
 331         }
 332
 333         // Check that we don't allow mutable borrows of aliasable data.
 334         if check_aliasability(self.bccx, borrow_span, BorrowViolation(cause),
 335                               cmt, req_kind).is_err() {
 336             return; // reported an error, no sense in reporting more.
 337         }
 338
 339         // Compute the restrictions that are required to enforce the
 340         // loan is safe.
 341         let restr = restrictions::compute_restrictions(
 342             self.bccx, borrow_span, cause, &cmt, loan_region);
 343
 344         debug!("guarantee_valid(): restrictions={:?}", restr);
 345
 346         // Create the loan record (if needed).
 347         let loan = match restr {
 348             RestrictionResult::Safe => {
 349                 // No restrictions---no loan record necessary
 350                 return;
 351             }
 352
 353             RestrictionResult::SafeIf(loan_path, restricted_paths) => {
 354                 let loan_scope = match *loan_region {
 355                     ty::ReScope(scope) => scope,
 356
 357                     ty::ReEarlyBound(ref br) => {
 358                         self.bccx.region_scope_tree.early_free_scope(self.tcx(), br)
 359                     }
 360
 361                     ty::ReFree(ref fr) => {
 362                         self.bccx.region_scope_tree.free_scope(self.tcx(), fr)
 363                     }
 364
 365                     ty::ReStatic => self.item_ub,
 366
 367                     ty::ReCanonical(_) |
 368                     ty::ReEmpty |
 369                     ty::ReClosureBound(..) |
 370                     ty::ReLateBound(..) |
 371                     ty::ReVar(..) |
 372                     ty::ReSkolemized(..) |
 373                     ty::ReErased => {
 374                         span_bug!(
 375                             cmt.span,
 376                             "invalid borrow lifetime: {:?}",
 377                             loan_region);
 378                     }
 379                 };
 380                 debug!("loan_scope = {:?}", loan_scope);
 381
 382                 let borrow_scope = region::Scope::Node(borrow_id);
 383                 let gen_scope = self.compute_gen_scope(borrow_scope, loan_scope);
 384                 debug!("gen_scope = {:?}", gen_scope);
 385
 386                 let kill_scope = self.compute_kill_scope(loan_scope, &loan_path);
 387                 debug!("kill_scope = {:?}", kill_scope);
 388
 389                 if req_kind == ty::MutBorrow {
 390                     self.mark_loan_path_as_mutated(&loan_path);
 391                 }
 392
 393                 Loan {
 394                     index: self.all_loans.len(),
 395                     loan_path,
 396                     kind: req_kind,
 397                     gen_scope,
 398                     kill_scope,
 399                     span: borrow_span,
 400                     restricted_paths,
 401                     cause,
 402                 }
 403             }
 404         };
 405
 406         debug!("guarantee_valid(borrow_id={:?}), loan={:?}",
 407                borrow_id, loan);
 408
 409         // let loan_path = loan.loan_path;
 410         // let loan_gen_scope = loan.gen_scope;
 411         // let loan_kill_scope = loan.kill_scope;
 412         self.all_loans.push(loan);
 413
 414         // if loan_gen_scope != borrow_id {
 415             // FIXME(https://github.com/rust-lang/rfcs/issues/811) Nested method calls
 416             //
 417             // Typically, the scope of the loan includes the point at
 418             // which the loan is originated. This
 419             // This is a subtle case. See the test case
 420             // <compile-fail/borrowck-bad-nested-calls-free.rs>
 421             // to see what we are guarding against.
 422
 423             //let restr = restrictions::compute_restrictions(
 424             //    self.bccx, borrow_span, cmt, RESTR_EMPTY);
 425             //let loan = {
 426             //    Loan {
 427             //        index: self.all_loans.len(),
 428             //        loan_path,
 429             //        cmt,
 430             //        mutbl: ConstMutability,
 431             //        gen_scope: borrow_id,
 432             //        kill_scope,
 433             //        span: borrow_span,
 434             //        restrictions,
 435             //    }
 436         // }
 437     }
 438
 439     pub fn mark_loan_path_as_mutated(&self, loan_path: &LoanPath) {
 440         //! For mutable loans of content whose mutability derives
 441         //! from a local variable, mark the mutability decl as necessary.
 442
 443         let mut wrapped_path = Some(loan_path);
 444         let mut through_borrow = false;
 445
 446         while let Some(current_path) = wrapped_path {
 447             wrapped_path = match current_path.kind {
 448                 LpVar(local_id) => {
 449                     if !through_borrow {
 450                         let hir_id = self.bccx.tcx.hir.node_to_hir_id(local_id);
 451                         self.bccx.used_mut_nodes.borrow_mut().insert(hir_id);
 452                     }
 453                     None
 454                 }
 455                 LpUpvar(ty::UpvarId{ var_id, closure_expr_id: _ }) => {
 456                     self.bccx.used_mut_nodes.borrow_mut().insert(var_id);
 457                     None
 458                 }
 459                 LpExtend(ref base, mc::McInherited, LpDeref(pointer_kind)) |
 460                 LpExtend(ref base, mc::McDeclared, LpDeref(pointer_kind)) => {
 461                     if pointer_kind != mc::Unique {
 462                         through_borrow = true;
 463                     }
 464                     Some(base)
 465                 }
 466                 LpDowncast(ref base, _) |
 467                 LpExtend(ref base, mc::McInherited, _) |
 468                 LpExtend(ref base, mc::McDeclared, _) => {
 469                     Some(base)
 470                 }
 471                 LpExtend(_, mc::McImmutable, _) => {
 472                     // Nothing to do.
 473                     None
 474                 }
 475             }
 476         }
 477
 478     }
 479
 480     pub fn compute_gen_scope(&self,
 481                              borrow_scope: region::Scope,
 482                              loan_scope: region::Scope)
 483                              -> region::Scope {
 484         //! Determine when to introduce the loan. Typically the loan
 485         //! is introduced at the point of the borrow, but in some cases,
 486         //! notably method arguments, the loan may be introduced only
 487         //! later, once it comes into scope.
 488
 489         if self.bccx.region_scope_tree.is_subscope_of(borrow_scope, loan_scope) {
 490             borrow_scope
 491         } else {
 492             loan_scope
 493         }
 494     }
 495
 496     pub fn compute_kill_scope(&self, loan_scope: region::Scope, lp: &LoanPath<'tcx>)
 497                               -> region::Scope {
 498         //! Determine when the loan restrictions go out of scope.
 499         //! This is either when the lifetime expires or when the
 500         //! local variable which roots the loan-path goes out of scope,
 501         //! whichever happens faster.
 502         //!
 503         //! It may seem surprising that we might have a loan region
 504         //! larger than the variable which roots the loan-path; this can
 505         //! come about when variables of `&mut` type are re-borrowed,
 506         //! as in this example:
 507         //!
 508         //!     struct Foo { counter: u32 }
 509         //!
 510         //!     fn counter<'a>(v: &'a mut Foo) -> &'a mut u32 {
 511         //!         &mut v.counter
 512         //!     }
 513         //!
 514         //! In this case, the reference (`'a`) outlives the
 515         //! variable `v` that hosts it. Note that this doesn't come up
 516         //! with immutable `&` pointers, because borrows of such pointers
 517         //! do not require restrictions and hence do not cause a loan.
 518
 519         let lexical_scope = lp.kill_scope(self.bccx);
 520         if self.bccx.region_scope_tree.is_subscope_of(lexical_scope, loan_scope) {
 521             lexical_scope
 522         } else {
 523             assert!(self.bccx.region_scope_tree.is_subscope_of(loan_scope, lexical_scope));
 524             loan_scope
 525         }
 526     }
 527
 528     pub fn report_potential_errors(&self) {
 529         self.move_error_collector.report_potential_errors(self.bccx);
 530     }
 531 }