]> git.proxmox.com Git - rustc.git/blame - compiler/rustc_infer/src/infer/free_regions.rs
New upstream version 1.66.0+dfsg1
[rustc.git] / compiler / rustc_infer / src / infer / free_regions.rs
CommitLineData
f9f354fc
XL
1//! This module handles the relationships between "free regions", i.e., lifetime parameters.
2//! Ordinarily, free regions are unrelated to one another, but they can be related via implied
3//! or explicit bounds. In that case, we track the bounds using the `TransitiveRelation` type,
4//! and use that to decide when one free region outlives another, and so forth.
5
ff7c6d11 6use rustc_data_structures::transitive_relation::TransitiveRelation;
064997fb 7use rustc_middle::ty::{Lift, Region, TyCtxt};
f9f354fc 8
3dfed10e 9/// Combines a `FreeRegionMap` and a `TyCtxt`.
f9f354fc
XL
10///
11/// This stuff is a bit convoluted and should be refactored, but as we
12/// transition to NLL, it'll all go away anyhow.
a2a8927a 13pub(crate) struct RegionRelations<'a, 'tcx> {
f9f354fc
XL
14 pub tcx: TyCtxt<'tcx>,
15
f9f354fc
XL
16 /// Free-region relationships.
17 pub free_regions: &'a FreeRegionMap<'tcx>,
18}
19
20impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
064997fb
FG
21 pub fn new(tcx: TyCtxt<'tcx>, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
22 Self { tcx, free_regions }
f9f354fc
XL
23 }
24
25 pub fn lub_free_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
26 self.free_regions.lub_free_regions(self.tcx, r_a, r_b)
27 }
28}
ff7c6d11 29
f2b60f7d 30#[derive(Clone, Debug)]
ff7c6d11
XL
31pub struct FreeRegionMap<'tcx> {
32 // Stores the relation `a < b`, where `a` and `b` are regions.
33 //
34 // Invariant: only free regions like `'x` or `'static` are stored
35 // in this relation, not scopes.
f2b60f7d 36 pub(crate) relation: TransitiveRelation<Region<'tcx>>,
ff7c6d11
XL
37}
38
39impl<'tcx> FreeRegionMap<'tcx> {
5099ac24
FG
40 pub fn elements(&self) -> impl Iterator<Item = Region<'tcx>> + '_ {
41 self.relation.elements().copied()
dc9dc135
XL
42 }
43
ff7c6d11
XL
44 pub fn is_empty(&self) -> bool {
45 self.relation.is_empty()
46 }
47
74b04a01
XL
48 /// Tests whether `r_a <= r_b`.
49 ///
50 /// Both regions must meet `is_free_or_static`.
51 ///
52 /// Subtle: one tricky case that this code gets correct is as
53 /// follows. If we know that `r_b: 'static`, then this function
54 /// will return true, even though we don't know anything that
55 /// directly relates `r_a` and `r_b`.
74b04a01
XL
56 pub fn sub_free_regions(
57 &self,
58 tcx: TyCtxt<'tcx>,
59 r_a: Region<'tcx>,
60 r_b: Region<'tcx>,
61 ) -> bool {
064997fb 62 assert!(r_a.is_free_or_static() && r_b.is_free_or_static());
74b04a01
XL
63 let re_static = tcx.lifetimes.re_static;
64 if self.check_relation(re_static, r_b) {
65 // `'a <= 'static` is always true, and not stored in the
66 // relation explicitly, so check if `'b` is `'static` (or
67 // equivalent to it)
68 true
69 } else {
70 self.check_relation(r_a, r_b)
71 }
72 }
73
74 /// Check whether `r_a <= r_b` is found in the relation.
75 fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
5e7ed085 76 r_a == r_b || self.relation.contains(r_a, r_b)
74b04a01
XL
77 }
78
9fa01778 79 /// Computes the least-upper-bound of two free regions. In some
ff7c6d11
XL
80 /// cases, this is more conservative than necessary, in order to
81 /// avoid making arbitrary choices. See
82 /// `TransitiveRelation::postdom_upper_bound` for more details.
dc9dc135
XL
83 pub fn lub_free_regions(
84 &self,
85 tcx: TyCtxt<'tcx>,
86 r_a: Region<'tcx>,
87 r_b: Region<'tcx>,
88 ) -> Region<'tcx> {
ff7c6d11 89 debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
064997fb
FG
90 assert!(r_a.is_free());
91 assert!(r_b.is_free());
dfeec247
XL
92 let result = if r_a == r_b {
93 r_a
94 } else {
5e7ed085 95 match self.relation.postdom_upper_bound(r_a, r_b) {
74b04a01 96 None => tcx.lifetimes.re_static,
5e7ed085 97 Some(r) => r,
ff7c6d11
XL
98 }
99 };
100 debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
101 result
102 }
103}
104
ff7c6d11
XL
105impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
106 type Lifted = FreeRegionMap<'tcx>;
29967ef6 107 fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
5e7ed085 108 self.relation.maybe_map(|fr| tcx.lift(fr)).map(|relation| FreeRegionMap { relation })
ff7c6d11
XL
109 }
110}