src/librustc/middle/typeck/infer/region_inference/mod.rs

   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.
   4 //
   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.
  10
  11 /*! See doc.rs */
  12
  13
  14 use middle::ty;
  15 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
  16 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound,
  17                  ReLateBound};
  18 use middle::ty::{ReScope, ReVar, ReSkolemized, BrFresh};
  19 use middle::typeck::infer::cres;
  20 use middle::typeck::infer::{RegionVariableOrigin, SubregionOrigin, TypeTrace};
  21 use middle::typeck::infer;
  22 use middle::graph;
  23 use middle::graph::{Direction, NodeIndex};
  24 use util::common::indenter;
  25 use util::ppaux::{Repr};
  26
  27 use std::cell::{Cell, RefCell};
  28 use std::uint;
  29 use std::collections::{HashMap, HashSet};
  30 use syntax::ast;
  31
  32 mod doc;
  33
  34 #[deriving(PartialEq, Eq, Hash)]
  35 pub enum Constraint {
  36     ConstrainVarSubVar(RegionVid, RegionVid),
  37     ConstrainRegSubVar(Region, RegionVid),
  38     ConstrainVarSubReg(RegionVid, Region),
  39     ConstrainRegSubReg(Region, Region),
  40 }
  41
  42 #[deriving(PartialEq, Eq, Hash)]
  43 pub struct TwoRegions {
  44     a: Region,
  45     b: Region,
  46 }
  47
  48 #[deriving(PartialEq)]
  49 pub enum UndoLogEntry {
  50     OpenSnapshot,
  51     CommitedSnapshot,
  52     Mark,
  53     AddVar(RegionVid),
  54     AddConstraint(Constraint),
  55     AddCombination(CombineMapType, TwoRegions)
  56 }
  57
  58 #[deriving(PartialEq)]
  59 pub enum CombineMapType {
  60     Lub, Glb
  61 }
  62
  63 #[deriving(Clone)]
  64 pub enum RegionResolutionError {
  65     /// `ConcreteFailure(o, a, b)`:
  66     ///
  67     /// `o` requires that `a <= b`, but this does not hold
  68     ConcreteFailure(SubregionOrigin, Region, Region),
  69
  70     /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
  71     ///
  72     /// Could not infer a value for `v` because `sub_r <= v` (due to
  73     /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
  74     /// `sub_r <= sup_r` does not hold.
  75     SubSupConflict(RegionVariableOrigin,
  76                    SubregionOrigin, Region,
  77                    SubregionOrigin, Region),
  78
  79     /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
  80     ///
  81     /// Could not infer a value for `v` because `v <= r1` (due to
  82     /// `origin1`) and `v <= r2` (due to `origin2`) and
  83     /// `r1` and `r2` have no intersection.
  84     SupSupConflict(RegionVariableOrigin,
  85                    SubregionOrigin, Region,
  86                    SubregionOrigin, Region),
  87
  88     /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
  89     /// more specific errors message by suggesting to the user where they
  90     /// should put a lifetime. In those cases we process and put those errors
  91     /// into `ProcessedErrors` before we do any reporting.
  92     ProcessedErrors(Vec<RegionVariableOrigin>,
  93                     Vec<(TypeTrace, ty::type_err)>,
  94                     Vec<SameRegions>),
  95 }
  96
  97 /// SameRegions is used to group regions that we think are the same and would
  98 /// like to indicate so to the user.
  99 /// For example, the following function
 100 /// ```
 101 /// struct Foo { bar: int }
 102 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
 103 ///    &x.bar
 104 /// }
 105 /// ```
 106 /// would report an error because we expect 'a and 'b to match, and so we group
 107 /// 'a and 'b together inside a SameRegions struct
 108 #[deriving(Clone)]
 109 pub struct SameRegions {
 110     pub scope_id: ast::NodeId,
 111     pub regions: Vec<BoundRegion>
 112 }
 113
 114 impl SameRegions {
 115     pub fn contains(&self, other: &BoundRegion) -> bool {
 116         self.regions.contains(other)
 117     }
 118
 119     pub fn push(&mut self, other: BoundRegion) {
 120         self.regions.push(other);
 121     }
 122 }
 123
 124 pub type CombineMap = HashMap<TwoRegions, RegionVid>;
 125
 126 pub struct RegionVarBindings<'a> {
 127     tcx: &'a ty::ctxt,
 128     var_origins: RefCell<Vec<RegionVariableOrigin>>,
 129     constraints: RefCell<HashMap<Constraint, SubregionOrigin>>,
 130     lubs: RefCell<CombineMap>,
 131     glbs: RefCell<CombineMap>,
 132     skolemization_count: Cell<uint>,
 133     bound_count: Cell<uint>,
 134
 135     // The undo log records actions that might later be undone.
 136     //
 137     // Note: when the undo_log is empty, we are not actively
 138     // snapshotting. When the `start_snapshot()` method is called, we
 139     // push an OpenSnapshot entry onto the list to indicate that we
 140     // are now actively snapshotting. The reason for this is that
 141     // otherwise we end up adding entries for things like the lower
 142     // bound on a variable and so forth, which can never be rolled
 143     // back.
 144     undo_log: RefCell<Vec<UndoLogEntry>>,
 145
 146     // This contains the results of inference.  It begins as an empty
 147     // option and only acquires a value after inference is complete.
 148     values: RefCell<Option<Vec<VarValue>>>,
 149 }
 150
 151 #[deriving(Show)]
 152 pub struct RegionSnapshot {
 153     length: uint
 154 }
 155
 156 #[deriving(Show)]
 157 pub struct RegionMark {
 158     length: uint
 159 }
 160
 161 impl<'a> RegionVarBindings<'a> {
 162     pub fn new(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
 163         RegionVarBindings {
 164             tcx: tcx,
 165             var_origins: RefCell::new(Vec::new()),
 166             values: RefCell::new(None),
 167             constraints: RefCell::new(HashMap::new()),
 168             lubs: RefCell::new(HashMap::new()),
 169             glbs: RefCell::new(HashMap::new()),
 170             skolemization_count: Cell::new(0),
 171             bound_count: Cell::new(0),
 172             undo_log: RefCell::new(Vec::new())
 173         }
 174     }
 175
 176     pub fn in_snapshot(&self) -> bool {
 177         self.undo_log.borrow().len() > 0
 178     }
 179
 180     pub fn start_snapshot(&self) -> RegionSnapshot {
 181         let length = self.undo_log.borrow().len();
 182         debug!("RegionVarBindings: start_snapshot({})", length);
 183         self.undo_log.borrow_mut().push(OpenSnapshot);
 184         RegionSnapshot { length: length }
 185     }
 186
 187     pub fn mark(&self) -> RegionMark {
 188         let length = self.undo_log.borrow().len();
 189         debug!("RegionVarBindings: mark({})", length);
 190         self.undo_log.borrow_mut().push(Mark);
 191         RegionMark { length: length }
 192     }
 193
 194     pub fn commit(&self, snapshot: RegionSnapshot) {
 195         debug!("RegionVarBindings: commit()");
 196         assert!(self.undo_log.borrow().len() > snapshot.length);
 197         assert!(*self.undo_log.borrow().get(snapshot.length) == OpenSnapshot);
 198
 199         let mut undo_log = self.undo_log.borrow_mut();
 200         if snapshot.length == 0 {
 201             undo_log.truncate(0);
 202         } else {
 203             *undo_log.get_mut(snapshot.length) = CommitedSnapshot;
 204         }
 205     }
 206
 207     pub fn rollback_to(&self, snapshot: RegionSnapshot) {
 208         debug!("RegionVarBindings: rollback_to({})", snapshot);
 209         let mut undo_log = self.undo_log.borrow_mut();
 210         assert!(undo_log.len() > snapshot.length);
 211         assert!(*undo_log.get(snapshot.length) == OpenSnapshot);
 212         while undo_log.len() > snapshot.length + 1 {
 213             match undo_log.pop().unwrap() {
 214                 OpenSnapshot => {
 215                     fail!("Failure to observe stack discipline");
 216                 }
 217                 Mark | CommitedSnapshot => { }
 218                 AddVar(vid) => {
 219                     let mut var_origins = self.var_origins.borrow_mut();
 220                     assert_eq!(var_origins.len(), vid.index + 1);
 221                     var_origins.pop().unwrap();
 222                 }
 223                 AddConstraint(ref constraint) => {
 224                     self.constraints.borrow_mut().remove(constraint);
 225                 }
 226                 AddCombination(Glb, ref regions) => {
 227                     self.glbs.borrow_mut().remove(regions);
 228                 }
 229                 AddCombination(Lub, ref regions) => {
 230                     self.lubs.borrow_mut().remove(regions);
 231                 }
 232             }
 233         }
 234         let c = undo_log.pop().unwrap();
 235         assert!(c == OpenSnapshot);
 236     }
 237
 238     pub fn num_vars(&self) -> uint {
 239         self.var_origins.borrow().len()
 240     }
 241
 242     pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
 243         let id = self.num_vars();
 244         self.var_origins.borrow_mut().push(origin.clone());
 245         let vid = RegionVid { index: id };
 246         if self.in_snapshot() {
 247             self.undo_log.borrow_mut().push(AddVar(vid));
 248         }
 249         debug!("created new region variable {:?} with origin {:?}",
 250                vid, origin.repr(self.tcx));
 251         return vid;
 252     }
 253
 254     pub fn new_skolemized(&self, br: ty::BoundRegion) -> Region {
 255         let sc = self.skolemization_count.get();
 256         self.skolemization_count.set(sc + 1);
 257         ReInfer(ReSkolemized(sc, br))
 258     }
 259
 260     pub fn new_bound(&self, binder_id: ast::NodeId) -> Region {
 261         // Creates a fresh bound variable for use in GLB computations.
 262         // See discussion of GLB computation in the large comment at
 263         // the top of this file for more details.
 264         //
 265         // This computation is potentially wrong in the face of
 266         // rollover.  It's conceivable, if unlikely, that one might
 267         // wind up with accidental capture for nested functions in
 268         // that case, if the outer function had bound regions created
 269         // a very long time before and the inner function somehow
 270         // wound up rolling over such that supposedly fresh
 271         // identifiers were in fact shadowed. For now, we just assert
 272         // that there is no rollover -- eventually we should try to be
 273         // robust against this possibility, either by checking the set
 274         // of bound identifiers that appear in a given expression and
 275         // ensure that we generate one that is distinct, or by
 276         // changing the representation of bound regions in a fn
 277         // declaration
 278
 279         let sc = self.bound_count.get();
 280         self.bound_count.set(sc + 1);
 281
 282         if sc >= self.bound_count.get() {
 283             self.tcx.sess.bug("rollover in RegionInference new_bound()");
 284         }
 285
 286         ReLateBound(binder_id, BrFresh(sc))
 287     }
 288
 289     fn values_are_none(&self) -> bool {
 290         self.values.borrow().is_none()
 291     }
 292
 293     pub fn add_constraint(&self,
 294                           constraint: Constraint,
 295                           origin: SubregionOrigin) {
 296         // cannot add constraints once regions are resolved
 297         assert!(self.values_are_none());
 298
 299         debug!("RegionVarBindings: add_constraint({:?})", constraint);
 300
 301         if self.constraints.borrow_mut().insert(constraint, origin) {
 302             if self.in_snapshot() {
 303                 self.undo_log.borrow_mut().push(AddConstraint(constraint));
 304             }
 305         }
 306     }
 307
 308     pub fn make_subregion(&self,
 309                           origin: SubregionOrigin,
 310                           sub: Region,
 311                           sup: Region) {
 312         // cannot add constraints once regions are resolved
 313         assert!(self.values_are_none());
 314
 315         debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
 316                sub.repr(self.tcx),
 317                sup.repr(self.tcx),
 318                origin.repr(self.tcx));
 319
 320         match (sub, sup) {
 321           (ReEarlyBound(..), _) |
 322           (ReLateBound(..), _) |
 323           (_, ReEarlyBound(..)) |
 324           (_, ReLateBound(..)) => {
 325             self.tcx.sess.span_bug(
 326                 origin.span(),
 327                 format!("cannot relate bound region: {} <= {}",
 328                         sub.repr(self.tcx),
 329                         sup.repr(self.tcx)).as_slice());
 330           }
 331           (_, ReStatic) => {
 332             // all regions are subregions of static, so we can ignore this
 333           }
 334           (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
 335             self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
 336           }
 337           (r, ReInfer(ReVar(sup_id))) => {
 338             self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
 339           }
 340           (ReInfer(ReVar(sub_id)), r) => {
 341             self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
 342           }
 343           _ => {
 344             self.add_constraint(ConstrainRegSubReg(sub, sup), origin);
 345           }
 346         }
 347     }
 348
 349     pub fn lub_regions(&self,
 350                        origin: SubregionOrigin,
 351                        a: Region,
 352                        b: Region)
 353                        -> Region {
 354         // cannot add constraints once regions are resolved
 355         assert!(self.values_are_none());
 356
 357         debug!("RegionVarBindings: lub_regions({:?}, {:?})", a, b);
 358         match (a, b) {
 359             (ReStatic, _) | (_, ReStatic) => {
 360                 ReStatic // nothing lives longer than static
 361             }
 362
 363             _ => {
 364                 self.combine_vars(
 365                     Lub, a, b, origin.clone(),
 366                     |this, old_r, new_r|
 367                     this.make_subregion(origin.clone(), old_r, new_r))
 368             }
 369         }
 370     }
 371
 372     pub fn glb_regions(&self,
 373                        origin: SubregionOrigin,
 374                        a: Region,
 375                        b: Region)
 376                        -> Region {
 377         // cannot add constraints once regions are resolved
 378         assert!(self.values_are_none());
 379
 380         debug!("RegionVarBindings: glb_regions({:?}, {:?})", a, b);
 381         match (a, b) {
 382             (ReStatic, r) | (r, ReStatic) => {
 383                 // static lives longer than everything else
 384                 r
 385             }
 386
 387             _ => {
 388                 self.combine_vars(
 389                     Glb, a, b, origin.clone(),
 390                     |this, old_r, new_r|
 391                     this.make_subregion(origin.clone(), new_r, old_r))
 392             }
 393         }
 394     }
 395
 396     pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
 397         let v = match *self.values.borrow() {
 398             None => {
 399                 self.tcx.sess.span_bug(
 400                     self.var_origins.borrow().get(rid.index).span(),
 401                     "attempt to resolve region variable before values have \
 402                      been computed!")
 403             }
 404             Some(ref values) => *values.get(rid.index)
 405         };
 406
 407         debug!("RegionVarBindings: resolve_var({:?}={})={:?}",
 408                rid, rid.index, v);
 409         match v {
 410             Value(r) => r,
 411
 412             NoValue => {
 413                 // No constraints, return ty::ReEmpty
 414                 ReEmpty
 415             }
 416
 417             ErrorValue => {
 418                 // An error that has previously been reported.
 419                 ReStatic
 420             }
 421         }
 422     }
 423
 424     fn combine_map<'a>(&'a self, t: CombineMapType)
 425                    -> &'a RefCell<CombineMap> {
 426         match t {
 427             Glb => &self.glbs,
 428             Lub => &self.lubs,
 429         }
 430     }
 431
 432     pub fn combine_vars(&self,
 433                         t: CombineMapType,
 434                         a: Region,
 435                         b: Region,
 436                         origin: SubregionOrigin,
 437                         relate: |this: &RegionVarBindings,
 438                                  old_r: Region,
 439                                  new_r: Region|)
 440                         -> Region {
 441         let vars = TwoRegions { a: a, b: b };
 442         match self.combine_map(t).borrow().find(&vars) {
 443             Some(&c) => {
 444                 return ReInfer(ReVar(c));
 445             }
 446             None => {}
 447         }
 448         let c = self.new_region_var(infer::MiscVariable(origin.span()));
 449         self.combine_map(t).borrow_mut().insert(vars, c);
 450         if self.in_snapshot() {
 451             self.undo_log.borrow_mut().push(AddCombination(t, vars));
 452         }
 453         relate(self, a, ReInfer(ReVar(c)));
 454         relate(self, b, ReInfer(ReVar(c)));
 455         debug!("combine_vars() c={:?}", c);
 456         ReInfer(ReVar(c))
 457     }
 458
 459     pub fn vars_created_since_mark(&self, mark: RegionMark)
 460                                    -> Vec<RegionVid>
 461     {
 462         self.undo_log.borrow()
 463             .slice_from(mark.length)
 464             .iter()
 465             .filter_map(|&elt| match elt {
 466                 AddVar(vid) => Some(vid),
 467                 _ => None
 468             })
 469             .collect()
 470     }
 471
 472     pub fn tainted(&self, mark: RegionMark, r0: Region) -> Vec<Region> {
 473         /*!
 474          * Computes all regions that have been related to `r0` in any
 475          * way since the mark `mark` was made---`r0` itself will be
 476          * the first entry. This is used when checking whether
 477          * skolemized regions are being improperly related to other
 478          * regions.
 479          */
 480
 481         debug!("tainted(mark={}, r0={})", mark, r0.repr(self.tcx));
 482         let _indenter = indenter();
 483
 484         // `result_set` acts as a worklist: we explore all outgoing
 485         // edges and add any new regions we find to result_set.  This
 486         // is not a terribly efficient implementation.
 487         let mut result_set = vec!(r0);
 488         let mut result_index = 0;
 489         while result_index < result_set.len() {
 490             // nb: can't use uint::range() here because result_set grows
 491             let r = *result_set.get(result_index);
 492             debug!("result_index={}, r={:?}", result_index, r);
 493
 494             for undo_entry in
 495                 self.undo_log.borrow().slice_from(mark.length).iter()
 496             {
 497                 let regs = match undo_entry {
 498                     &AddConstraint(ConstrainVarSubVar(ref a, ref b)) => {
 499                         Some((ReInfer(ReVar(*a)), ReInfer(ReVar(*b))))
 500                     }
 501                     &AddConstraint(ConstrainRegSubVar(ref a, ref b)) => {
 502                         Some((*a, ReInfer(ReVar(*b))))
 503                     }
 504                     &AddConstraint(ConstrainVarSubReg(ref a, ref b)) => {
 505                         Some((ReInfer(ReVar(*a)), *b))
 506                     }
 507                     &AddConstraint(ConstrainRegSubReg(a, b)) => {
 508                         Some((a, b))
 509                     }
 510                     &AddCombination(..) |
 511                     &Mark |
 512                     &AddVar(..) |
 513                     &OpenSnapshot |
 514                     &CommitedSnapshot => {
 515                         None
 516                     }
 517                 };
 518
 519                 match regs {
 520                     None => {}
 521                     Some((r1, r2)) => {
 522                         result_set =
 523                             consider_adding_edge(result_set, r, r1, r2);
 524                         result_set =
 525                             consider_adding_edge(result_set, r, r2, r1);
 526                     }
 527                 }
 528             }
 529
 530             result_index += 1;
 531         }
 532
 533         return result_set;
 534
 535         fn consider_adding_edge(result_set: Vec<Region> ,
 536                                 r: Region,
 537                                 r1: Region,
 538                                 r2: Region) -> Vec<Region> {
 539             let mut result_set = result_set;
 540             if r == r1 { // Clearly, this is potentially inefficient.
 541                 if !result_set.iter().any(|x| *x == r2) {
 542                     result_set.push(r2);
 543                 }
 544             }
 545             return result_set;
 546         }
 547     }
 548
 549     /**
 550     This function performs the actual region resolution.  It must be
 551     called after all constraints have been added.  It performs a
 552     fixed-point iteration to find region values which satisfy all
 553     constraints, assuming such values can be found; if they cannot,
 554     errors are reported.
 555     */
 556     pub fn resolve_regions(&self) -> Vec<RegionResolutionError> {
 557         debug!("RegionVarBindings: resolve_regions()");
 558         let mut errors = vec!();
 559         let v = self.infer_variable_values(&mut errors);
 560         *self.values.borrow_mut() = Some(v);
 561         errors
 562     }
 563 }
 564
 565 impl<'a> RegionVarBindings<'a> {
 566     fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
 567         self.tcx.region_maps.is_subregion_of(sub, sup)
 568     }
 569
 570     fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
 571         match (a, b) {
 572           (ReLateBound(..), _) |
 573           (_, ReLateBound(..)) |
 574           (ReEarlyBound(..), _) |
 575           (_, ReEarlyBound(..)) => {
 576             self.tcx.sess.bug(
 577                 format!("cannot relate bound region: LUB({}, {})",
 578                         a.repr(self.tcx),
 579                         b.repr(self.tcx)).as_slice());
 580           }
 581
 582           (ReStatic, _) | (_, ReStatic) => {
 583             ReStatic // nothing lives longer than static
 584           }
 585
 586           (ReEmpty, r) | (r, ReEmpty) => {
 587             r // everything lives longer than empty
 588           }
 589
 590           (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
 591             self.tcx.sess.span_bug(
 592                 self.var_origins.borrow().get(v_id.index).span(),
 593                 format!("lub_concrete_regions invoked with \
 594                          non-concrete regions: {:?}, {:?}",
 595                         a,
 596                         b).as_slice());
 597           }
 598
 599           (f @ ReFree(ref fr), ReScope(s_id)) |
 600           (ReScope(s_id), f @ ReFree(ref fr)) => {
 601             // A "free" region can be interpreted as "some region
 602             // at least as big as the block fr.scope_id".  So, we can
 603             // reasonably compare free regions and scopes:
 604             match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
 605               // if the free region's scope `fr.scope_id` is bigger than
 606               // the scope region `s_id`, then the LUB is the free
 607               // region itself:
 608               Some(r_id) if r_id == fr.scope_id => f,
 609
 610               // otherwise, we don't know what the free region is,
 611               // so we must conservatively say the LUB is static:
 612               _ => ReStatic
 613             }
 614           }
 615
 616           (ReScope(a_id), ReScope(b_id)) => {
 617             // The region corresponding to an outer block is a
 618             // subtype of the region corresponding to an inner
 619             // block.
 620             match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
 621               Some(r_id) => ReScope(r_id),
 622               _ => ReStatic
 623             }
 624           }
 625
 626           (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 627              self.lub_free_regions(a_fr, b_fr)
 628           }
 629
 630           // For these types, we cannot define any additional
 631           // relationship:
 632           (ReInfer(ReSkolemized(..)), _) |
 633           (_, ReInfer(ReSkolemized(..))) => {
 634             if a == b {a} else {ReStatic}
 635           }
 636         }
 637     }
 638
 639     fn lub_free_regions(&self,
 640                         a: &FreeRegion,
 641                         b: &FreeRegion) -> ty::Region
 642     {
 643         /*!
 644          * Computes a region that encloses both free region arguments.
 645          * Guarantee that if the same two regions are given as argument,
 646          * in any order, a consistent result is returned.
 647          */
 648
 649         return match a.cmp(b) {
 650             Less => helper(self, a, b),
 651             Greater => helper(self, b, a),
 652             Equal => ty::ReFree(*a)
 653         };
 654
 655         fn helper(this: &RegionVarBindings,
 656                   a: &FreeRegion,
 657                   b: &FreeRegion) -> ty::Region
 658         {
 659             if this.tcx.region_maps.sub_free_region(*a, *b) {
 660                 ty::ReFree(*b)
 661             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 662                 ty::ReFree(*a)
 663             } else {
 664                 ty::ReStatic
 665             }
 666         }
 667     }
 668
 669     fn glb_concrete_regions(&self,
 670                             a: Region,
 671                             b: Region)
 672                          -> cres<Region> {
 673         debug!("glb_concrete_regions({:?}, {:?})", a, b);
 674         match (a, b) {
 675             (ReLateBound(..), _) |
 676             (_, ReLateBound(..)) |
 677             (ReEarlyBound(..), _) |
 678             (_, ReEarlyBound(..)) => {
 679               self.tcx.sess.bug(
 680                   format!("cannot relate bound region: GLB({}, {})",
 681                           a.repr(self.tcx),
 682                           b.repr(self.tcx)).as_slice());
 683             }
 684
 685             (ReStatic, r) | (r, ReStatic) => {
 686                 // static lives longer than everything else
 687                 Ok(r)
 688             }
 689
 690             (ReEmpty, _) | (_, ReEmpty) => {
 691                 // nothing lives shorter than everything else
 692                 Ok(ReEmpty)
 693             }
 694
 695             (ReInfer(ReVar(v_id)), _) |
 696             (_, ReInfer(ReVar(v_id))) => {
 697                 self.tcx.sess.span_bug(
 698                     self.var_origins.borrow().get(v_id.index).span(),
 699                     format!("glb_concrete_regions invoked with \
 700                              non-concrete regions: {:?}, {:?}",
 701                             a,
 702                             b).as_slice());
 703             }
 704
 705             (ReFree(ref fr), s @ ReScope(s_id)) |
 706             (s @ ReScope(s_id), ReFree(ref fr)) => {
 707                 // Free region is something "at least as big as
 708                 // `fr.scope_id`."  If we find that the scope `fr.scope_id` is bigger
 709                 // than the scope `s_id`, then we can say that the GLB
 710                 // is the scope `s_id`.  Otherwise, as we do not know
 711                 // big the free region is precisely, the GLB is undefined.
 712                 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
 713                     Some(r_id) if r_id == fr.scope_id => Ok(s),
 714                     _ => Err(ty::terr_regions_no_overlap(b, a))
 715                 }
 716             }
 717
 718             (ReScope(a_id), ReScope(b_id)) => {
 719                 self.intersect_scopes(a, b, a_id, b_id)
 720             }
 721
 722             (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 723                 self.glb_free_regions(a_fr, b_fr)
 724             }
 725
 726             // For these types, we cannot define any additional
 727             // relationship:
 728             (ReInfer(ReSkolemized(..)), _) |
 729             (_, ReInfer(ReSkolemized(..))) => {
 730                 if a == b {
 731                     Ok(a)
 732                 } else {
 733                     Err(ty::terr_regions_no_overlap(b, a))
 734                 }
 735             }
 736         }
 737     }
 738
 739     fn glb_free_regions(&self,
 740                         a: &FreeRegion,
 741                         b: &FreeRegion) -> cres<ty::Region>
 742     {
 743         /*!
 744          * Computes a region that is enclosed by both free region arguments,
 745          * if any. Guarantees that if the same two regions are given as argument,
 746          * in any order, a consistent result is returned.
 747          */
 748
 749         return match a.cmp(b) {
 750             Less => helper(self, a, b),
 751             Greater => helper(self, b, a),
 752             Equal => Ok(ty::ReFree(*a))
 753         };
 754
 755         fn helper(this: &RegionVarBindings,
 756                   a: &FreeRegion,
 757                   b: &FreeRegion) -> cres<ty::Region>
 758         {
 759             if this.tcx.region_maps.sub_free_region(*a, *b) {
 760                 Ok(ty::ReFree(*a))
 761             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 762                 Ok(ty::ReFree(*b))
 763             } else {
 764                 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
 765                                       a.scope_id, b.scope_id)
 766             }
 767         }
 768     }
 769
 770     fn intersect_scopes(&self,
 771                         region_a: ty::Region,
 772                         region_b: ty::Region,
 773                         scope_a: ast::NodeId,
 774                         scope_b: ast::NodeId) -> cres<Region>
 775     {
 776         // We want to generate the intersection of two
 777         // scopes or two free regions.  So, if one of
 778         // these scopes is a subscope of the other, return
 779         // it.  Otherwise fail.
 780         debug!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
 781                scope_a, scope_b, region_a, region_b);
 782         match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
 783             Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
 784             Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
 785             _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
 786         }
 787     }
 788 }
 789
 790 // ______________________________________________________________________
 791
 792 #[deriving(PartialEq, Show)]
 793 enum Classification { Expanding, Contracting }
 794
 795 pub enum VarValue { NoValue, Value(Region), ErrorValue }
 796
 797 struct VarData {
 798     classification: Classification,
 799     value: VarValue,
 800 }
 801
 802 struct RegionAndOrigin {
 803     region: Region,
 804     origin: SubregionOrigin,
 805 }
 806
 807 type RegionGraph = graph::Graph<(), Constraint>;
 808
 809 impl<'a> RegionVarBindings<'a> {
 810     fn infer_variable_values(&self,
 811                              errors: &mut Vec<RegionResolutionError>)
 812                              -> Vec<VarValue> {
 813         let mut var_data = self.construct_var_data();
 814         self.expansion(var_data.as_mut_slice());
 815         self.contraction(var_data.as_mut_slice());
 816         self.collect_concrete_region_errors(&mut *errors);
 817         self.extract_values_and_collect_conflicts(var_data.as_slice(), errors)
 818     }
 819
 820     fn construct_var_data(&self) -> Vec<VarData> {
 821         Vec::from_fn(self.num_vars(), |_| {
 822             VarData {
 823                 // All nodes are initially classified as contracting; during
 824                 // the expansion phase, we will shift the classification for
 825                 // those nodes that have a concrete region predecessor to
 826                 // Expanding.
 827                 classification: Contracting,
 828                 value: NoValue,
 829             }
 830         })
 831     }
 832
 833     fn expansion(&self, var_data: &mut [VarData]) {
 834         self.iterate_until_fixed_point("Expansion", |constraint| {
 835             match *constraint {
 836               ConstrainRegSubVar(a_region, b_vid) => {
 837                 let b_data = &mut var_data[b_vid.index];
 838                 self.expand_node(a_region, b_vid, b_data)
 839               }
 840               ConstrainVarSubVar(a_vid, b_vid) => {
 841                 match var_data[a_vid.index].value {
 842                   NoValue | ErrorValue => false,
 843                   Value(a_region) => {
 844                     let b_node = &mut var_data[b_vid.index];
 845                     self.expand_node(a_region, b_vid, b_node)
 846                   }
 847                 }
 848               }
 849               ConstrainVarSubReg(..) => {
 850                 // This is a contraction constraint.  Ignore it.
 851                 false
 852               }
 853               ConstrainRegSubReg(..) => {
 854                 // No region variables involved. Ignore.
 855                 false
 856               }
 857             }
 858         })
 859     }
 860
 861     fn expand_node(&self,
 862                    a_region: Region,
 863                    b_vid: RegionVid,
 864                    b_data: &mut VarData)
 865                    -> bool {
 866         debug!("expand_node({:?}, {:?} == {:?})",
 867                a_region, b_vid, b_data.value);
 868
 869         b_data.classification = Expanding;
 870         match b_data.value {
 871           NoValue => {
 872             debug!("Setting initial value of {:?} to {:?}", b_vid, a_region);
 873
 874             b_data.value = Value(a_region);
 875             return true;
 876           }
 877
 878           Value(cur_region) => {
 879             let lub = self.lub_concrete_regions(a_region, cur_region);
 880             if lub == cur_region {
 881                 return false;
 882             }
 883
 884             debug!("Expanding value of {:?} from {:?} to {:?}",
 885                    b_vid, cur_region, lub);
 886
 887             b_data.value = Value(lub);
 888             return true;
 889           }
 890
 891           ErrorValue => {
 892             return false;
 893           }
 894         }
 895     }
 896
 897     fn contraction(&self,
 898                    var_data: &mut [VarData]) {
 899         self.iterate_until_fixed_point("Contraction", |constraint| {
 900             match *constraint {
 901               ConstrainRegSubVar(..) => {
 902                 // This is an expansion constraint.  Ignore.
 903                 false
 904               }
 905               ConstrainVarSubVar(a_vid, b_vid) => {
 906                 match var_data[b_vid.index].value {
 907                   NoValue | ErrorValue => false,
 908                   Value(b_region) => {
 909                     let a_data = &mut var_data[a_vid.index];
 910                     self.contract_node(a_vid, a_data, b_region)
 911                   }
 912                 }
 913               }
 914               ConstrainVarSubReg(a_vid, b_region) => {
 915                 let a_data = &mut var_data[a_vid.index];
 916                 self.contract_node(a_vid, a_data, b_region)
 917               }
 918               ConstrainRegSubReg(..) => {
 919                 // No region variables involved. Ignore.
 920                 false
 921               }
 922             }
 923         })
 924     }
 925
 926     fn contract_node(&self,
 927                      a_vid: RegionVid,
 928                      a_data: &mut VarData,
 929                      b_region: Region)
 930                      -> bool {
 931         debug!("contract_node({:?} == {:?}/{:?}, {:?})",
 932                a_vid, a_data.value, a_data.classification, b_region);
 933
 934         return match a_data.value {
 935             NoValue => {
 936                 assert_eq!(a_data.classification, Contracting);
 937                 a_data.value = Value(b_region);
 938                 true // changed
 939             }
 940
 941             ErrorValue => {
 942                 false // no change
 943             }
 944
 945             Value(a_region) => {
 946                 match a_data.classification {
 947                     Expanding => {
 948                         check_node(self, a_vid, a_data, a_region, b_region)
 949                     }
 950                     Contracting => {
 951                         adjust_node(self, a_vid, a_data, a_region, b_region)
 952                     }
 953                 }
 954             }
 955         };
 956
 957         fn check_node(this: &RegionVarBindings,
 958                       a_vid: RegionVid,
 959                       a_data: &mut VarData,
 960                       a_region: Region,
 961                       b_region: Region)
 962                    -> bool {
 963             if !this.is_subregion_of(a_region, b_region) {
 964                 debug!("Setting {:?} to ErrorValue: {:?} not subregion of {:?}",
 965                        a_vid, a_region, b_region);
 966                 a_data.value = ErrorValue;
 967             }
 968             false
 969         }
 970
 971         fn adjust_node(this: &RegionVarBindings,
 972                        a_vid: RegionVid,
 973                        a_data: &mut VarData,
 974                        a_region: Region,
 975                        b_region: Region)
 976                     -> bool {
 977             match this.glb_concrete_regions(a_region, b_region) {
 978                 Ok(glb) => {
 979                     if glb == a_region {
 980                         false
 981                     } else {
 982                         debug!("Contracting value of {:?} from {:?} to {:?}",
 983                                a_vid, a_region, glb);
 984                         a_data.value = Value(glb);
 985                         true
 986                     }
 987                 }
 988                 Err(_) => {
 989                     debug!("Setting {:?} to ErrorValue: no glb of {:?}, {:?}",
 990                            a_vid, a_region, b_region);
 991                     a_data.value = ErrorValue;
 992                     false
 993                 }
 994             }
 995         }
 996     }
 997
 998     fn collect_concrete_region_errors(
 999         &self,
1000         errors: &mut Vec<RegionResolutionError>)
1001     {
1002         for (constraint, _) in self.constraints.borrow().iter() {
1003             let (sub, sup) = match *constraint {
1004                 ConstrainVarSubVar(..) |
1005                 ConstrainRegSubVar(..) |
1006                 ConstrainVarSubReg(..) => {
1007                     continue;
1008                 }
1009                 ConstrainRegSubReg(sub, sup) => {
1010                     (sub, sup)
1011                 }
1012             };
1013
1014             if self.is_subregion_of(sub, sup) {
1015                 continue;
1016             }
1017
1018             debug!("ConcreteFailure: !(sub <= sup): sub={:?}, sup={:?}",
1019                    sub, sup);
1020             let origin = self.constraints.borrow().get_copy(constraint);
1021             errors.push(ConcreteFailure(origin, sub, sup));
1022         }
1023     }
1024
1025     fn extract_values_and_collect_conflicts(
1026         &self,
1027         var_data: &[VarData],
1028         errors: &mut Vec<RegionResolutionError>)
1029         -> Vec<VarValue> {
1030         debug!("extract_values_and_collect_conflicts()");
1031
1032         // This is the best way that I have found to suppress
1033         // duplicate and related errors. Basically we keep a set of
1034         // flags for every node. Whenever an error occurs, we will
1035         // walk some portion of the graph looking to find pairs of
1036         // conflicting regions to report to the user. As we walk, we
1037         // trip the flags from false to true, and if we find that
1038         // we've already reported an error involving any particular
1039         // node we just stop and don't report the current error.  The
1040         // idea is to report errors that derive from independent
1041         // regions of the graph, but not those that derive from
1042         // overlapping locations.
1043         let mut dup_vec = Vec::from_elem(self.num_vars(), uint::MAX);
1044
1045         let mut opt_graph = None;
1046
1047         for idx in range(0u, self.num_vars()) {
1048             match var_data[idx].value {
1049                 Value(_) => {
1050                     /* Inference successful */
1051                 }
1052                 NoValue => {
1053                     /* Unconstrained inference: do not report an error
1054                        until the value of this variable is requested.
1055                        After all, sometimes we make region variables but never
1056                        really use their values. */
1057                 }
1058                 ErrorValue => {
1059                     /* Inference impossible, this value contains
1060                        inconsistent constraints.
1061
1062                        I think that in this case we should report an
1063                        error now---unlike the case above, we can't
1064                        wait to see whether the user needs the result
1065                        of this variable.  The reason is that the mere
1066                        existence of this variable implies that the
1067                        region graph is inconsistent, whether or not it
1068                        is used.
1069
1070                        For example, we may have created a region
1071                        variable that is the GLB of two other regions
1072                        which do not have a GLB.  Even if that variable
1073                        is not used, it implies that those two regions
1074                        *should* have a GLB.
1075
1076                        At least I think this is true. It may be that
1077                        the mere existence of a conflict in a region variable
1078                        that is not used is not a problem, so if this rule
1079                        starts to create problems we'll have to revisit
1080                        this portion of the code and think hard about it. =) */
1081
1082                     if opt_graph.is_none() {
1083                         opt_graph = Some(self.construct_graph());
1084                     }
1085                     let graph = opt_graph.get_ref();
1086
1087                     let node_vid = RegionVid { index: idx };
1088                     match var_data[idx].classification {
1089                         Expanding => {
1090                             self.collect_error_for_expanding_node(
1091                                 graph, var_data, dup_vec.as_mut_slice(),
1092                                 node_vid, errors);
1093                         }
1094                         Contracting => {
1095                             self.collect_error_for_contracting_node(
1096                                 graph, var_data, dup_vec.as_mut_slice(),
1097                                 node_vid, errors);
1098                         }
1099                     }
1100                 }
1101             }
1102         }
1103
1104         Vec::from_fn(self.num_vars(), |idx| var_data[idx].value)
1105     }
1106
1107     fn construct_graph(&self) -> RegionGraph {
1108         let num_vars = self.num_vars();
1109
1110         let constraints = self.constraints.borrow();
1111         let num_edges = constraints.len();
1112
1113         let mut graph = graph::Graph::with_capacity(num_vars + 1,
1114                                                     num_edges);
1115
1116         for _ in range(0u, num_vars) {
1117             graph.add_node(());
1118         }
1119         let dummy_idx = graph.add_node(());
1120
1121         for (constraint, _) in constraints.iter() {
1122             match *constraint {
1123                 ConstrainVarSubVar(a_id, b_id) => {
1124                     graph.add_edge(NodeIndex(a_id.index),
1125                                    NodeIndex(b_id.index),
1126                                    *constraint);
1127                 }
1128                 ConstrainRegSubVar(_, b_id) => {
1129                     graph.add_edge(dummy_idx,
1130                                    NodeIndex(b_id.index),
1131                                    *constraint);
1132                 }
1133                 ConstrainVarSubReg(a_id, _) => {
1134                     graph.add_edge(NodeIndex(a_id.index),
1135                                    dummy_idx,
1136                                    *constraint);
1137                 }
1138                 ConstrainRegSubReg(..) => {
1139                     // Relations between two concrete regions do not
1140                     // require an edge in the graph.
1141                 }
1142             }
1143         }
1144
1145         return graph;
1146     }
1147
1148     fn collect_error_for_expanding_node(
1149         &self,
1150         graph: &RegionGraph,
1151         var_data: &[VarData],
1152         dup_vec: &mut [uint],
1153         node_idx: RegionVid,
1154         errors: &mut Vec<RegionResolutionError>)
1155     {
1156         // Errors in expanding nodes result from a lower-bound that is
1157         // not contained by an upper-bound.
1158         let (mut lower_bounds, lower_dup) =
1159             self.collect_concrete_regions(graph, var_data, node_idx,
1160                                           graph::Incoming, dup_vec);
1161         let (mut upper_bounds, upper_dup) =
1162             self.collect_concrete_regions(graph, var_data, node_idx,
1163                                           graph::Outgoing, dup_vec);
1164
1165         if lower_dup || upper_dup {
1166             return;
1167         }
1168
1169         // We place free regions first because we are special casing
1170         // SubSupConflict(ReFree, ReFree) when reporting error, and so
1171         // the user will more likely get a specific suggestion.
1172         fn free_regions_first(a: &RegionAndOrigin,
1173                               b: &RegionAndOrigin)
1174                               -> Ordering {
1175             match (a.region, b.region) {
1176                 (ReFree(..), ReFree(..)) => Equal,
1177                 (ReFree(..), _) => Less,
1178                 (_, ReFree(..)) => Greater,
1179                 (_, _) => Equal,
1180             }
1181         }
1182         lower_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1183         upper_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1184
1185         for lower_bound in lower_bounds.iter() {
1186             for upper_bound in upper_bounds.iter() {
1187                 if !self.is_subregion_of(lower_bound.region,
1188                                          upper_bound.region) {
1189                     errors.push(SubSupConflict(
1190                         self.var_origins.borrow().get(node_idx.index).clone(),
1191                         lower_bound.origin.clone(),
1192                         lower_bound.region,
1193                         upper_bound.origin.clone(),
1194                         upper_bound.region));
1195                     return;
1196                 }
1197             }
1198         }
1199
1200         self.tcx.sess.span_bug(
1201             self.var_origins.borrow().get(node_idx.index).span(),
1202             format!("collect_error_for_expanding_node() could not find error \
1203                   for var {:?}, lower_bounds={}, upper_bounds={}",
1204                  node_idx,
1205                  lower_bounds.iter()
1206                              .map(|x| x.region)
1207                              .collect::<Vec<ty::Region>>()
1208                              .repr(self.tcx),
1209                  upper_bounds.iter()
1210                              .map(|x| x.region)
1211                              .collect::<Vec<ty::Region>>()
1212                              .repr(self.tcx)).as_slice());
1213     }
1214
1215     fn collect_error_for_contracting_node(
1216         &self,
1217         graph: &RegionGraph,
1218         var_data: &[VarData],
1219         dup_vec: &mut [uint],
1220         node_idx: RegionVid,
1221         errors: &mut Vec<RegionResolutionError>)
1222     {
1223         // Errors in contracting nodes result from two upper-bounds
1224         // that have no intersection.
1225         let (upper_bounds, dup_found) =
1226             self.collect_concrete_regions(graph, var_data, node_idx,
1227                                           graph::Outgoing, dup_vec);
1228
1229         if dup_found {
1230             return;
1231         }
1232
1233         for upper_bound_1 in upper_bounds.iter() {
1234             for upper_bound_2 in upper_bounds.iter() {
1235                 match self.glb_concrete_regions(upper_bound_1.region,
1236                                                 upper_bound_2.region) {
1237                   Ok(_) => {}
1238                   Err(_) => {
1239                     errors.push(SupSupConflict(
1240                         self.var_origins.borrow().get(node_idx.index).clone(),
1241                         upper_bound_1.origin.clone(),
1242                         upper_bound_1.region,
1243                         upper_bound_2.origin.clone(),
1244                         upper_bound_2.region));
1245                     return;
1246                   }
1247                 }
1248             }
1249         }
1250
1251         self.tcx.sess.span_bug(
1252             self.var_origins.borrow().get(node_idx.index).span(),
1253             format!("collect_error_for_contracting_node() could not find error \
1254                   for var {:?}, upper_bounds={}",
1255                  node_idx,
1256                  upper_bounds.iter()
1257                              .map(|x| x.region)
1258                              .collect::<Vec<ty::Region>>()
1259                              .repr(self.tcx)).as_slice());
1260     }
1261
1262     fn collect_concrete_regions(&self,
1263                                 graph: &RegionGraph,
1264                                 var_data: &[VarData],
1265                                 orig_node_idx: RegionVid,
1266                                 dir: Direction,
1267                                 dup_vec: &mut [uint])
1268                                 -> (Vec<RegionAndOrigin> , bool) {
1269         struct WalkState {
1270             set: HashSet<RegionVid>,
1271             stack: Vec<RegionVid> ,
1272             result: Vec<RegionAndOrigin> ,
1273             dup_found: bool
1274         }
1275         let mut state = WalkState {
1276             set: HashSet::new(),
1277             stack: vec!(orig_node_idx),
1278             result: Vec::new(),
1279             dup_found: false
1280         };
1281         state.set.insert(orig_node_idx);
1282
1283         // to start off the process, walk the source node in the
1284         // direction specified
1285         process_edges(self, &mut state, graph, orig_node_idx, dir);
1286
1287         while !state.stack.is_empty() {
1288             let node_idx = state.stack.pop().unwrap();
1289             let classification = var_data[node_idx.index].classification;
1290
1291             // check whether we've visited this node on some previous walk
1292             if dup_vec[node_idx.index] == uint::MAX {
1293                 dup_vec[node_idx.index] = orig_node_idx.index;
1294             } else if dup_vec[node_idx.index] != orig_node_idx.index {
1295                 state.dup_found = true;
1296             }
1297
1298             debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1299                     classification={:?})",
1300                    orig_node_idx, node_idx, classification);
1301
1302             // figure out the direction from which this node takes its
1303             // values, and search for concrete regions etc in that direction
1304             let dir = match classification {
1305                 Expanding => graph::Incoming,
1306                 Contracting => graph::Outgoing,
1307             };
1308
1309             process_edges(self, &mut state, graph, node_idx, dir);
1310         }
1311
1312         let WalkState {result, dup_found, ..} = state;
1313         return (result, dup_found);
1314
1315         fn process_edges(this: &RegionVarBindings,
1316                          state: &mut WalkState,
1317                          graph: &RegionGraph,
1318                          source_vid: RegionVid,
1319                          dir: Direction) {
1320             debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1321
1322             let source_node_index = NodeIndex(source_vid.index);
1323             graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
1324                 match edge.data {
1325                     ConstrainVarSubVar(from_vid, to_vid) => {
1326                         let opp_vid =
1327                             if from_vid == source_vid {to_vid} else {from_vid};
1328                         if state.set.insert(opp_vid) {
1329                             state.stack.push(opp_vid);
1330                         }
1331                     }
1332
1333                     ConstrainRegSubVar(region, _) |
1334                     ConstrainVarSubReg(_, region) => {
1335                         state.result.push(RegionAndOrigin {
1336                             region: region,
1337                             origin: this.constraints.borrow().get_copy(&edge.data)
1338                         });
1339                     }
1340
1341                     ConstrainRegSubReg(..) => {}
1342                 }
1343                 true
1344             });
1345         }
1346     }
1347
1348     fn iterate_until_fixed_point(&self,
1349                                  tag: &str,
1350                                  body: |constraint: &Constraint| -> bool) {
1351         let mut iteration = 0;
1352         let mut changed = true;
1353         while changed {
1354             changed = false;
1355             iteration += 1;
1356             debug!("---- {} Iteration {}{}", "#", tag, iteration);
1357             for (constraint, _) in self.constraints.borrow().iter() {
1358                 let edge_changed = body(constraint);
1359                 if edge_changed {
1360                     debug!("Updated due to constraint {}",
1361                            constraint.repr(self.tcx));
1362                     changed = true;
1363                 }
1364             }
1365         }
1366         debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1367     }
1368
1369 }
1370
1371 impl Repr for Constraint {
1372     fn repr(&self, tcx: &ty::ctxt) -> String {
1373         match *self {
1374             ConstrainVarSubVar(a, b) => {
1375                 format!("ConstrainVarSubVar({}, {})", a.repr(tcx), b.repr(tcx))
1376             }
1377             ConstrainRegSubVar(a, b) => {
1378                 format!("ConstrainRegSubVar({}, {})", a.repr(tcx), b.repr(tcx))
1379             }
1380             ConstrainVarSubReg(a, b) => {
1381                 format!("ConstrainVarSubReg({}, {})", a.repr(tcx), b.repr(tcx))
1382             }
1383             ConstrainRegSubReg(a, b) => {
1384                 format!("ConstrainRegSubReg({}, {})", a.repr(tcx), b.repr(tcx))
1385             }
1386         }
1387     }
1388 }