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