]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | //! See `README.md`. |
abe05a73 | 2 | |
abe05a73 | 3 | use self::CombineMapType::*; |
a1dfa0c6 | 4 | use self::UndoLog::*; |
abe05a73 | 5 | |
abe05a73 | 6 | use super::unify_key; |
0bf4aa26 | 7 | use super::{MiscVariable, RegionVariableOrigin, SubregionOrigin}; |
abe05a73 | 8 | |
dfeec247 XL |
9 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
10 | use rustc_data_structures::sync::Lrc; | |
11 | use rustc_data_structures::unify as ut; | |
12 | use rustc_hir::def_id::DefId; | |
13 | use rustc_index::vec::IndexVec; | |
ba9703b0 XL |
14 | use rustc_middle::ty::ReStatic; |
15 | use rustc_middle::ty::{self, Ty, TyCtxt}; | |
16 | use rustc_middle::ty::{ReLateBound, ReVar}; | |
17 | use rustc_middle::ty::{Region, RegionVid}; | |
dfeec247 | 18 | use rustc_span::Span; |
abe05a73 XL |
19 | |
20 | use std::collections::BTreeMap; | |
532ac7d7 | 21 | use std::ops::Range; |
dfeec247 | 22 | use std::{cmp, fmt, mem}; |
abe05a73 | 23 | |
0731742a | 24 | mod leak_check; |
abe05a73 | 25 | |
ba9703b0 | 26 | pub use rustc_middle::infer::MemberConstraint; |
74b04a01 | 27 | |
a1dfa0c6 | 28 | #[derive(Default)] |
abe05a73 XL |
29 | pub struct RegionConstraintCollector<'tcx> { |
30 | /// For each `RegionVid`, the corresponding `RegionVariableOrigin`. | |
83c7162d | 31 | var_infos: IndexVec<RegionVid, RegionVariableInfo>, |
abe05a73 XL |
32 | |
33 | data: RegionConstraintData<'tcx>, | |
34 | ||
35 | /// For a given pair of regions (R1, R2), maps to a region R3 that | |
36 | /// is designated as their LUB (edges R1 <= R3 and R2 <= R3 | |
37 | /// exist). This prevents us from making many such regions. | |
38 | lubs: CombineMap<'tcx>, | |
39 | ||
40 | /// For a given pair of regions (R1, R2), maps to a region R3 that | |
41 | /// is designated as their GLB (edges R3 <= R1 and R3 <= R2 | |
42 | /// exist). This prevents us from making many such regions. | |
43 | glbs: CombineMap<'tcx>, | |
44 | ||
abe05a73 XL |
45 | /// The undo log records actions that might later be undone. |
46 | /// | |
a1dfa0c6 | 47 | /// Note: `num_open_snapshots` is used to track if we are actively |
abe05a73 | 48 | /// snapshotting. When the `start_snapshot()` method is called, we |
a1dfa0c6 XL |
49 | /// increment `num_open_snapshots` to indicate that we are now actively |
50 | /// snapshotting. The reason for this is that otherwise we end up adding | |
51 | /// entries for things like the lower bound on a variable and so forth, | |
52 | /// which can never be rolled back. | |
53 | undo_log: Vec<UndoLog<'tcx>>, | |
54 | ||
0731742a | 55 | /// The number of open snapshots, i.e., those that haven't been committed or |
a1dfa0c6 XL |
56 | /// rolled back. |
57 | num_open_snapshots: usize, | |
abe05a73 XL |
58 | |
59 | /// When we add a R1 == R2 constriant, we currently add (a) edges | |
60 | /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this | |
61 | /// table. You can then call `opportunistic_resolve_var` early | |
62 | /// which will map R1 and R2 to some common region (i.e., either | |
63 | /// R1 or R2). This is important when dropck and other such code | |
64 | /// is iterating to a fixed point, because otherwise we sometimes | |
65 | /// would wind up with a fresh stream of region variables that | |
66 | /// have been equated but appear distinct. | |
0531ce1d | 67 | unification_table: ut::UnificationTable<ut::InPlace<ty::RegionVid>>, |
94b46f34 XL |
68 | |
69 | /// a flag set to true when we perform any unifications; this is used | |
70 | /// to micro-optimize `take_and_reset_data` | |
71 | any_unifications: bool, | |
abe05a73 XL |
72 | } |
73 | ||
83c7162d | 74 | pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>; |
abe05a73 XL |
75 | |
76 | /// The full set of region constraints gathered up by the collector. | |
77 | /// Describes constraints between the region variables and other | |
78 | /// regions, as well as other conditions that must be verified, or | |
79 | /// assumptions that can be made. | |
0531ce1d | 80 | #[derive(Debug, Default, Clone)] |
abe05a73 XL |
81 | pub struct RegionConstraintData<'tcx> { |
82 | /// Constraints of the form `A <= B`, where either `A` or `B` can | |
83 | /// be a region variable (or neither, as it happens). | |
84 | pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>, | |
85 | ||
dc9dc135 XL |
86 | /// Constraints of the form `R0 member of [R1, ..., Rn]`, meaning that |
87 | /// `R0` must be equal to one of the regions `R1..Rn`. These occur | |
88 | /// with `impl Trait` quite frequently. | |
89 | pub member_constraints: Vec<MemberConstraint<'tcx>>, | |
90 | ||
abe05a73 XL |
91 | /// A "verify" is something that we need to verify after inference |
92 | /// is done, but which does not directly affect inference in any | |
93 | /// way. | |
94 | /// | |
95 | /// An example is a `A <= B` where neither `A` nor `B` are | |
96 | /// inference variables. | |
97 | pub verifys: Vec<Verify<'tcx>>, | |
98 | ||
99 | /// A "given" is a relationship that is known to hold. In | |
100 | /// particular, we often know from closure fn signatures that a | |
101 | /// particular free region must be a subregion of a region | |
102 | /// variable: | |
103 | /// | |
104 | /// foo.iter().filter(<'a> |x: &'a &'b T| ...) | |
105 | /// | |
106 | /// In situations like this, `'b` is in fact a region variable | |
107 | /// introduced by the call to `iter()`, and `'a` is a bound region | |
108 | /// on the closure (as indicated by the `<'a>` prefix). If we are | |
109 | /// naive, we wind up inferring that `'b` must be `'static`, | |
110 | /// because we require that it be greater than `'a` and we do not | |
111 | /// know what `'a` is precisely. | |
112 | /// | |
113 | /// This hashmap is used to avoid that naive scenario. Basically | |
114 | /// we record the fact that `'a <= 'b` is implied by the fn | |
115 | /// signature, and then ignore the constraint when solving | |
116 | /// equations. This is a bit of a hack but seems to work. | |
117 | pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>, | |
118 | } | |
119 | ||
9fa01778 | 120 | /// Represents a constraint that influences the inference process. |
e74abb32 | 121 | #[derive(Clone, Copy, PartialEq, Eq, Debug, PartialOrd, Ord)] |
abe05a73 | 122 | pub enum Constraint<'tcx> { |
9fa01778 | 123 | /// A region variable is a subregion of another. |
abe05a73 XL |
124 | VarSubVar(RegionVid, RegionVid), |
125 | ||
9fa01778 | 126 | /// A concrete region is a subregion of region variable. |
abe05a73 XL |
127 | RegSubVar(Region<'tcx>, RegionVid), |
128 | ||
9fa01778 | 129 | /// A region variable is a subregion of a concrete region. This does not |
abe05a73 XL |
130 | /// directly affect inference, but instead is checked after |
131 | /// inference is complete. | |
132 | VarSubReg(RegionVid, Region<'tcx>), | |
133 | ||
134 | /// A constraint where neither side is a variable. This does not | |
135 | /// directly affect inference, but instead is checked after | |
136 | /// inference is complete. | |
137 | RegSubReg(Region<'tcx>, Region<'tcx>), | |
138 | } | |
139 | ||
0731742a XL |
140 | impl Constraint<'_> { |
141 | pub fn involves_placeholders(&self) -> bool { | |
142 | match self { | |
143 | Constraint::VarSubVar(_, _) => false, | |
144 | Constraint::VarSubReg(_, r) | Constraint::RegSubVar(r, _) => r.is_placeholder(), | |
145 | Constraint::RegSubReg(r, s) => r.is_placeholder() || s.is_placeholder(), | |
146 | } | |
147 | } | |
148 | } | |
149 | ||
9fa01778 | 150 | /// `VerifyGenericBound(T, _, R, RS)`: the parameter type `T` (or |
abe05a73 | 151 | /// associated type) must outlive the region `R`. `T` is known to |
9fa01778 | 152 | /// outlive `RS`. Therefore, verify that `R <= RS[i]` for some |
abe05a73 XL |
153 | /// `i`. Inference variables may be involved (but this verification |
154 | /// step doesn't influence inference). | |
0531ce1d | 155 | #[derive(Debug, Clone)] |
abe05a73 XL |
156 | pub struct Verify<'tcx> { |
157 | pub kind: GenericKind<'tcx>, | |
158 | pub origin: SubregionOrigin<'tcx>, | |
159 | pub region: Region<'tcx>, | |
160 | pub bound: VerifyBound<'tcx>, | |
161 | } | |
162 | ||
60c5eb7d | 163 | #[derive(Copy, Clone, PartialEq, Eq, Hash, TypeFoldable)] |
abe05a73 XL |
164 | pub enum GenericKind<'tcx> { |
165 | Param(ty::ParamTy), | |
166 | Projection(ty::ProjectionTy<'tcx>), | |
167 | } | |
168 | ||
9fa01778 | 169 | /// Describes the things that some `GenericKind` value `G` is known to |
0bf4aa26 XL |
170 | /// outlive. Each variant of `VerifyBound` can be thought of as a |
171 | /// function: | |
172 | /// | |
173 | /// fn(min: Region) -> bool { .. } | |
174 | /// | |
175 | /// where `true` means that the region `min` meets that `G: min`. | |
176 | /// (False means nothing.) | |
177 | /// | |
178 | /// So, for example, if we have the type `T` and we have in scope that | |
179 | /// `T: 'a` and `T: 'b`, then the verify bound might be: | |
180 | /// | |
181 | /// fn(min: Region) -> bool { | |
182 | /// ('a: min) || ('b: min) | |
183 | /// } | |
184 | /// | |
185 | /// This is described with a `AnyRegion('a, 'b)` node. | |
0531ce1d | 186 | #[derive(Debug, Clone)] |
abe05a73 | 187 | pub enum VerifyBound<'tcx> { |
0bf4aa26 XL |
188 | /// Given a kind K and a bound B, expands to a function like the |
189 | /// following, where `G` is the generic for which this verify | |
190 | /// bound was created: | |
191 | /// | |
9fa01778 XL |
192 | /// ```rust |
193 | /// fn(min) -> bool { | |
194 | /// if G == K { | |
0bf4aa26 | 195 | /// B(min) |
9fa01778 | 196 | /// } else { |
0bf4aa26 | 197 | /// false |
0bf4aa26 | 198 | /// } |
9fa01778 XL |
199 | /// } |
200 | /// ``` | |
0bf4aa26 XL |
201 | /// |
202 | /// In other words, if the generic `G` that we are checking is | |
203 | /// equal to `K`, then check the associated verify bound | |
204 | /// (otherwise, false). | |
205 | /// | |
206 | /// This is used when we have something in the environment that | |
207 | /// may or may not be relevant, depending on the region inference | |
208 | /// results. For example, we may have `where <T as | |
9fa01778 | 209 | /// Trait<'a>>::Item: 'b` in our where-clauses. If we are |
0bf4aa26 XL |
210 | /// generating the verify-bound for `<T as Trait<'0>>::Item`, then |
211 | /// this where-clause is only relevant if `'0` winds up inferred | |
212 | /// to `'a`. | |
213 | /// | |
214 | /// So we would compile to a verify-bound like | |
215 | /// | |
9fa01778 XL |
216 | /// ``` |
217 | /// IfEq(<T as Trait<'a>>::Item, AnyRegion('a)) | |
218 | /// ``` | |
abe05a73 | 219 | /// |
0bf4aa26 XL |
220 | /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item` |
221 | /// (after inference), and `'a: min`, then `G: min`. | |
222 | IfEq(Ty<'tcx>, Box<VerifyBound<'tcx>>), | |
abe05a73 | 223 | |
0bf4aa26 | 224 | /// Given a region `R`, expands to the function: |
abe05a73 | 225 | /// |
9fa01778 XL |
226 | /// ``` |
227 | /// fn(min) -> bool { | |
228 | /// R: min | |
229 | /// } | |
230 | /// ``` | |
0bf4aa26 XL |
231 | /// |
232 | /// This is used when we can establish that `G: R` -- therefore, | |
233 | /// if `R: min`, then by transitivity `G: min`. | |
234 | OutlivedBy(Region<'tcx>), | |
abe05a73 | 235 | |
74b04a01 XL |
236 | /// Given a region `R`, true if it is `'empty`. |
237 | IsEmpty, | |
238 | ||
0bf4aa26 XL |
239 | /// Given a set of bounds `B`, expands to the function: |
240 | /// | |
9fa01778 XL |
241 | /// ```rust |
242 | /// fn(min) -> bool { | |
243 | /// exists (b in B) { b(min) } | |
244 | /// } | |
245 | /// ``` | |
0bf4aa26 XL |
246 | /// |
247 | /// In other words, if we meet some bound in `B`, that suffices. | |
9fa01778 | 248 | /// This is used when all the bounds in `B` are known to apply to `G`. |
abe05a73 XL |
249 | AnyBound(Vec<VerifyBound<'tcx>>), |
250 | ||
0bf4aa26 XL |
251 | /// Given a set of bounds `B`, expands to the function: |
252 | /// | |
9fa01778 XL |
253 | /// ```rust |
254 | /// fn(min) -> bool { | |
255 | /// forall (b in B) { b(min) } | |
256 | /// } | |
257 | /// ``` | |
0bf4aa26 XL |
258 | /// |
259 | /// In other words, if we meet *all* bounds in `B`, that suffices. | |
260 | /// This is used when *some* bound in `B` is known to suffice, but | |
261 | /// we don't know which. | |
abe05a73 XL |
262 | AllBounds(Vec<VerifyBound<'tcx>>), |
263 | } | |
264 | ||
265 | #[derive(Copy, Clone, PartialEq, Eq, Hash)] | |
266 | struct TwoRegions<'tcx> { | |
267 | a: Region<'tcx>, | |
268 | b: Region<'tcx>, | |
269 | } | |
270 | ||
271 | #[derive(Copy, Clone, PartialEq)] | |
a1dfa0c6 | 272 | enum UndoLog<'tcx> { |
9fa01778 | 273 | /// We added `RegionVid`. |
abe05a73 XL |
274 | AddVar(RegionVid), |
275 | ||
9fa01778 | 276 | /// We added the given `constraint`. |
abe05a73 XL |
277 | AddConstraint(Constraint<'tcx>), |
278 | ||
9fa01778 | 279 | /// We added the given `verify`. |
abe05a73 XL |
280 | AddVerify(usize), |
281 | ||
9fa01778 | 282 | /// We added the given `given`. |
abe05a73 XL |
283 | AddGiven(Region<'tcx>, ty::RegionVid), |
284 | ||
9fa01778 | 285 | /// We added a GLB/LUB "combination variable". |
abe05a73 XL |
286 | AddCombination(CombineMapType, TwoRegions<'tcx>), |
287 | ||
288 | /// During skolemization, we sometimes purge entries from the undo | |
289 | /// log in a kind of minisnapshot (unlike other snapshots, this | |
290 | /// purging actually takes place *on success*). In that case, we | |
291 | /// replace the corresponding entry with `Noop` so as to avoid the | |
292 | /// need to do a bunch of swapping. (We can't use `swap_remove` as | |
293 | /// the order of the vector is important.) | |
294 | Purged, | |
295 | } | |
296 | ||
297 | #[derive(Copy, Clone, PartialEq)] | |
298 | enum CombineMapType { | |
299 | Lub, | |
300 | Glb, | |
301 | } | |
302 | ||
303 | type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>; | |
304 | ||
83c7162d XL |
305 | #[derive(Debug, Clone, Copy)] |
306 | pub struct RegionVariableInfo { | |
307 | pub origin: RegionVariableOrigin, | |
308 | pub universe: ty::UniverseIndex, | |
309 | } | |
310 | ||
abe05a73 XL |
311 | pub struct RegionSnapshot { |
312 | length: usize, | |
0531ce1d | 313 | region_snapshot: ut::Snapshot<ut::InPlace<ty::RegionVid>>, |
94b46f34 | 314 | any_unifications: bool, |
abe05a73 XL |
315 | } |
316 | ||
0bf4aa26 XL |
317 | /// When working with placeholder regions, we often wish to find all of |
318 | /// the regions that are either reachable from a placeholder region, or | |
319 | /// which can reach a placeholder region, or both. We call such regions | |
9fa01778 | 320 | /// *tainted* regions. This struct allows you to decide what set of |
abe05a73 XL |
321 | /// tainted regions you want. |
322 | #[derive(Debug)] | |
323 | pub struct TaintDirections { | |
324 | incoming: bool, | |
325 | outgoing: bool, | |
326 | } | |
327 | ||
328 | impl TaintDirections { | |
329 | pub fn incoming() -> Self { | |
dfeec247 | 330 | TaintDirections { incoming: true, outgoing: false } |
abe05a73 XL |
331 | } |
332 | ||
333 | pub fn outgoing() -> Self { | |
dfeec247 | 334 | TaintDirections { incoming: false, outgoing: true } |
abe05a73 XL |
335 | } |
336 | ||
337 | pub fn both() -> Self { | |
dfeec247 | 338 | TaintDirections { incoming: true, outgoing: true } |
abe05a73 XL |
339 | } |
340 | } | |
341 | ||
342 | impl<'tcx> RegionConstraintCollector<'tcx> { | |
a1dfa0c6 XL |
343 | pub fn new() -> Self { |
344 | Self::default() | |
abe05a73 XL |
345 | } |
346 | ||
83c7162d XL |
347 | pub fn num_region_vars(&self) -> usize { |
348 | self.var_infos.len() | |
abe05a73 XL |
349 | } |
350 | ||
0531ce1d XL |
351 | pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> { |
352 | &self.data | |
353 | } | |
354 | ||
abe05a73 XL |
355 | /// Once all the constraints have been gathered, extract out the final data. |
356 | /// | |
357 | /// Not legal during a snapshot. | |
83c7162d | 358 | pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) { |
abe05a73 | 359 | assert!(!self.in_snapshot()); |
83c7162d | 360 | (self.var_infos, self.data) |
abe05a73 XL |
361 | } |
362 | ||
363 | /// Takes (and clears) the current set of constraints. Note that | |
364 | /// the set of variables remains intact, but all relationships | |
9fa01778 | 365 | /// between them are reset. This is used during NLL checking to |
abe05a73 XL |
366 | /// grab the set of constraints that arose from a particular |
367 | /// operation. | |
368 | /// | |
369 | /// We don't want to leak relationships between variables between | |
370 | /// points because just because (say) `r1 == r2` was true at some | |
371 | /// point P in the graph doesn't imply that it will be true at | |
372 | /// some other point Q, in NLL. | |
373 | /// | |
374 | /// Not legal during a snapshot. | |
375 | pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> { | |
376 | assert!(!self.in_snapshot()); | |
377 | ||
378 | // If you add a new field to `RegionConstraintCollector`, you | |
379 | // should think carefully about whether it needs to be cleared | |
380 | // or updated in some way. | |
381 | let RegionConstraintCollector { | |
94b46f34 | 382 | var_infos: _, |
abe05a73 XL |
383 | data, |
384 | lubs, | |
385 | glbs, | |
abe05a73 | 386 | undo_log: _, |
a1dfa0c6 | 387 | num_open_snapshots: _, |
abe05a73 | 388 | unification_table, |
94b46f34 | 389 | any_unifications, |
abe05a73 XL |
390 | } = self; |
391 | ||
abe05a73 XL |
392 | // Clear the tables of (lubs, glbs), so that we will create |
393 | // fresh regions if we do a LUB operation. As it happens, | |
394 | // LUB/GLB are not performed by the MIR type-checker, which is | |
395 | // the one that uses this method, but it's good to be correct. | |
396 | lubs.clear(); | |
397 | glbs.clear(); | |
398 | ||
399 | // Clear all unifications and recreate the variables a "now | |
400 | // un-unified" state. Note that when we unify `a` and `b`, we | |
401 | // also insert `a <= b` and a `b <= a` edges, so the | |
402 | // `RegionConstraintData` contains the relationship here. | |
94b46f34 XL |
403 | if *any_unifications { |
404 | unification_table.reset_unifications(|vid| unify_key::RegionVidKey { min_vid: vid }); | |
405 | *any_unifications = false; | |
abe05a73 XL |
406 | } |
407 | ||
416331ca | 408 | mem::take(data) |
abe05a73 XL |
409 | } |
410 | ||
0531ce1d XL |
411 | pub fn data(&self) -> &RegionConstraintData<'tcx> { |
412 | &self.data | |
413 | } | |
414 | ||
abe05a73 | 415 | fn in_snapshot(&self) -> bool { |
a1dfa0c6 | 416 | self.num_open_snapshots > 0 |
abe05a73 XL |
417 | } |
418 | ||
419 | pub fn start_snapshot(&mut self) -> RegionSnapshot { | |
420 | let length = self.undo_log.len(); | |
421 | debug!("RegionConstraintCollector: start_snapshot({})", length); | |
a1dfa0c6 | 422 | self.num_open_snapshots += 1; |
abe05a73 XL |
423 | RegionSnapshot { |
424 | length, | |
425 | region_snapshot: self.unification_table.snapshot(), | |
94b46f34 | 426 | any_unifications: self.any_unifications, |
abe05a73 XL |
427 | } |
428 | } | |
429 | ||
a1dfa0c6 XL |
430 | fn assert_open_snapshot(&self, snapshot: &RegionSnapshot) { |
431 | assert!(self.undo_log.len() >= snapshot.length); | |
432 | assert!(self.num_open_snapshots > 0); | |
433 | } | |
434 | ||
abe05a73 XL |
435 | pub fn commit(&mut self, snapshot: RegionSnapshot) { |
436 | debug!("RegionConstraintCollector: commit({})", snapshot.length); | |
a1dfa0c6 | 437 | self.assert_open_snapshot(&snapshot); |
abe05a73 | 438 | |
a1dfa0c6 XL |
439 | if self.num_open_snapshots == 1 { |
440 | // The root snapshot. It's safe to clear the undo log because | |
441 | // there's no snapshot further out that we might need to roll back | |
442 | // to. | |
443 | assert!(snapshot.length == 0); | |
0bf4aa26 | 444 | self.undo_log.clear(); |
abe05a73 | 445 | } |
a1dfa0c6 XL |
446 | |
447 | self.num_open_snapshots -= 1; | |
448 | ||
abe05a73 XL |
449 | self.unification_table.commit(snapshot.region_snapshot); |
450 | } | |
451 | ||
452 | pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { | |
453 | debug!("RegionConstraintCollector: rollback_to({:?})", snapshot); | |
a1dfa0c6 XL |
454 | self.assert_open_snapshot(&snapshot); |
455 | ||
456 | while self.undo_log.len() > snapshot.length { | |
abe05a73 XL |
457 | let undo_entry = self.undo_log.pop().unwrap(); |
458 | self.rollback_undo_entry(undo_entry); | |
459 | } | |
a1dfa0c6 XL |
460 | |
461 | self.num_open_snapshots -= 1; | |
462 | ||
abe05a73 | 463 | self.unification_table.rollback_to(snapshot.region_snapshot); |
94b46f34 | 464 | self.any_unifications = snapshot.any_unifications; |
abe05a73 XL |
465 | } |
466 | ||
a1dfa0c6 | 467 | fn rollback_undo_entry(&mut self, undo_entry: UndoLog<'tcx>) { |
abe05a73 | 468 | match undo_entry { |
a1dfa0c6 | 469 | Purged => { |
abe05a73 XL |
470 | // nothing to do here |
471 | } | |
472 | AddVar(vid) => { | |
83c7162d XL |
473 | self.var_infos.pop().unwrap(); |
474 | assert_eq!(self.var_infos.len(), vid.index() as usize); | |
abe05a73 XL |
475 | } |
476 | AddConstraint(ref constraint) => { | |
477 | self.data.constraints.remove(constraint); | |
478 | } | |
479 | AddVerify(index) => { | |
480 | self.data.verifys.pop(); | |
481 | assert_eq!(self.data.verifys.len(), index); | |
482 | } | |
483 | AddGiven(sub, sup) => { | |
484 | self.data.givens.remove(&(sub, sup)); | |
485 | } | |
486 | AddCombination(Glb, ref regions) => { | |
487 | self.glbs.remove(regions); | |
488 | } | |
489 | AddCombination(Lub, ref regions) => { | |
490 | self.lubs.remove(regions); | |
491 | } | |
492 | } | |
493 | } | |
494 | ||
0bf4aa26 XL |
495 | pub fn new_region_var( |
496 | &mut self, | |
497 | universe: ty::UniverseIndex, | |
498 | origin: RegionVariableOrigin, | |
499 | ) -> RegionVid { | |
500 | let vid = self.var_infos.push(RegionVariableInfo { origin, universe }); | |
abe05a73 | 501 | |
dfeec247 | 502 | let u_vid = self.unification_table.new_key(unify_key::RegionVidKey { min_vid: vid }); |
abe05a73 XL |
503 | assert_eq!(vid, u_vid); |
504 | if self.in_snapshot() { | |
505 | self.undo_log.push(AddVar(vid)); | |
506 | } | |
dfeec247 | 507 | debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin); |
ba9703b0 | 508 | vid |
abe05a73 XL |
509 | } |
510 | ||
83c7162d XL |
511 | /// Returns the universe for the given variable. |
512 | pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex { | |
513 | self.var_infos[vid].universe | |
abe05a73 XL |
514 | } |
515 | ||
83c7162d XL |
516 | /// Returns the origin for the given variable. |
517 | pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin { | |
518 | self.var_infos[vid].origin | |
abe05a73 XL |
519 | } |
520 | ||
0bf4aa26 | 521 | /// Removes all the edges to/from the placeholder regions that are |
abe05a73 | 522 | /// in `skols`. This is used after a higher-ranked operation |
0bf4aa26 | 523 | /// completes to remove all trace of the placeholder regions |
abe05a73 | 524 | /// created in that time. |
a1dfa0c6 | 525 | pub fn pop_placeholders(&mut self, placeholders: &FxHashSet<ty::Region<'tcx>>) { |
0bf4aa26 | 526 | debug!("pop_placeholders(placeholders={:?})", placeholders); |
abe05a73 XL |
527 | |
528 | assert!(self.in_snapshot()); | |
abe05a73 | 529 | |
0731742a XL |
530 | let constraints_to_kill: Vec<usize> = self |
531 | .undo_log | |
abe05a73 XL |
532 | .iter() |
533 | .enumerate() | |
534 | .rev() | |
0bf4aa26 | 535 | .filter(|&(_, undo_entry)| kill_constraint(placeholders, undo_entry)) |
abe05a73 XL |
536 | .map(|(index, _)| index) |
537 | .collect(); | |
538 | ||
539 | for index in constraints_to_kill { | |
540 | let undo_entry = mem::replace(&mut self.undo_log[index], Purged); | |
541 | self.rollback_undo_entry(undo_entry); | |
542 | } | |
543 | ||
abe05a73 XL |
544 | return; |
545 | ||
546 | fn kill_constraint<'tcx>( | |
0bf4aa26 | 547 | placeholders: &FxHashSet<ty::Region<'tcx>>, |
a1dfa0c6 | 548 | undo_entry: &UndoLog<'tcx>, |
abe05a73 XL |
549 | ) -> bool { |
550 | match undo_entry { | |
551 | &AddConstraint(Constraint::VarSubVar(..)) => false, | |
0bf4aa26 XL |
552 | &AddConstraint(Constraint::RegSubVar(a, _)) => placeholders.contains(&a), |
553 | &AddConstraint(Constraint::VarSubReg(_, b)) => placeholders.contains(&b), | |
abe05a73 | 554 | &AddConstraint(Constraint::RegSubReg(a, b)) => { |
0bf4aa26 | 555 | placeholders.contains(&a) || placeholders.contains(&b) |
abe05a73 XL |
556 | } |
557 | &AddGiven(..) => false, | |
558 | &AddVerify(_) => false, | |
559 | &AddCombination(_, ref two_regions) => { | |
0bf4aa26 | 560 | placeholders.contains(&two_regions.a) || placeholders.contains(&two_regions.b) |
abe05a73 | 561 | } |
a1dfa0c6 | 562 | &AddVar(..) | &Purged => false, |
abe05a73 XL |
563 | } |
564 | } | |
565 | } | |
566 | ||
abe05a73 XL |
567 | fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { |
568 | // cannot add constraints once regions are resolved | |
dfeec247 | 569 | debug!("RegionConstraintCollector: add_constraint({:?})", constraint); |
abe05a73 XL |
570 | |
571 | // never overwrite an existing (constraint, origin) - only insert one if it isn't | |
572 | // present in the map yet. This prevents origins from outside the snapshot being | |
0731742a | 573 | // replaced with "less informative" origins e.g., during calls to `can_eq` |
abe05a73 XL |
574 | let in_snapshot = self.in_snapshot(); |
575 | let undo_log = &mut self.undo_log; | |
576 | self.data.constraints.entry(constraint).or_insert_with(|| { | |
577 | if in_snapshot { | |
578 | undo_log.push(AddConstraint(constraint)); | |
579 | } | |
580 | origin | |
581 | }); | |
582 | } | |
583 | ||
584 | fn add_verify(&mut self, verify: Verify<'tcx>) { | |
585 | // cannot add verifys once regions are resolved | |
586 | debug!("RegionConstraintCollector: add_verify({:?})", verify); | |
587 | ||
588 | // skip no-op cases known to be satisfied | |
0bf4aa26 | 589 | if let VerifyBound::AllBounds(ref bs) = verify.bound { |
74b04a01 | 590 | if bs.is_empty() { |
abe05a73 XL |
591 | return; |
592 | } | |
abe05a73 XL |
593 | } |
594 | ||
595 | let index = self.data.verifys.len(); | |
596 | self.data.verifys.push(verify); | |
597 | if self.in_snapshot() { | |
598 | self.undo_log.push(AddVerify(index)); | |
599 | } | |
600 | } | |
601 | ||
602 | pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { | |
603 | // cannot add givens once regions are resolved | |
604 | if self.data.givens.insert((sub, sup)) { | |
605 | debug!("add_given({:?} <= {:?})", sub, sup); | |
606 | ||
607 | if self.in_snapshot() { | |
608 | self.undo_log.push(AddGiven(sub, sup)); | |
609 | } | |
610 | } | |
611 | } | |
612 | ||
613 | pub fn make_eqregion( | |
614 | &mut self, | |
615 | origin: SubregionOrigin<'tcx>, | |
616 | sub: Region<'tcx>, | |
617 | sup: Region<'tcx>, | |
618 | ) { | |
619 | if sub != sup { | |
620 | // Eventually, it would be nice to add direct support for | |
621 | // equating regions. | |
622 | self.make_subregion(origin.clone(), sub, sup); | |
623 | self.make_subregion(origin, sup, sub); | |
624 | ||
625 | if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) { | |
9fa01778 | 626 | debug!("make_eqregion: uniying {:?} with {:?}", sub, sup); |
abe05a73 | 627 | self.unification_table.union(sub, sup); |
94b46f34 | 628 | self.any_unifications = true; |
abe05a73 XL |
629 | } |
630 | } | |
631 | } | |
632 | ||
dc9dc135 XL |
633 | pub fn member_constraint( |
634 | &mut self, | |
635 | opaque_type_def_id: DefId, | |
636 | definition_span: Span, | |
637 | hidden_ty: Ty<'tcx>, | |
638 | member_region: ty::Region<'tcx>, | |
639 | choice_regions: &Lrc<Vec<ty::Region<'tcx>>>, | |
640 | ) { | |
641 | debug!("member_constraint({:?} in {:#?})", member_region, choice_regions); | |
642 | ||
643 | if choice_regions.iter().any(|&r| r == member_region) { | |
644 | return; | |
645 | } | |
646 | ||
647 | self.data.member_constraints.push(MemberConstraint { | |
648 | opaque_type_def_id, | |
649 | definition_span, | |
650 | hidden_ty, | |
651 | member_region, | |
dfeec247 | 652 | choice_regions: choice_regions.clone(), |
dc9dc135 | 653 | }); |
dc9dc135 XL |
654 | } |
655 | ||
abe05a73 XL |
656 | pub fn make_subregion( |
657 | &mut self, | |
658 | origin: SubregionOrigin<'tcx>, | |
659 | sub: Region<'tcx>, | |
660 | sup: Region<'tcx>, | |
661 | ) { | |
662 | // cannot add constraints once regions are resolved | |
663 | debug!( | |
664 | "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}", | |
0bf4aa26 | 665 | sub, sup, origin |
abe05a73 XL |
666 | ); |
667 | ||
668 | match (sub, sup) { | |
669 | (&ReLateBound(..), _) | (_, &ReLateBound(..)) => { | |
dfeec247 | 670 | span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup); |
abe05a73 XL |
671 | } |
672 | (_, &ReStatic) => { | |
673 | // all regions are subregions of static, so we can ignore this | |
674 | } | |
675 | (&ReVar(sub_id), &ReVar(sup_id)) => { | |
676 | self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin); | |
677 | } | |
678 | (_, &ReVar(sup_id)) => { | |
679 | self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin); | |
680 | } | |
681 | (&ReVar(sub_id), _) => { | |
682 | self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin); | |
683 | } | |
684 | _ => { | |
685 | self.add_constraint(Constraint::RegSubReg(sub, sup), origin); | |
686 | } | |
687 | } | |
688 | } | |
689 | ||
9fa01778 | 690 | /// See [`Verify::VerifyGenericBound`]. |
abe05a73 XL |
691 | pub fn verify_generic_bound( |
692 | &mut self, | |
693 | origin: SubregionOrigin<'tcx>, | |
694 | kind: GenericKind<'tcx>, | |
695 | sub: Region<'tcx>, | |
696 | bound: VerifyBound<'tcx>, | |
697 | ) { | |
dfeec247 | 698 | self.add_verify(Verify { kind, origin, region: sub, bound }); |
abe05a73 XL |
699 | } |
700 | ||
701 | pub fn lub_regions( | |
702 | &mut self, | |
dc9dc135 | 703 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
704 | origin: SubregionOrigin<'tcx>, |
705 | a: Region<'tcx>, | |
706 | b: Region<'tcx>, | |
707 | ) -> Region<'tcx> { | |
708 | // cannot add constraints once regions are resolved | |
709 | debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b); | |
710 | match (a, b) { | |
711 | (r @ &ReStatic, _) | (_, r @ &ReStatic) => { | |
712 | r // nothing lives longer than static | |
713 | } | |
714 | ||
715 | _ if a == b => { | |
716 | a // LUB(a,a) = a | |
717 | } | |
718 | ||
0bf4aa26 | 719 | _ => self.combine_vars(tcx, Lub, a, b, origin), |
abe05a73 XL |
720 | } |
721 | } | |
722 | ||
723 | pub fn glb_regions( | |
724 | &mut self, | |
dc9dc135 | 725 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
726 | origin: SubregionOrigin<'tcx>, |
727 | a: Region<'tcx>, | |
728 | b: Region<'tcx>, | |
729 | ) -> Region<'tcx> { | |
730 | // cannot add constraints once regions are resolved | |
731 | debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b); | |
732 | match (a, b) { | |
733 | (&ReStatic, r) | (r, &ReStatic) => { | |
734 | r // static lives longer than everything else | |
735 | } | |
736 | ||
737 | _ if a == b => { | |
738 | a // GLB(a,a) = a | |
739 | } | |
740 | ||
0bf4aa26 | 741 | _ => self.combine_vars(tcx, Glb, a, b, origin), |
abe05a73 XL |
742 | } |
743 | } | |
744 | ||
745 | pub fn opportunistic_resolve_var( | |
746 | &mut self, | |
dc9dc135 | 747 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
748 | rid: RegionVid, |
749 | ) -> ty::Region<'tcx> { | |
0531ce1d | 750 | let vid = self.unification_table.probe_value(rid).min_vid; |
abe05a73 XL |
751 | tcx.mk_region(ty::ReVar(vid)) |
752 | } | |
753 | ||
754 | fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { | |
755 | match t { | |
756 | Glb => &mut self.glbs, | |
757 | Lub => &mut self.lubs, | |
758 | } | |
759 | } | |
760 | ||
761 | fn combine_vars( | |
762 | &mut self, | |
dc9dc135 | 763 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
764 | t: CombineMapType, |
765 | a: Region<'tcx>, | |
766 | b: Region<'tcx>, | |
767 | origin: SubregionOrigin<'tcx>, | |
768 | ) -> Region<'tcx> { | |
74b04a01 | 769 | let vars = TwoRegions { a, b }; |
abe05a73 XL |
770 | if let Some(&c) = self.combine_map(t).get(&vars) { |
771 | return tcx.mk_region(ReVar(c)); | |
772 | } | |
83c7162d XL |
773 | let a_universe = self.universe(a); |
774 | let b_universe = self.universe(b); | |
775 | let c_universe = cmp::max(a_universe, b_universe); | |
776 | let c = self.new_region_var(c_universe, MiscVariable(origin.span())); | |
abe05a73 XL |
777 | self.combine_map(t).insert(vars, c); |
778 | if self.in_snapshot() { | |
779 | self.undo_log.push(AddCombination(t, vars)); | |
780 | } | |
781 | let new_r = tcx.mk_region(ReVar(c)); | |
782 | for &old_r in &[a, b] { | |
783 | match t { | |
784 | Glb => self.make_subregion(origin.clone(), new_r, old_r), | |
785 | Lub => self.make_subregion(origin.clone(), old_r, new_r), | |
786 | } | |
787 | } | |
788 | debug!("combine_vars() c={:?}", c); | |
789 | new_r | |
790 | } | |
791 | ||
0731742a | 792 | pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex { |
83c7162d | 793 | match *region { |
0bf4aa26 XL |
794 | ty::ReScope(..) |
795 | | ty::ReStatic | |
0bf4aa26 XL |
796 | | ty::ReErased |
797 | | ty::ReFree(..) | |
798 | | ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT, | |
74b04a01 | 799 | ty::ReEmpty(ui) => ui, |
0bf4aa26 | 800 | ty::RePlaceholder(placeholder) => placeholder.universe, |
ba9703b0 | 801 | ty::ReVar(vid) => self.var_universe(vid), |
0bf4aa26 | 802 | ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region), |
83c7162d XL |
803 | } |
804 | } | |
805 | ||
532ac7d7 XL |
806 | pub fn vars_since_snapshot( |
807 | &self, | |
808 | mark: &RegionSnapshot, | |
809 | ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) { | |
810 | let range = self.unification_table.vars_since_snapshot(&mark.region_snapshot); | |
dfeec247 XL |
811 | ( |
812 | range.clone(), | |
813 | (range.start.index()..range.end.index()) | |
814 | .map(|index| self.var_infos[ty::RegionVid::from(index)].origin) | |
815 | .collect(), | |
816 | ) | |
0731742a | 817 | } |
abe05a73 | 818 | |
9fa01778 | 819 | /// See [`RegionInference::region_constraints_added_in_snapshot`]. |
0731742a XL |
820 | pub fn region_constraints_added_in_snapshot(&self, mark: &RegionSnapshot) -> Option<bool> { |
821 | self.undo_log[mark.length..] | |
822 | .iter() | |
823 | .map(|&elt| match elt { | |
824 | AddConstraint(constraint) => Some(constraint.involves_placeholders()), | |
825 | _ => None, | |
dfeec247 XL |
826 | }) |
827 | .max() | |
0731742a | 828 | .unwrap_or(None) |
abe05a73 XL |
829 | } |
830 | } | |
831 | ||
832 | impl fmt::Debug for RegionSnapshot { | |
0bf4aa26 | 833 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
83c7162d | 834 | write!(f, "RegionSnapshot(length={})", self.length) |
abe05a73 XL |
835 | } |
836 | } | |
837 | ||
838 | impl<'tcx> fmt::Debug for GenericKind<'tcx> { | |
0bf4aa26 | 839 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
840 | match *self { |
841 | GenericKind::Param(ref p) => write!(f, "{:?}", p), | |
842 | GenericKind::Projection(ref p) => write!(f, "{:?}", p), | |
843 | } | |
844 | } | |
845 | } | |
846 | ||
847 | impl<'tcx> fmt::Display for GenericKind<'tcx> { | |
0bf4aa26 | 848 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
849 | match *self { |
850 | GenericKind::Param(ref p) => write!(f, "{}", p), | |
851 | GenericKind::Projection(ref p) => write!(f, "{}", p), | |
852 | } | |
853 | } | |
854 | } | |
855 | ||
dc9dc135 XL |
856 | impl<'tcx> GenericKind<'tcx> { |
857 | pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { | |
abe05a73 XL |
858 | match *self { |
859 | GenericKind::Param(ref p) => p.to_ty(tcx), | |
860 | GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs), | |
861 | } | |
862 | } | |
863 | } | |
864 | ||
dc9dc135 | 865 | impl<'tcx> VerifyBound<'tcx> { |
abe05a73 XL |
866 | pub fn must_hold(&self) -> bool { |
867 | match self { | |
0bf4aa26 XL |
868 | VerifyBound::IfEq(..) => false, |
869 | VerifyBound::OutlivedBy(ty::ReStatic) => true, | |
870 | VerifyBound::OutlivedBy(_) => false, | |
74b04a01 | 871 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
872 | VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()), |
873 | VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()), | |
abe05a73 XL |
874 | } |
875 | } | |
876 | ||
877 | pub fn cannot_hold(&self) -> bool { | |
878 | match self { | |
0bf4aa26 | 879 | VerifyBound::IfEq(_, b) => b.cannot_hold(), |
74b04a01 | 880 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
881 | VerifyBound::OutlivedBy(_) => false, |
882 | VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()), | |
883 | VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()), | |
abe05a73 XL |
884 | } |
885 | } | |
886 | ||
887 | pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
888 | if self.must_hold() || vb.cannot_hold() { | |
889 | self | |
890 | } else if self.cannot_hold() || vb.must_hold() { | |
891 | vb | |
892 | } else { | |
893 | VerifyBound::AnyBound(vec![self, vb]) | |
894 | } | |
895 | } | |
896 | ||
897 | pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
898 | if self.must_hold() && vb.must_hold() { | |
899 | self | |
900 | } else if self.cannot_hold() && vb.cannot_hold() { | |
901 | self | |
902 | } else { | |
903 | VerifyBound::AllBounds(vec![self, vb]) | |
904 | } | |
905 | } | |
906 | } | |
907 | ||
908 | impl<'tcx> RegionConstraintData<'tcx> { | |
9fa01778 XL |
909 | /// Returns `true` if this region constraint data contains no constraints, and `false` |
910 | /// otherwise. | |
abe05a73 | 911 | pub fn is_empty(&self) -> bool { |
dfeec247 XL |
912 | let RegionConstraintData { constraints, member_constraints, verifys, givens } = self; |
913 | constraints.is_empty() | |
914 | && member_constraints.is_empty() | |
915 | && verifys.is_empty() | |
916 | && givens.is_empty() | |
abe05a73 XL |
917 | } |
918 | } |