Auto merge of #27892 - nikomatsakis:issue-27583, r=pnkfelix

Issue #27583 was caused by the fact that `LUB('a,'b)` yielded `'static`, even if there existed a region `'tcx:'a+'b`. This PR replaces the old very hacky code for computing how free regions relate to one another with something rather more robust. This solves the issue for #27583, though I think that similar bizarro bugs can no doubt arise in other ways -- the root of the problem is that the region-inference code was written in an era when a LUB always existed, but that hasn't held for some time. To *truly* solve this problem, it needs to be generalized to cope with that reality. But let's leave that battle for another day.

r? @aturon 

9 files changed, 925 insertions, 116 deletions

diff --git a/src/librustc/middle/free_region.rs b/src/librustc/middle/free_region.rs
index 5af37e9530c..744ceb3701d 100644
--- a/src/librustc/middle/free_region.rs
+++ b/src/librustc/middle/free_region.rs
@@ -8,26 +8,26 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! This file defines
-
+//! This file handles the relationships between free regions --
+//! meaning lifetime parameters. Ordinarily, free regions are
+//! unrelated to one another, but they can be related vai implied or
+//! explicit bounds.  In that case, we track the bounds using the
+//! `TransitiveRelation` type and use that to decide when one free
+//! region outlives another and so forth.
+
+use middle::ty::{self, FreeRegion, Region};
 use middle::wf::ImpliedBound;
-use middle::ty::{self, FreeRegion};
-use util::common::can_reach;
-use util::nodemap::{FnvHashMap, FnvHashSet};
+use rustc_data_structures::transitive_relation::TransitiveRelation;
 
 #[derive(Clone)]
 pub struct FreeRegionMap {
-    /// `map` maps from a free region `a` to a list of
-    /// free regions `bs` such that `a <= b for all b in bs`
-    map: FnvHashMap<FreeRegion, Vec<FreeRegion>>,
-    /// regions that are required to outlive (and therefore be
-    /// equal to) 'static.
-    statics: FnvHashSet<FreeRegion>
+    // Stores the relation `a < b`, where `a` and `b` are regions.
+    relation: TransitiveRelation<Region>
 }
 
 impl FreeRegionMap {
     pub fn new() -> FreeRegionMap {
-        FreeRegionMap { map: FnvHashMap(), statics: FnvHashSet() }
+        FreeRegionMap { relation: TransitiveRelation::new() }
     }
 
     pub fn relate_free_regions_from_implied_bounds<'tcx>(&mut self,
@@ -84,14 +84,11 @@ impl FreeRegionMap {
     }
 
     fn relate_to_static(&mut self, sup: FreeRegion) {
-        self.statics.insert(sup);
+        self.relation.add(ty::ReStatic, ty::ReFree(sup));
     }
 
     fn relate_free_regions(&mut self, sub: FreeRegion, sup: FreeRegion) {
-       let mut sups = self.map.entry(sub).or_insert(Vec::new());
-        if !sups.contains(&sup) {
-            sups.push(sup);
-        }
+        self.relation.add(ty::ReFree(sub), ty::ReFree(sup))
     }
 
     /// Determines whether two free regions have a subregion relationship
@@ -99,7 +96,26 @@ impl FreeRegionMap {
     /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
     /// (that is, the user can give two different names to the same lifetime).
     pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
-        can_reach(&self.map, sub, sup) || self.is_static(&sup)
+        let result = sub == sup || {
+            let sub = ty::ReFree(sub);
+            let sup = ty::ReFree(sup);
+            self.relation.contains(&sub, &sup) || self.relation.contains(&ty::ReStatic, &sup)
+        };
+        debug!("sub_free_region(sub={:?}, sup={:?}) = {:?}", sub, sup, result);
+        result
+    }
+
+    pub fn lub_free_regions(&self, fr_a: FreeRegion, fr_b: FreeRegion) -> Region {
+        let r_a = ty::ReFree(fr_a);
+        let r_b = ty::ReFree(fr_b);
+        let result = if fr_a == fr_b { r_a } else {
+            match self.relation.postdom_upper_bound(&r_a, &r_b) {
+                None => ty::ReStatic,
+                Some(r) => *r,
+            }
+        };
+        debug!("lub_free_regions(fr_a={:?}, fr_b={:?}) = {:?}", fr_a, fr_b, result);
+        result
     }
 
     /// Determines whether one region is a subregion of another.  This is intended to run *after
@@ -109,10 +125,7 @@ impl FreeRegionMap {
                            sub_region: ty::Region,
                            super_region: ty::Region)
                            -> bool {
-        debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
-               sub_region, super_region);
-
-        sub_region == super_region || {
+        let result = sub_region == super_region || {
             match (sub_region, super_region) {
                 (ty::ReEmpty, _) |
                 (_, ty::ReStatic) =>
@@ -121,23 +134,47 @@ impl FreeRegionMap {
                 (ty::ReScope(sub_scope), ty::ReScope(super_scope)) =>
                     tcx.region_maps.is_subscope_of(sub_scope, super_scope),
 
-                (ty::ReScope(sub_scope), ty::ReFree(ref fr)) =>
-                    tcx.region_maps.is_subscope_of(sub_scope, fr.scope.to_code_extent()),
+                (ty::ReScope(sub_scope), ty::ReFree(fr)) =>
+                    tcx.region_maps.is_subscope_of(sub_scope, fr.scope.to_code_extent()) ||
+                    self.is_static(fr),
 
                 (ty::ReFree(sub_fr), ty::ReFree(super_fr)) =>
                     self.sub_free_region(sub_fr, super_fr),
 
-                (ty::ReStatic, ty::ReFree(ref sup_fr)) => self.is_static(sup_fr),
+                (ty::ReStatic, ty::ReFree(sup_fr)) =>
+                    self.is_static(sup_fr),
 
                 _ =>
                     false,
             }
-        }
+        };
+        debug!("is_subregion_of(sub_region={:?}, super_region={:?}) = {:?}",
+               sub_region, super_region, result);
+        result
     }
 
     /// Determines whether this free-region is required to be 'static
-    pub fn is_static(&self, super_region: &ty::FreeRegion) -> bool {
+    pub fn is_static(&self, super_region: ty::FreeRegion) -> bool {
         debug!("is_static(super_region={:?})", super_region);
-        self.statics.iter().any(|s| can_reach(&self.map, *s, *super_region))
+        self.relation.contains(&ty::ReStatic, &ty::ReFree(super_region))
     }
 }
+
+#[cfg(test)]
+fn free_region(index: u32) -> FreeRegion {
+    use middle::region::DestructionScopeData;
+    FreeRegion { scope: DestructionScopeData::new(0),
+                 bound_region: ty::BoundRegion::BrAnon(index) }
+}
+
+#[test]
+fn lub() {
+    // a very VERY basic test, but see the tests in
+    // TransitiveRelation, which are much more thorough.
+    let frs: Vec<_> = (0..3).map(|i| free_region(i)).collect();
+    let mut map = FreeRegionMap::new();
+    map.relate_free_regions(frs[0], frs[2]);
+    map.relate_free_regions(frs[1], frs[2]);
+    assert_eq!(map.lub_free_regions(frs[0], frs[1]), ty::ReFree(frs[2]));
+}
+
diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index e8f8dbfbb0e..e04f2955ddc 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -812,8 +812,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             ReScope(self.tcx.region_maps.nearest_common_ancestor(a_id, b_id))
           }
 
