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::ast::NodeId;
  29 use syntax_pos::Span;
  30 use rustc::hir;
  31 use rustc::hir::Expr;
  32 use rustc::hir::intravisit;
  33 use rustc::hir::intravisit::Visitor;
  34
  35 use self::restrictions::RestrictionResult;
  36
  37 mod lifetime;
  38 mod restrictions;
  39 mod gather_moves;
  40 mod move_error;
  41
  42 pub fn gather_loans_in_fn<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
  43                                     fn_id: NodeId,
  44                                     decl: &hir::FnDecl,
  45                                     body: &hir::Block)
  46                                     -> (Vec<Loan<'tcx>>,
  47                                         move_data::MoveData<'tcx>) {
  48     let mut glcx = GatherLoanCtxt {
  49         bccx: bccx,
  50         all_loans: Vec::new(),
  51         item_ub: bccx.tcx.region_maps.node_extent(body.id),
  52         move_data: MoveData::new(),
  53         move_error_collector: move_error::MoveErrorCollector::new(),
  54     };
  55
  56     let param_env = ty::ParameterEnvironment::for_item(bccx.tcx, fn_id);
  57     let infcx = bccx.tcx.borrowck_fake_infer_ctxt(param_env);
  58     euv::ExprUseVisitor::new(&mut glcx, &infcx).walk_fn(decl, 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::CodeExtent,
  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                     consume_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         if let Categorization::Downcast(..) = cmt.cat {
 104             gather_moves::gather_match_variant(
 105                 self.bccx, &self.move_data, &mut self.move_error_collector,
 106                 matched_pat, cmt, mode);
 107         }
 108     }
 109
 110     fn consume_pat(&mut self,
 111                    consume_pat: &hir::Pat,
 112                    cmt: mc::cmt<'tcx>,
 113                    mode: euv::ConsumeMode) {
 114         debug!("consume_pat(consume_pat={:?}, cmt={:?}, mode={:?})",
 115                consume_pat,
 116                cmt,
 117                mode);
 118
 119         match mode {
 120             euv::Copy => { return; }
 121             euv::Move(_) => { }
 122         }
 123
 124         gather_moves::gather_move_from_pat(
 125             self.bccx, &self.move_data, &mut self.move_error_collector,
 126             consume_pat, cmt);
 127     }
 128
 129     fn borrow(&mut self,
 130               borrow_id: ast::NodeId,
 131               borrow_span: Span,
 132               cmt: mc::cmt<'tcx>,
 133               loan_region: &'tcx ty::Region,
 134               bk: ty::BorrowKind,
 135               loan_cause: euv::LoanCause)
 136     {
 137         debug!("borrow(borrow_id={}, cmt={:?}, loan_region={:?}, \
 138                bk={:?}, loan_cause={:?})",
 139                borrow_id, cmt, loan_region,
 140                bk, loan_cause);
 141
 142         self.guarantee_valid(borrow_id,
 143                              borrow_span,
 144                              cmt,
 145                              bk,
 146                              loan_region,
 147                              loan_cause);
 148     }
 149
 150     fn mutate(&mut self,
 151               assignment_id: ast::NodeId,
 152               assignment_span: Span,
 153               assignee_cmt: mc::cmt<'tcx>,
 154               mode: euv::MutateMode)
 155     {
 156         self.guarantee_assignment_valid(assignment_id,
 157                                         assignment_span,
 158                                         assignee_cmt,
 159                                         mode);
 160     }
 161
 162     fn decl_without_init(&mut self, id: ast::NodeId, span: Span) {
 163         gather_moves::gather_decl(self.bccx, &self.move_data, id, span, id);
 164     }
 165 }
 166
 167 /// Implements the A-* rules in README.md.
 168 fn check_aliasability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
 169                                 borrow_span: Span,
 170                                 loan_cause: AliasableViolationKind,
 171                                 cmt: mc::cmt<'tcx>,
 172                                 req_kind: ty::BorrowKind)
 173                                 -> Result<(),()> {
 174
 175     let aliasability = cmt.freely_aliasable();
 176     debug!("check_aliasability aliasability={:?} req_kind={:?}",
 177            aliasability, req_kind);
 178
 179     match (aliasability, req_kind) {
 180         (mc::Aliasability::NonAliasable, _) => {
 181             /* Uniquely accessible path -- OK for `&` and `&mut` */
 182             Ok(())
 183         }
 184         (mc::Aliasability::FreelyAliasable(mc::AliasableStatic), ty::ImmBorrow) => {
 185             // Borrow of an immutable static item.
 186             Ok(())
 187         }
 188         (mc::Aliasability::FreelyAliasable(mc::AliasableStaticMut), _) => {
 189             // Even touching a static mut is considered unsafe. We assume the
 190             // user knows what they're doing in these cases.
 191             Ok(())
 192         }
 193         (mc::Aliasability::ImmutableUnique(_), ty::MutBorrow) => {
 194             bccx.report_aliasability_violation(
 195                         borrow_span,
 196                         loan_cause,
 197                         mc::AliasableReason::UnaliasableImmutable);
 198             Err(())
 199         }
 200         (mc::Aliasability::FreelyAliasable(alias_cause), ty::UniqueImmBorrow) |
 201         (mc::Aliasability::FreelyAliasable(alias_cause), ty::MutBorrow) => {
 202             bccx.report_aliasability_violation(
 203                         borrow_span,
 204                         loan_cause,
 205                         alias_cause);
 206             Err(())
 207         }
 208         (_, _) => {
 209             Ok(())
 210         }
 211     }
 212 }
 213
 214 /// Implements the M-* rules in README.md.
 215 fn check_mutability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
 216                               borrow_span: Span,
 217                               cause: AliasableViolationKind,
 218                               cmt: mc::cmt<'tcx>,
 219                               req_kind: ty::BorrowKind)
 220                               -> Result<(),()> {
 221     debug!("check_mutability(cause={:?} cmt={:?} req_kind={:?}",
 222            cause, cmt, req_kind);
 223     match req_kind {
 224         ty::UniqueImmBorrow | ty::ImmBorrow => {
 225             match cmt.mutbl {
 226                 // I am intentionally leaving this here to help
 227                 // refactoring if, in the future, we should add new
 228                 // kinds of mutability.
 229                 mc::McImmutable | mc::McDeclared | mc::McInherited => {
 230                     // both imm and mut data can be lent as imm;
 231                     // for mutable data, this is a freeze
 232                     Ok(())
 233                 }
 234             }
 235         }
 236
 237         ty::MutBorrow => {
 238             // Only mutable data can be lent as mutable.
 239             if !cmt.mutbl.is_mutable() {
 240                 Err(bccx.report(BckError { span: borrow_span,
 241                                            cause: cause,
 242                                            cmt: cmt,
 243                                            code: err_mutbl }))
 244             } else {
 245                 Ok(())
 246             }
 247         }
 248     }
 249 }
 250
 251 impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
 252     pub fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> { self.bccx.tcx }
 253
 254     /// Guarantees that `cmt` is assignable, or reports an error.
 255     fn guarantee_assignment_valid(&mut self,
 256                                   assignment_id: ast::NodeId,
 257                                   assignment_span: Span,
 258                                   cmt: mc::cmt<'tcx>,
 259                                   mode: euv::MutateMode) {
 260
 261         let opt_lp = opt_loan_path(&cmt);
 262         debug!("guarantee_assignment_valid(assignment_id={}, cmt={:?}) opt_lp={:?}",
 263                assignment_id, cmt, opt_lp);
 264
 265         if let Categorization::Local(..) = cmt.cat {
 266             // Only re-assignments to locals require it to be
 267             // mutable - this is checked in check_loans.
 268         } else {
 269             // Check that we don't allow assignments to non-mutable data.
 270             if check_mutability(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
 276         // Check that we don't allow assignments to aliasable data
 277         if check_aliasability(self.bccx, assignment_span, MutabilityViolation,
 278                               cmt.clone(), ty::MutBorrow).is_err() {
 279             return; // reported an error, no sense in reporting more.
 280         }
 281
 282         match opt_lp {
 283             Some(lp) => {
 284                 if let Categorization::Local(..) = cmt.cat {
 285                     // Only re-assignments to locals require it to be
 286                     // mutable - this is checked in check_loans.
 287                 } else {
 288                     self.mark_loan_path_as_mutated(&lp);
 289                 }
 290                 gather_moves::gather_assignment(self.bccx, &self.move_data,
 291                                                 assignment_id, assignment_span,
 292                                                 lp, cmt.id, mode);
 293             }
 294             None => {
 295                 // This can occur with e.g. `*foo() = 5`.  In such
 296                 // cases, there is no need to check for conflicts
 297                 // with moves etc, just ignore.
 298             }
 299         }
 300     }
 301
 302     /// Guarantees that `addr_of(cmt)` will be valid for the duration of `static_scope_r`, or
 303     /// reports an error.  This may entail taking out loans, which will be added to the
 304     /// `req_loan_map`.
 305     fn guarantee_valid(&mut self,
 306                        borrow_id: ast::NodeId,
 307                        borrow_span: Span,
 308                        cmt: mc::cmt<'tcx>,
 309                        req_kind: ty::BorrowKind,
 310                        loan_region: &'tcx ty::Region,
 311                        cause: euv::LoanCause) {
 312         debug!("guarantee_valid(borrow_id={}, cmt={:?}, \
 313                 req_mutbl={:?}, loan_region={:?})",
 314                borrow_id,
 315                cmt,
 316                req_kind,
 317                loan_region);
 318
 319         // a loan for the empty region can never be dereferenced, so
 320         // it is always safe
 321         if *loan_region == ty::ReEmpty {
 322             return;
 323         }
 324
 325         // Check that the lifetime of the borrow does not exceed
 326         // the lifetime of the data being borrowed.
 327         if lifetime::guarantee_lifetime(self.bccx, self.item_ub,
 328                                         borrow_span, cause, cmt.clone(), loan_region,
 329                                         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 non-mutable data.
 334         if check_mutability(self.bccx, borrow_span, BorrowViolation(cause),
 335                             cmt.clone(), req_kind).is_err() {
 336             return; // reported an error, no sense in reporting more.
 337         }
 338
 339         // Check that we don't allow mutable borrows of aliasable data.
 340         if check_aliasability(self.bccx, borrow_span, BorrowViolation(cause),
 341                               cmt.clone(), req_kind).is_err() {
 342             return; // reported an error, no sense in reporting more.
 343         }
 344
 345         // Compute the restrictions that are required to enforce the
 346         // loan is safe.
 347         let restr = restrictions::compute_restrictions(
 348             self.bccx, borrow_span, cause,
 349             cmt.clone(), loan_region);
 350
 351         debug!("guarantee_valid(): restrictions={:?}", restr);
 352
 353         // Create the loan record (if needed).
 354         let loan = match restr {
 355             RestrictionResult::Safe => {
 356                 // No restrictions---no loan record necessary
 357                 return;
 358             }
 359
 360             RestrictionResult::SafeIf(loan_path, restricted_paths) => {
 361                 let loan_scope = match *loan_region {
 362                     ty::ReScope(scope) => scope,
 363
 364                     ty::ReFree(ref fr) => fr.scope,
 365
 366                     ty::ReStatic => self.item_ub,
 367
 368                     ty::ReEmpty |
 369                     ty::ReLateBound(..) |
 370                     ty::ReEarlyBound(..) |
 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 = self.tcx().region_maps.node_extent(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: loan_path,
 396                     kind: req_kind,
 397                     gen_scope: gen_scope,
 398                     kill_scope: kill_scope,
 399                     span: borrow_span,
 400                     restricted_paths: restricted_paths,
 401                     cause: 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(#6268) 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             //    let all_loans = &mut *self.all_loans; // FIXME(#5074)
 427             //    Loan {
 428             //        index: all_loans.len(),
 429             //        loan_path: loan_path,
 430             //        cmt: cmt,
 431             //        mutbl: ConstMutability,
 432             //        gen_scope: borrow_id,
 433             //        kill_scope: kill_scope,
 434             //        span: borrow_span,
 435             //        restrictions: restrictions
 436             //    }
 437         // }
 438     }
 439
 440     pub fn mark_loan_path_as_mutated(&self, loan_path: &LoanPath) {
 441         //! For mutable loans of content whose mutability derives
 442         //! from a local variable, mark the mutability decl as necessary.
 443
 444         match loan_path.kind {
 445             LpVar(local_id) |
 446             LpUpvar(ty::UpvarId{ var_id: local_id, closure_expr_id: _ }) => {
 447                 self.tcx().used_mut_nodes.borrow_mut().insert(local_id);
 448             }
 449             LpDowncast(ref base, _) |
 450             LpExtend(ref base, mc::McInherited, _) |
 451             LpExtend(ref base, mc::McDeclared, _) => {
 452                 self.mark_loan_path_as_mutated(&base);
 453             }
 454             LpExtend(_, mc::McImmutable, _) => {
 455                 // Nothing to do.
 456             }
 457         }
 458     }
 459
 460     pub fn compute_gen_scope(&self,
 461                              borrow_scope: region::CodeExtent,
 462                              loan_scope: region::CodeExtent)
 463                              -> region::CodeExtent {
 464         //! Determine when to introduce the loan. Typically the loan
 465         //! is introduced at the point of the borrow, but in some cases,
 466         //! notably method arguments, the loan may be introduced only
 467         //! later, once it comes into scope.
 468
 469         if self.bccx.tcx.region_maps.is_subscope_of(borrow_scope, loan_scope) {
 470             borrow_scope
 471         } else {
 472             loan_scope
 473         }
 474     }
 475
 476     pub fn compute_kill_scope(&self, loan_scope: region::CodeExtent, lp: &LoanPath<'tcx>)
 477                               -> region::CodeExtent {
 478         //! Determine when the loan restrictions go out of scope.
 479         //! This is either when the lifetime expires or when the
 480         //! local variable which roots the loan-path goes out of scope,
 481         //! whichever happens faster.
 482         //!
 483         //! It may seem surprising that we might have a loan region
 484         //! larger than the variable which roots the loan-path; this can
 485         //! come about when variables of `&mut` type are re-borrowed,
 486         //! as in this example:
 487         //!
 488         //!     struct Foo { counter: u32 }
 489         //!
 490         //!     fn counter<'a>(v: &'a mut Foo) -> &'a mut u32 {
 491         //!         &mut v.counter
 492         //!     }
 493         //!
 494         //! In this case, the reference (`'a`) outlives the
 495         //! variable `v` that hosts it. Note that this doesn't come up
 496         //! with immutable `&` pointers, because borrows of such pointers
 497         //! do not require restrictions and hence do not cause a loan.
 498
 499         let lexical_scope = lp.kill_scope(self.bccx.tcx);
 500         let rm = &self.bccx.tcx.region_maps;
 501         if rm.is_subscope_of(lexical_scope, loan_scope) {
 502             lexical_scope
 503         } else {
 504             assert!(self.bccx.tcx.region_maps.is_subscope_of(loan_scope, lexical_scope));
 505             loan_scope
 506         }
 507     }
 508
 509     pub fn report_potential_errors(&self) {
 510         self.move_error_collector.report_potential_errors(self.bccx);
 511     }
 512 }
 513
 514 /// Context used while gathering loans on static initializers
 515 ///
 516 /// This visitor walks static initializer's expressions and makes
 517 /// sure the loans being taken are sound.
 518 struct StaticInitializerCtxt<'a, 'tcx: 'a> {
 519     bccx: &'a BorrowckCtxt<'a, 'tcx>,
 520     item_id: ast::NodeId
 521 }
 522
 523 impl<'a, 'tcx, 'v> Visitor<'v> for StaticInitializerCtxt<'a, 'tcx> {
 524     fn visit_expr(&mut self, ex: &Expr) {
 525         if let hir::ExprAddrOf(mutbl, ref base) = ex.node {
 526             let param_env = ty::ParameterEnvironment::for_item(self.bccx.tcx,
 527                                                                self.item_id);
 528             let infcx = self.bccx.tcx.borrowck_fake_infer_ctxt(param_env);
 529             let mc = mc::MemCategorizationContext::new(&infcx);
 530             let base_cmt = mc.cat_expr(&base).unwrap();
 531             let borrow_kind = ty::BorrowKind::from_mutbl(mutbl);
 532             // Check that we don't allow borrows of unsafe static items.
 533             let err = check_aliasability(self.bccx, ex.span,
 534                                          BorrowViolation(euv::AddrOf),
 535                                          base_cmt, borrow_kind).is_err();
 536             if err {
 537                 return; // reported an error, no sense in reporting more.
 538             }
 539         }
 540
 541         intravisit::walk_expr(self, ex);
 542     }
 543 }
 544
 545 pub fn gather_loans_in_static_initializer(bccx: &mut BorrowckCtxt,
 546                                           item_id: ast::NodeId,
 547                                           expr: &hir::Expr) {
 548
 549     debug!("gather_loans_in_static_initializer(expr={:?})", expr);
 550
 551     let mut sicx = StaticInitializerCtxt {
 552         bccx: bccx,
 553         item_id: item_id
 554     };
 555
 556     sicx.visit_expr(expr);
 557 }