src/librustc/middle/region.rs

   1 // Copyright 2012 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
  13 This file actually contains two passes related to regions.  The first
  14 pass builds up the `scope_map`, which describes the parent links in
  15 the region hierarchy.  The second pass infers which types must be
  16 region parameterized.
  17
  18 Most of the documentation on regions can be found in
  19 `middle/typeck/infer/region_inference.rs`
  20
  21 */
  22
  23
  24 use driver::session::Session;
  25 use middle::ty::{FreeRegion};
  26 use middle::ty;
  27 use util::nodemap::NodeMap;
  28
  29 use std::cell::RefCell;
  30 use collections::{HashMap, HashSet};
  31 use syntax::codemap::Span;
  32 use syntax::{ast, visit};
  33 use syntax::visit::{Visitor, FnKind};
  34 use syntax::ast::{Block, Item, FnDecl, NodeId, Arm, Pat, Stmt, Expr, Local};
  35 use syntax::ast_util::{stmt_id};
  36
  37 /**
  38 The region maps encode information about region relationships.
  39
  40 - `scope_map` maps from a scope id to the enclosing scope id; this is
  41   usually corresponding to the lexical nesting, though in the case of
  42   closures the parent scope is the innermost conditinal expression or repeating
  43   block
  44
  45 - `var_map` maps from a variable or binding id to the block in which
  46   that variable is declared.
  47
  48 - `free_region_map` maps from a free region `a` to a list of free
  49   regions `bs` such that `a <= b for all b in bs`
  50   - the free region map is populated during type check as we check
  51     each function. See the function `relate_free_regions` for
  52     more information.
  53
  54 - `rvalue_scopes` includes entries for those expressions whose cleanup
  55   scope is larger than the default. The map goes from the expression
  56   id to the cleanup scope id. For rvalues not present in this table,
  57   the appropriate cleanup scope is the innermost enclosing statement,
  58   conditional expression, or repeating block (see `terminating_scopes`).
  59
  60 - `terminating_scopes` is a set containing the ids of each statement,
  61   or conditional/repeating expression. These scopes are calling "terminating
  62   scopes" because, when attempting to find the scope of a temporary, by
  63   default we search up the enclosing scopes until we encounter the
  64   terminating scope. A conditional/repeating
  65   expression is one which is not guaranteed to execute exactly once
  66   upon entering the parent scope. This could be because the expression
  67   only executes conditionally, such as the expression `b` in `a && b`,
  68   or because the expression may execute many times, such as a loop
  69   body. The reason that we distinguish such expressions is that, upon
  70   exiting the parent scope, we cannot statically know how many times
  71   the expression executed, and thus if the expression creates
  72   temporaries we cannot know statically how many such temporaries we
  73   would have to cleanup. Therefore we ensure that the temporaries never
  74   outlast the conditional/repeating expression, preventing the need
  75   for dynamic checks and/or arbitrary amounts of stack space.
  76 */
  77 pub struct RegionMaps {
  78     scope_map: RefCell<NodeMap<ast::NodeId>>,
  79     var_map: RefCell<NodeMap<ast::NodeId>>,
  80     free_region_map: RefCell<HashMap<FreeRegion, Vec<FreeRegion> >>,
  81     rvalue_scopes: RefCell<NodeMap<ast::NodeId>>,
  82     terminating_scopes: RefCell<HashSet<ast::NodeId>>,
  83 }
  84
  85 #[deriving(Clone)]
  86 pub struct Context {
  87     var_parent: Option<ast::NodeId>,
  88
  89     // Innermost enclosing expression
  90     parent: Option<ast::NodeId>,
  91 }
  92
  93 struct RegionResolutionVisitor<'a> {
  94     sess: &'a Session,
  95
  96     // Generated maps:
  97     region_maps: &'a RegionMaps,
  98 }
  99
 100
 101 impl RegionMaps {
 102     pub fn relate_free_regions(&self, sub: FreeRegion, sup: FreeRegion) {
 103         match self.free_region_map.borrow_mut().find_mut(&sub) {
 104             Some(sups) => {
 105                 if !sups.iter().any(|x| x == &sup) {
 106                     sups.push(sup);
 107                 }
 108                 return;
 109             }
 110             None => {}
 111         }
 112
 113         debug!("relate_free_regions(sub={:?}, sup={:?})", sub, sup);
 114         self.free_region_map.borrow_mut().insert(sub, vec!(sup));
 115     }
 116
 117     pub fn record_encl_scope(&self, sub: ast::NodeId, sup: ast::NodeId) {
 118         debug!("record_encl_scope(sub={}, sup={})", sub, sup);
 119         assert!(sub != sup);
 120         self.scope_map.borrow_mut().insert(sub, sup);
 121     }
 122
 123     pub fn record_var_scope(&self, var: ast::NodeId, lifetime: ast::NodeId) {
 124         debug!("record_var_scope(sub={}, sup={})", var, lifetime);
 125         assert!(var != lifetime);
 126         self.var_map.borrow_mut().insert(var, lifetime);
 127     }
 128
 129     pub fn record_rvalue_scope(&self, var: ast::NodeId, lifetime: ast::NodeId) {
 130         debug!("record_rvalue_scope(sub={}, sup={})", var, lifetime);
 131         assert!(var != lifetime);
 132         self.rvalue_scopes.borrow_mut().insert(var, lifetime);
 133     }
 134
 135     pub fn mark_as_terminating_scope(&self, scope_id: ast::NodeId) {
 136         /*!
 137          * Records that a scope is a TERMINATING SCOPE. Whenever we
 138          * create automatic temporaries -- e.g. by an
 139          * expression like `a().f` -- they will be freed within
 140          * the innermost terminating scope.
 141          */
 142
 143         debug!("record_terminating_scope(scope_id={})", scope_id);
 144         self.terminating_scopes.borrow_mut().insert(scope_id);
 145     }
 146
 147     pub fn opt_encl_scope(&self, id: ast::NodeId) -> Option<ast::NodeId> {
 148         //! Returns the narrowest scope that encloses `id`, if any.
 149         self.scope_map.borrow().find(&id).map(|x| *x)
 150     }
 151
 152     #[allow(dead_code)] // used in middle::cfg
 153     pub fn encl_scope(&self, id: ast::NodeId) -> ast::NodeId {
 154         //! Returns the narrowest scope that encloses `id`, if any.
 155         match self.scope_map.borrow().find(&id) {
 156             Some(&r) => r,
 157             None => { fail!("no enclosing scope for id {}", id); }
 158         }
 159     }
 160
 161     pub fn var_scope(&self, var_id: ast::NodeId) -> ast::NodeId {
 162         /*!
 163          * Returns the lifetime of the local variable `var_id`
 164          */
 165         match self.var_map.borrow().find(&var_id) {
 166             Some(&r) => r,
 167             None => { fail!("no enclosing scope for id {}", var_id); }
 168         }
 169     }
 170
 171     pub fn temporary_scope(&self, expr_id: ast::NodeId) -> Option<ast::NodeId> {
 172         //! Returns the scope when temp created by expr_id will be cleaned up
 173
 174         // check for a designated rvalue scope
 175         match self.rvalue_scopes.borrow().find(&expr_id) {
 176             Some(&s) => {
 177                 debug!("temporary_scope({}) = {} [custom]", expr_id, s);
 178                 return Some(s);
 179             }
 180             None => { }
 181         }
 182
 183         // else, locate the innermost terminating scope
 184         // if there's one. Static items, for instance, won't
 185         // have an enclosing scope, hence no scope will be
 186         // returned.
 187         let mut id = match self.opt_encl_scope(expr_id) {
 188             Some(i) => i,
 189             None => { return None; }
 190         };
 191
 192         while !self.terminating_scopes.borrow().contains(&id) {
 193             match self.opt_encl_scope(id) {
 194                 Some(p) => {
 195                     id = p;
 196                 }
 197                 None => {
 198                     debug!("temporary_scope({}) = None", expr_id);
 199                     return None;
 200                 }
 201             }
 202         }
 203         debug!("temporary_scope({}) = {} [enclosing]", expr_id, id);
 204         return Some(id);
 205     }
 206
 207     pub fn var_region(&self, id: ast::NodeId) -> ty::Region {
 208         //! Returns the lifetime of the variable `id`.
 209
 210         ty::ReScope(self.var_scope(id))
 211     }
 212
 213     pub fn scopes_intersect(&self, scope1: ast::NodeId, scope2: ast::NodeId)
 214                             -> bool {
 215         self.is_subscope_of(scope1, scope2) ||
 216         self.is_subscope_of(scope2, scope1)
 217     }
 218
 219     pub fn is_subscope_of(&self,
 220                           subscope: ast::NodeId,
 221                           superscope: ast::NodeId)
 222                           -> bool {
 223         /*!
 224          * Returns true if `subscope` is equal to or is lexically
 225          * nested inside `superscope` and false otherwise.
 226          */
 227
 228         let mut s = subscope;
 229         while superscope != s {
 230             match self.scope_map.borrow().find(&s) {
 231                 None => {
 232                     debug!("is_subscope_of({}, {}, s={})=false",
 233                            subscope, superscope, s);
 234
 235                     return false;
 236                 }
 237                 Some(&scope) => s = scope
 238             }
 239         }
 240
 241         debug!("is_subscope_of({}, {})=true",
 242                subscope, superscope);
 243
 244         return true;
 245     }
 246
 247     pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
 248         /*!
 249          * Determines whether two free regions have a subregion relationship
 250          * by walking the graph encoded in `free_region_map`.  Note that
 251          * it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
 252          * (that is, the user can give two different names to the same lifetime).
 253          */
 254
 255         if sub == sup {
 256             return true;
 257         }
 258
 259         // Do a little breadth-first-search here.  The `queue` list
 260         // doubles as a way to detect if we've seen a particular FR
 261         // before.  Note that we expect this graph to be an *extremely
 262         // shallow* tree.
 263         let mut queue = vec!(sub);
 264         let mut i = 0;
 265         while i < queue.len() {
 266             match self.free_region_map.borrow().find(queue.get(i)) {
 267                 Some(parents) => {
 268                     for parent in parents.iter() {
 269                         if *parent == sup {
 270                             return true;
 271                         }
 272
 273                         if !queue.iter().any(|x| x == parent) {
 274                             queue.push(*parent);
 275                         }
 276                     }
 277                 }
 278                 None => {}
 279             }
 280             i += 1;
 281         }
 282         return false;
 283     }
 284
 285     pub fn is_subregion_of(&self,
 286                            sub_region: ty::Region,
 287                            super_region: ty::Region)
 288                            -> bool {
 289         /*!
 290          * Determines whether one region is a subregion of another.  This is
 291          * intended to run *after inference* and sadly the logic is somewhat
 292          * duplicated with the code in infer.rs.
 293          */
 294
 295         debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
 296                sub_region, super_region);
 297
 298         sub_region == super_region || {
 299             match (sub_region, super_region) {
 300                 (_, ty::ReStatic) => {
 301                     true
 302                 }
 303
 304                 (ty::ReScope(sub_scope), ty::ReScope(super_scope)) => {
 305                     self.is_subscope_of(sub_scope, super_scope)
 306                 }
 307
 308                 (ty::ReScope(sub_scope), ty::ReFree(ref fr)) => {
 309                     self.is_subscope_of(sub_scope, fr.scope_id)
 310                 }
 311
 312                 (ty::ReFree(sub_fr), ty::ReFree(super_fr)) => {
 313                     self.sub_free_region(sub_fr, super_fr)
 314                 }
 315
 316                 _ => {
 317                     false
 318                 }
 319             }
 320         }
 321     }
 322
 323     pub fn nearest_common_ancestor(&self,
 324                                    scope_a: ast::NodeId,
 325                                    scope_b: ast::NodeId)
 326                                    -> Option<ast::NodeId> {
 327         /*!
 328          * Finds the nearest common ancestor (if any) of two scopes.  That
 329          * is, finds the smallest scope which is greater than or equal to
 330          * both `scope_a` and `scope_b`.
 331          */
 332
 333         if scope_a == scope_b { return Some(scope_a); }
 334
 335         let a_ancestors = ancestors_of(self, scope_a);
 336         let b_ancestors = ancestors_of(self, scope_b);
 337         let mut a_index = a_ancestors.len() - 1u;
 338         let mut b_index = b_ancestors.len() - 1u;
 339
 340         // Here, ~[ab]_ancestors is a vector going from narrow to broad.
 341         // The end of each vector will be the item where the scope is
 342         // defined; if there are any common ancestors, then the tails of
 343         // the vector will be the same.  So basically we want to walk
 344         // backwards from the tail of each vector and find the first point
 345         // where they diverge.  If one vector is a suffix of the other,
 346         // then the corresponding scope is a superscope of the other.
 347
 348         if *a_ancestors.get(a_index) != *b_ancestors.get(b_index) {
 349             return None;
 350         }
 351
 352         loop {
 353             // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
 354             // for all indices between a_index and the end of the array
 355             if a_index == 0u { return Some(scope_a); }
 356             if b_index == 0u { return Some(scope_b); }
 357             a_index -= 1u;
 358             b_index -= 1u;
 359             if *a_ancestors.get(a_index) != *b_ancestors.get(b_index) {
 360                 return Some(*a_ancestors.get(a_index + 1u));
 361             }
 362         }
 363
 364         fn ancestors_of(this: &RegionMaps, scope: ast::NodeId)
 365             -> Vec<ast::NodeId> {
 366             // debug!("ancestors_of(scope={})", scope);
 367             let mut result = vec!(scope);
 368             let mut scope = scope;
 369             loop {
 370                 match this.scope_map.borrow().find(&scope) {
 371                     None => return result,
 372                     Some(&superscope) => {
 373                         result.push(superscope);
 374                         scope = superscope;
 375                     }
 376                 }
 377                 // debug!("ancestors_of_loop(scope={})", scope);
 378             }
 379         }
 380     }
 381 }
 382
 383 /// Records the current parent (if any) as the parent of `child_id`.
 384 fn record_superlifetime(visitor: &mut RegionResolutionVisitor,
 385                         cx: Context,
 386                         child_id: ast::NodeId,
 387                         _sp: Span) {
 388     for &parent_id in cx.parent.iter() {
 389         visitor.region_maps.record_encl_scope(child_id, parent_id);
 390     }
 391 }
 392
 393 /// Records the lifetime of a local variable as `cx.var_parent`
 394 fn record_var_lifetime(visitor: &mut RegionResolutionVisitor,
 395                        cx: Context,
 396                        var_id: ast::NodeId,
 397                        _sp: Span) {
 398     match cx.var_parent {
 399         Some(parent_id) => {
 400             visitor.region_maps.record_var_scope(var_id, parent_id);
 401         }
 402         None => {
 403             // this can happen in extern fn declarations like
 404             //
 405             // extern fn isalnum(c: c_int) -> c_int
 406         }
 407     }
 408 }
 409
 410 fn resolve_block(visitor: &mut RegionResolutionVisitor,
 411                  blk: &ast::Block,
 412                  cx: Context) {
 413     debug!("resolve_block(blk.id={})", blk.id);
 414
 415     // Record the parent of this block.
 416     record_superlifetime(visitor, cx, blk.id, blk.span);
 417
 418     // We treat the tail expression in the block (if any) somewhat
 419     // differently from the statements. The issue has to do with
 420     // temporary lifetimes. If the user writes:
 421     //
 422     //   {
 423     //     ... (&foo()) ...
 424     //   }
 425     //
 426
 427     let subcx = Context {var_parent: Some(blk.id), parent: Some(blk.id)};
 428     visit::walk_block(visitor, blk, subcx);
 429 }
 430
 431 fn resolve_arm(visitor: &mut RegionResolutionVisitor,
 432                arm: &ast::Arm,
 433                cx: Context) {
 434     visitor.region_maps.mark_as_terminating_scope(arm.body.id);
 435
 436     match arm.guard {
 437         Some(expr) => {
 438             visitor.region_maps.mark_as_terminating_scope(expr.id);
 439         }
 440         None => { }
 441     }
 442
 443     visit::walk_arm(visitor, arm, cx);
 444 }
 445
 446 fn resolve_pat(visitor: &mut RegionResolutionVisitor,
 447                pat: &ast::Pat,
 448                cx: Context) {
 449     record_superlifetime(visitor, cx, pat.id, pat.span);
 450
 451     // If this is a binding (or maybe a binding, I'm too lazy to check
 452     // the def map) then record the lifetime of that binding.
 453     match pat.node {
 454         ast::PatIdent(..) => {
 455             record_var_lifetime(visitor, cx, pat.id, pat.span);
 456         }
 457         _ => { }
 458     }
 459
 460     visit::walk_pat(visitor, pat, cx);
 461 }
 462
 463 fn resolve_stmt(visitor: &mut RegionResolutionVisitor,
 464                 stmt: &ast::Stmt,
 465                 cx: Context) {
 466     let stmt_id = stmt_id(stmt);
 467     debug!("resolve_stmt(stmt.id={})", stmt_id);
 468
 469     visitor.region_maps.mark_as_terminating_scope(stmt_id);
 470     record_superlifetime(visitor, cx, stmt_id, stmt.span);
 471
 472     let subcx = Context {parent: Some(stmt_id), ..cx};
 473     visit::walk_stmt(visitor, stmt, subcx);
 474 }
 475
 476 fn resolve_expr(visitor: &mut RegionResolutionVisitor,
 477                 expr: &ast::Expr,
 478                 cx: Context) {
 479     debug!("resolve_expr(expr.id={})", expr.id);
 480
 481     record_superlifetime(visitor, cx, expr.id, expr.span);
 482
 483     let mut new_cx = cx;
 484     new_cx.parent = Some(expr.id);
 485     match expr.node {
 486         // Conditional or repeating scopes are always terminating
 487         // scopes, meaning that temporaries cannot outlive them.
 488         // This ensures fixed size stacks.
 489
 490         ast::ExprBinary(ast::BiAnd, _, r) |
 491         ast::ExprBinary(ast::BiOr, _, r) => {
 492             // For shortcircuiting operators, mark the RHS as a terminating
 493             // scope since it only executes conditionally.
 494             visitor.region_maps.mark_as_terminating_scope(r.id);
 495         }
 496
 497         ast::ExprIf(_, then, Some(otherwise)) => {
 498             visitor.region_maps.mark_as_terminating_scope(then.id);
 499             visitor.region_maps.mark_as_terminating_scope(otherwise.id);
 500         }
 501
 502         ast::ExprIf(expr, then, None) => {
 503             visitor.region_maps.mark_as_terminating_scope(expr.id);
 504             visitor.region_maps.mark_as_terminating_scope(then.id);
 505         }
 506
 507         ast::ExprLoop(body, _) => {
 508             visitor.region_maps.mark_as_terminating_scope(body.id);
 509         }
 510
 511         ast::ExprWhile(expr, body) => {
 512             visitor.region_maps.mark_as_terminating_scope(expr.id);
 513             visitor.region_maps.mark_as_terminating_scope(body.id);
 514         }
 515
 516         ast::ExprMatch(..) => {
 517             new_cx.var_parent = Some(expr.id);
 518         }
 519
 520         ast::ExprAssignOp(..) | ast::ExprIndex(..) |
 521         ast::ExprUnary(..) | ast::ExprCall(..) | ast::ExprMethodCall(..) => {
 522             // FIXME(#6268) Nested method calls
 523             //
 524             // The lifetimes for a call or method call look as follows:
 525             //
 526             // call.id
 527             // - arg0.id
 528             // - ...
 529             // - argN.id
 530             // - call.callee_id
 531             //
 532             // The idea is that call.callee_id represents *the time when
 533             // the invoked function is actually running* and call.id
 534             // represents *the time to prepare the arguments and make the
 535             // call*.  See the section "Borrows in Calls" borrowck/doc.rs
 536             // for an extended explanation of why this distinction is
 537             // important.
 538             //
 539             // record_superlifetime(new_cx, expr.callee_id);
 540         }
 541
 542         _ => {}
 543     };
 544
 545
 546     visit::walk_expr(visitor, expr, new_cx);
 547 }
 548
 549 fn resolve_local(visitor: &mut RegionResolutionVisitor,
 550                  local: &ast::Local,
 551                  cx: Context) {
 552     debug!("resolve_local(local.id={},local.init={})",
 553            local.id,local.init.is_some());
 554
 555     let blk_id = match cx.var_parent {
 556         Some(id) => id,
 557         None => {
 558             visitor.sess.span_bug(
 559                 local.span,
 560                 "local without enclosing block");
 561         }
 562     };
 563
 564     // For convenience in trans, associate with the local-id the var
 565     // scope that will be used for any bindings declared in this
 566     // pattern.
 567     visitor.region_maps.record_var_scope(local.id, blk_id);
 568
 569     // As an exception to the normal rules governing temporary
 570     // lifetimes, initializers in a let have a temporary lifetime
 571     // of the enclosing block. This means that e.g. a program
 572     // like the following is legal:
 573     //
 574     //     let ref x = HashMap::new();
 575     //
 576     // Because the hash map will be freed in the enclosing block.
 577     //
 578     // We express the rules more formally based on 3 grammars (defined
 579     // fully in the helpers below that implement them):
 580     //
 581     // 1. `E&`, which matches expressions like `&<rvalue>` that
 582     //    own a pointer into the stack.
 583     //
 584     // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref
 585     //    y)` that produce ref bindings into the value they are
 586     //    matched against or something (at least partially) owned by
 587     //    the value they are matched against. (By partially owned,
 588     //    I mean that creating a binding into a ref-counted or managed value
 589     //    would still count.)
 590     //
 591     // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues
 592     //    based on rvalues like `foo().x[2].y`.
 593     //
 594     // A subexpression `<rvalue>` that appears in a let initializer
 595     // `let pat [: ty] = expr` has an extended temporary lifetime if
 596     // any of the following conditions are met:
 597     //
 598     // A. `pat` matches `P&` and `expr` matches `ET`
 599     //    (covers cases where `pat` creates ref bindings into an rvalue
 600     //     produced by `expr`)
 601     // B. `ty` is a borrowed pointer and `expr` matches `ET`
 602     //    (covers cases where coercion creates a borrow)
 603     // C. `expr` matches `E&`
 604     //    (covers cases `expr` borrows an rvalue that is then assigned
 605     //     to memory (at least partially) owned by the binding)
 606     //
 607     // Here are some examples hopefully giving an intuition where each
 608     // rule comes into play and why:
 609     //
 610     // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)`
 611     // would have an extended lifetime, but not `foo()`.
 612     //
 613     // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]`
 614     // would have an extended lifetime, but not `foo()`.
 615     //
 616     // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended
 617     // lifetime.
 618     //
 619     // In some cases, multiple rules may apply (though not to the same
 620     // rvalue). For example:
 621     //
 622     //     let ref x = [&a(), &b()];
 623     //
 624     // Here, the expression `[...]` has an extended lifetime due to rule
 625     // A, but the inner rvalues `a()` and `b()` have an extended lifetime
 626     // due to rule C.
 627     //
 628     // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST.
 629
 630     match local.init {
 631         Some(expr) => {
 632             record_rvalue_scope_if_borrow_expr(visitor, expr, blk_id);
 633
 634             if is_binding_pat(local.pat) || is_borrowed_ty(local.ty) {
 635                 record_rvalue_scope(visitor, expr, blk_id);
 636             }
 637         }
 638
 639         None => { }
 640     }
 641
 642     visit::walk_local(visitor, local, cx);
 643
 644     fn is_binding_pat(pat: &ast::Pat) -> bool {
 645         /*!
 646          * True if `pat` match the `P&` nonterminal:
 647          *
 648          *     P& = ref X
 649          *        | StructName { ..., P&, ... }
 650          *        | VariantName(..., P&, ...)
 651          *        | [ ..., P&, ... ]
 652          *        | ( ..., P&, ... )
 653          *        | ~P&
 654          *        | box P&
 655          */
 656
 657         match pat.node {
 658             ast::PatIdent(ast::BindByRef(_), _, _) => true,
 659
 660             ast::PatStruct(_, ref field_pats, _) => {
 661                 field_pats.iter().any(|fp| is_binding_pat(fp.pat))
 662             }
 663
 664             ast::PatVec(ref pats1, ref pats2, ref pats3) => {
 665                 pats1.iter().any(|&p| is_binding_pat(p)) ||
 666                 pats2.iter().any(|&p| is_binding_pat(p)) ||
 667                 pats3.iter().any(|&p| is_binding_pat(p))
 668             }
 669
 670             ast::PatEnum(_, Some(ref subpats)) |
 671             ast::PatTup(ref subpats) => {
 672                 subpats.iter().any(|&p| is_binding_pat(p))
 673             }
 674
 675             ast::PatUniq(subpat) => {
 676                 is_binding_pat(subpat)
 677             }
 678
 679             _ => false,
 680         }
 681     }
 682
 683     fn is_borrowed_ty(ty: &ast::Ty) -> bool {
 684         /*!
 685          * True if `ty` is a borrowed pointer type
 686          * like `&int` or `&[...]`.
 687          */
 688
 689         match ty.node {
 690             ast::TyRptr(..) => true,
 691             _ => false
 692         }
 693     }
 694
 695     fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor,
 696                                           expr: &ast::Expr,
 697                                           blk_id: ast::NodeId) {
 698         /*!
 699          * If `expr` matches the `E&` grammar, then records an extended
 700          * rvalue scope as appropriate:
 701          *
 702          *     E& = & ET
 703          *        | StructName { ..., f: E&, ... }
 704          *        | [ ..., E&, ... ]
 705          *        | ( ..., E&, ... )
 706          *        | {...; E&}
 707          *        | ~E&
 708          *        | E& as ...
 709          *        | ( E& )
 710          */
 711
 712         match expr.node {
 713             ast::ExprAddrOf(_, subexpr) => {
 714                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 715                 record_rvalue_scope(visitor, subexpr, blk_id);
 716             }
 717             ast::ExprStruct(_, ref fields, _) => {
 718                 for field in fields.iter() {
 719                     record_rvalue_scope_if_borrow_expr(
 720                         visitor, field.expr, blk_id);
 721                 }
 722             }
 723             ast::ExprVstore(subexpr, _) => {
 724                 visitor.region_maps.record_rvalue_scope(subexpr.id, blk_id);
 725                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 726             }
 727             ast::ExprVec(ref subexprs) |
 728             ast::ExprTup(ref subexprs) => {
 729                 for &subexpr in subexprs.iter() {
 730                     record_rvalue_scope_if_borrow_expr(
 731                         visitor, subexpr, blk_id);
 732                 }
 733             }
 734             ast::ExprUnary(ast::UnUniq, subexpr) => {
 735                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 736             }
 737             ast::ExprCast(subexpr, _) |
 738             ast::ExprParen(subexpr) => {
 739                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id)
 740             }
 741             ast::ExprBlock(ref block) => {
 742                 match block.expr {
 743                     Some(subexpr) => {
 744                         record_rvalue_scope_if_borrow_expr(
 745                             visitor, subexpr, blk_id);
 746                     }
 747                     None => { }
 748                 }
 749             }
 750             _ => {
 751             }
 752         }
 753     }
 754
 755     fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor,
 756                                expr: &'a ast::Expr,
 757                                blk_id: ast::NodeId) {
 758         /*!
 759          * Applied to an expression `expr` if `expr` -- or something
 760          * owned or partially owned by `expr` -- is going to be
 761          * indirectly referenced by a variable in a let statement. In
 762          * that case, the "temporary lifetime" or `expr` is extended
 763          * to be the block enclosing the `let` statement.
 764          *
 765          * More formally, if `expr` matches the grammar `ET`, record
 766          * the rvalue scope of the matching `<rvalue>` as `blk_id`:
 767          *
 768          *     ET = *ET
 769          *        | ET[...]
 770          *        | ET.f
 771          *        | (ET)
 772          *        | <rvalue>
 773          *
 774          * Note: ET is intended to match "rvalues or
 775          * lvalues based on rvalues".
 776          */
 777
 778         let mut expr = expr;
 779         loop {
 780             // Note: give all the expressions matching `ET` with the
 781             // extended temporary lifetime, not just the innermost rvalue,
 782             // because in trans if we must compile e.g. `*rvalue()`
 783             // into a temporary, we request the temporary scope of the
 784             // outer expression.
 785             visitor.region_maps.record_rvalue_scope(expr.id, blk_id);
 786
 787             match expr.node {
 788                 ast::ExprAddrOf(_, ref subexpr) |
 789                 ast::ExprUnary(ast::UnDeref, ref subexpr) |
 790                 ast::ExprField(ref subexpr, _, _) |
 791                 ast::ExprIndex(ref subexpr, _) |
 792                 ast::ExprParen(ref subexpr) => {
 793                     let subexpr: &'a @Expr = subexpr; // FIXME(#11586)
 794                     expr = &**subexpr;
 795                 }
 796                 _ => {
 797                     return;
 798                 }
 799             }
 800         }
 801     }
 802 }
 803
 804 fn resolve_item(visitor: &mut RegionResolutionVisitor,
 805                 item: &ast::Item,
 806                 cx: Context) {
 807     // Items create a new outer block scope as far as we're concerned.
 808     let new_cx = Context {var_parent: None, parent: None, ..cx};
 809     visit::walk_item(visitor, item, new_cx);
 810 }
 811
 812 fn resolve_fn(visitor: &mut RegionResolutionVisitor,
 813               fk: &FnKind,
 814               decl: &ast::FnDecl,
 815               body: &ast::Block,
 816               sp: Span,
 817               id: ast::NodeId,
 818               cx: Context) {
 819     debug!("region::resolve_fn(id={}, \
 820                                span={:?}, \
 821                                body.id={}, \
 822                                cx.parent={})",
 823            id,
 824            visitor.sess.codemap().span_to_str(sp),
 825            body.id,
 826            cx.parent);
 827
 828     visitor.region_maps.mark_as_terminating_scope(body.id);
 829
 830     // The arguments and `self` are parented to the body of the fn.
 831     let decl_cx = Context {parent: Some(body.id),
 832                            var_parent: Some(body.id)};
 833     visit::walk_fn_decl(visitor, decl, decl_cx);
 834
 835     // The body of the fn itself is either a root scope (top-level fn)
 836     // or it continues with the inherited scope (closures).
 837     let body_cx = match *fk {
 838         visit::FkItemFn(..) | visit::FkMethod(..) => {
 839             Context {parent: None, var_parent: None, ..cx}
 840         }
 841         visit::FkFnBlock(..) => {
 842             // FIXME(#3696) -- at present we are place the closure body
 843             // within the region hierarchy exactly where it appears lexically.
 844             // This is wrong because the closure may live longer
 845             // than the enclosing expression. We should probably fix this,
 846             // but the correct fix is a bit subtle, and I am also not sure
 847             // that the present approach is unsound -- it may not permit
 848             // any illegal programs. See issue for more details.
 849             cx
 850         }
 851     };
 852     visitor.visit_block(body, body_cx);
 853 }
 854
 855 impl<'a> Visitor<Context> for RegionResolutionVisitor<'a> {
 856
 857     fn visit_block(&mut self, b: &Block, cx: Context) {
 858         resolve_block(self, b, cx);
 859     }
 860
 861     fn visit_item(&mut self, i: &Item, cx: Context) {
 862         resolve_item(self, i, cx);
 863     }
 864
 865     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
 866                 b: &Block, s: Span, n: NodeId, cx: Context) {
 867         resolve_fn(self, fk, fd, b, s, n, cx);
 868     }
 869     fn visit_arm(&mut self, a: &Arm, cx: Context) {
 870         resolve_arm(self, a, cx);
 871     }
 872     fn visit_pat(&mut self, p: &Pat, cx: Context) {
 873         resolve_pat(self, p, cx);
 874     }
 875     fn visit_stmt(&mut self, s: &Stmt, cx: Context) {
 876         resolve_stmt(self, s, cx);
 877     }
 878     fn visit_expr(&mut self, ex: &Expr, cx: Context) {
 879         resolve_expr(self, ex, cx);
 880     }
 881     fn visit_local(&mut self, l: &Local, cx: Context) {
 882         resolve_local(self, l, cx);
 883     }
 884 }
 885
 886 pub fn resolve_crate(sess: &Session, krate: &ast::Crate) -> RegionMaps {
 887     let maps = RegionMaps {
 888         scope_map: RefCell::new(NodeMap::new()),
 889         var_map: RefCell::new(NodeMap::new()),
 890         free_region_map: RefCell::new(HashMap::new()),
 891         rvalue_scopes: RefCell::new(NodeMap::new()),
 892         terminating_scopes: RefCell::new(HashSet::new()),
 893     };
 894     {
 895         let mut visitor = RegionResolutionVisitor {
 896             sess: sess,
 897             region_maps: &maps
 898         };
 899         let cx = Context { parent: None, var_parent: None };
 900         visit::walk_crate(&mut visitor, krate, cx);
 901     }
 902     return maps;
 903 }
 904
 905 pub fn resolve_inlined_item(sess: &Session,
 906                             region_maps: &RegionMaps,
 907                             item: &ast::InlinedItem) {
 908     let cx = Context {parent: None,
 909                       var_parent: None};
 910     let mut visitor = RegionResolutionVisitor {
 911         sess: sess,
 912         region_maps: region_maps,
 913     };
 914     visit::walk_inlined_item(&mut visitor, item, cx);
 915 }
 916