auto merge of #19176 : aturon/rust/stab-iter, r=alexcrichton

This is an initial pass at stabilizing the `iter` module. The module is
fairly large, but is also pretty polished, so most of the stabilization
leaves things as they are.

Some changes:

* Due to the new object safety rules, various traits needs to be split
  into object-safe traits and extension traits. This includes `Iterator`
  itself. While splitting up the traits adds some complexity, it will
  also increase flexbility: once we have automatic impls of `Trait` for
  trait objects over `Trait`, then things like the iterator adapters
  will all work with trait objects.

* Iterator adapters that use up the entire iterator now take it by
  value, which makes the semantics more clear and helps catch bugs. Due
  to the splitting of Iterator, this does not affect trait objects. If
  the underlying iterator is still desired for some reason, `by_ref` can
  be used. (Note: this change had no fallout in the Rust distro except
  for the useless mut lint.)

* In general, extension traits new and old are following an [in-progress
  convention](rust-lang/rfcs#445). As such, they
  are marked `unstable`.

* As usual, anything involving closures is `unstable` pending unboxed
  closures.

* A few of the more esoteric/underdeveloped iterator forms (like
  `RandomAccessIterator` and `MutableDoubleEndedIterator`, along with
  various unfolds) are left experimental for now.

* The `order` submodule is left `experimental` because it will hopefully
  be replaced by generalized comparison traits.

* "Leaf" iterators (like `Repeat` and `Counter`) are uniformly
  constructed by free fns at the module level. That's because the types
  are not otherwise of any significance (if we had `impl Trait`, you
  wouldn't want to define a type at all).

Closes #17701

Due to renamings and splitting of traits, this is a:

[breaking-change]

19 files changed, 29 insertions, 28 deletions

diff --git a/src/libstd/ascii.rs b/src/libstd/ascii.rs
index 9754e673d38..403ca9d1432 100644
--- a/src/libstd/ascii.rs
+++ b/src/libstd/ascii.rs
@@ -17,7 +17,7 @@
 
 use core::kinds::Sized;
 use fmt;
-use iter::Iterator;
+use iter::IteratorExt;
 use mem;
 use option::{Option, Some, None};
 use slice::{SlicePrelude, AsSlice};
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 662ae913764..9c7967d17bb 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -20,7 +20,7 @@ use cmp::{max, Eq, Equiv, PartialEq};
 use default::Default;
 use fmt::{mod, Show};
 use hash::{Hash, Hasher, RandomSipHasher};
-use iter::{mod, Iterator, FromIterator, Extend};
+use iter::{mod, Iterator, IteratorExt, FromIterator, Extend};
 use kinds::Sized;
 use mem::{mod, replace};
 use num::UnsignedInt;
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 2fbcb464358..f6d526cca39 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -17,7 +17,7 @@ use default::Default;
 use fmt::Show;
 use fmt;
 use hash::{Hash, Hasher, RandomSipHasher};
-use iter::{Iterator, FromIterator, FilterMap, Chain, Repeat, Zip, Extend};
+use iter::{Iterator, IteratorExt, FromIterator, FilterMap, Chain, Repeat, Zip, Extend, repeat};
 use iter;
 use option::{Some, None};
 use result::{Ok, Err};
@@ -262,7 +262,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[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())
+        repeat(other).zip(self.iter())
             .filter_map(|(other, elt)| {
                 if !other.contains(elt) { Some(elt) } else { None }
             })
@@ -314,7 +314,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     #[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())
+        repeat(other).zip(self.iter())
             .filter_map(|(other, elt)| {
                 if other.contains(elt) { Some(elt) } else { None }
             })
diff --git a/src/libstd/dynamic_lib.rs b/src/libstd/dynamic_lib.rs
index 0f119d44485..4b868f6a95b 100644
--- a/src/libstd/dynamic_lib.rs
+++ b/src/libstd/dynamic_lib.rs
@@ -21,7 +21,7 @@ A simple wrapper over the platform's dynamic library facilities
 
 use clone::Clone;
 use c_str::ToCStr;
-use iter::Iterator;
+use iter::IteratorExt;
 use mem;
 use ops::*;
 use option::*;
@@ -280,7 +280,7 @@ pub mod dl {
 #[cfg(target_os = "windows")]
 pub mod dl {
     use c_str::ToCStr;
-    use iter::Iterator;
+    use iter::IteratorExt;
     use libc;
     use os;
     use ptr;
diff --git a/src/libstd/io/buffered.rs b/src/libstd/io/buffered.rs
index 148323762c8..025033a112c 100644
--- a/src/libstd/io/buffered.rs
+++ b/src/libstd/io/buffered.rs
@@ -14,7 +14,7 @@
 
 use cmp;
 use io::{Reader, Writer, Stream, Buffer, DEFAULT_BUF_SIZE, IoResult};
-use iter::ExactSize;
+use iter::ExactSizeIterator;
 use ops::Drop;
 use option::{Some, None, Option};
 use result::{Ok, Err};
diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs
index 681400e9db5..a25674030ae 100644
--- a/src/libstd/io/mod.rs
+++ b/src/libstd/io/mod.rs
@@ -233,7 +233,7 @@ use default::Default;
 use error::{FromError, Error};
 use fmt;
 use int;
-use iter::Iterator;
+use iter::{Iterator, IteratorExt};
 use mem::transmute;
 use ops::{BitOr, BitXor, BitAnd, Sub, Not};
 use option::{Option, Some, None};
diff --git a/src/libstd/io/net/addrinfo.rs b/src/libstd/io/net/addrinfo.rs
index 13f602de03a..d6a48fd39e6 100644
--- a/src/libstd/io/net/addrinfo.rs
+++ b/src/libstd/io/net/addrinfo.rs
@@ -23,7 +23,7 @@ pub use self::SocketType::*;
 pub use self::Flag::*;
 pub use self::Protocol::*;
 
-use iter::Iterator;
+use iter::IteratorExt;
 use io::{IoResult};
 use io::net::ip::{SocketAddr, IpAddr};
 use option::{Option, Some, None};
diff --git a/src/libstd/io/net/ip.rs b/src/libstd/io/net/ip.rs
index d87768a0860..4812e911cc4 100644
--- a/src/libstd/io/net/ip.rs
+++ b/src/libstd/io/net/ip.rs
@@ -20,7 +20,7 @@ pub use self::IpAddr::*;
 use fmt;
 use io::{mod, IoResult, IoError};
 use io::net;
-use iter::Iterator;
+use iter::{Iterator, IteratorExt};
 use option::{Option, None, Some};
 use result::{Ok, Err};
 use str::{FromStr, StrPrelude};
diff --git a/src/libstd/io/net/tcp.rs b/src/libstd/io/net/tcp.rs
index a989be758c3..aa223417591 100644
--- a/src/libstd/io/net/tcp.rs
+++ b/src/libstd/io/net/tcp.rs
@@ -19,7 +19,6 @@
 
 use clone::Clone;
 use io::IoResult;
-use iter::Iterator;
 use result::Err;
 use io::net::ip::{SocketAddr, ToSocketAddr};
 use io::{Reader, Writer, Listener, Acceptor};
diff --git a/src/libstd/io/stdio.rs b/src/libstd/io/stdio.rs
index d450e9f1dce..e6dd20f63fb 100644
--- a/src/libstd/io/stdio.rs
+++ b/src/libstd/io/stdio.rs
@@ -35,7 +35,6 @@ use failure::LOCAL_STDERR;
 use fmt;
 use io::{Reader, Writer, IoResult, IoError, OtherIoError,
          standard_error, EndOfFile, LineBufferedWriter, BufferedReader};
-use iter::Iterator;
 use kinds::Send;
 use libc;
 use mem;
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index 33c9f38da9b..6b5ec983a80 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -39,7 +39,7 @@ use clone::Clone;
 use error::{FromError, Error};
 use fmt;
 use io::{IoResult, IoError};
-use iter::Iterator;
+use iter::{Iterator, IteratorExt};
 use libc::{c_void, c_int};
 use libc;
 use boxed::Box;
diff --git a/src/libstd/path/mod.rs b/src/libstd/path/mod.rs
index ce3440ead40..047fa51b92f 100644
--- a/src/libstd/path/mod.rs
+++ b/src/libstd/path/mod.rs
@@ -71,7 +71,7 @@ use core::kinds::Sized;
 use c_str::CString;
 use clone::Clone;
 use fmt;
-use iter::Iterator;
+use iter::IteratorExt;
 use option::{Option, None, Some};
 use str;
 use str::{CowString, MaybeOwned, Str, StrPrelude};
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index bdce759a1df..cc8fcccf14a 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -15,9 +15,10 @@ use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
 use hash;
 use io::Writer;
-use iter::{DoubleEndedIterator, AdditiveIterator, Extend, Iterator, Map};
-use kinds::Sized;
+use iter::{DoubleEndedIteratorExt, AdditiveIterator, Extend};
+use iter::{Iterator, IteratorExt, Map};
 use option::{Option, None, Some};
+use kinds::Sized;
 use str::{FromStr, Str};
 use str;
 use slice::{CloneSliceAllocPrelude, Splits, AsSlice, VectorVector,
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index fc367710131..6a6551af499 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -20,7 +20,8 @@ use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
 use hash;
 use io::Writer;
-use iter::{AdditiveIterator, DoubleEndedIterator, Extend, Iterator, Map};
+use iter::{AdditiveIterator, DoubleEndedIteratorExt, Extend};
+use iter::{Iterator, IteratorExt, Map};
 use mem;
 use option::{Option, Some, None};
 use slice::{AsSlice, SlicePrelude};
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 756ff1c58f3..590a7894fa7 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -50,7 +50,7 @@
 #[doc(no_inline)] pub use ops::{Fn, FnMut, FnOnce};
 
 // Reexported functions
-#[doc(no_inline)] pub use iter::{range, repeat};
+#[doc(no_inline)] pub use iter::range;
 #[doc(no_inline)] pub use mem::drop;
 #[doc(no_inline)] pub use str::from_str;
 
@@ -65,10 +65,11 @@
 #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 #[doc(no_inline)] pub use cmp::{Ordering, Equiv};
 #[doc(no_inline)] pub use cmp::Ordering::{Less, Equal, Greater};
-#[doc(no_inline)] pub use iter::{FromIterator, Extend, ExactSize};
-#[doc(no_inline)] pub use iter::{Iterator, DoubleEndedIterator};
-#[doc(no_inline)] pub use iter::{RandomAccessIterator, CloneableIterator};
-#[doc(no_inline)] pub use iter::{OrdIterator, MutableDoubleEndedIterator};
+#[doc(no_inline)] pub use iter::{FromIterator, Extend, ExactSizeIterator};
+#[doc(no_inline)] pub use iter::{Iterator, IteratorExt, DoubleEndedIterator};
+#[doc(no_inline)] pub use iter::{DoubleEndedIteratorExt, CloneIteratorExt};
+#[doc(no_inline)] pub use iter::{RandomAccessIterator, IteratorCloneExt};
+#[doc(no_inline)] pub use iter::{IteratorOrdExt, MutableDoubleEndedIterator};
 #[doc(no_inline)] pub use num::{ToPrimitive, FromPrimitive};
 #[doc(no_inline)] pub use boxed::Box;
 #[doc(no_inline)] pub use option::Option;
diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
index f9f9147b107..da690f5d154 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -224,7 +224,7 @@
 use cell::RefCell;
 use clone::Clone;
 use io::IoResult;
-use iter::Iterator;
+use iter::{Iterator, IteratorExt};
 use mem;
 use rc::Rc;
 use result::{Ok, Err};
diff --git a/src/libstd/rt/backtrace.rs b/src/libstd/rt/backtrace.rs
index 81022994387..4f6c1f8a2c6 100644
--- a/src/libstd/rt/backtrace.rs
+++ b/src/libstd/rt/backtrace.rs
@@ -13,7 +13,7 @@
 #![allow(non_camel_case_types)]
 
 use io::{IoResult, Writer};
-use iter::Iterator;
+use iter::{Iterator, IteratorExt};
 use option::{Some, None};
 use os;
 use result::{Ok, Err};
@@ -388,7 +388,7 @@ mod imp {
 
     #[cfg(not(any(target_os = "macos", target_os = "ios")))]
     fn print(w: &mut Writer, idx: int, addr: *mut libc::c_void) -> IoResult<()> {
-        use iter::Iterator;
+        use iter::IteratorExt;
         use os;
         use path::GenericPath;
         use ptr::RawPtr;
diff --git a/src/libstd/sys/windows/c.rs b/src/libstd/sys/windows/c.rs
index b8e9b1dca3a..e46765f25b8 100644
--- a/src/libstd/sys/windows/c.rs
+++ b/src/libstd/sys/windows/c.rs
@@ -131,7 +131,7 @@ extern "system" {
 
 pub mod compat {
     use intrinsics::{atomic_store_relaxed, transmute};
-    use iter::Iterator;
+    use iter::IteratorExt;
     use libc::types::os::arch::extra::{LPCWSTR, HMODULE, LPCSTR, LPVOID};
     use prelude::*;
 
diff --git a/src/libstd/sys/windows/process.rs b/src/libstd/sys/windows/process.rs
index eddb89c673d..7d0151a7b6b 100644
--- a/src/libstd/sys/windows/process.rs
+++ b/src/libstd/sys/windows/process.rs
@@ -124,7 +124,7 @@ impl Process {
         use libc::funcs::extra::msvcrt::get_osfhandle;
 
         use mem;
-        use iter::Iterator;
+        use iter::{Iterator, IteratorExt};
         use str::StrPrelude;
 
         if cfg.gid().is_some() || cfg.uid().is_some() {