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