]>
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 | |
dfeec247 XL |
10 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
11 | use rustc_data_structures::sync::Lrc; | |
f9f354fc | 12 | use rustc_data_structures::undo_log::UndoLogs; |
dfeec247 XL |
13 | use rustc_data_structures::unify as ut; |
14 | use rustc_hir::def_id::DefId; | |
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 | |
a1dfa0c6 | 31 | #[derive(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 | ||
abe05a73 XL |
48 | /// When we add a R1 == R2 constriant, we currently add (a) edges |
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 | ||
68 | impl std::ops::Deref for RegionConstraintCollector<'_, 'tcx> { | |
69 | type Target = RegionConstraintStorage<'tcx>; | |
70 | #[inline] | |
71 | fn deref(&self) -> &RegionConstraintStorage<'tcx> { | |
72 | self.storage | |
73 | } | |
74 | } | |
75 | ||
76 | impl std::ops::DerefMut for RegionConstraintCollector<'_, 'tcx> { | |
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. | |
126 | pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>, | |
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 | ||
60c5eb7d | 167 | #[derive(Copy, Clone, PartialEq, Eq, Hash, TypeFoldable)] |
abe05a73 XL |
168 | pub enum GenericKind<'tcx> { |
169 | Param(ty::ParamTy), | |
170 | Projection(ty::ProjectionTy<'tcx>), | |
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: | |
176 | /// | |
177 | /// fn(min: Region) -> bool { .. } | |
178 | /// | |
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: | |
184 | /// | |
185 | /// fn(min: Region) -> bool { | |
186 | /// ('a: min) || ('b: min) | |
187 | /// } | |
188 | /// | |
189 | /// This is described with a `AnyRegion('a, 'b)` node. | |
0531ce1d | 190 | #[derive(Debug, Clone)] |
abe05a73 | 191 | pub enum VerifyBound<'tcx> { |
0bf4aa26 XL |
192 | /// Given a kind K and a bound B, expands to a function like the |
193 | /// following, where `G` is the generic for which this verify | |
194 | /// bound was created: | |
195 | /// | |
9fa01778 XL |
196 | /// ```rust |
197 | /// fn(min) -> bool { | |
198 | /// if G == K { | |
0bf4aa26 | 199 | /// B(min) |
9fa01778 | 200 | /// } else { |
0bf4aa26 | 201 | /// false |
0bf4aa26 | 202 | /// } |
9fa01778 XL |
203 | /// } |
204 | /// ``` | |
0bf4aa26 XL |
205 | /// |
206 | /// In other words, if the generic `G` that we are checking is | |
207 | /// equal to `K`, then check the associated verify bound | |
208 | /// (otherwise, false). | |
209 | /// | |
210 | /// This is used when we have something in the environment that | |
211 | /// may or may not be relevant, depending on the region inference | |
212 | /// results. For example, we may have `where <T as | |
9fa01778 | 213 | /// Trait<'a>>::Item: 'b` in our where-clauses. If we are |
0bf4aa26 XL |
214 | /// generating the verify-bound for `<T as Trait<'0>>::Item`, then |
215 | /// this where-clause is only relevant if `'0` winds up inferred | |
216 | /// to `'a`. | |
217 | /// | |
218 | /// So we would compile to a verify-bound like | |
219 | /// | |
9fa01778 XL |
220 | /// ``` |
221 | /// IfEq(<T as Trait<'a>>::Item, AnyRegion('a)) | |
222 | /// ``` | |
abe05a73 | 223 | /// |
0bf4aa26 XL |
224 | /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item` |
225 | /// (after inference), and `'a: min`, then `G: min`. | |
226 | IfEq(Ty<'tcx>, Box<VerifyBound<'tcx>>), | |
abe05a73 | 227 | |
0bf4aa26 | 228 | /// Given a region `R`, expands to the function: |
abe05a73 | 229 | /// |
9fa01778 XL |
230 | /// ``` |
231 | /// fn(min) -> bool { | |
232 | /// R: min | |
233 | /// } | |
234 | /// ``` | |
0bf4aa26 XL |
235 | /// |
236 | /// This is used when we can establish that `G: R` -- therefore, | |
237 | /// if `R: min`, then by transitivity `G: min`. | |
238 | OutlivedBy(Region<'tcx>), | |
abe05a73 | 239 | |
74b04a01 XL |
240 | /// Given a region `R`, true if it is `'empty`. |
241 | IsEmpty, | |
242 | ||
0bf4aa26 XL |
243 | /// Given a set of bounds `B`, expands to the function: |
244 | /// | |
9fa01778 XL |
245 | /// ```rust |
246 | /// fn(min) -> bool { | |
247 | /// exists (b in B) { b(min) } | |
248 | /// } | |
249 | /// ``` | |
0bf4aa26 XL |
250 | /// |
251 | /// In other words, if we meet some bound in `B`, that suffices. | |
9fa01778 | 252 | /// This is used when all the bounds in `B` are known to apply to `G`. |
abe05a73 XL |
253 | AnyBound(Vec<VerifyBound<'tcx>>), |
254 | ||
0bf4aa26 XL |
255 | /// Given a set of bounds `B`, expands to the function: |
256 | /// | |
9fa01778 XL |
257 | /// ```rust |
258 | /// fn(min) -> bool { | |
259 | /// forall (b in B) { b(min) } | |
260 | /// } | |
261 | /// ``` | |
0bf4aa26 XL |
262 | /// |
263 | /// In other words, if we meet *all* bounds in `B`, that suffices. | |
264 | /// This is used when *some* bound in `B` is known to suffice, but | |
265 | /// we don't know which. | |
abe05a73 XL |
266 | AllBounds(Vec<VerifyBound<'tcx>>), |
267 | } | |
268 | ||
269 | #[derive(Copy, Clone, PartialEq, Eq, Hash)] | |
f9f354fc | 270 | pub(crate) struct TwoRegions<'tcx> { |
abe05a73 XL |
271 | a: Region<'tcx>, |
272 | b: Region<'tcx>, | |
273 | } | |
274 | ||
275 | #[derive(Copy, Clone, PartialEq)] | |
f9f354fc | 276 | pub(crate) enum UndoLog<'tcx> { |
9fa01778 | 277 | /// We added `RegionVid`. |
abe05a73 XL |
278 | AddVar(RegionVid), |
279 | ||
9fa01778 | 280 | /// We added the given `constraint`. |
abe05a73 XL |
281 | AddConstraint(Constraint<'tcx>), |
282 | ||
9fa01778 | 283 | /// We added the given `verify`. |
abe05a73 XL |
284 | AddVerify(usize), |
285 | ||
9fa01778 | 286 | /// We added the given `given`. |
abe05a73 XL |
287 | AddGiven(Region<'tcx>, ty::RegionVid), |
288 | ||
9fa01778 | 289 | /// We added a GLB/LUB "combination variable". |
abe05a73 | 290 | AddCombination(CombineMapType, TwoRegions<'tcx>), |
abe05a73 XL |
291 | } |
292 | ||
293 | #[derive(Copy, Clone, PartialEq)] | |
f9f354fc | 294 | pub(crate) enum CombineMapType { |
abe05a73 XL |
295 | Lub, |
296 | Glb, | |
297 | } | |
298 | ||
299 | type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>; | |
300 | ||
83c7162d XL |
301 | #[derive(Debug, Clone, Copy)] |
302 | pub struct RegionVariableInfo { | |
303 | pub origin: RegionVariableOrigin, | |
304 | pub universe: ty::UniverseIndex, | |
305 | } | |
306 | ||
abe05a73 | 307 | pub struct RegionSnapshot { |
94b46f34 | 308 | any_unifications: bool, |
abe05a73 XL |
309 | } |
310 | ||
f9f354fc | 311 | impl<'tcx> RegionConstraintStorage<'tcx> { |
a1dfa0c6 XL |
312 | pub fn new() -> Self { |
313 | Self::default() | |
abe05a73 XL |
314 | } |
315 | ||
f9f354fc XL |
316 | #[inline] |
317 | pub(crate) fn with_log<'a>( | |
318 | &'a mut self, | |
319 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
320 | ) -> RegionConstraintCollector<'a, 'tcx> { | |
321 | RegionConstraintCollector { storage: self, undo_log } | |
322 | } | |
323 | ||
324 | fn rollback_undo_entry(&mut self, undo_entry: UndoLog<'tcx>) { | |
325 | match undo_entry { | |
f9f354fc XL |
326 | AddVar(vid) => { |
327 | self.var_infos.pop().unwrap(); | |
328 | assert_eq!(self.var_infos.len(), vid.index() as usize); | |
329 | } | |
330 | AddConstraint(ref constraint) => { | |
331 | self.data.constraints.remove(constraint); | |
332 | } | |
333 | AddVerify(index) => { | |
334 | self.data.verifys.pop(); | |
335 | assert_eq!(self.data.verifys.len(), index); | |
336 | } | |
337 | AddGiven(sub, sup) => { | |
338 | self.data.givens.remove(&(sub, sup)); | |
339 | } | |
340 | AddCombination(Glb, ref regions) => { | |
341 | self.glbs.remove(regions); | |
342 | } | |
343 | AddCombination(Lub, ref regions) => { | |
344 | self.lubs.remove(regions); | |
345 | } | |
346 | } | |
347 | } | |
348 | } | |
349 | ||
350 | impl<'tcx> RegionConstraintCollector<'_, 'tcx> { | |
83c7162d XL |
351 | pub fn num_region_vars(&self) -> usize { |
352 | self.var_infos.len() | |
abe05a73 XL |
353 | } |
354 | ||
0531ce1d XL |
355 | pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> { |
356 | &self.data | |
357 | } | |
358 | ||
abe05a73 XL |
359 | /// Once all the constraints have been gathered, extract out the final data. |
360 | /// | |
361 | /// Not legal during a snapshot. | |
83c7162d | 362 | pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) { |
f9f354fc XL |
363 | assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log)); |
364 | (mem::take(&mut self.storage.var_infos), mem::take(&mut self.storage.data)) | |
abe05a73 XL |
365 | } |
366 | ||
367 | /// Takes (and clears) the current set of constraints. Note that | |
368 | /// the set of variables remains intact, but all relationships | |
9fa01778 | 369 | /// between them are reset. This is used during NLL checking to |
abe05a73 XL |
370 | /// grab the set of constraints that arose from a particular |
371 | /// operation. | |
372 | /// | |
373 | /// We don't want to leak relationships between variables between | |
374 | /// points because just because (say) `r1 == r2` was true at some | |
375 | /// point P in the graph doesn't imply that it will be true at | |
376 | /// some other point Q, in NLL. | |
377 | /// | |
378 | /// Not legal during a snapshot. | |
379 | pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> { | |
f9f354fc | 380 | assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log)); |
abe05a73 XL |
381 | |
382 | // If you add a new field to `RegionConstraintCollector`, you | |
383 | // should think carefully about whether it needs to be cleared | |
384 | // or updated in some way. | |
f9f354fc | 385 | let RegionConstraintStorage { |
94b46f34 | 386 | var_infos: _, |
abe05a73 XL |
387 | data, |
388 | lubs, | |
389 | glbs, | |
f9f354fc | 390 | unification_table: _, |
94b46f34 | 391 | any_unifications, |
f9f354fc | 392 | } = self.storage; |
abe05a73 | 393 | |
abe05a73 XL |
394 | // Clear the tables of (lubs, glbs), so that we will create |
395 | // fresh regions if we do a LUB operation. As it happens, | |
396 | // LUB/GLB are not performed by the MIR type-checker, which is | |
397 | // the one that uses this method, but it's good to be correct. | |
398 | lubs.clear(); | |
399 | glbs.clear(); | |
400 | ||
f9f354fc XL |
401 | let data = mem::take(data); |
402 | ||
abe05a73 XL |
403 | // Clear all unifications and recreate the variables a "now |
404 | // un-unified" state. Note that when we unify `a` and `b`, we | |
405 | // also insert `a <= b` and a `b <= a` edges, so the | |
406 | // `RegionConstraintData` contains the relationship here. | |
94b46f34 | 407 | if *any_unifications { |
94b46f34 | 408 | *any_unifications = false; |
17df50a5 | 409 | self.unification_table().reset_unifications(|_| UnifiedRegion(None)); |
abe05a73 XL |
410 | } |
411 | ||
f9f354fc | 412 | data |
abe05a73 XL |
413 | } |
414 | ||
0531ce1d XL |
415 | pub fn data(&self) -> &RegionConstraintData<'tcx> { |
416 | &self.data | |
417 | } | |
418 | ||
abe05a73 | 419 | pub fn start_snapshot(&mut self) -> RegionSnapshot { |
f9f354fc XL |
420 | debug!("RegionConstraintCollector: start_snapshot"); |
421 | RegionSnapshot { any_unifications: self.any_unifications } | |
abe05a73 XL |
422 | } |
423 | ||
424 | pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { | |
425 | debug!("RegionConstraintCollector: rollback_to({:?})", snapshot); | |
94b46f34 | 426 | self.any_unifications = snapshot.any_unifications; |
abe05a73 XL |
427 | } |
428 | ||
0bf4aa26 XL |
429 | pub fn new_region_var( |
430 | &mut self, | |
431 | universe: ty::UniverseIndex, | |
432 | origin: RegionVariableOrigin, | |
433 | ) -> RegionVid { | |
434 | let vid = self.var_infos.push(RegionVariableInfo { origin, universe }); | |
abe05a73 | 435 | |
17df50a5 XL |
436 | let u_vid = self.unification_table().new_key(UnifiedRegion(None)); |
437 | assert_eq!(vid, u_vid.vid); | |
f9f354fc | 438 | self.undo_log.push(AddVar(vid)); |
dfeec247 | 439 | debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin); |
ba9703b0 | 440 | vid |
abe05a73 XL |
441 | } |
442 | ||
83c7162d XL |
443 | /// Returns the universe for the given variable. |
444 | pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex { | |
445 | self.var_infos[vid].universe | |
abe05a73 XL |
446 | } |
447 | ||
abe05a73 XL |
448 | fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { |
449 | // cannot add constraints once regions are resolved | |
dfeec247 | 450 | debug!("RegionConstraintCollector: add_constraint({:?})", constraint); |
abe05a73 XL |
451 | |
452 | // never overwrite an existing (constraint, origin) - only insert one if it isn't | |
453 | // present in the map yet. This prevents origins from outside the snapshot being | |
0731742a | 454 | // replaced with "less informative" origins e.g., during calls to `can_eq` |
abe05a73 | 455 | let undo_log = &mut self.undo_log; |
f9f354fc XL |
456 | self.storage.data.constraints.entry(constraint).or_insert_with(|| { |
457 | undo_log.push(AddConstraint(constraint)); | |
abe05a73 XL |
458 | origin |
459 | }); | |
460 | } | |
461 | ||
462 | fn add_verify(&mut self, verify: Verify<'tcx>) { | |
463 | // cannot add verifys once regions are resolved | |
464 | debug!("RegionConstraintCollector: add_verify({:?})", verify); | |
465 | ||
466 | // skip no-op cases known to be satisfied | |
0bf4aa26 | 467 | if let VerifyBound::AllBounds(ref bs) = verify.bound { |
74b04a01 | 468 | if bs.is_empty() { |
abe05a73 XL |
469 | return; |
470 | } | |
abe05a73 XL |
471 | } |
472 | ||
473 | let index = self.data.verifys.len(); | |
474 | self.data.verifys.push(verify); | |
f9f354fc | 475 | self.undo_log.push(AddVerify(index)); |
abe05a73 XL |
476 | } |
477 | ||
478 | pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { | |
479 | // cannot add givens once regions are resolved | |
480 | if self.data.givens.insert((sub, sup)) { | |
481 | debug!("add_given({:?} <= {:?})", sub, sup); | |
482 | ||
f9f354fc | 483 | self.undo_log.push(AddGiven(sub, sup)); |
abe05a73 XL |
484 | } |
485 | } | |
486 | ||
487 | pub fn make_eqregion( | |
488 | &mut self, | |
489 | origin: SubregionOrigin<'tcx>, | |
490 | sub: Region<'tcx>, | |
491 | sup: Region<'tcx>, | |
492 | ) { | |
493 | if sub != sup { | |
494 | // Eventually, it would be nice to add direct support for | |
495 | // equating regions. | |
496 | self.make_subregion(origin.clone(), sub, sup); | |
497 | self.make_subregion(origin, sup, sub); | |
498 | ||
17df50a5 XL |
499 | match (sub, sup) { |
500 | (&ty::ReVar(sub), &ty::ReVar(sup)) => { | |
501 | debug!("make_eqregion: unifying {:?} with {:?}", sub, sup); | |
502 | self.unification_table().union(sub, sup); | |
503 | self.any_unifications = true; | |
504 | } | |
505 | (&ty::ReVar(vid), value) | (value, &ty::ReVar(vid)) => { | |
506 | debug!("make_eqregion: unifying {:?} with {:?}", vid, value); | |
507 | self.unification_table().union_value(vid, UnifiedRegion(Some(value))); | |
508 | self.any_unifications = true; | |
509 | } | |
510 | (_, _) => {} | |
abe05a73 XL |
511 | } |
512 | } | |
513 | } | |
514 | ||
dc9dc135 XL |
515 | pub fn member_constraint( |
516 | &mut self, | |
517 | opaque_type_def_id: DefId, | |
518 | definition_span: Span, | |
519 | hidden_ty: Ty<'tcx>, | |
520 | member_region: ty::Region<'tcx>, | |
521 | choice_regions: &Lrc<Vec<ty::Region<'tcx>>>, | |
522 | ) { | |
523 | debug!("member_constraint({:?} in {:#?})", member_region, choice_regions); | |
524 | ||
525 | if choice_regions.iter().any(|&r| r == member_region) { | |
526 | return; | |
527 | } | |
528 | ||
529 | self.data.member_constraints.push(MemberConstraint { | |
530 | opaque_type_def_id, | |
531 | definition_span, | |
532 | hidden_ty, | |
533 | member_region, | |
dfeec247 | 534 | choice_regions: choice_regions.clone(), |
dc9dc135 | 535 | }); |
dc9dc135 XL |
536 | } |
537 | ||
abe05a73 XL |
538 | pub fn make_subregion( |
539 | &mut self, | |
540 | origin: SubregionOrigin<'tcx>, | |
541 | sub: Region<'tcx>, | |
542 | sup: Region<'tcx>, | |
543 | ) { | |
544 | // cannot add constraints once regions are resolved | |
545 | debug!( | |
546 | "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}", | |
0bf4aa26 | 547 | sub, sup, origin |
abe05a73 XL |
548 | ); |
549 | ||
550 | match (sub, sup) { | |
551 | (&ReLateBound(..), _) | (_, &ReLateBound(..)) => { | |
dfeec247 | 552 | span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup); |
abe05a73 XL |
553 | } |
554 | (_, &ReStatic) => { | |
555 | // all regions are subregions of static, so we can ignore this | |
556 | } | |
557 | (&ReVar(sub_id), &ReVar(sup_id)) => { | |
558 | self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin); | |
559 | } | |
560 | (_, &ReVar(sup_id)) => { | |
561 | self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin); | |
562 | } | |
563 | (&ReVar(sub_id), _) => { | |
564 | self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin); | |
565 | } | |
566 | _ => { | |
567 | self.add_constraint(Constraint::RegSubReg(sub, sup), origin); | |
568 | } | |
569 | } | |
570 | } | |
571 | ||
abe05a73 XL |
572 | pub fn verify_generic_bound( |
573 | &mut self, | |
574 | origin: SubregionOrigin<'tcx>, | |
575 | kind: GenericKind<'tcx>, | |
576 | sub: Region<'tcx>, | |
577 | bound: VerifyBound<'tcx>, | |
578 | ) { | |
dfeec247 | 579 | self.add_verify(Verify { kind, origin, region: sub, bound }); |
abe05a73 XL |
580 | } |
581 | ||
582 | pub fn lub_regions( | |
583 | &mut self, | |
dc9dc135 | 584 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
585 | origin: SubregionOrigin<'tcx>, |
586 | a: Region<'tcx>, | |
587 | b: Region<'tcx>, | |
588 | ) -> Region<'tcx> { | |
589 | // cannot add constraints once regions are resolved | |
590 | debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b); | |
591 | match (a, b) { | |
592 | (r @ &ReStatic, _) | (_, r @ &ReStatic) => { | |
593 | r // nothing lives longer than static | |
594 | } | |
595 | ||
596 | _ if a == b => { | |
597 | a // LUB(a,a) = a | |
598 | } | |
599 | ||
0bf4aa26 | 600 | _ => self.combine_vars(tcx, Lub, a, b, origin), |
abe05a73 XL |
601 | } |
602 | } | |
603 | ||
604 | pub fn glb_regions( | |
605 | &mut self, | |
dc9dc135 | 606 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
607 | origin: SubregionOrigin<'tcx>, |
608 | a: Region<'tcx>, | |
609 | b: Region<'tcx>, | |
610 | ) -> Region<'tcx> { | |
611 | // cannot add constraints once regions are resolved | |
612 | debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b); | |
613 | match (a, b) { | |
614 | (&ReStatic, r) | (r, &ReStatic) => { | |
615 | r // static lives longer than everything else | |
616 | } | |
617 | ||
618 | _ if a == b => { | |
619 | a // GLB(a,a) = a | |
620 | } | |
621 | ||
0bf4aa26 | 622 | _ => self.combine_vars(tcx, Glb, a, b, origin), |
abe05a73 XL |
623 | } |
624 | } | |
625 | ||
17df50a5 XL |
626 | /// Resolves the passed RegionVid to the root RegionVid in the unification table |
627 | pub fn opportunistic_resolve_var(&mut self, rid: ty::RegionVid) -> ty::RegionVid { | |
628 | self.unification_table().find(rid).vid | |
629 | } | |
630 | ||
631 | /// If the Region is a `ReVar`, then resolves it either to the root value in | |
632 | /// the unification table, if it exists, or to the root `ReVar` in the table. | |
633 | /// If the Region is not a `ReVar`, just returns the Region itself. | |
634 | pub fn opportunistic_resolve_region( | |
635 | &mut self, | |
636 | tcx: TyCtxt<'tcx>, | |
637 | region: ty::Region<'tcx>, | |
638 | ) -> ty::Region<'tcx> { | |
639 | match region { | |
640 | ty::ReVar(rid) => { | |
641 | let unified_region = self.unification_table().probe_value(*rid); | |
642 | unified_region.0.unwrap_or_else(|| { | |
643 | let root = self.unification_table().find(*rid).vid; | |
644 | tcx.reuse_or_mk_region(region, ty::ReVar(root)) | |
645 | }) | |
646 | } | |
647 | _ => region, | |
648 | } | |
abe05a73 XL |
649 | } |
650 | ||
651 | fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { | |
652 | match t { | |
653 | Glb => &mut self.glbs, | |
654 | Lub => &mut self.lubs, | |
655 | } | |
656 | } | |
657 | ||
658 | fn combine_vars( | |
659 | &mut self, | |
dc9dc135 | 660 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
661 | t: CombineMapType, |
662 | a: Region<'tcx>, | |
663 | b: Region<'tcx>, | |
664 | origin: SubregionOrigin<'tcx>, | |
665 | ) -> Region<'tcx> { | |
74b04a01 | 666 | let vars = TwoRegions { a, b }; |
abe05a73 XL |
667 | if let Some(&c) = self.combine_map(t).get(&vars) { |
668 | return tcx.mk_region(ReVar(c)); | |
669 | } | |
83c7162d XL |
670 | let a_universe = self.universe(a); |
671 | let b_universe = self.universe(b); | |
672 | let c_universe = cmp::max(a_universe, b_universe); | |
673 | let c = self.new_region_var(c_universe, MiscVariable(origin.span())); | |
abe05a73 | 674 | self.combine_map(t).insert(vars, c); |
f9f354fc | 675 | self.undo_log.push(AddCombination(t, vars)); |
abe05a73 XL |
676 | let new_r = tcx.mk_region(ReVar(c)); |
677 | for &old_r in &[a, b] { | |
678 | match t { | |
679 | Glb => self.make_subregion(origin.clone(), new_r, old_r), | |
680 | Lub => self.make_subregion(origin.clone(), old_r, new_r), | |
681 | } | |
682 | } | |
683 | debug!("combine_vars() c={:?}", c); | |
684 | new_r | |
685 | } | |
686 | ||
0731742a | 687 | pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex { |
83c7162d | 688 | match *region { |
f9f354fc XL |
689 | ty::ReStatic | ty::ReErased | ty::ReFree(..) | ty::ReEarlyBound(..) => { |
690 | ty::UniverseIndex::ROOT | |
691 | } | |
74b04a01 | 692 | ty::ReEmpty(ui) => ui, |
0bf4aa26 | 693 | ty::RePlaceholder(placeholder) => placeholder.universe, |
ba9703b0 | 694 | ty::ReVar(vid) => self.var_universe(vid), |
0bf4aa26 | 695 | ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region), |
83c7162d XL |
696 | } |
697 | } | |
698 | ||
532ac7d7 XL |
699 | pub fn vars_since_snapshot( |
700 | &self, | |
f9f354fc | 701 | value_count: usize, |
532ac7d7 | 702 | ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) { |
17df50a5 | 703 | let range = RegionVid::from(value_count)..RegionVid::from(self.unification_table.len()); |
dfeec247 XL |
704 | ( |
705 | range.clone(), | |
706 | (range.start.index()..range.end.index()) | |
707 | .map(|index| self.var_infos[ty::RegionVid::from(index)].origin) | |
708 | .collect(), | |
709 | ) | |
0731742a | 710 | } |
abe05a73 | 711 | |
f9f354fc XL |
712 | /// See `InferCtxt::region_constraints_added_in_snapshot`. |
713 | pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option<bool> { | |
714 | self.undo_log | |
715 | .region_constraints_in_snapshot(mark) | |
0731742a XL |
716 | .map(|&elt| match elt { |
717 | AddConstraint(constraint) => Some(constraint.involves_placeholders()), | |
718 | _ => None, | |
dfeec247 XL |
719 | }) |
720 | .max() | |
0731742a | 721 | .unwrap_or(None) |
abe05a73 | 722 | } |
f9f354fc XL |
723 | |
724 | #[inline] | |
17df50a5 | 725 | fn unification_table(&mut self) -> super::UnificationTable<'_, 'tcx, RegionVidKey<'tcx>> { |
f9f354fc XL |
726 | ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log) |
727 | } | |
abe05a73 XL |
728 | } |
729 | ||
730 | impl fmt::Debug for RegionSnapshot { | |
0bf4aa26 | 731 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
f9f354fc | 732 | write!(f, "RegionSnapshot") |
abe05a73 XL |
733 | } |
734 | } | |
735 | ||
736 | impl<'tcx> fmt::Debug for GenericKind<'tcx> { | |
0bf4aa26 | 737 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
738 | match *self { |
739 | GenericKind::Param(ref p) => write!(f, "{:?}", p), | |
740 | GenericKind::Projection(ref p) => write!(f, "{:?}", p), | |
741 | } | |
742 | } | |
743 | } | |
744 | ||
745 | impl<'tcx> fmt::Display 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), | |
749 | GenericKind::Projection(ref p) => write!(f, "{}", p), | |
750 | } | |
751 | } | |
752 | } | |
753 | ||
dc9dc135 XL |
754 | impl<'tcx> GenericKind<'tcx> { |
755 | pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { | |
abe05a73 XL |
756 | match *self { |
757 | GenericKind::Param(ref p) => p.to_ty(tcx), | |
758 | GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs), | |
759 | } | |
760 | } | |
761 | } | |
762 | ||
dc9dc135 | 763 | impl<'tcx> VerifyBound<'tcx> { |
abe05a73 XL |
764 | pub fn must_hold(&self) -> bool { |
765 | match self { | |
0bf4aa26 XL |
766 | VerifyBound::IfEq(..) => false, |
767 | VerifyBound::OutlivedBy(ty::ReStatic) => true, | |
768 | VerifyBound::OutlivedBy(_) => false, | |
74b04a01 | 769 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
770 | VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()), |
771 | VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()), | |
abe05a73 XL |
772 | } |
773 | } | |
774 | ||
775 | pub fn cannot_hold(&self) -> bool { | |
776 | match self { | |
0bf4aa26 | 777 | VerifyBound::IfEq(_, b) => b.cannot_hold(), |
74b04a01 | 778 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
779 | VerifyBound::OutlivedBy(_) => false, |
780 | VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()), | |
781 | VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()), | |
abe05a73 XL |
782 | } |
783 | } | |
784 | ||
785 | pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
786 | if self.must_hold() || vb.cannot_hold() { | |
787 | self | |
788 | } else if self.cannot_hold() || vb.must_hold() { | |
789 | vb | |
790 | } else { | |
791 | VerifyBound::AnyBound(vec![self, vb]) | |
792 | } | |
793 | } | |
abe05a73 XL |
794 | } |
795 | ||
796 | impl<'tcx> RegionConstraintData<'tcx> { | |
9fa01778 XL |
797 | /// Returns `true` if this region constraint data contains no constraints, and `false` |
798 | /// otherwise. | |
abe05a73 | 799 | pub fn is_empty(&self) -> bool { |
dfeec247 XL |
800 | let RegionConstraintData { constraints, member_constraints, verifys, givens } = self; |
801 | constraints.is_empty() | |
802 | && member_constraints.is_empty() | |
803 | && verifys.is_empty() | |
804 | && givens.is_empty() | |
abe05a73 XL |
805 | } |
806 | } | |
f9f354fc XL |
807 | |
808 | impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> { | |
809 | fn reverse(&mut self, undo: UndoLog<'tcx>) { | |
810 | self.rollback_undo_entry(undo) | |
811 | } | |
812 | } |