make transitive relation use a hash map

1 files changed, 42 insertions, 27 deletions

diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index b0fca5c0ff3..0d166cc0b9e 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 {
@@ -335,7 +344,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 +356,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 +382,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;