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