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(&'tcx Region, 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, &'tcx Region),
  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(&'tcx Region, &'tcx Region),
  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: &'tcx Region,
  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<&'tcx Region>),
  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<&'tcx Region>),
  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: &'tcx Region,
 108     b: &'tcx Region,
 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, 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>, &'tcx Region, &'tcx Region),
 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>, &'tcx Region),
 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                    &'tcx Region,
 172                    SubregionOrigin<'tcx>,
 173                    &'tcx Region),
 174 }
 175
 176 #[derive(Clone, Debug)]
 177 pub enum ProcessedErrorOrigin<'tcx> {
 178     ConcreteFailure(SubregionOrigin<'tcx>, &'tcx Region, &'tcx Region),
 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, 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<&'tcx ty::Region>
 275 }
 276
 277 impl<'a, 'gcx, 'tcx> TaintSet<'tcx> {
 278     fn new(directions: TaintDirections,
 279            initial_region: &'tcx ty::Region)
 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<&'tcx ty::Region> {
 332         self.regions
 333     }
 334
 335     fn len(&self) -> usize {
 336         self.regions.len()
 337     }
 338
 339     fn add_edge(&mut self,
 340                 source: &'tcx ty::Region,
 341                 target: &'tcx ty::Region) {
 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                            -> &'tcx Region {
 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<&'tcx ty::Region>,
 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<&'tcx ty::Region>,
 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) -> &'tcx Region {
 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, 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: &'tcx Region,
 680                          sup: &'tcx Region) {
 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: &'tcx Region,
 696                           sup: &'tcx Region) {
 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: &'tcx Region,
 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: &'tcx Region,
 750                        b: &'tcx Region)
 751                        -> &'tcx Region {
 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: &'tcx Region,
 776                        b: &'tcx Region)
 777                        -> &'tcx Region {
 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) -> &'tcx ty::Region {
 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) -> &'tcx ty::Region {
 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: &'tcx Region,
 829                            b: &'tcx Region,
 830                            origin: SubregionOrigin<'tcx>,
 831                            mut relate: F)
 832                            -> &'tcx Region
 833         where F: FnMut(&RegionVarBindings<'a, 'gcx, 'tcx>, &'tcx Region, &'tcx Region)
 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: &'tcx Region,
 873                    directions: TaintDirections)
 874                    -> FxHashSet<&'tcx ty::Region> {
 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,
 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,
 907                             a: &'tcx Region,
 908                             b: &'tcx Region)
 909                             -> &'tcx Region {
 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                 let r_id = self.tcx.region_maps.nearest_common_ancestor(fr.scope, s_id);
 942
 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                     self.tcx.mk_region(ReFree(fr))
 948                 } else {
 949                     // otherwise, we don't know what the free region is,
 950                     // so we must conservatively say the LUB is static:
 951                     self.tcx.mk_region(ReStatic)
 952                 }
 953             }
 954
 955             (&ReScope(a_id), &ReScope(b_id)) => {
 956                 // The region corresponding to an outer block is a
 957                 // subtype of the region corresponding to an inner
 958                 // block.
 959                 self.tcx.mk_region(ReScope(
 960                     self.tcx.region_maps.nearest_common_ancestor(a_id, b_id)))
 961             }
 962
 963             (&ReFree(a_fr), &ReFree(b_fr)) => {
 964                 self.tcx.mk_region(free_regions.lub_free_regions(a_fr, b_fr))
 965             }
 966
 967             // For these types, we cannot define any additional
 968             // relationship:
 969             (&ReSkolemized(..), _) |
 970             (_, &ReSkolemized(..)) => {
 971                 if a == b {
 972                     a
 973                 } else {
 974                     self.tcx.mk_region(ReStatic)
 975                 }
 976             }
 977         }
 978     }
 979 }
 980
 981 // ______________________________________________________________________
 982
 983 #[derive(Copy, Clone, Debug)]
 984 pub enum VarValue<'tcx> {
 985     Value(&'tcx Region),
 986     ErrorValue,
 987 }
 988
 989 struct RegionAndOrigin<'tcx> {
 990     region: &'tcx Region,
 991     origin: SubregionOrigin<'tcx>,
 992 }
 993
 994 type RegionGraph<'tcx> = graph::Graph<(), Constraint<'tcx>>;
 995
 996 impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
 997     fn infer_variable_values(&self,
 998                              free_regions: &FreeRegionMap,
 999                              errors: &mut Vec<RegionResolutionError<'tcx>>,
1000                              subject: ast::NodeId)
1001                              -> Vec<VarValue<'tcx>> {
1002         let mut var_data = self.construct_var_data();
1003
1004         // Dorky hack to cause `dump_constraints` to only get called
1005         // if debug mode is enabled:
1006         debug!("----() End constraint listing (subject={}) {:?}---",
1007                subject,
1008                self.dump_constraints(subject));
1009         graphviz::maybe_print_constraints_for(self, subject);
1010
1011         let graph = self.construct_graph();
1012         self.expand_givens(&graph);
1013         self.expansion(free_regions, &mut var_data);
1014         self.collect_errors(free_regions, &mut var_data, errors);
1015         self.collect_var_errors(free_regions, &var_data, &graph, errors);
1016         var_data
1017     }
1018
1019     fn construct_var_data(&self) -> Vec<VarValue<'tcx>> {
1020         (0..self.num_vars() as usize)
1021             .map(|_| Value(self.tcx.mk_region(ty::ReEmpty)))
1022             .collect()
1023     }
1024
1025     fn dump_constraints(&self, subject: ast::NodeId) {
1026         debug!("----() Start constraint listing (subject={}) ()----",
1027                subject);
1028         for (idx, (constraint, _)) in self.constraints.borrow().iter().enumerate() {
1029             debug!("Constraint {} => {:?}", idx, constraint);
1030         }
1031     }
1032
1033     fn expand_givens(&self, graph: &RegionGraph) {
1034         // Givens are a kind of horrible hack to account for
1035         // constraints like 'c <= '0 that are known to hold due to
1036         // closure signatures (see the comment above on the `givens`
1037         // field). They should go away. But until they do, the role
1038         // of this fn is to account for the transitive nature:
1039         //
1040         //     Given 'c <= '0
1041         //     and   '0 <= '1
1042         //     then  'c <= '1
1043
1044         let mut givens = self.givens.borrow_mut();
1045         let seeds: Vec<_> = givens.iter().cloned().collect();
1046         for (fr, vid) in seeds {
1047             let seed_index = NodeIndex(vid.index as usize);
1048             for succ_index in graph.depth_traverse(seed_index, OUTGOING) {
1049                 let succ_index = succ_index.0 as u32;
1050                 if succ_index < self.num_vars() {
1051                     let succ_vid = RegionVid { index: succ_index };
1052                     givens.insert((fr, succ_vid));
1053                 }
1054             }
1055         }
1056     }
1057
1058     fn expansion(&self, free_regions: &FreeRegionMap, 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(free_regions, 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(free_regions, 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                    free_regions: &FreeRegionMap,
1088                    a_region: &'tcx Region,
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(free_regions, 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                       free_regions: &FreeRegionMap,
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 free_regions.is_subregion_of(self.tcx, 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 !free_regions.is_subregion_of(self.tcx, 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(self.tcx, free_regions, 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                           free_regions: &FreeRegionMap,
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(free_regions,
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                                         free_regions: &FreeRegionMap,
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 !free_regions.is_subregion_of(self.tcx, 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: &'tcx ty::Region)
1483                              -> &'tcx ty::Region {
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                           -> &'tcx ty::Region {
1494     match values[rid.index as usize] {
1495         Value(r) => r,
1496         ErrorValue => tcx.mk_region(ReStatic), // 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(&'tcx ty::Region)) {
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, tcx: TyCtxt<'a, 'gcx, 'tcx>,
1594               free_regions: &FreeRegionMap,
1595               var_values: &Vec<VarValue<'tcx>>,
1596               min: &'tcx ty::Region)
1597               -> bool {
1598         match self {
1599             &VerifyBound::AnyRegion(ref rs) =>
1600                 rs.iter()
1601                   .map(|&r| normalize(tcx, var_values, r))
1602                   .any(|r| free_regions.is_subregion_of(tcx, min, r)),
1603
1604             &VerifyBound::AllRegions(ref rs) =>
1605                 rs.iter()
1606                   .map(|&r| normalize(tcx, var_values, r))
1607                   .all(|r| free_regions.is_subregion_of(tcx, min, r)),
1608
1609             &VerifyBound::AnyBound(ref bs) =>
1610                 bs.iter()
1611                   .any(|b| b.is_met(tcx, free_regions, var_values, min)),
1612
1613             &VerifyBound::AllBounds(ref bs) =>
1614                 bs.iter()
1615                   .all(|b| b.is_met(tcx, free_regions, var_values, min)),
1616         }
1617     }
1618 }