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
>>,
50 pub(crate) error_region
: ty
::Region
<'tcx
>,
53 #[derive(Copy, Clone, Debug)]
54 pub(crate) enum VarValue
<'tcx
> {
59 #[derive(Clone, Debug)]
60 pub enum RegionResolutionError
<'tcx
> {
61 /// `ConcreteFailure(o, a, b)`:
63 /// `o` requires that `a <= b`, but this does not hold
64 ConcreteFailure(SubregionOrigin
<'tcx
>, Region
<'tcx
>, Region
<'tcx
>),
66 /// `GenericBoundFailure(p, s, a)
68 /// The parameter/associated-type `p` must be known to outlive the lifetime
69 /// `a` (but none of the known bounds are sufficient).
70 GenericBoundFailure(SubregionOrigin
<'tcx
>, GenericKind
<'tcx
>, Region
<'tcx
>),
72 /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
74 /// Could not infer a value for `v` (which has origin `v_origin`)
75 /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
76 /// `sub_r <= sup_r` does not hold.
80 SubregionOrigin
<'tcx
>,
82 SubregionOrigin
<'tcx
>,
84 Vec
<Span
>, // All the influences on a given value that didn't meet its constraints.
87 /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
88 /// cannot name the placeholder `'b`.
89 UpperBoundUniverseConflict(
92 ty
::UniverseIndex
, // the universe index of the region variable
93 SubregionOrigin
<'tcx
>, // cause of the constraint
94 Region
<'tcx
>, // the placeholder `'b`
98 struct RegionAndOrigin
<'tcx
> {
100 origin
: SubregionOrigin
<'tcx
>,
103 type RegionGraph
<'tcx
> = Graph
<(), Constraint
<'tcx
>>;
105 struct LexicalResolver
<'cx
, 'tcx
> {
106 param_env
: ty
::ParamEnv
<'tcx
>,
107 region_rels
: &'cx RegionRelations
<'cx
, 'tcx
>,
109 data
: RegionConstraintData
<'tcx
>,
112 impl<'cx
, 'tcx
> LexicalResolver
<'cx
, 'tcx
> {
113 fn tcx(&self) -> TyCtxt
<'tcx
> {
117 fn infer_variable_values(
119 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
120 ) -> LexicalRegionResolutions
<'tcx
> {
121 let mut var_data
= self.construct_var_data(self.tcx());
123 // Dorky hack to cause `dump_constraints` to only get called
124 // if debug mode is enabled:
126 "----() End constraint listing (context={:?}) {:?}---",
127 self.region_rels
.context
,
128 self.dump_constraints(self.region_rels
)
131 let graph
= self.construct_graph();
132 self.expand_givens(&graph
);
133 self.expansion(&mut var_data
);
134 self.collect_errors(&mut var_data
, errors
);
135 self.collect_var_errors(&var_data
, &graph
, errors
);
139 fn num_vars(&self) -> usize {
143 /// Initially, the value for all variables is set to `'empty`, the
144 /// empty region. The `expansion` phase will grow this larger.
145 fn construct_var_data(&self, tcx
: TyCtxt
<'tcx
>) -> LexicalRegionResolutions
<'tcx
> {
146 LexicalRegionResolutions
{
147 error_region
: tcx
.lifetimes
.re_static
,
148 values
: IndexVec
::from_fn_n(
150 let vid_universe
= self.var_infos
[vid
].universe
;
151 let re_empty
= tcx
.mk_region(ty
::ReEmpty(vid_universe
));
152 VarValue
::Value(re_empty
)
159 fn dump_constraints(&self, free_regions
: &RegionRelations
<'_
, 'tcx
>) {
160 debug
!("----() Start constraint listing (context={:?}) ()----", free_regions
.context
);
161 for (idx
, (constraint
, _
)) in self.data
.constraints
.iter().enumerate() {
162 debug
!("Constraint {} => {:?}", idx
, constraint
);
166 fn expand_givens(&mut self, graph
: &RegionGraph
<'_
>) {
167 // Givens are a kind of horrible hack to account for
168 // constraints like 'c <= '0 that are known to hold due to
169 // closure signatures (see the comment above on the `givens`
170 // field). They should go away. But until they do, the role
171 // of this fn is to account for the transitive nature:
177 let seeds
: Vec
<_
> = self.data
.givens
.iter().cloned().collect();
178 for (r
, vid
) in seeds
{
179 // While all things transitively reachable in the graph
180 // from the variable (`'0` in the example above).
181 let seed_index
= NodeIndex(vid
.index() as usize);
182 for succ_index
in graph
.depth_traverse(seed_index
, OUTGOING
) {
183 let succ_index
= succ_index
.0;
185 // The first N nodes correspond to the region
186 // variables. Other nodes correspond to constant
188 if succ_index
< self.num_vars() {
189 let succ_vid
= RegionVid
::new(succ_index
);
192 self.data
.givens
.insert((r
, succ_vid
));
198 fn expansion(&self, var_values
: &mut LexicalRegionResolutions
<'tcx
>) {
199 let mut constraints
= IndexVec
::from_elem_n(Vec
::new(), var_values
.values
.len());
200 let mut changes
= Vec
::new();
201 for constraint
in self.data
.constraints
.keys() {
202 let (a_vid
, a_region
, b_vid
, b_data
) = match *constraint
{
203 Constraint
::RegSubVar(a_region
, b_vid
) => {
204 let b_data
= var_values
.value_mut(b_vid
);
205 (None
, a_region
, b_vid
, b_data
)
207 Constraint
::VarSubVar(a_vid
, b_vid
) => match *var_values
.value(a_vid
) {
208 VarValue
::ErrorValue
=> continue,
209 VarValue
::Value(a_region
) => {
210 let b_data
= var_values
.value_mut(b_vid
);
211 (Some(a_vid
), a_region
, b_vid
, b_data
)
214 Constraint
::RegSubReg(..) | Constraint
::VarSubReg(..) => {
215 // These constraints are checked after expansion
216 // is done, in `collect_errors`.
220 if self.expand_node(a_region
, b_vid
, b_data
) {
223 if let Some(a_vid
) = a_vid
{
225 VarValue
::Value(Region(Interned(ReStatic
, _
))) | VarValue
::ErrorValue
=> (),
227 constraints
[a_vid
].push((a_vid
, b_vid
));
228 constraints
[b_vid
].push((a_vid
, b_vid
));
234 while let Some(vid
) = changes
.pop() {
235 constraints
[vid
].retain(|&(a_vid
, b_vid
)| {
236 let VarValue
::Value(a_region
) = *var_values
.value(a_vid
) else {
239 let b_data
= var_values
.value_mut(b_vid
);
240 if self.expand_node(a_region
, b_vid
, b_data
) {
245 VarValue
::Value(Region(Interned(ReStatic
, _
))) | VarValue
::ErrorValue
253 a_region
: Region
<'tcx
>,
255 b_data
: &mut VarValue
<'tcx
>,
257 debug
!("expand_node({:?}, {:?} == {:?})", a_region
, b_vid
, b_data
);
260 // Check if this relationship is implied by a given.
261 ty
::ReEarlyBound(_
) | ty
::ReFree(_
) => {
262 if self.data
.givens
.contains(&(a_region
, b_vid
)) {
272 VarValue
::Value(cur_region
) => {
273 // This is a specialized version of the `lub_concrete_regions`
274 // check below for a common case, here purely as an
276 let b_universe
= self.var_infos
[b_vid
].universe
;
277 if let ReEmpty(a_universe
) = *a_region
&& a_universe
== b_universe
{
281 let mut lub
= self.lub_concrete_regions(a_region
, cur_region
);
282 if lub
== cur_region
{
286 // Watch out for `'b: !1` relationships, where the
287 // universe of `'b` can't name the placeholder `!1`. In
288 // that case, we have to grow `'b` to be `'static` for the
289 // relationship to hold. This is obviously a kind of sub-optimal
290 // choice -- in the future, when we incorporate a knowledge
291 // of the parameter environment, we might be able to find a
292 // tighter bound than `'static`.
294 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
295 if let ty
::RePlaceholder(p
) = *lub
&& b_universe
.cannot_name(p
.universe
) {
296 lub
= self.tcx().lifetimes
.re_static
;
299 debug
!("Expanding value of {:?} from {:?} to {:?}", b_vid
, cur_region
, lub
);
301 *b_data
= VarValue
::Value(lub
);
305 VarValue
::ErrorValue
=> false,
309 /// True if `a <= b`, but not defined over inference variables.
310 #[instrument(level = "trace", skip(self))]
311 fn sub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> bool
{
312 let tcx
= self.tcx();
313 let sub_free_regions
= |r1
, r2
| self.region_rels
.free_regions
.sub_free_regions(tcx
, r1
, r2
);
315 // Check for the case where we know that `'b: 'static` -- in that case,
316 // `a <= b` for all `a`.
317 let b_free_or_static
= self.region_rels
.free_regions
.is_free_or_static(b
);
318 if b_free_or_static
&& sub_free_regions(tcx
.lifetimes
.re_static
, b
) {
322 // If both `a` and `b` are free, consult the declared
323 // relationships. Note that this can be more precise than the
324 // `lub` relationship defined below, since sometimes the "lub"
325 // is actually the `postdom_upper_bound` (see
326 // `TransitiveRelation` for more details).
327 let a_free_or_static
= self.region_rels
.free_regions
.is_free_or_static(a
);
328 if a_free_or_static
&& b_free_or_static
{
329 return sub_free_regions(a
, b
);
332 // For other cases, leverage the LUB code to find the LUB and
333 // check if it is equal to `b`.
334 self.lub_concrete_regions(a
, b
) == b
337 /// Returns the least-upper-bound of `a` and `b`; i.e., the
338 /// smallest region `c` such that `a <= c` and `b <= c`.
340 /// Neither `a` nor `b` may be an inference variable (hence the
341 /// term "concrete regions").
342 #[instrument(level = "trace", skip(self))]
343 fn lub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> Region
<'tcx
> {
344 let r
= match (*a
, *b
) {
345 (ReLateBound(..), _
) | (_
, ReLateBound(..)) | (ReErased
, _
) | (_
, ReErased
) => {
346 bug
!("cannot relate region: LUB({:?}, {:?})", a
, b
);
349 (ReVar(v_id
), _
) | (_
, ReVar(v_id
)) => {
351 self.var_infos
[v_id
].origin
.span(),
352 "lub_concrete_regions invoked with non-concrete \
353 regions: {:?}, {:?}",
359 (ReStatic
, _
) | (_
, ReStatic
) => {
360 // nothing lives longer than `'static`
361 self.tcx().lifetimes
.re_static
364 (ReEmpty(_
), ReEarlyBound(_
) | ReFree(_
)) => {
365 // All empty regions are less than early-bound, free,
366 // and scope regions.
370 (ReEarlyBound(_
) | ReFree(_
), ReEmpty(_
)) => {
371 // All empty regions are less than early-bound, free,
372 // and scope regions.
376 (ReEmpty(a_ui
), ReEmpty(b_ui
)) => {
377 // Empty regions are ordered according to the universe
378 // they are associated with.
379 let ui
= a_ui
.min(b_ui
);
380 self.tcx().mk_region(ReEmpty(ui
))
383 (ReEmpty(empty_ui
), RePlaceholder(placeholder
))
384 | (RePlaceholder(placeholder
), ReEmpty(empty_ui
)) => {
385 // If this empty region is from a universe that can
386 // name the placeholder, then the placeholder is
387 // larger; otherwise, the only ancestor is `'static`.
388 if empty_ui
.can_name(placeholder
.universe
) {
389 self.tcx().mk_region(RePlaceholder(placeholder
))
391 self.tcx().lifetimes
.re_static
395 (ReEarlyBound(_
) | ReFree(_
), ReEarlyBound(_
) | ReFree(_
)) => {
396 self.region_rels
.lub_free_regions(a
, b
)
399 // For these types, we cannot define any additional
401 (RePlaceholder(..), _
) | (_
, RePlaceholder(..)) => {
405 self.tcx().lifetimes
.re_static
410 debug
!("lub_concrete_regions({:?}, {:?}) = {:?}", a
, b
, r
);
415 /// After expansion is complete, go and check upper bounds (i.e.,
416 /// cases where the region cannot grow larger than a fixed point)
417 /// and check that they are satisfied.
418 #[instrument(skip(self, var_data, errors))]
421 var_data
: &mut LexicalRegionResolutions
<'tcx
>,
422 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
424 for (constraint
, origin
) in &self.data
.constraints
{
425 debug
!(?constraint
, ?origin
);
427 Constraint
::RegSubVar(..) | Constraint
::VarSubVar(..) => {
428 // Expansion will ensure that these constraints hold. Ignore.
431 Constraint
::RegSubReg(sub
, sup
) => {
432 if self.sub_concrete_regions(sub
, sup
) {
437 "region error at {:?}: \
438 cannot verify that {:?} <= {:?}",
442 errors
.push(RegionResolutionError
::ConcreteFailure(
449 Constraint
::VarSubReg(a_vid
, b_region
) => {
450 let a_data
= var_data
.value_mut(a_vid
);
451 debug
!("contraction: {:?} == {:?}, {:?}", a_vid
, a_data
, b_region
);
453 let VarValue
::Value(a_region
) = *a_data
else {
457 // Do not report these errors immediately:
458 // instead, set the variable value to error and
459 // collect them later.
460 if !self.sub_concrete_regions(a_region
, b_region
) {
462 "region error at {:?}: \
463 cannot verify that {:?}={:?} <= {:?}",
464 origin
, a_vid
, a_region
, b_region
466 *a_data
= VarValue
::ErrorValue
;
472 for verify
in &self.data
.verifys
{
473 debug
!("collect_errors: verify={:?}", verify
);
474 let sub
= var_data
.normalize(self.tcx(), verify
.region
);
476 let verify_kind_ty
= verify
.kind
.to_ty(self.tcx());
477 let verify_kind_ty
= var_data
.normalize(self.tcx(), verify_kind_ty
);
478 if self.bound_is_met(&verify
.bound
, var_data
, verify_kind_ty
, sub
) {
483 "collect_errors: region error at {:?}: \
484 cannot verify that {:?} <= {:?}",
485 verify
.origin
, verify
.region
, verify
.bound
488 errors
.push(RegionResolutionError
::GenericBoundFailure(
489 verify
.origin
.clone(),
496 /// Go over the variables that were declared to be error variables
497 /// and create a `RegionResolutionError` for each of them.
498 fn collect_var_errors(
500 var_data
: &LexicalRegionResolutions
<'tcx
>,
501 graph
: &RegionGraph
<'tcx
>,
502 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
504 debug
!("collect_var_errors, var_data = {:#?}", var_data
.values
);
506 // This is the best way that I have found to suppress
507 // duplicate and related errors. Basically we keep a set of
508 // flags for every node. Whenever an error occurs, we will
509 // walk some portion of the graph looking to find pairs of
510 // conflicting regions to report to the user. As we walk, we
511 // trip the flags from false to true, and if we find that
512 // we've already reported an error involving any particular
513 // node we just stop and don't report the current error. The
514 // idea is to report errors that derive from independent
515 // regions of the graph, but not those that derive from
516 // overlapping locations.
517 let mut dup_vec
= IndexVec
::from_elem_n(None
, self.num_vars());
519 for (node_vid
, value
) in var_data
.values
.iter_enumerated() {
521 VarValue
::Value(_
) => { /* Inference successful */ }
522 VarValue
::ErrorValue
=> {
523 // Inference impossible: this value contains
524 // inconsistent constraints.
526 // I think that in this case we should report an
527 // error now -- unlike the case above, we can't
528 // wait to see whether the user needs the result
529 // of this variable. The reason is that the mere
530 // existence of this variable implies that the
531 // region graph is inconsistent, whether or not it
534 // For example, we may have created a region
535 // variable that is the GLB of two other regions
536 // which do not have a GLB. Even if that variable
537 // is not used, it implies that those two regions
538 // *should* have a GLB.
540 // At least I think this is true. It may be that
541 // the mere existence of a conflict in a region
542 // variable that is not used is not a problem, so
543 // if this rule starts to create problems we'll
544 // have to revisit this portion of the code and
545 // think hard about it. =) -- nikomatsakis
547 // Obtain the spans for all the places that can
548 // influence the constraints on this value for
549 // richer diagnostics in `static_impl_trait`.
550 let influences
: Vec
<Span
> = self
554 .filter_map(|(constraint
, origin
)| match (constraint
, origin
) {
556 Constraint
::VarSubVar(_
, sup
),
557 SubregionOrigin
::DataBorrowed(_
, sp
),
558 ) if sup
== &node_vid
=> Some(*sp
),
563 self.collect_error_for_expanding_node(
575 fn construct_graph(&self) -> RegionGraph
<'tcx
> {
576 let num_vars
= self.num_vars();
578 let mut graph
= Graph
::new();
580 for _
in 0..num_vars
{
584 // Issue #30438: two distinct dummy nodes, one for incoming
585 // edges (dummy_source) and another for outgoing edges
586 // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
587 // dummy node leads one to think (erroneously) there exists a
588 // path from `b` to `a`. Two dummy nodes sidesteps the issue.
589 let dummy_source
= graph
.add_node(());
590 let dummy_sink
= graph
.add_node(());
592 for constraint
in self.data
.constraints
.keys() {
594 Constraint
::VarSubVar(a_id
, b_id
) => {
596 NodeIndex(a_id
.index() as usize),
597 NodeIndex(b_id
.index() as usize),
601 Constraint
::RegSubVar(_
, b_id
) => {
602 graph
.add_edge(dummy_source
, NodeIndex(b_id
.index() as usize), *constraint
);
604 Constraint
::VarSubReg(a_id
, _
) => {
605 graph
.add_edge(NodeIndex(a_id
.index() as usize), dummy_sink
, *constraint
);
607 Constraint
::RegSubReg(..) => {
608 // this would be an edge from `dummy_source` to
609 // `dummy_sink`; just ignore it.
617 fn collect_error_for_expanding_node(
619 graph
: &RegionGraph
<'tcx
>,
620 dup_vec
: &mut IndexVec
<RegionVid
, Option
<RegionVid
>>,
622 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
623 influences
: Vec
<Span
>,
625 // Errors in expanding nodes result from a lower-bound that is
626 // not contained by an upper-bound.
627 let (mut lower_bounds
, lower_vid_bounds
, lower_dup
) =
628 self.collect_bounding_regions(graph
, node_idx
, INCOMING
, Some(dup_vec
));
629 let (mut upper_bounds
, _
, upper_dup
) =
630 self.collect_bounding_regions(graph
, node_idx
, OUTGOING
, Some(dup_vec
));
632 if lower_dup
|| upper_dup
{
636 // We place free regions first because we are special casing
637 // SubSupConflict(ReFree, ReFree) when reporting error, and so
638 // the user will more likely get a specific suggestion.
639 fn region_order_key(x
: &RegionAndOrigin
<'_
>) -> u8 {
641 ReEarlyBound(_
) => 0,
646 lower_bounds
.sort_by_key(region_order_key
);
647 upper_bounds
.sort_by_key(region_order_key
);
649 let node_universe
= self.var_infos
[node_idx
].universe
;
651 for lower_bound
in &lower_bounds
{
652 let effective_lower_bound
= if let ty
::RePlaceholder(p
) = *lower_bound
.region
{
653 if node_universe
.cannot_name(p
.universe
) {
654 self.tcx().lifetimes
.re_static
662 for upper_bound
in &upper_bounds
{
663 if !self.sub_concrete_regions(effective_lower_bound
, upper_bound
.region
) {
664 let origin
= self.var_infos
[node_idx
].origin
;
666 "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
668 origin
, node_idx
, lower_bound
.region
, upper_bound
.region
671 errors
.push(RegionResolutionError
::SubSupConflict(
674 lower_bound
.origin
.clone(),
676 upper_bound
.origin
.clone(),
685 // If we have a scenario like `exists<'a> { forall<'b> { 'b:
686 // 'a } }`, we wind up without any lower-bound -- all we have
687 // are placeholders as upper bounds, but the universe of the
688 // variable `'a`, or some variable that `'a` has to outlive, doesn't
689 // permit those placeholders.
690 let min_universe
= lower_vid_bounds
692 .map(|vid
| self.var_infos
[vid
].universe
)
694 .expect("lower_vid_bounds should at least include `node_idx`");
696 for upper_bound
in &upper_bounds
{
697 if let ty
::RePlaceholder(p
) = *upper_bound
.region
{
698 if min_universe
.cannot_name(p
.universe
) {
699 let origin
= self.var_infos
[node_idx
].origin
;
700 errors
.push(RegionResolutionError
::UpperBoundUniverseConflict(
704 upper_bound
.origin
.clone(),
712 // Errors in earlier passes can yield error variables without
713 // resolution errors here; delay ICE in favor of those errors.
714 self.tcx().sess
.delay_span_bug(
715 self.var_infos
[node_idx
].origin
.span(),
717 "collect_error_for_expanding_node() could not find \
718 error for var {:?} in universe {:?}, lower_bounds={:#?}, \
720 node_idx
, node_universe
, lower_bounds
, upper_bounds
725 /// Collects all regions that "bound" the variable `orig_node_idx` in the
728 /// If `dup_vec` is `Some` it's used to track duplicates between successive
729 /// calls of this function.
731 /// The return tuple fields are:
732 /// - a list of all concrete regions bounding the given region.
733 /// - the set of all region variables bounding the given region.
734 /// - a `bool` that's true if the returned region variables overlap with
735 /// those returned by a previous call for another region.
736 fn collect_bounding_regions(
738 graph
: &RegionGraph
<'tcx
>,
739 orig_node_idx
: RegionVid
,
741 mut dup_vec
: Option
<&mut IndexVec
<RegionVid
, Option
<RegionVid
>>>,
742 ) -> (Vec
<RegionAndOrigin
<'tcx
>>, FxHashSet
<RegionVid
>, bool
) {
743 struct WalkState
<'tcx
> {
744 set
: FxHashSet
<RegionVid
>,
745 stack
: Vec
<RegionVid
>,
746 result
: Vec
<RegionAndOrigin
<'tcx
>>,
749 let mut state
= WalkState
{
750 set
: Default
::default(),
751 stack
: vec
![orig_node_idx
],
755 state
.set
.insert(orig_node_idx
);
757 // to start off the process, walk the source node in the
758 // direction specified
759 process_edges(&self.data
, &mut state
, graph
, orig_node_idx
, dir
);
761 while let Some(node_idx
) = state
.stack
.pop() {
762 // check whether we've visited this node on some previous walk
763 if let Some(dup_vec
) = &mut dup_vec
{
764 if dup_vec
[node_idx
].is_none() {
765 dup_vec
[node_idx
] = Some(orig_node_idx
);
766 } else if dup_vec
[node_idx
] != Some(orig_node_idx
) {
767 state
.dup_found
= true;
771 "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
772 orig_node_idx
, node_idx
776 process_edges(&self.data
, &mut state
, graph
, node_idx
, dir
);
779 let WalkState { result, dup_found, set, .. }
= state
;
780 return (result
, set
, dup_found
);
782 fn process_edges
<'tcx
>(
783 this
: &RegionConstraintData
<'tcx
>,
784 state
: &mut WalkState
<'tcx
>,
785 graph
: &RegionGraph
<'tcx
>,
786 source_vid
: RegionVid
,
789 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
791 let source_node_index
= NodeIndex(source_vid
.index() as usize);
792 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
794 Constraint
::VarSubVar(from_vid
, to_vid
) => {
795 let opp_vid
= if from_vid
== source_vid { to_vid }
else { from_vid }
;
796 if state
.set
.insert(opp_vid
) {
797 state
.stack
.push(opp_vid
);
801 Constraint
::RegSubVar(region
, _
) | Constraint
::VarSubReg(_
, region
) => {
802 state
.result
.push(RegionAndOrigin
{
804 origin
: this
.constraints
.get(&edge
.data
).unwrap().clone(),
808 Constraint
::RegSubReg(..) => panic
!(
809 "cannot reach reg-sub-reg edge in region inference \
819 bound
: &VerifyBound
<'tcx
>,
820 var_values
: &LexicalRegionResolutions
<'tcx
>,
821 generic_ty
: Ty
<'tcx
>,
822 min
: ty
::Region
<'tcx
>,
825 VerifyBound
::IfEq(verify_if_eq_b
) => {
826 let verify_if_eq_b
= var_values
.normalize(self.region_rels
.tcx
, *verify_if_eq_b
);
827 match test_type_match
::extract_verify_if_eq(
834 self.bound_is_met(&VerifyBound
::OutlivedBy(r
), var_values
, generic_ty
, min
)
841 VerifyBound
::OutlivedBy(r
) => {
842 self.sub_concrete_regions(min
, var_values
.normalize(self.tcx(), *r
))
845 VerifyBound
::IsEmpty
=> {
846 matches
!(*min
, ty
::ReEmpty(_
))
849 VerifyBound
::AnyBound(bs
) => {
850 bs
.iter().any(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
853 VerifyBound
::AllBounds(bs
) => {
854 bs
.iter().all(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
860 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
861 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
862 write
!(f
, "RegionAndOrigin({:?},{:?})", self.region
, self.origin
)
866 impl<'tcx
> LexicalRegionResolutions
<'tcx
> {
867 fn normalize
<T
>(&self, tcx
: TyCtxt
<'tcx
>, value
: T
) -> T
869 T
: TypeFoldable
<'tcx
>,
871 tcx
.fold_regions(value
, &mut false, |r
, _db
| match *r
{
872 ty
::ReVar(rid
) => self.resolve_var(rid
),
877 fn value(&self, rid
: RegionVid
) -> &VarValue
<'tcx
> {
881 fn value_mut(&mut self, rid
: RegionVid
) -> &mut VarValue
<'tcx
> {
882 &mut self.values
[rid
]
885 pub fn resolve_var(&self, rid
: RegionVid
) -> ty
::Region
<'tcx
> {
886 let result
= match self.values
[rid
] {
887 VarValue
::Value(r
) => r
,
888 VarValue
::ErrorValue
=> self.error_region
,
890 debug
!("resolve_var({:?}) = {:?}", rid
, result
);