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 //! This file actually contains two passes related to regions.  The first
  12 //! pass builds up the `scope_map`, which describes the parent links in
  13 //! the region hierarchy.  The second pass infers which types must be
  14 //! region parameterized.
  15 //!
  16 //! Most of the documentation on regions can be found in
  17 //! `middle/typeck/infer/region_inference.rs`
  18
  19 use session::Session;
  20 use middle::ty::{self, Ty, FreeRegion};
  21 use util::nodemap::{FnvHashMap, FnvHashSet, NodeMap};
  22 use util::common::can_reach;
  23
  24 use std::cell::RefCell;
  25 use syntax::codemap::{self, Span};
  26 use syntax::{ast, visit};
  27 use syntax::ast::{Block, Item, FnDecl, NodeId, Arm, Pat, Stmt, Expr, Local};
  28 use syntax::ast_util::{stmt_id};
  29 use syntax::ast_map;
  30 use syntax::ptr::P;
  31 use syntax::visit::{Visitor, FnKind};
  32
  33 /// CodeExtent represents a statically-describable extent that can be
  34 /// used to bound the lifetime/region for values.
  35 ///
  36 /// `Misc(node_id)`: Any AST node that has any extent at all has the
  37 /// `Misc(node_id)` extent. Other variants represent special cases not
  38 /// immediately derivable from the abstract syntax tree structure.
  39 ///
  40 /// `DestructionScope(node_id)` represents the extent of destructors
  41 /// implicitly-attached to `node_id` that run immediately after the
  42 /// expression for `node_id` itself. Not every AST node carries a
  43 /// `DestructionScope`, but those that are `terminating_scopes` do;
  44 /// see discussion with `RegionMaps`.
  45 ///
  46 /// `Remainder(BlockRemainder { block, statement_index })` represents
  47 /// the extent of user code running immediately after the initializer
  48 /// expression for the indexed statement, until the end of the block.
  49 ///
  50 /// So: the following code can be broken down into the extents beneath:
  51 /// ```
  52 /// let a = f().g( 'b: { let x = d(); let y = d(); x.h(y)  }   ) ;
  53 /// ```
  54 ///
  55 ///                                                              +-+ (D12.)
  56 ///                                                        +-+       (D11.)
  57 ///                                              +---------+         (R10.)
  58 ///                                              +-+                  (D9.)
  59 ///                                   +----------+                    (M8.)
  60 ///                                 +----------------------+          (R7.)
  61 ///                                 +-+                               (D6.)
  62 ///                      +----------+                                 (M5.)
  63 ///                    +-----------------------------------+          (M4.)
  64 ///         +--------------------------------------------------+      (M3.)
  65 ///         +--+                                                      (M2.)
  66 /// +-----------------------------------------------------------+     (M1.)
  67 ///
  68 ///  (M1.): Misc extent of the whole `let a = ...;` statement.
  69 ///  (M2.): Misc extent of the `f()` expression.
  70 ///  (M3.): Misc extent of the `f().g(..)` expression.
  71 ///  (M4.): Misc extent of the block labelled `'b:`.
  72 ///  (M5.): Misc extent of the `let x = d();` statement
  73 ///  (D6.): DestructionScope for temporaries created during M5.
  74 ///  (R7.): Remainder extent for block `'b:`, stmt 0 (let x = ...).
  75 ///  (M8.): Misc Extent of the `let y = d();` statement.
  76 ///  (D9.): DestructionScope for temporaries created during M8.
  77 /// (R10.): Remainder extent for block `'b:`, stmt 1 (let y = ...).
  78 /// (D11.): DestructionScope for temporaries and bindings from block `'b:`.
  79 /// (D12.): DestructionScope for temporaries created during M1 (e.g. f()).
  80 ///
  81 /// Note that while the above picture shows the destruction scopes
  82 /// as following their corresponding misc extents, in the internal
  83 /// data structures of the compiler the destruction scopes are
  84 /// represented as enclosing parents. This is sound because we use the
  85 /// enclosing parent relationship just to ensure that referenced
  86 /// values live long enough; phrased another way, the starting point
  87 /// of each range is not really the important thing in the above
  88 /// picture, but rather the ending point.
  89 ///
  90 /// FIXME (pnkfelix): This currently derives `PartialOrd` and `Ord` to
  91 /// placate the same deriving in `ty::FreeRegion`, but we may want to
  92 /// actually attach a more meaningful ordering to scopes than the one
  93 /// generated via deriving here.
  94 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
  95            RustcDecodable, Debug, Copy)]
  96 pub enum CodeExtent {
  97     Misc(ast::NodeId),
  98     DestructionScope(ast::NodeId), // extent of destructors for temporaries of node-id
  99     Remainder(BlockRemainder)
 100 }
 101
 102 /// extent of destructors for temporaries of node-id
 103 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
 104            RustcDecodable, Debug, Copy)]
 105 pub struct DestructionScopeData {
 106     pub node_id: ast::NodeId
 107 }
 108
 109 impl DestructionScopeData {
 110     pub fn new(node_id: ast::NodeId) -> DestructionScopeData {
 111         DestructionScopeData { node_id: node_id }
 112     }
 113     pub fn to_code_extent(&self) -> CodeExtent {
 114         CodeExtent::DestructionScope(self.node_id)
 115     }
 116 }
 117
 118 /// Represents a subscope of `block` for a binding that is introduced
 119 /// by `block.stmts[first_statement_index]`. Such subscopes represent
 120 /// a suffix of the block. Note that each subscope does not include
 121 /// the initializer expression, if any, for the statement indexed by
 122 /// `first_statement_index`.
 123 ///
 124 /// For example, given `{ let (a, b) = EXPR_1; let c = EXPR_2; ... }`:
 125 ///
 126 /// * the subscope with `first_statement_index == 0` is scope of both
 127 ///   `a` and `b`; it does not include EXPR_1, but does include
 128 ///   everything after that first `let`. (If you want a scope that
 129 ///   includes EXPR_1 as well, then do not use `CodeExtent::Remainder`,
 130 ///   but instead another `CodeExtent` that encompasses the whole block,
 131 ///   e.g. `CodeExtent::Misc`.
 132 ///
 133 /// * the subscope with `first_statement_index == 1` is scope of `c`,
 134 ///   and thus does not include EXPR_2, but covers the `...`.
 135 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
 136          RustcDecodable, Debug, Copy)]
 137 pub struct BlockRemainder {
 138     pub block: ast::NodeId,
 139     pub first_statement_index: uint,
 140 }
 141
 142 impl CodeExtent {
 143     /// Creates a scope that represents the dynamic extent associated
 144     /// with `node_id`.
 145     pub fn from_node_id(node_id: ast::NodeId) -> CodeExtent {
 146         CodeExtent::Misc(node_id)
 147     }
 148
 149     /// Returns a node id associated with this scope.
 150     ///
 151     /// NB: likely to be replaced as API is refined; e.g. pnkfelix
 152     /// anticipates `fn entry_node_id` and `fn each_exit_node_id`.
 153     pub fn node_id(&self) -> ast::NodeId {
 154         match *self {
 155             CodeExtent::Misc(node_id) => node_id,
 156             CodeExtent::Remainder(br) => br.block,
 157             CodeExtent::DestructionScope(node_id) => node_id,
 158         }
 159     }
 160
 161     /// Maps this scope to a potentially new one according to the
 162     /// NodeId transformer `f_id`.
 163     pub fn map_id<F>(&self, f_id: F) -> CodeExtent where
 164         F: FnOnce(ast::NodeId) -> ast::NodeId,
 165     {
 166         match *self {
 167             CodeExtent::Misc(node_id) => CodeExtent::Misc(f_id(node_id)),
 168             CodeExtent::Remainder(br) =>
 169                 CodeExtent::Remainder(BlockRemainder {
 170                     block: f_id(br.block), first_statement_index: br.first_statement_index }),
 171             CodeExtent::DestructionScope(node_id) =>
 172                 CodeExtent::DestructionScope(f_id(node_id)),
 173         }
 174     }
 175
 176     /// Returns the span of this CodeExtent.  Note that in general the
 177     /// returned span may not correspond to the span of any node id in
 178     /// the AST.
 179     pub fn span(&self, ast_map: &ast_map::Map) -> Option<Span> {
 180         match ast_map.find(self.node_id()) {
 181             Some(ast_map::NodeBlock(ref blk)) => {
 182                 match *self {
 183                     CodeExtent::Misc(_) |
 184                     CodeExtent::DestructionScope(_) => Some(blk.span),
 185
 186                     CodeExtent::Remainder(r) => {
 187                         assert_eq!(r.block, blk.id);
 188                         // Want span for extent starting after the
 189                         // indexed statement and ending at end of
 190                         // `blk`; reuse span of `blk` and shift `lo`
 191                         // forward to end of indexed statement.
 192                         //
 193                         // (This is the special case aluded to in the
 194                         // doc-comment for this method)
 195                         let stmt_span = blk.stmts[r.first_statement_index].span;
 196                         Some(Span { lo: stmt_span.hi, ..blk.span })
 197                     }
 198                 }
 199             }
 200             Some(ast_map::NodeExpr(ref expr)) => Some(expr.span),
 201             Some(ast_map::NodeStmt(ref stmt)) => Some(stmt.span),
 202             Some(ast_map::NodeItem(ref item)) => Some(item.span),
 203             Some(_) | None => None,
 204          }
 205     }
 206 }
 207
 208 /// The region maps encode information about region relationships.
 209 ///
 210 /// - `scope_map` maps from a scope id to the enclosing scope id; this is
 211 ///   usually corresponding to the lexical nesting, though in the case of
 212 ///   closures the parent scope is the innermost conditional expression or repeating
 213 ///   block. (Note that the enclosing scope id for the block
 214 ///   associated with a closure is the closure itself.)
 215 ///
 216 /// - `var_map` maps from a variable or binding id to the block in which
 217 ///   that variable is declared.
 218 ///
 219 /// - `free_region_map` maps from a free region `a` to a list of free
 220 ///   regions `bs` such that `a <= b for all b in bs`
 221 ///   - the free region map is populated during type check as we check
 222 ///     each function. See the function `relate_free_regions` for
 223 ///     more information.
 224 ///
 225 /// - `rvalue_scopes` includes entries for those expressions whose cleanup
 226 ///   scope is larger than the default. The map goes from the expression
 227 ///   id to the cleanup scope id. For rvalues not present in this table,
 228 ///   the appropriate cleanup scope is the innermost enclosing statement,
 229 ///   conditional expression, or repeating block (see `terminating_scopes`).
 230 ///
 231 /// - `terminating_scopes` is a set containing the ids of each statement,
 232 ///   or conditional/repeating expression. These scopes are calling "terminating
 233 ///   scopes" because, when attempting to find the scope of a temporary, by
 234 ///   default we search up the enclosing scopes until we encounter the
 235 ///   terminating scope. A conditional/repeating
 236 ///   expression is one which is not guaranteed to execute exactly once
 237 ///   upon entering the parent scope. This could be because the expression
 238 ///   only executes conditionally, such as the expression `b` in `a && b`,
 239 ///   or because the expression may execute many times, such as a loop
 240 ///   body. The reason that we distinguish such expressions is that, upon
 241 ///   exiting the parent scope, we cannot statically know how many times
 242 ///   the expression executed, and thus if the expression creates
 243 ///   temporaries we cannot know statically how many such temporaries we
 244 ///   would have to cleanup. Therefore we ensure that the temporaries never
 245 ///   outlast the conditional/repeating expression, preventing the need
 246 ///   for dynamic checks and/or arbitrary amounts of stack space.
 247 pub struct RegionMaps {
 248     scope_map: RefCell<FnvHashMap<CodeExtent, CodeExtent>>,
 249     var_map: RefCell<NodeMap<CodeExtent>>,
 250     free_region_map: RefCell<FnvHashMap<FreeRegion, Vec<FreeRegion>>>,
 251     rvalue_scopes: RefCell<NodeMap<CodeExtent>>,
 252     terminating_scopes: RefCell<FnvHashSet<CodeExtent>>,
 253 }
 254
 255 /// Carries the node id for the innermost block or match expression,
 256 /// for building up the `var_map` which maps ids to the blocks in
 257 /// which they were declared.
 258 #[derive(PartialEq, Eq, Debug, Copy)]
 259 enum InnermostDeclaringBlock {
 260     None,
 261     Block(ast::NodeId),
 262     Statement(DeclaringStatementContext),
 263     Match(ast::NodeId),
 264 }
 265
 266 impl InnermostDeclaringBlock {
 267     fn to_code_extent(&self) -> Option<CodeExtent> {
 268         let extent = match *self {
 269             InnermostDeclaringBlock::None => {
 270                 return Option::None;
 271             }
 272             InnermostDeclaringBlock::Block(id) |
 273             InnermostDeclaringBlock::Match(id) => CodeExtent::from_node_id(id),
 274             InnermostDeclaringBlock::Statement(s) =>  s.to_code_extent(),
 275         };
 276         Option::Some(extent)
 277     }
 278 }
 279
 280 /// Contextual information for declarations introduced by a statement
 281 /// (i.e. `let`). It carries node-id's for statement and enclosing
 282 /// block both, as well as the statement's index within the block.
 283 #[derive(PartialEq, Eq, Debug, Copy)]
 284 struct DeclaringStatementContext {
 285     stmt_id: ast::NodeId,
 286     block_id: ast::NodeId,
 287     stmt_index: uint,
 288 }
 289
 290 impl DeclaringStatementContext {
 291     fn to_code_extent(&self) -> CodeExtent {
 292         CodeExtent::Remainder(BlockRemainder {
 293             block: self.block_id,
 294             first_statement_index: self.stmt_index,
 295         })
 296     }
 297 }
 298
 299 #[derive(PartialEq, Eq, Debug, Copy)]
 300 enum InnermostEnclosingExpr {
 301     None,
 302     Some(ast::NodeId),
 303     Statement(DeclaringStatementContext),
 304 }
 305
 306 impl InnermostEnclosingExpr {
 307     fn to_code_extent(&self) -> Option<CodeExtent> {
 308         let extent = match *self {
 309             InnermostEnclosingExpr::None => {
 310                 return Option::None;
 311             }
 312             InnermostEnclosingExpr::Statement(s) =>
 313                 s.to_code_extent(),
 314             InnermostEnclosingExpr::Some(parent_id) =>
 315                 CodeExtent::from_node_id(parent_id),
 316         };
 317         Some(extent)
 318     }
 319 }
 320
 321 #[derive(Debug, Copy)]
 322 pub struct Context {
 323     var_parent: InnermostDeclaringBlock,
 324
 325     parent: InnermostEnclosingExpr,
 326 }
 327
 328 struct RegionResolutionVisitor<'a> {
 329     sess: &'a Session,
 330
 331     // Generated maps:
 332     region_maps: &'a RegionMaps,
 333
 334     cx: Context
 335 }
 336
 337
 338 impl RegionMaps {
 339     pub fn each_encl_scope<E>(&self, mut e:E) where E: FnMut(&CodeExtent, &CodeExtent) {
 340         for (child, parent) in self.scope_map.borrow().iter() {
 341             e(child, parent)
 342         }
 343     }
 344     pub fn each_var_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) {
 345         for (child, parent) in self.var_map.borrow().iter() {
 346             e(child, parent)
 347         }
 348     }
 349     pub fn each_encl_free_region<E>(&self, mut e:E) where E: FnMut(&FreeRegion, &FreeRegion) {
 350         for (child, parents) in self.free_region_map.borrow().iter() {
 351             for parent in parents.iter() {
 352                 e(child, parent)
 353             }
 354         }
 355     }
 356     pub fn each_rvalue_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) {
 357         for (child, parent) in self.rvalue_scopes.borrow().iter() {
 358             e(child, parent)
 359         }
 360     }
 361     pub fn each_terminating_scope<E>(&self, mut e:E) where E: FnMut(&CodeExtent) {
 362         for scope in self.terminating_scopes.borrow().iter() {
 363             e(scope)
 364         }
 365     }
 366
 367     pub fn relate_free_regions(&self, sub: FreeRegion, sup: FreeRegion) {
 368         match self.free_region_map.borrow_mut().get_mut(&sub) {
 369             Some(sups) => {
 370                 if !sups.iter().any(|x| x == &sup) {
 371                     sups.push(sup);
 372                 }
 373                 return;
 374             }
 375             None => {}
 376         }
 377
 378         debug!("relate_free_regions(sub={:?}, sup={:?})", sub, sup);
 379         self.free_region_map.borrow_mut().insert(sub, vec!(sup));
 380     }
 381
 382     pub fn record_encl_scope(&self, sub: CodeExtent, sup: CodeExtent) {
 383         debug!("record_encl_scope(sub={:?}, sup={:?})", sub, sup);
 384         assert!(sub != sup);
 385         self.scope_map.borrow_mut().insert(sub, sup);
 386     }
 387
 388     pub fn record_var_scope(&self, var: ast::NodeId, lifetime: CodeExtent) {
 389         debug!("record_var_scope(sub={:?}, sup={:?})", var, lifetime);
 390         assert!(var != lifetime.node_id());
 391         self.var_map.borrow_mut().insert(var, lifetime);
 392     }
 393
 394     pub fn record_rvalue_scope(&self, var: ast::NodeId, lifetime: CodeExtent) {
 395         debug!("record_rvalue_scope(sub={:?}, sup={:?})", var, lifetime);
 396         assert!(var != lifetime.node_id());
 397         self.rvalue_scopes.borrow_mut().insert(var, lifetime);
 398     }
 399
 400     /// Records that a scope is a TERMINATING SCOPE. Whenever we create automatic temporaries --
 401     /// e.g. by an expression like `a().f` -- they will be freed within the innermost terminating
 402     /// scope.
 403     pub fn mark_as_terminating_scope(&self, scope_id: CodeExtent) {
 404         debug!("record_terminating_scope(scope_id={:?})", scope_id);
 405         self.terminating_scopes.borrow_mut().insert(scope_id);
 406     }
 407
 408     pub fn opt_encl_scope(&self, id: CodeExtent) -> Option<CodeExtent> {
 409         //! Returns the narrowest scope that encloses `id`, if any.
 410         self.scope_map.borrow().get(&id).map(|x| *x)
 411     }
 412
 413     #[allow(dead_code)] // used in middle::cfg
 414     pub fn encl_scope(&self, id: CodeExtent) -> CodeExtent {
 415         //! Returns the narrowest scope that encloses `id`, if any.
 416         match self.scope_map.borrow().get(&id) {
 417             Some(&r) => r,
 418             None => { panic!("no enclosing scope for id {:?}", id); }
 419         }
 420     }
 421
 422     /// Returns the lifetime of the local variable `var_id`
 423     pub fn var_scope(&self, var_id: ast::NodeId) -> CodeExtent {
 424         match self.var_map.borrow().get(&var_id) {
 425             Some(&r) => r,
 426             None => { panic!("no enclosing scope for id {:?}", var_id); }
 427         }
 428     }
 429
 430     pub fn temporary_scope(&self, expr_id: ast::NodeId) -> Option<CodeExtent> {
 431         //! Returns the scope when temp created by expr_id will be cleaned up
 432
 433         // check for a designated rvalue scope
 434         match self.rvalue_scopes.borrow().get(&expr_id) {
 435             Some(&s) => {
 436                 debug!("temporary_scope({:?}) = {:?} [custom]", expr_id, s);
 437                 return Some(s);
 438             }
 439             None => { }
 440         }
 441
 442         // else, locate the innermost terminating scope
 443         // if there's one. Static items, for instance, won't
 444         // have an enclosing scope, hence no scope will be
 445         // returned.
 446         let mut id = match self.opt_encl_scope(CodeExtent::from_node_id(expr_id)) {
 447             Some(i) => i,
 448             None => { return None; }
 449         };
 450
 451         while !self.terminating_scopes.borrow().contains(&id) {
 452             match self.opt_encl_scope(id) {
 453                 Some(p) => {
 454                     id = p;
 455                 }
 456                 None => {
 457                     debug!("temporary_scope({:?}) = None", expr_id);
 458                     return None;
 459                 }
 460             }
 461         }
 462         debug!("temporary_scope({:?}) = {:?} [enclosing]", expr_id, id);
 463         return Some(id);
 464     }
 465
 466     pub fn var_region(&self, id: ast::NodeId) -> ty::Region {
 467         //! Returns the lifetime of the variable `id`.
 468
 469         let scope = ty::ReScope(self.var_scope(id));
 470         debug!("var_region({:?}) = {:?}", id, scope);
 471         scope
 472     }
 473
 474     pub fn scopes_intersect(&self, scope1: CodeExtent, scope2: CodeExtent)
 475                             -> bool {
 476         self.is_subscope_of(scope1, scope2) ||
 477         self.is_subscope_of(scope2, scope1)
 478     }
 479
 480     /// Returns true if `subscope` is equal to or is lexically nested inside `superscope` and false
 481     /// otherwise.
 482     pub fn is_subscope_of(&self,
 483                           subscope: CodeExtent,
 484                           superscope: CodeExtent)
 485                           -> bool {
 486         let mut s = subscope;
 487         while superscope != s {
 488             match self.scope_map.borrow().get(&s) {
 489                 None => {
 490                     debug!("is_subscope_of({:?}, {:?}, s={:?})=false",
 491                            subscope, superscope, s);
 492
 493                     return false;
 494                 }
 495                 Some(&scope) => s = scope
 496             }
 497         }
 498
 499         debug!("is_subscope_of({:?}, {:?})=true",
 500                subscope, superscope);
 501
 502         return true;
 503     }
 504
 505     /// Determines whether two free regions have a subregion relationship
 506     /// by walking the graph encoded in `free_region_map`.  Note that
 507     /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
 508     /// (that is, the user can give two different names to the same lifetime).
 509     pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
 510         can_reach(&*self.free_region_map.borrow(), sub, sup)
 511     }
 512
 513     /// Determines whether one region is a subregion of another.  This is intended to run *after
 514     /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
 515     pub fn is_subregion_of(&self,
 516                            sub_region: ty::Region,
 517                            super_region: ty::Region)
 518                            -> bool {
 519         debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
 520                sub_region, super_region);
 521
 522         sub_region == super_region || {
 523             match (sub_region, super_region) {
 524                 (ty::ReEmpty, _) |
 525                 (_, ty::ReStatic) => {
 526                     true
 527                 }
 528
 529                 (ty::ReScope(sub_scope), ty::ReScope(super_scope)) => {
 530                     self.is_subscope_of(sub_scope, super_scope)
 531                 }
 532
 533                 (ty::ReScope(sub_scope), ty::ReFree(ref fr)) => {
 534                     self.is_subscope_of(sub_scope, fr.scope.to_code_extent())
 535                 }
 536
 537                 (ty::ReFree(sub_fr), ty::ReFree(super_fr)) => {
 538                     self.sub_free_region(sub_fr, super_fr)
 539                 }
 540
 541                 (ty::ReEarlyBound(param_id_a, param_space_a, index_a, _),
 542                  ty::ReEarlyBound(param_id_b, param_space_b, index_b, _)) => {
 543                     // This case is used only to make sure that explicitly-
 544                     // specified `Self` types match the real self type in
 545                     // implementations.
 546                     param_id_a == param_id_b &&
 547                         param_space_a == param_space_b &&
 548                         index_a == index_b
 549                 }
 550
 551                 _ => {
 552                     false
 553                 }
 554             }
 555         }
 556     }
 557
 558     /// Finds the nearest common ancestor (if any) of two scopes.  That is, finds the smallest
 559     /// scope which is greater than or equal to both `scope_a` and `scope_b`.
 560     pub fn nearest_common_ancestor(&self,
 561                                    scope_a: CodeExtent,
 562                                    scope_b: CodeExtent)
 563                                    -> Option<CodeExtent> {
 564         if scope_a == scope_b { return Some(scope_a); }
 565
 566         let a_ancestors = ancestors_of(self, scope_a);
 567         let b_ancestors = ancestors_of(self, scope_b);
 568         let mut a_index = a_ancestors.len() - 1;
 569         let mut b_index = b_ancestors.len() - 1;
 570
 571         // Here, ~[ab]_ancestors is a vector going from narrow to broad.
 572         // The end of each vector will be the item where the scope is
 573         // defined; if there are any common ancestors, then the tails of
 574         // the vector will be the same.  So basically we want to walk
 575         // backwards from the tail of each vector and find the first point
 576         // where they diverge.  If one vector is a suffix of the other,
 577         // then the corresponding scope is a superscope of the other.
 578
 579         if a_ancestors[a_index] != b_ancestors[b_index] {
 580             return None;
 581         }
 582
 583         loop {
 584             // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
 585             // for all indices between a_index and the end of the array
 586             if a_index == 0 { return Some(scope_a); }
 587             if b_index == 0 { return Some(scope_b); }
 588             a_index -= 1;
 589             b_index -= 1;
 590             if a_ancestors[a_index] != b_ancestors[b_index] {
 591                 return Some(a_ancestors[a_index + 1]);
 592             }
 593         }
 594
 595         fn ancestors_of(this: &RegionMaps, scope: CodeExtent)
 596             -> Vec<CodeExtent> {
 597             // debug!("ancestors_of(scope={:?})", scope);
 598             let mut result = vec!(scope);
 599             let mut scope = scope;
 600             loop {
 601                 match this.scope_map.borrow().get(&scope) {
 602                     None => return result,
 603                     Some(&superscope) => {
 604                         result.push(superscope);
 605                         scope = superscope;
 606                     }
 607                 }
 608                 // debug!("ancestors_of_loop(scope={:?})", scope);
 609             }
 610         }
 611     }
 612 }
 613
 614 /// Records the current parent (if any) as the parent of `child_scope`.
 615 fn record_superlifetime(visitor: &mut RegionResolutionVisitor,
 616                         child_scope: CodeExtent,
 617                         _sp: Span) {
 618     match visitor.cx.parent.to_code_extent() {
 619         Some(parent_scope) =>
 620             visitor.region_maps.record_encl_scope(child_scope, parent_scope),
 621         None => {}
 622     }
 623 }
 624
 625 /// Records the lifetime of a local variable as `cx.var_parent`
 626 fn record_var_lifetime(visitor: &mut RegionResolutionVisitor,
 627                        var_id: ast::NodeId,
 628                        _sp: Span) {
 629     match visitor.cx.var_parent.to_code_extent() {
 630         Some(parent_scope) =>
 631             visitor.region_maps.record_var_scope(var_id, parent_scope),
 632         None => {
 633             // this can happen in extern fn declarations like
 634             //
 635             // extern fn isalnum(c: c_int) -> c_int
 636         }
 637     }
 638 }
 639
 640 fn resolve_block(visitor: &mut RegionResolutionVisitor, blk: &ast::Block) {
 641     debug!("resolve_block(blk.id={:?})", blk.id);
 642
 643     let prev_cx = visitor.cx;
 644
 645     let blk_scope = CodeExtent::Misc(blk.id);
 646     // If block was previously marked as a terminating scope during
 647     // the recursive visit of its parent node in the AST, then we need
 648     // to account for the destruction scope representing the extent of
 649     // the destructors that run immediately after the the block itself
 650     // completes.
 651     if visitor.region_maps.terminating_scopes.borrow().contains(&blk_scope) {
 652         let dtor_scope = CodeExtent::DestructionScope(blk.id);
 653         record_superlifetime(visitor, dtor_scope, blk.span);
 654         visitor.region_maps.record_encl_scope(blk_scope, dtor_scope);
 655     } else {
 656         record_superlifetime(visitor, blk_scope, blk.span);
 657     }
 658
 659     // We treat the tail expression in the block (if any) somewhat
 660     // differently from the statements. The issue has to do with
 661     // temporary lifetimes. Consider the following:
 662     //
 663     //    quux({
 664     //        let inner = ... (&bar()) ...;
 665     //
 666     //        (... (&foo()) ...) // (the tail expression)
 667     //    }, other_argument());
 668     //
 669     // Each of the statements within the block is a terminating
 670     // scope, and thus a temporary (e.g. the result of calling
 671     // `bar()` in the initalizer expression for `let inner = ...;`)
 672     // will be cleaned up immediately after its corresponding
 673     // statement (i.e. `let inner = ...;`) executes.
 674     //
 675     // On the other hand, temporaries associated with evaluating the
 676     // tail expression for the block are assigned lifetimes so that
 677     // they will be cleaned up as part of the terminating scope
 678     // *surrounding* the block expression. Here, the terminating
 679     // scope for the block expression is the `quux(..)` call; so
 680     // those temporaries will only be cleaned up *after* both
 681     // `other_argument()` has run and also the call to `quux(..)`
 682     // itself has returned.
 683
 684     visitor.cx = Context {
 685         var_parent: InnermostDeclaringBlock::Block(blk.id),
 686         parent: InnermostEnclosingExpr::Some(blk.id),
 687     };
 688
 689     {
 690         // This block should be kept approximately in sync with
 691         // `visit::walk_block`. (We manually walk the block, rather
 692         // than call `walk_block`, in order to maintain precise
 693         // `InnermostDeclaringBlock` information.)
 694
 695         for (i, statement) in blk.stmts.iter().enumerate() {
 696             if let ast::StmtDecl(_, stmt_id) = statement.node {
 697                 // Each StmtDecl introduces a subscope for bindings
 698                 // introduced by the declaration; this subscope covers
 699                 // a suffix of the block . Each subscope in a block
 700                 // has the previous subscope in the block as a parent,
 701                 // except for the first such subscope, which has the
 702                 // block itself as a parent.
 703                 let declaring = DeclaringStatementContext {
 704                     stmt_id: stmt_id,
 705                     block_id: blk.id,
 706                     stmt_index: i,
 707                 };
 708                 record_superlifetime(
 709                     visitor, declaring.to_code_extent(), statement.span);
 710                 visitor.cx = Context {
 711                     var_parent: InnermostDeclaringBlock::Statement(declaring),
 712                     parent: InnermostEnclosingExpr::Statement(declaring),
 713                 };
 714             }
 715             visitor.visit_stmt(&**statement)
 716         }
 717         visit::walk_expr_opt(visitor, &blk.expr)
 718     }
 719
 720     visitor.cx = prev_cx;
 721 }
 722
 723 fn resolve_arm(visitor: &mut RegionResolutionVisitor, arm: &ast::Arm) {
 724     let arm_body_scope = CodeExtent::from_node_id(arm.body.id);
 725     visitor.region_maps.mark_as_terminating_scope(arm_body_scope);
 726
 727     match arm.guard {
 728         Some(ref expr) => {
 729             let guard_scope = CodeExtent::from_node_id(expr.id);
 730             visitor.region_maps.mark_as_terminating_scope(guard_scope);
 731         }
 732         None => { }
 733     }
 734
 735     visit::walk_arm(visitor, arm);
 736 }
 737
 738 fn resolve_pat(visitor: &mut RegionResolutionVisitor, pat: &ast::Pat) {
 739     record_superlifetime(visitor, CodeExtent::from_node_id(pat.id), pat.span);
 740
 741     // If this is a binding (or maybe a binding, I'm too lazy to check
 742     // the def map) then record the lifetime of that binding.
 743     match pat.node {
 744         ast::PatIdent(..) => {
 745             record_var_lifetime(visitor, pat.id, pat.span);
 746         }
 747         _ => { }
 748     }
 749
 750     visit::walk_pat(visitor, pat);
 751 }
 752
 753 fn resolve_stmt(visitor: &mut RegionResolutionVisitor, stmt: &ast::Stmt) {
 754     let stmt_id = stmt_id(stmt);
 755     debug!("resolve_stmt(stmt.id={:?})", stmt_id);
 756
 757     let stmt_scope = CodeExtent::from_node_id(stmt_id);
 758
 759     // Every statement will clean up the temporaries created during
 760     // execution of that statement. Therefore each statement has an
 761     // associated destruction scope that represents the extent of the
 762     // statement plus its destructors, and thus the extent for which
 763     // regions referenced by the destructors need to survive.
 764     visitor.region_maps.mark_as_terminating_scope(stmt_scope);
 765     let dtor_scope = CodeExtent::DestructionScope(stmt_id);
 766     visitor.region_maps.record_encl_scope(stmt_scope, dtor_scope);
 767     record_superlifetime(visitor, dtor_scope, stmt.span);
 768
 769     let prev_parent = visitor.cx.parent;
 770     visitor.cx.parent = InnermostEnclosingExpr::Some(stmt_id);
 771     visit::walk_stmt(visitor, stmt);
 772     visitor.cx.parent = prev_parent;
 773 }
 774
 775 fn resolve_expr(visitor: &mut RegionResolutionVisitor, expr: &ast::Expr) {
 776     debug!("resolve_expr(expr.id={:?})", expr.id);
 777
 778     let expr_scope = CodeExtent::Misc(expr.id);
 779     // If expr was previously marked as a terminating scope during the
 780     // recursive visit of its parent node in the AST, then we need to
 781     // account for the destruction scope representing the extent of
 782     // the destructors that run immediately after the the expression
 783     // itself completes.
 784     if visitor.region_maps.terminating_scopes.borrow().contains(&expr_scope) {
 785         let dtor_scope = CodeExtent::DestructionScope(expr.id);
 786         record_superlifetime(visitor, dtor_scope, expr.span);
 787         visitor.region_maps.record_encl_scope(expr_scope, dtor_scope);
 788     } else {
 789         record_superlifetime(visitor, expr_scope, expr.span);
 790     }
 791
 792     let prev_cx = visitor.cx;
 793     visitor.cx.parent = InnermostEnclosingExpr::Some(expr.id);
 794
 795     {
 796         let region_maps = &mut visitor.region_maps;
 797         let terminating = |e: &P<ast::Expr>| {
 798             let scope = CodeExtent::from_node_id(e.id);
 799             region_maps.mark_as_terminating_scope(scope)
 800         };
 801         let terminating_block = |b: &P<ast::Block>| {
 802             let scope = CodeExtent::from_node_id(b.id);
 803             region_maps.mark_as_terminating_scope(scope)
 804         };
 805         match expr.node {
 806             // Conditional or repeating scopes are always terminating
 807             // scopes, meaning that temporaries cannot outlive them.
 808             // This ensures fixed size stacks.
 809
 810             ast::ExprBinary(codemap::Spanned { node: ast::BiAnd, .. }, _, ref r) |
 811             ast::ExprBinary(codemap::Spanned { node: ast::BiOr, .. }, _, ref r) => {
 812                 // For shortcircuiting operators, mark the RHS as a terminating
 813                 // scope since it only executes conditionally.
 814                 terminating(r);
 815             }
 816
 817             ast::ExprIf(_, ref then, Some(ref otherwise)) => {
 818                 terminating_block(then);
 819                 terminating(otherwise);
 820             }
 821
 822             ast::ExprIf(ref expr, ref then, None) => {
 823                 terminating(expr);
 824                 terminating_block(then);
 825             }
 826
 827             ast::ExprLoop(ref body, _) => {
 828                 terminating_block(body);
 829             }
 830
 831             ast::ExprWhile(ref expr, ref body, _) => {
 832                 terminating(expr);
 833                 terminating_block(body);
 834             }
 835
 836             ast::ExprMatch(..) => {
 837                 visitor.cx.var_parent = InnermostDeclaringBlock::Match(expr.id);
 838             }
 839
 840             ast::ExprAssignOp(..) | ast::ExprIndex(..) |
 841             ast::ExprUnary(..) | ast::ExprCall(..) | ast::ExprMethodCall(..) => {
 842                 // FIXME(#6268) Nested method calls
 843                 //
 844                 // The lifetimes for a call or method call look as follows:
 845                 //
 846                 // call.id
 847                 // - arg0.id
 848                 // - ...
 849                 // - argN.id
 850                 // - call.callee_id
 851                 //
 852                 // The idea is that call.callee_id represents *the time when
 853                 // the invoked function is actually running* and call.id
 854                 // represents *the time to prepare the arguments and make the
 855                 // call*.  See the section "Borrows in Calls" borrowck/doc.rs
 856                 // for an extended explanation of why this distinction is
 857                 // important.
 858                 //
 859                 // record_superlifetime(new_cx, expr.callee_id);
 860             }
 861
 862             _ => {}
 863         }
 864     }
 865
 866     visit::walk_expr(visitor, expr);
 867     visitor.cx = prev_cx;
 868 }
 869
 870 fn resolve_local(visitor: &mut RegionResolutionVisitor, local: &ast::Local) {
 871     debug!("resolve_local(local.id={:?},local.init={:?})",
 872            local.id,local.init.is_some());
 873
 874     // For convenience in trans, associate with the local-id the var
 875     // scope that will be used for any bindings declared in this
 876     // pattern.
 877     let blk_scope = visitor.cx.var_parent.to_code_extent()
 878         .unwrap_or_else(|| visitor.sess.span_bug(
 879             local.span, "local without enclosing block"));
 880
 881     visitor.region_maps.record_var_scope(local.id, blk_scope);
 882
 883     // As an exception to the normal rules governing temporary
 884     // lifetimes, initializers in a let have a temporary lifetime
 885     // of the enclosing block. This means that e.g. a program
 886     // like the following is legal:
 887     //
 888     //     let ref x = HashMap::new();
 889     //
 890     // Because the hash map will be freed in the enclosing block.
 891     //
 892     // We express the rules more formally based on 3 grammars (defined
 893     // fully in the helpers below that implement them):
 894     //
 895     // 1. `E&`, which matches expressions like `&<rvalue>` that
 896     //    own a pointer into the stack.
 897     //
 898     // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref
 899     //    y)` that produce ref bindings into the value they are
 900     //    matched against or something (at least partially) owned by
 901     //    the value they are matched against. (By partially owned,
 902     //    I mean that creating a binding into a ref-counted or managed value
 903     //    would still count.)
 904     //
 905     // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues
 906     //    based on rvalues like `foo().x[2].y`.
 907     //
 908     // A subexpression `<rvalue>` that appears in a let initializer
 909     // `let pat [: ty] = expr` has an extended temporary lifetime if
 910     // any of the following conditions are met:
 911     //
 912     // A. `pat` matches `P&` and `expr` matches `ET`
 913     //    (covers cases where `pat` creates ref bindings into an rvalue
 914     //     produced by `expr`)
 915     // B. `ty` is a borrowed pointer and `expr` matches `ET`
 916     //    (covers cases where coercion creates a borrow)
 917     // C. `expr` matches `E&`
 918     //    (covers cases `expr` borrows an rvalue that is then assigned
 919     //     to memory (at least partially) owned by the binding)
 920     //
 921     // Here are some examples hopefully giving an intuition where each
 922     // rule comes into play and why:
 923     //
 924     // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)`
 925     // would have an extended lifetime, but not `foo()`.
 926     //
 927     // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]`
 928     // would have an extended lifetime, but not `foo()`.
 929     //
 930     // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended
 931     // lifetime.
 932     //
 933     // In some cases, multiple rules may apply (though not to the same
 934     // rvalue). For example:
 935     //
 936     //     let ref x = [&a(), &b()];
 937     //
 938     // Here, the expression `[...]` has an extended lifetime due to rule
 939     // A, but the inner rvalues `a()` and `b()` have an extended lifetime
 940     // due to rule C.
 941     //
 942     // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST.
 943
 944     match local.init {
 945         Some(ref expr) => {
 946             record_rvalue_scope_if_borrow_expr(visitor, &**expr, blk_scope);
 947
 948             let is_borrow =
 949                 if let Some(ref ty) = local.ty { is_borrowed_ty(&**ty) } else { false };
 950
 951             if is_binding_pat(&*local.pat) || is_borrow {
 952                 record_rvalue_scope(visitor, &**expr, blk_scope);
 953             }
 954         }
 955
 956         None => { }
 957     }
 958
 959     visit::walk_local(visitor, local);
 960
 961     /// True if `pat` match the `P&` nonterminal:
 962     ///
 963     ///     P& = ref X
 964     ///        | StructName { ..., P&, ... }
 965     ///        | VariantName(..., P&, ...)
 966     ///        | [ ..., P&, ... ]
 967     ///        | ( ..., P&, ... )
 968     ///        | box P&
 969     fn is_binding_pat(pat: &ast::Pat) -> bool {
 970         match pat.node {
 971             ast::PatIdent(ast::BindByRef(_), _, _) => true,
 972
 973             ast::PatStruct(_, ref field_pats, _) => {
 974                 field_pats.iter().any(|fp| is_binding_pat(&*fp.node.pat))
 975             }
 976
 977             ast::PatVec(ref pats1, ref pats2, ref pats3) => {
 978                 pats1.iter().any(|p| is_binding_pat(&**p)) ||
 979                 pats2.iter().any(|p| is_binding_pat(&**p)) ||
 980                 pats3.iter().any(|p| is_binding_pat(&**p))
 981             }
 982
 983             ast::PatEnum(_, Some(ref subpats)) |
 984             ast::PatTup(ref subpats) => {
 985                 subpats.iter().any(|p| is_binding_pat(&**p))
 986             }
 987
 988             ast::PatBox(ref subpat) => {
 989                 is_binding_pat(&**subpat)
 990             }
 991
 992             _ => false,
 993         }
 994     }
 995
 996     /// True if `ty` is a borrowed pointer type like `&int` or `&[...]`.
 997     fn is_borrowed_ty(ty: &ast::Ty) -> bool {
 998         match ty.node {
 999             ast::TyRptr(..) => true,
1000             _ => false
1001         }
1002     }
1003
1004     /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate:
1005     ///
1006     ///     E& = & ET
1007     ///        | StructName { ..., f: E&, ... }
1008     ///        | [ ..., E&, ... ]
1009     ///        | ( ..., E&, ... )
1010     ///        | {...; E&}
1011     ///        | box E&
1012     ///        | E& as ...
1013     ///        | ( E& )
1014     fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor,
1015                                           expr: &ast::Expr,
1016                                           blk_id: CodeExtent) {
1017         match expr.node {
1018             ast::ExprAddrOf(_, ref subexpr) => {
1019                 record_rvalue_scope_if_borrow_expr(visitor, &**subexpr, blk_id);
1020                 record_rvalue_scope(visitor, &**subexpr, blk_id);
1021             }
1022             ast::ExprStruct(_, ref fields, _) => {
1023                 for field in fields {
1024                     record_rvalue_scope_if_borrow_expr(
1025                         visitor, &*field.expr, blk_id);
1026                 }
1027             }
1028             ast::ExprVec(ref subexprs) |
1029             ast::ExprTup(ref subexprs) => {
1030                 for subexpr in subexprs {
1031                     record_rvalue_scope_if_borrow_expr(
1032                         visitor, &**subexpr, blk_id);
1033                 }
1034             }
1035             ast::ExprUnary(ast::UnUniq, ref subexpr) => {
1036                 record_rvalue_scope_if_borrow_expr(visitor, &**subexpr, blk_id);
1037             }
1038             ast::ExprCast(ref subexpr, _) |
1039             ast::ExprParen(ref subexpr) => {
1040                 record_rvalue_scope_if_borrow_expr(visitor, &**subexpr, blk_id)
1041             }
1042             ast::ExprBlock(ref block) => {
1043                 match block.expr {
1044                     Some(ref subexpr) => {
1045                         record_rvalue_scope_if_borrow_expr(
1046                             visitor, &**subexpr, blk_id);
1047                     }
1048                     None => { }
1049                 }
1050             }
1051             _ => {
1052             }
1053         }
1054     }
1055
1056     /// Applied to an expression `expr` if `expr` -- or something owned or partially owned by
1057     /// `expr` -- is going to be indirectly referenced by a variable in a let statement. In that
1058     /// case, the "temporary lifetime" or `expr` is extended to be the block enclosing the `let`
1059     /// statement.
1060     ///
1061     /// More formally, if `expr` matches the grammar `ET`, record the rvalue scope of the matching
1062     /// `<rvalue>` as `blk_id`:
1063     ///
1064     ///     ET = *ET
1065     ///        | ET[...]
1066     ///        | ET.f
1067     ///        | (ET)
1068     ///        | <rvalue>
1069     ///
1070     /// Note: ET is intended to match "rvalues or lvalues based on rvalues".
1071     fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor,
1072                                expr: &'a ast::Expr,
1073                                blk_scope: CodeExtent) {
1074         let mut expr = expr;
1075         loop {
1076             // Note: give all the expressions matching `ET` with the
1077             // extended temporary lifetime, not just the innermost rvalue,
1078             // because in trans if we must compile e.g. `*rvalue()`
1079             // into a temporary, we request the temporary scope of the
1080             // outer expression.
1081             visitor.region_maps.record_rvalue_scope(expr.id, blk_scope);
1082
1083             match expr.node {
1084                 ast::ExprAddrOf(_, ref subexpr) |
1085                 ast::ExprUnary(ast::UnDeref, ref subexpr) |
1086                 ast::ExprField(ref subexpr, _) |
1087                 ast::ExprTupField(ref subexpr, _) |
1088                 ast::ExprIndex(ref subexpr, _) |
1089                 ast::ExprParen(ref subexpr) => {
1090                     expr = &**subexpr;
1091                 }
1092                 _ => {
1093                     return;
1094                 }
1095             }
1096         }
1097     }
1098 }
1099
1100 fn resolve_item(visitor: &mut RegionResolutionVisitor, item: &ast::Item) {
1101     // Items create a new outer block scope as far as we're concerned.
1102     let prev_cx = visitor.cx;
1103     visitor.cx = Context {
1104         var_parent: InnermostDeclaringBlock::None,
1105         parent: InnermostEnclosingExpr::None
1106     };
1107     visit::walk_item(visitor, item);
1108     visitor.cx = prev_cx;
1109 }
1110
1111 fn resolve_fn(visitor: &mut RegionResolutionVisitor,
1112               fk: FnKind,
1113               decl: &ast::FnDecl,
1114               body: &ast::Block,
1115               sp: Span,
1116               id: ast::NodeId) {
1117     debug!("region::resolve_fn(id={:?}, \
1118                                span={:?}, \
1119                                body.id={:?}, \
1120                                cx.parent={:?})",
1121            id,
1122            visitor.sess.codemap().span_to_string(sp),
1123            body.id,
1124            visitor.cx.parent);
1125
1126     let body_scope = CodeExtent::from_node_id(body.id);
1127     visitor.region_maps.mark_as_terminating_scope(body_scope);
1128     let dtor_scope = CodeExtent::DestructionScope(body.id);
1129     visitor.region_maps.record_encl_scope(body_scope, dtor_scope);
1130     record_superlifetime(visitor, dtor_scope, body.span);
1131
1132     let outer_cx = visitor.cx;
1133
1134     // The arguments and `self` are parented to the body of the fn.
1135     visitor.cx = Context {
1136         parent: InnermostEnclosingExpr::Some(body.id),
1137         var_parent: InnermostDeclaringBlock::Block(body.id)
1138     };
1139     visit::walk_fn_decl(visitor, decl);
1140
1141     // The body of the fn itself is either a root scope (top-level fn)
1142     // or it continues with the inherited scope (closures).
1143     match fk {
1144         visit::FkItemFn(..) | visit::FkMethod(..) => {
1145             visitor.cx = Context {
1146                 parent: InnermostEnclosingExpr::None,
1147                 var_parent: InnermostDeclaringBlock::None
1148             };
1149             visitor.visit_block(body);
1150             visitor.cx = outer_cx;
1151         }
1152         visit::FkFnBlock(..) => {
1153             // FIXME(#3696) -- at present we are place the closure body
1154             // within the region hierarchy exactly where it appears lexically.
1155             // This is wrong because the closure may live longer
1156             // than the enclosing expression. We should probably fix this,
1157             // but the correct fix is a bit subtle, and I am also not sure
1158             // that the present approach is unsound -- it may not permit
1159             // any illegal programs. See issue for more details.
1160             visitor.cx = outer_cx;
1161             visitor.visit_block(body);
1162         }
1163     }
1164 }
1165
1166 impl<'a, 'v> Visitor<'v> for RegionResolutionVisitor<'a> {
1167
1168     fn visit_block(&mut self, b: &Block) {
1169         resolve_block(self, b);
1170     }
1171
1172     fn visit_item(&mut self, i: &Item) {
1173         resolve_item(self, i);
1174     }
1175
1176     fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl,
1177                 b: &'v Block, s: Span, n: NodeId) {
1178         resolve_fn(self, fk, fd, b, s, n);
1179     }
1180     fn visit_arm(&mut self, a: &Arm) {
1181         resolve_arm(self, a);
1182     }
1183     fn visit_pat(&mut self, p: &Pat) {
1184         resolve_pat(self, p);
1185     }
1186     fn visit_stmt(&mut self, s: &Stmt) {
1187         resolve_stmt(self, s);
1188     }
1189     fn visit_expr(&mut self, ex: &Expr) {
1190         resolve_expr(self, ex);
1191     }
1192     fn visit_local(&mut self, l: &Local) {
1193         resolve_local(self, l);
1194     }
1195 }
1196
1197 pub fn resolve_crate(sess: &Session, krate: &ast::Crate) -> RegionMaps {
1198     let maps = RegionMaps {
1199         scope_map: RefCell::new(FnvHashMap()),
1200         var_map: RefCell::new(NodeMap()),
1201         free_region_map: RefCell::new(FnvHashMap()),
1202         rvalue_scopes: RefCell::new(NodeMap()),
1203         terminating_scopes: RefCell::new(FnvHashSet()),
1204     };
1205     {
1206         let mut visitor = RegionResolutionVisitor {
1207             sess: sess,
1208             region_maps: &maps,
1209             cx: Context {
1210                 parent: InnermostEnclosingExpr::None,
1211                 var_parent: InnermostDeclaringBlock::None,
1212             }
1213         };
1214         visit::walk_crate(&mut visitor, krate);
1215     }
1216     return maps;
1217 }
1218
1219 pub fn resolve_inlined_item(sess: &Session,
1220                             region_maps: &RegionMaps,
1221                             item: &ast::InlinedItem) {
1222     let mut visitor = RegionResolutionVisitor {
1223         sess: sess,
1224         region_maps: region_maps,
1225         cx: Context {
1226             parent: InnermostEnclosingExpr::None,
1227             var_parent: InnermostDeclaringBlock::None
1228         }
1229     };
1230     visit::walk_inlined_item(&mut visitor, item);
1231 }