]>
Commit | Line | Data |
---|---|---|
ff7c6d11 XL |
1 | //! Code to extract the universally quantified regions declared on a |
2 | //! function and the relationships between them. For example: | |
3 | //! | |
4 | //! ``` | |
5 | //! fn foo<'a, 'b, 'c: 'b>() { } | |
6 | //! ``` | |
7 | //! | |
dfeec247 | 8 | //! here we would return a map assigning each of `{'a, 'b, 'c}` |
ff7c6d11 XL |
9 | //! to an index, as well as the `FreeRegionMap` which can compute |
10 | //! relationships between them. | |
11 | //! | |
12 | //! The code in this file doesn't *do anything* with those results; it | |
13 | //! just returns them for other code to use. | |
14 | ||
8faf50e0 | 15 | use either::Either; |
dfeec247 | 16 | use rustc_data_structures::fx::FxHashMap; |
b7449926 | 17 | use rustc_errors::DiagnosticBuilder; |
dfeec247 XL |
18 | use rustc_hir as hir; |
19 | use rustc_hir::def_id::DefId; | |
ba9703b0 | 20 | use rustc_hir::lang_items; |
dfeec247 XL |
21 | use rustc_hir::{BodyOwnerKind, HirId}; |
22 | use rustc_index::vec::{Idx, IndexVec}; | |
74b04a01 | 23 | use rustc_infer::infer::{InferCtxt, NLLRegionVariableOrigin}; |
ba9703b0 XL |
24 | use rustc_middle::ty::fold::TypeFoldable; |
25 | use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef}; | |
26 | use rustc_middle::ty::{self, RegionVid, Ty, TyCtxt}; | |
ff7c6d11 | 27 | use std::iter; |
ff7c6d11 | 28 | |
60c5eb7d | 29 | use crate::borrow_check::nll::ToRegionVid; |
ff7c6d11 XL |
30 | |
31 | #[derive(Debug)] | |
32 | pub struct UniversalRegions<'tcx> { | |
33 | indices: UniversalRegionIndices<'tcx>, | |
34 | ||
35 | /// The vid assigned to `'static` | |
36 | pub fr_static: RegionVid, | |
37 | ||
38 | /// A special region vid created to represent the current MIR fn | |
9fa01778 | 39 | /// body. It will outlive the entire CFG but it will not outlive |
ff7c6d11 XL |
40 | /// any other universal regions. |
41 | pub fr_fn_body: RegionVid, | |
42 | ||
43 | /// We create region variables such that they are ordered by their | |
44 | /// `RegionClassification`. The first block are globals, then | |
9fa01778 XL |
45 | /// externals, then locals. So, things from: |
46 | /// - `FIRST_GLOBAL_INDEX..first_extern_index` are global, | |
47 | /// - `first_extern_index..first_local_index` are external, | |
8faf50e0 | 48 | /// - `first_local_index..num_universals` are local. |
ff7c6d11 XL |
49 | first_extern_index: usize, |
50 | ||
51 | /// See `first_extern_index`. | |
52 | first_local_index: usize, | |
53 | ||
54 | /// The total number of universal region variables instantiated. | |
55 | num_universals: usize, | |
56 | ||
57 | /// The "defining" type for this function, with all universal | |
9fa01778 | 58 | /// regions instantiated. For a closure or generator, this is the |
b7449926 | 59 | /// closure type, but for a top-level function it's the `FnDef`. |
ff7c6d11 XL |
60 | pub defining_ty: DefiningTy<'tcx>, |
61 | ||
62 | /// The return type of this function, with all regions replaced by | |
63 | /// their universal `RegionVid` equivalents. | |
64 | /// | |
9fa01778 | 65 | /// N.B., associated types in this type have not been normalized, |
ff7c6d11 XL |
66 | /// as the name suggests. =) |
67 | pub unnormalized_output_ty: Ty<'tcx>, | |
68 | ||
69 | /// The fully liberated input types of this function, with all | |
70 | /// regions replaced by their universal `RegionVid` equivalents. | |
71 | /// | |
9fa01778 | 72 | /// N.B., associated types in these types have not been normalized, |
ff7c6d11 XL |
73 | /// as the name suggests. =) |
74 | pub unnormalized_input_tys: &'tcx [Ty<'tcx>], | |
75 | ||
2c00a5a8 | 76 | pub yield_ty: Option<Ty<'tcx>>, |
ff7c6d11 XL |
77 | } |
78 | ||
79 | /// The "defining type" for this MIR. The key feature of the "defining | |
80 | /// type" is that it contains the information needed to derive all the | |
81 | /// universal regions that are in scope as well as the types of the | |
82 | /// inputs/output from the MIR. In general, early-bound universal | |
83 | /// regions appear free in the defining type and late-bound regions | |
84 | /// appear bound in the signature. | |
85 | #[derive(Copy, Clone, Debug)] | |
86 | pub enum DefiningTy<'tcx> { | |
87 | /// The MIR is a closure. The signature is found via | |
88 | /// `ClosureSubsts::closure_sig_ty`. | |
e74abb32 | 89 | Closure(DefId, SubstsRef<'tcx>), |
ff7c6d11 XL |
90 | |
91 | /// The MIR is a generator. The signature is that generators take | |
92 | /// no parameters and return the result of | |
93 | /// `ClosureSubsts::generator_return_ty`. | |
60c5eb7d | 94 | Generator(DefId, SubstsRef<'tcx>, hir::Movability), |
ff7c6d11 | 95 | |
9fa01778 | 96 | /// The MIR is a fn item with the given `DefId` and substs. The signature |
ff7c6d11 | 97 | /// of the function can be bound then with the `fn_sig` query. |
532ac7d7 | 98 | FnDef(DefId, SubstsRef<'tcx>), |
ff7c6d11 XL |
99 | |
100 | /// The MIR represents some form of constant. The signature then | |
101 | /// is that it has no inputs and a single return value, which is | |
102 | /// the value of the constant. | |
532ac7d7 | 103 | Const(DefId, SubstsRef<'tcx>), |
ff7c6d11 XL |
104 | } |
105 | ||
8faf50e0 XL |
106 | impl<'tcx> DefiningTy<'tcx> { |
107 | /// Returns a list of all the upvar types for this MIR. If this is | |
108 | /// not a closure or generator, there are no upvars, and hence it | |
109 | /// will be an empty list. The order of types in this list will | |
48663c56 | 110 | /// match up with the upvar order in the HIR, typesystem, and MIR. |
ba9703b0 | 111 | pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx { |
8faf50e0 | 112 | match self { |
ba9703b0 XL |
113 | DefiningTy::Closure(_, substs) => Either::Left(substs.as_closure().upvar_tys()), |
114 | DefiningTy::Generator(_, substs, _) => { | |
115 | Either::Right(Either::Left(substs.as_generator().upvar_tys())) | |
8faf50e0 XL |
116 | } |
117 | DefiningTy::FnDef(..) | DefiningTy::Const(..) => { | |
118 | Either::Right(Either::Right(iter::empty())) | |
119 | } | |
120 | } | |
121 | } | |
122 | ||
123 | /// Number of implicit inputs -- notably the "environment" | |
124 | /// parameter for closures -- that appear in MIR but not in the | |
125 | /// user's code. | |
126 | pub fn implicit_inputs(self) -> usize { | |
127 | match self { | |
128 | DefiningTy::Closure(..) | DefiningTy::Generator(..) => 1, | |
129 | DefiningTy::FnDef(..) | DefiningTy::Const(..) => 0, | |
130 | } | |
131 | } | |
74b04a01 XL |
132 | |
133 | pub fn is_fn_def(&self) -> bool { | |
134 | match *self { | |
135 | DefiningTy::FnDef(..) => true, | |
136 | _ => false, | |
137 | } | |
138 | } | |
139 | ||
140 | pub fn is_const(&self) -> bool { | |
141 | match *self { | |
142 | DefiningTy::Const(..) => true, | |
143 | _ => false, | |
144 | } | |
145 | } | |
146 | ||
147 | pub fn def_id(&self) -> DefId { | |
148 | match *self { | |
149 | DefiningTy::Closure(def_id, ..) | |
150 | | DefiningTy::Generator(def_id, ..) | |
151 | | DefiningTy::FnDef(def_id, ..) | |
152 | | DefiningTy::Const(def_id, ..) => def_id, | |
153 | } | |
154 | } | |
8faf50e0 XL |
155 | } |
156 | ||
ff7c6d11 XL |
157 | #[derive(Debug)] |
158 | struct UniversalRegionIndices<'tcx> { | |
159 | /// For those regions that may appear in the parameter environment | |
160 | /// ('static and early-bound regions), we maintain a map from the | |
161 | /// `ty::Region` to the internal `RegionVid` we are using. This is | |
162 | /// used because trait matching and type-checking will feed us | |
163 | /// region constraints that reference those regions and we need to | |
164 | /// be able to map them our internal `RegionVid`. This is | |
532ac7d7 | 165 | /// basically equivalent to a `InternalSubsts`, except that it also |
ff7c6d11 XL |
166 | /// contains an entry for `ReStatic` -- it might be nice to just |
167 | /// use a substs, and then handle `ReStatic` another way. | |
168 | indices: FxHashMap<ty::Region<'tcx>, RegionVid>, | |
169 | } | |
170 | ||
e74abb32 | 171 | #[derive(Debug, PartialEq)] |
ff7c6d11 XL |
172 | pub enum RegionClassification { |
173 | /// A **global** region is one that can be named from | |
174 | /// anywhere. There is only one, `'static`. | |
175 | Global, | |
176 | ||
177 | /// An **external** region is only relevant for closures. In that | |
178 | /// case, it refers to regions that are free in the closure type | |
179 | /// -- basically, something bound in the surrounding context. | |
180 | /// | |
181 | /// Consider this example: | |
182 | /// | |
183 | /// ``` | |
184 | /// fn foo<'a, 'b>(a: &'a u32, b: &'b u32, c: &'static u32) { | |
185 | /// let closure = for<'x> |x: &'x u32| { .. }; | |
186 | /// ^^^^^^^ pretend this were legal syntax | |
187 | /// for declaring a late-bound region in | |
188 | /// a closure signature | |
189 | /// } | |
190 | /// ``` | |
191 | /// | |
192 | /// Here, the lifetimes `'a` and `'b` would be **external** to the | |
193 | /// closure. | |
194 | /// | |
195 | /// If we are not analyzing a closure, there are no external | |
196 | /// lifetimes. | |
197 | External, | |
198 | ||
199 | /// A **local** lifetime is one about which we know the full set | |
200 | /// of relevant constraints (that is, relationships to other named | |
9fa01778 XL |
201 | /// regions). For a closure, this includes any region bound in |
202 | /// the closure's signature. For a fn item, this includes all | |
ff7c6d11 XL |
203 | /// regions other than global ones. |
204 | /// | |
205 | /// Continuing with the example from `External`, if we were | |
206 | /// analyzing the closure, then `'x` would be local (and `'a` and | |
9fa01778 | 207 | /// `'b` are external). If we are analyzing the function item |
ff7c6d11 XL |
208 | /// `foo`, then `'a` and `'b` are local (and `'x` is not in |
209 | /// scope). | |
210 | Local, | |
211 | } | |
212 | ||
213 | const FIRST_GLOBAL_INDEX: usize = 0; | |
214 | ||
215 | impl<'tcx> UniversalRegions<'tcx> { | |
216 | /// Creates a new and fully initialized `UniversalRegions` that | |
217 | /// contains indices for all the free regions found in the given | |
218 | /// MIR -- that is, all the regions that appear in the function's | |
219 | /// signature. This will also compute the relationships that are | |
220 | /// known between those regions. | |
221 | pub fn new( | |
dc9dc135 | 222 | infcx: &InferCtxt<'_, 'tcx>, |
ff7c6d11 XL |
223 | mir_def_id: DefId, |
224 | param_env: ty::ParamEnv<'tcx>, | |
225 | ) -> Self { | |
226 | let tcx = infcx.tcx; | |
532ac7d7 | 227 | let mir_hir_id = tcx.hir().as_local_hir_id(mir_def_id).unwrap(); |
dfeec247 | 228 | UniversalRegionsBuilder { infcx, mir_def_id, mir_hir_id, param_env }.build() |
ff7c6d11 XL |
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( | |
dc9dc135 | 241 | tcx: TyCtxt<'tcx>, |
532ac7d7 | 242 | closure_substs: SubstsRef<'tcx>, |
ff7c6d11 | 243 | expected_num_vars: usize, |
8faf50e0 | 244 | closure_base_def_id: DefId, |
ff7c6d11 XL |
245 | ) -> IndexVec<RegionVid, ty::Region<'tcx>> { |
246 | let mut region_mapping = IndexVec::with_capacity(expected_num_vars); | |
48663c56 | 247 | region_mapping.push(tcx.lifetimes.re_static); |
0bf4aa26 | 248 | tcx.for_each_free_region(&closure_substs, |fr| { |
ff7c6d11 XL |
249 | region_mapping.push(fr); |
250 | }); | |
251 | ||
b7449926 XL |
252 | for_each_late_bound_region_defined_on(tcx, closure_base_def_id, |r| { |
253 | region_mapping.push(r); | |
254 | }); | |
8faf50e0 | 255 | |
ff7c6d11 XL |
256 | assert_eq!( |
257 | region_mapping.len(), | |
258 | expected_num_vars, | |
259 | "index vec had unexpected number of variables" | |
260 | ); | |
261 | ||
262 | region_mapping | |
263 | } | |
264 | ||
9fa01778 | 265 | /// Returns `true` if `r` is a member of this set of universal regions. |
ff7c6d11 | 266 | pub fn is_universal_region(&self, r: RegionVid) -> bool { |
83c7162d | 267 | (FIRST_GLOBAL_INDEX..self.num_universals).contains(&r.index()) |
ff7c6d11 XL |
268 | } |
269 | ||
270 | /// Classifies `r` as a universal region, returning `None` if this | |
271 | /// is not a member of this set of universal regions. | |
272 | pub fn region_classification(&self, r: RegionVid) -> Option<RegionClassification> { | |
273 | let index = r.index(); | |
83c7162d | 274 | if (FIRST_GLOBAL_INDEX..self.first_extern_index).contains(&index) { |
ff7c6d11 | 275 | Some(RegionClassification::Global) |
83c7162d | 276 | } else if (self.first_extern_index..self.first_local_index).contains(&index) { |
ff7c6d11 | 277 | Some(RegionClassification::External) |
83c7162d | 278 | } else if (self.first_local_index..self.num_universals).contains(&index) { |
ff7c6d11 XL |
279 | Some(RegionClassification::Local) |
280 | } else { | |
281 | None | |
282 | } | |
283 | } | |
284 | ||
285 | /// Returns an iterator over all the RegionVids corresponding to | |
286 | /// universally quantified free regions. | |
287 | pub fn universal_regions(&self) -> impl Iterator<Item = RegionVid> { | |
288 | (FIRST_GLOBAL_INDEX..self.num_universals).map(RegionVid::new) | |
289 | } | |
290 | ||
9fa01778 | 291 | /// Returns `true` if `r` is classified as an local region. |
ff7c6d11 XL |
292 | pub fn is_local_free_region(&self, r: RegionVid) -> bool { |
293 | self.region_classification(r) == Some(RegionClassification::Local) | |
294 | } | |
295 | ||
296 | /// Returns the number of universal regions created in any category. | |
297 | pub fn len(&self) -> usize { | |
298 | self.num_universals | |
299 | } | |
300 | ||
ff7c6d11 XL |
301 | /// Returns the number of global plus external universal regions. |
302 | /// For closures, these are the regions that appear free in the | |
303 | /// closure type (versus those bound in the closure | |
304 | /// signature). They are therefore the regions between which the | |
305 | /// closure may impose constraints that its creator must verify. | |
306 | pub fn num_global_and_external_regions(&self) -> usize { | |
307 | self.first_local_index | |
308 | } | |
309 | ||
9fa01778 | 310 | /// Gets an iterator over all the early-bound regions that have names. |
ff7c6d11 XL |
311 | pub fn named_universal_regions<'s>( |
312 | &'s self, | |
313 | ) -> impl Iterator<Item = (ty::Region<'tcx>, ty::RegionVid)> + 's { | |
314 | self.indices.indices.iter().map(|(&r, &v)| (r, v)) | |
315 | } | |
316 | ||
317 | /// See `UniversalRegionIndices::to_region_vid`. | |
318 | pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { | |
319 | self.indices.to_region_vid(r) | |
320 | } | |
b7449926 XL |
321 | |
322 | /// As part of the NLL unit tests, you can annotate a function with | |
323 | /// `#[rustc_regions]`, and we will emit information about the region | |
324 | /// inference context and -- in particular -- the external constraints | |
325 | /// that this region imposes on others. The methods in this file | |
326 | /// handle the part about dumping the inference context internal | |
327 | /// state. | |
dc9dc135 | 328 | crate fn annotate(&self, tcx: TyCtxt<'tcx>, err: &mut DiagnosticBuilder<'_>) { |
b7449926 XL |
329 | match self.defining_ty { |
330 | DefiningTy::Closure(def_id, substs) => { | |
331 | err.note(&format!( | |
60c5eb7d XL |
332 | "defining type: {} with closure substs {:#?}", |
333 | tcx.def_path_str_with_substs(def_id, substs), | |
334 | &substs[tcx.generics_of(def_id).parent_count..], | |
b7449926 XL |
335 | )); |
336 | ||
337 | // FIXME: It'd be nice to print the late-bound regions | |
338 | // here, but unfortunately these wind up stored into | |
339 | // tests, and the resulting print-outs include def-ids | |
340 | // and other things that are not stable across tests! | |
341 | // So we just include the region-vid. Annoying. | |
342 | let closure_base_def_id = tcx.closure_base_def_id(def_id); | |
343 | for_each_late_bound_region_defined_on(tcx, closure_base_def_id, |r| { | |
dfeec247 | 344 | err.note(&format!("late-bound region is {:?}", self.to_region_vid(r),)); |
b7449926 XL |
345 | }); |
346 | } | |
347 | DefiningTy::Generator(def_id, substs, _) => { | |
348 | err.note(&format!( | |
60c5eb7d XL |
349 | "defining type: {} with generator substs {:#?}", |
350 | tcx.def_path_str_with_substs(def_id, substs), | |
351 | &substs[tcx.generics_of(def_id).parent_count..], | |
b7449926 XL |
352 | )); |
353 | ||
354 | // FIXME: As above, we'd like to print out the region | |
355 | // `r` but doing so is not stable across architectures | |
356 | // and so forth. | |
357 | let closure_base_def_id = tcx.closure_base_def_id(def_id); | |
358 | for_each_late_bound_region_defined_on(tcx, closure_base_def_id, |r| { | |
dfeec247 | 359 | err.note(&format!("late-bound region is {:?}", self.to_region_vid(r),)); |
b7449926 XL |
360 | }); |
361 | } | |
362 | DefiningTy::FnDef(def_id, substs) => { | |
363 | err.note(&format!( | |
60c5eb7d XL |
364 | "defining type: {}", |
365 | tcx.def_path_str_with_substs(def_id, substs), | |
b7449926 XL |
366 | )); |
367 | } | |
368 | DefiningTy::Const(def_id, substs) => { | |
369 | err.note(&format!( | |
60c5eb7d XL |
370 | "defining constant type: {}", |
371 | tcx.def_path_str_with_substs(def_id, substs), | |
b7449926 XL |
372 | )); |
373 | } | |
374 | } | |
375 | } | |
ff7c6d11 XL |
376 | } |
377 | ||
dc9dc135 XL |
378 | struct UniversalRegionsBuilder<'cx, 'tcx> { |
379 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
ff7c6d11 XL |
380 | mir_def_id: DefId, |
381 | mir_hir_id: HirId, | |
ff7c6d11 | 382 | param_env: ty::ParamEnv<'tcx>, |
ff7c6d11 XL |
383 | } |
384 | ||
385 | const FR: NLLRegionVariableOrigin = NLLRegionVariableOrigin::FreeRegion; | |
386 | ||
dc9dc135 | 387 | impl<'cx, 'tcx> UniversalRegionsBuilder<'cx, 'tcx> { |
8faf50e0 | 388 | fn build(self) -> UniversalRegions<'tcx> { |
ff7c6d11 XL |
389 | debug!("build(mir_def_id={:?})", self.mir_def_id); |
390 | ||
391 | let param_env = self.param_env; | |
392 | debug!("build: param_env={:?}", param_env); | |
393 | ||
394 | assert_eq!(FIRST_GLOBAL_INDEX, self.infcx.num_region_vars()); | |
395 | ||
396 | // Create the "global" region that is always free in all contexts: 'static. | |
397 | let fr_static = self.infcx.next_nll_region_var(FR).to_region_vid(); | |
398 | ||
399 | // We've now added all the global regions. The next ones we | |
400 | // add will be external. | |
401 | let first_extern_index = self.infcx.num_region_vars(); | |
402 | ||
403 | let defining_ty = self.defining_ty(); | |
404 | debug!("build: defining_ty={:?}", defining_ty); | |
405 | ||
406 | let mut indices = self.compute_indices(fr_static, defining_ty); | |
407 | debug!("build: indices={:?}", indices); | |
408 | ||
8faf50e0 XL |
409 | let closure_base_def_id = self.infcx.tcx.closure_base_def_id(self.mir_def_id); |
410 | ||
411 | // If this is a closure or generator, then the late-bound regions from the enclosing | |
412 | // function are actually external regions to us. For example, here, 'a is not local | |
413 | // to the closure c (although it is local to the fn foo): | |
414 | // fn foo<'a>() { | |
415 | // let c = || { let x: &'a u32 = ...; } | |
416 | // } | |
417 | if self.mir_def_id != closure_base_def_id { | |
dfeec247 | 418 | self.infcx.replace_late_bound_regions_with_nll_infer_vars(self.mir_def_id, &mut indices) |
8faf50e0 XL |
419 | } |
420 | ||
ff7c6d11 XL |
421 | let bound_inputs_and_output = self.compute_inputs_and_output(&indices, defining_ty); |
422 | ||
423 | // "Liberate" the late-bound regions. These correspond to | |
424 | // "local" free regions. | |
425 | let first_local_index = self.infcx.num_region_vars(); | |
426 | let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars( | |
427 | FR, | |
428 | self.mir_def_id, | |
429 | &bound_inputs_and_output, | |
430 | &mut indices, | |
431 | ); | |
8faf50e0 XL |
432 | // Converse of above, if this is a function then the late-bound regions declared on its |
433 | // signature are local to the fn. | |
434 | if self.mir_def_id == closure_base_def_id { | |
b7449926 XL |
435 | self.infcx |
436 | .replace_late_bound_regions_with_nll_infer_vars(self.mir_def_id, &mut indices); | |
ff7c6d11 XL |
437 | } |
438 | ||
e74abb32 XL |
439 | let (unnormalized_output_ty, mut unnormalized_input_tys) = |
440 | inputs_and_output.split_last().unwrap(); | |
441 | ||
442 | // C-variadic fns also have a `VaList` input that's not listed in the signature | |
443 | // (as it's created inside the body itself, not passed in from outside). | |
444 | if let DefiningTy::FnDef(def_id, _) = defining_ty { | |
445 | if self.infcx.tcx.fn_sig(def_id).c_variadic() { | |
446 | let va_list_did = self.infcx.tcx.require_lang_item( | |
447 | lang_items::VaListTypeLangItem, | |
dfeec247 | 448 | Some(self.infcx.tcx.def_span(self.mir_def_id)), |
e74abb32 | 449 | ); |
dfeec247 XL |
450 | let region = self |
451 | .infcx | |
452 | .tcx | |
453 | .mk_region(ty::ReVar(self.infcx.next_nll_region_var(FR).to_region_vid())); | |
454 | let va_list_ty = | |
455 | self.infcx.tcx.type_of(va_list_did).subst(self.infcx.tcx, &[region.into()]); | |
e74abb32 XL |
456 | |
457 | unnormalized_input_tys = self.infcx.tcx.mk_type_list( | |
dfeec247 | 458 | unnormalized_input_tys.iter().copied().chain(iter::once(va_list_ty)), |
e74abb32 XL |
459 | ); |
460 | } | |
461 | } | |
462 | ||
8faf50e0 XL |
463 | let fr_fn_body = self.infcx.next_nll_region_var(FR).to_region_vid(); |
464 | let num_universals = self.infcx.num_region_vars(); | |
ff7c6d11 | 465 | |
dfeec247 XL |
466 | debug!("build: global regions = {}..{}", FIRST_GLOBAL_INDEX, first_extern_index); |
467 | debug!("build: extern regions = {}..{}", first_extern_index, first_local_index); | |
468 | debug!("build: local regions = {}..{}", first_local_index, num_universals); | |
ff7c6d11 | 469 | |
2c00a5a8 | 470 | let yield_ty = match defining_ty { |
ba9703b0 | 471 | DefiningTy::Generator(_, substs, _) => Some(substs.as_generator().yield_ty()), |
2c00a5a8 XL |
472 | _ => None, |
473 | }; | |
474 | ||
ff7c6d11 XL |
475 | UniversalRegions { |
476 | indices, | |
477 | fr_static, | |
478 | fr_fn_body, | |
479 | first_extern_index, | |
480 | first_local_index, | |
481 | num_universals, | |
482 | defining_ty, | |
483 | unnormalized_output_ty, | |
484 | unnormalized_input_tys, | |
74b04a01 | 485 | yield_ty, |
ff7c6d11 XL |
486 | } |
487 | } | |
488 | ||
489 | /// Returns the "defining type" of the current MIR; | |
490 | /// see `DefiningTy` for details. | |
491 | fn defining_ty(&self) -> DefiningTy<'tcx> { | |
492 | let tcx = self.infcx.tcx; | |
ff7c6d11 XL |
493 | let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id); |
494 | ||
dc9dc135 | 495 | match tcx.hir().body_owner_kind(self.mir_hir_id) { |
dfeec247 | 496 | BodyOwnerKind::Closure | BodyOwnerKind::Fn => { |
2c00a5a8 XL |
497 | let defining_ty = if self.mir_def_id == closure_base_def_id { |
498 | tcx.type_of(closure_base_def_id) | |
499 | } else { | |
500 | let tables = tcx.typeck_tables_of(self.mir_def_id); | |
9fa01778 | 501 | tables.node_type(self.mir_hir_id) |
2c00a5a8 XL |
502 | }; |
503 | ||
8faf50e0 XL |
504 | debug!("defining_ty (pre-replacement): {:?}", defining_ty); |
505 | ||
dfeec247 XL |
506 | let defining_ty = |
507 | self.infcx.replace_free_regions_with_nll_infer_vars(FR, &defining_ty); | |
2c00a5a8 | 508 | |
e74abb32 | 509 | match defining_ty.kind { |
b7449926 XL |
510 | ty::Closure(def_id, substs) => DefiningTy::Closure(def_id, substs), |
511 | ty::Generator(def_id, substs, movability) => { | |
94b46f34 | 512 | DefiningTy::Generator(def_id, substs, movability) |
2c00a5a8 | 513 | } |
b7449926 | 514 | ty::FnDef(def_id, substs) => DefiningTy::FnDef(def_id, substs), |
2c00a5a8 XL |
515 | _ => span_bug!( |
516 | tcx.def_span(self.mir_def_id), | |
517 | "expected defining type for `{:?}`: `{:?}`", | |
518 | self.mir_def_id, | |
519 | defining_ty | |
520 | ), | |
ff7c6d11 | 521 | } |
2c00a5a8 XL |
522 | } |
523 | ||
524 | BodyOwnerKind::Const | BodyOwnerKind::Static(..) => { | |
525 | assert_eq!(closure_base_def_id, self.mir_def_id); | |
532ac7d7 | 526 | let identity_substs = InternalSubsts::identity_for_item(tcx, closure_base_def_id); |
dfeec247 XL |
527 | let substs = |
528 | self.infcx.replace_free_regions_with_nll_infer_vars(FR, &identity_substs); | |
2c00a5a8 XL |
529 | DefiningTy::Const(self.mir_def_id, substs) |
530 | } | |
ff7c6d11 XL |
531 | } |
532 | } | |
533 | ||
534 | /// Builds a hashmap that maps from the universal regions that are | |
535 | /// in scope (as a `ty::Region<'tcx>`) to their indices (as a | |
536 | /// `RegionVid`). The map returned by this function contains only | |
537 | /// the early-bound regions. | |
538 | fn compute_indices( | |
539 | &self, | |
540 | fr_static: RegionVid, | |
541 | defining_ty: DefiningTy<'tcx>, | |
542 | ) -> UniversalRegionIndices<'tcx> { | |
543 | let tcx = self.infcx.tcx; | |
ff7c6d11 | 544 | let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id); |
e74abb32 | 545 | let identity_substs = InternalSubsts::identity_for_item(tcx, closure_base_def_id); |
ff7c6d11 | 546 | let fr_substs = match defining_ty { |
dfeec247 | 547 | DefiningTy::Closure(_, ref substs) | DefiningTy::Generator(_, ref substs, _) => { |
ff7c6d11 XL |
548 | // In the case of closures, we rely on the fact that |
549 | // the first N elements in the ClosureSubsts are | |
550 | // inherited from the `closure_base_def_id`. | |
551 | // Therefore, when we zip together (below) with | |
552 | // `identity_substs`, we will get only those regions | |
553 | // that correspond to early-bound regions declared on | |
554 | // the `closure_base_def_id`. | |
94b46f34 XL |
555 | assert!(substs.len() >= identity_substs.len()); |
556 | assert_eq!(substs.regions().count(), identity_substs.regions().count()); | |
557 | substs | |
ff7c6d11 XL |
558 | } |
559 | ||
2c00a5a8 | 560 | DefiningTy::FnDef(_, substs) | DefiningTy::Const(_, substs) => substs, |
ff7c6d11 XL |
561 | }; |
562 | ||
e74abb32 | 563 | let global_mapping = iter::once((tcx.lifetimes.re_static, fr_static)); |
dfeec247 XL |
564 | let subst_mapping = |
565 | identity_substs.regions().zip(fr_substs.regions().map(|r| r.to_region_vid())); | |
ff7c6d11 | 566 | |
dfeec247 | 567 | UniversalRegionIndices { indices: global_mapping.chain(subst_mapping).collect() } |
ff7c6d11 XL |
568 | } |
569 | ||
570 | fn compute_inputs_and_output( | |
571 | &self, | |
572 | indices: &UniversalRegionIndices<'tcx>, | |
573 | defining_ty: DefiningTy<'tcx>, | |
b7449926 | 574 | ) -> ty::Binder<&'tcx ty::List<Ty<'tcx>>> { |
ff7c6d11 XL |
575 | let tcx = self.infcx.tcx; |
576 | match defining_ty { | |
577 | DefiningTy::Closure(def_id, substs) => { | |
578 | assert_eq!(self.mir_def_id, def_id); | |
ba9703b0 | 579 | let closure_sig = substs.as_closure().sig(); |
ff7c6d11 XL |
580 | let inputs_and_output = closure_sig.inputs_and_output(); |
581 | let closure_ty = tcx.closure_env_ty(def_id, substs).unwrap(); | |
dfeec247 XL |
582 | ty::Binder::fuse(closure_ty, inputs_and_output, |closure_ty, inputs_and_output| { |
583 | // The "inputs" of the closure in the | |
584 | // signature appear as a tuple. The MIR side | |
585 | // flattens this tuple. | |
586 | let (&output, tuplized_inputs) = inputs_and_output.split_last().unwrap(); | |
587 | assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs"); | |
588 | let inputs = match tuplized_inputs[0].kind { | |
589 | ty::Tuple(inputs) => inputs, | |
590 | _ => bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]), | |
591 | }; | |
592 | ||
593 | tcx.mk_type_list( | |
594 | iter::once(closure_ty) | |
595 | .chain(inputs.iter().map(|k| k.expect_ty())) | |
596 | .chain(iter::once(output)), | |
597 | ) | |
598 | }) | |
ff7c6d11 XL |
599 | } |
600 | ||
94b46f34 | 601 | DefiningTy::Generator(def_id, substs, movability) => { |
ff7c6d11 | 602 | assert_eq!(self.mir_def_id, def_id); |
ba9703b0 XL |
603 | let resume_ty = substs.as_generator().resume_ty(); |
604 | let output = substs.as_generator().return_ty(); | |
94b46f34 | 605 | let generator_ty = tcx.mk_generator(def_id, substs, movability); |
74b04a01 XL |
606 | let inputs_and_output = |
607 | self.infcx.tcx.intern_type_list(&[generator_ty, resume_ty, output]); | |
ff7c6d11 XL |
608 | ty::Binder::dummy(inputs_and_output) |
609 | } | |
610 | ||
611 | DefiningTy::FnDef(def_id, _) => { | |
612 | let sig = tcx.fn_sig(def_id); | |
613 | let sig = indices.fold_to_region_vids(tcx, &sig); | |
614 | sig.inputs_and_output() | |
615 | } | |
616 | ||
2c00a5a8 XL |
617 | DefiningTy::Const(def_id, _) => { |
618 | // For a constant body, there are no inputs, and one | |
619 | // "output" (the type of the constant). | |
620 | assert_eq!(self.mir_def_id, def_id); | |
621 | let ty = tcx.type_of(def_id); | |
622 | let ty = indices.fold_to_region_vids(tcx, &ty); | |
94b46f34 | 623 | ty::Binder::dummy(tcx.intern_type_list(&[ty])) |
2c00a5a8 | 624 | } |
ff7c6d11 XL |
625 | } |
626 | } | |
ff7c6d11 XL |
627 | } |
628 | ||
629 | trait InferCtxtExt<'tcx> { | |
630 | fn replace_free_regions_with_nll_infer_vars<T>( | |
631 | &self, | |
632 | origin: NLLRegionVariableOrigin, | |
633 | value: &T, | |
634 | ) -> T | |
635 | where | |
636 | T: TypeFoldable<'tcx>; | |
637 | ||
638 | fn replace_bound_regions_with_nll_infer_vars<T>( | |
639 | &self, | |
640 | origin: NLLRegionVariableOrigin, | |
641 | all_outlive_scope: DefId, | |
642 | value: &ty::Binder<T>, | |
643 | indices: &mut UniversalRegionIndices<'tcx>, | |
644 | ) -> T | |
645 | where | |
646 | T: TypeFoldable<'tcx>; | |
8faf50e0 | 647 | |
8faf50e0 XL |
648 | fn replace_late_bound_regions_with_nll_infer_vars( |
649 | &self, | |
650 | mir_def_id: DefId, | |
b7449926 | 651 | indices: &mut UniversalRegionIndices<'tcx>, |
8faf50e0 | 652 | ); |
ff7c6d11 XL |
653 | } |
654 | ||
dc9dc135 | 655 | impl<'cx, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'cx, 'tcx> { |
ff7c6d11 XL |
656 | fn replace_free_regions_with_nll_infer_vars<T>( |
657 | &self, | |
658 | origin: NLLRegionVariableOrigin, | |
659 | value: &T, | |
660 | ) -> T | |
661 | where | |
662 | T: TypeFoldable<'tcx>, | |
663 | { | |
dfeec247 | 664 | self.tcx.fold_regions(value, &mut false, |_region, _depth| self.next_nll_region_var(origin)) |
ff7c6d11 XL |
665 | } |
666 | ||
667 | fn replace_bound_regions_with_nll_infer_vars<T>( | |
668 | &self, | |
669 | origin: NLLRegionVariableOrigin, | |
670 | all_outlive_scope: DefId, | |
671 | value: &ty::Binder<T>, | |
672 | indices: &mut UniversalRegionIndices<'tcx>, | |
673 | ) -> T | |
674 | where | |
675 | T: TypeFoldable<'tcx>, | |
676 | { | |
0531ce1d XL |
677 | debug!( |
678 | "replace_bound_regions_with_nll_infer_vars(value={:?}, all_outlive_scope={:?})", | |
8faf50e0 | 679 | value, all_outlive_scope, |
0531ce1d | 680 | ); |
ff7c6d11 | 681 | let (value, _map) = self.tcx.replace_late_bound_regions(value, |br| { |
b7449926 | 682 | debug!("replace_bound_regions_with_nll_infer_vars: br={:?}", br); |
ff7c6d11 XL |
683 | let liberated_region = self.tcx.mk_region(ty::ReFree(ty::FreeRegion { |
684 | scope: all_outlive_scope, | |
685 | bound_region: br, | |
686 | })); | |
687 | let region_vid = self.next_nll_region_var(origin); | |
688 | indices.insert_late_bound_region(liberated_region, region_vid.to_region_vid()); | |
8faf50e0 | 689 | debug!( |
b7449926 | 690 | "replace_bound_regions_with_nll_infer_vars: liberated_region={:?} => {:?}", |
8faf50e0 XL |
691 | liberated_region, region_vid |
692 | ); | |
ff7c6d11 XL |
693 | region_vid |
694 | }); | |
695 | value | |
696 | } | |
8faf50e0 XL |
697 | |
698 | /// Finds late-bound regions that do not appear in the parameter listing and adds them to the | |
699 | /// indices vector. Typically, we identify late-bound regions as we process the inputs and | |
700 | /// outputs of the closure/function. However, sometimes there are late-bound regions which do | |
701 | /// not appear in the fn parameters but which are nonetheless in scope. The simplest case of | |
9fa01778 | 702 | /// this are unused functions, like fn foo<'a>() { } (see e.g., #51351). Despite not being used, |
8faf50e0 XL |
703 | /// users can still reference these regions (e.g., let x: &'a u32 = &22;), so we need to create |
704 | /// entries for them and store them in the indices map. This code iterates over the complete | |
705 | /// set of late-bound regions and checks for any that we have not yet seen, adding them to the | |
706 | /// inputs vector. | |
707 | fn replace_late_bound_regions_with_nll_infer_vars( | |
708 | &self, | |
709 | mir_def_id: DefId, | |
710 | indices: &mut UniversalRegionIndices<'tcx>, | |
711 | ) { | |
dfeec247 | 712 | debug!("replace_late_bound_regions_with_nll_infer_vars(mir_def_id={:?})", mir_def_id); |
8faf50e0 XL |
713 | let closure_base_def_id = self.tcx.closure_base_def_id(mir_def_id); |
714 | for_each_late_bound_region_defined_on(self.tcx, closure_base_def_id, |r| { | |
b7449926 | 715 | debug!("replace_late_bound_regions_with_nll_infer_vars: r={:?}", r); |
8faf50e0 XL |
716 | if !indices.indices.contains_key(&r) { |
717 | let region_vid = self.next_nll_region_var(FR); | |
718 | indices.insert_late_bound_region(r, region_vid.to_region_vid()); | |
b7449926 XL |
719 | } |
720 | }); | |
8faf50e0 | 721 | } |
ff7c6d11 XL |
722 | } |
723 | ||
724 | impl<'tcx> UniversalRegionIndices<'tcx> { | |
725 | /// Initially, the `UniversalRegionIndices` map contains only the | |
726 | /// early-bound regions in scope. Once that is all setup, we come | |
727 | /// in later and instantiate the late-bound regions, and then we | |
728 | /// insert the `ReFree` version of those into the map as | |
729 | /// well. These are used for error reporting. | |
8faf50e0 XL |
730 | fn insert_late_bound_region(&mut self, r: ty::Region<'tcx>, vid: ty::RegionVid) { |
731 | debug!("insert_late_bound_region({:?}, {:?})", r, vid); | |
ff7c6d11 XL |
732 | self.indices.insert(r, vid); |
733 | } | |
734 | ||
735 | /// Converts `r` into a local inference variable: `r` can either | |
736 | /// by a `ReVar` (i.e., already a reference to an inference | |
737 | /// variable) or it can be `'static` or some early-bound | |
738 | /// region. This is useful when taking the results from | |
739 | /// type-checking and trait-matching, which may sometimes | |
740 | /// reference those regions from the `ParamEnv`. It is also used | |
741 | /// during initialization. Relies on the `indices` map having been | |
742 | /// fully initialized. | |
743 | pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { | |
2c00a5a8 XL |
744 | if let ty::ReVar(..) = r { |
745 | r.to_region_vid() | |
746 | } else { | |
dfeec247 XL |
747 | *self |
748 | .indices | |
8faf50e0 XL |
749 | .get(&r) |
750 | .unwrap_or_else(|| bug!("cannot convert `{:?}` to a region vid", r)) | |
ff7c6d11 XL |
751 | } |
752 | } | |
753 | ||
9fa01778 | 754 | /// Replaces all free regions in `value` with region vids, as |
ff7c6d11 | 755 | /// returned by `to_region_vid`. |
dc9dc135 | 756 | pub fn fold_to_region_vids<T>(&self, tcx: TyCtxt<'tcx>, value: &T) -> T |
ff7c6d11 XL |
757 | where |
758 | T: TypeFoldable<'tcx>, | |
759 | { | |
760 | tcx.fold_regions(value, &mut false, |region, _| { | |
761 | tcx.mk_region(ty::ReVar(self.to_region_vid(region))) | |
762 | }) | |
763 | } | |
764 | } | |
765 | ||
8faf50e0 XL |
766 | /// Iterates over the late-bound regions defined on fn_def_id and |
767 | /// invokes `f` with the liberated form of each one. | |
768 | fn for_each_late_bound_region_defined_on<'tcx>( | |
dc9dc135 | 769 | tcx: TyCtxt<'tcx>, |
8faf50e0 | 770 | fn_def_id: DefId, |
b7449926 XL |
771 | mut f: impl FnMut(ty::Region<'tcx>), |
772 | ) { | |
ba9703b0 | 773 | if let Some(late_bounds) = tcx.is_late_bound_map(fn_def_id.expect_local()) { |
8faf50e0 | 774 | for late_bound in late_bounds.iter() { |
ba9703b0 | 775 | let hir_id = HirId { owner: fn_def_id.expect_local(), local_id: *late_bound }; |
e74abb32 | 776 | let name = tcx.hir().name(hir_id); |
416331ca | 777 | let region_def_id = tcx.hir().local_def_id(hir_id); |
8faf50e0 XL |
778 | let liberated_region = tcx.mk_region(ty::ReFree(ty::FreeRegion { |
779 | scope: fn_def_id, | |
780 | bound_region: ty::BoundRegion::BrNamed(region_def_id, name), | |
781 | })); | |
782 | f(liberated_region); | |
783 | } | |
ff7c6d11 XL |
784 | } |
785 | } |