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::cmp::Ordering::{mod, Less, Greater, Equal};
  37 use std::iter::repeat;
  38 use std::u32;
  39 use syntax::ast;
  40
  41 mod doc;
  42 mod graphviz;
  43
  44 // A constraint that influences the inference process.
  45 #[deriving(Clone, Copy, PartialEq, Eq, Hash, Show)]
  46 pub enum Constraint {
  47     // One region variable is subregion of another
  48     ConstrainVarSubVar(RegionVid, RegionVid),
  49
  50     // Concrete region is subregion of region variable
  51     ConstrainRegSubVar(Region, RegionVid),
  52
  53     // Region variable is subregion of concrete region
  54     ConstrainVarSubReg(RegionVid, Region),
  55 }
  56
  57 // Something we have to verify after region inference is done, but
  58 // which does not directly influence the inference process
  59 pub enum Verify<'tcx> {
  60     // VerifyRegSubReg(a, b): Verify that `a <= b`. Neither `a` nor
  61     // `b` are inference variables.
  62     VerifyRegSubReg(SubregionOrigin<'tcx>, Region, Region),
  63
  64     // VerifyParamBound(T, _, R, RS): The parameter type `T` must
  65     // outlive the region `R`. `T` is known to outlive `RS`. Therefore
  66     // verify that `R <= RS[i]` for some `i`. Inference variables may
  67     // be involved (but this verification step doesn't influence
  68     // inference).
  69     VerifyParamBound(ty::ParamTy, SubregionOrigin<'tcx>, Region, Vec<Region>),
  70 }
  71
  72 #[deriving(Copy, PartialEq, Eq, Hash)]
  73 pub struct TwoRegions {
  74     a: Region,
  75     b: Region,
  76 }
  77
  78 #[deriving(Copy, PartialEq)]
  79 pub enum UndoLogEntry {
  80     OpenSnapshot,
  81     CommitedSnapshot,
  82     AddVar(RegionVid),
  83     AddConstraint(Constraint),
  84     AddVerify(uint),
  85     AddGiven(ty::FreeRegion, ty::RegionVid),
  86     AddCombination(CombineMapType, TwoRegions)
  87 }
  88
  89 #[deriving(Copy, PartialEq)]
  90 pub enum CombineMapType {
  91     Lub, Glb
  92 }
  93
  94 #[deriving(Clone, Show)]
  95 pub enum RegionResolutionError<'tcx> {
  96     /// `ConcreteFailure(o, a, b)`:
  97     ///
  98     /// `o` requires that `a <= b`, but this does not hold
  99     ConcreteFailure(SubregionOrigin<'tcx>, Region, Region),
 100
 101     /// `ParamBoundFailure(p, s, a, bs)
 102     ///
 103     /// The parameter type `p` must be known to outlive the lifetime
 104     /// `a`, but it is only known to outlive `bs` (and none of the
 105     /// regions in `bs` outlive `a`).
 106     ParamBoundFailure(SubregionOrigin<'tcx>, ty::ParamTy, Region, Vec<Region>),
 107
 108     /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
 109     ///
 110     /// Could not infer a value for `v` because `sub_r <= v` (due to
 111     /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
 112     /// `sub_r <= sup_r` does not hold.
 113     SubSupConflict(RegionVariableOrigin<'tcx>,
 114                    SubregionOrigin<'tcx>, Region,
 115                    SubregionOrigin<'tcx>, Region),
 116
 117     /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
 118     ///
 119     /// Could not infer a value for `v` because `v <= r1` (due to
 120     /// `origin1`) and `v <= r2` (due to `origin2`) and
 121     /// `r1` and `r2` have no intersection.
 122     SupSupConflict(RegionVariableOrigin<'tcx>,
 123                    SubregionOrigin<'tcx>, Region,
 124                    SubregionOrigin<'tcx>, Region),
 125
 126     /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
 127     /// more specific errors message by suggesting to the user where they
 128     /// should put a lifetime. In those cases we process and put those errors
 129     /// into `ProcessedErrors` before we do any reporting.
 130     ProcessedErrors(Vec<RegionVariableOrigin<'tcx>>,
 131                     Vec<(TypeTrace<'tcx>, ty::type_err<'tcx>)>,
 132                     Vec<SameRegions>),
 133 }
 134
 135 /// SameRegions is used to group regions that we think are the same and would
 136 /// like to indicate so to the user.
 137 /// For example, the following function
 138 /// ```
 139 /// struct Foo { bar: int }
 140 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
 141 ///    &x.bar
 142 /// }
 143 /// ```
 144 /// would report an error because we expect 'a and 'b to match, and so we group
 145 /// 'a and 'b together inside a SameRegions struct
 146 #[deriving(Clone, Show)]
 147 pub struct SameRegions {
 148     pub scope_id: ast::NodeId,
 149     pub regions: Vec<BoundRegion>
 150 }
 151
 152 impl SameRegions {
 153     pub fn contains(&self, other: &BoundRegion) -> bool {
 154         self.regions.contains(other)
 155     }
 156
 157     pub fn push(&mut self, other: BoundRegion) {
 158         self.regions.push(other);
 159     }
 160 }
 161
 162 pub type CombineMap = FnvHashMap<TwoRegions, RegionVid>;
 163
 164 pub struct RegionVarBindings<'a, 'tcx: 'a> {
 165     tcx: &'a ty::ctxt<'tcx>,
 166     var_origins: RefCell<Vec<RegionVariableOrigin<'tcx>>>,
 167
 168     // Constraints of the form `A <= B` introduced by the region
 169     // checker.  Here at least one of `A` and `B` must be a region
 170     // variable.
 171     constraints: RefCell<FnvHashMap<Constraint, SubregionOrigin<'tcx>>>,
 172
 173     // A "verify" is something that we need to verify after inference is
 174     // done, but which does not directly affect inference in any way.
 175     //
 176     // An example is a `A <= B` where neither `A` nor `B` are
 177     // inference variables.
 178     verifys: RefCell<Vec<Verify<'tcx>>>,
 179
 180     // A "given" is a relationship that is known to hold. In particular,
 181     // we often know from closure fn signatures that a particular free
 182     // region must be a subregion of a region variable:
 183     //
 184     //    foo.iter().filter(<'a> |x: &'a &'b T| ...)
 185     //
 186     // In situations like this, `'b` is in fact a region variable
 187     // introduced by the call to `iter()`, and `'a` is a bound region
 188     // on the closure (as indicated by the `<'a>` prefix). If we are
 189     // naive, we wind up inferring that `'b` must be `'static`,
 190     // because we require that it be greater than `'a` and we do not
 191     // know what `'a` is precisely.
 192     //
 193     // This hashmap is used to avoid that naive scenario. Basically we
 194     // record the fact that `'a <= 'b` is implied by the fn signature,
 195     // and then ignore the constraint when solving equations. This is
 196     // a bit of a hack but seems to work.
 197     givens: RefCell<FnvHashSet<(ty::FreeRegion, ty::RegionVid)>>,
 198
 199     lubs: RefCell<CombineMap>,
 200     glbs: RefCell<CombineMap>,
 201     skolemization_count: Cell<u32>,
 202     bound_count: Cell<u32>,
 203
 204     // The undo log records actions that might later be undone.
 205     //
 206     // Note: when the undo_log is empty, we are not actively
 207     // snapshotting. When the `start_snapshot()` method is called, we
 208     // push an OpenSnapshot entry onto the list to indicate that we
 209     // are now actively snapshotting. The reason for this is that
 210     // otherwise we end up adding entries for things like the lower
 211     // bound on a variable and so forth, which can never be rolled
 212     // back.
 213     undo_log: RefCell<Vec<UndoLogEntry>>,
 214
 215     // This contains the results of inference.  It begins as an empty
 216     // option and only acquires a value after inference is complete.
 217     values: RefCell<Option<Vec<VarValue>>>,
 218 }
 219
 220 #[deriving(Show)]
 221 #[allow(missing_copy_implementations)]
 222 pub struct RegionSnapshot {
 223     length: uint,
 224     skolemization_count: u32,
 225 }
 226
 227 impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 228     pub fn new(tcx: &'a ty::ctxt<'tcx>) -> RegionVarBindings<'a, 'tcx> {
 229         RegionVarBindings {
 230             tcx: tcx,
 231             var_origins: RefCell::new(Vec::new()),
 232             values: RefCell::new(None),
 233             constraints: RefCell::new(FnvHashMap::new()),
 234             verifys: RefCell::new(Vec::new()),
 235             givens: RefCell::new(FnvHashSet::new()),
 236             lubs: RefCell::new(FnvHashMap::new()),
 237             glbs: RefCell::new(FnvHashMap::new()),
 238             skolemization_count: Cell::new(0),
 239             bound_count: Cell::new(0),
 240             undo_log: RefCell::new(Vec::new())
 241         }
 242     }
 243
 244     fn in_snapshot(&self) -> bool {
 245         self.undo_log.borrow().len() > 0
 246     }
 247
 248     pub fn start_snapshot(&self) -> RegionSnapshot {
 249         let length = self.undo_log.borrow().len();
 250         debug!("RegionVarBindings: start_snapshot({})", length);
 251         self.undo_log.borrow_mut().push(OpenSnapshot);
 252         RegionSnapshot { length: length, skolemization_count: self.skolemization_count.get() }
 253     }
 254
 255     pub fn commit(&self, snapshot: RegionSnapshot) {
 256         debug!("RegionVarBindings: commit({})", snapshot.length);
 257         assert!(self.undo_log.borrow().len() > snapshot.length);
 258         assert!((*self.undo_log.borrow())[snapshot.length] == OpenSnapshot);
 259
 260         let mut undo_log = self.undo_log.borrow_mut();
 261         if snapshot.length == 0 {
 262             undo_log.truncate(0);
 263         } else {
 264             (*undo_log)[snapshot.length] = CommitedSnapshot;
 265         }
 266         self.skolemization_count.set(snapshot.skolemization_count);
 267     }
 268
 269     pub fn rollback_to(&self, snapshot: RegionSnapshot) {
 270         debug!("RegionVarBindings: rollback_to({})", snapshot);
 271         let mut undo_log = self.undo_log.borrow_mut();
 272         assert!(undo_log.len() > snapshot.length);
 273         assert!((*undo_log)[snapshot.length] == OpenSnapshot);
 274         while undo_log.len() > snapshot.length + 1 {
 275             match undo_log.pop().unwrap() {
 276                 OpenSnapshot => {
 277                     panic!("Failure to observe stack discipline");
 278                 }
 279                 CommitedSnapshot => { }
 280                 AddVar(vid) => {
 281                     let mut var_origins = self.var_origins.borrow_mut();
 282                     var_origins.pop().unwrap();
 283                     assert_eq!(var_origins.len(), vid.index as uint);
 284                 }
 285                 AddConstraint(ref constraint) => {
 286                     self.constraints.borrow_mut().remove(constraint);
 287                 }
 288                 AddVerify(index) => {
 289                     self.verifys.borrow_mut().pop();
 290                     assert_eq!(self.verifys.borrow().len(), index);
 291                 }
 292                 AddGiven(sub, sup) => {
 293                     self.givens.borrow_mut().remove(&(sub, sup));
 294                 }
 295                 AddCombination(Glb, ref regions) => {
 296                     self.glbs.borrow_mut().remove(regions);
 297                 }
 298                 AddCombination(Lub, ref regions) => {
 299                     self.lubs.borrow_mut().remove(regions);
 300                 }
 301             }
 302         }
 303         let c = undo_log.pop().unwrap();
 304         assert!(c == OpenSnapshot);
 305         self.skolemization_count.set(snapshot.skolemization_count);
 306     }
 307
 308     pub fn num_vars(&self) -> u32 {
 309         let len = self.var_origins.borrow().len();
 310         // enforce no overflow
 311         assert!(len as u32 as uint == len);
 312         len as u32
 313     }
 314
 315     pub fn new_region_var(&self, origin: RegionVariableOrigin<'tcx>) -> RegionVid {
 316         let id = self.num_vars();
 317         self.var_origins.borrow_mut().push(origin.clone());
 318         let vid = RegionVid { index: id };
 319         if self.in_snapshot() {
 320             self.undo_log.borrow_mut().push(AddVar(vid));
 321         }
 322         debug!("created new region variable {} with origin {}",
 323                vid, origin.repr(self.tcx));
 324         return vid;
 325     }
 326
 327     /// Creates a new skolemized region. Skolemized regions are fresh
 328     /// regions used when performing higher-ranked computations. They
 329     /// must be used in a very particular way and are never supposed
 330     /// to "escape" out into error messages or the code at large.
 331     ///
 332     /// The idea is to always create a snapshot. Skolemized regions
 333     /// can be created in the context of this snapshot, but once the
 334     /// snapshot is commited or rolled back, their numbers will be
 335     /// recycled, so you must be finished with them. See the extensive
 336     /// comments in `higher_ranked.rs` to see how it works (in
 337     /// particular, the subtyping comparison).
 338     ///
 339     /// The `snapshot` argument to this function is not really used;
 340     /// it's just there to make it explicit which snapshot bounds the
 341     /// skolemized region that results.
 342     pub fn new_skolemized(&self, br: ty::BoundRegion, snapshot: &RegionSnapshot) -> Region {
 343         assert!(self.in_snapshot());
 344         assert!(self.undo_log.borrow()[snapshot.length] == OpenSnapshot);
 345
 346         let sc = self.skolemization_count.get();
 347         self.skolemization_count.set(sc + 1);
 348         ReInfer(ReSkolemized(sc, br))
 349     }
 350
 351     pub fn new_bound(&self, debruijn: ty::DebruijnIndex) -> Region {
 352         // Creates a fresh bound variable for use in GLB computations.
 353         // See discussion of GLB computation in the large comment at
 354         // the top of this file for more details.
 355         //
 356         // This computation is potentially wrong in the face of
 357         // rollover.  It's conceivable, if unlikely, that one might
 358         // wind up with accidental capture for nested functions in
 359         // that case, if the outer function had bound regions created
 360         // a very long time before and the inner function somehow
 361         // wound up rolling over such that supposedly fresh
 362         // identifiers were in fact shadowed. For now, we just assert
 363         // that there is no rollover -- eventually we should try to be
 364         // robust against this possibility, either by checking the set
 365         // of bound identifiers that appear in a given expression and
 366         // ensure that we generate one that is distinct, or by
 367         // changing the representation of bound regions in a fn
 368         // declaration
 369
 370         let sc = self.bound_count.get();
 371         self.bound_count.set(sc + 1);
 372
 373         if sc >= self.bound_count.get() {
 374             self.tcx.sess.bug("rollover in RegionInference new_bound()");
 375         }
 376
 377         ReLateBound(debruijn, BrFresh(sc))
 378     }
 379
 380     fn values_are_none(&self) -> bool {
 381         self.values.borrow().is_none()
 382     }
 383
 384     fn add_constraint(&self,
 385                       constraint: Constraint,
 386                       origin: SubregionOrigin<'tcx>) {
 387         // cannot add constraints once regions are resolved
 388         assert!(self.values_are_none());
 389
 390         debug!("RegionVarBindings: add_constraint({})",
 391                constraint.repr(self.tcx));
 392
 393         if self.constraints.borrow_mut().insert(constraint, origin).is_none() {
 394             if self.in_snapshot() {
 395                 self.undo_log.borrow_mut().push(AddConstraint(constraint));
 396             }
 397         }
 398     }
 399
 400     fn add_verify(&self,
 401                   verify: Verify<'tcx>) {
 402         // cannot add verifys once regions are resolved
 403         assert!(self.values_are_none());
 404
 405         debug!("RegionVarBindings: add_verify({})",
 406                verify.repr(self.tcx));
 407
 408         let mut verifys = self.verifys.borrow_mut();
 409         let index = verifys.len();
 410         verifys.push(verify);
 411         if self.in_snapshot() {
 412             self.undo_log.borrow_mut().push(AddVerify(index));
 413         }
 414     }
 415
 416     pub fn add_given(&self,
 417                      sub: ty::FreeRegion,
 418                      sup: ty::RegionVid) {
 419         // cannot add givens once regions are resolved
 420         assert!(self.values_are_none());
 421
 422         let mut givens = self.givens.borrow_mut();
 423         if givens.insert((sub, sup)) {
 424             debug!("add_given({} <= {})",
 425                    sub.repr(self.tcx),
 426                    sup);
 427
 428             self.undo_log.borrow_mut().push(AddGiven(sub, sup));
 429         }
 430     }
 431
 432     pub fn make_eqregion(&self,
 433                          origin: SubregionOrigin<'tcx>,
 434                          sub: Region,
 435                          sup: Region) {
 436         if sub != sup {
 437             // Eventually, it would be nice to add direct support for
 438             // equating regions.
 439             self.make_subregion(origin.clone(), sub, sup);
 440             self.make_subregion(origin, sup, sub);
 441         }
 442     }
 443
 444     pub fn make_subregion(&self,
 445                           origin: SubregionOrigin<'tcx>,
 446                           sub: Region,
 447                           sup: Region) {
 448         // cannot add constraints once regions are resolved
 449         assert!(self.values_are_none());
 450
 451         debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
 452                sub.repr(self.tcx),
 453                sup.repr(self.tcx),
 454                origin.repr(self.tcx));
 455
 456         match (sub, sup) {
 457           (ReEarlyBound(..), ReEarlyBound(..)) => {
 458             // This case is used only to make sure that explicitly-specified
 459             // `Self` types match the real self type in implementations.
 460             //
 461             // FIXME(NDM) -- we really shouldn't be comparing bound things
 462             self.add_verify(VerifyRegSubReg(origin, sub, sup));
 463           }
 464           (ReEarlyBound(..), _) |
 465           (ReLateBound(..), _) |
 466           (_, ReEarlyBound(..)) |
 467           (_, ReLateBound(..)) => {
 468             self.tcx.sess.span_bug(
 469                 origin.span(),
 470                 format!("cannot relate bound region: {} <= {}",
 471                         sub.repr(self.tcx),
 472                         sup.repr(self.tcx))[]);
 473           }
 474           (_, ReStatic) => {
 475             // all regions are subregions of static, so we can ignore this
 476           }
 477           (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
 478             self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
 479           }
 480           (r, ReInfer(ReVar(sup_id))) => {
 481             self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
 482           }
 483           (ReInfer(ReVar(sub_id)), r) => {
 484             self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
 485           }
 486           _ => {
 487             self.add_verify(VerifyRegSubReg(origin, sub, sup));
 488           }
 489         }
 490     }
 491
 492     pub fn verify_param_bound(&self,
 493                               origin: SubregionOrigin<'tcx>,
 494                               param_ty: ty::ParamTy,
 495                               sub: Region,
 496                               sups: Vec<Region>) {
 497         self.add_verify(VerifyParamBound(param_ty, origin, sub, sups));
 498     }
 499
 500     pub fn lub_regions(&self,
 501                        origin: SubregionOrigin<'tcx>,
 502                        a: Region,
 503                        b: Region)
 504                        -> Region {
 505         // cannot add constraints once regions are resolved
 506         assert!(self.values_are_none());
 507
 508         debug!("RegionVarBindings: lub_regions({}, {})",
 509                a.repr(self.tcx),
 510                b.repr(self.tcx));
 511         match (a, b) {
 512             (ReStatic, _) | (_, ReStatic) => {
 513                 ReStatic // nothing lives longer than static
 514             }
 515
 516             _ => {
 517                 self.combine_vars(
 518                     Lub, a, b, origin.clone(),
 519                     |this, old_r, new_r|
 520                     this.make_subregion(origin.clone(), old_r, new_r))
 521             }
 522         }
 523     }
 524
 525     pub fn glb_regions(&self,
 526                        origin: SubregionOrigin<'tcx>,
 527                        a: Region,
 528                        b: Region)
 529                        -> Region {
 530         // cannot add constraints once regions are resolved
 531         assert!(self.values_are_none());
 532
 533         debug!("RegionVarBindings: glb_regions({}, {})",
 534                a.repr(self.tcx),
 535                b.repr(self.tcx));
 536         match (a, b) {
 537             (ReStatic, r) | (r, ReStatic) => {
 538                 // static lives longer than everything else
 539                 r
 540             }
 541
 542             _ => {
 543                 self.combine_vars(
 544                     Glb, a, b, origin.clone(),
 545                     |this, old_r, new_r|
 546                     this.make_subregion(origin.clone(), new_r, old_r))
 547             }
 548         }
 549     }
 550
 551     pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
 552         match *self.values.borrow() {
 553             None => {
 554                 self.tcx.sess.span_bug(
 555                     (*self.var_origins.borrow())[rid.index as uint].span(),
 556                     "attempt to resolve region variable before values have \
 557                      been computed!")
 558             }
 559             Some(ref values) => {
 560                 let r = lookup(values, rid);
 561                 debug!("resolve_var({}) = {}", rid, r.repr(self.tcx));
 562                 r
 563             }
 564         }
 565     }
 566
 567     fn combine_map(&self, t: CombineMapType)
 568                    -> &RefCell<CombineMap> {
 569         match t {
 570             Glb => &self.glbs,
 571             Lub => &self.lubs,
 572         }
 573     }
 574
 575     pub fn combine_vars<F>(&self,
 576                            t: CombineMapType,
 577                            a: Region,
 578                            b: Region,
 579                            origin: SubregionOrigin<'tcx>,
 580                            mut relate: F)
 581                            -> Region where
 582         F: FnMut(&RegionVarBindings<'a, 'tcx>, Region, Region),
 583     {
 584         let vars = TwoRegions { a: a, b: b };
 585         match self.combine_map(t).borrow().get(&vars) {
 586             Some(&c) => {
 587                 return ReInfer(ReVar(c));
 588             }
 589             None => {}
 590         }
 591         let c = self.new_region_var(MiscVariable(origin.span()));
 592         self.combine_map(t).borrow_mut().insert(vars, c);
 593         if self.in_snapshot() {
 594             self.undo_log.borrow_mut().push(AddCombination(t, vars));
 595         }
 596         relate(self, a, ReInfer(ReVar(c)));
 597         relate(self, b, ReInfer(ReVar(c)));
 598         debug!("combine_vars() c={}", c);
 599         ReInfer(ReVar(c))
 600     }
 601
 602     pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot)
 603                                        -> Vec<RegionVid>
 604     {
 605         self.undo_log.borrow()
 606             .slice_from(mark.length)
 607             .iter()
 608             .filter_map(|&elt| match elt {
 609                 AddVar(vid) => Some(vid),
 610                 _ => None
 611             })
 612             .collect()
 613     }
 614
 615     /// Computes all regions that have been related to `r0` in any way since the mark `mark` was
 616     /// made---`r0` itself will be the first entry. This is used when checking whether skolemized
 617     /// regions are being improperly related to other regions.
 618     pub fn tainted(&self, mark: &RegionSnapshot, r0: Region) -> Vec<Region> {
 619         debug!("tainted(mark={}, r0={})", mark, r0.repr(self.tcx));
 620         let _indenter = indenter();
 621
 622         // `result_set` acts as a worklist: we explore all outgoing
 623         // edges and add any new regions we find to result_set.  This
 624         // is not a terribly efficient implementation.
 625         let mut result_set = vec!(r0);
 626         let mut result_index = 0;
 627         while result_index < result_set.len() {
 628             // nb: can't use uint::range() here because result_set grows
 629             let r = result_set[result_index];
 630             debug!("result_index={}, r={}", result_index, r);
 631
 632             for undo_entry in
 633                 self.undo_log.borrow().slice_from(mark.length).iter()
 634             {
 635                 match undo_entry {
 636                     &AddConstraint(ConstrainVarSubVar(a, b)) => {
 637                         consider_adding_bidirectional_edges(
 638                             &mut result_set, r,
 639                             ReInfer(ReVar(a)), ReInfer(ReVar(b)));
 640                     }
 641                     &AddConstraint(ConstrainRegSubVar(a, b)) => {
 642                         consider_adding_bidirectional_edges(
 643                             &mut result_set, r,
 644                             a, ReInfer(ReVar(b)));
 645                     }
 646                     &AddConstraint(ConstrainVarSubReg(a, b)) => {
 647                         consider_adding_bidirectional_edges(
 648                             &mut result_set, r,
 649                             ReInfer(ReVar(a)), b);
 650                     }
 651                     &AddGiven(a, b) => {
 652                         consider_adding_bidirectional_edges(
 653                             &mut result_set, r,
 654                             ReFree(a), ReInfer(ReVar(b)));
 655                     }
 656                     &AddVerify(i) => {
 657                         match (*self.verifys.borrow())[i] {
 658                             VerifyRegSubReg(_, a, b) => {
 659                                 consider_adding_bidirectional_edges(
 660                                     &mut result_set, r,
 661                                     a, b);
 662                             }
 663                             VerifyParamBound(_, _, a, ref bs) => {
 664                                 for &b in bs.iter() {
 665                                     consider_adding_bidirectional_edges(
 666                                         &mut result_set, r,
 667                                         a, b);
 668                                 }
 669                             }
 670                         }
 671                     }
 672                     &AddCombination(..) |
 673                     &AddVar(..) |
 674                     &OpenSnapshot |
 675                     &CommitedSnapshot => {
 676                     }
 677                 }
 678             }
 679
 680             result_index += 1;
 681         }
 682
 683         return result_set;
 684
 685         fn consider_adding_bidirectional_edges(result_set: &mut Vec<Region>,
 686                                                r: Region,
 687                                                r1: Region,
 688                                                r2: Region) {
 689             consider_adding_directed_edge(result_set, r, r1, r2);
 690             consider_adding_directed_edge(result_set, r, r2, r1);
 691         }
 692
 693         fn consider_adding_directed_edge(result_set: &mut Vec<Region>,
 694                                          r: Region,
 695                                          r1: Region,
 696                                          r2: Region) {
 697             if r == r1 {
 698                 // Clearly, this is potentially inefficient.
 699                 if !result_set.iter().any(|x| *x == r2) {
 700                     result_set.push(r2);
 701                 }
 702             }
 703         }
 704     }
 705
 706     /// This function performs the actual region resolution.  It must be
 707     /// called after all constraints have been added.  It performs a
 708     /// fixed-point iteration to find region values which satisfy all
 709     /// constraints, assuming such values can be found; if they cannot,
 710     /// errors are reported.
 711     pub fn resolve_regions(&self, subject_node: ast::NodeId) -> Vec<RegionResolutionError<'tcx>> {
 712         debug!("RegionVarBindings: resolve_regions()");
 713         let mut errors = vec!();
 714         let v = self.infer_variable_values(&mut errors, subject_node);
 715         *self.values.borrow_mut() = Some(v);
 716         errors
 717     }
 718
 719     fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
 720         self.tcx.region_maps.is_subregion_of(sub, sup)
 721     }
 722
 723     fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
 724         match (a, b) {
 725           (ReLateBound(..), _) |
 726           (_, ReLateBound(..)) |
 727           (ReEarlyBound(..), _) |
 728           (_, ReEarlyBound(..)) => {
 729             self.tcx.sess.bug(
 730                 format!("cannot relate bound region: LUB({}, {})",
 731                         a.repr(self.tcx),
 732                         b.repr(self.tcx))[]);
 733           }
 734
 735           (ReStatic, _) | (_, ReStatic) => {
 736             ReStatic // nothing lives longer than static
 737           }
 738
 739           (ReEmpty, r) | (r, ReEmpty) => {
 740             r // everything lives longer than empty
 741           }
 742
 743           (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
 744             self.tcx.sess.span_bug(
 745                 (*self.var_origins.borrow())[v_id.index as uint].span(),
 746                 format!("lub_concrete_regions invoked with \
 747                          non-concrete regions: {}, {}",
 748                         a,
 749                         b)[]);
 750           }
 751
 752           (ReFree(ref fr), ReScope(s_id)) |
 753           (ReScope(s_id), ReFree(ref fr)) => {
 754             let f = ReFree(*fr);
 755             // A "free" region can be interpreted as "some region
 756             // at least as big as the block fr.scope_id".  So, we can
 757             // reasonably compare free regions and scopes:
 758             match self.tcx.region_maps.nearest_common_ancestor(fr.scope, s_id) {
 759               // if the free region's scope `fr.scope_id` is bigger than
 760               // the scope region `s_id`, then the LUB is the free
 761               // region itself:
 762               Some(r_id) if r_id == fr.scope => f,
 763
 764               // otherwise, we don't know what the free region is,
 765               // so we must conservatively say the LUB is static:
 766               _ => ReStatic
 767             }
 768           }
 769
 770           (ReScope(a_id), ReScope(b_id)) => {
 771             // The region corresponding to an outer block is a
 772             // subtype of the region corresponding to an inner
 773             // block.
 774             match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
 775               Some(r_id) => ReScope(r_id),
 776               _ => ReStatic
 777             }
 778           }
 779
 780           (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 781              self.lub_free_regions(a_fr, b_fr)
 782           }
 783
 784           // For these types, we cannot define any additional
 785           // relationship:
 786           (ReInfer(ReSkolemized(..)), _) |
 787           (_, ReInfer(ReSkolemized(..))) => {
 788             if a == b {a} else {ReStatic}
 789           }
 790         }
 791     }
 792
 793     /// Computes a region that encloses both free region arguments. Guarantee that if the same two
 794     /// regions are given as argument, in any order, a consistent result is returned.
 795     fn lub_free_regions(&self,
 796                         a: &FreeRegion,
 797                         b: &FreeRegion) -> ty::Region
 798     {
 799         return match a.cmp(b) {
 800             Less => helper(self, a, b),
 801             Greater => helper(self, b, a),
 802             Equal => ty::ReFree(*a)
 803         };
 804
 805         fn helper(this: &RegionVarBindings,
 806                   a: &FreeRegion,
 807                   b: &FreeRegion) -> ty::Region
 808         {
 809             if this.tcx.region_maps.sub_free_region(*a, *b) {
 810                 ty::ReFree(*b)
 811             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 812                 ty::ReFree(*a)
 813             } else {
 814                 ty::ReStatic
 815             }
 816         }
 817     }
 818
 819     fn glb_concrete_regions(&self,
 820                             a: Region,
 821                             b: Region)
 822                          -> cres<'tcx, Region> {
 823         debug!("glb_concrete_regions({}, {})", a, b);
 824         match (a, b) {
 825             (ReLateBound(..), _) |
 826             (_, ReLateBound(..)) |
 827             (ReEarlyBound(..), _) |
 828             (_, ReEarlyBound(..)) => {
 829               self.tcx.sess.bug(
 830                   format!("cannot relate bound region: GLB({}, {})",
 831                           a.repr(self.tcx),
 832                           b.repr(self.tcx))[]);
 833             }
 834
 835             (ReStatic, r) | (r, ReStatic) => {
 836                 // static lives longer than everything else
 837                 Ok(r)
 838             }
 839
 840             (ReEmpty, _) | (_, ReEmpty) => {
 841                 // nothing lives shorter than everything else
 842                 Ok(ReEmpty)
 843             }
 844
 845             (ReInfer(ReVar(v_id)), _) |
 846             (_, ReInfer(ReVar(v_id))) => {
 847                 self.tcx.sess.span_bug(
 848                     (*self.var_origins.borrow())[v_id.index as uint].span(),
 849                     format!("glb_concrete_regions invoked with \
 850                              non-concrete regions: {}, {}",
 851                             a,
 852                             b)[]);
 853             }
 854
 855             (ReFree(ref fr), ReScope(s_id)) |
 856             (ReScope(s_id), ReFree(ref fr)) => {
 857                 let s = ReScope(s_id);
 858                 // Free region is something "at least as big as
 859                 // `fr.scope_id`."  If we find that the scope `fr.scope_id` is bigger
 860                 // than the scope `s_id`, then we can say that the GLB
 861                 // is the scope `s_id`.  Otherwise, as we do not know
 862                 // big the free region is precisely, the GLB is undefined.
 863                 match self.tcx.region_maps.nearest_common_ancestor(fr.scope, s_id) {
 864                     Some(r_id) if r_id == fr.scope => Ok(s),
 865                     _ => Err(ty::terr_regions_no_overlap(b, a))
 866                 }
 867             }
 868
 869             (ReScope(a_id), ReScope(b_id)) => {
 870                 self.intersect_scopes(a, b, a_id, b_id)
 871             }
 872
 873             (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 874                 self.glb_free_regions(a_fr, b_fr)
 875             }
 876
 877             // For these types, we cannot define any additional
 878             // relationship:
 879             (ReInfer(ReSkolemized(..)), _) |
 880             (_, ReInfer(ReSkolemized(..))) => {
 881                 if a == b {
 882                     Ok(a)
 883                 } else {
 884                     Err(ty::terr_regions_no_overlap(b, a))
 885                 }
 886             }
 887         }
 888     }
 889
 890     /// Computes a region that is enclosed by both free region arguments, if any. Guarantees that
 891     /// if the same two regions are given as argument, in any order, a consistent result is
 892     /// returned.
 893     fn glb_free_regions(&self,
 894                         a: &FreeRegion,
 895                         b: &FreeRegion) -> cres<'tcx, ty::Region>
 896     {
 897         return match a.cmp(b) {
 898             Less => helper(self, a, b),
 899             Greater => helper(self, b, a),
 900             Equal => Ok(ty::ReFree(*a))
 901         };
 902
 903         fn helper<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
 904                             a: &FreeRegion,
 905                             b: &FreeRegion) -> cres<'tcx, ty::Region>
 906         {
 907             if this.tcx.region_maps.sub_free_region(*a, *b) {
 908                 Ok(ty::ReFree(*a))
 909             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 910                 Ok(ty::ReFree(*b))
 911             } else {
 912                 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
 913                                       a.scope, b.scope)
 914             }
 915         }
 916     }
 917
 918     fn intersect_scopes(&self,
 919                         region_a: ty::Region,
 920                         region_b: ty::Region,
 921                         scope_a: region::CodeExtent,
 922                         scope_b: region::CodeExtent) -> cres<'tcx, Region>
 923     {
 924         // We want to generate the intersection of two
 925         // scopes or two free regions.  So, if one of
 926         // these scopes is a subscope of the other, return
 927         // it. Otherwise fail.
 928         debug!("intersect_scopes(scope_a={}, scope_b={}, region_a={}, region_b={})",
 929                scope_a, scope_b, region_a, region_b);
 930         match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
 931             Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
 932             Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
 933             _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
 934         }
 935     }
 936 }
 937
 938 // ______________________________________________________________________
 939
 940 #[deriving(Copy, PartialEq, Show)]
 941 enum Classification { Expanding, Contracting }
 942
 943 #[deriving(Copy)]
 944 pub enum VarValue { NoValue, Value(Region), ErrorValue }
 945
 946 struct VarData {
 947     classification: Classification,
 948     value: VarValue,
 949 }
 950
 951 struct RegionAndOrigin<'tcx> {
 952     region: Region,
 953     origin: SubregionOrigin<'tcx>,
 954 }
 955
 956 type RegionGraph = graph::Graph<(), Constraint>;
 957
 958 impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 959     fn infer_variable_values(&self,
 960                              errors: &mut Vec<RegionResolutionError<'tcx>>,
 961                              subject: ast::NodeId) -> Vec<VarValue>
 962     {
 963         let mut var_data = self.construct_var_data();
 964
 965         // Dorky hack to cause `dump_constraints` to only get called
 966         // if debug mode is enabled:
 967         debug!("----() End constraint listing {}---", self.dump_constraints());
 968         graphviz::maybe_print_constraints_for(self, subject);
 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[],
 974                                                       errors);
 975         self.collect_concrete_region_errors(&values, errors);
 976         values
 977     }
 978
 979     fn construct_var_data(&self) -> Vec<VarData> {
 980         range(0, self.num_vars() as uint).map(|_| {
 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         }).collect()
 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 as uint];
