src/librustc/middle/region.rs

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