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