auto merge of #20163 : bfops/rust/master, r=Gankro

TODOs:
  - ~~Entry is still `<'a, K, V>` instead of `<'a, O, V>`~~
  - ~~BTreeMap is still outstanding~~.
  - ~~Transform appropriate things into `.entry(...).get().or_else(|e| ...)`~~

Things that make me frowny face:
  - I'm not happy about the fact that this `clone`s the key even when it's already owned.
  - With small keys (e.g. `int`s), taking a reference seems wasteful.

r? @Gankro
cc: @cgaebel

2 files changed, 61 insertions, 33 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 651f31b205d..a6532707f3e 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -14,7 +14,7 @@ use self::Entry::*;
 use self::SearchResult::*;
 use self::VacantEntryState::*;
 
-use borrow::BorrowFrom;
+use borrow::{BorrowFrom, ToOwned};
 use clone::Clone;
 use cmp::{max, Eq, PartialEq};
 use default::Default;
@@ -920,12 +920,16 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
-    /// Gets the given key's corresponding entry in the map for in-place manipulation
-    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
+    #[stable]
+    /// Gets the given key's corresponding entry in the map for in-place manipulation.
+    /// Regardless of whether or not `to_owned()` has been called, the key must hash the same way.
+    pub fn entry<'a, Sized? Q>(&'a mut self, key: &'a Q) -> Entry<'a, Q, K, V>
+        where Q: Eq + Hash<S> + ToOwned<K>
+    {
         // Gotta resize now.
         self.reserve(1);
 
-        let hash = self.make_hash(&key);
+        let hash = self.make_hash(key);
         search_entry_hashed(&mut self.table, hash, key)
     }
 
