rustc_borrowck/
universal_regions.rs

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//!
8//! here we would return a map assigning each of `{'a, 'b, 'c}`
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
15#![allow(rustc::diagnostic_outside_of_impl)]
16#![allow(rustc::untranslatable_diagnostic)]
17
18use std::cell::Cell;
19use std::iter;
20
21use rustc_data_structures::fx::FxIndexMap;
22use rustc_errors::Diag;
23use rustc_hir::BodyOwnerKind;
24use rustc_hir::def::DefKind;
25use rustc_hir::def_id::{DefId, LocalDefId};
26use rustc_hir::lang_items::LangItem;
27use rustc_index::IndexVec;
28use rustc_infer::infer::NllRegionVariableOrigin;
29use rustc_macros::extension;
30use rustc_middle::ty::print::with_no_trimmed_paths;
31use rustc_middle::ty::{
32    self, GenericArgs, GenericArgsRef, InlineConstArgs, InlineConstArgsParts, RegionVid, Ty,
33    TyCtxt, TypeFoldable, TypeVisitableExt, fold_regions,
34};
35use rustc_middle::{bug, span_bug};
36use rustc_span::{ErrorGuaranteed, kw, sym};
37use tracing::{debug, instrument};
38
39use crate::BorrowckInferCtxt;
40use crate::renumber::RegionCtxt;
41
42#[derive(Debug)]
43pub(crate) 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,
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 coroutine, this is the
70    /// closure type, but for a top-level function it's the `FnDef`.
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    /// N.B., 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    /// N.B., associated types in these types have not been normalized,
84    /// as the name suggests. =)
85    pub unnormalized_input_tys: &'tcx [Ty<'tcx>],
86
87    pub yield_ty: Option<Ty<'tcx>>,
88
89    pub resume_ty: Option<Ty<'tcx>>,
90}
91
92/// The "defining type" for this MIR. The key feature of the "defining
93/// type" is that it contains the information needed to derive all the
94/// universal regions that are in scope as well as the types of the
95/// inputs/output from the MIR. In general, early-bound universal
96/// regions appear free in the defining type and late-bound regions
97/// appear bound in the signature.
98#[derive(Copy, Clone, Debug)]
99pub(crate) enum DefiningTy<'tcx> {
100    /// The MIR is a closure. The signature is found via
101    /// `ClosureArgs::closure_sig_ty`.
102    Closure(DefId, GenericArgsRef<'tcx>),
103
104    /// The MIR is a coroutine. The signature is that coroutines take
105    /// no parameters and return the result of
106    /// `ClosureArgs::coroutine_return_ty`.
107    Coroutine(DefId, GenericArgsRef<'tcx>),
108
109    /// The MIR is a special kind of closure that returns coroutines.
110    ///
111    /// See the documentation on `CoroutineClosureSignature` for details
112    /// on how to construct the callable signature of the coroutine from
113    /// its args.
114    CoroutineClosure(DefId, GenericArgsRef<'tcx>),
115
116    /// The MIR is a fn item with the given `DefId` and args. The signature
117    /// of the function can be bound then with the `fn_sig` query.
118    FnDef(DefId, GenericArgsRef<'tcx>),
119
120    /// The MIR represents some form of constant. The signature then
121    /// is that it has no inputs and a single return value, which is
122    /// the value of the constant.
123    Const(DefId, GenericArgsRef<'tcx>),
124
125    /// The MIR represents an inline const. The signature has no inputs and a
126    /// single return value found via `InlineConstArgs::ty`.
127    InlineConst(DefId, GenericArgsRef<'tcx>),
128
129    // Fake body for a global asm. Not particularly useful or interesting,
130    // but we need it so we can properly store the typeck results of the asm
131    // operands, which aren't associated with a body otherwise.
132    GlobalAsm(DefId),
133}
134
135impl<'tcx> DefiningTy<'tcx> {
136    /// Returns a list of all the upvar types for this MIR. If this is
137    /// not a closure or coroutine, there are no upvars, and hence it
138    /// will be an empty list. The order of types in this list will
139    /// match up with the upvar order in the HIR, typesystem, and MIR.
140    pub(crate) fn upvar_tys(self) -> &'tcx ty::List<Ty<'tcx>> {
141        match self {
142            DefiningTy::Closure(_, args) => args.as_closure().upvar_tys(),
143            DefiningTy::CoroutineClosure(_, args) => args.as_coroutine_closure().upvar_tys(),
144            DefiningTy::Coroutine(_, args) => args.as_coroutine().upvar_tys(),
145            DefiningTy::FnDef(..)
146            | DefiningTy::Const(..)
147            | DefiningTy::InlineConst(..)
148            | DefiningTy::GlobalAsm(_) => ty::List::empty(),
149        }
150    }
151
152    /// Number of implicit inputs -- notably the "environment"
153    /// parameter for closures -- that appear in MIR but not in the
154    /// user's code.
155    pub(crate) fn implicit_inputs(self) -> usize {
156        match self {
157            DefiningTy::Closure(..)
158            | DefiningTy::CoroutineClosure(..)
159            | DefiningTy::Coroutine(..) => 1,
160            DefiningTy::FnDef(..)
161            | DefiningTy::Const(..)
162            | DefiningTy::InlineConst(..)
163            | DefiningTy::GlobalAsm(_) => 0,
164        }
165    }
166
167    pub(crate) fn is_fn_def(&self) -> bool {
168        matches!(*self, DefiningTy::FnDef(..))
169    }
170
171    pub(crate) fn is_const(&self) -> bool {
172        matches!(*self, DefiningTy::Const(..) | DefiningTy::InlineConst(..))
173    }
174
175    pub(crate) fn def_id(&self) -> DefId {
176        match *self {
177            DefiningTy::Closure(def_id, ..)
178            | DefiningTy::CoroutineClosure(def_id, ..)
179            | DefiningTy::Coroutine(def_id, ..)
180            | DefiningTy::FnDef(def_id, ..)
181            | DefiningTy::Const(def_id, ..)
182            | DefiningTy::InlineConst(def_id, ..)
183            | DefiningTy::GlobalAsm(def_id) => def_id,
184        }
185    }
186
187    /// Returns the args of the `DefiningTy`. These are equivalent to the identity
188    /// substs of the body, but replaced with region vids.
189    pub(crate) fn args(&self) -> ty::GenericArgsRef<'tcx> {
190        match *self {
191            DefiningTy::Closure(_, args)
192            | DefiningTy::Coroutine(_, args)
193            | DefiningTy::CoroutineClosure(_, args)
194            | DefiningTy::FnDef(_, args)
195            | DefiningTy::Const(_, args)
196            | DefiningTy::InlineConst(_, args) => args,
197            DefiningTy::GlobalAsm(_) => ty::List::empty(),
198        }
199    }
200}
201
202#[derive(Debug)]
203struct UniversalRegionIndices<'tcx> {
204    /// For those regions that may appear in the parameter environment
205    /// ('static and early-bound regions), we maintain a map from the
206    /// `ty::Region` to the internal `RegionVid` we are using. This is
207    /// used because trait matching and type-checking will feed us
208    /// region constraints that reference those regions and we need to
209    /// be able to map them to our internal `RegionVid`. This is
210    /// basically equivalent to an `GenericArgs`, except that it also
211    /// contains an entry for `ReStatic` -- it might be nice to just
212    /// use an args, and then handle `ReStatic` another way.
213    indices: FxIndexMap<ty::Region<'tcx>, RegionVid>,
214
215    /// The vid assigned to `'static`. Used only for diagnostics.
216    pub fr_static: RegionVid,
217
218    /// Whether we've encountered an error region. If we have, cancel all
219    /// outlives errors, as they are likely bogus.
220    pub tainted_by_errors: Cell<Option<ErrorGuaranteed>>,
221}
222
223#[derive(Debug, PartialEq)]
224pub(crate) enum RegionClassification {
225    /// A **global** region is one that can be named from
226    /// anywhere. There is only one, `'static`.
227    Global,
228
229    /// An **external** region is only relevant for
230    /// closures, coroutines, and inline consts. In that
231    /// case, it refers to regions that are free in the type
232    /// -- basically, something bound in the surrounding context.
233    ///
234    /// Consider this example:
235    ///
236    /// ```ignore (pseudo-rust)
237    /// fn foo<'a, 'b>(a: &'a u32, b: &'b u32, c: &'static u32) {
238    ///   let closure = for<'x> |x: &'x u32| { .. };
239    ///    //           ^^^^^^^ pretend this were legal syntax
240    ///    //                   for declaring a late-bound region in
241    ///    //                   a closure signature
242    /// }
243    /// ```
244    ///
245    /// Here, the lifetimes `'a` and `'b` would be **external** to the
246    /// closure.
247    ///
248    /// If we are not analyzing a closure/coroutine/inline-const,
249    /// there are no external lifetimes.
250    External,
251
252    /// A **local** lifetime is one about which we know the full set
253    /// of relevant constraints (that is, relationships to other named
254    /// regions). For a closure, this includes any region bound in
255    /// the closure's signature. For a fn item, this includes all
256    /// regions other than global ones.
257    ///
258    /// Continuing with the example from `External`, if we were
259    /// analyzing the closure, then `'x` would be local (and `'a` and
260    /// `'b` are external). If we are analyzing the function item
261    /// `foo`, then `'a` and `'b` are local (and `'x` is not in
262    /// scope).
263    Local,
264}
265
266const FIRST_GLOBAL_INDEX: usize = 0;
267
268impl<'tcx> UniversalRegions<'tcx> {
269    /// Creates a new and fully initialized `UniversalRegions` that
270    /// contains indices for all the free regions found in the given
271    /// MIR -- that is, all the regions that appear in the function's
272    /// signature. This will also compute the relationships that are
273    /// known between those regions.
274    pub(crate) fn new(infcx: &BorrowckInferCtxt<'tcx>, mir_def: LocalDefId) -> Self {
275        UniversalRegionsBuilder { infcx, mir_def }.build()
276    }
277
278    /// Given a reference to a closure type, extracts all the values
279    /// from its free regions and returns a vector with them. This is
280    /// used when the closure's creator checks that the
281    /// `ClosureRegionRequirements` are met. The requirements from
282    /// `ClosureRegionRequirements` are expressed in terms of
283    /// `RegionVid` entries that map into the returned vector `V`: so
284    /// if the `ClosureRegionRequirements` contains something like
285    /// `'1: '2`, then the caller would impose the constraint that
286    /// `V[1]: V[2]`.
287    pub(crate) fn closure_mapping(
288        tcx: TyCtxt<'tcx>,
289        closure_args: GenericArgsRef<'tcx>,
290        expected_num_vars: usize,
291        closure_def_id: LocalDefId,
292    ) -> IndexVec<RegionVid, ty::Region<'tcx>> {
293        let mut region_mapping = IndexVec::with_capacity(expected_num_vars);
294        region_mapping.push(tcx.lifetimes.re_static);
295        tcx.for_each_free_region(&closure_args, |fr| {
296            region_mapping.push(fr);
297        });
298
299        for_each_late_bound_region_in_recursive_scope(tcx, tcx.local_parent(closure_def_id), |r| {
300            region_mapping.push(r);
301        });
302
303        assert_eq!(
304            region_mapping.len(),
305            expected_num_vars,
306            "index vec had unexpected number of variables"
307        );
308
309        region_mapping
310    }
311
312    /// Returns `true` if `r` is a member of this set of universal regions.
313    pub(crate) fn is_universal_region(&self, r: RegionVid) -> bool {
314        (FIRST_GLOBAL_INDEX..self.num_universals).contains(&r.index())
315    }
316
317    /// Classifies `r` as a universal region, returning `None` if this
318    /// is not a member of this set of universal regions.
319    pub(crate) fn region_classification(&self, r: RegionVid) -> Option<RegionClassification> {
320        let index = r.index();
321        if (FIRST_GLOBAL_INDEX..self.first_extern_index).contains(&index) {
322            Some(RegionClassification::Global)
323        } else if (self.first_extern_index..self.first_local_index).contains(&index) {
324            Some(RegionClassification::External)
325        } else if (self.first_local_index..self.num_universals).contains(&index) {
326            Some(RegionClassification::Local)
327        } else {
328            None
329        }
330    }
331
332    /// Returns an iterator over all the RegionVids corresponding to
333    /// universally quantified free regions.
334    pub(crate) fn universal_regions_iter(&self) -> impl Iterator<Item = RegionVid> + 'static {
335        (FIRST_GLOBAL_INDEX..self.num_universals).map(RegionVid::from_usize)
336    }
337
338    /// Returns `true` if `r` is classified as a local region.
339    pub(crate) fn is_local_free_region(&self, r: RegionVid) -> bool {
340        self.region_classification(r) == Some(RegionClassification::Local)
341    }
342
343    /// Returns the number of universal regions created in any category.
344    pub(crate) fn len(&self) -> usize {
345        self.num_universals
346    }
347
348    /// Returns the number of global plus external universal regions.
349    /// For closures, these are the regions that appear free in the
350    /// closure type (versus those bound in the closure
351    /// signature). They are therefore the regions between which the
352    /// closure may impose constraints that its creator must verify.
353    pub(crate) fn num_global_and_external_regions(&self) -> usize {
354        self.first_local_index
355    }
356
357    /// Gets an iterator over all the early-bound regions that have names.
358    pub(crate) fn named_universal_regions_iter(
359        &self,
360    ) -> impl Iterator<Item = (ty::Region<'tcx>, ty::RegionVid)> {
361        self.indices.indices.iter().map(|(&r, &v)| (r, v))
362    }
363
364    /// See [UniversalRegionIndices::to_region_vid].
365    pub(crate) fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid {
366        self.indices.to_region_vid(r)
367    }
368
369    /// As part of the NLL unit tests, you can annotate a function with
370    /// `#[rustc_regions]`, and we will emit information about the region
371    /// inference context and -- in particular -- the external constraints
372    /// that this region imposes on others. The methods in this file
373    /// handle the part about dumping the inference context internal
374    /// state.
375    pub(crate) fn annotate(&self, tcx: TyCtxt<'tcx>, err: &mut Diag<'_, ()>) {
376        match self.defining_ty {
377            DefiningTy::Closure(def_id, args) => {
378                let v = with_no_trimmed_paths!(
379                    args[tcx.generics_of(def_id).parent_count..]
380                        .iter()
381                        .map(|arg| arg.to_string())
382                        .collect::<Vec<_>>()
383                );
384                err.note(format!(
385                    "defining type: {} with closure args [\n    {},\n]",
386                    tcx.def_path_str_with_args(def_id, args),
387                    v.join(",\n    "),
388                ));
389
390                // FIXME: It'd be nice to print the late-bound regions
391                // here, but unfortunately these wind up stored into
392                // tests, and the resulting print-outs include def-ids
393                // and other things that are not stable across tests!
394                // So we just include the region-vid. Annoying.
395                for_each_late_bound_region_in_recursive_scope(tcx, def_id.expect_local(), |r| {
396                    err.note(format!("late-bound region is {:?}", self.to_region_vid(r)));
397                });
398            }
399            DefiningTy::CoroutineClosure(..) => {
400                todo!()
401            }
402            DefiningTy::Coroutine(def_id, args) => {
403                let v = with_no_trimmed_paths!(
404                    args[tcx.generics_of(def_id).parent_count..]
405                        .iter()
406                        .map(|arg| arg.to_string())
407                        .collect::<Vec<_>>()
408                );
409                err.note(format!(
410                    "defining type: {} with coroutine args [\n    {},\n]",
411                    tcx.def_path_str_with_args(def_id, args),
412                    v.join(",\n    "),
413                ));
414
415                // FIXME: As above, we'd like to print out the region
416                // `r` but doing so is not stable across architectures
417                // and so forth.
418                for_each_late_bound_region_in_recursive_scope(tcx, def_id.expect_local(), |r| {
419                    err.note(format!("late-bound region is {:?}", self.to_region_vid(r)));
420                });
421            }
422            DefiningTy::FnDef(def_id, args) => {
423                err.note(format!("defining type: {}", tcx.def_path_str_with_args(def_id, args),));
424            }
425            DefiningTy::Const(def_id, args) => {
426                err.note(format!(
427                    "defining constant type: {}",
428                    tcx.def_path_str_with_args(def_id, args),
429                ));
430            }
431            DefiningTy::InlineConst(def_id, args) => {
432                err.note(format!(
433                    "defining inline constant type: {}",
434                    tcx.def_path_str_with_args(def_id, args),
435                ));
436            }
437            DefiningTy::GlobalAsm(_) => unreachable!(),
438        }
439    }
440
441    pub(crate) fn tainted_by_errors(&self) -> Option<ErrorGuaranteed> {
442        self.indices.tainted_by_errors.get()
443    }
444}
445
446struct UniversalRegionsBuilder<'infcx, 'tcx> {
447    infcx: &'infcx BorrowckInferCtxt<'tcx>,
448    mir_def: LocalDefId,
449}
450
451const FR: NllRegionVariableOrigin = NllRegionVariableOrigin::FreeRegion;
452
453impl<'cx, 'tcx> UniversalRegionsBuilder<'cx, 'tcx> {
454    fn build(self) -> UniversalRegions<'tcx> {
455        debug!("build(mir_def={:?})", self.mir_def);
456
457        let param_env = self.infcx.param_env;
458        debug!("build: param_env={:?}", param_env);
459
460        assert_eq!(FIRST_GLOBAL_INDEX, self.infcx.num_region_vars());
461
462        // Create the "global" region that is always free in all contexts: 'static.
463        let fr_static =
464            self.infcx.next_nll_region_var(FR, || RegionCtxt::Free(kw::Static)).as_var();
465
466        // We've now added all the global regions. The next ones we
467        // add will be external.
468        let first_extern_index = self.infcx.num_region_vars();
469
470        let defining_ty = self.defining_ty();
471        debug!("build: defining_ty={:?}", defining_ty);
472
473        let mut indices = self.compute_indices(fr_static, defining_ty);
474        debug!("build: indices={:?}", indices);
475
476        let typeck_root_def_id = self.infcx.tcx.typeck_root_def_id(self.mir_def.to_def_id());
477
478        // If this is a 'root' body (not a closure/coroutine/inline const), then
479        // there are no extern regions, so the local regions start at the same
480        // position as the (empty) sub-list of extern regions
481        let first_local_index = if self.mir_def.to_def_id() == typeck_root_def_id {
482            first_extern_index
483        } else {
484            // If this is a closure, coroutine, or inline-const, then the late-bound regions from the enclosing
485            // function/closures are actually external regions to us. For example, here, 'a is not local
486            // to the closure c (although it is local to the fn foo):
487            // fn foo<'a>() {
488            //     let c = || { let x: &'a u32 = ...; }
489            // }
490            for_each_late_bound_region_in_recursive_scope(
491                self.infcx.tcx,
492                self.infcx.tcx.local_parent(self.mir_def),
493                |r| {
494                    debug!(?r);
495                    let region_vid = {
496                        let name = r.get_name_or_anon();
497                        self.infcx.next_nll_region_var(FR, || RegionCtxt::LateBound(name))
498                    };
499
500                    debug!(?region_vid);
501                    indices.insert_late_bound_region(r, region_vid.as_var());
502                },
503            );
504
505            // Any regions created during the execution of `defining_ty` or during the above
506            // late-bound region replacement are all considered 'extern' regions
507            self.infcx.num_region_vars()
508        };
509
510        // Converse of above, if this is a function/closure then the late-bound regions declared
511        // on its signature are local.
512        //
513        // We manually loop over `bound_inputs_and_output` instead of using
514        // `for_each_late_bound_region_in_item` as we may need to add the otherwise
515        // implicit `ClosureEnv` region.
516        let bound_inputs_and_output = self.compute_inputs_and_output(&indices, defining_ty);
517        for (idx, bound_var) in bound_inputs_and_output.bound_vars().iter().enumerate() {
518            if let ty::BoundVariableKind::Region(kind) = bound_var {
519                let kind = ty::LateParamRegionKind::from_bound(ty::BoundVar::from_usize(idx), kind);
520                let r = ty::Region::new_late_param(self.infcx.tcx, self.mir_def.to_def_id(), kind);
521                let region_vid = {
522                    let name = r.get_name_or_anon();
523                    self.infcx.next_nll_region_var(FR, || RegionCtxt::LateBound(name))
524                };
525
526                debug!(?region_vid);
527                indices.insert_late_bound_region(r, region_vid.as_var());
528            }
529        }
530        let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars(
531            self.mir_def,
532            bound_inputs_and_output,
533            &indices,
534        );
535
536        let (unnormalized_output_ty, mut unnormalized_input_tys) =
537            inputs_and_output.split_last().unwrap();
538
539        // C-variadic fns also have a `VaList` input that's not listed in the signature
540        // (as it's created inside the body itself, not passed in from outside).
541        if let DefiningTy::FnDef(def_id, _) = defining_ty {
542            if self.infcx.tcx.fn_sig(def_id).skip_binder().c_variadic() {
543                let va_list_did = self.infcx.tcx.require_lang_item(
544                    LangItem::VaList,
545                    Some(self.infcx.tcx.def_span(self.mir_def)),
546                );
547
548                let reg_vid = self
549                    .infcx
550                    .next_nll_region_var(FR, || RegionCtxt::Free(sym::c_dash_variadic))
551                    .as_var();
552
553                let region = ty::Region::new_var(self.infcx.tcx, reg_vid);
554                let va_list_ty = self
555                    .infcx
556                    .tcx
557                    .type_of(va_list_did)
558                    .instantiate(self.infcx.tcx, &[region.into()]);
559
560                unnormalized_input_tys = self.infcx.tcx.mk_type_list_from_iter(
561                    unnormalized_input_tys.iter().copied().chain(iter::once(va_list_ty)),
562                );
563            }
564        }
565
566        let fr_fn_body =
567            self.infcx.next_nll_region_var(FR, || RegionCtxt::Free(sym::fn_body)).as_var();
568
569        let num_universals = self.infcx.num_region_vars();
570
571        debug!("build: global regions = {}..{}", FIRST_GLOBAL_INDEX, first_extern_index);
572        debug!("build: extern regions = {}..{}", first_extern_index, first_local_index);
573        debug!("build: local regions  = {}..{}", first_local_index, num_universals);
574
575        let (resume_ty, yield_ty) = match defining_ty {
576            DefiningTy::Coroutine(_, args) => {
577                let tys = args.as_coroutine();
578                (Some(tys.resume_ty()), Some(tys.yield_ty()))
579            }
580            _ => (None, None),
581        };
582
583        UniversalRegions {
584            indices,
585            fr_static,
586            fr_fn_body,
587            first_extern_index,
588            first_local_index,
589            num_universals,
590            defining_ty,
591            unnormalized_output_ty: *unnormalized_output_ty,
592            unnormalized_input_tys,
593            yield_ty,
594            resume_ty,
595        }
596    }
597
598    /// Returns the "defining type" of the current MIR;
599    /// see `DefiningTy` for details.
600    fn defining_ty(&self) -> DefiningTy<'tcx> {
601        let tcx = self.infcx.tcx;
602        let typeck_root_def_id = tcx.typeck_root_def_id(self.mir_def.to_def_id());
603
604        match tcx.hir_body_owner_kind(self.mir_def) {
605            BodyOwnerKind::Closure | BodyOwnerKind::Fn => {
606                let defining_ty = tcx.type_of(self.mir_def).instantiate_identity();
607
608                debug!("defining_ty (pre-replacement): {:?}", defining_ty);
609
610                let defining_ty =
611                    self.infcx.replace_free_regions_with_nll_infer_vars(FR, defining_ty);
612
613                match *defining_ty.kind() {
614                    ty::Closure(def_id, args) => DefiningTy::Closure(def_id, args),
615                    ty::Coroutine(def_id, args) => DefiningTy::Coroutine(def_id, args),
616                    ty::CoroutineClosure(def_id, args) => {
617                        DefiningTy::CoroutineClosure(def_id, args)
618                    }
619                    ty::FnDef(def_id, args) => DefiningTy::FnDef(def_id, args),
620                    _ => span_bug!(
621                        tcx.def_span(self.mir_def),
622                        "expected defining type for `{:?}`: `{:?}`",
623                        self.mir_def,
624                        defining_ty
625                    ),
626                }
627            }
628
629            BodyOwnerKind::Const { .. } | BodyOwnerKind::Static(..) => {
630                let identity_args = GenericArgs::identity_for_item(tcx, typeck_root_def_id);
631                if self.mir_def.to_def_id() == typeck_root_def_id
632                    // Do not ICE when checking default_field_values consts with lifetimes (#135649)
633                    && DefKind::Field != tcx.def_kind(tcx.parent(typeck_root_def_id))
634                {
635                    let args =
636                        self.infcx.replace_free_regions_with_nll_infer_vars(FR, identity_args);
637                    DefiningTy::Const(self.mir_def.to_def_id(), args)
638                } else {
639                    // FIXME this line creates a dependency between borrowck and typeck.
640                    //
641                    // This is required for `AscribeUserType` canonical query, which will call
642                    // `type_of(inline_const_def_id)`. That `type_of` would inject erased lifetimes
643                    // into borrowck, which is ICE #78174.
644                    //
645                    // As a workaround, inline consts have an additional generic param (`ty`
646                    // below), so that `type_of(inline_const_def_id).args(args)` uses the
647                    // proper type with NLL infer vars.
648                    let ty = tcx
649                        .typeck(self.mir_def)
650                        .node_type(tcx.local_def_id_to_hir_id(self.mir_def));
651                    let args = InlineConstArgs::new(
652                        tcx,
653                        InlineConstArgsParts { parent_args: identity_args, ty },
654                    )
655                    .args;
656                    let args = self.infcx.replace_free_regions_with_nll_infer_vars(FR, args);
657                    DefiningTy::InlineConst(self.mir_def.to_def_id(), args)
658                }
659            }
660
661            BodyOwnerKind::GlobalAsm => DefiningTy::GlobalAsm(self.mir_def.to_def_id()),
662        }
663    }
664
665    /// Builds a hashmap that maps from the universal regions that are
666    /// in scope (as a `ty::Region<'tcx>`) to their indices (as a
667    /// `RegionVid`). The map returned by this function contains only
668    /// the early-bound regions.
669    fn compute_indices(
670        &self,
671        fr_static: RegionVid,
672        defining_ty: DefiningTy<'tcx>,
673    ) -> UniversalRegionIndices<'tcx> {
674        let tcx = self.infcx.tcx;
675        let typeck_root_def_id = tcx.typeck_root_def_id(self.mir_def.to_def_id());
676        let identity_args = GenericArgs::identity_for_item(tcx, typeck_root_def_id);
677        let fr_args = match defining_ty {
678            DefiningTy::Closure(_, args)
679            | DefiningTy::CoroutineClosure(_, args)
680            | DefiningTy::Coroutine(_, args)
681            | DefiningTy::InlineConst(_, args) => {
682                // In the case of closures, we rely on the fact that
683                // the first N elements in the ClosureArgs are
684                // inherited from the `typeck_root_def_id`.
685                // Therefore, when we zip together (below) with
686                // `identity_args`, we will get only those regions
687                // that correspond to early-bound regions declared on
688                // the `typeck_root_def_id`.
689                assert!(args.len() >= identity_args.len());
690                assert_eq!(args.regions().count(), identity_args.regions().count());
691                args
692            }
693
694            DefiningTy::FnDef(_, args) | DefiningTy::Const(_, args) => args,
695
696            DefiningTy::GlobalAsm(_) => ty::List::empty(),
697        };
698
699        let global_mapping = iter::once((tcx.lifetimes.re_static, fr_static));
700        let arg_mapping = iter::zip(identity_args.regions(), fr_args.regions().map(|r| r.as_var()));
701
702        UniversalRegionIndices {
703            indices: global_mapping.chain(arg_mapping).collect(),
704            fr_static,
705            tainted_by_errors: Cell::new(None),
706        }
707    }
708
709    fn compute_inputs_and_output(
710        &self,
711        indices: &UniversalRegionIndices<'tcx>,
712        defining_ty: DefiningTy<'tcx>,
713    ) -> ty::Binder<'tcx, &'tcx ty::List<Ty<'tcx>>> {
714        let tcx = self.infcx.tcx;
715
716        let inputs_and_output = match defining_ty {
717            DefiningTy::Closure(def_id, args) => {
718                assert_eq!(self.mir_def.to_def_id(), def_id);
719                let closure_sig = args.as_closure().sig();
720                let inputs_and_output = closure_sig.inputs_and_output();
721                let bound_vars = tcx.mk_bound_variable_kinds_from_iter(
722                    inputs_and_output.bound_vars().iter().chain(iter::once(
723                        ty::BoundVariableKind::Region(ty::BoundRegionKind::ClosureEnv),
724                    )),
725                );
726                let br = ty::BoundRegion {
727                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
728                    kind: ty::BoundRegionKind::ClosureEnv,
729                };
730                let env_region = ty::Region::new_bound(tcx, ty::INNERMOST, br);
731                let closure_ty = tcx.closure_env_ty(
732                    Ty::new_closure(tcx, def_id, args),
733                    args.as_closure().kind(),
734                    env_region,
735                );
736
737                // The "inputs" of the closure in the
738                // signature appear as a tuple. The MIR side
739                // flattens this tuple.
740                let (&output, tuplized_inputs) =
741                    inputs_and_output.skip_binder().split_last().unwrap();
742                assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs");
743                let &ty::Tuple(inputs) = tuplized_inputs[0].kind() else {
744                    bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]);
745                };
746
747                ty::Binder::bind_with_vars(
748                    tcx.mk_type_list_from_iter(
749                        iter::once(closure_ty).chain(inputs).chain(iter::once(output)),
750                    ),
751                    bound_vars,
752                )
753            }
754
755            DefiningTy::Coroutine(def_id, args) => {
756                assert_eq!(self.mir_def.to_def_id(), def_id);
757                let resume_ty = args.as_coroutine().resume_ty();
758                let output = args.as_coroutine().return_ty();
759                let coroutine_ty = Ty::new_coroutine(tcx, def_id, args);
760                let inputs_and_output =
761                    self.infcx.tcx.mk_type_list(&[coroutine_ty, resume_ty, output]);
762                ty::Binder::dummy(inputs_and_output)
763            }
764
765            // Construct the signature of the CoroutineClosure for the purposes of borrowck.
766            // This is pretty straightforward -- we:
767            // 1. first grab the `coroutine_closure_sig`,
768            // 2. compute the self type (`&`/`&mut`/no borrow),
769            // 3. flatten the tupled_input_tys,
770            // 4. construct the correct generator type to return with
771            //    `CoroutineClosureSignature::to_coroutine_given_kind_and_upvars`.
772            // Then we wrap it all up into a list of inputs and output.
773            DefiningTy::CoroutineClosure(def_id, args) => {
774                assert_eq!(self.mir_def.to_def_id(), def_id);
775                let closure_sig = args.as_coroutine_closure().coroutine_closure_sig();
776                let bound_vars =
777                    tcx.mk_bound_variable_kinds_from_iter(closure_sig.bound_vars().iter().chain(
778                        iter::once(ty::BoundVariableKind::Region(ty::BoundRegionKind::ClosureEnv)),
779                    ));
780                let br = ty::BoundRegion {
781                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
782                    kind: ty::BoundRegionKind::ClosureEnv,
783                };
784                let env_region = ty::Region::new_bound(tcx, ty::INNERMOST, br);
785                let closure_kind = args.as_coroutine_closure().kind();
786
787                let closure_ty = tcx.closure_env_ty(
788                    Ty::new_coroutine_closure(tcx, def_id, args),
789                    closure_kind,
790                    env_region,
791                );
792
793                let inputs = closure_sig.skip_binder().tupled_inputs_ty.tuple_fields();
794                let output = closure_sig.skip_binder().to_coroutine_given_kind_and_upvars(
795                    tcx,
796                    args.as_coroutine_closure().parent_args(),
797                    tcx.coroutine_for_closure(def_id),
798                    closure_kind,
799                    env_region,
800                    args.as_coroutine_closure().tupled_upvars_ty(),
801                    args.as_coroutine_closure().coroutine_captures_by_ref_ty(),
802                );
803
804                ty::Binder::bind_with_vars(
805                    tcx.mk_type_list_from_iter(
806                        iter::once(closure_ty).chain(inputs).chain(iter::once(output)),
807                    ),
808                    bound_vars,
809                )
810            }
811
812            DefiningTy::FnDef(def_id, _) => {
813                let sig = tcx.fn_sig(def_id).instantiate_identity();
814                let sig = indices.fold_to_region_vids(tcx, sig);
815                sig.inputs_and_output()
816            }
817
818            DefiningTy::Const(def_id, _) => {
819                // For a constant body, there are no inputs, and one
820                // "output" (the type of the constant).
821                assert_eq!(self.mir_def.to_def_id(), def_id);
822                let ty = tcx.type_of(self.mir_def).instantiate_identity();
823
824                let ty = indices.fold_to_region_vids(tcx, ty);
825                ty::Binder::dummy(tcx.mk_type_list(&[ty]))
826            }
827
828            DefiningTy::InlineConst(def_id, args) => {
829                assert_eq!(self.mir_def.to_def_id(), def_id);
830                let ty = args.as_inline_const().ty();
831                ty::Binder::dummy(tcx.mk_type_list(&[ty]))
832            }
833
834            DefiningTy::GlobalAsm(def_id) => {
835                ty::Binder::dummy(tcx.mk_type_list(&[tcx.type_of(def_id).instantiate_identity()]))
836            }
837        };
838
839        // FIXME(#129952): We probably want a more principled approach here.
840        if let Err(terr) = inputs_and_output.skip_binder().error_reported() {
841            self.infcx.set_tainted_by_errors(terr);
842        }
843
844        inputs_and_output
845    }
846}
847
848#[extension(trait InferCtxtExt<'tcx>)]
849impl<'tcx> BorrowckInferCtxt<'tcx> {
850    #[instrument(skip(self), level = "debug")]
851    fn replace_free_regions_with_nll_infer_vars<T>(
852        &self,
853        origin: NllRegionVariableOrigin,
854        value: T,
855    ) -> T
856    where
857        T: TypeFoldable<TyCtxt<'tcx>>,
858    {
859        fold_regions(self.infcx.tcx, value, |region, _depth| {
860            let name = region.get_name_or_anon();
861            debug!(?region, ?name);
862
863            self.next_nll_region_var(origin, || RegionCtxt::Free(name))
864        })
865    }
866
867    #[instrument(level = "debug", skip(self, indices))]
868    fn replace_bound_regions_with_nll_infer_vars<T>(
869        &self,
870        all_outlive_scope: LocalDefId,
871        value: ty::Binder<'tcx, T>,
872        indices: &UniversalRegionIndices<'tcx>,
873    ) -> T
874    where
875        T: TypeFoldable<TyCtxt<'tcx>>,
876    {
877        let (value, _map) = self.tcx.instantiate_bound_regions(value, |br| {
878            debug!(?br);
879            let kind = ty::LateParamRegionKind::from_bound(br.var, br.kind);
880            let liberated_region =
881                ty::Region::new_late_param(self.tcx, all_outlive_scope.to_def_id(), kind);
882            ty::Region::new_var(self.tcx, indices.to_region_vid(liberated_region))
883        });
884        value
885    }
886}
887
888impl<'tcx> UniversalRegionIndices<'tcx> {
889    /// Initially, the `UniversalRegionIndices` map contains only the
890    /// early-bound regions in scope. Once that is all setup, we come
891    /// in later and instantiate the late-bound regions, and then we
892    /// insert the `ReLateParam` version of those into the map as
893    /// well. These are used for error reporting.
894    fn insert_late_bound_region(&mut self, r: ty::Region<'tcx>, vid: ty::RegionVid) {
895        debug!("insert_late_bound_region({:?}, {:?})", r, vid);
896        assert_eq!(self.indices.insert(r, vid), None);
897    }
898
899    /// Converts `r` into a local inference variable: `r` can either
900    /// be a `ReVar` (i.e., already a reference to an inference
901    /// variable) or it can be `'static` or some early-bound
902    /// region. This is useful when taking the results from
903    /// type-checking and trait-matching, which may sometimes
904    /// reference those regions from the `ParamEnv`. It is also used
905    /// during initialization. Relies on the `indices` map having been
906    /// fully initialized.
907    ///
908    /// Panics if `r` is not a registered universal region, most notably
909    /// if it is a placeholder. Handling placeholders requires access to the
910    /// `MirTypeckRegionConstraints`.
911    fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid {
912        if let ty::ReVar(..) = *r {
913            r.as_var()
914        } else if let ty::ReError(guar) = *r {
915            self.tainted_by_errors.set(Some(guar));
916            // We use the `'static` `RegionVid` because `ReError` doesn't actually exist in the
917            // `UniversalRegionIndices`. This is fine because 1) it is a fallback only used if
918            // errors are being emitted and 2) it leaves the happy path unaffected.
919            self.fr_static
920        } else {
921            *self
922                .indices
923                .get(&r)
924                .unwrap_or_else(|| bug!("cannot convert `{:?}` to a region vid", r))
925        }
926    }
927
928    /// Replaces all free regions in `value` with region vids, as
929    /// returned by `to_region_vid`.
930    fn fold_to_region_vids<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T
931    where
932        T: TypeFoldable<TyCtxt<'tcx>>,
933    {
934        fold_regions(tcx, value, |region, _| ty::Region::new_var(tcx, self.to_region_vid(region)))
935    }
936}
937
938/// Iterates over the late-bound regions defined on `mir_def_id` and all of its
939/// parents, up to the typeck root, and invokes `f` with the liberated form
940/// of each one.
941fn for_each_late_bound_region_in_recursive_scope<'tcx>(
942    tcx: TyCtxt<'tcx>,
943    mut mir_def_id: LocalDefId,
944    mut f: impl FnMut(ty::Region<'tcx>),
945) {
946    let typeck_root_def_id = tcx.typeck_root_def_id(mir_def_id.to_def_id());
947
948    // Walk up the tree, collecting late-bound regions until we hit the typeck root
949    loop {
950        for_each_late_bound_region_in_item(tcx, mir_def_id, &mut f);
951
952        if mir_def_id.to_def_id() == typeck_root_def_id {
953            break;
954        } else {
955            mir_def_id = tcx.local_parent(mir_def_id);
956        }
957    }
958}
959
960/// Iterates over the late-bound regions defined on `mir_def_id` and all of its
961/// parents, up to the typeck root, and invokes `f` with the liberated form
962/// of each one.
963fn for_each_late_bound_region_in_item<'tcx>(
964    tcx: TyCtxt<'tcx>,
965    mir_def_id: LocalDefId,
966    mut f: impl FnMut(ty::Region<'tcx>),
967) {
968    if !tcx.def_kind(mir_def_id).is_fn_like() {
969        return;
970    }
971
972    for (idx, bound_var) in
973        tcx.late_bound_vars(tcx.local_def_id_to_hir_id(mir_def_id)).iter().enumerate()
974    {
975        if let ty::BoundVariableKind::Region(kind) = bound_var {
976            let kind = ty::LateParamRegionKind::from_bound(ty::BoundVar::from_usize(idx), kind);
977            let liberated_region = ty::Region::new_late_param(tcx, mir_def_id.to_def_id(), kind);
978            f(liberated_region);
979        }
980    }
981}