]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use crate::ty::{self, Lift, Region, TyCtxt}; |
ff7c6d11 XL |
2 | use rustc_data_structures::transitive_relation::TransitiveRelation; |
3 | ||
60c5eb7d | 4 | #[derive(Clone, RustcEncodable, RustcDecodable, Debug, Default, HashStable)] |
ff7c6d11 XL |
5 | pub struct FreeRegionMap<'tcx> { |
6 | // Stores the relation `a < b`, where `a` and `b` are regions. | |
7 | // | |
8 | // Invariant: only free regions like `'x` or `'static` are stored | |
9 | // in this relation, not scopes. | |
dfeec247 | 10 | relation: TransitiveRelation<Region<'tcx>>, |
ff7c6d11 XL |
11 | } |
12 | ||
13 | impl<'tcx> FreeRegionMap<'tcx> { | |
dfeec247 | 14 | pub fn elements(&self) -> impl Iterator<Item = &Region<'tcx>> { |
dc9dc135 XL |
15 | self.relation.elements() |
16 | } | |
17 | ||
ff7c6d11 XL |
18 | pub fn is_empty(&self) -> bool { |
19 | self.relation.is_empty() | |
20 | } | |
21 | ||
22 | // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`. | |
23 | // (with the exception that `'static: 'x` is not notable) | |
24 | pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) { | |
25 | debug!("relate_regions(sub={:?}, sup={:?})", sub, sup); | |
74b04a01 | 26 | if self.is_free_or_static(sub) && self.is_free(sup) { |
ff7c6d11 XL |
27 | self.relation.add(sub, sup) |
28 | } | |
29 | } | |
30 | ||
74b04a01 XL |
31 | /// Tests whether `r_a <= r_b`. |
32 | /// | |
33 | /// Both regions must meet `is_free_or_static`. | |
34 | /// | |
35 | /// Subtle: one tricky case that this code gets correct is as | |
36 | /// follows. If we know that `r_b: 'static`, then this function | |
37 | /// will return true, even though we don't know anything that | |
38 | /// directly relates `r_a` and `r_b`. | |
39 | /// | |
40 | /// Also available through the `FreeRegionRelations` trait below. | |
41 | pub fn sub_free_regions( | |
42 | &self, | |
43 | tcx: TyCtxt<'tcx>, | |
44 | r_a: Region<'tcx>, | |
45 | r_b: Region<'tcx>, | |
46 | ) -> bool { | |
47 | assert!(self.is_free_or_static(r_a) && self.is_free_or_static(r_b)); | |
48 | let re_static = tcx.lifetimes.re_static; | |
49 | if self.check_relation(re_static, r_b) { | |
50 | // `'a <= 'static` is always true, and not stored in the | |
51 | // relation explicitly, so check if `'b` is `'static` (or | |
52 | // equivalent to it) | |
53 | true | |
54 | } else { | |
55 | self.check_relation(r_a, r_b) | |
56 | } | |
57 | } | |
58 | ||
59 | /// Check whether `r_a <= r_b` is found in the relation. | |
60 | fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool { | |
61 | r_a == r_b || self.relation.contains(&r_a, &r_b) | |
62 | } | |
63 | ||
64 | /// True for free regions other than `'static`. | |
65 | pub fn is_free(&self, r: Region<'_>) -> bool { | |
66 | match *r { | |
67 | ty::ReEarlyBound(_) | ty::ReFree(_) => true, | |
68 | _ => false, | |
69 | } | |
70 | } | |
71 | ||
72 | /// True if `r` is a free region or static of the sort that this | |
73 | /// free region map can be used with. | |
74 | pub fn is_free_or_static(&self, r: Region<'_>) -> bool { | |
75 | match *r { | |
76 | ty::ReStatic => true, | |
77 | _ => self.is_free(r), | |
78 | } | |
79 | } | |
80 | ||
9fa01778 | 81 | /// Computes the least-upper-bound of two free regions. In some |
ff7c6d11 XL |
82 | /// cases, this is more conservative than necessary, in order to |
83 | /// avoid making arbitrary choices. See | |
84 | /// `TransitiveRelation::postdom_upper_bound` for more details. | |
dc9dc135 XL |
85 | pub fn lub_free_regions( |
86 | &self, | |
87 | tcx: TyCtxt<'tcx>, | |
88 | r_a: Region<'tcx>, | |
89 | r_b: Region<'tcx>, | |
90 | ) -> Region<'tcx> { | |
ff7c6d11 | 91 | debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b); |
74b04a01 XL |
92 | assert!(self.is_free(r_a)); |
93 | assert!(self.is_free(r_b)); | |
dfeec247 XL |
94 | let result = if r_a == r_b { |
95 | r_a | |
96 | } else { | |
ff7c6d11 | 97 | match self.relation.postdom_upper_bound(&r_a, &r_b) { |
74b04a01 | 98 | None => tcx.lifetimes.re_static, |
ff7c6d11 XL |
99 | Some(r) => *r, |
100 | } | |
101 | }; | |
102 | debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result); | |
103 | result | |
104 | } | |
105 | } | |
106 | ||
107 | /// The NLL region handling code represents free region relations in a | |
108 | /// slightly different way; this trait allows functions to be abstract | |
109 | /// over which version is in use. | |
110 | pub trait FreeRegionRelations<'tcx> { | |
111 | /// Tests whether `r_a <= r_b`. Both must be free regions or | |
112 | /// `'static`. | |
74b04a01 XL |
113 | fn sub_free_regions( |
114 | &self, | |
115 | tcx: TyCtxt<'tcx>, | |
116 | shorter: ty::Region<'tcx>, | |
117 | longer: ty::Region<'tcx>, | |
118 | ) -> bool; | |
ff7c6d11 XL |
119 | } |
120 | ||
121 | impl<'tcx> FreeRegionRelations<'tcx> for FreeRegionMap<'tcx> { | |
74b04a01 XL |
122 | fn sub_free_regions(&self, tcx: TyCtxt<'tcx>, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool { |
123 | // invoke the "inherent method" | |
124 | self.sub_free_regions(tcx, r_a, r_b) | |
ff7c6d11 XL |
125 | } |
126 | } | |
127 | ||
ff7c6d11 XL |
128 | impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> { |
129 | type Lifted = FreeRegionMap<'tcx>; | |
dc9dc135 | 130 | fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> { |
dfeec247 | 131 | self.relation.maybe_map(|&fr| tcx.lift(&fr)).map(|relation| FreeRegionMap { relation }) |
ff7c6d11 XL |
132 | } |
133 | } |