]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | use crate::infer::outlives::free_region_map::FreeRegionMap; |
2 | use crate::infer::{GenericKind, InferCtxt}; | |
3 | use crate::hir; | |
0bf4aa26 | 4 | use rustc_data_structures::fx::FxHashMap; |
abe05a73 | 5 | use syntax_pos::Span; |
9fa01778 XL |
6 | use crate::traits::query::outlives_bounds::{self, OutlivesBound}; |
7 | use crate::ty::{self, Ty}; | |
abe05a73 XL |
8 | |
9 | /// The `OutlivesEnvironment` collects information about what outlives | |
10 | /// what in a given type-checking setting. For example, if we have a | |
11 | /// where-clause like `where T: 'a` in scope, then the | |
12 | /// `OutlivesEnvironment` would record that (in its | |
13 | /// `region_bound_pairs` field). Similarly, it contains methods for | |
14 | /// processing and adding implied bounds into the outlives | |
15 | /// environment. | |
16 | /// | |
17 | /// Other code at present does not typically take a | |
18 | /// `&OutlivesEnvironment`, but rather takes some of its fields (e.g., | |
19 | /// `process_registered_region_obligations` wants the | |
20 | /// region-bound-pairs). There is no mistaking it: the current setup | |
21 | /// of tracking region information is quite scattered! The | |
22 | /// `OutlivesEnvironment`, for example, needs to sometimes be combined | |
23 | /// with the `middle::RegionRelations`, to yield a full picture of how | |
24 | /// (lexical) lifetimes interact. However, I'm reluctant to do more | |
25 | /// refactoring here, since the setup with NLL is quite different. | |
26 | /// For example, NLL has no need of `RegionRelations`, and is solely | |
27 | /// interested in the `OutlivesEnvironment`. -nmatsakis | |
28 | #[derive(Clone)] | |
29 | pub struct OutlivesEnvironment<'tcx> { | |
416331ca | 30 | pub param_env: ty::ParamEnv<'tcx>, |
abe05a73 | 31 | free_region_map: FreeRegionMap<'tcx>, |
0bf4aa26 XL |
32 | |
33 | // Contains, for each body B that we are checking (that is, the fn | |
34 | // item, but also any nested closures), the set of implied region | |
35 | // bounds that are in scope in that particular body. | |
36 | // | |
37 | // Example: | |
38 | // | |
39 | // ``` | |
40 | // fn foo<'a, 'b, T>(x: &'a T, y: &'b ()) { | |
41 | // bar(x, y, |y: &'b T| { .. } // body B1) | |
42 | // } // body B0 | |
43 | // ``` | |
44 | // | |
45 | // Here, for body B0, the list would be `[T: 'a]`, because we | |
46 | // infer that `T` must outlive `'a` from the implied bounds on the | |
47 | // fn declaration. | |
48 | // | |
49 | // For the body B1, the list would be `[T: 'a, T: 'b]`, because we | |
50 | // also can see that -- within the closure body! -- `T` must | |
51 | // outlive `'b`. This is not necessarily true outside the closure | |
52 | // body, since the closure may never be called. | |
53 | // | |
54 | // We collect this map as we descend the tree. We then use the | |
55 | // results when proving outlives obligations like `T: 'x` later | |
56 | // (e.g., if `T: 'x` must be proven within the body B1, then we | |
57 | // know it is true if either `'a: 'x` or `'b: 'x`). | |
9fa01778 | 58 | region_bound_pairs_map: FxHashMap<hir::HirId, RegionBoundPairs<'tcx>>, |
0bf4aa26 XL |
59 | |
60 | // Used to compute `region_bound_pairs_map`: contains the set of | |
61 | // in-scope region-bound pairs thus far. | |
62 | region_bound_pairs_accum: RegionBoundPairs<'tcx>, | |
abe05a73 XL |
63 | } |
64 | ||
0bf4aa26 | 65 | /// "Region-bound pairs" tracks outlives relations that are known to |
9fa01778 | 66 | /// be true, either because of explicit where-clauses like `T: 'a` or |
0bf4aa26 XL |
67 | /// because of implied bounds. |
68 | pub type RegionBoundPairs<'tcx> = Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>; | |
69 | ||
dc9dc135 | 70 | impl<'a, 'tcx> OutlivesEnvironment<'tcx> { |
abe05a73 | 71 | pub fn new(param_env: ty::ParamEnv<'tcx>) -> Self { |
ff7c6d11 | 72 | let mut env = OutlivesEnvironment { |
abe05a73 | 73 | param_env, |
0bf4aa26 XL |
74 | free_region_map: Default::default(), |
75 | region_bound_pairs_map: Default::default(), | |
76 | region_bound_pairs_accum: vec![], | |
ff7c6d11 XL |
77 | }; |
78 | ||
8faf50e0 | 79 | env.add_outlives_bounds(None, outlives_bounds::explicit_outlives_bounds(param_env)); |
ff7c6d11 XL |
80 | |
81 | env | |
abe05a73 XL |
82 | } |
83 | ||
84 | /// Borrows current value of the `free_region_map`. | |
85 | pub fn free_region_map(&self) -> &FreeRegionMap<'tcx> { | |
86 | &self.free_region_map | |
87 | } | |
88 | ||
89 | /// Borrows current value of the `region_bound_pairs`. | |
9fa01778 | 90 | pub fn region_bound_pairs_map(&self) -> &FxHashMap<hir::HirId, RegionBoundPairs<'tcx>> { |
0bf4aa26 | 91 | &self.region_bound_pairs_map |
abe05a73 XL |
92 | } |
93 | ||
94 | /// Returns ownership of the `free_region_map`. | |
95 | pub fn into_free_region_map(self) -> FreeRegionMap<'tcx> { | |
96 | self.free_region_map | |
97 | } | |
98 | ||
99 | /// This is a hack to support the old-skool regionck, which | |
100 | /// processes region constraints from the main function and the | |
101 | /// closure together. In that context, when we enter a closure, we | |
102 | /// want to be able to "save" the state of the surrounding a | |
103 | /// function. We can then add implied bounds and the like from the | |
104 | /// closure arguments into the environment -- these should only | |
105 | /// apply in the closure body, so once we exit, we invoke | |
106 | /// `pop_snapshot_post_closure` to remove them. | |
107 | /// | |
108 | /// Example: | |
109 | /// | |
110 | /// ``` | |
111 | /// fn foo<T>() { | |
112 | /// callback(for<'a> |x: &'a T| { | |
113 | /// // ^^^^^^^ not legal syntax, but probably should be | |
114 | /// // within this closure body, `T: 'a` holds | |
115 | /// }) | |
116 | /// } | |
117 | /// ``` | |
118 | /// | |
119 | /// This "containment" of closure's effects only works so well. In | |
120 | /// particular, we (intentionally) leak relationships between free | |
121 | /// regions that are created by the closure's bounds. The case | |
122 | /// where this is useful is when you have (e.g.) a closure with a | |
123 | /// signature like `for<'a, 'b> fn(x: &'a &'b u32)` -- in this | |
124 | /// case, we want to keep the relationship `'b: 'a` in the | |
125 | /// free-region-map, so that later if we have to take `LUB('b, | |
126 | /// 'a)` we can get the result `'b`. | |
127 | /// | |
128 | /// I have opted to keep **all modifications** to the | |
129 | /// free-region-map, however, and not just those that concern free | |
130 | /// variables bound in the closure. The latter seems more correct, | |
131 | /// but it is not the existing behavior, and I could not find a | |
132 | /// case where the existing behavior went wrong. In any case, it | |
133 | /// seems like it'd be readily fixed if we wanted. There are | |
134 | /// similar leaks around givens that seem equally suspicious, to | |
135 | /// be honest. --nmatsakis | |
136 | pub fn push_snapshot_pre_closure(&self) -> usize { | |
0bf4aa26 | 137 | self.region_bound_pairs_accum.len() |
abe05a73 XL |
138 | } |
139 | ||
140 | /// See `push_snapshot_pre_closure`. | |
141 | pub fn pop_snapshot_post_closure(&mut self, len: usize) { | |
0bf4aa26 | 142 | self.region_bound_pairs_accum.truncate(len); |
abe05a73 XL |
143 | } |
144 | ||
145 | /// This method adds "implied bounds" into the outlives environment. | |
146 | /// Implied bounds are outlives relationships that we can deduce | |
147 | /// on the basis that certain types must be well-formed -- these are | |
148 | /// either the types that appear in the function signature or else | |
149 | /// the input types to an impl. For example, if you have a function | |
150 | /// like | |
151 | /// | |
152 | /// ``` | |
153 | /// fn foo<'a, 'b, T>(x: &'a &'b [T]) { } | |
154 | /// ``` | |
155 | /// | |
156 | /// we can assume in the caller's body that `'b: 'a` and that `T: | |
157 | /// 'b` (and hence, transitively, that `T: 'a`). This method would | |
158 | /// add those assumptions into the outlives-environment. | |
159 | /// | |
160 | /// Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs` | |
161 | pub fn add_implied_bounds( | |
162 | &mut self, | |
dc9dc135 | 163 | infcx: &InferCtxt<'a, 'tcx>, |
abe05a73 | 164 | fn_sig_tys: &[Ty<'tcx>], |
9fa01778 | 165 | body_id: hir::HirId, |
abe05a73 XL |
166 | span: Span, |
167 | ) { | |
168 | debug!("add_implied_bounds()"); | |
169 | ||
170 | for &ty in fn_sig_tys { | |
dc9dc135 | 171 | let ty = infcx.resolve_vars_if_possible(&ty); |
abe05a73 | 172 | debug!("add_implied_bounds: ty = {}", ty); |
ff7c6d11 XL |
173 | let implied_bounds = infcx.implied_outlives_bounds(self.param_env, body_id, ty, span); |
174 | self.add_outlives_bounds(Some(infcx), implied_bounds) | |
abe05a73 XL |
175 | } |
176 | } | |
177 | ||
0bf4aa26 | 178 | /// Save the current set of region-bound pairs under the given `body_id`. |
9fa01778 | 179 | pub fn save_implied_bounds(&mut self, body_id: hir::HirId) { |
0bf4aa26 XL |
180 | let old = self.region_bound_pairs_map.insert( |
181 | body_id, | |
182 | self.region_bound_pairs_accum.clone(), | |
183 | ); | |
184 | assert!(old.is_none()); | |
185 | } | |
186 | ||
ff7c6d11 XL |
187 | /// Processes outlives bounds that are known to hold, whether from implied or other sources. |
188 | /// | |
189 | /// The `infcx` parameter is optional; if the implied bounds may | |
190 | /// contain inference variables, it must be supplied, in which | |
191 | /// case we will register "givens" on the inference context. (See | |
192 | /// `RegionConstraintData`.) | |
dc9dc135 XL |
193 | fn add_outlives_bounds<I>(&mut self, infcx: Option<&InferCtxt<'a, 'tcx>>, outlives_bounds: I) |
194 | where | |
ff7c6d11 XL |
195 | I: IntoIterator<Item = OutlivesBound<'tcx>>, |
196 | { | |
197 | // Record relationships such as `T:'x` that don't go into the | |
198 | // free-region-map but which we use here. | |
199 | for outlives_bound in outlives_bounds { | |
200 | debug!("add_outlives_bounds: outlives_bound={:?}", outlives_bound); | |
201 | match outlives_bound { | |
0bf4aa26 XL |
202 | OutlivesBound::RegionSubRegion(r_a @ &ty::ReEarlyBound(_), &ty::ReVar(vid_b)) |
203 | | OutlivesBound::RegionSubRegion(r_a @ &ty::ReFree(_), &ty::ReVar(vid_b)) => { | |
204 | infcx | |
205 | .expect("no infcx provided but region vars found") | |
206 | .add_given(r_a, vid_b); | |
abe05a73 | 207 | } |
ff7c6d11 | 208 | OutlivesBound::RegionSubParam(r_a, param_b) => { |
0bf4aa26 | 209 | self.region_bound_pairs_accum |
ff7c6d11 | 210 | .push((r_a, GenericKind::Param(param_b))); |
abe05a73 | 211 | } |
ff7c6d11 | 212 | OutlivesBound::RegionSubProjection(r_a, projection_b) => { |
0bf4aa26 | 213 | self.region_bound_pairs_accum |
ff7c6d11 XL |
214 | .push((r_a, GenericKind::Projection(projection_b))); |
215 | } | |
216 | OutlivesBound::RegionSubRegion(r_a, r_b) => { | |
217 | // In principle, we could record (and take | |
218 | // advantage of) every relationship here, but | |
219 | // we are also free not to -- it simply means | |
220 | // strictly less that we can successfully type | |
221 | // check. Right now we only look for things | |
222 | // relationships between free regions. (It may | |
223 | // also be that we should revise our inference | |
224 | // system to be more general and to make use | |
225 | // of *every* relationship that arises here, | |
226 | // but presently we do not.) | |
227 | self.free_region_map.relate_regions(r_a, r_b); | |
228 | } | |
229 | } | |
230 | } | |
abe05a73 XL |
231 | } |
232 | } |