]>
Commit | Line | Data |
---|---|---|
bd371182 AL |
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 | ||
e9174d1e SL |
11 | //! This file handles the relationships between free regions -- |
12 | //! meaning lifetime parameters. Ordinarily, free regions are | |
b039eaaf | 13 | //! unrelated to one another, but they can be related via implied or |
e9174d1e SL |
14 | //! explicit bounds. In that case, we track the bounds using the |
15 | //! `TransitiveRelation` type and use that to decide when one free | |
16 | //! region outlives another and so forth. | |
bd371182 | 17 | |
54a0048b SL |
18 | use ty::{self, TyCtxt, FreeRegion, Region}; |
19 | use ty::wf::ImpliedBound; | |
e9174d1e | 20 | use rustc_data_structures::transitive_relation::TransitiveRelation; |
bd371182 | 21 | |
8bb4bdeb | 22 | #[derive(Clone, RustcEncodable, RustcDecodable)] |
bd371182 | 23 | pub struct FreeRegionMap { |
e9174d1e SL |
24 | // Stores the relation `a < b`, where `a` and `b` are regions. |
25 | relation: TransitiveRelation<Region> | |
bd371182 AL |
26 | } |
27 | ||
28 | impl FreeRegionMap { | |
29 | pub fn new() -> FreeRegionMap { | |
e9174d1e | 30 | FreeRegionMap { relation: TransitiveRelation::new() } |
bd371182 AL |
31 | } |
32 | ||
8bb4bdeb XL |
33 | pub fn is_empty(&self) -> bool { |
34 | self.relation.is_empty() | |
35 | } | |
36 | ||
e9174d1e SL |
37 | pub fn relate_free_regions_from_implied_bounds<'tcx>(&mut self, |
38 | implied_bounds: &[ImpliedBound<'tcx>]) | |
bd371182 | 39 | { |
e9174d1e SL |
40 | debug!("relate_free_regions_from_implied_bounds()"); |
41 | for implied_bound in implied_bounds { | |
42 | debug!("implied bound: {:?}", implied_bound); | |
43 | match *implied_bound { | |
9e0c209e | 44 | ImpliedBound::RegionSubRegion(&ty::ReFree(free_a), &ty::ReFree(free_b)) => { |
bd371182 AL |
45 | self.relate_free_regions(free_a, free_b); |
46 | } | |
e9174d1e SL |
47 | ImpliedBound::RegionSubRegion(..) | |
48 | ImpliedBound::RegionSubParam(..) | | |
49 | ImpliedBound::RegionSubProjection(..) => { | |
bd371182 AL |
50 | } |
51 | } | |
52 | } | |
53 | } | |
54 | ||
a7813a04 XL |
55 | pub fn relate_free_regions_from_predicates(&mut self, |
56 | predicates: &[ty::Predicate]) { | |
62682a34 | 57 | debug!("relate_free_regions_from_predicates(predicates={:?})", predicates); |
bd371182 AL |
58 | for predicate in predicates { |
59 | match *predicate { | |
60 | ty::Predicate::Projection(..) | | |
61 | ty::Predicate::Trait(..) | | |
62 | ty::Predicate::Equate(..) | | |
e9174d1e SL |
63 | ty::Predicate::WellFormed(..) | |
64 | ty::Predicate::ObjectSafe(..) | | |
a7813a04 | 65 | ty::Predicate::ClosureKind(..) | |
bd371182 AL |
66 | ty::Predicate::TypeOutlives(..) => { |
67 | // No region bounds here | |
68 | } | |
69 | ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => { | |
70 | match (r_a, r_b) { | |
9e0c209e SL |
71 | (&ty::ReStatic, &ty::ReFree(_)) => {}, |
72 | (&ty::ReFree(fr_a), &ty::ReStatic) => self.relate_to_static(fr_a), | |
73 | (&ty::ReFree(fr_a), &ty::ReFree(fr_b)) => { | |
bd371182 AL |
74 | // Record that `'a:'b`. Or, put another way, `'b <= 'a`. |
75 | self.relate_free_regions(fr_b, fr_a); | |
76 | } | |
77 | _ => { | |
78 | // All named regions are instantiated with free regions. | |
54a0048b SL |
79 | bug!("record_region_bounds: non free region: {:?} / {:?}", |
80 | r_a, | |
81 | r_b); | |
bd371182 AL |
82 | } |
83 | } | |
84 | } | |
85 | } | |
86 | } | |
87 | } | |
88 | ||
c1a9b12d | 89 | fn relate_to_static(&mut self, sup: FreeRegion) { |
e9174d1e | 90 | self.relation.add(ty::ReStatic, ty::ReFree(sup)); |
c1a9b12d SL |
91 | } |
92 | ||
93 | fn relate_free_regions(&mut self, sub: FreeRegion, sup: FreeRegion) { | |
e9174d1e | 94 | self.relation.add(ty::ReFree(sub), ty::ReFree(sup)) |
bd371182 AL |
95 | } |
96 | ||
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 { | |
e9174d1e SL |
102 | let result = sub == sup || { |
103 | let sub = ty::ReFree(sub); | |
104 | let sup = ty::ReFree(sup); | |
105 | self.relation.contains(&sub, &sup) || self.relation.contains(&ty::ReStatic, &sup) | |
106 | }; | |
107 | debug!("sub_free_region(sub={:?}, sup={:?}) = {:?}", sub, sup, result); | |
108 | result | |
109 | } | |
110 | ||
111 | pub fn lub_free_regions(&self, fr_a: FreeRegion, fr_b: FreeRegion) -> Region { | |
112 | let r_a = ty::ReFree(fr_a); | |
113 | let r_b = ty::ReFree(fr_b); | |
114 | let result = if fr_a == fr_b { r_a } else { | |
115 | match self.relation.postdom_upper_bound(&r_a, &r_b) { | |
116 | None => ty::ReStatic, | |
117 | Some(r) => *r, | |
118 | } | |
119 | }; | |
120 | debug!("lub_free_regions(fr_a={:?}, fr_b={:?}) = {:?}", fr_a, fr_b, result); | |
121 | result | |
bd371182 AL |
122 | } |
123 | ||
124 | /// Determines whether one region is a subregion of another. This is intended to run *after | |
125 | /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs. | |
126 | pub fn is_subregion_of(&self, | |
a7813a04 | 127 | tcx: TyCtxt, |
9e0c209e SL |
128 | sub_region: &ty::Region, |
129 | super_region: &ty::Region) | |
bd371182 | 130 | -> bool { |
e9174d1e | 131 | let result = sub_region == super_region || { |
bd371182 | 132 | match (sub_region, super_region) { |
9e0c209e SL |
133 | (&ty::ReEmpty, _) | |
134 | (_, &ty::ReStatic) => | |
bd371182 AL |
135 | true, |
136 | ||
9e0c209e | 137 | (&ty::ReScope(sub_scope), &ty::ReScope(super_scope)) => |
bd371182 AL |
138 | tcx.region_maps.is_subscope_of(sub_scope, super_scope), |
139 | ||
9e0c209e | 140 | (&ty::ReScope(sub_scope), &ty::ReFree(fr)) => |
e9174d1e SL |
141 | tcx.region_maps.is_subscope_of(sub_scope, fr.scope) || |
142 | self.is_static(fr), | |
bd371182 | 143 | |
9e0c209e | 144 | (&ty::ReFree(sub_fr), &ty::ReFree(super_fr)) => |
bd371182 AL |
145 | self.sub_free_region(sub_fr, super_fr), |
146 | ||
9e0c209e | 147 | (&ty::ReStatic, &ty::ReFree(sup_fr)) => |
e9174d1e | 148 | self.is_static(sup_fr), |
c1a9b12d | 149 | |
bd371182 AL |
150 | _ => |
151 | false, | |
152 | } | |
e9174d1e SL |
153 | }; |
154 | debug!("is_subregion_of(sub_region={:?}, super_region={:?}) = {:?}", | |
155 | sub_region, super_region, result); | |
156 | result | |
bd371182 | 157 | } |
bd371182 | 158 | |
c1a9b12d | 159 | /// Determines whether this free-region is required to be 'static |
e9174d1e | 160 | pub fn is_static(&self, super_region: ty::FreeRegion) -> bool { |
c1a9b12d | 161 | debug!("is_static(super_region={:?})", super_region); |
e9174d1e | 162 | self.relation.contains(&ty::ReStatic, &ty::ReFree(super_region)) |
c1a9b12d SL |
163 | } |
164 | } | |
e9174d1e SL |
165 | |
166 | #[cfg(test)] | |
167 | fn free_region(index: u32) -> FreeRegion { | |
168 | use middle::region::DUMMY_CODE_EXTENT; | |
169 | FreeRegion { scope: DUMMY_CODE_EXTENT, | |
170 | bound_region: ty::BoundRegion::BrAnon(index) } | |
171 | } | |
172 | ||
173 | #[test] | |
174 | fn lub() { | |
175 | // a very VERY basic test, but see the tests in | |
176 | // TransitiveRelation, which are much more thorough. | |
177 | let frs: Vec<_> = (0..3).map(|i| free_region(i)).collect(); | |
178 | let mut map = FreeRegionMap::new(); | |
179 | map.relate_free_regions(frs[0], frs[2]); | |
180 | map.relate_free_regions(frs[1], frs[2]); | |
181 | assert_eq!(map.lub_free_regions(frs[0], frs[1]), ty::ReFree(frs[2])); | |
182 | } |