auto merge of #18719 : alexcrichton/rust/rollup, r=alexcrichton

10 files changed, 353 insertions, 237 deletions

diff --git a/src/libstd/collections/hash/bench.rs b/src/libstd/collections/hash/bench.rs
index 62b93336a34..87aebb24f98 100644
--- a/src/libstd/collections/hash/bench.rs
+++ b/src/libstd/collections/hash/bench.rs
@@ -102,14 +102,14 @@ fn hashmap_as_queue(b: &mut Bencher) {
     let mut k = 1i;
 
     b.iter(|| {
-        m.pop(&k);
+        m.remove(&k);
         m.insert(k + 1000, k + 1000);
         k += 1;
     });
 }
 
 #[bench]
-fn find_pop_insert(b: &mut Bencher) {
+fn get_remove_insert(b: &mut Bencher) {
     use super::map::HashMap;
 
     let mut m = HashMap::new();
@@ -121,9 +121,9 @@ fn find_pop_insert(b: &mut Bencher) {
     let mut k = 1i;
 
     b.iter(|| {
-        m.find(&(k + 400));
-        m.find(&(k + 2000));
-        m.pop(&k);
+        m.get(&(k + 400));
+        m.get(&(k + 2000));
+        m.remove(&k);
         m.insert(k + 1000, k + 1000);
         k += 1;
     })
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 596e483c2f6..e164128eeb1 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -36,6 +36,9 @@ use super::table::{
     SafeHash
 };
 
+// FIXME(conventions): update capacity management to match other collections (no auto-shrink)
+// FIXME(conventions): axe find_copy/get_copy in favour of Option.cloned (also implement that)
+
 const INITIAL_LOG2_CAP: uint = 5;
 pub const INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
 
@@ -233,7 +236,7 @@ impl DefaultResizePolicy {
 /// // look up the values associated with some keys.
 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
 /// for book in to_find.iter() {
-///     match book_reviews.find(book) {
+///     match book_reviews.get(book) {
 ///         Some(review) => println!("{}: {}", *book, *review),
 ///         None => println!("{} is unreviewed.", *book)
 ///     }
@@ -477,9 +480,10 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     ///
     /// ```
     /// use std::collections::HashMap;
-    /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
+    /// let mut map: HashMap<&str, int> = HashMap::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_hasher(hasher)
@@ -494,6 +498,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_capacity_and_hasher(capacity, hasher)
@@ -741,38 +746,6 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
-    /// Retrieves a mutable value for the given key.
-    /// See [`find_mut`](../trait.MutableMap.html#tymethod.find_mut) for a non-panicking
-    /// alternative.
-    ///
-    /// # Failure
-    ///
-    /// Fails if the key is not present.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// # #![allow(deprecated)]
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// map.insert("a", 1i);
-    /// {
-    ///     // val will freeze map to prevent usage during its lifetime
-    ///     let val = map.get_mut(&"a");
-    ///     *val = 40;
-    /// }
-    /// assert_eq!(map["a"], 40);
-    ///
-    /// // A more direct way could be:
-    /// *map.get_mut(&"a") = -2;
-    /// assert_eq!(map["a"], -2);
-    /// ```
-    #[deprecated = "use indexing instead: `&mut map[key]`"]
-    pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
-        &mut self[*k]
-    }
-
     /// Return true if the map contains a value for the specified key,
     /// using equivalence.
     ///
@@ -875,6 +848,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("{}", key);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys(&self) -> Keys<K, V> {
         self.iter().map(|(k, _v)| k)
     }
@@ -896,6 +870,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("{}", key);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values(&self) -> Values<K, V> {
         self.iter().map(|(_k, v)| v)
     }
@@ -917,6 +892,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("key: {} val: {}", key, val);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter(&self) -> Entries<K, V> {
         Entries { inner: self.table.iter() }
     }
@@ -944,6 +920,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("key: {} val: {}", key, val);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut(&mut self) -> MutEntries<K, V> {
         MutEntries { inner: self.table.iter_mut() }
     }
@@ -965,6 +942,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// // Not possible with .iter()
     /// let vec: Vec<(&str, int)> = map.into_iter().collect();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveEntries<K, V> {
         MoveEntries {
             inner: self.table.into_iter().map(|(_, k, v)| (k, v))
@@ -996,6 +974,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// a.insert(1u, "a");
     /// assert_eq!(a.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.table.size() }
 
     /// Return true if the map contains no elements.
@@ -1011,6 +990,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert!(!a.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the map, removing all key-value pairs. Keeps the allocated memory
@@ -1026,6 +1006,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// a.clear();
     /// assert!(a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         // Prevent reallocations from happening from now on. Makes it possible
         // for the map to be reused but has a downside: reserves permanently.
@@ -1045,6 +1026,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
+    /// Deprecated: Renamed to `get`.
+    #[deprecated = "Renamed to `get`"]
+    pub fn find(&self, k: &K) -> Option<&V> {
+        self.get(k)
+    }
+
     /// Returns a reference to the value corresponding to the key.
     ///
     /// # Example
@@ -1054,10 +1041,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
-    pub fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, k: &K) -> Option<&V> {
         self.search(k).map(|bucket| {
             let (_, v) = bucket.into_refs();
             v
@@ -1076,10 +1064,17 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map.contains_key(&1), true);
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, k: &K) -> bool {
         self.search(k).is_some()
     }
 
+    /// Deprecated: Renamed to `get_mut`.
+    #[deprecated = "Renamed to `get_mut`"]
+    pub fn find_mut(&mut self, k: &K) -> Option<&mut V> {
+        self.get_mut(k)
+    }
+
     /// Returns a mutable reference to the value corresponding to the key.
     ///
     /// # Example
@@ -1089,13 +1084,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
-    pub fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
         match self.search_mut(k) {
             Some(bucket) => {
                 let (_, v) = bucket.into_mut_refs();
@@ -1105,41 +1101,10 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// assert_eq!(map.insert(2u, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    #[inline]
-    pub fn insert(&mut self, key: K, value: V) -> bool {
-        self.swap(key, value).is_none()
-    }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// assert_eq!(map.remove(&1u), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    #[inline]
-    pub fn remove(&mut self, key: &K) -> bool {
-        self.pop(key).is_some()
+    /// Deprecated: Renamed to `insert`.
+    #[deprecated = "Renamed to `insert`"]
+    pub fn swap(&mut self, k: K, v: V) -> Option<V> {
+        self.insert(k, v)
     }
 
     /// Inserts a key-value pair from the map. If the key already had a value
@@ -1151,14 +1116,15 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// use std::collections::HashMap;
     ///
     /// let mut map = HashMap::new();
-    /// assert_eq!(map.swap(37u, "a"), None);
+    /// assert_eq!(map.insert(37u, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, k: K, v: V) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         let hash = self.make_hash(&k);
         let potential_new_size = self.table.size() + 1;
         self.make_some_room(potential_new_size);
@@ -1170,6 +1136,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         retval
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, k: &K) -> Option<V> {
+        self.remove(k)
+    }
+
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -1180,10 +1152,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, k: &K) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, k: &K) -> Option<V> {
         if self.table.size() == 0 {
             return None
         }
@@ -1260,7 +1233,7 @@ impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
     /// let s: String = map.find_copy(&1).unwrap();
     /// ```
     pub fn find_copy(&self, k: &K) -> Option<V> {
-        self.find(k).map(|v| (*v).clone())
+        self.get(k).map(|v| (*v).clone())
     }
 
     /// Return a copy of the value corresponding to the key.
@@ -1288,7 +1261,7 @@ impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V,
         if self.len() != other.len() { return false; }
 
         self.iter().all(|(key, value)|
-            other.find(key).map_or(false, |v| *value == *v)
+            other.get(key).map_or(false, |v| *value == *v)
         )
     }
 }
@@ -1317,14 +1290,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H>
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Index<K, V> for HashMap<K, V, H> {
     #[inline]
     fn index<'a>(&'a self, index: &K) -> &'a V {
-        self.find(index).expect("no entry found for key")
+        self.get(index).expect("no entry found for key")
     }
 }
 
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> IndexMut<K, V> for HashMap<K, V, H> {
     #[inline]
     fn index_mut<'a>(&'a mut self, index: &K) -> &'a mut V {
-        match self.find_mut(index) {
+        match self.get_mut(index) {
             Some(v) => v,
             None => panic!("no entry found for key")
         }
@@ -1514,7 +1487,7 @@ mod test_map {
     fn test_create_capacity_zero() {
         let mut m = HashMap::with_capacity(0);
 
-        assert!(m.insert(1i, 1i));
+        assert!(m.insert(1i, 1i).is_none());
 
         assert!(m.contains_key(&1));
         assert!(!m.contains_key(&0));
@@ -1524,12 +1497,12 @@ mod test_map {
     fn test_insert() {
         let mut m = HashMap::new();
         assert_eq!(m.len(), 0);
-        assert!(m.insert(1i, 2i));
+        assert!(m.insert(1i, 2i).is_none());
         assert_eq!(m.len(), 1);
-        assert!(m.insert(2i, 4i));
+        assert!(m.insert(2i, 4i).is_none());
         assert_eq!(m.len(), 2);
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&2).unwrap(), 4);
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&2).unwrap(), 4);
     }
 
     local_data_key!(drop_vector: RefCell<Vec<int>>)
@@ -1588,7 +1561,7 @@ mod test_map {
 
             for i in range(0u, 50) {
                 let k = Dropable::new(i);
-                let v = m.pop(&k);
+                let v = m.remove(&k);
 
                 assert!(v.is_some());
 
@@ -1679,7 +1652,7 @@ mod test_map {
     #[test]
     fn test_empty_pop() {
         let mut m: HashMap<int, bool> = HashMap::new();
-        assert_eq!(m.pop(&0), None);
+        assert_eq!(m.remove(&0), None);
     }
 
     #[test]
@@ -1692,15 +1665,15 @@ mod test_map {
             assert!(m.is_empty());
 
             for i in range_inclusive(1i, 1000) {
-                assert!(m.insert(i, i));
+                assert!(m.insert(i, i).is_none());
 
                 for j in range_inclusive(1, i) {
-                    let r = m.find(&j);
+                    let r = m.get(&j);
                     assert_eq!(r, Some(&j));
                 }
 
                 for j in range_inclusive(i+1, 1000) {
-                    let r = m.find(&j);
+                    let r = m.get(&j);
                     assert_eq!(r, None);
                 }
             }
@@ -1711,7 +1684,7 @@ mod test_map {
 
             // remove forwards
             for i in range_inclusive(1i, 1000) {
-                assert!(m.remove(&i));
+                assert!(m.remove(&i).is_some());
 
                 for j in range_inclusive(1, i) {
                     assert!(!m.contains_key(&j));
@@ -1727,12 +1700,12 @@ mod test_map {
             }
 
             for i in range_inclusive(1i, 1000) {
-                assert!(m.insert(i, i));
+                assert!(m.insert(i, i).is_none());
             }
 
             // remove backwards
             for i in range_step_inclusive(1000i, 1, -1) {
-                assert!(m.remove(&i));
+                assert!(m.remove(&i).is_some());
 
                 for j in range_inclusive(i, 1000) {
                     assert!(!m.contains_key(&j));
@@ -1748,59 +1721,59 @@ mod test_map {
     #[test]
     fn test_find_mut() {
         let mut m = HashMap::new();
-        assert!(m.insert(1i, 12i));
-        assert!(m.insert(2i, 8i));
-        assert!(m.insert(5i, 14i));
+        assert!(m.insert(1i, 12i).is_none());
+        assert!(m.insert(2i, 8i).is_none());
+        assert!(m.insert(5i, 14i).is_none());
         let new = 100;
-        match m.find_mut(&5) {
+        match m.get_mut(&5) {
             None => panic!(), Some(x) => *x = new
         }
-        assert_eq!(m.find(&5), Some(&new));
+        assert_eq!(m.get(&5), Some(&new));
     }
 
     #[test]
     fn test_insert_overwrite() {
         let mut m = HashMap::new();
-        assert!(m.insert(1i, 2i));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert!(!m.insert(1i, 3i));
-        assert_eq!(*m.find(&1).unwrap(), 3);
+        assert!(m.insert(1i, 2i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert!(!m.insert(1i, 3i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 3);
     }
 
     #[test]
     fn test_insert_conflicts() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
-        assert!(m.insert(5i, 3i));
-        assert!(m.insert(9i, 4i));
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert_eq!(*m.find(&1).unwrap(), 2);
+        assert!(m.insert(1i, 2i).is_none());
+        assert!(m.insert(5i, 3i).is_none());
+        assert!(m.insert(9i, 4i).is_none());
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert_eq!(*m.get(&1).unwrap(), 2);
     }
 
     #[test]
     fn test_conflict_remove() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert!(m.insert(5, 3));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert!(m.insert(9, 4));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert!(m.remove(&1));
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert_eq!(*m.find(&5).unwrap(), 3);
+        assert!(m.insert(1i, 2i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert!(m.insert(5, 3).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert!(m.insert(9, 4).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert!(m.remove(&1).is_some());
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert_eq!(*m.get(&5).unwrap(), 3);
     }
 
     #[test]
     fn test_is_empty() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
+        assert!(m.insert(1i, 2i).is_none());
         assert!(!m.is_empty());
-        assert!(m.remove(&1));
+        assert!(m.remove(&1).is_some());
         assert!(m.is_empty());
     }
 
@@ -1808,8 +1781,8 @@ mod test_map {
     fn test_pop() {
         let mut m = HashMap::new();
         m.insert(1i, 2i);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
+        assert_eq!(m.remove(&1), Some(2));
+        assert_eq!(m.remove(&1), None);
     }
 
     #[test]
@@ -1822,18 +1795,10 @@ mod test_map {
     }
 
     #[test]
-    fn test_swap() {
-        let mut m = HashMap::new();
-        assert_eq!(m.swap(1i, 2i), None);
-        assert_eq!(m.swap(1i, 3i), Some(2));
-        assert_eq!(m.swap(1i, 4i), Some(3));
-    }
-
-    #[test]
     fn test_iterate() {
         let mut m = HashMap::with_capacity(4);
         for i in range(0u, 32) {
-            assert!(m.insert(i, i*2));
+            assert!(m.insert(i, i*2).is_none());
         }
         assert_eq!(m.len(), 32);
 
@@ -1871,9 +1836,9 @@ mod test_map {
     #[test]
     fn test_find() {
         let mut m = HashMap::new();
-        assert!(m.find(&1i).is_none());
+        assert!(m.get(&1i).is_none());
         m.insert(1i, 2i);
-        match m.find(&1) {
+        match m.get(&1) {
             None => panic!(),
             Some(v) => assert_eq!(*v, 2)
         }
@@ -1882,7 +1847,7 @@ mod test_map {
     #[test]
     fn test_find_copy() {
         let mut m = HashMap::new();
-        assert!(m.find(&1i).is_none());
+        assert!(m.get(&1i).is_none());
 
         for i in range(1i, 10000) {
             m.insert(i, i + 7);
@@ -2026,7 +1991,7 @@ mod test_map {
         let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
+            assert_eq!(map.get(&k), Some(&v));
         }
     }
 
@@ -2093,7 +2058,7 @@ mod test_map {
                 assert_eq!(view.set(100), 10);
             }
         }
-        assert_eq!(map.find(&1).unwrap(), &100);
+        assert_eq!(map.get(&1).unwrap(), &100);
         assert_eq!(map.len(), 6);
 
 
@@ -2106,7 +2071,7 @@ mod test_map {
                 *v = new_v;
             }
         }
-        assert_eq!(map.find(&2).unwrap(), &200);
+        assert_eq!(map.get(&2).unwrap(), &200);
         assert_eq!(map.len(), 6);
 
         // Existing key (take)
@@ -2116,7 +2081,7 @@ mod test_map {
                 assert_eq!(view.take(), 30);
             }
         }
-        assert_eq!(map.find(&3), None);
+        assert_eq!(map.get(&3), None);
         assert_eq!(map.len(), 5);
 
 
@@ -2127,7 +2092,7 @@ mod test_map {
                 assert_eq!(*view.set(1000), 1000);
             }
         }
-        assert_eq!(map.find(&10).unwrap(), &1000);
+        assert_eq!(map.get(&10).unwrap(), &1000);
         assert_eq!(map.len(), 6);
     }
 }
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index cde862a1d17..58386882ac5 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -23,6 +23,9 @@ use result::{Ok, Err};
 
 use super::map::{HashMap, Entries, MoveEntries, INITIAL_CAPACITY};
 
+// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
+// FIXME(conventions): update capacity management to match other collections (no auto-shrink)
+
 
 // Future Optimization (FIXME!)
 // =============================
@@ -103,6 +106,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// let mut set: HashSet<int> = HashSet::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> HashSet<T, RandomSipHasher> {
         HashSet::with_capacity(INITIAL_CAPACITY)
     }
@@ -117,6 +121,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// let mut set: HashSet<int> = HashSet::with_capacity(10);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
         HashSet { map: HashMap::with_capacity(capacity) }
     }
@@ -240,16 +245,11 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
         self.map.keys()
     }
 
-    /// Deprecated: use `into_iter`.
-    #[deprecated = "use into_iter"]
-    pub fn move_iter(self) -> SetMoveItems<T> {
-        self.into_iter()
-    }
-
     /// Creates a consuming iterator, that is, one that moves each value out
     /// of the set in arbitrary order. The set cannot be used after calling
     /// this.
@@ -270,6 +270,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> SetMoveItems<T> {
         self.map.into_iter().map(|(k, _)| k)
     }
@@ -296,6 +297,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
     /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> {
         Repeat::new(other).zip(self.iter())
             .filter_map(|(other, elt)| {
@@ -323,6 +325,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff1, diff2);
     /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
         -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
         self.difference(other).chain(other.difference(self))
@@ -345,6 +348,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>)
         -> SetAlgebraItems<'a, T, H> {
         Repeat::new(other).zip(self.iter())
@@ -370,6 +374,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
         -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
         self.iter().chain(other.difference(self))
@@ -387,6 +392,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.insert(1u);
     /// assert_eq!(v.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -401,6 +407,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.insert(1u);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.map.len() == 0 }
 
     /// Clears the set, removing all values.
@@ -415,6 +422,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.clear();
     /// assert!(v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear() }
 
     /// Returns `true` if the set contains a value.
@@ -428,6 +436,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.contains(&1), true);
     /// assert_eq!(set.contains(&4), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 
     /// Returns `true` if the set has no elements in common with `other`.
@@ -447,6 +456,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// b.insert(1);
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| !other.contains(v))
     }
@@ -467,6 +477,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// set.insert(4);
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| other.contains(v))
     }
@@ -491,6 +502,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.is_superset(&sub), true);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
         other.is_subset(self)
     }
@@ -509,7 +521,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.insert(2), false);
     /// assert_eq!(set.len(), 1);
     /// ```
-    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 
     /// Removes a value from the set. Returns `true` if the value was
     /// present in the set.
@@ -525,7 +538,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.remove(&2), true);
     /// assert_eq!(set.remove(&2), false);
     /// ```
-    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value).is_some() }
 }
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs
index 93e649f9355..aab0924e7e4 100644
--- a/src/libstd/collections/lru_cache.rs
+++ b/src/libstd/collections/lru_cache.rs
@@ -20,20 +20,20 @@
 //! use std::collections::LruCache;
 //!
 //! let mut cache: LruCache<int, int> = LruCache::new(2);
-//! cache.put(1, 10);
-//! cache.put(2, 20);
-//! cache.put(3, 30);
+//! cache.insert(1, 10);
+//! cache.insert(2, 20);
+//! cache.insert(3, 30);
 //! assert!(cache.get(&1).is_none());
 //! assert_eq!(*cache.get(&2).unwrap(), 20);
 //! assert_eq!(*cache.get(&3).unwrap(), 30);
 //!
-//! cache.put(2, 22);
+//! cache.insert(2, 22);
 //! assert_eq!(*cache.get(&2).unwrap(), 22);
 //!
-//! cache.put(6, 60);
+//! cache.insert(6, 60);
 //! assert!(cache.get(&3).is_none());
 //!
-//! cache.change_capacity(1);
+//! cache.set_capacity(1);
 //! assert!(cache.get(&2).is_none());
 //! ```
 
@@ -49,6 +49,9 @@ use boxed::Box;
 use ptr;
 use result::{Ok, Err};
 
+// FIXME(conventions): implement iterators?
+// FIXME(conventions): implement indexing?
+
 struct KeyRef<K> { k: *const K }
 
 struct LruEntry<K, V> {
@@ -99,6 +102,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache: LruCache<int, &str> = LruCache::new(10);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new(capacity: uint) -> LruCache<K, V> {
         let cache = LruCache {
             map: HashMap::new(),
@@ -112,7 +116,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         return cache;
     }
 
-    /// Put a key-value pair into cache.
+    /// Deprecated: Replaced with `insert`.
+    #[deprecated = "Replaced with `insert`"]
+    pub fn put(&mut self, k: K, v: V) {
+        self.insert(k, v);
+    }
+
+    /// Inserts a key-value pair into the cache. If the key already existed, the old value is
+    /// returned.
     ///
     /// # Example
     ///
@@ -120,22 +131,23 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
     /// assert_eq!(cache.get(&1), Some(&"a"));
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// ```
-    pub fn put(&mut self, k: K, v: V) {
-        let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
+        let (node_ptr, node_opt, old_val) = match self.map.get_mut(&KeyRef{k: &k}) {
             Some(node) => {
-                node.value = v;
+                let old_val = mem::replace(&mut node.value, v);
                 let node_ptr: *mut LruEntry<K, V> = &mut **node;
-                (node_ptr, None)
+                (node_ptr, None, Some(old_val))
             }
             None => {
                 let mut node = box LruEntry::new(k, v);
                 let node_ptr: *mut LruEntry<K, V> = &mut *node;
-                (node_ptr, Some(node))
+                (node_ptr, Some(node), None)
             }
         };
         match node_opt {
@@ -146,13 +158,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
             }
             Some(node) => {
                 let keyref = unsafe { &(*node_ptr).key };
-                self.map.swap(KeyRef{k: keyref}, node);
+                self.map.insert(KeyRef{k: keyref}, node);
                 self.attach(node_ptr);
                 if self.len() > self.capacity() {
                     self.remove_lru();
                 }
             }
         }
+        old_val
     }
 
     /// Return a value corresponding to the key in the cache.
@@ -163,16 +176,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
-    /// cache.put(2, "c");
-    /// cache.put(3, "d");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
+    /// cache.insert(2, "c");
+    /// cache.insert(3, "d");
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), Some(&"c"));
     /// ```
-    pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
-        let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&mut self, k: &K) -> Option<&V> {
+        let (value, node_ptr_opt) = match self.map.get_mut(&KeyRef{k: k}) {
             None => (None, None),
             Some(node) => {
                 let node_ptr: *mut LruEntry<K, V> = &mut **node;
@@ -189,6 +203,12 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         return value;
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, k: &K) -> Option<V> {
+        self.remove(k)
+    }
+
     /// Remove and return a value corresponding to the key from the cache.
     ///
     /// # Example
@@ -197,15 +217,16 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(2i, "a");
+    /// cache.insert(2i, "a");
     ///
-    /// assert_eq!(cache.pop(&1), None);
-    /// assert_eq!(cache.pop(&2), Some("a"));
-    /// assert_eq!(cache.pop(&2), None);
+    /// assert_eq!(cache.remove(&1), None);
+    /// assert_eq!(cache.remove(&2), Some("a"));
+    /// assert_eq!(cache.remove(&2), None);
     /// assert_eq!(cache.len(), 0);
     /// ```
-    pub fn pop(&mut self, k: &K) -> Option<V> {
-        match self.map.pop(&KeyRef{k: k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, k: &K) -> Option<V> {
+        match self.map.remove(&KeyRef{k: k}) {
             None => None,
             Some(lru_entry) => Some(lru_entry.value)
         }
@@ -220,10 +241,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// let mut cache: LruCache<int, &str> = LruCache::new(2);
     /// assert_eq!(cache.capacity(), 2);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn capacity(&self) -> uint {
         self.max_size
     }
 
+    /// Deprecated: Renamed to `set_capacity`.
+    #[deprecated = "Renamed to `set_capacity`"]
+    pub fn change_capacity(&mut self, capacity: uint) {
+        self.set_capacity(capacity)
+    }
+
     /// Change the number of key-value pairs the cache can hold. Remove
     /// least-recently-used key-value pairs if necessary.
     ///
@@ -233,29 +261,30 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
-    /// cache.put(3, "c");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
+    /// cache.insert(3, "c");
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// assert_eq!(cache.get(&3), Some(&"c"));
     ///
-    /// cache.change_capacity(3);
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
+    /// cache.set_capacity(3);
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
     ///
     /// assert_eq!(cache.get(&1), Some(&"a"));
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// assert_eq!(cache.get(&3), Some(&"c"));
     ///
-    /// cache.change_capacity(1);
+    /// cache.set_capacity(1);
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), None);
     /// assert_eq!(cache.get(&3), Some(&"c"));
     /// ```
-    pub fn change_capacity(&mut self, capacity: uint) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn set_capacity(&mut self, capacity: uint) {
         for _ in range(capacity, self.len()) {
             self.remove_lru();
         }
@@ -267,7 +296,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         if self.len() > 0 {
             let lru = unsafe { (*self.head).prev };
             self.detach(lru);
-            self.map.pop(&KeyRef{k: unsafe { &(*lru).key }});
+            self.map.remove(&KeyRef{k: unsafe { &(*lru).key }});
         }
     }
 
@@ -290,12 +319,15 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     }
 
     /// Return the number of key-value pairs in the cache.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns whether the cache is currently empty.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clear the cache of all key-value pairs.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear(); }
 }
 
@@ -347,8 +379,8 @@ mod tests {
     #[test]
     fn test_put_and_get() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         assert_opt_eq(cache.get(&1), 10);
         assert_opt_eq(cache.get(&2), 20);
         assert_eq!(cache.len(), 2);
@@ -357,8 +389,8 @@ mod tests {
     #[test]
     fn test_put_update() {
         let mut cache: LruCache<String, Vec<u8>> = LruCache::new(1);
-        cache.put("1".to_string(), vec![10, 10]);
-        cache.put("1".to_string(), vec![10, 19]);
+        cache.insert("1".to_string(), vec![10, 10]);
+        cache.insert("1".to_string(), vec![10, 19]);
         assert_opt_eq(cache.get(&"1".to_string()), vec![10, 19]);
         assert_eq!(cache.len(), 1);
     }
@@ -366,22 +398,22 @@ mod tests {
     #[test]
     fn test_expire_lru() {
         let mut cache: LruCache<String, String> = LruCache::new(2);
-        cache.put("foo1".to_string(), "bar1".to_string());
-        cache.put("foo2".to_string(), "bar2".to_string());
-        cache.put("foo3".to_string(), "bar3".to_string());
+        cache.insert("foo1".to_string(), "bar1".to_string());
+        cache.insert("foo2".to_string(), "bar2".to_string());
+        cache.insert("foo3".to_string(), "bar3".to_string());
         assert!(cache.get(&"foo1".to_string()).is_none());
-        cache.put("foo2".to_string(), "bar2update".to_string());
-        cache.put("foo4".to_string(), "bar4".to_string());
+        cache.insert("foo2".to_string(), "bar2update".to_string());
+        cache.insert("foo4".to_string(), "bar4".to_string());
         assert!(cache.get(&"foo3".to_string()).is_none());
     }
 
     #[test]
     fn test_pop() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         assert_eq!(cache.len(), 2);
-        let opt1 = cache.pop(&1);
+        let opt1 = cache.remove(&1);
         assert!(opt1.is_some());
         assert_eq!(opt1.unwrap(), 10);
         assert!(cache.get(&1).is_none());
@@ -392,9 +424,9 @@ mod tests {
     fn test_change_capacity() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
         assert_eq!(cache.capacity(), 2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.change_capacity(1);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
+        cache.set_capacity(1);
         assert!(cache.get(&1).is_none());
         assert_eq!(cache.capacity(), 1);
     }
@@ -402,25 +434,25 @@ mod tests {
     #[test]
     fn test_to_string() {
         let mut cache: LruCache<int, int> = LruCache::new(3);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.put(3, 30);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
+        cache.insert(3, 30);
         assert_eq!(cache.to_string(), "{3: 30, 2: 20, 1: 10}".to_string());
-        cache.put(2, 22);
+        cache.insert(2, 22);
         assert_eq!(cache.to_string(), "{2: 22, 3: 30, 1: 10}".to_string());
-        cache.put(6, 60);
+        cache.insert(6, 60);
         assert_eq!(cache.to_string(), "{6: 60, 2: 22, 3: 30}".to_string());
         cache.get(&3);
         assert_eq!(cache.to_string(), "{3: 30, 6: 60, 2: 22}".to_string());
-        cache.change_capacity(2);
+        cache.set_capacity(2);
         assert_eq!(cache.to_string(), "{3: 30, 6: 60}".to_string());
     }
 
     #[test]
     fn test_clear() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         cache.clear();
         assert!(cache.get(&1).is_none());
         assert!(cache.get(&2).is_none());
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 13486d4b8f8..3419a3d98a1 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -278,7 +278,7 @@
 //!     }
 //! }
 //!
-//! assert_eq!(count.find(&'s'), Some(&8));
+//! assert_eq!(count.get(&'s'), Some(&8));
 //!
 //! println!("Number of occurences of each character");
 //! for (char, count) in count.iter() {
diff --git a/src/libstd/error.rs b/src/libstd/error.rs
index 6bb9f4b473b..b048ab13968 100644
--- a/src/libstd/error.rs
+++ b/src/libstd/error.rs
@@ -33,9 +33,6 @@
 //! particular implementation, but also reveal some of its implementation for
 //! debugging via `cause` chains.
 //!
-//! The trait inherits from `Any` to allow *downcasting*: converting from a
-//! trait object to a specific concrete type when applicable.
-//!
 //! # The `FromError` trait
 //!
 //! `FromError` is a simple trait that expresses conversions between different
diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs
index da5286b16ae..c404741b7c3 100644
--- a/src/libstd/io/mod.rs
+++ b/src/libstd/io/mod.rs
@@ -627,7 +627,7 @@ pub trait Reader {
     /// as `Err(IoError)`. See `read()` for more details.
     fn push(&mut self, len: uint, buf: &mut Vec<u8>) -> IoResult<uint> {
         let start_len = buf.len();
-        buf.reserve_additional(len);
+        buf.reserve(len);
 
         let n = {
             let s = unsafe { slice_vec_capacity(buf, start_len, start_len + len) };
@@ -658,7 +658,7 @@ pub trait Reader {
         }
 
         let start_len = buf.len();
-        buf.reserve_additional(len);
+        buf.reserve(len);
 
         // we can't just use self.read_at_least(min, slice) because we need to push
         // successful reads onto the vector before any returned errors.
@@ -1737,7 +1737,7 @@ pub enum FileAccess {
 }
 
 /// Different kinds of files which can be identified by a call to stat
-#[deriving(PartialEq, Show, Hash)]
+#[deriving(PartialEq, Show, Hash, Clone)]
 pub enum FileType {
     /// This is a normal file, corresponding to `S_IFREG`
     TypeFile,
diff --git a/src/libstd/io/process.rs b/src/libstd/io/process.rs
index 493e1b559d7..698e0a3460f 100644
--- a/src/libstd/io/process.rs
+++ b/src/libstd/io/process.rs
@@ -1137,7 +1137,7 @@ mod tests {
         cmd.env("path", "foo");
         cmd.env("Path", "bar");
         let env = &cmd.env.unwrap();
-        let val = env.find(&EnvKey("PATH".to_c_str()));
+        let val = env.get(&EnvKey("PATH".to_c_str()));
         assert!(val.unwrap() == &"bar".to_c_str());
     }
 }
diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
index 21e531d211a..5ef2c2fe23d 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -45,8 +45,12 @@
 //!     so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases.
 //!     However, this means that `/dev/urandom` can yield somewhat predictable randomness
 //!     if the entropy pool is very small, such as immediately after first booting.
-//!     If an application likely to be run soon after first booting, or on a system with very
-//!     few entropy sources, one should consider using `/dev/random` via `ReaderRng`.
+//!     Linux 3,17 added `getrandom(2)` system call which solves the issue: it blocks if entropy
+//!     pool is not initialized yet, but it does not block once initialized.
+//!     `OsRng` tries to use `getrandom(2)` if available, and use `/dev/urandom` fallback if not.
+//!     If an application does not have `getrandom` and likely to be run soon after first booting,
+//!     or on a system with very few entropy sources, one should consider using `/dev/random` via
+//!     `ReaderRng`.
 //! -   On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no difference
 //!     between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random`
 //!     and `/dev/urandom` may block once if the CSPRNG has not seeded yet.)
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
index b6b66e593a2..6bf259d201e 100644
--- a/src/libstd/rand/os.rs
+++ b/src/libstd/rand/os.rs
@@ -15,45 +15,149 @@ pub use self::imp::OsRng;
 
 #[cfg(all(unix, not(target_os = "ios")))]
 mod imp {
+    extern crate libc;
+
     use io::{IoResult, File};
     use path::Path;
     use rand::Rng;
     use rand::reader::ReaderRng;
     use result::{Ok, Err};
+    use slice::SlicePrelude;
+    use mem;
+    use os::errno;
+
+    #[cfg(all(target_os = "linux",
+              any(target_arch = "x86_64", target_arch = "x86", target_arch = "arm")))]
+    fn getrandom(buf: &mut [u8]) -> libc::c_long {
+        extern "C" {
+            fn syscall(number: libc::c_long, ...) -> libc::c_long;
+        }
+
+        #[cfg(target_arch = "x86_64")]
+        const NR_GETRANDOM: libc::c_long = 318;
+        #[cfg(target_arch = "x86")]
+        const NR_GETRANDOM: libc::c_long = 355;
+        #[cfg(target_arch = "arm")]
+        const NR_GETRANDOM: libc::c_long = 384;
+
+        unsafe {
+            syscall(NR_GETRANDOM, buf.as_mut_ptr(), buf.len(), 0u)
+        }
+    }
+
+    #[cfg(not(all(target_os = "linux",
+                  any(target_arch = "x86_64", target_arch = "x86", target_arch = "arm"))))]
+    fn getrandom(_buf: &mut [u8]) -> libc::c_long { -1 }
+
+    fn getrandom_fill_bytes(v: &mut [u8]) {
+        let mut read = 0;
+        let len = v.len();
+        while read < len {
+            let result = getrandom(v[mut read..]);
+            if result == -1 {
+                let err = errno() as libc::c_int;
+                if err == libc::EINTR {
+                    continue;
+                } else {
+                    panic!("unexpected getrandom error: {}", err);
+                }
+            } else {
+                read += result as uint;
+            }
+        }
+    }
+
+    fn getrandom_next_u32() -> u32 {
+        let mut buf: [u8, ..4] = [0u8, ..4];
+        getrandom_fill_bytes(&mut buf);
+        unsafe { mem::transmute::<[u8, ..4], u32>(buf) }
+    }
+
+    fn getrandom_next_u64() -> u64 {
+        let mut buf: [u8, ..8] = [0u8, ..8];
+        getrandom_fill_bytes(&mut buf);
+        unsafe { mem::transmute::<[u8, ..8], u64>(buf) }
+    }
+
+    #[cfg(all(target_os = "linux",
+              any(target_arch = "x86_64", target_arch = "x86", target_arch = "arm")))]
+    fn is_getrandom_available() -> bool {
+        use sync::atomic::{AtomicBool, INIT_ATOMIC_BOOL, Relaxed};
+
+        static GETRANDOM_CHECKED: AtomicBool = INIT_ATOMIC_BOOL;
+        static GETRANDOM_AVAILABLE: AtomicBool = INIT_ATOMIC_BOOL;
+
+        if !GETRANDOM_CHECKED.load(Relaxed) {
+            let mut buf: [u8, ..0] = [];
+            let result = getrandom(&mut buf);
+            let available = if result == -1 {
+                let err = errno() as libc::c_int;
+                err != libc::ENOSYS
+            } else {
+                true
+            };
+            GETRANDOM_AVAILABLE.store(available, Relaxed);
+            GETRANDOM_CHECKED.store(true, Relaxed);
+            available
+        } else {
+            GETRANDOM_AVAILABLE.load(Relaxed)
+        }
+    }
+
+    #[cfg(not(all(target_os = "linux",
+                  any(target_arch = "x86_64", target_arch = "x86", target_arch = "arm"))))]
+    fn is_getrandom_available() -> bool { false }
 
     /// A random number generator that retrieves randomness straight from
     /// the operating system. Platform sources:
     ///
     /// - Unix-like systems (Linux, Android, Mac OSX): read directly from
