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, Vec<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: &'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         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, vec!(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 = vec!(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.get(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.get(a_index) != *b_ancestors.get(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.get(a_index) != *b_ancestors.get(b_index) {
 384                 return Some(*a_ancestors.get(a_index + 1u));
 385             }
 386         }
 387
 388         fn ancestors_of(this: &RegionMaps, scope: ast::NodeId)
 389             -> Vec<ast::NodeId> {
 390             // debug!("ancestors_of(scope={})", scope);
 391             let mut result = vec!(scope);
 392             let mut scope = scope;
 393             loop {
 394                 let scope_map = this.scope_map.borrow();
 395                 match scope_map.get().find(&scope) {
 396                     None => return result,
 397                     Some(&superscope) => {
 398                         result.push(superscope);
 399                         scope = superscope;
 400                     }
 401                 }
 402                 // debug!("ancestors_of_loop(scope={})", scope);
 403             }
 404         }
 405     }
 406 }
 407
 408 /// Records the current parent (if any) as the parent of `child_id`.
 409 fn record_superlifetime(visitor: &mut RegionResolutionVisitor,
 410                         cx: Context,
 411                         child_id: ast::NodeId,
 412                         _sp: Span) {
 413     for &parent_id in cx.parent.iter() {
 414         visitor.region_maps.record_encl_scope(child_id, parent_id);
 415     }
 416 }
 417
 418 /// Records the lifetime of a local variable as `cx.var_parent`
 419 fn record_var_lifetime(visitor: &mut RegionResolutionVisitor,
 420                        cx: Context,
 421                        var_id: ast::NodeId,
 422                        _sp: Span) {
 423     match cx.var_parent {
 424         Some(parent_id) => {
 425             visitor.region_maps.record_var_scope(var_id, parent_id);
 426         }
 427         None => {
 428             // this can happen in extern fn declarations like
 429             //
 430             // extern fn isalnum(c: c_int) -> c_int
 431         }
 432     }
 433 }
 434
 435 fn resolve_block(visitor: &mut RegionResolutionVisitor,
 436                  blk: &ast::Block,
 437                  cx: Context) {
 438     debug!("resolve_block(blk.id={})", blk.id);
 439
 440     // Record the parent of this block.
 441     record_superlifetime(visitor, cx, blk.id, blk.span);
 442
 443     // We treat the tail expression in the block (if any) somewhat
 444     // differently from the statements. The issue has to do with
 445     // temporary lifetimes. If the user writes:
 446     //
 447     //   {
 448     //     ... (&foo()) ...
 449     //   }
 450     //
 451
 452     let subcx = Context {var_parent: Some(blk.id), parent: Some(blk.id)};
 453     visit::walk_block(visitor, blk, subcx);
 454 }
 455
 456 fn resolve_arm(visitor: &mut RegionResolutionVisitor,
 457                arm: &ast::Arm,
 458                cx: Context) {
 459     visitor.region_maps.mark_as_terminating_scope(arm.body.id);
 460
 461     match arm.guard {
 462         Some(expr) => {
 463             visitor.region_maps.mark_as_terminating_scope(expr.id);
 464         }
 465         None => { }
 466     }
 467
 468     visit::walk_arm(visitor, arm, cx);
 469 }
 470
 471 fn resolve_pat(visitor: &mut RegionResolutionVisitor,
 472                pat: &ast::Pat,
 473                cx: Context) {
 474     record_superlifetime(visitor, cx, pat.id, pat.span);
 475
 476     // If this is a binding (or maybe a binding, I'm too lazy to check
 477     // the def map) then record the lifetime of that binding.
 478     match pat.node {
 479         ast::PatIdent(..) => {
 480             record_var_lifetime(visitor, cx, pat.id, pat.span);
 481         }
 482         _ => { }
 483     }
 484
 485     visit::walk_pat(visitor, pat, cx);
 486 }
 487
 488 fn resolve_stmt(visitor: &mut RegionResolutionVisitor,
 489                 stmt: &ast::Stmt,
 490                 cx: Context) {
 491     let stmt_id = stmt_id(stmt);
 492     debug!("resolve_stmt(stmt.id={})", stmt_id);
 493
 494     visitor.region_maps.mark_as_terminating_scope(stmt_id);
 495     record_superlifetime(visitor, cx, stmt_id, stmt.span);
 496
 497     let subcx = Context {parent: Some(stmt_id), ..cx};
 498     visit::walk_stmt(visitor, stmt, subcx);
 499 }
 500
 501 fn resolve_expr(visitor: &mut RegionResolutionVisitor,
 502                 expr: &ast::Expr,
 503                 cx: Context) {
 504     debug!("resolve_expr(expr.id={})", expr.id);
 505
 506     record_superlifetime(visitor, cx, expr.id, expr.span);
 507
 508     let mut new_cx = cx;
 509     new_cx.parent = Some(expr.id);
 510     match expr.node {
 511         // Conditional or repeating scopes are always terminating
 512         // scopes, meaning that temporaries cannot outlive them.
 513         // This ensures fixed size stacks.
 514
 515         ast::ExprBinary(ast::BiAnd, _, r) |
 516         ast::ExprBinary(ast::BiOr, _, r) => {
 517             // For shortcircuiting operators, mark the RHS as a terminating
 518             // scope since it only executes conditionally.
 519             visitor.region_maps.mark_as_terminating_scope(r.id);
 520         }
 521
 522         ast::ExprIf(_, then, Some(otherwise)) => {
 523             visitor.region_maps.mark_as_terminating_scope(then.id);
 524             visitor.region_maps.mark_as_terminating_scope(otherwise.id);
 525         }
 526
 527         ast::ExprIf(expr, then, None) => {
 528             visitor.region_maps.mark_as_terminating_scope(expr.id);
 529             visitor.region_maps.mark_as_terminating_scope(then.id);
 530         }
 531
 532         ast::ExprLoop(body, _) => {
 533             visitor.region_maps.mark_as_terminating_scope(body.id);
 534         }
 535
 536         ast::ExprWhile(expr, body) => {
 537             visitor.region_maps.mark_as_terminating_scope(expr.id);
 538             visitor.region_maps.mark_as_terminating_scope(body.id);
 539         }
 540
 541         ast::ExprMatch(..) => {
 542             new_cx.var_parent = Some(expr.id);
 543         }
 544
 545         ast::ExprAssignOp(..) | ast::ExprIndex(..) |
 546         ast::ExprUnary(..) | ast::ExprCall(..) | ast::ExprMethodCall(..) => {
 547             // FIXME(#6268) Nested method calls
 548             //
 549             // The lifetimes for a call or method call look as follows:
 550             //
 551             // call.id
 552             // - arg0.id
 553             // - ...
 554             // - argN.id
 555             // - call.callee_id
 556             //
 557             // The idea is that call.callee_id represents *the time when
 558             // the invoked function is actually running* and call.id
 559             // represents *the time to prepare the arguments and make the
 560             // call*.  See the section "Borrows in Calls" borrowck/doc.rs
 561             // for an extended explanantion of why this distinction is
 562             // important.
 563             //
 564             // record_superlifetime(new_cx, expr.callee_id);
 565         }
 566
 567         _ => {}
 568     };
 569
 570
 571     visit::walk_expr(visitor, expr, new_cx);
 572 }
 573
 574 fn resolve_local(visitor: &mut RegionResolutionVisitor,
 575                  local: &ast::Local,
 576                  cx: Context) {
 577     debug!("resolve_local(local.id={},local.init={})",
 578            local.id,local.init.is_some());
 579
 580     let blk_id = match cx.var_parent {
 581         Some(id) => id,
 582         None => {
 583             visitor.sess.span_bug(
 584                 local.span,
 585                 "local without enclosing block");
 586         }
 587     };
 588
 589     // For convenience in trans, associate with the local-id the var
 590     // scope that will be used for any bindings declared in this
 591     // pattern.
 592     visitor.region_maps.record_var_scope(local.id, blk_id);
 593
 594     // As an exception to the normal rules governing temporary
 595     // lifetimes, initializers in a let have a temporary lifetime
 596     // of the enclosing block. This means that e.g. a program
 597     // like the following is legal:
 598     //
 599     //     let ref x = HashMap::new();
 600     //
 601     // Because the hash map will be freed in the enclosing block.
 602     //
 603     // We express the rules more formally based on 3 grammars (defined
 604     // fully in the helpers below that implement them):
 605     //
 606     // 1. `E&`, which matches expressions like `&<rvalue>` that
 607     //    own a pointer into the stack.
 608     //
 609     // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref
 610     //    y)` that produce ref bindings into the value they are
 611     //    matched against or something (at least partially) owned by
 612     //    the value they are matched against. (By partially owned,
 613     //    I mean that creating a binding into a ref-counted or managed value
 614     //    would still count.)
 615     //
 616     // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues
 617     //    based on rvalues like `foo().x[2].y`.
 618     //
 619     // A subexpression `<rvalue>` that appears in a let initializer
 620     // `let pat [: ty] = expr` has an extended temporary lifetime if
 621     // any of the following conditions are met:
 622     //
 623     // A. `pat` matches `P&` and `expr` matches `ET`
 624     //    (covers cases where `pat` creates ref bindings into an rvalue
 625     //     produced by `expr`)
 626     // B. `ty` is a borrowed pointer and `expr` matches `ET`
 627     //    (covers cases where coercion creates a borrow)
 628     // C. `expr` matches `E&`
 629     //    (covers cases `expr` borrows an rvalue that is then assigned
 630     //     to memory (at least partially) owned by the binding)
 631     //
 632     // Here are some examples hopefully giving an intution where each
 633     // rule comes into play and why:
 634     //
 635     // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)`
 636     // would have an extended lifetime, but not `foo()`.
 637     //
 638     // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]`
 639     // would have an extended lifetime, but not `foo()`.
 640     //
 641     // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended
 642     // lifetime.
 643     //
 644     // In some cases, multiple rules may apply (though not to the same
 645     // rvalue). For example:
 646     //
 647     //     let ref x = [&a(), &b()];
 648     //
 649     // Here, the expression `[...]` has an extended lifetime due to rule
 650     // A, but the inner rvalues `a()` and `b()` have an extended lifetime
 651     // due to rule C.
 652     //
 653     // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST.
 654
 655     match local.init {
 656         Some(expr) => {
 657             record_rvalue_scope_if_borrow_expr(visitor, expr, blk_id);
 658
 659             if is_binding_pat(local.pat) || is_borrowed_ty(local.ty) {
 660                 record_rvalue_scope(visitor, expr, blk_id);
 661             }
 662         }
 663
 664         None => { }
 665     }
 666
 667     visit::walk_local(visitor, local, cx);
 668
 669     fn is_binding_pat(pat: &ast::Pat) -> bool {
 670         /*!
 671          * True if `pat` match the `P&` nonterminal:
 672          *
 673          *     P& = ref X
 674          *        | StructName { ..., P&, ... }
 675          *        | VariantName(..., P&, ...)
 676          *        | [ ..., P&, ... ]
 677          *        | ( ..., P&, ... )
 678          *        | ~P&
 679          *        | box P&
 680          */
 681
 682         match pat.node {
 683             ast::PatIdent(ast::BindByRef(_), _, _) => true,
 684
 685             ast::PatStruct(_, ref field_pats, _) => {
 686                 field_pats.iter().any(|fp| is_binding_pat(fp.pat))
 687             }
 688
 689             ast::PatVec(ref pats1, ref pats2, ref pats3) => {
 690                 pats1.iter().any(|&p| is_binding_pat(p)) ||
 691                 pats2.iter().any(|&p| is_binding_pat(p)) ||
 692                 pats3.iter().any(|&p| is_binding_pat(p))
 693             }
 694
 695             ast::PatEnum(_, Some(ref subpats)) |
 696             ast::PatTup(ref subpats) => {
 697                 subpats.iter().any(|&p| is_binding_pat(p))
 698             }
 699
 700             ast::PatUniq(subpat) => {
 701                 is_binding_pat(subpat)
 702             }
 703
 704             _ => false,
 705         }
 706     }
 707
 708     fn is_borrowed_ty(ty: &ast::Ty) -> bool {
 709         /*!
 710          * True if `ty` is a borrowed pointer type
 711          * like `&int` or `&[...]`.
 712          */
 713
 714         match ty.node {
 715             ast::TyRptr(..) => true,
 716             _ => false
 717         }
 718     }
 719
 720     fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor,
 721                                           expr: &ast::Expr,
 722                                           blk_id: ast::NodeId) {
 723         /*!
 724          * If `expr` matches the `E&` grammar, then records an extended
 725          * rvalue scope as appropriate:
 726          *
 727          *     E& = & ET
 728          *        | StructName { ..., f: E&, ... }
 729          *        | [ ..., E&, ... ]
 730          *        | ( ..., E&, ... )
 731          *        | {...; E&}
 732          *        | ~E&
 733          *        | E& as ...
 734          *        | ( E& )
 735          */
 736
 737         match expr.node {
 738             ast::ExprAddrOf(_, subexpr) => {
 739                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 740                 record_rvalue_scope(visitor, subexpr, blk_id);
 741             }
 742             ast::ExprStruct(_, ref fields, _) => {
 743                 for field in fields.iter() {
 744                     record_rvalue_scope_if_borrow_expr(
 745                         visitor, field.expr, blk_id);
 746                 }
 747             }
 748             ast::ExprVstore(subexpr, _) => {
 749                 visitor.region_maps.record_rvalue_scope(subexpr.id, blk_id);
 750                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 751             }
 752             ast::ExprVec(ref subexprs, _) |
 753             ast::ExprTup(ref subexprs) => {
 754                 for &subexpr in subexprs.iter() {
 755                     record_rvalue_scope_if_borrow_expr(
 756                         visitor, subexpr, blk_id);
 757                 }
 758             }
 759             ast::ExprUnary(ast::UnUniq, subexpr) => {
 760                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id);
 761             }
 762             ast::ExprCast(subexpr, _) |
 763             ast::ExprParen(subexpr) => {
 764                 record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id)
 765             }
 766             ast::ExprBlock(ref block) => {
 767                 match block.expr {
 768                     Some(subexpr) => {
 769                         record_rvalue_scope_if_borrow_expr(
 770                             visitor, subexpr, blk_id);
 771                     }
 772                     None => { }
 773                 }
 774             }
 775             _ => {
 776             }
 777         }
 778     }
 779
 780     fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor,
 781                                expr: &'a ast::Expr,
 782                                blk_id: ast::NodeId) {
 783         /*!
 784          * Applied to an expression `expr` if `expr` -- or something
 785          * owned or partially owned by `expr` -- is going to be
 786          * indirectly referenced by a variable in a let statement. In
 787          * that case, the "temporary lifetime" or `expr` is extended
 788          * to be the block enclosing the `let` statement.
 789          *
 790          * More formally, if `expr` matches the grammar `ET`, record
 791          * the rvalue scope of the matching `<rvalue>` as `blk_id`:
 792          *
 793          *     ET = *ET
 794          *        | ET[...]
 795          *        | ET.f
 796          *        | (ET)
 797          *        | <rvalue>
 798          *
 799          * Note: ET is intended to match "rvalues or
 800          * lvalues based on rvalues".
 801          */
 802
 803         let mut expr = expr;
 804         loop {
 805             // Note: give all the expressions matching `ET` with the
 806             // extended temporary lifetime, not just the innermost rvalue,
 807             // because in trans if we must compile e.g. `*rvalue()`
 808             // into a temporary, we request the temporary scope of the
 809             // outer expression.
 810             visitor.region_maps.record_rvalue_scope(expr.id, blk_id);
 811
 812             match expr.node {
 813                 ast::ExprAddrOf(_, ref subexpr) |
 814                 ast::ExprUnary(ast::UnDeref, ref subexpr) |
 815                 ast::ExprField(ref subexpr, _, _) |
 816                 ast::ExprIndex(ref subexpr, _) |
 817                 ast::ExprParen(ref subexpr) => {
 818                     let subexpr: &'a @Expr = subexpr; // FIXME(#11586)
 819                     expr = &**subexpr;
 820                 }
 821                 _ => {
 822                     return;
 823                 }
 824             }
 825         }
 826     }
 827 }
 828
 829 fn resolve_item(visitor: &mut RegionResolutionVisitor,
 830                 item: &ast::Item,
 831                 cx: Context) {
 832     // Items create a new outer block scope as far as we're concerned.
 833     let new_cx = Context {var_parent: None, parent: None, ..cx};
 834     visit::walk_item(visitor, item, new_cx);
 835 }
 836
 837 fn resolve_fn(visitor: &mut RegionResolutionVisitor,
 838               fk: &FnKind,
 839               decl: &ast::FnDecl,
 840               body: &ast::Block,
 841               sp: Span,
 842               id: ast::NodeId,
 843               cx: Context) {
 844     debug!("region::resolve_fn(id={}, \
 845                                span={:?}, \
 846                                body.id={}, \
 847                                cx.parent={})",
 848            id,
 849            visitor.sess.codemap().span_to_str(sp),
 850            body.id,
 851            cx.parent);
 852
 853     visitor.region_maps.mark_as_terminating_scope(body.id);
 854
 855     // The arguments and `self` are parented to the body of the fn.
 856     let decl_cx = Context {parent: Some(body.id),
 857                            var_parent: Some(body.id)};
 858     visit::walk_fn_decl(visitor, decl, decl_cx);
 859
 860     // The body of the fn itself is either a root scope (top-level fn)
 861     // or it continues with the inherited scope (closures).
 862     let body_cx = match *fk {
 863         visit::FkItemFn(..) | visit::FkMethod(..) => {
 864             Context {parent: None, var_parent: None, ..cx}
 865         }
 866         visit::FkFnBlock(..) => {
 867             // FIXME(#3696) -- at present we are place the closure body
 868             // within the region hierarchy exactly where it appears lexically.
 869             // This is wrong because the closure may live longer
 870             // than the enclosing expression. We should probably fix this,
 871             // but the correct fix is a bit subtle, and I am also not sure
 872             // that the present approach is unsound -- it may not permit
 873             // any illegal programs. See issue for more details.
 874             cx
 875         }
 876     };
 877     visitor.visit_block(body, body_cx);
 878 }
 879
 880 impl<'a> Visitor<Context> for RegionResolutionVisitor<'a> {
 881
 882     fn visit_block(&mut self, b: &Block, cx: Context) {
 883         resolve_block(self, b, cx);
 884     }
 885
 886     fn visit_item(&mut self, i: &Item, cx: Context) {
 887         resolve_item(self, i, cx);
 888     }
 889
 890     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
 891                 b: &Block, s: Span, n: NodeId, cx: Context) {
 892         resolve_fn(self, fk, fd, b, s, n, cx);
 893     }
 894     fn visit_arm(&mut self, a: &Arm, cx: Context) {
 895         resolve_arm(self, a, cx);
 896     }
 897     fn visit_pat(&mut self, p: &Pat, cx: Context) {
 898         resolve_pat(self, p, cx);
 899     }
 900     fn visit_stmt(&mut self, s: &Stmt, cx: Context) {
 901         resolve_stmt(self, s, cx);
 902     }
 903     fn visit_expr(&mut self, ex: &Expr, cx: Context) {
 904         resolve_expr(self, ex, cx);
 905     }
 906     fn visit_local(&mut self, l: &Local, cx: Context) {
 907         resolve_local(self, l, cx);
 908     }
 909 }
 910
 911 pub fn resolve_crate(sess: &Session, krate: &ast::Crate) -> RegionMaps {
 912     let maps = RegionMaps {
 913         scope_map: RefCell::new(NodeMap::new()),
 914         var_map: RefCell::new(NodeMap::new()),
 915         free_region_map: RefCell::new(HashMap::new()),
 916         rvalue_scopes: RefCell::new(NodeMap::new()),
 917         terminating_scopes: RefCell::new(HashSet::new()),
 918     };
 919     {
 920         let mut visitor = RegionResolutionVisitor {
 921             sess: sess,
 922             region_maps: &maps
 923         };
 924         let cx = Context { parent: None, var_parent: None };
 925         visit::walk_crate(&mut visitor, krate, cx);
 926     }
 927     return maps;
 928 }
 929
 930 pub fn resolve_inlined_item(sess: &Session,
 931                             region_maps: &RegionMaps,
 932                             item: &ast::InlinedItem) {
 933     let cx = Context {parent: None,
 934                       var_parent: None};
 935     let mut visitor = RegionResolutionVisitor {
 936         sess: sess,
 937         region_maps: region_maps,
 938     };
 939     visit::walk_inlined_item(&mut visitor, item, cx);
 940 }
 941