1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Code to extract the universally quantified regions declared on a
12 //! function and the relationships between them. For example:
15 //! fn foo<'a, 'b, 'c: 'b>() { }
18 //! here we would be returning a map assigning each of `{'a, 'b, 'c}`
19 //! to an index, as well as the `FreeRegionMap` which can compute
20 //! relationships between them.
22 //! The code in this file doesn't *do anything* with those results; it
23 //! just returns them for other code to use.
25 use rustc::hir::{self, BodyOwnerKind, HirId};
26 use rustc::hir::def_id::DefId;
27 use rustc::infer::{InferCtxt, NLLRegionVariableOrigin};
28 use rustc::infer::region_constraints::GenericKind;
29 use rustc::infer::outlives::bounds::{self, OutlivesBound};
30 use rustc::infer::outlives::free_region_map::FreeRegionRelations;
31 use rustc::ty::{self, RegionVid, Ty, TyCtxt, ClosureSubsts, GeneratorSubsts};
32 use rustc::ty::fold::TypeFoldable;
33 use rustc::ty::subst::Substs;
34 use rustc::util::nodemap::FxHashMap;
35 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
36 use rustc_data_structures::transitive_relation::TransitiveRelation;
40 use super::ToRegionVid;
43 pub struct UniversalRegions<'tcx> {
44 indices: UniversalRegionIndices<'tcx>,
46 /// The vid assigned to `'static`
47 pub fr_static: RegionVid,
49 /// A special region vid created to represent the current MIR fn
50 /// body. It will outlive the entire CFG but it will not outlive
51 /// any other universal regions.
52 pub fr_fn_body: RegionVid,
54 /// We create region variables such that they are ordered by their
55 /// `RegionClassification`. The first block are globals, then
56 /// externals, then locals. So things from:
57 /// - `FIRST_GLOBAL_INDEX..first_extern_index` are global;
58 /// - `first_extern_index..first_local_index` are external; and
59 /// - first_local_index..num_universals` are local.
60 first_extern_index: usize,
62 /// See `first_extern_index`.
63 first_local_index: usize,
65 /// The total number of universal region variables instantiated.
66 num_universals: usize,
68 /// The "defining" type for this function, with all universal
69 /// regions instantiated. For a closure or generator, this is the
70 /// closure type, but for a top-level function it's the `TyFnDef`.
71 pub defining_ty: DefiningTy<'tcx>,
73 /// The return type of this function, with all regions replaced by
74 /// their universal `RegionVid` equivalents.
76 /// NB. Associated types in this type have not been normalized,
77 /// as the name suggests. =)
78 pub unnormalized_output_ty: Ty<'tcx>,
80 /// The fully liberated input types of this function, with all
81 /// regions replaced by their universal `RegionVid` equivalents.
83 /// NB. Associated types in these types have not been normalized,
84 /// as the name suggests. =)
85 pub unnormalized_input_tys: &'tcx [Ty<'tcx>],
87 /// Each RBP `('a, GK)` indicates that `GK: 'a` can be assumed to
88 /// be true. These encode relationships like `T: 'a` that are
89 /// added via implicit bounds.
91 /// Each region here is guaranteed to be a key in the `indices`
92 /// map. We use the "original" regions (i.e., the keys from the
93 /// map, and not the values) because the code in
94 /// `process_registered_region_obligations` has some special-cased
95 /// logic expecting to see (e.g.) `ReStatic`, and if we supplied
96 /// our special inference variable there, we would mess that up.
97 pub region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
99 pub yield_ty: Option<Ty<'tcx>>,
101 relations: UniversalRegionRelations,
104 /// The "defining type" for this MIR. The key feature of the "defining
105 /// type" is that it contains the information needed to derive all the
106 /// universal regions that are in scope as well as the types of the
107 /// inputs/output from the MIR. In general, early-bound universal
108 /// regions appear free in the defining type and late-bound regions
109 /// appear bound in the signature.
110 #[derive(Copy, Clone, Debug)]
111 pub enum DefiningTy<'tcx> {
112 /// The MIR is a closure. The signature is found via
113 /// `ClosureSubsts::closure_sig_ty`.
114 Closure(DefId, ty::ClosureSubsts<'tcx>),
116 /// The MIR is a generator. The signature is that generators take
117 /// no parameters and return the result of
118 /// `ClosureSubsts::generator_return_ty`.
119 Generator(DefId, ty::GeneratorSubsts<'tcx>, hir::GeneratorMovability),
121 /// The MIR is a fn item with the given def-id and substs. The signature
122 /// of the function can be bound then with the `fn_sig` query.
123 FnDef(DefId, &'tcx Substs<'tcx>),
125 /// The MIR represents some form of constant. The signature then
126 /// is that it has no inputs and a single return value, which is
127 /// the value of the constant.
128 Const(DefId, &'tcx Substs<'tcx>),
132 struct UniversalRegionIndices<'tcx> {
133 /// For those regions that may appear in the parameter environment
134 /// ('static and early-bound regions), we maintain a map from the
135 /// `ty::Region` to the internal `RegionVid` we are using. This is
136 /// used because trait matching and type-checking will feed us
137 /// region constraints that reference those regions and we need to
138 /// be able to map them our internal `RegionVid`. This is
139 /// basically equivalent to a `Substs`, except that it also
140 /// contains an entry for `ReStatic` -- it might be nice to just
141 /// use a substs, and then handle `ReStatic` another way.
142 indices: FxHashMap<ty::Region<'tcx>, RegionVid>,
146 struct UniversalRegionRelations {
147 /// Stores the outlives relations that are known to hold from the
148 /// implied bounds, in-scope where clauses, and that sort of
150 outlives: TransitiveRelation<RegionVid>,
152 /// This is the `<=` relation; that is, if `a: b`, then `b <= a`,
153 /// and we store that here. This is useful when figuring out how
154 /// to express some local region in terms of external regions our
155 /// caller will understand.
156 inverse_outlives: TransitiveRelation<RegionVid>,
159 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
160 pub enum RegionClassification {
161 /// A **global** region is one that can be named from
162 /// anywhere. There is only one, `'static`.
165 /// An **external** region is only relevant for closures. In that
166 /// case, it refers to regions that are free in the closure type
167 /// -- basically, something bound in the surrounding context.
169 /// Consider this example:
172 /// fn foo<'a, 'b>(a: &'a u32, b: &'b u32, c: &'static u32) {
173 /// let closure = for<'x> |x: &'x u32| { .. };
174 /// ^^^^^^^ pretend this were legal syntax
175 /// for declaring a late-bound region in
176 /// a closure signature
180 /// Here, the lifetimes `'a` and `'b` would be **external** to the
183 /// If we are not analyzing a closure, there are no external
187 /// A **local** lifetime is one about which we know the full set
188 /// of relevant constraints (that is, relationships to other named
189 /// regions). For a closure, this includes any region bound in
190 /// the closure's signature. For a fn item, this includes all
191 /// regions other than global ones.
193 /// Continuing with the example from `External`, if we were
194 /// analyzing the closure, then `'x` would be local (and `'a` and
195 /// `'b` are external). If we are analyzing the function item
196 /// `foo`, then `'a` and `'b` are local (and `'x` is not in
201 const FIRST_GLOBAL_INDEX: usize = 0;
203 impl<'tcx> UniversalRegions<'tcx> {
204 /// Creates a new and fully initialized `UniversalRegions` that
205 /// contains indices for all the free regions found in the given
206 /// MIR -- that is, all the regions that appear in the function's
207 /// signature. This will also compute the relationships that are
208 /// known between those regions.
210 infcx: &InferCtxt<'_, '_, 'tcx>,
212 param_env: ty::ParamEnv<'tcx>,
215 let mir_node_id = tcx.hir.as_local_node_id(mir_def_id).unwrap();
216 let mir_hir_id = tcx.hir.node_to_hir_id(mir_node_id);
217 UniversalRegionsBuilder {
223 region_bound_pairs: vec![],
224 relations: UniversalRegionRelations {
225 outlives: TransitiveRelation::new(),
226 inverse_outlives: TransitiveRelation::new(),
231 /// Given a reference to a closure type, extracts all the values
232 /// from its free regions and returns a vector with them. This is
233 /// used when the closure's creator checks that the
234 /// `ClosureRegionRequirements` are met. The requirements from
235 /// `ClosureRegionRequirements` are expressed in terms of
236 /// `RegionVid` entries that map into the returned vector `V`: so
237 /// if the `ClosureRegionRequirements` contains something like
238 /// `'1: '2`, then the caller would impose the constraint that
240 pub fn closure_mapping(
241 infcx: &InferCtxt<'_, '_, 'tcx>,
242 closure_ty: Ty<'tcx>,
243 expected_num_vars: usize,
244 ) -> IndexVec<RegionVid, ty::Region<'tcx>> {
245 let mut region_mapping = IndexVec::with_capacity(expected_num_vars);
246 region_mapping.push(infcx.tcx.types.re_static);
247 infcx.tcx.for_each_free_region(&closure_ty, |fr| {
248 region_mapping.push(fr);
252 region_mapping.len(),
254 "index vec had unexpected number of variables"
260 /// True if `r` is a member of this set of universal regions.
261 pub fn is_universal_region(&self, r: RegionVid) -> bool {
262 (FIRST_GLOBAL_INDEX..self.num_universals).contains(&r.index())
265 /// Classifies `r` as a universal region, returning `None` if this
266 /// is not a member of this set of universal regions.
267 pub fn region_classification(&self, r: RegionVid) -> Option<RegionClassification> {
268 let index = r.index();
269 if (FIRST_GLOBAL_INDEX..self.first_extern_index).contains(&index) {
270 Some(RegionClassification::Global)
271 } else if (self.first_extern_index..self.first_local_index).contains(&index) {
272 Some(RegionClassification::External)
273 } else if (self.first_local_index..self.num_universals).contains(&index) {
274 Some(RegionClassification::Local)
280 /// Returns an iterator over all the RegionVids corresponding to
281 /// universally quantified free regions.
282 pub fn universal_regions(&self) -> impl Iterator<Item = RegionVid> {
283 (FIRST_GLOBAL_INDEX..self.num_universals).map(RegionVid::new)
286 /// True if `r` is classified as an local region.
287 pub fn is_local_free_region(&self, r: RegionVid) -> bool {
288 self.region_classification(r) == Some(RegionClassification::Local)
291 /// Returns the number of universal regions created in any category.
292 pub fn len(&self) -> usize {
296 /// Given two universal regions, returns the postdominating
297 /// upper-bound (effectively the least upper bound).
299 /// (See `TransitiveRelation::postdom_upper_bound` for details on
300 /// the postdominating upper bound in general.)
301 pub fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
302 assert!(self.is_universal_region(fr1));
303 assert!(self.is_universal_region(fr2));
306 .postdom_upper_bound(&fr1, &fr2)
307 .unwrap_or(&self.fr_static)
310 /// Finds an "upper bound" for `fr` that is not local. In other
311 /// words, returns the smallest (*) known region `fr1` that (a)
312 /// outlives `fr` and (b) is not local. This cannot fail, because
313 /// we will always find `'static` at worst.
315 /// (*) If there are multiple competing choices, we pick the "postdominating"
316 /// one. See `TransitiveRelation::postdom_upper_bound` for details.
317 pub fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid {
318 debug!("non_local_upper_bound(fr={:?})", fr);
319 self.non_local_bound(&self.relations.inverse_outlives, fr)
320 .unwrap_or(self.fr_static)
323 /// Finds a "lower bound" for `fr` that is not local. In other
324 /// words, returns the largest (*) known region `fr1` that (a) is
325 /// outlived by `fr` and (b) is not local. This cannot fail,
326 /// because we will always find `'static` at worst.
328 /// (*) If there are multiple competing choices, we pick the "postdominating"
329 /// one. See `TransitiveRelation::postdom_upper_bound` for details.
330 pub fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> {
331 debug!("non_local_lower_bound(fr={:?})", fr);
332 self.non_local_bound(&self.relations.outlives, fr)
335 /// Returns the number of global plus external universal regions.
336 /// For closures, these are the regions that appear free in the
337 /// closure type (versus those bound in the closure
338 /// signature). They are therefore the regions between which the
339 /// closure may impose constraints that its creator must verify.
340 pub fn num_global_and_external_regions(&self) -> usize {
341 self.first_local_index
344 /// Helper for `non_local_upper_bound` and
345 /// `non_local_lower_bound`. Repeatedly invokes `postdom_parent`
346 /// until we find something that is not local. Returns None if we
350 relation: &TransitiveRelation<RegionVid>,
352 ) -> Option<RegionVid> {
353 // This method assumes that `fr0` is one of the universally
354 // quantified region variables.
355 assert!(self.is_universal_region(fr0));
357 let mut external_parents = vec![];
358 let mut queue = vec![&fr0];
360 // Keep expanding `fr` into its parents until we reach
361 // non-local regions.
362 while let Some(fr) = queue.pop() {
363 if !self.is_local_free_region(*fr) {
364 external_parents.push(fr);
368 queue.extend(relation.parents(fr));
371 debug!("non_local_bound: external_parents={:?}", external_parents);
373 // In case we find more than one, reduce to one for
374 // convenience. This is to prevent us from generating more
375 // complex constraints, but it will cause spurious errors.
376 let post_dom = relation
377 .mutual_immediate_postdominator(external_parents)
380 debug!("non_local_bound: post_dom={:?}", post_dom);
382 post_dom.and_then(|post_dom| {
383 // If the mutual immediate postdom is not local, then
384 // there is no non-local result we can return.
385 if !self.is_local_free_region(post_dom) {
393 /// True if fr1 is known to outlive fr2.
395 /// This will only ever be true for universally quantified regions.
396 pub fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
397 self.relations.outlives.contains(&fr1, &fr2)
400 /// Returns a vector of free regions `x` such that `fr1: x` is
402 pub fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<&RegionVid> {
403 self.relations.outlives.reachable_from(&fr1)
406 /// Get an iterator over all the early-bound regions that have names.
407 pub fn named_universal_regions<'s>(
409 ) -> impl Iterator<Item = (ty::Region<'tcx>, ty::RegionVid)> + 's {
410 self.indices.indices.iter().map(|(&r, &v)| (r, v))
413 /// See `UniversalRegionIndices::to_region_vid`.
414 pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid {
415 self.indices.to_region_vid(r)
419 struct UniversalRegionsBuilder<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
420 infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
423 mir_node_id: ast::NodeId,
424 param_env: ty::ParamEnv<'tcx>,
425 region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
426 relations: UniversalRegionRelations,
429 const FR: NLLRegionVariableOrigin = NLLRegionVariableOrigin::FreeRegion;
431 impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> {
432 fn build(mut self) -> UniversalRegions<'tcx> {
433 debug!("build(mir_def_id={:?})", self.mir_def_id);
435 let param_env = self.param_env;
436 debug!("build: param_env={:?}", param_env);
438 assert_eq!(FIRST_GLOBAL_INDEX, self.infcx.num_region_vars());
440 // Create the "global" region that is always free in all contexts: 'static.
441 let fr_static = self.infcx.next_nll_region_var(FR).to_region_vid();
443 // We've now added all the global regions. The next ones we
444 // add will be external.
445 let first_extern_index = self.infcx.num_region_vars();
447 let defining_ty = self.defining_ty();
448 debug!("build: defining_ty={:?}", defining_ty);
450 let mut indices = self.compute_indices(fr_static, defining_ty);
451 debug!("build: indices={:?}", indices);
453 let bound_inputs_and_output = self.compute_inputs_and_output(&indices, defining_ty);
455 // "Liberate" the late-bound regions. These correspond to
456 // "local" free regions.
457 let first_local_index = self.infcx.num_region_vars();
458 let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars(
461 &bound_inputs_and_output,
464 let fr_fn_body = self.infcx.next_nll_region_var(FR).to_region_vid();
465 let num_universals = self.infcx.num_region_vars();
467 // Insert the facts we know from the predicates. Why? Why not.
468 self.add_outlives_bounds(&indices, bounds::explicit_outlives_bounds(param_env));
470 // Add the implied bounds from inputs and outputs.
471 for ty in inputs_and_output {
472 debug!("build: input_or_output={:?}", ty);
473 self.add_implied_bounds(&indices, ty);
477 // - outlives is reflexive, so `'r: 'r` for every region `'r`
478 // - `'static: 'r` for every region `'r`
479 // - `'r: 'fn_body` for every (other) universally quantified
480 // region `'r`, all of which are provided by our caller
481 for fr in (FIRST_GLOBAL_INDEX..num_universals).map(RegionVid::new) {
483 "build: relating free region {:?} to itself and to 'static",
486 self.relations.relate_universal_regions(fr, fr);
487 self.relations.relate_universal_regions(fr_static, fr);
488 self.relations.relate_universal_regions(fr, fr_fn_body);
491 let (unnormalized_output_ty, unnormalized_input_tys) =
492 inputs_and_output.split_last().unwrap();
495 "build: global regions = {}..{}",
500 "build: extern regions = {}..{}",
505 "build: local regions = {}..{}",
510 let yield_ty = match defining_ty {
511 DefiningTy::Generator(def_id, substs, _) => {
512 Some(substs.yield_ty(def_id, self.infcx.tcx))
525 unnormalized_output_ty,
526 unnormalized_input_tys,
527 region_bound_pairs: self.region_bound_pairs,
529 relations: self.relations,
533 /// Returns the "defining type" of the current MIR;
534 /// see `DefiningTy` for details.
535 fn defining_ty(&self) -> DefiningTy<'tcx> {
536 let tcx = self.infcx.tcx;
537 let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id);
539 match tcx.hir.body_owner_kind(self.mir_node_id) {
540 BodyOwnerKind::Fn => {
541 let defining_ty = if self.mir_def_id == closure_base_def_id {
542 tcx.type_of(closure_base_def_id)
544 let tables = tcx.typeck_tables_of(self.mir_def_id);
545 tables.node_id_to_type(self.mir_hir_id)
548 let defining_ty = self.infcx
549 .replace_free_regions_with_nll_infer_vars(FR, &defining_ty);
551 match defining_ty.sty {
552 ty::TyClosure(def_id, substs) => DefiningTy::Closure(def_id, substs),
553 ty::TyGenerator(def_id, substs, movability) => {
554 DefiningTy::Generator(def_id, substs, movability)
556 ty::TyFnDef(def_id, substs) => DefiningTy::FnDef(def_id, substs),
558 tcx.def_span(self.mir_def_id),
559 "expected defining type for `{:?}`: `{:?}`",
566 BodyOwnerKind::Const | BodyOwnerKind::Static(..) => {
567 assert_eq!(closure_base_def_id, self.mir_def_id);
568 let identity_substs = Substs::identity_for_item(tcx, closure_base_def_id);
569 let substs = self.infcx
570 .replace_free_regions_with_nll_infer_vars(FR, &identity_substs);
571 DefiningTy::Const(self.mir_def_id, substs)
576 /// Builds a hashmap that maps from the universal regions that are
577 /// in scope (as a `ty::Region<'tcx>`) to their indices (as a
578 /// `RegionVid`). The map returned by this function contains only
579 /// the early-bound regions.
582 fr_static: RegionVid,
583 defining_ty: DefiningTy<'tcx>,
584 ) -> UniversalRegionIndices<'tcx> {
585 let tcx = self.infcx.tcx;
586 let gcx = tcx.global_tcx();
587 let closure_base_def_id = tcx.closure_base_def_id(self.mir_def_id);
588 let identity_substs = Substs::identity_for_item(gcx, closure_base_def_id);
589 let fr_substs = match defining_ty {
590 DefiningTy::Closure(_, ClosureSubsts { ref substs }) |
591 DefiningTy::Generator(_, GeneratorSubsts { ref substs }, _) => {
592 // In the case of closures, we rely on the fact that
593 // the first N elements in the ClosureSubsts are
594 // inherited from the `closure_base_def_id`.
595 // Therefore, when we zip together (below) with
596 // `identity_substs`, we will get only those regions
597 // that correspond to early-bound regions declared on
598 // the `closure_base_def_id`.
599 assert!(substs.len() >= identity_substs.len());
600 assert_eq!(substs.regions().count(), identity_substs.regions().count());
604 DefiningTy::FnDef(_, substs) | DefiningTy::Const(_, substs) => substs,
607 let global_mapping = iter::once((gcx.types.re_static, fr_static));
608 let subst_mapping = identity_substs
610 .zip(fr_substs.regions().map(|r| r.to_region_vid()));
612 UniversalRegionIndices {
613 indices: global_mapping.chain(subst_mapping).collect(),
617 fn compute_inputs_and_output(
619 indices: &UniversalRegionIndices<'tcx>,
620 defining_ty: DefiningTy<'tcx>,
621 ) -> ty::Binder<&'tcx ty::Slice<Ty<'tcx>>> {
622 let tcx = self.infcx.tcx;
624 DefiningTy::Closure(def_id, substs) => {
625 assert_eq!(self.mir_def_id, def_id);
626 let closure_sig = substs.closure_sig_ty(def_id, tcx).fn_sig(tcx);
627 let inputs_and_output = closure_sig.inputs_and_output();
628 let closure_ty = tcx.closure_env_ty(def_id, substs).unwrap();
632 |closure_ty, inputs_and_output| {
633 // The "inputs" of the closure in the
634 // signature appear as a tuple. The MIR side
635 // flattens this tuple.
636 let (&output, tuplized_inputs) = inputs_and_output.split_last().unwrap();
637 assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs");
638 let inputs = match tuplized_inputs[0].sty {
639 ty::TyTuple(inputs) => inputs,
640 _ => bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]),
644 iter::once(closure_ty)
645 .chain(inputs.iter().cloned())
646 .chain(iter::once(output)),
652 DefiningTy::Generator(def_id, substs, movability) => {
653 assert_eq!(self.mir_def_id, def_id);
654 let output = substs.return_ty(def_id, tcx);
655 let generator_ty = tcx.mk_generator(def_id, substs, movability);
656 let inputs_and_output = self.infcx.tcx.intern_type_list(&[generator_ty, output]);
657 ty::Binder::dummy(inputs_and_output)
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()
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_id, def_id);
670 let ty = tcx.type_of(def_id);
671 let ty = indices.fold_to_region_vids(tcx, &ty);
672 ty::Binder::dummy(tcx.intern_type_list(&[ty]))
677 /// Update the type of a single local, which should represent
678 /// either the return type of the MIR or one of its arguments. At
679 /// the same time, compute and add any implied bounds that come
682 /// Assumes that `universal_regions` indices map is fully constructed.
683 fn add_implied_bounds(&mut self, indices: &UniversalRegionIndices<'tcx>, ty: Ty<'tcx>) {
684 debug!("add_implied_bounds(ty={:?})", ty);
685 let span = self.infcx.tcx.def_span(self.mir_def_id);
686 let bounds = self.infcx
687 .implied_outlives_bounds(self.param_env, self.mir_node_id, ty, span);
688 self.add_outlives_bounds(indices, bounds);
691 /// Registers the `OutlivesBound` items from `outlives_bounds` in
692 /// the outlives relation as well as the region-bound pairs
694 fn add_outlives_bounds<I>(&mut self, indices: &UniversalRegionIndices<'tcx>, outlives_bounds: I)
696 I: IntoIterator<Item = OutlivesBound<'tcx>>,
698 for outlives_bound in outlives_bounds {
699 debug!("add_outlives_bounds(bound={:?})", outlives_bound);
701 match outlives_bound {
702 OutlivesBound::RegionSubRegion(r1, r2) => {
703 // The bound says that `r1 <= r2`; we store `r2: r1`.
704 let r1 = indices.to_region_vid(r1);
705 let r2 = indices.to_region_vid(r2);
706 self.relations.relate_universal_regions(r2, r1);
709 OutlivesBound::RegionSubParam(r_a, param_b) => {
710 self.region_bound_pairs
711 .push((r_a, GenericKind::Param(param_b)));
714 OutlivesBound::RegionSubProjection(r_a, projection_b) => {
715 self.region_bound_pairs
716 .push((r_a, GenericKind::Projection(projection_b)));
723 impl UniversalRegionRelations {
724 /// Records in the `outlives_relation` (and
725 /// `inverse_outlives_relation`) that `fr_a: fr_b`.
726 fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
728 "relate_universal_regions: fr_a={:?} outlives fr_b={:?}",
732 self.outlives.add(fr_a, fr_b);
733 self.inverse_outlives.add(fr_b, fr_a);
737 trait InferCtxtExt<'tcx> {
738 fn replace_free_regions_with_nll_infer_vars<T>(
740 origin: NLLRegionVariableOrigin,
744 T: TypeFoldable<'tcx>;
746 fn replace_bound_regions_with_nll_infer_vars<T>(
748 origin: NLLRegionVariableOrigin,
749 all_outlive_scope: DefId,
750 value: &ty::Binder<T>,
751 indices: &mut UniversalRegionIndices<'tcx>,
754 T: TypeFoldable<'tcx>;
757 impl<'cx, 'gcx, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'cx, 'gcx, 'tcx> {
758 fn replace_free_regions_with_nll_infer_vars<T>(
760 origin: NLLRegionVariableOrigin,
764 T: TypeFoldable<'tcx>,
766 self.tcx.fold_regions(value, &mut false, |_region, _depth| {
767 self.next_nll_region_var(origin)
771 fn replace_bound_regions_with_nll_infer_vars<T>(
773 origin: NLLRegionVariableOrigin,
774 all_outlive_scope: DefId,
775 value: &ty::Binder<T>,
776 indices: &mut UniversalRegionIndices<'tcx>,
779 T: TypeFoldable<'tcx>,
782 "replace_bound_regions_with_nll_infer_vars(value={:?}, all_outlive_scope={:?})",
786 let (value, _map) = self.tcx.replace_late_bound_regions(value, |br| {
787 let liberated_region = self.tcx.mk_region(ty::ReFree(ty::FreeRegion {
788 scope: all_outlive_scope,
791 let region_vid = self.next_nll_region_var(origin);
792 indices.insert_late_bound_region(liberated_region, region_vid.to_region_vid());
793 debug!("liberated_region={:?} => {:?}", liberated_region, region_vid);
800 impl<'tcx> UniversalRegionIndices<'tcx> {
801 /// Initially, the `UniversalRegionIndices` map contains only the
802 /// early-bound regions in scope. Once that is all setup, we come
803 /// in later and instantiate the late-bound regions, and then we
804 /// insert the `ReFree` version of those into the map as
805 /// well. These are used for error reporting.
806 fn insert_late_bound_region(&mut self, r: ty::Region<'tcx>,
809 self.indices.insert(r, vid);
812 /// Converts `r` into a local inference variable: `r` can either
813 /// by a `ReVar` (i.e., already a reference to an inference
814 /// variable) or it can be `'static` or some early-bound
815 /// region. This is useful when taking the results from
816 /// type-checking and trait-matching, which may sometimes
817 /// reference those regions from the `ParamEnv`. It is also used
818 /// during initialization. Relies on the `indices` map having been
819 /// fully initialized.
820 pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid {
821 if let ty::ReVar(..) = r {
824 *self.indices.get(&r).unwrap_or_else(|| {
825 bug!("cannot convert `{:?}` to a region vid", r)
830 /// Replace all free regions in `value` with region vids, as
831 /// returned by `to_region_vid`.
832 pub fn fold_to_region_vids<T>(&self, tcx: TyCtxt<'_, '_, 'tcx>, value: &T) -> T
834 T: TypeFoldable<'tcx>,
836 tcx.fold_regions(value, &mut false, |region, _| {
837 tcx.mk_region(ty::ReVar(self.to_region_vid(region)))
842 /// This trait is used by the `impl-trait` constraint code to abstract
843 /// over the `FreeRegionMap` from lexical regions and
844 /// `UniversalRegions` (from NLL)`.
845 impl<'tcx> FreeRegionRelations<'tcx> for UniversalRegions<'tcx> {
846 fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool {
847 let shorter = shorter.to_region_vid();
848 assert!(self.is_universal_region(shorter));
849 let longer = longer.to_region_vid();
850 assert!(self.is_universal_region(longer));
851 self.outlives(longer, shorter)