src/librustc/middle/typeck/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
  14 use middle::ty;
  15 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid, Vid};
  16 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound,
  17                  ReLateBound};
  18 use middle::ty::{ReScope, ReVar, ReSkolemized, BrFresh};
  19 use middle::typeck::infer::cres;
  20 use middle::typeck::infer::{RegionVariableOrigin, SubregionOrigin, TypeTrace};
  21 use middle::typeck::infer;
  22 use middle::graph;
  23 use middle::graph::{Direction, NodeIndex};
  24 use util::common::indenter;
  25 use util::ppaux::{Repr};
  26
  27 use std::cell::{Cell, RefCell};
  28 use std::uint;
  29 use std::slice;
  30 use collections::{HashMap, HashSet};
  31 use syntax::ast;
  32
  33 mod doc;
  34
  35 #[deriving(Eq, TotalEq, Hash)]
  36 pub enum Constraint {
  37     ConstrainVarSubVar(RegionVid, RegionVid),
  38     ConstrainRegSubVar(Region, RegionVid),
  39     ConstrainVarSubReg(RegionVid, Region),
  40     ConstrainRegSubReg(Region, Region),
  41 }
  42
  43 #[deriving(Eq, TotalEq, Hash)]
  44 pub struct TwoRegions {
  45     a: Region,
  46     b: Region,
  47 }
  48
  49 pub enum UndoLogEntry {
  50     Snapshot,
  51     AddVar(RegionVid),
  52     AddConstraint(Constraint),
  53     AddCombination(CombineMapType, TwoRegions)
  54 }
  55
  56 pub enum CombineMapType {
  57     Lub, Glb
  58 }
  59
  60 #[deriving(Clone)]
  61 pub enum RegionResolutionError {
  62     /// `ConcreteFailure(o, a, b)`:
  63     ///
  64     /// `o` requires that `a <= b`, but this does not hold
  65     ConcreteFailure(SubregionOrigin, Region, Region),
  66
  67     /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
  68     ///
  69     /// Could not infer a value for `v` because `sub_r <= v` (due to
  70     /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
  71     /// `sub_r <= sup_r` does not hold.
  72     SubSupConflict(RegionVariableOrigin,
  73                    SubregionOrigin, Region,
  74                    SubregionOrigin, Region),
  75
  76     /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
  77     ///
  78     /// Could not infer a value for `v` because `v <= r1` (due to
  79     /// `origin1`) and `v <= r2` (due to `origin2`) and
  80     /// `r1` and `r2` have no intersection.
  81     SupSupConflict(RegionVariableOrigin,
  82                    SubregionOrigin, Region,
  83                    SubregionOrigin, Region),
  84
  85     /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
  86     /// more specific errors message by suggesting to the user where they
  87     /// should put a lifetime. In those cases we process and put those errors
  88     /// into `ProcessedErrors` before we do any reporting.
  89     ProcessedErrors(Vec<RegionVariableOrigin>,
  90                     Vec<(TypeTrace, ty::type_err)>,
  91                     Vec<SameRegions>),
  92 }
  93
  94 /// SameRegions is used to group regions that we think are the same and would
  95 /// like to indicate so to the user.
  96 /// For example, the following function
  97 /// ```
  98 /// struct Foo { bar: int }
  99 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
 100 ///    &x.bar
 101 /// }
 102 /// ```
 103 /// would report an error because we expect 'a and 'b to match, and so we group
 104 /// 'a and 'b together inside a SameRegions struct
 105 #[deriving(Clone)]
 106 pub struct SameRegions {
 107     scope_id: ast::NodeId,
 108     regions: Vec<BoundRegion>
 109 }
 110
 111 impl SameRegions {
 112     pub fn contains(&self, other: &BoundRegion) -> bool {
 113         self.regions.contains(other)
 114     }
 115
 116     pub fn push(&mut self, other: BoundRegion) {
 117         self.regions.push(other);
 118     }
 119 }
 120
 121 pub type CombineMap = HashMap<TwoRegions, RegionVid>;
 122
 123 pub struct RegionVarBindings<'a> {
 124     tcx: &'a ty::ctxt,
 125     var_origins: RefCell<Vec<RegionVariableOrigin>>,
 126     constraints: RefCell<HashMap<Constraint, SubregionOrigin>>,
 127     lubs: RefCell<CombineMap>,
 128     glbs: RefCell<CombineMap>,
 129     skolemization_count: Cell<uint>,
 130     bound_count: Cell<uint>,
 131
 132     // The undo log records actions that might later be undone.
 133     //
 134     // Note: when the undo_log is empty, we are not actively
 135     // snapshotting.  When the `start_snapshot()` method is called, we
 136     // push a Snapshot entry onto the list to indicate that we are now
 137     // actively snapshotting.  The reason for this is that otherwise
 138     // we end up adding entries for things like the lower bound on
 139     // a variable and so forth, which can never be rolled back.
 140     undo_log: RefCell<Vec<UndoLogEntry> >,
 141
 142     // This contains the results of inference.  It begins as an empty
 143     // option and only acquires a value after inference is complete.
 144     values: RefCell<Option<Vec<VarValue> >>,
 145 }
 146
 147 pub fn RegionVarBindings<'a>(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
 148     RegionVarBindings {
 149         tcx: tcx,
 150         var_origins: RefCell::new(Vec::new()),
 151         values: RefCell::new(None),
 152         constraints: RefCell::new(HashMap::new()),
 153         lubs: RefCell::new(HashMap::new()),
 154         glbs: RefCell::new(HashMap::new()),
 155         skolemization_count: Cell::new(0),
 156         bound_count: Cell::new(0),
 157         undo_log: RefCell::new(Vec::new())
 158     }
 159 }
 160
 161 impl<'a> RegionVarBindings<'a> {
 162     pub fn in_snapshot(&self) -> bool {
 163         self.undo_log.borrow().len() > 0
 164     }
 165
 166     pub fn start_snapshot(&self) -> uint {
 167         debug!("RegionVarBindings: start_snapshot()");
 168         if self.in_snapshot() {
 169             self.undo_log.borrow().len()
 170         } else {
 171             self.undo_log.borrow_mut().push(Snapshot);
 172             0
 173         }
 174     }
 175
 176     pub fn commit(&self) {
 177         debug!("RegionVarBindings: commit()");
 178         let mut undo_log = self.undo_log.borrow_mut();
 179         while undo_log.len() > 0 {
 180             undo_log.pop().unwrap();
 181         }
 182     }
 183
 184     pub fn rollback_to(&self, snapshot: uint) {
 185         debug!("RegionVarBindings: rollback_to({})", snapshot);
 186         let mut undo_log = self.undo_log.borrow_mut();
 187         while undo_log.len() > snapshot {
 188             let undo_item = undo_log.pop().unwrap();
 189             debug!("undo_item={:?}", undo_item);
 190             match undo_item {
 191               Snapshot => {}
 192               AddVar(vid) => {
 193                 let mut var_origins = self.var_origins.borrow_mut();
 194                 assert_eq!(var_origins.len(), vid.to_uint() + 1);
 195                 var_origins.pop().unwrap();
 196               }
 197               AddConstraint(ref constraint) => {
 198                 self.constraints.borrow_mut().remove(constraint);
 199               }
 200               AddCombination(Glb, ref regions) => {
 201                 self.glbs.borrow_mut().remove(regions);
 202               }
 203               AddCombination(Lub, ref regions) => {
 204                 self.lubs.borrow_mut().remove(regions);
 205               }
 206             }
 207         }
 208     }
 209
 210     pub fn num_vars(&self) -> uint {
 211         self.var_origins.borrow().len()
 212     }
 213
 214     pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
 215         let id = self.num_vars();
 216         self.var_origins.borrow_mut().push(origin);
 217         let vid = RegionVid { id: id };
 218         if self.in_snapshot() {
 219             self.undo_log.borrow_mut().push(AddVar(vid));
 220         }
 221         debug!("created new region variable {:?} with origin {:?}",
 222                vid, origin.repr(self.tcx));
 223         return vid;
 224     }
 225
 226     pub fn new_skolemized(&self, br: ty::BoundRegion) -> Region {
 227         let sc = self.skolemization_count.get();
 228         self.skolemization_count.set(sc + 1);
 229         ReInfer(ReSkolemized(sc, br))
 230     }
 231
 232     pub fn new_bound(&self, binder_id: ast::NodeId) -> Region {
 233         // Creates a fresh bound variable for use in GLB computations.
 234         // See discussion of GLB computation in the large comment at
 235         // the top of this file for more details.
 236         //
 237         // This computation is potentially wrong in the face of
 238         // rollover.  It's conceivable, if unlikely, that one might
 239         // wind up with accidental capture for nested functions in
 240         // that case, if the outer function had bound regions created
 241         // a very long time before and the inner function somehow
 242         // wound up rolling over such that supposedly fresh
 243         // identifiers were in fact shadowed. For now, we just assert
 244         // that there is no rollover -- eventually we should try to be
 245         // robust against this possibility, either by checking the set
 246         // of bound identifiers that appear in a given expression and
 247         // ensure that we generate one that is distinct, or by
 248         // changing the representation of bound regions in a fn
 249         // declaration
 250
 251         let sc = self.bound_count.get();
 252         self.bound_count.set(sc + 1);
 253
 254         if sc >= self.bound_count.get() {
 255             self.tcx.sess.bug("rollover in RegionInference new_bound()");
 256         }
 257
 258         ReLateBound(binder_id, BrFresh(sc))
 259     }
 260
 261     fn values_are_none(&self) -> bool {
 262         self.values.borrow().is_none()
 263     }
 264
 265     pub fn add_constraint(&self,
 266                           constraint: Constraint,
 267                           origin: SubregionOrigin) {
 268         // cannot add constraints once regions are resolved
 269         assert!(self.values_are_none());
 270
 271         debug!("RegionVarBindings: add_constraint({:?})", constraint);
 272
 273         if self.constraints.borrow_mut().insert(constraint, origin) {
 274             if self.in_snapshot() {
 275                 self.undo_log.borrow_mut().push(AddConstraint(constraint));
 276             }
 277         }
 278     }
 279
 280     pub fn make_subregion(&self,
 281                           origin: SubregionOrigin,
 282                           sub: Region,
 283                           sup: Region) {
 284         // cannot add constraints once regions are resolved
 285         assert!(self.values_are_none());
 286
 287         debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
 288                sub.repr(self.tcx),
 289                sup.repr(self.tcx),
 290                origin.repr(self.tcx));
 291
 292         match (sub, sup) {
 293           (ReEarlyBound(..), _) |
 294           (ReLateBound(..), _) |
 295           (_, ReEarlyBound(..)) |
 296           (_, ReLateBound(..)) => {
 297             self.tcx.sess.span_bug(
 298                 origin.span(),
 299                 format!("cannot relate bound region: {} <= {}",
 300                         sub.repr(self.tcx),
 301                         sup.repr(self.tcx)));
 302           }
 303           (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
 304             self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
 305           }
 306           (r, ReInfer(ReVar(sup_id))) => {
 307             self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
 308           }
 309           (ReInfer(ReVar(sub_id)), r) => {
 310             self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
 311           }
 312           _ => {
 313             self.add_constraint(ConstrainRegSubReg(sub, sup), origin);
 314           }
 315         }
 316     }
 317
 318     pub fn lub_regions(&self,
 319                        origin: SubregionOrigin,
 320                        a: Region,
 321                        b: Region)
 322                        -> Region {
 323         // cannot add constraints once regions are resolved
 324         assert!(self.values_are_none());
 325
 326         debug!("RegionVarBindings: lub_regions({:?}, {:?})", a, b);
 327         match (a, b) {
 328             (ReStatic, _) | (_, ReStatic) => {
 329                 ReStatic // nothing lives longer than static
 330             }
 331
 332             _ => {
 333                 self.combine_vars(
 334                     Lub, a, b, origin,
 335                     |this, old_r, new_r|
 336                     this.make_subregion(origin, old_r, new_r))
 337             }
 338         }
 339     }
 340
 341     pub fn glb_regions(&self,
 342                        origin: SubregionOrigin,
 343                        a: Region,
 344                        b: Region)
 345                        -> Region {
 346         // cannot add constraints once regions are resolved
 347         assert!(self.values_are_none());
 348
 349         debug!("RegionVarBindings: glb_regions({:?}, {:?})", a, b);
 350         match (a, b) {
 351             (ReStatic, r) | (r, ReStatic) => {
 352                 // static lives longer than everything else
 353                 r
 354             }
 355
 356             _ => {
 357                 self.combine_vars(
 358                     Glb, a, b, origin,
 359                     |this, old_r, new_r|
 360                     this.make_subregion(origin, new_r, old_r))
 361             }
 362         }
 363     }
 364
 365     pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
 366         let v = match *self.values.borrow() {
 367             None => {
 368                 self.tcx.sess.span_bug(
 369                     self.var_origins.borrow().get(rid.to_uint()).span(),
 370                     format!("attempt to resolve region variable before \
 371                              values have been computed!"))
 372             }
 373             Some(ref values) => *values.get(rid.to_uint())
 374         };
 375
 376         debug!("RegionVarBindings: resolve_var({:?}={})={:?}",
 377                rid, rid.to_uint(), v);
 378         match v {
 379             Value(r) => r,
 380
 381             NoValue => {
 382                 // No constraints, return ty::ReEmpty
 383                 ReEmpty
 384             }
 385
 386             ErrorValue => {
 387                 // An error that has previously been reported.
 388                 ReStatic
 389             }
 390         }
 391     }
 392
 393     fn combine_map<'a>(&'a self, t: CombineMapType)
 394                    -> &'a RefCell<CombineMap> {
 395         match t {
 396             Glb => &self.glbs,
 397             Lub => &self.lubs,
 398         }
 399     }
 400
 401     pub fn combine_vars(&self,
 402                         t: CombineMapType,
 403                         a: Region,
 404                         b: Region,
 405                         origin: SubregionOrigin,
 406                         relate: |this: &RegionVarBindings,
 407                                  old_r: Region,
 408                                  new_r: Region|)
 409                         -> Region {
 410         let vars = TwoRegions { a: a, b: b };
 411         match self.combine_map(t).borrow().find(&vars) {
 412             Some(&c) => {
 413                 return ReInfer(ReVar(c));
 414             }
 415             None => {}
 416         }
 417         let c = self.new_region_var(infer::MiscVariable(origin.span()));
 418         self.combine_map(t).borrow_mut().insert(vars, c);
 419         if self.in_snapshot() {
 420             self.undo_log.borrow_mut().push(AddCombination(t, vars));
 421         }
 422         relate(self, a, ReInfer(ReVar(c)));
 423         relate(self, b, ReInfer(ReVar(c)));
 424         debug!("combine_vars() c={:?}", c);
 425         ReInfer(ReVar(c))
 426     }
 427
 428     pub fn vars_created_since_snapshot(&self, snapshot: uint)
 429                                        -> Vec<RegionVid> {
 430         self.undo_log.borrow().slice_from(snapshot).iter()
 431             .filter_map(|&elt| match elt {
 432                 AddVar(vid) => Some(vid),
 433                 _ => None
 434             })
 435             .collect()
 436     }
 437
 438     pub fn tainted(&self, snapshot: uint, r0: Region) -> Vec<Region> {
 439         /*!
 440          * Computes all regions that have been related to `r0` in any
 441          * way since the snapshot `snapshot` was taken---`r0` itself
 442          * will be the first entry. This is used when checking whether
 443          * skolemized regions are being improperly related to other
 444          * regions.
 445          */
 446
 447         debug!("tainted(snapshot={}, r0={:?})", snapshot, r0);
 448         let _indenter = indenter();
 449
 450         let undo_len = self.undo_log.borrow().len();
 451
 452         // `result_set` acts as a worklist: we explore all outgoing
 453         // edges and add any new regions we find to result_set.  This
 454         // is not a terribly efficient implementation.
 455         let mut result_set = vec!(r0);
 456         let mut result_index = 0;
 457         while result_index < result_set.len() {
 458             // nb: can't use uint::range() here because result_set grows
 459             let r = *result_set.get(result_index);
 460
 461             debug!("result_index={}, r={:?}", result_index, r);
 462
 463             let mut undo_index = snapshot;
 464             while undo_index < undo_len {
 465                 // nb: can't use uint::range() here as we move result_set
 466                 let regs = match self.undo_log.borrow().get(undo_index) {
 467                     &AddConstraint(ConstrainVarSubVar(ref a, ref b)) => {
 468                         Some((ReInfer(ReVar(*a)),
 469                               ReInfer(ReVar(*b))))
 470                     }
 471                     &AddConstraint(ConstrainRegSubVar(ref a, ref b)) => {
 472                         Some((*a, ReInfer(ReVar(*b))))
 473                     }
 474                     &AddConstraint(ConstrainVarSubReg(ref a, ref b)) => {
 475                         Some((ReInfer(ReVar(*a)), *b))
 476                     }
 477                     &AddConstraint(ConstrainRegSubReg(a, b)) => {
 478                         Some((a, b))
 479                     }
 480                     _ => {
 481                         None
 482                     }
 483                 };
 484
 485                 match regs {
 486                     None => {}
 487                     Some((r1, r2)) => {
 488                         result_set =
 489                             consider_adding_edge(result_set, r, r1, r2);
 490                         result_set =
 491                             consider_adding_edge(result_set, r, r2, r1);
 492                     }
 493                 }
 494
 495                 undo_index += 1;
 496             }
 497
 498             result_index += 1;
 499         }
 500
 501         return result_set;
 502
 503         fn consider_adding_edge(result_set: Vec<Region> ,
 504                                 r: Region,
 505                                 r1: Region,
 506                                 r2: Region) -> Vec<Region> {
 507             let mut result_set = result_set;
 508             if r == r1 { // Clearly, this is potentially inefficient.
 509                 if !result_set.iter().any(|x| *x == r2) {
 510                     result_set.push(r2);
 511                 }
 512             }
 513             return result_set;
 514         }
 515     }
 516
 517     /**
 518     This function performs the actual region resolution.  It must be
 519     called after all constraints have been added.  It performs a
 520     fixed-point iteration to find region values which satisfy all
 521     constraints, assuming such values can be found; if they cannot,
 522     errors are reported.
 523     */
 524     pub fn resolve_regions(&self) -> Vec<RegionResolutionError> {
 525         debug!("RegionVarBindings: resolve_regions()");
 526         let mut errors = vec!();
 527         let v = self.infer_variable_values(&mut errors);
 528         *self.values.borrow_mut() = Some(v);
 529         errors
 530     }
 531 }
 532
 533 impl<'a> RegionVarBindings<'a> {
 534     fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
 535         self.tcx.region_maps.is_subregion_of(sub, sup)
 536     }
 537
 538     fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
 539         match (a, b) {
 540           (ReLateBound(..), _) |
 541           (_, ReLateBound(..)) |
 542           (ReEarlyBound(..), _) |
 543           (_, ReEarlyBound(..)) => {
 544             self.tcx.sess.bug(
 545                 format!("cannot relate bound region: LUB({}, {})",
 546                         a.repr(self.tcx),
 547                         b.repr(self.tcx)));
 548           }
 549
 550           (ReStatic, _) | (_, ReStatic) => {
 551             ReStatic // nothing lives longer than static
 552           }
 553
 554           (ReEmpty, r) | (r, ReEmpty) => {
 555             r // everything lives longer than empty
 556           }
 557
 558           (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
 559             self.tcx.sess.span_bug(
 560                 self.var_origins.borrow().get(v_id.to_uint()).span(),
 561                 format!("lub_concrete_regions invoked with \
 562                       non-concrete regions: {:?}, {:?}", a, b));
 563           }
 564
 565           (f @ ReFree(ref fr), ReScope(s_id)) |
 566           (ReScope(s_id), f @ ReFree(ref fr)) => {
 567             // A "free" region can be interpreted as "some region
 568             // at least as big as the block fr.scope_id".  So, we can
 569             // reasonably compare free regions and scopes:
 570             match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
 571               // if the free region's scope `fr.scope_id` is bigger than
 572               // the scope region `s_id`, then the LUB is the free
 573               // region itself:
 574               Some(r_id) if r_id == fr.scope_id => f,
 575
 576               // otherwise, we don't know what the free region is,
 577               // so we must conservatively say the LUB is static:
 578               _ => ReStatic
 579             }
 580           }
 581
 582           (ReScope(a_id), ReScope(b_id)) => {
 583             // The region corresponding to an outer block is a
 584             // subtype of the region corresponding to an inner
 585             // block.
 586             match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
 587               Some(r_id) => ReScope(r_id),
 588               _ => ReStatic
 589             }
 590           }
 591
 592           (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 593              self.lub_free_regions(a_fr, b_fr)
 594           }
 595
 596           // For these types, we cannot define any additional
 597           // relationship:
 598           (ReInfer(ReSkolemized(..)), _) |
 599           (_, ReInfer(ReSkolemized(..))) => {
 600             if a == b {a} else {ReStatic}
 601           }
 602         }
 603     }
 604
 605     fn lub_free_regions(&self,
 606                         a: &FreeRegion,
 607                         b: &FreeRegion) -> ty::Region
 608     {
 609         /*!
 610          * Computes a region that encloses both free region arguments.
 611          * Guarantee that if the same two regions are given as argument,
 612          * in any order, a consistent result is returned.
 613          */
 614
 615         return match a.cmp(b) {
 616             Less => helper(self, a, b),
 617             Greater => helper(self, b, a),
 618             Equal => ty::ReFree(*a)
 619         };
 620
 621         fn helper(this: &RegionVarBindings,
 622                   a: &FreeRegion,
 623                   b: &FreeRegion) -> ty::Region
 624         {
 625             if this.tcx.region_maps.sub_free_region(*a, *b) {
 626                 ty::ReFree(*b)
 627             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 628                 ty::ReFree(*a)
 629             } else {
 630                 ty::ReStatic
 631             }
 632         }
 633     }
 634
 635     fn glb_concrete_regions(&self,
 636                             a: Region,
 637                             b: Region)
 638                          -> cres<Region> {
 639         debug!("glb_concrete_regions({:?}, {:?})", a, b);
 640         match (a, b) {
 641             (ReLateBound(..), _) |
 642             (_, ReLateBound(..)) |
 643             (ReEarlyBound(..), _) |
 644             (_, ReEarlyBound(..)) => {
 645               self.tcx.sess.bug(
 646                   format!("cannot relate bound region: GLB({}, {})",
 647                           a.repr(self.tcx),
 648                           b.repr(self.tcx)));
 649             }
 650
 651             (ReStatic, r) | (r, ReStatic) => {
 652                 // static lives longer than everything else
 653                 Ok(r)
 654             }
 655
 656             (ReEmpty, _) | (_, ReEmpty) => {
 657                 // nothing lives shorter than everything else
 658                 Ok(ReEmpty)
 659             }
 660
 661             (ReInfer(ReVar(v_id)), _) |
 662             (_, ReInfer(ReVar(v_id))) => {
 663                 self.tcx.sess.span_bug(
 664                     self.var_origins.borrow().get(v_id.to_uint()).span(),
 665                     format!("glb_concrete_regions invoked with \
 666                           non-concrete regions: {:?}, {:?}", a, b));
 667             }
 668
 669             (ReFree(ref fr), s @ ReScope(s_id)) |
 670             (s @ ReScope(s_id), ReFree(ref fr)) => {
 671                 // Free region is something "at least as big as
 672                 // `fr.scope_id`."  If we find that the scope `fr.scope_id` is bigger
 673                 // than the scope `s_id`, then we can say that the GLB
 674                 // is the scope `s_id`.  Otherwise, as we do not know
 675                 // big the free region is precisely, the GLB is undefined.
 676                 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
 677                     Some(r_id) if r_id == fr.scope_id => Ok(s),
 678                     _ => Err(ty::terr_regions_no_overlap(b, a))
 679                 }
 680             }
 681
 682             (ReScope(a_id), ReScope(b_id)) => {
 683                 self.intersect_scopes(a, b, a_id, b_id)
 684             }
 685
 686             (ReFree(ref a_fr), ReFree(ref b_fr)) => {
 687                 self.glb_free_regions(a_fr, b_fr)
 688             }
 689
 690             // For these types, we cannot define any additional
 691             // relationship:
 692             (ReInfer(ReSkolemized(..)), _) |
 693             (_, ReInfer(ReSkolemized(..))) => {
 694                 if a == b {
 695                     Ok(a)
 696                 } else {
 697                     Err(ty::terr_regions_no_overlap(b, a))
 698                 }
 699             }
 700         }
 701     }
 702
 703     fn glb_free_regions(&self,
 704                         a: &FreeRegion,
 705                         b: &FreeRegion) -> cres<ty::Region>
 706     {
 707         /*!
 708          * Computes a region that is enclosed by both free region arguments,
 709          * if any. Guarantees that if the same two regions are given as argument,
 710          * in any order, a consistent result is returned.
 711          */
 712
 713         return match a.cmp(b) {
 714             Less => helper(self, a, b),
 715             Greater => helper(self, b, a),
 716             Equal => Ok(ty::ReFree(*a))
 717         };
 718
 719         fn helper(this: &RegionVarBindings,
 720                   a: &FreeRegion,
 721                   b: &FreeRegion) -> cres<ty::Region>
 722         {
 723             if this.tcx.region_maps.sub_free_region(*a, *b) {
 724                 Ok(ty::ReFree(*a))
 725             } else if this.tcx.region_maps.sub_free_region(*b, *a) {
 726                 Ok(ty::ReFree(*b))
 727             } else {
 728                 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
 729                                       a.scope_id, b.scope_id)
 730             }
 731         }
 732     }
 733
 734     fn intersect_scopes(&self,
 735                         region_a: ty::Region,
 736                         region_b: ty::Region,
 737                         scope_a: ast::NodeId,
 738                         scope_b: ast::NodeId) -> cres<Region>
 739     {
 740         // We want to generate the intersection of two
 741         // scopes or two free regions.  So, if one of
 742         // these scopes is a subscope of the other, return
 743         // it.  Otherwise fail.
 744         debug!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
 745                scope_a, scope_b, region_a, region_b);
 746         match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
 747             Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
 748             Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
 749             _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
 750         }
 751     }
 752 }
 753
 754 // ______________________________________________________________________
 755
 756 #[deriving(Eq, Show)]
 757 enum Classification { Expanding, Contracting }
 758
 759 pub enum VarValue { NoValue, Value(Region), ErrorValue }
 760
 761 struct VarData {
 762     classification: Classification,
 763     value: VarValue,
 764 }
 765
 766 struct RegionAndOrigin {
 767     region: Region,
 768     origin: SubregionOrigin,
 769 }
 770
 771 type RegionGraph = graph::Graph<(), Constraint>;
 772
 773 impl<'a> RegionVarBindings<'a> {
 774     fn infer_variable_values(&self,
 775                              errors: &mut Vec<RegionResolutionError>)
 776                              -> Vec<VarValue> {
 777         let mut var_data = self.construct_var_data();
 778         self.expansion(var_data.as_mut_slice());
 779         self.contraction(var_data.as_mut_slice());
 780         self.collect_concrete_region_errors(&mut *errors);
 781         self.extract_values_and_collect_conflicts(var_data.as_slice(), errors)
 782     }
 783
 784     fn construct_var_data(&self) -> Vec<VarData> {
 785         Vec::from_fn(self.num_vars(), |_| {
 786             VarData {
 787                 // All nodes are initially classified as contracting; during
 788                 // the expansion phase, we will shift the classification for
 789                 // those nodes that have a concrete region predecessor to
 790                 // Expanding.
 791                 classification: Contracting,
 792                 value: NoValue,
 793             }
 794         })
 795     }
 796
 797     fn expansion(&self, var_data: &mut [VarData]) {
 798         self.iterate_until_fixed_point("Expansion", |constraint| {
 799             match *constraint {
 800               ConstrainRegSubVar(a_region, b_vid) => {
 801                 let b_data = &mut var_data[b_vid.to_uint()];
 802                 self.expand_node(a_region, b_vid, b_data)
 803               }
 804               ConstrainVarSubVar(a_vid, b_vid) => {
 805                 match var_data[a_vid.to_uint()].value {
 806                   NoValue | ErrorValue => false,
 807                   Value(a_region) => {
 808                     let b_node = &mut var_data[b_vid.to_uint()];
 809                     self.expand_node(a_region, b_vid, b_node)
 810                   }
 811                 }
 812               }
 813               ConstrainVarSubReg(..) => {
 814                 // This is a contraction constraint.  Ignore it.
 815                 false
 816               }
 817               ConstrainRegSubReg(..) => {
 818                 // No region variables involved. Ignore.
 819                 false
 820               }
 821             }
 822         })
 823     }
 824
 825     fn expand_node(&self,
 826                    a_region: Region,
 827                    b_vid: RegionVid,
 828                    b_data: &mut VarData)
 829                    -> bool {
 830         debug!("expand_node({:?}, {:?} == {:?})",
 831                a_region, b_vid, b_data.value);
 832
 833         b_data.classification = Expanding;
 834         match b_data.value {
 835           NoValue => {
 836             debug!("Setting initial value of {:?} to {:?}", b_vid, a_region);
 837
 838             b_data.value = Value(a_region);
 839             return true;
 840           }
 841
 842           Value(cur_region) => {
 843             let lub = self.lub_concrete_regions(a_region, cur_region);
 844             if lub == cur_region {
 845                 return false;
 846             }
 847
 848             debug!("Expanding value of {:?} from {:?} to {:?}",
 849                    b_vid, cur_region, lub);
 850
 851             b_data.value = Value(lub);
 852             return true;
 853           }
 854
 855           ErrorValue => {
 856             return false;
 857           }
 858         }
 859     }
 860
 861     fn contraction(&self,
 862                    var_data: &mut [VarData]) {
 863         self.iterate_until_fixed_point("Contraction", |constraint| {
 864             match *constraint {
 865               ConstrainRegSubVar(..) => {
 866                 // This is an expansion constraint.  Ignore.
 867                 false
 868               }
 869               ConstrainVarSubVar(a_vid, b_vid) => {
 870                 match var_data[b_vid.to_uint()].value {
 871                   NoValue | ErrorValue => false,
 872                   Value(b_region) => {
 873                     let a_data = &mut var_data[a_vid.to_uint()];
 874                     self.contract_node(a_vid, a_data, b_region)
 875                   }
 876                 }
 877               }
 878               ConstrainVarSubReg(a_vid, b_region) => {
 879                 let a_data = &mut var_data[a_vid.to_uint()];
 880                 self.contract_node(a_vid, a_data, b_region)
 881               }
 882               ConstrainRegSubReg(..) => {
 883                 // No region variables involved. Ignore.
 884                 false
 885               }
 886             }
 887         })
 888     }
 889
 890     fn contract_node(&self,
 891                      a_vid: RegionVid,
 892                      a_data: &mut VarData,
 893                      b_region: Region)
 894                      -> bool {
 895         debug!("contract_node({:?} == {:?}/{:?}, {:?})",
 896                a_vid, a_data.value, a_data.classification, b_region);
 897
 898         return match a_data.value {
 899             NoValue => {
 900                 assert_eq!(a_data.classification, Contracting);
 901                 a_data.value = Value(b_region);
 902                 true // changed
 903             }
 904
 905             ErrorValue => {
 906                 false // no change
 907             }
 908
 909             Value(a_region) => {
 910                 match a_data.classification {
 911                     Expanding => {
 912                         check_node(self, a_vid, a_data, a_region, b_region)
 913                     }
 914                     Contracting => {
 915                         adjust_node(self, a_vid, a_data, a_region, b_region)
 916                     }
 917                 }
 918             }
 919         };
 920
 921         fn check_node(this: &RegionVarBindings,
 922                       a_vid: RegionVid,
 923                       a_data: &mut VarData,
 924                       a_region: Region,
 925                       b_region: Region)
 926                    -> bool {
 927             if !this.is_subregion_of(a_region, b_region) {
 928                 debug!("Setting {:?} to ErrorValue: {:?} not subregion of {:?}",
 929                        a_vid, a_region, b_region);
 930                 a_data.value = ErrorValue;
 931             }
 932             false
 933         }
 934
 935         fn adjust_node(this: &RegionVarBindings,
 936                        a_vid: RegionVid,
 937                        a_data: &mut VarData,
 938                        a_region: Region,
 939                        b_region: Region)
 940                     -> bool {
 941             match this.glb_concrete_regions(a_region, b_region) {
 942                 Ok(glb) => {
 943                     if glb == a_region {
 944                         false
 945                     } else {
 946                         debug!("Contracting value of {:?} from {:?} to {:?}",
 947                                a_vid, a_region, glb);
 948                         a_data.value = Value(glb);
 949                         true
 950                     }
 951                 }
 952                 Err(_) => {
 953                     debug!("Setting {:?} to ErrorValue: no glb of {:?}, {:?}",
 954                            a_vid, a_region, b_region);
 955                     a_data.value = ErrorValue;
 956                     false
 957                 }
 958             }
 959         }
 960     }
 961
 962     fn collect_concrete_region_errors(
 963         &self,
 964         errors: &mut Vec<RegionResolutionError>)
 965     {
 966         for (constraint, _) in self.constraints.borrow().iter() {
 967             let (sub, sup) = match *constraint {
 968                 ConstrainVarSubVar(..) |
 969                 ConstrainRegSubVar(..) |
 970                 ConstrainVarSubReg(..) => {
 971                     continue;
 972                 }
 973                 ConstrainRegSubReg(sub, sup) => {
 974                     (sub, sup)
 975                 }
 976             };
 977
 978             if self.is_subregion_of(sub, sup) {
 979                 continue;
 980             }
 981
 982             debug!("ConcreteFailure: !(sub <= sup): sub={:?}, sup={:?}",
 983                    sub, sup);
 984             let origin = self.constraints.borrow().get_copy(constraint);
 985             errors.push(ConcreteFailure(origin, sub, sup));
 986         }
 987     }
 988
 989     fn extract_values_and_collect_conflicts(
 990         &self,
 991         var_data: &[VarData],
 992         errors: &mut Vec<RegionResolutionError>)
 993         -> Vec<VarValue> {
 994         debug!("extract_values_and_collect_conflicts()");
 995
 996         // This is the best way that I have found to suppress
 997         // duplicate and related errors. Basically we keep a set of
 998         // flags for every node. Whenever an error occurs, we will
 999         // walk some portion of the graph looking to find pairs of
1000         // conflicting regions to report to the user. As we walk, we
1001         // trip the flags from false to true, and if we find that
1002         // we've already reported an error involving any particular
1003         // node we just stop and don't report the current error.  The
1004         // idea is to report errors that derive from independent
1005         // regions of the graph, but not those that derive from
1006         // overlapping locations.
1007         let mut dup_vec = slice::from_elem(self.num_vars(), uint::MAX);
1008
1009         let mut opt_graph = None;
1010
1011         for idx in range(0u, self.num_vars()) {
1012             match var_data[idx].value {
1013                 Value(_) => {
1014                     /* Inference successful */
1015                 }
1016                 NoValue => {
1017                     /* Unconstrained inference: do not report an error
1018                        until the value of this variable is requested.
1019                        After all, sometimes we make region variables but never
1020                        really use their values. */
1021                 }
1022                 ErrorValue => {
1023                     /* Inference impossible, this value contains
1024                        inconsistent constraints.
1025
1026                        I think that in this case we should report an
1027                        error now---unlike the case above, we can't
1028                        wait to see whether the user needs the result
1029                        of this variable.  The reason is that the mere
1030                        existence of this variable implies that the
1031                        region graph is inconsistent, whether or not it
1032                        is used.
1033
1034                        For example, we may have created a region
1035                        variable that is the GLB of two other regions
1036                        which do not have a GLB.  Even if that variable
1037                        is not used, it implies that those two regions
1038                        *should* have a GLB.
1039
1040                        At least I think this is true. It may be that
1041                        the mere existence of a conflict in a region variable
1042                        that is not used is not a problem, so if this rule
1043                        starts to create problems we'll have to revisit
1044                        this portion of the code and think hard about it. =) */
1045
1046                     if opt_graph.is_none() {
1047                         opt_graph = Some(self.construct_graph());
1048                     }
1049                     let graph = opt_graph.get_ref();
1050
1051                     let node_vid = RegionVid { id: idx };
1052                     match var_data[idx].classification {
1053                         Expanding => {
1054                             self.collect_error_for_expanding_node(
1055                                 graph, var_data, dup_vec, node_vid, errors);
1056                         }
1057                         Contracting => {
1058                             self.collect_error_for_contracting_node(
1059                                 graph, var_data, dup_vec, node_vid, errors);
1060                         }
1061                     }
1062                 }
1063             }
1064         }
1065
1066         Vec::from_fn(self.num_vars(), |idx| var_data[idx].value)
1067     }
1068
1069     fn construct_graph(&self) -> RegionGraph {
1070         let num_vars = self.num_vars();
1071
1072         let constraints = self.constraints.borrow();
1073         let num_edges = constraints.len();
1074
1075         let mut graph = graph::Graph::with_capacity(num_vars + 1,
1076                                                     num_edges);
1077
1078         for _ in range(0u, num_vars) {
1079             graph.add_node(());
1080         }
1081         let dummy_idx = graph.add_node(());
1082
1083         for (constraint, _) in constraints.iter() {
1084             match *constraint {
1085                 ConstrainVarSubVar(a_id, b_id) => {
1086                     graph.add_edge(NodeIndex(a_id.to_uint()),
1087                                    NodeIndex(b_id.to_uint()),
1088                                    *constraint);
1089                 }
1090                 ConstrainRegSubVar(_, b_id) => {
1091                     graph.add_edge(dummy_idx,
1092                                    NodeIndex(b_id.to_uint()),
1093                                    *constraint);
1094                 }
1095                 ConstrainVarSubReg(a_id, _) => {
1096                     graph.add_edge(NodeIndex(a_id.to_uint()),
1097                                    dummy_idx,
1098                                    *constraint);
1099                 }
1100                 ConstrainRegSubReg(..) => {
1101                     // Relations between two concrete regions do not
1102                     // require an edge in the graph.
1103                 }
1104             }
1105         }
1106
1107         return graph;
1108     }
1109
1110     fn collect_error_for_expanding_node(
1111         &self,
1112         graph: &RegionGraph,
1113         var_data: &[VarData],
1114         dup_vec: &mut [uint],
1115         node_idx: RegionVid,
1116         errors: &mut Vec<RegionResolutionError>)
1117     {
1118         // Errors in expanding nodes result from a lower-bound that is
1119         // not contained by an upper-bound.
1120         let (lower_bounds, lower_dup) =
1121             self.collect_concrete_regions(graph, var_data, node_idx,
1122                                           graph::Incoming, dup_vec);
1123         let (upper_bounds, upper_dup) =
1124             self.collect_concrete_regions(graph, var_data, node_idx,
1125                                           graph::Outgoing, dup_vec);
1126
1127         if lower_dup || upper_dup {
1128             return;
1129         }
1130
1131         for lower_bound in lower_bounds.iter() {
1132             for upper_bound in upper_bounds.iter() {
1133                 if !self.is_subregion_of(lower_bound.region,
1134                                          upper_bound.region) {
1135                     errors.push(SubSupConflict(
1136                         *self.var_origins.borrow().get(node_idx.to_uint()),
1137                         lower_bound.origin,
1138                         lower_bound.region,
1139                         upper_bound.origin,
1140                         upper_bound.region));
1141                     return;
1142                 }
1143             }
1144         }
1145
1146         self.tcx.sess.span_bug(
1147             self.var_origins.borrow().get(node_idx.to_uint()).span(),
1148             format!("collect_error_for_expanding_node() could not find error \
1149                   for var {:?}, lower_bounds={}, upper_bounds={}",
1150                  node_idx,
1151                  lower_bounds.map(|x| x.region).repr(self.tcx),
1152                  upper_bounds.map(|x| x.region).repr(self.tcx)));
1153     }
1154
1155     fn collect_error_for_contracting_node(
1156         &self,
1157         graph: &RegionGraph,
1158         var_data: &[VarData],
1159         dup_vec: &mut [uint],
1160         node_idx: RegionVid,
1161         errors: &mut Vec<RegionResolutionError>)
1162     {
1163         // Errors in contracting nodes result from two upper-bounds
1164         // that have no intersection.
1165         let (upper_bounds, dup_found) =
1166             self.collect_concrete_regions(graph, var_data, node_idx,
1167                                           graph::Outgoing, dup_vec);
1168
1169         if dup_found {
1170             return;
1171         }
1172
1173         for upper_bound_1 in upper_bounds.iter() {
1174             for upper_bound_2 in upper_bounds.iter() {
1175                 match self.glb_concrete_regions(upper_bound_1.region,
1176                                                 upper_bound_2.region) {
1177                   Ok(_) => {}
1178                   Err(_) => {
1179                     errors.push(SupSupConflict(
1180                         *self.var_origins.borrow().get(node_idx.to_uint()),
1181                         upper_bound_1.origin,
1182                         upper_bound_1.region,
1183                         upper_bound_2.origin,
1184                         upper_bound_2.region));
1185                     return;
1186                   }
1187                 }
1188             }
1189         }
1190
1191         self.tcx.sess.span_bug(
1192             self.var_origins.borrow().get(node_idx.to_uint()).span(),
1193             format!("collect_error_for_contracting_node() could not find error \
1194                   for var {:?}, upper_bounds={}",
1195                  node_idx,
1196                  upper_bounds.map(|x| x.region).repr(self.tcx)));
1197     }
1198
1199     fn collect_concrete_regions(&self,
1200                                 graph: &RegionGraph,
1201                                 var_data: &[VarData],
1202                                 orig_node_idx: RegionVid,
1203                                 dir: Direction,
1204                                 dup_vec: &mut [uint])
1205                                 -> (Vec<RegionAndOrigin> , bool) {
1206         struct WalkState {
1207             set: HashSet<RegionVid>,
1208             stack: Vec<RegionVid> ,
1209             result: Vec<RegionAndOrigin> ,
1210             dup_found: bool
1211         }
1212         let mut state = WalkState {
1213             set: HashSet::new(),
1214             stack: vec!(orig_node_idx),
1215             result: Vec::new(),
1216             dup_found: false
1217         };
1218         state.set.insert(orig_node_idx);
1219
1220         // to start off the process, walk the source node in the
1221         // direction specified
1222         process_edges(self, &mut state, graph, orig_node_idx, dir);
1223
1224         while !state.stack.is_empty() {
1225             let node_idx = state.stack.pop().unwrap();
1226             let classification = var_data[node_idx.to_uint()].classification;
1227
1228             // check whether we've visited this node on some previous walk
1229             if dup_vec[node_idx.to_uint()] == uint::MAX {
1230                 dup_vec[node_idx.to_uint()] = orig_node_idx.to_uint();
1231             } else if dup_vec[node_idx.to_uint()] != orig_node_idx.to_uint() {
1232                 state.dup_found = true;
1233             }
1234
1235             debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1236                     classification={:?})",
1237                    orig_node_idx, node_idx, classification);
1238
1239             // figure out the direction from which this node takes its
1240             // values, and search for concrete regions etc in that direction
1241             let dir = match classification {
1242                 Expanding => graph::Incoming,
1243                 Contracting => graph::Outgoing,
1244             };
1245
1246             process_edges(self, &mut state, graph, node_idx, dir);
1247         }
1248
1249         let WalkState {result, dup_found, ..} = state;
1250         return (result, dup_found);
1251
1252         fn process_edges(this: &RegionVarBindings,
1253                          state: &mut WalkState,
1254                          graph: &RegionGraph,
1255                          source_vid: RegionVid,
1256                          dir: Direction) {
1257             debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1258
1259             let source_node_index = NodeIndex(source_vid.to_uint());
1260             graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
1261                 match edge.data {
1262                     ConstrainVarSubVar(from_vid, to_vid) => {
1263                         let opp_vid =
1264                             if from_vid == source_vid {to_vid} else {from_vid};
1265                         if state.set.insert(opp_vid) {
1266                             state.stack.push(opp_vid);
1267                         }
1268                     }
1269
1270                     ConstrainRegSubVar(region, _) |
1271                     ConstrainVarSubReg(_, region) => {
1272                         state.result.push(RegionAndOrigin {
1273                             region: region,
1274                             origin: this.constraints.borrow().get_copy(&edge.data)
1275                         });
1276                     }
1277
1278                     ConstrainRegSubReg(..) => {}
1279                 }
1280                 true
1281             });
1282         }
1283     }
1284
1285     fn iterate_until_fixed_point(&self,
1286                                  tag: &str,
1287                                  body: |constraint: &Constraint| -> bool) {
1288         let mut iteration = 0;
1289         let mut changed = true;
1290         while changed {
1291             changed = false;
1292             iteration += 1;
1293             debug!("---- {} Iteration \\#{}", tag, iteration);
1294             for (constraint, _) in self.constraints.borrow().iter() {
1295                 let edge_changed = body(constraint);
1296                 if edge_changed {
1297                     debug!("Updated due to constraint {}",
1298                            constraint.repr(self.tcx));
1299                     changed = true;
1300                 }
1301             }
1302         }
1303         debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1304     }
1305
1306 }
1307
1308 impl Repr for Constraint {
1309     fn repr(&self, tcx: &ty::ctxt) -> ~str {
1310         match *self {
1311             ConstrainVarSubVar(a, b) => format!("ConstrainVarSubVar({}, {})",
1312                                              a.repr(tcx), b.repr(tcx)),
1313             ConstrainRegSubVar(a, b) => format!("ConstrainRegSubVar({}, {})",
1314                                              a.repr(tcx), b.repr(tcx)),
1315             ConstrainVarSubReg(a, b) => format!("ConstrainVarSubReg({}, {})",
1316                                              a.repr(tcx), b.repr(tcx)),
1317             ConstrainRegSubReg(a, b) => format!("ConstrainRegSubReg({}, {})",
1318                                              a.repr(tcx), b.repr(tcx)),
1319         }
1320     }
1321 }