std: Add Default/IntoIterator/ToOwned to the prelude

This is an implementation of [RFC 1030][rfc] which adds these traits to the
prelude and additionally removes all inherent `into_iter` methods on collections
in favor of the trait implementation (which is now accessible by default).

[rfc]: https://github.com/rust-lang/rfcs/pull/1030

This is technically a breaking change due to the prelude additions and removal
of inherent methods, but it is expected that essentially no code breaks in
practice.

[breaking-change]
Closes #24538

10 files changed, 133 insertions, 175 deletions

diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs
index 3804874a650..0f05e5796aa 100644
--- a/src/libcollections/binary_heap.rs
+++ b/src/libcollections/binary_heap.rs
@@ -152,8 +152,7 @@
 
 use core::prelude::*;
 
-use core::default::Default;
-use core::iter::{FromIterator, IntoIterator};
+use core::iter::{FromIterator};
 use core::mem::{zeroed, replace, swap};
 use core::ptr;
 
@@ -250,28 +249,6 @@ impl<T: Ord> BinaryHeap<T> {
         Iter { iter: self.data.iter() }
     }
 
-    /// Creates a consuming iterator, that is, one that moves each value out of
-    /// the binary heap in arbitrary order. The binary heap cannot be used
-    /// after calling this.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// # #![feature(collections)]
-    /// use std::collections::BinaryHeap;
-    /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4]);
-    ///
-    /// // Print 1, 2, 3, 4 in arbitrary order
-    /// for x in heap.into_iter() {
-    ///     // x has type i32, not &i32
-    ///     println!("{}", x);
-    /// }
-    /// ```
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        IntoIter { iter: self.data.into_iter() }
-    }
-
     /// Returns the greatest item in the binary heap, or `None` if it is empty.
     ///
     /// # Examples
@@ -675,8 +652,25 @@ impl<T: Ord> IntoIterator for BinaryHeap<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// Creates a consuming iterator, that is, one that moves each value out of
+    /// the binary heap in arbitrary order. The binary heap cannot be used
+    /// after calling this.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(collections)]
+    /// use std::collections::BinaryHeap;
+    /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4]);
+    ///
+    /// // Print 1, 2, 3, 4 in arbitrary order
+    /// for x in heap.into_iter() {
+    ///     // x has type i32, not &i32
+    ///     println!("{}", x);
+    /// }
+    /// ```
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        IntoIter { iter: self.data.into_iter() }
     }
 }
 
diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index d12b979e084..a72f628e10d 100644
--- a/src/libcollections/bit.rs
+++ b/src/libcollections/bit.rs
@@ -85,12 +85,11 @@ use core::prelude::*;
 
 use core::cmp::Ordering;
 use core::cmp;
-use core::default::Default;
 use core::fmt;
 use core::hash;
 use core::iter::RandomAccessIterator;
 use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned};
-use core::iter::{self, FromIterator, IntoIterator};
+use core::iter::{self, FromIterator};
 use core::ops::Index;
 use core::slice;
 use core::{u8, u32, usize};
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 859d5ea99bf..bd4028db42e 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -20,10 +20,9 @@ use self::Entry::*;
 use core::prelude::*;
 
 use core::cmp::Ordering;
-use core::default::Default;
 use core::fmt::Debug;
 use core::hash::{Hash, Hasher};
-use core::iter::{Map, FromIterator, IntoIterator};
+use core::iter::{Map, FromIterator};
 use core::ops::Index;
 use core::{iter, fmt, mem, usize};
 use Bound::{self, Included, Excluded, Unbounded};
@@ -472,8 +471,32 @@ impl<K, V> IntoIterator for BTreeMap<K, V> {
     type Item = (K, V);
     type IntoIter = IntoIter<K, V>;
 
+    /// Gets an owning iterator over the entries of the map.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// map.insert(2, "b");
+    /// map.insert(3, "c");
+    ///
+    /// for (key, value) in map.into_iter() {
+    ///     println!("{}: {}", key, value);
+    /// }
+    /// ```
     fn into_iter(self) -> IntoIter<K, V> {
-        self.into_iter()
+        let len = self.len();
+        let mut lca = VecDeque::new();
+        lca.push_back(Traverse::traverse(self.root));
+        IntoIter {
+            inner: AbsIter {
+                traversals: lca,
+                size: len,
+            }
+        }
     }
 }
 