-          (ReFree(ref a_fr), ReFree(ref b_fr)) => {
-             self.lub_free_regions(free_regions, a_fr, b_fr)
+          (ReFree(a_fr), ReFree(b_fr)) => {
+            free_regions.lub_free_regions(a_fr, b_fr)
           }
 
           // For these types, we cannot define any additional
@@ -825,35 +825,6 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         }
     }
 
-    /// Computes a region that encloses both free region arguments. Guarantee that if the same two
-    /// regions are given as argument, in any order, a consistent result is returned.
-    fn lub_free_regions(&self,
-                        free_regions: &FreeRegionMap,
-                        a: &FreeRegion,
-                        b: &FreeRegion)
-                        -> ty::Region
-    {
-        return match a.cmp(b) {
-            Less => helper(self, free_regions, a, b),
-            Greater => helper(self, free_regions, b, a),
-            Equal => ty::ReFree(*a)
-        };
-
-        fn helper(_this: &RegionVarBindings,
-                  free_regions: &FreeRegionMap,
-                  a: &FreeRegion,
-                  b: &FreeRegion) -> ty::Region
-        {
-            if free_regions.sub_free_region(*a, *b) {
-                ty::ReFree(*b)
-            } else if free_regions.sub_free_region(*b, *a) {
-                ty::ReFree(*a)
-            } else {
-                ty::ReStatic
-            }
-        }
-    }
-
     fn glb_concrete_regions(&self,
                             free_regions: &FreeRegionMap,
                             a: Region,
@@ -892,8 +863,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                             b));
             }
 
-            (ReFree(ref fr), ReScope(s_id)) |
-            (ReScope(s_id), ReFree(ref fr)) => {
+            (ReFree(fr), ReScope(s_id)) |
+            (ReScope(s_id), ReFree(fr)) => {
                 let s = ReScope(s_id);
                 // Free region is something "at least as big as
                 // `fr.scope_id`."  If we find that the scope `fr.scope_id` is bigger
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index 2314368177c..1ad5ae9917d 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -203,49 +203,6 @@ pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) -
     return v.flag;
 }
 
