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