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 pub use self::Constraint
::*;
14 pub use self::UndoLogEntry
::*;
15 pub use self::CombineMapType
::*;
16 pub use self::RegionResolutionError
::*;
17 pub use self::VarValue
::*;
19 use super::{RegionVariableOrigin, SubregionOrigin, MiscVariable}
;
22 use rustc_data_structures
::fnv
::{FnvHashMap, FnvHashSet}
;
23 use rustc_data_structures
::graph
::{self, Direction, NodeIndex, OUTGOING}
;
24 use rustc_data_structures
::unify
::{self, UnificationTable}
;
25 use middle
::free_region
::FreeRegionMap
;
26 use ty
::{self, Ty, TyCtxt}
;
27 use ty
::{BoundRegion, Region, RegionVid}
;
28 use ty
::{ReEmpty, ReStatic, ReFree, ReEarlyBound, ReErased}
;
29 use ty
::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh}
;
31 use std
::cell
::{Cell, RefCell}
;
32 use std
::cmp
::Ordering
::{self, Less, Greater, Equal}
;
40 // A constraint that influences the inference process.
41 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
42 pub enum Constraint
<'tcx
> {
43 // One region variable is subregion of another
44 ConstrainVarSubVar(RegionVid
, RegionVid
),
46 // Concrete region is subregion of region variable
47 ConstrainRegSubVar(&'tcx Region
, RegionVid
),
49 // Region variable is subregion of concrete region. This does not
50 // directly affect inference, but instead is checked after
51 // inference is complete.
52 ConstrainVarSubReg(RegionVid
, &'tcx Region
),
54 // A constraint where neither side is a variable. This does not
55 // directly affect inference, but instead is checked after
56 // inference is complete.
57 ConstrainRegSubReg(&'tcx Region
, &'tcx Region
),
60 // VerifyGenericBound(T, _, R, RS): The parameter type `T` (or
61 // associated type) must outlive the region `R`. `T` is known to
62 // outlive `RS`. Therefore verify that `R <= RS[i]` for some
63 // `i`. Inference variables may be involved (but this verification
64 // step doesn't influence inference).
66 pub struct Verify
<'tcx
> {
67 kind
: GenericKind
<'tcx
>,
68 origin
: SubregionOrigin
<'tcx
>,
70 bound
: VerifyBound
<'tcx
>,
73 #[derive(Copy, Clone, PartialEq, Eq)]
74 pub enum GenericKind
<'tcx
> {
76 Projection(ty
::ProjectionTy
<'tcx
>),
79 // When we introduce a verification step, we wish to test that a
80 // particular region (let's call it `'min`) meets some bound.
81 // The bound is described the by the following grammar:
83 pub enum VerifyBound
<'tcx
> {
84 // B = exists {R} --> some 'r in {R} must outlive 'min
86 // Put another way, the subject value is known to outlive all
87 // regions in {R}, so if any of those outlives 'min, then the
89 AnyRegion(Vec
<&'tcx Region
>),
91 // B = forall {R} --> all 'r in {R} must outlive 'min
93 // Put another way, the subject value is known to outlive some
94 // region in {R}, so if all of those outlives 'min, then the bound
96 AllRegions(Vec
<&'tcx Region
>),
98 // B = exists {B} --> 'min must meet some bound b in {B}
99 AnyBound(Vec
<VerifyBound
<'tcx
>>),
101 // B = forall {B} --> 'min must meet all bounds b in {B}
102 AllBounds(Vec
<VerifyBound
<'tcx
>>),
105 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
106 pub struct TwoRegions
<'tcx
> {
111 #[derive(Copy, Clone, PartialEq)]
112 pub enum UndoLogEntry
<'tcx
> {
113 /// Pushed when we start a snapshot.
116 /// Replaces an `OpenSnapshot` when a snapshot is committed, but
117 /// that snapshot is not the root. If the root snapshot is
118 /// unrolled, all nested snapshots must be committed.
121 /// We added `RegionVid`
124 /// We added the given `constraint`
125 AddConstraint(Constraint
<'tcx
>),
127 /// We added the given `verify`
130 /// We added the given `given`
131 AddGiven(ty
::FreeRegion
, ty
::RegionVid
),
133 /// We added a GLB/LUB "combinaton variable"
134 AddCombination(CombineMapType
, TwoRegions
<'tcx
>),
136 /// During skolemization, we sometimes purge entries from the undo
137 /// log in a kind of minisnapshot (unlike other snapshots, this
138 /// purging actually takes place *on success*). In that case, we
139 /// replace the corresponding entry with `Noop` so as to avoid the
140 /// need to do a bunch of swapping. (We can't use `swap_remove` as
141 /// the order of the vector is important.)
145 #[derive(Copy, Clone, PartialEq)]
146 pub enum CombineMapType
{
151 #[derive(Clone, Debug)]
152 pub enum RegionResolutionError
<'tcx
> {
153 /// `ConcreteFailure(o, a, b)`:
155 /// `o` requires that `a <= b`, but this does not hold
156 ConcreteFailure(SubregionOrigin
<'tcx
>, &'tcx Region
, &'tcx Region
),
158 /// `GenericBoundFailure(p, s, a)
160 /// The parameter/associated-type `p` must be known to outlive the lifetime
161 /// `a` (but none of the known bounds are sufficient).
162 GenericBoundFailure(SubregionOrigin
<'tcx
>, GenericKind
<'tcx
>, &'tcx Region
),
164 /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
166 /// Could not infer a value for `v` because `sub_r <= v` (due to
167 /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
168 /// `sub_r <= sup_r` does not hold.
169 SubSupConflict(RegionVariableOrigin
,
170 SubregionOrigin
<'tcx
>,
172 SubregionOrigin
<'tcx
>,
175 /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
176 /// more specific errors message by suggesting to the user where they
177 /// should put a lifetime. In those cases we process and put those errors
178 /// into `ProcessedErrors` before we do any reporting.
179 ProcessedErrors(Vec
<ProcessedErrorOrigin
<'tcx
>>,
183 #[derive(Clone, Debug)]
184 pub enum ProcessedErrorOrigin
<'tcx
> {
185 ConcreteFailure(SubregionOrigin
<'tcx
>, &'tcx Region
, &'tcx Region
),
186 VariableFailure(RegionVariableOrigin
),
189 /// SameRegions is used to group regions that we think are the same and would
190 /// like to indicate so to the user.
191 /// For example, the following function
193 /// struct Foo { bar: i32 }
194 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b i32 {
198 /// would report an error because we expect 'a and 'b to match, and so we group
199 /// 'a and 'b together inside a SameRegions struct
200 #[derive(Clone, Debug)]
201 pub struct SameRegions
{
202 pub scope_id
: ast
::NodeId
,
203 pub regions
: Vec
<BoundRegion
>,
207 pub fn contains(&self, other
: &BoundRegion
) -> bool
{
208 self.regions
.contains(other
)
211 pub fn push(&mut self, other
: BoundRegion
) {
212 self.regions
.push(other
);
216 pub type CombineMap
<'tcx
> = FnvHashMap
<TwoRegions
<'tcx
>, RegionVid
>;
218 pub struct RegionVarBindings
<'a
, 'gcx
: 'a
+'tcx
, 'tcx
: 'a
> {
219 tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
220 var_origins
: RefCell
<Vec
<RegionVariableOrigin
>>,
222 // Constraints of the form `A <= B` introduced by the region
223 // checker. Here at least one of `A` and `B` must be a region
225 constraints
: RefCell
<FnvHashMap
<Constraint
<'tcx
>, SubregionOrigin
<'tcx
>>>,
227 // A "verify" is something that we need to verify after inference is
228 // done, but which does not directly affect inference in any way.
230 // An example is a `A <= B` where neither `A` nor `B` are
231 // inference variables.
232 verifys
: RefCell
<Vec
<Verify
<'tcx
>>>,
234 // A "given" is a relationship that is known to hold. In particular,
235 // we often know from closure fn signatures that a particular free
236 // region must be a subregion of a region variable:
238 // foo.iter().filter(<'a> |x: &'a &'b T| ...)
240 // In situations like this, `'b` is in fact a region variable
241 // introduced by the call to `iter()`, and `'a` is a bound region
242 // on the closure (as indicated by the `<'a>` prefix). If we are
243 // naive, we wind up inferring that `'b` must be `'static`,
244 // because we require that it be greater than `'a` and we do not
245 // know what `'a` is precisely.
247 // This hashmap is used to avoid that naive scenario. Basically we
248 // record the fact that `'a <= 'b` is implied by the fn signature,
249 // and then ignore the constraint when solving equations. This is
250 // a bit of a hack but seems to work.
251 givens
: RefCell
<FnvHashSet
<(ty
::FreeRegion
, ty
::RegionVid
)>>,
253 lubs
: RefCell
<CombineMap
<'tcx
>>,
254 glbs
: RefCell
<CombineMap
<'tcx
>>,
255 skolemization_count
: Cell
<u32>,
256 bound_count
: Cell
<u32>,
258 // The undo log records actions that might later be undone.
260 // Note: when the undo_log is empty, we are not actively
261 // snapshotting. When the `start_snapshot()` method is called, we
262 // push an OpenSnapshot entry onto the list to indicate that we
263 // are now actively snapshotting. The reason for this is that
264 // otherwise we end up adding entries for things like the lower
265 // bound on a variable and so forth, which can never be rolled
267 undo_log
: RefCell
<Vec
<UndoLogEntry
<'tcx
>>>,
268 unification_table
: RefCell
<UnificationTable
<ty
::RegionVid
>>,
270 // This contains the results of inference. It begins as an empty
271 // option and only acquires a value after inference is complete.
272 values
: RefCell
<Option
<Vec
<VarValue
<'tcx
>>>>,
275 pub struct RegionSnapshot
{
277 region_snapshot
: unify
::Snapshot
<ty
::RegionVid
>,
278 skolemization_count
: u32,
281 /// When working with skolemized regions, we often wish to find all of
282 /// the regions that are either reachable from a skolemized region, or
283 /// which can reach a skolemized region, or both. We call such regions
284 /// *tained* regions. This struct allows you to decide what set of
285 /// tainted regions you want.
287 pub struct TaintDirections
{
292 impl TaintDirections
{
293 pub fn incoming() -> Self {
294 TaintDirections { incoming: true, outgoing: false }
297 pub fn outgoing() -> Self {
298 TaintDirections { incoming: false, outgoing: true }
301 pub fn both() -> Self {
302 TaintDirections { incoming: true, outgoing: true }
306 struct TaintSet
<'tcx
> {
307 directions
: TaintDirections
,
308 regions
: FnvHashSet
<&'tcx ty
::Region
>
311 impl<'a
, 'gcx
, 'tcx
> TaintSet
<'tcx
> {
312 fn new(directions
: TaintDirections
,
313 initial_region
: &'tcx ty
::Region
)
315 let mut regions
= FnvHashSet();
316 regions
.insert(initial_region
);
317 TaintSet { directions: directions, regions: regions }
320 fn fixed_point(&mut self,
321 tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
322 undo_log
: &[UndoLogEntry
<'tcx
>],
323 verifys
: &[Verify
<'tcx
>]) {
324 let mut prev_len
= 0;
325 while prev_len
< self.len() {
326 debug
!("tainted: prev_len = {:?} new_len = {:?}",
327 prev_len
, self.len());
329 prev_len
= self.len();
331 for undo_entry
in undo_log
{
333 &AddConstraint(ConstrainVarSubVar(a
, b
)) => {
334 self.add_edge(tcx
.mk_region(ReVar(a
)),
335 tcx
.mk_region(ReVar(b
)));
337 &AddConstraint(ConstrainRegSubVar(a
, b
)) => {
338 self.add_edge(a
, tcx
.mk_region(ReVar(b
)));
340 &AddConstraint(ConstrainVarSubReg(a
, b
)) => {
341 self.add_edge(tcx
.mk_region(ReVar(a
)), b
);
343 &AddConstraint(ConstrainRegSubReg(a
, b
)) => {
347 self.add_edge(tcx
.mk_region(ReFree(a
)),
348 tcx
.mk_region(ReVar(b
)));
351 verifys
[i
].bound
.for_each_region(&mut |b
| {
352 self.add_edge(verifys
[i
].region
, b
);
356 &AddCombination(..) |
359 &CommitedSnapshot
=> {}
365 fn into_set(self) -> FnvHashSet
<&'tcx ty
::Region
> {
369 fn len(&self) -> usize {
373 fn add_edge(&mut self,
374 source
: &'tcx ty
::Region
,
375 target
: &'tcx ty
::Region
) {
376 if self.directions
.incoming
{
377 if self.regions
.contains(&target
) {
378 self.regions
.insert(source
);
382 if self.directions
.outgoing
{
383 if self.regions
.contains(&source
) {
384 self.regions
.insert(target
);
390 impl<'a
, 'gcx
, 'tcx
> RegionVarBindings
<'a
, 'gcx
, 'tcx
> {
391 pub fn new(tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>) -> RegionVarBindings
<'a
, 'gcx
, 'tcx
> {
394 var_origins
: RefCell
::new(Vec
::new()),
395 values
: RefCell
::new(None
),
396 constraints
: RefCell
::new(FnvHashMap()),
397 verifys
: RefCell
::new(Vec
::new()),
398 givens
: RefCell
::new(FnvHashSet()),
399 lubs
: RefCell
::new(FnvHashMap()),
400 glbs
: RefCell
::new(FnvHashMap()),
401 skolemization_count
: Cell
::new(0),
402 bound_count
: Cell
::new(0),
403 undo_log
: RefCell
::new(Vec
::new()),
404 unification_table
: RefCell
::new(UnificationTable
::new()),
408 fn in_snapshot(&self) -> bool
{
409 !self.undo_log
.borrow().is_empty()
412 pub fn start_snapshot(&self) -> RegionSnapshot
{
413 let length
= self.undo_log
.borrow().len();
414 debug
!("RegionVarBindings: start_snapshot({})", length
);
415 self.undo_log
.borrow_mut().push(OpenSnapshot
);
418 region_snapshot
: self.unification_table
.borrow_mut().snapshot(),
419 skolemization_count
: self.skolemization_count
.get(),
423 pub fn commit(&self, snapshot
: RegionSnapshot
) {
424 debug
!("RegionVarBindings: commit({})", snapshot
.length
);
425 assert
!(self.undo_log
.borrow().len() > snapshot
.length
);
426 assert
!((*self.undo_log
.borrow())[snapshot
.length
] == OpenSnapshot
);
427 assert
!(self.skolemization_count
.get() == snapshot
.skolemization_count
,
428 "failed to pop skolemized regions: {} now vs {} at start",
429 self.skolemization_count
.get(),
430 snapshot
.skolemization_count
);
432 let mut undo_log
= self.undo_log
.borrow_mut();
433 if snapshot
.length
== 0 {
434 undo_log
.truncate(0);
436 (*undo_log
)[snapshot
.length
] = CommitedSnapshot
;
438 self.unification_table
.borrow_mut().commit(snapshot
.region_snapshot
);
441 pub fn rollback_to(&self, snapshot
: RegionSnapshot
) {
442 debug
!("RegionVarBindings: rollback_to({:?})", snapshot
);
443 let mut undo_log
= self.undo_log
.borrow_mut();
444 assert
!(undo_log
.len() > snapshot
.length
);
445 assert
!((*undo_log
)[snapshot
.length
] == OpenSnapshot
);
446 while undo_log
.len() > snapshot
.length
+ 1 {
447 self.rollback_undo_entry(undo_log
.pop().unwrap());
449 let c
= undo_log
.pop().unwrap();
450 assert
!(c
== OpenSnapshot
);
451 self.skolemization_count
.set(snapshot
.skolemization_count
);
452 self.unification_table
.borrow_mut()
453 .rollback_to(snapshot
.region_snapshot
);
456 pub fn rollback_undo_entry(&self, undo_entry
: UndoLogEntry
<'tcx
>) {
459 panic
!("Failure to observe stack discipline");
461 Purged
| CommitedSnapshot
=> {
462 // nothing to do here
465 let mut var_origins
= self.var_origins
.borrow_mut();
466 var_origins
.pop().unwrap();
467 assert_eq
!(var_origins
.len(), vid
.index
as usize);
469 AddConstraint(ref constraint
) => {
470 self.constraints
.borrow_mut().remove(constraint
);
472 AddVerify(index
) => {
473 self.verifys
.borrow_mut().pop();
474 assert_eq
!(self.verifys
.borrow().len(), index
);
476 AddGiven(sub
, sup
) => {
477 self.givens
.borrow_mut().remove(&(sub
, sup
));
479 AddCombination(Glb
, ref regions
) => {
480 self.glbs
.borrow_mut().remove(regions
);
482 AddCombination(Lub
, ref regions
) => {
483 self.lubs
.borrow_mut().remove(regions
);
488 pub fn num_vars(&self) -> u32 {
489 let len
= self.var_origins
.borrow().len();
490 // enforce no overflow
491 assert
!(len
as u32 as usize == len
);
495 pub fn new_region_var(&self, origin
: RegionVariableOrigin
) -> RegionVid
{
496 let vid
= RegionVid { index: self.num_vars() }
;
497 self.var_origins
.borrow_mut().push(origin
.clone());
499 let u_vid
= self.unification_table
.borrow_mut().new_key(
500 unify_key
::RegionVidKey { min_vid: vid }
502 assert_eq
!(vid
, u_vid
);
503 if self.in_snapshot() {
504 self.undo_log
.borrow_mut().push(AddVar(vid
));
506 debug
!("created new region variable {:?} with origin {:?}",
512 pub fn var_origin(&self, vid
: RegionVid
) -> RegionVariableOrigin
{
513 self.var_origins
.borrow()[vid
.index
as usize].clone()
516 /// Creates a new skolemized region. Skolemized regions are fresh
517 /// regions used when performing higher-ranked computations. They
518 /// must be used in a very particular way and are never supposed
519 /// to "escape" out into error messages or the code at large.
521 /// The idea is to always create a snapshot. Skolemized regions
522 /// can be created in the context of this snapshot, but before the
523 /// snapshot is committed or rolled back, they must be popped
524 /// (using `pop_skolemized_regions`), so that their numbers can be
525 /// recycled. Normally you don't have to think about this: you use
526 /// the APIs in `higher_ranked/mod.rs`, such as
527 /// `skolemize_late_bound_regions` and `plug_leaks`, which will
528 /// guide you on this path (ensure that the `SkolemizationMap` is
529 /// consumed and you are good). There are also somewhat extensive
530 /// comments in `higher_ranked/README.md`.
532 /// The `snapshot` argument to this function is not really used;
533 /// it's just there to make it explicit which snapshot bounds the
534 /// skolemized region that results. It should always be the top-most snapshot.
535 pub fn push_skolemized(&self, br
: ty
::BoundRegion
, snapshot
: &RegionSnapshot
)
537 assert
!(self.in_snapshot());
538 assert
!(self.undo_log
.borrow()[snapshot
.length
] == OpenSnapshot
);
540 let sc
= self.skolemization_count
.get();
541 self.skolemization_count
.set(sc
+ 1);
542 self.tcx
.mk_region(ReSkolemized(ty
::SkolemizedRegionVid { index: sc }
, br
))
545 /// Removes all the edges to/from the skolemized regions that are
546 /// in `skols`. This is used after a higher-ranked operation
547 /// completes to remove all trace of the skolemized regions
548 /// created in that time.
549 pub fn pop_skolemized(&self,
550 skols
: &FnvHashSet
<&'tcx ty
::Region
>,
551 snapshot
: &RegionSnapshot
) {
552 debug
!("pop_skolemized_regions(skols={:?})", skols
);
554 assert
!(self.in_snapshot());
555 assert
!(self.undo_log
.borrow()[snapshot
.length
] == OpenSnapshot
);
556 assert
!(self.skolemization_count
.get() as usize >= skols
.len(),
557 "popping more skolemized variables than actually exist, \
558 sc now = {}, skols.len = {}",
559 self.skolemization_count
.get(),
562 let last_to_pop
= self.skolemization_count
.get();
563 let first_to_pop
= last_to_pop
- (skols
.len() as u32);
565 assert
!(first_to_pop
>= snapshot
.skolemization_count
,
566 "popping more regions than snapshot contains, \
567 sc now = {}, sc then = {}, skols.len = {}",
568 self.skolemization_count
.get(),
569 snapshot
.skolemization_count
,
574 ty
::ReSkolemized(index
, _
) =>
575 index
.index
>= first_to_pop
&&
576 index
.index
< last_to_pop
,
580 "invalid skolemization keys or keys out of range ({}..{}): {:?}",
581 snapshot
.skolemization_count
,
582 self.skolemization_count
.get(),
586 let mut undo_log
= self.undo_log
.borrow_mut();
588 let constraints_to_kill
: Vec
<usize> =
592 .filter(|&(_
, undo_entry
)| kill_constraint(skols
, undo_entry
))
593 .map(|(index
, _
)| index
)
596 for index
in constraints_to_kill
{
597 let undo_entry
= mem
::replace(&mut undo_log
[index
], Purged
);
598 self.rollback_undo_entry(undo_entry
);
601 self.skolemization_count
.set(snapshot
.skolemization_count
);
604 fn kill_constraint
<'tcx
>(skols
: &FnvHashSet
<&'tcx ty
::Region
>,
605 undo_entry
: &UndoLogEntry
<'tcx
>)
608 &AddConstraint(ConstrainVarSubVar(..)) =>
610 &AddConstraint(ConstrainRegSubVar(a
, _
)) =>
612 &AddConstraint(ConstrainVarSubReg(_
, b
)) =>
614 &AddConstraint(ConstrainRegSubReg(a
, b
)) =>
615 skols
.contains(&a
) || skols
.contains(&b
),
620 &AddCombination(_
, ref two_regions
) =>
621 skols
.contains(&two_regions
.a
) ||
622 skols
.contains(&two_regions
.b
),
633 pub fn new_bound(&self, debruijn
: ty
::DebruijnIndex
) -> &'tcx Region
{
634 // Creates a fresh bound variable for use in GLB computations.
635 // See discussion of GLB computation in the large comment at
636 // the top of this file for more details.
638 // This computation is potentially wrong in the face of
639 // rollover. It's conceivable, if unlikely, that one might
640 // wind up with accidental capture for nested functions in
641 // that case, if the outer function had bound regions created
642 // a very long time before and the inner function somehow
643 // wound up rolling over such that supposedly fresh
644 // identifiers were in fact shadowed. For now, we just assert
645 // that there is no rollover -- eventually we should try to be
646 // robust against this possibility, either by checking the set
647 // of bound identifiers that appear in a given expression and
648 // ensure that we generate one that is distinct, or by
649 // changing the representation of bound regions in a fn
652 let sc
= self.bound_count
.get();
653 self.bound_count
.set(sc
+ 1);
655 if sc
>= self.bound_count
.get() {
656 bug
!("rollover in RegionInference new_bound()");
659 self.tcx
.mk_region(ReLateBound(debruijn
, BrFresh(sc
)))
662 fn values_are_none(&self) -> bool
{
663 self.values
.borrow().is_none()
666 fn add_constraint(&self, constraint
: Constraint
<'tcx
>, origin
: SubregionOrigin
<'tcx
>) {
667 // cannot add constraints once regions are resolved
668 assert
!(self.values_are_none());
670 debug
!("RegionVarBindings: add_constraint({:?})", constraint
);
672 if self.constraints
.borrow_mut().insert(constraint
, origin
).is_none() {
673 if self.in_snapshot() {
674 self.undo_log
.borrow_mut().push(AddConstraint(constraint
));
679 fn add_verify(&self, verify
: Verify
<'tcx
>) {
680 // cannot add verifys once regions are resolved
681 assert
!(self.values_are_none());
683 debug
!("RegionVarBindings: add_verify({:?})", verify
);
685 // skip no-op cases known to be satisfied
687 VerifyBound
::AllBounds(ref bs
) if bs
.len() == 0 => { return; }
691 let mut verifys
= self.verifys
.borrow_mut();
692 let index
= verifys
.len();
693 verifys
.push(verify
);
694 if self.in_snapshot() {
695 self.undo_log
.borrow_mut().push(AddVerify(index
));
699 pub fn add_given(&self, sub
: ty
::FreeRegion
, sup
: ty
::RegionVid
) {
700 // cannot add givens once regions are resolved
701 assert
!(self.values_are_none());
703 let mut givens
= self.givens
.borrow_mut();
704 if givens
.insert((sub
, sup
)) {
705 debug
!("add_given({:?} <= {:?})", sub
, sup
);
707 self.undo_log
.borrow_mut().push(AddGiven(sub
, sup
));
711 pub fn make_eqregion(&self,
712 origin
: SubregionOrigin
<'tcx
>,
716 // Eventually, it would be nice to add direct support for
718 self.make_subregion(origin
.clone(), sub
, sup
);
719 self.make_subregion(origin
, sup
, sub
);
721 if let (ty
::ReVar(sub
), ty
::ReVar(sup
)) = (*sub
, *sup
) {
722 self.unification_table
.borrow_mut().union(sub
, sup
);
727 pub fn make_subregion(&self,
728 origin
: SubregionOrigin
<'tcx
>,
731 // cannot add constraints once regions are resolved
732 assert
!(self.values_are_none());
734 debug
!("RegionVarBindings: make_subregion({:?}, {:?}) due to {:?}",
740 (&ReEarlyBound(..), _
) |
741 (&ReLateBound(..), _
) |
742 (_
, &ReEarlyBound(..)) |
743 (_
, &ReLateBound(..)) => {
744 span_bug
!(origin
.span(),
745 "cannot relate bound region: {:?} <= {:?}",
750 // all regions are subregions of static, so we can ignore this
752 (&ReVar(sub_id
), &ReVar(sup_id
)) => {
753 self.add_constraint(ConstrainVarSubVar(sub_id
, sup_id
), origin
);
755 (_
, &ReVar(sup_id
)) => {
756 self.add_constraint(ConstrainRegSubVar(sub
, sup_id
), origin
);
758 (&ReVar(sub_id
), _
) => {
759 self.add_constraint(ConstrainVarSubReg(sub_id
, sup
), origin
);
762 self.add_constraint(ConstrainRegSubReg(sub
, sup
), origin
);
767 /// See `Verify::VerifyGenericBound`
768 pub fn verify_generic_bound(&self,
769 origin
: SubregionOrigin
<'tcx
>,
770 kind
: GenericKind
<'tcx
>,
772 bound
: VerifyBound
<'tcx
>) {
773 self.add_verify(Verify
{
781 pub fn lub_regions(&self,
782 origin
: SubregionOrigin
<'tcx
>,
786 // cannot add constraints once regions are resolved
787 assert
!(self.values_are_none());
789 debug
!("RegionVarBindings: lub_regions({:?}, {:?})", a
, b
);
791 (r @
&ReStatic
, _
) | (_
, r @
&ReStatic
) => {
792 r
// nothing lives longer than static
800 self.combine_vars(Lub
, a
, b
, origin
.clone(), |this
, old_r
, new_r
| {
801 this
.make_subregion(origin
.clone(), old_r
, new_r
)
807 pub fn glb_regions(&self,
808 origin
: SubregionOrigin
<'tcx
>,
812 // cannot add constraints once regions are resolved
813 assert
!(self.values_are_none());
815 debug
!("RegionVarBindings: glb_regions({:?}, {:?})", a
, b
);
817 (&ReStatic
, r
) | (r
, &ReStatic
) => {
818 r
// static lives longer than everything else
826 self.combine_vars(Glb
, a
, b
, origin
.clone(), |this
, old_r
, new_r
| {
827 this
.make_subregion(origin
.clone(), new_r
, old_r
)
833 pub fn resolve_var(&self, rid
: RegionVid
) -> &'tcx ty
::Region
{
834 match *self.values
.borrow() {
836 span_bug
!((*self.var_origins
.borrow())[rid
.index
as usize].span(),
837 "attempt to resolve region variable before values have \
840 Some(ref values
) => {
841 let r
= lookup(self.tcx
, values
, rid
);
842 debug
!("resolve_var({:?}) = {:?}", rid
, r
);
848 pub fn opportunistic_resolve_var(&self, rid
: RegionVid
) -> &'tcx ty
::Region
{
849 let vid
= self.unification_table
.borrow_mut().find_value(rid
).min_vid
;
850 self.tcx
.mk_region(ty
::ReVar(vid
))
853 fn combine_map(&self, t
: CombineMapType
) -> &RefCell
<CombineMap
<'tcx
>> {
860 pub fn combine_vars
<F
>(&self,
864 origin
: SubregionOrigin
<'tcx
>,
867 where F
: FnMut(&RegionVarBindings
<'a
, 'gcx
, 'tcx
>, &'tcx Region
, &'tcx Region
)
869 let vars
= TwoRegions { a: a, b: b }
;
870 if let Some(&c
) = self.combine_map(t
).borrow().get(&vars
) {
871 return self.tcx
.mk_region(ReVar(c
));
873 let c
= self.new_region_var(MiscVariable(origin
.span()));
874 self.combine_map(t
).borrow_mut().insert(vars
, c
);
875 if self.in_snapshot() {
876 self.undo_log
.borrow_mut().push(AddCombination(t
, vars
));
878 relate(self, a
, self.tcx
.mk_region(ReVar(c
)));
879 relate(self, b
, self.tcx
.mk_region(ReVar(c
)));
880 debug
!("combine_vars() c={:?}", c
);
881 self.tcx
.mk_region(ReVar(c
))
884 pub fn vars_created_since_snapshot(&self, mark
: &RegionSnapshot
) -> Vec
<RegionVid
> {
885 self.undo_log
.borrow()[mark
.length
..]
889 AddVar(vid
) => Some(vid
),
896 /// Computes all regions that have been related to `r0` since the
897 /// mark `mark` was made---`r0` itself will be the first
898 /// entry. The `directions` parameter controls what kind of
899 /// relations are considered. For example, one can say that only
900 /// "incoming" edges to `r0` are desired, in which case one will
901 /// get the set of regions `{r|r <= r0}`. This is used when
902 /// checking whether skolemized regions are being improperly
903 /// related to other regions.
904 pub fn tainted(&self,
905 mark
: &RegionSnapshot
,
907 directions
: TaintDirections
)
908 -> FnvHashSet
<&'tcx ty
::Region
> {
909 debug
!("tainted(mark={:?}, r0={:?}, directions={:?})",
910 mark
, r0
, directions
);
912 // `result_set` acts as a worklist: we explore all outgoing
913 // edges and add any new regions we find to result_set. This
914 // is not a terribly efficient implementation.
915 let mut taint_set
= TaintSet
::new(directions
, r0
);
916 taint_set
.fixed_point(self.tcx
,
917 &self.undo_log
.borrow()[mark
.length
..],
918 &self.verifys
.borrow());
919 debug
!("tainted: result={:?}", taint_set
.regions
);
920 return taint_set
.into_set();
923 /// This function performs the actual region resolution. It must be
924 /// called after all constraints have been added. It performs a
925 /// fixed-point iteration to find region values which satisfy all
926 /// constraints, assuming such values can be found; if they cannot,
927 /// errors are reported.
928 pub fn resolve_regions(&self,
929 free_regions
: &FreeRegionMap
,
930 subject_node
: ast
::NodeId
)
931 -> Vec
<RegionResolutionError
<'tcx
>> {
932 debug
!("RegionVarBindings: resolve_regions()");
933 let mut errors
= vec
![];
934 let v
= self.infer_variable_values(free_regions
, &mut errors
, subject_node
);
935 *self.values
.borrow_mut() = Some(v
);
939 fn lub_concrete_regions(&self,
940 free_regions
: &FreeRegionMap
,
945 (&ReLateBound(..), _
) |
946 (_
, &ReLateBound(..)) |
947 (&ReEarlyBound(..), _
) |
948 (_
, &ReEarlyBound(..)) |
951 bug
!("cannot relate region: LUB({:?}, {:?})", a
, b
);
954 (r @
&ReStatic
, _
) | (_
, r @
&ReStatic
) => {
955 r
// nothing lives longer than static
958 (&ReEmpty
, r
) | (r
, &ReEmpty
) => {
959 r
// everything lives longer than empty
962 (&ReVar(v_id
), _
) | (_
, &ReVar(v_id
)) => {
963 span_bug
!((*self.var_origins
.borrow())[v_id
.index
as usize].span(),
964 "lub_concrete_regions invoked with non-concrete \
965 regions: {:?}, {:?}",
970 (&ReFree(fr
), &ReScope(s_id
)) |
971 (&ReScope(s_id
), &ReFree(fr
)) => {
972 // A "free" region can be interpreted as "some region
973 // at least as big as the block fr.scope_id". So, we can
974 // reasonably compare free regions and scopes:
975 let r_id
= self.tcx
.region_maps
.nearest_common_ancestor(fr
.scope
, s_id
);
977 if r_id
== fr
.scope
{
978 // if the free region's scope `fr.scope_id` is bigger than
979 // the scope region `s_id`, then the LUB is the free
981 self.tcx
.mk_region(ReFree(fr
))
983 // otherwise, we don't know what the free region is,
984 // so we must conservatively say the LUB is static:
985 self.tcx
.mk_region(ReStatic
)
989 (&ReScope(a_id
), &ReScope(b_id
)) => {
990 // The region corresponding to an outer block is a
991 // subtype of the region corresponding to an inner
993 self.tcx
.mk_region(ReScope(
994 self.tcx
.region_maps
.nearest_common_ancestor(a_id
, b_id
)))
997 (&ReFree(a_fr
), &ReFree(b_fr
)) => {
998 self.tcx
.mk_region(free_regions
.lub_free_regions(a_fr
, b_fr
))
1001 // For these types, we cannot define any additional
1003 (&ReSkolemized(..), _
) |
1004 (_
, &ReSkolemized(..)) => {
1008 self.tcx
.mk_region(ReStatic
)
1015 // ______________________________________________________________________
1017 #[derive(Copy, Clone, Debug)]
1018 pub enum VarValue
<'tcx
> {
1019 Value(&'tcx Region
),
1023 struct RegionAndOrigin
<'tcx
> {
1024 region
: &'tcx Region
,
1025 origin
: SubregionOrigin
<'tcx
>,
1028 type RegionGraph
<'tcx
> = graph
::Graph
<(), Constraint
<'tcx
>>;
1030 impl<'a
, 'gcx
, 'tcx
> RegionVarBindings
<'a
, 'gcx
, 'tcx
> {
1031 fn infer_variable_values(&self,
1032 free_regions
: &FreeRegionMap
,
1033 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
1034 subject
: ast
::NodeId
)
1035 -> Vec
<VarValue
<'tcx
>> {
1036 let mut var_data
= self.construct_var_data();
1038 // Dorky hack to cause `dump_constraints` to only get called
1039 // if debug mode is enabled:
1040 debug
!("----() End constraint listing (subject={}) {:?}---",
1042 self.dump_constraints(subject
));
1043 graphviz
::maybe_print_constraints_for(self, subject
);
1045 let graph
= self.construct_graph();
1046 self.expand_givens(&graph
);
1047 self.expansion(free_regions
, &mut var_data
);
1048 self.collect_errors(free_regions
, &mut var_data
, errors
);
1049 self.collect_var_errors(free_regions
, &var_data
, &graph
, errors
);
1053 fn construct_var_data(&self) -> Vec
<VarValue
<'tcx
>> {
1054 (0..self.num_vars() as usize)
1055 .map(|_
| Value(self.tcx
.mk_region(ty
::ReEmpty
)))
1059 fn dump_constraints(&self, subject
: ast
::NodeId
) {
1060 debug
!("----() Start constraint listing (subject={}) ()----",
1062 for (idx
, (constraint
, _
)) in self.constraints
.borrow().iter().enumerate() {
1063 debug
!("Constraint {} => {:?}", idx
, constraint
);
1067 fn expand_givens(&self, graph
: &RegionGraph
) {
1068 // Givens are a kind of horrible hack to account for
1069 // constraints like 'c <= '0 that are known to hold due to
1070 // closure signatures (see the comment above on the `givens`
1071 // field). They should go away. But until they do, the role
1072 // of this fn is to account for the transitive nature:
1078 let mut givens
= self.givens
.borrow_mut();
1079 let seeds
: Vec
<_
> = givens
.iter().cloned().collect();
1080 for (fr
, vid
) in seeds
{
1081 let seed_index
= NodeIndex(vid
.index
as usize);
1082 for succ_index
in graph
.depth_traverse(seed_index
, OUTGOING
) {
1083 let succ_index
= succ_index
.0 as u32;
1084 if succ_index
< self.num_vars() {
1085 let succ_vid
= RegionVid { index: succ_index }
;
1086 givens
.insert((fr
, succ_vid
));
1092 fn expansion(&self, free_regions
: &FreeRegionMap
, var_values
: &mut [VarValue
<'tcx
>]) {
1093 self.iterate_until_fixed_point("Expansion", |constraint
, origin
| {
1094 debug
!("expansion: constraint={:?} origin={:?}",
1095 constraint
, origin
);
1097 ConstrainRegSubVar(a_region
, b_vid
) => {
1098 let b_data
= &mut var_values
[b_vid
.index
as usize];
1099 self.expand_node(free_regions
, a_region
, b_vid
, b_data
)
1101 ConstrainVarSubVar(a_vid
, b_vid
) => {
1102 match var_values
[a_vid
.index
as usize] {
1103 ErrorValue
=> false,
1104 Value(a_region
) => {
1105 let b_node
= &mut var_values
[b_vid
.index
as usize];
1106 self.expand_node(free_regions
, a_region
, b_vid
, b_node
)
1110 ConstrainRegSubReg(..) |
1111 ConstrainVarSubReg(..) => {
1112 // These constraints are checked after expansion
1113 // is done, in `collect_errors`.
1120 fn expand_node(&self,
1121 free_regions
: &FreeRegionMap
,
1122 a_region
: &'tcx Region
,
1124 b_data
: &mut VarValue
<'tcx
>)
1126 debug
!("expand_node({:?}, {:?} == {:?})",
1131 // Check if this relationship is implied by a given.
1134 if self.givens
.borrow().contains(&(fr
, b_vid
)) {
1143 Value(cur_region
) => {
1144 let lub
= self.lub_concrete_regions(free_regions
, a_region
, cur_region
);
1145 if lub
== cur_region
{
1149 debug
!("Expanding value of {:?} from {:?} to {:?}",
1154 *b_data
= Value(lub
);
1164 /// After expansion is complete, go and check upper bounds (i.e.,
1165 /// cases where the region cannot grow larger than a fixed point)
1166 /// and check that they are satisfied.
1167 fn collect_errors(&self,
1168 free_regions
: &FreeRegionMap
,
1169 var_data
: &mut Vec
<VarValue
<'tcx
>>,
1170 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>) {
1171 let constraints
= self.constraints
.borrow();
1172 for (constraint
, origin
) in constraints
.iter() {
1173 debug
!("collect_errors: constraint={:?} origin={:?}",
1174 constraint
, origin
);
1176 ConstrainRegSubVar(..) |
1177 ConstrainVarSubVar(..) => {
1178 // Expansion will ensure that these constraints hold. Ignore.
1181 ConstrainRegSubReg(sub
, sup
) => {
1182 if free_regions
.is_subregion_of(self.tcx
, sub
, sup
) {
1186 debug
!("collect_errors: region error at {:?}: \
1187 cannot verify that {:?} <= {:?}",
1192 errors
.push(ConcreteFailure((*origin
).clone(), sub
, sup
));
1195 ConstrainVarSubReg(a_vid
, b_region
) => {
1196 let a_data
= &mut var_data
[a_vid
.index
as usize];
1197 debug
!("contraction: {:?} == {:?}, {:?}",
1202 let a_region
= match *a_data
{
1203 ErrorValue
=> continue,
1204 Value(a_region
) => a_region
,
1207 // Do not report these errors immediately:
1208 // instead, set the variable value to error and
1209 // collect them later.
1210 if !free_regions
.is_subregion_of(self.tcx
, a_region
, b_region
) {
1211 debug
!("collect_errors: region error at {:?}: \
1212 cannot verify that {:?}={:?} <= {:?}",
1217 *a_data
= ErrorValue
;
1223 for verify
in self.verifys
.borrow().iter() {
1224 debug
!("collect_errors: verify={:?}", verify
);
1225 let sub
= normalize(self.tcx
, var_data
, verify
.region
);
1226 if verify
.bound
.is_met(self.tcx
, free_regions
, var_data
, sub
) {
1230 debug
!("collect_errors: region error at {:?}: \
1231 cannot verify that {:?} <= {:?}",
1236 errors
.push(GenericBoundFailure(verify
.origin
.clone(),
1237 verify
.kind
.clone(),
1242 /// Go over the variables that were declared to be error variables
1243 /// and create a `RegionResolutionError` for each of them.
1244 fn collect_var_errors(&self,
1245 free_regions
: &FreeRegionMap
,
1246 var_data
: &[VarValue
<'tcx
>],
1247 graph
: &RegionGraph
<'tcx
>,
1248 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>) {
1249 debug
!("collect_var_errors");
1251 // This is the best way that I have found to suppress
1252 // duplicate and related errors. Basically we keep a set of
1253 // flags for every node. Whenever an error occurs, we will
1254 // walk some portion of the graph looking to find pairs of
1255 // conflicting regions to report to the user. As we walk, we
1256 // trip the flags from false to true, and if we find that
1257 // we've already reported an error involving any particular
1258 // node we just stop and don't report the current error. The
1259 // idea is to report errors that derive from independent
1260 // regions of the graph, but not those that derive from
1261 // overlapping locations.
1262 let mut dup_vec
= vec
![u32::MAX
; self.num_vars() as usize];
1264 for idx
in 0..self.num_vars() as usize {
1265 match var_data
[idx
] {
1267 /* Inference successful */
1270 /* Inference impossible, this value contains
1271 inconsistent constraints.
1273 I think that in this case we should report an
1274 error now---unlike the case above, we can't
1275 wait to see whether the user needs the result
1276 of this variable. The reason is that the mere
1277 existence of this variable implies that the
1278 region graph is inconsistent, whether or not it
1281 For example, we may have created a region
1282 variable that is the GLB of two other regions
1283 which do not have a GLB. Even if that variable
1284 is not used, it implies that those two regions
1285 *should* have a GLB.
1287 At least I think this is true. It may be that
1288 the mere existence of a conflict in a region variable
1289 that is not used is not a problem, so if this rule
1290 starts to create problems we'll have to revisit
1291 this portion of the code and think hard about it. =) */
1293 let node_vid
= RegionVid { index: idx as u32 }
;
1294 self.collect_error_for_expanding_node(free_regions
,
1304 fn construct_graph(&self) -> RegionGraph
<'tcx
> {
1305 let num_vars
= self.num_vars();
1307 let constraints
= self.constraints
.borrow();
1309 let mut graph
= graph
::Graph
::new();
1311 for _
in 0..num_vars
{
1315 // Issue #30438: two distinct dummy nodes, one for incoming
1316 // edges (dummy_source) and another for outgoing edges
1317 // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
1318 // dummy node leads one to think (erroneously) there exists a
1319 // path from `b` to `a`. Two dummy nodes sidesteps the issue.
1320 let dummy_source
= graph
.add_node(());
1321 let dummy_sink
= graph
.add_node(());
1323 for (constraint
, _
) in constraints
.iter() {
1325 ConstrainVarSubVar(a_id
, b_id
) => {
1326 graph
.add_edge(NodeIndex(a_id
.index
as usize),
1327 NodeIndex(b_id
.index
as usize),
1330 ConstrainRegSubVar(_
, b_id
) => {
1331 graph
.add_edge(dummy_source
, NodeIndex(b_id
.index
as usize), *constraint
);
1333 ConstrainVarSubReg(a_id
, _
) => {
1334 graph
.add_edge(NodeIndex(a_id
.index
as usize), dummy_sink
, *constraint
);
1336 ConstrainRegSubReg(..) => {
1337 // this would be an edge from `dummy_source` to
1338 // `dummy_sink`; just ignore it.
1346 fn collect_error_for_expanding_node(&self,
1347 free_regions
: &FreeRegionMap
,
1348 graph
: &RegionGraph
<'tcx
>,
1349 dup_vec
: &mut [u32],
1350 node_idx
: RegionVid
,
1351 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>) {
1352 // Errors in expanding nodes result from a lower-bound that is
1353 // not contained by an upper-bound.
1354 let (mut lower_bounds
, lower_dup
) = self.collect_concrete_regions(graph
,
1358 let (mut upper_bounds
, upper_dup
) = self.collect_concrete_regions(graph
,
1363 if lower_dup
|| upper_dup
{
1367 // We place free regions first because we are special casing
1368 // SubSupConflict(ReFree, ReFree) when reporting error, and so
1369 // the user will more likely get a specific suggestion.
1370 fn free_regions_first(a
: &RegionAndOrigin
, b
: &RegionAndOrigin
) -> Ordering
{
1371 match (a
.region
, b
.region
) {
1372 (&ReFree(..), &ReFree(..)) => Equal
,
1373 (&ReFree(..), _
) => Less
,
1374 (_
, &ReFree(..)) => Greater
,
1378 lower_bounds
.sort_by(|a
, b
| free_regions_first(a
, b
));
1379 upper_bounds
.sort_by(|a
, b
| free_regions_first(a
, b
));
1381 for lower_bound
in &lower_bounds
{
1382 for upper_bound
in &upper_bounds
{
1383 if !free_regions
.is_subregion_of(self.tcx
, lower_bound
.region
, upper_bound
.region
) {
1384 let origin
= (*self.var_origins
.borrow())[node_idx
.index
as usize].clone();
1385 debug
!("region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
1390 upper_bound
.region
);
1391 errors
.push(SubSupConflict(origin
,
1392 lower_bound
.origin
.clone(),
1394 upper_bound
.origin
.clone(),
1395 upper_bound
.region
));
1401 span_bug
!((*self.var_origins
.borrow())[node_idx
.index
as usize].span(),
1402 "collect_error_for_expanding_node() could not find \
1403 error for var {:?}, lower_bounds={:?}, \
1410 fn collect_concrete_regions(&self,
1411 graph
: &RegionGraph
<'tcx
>,
1412 orig_node_idx
: RegionVid
,
1414 dup_vec
: &mut [u32])
1415 -> (Vec
<RegionAndOrigin
<'tcx
>>, bool
) {
1416 struct WalkState
<'tcx
> {
1417 set
: FnvHashSet
<RegionVid
>,
1418 stack
: Vec
<RegionVid
>,
1419 result
: Vec
<RegionAndOrigin
<'tcx
>>,
1422 let mut state
= WalkState
{
1424 stack
: vec
![orig_node_idx
],
1428 state
.set
.insert(orig_node_idx
);
1430 // to start off the process, walk the source node in the
1431 // direction specified
1432 process_edges(self, &mut state
, graph
, orig_node_idx
, dir
);
1434 while !state
.stack
.is_empty() {
1435 let node_idx
= state
.stack
.pop().unwrap();
1437 // check whether we've visited this node on some previous walk
1438 if dup_vec
[node_idx
.index
as usize] == u32::MAX
{
1439 dup_vec
[node_idx
.index
as usize] = orig_node_idx
.index
;
1440 } else if dup_vec
[node_idx
.index
as usize] != orig_node_idx
.index
{
1441 state
.dup_found
= true;
1444 debug
!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
1448 process_edges(self, &mut state
, graph
, node_idx
, dir
);
1451 let WalkState {result, dup_found, ..}
= state
;
1452 return (result
, dup_found
);
1454 fn process_edges
<'a
, 'gcx
, 'tcx
>(this
: &RegionVarBindings
<'a
, 'gcx
, 'tcx
>,
1455 state
: &mut WalkState
<'tcx
>,
1456 graph
: &RegionGraph
<'tcx
>,
1457 source_vid
: RegionVid
,
1459 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
1461 let source_node_index
= NodeIndex(source_vid
.index
as usize);
1462 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
1464 ConstrainVarSubVar(from_vid
, to_vid
) => {
1465 let opp_vid
= if from_vid
== source_vid
{
1470 if state
.set
.insert(opp_vid
) {
1471 state
.stack
.push(opp_vid
);
1475 ConstrainRegSubVar(region
, _
) |
1476 ConstrainVarSubReg(_
, region
) => {
1477 state
.result
.push(RegionAndOrigin
{
1479 origin
: this
.constraints
.borrow().get(&edge
.data
).unwrap().clone(),
1483 ConstrainRegSubReg(..) => {
1484 panic
!("cannot reach reg-sub-reg edge in region inference \
1492 fn iterate_until_fixed_point
<F
>(&self, tag
: &str, mut body
: F
)
1493 where F
: FnMut(&Constraint
<'tcx
>, &SubregionOrigin
<'tcx
>) -> bool
1495 let mut iteration
= 0;
1496 let mut changed
= true;
1500 debug
!("---- {} Iteration {}{}", "#", tag
, iteration
);
1501 for (constraint
, origin
) in self.constraints
.borrow().iter() {
1502 let edge_changed
= body(constraint
, origin
);
1504 debug
!("Updated due to constraint {:?}", constraint
);
1509 debug
!("---- {} Complete after {} iteration(s)", tag
, iteration
);
1514 fn normalize
<'a
, 'gcx
, 'tcx
>(tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
1515 values
: &Vec
<VarValue
<'tcx
>>,
1516 r
: &'tcx ty
::Region
)
1517 -> &'tcx ty
::Region
{
1519 ty
::ReVar(rid
) => lookup(tcx
, values
, rid
),
1524 fn lookup
<'a
, 'gcx
, 'tcx
>(tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
1525 values
: &Vec
<VarValue
<'tcx
>>,
1527 -> &'tcx ty
::Region
{
1528 match values
[rid
.index
as usize] {
1530 ErrorValue
=> tcx
.mk_region(ReStatic
), // Previously reported error.
1534 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
1535 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1536 write
!(f
, "RegionAndOrigin({:?},{:?})", self.region
, self.origin
)
1540 impl fmt
::Debug
for RegionSnapshot
{
1541 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1542 write
!(f
, "RegionSnapshot(length={},skolemization={})",
1543 self.length
, self.skolemization_count
)
1547 impl<'tcx
> fmt
::Debug
for GenericKind
<'tcx
> {
1548 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1550 GenericKind
::Param(ref p
) => write
!(f
, "{:?}", p
),
1551 GenericKind
::Projection(ref p
) => write
!(f
, "{:?}", p
),
1556 impl<'tcx
> fmt
::Display
for GenericKind
<'tcx
> {
1557 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1559 GenericKind
::Param(ref p
) => write
!(f
, "{}", p
),
1560 GenericKind
::Projection(ref p
) => write
!(f
, "{}", p
),
1565 impl<'a
, 'gcx
, 'tcx
> GenericKind
<'tcx
> {
1566 pub fn to_ty(&self, tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>) -> Ty
<'tcx
> {
1568 GenericKind
::Param(ref p
) => p
.to_ty(tcx
),
1569 GenericKind
::Projection(ref p
) => tcx
.mk_projection(p
.trait_ref
.clone(), p
.item_name
),
1574 impl<'a
, 'gcx
, 'tcx
> VerifyBound
<'tcx
> {
1575 fn for_each_region(&self, f
: &mut FnMut(&'tcx ty
::Region
)) {
1577 &VerifyBound
::AnyRegion(ref rs
) |
1578 &VerifyBound
::AllRegions(ref rs
) => for &r
in rs
{
1582 &VerifyBound
::AnyBound(ref bs
) |
1583 &VerifyBound
::AllBounds(ref bs
) => for b
in bs
{
1584 b
.for_each_region(f
);
1589 pub fn must_hold(&self) -> bool
{
1591 &VerifyBound
::AnyRegion(ref bs
) => bs
.contains(&&ty
::ReStatic
),
1592 &VerifyBound
::AllRegions(ref bs
) => bs
.is_empty(),
1593 &VerifyBound
::AnyBound(ref bs
) => bs
.iter().any(|b
| b
.must_hold()),
1594 &VerifyBound
::AllBounds(ref bs
) => bs
.iter().all(|b
| b
.must_hold()),
1598 pub fn cannot_hold(&self) -> bool
{
1600 &VerifyBound
::AnyRegion(ref bs
) => bs
.is_empty(),
1601 &VerifyBound
::AllRegions(ref bs
) => bs
.contains(&&ty
::ReEmpty
),
1602 &VerifyBound
::AnyBound(ref bs
) => bs
.iter().all(|b
| b
.cannot_hold()),
1603 &VerifyBound
::AllBounds(ref bs
) => bs
.iter().any(|b
| b
.cannot_hold()),
1607 pub fn or(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
1608 if self.must_hold() || vb
.cannot_hold() {
1610 } else if self.cannot_hold() || vb
.must_hold() {
1613 VerifyBound
::AnyBound(vec
![self, vb
])
1617 pub fn and(self, vb
: VerifyBound
<'tcx
>) -> VerifyBound
<'tcx
> {
1618 if self.must_hold() && vb
.must_hold() {
1620 } else if self.cannot_hold() && vb
.cannot_hold() {
1623 VerifyBound
::AllBounds(vec
![self, vb
])
1627 fn is_met(&self, tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
1628 free_regions
: &FreeRegionMap
,
1629 var_values
: &Vec
<VarValue
<'tcx
>>,
1630 min
: &'tcx ty
::Region
)
1633 &VerifyBound
::AnyRegion(ref rs
) =>
1635 .map(|&r
| normalize(tcx
, var_values
, r
))
1636 .any(|r
| free_regions
.is_subregion_of(tcx
, min
, r
)),
1638 &VerifyBound
::AllRegions(ref rs
) =>
1640 .map(|&r
| normalize(tcx
, var_values
, r
))
1641 .all(|r
| free_regions
.is_subregion_of(tcx
, min
, r
)),
1643 &VerifyBound
::AnyBound(ref bs
) =>
1645 .any(|b
| b
.is_met(tcx
, free_regions
, var_values
, min
)),
1647 &VerifyBound
::AllBounds(ref bs
) =>
1649 .all(|b
| b
.is_met(tcx
, free_regions
, var_values
, min
)),