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.
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.
13 use self::UndoLogEntry::*;
14 use self::CombineMapType::*;
16 use super::{MiscVariable, RegionVariableOrigin, SubregionOrigin};
19 use rustc_data_structures::indexed_vec::IndexVec;
20 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
21 use rustc_data_structures::unify as ut;
22 use ty::{self, Ty, TyCtxt};
23 use ty::{Region, RegionVid};
25 use ty::{BrFresh, ReLateBound, ReVar};
27 use std::collections::BTreeMap;
28 use std::{cmp, fmt, mem, u32};
32 pub struct RegionConstraintCollector<'tcx> {
33 /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
34 var_infos: IndexVec<RegionVid, RegionVariableInfo>,
36 data: RegionConstraintData<'tcx>,
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>,
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>,
48 /// Global counter used during the GLB algorithm to create unique
49 /// names for fresh bound regions
52 /// The undo log records actions that might later be undone.
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
61 undo_log: Vec<UndoLogEntry<'tcx>>,
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.
71 unification_table: ut::UnificationTable<ut::InPlace<ty::RegionVid>>,
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,
78 pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>;
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.
84 #[derive(Debug, Default, Clone)]
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>>,
90 /// A "verify" is something that we need to verify after inference
91 /// is done, but which does not directly affect inference in any
94 /// An example is a `A <= B` where neither `A` nor `B` are
95 /// inference variables.
96 pub verifys: Vec<Verify<'tcx>>,
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
103 /// foo.iter().filter(<'a> |x: &'a &'b T| ...)
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.
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)>,
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),
125 /// Concrete region is subregion of region variable
126 RegSubVar(Region<'tcx>, RegionVid),
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>),
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>),
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).
144 #[derive(Debug, Clone)]
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>,
152 #[derive(Copy, Clone, PartialEq, Eq)]
153 pub enum GenericKind<'tcx> {
155 Projection(ty::ProjectionTy<'tcx>),
158 EnumTypeFoldableImpl! {
159 impl<'tcx> TypeFoldable<'tcx> for GenericKind<'tcx> {
160 (GenericKind::Param)(a),
161 (GenericKind::Projection)(a),
165 /// Describes the things that some `GenericKind` value G is known to
166 /// outlive. Each variant of `VerifyBound` can be thought of as a
169 /// fn(min: Region) -> bool { .. }
171 /// where `true` means that the region `min` meets that `G: min`.
172 /// (False means nothing.)
174 /// So, for example, if we have the type `T` and we have in scope that
175 /// `T: 'a` and `T: 'b`, then the verify bound might be:
177 /// fn(min: Region) -> bool {
178 /// ('a: min) || ('b: min)
181 /// This is described with a `AnyRegion('a, 'b)` node.
182 #[derive(Debug, Clone)]
183 pub enum VerifyBound<'tcx> {
184 /// Given a kind K and a bound B, expands to a function like the
185 /// following, where `G` is the generic for which this verify
186 /// bound was created:
188 /// fn(min) -> bool {
196 /// In other words, if the generic `G` that we are checking is
197 /// equal to `K`, then check the associated verify bound
198 /// (otherwise, false).
200 /// This is used when we have something in the environment that
201 /// may or may not be relevant, depending on the region inference
202 /// results. For example, we may have `where <T as
203 /// Trait<'a>>::Item: 'b` in our where clauses. If we are
204 /// generating the verify-bound for `<T as Trait<'0>>::Item`, then
205 /// this where-clause is only relevant if `'0` winds up inferred
208 /// So we would compile to a verify-bound like
210 /// IfEq(<T as Trait<'a>>::Item, AnyRegion('a))
212 /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item`
213 /// (after inference), and `'a: min`, then `G: min`.
214 IfEq(Ty<'tcx>, Box<VerifyBound<'tcx>>),
216 /// Given a region `R`, expands to the function:
218 /// fn(min) -> bool {
222 /// This is used when we can establish that `G: R` -- therefore,
223 /// if `R: min`, then by transitivity `G: min`.
224 OutlivedBy(Region<'tcx>),
226 /// Given a set of bounds `B`, expands to the function:
228 /// fn(min) -> bool {
229 /// exists (b in B) { b(min) }
232 /// In other words, if we meet some bound in `B`, that suffices.
233 /// This is used when all the bounds in `B` are known to apply to
235 AnyBound(Vec<VerifyBound<'tcx>>),
237 /// Given a set of bounds `B`, expands to the function:
239 /// fn(min) -> bool {
240 /// forall (b in B) { b(min) }
243 /// In other words, if we meet *all* bounds in `B`, that suffices.
244 /// This is used when *some* bound in `B` is known to suffice, but
245 /// we don't know which.
246 AllBounds(Vec<VerifyBound<'tcx>>),
249 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
250 struct TwoRegions<'tcx> {
255 #[derive(Copy, Clone, PartialEq)]
256 enum UndoLogEntry<'tcx> {
257 /// Pushed when we start a snapshot.
260 /// Replaces an `OpenSnapshot` when a snapshot is committed, but
261 /// that snapshot is not the root. If the root snapshot is
262 /// unrolled, all nested snapshots must be committed.
265 /// We added `RegionVid`
268 /// We added the given `constraint`
269 AddConstraint(Constraint<'tcx>),
271 /// We added the given `verify`
274 /// We added the given `given`
275 AddGiven(Region<'tcx>, ty::RegionVid),
277 /// We added a GLB/LUB "combination variable"
278 AddCombination(CombineMapType, TwoRegions<'tcx>),
280 /// During skolemization, we sometimes purge entries from the undo
281 /// log in a kind of minisnapshot (unlike other snapshots, this
282 /// purging actually takes place *on success*). In that case, we
283 /// replace the corresponding entry with `Noop` so as to avoid the
284 /// need to do a bunch of swapping. (We can't use `swap_remove` as
285 /// the order of the vector is important.)
289 #[derive(Copy, Clone, PartialEq)]
290 enum CombineMapType {
295 type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
297 #[derive(Debug, Clone, Copy)]
298 pub struct RegionVariableInfo {
299 pub origin: RegionVariableOrigin,
300 pub universe: ty::UniverseIndex,
303 pub struct RegionSnapshot {
305 region_snapshot: ut::Snapshot<ut::InPlace<ty::RegionVid>>,
306 any_unifications: bool,
309 /// When working with skolemized regions, we often wish to find all of
310 /// the regions that are either reachable from a skolemized region, or
311 /// which can reach a skolemized region, or both. We call such regions
312 /// *tained* regions. This struct allows you to decide what set of
313 /// tainted regions you want.
315 pub struct TaintDirections {
320 impl TaintDirections {
321 pub fn incoming() -> Self {
328 pub fn outgoing() -> Self {
335 pub fn both() -> Self {
343 impl<'tcx> RegionConstraintCollector<'tcx> {
344 pub fn new() -> RegionConstraintCollector<'tcx> {
345 RegionConstraintCollector {
346 var_infos: VarInfos::default(),
347 data: RegionConstraintData::default(),
351 undo_log: Vec::new(),
352 unification_table: ut::UnificationTable::new(),
353 any_unifications: false,
357 pub fn num_region_vars(&self) -> usize {
361 pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> {
365 /// Once all the constraints have been gathered, extract out the final data.
367 /// Not legal during a snapshot.
368 pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) {
369 assert!(!self.in_snapshot());
370 (self.var_infos, self.data)
373 /// Takes (and clears) the current set of constraints. Note that
374 /// the set of variables remains intact, but all relationships
375 /// between them are reset. This is used during NLL checking to
376 /// grab the set of constraints that arose from a particular
379 /// We don't want to leak relationships between variables between
380 /// points because just because (say) `r1 == r2` was true at some
381 /// point P in the graph doesn't imply that it will be true at
382 /// some other point Q, in NLL.
384 /// Not legal during a snapshot.
385 pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> {
386 assert!(!self.in_snapshot());
388 // If you add a new field to `RegionConstraintCollector`, you
389 // should think carefully about whether it needs to be cleared
390 // or updated in some way.
391 let RegionConstraintCollector {
402 // Clear the tables of (lubs, glbs), so that we will create
403 // fresh regions if we do a LUB operation. As it happens,
404 // LUB/GLB are not performed by the MIR type-checker, which is
405 // the one that uses this method, but it's good to be correct.
409 // Clear all unifications and recreate the variables a "now
410 // un-unified" state. Note that when we unify `a` and `b`, we
411 // also insert `a <= b` and a `b <= a` edges, so the
412 // `RegionConstraintData` contains the relationship here.
413 if *any_unifications {
414 unification_table.reset_unifications(|vid| unify_key::RegionVidKey { min_vid: vid });
415 *any_unifications = false;
418 mem::replace(data, RegionConstraintData::default())
421 pub fn data(&self) -> &RegionConstraintData<'tcx> {
425 fn in_snapshot(&self) -> bool {
426 !self.undo_log.is_empty()
429 pub fn start_snapshot(&mut self) -> RegionSnapshot {
430 let length = self.undo_log.len();
431 debug!("RegionConstraintCollector: start_snapshot({})", length);
432 self.undo_log.push(OpenSnapshot);
435 region_snapshot: self.unification_table.snapshot(),
436 any_unifications: self.any_unifications,
440 pub fn commit(&mut self, snapshot: RegionSnapshot) {
441 debug!("RegionConstraintCollector: commit({})", snapshot.length);
442 assert!(self.undo_log.len() > snapshot.length);
443 assert!(self.undo_log[snapshot.length] == OpenSnapshot);
445 if snapshot.length == 0 {
446 self.undo_log.truncate(0);
448 (*self.undo_log)[snapshot.length] = CommitedSnapshot;
450 self.unification_table.commit(snapshot.region_snapshot);
453 pub fn rollback_to(&mut self, snapshot: RegionSnapshot) {
454 debug!("RegionConstraintCollector: rollback_to({:?})", snapshot);
455 assert!(self.undo_log.len() > snapshot.length);
456 assert!(self.undo_log[snapshot.length] == OpenSnapshot);
457 while self.undo_log.len() > snapshot.length + 1 {
458 let undo_entry = self.undo_log.pop().unwrap();
459 self.rollback_undo_entry(undo_entry);
461 let c = self.undo_log.pop().unwrap();
462 assert!(c == OpenSnapshot);
463 self.unification_table.rollback_to(snapshot.region_snapshot);
464 self.any_unifications = snapshot.any_unifications;
467 fn rollback_undo_entry(&mut self, undo_entry: UndoLogEntry<'tcx>) {
470 panic!("Failure to observe stack discipline");
472 Purged | CommitedSnapshot => {
473 // nothing to do here
476 self.var_infos.pop().unwrap();
477 assert_eq!(self.var_infos.len(), vid.index() as usize);
479 AddConstraint(ref constraint) => {
480 self.data.constraints.remove(constraint);
482 AddVerify(index) => {
483 self.data.verifys.pop();
484 assert_eq!(self.data.verifys.len(), index);
486 AddGiven(sub, sup) => {
487 self.data.givens.remove(&(sub, sup));
489 AddCombination(Glb, ref regions) => {
490 self.glbs.remove(regions);
492 AddCombination(Lub, ref regions) => {
493 self.lubs.remove(regions);
498 pub fn new_region_var(&mut self,
499 universe: ty::UniverseIndex,
500 origin: RegionVariableOrigin) -> RegionVid {
501 let vid = self.var_infos.push(RegionVariableInfo {
506 let u_vid = self.unification_table
507 .new_key(unify_key::RegionVidKey { min_vid: vid });
508 assert_eq!(vid, u_vid);
509 if self.in_snapshot() {
510 self.undo_log.push(AddVar(vid));
513 "created new region variable {:?} with origin {:?}",
520 /// Returns the universe for the given variable.
521 pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex {
522 self.var_infos[vid].universe
525 /// Returns the origin for the given variable.
526 pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
527 self.var_infos[vid].origin
530 /// Removes all the edges to/from the skolemized regions that are
531 /// in `skols`. This is used after a higher-ranked operation
532 /// completes to remove all trace of the skolemized regions
533 /// created in that time.
534 pub fn pop_skolemized(
536 skolemization_count: ty::UniverseIndex,
537 skols: &FxHashSet<ty::Region<'tcx>>,
538 snapshot: &RegionSnapshot,
540 debug!("pop_skolemized_regions(skols={:?})", skols);
542 assert!(self.in_snapshot());
543 assert!(self.undo_log[snapshot.length] == OpenSnapshot);
545 skolemization_count.as_usize() >= skols.len(),
546 "popping more skolemized variables than actually exist, \
547 sc now = {:?}, skols.len = {:?}",
552 let last_to_pop = skolemization_count.subuniverse();
553 let first_to_pop = ty::UniverseIndex::from(last_to_pop.as_u32() - skols.len() as u32);
558 ty::ReSkolemized(universe, _) =>
559 universe >= first_to_pop &&
560 universe < last_to_pop,
564 "invalid skolemization keys or keys out of range ({:?}..{:?}): {:?}",
570 let constraints_to_kill: Vec<usize> = self.undo_log
574 .filter(|&(_, undo_entry)| kill_constraint(skols, undo_entry))
575 .map(|(index, _)| index)
578 for index in constraints_to_kill {
579 let undo_entry = mem::replace(&mut self.undo_log[index], Purged);
580 self.rollback_undo_entry(undo_entry);
585 fn kill_constraint<'tcx>(
586 skols: &FxHashSet<ty::Region<'tcx>>,
587 undo_entry: &UndoLogEntry<'tcx>,
590 &AddConstraint(Constraint::VarSubVar(..)) => false,
591 &AddConstraint(Constraint::RegSubVar(a, _)) => skols.contains(&a),
592 &AddConstraint(Constraint::VarSubReg(_, b)) => skols.contains(&b),
593 &AddConstraint(Constraint::RegSubReg(a, b)) => {
594 skols.contains(&a) || skols.contains(&b)
596 &AddGiven(..) => false,
597 &AddVerify(_) => false,
598 &AddCombination(_, ref two_regions) => {
599 skols.contains(&two_regions.a) || skols.contains(&two_regions.b)
601 &AddVar(..) | &OpenSnapshot | &Purged | &CommitedSnapshot => false,
608 tcx: TyCtxt<'_, '_, 'tcx>,
609 debruijn: ty::DebruijnIndex,
611 // Creates a fresh bound variable for use in GLB computations.
612 // See discussion of GLB computation in the large comment at
613 // the top of this file for more details.
615 // This computation is potentially wrong in the face of
616 // rollover. It's conceivable, if unlikely, that one might
617 // wind up with accidental capture for nested functions in
618 // that case, if the outer function had bound regions created
619 // a very long time before and the inner function somehow
620 // wound up rolling over such that supposedly fresh
621 // identifiers were in fact shadowed. For now, we just assert
622 // that there is no rollover -- eventually we should try to be
623 // robust against this possibility, either by checking the set
624 // of bound identifiers that appear in a given expression and
625 // ensure that we generate one that is distinct, or by
626 // changing the representation of bound regions in a fn
629 let sc = self.bound_count;
630 self.bound_count = sc + 1;
632 if sc >= self.bound_count {
633 bug!("rollover in RegionInference new_bound()");
636 tcx.mk_region(ReLateBound(debruijn, BrFresh(sc)))
639 fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) {
640 // cannot add constraints once regions are resolved
642 "RegionConstraintCollector: add_constraint({:?})",
646 // never overwrite an existing (constraint, origin) - only insert one if it isn't
647 // present in the map yet. This prevents origins from outside the snapshot being
648 // replaced with "less informative" origins e.g. during calls to `can_eq`
649 let in_snapshot = self.in_snapshot();
650 let undo_log = &mut self.undo_log;
651 self.data.constraints.entry(constraint).or_insert_with(|| {
653 undo_log.push(AddConstraint(constraint));
659 fn add_verify(&mut self, verify: Verify<'tcx>) {
660 // cannot add verifys once regions are resolved
661 debug!("RegionConstraintCollector: add_verify({:?})", verify);
663 // skip no-op cases known to be satisfied
665 VerifyBound::AllBounds(ref bs) if bs.len() == 0 => {
671 let index = self.data.verifys.len();
672 self.data.verifys.push(verify);
673 if self.in_snapshot() {
674 self.undo_log.push(AddVerify(index));
678 pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) {
679 // cannot add givens once regions are resolved
680 if self.data.givens.insert((sub, sup)) {
681 debug!("add_given({:?} <= {:?})", sub, sup);
683 if self.in_snapshot() {
684 self.undo_log.push(AddGiven(sub, sup));
689 pub fn make_eqregion(
691 origin: SubregionOrigin<'tcx>,
696 // Eventually, it would be nice to add direct support for
698 self.make_subregion(origin.clone(), sub, sup);
699 self.make_subregion(origin, sup, sub);
701 if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) {
702 self.unification_table.union(sub, sup);
703 self.any_unifications = true;
708 pub fn make_subregion(
710 origin: SubregionOrigin<'tcx>,
714 // cannot add constraints once regions are resolved
716 "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}",
723 (&ReLateBound(..), _) | (_, &ReLateBound(..)) => {
726 "cannot relate bound region: {:?} <= {:?}",
732 // all regions are subregions of static, so we can ignore this
734 (&ReVar(sub_id), &ReVar(sup_id)) => {
735 self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin);
737 (_, &ReVar(sup_id)) => {
738 self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin);
740 (&ReVar(sub_id), _) => {
741 self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin);
744 self.add_constraint(Constraint::RegSubReg(sub, sup), origin);
749 /// See `Verify::VerifyGenericBound`
750 pub fn verify_generic_bound(
752 origin: SubregionOrigin<'tcx>,
753 kind: GenericKind<'tcx>,
755 bound: VerifyBound<'tcx>,
757 self.add_verify(Verify {
767 tcx: TyCtxt<'_, '_, 'tcx>,
768 origin: SubregionOrigin<'tcx>,
772 // cannot add constraints once regions are resolved
773 debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b);
775 (r @ &ReStatic, _) | (_, r @ &ReStatic) => {
776 r // nothing lives longer than static
783 _ => self.combine_vars(tcx, Lub, a, b, origin.clone()),
789 tcx: TyCtxt<'_, '_, 'tcx>,
790 origin: SubregionOrigin<'tcx>,
794 // cannot add constraints once regions are resolved
795 debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b);
797 (&ReStatic, r) | (r, &ReStatic) => {
798 r // static lives longer than everything else
805 _ => self.combine_vars(tcx, Glb, a, b, origin.clone()),
809 pub fn opportunistic_resolve_var(
811 tcx: TyCtxt<'_, '_, 'tcx>,
813 ) -> ty::Region<'tcx> {
814 let vid = self.unification_table.probe_value(rid).min_vid;
815 tcx.mk_region(ty::ReVar(vid))
818 fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
820 Glb => &mut self.glbs,
821 Lub => &mut self.lubs,
827 tcx: TyCtxt<'_, '_, 'tcx>,
831 origin: SubregionOrigin<'tcx>,
833 let vars = TwoRegions { a: a, b: b };
834 if let Some(&c) = self.combine_map(t).get(&vars) {
835 return tcx.mk_region(ReVar(c));
837 let a_universe = self.universe(a);
838 let b_universe = self.universe(b);
839 let c_universe = cmp::max(a_universe, b_universe);
840 let c = self.new_region_var(c_universe, MiscVariable(origin.span()));
841 self.combine_map(t).insert(vars, c);
842 if self.in_snapshot() {
843 self.undo_log.push(AddCombination(t, vars));
845 let new_r = tcx.mk_region(ReVar(c));
846 for &old_r in &[a, b] {
848 Glb => self.make_subregion(origin.clone(), new_r, old_r),
849 Lub => self.make_subregion(origin.clone(), old_r, new_r),
852 debug!("combine_vars() c={:?}", c);
856 fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
863 ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT,
864 ty::ReSkolemized(universe, _) => universe,
865 ty::ReClosureBound(vid) |
866 ty::ReVar(vid) => self.var_universe(vid),
867 ty::ReLateBound(..) =>
868 bug!("universe(): encountered bound region {:?}", region),
869 ty::ReCanonical(..) =>
870 bug!("region_universe(): encountered canonical region {:?}", region),
874 pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot) -> Vec<RegionVid> {
875 self.undo_log[mark.length..]
877 .filter_map(|&elt| match elt {
878 AddVar(vid) => Some(vid),
884 /// Computes all regions that have been related to `r0` since the
885 /// mark `mark` was made---`r0` itself will be the first
886 /// entry. The `directions` parameter controls what kind of
887 /// relations are considered. For example, one can say that only
888 /// "incoming" edges to `r0` are desired, in which case one will
889 /// get the set of regions `{r|r <= r0}`. This is used when
890 /// checking whether skolemized regions are being improperly
891 /// related to other regions.
894 tcx: TyCtxt<'_, '_, 'tcx>,
895 mark: &RegionSnapshot,
897 directions: TaintDirections,
898 ) -> FxHashSet<ty::Region<'tcx>> {
900 "tainted(mark={:?}, r0={:?}, directions={:?})",
906 // `result_set` acts as a worklist: we explore all outgoing
907 // edges and add any new regions we find to result_set. This
908 // is not a terribly efficient implementation.
909 let mut taint_set = taint::TaintSet::new(directions, r0);
910 taint_set.fixed_point(tcx, &self.undo_log[mark.length..], &self.data.verifys);
911 debug!("tainted: result={:?}", taint_set);
912 return taint_set.into_set();
916 impl fmt::Debug for RegionSnapshot {
917 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
918 write!(f, "RegionSnapshot(length={})", self.length)
922 impl<'tcx> fmt::Debug for GenericKind<'tcx> {
923 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
925 GenericKind::Param(ref p) => write!(f, "{:?}", p),
926 GenericKind::Projection(ref p) => write!(f, "{:?}", p),
931 impl<'tcx> fmt::Display for GenericKind<'tcx> {
932 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
934 GenericKind::Param(ref p) => write!(f, "{}", p),
935 GenericKind::Projection(ref p) => write!(f, "{}", p),
940 impl<'a, 'gcx, 'tcx> GenericKind<'tcx> {
941 pub fn to_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> {
943 GenericKind::Param(ref p) => p.to_ty(tcx),
944 GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs),
949 impl<'a, 'gcx, 'tcx> VerifyBound<'tcx> {
950 pub fn must_hold(&self) -> bool {
952 VerifyBound::IfEq(..) => false,
953 VerifyBound::OutlivedBy(ty::ReStatic) => true,
954 VerifyBound::OutlivedBy(_) => false,
955 VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()),
956 VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()),
960 pub fn cannot_hold(&self) -> bool {
962 VerifyBound::IfEq(_, b) => b.cannot_hold(),
963 VerifyBound::OutlivedBy(ty::ReEmpty) => true,
964 VerifyBound::OutlivedBy(_) => false,
965 VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()),
966 VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()),
970 pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
971 if self.must_hold() || vb.cannot_hold() {
973 } else if self.cannot_hold() || vb.must_hold() {
976 VerifyBound::AnyBound(vec![self, vb])
980 pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
981 if self.must_hold() && vb.must_hold() {
983 } else if self.cannot_hold() && vb.cannot_hold() {
986 VerifyBound::AllBounds(vec![self, vb])
991 impl<'tcx> RegionConstraintData<'tcx> {
992 /// True if this region constraint data contains no constraints.
993 pub fn is_empty(&self) -> bool {
994 let RegionConstraintData {
999 constraints.is_empty() && verifys.is_empty() && givens.is_empty()