@@ -1264,35 +1287,6 @@ impl<K, V> BTreeMap<K, V> {
         }
     }
 
-    /// Gets an owning iterator over the entries of the map.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::BTreeMap;
-    ///
-    /// let mut map = BTreeMap::new();
-    /// map.insert(1, "a");
-    /// map.insert(2, "b");
-    /// map.insert(3, "c");
-    ///
-    /// for (key, value) in map.into_iter() {
-    ///     println!("{}: {}", key, value);
-    /// }
-    /// ```
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<K, V> {
-        let len = self.len();
-        let mut lca = VecDeque::new();
-        lca.push_back(Traverse::traverse(self.root));
-        IntoIter {
-            inner: AbsIter {
-                traversals: lca,
-                size: len,
-            }
-        }
-    }
-
     /// Gets an iterator over the keys of the map.
     ///
     /// # Examples
diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs
index 1abd56fd145..fc346151e0b 100644
--- a/src/libcollections/btree/set.rs
+++ b/src/libcollections/btree/set.rs
@@ -14,10 +14,9 @@
 use core::prelude::*;
 
 use core::cmp::Ordering::{self, Less, Greater, Equal};
-use core::default::Default;
 use core::fmt::Debug;
 use core::fmt;
-use core::iter::{Peekable, Map, FromIterator, IntoIterator};
+use core::iter::{Peekable, Map, FromIterator};
 use core::ops::{BitOr, BitAnd, BitXor, Sub};
 
 use borrow::Borrow;
@@ -132,27 +131,6 @@ impl<T> BTreeSet<T> {
     pub fn iter(&self) -> Iter<T> {
         Iter { iter: self.map.keys() }
     }
-
-    /// Gets an iterator for moving out the BtreeSet's contents.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// # #![feature(core)]
-    /// use std::collections::BTreeSet;
-    ///
-    /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
-    ///
-    /// let v: Vec<usize> = set.into_iter().collect();
-    /// assert_eq!(v, [1, 2, 3, 4]);
-    /// ```
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        fn first<A, B>((a, _): (A, B)) -> A { a }
-        let first: fn((T, ())) -> T = first; // coerce to fn pointer
-
-        IntoIter { iter: self.map.into_iter().map(first) }
-    }
 }
 
 impl<T: Ord> BTreeSet<T> {
@@ -500,8 +478,24 @@ impl<T> IntoIterator for BTreeSet<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// Gets an iterator for moving out the BtreeSet's contents.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(core)]
+    /// use std::collections::BTreeSet;
+    ///
+    /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
+    ///
+    /// let v: Vec<usize> = set.into_iter().collect();
+    /// assert_eq!(v, [1, 2, 3, 4]);
+    /// ```
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+        let first: fn((T, ())) -> T = first; // coerce to fn pointer
+
+        IntoIter { iter: self.map.into_iter().map(first) }
     }
 }
 
diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs
index a3a266669b1..e6cdb88d3e1 100644
--- a/src/libcollections/enum_set.rs
+++ b/src/libcollections/enum_set.rs
@@ -16,7 +16,7 @@
 use core::prelude::*;
 use core::marker;
 use core::fmt;
-use core::iter::{FromIterator, IntoIterator};
+use core::iter::{FromIterator};
 use core::ops::{Sub, BitOr, BitAnd, BitXor};
 
 // FIXME(contentions): implement union family of methods? (general design may be wrong here)
diff --git a/src/libcollections/linked_list.rs b/src/libcollections/linked_list.rs
index 391439bcdf2..deb1476c23f 100644
--- a/src/libcollections/linked_list.rs
+++ b/src/libcollections/linked_list.rs
@@ -25,10 +25,9 @@ use core::prelude::*;
 
 use alloc::boxed::Box;
 use core::cmp::Ordering;
