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