]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use std::collections::VecDeque; |
e1599b0c XL |
2 | use std::rc::Rc; |
3 | ||
dc9dc135 | 4 | use rustc_data_structures::binary_search_util; |
ba9703b0 | 5 | use rustc_data_structures::frozen::Frozen; |
0bf4aa26 | 6 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
8faf50e0 | 7 | use rustc_data_structures::graph::scc::Sccs; |
c295e0f8 XL |
8 | use rustc_hir::def_id::{DefId, CRATE_DEF_ID}; |
9 | use rustc_hir::CRATE_HIR_ID; | |
e74abb32 | 10 | use rustc_index::vec::IndexVec; |
74b04a01 XL |
11 | use rustc_infer::infer::canonical::QueryOutlivesConstraint; |
12 | use rustc_infer::infer::region_constraints::{GenericKind, VarInfos, VerifyBound}; | |
5869c6ff | 13 | use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin}; |
ba9703b0 XL |
14 | use rustc_middle::mir::{ |
15 | Body, ClosureOutlivesRequirement, ClosureOutlivesSubject, ClosureRegionRequirements, | |
f035d41b | 16 | ConstraintCategory, Local, Location, ReturnConstraint, |
ba9703b0 | 17 | }; |
c295e0f8 XL |
18 | use rustc_middle::traits::ObligationCause; |
19 | use rustc_middle::traits::ObligationCauseCode; | |
ba9703b0 | 20 | use rustc_middle::ty::{self, subst::SubstsRef, RegionVid, Ty, TyCtxt, TypeFoldable}; |
dfeec247 | 21 | use rustc_span::Span; |
8faf50e0 | 22 | |
c295e0f8 | 23 | use crate::{ |
60c5eb7d | 24 | constraints::{ |
dfeec247 | 25 | graph::NormalConstraintGraph, ConstraintSccIndex, OutlivesConstraint, OutlivesConstraintSet, |
60c5eb7d | 26 | }, |
94222f64 | 27 | diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo}, |
60c5eb7d | 28 | member_constraints::{MemberConstraintSet, NllMemberConstraintIndex}, |
dfeec247 | 29 | nll::{PoloniusOutput, ToRegionVid}, |
74b04a01 | 30 | region_infer::reverse_sccs::ReverseSccGraph, |
60c5eb7d | 31 | region_infer::values::{ |
dfeec247 XL |
32 | LivenessValues, PlaceholderIndices, RegionElement, RegionValueElements, RegionValues, |
33 | ToElementIndex, | |
60c5eb7d XL |
34 | }, |
35 | type_check::{free_region_relations::UniversalRegionRelations, Locations}, | |
60c5eb7d | 36 | universal_regions::UniversalRegions, |
60c5eb7d | 37 | }; |
ff7c6d11 | 38 | |
ff7c6d11 XL |
39 | mod dump_mir; |
40 | mod graphviz; | |
74b04a01 XL |
41 | mod opaque_types; |
42 | mod reverse_sccs; | |
ff7c6d11 | 43 | |
e1599b0c | 44 | pub mod values; |
ff7c6d11 XL |
45 | |
46 | pub struct RegionInferenceContext<'tcx> { | |
9fa01778 | 47 | /// Contains the definition for every region variable. Region |
ff7c6d11 XL |
48 | /// variables are identified by their index (`RegionVid`). The |
49 | /// definition contains information about where the region came | |
50 | /// from as well as its final inferred value. | |
dfeec247 | 51 | definitions: IndexVec<RegionVid, RegionDefinition<'tcx>>, |
ff7c6d11 | 52 | |
ff7c6d11 XL |
53 | /// The liveness constraints added to each region. For most |
54 | /// regions, these start out empty and steadily grow, though for | |
55 | /// each universally quantified region R they start out containing | |
56 | /// the entire CFG and `end(R)`. | |
dfeec247 | 57 | liveness_constraints: LivenessValues<RegionVid>, |
ff7c6d11 | 58 | |
8faf50e0 | 59 | /// The outlives constraints computed by the type-check. |
17df50a5 | 60 | constraints: Frozen<OutlivesConstraintSet<'tcx>>, |
ff7c6d11 | 61 | |
8faf50e0 XL |
62 | /// The constraint-set, but in graph form, making it easy to traverse |
63 | /// the constraints adjacent to a particular region. Used to construct | |
64 | /// the SCC (see `constraint_sccs`) and for error reporting. | |
ba9703b0 | 65 | constraint_graph: Frozen<NormalConstraintGraph>, |
8faf50e0 | 66 | |
dc9dc135 XL |
67 | /// The SCC computed from `constraints` and the constraint |
68 | /// graph. We have an edge from SCC A to SCC B if `A: B`. Used to | |
0bf4aa26 | 69 | /// compute the values of each region. |
dfeec247 | 70 | constraint_sccs: Rc<Sccs<RegionVid, ConstraintSccIndex>>, |
8faf50e0 | 71 | |
74b04a01 XL |
72 | /// Reverse of the SCC constraint graph -- i.e., an edge `A -> B` exists if |
73 | /// `B: A`. This is used to compute the universal regions that are required | |
74 | /// to outlive a given SCC. Computed lazily. | |
75 | rev_scc_graph: Option<Rc<ReverseSccGraph>>, | |
dc9dc135 XL |
76 | |
77 | /// The "R0 member of [R1..Rn]" constraints, indexed by SCC. | |
dfeec247 | 78 | member_constraints: Rc<MemberConstraintSet<'tcx, ConstraintSccIndex>>, |
dc9dc135 XL |
79 | |
80 | /// Records the member constraints that we applied to each scc. | |
81 | /// This is useful for error reporting. Once constraint | |
82 | /// propagation is done, this vector is sorted according to | |
83 | /// `member_region_scc`. | |
dfeec247 | 84 | member_constraints_applied: Vec<AppliedMemberConstraint>, |
dc9dc135 | 85 | |
0bf4aa26 | 86 | /// Map closure bounds to a `Span` that should be used for error reporting. |
dfeec247 | 87 | closure_bounds_mapping: |
0bf4aa26 XL |
88 | FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>, |
89 | ||
94222f64 | 90 | /// Map universe indexes to information on why we created it. |
c295e0f8 | 91 | universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>, |
94222f64 | 92 | |
8faf50e0 XL |
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. | |
dfeec247 | 96 | scc_universes: IndexVec<ConstraintSccIndex, ty::UniverseIndex>, |
0531ce1d | 97 | |
0bf4aa26 XL |
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). | |
dfeec247 | 105 | scc_representatives: IndexVec<ConstraintSccIndex, ty::RegionVid>, |
0bf4aa26 | 106 | |
8faf50e0 XL |
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. | |
dfeec247 | 110 | scc_values: RegionValues<ConstraintSccIndex>, |
ff7c6d11 XL |
111 | |
112 | /// Type constraints that we check after solving. | |
dfeec247 | 113 | type_tests: Vec<TypeTest<'tcx>>, |
ff7c6d11 XL |
114 | |
115 | /// Information about the universally quantified regions in scope | |
8faf50e0 | 116 | /// on this function. |
dfeec247 | 117 | universal_regions: Rc<UniversalRegions<'tcx>>, |
ff7c6d11 | 118 | |
8faf50e0 XL |
119 | /// Information about how the universally quantified regions in |
120 | /// scope on this function relate to one another. | |
ba9703b0 | 121 | universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, |
8faf50e0 | 122 | } |
ff7c6d11 | 123 | |
dc9dc135 XL |
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. | |
127 | /// | |
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. | |
132 | #[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)] | |
60c5eb7d | 133 | pub(crate) struct AppliedMemberConstraint { |
dc9dc135 XL |
134 | /// The SCC that was affected. (The "member region".) |
135 | /// | |
136 | /// The vector if `AppliedMemberConstraint` elements is kept sorted | |
137 | /// by this field. | |
c295e0f8 | 138 | pub(crate) member_region_scc: ConstraintSccIndex, |
dc9dc135 XL |
139 | |
140 | /// The "best option" that `apply_member_constraint` found -- this was | |
141 | /// added as an "ad-hoc" lower-bound to `member_region_scc`. | |
c295e0f8 | 142 | pub(crate) min_choice: ty::RegionVid, |
dc9dc135 XL |
143 | |
144 | /// The "member constraint index" -- we can find out details about | |
145 | /// the constraint from | |
146 | /// `set.member_constraints[member_constraint_index]`. | |
c295e0f8 | 147 | pub(crate) member_constraint_index: NllMemberConstraintIndex, |
dc9dc135 XL |
148 | } |
149 | ||
60c5eb7d | 150 | pub(crate) struct RegionDefinition<'tcx> { |
8faf50e0 | 151 | /// What kind of variable is this -- a free region? existential |
5869c6ff | 152 | /// variable? etc. (See the `NllRegionVariableOrigin` for more |
8faf50e0 | 153 | /// info.) |
c295e0f8 | 154 | pub(crate) origin: NllRegionVariableOrigin, |
8faf50e0 XL |
155 | |
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 | |
0bf4aa26 | 159 | /// the variable for `'a` in a fresh universe that extends ROOT. |
c295e0f8 | 160 | pub(crate) universe: ty::UniverseIndex, |
ff7c6d11 XL |
161 | |
162 | /// If this is 'static or an early-bound region, then this is | |
163 | /// `Some(X)` where `X` is the name of the region. | |
c295e0f8 | 164 | pub(crate) external_name: Option<ty::Region<'tcx>>, |
ff7c6d11 XL |
165 | } |
166 | ||
0731742a | 167 | /// N.B., the variants in `Cause` are intentionally ordered. Lower |
ff7c6d11 XL |
168 | /// values are preferred when it comes to error messages. Do not |
169 | /// reorder willy nilly. | |
94b46f34 | 170 | #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)] |
ff7c6d11 XL |
171 | pub(crate) enum Cause { |
172 | /// point inserted because Local was live at the given Location | |
173 | LiveVar(Local, Location), | |
174 | ||
175 | /// point inserted because Local was dropped at the given Location | |
176 | DropVar(Local, Location), | |
0531ce1d XL |
177 | } |
178 | ||
ff7c6d11 | 179 | /// A "type test" corresponds to an outlives constraint between a type |
9fa01778 | 180 | /// and a lifetime, like `T: 'x` or `<T as Foo>::Bar: 'x`. They are |
ff7c6d11 XL |
181 | /// translated from the `Verify` region constraints in the ordinary |
182 | /// inference context. | |
183 | /// | |
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`). | |
190 | /// | |
191 | /// In some cases, however, there are outlives relationships that are | |
192 | /// not converted into a region constraint, but rather into one of | |
9fa01778 | 193 | /// these "type tests". The distinction is that a type test does not |
ff7c6d11 XL |
194 | /// influence the inference result, but instead just examines the |
195 | /// values that we ultimately inferred for each region variable and | |
9fa01778 | 196 | /// checks that they meet certain extra criteria. If not, an error |
ff7c6d11 XL |
197 | /// can be issued. |
198 | /// | |
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 | |
206 | /// than one way. | |
207 | /// | |
208 | /// For more information about this translation, see | |
209 | /// `InferCtxt::process_registered_region_obligations` and | |
ba9703b0 | 210 | /// `InferCtxt::type_must_outlive` in `rustc_infer::infer::InferCtxt`. |
ff7c6d11 XL |
211 | #[derive(Clone, Debug)] |
212 | pub struct TypeTest<'tcx> { | |
213 | /// The type `T` that must outlive the region. | |
214 | pub generic_kind: GenericKind<'tcx>, | |
215 | ||
216 | /// The region `'x` that the type must outlive. | |
217 | pub lower_bound: RegionVid, | |
218 | ||
8faf50e0 XL |
219 | /// Where did this constraint arise and why? |
220 | pub locations: Locations, | |
ff7c6d11 XL |
221 | |
222 | /// A test which, if met by the region `'x`, proves that this type | |
223 | /// constraint is satisfied. | |
0bf4aa26 | 224 | pub verify_bound: VerifyBound<'tcx>, |
ff7c6d11 XL |
225 | } |
226 | ||
dfeec247 XL |
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 { | |
231 | Ok, | |
232 | Propagated, | |
233 | Error, | |
234 | } | |
235 | ||
17df50a5 XL |
236 | #[derive(Clone, PartialEq, Eq, Debug)] |
237 | enum Trace<'tcx> { | |
dfeec247 | 238 | StartRegion, |
17df50a5 | 239 | FromOutlivesConstraint(OutlivesConstraint<'tcx>), |
dfeec247 XL |
240 | NotVisited, |
241 | } | |
242 | ||
ff7c6d11 XL |
243 | impl<'tcx> RegionInferenceContext<'tcx> { |
244 | /// Creates a new region inference context with a total of | |
245 | /// `num_region_variables` valid inference variables; the first N | |
246 | /// of those will be constant regions representing the free | |
247 | /// regions defined in `universal_regions`. | |
94b46f34 XL |
248 | /// |
249 | /// The `outlives_constraints` and `type_tests` are an initial set | |
250 | /// of constraints produced by the MIR type check. | |
c295e0f8 | 251 | pub(crate) fn new( |
83c7162d | 252 | var_infos: VarInfos, |
8faf50e0 | 253 | universal_regions: Rc<UniversalRegions<'tcx>>, |
0bf4aa26 | 254 | placeholder_indices: Rc<PlaceholderIndices>, |
ba9703b0 | 255 | universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, |
17df50a5 | 256 | outlives_constraints: OutlivesConstraintSet<'tcx>, |
dc9dc135 | 257 | member_constraints_in: MemberConstraintSet<'tcx, RegionVid>, |
0bf4aa26 XL |
258 | closure_bounds_mapping: FxHashMap< |
259 | Location, | |
260 | FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>, | |
261 | >, | |
c295e0f8 | 262 | universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>, |
94b46f34 | 263 | type_tests: Vec<TypeTest<'tcx>>, |
8faf50e0 XL |
264 | liveness_constraints: LivenessValues<RegionVid>, |
265 | elements: &Rc<RegionValueElements>, | |
ff7c6d11 | 266 | ) -> Self { |
ff7c6d11 | 267 | // Create a RegionDefinition for each inference variable. |
8faf50e0 | 268 | let definitions: IndexVec<_, _> = var_infos |
ff7c6d11 | 269 | .into_iter() |
8faf50e0 | 270 | .map(|info| RegionDefinition::new(info.universe, info.origin)) |
ff7c6d11 XL |
271 | .collect(); |
272 | ||
ba9703b0 XL |
273 | let constraints = Frozen::freeze(outlives_constraints); |
274 | let constraint_graph = Frozen::freeze(constraints.graph(definitions.len())); | |
b7449926 XL |
275 | let fr_static = universal_regions.fr_static; |
276 | let constraint_sccs = Rc::new(constraints.compute_sccs(&constraint_graph, fr_static)); | |
8faf50e0 | 277 | |
0bf4aa26 XL |
278 | let mut scc_values = |
279 | RegionValues::new(elements, universal_regions.len(), &placeholder_indices); | |
8faf50e0 XL |
280 | |
281 | for region in liveness_constraints.rows() { | |
282 | let scc = constraint_sccs.scc(region); | |
283 | scc_values.merge_liveness(scc, region, &liveness_constraints); | |
284 | } | |
285 | ||
286 | let scc_universes = Self::compute_scc_universes(&constraint_sccs, &definitions); | |
287 | ||
0bf4aa26 XL |
288 | let scc_representatives = Self::compute_scc_representatives(&constraint_sccs, &definitions); |
289 | ||
dc9dc135 XL |
290 | let member_constraints = |
291 | Rc::new(member_constraints_in.into_mapped(|r| constraint_sccs.scc(r))); | |
292 | ||
ff7c6d11 XL |
293 | let mut result = Self { |
294 | definitions, | |
8faf50e0 XL |
295 | liveness_constraints, |
296 | constraints, | |
297 | constraint_graph, | |
298 | constraint_sccs, | |
74b04a01 | 299 | rev_scc_graph: None, |
dc9dc135 XL |
300 | member_constraints, |
301 | member_constraints_applied: Vec::new(), | |
0bf4aa26 | 302 | closure_bounds_mapping, |
94222f64 | 303 | universe_causes, |
8faf50e0 | 304 | scc_universes, |
0bf4aa26 | 305 | scc_representatives, |
8faf50e0 | 306 | scc_values, |
94b46f34 | 307 | type_tests, |
ff7c6d11 | 308 | universal_regions, |
8faf50e0 | 309 | universal_region_relations, |
ff7c6d11 XL |
310 | }; |
311 | ||
8faf50e0 | 312 | result.init_free_and_bound_regions(); |
ff7c6d11 XL |
313 | |
314 | result | |
315 | } | |
316 | ||
8faf50e0 XL |
317 | /// Each SCC is the combination of many region variables which |
318 | /// have been equated. Therefore, we can associate a universe with | |
319 | /// each SCC which is minimum of all the universes of its | |
320 | /// constituent regions -- this is because whatever value the SCC | |
321 | /// takes on must be a value that each of the regions within the | |
322 | /// SCC could have as well. This implies that the SCC must have | |
323 | /// the minimum, or narrowest, universe. | |
324 | fn compute_scc_universes( | |
f9f354fc | 325 | constraint_sccs: &Sccs<RegionVid, ConstraintSccIndex>, |
8faf50e0 XL |
326 | definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>, |
327 | ) -> IndexVec<ConstraintSccIndex, ty::UniverseIndex> { | |
f9f354fc | 328 | let num_sccs = constraint_sccs.num_sccs(); |
8faf50e0 XL |
329 | let mut scc_universes = IndexVec::from_elem_n(ty::UniverseIndex::MAX, num_sccs); |
330 | ||
f9f354fc XL |
331 | debug!("compute_scc_universes()"); |
332 | ||
333 | // For each region R in universe U, ensure that the universe for the SCC | |
334 | // that contains R is "no bigger" than U. This effectively sets the universe | |
335 | // for each SCC to be the minimum of the regions within. | |
8faf50e0 | 336 | for (region_vid, region_definition) in definitions.iter_enumerated() { |
f9f354fc | 337 | let scc = constraint_sccs.scc(region_vid); |
8faf50e0 | 338 | let scc_universe = &mut scc_universes[scc]; |
f9f354fc XL |
339 | let scc_min = std::cmp::min(region_definition.universe, *scc_universe); |
340 | if scc_min != *scc_universe { | |
341 | *scc_universe = scc_min; | |
342 | debug!( | |
343 | "compute_scc_universes: lowered universe of {scc:?} to {scc_min:?} \ | |
344 | because it contains {region_vid:?} in {region_universe:?}", | |
345 | scc = scc, | |
346 | scc_min = scc_min, | |
347 | region_vid = region_vid, | |
348 | region_universe = region_definition.universe, | |
349 | ); | |
350 | } | |
351 | } | |
352 | ||
353 | // Walk each SCC `A` and `B` such that `A: B` | |
354 | // and ensure that universe(A) can see universe(B). | |
355 | // | |
356 | // This serves to enforce the 'empty/placeholder' hierarchy | |
357 | // (described in more detail on `RegionKind`): | |
358 | // | |
359 | // ``` | |
360 | // static -----+ | |
361 | // | | | |
362 | // empty(U0) placeholder(U1) | |
363 | // | / | |
364 | // empty(U1) | |
365 | // ``` | |
366 | // | |
367 | // In particular, imagine we have variables R0 in U0 and R1 | |
368 | // created in U1, and constraints like this; | |
369 | // | |
370 | // ``` | |
371 | // R1: !1 // R1 outlives the placeholder in U1 | |
372 | // R1: R0 // R1 outlives R0 | |
373 | // ``` | |
374 | // | |
375 | // Here, we wish for R1 to be `'static`, because it | |
376 | // cannot outlive `placeholder(U1)` and `empty(U0)` any other way. | |
377 | // | |
378 | // Thanks to this loop, what happens is that the `R1: R0` | |
379 | // constraint lowers the universe of `R1` to `U0`, which in turn | |
380 | // means that the `R1: !1` constraint will (later) cause | |
381 | // `R1` to become `'static`. | |
382 | for scc_a in constraint_sccs.all_sccs() { | |
383 | for &scc_b in constraint_sccs.successors(scc_a) { | |
384 | let scc_universe_a = scc_universes[scc_a]; | |
385 | let scc_universe_b = scc_universes[scc_b]; | |
386 | let scc_universe_min = std::cmp::min(scc_universe_a, scc_universe_b); | |
387 | if scc_universe_a != scc_universe_min { | |
388 | scc_universes[scc_a] = scc_universe_min; | |
389 | ||
390 | debug!( | |
391 | "compute_scc_universes: lowered universe of {scc_a:?} to {scc_universe_min:?} \ | |
392 | because {scc_a:?}: {scc_b:?} and {scc_b:?} is in universe {scc_universe_b:?}", | |
393 | scc_a = scc_a, | |
394 | scc_b = scc_b, | |
395 | scc_universe_min = scc_universe_min, | |
396 | scc_universe_b = scc_universe_b | |
397 | ); | |
398 | } | |
399 | } | |
8faf50e0 XL |
400 | } |
401 | ||
402 | debug!("compute_scc_universes: scc_universe = {:#?}", scc_universes); | |
403 | ||
404 | scc_universes | |
405 | } | |
406 | ||
0bf4aa26 XL |
407 | /// For each SCC, we compute a unique `RegionVid` (in fact, the |
408 | /// minimal one that belongs to the SCC). See | |
409 | /// `scc_representatives` field of `RegionInferenceContext` for | |
410 | /// more details. | |
411 | fn compute_scc_representatives( | |
412 | constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>, | |
413 | definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>, | |
414 | ) -> IndexVec<ConstraintSccIndex, ty::RegionVid> { | |
415 | let num_sccs = constraints_scc.num_sccs(); | |
416 | let next_region_vid = definitions.next_index(); | |
417 | let mut scc_representatives = IndexVec::from_elem_n(next_region_vid, num_sccs); | |
418 | ||
419 | for region_vid in definitions.indices() { | |
420 | let scc = constraints_scc.scc(region_vid); | |
421 | let prev_min = scc_representatives[scc]; | |
422 | scc_representatives[scc] = region_vid.min(prev_min); | |
423 | } | |
424 | ||
425 | scc_representatives | |
426 | } | |
427 | ||
ff7c6d11 XL |
428 | /// Initializes the region variables for each universally |
429 | /// quantified region (lifetime parameter). The first N variables | |
430 | /// always correspond to the regions appearing in the function | |
9fa01778 | 431 | /// signature (both named and anonymous) and where-clauses. This |
ff7c6d11 XL |
432 | /// function iterates over those regions and initializes them with |
433 | /// minimum values. | |
434 | /// | |
435 | /// For example: | |
436 | /// | |
437 | /// fn foo<'a, 'b>(..) where 'a: 'b | |
438 | /// | |
439 | /// would initialize two variables like so: | |
440 | /// | |
441 | /// R0 = { CFG, R0 } // 'a | |
442 | /// R1 = { CFG, R0, R1 } // 'b | |
443 | /// | |
444 | /// Here, R0 represents `'a`, and it contains (a) the entire CFG | |
445 | /// and (b) any universally quantified regions that it outlives, | |
446 | /// which in this case is just itself. R1 (`'b`) in contrast also | |
447 | /// outlives `'a` and hence contains R0 and R1. | |
8faf50e0 | 448 | fn init_free_and_bound_regions(&mut self) { |
ff7c6d11 XL |
449 | // Update the names (if any) |
450 | for (external_name, variable) in self.universal_regions.named_universal_regions() { | |
8faf50e0 XL |
451 | debug!( |
452 | "init_universal_regions: region {:?} has external name {:?}", | |
453 | variable, external_name | |
454 | ); | |
ff7c6d11 XL |
455 | self.definitions[variable].external_name = Some(external_name); |
456 | } | |
457 | ||
8faf50e0 | 458 | for variable in self.definitions.indices() { |
b7449926 XL |
459 | let scc = self.constraint_sccs.scc(variable); |
460 | ||
8faf50e0 | 461 | match self.definitions[variable].origin { |
5869c6ff | 462 | NllRegionVariableOrigin::FreeRegion => { |
8faf50e0 | 463 | // For each free, universally quantified region X: |
ff7c6d11 | 464 | |
8faf50e0 | 465 | // Add all nodes in the CFG to liveness constraints |
8faf50e0 | 466 | self.liveness_constraints.add_all_points(variable); |
b7449926 | 467 | self.scc_values.add_all_points(scc); |
ff7c6d11 | 468 | |
8faf50e0 | 469 | // Add `end(X)` into the set for X. |
b7449926 | 470 | self.scc_values.add_element(scc, variable); |
8faf50e0 | 471 | } |
ff7c6d11 | 472 | |
5869c6ff | 473 | NllRegionVariableOrigin::Placeholder(placeholder) => { |
0bf4aa26 XL |
474 | // Each placeholder region is only visible from |
475 | // its universe `ui` and its extensions. So we | |
476 | // can't just add it into `scc` unless the | |
477 | // universe of the scc can name this region. | |
b7449926 | 478 | let scc_universe = self.scc_universes[scc]; |
0bf4aa26 XL |
479 | if scc_universe.can_name(placeholder.universe) { |
480 | self.scc_values.add_element(scc, placeholder); | |
b7449926 | 481 | } else { |
a1dfa0c6 XL |
482 | debug!( |
483 | "init_free_and_bound_regions: placeholder {:?} is \ | |
484 | not compatible with universe {:?} of its SCC {:?}", | |
dc9dc135 | 485 | placeholder, scc_universe, scc, |
a1dfa0c6 | 486 | ); |
b7449926 XL |
487 | self.add_incompatible_universe(scc); |
488 | } | |
8faf50e0 XL |
489 | } |
490 | ||
5869c6ff XL |
491 | NllRegionVariableOrigin::RootEmptyRegion |
492 | | NllRegionVariableOrigin::Existential { .. } => { | |
8faf50e0 XL |
493 | // For existential, regions, nothing to do. |
494 | } | |
495 | } | |
ff7c6d11 XL |
496 | } |
497 | } | |
498 | ||
499 | /// Returns an iterator over all the region indices. | |
c295e0f8 | 500 | pub fn regions(&self) -> impl Iterator<Item = RegionVid> + '_ { |
ff7c6d11 XL |
501 | self.definitions.indices() |
502 | } | |
503 | ||
504 | /// Given a universal region in scope on the MIR, returns the | |
505 | /// corresponding index. | |
506 | /// | |
507 | /// (Panics if `r` is not a registered universal region.) | |
508 | pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { | |
509 | self.universal_regions.to_region_vid(r) | |
510 | } | |
511 | ||
9fa01778 | 512 | /// Adds annotations for `#[rustc_regions]`; see `UniversalRegions::annotate`. |
dfeec247 | 513 | crate fn annotate(&self, tcx: TyCtxt<'tcx>, err: &mut rustc_errors::DiagnosticBuilder<'_>) { |
b7449926 XL |
514 | self.universal_regions.annotate(tcx, err) |
515 | } | |
516 | ||
9fa01778 | 517 | /// Returns `true` if the region `r` contains the point `p`. |
ff7c6d11 XL |
518 | /// |
519 | /// Panics if called before `solve()` executes, | |
8faf50e0 XL |
520 | crate fn region_contains(&self, r: impl ToRegionVid, p: impl ToElementIndex) -> bool { |
521 | let scc = self.constraint_sccs.scc(r.to_region_vid()); | |
522 | self.scc_values.contains(scc, p) | |
ff7c6d11 XL |
523 | } |
524 | ||
ff7c6d11 | 525 | /// Returns access to the value of `r` for debugging purposes. |
94b46f34 | 526 | crate fn region_value_str(&self, r: RegionVid) -> String { |
8faf50e0 XL |
527 | let scc = self.constraint_sccs.scc(r.to_region_vid()); |
528 | self.scc_values.region_value_str(scc) | |
ff7c6d11 XL |
529 | } |
530 | ||
8faf50e0 XL |
531 | /// Returns access to the value of `r` for debugging purposes. |
532 | crate fn region_universe(&self, r: RegionVid) -> ty::UniverseIndex { | |
533 | let scc = self.constraint_sccs.scc(r.to_region_vid()); | |
534 | self.scc_universes[scc] | |
ff7c6d11 XL |
535 | } |
536 | ||
dc9dc135 XL |
537 | /// Once region solving has completed, this function will return |
538 | /// the member constraints that were applied to the value of a given | |
539 | /// region `r`. See `AppliedMemberConstraint`. | |
c295e0f8 | 540 | pub(crate) fn applied_member_constraints( |
dfeec247 XL |
541 | &self, |
542 | r: impl ToRegionVid, | |
60c5eb7d | 543 | ) -> &[AppliedMemberConstraint] { |
dc9dc135 XL |
544 | let scc = self.constraint_sccs.scc(r.to_region_vid()); |
545 | binary_search_util::binary_search_slice( | |
546 | &self.member_constraints_applied, | |
547 | |applied| applied.member_region_scc, | |
548 | &scc, | |
549 | ) | |
550 | } | |
551 | ||
9fa01778 | 552 | /// Performs region inference and report errors if we see any |
ff7c6d11 XL |
553 | /// unsatisfiable constraints. If this is a closure, returns the |
554 | /// region requirements to propagate to our creator, if any. | |
c295e0f8 | 555 | #[instrument(skip(self, infcx, body, polonius_output), level = "debug")] |
dc9dc135 | 556 | pub(super) fn solve( |
ff7c6d11 | 557 | &mut self, |
dc9dc135 XL |
558 | infcx: &InferCtxt<'_, 'tcx>, |
559 | body: &Body<'tcx>, | |
60c5eb7d | 560 | polonius_output: Option<Rc<PoloniusOutput>>, |
dfeec247 | 561 | ) -> (Option<ClosureRegionRequirements<'tcx>>, RegionErrors<'tcx>) { |
29967ef6 | 562 | let mir_def_id = body.source.def_id(); |
136023e0 | 563 | self.propagate_constraints(body); |
ff7c6d11 | 564 | |
dfeec247 XL |
565 | let mut errors_buffer = RegionErrors::new(); |
566 | ||
ff7c6d11 XL |
567 | // If this is a closure, we can propagate unsatisfied |
568 | // `outlives_requirements` to our creator, so create a vector | |
569 | // to store those. Otherwise, we'll pass in `None` to the | |
570 | // functions below, which will trigger them to report errors | |
571 | // eagerly. | |
3c0e092e | 572 | let mut outlives_requirements = infcx.tcx.is_typeck_child(mir_def_id).then(Vec::new); |
ff7c6d11 | 573 | |
dfeec247 | 574 | self.check_type_tests(infcx, body, outlives_requirements.as_mut(), &mut errors_buffer); |
e1599b0c | 575 | |
60c5eb7d XL |
576 | // In Polonius mode, the errors about missing universal region relations are in the output |
577 | // and need to be emitted or propagated. Otherwise, we need to check whether the | |
578 | // constraints were too strong, and if so, emit or propagate those errors. | |
579 | if infcx.tcx.sess.opts.debugging_opts.polonius { | |
580 | self.check_polonius_subset_errors( | |
60c5eb7d | 581 | body, |
60c5eb7d | 582 | outlives_requirements.as_mut(), |
dfeec247 | 583 | &mut errors_buffer, |
60c5eb7d XL |
584 | polonius_output.expect("Polonius output is unavailable despite `-Z polonius`"), |
585 | ); | |
586 | } else { | |
dfeec247 | 587 | self.check_universal_regions(body, outlives_requirements.as_mut(), &mut errors_buffer); |
60c5eb7d | 588 | } |
ff7c6d11 | 589 | |
74b04a01 XL |
590 | if errors_buffer.is_empty() { |
591 | self.check_member_constraints(infcx, &mut errors_buffer); | |
592 | } | |
dc9dc135 | 593 | |
29967ef6 | 594 | let outlives_requirements = outlives_requirements.unwrap_or_default(); |
ff7c6d11 XL |
595 | |
596 | if outlives_requirements.is_empty() { | |
dfeec247 | 597 | (None, errors_buffer) |
ff7c6d11 XL |
598 | } else { |
599 | let num_external_vids = self.universal_regions.num_global_and_external_regions(); | |
dfeec247 XL |
600 | ( |
601 | Some(ClosureRegionRequirements { num_external_vids, outlives_requirements }), | |
602 | errors_buffer, | |
603 | ) | |
ff7c6d11 XL |
604 | } |
605 | } | |
606 | ||
607 | /// Propagate the region constraints: this will grow the values | |
608 | /// for each region variable until all the constraints are | |
609 | /// satisfied. Note that some values may grow **too** large to be | |
610 | /// feasible, but we check this later. | |
c295e0f8 | 611 | #[instrument(skip(self, _body), level = "debug")] |
136023e0 | 612 | fn propagate_constraints(&mut self, _body: &Body<'tcx>) { |
c295e0f8 | 613 | debug!("constraints={:#?}", { |
dc9dc135 | 614 | let mut constraints: Vec<_> = self.constraints.outlives().iter().collect(); |
5099ac24 | 615 | constraints.sort_by_key(|c| (c.sup, c.sub)); |
ff7c6d11 | 616 | constraints |
a1dfa0c6 XL |
617 | .into_iter() |
618 | .map(|c| (c, self.constraint_sccs.scc(c.sup), self.constraint_sccs.scc(c.sub))) | |
619 | .collect::<Vec<_>>() | |
ff7c6d11 XL |
620 | }); |
621 | ||
8faf50e0 XL |
622 | // To propagate constraints, we walk the DAG induced by the |
623 | // SCC. For each SCC, we visit its successors and compute | |
624 | // their values, then we union all those values to get our | |
625 | // own. | |
f9f354fc XL |
626 | let constraint_sccs = self.constraint_sccs.clone(); |
627 | for scc in constraint_sccs.all_sccs() { | |
136023e0 | 628 | self.compute_value_for_scc(scc); |
8faf50e0 | 629 | } |
dc9dc135 XL |
630 | |
631 | // Sort the applied member constraints so we can binary search | |
632 | // through them later. | |
633 | self.member_constraints_applied.sort_by_key(|applied| applied.member_region_scc); | |
8faf50e0 | 634 | } |
ff7c6d11 | 635 | |
dc9dc135 | 636 | /// Computes the value of the SCC `scc_a`, which has not yet been |
f9f354fc XL |
637 | /// computed, by unioning the values of its successors. |
638 | /// Assumes that all successors have been computed already | |
639 | /// (which is assured by iterating over SCCs in dependency order). | |
c295e0f8 | 640 | #[instrument(skip(self), level = "debug")] |
136023e0 | 641 | fn compute_value_for_scc(&mut self, scc_a: ConstraintSccIndex) { |
8faf50e0 | 642 | let constraint_sccs = self.constraint_sccs.clone(); |
2c00a5a8 | 643 | |
8faf50e0 XL |
644 | // Walk each SCC `B` such that `A: B`... |
645 | for &scc_b in constraint_sccs.successors(scc_a) { | |
c295e0f8 | 646 | debug!(?scc_b); |
2c00a5a8 | 647 | |
8faf50e0 XL |
648 | // ...and add elements from `B` into `A`. One complication |
649 | // arises because of universes: If `B` contains something | |
650 | // that `A` cannot name, then `A` can only contain `B` if | |
651 | // it outlives static. | |
652 | if self.universe_compatible(scc_b, scc_a) { | |
653 | // `A` can name everything that is in `B`, so just | |
654 | // merge the bits. | |
655 | self.scc_values.add_region(scc_a, scc_b); | |
656 | } else { | |
b7449926 | 657 | self.add_incompatible_universe(scc_a); |
ff7c6d11 | 658 | } |
ff7c6d11 XL |
659 | } |
660 | ||
dc9dc135 XL |
661 | // Now take member constraints into account. |
662 | let member_constraints = self.member_constraints.clone(); | |
663 | for m_c_i in member_constraints.indices(scc_a) { | |
136023e0 | 664 | self.apply_member_constraint(scc_a, m_c_i, member_constraints.choice_regions(m_c_i)); |
dc9dc135 XL |
665 | } |
666 | ||
c295e0f8 | 667 | debug!(value = ?self.scc_values.region_value_str(scc_a)); |
ff7c6d11 XL |
668 | } |
669 | ||
dc9dc135 XL |
670 | /// Invoked for each `R0 member of [R1..Rn]` constraint. |
671 | /// | |
672 | /// `scc` is the SCC containing R0, and `choice_regions` are the | |
673 | /// `R1..Rn` regions -- they are always known to be universal | |
674 | /// regions (and if that's not true, we just don't attempt to | |
675 | /// enforce the constraint). | |
676 | /// | |
677 | /// The current value of `scc` at the time the method is invoked | |
678 | /// is considered a *lower bound*. If possible, we will modify | |
679 | /// the constraint to set it equal to one of the option regions. | |
680 | /// If we make any changes, returns true, else false. | |
c295e0f8 | 681 | #[instrument(skip(self, member_constraint_index), level = "debug")] |
dc9dc135 XL |
682 | fn apply_member_constraint( |
683 | &mut self, | |
684 | scc: ConstraintSccIndex, | |
685 | member_constraint_index: NllMemberConstraintIndex, | |
686 | choice_regions: &[ty::RegionVid], | |
687 | ) -> bool { | |
dc9dc135 XL |
688 | // Create a mutable vector of the options. We'll try to winnow |
689 | // them down. | |
690 | let mut choice_regions: Vec<ty::RegionVid> = choice_regions.to_vec(); | |
691 | ||
3c0e092e XL |
692 | // Convert to the SCC representative: sometimes we have inference |
693 | // variables in the member constraint that wind up equated with | |
694 | // universal regions. The scc representative is the minimal numbered | |
695 | // one from the corresponding scc so it will be the universal region | |
696 | // if one exists. | |
697 | for c_r in &mut choice_regions { | |
698 | let scc = self.constraint_sccs.scc(*c_r); | |
699 | *c_r = self.scc_representatives[scc]; | |
700 | } | |
701 | ||
dc9dc135 XL |
702 | // The 'member region' in a member constraint is part of the |
703 | // hidden type, which must be in the root universe. Therefore, | |
704 | // it cannot have any placeholders in its value. | |
705 | assert!(self.scc_universes[scc] == ty::UniverseIndex::ROOT); | |
706 | debug_assert!( | |
707 | self.scc_values.placeholders_contained_in(scc).next().is_none(), | |
708 | "scc {:?} in a member constraint has placeholder value: {:?}", | |
709 | scc, | |
710 | self.scc_values.region_value_str(scc), | |
711 | ); | |
712 | ||
713 | // The existing value for `scc` is a lower-bound. This will | |
714 | // consist of some set `{P} + {LB}` of points `{P}` and | |
715 | // lower-bound free regions `{LB}`. As each choice region `O` | |
716 | // is a free region, it will outlive the points. But we can | |
717 | // only consider the option `O` if `O: LB`. | |
718 | choice_regions.retain(|&o_r| { | |
719 | self.scc_values | |
720 | .universal_regions_outlived_by(scc) | |
721 | .all(|lb| self.universal_region_relations.outlives(o_r, lb)) | |
722 | }); | |
c295e0f8 | 723 | debug!(?choice_regions, "after lb"); |
dc9dc135 XL |
724 | |
725 | // Now find all the *upper bounds* -- that is, each UB is a | |
726 | // free region that must outlive the member region `R0` (`UB: | |
727 | // R0`). Therefore, we need only keep an option `O` if `UB: O` | |
728 | // for all UB. | |
74b04a01 XL |
729 | let rev_scc_graph = self.reverse_scc_graph(); |
730 | let universal_region_relations = &self.universal_region_relations; | |
731 | for ub in rev_scc_graph.upper_bounds(scc) { | |
c295e0f8 | 732 | debug!(?ub); |
74b04a01 | 733 | choice_regions.retain(|&o_r| universal_region_relations.outlives(ub, o_r)); |
dc9dc135 | 734 | } |
c295e0f8 | 735 | debug!(?choice_regions, "after ub"); |
dc9dc135 XL |
736 | |
737 | // If we ruled everything out, we're done. | |
738 | if choice_regions.is_empty() { | |
739 | return false; | |
740 | } | |
741 | ||
742 | // Otherwise, we need to find the minimum remaining choice, if | |
743 | // any, and take that. | |
c295e0f8 | 744 | debug!("choice_regions remaining are {:#?}", choice_regions); |
dc9dc135 XL |
745 | let min = |r1: ty::RegionVid, r2: ty::RegionVid| -> Option<ty::RegionVid> { |
746 | let r1_outlives_r2 = self.universal_region_relations.outlives(r1, r2); | |
747 | let r2_outlives_r1 = self.universal_region_relations.outlives(r2, r1); | |
60c5eb7d XL |
748 | match (r1_outlives_r2, r2_outlives_r1) { |
749 | (true, true) => Some(r1.min(r2)), | |
750 | (true, false) => Some(r2), | |
751 | (false, true) => Some(r1), | |
752 | (false, false) => None, | |
dc9dc135 XL |
753 | } |
754 | }; | |
755 | let mut min_choice = choice_regions[0]; | |
756 | for &other_option in &choice_regions[1..] { | |
c295e0f8 | 757 | debug!(?min_choice, ?other_option,); |
dc9dc135 XL |
758 | match min(min_choice, other_option) { |
759 | Some(m) => min_choice = m, | |
760 | None => { | |
c295e0f8 | 761 | debug!(?min_choice, ?other_option, "incomparable; no min choice",); |
dc9dc135 XL |
762 | return false; |
763 | } | |
764 | } | |
765 | } | |
766 | ||
767 | let min_choice_scc = self.constraint_sccs.scc(min_choice); | |
c295e0f8 | 768 | debug!(?min_choice, ?min_choice_scc); |
dc9dc135 XL |
769 | if self.scc_values.add_region(scc, min_choice_scc) { |
770 | self.member_constraints_applied.push(AppliedMemberConstraint { | |
771 | member_region_scc: scc, | |
772 | min_choice, | |
773 | member_constraint_index, | |
774 | }); | |
775 | ||
776 | true | |
777 | } else { | |
778 | false | |
779 | } | |
780 | } | |
781 | ||
9fa01778 | 782 | /// Returns `true` if all the elements in the value of `scc_b` are nameable |
8faf50e0 XL |
783 | /// in `scc_a`. Used during constraint propagation, and only once |
784 | /// the value of `scc_b` has been computed. | |
785 | fn universe_compatible(&self, scc_b: ConstraintSccIndex, scc_a: ConstraintSccIndex) -> bool { | |
786 | let universe_a = self.scc_universes[scc_a]; | |
787 | ||
788 | // Quick check: if scc_b's declared universe is a subset of | |
789 | // scc_a's declared univese (typically, both are ROOT), then | |
790 | // it cannot contain any problematic universe elements. | |
0bf4aa26 | 791 | if universe_a.can_name(self.scc_universes[scc_b]) { |
8faf50e0 | 792 | return true; |
2c00a5a8 XL |
793 | } |
794 | ||
8faf50e0 XL |
795 | // Otherwise, we have to iterate over the universe elements in |
796 | // B's value, and check whether all of them are nameable | |
797 | // from universe_a | |
dc9dc135 | 798 | self.scc_values.placeholders_contained_in(scc_b).all(|p| universe_a.can_name(p.universe)) |
2c00a5a8 XL |
799 | } |
800 | ||
b7449926 XL |
801 | /// Extend `scc` so that it can outlive some placeholder region |
802 | /// from a universe it can't name; at present, the only way for | |
803 | /// this to be true is if `scc` outlives `'static`. This is | |
804 | /// actually stricter than necessary: ideally, we'd support bounds | |
805 | /// like `for<'a: 'b`>` that might then allow us to approximate | |
806 | /// `'a` with `'b` and not `'static`. But it will have to do for | |
807 | /// now. | |
808 | fn add_incompatible_universe(&mut self, scc: ConstraintSccIndex) { | |
a1dfa0c6 XL |
809 | debug!("add_incompatible_universe(scc={:?})", scc); |
810 | ||
b7449926 XL |
811 | let fr_static = self.universal_regions.fr_static; |
812 | self.scc_values.add_all_points(scc); | |
813 | self.scc_values.add_element(scc, fr_static); | |
814 | } | |
815 | ||
ff7c6d11 XL |
816 | /// Once regions have been propagated, this method is used to see |
817 | /// whether the "type tests" produced by typeck were satisfied; | |
818 | /// type tests encode type-outlives relationships like `T: | |
819 | /// 'a`. See `TypeTest` for more details. | |
dc9dc135 | 820 | fn check_type_tests( |
ff7c6d11 | 821 | &self, |
dc9dc135 XL |
822 | infcx: &InferCtxt<'_, 'tcx>, |
823 | body: &Body<'tcx>, | |
dc9dc135 | 824 | mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 825 | errors_buffer: &mut RegionErrors<'tcx>, |
ff7c6d11 XL |
826 | ) { |
827 | let tcx = infcx.tcx; | |
828 | ||
0bf4aa26 XL |
829 | // Sometimes we register equivalent type-tests that would |
830 | // result in basically the exact same error being reported to | |
831 | // the user. Avoid that. | |
832 | let mut deduplicate_errors = FxHashSet::default(); | |
833 | ||
ff7c6d11 XL |
834 | for type_test in &self.type_tests { |
835 | debug!("check_type_test: {:?}", type_test); | |
836 | ||
0bf4aa26 XL |
837 | let generic_ty = type_test.generic_kind.to_ty(tcx); |
838 | if self.eval_verify_bound( | |
839 | tcx, | |
dc9dc135 | 840 | body, |
0bf4aa26 XL |
841 | generic_ty, |
842 | type_test.lower_bound, | |
843 | &type_test.verify_bound, | |
844 | ) { | |
ff7c6d11 XL |
845 | continue; |
846 | } | |
847 | ||
848 | if let Some(propagated_outlives_requirements) = &mut propagated_outlives_requirements { | |
8faf50e0 XL |
849 | if self.try_promote_type_test( |
850 | infcx, | |
dc9dc135 | 851 | body, |
8faf50e0 XL |
852 | type_test, |
853 | propagated_outlives_requirements, | |
854 | ) { | |
ff7c6d11 XL |
855 | continue; |
856 | } | |
857 | } | |
858 | ||
0bf4aa26 | 859 | // Type-test failed. Report the error. |
fc512014 | 860 | let erased_generic_kind = infcx.tcx.erase_regions(type_test.generic_kind); |
0bf4aa26 XL |
861 | |
862 | // Skip duplicate-ish errors. | |
dfeec247 | 863 | if deduplicate_errors.insert(( |
0bf4aa26 | 864 | erased_generic_kind, |
dfeec247 | 865 | type_test.lower_bound, |
0bf4aa26 XL |
866 | type_test.locations, |
867 | )) { | |
0bf4aa26 XL |
868 | debug!( |
869 | "check_type_test: reporting error for erased_generic_kind={:?}, \ | |
870 | lower_bound_region={:?}, \ | |
871 | type_test.locations={:?}", | |
dfeec247 | 872 | erased_generic_kind, type_test.lower_bound, type_test.locations, |
0bf4aa26 | 873 | ); |
ff7c6d11 | 874 | |
dfeec247 | 875 | errors_buffer.push(RegionErrorKind::TypeTestError { type_test: type_test.clone() }); |
ff7c6d11 XL |
876 | } |
877 | } | |
878 | } | |
879 | ||
b7449926 XL |
880 | /// Invoked when we have some type-test (e.g., `T: 'X`) that we cannot |
881 | /// prove to be satisfied. If this is a closure, we will attempt to | |
882 | /// "promote" this type-test into our `ClosureRegionRequirements` and | |
883 | /// hence pass it up the creator. To do this, we have to phrase the | |
884 | /// type-test in terms of external free regions, as local free | |
885 | /// regions are not nameable by the closure's creator. | |
886 | /// | |
887 | /// Promotion works as follows: we first check that the type `T` | |
888 | /// contains only regions that the creator knows about. If this is | |
889 | /// true, then -- as a consequence -- we know that all regions in | |
890 | /// the type `T` are free regions that outlive the closure body. If | |
891 | /// false, then promotion fails. | |
892 | /// | |
893 | /// Once we've promoted T, we have to "promote" `'X` to some region | |
894 | /// that is "external" to the closure. Generally speaking, a region | |
895 | /// may be the union of some points in the closure body as well as | |
896 | /// various free lifetimes. We can ignore the points in the closure | |
897 | /// body: if the type T can be expressed in terms of external regions, | |
898 | /// we know it outlives the points in the closure body. That | |
899 | /// just leaves the free regions. | |
900 | /// | |
901 | /// The idea then is to lower the `T: 'X` constraint into multiple | |
902 | /// bounds -- e.g., if `'X` is the union of two free lifetimes, | |
903 | /// `'1` and `'2`, then we would create `T: '1` and `T: '2`. | |
dc9dc135 | 904 | fn try_promote_type_test( |
ff7c6d11 | 905 | &self, |
dc9dc135 XL |
906 | infcx: &InferCtxt<'_, 'tcx>, |
907 | body: &Body<'tcx>, | |
ff7c6d11 | 908 | type_test: &TypeTest<'tcx>, |
dc9dc135 | 909 | propagated_outlives_requirements: &mut Vec<ClosureOutlivesRequirement<'tcx>>, |
ff7c6d11 XL |
910 | ) -> bool { |
911 | let tcx = infcx.tcx; | |
912 | ||
dc9dc135 | 913 | let TypeTest { generic_kind, lower_bound, locations, verify_bound: _ } = type_test; |
ff7c6d11 XL |
914 | |
915 | let generic_ty = generic_kind.to_ty(tcx); | |
916 | let subject = match self.try_promote_type_test_subject(infcx, generic_ty) { | |
917 | Some(s) => s, | |
918 | None => return false, | |
919 | }; | |
920 | ||
b7449926 XL |
921 | // For each region outlived by lower_bound find a non-local, |
922 | // universal region (it may be the same region) and add it to | |
923 | // `ClosureOutlivesRequirement`. | |
924 | let r_scc = self.constraint_sccs.scc(*lower_bound); | |
925 | for ur in self.scc_values.universal_regions_outlived_by(r_scc) { | |
926 | // Check whether we can already prove that the "subject" outlives `ur`. | |
927 | // If so, we don't have to propagate this requirement to our caller. | |
928 | // | |
929 | // To continue the example from the function, if we are trying to promote | |
930 | // a requirement that `T: 'X`, and we know that `'X = '1 + '2` (i.e., the union | |
931 | // `'1` and `'2`), then in this loop `ur` will be `'1` (and `'2`). So here | |
932 | // we check whether `T: '1` is something we *can* prove. If so, no need | |
933 | // to propagate that requirement. | |
934 | // | |
935 | // This is needed because -- particularly in the case | |
936 | // where `ur` is a local bound -- we are sometimes in a | |
937 | // position to prove things that our caller cannot. See | |
938 | // #53570 for an example. | |
dc9dc135 | 939 | if self.eval_verify_bound(tcx, body, generic_ty, ur, &type_test.verify_bound) { |
b7449926 XL |
940 | continue; |
941 | } | |
ff7c6d11 | 942 | |
b7449926 XL |
943 | debug!("try_promote_type_test: ur={:?}", ur); |
944 | ||
9fa01778 | 945 | let non_local_ub = self.universal_region_relations.non_local_upper_bounds(&ur); |
b7449926 XL |
946 | debug!("try_promote_type_test: non_local_ub={:?}", non_local_ub); |
947 | ||
9fa01778 XL |
948 | // This is slightly too conservative. To show T: '1, given `'2: '1` |
949 | // and `'3: '1` we only need to prove that T: '2 *or* T: '3, but to | |
950 | // avoid potential non-determinism we approximate this by requiring | |
951 | // T: '1 and T: '2. | |
952 | for &upper_bound in non_local_ub { | |
953 | debug_assert!(self.universal_regions.is_universal_region(upper_bound)); | |
954 | debug_assert!(!self.universal_regions.is_local_free_region(upper_bound)); | |
955 | ||
956 | let requirement = ClosureOutlivesRequirement { | |
957 | subject, | |
958 | outlived_free_region: upper_bound, | |
dc9dc135 | 959 | blame_span: locations.span(body), |
9fa01778 XL |
960 | category: ConstraintCategory::Boring, |
961 | }; | |
962 | debug!("try_promote_type_test: pushing {:#?}", requirement); | |
963 | propagated_outlives_requirements.push(requirement); | |
964 | } | |
b7449926 | 965 | } |
ff7c6d11 XL |
966 | true |
967 | } | |
968 | ||
969 | /// When we promote a type test `T: 'r`, we have to convert the | |
970 | /// type `T` into something we can store in a query result (so | |
dc9dc135 | 971 | /// something allocated for `'tcx`). This is problematic if `ty` |
ff7c6d11 XL |
972 | /// contains regions. During the course of NLL region checking, we |
973 | /// will have replaced all of those regions with fresh inference | |
974 | /// variables. To create a test subject, we want to replace those | |
975 | /// inference variables with some region from the closure | |
976 | /// signature -- this is not always possible, so this is a | |
977 | /// fallible process. Presuming we do find a suitable region, we | |
ba9703b0 XL |
978 | /// will use it's *external name*, which will be a `RegionKind` |
979 | /// variant that can be used in query responses such as | |
980 | /// `ReEarlyBound`. | |
dc9dc135 | 981 | fn try_promote_type_test_subject( |
ff7c6d11 | 982 | &self, |
dc9dc135 | 983 | infcx: &InferCtxt<'_, 'tcx>, |
ff7c6d11 | 984 | ty: Ty<'tcx>, |
dc9dc135 | 985 | ) -> Option<ClosureOutlivesSubject<'tcx>> { |
ff7c6d11 | 986 | let tcx = infcx.tcx; |
ff7c6d11 XL |
987 | |
988 | debug!("try_promote_type_test_subject(ty = {:?})", ty); | |
989 | ||
fc512014 | 990 | let ty = tcx.fold_regions(ty, &mut false, |r, _depth| { |
ff7c6d11 XL |
991 | let region_vid = self.to_region_vid(r); |
992 | ||
993 | // The challenge if this. We have some region variable `r` | |
994 | // whose value is a set of CFG points and universal | |
995 | // regions. We want to find if that set is *equivalent* to | |
996 | // any of the named regions found in the closure. | |
997 | // | |
998 | // To do so, we compute the | |
999 | // `non_local_universal_upper_bound`. This will be a | |
1000 | // non-local, universal region that is greater than `r`. | |
1001 | // However, it might not be *contained* within `r`, so | |
1002 | // then we further check whether this bound is contained | |
1003 | // in `r`. If so, we can say that `r` is equivalent to the | |
1004 | // bound. | |
1005 | // | |
1006 | // Let's work through a few examples. For these, imagine | |
1007 | // that we have 3 non-local regions (I'll denote them as | |
1008 | // `'static`, `'a`, and `'b`, though of course in the code | |
1009 | // they would be represented with indices) where: | |
1010 | // | |
1011 | // - `'static: 'a` | |
1012 | // - `'static: 'b` | |
1013 | // | |
1014 | // First, let's assume that `r` is some existential | |
1015 | // variable with an inferred value `{'a, 'static}` (plus | |
1016 | // some CFG nodes). In this case, the non-local upper | |
1017 | // bound is `'static`, since that outlives `'a`. `'static` | |
1018 | // is also a member of `r` and hence we consider `r` | |
1019 | // equivalent to `'static` (and replace it with | |
1020 | // `'static`). | |
1021 | // | |
1022 | // Now let's consider the inferred value `{'a, 'b}`. This | |
1023 | // means `r` is effectively `'a | 'b`. I'm not sure if | |
1024 | // this can come about, actually, but assuming it did, we | |
1025 | // would get a non-local upper bound of `'static`. Since | |
1026 | // `'static` is not contained in `r`, we would fail to | |
1027 | // find an equivalent. | |
1028 | let upper_bound = self.non_local_universal_upper_bound(region_vid); | |
8faf50e0 | 1029 | if self.region_contains(region_vid, upper_bound) { |
ba9703b0 | 1030 | self.definitions[upper_bound].external_name.unwrap_or(r) |
ff7c6d11 | 1031 | } else { |
ba9703b0 XL |
1032 | // In the case of a failure, use a `ReVar` result. This will |
1033 | // cause the `needs_infer` later on to return `None`. | |
ff7c6d11 XL |
1034 | r |
1035 | } | |
1036 | }); | |
ba9703b0 | 1037 | |
ff7c6d11 XL |
1038 | debug!("try_promote_type_test_subject: folded ty = {:?}", ty); |
1039 | ||
ba9703b0 XL |
1040 | // `needs_infer` will only be true if we failed to promote some region. |
1041 | if ty.needs_infer() { | |
dc9dc135 XL |
1042 | return None; |
1043 | } | |
ff7c6d11 XL |
1044 | |
1045 | Some(ClosureOutlivesSubject::Ty(ty)) | |
1046 | } | |
1047 | ||
1048 | /// Given some universal or existential region `r`, finds a | |
1049 | /// non-local, universal region `r+` that outlives `r` at entry to (and | |
1050 | /// exit from) the closure. In the worst case, this will be | |
1051 | /// `'static`. | |
1052 | /// | |
1053 | /// This is used for two purposes. First, if we are propagated | |
1054 | /// some requirement `T: r`, we can use this method to enlarge `r` | |
1055 | /// to something we can encode for our creator (which only knows | |
1056 | /// about non-local, universal regions). It is also used when | |
1057 | /// encoding `T` as part of `try_promote_type_test_subject` (see | |
1058 | /// that fn for details). | |
1059 | /// | |
1060 | /// This is based on the result `'y` of `universal_upper_bound`, | |
1061 | /// except that it converts further takes the non-local upper | |
1062 | /// bound of `'y`, so that the final result is non-local. | |
1063 | fn non_local_universal_upper_bound(&self, r: RegionVid) -> RegionVid { | |
dc9dc135 | 1064 | debug!("non_local_universal_upper_bound(r={:?}={})", r, self.region_value_str(r)); |
ff7c6d11 XL |
1065 | |
1066 | let lub = self.universal_upper_bound(r); | |
1067 | ||
1068 | // Grow further to get smallest universal region known to | |
1069 | // creator. | |
8faf50e0 | 1070 | let non_local_lub = self.universal_region_relations.non_local_upper_bound(lub); |
ff7c6d11 | 1071 | |
dc9dc135 | 1072 | debug!("non_local_universal_upper_bound: non_local_lub={:?}", non_local_lub); |
ff7c6d11 XL |
1073 | |
1074 | non_local_lub | |
1075 | } | |
1076 | ||
1077 | /// Returns a universally quantified region that outlives the | |
1078 | /// value of `r` (`r` may be existentially or universally | |
1079 | /// quantified). | |
1080 | /// | |
1081 | /// Since `r` is (potentially) an existential region, it has some | |
1082 | /// value which may include (a) any number of points in the CFG | |
1083 | /// and (b) any number of `end('x)` elements of universally | |
1084 | /// quantified regions. To convert this into a single universal | |
1085 | /// region we do as follows: | |
1086 | /// | |
1087 | /// - Ignore the CFG points in `'r`. All universally quantified regions | |
1088 | /// include the CFG anyhow. | |
1089 | /// - For each `end('x)` element in `'r`, compute the mutual LUB, yielding | |
1090 | /// a result `'y`. | |
c295e0f8 XL |
1091 | #[instrument(skip(self), level = "debug")] |
1092 | pub(crate) fn universal_upper_bound(&self, r: RegionVid) -> RegionVid { | |
1093 | debug!(r = %self.region_value_str(r)); | |
ff7c6d11 XL |
1094 | |
1095 | // Find the smallest universal region that contains all other | |
1096 | // universal regions within `region`. | |
1097 | let mut lub = self.universal_regions.fr_fn_body; | |
8faf50e0 XL |
1098 | let r_scc = self.constraint_sccs.scc(r); |
1099 | for ur in self.scc_values.universal_regions_outlived_by(r_scc) { | |
1100 | lub = self.universal_region_relations.postdom_upper_bound(lub, ur); | |
ff7c6d11 XL |
1101 | } |
1102 | ||
c295e0f8 | 1103 | debug!(?lub); |
ff7c6d11 XL |
1104 | |
1105 | lub | |
1106 | } | |
1107 | ||
f035d41b XL |
1108 | /// Like `universal_upper_bound`, but returns an approximation more suitable |
1109 | /// for diagnostics. If `r` contains multiple disjoint universal regions | |
1110 | /// (e.g. 'a and 'b in `fn foo<'a, 'b> { ... }`, we pick the lower-numbered region. | |
1111 | /// This corresponds to picking named regions over unnamed regions | |
1112 | /// (e.g. picking early-bound regions over a closure late-bound region). | |
1113 | /// | |
1114 | /// This means that the returned value may not be a true upper bound, since | |
1115 | /// only 'static is known to outlive disjoint universal regions. | |
1116 | /// Therefore, this method should only be used in diagnostic code, | |
1117 | /// where displaying *some* named universal region is better than | |
1118 | /// falling back to 'static. | |
c295e0f8 | 1119 | pub(crate) fn approx_universal_upper_bound(&self, r: RegionVid) -> RegionVid { |
f035d41b XL |
1120 | debug!("approx_universal_upper_bound(r={:?}={})", r, self.region_value_str(r)); |
1121 | ||
1122 | // Find the smallest universal region that contains all other | |
1123 | // universal regions within `region`. | |
1124 | let mut lub = self.universal_regions.fr_fn_body; | |
1125 | let r_scc = self.constraint_sccs.scc(r); | |
1126 | let static_r = self.universal_regions.fr_static; | |
1127 | for ur in self.scc_values.universal_regions_outlived_by(r_scc) { | |
1128 | let new_lub = self.universal_region_relations.postdom_upper_bound(lub, ur); | |
1129 | debug!("approx_universal_upper_bound: ur={:?} lub={:?} new_lub={:?}", ur, lub, new_lub); | |
fc512014 XL |
1130 | // The upper bound of two non-static regions is static: this |
1131 | // means we know nothing about the relationship between these | |
1132 | // two regions. Pick a 'better' one to use when constructing | |
1133 | // a diagnostic | |
f035d41b | 1134 | if ur != static_r && lub != static_r && new_lub == static_r { |
fc512014 XL |
1135 | // Prefer the region with an `external_name` - this |
1136 | // indicates that the region is early-bound, so working with | |
1137 | // it can produce a nicer error. | |
1138 | if self.region_definition(ur).external_name.is_some() { | |
1139 | lub = ur; | |
1140 | } else if self.region_definition(lub).external_name.is_some() { | |
1141 | // Leave lub unchanged | |
1142 | } else { | |
1143 | // If we get here, we don't have any reason to prefer | |
1144 | // one region over the other. Just pick the | |
1145 | // one with the lower index for now. | |
1146 | lub = std::cmp::min(ur, lub); | |
1147 | } | |
f035d41b XL |
1148 | } else { |
1149 | lub = new_lub; | |
1150 | } | |
1151 | } | |
1152 | ||
1153 | debug!("approx_universal_upper_bound: r={:?} lub={:?}", r, lub); | |
1154 | ||
1155 | lub | |
1156 | } | |
1157 | ||
9fa01778 XL |
1158 | /// Tests if `test` is true when applied to `lower_bound` at |
1159 | /// `point`. | |
0bf4aa26 XL |
1160 | fn eval_verify_bound( |
1161 | &self, | |
dc9dc135 XL |
1162 | tcx: TyCtxt<'tcx>, |
1163 | body: &Body<'tcx>, | |
0bf4aa26 XL |
1164 | generic_ty: Ty<'tcx>, |
1165 | lower_bound: RegionVid, | |
1166 | verify_bound: &VerifyBound<'tcx>, | |
1167 | ) -> bool { | |
dc9dc135 | 1168 | debug!("eval_verify_bound(lower_bound={:?}, verify_bound={:?})", lower_bound, verify_bound); |
ff7c6d11 | 1169 | |
0bf4aa26 XL |
1170 | match verify_bound { |
1171 | VerifyBound::IfEq(test_ty, verify_bound1) => { | |
5099ac24 | 1172 | self.eval_if_eq(tcx, body, generic_ty, lower_bound, *test_ty, verify_bound1) |
0bf4aa26 XL |
1173 | } |
1174 | ||
74b04a01 XL |
1175 | VerifyBound::IsEmpty => { |
1176 | let lower_bound_scc = self.constraint_sccs.scc(lower_bound); | |
1177 | self.scc_values.elements_contained_in(lower_bound_scc).next().is_none() | |
1178 | } | |
1179 | ||
0bf4aa26 | 1180 | VerifyBound::OutlivedBy(r) => { |
5099ac24 | 1181 | let r_vid = self.to_region_vid(*r); |
dc9dc135 | 1182 | self.eval_outlives(r_vid, lower_bound) |
0bf4aa26 | 1183 | } |
ff7c6d11 | 1184 | |
0bf4aa26 | 1185 | VerifyBound::AnyBound(verify_bounds) => verify_bounds.iter().any(|verify_bound| { |
dc9dc135 | 1186 | self.eval_verify_bound(tcx, body, generic_ty, lower_bound, verify_bound) |
0bf4aa26 | 1187 | }), |
ff7c6d11 | 1188 | |
0bf4aa26 | 1189 | VerifyBound::AllBounds(verify_bounds) => verify_bounds.iter().all(|verify_bound| { |
dc9dc135 | 1190 | self.eval_verify_bound(tcx, body, generic_ty, lower_bound, verify_bound) |
0bf4aa26 XL |
1191 | }), |
1192 | } | |
1193 | } | |
ff7c6d11 | 1194 | |
0bf4aa26 XL |
1195 | fn eval_if_eq( |
1196 | &self, | |
dc9dc135 XL |
1197 | tcx: TyCtxt<'tcx>, |
1198 | body: &Body<'tcx>, | |
0bf4aa26 XL |
1199 | generic_ty: Ty<'tcx>, |
1200 | lower_bound: RegionVid, | |
1201 | test_ty: Ty<'tcx>, | |
1202 | verify_bound: &VerifyBound<'tcx>, | |
1203 | ) -> bool { | |
1204 | let generic_ty_normalized = self.normalize_to_scc_representatives(tcx, generic_ty); | |
1205 | let test_ty_normalized = self.normalize_to_scc_representatives(tcx, test_ty); | |
1206 | if generic_ty_normalized == test_ty_normalized { | |
dc9dc135 | 1207 | self.eval_verify_bound(tcx, body, generic_ty, lower_bound, verify_bound) |
0bf4aa26 XL |
1208 | } else { |
1209 | false | |
ff7c6d11 XL |
1210 | } |
1211 | } | |
1212 | ||
0bf4aa26 XL |
1213 | /// This is a conservative normalization procedure. It takes every |
1214 | /// free region in `value` and replaces it with the | |
1215 | /// "representative" of its SCC (see `scc_representatives` field). | |
1216 | /// We are guaranteed that if two values normalize to the same | |
1217 | /// thing, then they are equal; this is a conservative check in | |
1218 | /// that they could still be equal even if they normalize to | |
1219 | /// different results. (For example, there might be two regions | |
1220 | /// with the same value that are not in the same SCC). | |
1221 | /// | |
9fa01778 | 1222 | /// N.B., this is not an ideal approach and I would like to revisit |
0bf4aa26 XL |
1223 | /// it. However, it works pretty well in practice. In particular, |
1224 | /// this is needed to deal with projection outlives bounds like | |
1225 | /// | |
17df50a5 | 1226 | /// ```text |
29967ef6 XL |
1227 | /// <T as Foo<'0>>::Item: '1 |
1228 | /// ``` | |
0bf4aa26 XL |
1229 | /// |
1230 | /// In particular, this routine winds up being important when | |
1231 | /// there are bounds like `where <T as Foo<'a>>::Item: 'b` in the | |
9fa01778 | 1232 | /// environment. In this case, if we can show that `'0 == 'a`, |
0bf4aa26 XL |
1233 | /// and that `'b: '1`, then we know that the clause is |
1234 | /// satisfied. In such cases, particularly due to limitations of | |
1235 | /// the trait solver =), we usually wind up with a where-clause like | |
1236 | /// `T: Foo<'a>` in scope, which thus forces `'0 == 'a` to be added as | |
1237 | /// a constraint, and thus ensures that they are in the same SCC. | |
1238 | /// | |
1239 | /// So why can't we do a more correct routine? Well, we could | |
1240 | /// *almost* use the `relate_tys` code, but the way it is | |
1241 | /// currently setup it creates inference variables to deal with | |
1242 | /// higher-ranked things and so forth, and right now the inference | |
1243 | /// context is not permitted to make more inference variables. So | |
1244 | /// we use this kind of hacky solution. | |
dc9dc135 | 1245 | fn normalize_to_scc_representatives<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T |
0bf4aa26 XL |
1246 | where |
1247 | T: TypeFoldable<'tcx>, | |
1248 | { | |
fc512014 | 1249 | tcx.fold_regions(value, &mut false, |r, _db| { |
0bf4aa26 XL |
1250 | let vid = self.to_region_vid(r); |
1251 | let scc = self.constraint_sccs.scc(vid); | |
1252 | let repr = self.scc_representatives[scc]; | |
1253 | tcx.mk_region(ty::ReVar(repr)) | |
1254 | }) | |
1255 | } | |
1256 | ||
dc9dc135 XL |
1257 | // Evaluate whether `sup_region == sub_region`. |
1258 | fn eval_equal(&self, r1: RegionVid, r2: RegionVid) -> bool { | |
1259 | self.eval_outlives(r1, r2) && self.eval_outlives(r2, r1) | |
1260 | } | |
1261 | ||
1262 | // Evaluate whether `sup_region: sub_region`. | |
c295e0f8 | 1263 | #[instrument(skip(self), level = "debug")] |
dc9dc135 | 1264 | fn eval_outlives(&self, sup_region: RegionVid, sub_region: RegionVid) -> bool { |
94b46f34 | 1265 | debug!( |
dc9dc135 | 1266 | "eval_outlives: sup_region's value = {:?} universal={:?}", |
8faf50e0 | 1267 | self.region_value_str(sup_region), |
dc9dc135 | 1268 | self.universal_regions.is_universal_region(sup_region), |
94b46f34 XL |
1269 | ); |
1270 | debug!( | |
dc9dc135 | 1271 | "eval_outlives: sub_region's value = {:?} universal={:?}", |
8faf50e0 | 1272 | self.region_value_str(sub_region), |
dc9dc135 | 1273 | self.universal_regions.is_universal_region(sub_region), |
94b46f34 XL |
1274 | ); |
1275 | ||
8faf50e0 XL |
1276 | let sub_region_scc = self.constraint_sccs.scc(sub_region); |
1277 | let sup_region_scc = self.constraint_sccs.scc(sup_region); | |
1278 | ||
94b46f34 XL |
1279 | // Both the `sub_region` and `sup_region` consist of the union |
1280 | // of some number of universal regions (along with the union | |
1281 | // of various points in the CFG; ignore those points for | |
1282 | // now). Therefore, the sup-region outlives the sub-region if, | |
1283 | // for each universal region R1 in the sub-region, there | |
1284 | // exists some region R2 in the sup-region that outlives R1. | |
dc9dc135 XL |
1285 | let universal_outlives = |
1286 | self.scc_values.universal_regions_outlived_by(sub_region_scc).all(|r1| { | |
8faf50e0 XL |
1287 | self.scc_values |
1288 | .universal_regions_outlived_by(sup_region_scc) | |
1289 | .any(|r2| self.universal_region_relations.outlives(r2, r1)) | |
94b46f34 XL |
1290 | }); |
1291 | ||
1292 | if !universal_outlives { | |
1293 | return false; | |
ff7c6d11 | 1294 | } |
94b46f34 XL |
1295 | |
1296 | // Now we have to compare all the points in the sub region and make | |
1297 | // sure they exist in the sup region. | |
1298 | ||
1299 | if self.universal_regions.is_universal_region(sup_region) { | |
1300 | // Micro-opt: universal regions contain all points. | |
1301 | return true; | |
1302 | } | |
1303 | ||
dc9dc135 | 1304 | self.scc_values.contains_points(sup_region_scc, sub_region_scc) |
ff7c6d11 XL |
1305 | } |
1306 | ||
1307 | /// Once regions have been propagated, this method is used to see | |
1308 | /// whether any of the constraints were too strong. In particular, | |
1309 | /// we want to check for a case where a universally quantified | |
9fa01778 | 1310 | /// region exceeded its bounds. Consider: |
ff7c6d11 XL |
1311 | /// |
1312 | /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } | |
1313 | /// | |
1314 | /// In this case, returning `x` requires `&'a u32 <: &'b u32` | |
1315 | /// and hence we establish (transitively) a constraint that | |
1316 | /// `'a: 'b`. The `propagate_constraints` code above will | |
1317 | /// therefore add `end('a)` into the region for `'b` -- but we | |
1318 | /// have no evidence that `'b` outlives `'a`, so we want to report | |
1319 | /// an error. | |
1320 | /// | |
1321 | /// If `propagated_outlives_requirements` is `Some`, then we will | |
1322 | /// push unsatisfied obligations into there. Otherwise, we'll | |
1323 | /// report them as errors. | |
dc9dc135 | 1324 | fn check_universal_regions( |
ff7c6d11 | 1325 | &self, |
dc9dc135 | 1326 | body: &Body<'tcx>, |
dc9dc135 | 1327 | mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 1328 | errors_buffer: &mut RegionErrors<'tcx>, |
ff7c6d11 | 1329 | ) { |
8faf50e0 XL |
1330 | for (fr, fr_definition) in self.definitions.iter_enumerated() { |
1331 | match fr_definition.origin { | |
5869c6ff | 1332 | NllRegionVariableOrigin::FreeRegion => { |
8faf50e0 XL |
1333 | // Go through each of the universal regions `fr` and check that |
1334 | // they did not grow too large, accumulating any requirements | |
1335 | // for our caller into the `outlives_requirements` vector. | |
1336 | self.check_universal_region( | |
dc9dc135 | 1337 | body, |
8faf50e0 XL |
1338 | fr, |
1339 | &mut propagated_outlives_requirements, | |
1340 | errors_buffer, | |
1341 | ); | |
1342 | } | |
1343 | ||
5869c6ff | 1344 | NllRegionVariableOrigin::Placeholder(placeholder) => { |
dfeec247 | 1345 | self.check_bound_universal_region(fr, placeholder, errors_buffer); |
8faf50e0 XL |
1346 | } |
1347 | ||
5869c6ff XL |
1348 | NllRegionVariableOrigin::RootEmptyRegion |
1349 | | NllRegionVariableOrigin::Existential { .. } => { | |
8faf50e0 XL |
1350 | // nothing to check here |
1351 | } | |
1352 | } | |
ff7c6d11 | 1353 | } |
60c5eb7d XL |
1354 | } |
1355 | ||
1356 | /// Checks if Polonius has found any unexpected free region relations. | |
1357 | /// | |
1358 | /// In Polonius terms, a "subset error" (or "illegal subset relation error") is the equivalent | |
1359 | /// of NLL's "checking if any region constraints were too strong": a placeholder origin `'a` | |
1360 | /// was unexpectedly found to be a subset of another placeholder origin `'b`, and means in NLL | |
1361 | /// terms that the "longer free region" `'a` outlived the "shorter free region" `'b`. | |
1362 | /// | |
1363 | /// More details can be found in this blog post by Niko: | |
136023e0 | 1364 | /// <https://smallcultfollowing.com/babysteps/blog/2019/01/17/polonius-and-region-errors/> |
60c5eb7d XL |
1365 | /// |
1366 | /// In the canonical example | |
1367 | /// | |
1368 | /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } | |
1369 | /// | |
1370 | /// returning `x` requires `&'a u32 <: &'b u32` and hence we establish (transitively) a | |
1371 | /// constraint that `'a: 'b`. It is an error that we have no evidence that this | |
1372 | /// constraint holds. | |
1373 | /// | |
1374 | /// If `propagated_outlives_requirements` is `Some`, then we will | |
1375 | /// push unsatisfied obligations into there. Otherwise, we'll | |
1376 | /// report them as errors. | |
1377 | fn check_polonius_subset_errors( | |
1378 | &self, | |
60c5eb7d | 1379 | body: &Body<'tcx>, |
60c5eb7d | 1380 | mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 1381 | errors_buffer: &mut RegionErrors<'tcx>, |
60c5eb7d XL |
1382 | polonius_output: Rc<PoloniusOutput>, |
1383 | ) { | |
1384 | debug!( | |
1385 | "check_polonius_subset_errors: {} subset_errors", | |
1386 | polonius_output.subset_errors.len() | |
1387 | ); | |
1388 | ||
60c5eb7d XL |
1389 | // Similarly to `check_universal_regions`: a free region relation, which was not explicitly |
1390 | // declared ("known") was found by Polonius, so emit an error, or propagate the | |
1391 | // requirements for our caller into the `propagated_outlives_requirements` vector. | |
1392 | // | |
1393 | // Polonius doesn't model regions ("origins") as CFG-subsets or durations, but the | |
1394 | // `longer_fr` and `shorter_fr` terminology will still be used here, for consistency with | |
1395 | // the rest of the NLL infrastructure. The "subset origin" is the "longer free region", | |
1396 | // and the "superset origin" is the outlived "shorter free region". | |
1397 | // | |
1398 | // Note: Polonius will produce a subset error at every point where the unexpected | |
1399 | // `longer_fr`'s "placeholder loan" is contained in the `shorter_fr`. This can be helpful | |
1400 | // for diagnostics in the future, e.g. to point more precisely at the key locations | |
1401 | // requiring this constraint to hold. However, the error and diagnostics code downstream | |
1402 | // expects that these errors are not duplicated (and that they are in a certain order). | |
1403 | // Otherwise, diagnostics messages such as the ones giving names like `'1` to elided or | |
1404 | // anonymous lifetimes for example, could give these names differently, while others like | |
1405 | // the outlives suggestions or the debug output from `#[rustc_regions]` would be | |
1406 | // duplicated. The polonius subset errors are deduplicated here, while keeping the | |
1407 | // CFG-location ordering. | |
1408 | let mut subset_errors: Vec<_> = polonius_output | |
1409 | .subset_errors | |
1410 | .iter() | |
1411 | .flat_map(|(_location, subset_errors)| subset_errors.iter()) | |
1412 | .collect(); | |
1413 | subset_errors.sort(); | |
1414 | subset_errors.dedup(); | |
1415 | ||
1416 | for (longer_fr, shorter_fr) in subset_errors.into_iter() { | |
dfeec247 XL |
1417 | debug!( |
1418 | "check_polonius_subset_errors: subset_error longer_fr={:?},\ | |
1419 | shorter_fr={:?}", | |
1420 | longer_fr, shorter_fr | |
1421 | ); | |
60c5eb7d | 1422 | |
dfeec247 | 1423 | let propagated = self.try_propagate_universal_region_error( |
60c5eb7d XL |
1424 | *longer_fr, |
1425 | *shorter_fr, | |
60c5eb7d | 1426 | body, |
60c5eb7d | 1427 | &mut propagated_outlives_requirements, |
60c5eb7d | 1428 | ); |
dfeec247 XL |
1429 | if propagated == RegionRelationCheckResult::Error { |
1430 | errors_buffer.push(RegionErrorKind::RegionError { | |
1431 | longer_fr: *longer_fr, | |
1432 | shorter_fr: *shorter_fr, | |
5869c6ff | 1433 | fr_origin: NllRegionVariableOrigin::FreeRegion, |
dfeec247 XL |
1434 | is_reported: true, |
1435 | }); | |
1436 | } | |
60c5eb7d XL |
1437 | } |
1438 | ||
1439 | // Handle the placeholder errors as usual, until the chalk-rustc-polonius triumvirate has | |
1440 | // a more complete picture on how to separate this responsibility. | |
1441 | for (fr, fr_definition) in self.definitions.iter_enumerated() { | |
1442 | match fr_definition.origin { | |
5869c6ff | 1443 | NllRegionVariableOrigin::FreeRegion => { |
60c5eb7d XL |
1444 | // handled by polonius above |
1445 | } | |
1446 | ||
5869c6ff | 1447 | NllRegionVariableOrigin::Placeholder(placeholder) => { |
dfeec247 | 1448 | self.check_bound_universal_region(fr, placeholder, errors_buffer); |
60c5eb7d XL |
1449 | } |
1450 | ||
5869c6ff XL |
1451 | NllRegionVariableOrigin::RootEmptyRegion |
1452 | | NllRegionVariableOrigin::Existential { .. } => { | |
60c5eb7d XL |
1453 | // nothing to check here |
1454 | } | |
1455 | } | |
1456 | } | |
ff7c6d11 XL |
1457 | } |
1458 | ||
9fa01778 | 1459 | /// Checks the final value for the free region `fr` to see if it |
ff7c6d11 XL |
1460 | /// grew too large. In particular, examine what `end(X)` points |
1461 | /// wound up in `fr`'s final value; for each `end(X)` where `X != | |
1462 | /// fr`, we want to check that `fr: X`. If not, that's either an | |
1463 | /// error, or something we have to propagate to our creator. | |
1464 | /// | |
1465 | /// Things that are to be propagated are accumulated into the | |
1466 | /// `outlives_requirements` vector. | |
c295e0f8 XL |
1467 | #[instrument( |
1468 | skip(self, body, propagated_outlives_requirements, errors_buffer), | |
1469 | level = "debug" | |
1470 | )] | |
dc9dc135 | 1471 | fn check_universal_region( |
ff7c6d11 | 1472 | &self, |
dc9dc135 | 1473 | body: &Body<'tcx>, |
ff7c6d11 | 1474 | longer_fr: RegionVid, |
dc9dc135 | 1475 | propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 1476 | errors_buffer: &mut RegionErrors<'tcx>, |
ff7c6d11 | 1477 | ) { |
8faf50e0 XL |
1478 | let longer_fr_scc = self.constraint_sccs.scc(longer_fr); |
1479 | ||
1480 | // Because this free region must be in the ROOT universe, we | |
1481 | // know it cannot contain any bound universes. | |
1482 | assert!(self.scc_universes[longer_fr_scc] == ty::UniverseIndex::ROOT); | |
dc9dc135 | 1483 | debug_assert!(self.scc_values.placeholders_contained_in(longer_fr_scc).next().is_none()); |
8faf50e0 | 1484 | |
9fa01778 XL |
1485 | // Only check all of the relations for the main representative of each |
1486 | // SCC, otherwise just check that we outlive said representative. This | |
1487 | // reduces the number of redundant relations propagated out of | |
1488 | // closures. | |
1489 | // Note that the representative will be a universal region if there is | |
1490 | // one in this SCC, so we will always check the representative here. | |
1491 | let representative = self.scc_representatives[longer_fr_scc]; | |
1492 | if representative != longer_fr { | |
dfeec247 | 1493 | if let RegionRelationCheckResult::Error = self.check_universal_region_relation( |
9fa01778 XL |
1494 | longer_fr, |
1495 | representative, | |
dc9dc135 | 1496 | body, |
9fa01778 | 1497 | propagated_outlives_requirements, |
dfeec247 XL |
1498 | ) { |
1499 | errors_buffer.push(RegionErrorKind::RegionError { | |
1500 | longer_fr, | |
1501 | shorter_fr: representative, | |
5869c6ff | 1502 | fr_origin: NllRegionVariableOrigin::FreeRegion, |
dfeec247 XL |
1503 | is_reported: true, |
1504 | }); | |
1505 | } | |
9fa01778 XL |
1506 | return; |
1507 | } | |
1508 | ||
ff7c6d11 XL |
1509 | // Find every region `o` such that `fr: o` |
1510 | // (because `fr` includes `end(o)`). | |
dfeec247 | 1511 | let mut error_reported = false; |
8faf50e0 | 1512 | for shorter_fr in self.scc_values.universal_regions_outlived_by(longer_fr_scc) { |
dfeec247 | 1513 | if let RegionRelationCheckResult::Error = self.check_universal_region_relation( |
9fa01778 XL |
1514 | longer_fr, |
1515 | shorter_fr, | |
dc9dc135 | 1516 | body, |
9fa01778 | 1517 | propagated_outlives_requirements, |
9fa01778 | 1518 | ) { |
dfeec247 XL |
1519 | // We only report the first region error. Subsequent errors are hidden so as |
1520 | // not to overwhelm the user, but we do record them so as to potentially print | |
1521 | // better diagnostics elsewhere... | |
1522 | errors_buffer.push(RegionErrorKind::RegionError { | |
1523 | longer_fr, | |
1524 | shorter_fr, | |
5869c6ff | 1525 | fr_origin: NllRegionVariableOrigin::FreeRegion, |
dfeec247 XL |
1526 | is_reported: !error_reported, |
1527 | }); | |
1528 | ||
1529 | error_reported = true; | |
ff7c6d11 | 1530 | } |
9fa01778 XL |
1531 | } |
1532 | } | |
ff7c6d11 | 1533 | |
dfeec247 XL |
1534 | /// Checks that we can prove that `longer_fr: shorter_fr`. If we can't we attempt to propagate |
1535 | /// the constraint outward (e.g. to a closure environment), but if that fails, there is an | |
1536 | /// error. | |
9fa01778 XL |
1537 | fn check_universal_region_relation( |
1538 | &self, | |
1539 | longer_fr: RegionVid, | |
1540 | shorter_fr: RegionVid, | |
dc9dc135 | 1541 | body: &Body<'tcx>, |
dc9dc135 | 1542 | propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 1543 | ) -> RegionRelationCheckResult { |
9fa01778 | 1544 | // If it is known that `fr: o`, carry on. |
dc9dc135 | 1545 | if self.universal_region_relations.outlives(longer_fr, shorter_fr) { |
dfeec247 XL |
1546 | RegionRelationCheckResult::Ok |
1547 | } else { | |
1548 | // If we are not in a context where we can't propagate errors, or we | |
1549 | // could not shrink `fr` to something smaller, then just report an | |
1550 | // error. | |
1551 | // | |
1552 | // Note: in this case, we use the unapproximated regions to report the | |
1553 | // error. This gives better error messages in some cases. | |
1554 | self.try_propagate_universal_region_error( | |
1555 | longer_fr, | |
1556 | shorter_fr, | |
1557 | body, | |
1558 | propagated_outlives_requirements, | |
1559 | ) | |
9fa01778 | 1560 | } |
60c5eb7d XL |
1561 | } |
1562 | ||
dfeec247 XL |
1563 | /// Attempt to propagate a region error (e.g. `'a: 'b`) that is not met to a closure's |
1564 | /// creator. If we cannot, then the caller should report an error to the user. | |
1565 | fn try_propagate_universal_region_error( | |
60c5eb7d XL |
1566 | &self, |
1567 | longer_fr: RegionVid, | |
1568 | shorter_fr: RegionVid, | |
60c5eb7d | 1569 | body: &Body<'tcx>, |
60c5eb7d | 1570 | propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, |
dfeec247 | 1571 | ) -> RegionRelationCheckResult { |
9fa01778 XL |
1572 | if let Some(propagated_outlives_requirements) = propagated_outlives_requirements { |
1573 | // Shrink `longer_fr` until we find a non-local region (if we do). | |
1574 | // We'll call it `fr-` -- it's ever so slightly smaller than | |
1575 | // `longer_fr`. | |
dfeec247 XL |
1576 | if let Some(fr_minus) = self.universal_region_relations.non_local_lower_bound(longer_fr) |
1577 | { | |
1578 | debug!("try_propagate_universal_region_error: fr_minus={:?}", fr_minus); | |
9fa01778 | 1579 | |
dfeec247 XL |
1580 | let blame_span_category = self.find_outlives_blame_span( |
1581 | body, | |
1582 | longer_fr, | |
5869c6ff | 1583 | NllRegionVariableOrigin::FreeRegion, |
dfeec247 XL |
1584 | shorter_fr, |
1585 | ); | |
9fa01778 XL |
1586 | |
1587 | // Grow `shorter_fr` until we find some non-local regions. (We | |
1588 | // always will.) We'll call them `shorter_fr+` -- they're ever | |
1589 | // so slightly larger than `shorter_fr`. | |
dfeec247 XL |
1590 | let shorter_fr_plus = |
1591 | self.universal_region_relations.non_local_upper_bounds(&shorter_fr); | |
60c5eb7d | 1592 | debug!( |
dfeec247 | 1593 | "try_propagate_universal_region_error: shorter_fr_plus={:?}", |
60c5eb7d XL |
1594 | shorter_fr_plus |
1595 | ); | |
9fa01778 | 1596 | for &&fr in &shorter_fr_plus { |
ff7c6d11 XL |
1597 | // Push the constraint `fr-: shorter_fr+` |
1598 | propagated_outlives_requirements.push(ClosureOutlivesRequirement { | |
1599 | subject: ClosureOutlivesSubject::Region(fr_minus), | |
9fa01778 | 1600 | outlived_free_region: fr, |
c295e0f8 | 1601 | blame_span: blame_span_category.1.span, |
0bf4aa26 | 1602 | category: blame_span_category.0, |
ff7c6d11 | 1603 | }); |
ff7c6d11 | 1604 | } |
dfeec247 | 1605 | return RegionRelationCheckResult::Propagated; |
ff7c6d11 | 1606 | } |
ff7c6d11 | 1607 | } |
9fa01778 | 1608 | |
dfeec247 | 1609 | RegionRelationCheckResult::Error |
ff7c6d11 XL |
1610 | } |
1611 | ||
dc9dc135 | 1612 | fn check_bound_universal_region( |
ff7c6d11 | 1613 | &self, |
8faf50e0 | 1614 | longer_fr: RegionVid, |
a1dfa0c6 | 1615 | placeholder: ty::PlaceholderRegion, |
dfeec247 | 1616 | errors_buffer: &mut RegionErrors<'tcx>, |
ff7c6d11 | 1617 | ) { |
dc9dc135 | 1618 | debug!("check_bound_universal_region(fr={:?}, placeholder={:?})", longer_fr, placeholder,); |
8faf50e0 XL |
1619 | |
1620 | let longer_fr_scc = self.constraint_sccs.scc(longer_fr); | |
dc9dc135 | 1621 | debug!("check_bound_universal_region: longer_fr_scc={:?}", longer_fr_scc,); |
8faf50e0 XL |
1622 | |
1623 | // If we have some bound universal region `'a`, then the only | |
1624 | // elements it can contain is itself -- we don't know anything | |
1625 | // else about it! | |
1626 | let error_element = match { | |
dc9dc135 XL |
1627 | self.scc_values.elements_contained_in(longer_fr_scc).find(|element| match element { |
1628 | RegionElement::Location(_) => true, | |
1629 | RegionElement::RootUniversalRegion(_) => true, | |
1630 | RegionElement::PlaceholderRegion(placeholder1) => placeholder != *placeholder1, | |
1631 | }) | |
8faf50e0 XL |
1632 | } { |
1633 | Some(v) => v, | |
1634 | None => return, | |
ff7c6d11 | 1635 | }; |
a1dfa0c6 | 1636 | debug!("check_bound_universal_region: error_element = {:?}", error_element); |
ff7c6d11 | 1637 | |
8faf50e0 | 1638 | // Find the region that introduced this `error_element`. |
dfeec247 XL |
1639 | errors_buffer.push(RegionErrorKind::BoundUniversalRegionError { |
1640 | longer_fr, | |
1641 | error_element, | |
94222f64 | 1642 | placeholder, |
dfeec247 | 1643 | }); |
ff7c6d11 | 1644 | } |
dc9dc135 XL |
1645 | |
1646 | fn check_member_constraints( | |
1647 | &self, | |
1648 | infcx: &InferCtxt<'_, 'tcx>, | |
dfeec247 | 1649 | errors_buffer: &mut RegionErrors<'tcx>, |
dc9dc135 XL |
1650 | ) { |
1651 | let member_constraints = self.member_constraints.clone(); | |
1652 | for m_c_i in member_constraints.all_indices() { | |
1653 | debug!("check_member_constraint(m_c_i={:?})", m_c_i); | |
1654 | let m_c = &member_constraints[m_c_i]; | |
1655 | let member_region_vid = m_c.member_region_vid; | |
1656 | debug!( | |
1657 | "check_member_constraint: member_region_vid={:?} with value {}", | |
1658 | member_region_vid, | |
1659 | self.region_value_str(member_region_vid), | |
1660 | ); | |
1661 | let choice_regions = member_constraints.choice_regions(m_c_i); | |
1662 | debug!("check_member_constraint: choice_regions={:?}", choice_regions); | |
1663 | ||
1664 | // Did the member region wind up equal to any of the option regions? | |
dfeec247 XL |
1665 | if let Some(o) = |
1666 | choice_regions.iter().find(|&&o_r| self.eval_equal(o_r, m_c.member_region_vid)) | |
1667 | { | |
dc9dc135 XL |
1668 | debug!("check_member_constraint: evaluated as equal to {:?}", o); |
1669 | continue; | |
1670 | } | |
1671 | ||
1672 | // If not, report an error. | |
dc9dc135 | 1673 | let member_region = infcx.tcx.mk_region(ty::ReVar(member_region_vid)); |
dfeec247 | 1674 | errors_buffer.push(RegionErrorKind::UnexpectedHiddenRegion { |
74b04a01 | 1675 | span: m_c.definition_span, |
dfeec247 | 1676 | hidden_ty: m_c.hidden_ty, |
dc9dc135 | 1677 | member_region, |
dfeec247 | 1678 | }); |
dc9dc135 XL |
1679 | } |
1680 | } | |
dfeec247 XL |
1681 | |
1682 | /// We have a constraint `fr1: fr2` that is not satisfied, where | |
1683 | /// `fr2` represents some universal region. Here, `r` is some | |
1684 | /// region where we know that `fr1: r` and this function has the | |
1685 | /// job of determining whether `r` is "to blame" for the fact that | |
1686 | /// `fr1: fr2` is required. | |
1687 | /// | |
1688 | /// This is true under two conditions: | |
1689 | /// | |
1690 | /// - `r == fr2` | |
1691 | /// - `fr2` is `'static` and `r` is some placeholder in a universe | |
1692 | /// that cannot be named by `fr1`; in that case, we will require | |
1693 | /// that `fr1: 'static` because it is the only way to `fr1: r` to | |
1694 | /// be satisfied. (See `add_incompatible_universe`.) | |
1695 | crate fn provides_universal_region( | |
1696 | &self, | |
1697 | r: RegionVid, | |
1698 | fr1: RegionVid, | |
1699 | fr2: RegionVid, | |
1700 | ) -> bool { | |
1701 | debug!("provides_universal_region(r={:?}, fr1={:?}, fr2={:?})", r, fr1, fr2); | |
1702 | let result = { | |
1703 | r == fr2 || { | |
1704 | fr2 == self.universal_regions.fr_static && self.cannot_name_placeholder(fr1, r) | |
1705 | } | |
1706 | }; | |
1707 | debug!("provides_universal_region: result = {:?}", result); | |
1708 | result | |
1709 | } | |
1710 | ||
1711 | /// If `r2` represents a placeholder region, then this returns | |
1712 | /// `true` if `r1` cannot name that placeholder in its | |
1713 | /// value; otherwise, returns `false`. | |
1714 | crate fn cannot_name_placeholder(&self, r1: RegionVid, r2: RegionVid) -> bool { | |
1715 | debug!("cannot_name_value_of(r1={:?}, r2={:?})", r1, r2); | |
1716 | ||
1717 | match self.definitions[r2].origin { | |
5869c6ff | 1718 | NllRegionVariableOrigin::Placeholder(placeholder) => { |
dfeec247 XL |
1719 | let universe1 = self.definitions[r1].universe; |
1720 | debug!( | |
1721 | "cannot_name_value_of: universe1={:?} placeholder={:?}", | |
1722 | universe1, placeholder | |
1723 | ); | |
1724 | universe1.cannot_name(placeholder.universe) | |
1725 | } | |
1726 | ||
5869c6ff XL |
1727 | NllRegionVariableOrigin::RootEmptyRegion |
1728 | | NllRegionVariableOrigin::FreeRegion | |
1729 | | NllRegionVariableOrigin::Existential { .. } => false, | |
dfeec247 XL |
1730 | } |
1731 | } | |
1732 | ||
1733 | crate fn retrieve_closure_constraint_info( | |
1734 | &self, | |
1735 | body: &Body<'tcx>, | |
17df50a5 XL |
1736 | constraint: &OutlivesConstraint<'tcx>, |
1737 | ) -> BlameConstraint<'tcx> { | |
dfeec247 | 1738 | let loc = match constraint.locations { |
17df50a5 XL |
1739 | Locations::All(span) => { |
1740 | return BlameConstraint { | |
1741 | category: constraint.category, | |
1742 | from_closure: false, | |
c295e0f8 XL |
1743 | cause: ObligationCause::dummy_with_span(span), |
1744 | variance_info: constraint.variance_info, | |
17df50a5 XL |
1745 | }; |
1746 | } | |
dfeec247 XL |
1747 | Locations::Single(loc) => loc, |
1748 | }; | |
1749 | ||
1750 | let opt_span_category = | |
1751 | self.closure_bounds_mapping[&loc].get(&(constraint.sup, constraint.sub)); | |
17df50a5 XL |
1752 | opt_span_category |
1753 | .map(|&(category, span)| BlameConstraint { | |
1754 | category, | |
1755 | from_closure: true, | |
c295e0f8 XL |
1756 | cause: ObligationCause::dummy_with_span(span), |
1757 | variance_info: constraint.variance_info, | |
17df50a5 XL |
1758 | }) |
1759 | .unwrap_or(BlameConstraint { | |
1760 | category: constraint.category, | |
1761 | from_closure: false, | |
c295e0f8 XL |
1762 | cause: ObligationCause::dummy_with_span(body.source_info(loc).span), |
1763 | variance_info: constraint.variance_info, | |
17df50a5 | 1764 | }) |
dfeec247 XL |
1765 | } |
1766 | ||
c295e0f8 | 1767 | /// Finds a good `ObligationCause` to blame for the fact that `fr1` outlives `fr2`. |
dfeec247 XL |
1768 | crate fn find_outlives_blame_span( |
1769 | &self, | |
1770 | body: &Body<'tcx>, | |
1771 | fr1: RegionVid, | |
5869c6ff | 1772 | fr1_origin: NllRegionVariableOrigin, |
dfeec247 | 1773 | fr2: RegionVid, |
c295e0f8 XL |
1774 | ) -> (ConstraintCategory, ObligationCause<'tcx>) { |
1775 | let BlameConstraint { category, cause, .. } = | |
17df50a5 XL |
1776 | self.best_blame_constraint(body, fr1, fr1_origin, |r| { |
1777 | self.provides_universal_region(r, fr1, fr2) | |
1778 | }); | |
c295e0f8 | 1779 | (category, cause) |
dfeec247 XL |
1780 | } |
1781 | ||
1782 | /// Walks the graph of constraints (where `'a: 'b` is considered | |
1783 | /// an edge `'a -> 'b`) to find all paths from `from_region` to | |
1784 | /// `to_region`. The paths are accumulated into the vector | |
1785 | /// `results`. The paths are stored as a series of | |
1786 | /// `ConstraintIndex` values -- in other words, a list of *edges*. | |
1787 | /// | |
1788 | /// Returns: a series of constraints as well as the region `R` | |
1789 | /// that passed the target test. | |
1790 | crate fn find_constraint_paths_between_regions( | |
1791 | &self, | |
1792 | from_region: RegionVid, | |
1793 | target_test: impl Fn(RegionVid) -> bool, | |
17df50a5 | 1794 | ) -> Option<(Vec<OutlivesConstraint<'tcx>>, RegionVid)> { |
dfeec247 XL |
1795 | let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions); |
1796 | context[from_region] = Trace::StartRegion; | |
1797 | ||
1798 | // Use a deque so that we do a breadth-first search. We will | |
1799 | // stop at the first match, which ought to be the shortest | |
1800 | // path (fewest constraints). | |
1801 | let mut deque = VecDeque::new(); | |
1802 | deque.push_back(from_region); | |
1803 | ||
1804 | while let Some(r) = deque.pop_front() { | |
1805 | debug!( | |
1806 | "find_constraint_paths_between_regions: from_region={:?} r={:?} value={}", | |
1807 | from_region, | |
1808 | r, | |
1809 | self.region_value_str(r), | |
1810 | ); | |
1811 | ||
1812 | // Check if we reached the region we were looking for. If so, | |
1813 | // we can reconstruct the path that led to it and return it. | |
1814 | if target_test(r) { | |
1815 | let mut result = vec![]; | |
1816 | let mut p = r; | |
1817 | loop { | |
17df50a5 | 1818 | match context[p].clone() { |
dfeec247 XL |
1819 | Trace::NotVisited => { |
1820 | bug!("found unvisited region {:?} on path to {:?}", p, r) | |
1821 | } | |
1822 | ||
1823 | Trace::FromOutlivesConstraint(c) => { | |
dfeec247 | 1824 | p = c.sup; |
17df50a5 | 1825 | result.push(c); |
dfeec247 XL |
1826 | } |
1827 | ||
1828 | Trace::StartRegion => { | |
1829 | result.reverse(); | |
1830 | return Some((result, r)); | |
1831 | } | |
1832 | } | |
1833 | } | |
1834 | } | |
1835 | ||
1836 | // Otherwise, walk over the outgoing constraints and | |
1837 | // enqueue any regions we find, keeping track of how we | |
1838 | // reached them. | |
1839 | ||
1840 | // A constraint like `'r: 'x` can come from our constraint | |
1841 | // graph. | |
1842 | let fr_static = self.universal_regions.fr_static; | |
1843 | let outgoing_edges_from_graph = | |
1844 | self.constraint_graph.outgoing_edges(r, &self.constraints, fr_static); | |
1845 | ||
1846 | // Always inline this closure because it can be hot. | |
1847 | let mut handle_constraint = #[inline(always)] | |
17df50a5 | 1848 | |constraint: OutlivesConstraint<'tcx>| { |
dfeec247 XL |
1849 | debug_assert_eq!(constraint.sup, r); |
1850 | let sub_region = constraint.sub; | |
1851 | if let Trace::NotVisited = context[sub_region] { | |
1852 | context[sub_region] = Trace::FromOutlivesConstraint(constraint); | |
1853 | deque.push_back(sub_region); | |
1854 | } | |
1855 | }; | |
1856 | ||
1857 | // This loop can be hot. | |
1858 | for constraint in outgoing_edges_from_graph { | |
1859 | handle_constraint(constraint); | |
1860 | } | |
1861 | ||
1862 | // Member constraints can also give rise to `'r: 'x` edges that | |
1863 | // were not part of the graph initially, so watch out for those. | |
1864 | // (But they are extremely rare; this loop is very cold.) | |
1865 | for constraint in self.applied_member_constraints(r) { | |
1866 | let p_c = &self.member_constraints[constraint.member_constraint_index]; | |
1867 | let constraint = OutlivesConstraint { | |
1868 | sup: r, | |
1869 | sub: constraint.min_choice, | |
1870 | locations: Locations::All(p_c.definition_span), | |
1871 | category: ConstraintCategory::OpaqueType, | |
17df50a5 | 1872 | variance_info: ty::VarianceDiagInfo::default(), |
dfeec247 XL |
1873 | }; |
1874 | handle_constraint(constraint); | |
1875 | } | |
1876 | } | |
1877 | ||
1878 | None | |
1879 | } | |
1880 | ||
1881 | /// Finds some region R such that `fr1: R` and `R` is live at `elem`. | |
c295e0f8 | 1882 | #[instrument(skip(self), level = "trace")] |
dfeec247 | 1883 | crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid { |
c295e0f8 XL |
1884 | trace!(scc = ?self.constraint_sccs.scc(fr1)); |
1885 | trace!(universe = ?self.scc_universes[self.constraint_sccs.scc(fr1)]); | |
dfeec247 XL |
1886 | self.find_constraint_paths_between_regions(fr1, |r| { |
1887 | // First look for some `r` such that `fr1: r` and `r` is live at `elem` | |
c295e0f8 | 1888 | trace!(?r, liveness_constraints=?self.liveness_constraints.region_value_str(r)); |
dfeec247 XL |
1889 | self.liveness_constraints.contains(r, elem) |
1890 | }) | |
1891 | .or_else(|| { | |
1892 | // If we fail to find that, we may find some `r` such that | |
1893 | // `fr1: r` and `r` is a placeholder from some universe | |
1894 | // `fr1` cannot name. This would force `fr1` to be | |
1895 | // `'static`. | |
1896 | self.find_constraint_paths_between_regions(fr1, |r| { | |
1897 | self.cannot_name_placeholder(fr1, r) | |
1898 | }) | |
1899 | }) | |
1900 | .or_else(|| { | |
1901 | // If we fail to find THAT, it may be that `fr1` is a | |
1902 | // placeholder that cannot "fit" into its SCC. In that | |
f9f354fc | 1903 | // case, there should be some `r` where `fr1: r` and `fr1` is a |
dfeec247 XL |
1904 | // placeholder that `r` cannot name. We can blame that |
1905 | // edge. | |
f9f354fc XL |
1906 | // |
1907 | // Remember that if `R1: R2`, then the universe of R1 | |
1908 | // must be able to name the universe of R2, because R2 will | |
1909 | // be at least `'empty(Universe(R2))`, and `R1` must be at | |
1910 | // larger than that. | |
dfeec247 | 1911 | self.find_constraint_paths_between_regions(fr1, |r| { |
f9f354fc | 1912 | self.cannot_name_placeholder(r, fr1) |
dfeec247 XL |
1913 | }) |
1914 | }) | |
1915 | .map(|(_path, r)| r) | |
1916 | .unwrap() | |
1917 | } | |
1918 | ||
1919 | /// Get the region outlived by `longer_fr` and live at `element`. | |
94222f64 XL |
1920 | crate fn region_from_element( |
1921 | &self, | |
1922 | longer_fr: RegionVid, | |
1923 | element: &RegionElement, | |
1924 | ) -> RegionVid { | |
1925 | match *element { | |
dfeec247 XL |
1926 | RegionElement::Location(l) => self.find_sub_region_live_at(longer_fr, l), |
1927 | RegionElement::RootUniversalRegion(r) => r, | |
1928 | RegionElement::PlaceholderRegion(error_placeholder) => self | |
1929 | .definitions | |
1930 | .iter_enumerated() | |
f9f354fc | 1931 | .find_map(|(r, definition)| match definition.origin { |
5869c6ff | 1932 | NllRegionVariableOrigin::Placeholder(p) if p == error_placeholder => Some(r), |
dfeec247 XL |
1933 | _ => None, |
1934 | }) | |
dfeec247 XL |
1935 | .unwrap(), |
1936 | } | |
1937 | } | |
1938 | ||
1939 | /// Get the region definition of `r`. | |
1940 | crate fn region_definition(&self, r: RegionVid) -> &RegionDefinition<'tcx> { | |
1941 | &self.definitions[r] | |
1942 | } | |
1943 | ||
1944 | /// Check if the SCC of `r` contains `upper`. | |
1945 | crate fn upper_bound_in_region_scc(&self, r: RegionVid, upper: RegionVid) -> bool { | |
1946 | let r_scc = self.constraint_sccs.scc(r); | |
1947 | self.scc_values.contains(r_scc, upper) | |
1948 | } | |
1949 | ||
1950 | crate fn universal_regions(&self) -> &UniversalRegions<'tcx> { | |
1951 | self.universal_regions.as_ref() | |
1952 | } | |
1953 | ||
1954 | /// Tries to find the best constraint to blame for the fact that | |
1955 | /// `R: from_region`, where `R` is some region that meets | |
1956 | /// `target_test`. This works by following the constraint graph, | |
1957 | /// creating a constraint path that forces `R` to outlive | |
1958 | /// `from_region`, and then finding the best choices within that | |
1959 | /// path to blame. | |
1960 | crate fn best_blame_constraint( | |
1961 | &self, | |
1962 | body: &Body<'tcx>, | |
1963 | from_region: RegionVid, | |
5869c6ff | 1964 | from_region_origin: NllRegionVariableOrigin, |
dfeec247 | 1965 | target_test: impl Fn(RegionVid) -> bool, |
17df50a5 | 1966 | ) -> BlameConstraint<'tcx> { |
dfeec247 XL |
1967 | debug!( |
1968 | "best_blame_constraint(from_region={:?}, from_region_origin={:?})", | |
1969 | from_region, from_region_origin | |
1970 | ); | |
1971 | ||
1972 | // Find all paths | |
1973 | let (path, target_region) = | |
1974 | self.find_constraint_paths_between_regions(from_region, target_test).unwrap(); | |
1975 | debug!( | |
1976 | "best_blame_constraint: path={:#?}", | |
1977 | path.iter() | |
17df50a5 | 1978 | .map(|c| format!( |
dfeec247 XL |
1979 | "{:?} ({:?}: {:?})", |
1980 | c, | |
1981 | self.constraint_sccs.scc(c.sup), | |
1982 | self.constraint_sccs.scc(c.sub), | |
1983 | )) | |
1984 | .collect::<Vec<_>>() | |
1985 | ); | |
1986 | ||
c295e0f8 XL |
1987 | // We try to avoid reporting a `ConstraintCategory::Predicate` as our best constraint. |
1988 | // Instead, we use it to produce an improved `ObligationCauseCode`. | |
1989 | // FIXME - determine what we should do if we encounter multiple `ConstraintCategory::Predicate` | |
1990 | // constraints. Currently, we just pick the first one. | |
1991 | let cause_code = path | |
1992 | .iter() | |
1993 | .find_map(|constraint| { | |
1994 | if let ConstraintCategory::Predicate(predicate_span) = constraint.category { | |
1995 | // We currentl'y doesn't store the `DefId` in the `ConstraintCategory` | |
1996 | // for perforamnce reasons. The error reporting code used by NLL only | |
1997 | // uses the span, so this doesn't cause any problems at the moment. | |
1998 | Some(ObligationCauseCode::BindingObligation( | |
1999 | CRATE_DEF_ID.to_def_id(), | |
2000 | predicate_span, | |
2001 | )) | |
2002 | } else { | |
2003 | None | |
2004 | } | |
2005 | }) | |
2006 | .unwrap_or_else(|| ObligationCauseCode::MiscObligation); | |
2007 | ||
dfeec247 | 2008 | // Classify each of the constraints along the path. |
17df50a5 | 2009 | let mut categorized_path: Vec<BlameConstraint<'tcx>> = path |
dfeec247 XL |
2010 | .iter() |
2011 | .map(|constraint| { | |
2012 | if constraint.category == ConstraintCategory::ClosureBounds { | |
2013 | self.retrieve_closure_constraint_info(body, &constraint) | |
2014 | } else { | |
17df50a5 XL |
2015 | BlameConstraint { |
2016 | category: constraint.category, | |
2017 | from_closure: false, | |
c295e0f8 XL |
2018 | cause: ObligationCause::new( |
2019 | constraint.locations.span(body), | |
2020 | CRATE_HIR_ID, | |
2021 | cause_code.clone(), | |
2022 | ), | |
2023 | variance_info: constraint.variance_info, | |
17df50a5 | 2024 | } |
dfeec247 XL |
2025 | } |
2026 | }) | |
2027 | .collect(); | |
2028 | debug!("best_blame_constraint: categorized_path={:#?}", categorized_path); | |
2029 | ||
2030 | // To find the best span to cite, we first try to look for the | |
2031 | // final constraint that is interesting and where the `sup` is | |
2032 | // not unified with the ultimate target region. The reason | |
2033 | // for this is that we have a chain of constraints that lead | |
2034 | // from the source to the target region, something like: | |
2035 | // | |
2036 | // '0: '1 ('0 is the source) | |
2037 | // '1: '2 | |
2038 | // '2: '3 | |
2039 | // '3: '4 | |
2040 | // '4: '5 | |
2041 | // '5: '6 ('6 is the target) | |
2042 | // | |
2043 | // Some of those regions are unified with `'6` (in the same | |
2044 | // SCC). We want to screen those out. After that point, the | |
2045 | // "closest" constraint we have to the end is going to be the | |
2046 | // most likely to be the point where the value escapes -- but | |
2047 | // we still want to screen for an "interesting" point to | |
2048 | // highlight (e.g., a call site or something). | |
2049 | let target_scc = self.constraint_sccs.scc(target_region); | |
2050 | let mut range = 0..path.len(); | |
2051 | ||
2052 | // As noted above, when reporting an error, there is typically a chain of constraints | |
2053 | // leading from some "source" region which must outlive some "target" region. | |
2054 | // In most cases, we prefer to "blame" the constraints closer to the target -- | |
2055 | // but there is one exception. When constraints arise from higher-ranked subtyping, | |
2056 | // we generally prefer to blame the source value, | |
2057 | // as the "target" in this case tends to be some type annotation that the user gave. | |
2058 | // Therefore, if we find that the region origin is some instantiation | |
2059 | // of a higher-ranked region, we start our search from the "source" point | |
2060 | // rather than the "target", and we also tweak a few other things. | |
2061 | // | |
2062 | // An example might be this bit of Rust code: | |
2063 | // | |
2064 | // ```rust | |
2065 | // let x: fn(&'static ()) = |_| {}; | |
2066 | // let y: for<'a> fn(&'a ()) = x; | |
2067 | // ``` | |
2068 | // | |
2069 | // In MIR, this will be converted into a combination of assignments and type ascriptions. | |
2070 | // In particular, the 'static is imposed through a type ascription: | |
2071 | // | |
2072 | // ```rust | |
2073 | // x = ...; | |
2074 | // AscribeUserType(x, fn(&'static ()) | |
2075 | // y = x; | |
2076 | // ``` | |
2077 | // | |
2078 | // We wind up ultimately with constraints like | |
2079 | // | |
2080 | // ```rust | |
2081 | // !a: 'temp1 // from the `y = x` statement | |
2082 | // 'temp1: 'temp2 | |
2083 | // 'temp2: 'static // from the AscribeUserType | |
2084 | // ``` | |
2085 | // | |
2086 | // and here we prefer to blame the source (the y = x statement). | |
2087 | let blame_source = match from_region_origin { | |
5869c6ff XL |
2088 | NllRegionVariableOrigin::FreeRegion |
2089 | | NllRegionVariableOrigin::Existential { from_forall: false } => true, | |
2090 | NllRegionVariableOrigin::RootEmptyRegion | |
2091 | | NllRegionVariableOrigin::Placeholder(_) | |
2092 | | NllRegionVariableOrigin::Existential { from_forall: true } => false, | |
dfeec247 XL |
2093 | }; |
2094 | ||
2095 | let find_region = |i: &usize| { | |
17df50a5 | 2096 | let constraint = &path[*i]; |
dfeec247 XL |
2097 | |
2098 | let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup); | |
2099 | ||
2100 | if blame_source { | |
17df50a5 | 2101 | match categorized_path[*i].category { |
dfeec247 XL |
2102 | ConstraintCategory::OpaqueType |
2103 | | ConstraintCategory::Boring | |
2104 | | ConstraintCategory::BoringNoLocation | |
c295e0f8 XL |
2105 | | ConstraintCategory::Internal |
2106 | | ConstraintCategory::Predicate(_) => false, | |
dfeec247 | 2107 | ConstraintCategory::TypeAnnotation |
f035d41b | 2108 | | ConstraintCategory::Return(_) |
dfeec247 XL |
2109 | | ConstraintCategory::Yield => true, |
2110 | _ => constraint_sup_scc != target_scc, | |
2111 | } | |
2112 | } else { | |
3c0e092e XL |
2113 | !matches!( |
2114 | categorized_path[*i].category, | |
dfeec247 | 2115 | ConstraintCategory::OpaqueType |
3c0e092e XL |
2116 | | ConstraintCategory::Boring |
2117 | | ConstraintCategory::BoringNoLocation | |
2118 | | ConstraintCategory::Internal | |
2119 | | ConstraintCategory::Predicate(_) | |
2120 | ) | |
dfeec247 XL |
2121 | } |
2122 | }; | |
2123 | ||
2124 | let best_choice = | |
2125 | if blame_source { range.rev().find(find_region) } else { range.find(find_region) }; | |
2126 | ||
2127 | debug!( | |
2128 | "best_blame_constraint: best_choice={:?} blame_source={}", | |
2129 | best_choice, blame_source | |
2130 | ); | |
2131 | ||
2132 | if let Some(i) = best_choice { | |
2133 | if let Some(next) = categorized_path.get(i + 1) { | |
17df50a5 XL |
2134 | if matches!(categorized_path[i].category, ConstraintCategory::Return(_)) |
2135 | && next.category == ConstraintCategory::OpaqueType | |
dfeec247 XL |
2136 | { |
2137 | // The return expression is being influenced by the return type being | |
2138 | // impl Trait, point at the return type and not the return expr. | |
17df50a5 | 2139 | return next.clone(); |
dfeec247 XL |
2140 | } |
2141 | } | |
f035d41b | 2142 | |
17df50a5 XL |
2143 | if categorized_path[i].category == ConstraintCategory::Return(ReturnConstraint::Normal) |
2144 | { | |
f035d41b | 2145 | let field = categorized_path.iter().find_map(|p| { |
17df50a5 XL |
2146 | if let ConstraintCategory::ClosureUpvar(f) = p.category { |
2147 | Some(f) | |
2148 | } else { | |
2149 | None | |
2150 | } | |
f035d41b XL |
2151 | }); |
2152 | ||
2153 | if let Some(field) = field { | |
17df50a5 | 2154 | categorized_path[i].category = |
f035d41b XL |
2155 | ConstraintCategory::Return(ReturnConstraint::ClosureUpvar(field)); |
2156 | } | |
2157 | } | |
2158 | ||
17df50a5 | 2159 | return categorized_path[i].clone(); |
dfeec247 XL |
2160 | } |
2161 | ||
2162 | // If that search fails, that is.. unusual. Maybe everything | |
2163 | // is in the same SCC or something. In that case, find what | |
2164 | // appears to be the most interesting point to report to the | |
2165 | // user via an even more ad-hoc guess. | |
17df50a5 | 2166 | categorized_path.sort_by(|p0, p1| p0.category.cmp(&p1.category)); |
c295e0f8 | 2167 | debug!("best_blame_constraint: sorted_path={:#?}", categorized_path); |
dfeec247 | 2168 | |
17df50a5 | 2169 | categorized_path.remove(0) |
dfeec247 | 2170 | } |
94222f64 XL |
2171 | |
2172 | crate fn universe_info(&self, universe: ty::UniverseIndex) -> UniverseInfo<'tcx> { | |
c295e0f8 | 2173 | self.universe_causes[&universe].clone() |
94222f64 | 2174 | } |
ff7c6d11 XL |
2175 | } |
2176 | ||
2177 | impl<'tcx> RegionDefinition<'tcx> { | |
8faf50e0 | 2178 | fn new(universe: ty::UniverseIndex, rv_origin: RegionVariableOrigin) -> Self { |
ff7c6d11 | 2179 | // Create a new region definition. Note that, for free |
8faf50e0 | 2180 | // regions, the `external_name` field gets updated later in |
ff7c6d11 | 2181 | // `init_universal_regions`. |
8faf50e0 XL |
2182 | |
2183 | let origin = match rv_origin { | |
5869c6ff XL |
2184 | RegionVariableOrigin::Nll(origin) => origin, |
2185 | _ => NllRegionVariableOrigin::Existential { from_forall: false }, | |
8faf50e0 XL |
2186 | }; |
2187 | ||
dc9dc135 | 2188 | Self { origin, universe, external_name: None } |
ff7c6d11 XL |
2189 | } |
2190 | } | |
2191 | ||
dc9dc135 | 2192 | pub trait ClosureRegionRequirementsExt<'tcx> { |
ff7c6d11 XL |
2193 | fn apply_requirements( |
2194 | &self, | |
dc9dc135 | 2195 | tcx: TyCtxt<'tcx>, |
ff7c6d11 | 2196 | closure_def_id: DefId, |
532ac7d7 | 2197 | closure_substs: SubstsRef<'tcx>, |
dc9dc135 | 2198 | ) -> Vec<QueryOutlivesConstraint<'tcx>>; |
ff7c6d11 XL |
2199 | } |
2200 | ||
dc9dc135 | 2201 | impl<'tcx> ClosureRegionRequirementsExt<'tcx> for ClosureRegionRequirements<'tcx> { |
ff7c6d11 XL |
2202 | /// Given an instance T of the closure type, this method |
2203 | /// instantiates the "extra" requirements that we computed for the | |
2204 | /// closure into the inference context. This has the effect of | |
2205 | /// adding new outlives obligations to existing variables. | |
2206 | /// | |
2207 | /// As described on `ClosureRegionRequirements`, the extra | |
2208 | /// requirements are expressed in terms of regionvids that index | |
2209 | /// into the free regions that appear on the closure type. So, to | |
2210 | /// do this, we first copy those regions out from the type T into | |
2211 | /// a vector. Then we can just index into that vector to extract | |
2212 | /// out the corresponding region from T and apply the | |
2213 | /// requirements. | |
2214 | fn apply_requirements( | |
2215 | &self, | |
dc9dc135 | 2216 | tcx: TyCtxt<'tcx>, |
ff7c6d11 | 2217 | closure_def_id: DefId, |
532ac7d7 | 2218 | closure_substs: SubstsRef<'tcx>, |
dc9dc135 | 2219 | ) -> Vec<QueryOutlivesConstraint<'tcx>> { |
ff7c6d11 | 2220 | debug!( |
9fa01778 XL |
2221 | "apply_requirements(closure_def_id={:?}, closure_substs={:?})", |
2222 | closure_def_id, closure_substs | |
ff7c6d11 XL |
2223 | ); |
2224 | ||
0bf4aa26 | 2225 | // Extract the values of the free regions in `closure_substs` |
ff7c6d11 XL |
2226 | // into a vector. These are the regions that we will be |
2227 | // relating to one another. | |
8faf50e0 | 2228 | let closure_mapping = &UniversalRegions::closure_mapping( |
b7449926 | 2229 | tcx, |
0bf4aa26 | 2230 | closure_substs, |
b7449926 | 2231 | self.num_external_vids, |
3c0e092e | 2232 | tcx.typeck_root_def_id(closure_def_id), |
b7449926 | 2233 | ); |
ff7c6d11 XL |
2234 | debug!("apply_requirements: closure_mapping={:?}", closure_mapping); |
2235 | ||
2236 | // Create the predicates. | |
8faf50e0 XL |
2237 | self.outlives_requirements |
2238 | .iter() | |
2239 | .map(|outlives_requirement| { | |
2240 | let outlived_region = closure_mapping[outlives_requirement.outlived_free_region]; | |
2241 | ||
2242 | match outlives_requirement.subject { | |
2243 | ClosureOutlivesSubject::Region(region) => { | |
2244 | let region = closure_mapping[region]; | |
2245 | debug!( | |
2246 | "apply_requirements: region={:?} \ | |
2247 | outlived_region={:?} \ | |
2248 | outlives_requirement={:?}", | |
2249 | region, outlived_region, outlives_requirement, | |
2250 | ); | |
2251 | ty::Binder::dummy(ty::OutlivesPredicate(region.into(), outlived_region)) | |
2252 | } | |
ff7c6d11 | 2253 | |
8faf50e0 | 2254 | ClosureOutlivesSubject::Ty(ty) => { |
8faf50e0 XL |
2255 | debug!( |
2256 | "apply_requirements: ty={:?} \ | |
2257 | outlived_region={:?} \ | |
2258 | outlives_requirement={:?}", | |
2259 | ty, outlived_region, outlives_requirement, | |
2260 | ); | |
2261 | ty::Binder::dummy(ty::OutlivesPredicate(ty.into(), outlived_region)) | |
2262 | } | |
ff7c6d11 | 2263 | } |
8faf50e0 XL |
2264 | }) |
2265 | .collect() | |
ff7c6d11 | 2266 | } |
ff7c6d11 | 2267 | } |
17df50a5 XL |
2268 | |
2269 | #[derive(Clone, Debug)] | |
2270 | pub struct BlameConstraint<'tcx> { | |
2271 | pub category: ConstraintCategory, | |
2272 | pub from_closure: bool, | |
c295e0f8 | 2273 | pub cause: ObligationCause<'tcx>, |
17df50a5 XL |
2274 | pub variance_info: ty::VarianceDiagInfo<'tcx>, |
2275 | } |