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 implicit_region_bound(&self) -> RegionVid {
442        self.fr_fn_body
443    }
444
445    pub(crate) fn tainted_by_errors(&self) -> Option<ErrorGuaranteed> {
446        self.indices.tainted_by_errors.get()
447    }
448}
449
450struct UniversalRegionsBuilder<'infcx, 'tcx> {
451    infcx: &'infcx BorrowckInferCtxt<'tcx>,
452    mir_def: LocalDefId,
453}
454
455const FR: NllRegionVariableOrigin = NllRegionVariableOrigin::FreeRegion;
456
457impl<'cx, 'tcx> UniversalRegionsBuilder<'cx, 'tcx> {
458    fn build(self) -> UniversalRegions<'tcx> {
459        debug!("build(mir_def={:?})", self.mir_def);
460
461        let param_env = self.infcx.param_env;
462        debug!("build: param_env={:?}", param_env);
463
464        assert_eq!(FIRST_GLOBAL_INDEX, self.infcx.num_region_vars());
465
466        // Create the "global" region that is always free in all contexts: 'static.
467        let fr_static =
468            self.infcx.next_nll_region_var(FR, || RegionCtxt::Free(kw::Static)).as_var();
469
470        // We've now added all the global regions. The next ones we
471        // add will be external.
472        let first_extern_index = self.infcx.num_region_vars();
473
474        let defining_ty = self.defining_ty();
475        debug!("build: defining_ty={:?}", defining_ty);
476
477        let mut indices = self.compute_indices(fr_static, defining_ty);
478        debug!("build: indices={:?}", indices);
479
480        let typeck_root_def_id = self.infcx.tcx.typeck_root_def_id(self.mir_def.to_def_id());
481
482        // If this is a 'root' body (not a closure/coroutine/inline const), then
483        // there are no extern regions, so the local regions start at the same
484        // position as the (empty) sub-list of extern regions
485        let first_local_index = if self.mir_def.to_def_id() == typeck_root_def_id {
486            first_extern_index
487        } else {
488            // If this is a closure, coroutine, or inline-const, then the late-bound regions from the enclosing
489            // function/closures are actually external regions to us. For example, here, 'a is not local
490            // to the closure c (although it is local to the fn foo):
491            // fn foo<'a>() {
492            //     let c = || { let x: &'a u32 = ...; }
493            // }
494            for_each_late_bound_region_in_recursive_scope(
495                self.infcx.tcx,
496                self.infcx.tcx.local_parent(self.mir_def),
497                |r| {
498                    debug!(?r);
499                    let region_vid = {
500                        let name = r.get_name_or_anon();
501                        self.infcx.next_nll_region_var(FR, || RegionCtxt::LateBound(name))
502                    };
503
504                    debug!(?region_vid);
505                    indices.insert_late_bound_region(r, region_vid.as_var());
506                },
507            );
508
509            // Any regions created during the execution of `defining_ty` or during the above
510            // late-bound region replacement are all considered 'extern' regions
511            self.infcx.num_region_vars()
512        };
513
514        // Converse of above, if this is a function/closure then the late-bound regions declared
515        // on its signature are local.
516        //
517        // We manually loop over `bound_inputs_and_output` instead of using
518        // `for_each_late_bound_region_in_item` as we may need to add the otherwise
519        // implicit `ClosureEnv` region.
520        let bound_inputs_and_output = self.compute_inputs_and_output(&indices, defining_ty);
521        for (idx, bound_var) in bound_inputs_and_output.bound_vars().iter().enumerate() {
522            if let ty::BoundVariableKind::Region(kind) = bound_var {
523                let kind = ty::LateParamRegionKind::from_bound(ty::BoundVar::from_usize(idx), kind);
524                let r = ty::Region::new_late_param(self.infcx.tcx, self.mir_def.to_def_id(), kind);
525                let region_vid = {
526                    let name = r.get_name_or_anon();
527                    self.infcx.next_nll_region_var(FR, || RegionCtxt::LateBound(name))
528                };
529
530                debug!(?region_vid);
531                indices.insert_late_bound_region(r, region_vid.as_var());
532            }
533        }
534        let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars(
535            self.mir_def,
536            bound_inputs_and_output,
537            &indices,
538        );
539
540        let (unnormalized_output_ty, mut unnormalized_input_tys) =
541            inputs_and_output.split_last().unwrap();
542
543        // C-variadic fns also have a `VaList` input that's not listed in the signature
544        // (as it's created inside the body itself, not passed in from outside).
545        if let DefiningTy::FnDef(def_id, _) = defining_ty {
546            if self.infcx.tcx.fn_sig(def_id).skip_binder().c_variadic() {
547                let va_list_did = self.infcx.tcx.require_lang_item(
548                    LangItem::VaList,
549                    Some(self.infcx.tcx.def_span(self.mir_def)),
550                );
551
552                let reg_vid = self
553                    .infcx
554                    .next_nll_region_var(FR, || RegionCtxt::Free(sym::c_dash_variadic))
555                    .as_var();
556
557                let region = ty::Region::new_var(self.infcx.tcx, reg_vid);
558                let va_list_ty = self
559                    .infcx
560                    .tcx
561                    .type_of(va_list_did)
562                    .instantiate(self.infcx.tcx, &[region.into()]);
563
564                unnormalized_input_tys = self.infcx.tcx.mk_type_list_from_iter(
565                    unnormalized_input_tys.iter().copied().chain(iter::once(va_list_ty)),
566                );
567            }
568        }
569
570        let fr_fn_body =
571            self.infcx.next_nll_region_var(FR, || RegionCtxt::Free(sym::fn_body)).as_var();
572
573        let num_universals = self.infcx.num_region_vars();
574
575        debug!("build: global regions = {}..{}", FIRST_GLOBAL_INDEX, first_extern_index);
576        debug!("build: extern regions = {}..{}", first_extern_index, first_local_index);
577        debug!("build: local regions  = {}..{}", first_local_index, num_universals);
578
579        let (resume_ty, yield_ty) = match defining_ty {
580            DefiningTy::Coroutine(_, args) => {
581                let tys = args.as_coroutine();
582                (Some(tys.resume_ty()), Some(tys.yield_ty()))
583            }
584            _ => (None, None),
585        };
586
587        UniversalRegions {
588            indices,
589            fr_static,
590            fr_fn_body,
591            first_extern_index,
592            first_local_index,
593            num_universals,
594            defining_ty,
595            unnormalized_output_ty: *unnormalized_output_ty,
596            unnormalized_input_tys,
597            yield_ty,
598            resume_ty,
599        }
600    }
601
602    /// Returns the "defining type" of the current MIR;
603    /// see `DefiningTy` for details.
604    fn defining_ty(&self) -> DefiningTy<'tcx> {
605        let tcx = self.infcx.tcx;
606        let typeck_root_def_id = tcx.typeck_root_def_id(self.mir_def.to_def_id());
607
608        match tcx.hir_body_owner_kind(self.mir_def) {
609            BodyOwnerKind::Closure | BodyOwnerKind::Fn => {
610                let defining_ty = tcx.type_of(self.mir_def).instantiate_identity();
611
612                debug!("defining_ty (pre-replacement): {:?}", defining_ty);
613
614                let defining_ty =
615                    self.infcx.replace_free_regions_with_nll_infer_vars(FR, defining_ty);
616
617                match *defining_ty.kind() {
618                    ty::Closure(def_id, args) => DefiningTy::Closure(def_id, args),
619                    ty::Coroutine(def_id, args) => DefiningTy::Coroutine(def_id, args),
620                    ty::CoroutineClosure(def_id, args) => {
621                        DefiningTy::CoroutineClosure(def_id, args)
622                    }
623                    ty::FnDef(def_id, args) => DefiningTy::FnDef(def_id, args),
624                    _ => span_bug!(
625                        tcx.def_span(self.mir_def),
626                        "expected defining type for `{:?}`: `{:?}`",
627                        self.mir_def,
628                        defining_ty
629                    ),
630                }
631            }
632
633            BodyOwnerKind::Const { .. } | BodyOwnerKind::Static(..) => {
634                let identity_args = GenericArgs::identity_for_item(tcx, typeck_root_def_id);
635                if self.mir_def.to_def_id() == typeck_root_def_id
636                    // Do not ICE when checking default_field_values consts with lifetimes (#135649)
637                    && DefKind::Field != tcx.def_kind(tcx.parent(typeck_root_def_id))
638                {
639                    let args =
640                        self.infcx.replace_free_regions_with_nll_infer_vars(FR, identity_args);
641                    DefiningTy::Const(self.mir_def.to_def_id(), args)
642                } else {
643                    // FIXME this line creates a dependency between borrowck and typeck.
644                    //
645                    // This is required for `AscribeUserType` canonical query, which will call
646                    // `type_of(inline_const_def_id)`. That `type_of` would inject erased lifetimes
647                    // into borrowck, which is ICE #78174.
648                    //
649                    // As a workaround, inline consts have an additional generic param (`ty`
650                    // below), so that `type_of(inline_const_def_id).args(args)` uses the
651                    // proper type with NLL infer vars.
652                    let ty = tcx
653                        .typeck(self.mir_def)
654                        .node_type(tcx.local_def_id_to_hir_id(self.mir_def));
655                    let args = InlineConstArgs::new(
656                        tcx,
657                        InlineConstArgsParts { parent_args: identity_args, ty },
658                    )
659                    .args;
660                    let args = self.infcx.replace_free_regions_with_nll_infer_vars(FR, args);
661                    DefiningTy::InlineConst(self.mir_def.to_def_id(), args)
662                }
663            }
664
665            BodyOwnerKind::GlobalAsm => DefiningTy::GlobalAsm(self.mir_def.to_def_id()),
666        }
667    }
668
669    /// Builds a hashmap that maps from the universal regions that are
670    /// in scope (as a `ty::Region<'tcx>`) to their indices (as a
671    /// `RegionVid`). The map returned by this function contains only
672    /// the early-bound regions.
673    fn compute_indices(
674        &self,
675        fr_static: RegionVid,
676        defining_ty: DefiningTy<'tcx>,
677    ) -> UniversalRegionIndices<'tcx> {
678        let tcx = self.infcx.tcx;
679        let typeck_root_def_id = tcx.typeck_root_def_id(self.mir_def.to_def_id());
680        let identity_args = GenericArgs::identity_for_item(tcx, typeck_root_def_id);
681        let fr_args = match defining_ty {
682            DefiningTy::Closure(_, args)
683            | DefiningTy::CoroutineClosure(_, args)
684            | DefiningTy::Coroutine(_, args)
685            | DefiningTy::InlineConst(_, args) => {
686                // In the case of closures, we rely on the fact that
687                // the first N elements in the ClosureArgs are
688                // inherited from the `typeck_root_def_id`.
689                // Therefore, when we zip together (below) with
690                // `identity_args`, we will get only those regions
691                // that correspond to early-bound regions declared on
692                // the `typeck_root_def_id`.
693                assert!(args.len() >= identity_args.len());
694                assert_eq!(args.regions().count(), identity_args.regions().count());
695                args
696            }
697
698            DefiningTy::FnDef(_, args) | DefiningTy::Const(_, args) => args,
699
700            DefiningTy::GlobalAsm(_) => ty::List::empty(),
701        };
702
703        let global_mapping = iter::once((tcx.lifetimes.re_static, fr_static));
704        let arg_mapping = iter::zip(identity_args.regions(), fr_args.regions().map(|r| r.as_var()));
705
706        UniversalRegionIndices {
707            indices: global_mapping.chain(arg_mapping).collect(),
708            fr_static,
709            tainted_by_errors: Cell::new(None),
710        }
711    }
712
713    fn compute_inputs_and_output(
714        &self,
715        indices: &UniversalRegionIndices<'tcx>,
716        defining_ty: DefiningTy<'tcx>,
717    ) -> ty::Binder<'tcx, &'tcx ty::List<Ty<'tcx>>> {
718        let tcx = self.infcx.tcx;
719
720        let inputs_and_output = match defining_ty {
721            DefiningTy::Closure(def_id, args) => {
722                assert_eq!(self.mir_def.to_def_id(), def_id);
723                let closure_sig = args.as_closure().sig();
724                let inputs_and_output = closure_sig.inputs_and_output();
725                let bound_vars = tcx.mk_bound_variable_kinds_from_iter(
726                    inputs_and_output.bound_vars().iter().chain(iter::once(
727                        ty::BoundVariableKind::Region(ty::BoundRegionKind::ClosureEnv),
728                    )),
729                );
730                let br = ty::BoundRegion {
731                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
732                    kind: ty::BoundRegionKind::ClosureEnv,
733                };
734                let env_region = ty::Region::new_bound(tcx, ty::INNERMOST, br);
735                let closure_ty = tcx.closure_env_ty(
736                    Ty::new_closure(tcx, def_id, args),
737                    args.as_closure().kind(),
738                    env_region,
739                );
740
741                // The "inputs" of the closure in the
742                // signature appear as a tuple. The MIR side
743                // flattens this tuple.
744                let (&output, tuplized_inputs) =
745                    inputs_and_output.skip_binder().split_last().unwrap();
746                assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs");
747                let &ty::Tuple(inputs) = tuplized_inputs[0].kind() else {
748                    bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]);
749                };
750
751                ty::Binder::bind_with_vars(
752                    tcx.mk_type_list_from_iter(
753                        iter::once(closure_ty).chain(inputs).chain(iter::once(output)),
754                    ),
755                    bound_vars,
756                )
757            }
758
759            DefiningTy::Coroutine(def_id, args) => {
760                assert_eq!(self.mir_def.to_def_id(), def_id);
761                let resume_ty = args.as_coroutine().resume_ty();
762                let output = args.as_coroutine().return_ty();
763                let coroutine_ty = Ty::new_coroutine(tcx, def_id, args);
764                let inputs_and_output =
765                    self.infcx.tcx.mk_type_list(&[coroutine_ty, resume_ty, output]);
766                ty::Binder::dummy(inputs_and_output)
767            }
768
769            // Construct the signature of the CoroutineClosure for the purposes of borrowck.
770            // This is pretty straightforward -- we:
771            // 1. first grab the `coroutine_closure_sig`,
772            // 2. compute the self type (`&`/`&mut`/no borrow),
773            // 3. flatten the tupled_input_tys,
774            // 4. construct the correct generator type to return with
775            //    `CoroutineClosureSignature::to_coroutine_given_kind_and_upvars`.
776            // Then we wrap it all up into a list of inputs and output.
777            DefiningTy::CoroutineClosure(def_id, args) => {
778                assert_eq!(self.mir_def.to_def_id(), def_id);
779                let closure_sig = args.as_coroutine_closure().coroutine_closure_sig();
780                let bound_vars =
781                    tcx.mk_bound_variable_kinds_from_iter(closure_sig.bound_vars().iter().chain(
782                        iter::once(ty::BoundVariableKind::Region(ty::BoundRegionKind::ClosureEnv)),
783                    ));
784                let br = ty::BoundRegion {
785                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
786                    kind: ty::BoundRegionKind::ClosureEnv,
787                };
788                let env_region = ty::Region::new_bound(tcx, ty::INNERMOST, br);
789                let closure_kind = args.as_coroutine_closure().kind();
790
791                let closure_ty = tcx.closure_env_ty(
792                    Ty::new_coroutine_closure(tcx, def_id, args),
793                    closure_kind,
794                    env_region,
795                );
796
797                let inputs = closure_sig.skip_binder().tupled_inputs_ty.tuple_fields();
798                let output = closure_sig.skip_binder().to_coroutine_given_kind_and_upvars(
799                    tcx,
800                    args.as_coroutine_closure().parent_args(),
801                    tcx.coroutine_for_closure(def_id),
802                    closure_kind,
803                    env_region,
804                    args.as_coroutine_closure().tupled_upvars_ty(),
805                    args.as_coroutine_closure().coroutine_captures_by_ref_ty(),
806                );
807
808                ty::Binder::bind_with_vars(
809                    tcx.mk_type_list_from_iter(
810                        iter::once(closure_ty).chain(inputs).chain(iter::once(output)),
811                    ),
812                    bound_vars,
813                )
814            }
815
816            DefiningTy::FnDef(def_id, _) => {
817                let sig = tcx.fn_sig(def_id).instantiate_identity();
818                let sig = indices.fold_to_region_vids(tcx, sig);
819                sig.inputs_and_output()
820            }
821
822            DefiningTy::Const(def_id, _) => {
823                // For a constant body, there are no inputs, and one
824                // "output" (the type of the constant).
825                assert_eq!(self.mir_def.to_def_id(), def_id);
826                let ty = tcx.type_of(self.mir_def).instantiate_identity();
827
828                let ty = indices.fold_to_region_vids(tcx, ty);
829                ty::Binder::dummy(tcx.mk_type_list(&[ty]))
830            }
831
832            DefiningTy::InlineConst(def_id, args) => {
833                assert_eq!(self.mir_def.to_def_id(), def_id);
834                let ty = args.as_inline_const().ty();
835                ty::Binder::dummy(tcx.mk_type_list(&[ty]))
836            }
837
838            DefiningTy::GlobalAsm(def_id) => {
839                ty::Binder::dummy(tcx.mk_type_list(&[tcx.type_of(def_id).instantiate_identity()]))
840            }
841        };
842
843        // FIXME(#129952): We probably want a more principled approach here.
844        if let Err(terr) = inputs_and_output.skip_binder().error_reported() {
845            self.infcx.set_tainted_by_errors(terr);
846        }
847
848        inputs_and_output
849    }
850}
851
852#[extension(trait InferCtxtExt<'tcx>)]
853impl<'tcx> BorrowckInferCtxt<'tcx> {
854    #[instrument(skip(self), level = "debug")]
855    fn replace_free_regions_with_nll_infer_vars<T>(
856        &self,
857        origin: NllRegionVariableOrigin,
858        value: T,
859    ) -> T
860    where
861        T: TypeFoldable<TyCtxt<'tcx>>,
862    {
863        fold_regions(self.infcx.tcx, value, |region, _depth| {
864            let name = region.get_name_or_anon();
865            debug!(?region, ?name);
866
867            self.next_nll_region_var(origin, || RegionCtxt::Free(name))
868        })
869    }
870
871    #[instrument(level = "debug", skip(self, indices))]
872    fn replace_bound_regions_with_nll_infer_vars<T>(
873        &self,
874        all_outlive_scope: LocalDefId,
875        value: ty::Binder<'tcx, T>,
876        indices: &UniversalRegionIndices<'tcx>,
877    ) -> T
878    where
879        T: TypeFoldable<TyCtxt<'tcx>>,
880    {
881        let (value, _map) = self.tcx.instantiate_bound_regions(value, |br| {
882            debug!(?br);
883            let kind = ty::LateParamRegionKind::from_bound(br.var, br.kind);
884            let liberated_region =
885                ty::Region::new_late_param(self.tcx, all_outlive_scope.to_def_id(), kind);
886            ty::Region::new_var(self.tcx, indices.to_region_vid(liberated_region))
887        });
888        value
889    }
890}
891
892impl<'tcx> UniversalRegionIndices<'tcx> {
893    /// Initially, the `UniversalRegionIndices` map contains only the
894    /// early-bound regions in scope. Once that is all setup, we come
895    /// in later and instantiate the late-bound regions, and then we
896    /// insert the `ReLateParam` version of those into the map as
897    /// well. These are used for error reporting.
898    fn insert_late_bound_region(&mut self, r: ty::Region<'tcx>, vid: ty::RegionVid) {
899        debug!("insert_late_bound_region({:?}, {:?})", r, vid);
900        assert_eq!(self.indices.insert(r, vid), None);
901    }
902
903    /// Converts `r` into a local inference variable: `r` can either
904    /// be a `ReVar` (i.e., already a reference to an inference
905    /// variable) or it can be `'static` or some early-bound
906    /// region. This is useful when taking the results from
907    /// type-checking and trait-matching, which may sometimes
908    /// reference those regions from the `ParamEnv`. It is also used
909    /// during initialization. Relies on the `indices` map having been
910    /// fully initialized.
911    ///
912    /// Panics if `r` is not a registered universal region, most notably
913    /// if it is a placeholder. Handling placeholders requires access to the
914    /// `MirTypeckRegionConstraints`.
915    fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid {
916        match r.kind() {
917            ty::ReVar(..) => r.as_var(),
918            ty::ReError(guar) => {
919                self.tainted_by_errors.set(Some(guar));
920                // We use the `'static` `RegionVid` because `ReError` doesn't actually exist in the
921                // `UniversalRegionIndices`. This is fine because 1) it is a fallback only used if
922                // errors are being emitted and 2) it leaves the happy path unaffected.
923                self.fr_static
924            }
925            _ => *self
926                .indices
927                .get(&r)
928                .unwrap_or_else(|| bug!("cannot convert `{:?}` to a region vid", r)),
929        }
930    }
931
932    /// Replaces all free regions in `value` with region vids, as
933    /// returned by `to_region_vid`.
934    fn fold_to_region_vids<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T
935    where
936        T: TypeFoldable<TyCtxt<'tcx>>,
937    {
938        fold_regions(tcx, value, |region, _| ty::Region::new_var(tcx, self.to_region_vid(region)))
939    }
940}
941
942/// Iterates over the late-bound regions defined on `mir_def_id` and all of its
943/// parents, up to the typeck root, and invokes `f` with the liberated form
944/// of each one.
945fn for_each_late_bound_region_in_recursive_scope<'tcx>(
946    tcx: TyCtxt<'tcx>,
947    mut mir_def_id: LocalDefId,
948    mut f: impl FnMut(ty::Region<'tcx>),
949) {
950    let typeck_root_def_id = tcx.typeck_root_def_id(mir_def_id.to_def_id());
951
952    // Walk up the tree, collecting late-bound regions until we hit the typeck root
953    loop {
954        for_each_late_bound_region_in_item(tcx, mir_def_id, &mut f);
955
956        if mir_def_id.to_def_id() == typeck_root_def_id {
957            break;
958        } else {
959            mir_def_id = tcx.local_parent(mir_def_id);
960        }
961    }
962}
963
964/// Iterates over the late-bound regions defined on `mir_def_id` and all of its
965/// parents, up to the typeck root, and invokes `f` with the liberated form
966/// of each one.
967fn for_each_late_bound_region_in_item<'tcx>(
968    tcx: TyCtxt<'tcx>,
969    mir_def_id: LocalDefId,
970    mut f: impl FnMut(ty::Region<'tcx>),
971) {
972    if !tcx.def_kind(mir_def_id).is_fn_like() {
973        return;
974    }
975
976    for (idx, bound_var) in
977        tcx.late_bound_vars(tcx.local_def_id_to_hir_id(mir_def_id)).iter().enumerate()
978    {
979        if let ty::BoundVariableKind::Region(kind) = bound_var {
980            let kind = ty::LateParamRegionKind::from_bound(ty::BoundVar::from_usize(idx), kind);
981            let liberated_region = ty::Region::new_late_param(tcx, mir_def_id.to_def_id(), kind);
982            f(liberated_region);
983        }
984    }
985}