@@ -1138,8 +1142,10 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
-        -> Entry<'a, K, V> {
+fn search_entry_hashed<'a, K, V, Sized? Q>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: &'a Q)
+        -> Entry<'a, Q, K, V>
+    where Q: Eq + ToOwned<K>
+{
     // Worst case, we'll find one empty bucket among `size + 1` buckets.
     let size = table.size();
     let mut probe = Bucket::new(table, hash);
@@ -1161,7 +1167,7 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas
         // hash matches?
         if bucket.hash() == hash {
             // key matches?
-            if k == *bucket.read().0 {
+            if *k == *BorrowFrom::borrow_from(bucket.read().0) {
                 return Occupied(OccupiedEntry{
                     elem: bucket,
                 });
@@ -1343,24 +1349,27 @@ pub struct Drain<'a, K: 'a, V: 'a> {
     >
 }
 
+#[stable]
 /// A view into a single occupied location in a HashMap
-pub struct OccupiedEntry<'a, K:'a, V:'a> {
+pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
 }
 
+#[stable]
 /// A view into a single empty location in a HashMap
-pub struct VacantEntry<'a, K:'a, V:'a> {
+pub struct VacantEntry<'a, Sized? Q: 'a, K: 'a, V: 'a> {
     hash: SafeHash,
-    key: K,
-    elem: VacantEntryState<K,V, &'a mut RawTable<K, V>>,
+    key: &'a Q,
+    elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
 }
 
+#[stable]
 /// A view into a single location in a map, which may be vacant or occupied
-pub enum Entry<'a, K:'a, V:'a> {
+pub enum Entry<'a, Sized? Q: 'a, K: 'a, V: 'a> {
     /// An occupied Entry
     Occupied(OccupiedEntry<'a, K, V>),
     /// A vacant Entry
-    Vacant(VacantEntry<'a, K, V>),
+    Vacant(VacantEntry<'a, Q, K, V>),
 }
 
 /// Possible states of a VacantEntry
@@ -1426,46 +1435,63 @@ impl<'a, K: 'a, V: 'a> Iterator for Drain<'a, K, V> {
     }
 }
 
+impl<'a, Sized? Q, K, V> Entry<'a, Q, K, V> {
+    #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
+    /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
+    pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, Q, K, V>> {
+        match self {
+            Occupied(entry) => Ok(entry.into_mut()),
+            Vacant(entry) => Err(entry),
+        }
+    }
+}
+
 impl<'a, K, V> OccupiedEntry<'a, K, V> {
+    #[stable]
     /// Gets a reference to the value in the entry
     pub fn get(&self) -> &V {
         self.elem.read().1
     }
 
+    #[stable]
     /// Gets a mutable reference to the value in the entry
     pub fn get_mut(&mut self) -> &mut V {
         self.elem.read_mut().1
     }
 
+    #[stable]
     /// Converts the OccupiedEntry into a mutable reference to the value in the entry
     /// with a lifetime bound to the map itself
     pub fn into_mut(self) -> &'a mut V {
         self.elem.into_mut_refs().1
     }
 
+    #[stable]
     /// Sets the value of the entry, and returns the entry's old value
-    pub fn set(&mut self, mut value: V) -> V {
+    pub fn insert(&mut self, mut value: V) -> V {
         let old_value = self.get_mut();
         mem::swap(&mut value, old_value);
         value
     }
 
+    #[stable]
     /// Takes the value out of the entry, and returns it
-    pub fn take(self) -> V {
+    pub fn remove(self) -> V {
         pop_internal(self.elem).1
     }
 }
 
-impl<'a, K, V> VacantEntry<'a, K, V> {
+impl<'a, Sized? Q: 'a + ToOwned<K>, K: 'a, V: 'a> VacantEntry<'a, Q, K, V> {
+    #[stable]
     /// Sets the value of the entry with the VacantEntry's key,
     /// and returns a mutable reference to it
-    pub fn set(self, value: V) -> &'a mut V {
+    pub fn insert(self, value: V) -> &'a mut V {
         match self.elem {
             NeqElem(bucket, ib) => {
-                robin_hood(bucket, ib, self.hash, self.key, value)
+                robin_hood(bucket, ib, self.hash, self.key.to_owned(), value)
             }
             NoElem(bucket) => {
-                bucket.put(self.hash, self.key, value).into_mut_refs().1
+                bucket.put(self.hash, self.key.to_owned(), value).into_mut_refs().1
             }
         }
     }
@@ -1497,6 +1523,8 @@ mod test_map {
     use super::HashMap;
     use super::Entry::{Occupied, Vacant};
     use iter::{range_inclusive, range_step_inclusive, repeat};
+    use borrow::ToOwned;
+    use hash;
     use cell::RefCell;
     use rand::{weak_rng, Rng};
 
@@ -2090,11 +2118,11 @@ mod test_map {
         let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
 
         // Existing key (insert)
-        match map.entry(1) {
+        match map.entry(&1) {
             Vacant(_) => unreachable!(),
             Occupied(mut view) => {
                 assert_eq!(view.get(), &10);
-                assert_eq!(view.set(100), 10);
+                assert_eq!(view.insert(100), 10);
             }
         }
         assert_eq!(map.get(&1).unwrap(), &100);
@@ -2102,7 +2130,7 @@ mod test_map {
 
 
         // Existing key (update)
-        match map.entry(2) {
+        match map.entry(&2) {
             Vacant(_) => unreachable!(),
             Occupied(mut view) => {
                 let v = view.get_mut();
@@ -2114,10 +2142,10 @@ mod test_map {
         assert_eq!(map.len(), 6);
 
         // Existing key (take)
-        match map.entry(3) {
+        match map.entry(&3) {
             Vacant(_) => unreachable!(),
             Occupied(view) => {
-                assert_eq!(view.take(), 30);
+                assert_eq!(view.remove(), 30);
             }
         }
         assert_eq!(map.get(&3), None);
@@ -2125,10 +2153,10 @@ mod test_map {
 
 
         // Inexistent key (insert)
-        match map.entry(10) {
+        match map.entry(&10) {
             Occupied(_) => unreachable!(),
             Vacant(view) => {
-                assert_eq!(*view.set(1000), 1000);
+                assert_eq!(*view.insert(1000), 1000);
             }
         }
         assert_eq!(map.get(&10).unwrap(), &1000);
@@ -2156,11 +2184,11 @@ mod test_map {
 
         for i in range(0u, 1000) {
             let x = rng.gen_range(-10, 10);
-            match m.entry(x) {
+            match m.entry(&x) {
                 Vacant(_) => {},
                 Occupied(e) => {
                     println!("{}: remove {}", i, x);
-                    e.take();
+                    e.remove();
                 },
             }
 
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 4be83bfc664..c0445fb5aea 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -226,7 +226,7 @@
 //! the key has been seen or not. Normally, this would require a `find` followed by an
 //! `insert`, effectively duplicating the search effort on each insertion.
 //!
-//! When a user calls `map.entry(key)`, the map will search for the key and then yield
+//! When a user calls `map.entry(&key)`, the map will search for the key and then yield
 //! a variant of the `Entry` enum.
 //!
 //! If a `Vacant(entry)` is yielded, then the key *was not* found. In this case the
@@ -255,8 +255,8 @@
 //! let message = "she sells sea shells by the sea shore";
 //!
 //! for c in message.chars() {
-//!     match count.entry(c) {
-//!         Vacant(entry) => { entry.set(1u); },
+//!     match count.entry(&c) {
+//!         Vacant(entry) => { entry.insert(1u); },
 //!         Occupied(mut entry) => *entry.get_mut() += 1,
 //!     }
 //! }
@@ -290,8 +290,8 @@
 //! for id in orders.into_iter() {
 //!     // If this is the first time we've seen this customer, initialize them
 //!     // with no blood alcohol. Otherwise, just retrieve them.
-//!     let person = match blood_alcohol.entry(id) {
-//!         Vacant(entry) => entry.set(Person{id: id, blood_alcohol: 0.0}),
+//!     let person = match blood_alcohol.entry(&id) {
+//!         Vacant(entry) => entry.insert(Person{id: id, blood_alcohol: 0.0}),
 //!         Occupied(entry) => entry.into_mut(),
 //!     };
 //!