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}
;
24 use middle
::ty
::{self, Ty}
;
25 use middle
::ty
::{BoundRegion, FreeRegion, Region, RegionVid}
;
26 use middle
::ty
::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound}
;
27 use middle
::ty
::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh}
;
28 use middle
::ty_relate
::RelateResult
;
30 use middle
::graph
::{Direction, NodeIndex}
;
31 use util
::common
::indenter
;
32 use util
::nodemap
::{FnvHashMap, FnvHashSet}
;
33 use util
::ppaux
::{Repr, UserString}
;
35 use std
::cell
::{Cell, RefCell}
;
36 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, Debug, 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 {}",
327 vid
, origin
.repr(self.tcx
));
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({})",
395 constraint
.repr(self.tcx
));
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({})",
410 verify
.repr(self.tcx
));
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 {}",
458 origin
.repr(self.tcx
));
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: {} <= {}",
476 sup
.repr(self.tcx
)));
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
.repr(self.tcx
));
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
.repr(self.tcx
));
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, subject_node
: ast
::NodeId
) -> Vec
<RegionResolutionError
<'tcx
>> {
716 debug
!("RegionVarBindings: resolve_regions()");
717 let mut errors
= vec
!();
718 let v
= self.infer_variable_values(&mut errors
, subject_node
);
719 *self.values
.borrow_mut() = Some(v
);
723 fn is_subregion_of(&self, sub
: Region
, sup
: Region
) -> bool
{
724 self.tcx
.region_maps
.is_subregion_of(sub
, sup
)
727 fn lub_concrete_regions(&self, 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(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,
804 return match a
.cmp(b
) {
805 Less
=> helper(self, a
, b
),
806 Greater
=> helper(self, b
, a
),
807 Equal
=> ty
::ReFree(*a
)
810 fn helper(this
: &RegionVarBindings
,
812 b
: &FreeRegion
) -> ty
::Region
814 if this
.tcx
.region_maps
.sub_free_region(*a
, *b
) {
816 } else if this
.tcx
.region_maps
.sub_free_region(*b
, *a
) {
824 fn glb_concrete_regions(&self,
827 -> RelateResult
<'tcx
, Region
>
829 debug
!("glb_concrete_regions({:?}, {:?})", a
, b
);
831 (ReLateBound(..), _
) |
832 (_
, ReLateBound(..)) |
833 (ReEarlyBound(..), _
) |
834 (_
, ReEarlyBound(..)) => {
836 &format
!("cannot relate bound region: GLB({}, {})",
841 (ReStatic
, r
) | (r
, ReStatic
) => {
842 // static lives longer than everything else
846 (ReEmpty
, _
) | (_
, ReEmpty
) => {
847 // nothing lives shorter than everything else
851 (ReInfer(ReVar(v_id
)), _
) |
852 (_
, ReInfer(ReVar(v_id
))) => {
853 self.tcx
.sess
.span_bug(
854 (*self.var_origins
.borrow())[v_id
.index
as usize].span(),
855 &format
!("glb_concrete_regions invoked with \
856 non-concrete regions: {:?}, {:?}",
861 (ReFree(ref fr
), ReScope(s_id
)) |
862 (ReScope(s_id
), ReFree(ref fr
)) => {
863 let s
= ReScope(s_id
);
864 // Free region is something "at least as big as
865 // `fr.scope_id`." If we find that the scope `fr.scope_id` is bigger
866 // than the scope `s_id`, then we can say that the GLB
867 // is the scope `s_id`. Otherwise, as we do not know
868 // big the free region is precisely, the GLB is undefined.
869 let fr_scope
= fr
.scope
.to_code_extent();
870 if self.tcx
.region_maps
.nearest_common_ancestor(fr_scope
, s_id
) == fr_scope
{
873 Err(ty
::terr_regions_no_overlap(b
, a
))
877 (ReScope(a_id
), ReScope(b_id
)) => {
878 self.intersect_scopes(a
, b
, a_id
, b_id
)
881 (ReFree(ref a_fr
), ReFree(ref b_fr
)) => {
882 self.glb_free_regions(a_fr
, b_fr
)
885 // For these types, we cannot define any additional
887 (ReInfer(ReSkolemized(..)), _
) |
888 (_
, ReInfer(ReSkolemized(..))) => {
892 Err(ty
::terr_regions_no_overlap(b
, a
))
898 /// Computes a region that is enclosed by both free region arguments, if any. Guarantees that
899 /// if the same two regions are given as argument, in any order, a consistent result is
901 fn glb_free_regions(&self,
904 -> RelateResult
<'tcx
, ty
::Region
>
906 return match a
.cmp(b
) {
907 Less
=> helper(self, a
, b
),
908 Greater
=> helper(self, b
, a
),
909 Equal
=> Ok(ty
::ReFree(*a
))
912 fn helper
<'a
, 'tcx
>(this
: &RegionVarBindings
<'a
, 'tcx
>,
914 b
: &FreeRegion
) -> RelateResult
<'tcx
, ty
::Region
>
916 if this
.tcx
.region_maps
.sub_free_region(*a
, *b
) {
918 } else if this
.tcx
.region_maps
.sub_free_region(*b
, *a
) {
921 this
.intersect_scopes(ty
::ReFree(*a
), ty
::ReFree(*b
),
922 a
.scope
.to_code_extent(),
923 b
.scope
.to_code_extent())
928 fn intersect_scopes(&self,
929 region_a
: ty
::Region
,
930 region_b
: ty
::Region
,
931 scope_a
: region
::CodeExtent
,
932 scope_b
: region
::CodeExtent
)
933 -> RelateResult
<'tcx
, Region
>
935 // We want to generate the intersection of two
936 // scopes or two free regions. So, if one of
937 // these scopes is a subscope of the other, return
938 // it. Otherwise fail.
939 debug
!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
940 scope_a
, scope_b
, region_a
, region_b
);
941 let r_id
= self.tcx
.region_maps
.nearest_common_ancestor(scope_a
, scope_b
);
944 } else if r_id
== scope_b
{
947 Err(ty
::terr_regions_no_overlap(region_a
, region_b
))
952 // ______________________________________________________________________
954 #[derive(Copy, Clone, PartialEq, Debug)]
955 enum Classification { Expanding, Contracting }
957 #[derive(Copy, Clone)]
958 pub enum VarValue { NoValue, Value(Region), ErrorValue }
961 classification
: Classification
,
965 struct RegionAndOrigin
<'tcx
> {
967 origin
: SubregionOrigin
<'tcx
>,
970 type RegionGraph
= graph
::Graph
<(), Constraint
>;
972 impl<'a
, 'tcx
> RegionVarBindings
<'a
, 'tcx
> {
973 fn infer_variable_values(&self,
974 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>,
975 subject
: ast
::NodeId
) -> Vec
<VarValue
>
977 let mut var_data
= self.construct_var_data();
979 // Dorky hack to cause `dump_constraints` to only get called
980 // if debug mode is enabled:
981 debug
!("----() End constraint listing {:?}---", self.dump_constraints());
982 graphviz
::maybe_print_constraints_for(self, subject
);
984 self.expansion(&mut var_data
);
985 self.contraction(&mut var_data
);
987 self.extract_values_and_collect_conflicts(&var_data
[..],
989 self.collect_concrete_region_errors(&values
, errors
);
993 fn construct_var_data(&self) -> Vec
<VarData
> {
994 (0..self.num_vars() as usize).map(|_
| {
996 // All nodes are initially classified as contracting; during
997 // the expansion phase, we will shift the classification for
998 // those nodes that have a concrete region predecessor to
1000 classification
: Contracting
,
1006 fn dump_constraints(&self) {
1007 debug
!("----() Start constraint listing ()----");
1008 for (idx
, (constraint
, _
)) in self.constraints
.borrow().iter().enumerate() {
1009 debug
!("Constraint {} => {}", idx
, constraint
.repr(self.tcx
));
1013 fn expansion(&self, var_data
: &mut [VarData
]) {
1014 self.iterate_until_fixed_point("Expansion", |constraint
| {
1015 debug
!("expansion: constraint={} origin={}",
1016 constraint
.repr(self.tcx
),
1017 self.constraints
.borrow()
1022 ConstrainRegSubVar(a_region
, b_vid
) => {
1023 let b_data
= &mut var_data
[b_vid
.index
as usize];
1024 self.expand_node(a_region
, b_vid
, b_data
)
1026 ConstrainVarSubVar(a_vid
, b_vid
) => {
1027 match var_data
[a_vid
.index
as usize].value
{
1028 NoValue
| ErrorValue
=> false,
1029 Value(a_region
) => {
1030 let b_node
= &mut var_data
[b_vid
.index
as usize];
1031 self.expand_node(a_region
, b_vid
, b_node
)
1035 ConstrainVarSubReg(..) => {
1036 // This is a contraction constraint. Ignore it.
1043 fn expand_node(&self,
1046 b_data
: &mut VarData
)
1049 debug
!("expand_node({}, {:?} == {})",
1050 a_region
.repr(self.tcx
),
1052 b_data
.value
.repr(self.tcx
));
1054 // Check if this relationship is implied by a given.
1057 if self.givens
.borrow().contains(&(fr
, b_vid
)) {
1065 b_data
.classification
= Expanding
;
1066 match b_data
.value
{
1068 debug
!("Setting initial value of {:?} to {}",
1069 b_vid
, a_region
.repr(self.tcx
));
1071 b_data
.value
= Value(a_region
);
1075 Value(cur_region
) => {
1076 let lub
= self.lub_concrete_regions(a_region
, cur_region
);
1077 if lub
== cur_region
{
1081 debug
!("Expanding value of {:?} from {} to {}",
1083 cur_region
.repr(self.tcx
),
1084 lub
.repr(self.tcx
));
1086 b_data
.value
= Value(lub
);
1096 fn contraction(&self,
1097 var_data
: &mut [VarData
]) {
1098 self.iterate_until_fixed_point("Contraction", |constraint
| {
1099 debug
!("contraction: constraint={} origin={}",
1100 constraint
.repr(self.tcx
),
1101 self.constraints
.borrow()
1106 ConstrainRegSubVar(..) => {
1107 // This is an expansion constraint. Ignore.
1110 ConstrainVarSubVar(a_vid
, b_vid
) => {
1111 match var_data
[b_vid
.index
as usize].value
{
1112 NoValue
| ErrorValue
=> false,
1113 Value(b_region
) => {
1114 let a_data
= &mut var_data
[a_vid
.index
as usize];
1115 self.contract_node(a_vid
, a_data
, b_region
)
1119 ConstrainVarSubReg(a_vid
, b_region
) => {
1120 let a_data
= &mut var_data
[a_vid
.index
as usize];
1121 self.contract_node(a_vid
, a_data
, b_region
)
1127 fn contract_node(&self,
1129 a_data
: &mut VarData
,
1132 debug
!("contract_node({:?} == {}/{:?}, {})",
1133 a_vid
, a_data
.value
.repr(self.tcx
),
1134 a_data
.classification
, b_region
.repr(self.tcx
));
1136 return match a_data
.value
{
1138 assert_eq
!(a_data
.classification
, Contracting
);
1139 a_data
.value
= Value(b_region
);
1143 ErrorValue
=> false, // no change
1145 Value(a_region
) => {
1146 match a_data
.classification
{
1147 Expanding
=> check_node(self, a_vid
, a_data
, a_region
, b_region
),
1148 Contracting
=> adjust_node(self, a_vid
, a_data
, a_region
, b_region
),
1153 fn check_node(this
: &RegionVarBindings
,
1155 a_data
: &mut VarData
,
1159 if !this
.is_subregion_of(a_region
, b_region
) {
1160 debug
!("Setting {:?} to ErrorValue: {} not subregion of {}",
1162 a_region
.repr(this
.tcx
),
1163 b_region
.repr(this
.tcx
));
1164 a_data
.value
= ErrorValue
;
1169 fn adjust_node(this
: &RegionVarBindings
,
1171 a_data
: &mut VarData
,
1175 match this
.glb_concrete_regions(a_region
, b_region
) {
1177 if glb
== a_region
{
1180 debug
!("Contracting value of {:?} from {} to {}",
1182 a_region
.repr(this
.tcx
),
1183 glb
.repr(this
.tcx
));
1184 a_data
.value
= Value(glb
);
1189 debug
!("Setting {:?} to ErrorValue: no glb of {}, {}",
1191 a_region
.repr(this
.tcx
),
1192 b_region
.repr(this
.tcx
));
1193 a_data
.value
= ErrorValue
;
1200 fn collect_concrete_region_errors(&self,
1201 values
: &Vec
<VarValue
>,
1202 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1204 let mut reg_reg_dups
= FnvHashSet();
1205 for verify
in &*self.verifys
.borrow() {
1207 VerifyRegSubReg(ref origin
, sub
, sup
) => {
1208 if self.is_subregion_of(sub
, sup
) {
1212 if !reg_reg_dups
.insert((sub
, sup
)) {
1216 debug
!("ConcreteFailure: !(sub <= sup): sub={}, sup={}",
1218 sup
.repr(self.tcx
));
1219 errors
.push(ConcreteFailure((*origin
).clone(), sub
, sup
));
1222 VerifyGenericBound(ref kind
, ref origin
, sub
, ref sups
) => {
1223 let sub
= normalize(values
, sub
);
1225 .map(|&sup
| normalize(values
, sup
))
1226 .any(|sup
| self.is_subregion_of(sub
, sup
))
1231 let sups
= sups
.iter().map(|&sup
| normalize(values
, sup
))
1234 GenericBoundFailure(
1235 (*origin
).clone(), kind
.clone(), sub
, sups
));
1241 fn extract_values_and_collect_conflicts(
1243 var_data
: &[VarData
],
1244 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1247 debug
!("extract_values_and_collect_conflicts()");
1249 // This is the best way that I have found to suppress
1250 // duplicate and related errors. Basically we keep a set of
1251 // flags for every node. Whenever an error occurs, we will
1252 // walk some portion of the graph looking to find pairs of
1253 // conflicting regions to report to the user. As we walk, we
1254 // trip the flags from false to true, and if we find that
1255 // we've already reported an error involving any particular
1256 // node we just stop and don't report the current error. The
1257 // idea is to report errors that derive from independent
1258 // regions of the graph, but not those that derive from
1259 // overlapping locations.
1260 let mut dup_vec
: Vec
<_
> = repeat(u32::MAX
).take(self.num_vars() as usize).collect();
1262 let mut opt_graph
= None
;
1264 for idx
in 0..self.num_vars() as usize {
1265 match var_data
[idx
].value
{
1267 /* Inference successful */
1270 /* Unconstrained inference: do not report an error
1271 until the value of this variable is requested.
1272 After all, sometimes we make region variables but never
1273 really use their values. */
1276 /* Inference impossible, this value contains
1277 inconsistent constraints.
1279 I think that in this case we should report an
1280 error now---unlike the case above, we can't
1281 wait to see whether the user needs the result
1282 of this variable. The reason is that the mere
1283 existence of this variable implies that the
1284 region graph is inconsistent, whether or not it
1287 For example, we may have created a region
1288 variable that is the GLB of two other regions
1289 which do not have a GLB. Even if that variable
1290 is not used, it implies that those two regions
1291 *should* have a GLB.
1293 At least I think this is true. It may be that
1294 the mere existence of a conflict in a region variable
1295 that is not used is not a problem, so if this rule
1296 starts to create problems we'll have to revisit
1297 this portion of the code and think hard about it. =) */
1299 if opt_graph
.is_none() {
1300 opt_graph
= Some(self.construct_graph());
1302 let graph
= opt_graph
.as_ref().unwrap();
1304 let node_vid
= RegionVid { index: idx as u32 }
;
1305 match var_data
[idx
].classification
{
1307 self.collect_error_for_expanding_node(
1308 graph
, var_data
, &mut dup_vec
,
1312 self.collect_error_for_contracting_node(
1313 graph
, var_data
, &mut dup_vec
,
1321 (0..self.num_vars() as usize).map(|idx
| var_data
[idx
].value
).collect()
1324 fn construct_graph(&self) -> RegionGraph
{
1325 let num_vars
= self.num_vars();
1327 let constraints
= self.constraints
.borrow();
1328 let num_edges
= constraints
.len();
1330 let mut graph
= graph
::Graph
::with_capacity(num_vars
as usize + 1,
1333 for _
in 0..num_vars
{
1336 let dummy_idx
= graph
.add_node(());
1338 for (constraint
, _
) in &*constraints
{
1340 ConstrainVarSubVar(a_id
, b_id
) => {
1341 graph
.add_edge(NodeIndex(a_id
.index
as usize),
1342 NodeIndex(b_id
.index
as usize),
1345 ConstrainRegSubVar(_
, b_id
) => {
1346 graph
.add_edge(dummy_idx
,
1347 NodeIndex(b_id
.index
as usize),
1350 ConstrainVarSubReg(a_id
, _
) => {
1351 graph
.add_edge(NodeIndex(a_id
.index
as usize),
1361 fn collect_error_for_expanding_node(
1363 graph
: &RegionGraph
,
1364 var_data
: &[VarData
],
1365 dup_vec
: &mut [u32],
1366 node_idx
: RegionVid
,
1367 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1369 // Errors in expanding nodes result from a lower-bound that is
1370 // not contained by an upper-bound.
1371 let (mut lower_bounds
, lower_dup
) =
1372 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1373 graph
::Incoming
, dup_vec
);
1374 let (mut upper_bounds
, upper_dup
) =
1375 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1376 graph
::Outgoing
, dup_vec
);
1378 if lower_dup
|| upper_dup
{
1382 // We place free regions first because we are special casing
1383 // SubSupConflict(ReFree, ReFree) when reporting error, and so
1384 // the user will more likely get a specific suggestion.
1385 fn free_regions_first(a
: &RegionAndOrigin
,
1386 b
: &RegionAndOrigin
)
1388 match (a
.region
, b
.region
) {
1389 (ReFree(..), ReFree(..)) => Equal
,
1390 (ReFree(..), _
) => Less
,
1391 (_
, ReFree(..)) => Greater
,
1395 lower_bounds
.sort_by(|a
, b
| { free_regions_first(a, b) }
);
1396 upper_bounds
.sort_by(|a
, b
| { free_regions_first(a, b) }
);
1398 for lower_bound
in &lower_bounds
{
1399 for upper_bound
in &upper_bounds
{
1400 if !self.is_subregion_of(lower_bound
.region
,
1401 upper_bound
.region
) {
1402 debug
!("pushing SubSupConflict sub: {:?} sup: {:?}",
1403 lower_bound
.region
, upper_bound
.region
);
1404 errors
.push(SubSupConflict(
1405 (*self.var_origins
.borrow())[node_idx
.index
as usize].clone(),
1406 lower_bound
.origin
.clone(),
1408 upper_bound
.origin
.clone(),
1409 upper_bound
.region
));
1415 self.tcx
.sess
.span_bug(
1416 (*self.var_origins
.borrow())[node_idx
.index
as usize].span(),
1417 &format
!("collect_error_for_expanding_node() could not find error \
1418 for var {:?}, lower_bounds={}, upper_bounds={}",
1420 lower_bounds
.repr(self.tcx
),
1421 upper_bounds
.repr(self.tcx
)));
1424 fn collect_error_for_contracting_node(
1426 graph
: &RegionGraph
,
1427 var_data
: &[VarData
],
1428 dup_vec
: &mut [u32],
1429 node_idx
: RegionVid
,
1430 errors
: &mut Vec
<RegionResolutionError
<'tcx
>>)
1432 // Errors in contracting nodes result from two upper-bounds
1433 // that have no intersection.
1434 let (upper_bounds
, dup_found
) =
1435 self.collect_concrete_regions(graph
, var_data
, node_idx
,
1436 graph
::Outgoing
, dup_vec
);
1442 for upper_bound_1
in &upper_bounds
{
1443 for upper_bound_2
in &upper_bounds
{
1444 match self.glb_concrete_regions(upper_bound_1
.region
,
1445 upper_bound_2
.region
) {
1448 errors
.push(SupSupConflict(
1449 (*self.var_origins
.borrow())[node_idx
.index
as usize].clone(),
1450 upper_bound_1
.origin
.clone(),
1451 upper_bound_1
.region
,
1452 upper_bound_2
.origin
.clone(),
1453 upper_bound_2
.region
));
1460 self.tcx
.sess
.span_bug(
1461 (*self.var_origins
.borrow())[node_idx
.index
as usize].span(),
1462 &format
!("collect_error_for_contracting_node() could not find error \
1463 for var {:?}, upper_bounds={}",
1465 upper_bounds
.repr(self.tcx
)));
1468 fn collect_concrete_regions(&self,
1469 graph
: &RegionGraph
,
1470 var_data
: &[VarData
],
1471 orig_node_idx
: RegionVid
,
1473 dup_vec
: &mut [u32])
1474 -> (Vec
<RegionAndOrigin
<'tcx
>>, bool
) {
1475 struct WalkState
<'tcx
> {
1476 set
: FnvHashSet
<RegionVid
>,
1477 stack
: Vec
<RegionVid
>,
1478 result
: Vec
<RegionAndOrigin
<'tcx
>>,
1481 let mut state
= WalkState
{
1483 stack
: vec
!(orig_node_idx
),
1487 state
.set
.insert(orig_node_idx
);
1489 // to start off the process, walk the source node in the
1490 // direction specified
1491 process_edges(self, &mut state
, graph
, orig_node_idx
, dir
);
1493 while !state
.stack
.is_empty() {
1494 let node_idx
= state
.stack
.pop().unwrap();
1495 let classification
= var_data
[node_idx
.index
as usize].classification
;
1497 // check whether we've visited this node on some previous walk
1498 if dup_vec
[node_idx
.index
as usize] == u32::MAX
{
1499 dup_vec
[node_idx
.index
as usize] = orig_node_idx
.index
;
1500 } else if dup_vec
[node_idx
.index
as usize] != orig_node_idx
.index
{
1501 state
.dup_found
= true;
1504 debug
!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1505 classification={:?})",
1506 orig_node_idx
, node_idx
, classification
);
1508 // figure out the direction from which this node takes its
1509 // values, and search for concrete regions etc in that direction
1510 let dir
= match classification
{
1511 Expanding
=> graph
::Incoming
,
1512 Contracting
=> graph
::Outgoing
,
1515 process_edges(self, &mut state
, graph
, node_idx
, dir
);
1518 let WalkState {result, dup_found, ..}
= state
;
1519 return (result
, dup_found
);
1521 fn process_edges
<'a
, 'tcx
>(this
: &RegionVarBindings
<'a
, 'tcx
>,
1522 state
: &mut WalkState
<'tcx
>,
1523 graph
: &RegionGraph
,
1524 source_vid
: RegionVid
,
1526 debug
!("process_edges(source_vid={:?}, dir={:?})", source_vid
, dir
);
1528 let source_node_index
= NodeIndex(source_vid
.index
as usize);
1529 graph
.each_adjacent_edge(source_node_index
, dir
, |_
, edge
| {
1531 ConstrainVarSubVar(from_vid
, to_vid
) => {
1533 if from_vid
== source_vid {to_vid}
else {from_vid}
;
1534 if state
.set
.insert(opp_vid
) {
1535 state
.stack
.push(opp_vid
);
1539 ConstrainRegSubVar(region
, _
) |
1540 ConstrainVarSubReg(_
, region
) => {
1541 state
.result
.push(RegionAndOrigin
{
1543 origin
: this
.constraints
.borrow().get(&edge
.data
).unwrap().clone()
1552 fn iterate_until_fixed_point
<F
>(&self, tag
: &str, mut body
: F
) where
1553 F
: FnMut(&Constraint
) -> bool
,
1555 let mut iteration
= 0;
1556 let mut changed
= true;
1560 debug
!("---- {} Iteration {}{}", "#", tag
, iteration
);
1561 for (constraint
, _
) in &*self.constraints
.borrow() {
1562 let edge_changed
= body(constraint
);
1564 debug
!("Updated due to constraint {}",
1565 constraint
.repr(self.tcx
));
1570 debug
!("---- {} Complete after {} iteration(s)", tag
, iteration
);
1575 impl<'tcx
> Repr
<'tcx
> for Constraint
{
1576 fn repr(&self, tcx
: &ty
::ctxt
) -> String
{
1578 ConstrainVarSubVar(a
, b
) => {
1579 format
!("ConstrainVarSubVar({}, {})", a
.repr(tcx
), b
.repr(tcx
))
1581 ConstrainRegSubVar(a
, b
) => {
1582 format
!("ConstrainRegSubVar({}, {})", a
.repr(tcx
), b
.repr(tcx
))
1584 ConstrainVarSubReg(a
, b
) => {
1585 format
!("ConstrainVarSubReg({}, {})", a
.repr(tcx
), b
.repr(tcx
))
1591 impl<'tcx
> Repr
<'tcx
> for Verify
<'tcx
> {
1592 fn repr(&self, tcx
: &ty
::ctxt
<'tcx
>) -> String
{
1594 VerifyRegSubReg(_
, ref a
, ref b
) => {
1595 format
!("VerifyRegSubReg({}, {})", a
.repr(tcx
), b
.repr(tcx
))
1597 VerifyGenericBound(_
, ref p
, ref a
, ref bs
) => {
1598 format
!("VerifyGenericBound({}, {}, {})",
1599 p
.repr(tcx
), a
.repr(tcx
), bs
.repr(tcx
))
1605 fn normalize(values
: &Vec
<VarValue
>, r
: ty
::Region
) -> ty
::Region
{
1607 ty
::ReInfer(ReVar(rid
)) => lookup(values
, rid
),
1612 fn lookup(values
: &Vec
<VarValue
>, rid
: ty
::RegionVid
) -> ty
::Region
{
1613 match values
[rid
.index
as usize] {
1615 NoValue
=> ReEmpty
, // No constraints, return ty::ReEmpty
1616 ErrorValue
=> ReStatic
, // Previously reported error.
1620 impl<'tcx
> Repr
<'tcx
> for VarValue
{
1621 fn repr(&self, tcx
: &ty
::ctxt
) -> String
{
1623 NoValue
=> format
!("NoValue"),
1624 Value(r
) => format
!("Value({})", r
.repr(tcx
)),
1625 ErrorValue
=> format
!("ErrorValue"),
1630 impl<'tcx
> Repr
<'tcx
> for RegionAndOrigin
<'tcx
> {
1631 fn repr(&self, tcx
: &ty
::ctxt
<'tcx
>) -> String
{
1632 format
!("RegionAndOrigin({},{})",
1633 self.region
.repr(tcx
),
1634 self.origin
.repr(tcx
))
1638 impl<'tcx
> Repr
<'tcx
> for GenericKind
<'tcx
> {
1639 fn repr(&self, tcx
: &ty
::ctxt
<'tcx
>) -> String
{
1641 GenericKind
::Param(ref p
) => p
.repr(tcx
),
1642 GenericKind
::Projection(ref p
) => p
.repr(tcx
),
1647 impl<'tcx
> UserString
<'tcx
> for GenericKind
<'tcx
> {
1648 fn user_string(&self, tcx
: &ty
::ctxt
<'tcx
>) -> String
{
1650 GenericKind
::Param(ref p
) => p
.user_string(tcx
),
1651 GenericKind
::Projection(ref p
) => p
.user_string(tcx
),
1656 impl<'tcx
> GenericKind
<'tcx
> {
1657 pub fn to_ty(&self, tcx
: &ty
::ctxt
<'tcx
>) -> Ty
<'tcx
> {
1659 GenericKind
::Param(ref p
) =>
1661 GenericKind
::Projection(ref p
) =>
1662 ty
::mk_projection(tcx
, p
.trait_ref
.clone(), p
.item_name
),