src/librustc/middle/borrowck/gather_loans/mod.rs

   1 // Copyright 2012-2013 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 middle::borrowck::*;
  20 use middle::borrowck::move_data::MoveData;
  21 use mc = middle::mem_categorization;
  22 use middle::moves;
  23 use middle::pat_util;
  24 use middle::ty::{ty_region};
  25 use middle::ty;
  26 use middle::typeck::MethodCall;
  27 use util::common::indenter;
  28 use util::ppaux::{Repr};
  29
  30 use syntax::ast;
  31 use syntax::ast_util;
  32 use syntax::ast_util::IdRange;
  33 use syntax::codemap::Span;
  34 use syntax::print::pprust;
  35 use syntax::visit;
  36 use syntax::visit::{Visitor, FnKind};
  37 use syntax::ast::{Expr, FnDecl, Block, NodeId, Stmt, Pat, Local};
  38
  39 mod lifetime;
  40 mod restrictions;
  41 mod gather_moves;
  42
  43 /// Context used while gathering loans:
  44 ///
  45 /// - `bccx`: the borrow check context
  46 /// - `item_ub`: the id of the block for the enclosing fn/method item
  47 /// - `root_ub`: the id of the outermost block for which we can root
  48 ///   an `@T`.  This is the id of the innermost enclosing
  49 ///   loop or function body.
  50 ///
  51 /// The role of `root_ub` is to prevent us from having to accumulate
  52 /// vectors of rooted items at runtime.  Consider this case:
  53 ///
  54 ///     fn foo(...) -> int {
  55 ///         let mut ptr: &int;
  56 ///         while some_cond {
  57 ///             let x: @int = ...;
  58 ///             ptr = &*x;
  59 ///         }
  60 ///         *ptr
  61 ///     }
  62 ///
  63 /// If we are not careful here, we would infer the scope of the borrow `&*x`
  64 /// to be the body of the function `foo()` as a whole.  We would then
  65 /// have root each `@int` that is produced, which is an unbounded number.
  66 /// No good.  Instead what will happen is that `root_ub` will be set to the
  67 /// body of the while loop and we will refuse to root the pointer `&*x`
  68 /// because it would have to be rooted for a region greater than `root_ub`.
  69 struct GatherLoanCtxt<'a> {
  70     bccx: &'a BorrowckCtxt<'a>,
  71     id_range: IdRange,
  72     move_data: move_data::MoveData,
  73     all_loans: Vec<Loan>,
  74     item_ub: ast::NodeId,
  75     repeating_ids: Vec<ast::NodeId> }
  76
  77 impl<'a> visit::Visitor<()> for GatherLoanCtxt<'a> {
  78     fn visit_expr(&mut self, ex: &Expr, _: ()) {
  79         gather_loans_in_expr(self, ex);
  80     }
  81     fn visit_block(&mut self, b: &Block, _: ()) {
  82         gather_loans_in_block(self, b);
  83     }
  84
  85     /// Do not visit closures or fn items here, the outer loop in
  86     /// borrowck/mod will visit them for us in turn.
  87     fn visit_fn(&mut self, _: &FnKind, _: &FnDecl, _: &Block,
  88                 _: Span, _: NodeId, _: ()) {}
  89
  90     fn visit_stmt(&mut self, s: &Stmt, _: ()) {
  91         visit::walk_stmt(self, s, ());
  92     }
  93     fn visit_pat(&mut self, p: &Pat, _: ()) {
  94         add_pat_to_id_range(self, p);
  95     }
  96     fn visit_local(&mut self, l: &Local, _: ()) {
  97         gather_loans_in_local(self, l);
  98     }
  99
 100     // #7740: Do not visit items here, not even fn items nor methods
 101     // of impl items; the outer loop in borrowck/mod will visit them
 102     // for us in turn.  Thus override visit_item's walk with a no-op.
 103     fn visit_item(&mut self, _: &ast::Item, _: ()) {}
 104 }
 105
 106 fn add_pat_to_id_range(this: &mut GatherLoanCtxt,
 107                        p: &ast::Pat) {
 108     // NB: This visitor function just adds the pat ids into the id
 109     // range. We gather loans that occur in patterns using the
 110     // `gather_pat()` method below. Eventually these two should be
 111     // brought together.
 112     this.id_range.add(p.id);
 113     visit::walk_pat(this, p, ());
 114 }
 115
 116 pub fn gather_loans_in_fn(bccx: &BorrowckCtxt, decl: &ast::FnDecl, body: &ast::Block)
 117                     -> (IdRange, Vec<Loan>, move_data::MoveData) {
 118     let mut glcx = GatherLoanCtxt {
 119         bccx: bccx,
 120         id_range: IdRange::max(),
 121         all_loans: Vec::new(),
 122         item_ub: body.id,
 123         repeating_ids: vec!(body.id),
 124         move_data: MoveData::new()
 125     };
 126     glcx.gather_fn_arg_patterns(decl, body);
 127
 128     glcx.visit_block(body, ());
 129     let GatherLoanCtxt { id_range, all_loans, move_data, .. } = glcx;
 130     (id_range, all_loans, move_data)
 131 }
 132
 133 fn gather_loans_in_block(this: &mut GatherLoanCtxt,
 134                          blk: &ast::Block) {
 135     this.id_range.add(blk.id);
 136     visit::walk_block(this, blk, ());
 137 }
 138
 139 fn gather_loans_in_local(this: &mut GatherLoanCtxt,
 140                          local: &ast::Local) {
 141     match local.init {
 142         None => {
 143             // Variable declarations without initializers are considered "moves":
 144             let tcx = this.bccx.tcx;
 145             pat_util::pat_bindings(tcx.def_map, local.pat, |_, id, span, _| {
 146                 gather_moves::gather_decl(this.bccx,
 147                                           &this.move_data,
 148                                           id,
 149                                           span,
 150                                           id);
 151             })
 152         }
 153         Some(init) => {
 154             // Variable declarations with initializers are considered "assigns",
 155             // which is handled by `gather_pat`:
 156             let init_cmt = this.bccx.cat_expr(init);
 157             this.gather_pat(init_cmt, local.pat, None);
 158         }
 159     }
 160
 161     visit::walk_local(this, local, ());
 162 }
 163
 164 pub fn gather_loans_in_static_initializer(bccx: &mut BorrowckCtxt, expr: &ast::Expr) {
 165
 166     debug!("gather_loans_in_item(expr={})", expr.repr(bccx.tcx));
 167
 168     let mut glcx = GatherLoanCtxt {
 169         bccx: bccx,
 170         id_range: IdRange::max(),
 171         all_loans: Vec::new(),
 172         item_ub: expr.id,
 173         repeating_ids: vec!(expr.id),
 174         move_data: MoveData::new()
 175     };
 176
 177     // FIXME #13005 This should also walk the
 178     // expression.
 179     match expr.node {
 180         ast::ExprAddrOf(..) => {
 181             glcx.visit_expr(expr, ());
 182         }
 183         _ => {}
 184     }
 185 }
 186
 187 fn gather_loans_in_expr(this: &mut GatherLoanCtxt,
 188                         ex: &ast::Expr) {
 189     let bccx = this.bccx;
 190     let tcx = bccx.tcx;
 191
 192     debug!("gather_loans_in_expr(expr={:?}/{})",
 193            ex.id, pprust::expr_to_str(ex));
 194
 195     this.id_range.add(ex.id);
 196
 197     // If this expression is borrowed, have to ensure it remains valid:
 198     for &adjustments in tcx.adjustments.borrow().find(&ex.id).iter() {
 199         this.guarantee_adjustments(ex, *adjustments);
 200     }
 201
 202     // If this expression is a move, gather it:
 203     if this.bccx.is_move(ex.id) {
 204         let cmt = this.bccx.cat_expr(ex);
 205         gather_moves::gather_move_from_expr(
 206             this.bccx, &this.move_data, ex, cmt);
 207     }
 208
 209     // Special checks for various kinds of expressions:
 210     let method_map = this.bccx.method_map.borrow();
 211     match ex.node {
 212       ast::ExprAddrOf(mutbl, base) => {
 213         let base_cmt = this.bccx.cat_expr(base);
 214
 215         // make sure that the thing we are pointing out stays valid
 216         // for the lifetime `scope_r` of the resulting ptr:
 217         let expr_ty = ty::expr_ty(tcx, ex);
 218         if !ty::type_is_bot(expr_ty) {
 219             let scope_r = ty_region(tcx, ex.span, expr_ty);
 220             this.guarantee_valid(ex.id,
 221                                  ex.span,
 222                                  base_cmt,
 223                                  mutbl,
 224                                  scope_r,
 225                                  AddrOf);
 226         }
 227         visit::walk_expr(this, ex, ());
 228       }
 229
 230       ast::ExprAssign(l, _) => {
 231           with_assignee_loan_path(
 232               this.bccx, l,
 233               |lp| gather_moves::gather_assignment(this.bccx, &this.move_data,
 234                                                    ex.id, ex.span, lp, l.id));
 235           visit::walk_expr(this, ex, ());
 236       }
 237
 238       ast::ExprAssignOp(_, l, _) => {
 239           with_assignee_loan_path(
 240               this.bccx, l,
 241               |lp| gather_moves::gather_move_and_assignment(this.bccx, &this.move_data,
 242                                                             ex.id, ex.span, lp, l.id));
 243           visit::walk_expr(this, ex, ());
 244       }
 245
 246       ast::ExprMatch(ex_v, ref arms) => {
 247         let cmt = this.bccx.cat_expr(ex_v);
 248         for arm in arms.iter() {
 249             for pat in arm.pats.iter() {
 250                 this.gather_pat(cmt, *pat, Some((arm.body.id, ex.id)));
 251             }
 252         }
 253         visit::walk_expr(this, ex, ());
 254       }
 255
 256       ast::ExprIndex(_, arg) |
 257       ast::ExprBinary(_, _, arg)
 258       if method_map.contains_key(&MethodCall::expr(ex.id)) => {
 259           // Arguments in method calls are always passed by ref.
 260           //
 261           // Currently these do not use adjustments, so we have to
 262           // hardcode this check here (note that the receiver DOES use
 263           // adjustments).
 264           let scope_r = ty::ReScope(ex.id);
 265           let arg_cmt = this.bccx.cat_expr(arg);
 266           this.guarantee_valid(arg.id,
 267                                arg.span,
 268                                arg_cmt,
 269                                ast::MutImmutable,
 270                                scope_r,
 271                                AutoRef);
 272           visit::walk_expr(this, ex, ());
 273       }
 274
 275       // see explanation attached to the `root_ub` field:
 276       ast::ExprWhile(cond, body) => {
 277           // during the condition, can only root for the condition
 278           this.push_repeating_id(cond.id);
 279           this.visit_expr(cond, ());
 280           this.pop_repeating_id(cond.id);
 281
 282           // during body, can only root for the body
 283           this.push_repeating_id(body.id);
 284           this.visit_block(body, ());
 285           this.pop_repeating_id(body.id);
 286       }
 287
 288       // see explanation attached to the `root_ub` field:
 289       ast::ExprLoop(body, _) => {
 290           this.push_repeating_id(body.id);
 291           visit::walk_expr(this, ex, ());
 292           this.pop_repeating_id(body.id);
 293       }
 294
 295       ast::ExprFnBlock(..) | ast::ExprProc(..) => {
 296           gather_moves::gather_captures(this.bccx, &this.move_data, ex);
 297           this.guarantee_captures(ex);
 298           visit::walk_expr(this, ex, ());
 299       }
 300
 301       ast::ExprInlineAsm(ref ia) => {
 302           for &(_, out) in ia.outputs.iter() {
 303               with_assignee_loan_path(
 304                   this.bccx, out,
 305                   |lp| gather_moves::gather_assignment(this.bccx, &this.move_data,
 306                                                        ex.id, ex.span, lp, out.id));
 307           }
 308           visit::walk_expr(this, ex, ());
 309       }
 310
 311       _ => {
 312           visit::walk_expr(this, ex, ());
 313       }
 314     }
 315 }
 316
 317 fn with_assignee_loan_path(bccx: &BorrowckCtxt, expr: &ast::Expr, op: |@LoanPath|) {
 318     let cmt = bccx.cat_expr(expr);
 319     match opt_loan_path(cmt) {
 320         Some(lp) => op(lp),
 321         None => {
 322             // This can occur with e.g. `*foo() = 5`.  In such
 323             // cases, there is no need to check for conflicts
 324             // with moves etc, just ignore.
 325         }
 326     }
 327 }
 328
 329 impl<'a> GatherLoanCtxt<'a> {
 330     pub fn tcx(&self) -> &'a ty::ctxt { self.bccx.tcx }
 331
 332     pub fn push_repeating_id(&mut self, id: ast::NodeId) {
 333         self.repeating_ids.push(id);
 334     }
 335
 336     pub fn pop_repeating_id(&mut self, id: ast::NodeId) {
 337         let popped = self.repeating_ids.pop().unwrap();
 338         assert_eq!(id, popped);
 339     }
 340
 341     pub fn guarantee_autoderefs(&mut self,
 342                                 expr: &ast::Expr,
 343                                 autoderefs: uint) {
 344         let method_map = self.bccx.method_map.borrow();
 345         for i in range(0, autoderefs) {
 346             match method_map.find(&MethodCall::autoderef(expr.id, i as u32)) {
 347                 Some(method) => {
 348                     // Treat overloaded autoderefs as if an AutoRef adjustment
 349                     // was applied on the base type, as that is always the case.
 350                     let mut mc = self.bccx.mc();
 351                     let cmt = match mc.cat_expr_autoderefd(expr, i) {
 352                         Ok(v) => v,
 353                         Err(()) => self.tcx().sess.span_bug(expr.span, "Err from mc")
 354                     };
 355                     let self_ty = *ty::ty_fn_args(method.ty).get(0);
 356                     let (m, r) = match ty::get(self_ty).sty {
 357                         ty::ty_rptr(r, ref m) => (m.mutbl, r),
 358                         _ => self.tcx().sess.span_bug(expr.span,
 359                                 format!("bad overloaded deref type {}",
 360                                     method.ty.repr(self.tcx())))
 361                     };
 362                     self.guarantee_valid(expr.id,
 363                                          expr.span,
 364                                          cmt,
 365                                          m,
 366                                          r,
 367                                          AutoRef);
 368                 }
 369                 None => {}
 370             }
 371         }
 372     }
 373
 374     pub fn guarantee_adjustments(&mut self,
 375                                  expr: &ast::Expr,
 376                                  adjustment: &ty::AutoAdjustment) {
 377         debug!("guarantee_adjustments(expr={}, adjustment={:?})",
 378                expr.repr(self.tcx()), adjustment);
 379         let _i = indenter();
 380
 381         match *adjustment {
 382             ty::AutoAddEnv(..) => {
 383                 debug!("autoaddenv -- no autoref");
 384                 return;
 385             }
 386
 387             ty::AutoDerefRef(
 388                 ty::AutoDerefRef {
 389                     autoref: None, autoderefs }) => {
 390                 debug!("no autoref");
 391                 self.guarantee_autoderefs(expr, autoderefs);
 392                 return;
 393             }
 394
 395             ty::AutoDerefRef(
 396                 ty::AutoDerefRef {
 397                     autoref: Some(ref autoref),
 398                     autoderefs}) => {
 399                 self.guarantee_autoderefs(expr, autoderefs);
 400                 let mut mc = self.bccx.mc();
 401                 let cmt = match mc.cat_expr_autoderefd(expr, autoderefs) {
 402                     Ok(v) => v,
 403                     Err(()) => self.tcx().sess.span_bug(expr.span, "Err from mc")
 404                 };
 405                 debug!("after autoderef, cmt={}", cmt.repr(self.tcx()));
 406
 407                 match *autoref {
 408                     ty::AutoPtr(r, m) => {
 409                         self.guarantee_valid(expr.id,
 410                                              expr.span,
 411                                              cmt,
 412                                              m,
 413                                              r,
 414                                              AutoRef)
 415                     }
 416                     ty::AutoBorrowVec(r, m) | ty::AutoBorrowVecRef(r, m) => {
 417                         let cmt_index = mc.cat_index(expr, cmt, autoderefs+1);
 418                         self.guarantee_valid(expr.id,
 419                                              expr.span,
 420                                              cmt_index,
 421                                              m,
 422                                              r,
 423                                              AutoRef)
 424                     }
 425                     ty::AutoBorrowFn(r) => {
 426                         let cmt_deref = mc.cat_deref_fn_or_obj(expr, cmt, 0);
 427                         self.guarantee_valid(expr.id,
 428                                              expr.span,
 429                                              cmt_deref,
 430                                              ast::MutImmutable,
 431                                              r,
 432                                              AutoRef)
 433                     }
 434                     ty::AutoBorrowObj(r, m) => {
 435                         let cmt_deref = mc.cat_deref_fn_or_obj(expr, cmt, 0);
 436                         self.guarantee_valid(expr.id,
 437                                              expr.span,
 438                                              cmt_deref,
 439                                              m,
 440                                              r,
 441                                              AutoRef)
 442                     }
 443                     ty::AutoUnsafe(_) => {}
 444                 }
 445             }
 446
 447             ty::AutoObject(..) => {
 448                 // FIXME: Handle ~Trait to &Trait casts here?
 449             }
 450         }
 451     }
 452
 453     fn guarantee_captures(&mut self,
 454                           closure_expr: &ast::Expr) {
 455         for captured_var in self.bccx.capture_map.get(&closure_expr.id).iter() {
 456             match captured_var.mode {
 457                 moves::CapCopy | moves::CapMove => { continue; }
 458                 moves::CapRef => { }
 459             }
 460
 461             let var_id = ast_util::def_id_of_def(captured_var.def).node;
 462             let var_cmt = self.bccx.cat_captured_var(closure_expr.id,
 463                                                      closure_expr.span,
 464                                                      captured_var);
 465
 466             // Lookup the kind of borrow the callee requires
 467             let upvar_id = ty::UpvarId { var_id: var_id,
 468                                          closure_expr_id: closure_expr.id };
 469             let upvar_borrow = self.tcx().upvar_borrow_map.borrow()
 470                                    .get_copy(&upvar_id);
 471
 472             self.guarantee_valid_kind(closure_expr.id,
 473                                       closure_expr.span,
 474                                       var_cmt,
 475                                       upvar_borrow.kind,
 476                                       upvar_borrow.region,
 477                                       ClosureCapture(captured_var.span));
 478         }
 479     }
 480
 481     pub fn guarantee_valid(&mut self,
 482                            borrow_id: ast::NodeId,
 483                            borrow_span: Span,
 484                            cmt: mc::cmt,
 485                            req_mutbl: ast::Mutability,
 486                            loan_region: ty::Region,
 487                            cause: LoanCause) {
 488         self.guarantee_valid_kind(borrow_id,
 489                                   borrow_span,
 490                                   cmt,
 491                                   ty::BorrowKind::from_mutbl(req_mutbl),
 492                                   loan_region,
 493                                   cause);
 494     }
 495
 496     fn guarantee_valid_kind(&mut self,
 497                             borrow_id: ast::NodeId,
 498                             borrow_span: Span,
 499                             cmt: mc::cmt,
 500                             req_kind: ty::BorrowKind,
 501                             loan_region: ty::Region,
 502                             cause: LoanCause) {
 503         /*!
 504          * Guarantees that `addr_of(cmt)` will be valid for the duration of
 505          * `static_scope_r`, or reports an error.  This may entail taking
 506          * out loans, which will be added to the `req_loan_map`.  This can
 507          * also entail "rooting" GC'd pointers, which means ensuring
 508          * dynamically that they are not freed.
 509          */
 510
 511         debug!("guarantee_valid(borrow_id={:?}, cmt={}, \
 512                 req_mutbl={:?}, loan_region={:?})",
 513                borrow_id,
 514                cmt.repr(self.tcx()),
 515                req_kind,
 516                loan_region);
 517
 518         // a loan for the empty region can never be dereferenced, so
 519         // it is always safe
 520         if loan_region == ty::ReEmpty {
 521             return;
 522         }
 523
 524         let root_ub = { *self.repeating_ids.last().unwrap() }; // FIXME(#5074)
 525
 526         // Check that the lifetime of the borrow does not exceed
 527         // the lifetime of the data being borrowed.
 528         if lifetime::guarantee_lifetime(self.bccx, self.item_ub, root_ub,
 529                                         borrow_span, cause, cmt, loan_region,
 530                                         req_kind).is_err() {
 531             return; // reported an error, no sense in reporting more.
 532         }
 533
 534         // Check that we don't allow mutable borrows of non-mutable data.
 535         if check_mutability(self.bccx, borrow_span, cause,
 536                             cmt, req_kind).is_err() {
 537             return; // reported an error, no sense in reporting more.
 538         }
 539
 540         // Check that we don't allow mutable borrows of aliasable data.
 541         if check_aliasability(self.bccx, borrow_span, cause,
 542                               cmt, req_kind).is_err() {
 543             return; // reported an error, no sense in reporting more.
 544         }
 545
 546         // Compute the restrictions that are required to enforce the
 547         // loan is safe.
 548         let restr = restrictions::compute_restrictions(
 549             self.bccx, borrow_span, cause,
 550             cmt, loan_region, self.restriction_set(req_kind));
 551
 552         // Create the loan record (if needed).
 553         let loan = match restr {
 554             restrictions::Safe => {
 555                 // No restrictions---no loan record necessary
 556                 return;
 557             }
 558
 559             restrictions::SafeIf(loan_path, restrictions) => {
 560                 let loan_scope = match loan_region {
 561                     ty::ReScope(id) => id,
 562                     ty::ReFree(ref fr) => fr.scope_id,
 563
 564                     ty::ReStatic => {
 565                         // If we get here, an error must have been
 566                         // reported in
 567                         // `lifetime::guarantee_lifetime()`, because
 568                         // the only legal ways to have a borrow with a
 569                         // static lifetime should not require
 570                         // restrictions. To avoid reporting derived
 571                         // errors, we just return here without adding
 572                         // any loans.
 573                         return;
 574                     }
 575
 576                     ty::ReEmpty |
 577                     ty::ReLateBound(..) |
 578                     ty::ReEarlyBound(..) |
 579                     ty::ReInfer(..) => {
 580                         self.tcx().sess.span_bug(
 581                             cmt.span,
 582                             format!("invalid borrow lifetime: {:?}", loan_region));
 583                     }
 584                 };
 585                 debug!("loan_scope = {:?}", loan_scope);
 586
 587                 let gen_scope = self.compute_gen_scope(borrow_id, loan_scope);
 588                 debug!("gen_scope = {:?}", gen_scope);
 589
 590                 let kill_scope = self.compute_kill_scope(loan_scope, loan_path);
 591                 debug!("kill_scope = {:?}", kill_scope);
 592
 593                 if req_kind == ty::MutBorrow {
 594                     self.mark_loan_path_as_mutated(loan_path);
 595                 }
 596
 597                 Loan {
 598                     index: self.all_loans.len(),
 599                     loan_path: loan_path,
 600                     cmt: cmt,
 601                     kind: req_kind,
 602                     gen_scope: gen_scope,
 603                     kill_scope: kill_scope,
 604                     span: borrow_span,
 605                     restrictions: restrictions,
 606                     cause: cause,
 607                 }
 608             }
 609         };
 610
 611         debug!("guarantee_valid(borrow_id={:?}), loan={}",
 612                borrow_id, loan.repr(self.tcx()));
 613
 614         // let loan_path = loan.loan_path;
 615         // let loan_gen_scope = loan.gen_scope;
 616         // let loan_kill_scope = loan.kill_scope;
 617         self.all_loans.push(loan);
 618
 619         // if loan_gen_scope != borrow_id {
 620             // FIXME(#6268) Nested method calls
 621             //
 622             // Typically, the scope of the loan includes the point at
 623             // which the loan is originated. This
 624             // This is a subtle case. See the test case
 625             // <compile-fail/borrowck-bad-nested-calls-free.rs>
 626             // to see what we are guarding against.
 627
 628             //let restr = restrictions::compute_restrictions(
 629             //    self.bccx, borrow_span, cmt, RESTR_EMPTY);
 630             //let loan = {
 631             //    let all_loans = &mut *self.all_loans; // FIXME(#5074)
 632             //    Loan {
 633             //        index: all_loans.len(),
 634             //        loan_path: loan_path,
 635             //        cmt: cmt,
 636             //        mutbl: ConstMutability,
 637             //        gen_scope: borrow_id,
 638             //        kill_scope: kill_scope,
 639             //        span: borrow_span,
 640             //        restrictions: restrictions
 641             //    }
 642         // }
 643
 644         fn check_mutability(bccx: &BorrowckCtxt,
 645                             borrow_span: Span,
 646                             cause: LoanCause,
 647                             cmt: mc::cmt,
 648                             req_kind: ty::BorrowKind)
 649                             -> Result<(),()> {
 650             //! Implements the M-* rules in doc.rs.
 651
 652             match req_kind {
 653                 ty::UniqueImmBorrow | ty::ImmBorrow => {
 654                     match cmt.mutbl {
 655                         // I am intentionally leaving this here to help
 656                         // refactoring if, in the future, we should add new
 657                         // kinds of mutability.
 658                         mc::McImmutable | mc::McDeclared | mc::McInherited => {
 659                             // both imm and mut data can be lent as imm;
 660                             // for mutable data, this is a freeze
 661                             Ok(())
 662                         }
 663                     }
 664                 }
 665
 666                 ty::MutBorrow => {
 667                     // Only mutable data can be lent as mutable.
 668                     if !cmt.mutbl.is_mutable() {
 669                         Err(bccx.report(BckError { span: borrow_span,
 670                                                    cause: cause,
 671                                                    cmt: cmt,
 672                                                    code: err_mutbl }))
 673                     } else {
 674                         Ok(())
 675                     }
 676                 }
 677             }
 678         }
 679
 680         fn check_aliasability(bccx: &BorrowckCtxt,
 681                               borrow_span: Span,
 682                               loan_cause: LoanCause,
 683                               cmt: mc::cmt,
 684                               req_kind: ty::BorrowKind)
 685                               -> Result<(),()> {
 686             //! Implements the A-* rules in doc.rs.
 687
 688             match (cmt.freely_aliasable(bccx.tcx), req_kind) {
 689                 (None, _) => {
 690                     /* Uniquely accessible path -- OK for `&` and `&mut` */
 691                     Ok(())
 692                 }
 693                 (Some(mc::AliasableStatic(safety)), ty::ImmBorrow) => {
 694                     // Borrow of an immutable static item:
 695                     match safety {
 696                         mc::InteriorUnsafe => {
 697                             // If the static item contains an Unsafe<T>, it has interior mutability.
 698                             // In such cases, we cannot permit it to be borrowed, because the
 699                             // static item resides in immutable memory and mutating it would
 700                             // cause segfaults.
 701                             bccx.tcx.sess.span_err(borrow_span,
 702                                                    format!("borrow of immutable static items with \
 703                                                             unsafe interior is not allowed"));
 704                             Err(())
 705                         }
 706                         mc::InteriorSafe => {
 707                             // Immutable static can be borrowed, no problem.
 708                             Ok(())
 709                         }
 710                     }
 711                 }
 712                 (Some(mc::AliasableStaticMut(..)), _) => {
 713                     // Even touching a static mut is considered unsafe. We assume the
 714                     // user knows what they're doing in these cases.
 715                     Ok(())
 716                 }
 717                 (Some(alias_cause), ty::UniqueImmBorrow) |
 718                 (Some(alias_cause), ty::MutBorrow) => {
 719                     bccx.report_aliasability_violation(
 720                                 borrow_span,
 721                                 BorrowViolation(loan_cause),
 722                                 alias_cause);
 723                     Err(())
 724                 }
 725                 (_, _) => {
 726                     Ok(())
 727                 }
 728             }
 729         }
 730     }
 731
 732     fn restriction_set(&self, req_kind: ty::BorrowKind) -> RestrictionSet {
 733         match req_kind {
 734             // If borrowing data as immutable, no mutation allowed:
 735             ty::ImmBorrow => RESTR_MUTATE,
 736
 737             // If borrowing data as mutable, no mutation nor other
 738             // borrows allowed:
 739             ty::MutBorrow => RESTR_MUTATE | RESTR_FREEZE,
 740
 741             // If borrowing data as unique imm, no mutation nor other
 742             // borrows allowed:
 743             ty::UniqueImmBorrow => RESTR_MUTATE | RESTR_FREEZE,
 744         }
 745     }
 746
 747     pub fn mark_loan_path_as_mutated(&self, loan_path: @LoanPath) {
 748         //! For mutable loans of content whose mutability derives
 749         //! from a local variable, mark the mutability decl as necessary.
 750
 751         match *loan_path {
 752             LpVar(local_id) => {
 753                 self.tcx().used_mut_nodes.borrow_mut().insert(local_id);
 754             }
 755             LpExtend(base, mc::McInherited, _) => {
 756                 self.mark_loan_path_as_mutated(base);
 757             }
 758             LpExtend(_, mc::McDeclared, _) |
 759             LpExtend(_, mc::McImmutable, _) => {
 760                 // Nothing to do.
 761             }
 762         }
 763     }
 764
 765     pub fn compute_gen_scope(&self,
 766                              borrow_id: ast::NodeId,
 767                              loan_scope: ast::NodeId)
 768                              -> ast::NodeId {
 769         //! Determine when to introduce the loan. Typically the loan
 770         //! is introduced at the point of the borrow, but in some cases,
 771         //! notably method arguments, the loan may be introduced only
 772         //! later, once it comes into scope.
 773
 774         if self.bccx.tcx.region_maps.is_subscope_of(borrow_id, loan_scope) {
 775             borrow_id
 776         } else {
 777             loan_scope
 778         }
 779     }
 780
 781     pub fn compute_kill_scope(&self, loan_scope: ast::NodeId, lp: @LoanPath)
 782                               -> ast::NodeId {
 783         //! Determine when the loan restrictions go out of scope.
 784         //! This is either when the lifetime expires or when the
 785         //! local variable which roots the loan-path goes out of scope,
 786         //! whichever happens faster.
 787         //!
 788         //! It may seem surprising that we might have a loan region
 789         //! larger than the variable which roots the loan-path; this can
 790         //! come about when variables of `&mut` type are re-borrowed,
 791         //! as in this example:
 792         //!
 793         //!     fn counter<'a>(v: &'a mut Foo) -> &'a mut uint {
 794         //!         &mut v.counter
 795         //!     }
 796         //!
 797         //! In this case, the reference (`'a`) outlives the
 798         //! variable `v` that hosts it. Note that this doesn't come up
 799         //! with immutable `&` pointers, because borrows of such pointers
 800         //! do not require restrictions and hence do not cause a loan.
 801
 802         let rm = &self.bccx.tcx.region_maps;
 803         let lexical_scope = rm.var_scope(lp.node_id());
 804         if rm.is_subscope_of(lexical_scope, loan_scope) {
 805             lexical_scope
 806         } else {
 807             assert!(self.bccx.tcx.region_maps.is_subscope_of(loan_scope, lexical_scope));
 808             loan_scope
 809         }
 810     }
 811
 812     fn gather_fn_arg_patterns(&mut self,
 813                               decl: &ast::FnDecl,
 814                               body: &ast::Block) {
 815         /*!
 816          * Walks the patterns for fn arguments, checking that they
 817          * do not attempt illegal moves or create refs that outlive
 818          * the arguments themselves. Just a shallow wrapper around
 819          * `gather_pat()`.
 820          */
 821
 822         let mut mc = self.bccx.mc();
 823         for arg in decl.inputs.iter() {
 824             let arg_ty = ty::node_id_to_type(self.tcx(), arg.pat.id);
 825
 826             let arg_cmt = mc.cat_rvalue(
 827                 arg.id,
 828                 arg.pat.span,
 829                 ty::ReScope(body.id), // Args live only as long as the fn body.
 830                 arg_ty);
 831
 832             self.gather_pat(arg_cmt, arg.pat, None);
 833         }
 834     }
 835
 836     fn gather_pat(&mut self,
 837                   discr_cmt: mc::cmt,
 838                   root_pat: @ast::Pat,
 839                   arm_match_ids: Option<(ast::NodeId, ast::NodeId)>) {
 840         /*!
 841          * Walks patterns, examining the bindings to determine if they
 842          * cause borrows (`ref` bindings, vector patterns) or
 843          * moves (non-`ref` bindings with linear type).
 844          */
 845
 846         self.bccx.cat_pattern(discr_cmt, root_pat, |cmt, pat| {
 847             match pat.node {
 848               ast::PatIdent(bm, _, _) if self.pat_is_binding(pat) => {
 849                 // Each match binding is effectively an assignment.
 850                 let tcx = self.bccx.tcx;
 851                 pat_util::pat_bindings(tcx.def_map, pat, |_, id, span, _| {
 852                     gather_moves::gather_assignment(self.bccx,
 853                                                     &self.move_data,
 854                                                     id,
 855                                                     span,
 856                                                     @LpVar(id),
 857                                                     id);
 858                 });
 859
 860                 match bm {
 861                   ast::BindByRef(mutbl) => {
 862                     // ref x or ref x @ p --- creates a ptr which must
 863                     // remain valid for the scope of the match
 864
 865                     // find the region of the resulting pointer (note that
 866                     // the type of such a pattern will *always* be a
 867                     // region pointer)
 868                     let scope_r =
 869                         ty_region(self.tcx(), pat.span,
 870                                   ty::node_id_to_type(self.tcx(), pat.id));
 871
 872                     // if the scope of the region ptr turns out to be
 873                     // specific to this arm, wrap the categorization
 874                     // with a cat_discr() node.  There is a detailed
 875                     // discussion of the function of this node in
 876                     // `lifetime.rs`:
 877                     let cmt_discr = match arm_match_ids {
 878                         None => cmt,
 879                         Some((arm_id, match_id)) => {
 880                             let arm_scope = ty::ReScope(arm_id);
 881                             if self.bccx.is_subregion_of(scope_r, arm_scope) {
 882                                 self.bccx.cat_discr(cmt, match_id)
 883                             } else {
 884                                 cmt
 885                             }
 886                         }
 887                     };
 888                     self.guarantee_valid(pat.id,
 889                                          pat.span,
 890                                          cmt_discr,
 891                                          mutbl,
 892                                          scope_r,
 893                                          RefBinding);
 894                   }
 895                   ast::BindByValue(_) => {
 896                       // No borrows here, but there may be moves
 897                       if self.bccx.is_move(pat.id) {
 898                           gather_moves::gather_move_from_pat(
 899                               self.bccx, &self.move_data, pat, cmt);
 900                       }
 901                   }
 902                 }
 903               }
 904
 905               ast::PatVec(_, Some(slice_pat), _) => {
 906                   // The `slice_pat` here creates a slice into the
 907                   // original vector.  This is effectively a borrow of
 908                   // the elements of the vector being matched.
 909
 910                   let (slice_cmt, slice_borrow_kind, slice_r) = {
 911                       match self.bccx.mc().cat_slice_pattern(cmt, slice_pat) {
 912                           Ok(v) => v,
 913                           Err(()) => {
 914                               self.tcx().sess.span_bug(slice_pat.span,
 915                                                        "Err from mc")
 916                           }
 917                       }
 918                   };
 919
 920                   // Note: We declare here that the borrow occurs upon
 921                   // entering the `[...]` pattern. This implies that
 922                   // something like `[a, ..b]` where `a` is a move is
 923                   // illegal, because the borrow is already in effect.
 924                   // In fact such a move would be safe-ish, but it
 925                   // effectively *requires* that we use the nulling
 926                   // out semantics to indicate when a value has been
 927                   // moved, which we are trying to move away from.
 928                   // Otherwise, how can we indicate that the first
 929                   // element in the vector has been moved?
 930                   // Eventually, we could perhaps modify this rule to
 931                   // permit `[..a, b]` where `b` is a move, because in
 932                   // that case we can adjust the length of the
 933                   // original vec accordingly, but we'd have to make
 934                   // trans do the right thing, and it would only work
 935                   // for `~` vectors. It seems simpler to just require
 936                   // that people call `vec.pop()` or `vec.unshift()`.
 937                   self.guarantee_valid(pat.id, pat.span,
 938                                        slice_cmt, slice_borrow_kind, slice_r,
 939                                        RefBinding);
 940               }
 941
 942               _ => {}
 943             }
 944         })
 945     }
 946
 947     pub fn pat_is_binding(&self, pat: &ast::Pat) -> bool {
 948         pat_util::pat_is_binding(self.bccx.tcx.def_map, pat)
 949     }
 950 }