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