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