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