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