-/// K: Eq + Hash<S>, V, S, H: Hasher<S>
-///
-/// Determines whether there exists a path from `source` to `destination`.  The
-/// graph is defined by the `edges_map`, which maps from a node `S` to a list of
-/// its adjacent nodes `T`.
-///
-/// Efficiency note: This is implemented in an inefficient way because it is
-/// typically invoked on very small graphs. If the graphs become larger, a more
-/// efficient graph representation and algorithm would probably be advised.
-pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
-                       destination: T) -> bool
-    where S: HashState, T: Hash + Eq + Clone,
-{
-    if source == destination {
-        return true;
-    }
-
-    // Do a little breadth-first-search here.  The `queue` list
-    // doubles as a way to detect if we've seen a particular FR
-    // before.  Note that we expect this graph to be an *extremely
-    // shallow* tree.
-    let mut queue = vec!(source);
-    let mut i = 0;
-    while i < queue.len() {
-        match edges_map.get(&queue[i]) {
-            Some(edges) => {
-                for target in edges {
-                    if *target == destination {
-                        return true;
-                    }
-
-                    if !queue.iter().any(|x| x == target) {
-                        queue.push((*target).clone());
-                    }
-                }
-            }
-            None => {}
-        }
-        i += 1;
-    }
-    return false;
-}
-
 /// Memoizes a one-argument closure using the given RefCell containing
 /// a type implementing MutableMap to serve as a cache.
 ///
diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index f2f4a69d882..f26307fd8c5 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -15,26 +15,200 @@ pub struct BitVector {
 
 impl BitVector {
     pub fn new(num_bits: usize) -> BitVector {
-        let num_words = (num_bits + 63) / 64;
+        let num_words = u64s(num_bits);
         BitVector { data: vec![0; num_words] }
     }
 
-    fn word_mask(&self, bit: usize) -> (usize, u64) {
-        let word = bit / 64;
-        let mask = 1 << (bit % 64);
-        (word, mask)
-    }
-
     pub fn contains(&self, bit: usize) -> bool {
-        let (word, mask) = self.word_mask(bit);
+        let (word, mask) = word_mask(bit);
         (self.data[word] & mask) != 0
     }
 
     pub fn insert(&mut self, bit: usize) -> bool {
-        let (word, mask) = self.word_mask(bit);
+        let (word, mask) = word_mask(bit);
         let data = &mut self.data[word];
         let value = *data;
         *data = value | mask;
         (value | mask) != value
     }
+
+    pub fn insert_all(&mut self, all: &BitVector) -> bool {
+        assert!(self.data.len() == all.data.len());
+        let mut changed = false;
+        for (i, j) in self.data.iter_mut().zip(&all.data) {
+            let value = *i;
+            *i = value | *j;
+            if value != *i { changed = true; }
+        }
+        changed
+    }
+
+    pub fn grow(&mut self, num_bits: usize) {
+        let num_words = u64s(num_bits);
+        let extra_words = self.data.len() - num_words;
+        self.data.extend((0..extra_words).map(|_| 0));
+    }
+}
+
+/// A "bit matrix" is basically a square matrix of booleans
+/// represented as one gigantic bitvector. In other words, it is as if
+/// you have N bitvectors, each of length N. Note that `elements` here is `N`/
+#[derive(Clone)]
+pub struct BitMatrix {
+    elements: usize,
+    vector: Vec<u64>,
+}
+
+impl BitMatrix {
+    // Create a new `elements x elements` matrix, initially empty.
+    pub fn new(elements: usize) -> BitMatrix {
+        // For every element, we need one bit for every other
+        // element. Round up to an even number of u64s.
+        let u64s_per_elem = u64s(elements);
+        BitMatrix {
+            elements: elements,
+            vector: vec![0; elements * u64s_per_elem]
+        }
+    }
+
+    /// The range of bits for a given element.
+    fn range(&self, element: usize) -> (usize, usize) {
+        let u64s_per_elem = u64s(self.elements);
+        let start = element * u64s_per_elem;
+        (start, start + u64s_per_elem)
+    }
+
+    pub fn add(&mut self, source: usize, target: usize) -> bool {
+        let (start, _) = self.range(source);
+        let (word, mask) = word_mask(target);
+        let mut vector = &mut self.vector[..];
+        let v1 = vector[start+word];
+        let v2 = v1 | mask;
+        vector[start+word] = v2;
+        v1 != v2
+    }
+
+    /// Do the bits from `source` contain `target`?
+    ///
+    /// Put another way, if the matrix represents (transitive)
+    /// reachability, can `source` reach `target`?
+    pub fn contains(&self, source: usize, target: usize) -> bool {
+        let (start, _) = self.range(source);
+        let (word, mask) = word_mask(target);
+        (self.vector[start+word] & mask) != 0
+    }
+
+    /// Returns those indices that are reachable from both `a` and
+    /// `b`. This is an O(n) operation where `n` is the number of
+    /// elements (somewhat independent from the actual size of the
+    /// intersection, in particular).
+    pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
+        let (a_start, a_end) = self.range(a);
+        let (b_start, b_end) = self.range(b);
+        let mut result = Vec::with_capacity(self.elements);
+        for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
+            let mut v = self.vector[i] & self.vector[j];
+            for bit in 0..64 {
+                if v == 0 { break; }
+                if v & 0x1 != 0 { result.push(base*64 + bit); }
+                v >>= 1;
+            }
+        }
+        result
+    }
+
+    /// Add the bits from `read` to the bits from `write`,
+    /// return true if anything changed.
+    ///
+    /// This is used when computing transitive reachability because if
+    /// you have an edge `write -> read`, because in that case
+    /// `write` can reach everything that `read` can (and
+    /// potentially more).
+    pub fn merge(&mut self, read: usize, write: usize) -> bool {
+        let (read_start, read_end) = self.range(read);
+        let (write_start, write_end) = self.range(write);
+        let vector = &mut self.vector[..];
+        let mut changed = false;
+        for (read_index, write_index) in
+            (read_start..read_end).zip(write_start..write_end)
+        {
+            let v1 = vector[write_index];
+            let v2 = v1 | vector[read_index];
+            vector[write_index] = v2;
+            changed = changed | (v1 != v2);
+        }
+        changed
+    }
+}
+
+fn u64s(elements: usize) -> usize {
+    (elements + 63) / 64
+}
+
+fn word_mask(index: usize) -> (usize, u64) {
+    let word = index / 64;
+    let mask = 1 << (index % 64);
+    (word, mask)
+}
+
+#[test]
+fn union_two_vecs() {
+    let mut vec1 = BitVector::new(65);
+    let mut vec2 = BitVector::new(65);
+    assert!(vec1.insert(3));
+    assert!(!vec1.insert(3));
+    assert!(vec2.insert(5));
+    assert!(vec2.insert(64));
+    assert!(vec1.insert_all(&vec2));
+    assert!(!vec1.insert_all(&vec2));
+    assert!(vec1.contains(3));
+    assert!(!vec1.contains(4));
+    assert!(vec1.contains(5));
+    assert!(!vec1.contains(63));
+    assert!(vec1.contains(64));
+}
+
+#[test]
+fn grow() {
+    let mut vec1 = BitVector::new(65);
+    assert!(vec1.insert(3));
+    assert!(!vec1.insert(3));
+    assert!(vec1.insert(5));
+    assert!(vec1.insert(64));
+    vec1.grow(128);
+    assert!(vec1.contains(3));
+    assert!(vec1.contains(5));
+    assert!(vec1.contains(64));
+    assert!(!vec1.contains(126));
+}
+
+#[test]
+fn matrix_intersection() {
+    let mut vec1 = BitMatrix::new(200);
+
+    // (*) Elements reachable from both 2 and 65.
+
+    vec1.add(2, 3);
+    vec1.add(2, 6);
+    vec1.add(2, 10); // (*)
+    vec1.add(2, 64); // (*)
+    vec1.add(2, 65);
+    vec1.add(2, 130);
+    vec1.add(2, 160); // (*)
+
+    vec1.add(64, 133);
+
+    vec1.add(65, 2);
+    vec1.add(65, 8);
+    vec1.add(65, 10); // (*)
+    vec1.add(65, 64); // (*)
+    vec1.add(65, 68);
+    vec1.add(65, 133);
+    vec1.add(65, 160); // (*)
+
+    let intersection = vec1.intersection(2, 64);
+    assert!(intersection.is_empty());
+
+    let intersection = vec1.intersection(2, 65);
+    assert_eq!(intersection, &[10, 64, 160]);
 }
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index eb9ed83b2b0..78edae76253 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -33,10 +33,11 @@
 #[macro_use] extern crate log;
 extern crate serialize as rustc_serialize; // used by deriving
 
-pub mod snapshot_vec;
-pub mod graph;
 pub mod bitvec;
+pub mod graph;
 pub mod ivar;
