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