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