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::CombineMapType
::*;
17 use super::{MiscVariable, RegionVariableOrigin, SubregionOrigin}
;
19 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
20 use rustc_data_structures
::indexed_vec
::IndexVec
;
21 use rustc_data_structures
::unify
as ut
;
23 use ty
::{self, Ty, TyCtxt}
;
24 use ty
::{BrFresh, ReLateBound, ReVar}
;
25 use ty
::{Region, RegionVid}
;
27 use std
::collections
::BTreeMap
;
28 use std
::{cmp, fmt, mem, u32}
;
33 pub struct RegionConstraintCollector
<'tcx
> {
34 /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
35 var_infos
: IndexVec
<RegionVid
, RegionVariableInfo
>,
37 data
: RegionConstraintData
<'tcx
>,
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
>,
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
>,
49 /// Global counter used during the GLB algorithm to create unique
50 /// names for fresh bound regions
53 /// The undo log records actions that might later be undone.
55 /// Note: `num_open_snapshots` is used to track if we are actively
56 /// snapshotting. When the `start_snapshot()` method is called, we
57 /// increment `num_open_snapshots` to indicate that we are now actively
58 /// snapshotting. The reason for this is that otherwise we end up adding
59 /// entries for things like the lower bound on a variable and so forth,
60 /// which can never be rolled back.
61 undo_log
: Vec
<UndoLog
<'tcx
>>,
63 /// The number of open snapshots, i.e. those that haven't been committed or
65 num_open_snapshots
: usize,
67 /// When we add a R1 == R2 constriant, we currently add (a) edges
68 /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this
69 /// table. You can then call `opportunistic_resolve_var` early
70 /// which will map R1 and R2 to some common region (i.e., either
71 /// R1 or R2). This is important when dropck and other such code
72 /// is iterating to a fixed point, because otherwise we sometimes
73 /// would wind up with a fresh stream of region variables that
74 /// have been equated but appear distinct.
75 unification_table
: ut
::UnificationTable
<ut
::InPlace
<ty
::RegionVid
>>,
77 /// a flag set to true when we perform any unifications; this is used
78 /// to micro-optimize `take_and_reset_data`
79 any_unifications
: bool
,
82 pub type VarInfos
= IndexVec
<RegionVid
, RegionVariableInfo
>;
84 /// The full set of region constraints gathered up by the collector.
85 /// Describes constraints between the region variables and other
86 /// regions, as well as other conditions that must be verified, or
87 /// assumptions that can be made.
88 #[derive(Debug, Default, Clone)]
89 pub struct RegionConstraintData
<'tcx
> {
90 /// Constraints of the form `A <= B`, where either `A` or `B` can
91 /// be a region variable (or neither, as it happens).
92 pub constraints
: BTreeMap
<Constraint
<'tcx
>, SubregionOrigin
<'tcx
>>,
94 /// A "verify" is something that we need to verify after inference
95 /// is done, but which does not directly affect inference in any
98 /// An example is a `A <= B` where neither `A` nor `B` are
99 /// inference variables.
100 pub verifys
: Vec
<Verify
<'tcx
>>,
102 /// A "given" is a relationship that is known to hold. In
103 /// particular, we often know from closure fn signatures that a
104 /// particular free region must be a subregion of a region
107 /// foo.iter().filter(<'a> |x: &'a &'b T| ...)
109 /// In situations like this, `'b` is in fact a region variable
110 /// introduced by the call to `iter()`, and `'a` is a bound region
111 /// on the closure (as indicated by the `<'a>` prefix). If we are
112 /// naive, we wind up inferring that `'b` must be `'static`,
113 /// because we require that it be greater than `'a` and we do not
114 /// know what `'a` is precisely.
116 /// This hashmap is used to avoid that naive scenario. Basically
117 /// we record the fact that `'a <= 'b` is implied by the fn
118 /// signature, and then ignore the constraint when solving
119 /// equations. This is a bit of a hack but seems to work.
120 pub givens
: FxHashSet
<(Region
<'tcx
>, ty
::RegionVid
)>,
123 /// A constraint that influences the inference process.
124 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
125 pub enum Constraint
<'tcx
> {
126 /// One region variable is subregion of another
127 VarSubVar(RegionVid
, RegionVid
),
129 /// Concrete region is subregion of region variable
130 RegSubVar(Region
<'tcx
>, RegionVid
),
132 /// Region variable is subregion of concrete region. This does not
133 /// directly affect inference, but instead is checked after
134 /// inference is complete.
135 VarSubReg(RegionVid
, Region
<'tcx
>),
137 /// A constraint where neither side is a variable. This does not
138 /// directly affect inference, but instead is checked after
139 /// inference is complete.
140 RegSubReg(Region
<'tcx
>, Region
<'tcx
>),
143 /// VerifyGenericBound(T, _, R, RS): The parameter type `T` (or
144 /// associated type) must outlive the region `R`. `T` is known to
145 /// outlive `RS`. Therefore verify that `R <= RS[i]` for some
146 /// `i`. Inference variables may be involved (but this verification
147 /// step doesn't influence inference).
148 #[derive(Debug, Clone)]
149 pub struct Verify
<'tcx
> {
150 pub kind
: GenericKind
<'tcx
>,
151 pub origin
: SubregionOrigin
<'tcx
>,
152 pub region
: Region
<'tcx
>,
153 pub bound
: VerifyBound
<'tcx
>,
156 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
157 pub enum GenericKind
<'tcx
> {
159 Projection(ty
::ProjectionTy
<'tcx
>),
162 EnumTypeFoldableImpl
! {
163 impl<'tcx
> TypeFoldable
<'tcx
> for GenericKind
<'tcx
> {
164 (GenericKind
::Param
)(a
),
165 (GenericKind
::Projection
)(a
),
169 /// Describes the things that some `GenericKind` value G is known to
170 /// outlive. Each variant of `VerifyBound` can be thought of as a
173 /// fn(min: Region) -> bool { .. }
175 /// where `true` means that the region `min` meets that `G: min`.
176 /// (False means nothing.)
178 /// So, for example, if we have the type `T` and we have in scope that
179 /// `T: 'a` and `T: 'b`, then the verify bound might be:
181 /// fn(min: Region) -> bool {
182 /// ('a: min) || ('b: min)
185 /// This is described with a `AnyRegion('a, 'b)` node.
186 #[derive(Debug, Clone)]
187 pub enum VerifyBound
<'tcx
> {
188 /// Given a kind K and a bound B, expands to a function like the
189 /// following, where `G` is the generic for which this verify
190 /// bound was created:
192 /// fn(min) -> bool {
200 /// In other words, if the generic `G` that we are checking is
201 /// equal to `K`, then check the associated verify bound
202 /// (otherwise, false).
204 /// This is used when we have something in the environment that
205 /// may or may not be relevant, depending on the region inference
206 /// results. For example, we may have `where <T as
207 /// Trait<'a>>::Item: 'b` in our where clauses. If we are
208 /// generating the verify-bound for `<T as Trait<'0>>::Item`, then
209 /// this where-clause is only relevant if `'0` winds up inferred
212 /// So we would compile to a verify-bound like
214 /// IfEq(<T as Trait<'a>>::Item, AnyRegion('a))
216 /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item`
217 /// (after inference), and `'a: min`, then `G: min`.
218 IfEq(Ty
<'tcx
>, Box
<VerifyBound
<'tcx
>>),
220 /// Given a region `R`, expands to the function:
222 /// fn(min) -> bool {
226 /// This is used when we can establish that `G: R` -- therefore,
227 /// if `R: min`, then by transitivity `G: min`.
228 OutlivedBy(Region
<'tcx
>),
230 /// Given a set of bounds `B`, expands to the function:
232 /// fn(min) -> bool {
233 /// exists (b in B) { b(min) }
236 /// In other words, if we meet some bound in `B`, that suffices.
237 /// This is used when all the bounds in `B` are known to apply to
239 AnyBound(Vec
<VerifyBound
<'tcx
>>),
241 /// Given a set of bounds `B`, expands to the function:
243 /// fn(min) -> bool {
244 /// forall (b in B) { b(min) }
247 /// In other words, if we meet *all* bounds in `B`, that suffices.
248 /// This is used when *some* bound in `B` is known to suffice, but
249 /// we don't know which.
250 AllBounds(Vec
<VerifyBound
<'tcx
>>),
253 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
254 struct TwoRegions
<'tcx
> {
259 #[derive(Copy, Clone, PartialEq)]
261 /// We added `RegionVid`
264 /// We added the given `constraint`
265 AddConstraint(Constraint
<'tcx
>),
267 /// We added the given `verify`
270 /// We added the given `given`
271 AddGiven(Region
<'tcx
>, ty
::RegionVid
),
273 /// We added a GLB/LUB "combination variable"
274 AddCombination(CombineMapType
, TwoRegions
<'tcx
>),
276 /// During skolemization, we sometimes purge entries from the undo
277 /// log in a kind of minisnapshot (unlike other snapshots, this
278 /// purging actually takes place *on success*). In that case, we
279 /// replace the corresponding entry with `Noop` so as to avoid the
280 /// need to do a bunch of swapping. (We can't use `swap_remove` as
281 /// the order of the vector is important.)
285 #[derive(Copy, Clone, PartialEq)]
286 enum CombineMapType
{
291 type CombineMap
<'tcx
> = FxHashMap
<TwoRegions
<'tcx
>, RegionVid
>;
293 #[derive(Debug, Clone, Copy)]
294 pub struct RegionVariableInfo
{
295 pub origin
: RegionVariableOrigin
,
296 pub universe
: ty
::UniverseIndex
,
299 pub struct RegionSnapshot
{
301 region_snapshot
: ut
::Snapshot
<ut
::InPlace
<ty
::RegionVid
>>,
302 any_unifications
: bool
,
305 /// When working with placeholder regions, we often wish to find all of
306 /// the regions that are either reachable from a placeholder region, or
307 /// which can reach a placeholder region, or both. We call such regions
308 /// *tainted* regions. This struct allows you to decide what set of
309 /// tainted regions you want.
311 pub struct TaintDirections
{
316 impl TaintDirections
{
317 pub fn incoming() -> Self {
324 pub fn outgoing() -> Self {
331 pub fn both() -> Self {
339 impl<'tcx
> RegionConstraintCollector
<'tcx
> {
340 pub fn new() -> Self {
344 pub fn num_region_vars(&self) -> usize {
348 pub fn region_constraint_data(&self) -> &RegionConstraintData
<'tcx
> {
352 /// Once all the constraints have been gathered, extract out the final data.
354 /// Not legal during a snapshot.
355 pub fn into_infos_and_data(self) -> (VarInfos
, RegionConstraintData
<'tcx
>) {
356 assert
!(!self.in_snapshot());
357 (self.var_infos
, self.data
)
360 /// Takes (and clears) the current set of constraints. Note that
361 /// the set of variables remains intact, but all relationships
362 /// between them are reset. This is used during NLL checking to
363 /// grab the set of constraints that arose from a particular
366 /// We don't want to leak relationships between variables between
367 /// points because just because (say) `r1 == r2` was true at some
368 /// point P in the graph doesn't imply that it will be true at
369 /// some other point Q, in NLL.
371 /// Not legal during a snapshot.
372 pub fn take_and_reset_data(&mut self) -> RegionConstraintData
<'tcx
> {
373 assert
!(!self.in_snapshot());
375 // If you add a new field to `RegionConstraintCollector`, you
376 // should think carefully about whether it needs to be cleared
377 // or updated in some way.
378 let RegionConstraintCollector
{
385 num_open_snapshots
: _
,
390 // Clear the tables of (lubs, glbs), so that we will create
391 // fresh regions if we do a LUB operation. As it happens,
392 // LUB/GLB are not performed by the MIR type-checker, which is
393 // the one that uses this method, but it's good to be correct.
397 // Clear all unifications and recreate the variables a "now
398 // un-unified" state. Note that when we unify `a` and `b`, we
399 // also insert `a <= b` and a `b <= a` edges, so the
400 // `RegionConstraintData` contains the relationship here.
401 if *any_unifications
{
402 unification_table
.reset_unifications(|vid
| unify_key
::RegionVidKey { min_vid: vid }
);
403 *any_unifications
= false;
406 mem
::replace(data
, RegionConstraintData
::default())
409 pub fn data(&self) -> &RegionConstraintData
<'tcx
> {
413 fn in_snapshot(&self) -> bool
{
414 self.num_open_snapshots
> 0
417 pub fn start_snapshot(&mut self) -> RegionSnapshot
{
418 let length
= self.undo_log
.len();
419 debug
!("RegionConstraintCollector: start_snapshot({})", length
);
420 self.num_open_snapshots
+= 1;
423 region_snapshot
: self.unification_table
.snapshot(),
424 any_unifications
: self.any_unifications
,
428 fn assert_open_snapshot(&self, snapshot
: &RegionSnapshot
) {
429 assert
!(self.undo_log
.len() >= snapshot
.length
);
430 assert
!(self.num_open_snapshots
> 0);
433 pub fn commit(&mut self, snapshot
: RegionSnapshot
) {
434 debug
!("RegionConstraintCollector: commit({})", snapshot
.length
);
435 self.assert_open_snapshot(&snapshot
);
437 if self.num_open_snapshots
== 1 {
438 // The root snapshot. It's safe to clear the undo log because
439 // there's no snapshot further out that we might need to roll back
441 assert
!(snapshot
.length
== 0);
442 self.undo_log
.clear();
445 self.num_open_snapshots
-= 1;
447 self.unification_table
.commit(snapshot
.region_snapshot
);
450 pub fn rollback_to(&mut self, snapshot
: RegionSnapshot
) {
451 debug
!("RegionConstraintCollector: rollback_to({:?})", snapshot
);
452 self.assert_open_snapshot(&snapshot
);
454 while self.undo_log
.len() > snapshot
.length
{
455 let undo_entry
= self.undo_log
.pop().unwrap();
456 self.rollback_undo_entry(undo_entry
);
459 self.num_open_snapshots
-= 1;
461 self.unification_table
.rollback_to(snapshot
.region_snapshot
);
462 self.any_unifications
= snapshot
.any_unifications
;
465 fn rollback_undo_entry(&mut self, undo_entry
: UndoLog
<'tcx
>) {
468 // nothing to do here
471 self.var_infos
.pop().unwrap();
472 assert_eq
!(self.var_infos
.len(), vid
.index() as usize);
474 AddConstraint(ref constraint
) => {
475 self.data
.constraints
.remove(constraint
);
477 AddVerify(index
) => {
478 self.data
.verifys
.pop();
479 assert_eq
!(self.data
.verifys
.len(), index
);
481 AddGiven(sub
, sup
) => {
482 self.data
.givens
.remove(&(sub
, sup
));
484 AddCombination(Glb
, ref regions
) => {
485 self.glbs
.remove(regions
);
487 AddCombination(Lub
, ref regions
) => {
488 self.lubs
.remove(regions
);
493 pub fn new_region_var(
495 universe
: ty
::UniverseIndex
,
496 origin
: RegionVariableOrigin
,
498 let vid
= self.var_infos
.push(RegionVariableInfo { origin, universe }
);
500 let u_vid
= self.unification_table
501 .new_key(unify_key
::RegionVidKey { min_vid: vid }
);
502 assert_eq
!(vid
, u_vid
);
503 if self.in_snapshot() {
504 self.undo_log
.push(AddVar(vid
));
507 "created new region variable {:?} with origin {:?}",
513 /// Returns the universe for the given variable.
514 pub fn var_universe(&self, vid
: RegionVid
) -> ty
::UniverseIndex
{
515 self.var_infos
[vid
].universe
518 /// Returns the origin for the given variable.
519 pub fn var_origin(&self, vid
: RegionVid
) -> RegionVariableOrigin
{
520 self.var_infos
[vid
].origin
523 /// Removes all the edges to/from the placeholder regions that are
524 /// in `skols`. This is used after a higher-ranked operation
525 /// completes to remove all trace of the placeholder regions
526 /// created in that time.
527 pub fn pop_placeholders(&mut self, placeholders
: &FxHashSet
<ty
::Region
<'tcx
>>) {
528 debug
!("pop_placeholders(placeholders={:?})", placeholders
);
530 assert
!(self.in_snapshot());
532 let constraints_to_kill
: Vec
<usize> = self.undo_log
536 .filter(|&(_
, undo_entry
)| kill_constraint(placeholders
, undo_entry
))
537 .map(|(index
, _
)| index
)
540 for index
in constraints_to_kill
{
541 let undo_entry
= mem
::replace(&mut self.undo_log
[index
], Purged
);
542 self.rollback_undo_entry(undo_entry
);
547 fn kill_constraint
<'tcx
>(
548 placeholders
: &FxHashSet
<ty
::Region
<'tcx
>>,
549 undo_entry
: &UndoLog
<'tcx
>,
552 &AddConstraint(Constraint
::VarSubVar(..)) => false,
553 &AddConstraint(Constraint
::RegSubVar(a
, _
)) => placeholders
.contains(&a
),
554 &AddConstraint(Constraint
::VarSubReg(_
, b
)) => placeholders
.contains(&b
),
555 &AddConstraint(Constraint
::RegSubReg(a
, b
)) => {
556 placeholders
.contains(&a
) || placeholders
.contains(&b
)
558 &AddGiven(..) => false,
559 &AddVerify(_
) => false,
560 &AddCombination(_
, ref two_regions
) => {
561 placeholders
.contains(&two_regions
.a
) || placeholders
.contains(&two_regions
.b
)
563 &AddVar(..) | &Purged
=> false,
570 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
571 debruijn
: ty
::DebruijnIndex
,
573 // Creates a fresh bound variable for use in GLB computations.
574 // See discussion of GLB computation in the large comment at
575 // the top of this file for more details.
577 // This computation is potentially wrong in the face of
578 // rollover. It's conceivable, if unlikely, that one might
579 // wind up with accidental capture for nested functions in
580 // that case, if the outer function had bound regions created
581 // a very long time before and the inner function somehow
582 // wound up rolling over such that supposedly fresh
583 // identifiers were in fact shadowed. For now, we just assert
584 // that there is no rollover -- eventually we should try to be
585 // robust against this possibility, either by checking the set
586 // of bound identifiers that appear in a given expression and
587 // ensure that we generate one that is distinct, or by
588 // changing the representation of bound regions in a fn
591 let sc
= self.bound_count
;
592 self.bound_count
= sc
+ 1;
594 if sc
>= self.bound_count
{
595 bug
!("rollover in RegionInference new_bound()");
598 tcx
.mk_region(ReLateBound(debruijn
, BrFresh(sc
)))
601 fn add_constraint(&mut self, constraint
: Constraint
<'tcx
>, origin
: SubregionOrigin
<'tcx
>) {
602 // cannot add constraints once regions are resolved
604 "RegionConstraintCollector: add_constraint({:?})",
608 // never overwrite an existing (constraint, origin) - only insert one if it isn't
609 // present in the map yet. This prevents origins from outside the snapshot being
610 // replaced with "less informative" origins e.g. during calls to `can_eq`
611 let in_snapshot
= self.in_snapshot();
612 let undo_log
= &mut self.undo_log
;
613 self.data
.constraints
.entry(constraint
).or_insert_with(|| {
615 undo_log
.push(AddConstraint(constraint
));
621 fn add_verify(&mut self, verify
: Verify
<'tcx
>) {
622 // cannot add verifys once regions are resolved
623 debug
!("RegionConstraintCollector: add_verify({:?})", verify
);
625 // skip no-op cases known to be satisfied
626 if let VerifyBound
::AllBounds(ref bs
) = verify
.bound
{
632 let index
= self.data
.verifys
.len();
633 self.data
.verifys
.push(verify
);
634 if self.in_snapshot() {
635 self.undo_log
.push(AddVerify(index
));
639 pub fn add_given(&mut self, sub
: Region
<'tcx
>, sup
: ty
::RegionVid
) {
640 // cannot add givens once regions are resolved
641 if self.data
.givens
.insert((sub
, sup
)) {
642 debug
!("add_given({:?} <= {:?})", sub
, sup
);
644 if self.in_snapshot() {
645 self.undo_log
.push(AddGiven(sub
, sup
));
650 pub fn make_eqregion(
652 origin
: SubregionOrigin
<'tcx
>,
657 // Eventually, it would be nice to add direct support for
659 self.make_subregion(origin
.clone(), sub
, sup
);
660 self.make_subregion(origin
, sup
, sub
);
662 if let (ty
::ReVar(sub
), ty
::ReVar(sup
)) = (*sub
, *sup
) {
663 self.unification_table
.union(sub
, sup
);
664 self.any_unifications
= true;
669 pub fn make_subregion(
671 origin
: SubregionOrigin
<'tcx
>,
675 // cannot add constraints once regions are resolved
677 "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}",
682 (&ReLateBound(..), _
) | (_
, &ReLateBound(..)) => {
685 "cannot relate bound region: {:?} <= {:?}",
691 // all regions are subregions of static, so we can ignore this
693 (&ReVar(sub_id
), &ReVar(sup_id
)) => {
694 self.add_constraint(Constraint
::VarSubVar(sub_id
, sup_id
), origin
);
696 (_
, &ReVar(sup_id
)) => {
697 self.add_constraint(Constraint
::RegSubVar(sub
, sup_id
), origin
);
699 (&ReVar(sub_id
), _
) => {
700 self.add_constraint(Constraint
::VarSubReg(sub_id
, sup
), origin
);
703 self.add_constraint(Constraint
::RegSubReg(sub
, sup
), origin
);
708 /// See `Verify::VerifyGenericBound`
709 pub fn verify_generic_bound(
711 origin
: SubregionOrigin
<'tcx
>,
712 kind
: GenericKind
<'tcx
>,
714 bound
: VerifyBound
<'tcx
>,
716 self.add_verify(Verify
{
726 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
727 origin
: SubregionOrigin
<'tcx
>,
731 // cannot add constraints once regions are resolved
732 debug
!("RegionConstraintCollector: lub_regions({:?}, {:?})", a
, b
);
734 (r @
&ReStatic
, _
) | (_
, r @
&ReStatic
) => {
735 r
// nothing lives longer than static
742 _
=> self.combine_vars(tcx
, Lub
, a
, b
, origin
),
748 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
749 origin
: SubregionOrigin
<'tcx
>,
753 // cannot add constraints once regions are resolved
754 debug
!("RegionConstraintCollector: glb_regions({:?}, {:?})", a
, b
);
756 (&ReStatic
, r
) | (r
, &ReStatic
) => {
757 r
// static lives longer than everything else
764 _
=> self.combine_vars(tcx
, Glb
, a
, b
, origin
),
768 pub fn opportunistic_resolve_var(
770 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
772 ) -> ty
::Region
<'tcx
> {
773 let vid
= self.unification_table
.probe_value(rid
).min_vid
;
774 tcx
.mk_region(ty
::ReVar(vid
))
777 fn combine_map(&mut self, t
: CombineMapType
) -> &mut CombineMap
<'tcx
> {
779 Glb
=> &mut self.glbs
,
780 Lub
=> &mut self.lubs
,
786 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
790 origin
: SubregionOrigin
<'tcx
>,
792 let vars
= TwoRegions { a: a, b: b }
;
793 if let Some(&c
) = self.combine_map(t
).get(&vars
) {
794 return tcx
.mk_region(ReVar(c
));
796 let a_universe
= self.universe(a
);
797 let b_universe
= self.universe(b
);
798 let c_universe
= cmp
::max(a_universe
, b_universe
);
799 let c
= self.new_region_var(c_universe
, MiscVariable(origin
.span()));
800 self.combine_map(t
).insert(vars
, c
);
801 if self.in_snapshot() {
802 self.undo_log
.push(AddCombination(t
, vars
));
804 let new_r
= tcx
.mk_region(ReVar(c
));
805 for &old_r
in &[a
, b
] {
807 Glb
=> self.make_subregion(origin
.clone(), new_r
, old_r
),
808 Lub
=> self.make_subregion(origin
.clone(), old_r
, new_r
),
811 debug
!("combine_vars() c={:?}", c
);
815 fn universe(&self, region
: Region
<'tcx
>) -> ty
::UniverseIndex
{
822 | ty
::ReEarlyBound(..) => ty
::UniverseIndex
::ROOT
,
823 ty
::RePlaceholder(placeholder
) => placeholder
.universe
,
824 ty
::ReClosureBound(vid
) | ty
::ReVar(vid
) => self.var_universe(vid
),
825 ty
::ReLateBound(..) => bug
!("universe(): encountered bound region {:?}", region
),
829 pub fn vars_created_since_snapshot(&self, mark
: &RegionSnapshot
) -> Vec
<RegionVid
> {
830 self.undo_log
[mark
.length
..]
832 .filter_map(|&elt
| match elt
{
833 AddVar(vid
) => Some(vid
),
839 /// Computes all regions that have been related to `r0` since the
840 /// mark `mark` was made---`r0` itself will be the first
841 /// entry. The `directions` parameter controls what kind of
842 /// relations are considered. For example, one can say that only
843 /// "incoming" edges to `r0` are desired, in which case one will
844 /// get the set of regions `{r|r <= r0}`. This is used when
845 /// checking whether placeholder regions are being improperly
846 /// related to other regions.
849 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
850 mark
: &RegionSnapshot
,
852 directions
: TaintDirections
,
853 ) -> FxHashSet
<ty
::Region
<'tcx
>> {
855 "tainted(mark={:?}, r0={:?}, directions={:?})",
859 // `result_set` acts as a worklist: we explore all outgoing
860 // edges and add any new regions we find to result_set. This
861 // is not a terribly efficient implementation.
862 let mut taint_set
= taint
::TaintSet
::new(directions
, r0
);
863 taint_set
.fixed_point(tcx
, &self.undo_log
[mark
.length
..], &self.data
.verifys
);
864 debug
!("tainted: result={:?}", taint_set
);
865 return taint_set
.into_set();
869 impl fmt
::Debug
for RegionSnapshot
{
870 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
871 write
!(f
, "RegionSnapshot(length={})", self.length
)
875 impl<'tcx
> fmt
::Debug
for GenericKind
<'tcx
> {
876 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
878 GenericKind
::Param(ref p
) => write
!(f
, "{:?}", p
),
879 GenericKind
::Projection(ref p
) => write
!(f
, "{:?}", p
),
884 impl<'tcx
> fmt
::Display
for GenericKind
<'tcx
> {
885 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
887 GenericKind
::Param(ref p
) => write
!(f
, "{}", p
),
888 GenericKind
::Projection(ref p
) => write
!(f
, "{}", p
),
893 impl<'a
, 'gcx
, 'tcx
> GenericKind
<'tcx
> {
894 pub fn to_ty(&self, tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>) -> Ty
<'tcx
> {
896 GenericKind
::Param(ref p
) => p
.to_ty(tcx
),
897 GenericKind
::Projection(ref p
) => tcx
.mk_projection(p
.item_def_id
, p
.substs
),
902 impl<'a
, 'gcx
, 'tcx
> VerifyBound
<'tcx
> {
903 pub fn must_hold(&self) -> bool
{
905 VerifyBound
::IfEq(..) => false,
906 VerifyBound
::OutlivedBy(ty
::ReStatic
) => true,
907 VerifyBound
::OutlivedBy(_
) => false,
908 VerifyBound
::AnyBound(bs
) => bs
.iter().any(|b
| b
.must_hold()),
909 VerifyBound
::AllBounds(bs
) => bs
.iter().all(|b
| b
.must_hold()),
913 pub fn cannot_hold(&self) -> bool
{
915 VerifyBound
::IfEq(_
, b
) => b
.cannot_hold(),
916 VerifyBound
::OutlivedBy(ty
::ReEmpty
) => true,
917 VerifyBound
::OutlivedBy(_
) => false,
918 VerifyBound
::AnyBound(bs
) => bs
.iter().all(|b
| b
.cannot_hold()),
919 VerifyBound
::AllBounds(bs
) => bs
.iter().any(|b
| b
.cannot_hold()),
923 pub fn or(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
924 if self.must_hold() || vb
.cannot_hold() {
926 } else if self.cannot_hold() || vb
.must_hold() {
929 VerifyBound
::AnyBound(vec
![self, vb
])
933 pub fn and(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
934 if self.must_hold() && vb
.must_hold() {
936 } else if self.cannot_hold() && vb
.cannot_hold() {
939 VerifyBound
::AllBounds(vec
![self, vb
])
944 impl<'tcx
> RegionConstraintData
<'tcx
> {
945 /// True if this region constraint data contains no constraints.
946 pub fn is_empty(&self) -> bool
{
947 let RegionConstraintData
{
952 constraints
.is_empty() && verifys
.is_empty() && givens
.is_empty()