-    ///   `/dev/urandom`.
+    ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
     /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
     /// This does not block.
-    #[cfg(unix)]
     pub struct OsRng {
-        inner: ReaderRng<File>
+        inner: OsRngInner,
+    }
+
+    enum OsRngInner {
+        OsGetrandomRng,
+        OsReaderRng(ReaderRng<File>),
     }
 
     impl OsRng {
         /// Create a new `OsRng`.
         pub fn new() -> IoResult<OsRng> {
+            if is_getrandom_available() {
+                return Ok(OsRng { inner: OsGetrandomRng });
+            }
+
             let reader = try!(File::open(&Path::new("/dev/urandom")));
             let reader_rng = ReaderRng::new(reader);
 
-            Ok(OsRng { inner: reader_rng })
+            Ok(OsRng { inner: OsReaderRng(reader_rng) })
         }
     }
 
     impl Rng for OsRng {
         fn next_u32(&mut self) -> u32 {
-            self.inner.next_u32()
+            match self.inner {
+                OsGetrandomRng => getrandom_next_u32(),
+                OsReaderRng(ref mut rng) => rng.next_u32(),
+            }
         }
         fn next_u64(&mut self) -> u64 {
-            self.inner.next_u64()
+            match self.inner {
+                OsGetrandomRng => getrandom_next_u64(),
+                OsReaderRng(ref mut rng) => rng.next_u64(),
+            }
         }
         fn fill_bytes(&mut self, v: &mut [u8]) {
-            self.inner.fill_bytes(v)
+            match self.inner {
+                OsGetrandomRng => getrandom_fill_bytes(v),
+                OsReaderRng(ref mut rng) => rng.fill_bytes(v)
+            }
         }
     }
 }
@@ -75,7 +179,7 @@ mod imp {
     /// the operating system. Platform sources:
     ///
     /// - Unix-like systems (Linux, Android, Mac OSX): read directly from
-    ///   `/dev/urandom`.
+    ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
     /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
@@ -145,10 +249,10 @@ mod imp {
     /// the operating system. Platform sources:
     ///
     /// - Unix-like systems (Linux, Android, Mac OSX): read directly from
-    ///   `/dev/urandom`.
+    ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
-    ///
+    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
     /// This does not block.
     pub struct OsRng {
         hcryptprov: HCRYPTPROV