1 //! Lexical region resolution.
3 use crate::infer
::region_constraints
::Constraint
;
4 use crate::infer
::region_constraints
::GenericKind
;
5 use crate::infer
::region_constraints
::MemberConstraint
;
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
::RegionRelations
;
10 use crate::infer
::RegionVariableOrigin
;
11 use crate::infer
::RegionckMode
;
12 use crate::infer
::SubregionOrigin
;
13 use rustc_data_structures
::fx
::FxHashSet
;
14 use rustc_data_structures
::graph
::implementation
::{
15 Direction
, Graph
, NodeIndex
, INCOMING
, OUTGOING
,
17 use rustc_index
::vec
::{Idx, IndexVec}
;
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, ReVar}
;
22 use rustc_middle
::ty
::{Region, RegionVid}
;
26 /// This function performs lexical region resolution given a complete
27 /// set of constraints and variable origins. It performs a fixed-point
28 /// iteration to find region values which satisfy all constraints,
29 /// assuming such values can be found. It returns the final values of
30 /// all the variables as well as a set of errors that must be reported.
32 region_rels
: &RegionRelations
<'_
, 'tcx
>,
34 data
: RegionConstraintData
<'tcx
>,
36 ) -> (LexicalRegionResolutions
<'tcx
>, Vec
<RegionResolutionError
<'tcx
>>) {
37 debug
!("RegionConstraintData: resolve_regions()");
38 let mut errors
= vec
![];
39 let mut resolver
= LexicalResolver { region_rels, var_infos, data }
;
41 RegionckMode
::Solve
=> {
42 let values
= resolver
.infer_variable_values(&mut errors
);
45 RegionckMode
::Erase { suppress_errors: false }
=> {
46 // Do real inference to get errors, then erase the results.
47 let mut values
= resolver
.infer_variable_values(&mut errors
);
48 let re_erased
= region_rels
.tcx
.lifetimes
.re_erased
;
50 values
.values
.iter_mut().for_each(|v
| match *v
{
51 VarValue
::Value(ref mut r
) => *r
= re_erased
,
52 VarValue
::ErrorValue
=> {}
56 RegionckMode
::Erase { suppress_errors: true }
=> {
57 // Skip region inference entirely.
58 (resolver
.erased_data(region_rels
.tcx
), Vec
::new())
63 /// Contains the result of lexical region resolution. Offers methods
64 /// to lookup up the final value of a region variable.
65 pub struct LexicalRegionResolutions
<'tcx
> {
66 values
: IndexVec
<RegionVid
, VarValue
<'tcx
>>,
67 error_region
: ty
::Region
<'tcx
>,
70 #[derive(Copy, Clone, Debug)]
76 #[derive(Clone, Debug)]
77 pub enum RegionResolutionError
<'tcx
> {
78 /// `ConcreteFailure(o, a, b)`:
80 /// `o` requires that `a <= b`, but this does not hold
81 ConcreteFailure(SubregionOrigin
<'tcx
>, Region
<'tcx
>, Region
<'tcx
>),
83 /// `GenericBoundFailure(p, s, a)
85 /// The parameter/associated-type `p` must be known to outlive the lifetime
86 /// `a` (but none of the known bounds are sufficient).
87 GenericBoundFailure(SubregionOrigin
<'tcx
>, GenericKind
<'tcx
>, Region
<'tcx
>),
89 /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
91 /// Could not infer a value for `v` (which has origin `v_origin`)
92 /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
93 /// `sub_r <= sup_r` does not hold.
97 SubregionOrigin
<'tcx
>,
99 SubregionOrigin
<'tcx
>,
103 /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
104 /// cannot name the placeholder `'b`.
105 UpperBoundUniverseConflict(
107 RegionVariableOrigin
,
108 ty
::UniverseIndex
, // the universe index of the region variable
109 SubregionOrigin
<'tcx
>, // cause of the constraint
110 Region
<'tcx
>, // the placeholder `'b`
113 /// Indicates a failure of a `MemberConstraint`. These arise during
114 /// impl trait processing explicitly -- basically, the impl trait's hidden type
115 /// included some region that it was not supposed to.
116 MemberConstraintFailure { span: Span, hidden_ty: Ty<'tcx>, member_region: Region<'tcx> }
,
119 struct RegionAndOrigin
<'tcx
> {
120 region
: Region
<'tcx
>,
121 origin
: SubregionOrigin
<'tcx
>,
124 type RegionGraph
<'tcx
> = Graph
<(), Constraint
<'tcx
>>;
126 struct LexicalResolver
<'cx
, 'tcx
> {
127 region_rels
: &'cx RegionRelations
<'cx
, 'tcx
>,
129 data
: RegionConstraintData
<'tcx
>,
132 impl<'cx
, 'tcx
> LexicalResolver
<'cx
, 'tcx
> {
133 fn tcx(&self) -> TyCtxt
<'tcx
> {
137 fn infer_variable_values(
139 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
140 ) -> LexicalRegionResolutions
<'tcx
> {
141 let mut var_data
= self.construct_var_data(self.tcx());
143 // Dorky hack to cause `dump_constraints` to only get called
144 // if debug mode is enabled:
146 "----() End constraint listing (context={:?}) {:?}---",
147 self.region_rels
.context
,
148 self.dump_constraints(self.region_rels
)
151 let graph
= self.construct_graph();
152 self.expand_givens(&graph
);
154 self.expansion(&mut var_data
);
155 if !self.enforce_member_constraints(&graph
, &mut var_data
) {
159 self.collect_errors(&mut var_data
, errors
);
160 self.collect_var_errors(&var_data
, &graph
, errors
);
164 fn num_vars(&self) -> usize {
168 /// Initially, the value for all variables is set to `'empty`, the
169 /// empty region. The `expansion` phase will grow this larger.
170 fn construct_var_data(&self, tcx
: TyCtxt
<'tcx
>) -> LexicalRegionResolutions
<'tcx
> {
171 LexicalRegionResolutions
{
172 error_region
: tcx
.lifetimes
.re_static
,
173 values
: IndexVec
::from_fn_n(
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
)
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
),
197 fn dump_constraints(&self, free_regions
: &RegionRelations
<'_
, 'tcx
>) {
198 debug
!("----() Start constraint listing (context={:?}) ()----", free_regions
.context
);
199 for (idx
, (constraint
, _
)) in self.data
.constraints
.iter().enumerate() {
200 debug
!("Constraint {} => {:?}", idx
, constraint
);
204 fn expand_givens(&mut self, graph
: &RegionGraph
<'_
>) {
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:
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).
219 let seed_index
= NodeIndex(vid
.index() as usize);
220 for succ_index
in graph
.depth_traverse(seed_index
, OUTGOING
) {
221 let succ_index
= succ_index
.0;
223 // The first N nodes correspond to the region
224 // variables. Other nodes correspond to constant
226 if succ_index
< self.num_vars() {
227 let succ_vid
= RegionVid
::new(succ_index
);
230 self.data
.givens
.insert((r
, succ_vid
));
236 /// Enforce all member constraints and return true if anything
237 /// changed. See `enforce_member_constraint` for more details.
238 fn enforce_member_constraints(
240 graph
: &RegionGraph
<'tcx
>,
241 var_values
: &mut LexicalRegionResolutions
<'tcx
>,
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
{
247 any_changed
|= self.enforce_member_constraint(graph
, member_constraint
, var_values
);
252 /// Enforce a constraint like
255 /// 'r member of ['c...]
258 /// We look for all choice regions from the list `'c...` that:
260 /// (a) are greater than the current value of `'r` (which is a lower bound)
264 /// (b) are compatible with the upper bounds of `'r` that we can
265 /// find by traversing the graph.
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(
271 graph
: &RegionGraph
<'tcx
>,
272 member_constraint
: &MemberConstraint
<'tcx
>,
273 var_values
: &mut LexicalRegionResolutions
<'tcx
>,
275 debug
!("enforce_member_constraint(member_constraint={:#?})", member_constraint
);
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
,
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
,
291 // Find all the "upper bounds" -- that is, each region `b` such that
292 // `r0 <= b` must hold.
293 let (member_upper_bounds
, ..) =
294 self.collect_bounding_regions(graph
, member_vid
, OUTGOING
, None
);
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
304 .all(|upper_bound
| self.sub_concrete_regions(option
, upper_bound
.region
))
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() {
312 None
=> return false,
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
;
322 debug
!("enforce_member_constraint: no least choice");
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 ()`.
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
337 let lub
= self.lub_concrete_regions(least_choice
, member_lower_bound
);
339 "enforce_member_constraint: final least choice = {:?}\nlub = {:?}",
342 if lub
!= member_lower_bound
{
343 *var_values
.value_mut(member_vid
) = VarValue
::Value(least_choice
);
350 fn expansion(&self, var_values
: &mut LexicalRegionResolutions
<'tcx
>) {
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
{
355 Constraint
::RegSubVar(a_region
, b_vid
) => {
356 let b_data
= var_values
.value_mut(b_vid
);
357 (None
, a_region
, b_vid
, b_data
)
359 Constraint
::VarSubVar(a_vid
, b_vid
) => match *var_values
.value(a_vid
) {
360 VarValue
::ErrorValue
=> continue,
361 VarValue
::Value(a_region
) => {
362 let b_data
= var_values
.value_mut(b_vid
);
363 (Some(a_vid
), a_region
, b_vid
, b_data
)
366 Constraint
::RegSubReg(..) | Constraint
::VarSubReg(..) => {
367 // These constraints are checked after expansion
368 // is done, in `collect_errors`.
372 if self.expand_node(a_region
, b_vid
, b_data
) {
375 if let Some(a_vid
) = a_vid
{
377 VarValue
::Value(ReStatic
) | VarValue
::ErrorValue
=> (),
379 constraints
[a_vid
].push((a_vid
, b_vid
));
380 constraints
[b_vid
].push((a_vid
, b_vid
));
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
,
392 let b_data
= var_values
.value_mut(b_vid
);
393 if self.expand_node(a_region
, b_vid
, b_data
) {
397 VarValue
::Value(ReStatic
) | VarValue
::ErrorValue
=> false,
406 a_region
: Region
<'tcx
>,
408 b_data
: &mut VarValue
<'tcx
>,
410 debug
!("expand_node({:?}, {:?} == {:?})", a_region
, b_vid
, b_data
);
413 // Check if this relationship is implied by a given.
414 ty
::ReEarlyBound(_
) | ty
::ReFree(_
) => {
415 if self.data
.givens
.contains(&(a_region
, b_vid
)) {
425 VarValue
::Value(cur_region
) => {
426 // This is a specialized version of the `lub_concrete_regions`
427 // check below for a common case, here purely as an
429 let b_universe
= self.var_infos
[b_vid
].universe
;
430 if let ReEmpty(a_universe
) = a_region
{
431 if *a_universe
== b_universe
{
436 let mut lub
= self.lub_concrete_regions(a_region
, cur_region
);
437 if lub
== cur_region
{
441 // Watch out for `'b: !1` relationships, where the
442 // universe of `'b` can't name the placeholder `!1`. In
443 // that case, we have to grow `'b` to be `'static` for the
444 // relationship to hold. This is obviously a kind of sub-optimal
445 // choice -- in the future, when we incorporate a knowledge
446 // of the parameter environment, we might be able to find a
447 // tighter bound than `'static`.
449 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
450 if let ty
::RePlaceholder(p
) = lub
{
451 if b_universe
.cannot_name(p
.universe
) {
452 lub
= self.tcx().lifetimes
.re_static
;
456 debug
!("Expanding value of {:?} from {:?} to {:?}", b_vid
, cur_region
, lub
);
458 *b_data
= VarValue
::Value(lub
);
462 VarValue
::ErrorValue
=> false,
466 /// True if `a <= b`, but not defined over inference variables.
467 fn sub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> bool
{
468 let tcx
= self.tcx();
469 let sub_free_regions
= |r1
, r2
| self.region_rels
.free_regions
.sub_free_regions(tcx
, r1
, r2
);
471 // Check for the case where we know that `'b: 'static` -- in that case,
472 // `a <= b` for all `a`.
473 let b_free_or_static
= self.region_rels
.free_regions
.is_free_or_static(b
);
474 if b_free_or_static
&& sub_free_regions(tcx
.lifetimes
.re_static
, b
) {
478 // If both `a` and `b` are free, consult the declared
479 // relationships. Note that this can be more precise than the
480 // `lub` relationship defined below, since sometimes the "lub"
481 // is actually the `postdom_upper_bound` (see
482 // `TransitiveRelation` for more details).
483 let a_free_or_static
= self.region_rels
.free_regions
.is_free_or_static(a
);
484 if a_free_or_static
&& b_free_or_static
{
485 return sub_free_regions(a
, b
);
488 // For other cases, leverage the LUB code to find the LUB and
489 // check if it is equal to `b`.
490 self.lub_concrete_regions(a
, b
) == b
493 /// Returns the least-upper-bound of `a` and `b`; i.e., the
494 /// smallest region `c` such that `a <= c` and `b <= c`.
496 /// Neither `a` nor `b` may be an inference variable (hence the
497 /// term "concrete regions").
498 fn lub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> Region
<'tcx
> {
499 let r
= match (a
, b
) {
500 (&ReLateBound(..), _
) | (_
, &ReLateBound(..)) | (&ReErased
, _
) | (_
, &ReErased
) => {
501 bug
!("cannot relate region: LUB({:?}, {:?})", a
, b
);
504 (&ReVar(v_id
), _
) | (_
, &ReVar(v_id
)) => {
506 self.var_infos
[v_id
].origin
.span(),
507 "lub_concrete_regions invoked with non-concrete \
508 regions: {:?}, {:?}",
514 (&ReStatic
, _
) | (_
, &ReStatic
) => {
515 // nothing lives longer than `'static`
516 self.tcx().lifetimes
.re_static
519 (&ReEmpty(_
), r @
(ReEarlyBound(_
) | ReFree(_
)))
520 | (r @
(ReEarlyBound(_
) | ReFree(_
)), &ReEmpty(_
)) => {
521 // All empty regions are less than early-bound, free,
522 // and scope regions.
526 (&ReEmpty(a_ui
), &ReEmpty(b_ui
)) => {
527 // Empty regions are ordered according to the universe
528 // they are associated with.
529 let ui
= a_ui
.min(b_ui
);
530 self.tcx().mk_region(ReEmpty(ui
))
533 (&ReEmpty(empty_ui
), &RePlaceholder(placeholder
))
534 | (&RePlaceholder(placeholder
), &ReEmpty(empty_ui
)) => {
535 // If this empty region is from a universe that can
536 // name the placeholder, then the placeholder is
537 // larger; otherwise, the only ancestor is `'static`.
538 if empty_ui
.can_name(placeholder
.universe
) {
539 self.tcx().mk_region(RePlaceholder(placeholder
))
541 self.tcx().lifetimes
.re_static
545 (&ReEarlyBound(_
) | &ReFree(_
), &ReEarlyBound(_
) | &ReFree(_
)) => {
546 self.region_rels
.lub_free_regions(a
, b
)
549 // For these types, we cannot define any additional
551 (&RePlaceholder(..), _
) | (_
, &RePlaceholder(..)) => {
555 self.tcx().lifetimes
.re_static
560 debug
!("lub_concrete_regions({:?}, {:?}) = {:?}", a
, b
, r
);
565 /// After expansion is complete, go and check upper bounds (i.e.,
566 /// cases where the region cannot grow larger than a fixed point)
567 /// and check that they are satisfied.
570 var_data
: &mut LexicalRegionResolutions
<'tcx
>,
571 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
573 for (constraint
, origin
) in &self.data
.constraints
{
574 debug
!("collect_errors: constraint={:?} origin={:?}", constraint
, origin
);
576 Constraint
::RegSubVar(..) | Constraint
::VarSubVar(..) => {
577 // Expansion will ensure that these constraints hold. Ignore.
580 Constraint
::RegSubReg(sub
, sup
) => {
581 if self.sub_concrete_regions(sub
, sup
) {
586 "collect_errors: region error at {:?}: \
587 cannot verify that {:?} <= {:?}",
591 errors
.push(RegionResolutionError
::ConcreteFailure(
598 Constraint
::VarSubReg(a_vid
, b_region
) => {
599 let a_data
= var_data
.value_mut(a_vid
);
600 debug
!("contraction: {:?} == {:?}, {:?}", a_vid
, a_data
, b_region
);
602 let a_region
= match *a_data
{
603 VarValue
::ErrorValue
=> continue,
604 VarValue
::Value(a_region
) => a_region
,
607 // Do not report these errors immediately:
608 // instead, set the variable value to error and
609 // collect them later.
610 if !self.sub_concrete_regions(a_region
, b_region
) {
612 "collect_errors: region error at {:?}: \
613 cannot verify that {:?}={:?} <= {:?}",
614 origin
, a_vid
, a_region
, b_region
616 *a_data
= VarValue
::ErrorValue
;
622 // Check that all member constraints are satisfied.
623 for member_constraint
in &self.data
.member_constraints
{
624 let member_region
= var_data
.normalize(self.tcx(), member_constraint
.member_region
);
625 let choice_regions
= member_constraint
628 .map(|&choice_region
| var_data
.normalize(self.tcx(), choice_region
));
629 if !choice_regions
.clone().any(|choice_region
| member_region
== choice_region
) {
630 let span
= self.tcx().def_span(member_constraint
.opaque_type_def_id
);
631 errors
.push(RegionResolutionError
::MemberConstraintFailure
{
633 hidden_ty
: member_constraint
.hidden_ty
,
639 for verify
in &self.data
.verifys
{
640 debug
!("collect_errors: verify={:?}", verify
);
641 let sub
= var_data
.normalize(self.tcx(), verify
.region
);
643 let verify_kind_ty
= verify
.kind
.to_ty(self.tcx());
644 if self.bound_is_met(&verify
.bound
, var_data
, verify_kind_ty
, sub
) {
649 "collect_errors: region error at {:?}: \
650 cannot verify that {:?} <= {:?}",
651 verify
.origin
, verify
.region
, verify
.bound
654 errors
.push(RegionResolutionError
::GenericBoundFailure(
655 verify
.origin
.clone(),
662 /// Go over the variables that were declared to be error variables
663 /// and create a `RegionResolutionError` for each of them.
664 fn collect_var_errors(
666 var_data
: &LexicalRegionResolutions
<'tcx
>,
667 graph
: &RegionGraph
<'tcx
>,
668 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
670 debug
!("collect_var_errors, var_data = {:#?}", var_data
.values
);
672 // This is the best way that I have found to suppress
673 // duplicate and related errors. Basically we keep a set of
674 // flags for every node. Whenever an error occurs, we will
675 // walk some portion of the graph looking to find pairs of
676 // conflicting regions to report to the user. As we walk, we
677 // trip the flags from false to true, and if we find that
678 // we've already reported an error involving any particular
679 // node we just stop and don't report the current error. The
680 // idea is to report errors that derive from independent
681 // regions of the graph, but not those that derive from
682 // overlapping locations.
683 let mut dup_vec
= IndexVec
::from_elem_n(None
, self.num_vars());
685 for (node_vid
, value
) in var_data
.values
.iter_enumerated() {
687 VarValue
::Value(_
) => { /* Inference successful */ }
688 VarValue
::ErrorValue
=> {
689 // Inference impossible: this value contains
690 // inconsistent constraints.
692 // I think that in this case we should report an
693 // error now -- unlike the case above, we can't
694 // wait to see whether the user needs the result
695 // of this variable. The reason is that the mere
696 // existence of this variable implies that the
697 // region graph is inconsistent, whether or not it
700 // For example, we may have created a region
701 // variable that is the GLB of two other regions
702 // which do not have a GLB. Even if that variable
703 // is not used, it implies that those two regions
704 // *should* have a GLB.
706 // At least I think this is true. It may be that
707 // the mere existence of a conflict in a region
708 // variable that is not used is not a problem, so
709 // if this rule starts to create problems we'll
710 // have to revisit this portion of the code and
711 // think hard about it. =) -- nikomatsakis
712 self.collect_error_for_expanding_node(graph
, &mut dup_vec
, node_vid
, errors
);
718 fn construct_graph(&self) -> RegionGraph
<'tcx
> {
719 let num_vars
= self.num_vars();
721 let mut graph
= Graph
::new();
723 for _
in 0..num_vars
{
727 // Issue #30438: two distinct dummy nodes, one for incoming
728 // edges (dummy_source) and another for outgoing edges
729 // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
730 // dummy node leads one to think (erroneously) there exists a
731 // path from `b` to `a`. Two dummy nodes sidesteps the issue.
732 let dummy_source
= graph
.add_node(());
733 let dummy_sink
= graph
.add_node(());
735 for constraint
in self.data
.constraints
.keys() {
737 Constraint
::VarSubVar(a_id
, b_id
) => {
739 NodeIndex(a_id
.index() as usize),
740 NodeIndex(b_id
.index() as usize),
744 Constraint
::RegSubVar(_
, b_id
) => {
745 graph
.add_edge(dummy_source
, NodeIndex(b_id
.index() as usize), *constraint
);
747 Constraint
::VarSubReg(a_id
, _
) => {
748 graph
.add_edge(NodeIndex(a_id
.index() as usize), dummy_sink
, *constraint
);
750 Constraint
::RegSubReg(..) => {
751 // this would be an edge from `dummy_source` to
752 // `dummy_sink`; just ignore it.
760 fn collect_error_for_expanding_node(
762 graph
: &RegionGraph
<'tcx
>,
763 dup_vec
: &mut IndexVec
<RegionVid
, Option
<RegionVid
>>,
765 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
767 // Errors in expanding nodes result from a lower-bound that is
768 // not contained by an upper-bound.
769 let (mut lower_bounds
, lower_vid_bounds
, lower_dup
) =
770 self.collect_bounding_regions(graph
, node_idx
, INCOMING
, Some(dup_vec
));
771 let (mut upper_bounds
, _
, upper_dup
) =
772 self.collect_bounding_regions(graph
, node_idx
, OUTGOING
, Some(dup_vec
));
774 if lower_dup
|| upper_dup
{
778 // We place free regions first because we are special casing
779 // SubSupConflict(ReFree, ReFree) when reporting error, and so
780 // the user will more likely get a specific suggestion.
781 fn region_order_key(x
: &RegionAndOrigin
<'_
>) -> u8 {
783 ReEarlyBound(_
) => 0,
788 lower_bounds
.sort_by_key(region_order_key
);
789 upper_bounds
.sort_by_key(region_order_key
);
791 let node_universe
= self.var_infos
[node_idx
].universe
;
793 for lower_bound
in &lower_bounds
{
794 let effective_lower_bound
= if let ty
::RePlaceholder(p
) = lower_bound
.region
{
795 if node_universe
.cannot_name(p
.universe
) {
796 self.tcx().lifetimes
.re_static
804 for upper_bound
in &upper_bounds
{
805 if !self.sub_concrete_regions(effective_lower_bound
, upper_bound
.region
) {
806 let origin
= self.var_infos
[node_idx
].origin
;
808 "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
810 origin
, node_idx
, lower_bound
.region
, upper_bound
.region
812 errors
.push(RegionResolutionError
::SubSupConflict(
815 lower_bound
.origin
.clone(),
817 upper_bound
.origin
.clone(),
825 // If we have a scenario like `exists<'a> { forall<'b> { 'b:
826 // 'a } }`, we wind up without any lower-bound -- all we have
827 // are placeholders as upper bounds, but the universe of the
828 // variable `'a`, or some variable that `'a` has to outlive, doesn't
829 // permit those placeholders.
830 let min_universe
= lower_vid_bounds
832 .map(|vid
| self.var_infos
[vid
].universe
)
834 .expect("lower_vid_bounds should at least include `node_idx`");
836 for upper_bound
in &upper_bounds
{
837 if let ty
::RePlaceholder(p
) = upper_bound
.region
{
838 if min_universe
.cannot_name(p
.universe
) {
839 let origin
= self.var_infos
[node_idx
].origin
;
840 errors
.push(RegionResolutionError
::UpperBoundUniverseConflict(
844 upper_bound
.origin
.clone(),
852 // Errors in earlier passes can yield error variables without
853 // resolution errors here; delay ICE in favor of those errors.
854 self.tcx().sess
.delay_span_bug(
855 self.var_infos
[node_idx
].origin
.span(),
857 "collect_error_for_expanding_node() could not find \
858 error for var {:?} in universe {:?}, lower_bounds={:#?}, \
860 node_idx
, node_universe
, lower_bounds
, upper_bounds
865 /// Collects all regions that "bound" the variable `orig_node_idx` in the
868 /// If `dup_vec` is `Some` it's used to track duplicates between successive
869 /// calls of this function.
871 /// The return tuple fields are:
872 /// - a list of all concrete regions bounding the given region.
873 /// - the set of all region variables bounding the given region.
874 /// - a `bool` that's true if the returned region variables overlap with
875 /// those returned by a previous call for another region.
876 fn collect_bounding_regions(
878 graph
: &RegionGraph
<'tcx
>,
879 orig_node_idx
: RegionVid
,
881 mut dup_vec
: Option
<&mut IndexVec
<RegionVid
, Option
<RegionVid
>>>,
882 ) -> (Vec
<RegionAndOrigin
<'tcx
>>, FxHashSet
<RegionVid
>, bool
) {
883 struct WalkState
<'tcx
> {
884 set
: FxHashSet
<RegionVid
>,
885 stack
: Vec
<RegionVid
>,
886 result
: Vec
<RegionAndOrigin
<'tcx
>>,
889 let mut state
= WalkState
{
890 set
: Default
::default(),
891 stack
: vec
![orig_node_idx
],
895 state
.set
.insert(orig_node_idx
);
897 // to start off the process, walk the source node in the
898 // direction specified
899 process_edges(&self.data
, &mut state
, graph
, orig_node_idx
, dir
);
901 while let Some(node_idx
) = state
.stack
.pop() {
902 // check whether we've visited this node on some previous walk
903 if let Some(dup_vec
) = &mut dup_vec
{
904 if dup_vec
[node_idx
].is_none() {
905 dup_vec
[node_idx
] = Some(orig_node_idx
);
906 } else if dup_vec
[node_idx
] != Some(orig_node_idx
) {
907 state
.dup_found
= true;
911 "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
912 orig_node_idx
, node_idx
916 process_edges(&self.data
, &mut state
, graph
, node_idx
, dir
);
919 let WalkState { result, dup_found, set, .. }
= state
;
920 return (result
, set
, dup_found
);
922 fn process_edges
<'tcx
>(
923 this
: &RegionConstraintData
<'tcx
>,
924 state
: &mut WalkState
<'tcx
>,
925 graph
: &RegionGraph
<'tcx
>,
926 source_vid
: RegionVid
,
929 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
931 let source_node_index
= NodeIndex(source_vid
.index() as usize);
932 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
934 Constraint
::VarSubVar(from_vid
, to_vid
) => {
935 let opp_vid
= if from_vid
== source_vid { to_vid }
else { from_vid }
;
936 if state
.set
.insert(opp_vid
) {
937 state
.stack
.push(opp_vid
);
941 Constraint
::RegSubVar(region
, _
) | Constraint
::VarSubReg(_
, region
) => {
942 state
.result
.push(RegionAndOrigin
{
944 origin
: this
.constraints
.get(&edge
.data
).unwrap().clone(),
948 Constraint
::RegSubReg(..) => panic
!(
949 "cannot reach reg-sub-reg edge in region inference \
959 bound
: &VerifyBound
<'tcx
>,
960 var_values
: &LexicalRegionResolutions
<'tcx
>,
961 generic_ty
: Ty
<'tcx
>,
962 min
: ty
::Region
<'tcx
>,
965 VerifyBound
::IfEq(k
, b
) => {
966 (var_values
.normalize(self.region_rels
.tcx
, *k
) == generic_ty
)
967 && self.bound_is_met(b
, var_values
, generic_ty
, min
)
970 VerifyBound
::OutlivedBy(r
) => {
971 self.sub_concrete_regions(min
, var_values
.normalize(self.tcx(), r
))
974 VerifyBound
::IsEmpty
=> {
975 if let ty
::ReEmpty(_
) = min
{
982 VerifyBound
::AnyBound(bs
) => {
983 bs
.iter().any(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
986 VerifyBound
::AllBounds(bs
) => {
987 bs
.iter().all(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
993 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
994 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
995 write
!(f
, "RegionAndOrigin({:?},{:?})", self.region
, self.origin
)
999 impl<'tcx
> LexicalRegionResolutions
<'tcx
> {
1000 fn normalize
<T
>(&self, tcx
: TyCtxt
<'tcx
>, value
: T
) -> T
1002 T
: TypeFoldable
<'tcx
>,
1004 tcx
.fold_regions(&value
, &mut false, |r
, _db
| match r
{
1005 ty
::ReVar(rid
) => self.resolve_var(*rid
),
1010 fn value(&self, rid
: RegionVid
) -> &VarValue
<'tcx
> {
1014 fn value_mut(&mut self, rid
: RegionVid
) -> &mut VarValue
<'tcx
> {
1015 &mut self.values
[rid
]
1018 pub fn resolve_var(&self, rid
: RegionVid
) -> ty
::Region
<'tcx
> {
1019 let result
= match self.values
[rid
] {
1020 VarValue
::Value(r
) => r
,
1021 VarValue
::ErrorValue
=> self.error_region
,
1023 debug
!("resolve_var({:?}) = {:?}", rid
, result
);