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