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.
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.
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
20 use driver::session::Session;
21 use metadata::csearch;
23 use middle::ty::{region_variance, rv_covariant, rv_invariant};
24 use middle::ty::{rv_contravariant, FreeRegion};
27 use core::hashmap::{HashMap, HashSet};
29 use syntax::codemap::span;
30 use syntax::print::pprust;
31 use syntax::parse::token::special_idents;
32 use syntax::{ast, visit};
34 pub type parent = Option<ast::node_id>;
37 The region maps encode information about region relationships.
39 - `scope_map` maps from:
40 - an expression to the expression or block encoding the maximum
41 (static) lifetime of a value produced by that expression. This is
42 generally the innermost call, statement, match, or block.
43 - a variable or binding id to the block in which that variable is declared.
44 - `free_region_map` maps from:
45 - a free region `a` to a list of free regions `bs` such that
46 `a <= b for all b in bs`
47 - the free region map is populated during type check as we check
48 each function. See the function `relate_free_regions` for
51 pub struct RegionMaps {
52 priv scope_map: HashMap<ast::node_id, ast::node_id>,
53 priv free_region_map: HashMap<FreeRegion, ~[FreeRegion]>,
58 def_map: resolve::DefMap,
61 region_maps: @mut RegionMaps,
63 // Generally speaking, expressions are parented to their innermost
64 // enclosing block. But some kinds of expressions serve as
65 // parents: calls, methods, etc. In addition, some expressions
66 // serve as parents by virtue of where they appear. For example,
67 // the condition in a while loop is always a parent. In those
68 // cases, we add the node id of such an expression to this set so
69 // that when we visit it we can view it as a parent.
70 root_exprs: @mut HashSet<ast::node_id>,
72 // The parent scope is the innermost block, statement, call, or match
73 // expression during the execution of which the current expression
74 // will be evaluated. Generally speaking, the innermost parent
75 // scope is also the closest suitable ancestor in the AST tree.
77 // There is a subtle point concerning call arguments. Imagine
86 // In what lifetime are the expressions `x` and `y` evaluated? At
87 // first, I imagine the answer was the block `a`, as the arguments
88 // are evaluated before the call takes place. But this turns out
89 // to be wrong. The lifetime of the call must encompass the
90 // argument evaluation as well.
92 // The reason is that evaluation of an earlier argument could
93 // create a borrow which exists during the evaluation of later
94 // arguments. Consider this torture test, for example,
96 // fn test1(x: @mut ~int) {
97 // foo(&**x, *x = ~5);
100 // Here, the first argument `&**x` will be a borrow of the `~int`,
101 // but the second argument overwrites that very value! Bad.
102 // (This test is borrowck-pure-scope-in-call.rs, btw)
106 pub impl RegionMaps {
107 fn relate_free_regions(&mut self,
111 match self.free_region_map.find_mut(&sub) {
113 if !sups.contains(&sup) {
121 debug!("relate_free_regions(sub=%?, sup=%?)", sub, sup);
123 self.free_region_map.insert(sub, ~[sup]);
126 fn record_parent(&mut self,
130 debug!("record_parent(sub=%?, sup=%?)", sub, sup);
132 self.scope_map.insert(sub, sup);
135 fn opt_encl_scope(&self,
136 id: ast::node_id) -> Option<ast::node_id>
138 //! Returns the narrowest scope that encloses `id`, if any.
140 self.scope_map.find(&id).map(|&x| *x)
144 id: ast::node_id) -> ast::node_id
146 //! Returns the narrowest scope that encloses `id`, if any.
148 match self.scope_map.find(&id) {
150 None => { fail!(fmt!("No enclosing scope for id %?", id)); }
154 fn encl_region(&self,
155 id: ast::node_id) -> ty::Region
157 //! Returns the narrowest scope region that encloses `id`, if any.
159 ty::re_scope(self.encl_scope(id))
162 fn is_sub_scope(&self,
163 sub_scope: ast::node_id,
164 superscope: ast::node_id) -> bool
167 * Returns true if `sub_scope` is equal to or is lexically
168 * nested inside `superscope` and false otherwise.
171 let mut sub_scope = sub_scope;
172 while superscope != sub_scope {
173 match self.scope_map.find(&sub_scope) {
174 None => return false,
175 Some(&scope) => sub_scope = scope
181 fn sub_free_region(&self,
183 sup: FreeRegion) -> bool
186 * Determines whether two free regions have a subregion relationship
187 * by walking the graph encoded in `free_region_map`. Note that
188 * it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
189 * (that is, the user can give two different names to the same lifetime).
196 // Do a little breadth-first-search here. The `queue` list
197 // doubles as a way to detect if we've seen a particular FR
198 // before. Note that we expect this graph to be an *extremely
200 let mut queue = ~[sub];
202 while i < queue.len() {
203 match self.free_region_map.find(&queue[i]) {
205 for parents.each |parent| {
210 if !queue.contains(parent) {
222 fn is_subregion_of(&self,
223 sub_region: ty::Region,
224 super_region: ty::Region) -> bool
227 * Determines whether one region is a subregion of another. This is
228 * intended to run *after inference* and sadly the logic is somewhat
229 * duplicated with the code in infer.rs.
232 debug!("is_subregion_of(sub_region=%?, super_region=%?)",
233 sub_region, super_region);
235 sub_region == super_region || {
236 match (sub_region, super_region) {
237 (_, ty::re_static) => {
241 (ty::re_scope(sub_scope), ty::re_scope(super_scope)) => {
242 self.is_sub_scope(sub_scope, super_scope)
245 (ty::re_scope(sub_scope), ty::re_free(ref fr)) => {
246 self.is_sub_scope(sub_scope, fr.scope_id)
249 (ty::re_free(sub_fr), ty::re_free(super_fr)) => {
250 self.sub_free_region(sub_fr, super_fr)
260 fn nearest_common_ancestor(&self,
261 scope_a: ast::node_id,
262 scope_b: ast::node_id) -> Option<ast::node_id>
265 * Finds the nearest common ancestor (if any) of two scopes. That
266 * is, finds the smallest scope which is greater than or equal to
267 * both `scope_a` and `scope_b`.
270 if scope_a == scope_b { return Some(scope_a); }
272 let a_ancestors = ancestors_of(self, scope_a);
273 let b_ancestors = ancestors_of(self, scope_b);
274 let mut a_index = vec::len(a_ancestors) - 1u;
275 let mut b_index = vec::len(b_ancestors) - 1u;
277 // Here, ~[ab]_ancestors is a vector going from narrow to broad.
278 // The end of each vector will be the item where the scope is
279 // defined; if there are any common ancestors, then the tails of
280 // the vector will be the same. So basically we want to walk
281 // backwards from the tail of each vector and find the first point
282 // where they diverge. If one vector is a suffix of the other,
283 // then the corresponding scope is a superscope of the other.
285 if a_ancestors[a_index] != b_ancestors[b_index] {
290 // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
291 // for all indices between a_index and the end of the array
292 if a_index == 0u { return Some(scope_a); }
293 if b_index == 0u { return Some(scope_b); }
296 if a_ancestors[a_index] != b_ancestors[b_index] {
297 return Some(a_ancestors[a_index + 1u]);
301 fn ancestors_of(self: &RegionMaps, scope: ast::node_id)
304 let mut result = ~[scope];
305 let mut scope = scope;
307 match self.scope_map.find(&scope) {
308 None => return result,
309 Some(&superscope) => {
310 result.push(superscope);
319 /// Extracts that current parent from cx, failing if there is none.
320 pub fn parent_id(cx: ctxt, span: span) -> ast::node_id {
323 cx.sess.span_bug(span, ~"crate should not be parent here");
331 /// Records the current parent (if any) as the parent of `child_id`.
332 pub fn record_parent(cx: ctxt, child_id: ast::node_id) {
333 for cx.parent.each |parent_id| {
334 cx.region_maps.record_parent(child_id, *parent_id);
338 pub fn resolve_block(blk: &ast::blk, cx: ctxt, visitor: visit::vt<ctxt>) {
339 // Record the parent of this block.
340 record_parent(cx, blk.node.id);
343 let new_cx: ctxt = ctxt {parent: Some(blk.node.id),.. cx};
344 visit::visit_block(blk, new_cx, visitor);
347 pub fn resolve_arm(arm: &ast::arm, cx: ctxt, visitor: visit::vt<ctxt>) {
348 visit::visit_arm(arm, cx, visitor);
351 pub fn resolve_pat(pat: @ast::pat, cx: ctxt, visitor: visit::vt<ctxt>) {
353 ast::pat_ident(*) => {
354 let defn_opt = cx.def_map.find(&pat.id);
356 Some(&ast::def_variant(_,_)) => {
357 /* Nothing to do; this names a variant. */
360 /* This names a local. Bind it to the containing scope. */
361 record_parent(cx, pat.id);
368 visit::visit_pat(pat, cx, visitor);
371 pub fn resolve_stmt(stmt: @ast::stmt, cx: ctxt, visitor: visit::vt<ctxt>) {
373 ast::stmt_decl(*) => {
374 visit::visit_stmt(stmt, cx, visitor);
376 // This code has to be kept consistent with trans::base::trans_stmt
377 ast::stmt_expr(_, stmt_id) |
378 ast::stmt_semi(_, stmt_id) => {
379 record_parent(cx, stmt_id);
380 let mut expr_cx = cx;
381 expr_cx.parent = Some(stmt_id);
382 visit::visit_stmt(stmt, expr_cx, visitor);
384 ast::stmt_mac(*) => cx.sess.bug(~"unexpanded macro")
388 pub fn resolve_expr(expr: @ast::expr, cx: ctxt, visitor: visit::vt<ctxt>) {
389 record_parent(cx, expr.id);
393 // Calls or overloadable operators
395 // ast::expr_index(*) | ast::expr_binary(*) |
396 // ast::expr_unary(*) |
397 ast::expr_call(*) | ast::expr_method_call(*) => {
398 debug!("node %d: %s", expr.id, pprust::expr_to_str(expr,
400 new_cx.parent = Some(expr.id);
402 ast::expr_match(*) => {
403 debug!("node %d: %s", expr.id, pprust::expr_to_str(expr,
405 new_cx.parent = Some(expr.id);
407 ast::expr_while(cond, _) => {
408 new_cx.root_exprs.insert(cond.id);
413 if new_cx.root_exprs.contains(&expr.id) {
414 new_cx.parent = Some(expr.id);
417 visit::visit_expr(expr, new_cx, visitor);
420 pub fn resolve_local(local: @ast::local,
422 visitor: visit::vt<ctxt>) {
423 record_parent(cx, local.node.id);
424 visit::visit_local(local, cx, visitor);
427 pub fn resolve_item(item: @ast::item, cx: ctxt, visitor: visit::vt<ctxt>) {
428 // Items create a new outer block scope as far as we're concerned.
429 let new_cx: ctxt = ctxt {parent: None,.. cx};
430 visit::visit_item(item, new_cx, visitor);
433 pub fn resolve_fn(fk: &visit::fn_kind,
439 visitor: visit::vt<ctxt>) {
440 let fn_cx = match *fk {
441 visit::fk_item_fn(*) | visit::fk_method(*) => {
442 // Top-level functions are a root scope.
443 ctxt {parent: Some(id),.. cx}
446 visit::fk_anon(*) | visit::fk_fn_block(*) => {
447 // Closures continue with the inherited scope.
452 // Record the ID of `self`.
454 visit::fk_method(_, _, method) => {
455 cx.region_maps.record_parent(method.self_id, body.node.id);
460 debug!("visiting fn with body %d. cx.parent: %? \
462 body.node.id, cx.parent, fn_cx.parent);
464 for decl.inputs.each |input| {
465 cx.region_maps.record_parent(input.id, body.node.id);
468 visit::visit_fn(fk, decl, body, sp, id, fn_cx, visitor);
471 pub fn resolve_crate(sess: Session,
472 def_map: resolve::DefMap,
473 crate: @ast::crate) -> @mut RegionMaps
475 let region_maps = @mut RegionMaps {
476 scope_map: HashMap::new(),
477 free_region_map: HashMap::new()
479 let cx: ctxt = ctxt {sess: sess,
481 region_maps: region_maps,
482 root_exprs: @mut HashSet::new(),
484 let visitor = visit::mk_vt(@visit::Visitor {
485 visit_block: resolve_block,
486 visit_item: resolve_item,
487 visit_fn: resolve_fn,
488 visit_arm: resolve_arm,
489 visit_pat: resolve_pat,
490 visit_stmt: resolve_stmt,
491 visit_expr: resolve_expr,
492 visit_local: resolve_local,
493 .. *visit::default_visitor()
495 visit::visit_crate(crate, cx, visitor);
499 // ___________________________________________________________________________
500 // Determining region parameterization
502 // Infers which type defns must be region parameterized---this is done
503 // by scanning their contents to see whether they reference a region
504 // type, directly or indirectly. This is a fixed-point computation.
506 // We do it in two passes. First we walk the AST and construct a map
507 // from each type defn T1 to other defns which make use of it. For example,
508 // if we have a type like:
513 // Then there would be a map entry from S to T. During the same walk,
514 // we also construct add any types that reference regions to a set and
515 // a worklist. We can then process the worklist, propagating indirect
516 // dependencies until a fixed point is reached.
518 pub type region_paramd_items = @mut HashMap<ast::node_id, region_variance>;
521 pub struct region_dep {
522 ambient_variance: region_variance,
526 pub type dep_map = @mut HashMap<ast::node_id, @mut ~[region_dep]>;
528 pub struct DetermineRpCtxt {
530 ast_map: ast_map::map,
531 def_map: resolve::DefMap,
532 region_paramd_items: region_paramd_items,
534 worklist: ~[ast::node_id],
536 // the innermost enclosing item id
537 item_id: ast::node_id,
539 // true when we are within an item but not within a method.
540 // see long discussion on region_is_relevant().
541 anon_implies_rp: bool,
543 // encodes the context of the current type; invariant if
544 // mutable, covariant otherwise
545 ambient_variance: region_variance,
548 pub fn join_variance(variance1: region_variance,
549 variance2: region_variance)
551 match (variance1, variance2) {
552 (rv_invariant, _) => {rv_invariant}
553 (_, rv_invariant) => {rv_invariant}
554 (rv_covariant, rv_contravariant) => {rv_invariant}
555 (rv_contravariant, rv_covariant) => {rv_invariant}
556 (rv_covariant, rv_covariant) => {rv_covariant}
557 (rv_contravariant, rv_contravariant) => {rv_contravariant}
561 /// Combines the ambient variance with the variance of a
562 /// particular site to yield the final variance of the reference.
564 /// Example: if we are checking function arguments then the ambient
565 /// variance is contravariant. If we then find a `&'r T` pointer, `r`
566 /// appears in a co-variant position. This implies that this
567 /// occurrence of `r` is contra-variant with respect to the current
568 /// item, and hence the function returns `rv_contravariant`.
569 pub fn add_variance(ambient_variance: region_variance,
570 variance: region_variance)
572 match (ambient_variance, variance) {
573 (rv_invariant, _) => rv_invariant,
574 (_, rv_invariant) => rv_invariant,
575 (rv_covariant, c) => c,
576 (c, rv_covariant) => c,
577 (rv_contravariant, rv_contravariant) => rv_covariant
581 pub impl DetermineRpCtxt {
582 fn add_variance(&self, variance: region_variance) -> region_variance {
583 add_variance(self.ambient_variance, variance)
586 /// Records that item `id` is region-parameterized with the
587 /// variance `variance`. If `id` was already parameterized, then
588 /// the new variance is joined with the old variance.
589 fn add_rp(&mut self, id: ast::node_id, variance: region_variance) {
591 let old_variance = self.region_paramd_items.find(&id).
593 let joined_variance = match old_variance {
595 Some(v) => join_variance(v, variance)
598 debug!("add_rp() variance for %s: %? == %? ^ %?",
599 ast_map::node_id_to_str(self.ast_map, id,
600 self.sess.parse_sess.interner),
601 joined_variance, old_variance, variance);
603 if Some(joined_variance) != old_variance {
604 let region_paramd_items = self.region_paramd_items;
605 region_paramd_items.insert(id, joined_variance);
606 self.worklist.push(id);
610 /// Indicates that the region-parameterization of the current item
611 /// is dependent on the region-parameterization of the item
612 /// `from`. Put another way, it indicates that the current item
613 /// contains a value of type `from`, so if `from` is
614 /// region-parameterized, so is the current item.
615 fn add_dep(&mut self, from: ast::node_id) {
616 debug!("add dependency from %d -> %d (%s -> %s) with variance %?",
618 ast_map::node_id_to_str(self.ast_map, from,
619 self.sess.parse_sess.interner),
620 ast_map::node_id_to_str(self.ast_map, self.item_id,
621 self.sess.parse_sess.interner),
622 copy self.ambient_variance);
623 let vec = match self.dep_map.find(&from) {
627 let dep_map = self.dep_map;
628 dep_map.insert(from, vec);
632 let dep = region_dep {
633 ambient_variance: self.ambient_variance,
636 if !vec.contains(&dep) { vec.push(dep); }
639 // Determines whether a reference to a region that appears in the
640 // AST implies that the enclosing type is region-parameterized (RP).
641 // This point is subtle. Here are some examples to make it more
644 // 1. impl foo for &int { ... }
645 // 2. impl foo for &'self int { ... }
646 // 3. impl foo for bar { fn m(@self) -> &'self int { ... } }
647 // 4. impl foo for bar { fn m(&self) -> &'self int { ... } }
648 // 5. impl foo for bar { fn m(&self) -> &int { ... } }
650 // In case 1, the anonymous region is being referenced,
651 // but it appears in a context where the anonymous region
652 // resolves to self, so the impl foo is RP.
654 // In case 2, the self parameter is written explicitly.
656 // In case 3, the method refers to the region `self`, so that
657 // implies that the impl must be region parameterized. (If the
658 // type bar is not region parameterized, that is an error, because
659 // the self region is effectively unconstrained, but that is
660 // detected elsewhere).
662 // In case 4, the method refers to the region `self`, but the
663 // `self` region is bound by the `&self` receiver, and so this
664 // does not require that `bar` be RP.
666 // In case 5, the anonymous region is referenced, but it
667 // bound by the method, so it does not refer to self. This impl
668 // need not be region parameterized.
670 // Normally, & or &self implies that the enclosing item is RP.
671 // However, within a function, & is always bound. Within a method
672 // with &self type, &self is also bound. We detect those last two
673 // cases via flags (anon_implies_rp and self_implies_rp) that are
674 // true when the anon or self region implies RP.
675 fn region_is_relevant(&self, r: Option<@ast::Lifetime>) -> bool {
680 Some(ref l) if l.ident == special_idents::static => {
683 Some(ref l) if l.ident == special_idents::self_ => {
693 item_id: ast::node_id,
694 anon_implies_rp: bool,
696 let old_item_id = self.item_id;
697 let old_anon_implies_rp = self.anon_implies_rp;
698 self.item_id = item_id;
699 self.anon_implies_rp = anon_implies_rp;
700 debug!("with_item_id(%d, %b)",
703 let _i = ::util::common::indenter();
705 self.item_id = old_item_id;
706 self.anon_implies_rp = old_anon_implies_rp;
709 fn with_ambient_variance(@mut self, variance: region_variance, f: &fn()) {
710 let old_ambient_variance = self.ambient_variance;
711 self.ambient_variance = self.add_variance(variance);
713 self.ambient_variance = old_ambient_variance;
717 pub fn determine_rp_in_item(item: @ast::item,
718 cx: @mut DetermineRpCtxt,
719 visitor: visit::vt<@mut DetermineRpCtxt>) {
720 do cx.with(item.id, true) {
721 visit::visit_item(item, cx, visitor);
725 pub fn determine_rp_in_fn(fk: &visit::fn_kind,
730 cx: @mut DetermineRpCtxt,
731 visitor: visit::vt<@mut DetermineRpCtxt>) {
732 do cx.with(cx.item_id, false) {
733 do cx.with_ambient_variance(rv_contravariant) {
734 for decl.inputs.each |a| {
735 (visitor.visit_ty)(a.ty, cx, visitor);
738 (visitor.visit_ty)(decl.output, cx, visitor);
739 let generics = visit::generics_of_fn(fk);
740 (visitor.visit_generics)(&generics, cx, visitor);
741 (visitor.visit_block)(body, cx, visitor);
745 pub fn determine_rp_in_ty_method(ty_m: &ast::ty_method,
746 cx: @mut DetermineRpCtxt,
747 visitor: visit::vt<@mut DetermineRpCtxt>) {
748 do cx.with(cx.item_id, false) {
749 visit::visit_ty_method(ty_m, cx, visitor);
753 pub fn determine_rp_in_ty(ty: @ast::Ty,
754 cx: @mut DetermineRpCtxt,
755 visitor: visit::vt<@mut DetermineRpCtxt>) {
756 // we are only interested in types that will require an item to
757 // be region-parameterized. if cx.item_id is zero, then this type
758 // is not a member of a type defn nor is it a constitutent of an
759 // impl etc. So we can ignore it and its components.
760 if cx.item_id == 0 { return; }
762 // if this type directly references a region pointer like &'r ty,
763 // add to the worklist/set. Note that &'r ty is contravariant with
764 // respect to &r, because &'r ty can be used whereever a *smaller*
765 // region is expected (and hence is a supertype of those
769 ast::ty_rptr(r, _) => {
770 debug!("referenced rptr type %s",
771 pprust::ty_to_str(ty, sess.intr()));
773 if cx.region_is_relevant(r) {
774 cx.add_rp(cx.item_id, cx.add_variance(rv_contravariant))
778 ast::ty_closure(ref f) => {
779 debug!("referenced fn type: %s",
780 pprust::ty_to_str(ty, sess.intr()));
783 if cx.region_is_relevant(f.region) {
784 cx.add_rp(cx.item_id,
785 cx.add_variance(rv_contravariant))
789 if f.sigil == ast::BorrowedSigil && cx.anon_implies_rp {
790 cx.add_rp(cx.item_id,
791 cx.add_variance(rv_contravariant));
800 // if this references another named type, add the dependency
801 // to the dep_map. If the type is not defined in this crate,
802 // then check whether it is region-parameterized and consider
803 // that as a direct dependency.
805 ast::ty_path(path, id) => {
806 match cx.def_map.find(&id) {
807 Some(&ast::def_ty(did)) |
808 Some(&ast::def_trait(did)) |
809 Some(&ast::def_struct(did)) => {
810 if did.crate == ast::local_crate {
811 if cx.region_is_relevant(path.rp) {
812 cx.add_dep(did.node);
815 let cstore = sess.cstore;
816 match csearch::get_region_param(cstore, did) {
819 debug!("reference to external, rp'd type %s",
820 pprust::ty_to_str(ty, sess.intr()));
821 if cx.region_is_relevant(path.rp) {
822 cx.add_rp(cx.item_id, cx.add_variance(variance))
835 ast::ty_box(mt) | ast::ty_uniq(mt) | ast::ty_vec(mt) |
836 ast::ty_rptr(_, mt) | ast::ty_ptr(mt) => {
837 visit_mt(mt, cx, visitor);
840 ast::ty_path(path, _) => {
841 // type parameters are---for now, anyway---always invariant
842 do cx.with_ambient_variance(rv_invariant) {
843 for path.types.each |tp| {
844 (visitor.visit_ty)(*tp, cx, visitor);
849 ast::ty_closure(@ast::TyClosure {decl: ref decl, _}) |
850 ast::ty_bare_fn(@ast::TyBareFn {decl: ref decl, _}) => {
851 // fn() binds the & region, so do not consider &T types that
852 // appear *inside* a fn() type to affect the enclosing item:
853 do cx.with(cx.item_id, false) {
854 // parameters are contravariant
855 do cx.with_ambient_variance(rv_contravariant) {
856 for decl.inputs.each |a| {
857 (visitor.visit_ty)(a.ty, cx, visitor);
860 (visitor.visit_ty)(decl.output, cx, visitor);
865 visit::visit_ty(ty, cx, visitor);
869 fn visit_mt(mt: ast::mt,
870 cx: @mut DetermineRpCtxt,
871 visitor: visit::vt<@mut DetermineRpCtxt>) {
872 // mutability is invariant
873 if mt.mutbl == ast::m_mutbl {
874 do cx.with_ambient_variance(rv_invariant) {
875 (visitor.visit_ty)(mt.ty, cx, visitor);
878 (visitor.visit_ty)(mt.ty, cx, visitor);
883 pub fn determine_rp_in_struct_field(
884 cm: @ast::struct_field,
885 cx: @mut DetermineRpCtxt,
886 visitor: visit::vt<@mut DetermineRpCtxt>) {
888 ast::named_field(_, ast::struct_mutable, _) => {
889 do cx.with_ambient_variance(rv_invariant) {
890 visit::visit_struct_field(cm, cx, visitor);
893 ast::named_field(_, ast::struct_immutable, _) |
894 ast::unnamed_field => {
895 visit::visit_struct_field(cm, cx, visitor);
900 pub fn determine_rp_in_crate(sess: Session,
901 ast_map: ast_map::map,
902 def_map: resolve::DefMap,
904 -> region_paramd_items {
905 let cx = @mut DetermineRpCtxt {
909 region_paramd_items: @mut HashMap::new(),
910 dep_map: @mut HashMap::new(),
913 anon_implies_rp: false,
914 ambient_variance: rv_covariant
917 // Gather up the base set, worklist and dep_map
918 let visitor = visit::mk_vt(@visit::Visitor {
919 visit_fn: determine_rp_in_fn,
920 visit_item: determine_rp_in_item,
921 visit_ty: determine_rp_in_ty,
922 visit_ty_method: determine_rp_in_ty_method,
923 visit_struct_field: determine_rp_in_struct_field,
924 .. *visit::default_visitor()
926 visit::visit_crate(crate, cx, visitor);
928 // Propagate indirect dependencies
930 // Each entry in the worklist is the id of an item C whose region
931 // parameterization has been updated. So we pull ids off of the
932 // worklist, find the current variance, and then iterate through
933 // all of the dependent items (that is, those items that reference
934 // C). For each dependent item D, we combine the variance of C
935 // with the ambient variance where the reference occurred and then
936 // update the region-parameterization of D to reflect the result.
939 while cx.worklist.len() != 0 {
940 let c_id = cx.worklist.pop();
941 let c_variance = *cx.region_paramd_items.get(&c_id);
942 debug!("popped %d from worklist", c_id);
943 match cx.dep_map.find(&c_id) {
946 for deps.each |dep| {
947 let v = add_variance(dep.ambient_variance, c_variance);
948 cx.add_rp(dep.id, v);
956 debug!("Region variance results:");
957 let region_paramd_items = cx.region_paramd_items;
958 for region_paramd_items.each |&key, &value| {
959 debug!("item %? (%s) is parameterized with variance %?",
961 ast_map::node_id_to_str(ast_map, key,
962 sess.parse_sess.interner),
969 return cx.region_paramd_items;