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