+pub mod snapshot_vec;
+pub mod transitive_relation;
 pub mod unify;
 
 // See comments in src/librustc/lib.rs
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
new file mode 100644
index 00000000000..728137f4ae9
--- /dev/null
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -0,0 +1,589 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use bitvec::BitMatrix;
+use std::cell::RefCell;
+use std::fmt::Debug;
+use std::mem;
+
+#[derive(Clone)]
+pub struct TransitiveRelation<T:Debug+PartialEq> {
+    // List of elements. This is used to map from a T to a usize.  We
+    // expect domain to be small so just use a linear list versus a
+    // hashmap or something.
+    elements: Vec<T>,
+
+    // List of base edges in the graph. Require to compute transitive
+    // closure.
+    edges: Vec<Edge>,
+
+    // This is a cached transitive closure derived from the edges.
+    // Currently, we build it lazilly and just throw out any existing
+    // copy whenever a new edge is added. (The RefCell is to permit
+    // the lazy computation.) This is kind of silly, except for the
+    // fact its size is tied to `self.elements.len()`, so I wanted to
+    // wait before building it up to avoid reallocating as new edges
+    // are added with new elements. Perhaps better would be to ask the
+    // user for a batch of edges to minimize this effect, but I
+    // already wrote the code this way. :P -nmatsakis
+    closure: RefCell<Option<BitMatrix>>
+}
+
+#[derive(Clone, PartialEq, PartialOrd)]
+struct Index(usize);
+
+#[derive(Clone, PartialEq)]
+struct Edge {
+    source: Index,
+    target: Index,
+}
+
+impl<T:Debug+PartialEq> TransitiveRelation<T> {
+    pub fn new() -> TransitiveRelation<T> {
+        TransitiveRelation { elements: vec![],
+                             edges: vec![],
+                             closure: RefCell::new(None) }
+    }
+
+    fn index(&self, a: &T) -> Option<Index> {
+        self.elements.iter().position(|e| *e == *a).map(Index)
+    }
+
+    fn add_index(&mut self, a: T) -> Index {
+        match self.index(&a) {
+            Some(i) => i,
+            None => {
+                self.elements.push(a);
+
+                // if we changed the dimensions, clear the cache
+                *self.closure.borrow_mut() = None;
+
+                Index(self.elements.len() - 1)
+            }
+        }
+    }
+
+    /// Indicate that `a < b` (where `<` is this relation)
+    pub fn add(&mut self, a: T, b: T) {
+        let a = self.add_index(a);
+        let b = self.add_index(b);
+        let edge = Edge { source: a, target: b };
+        if !self.edges.contains(&edge) {
+            self.edges.push(edge);
+
+            // added an edge, clear the cache
+            *self.closure.borrow_mut() = None;
+        }
+    }
+
+    /// Check whether `a < target` (transitively)
+    pub fn contains(&self, a: &T, b: &T) -> bool {
+        match (self.index(a), self.index(b)) {
+            (Some(a), Some(b)) =>
+                self.with_closure(|closure| closure.contains(a.0, b.0)),
+            (None, _) | (_, None) =>
+                false,
+        }
+    }
+
+    /// Picks what I am referring to as the "postdominating"
+    /// upper-bound for `a` and `b`. This is usually the least upper
+    /// bound, but in cases where there is no single least upper
+    /// bound, it is the "mutual immediate postdominator", if you
+    /// imagine a graph where `a < b` means `a -> b`.
+    ///
+    /// This function is needed because region inference currently
+    /// requires that we produce a single "UB", and there is no best
+    /// choice for the LUB. Rather than pick arbitrarily, I pick a
+    /// less good, but predictable choice. This should help ensure
+    /// that region inference yields predictable results (though it
+    /// itself is not fully sufficient).
+    ///
+    /// Examples are probably clearer than any prose I could write
+    /// (there are corresponding tests below, btw). In each case,
+    /// the query is `postdom_upper_bound(a, b)`:
+    ///
+    /// ```
+    /// // returns Some(x), which is also LUB
+    /// a -> a1 -> x
+    ///            ^
+    ///            |
+    /// b -> b1 ---+
+    ///
+    /// // returns Some(x), which is not LUB (there is none)
+    /// // diagonal edges run left-to-right
+    /// a -> a1 -> x
+    ///   \/       ^
+    ///   /\       |
+    /// b -> b1 ---+
+    ///
+    /// // returns None
+    /// a -> a1
+    /// b -> b1
+    /// ```
+    pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
+        let mut mubs = self.minimal_upper_bounds(a, b);
+        loop {
+            match mubs.len() {
+                0 => return None,
+                1 => return Some(mubs[0]),
+                _ => {
+                    let m = mubs.pop().unwrap();
+                    let n = mubs.pop().unwrap();
+                    mubs.extend(self.minimal_upper_bounds(n, m));
+                }
+            }
+        }
+    }
+
+    /// Returns the set of bounds `X` such that:
+    ///
+    /// - `a < X` and `b < X`
+    /// - there is no `Y != X` such that `a < Y` and `Y < X`
+    ///   - except for the case where `X < a` (i.e., a strongly connected
+    ///     component in the graph). In that case, the smallest
+    ///     representative of the SCC is returned (as determined by the
+    ///     internal indices).
+    ///
+    /// Note that this set can, in principle, have any size.
+    pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
+        let (mut a, mut b) = match (self.index(a), self.index(b)) {
+            (Some(a), Some(b)) => (a, b),
+            (None, _) | (_, None) => { return vec![]; }
+        };
+
+        // in some cases, there are some arbitrary choices to be made;
+        // it doesn't really matter what we pick, as long as we pick
+        // the same thing consistently when queried, so ensure that
+        // (a, b) are in a consistent relative order
+        if a > b {
+            mem::swap(&mut a, &mut b);
+        }
+
+        let lub_indices = self.with_closure(|closure| {
+            // Easy case is when either a < b or b < a:
+            if closure.contains(a.0, b.0) {
+                return vec![b.0];
+            }
+            if closure.contains(b.0, a.0) {
+                return vec![a.0];
+            }
+
+            // Otherwise, the tricky part is that there may be some c
+            // where a < c and b < c. In fact, there may be many such
+            // values. So here is what we do:
+            //
+            // 1. Find the vector `[X | a < X && b < X]` of all values
+            //    `X` where `a < X` and `b < X`.  In terms of the
+            //    graph, this means all values reachable from both `a`
+            //    and `b`. Note that this vector is also a set, but we
+            //    use the term vector because the order matters
+            //    to the steps below.
+            //    - This vector contains upper bounds, but they are
+            //      not minimal upper bounds. So you may have e.g.
+            //      `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
+            //      `z < x` and `z < y`:
+            //
+            //           z --+---> x ----+----> tcx
+            //               |           |
+            //               |           |
+            //               +---> y ----+
+            //
+            //      In this case, we really want to return just `[z]`.
+            //      The following steps below achieve this by gradually
+            //      reducing the list.
+            // 2. Pare down the vector using `pare_down`. This will
+            //    remove elements from the vector that can be reached
+            //    by an earlier element.
+            //    - In the example above, this would convert `[x, y,
+            //      tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
+            //      still in the vector; this is because while `z < x`
+            //      (and `z < y`) holds, `z` comes after them in the
+            //      vector.
+            // 3. Reverse the vector and repeat the pare down process.
+            //    - In the example above, we would reverse to
+            //      `[z, y, x]` and then pare down to `[z]`.
+            // 4. Reverse once more just so that we yield a vector in
+            //    increasing order of index. Not necessary, but why not.
+            //
+            // I believe this algorithm yields a minimal set. The
+            // argument is that, after step 2, we know that no element
+            // can reach its successors (in the vector, not the graph).
+            // After step 3, we know that no element can reach any of
+            // its predecesssors (because of step 2) nor successors
+            // (because we just called `pare_down`)
+
+            let mut candidates = closure.intersection(a.0, b.0); // (1)
+            pare_down(&mut candidates, closure); // (2)
+            candidates.reverse(); // (3a)
+            pare_down(&mut candidates, closure); // (3b)
+            candidates
+        });
+
+        lub_indices.into_iter()
+                   .rev() // (4)
+                   .map(|i| &self.elements[i])
+                   .collect()
+    }
+
+    fn with_closure<OP,R>(&self, op: OP) -> R
+        where OP: FnOnce(&BitMatrix) -> R
+    {
+        let mut closure_cell = self.closure.borrow_mut();
+        let mut closure = closure_cell.take();
+        if closure.is_none() {
+            closure = Some(self.compute_closure());
+        }
+        let result = op(closure.as_ref().unwrap());
+        *closure_cell = closure;
+        result
+    }
+
+    fn compute_closure(&self) -> BitMatrix {
+        let mut matrix = BitMatrix::new(self.elements.len());
+        let mut changed = true;
+        while changed {
+            changed = false;
+            for edge in self.edges.iter() {
+                // add an edge from S -> T
+                changed |= matrix.add(edge.source.0, edge.target.0);
+
+                // add all outgoing edges from T into S
+                changed |= matrix.merge(edge.target.0, edge.source.0);
+            }
+        }
+        matrix
+    }
+}
+
+/// Pare down is used as a step in the LUB computation. It edits the
+/// candidates array in place by removing any element j for which
+/// there exists an earlier element i<j such that i -> j. That is,
+/// after you run `pare_down`, you know that for all elements that
+/// remain in candidates, they cannot reach any of the elements that
+/// come after them.
+///
+/// Examples follow. Assume that a -> b -> c and x -> y -> z.
+///
+/// - Input: `[a, b, x]`. Output: `[a, x]`.
+/// - Input: `[b, a, x]`. Output: `[b, a, x]`.
+/// - Input: `[a, x, b, y]`. Output: `[a, x]`.
+fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
+    let mut i = 0;
+    while i < candidates.len() {
+        let candidate_i = candidates[i];
+        i += 1;
+
+        let mut j = i;
+        let mut dead = 0;
+        while j < candidates.len() {
+            let candidate_j = candidates[j];
+            if closure.contains(candidate_i, candidate_j) {
+                // If `i` can reach `j`, then we can remove `j`. So just
+                // mark it as dead and move on; subsequent indices will be
+                // shifted into its place.
+                dead += 1;
+            } else {
+                candidates[j - dead] = candidate_j;
+            }
+            j += 1;
+        }
+        candidates.truncate(j - dead);
+    }
+}
+
+#[test]
+fn test_one_step() {
+    let mut relation = TransitiveRelation::new();
+    relation.add("a", "b");
+    relation.add("a", "c");
+    assert!(relation.contains(&"a", &"c"));
+    assert!(relation.contains(&"a", &"b"));
+    assert!(!relation.contains(&"b", &"a"));
+    assert!(!relation.contains(&"a", &"d"));
+}
+
+#[test]
+fn test_many_steps() {
+    let mut relation = TransitiveRelation::new();
+    relation.add("a", "b");
+    relation.add("a", "c");
+    relation.add("a", "f");
+
+    relation.add("b", "c");
+    relation.add("b", "d");
+    relation.add("b", "e");
+
+    relation.add("e", "g");
+
+    assert!(relation.contains(&"a", &"b"));
+    assert!(relation.contains(&"a", &"c"));
+    assert!(relation.contains(&"a", &"d"));
+    assert!(relation.contains(&"a", &"e"));
+    assert!(relation.contains(&"a", &"f"));
+    assert!(relation.contains(&"a", &"g"));
+
+    assert!(relation.contains(&"b", &"g"));
+
+    assert!(!relation.contains(&"a", &"x"));
+    assert!(!relation.contains(&"b", &"f"));
+}
+
+#[test]
+fn mubs_triange() {
+    let mut relation = TransitiveRelation::new();
+    relation.add("a", "tcx");
+    relation.add("b", "tcx");
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
+}
+
+#[test]
+fn mubs_best_choice1() {
+    // 0 -> 1 <- 3
+    // |    ^    |
+    // |    |    |
+    // +--> 2 <--+
+    //
+    // mubs(0,3) = [1]
+
+    // This tests a particular state in the algorithm, in which we
+    // need the second pare down call to get the right result (after
+    // intersection, we have [1, 2], but 2 -> 1).
+
+    let mut relation = TransitiveRelation::new();
+    relation.add("0", "1");
+    relation.add("0", "2");
+
+    relation.add("2", "1");
+
+    relation.add("3", "1");
+    relation.add("3", "2");
+
+    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
+}
+
+#[test]
+fn mubs_best_choice2() {
+    // 0 -> 1 <- 3
+    // |    |    |
+    // |    v    |
+    // +--> 2 <--+
+    //
+    // mubs(0,3) = [2]
+
+    // Like the precedecing test, but in this case intersection is [2,
+    // 1], and hence we rely on the first pare down call.
+
+    let mut relation = TransitiveRelation::new();
+    relation.add("0", "1");
+    relation.add("0", "2");
+
+    relation.add("1", "2");
+
+    relation.add("3", "1");
+    relation.add("3", "2");
+
+    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
+}
+
+#[test]
+fn mubs_no_best_choice() {
+    // in this case, the intersection yields [1, 2], and the "pare
+    // down" calls find nothing to remove.
+    let mut relation = TransitiveRelation::new();
+    relation.add("0", "1");
+    relation.add("0", "2");
+
+    relation.add("3", "1");
+    relation.add("3", "2");
+
+    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
+}
+
+#[test]
+fn mubs_best_choice_scc() {
+    let mut relation = TransitiveRelation::new();
+    relation.add("0", "1");
+    relation.add("0", "2");
+
+    relation.add("1", "2");
+    relation.add("2", "1");
+
+    relation.add("3", "1");
+    relation.add("3", "2");
+
+    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
+}
+
+#[test]
+fn pdub_crisscross() {
+    // diagonal edges run left-to-right
+    // a -> a1 -> x
+    //   \/       ^
+    //   /\       |
+    // b -> b1 ---+
+
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "a1");
+    relation.add("a",  "b1");
+    relation.add("b",  "a1");
+    relation.add("b",  "b1");
+    relation.add("a1", "x");
+    relation.add("b1", "x");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
+    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
+}
+
+#[test]
+fn pdub_crisscross_more() {
+    // diagonal edges run left-to-right
+    // a -> a1 -> a2 -> a3 -> x
+    //   \/    \/             ^
+    //   /\    /\             |
+    // b -> b1 -> b2 ---------+
+
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "a1");
+    relation.add("a",  "b1");
+    relation.add("b",  "a1");
+    relation.add("b",  "b1");
+
+    relation.add("a1",  "a2");
+    relation.add("a1",  "b2");
+    relation.add("b1",  "a2");
+    relation.add("b1",  "b2");
+
+    relation.add("a2", "a3");
+
+    relation.add("a3", "x");
+    relation.add("b2", "x");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
+    assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), vec![&"a2", &"b2"]);
+    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
+}
+
+#[test]
+fn pdub_lub() {
+    // a -> a1 -> x
+    //            ^
+    //            |
+    // b -> b1 ---+
+
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "a1");
+    relation.add("b",  "b1");
+    relation.add("a1", "x");
+    relation.add("b1", "x");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
+    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
+}
+
+#[test]
+fn mubs_intermediate_node_on_one_side_only() {
+    // a -> c -> d
+    //           ^
+    //           |
+    //           b
+
+    // "digraph { a -> c -> d; b -> d; }",
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("b",  "d");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
+}
+
+#[test]
+fn mubs_scc_1() {
+    // +-------------+
+    // |    +----+   |
+    // |    v    |   |
+    // a -> c -> d <-+
+    //           ^
+    //           |
+    //           b
+
+    // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("d",  "c");
+    relation.add("a",  "d");
+    relation.add("b",  "d");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
+}
+
+#[test]
+fn mubs_scc_2() {
+    //      +----+
+    //      v    |
+    // a -> c -> d
+    //      ^    ^
+    //      |    |
+    //      +--- b
+
+    // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("d",  "c");
+    relation.add("b",  "d");
+    relation.add("b",  "c");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
+}
+
+#[test]
+fn mubs_scc_3() {
+    //      +---------+
+    //      v         |
+    // a -> c -> d -> e
+    //           ^    ^
+    //           |    |
+    //           b ---+
+
+    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("d",  "e");
+    relation.add("e",  "c");
+    relation.add("b",  "d");
+    relation.add("b",  "e");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
+}
+
+#[test]
+fn mubs_scc_4() {
+    //      +---------+
+    //      v         |
+    // a -> c -> d -> e
+    // |         ^    ^
+    // +---------+    |
+    //                |
+    //           b ---+
+
+    // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
+    let mut relation = TransitiveRelation::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("d",  "e");
+    relation.add("e",  "c");
+    relation.add("a",  "d");
+    relation.add("b",  "e");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
+}
diff --git a/src/librustc_data_structures/unify/tests.rs b/src/librustc_data_structures/unify/tests.rs
index dbe3cfc7a48..089e629a569 100644
--- a/src/librustc_data_structures/unify/tests.rs
+++ b/src/librustc_data_structures/unify/tests.rs
@@ -12,7 +12,6 @@
 
 extern crate test;
 use self::test::Bencher;
