rollup merge of #24541: alexcrichton/issue-24538

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

25 files changed, 241 insertions, 289 deletions

diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs
index 3afc34be2ca..554ca3ea539 100644
--- a/src/liballoc/arc.rs
+++ b/src/liballoc/arc.rs
@@ -77,7 +77,6 @@ use core::atomic;
 use core::atomic::Ordering::{Relaxed, Release, Acquire, SeqCst};
 use core::fmt;
 use core::cmp::Ordering;
-use core::default::Default;
 use core::mem::{min_align_of, size_of};
 use core::mem;
 use core::nonzero::NonZero;
diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index 009266c3d2c..7696abd659f 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -55,7 +55,6 @@ use core::prelude::*;
 
 use core::any::Any;
 use core::cmp::Ordering;
-use core::default::Default;
 use core::fmt;
 use core::hash::{self, Hash};
 use core::mem;
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 ef335e31e08..291b66939e5 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};
@@ -471,8 +470,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,
+            }
+        }
     }
 }
 
@@ -1263,35 +1286,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 25f450e53a4..ce0be3029dc 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -14,14 +14,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 rustc_unicode::str as unicode_str;
 use rustc_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 858838a3a4b..bbe7830b423 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};
@@ -557,14 +556,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]
@@ -1728,8 +1719,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 07d783ef46a..d473504d544 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};
@@ -301,35 +300,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
@@ -800,8 +770,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) }
     }
 }
 
diff --git a/src/libcore/hash/mod.rs b/src/libcore/hash/mod.rs
index 553e0c0dfe6..e848a44e01c 100644
--- a/src/libcore/hash/mod.rs
+++ b/src/libcore/hash/mod.rs
@@ -62,7 +62,6 @@
 
 use prelude::*;
 
-use default::Default;
 use mem;
 
 pub use self::sip::SipHasher;
diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs
index 65f790d5d43..be419e2cdad 100644
--- a/src/libcore/hash/sip.rs
+++ b/src/libcore/hash/sip.rs
@@ -13,7 +13,6 @@
 #![allow(deprecated)] // until the next snapshot for inherent wrapping ops
 
 use prelude::*;
-use default::Default;
 use super::Hasher;
 
 /// An implementation of SipHash 2-4.
diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index 4c784a579da..d1bc24bd9ba 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -551,25 +551,6 @@ impl<T> Option<T> {
         IterMut { inner: Item { opt: self.as_mut() } }
     }
 
-    /// Returns a consuming iterator over the possibly contained value.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let x = Some("string");
-    /// let v: Vec<&str> = x.into_iter().collect();
-    /// assert_eq!(v, ["string"]);
-    ///
-    /// let x = None;
-    /// let v: Vec<&str> = x.into_iter().collect();
-    /// assert!(v.is_empty());
-    /// ```
-    #[inline]
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        IntoIter { inner: Item { opt: self } }
-    }
-
     /////////////////////////////////////////////////////////////////////////
     // Boolean operations on the values, eager and lazy
     /////////////////////////////////////////////////////////////////////////
@@ -770,6 +751,30 @@ impl<T> Default for Option<T> {
     fn default() -> Option<T> { None }
 }
 
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> IntoIterator for Option<T> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+
+    /// Returns a consuming iterator over the possibly contained value.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let x = Some("string");
+    /// let v: Vec<&str> = x.into_iter().collect();
+    /// assert_eq!(v, ["string"]);
+    ///
+    /// let x = None;
+    /// let v: Vec<&str> = x.into_iter().collect();
+    /// assert!(v.is_empty());
+    /// ```
+    #[inline]
+    fn into_iter(self) -> IntoIter<T> {
+        IntoIter { inner: Item { opt: self } }
+    }
+}
+
 /////////////////////////////////////////////////////////////////////////////
 // The Option Iterators
 /////////////////////////////////////////////////////////////////////////////
diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs
index e60bc494081..a4d529ad47d 100644
--- a/src/libcore/prelude.rs
+++ b/src/libcore/prelude.rs
@@ -37,11 +37,10 @@ pub use char::CharExt;
 pub use clone::Clone;
 pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 pub use convert::{AsRef, AsMut, Into, From};
+pub use default::Default;
+pub use iter::IntoIterator;
 pub use iter::{Iterator, DoubleEndedIterator, Extend, ExactSizeIterator};
 pub use option::Option::{self, Some, None};
 pub use result::Result::{self, Ok, Err};
 pub use slice::SliceExt;
 pub use str::StrExt;
