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