-use std::collections::HashSet;
 use unify::{UnifyKey, UnificationTable};
 
 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
diff --git a/src/test/run-pass/issue-27583.rs b/src/test/run-pass/issue-27583.rs
new file mode 100644
index 00000000000..df1b2c2cf43
--- /dev/null
+++ b/src/test/run-pass/issue-27583.rs
@@ -0,0 +1,56 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for issue #27583. Unclear how useful this will be
+// going forward, since the issue in question was EXTREMELY sensitive
+// to compiler internals (like the precise numbering of nodes), but
+// what the hey.
+
+#![allow(warnings)]
+
+use std::cell::Cell;
+use std::marker::PhantomData;
+
+pub trait Delegate<'tcx> { }
+
+pub struct InferCtxt<'a, 'tcx: 'a> {
+    x: PhantomData<&'a Cell<&'tcx ()>>
+}
+
+pub struct MemCategorizationContext<'t, 'a: 't, 'tcx : 'a> {
+    x: &'t InferCtxt<'a, 'tcx>,
+}
+
+pub struct ExprUseVisitor<'d, 't, 'a: 't, 'tcx:'a+'d> {
+    typer: &'t InferCtxt<'a, 'tcx>,
+    mc: MemCategorizationContext<'t, 'a, 'tcx>,
+    delegate: &'d mut (Delegate<'tcx>+'d),
+}
+
+impl<'d,'t,'a,'tcx> ExprUseVisitor<'d,'t,'a,'tcx> {
+    pub fn new(delegate: &'d mut Delegate<'tcx>,
+               typer: &'t InferCtxt<'a, 'tcx>)
+               -> ExprUseVisitor<'d,'t,'a,'tcx>
+    {
+        ExprUseVisitor {
+            typer: typer,
+            mc: MemCategorizationContext::new(typer),
+            delegate: delegate,
+        }
+    }
+}
+
+impl<'t, 'a,'tcx> MemCategorizationContext<'t, 'a, 'tcx> {
+    pub fn new(typer: &'t InferCtxt<'a, 'tcx>) -> MemCategorizationContext<'t, 'a, 'tcx> {
+        MemCategorizationContext { x: typer }
+    }
+}
+
+fn main() { }
diff --git a/src/test/run-pass/regions-free-region-outlives-static-outlives-free-region.rs b/src/test/run-pass/regions-free-region-outlives-static-outlives-free-region.rs
new file mode 100644
index 00000000000..09c8d1f23a2
--- /dev/null
+++ b/src/test/run-pass/regions-free-region-outlives-static-outlives-free-region.rs
@@ -0,0 +1,25 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we recognize that if you have
+//
+//     'a : 'static
+//
+// then
+//
+//     'a : 'b
+
+fn test<'a,'b>(x: &'a i32) -> &'b i32
+    where 'a: 'static
+{
+    x
+}
+
+fn main() { }