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