]>
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 | ||
0bf4aa26 XL |
312 | /// When working with placeholder regions, we often wish to find all of |
313 | /// the regions that are either reachable from a placeholder region, or | |
314 | /// which can reach a placeholder region, or both. We call such regions | |
9fa01778 | 315 | /// *tainted* regions. This struct allows you to decide what set of |
abe05a73 XL |
316 | /// tainted regions you want. |
317 | #[derive(Debug)] | |
318 | pub struct TaintDirections { | |
319 | incoming: bool, | |
320 | outgoing: bool, | |
321 | } | |
322 | ||
323 | impl TaintDirections { | |
324 | pub fn incoming() -> Self { | |
dfeec247 | 325 | TaintDirections { incoming: true, outgoing: false } |
abe05a73 XL |
326 | } |
327 | ||
328 | pub fn outgoing() -> Self { | |
dfeec247 | 329 | TaintDirections { incoming: false, outgoing: true } |
abe05a73 XL |
330 | } |
331 | ||
332 | pub fn both() -> Self { | |
dfeec247 | 333 | TaintDirections { incoming: true, outgoing: true } |
abe05a73 XL |
334 | } |
335 | } | |
336 | ||
f9f354fc | 337 | impl<'tcx> RegionConstraintStorage<'tcx> { |
a1dfa0c6 XL |
338 | pub fn new() -> Self { |
339 | Self::default() | |
abe05a73 XL |
340 | } |
341 | ||
f9f354fc XL |
342 | #[inline] |
343 | pub(crate) fn with_log<'a>( | |
344 | &'a mut self, | |
345 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
346 | ) -> RegionConstraintCollector<'a, 'tcx> { | |
347 | RegionConstraintCollector { storage: self, undo_log } | |
348 | } | |
349 | ||
350 | fn rollback_undo_entry(&mut self, undo_entry: UndoLog<'tcx>) { | |
351 | match undo_entry { | |
f9f354fc XL |
352 | AddVar(vid) => { |
353 | self.var_infos.pop().unwrap(); | |
354 | assert_eq!(self.var_infos.len(), vid.index() as usize); | |
355 | } | |
356 | AddConstraint(ref constraint) => { | |
357 | self.data.constraints.remove(constraint); | |
358 | } | |
359 | AddVerify(index) => { | |
360 | self.data.verifys.pop(); | |
361 | assert_eq!(self.data.verifys.len(), index); | |
362 | } | |
363 | AddGiven(sub, sup) => { | |
364 | self.data.givens.remove(&(sub, sup)); | |
365 | } | |
366 | AddCombination(Glb, ref regions) => { | |
367 | self.glbs.remove(regions); | |
368 | } | |
369 | AddCombination(Lub, ref regions) => { | |
370 | self.lubs.remove(regions); | |
371 | } | |
372 | } | |
373 | } | |
374 | } | |
375 | ||
376 | impl<'tcx> RegionConstraintCollector<'_, 'tcx> { | |
83c7162d XL |
377 | pub fn num_region_vars(&self) -> usize { |
378 | self.var_infos.len() | |
abe05a73 XL |
379 | } |
380 | ||
0531ce1d XL |
381 | pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> { |
382 | &self.data | |
383 | } | |
384 | ||
abe05a73 XL |
385 | /// Once all the constraints have been gathered, extract out the final data. |
386 | /// | |
387 | /// Not legal during a snapshot. | |
83c7162d | 388 | pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) { |
f9f354fc XL |
389 | assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log)); |
390 | (mem::take(&mut self.storage.var_infos), mem::take(&mut self.storage.data)) | |
abe05a73 XL |
391 | } |
392 | ||
393 | /// Takes (and clears) the current set of constraints. Note that | |
394 | /// the set of variables remains intact, but all relationships | |
9fa01778 | 395 | /// between them are reset. This is used during NLL checking to |
abe05a73 XL |
396 | /// grab the set of constraints that arose from a particular |
397 | /// operation. | |
398 | /// | |
399 | /// We don't want to leak relationships between variables between | |
400 | /// points because just because (say) `r1 == r2` was true at some | |
401 | /// point P in the graph doesn't imply that it will be true at | |
402 | /// some other point Q, in NLL. | |
403 | /// | |
404 | /// Not legal during a snapshot. | |
405 | pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> { | |
f9f354fc | 406 | assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log)); |
abe05a73 XL |
407 | |
408 | // If you add a new field to `RegionConstraintCollector`, you | |
409 | // should think carefully about whether it needs to be cleared | |
410 | // or updated in some way. | |
f9f354fc | 411 | let RegionConstraintStorage { |
94b46f34 | 412 | var_infos: _, |
abe05a73 XL |
413 | data, |
414 | lubs, | |
415 | glbs, | |
f9f354fc | 416 | unification_table: _, |
94b46f34 | 417 | any_unifications, |
f9f354fc | 418 | } = self.storage; |
abe05a73 | 419 | |
abe05a73 XL |
420 | // Clear the tables of (lubs, glbs), so that we will create |
421 | // fresh regions if we do a LUB operation. As it happens, | |
422 | // LUB/GLB are not performed by the MIR type-checker, which is | |
423 | // the one that uses this method, but it's good to be correct. | |
424 | lubs.clear(); | |
425 | glbs.clear(); | |
426 | ||
f9f354fc XL |
427 | let data = mem::take(data); |
428 | ||
abe05a73 XL |
429 | // Clear all unifications and recreate the variables a "now |
430 | // un-unified" state. Note that when we unify `a` and `b`, we | |
431 | // also insert `a <= b` and a `b <= a` edges, so the | |
432 | // `RegionConstraintData` contains the relationship here. | |
94b46f34 | 433 | if *any_unifications { |
94b46f34 | 434 | *any_unifications = false; |
f9f354fc XL |
435 | self.unification_table() |
436 | .reset_unifications(|vid| unify_key::RegionVidKey { min_vid: vid }); | |
abe05a73 XL |
437 | } |
438 | ||
f9f354fc | 439 | data |
abe05a73 XL |
440 | } |
441 | ||
0531ce1d XL |
442 | pub fn data(&self) -> &RegionConstraintData<'tcx> { |
443 | &self.data | |
444 | } | |
445 | ||
abe05a73 | 446 | pub fn start_snapshot(&mut self) -> RegionSnapshot { |
f9f354fc XL |
447 | debug!("RegionConstraintCollector: start_snapshot"); |
448 | RegionSnapshot { any_unifications: self.any_unifications } | |
abe05a73 XL |
449 | } |
450 | ||
451 | pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { | |
452 | debug!("RegionConstraintCollector: rollback_to({:?})", snapshot); | |
94b46f34 | 453 | self.any_unifications = snapshot.any_unifications; |
abe05a73 XL |
454 | } |
455 | ||
0bf4aa26 XL |
456 | pub fn new_region_var( |
457 | &mut self, | |
458 | universe: ty::UniverseIndex, | |
459 | origin: RegionVariableOrigin, | |
460 | ) -> RegionVid { | |
461 | let vid = self.var_infos.push(RegionVariableInfo { origin, universe }); | |
abe05a73 | 462 | |
f9f354fc | 463 | let u_vid = self.unification_table().new_key(unify_key::RegionVidKey { min_vid: vid }); |
abe05a73 | 464 | assert_eq!(vid, u_vid); |
f9f354fc | 465 | self.undo_log.push(AddVar(vid)); |
dfeec247 | 466 | debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin); |
ba9703b0 | 467 | vid |
abe05a73 XL |
468 | } |
469 | ||
83c7162d XL |
470 | /// Returns the universe for the given variable. |
471 | pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex { | |
472 | self.var_infos[vid].universe | |
abe05a73 XL |
473 | } |
474 | ||
83c7162d XL |
475 | /// Returns the origin for the given variable. |
476 | pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin { | |
477 | self.var_infos[vid].origin | |
abe05a73 XL |
478 | } |
479 | ||
abe05a73 XL |
480 | fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { |
481 | // cannot add constraints once regions are resolved | |
dfeec247 | 482 | debug!("RegionConstraintCollector: add_constraint({:?})", constraint); |
abe05a73 XL |
483 | |
484 | // never overwrite an existing (constraint, origin) - only insert one if it isn't | |
485 | // present in the map yet. This prevents origins from outside the snapshot being | |
0731742a | 486 | // replaced with "less informative" origins e.g., during calls to `can_eq` |
abe05a73 | 487 | let undo_log = &mut self.undo_log; |
f9f354fc XL |
488 | self.storage.data.constraints.entry(constraint).or_insert_with(|| { |
489 | undo_log.push(AddConstraint(constraint)); | |
abe05a73 XL |
490 | origin |
491 | }); | |
492 | } | |
493 | ||
494 | fn add_verify(&mut self, verify: Verify<'tcx>) { | |
495 | // cannot add verifys once regions are resolved | |
496 | debug!("RegionConstraintCollector: add_verify({:?})", verify); | |
497 | ||
498 | // skip no-op cases known to be satisfied | |
0bf4aa26 | 499 | if let VerifyBound::AllBounds(ref bs) = verify.bound { |
74b04a01 | 500 | if bs.is_empty() { |
abe05a73 XL |
501 | return; |
502 | } | |
abe05a73 XL |
503 | } |
504 | ||
505 | let index = self.data.verifys.len(); | |
506 | self.data.verifys.push(verify); | |
f9f354fc | 507 | self.undo_log.push(AddVerify(index)); |
abe05a73 XL |
508 | } |
509 | ||
510 | pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { | |
511 | // cannot add givens once regions are resolved | |
512 | if self.data.givens.insert((sub, sup)) { | |
513 | debug!("add_given({:?} <= {:?})", sub, sup); | |
514 | ||
f9f354fc | 515 | self.undo_log.push(AddGiven(sub, sup)); |
abe05a73 XL |
516 | } |
517 | } | |
518 | ||
519 | pub fn make_eqregion( | |
520 | &mut self, | |
521 | origin: SubregionOrigin<'tcx>, | |
522 | sub: Region<'tcx>, | |
523 | sup: Region<'tcx>, | |
524 | ) { | |
525 | if sub != sup { | |
526 | // Eventually, it would be nice to add direct support for | |
527 | // equating regions. | |
528 | self.make_subregion(origin.clone(), sub, sup); | |
529 | self.make_subregion(origin, sup, sub); | |
530 | ||
531 | if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) { | |
9fa01778 | 532 | debug!("make_eqregion: uniying {:?} with {:?}", sub, sup); |
f9f354fc | 533 | self.unification_table().union(sub, sup); |
94b46f34 | 534 | self.any_unifications = true; |
abe05a73 XL |
535 | } |
536 | } | |
537 | } | |
538 | ||
dc9dc135 XL |
539 | pub fn member_constraint( |
540 | &mut self, | |
541 | opaque_type_def_id: DefId, | |
542 | definition_span: Span, | |
543 | hidden_ty: Ty<'tcx>, | |
544 | member_region: ty::Region<'tcx>, | |
545 | choice_regions: &Lrc<Vec<ty::Region<'tcx>>>, | |
546 | ) { | |
547 | debug!("member_constraint({:?} in {:#?})", member_region, choice_regions); | |
548 | ||
549 | if choice_regions.iter().any(|&r| r == member_region) { | |
550 | return; | |
551 | } | |
552 | ||
553 | self.data.member_constraints.push(MemberConstraint { | |
554 | opaque_type_def_id, | |
555 | definition_span, | |
556 | hidden_ty, | |
557 | member_region, | |
dfeec247 | 558 | choice_regions: choice_regions.clone(), |
dc9dc135 | 559 | }); |
dc9dc135 XL |
560 | } |
561 | ||
abe05a73 XL |
562 | pub fn make_subregion( |
563 | &mut self, | |
564 | origin: SubregionOrigin<'tcx>, | |
565 | sub: Region<'tcx>, | |
566 | sup: Region<'tcx>, | |
567 | ) { | |
568 | // cannot add constraints once regions are resolved | |
569 | debug!( | |
570 | "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}", | |
0bf4aa26 | 571 | sub, sup, origin |
abe05a73 XL |
572 | ); |
573 | ||
574 | match (sub, sup) { | |
575 | (&ReLateBound(..), _) | (_, &ReLateBound(..)) => { | |
dfeec247 | 576 | span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup); |
abe05a73 XL |
577 | } |
578 | (_, &ReStatic) => { | |
579 | // all regions are subregions of static, so we can ignore this | |
580 | } | |
581 | (&ReVar(sub_id), &ReVar(sup_id)) => { | |
582 | self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin); | |
583 | } | |
584 | (_, &ReVar(sup_id)) => { | |
585 | self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin); | |
586 | } | |
587 | (&ReVar(sub_id), _) => { | |
588 | self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin); | |
589 | } | |
590 | _ => { | |
591 | self.add_constraint(Constraint::RegSubReg(sub, sup), origin); | |
592 | } | |
593 | } | |
594 | } | |
595 | ||
abe05a73 XL |
596 | pub fn verify_generic_bound( |
597 | &mut self, | |
598 | origin: SubregionOrigin<'tcx>, | |
599 | kind: GenericKind<'tcx>, | |
600 | sub: Region<'tcx>, | |
601 | bound: VerifyBound<'tcx>, | |
602 | ) { | |
dfeec247 | 603 | self.add_verify(Verify { kind, origin, region: sub, bound }); |
abe05a73 XL |
604 | } |
605 | ||
606 | pub fn lub_regions( | |
607 | &mut self, | |
dc9dc135 | 608 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
609 | origin: SubregionOrigin<'tcx>, |
610 | a: Region<'tcx>, | |
611 | b: Region<'tcx>, | |
612 | ) -> Region<'tcx> { | |
613 | // cannot add constraints once regions are resolved | |
614 | debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b); | |
615 | match (a, b) { | |
616 | (r @ &ReStatic, _) | (_, r @ &ReStatic) => { | |
617 | r // nothing lives longer than static | |
618 | } | |
619 | ||
620 | _ if a == b => { | |
621 | a // LUB(a,a) = a | |
622 | } | |
623 | ||
0bf4aa26 | 624 | _ => self.combine_vars(tcx, Lub, a, b, origin), |
abe05a73 XL |
625 | } |
626 | } | |
627 | ||
628 | pub fn glb_regions( | |
629 | &mut self, | |
dc9dc135 | 630 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
631 | origin: SubregionOrigin<'tcx>, |
632 | a: Region<'tcx>, | |
633 | b: Region<'tcx>, | |
634 | ) -> Region<'tcx> { | |
635 | // cannot add constraints once regions are resolved | |
636 | debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b); | |
637 | match (a, b) { | |
638 | (&ReStatic, r) | (r, &ReStatic) => { | |
639 | r // static lives longer than everything else | |
640 | } | |
641 | ||
642 | _ if a == b => { | |
643 | a // GLB(a,a) = a | |
644 | } | |
645 | ||
0bf4aa26 | 646 | _ => self.combine_vars(tcx, Glb, a, b, origin), |
abe05a73 XL |
647 | } |
648 | } | |
649 | ||
f035d41b XL |
650 | pub fn opportunistic_resolve_var(&mut self, rid: RegionVid) -> ty::RegionVid { |
651 | self.unification_table().probe_value(rid).min_vid | |
abe05a73 XL |
652 | } |
653 | ||
654 | fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { | |
655 | match t { | |
656 | Glb => &mut self.glbs, | |
657 | Lub => &mut self.lubs, | |
658 | } | |
659 | } | |
660 | ||
661 | fn combine_vars( | |
662 | &mut self, | |
dc9dc135 | 663 | tcx: TyCtxt<'tcx>, |
abe05a73 XL |
664 | t: CombineMapType, |
665 | a: Region<'tcx>, | |
666 | b: Region<'tcx>, | |
667 | origin: SubregionOrigin<'tcx>, | |
668 | ) -> Region<'tcx> { | |
74b04a01 | 669 | let vars = TwoRegions { a, b }; |
abe05a73 XL |
670 | if let Some(&c) = self.combine_map(t).get(&vars) { |
671 | return tcx.mk_region(ReVar(c)); | |
672 | } | |
83c7162d XL |
673 | let a_universe = self.universe(a); |
674 | let b_universe = self.universe(b); | |
675 | let c_universe = cmp::max(a_universe, b_universe); | |
676 | let c = self.new_region_var(c_universe, MiscVariable(origin.span())); | |
abe05a73 | 677 | self.combine_map(t).insert(vars, c); |
f9f354fc | 678 | self.undo_log.push(AddCombination(t, vars)); |
abe05a73 XL |
679 | let new_r = tcx.mk_region(ReVar(c)); |
680 | for &old_r in &[a, b] { | |
681 | match t { | |
682 | Glb => self.make_subregion(origin.clone(), new_r, old_r), | |
683 | Lub => self.make_subregion(origin.clone(), old_r, new_r), | |
684 | } | |
685 | } | |
686 | debug!("combine_vars() c={:?}", c); | |
687 | new_r | |
688 | } | |
689 | ||
0731742a | 690 | pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex { |
83c7162d | 691 | match *region { |
f9f354fc XL |
692 | ty::ReStatic | ty::ReErased | ty::ReFree(..) | ty::ReEarlyBound(..) => { |
693 | ty::UniverseIndex::ROOT | |
694 | } | |
74b04a01 | 695 | ty::ReEmpty(ui) => ui, |
0bf4aa26 | 696 | ty::RePlaceholder(placeholder) => placeholder.universe, |
ba9703b0 | 697 | ty::ReVar(vid) => self.var_universe(vid), |
0bf4aa26 | 698 | ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region), |
83c7162d XL |
699 | } |
700 | } | |
701 | ||
532ac7d7 XL |
702 | pub fn vars_since_snapshot( |
703 | &self, | |
f9f354fc | 704 | value_count: usize, |
532ac7d7 | 705 | ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) { |
f9f354fc XL |
706 | let range = RegionVid::from_index(value_count as u32) |
707 | ..RegionVid::from_index(self.unification_table.len() as u32); | |
dfeec247 XL |
708 | ( |
709 | range.clone(), | |
710 | (range.start.index()..range.end.index()) | |
711 | .map(|index| self.var_infos[ty::RegionVid::from(index)].origin) | |
712 | .collect(), | |
713 | ) | |
0731742a | 714 | } |
abe05a73 | 715 | |
f9f354fc XL |
716 | /// See `InferCtxt::region_constraints_added_in_snapshot`. |
717 | pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option<bool> { | |
718 | self.undo_log | |
719 | .region_constraints_in_snapshot(mark) | |
0731742a XL |
720 | .map(|&elt| match elt { |
721 | AddConstraint(constraint) => Some(constraint.involves_placeholders()), | |
722 | _ => None, | |
dfeec247 XL |
723 | }) |
724 | .max() | |
0731742a | 725 | .unwrap_or(None) |
abe05a73 | 726 | } |
f9f354fc XL |
727 | |
728 | #[inline] | |
729 | fn unification_table(&mut self) -> super::UnificationTable<'_, 'tcx, ty::RegionVid> { | |
730 | ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log) | |
731 | } | |
abe05a73 XL |
732 | } |
733 | ||
734 | impl fmt::Debug for RegionSnapshot { | |
0bf4aa26 | 735 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
f9f354fc | 736 | write!(f, "RegionSnapshot") |
abe05a73 XL |
737 | } |
738 | } | |
739 | ||
740 | impl<'tcx> fmt::Debug for GenericKind<'tcx> { | |
0bf4aa26 | 741 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
742 | match *self { |
743 | GenericKind::Param(ref p) => write!(f, "{:?}", p), | |
744 | GenericKind::Projection(ref p) => write!(f, "{:?}", p), | |
745 | } | |
746 | } | |
747 | } | |
748 | ||
749 | impl<'tcx> fmt::Display for GenericKind<'tcx> { | |
0bf4aa26 | 750 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
751 | match *self { |
752 | GenericKind::Param(ref p) => write!(f, "{}", p), | |
753 | GenericKind::Projection(ref p) => write!(f, "{}", p), | |
754 | } | |
755 | } | |
756 | } | |
757 | ||
dc9dc135 XL |
758 | impl<'tcx> GenericKind<'tcx> { |
759 | pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { | |
abe05a73 XL |
760 | match *self { |
761 | GenericKind::Param(ref p) => p.to_ty(tcx), | |
762 | GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs), | |
763 | } | |
764 | } | |
765 | } | |
766 | ||
dc9dc135 | 767 | impl<'tcx> VerifyBound<'tcx> { |
abe05a73 XL |
768 | pub fn must_hold(&self) -> bool { |
769 | match self { | |
0bf4aa26 XL |
770 | VerifyBound::IfEq(..) => false, |
771 | VerifyBound::OutlivedBy(ty::ReStatic) => true, | |
772 | VerifyBound::OutlivedBy(_) => false, | |
74b04a01 | 773 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
774 | VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()), |
775 | VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()), | |
abe05a73 XL |
776 | } |
777 | } | |
778 | ||
779 | pub fn cannot_hold(&self) -> bool { | |
780 | match self { | |
0bf4aa26 | 781 | VerifyBound::IfEq(_, b) => b.cannot_hold(), |
74b04a01 | 782 | VerifyBound::IsEmpty => false, |
0bf4aa26 XL |
783 | VerifyBound::OutlivedBy(_) => false, |
784 | VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()), | |
785 | VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()), | |
abe05a73 XL |
786 | } |
787 | } | |
788 | ||
789 | pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
790 | if self.must_hold() || vb.cannot_hold() { | |
791 | self | |
792 | } else if self.cannot_hold() || vb.must_hold() { | |
793 | vb | |
794 | } else { | |
795 | VerifyBound::AnyBound(vec![self, vb]) | |
796 | } | |
797 | } | |
798 | ||
799 | pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
800 | if self.must_hold() && vb.must_hold() { | |
801 | self | |
802 | } else if self.cannot_hold() && vb.cannot_hold() { | |
803 | self | |
804 | } else { | |
805 | VerifyBound::AllBounds(vec![self, vb]) | |
806 | } | |
807 | } | |
808 | } | |
809 | ||
810 | impl<'tcx> RegionConstraintData<'tcx> { | |
9fa01778 XL |
811 | /// Returns `true` if this region constraint data contains no constraints, and `false` |
812 | /// otherwise. | |
abe05a73 | 813 | pub fn is_empty(&self) -> bool { |
dfeec247 XL |
814 | let RegionConstraintData { constraints, member_constraints, verifys, givens } = self; |
815 | constraints.is_empty() | |
816 | && member_constraints.is_empty() | |
817 | && verifys.is_empty() | |
818 | && givens.is_empty() | |
abe05a73 XL |
819 | } |
820 | } | |
f9f354fc XL |
821 | |
822 | impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> { | |
823 | fn reverse(&mut self, undo: UndoLog<'tcx>) { | |
824 | self.rollback_undo_entry(undo) | |
825 | } | |
826 | } |