Auto merge of #22541 - Manishearth:rollup, r=Gankro 1.0.0-alpha.2

Continued from #22520

1 files changed, 38 insertions, 19 deletions

diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 747211e9238..7823f536c7a 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -19,7 +19,6 @@ use self::Entry::*;
 
 use core::prelude::*;
 
-use core::borrow::BorrowFrom;
 use core::cmp::Ordering;
 use core::default::Default;
 use core::fmt::Debug;
@@ -29,7 +28,8 @@ use core::ops::{Index, IndexMut};
 use core::{iter, fmt, mem};
 use Bound::{self, Included, Excluded, Unbounded};
 
-use ring_buf::RingBuf;
+use borrow::Borrow;
+use vec_deque::VecDeque;
 
 use self::Continuation::{Continue, Finished};
 use self::StackOp::*;
@@ -75,7 +75,7 @@ pub struct BTreeMap<K, V> {
 
 /// An abstract base over-which all other BTree iterators are built.
 struct AbsIter<T> {
-    traversals: RingBuf<T>,
+    traversals: VecDeque<T>,
     size: usize,
 }
 
@@ -208,7 +208,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.get(&2), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord {
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
         let mut cur_node = &self.root;
         loop {
             match Node::search(cur_node, key) {
@@ -240,7 +240,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord {
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
         self.get(key).is_some()
     }
 
@@ -264,7 +264,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     // See `get` for implementation notes, this is basically a copy-paste with mut's added
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord {
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
         // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
         let mut temp_node = &mut self.root;
         loop {
@@ -434,7 +434,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.remove(&1), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord {
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
         // See `swap` for a more thorough description of the stuff going on in here
         let mut stack = stack::PartialSearchStack::new(self);
         loop {
@@ -512,13 +512,22 @@ mod stack {
     use super::super::node::handle;
     use vec::Vec;
 
+    struct InvariantLifetime<'id>(
+        marker::PhantomData<::core::cell::Cell<&'id ()>>);
+
+    impl<'id> InvariantLifetime<'id> {
+        fn new() -> InvariantLifetime<'id> {
+            InvariantLifetime(marker::PhantomData)
+        }
+    }
+
     /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
     /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
     /// with the exact requested lifetime can be used. This is in contrast to normal references,
     /// where `&'static` can be used in any function expecting any lifetime reference.
     pub struct IdRef<'id, T: 'id> {
         inner: &'id mut T,
-        marker: marker::InvariantLifetime<'id>
+        _marker: InvariantLifetime<'id>,
     }
 
     impl<'id, T> Deref for IdRef<'id, T> {
@@ -560,7 +569,7 @@ mod stack {
     pub struct Pusher<'id, 'a, K:'a, V:'a> {
         map: &'a mut BTreeMap<K, V>,
         stack: Stack<K, V>,
-        marker: marker::InvariantLifetime<'id>
+        _marker: InvariantLifetime<'id>,
     }
 
     impl<'a, K, V> PartialSearchStack<'a, K, V> {
@@ -595,11 +604,11 @@ mod stack {
             let pusher = Pusher {
                 map: self.map,
                 stack: self.stack,
-                marker: marker::InvariantLifetime
+                _marker: InvariantLifetime::new(),
             };
             let node = IdRef {
                 inner: unsafe { &mut *self.next },
-                marker: marker::InvariantLifetime
+                _marker: InvariantLifetime::new(),
             };
 
             closure(pusher, node)
@@ -826,7 +835,7 @@ mod stack {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
-    fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
+    fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
         let mut map = BTreeMap::new();
         map.extend(iter);
         map
@@ -836,13 +845,14 @@ impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
     #[inline]
-    fn extend<T: Iterator<Item=(K, V)>>(&mut self, iter: T) {
+    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
         for (k, v) in iter {
             self.insert(k, v);
         }
     }
 }
 
+#[cfg(stage0)]
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
     fn hash(&self, state: &mut S) {
@@ -851,6 +861,15 @@ impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
         }
     }
 }
+#[cfg(not(stage0))]
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        for elt in self {
+            elt.hash(state);
+        }
+    }
+}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, V> Default for BTreeMap<K, V> {
@@ -903,7 +922,7 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
-    where Q: BorrowFrom<K> + Ord
+    where K: Borrow<Q>, Q: Ord
 {
     type Output = V;
 
@@ -914,7 +933,7 @@ impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V>
-    where Q: BorrowFrom<K> + Ord
+    where K: Borrow<Q>, Q: Ord
 {
     fn index_mut(&mut self, key: &Q) -> &mut V {
         self.get_mut(key).expect("no entry found for key")
@@ -1189,7 +1208,7 @@ impl<K, V> BTreeMap<K, V> {
     pub fn iter(&self) -> Iter<K, V> {
         let len = self.len();
         // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(&self.root));
         Iter {
             inner: AbsIter {
@@ -1221,7 +1240,7 @@ impl<K, V> BTreeMap<K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<K, V> {
         let len = self.len();
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(&mut self.root));
         IterMut {
             inner: AbsIter {
@@ -1250,7 +1269,7 @@ impl<K, V> BTreeMap<K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn into_iter(self) -> IntoIter<K, V> {
         let len = self.len();
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(self.root));
         IntoIter {
             inner: AbsIter {
@@ -1342,7 +1361,7 @@ macro_rules! range_impl {
             // A deque that encodes two search paths containing (left-to-right):
             // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
             // and a series of truncated-from-the-right iterators.
-            let mut traversals = RingBuf::new();
+            let mut traversals = VecDeque::new();
             let (root, min, max) = ($root, $min, $max);
 
             let mut leftmost = None;