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]

8 files changed, 31 insertions, 29 deletions

diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs
index 8efc4cd50c1..ed931028446 100644
--- a/src/libcollections/binary_heap.rs
+++ b/src/libcollections/binary_heap.rs
@@ -585,10 +585,10 @@ impl<T> DoubleEndedIterator<T> for MoveItems<T> {
     fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
 }
 
-impl<T> ExactSize<T> for MoveItems<T> {}
+impl<T> ExactSizeIterator<T> for MoveItems<T> {}
 
 impl<T: Ord> FromIterator<T> for BinaryHeap<T> {
-    fn from_iter<Iter: Iterator<T>>(mut iter: Iter) -> BinaryHeap<T> {
+    fn from_iter<Iter: Iterator<T>>(iter: Iter) -> BinaryHeap<T> {
         let vec: Vec<T> = iter.collect();
         BinaryHeap::from_vec(vec)
     }
diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index 64abc78daf3..903a9bd9823 100644
--- a/src/libcollections/bit.rs
+++ b/src/libcollections/bit.rs
@@ -68,7 +68,7 @@ use core::prelude::*;
 use core::cmp;
 use core::default::Default;
 use core::fmt;
-use core::iter::{Chain, Enumerate, Repeat, Skip, Take};
+use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat};
 use core::iter;
 use core::num::Int;
 use core::slice;
@@ -88,11 +88,11 @@ fn match_words <'a,'b>(a: &'a Bitv, b: &'b Bitv) -> (MatchWords<'a>, MatchWords<
 
     // have to uselessly pretend to pad the longer one for type matching
     if a_len < b_len {
-        (a.mask_words(0).chain(Repeat::new(0u32).enumerate().take(b_len).skip(a_len)),
-         b.mask_words(0).chain(Repeat::new(0u32).enumerate().take(0).skip(0)))
+        (a.mask_words(0).chain(repeat(0u32).enumerate().take(b_len).skip(a_len)),
+         b.mask_words(0).chain(repeat(0u32).enumerate().take(0).skip(0)))
     } else {
-        (a.mask_words(0).chain(Repeat::new(0u32).enumerate().take(0).skip(0)),
-         b.mask_words(0).chain(Repeat::new(0u32).enumerate().take(a_len).skip(b_len)))
+        (a.mask_words(0).chain(repeat(0u32).enumerate().take(0).skip(0)),
+         b.mask_words(0).chain(repeat(0u32).enumerate().take(a_len).skip(b_len)))
     }
 }
 
@@ -943,7 +943,7 @@ impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
     }
 }
 
-impl<'a> ExactSize<bool> for Bits<'a> {}
+impl<'a> ExactSizeIterator<bool> for Bits<'a> {}
 
 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
     #[inline]
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index adb9a9ae5bd..8a6d26c26bf 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -863,7 +863,7 @@ impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>>
     // Note that the design of these iterators permits an *arbitrary* initial pair of min and max,
     // making these arbitrary sub-range iterators. However the logic to construct these paths
     // efficiently is fairly involved, so this is a FIXME. The sub-range iterators also wouldn't be
-    // able to accurately predict size, so those iterators can't implement ExactSize.
+    // able to accurately predict size, so those iterators can't implement ExactSizeIterator.
     fn next(&mut self) -> Option<(K, V)> {
         loop {
             // We want the smallest element, so try to get the top of the left stack
@@ -963,7 +963,7 @@ impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
 impl<'a, K, V> DoubleEndedIterator<(&'a K, &'a V)> for Entries<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
 }
-impl<'a, K, V> ExactSize<(&'a K, &'a V)> for Entries<'a, K, V> {}
+impl<'a, K, V> ExactSizeIterator<(&'a K, &'a V)> for Entries<'a, K, V> {}
 
 
 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
@@ -973,7 +973,7 @@ impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
 impl<'a, K, V> DoubleEndedIterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
 }
-impl<'a, K, V> ExactSize<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {}
+impl<'a, K, V> ExactSizeIterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {}
 
 
 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
@@ -983,7 +983,7 @@ impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
 impl<K, V> DoubleEndedIterator<(K, V)> for MoveEntries<K, V> {
     fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() }
 }
-impl<K, V> ExactSize<(K, V)> for MoveEntries<K, V> {}
+impl<K, V> ExactSizeIterator<(K, V)> for MoveEntries<K, V> {}
 
 
 
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index 19216b32ce7..3f95bda663e 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -607,7 +607,7 @@ impl<'a, A> DoubleEndedIterator<&'a A> for Items<'a, A> {
     }
 }
 
-impl<'a, A> ExactSize<&'a A> for Items<'a, A> {}
+impl<'a, A> ExactSizeIterator<&'a A> for Items<'a, A> {}
 
 impl<'a, A> Iterator<&'a mut A> for MutItems<'a, A> {
     #[inline]
@@ -645,7 +645,7 @@ impl<'a, A> DoubleEndedIterator<&'a mut A> for MutItems<'a, A> {
     }
 }
 
