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