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
::RegionVariableOrigin
;
10 use crate::infer
::RegionckMode
;
11 use crate::infer
::SubregionOrigin
;
12 use rustc_data_structures
::fx
::FxHashSet
;
13 use rustc_data_structures
::graph
::implementation
::{
14 Direction
, Graph
, NodeIndex
, INCOMING
, OUTGOING
,
16 use rustc_index
::vec
::{Idx, IndexVec}
;
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}
;
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.
34 region_rels
: &RegionRelations
<'_
, 'tcx
>,
36 data
: RegionConstraintData
<'tcx
>,
38 ) -> (LexicalRegionResolutions
<'tcx
>, Vec
<RegionResolutionError
<'tcx
>>) {
39 debug
!("RegionConstraintData: resolve_regions()");
40 let mut errors
= vec
![];
41 let mut resolver
= LexicalResolver { region_rels, var_infos, data }
;
43 RegionckMode
::Solve
=> {
44 let values
= resolver
.infer_variable_values(&mut errors
);
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
;
52 values
.values
.iter_mut().for_each(|v
| *v
= VarValue
::Value(re_erased
));
55 RegionckMode
::Erase { suppress_errors: true }
=> {
56 // Skip region inference entirely.
57 (resolver
.erased_data(region_rels
.tcx
), Vec
::new())
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
>,
69 #[derive(Copy, Clone, Debug)]
75 #[derive(Clone, Debug)]
76 pub enum RegionResolutionError
<'tcx
> {
77 /// `ConcreteFailure(o, a, b)`:
79 /// `o` requires that `a <= b`, but this does not hold
80 ConcreteFailure(SubregionOrigin
<'tcx
>, Region
<'tcx
>, Region
<'tcx
>),
82 /// `GenericBoundFailure(p, s, a)
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
>),
88 /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
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
92 /// `sub_r <= sup_r` does not hold.
96 SubregionOrigin
<'tcx
>,
98 SubregionOrigin
<'tcx
>,
102 /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
103 /// cannot name the placeholder `'b`.
104 UpperBoundUniverseConflict(
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`
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.
115 MemberConstraintFailure { span: Span, hidden_ty: Ty<'tcx>, member_region: Region<'tcx> }
,
118 struct RegionAndOrigin
<'tcx
> {
119 region
: Region
<'tcx
>,
120 origin
: SubregionOrigin
<'tcx
>,
123 type RegionGraph
<'tcx
> = Graph
<(), Constraint
<'tcx
>>;
125 struct LexicalResolver
<'cx
, 'tcx
> {
126 region_rels
: &'cx RegionRelations
<'cx
, 'tcx
>,
128 data
: RegionConstraintData
<'tcx
>,
131 impl<'cx
, 'tcx
> LexicalResolver
<'cx
, 'tcx
> {
132 fn tcx(&self) -> TyCtxt
<'tcx
> {
136 fn infer_variable_values(
138 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
139 ) -> LexicalRegionResolutions
<'tcx
> {
140 let mut var_data
= self.construct_var_data(self.tcx());
142 // Dorky hack to cause `dump_constraints` to only get called
143 // if debug mode is enabled:
145 "----() End constraint listing (context={:?}) {:?}---",
146 self.region_rels
.context
,
147 self.dump_constraints(self.region_rels
)
149 graphviz
::maybe_print_constraints_for(&self.data
, 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_concrete_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 // Identical scopes can show up quite often, if the fixed point
427 // iteration converges slowly. Skip them. This is purely an
429 if let (ReScope(a_scope
), ReScope(cur_scope
)) = (a_region
, cur_region
) {
430 if a_scope
== cur_scope
{
435 // This is a specialized version of the `lub_concrete_regions`
436 // check below for a common case, here purely as an
438 let b_universe
= self.var_infos
[b_vid
].universe
;
439 if let ReEmpty(a_universe
) = a_region
{
440 if *a_universe
== b_universe
{
445 let mut lub
= self.lub_concrete_regions(a_region
, cur_region
);
446 if lub
== cur_region
{
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`.
458 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
459 if let ty
::RePlaceholder(p
) = lub
{
460 if b_universe
.cannot_name(p
.universe
) {
461 lub
= self.tcx().lifetimes
.re_static
;
465 debug
!("Expanding value of {:?} from {:?} to {:?}", b_vid
, cur_region
, lub
);
467 *b_data
= VarValue
::Value(lub
);
471 VarValue
::ErrorValue
=> false,
475 /// True if `a <= b`, but not defined over inference variables.
476 fn sub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> bool
{
477 let tcx
= self.tcx();
478 let sub_free_regions
= |r1
, r2
| self.region_rels
.free_regions
.sub_free_regions(tcx
, r1
, r2
);
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
) {
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
);
497 // For other cases, leverage the LUB code to find the LUB and
498 // check if it is equal to `b`.
499 self.lub_concrete_regions(a
, b
) == b
502 /// Returns the least-upper-bound of `a` and `b`; i.e., the
503 /// smallest region `c` such that `a <= c` and `b <= c`.
505 /// Neither `a` nor `b` may be an inference variable (hence the
506 /// term "concrete regions").
507 fn lub_concrete_regions(&self, a
: Region
<'tcx
>, b
: Region
<'tcx
>) -> Region
<'tcx
> {
508 let r
= match (a
, b
) {
509 (&ReLateBound(..), _
) | (_
, &ReLateBound(..)) | (&ReErased
, _
) | (_
, &ReErased
) => {
510 bug
!("cannot relate region: LUB({:?}, {:?})", a
, b
);
513 (&ReVar(v_id
), _
) | (_
, &ReVar(v_id
)) => {
515 self.var_infos
[v_id
].origin
.span(),
516 "lub_concrete_regions invoked with non-concrete \
517 regions: {:?}, {:?}",
523 (&ReStatic
, _
) | (_
, &ReStatic
) => {
524 // nothing lives longer than `'static`
525 self.tcx().lifetimes
.re_static
528 (&ReEmpty(_
), r @
(ReEarlyBound(_
) | ReFree(_
) | ReScope(_
)))
529 | (r @
(ReEarlyBound(_
) | ReFree(_
) | ReScope(_
)), &ReEmpty(_
)) => {
530 // All empty regions are less than early-bound, free,
531 // and scope regions.
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
))
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
))
550 self.tcx().lifetimes
.re_static
554 (&ReEarlyBound(_
) | &ReFree(_
), &ReScope(s_id
))
555 | (&ReScope(s_id
), &ReEarlyBound(_
) | &ReFree(_
)) => {
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
) {
560 (&ReEarlyBound(ref br
), _
) | (_
, &ReEarlyBound(ref br
)) => {
561 self.region_rels
.region_scope_tree
.early_free_scope(self.tcx(), br
)
563 (&ReFree(ref fr
), _
) | (_
, &ReFree(ref fr
)) => {
564 self.region_rels
.region_scope_tree
.free_scope(self.tcx(), fr
)
569 self.region_rels
.region_scope_tree
.nearest_common_ancestor(fr_scope
, s_id
);
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
575 (_
, &ReScope(_
)) => return a
,
576 (&ReScope(_
), _
) => return b
,
581 // otherwise, we don't know what the free region is,
582 // so we must conservatively say the LUB is static:
583 self.tcx().lifetimes
.re_static
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
590 let lub
= self.region_rels
.region_scope_tree
.nearest_common_ancestor(a_id
, b_id
);
591 self.tcx().mk_region(ReScope(lub
))
594 (&ReEarlyBound(_
) | &ReFree(_
), &ReEarlyBound(_
) | &ReFree(_
)) => {
595 self.region_rels
.lub_free_regions(a
, b
)
598 // For these types, we cannot define any additional
600 (&RePlaceholder(..), _
) | (_
, &RePlaceholder(..)) => {
604 self.tcx().lifetimes
.re_static
609 debug
!("lub_concrete_regions({:?}, {:?}) = {:?}", a
, b
, r
);
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.
619 var_data
: &mut LexicalRegionResolutions
<'tcx
>,
620 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
622 for (constraint
, origin
) in &self.data
.constraints
{
623 debug
!("collect_errors: constraint={:?} origin={:?}", constraint
, origin
);
625 Constraint
::RegSubVar(..) | Constraint
::VarSubVar(..) => {
626 // Expansion will ensure that these constraints hold. Ignore.
629 Constraint
::RegSubReg(sub
, sup
) => {
630 if self.sub_concrete_regions(sub
, sup
) {
635 "collect_errors: region error at {:?}: \
636 cannot verify that {:?} <= {:?}",
640 errors
.push(RegionResolutionError
::ConcreteFailure(
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
);
651 let a_region
= match *a_data
{
652 VarValue
::ErrorValue
=> continue,
653 VarValue
::Value(a_region
) => a_region
,
656 // Do not report these errors immediately:
657 // instead, set the variable value to error and
658 // collect them later.
659 if !self.sub_concrete_regions(a_region
, b_region
) {
661 "collect_errors: region error at {:?}: \
662 cannot verify that {:?}={:?} <= {:?}",
663 origin
, a_vid
, a_region
, b_region
665 *a_data
= VarValue
::ErrorValue
;
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
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
{
682 hidden_ty
: member_constraint
.hidden_ty
,
688 for verify
in &self.data
.verifys
{
689 debug
!("collect_errors: verify={:?}", verify
);
690 let sub
= var_data
.normalize(self.tcx(), verify
.region
);
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
) {
698 "collect_errors: region error at {:?}: \
699 cannot verify that {:?} <= {:?}",
700 verify
.origin
, verify
.region
, verify
.bound
703 errors
.push(RegionResolutionError
::GenericBoundFailure(
704 verify
.origin
.clone(),
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(
715 var_data
: &LexicalRegionResolutions
<'tcx
>,
716 graph
: &RegionGraph
<'tcx
>,
717 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
719 debug
!("collect_var_errors");
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.
732 let mut dup_vec
= IndexVec
::from_elem_n(None
, self.num_vars());
734 for (node_vid
, value
) in var_data
.values
.iter_enumerated() {
736 VarValue
::Value(_
) => { /* Inference successful */ }
737 VarValue
::ErrorValue
=> {
738 // Inference impossible: this value contains
739 // inconsistent constraints.
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
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.
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
761 self.collect_error_for_expanding_node(graph
, &mut dup_vec
, node_vid
, errors
);
767 fn construct_graph(&self) -> RegionGraph
<'tcx
> {
768 let num_vars
= self.num_vars();
770 let mut graph
= Graph
::new();
772 for _
in 0..num_vars
{
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(());
784 for constraint
in self.data
.constraints
.keys() {
786 Constraint
::VarSubVar(a_id
, b_id
) => {
788 NodeIndex(a_id
.index() as usize),
789 NodeIndex(b_id
.index() as usize),
793 Constraint
::RegSubVar(_
, b_id
) => {
794 graph
.add_edge(dummy_source
, NodeIndex(b_id
.index() as usize), *constraint
);
796 Constraint
::VarSubReg(a_id
, _
) => {
797 graph
.add_edge(NodeIndex(a_id
.index() as usize), dummy_sink
, *constraint
);
799 Constraint
::RegSubReg(..) => {
800 // this would be an edge from `dummy_source` to
801 // `dummy_sink`; just ignore it.
809 fn collect_error_for_expanding_node(
811 graph
: &RegionGraph
<'tcx
>,
812 dup_vec
: &mut IndexVec
<RegionVid
, Option
<RegionVid
>>,
814 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
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
) =
819 self.collect_concrete_regions(graph
, node_idx
, INCOMING
, Some(dup_vec
));
820 let (mut upper_bounds
, upper_dup
) =
821 self.collect_concrete_regions(graph
, node_idx
, OUTGOING
, Some(dup_vec
));
823 if lower_dup
|| upper_dup
{
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.
830 fn region_order_key(x
: &RegionAndOrigin
<'_
>) -> u8 {
832 ReEarlyBound(_
) => 0,
837 lower_bounds
.sort_by_key(region_order_key
);
838 upper_bounds
.sort_by_key(region_order_key
);
840 let node_universe
= self.var_infos
[node_idx
].universe
;
842 for lower_bound
in &lower_bounds
{
843 let effective_lower_bound
= if let ty
::RePlaceholder(p
) = lower_bound
.region
{
844 if node_universe
.cannot_name(p
.universe
) {
845 self.tcx().lifetimes
.re_static
853 for upper_bound
in &upper_bounds
{
854 if !self.sub_concrete_regions(effective_lower_bound
, upper_bound
.region
) {
855 let origin
= self.var_infos
[node_idx
].origin
;
857 "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
859 origin
, node_idx
, lower_bound
.region
, upper_bound
.region
861 errors
.push(RegionResolutionError
::SubSupConflict(
864 lower_bound
.origin
.clone(),
866 upper_bound
.origin
.clone(),
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(
886 upper_bound
.origin
.clone(),
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(
897 self.var_infos
[node_idx
].origin
.span(),
899 "collect_error_for_expanding_node() could not find \
900 error for var {:?} in universe {:?}, lower_bounds={:#?}, \
902 node_idx
, node_universe
, lower_bounds
, upper_bounds
907 fn collect_concrete_regions(
909 graph
: &RegionGraph
<'tcx
>,
910 orig_node_idx
: RegionVid
,
912 mut dup_vec
: Option
<&mut IndexVec
<RegionVid
, Option
<RegionVid
>>>,
913 ) -> (Vec
<RegionAndOrigin
<'tcx
>>, bool
) {
914 struct WalkState
<'tcx
> {
915 set
: FxHashSet
<RegionVid
>,
916 stack
: Vec
<RegionVid
>,
917 result
: Vec
<RegionAndOrigin
<'tcx
>>,
920 let mut state
= WalkState
{
921 set
: Default
::default(),
922 stack
: vec
![orig_node_idx
],
926 state
.set
.insert(orig_node_idx
);
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
);
932 while !state
.stack
.is_empty() {
933 let node_idx
= state
.stack
.pop().unwrap();
935 // check whether we've visited this node on some previous walk
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;
944 "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
945 orig_node_idx
, node_idx
949 process_edges(&self.data
, &mut state
, graph
, node_idx
, dir
);
952 let WalkState { result, dup_found, .. }
= state
;
953 return (result
, dup_found
);
955 fn process_edges
<'tcx
>(
956 this
: &RegionConstraintData
<'tcx
>,
957 state
: &mut WalkState
<'tcx
>,
958 graph
: &RegionGraph
<'tcx
>,
959 source_vid
: RegionVid
,
962 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
964 let source_node_index
= NodeIndex(source_vid
.index() as usize);
965 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
967 Constraint
::VarSubVar(from_vid
, to_vid
) => {
968 let opp_vid
= if from_vid
== source_vid { to_vid }
else { from_vid }
;
969 if state
.set
.insert(opp_vid
) {
970 state
.stack
.push(opp_vid
);
974 Constraint
::RegSubVar(region
, _
) | Constraint
::VarSubReg(_
, region
) => {
975 state
.result
.push(RegionAndOrigin
{
977 origin
: this
.constraints
.get(&edge
.data
).unwrap().clone(),
981 Constraint
::RegSubReg(..) => panic
!(
982 "cannot reach reg-sub-reg edge in region inference \
992 bound
: &VerifyBound
<'tcx
>,
993 var_values
: &LexicalRegionResolutions
<'tcx
>,
994 generic_ty
: Ty
<'tcx
>,
995 min
: ty
::Region
<'tcx
>,
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
)
1003 VerifyBound
::OutlivedBy(r
) => {
1004 self.sub_concrete_regions(min
, var_values
.normalize(self.tcx(), r
))
1007 VerifyBound
::IsEmpty
=> {
1008 if let ty
::ReEmpty(_
) = min
{
1015 VerifyBound
::AnyBound(bs
) => {
1016 bs
.iter().any(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
1019 VerifyBound
::AllBounds(bs
) => {
1020 bs
.iter().all(|b
| self.bound_is_met(b
, var_values
, generic_ty
, min
))
1026 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
1027 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1028 write
!(f
, "RegionAndOrigin({:?},{:?})", self.region
, self.origin
)
1032 impl<'tcx
> LexicalRegionResolutions
<'tcx
> {
1033 fn normalize
<T
>(&self, tcx
: TyCtxt
<'tcx
>, value
: T
) -> T
1035 T
: TypeFoldable
<'tcx
>,
1037 tcx
.fold_regions(&value
, &mut false, |r
, _db
| match r
{
1038 ty
::ReVar(rid
) => self.resolve_var(*rid
),
1043 fn value(&self, rid
: RegionVid
) -> &VarValue
<'tcx
> {
1047 fn value_mut(&mut self, rid
: RegionVid
) -> &mut VarValue
<'tcx
> {
1048 &mut self.values
[rid
]
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
,
1056 debug
!("resolve_var({:?}) = {:?}", rid
, result
);