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