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