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