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