src/librustc/middle/typeck/infer/region_inference/mod.rs

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