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