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