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

6 files changed, 55 insertions, 64 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 9b93066f9fb..512eb6086dd 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -916,33 +916,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> {
@@ -1391,8 +1364,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 62c03389b24..c51fceddd53 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -271,34 +271,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
@@ -850,8 +822,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 cb78fc56bf2..46efd378cc6 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 34a4a773f8e..631e47edb78 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;