]>
Commit | Line | Data |
---|---|---|
abe05a73 XL |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! See README.md | |
12 | ||
13 | use self::UndoLogEntry::*; | |
14 | use self::CombineMapType::*; | |
15 | ||
16 | use super::{MiscVariable, RegionVariableOrigin, SubregionOrigin}; | |
17 | use super::unify_key; | |
18 | ||
b7449926 | 19 | use rustc_data_structures::indexed_vec::IndexVec; |
abe05a73 | 20 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
0531ce1d | 21 | use rustc_data_structures::unify as ut; |
abe05a73 XL |
22 | use ty::{self, Ty, TyCtxt}; |
23 | use ty::{Region, RegionVid}; | |
24 | use ty::ReStatic; | |
83c7162d | 25 | use ty::{BrFresh, ReLateBound, ReVar}; |
abe05a73 XL |
26 | |
27 | use std::collections::BTreeMap; | |
83c7162d | 28 | use std::{cmp, fmt, mem, u32}; |
abe05a73 XL |
29 | |
30 | mod taint; | |
31 | ||
32 | pub struct RegionConstraintCollector<'tcx> { | |
33 | /// For each `RegionVid`, the corresponding `RegionVariableOrigin`. | |
83c7162d | 34 | var_infos: IndexVec<RegionVid, RegionVariableInfo>, |
abe05a73 XL |
35 | |
36 | data: RegionConstraintData<'tcx>, | |
37 | ||
38 | /// For a given pair of regions (R1, R2), maps to a region R3 that | |
39 | /// is designated as their LUB (edges R1 <= R3 and R2 <= R3 | |
40 | /// exist). This prevents us from making many such regions. | |
41 | lubs: CombineMap<'tcx>, | |
42 | ||
43 | /// For a given pair of regions (R1, R2), maps to a region R3 that | |
44 | /// is designated as their GLB (edges R3 <= R1 and R3 <= R2 | |
45 | /// exist). This prevents us from making many such regions. | |
46 | glbs: CombineMap<'tcx>, | |
47 | ||
abe05a73 XL |
48 | /// Global counter used during the GLB algorithm to create unique |
49 | /// names for fresh bound regions | |
50 | bound_count: u32, | |
51 | ||
52 | /// The undo log records actions that might later be undone. | |
53 | /// | |
54 | /// Note: when the undo_log is empty, we are not actively | |
55 | /// snapshotting. When the `start_snapshot()` method is called, we | |
56 | /// push an OpenSnapshot entry onto the list to indicate that we | |
57 | /// are now actively snapshotting. The reason for this is that | |
58 | /// otherwise we end up adding entries for things like the lower | |
59 | /// bound on a variable and so forth, which can never be rolled | |
60 | /// back. | |
61 | undo_log: Vec<UndoLogEntry<'tcx>>, | |
62 | ||
63 | /// When we add a R1 == R2 constriant, we currently add (a) edges | |
64 | /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this | |
65 | /// table. You can then call `opportunistic_resolve_var` early | |
66 | /// which will map R1 and R2 to some common region (i.e., either | |
67 | /// R1 or R2). This is important when dropck and other such code | |
68 | /// is iterating to a fixed point, because otherwise we sometimes | |
69 | /// would wind up with a fresh stream of region variables that | |
70 | /// have been equated but appear distinct. | |
0531ce1d | 71 | unification_table: ut::UnificationTable<ut::InPlace<ty::RegionVid>>, |
94b46f34 XL |
72 | |
73 | /// a flag set to true when we perform any unifications; this is used | |
74 | /// to micro-optimize `take_and_reset_data` | |
75 | any_unifications: bool, | |
abe05a73 XL |
76 | } |
77 | ||
83c7162d | 78 | pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>; |
abe05a73 XL |
79 | |
80 | /// The full set of region constraints gathered up by the collector. | |
81 | /// Describes constraints between the region variables and other | |
82 | /// regions, as well as other conditions that must be verified, or | |
83 | /// assumptions that can be made. | |
0531ce1d | 84 | #[derive(Debug, Default, Clone)] |
abe05a73 XL |
85 | pub struct RegionConstraintData<'tcx> { |
86 | /// Constraints of the form `A <= B`, where either `A` or `B` can | |
87 | /// be a region variable (or neither, as it happens). | |
88 | pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>, | |
89 | ||
90 | /// A "verify" is something that we need to verify after inference | |
91 | /// is done, but which does not directly affect inference in any | |
92 | /// way. | |
93 | /// | |
94 | /// An example is a `A <= B` where neither `A` nor `B` are | |
95 | /// inference variables. | |
96 | pub verifys: Vec<Verify<'tcx>>, | |
97 | ||
98 | /// A "given" is a relationship that is known to hold. In | |
99 | /// particular, we often know from closure fn signatures that a | |
100 | /// particular free region must be a subregion of a region | |
101 | /// variable: | |
102 | /// | |
103 | /// foo.iter().filter(<'a> |x: &'a &'b T| ...) | |
104 | /// | |
105 | /// In situations like this, `'b` is in fact a region variable | |
106 | /// introduced by the call to `iter()`, and `'a` is a bound region | |
107 | /// on the closure (as indicated by the `<'a>` prefix). If we are | |
108 | /// naive, we wind up inferring that `'b` must be `'static`, | |
109 | /// because we require that it be greater than `'a` and we do not | |
110 | /// know what `'a` is precisely. | |
111 | /// | |
112 | /// This hashmap is used to avoid that naive scenario. Basically | |
113 | /// we record the fact that `'a <= 'b` is implied by the fn | |
114 | /// signature, and then ignore the constraint when solving | |
115 | /// equations. This is a bit of a hack but seems to work. | |
116 | pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>, | |
117 | } | |
118 | ||
119 | /// A constraint that influences the inference process. | |
120 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)] | |
121 | pub enum Constraint<'tcx> { | |
122 | /// One region variable is subregion of another | |
123 | VarSubVar(RegionVid, RegionVid), | |
124 | ||
125 | /// Concrete region is subregion of region variable | |
126 | RegSubVar(Region<'tcx>, RegionVid), | |
127 | ||
128 | /// Region variable is subregion of concrete region. This does not | |
129 | /// directly affect inference, but instead is checked after | |
130 | /// inference is complete. | |
131 | VarSubReg(RegionVid, Region<'tcx>), | |
132 | ||
133 | /// A constraint where neither side is a variable. This does not | |
134 | /// directly affect inference, but instead is checked after | |
135 | /// inference is complete. | |
136 | RegSubReg(Region<'tcx>, Region<'tcx>), | |
137 | } | |
138 | ||
139 | /// VerifyGenericBound(T, _, R, RS): The parameter type `T` (or | |
140 | /// associated type) must outlive the region `R`. `T` is known to | |
141 | /// outlive `RS`. Therefore verify that `R <= RS[i]` for some | |
142 | /// `i`. Inference variables may be involved (but this verification | |
143 | /// step doesn't influence inference). | |
0531ce1d | 144 | #[derive(Debug, Clone)] |
abe05a73 XL |
145 | pub struct Verify<'tcx> { |
146 | pub kind: GenericKind<'tcx>, | |
147 | pub origin: SubregionOrigin<'tcx>, | |
148 | pub region: Region<'tcx>, | |
149 | pub bound: VerifyBound<'tcx>, | |
150 | } | |
151 | ||
152 | #[derive(Copy, Clone, PartialEq, Eq)] | |
153 | pub enum GenericKind<'tcx> { | |
154 | Param(ty::ParamTy), | |
155 | Projection(ty::ProjectionTy<'tcx>), | |
156 | } | |
157 | ||
158 | /// When we introduce a verification step, we wish to test that a | |
159 | /// particular region (let's call it `'min`) meets some bound. | |
160 | /// The bound is described the by the following grammar: | |
0531ce1d | 161 | #[derive(Debug, Clone)] |
abe05a73 XL |
162 | pub enum VerifyBound<'tcx> { |
163 | /// B = exists {R} --> some 'r in {R} must outlive 'min | |
164 | /// | |
165 | /// Put another way, the subject value is known to outlive all | |
166 | /// regions in {R}, so if any of those outlives 'min, then the | |
167 | /// bound is met. | |
168 | AnyRegion(Vec<Region<'tcx>>), | |
169 | ||
170 | /// B = forall {R} --> all 'r in {R} must outlive 'min | |
171 | /// | |
172 | /// Put another way, the subject value is known to outlive some | |
173 | /// region in {R}, so if all of those outlives 'min, then the bound | |
174 | /// is met. | |
175 | AllRegions(Vec<Region<'tcx>>), | |
176 | ||
177 | /// B = exists {B} --> 'min must meet some bound b in {B} | |
178 | AnyBound(Vec<VerifyBound<'tcx>>), | |
179 | ||
180 | /// B = forall {B} --> 'min must meet all bounds b in {B} | |
181 | AllBounds(Vec<VerifyBound<'tcx>>), | |
182 | } | |
183 | ||
184 | #[derive(Copy, Clone, PartialEq, Eq, Hash)] | |
185 | struct TwoRegions<'tcx> { | |
186 | a: Region<'tcx>, | |
187 | b: Region<'tcx>, | |
188 | } | |
189 | ||
190 | #[derive(Copy, Clone, PartialEq)] | |
191 | enum UndoLogEntry<'tcx> { | |
192 | /// Pushed when we start a snapshot. | |
193 | OpenSnapshot, | |
194 | ||
195 | /// Replaces an `OpenSnapshot` when a snapshot is committed, but | |
196 | /// that snapshot is not the root. If the root snapshot is | |
197 | /// unrolled, all nested snapshots must be committed. | |
198 | CommitedSnapshot, | |
199 | ||
200 | /// We added `RegionVid` | |
201 | AddVar(RegionVid), | |
202 | ||
203 | /// We added the given `constraint` | |
204 | AddConstraint(Constraint<'tcx>), | |
205 | ||
206 | /// We added the given `verify` | |
207 | AddVerify(usize), | |
208 | ||
209 | /// We added the given `given` | |
210 | AddGiven(Region<'tcx>, ty::RegionVid), | |
211 | ||
212 | /// We added a GLB/LUB "combination variable" | |
213 | AddCombination(CombineMapType, TwoRegions<'tcx>), | |
214 | ||
215 | /// During skolemization, we sometimes purge entries from the undo | |
216 | /// log in a kind of minisnapshot (unlike other snapshots, this | |
217 | /// purging actually takes place *on success*). In that case, we | |
218 | /// replace the corresponding entry with `Noop` so as to avoid the | |
219 | /// need to do a bunch of swapping. (We can't use `swap_remove` as | |
220 | /// the order of the vector is important.) | |
221 | Purged, | |
222 | } | |
223 | ||
224 | #[derive(Copy, Clone, PartialEq)] | |
225 | enum CombineMapType { | |
226 | Lub, | |
227 | Glb, | |
228 | } | |
229 | ||
230 | type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>; | |
231 | ||
83c7162d XL |
232 | #[derive(Debug, Clone, Copy)] |
233 | pub struct RegionVariableInfo { | |
234 | pub origin: RegionVariableOrigin, | |
235 | pub universe: ty::UniverseIndex, | |
236 | } | |
237 | ||
abe05a73 XL |
238 | pub struct RegionSnapshot { |
239 | length: usize, | |
0531ce1d | 240 | region_snapshot: ut::Snapshot<ut::InPlace<ty::RegionVid>>, |
94b46f34 | 241 | any_unifications: bool, |
abe05a73 XL |
242 | } |
243 | ||
244 | /// When working with skolemized regions, we often wish to find all of | |
245 | /// the regions that are either reachable from a skolemized region, or | |
246 | /// which can reach a skolemized region, or both. We call such regions | |
247 | /// *tained* regions. This struct allows you to decide what set of | |
248 | /// tainted regions you want. | |
249 | #[derive(Debug)] | |
250 | pub struct TaintDirections { | |
251 | incoming: bool, | |
252 | outgoing: bool, | |
253 | } | |
254 | ||
255 | impl TaintDirections { | |
256 | pub fn incoming() -> Self { | |
257 | TaintDirections { | |
258 | incoming: true, | |
259 | outgoing: false, | |
260 | } | |
261 | } | |
262 | ||
263 | pub fn outgoing() -> Self { | |
264 | TaintDirections { | |
265 | incoming: false, | |
266 | outgoing: true, | |
267 | } | |
268 | } | |
269 | ||
270 | pub fn both() -> Self { | |
271 | TaintDirections { | |
272 | incoming: true, | |
273 | outgoing: true, | |
274 | } | |
275 | } | |
276 | } | |
277 | ||
278 | impl<'tcx> RegionConstraintCollector<'tcx> { | |
279 | pub fn new() -> RegionConstraintCollector<'tcx> { | |
280 | RegionConstraintCollector { | |
83c7162d | 281 | var_infos: VarInfos::default(), |
abe05a73 XL |
282 | data: RegionConstraintData::default(), |
283 | lubs: FxHashMap(), | |
284 | glbs: FxHashMap(), | |
abe05a73 XL |
285 | bound_count: 0, |
286 | undo_log: Vec::new(), | |
0531ce1d | 287 | unification_table: ut::UnificationTable::new(), |
94b46f34 | 288 | any_unifications: false, |
abe05a73 XL |
289 | } |
290 | } | |
291 | ||
83c7162d XL |
292 | pub fn num_region_vars(&self) -> usize { |
293 | self.var_infos.len() | |
abe05a73 XL |
294 | } |
295 | ||
0531ce1d XL |
296 | pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> { |
297 | &self.data | |
298 | } | |
299 | ||
abe05a73 XL |
300 | /// Once all the constraints have been gathered, extract out the final data. |
301 | /// | |
302 | /// Not legal during a snapshot. | |
83c7162d | 303 | pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) { |
abe05a73 | 304 | assert!(!self.in_snapshot()); |
83c7162d | 305 | (self.var_infos, self.data) |
abe05a73 XL |
306 | } |
307 | ||
308 | /// Takes (and clears) the current set of constraints. Note that | |
309 | /// the set of variables remains intact, but all relationships | |
310 | /// between them are reset. This is used during NLL checking to | |
311 | /// grab the set of constraints that arose from a particular | |
312 | /// operation. | |
313 | /// | |
314 | /// We don't want to leak relationships between variables between | |
315 | /// points because just because (say) `r1 == r2` was true at some | |
316 | /// point P in the graph doesn't imply that it will be true at | |
317 | /// some other point Q, in NLL. | |
318 | /// | |
319 | /// Not legal during a snapshot. | |
320 | pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> { | |
321 | assert!(!self.in_snapshot()); | |
322 | ||
323 | // If you add a new field to `RegionConstraintCollector`, you | |
324 | // should think carefully about whether it needs to be cleared | |
325 | // or updated in some way. | |
326 | let RegionConstraintCollector { | |
94b46f34 | 327 | var_infos: _, |
abe05a73 XL |
328 | data, |
329 | lubs, | |
330 | glbs, | |
abe05a73 XL |
331 | bound_count: _, |
332 | undo_log: _, | |
333 | unification_table, | |
94b46f34 | 334 | any_unifications, |
abe05a73 XL |
335 | } = self; |
336 | ||
abe05a73 XL |
337 | // Clear the tables of (lubs, glbs), so that we will create |
338 | // fresh regions if we do a LUB operation. As it happens, | |
339 | // LUB/GLB are not performed by the MIR type-checker, which is | |
340 | // the one that uses this method, but it's good to be correct. | |
341 | lubs.clear(); | |
342 | glbs.clear(); | |
343 | ||
344 | // Clear all unifications and recreate the variables a "now | |
345 | // un-unified" state. Note that when we unify `a` and `b`, we | |
346 | // also insert `a <= b` and a `b <= a` edges, so the | |
347 | // `RegionConstraintData` contains the relationship here. | |
94b46f34 XL |
348 | if *any_unifications { |
349 | unification_table.reset_unifications(|vid| unify_key::RegionVidKey { min_vid: vid }); | |
350 | *any_unifications = false; | |
abe05a73 XL |
351 | } |
352 | ||
353 | mem::replace(data, RegionConstraintData::default()) | |
354 | } | |
355 | ||
0531ce1d XL |
356 | pub fn data(&self) -> &RegionConstraintData<'tcx> { |
357 | &self.data | |
358 | } | |
359 | ||
abe05a73 XL |
360 | fn in_snapshot(&self) -> bool { |
361 | !self.undo_log.is_empty() | |
362 | } | |
363 | ||
364 | pub fn start_snapshot(&mut self) -> RegionSnapshot { | |
365 | let length = self.undo_log.len(); | |
366 | debug!("RegionConstraintCollector: start_snapshot({})", length); | |
367 | self.undo_log.push(OpenSnapshot); | |
368 | RegionSnapshot { | |
369 | length, | |
370 | region_snapshot: self.unification_table.snapshot(), | |
94b46f34 | 371 | any_unifications: self.any_unifications, |
abe05a73 XL |
372 | } |
373 | } | |
374 | ||
375 | pub fn commit(&mut self, snapshot: RegionSnapshot) { | |
376 | debug!("RegionConstraintCollector: commit({})", snapshot.length); | |
377 | assert!(self.undo_log.len() > snapshot.length); | |
378 | assert!(self.undo_log[snapshot.length] == OpenSnapshot); | |
abe05a73 XL |
379 | |
380 | if snapshot.length == 0 { | |
381 | self.undo_log.truncate(0); | |
382 | } else { | |
383 | (*self.undo_log)[snapshot.length] = CommitedSnapshot; | |
384 | } | |
385 | self.unification_table.commit(snapshot.region_snapshot); | |
386 | } | |
387 | ||
388 | pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { | |
389 | debug!("RegionConstraintCollector: rollback_to({:?})", snapshot); | |
390 | assert!(self.undo_log.len() > snapshot.length); | |
391 | assert!(self.undo_log[snapshot.length] == OpenSnapshot); | |
392 | while self.undo_log.len() > snapshot.length + 1 { | |
393 | let undo_entry = self.undo_log.pop().unwrap(); | |
394 | self.rollback_undo_entry(undo_entry); | |
395 | } | |
396 | let c = self.undo_log.pop().unwrap(); | |
397 | assert!(c == OpenSnapshot); | |
abe05a73 | 398 | self.unification_table.rollback_to(snapshot.region_snapshot); |
94b46f34 | 399 | self.any_unifications = snapshot.any_unifications; |
abe05a73 XL |
400 | } |
401 | ||
402 | fn rollback_undo_entry(&mut self, undo_entry: UndoLogEntry<'tcx>) { | |
403 | match undo_entry { | |
404 | OpenSnapshot => { | |
405 | panic!("Failure to observe stack discipline"); | |
406 | } | |
407 | Purged | CommitedSnapshot => { | |
408 | // nothing to do here | |
409 | } | |
410 | AddVar(vid) => { | |
83c7162d XL |
411 | self.var_infos.pop().unwrap(); |
412 | assert_eq!(self.var_infos.len(), vid.index() as usize); | |
abe05a73 XL |
413 | } |
414 | AddConstraint(ref constraint) => { | |
415 | self.data.constraints.remove(constraint); | |
416 | } | |
417 | AddVerify(index) => { | |
418 | self.data.verifys.pop(); | |
419 | assert_eq!(self.data.verifys.len(), index); | |
420 | } | |
421 | AddGiven(sub, sup) => { | |
422 | self.data.givens.remove(&(sub, sup)); | |
423 | } | |
424 | AddCombination(Glb, ref regions) => { | |
425 | self.glbs.remove(regions); | |
426 | } | |
427 | AddCombination(Lub, ref regions) => { | |
428 | self.lubs.remove(regions); | |
429 | } | |
430 | } | |
431 | } | |
432 | ||
83c7162d XL |
433 | pub fn new_region_var(&mut self, |
434 | universe: ty::UniverseIndex, | |
435 | origin: RegionVariableOrigin) -> RegionVid { | |
436 | let vid = self.var_infos.push(RegionVariableInfo { | |
437 | origin, | |
438 | universe, | |
439 | }); | |
abe05a73 XL |
440 | |
441 | let u_vid = self.unification_table | |
442 | .new_key(unify_key::RegionVidKey { min_vid: vid }); | |
443 | assert_eq!(vid, u_vid); | |
444 | if self.in_snapshot() { | |
445 | self.undo_log.push(AddVar(vid)); | |
446 | } | |
447 | debug!( | |
448 | "created new region variable {:?} with origin {:?}", | |
449 | vid, | |
450 | origin | |
451 | ); | |
452 | return vid; | |
453 | } | |
454 | ||
83c7162d XL |
455 | /// Returns the universe for the given variable. |
456 | pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex { | |
457 | self.var_infos[vid].universe | |
abe05a73 XL |
458 | } |
459 | ||
83c7162d XL |
460 | /// Returns the origin for the given variable. |
461 | pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin { | |
462 | self.var_infos[vid].origin | |
abe05a73 XL |
463 | } |
464 | ||
465 | /// Removes all the edges to/from the skolemized regions that are | |
466 | /// in `skols`. This is used after a higher-ranked operation | |
467 | /// completes to remove all trace of the skolemized regions | |
468 | /// created in that time. | |
469 | pub fn pop_skolemized( | |
470 | &mut self, | |
83c7162d | 471 | skolemization_count: ty::UniverseIndex, |
abe05a73 XL |
472 | skols: &FxHashSet<ty::Region<'tcx>>, |
473 | snapshot: &RegionSnapshot, | |
474 | ) { | |
475 | debug!("pop_skolemized_regions(skols={:?})", skols); | |
476 | ||
477 | assert!(self.in_snapshot()); | |
478 | assert!(self.undo_log[snapshot.length] == OpenSnapshot); | |
479 | assert!( | |
83c7162d | 480 | skolemization_count.as_usize() >= skols.len(), |
abe05a73 | 481 | "popping more skolemized variables than actually exist, \ |
83c7162d XL |
482 | sc now = {:?}, skols.len = {:?}", |
483 | skolemization_count, | |
abe05a73 XL |
484 | skols.len() |
485 | ); | |
486 | ||
83c7162d XL |
487 | let last_to_pop = skolemization_count.subuniverse(); |
488 | let first_to_pop = ty::UniverseIndex::from(last_to_pop.as_u32() - skols.len() as u32); | |
abe05a73 | 489 | |
abe05a73 XL |
490 | debug_assert! { |
491 | skols.iter() | |
492 | .all(|&k| match *k { | |
83c7162d XL |
493 | ty::ReSkolemized(universe, _) => |
494 | universe >= first_to_pop && | |
495 | universe < last_to_pop, | |
abe05a73 XL |
496 | _ => |
497 | false | |
498 | }), | |
83c7162d XL |
499 | "invalid skolemization keys or keys out of range ({:?}..{:?}): {:?}", |
500 | first_to_pop, | |
501 | last_to_pop, | |
abe05a73 XL |
502 | skols |
503 | } | |
504 | ||
505 | let constraints_to_kill: Vec<usize> = self.undo_log | |
506 | .iter() | |
507 | .enumerate() | |
508 | .rev() | |
509 | .filter(|&(_, undo_entry)| kill_constraint(skols, undo_entry)) | |
510 | .map(|(index, _)| index) | |
511 | .collect(); | |
512 | ||
513 | for index in constraints_to_kill { | |
514 | let undo_entry = mem::replace(&mut self.undo_log[index], Purged); | |
515 | self.rollback_undo_entry(undo_entry); | |
516 | } | |
517 | ||
abe05a73 XL |
518 | return; |
519 | ||
520 | fn kill_constraint<'tcx>( | |
521 | skols: &FxHashSet<ty::Region<'tcx>>, | |
522 | undo_entry: &UndoLogEntry<'tcx>, | |
523 | ) -> bool { | |
524 | match undo_entry { | |
525 | &AddConstraint(Constraint::VarSubVar(..)) => false, | |
526 | &AddConstraint(Constraint::RegSubVar(a, _)) => skols.contains(&a), | |
527 | &AddConstraint(Constraint::VarSubReg(_, b)) => skols.contains(&b), | |
528 | &AddConstraint(Constraint::RegSubReg(a, b)) => { | |
529 | skols.contains(&a) || skols.contains(&b) | |
530 | } | |
531 | &AddGiven(..) => false, | |
532 | &AddVerify(_) => false, | |
533 | &AddCombination(_, ref two_regions) => { | |
534 | skols.contains(&two_regions.a) || skols.contains(&two_regions.b) | |
535 | } | |
536 | &AddVar(..) | &OpenSnapshot | &Purged | &CommitedSnapshot => false, | |
537 | } | |
538 | } | |
539 | } | |
540 | ||
541 | pub fn new_bound( | |
542 | &mut self, | |
543 | tcx: TyCtxt<'_, '_, 'tcx>, | |
544 | debruijn: ty::DebruijnIndex, | |
545 | ) -> Region<'tcx> { | |
546 | // Creates a fresh bound variable for use in GLB computations. | |
547 | // See discussion of GLB computation in the large comment at | |
548 | // the top of this file for more details. | |
549 | // | |
550 | // This computation is potentially wrong in the face of | |
551 | // rollover. It's conceivable, if unlikely, that one might | |
552 | // wind up with accidental capture for nested functions in | |
553 | // that case, if the outer function had bound regions created | |
554 | // a very long time before and the inner function somehow | |
555 | // wound up rolling over such that supposedly fresh | |
556 | // identifiers were in fact shadowed. For now, we just assert | |
557 | // that there is no rollover -- eventually we should try to be | |
558 | // robust against this possibility, either by checking the set | |
559 | // of bound identifiers that appear in a given expression and | |
560 | // ensure that we generate one that is distinct, or by | |
561 | // changing the representation of bound regions in a fn | |
562 | // declaration | |
563 | ||
564 | let sc = self.bound_count; | |
565 | self.bound_count = sc + 1; | |
566 | ||
567 | if sc >= self.bound_count { | |
568 | bug!("rollover in RegionInference new_bound()"); | |
569 | } | |
570 | ||
571 | tcx.mk_region(ReLateBound(debruijn, BrFresh(sc))) | |
572 | } | |
573 | ||
574 | fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { | |
575 | // cannot add constraints once regions are resolved | |
576 | debug!( | |
577 | "RegionConstraintCollector: add_constraint({:?})", | |
578 | constraint | |
579 | ); | |
580 | ||
581 | // never overwrite an existing (constraint, origin) - only insert one if it isn't | |
582 | // present in the map yet. This prevents origins from outside the snapshot being | |
583 | // replaced with "less informative" origins e.g. during calls to `can_eq` | |
584 | let in_snapshot = self.in_snapshot(); | |
585 | let undo_log = &mut self.undo_log; | |
586 | self.data.constraints.entry(constraint).or_insert_with(|| { | |
587 | if in_snapshot { | |
588 | undo_log.push(AddConstraint(constraint)); | |
589 | } | |
590 | origin | |
591 | }); | |
592 | } | |
593 | ||
594 | fn add_verify(&mut self, verify: Verify<'tcx>) { | |
595 | // cannot add verifys once regions are resolved | |
596 | debug!("RegionConstraintCollector: add_verify({:?})", verify); | |
597 | ||
598 | // skip no-op cases known to be satisfied | |
599 | match verify.bound { | |
600 | VerifyBound::AllBounds(ref bs) if bs.len() == 0 => { | |
601 | return; | |
602 | } | |
603 | _ => {} | |
604 | } | |
605 | ||
606 | let index = self.data.verifys.len(); | |
607 | self.data.verifys.push(verify); | |
608 | if self.in_snapshot() { | |
609 | self.undo_log.push(AddVerify(index)); | |
610 | } | |
611 | } | |
612 | ||
613 | pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { | |
614 | // cannot add givens once regions are resolved | |
615 | if self.data.givens.insert((sub, sup)) { | |
616 | debug!("add_given({:?} <= {:?})", sub, sup); | |
617 | ||
618 | if self.in_snapshot() { | |
619 | self.undo_log.push(AddGiven(sub, sup)); | |
620 | } | |
621 | } | |
622 | } | |
623 | ||
624 | pub fn make_eqregion( | |
625 | &mut self, | |
626 | origin: SubregionOrigin<'tcx>, | |
627 | sub: Region<'tcx>, | |
628 | sup: Region<'tcx>, | |
629 | ) { | |
630 | if sub != sup { | |
631 | // Eventually, it would be nice to add direct support for | |
632 | // equating regions. | |
633 | self.make_subregion(origin.clone(), sub, sup); | |
634 | self.make_subregion(origin, sup, sub); | |
635 | ||
636 | if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) { | |
637 | self.unification_table.union(sub, sup); | |
94b46f34 | 638 | self.any_unifications = true; |
abe05a73 XL |
639 | } |
640 | } | |
641 | } | |
642 | ||
643 | pub fn make_subregion( | |
644 | &mut self, | |
645 | origin: SubregionOrigin<'tcx>, | |
646 | sub: Region<'tcx>, | |
647 | sup: Region<'tcx>, | |
648 | ) { | |
649 | // cannot add constraints once regions are resolved | |
650 | debug!( | |
651 | "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}", | |
652 | sub, | |
653 | sup, | |
654 | origin | |
655 | ); | |
656 | ||
657 | match (sub, sup) { | |
658 | (&ReLateBound(..), _) | (_, &ReLateBound(..)) => { | |
659 | span_bug!( | |
660 | origin.span(), | |
661 | "cannot relate bound region: {:?} <= {:?}", | |
662 | sub, | |
663 | sup | |
664 | ); | |
665 | } | |
666 | (_, &ReStatic) => { | |
667 | // all regions are subregions of static, so we can ignore this | |
668 | } | |
669 | (&ReVar(sub_id), &ReVar(sup_id)) => { | |
670 | self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin); | |
671 | } | |
672 | (_, &ReVar(sup_id)) => { | |
673 | self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin); | |
674 | } | |
675 | (&ReVar(sub_id), _) => { | |
676 | self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin); | |
677 | } | |
678 | _ => { | |
679 | self.add_constraint(Constraint::RegSubReg(sub, sup), origin); | |
680 | } | |
681 | } | |
682 | } | |
683 | ||
684 | /// See `Verify::VerifyGenericBound` | |
685 | pub fn verify_generic_bound( | |
686 | &mut self, | |
687 | origin: SubregionOrigin<'tcx>, | |
688 | kind: GenericKind<'tcx>, | |
689 | sub: Region<'tcx>, | |
690 | bound: VerifyBound<'tcx>, | |
691 | ) { | |
692 | self.add_verify(Verify { | |
693 | kind, | |
694 | origin, | |
695 | region: sub, | |
696 | bound, | |
697 | }); | |
698 | } | |
699 | ||
700 | pub fn lub_regions( | |
701 | &mut self, | |
702 | tcx: TyCtxt<'_, '_, 'tcx>, | |
703 | origin: SubregionOrigin<'tcx>, | |
704 | a: Region<'tcx>, | |
705 | b: Region<'tcx>, | |
706 | ) -> Region<'tcx> { | |
707 | // cannot add constraints once regions are resolved | |
708 | debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b); | |
709 | match (a, b) { | |
710 | (r @ &ReStatic, _) | (_, r @ &ReStatic) => { | |
711 | r // nothing lives longer than static | |
712 | } | |
713 | ||
714 | _ if a == b => { | |
715 | a // LUB(a,a) = a | |
716 | } | |
717 | ||
718 | _ => self.combine_vars(tcx, Lub, a, b, origin.clone()), | |
719 | } | |
720 | } | |
721 | ||
722 | pub fn glb_regions( | |
723 | &mut self, | |
724 | tcx: TyCtxt<'_, '_, 'tcx>, | |
725 | origin: SubregionOrigin<'tcx>, | |
726 | a: Region<'tcx>, | |
727 | b: Region<'tcx>, | |
728 | ) -> Region<'tcx> { | |
729 | // cannot add constraints once regions are resolved | |
730 | debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b); | |
731 | match (a, b) { | |
732 | (&ReStatic, r) | (r, &ReStatic) => { | |
733 | r // static lives longer than everything else | |
734 | } | |
735 | ||
736 | _ if a == b => { | |
737 | a // GLB(a,a) = a | |
738 | } | |
739 | ||
740 | _ => self.combine_vars(tcx, Glb, a, b, origin.clone()), | |
741 | } | |
742 | } | |
743 | ||
744 | pub fn opportunistic_resolve_var( | |
745 | &mut self, | |
746 | tcx: TyCtxt<'_, '_, 'tcx>, | |
747 | rid: RegionVid, | |
748 | ) -> ty::Region<'tcx> { | |
0531ce1d | 749 | let vid = self.unification_table.probe_value(rid).min_vid; |
abe05a73 XL |
750 | tcx.mk_region(ty::ReVar(vid)) |
751 | } | |
752 | ||
753 | fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { | |
754 | match t { | |
755 | Glb => &mut self.glbs, | |
756 | Lub => &mut self.lubs, | |
757 | } | |
758 | } | |
759 | ||
760 | fn combine_vars( | |
761 | &mut self, | |
762 | tcx: TyCtxt<'_, '_, 'tcx>, | |
763 | t: CombineMapType, | |
764 | a: Region<'tcx>, | |
765 | b: Region<'tcx>, | |
766 | origin: SubregionOrigin<'tcx>, | |
767 | ) -> Region<'tcx> { | |
768 | let vars = TwoRegions { a: a, b: b }; | |
769 | if let Some(&c) = self.combine_map(t).get(&vars) { | |
770 | return tcx.mk_region(ReVar(c)); | |
771 | } | |
83c7162d XL |
772 | let a_universe = self.universe(a); |
773 | let b_universe = self.universe(b); | |
774 | let c_universe = cmp::max(a_universe, b_universe); | |
775 | let c = self.new_region_var(c_universe, MiscVariable(origin.span())); | |
abe05a73 XL |
776 | self.combine_map(t).insert(vars, c); |
777 | if self.in_snapshot() { | |
778 | self.undo_log.push(AddCombination(t, vars)); | |
779 | } | |
780 | let new_r = tcx.mk_region(ReVar(c)); | |
781 | for &old_r in &[a, b] { | |
782 | match t { | |
783 | Glb => self.make_subregion(origin.clone(), new_r, old_r), | |
784 | Lub => self.make_subregion(origin.clone(), old_r, new_r), | |
785 | } | |
786 | } | |
787 | debug!("combine_vars() c={:?}", c); | |
788 | new_r | |
789 | } | |
790 | ||
83c7162d XL |
791 | fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex { |
792 | match *region { | |
793 | ty::ReScope(..) | | |
794 | ty::ReStatic | | |
795 | ty::ReEmpty | | |
796 | ty::ReErased | | |
797 | ty::ReFree(..) | | |
798 | ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT, | |
799 | ty::ReSkolemized(universe, _) => universe, | |
800 | ty::ReClosureBound(vid) | | |
801 | ty::ReVar(vid) => self.var_universe(vid), | |
802 | ty::ReLateBound(..) => | |
803 | bug!("universe(): encountered bound region {:?}", region), | |
804 | ty::ReCanonical(..) => | |
805 | bug!("region_universe(): encountered canonical region {:?}", region), | |
806 | } | |
807 | } | |
808 | ||
abe05a73 XL |
809 | pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot) -> Vec<RegionVid> { |
810 | self.undo_log[mark.length..] | |
811 | .iter() | |
812 | .filter_map(|&elt| match elt { | |
813 | AddVar(vid) => Some(vid), | |
814 | _ => None, | |
815 | }) | |
816 | .collect() | |
817 | } | |
818 | ||
819 | /// Computes all regions that have been related to `r0` since the | |
820 | /// mark `mark` was made---`r0` itself will be the first | |
821 | /// entry. The `directions` parameter controls what kind of | |
822 | /// relations are considered. For example, one can say that only | |
823 | /// "incoming" edges to `r0` are desired, in which case one will | |
824 | /// get the set of regions `{r|r <= r0}`. This is used when | |
825 | /// checking whether skolemized regions are being improperly | |
826 | /// related to other regions. | |
827 | pub fn tainted( | |
828 | &self, | |
829 | tcx: TyCtxt<'_, '_, 'tcx>, | |
830 | mark: &RegionSnapshot, | |
831 | r0: Region<'tcx>, | |
832 | directions: TaintDirections, | |
833 | ) -> FxHashSet<ty::Region<'tcx>> { | |
834 | debug!( | |
835 | "tainted(mark={:?}, r0={:?}, directions={:?})", | |
836 | mark, | |
837 | r0, | |
838 | directions | |
839 | ); | |
840 | ||
841 | // `result_set` acts as a worklist: we explore all outgoing | |
842 | // edges and add any new regions we find to result_set. This | |
843 | // is not a terribly efficient implementation. | |
844 | let mut taint_set = taint::TaintSet::new(directions, r0); | |
845 | taint_set.fixed_point(tcx, &self.undo_log[mark.length..], &self.data.verifys); | |
846 | debug!("tainted: result={:?}", taint_set); | |
847 | return taint_set.into_set(); | |
848 | } | |
849 | } | |
850 | ||
851 | impl fmt::Debug for RegionSnapshot { | |
852 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
83c7162d | 853 | write!(f, "RegionSnapshot(length={})", self.length) |
abe05a73 XL |
854 | } |
855 | } | |
856 | ||
857 | impl<'tcx> fmt::Debug for GenericKind<'tcx> { | |
858 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
859 | match *self { | |
860 | GenericKind::Param(ref p) => write!(f, "{:?}", p), | |
861 | GenericKind::Projection(ref p) => write!(f, "{:?}", p), | |
862 | } | |
863 | } | |
864 | } | |
865 | ||
866 | impl<'tcx> fmt::Display for GenericKind<'tcx> { | |
867 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
868 | match *self { | |
869 | GenericKind::Param(ref p) => write!(f, "{}", p), | |
870 | GenericKind::Projection(ref p) => write!(f, "{}", p), | |
871 | } | |
872 | } | |
873 | } | |
874 | ||
875 | impl<'a, 'gcx, 'tcx> GenericKind<'tcx> { | |
876 | pub fn to_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> { | |
877 | match *self { | |
878 | GenericKind::Param(ref p) => p.to_ty(tcx), | |
879 | GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs), | |
880 | } | |
881 | } | |
882 | } | |
883 | ||
884 | impl<'a, 'gcx, 'tcx> VerifyBound<'tcx> { | |
0531ce1d | 885 | fn for_each_region(&self, f: &mut dyn FnMut(ty::Region<'tcx>)) { |
abe05a73 XL |
886 | match self { |
887 | &VerifyBound::AnyRegion(ref rs) | &VerifyBound::AllRegions(ref rs) => for &r in rs { | |
888 | f(r); | |
889 | }, | |
890 | ||
891 | &VerifyBound::AnyBound(ref bs) | &VerifyBound::AllBounds(ref bs) => for b in bs { | |
892 | b.for_each_region(f); | |
893 | }, | |
894 | } | |
895 | } | |
896 | ||
897 | pub fn must_hold(&self) -> bool { | |
898 | match self { | |
899 | &VerifyBound::AnyRegion(ref bs) => bs.contains(&&ty::ReStatic), | |
900 | &VerifyBound::AllRegions(ref bs) => bs.is_empty(), | |
901 | &VerifyBound::AnyBound(ref bs) => bs.iter().any(|b| b.must_hold()), | |
902 | &VerifyBound::AllBounds(ref bs) => bs.iter().all(|b| b.must_hold()), | |
903 | } | |
904 | } | |
905 | ||
906 | pub fn cannot_hold(&self) -> bool { | |
907 | match self { | |
908 | &VerifyBound::AnyRegion(ref bs) => bs.is_empty(), | |
909 | &VerifyBound::AllRegions(ref bs) => bs.contains(&&ty::ReEmpty), | |
910 | &VerifyBound::AnyBound(ref bs) => bs.iter().all(|b| b.cannot_hold()), | |
911 | &VerifyBound::AllBounds(ref bs) => bs.iter().any(|b| b.cannot_hold()), | |
912 | } | |
913 | } | |
914 | ||
915 | pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
916 | if self.must_hold() || vb.cannot_hold() { | |
917 | self | |
918 | } else if self.cannot_hold() || vb.must_hold() { | |
919 | vb | |
920 | } else { | |
921 | VerifyBound::AnyBound(vec![self, vb]) | |
922 | } | |
923 | } | |
924 | ||
925 | pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> { | |
926 | if self.must_hold() && vb.must_hold() { | |
927 | self | |
928 | } else if self.cannot_hold() && vb.cannot_hold() { | |
929 | self | |
930 | } else { | |
931 | VerifyBound::AllBounds(vec![self, vb]) | |
932 | } | |
933 | } | |
934 | } | |
935 | ||
936 | impl<'tcx> RegionConstraintData<'tcx> { | |
937 | /// True if this region constraint data contains no constraints. | |
938 | pub fn is_empty(&self) -> bool { | |
939 | let RegionConstraintData { | |
940 | constraints, | |
941 | verifys, | |
942 | givens, | |
943 | } = self; | |
944 | constraints.is_empty() && verifys.is_empty() && givens.is_empty() | |
945 | } | |
946 | } |