]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | //! Lexical region resolution. |
2 | ||
3 | use crate::infer::region_constraints::Constraint; | |
4 | use crate::infer::region_constraints::GenericKind; | |
5 | use crate::infer::region_constraints::RegionConstraintData; | |
6 | use crate::infer::region_constraints::VarInfos; | |
7 | use crate::infer::region_constraints::VerifyBound; | |
f9f354fc | 8 | use crate::infer::RegionRelations; |
9fa01778 XL |
9 | use crate::infer::RegionVariableOrigin; |
10 | use crate::infer::SubregionOrigin; | |
abe05a73 | 11 | use rustc_data_structures::fx::FxHashSet; |
0bf4aa26 XL |
12 | use rustc_data_structures::graph::implementation::{ |
13 | Direction, Graph, NodeIndex, INCOMING, OUTGOING, | |
14 | }; | |
5099ac24 | 15 | use rustc_data_structures::intern::Interned; |
49aad941 | 16 | use rustc_index::{IndexSlice, IndexVec}; |
ba9703b0 | 17 | use rustc_middle::ty::fold::TypeFoldable; |
f2b60f7d | 18 | use rustc_middle::ty::PlaceholderRegion; |
ba9703b0 | 19 | use rustc_middle::ty::{self, Ty, TyCtxt}; |
9ffffee4 | 20 | use rustc_middle::ty::{ReEarlyBound, ReErased, ReError, ReFree, ReStatic}; |
f9f354fc | 21 | use rustc_middle::ty::{ReLateBound, RePlaceholder, ReVar}; |
ba9703b0 | 22 | use rustc_middle::ty::{Region, RegionVid}; |
a2a8927a | 23 | use rustc_span::Span; |
abe05a73 | 24 | use std::fmt; |
abe05a73 | 25 | |
923072b8 FG |
26 | use super::outlives::test_type_match; |
27 | ||
abe05a73 XL |
28 | /// This function performs lexical region resolution given a complete |
29 | /// set of constraints and variable origins. It performs a fixed-point | |
30 | /// iteration to find region values which satisfy all constraints, | |
31 | /// assuming such values can be found. It returns the final values of | |
32 | /// all the variables as well as a set of errors that must be reported. | |
3c0e092e | 33 | #[instrument(level = "debug", skip(region_rels, var_infos, data))] |
a2a8927a | 34 | pub(crate) fn resolve<'tcx>( |
923072b8 | 35 | param_env: ty::ParamEnv<'tcx>, |
dc9dc135 | 36 | region_rels: &RegionRelations<'_, 'tcx>, |
83c7162d | 37 | var_infos: VarInfos, |
abe05a73 | 38 | data: RegionConstraintData<'tcx>, |
dc9dc135 | 39 | ) -> (LexicalRegionResolutions<'tcx>, Vec<RegionResolutionError<'tcx>>) { |
abe05a73 | 40 | let mut errors = vec![]; |
923072b8 FG |
41 | let mut resolver = LexicalResolver { param_env, region_rels, var_infos, data }; |
42 | let values = resolver.infer_variable_values(&mut errors); | |
43 | (values, errors) | |
abe05a73 XL |
44 | } |
45 | ||
46 | /// Contains the result of lexical region resolution. Offers methods | |
47 | /// to lookup up the final value of a region variable. | |
5099ac24 | 48 | #[derive(Clone)] |
abe05a73 | 49 | pub struct LexicalRegionResolutions<'tcx> { |
923072b8 | 50 | pub(crate) values: IndexVec<RegionVid, VarValue<'tcx>>, |
abe05a73 XL |
51 | } |
52 | ||
53 | #[derive(Copy, Clone, Debug)] | |
923072b8 | 54 | pub(crate) enum VarValue<'tcx> { |
9c376795 | 55 | /// Empty lifetime is for data that is never accessed. We tag the |
f2b60f7d FG |
56 | /// empty lifetime with a universe -- the idea is that we don't |
57 | /// want `exists<'a> { forall<'b> { 'b: 'a } }` to be satisfiable. | |
58 | /// Therefore, the `'empty` in a universe `U` is less than all | |
59 | /// regions visible from `U`, but not less than regions not visible | |
60 | /// from `U`. | |
61 | Empty(ty::UniverseIndex), | |
abe05a73 XL |
62 | Value(Region<'tcx>), |
63 | ErrorValue, | |
64 | } | |
65 | ||
66 | #[derive(Clone, Debug)] | |
67 | pub enum RegionResolutionError<'tcx> { | |
68 | /// `ConcreteFailure(o, a, b)`: | |
69 | /// | |
70 | /// `o` requires that `a <= b`, but this does not hold | |
71 | ConcreteFailure(SubregionOrigin<'tcx>, Region<'tcx>, Region<'tcx>), | |
72 | ||
9ffffee4 | 73 | /// `GenericBoundFailure(p, s, a)`: |
abe05a73 XL |
74 | /// |
75 | /// The parameter/associated-type `p` must be known to outlive the lifetime | |
76 | /// `a` (but none of the known bounds are sufficient). | |
77 | GenericBoundFailure(SubregionOrigin<'tcx>, GenericKind<'tcx>, Region<'tcx>), | |
78 | ||
0731742a | 79 | /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`: |
abe05a73 | 80 | /// |
0731742a XL |
81 | /// Could not infer a value for `v` (which has origin `v_origin`) |
82 | /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and | |
abe05a73 XL |
83 | /// `sub_r <= sup_r` does not hold. |
84 | SubSupConflict( | |
0731742a | 85 | RegionVid, |
abe05a73 XL |
86 | RegionVariableOrigin, |
87 | SubregionOrigin<'tcx>, | |
88 | Region<'tcx>, | |
89 | SubregionOrigin<'tcx>, | |
90 | Region<'tcx>, | |
a2a8927a | 91 | Vec<Span>, // All the influences on a given value that didn't meet its constraints. |
abe05a73 | 92 | ), |
dc9dc135 | 93 | |
74b04a01 XL |
94 | /// Indicates a `'b: 'a` constraint where `'a` is in a universe that |
95 | /// cannot name the placeholder `'b`. | |
96 | UpperBoundUniverseConflict( | |
97 | RegionVid, | |
98 | RegionVariableOrigin, | |
99 | ty::UniverseIndex, // the universe index of the region variable | |
100 | SubregionOrigin<'tcx>, // cause of the constraint | |
101 | Region<'tcx>, // the placeholder `'b` | |
102 | ), | |
abe05a73 XL |
103 | } |
104 | ||
49aad941 FG |
105 | impl<'tcx> RegionResolutionError<'tcx> { |
106 | pub fn origin(&self) -> &SubregionOrigin<'tcx> { | |
107 | match self { | |
108 | RegionResolutionError::ConcreteFailure(origin, _, _) | |
109 | | RegionResolutionError::GenericBoundFailure(origin, _, _) | |
110 | | RegionResolutionError::SubSupConflict(_, _, origin, _, _, _, _) | |
111 | | RegionResolutionError::UpperBoundUniverseConflict(_, _, _, origin, _) => origin, | |
112 | } | |
113 | } | |
114 | } | |
115 | ||
abe05a73 XL |
116 | struct RegionAndOrigin<'tcx> { |
117 | region: Region<'tcx>, | |
118 | origin: SubregionOrigin<'tcx>, | |
119 | } | |
120 | ||
8faf50e0 | 121 | type RegionGraph<'tcx> = Graph<(), Constraint<'tcx>>; |
abe05a73 | 122 | |
dc9dc135 | 123 | struct LexicalResolver<'cx, 'tcx> { |
923072b8 | 124 | param_env: ty::ParamEnv<'tcx>, |
dc9dc135 | 125 | region_rels: &'cx RegionRelations<'cx, 'tcx>, |
83c7162d | 126 | var_infos: VarInfos, |
abe05a73 XL |
127 | data: RegionConstraintData<'tcx>, |
128 | } | |
129 | ||
dc9dc135 XL |
130 | impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { |
131 | fn tcx(&self) -> TyCtxt<'tcx> { | |
0bf4aa26 XL |
132 | self.region_rels.tcx |
133 | } | |
134 | ||
abe05a73 XL |
135 | fn infer_variable_values( |
136 | &mut self, | |
137 | errors: &mut Vec<RegionResolutionError<'tcx>>, | |
138 | ) -> LexicalRegionResolutions<'tcx> { | |
f2b60f7d | 139 | let mut var_data = self.construct_var_data(); |
abe05a73 | 140 | |
064997fb FG |
141 | if cfg!(debug_assertions) { |
142 | self.dump_constraints(); | |
143 | } | |
abe05a73 | 144 | |
3c0e092e | 145 | self.expansion(&mut var_data); |
abe05a73 | 146 | self.collect_errors(&mut var_data, errors); |
49aad941 | 147 | self.collect_var_errors(&var_data, errors); |
abe05a73 XL |
148 | var_data |
149 | } | |
150 | ||
151 | fn num_vars(&self) -> usize { | |
83c7162d | 152 | self.var_infos.len() |
abe05a73 XL |
153 | } |
154 | ||
155 | /// Initially, the value for all variables is set to `'empty`, the | |
156 | /// empty region. The `expansion` phase will grow this larger. | |
f2b60f7d | 157 | fn construct_var_data(&self) -> LexicalRegionResolutions<'tcx> { |
abe05a73 | 158 | LexicalRegionResolutions { |
74b04a01 XL |
159 | values: IndexVec::from_fn_n( |
160 | |vid| { | |
161 | let vid_universe = self.var_infos[vid].universe; | |
f2b60f7d | 162 | VarValue::Empty(vid_universe) |
74b04a01 XL |
163 | }, |
164 | self.num_vars(), | |
165 | ), | |
abe05a73 XL |
166 | } |
167 | } | |
168 | ||
064997fb FG |
169 | #[instrument(level = "debug", skip(self))] |
170 | fn dump_constraints(&self) { | |
abe05a73 XL |
171 | for (idx, (constraint, _)) in self.data.constraints.iter().enumerate() { |
172 | debug!("Constraint {} => {:?}", idx, constraint); | |
173 | } | |
174 | } | |
175 | ||
f2b60f7d FG |
176 | /// Gets the LUb of a given region and the empty region |
177 | fn lub_empty(&self, a_region: Region<'tcx>) -> Result<Region<'tcx>, PlaceholderRegion> { | |
178 | match *a_region { | |
179 | ReLateBound(..) | ReErased => { | |
180 | bug!("cannot relate region: {:?}", a_region); | |
181 | } | |
182 | ||
183 | ReVar(v_id) => { | |
184 | span_bug!( | |
185 | self.var_infos[v_id].origin.span(), | |
186 | "lub invoked with non-concrete regions: {:?}", | |
187 | a_region, | |
188 | ); | |
189 | } | |
190 | ||
191 | ReStatic => { | |
192 | // nothing lives longer than `'static` | |
193 | Ok(self.tcx().lifetimes.re_static) | |
194 | } | |
195 | ||
9ffffee4 FG |
196 | ReError(_) => Ok(a_region), |
197 | ||
f2b60f7d FG |
198 | ReEarlyBound(_) | ReFree(_) => { |
199 | // All empty regions are less than early-bound, free, | |
200 | // and scope regions. | |
201 | Ok(a_region) | |
202 | } | |
203 | ||
204 | RePlaceholder(placeholder) => Err(placeholder), | |
205 | } | |
206 | } | |
207 | ||
abe05a73 | 208 | fn expansion(&self, var_values: &mut LexicalRegionResolutions<'tcx>) { |
f2b60f7d FG |
209 | // In the first pass, we expand region vids according to constraints we |
210 | // have previously found. In the second pass, we loop through the region | |
211 | // vids we expanded and expand *across* region vids (effectively | |
212 | // "expanding" new `RegSubVar` constraints). | |
213 | ||
214 | // Tracks the `VarSubVar` constraints generated for each region vid. We | |
215 | // later use this to expand across vids. | |
353b0b11 | 216 | let mut constraints = IndexVec::from_elem(Vec::new(), &var_values.values); |
f2b60f7d | 217 | // Tracks the changed region vids. |
dfeec247 XL |
218 | let mut changes = Vec::new(); |
219 | for constraint in self.data.constraints.keys() { | |
f2b60f7d | 220 | match *constraint { |
abe05a73 XL |
221 | Constraint::RegSubVar(a_region, b_vid) => { |
222 | let b_data = var_values.value_mut(b_vid); | |
f2b60f7d FG |
223 | |
224 | if self.expand_node(a_region, b_vid, b_data) { | |
225 | changes.push(b_vid); | |
226 | } | |
abe05a73 XL |
227 | } |
228 | Constraint::VarSubVar(a_vid, b_vid) => match *var_values.value(a_vid) { | |
dfeec247 | 229 | VarValue::ErrorValue => continue, |
f2b60f7d FG |
230 | VarValue::Empty(a_universe) => { |
231 | let b_data = var_values.value_mut(b_vid); | |
232 | ||
9c376795 | 233 | let changed = match *b_data { |
f2b60f7d FG |
234 | VarValue::Empty(b_universe) => { |
235 | // Empty regions are ordered according to the universe | |
236 | // they are associated with. | |
237 | let ui = a_universe.min(b_universe); | |
238 | ||
239 | debug!( | |
240 | "Expanding value of {:?} \ | |
241 | from empty lifetime with universe {:?} \ | |
242 | to empty lifetime with universe {:?}", | |
243 | b_vid, b_universe, ui | |
244 | ); | |
245 | ||
246 | *b_data = VarValue::Empty(ui); | |
247 | true | |
248 | } | |
249 | VarValue::Value(cur_region) => { | |
250 | let lub = match self.lub_empty(cur_region) { | |
251 | Ok(r) => r, | |
252 | // If the empty and placeholder regions are in the same universe, | |
253 | // then the LUB is the Placeholder region (which is the cur_region). | |
254 | // If they are not in the same universe, the LUB is the Static lifetime. | |
255 | Err(placeholder) if a_universe == placeholder.universe => { | |
256 | cur_region | |
257 | } | |
258 | Err(_) => self.tcx().lifetimes.re_static, | |
259 | }; | |
260 | ||
261 | if lub == cur_region { | |
9c376795 FG |
262 | false |
263 | } else { | |
264 | debug!( | |
265 | "Expanding value of {:?} from {:?} to {:?}", | |
266 | b_vid, cur_region, lub | |
267 | ); | |
268 | ||
269 | *b_data = VarValue::Value(lub); | |
270 | true | |
f2b60f7d | 271 | } |
f2b60f7d FG |
272 | } |
273 | ||
274 | VarValue::ErrorValue => false, | |
9c376795 | 275 | }; |
f2b60f7d FG |
276 | |
277 | if changed { | |
278 | changes.push(b_vid); | |
279 | } | |
280 | match b_data { | |
281 | VarValue::Value(Region(Interned(ReStatic, _))) | |
282 | | VarValue::ErrorValue => (), | |
283 | _ => { | |
284 | constraints[a_vid].push((a_vid, b_vid)); | |
285 | constraints[b_vid].push((a_vid, b_vid)); | |
286 | } | |
287 | } | |
288 | } | |
abe05a73 | 289 | VarValue::Value(a_region) => { |
9fa01778 | 290 | let b_data = var_values.value_mut(b_vid); |
f2b60f7d FG |
291 | |
292 | if self.expand_node(a_region, b_vid, b_data) { | |
293 | changes.push(b_vid); | |
294 | } | |
295 | match b_data { | |
296 | VarValue::Value(Region(Interned(ReStatic, _))) | |
297 | | VarValue::ErrorValue => (), | |
298 | _ => { | |
299 | constraints[a_vid].push((a_vid, b_vid)); | |
300 | constraints[b_vid].push((a_vid, b_vid)); | |
301 | } | |
302 | } | |
abe05a73 XL |
303 | } |
304 | }, | |
305 | Constraint::RegSubReg(..) | Constraint::VarSubReg(..) => { | |
306 | // These constraints are checked after expansion | |
307 | // is done, in `collect_errors`. | |
dfeec247 | 308 | continue; |
abe05a73 | 309 | } |
e74abb32 | 310 | } |
dfeec247 | 311 | } |
e74abb32 | 312 | |
dfeec247 XL |
313 | while let Some(vid) = changes.pop() { |
314 | constraints[vid].retain(|&(a_vid, b_vid)| { | |
5e7ed085 FG |
315 | let VarValue::Value(a_region) = *var_values.value(a_vid) else { |
316 | return false; | |
dfeec247 XL |
317 | }; |
318 | let b_data = var_values.value_mut(b_vid); | |
319 | if self.expand_node(a_region, b_vid, b_data) { | |
320 | changes.push(b_vid); | |
321 | } | |
5099ac24 FG |
322 | !matches!( |
323 | b_data, | |
324 | VarValue::Value(Region(Interned(ReStatic, _))) | VarValue::ErrorValue | |
325 | ) | |
dfeec247 | 326 | }); |
e74abb32 | 327 | } |
abe05a73 XL |
328 | } |
329 | ||
f2b60f7d FG |
330 | /// Expands the value of the region represented with `b_vid` with current |
331 | /// value `b_data` to the lub of `b_data` and `a_region`. The corresponds | |
332 | /// with the constraint `'?b: 'a` (`'a <: '?b`), where `'a` is some known | |
333 | /// region and `'?b` is some region variable. | |
abe05a73 XL |
334 | fn expand_node( |
335 | &self, | |
336 | a_region: Region<'tcx>, | |
337 | b_vid: RegionVid, | |
338 | b_data: &mut VarValue<'tcx>, | |
339 | ) -> bool { | |
340 | debug!("expand_node({:?}, {:?} == {:?})", a_region, b_vid, b_data); | |
341 | ||
abe05a73 | 342 | match *b_data { |
f2b60f7d FG |
343 | VarValue::Empty(empty_ui) => { |
344 | let lub = match self.lub_empty(a_region) { | |
345 | Ok(r) => r, | |
346 | // If this empty region is from a universe that can | |
347 | // name the placeholder, then the placeholder is | |
348 | // larger; otherwise, the only ancestor is `'static`. | |
349 | Err(placeholder) if empty_ui.can_name(placeholder.universe) => { | |
9ffffee4 | 350 | self.tcx().mk_re_placeholder(placeholder) |
f2b60f7d FG |
351 | } |
352 | Err(_) => self.tcx().lifetimes.re_static, | |
353 | }; | |
354 | ||
355 | debug!("Expanding value of {:?} from empty lifetime to {:?}", b_vid, lub); | |
356 | ||
357 | *b_data = VarValue::Value(lub); | |
358 | true | |
359 | } | |
abe05a73 | 360 | VarValue::Value(cur_region) => { |
e74abb32 XL |
361 | // This is a specialized version of the `lub_concrete_regions` |
362 | // check below for a common case, here purely as an | |
363 | // optimization. | |
74b04a01 | 364 | let b_universe = self.var_infos[b_vid].universe; |
e74abb32 | 365 | |
0731742a | 366 | let mut lub = self.lub_concrete_regions(a_region, cur_region); |
abe05a73 XL |
367 | if lub == cur_region { |
368 | return false; | |
369 | } | |
370 | ||
0731742a XL |
371 | // Watch out for `'b: !1` relationships, where the |
372 | // universe of `'b` can't name the placeholder `!1`. In | |
373 | // that case, we have to grow `'b` to be `'static` for the | |
374 | // relationship to hold. This is obviously a kind of sub-optimal | |
375 | // choice -- in the future, when we incorporate a knowledge | |
376 | // of the parameter environment, we might be able to find a | |
377 | // tighter bound than `'static`. | |
378 | // | |
379 | // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.) | |
5e7ed085 FG |
380 | if let ty::RePlaceholder(p) = *lub && b_universe.cannot_name(p.universe) { |
381 | lub = self.tcx().lifetimes.re_static; | |
0731742a XL |
382 | } |
383 | ||
dc9dc135 | 384 | debug!("Expanding value of {:?} from {:?} to {:?}", b_vid, cur_region, lub); |
abe05a73 XL |
385 | |
386 | *b_data = VarValue::Value(lub); | |
ba9703b0 | 387 | true |
abe05a73 XL |
388 | } |
389 | ||
ba9703b0 | 390 | VarValue::ErrorValue => false, |
abe05a73 XL |
391 | } |
392 | } | |
393 | ||
f2b60f7d FG |
394 | /// True if `a <= b`. |
395 | fn sub_region_values(&self, a: VarValue<'tcx>, b: VarValue<'tcx>) -> bool { | |
396 | match (a, b) { | |
397 | // Error region is `'static` | |
398 | (VarValue::ErrorValue, _) | (_, VarValue::ErrorValue) => return true, | |
399 | (VarValue::Empty(a_ui), VarValue::Empty(b_ui)) => { | |
400 | // Empty regions are ordered according to the universe | |
401 | // they are associated with. | |
402 | a_ui.min(b_ui) == b_ui | |
403 | } | |
404 | (VarValue::Value(a), VarValue::Empty(_)) => { | |
405 | match *a { | |
9ffffee4 FG |
406 | // this is always on an error path, |
407 | // so it doesn't really matter if it's shorter or longer than an empty region | |
408 | ReError(_) => false, | |
409 | ||
f2b60f7d FG |
410 | ReLateBound(..) | ReErased => { |
411 | bug!("cannot relate region: {:?}", a); | |
412 | } | |
413 | ||
414 | ReVar(v_id) => { | |
415 | span_bug!( | |
416 | self.var_infos[v_id].origin.span(), | |
417 | "lub_concrete_regions invoked with non-concrete region: {:?}", | |
418 | a | |
419 | ); | |
420 | } | |
421 | ||
422 | ReStatic | ReEarlyBound(_) | ReFree(_) => { | |
423 | // nothing lives longer than `'static` | |
424 | ||
425 | // All empty regions are less than early-bound, free, | |
426 | // and scope regions. | |
427 | ||
428 | false | |
429 | } | |
430 | ||
431 | RePlaceholder(_) => { | |
432 | // The LUB is either `a` or `'static` | |
433 | false | |
434 | } | |
435 | } | |
436 | } | |
437 | (VarValue::Empty(a_ui), VarValue::Value(b)) => { | |
438 | match *b { | |
9ffffee4 FG |
439 | // this is always on an error path, |
440 | // so it doesn't really matter if it's shorter or longer than an empty region | |
441 | ReError(_) => false, | |
442 | ||
f2b60f7d FG |
443 | ReLateBound(..) | ReErased => { |
444 | bug!("cannot relate region: {:?}", b); | |
445 | } | |
446 | ||
447 | ReVar(v_id) => { | |
448 | span_bug!( | |
449 | self.var_infos[v_id].origin.span(), | |
450 | "lub_concrete_regions invoked with non-concrete regions: {:?}", | |
451 | b | |
452 | ); | |
453 | } | |
454 | ||
455 | ReStatic | ReEarlyBound(_) | ReFree(_) => { | |
456 | // nothing lives longer than `'static` | |
457 | // All empty regions are less than early-bound, free, | |
458 | // and scope regions. | |
459 | true | |
460 | } | |
461 | ||
462 | RePlaceholder(placeholder) => { | |
463 | // If this empty region is from a universe that can | |
464 | // name the placeholder, then the placeholder is | |
465 | // larger; otherwise, the only ancestor is `'static`. | |
9c376795 | 466 | return a_ui.can_name(placeholder.universe); |
f2b60f7d FG |
467 | } |
468 | } | |
469 | } | |
470 | (VarValue::Value(a), VarValue::Value(b)) => self.sub_concrete_regions(a, b), | |
471 | } | |
472 | } | |
473 | ||
dc9dc135 | 474 | /// True if `a <= b`, but not defined over inference variables. |
3c0e092e | 475 | #[instrument(level = "trace", skip(self))] |
dc9dc135 | 476 | fn sub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> bool { |
74b04a01 XL |
477 | let tcx = self.tcx(); |
478 | let sub_free_regions = |r1, r2| self.region_rels.free_regions.sub_free_regions(tcx, r1, r2); | |
479 | ||
480 | // Check for the case where we know that `'b: 'static` -- in that case, | |
481 | // `a <= b` for all `a`. | |
064997fb | 482 | let b_free_or_static = b.is_free_or_static(); |
74b04a01 XL |
483 | if b_free_or_static && sub_free_regions(tcx.lifetimes.re_static, b) { |
484 | return true; | |
485 | } | |
486 | ||
487 | // If both `a` and `b` are free, consult the declared | |
9c376795 | 488 | // relationships. Note that this can be more precise than the |
74b04a01 XL |
489 | // `lub` relationship defined below, since sometimes the "lub" |
490 | // is actually the `postdom_upper_bound` (see | |
491 | // `TransitiveRelation` for more details). | |
064997fb | 492 | let a_free_or_static = a.is_free_or_static(); |
74b04a01 XL |
493 | if a_free_or_static && b_free_or_static { |
494 | return sub_free_regions(a, b); | |
495 | } | |
496 | ||
497 | // For other cases, leverage the LUB code to find the LUB and | |
498 | // check if it is equal to `b`. | |
dc9dc135 XL |
499 | self.lub_concrete_regions(a, b) == b |
500 | } | |
501 | ||
74b04a01 XL |
502 | /// Returns the least-upper-bound of `a` and `b`; i.e., the |
503 | /// smallest region `c` such that `a <= c` and `b <= c`. | |
504 | /// | |
505 | /// Neither `a` nor `b` may be an inference variable (hence the | |
506 | /// term "concrete regions"). | |
f2b60f7d | 507 | #[instrument(level = "trace", skip(self), ret)] |
abe05a73 | 508 | fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> { |
f2b60f7d | 509 | match (*a, *b) { |
5099ac24 | 510 | (ReLateBound(..), _) | (_, ReLateBound(..)) | (ReErased, _) | (_, ReErased) => { |
abe05a73 XL |
511 | bug!("cannot relate region: LUB({:?}, {:?})", a, b); |
512 | } | |
513 | ||
5099ac24 | 514 | (ReVar(v_id), _) | (_, ReVar(v_id)) => { |
abe05a73 | 515 | span_bug!( |
83c7162d | 516 | self.var_infos[v_id].origin.span(), |
abe05a73 XL |
517 | "lub_concrete_regions invoked with non-concrete \ |
518 | regions: {:?}, {:?}", | |
519 | a, | |
520 | b | |
521 | ); | |
522 | } | |
523 | ||
9ffffee4 FG |
524 | (ReError(_), _) => a, |
525 | ||
526 | (_, ReError(_)) => b, | |
527 | ||
5099ac24 | 528 | (ReStatic, _) | (_, ReStatic) => { |
74b04a01 XL |
529 | // nothing lives longer than `'static` |
530 | self.tcx().lifetimes.re_static | |
531 | } | |
532 | ||
5099ac24 | 533 | (ReEarlyBound(_) | ReFree(_), ReEarlyBound(_) | ReFree(_)) => { |
ba9703b0 XL |
534 | self.region_rels.lub_free_regions(a, b) |
535 | } | |
abe05a73 XL |
536 | |
537 | // For these types, we cannot define any additional | |
538 | // relationship: | |
5099ac24 | 539 | (RePlaceholder(..), _) | (_, RePlaceholder(..)) => { |
dc9dc135 XL |
540 | if a == b { |
541 | a | |
542 | } else { | |
e74abb32 | 543 | self.tcx().lifetimes.re_static |
dc9dc135 XL |
544 | } |
545 | } | |
f2b60f7d | 546 | } |
abe05a73 XL |
547 | } |
548 | ||
549 | /// After expansion is complete, go and check upper bounds (i.e., | |
550 | /// cases where the region cannot grow larger than a fixed point) | |
551 | /// and check that they are satisfied. | |
3c0e092e | 552 | #[instrument(skip(self, var_data, errors))] |
abe05a73 XL |
553 | fn collect_errors( |
554 | &self, | |
555 | var_data: &mut LexicalRegionResolutions<'tcx>, | |
556 | errors: &mut Vec<RegionResolutionError<'tcx>>, | |
557 | ) { | |
558 | for (constraint, origin) in &self.data.constraints { | |
3c0e092e | 559 | debug!(?constraint, ?origin); |
abe05a73 XL |
560 | match *constraint { |
561 | Constraint::RegSubVar(..) | Constraint::VarSubVar(..) => { | |
562 | // Expansion will ensure that these constraints hold. Ignore. | |
563 | } | |
564 | ||
565 | Constraint::RegSubReg(sub, sup) => { | |
74b04a01 | 566 | if self.sub_concrete_regions(sub, sup) { |
abe05a73 XL |
567 | continue; |
568 | } | |
569 | ||
570 | debug!( | |
3c0e092e | 571 | "region error at {:?}: \ |
abe05a73 | 572 | cannot verify that {:?} <= {:?}", |
0bf4aa26 | 573 | origin, sub, sup |
abe05a73 XL |
574 | ); |
575 | ||
576 | errors.push(RegionResolutionError::ConcreteFailure( | |
577 | (*origin).clone(), | |
578 | sub, | |
579 | sup, | |
580 | )); | |
581 | } | |
582 | ||
583 | Constraint::VarSubReg(a_vid, b_region) => { | |
584 | let a_data = var_data.value_mut(a_vid); | |
585 | debug!("contraction: {:?} == {:?}, {:?}", a_vid, a_data, b_region); | |
586 | ||
5e7ed085 FG |
587 | let VarValue::Value(a_region) = *a_data else { |
588 | continue; | |
abe05a73 XL |
589 | }; |
590 | ||
591 | // Do not report these errors immediately: | |
592 | // instead, set the variable value to error and | |
593 | // collect them later. | |
74b04a01 | 594 | if !self.sub_concrete_regions(a_region, b_region) { |
abe05a73 | 595 | debug!( |
3c0e092e | 596 | "region error at {:?}: \ |
f9f354fc | 597 | cannot verify that {:?}={:?} <= {:?}", |
0bf4aa26 | 598 | origin, a_vid, a_region, b_region |
abe05a73 XL |
599 | ); |
600 | *a_data = VarValue::ErrorValue; | |
601 | } | |
602 | } | |
603 | } | |
604 | } | |
605 | ||
606 | for verify in &self.data.verifys { | |
607 | debug!("collect_errors: verify={:?}", verify); | |
0bf4aa26 | 608 | let sub = var_data.normalize(self.tcx(), verify.region); |
abe05a73 | 609 | |
0bf4aa26 | 610 | let verify_kind_ty = verify.kind.to_ty(self.tcx()); |
136023e0 | 611 | let verify_kind_ty = var_data.normalize(self.tcx(), verify_kind_ty); |
0bf4aa26 | 612 | if self.bound_is_met(&verify.bound, var_data, verify_kind_ty, sub) { |
abe05a73 XL |
613 | continue; |
614 | } | |
615 | ||
616 | debug!( | |
617 | "collect_errors: region error at {:?}: \ | |
618 | cannot verify that {:?} <= {:?}", | |
0bf4aa26 | 619 | verify.origin, verify.region, verify.bound |
abe05a73 XL |
620 | ); |
621 | ||
622 | errors.push(RegionResolutionError::GenericBoundFailure( | |
623 | verify.origin.clone(), | |
dfeec247 | 624 | verify.kind, |
abe05a73 XL |
625 | sub, |
626 | )); | |
627 | } | |
628 | } | |
629 | ||
630 | /// Go over the variables that were declared to be error variables | |
631 | /// and create a `RegionResolutionError` for each of them. | |
632 | fn collect_var_errors( | |
633 | &self, | |
634 | var_data: &LexicalRegionResolutions<'tcx>, | |
abe05a73 XL |
635 | errors: &mut Vec<RegionResolutionError<'tcx>>, |
636 | ) { | |
f9f354fc | 637 | debug!("collect_var_errors, var_data = {:#?}", var_data.values); |
abe05a73 XL |
638 | |
639 | // This is the best way that I have found to suppress | |
640 | // duplicate and related errors. Basically we keep a set of | |
641 | // flags for every node. Whenever an error occurs, we will | |
642 | // walk some portion of the graph looking to find pairs of | |
643 | // conflicting regions to report to the user. As we walk, we | |
644 | // trip the flags from false to true, and if we find that | |
645 | // we've already reported an error involving any particular | |
9c376795 | 646 | // node we just stop and don't report the current error. The |
abe05a73 XL |
647 | // idea is to report errors that derive from independent |
648 | // regions of the graph, but not those that derive from | |
649 | // overlapping locations. | |
dc9dc135 | 650 | let mut dup_vec = IndexVec::from_elem_n(None, self.num_vars()); |
abe05a73 | 651 | |
49aad941 FG |
652 | // Only construct the graph when necessary, because it's moderately |
653 | // expensive. | |
654 | let mut graph = None; | |
655 | ||
abe05a73 XL |
656 | for (node_vid, value) in var_data.values.iter_enumerated() { |
657 | match *value { | |
f2b60f7d | 658 | VarValue::Empty(_) | VarValue::Value(_) => { /* Inference successful */ } |
abe05a73 | 659 | VarValue::ErrorValue => { |
dc9dc135 XL |
660 | // Inference impossible: this value contains |
661 | // inconsistent constraints. | |
662 | // | |
663 | // I think that in this case we should report an | |
664 | // error now -- unlike the case above, we can't | |
665 | // wait to see whether the user needs the result | |
666 | // of this variable. The reason is that the mere | |
667 | // existence of this variable implies that the | |
668 | // region graph is inconsistent, whether or not it | |
669 | // is used. | |
670 | // | |
671 | // For example, we may have created a region | |
672 | // variable that is the GLB of two other regions | |
673 | // which do not have a GLB. Even if that variable | |
674 | // is not used, it implies that those two regions | |
675 | // *should* have a GLB. | |
676 | // | |
677 | // At least I think this is true. It may be that | |
678 | // the mere existence of a conflict in a region | |
679 | // variable that is not used is not a problem, so | |
680 | // if this rule starts to create problems we'll | |
681 | // have to revisit this portion of the code and | |
682 | // think hard about it. =) -- nikomatsakis | |
a2a8927a XL |
683 | |
684 | // Obtain the spans for all the places that can | |
685 | // influence the constraints on this value for | |
686 | // richer diagnostics in `static_impl_trait`. | |
9c376795 | 687 | |
49aad941 FG |
688 | let g = graph.get_or_insert_with(|| self.construct_graph()); |
689 | self.collect_error_for_expanding_node(g, &mut dup_vec, node_vid, errors); | |
abe05a73 XL |
690 | } |
691 | } | |
692 | } | |
693 | } | |
694 | ||
695 | fn construct_graph(&self) -> RegionGraph<'tcx> { | |
696 | let num_vars = self.num_vars(); | |
697 | ||
8faf50e0 | 698 | let mut graph = Graph::new(); |
abe05a73 XL |
699 | |
700 | for _ in 0..num_vars { | |
701 | graph.add_node(()); | |
702 | } | |
703 | ||
704 | // Issue #30438: two distinct dummy nodes, one for incoming | |
705 | // edges (dummy_source) and another for outgoing edges | |
706 | // (dummy_sink). In `dummy -> a -> b -> dummy`, using one | |
707 | // dummy node leads one to think (erroneously) there exists a | |
708 | // path from `b` to `a`. Two dummy nodes sidesteps the issue. | |
709 | let dummy_source = graph.add_node(()); | |
710 | let dummy_sink = graph.add_node(()); | |
711 | ||
74b04a01 | 712 | for constraint in self.data.constraints.keys() { |
abe05a73 XL |
713 | match *constraint { |
714 | Constraint::VarSubVar(a_id, b_id) => { | |
715 | graph.add_edge( | |
ff7c6d11 XL |
716 | NodeIndex(a_id.index() as usize), |
717 | NodeIndex(b_id.index() as usize), | |
abe05a73 XL |
718 | *constraint, |
719 | ); | |
720 | } | |
721 | Constraint::RegSubVar(_, b_id) => { | |
ff7c6d11 | 722 | graph.add_edge(dummy_source, NodeIndex(b_id.index() as usize), *constraint); |
abe05a73 XL |
723 | } |
724 | Constraint::VarSubReg(a_id, _) => { | |
ff7c6d11 | 725 | graph.add_edge(NodeIndex(a_id.index() as usize), dummy_sink, *constraint); |
abe05a73 XL |
726 | } |
727 | Constraint::RegSubReg(..) => { | |
728 | // this would be an edge from `dummy_source` to | |
729 | // `dummy_sink`; just ignore it. | |
730 | } | |
731 | } | |
732 | } | |
733 | ||
ba9703b0 | 734 | graph |
abe05a73 XL |
735 | } |
736 | ||
737 | fn collect_error_for_expanding_node( | |
738 | &self, | |
739 | graph: &RegionGraph<'tcx>, | |
353b0b11 | 740 | dup_vec: &mut IndexSlice<RegionVid, Option<RegionVid>>, |
abe05a73 XL |
741 | node_idx: RegionVid, |
742 | errors: &mut Vec<RegionResolutionError<'tcx>>, | |
743 | ) { | |
744 | // Errors in expanding nodes result from a lower-bound that is | |
745 | // not contained by an upper-bound. | |
f9f354fc XL |
746 | let (mut lower_bounds, lower_vid_bounds, lower_dup) = |
747 | self.collect_bounding_regions(graph, node_idx, INCOMING, Some(dup_vec)); | |
748 | let (mut upper_bounds, _, upper_dup) = | |
749 | self.collect_bounding_regions(graph, node_idx, OUTGOING, Some(dup_vec)); | |
abe05a73 XL |
750 | |
751 | if lower_dup || upper_dup { | |
752 | return; | |
753 | } | |
754 | ||
755 | // We place free regions first because we are special casing | |
756 | // SubSupConflict(ReFree, ReFree) when reporting error, and so | |
757 | // the user will more likely get a specific suggestion. | |
0bf4aa26 | 758 | fn region_order_key(x: &RegionAndOrigin<'_>) -> u8 { |
abe05a73 XL |
759 | match *x.region { |
760 | ReEarlyBound(_) => 0, | |
761 | ReFree(_) => 1, | |
762 | _ => 2, | |
763 | } | |
764 | } | |
765 | lower_bounds.sort_by_key(region_order_key); | |
766 | upper_bounds.sort_by_key(region_order_key); | |
767 | ||
0731742a XL |
768 | let node_universe = self.var_infos[node_idx].universe; |
769 | ||
abe05a73 | 770 | for lower_bound in &lower_bounds { |
5099ac24 | 771 | let effective_lower_bound = if let ty::RePlaceholder(p) = *lower_bound.region { |
0731742a | 772 | if node_universe.cannot_name(p.universe) { |
48663c56 | 773 | self.tcx().lifetimes.re_static |
0731742a XL |
774 | } else { |
775 | lower_bound.region | |
776 | } | |
777 | } else { | |
778 | lower_bound.region | |
779 | }; | |
780 | ||
abe05a73 | 781 | for upper_bound in &upper_bounds { |
74b04a01 | 782 | if !self.sub_concrete_regions(effective_lower_bound, upper_bound.region) { |
dfeec247 | 783 | let origin = self.var_infos[node_idx].origin; |
abe05a73 XL |
784 | debug!( |
785 | "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \ | |
786 | sup: {:?}", | |
0bf4aa26 | 787 | origin, node_idx, lower_bound.region, upper_bound.region |
abe05a73 | 788 | ); |
a2a8927a | 789 | |
abe05a73 | 790 | errors.push(RegionResolutionError::SubSupConflict( |
0731742a | 791 | node_idx, |
abe05a73 XL |
792 | origin, |
793 | lower_bound.origin.clone(), | |
794 | lower_bound.region, | |
795 | upper_bound.origin.clone(), | |
796 | upper_bound.region, | |
9c376795 | 797 | vec![], |
abe05a73 XL |
798 | )); |
799 | return; | |
800 | } | |
801 | } | |
802 | } | |
803 | ||
74b04a01 XL |
804 | // If we have a scenario like `exists<'a> { forall<'b> { 'b: |
805 | // 'a } }`, we wind up without any lower-bound -- all we have | |
806 | // are placeholders as upper bounds, but the universe of the | |
f9f354fc XL |
807 | // variable `'a`, or some variable that `'a` has to outlive, doesn't |
808 | // permit those placeholders. | |
487cf647 FG |
809 | // |
810 | // We only iterate to find the min, which means it doesn't cause reproducibility issues | |
811 | #[allow(rustc::potential_query_instability)] | |
f9f354fc XL |
812 | let min_universe = lower_vid_bounds |
813 | .into_iter() | |
814 | .map(|vid| self.var_infos[vid].universe) | |
815 | .min() | |
816 | .expect("lower_vid_bounds should at least include `node_idx`"); | |
817 | ||
74b04a01 | 818 | for upper_bound in &upper_bounds { |
5099ac24 | 819 | if let ty::RePlaceholder(p) = *upper_bound.region { |
f9f354fc | 820 | if min_universe.cannot_name(p.universe) { |
74b04a01 XL |
821 | let origin = self.var_infos[node_idx].origin; |
822 | errors.push(RegionResolutionError::UpperBoundUniverseConflict( | |
823 | node_idx, | |
824 | origin, | |
f9f354fc | 825 | min_universe, |
74b04a01 XL |
826 | upper_bound.origin.clone(), |
827 | upper_bound.region, | |
828 | )); | |
829 | return; | |
830 | } | |
831 | } | |
832 | } | |
833 | ||
416331ca XL |
834 | // Errors in earlier passes can yield error variables without |
835 | // resolution errors here; delay ICE in favor of those errors. | |
836 | self.tcx().sess.delay_span_bug( | |
83c7162d | 837 | self.var_infos[node_idx].origin.span(), |
49aad941 | 838 | format!( |
dfeec247 XL |
839 | "collect_error_for_expanding_node() could not find \ |
840 | error for var {:?} in universe {:?}, lower_bounds={:#?}, \ | |
841 | upper_bounds={:#?}", | |
842 | node_idx, node_universe, lower_bounds, upper_bounds | |
843 | ), | |
844 | ); | |
abe05a73 XL |
845 | } |
846 | ||
f9f354fc XL |
847 | /// Collects all regions that "bound" the variable `orig_node_idx` in the |
848 | /// given direction. | |
849 | /// | |
850 | /// If `dup_vec` is `Some` it's used to track duplicates between successive | |
851 | /// calls of this function. | |
852 | /// | |
853 | /// The return tuple fields are: | |
854 | /// - a list of all concrete regions bounding the given region. | |
855 | /// - the set of all region variables bounding the given region. | |
856 | /// - a `bool` that's true if the returned region variables overlap with | |
857 | /// those returned by a previous call for another region. | |
858 | fn collect_bounding_regions( | |
abe05a73 XL |
859 | &self, |
860 | graph: &RegionGraph<'tcx>, | |
861 | orig_node_idx: RegionVid, | |
862 | dir: Direction, | |
353b0b11 | 863 | mut dup_vec: Option<&mut IndexSlice<RegionVid, Option<RegionVid>>>, |
f9f354fc | 864 | ) -> (Vec<RegionAndOrigin<'tcx>>, FxHashSet<RegionVid>, bool) { |
abe05a73 XL |
865 | struct WalkState<'tcx> { |
866 | set: FxHashSet<RegionVid>, | |
867 | stack: Vec<RegionVid>, | |
868 | result: Vec<RegionAndOrigin<'tcx>>, | |
869 | dup_found: bool, | |
870 | } | |
871 | let mut state = WalkState { | |
0bf4aa26 | 872 | set: Default::default(), |
abe05a73 XL |
873 | stack: vec![orig_node_idx], |
874 | result: Vec::new(), | |
875 | dup_found: false, | |
876 | }; | |
877 | state.set.insert(orig_node_idx); | |
878 | ||
879 | // to start off the process, walk the source node in the | |
880 | // direction specified | |
881 | process_edges(&self.data, &mut state, graph, orig_node_idx, dir); | |
882 | ||
f9f354fc | 883 | while let Some(node_idx) = state.stack.pop() { |
abe05a73 | 884 | // check whether we've visited this node on some previous walk |
dc9dc135 XL |
885 | if let Some(dup_vec) = &mut dup_vec { |
886 | if dup_vec[node_idx].is_none() { | |
887 | dup_vec[node_idx] = Some(orig_node_idx); | |
888 | } else if dup_vec[node_idx] != Some(orig_node_idx) { | |
889 | state.dup_found = true; | |
890 | } | |
abe05a73 | 891 | |
dc9dc135 XL |
892 | debug!( |
893 | "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})", | |
894 | orig_node_idx, node_idx | |
895 | ); | |
896 | } | |
abe05a73 XL |
897 | |
898 | process_edges(&self.data, &mut state, graph, node_idx, dir); | |
899 | } | |
900 | ||
f9f354fc XL |
901 | let WalkState { result, dup_found, set, .. } = state; |
902 | return (result, set, dup_found); | |
abe05a73 XL |
903 | |
904 | fn process_edges<'tcx>( | |
905 | this: &RegionConstraintData<'tcx>, | |
906 | state: &mut WalkState<'tcx>, | |
907 | graph: &RegionGraph<'tcx>, | |
908 | source_vid: RegionVid, | |
909 | dir: Direction, | |
910 | ) { | |
911 | debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir); | |
912 | ||
ff7c6d11 | 913 | let source_node_index = NodeIndex(source_vid.index() as usize); |
abe05a73 XL |
914 | for (_, edge) in graph.adjacent_edges(source_node_index, dir) { |
915 | match edge.data { | |
916 | Constraint::VarSubVar(from_vid, to_vid) => { | |
dc9dc135 | 917 | let opp_vid = if from_vid == source_vid { to_vid } else { from_vid }; |
abe05a73 XL |
918 | if state.set.insert(opp_vid) { |
919 | state.stack.push(opp_vid); | |
920 | } | |
921 | } | |
922 | ||
923 | Constraint::RegSubVar(region, _) | Constraint::VarSubReg(_, region) => { | |
924 | state.result.push(RegionAndOrigin { | |
925 | region, | |
926 | origin: this.constraints.get(&edge.data).unwrap().clone(), | |
927 | }); | |
928 | } | |
929 | ||
930 | Constraint::RegSubReg(..) => panic!( | |
931 | "cannot reach reg-sub-reg edge in region inference \ | |
932 | post-processing" | |
933 | ), | |
934 | } | |
935 | } | |
936 | } | |
937 | } | |
938 | ||
abe05a73 XL |
939 | fn bound_is_met( |
940 | &self, | |
941 | bound: &VerifyBound<'tcx>, | |
942 | var_values: &LexicalRegionResolutions<'tcx>, | |
0bf4aa26 | 943 | generic_ty: Ty<'tcx>, |
abe05a73 XL |
944 | min: ty::Region<'tcx>, |
945 | ) -> bool { | |
946 | match bound { | |
923072b8 FG |
947 | VerifyBound::IfEq(verify_if_eq_b) => { |
948 | let verify_if_eq_b = var_values.normalize(self.region_rels.tcx, *verify_if_eq_b); | |
949 | match test_type_match::extract_verify_if_eq( | |
950 | self.tcx(), | |
951 | self.param_env, | |
952 | &verify_if_eq_b, | |
953 | generic_ty, | |
954 | ) { | |
955 | Some(r) => { | |
956 | self.bound_is_met(&VerifyBound::OutlivedBy(r), var_values, generic_ty, min) | |
957 | } | |
958 | ||
959 | None => false, | |
960 | } | |
0bf4aa26 | 961 | } |
abe05a73 | 962 | |
dc9dc135 | 963 | VerifyBound::OutlivedBy(r) => { |
f2b60f7d FG |
964 | let a = match *min { |
965 | ty::ReVar(rid) => var_values.values[rid], | |
966 | _ => VarValue::Value(min), | |
967 | }; | |
968 | let b = match **r { | |
969 | ty::ReVar(rid) => var_values.values[rid], | |
970 | _ => VarValue::Value(*r), | |
971 | }; | |
972 | self.sub_region_values(a, b) | |
74b04a01 XL |
973 | } |
974 | ||
f2b60f7d FG |
975 | VerifyBound::IsEmpty => match *min { |
976 | ty::ReVar(rid) => match var_values.values[rid] { | |
977 | VarValue::ErrorValue => false, | |
978 | VarValue::Empty(_) => true, | |
979 | VarValue::Value(_) => false, | |
980 | }, | |
981 | _ => false, | |
982 | }, | |
abe05a73 | 983 | |
dc9dc135 XL |
984 | VerifyBound::AnyBound(bs) => { |
985 | bs.iter().any(|b| self.bound_is_met(b, var_values, generic_ty, min)) | |
986 | } | |
abe05a73 | 987 | |
dc9dc135 XL |
988 | VerifyBound::AllBounds(bs) => { |
989 | bs.iter().all(|b| self.bound_is_met(b, var_values, generic_ty, min)) | |
990 | } | |
abe05a73 XL |
991 | } |
992 | } | |
993 | } | |
994 | ||
995 | impl<'tcx> fmt::Debug for RegionAndOrigin<'tcx> { | |
0bf4aa26 | 996 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
997 | write!(f, "RegionAndOrigin({:?},{:?})", self.region, self.origin) |
998 | } | |
999 | } | |
1000 | ||
abe05a73 | 1001 | impl<'tcx> LexicalRegionResolutions<'tcx> { |
dc9dc135 | 1002 | fn normalize<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T |
0bf4aa26 | 1003 | where |
9ffffee4 | 1004 | T: TypeFoldable<TyCtxt<'tcx>>, |
0bf4aa26 | 1005 | { |
064997fb | 1006 | tcx.fold_regions(value, |r, _db| self.resolve_region(tcx, r)) |
abe05a73 XL |
1007 | } |
1008 | ||
1009 | fn value(&self, rid: RegionVid) -> &VarValue<'tcx> { | |
1010 | &self.values[rid] | |
1011 | } | |
1012 | ||
1013 | fn value_mut(&mut self, rid: RegionVid) -> &mut VarValue<'tcx> { | |
1014 | &mut self.values[rid] | |
1015 | } | |
1016 | ||
064997fb FG |
1017 | pub(crate) fn resolve_region( |
1018 | &self, | |
1019 | tcx: TyCtxt<'tcx>, | |
1020 | r: ty::Region<'tcx>, | |
1021 | ) -> ty::Region<'tcx> { | |
1022 | let result = match *r { | |
1023 | ty::ReVar(rid) => match self.values[rid] { | |
f2b60f7d | 1024 | VarValue::Empty(_) => r, |
064997fb FG |
1025 | VarValue::Value(r) => r, |
1026 | VarValue::ErrorValue => tcx.lifetimes.re_static, | |
1027 | }, | |
1028 | _ => r, | |
abe05a73 | 1029 | }; |
064997fb | 1030 | debug!("resolve_region({:?}) = {:?}", r, result); |
abe05a73 XL |
1031 | result |
1032 | } | |
1033 | } |