]>
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 | 10 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
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 XL |
14 | use rustc_data_structures::unify as ut; |
15 | use rustc_hir::def_id::DefId; | |
16 | use rustc_index::vec::IndexVec; | |
17df50a5 | 17 | use rustc_middle::infer::unify_key::{RegionVidKey, UnifiedRegion}; |
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 | |
5099ac24 | 32 | #[derive(Clone, 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. | |
17df50a5 | 57 | pub(super) unification_table: ut::UnificationTableStorage<RegionVidKey<'tcx>>, |
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 | ||
a2a8927a | 69 | impl<'tcx> std::ops::Deref for RegionConstraintCollector<'_, 'tcx> { |
f9f354fc XL |
70 | type Target = RegionConstraintStorage<'tcx>; |
71 | #[inline] | |
72 | fn deref(&self) -> &RegionConstraintStorage<'tcx> { | |
73 | self.storage | |
74 | } | |
75 | } | |
76 | ||
a2a8927a | 77 | impl<'tcx> std::ops::DerefMut for RegionConstraintCollector<'_, 'tcx> { |
f9f354fc XL |
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 | /// | |
94222f64 | 190 | /// This is described with an `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; |
17df50a5 | 410 | self.unification_table().reset_unifications(|_| UnifiedRegion(None)); |
abe05a73 XL |
411 | } |
412 | ||
f9f354fc | 413 | data |
abe05a73 XL |
414 | } |
415 | ||
0531ce1d XL |
416 | pub fn data(&self) -> &RegionConstraintData<'tcx> { |
417 | &self.data | |
418 | } | |
419 | ||
abe05a73 | 420 | pub fn start_snapshot(&mut self) -> RegionSnapshot { |
f9f354fc XL |
421 | debug!("RegionConstraintCollector: start_snapshot"); |
422 | RegionSnapshot { any_unifications: self.any_unifications } | |
abe05a73 XL |
423 | } |
424 | ||
425 | pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { | |
426 | debug!("RegionConstraintCollector: rollback_to({:?})", snapshot); | |
94b46f34 | 427 | self.any_unifications = snapshot.any_unifications; |
abe05a73 XL |
428 | } |
429 | ||
0bf4aa26 XL |
430 | pub fn new_region_var( |
431 | &mut self, | |
432 | universe: ty::UniverseIndex, | |
433 | origin: RegionVariableOrigin, | |
434 | ) -> RegionVid { | |
435 | let vid = self.var_infos.push(RegionVariableInfo { origin, universe }); | |
abe05a73 | 436 | |
17df50a5 XL |
437 | let u_vid = self.unification_table().new_key(UnifiedRegion(None)); |
438 | assert_eq!(vid, u_vid.vid); | |
f9f354fc | 439 | self.undo_log.push(AddVar(vid)); |
dfeec247 | 440 | debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin); |
ba9703b0 | 441 | vid |
abe05a73 XL |
442 | } |
443 | ||
83c7162d XL |
444 | /// Returns the universe for the given variable. |
445 | pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex { | |
446 | self.var_infos[vid].universe | |
abe05a73 XL |
447 | } |
448 | ||
94222f64 XL |
449 | /// Returns the origin for the given variable. |
450 | pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin { | |
451 | self.var_infos[vid].origin | |
452 | } | |
453 | ||
abe05a73 XL |
454 | fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { |
455 | // cannot add constraints once regions are resolved | |
dfeec247 | 456 | debug!("RegionConstraintCollector: add_constraint({:?})", constraint); |
abe05a73 XL |
457 | |
458 | // never overwrite an existing (constraint, origin) - only insert one if it isn't | |
459 | // present in the map yet. This prevents origins from outside the snapshot being | |
0731742a | 460 | // replaced with "less informative" origins e.g., during calls to `can_eq` |
abe05a73 | 461 | let undo_log = &mut self.undo_log; |
f9f354fc XL |
462 | self.storage.data.constraints.entry(constraint).or_insert_with(|| { |
463 | undo_log.push(AddConstraint(constraint)); | |
abe05a73 XL |
464 | origin |
465 | }); | |
466 | } | |
467 | ||
468 | fn add_verify(&mut self, verify: Verify<'tcx>) { | |
469 | // cannot add verifys once regions are resolved | |
470 | debug!("RegionConstraintCollector: add_verify({:?})", verify); | |
471 | ||
472 | // skip no-op cases known to be satisfied | |
0bf4aa26 | 473 | if let VerifyBound::AllBounds(ref bs) = verify.bound { |
74b04a01 | 474 | if bs.is_empty() { |
abe05a73 XL |
475 | return; |
476 | } | |
abe05a73 XL |
477 | } |
478 | ||
479 | let index = self.data.verifys.len(); | |
480 | self.data.verifys.push(verify); | |
f9f354fc | 481 | self.undo_log.push(AddVerify(index)); |
abe05a73 XL |
482 | } |
483 | ||
484 | pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { | |
485 | // cannot add givens once regions are resolved | |
486 | if self.data.givens.insert((sub, sup)) { | |
487 | debug!("add_given({:?} <= {:?})", sub, sup); | |
488 | ||
f9f354fc | 489 | self.undo_log.push(AddGiven(sub, sup)); |
abe05a73 XL |
490 | } |
491 | } | |
492 | ||
493 | pub fn make_eqregion( | |
494 | &mut self, | |
495 | origin: SubregionOrigin<'tcx>, | |
496 | sub: Region<'tcx>, | |
497 | sup: Region<'tcx>, | |
498 | ) { | |
499 | if sub != sup { | |
500 | // Eventually, it would be nice to add direct support for | |
501 | // equating regions. | |
502 | self.make_subregion(origin.clone(), sub, sup); | |
503 | self.make_subregion(origin, sup, sub); | |
504 | ||
17df50a5 | 505 | match (sub, sup) { |
5099ac24 | 506 | (Region(Interned(ReVar(sub), _)), Region(Interned(ReVar(sup), _))) => { |
17df50a5 | 507 | debug!("make_eqregion: unifying {:?} with {:?}", sub, sup); |
5099ac24 | 508 | self.unification_table().union(*sub, *sup); |
17df50a5 XL |
509 | self.any_unifications = true; |
510 | } | |
5099ac24 FG |
511 | (Region(Interned(ReVar(vid), _)), value) |
512 | | (value, Region(Interned(ReVar(vid), _))) => { | |
17df50a5 | 513 | debug!("make_eqregion: unifying {:?} with {:?}", vid, value); |
5099ac24 | 514 | self.unification_table().union_value(*vid, UnifiedRegion(Some(value))); |
17df50a5 XL |
515 | self.any_unifications = true; |
516 | } | |
517 | (_, _) => {} | |
abe05a73 XL |
518 | } |
519 | } | |
520 | } | |
521 | ||
dc9dc135 XL |
522 | pub fn member_constraint( |
523 | &mut self, | |
524 | opaque_type_def_id: DefId, | |
525 | definition_span: Span, | |
526 | hidden_ty: Ty<'tcx>, | |
527 | member_region: ty::Region<'tcx>, | |
528 | choice_regions: &Lrc<Vec<ty::Region<'tcx>>>, | |
529 | ) { | |
530 | debug!("member_constraint({:?} in {:#?})", member_region, choice_regions); | |
531 | ||
532 | if choice_regions.iter().any(|&r| r == member_region) { | |
533 | return; | |
534 | } | |
535 | ||
536 | self.data.member_constraints.push(MemberConstraint { | |
537 | opaque_type_def_id, | |
538 | definition_span, | |
539 | hidden_ty, | |
540 | member_region, | |
dfeec247 | 541 | choice_regions: choice_regions.clone(), |
dc9dc135 | 542 | }); |
dc9dc135 XL |
543 | } |
544 | ||
c295e0f8 | 545 | #[instrument(skip(self, origin), level = "debug")] |
abe05a73 XL |
546 | pub fn make_subregion( |
547 | &mut self, | |
548 | origin: SubregionOrigin<'tcx>, | |
549 | sub: Region<'tcx>, | |
550 | sup: Region<'tcx>, | |
551 | ) { | |
552 | // cannot add constraints once regions are resolved | |
c295e0f8 | 553 | debug!("origin = {:#?}", origin); |
abe05a73 | 554 | |
5099ac24 FG |
555 | match (*sub, *sup) { |
556 | (ReLateBound(..), _) | (_, ReLateBound(..)) => { | |
dfeec247 | 557 | span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup); |
abe05a73 | 558 | } |
5099ac24 | 559 | (_, ReStatic) => { |
abe05a73 XL |
560 | // all regions are subregions of static, so we can ignore this |
561 | } | |
5099ac24 | 562 | (ReVar(sub_id), ReVar(sup_id)) => { |
abe05a73 XL |
563 | self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin); |
564 | } | |
5099ac24 | 565 | (_, ReVar(sup_id)) => { |
abe05a73 XL |
566 | self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin); |
567 | } | |
5099ac24 | 568 | (ReVar(sub_id), _) => { |
abe05a73 XL |
569 | self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin); |
570 | } | |
571 | _ => { | |
572 | self.add_constraint(Constraint::RegSubReg(sub, sup), origin); | |
573 | } | |
574 | } | |
575 | } | |
576 | ||
abe05a73 XL |
577 | pub fn verify_generic_bound( |
578 | &mut self, | |
579 | origin: SubregionOrigin<'tcx>, | |
580 | kind: GenericKind<'tcx>, | |
581 | sub: Region<'tcx>, | |
582 | bound: VerifyBound<'tcx>, | |
583 | ) { | |
dfeec247 | 584 | self.add_verify(Verify { kind, origin, region: sub, bound }); |
abe05a73 XL |
585 | } |
586 | ||
587 | pub fn lub_regions( | |
588 | &mut self, | |
dc9dc135 | 589 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
590 | origin: SubregionOrigin<'tcx>, |
591 | a: Region<'tcx>, | |
592 | b: Region<'tcx>, | |
593 | ) -> Region<'tcx> { | |
594 | // cannot add constraints once regions are resolved | |
595 | debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b); | |
5099ac24 FG |
596 | if a.is_static() || b.is_static() { |
597 | a // nothing lives longer than static | |
598 | } else if a == b { | |
599 | a // LUB(a,a) = a | |
600 | } else { | |
601 | self.combine_vars(tcx, Lub, a, b, origin) | |
abe05a73 XL |
602 | } |
603 | } | |
604 | ||
605 | pub fn glb_regions( | |
606 | &mut self, | |
dc9dc135 | 607 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
608 | origin: SubregionOrigin<'tcx>, |
609 | a: Region<'tcx>, | |
610 | b: Region<'tcx>, | |
611 | ) -> Region<'tcx> { | |
612 | // cannot add constraints once regions are resolved | |
613 | debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b); | |
5099ac24 FG |
614 | if a.is_static() { |
615 | b // static lives longer than everything else | |
616 | } else if b.is_static() { | |
617 | a // static lives longer than everything else | |
618 | } else if a == b { | |
619 | a // GLB(a,a) = a | |
620 | } else { | |
621 | self.combine_vars(tcx, Glb, a, b, origin) | |
abe05a73 XL |
622 | } |
623 | } | |
624 | ||
17df50a5 XL |
625 | /// Resolves the passed RegionVid to the root RegionVid in the unification table |
626 | pub fn opportunistic_resolve_var(&mut self, rid: ty::RegionVid) -> ty::RegionVid { | |
627 | self.unification_table().find(rid).vid | |
628 | } | |
629 | ||
630 | /// If the Region is a `ReVar`, then resolves it either to the root value in | |
631 | /// the unification table, if it exists, or to the root `ReVar` in the table. | |
632 | /// If the Region is not a `ReVar`, just returns the Region itself. | |
633 | pub fn opportunistic_resolve_region( | |
634 | &mut self, | |
635 | tcx: TyCtxt<'tcx>, | |
636 | region: ty::Region<'tcx>, | |
637 | ) -> ty::Region<'tcx> { | |
5099ac24 | 638 | match *region { |
17df50a5 | 639 | ty::ReVar(rid) => { |
5099ac24 | 640 | let unified_region = self.unification_table().probe_value(rid); |
17df50a5 | 641 | unified_region.0.unwrap_or_else(|| { |
5099ac24 | 642 | let root = self.unification_table().find(rid).vid; |
17df50a5 XL |
643 | tcx.reuse_or_mk_region(region, ty::ReVar(root)) |
644 | }) | |
645 | } | |
646 | _ => region, | |
647 | } | |
abe05a73 XL |
648 | } |
649 | ||
650 | fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { | |
651 | match t { | |
652 | Glb => &mut self.glbs, | |
653 | Lub => &mut self.lubs, | |
654 | } | |
655 | } | |
656 | ||
657 | fn combine_vars( | |
658 | &mut self, | |
dc9dc135 | 659 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
660 | t: CombineMapType, |
661 | a: Region<'tcx>, | |
662 | b: Region<'tcx>, | |
663 | origin: SubregionOrigin<'tcx>, | |
664 | ) -> Region<'tcx> { | |
74b04a01 | 665 | let vars = TwoRegions { a, b }; |
abe05a73 XL |
666 | if let Some(&c) = self.combine_map(t).get(&vars) { |
667 | return tcx.mk_region(ReVar(c)); | |
668 | } | |
83c7162d XL |
669 | let a_universe = self.universe(a); |
670 | let b_universe = self.universe(b); | |
671 | let c_universe = cmp::max(a_universe, b_universe); | |
672 | let c = self.new_region_var(c_universe, MiscVariable(origin.span())); | |
abe05a73 | 673 | self.combine_map(t).insert(vars, c); |
f9f354fc | 674 | self.undo_log.push(AddCombination(t, vars)); |
abe05a73 | 675 | let new_r = tcx.mk_region(ReVar(c)); |
136023e0 | 676 | for old_r in [a, b] { |
abe05a73 XL |
677 | match t { |
678 | Glb => self.make_subregion(origin.clone(), new_r, old_r), | |
679 | Lub => self.make_subregion(origin.clone(), old_r, new_r), | |
680 | } | |
681 | } | |
682 | debug!("combine_vars() c={:?}", c); | |
683 | new_r | |
684 | } | |
685 | ||
0731742a | 686 | pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex { |
83c7162d | 687 | match *region { |
f9f354fc XL |
688 | ty::ReStatic | ty::ReErased | ty::ReFree(..) | ty::ReEarlyBound(..) => { |
689 | ty::UniverseIndex::ROOT | |
690 | } | |
74b04a01 | 691 | ty::ReEmpty(ui) => ui, |
0bf4aa26 | 692 | ty::RePlaceholder(placeholder) => placeholder.universe, |
ba9703b0 | 693 | ty::ReVar(vid) => self.var_universe(vid), |
0bf4aa26 | 694 | ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region), |
83c7162d XL |
695 | } |
696 | } | |
697 | ||
532ac7d7 XL |
698 | pub fn vars_since_snapshot( |
699 | &self, | |
f9f354fc | 700 | value_count: usize, |
532ac7d7 | 701 | ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) { |
17df50a5 | 702 | let range = RegionVid::from(value_count)..RegionVid::from(self.unification_table.len()); |
dfeec247 XL |
703 | ( |
704 | range.clone(), | |
705 | (range.start.index()..range.end.index()) | |
706 | .map(|index| self.var_infos[ty::RegionVid::from(index)].origin) | |
707 | .collect(), | |
708 | ) | |
0731742a | 709 | } |
abe05a73 | 710 | |
f9f354fc XL |
711 | /// See `InferCtxt::region_constraints_added_in_snapshot`. |
712 | pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option<bool> { | |
713 | self.undo_log | |
714 | .region_constraints_in_snapshot(mark) | |
0731742a XL |
715 | .map(|&elt| match elt { |
716 | AddConstraint(constraint) => Some(constraint.involves_placeholders()), | |
717 | _ => None, | |
dfeec247 XL |
718 | }) |
719 | .max() | |
0731742a | 720 | .unwrap_or(None) |
abe05a73 | 721 | } |
f9f354fc XL |
722 | |
723 | #[inline] | |
17df50a5 | 724 | fn unification_table(&mut self) -> super::UnificationTable<'_, 'tcx, RegionVidKey<'tcx>> { |
f9f354fc XL |
725 | ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log) |
726 | } | |
abe05a73 XL |
727 | } |
728 | ||
729 | impl fmt::Debug for RegionSnapshot { | |
0bf4aa26 | 730 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
f9f354fc | 731 | write!(f, "RegionSnapshot") |
abe05a73 XL |
732 | } |
733 | } | |
734 | ||
735 | impl<'tcx> fmt::Debug for GenericKind<'tcx> { | |
0bf4aa26 | 736 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
737 | match *self { |
738 | GenericKind::Param(ref p) => write!(f, "{:?}", p), | |
739 | GenericKind::Projection(ref p) => write!(f, "{:?}", p), | |
740 | } | |
741 | } | |
742 | } | |
743 | ||
744 | impl<'tcx> fmt::Display for GenericKind<'tcx> { | |
0bf4aa26 | 745 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
746 | match *self { |
747 | GenericKind::Param(ref p) => write!(f, "{}", p), | |
748 | GenericKind::Projection(ref p) => write!(f, "{}", p), | |
749 | } | |
750 | } | |
751 | } | |
752 | ||
dc9dc135 XL |
753 | impl<'tcx> GenericKind<'tcx> { |
754 | pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { | |
abe05a73 XL |
755 | match *self { |
756 | GenericKind::Param(ref p) => p.to_ty(tcx), | |
757 | GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs), | |
758 | } | |
759 | } | |
760 | } | |
761 | ||
dc9dc135 | 762 | impl<'tcx> VerifyBound<'tcx> { |
abe05a73 XL |
763 | pub fn must_hold(&self) -> bool { |
764 | match self { | |
0bf4aa26 | 765 | VerifyBound::IfEq(..) => false, |
5099ac24 | 766 | VerifyBound::OutlivedBy(re) => re.is_static(), |
74b04a01 | 767 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
768 | VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()), |
769 | VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()), | |
abe05a73 XL |
770 | } |
771 | } | |
772 | ||
773 | pub fn cannot_hold(&self) -> bool { | |
774 | match self { | |
0bf4aa26 | 775 | VerifyBound::IfEq(_, b) => b.cannot_hold(), |
74b04a01 | 776 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
777 | VerifyBound::OutlivedBy(_) => false, |
778 | VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()), | |
779 | VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()), | |
abe05a73 XL |
780 | } |
781 | } | |
782 | ||
783 | pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
784 | if self.must_hold() || vb.cannot_hold() { | |
785 | self | |
786 | } else if self.cannot_hold() || vb.must_hold() { | |
787 | vb | |
788 | } else { | |
789 | VerifyBound::AnyBound(vec![self, vb]) | |
790 | } | |
791 | } | |
abe05a73 XL |
792 | } |
793 | ||
794 | impl<'tcx> RegionConstraintData<'tcx> { | |
9fa01778 XL |
795 | /// Returns `true` if this region constraint data contains no constraints, and `false` |
796 | /// otherwise. | |
abe05a73 | 797 | pub fn is_empty(&self) -> bool { |
dfeec247 XL |
798 | let RegionConstraintData { constraints, member_constraints, verifys, givens } = self; |
799 | constraints.is_empty() | |
800 | && member_constraints.is_empty() | |
801 | && verifys.is_empty() | |
802 | && givens.is_empty() | |
abe05a73 XL |
803 | } |
804 | } | |
f9f354fc XL |
805 | |
806 | impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> { | |
807 | fn reverse(&mut self, undo: UndoLog<'tcx>) { | |
808 | self.rollback_undo_entry(undo) | |
809 | } | |
810 | } |