1010                 self.expand_node(a_region, b_vid, b_data)
1011               }
1012               ConstrainVarSubVar(a_vid, b_vid) => {
1013                 match var_data[a_vid.index as uint].value {
1014                   NoValue | ErrorValue => false,
1015                   Value(a_region) => {
1016                     let b_node = &mut var_data[b_vid.index as uint];
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 as uint].value {
1098                   NoValue | ErrorValue => false,
1099                   Value(b_region) => {
1100                     let a_data = &mut var_data[a_vid.index as uint];
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 as uint];
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<_> = repeat(u32::MAX).take(self.num_vars() as uint).collect();
1253
1254         let mut opt_graph = None;
1255
1256         for idx in range(0u, self.num_vars() as uint) {
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 as u32 };
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         range(0, self.num_vars() as uint).map(|idx| var_data[idx].value).collect()
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 as uint + 1,
1323                                                     num_edges);
1324
1325         for _ in range(0, 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 as uint),
1334                                    NodeIndex(b_id.index as uint),
1335                                    *constraint);
1336                 }
1337                 ConstrainRegSubVar(_, b_id) => {
1338                     graph.add_edge(dummy_idx,
1339                                    NodeIndex(b_id.index as uint),
1340                                    *constraint);
1341                 }
1342                 ConstrainVarSubReg(a_id, _) => {
1343                     graph.add_edge(NodeIndex(a_id.index as uint),
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 [u32],
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 as uint].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 as uint].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))[]);
1412     }
1413
1414     fn collect_error_for_contracting_node(
1415         &self,
1416         graph: &RegionGraph,
1417         var_data: &[VarData],
1418         dup_vec: &mut [u32],
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 as uint].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 as uint].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))[]);
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 [u32])
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 as uint].classification;
1486
1487             // check whether we've visited this node on some previous walk
1488             if dup_vec[node_idx.index as uint] == u32::MAX {
1489                 dup_vec[node_idx.index as uint] = orig_node_idx.index;
1490             } else if dup_vec[node_idx.index as uint] != 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 as uint);
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<F>(&self, tag: &str, mut body: F) where
1543         F: FnMut(&Constraint) -> bool,
1544     {
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 as uint] {
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 }