resolved merge conflicts

5 files changed, 70 insertions, 31 deletions

diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index 848e5a076bb..078bb801751 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -255,7 +255,7 @@ impl<'a, A: Array> Drop for Drain<'a, A> {
 
         if self.tail_len > 0 {
             unsafe {
-                let source_array_vec = &mut *self.array_vec.as_mut_ptr();
+                let source_array_vec = self.array_vec.as_mut();
                 // memmove back untouched tail, update to new length
                 let start = source_array_vec.len();
                 let tail = self.tail_start;
diff --git a/src/librustc_data_structures/flock.rs b/src/librustc_data_structures/flock.rs
index 32f0fd41997..ff1ebb11b72 100644
--- a/src/librustc_data_structures/flock.rs
+++ b/src/librustc_data_structures/flock.rs
@@ -247,11 +247,11 @@ mod imp {
     use std::os::windows::raw::HANDLE;
     use std::path::Path;
     use std::fs::{File, OpenOptions};
-    use std::os::raw::{c_ulong, c_ulonglong, c_int};
+    use std::os::raw::{c_ulong, c_int};
 
     type DWORD = c_ulong;
     type BOOL = c_int;
-    type ULONG_PTR = c_ulonglong;
+    type ULONG_PTR = usize;
 
     type LPOVERLAPPED = *mut OVERLAPPED;
     const LOCKFILE_EXCLUSIVE_LOCK: DWORD = 0x00000002;
diff --git a/src/librustc_data_structures/obligation_forest/node_index.rs b/src/librustc_data_structures/obligation_forest/node_index.rs
index 1063bb3611e..023c56ca59b 100644
--- a/src/librustc_data_structures/obligation_forest/node_index.rs
+++ b/src/librustc_data_structures/obligation_forest/node_index.rs
@@ -23,6 +23,6 @@ impl NodeIndex {
     }
 
     pub fn get(self) -> usize {
-        (*self.index - 1) as usize
+        (self.index.get() - 1) as usize
     }
 }
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 95f063976d4..635b95d861d 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -283,6 +283,16 @@ impl<CTX> HashStable<CTX> for str {
     }
 }
 
+
+impl<CTX> HashStable<CTX> for String {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (&self[..]).hash_stable(hcx, hasher);
+    }
+}
+
 impl<CTX> HashStable<CTX> for bool {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index b0fca5c0ff3..46463944043 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -9,21 +9,23 @@
 // except according to those terms.
 
 use bitvec::BitMatrix;
-use stable_hasher::{HashStable, StableHasher, StableHasherResult};
+use fx::FxHashMap;
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
+use stable_hasher::{HashStable, StableHasher, StableHasherResult};
 use std::cell::RefCell;
 use std::fmt::Debug;
+use std::hash::Hash;
 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.
+pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash + Clone> {
+    // List of elements. This is used to map from a T to a usize.
     elements: Vec<T>,
 
+    // Maps each element to an index.
+    map: FxHashMap<T, Index>,
+
     // List of base edges in the graph. Require to compute transitive
     // closure.
     edges: Vec<Edge>,
@@ -40,19 +42,20 @@ pub struct TransitiveRelation<T: Debug + PartialEq> {
     closure: RefCell<Option<BitMatrix>>,
 }
 
-#[derive(Clone, PartialEq, PartialOrd, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 struct Index(usize);
 
-#[derive(Clone, PartialEq, RustcEncodable, RustcDecodable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 struct Edge {
     source: Index,
     target: Index,
 }
 
-impl<T: Debug + PartialEq> TransitiveRelation<T> {
+impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
     pub fn new() -> TransitiveRelation<T> {
         TransitiveRelation {
             elements: vec![],
+            map: FxHashMap(),
             edges: vec![],
             closure: RefCell::new(None),
         }
@@ -63,21 +66,27 @@ impl<T: Debug + PartialEq> TransitiveRelation<T> {
     }
 
     fn index(&self, a: &T) -> Option<Index> {
-        self.elements.iter().position(|e| *e == *a).map(Index)
+        self.map.get(a).cloned()
     }
 
     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)
-            }
-        }
+        let &mut TransitiveRelation {
+            ref mut elements,
+            ref closure,
+            ref mut map,
+            ..
+        } = self;
+
+        map.entry(a.clone())
+           .or_insert_with(|| {
+               elements.push(a);
+
+               // if we changed the dimensions, clear the cache
+               *closure.borrow_mut() = None;
+
+               Index(elements.len() - 1)
+           })
+           .clone()
     }
 
     /// Applies the (partial) function to each edge and returns a new
@@ -85,7 +94,7 @@ impl<T: Debug + PartialEq> TransitiveRelation<T> {
     /// `None`.
     pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
         where F: FnMut(&T) -> Option<U>,
-              U: Debug + PartialEq,
+              U: Clone + Debug + Eq + Hash + Clone,
     {
         let mut result = TransitiveRelation::new();
         for edge in &self.edges {
@@ -125,6 +134,20 @@ impl<T: Debug + PartialEq> TransitiveRelation<T> {
         }
     }
 
+    /// Returns a vector of all things less than `a`.
+    ///
+    /// Really this probably ought to be `impl Iterator<Item=&T>`, but
+    /// I'm too lazy to make that work, and -- given the caching
+    /// strategy -- it'd be a touch tricky anyhow.
+    pub fn less_than(&self, a: &T) -> Vec<&T> {
+        match self.index(a) {
+            Some(a) => self.with_closure(|closure| {
+                closure.iter(a.0).map(|i| &self.elements[i]).collect()
+            }),
+            None => vec![],
+        }
+    }
+
     /// 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
@@ -335,7 +358,7 @@ fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
 }
 
 impl<T> Encodable for TransitiveRelation<T>
-    where T: Encodable + Debug + PartialEq
+    where T: Clone + Encodable + Debug + Eq + Hash + Clone
 {
     fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
         s.emit_struct("TransitiveRelation", 2, |s| {
@@ -347,19 +370,23 @@ impl<T> Encodable for TransitiveRelation<T>
 }
 
 impl<T> Decodable for TransitiveRelation<T>
-    where T: Decodable + Debug + PartialEq
+    where T: Clone + Decodable + Debug + Eq + Hash + Clone
 {
     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
         d.read_struct("TransitiveRelation", 2, |d| {
-            let elements = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
+            let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
             let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
-            Ok(TransitiveRelation { elements, edges, closure: RefCell::new(None) })
+            let map = elements.iter()
+                              .enumerate()
+                              .map(|(index, elem)| (elem.clone(), Index(index)))
+                              .collect();
+            Ok(TransitiveRelation { elements, edges, map, closure: RefCell::new(None) })
         })
     }
 }
 
 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
-    where T: HashStable<CTX> + PartialEq + Debug
+    where T: HashStable<CTX> + Eq + Debug + Clone + Hash
 {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut CTX,
@@ -369,6 +396,8 @@ impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
         let TransitiveRelation {
             ref elements,
             ref edges,
+            // "map" is just a copy of elements vec
+            map: _,
             // "closure" is just a copy of the data above
             closure: _
         } = *self;