]>
Commit | Line | Data |
---|---|---|
ff7c6d11 XL |
1 | // Copyright 2017 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 | //! Code to extract the universally quantified regions declared on a | |
12 | //! function and the relationships between them. For example: | |
13 | //! | |
14 | //! ``` | |
15 | //! fn foo<'a, 'b, 'c: 'b>() { } | |
16 | //! ``` | |
17 | //! | |
18 | //! here we would be returning a map assigning each of `{'a, 'b, 'c}` | |
19 | //! to an index, as well as the `FreeRegionMap` which can compute | |
20 | //! relationships between them. | |
21 | //! | |
22 | //! The code in this file doesn't *do anything* with those results; it | |
23 | //! just returns them for other code to use. | |
24 | ||
94b46f34 | 25 | use rustc::hir::{self, BodyOwnerKind, HirId}; |
ff7c6d11 XL |
26 | use rustc::hir::def_id::DefId; |
27 | use rustc::infer::{InferCtxt, NLLRegionVariableOrigin}; | |
28 | use rustc::infer::region_constraints::GenericKind; | |
29 | use rustc::infer::outlives::bounds::{self, OutlivesBound}; | |
30 | use rustc::infer::outlives::free_region_map::FreeRegionRelations; | |
94b46f34 | 31 | use rustc::ty::{self, RegionVid, Ty, TyCtxt, ClosureSubsts, GeneratorSubsts}; |
ff7c6d11 XL |
32 | use rustc::ty::fold::TypeFoldable; |
33 | use rustc::ty::subst::Substs; | |
34 | use rustc::util::nodemap::FxHashMap; | |
35 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; | |
36 | use rustc_data_structures::transitive_relation::TransitiveRelation; | |
37 | use std::iter; | |
38 | use syntax::ast; | |
39 | ||
40 | use super::ToRegionVid; | |
41 | ||
42 | #[derive(Debug)] | |
43 | pub struct UniversalRegions<'tcx> { | |
44 | indices: UniversalRegionIndices<'tcx>, | |
45 | ||
46 | /// The vid assigned to `'static` | |
47 | pub fr_static: RegionVid, | |
48 | ||
49 | /// A special region vid created to represent the current MIR fn | |
50 | /// body. It will outlive the entire CFG but it will not outlive | |
51 | /// any other universal regions. | |
52 | pub fr_fn_body: RegionVid, | |
53 | ||
54 | /// We create region variables such that they are ordered by their | |
55 | /// `RegionClassification`. The first block are globals, then | |
56 | /// externals, then locals. So things from: | |
57 | /// - `FIRST_GLOBAL_INDEX..first_extern_index` are global; | |
58 | /// - `first_extern_index..first_local_index` are external; and | |
59 | /// - first_local_index..num_universals` are local. | |
60 | first_extern_index: usize, | |
61 | ||
62 | /// See `first_extern_index`. | |
63 | first_local_index: usize, | |
64 | ||
65 | /// The total number of universal region variables instantiated. | |
66 | num_universals: usize, | |
67 | ||
68 | /// The "defining" type for this function, with all universal | |
69 | /// regions instantiated. For a closure or generator, this is the | |
70 | /// closure type, but for a top-level function it's the `TyFnDef`. | |
71 | pub defining_ty: DefiningTy<'tcx>, | |
72 | ||
73 | /// The return type of this function, with all regions replaced by | |
74 | /// their universal `RegionVid` equivalents. | |
75 | /// | |
76 | /// NB. Associated types in this type have not been normalized, | |
77 | /// as the name suggests. =) | |
78 | pub unnormalized_output_ty: Ty<'tcx>, | |
79 | ||
80 | /// The fully liberated input types of this function, with all | |
81 | /// regions replaced by their universal `RegionVid` equivalents. | |
82 | /// | |
83 | /// NB. Associated types in these types have not been normalized, | |
84 | /// as the name suggests. =) | |
85 | pub unnormalized_input_tys: &'tcx [Ty<'tcx>], | |
86 | ||
87 | /// Each RBP `('a, GK)` indicates that `GK: 'a` can be assumed to | |
88 | /// be true. These encode relationships like `T: 'a` that are | |
89 | /// added via implicit bounds. | |
90 | /// | |
91 | /// Each region here is guaranteed to be a key in the `indices` | |
92 | /// map. We use the "original" regions (i.e., the keys from the | |
93 | /// map, and not the values) because the code in | |
94 | /// `process_registered_region_obligations` has some special-cased | |
95 | /// logic expecting to see (e.g.) `ReStatic`, and if we supplied | |
96 | /// our special inference variable there, we would mess that up. | |
97 | pub region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>, | |
98 | ||
2c00a5a8 XL |
99 | pub yield_ty: Option<Ty<'tcx>>, |
100 | ||
ff7c6d11 XL |
101 | relations: UniversalRegionRelations, |
102 | } | |
103 | ||
104 | /// The "defining type" for this MIR. The key feature of the "defining | |
105 | /// type" is that it contains the information needed to derive all the | |
106 | /// universal regions that are in scope as well as the types of the | |
107 | /// inputs/output from the MIR. In general, early-bound universal | |
108 | /// regions appear free in the defining type and late-bound regions | |
109 | /// appear bound in the signature. | |
110 | #[derive(Copy, Clone, Debug)] | |
111 | pub enum DefiningTy<'tcx> { | |
112 | /// The MIR is a closure. The signature is found via | |
113 | /// `ClosureSubsts::closure_sig_ty`. | |
114 | Closure(DefId, ty::ClosureSubsts<'tcx>), | |
115 | ||
116 | /// The MIR is a generator. The signature is that generators take | |
117 | /// no parameters and return the result of | |
118 | /// `ClosureSubsts::generator_return_ty`. | |
94b46f34 | 119 | Generator(DefId, ty::GeneratorSubsts<'tcx>, hir::GeneratorMovability), |
ff7c6d11 XL |
120 | |
121 | /// The MIR is a fn item with the given def-id and substs. The signature | |
122 | /// of the function can be bound then with the `fn_sig` query. | |
123 | FnDef(DefId, &'tcx Substs<'tcx>), | |
124 | ||
125 | /// The MIR represents some form of constant. The signature then | |
126 | /// is that it has no inputs and a single return value, which is | |
127 | /// the value of the constant. | |
2c00a5a8 | 128 | Const(DefId, &'tcx Substs<'tcx>), |
ff7c6d11 XL |
129 | } |
130 | ||
131 | #[derive(Debug)] | |
132 | struct UniversalRegionIndices<'tcx> { | |
133 | /// For those regions that may appear in the parameter environment | |
134 | /// ('static and early-bound regions), we maintain a map from the | |
135 | /// `ty::Region` to the internal `RegionVid` we are using. This is | |
136 | /// used because trait matching and type-checking will feed us | |
137 | /// region constraints that reference those regions and we need to | |
138 | /// be able to map them our internal `RegionVid`. This is | |
139 | /// basically equivalent to a `Substs`, except that it also | |
140 | /// contains an entry for `ReStatic` -- it might be nice to just | |
141 | /// use a substs, and then handle `ReStatic` another way. | |
142 | indices: FxHashMap<ty::Region<'tcx>, RegionVid>, | |
143 | } | |
144 | ||
145 | #[derive(Debug)] | |
146 | struct UniversalRegionRelations { | |
147 | /// Stores the outlives relations that are known to hold from the | |
148 | /// implied bounds, in-scope where clauses, and that sort of | |
149 | /// thing. | |
150 | outlives: TransitiveRelation<RegionVid>, | |
151 | ||
152 | /// This is the `<=` relation; that is, if `a: b`, then `b <= a`, | |
153 | /// and we store that here. This is useful when figuring out how | |
154 | /// to express some local region in terms of external regions our | |
155 | /// caller will understand. | |
156 | inverse_outlives: TransitiveRelation<RegionVid>, | |
157 | } | |
158 | ||
159 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] | |
160 | pub enum RegionClassification { | |
161 | /// A **global** region is one that can be named from | |
162 | /// anywhere. There is only one, `'static`. | |
163 | Global, | |
164 | ||
165 | /// An **external** region is only relevant for closures. In that | |
166 | /// case, it refers to regions that are free in the closure type | |
167 | /// -- basically, something bound in the surrounding context. | |
168 | /// | |
169 | /// Consider this example: | |
170 | /// | |
171 | /// ``` | |
172 | /// fn foo<'a, 'b>(a: &'a u32, b: &'b u32, c: &'static u32) { | |
173 | /// let closure = for<'x> |x: &'x u32| { .. }; | |
174 | /// ^^^^^^^ pretend this were legal syntax | |
175 | /// for declaring a late-bound region in | |
176 | /// a closure signature | |
177 | /// } | |
178 | /// ``` | |
179 | /// | |
180 | /// Here, the lifetimes `'a` and `'b` would be **external** to the | |
181 | /// closure. | |
182 | /// | |
183 | /// If we are not analyzing a closure, there are no external | |
184 | /// lifetimes. | |
185 | External, | |
186 | ||
187 | /// A **local** lifetime is one about which we know the full set | |
188 | /// of relevant constraints (that is, relationships to other named | |
189 | /// regions). For a closure, this includes any region bound in | |
190 | /// the closure's signature. For a fn item, this includes all | |
191 | /// regions other than global ones. | |
192 | /// | |
193 | /// Continuing with the example from `External`, if we were | |
194 | /// analyzing the closure, then `'x` would be local (and `'a` and | |
195 | /// `'b` are external). If we are analyzing the function item | |
196 | /// `foo`, then `'a` and `'b` are local (and `'x` is not in | |
197 | /// scope). | |
198 | Local, | |
199 | } | |
200 | ||
201 | const FIRST_GLOBAL_INDEX: usize = 0; | |
202 | ||
203 | impl<'tcx> UniversalRegions<'tcx> { | |
204 | /// Creates a new and fully initialized `UniversalRegions` that | |
205 | /// contains indices for all the free regions found in the given | |
206 | /// MIR -- that is, all the regions that appear in the function's | |
207 | /// signature. This will also compute the relationships that are | |
208 | /// known between those regions. | |
209 | pub fn new( | |
210 | infcx: &InferCtxt<'_, '_, 'tcx>, | |
211 | mir_def_id: DefId, | |
212 | param_env: ty::ParamEnv<'tcx>, | |
213 | ) -> Self { | |
214 | let tcx = infcx.tcx; | |
215 | let mir_node_id = tcx.hir.as_local_node_id(mir_def_id).unwrap(); | |
216 | let mir_hir_id = tcx.hir.node_to_hir_id(mir_node_id); | |
217 | UniversalRegionsBuilder { | |
218 | infcx, | |
219 | mir_def_id, | |
220 | mir_node_id, | |
221 | mir_hir_id, | |
222 | param_env, | |
223 | region_bound_pairs: vec![], | |
224 | relations: UniversalRegionRelations { | |
225 | outlives: TransitiveRelation::new(), | |
226 | inverse_outlives: TransitiveRelation::new(), | |
227 | }, | |
228 | }.build() | |
229 | } | |
230 | ||
231 | /// Given a reference to a closure type, extracts all the values | |
232 | /// from its free regions and returns a vector with them. This is | |
233 | /// used when the closure's creator checks that the | |
234 | /// `ClosureRegionRequirements` are met. The requirements from | |
235 | /// `ClosureRegionRequirements` are expressed in terms of | |
236 | /// `RegionVid` entries that map into the returned vector `V`: so | |
237 | /// if the `ClosureRegionRequirements` contains something like | |
238 | /// `'1: '2`, then the caller would impose the constraint that | |
239 | /// `V[1]: V[2]`. | |
240 | pub fn closure_mapping( | |
241 | infcx: &InferCtxt<'_, '_, 'tcx>, | |
242 | closure_ty: Ty<'tcx>, | |
243 | expected_num_vars: usize, | |
244 | ) -> IndexVec<RegionVid, ty::Region<'tcx>> { | |
245 | let mut region_mapping = IndexVec::with_capacity(expected_num_vars); | |
246 | region_mapping.push(infcx.tcx.types.re_static); | |
247 | infcx.tcx.for_each_free_region(&closure_ty, |fr| { | |
248 | region_mapping.push(fr); | |
249 | }); | |
250 | ||
251 | assert_eq!( | |
252 | region_mapping.len(), | |
253 | expected_num_vars, | |
254 | "index vec had unexpected number of variables" | |
255 | ); | |
256 | ||
257 | region_mapping | |
258 | } | |
259 | ||
260 | /// True if `r` is a member of this set of universal regions. | |
261 | pub fn is_universal_region(&self, r: RegionVid) -> bool { | |
83c7162d | 262 | (FIRST_GLOBAL_INDEX..self.num_universals).contains(&r.index()) |
ff7c6d11 XL |
263 | } |
264 | ||
265 | /// Classifies `r` as a universal region, returning `None` if this | |
266 | /// is not a member of this set of universal regions. | |
267 | pub fn region_classification(&self, r: RegionVid) -> Option<RegionClassification> { | |
268 | let index = r.index(); | |
83c7162d | 269 | if (FIRST_GLOBAL_INDEX..self.first_extern_index).contains(&index) { |
ff7c6d11 | 270 | Some(RegionClassification::Global) |
83c7162d | 271 | } else if (self.first_extern_index..self.first_local_index).contains(&index) { |
ff7c6d11 | 272 | Some(RegionClassification::External) |
83c7162d | 273 | } else if (self.first_local_index..self.num_universals).contains(&index) { |
ff7c6d11 XL |
274 | Some(RegionClassification::Local) |
275 | } else { | |
276 | None | |
277 | } | |
278 | } | |
279 | ||
280 | /// Returns an iterator over all the RegionVids corresponding to | |
281 | /// universally quantified free regions. | |
282 | pub fn universal_regions(&self) -> impl Iterator<Item = RegionVid> { | |
283 | (FIRST_GLOBAL_INDEX..self.num_universals).map(RegionVid::new) | |
284 | } | |
285 | ||
286 | /// True if `r` is classified as an local region. | |
287 | pub fn is_local_free_region(&self, r: RegionVid) -> bool { | |
288 | self.region_classification(r) == Some(RegionClassification::Local) | |
289 | } | |
290 | ||
291 | /// Returns the number of universal regions created in any category. | |
292 | pub fn len(&self) -> usize { | |
293 | self.num_universals | |
294 | } | |
295 | ||
296 | /// Given two universal regions, returns the postdominating | |
297 | /// upper-bound (effectively the least upper bound). | |
298 | /// | |
299 | /// (See `TransitiveRelation::postdom_upper_bound` for details on | |
300 | /// the postdominating upper bound in general.) | |
301 | pub fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid { | |
302 | assert!(self.is_universal_region(fr1)); | |
303 | assert!(self.is_universal_region(fr2)); | |
304 | *self.relations | |
305 | .inverse_outlives | |
306 | .postdom_upper_bound(&fr1, &fr2) | |
307 | .unwrap_or(&self.fr_static) | |
308 | } | |
309 | ||
310 | /// Finds an "upper bound" for `fr` that is not local. In other | |
311 | /// words, returns the smallest (*) known region `fr1` that (a) | |
312 | /// outlives `fr` and (b) is not local. This cannot fail, because | |
313 | /// we will always find `'static` at worst. | |
314 | /// | |
315 | /// (*) If there are multiple competing choices, we pick the "postdominating" | |
316 | /// one. See `TransitiveRelation::postdom_upper_bound` for details. | |
317 | pub fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid { | |
318 | debug!("non_local_upper_bound(fr={:?})", fr); | |
319 | self.non_local_bound(&self.relations.inverse_outlives, fr) | |
320 | .unwrap_or(self.fr_static) | |
321 | } | |
322 | ||
323 | /// Finds a "lower bound" for `fr` that is not local. In other | |
324 | /// words, returns the largest (*) known region `fr1` that (a) is | |
325 | /// outlived by `fr` and (b) is not local. This cannot fail, | |
326 | /// because we will always find `'static` at worst. | |
327 | /// | |
328 | /// (*) If there are multiple competing choices, we pick the "postdominating" | |
329 | /// one. See `TransitiveRelation::postdom_upper_bound` for details. | |
330 | pub fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> { | |
331 | debug!("non_local_lower_bound(fr={:?})", fr); | |
332 | self.non_local_bound(&self.relations.outlives, fr) | |
333 | } | |
334 | ||
335 | /// Returns the number of global plus external universal regions. | |
336 | /// For closures, these are the regions that appear free in the | |
337 | /// closure type (versus those bound in the closure | |
338 | /// signature). They are therefore the regions between which the | |
339 | /// closure may impose constraints that its creator must verify. | |
340 | pub fn num_global_and_external_regions(&self) -> usize { | |
341 | self.first_local_index | |
342 | } | |
343 | ||
344 | /// Helper for `non_local_upper_bound` and | |
345 | /// `non_local_lower_bound`. Repeatedly invokes `postdom_parent` | |
346 | /// until we find something that is not local. Returns None if we | |
347 | /// never do so. | |
348 | fn non_local_bound( | |
349 | &self, | |
350 | relation: &TransitiveRelation<RegionVid>, | |
351 | fr0: RegionVid, | |
352 | ) -> Option<RegionVid> { | |
353 | // This method assumes that `fr0` is one of the universally | |
354 | // quantified region variables. | |
355 | assert!(self.is_universal_region(fr0)); | |
356 | ||
357 | let mut external_parents = vec![]; | |
358 | let mut queue = vec![&fr0]; | |
359 | ||
360 | // Keep expanding `fr` into its parents until we reach | |
361 | // non-local regions. | |
362 | while let Some(fr) = queue.pop() { | |
363 | if !self.is_local_free_region(*fr) { | |
364 | external_parents.push(fr); | |
365 | continue; | |
366 | } | |
367 | ||
368 | queue.extend(relation.parents(fr)); | |
369 | } | |
370 | ||
371 | debug!("non_local_bound: external_parents={:?}", external_parents); | |
372 | ||
373 | // In case we find more than one, reduce to one for | |
374 | // convenience. This is to prevent us from generating more | |
375 | // complex constraints, but it will cause spurious errors. | |
376 | let post_dom = relation | |
377 | .mutual_immediate_postdominator(external_parents) | |
378 | .cloned(); | |
379 | ||
380 | debug!("non_local_bound: post_dom={:?}", post_dom); | |
381 | ||
382 | post_dom.and_then(|post_dom| { | |
383 | // If the mutual immediate postdom is not local, then | |
384 | // there is no non-local result we can return. | |
385 | if !self.is_local_free_region(post_dom) { | |
386 | Some(post_dom) | |
387 | } else { | |
388 | None | |
389 | } | |
390 | }) | |
391 | } | |
392 | ||
393 | /// True if fr1 is known to outlive fr2. | |
394 | /// | |
395 | /// This will only ever be true for universally quantified regions. | |
396 | pub fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool { | |
397 | self.relations.outlives.contains(&fr1, &fr2) | |
398 | } | |
399 | ||
400 | /// Returns a vector of free regions `x` such that `fr1: x` is | |
401 | /// known to hold. | |
402 | pub fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<&RegionVid> { | |
403 | self.relations.outlives.reachable_from(&fr1) | |
404 | } | |
405 | ||
406 | /// Get an iterator over all the early-bound regions that have names. | |
407 | pub fn named_universal_regions<'s>( | |
408 | &'s self, | |
409 | ) -> impl Iterator<Item = (ty::Region<'tcx>, ty::RegionVid)> + 's { | |
410 | self.indices.indices.iter().map(|(&r, &v)| (r, v)) | |
411 | } | |
412 | ||
413 | /// See `UniversalRegionIndices::to_region_vid`. | |
414 | pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { | |
415 | self.indices.to_region_vid(r) | |
416 | } | |
417 | } | |
418 | ||
419 | struct UniversalRegionsBuilder<'cx, 'gcx: 'tcx, 'tcx: 'cx> { | |
420 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, | |
421 | mir_def_id: DefId, | |
422 | mir_hir_id: HirId, | |
423 | mir_node_id: ast::NodeId, | |
424 | param_env: ty::ParamEnv<'tcx>, | |
425 | region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>, | |
426 | relations: UniversalRegionRelations, | |
427 | } | |
428 | ||
429 | const FR: NLLRegionVariableOrigin = NLLRegionVariableOrigin::FreeRegion; | |
430 | ||
431 | impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> { | |
432 | fn build(mut self) -> UniversalRegions<'tcx> { | |
433 | debug!("build(mir_def_id={:?})", self.mir_def_id); | |
434 | ||
435 | let param_env = self.param_env; | |
436 | debug!("build: param_env={:?}", param_env); | |
437 | ||
438 | assert_eq!(FIRST_GLOBAL_INDEX, self.infcx.num_region_vars()); | |
439 | ||
440 | // Create the "global" region that is always free in all contexts: 'static. | |
441 | let fr_static = self.infcx.next_nll_region_var(FR).to_region_vid(); | |
442 | ||
443 | // We've now added all the global regions. The next ones we | |
444 | // add will be external. | |
445 | let first_extern_index = self.infcx.num_region_vars(); | |
446 | ||
447 | let defining_ty = self.defining_ty(); | |
448 | debug!("build: defining_ty={:?}", defining_ty); | |
449 | ||
450 | let mut indices = self.compute_indices(fr_static, defining_ty); | |
451 | debug!("build: indices={:?}", indices); | |
452 | ||
453 | let bound_inputs_and_output = self.compute_inputs_and_output(&indices, defining_ty); | |
454 | ||
455 | // "Liberate" the late-bound regions. These correspond to | |
456 | // "local" free regions. | |
457 | let first_local_index = self.infcx.num_region_vars(); | |
458 | let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars( | |
459 | FR, | |
460 | self.mir_def_id, | |
461 | &bound_inputs_and_output, | |
462 | &mut indices, | |
463 | ); | |
464 | let fr_fn_body = self.infcx.next_nll_region_var(FR).to_region_vid(); | |
465 | let num_universals = self.infcx.num_region_vars(); | |
466 | ||
467 | // Insert the facts we know from the predicates. Why? Why not. | |
468 | self.add_outlives_bounds(&indices, bounds::explicit_outlives_bounds(param_env)); | |
469 | ||
470 | // Add the implied bounds from inputs and outputs. | |
471 | for ty in inputs_and_output { | |
472 | debug!("build: input_or_output={:?}", ty); | |
473 | self.add_implied_bounds(&indices, ty); | |
474 | } | |
475 | ||
476 | // Finally: | |
477 | // - outlives is reflexive, so `'r: 'r` for every region `'r` | |
478 | // - `'static: 'r` for every region `'r` | |
479 | // - `'r: 'fn_body` for every (other) universally quantified | |
480 | // region `'r`, all of which are provided by our caller | |
481 | for fr in (FIRST_GLOBAL_INDEX..num_universals).map(RegionVid::new) { | |
482 | debug!( | |
483 | "build: relating free region {:?} to itself and to 'static", | |
484 | fr | |
485 | ); | |
486 | self.relations.relate_universal_regions(fr, fr); | |
487 | self.relations.relate_universal_regions(fr_static, fr); | |
488 | self.relations.relate_universal_regions(fr, fr_fn_body); | |
489 | } | |
490 | ||
491 | let (unnormalized_output_ty, unnormalized_input_tys) = | |
492 | inputs_and_output.split_last().unwrap(); | |
493 | ||
494 | debug!( | |
495 | "build: global regions = {}..{}", | |
496 | FIRST_GLOBAL_INDEX, | |
497 | first_extern_index | |
498 | ); | |
499 | debug!( | |
500 | "build: extern regions = {}..{}", | |
501 | first_extern_index, | |
502 | first_local_index | |
503 | ); | |
504 | debug!( | |
505 | "build: local regions = {}..{}", | |
506 | first_local_index, | |
507 | num_universals | |
508 | ); | |
509 | ||
2c00a5a8 XL |
510 | let yield_ty = match defining_ty { |
511 | DefiningTy::Generator(def_id, substs, _) => { | |
94b46f34 | 512 | Some(substs.yield_ty(def_id, self.infcx.tcx)) |
2c00a5a8 XL |
513 | } |
514 | _ => None, | |
515 | }; | |
516 | ||
ff7c6d11 XL |
517 | UniversalRegions { |
518 | indices, | |
519 | fr_static, | |
520 | fr_fn_body, | |
521 | first_extern_index, | |
522 | first_local_index, | |
523 | num_universals, | |
524 | defining_ty, | |
525 | unnormalized_output_ty, | |
526 | unnormalized_input_tys, | |
527 | region_bound_pairs: self.region_bound_pairs, | |
2c00a5a8 | 528 | yield_ty: yield_ty, |
ff7c6d11 XL |
529 | relations: self.relations, |
530 | } | |
531 | } | |
532 | ||
533 | /// Returns the "defining type" of the current MIR; | |
534 | /// see `DefiningTy` for details. | |
535 | fn defining_ty(&self) -> DefiningTy<'tcx> { | |
536 | let tcx = self.infcx.tcx; | |
ff7c6d11 XL |
537 | let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id); |
538 | ||
ff7c6d11 | 539 | match tcx.hir.body_owner_kind(self.mir_node_id) { |
2c00a5a8 XL |
540 | BodyOwnerKind::Fn => { |
541 | let defining_ty = if self.mir_def_id == closure_base_def_id { | |
542 | tcx.type_of(closure_base_def_id) | |
543 | } else { | |
544 | let tables = tcx.typeck_tables_of(self.mir_def_id); | |
545 | tables.node_id_to_type(self.mir_hir_id) | |
546 | }; | |
547 | ||
548 | let defining_ty = self.infcx | |
549 | .replace_free_regions_with_nll_infer_vars(FR, &defining_ty); | |
550 | ||
551 | match defining_ty.sty { | |
552 | ty::TyClosure(def_id, substs) => DefiningTy::Closure(def_id, substs), | |
94b46f34 XL |
553 | ty::TyGenerator(def_id, substs, movability) => { |
554 | DefiningTy::Generator(def_id, substs, movability) | |
2c00a5a8 XL |
555 | } |
556 | ty::TyFnDef(def_id, substs) => DefiningTy::FnDef(def_id, substs), | |
557 | _ => span_bug!( | |
558 | tcx.def_span(self.mir_def_id), | |
559 | "expected defining type for `{:?}`: `{:?}`", | |
560 | self.mir_def_id, | |
561 | defining_ty | |
562 | ), | |
ff7c6d11 | 563 | } |
2c00a5a8 XL |
564 | } |
565 | ||
566 | BodyOwnerKind::Const | BodyOwnerKind::Static(..) => { | |
567 | assert_eq!(closure_base_def_id, self.mir_def_id); | |
568 | let identity_substs = Substs::identity_for_item(tcx, closure_base_def_id); | |
569 | let substs = self.infcx | |
570 | .replace_free_regions_with_nll_infer_vars(FR, &identity_substs); | |
571 | DefiningTy::Const(self.mir_def_id, substs) | |
572 | } | |
ff7c6d11 XL |
573 | } |
574 | } | |
575 | ||
576 | /// Builds a hashmap that maps from the universal regions that are | |
577 | /// in scope (as a `ty::Region<'tcx>`) to their indices (as a | |
578 | /// `RegionVid`). The map returned by this function contains only | |
579 | /// the early-bound regions. | |
580 | fn compute_indices( | |
581 | &self, | |
582 | fr_static: RegionVid, | |
583 | defining_ty: DefiningTy<'tcx>, | |
584 | ) -> UniversalRegionIndices<'tcx> { | |
585 | let tcx = self.infcx.tcx; | |
586 | let gcx = tcx.global_tcx(); | |
587 | let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id); | |
588 | let identity_substs = Substs::identity_for_item(gcx, closure_base_def_id); | |
589 | let fr_substs = match defining_ty { | |
94b46f34 XL |
590 | DefiningTy::Closure(_, ClosureSubsts { ref substs }) | |
591 | DefiningTy::Generator(_, GeneratorSubsts { ref substs }, _) => { | |
ff7c6d11 XL |
592 | // In the case of closures, we rely on the fact that |
593 | // the first N elements in the ClosureSubsts are | |
594 | // inherited from the `closure_base_def_id`. | |
595 | // Therefore, when we zip together (below) with | |
596 | // `identity_substs`, we will get only those regions | |
597 | // that correspond to early-bound regions declared on | |
598 | // the `closure_base_def_id`. | |
94b46f34 XL |
599 | assert!(substs.len() >= identity_substs.len()); |
600 | assert_eq!(substs.regions().count(), identity_substs.regions().count()); | |
601 | substs | |
ff7c6d11 XL |
602 | } |
603 | ||
2c00a5a8 | 604 | DefiningTy::FnDef(_, substs) | DefiningTy::Const(_, substs) => substs, |
ff7c6d11 XL |
605 | }; |
606 | ||
607 | let global_mapping = iter::once((gcx.types.re_static, fr_static)); | |
608 | let subst_mapping = identity_substs | |
609 | .regions() | |
610 | .zip(fr_substs.regions().map(|r| r.to_region_vid())); | |
611 | ||
612 | UniversalRegionIndices { | |
613 | indices: global_mapping.chain(subst_mapping).collect(), | |
614 | } | |
615 | } | |
616 | ||
617 | fn compute_inputs_and_output( | |
618 | &self, | |
619 | indices: &UniversalRegionIndices<'tcx>, | |
620 | defining_ty: DefiningTy<'tcx>, | |
621 | ) -> ty::Binder<&'tcx ty::Slice<Ty<'tcx>>> { | |
622 | let tcx = self.infcx.tcx; | |
623 | match defining_ty { | |
624 | DefiningTy::Closure(def_id, substs) => { | |
625 | assert_eq!(self.mir_def_id, def_id); | |
626 | let closure_sig = substs.closure_sig_ty(def_id, tcx).fn_sig(tcx); | |
627 | let inputs_and_output = closure_sig.inputs_and_output(); | |
628 | let closure_ty = tcx.closure_env_ty(def_id, substs).unwrap(); | |
629 | ty::Binder::fuse( | |
630 | closure_ty, | |
631 | inputs_and_output, | |
632 | |closure_ty, inputs_and_output| { | |
633 | // The "inputs" of the closure in the | |
634 | // signature appear as a tuple. The MIR side | |
635 | // flattens this tuple. | |
636 | let (&output, tuplized_inputs) = inputs_and_output.split_last().unwrap(); | |
637 | assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs"); | |
638 | let inputs = match tuplized_inputs[0].sty { | |
0531ce1d | 639 | ty::TyTuple(inputs) => inputs, |
ff7c6d11 XL |
640 | _ => bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]), |
641 | }; | |
642 | ||
643 | tcx.mk_type_list( | |
644 | iter::once(closure_ty) | |
645 | .chain(inputs.iter().cloned()) | |
646 | .chain(iter::once(output)), | |
647 | ) | |
648 | }, | |
649 | ) | |
650 | } | |
651 | ||
94b46f34 | 652 | DefiningTy::Generator(def_id, substs, movability) => { |
ff7c6d11 | 653 | assert_eq!(self.mir_def_id, def_id); |
94b46f34 XL |
654 | let output = substs.return_ty(def_id, tcx); |
655 | let generator_ty = tcx.mk_generator(def_id, substs, movability); | |
ff7c6d11 XL |
656 | let inputs_and_output = self.infcx.tcx.intern_type_list(&[generator_ty, output]); |
657 | ty::Binder::dummy(inputs_and_output) | |
658 | } | |
659 | ||
660 | DefiningTy::FnDef(def_id, _) => { | |
661 | let sig = tcx.fn_sig(def_id); | |
662 | let sig = indices.fold_to_region_vids(tcx, &sig); | |
663 | sig.inputs_and_output() | |
664 | } | |
665 | ||
2c00a5a8 XL |
666 | DefiningTy::Const(def_id, _) => { |
667 | // For a constant body, there are no inputs, and one | |
668 | // "output" (the type of the constant). | |
669 | assert_eq!(self.mir_def_id, def_id); | |
670 | let ty = tcx.type_of(def_id); | |
671 | let ty = indices.fold_to_region_vids(tcx, &ty); | |
94b46f34 | 672 | ty::Binder::dummy(tcx.intern_type_list(&[ty])) |
2c00a5a8 | 673 | } |
ff7c6d11 XL |
674 | } |
675 | } | |
676 | ||
677 | /// Update the type of a single local, which should represent | |
678 | /// either the return type of the MIR or one of its arguments. At | |
679 | /// the same time, compute and add any implied bounds that come | |
680 | /// from this local. | |
681 | /// | |
682 | /// Assumes that `universal_regions` indices map is fully constructed. | |
683 | fn add_implied_bounds(&mut self, indices: &UniversalRegionIndices<'tcx>, ty: Ty<'tcx>) { | |
684 | debug!("add_implied_bounds(ty={:?})", ty); | |
685 | let span = self.infcx.tcx.def_span(self.mir_def_id); | |
686 | let bounds = self.infcx | |
687 | .implied_outlives_bounds(self.param_env, self.mir_node_id, ty, span); | |
688 | self.add_outlives_bounds(indices, bounds); | |
689 | } | |
690 | ||
691 | /// Registers the `OutlivesBound` items from `outlives_bounds` in | |
692 | /// the outlives relation as well as the region-bound pairs | |
693 | /// listing. | |
694 | fn add_outlives_bounds<I>(&mut self, indices: &UniversalRegionIndices<'tcx>, outlives_bounds: I) | |
695 | where | |
696 | I: IntoIterator<Item = OutlivesBound<'tcx>>, | |
697 | { | |
698 | for outlives_bound in outlives_bounds { | |
699 | debug!("add_outlives_bounds(bound={:?})", outlives_bound); | |
700 | ||
701 | match outlives_bound { | |
702 | OutlivesBound::RegionSubRegion(r1, r2) => { | |
703 | // The bound says that `r1 <= r2`; we store `r2: r1`. | |
704 | let r1 = indices.to_region_vid(r1); | |
705 | let r2 = indices.to_region_vid(r2); | |
706 | self.relations.relate_universal_regions(r2, r1); | |
707 | } | |
708 | ||
709 | OutlivesBound::RegionSubParam(r_a, param_b) => { | |
710 | self.region_bound_pairs | |
711 | .push((r_a, GenericKind::Param(param_b))); | |
712 | } | |
713 | ||
714 | OutlivesBound::RegionSubProjection(r_a, projection_b) => { | |
715 | self.region_bound_pairs | |
716 | .push((r_a, GenericKind::Projection(projection_b))); | |
717 | } | |
718 | } | |
719 | } | |
720 | } | |
721 | } | |
722 | ||
723 | impl UniversalRegionRelations { | |
724 | /// Records in the `outlives_relation` (and | |
725 | /// `inverse_outlives_relation`) that `fr_a: fr_b`. | |
726 | fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) { | |
727 | debug!( | |
728 | "relate_universal_regions: fr_a={:?} outlives fr_b={:?}", | |
729 | fr_a, | |
730 | fr_b | |
731 | ); | |
732 | self.outlives.add(fr_a, fr_b); | |
733 | self.inverse_outlives.add(fr_b, fr_a); | |
734 | } | |
735 | } | |
736 | ||
737 | trait InferCtxtExt<'tcx> { | |
738 | fn replace_free_regions_with_nll_infer_vars<T>( | |
739 | &self, | |
740 | origin: NLLRegionVariableOrigin, | |
741 | value: &T, | |
742 | ) -> T | |
743 | where | |
744 | T: TypeFoldable<'tcx>; | |
745 | ||
746 | fn replace_bound_regions_with_nll_infer_vars<T>( | |
747 | &self, | |
748 | origin: NLLRegionVariableOrigin, | |
749 | all_outlive_scope: DefId, | |
750 | value: &ty::Binder<T>, | |
751 | indices: &mut UniversalRegionIndices<'tcx>, | |
752 | ) -> T | |
753 | where | |
754 | T: TypeFoldable<'tcx>; | |
755 | } | |
756 | ||
757 | impl<'cx, 'gcx, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'cx, 'gcx, 'tcx> { | |
758 | fn replace_free_regions_with_nll_infer_vars<T>( | |
759 | &self, | |
760 | origin: NLLRegionVariableOrigin, | |
761 | value: &T, | |
762 | ) -> T | |
763 | where | |
764 | T: TypeFoldable<'tcx>, | |
765 | { | |
766 | self.tcx.fold_regions(value, &mut false, |_region, _depth| { | |
767 | self.next_nll_region_var(origin) | |
768 | }) | |
769 | } | |
770 | ||
771 | fn replace_bound_regions_with_nll_infer_vars<T>( | |
772 | &self, | |
773 | origin: NLLRegionVariableOrigin, | |
774 | all_outlive_scope: DefId, | |
775 | value: &ty::Binder<T>, | |
776 | indices: &mut UniversalRegionIndices<'tcx>, | |
777 | ) -> T | |
778 | where | |
779 | T: TypeFoldable<'tcx>, | |
780 | { | |
0531ce1d XL |
781 | debug!( |
782 | "replace_bound_regions_with_nll_infer_vars(value={:?}, all_outlive_scope={:?})", | |
783 | value, | |
784 | all_outlive_scope, | |
785 | ); | |
ff7c6d11 XL |
786 | let (value, _map) = self.tcx.replace_late_bound_regions(value, |br| { |
787 | let liberated_region = self.tcx.mk_region(ty::ReFree(ty::FreeRegion { | |
788 | scope: all_outlive_scope, | |
789 | bound_region: br, | |
790 | })); | |
791 | let region_vid = self.next_nll_region_var(origin); | |
792 | indices.insert_late_bound_region(liberated_region, region_vid.to_region_vid()); | |
0531ce1d | 793 | debug!("liberated_region={:?} => {:?}", liberated_region, region_vid); |
ff7c6d11 XL |
794 | region_vid |
795 | }); | |
796 | value | |
797 | } | |
798 | } | |
799 | ||
800 | impl<'tcx> UniversalRegionIndices<'tcx> { | |
801 | /// Initially, the `UniversalRegionIndices` map contains only the | |
802 | /// early-bound regions in scope. Once that is all setup, we come | |
803 | /// in later and instantiate the late-bound regions, and then we | |
804 | /// insert the `ReFree` version of those into the map as | |
805 | /// well. These are used for error reporting. | |
806 | fn insert_late_bound_region(&mut self, r: ty::Region<'tcx>, | |
807 | vid: ty::RegionVid) | |
808 | { | |
809 | self.indices.insert(r, vid); | |
810 | } | |
811 | ||
812 | /// Converts `r` into a local inference variable: `r` can either | |
813 | /// by a `ReVar` (i.e., already a reference to an inference | |
814 | /// variable) or it can be `'static` or some early-bound | |
815 | /// region. This is useful when taking the results from | |
816 | /// type-checking and trait-matching, which may sometimes | |
817 | /// reference those regions from the `ParamEnv`. It is also used | |
818 | /// during initialization. Relies on the `indices` map having been | |
819 | /// fully initialized. | |
820 | pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { | |
2c00a5a8 XL |
821 | if let ty::ReVar(..) = r { |
822 | r.to_region_vid() | |
823 | } else { | |
824 | *self.indices.get(&r).unwrap_or_else(|| { | |
825 | bug!("cannot convert `{:?}` to a region vid", r) | |
826 | }) | |
ff7c6d11 XL |
827 | } |
828 | } | |
829 | ||
830 | /// Replace all free regions in `value` with region vids, as | |
831 | /// returned by `to_region_vid`. | |
832 | pub fn fold_to_region_vids<T>(&self, tcx: TyCtxt<'_, '_, 'tcx>, value: &T) -> T | |
833 | where | |
834 | T: TypeFoldable<'tcx>, | |
835 | { | |
836 | tcx.fold_regions(value, &mut false, |region, _| { | |
837 | tcx.mk_region(ty::ReVar(self.to_region_vid(region))) | |
838 | }) | |
839 | } | |
840 | } | |
841 | ||
842 | /// This trait is used by the `impl-trait` constraint code to abstract | |
843 | /// over the `FreeRegionMap` from lexical regions and | |
844 | /// `UniversalRegions` (from NLL)`. | |
845 | impl<'tcx> FreeRegionRelations<'tcx> for UniversalRegions<'tcx> { | |
846 | fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool { | |
847 | let shorter = shorter.to_region_vid(); | |
848 | assert!(self.is_universal_region(shorter)); | |
849 | let longer = longer.to_region_vid(); | |
850 | assert!(self.is_universal_region(longer)); | |
851 | self.outlives(longer, shorter) | |
852 | } | |
853 | } |