-
-#[allow(deprecated)] pub use slice::AsSlice;
-#[allow(deprecated)] pub use str::Str;
diff --git a/src/libcore/result.rs b/src/libcore/result.rs
index 03894926293..17edce56e2b 100644
--- a/src/libcore/result.rs
+++ b/src/libcore/result.rs
@@ -547,25 +547,6 @@ impl<T, E> Result<T, E> {
         IterMut { inner: self.as_mut().ok() }
     }
 
-    /// Returns a consuming iterator over the possibly contained value.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let x: Result<u32, &str> = Ok(5);
-    /// let v: Vec<u32> = x.into_iter().collect();
-    /// assert_eq!(v, [5]);
-    ///
-    /// let x: Result<u32, &str> = Err("nothing!");
-    /// let v: Vec<u32> = x.into_iter().collect();
-    /// assert_eq!(v, []);
-    /// ```
-    #[inline]
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<T> {
-        IntoIter { inner: self.ok() }
-    }
-
     ////////////////////////////////////////////////////////////////////////
     // Boolean operations on the values, eager and lazy
     /////////////////////////////////////////////////////////////////////////
@@ -807,6 +788,30 @@ impl<T, E> AsSlice<T> for Result<T, E> {
     }
 }
 
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, E> IntoIterator for Result<T, E> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+
+    /// Returns a consuming iterator over the possibly contained value.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let x: Result<u32, &str> = Ok(5);
+    /// let v: Vec<u32> = x.into_iter().collect();
+    /// assert_eq!(v, [5]);
+    ///
+    /// let x: Result<u32, &str> = Err("nothing!");
+    /// let v: Vec<u32> = x.into_iter().collect();
+    /// assert_eq!(v, []);
+    /// ```
+    #[inline]
+    fn into_iter(self) -> IntoIter<T> {
+        IntoIter { inner: self.ok() }
+    }
+}
+
 /////////////////////////////////////////////////////////////////////////////
 // The Result Iterators
 /////////////////////////////////////////////////////////////////////////////
diff --git a/src/librand/reseeding.rs b/src/librand/reseeding.rs
index 287a23cf1d1..ea084b2816d 100644
--- a/src/librand/reseeding.rs
+++ b/src/librand/reseeding.rs
@@ -14,7 +14,6 @@
 use core::prelude::*;
 
 use {Rng, SeedableRng};
-use core::default::Default;
 
 /// How many bytes of entropy the underling RNG is allowed to generate
 /// before it is reseeded.
@@ -126,7 +125,6 @@ mod test {
 
     use core::iter::{order, repeat};
     use super::{ReseedingRng, ReseedWithDefault};
-    use std::default::Default;
     use {SeedableRng, Rng};
 
     struct Counter {
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index a5bbbee790a..33e609702c4 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -914,33 +914,6 @@ impl<K, V, S> HashMap<K, V, S>
         IterMut { inner: self.table.iter_mut() }
     }
 
-    /// Creates a consuming iterator, that is, one that moves each key-value
-    /// pair out of the map in arbitrary order. The map cannot be used after
-    /// calling this.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// map.insert("a", 1);
-    /// map.insert("b", 2);
-    /// map.insert("c", 3);
-    ///
-    /// // Not possible with .iter()
-    /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
-    /// ```
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_iter(self) -> IntoIter<K, V> {
-        fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
-        let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
-
-        IntoIter {
-            inner: self.table.into_iter().map(last_two)
-        }
-    }
-
     /// Gets the given key's corresponding entry in the map for in-place manipulation.
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn entry(&mut self, key: K) -> Entry<K, V> {
@@ -1388,8 +1361,30 @@ impl<K, V, S> IntoIterator for HashMap<K, V, S>
     type Item = (K, V);
     type IntoIter = IntoIter<K, V>;
 
+    /// Creates a consuming iterator, that is, one that moves each key-value
+    /// pair out of the map in arbitrary order. The map cannot be used after
+    /// calling this.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// map.insert("a", 1);
+    /// map.insert("b", 2);
+    /// map.insert("c", 3);
+    ///
+    /// // Not possible with .iter()
+    /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
+    /// ```
     fn into_iter(self) -> IntoIter<K, V> {
-        self.into_iter()
+        fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
+        let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
+
+        IntoIter {
+            inner: self.table.into_iter().map(last_two)
+        }
     }
 }
 
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 82109900bf2..f7e43b38539 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -269,34 +269,6 @@ impl<T, S> HashSet<T, S>
         Iter { iter: self.map.keys() }
     }
 
-    /// 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.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashSet;
-    /// let mut set = HashSet::new();
-    /// set.insert("a".to_string());
-    /// set.insert("b".to_string());
-    ///
-    /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
-    /// let v: Vec<String> = set.into_iter().collect();
-    ///
-    /// // Will print in an arbitrary order.
-    /// for x in v.iter() {
-    ///     println!("{}", x);
-    /// }
-    /// ```
-    #[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;
-
-        IntoIter { iter: self.map.into_iter().map(first) }
-    }
-
     /// Visit the values representing the difference.
     ///
     /// # Examples
