]>
Commit | Line | Data |
---|---|---|
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 | 6 | use rustc_data_structures::transitive_relation::TransitiveRelation; |
064997fb | 7 | use 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 | 13 | pub(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 | ||
20 | impl<'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 | |
3dfed10e | 30 | #[derive(Clone, Debug, Default)] |
ff7c6d11 XL |
31 | pub 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. | |
dfeec247 | 36 | relation: TransitiveRelation<Region<'tcx>>, |
ff7c6d11 XL |
37 | } |
38 | ||
39 | impl<'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 | ||
48 | // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`. | |
49 | // (with the exception that `'static: 'x` is not notable) | |
50 | pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) { | |
51 | debug!("relate_regions(sub={:?}, sup={:?})", sub, sup); | |
064997fb | 52 | if sub.is_free_or_static() && sup.is_free() { |
ff7c6d11 XL |
53 | self.relation.add(sub, sup) |
54 | } | |
55 | } | |
56 | ||
74b04a01 XL |
57 | /// Tests whether `r_a <= r_b`. |
58 | /// | |
59 | /// Both regions must meet `is_free_or_static`. | |
60 | /// | |
61 | /// Subtle: one tricky case that this code gets correct is as | |
62 | /// follows. If we know that `r_b: 'static`, then this function | |
63 | /// will return true, even though we don't know anything that | |
64 | /// directly relates `r_a` and `r_b`. | |
74b04a01 XL |
65 | pub fn sub_free_regions( |
66 | &self, | |
67 | tcx: TyCtxt<'tcx>, | |
68 | r_a: Region<'tcx>, | |
69 | r_b: Region<'tcx>, | |
70 | ) -> bool { | |
064997fb | 71 | assert!(r_a.is_free_or_static() && r_b.is_free_or_static()); |
74b04a01 XL |
72 | let re_static = tcx.lifetimes.re_static; |
73 | if self.check_relation(re_static, r_b) { | |
74 | // `'a <= 'static` is always true, and not stored in the | |
75 | // relation explicitly, so check if `'b` is `'static` (or | |
76 | // equivalent to it) | |
77 | true | |
78 | } else { | |
79 | self.check_relation(r_a, r_b) | |
80 | } | |
81 | } | |
82 | ||
83 | /// Check whether `r_a <= r_b` is found in the relation. | |
84 | fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool { | |
5e7ed085 | 85 | r_a == r_b || self.relation.contains(r_a, r_b) |
74b04a01 XL |
86 | } |
87 | ||
9fa01778 | 88 | /// Computes the least-upper-bound of two free regions. In some |
ff7c6d11 XL |
89 | /// cases, this is more conservative than necessary, in order to |
90 | /// avoid making arbitrary choices. See | |
91 | /// `TransitiveRelation::postdom_upper_bound` for more details. | |
dc9dc135 XL |
92 | pub fn lub_free_regions( |
93 | &self, | |
94 | tcx: TyCtxt<'tcx>, | |
95 | r_a: Region<'tcx>, | |
96 | r_b: Region<'tcx>, | |
97 | ) -> Region<'tcx> { | |
ff7c6d11 | 98 | debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b); |
064997fb FG |
99 | assert!(r_a.is_free()); |
100 | assert!(r_b.is_free()); | |
dfeec247 XL |
101 | let result = if r_a == r_b { |
102 | r_a | |
103 | } else { | |
5e7ed085 | 104 | match self.relation.postdom_upper_bound(r_a, r_b) { |
74b04a01 | 105 | None => tcx.lifetimes.re_static, |
5e7ed085 | 106 | Some(r) => r, |
ff7c6d11 XL |
107 | } |
108 | }; | |
109 | debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result); | |
110 | result | |
111 | } | |
112 | } | |
113 | ||
ff7c6d11 XL |
114 | impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> { |
115 | type Lifted = FreeRegionMap<'tcx>; | |
29967ef6 | 116 | fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> { |
5e7ed085 | 117 | self.relation.maybe_map(|fr| tcx.lift(fr)).map(|relation| FreeRegionMap { relation }) |
ff7c6d11 XL |
118 | } |
119 | } |