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