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,
1057                  region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1058                  var_values: &mut [VarValue<'tcx>]) {
1059         self.iterate_until_fixed_point("Expansion", |constraint, origin| {
1060             debug!("expansion: constraint={:?} origin={:?}",
1061                    constraint, origin);
1062             match *constraint {
1063                 ConstrainRegSubVar(a_region, b_vid) => {
1064                     let b_data = &mut var_values[b_vid.index as usize];
1065                     self.expand_node(region_rels, a_region, b_vid, b_data)
1066                 }
1067                 ConstrainVarSubVar(a_vid, b_vid) => {
1068                     match var_values[a_vid.index as usize] {
1069                         ErrorValue => false,
1070                         Value(a_region) => {
1071                             let b_node = &mut var_values[b_vid.index as usize];
1072                             self.expand_node(region_rels, a_region, b_vid, b_node)
1073                         }
1074                     }
1075                 }
1076                 ConstrainRegSubReg(..) |
1077                 ConstrainVarSubReg(..) => {
1078                     // These constraints are checked after expansion
1079                     // is done, in `collect_errors`.
1080                     false
1081                 }
1082             }
1083         })
1084     }
1085
1086     fn expand_node(&self,
1087                    region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1088                    a_region: Region<'tcx>,
1089                    b_vid: RegionVid,
1090                    b_data: &mut VarValue<'tcx>)
1091                    -> bool {
1092         debug!("expand_node({:?}, {:?} == {:?})",
1093                a_region,
1094                b_vid,
1095                b_data);
1096
1097         // Check if this relationship is implied by a given.
1098         match *a_region {
1099             ty::ReFree(fr) => {
1100                 if self.givens.borrow().contains(&(fr, b_vid)) {
1101                     debug!("given");
1102                     return false;
1103                 }
1104             }
1105             _ => {}
1106         }
1107
1108         match *b_data {
1109             Value(cur_region) => {
1110                 let lub = self.lub_concrete_regions(region_rels, a_region, cur_region);
1111                 if lub == cur_region {
1112                     return false;
1113                 }
1114
1115                 debug!("Expanding value of {:?} from {:?} to {:?}",
1116                        b_vid,
1117                        cur_region,
1118                        lub);
1119
1120                 *b_data = Value(lub);
1121                 return true;
1122             }
1123
1124             ErrorValue => {
1125                 return false;
1126             }
1127         }
1128     }
1129
1130     /// After expansion is complete, go and check upper bounds (i.e.,
1131     /// cases where the region cannot grow larger than a fixed point)
1132     /// and check that they are satisfied.
1133     fn collect_errors(&self,
1134                       region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1135                       var_data: &mut Vec<VarValue<'tcx>>,
1136                       errors: &mut Vec<RegionResolutionError<'tcx>>) {
1137         let constraints = self.constraints.borrow();
1138         for (constraint, origin) in constraints.iter() {
1139             debug!("collect_errors: constraint={:?} origin={:?}",
1140                    constraint, origin);
1141             match *constraint {
1142                 ConstrainRegSubVar(..) |
1143                 ConstrainVarSubVar(..) => {
1144                     // Expansion will ensure that these constraints hold. Ignore.
1145                 }
1146
1147                 ConstrainRegSubReg(sub, sup) => {
1148                     if region_rels.is_subregion_of(sub, sup) {
1149                         continue;
1150                     }
1151
1152                     debug!("collect_errors: region error at {:?}: \
1153                             cannot verify that {:?} <= {:?}",
1154                            origin,
1155                            sub,
1156                            sup);
1157
1158                     errors.push(ConcreteFailure((*origin).clone(), sub, sup));
1159                 }
1160
1161                 ConstrainVarSubReg(a_vid, b_region) => {
1162                     let a_data = &mut var_data[a_vid.index as usize];
1163                     debug!("contraction: {:?} == {:?}, {:?}",
1164                            a_vid,
1165                            a_data,
1166                            b_region);
1167
1168                     let a_region = match *a_data {
1169                         ErrorValue => continue,
1170                         Value(a_region) => a_region,
1171                     };
1172
1173                     // Do not report these errors immediately:
1174                     // instead, set the variable value to error and
1175                     // collect them later.
1176                     if !region_rels.is_subregion_of(a_region, b_region) {
1177                         debug!("collect_errors: region error at {:?}: \
1178                                 cannot verify that {:?}={:?} <= {:?}",
1179                                origin,
1180                                a_vid,
1181                                a_region,
1182                                b_region);
1183                         *a_data = ErrorValue;
1184                     }
1185                 }
1186             }
1187         }
1188
1189         for verify in self.verifys.borrow().iter() {
1190             debug!("collect_errors: verify={:?}", verify);
1191             let sub = normalize(self.tcx, var_data, verify.region);
1192             if verify.bound.is_met(region_rels, var_data, sub) {
1193                 continue;
1194             }
1195
1196             debug!("collect_errors: region error at {:?}: \
1197                     cannot verify that {:?} <= {:?}",
1198                    verify.origin,
1199                    verify.region,
1200                    verify.bound);
1201
1202             errors.push(GenericBoundFailure(verify.origin.clone(),
1203                                             verify.kind.clone(),
1204                                             sub));
1205         }
1206     }
1207
1208     /// Go over the variables that were declared to be error variables
1209     /// and create a `RegionResolutionError` for each of them.
1210     fn collect_var_errors(&self,
1211                           region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1212                           var_data: &[VarValue<'tcx>],
1213                           graph: &RegionGraph<'tcx>,
1214                           errors: &mut Vec<RegionResolutionError<'tcx>>) {
1215         debug!("collect_var_errors");
1216
1217         // This is the best way that I have found to suppress
1218         // duplicate and related errors. Basically we keep a set of
1219         // flags for every node. Whenever an error occurs, we will
1220         // walk some portion of the graph looking to find pairs of
1221         // conflicting regions to report to the user. As we walk, we
1222         // trip the flags from false to true, and if we find that
1223         // we've already reported an error involving any particular
1224         // node we just stop and don't report the current error.  The
1225         // idea is to report errors that derive from independent
1226         // regions of the graph, but not those that derive from
1227         // overlapping locations.
1228         let mut dup_vec = vec![u32::MAX; self.num_vars() as usize];
1229
1230         for idx in 0..self.num_vars() as usize {
1231             match var_data[idx] {
1232                 Value(_) => {
1233                     /* Inference successful */
1234                 }
1235                 ErrorValue => {
1236                     /* Inference impossible, this value contains
1237                        inconsistent constraints.
1238
1239                        I think that in this case we should report an
1240                        error now---unlike the case above, we can't
1241                        wait to see whether the user needs the result
1242                        of this variable.  The reason is that the mere
1243                        existence of this variable implies that the
1244                        region graph is inconsistent, whether or not it
1245                        is used.
1246
1247                        For example, we may have created a region
1248                        variable that is the GLB of two other regions
1249                        which do not have a GLB.  Even if that variable
1250                        is not used, it implies that those two regions
1251                        *should* have a GLB.
1252
1253                        At least I think this is true. It may be that
1254                        the mere existence of a conflict in a region variable
1255                        that is not used is not a problem, so if this rule
1256                        starts to create problems we'll have to revisit
1257                        this portion of the code and think hard about it. =) */
1258
1259                     let node_vid = RegionVid { index: idx as u32 };
1260                     self.collect_error_for_expanding_node(region_rels,
1261                                                           graph,
1262                                                           &mut dup_vec,
1263                                                           node_vid,
1264                                                           errors);
1265                 }
1266             }
1267         }
1268     }
1269
1270     fn construct_graph(&self) -> RegionGraph<'tcx> {
1271         let num_vars = self.num_vars();
1272
1273         let constraints = self.constraints.borrow();
1274
1275         let mut graph = graph::Graph::new();
1276
1277         for _ in 0..num_vars {
1278             graph.add_node(());
1279         }
1280
1281         // Issue #30438: two distinct dummy nodes, one for incoming
1282         // edges (dummy_source) and another for outgoing edges
1283         // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
1284         // dummy node leads one to think (erroneously) there exists a
1285         // path from `b` to `a`. Two dummy nodes sidesteps the issue.
1286         let dummy_source = graph.add_node(());
1287         let dummy_sink = graph.add_node(());
1288
1289         for (constraint, _) in constraints.iter() {
1290             match *constraint {
1291                 ConstrainVarSubVar(a_id, b_id) => {
1292                     graph.add_edge(NodeIndex(a_id.index as usize),
1293                                    NodeIndex(b_id.index as usize),
1294                                    *constraint);
1295                 }
1296                 ConstrainRegSubVar(_, b_id) => {
1297                     graph.add_edge(dummy_source, NodeIndex(b_id.index as usize), *constraint);
1298                 }
1299                 ConstrainVarSubReg(a_id, _) => {
1300                     graph.add_edge(NodeIndex(a_id.index as usize), dummy_sink, *constraint);
1301                 }
1302                 ConstrainRegSubReg(..) => {
1303                     // this would be an edge from `dummy_source` to
1304                     // `dummy_sink`; just ignore it.
1305                 }
1306             }
1307         }
1308
1309         return graph;
1310     }
1311
1312     fn collect_error_for_expanding_node(&self,
1313                                         region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1314                                         graph: &RegionGraph<'tcx>,
1315                                         dup_vec: &mut [u32],
1316                                         node_idx: RegionVid,
1317                                         errors: &mut Vec<RegionResolutionError<'tcx>>) {
1318         // Errors in expanding nodes result from a lower-bound that is
1319         // not contained by an upper-bound.
1320         let (mut lower_bounds, lower_dup) = self.collect_concrete_regions(graph,
1321                                                                           node_idx,
1322                                                                           graph::INCOMING,
1323                                                                           dup_vec);
1324         let (mut upper_bounds, upper_dup) = self.collect_concrete_regions(graph,
1325                                                                           node_idx,
1326                                                                           graph::OUTGOING,
1327                                                                           dup_vec);
1328
1329         if lower_dup || upper_dup {
1330             return;
1331         }
1332
1333         // We place free regions first because we are special casing
1334         // SubSupConflict(ReFree, ReFree) when reporting error, and so
1335         // the user will more likely get a specific suggestion.
1336         fn free_regions_first(a: &RegionAndOrigin, b: &RegionAndOrigin) -> Ordering {
1337             match (a.region, b.region) {
1338                 (&ReFree(..), &ReFree(..)) => Equal,
1339                 (&ReFree(..), _) => Less,
1340                 (_, &ReFree(..)) => Greater,
1341                 (..) => Equal,
1342             }
1343         }
1344         lower_bounds.sort_by(|a, b| free_regions_first(a, b));
1345         upper_bounds.sort_by(|a, b| free_regions_first(a, b));
1346
1347         for lower_bound in &lower_bounds {
1348             for upper_bound in &upper_bounds {
1349                 if !region_rels.is_subregion_of(lower_bound.region, upper_bound.region) {
1350                     let origin = (*self.var_origins.borrow())[node_idx.index as usize].clone();
1351                     debug!("region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
1352                             sup: {:?}",
1353                            origin,
1354                            node_idx,
1355                            lower_bound.region,
1356                            upper_bound.region);
1357                     errors.push(SubSupConflict(origin,
1358                                                lower_bound.origin.clone(),
1359                                                lower_bound.region,
1360                                                upper_bound.origin.clone(),
1361                                                upper_bound.region));
1362                     return;
1363                 }
1364             }
1365         }
1366
1367         span_bug!((*self.var_origins.borrow())[node_idx.index as usize].span(),
1368                   "collect_error_for_expanding_node() could not find \
1369                    error for var {:?}, lower_bounds={:?}, \
1370                    upper_bounds={:?}",
1371                   node_idx,
1372                   lower_bounds,
1373                   upper_bounds);
1374     }
1375
1376     fn collect_concrete_regions(&self,
1377                                 graph: &RegionGraph<'tcx>,
1378                                 orig_node_idx: RegionVid,
1379                                 dir: Direction,
1380                                 dup_vec: &mut [u32])
1381                                 -> (Vec<RegionAndOrigin<'tcx>>, bool) {
1382         struct WalkState<'tcx> {
1383             set: FxHashSet<RegionVid>,
1384             stack: Vec<RegionVid>,
1385             result: Vec<RegionAndOrigin<'tcx>>,
1386             dup_found: bool,
1387         }
1388         let mut state = WalkState {
1389             set: FxHashSet(),
1390             stack: vec![orig_node_idx],
1391             result: Vec::new(),
1392             dup_found: false,
1393         };
1394         state.set.insert(orig_node_idx);
1395
1396         // to start off the process, walk the source node in the
1397         // direction specified
1398         process_edges(self, &mut state, graph, orig_node_idx, dir);
1399
1400         while !state.stack.is_empty() {
1401             let node_idx = state.stack.pop().unwrap();
1402
1403             // check whether we've visited this node on some previous walk
1404             if dup_vec[node_idx.index as usize] == u32::MAX {
1405                 dup_vec[node_idx.index as usize] = orig_node_idx.index;
1406             } else if dup_vec[node_idx.index as usize] != orig_node_idx.index {
1407                 state.dup_found = true;
1408             }
1409
1410             debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
1411                    orig_node_idx,
1412                    node_idx);
1413
1414             process_edges(self, &mut state, graph, node_idx, dir);
1415         }
1416
1417         let WalkState {result, dup_found, ..} = state;
1418         return (result, dup_found);
1419
1420         fn process_edges<'a, 'gcx, 'tcx>(this: &RegionVarBindings<'a, 'gcx, 'tcx>,
1421                                          state: &mut WalkState<'tcx>,
1422                                          graph: &RegionGraph<'tcx>,
1423                                          source_vid: RegionVid,
1424                                          dir: Direction) {
1425             debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1426
1427             let source_node_index = NodeIndex(source_vid.index as usize);
1428             for (_, edge) in graph.adjacent_edges(source_node_index, dir) {
1429                 match edge.data {
1430                     ConstrainVarSubVar(from_vid, to_vid) => {
1431                         let opp_vid = if from_vid == source_vid {
1432                             to_vid
1433                         } else {
1434                             from_vid
1435                         };
1436                         if state.set.insert(opp_vid) {
1437                             state.stack.push(opp_vid);
1438                         }
1439                     }
1440
1441                     ConstrainRegSubVar(region, _) |
1442                     ConstrainVarSubReg(_, region) => {
1443                         state.result.push(RegionAndOrigin {
1444                             region: region,
1445                             origin: this.constraints.borrow().get(&edge.data).unwrap().clone(),
1446                         });
1447                     }
1448
1449                     ConstrainRegSubReg(..) => {
1450                         panic!("cannot reach reg-sub-reg edge in region inference \
1451                                 post-processing")
1452                     }
1453                 }
1454             }
1455         }
1456     }
1457
1458     fn iterate_until_fixed_point<F>(&self, tag: &str, mut body: F)
1459         where F: FnMut(&Constraint<'tcx>, &SubregionOrigin<'tcx>) -> bool
1460     {
1461         let mut iteration = 0;
1462         let mut changed = true;
1463         while changed {
1464             changed = false;
1465             iteration += 1;
1466             debug!("---- {} Iteration {}{}", "#", tag, iteration);
1467             for (constraint, origin) in self.constraints.borrow().iter() {
1468                 let edge_changed = body(constraint, origin);
1469                 if edge_changed {
1470                     debug!("Updated due to constraint {:?}", constraint);
1471                     changed = true;
1472                 }
1473             }
1474         }
1475         debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1476     }
1477
1478 }
1479
1480 fn normalize<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
1481                              values: &Vec<VarValue<'tcx>>,
1482                              r: ty::Region<'tcx>)
1483                              -> ty::Region<'tcx> {
1484     match *r {
1485         ty::ReVar(rid) => lookup(tcx, values, rid),
1486         _ => r,
1487     }
1488 }
1489
1490 fn lookup<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
1491                           values: &Vec<VarValue<'tcx>>,
1492                           rid: ty::RegionVid)
1493                           -> ty::Region<'tcx> {
1494     match values[rid.index as usize] {
1495         Value(r) => r,
1496         ErrorValue => tcx.types.re_static, // Previously reported error.
1497     }
1498 }
1499
1500 impl<'tcx> fmt::Debug for RegionAndOrigin<'tcx> {
1501     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1502         write!(f, "RegionAndOrigin({:?},{:?})", self.region, self.origin)
1503     }
1504 }
1505
1506 impl fmt::Debug for RegionSnapshot {
1507     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1508         write!(f, "RegionSnapshot(length={},skolemization={})",
1509                self.length, self.skolemization_count)
1510     }
1511 }
1512
1513 impl<'tcx> fmt::Debug for GenericKind<'tcx> {
1514     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1515         match *self {
1516             GenericKind::Param(ref p) => write!(f, "{:?}", p),
1517             GenericKind::Projection(ref p) => write!(f, "{:?}", p),
1518         }
1519     }
1520 }
1521
1522 impl<'tcx> fmt::Display for GenericKind<'tcx> {
1523     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1524         match *self {
1525             GenericKind::Param(ref p) => write!(f, "{}", p),
1526             GenericKind::Projection(ref p) => write!(f, "{}", p),
1527         }
1528     }
1529 }
1530
1531 impl<'a, 'gcx, 'tcx> GenericKind<'tcx> {
1532     pub fn to_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> {
1533         match *self {
1534             GenericKind::Param(ref p) => p.to_ty(tcx),
1535             GenericKind::Projection(ref p) => tcx.mk_projection(p.trait_ref.clone(), p.item_name),
1536         }
1537     }
1538 }
1539
1540 impl<'a, 'gcx, 'tcx> VerifyBound<'tcx> {
1541     fn for_each_region(&self, f: &mut FnMut(ty::Region<'tcx>)) {
1542         match self {
1543             &VerifyBound::AnyRegion(ref rs) |
1544             &VerifyBound::AllRegions(ref rs) => for &r in rs {
1545                 f(r);
1546             },
1547
1548             &VerifyBound::AnyBound(ref bs) |
1549             &VerifyBound::AllBounds(ref bs) => for b in bs {
1550                 b.for_each_region(f);
1551             },
1552         }
1553     }
1554
1555     pub fn must_hold(&self) -> bool {
1556         match self {
1557             &VerifyBound::AnyRegion(ref bs) => bs.contains(&&ty::ReStatic),
1558             &VerifyBound::AllRegions(ref bs) => bs.is_empty(),
1559             &VerifyBound::AnyBound(ref bs) => bs.iter().any(|b| b.must_hold()),
1560             &VerifyBound::AllBounds(ref bs) => bs.iter().all(|b| b.must_hold()),
1561         }
1562     }
1563
1564     pub fn cannot_hold(&self) -> bool {
1565         match self {
1566             &VerifyBound::AnyRegion(ref bs) => bs.is_empty(),
1567             &VerifyBound::AllRegions(ref bs) => bs.contains(&&ty::ReEmpty),
1568             &VerifyBound::AnyBound(ref bs) => bs.iter().all(|b| b.cannot_hold()),
1569             &VerifyBound::AllBounds(ref bs) => bs.iter().any(|b| b.cannot_hold()),
1570         }
1571     }
1572
1573     pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
1574         if self.must_hold() || vb.cannot_hold() {
1575             self
1576         } else if self.cannot_hold() || vb.must_hold() {
1577             vb
1578         } else {
1579             VerifyBound::AnyBound(vec![self, vb])
1580         }
1581     }
1582
1583     pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
1584         if self.must_hold() && vb.must_hold() {
1585             self
1586         } else if self.cannot_hold() && vb.cannot_hold() {
1587             self
1588         } else {
1589             VerifyBound::AllBounds(vec![self, vb])
1590         }
1591     }
1592
1593     fn is_met(&self,
1594               region_rels: &RegionRelations<'a, 'gcx, 'tcx>,
1595               var_values: &Vec<VarValue<'tcx>>,
1596               min: ty::Region<'tcx>)
1597               -> bool {
1598         let tcx = region_rels.tcx;
1599         match self {
1600             &VerifyBound::AnyRegion(ref rs) =>
1601                 rs.iter()
1602                   .map(|&r| normalize(tcx, var_values, r))
1603                   .any(|r| region_rels.is_subregion_of(min, r)),
1604
1605             &VerifyBound::AllRegions(ref rs) =>
1606                 rs.iter()
1607                   .map(|&r| normalize(tcx, var_values, r))
1608                   .all(|r| region_rels.is_subregion_of(min, r)),
1609
1610             &VerifyBound::AnyBound(ref bs) =>
1611                 bs.iter()
1612                   .any(|b| b.is_met(region_rels, var_values, min)),
1613
1614             &VerifyBound::AllBounds(ref bs) =>
1615                 bs.iter()
1616                   .all(|b| b.is_met(region_rels, var_values, min)),
1617         }
1618     }
1619 }