1 //! Lexical region resolution.
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
;
8 use crate::infer
::RegionRelations
;
9 use crate::infer
::RegionVariableOrigin
;
10 use crate::infer
::SubregionOrigin
;
11 use rustc_data_structures
::fx
::FxHashSet
;
12 use rustc_data_structures
::graph
::implementation
::{
13 Direction
, Graph
, NodeIndex
, INCOMING
, OUTGOING
,
15 use rustc_data_structures
::intern
::Interned
;
16 use rustc_index
::vec
::{Idx, IndexVec}
;
17 use rustc_middle
::ty
::fold
::TypeFoldable
;
18 use rustc_middle
::ty
::{self, Ty, TyCtxt}
;
19 use rustc_middle
::ty
::{ReEarlyBound, ReEmpty, ReErased, ReFree, ReStatic}
;
20 use rustc_middle
::ty
::{ReLateBound, RePlaceholder, ReVar}
;
21 use rustc_middle
::ty
::{Region, RegionVid}
;
25 use super::outlives
::test_type_match
;
27 /// This function performs lexical region resolution given a complete
28 /// set of constraints and variable origins. It performs a fixed-point
29 /// iteration to find region values which satisfy all constraints,
30 /// assuming such values can be found. It returns the final values of
31 /// all the variables as well as a set of errors that must be reported.
32 #[instrument(level = "debug", skip(region_rels, var_infos, data))]
33 pub(crate) fn resolve
<'tcx
>(
34 param_env
: ty
::ParamEnv
<'tcx
>,
35 region_rels
: &RegionRelations
<'_
, 'tcx
>,
37 data
: RegionConstraintData
<'tcx
>,
38 ) -> (LexicalRegionResolutions
<'tcx
>, Vec
<RegionResolutionError
<'tcx
>>) {
39 let mut errors
= vec
![];
40 let mut resolver
= LexicalResolver { param_env, region_rels, var_infos, data }
;
41 let values
= resolver
.infer_variable_values(&mut errors
);
45 /// Contains the result of lexical region resolution. Offers methods
46 /// to lookup up the final value of a region variable.
48 pub struct LexicalRegionResolutions
<'tcx
> {
49 pub(crate) values
: IndexVec
<RegionVid
, VarValue
<'tcx
>>,
52 #[derive(Copy, Clone, Debug)]
53 pub(crate) enum VarValue
<'tcx
> {
58 #[derive(Clone, Debug)]
59 pub enum RegionResolutionError
<'tcx
> {
60 /// `ConcreteFailure(o, a, b)`:
62 /// `o` requires that `a <= b`, but this does not hold
63 ConcreteFailure(SubregionOrigin
<'tcx
>, Region
<'tcx
>, Region
<'tcx
>),
65 /// `GenericBoundFailure(p, s, a)
67 /// The parameter/associated-type `p` must be known to outlive the lifetime
68 /// `a` (but none of the known bounds are sufficient).
69 GenericBoundFailure(SubregionOrigin
<'tcx
>, GenericKind
<'tcx
>, Region
<'tcx
>),
71 /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
73 /// Could not infer a value for `v` (which has origin `v_origin`)
74 /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
75 /// `sub_r <= sup_r` does not hold.
79 SubregionOrigin
<'tcx
>,
81 SubregionOrigin
<'tcx
>,
83 Vec
<Span
>, // All the influences on a given value that didn't meet its constraints.
86 /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
87 /// cannot name the placeholder `'b`.
88 UpperBoundUniverseConflict(
91 ty
::UniverseIndex
, // the universe index of the region variable
92 SubregionOrigin
<'tcx
>, // cause of the constraint
93 Region
<'tcx
>, // the placeholder `'b`
97 struct RegionAndOrigin
<'tcx
> {
99 origin
: SubregionOrigin
<'tcx
>,
102 type RegionGraph
<'tcx
> = Graph
<(), Constraint
<'tcx
>>;
104 struct LexicalResolver
<'cx
, 'tcx
> {
105 param_env
: ty
::ParamEnv
<'tcx
>,
106 region_rels
: &'cx RegionRelations
<'cx
, 'tcx
>,
108 data
: RegionConstraintData
<'tcx
>,
111 impl<'cx
, 'tcx
> LexicalResolver
<'cx
, 'tcx
> {
112 fn tcx(&self) -> TyCtxt
<'tcx
> {
116 fn infer_variable_values(
118 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
119 ) -> LexicalRegionResolutions
<'tcx
> {
120 let mut var_data
= self.construct_var_data(self.tcx());
122 if cfg
!(debug_assertions
) {
123 self.dump_constraints();
126 let graph
= self.construct_graph();
127 self.expand_givens(&graph
);
128 self.expansion(&mut var_data
);
129 self.collect_errors(&mut var_data
, errors
);
130 self.collect_var_errors(&var_data
, &graph
, errors
);
134 fn num_vars(&self) -> usize {
138 /// Initially, the value for all variables is set to `'empty`, the
139 /// empty region. The `expansion` phase will grow this larger.
140 fn construct_var_data(&self, tcx
: TyCtxt
<'tcx
>) -> LexicalRegionResolutions
<'tcx
> {
141 LexicalRegionResolutions
{
142 values
: IndexVec
::from_fn_n(
144 let vid_universe
= self.var_infos
[vid
].universe
;
145 let re_empty
= tcx
.mk_region(ty
::ReEmpty(vid_universe
));
146 VarValue
::Value(re_empty
)
153 #[instrument(level = "debug", skip(self))]
154 fn dump_constraints(&self) {
155 for (idx
, (constraint
, _
)) in self.data
.constraints
.iter().enumerate() {
156 debug
!("Constraint {} => {:?}", idx
, constraint
);
160 fn expand_givens(&mut self, graph
: &RegionGraph
<'_
>) {
161 // Givens are a kind of horrible hack to account for
162 // constraints like 'c <= '0 that are known to hold due to
163 // closure signatures (see the comment above on the `givens`
164 // field). They should go away. But until they do, the role
165 // of this fn is to account for the transitive nature:
171 let seeds
: Vec
<_
> = self.data
.givens
.iter().cloned().collect();
172 for (r
, vid
) in seeds
{
173 // While all things transitively reachable in the graph
174 // from the variable (`'0` in the example above).
175 let seed_index
= NodeIndex(vid
.index() as usize);
176 for succ_index
in graph
.depth_traverse(seed_index
, OUTGOING
) {
177 let succ_index
= succ_index
.0;
179 // The first N nodes correspond to the region
180 // variables. Other nodes correspond to constant
182 if succ_index
< self.num_vars() {
183 let succ_vid
= RegionVid
::new(succ_index
);
186 self.data
.givens
.insert((r
, succ_vid
));
192 fn expansion(&self, var_values
: &mut LexicalRegionResolutions
<'tcx
>) {
193 let mut constraints
= IndexVec
::from_elem_n(Vec
::new(), var_values
.values
.len());
194 let mut changes
= Vec
::new();
195 for constraint
in self.data
.constraints
.keys() {
196 let (a_vid
, a_region
, b_vid
, b_data
) = match *constraint
{
197 Constraint
::RegSubVar(a_region
, b_vid
) => {
198 let b_data
= var_values
.value_mut(b_vid
);
199 (None
, a_region
, b_vid
, b_data
)
201 Constraint
::VarSubVar(a_vid
, b_vid
) => match *var_values
.value(a_vid
) {
202 VarValue
::ErrorValue
=> continue,
203 VarValue
::Value(a_region
) => {
204 let b_data
= var_values
.value_mut(b_vid
);
205 (Some(a_vid
), a_region
, b_vid
, b_data
)
208 Constraint
::RegSubReg(..) | Constraint
::VarSubReg(..) => {
209 // These constraints are checked after expansion
210 // is done, in `collect_errors`.
214 if self.expand_node(a_region
, b_vid
, b_data
) {
217 if let Some(a_vid
) = a_vid
{
219 VarValue
::Value(Region(Interned(ReStatic
, _
))) | VarValue
::ErrorValue
=> (),
221 constraints
[a_vid
].push((a_vid
, b_vid
));
222 constraints
[b_vid
].push((a_vid
, b_vid
));
228 while let Some(vid
) = changes
.pop() {
229 constraints
[vid
].retain(|&(a_vid
, b_vid
)| {
230 let VarValue
::Value(a_region
) = *var_values
.value(a_vid
) else {
233 let b_data
= var_values
.value_mut(b_vid
);
234 if self.expand_node(a_region
, b_vid
, b_data
) {
239 VarValue
::Value(Region(Interned(ReStatic
, _
))) | VarValue
::ErrorValue
247 a_region
: Region
<'tcx
>,
249 b_data
: &mut VarValue
<'tcx
>,
251 debug
!("expand_node({:?}, {:?} == {:?})", a_region
, b_vid
, b_data
);
254 // Check if this relationship is implied by a given.
255 ty
::ReEarlyBound(_
) | ty
::ReFree(_
) => {
256 if self.data
.givens
.contains(&(a_region
, b_vid
)) {
266 VarValue
::Value(cur_region
) => {
267 // This is a specialized version of the `lub_concrete_regions`
268 // check below for a common case, here purely as an
270 let b_universe
= self.var_infos
[b_vid
].universe
;
271 if let ReEmpty(a_universe
) = *a_region
&& a_universe
== b_universe
{
275 let mut lub
= self.lub_concrete_regions(a_region
, cur_region
);
276 if lub
== cur_region
{
280 // Watch out for `'b: !1` relationships, where the
281 // universe of `'b` can't name the placeholder `!1`. In
282 // that case, we have to grow `'b` to be `'static` for the
283 // relationship to hold. This is obviously a kind of sub-optimal
284 // choice -- in the future, when we incorporate a knowledge
285 // of the parameter environment, we might be able to find a
286 // tighter bound than `'static`.
288 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
289 if let ty
::RePlaceholder(p
) = *lub
&& b_universe
.cannot_name(p
.universe
) {
290 lub
= self.tcx().lifetimes
.re_static
;
293 debug
!("Expanding value of {:?} from {:?} to {:?}", b_vid
, cur_region
, lub
);
295 *b_data
= VarValue
::Value(lub
);
299 VarValue
::ErrorValue
=> false,
303 /// True if `a <= b`, but not defined over inference variables.
304 #[instrument(level = "trace", skip(self))]
305 fn sub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> bool
{
306 let tcx
= self.tcx();
307 let sub_free_regions
= |r1
, r2
| self.region_rels
.free_regions
.sub_free_regions(tcx
, r1
, r2
);
309 // Check for the case where we know that `'b: 'static` -- in that case,
310 // `a <= b` for all `a`.
311 let b_free_or_static
= b
.is_free_or_static();
312 if b_free_or_static
&& sub_free_regions(tcx
.lifetimes
.re_static
, b
) {
316 // If both `a` and `b` are free, consult the declared
317 // relationships. Note that this can be more precise than the
318 // `lub` relationship defined below, since sometimes the "lub"
319 // is actually the `postdom_upper_bound` (see
320 // `TransitiveRelation` for more details).
321 let a_free_or_static
= a
.is_free_or_static();
322 if a_free_or_static
&& b_free_or_static
{
323 return sub_free_regions(a
, b
);
326 // For other cases, leverage the LUB code to find the LUB and
327 // check if it is equal to `b`.
328 self.lub_concrete_regions(a
, b
) == b
331 /// Returns the least-upper-bound of `a` and `b`; i.e., the
332 /// smallest region `c` such that `a <= c` and `b <= c`.
334 /// Neither `a` nor `b` may be an inference variable (hence the
335 /// term "concrete regions").
336 #[instrument(level = "trace", skip(self))]
337 fn lub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> Region
<'tcx
> {
338 let r
= match (*a
, *b
) {
339 (ReLateBound(..), _
) | (_
, ReLateBound(..)) | (ReErased
, _
) | (_
, ReErased
) => {
340 bug
!("cannot relate region: LUB({:?}, {:?})", a
, b
);
343 (ReVar(v_id
), _
) | (_
, ReVar(v_id
)) => {
345 self.var_infos
[v_id
].origin
.span(),
346 "lub_concrete_regions invoked with non-concrete \
347 regions: {:?}, {:?}",
353 (ReStatic
, _
) | (_
, ReStatic
) => {
354 // nothing lives longer than `'static`
355 self.tcx().lifetimes
.re_static
358 (ReEmpty(_
), ReEarlyBound(_
) | ReFree(_
)) => {
359 // All empty regions are less than early-bound, free,
360 // and scope regions.
364 (ReEarlyBound(_
) | ReFree(_
), ReEmpty(_
)) => {
365 // All empty regions are less than early-bound, free,
366 // and scope regions.
370 (ReEmpty(a_ui
), ReEmpty(b_ui
)) => {
371 // Empty regions are ordered according to the universe
372 // they are associated with.
373 let ui
= a_ui
.min(b_ui
);
374 self.tcx().mk_region(ReEmpty(ui
))
377 (ReEmpty(empty_ui
), RePlaceholder(placeholder
))
378 | (RePlaceholder(placeholder
), ReEmpty(empty_ui
)) => {
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 if empty_ui
.can_name(placeholder
.universe
) {
383 self.tcx().mk_region(RePlaceholder(placeholder
))
385 self.tcx().lifetimes
.re_static
389 (ReEarlyBound(_
) | ReFree(_
), ReEarlyBound(_
) | ReFree(_
)) => {
390 self.region_rels
.lub_free_regions(a
, b
)
393 // For these types, we cannot define any additional
395 (RePlaceholder(..), _
) | (_
, RePlaceholder(..)) => {
399 self.tcx().lifetimes
.re_static
404 debug
!("lub_concrete_regions({:?}, {:?}) = {:?}", a
, b
, r
);
409 /// After expansion is complete, go and check upper bounds (i.e.,
410 /// cases where the region cannot grow larger than a fixed point)
411 /// and check that they are satisfied.
412 #[instrument(skip(self, var_data, errors))]
415 var_data
: &mut LexicalRegionResolutions
<'tcx
>,
416 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
418 for (constraint
, origin
) in &self.data
.constraints
{
419 debug
!(?constraint
, ?origin
);
421 Constraint
::RegSubVar(..) | Constraint
::VarSubVar(..) => {
422 // Expansion will ensure that these constraints hold. Ignore.
425 Constraint
::RegSubReg(sub
, sup
) => {
426 if self.sub_concrete_regions(sub
, sup
) {
431 "region error at {:?}: \
432 cannot verify that {:?} <= {:?}",
436 errors
.push(RegionResolutionError
::ConcreteFailure(
443 Constraint
::VarSubReg(a_vid
, b_region
) => {
444 let a_data
= var_data
.value_mut(a_vid
);
445 debug
!("contraction: {:?} == {:?}, {:?}", a_vid
, a_data
, b_region
);
447 let VarValue
::Value(a_region
) = *a_data
else {
451 // Do not report these errors immediately:
452 // instead, set the variable value to error and
453 // collect them later.
454 if !self.sub_concrete_regions(a_region
, b_region
) {
456 "region error at {:?}: \
457 cannot verify that {:?}={:?} <= {:?}",
458 origin
, a_vid
, a_region
, b_region
460 *a_data
= VarValue
::ErrorValue
;
466 for verify
in &self.data
.verifys
{
467 debug
!("collect_errors: verify={:?}", verify
);
468 let sub
= var_data
.normalize(self.tcx(), verify
.region
);
470 let verify_kind_ty
= verify
.kind
.to_ty(self.tcx());
471 let verify_kind_ty
= var_data
.normalize(self.tcx(), verify_kind_ty
);
472 if self.bound_is_met(&verify
.bound
, var_data
, verify_kind_ty
, sub
) {
477 "collect_errors: region error at {:?}: \
478 cannot verify that {:?} <= {:?}",
479 verify
.origin
, verify
.region
, verify
.bound
482 errors
.push(RegionResolutionError
::GenericBoundFailure(
483 verify
.origin
.clone(),
490 /// Go over the variables that were declared to be error variables
491 /// and create a `RegionResolutionError` for each of them.
492 fn collect_var_errors(
494 var_data
: &LexicalRegionResolutions
<'tcx
>,
495 graph
: &RegionGraph
<'tcx
>,
496 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
498 debug
!("collect_var_errors, var_data = {:#?}", var_data
.values
);
500 // This is the best way that I have found to suppress
501 // duplicate and related errors. Basically we keep a set of
502 // flags for every node. Whenever an error occurs, we will
503 // walk some portion of the graph looking to find pairs of
504 // conflicting regions to report to the user. As we walk, we
505 // trip the flags from false to true, and if we find that
506 // we've already reported an error involving any particular
507 // node we just stop and don't report the current error. The
508 // idea is to report errors that derive from independent
509 // regions of the graph, but not those that derive from
510 // overlapping locations.
511 let mut dup_vec
= IndexVec
::from_elem_n(None
, self.num_vars());
513 for (node_vid
, value
) in var_data
.values
.iter_enumerated() {
515 VarValue
::Value(_
) => { /* Inference successful */ }
516 VarValue
::ErrorValue
=> {
517 // Inference impossible: this value contains
518 // inconsistent constraints.
520 // I think that in this case we should report an
521 // error now -- unlike the case above, we can't
522 // wait to see whether the user needs the result
523 // of this variable. The reason is that the mere
524 // existence of this variable implies that the
525 // region graph is inconsistent, whether or not it
528 // For example, we may have created a region
529 // variable that is the GLB of two other regions
530 // which do not have a GLB. Even if that variable
531 // is not used, it implies that those two regions
532 // *should* have a GLB.
534 // At least I think this is true. It may be that
535 // the mere existence of a conflict in a region
536 // variable that is not used is not a problem, so
537 // if this rule starts to create problems we'll
538 // have to revisit this portion of the code and
539 // think hard about it. =) -- nikomatsakis
541 // Obtain the spans for all the places that can
542 // influence the constraints on this value for
543 // richer diagnostics in `static_impl_trait`.
544 let influences
: Vec
<Span
> = self
548 .filter_map(|(constraint
, origin
)| match (constraint
, origin
) {
550 Constraint
::VarSubVar(_
, sup
),
551 SubregionOrigin
::DataBorrowed(_
, sp
),
552 ) if sup
== &node_vid
=> Some(*sp
),
557 self.collect_error_for_expanding_node(
569 fn construct_graph(&self) -> RegionGraph
<'tcx
> {
570 let num_vars
= self.num_vars();
572 let mut graph
= Graph
::new();
574 for _
in 0..num_vars
{
578 // Issue #30438: two distinct dummy nodes, one for incoming
579 // edges (dummy_source) and another for outgoing edges
580 // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
581 // dummy node leads one to think (erroneously) there exists a
582 // path from `b` to `a`. Two dummy nodes sidesteps the issue.
583 let dummy_source
= graph
.add_node(());
584 let dummy_sink
= graph
.add_node(());
586 for constraint
in self.data
.constraints
.keys() {
588 Constraint
::VarSubVar(a_id
, b_id
) => {
590 NodeIndex(a_id
.index() as usize),
591 NodeIndex(b_id
.index() as usize),
595 Constraint
::RegSubVar(_
, b_id
) => {
596 graph
.add_edge(dummy_source
, NodeIndex(b_id
.index() as usize), *constraint
);
598 Constraint
::VarSubReg(a_id
, _
) => {
599 graph
.add_edge(NodeIndex(a_id
.index() as usize), dummy_sink
, *constraint
);
601 Constraint
::RegSubReg(..) => {
602 // this would be an edge from `dummy_source` to
603 // `dummy_sink`; just ignore it.
611 fn collect_error_for_expanding_node(
613 graph
: &RegionGraph
<'tcx
>,
614 dup_vec
: &mut IndexVec
<RegionVid
, Option
<RegionVid
>>,
616 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
617 influences
: Vec
<Span
>,
619 // Errors in expanding nodes result from a lower-bound that is
620 // not contained by an upper-bound.
621 let (mut lower_bounds
, lower_vid_bounds
, lower_dup
) =
622 self.collect_bounding_regions(graph
, node_idx
, INCOMING
, Some(dup_vec
));
623 let (mut upper_bounds
, _
, upper_dup
) =
624 self.collect_bounding_regions(graph
, node_idx
, OUTGOING
, Some(dup_vec
));
626 if lower_dup
|| upper_dup
{
630 // We place free regions first because we are special casing
631 // SubSupConflict(ReFree, ReFree) when reporting error, and so
632 // the user will more likely get a specific suggestion.
633 fn region_order_key(x
: &RegionAndOrigin
<'_
>) -> u8 {
635 ReEarlyBound(_
) => 0,
640 lower_bounds
.sort_by_key(region_order_key
);
641 upper_bounds
.sort_by_key(region_order_key
);
643 let node_universe
= self.var_infos
[node_idx
].universe
;
645 for lower_bound
in &lower_bounds
{
646 let effective_lower_bound
= if let ty
::RePlaceholder(p
) = *lower_bound
.region
{
647 if node_universe
.cannot_name(p
.universe
) {
648 self.tcx().lifetimes
.re_static
656 for upper_bound
in &upper_bounds
{
657 if !self.sub_concrete_regions(effective_lower_bound
, upper_bound
.region
) {
658 let origin
= self.var_infos
[node_idx
].origin
;
660 "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
662 origin
, node_idx
, lower_bound
.region
, upper_bound
.region
665 errors
.push(RegionResolutionError
::SubSupConflict(
668 lower_bound
.origin
.clone(),
670 upper_bound
.origin
.clone(),
679 // If we have a scenario like `exists<'a> { forall<'b> { 'b:
680 // 'a } }`, we wind up without any lower-bound -- all we have
681 // are placeholders as upper bounds, but the universe of the
682 // variable `'a`, or some variable that `'a` has to outlive, doesn't
683 // permit those placeholders.
684 let min_universe
= lower_vid_bounds
686 .map(|vid
| self.var_infos
[vid
].universe
)
688 .expect("lower_vid_bounds should at least include `node_idx`");
690 for upper_bound
in &upper_bounds
{
691 if let ty
::RePlaceholder(p
) = *upper_bound
.region
{
692 if min_universe
.cannot_name(p
.universe
) {
693 let origin
= self.var_infos
[node_idx
].origin
;
694 errors
.push(RegionResolutionError
::UpperBoundUniverseConflict(
698 upper_bound
.origin
.clone(),
706 // Errors in earlier passes can yield error variables without
707 // resolution errors here; delay ICE in favor of those errors.
708 self.tcx().sess
.delay_span_bug(
709 self.var_infos
[node_idx
].origin
.span(),
711 "collect_error_for_expanding_node() could not find \
712 error for var {:?} in universe {:?}, lower_bounds={:#?}, \
714 node_idx
, node_universe
, lower_bounds
, upper_bounds
719 /// Collects all regions that "bound" the variable `orig_node_idx` in the
722 /// If `dup_vec` is `Some` it's used to track duplicates between successive
723 /// calls of this function.
725 /// The return tuple fields are:
726 /// - a list of all concrete regions bounding the given region.
727 /// - the set of all region variables bounding the given region.
728 /// - a `bool` that's true if the returned region variables overlap with
729 /// those returned by a previous call for another region.
730 fn collect_bounding_regions(
732 graph
: &RegionGraph
<'tcx
>,
733 orig_node_idx
: RegionVid
,
735 mut dup_vec
: Option
<&mut IndexVec
<RegionVid
, Option
<RegionVid
>>>,
736 ) -> (Vec
<RegionAndOrigin
<'tcx
>>, FxHashSet
<RegionVid
>, bool
) {
737 struct WalkState
<'tcx
> {
738 set
: FxHashSet
<RegionVid
>,
739 stack
: Vec
<RegionVid
>,
740 result
: Vec
<RegionAndOrigin
<'tcx
>>,
743 let mut state
= WalkState
{
744 set
: Default
::default(),
745 stack
: vec
![orig_node_idx
],
749 state
.set
.insert(orig_node_idx
);
751 // to start off the process, walk the source node in the
752 // direction specified
753 process_edges(&self.data
, &mut state
, graph
, orig_node_idx
, dir
);
755 while let Some(node_idx
) = state
.stack
.pop() {
756 // check whether we've visited this node on some previous walk
757 if let Some(dup_vec
) = &mut dup_vec
{
758 if dup_vec
[node_idx
].is_none() {
759 dup_vec
[node_idx
] = Some(orig_node_idx
);
760 } else if dup_vec
[node_idx
] != Some(orig_node_idx
) {
761 state
.dup_found
= true;
765 "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
766 orig_node_idx
, node_idx
770 process_edges(&self.data
, &mut state
, graph
, node_idx
, dir
);
773 let WalkState { result, dup_found, set, .. }
= state
;
774 return (result
, set
, dup_found
);
776 fn process_edges
<'tcx
>(
777 this
: &RegionConstraintData
<'tcx
>,
778 state
: &mut WalkState
<'tcx
>,
779 graph
: &RegionGraph
<'tcx
>,
780 source_vid
: RegionVid
,
783 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
785 let source_node_index
= NodeIndex(source_vid
.index() as usize);
786 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
788 Constraint
::VarSubVar(from_vid
, to_vid
) => {
789 let opp_vid
= if from_vid
== source_vid { to_vid }
else { from_vid }
;
790 if state
.set
.insert(opp_vid
) {
791 state
.stack
.push(opp_vid
);
795 Constraint
::RegSubVar(region
, _
) | Constraint
::VarSubReg(_
, region
) => {
796 state
.result
.push(RegionAndOrigin
{
798 origin
: this
.constraints
.get(&edge
.data
).unwrap().clone(),
802 Constraint
::RegSubReg(..) => panic
!(
803 "cannot reach reg-sub-reg edge in region inference \
813 bound
: &VerifyBound
<'tcx
>,
814 var_values
: &LexicalRegionResolutions
<'tcx
>,
815 generic_ty
: Ty
<'tcx
>,
816 min
: ty
::Region
<'tcx
>,
819 VerifyBound
::IfEq(verify_if_eq_b
) => {
820 let verify_if_eq_b
= var_values
.normalize(self.region_rels
.tcx
, *verify_if_eq_b
);
821 match test_type_match
::extract_verify_if_eq(
828 self.bound_is_met(&VerifyBound
::OutlivedBy(r
), var_values
, generic_ty
, min
)
835 VerifyBound
::OutlivedBy(r
) => {
836 self.sub_concrete_regions(min
, var_values
.normalize(self.tcx(), *r
))
839 VerifyBound
::IsEmpty
=> {
840 matches
!(*min
, ty
::ReEmpty(_
))
843 VerifyBound
::AnyBound(bs
) => {
844 bs
.iter().any(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
847 VerifyBound
::AllBounds(bs
) => {
848 bs
.iter().all(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
854 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
855 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
856 write
!(f
, "RegionAndOrigin({:?},{:?})", self.region
, self.origin
)
860 impl<'tcx
> LexicalRegionResolutions
<'tcx
> {
861 fn normalize
<T
>(&self, tcx
: TyCtxt
<'tcx
>, value
: T
) -> T
863 T
: TypeFoldable
<'tcx
>,
865 tcx
.fold_regions(value
, |r
, _db
| self.resolve_region(tcx
, r
))
868 fn value(&self, rid
: RegionVid
) -> &VarValue
<'tcx
> {
872 fn value_mut(&mut self, rid
: RegionVid
) -> &mut VarValue
<'tcx
> {
873 &mut self.values
[rid
]
876 pub(crate) fn resolve_region(
880 ) -> ty
::Region
<'tcx
> {
881 let result
= match *r
{
882 ty
::ReVar(rid
) => match self.values
[rid
] {
883 VarValue
::Value(r
) => r
,
884 VarValue
::ErrorValue
=> tcx
.lifetimes
.re_static
,
888 debug
!("resolve_region({:?}) = {:?}", r
, result
);