src/librustc_borrowck/borrowck/gather_loans/mod.rs

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