-impl<'a, A> ExactSize<&'a mut A> for MutItems<'a, A> {}
+impl<'a, A> ExactSizeIterator<&'a mut A> for MutItems<'a, A> {}
 
 /// Allows mutating a `DList` while iterating.
 pub trait ListInsertion<A> {
diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/ring_buf.rs
index 643b500ec3e..8f0b0d41b03 100644
--- a/src/libcollections/ring_buf.rs
+++ b/src/libcollections/ring_buf.rs
@@ -695,8 +695,7 @@ impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
     }
 }
 
-
-impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
+impl<'a, T> ExactSizeIterator<&'a T> for Items<'a, T> {}
 
 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
     #[inline]
@@ -763,7 +762,7 @@ impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
     }
 }
 
-impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
+impl<'a, T> ExactSizeIterator<&'a mut T> for MutItems<'a, T> {}
 
 impl<A: PartialEq> PartialEq for RingBuf<A> {
     fn eq(&self, other: &RingBuf<A>) -> bool {
@@ -1322,7 +1321,7 @@ mod tests {
         let u: Vec<int> = deq.iter().map(|&x| x).collect();
         assert_eq!(u, v);
 
-        let mut seq = iter::count(0u, 2).take(256);
+        let seq = iter::count(0u, 2).take(256);
         let deq: RingBuf<uint> = seq.collect();
         for (i, &x) in deq.iter().enumerate() {
             assert_eq!(2*i, x);
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index ab5ac5bf9e1..06e1ee0fc0f 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -94,7 +94,7 @@ use core::cmp;
 use core::kinds::Sized;
 use core::mem::size_of;
 use core::mem;
-use core::prelude::{Clone, Greater, Iterator, Less, None, Option};
+use core::prelude::{Clone, Greater, Iterator, IteratorExt, Less, None, Option};
 use core::prelude::{Ord, Ordering, RawPtr, Some, range};
 use core::ptr;
 use core::iter::{range_step, MultiplicativeIterator};
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 7b53fead6b2..ebd30d758f2 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -61,7 +61,7 @@ use core::cmp;
 use core::iter::AdditiveIterator;
 use core::kinds::Sized;
 use core::prelude::{Char, Clone, Eq, Equiv};
-use core::prelude::{Iterator, SlicePrelude, None, Option, Ord, Ordering};
+use core::prelude::{Iterator, IteratorExt, SlicePrelude, None, Option, Ord, Ordering};
 use core::prelude::{PartialEq, PartialOrd, Result, AsSlice, Some, Tuple2};
 use core::prelude::{range};
 
@@ -828,7 +828,7 @@ mod tests {
     use std::cmp::{Equal, Greater, Less, Ord, PartialOrd, Equiv};
     use std::option::{Some, None};
     use std::ptr::RawPtr;
-    use std::iter::{Iterator, DoubleEndedIterator};
+    use std::iter::{Iterator, IteratorExt, DoubleEndedIteratorExt};
 
     use super::*;
     use std::slice::{AsSlice, SlicePrelude};
@@ -2177,12 +2177,15 @@ mod tests {
         let gr_inds = s.grapheme_indices(true).rev().collect::<Vec<(uint, &str)>>();
         let b: &[_] = &[(11, "\r\n"), (6, "ö̲"), (3, "é"), (0u, "a̐")];
         assert_eq!(gr_inds.as_slice(), b);
-        let mut gr_inds = s.grapheme_indices(true);
-        let e1 = gr_inds.size_hint();
-        assert_eq!(e1, (1, Some(13)));
-        let c = gr_inds.count();
-        assert_eq!(c, 4);
-        let e2 = gr_inds.size_hint();
+        let mut gr_inds_iter = s.grapheme_indices(true);
+        {
+            let gr_inds = gr_inds_iter.by_ref();
+            let e1 = gr_inds.size_hint();
+            assert_eq!(e1, (1, Some(13)));
+            let c = gr_inds.count();
+            assert_eq!(c, 4);
+        }
+        let e2 = gr_inds_iter.size_hint();
         assert_eq!(e2, (0, Some(0)));
 
         // make sure the reverse iterator does the right thing with "\n" at beginning of string
@@ -2319,7 +2322,7 @@ mod bench {
     use test::Bencher;
     use test::black_box;
     use super::*;
-    use std::iter::{Iterator, DoubleEndedIterator};
+    use std::iter::{IteratorExt, DoubleEndedIteratorExt};
     use std::str::StrPrelude;
     use std::slice::SlicePrelude;
 
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index ec520a93c1e..acbb28293fd 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1341,7 +1341,7 @@ impl<T> DoubleEndedIterator<T> for MoveItems<T> {
     }
 }
 
-impl<T> ExactSize<T> for MoveItems<T> {}
+impl<T> ExactSizeIterator<T> for MoveItems<T> {}
 
 #[unsafe_destructor]
 impl<T> Drop for MoveItems<T> {