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