@@ -848,8 +820,31 @@ impl<T, S> IntoIterator for HashSet<T, S>
     type Item = T;
     type IntoIter = IntoIter<T>;
 
+    /// 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.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    /// let mut set = HashSet::new();
+    /// set.insert("a".to_string());
+    /// set.insert("b".to_string());
+    ///
+    /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
+    /// let v: Vec<String> = set.into_iter().collect();
+    ///
+    /// // Will print in an arbitrary order.
+    /// for x in v.iter() {
+    ///     println!("{}", x);
+    /// }
+    /// ```
     fn into_iter(self) -> IntoIter<T> {
-        self.into_iter()
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+        let first: fn((T, ())) -> T = first;
+
+        IntoIter { iter: self.map.into_iter().map(first) }
     }
 }
 
diff --git a/src/libstd/env.rs b/src/libstd/env.rs
index bcc109a71cb..c66be35f3f6 100644
--- a/src/libstd/env.rs
+++ b/src/libstd/env.rs
@@ -18,7 +18,6 @@
 
 use prelude::v1::*;
 
-use iter::IntoIterator;
 use error::Error;
 use ffi::{OsStr, OsString};
 use fmt;
diff --git a/src/libstd/path.rs b/src/libstd/path.rs
index 1ad1508ae2d..26aaa63aabb 100644
--- a/src/libstd/path.rs
+++ b/src/libstd/path.rs
@@ -103,7 +103,7 @@ use core::prelude::*;
 use ascii::*;
 use borrow::{Borrow, IntoCow, ToOwned, Cow};
 use cmp;
-use iter::{self, IntoIterator};
+use iter;
 use mem;
 use ops::{self, Deref};
 use string::String;
diff --git a/src/libstd/prelude/v1.rs b/src/libstd/prelude/v1.rs
index c93fc13284b..6dc11c505a9 100644
--- a/src/libstd/prelude/v1.rs
+++ b/src/libstd/prelude/v1.rs
@@ -26,17 +26,19 @@
 #[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use boxed::Box;
 #[stable(feature = "rust1", since = "1.0.0")]
+#[doc(no_inline)] pub use borrow::ToOwned;
+#[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use clone::Clone;
 #[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
-#[unstable(feature = "convert")]
+#[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use convert::{AsRef, AsMut, Into, From};
 #[stable(feature = "rust1", since = "1.0.0")]
-#[doc(no_inline)] pub use iter::DoubleEndedIterator;
+#[doc(no_inline)] pub use default::Default;
 #[stable(feature = "rust1", since = "1.0.0")]
-#[doc(no_inline)] pub use iter::ExactSizeIterator;
+#[doc(no_inline)] pub use iter::{Iterator, Extend, IntoIterator};
 #[stable(feature = "rust1", since = "1.0.0")]
-#[doc(no_inline)] pub use iter::{Iterator, Extend};
+#[doc(no_inline)] pub use iter::{DoubleEndedIterator, ExactSizeIterator};
 #[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use option::Option::{self, Some, None};
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libstd/sys/common/wtf8.rs b/src/libstd/sys/common/wtf8.rs
index aa035a18437..c44bf08cae7 100644
--- a/src/libstd/sys/common/wtf8.rs
+++ b/src/libstd/sys/common/wtf8.rs
@@ -35,7 +35,7 @@ use borrow::Cow;
 use cmp;
 use fmt;
 use hash::{Hash, Hasher};
-use iter::{FromIterator, IntoIterator};
+use iter::FromIterator;
 use mem;
 #[allow(deprecated)] // Int
 use num::Int;
diff --git a/src/test/run-pass/issue-21245.rs b/src/test/run-pass/issue-21245.rs
index 75d064a00fa..e3340d9767d 100644
--- a/src/test/run-pass/issue-21245.rs
+++ b/src/test/run-pass/issue-21245.rs
@@ -20,19 +20,19 @@ use std::ptr;
 trait IntoIterator {
     type Iter: Iterator;
 
-    fn into_iter(self) -> Self::Iter;
+    fn into_iter2(self) -> Self::Iter;
 }
 
 impl<I> IntoIterator for I where I: Iterator {
     type Iter = I;
 
-    fn into_iter(self) -> I {
+    fn into_iter2(self) -> I {
         self
     }
 }
 
 fn desugared_for_loop_bad<T>(v: Vec<T>) {
-    match IntoIterator::into_iter(v.iter()) {
+    match IntoIterator::into_iter2(v.iter()) {
         mut iter => {
             loop {
                 match ::std::iter::Iterator::next(&mut iter) {