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, Idx}
;
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 /// 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:
161 #[derive(Debug, Clone)]
162 pub enum VerifyBound
<'tcx
> {
163 /// B = exists {R} --> some 'r in {R} must outlive 'min
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
168 AnyRegion(Vec
<Region
<'tcx
>>),
170 /// B = forall {R} --> all 'r in {R} must outlive 'min
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
175 AllRegions(Vec
<Region
<'tcx
>>),
177 /// B = exists {B} --> 'min must meet some bound b in {B}
178 AnyBound(Vec
<VerifyBound
<'tcx
>>),
180 /// B = forall {B} --> 'min must meet all bounds b in {B}
181 AllBounds(Vec
<VerifyBound
<'tcx
>>),
184 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
185 struct TwoRegions
<'tcx
> {
190 #[derive(Copy, Clone, PartialEq)]
191 enum UndoLogEntry
<'tcx
> {
192 /// Pushed when we start a snapshot.
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.
200 /// We added `RegionVid`
203 /// We added the given `constraint`
204 AddConstraint(Constraint
<'tcx
>),
206 /// We added the given `verify`
209 /// We added the given `given`
210 AddGiven(Region
<'tcx
>, ty
::RegionVid
),
212 /// We added a GLB/LUB "combination variable"
213 AddCombination(CombineMapType
, TwoRegions
<'tcx
>),
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.)
224 #[derive(Copy, Clone, PartialEq)]
225 enum CombineMapType
{
230 type CombineMap
<'tcx
> = FxHashMap
<TwoRegions
<'tcx
>, RegionVid
>;
232 #[derive(Debug, Clone, Copy)]
233 pub struct RegionVariableInfo
{
234 pub origin
: RegionVariableOrigin
,
235 pub universe
: ty
::UniverseIndex
,
238 pub struct RegionSnapshot
{
240 region_snapshot
: ut
::Snapshot
<ut
::InPlace
<ty
::RegionVid
>>,
241 any_unifications
: bool
,
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.
250 pub struct TaintDirections
{
255 impl TaintDirections
{
256 pub fn incoming() -> Self {
263 pub fn outgoing() -> Self {
270 pub fn both() -> Self {
278 impl<'tcx
> RegionConstraintCollector
<'tcx
> {
279 pub fn new() -> RegionConstraintCollector
<'tcx
> {
280 RegionConstraintCollector
{
281 var_infos
: VarInfos
::default(),
282 data
: RegionConstraintData
::default(),
286 undo_log
: Vec
::new(),
287 unification_table
: ut
::UnificationTable
::new(),
288 any_unifications
: false,
292 pub fn num_region_vars(&self) -> usize {
296 pub fn region_constraint_data(&self) -> &RegionConstraintData
<'tcx
> {
300 /// Once all the constraints have been gathered, extract out the final data.
302 /// Not legal during a snapshot.
303 pub fn into_infos_and_data(self) -> (VarInfos
, RegionConstraintData
<'tcx
>) {
304 assert
!(!self.in_snapshot());
305 (self.var_infos
, self.data
)
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
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.
319 /// Not legal during a snapshot.
320 pub fn take_and_reset_data(&mut self) -> RegionConstraintData
<'tcx
> {
321 assert
!(!self.in_snapshot());
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
{
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.
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.
348 if *any_unifications
{
349 unification_table
.reset_unifications(|vid
| unify_key
::RegionVidKey { min_vid: vid }
);
350 *any_unifications
= false;
353 mem
::replace(data
, RegionConstraintData
::default())
356 pub fn data(&self) -> &RegionConstraintData
<'tcx
> {
360 fn in_snapshot(&self) -> bool
{
361 !self.undo_log
.is_empty()
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
);
370 region_snapshot
: self.unification_table
.snapshot(),
371 any_unifications
: self.any_unifications
,
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
);
380 if snapshot
.length
== 0 {
381 self.undo_log
.truncate(0);
383 (*self.undo_log
)[snapshot
.length
] = CommitedSnapshot
;
385 self.unification_table
.commit(snapshot
.region_snapshot
);
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
);
396 let c
= self.undo_log
.pop().unwrap();
397 assert
!(c
== OpenSnapshot
);
398 self.unification_table
.rollback_to(snapshot
.region_snapshot
);
399 self.any_unifications
= snapshot
.any_unifications
;
402 fn rollback_undo_entry(&mut self, undo_entry
: UndoLogEntry
<'tcx
>) {
405 panic
!("Failure to observe stack discipline");
407 Purged
| CommitedSnapshot
=> {
408 // nothing to do here
411 self.var_infos
.pop().unwrap();
412 assert_eq
!(self.var_infos
.len(), vid
.index() as usize);
414 AddConstraint(ref constraint
) => {
415 self.data
.constraints
.remove(constraint
);
417 AddVerify(index
) => {
418 self.data
.verifys
.pop();
419 assert_eq
!(self.data
.verifys
.len(), index
);
421 AddGiven(sub
, sup
) => {
422 self.data
.givens
.remove(&(sub
, sup
));
424 AddCombination(Glb
, ref regions
) => {
425 self.glbs
.remove(regions
);
427 AddCombination(Lub
, ref regions
) => {
428 self.lubs
.remove(regions
);
433 pub fn new_region_var(&mut self,
434 universe
: ty
::UniverseIndex
,
435 origin
: RegionVariableOrigin
) -> RegionVid
{
436 let vid
= self.var_infos
.push(RegionVariableInfo
{
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
));
448 "created new region variable {:?} with origin {:?}",
455 /// Returns the universe for the given variable.
456 pub fn var_universe(&self, vid
: RegionVid
) -> ty
::UniverseIndex
{
457 self.var_infos
[vid
].universe
460 /// Returns the origin for the given variable.
461 pub fn var_origin(&self, vid
: RegionVid
) -> RegionVariableOrigin
{
462 self.var_infos
[vid
].origin
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(
471 skolemization_count
: ty
::UniverseIndex
,
472 skols
: &FxHashSet
<ty
::Region
<'tcx
>>,
473 snapshot
: &RegionSnapshot
,
475 debug
!("pop_skolemized_regions(skols={:?})", skols
);
477 assert
!(self.in_snapshot());
478 assert
!(self.undo_log
[snapshot
.length
] == OpenSnapshot
);
480 skolemization_count
.as_usize() >= skols
.len(),
481 "popping more skolemized variables than actually exist, \
482 sc now = {:?}, skols.len = {:?}",
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);
493 ty
::ReSkolemized(universe
, _
) =>
494 universe
>= first_to_pop
&&
495 universe
< last_to_pop
,
499 "invalid skolemization keys or keys out of range ({:?}..{:?}): {:?}",
505 let constraints_to_kill
: Vec
<usize> = self.undo_log
509 .filter(|&(_
, undo_entry
)| kill_constraint(skols
, undo_entry
))
510 .map(|(index
, _
)| index
)
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
);
520 fn kill_constraint
<'tcx
>(
521 skols
: &FxHashSet
<ty
::Region
<'tcx
>>,
522 undo_entry
: &UndoLogEntry
<'tcx
>,
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
)
531 &AddGiven(..) => false,
532 &AddVerify(_
) => false,
533 &AddCombination(_
, ref two_regions
) => {
534 skols
.contains(&two_regions
.a
) || skols
.contains(&two_regions
.b
)
536 &AddVar(..) | &OpenSnapshot
| &Purged
| &CommitedSnapshot
=> false,
543 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
544 debruijn
: ty
::DebruijnIndex
,
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.
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
564 let sc
= self.bound_count
;
565 self.bound_count
= sc
+ 1;
567 if sc
>= self.bound_count
{
568 bug
!("rollover in RegionInference new_bound()");
571 tcx
.mk_region(ReLateBound(debruijn
, BrFresh(sc
)))
574 fn add_constraint(&mut self, constraint
: Constraint
<'tcx
>, origin
: SubregionOrigin
<'tcx
>) {
575 // cannot add constraints once regions are resolved
577 "RegionConstraintCollector: add_constraint({:?})",
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(|| {
588 undo_log
.push(AddConstraint(constraint
));
594 fn add_verify(&mut self, verify
: Verify
<'tcx
>) {
595 // cannot add verifys once regions are resolved
596 debug
!("RegionConstraintCollector: add_verify({:?})", verify
);
598 // skip no-op cases known to be satisfied
600 VerifyBound
::AllBounds(ref bs
) if bs
.len() == 0 => {
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
));
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
);
618 if self.in_snapshot() {
619 self.undo_log
.push(AddGiven(sub
, sup
));
624 pub fn make_eqregion(
626 origin
: SubregionOrigin
<'tcx
>,
631 // Eventually, it would be nice to add direct support for
633 self.make_subregion(origin
.clone(), sub
, sup
);
634 self.make_subregion(origin
, sup
, sub
);
636 if let (ty
::ReVar(sub
), ty
::ReVar(sup
)) = (*sub
, *sup
) {
637 self.unification_table
.union(sub
, sup
);
638 self.any_unifications
= true;
643 pub fn make_subregion(
645 origin
: SubregionOrigin
<'tcx
>,
649 // cannot add constraints once regions are resolved
651 "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}",
658 (&ReLateBound(..), _
) | (_
, &ReLateBound(..)) => {
661 "cannot relate bound region: {:?} <= {:?}",
667 // all regions are subregions of static, so we can ignore this
669 (&ReVar(sub_id
), &ReVar(sup_id
)) => {
670 self.add_constraint(Constraint
::VarSubVar(sub_id
, sup_id
), origin
);
672 (_
, &ReVar(sup_id
)) => {
673 self.add_constraint(Constraint
::RegSubVar(sub
, sup_id
), origin
);
675 (&ReVar(sub_id
), _
) => {
676 self.add_constraint(Constraint
::VarSubReg(sub_id
, sup
), origin
);
679 self.add_constraint(Constraint
::RegSubReg(sub
, sup
), origin
);
684 /// See `Verify::VerifyGenericBound`
685 pub fn verify_generic_bound(
687 origin
: SubregionOrigin
<'tcx
>,
688 kind
: GenericKind
<'tcx
>,
690 bound
: VerifyBound
<'tcx
>,
692 self.add_verify(Verify
{
702 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
703 origin
: SubregionOrigin
<'tcx
>,
707 // cannot add constraints once regions are resolved
708 debug
!("RegionConstraintCollector: lub_regions({:?}, {:?})", a
, b
);
710 (r @
&ReStatic
, _
) | (_
, r @
&ReStatic
) => {
711 r
// nothing lives longer than static
718 _
=> self.combine_vars(tcx
, Lub
, a
, b
, origin
.clone()),
724 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
725 origin
: SubregionOrigin
<'tcx
>,
729 // cannot add constraints once regions are resolved
730 debug
!("RegionConstraintCollector: glb_regions({:?}, {:?})", a
, b
);
732 (&ReStatic
, r
) | (r
, &ReStatic
) => {
733 r
// static lives longer than everything else
740 _
=> self.combine_vars(tcx
, Glb
, a
, b
, origin
.clone()),
744 pub fn opportunistic_resolve_var(
746 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
748 ) -> ty
::Region
<'tcx
> {
749 let vid
= self.unification_table
.probe_value(rid
).min_vid
;
750 tcx
.mk_region(ty
::ReVar(vid
))
753 fn combine_map(&mut self, t
: CombineMapType
) -> &mut CombineMap
<'tcx
> {
755 Glb
=> &mut self.glbs
,
756 Lub
=> &mut self.lubs
,
762 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
766 origin
: SubregionOrigin
<'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
));
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()));
776 self.combine_map(t
).insert(vars
, c
);
777 if self.in_snapshot() {
778 self.undo_log
.push(AddCombination(t
, vars
));
780 let new_r
= tcx
.mk_region(ReVar(c
));
781 for &old_r
in &[a
, b
] {
783 Glb
=> self.make_subregion(origin
.clone(), new_r
, old_r
),
784 Lub
=> self.make_subregion(origin
.clone(), old_r
, new_r
),
787 debug
!("combine_vars() c={:?}", c
);
791 fn universe(&self, region
: Region
<'tcx
>) -> ty
::UniverseIndex
{
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
),
809 pub fn vars_created_since_snapshot(&self, mark
: &RegionSnapshot
) -> Vec
<RegionVid
> {
810 self.undo_log
[mark
.length
..]
812 .filter_map(|&elt
| match elt
{
813 AddVar(vid
) => Some(vid
),
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.
829 tcx
: TyCtxt
<'_
, '_
, 'tcx
>,
830 mark
: &RegionSnapshot
,
832 directions
: TaintDirections
,
833 ) -> FxHashSet
<ty
::Region
<'tcx
>> {
835 "tainted(mark={:?}, r0={:?}, directions={:?})",
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();
851 impl fmt
::Debug
for RegionSnapshot
{
852 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
853 write
!(f
, "RegionSnapshot(length={})", self.length
)
857 impl<'tcx
> fmt
::Debug
for GenericKind
<'tcx
> {
858 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
860 GenericKind
::Param(ref p
) => write
!(f
, "{:?}", p
),
861 GenericKind
::Projection(ref p
) => write
!(f
, "{:?}", p
),
866 impl<'tcx
> fmt
::Display
for GenericKind
<'tcx
> {
867 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
869 GenericKind
::Param(ref p
) => write
!(f
, "{}", p
),
870 GenericKind
::Projection(ref p
) => write
!(f
, "{}", p
),
875 impl<'a
, 'gcx
, 'tcx
> GenericKind
<'tcx
> {
876 pub fn to_ty(&self, tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>) -> Ty
<'tcx
> {
878 GenericKind
::Param(ref p
) => p
.to_ty(tcx
),
879 GenericKind
::Projection(ref p
) => tcx
.mk_projection(p
.item_def_id
, p
.substs
),
884 impl<'a
, 'gcx
, 'tcx
> VerifyBound
<'tcx
> {
885 fn for_each_region(&self, f
: &mut dyn FnMut(ty
::Region
<'tcx
>)) {
887 &VerifyBound
::AnyRegion(ref rs
) | &VerifyBound
::AllRegions(ref rs
) => for &r
in rs
{
891 &VerifyBound
::AnyBound(ref bs
) | &VerifyBound
::AllBounds(ref bs
) => for b
in bs
{
892 b
.for_each_region(f
);
897 pub fn must_hold(&self) -> bool
{
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()),
906 pub fn cannot_hold(&self) -> bool
{
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()),
915 pub fn or(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
916 if self.must_hold() || vb
.cannot_hold() {
918 } else if self.cannot_hold() || vb
.must_hold() {
921 VerifyBound
::AnyBound(vec
![self, vb
])
925 pub fn and(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
926 if self.must_hold() && vb
.must_hold() {
928 } else if self.cannot_hold() && vb
.cannot_hold() {
931 VerifyBound
::AllBounds(vec
![self, vb
])
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
{
944 constraints
.is_empty() && verifys
.is_empty() && givens
.is_empty()