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