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::Verify
::*;
15 pub use self::UndoLogEntry
::*;
16 pub use self::CombineMapType
::*;
17 pub use self::RegionResolutionError
::*;
18 pub use self::VarValue
::*;
19 use self::Classification
::*;
21 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable}
;
23 use rustc_data_structures
::graph
::{self, Direction, NodeIndex}
;
24 use middle
::free_region
::FreeRegionMap
;
26 use middle
::ty
::{self, Ty}
;
27 use middle
::ty
::{BoundRegion, FreeRegion, Region, RegionVid}
;
28 use middle
::ty
::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound}
;
29 use middle
::ty
::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh}
;
30 use middle
::ty_relate
::RelateResult
;
31 use util
::common
::indenter
;
32 use util
::nodemap
::{FnvHashMap, FnvHashSet}
;
34 use std
::cell
::{Cell, RefCell}
;
35 use std
::cmp
::Ordering
::{self, Less, Greater, Equal}
;
37 use std
::iter
::repeat
;
43 // A constraint that influences the inference process.
44 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
46 // One region variable is subregion of another
47 ConstrainVarSubVar(RegionVid
, RegionVid
),
49 // Concrete region is subregion of region variable
50 ConstrainRegSubVar(Region
, RegionVid
),
52 // Region variable is subregion of concrete region
53 ConstrainVarSubReg(RegionVid
, Region
),
56 // Something we have to verify after region inference is done, but
57 // which does not directly influence the inference process
58 pub enum Verify
<'tcx
> {
59 // VerifyRegSubReg(a, b): Verify that `a <= b`. Neither `a` nor
60 // `b` are inference variables.
61 VerifyRegSubReg(SubregionOrigin
<'tcx
>, Region
, Region
),
63 // VerifyGenericBound(T, _, R, RS): The parameter type `T` (or
64 // associated type) must outlive the region `R`. `T` is known to
65 // outlive `RS`. Therefore verify that `R <= RS[i]` for some
66 // `i`. Inference variables may be involved (but this verification
67 // step doesn't influence inference).
68 VerifyGenericBound(GenericKind
<'tcx
>, SubregionOrigin
<'tcx
>, Region
, Vec
<Region
>),
71 #[derive(Clone, PartialEq, Eq)]
72 pub enum GenericKind
<'tcx
> {
74 Projection(ty
::ProjectionTy
<'tcx
>),
77 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
78 pub struct TwoRegions
{
83 #[derive(Copy, Clone, PartialEq)]
84 pub enum UndoLogEntry
{
88 AddConstraint(Constraint
),
90 AddGiven(ty
::FreeRegion
, ty
::RegionVid
),
91 AddCombination(CombineMapType
, TwoRegions
)
94 #[derive(Copy, Clone, PartialEq)]
95 pub enum CombineMapType
{
99 #[derive(Clone, Debug)]
100 pub enum RegionResolutionError
<'tcx
> {
101 /// `ConcreteFailure(o, a, b)`:
103 /// `o` requires that `a <= b`, but this does not hold
104 ConcreteFailure(SubregionOrigin
<'tcx
>, Region
, Region
),
106 /// `GenericBoundFailure(p, s, a, bs)
108 /// The parameter/associated-type `p` must be known to outlive the lifetime
109 /// `a`, but it is only known to outlive `bs` (and none of the
110 /// regions in `bs` outlive `a`).
111 GenericBoundFailure(SubregionOrigin
<'tcx
>, GenericKind
<'tcx
>, Region
, Vec
<Region
>),
113 /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
115 /// Could not infer a value for `v` because `sub_r <= v` (due to
116 /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
117 /// `sub_r <= sup_r` does not hold.
118 SubSupConflict(RegionVariableOrigin
,
119 SubregionOrigin
<'tcx
>, Region
,
120 SubregionOrigin
<'tcx
>, Region
),
122 /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
124 /// Could not infer a value for `v` because `v <= r1` (due to
125 /// `origin1`) and `v <= r2` (due to `origin2`) and
126 /// `r1` and `r2` have no intersection.
127 SupSupConflict(RegionVariableOrigin
,
128 SubregionOrigin
<'tcx
>, Region
,
129 SubregionOrigin
<'tcx
>, Region
),
131 /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
132 /// more specific errors message by suggesting to the user where they
133 /// should put a lifetime. In those cases we process and put those errors
134 /// into `ProcessedErrors` before we do any reporting.
135 ProcessedErrors(Vec
<RegionVariableOrigin
>,
136 Vec
<(TypeTrace
<'tcx
>, ty
::type_err
<'tcx
>)>,
140 /// SameRegions is used to group regions that we think are the same and would
141 /// like to indicate so to the user.
142 /// For example, the following function
144 /// struct Foo { bar: int }
145 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
149 /// would report an error because we expect 'a and 'b to match, and so we group
150 /// 'a and 'b together inside a SameRegions struct
151 #[derive(Clone, Debug)]
152 pub struct SameRegions
{
153 pub scope_id
: ast
::NodeId
,
154 pub regions
: Vec
<BoundRegion
>
158 pub fn contains(&self, other
: &BoundRegion
) -> bool
{
159 self.regions
.contains(other
)
162 pub fn push(&mut self, other
: BoundRegion
) {
163 self.regions
.push(other
);
167 pub type CombineMap
= FnvHashMap
<TwoRegions
, RegionVid
>;
169 pub struct RegionVarBindings
<'a
, 'tcx
: 'a
> {
170 tcx
: &'a ty
::ctxt
<'tcx
>,
171 var_origins
: RefCell
<Vec
<RegionVariableOrigin
>>,
173 // Constraints of the form `A <= B` introduced by the region
174 // checker. Here at least one of `A` and `B` must be a region
176 constraints
: RefCell
<FnvHashMap
<Constraint
, SubregionOrigin
<'tcx
>>>,
178 // A "verify" is something that we need to verify after inference is
179 // done, but which does not directly affect inference in any way.
181 // An example is a `A <= B` where neither `A` nor `B` are
182 // inference variables.
183 verifys
: RefCell
<Vec
<Verify
<'tcx
>>>,
185 // A "given" is a relationship that is known to hold. In particular,
186 // we often know from closure fn signatures that a particular free
187 // region must be a subregion of a region variable:
189 // foo.iter().filter(<'a> |x: &'a &'b T| ...)
191 // In situations like this, `'b` is in fact a region variable
192 // introduced by the call to `iter()`, and `'a` is a bound region
193 // on the closure (as indicated by the `<'a>` prefix). If we are
194 // naive, we wind up inferring that `'b` must be `'static`,
195 // because we require that it be greater than `'a` and we do not
196 // know what `'a` is precisely.
198 // This hashmap is used to avoid that naive scenario. Basically we
199 // record the fact that `'a <= 'b` is implied by the fn signature,
200 // and then ignore the constraint when solving equations. This is
201 // a bit of a hack but seems to work.
202 givens
: RefCell
<FnvHashSet
<(ty
::FreeRegion
, ty
::RegionVid
)>>,
204 lubs
: RefCell
<CombineMap
>,
205 glbs
: RefCell
<CombineMap
>,
206 skolemization_count
: Cell
<u32>,
207 bound_count
: Cell
<u32>,
209 // The undo log records actions that might later be undone.
211 // Note: when the undo_log is empty, we are not actively
212 // snapshotting. When the `start_snapshot()` method is called, we
213 // push an OpenSnapshot entry onto the list to indicate that we
214 // are now actively snapshotting. The reason for this is that
215 // otherwise we end up adding entries for things like the lower
216 // bound on a variable and so forth, which can never be rolled
218 undo_log
: RefCell
<Vec
<UndoLogEntry
>>,
220 // This contains the results of inference. It begins as an empty
221 // option and only acquires a value after inference is complete.
222 values
: RefCell
<Option
<Vec
<VarValue
>>>,
226 pub struct RegionSnapshot
{
228 skolemization_count
: u32,
231 impl<'a
, 'tcx
> RegionVarBindings
<'a
, 'tcx
> {
232 pub fn new(tcx
: &'a ty
::ctxt
<'tcx
>) -> RegionVarBindings
<'a
, 'tcx
> {
235 var_origins
: RefCell
::new(Vec
::new()),
236 values
: RefCell
::new(None
),
237 constraints
: RefCell
::new(FnvHashMap()),
238 verifys
: RefCell
::new(Vec
::new()),
239 givens
: RefCell
::new(FnvHashSet()),
240 lubs
: RefCell
::new(FnvHashMap()),
241 glbs
: RefCell
::new(FnvHashMap()),
242 skolemization_count
: Cell
::new(0),
243 bound_count
: Cell
::new(0),
244 undo_log
: RefCell
::new(Vec
::new())
248 fn in_snapshot(&self) -> bool
{
249 !self.undo_log
.borrow().is_empty()
252 pub fn start_snapshot(&self) -> RegionSnapshot
{
253 let length
= self.undo_log
.borrow().len();
254 debug
!("RegionVarBindings: start_snapshot({})", length
);
255 self.undo_log
.borrow_mut().push(OpenSnapshot
);
256 RegionSnapshot { length: length, skolemization_count: self.skolemization_count.get() }
259 pub fn commit(&self, snapshot
: RegionSnapshot
) {
260 debug
!("RegionVarBindings: commit({})", snapshot
.length
);
261 assert
!(self.undo_log
.borrow().len() > snapshot
.length
);
262 assert
!((*self.undo_log
.borrow())[snapshot
.length
] == OpenSnapshot
);
264 let mut undo_log
= self.undo_log
.borrow_mut();
265 if snapshot
.length
== 0 {
266 undo_log
.truncate(0);
268 (*undo_log
)[snapshot
.length
] = CommitedSnapshot
;
270 self.skolemization_count
.set(snapshot
.skolemization_count
);
273 pub fn rollback_to(&self, snapshot
: RegionSnapshot
) {
274 debug
!("RegionVarBindings: rollback_to({:?})", snapshot
);
275 let mut undo_log
= self.undo_log
.borrow_mut();
276 assert
!(undo_log
.len() > snapshot
.length
);
277 assert
!((*undo_log
)[snapshot
.length
] == OpenSnapshot
);
278 while undo_log
.len() > snapshot
.length
+ 1 {
279 match undo_log
.pop().unwrap() {
281 panic
!("Failure to observe stack discipline");
283 CommitedSnapshot
=> { }
285 let mut var_origins
= self.var_origins
.borrow_mut();
286 var_origins
.pop().unwrap();
287 assert_eq
!(var_origins
.len(), vid
.index
as usize);
289 AddConstraint(ref constraint
) => {
290 self.constraints
.borrow_mut().remove(constraint
);
292 AddVerify(index
) => {
293 self.verifys
.borrow_mut().pop();
294 assert_eq
!(self.verifys
.borrow().len(), index
);
296 AddGiven(sub
, sup
) => {
297 self.givens
.borrow_mut().remove(&(sub
, sup
));
299 AddCombination(Glb
, ref regions
) => {
300 self.glbs
.borrow_mut().remove(regions
);
302 AddCombination(Lub
, ref regions
) => {
303 self.lubs
.borrow_mut().remove(regions
);
307 let c
= undo_log
.pop().unwrap();
308 assert
!(c
== OpenSnapshot
);
309 self.skolemization_count
.set(snapshot
.skolemization_count
);
312 pub fn num_vars(&self) -> u32 {
313 let len
= self.var_origins
.borrow().len();
314 // enforce no overflow
315 assert
!(len
as u32 as usize == len
);
319 pub fn new_region_var(&self, origin
: RegionVariableOrigin
) -> RegionVid
{
320 let id
= self.num_vars();
321 self.var_origins
.borrow_mut().push(origin
.clone());
322 let vid
= RegionVid { index: id }
;
323 if self.in_snapshot() {
324 self.undo_log
.borrow_mut().push(AddVar(vid
));
326 debug
!("created new region variable {:?} with origin {:?}",
331 /// Creates a new skolemized region. Skolemized regions are fresh
332 /// regions used when performing higher-ranked computations. They
333 /// must be used in a very particular way and are never supposed
334 /// to "escape" out into error messages or the code at large.
336 /// The idea is to always create a snapshot. Skolemized regions
337 /// can be created in the context of this snapshot, but once the
338 /// snapshot is committed or rolled back, their numbers will be
339 /// recycled, so you must be finished with them. See the extensive
340 /// comments in `higher_ranked.rs` to see how it works (in
341 /// particular, the subtyping comparison).
343 /// The `snapshot` argument to this function is not really used;
344 /// it's just there to make it explicit which snapshot bounds the
345 /// skolemized region that results.
346 pub fn new_skolemized(&self, br
: ty
::BoundRegion
, snapshot
: &RegionSnapshot
) -> Region
{
347 assert
!(self.in_snapshot());
348 assert
!(self.undo_log
.borrow()[snapshot
.length
] == OpenSnapshot
);
350 let sc
= self.skolemization_count
.get();
351 self.skolemization_count
.set(sc
+ 1);
352 ReInfer(ReSkolemized(sc
, br
))
355 pub fn new_bound(&self, debruijn
: ty
::DebruijnIndex
) -> Region
{
356 // Creates a fresh bound variable for use in GLB computations.
357 // See discussion of GLB computation in the large comment at
358 // the top of this file for more details.
360 // This computation is potentially wrong in the face of
361 // rollover. It's conceivable, if unlikely, that one might
362 // wind up with accidental capture for nested functions in
363 // that case, if the outer function had bound regions created
364 // a very long time before and the inner function somehow
365 // wound up rolling over such that supposedly fresh
366 // identifiers were in fact shadowed. For now, we just assert
367 // that there is no rollover -- eventually we should try to be
368 // robust against this possibility, either by checking the set
369 // of bound identifiers that appear in a given expression and
370 // ensure that we generate one that is distinct, or by
371 // changing the representation of bound regions in a fn
374 let sc
= self.bound_count
.get();
375 self.bound_count
.set(sc
+ 1);
377 if sc
>= self.bound_count
.get() {
378 self.tcx
.sess
.bug("rollover in RegionInference new_bound()");
381 ReLateBound(debruijn
, BrFresh(sc
))
384 fn values_are_none(&self) -> bool
{
385 self.values
.borrow().is_none()
388 fn add_constraint(&self,
389 constraint
: Constraint
,
390 origin
: SubregionOrigin
<'tcx
>) {
391 // cannot add constraints once regions are resolved
392 assert
!(self.values_are_none());
394 debug
!("RegionVarBindings: add_constraint({:?})",
397 if self.constraints
.borrow_mut().insert(constraint
, origin
).is_none() {
398 if self.in_snapshot() {
399 self.undo_log
.borrow_mut().push(AddConstraint(constraint
));
405 verify
: Verify
<'tcx
>) {
406 // cannot add verifys once regions are resolved
407 assert
!(self.values_are_none());
409 debug
!("RegionVarBindings: add_verify({:?})",
412 let mut verifys
= self.verifys
.borrow_mut();
413 let index
= verifys
.len();
414 verifys
.push(verify
);
415 if self.in_snapshot() {
416 self.undo_log
.borrow_mut().push(AddVerify(index
));
420 pub fn add_given(&self,
422 sup
: ty
::RegionVid
) {
423 // cannot add givens once regions are resolved
424 assert
!(self.values_are_none());
426 let mut givens
= self.givens
.borrow_mut();
427 if givens
.insert((sub
, sup
)) {
428 debug
!("add_given({:?} <= {:?})",
432 self.undo_log
.borrow_mut().push(AddGiven(sub
, sup
));
436 pub fn make_eqregion(&self,
437 origin
: SubregionOrigin
<'tcx
>,
441 // Eventually, it would be nice to add direct support for
443 self.make_subregion(origin
.clone(), sub
, sup
);
444 self.make_subregion(origin
, sup
, sub
);
448 pub fn make_subregion(&self,
449 origin
: SubregionOrigin
<'tcx
>,
452 // cannot add constraints once regions are resolved
453 assert
!(self.values_are_none());
455 debug
!("RegionVarBindings: make_subregion({:?}, {:?}) due to {:?}",
461 (ReEarlyBound(..), ReEarlyBound(..)) => {
462 // This case is used only to make sure that explicitly-specified
463 // `Self` types match the real self type in implementations.
465 // FIXME(NDM) -- we really shouldn't be comparing bound things
466 self.add_verify(VerifyRegSubReg(origin
, sub
, sup
));
468 (ReEarlyBound(..), _
) |
469 (ReLateBound(..), _
) |
470 (_
, ReEarlyBound(..)) |
471 (_
, ReLateBound(..)) => {
472 self.tcx
.sess
.span_bug(
474 &format
!("cannot relate bound region: {:?} <= {:?}",
479 // all regions are subregions of static, so we can ignore this
481 (ReInfer(ReVar(sub_id
)), ReInfer(ReVar(sup_id
))) => {
482 self.add_constraint(ConstrainVarSubVar(sub_id
, sup_id
), origin
);
484 (r
, ReInfer(ReVar(sup_id
))) => {
485 self.add_constraint(ConstrainRegSubVar(r
, sup_id
), origin
);
487 (ReInfer(ReVar(sub_id
)), r
) => {
488 self.add_constraint(ConstrainVarSubReg(sub_id
, r
), origin
);
491 self.add_verify(VerifyRegSubReg(origin
, sub
, sup
));
496 /// See `Verify::VerifyGenericBound`
497 pub fn verify_generic_bound(&self,
498 origin
: SubregionOrigin
<'tcx
>,
499 kind
: GenericKind
<'tcx
>,
502 self.add_verify(VerifyGenericBound(kind
, origin
, sub
, sups
));
505 pub fn lub_regions(&self,
506 origin
: SubregionOrigin
<'tcx
>,
510 // cannot add constraints once regions are resolved
511 assert
!(self.values_are_none());
513 debug
!("RegionVarBindings: lub_regions({:?}, {:?})",
517 (ReStatic
, _
) | (_
, ReStatic
) => {
518 ReStatic
// nothing lives longer than static
523 Lub
, a
, b
, origin
.clone(),
525 this
.make_subregion(origin
.clone(), old_r
, new_r
))
530 pub fn glb_regions(&self,
531 origin
: SubregionOrigin
<'tcx
>,
535 // cannot add constraints once regions are resolved
536 assert
!(self.values_are_none());
538 debug
!("RegionVarBindings: glb_regions({:?}, {:?})",
542 (ReStatic
, r
) | (r
, ReStatic
) => {
543 // static lives longer than everything else
549 Glb
, a
, b
, origin
.clone(),
551 this
.make_subregion(origin
.clone(), new_r
, old_r
))
556 pub fn resolve_var(&self, rid
: RegionVid
) -> ty
::Region
{
557 match *self.values
.borrow() {
559 self.tcx
.sess
.span_bug(
560 (*self.var_origins
.borrow())[rid
.index
as usize].span(),
561 "attempt to resolve region variable before values have \
564 Some(ref values
) => {
565 let r
= lookup(values
, rid
);
566 debug
!("resolve_var({:?}) = {:?}", rid
, r
);
572 fn combine_map(&self, t
: CombineMapType
)
573 -> &RefCell
<CombineMap
> {
580 pub fn combine_vars
<F
>(&self,
584 origin
: SubregionOrigin
<'tcx
>,
587 F
: FnMut(&RegionVarBindings
<'a
, 'tcx
>, Region
, Region
),
589 let vars
= TwoRegions { a: a, b: b }
;
590 match self.combine_map(t
).borrow().get(&vars
) {
592 return ReInfer(ReVar(c
));
596 let c
= self.new_region_var(MiscVariable(origin
.span()));
597 self.combine_map(t
).borrow_mut().insert(vars
, c
);
598 if self.in_snapshot() {
599 self.undo_log
.borrow_mut().push(AddCombination(t
, vars
));
601 relate(self, a
, ReInfer(ReVar(c
)));
602 relate(self, b
, ReInfer(ReVar(c
)));
603 debug
!("combine_vars() c={:?}", c
);
607 pub fn vars_created_since_snapshot(&self, mark
: &RegionSnapshot
)
610 self.undo_log
.borrow()[mark
.length
..]
612 .filter_map(|&elt
| match elt
{
613 AddVar(vid
) => Some(vid
),
619 /// Computes all regions that have been related to `r0` in any way since the mark `mark` was
620 /// made---`r0` itself will be the first entry. This is used when checking whether skolemized
621 /// regions are being improperly related to other regions.
622 pub fn tainted(&self, mark
: &RegionSnapshot
, r0
: Region
) -> Vec
<Region
> {
623 debug
!("tainted(mark={:?}, r0={:?})", mark
, r0
);
624 let _indenter
= indenter();
626 // `result_set` acts as a worklist: we explore all outgoing
627 // edges and add any new regions we find to result_set. This
628 // is not a terribly efficient implementation.
629 let mut result_set
= vec
!(r0
);
630 let mut result_index
= 0;
631 while result_index
< result_set
.len() {
632 // nb: can't use usize::range() here because result_set grows
633 let r
= result_set
[result_index
];
634 debug
!("result_index={}, r={:?}", result_index
, r
);
637 self.undo_log
.borrow()[mark
.length
..].iter()
640 &AddConstraint(ConstrainVarSubVar(a
, b
)) => {
641 consider_adding_bidirectional_edges(
643 ReInfer(ReVar(a
)), ReInfer(ReVar(b
)));
645 &AddConstraint(ConstrainRegSubVar(a
, b
)) => {
646 consider_adding_bidirectional_edges(
648 a
, ReInfer(ReVar(b
)));
650 &AddConstraint(ConstrainVarSubReg(a
, b
)) => {
651 consider_adding_bidirectional_edges(
653 ReInfer(ReVar(a
)), b
);
656 consider_adding_bidirectional_edges(
658 ReFree(a
), ReInfer(ReVar(b
)));
661 match (*self.verifys
.borrow())[i
] {
662 VerifyRegSubReg(_
, a
, b
) => {
663 consider_adding_bidirectional_edges(
667 VerifyGenericBound(_
, _
, a
, ref bs
) => {
669 consider_adding_bidirectional_edges(
676 &AddCombination(..) |
679 &CommitedSnapshot
=> {
689 fn consider_adding_bidirectional_edges(result_set
: &mut Vec
<Region
>,
693 consider_adding_directed_edge(result_set
, r
, r1
, r2
);
694 consider_adding_directed_edge(result_set
, r
, r2
, r1
);
697 fn consider_adding_directed_edge(result_set
: &mut Vec
<Region
>,
702 // Clearly, this is potentially inefficient.
703 if !result_set
.iter().any(|x
| *x
== r2
) {
710 /// This function performs the actual region resolution. It must be
711 /// called after all constraints have been added. It performs a
712 /// fixed-point iteration to find region values which satisfy all
713 /// constraints, assuming such values can be found; if they cannot,
714 /// errors are reported.
715 pub fn resolve_regions(&self,
716 free_regions
: &FreeRegionMap
,
717 subject_node
: ast
::NodeId
)
718 -> Vec
<RegionResolutionError
<'tcx
>>
720 debug
!("RegionVarBindings: resolve_regions()");
721 let mut errors
= vec
!();
722 let v
= self.infer_variable_values(free_regions
, &mut errors
, subject_node
);
723 *self.values
.borrow_mut() = Some(v
);
727 fn lub_concrete_regions(&self, free_regions
: &FreeRegionMap
, a
: Region
, b
: Region
) -> Region
{
729 (ReLateBound(..), _
) |
730 (_
, ReLateBound(..)) |
731 (ReEarlyBound(..), _
) |
732 (_
, ReEarlyBound(..)) => {
734 &format
!("cannot relate bound region: LUB({:?}, {:?})",
739 (ReStatic
, _
) | (_
, ReStatic
) => {
740 ReStatic
// nothing lives longer than static
743 (ReEmpty
, r
) | (r
, ReEmpty
) => {
744 r
// everything lives longer than empty
747 (ReInfer(ReVar(v_id
)), _
) | (_
, ReInfer(ReVar(v_id
))) => {
748 self.tcx
.sess
.span_bug(
749 (*self.var_origins
.borrow())[v_id
.index
as usize].span(),
750 &format
!("lub_concrete_regions invoked with \
751 non-concrete regions: {:?}, {:?}",
756 (ReFree(ref fr
), ReScope(s_id
)) |
757 (ReScope(s_id
), ReFree(ref fr
)) => {
759 // A "free" region can be interpreted as "some region
760 // at least as big as the block fr.scope_id". So, we can
761 // reasonably compare free regions and scopes:
762 let fr_scope
= fr
.scope
.to_code_extent();
763 let r_id
= self.tcx
.region_maps
.nearest_common_ancestor(fr_scope
, s_id
);
765 if r_id
== fr_scope
{
766 // if the free region's scope `fr.scope_id` is bigger than
767 // the scope region `s_id`, then the LUB is the free
771 // otherwise, we don't know what the free region is,
772 // so we must conservatively say the LUB is static:
777 (ReScope(a_id
), ReScope(b_id
)) => {
778 // The region corresponding to an outer block is a
779 // subtype of the region corresponding to an inner
781 ReScope(self.tcx
.region_maps
.nearest_common_ancestor(a_id
, b_id
))
784 (ReFree(ref a_fr
), ReFree(ref b_fr
)) => {
785 self.lub_free_regions(free_regions
, a_fr
, b_fr
)
788 // For these types, we cannot define any additional
790 (ReInfer(ReSkolemized(..)), _
) |
791 (_
, ReInfer(ReSkolemized(..))) => {
792 if a
== b {a}
else {ReStatic}
797 /// Computes a region that encloses both free region arguments. Guarantee that if the same two
798 /// regions are given as argument, in any order, a consistent result is returned.
799 fn lub_free_regions(&self,
800 free_regions
: &FreeRegionMap
,
805 return match a
.cmp(b
) {
806 Less
=> helper(self, free_regions
, a
, b
),
807 Greater
=> helper(self, free_regions
, b
, a
),
808 Equal
=> ty
::ReFree(*a
)
811 fn helper(_this
: &RegionVarBindings
,
812 free_regions
: &FreeRegionMap
,
814 b
: &FreeRegion
) -> ty
::Region
816 if free_regions
.sub_free_region(*a
, *b
) {
818 } else if free_regions
.sub_free_region(*b
, *a
) {
826 fn glb_concrete_regions(&self,
827 free_regions
: &FreeRegionMap
,
830 -> RelateResult
<'tcx
, Region
>
832 debug
!("glb_concrete_regions({:?}, {:?})", a
, b
);
834 (ReLateBound(..), _
) |
835 (_
, ReLateBound(..)) |
836 (ReEarlyBound(..), _
) |
837 (_
, ReEarlyBound(..)) => {
839 &format
!("cannot relate bound region: GLB({:?}, {:?})",
844 (ReStatic
, r
) | (r
, ReStatic
) => {
845 // static lives longer than everything else
849 (ReEmpty
, _
) | (_
, ReEmpty
) => {
850 // nothing lives shorter than everything else
854 (ReInfer(ReVar(v_id
)), _
) |
855 (_
, ReInfer(ReVar(v_id
))) => {
856 self.tcx
.sess
.span_bug(
857 (*self.var_origins
.borrow())[v_id
.index
as usize].span(),
858 &format
!("glb_concrete_regions invoked with \
859 non-concrete regions: {:?}, {:?}",
864 (ReFree(ref fr
), ReScope(s_id
)) |
865 (ReScope(s_id
), ReFree(ref fr
)) => {
866 let s
= ReScope(s_id
);
867 // Free region is something "at least as big as
868 // `fr.scope_id`." If we find that the scope `fr.scope_id` is bigger
869 // than the scope `s_id`, then we can say that the GLB
870 // is the scope `s_id`. Otherwise, as we do not know
871 // big the free region is precisely, the GLB is undefined.
872 let fr_scope
= fr
.scope
.to_code_extent();
873 if self.tcx
.region_maps
.nearest_common_ancestor(fr_scope
, s_id
) == fr_scope
{
876 Err(ty
::terr_regions_no_overlap(b
, a
))
880 (ReScope(a_id
), ReScope(b_id
)) => {
881 self.intersect_scopes(a
, b
, a_id
, b_id
)
884 (ReFree(ref a_fr
), ReFree(ref b_fr
)) => {
885 self.glb_free_regions(free_regions
, a_fr
, b_fr
)
888 // For these types, we cannot define any additional
890 (ReInfer(ReSkolemized(..)), _
) |
891 (_
, ReInfer(ReSkolemized(..))) => {
895 Err(ty
::terr_regions_no_overlap(b
, a
))
901 /// Computes a region that is enclosed by both free region arguments, if any. Guarantees that
902 /// if the same two regions are given as argument, in any order, a consistent result is
904 fn glb_free_regions(&self,
905 free_regions
: &FreeRegionMap
,
908 -> RelateResult
<'tcx
, ty
::Region
>
910 return match a
.cmp(b
) {
911 Less
=> helper(self, free_regions
, a
, b
),
912 Greater
=> helper(self, free_regions
, b
, a
),
913 Equal
=> Ok(ty
::ReFree(*a
))
916 fn helper
<'a
, 'tcx
>(this
: &RegionVarBindings
<'a
, 'tcx
>,
917 free_regions
: &FreeRegionMap
,
919 b
: &FreeRegion
) -> RelateResult
<'tcx
, ty
::Region
>
921 if free_regions
.sub_free_region(*a
, *b
) {
923 } else if free_regions
.sub_free_region(*b
, *a
) {
926 this
.intersect_scopes(ty
::ReFree(*a
), ty
::ReFree(*b
),
927 a
.scope
.to_code_extent(),
928 b
.scope
.to_code_extent())
933 fn intersect_scopes(&self,
934 region_a
: ty
::Region
,
935 region_b
: ty
::Region
,
936 scope_a
: region
::CodeExtent
,
937 scope_b
: region
::CodeExtent
)
938 -> RelateResult
<'tcx
, Region
>
940 // We want to generate the intersection of two
941 // scopes or two free regions. So, if one of
942 // these scopes is a subscope of the other, return
943 // it. Otherwise fail.
944 debug
!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
945 scope_a
, scope_b
, region_a
, region_b
);
946 let r_id
= self.tcx
.region_maps
.nearest_common_ancestor(scope_a
, scope_b
);
949 } else if r_id
== scope_b
{
952 Err(ty
::terr_regions_no_overlap(region_a
, region_b
))
957 // ______________________________________________________________________
959 #[derive(Copy, Clone, PartialEq, Debug)]
960 enum Classification { Expanding, Contracting }
962 #[derive(Copy, Clone, Debug)]
963 pub enum VarValue { NoValue, Value(Region), ErrorValue }
966 classification
: Classification
,
970 struct RegionAndOrigin
<'tcx
> {
972 origin
: SubregionOrigin
<'tcx
>,
975 type RegionGraph
= graph
::Graph
<(), Constraint
>;
977 impl<'a
, 'tcx
> RegionVarBindings
<'a
, 'tcx
> {
978 fn infer_variable_values(&self,
979 free_regions
: &FreeRegionMap
,
980 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
981 subject
: ast
::NodeId
) -> Vec
<VarValue
>
983 let mut var_data
= self.construct_var_data();
985 // Dorky hack to cause `dump_constraints` to only get called
986 // if debug mode is enabled:
987 debug
!("----() End constraint listing (subject={}) {:?}---",
988 subject
, self.dump_constraints(subject
));
989 graphviz
::maybe_print_constraints_for(self, subject
);
991 let graph
= self.construct_graph();
992 self.expand_givens(&graph
);
993 self.expansion(free_regions
, &mut var_data
);
994 self.contraction(free_regions
, &mut var_data
);
996 self.extract_values_and_collect_conflicts(free_regions
,
1000 self.collect_concrete_region_errors(free_regions
, &values
, errors
);
1004 fn construct_var_data(&self) -> Vec
<VarData
> {
1005 (0..self.num_vars() as usize).map(|_
| {
1007 // All nodes are initially classified as contracting; during
1008 // the expansion phase, we will shift the classification for
1009 // those nodes that have a concrete region predecessor to
1011 classification
: Contracting
,
1017 fn dump_constraints(&self, subject
: ast
::NodeId
) {
1018 debug
!("----() Start constraint listing (subject={}) ()----", subject
);
1019 for (idx
, (constraint
, _
)) in self.constraints
.borrow().iter().enumerate() {
1020 debug
!("Constraint {} => {:?}", idx
, constraint
);
1024 fn expand_givens(&self, graph
: &RegionGraph
) {
1025 // Givens are a kind of horrible hack to account for
1026 // constraints like 'c <= '0 that are known to hold due to
1027 // closure signatures (see the comment above on the `givens`
1028 // field). They should go away. But until they do, the role
1029 // of this fn is to account for the transitive nature:
1035 let mut givens
= self.givens
.borrow_mut();
1036 let seeds
: Vec
<_
> = givens
.iter().cloned().collect();
1037 for (fr
, vid
) in seeds
{
1038 let seed_index
= NodeIndex(vid
.index
as usize);
1039 for succ_index
in graph
.depth_traverse(seed_index
) {
1040 let succ_index
= succ_index
.0 as u32;
1041 if succ_index
< self.num_vars() {
1042 let succ_vid
= RegionVid { index: succ_index }
;
1043 givens
.insert((fr
, succ_vid
));
1049 fn expansion(&self, free_regions
: &FreeRegionMap
, var_data
: &mut [VarData
]) {
1050 self.iterate_until_fixed_point("Expansion", |constraint
| {
1051 debug
!("expansion: constraint={:?} origin={:?}",
1053 self.constraints
.borrow()
1058 ConstrainRegSubVar(a_region
, b_vid
) => {
1059 let b_data
= &mut var_data
[b_vid
.index
as usize];
1060 self.expand_node(free_regions
, a_region
, b_vid
, b_data
)
1062 ConstrainVarSubVar(a_vid
, b_vid
) => {
1063 match var_data
[a_vid
.index
as usize].value
{
1064 NoValue
| ErrorValue
=> false,
1065 Value(a_region
) => {
1066 let b_node
= &mut var_data
[b_vid
.index
as usize];
1067 self.expand_node(free_regions
, a_region
, b_vid
, b_node
)
1071 ConstrainVarSubReg(..) => {
1072 // This is a contraction constraint. Ignore it.
1079 fn expand_node(&self,
1080 free_regions
: &FreeRegionMap
,
1083 b_data
: &mut VarData
)
1086 debug
!("expand_node({:?}, {:?} == {:?})",
1091 // Check if this relationship is implied by a given.
1094 if self.givens
.borrow().contains(&(fr
, b_vid
)) {
1102 b_data
.classification
= Expanding
;
1103 match b_data
.value
{
1105 debug
!("Setting initial value of {:?} to {:?}",
1108 b_data
.value
= Value(a_region
);
1112 Value(cur_region
) => {
1113 let lub
= self.lub_concrete_regions(free_regions
, a_region
, cur_region
);
1114 if lub
== cur_region
{
1118 debug
!("Expanding value of {:?} from {:?} to {:?}",
1123 b_data
.value
= Value(lub
);
1133 fn contraction(&self,
1134 free_regions
: &FreeRegionMap
,
1135 var_data
: &mut [VarData
]) {
1136 self.iterate_until_fixed_point("Contraction", |constraint
| {
1137 debug
!("contraction: constraint={:?} origin={:?}",
1139 self.constraints
.borrow()
1144 ConstrainRegSubVar(..) => {
1145 // This is an expansion constraint. Ignore.
1148 ConstrainVarSubVar(a_vid
, b_vid
) => {
1149 match var_data
[b_vid
.index
as usize].value
{
1150 NoValue
| ErrorValue
=> false,
1151 Value(b_region
) => {
1152 let a_data
= &mut var_data
[a_vid
.index
as usize];
1153 self.contract_node(free_regions
, a_vid
, a_data
, b_region
)
1157 ConstrainVarSubReg(a_vid
, b_region
) => {
1158 let a_data
= &mut var_data
[a_vid
.index
as usize];
1159 self.contract_node(free_regions
, a_vid
, a_data
, b_region
)
1165 fn contract_node(&self,
1166 free_regions
: &FreeRegionMap
,
1168 a_data
: &mut VarData
,
1171 debug
!("contract_node({:?} == {:?}/{:?}, {:?})",
1172 a_vid
, a_data
.value
,
1173 a_data
.classification
, b_region
);
1175 return match a_data
.value
{
1177 assert_eq
!(a_data
.classification
, Contracting
);
1178 a_data
.value
= Value(b_region
);
1182 ErrorValue
=> false, // no change
1184 Value(a_region
) => {
1185 match a_data
.classification
{
1187 check_node(self, free_regions
, a_vid
, a_data
, a_region
, b_region
),
1189 adjust_node(self, free_regions
, a_vid
, a_data
, a_region
, b_region
),
1194 fn check_node(this
: &RegionVarBindings
,
1195 free_regions
: &FreeRegionMap
,
1197 a_data
: &mut VarData
,
1202 if !free_regions
.is_subregion_of(this
.tcx
, a_region
, b_region
) {
1203 debug
!("Setting {:?} to ErrorValue: {:?} not subregion of {:?}",
1207 a_data
.value
= ErrorValue
;
1212 fn adjust_node(this
: &RegionVarBindings
,
1213 free_regions
: &FreeRegionMap
,
1215 a_data
: &mut VarData
,
1219 match this
.glb_concrete_regions(free_regions
, a_region
, b_region
) {
1221 if glb
== a_region
{
1224 debug
!("Contracting value of {:?} from {:?} to {:?}",
1228 a_data
.value
= Value(glb
);
1233 debug
!("Setting {:?} to ErrorValue: no glb of {:?}, {:?}",
1237 a_data
.value
= ErrorValue
;
1244 fn collect_concrete_region_errors(&self,
1245 free_regions
: &FreeRegionMap
,
1246 values
: &Vec
<VarValue
>,
1247 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1249 let mut reg_reg_dups
= FnvHashSet();
1250 for verify
in self.verifys
.borrow().iter() {
1252 VerifyRegSubReg(ref origin
, sub
, sup
) => {
1253 if free_regions
.is_subregion_of(self.tcx
, sub
, sup
) {
1257 if !reg_reg_dups
.insert((sub
, sup
)) {
1261 debug
!("ConcreteFailure: !(sub <= sup): sub={:?}, sup={:?}",
1264 errors
.push(ConcreteFailure((*origin
).clone(), sub
, sup
));
1267 VerifyGenericBound(ref kind
, ref origin
, sub
, ref sups
) => {
1268 let sub
= normalize(values
, sub
);
1270 .map(|&sup
| normalize(values
, sup
))
1271 .any(|sup
| free_regions
.is_subregion_of(self.tcx
, sub
, sup
))
1276 let sups
= sups
.iter().map(|&sup
| normalize(values
, sup
))
1279 GenericBoundFailure(
1280 (*origin
).clone(), kind
.clone(), sub
, sups
));
1286 fn extract_values_and_collect_conflicts(
1288 free_regions
: &FreeRegionMap
,
1289 var_data
: &[VarData
],
1290 graph
: &RegionGraph
,
1291 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1294 debug
!("extract_values_and_collect_conflicts()");
1296 // This is the best way that I have found to suppress
1297 // duplicate and related errors. Basically we keep a set of
1298 // flags for every node. Whenever an error occurs, we will
1299 // walk some portion of the graph looking to find pairs of
1300 // conflicting regions to report to the user. As we walk, we
1301 // trip the flags from false to true, and if we find that
1302 // we've already reported an error involving any particular
1303 // node we just stop and don't report the current error. The
1304 // idea is to report errors that derive from independent
1305 // regions of the graph, but not those that derive from
1306 // overlapping locations.
1307 let mut dup_vec
: Vec
<_
> = repeat(u32::MAX
).take(self.num_vars() as usize).collect();
1309 for idx
in 0..self.num_vars() as usize {
1310 match var_data
[idx
].value
{
1312 /* Inference successful */
1315 /* Unconstrained inference: do not report an error
1316 until the value of this variable is requested.
1317 After all, sometimes we make region variables but never
1318 really use their values. */
1321 /* Inference impossible, this value contains
1322 inconsistent constraints.
1324 I think that in this case we should report an
1325 error now---unlike the case above, we can't
1326 wait to see whether the user needs the result
1327 of this variable. The reason is that the mere
1328 existence of this variable implies that the
1329 region graph is inconsistent, whether or not it
1332 For example, we may have created a region
1333 variable that is the GLB of two other regions
1334 which do not have a GLB. Even if that variable
1335 is not used, it implies that those two regions
1336 *should* have a GLB.
1338 At least I think this is true. It may be that
1339 the mere existence of a conflict in a region variable
1340 that is not used is not a problem, so if this rule
1341 starts to create problems we'll have to revisit
1342 this portion of the code and think hard about it. =) */
1344 let node_vid
= RegionVid { index: idx as u32 }
;
1345 match var_data
[idx
].classification
{
1347 self.collect_error_for_expanding_node(
1348 free_regions
, graph
, var_data
, &mut dup_vec
,
1352 self.collect_error_for_contracting_node(
1353 free_regions
, graph
, var_data
, &mut dup_vec
,
1361 // Check for future hostile edges tied to a bad default
1362 self.report_future_hostility(&graph
);
1364 (0..self.num_vars() as usize).map(|idx
| var_data
[idx
].value
).collect()
1367 fn report_future_hostility(&self, graph
: &RegionGraph
) {
1368 let constraints
= self.constraints
.borrow();
1369 for edge
in graph
.all_edges() {
1370 match constraints
[&edge
.data
] {
1371 SubregionOrigin
::DefaultExistentialBound(_
) => {
1372 // this will become 'static in the future
1377 // this constraint will become a 'static constraint in the
1378 // future, so walk outward and see if we have any hard
1379 // bounds that could not be inferred to 'static
1380 for nid
in graph
.depth_traverse(edge
.target()) {
1381 for (_
, succ
) in graph
.outgoing_edges(nid
) {
1383 ConstrainVarSubReg(_
, r
) => {
1385 ty
::ReStatic
| ty
::ReInfer(_
) => {
1388 ty
::ReFree(_
) | ty
::ReScope(_
) | ty
::ReEmpty
=> {
1391 constraints
[&edge
.data
].span(),
1393 "this code may fail to compile in Rust 1.3 due to \
1394 the proposed change in object lifetime bound defaults");
1395 return; // only issue the warning once per fn
1397 ty
::ReEarlyBound(..) | ty
::ReLateBound(..) => {
1398 self.tcx
.sess
.span_bug(
1399 constraints
[&succ
.data
].span(),
1400 "relation to bound region");
1411 fn construct_graph(&self) -> RegionGraph
{
1412 let num_vars
= self.num_vars();
1414 let constraints
= self.constraints
.borrow();
1416 let mut graph
= graph
::Graph
::new();
1418 for _
in 0..num_vars
{
1421 let dummy_idx
= graph
.add_node(());
1423 for (constraint
, _
) in constraints
.iter() {
1425 ConstrainVarSubVar(a_id
, b_id
) => {
1426 graph
.add_edge(NodeIndex(a_id
.index
as usize),
1427 NodeIndex(b_id
.index
as usize),
1430 ConstrainRegSubVar(_
, b_id
) => {
1431 graph
.add_edge(dummy_idx
,
1432 NodeIndex(b_id
.index
as usize),
1435 ConstrainVarSubReg(a_id
, _
) => {
1436 graph
.add_edge(NodeIndex(a_id
.index
as usize),
1446 fn collect_error_for_expanding_node(&self,
1447 free_regions
: &FreeRegionMap
,
1448 graph
: &RegionGraph
,
1449 var_data
: &[VarData
],
1450 dup_vec
: &mut [u32],
1451 node_idx
: RegionVid
,
1452 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1454 // Errors in expanding nodes result from a lower-bound that is
1455 // not contained by an upper-bound.
1456 let (mut lower_bounds
, lower_dup
) =
1457 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1458 graph
::INCOMING
, dup_vec
);
1459 let (mut upper_bounds
, upper_dup
) =
1460 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1461 graph
::OUTGOING
, dup_vec
);
1463 if lower_dup
|| upper_dup
{
1467 // We place free regions first because we are special casing
1468 // SubSupConflict(ReFree, ReFree) when reporting error, and so
1469 // the user will more likely get a specific suggestion.
1470 fn free_regions_first(a
: &RegionAndOrigin
,
1471 b
: &RegionAndOrigin
)
1473 match (a
.region
, b
.region
) {
1474 (ReFree(..), ReFree(..)) => Equal
,
1475 (ReFree(..), _
) => Less
,
1476 (_
, ReFree(..)) => Greater
,
1480 lower_bounds
.sort_by(|a
, b
| { free_regions_first(a, b) }
);
1481 upper_bounds
.sort_by(|a
, b
| { free_regions_first(a, b) }
);
1483 for lower_bound
in &lower_bounds
{
1484 for upper_bound
in &upper_bounds
{
1485 if !free_regions
.is_subregion_of(self.tcx
,
1487 upper_bound
.region
) {
1488 debug
!("pushing SubSupConflict sub: {:?} sup: {:?}",
1489 lower_bound
.region
, upper_bound
.region
);
1490 errors
.push(SubSupConflict(
1491 (*self.var_origins
.borrow())[node_idx
.index
as usize].clone(),
1492 lower_bound
.origin
.clone(),
1494 upper_bound
.origin
.clone(),
1495 upper_bound
.region
));
1501 self.tcx
.sess
.span_bug(
1502 (*self.var_origins
.borrow())[node_idx
.index
as usize].span(),
1503 &format
!("collect_error_for_expanding_node() could not find error \
1504 for var {:?}, lower_bounds={:?}, upper_bounds={:?}",
1510 fn collect_error_for_contracting_node(
1512 free_regions
: &FreeRegionMap
,
1513 graph
: &RegionGraph
,
1514 var_data
: &[VarData
],
1515 dup_vec
: &mut [u32],
1516 node_idx
: RegionVid
,
1517 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1519 // Errors in contracting nodes result from two upper-bounds
1520 // that have no intersection.
1521 let (upper_bounds
, dup_found
) =
1522 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1523 graph
::OUTGOING
, dup_vec
);
1529 for upper_bound_1
in &upper_bounds
{
1530 for upper_bound_2
in &upper_bounds
{
1531 match self.glb_concrete_regions(free_regions
,
1532 upper_bound_1
.region
,
1533 upper_bound_2
.region
) {
1536 errors
.push(SupSupConflict(
1537 (*self.var_origins
.borrow())[node_idx
.index
as usize].clone(),
1538 upper_bound_1
.origin
.clone(),
1539 upper_bound_1
.region
,
1540 upper_bound_2
.origin
.clone(),
1541 upper_bound_2
.region
));
1548 self.tcx
.sess
.span_bug(
1549 (*self.var_origins
.borrow())[node_idx
.index
as usize].span(),
1550 &format
!("collect_error_for_contracting_node() could not find error \
1551 for var {:?}, upper_bounds={:?}",
1556 fn collect_concrete_regions(&self,
1557 graph
: &RegionGraph
,
1558 var_data
: &[VarData
],
1559 orig_node_idx
: RegionVid
,
1561 dup_vec
: &mut [u32])
1562 -> (Vec
<RegionAndOrigin
<'tcx
>>, bool
) {
1563 struct WalkState
<'tcx
> {
1564 set
: FnvHashSet
<RegionVid
>,
1565 stack
: Vec
<RegionVid
>,
1566 result
: Vec
<RegionAndOrigin
<'tcx
>>,
1569 let mut state
= WalkState
{
1571 stack
: vec
!(orig_node_idx
),
1575 state
.set
.insert(orig_node_idx
);
1577 // to start off the process, walk the source node in the
1578 // direction specified
1579 process_edges(self, &mut state
, graph
, orig_node_idx
, dir
);
1581 while !state
.stack
.is_empty() {
1582 let node_idx
= state
.stack
.pop().unwrap();
1583 let classification
= var_data
[node_idx
.index
as usize].classification
;
1585 // check whether we've visited this node on some previous walk
1586 if dup_vec
[node_idx
.index
as usize] == u32::MAX
{
1587 dup_vec
[node_idx
.index
as usize] = orig_node_idx
.index
;
1588 } else if dup_vec
[node_idx
.index
as usize] != orig_node_idx
.index
{
1589 state
.dup_found
= true;
1592 debug
!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1593 classification={:?})",
1594 orig_node_idx
, node_idx
, classification
);
1596 // figure out the direction from which this node takes its
1597 // values, and search for concrete regions etc in that direction
1598 let dir
= match classification
{
1599 Expanding
=> graph
::INCOMING
,
1600 Contracting
=> graph
::OUTGOING
,
1603 process_edges(self, &mut state
, graph
, node_idx
, dir
);
1606 let WalkState {result, dup_found, ..}
= state
;
1607 return (result
, dup_found
);
1609 fn process_edges
<'a
, 'tcx
>(this
: &RegionVarBindings
<'a
, 'tcx
>,
1610 state
: &mut WalkState
<'tcx
>,
1611 graph
: &RegionGraph
,
1612 source_vid
: RegionVid
,
1614 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
1616 let source_node_index
= NodeIndex(source_vid
.index
as usize);
1617 for (_
, edge
) in graph
.adjacent_edges(source_node_index
, dir
) {
1619 ConstrainVarSubVar(from_vid
, to_vid
) => {
1621 if from_vid
== source_vid {to_vid}
else {from_vid}
;
1622 if state
.set
.insert(opp_vid
) {
1623 state
.stack
.push(opp_vid
);
1627 ConstrainRegSubVar(region
, _
) |
1628 ConstrainVarSubReg(_
, region
) => {
1629 state
.result
.push(RegionAndOrigin
{
1631 origin
: this
.constraints
.borrow().get(&edge
.data
).unwrap().clone()
1639 fn iterate_until_fixed_point
<F
>(&self, tag
: &str, mut body
: F
) where
1640 F
: FnMut(&Constraint
) -> bool
,
1642 let mut iteration
= 0;
1643 let mut changed
= true;
1647 debug
!("---- {} Iteration {}{}", "#", tag
, iteration
);
1648 for (constraint
, _
) in self.constraints
.borrow().iter() {
1649 let edge_changed
= body(constraint
);
1651 debug
!("Updated due to constraint {:?}",
1657 debug
!("---- {} Complete after {} iteration(s)", tag
, iteration
);
1662 impl<'tcx
> fmt
::Debug
for Verify
<'tcx
> {
1663 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1665 VerifyRegSubReg(_
, ref a
, ref b
) => {
1666 write
!(f
, "VerifyRegSubReg({:?}, {:?})", a
, b
)
1668 VerifyGenericBound(_
, ref p
, ref a
, ref bs
) => {
1669 write
!(f
, "VerifyGenericBound({:?}, {:?}, {:?})", p
, a
, bs
)
1675 fn normalize(values
: &Vec
<VarValue
>, r
: ty
::Region
) -> ty
::Region
{
1677 ty
::ReInfer(ReVar(rid
)) => lookup(values
, rid
),
1682 fn lookup(values
: &Vec
<VarValue
>, rid
: ty
::RegionVid
) -> ty
::Region
{
1683 match values
[rid
.index
as usize] {
1685 NoValue
=> ReEmpty
, // No constraints, return ty::ReEmpty
1686 ErrorValue
=> ReStatic
, // Previously reported error.
1690 impl<'tcx
> fmt
::Debug
for RegionAndOrigin
<'tcx
> {
1691 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1692 write
!(f
, "RegionAndOrigin({:?},{:?})",
1698 impl<'tcx
> fmt
::Debug
for GenericKind
<'tcx
> {
1699 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1701 GenericKind
::Param(ref p
) => write
!(f
, "{:?}", p
),
1702 GenericKind
::Projection(ref p
) => write
!(f
, "{:?}", p
),
1707 impl<'tcx
> fmt
::Display
for GenericKind
<'tcx
> {
1708 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1710 GenericKind
::Param(ref p
) => write
!(f
, "{}", p
),
1711 GenericKind
::Projection(ref p
) => write
!(f
, "{}", p
),
1716 impl<'tcx
> GenericKind
<'tcx
> {
1717 pub fn to_ty(&self, tcx
: &ty
::ctxt
<'tcx
>) -> Ty
<'tcx
> {
1719 GenericKind
::Param(ref p
) =>
1721 GenericKind
::Projection(ref p
) =>
1722 ty
::mk_projection(tcx
, p
.trait_ref
.clone(), p
.item_name
),