-use core::default::Default;
 use core::fmt;
 use core::hash::{Hasher, Hash};
-use core::iter::{self, FromIterator, IntoIterator};
+use core::iter::{self, FromIterator};
 use core::mem;
 use core::ptr;
 
@@ -296,13 +295,6 @@ impl<T> LinkedList<T> {
         }
     }
 
-    /// Consumes the list into an iterator yielding elements by value.
-    #[inline]
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        IntoIter{list: self}
-    }
-
     /// Returns `true` if the `LinkedList` is empty.
     ///
     /// This operation should compute in O(1) time.
@@ -852,8 +844,10 @@ impl<T> IntoIterator for LinkedList<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// Consumes the list into an iterator yielding elements by value.
+    #[inline]
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        IntoIter{list: self}
     }
 }
 
@@ -941,7 +935,7 @@ impl<A: Hash> Hash for LinkedList<A> {
 #[cfg(test)]
 mod test {
     use std::clone::Clone;
-    use std::iter::Iterator;
+    use std::iter::{Iterator, IntoIterator};
     use std::option::Option::{Some, None, self};
     use std::__rand::{thread_rng, Rng};
     use std::thread;
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index 51ce5564c49..864801ab0b7 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -16,14 +16,14 @@
 
 use core::prelude::*;
 
-use core::default::Default;
 use core::fmt;
 use core::hash;
-use core::iter::{IntoIterator, FromIterator};
+use core::iter::FromIterator;
 use core::mem;
 use core::ops::{self, Deref, Add, Index};
 use core::ptr;
 use core::slice;
+#[allow(deprecated)] use core::str::Str;
 use core::str::pattern::Pattern;
 use unicode::str as unicode_str;
 use unicode::str::Utf16Item;
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 4fa91a6a16a..3e08096e166 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -53,18 +53,17 @@ use alloc::boxed::Box;
 use alloc::heap::{EMPTY, allocate, reallocate, deallocate};
 use core::cmp::max;
 use core::cmp::Ordering;
-use core::default::Default;
 use core::fmt;
 use core::hash::{self, Hash};
 use core::intrinsics::assume;
-use core::iter::{repeat, FromIterator, IntoIterator};
+use core::iter::{repeat, FromIterator};
 use core::marker::PhantomData;
 use core::mem;
 use core::ops::{Index, IndexMut, Deref, Add};
 use core::ops;
 use core::ptr;
 use core::ptr::Unique;
-use core::slice;
+use core::slice::{self, AsSlice};
 use core::isize;
 use core::usize;
 
@@ -450,37 +449,6 @@ impl<T> Vec<T> {
         &mut self[..]
     }
 
-    /// Creates a consuming iterator, that is, one that moves each value out of
-    /// the vector (from start to end). The vector cannot be used after calling
-    /// this.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let v = vec!["a".to_string(), "b".to_string()];
-    /// for s in v.into_iter() {
-    ///     // s has type String, not &String
-    ///     println!("{}", s);
-    /// }
-    /// ```
-    #[inline]
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        unsafe {
-            let ptr = *self.ptr;
-            assume(!ptr.is_null());
-            let cap = self.cap;
-            let begin = ptr as *const T;
-            let end = if mem::size_of::<T>() == 0 {
-                (ptr as usize + self.len()) as *const T
-            } else {
-                ptr.offset(self.len() as isize) as *const T
-            };
-            mem::forget(self);
-            IntoIter { allocation: ptr, cap: cap, ptr: begin, end: end }
-        }
-    }
-
     /// Sets the length of a vector.
     ///
     /// This will explicitly set the size of the vector, without actually
@@ -1512,8 +1480,34 @@ impl<T> IntoIterator for Vec<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// Creates a consuming iterator, that is, one that moves each value out of
+    /// the vector (from start to end). The vector cannot be used after calling
+    /// this.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let v = vec!["a".to_string(), "b".to_string()];
+    /// for s in v.into_iter() {
+    ///     // s has type String, not &String
+    ///     println!("{}", s);
+    /// }
+    /// ```
+    #[inline]
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        unsafe {
+            let ptr = *self.ptr;
+            assume(!ptr.is_null());
+            let cap = self.cap;
+            let begin = ptr as *const T;
+            let end = if mem::size_of::<T>() == 0 {
+                (ptr as usize + self.len()) as *const T
+            } else {
+                ptr.offset(self.len() as isize) as *const T
+            };
+            mem::forget(self);
+            IntoIter { allocation: ptr, cap: cap, ptr: begin, end: end }
+        }
     }
 }
 
diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs
index a66cde81c8b..fcb06b5631a 100644
--- a/src/libcollections/vec_deque.rs
+++ b/src/libcollections/vec_deque.rs
@@ -21,9 +21,8 @@
 use core::prelude::*;
 
 use core::cmp::Ordering;
-use core::default::Default;
 use core::fmt;
-use core::iter::{self, repeat, FromIterator, IntoIterator, RandomAccessIterator};
+use core::iter::{self, repeat, FromIterator, RandomAccessIterator};
 use core::mem;
 use core::ops::{Index, IndexMut};
 use core::ptr::{self, Unique};
@@ -560,14 +559,6 @@ impl<T> VecDeque<T> {
         }
     }
 
-    /// Consumes the list into a front-to-back iterator yielding elements by value.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        IntoIter {
-            inner: self,
-        }
-    }
-
     /// Returns a pair of slices which contain, in order, the contents of the
     /// `VecDeque`.
     #[inline]
@@ -1731,8 +1722,12 @@ impl<T> IntoIterator for VecDeque<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// Consumes the list into a front-to-back iterator yielding elements by
+    /// value.
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        IntoIter {
+            inner: self,
+        }
     }
 }
 
diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs
index cb86e4ab38d..d9cffc74ddd 100644
--- a/src/libcollections/vec_map.rs
+++ b/src/libcollections/vec_map.rs
@@ -18,10 +18,9 @@ use self::Entry::*;
 use core::prelude::*;
 
 use core::cmp::{max, Ordering};
-use core::default::Default;
 use core::fmt;
 use core::hash::{Hash, Hasher};
-use core::iter::{Enumerate, FilterMap, Map, FromIterator, IntoIterator};
+use core::iter::{Enumerate, FilterMap, Map, FromIterator};
 use core::iter;
 use core::mem::{replace, swap};
 use core::ops::{Index, IndexMut};
@@ -302,35 +301,6 @@ impl<V> VecMap<V> {
         }
     }
 
-    /// Returns an iterator visiting all key-value pairs in ascending order of
-    /// the keys, consuming the original `VecMap`.
-    /// The iterator's element type is `(usize, &'r V)`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// # #![feature(collections)]
-    /// use std::collections::VecMap;
-    ///
-    /// let mut map = VecMap::new();
-    /// map.insert(1, "a");
-    /// map.insert(3, "c");
-    /// map.insert(2, "b");
-    ///
-    /// let vec: Vec<(usize, &str)> = map.into_iter().collect();
-    ///
-    /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
-    /// ```
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<V> {
-        fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
-            v.map(|v| (i, v))
-        }
-        let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
-
-        IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
-    }
-
     /// Moves all elements from `other` into the map while overwriting existing keys.
     ///
     /// # Examples
@@ -802,8 +772,32 @@ impl<T> IntoIterator for VecMap<T> {
     type Item = (usize, T);
     type IntoIter = IntoIter<T>;
 
+    /// Returns an iterator visiting all key-value pairs in ascending order of
+    /// the keys, consuming the original `VecMap`.
+    /// The iterator's element type is `(usize, &'r V)`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(collections)]
+    /// use std::collections::VecMap;
+    ///
+    /// let mut map = VecMap::new();
+    /// map.insert(1, "a");
+    /// map.insert(3, "c");
+    /// map.insert(2, "b");
+    ///
+    /// let vec: Vec<(usize, &str)> = map.into_iter().collect();
+    ///
+    /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
+    /// ```
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
+            v.map(|v| (i, v))
+        }
+        let filter: fn((usize, Option<T>)) -> Option<(usize, T)> = filter; // coerce to fn ptr
+
+        IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
     }
 }