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