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