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.
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 use middle::wf::ImpliedBound;
14 use middle::ty::{self, FreeRegion};
15 use util::common::can_reach;
16 use util::nodemap::{FnvHashMap, FnvHashSet};
19 pub struct FreeRegionMap {
20 /// `map` maps from a free region `a` to a list of
21 /// free regions `bs` such that `a <= b for all b in bs`
22 map: FnvHashMap<FreeRegion, Vec<FreeRegion>>,
23 /// regions that are required to outlive (and therefore be
24 /// equal to) 'static.
25 statics: FnvHashSet<FreeRegion>
29 pub fn new() -> FreeRegionMap {
30 FreeRegionMap { map: FnvHashMap(), statics: FnvHashSet() }
33 pub fn relate_free_regions_from_implied_bounds<'tcx>(&mut self,
34 implied_bounds: &[ImpliedBound<'tcx>])
36 debug!("relate_free_regions_from_implied_bounds()");
37 for implied_bound in implied_bounds {
38 debug!("implied bound: {:?}", implied_bound);
39 match *implied_bound {
40 ImpliedBound::RegionSubRegion(ty::ReFree(free_a), ty::ReFree(free_b)) => {
41 self.relate_free_regions(free_a, free_b);
43 ImpliedBound::RegionSubRegion(..) |
44 ImpliedBound::RegionSubParam(..) |
45 ImpliedBound::RegionSubProjection(..) => {
51 pub fn relate_free_regions_from_predicates<'tcx>(&mut self,
53 predicates: &[ty::Predicate<'tcx>]) {
54 debug!("relate_free_regions_from_predicates(predicates={:?})", predicates);
55 for predicate in predicates {
57 ty::Predicate::Projection(..) |
58 ty::Predicate::Trait(..) |
59 ty::Predicate::Equate(..) |
60 ty::Predicate::WellFormed(..) |
61 ty::Predicate::ObjectSafe(..) |
62 ty::Predicate::TypeOutlives(..) => {
63 // No region bounds here
65 ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
67 (ty::ReStatic, ty::ReFree(_)) => {},
68 (ty::ReFree(fr_a), ty::ReStatic) => self.relate_to_static(fr_a),
69 (ty::ReFree(fr_a), ty::ReFree(fr_b)) => {
70 // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
71 self.relate_free_regions(fr_b, fr_a);
74 // All named regions are instantiated with free regions.
76 &format!("record_region_bounds: non free region: {:?} / {:?}",
86 fn relate_to_static(&mut self, sup: FreeRegion) {
87 self.statics.insert(sup);
90 fn relate_free_regions(&mut self, sub: FreeRegion, sup: FreeRegion) {
91 let mut sups = self.map.entry(sub).or_insert(Vec::new());
92 if !sups.contains(&sup) {
97 /// Determines whether two free regions have a subregion relationship
98 /// by walking the graph encoded in `map`. Note that
99 /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
100 /// (that is, the user can give two different names to the same lifetime).
101 pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
102 can_reach(&self.map, sub, sup) || self.is_static(&sup)
105 /// Determines whether one region is a subregion of another. This is intended to run *after
106 /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
107 pub fn is_subregion_of(&self,
109 sub_region: ty::Region,
110 super_region: ty::Region)
112 debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
113 sub_region, super_region);
115 sub_region == super_region || {
116 match (sub_region, super_region) {
121 (ty::ReScope(sub_scope), ty::ReScope(super_scope)) =>
122 tcx.region_maps.is_subscope_of(sub_scope, super_scope),
124 (ty::ReScope(sub_scope), ty::ReFree(ref fr)) =>
125 tcx.region_maps.is_subscope_of(sub_scope, fr.scope.to_code_extent()),
127 (ty::ReFree(sub_fr), ty::ReFree(super_fr)) =>
128 self.sub_free_region(sub_fr, super_fr),
130 (ty::ReStatic, ty::ReFree(ref sup_fr)) => self.is_static(sup_fr),
138 /// Determines whether this free-region is required to be 'static
139 pub fn is_static(&self, super_region: &ty::FreeRegion) -> bool {
140 debug!("is_static(super_region={:?})", super_region);
141 self.statics.iter().any(|s| can_reach(&self.map, *s, *super_region))