1 use std
::collections
::VecDeque
;
4 use rustc_data_structures
::binary_search_util
;
5 use rustc_data_structures
::frozen
::Frozen
;
6 use rustc_data_structures
::fx
::{FxIndexMap, FxIndexSet}
;
7 use rustc_data_structures
::graph
::scc
::Sccs
;
8 use rustc_errors
::Diagnostic
;
9 use rustc_hir
::def_id
::CRATE_DEF_ID
;
10 use rustc_index
::{IndexSlice, IndexVec}
;
11 use rustc_infer
::infer
::outlives
::test_type_match
;
12 use rustc_infer
::infer
::region_constraints
::{GenericKind, VarInfos, VerifyBound, VerifyIfEq}
;
13 use rustc_infer
::infer
::{InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin}
;
14 use rustc_middle
::mir
::{
15 BasicBlock
, Body
, ClosureOutlivesRequirement
, ClosureOutlivesSubject
, ClosureOutlivesSubjectTy
,
16 ClosureRegionRequirements
, ConstraintCategory
, Local
, Location
, ReturnConstraint
,
19 use rustc_middle
::traits
::ObligationCause
;
20 use rustc_middle
::traits
::ObligationCauseCode
;
21 use rustc_middle
::ty
::{self, RegionVid, Ty, TyCtxt, TypeFoldable, TypeVisitableExt}
;
26 graph
::NormalConstraintGraph
, ConstraintSccIndex
, OutlivesConstraint
, OutlivesConstraintSet
,
28 diagnostics
::{RegionErrorKind, RegionErrors, UniverseInfo}
,
29 member_constraints
::{MemberConstraintSet, NllMemberConstraintIndex}
,
31 region_infer
::reverse_sccs
::ReverseSccGraph
,
32 region_infer
::values
::{
33 LivenessValues
, PlaceholderIndices
, RegionElement
, RegionValueElements
, RegionValues
,
36 type_check
::{free_region_relations::UniversalRegionRelations, Locations}
,
37 universal_regions
::UniversalRegions
,
48 pub struct RegionInferenceContext
<'tcx
> {
49 pub var_infos
: VarInfos
,
51 /// Contains the definition for every region variable. Region
52 /// variables are identified by their index (`RegionVid`). The
53 /// definition contains information about where the region came
54 /// from as well as its final inferred value.
55 definitions
: IndexVec
<RegionVid
, RegionDefinition
<'tcx
>>,
57 /// The liveness constraints added to each region. For most
58 /// regions, these start out empty and steadily grow, though for
59 /// each universally quantified region R they start out containing
60 /// the entire CFG and `end(R)`.
61 liveness_constraints
: LivenessValues
<RegionVid
>,
63 /// The outlives constraints computed by the type-check.
64 constraints
: Frozen
<OutlivesConstraintSet
<'tcx
>>,
66 /// The constraint-set, but in graph form, making it easy to traverse
67 /// the constraints adjacent to a particular region. Used to construct
68 /// the SCC (see `constraint_sccs`) and for error reporting.
69 constraint_graph
: Frozen
<NormalConstraintGraph
>,
71 /// The SCC computed from `constraints` and the constraint
72 /// graph. We have an edge from SCC A to SCC B if `A: B`. Used to
73 /// compute the values of each region.
74 constraint_sccs
: Rc
<Sccs
<RegionVid
, ConstraintSccIndex
>>,
76 /// Reverse of the SCC constraint graph -- i.e., an edge `A -> B` exists if
77 /// `B: A`. This is used to compute the universal regions that are required
78 /// to outlive a given SCC. Computed lazily.
79 rev_scc_graph
: Option
<ReverseSccGraph
>,
81 /// The "R0 member of [R1..Rn]" constraints, indexed by SCC.
82 member_constraints
: Rc
<MemberConstraintSet
<'tcx
, ConstraintSccIndex
>>,
84 /// Records the member constraints that we applied to each scc.
85 /// This is useful for error reporting. Once constraint
86 /// propagation is done, this vector is sorted according to
87 /// `member_region_scc`.
88 member_constraints_applied
: Vec
<AppliedMemberConstraint
>,
90 /// Map universe indexes to information on why we created it.
91 universe_causes
: FxIndexMap
<ty
::UniverseIndex
, UniverseInfo
<'tcx
>>,
93 /// Contains the minimum universe of any variable within the same
94 /// SCC. We will ensure that no SCC contains values that are not
95 /// visible from this index.
96 scc_universes
: IndexVec
<ConstraintSccIndex
, ty
::UniverseIndex
>,
98 /// Contains a "representative" from each SCC. This will be the
99 /// minimal RegionVid belonging to that universe. It is used as a
100 /// kind of hacky way to manage checking outlives relationships,
101 /// since we can 'canonicalize' each region to the representative
102 /// of its SCC and be sure that -- if they have the same repr --
103 /// they *must* be equal (though not having the same repr does not
104 /// mean they are unequal).
105 scc_representatives
: IndexVec
<ConstraintSccIndex
, ty
::RegionVid
>,
107 /// The final inferred values of the region variables; we compute
108 /// one value per SCC. To get the value for any given *region*,
109 /// you first find which scc it is a part of.
110 scc_values
: RegionValues
<ConstraintSccIndex
>,
112 /// Type constraints that we check after solving.
113 type_tests
: Vec
<TypeTest
<'tcx
>>,
115 /// Information about the universally quantified regions in scope
116 /// on this function.
117 universal_regions
: Rc
<UniversalRegions
<'tcx
>>,
119 /// Information about how the universally quantified regions in
120 /// scope on this function relate to one another.
121 universal_region_relations
: Frozen
<UniversalRegionRelations
<'tcx
>>,
124 /// Each time that `apply_member_constraint` is successful, it appends
125 /// one of these structs to the `member_constraints_applied` field.
126 /// This is used in error reporting to trace out what happened.
128 /// The way that `apply_member_constraint` works is that it effectively
129 /// adds a new lower bound to the SCC it is analyzing: so you wind up
130 /// with `'R: 'O` where `'R` is the pick-region and `'O` is the
131 /// minimal viable option.
133 pub(crate) struct AppliedMemberConstraint
{
134 /// The SCC that was affected. (The "member region".)
136 /// The vector if `AppliedMemberConstraint` elements is kept sorted
138 pub(crate) member_region_scc
: ConstraintSccIndex
,
140 /// The "best option" that `apply_member_constraint` found -- this was
141 /// added as an "ad-hoc" lower-bound to `member_region_scc`.
142 pub(crate) min_choice
: ty
::RegionVid
,
144 /// The "member constraint index" -- we can find out details about
145 /// the constraint from
146 /// `set.member_constraints[member_constraint_index]`.
147 pub(crate) member_constraint_index
: NllMemberConstraintIndex
,
150 pub(crate) struct RegionDefinition
<'tcx
> {
151 /// What kind of variable is this -- a free region? existential
152 /// variable? etc. (See the `NllRegionVariableOrigin` for more
154 pub(crate) origin
: NllRegionVariableOrigin
,
156 /// Which universe is this region variable defined in? This is
157 /// most often `ty::UniverseIndex::ROOT`, but when we encounter
158 /// forall-quantifiers like `for<'a> { 'a = 'b }`, we would create
159 /// the variable for `'a` in a fresh universe that extends ROOT.
160 pub(crate) universe
: ty
::UniverseIndex
,
162 /// If this is 'static or an early-bound region, then this is
163 /// `Some(X)` where `X` is the name of the region.
164 pub(crate) external_name
: Option
<ty
::Region
<'tcx
>>,
167 /// N.B., the variants in `Cause` are intentionally ordered. Lower
168 /// values are preferred when it comes to error messages. Do not
169 /// reorder willy nilly.
170 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
171 pub(crate) enum Cause
{
172 /// point inserted because Local was live at the given Location
173 LiveVar(Local
, Location
),
175 /// point inserted because Local was dropped at the given Location
176 DropVar(Local
, Location
),
179 /// A "type test" corresponds to an outlives constraint between a type
180 /// and a lifetime, like `T: 'x` or `<T as Foo>::Bar: 'x`. They are
181 /// translated from the `Verify` region constraints in the ordinary
182 /// inference context.
184 /// These sorts of constraints are handled differently than ordinary
185 /// constraints, at least at present. During type checking, the
186 /// `InferCtxt::process_registered_region_obligations` method will
187 /// attempt to convert a type test like `T: 'x` into an ordinary
188 /// outlives constraint when possible (for example, `&'a T: 'b` will
189 /// be converted into `'a: 'b` and registered as a `Constraint`).
191 /// In some cases, however, there are outlives relationships that are
192 /// not converted into a region constraint, but rather into one of
193 /// these "type tests". The distinction is that a type test does not
194 /// influence the inference result, but instead just examines the
195 /// values that we ultimately inferred for each region variable and
196 /// checks that they meet certain extra criteria. If not, an error
199 /// One reason for this is that these type tests typically boil down
200 /// to a check like `'a: 'x` where `'a` is a universally quantified
201 /// region -- and therefore not one whose value is really meant to be
202 /// *inferred*, precisely (this is not always the case: one can have a
203 /// type test like `<Foo as Trait<'?0>>::Bar: 'x`, where `'?0` is an
204 /// inference variable). Another reason is that these type tests can
205 /// involve *disjunction* -- that is, they can be satisfied in more
208 /// For more information about this translation, see
209 /// `InferCtxt::process_registered_region_obligations` and
210 /// `InferCtxt::type_must_outlive` in `rustc_infer::infer::InferCtxt`.
211 #[derive(Clone, Debug)]
212 pub struct TypeTest
<'tcx
> {
213 /// The type `T` that must outlive the region.
214 pub generic_kind
: GenericKind
<'tcx
>,
216 /// The region `'x` that the type must outlive.
217 pub lower_bound
: RegionVid
,
219 /// The span to blame.
222 /// A test which, if met by the region `'x`, proves that this type
223 /// constraint is satisfied.
224 pub verify_bound
: VerifyBound
<'tcx
>,
227 /// When we have an unmet lifetime constraint, we try to propagate it outward (e.g. to a closure
228 /// environment). If we can't, it is an error.
229 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
230 enum RegionRelationCheckResult
{
236 #[derive(Clone, PartialEq, Eq, Debug)]
239 FromOutlivesConstraint(OutlivesConstraint
<'tcx
>),
243 #[derive(Clone, PartialEq, Eq, Debug)]
244 pub enum ExtraConstraintInfo
{
245 PlaceholderFromPredicate(Span
),
248 #[instrument(skip(infcx, sccs), level = "debug")]
249 fn sccs_info
<'cx
, 'tcx
>(
250 infcx
: &'cx BorrowckInferCtxt
<'cx
, 'tcx
>,
251 sccs
: Rc
<Sccs
<RegionVid
, ConstraintSccIndex
>>,
253 use crate::renumber
::RegionCtxt
;
255 let var_to_origin
= infcx
.reg_var_to_origin
.borrow();
257 let mut var_to_origin_sorted
= var_to_origin
.clone().into_iter().collect
::<Vec
<_
>>();
258 var_to_origin_sorted
.sort_by_key(|vto
| vto
.0);
260 let mut reg_vars_to_origins_str
= "region variables to origins:\n".to_string();
261 for (reg_var
, origin
) in var_to_origin_sorted
.into_iter() {
262 reg_vars_to_origins_str
.push_str(&format
!("{reg_var:?}: {origin:?}\n"));
264 debug
!("{}", reg_vars_to_origins_str
);
266 let num_components
= sccs
.scc_data().ranges().len();
267 let mut components
= vec
![FxIndexSet
::default(); num_components
];
269 for (reg_var_idx
, scc_idx
) in sccs
.scc_indices().iter().enumerate() {
270 let reg_var
= ty
::RegionVid
::from_usize(reg_var_idx
);
271 let origin
= var_to_origin
.get(®_var
).unwrap_or_else(|| &RegionCtxt
::Unknown
);
272 components
[scc_idx
.as_usize()].insert((reg_var
, *origin
));
275 let mut components_str
= "strongly connected components:".to_string();
276 for (scc_idx
, reg_vars_origins
) in components
.iter().enumerate() {
277 let regions_info
= reg_vars_origins
.clone().into_iter().collect
::<Vec
<_
>>();
278 components_str
.push_str(&format
!(
280 ConstraintSccIndex
::from_usize(scc_idx
),
284 debug
!("{}", components_str
);
286 // calculate the best representative for each component
287 let components_representatives
= components
290 .map(|(scc_idx
, region_ctxts
)| {
291 let repr
= region_ctxts
293 .map(|reg_var_origin
| reg_var_origin
.1)
294 .max_by(|x
, y
| x
.preference_value().cmp(&y
.preference_value()))
297 (ConstraintSccIndex
::from_usize(scc_idx
), repr
)
299 .collect
::<FxIndexMap
<_
, _
>>();
301 let mut scc_node_to_edges
= FxIndexMap
::default();
302 for (scc_idx
, repr
) in components_representatives
.iter() {
303 let edges_range
= sccs
.scc_data().ranges()[*scc_idx
].clone();
304 let edges
= &sccs
.scc_data().all_successors()[edges_range
];
305 let edge_representatives
=
306 edges
.iter().map(|scc_idx
| components_representatives
[scc_idx
]).collect
::<Vec
<_
>>();
307 scc_node_to_edges
.insert((scc_idx
, repr
), edge_representatives
);
310 debug
!("SCC edges {:#?}", scc_node_to_edges
);
313 impl<'tcx
> RegionInferenceContext
<'tcx
> {
314 /// Creates a new region inference context with a total of
315 /// `num_region_variables` valid inference variables; the first N
316 /// of those will be constant regions representing the free
317 /// regions defined in `universal_regions`.
319 /// The `outlives_constraints` and `type_tests` are an initial set
320 /// of constraints produced by the MIR type check.
321 pub(crate) fn new
<'cx
>(
322 _infcx
: &BorrowckInferCtxt
<'cx
, 'tcx
>,
324 universal_regions
: Rc
<UniversalRegions
<'tcx
>>,
325 placeholder_indices
: Rc
<PlaceholderIndices
>,
326 universal_region_relations
: Frozen
<UniversalRegionRelations
<'tcx
>>,
327 outlives_constraints
: OutlivesConstraintSet
<'tcx
>,
328 member_constraints_in
: MemberConstraintSet
<'tcx
, RegionVid
>,
329 universe_causes
: FxIndexMap
<ty
::UniverseIndex
, UniverseInfo
<'tcx
>>,
330 type_tests
: Vec
<TypeTest
<'tcx
>>,
331 liveness_constraints
: LivenessValues
<RegionVid
>,
332 elements
: &Rc
<RegionValueElements
>,
334 debug
!("universal_regions: {:#?}", universal_regions
);
335 debug
!("outlives constraints: {:#?}", outlives_constraints
);
336 debug
!("placeholder_indices: {:#?}", placeholder_indices
);
337 debug
!("type tests: {:#?}", type_tests
);
339 // Create a RegionDefinition for each inference variable.
340 let definitions
: IndexVec
<_
, _
> = var_infos
342 .map(|info
| RegionDefinition
::new(info
.universe
, info
.origin
))
345 let constraints
= Frozen
::freeze(outlives_constraints
);
346 let constraint_graph
= Frozen
::freeze(constraints
.graph(definitions
.len()));
347 let fr_static
= universal_regions
.fr_static
;
348 let constraint_sccs
= Rc
::new(constraints
.compute_sccs(&constraint_graph
, fr_static
));
350 if cfg
!(debug_assertions
) {
351 sccs_info(_infcx
, constraint_sccs
.clone());
355 RegionValues
::new(elements
, universal_regions
.len(), &placeholder_indices
);
357 for region
in liveness_constraints
.rows() {
358 let scc
= constraint_sccs
.scc(region
);
359 scc_values
.merge_liveness(scc
, region
, &liveness_constraints
);
362 let scc_universes
= Self::compute_scc_universes(&constraint_sccs
, &definitions
);
364 let scc_representatives
= Self::compute_scc_representatives(&constraint_sccs
, &definitions
);
366 let member_constraints
=
367 Rc
::new(member_constraints_in
.into_mapped(|r
| constraint_sccs
.scc(r
)));
369 let mut result
= Self {
372 liveness_constraints
,
378 member_constraints_applied
: Vec
::new(),
385 universal_region_relations
,
388 result
.init_free_and_bound_regions();
393 /// Each SCC is the combination of many region variables which
394 /// have been equated. Therefore, we can associate a universe with
395 /// each SCC which is minimum of all the universes of its
396 /// constituent regions -- this is because whatever value the SCC
397 /// takes on must be a value that each of the regions within the
398 /// SCC could have as well. This implies that the SCC must have
399 /// the minimum, or narrowest, universe.
400 fn compute_scc_universes(
401 constraint_sccs
: &Sccs
<RegionVid
, ConstraintSccIndex
>,
402 definitions
: &IndexSlice
<RegionVid
, RegionDefinition
<'tcx
>>,
403 ) -> IndexVec
<ConstraintSccIndex
, ty
::UniverseIndex
> {
404 let num_sccs
= constraint_sccs
.num_sccs();
405 let mut scc_universes
= IndexVec
::from_elem_n(ty
::UniverseIndex
::MAX
, num_sccs
);
407 debug
!("compute_scc_universes()");
409 // For each region R in universe U, ensure that the universe for the SCC
410 // that contains R is "no bigger" than U. This effectively sets the universe
411 // for each SCC to be the minimum of the regions within.
412 for (region_vid
, region_definition
) in definitions
.iter_enumerated() {
413 let scc
= constraint_sccs
.scc(region_vid
);
414 let scc_universe
= &mut scc_universes
[scc
];
415 let scc_min
= std
::cmp
::min(region_definition
.universe
, *scc_universe
);
416 if scc_min
!= *scc_universe
{
417 *scc_universe
= scc_min
;
419 "compute_scc_universes: lowered universe of {scc:?} to {scc_min:?} \
420 because it contains {region_vid:?} in {region_universe:?}",
423 region_vid
= region_vid
,
424 region_universe
= region_definition
.universe
,
429 // Walk each SCC `A` and `B` such that `A: B`
430 // and ensure that universe(A) can see universe(B).
432 // This serves to enforce the 'empty/placeholder' hierarchy
433 // (described in more detail on `RegionKind`):
438 // empty(U0) placeholder(U1)
443 // In particular, imagine we have variables R0 in U0 and R1
444 // created in U1, and constraints like this;
447 // R1: !1 // R1 outlives the placeholder in U1
448 // R1: R0 // R1 outlives R0
451 // Here, we wish for R1 to be `'static`, because it
452 // cannot outlive `placeholder(U1)` and `empty(U0)` any other way.
454 // Thanks to this loop, what happens is that the `R1: R0`
455 // constraint lowers the universe of `R1` to `U0`, which in turn
456 // means that the `R1: !1` constraint will (later) cause
457 // `R1` to become `'static`.
458 for scc_a
in constraint_sccs
.all_sccs() {
459 for &scc_b
in constraint_sccs
.successors(scc_a
) {
460 let scc_universe_a
= scc_universes
[scc_a
];
461 let scc_universe_b
= scc_universes
[scc_b
];
462 let scc_universe_min
= std
::cmp
::min(scc_universe_a
, scc_universe_b
);
463 if scc_universe_a
!= scc_universe_min
{
464 scc_universes
[scc_a
] = scc_universe_min
;
467 "compute_scc_universes: lowered universe of {scc_a:?} to {scc_universe_min:?} \
468 because {scc_a:?}: {scc_b:?} and {scc_b:?} is in universe {scc_universe_b:?}",
471 scc_universe_min
= scc_universe_min
,
472 scc_universe_b
= scc_universe_b
478 debug
!("compute_scc_universes: scc_universe = {:#?}", scc_universes
);
483 /// For each SCC, we compute a unique `RegionVid` (in fact, the
484 /// minimal one that belongs to the SCC). See
485 /// `scc_representatives` field of `RegionInferenceContext` for
487 fn compute_scc_representatives(
488 constraints_scc
: &Sccs
<RegionVid
, ConstraintSccIndex
>,
489 definitions
: &IndexSlice
<RegionVid
, RegionDefinition
<'tcx
>>,
490 ) -> IndexVec
<ConstraintSccIndex
, ty
::RegionVid
> {
491 let num_sccs
= constraints_scc
.num_sccs();
492 let next_region_vid
= definitions
.next_index();
493 let mut scc_representatives
= IndexVec
::from_elem_n(next_region_vid
, num_sccs
);
495 for region_vid
in definitions
.indices() {
496 let scc
= constraints_scc
.scc(region_vid
);
497 let prev_min
= scc_representatives
[scc
];
498 scc_representatives
[scc
] = region_vid
.min(prev_min
);
504 /// Initializes the region variables for each universally
505 /// quantified region (lifetime parameter). The first N variables
506 /// always correspond to the regions appearing in the function
507 /// signature (both named and anonymous) and where-clauses. This
508 /// function iterates over those regions and initializes them with
513 /// fn foo<'a, 'b>( /* ... */ ) where 'a: 'b { /* ... */ }
515 /// would initialize two variables like so:
516 /// ```ignore (illustrative)
517 /// R0 = { CFG, R0 } // 'a
518 /// R1 = { CFG, R0, R1 } // 'b
520 /// Here, R0 represents `'a`, and it contains (a) the entire CFG
521 /// and (b) any universally quantified regions that it outlives,
522 /// which in this case is just itself. R1 (`'b`) in contrast also
523 /// outlives `'a` and hence contains R0 and R1.
524 fn init_free_and_bound_regions(&mut self) {
525 // Update the names (if any)
526 // This iterator has unstable order but we collect it all into an IndexVec
527 for (external_name
, variable
) in self.universal_regions
.named_universal_regions() {
529 "init_universal_regions: region {:?} has external name {:?}",
530 variable
, external_name
532 self.definitions
[variable
].external_name
= Some(external_name
);
535 for variable
in self.definitions
.indices() {
536 let scc
= self.constraint_sccs
.scc(variable
);
538 match self.definitions
[variable
].origin
{
539 NllRegionVariableOrigin
::FreeRegion
=> {
540 // For each free, universally quantified region X:
542 // Add all nodes in the CFG to liveness constraints
543 self.liveness_constraints
.add_all_points(variable
);
544 self.scc_values
.add_all_points(scc
);
546 // Add `end(X)` into the set for X.
547 self.scc_values
.add_element(scc
, variable
);
550 NllRegionVariableOrigin
::Placeholder(placeholder
) => {
551 // Each placeholder region is only visible from
552 // its universe `ui` and its extensions. So we
553 // can't just add it into `scc` unless the
554 // universe of the scc can name this region.
555 let scc_universe
= self.scc_universes
[scc
];
556 if scc_universe
.can_name(placeholder
.universe
) {
557 self.scc_values
.add_element(scc
, placeholder
);
560 "init_free_and_bound_regions: placeholder {:?} is \
561 not compatible with universe {:?} of its SCC {:?}",
562 placeholder
, scc_universe
, scc
,
564 self.add_incompatible_universe(scc
);
568 NllRegionVariableOrigin
::Existential { .. }
=> {
569 // For existential, regions, nothing to do.
575 /// Returns an iterator over all the region indices.
576 pub fn regions(&self) -> impl Iterator
<Item
= RegionVid
> + 'tcx
{
577 self.definitions
.indices()
580 /// Given a universal region in scope on the MIR, returns the
581 /// corresponding index.
583 /// (Panics if `r` is not a registered universal region.)
584 pub fn to_region_vid(&self, r
: ty
::Region
<'tcx
>) -> RegionVid
{
585 self.universal_regions
.to_region_vid(r
)
588 /// Returns an iterator over all the outlives constraints.
589 pub fn outlives_constraints(&self) -> impl Iterator
<Item
= OutlivesConstraint
<'tcx
>> + '_
{
590 self.constraints
.outlives().iter().copied()
593 /// Adds annotations for `#[rustc_regions]`; see `UniversalRegions::annotate`.
594 pub(crate) fn annotate(&self, tcx
: TyCtxt
<'tcx
>, err
: &mut Diagnostic
) {
595 self.universal_regions
.annotate(tcx
, err
)
598 /// Returns `true` if the region `r` contains the point `p`.
600 /// Panics if called before `solve()` executes,
601 pub(crate) fn region_contains(&self, r
: RegionVid
, p
: impl ToElementIndex
) -> bool
{
602 let scc
= self.constraint_sccs
.scc(r
);
603 self.scc_values
.contains(scc
, p
)
606 /// Returns the lowest statement index in `start..=end` which is not contained by `r`.
608 /// Panics if called before `solve()` executes.
609 pub(crate) fn first_non_contained_inclusive(
616 let scc
= self.constraint_sccs
.scc(r
);
617 self.scc_values
.first_non_contained_inclusive(scc
, block
, start
, end
)
620 /// Returns access to the value of `r` for debugging purposes.
621 pub(crate) fn region_value_str(&self, r
: RegionVid
) -> String
{
622 let scc
= self.constraint_sccs
.scc(r
);
623 self.scc_values
.region_value_str(scc
)
626 pub(crate) fn placeholders_contained_in
<'a
>(
629 ) -> impl Iterator
<Item
= ty
::PlaceholderRegion
> + 'a
{
630 let scc
= self.constraint_sccs
.scc(r
);
631 self.scc_values
.placeholders_contained_in(scc
)
634 /// Returns access to the value of `r` for debugging purposes.
635 pub(crate) fn region_universe(&self, r
: RegionVid
) -> ty
::UniverseIndex
{
636 let scc
= self.constraint_sccs
.scc(r
);
637 self.scc_universes
[scc
]
640 /// Once region solving has completed, this function will return
641 /// the member constraints that were applied to the value of a given
642 /// region `r`. See `AppliedMemberConstraint`.
643 pub(crate) fn applied_member_constraints(&self, r
: RegionVid
) -> &[AppliedMemberConstraint
] {
644 let scc
= self.constraint_sccs
.scc(r
);
645 binary_search_util
::binary_search_slice(
646 &self.member_constraints_applied
,
647 |applied
| applied
.member_region_scc
,
652 /// Performs region inference and report errors if we see any
653 /// unsatisfiable constraints. If this is a closure, returns the
654 /// region requirements to propagate to our creator, if any.
655 #[instrument(skip(self, infcx, body, polonius_output), level = "debug")]
658 infcx
: &InferCtxt
<'tcx
>,
659 param_env
: ty
::ParamEnv
<'tcx
>,
661 polonius_output
: Option
<Rc
<PoloniusOutput
>>,
662 ) -> (Option
<ClosureRegionRequirements
<'tcx
>>, RegionErrors
<'tcx
>) {
663 let mir_def_id
= body
.source
.def_id();
664 self.propagate_constraints(body
);
666 let mut errors_buffer
= RegionErrors
::new(infcx
.tcx
);
668 // If this is a closure, we can propagate unsatisfied
669 // `outlives_requirements` to our creator, so create a vector
670 // to store those. Otherwise, we'll pass in `None` to the
671 // functions below, which will trigger them to report errors
673 let mut outlives_requirements
= infcx
.tcx
.is_typeck_child(mir_def_id
).then(Vec
::new
);
675 self.check_type_tests(
679 outlives_requirements
.as_mut(),
683 // In Polonius mode, the errors about missing universal region relations are in the output
684 // and need to be emitted or propagated. Otherwise, we need to check whether the
685 // constraints were too strong, and if so, emit or propagate those errors.
686 if infcx
.tcx
.sess
.opts
.unstable_opts
.polonius
{
687 self.check_polonius_subset_errors(
688 outlives_requirements
.as_mut(),
690 polonius_output
.expect("Polonius output is unavailable despite `-Z polonius`"),
693 self.check_universal_regions(outlives_requirements
.as_mut(), &mut errors_buffer
);
696 if errors_buffer
.is_empty() {
697 self.check_member_constraints(infcx
, &mut errors_buffer
);
700 let outlives_requirements
= outlives_requirements
.unwrap_or_default();
702 if outlives_requirements
.is_empty() {
703 (None
, errors_buffer
)
705 let num_external_vids
= self.universal_regions
.num_global_and_external_regions();
707 Some(ClosureRegionRequirements { num_external_vids, outlives_requirements }
),
713 /// Propagate the region constraints: this will grow the values
714 /// for each region variable until all the constraints are
715 /// satisfied. Note that some values may grow **too** large to be
716 /// feasible, but we check this later.
717 #[instrument(skip(self, _body), level = "debug")]
718 fn propagate_constraints(&mut self, _body
: &Body
<'tcx
>) {
719 debug
!("constraints={:#?}", {
720 let mut constraints
: Vec
<_
> = self.outlives_constraints().collect();
721 constraints
.sort_by_key(|c
| (c
.sup
, c
.sub
));
724 .map(|c
| (c
, self.constraint_sccs
.scc(c
.sup
), self.constraint_sccs
.scc(c
.sub
)))
728 // To propagate constraints, we walk the DAG induced by the
729 // SCC. For each SCC, we visit its successors and compute
730 // their values, then we union all those values to get our
732 let constraint_sccs
= self.constraint_sccs
.clone();
733 for scc
in constraint_sccs
.all_sccs() {
734 self.compute_value_for_scc(scc
);
737 // Sort the applied member constraints so we can binary search
738 // through them later.
739 self.member_constraints_applied
.sort_by_key(|applied
| applied
.member_region_scc
);
742 /// Computes the value of the SCC `scc_a`, which has not yet been
743 /// computed, by unioning the values of its successors.
744 /// Assumes that all successors have been computed already
745 /// (which is assured by iterating over SCCs in dependency order).
746 #[instrument(skip(self), level = "debug")]
747 fn compute_value_for_scc(&mut self, scc_a
: ConstraintSccIndex
) {
748 let constraint_sccs
= self.constraint_sccs
.clone();
750 // Walk each SCC `B` such that `A: B`...
751 for &scc_b
in constraint_sccs
.successors(scc_a
) {
754 // ...and add elements from `B` into `A`. One complication
755 // arises because of universes: If `B` contains something
756 // that `A` cannot name, then `A` can only contain `B` if
757 // it outlives static.
758 if self.universe_compatible(scc_b
, scc_a
) {
759 // `A` can name everything that is in `B`, so just
761 self.scc_values
.add_region(scc_a
, scc_b
);
763 self.add_incompatible_universe(scc_a
);
767 // Now take member constraints into account.
768 let member_constraints
= self.member_constraints
.clone();
769 for m_c_i
in member_constraints
.indices(scc_a
) {
770 self.apply_member_constraint(scc_a
, m_c_i
, member_constraints
.choice_regions(m_c_i
));
773 debug
!(value
= ?
self.scc_values
.region_value_str(scc_a
));
776 /// Invoked for each `R0 member of [R1..Rn]` constraint.
778 /// `scc` is the SCC containing R0, and `choice_regions` are the
779 /// `R1..Rn` regions -- they are always known to be universal
780 /// regions (and if that's not true, we just don't attempt to
781 /// enforce the constraint).
783 /// The current value of `scc` at the time the method is invoked
784 /// is considered a *lower bound*. If possible, we will modify
785 /// the constraint to set it equal to one of the option regions.
786 /// If we make any changes, returns true, else false.
788 /// This function only adds the member constraints to the region graph,
789 /// it does not check them. They are later checked in
790 /// `check_member_constraints` after the region graph has been computed.
791 #[instrument(skip(self, member_constraint_index), level = "debug")]
792 fn apply_member_constraint(
794 scc
: ConstraintSccIndex
,
795 member_constraint_index
: NllMemberConstraintIndex
,
796 choice_regions
: &[ty
::RegionVid
],
798 // Lazily compute the reverse graph, we'll need it later.
799 self.compute_reverse_scc_graph();
801 // Create a mutable vector of the options. We'll try to winnow
803 let mut choice_regions
: Vec
<ty
::RegionVid
> = choice_regions
.to_vec();
805 // Convert to the SCC representative: sometimes we have inference
806 // variables in the member constraint that wind up equated with
807 // universal regions. The scc representative is the minimal numbered
808 // one from the corresponding scc so it will be the universal region
810 for c_r
in &mut choice_regions
{
811 let scc
= self.constraint_sccs
.scc(*c_r
);
812 *c_r
= self.scc_representatives
[scc
];
815 // If the member region lives in a higher universe, we currently choose
816 // the most conservative option by leaving it unchanged.
817 if self.scc_universes
[scc
] != ty
::UniverseIndex
::ROOT
{
821 self.scc_values
.placeholders_contained_in(scc
).next().is_none(),
822 "scc {:?} in a member constraint has placeholder value: {:?}",
824 self.scc_values
.region_value_str(scc
),
827 // The existing value for `scc` is a lower-bound. This will
828 // consist of some set `{P} + {LB}` of points `{P}` and
829 // lower-bound free regions `{LB}`. As each choice region `O`
830 // is a free region, it will outlive the points. But we can
831 // only consider the option `O` if `O: LB`.
832 choice_regions
.retain(|&o_r
| {
834 .universal_regions_outlived_by(scc
)
835 .all(|lb
| self.universal_region_relations
.outlives(o_r
, lb
))
837 debug
!(?choice_regions
, "after lb");
839 // Now find all the *upper bounds* -- that is, each UB is a
840 // free region that must outlive the member region `R0` (`UB:
841 // R0`). Therefore, we need only keep an option `O` if `UB: O`
843 let universal_region_relations
= &self.universal_region_relations
;
844 for ub
in self.rev_scc_graph
.as_ref().unwrap().upper_bounds(scc
) {
846 choice_regions
.retain(|&o_r
| universal_region_relations
.outlives(ub
, o_r
));
848 debug
!(?choice_regions
, "after ub");
850 // At this point we can pick any member of `choice_regions`, but to avoid potential
851 // non-determinism we will pick the *unique minimum* choice.
853 // Because universal regions are only partially ordered (i.e, not every two regions are
854 // comparable), we will ignore any region that doesn't compare to all others when picking
855 // the minimum choice.
856 // For example, consider `choice_regions = ['static, 'a, 'b, 'c, 'd, 'e]`, where
857 // `'static: 'a, 'static: 'b, 'a: 'c, 'b: 'c, 'c: 'd, 'c: 'e`.
858 // `['d, 'e]` are ignored because they do not compare - the same goes for `['a, 'b]`.
859 let totally_ordered_subset
= choice_regions
.iter().copied().filter(|&r1
| {
860 choice_regions
.iter().all(|&r2
| {
861 self.universal_region_relations
.outlives(r1
, r2
)
862 || self.universal_region_relations
.outlives(r2
, r1
)
865 // Now we're left with `['static, 'c]`. Pick `'c` as the minimum!
866 let Some(min_choice
) = totally_ordered_subset
.reduce(|r1
, r2
| {
867 let r1_outlives_r2
= self.universal_region_relations
.outlives(r1
, r2
);
868 let r2_outlives_r1
= self.universal_region_relations
.outlives(r2
, r1
);
869 match (r1_outlives_r2
, r2_outlives_r1
) {
870 (true, true) => r1
.min(r2
),
873 (false, false) => bug
!("incomparable regions in total order"),
876 debug
!("no unique minimum choice");
880 let min_choice_scc
= self.constraint_sccs
.scc(min_choice
);
881 debug
!(?min_choice
, ?min_choice_scc
);
882 if self.scc_values
.add_region(scc
, min_choice_scc
) {
883 self.member_constraints_applied
.push(AppliedMemberConstraint
{
884 member_region_scc
: scc
,
886 member_constraint_index
,
891 /// Returns `true` if all the elements in the value of `scc_b` are nameable
892 /// in `scc_a`. Used during constraint propagation, and only once
893 /// the value of `scc_b` has been computed.
894 fn universe_compatible(&self, scc_b
: ConstraintSccIndex
, scc_a
: ConstraintSccIndex
) -> bool
{
895 let universe_a
= self.scc_universes
[scc_a
];
897 // Quick check: if scc_b's declared universe is a subset of
898 // scc_a's declared universe (typically, both are ROOT), then
899 // it cannot contain any problematic universe elements.
900 if universe_a
.can_name(self.scc_universes
[scc_b
]) {
904 // Otherwise, we have to iterate over the universe elements in
905 // B's value, and check whether all of them are nameable
907 self.scc_values
.placeholders_contained_in(scc_b
).all(|p
| universe_a
.can_name(p
.universe
))
910 /// Extend `scc` so that it can outlive some placeholder region
911 /// from a universe it can't name; at present, the only way for
912 /// this to be true is if `scc` outlives `'static`. This is
913 /// actually stricter than necessary: ideally, we'd support bounds
914 /// like `for<'a: 'b>` that might then allow us to approximate
915 /// `'a` with `'b` and not `'static`. But it will have to do for
917 fn add_incompatible_universe(&mut self, scc
: ConstraintSccIndex
) {
918 debug
!("add_incompatible_universe(scc={:?})", scc
);
920 let fr_static
= self.universal_regions
.fr_static
;
921 self.scc_values
.add_all_points(scc
);
922 self.scc_values
.add_element(scc
, fr_static
);
925 /// Once regions have been propagated, this method is used to see
926 /// whether the "type tests" produced by typeck were satisfied;
927 /// type tests encode type-outlives relationships like `T:
928 /// 'a`. See `TypeTest` for more details.
931 infcx
: &InferCtxt
<'tcx
>,
932 param_env
: ty
::ParamEnv
<'tcx
>,
934 mut propagated_outlives_requirements
: Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
935 errors_buffer
: &mut RegionErrors
<'tcx
>,
939 // Sometimes we register equivalent type-tests that would
940 // result in basically the exact same error being reported to
941 // the user. Avoid that.
942 let mut deduplicate_errors
= FxIndexSet
::default();
944 for type_test
in &self.type_tests
{
945 debug
!("check_type_test: {:?}", type_test
);
947 let generic_ty
= type_test
.generic_kind
.to_ty(tcx
);
948 if self.eval_verify_bound(
952 type_test
.lower_bound
,
953 &type_test
.verify_bound
,
958 if let Some(propagated_outlives_requirements
) = &mut propagated_outlives_requirements
{
959 if self.try_promote_type_test(
964 propagated_outlives_requirements
,
970 // Type-test failed. Report the error.
971 let erased_generic_kind
= infcx
.tcx
.erase_regions(type_test
.generic_kind
);
973 // Skip duplicate-ish errors.
974 if deduplicate_errors
.insert((
976 type_test
.lower_bound
,
980 "check_type_test: reporting error for erased_generic_kind={:?}, \
981 lower_bound_region={:?}, \
982 type_test.span={:?}",
983 erased_generic_kind
, type_test
.lower_bound
, type_test
.span
,
986 errors_buffer
.push(RegionErrorKind
::TypeTestError { type_test: type_test.clone() }
);
991 /// Invoked when we have some type-test (e.g., `T: 'X`) that we cannot
992 /// prove to be satisfied. If this is a closure, we will attempt to
993 /// "promote" this type-test into our `ClosureRegionRequirements` and
994 /// hence pass it up the creator. To do this, we have to phrase the
995 /// type-test in terms of external free regions, as local free
996 /// regions are not nameable by the closure's creator.
998 /// Promotion works as follows: we first check that the type `T`
999 /// contains only regions that the creator knows about. If this is
1000 /// true, then -- as a consequence -- we know that all regions in
1001 /// the type `T` are free regions that outlive the closure body. If
1002 /// false, then promotion fails.
1004 /// Once we've promoted T, we have to "promote" `'X` to some region
1005 /// that is "external" to the closure. Generally speaking, a region
1006 /// may be the union of some points in the closure body as well as
1007 /// various free lifetimes. We can ignore the points in the closure
1008 /// body: if the type T can be expressed in terms of external regions,
1009 /// we know it outlives the points in the closure body. That
1010 /// just leaves the free regions.
1012 /// The idea then is to lower the `T: 'X` constraint into multiple
1013 /// bounds -- e.g., if `'X` is the union of two free lifetimes,
1014 /// `'1` and `'2`, then we would create `T: '1` and `T: '2`.
1015 #[instrument(level = "debug", skip(self, infcx, propagated_outlives_requirements))]
1016 fn try_promote_type_test(
1018 infcx
: &InferCtxt
<'tcx
>,
1019 param_env
: ty
::ParamEnv
<'tcx
>,
1021 type_test
: &TypeTest
<'tcx
>,
1022 propagated_outlives_requirements
: &mut Vec
<ClosureOutlivesRequirement
<'tcx
>>,
1024 let tcx
= infcx
.tcx
;
1026 let TypeTest { generic_kind, lower_bound, span: _, verify_bound: _ }
= type_test
;
1028 let generic_ty
= generic_kind
.to_ty(tcx
);
1029 let Some(subject
) = self.try_promote_type_test_subject(infcx
, generic_ty
) else {
1033 debug
!("subject = {:?}", subject
);
1035 let r_scc
= self.constraint_sccs
.scc(*lower_bound
);
1038 "lower_bound = {:?} r_scc={:?} universe={:?}",
1039 lower_bound
, r_scc
, self.scc_universes
[r_scc
]
1042 // If the type test requires that `T: 'a` where `'a` is a
1043 // placeholder from another universe, that effectively requires
1044 // `T: 'static`, so we have to propagate that requirement.
1046 // It doesn't matter *what* universe because the promoted `T` will
1047 // always be in the root universe.
1048 if let Some(p
) = self.scc_values
.placeholders_contained_in(r_scc
).next() {
1049 debug
!("encountered placeholder in higher universe: {:?}, requiring 'static", p
);
1050 let static_r
= self.universal_regions
.fr_static
;
1051 propagated_outlives_requirements
.push(ClosureOutlivesRequirement
{
1053 outlived_free_region
: static_r
,
1054 blame_span
: type_test
.span
,
1055 category
: ConstraintCategory
::Boring
,
1058 // we can return here -- the code below might push add'l constraints
1059 // but they would all be weaker than this one.
1063 // For each region outlived by lower_bound find a non-local,
1064 // universal region (it may be the same region) and add it to
1065 // `ClosureOutlivesRequirement`.
1066 for ur
in self.scc_values
.universal_regions_outlived_by(r_scc
) {
1067 debug
!("universal_region_outlived_by ur={:?}", ur
);
1068 // Check whether we can already prove that the "subject" outlives `ur`.
1069 // If so, we don't have to propagate this requirement to our caller.
1071 // To continue the example from the function, if we are trying to promote
1072 // a requirement that `T: 'X`, and we know that `'X = '1 + '2` (i.e., the union
1073 // `'1` and `'2`), then in this loop `ur` will be `'1` (and `'2`). So here
1074 // we check whether `T: '1` is something we *can* prove. If so, no need
1075 // to propagate that requirement.
1077 // This is needed because -- particularly in the case
1078 // where `ur` is a local bound -- we are sometimes in a
1079 // position to prove things that our caller cannot. See
1080 // #53570 for an example.
1081 if self.eval_verify_bound(infcx
, param_env
, generic_ty
, ur
, &type_test
.verify_bound
) {
1085 let non_local_ub
= self.universal_region_relations
.non_local_upper_bounds(ur
);
1086 debug
!("try_promote_type_test: non_local_ub={:?}", non_local_ub
);
1088 // This is slightly too conservative. To show T: '1, given `'2: '1`
1089 // and `'3: '1` we only need to prove that T: '2 *or* T: '3, but to
1090 // avoid potential non-determinism we approximate this by requiring
1092 for upper_bound
in non_local_ub
{
1093 debug_assert
!(self.universal_regions
.is_universal_region(upper_bound
));
1094 debug_assert
!(!self.universal_regions
.is_local_free_region(upper_bound
));
1096 let requirement
= ClosureOutlivesRequirement
{
1098 outlived_free_region
: upper_bound
,
1099 blame_span
: type_test
.span
,
1100 category
: ConstraintCategory
::Boring
,
1102 debug
!("try_promote_type_test: pushing {:#?}", requirement
);
1103 propagated_outlives_requirements
.push(requirement
);
1109 /// When we promote a type test `T: 'r`, we have to replace all region
1110 /// variables in the type `T` with an equal universal region from the
1111 /// closure signature.
1112 /// This is not always possible, so this is a fallible process.
1113 #[instrument(level = "debug", skip(self, infcx))]
1114 fn try_promote_type_test_subject(
1116 infcx
: &InferCtxt
<'tcx
>,
1118 ) -> Option
<ClosureOutlivesSubject
<'tcx
>> {
1119 let tcx
= infcx
.tcx
;
1121 // Opaque types' args may include useless lifetimes.
1122 // We will replace them with ReStatic.
1123 struct OpaqueFolder
<'tcx
> {
1126 impl<'tcx
> ty
::TypeFolder
<TyCtxt
<'tcx
>> for OpaqueFolder
<'tcx
> {
1127 fn interner(&self) -> TyCtxt
<'tcx
> {
1130 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
1131 use ty
::TypeSuperFoldable
as _
;
1133 let &ty
::Alias(ty
::Opaque
, ty
::AliasTy { args, def_id, .. }
) = t
.kind() else {
1134 return t
.super_fold_with(self);
1136 let args
= std
::iter
::zip(args
, tcx
.variances_of(def_id
)).map(|(arg
, v
)| {
1137 match (arg
.unpack(), v
) {
1138 (ty
::GenericArgKind
::Lifetime(_
), ty
::Bivariant
) => {
1139 tcx
.lifetimes
.re_static
.into()
1141 _
=> arg
.fold_with(self),
1144 Ty
::new_opaque(tcx
, def_id
, tcx
.mk_args_from_iter(args
))
1148 let ty
= ty
.fold_with(&mut OpaqueFolder { tcx }
);
1150 let ty
= tcx
.fold_regions(ty
, |r
, _depth
| {
1151 let r_vid
= self.to_region_vid(r
);
1152 let r_scc
= self.constraint_sccs
.scc(r_vid
);
1154 // The challenge is this. We have some region variable `r`
1155 // whose value is a set of CFG points and universal
1156 // regions. We want to find if that set is *equivalent* to
1157 // any of the named regions found in the closure.
1158 // To do so, we simply check every candidate `u_r` for equality.
1160 .universal_regions_outlived_by(r_scc
)
1161 .filter(|&u_r
| !self.universal_regions
.is_local_free_region(u_r
))
1162 .find(|&u_r
| self.eval_equal(u_r
, r_vid
))
1163 .map(|u_r
| ty
::Region
::new_var(tcx
, u_r
))
1164 // In the case of a failure, use `ReErased`. We will eventually
1165 // return `None` in this case.
1166 .unwrap_or(tcx
.lifetimes
.re_erased
)
1169 debug
!("try_promote_type_test_subject: folded ty = {:?}", ty
);
1171 // This will be true if we failed to promote some region.
1172 if ty
.has_erased_regions() {
1176 Some(ClosureOutlivesSubject
::Ty(ClosureOutlivesSubjectTy
::bind(tcx
, ty
)))
1179 /// Returns a universally quantified region that outlives the
1180 /// value of `r` (`r` may be existentially or universally
1183 /// Since `r` is (potentially) an existential region, it has some
1184 /// value which may include (a) any number of points in the CFG
1185 /// and (b) any number of `end('x)` elements of universally
1186 /// quantified regions. To convert this into a single universal
1187 /// region we do as follows:
1189 /// - Ignore the CFG points in `'r`. All universally quantified regions
1190 /// include the CFG anyhow.
1191 /// - For each `end('x)` element in `'r`, compute the mutual LUB, yielding
1193 #[instrument(skip(self), level = "debug", ret)]
1194 pub(crate) fn universal_upper_bound(&self, r
: RegionVid
) -> RegionVid
{
1195 debug
!(r
= %self.region_value_str(r
));
1197 // Find the smallest universal region that contains all other
1198 // universal regions within `region`.
1199 let mut lub
= self.universal_regions
.fr_fn_body
;
1200 let r_scc
= self.constraint_sccs
.scc(r
);
1201 for ur
in self.scc_values
.universal_regions_outlived_by(r_scc
) {
1202 lub
= self.universal_region_relations
.postdom_upper_bound(lub
, ur
);
1208 /// Like `universal_upper_bound`, but returns an approximation more suitable
1209 /// for diagnostics. If `r` contains multiple disjoint universal regions
1210 /// (e.g. 'a and 'b in `fn foo<'a, 'b> { ... }`, we pick the lower-numbered region.
1211 /// This corresponds to picking named regions over unnamed regions
1212 /// (e.g. picking early-bound regions over a closure late-bound region).
1214 /// This means that the returned value may not be a true upper bound, since
1215 /// only 'static is known to outlive disjoint universal regions.
1216 /// Therefore, this method should only be used in diagnostic code,
1217 /// where displaying *some* named universal region is better than
1218 /// falling back to 'static.
1219 #[instrument(level = "debug", skip(self))]
1220 pub(crate) fn approx_universal_upper_bound(&self, r
: RegionVid
) -> RegionVid
{
1221 debug
!("{}", self.region_value_str(r
));
1223 // Find the smallest universal region that contains all other
1224 // universal regions within `region`.
1225 let mut lub
= self.universal_regions
.fr_fn_body
;
1226 let r_scc
= self.constraint_sccs
.scc(r
);
1227 let static_r
= self.universal_regions
.fr_static
;
1228 for ur
in self.scc_values
.universal_regions_outlived_by(r_scc
) {
1229 let new_lub
= self.universal_region_relations
.postdom_upper_bound(lub
, ur
);
1230 debug
!(?ur
, ?lub
, ?new_lub
);
1231 // The upper bound of two non-static regions is static: this
1232 // means we know nothing about the relationship between these
1233 // two regions. Pick a 'better' one to use when constructing
1235 if ur
!= static_r
&& lub
!= static_r
&& new_lub
== static_r
{
1236 // Prefer the region with an `external_name` - this
1237 // indicates that the region is early-bound, so working with
1238 // it can produce a nicer error.
1239 if self.region_definition(ur
).external_name
.is_some() {
1241 } else if self.region_definition(lub
).external_name
.is_some() {
1242 // Leave lub unchanged
1244 // If we get here, we don't have any reason to prefer
1245 // one region over the other. Just pick the
1246 // one with the lower index for now.
1247 lub
= std
::cmp
::min(ur
, lub
);
1259 /// Tests if `test` is true when applied to `lower_bound` at
1261 fn eval_verify_bound(
1263 infcx
: &InferCtxt
<'tcx
>,
1264 param_env
: ty
::ParamEnv
<'tcx
>,
1265 generic_ty
: Ty
<'tcx
>,
1266 lower_bound
: RegionVid
,
1267 verify_bound
: &VerifyBound
<'tcx
>,
1269 debug
!("eval_verify_bound(lower_bound={:?}, verify_bound={:?})", lower_bound
, verify_bound
);
1271 match verify_bound
{
1272 VerifyBound
::IfEq(verify_if_eq_b
) => {
1273 self.eval_if_eq(infcx
, param_env
, generic_ty
, lower_bound
, *verify_if_eq_b
)
1276 VerifyBound
::IsEmpty
=> {
1277 let lower_bound_scc
= self.constraint_sccs
.scc(lower_bound
);
1278 self.scc_values
.elements_contained_in(lower_bound_scc
).next().is_none()
1281 VerifyBound
::OutlivedBy(r
) => {
1282 let r_vid
= self.to_region_vid(*r
);
1283 self.eval_outlives(r_vid
, lower_bound
)
1286 VerifyBound
::AnyBound(verify_bounds
) => verify_bounds
.iter().any(|verify_bound
| {
1287 self.eval_verify_bound(infcx
, param_env
, generic_ty
, lower_bound
, verify_bound
)
1290 VerifyBound
::AllBounds(verify_bounds
) => verify_bounds
.iter().all(|verify_bound
| {
1291 self.eval_verify_bound(infcx
, param_env
, generic_ty
, lower_bound
, verify_bound
)
1298 infcx
: &InferCtxt
<'tcx
>,
1299 param_env
: ty
::ParamEnv
<'tcx
>,
1300 generic_ty
: Ty
<'tcx
>,
1301 lower_bound
: RegionVid
,
1302 verify_if_eq_b
: ty
::Binder
<'tcx
, VerifyIfEq
<'tcx
>>,
1304 let generic_ty
= self.normalize_to_scc_representatives(infcx
.tcx
, generic_ty
);
1305 let verify_if_eq_b
= self.normalize_to_scc_representatives(infcx
.tcx
, verify_if_eq_b
);
1306 match test_type_match
::extract_verify_if_eq(
1313 let r_vid
= self.to_region_vid(r
);
1314 self.eval_outlives(r_vid
, lower_bound
)
1320 /// This is a conservative normalization procedure. It takes every
1321 /// free region in `value` and replaces it with the
1322 /// "representative" of its SCC (see `scc_representatives` field).
1323 /// We are guaranteed that if two values normalize to the same
1324 /// thing, then they are equal; this is a conservative check in
1325 /// that they could still be equal even if they normalize to
1326 /// different results. (For example, there might be two regions
1327 /// with the same value that are not in the same SCC).
1329 /// N.B., this is not an ideal approach and I would like to revisit
1330 /// it. However, it works pretty well in practice. In particular,
1331 /// this is needed to deal with projection outlives bounds like
1334 /// <T as Foo<'0>>::Item: '1
1337 /// In particular, this routine winds up being important when
1338 /// there are bounds like `where <T as Foo<'a>>::Item: 'b` in the
1339 /// environment. In this case, if we can show that `'0 == 'a`,
1340 /// and that `'b: '1`, then we know that the clause is
1341 /// satisfied. In such cases, particularly due to limitations of
1342 /// the trait solver =), we usually wind up with a where-clause like
1343 /// `T: Foo<'a>` in scope, which thus forces `'0 == 'a` to be added as
1344 /// a constraint, and thus ensures that they are in the same SCC.
1346 /// So why can't we do a more correct routine? Well, we could
1347 /// *almost* use the `relate_tys` code, but the way it is
1348 /// currently setup it creates inference variables to deal with
1349 /// higher-ranked things and so forth, and right now the inference
1350 /// context is not permitted to make more inference variables. So
1351 /// we use this kind of hacky solution.
1352 fn normalize_to_scc_representatives
<T
>(&self, tcx
: TyCtxt
<'tcx
>, value
: T
) -> T
1354 T
: TypeFoldable
<TyCtxt
<'tcx
>>,
1356 tcx
.fold_regions(value
, |r
, _db
| {
1357 let vid
= self.to_region_vid(r
);
1358 let scc
= self.constraint_sccs
.scc(vid
);
1359 let repr
= self.scc_representatives
[scc
];
1360 ty
::Region
::new_var(tcx
, repr
)
1364 // Evaluate whether `sup_region == sub_region`.
1365 fn eval_equal(&self, r1
: RegionVid
, r2
: RegionVid
) -> bool
{
1366 self.eval_outlives(r1
, r2
) && self.eval_outlives(r2
, r1
)
1369 // Evaluate whether `sup_region: sub_region`.
1370 #[instrument(skip(self), level = "debug", ret)]
1371 fn eval_outlives(&self, sup_region
: RegionVid
, sub_region
: RegionVid
) -> bool
{
1373 "sup_region's value = {:?} universal={:?}",
1374 self.region_value_str(sup_region
),
1375 self.universal_regions
.is_universal_region(sup_region
),
1378 "sub_region's value = {:?} universal={:?}",
1379 self.region_value_str(sub_region
),
1380 self.universal_regions
.is_universal_region(sub_region
),
1383 let sub_region_scc
= self.constraint_sccs
.scc(sub_region
);
1384 let sup_region_scc
= self.constraint_sccs
.scc(sup_region
);
1386 // If we are checking that `'sup: 'sub`, and `'sub` contains
1387 // some placeholder that `'sup` cannot name, then this is only
1388 // true if `'sup` outlives static.
1389 if !self.universe_compatible(sub_region_scc
, sup_region_scc
) {
1391 "sub universe `{sub_region_scc:?}` is not nameable \
1392 by super `{sup_region_scc:?}`, promoting to static",
1395 return self.eval_outlives(sup_region
, self.universal_regions
.fr_static
);
1398 // Both the `sub_region` and `sup_region` consist of the union
1399 // of some number of universal regions (along with the union
1400 // of various points in the CFG; ignore those points for
1401 // now). Therefore, the sup-region outlives the sub-region if,
1402 // for each universal region R1 in the sub-region, there
1403 // exists some region R2 in the sup-region that outlives R1.
1404 let universal_outlives
=
1405 self.scc_values
.universal_regions_outlived_by(sub_region_scc
).all(|r1
| {
1407 .universal_regions_outlived_by(sup_region_scc
)
1408 .any(|r2
| self.universal_region_relations
.outlives(r2
, r1
))
1411 if !universal_outlives
{
1412 debug
!("sub region contains a universal region not present in super");
1416 // Now we have to compare all the points in the sub region and make
1417 // sure they exist in the sup region.
1419 if self.universal_regions
.is_universal_region(sup_region
) {
1420 // Micro-opt: universal regions contain all points.
1421 debug
!("super is universal and hence contains all points");
1425 debug
!("comparison between points in sup/sub");
1427 self.scc_values
.contains_points(sup_region_scc
, sub_region_scc
)
1430 /// Once regions have been propagated, this method is used to see
1431 /// whether any of the constraints were too strong. In particular,
1432 /// we want to check for a case where a universally quantified
1433 /// region exceeded its bounds. Consider:
1435 /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
1437 /// In this case, returning `x` requires `&'a u32 <: &'b u32`
1438 /// and hence we establish (transitively) a constraint that
1439 /// `'a: 'b`. The `propagate_constraints` code above will
1440 /// therefore add `end('a)` into the region for `'b` -- but we
1441 /// have no evidence that `'b` outlives `'a`, so we want to report
1444 /// If `propagated_outlives_requirements` is `Some`, then we will
1445 /// push unsatisfied obligations into there. Otherwise, we'll
1446 /// report them as errors.
1447 fn check_universal_regions(
1449 mut propagated_outlives_requirements
: Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
1450 errors_buffer
: &mut RegionErrors
<'tcx
>,
1452 for (fr
, fr_definition
) in self.definitions
.iter_enumerated() {
1453 match fr_definition
.origin
{
1454 NllRegionVariableOrigin
::FreeRegion
=> {
1455 // Go through each of the universal regions `fr` and check that
1456 // they did not grow too large, accumulating any requirements
1457 // for our caller into the `outlives_requirements` vector.
1458 self.check_universal_region(
1460 &mut propagated_outlives_requirements
,
1465 NllRegionVariableOrigin
::Placeholder(placeholder
) => {
1466 self.check_bound_universal_region(fr
, placeholder
, errors_buffer
);
1469 NllRegionVariableOrigin
::Existential { .. }
=> {
1470 // nothing to check here
1476 /// Checks if Polonius has found any unexpected free region relations.
1478 /// In Polonius terms, a "subset error" (or "illegal subset relation error") is the equivalent
1479 /// of NLL's "checking if any region constraints were too strong": a placeholder origin `'a`
1480 /// was unexpectedly found to be a subset of another placeholder origin `'b`, and means in NLL
1481 /// terms that the "longer free region" `'a` outlived the "shorter free region" `'b`.
1483 /// More details can be found in this blog post by Niko:
1484 /// <https://smallcultfollowing.com/babysteps/blog/2019/01/17/polonius-and-region-errors/>
1486 /// In the canonical example
1488 /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
1490 /// returning `x` requires `&'a u32 <: &'b u32` and hence we establish (transitively) a
1491 /// constraint that `'a: 'b`. It is an error that we have no evidence that this
1492 /// constraint holds.
1494 /// If `propagated_outlives_requirements` is `Some`, then we will
1495 /// push unsatisfied obligations into there. Otherwise, we'll
1496 /// report them as errors.
1497 fn check_polonius_subset_errors(
1499 mut propagated_outlives_requirements
: Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
1500 errors_buffer
: &mut RegionErrors
<'tcx
>,
1501 polonius_output
: Rc
<PoloniusOutput
>,
1504 "check_polonius_subset_errors: {} subset_errors",
1505 polonius_output
.subset_errors
.len()
1508 // Similarly to `check_universal_regions`: a free region relation, which was not explicitly
1509 // declared ("known") was found by Polonius, so emit an error, or propagate the
1510 // requirements for our caller into the `propagated_outlives_requirements` vector.
1512 // Polonius doesn't model regions ("origins") as CFG-subsets or durations, but the
1513 // `longer_fr` and `shorter_fr` terminology will still be used here, for consistency with
1514 // the rest of the NLL infrastructure. The "subset origin" is the "longer free region",
1515 // and the "superset origin" is the outlived "shorter free region".
1517 // Note: Polonius will produce a subset error at every point where the unexpected
1518 // `longer_fr`'s "placeholder loan" is contained in the `shorter_fr`. This can be helpful
1519 // for diagnostics in the future, e.g. to point more precisely at the key locations
1520 // requiring this constraint to hold. However, the error and diagnostics code downstream
1521 // expects that these errors are not duplicated (and that they are in a certain order).
1522 // Otherwise, diagnostics messages such as the ones giving names like `'1` to elided or
1523 // anonymous lifetimes for example, could give these names differently, while others like
1524 // the outlives suggestions or the debug output from `#[rustc_regions]` would be
1525 // duplicated. The polonius subset errors are deduplicated here, while keeping the
1526 // CFG-location ordering.
1527 // We can iterate the HashMap here because the result is sorted afterwards.
1528 #[allow(rustc::potential_query_instability)]
1529 let mut subset_errors
: Vec
<_
> = polonius_output
1532 .flat_map(|(_location
, subset_errors
)| subset_errors
.iter())
1534 subset_errors
.sort();
1535 subset_errors
.dedup();
1537 for (longer_fr
, shorter_fr
) in subset_errors
.into_iter() {
1539 "check_polonius_subset_errors: subset_error longer_fr={:?},\
1541 longer_fr
, shorter_fr
1544 let propagated
= self.try_propagate_universal_region_error(
1547 &mut propagated_outlives_requirements
,
1549 if propagated
== RegionRelationCheckResult
::Error
{
1550 errors_buffer
.push(RegionErrorKind
::RegionError
{
1551 longer_fr
: *longer_fr
,
1552 shorter_fr
: *shorter_fr
,
1553 fr_origin
: NllRegionVariableOrigin
::FreeRegion
,
1559 // Handle the placeholder errors as usual, until the chalk-rustc-polonius triumvirate has
1560 // a more complete picture on how to separate this responsibility.
1561 for (fr
, fr_definition
) in self.definitions
.iter_enumerated() {
1562 match fr_definition
.origin
{
1563 NllRegionVariableOrigin
::FreeRegion
=> {
1564 // handled by polonius above
1567 NllRegionVariableOrigin
::Placeholder(placeholder
) => {
1568 self.check_bound_universal_region(fr
, placeholder
, errors_buffer
);
1571 NllRegionVariableOrigin
::Existential { .. }
=> {
1572 // nothing to check here
1578 /// Checks the final value for the free region `fr` to see if it
1579 /// grew too large. In particular, examine what `end(X)` points
1580 /// wound up in `fr`'s final value; for each `end(X)` where `X !=
1581 /// fr`, we want to check that `fr: X`. If not, that's either an
1582 /// error, or something we have to propagate to our creator.
1584 /// Things that are to be propagated are accumulated into the
1585 /// `outlives_requirements` vector.
1586 #[instrument(skip(self, propagated_outlives_requirements, errors_buffer), level = "debug")]
1587 fn check_universal_region(
1589 longer_fr
: RegionVid
,
1590 propagated_outlives_requirements
: &mut Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
1591 errors_buffer
: &mut RegionErrors
<'tcx
>,
1593 let longer_fr_scc
= self.constraint_sccs
.scc(longer_fr
);
1595 // Because this free region must be in the ROOT universe, we
1596 // know it cannot contain any bound universes.
1597 assert
!(self.scc_universes
[longer_fr_scc
] == ty
::UniverseIndex
::ROOT
);
1598 debug_assert
!(self.scc_values
.placeholders_contained_in(longer_fr_scc
).next().is_none());
1600 // Only check all of the relations for the main representative of each
1601 // SCC, otherwise just check that we outlive said representative. This
1602 // reduces the number of redundant relations propagated out of
1604 // Note that the representative will be a universal region if there is
1605 // one in this SCC, so we will always check the representative here.
1606 let representative
= self.scc_representatives
[longer_fr_scc
];
1607 if representative
!= longer_fr
{
1608 if let RegionRelationCheckResult
::Error
= self.check_universal_region_relation(
1611 propagated_outlives_requirements
,
1613 errors_buffer
.push(RegionErrorKind
::RegionError
{
1615 shorter_fr
: representative
,
1616 fr_origin
: NllRegionVariableOrigin
::FreeRegion
,
1623 // Find every region `o` such that `fr: o`
1624 // (because `fr` includes `end(o)`).
1625 let mut error_reported
= false;
1626 for shorter_fr
in self.scc_values
.universal_regions_outlived_by(longer_fr_scc
) {
1627 if let RegionRelationCheckResult
::Error
= self.check_universal_region_relation(
1630 propagated_outlives_requirements
,
1632 // We only report the first region error. Subsequent errors are hidden so as
1633 // not to overwhelm the user, but we do record them so as to potentially print
1634 // better diagnostics elsewhere...
1635 errors_buffer
.push(RegionErrorKind
::RegionError
{
1638 fr_origin
: NllRegionVariableOrigin
::FreeRegion
,
1639 is_reported
: !error_reported
,
1642 error_reported
= true;
1647 /// Checks that we can prove that `longer_fr: shorter_fr`. If we can't we attempt to propagate
1648 /// the constraint outward (e.g. to a closure environment), but if that fails, there is an
1650 fn check_universal_region_relation(
1652 longer_fr
: RegionVid
,
1653 shorter_fr
: RegionVid
,
1654 propagated_outlives_requirements
: &mut Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
1655 ) -> RegionRelationCheckResult
{
1656 // If it is known that `fr: o`, carry on.
1657 if self.universal_region_relations
.outlives(longer_fr
, shorter_fr
) {
1658 RegionRelationCheckResult
::Ok
1660 // If we are not in a context where we can't propagate errors, or we
1661 // could not shrink `fr` to something smaller, then just report an
1664 // Note: in this case, we use the unapproximated regions to report the
1665 // error. This gives better error messages in some cases.
1666 self.try_propagate_universal_region_error(
1669 propagated_outlives_requirements
,
1674 /// Attempt to propagate a region error (e.g. `'a: 'b`) that is not met to a closure's
1675 /// creator. If we cannot, then the caller should report an error to the user.
1676 fn try_propagate_universal_region_error(
1678 longer_fr
: RegionVid
,
1679 shorter_fr
: RegionVid
,
1680 propagated_outlives_requirements
: &mut Option
<&mut Vec
<ClosureOutlivesRequirement
<'tcx
>>>,
1681 ) -> RegionRelationCheckResult
{
1682 if let Some(propagated_outlives_requirements
) = propagated_outlives_requirements
{
1683 // Shrink `longer_fr` until we find a non-local region (if we do).
1684 // We'll call it `fr-` -- it's ever so slightly smaller than
1686 if let Some(fr_minus
) = self.universal_region_relations
.non_local_lower_bound(longer_fr
)
1688 debug
!("try_propagate_universal_region_error: fr_minus={:?}", fr_minus
);
1690 let blame_span_category
= self.find_outlives_blame_span(
1692 NllRegionVariableOrigin
::FreeRegion
,
1696 // Grow `shorter_fr` until we find some non-local regions. (We
1697 // always will.) We'll call them `shorter_fr+` -- they're ever
1698 // so slightly larger than `shorter_fr`.
1699 let shorter_fr_plus
=
1700 self.universal_region_relations
.non_local_upper_bounds(shorter_fr
);
1702 "try_propagate_universal_region_error: shorter_fr_plus={:?}",
1705 for fr
in shorter_fr_plus
{
1706 // Push the constraint `fr-: shorter_fr+`
1707 propagated_outlives_requirements
.push(ClosureOutlivesRequirement
{
1708 subject
: ClosureOutlivesSubject
::Region(fr_minus
),
1709 outlived_free_region
: fr
,
1710 blame_span
: blame_span_category
.1.span
,
1711 category
: blame_span_category
.0,
1714 return RegionRelationCheckResult
::Propagated
;
1718 RegionRelationCheckResult
::Error
1721 fn check_bound_universal_region(
1723 longer_fr
: RegionVid
,
1724 placeholder
: ty
::PlaceholderRegion
,
1725 errors_buffer
: &mut RegionErrors
<'tcx
>,
1727 debug
!("check_bound_universal_region(fr={:?}, placeholder={:?})", longer_fr
, placeholder
,);
1729 let longer_fr_scc
= self.constraint_sccs
.scc(longer_fr
);
1730 debug
!("check_bound_universal_region: longer_fr_scc={:?}", longer_fr_scc
,);
1732 for error_element
in self.scc_values
.elements_contained_in(longer_fr_scc
) {
1733 match error_element
{
1734 RegionElement
::Location(_
) | RegionElement
::RootUniversalRegion(_
) => {}
1735 // If we have some bound universal region `'a`, then the only
1736 // elements it can contain is itself -- we don't know anything
1738 RegionElement
::PlaceholderRegion(placeholder1
) => {
1739 if placeholder
== placeholder1
{
1745 errors_buffer
.push(RegionErrorKind
::BoundUniversalRegionError
{
1751 // Stop after the first error, it gets too noisy otherwise, and does not provide more information.
1754 debug
!("check_bound_universal_region: all bounds satisfied");
1757 #[instrument(level = "debug", skip(self, infcx, errors_buffer))]
1758 fn check_member_constraints(
1760 infcx
: &InferCtxt
<'tcx
>,
1761 errors_buffer
: &mut RegionErrors
<'tcx
>,
1763 let member_constraints
= self.member_constraints
.clone();
1764 for m_c_i
in member_constraints
.all_indices() {
1766 let m_c
= &member_constraints
[m_c_i
];
1767 let member_region_vid
= m_c
.member_region_vid
;
1770 value
= ?
self.region_value_str(member_region_vid
),
1772 let choice_regions
= member_constraints
.choice_regions(m_c_i
);
1773 debug
!(?choice_regions
);
1775 // Did the member region wind up equal to any of the option regions?
1777 choice_regions
.iter().find(|&&o_r
| self.eval_equal(o_r
, m_c
.member_region_vid
))
1779 debug
!("evaluated as equal to {:?}", o
);
1783 // If not, report an error.
1784 let member_region
= ty
::Region
::new_var(infcx
.tcx
, member_region_vid
);
1785 errors_buffer
.push(RegionErrorKind
::UnexpectedHiddenRegion
{
1786 span
: m_c
.definition_span
,
1787 hidden_ty
: m_c
.hidden_ty
,
1794 /// We have a constraint `fr1: fr2` that is not satisfied, where
1795 /// `fr2` represents some universal region. Here, `r` is some
1796 /// region where we know that `fr1: r` and this function has the
1797 /// job of determining whether `r` is "to blame" for the fact that
1798 /// `fr1: fr2` is required.
1800 /// This is true under two conditions:
1803 /// - `fr2` is `'static` and `r` is some placeholder in a universe
1804 /// that cannot be named by `fr1`; in that case, we will require
1805 /// that `fr1: 'static` because it is the only way to `fr1: r` to
1806 /// be satisfied. (See `add_incompatible_universe`.)
1807 pub(crate) fn provides_universal_region(
1813 debug
!("provides_universal_region(r={:?}, fr1={:?}, fr2={:?})", r
, fr1
, fr2
);
1816 fr2
== self.universal_regions
.fr_static
&& self.cannot_name_placeholder(fr1
, r
)
1819 debug
!("provides_universal_region: result = {:?}", result
);
1823 /// If `r2` represents a placeholder region, then this returns
1824 /// `true` if `r1` cannot name that placeholder in its
1825 /// value; otherwise, returns `false`.
1826 pub(crate) fn cannot_name_placeholder(&self, r1
: RegionVid
, r2
: RegionVid
) -> bool
{
1827 debug
!("cannot_name_value_of(r1={:?}, r2={:?})", r1
, r2
);
1829 match self.definitions
[r2
].origin
{
1830 NllRegionVariableOrigin
::Placeholder(placeholder
) => {
1831 let universe1
= self.definitions
[r1
].universe
;
1833 "cannot_name_value_of: universe1={:?} placeholder={:?}",
1834 universe1
, placeholder
1836 universe1
.cannot_name(placeholder
.universe
)
1839 NllRegionVariableOrigin
::FreeRegion
| NllRegionVariableOrigin
::Existential { .. }
=> {
1845 /// Finds a good `ObligationCause` to blame for the fact that `fr1` outlives `fr2`.
1846 pub(crate) fn find_outlives_blame_span(
1849 fr1_origin
: NllRegionVariableOrigin
,
1851 ) -> (ConstraintCategory
<'tcx
>, ObligationCause
<'tcx
>) {
1852 let BlameConstraint { category, cause, .. }
= self
1853 .best_blame_constraint(fr1
, fr1_origin
, |r
| self.provides_universal_region(r
, fr1
, fr2
))
1858 /// Walks the graph of constraints (where `'a: 'b` is considered
1859 /// an edge `'a -> 'b`) to find all paths from `from_region` to
1860 /// `to_region`. The paths are accumulated into the vector
1861 /// `results`. The paths are stored as a series of
1862 /// `ConstraintIndex` values -- in other words, a list of *edges*.
1864 /// Returns: a series of constraints as well as the region `R`
1865 /// that passed the target test.
1866 pub(crate) fn find_constraint_paths_between_regions(
1868 from_region
: RegionVid
,
1869 target_test
: impl Fn(RegionVid
) -> bool
,
1870 ) -> Option
<(Vec
<OutlivesConstraint
<'tcx
>>, RegionVid
)> {
1871 let mut context
= IndexVec
::from_elem(Trace
::NotVisited
, &self.definitions
);
1872 context
[from_region
] = Trace
::StartRegion
;
1874 // Use a deque so that we do a breadth-first search. We will
1875 // stop at the first match, which ought to be the shortest
1876 // path (fewest constraints).
1877 let mut deque
= VecDeque
::new();
1878 deque
.push_back(from_region
);
1880 while let Some(r
) = deque
.pop_front() {
1882 "find_constraint_paths_between_regions: from_region={:?} r={:?} value={}",
1885 self.region_value_str(r
),
1888 // Check if we reached the region we were looking for. If so,
1889 // we can reconstruct the path that led to it and return it.
1891 let mut result
= vec
![];
1894 match context
[p
].clone() {
1895 Trace
::NotVisited
=> {
1896 bug
!("found unvisited region {:?} on path to {:?}", p
, r
)
1899 Trace
::FromOutlivesConstraint(c
) => {
1904 Trace
::StartRegion
=> {
1906 return Some((result
, r
));
1912 // Otherwise, walk over the outgoing constraints and
1913 // enqueue any regions we find, keeping track of how we
1916 // A constraint like `'r: 'x` can come from our constraint
1918 let fr_static
= self.universal_regions
.fr_static
;
1919 let outgoing_edges_from_graph
=
1920 self.constraint_graph
.outgoing_edges(r
, &self.constraints
, fr_static
);
1922 // Always inline this closure because it can be hot.
1923 let mut handle_constraint
= #[inline(always)]
1924 |constraint
: OutlivesConstraint
<'tcx
>| {
1925 debug_assert_eq
!(constraint
.sup
, r
);
1926 let sub_region
= constraint
.sub
;
1927 if let Trace
::NotVisited
= context
[sub_region
] {
1928 context
[sub_region
] = Trace
::FromOutlivesConstraint(constraint
);
1929 deque
.push_back(sub_region
);
1933 // This loop can be hot.
1934 for constraint
in outgoing_edges_from_graph
{
1935 handle_constraint(constraint
);
1938 // Member constraints can also give rise to `'r: 'x` edges that
1939 // were not part of the graph initially, so watch out for those.
1940 // (But they are extremely rare; this loop is very cold.)
1941 for constraint
in self.applied_member_constraints(r
) {
1942 let p_c
= &self.member_constraints
[constraint
.member_constraint_index
];
1943 let constraint
= OutlivesConstraint
{
1945 sub
: constraint
.min_choice
,
1946 locations
: Locations
::All(p_c
.definition_span
),
1947 span
: p_c
.definition_span
,
1948 category
: ConstraintCategory
::OpaqueType
,
1949 variance_info
: ty
::VarianceDiagInfo
::default(),
1950 from_closure
: false,
1952 handle_constraint(constraint
);
1959 /// Finds some region R such that `fr1: R` and `R` is live at `elem`.
1960 #[instrument(skip(self), level = "trace", ret)]
1961 pub(crate) fn find_sub_region_live_at(&self, fr1
: RegionVid
, elem
: Location
) -> RegionVid
{
1962 trace
!(scc
= ?
self.constraint_sccs
.scc(fr1
));
1963 trace
!(universe
= ?
self.scc_universes
[self.constraint_sccs
.scc(fr1
)]);
1964 self.find_constraint_paths_between_regions(fr1
, |r
| {
1965 // First look for some `r` such that `fr1: r` and `r` is live at `elem`
1966 trace
!(?r
, liveness_constraints
=?
self.liveness_constraints
.region_value_str(r
));
1967 self.liveness_constraints
.contains(r
, elem
)
1970 // If we fail to find that, we may find some `r` such that
1971 // `fr1: r` and `r` is a placeholder from some universe
1972 // `fr1` cannot name. This would force `fr1` to be
1974 self.find_constraint_paths_between_regions(fr1
, |r
| {
1975 self.cannot_name_placeholder(fr1
, r
)
1979 // If we fail to find THAT, it may be that `fr1` is a
1980 // placeholder that cannot "fit" into its SCC. In that
1981 // case, there should be some `r` where `fr1: r` and `fr1` is a
1982 // placeholder that `r` cannot name. We can blame that
1985 // Remember that if `R1: R2`, then the universe of R1
1986 // must be able to name the universe of R2, because R2 will
1987 // be at least `'empty(Universe(R2))`, and `R1` must be at
1988 // larger than that.
1989 self.find_constraint_paths_between_regions(fr1
, |r
| {
1990 self.cannot_name_placeholder(r
, fr1
)
1993 .map(|(_path
, r
)| r
)
1997 /// Get the region outlived by `longer_fr` and live at `element`.
1998 pub(crate) fn region_from_element(
2000 longer_fr
: RegionVid
,
2001 element
: &RegionElement
,
2004 RegionElement
::Location(l
) => self.find_sub_region_live_at(longer_fr
, l
),
2005 RegionElement
::RootUniversalRegion(r
) => r
,
2006 RegionElement
::PlaceholderRegion(error_placeholder
) => self
2009 .find_map(|(r
, definition
)| match definition
.origin
{
2010 NllRegionVariableOrigin
::Placeholder(p
) if p
== error_placeholder
=> Some(r
),
2017 /// Get the region definition of `r`.
2018 pub(crate) fn region_definition(&self, r
: RegionVid
) -> &RegionDefinition
<'tcx
> {
2019 &self.definitions
[r
]
2022 /// Check if the SCC of `r` contains `upper`.
2023 pub(crate) fn upper_bound_in_region_scc(&self, r
: RegionVid
, upper
: RegionVid
) -> bool
{
2024 let r_scc
= self.constraint_sccs
.scc(r
);
2025 self.scc_values
.contains(r_scc
, upper
)
2028 pub(crate) fn universal_regions(&self) -> &UniversalRegions
<'tcx
> {
2029 self.universal_regions
.as_ref()
2032 /// Tries to find the best constraint to blame for the fact that
2033 /// `R: from_region`, where `R` is some region that meets
2034 /// `target_test`. This works by following the constraint graph,
2035 /// creating a constraint path that forces `R` to outlive
2036 /// `from_region`, and then finding the best choices within that
2038 #[instrument(level = "debug", skip(self, target_test))]
2039 pub(crate) fn best_blame_constraint(
2041 from_region
: RegionVid
,
2042 from_region_origin
: NllRegionVariableOrigin
,
2043 target_test
: impl Fn(RegionVid
) -> bool
,
2044 ) -> (BlameConstraint
<'tcx
>, Vec
<ExtraConstraintInfo
>) {
2046 let (path
, target_region
) =
2047 self.find_constraint_paths_between_regions(from_region
, target_test
).unwrap();
2052 "{:?} ({:?}: {:?})",
2054 self.constraint_sccs
.scc(c
.sup
),
2055 self.constraint_sccs
.scc(c
.sub
),
2057 .collect
::<Vec
<_
>>()
2060 let mut extra_info
= vec
![];
2061 for constraint
in path
.iter() {
2062 let outlived
= constraint
.sub
;
2063 let Some(origin
) = self.var_infos
.get(outlived
) else {
2066 let RegionVariableOrigin
::Nll(NllRegionVariableOrigin
::Placeholder(p
)) = origin
.origin
2070 debug
!(?constraint
, ?p
);
2071 let ConstraintCategory
::Predicate(span
) = constraint
.category
else {
2074 extra_info
.push(ExtraConstraintInfo
::PlaceholderFromPredicate(span
));
2075 // We only want to point to one
2079 // We try to avoid reporting a `ConstraintCategory::Predicate` as our best constraint.
2080 // Instead, we use it to produce an improved `ObligationCauseCode`.
2081 // FIXME - determine what we should do if we encounter multiple `ConstraintCategory::Predicate`
2082 // constraints. Currently, we just pick the first one.
2083 let cause_code
= path
2085 .find_map(|constraint
| {
2086 if let ConstraintCategory
::Predicate(predicate_span
) = constraint
.category
{
2087 // We currently do not store the `DefId` in the `ConstraintCategory`
2088 // for performances reasons. The error reporting code used by NLL only
2089 // uses the span, so this doesn't cause any problems at the moment.
2090 Some(ObligationCauseCode
::BindingObligation(
2091 CRATE_DEF_ID
.to_def_id(),
2098 .unwrap_or_else(|| ObligationCauseCode
::MiscObligation
);
2100 // Classify each of the constraints along the path.
2101 let mut categorized_path
: Vec
<BlameConstraint
<'tcx
>> = path
2103 .map(|constraint
| BlameConstraint
{
2104 category
: constraint
.category
,
2105 from_closure
: constraint
.from_closure
,
2106 cause
: ObligationCause
::new(constraint
.span
, CRATE_DEF_ID
, cause_code
.clone()),
2107 variance_info
: constraint
.variance_info
,
2108 outlives_constraint
: *constraint
,
2111 debug
!("categorized_path={:#?}", categorized_path
);
2113 // To find the best span to cite, we first try to look for the
2114 // final constraint that is interesting and where the `sup` is
2115 // not unified with the ultimate target region. The reason
2116 // for this is that we have a chain of constraints that lead
2117 // from the source to the target region, something like:
2119 // '0: '1 ('0 is the source)
2124 // '5: '6 ('6 is the target)
2126 // Some of those regions are unified with `'6` (in the same
2127 // SCC). We want to screen those out. After that point, the
2128 // "closest" constraint we have to the end is going to be the
2129 // most likely to be the point where the value escapes -- but
2130 // we still want to screen for an "interesting" point to
2131 // highlight (e.g., a call site or something).
2132 let target_scc
= self.constraint_sccs
.scc(target_region
);
2133 let mut range
= 0..path
.len();
2135 // As noted above, when reporting an error, there is typically a chain of constraints
2136 // leading from some "source" region which must outlive some "target" region.
2137 // In most cases, we prefer to "blame" the constraints closer to the target --
2138 // but there is one exception. When constraints arise from higher-ranked subtyping,
2139 // we generally prefer to blame the source value,
2140 // as the "target" in this case tends to be some type annotation that the user gave.
2141 // Therefore, if we find that the region origin is some instantiation
2142 // of a higher-ranked region, we start our search from the "source" point
2143 // rather than the "target", and we also tweak a few other things.
2145 // An example might be this bit of Rust code:
2148 // let x: fn(&'static ()) = |_| {};
2149 // let y: for<'a> fn(&'a ()) = x;
2152 // In MIR, this will be converted into a combination of assignments and type ascriptions.
2153 // In particular, the 'static is imposed through a type ascription:
2157 // AscribeUserType(x, fn(&'static ())
2161 // We wind up ultimately with constraints like
2164 // !a: 'temp1 // from the `y = x` statement
2166 // 'temp2: 'static // from the AscribeUserType
2169 // and here we prefer to blame the source (the y = x statement).
2170 let blame_source
= match from_region_origin
{
2171 NllRegionVariableOrigin
::FreeRegion
2172 | NllRegionVariableOrigin
::Existential { from_forall: false }
=> true,
2173 NllRegionVariableOrigin
::Placeholder(_
)
2174 | NllRegionVariableOrigin
::Existential { from_forall: true }
=> false,
2177 let find_region
= |i
: &usize| {
2178 let constraint
= &path
[*i
];
2180 let constraint_sup_scc
= self.constraint_sccs
.scc(constraint
.sup
);
2183 match categorized_path
[*i
].category
{
2184 ConstraintCategory
::OpaqueType
2185 | ConstraintCategory
::Boring
2186 | ConstraintCategory
::BoringNoLocation
2187 | ConstraintCategory
::Internal
2188 | ConstraintCategory
::Predicate(_
) => false,
2189 ConstraintCategory
::TypeAnnotation
2190 | ConstraintCategory
::Return(_
)
2191 | ConstraintCategory
::Yield
=> true,
2192 _
=> constraint_sup_scc
!= target_scc
,
2196 categorized_path
[*i
].category
,
2197 ConstraintCategory
::OpaqueType
2198 | ConstraintCategory
::Boring
2199 | ConstraintCategory
::BoringNoLocation
2200 | ConstraintCategory
::Internal
2201 | ConstraintCategory
::Predicate(_
)
2207 if blame_source { range.rev().find(find_region) }
else { range.find(find_region) }
;
2209 debug
!(?best_choice
, ?blame_source
, ?extra_info
);
2211 if let Some(i
) = best_choice
{
2212 if let Some(next
) = categorized_path
.get(i
+ 1) {
2213 if matches
!(categorized_path
[i
].category
, ConstraintCategory
::Return(_
))
2214 && next
.category
== ConstraintCategory
::OpaqueType
2216 // The return expression is being influenced by the return type being
2217 // impl Trait, point at the return type and not the return expr.
2218 return (next
.clone(), extra_info
);
2222 if categorized_path
[i
].category
== ConstraintCategory
::Return(ReturnConstraint
::Normal
)
2224 let field
= categorized_path
.iter().find_map(|p
| {
2225 if let ConstraintCategory
::ClosureUpvar(f
) = p
.category
{
2232 if let Some(field
) = field
{
2233 categorized_path
[i
].category
=
2234 ConstraintCategory
::Return(ReturnConstraint
::ClosureUpvar(field
));
2238 return (categorized_path
[i
].clone(), extra_info
);
2241 // If that search fails, that is.. unusual. Maybe everything
2242 // is in the same SCC or something. In that case, find what
2243 // appears to be the most interesting point to report to the
2244 // user via an even more ad-hoc guess.
2245 categorized_path
.sort_by_key(|p
| p
.category
);
2246 debug
!("sorted_path={:#?}", categorized_path
);
2248 (categorized_path
.remove(0), extra_info
)
2251 pub(crate) fn universe_info(&self, universe
: ty
::UniverseIndex
) -> UniverseInfo
<'tcx
> {
2252 // Query canonicalization can create local superuniverses (for example in
2253 // `InferCtx::query_response_instantiation_guess`), but they don't have an associated
2254 // `UniverseInfo` explaining why they were created.
2255 // This can cause ICEs if these causes are accessed in diagnostics, for example in issue
2256 // #114907 where this happens via liveness and dropck outlives results.
2257 // Therefore, we return a default value in case that happens, which should at worst emit a
2258 // suboptimal error, instead of the ICE.
2259 self.universe_causes
.get(&universe
).cloned().unwrap_or_else(|| UniverseInfo
::other())
2262 /// Tries to find the terminator of the loop in which the region 'r' resides.
2263 /// Returns the location of the terminator if found.
2264 pub(crate) fn find_loop_terminator_location(
2268 ) -> Option
<Location
> {
2269 let scc
= self.constraint_sccs
.scc(r
);
2270 let locations
= self.scc_values
.locations_outlived_by(scc
);
2271 for location
in locations
{
2272 let bb
= &body
[location
.block
];
2273 if let Some(terminator
) = &bb
.terminator
{
2274 // terminator of a loop should be TerminatorKind::FalseUnwind
2275 if let TerminatorKind
::FalseUnwind { .. }
= terminator
.kind
{
2276 return Some(location
);
2284 impl<'tcx
> RegionDefinition
<'tcx
> {
2285 fn new(universe
: ty
::UniverseIndex
, rv_origin
: RegionVariableOrigin
) -> Self {
2286 // Create a new region definition. Note that, for free
2287 // regions, the `external_name` field gets updated later in
2288 // `init_universal_regions`.
2290 let origin
= match rv_origin
{
2291 RegionVariableOrigin
::Nll(origin
) => origin
,
2292 _
=> NllRegionVariableOrigin
::Existential { from_forall: false }
,
2295 Self { origin, universe, external_name: None }
2299 #[derive(Clone, Debug)]
2300 pub struct BlameConstraint
<'tcx
> {
2301 pub category
: ConstraintCategory
<'tcx
>,
2302 pub from_closure
: bool
,
2303 pub cause
: ObligationCause
<'tcx
>,
2304 pub variance_info
: ty
::VarianceDiagInfo
<'tcx
>,
2305 pub outlives_constraint
: OutlivesConstraint
<'tcx
>,