libcore: Implement an `Equiv` trait and use it on hashmaps.

7.3x speedup in string map search speed on a microbenchmark of pure hashmap
searching against a constant string, due to the lack of allocations.

I ran into a few snags.

1. The way the coherence check is set up, I can't implement `Equiv<@str>` and
   `Equiv<~str>` for `&str` simultaneously.

2. I wanted to implement `Equiv<T>` for all `T:Eq` (i.e. every type can be
   compared to itself if it implements `Eq`), but the coherence check didn't
   like that either.

3. I couldn't add this to the `Map` trait because `LinearMap` needs special
   handling for its `Q` type parameter: it must not only implement `Equiv<T>`
   but also `Hash` and `Eq`.

4. `find_equiv(&&"foo")` doesn't parse, because of the double ampersand. It has
   to be written `find_equiv(& &"foo")`. We can probably just fix this.

Nevertheless, this is a huge win; it should address a major source of
performance problems, including the one here:

http://maniagnosis.crsr.net/2013/02/creating-letterpress-cheating-program.html

5 files changed, 73 insertions, 3 deletions

diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index d00824f8be6..ac2afc920ff 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -150,6 +150,14 @@ pub pure fn gt<T:Ord>(v1: &T, v2: &T) -> bool {
     (*v1).gt(v2)
 }
 
+/// The equivalence relation. Two values may be equivalent even if they are
+/// of different types. The most common use case for this relation is
+/// container types; e.g. it is often desirable to be able to use `&str`
+/// values to look up entries in a container with `~str` keys.
+pub trait Equiv<T> {
+    pure fn equiv(&self, other: &T) -> bool;
+}
+
 #[inline(always)]
 pub pure fn min<T:Ord>(v1: T, v2: T) -> T {
     if v1 < v2 { v1 } else { v2 }
diff --git a/src/libcore/container.rs b/src/libcore/container.rs
index 36424d1bfaa..d7e05a62c51 100644
--- a/src/libcore/container.rs
+++ b/src/libcore/container.rs
@@ -10,6 +10,7 @@
 
 //! Container traits
 
+use cmp::Equiv;
 use option::Option;
 
 pub trait Container {
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index b6ba790c300..43ec6294bdc 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -13,7 +13,7 @@
 /// Open addressing with linear probing.
 pub mod linear {
     use container::{Container, Mutable, Map, Set};
-    use cmp::Eq;
+    use cmp::{Eq, Equiv};
     use hash::Hash;
     use to_bytes::IterBytes;
     use iter::BaseIter;
@@ -108,6 +108,15 @@ pub mod linear {
         }
 
         #[inline(always)]
+        pure fn bucket_for_key_equiv<Q:Hash + IterBytes + Equiv<K>>(
+                &self,
+                k: &Q)
+             -> SearchResult {
+            let hash = k.hash_keyed(self.k0, self.k1) as uint;
+            self.bucket_for_key_with_hash_equiv(hash, k)
+        }
+
+        #[inline(always)]
         pure fn bucket_for_key_with_hash(&self,
                                          hash: uint,
                                          k: &K) -> SearchResult {
@@ -122,6 +131,24 @@ pub mod linear {
             TableFull
         }
 
+        #[inline(always)]
+        pure fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
+                                                           hash: uint,
+                                                           k: &Q)
+                                                        -> SearchResult {
+            let _ = for self.bucket_sequence(hash) |i| {
+                match self.buckets[i] {
+                    Some(ref bkt) => {
+                        if bkt.hash == hash && k.equiv(&bkt.key) {
+                            return FoundEntry(i);
+                        }
+                    },
+                    None => return FoundHole(i)
+                }
+            };
+            TableFull
+        }
+
         /// Expand the capacity of the array to the next power of two
         /// and re-insert each of the existing buckets.
         #[inline(always)]
@@ -450,6 +477,28 @@ pub mod linear {
                 None => fail!(fmt!("No entry found for key: %?", k)),
             }
         }
+
+        /// Return true if the map contains a value for the specified key,
+        /// using equivalence
+        pure fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(
+                &self,
+                key: &Q)
+             -> bool {
+            match self.bucket_for_key_equiv(key) {
+                FoundEntry(_) => {true}
+                TableFull | FoundHole(_) => {false}
+            }
+        }
+
+        /// Return the value corresponding to the key in the map, using
+        /// equivalence
+        pure fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
+                                                       -> Option<&self/V> {
+            match self.bucket_for_key_equiv(k) {
+                FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+                TableFull | FoundHole(_) => None,
+            }
+        }
     }
 
     impl<K:Hash + IterBytes + Eq,V:Eq> Eq for LinearMap<K, V> {
diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 471e1ae5396..24b2d8b5813 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -20,7 +20,7 @@
 use at_vec;
 use cast;
 use char;
-use cmp::{TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Equiv, TotalOrd, Ordering, Less, Equal, Greater};
 use libc;
 use option::{None, Option, Some};
 use ptr;
@@ -898,6 +898,12 @@ impl Ord for @str {
     pure fn gt(&self, other: &@str) -> bool { gt((*self), (*other)) }
 }
 
+#[cfg(notest)]
+impl Equiv<~str> for &str {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~str) -> bool { eq_slice(*self, *other) }
+}
+
 /*
 Section: Iterating through strings
 */
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index f7676bd211e..ab5f04ace79 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -14,7 +14,7 @@
 
 use container::{Container, Mutable};
 use cast;
-use cmp::{Eq, Ord, TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Eq, Equiv, Ord, TotalOrd, Ordering, Less, Equal, Greater};
 use iter::BaseIter;
 use iter;
 use kinds::Copy;
@@ -1572,6 +1572,12 @@ impl<T:Eq> Eq for @[T] {
     pure fn ne(&self, other: &@[T]) -> bool { !(*self).eq(other) }
 }
 
+#[cfg(notest)]
+impl<T:Eq> Equiv<~[T]> for &[T] {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~[T]) -> bool { eq(*self, *other) }
+}
+
 // Lexicographical comparison
 
 pure fn cmp<T: TotalOrd>(a: &[T], b: &[T]) -> Ordering {