rustc_type_ir/region_kind.rs
1use std::fmt;
2
3use derive_where::derive_where;
4#[cfg(feature = "nightly")]
5use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
6#[cfg(feature = "nightly")]
7use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
8
9use self::RegionKind::*;
10use crate::{DebruijnIndex, Interner};
11
12rustc_index::newtype_index! {
13 /// A **region** **v**ariable **ID**.
14 #[encodable]
15 #[orderable]
16 #[debug_format = "'?{}"]
17 #[gate_rustc_only]
18 #[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
19 pub struct RegionVid {}
20}
21
22/// Representation of regions. Note that the NLL checker uses a distinct
23/// representation of regions. For this reason, it internally replaces all the
24/// regions with inference variables -- the index of the variable is then used
25/// to index into internal NLL data structures. See `rustc_const_eval::borrow_check`
26/// module for more information.
27///
28/// Note: operations are on the wrapper `Region` type, which is interned,
29/// rather than this type.
30///
31/// ## The Region lattice within a given function
32///
33/// In general, the region lattice looks like
34///
35/// ```text
36/// static ----------+-----...------+ (greatest)
37/// | | |
38/// param regions | |
39/// | | |
40/// | | |
41/// | | |
42/// empty(root) placeholder(U1) |
43/// | / |
44/// | / placeholder(Un)
45/// empty(U1) -- /
46/// | /
47/// ... /
48/// | /
49/// empty(Un) -------- (smallest)
50/// ```
51///
52/// Early-bound/free regions are the named lifetimes in scope from the
53/// function declaration. They have relationships to one another
54/// determined based on the declared relationships from the
55/// function.
56///
57/// Note that inference variables and bound regions are not included
58/// in this diagram. In the case of inference variables, they should
59/// be inferred to some other region from the diagram. In the case of
60/// bound regions, they are excluded because they don't make sense to
61/// include -- the diagram indicates the relationship between free
62/// regions.
63///
64/// ## Inference variables
65///
66/// During region inference, we sometimes create inference variables,
67/// represented as `ReVar`. These will be inferred by the code in
68/// `infer::lexical_region_resolve` to some free region from the
69/// lattice above (the minimal region that meets the
70/// constraints).
71///
72/// During NLL checking, where regions are defined differently, we
73/// also use `ReVar` -- in that case, the index is used to index into
74/// the NLL region checker's data structures. The variable may in fact
75/// represent either a free region or an inference variable, in that
76/// case.
77///
78/// ## Bound Regions
79///
80/// These are regions that are stored behind a binder and must be instantiated
81/// with some concrete region before being used. There are two kind of
82/// bound regions: early-bound, which are bound in an item's `Generics`,
83/// and are instantiated by an `GenericArgs`, and late-bound, which are part of
84/// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are instantiated by
85/// the likes of `liberate_late_bound_regions`. The distinction exists
86/// because higher-ranked lifetimes aren't supported in all places. See [1][2].
87///
88/// Unlike `Param`s, bound regions are not supposed to exist "in the wild"
89/// outside their binder, e.g., in types passed to type inference, and
90/// should first be instantiated (by placeholder regions, free regions,
91/// or region variables).
92///
93/// ## Placeholder and Free Regions
94///
95/// One often wants to work with bound regions without knowing their precise
96/// identity. For example, when checking a function, the lifetime of a borrow
97/// can end up being assigned to some region parameter. In these cases,
98/// it must be ensured that bounds on the region can't be accidentally
99/// assumed without being checked.
100///
101/// To do this, we replace the bound regions with placeholder markers,
102/// which don't satisfy any relation not explicitly provided.
103///
104/// There are two kinds of placeholder regions in rustc: `ReLateParam` and
105/// `RePlaceholder`. When checking an item's body, `ReLateParam` is supposed
106/// to be used. These also support explicit bounds: both the internally-stored
107/// *scope*, which the region is assumed to outlive, as well as other
108/// relations stored in the `FreeRegionMap`. Note that these relations
109/// aren't checked when you `make_subregion` (or `eq_types`), only by
110/// `resolve_regions_and_report_errors`.
111///
112/// When working with higher-ranked types, some region relations aren't
113/// yet known, so you can't just call `resolve_regions_and_report_errors`.
114/// `RePlaceholder` is designed for this purpose. In these contexts,
115/// there's also the risk that some inference variable laying around will
116/// get unified with your placeholder region: if you want to check whether
117/// `for<'a> Foo<'_>: 'a`, and you instantiate your bound region `'a`
118/// with a placeholder region `'%a`, the variable `'_` would just be
119/// instantiated to the placeholder region `'%a`, which is wrong because
120/// the inference variable is supposed to satisfy the relation
121/// *for every value of the placeholder region*. To ensure that doesn't
122/// happen, you can use `leak_check`. This is more clearly explained
123/// by the [rustc dev guide].
124///
125/// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
126/// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
127/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
128#[derive_where(Clone, Copy, Hash, PartialEq, Eq; I: Interner)]
129#[cfg_attr(feature = "nightly", derive(Encodable_NoContext, Decodable_NoContext))]
130pub enum RegionKind<I: Interner> {
131 /// A region parameter; for example `'a` in `impl<'a> Trait for &'a ()`.
132 ///
133 /// There are some important differences between region and type parameters.
134 /// Not all region parameters in the source are represented via `ReEarlyParam`:
135 /// late-bound function parameters are instead lowered to a `ReBound`. Late-bound
136 /// regions get eagerly replaced with `ReLateParam` which behaves in the same way as
137 /// `ReEarlyParam`. Region parameters are also sometimes implicit,
138 /// e.g. in `impl Trait for &()`.
139 ReEarlyParam(I::EarlyParamRegion),
140
141 /// A higher-ranked region. These represent either late-bound function parameters
142 /// or bound variables from a `for<'a>`-binder.
143 ///
144 /// While inside of a function, e.g. during typeck, the late-bound function parameters
145 /// can be converted to `ReLateParam` by calling `tcx.liberate_late_bound_regions`.
146 ///
147 /// Bound regions inside of types **must not** be erased, as they impact trait
148 /// selection and the `TypeId` of that type. `for<'a> fn(&'a ())` and
149 /// `fn(&'static ())` are different types and have to be treated as such.
150 ReBound(DebruijnIndex, I::BoundRegion),
151
152 /// Late-bound function parameters are represented using a `ReBound`. When
153 /// inside of a function, we convert these bound variables to placeholder
154 /// parameters via `tcx.liberate_late_bound_regions`. They are then treated
155 /// the same way as `ReEarlyParam` while inside of the function.
156 ///
157 /// See <https://rustc-dev-guide.rust-lang.org/early-late-bound-params/early-late-bound-summary.html> for
158 /// more info about early and late bound lifetime parameters.
159 ReLateParam(I::LateParamRegion),
160
161 /// Static data that has an "infinite" lifetime. Top in the region lattice.
162 ReStatic,
163
164 /// A region variable. Should not exist outside of type inference.
165 ReVar(RegionVid),
166
167 /// A placeholder region -- the higher-ranked version of `ReLateParam`.
168 /// Should not exist outside of type inference.
169 ///
170 /// Used when instantiating a `forall` binder via `infcx.enter_forall`.
171 RePlaceholder(I::PlaceholderRegion),
172
173 /// Erased region, used by trait selection, in MIR and during codegen.
174 ReErased,
175
176 /// A region that resulted from some other error. Used exclusively for diagnostics.
177 ReError(I::ErrorGuaranteed),
178}
179
180impl<I: Interner> fmt::Debug for RegionKind<I> {
181 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
182 match self {
183 ReEarlyParam(data) => write!(f, "{data:?}"),
184
185 ReBound(binder_id, bound_region) => {
186 write!(f, "'")?;
187 crate::debug_bound_var(f, *binder_id, bound_region)
188 }
189
190 ReLateParam(fr) => write!(f, "{fr:?}"),
191
192 ReStatic => f.write_str("'static"),
193
194 ReVar(vid) => write!(f, "{vid:?}"),
195
196 RePlaceholder(placeholder) => write!(f, "{placeholder:?}"),
197
198 // Use `'{erased}` as the output instead of `'erased` so that its more obviously distinct from
199 // a `ReEarlyParam` named `'erased`. Technically that would print as `'erased/#IDX` so this is
200 // not strictly necessary but *shrug*
201 ReErased => f.write_str("'{erased}"),
202
203 ReError(_) => f.write_str("'{region error}"),
204 }
205 }
206}
207
208#[cfg(feature = "nightly")]
209// This is not a derived impl because a derive would require `I: HashStable`
210impl<CTX, I: Interner> HashStable<CTX> for RegionKind<I>
211where
212 I::EarlyParamRegion: HashStable<CTX>,
213 I::BoundRegion: HashStable<CTX>,
214 I::LateParamRegion: HashStable<CTX>,
215 I::PlaceholderRegion: HashStable<CTX>,
216{
217 #[inline]
218 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
219 std::mem::discriminant(self).hash_stable(hcx, hasher);
220 match self {
221 ReErased | ReStatic | ReError(_) => {
222 // No variant fields to hash for these ...
223 }
224 ReBound(d, r) => {
225 d.hash_stable(hcx, hasher);
226 r.hash_stable(hcx, hasher);
227 }
228 ReEarlyParam(r) => {
229 r.hash_stable(hcx, hasher);
230 }
231 ReLateParam(r) => {
232 r.hash_stable(hcx, hasher);
233 }
234 RePlaceholder(r) => {
235 r.hash_stable(hcx, hasher);
236 }
237 ReVar(_) => {
238 panic!("region variables should not be hashed: {self:?}")
239 }
240 }
241 }
242}