Remove IteratorExt

All methods are inlined into Iterator with `Self: Sized` bounds to make
sure Iterator is still object safe.

[breaking-change]

33 files changed, 130 insertions, 129 deletions

diff --git a/src/libcollections/linked_list.rs b/src/libcollections/linked_list.rs
index 908c78a17f4..5b392c87652 100644
--- a/src/libcollections/linked_list.rs
+++ b/src/libcollections/linked_list.rs
@@ -951,7 +951,7 @@ impl<A: Hash> Hash for LinkedList<A> {
 #[cfg(test)]
 mod test {
     use std::clone::Clone;
-    use std::iter::{Iterator, IteratorExt};
+    use std::iter::Iterator;
     use std::option::Option::{Some, None, self};
     use std::rand;
     use std::thread;
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 83e632e6c96..ba1ab75de80 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -76,7 +76,6 @@
 //!   iterators.
 //! * Further methods that return iterators are `.split()`, `.splitn()`,
 //!   `.chunks()`, `.windows()` and more.
-
 #![doc(primitive = "slice")]
 #![stable(feature = "rust1", since = "1.0.0")]
 
@@ -85,7 +84,7 @@ use core::convert::AsRef;
 use core::clone::Clone;
 use core::cmp::Ordering::{self, Greater, Less};
 use core::cmp::{self, Ord, PartialEq};
-use core::iter::{Iterator, IteratorExt};
+use core::iter::Iterator;
 use core::iter::MultiplicativeIterator;
 use core::marker::Sized;
 use core::mem::size_of;
@@ -131,7 +130,7 @@ mod hack {
     use alloc::boxed::Box;
     use core::clone::Clone;
     #[cfg(test)]
-    use core::iter::{Iterator, IteratorExt};
+    use core::iter::Iterator;
     use core::mem;
     #[cfg(test)]
     use core::option::Option::{Some, None};
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index aaa73badcac..0665abc9e95 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -58,7 +58,7 @@ use self::DecompositionType::*;
 
 use core::clone::Clone;
 use core::iter::AdditiveIterator;
-use core::iter::{Iterator, IteratorExt, Extend};
+use core::iter::{Iterator, Extend};
 use core::option::Option::{self, Some, None};
 use core::result::Result;
 use core::str as core_str;
diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs
index 944908e7b4e..8f3f4e6b890 100644
--- a/src/libcollections/vec_deque.rs
+++ b/src/libcollections/vec_deque.rs
@@ -1785,7 +1785,7 @@ impl<T: fmt::Debug> fmt::Debug for VecDeque<T> {
 
 #[cfg(test)]
 mod test {
-    use core::iter::{IteratorExt, self};
+    use core::iter::{Iterator, self};
     use core::option::Option::Some;
 
     use test;
diff --git a/src/libcollectionstest/bench.rs b/src/libcollectionstest/bench.rs
index 2396a577589..e883b07dc5a 100644
--- a/src/libcollectionstest/bench.rs
+++ b/src/libcollectionstest/bench.rs
@@ -66,7 +66,7 @@ macro_rules! map_find_rand_bench {
     ($name: ident, $n: expr, $map: ident) => (
         #[bench]
         pub fn $name(b: &mut ::test::Bencher) {
-            use std::iter::IteratorExt;
+            use std::iter::Iterator;
             use std::rand::Rng;
             use std::rand;
             use std::vec::Vec;
diff --git a/src/libcore/fmt/float.rs b/src/libcore/fmt/float.rs
index ee2951602c7..6e82b18abc6 100644
--- a/src/libcore/fmt/float.rs
+++ b/src/libcore/fmt/float.rs
@@ -17,7 +17,7 @@ pub use self::SignFormat::*;
 use char;
 use char::CharExt;
 use fmt;
-use iter::IteratorExt;
+use iter::Iterator;
 use num::{cast, Float, ToPrimitive};
 use num::FpCategory as Fp;
 use ops::FnOnce;
diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs
index aa0d0a1539a..a3de23bd7f3 100644
--- a/src/libcore/fmt/mod.rs
+++ b/src/libcore/fmt/mod.rs
@@ -15,7 +15,7 @@
 use any;
 use cell::{Cell, RefCell, Ref, RefMut, BorrowState};
 use char::CharExt;
-use iter::{Iterator, IteratorExt};
+use iter::Iterator;
 use marker::{Copy, PhantomData, Sized};
 use mem;
 use option::Option;
diff --git a/src/libcore/fmt/num.rs b/src/libcore/fmt/num.rs
index 49da99b97cb..974252a92af 100644
--- a/src/libcore/fmt/num.rs
+++ b/src/libcore/fmt/num.rs
@@ -15,7 +15,7 @@
 #![allow(unsigned_negation)]
 
 use fmt;
-use iter::IteratorExt;
+use iter::Iterator;
 use num::{Int, cast};
 use slice::SliceExt;
 use str;
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index da89dda3af1..bb057c553db 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -71,6 +71,8 @@ use option::Option::{Some, None};
 use marker::Sized;
 use usize;
 
+fn _assert_is_object_safe(_: &Iterator) {}
+
 /// An interface for dealing with "external iterators". These types of iterators
 /// can be resumed at any time as all state is stored internally as opposed to
 /// being located on the call stack.
@@ -101,62 +103,7 @@ pub trait Iterator {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
-    type Item = I::Item;
-    fn next(&mut self) -> Option<I::Item> { (**self).next() }
-    fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
-}
-
-/// Conversion from an `Iterator`
-#[stable(feature = "rust1", since = "1.0.0")]
-#[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
-                          built from an iterator over elements of type `{A}`"]
-pub trait FromIterator<A> {
-    /// Build a container with elements from something iterable.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self;
-}
-
-/// Conversion into an `Iterator`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub trait IntoIterator {
-    /// The type of the elements being iterated
-    #[stable(feature = "rust1", since = "1.0.0")]
-    type Item;
-
-    /// A container for iterating over elements of type Item
-    #[stable(feature = "rust1", since = "1.0.0")]
-    type IntoIter: Iterator<Item=Self::Item>;
-
-    /// Consumes `Self` and returns an iterator over it
-    #[stable(feature = "rust1", since = "1.0.0")]
-    fn into_iter(self) -> Self::IntoIter;
-}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator> IntoIterator for I {
-    type Item = I::Item;
-    type IntoIter = I;
-
-    fn into_iter(self) -> I {
-        self
-    }
-}
-
-/// A type growable from an `Iterator` implementation
-#[stable(feature = "rust1", since = "1.0.0")]
-pub trait Extend<A> {
-    /// Extend a container with the elements yielded by an arbitrary iterator
-    #[stable(feature = "rust1", since = "1.0.0")]
-    fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T);
-}
-
-/// An extension trait providing numerous methods applicable to all iterators.
-#[stable(feature = "rust1", since = "1.0.0")]
-pub trait IteratorExt: Iterator + Sized {
     /// Counts the number of elements in this iterator.
     ///
     /// # Examples
@@ -167,7 +114,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn count(self) -> usize {
+    fn count(self) -> usize where Self: Sized {
         self.fold(0, |cnt, _x| cnt + 1)
     }
 
@@ -181,7 +128,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn last(self) -> Option<Self::Item> {
+    fn last(self) -> Option<Self::Item> where Self: Sized {
         let mut last = None;
         for x in self { last = Some(x); }
         last
@@ -200,7 +147,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
+    fn nth(&mut self, mut n: usize) -> Option<Self::Item> where Self: Sized {
         for x in self.by_ref() {
             if n == 0 { return Some(x) }
             n -= 1;
@@ -225,7 +172,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn chain<U>(self, other: U) -> Chain<Self, U> where
-        U: Iterator<Item=Self::Item>,
+        Self: Sized, U: Iterator<Item=Self::Item>,
     {
         Chain{a: self, b: other, flag: false}
     }
@@ -260,7 +207,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// both produce the same output.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn zip<U: Iterator>(self, other: U) -> Zip<Self, U> {
+    fn zip<U: Iterator>(self, other: U) -> Zip<Self, U> where Self: Sized {
         Zip{a: self, b: other}
     }
 
@@ -279,7 +226,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn map<B, F>(self, f: F) -> Map<Self, F> where
-        F: FnMut(Self::Item) -> B,
+        Self: Sized, F: FnMut(Self::Item) -> B,
     {
         Map{iter: self, f: f}
     }
@@ -299,7 +246,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn filter<P>(self, predicate: P) -> Filter<Self, P> where
-        P: FnMut(&Self::Item) -> bool,
+        Self: Sized, P: FnMut(&Self::Item) -> bool,
     {
         Filter{iter: self, predicate: predicate}
     }
@@ -319,7 +266,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
-        F: FnMut(Self::Item) -> Option<B>,
+        Self: Sized, F: FnMut(Self::Item) -> Option<B>,
     {
         FilterMap { iter: self, f: f }
     }
@@ -341,7 +288,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn enumerate(self) -> Enumerate<Self> {
+    fn enumerate(self) -> Enumerate<Self> where Self: Sized {
         Enumerate{iter: self, count: 0}
     }
 
@@ -365,7 +312,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn peekable(self) -> Peekable<Self> {
+    fn peekable(self) -> Peekable<Self> where Self: Sized {
         Peekable{iter: self, peeked: None}
     }
 
@@ -386,7 +333,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
-        P: FnMut(&Self::Item) -> bool,
+        Self: Sized, P: FnMut(&Self::Item) -> bool,
     {
         SkipWhile{iter: self, flag: false, predicate: predicate}
     }
@@ -407,7 +354,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
-        P: FnMut(&Self::Item) -> bool,
+        Self: Sized, P: FnMut(&Self::Item) -> bool,
     {
         TakeWhile{iter: self, flag: false, predicate: predicate}
     }
@@ -426,7 +373,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn skip(self, n: usize) -> Skip<Self> {
+    fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
         Skip{iter: self, n: n}
     }
 
@@ -445,7 +392,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn take(self, n: usize) -> Take<Self> {
+    fn take(self, n: usize) -> Take<Self> where Self: Sized, {
         Take{iter: self, n: n}
     }
 
@@ -472,7 +419,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
-        where F: FnMut(&mut St, Self::Item) -> Option<B>,
+        where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
     {
         Scan{iter: self, f: f, state: initial_state}
     }
@@ -495,7 +442,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
-        where U: Iterator, F: FnMut(Self::Item) -> U,
+        where Self: Sized, U: Iterator, F: FnMut(Self::Item) -> U,
     {
         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
     }
@@ -529,7 +476,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn fuse(self) -> Fuse<Self> {
+    fn fuse(self) -> Fuse<Self> where Self: Sized {
         Fuse{iter: self, done: false}
     }
 
@@ -555,7 +502,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn inspect<F>(self, f: F) -> Inspect<Self, F> where
-        F: FnMut(&Self::Item),
+        Self: Sized, F: FnMut(&Self::Item),
     {
         Inspect{iter: self, f: f}
     }
@@ -575,7 +522,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// assert!(it.next() == Some(5));
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn by_ref(&mut self) -> &mut Self { self }
+    fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
 
     /// Loops through the entire iterator, collecting all of the elements into
     /// a container implementing `FromIterator`.
@@ -590,7 +537,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn collect<B: FromIterator<Self::Item>>(self) -> B {
+    fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
         FromIterator::from_iter(self)
     }
 
@@ -609,6 +556,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[unstable(feature = "core",
                reason = "recently added as part of collections reform")]
     fn partition<B, F>(self, mut f: F) -> (B, B) where
+        Self: Sized,
         B: Default + Extend<Self::Item>,
         F: FnMut(&Self::Item) -> bool
     {
@@ -638,7 +586,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn fold<B, F>(self, init: B, mut f: F) -> B where
-        F: FnMut(B, Self::Item) -> B,
+        Self: Sized, F: FnMut(B, Self::Item) -> B,
     {
         let mut accum = init;
         for x in self {
@@ -658,7 +606,9 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn all<F>(&mut self, mut f: F) -> bool where F: FnMut(Self::Item) -> bool {
+    fn all<F>(&mut self, mut f: F) -> bool where
+        Self: Sized, F: FnMut(Self::Item) -> bool
+    {
         for x in self.by_ref() { if !f(x) { return false; } }
         true
     }
@@ -679,7 +629,10 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn any<F>(&mut self, mut f: F) -> bool where F: FnMut(Self::Item) -> bool {
+    fn any<F>(&mut self, mut f: F) -> bool where
+        Self: Sized,
+        F: FnMut(Self::Item) -> bool
+    {
         for x in self.by_ref() { if f(x) { return true; } }
         false
     }
@@ -699,6 +652,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
+        Self: Sized,
         P: FnMut(&Self::Item) -> bool,
     {
         for x in self.by_ref() {
@@ -722,6 +676,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
+        Self: Sized,
         P: FnMut(Self::Item) -> bool,
     {
         let mut i = 0;
@@ -752,7 +707,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[stable(feature = "rust1", since = "1.0.0")]
     fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
         P: FnMut(Self::Item) -> bool,
-        Self: ExactSizeIterator + DoubleEndedIterator
+        Self: Sized + ExactSizeIterator + DoubleEndedIterator
     {
         let mut i = self.len();
 
@@ -775,7 +730,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn max(self) -> Option<Self::Item> where Self::Item: Ord
+    fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
     {
         self.fold(None, |max, x| {
             match max {
@@ -795,7 +750,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn min(self) -> Option<Self::Item> where Self::Item: Ord
+    fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
     {
         self.fold(None, |min, x| {
             match min {
@@ -837,7 +792,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// assert!(a.iter().min_max() == MinMax(&1, &1));
     /// ```
     #[unstable(feature = "core", reason = "return type may change")]
-    fn min_max(mut self) -> MinMaxResult<Self::Item> where Self::Item: Ord
+    fn min_max(mut self) -> MinMaxResult<Self::Item> where Self: Sized, Self::Item: Ord
     {
         let (mut min, mut max) = match self.next() {
             None => return NoElements,
@@ -897,6 +852,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[unstable(feature = "core",
                reason = "may want to produce an Ordering directly; see #15311")]
     fn max_by<B: Ord, F>(self, mut f: F) -> Option<Self::Item> where
+        Self: Sized,
         F: FnMut(&Self::Item) -> B,
     {
         self.fold(None, |max: Option<(Self::Item, B)>, x| {
@@ -928,6 +884,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[unstable(feature = "core",
                reason = "may want to produce an Ordering directly; see #15311")]
     fn min_by<B: Ord, F>(self, mut f: F) -> Option<Self::Item> where
+        Self: Sized,
         F: FnMut(&Self::Item) -> B,
     {
         self.fold(None, |min: Option<(Self::Item, B)>, x| {
@@ -957,7 +914,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// `std::usize::MAX` elements of the original iterator.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn rev(self) -> Rev<Self> {
+    fn rev(self) -> Rev<Self> where Self: Sized {
         Rev{iter: self}
     }
 
@@ -979,7 +936,7 @@ pub trait IteratorExt: Iterator + Sized {
     fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
         FromA: Default + Extend<A>,
         FromB: Default + Extend<B>,
-        Self: Iterator<Item=(A, B)>,
+        Self: Sized + Iterator<Item=(A, B)>,
     {
         struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>);
         impl<A> Iterator for SizeHint<A> {
@@ -1010,7 +967,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// converting an Iterator<&T> to an Iterator<T>.
     #[stable(feature = "rust1", since = "1.0.0")]
     fn cloned<'a, T: 'a>(self) -> Cloned<Self>
-        where Self: Iterator<Item=&'a T>, T: Clone
+        where Self: Sized + Iterator<Item=&'a T>, T: Clone
     {
         Cloned { it: self }
     }
@@ -1028,7 +985,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    fn cycle(self) -> Cycle<Self> where Self: Clone {
+    fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
         Cycle{orig: self.clone(), iter: self}
     }
 
@@ -1036,7 +993,7 @@ pub trait IteratorExt: Iterator + Sized {
     #[unstable(feature = "core",
                reason = "uncertain about placement or widespread use")]
     fn reverse_in_place<'a, T: 'a>(&mut self) where
-        Self: Iterator<Item=&'a mut T> + DoubleEndedIterator
+        Self: Sized + Iterator<Item=&'a mut T> + DoubleEndedIterator
     {
         loop {
             match (self.next(), self.next_back()) {
@@ -1048,7 +1005,55 @@ pub trait IteratorExt: Iterator + Sized {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<I> IteratorExt for I where I: Iterator {}
+impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
+    type Item = I::Item;
+    fn next(&mut self) -> Option<I::Item> { (**self).next() }
+    fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
+}
+
+/// Conversion from an `Iterator`
+#[stable(feature = "rust1", since = "1.0.0")]
+#[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
+                          built from an iterator over elements of type `{A}`"]
+pub trait FromIterator<A> {
+    /// Build a container with elements from something iterable.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self;
+}
+
+/// Conversion into an `Iterator`
+#[stable(feature = "rust1", since = "1.0.0")]
+pub trait IntoIterator {
+    /// The type of the elements being iterated
+    #[stable(feature = "rust1", since = "1.0.0")]
+    type Item;
+
+    /// A container for iterating over elements of type Item
+    #[stable(feature = "rust1", since = "1.0.0")]
+    type IntoIter: Iterator<Item=Self::Item>;
+
+    /// Consumes `Self` and returns an iterator over it
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn into_iter(self) -> Self::IntoIter;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<I: Iterator> IntoIterator for I {
+    type Item = I::Item;
+    type IntoIter = I;
+
+    fn into_iter(self) -> I {
+        self
+    }
+}
+
+/// A type growable from an `Iterator` implementation
+#[stable(feature = "rust1", since = "1.0.0")]
+pub trait Extend<A> {
+    /// Extend a container with the elements yielded by an arbitrary iterator
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T);
+}
 
 /// A range iterator able to yield elements from both ends
 ///
@@ -1256,7 +1261,7 @@ impl_multiplicative! { usize, 1 }
 impl_multiplicative! { f32,  1.0 }
 impl_multiplicative! { f64,  1.0 }
 
-/// `MinMaxResult` is an enum returned by `min_max`. See `IteratorOrdExt::min_max` for more detail.
+/// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for more detail.
 #[derive(Clone, PartialEq, Debug)]
 #[unstable(feature = "core",
            reason = "unclear whether such a fine-grained result is widely useful")]
diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs
index 745a1213ad5..dc98bb8e603 100644
--- a/src/libcore/num/mod.rs
+++ b/src/libcore/num/mod.rs
@@ -23,7 +23,7 @@ use cmp::{PartialEq, Eq, PartialOrd, Ord};
 use error::Error;
 use fmt;
 use intrinsics;
-use iter::IteratorExt;
+use iter::Iterator;
 use marker::Copy;
 use mem::size_of;
 use ops::{Add, Sub, Mul, Div, Rem, Neg};
diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index b3bb4a980eb..cd82936b0b3 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -149,7 +149,7 @@ use clone::Clone;
 use cmp::{Eq, Ord};
 use default::Default;
 use iter::ExactSizeIterator;
-use iter::{Iterator, IteratorExt, DoubleEndedIterator, FromIterator, IntoIterator};
+use iter::{Iterator, DoubleEndedIterator, FromIterator, IntoIterator};
 use mem;
 use ops::FnOnce;
 use result::Result::{Ok, Err};
diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs
index 424829939b9..448b90c0dbd 100644
--- a/src/libcore/prelude.rs
+++ b/src/libcore/prelude.rs
@@ -37,7 +37,7 @@ pub use char::CharExt;
 pub use clone::Clone;
 pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 pub use convert::{AsRef, AsMut, Into, From};
-pub use iter::{Extend, IteratorExt};
+pub use iter::Extend;
 pub use iter::{Iterator, DoubleEndedIterator};
 pub use iter::{ExactSizeIterator};
 pub use option::Option::{self, Some, None};
diff --git a/src/libcore/result.rs b/src/libcore/result.rs
index c7e166b49be..eff04dd5903 100644
--- a/src/libcore/result.rs
+++ b/src/libcore/result.rs
@@ -243,8 +243,7 @@ use self::Result::{Ok, Err};
 
 use clone::Clone;
 use fmt;
-use iter::{Iterator, IteratorExt, DoubleEndedIterator,
-           FromIterator, ExactSizeIterator, IntoIterator};
+use iter::{Iterator, DoubleEndedIterator, FromIterator, ExactSizeIterator, IntoIterator};
 use ops::{FnMut, FnOnce};
 use option::Option::{self, None, Some};
 #[allow(deprecated)]
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 13075fd5ee9..189cf3d3498 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -25,7 +25,7 @@ use default::Default;
 use error::Error;
 use fmt;
 use iter::ExactSizeIterator;
-use iter::{Map, Iterator, IteratorExt, DoubleEndedIterator};
+use iter::{Map, Iterator, DoubleEndedIterator};
 use marker::Sized;
 use mem;
 #[allow(deprecated)]
@@ -1237,7 +1237,7 @@ Section: Trait implementations
 mod traits {
     use cmp::{Ordering, Ord, PartialEq, PartialOrd, Eq};
     use cmp::Ordering::{Less, Equal, Greater};
-    use iter::IteratorExt;
+    use iter::Iterator;
     use option::Option;
     use option::Option::Some;
     use ops;
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index f9e1cb877b6..9e229a28279 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -20,7 +20,7 @@ use cmp::{max, Eq, PartialEq};
 use default::Default;
 use fmt::{self, Debug};
 use hash::{Hash, SipHasher};
-use iter::{self, Iterator, ExactSizeIterator, IntoIterator, IteratorExt, FromIterator, Extend, Map};
+use iter::{self, Iterator, ExactSizeIterator, IntoIterator, FromIterator, Extend, Map};
 use marker::Sized;
 use mem::{self, replace};
 use ops::{Deref, FnMut, FnOnce, Index};
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 0933b4f662a..34b905595b7 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -18,9 +18,7 @@ use default::Default;
 use fmt::Debug;
 use fmt;
 use hash::Hash;
-use iter::{
-    Iterator, IntoIterator, ExactSizeIterator, IteratorExt, FromIterator, Map, Chain, Extend,
-};
+use iter::{Iterator, IntoIterator, ExactSizeIterator, FromIterator, Map, Chain, Extend};
 use ops::{BitOr, BitAnd, BitXor, Sub};
 use option::Option::{Some, None, self};
 
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 710f0fe19db..8f659334538 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -15,7 +15,7 @@ use self::BucketState::*;
 use clone::Clone;
 use cmp;
 use hash::{Hash, Hasher};
-use iter::{Iterator, IteratorExt, ExactSizeIterator, count};
+use iter::{Iterator, ExactSizeIterator, count};
 use marker::{Copy, Send, Sync, Sized, self};
 use mem::{min_align_of, size_of};
 use mem;
diff --git a/src/libstd/dynamic_lib.rs b/src/libstd/dynamic_lib.rs
index b96fe94dd2e..d8a95133d94 100644
--- a/src/libstd/dynamic_lib.rs
+++ b/src/libstd/dynamic_lib.rs
@@ -261,7 +261,7 @@ mod dl {
 #[cfg(target_os = "windows")]
 mod dl {
     use ffi::OsStr;
-    use iter::IteratorExt;
+    use iter::Iterator;
     use libc;
     use libc::consts::os::extra::ERROR_CALL_NOT_IMPLEMENTED;
     use ops::FnOnce;
diff --git a/src/libstd/ffi/c_str.rs b/src/libstd/ffi/c_str.rs
index 8b19d160172..a00f7708025 100644
--- a/src/libstd/ffi/c_str.rs
+++ b/src/libstd/ffi/c_str.rs
@@ -15,7 +15,7 @@ use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
 use error::{Error, FromError};
 use fmt;
 use io;
-use iter::IteratorExt;
+use iter::Iterator;
 use libc;
 use mem;
 #[allow(deprecated)]
diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs
index 5d62f1341e3..be0b3687bad 100644
--- a/src/libstd/io/mod.rs
+++ b/src/libstd/io/mod.rs
@@ -16,7 +16,7 @@ use cmp;
 use unicode::str as core_str;
 use error as std_error;
 use fmt;
-use iter::{self, Iterator, IteratorExt, Extend};
+use iter::{self, Iterator, Extend};
 use marker::Sized;
 use ops::{Drop, FnOnce};
 use option::Option::{self, Some, None};
diff --git a/src/libstd/old_io/buffered.rs b/src/libstd/old_io/buffered.rs
index 502f414d50b..b8b7df75003 100644
--- a/src/libstd/old_io/buffered.rs
+++ b/src/libstd/old_io/buffered.rs
@@ -15,7 +15,7 @@
 use cmp;
 use fmt;
 use old_io::{Reader, Writer, Stream, Buffer, DEFAULT_BUF_SIZE, IoResult};
-use iter::{IteratorExt, ExactSizeIterator, repeat};
+use iter::{Iterator, ExactSizeIterator, repeat};
 use ops::Drop;
 use option::Option;
 use option::Option::{Some, None};
diff --git a/src/libstd/old_io/mem.rs b/src/libstd/old_io/mem.rs
index 76a448c4aae..5f20c383bb7 100644
--- a/src/libstd/old_io/mem.rs
+++ b/src/libstd/old_io/mem.rs
@@ -400,7 +400,7 @@ mod test {
     extern crate test as test_crate;
     use old_io::{SeekSet, SeekCur, SeekEnd, Reader, Writer, Seek, Buffer};
     use prelude::v1::{Ok, Err, Vec,  AsSlice};
-    use prelude::v1::IteratorExt;
+    use prelude::v1::Iterator;
     use old_io;
     use iter::repeat;
     use self::test_crate::Bencher;
diff --git a/src/libstd/old_io/mod.rs b/src/libstd/old_io/mod.rs
index aaa55c5d1d9..df8ac78f7e5 100644
--- a/src/libstd/old_io/mod.rs
+++ b/src/libstd/old_io/mod.rs
@@ -268,7 +268,7 @@ use default::Default;
 use error::Error;
 use fmt;
 use isize;
-use iter::{Iterator, IteratorExt};
+use iter::Iterator;
 use marker::{PhantomFn, Sized};
 use mem::transmute;
 use ops::FnOnce;
diff --git a/src/libstd/old_io/net/addrinfo.rs b/src/libstd/old_io/net/addrinfo.rs
index 6237bb97f3e..739439ebd15 100644
--- a/src/libstd/old_io/net/addrinfo.rs
+++ b/src/libstd/old_io/net/addrinfo.rs
@@ -19,7 +19,7 @@ pub use self::SocketType::*;
 pub use self::Flag::*;
 pub use self::Protocol::*;
 
-use iter::IteratorExt;
+use iter::Iterator;
 use old_io::IoResult;
 use old_io::net::ip::{SocketAddr, IpAddr};
 use option::Option;
diff --git a/src/libstd/old_io/net/ip.rs b/src/libstd/old_io/net/ip.rs
index ba3578f7425..26e1bb6550b 100644
--- a/src/libstd/old_io/net/ip.rs
+++ b/src/libstd/old_io/net/ip.rs
@@ -21,7 +21,7 @@ use boxed::Box;
 use fmt;
 use old_io::{self, IoResult, IoError};
 use old_io::net;
-use iter::{Iterator, IteratorExt};
+use iter::Iterator;
 use ops::{FnOnce, FnMut};
 use option::Option;
 use option::Option::{None, Some};
diff --git a/src/libstd/old_io/tempfile.rs b/src/libstd/old_io/tempfile.rs
index 572cfa1395d..0a2cc517a06 100644
--- a/src/libstd/old_io/tempfile.rs
+++ b/src/libstd/old_io/tempfile.rs
@@ -12,7 +12,7 @@
 #![allow(deprecated)] // rand
 
 use env;
-use iter::IteratorExt;
+use iter::Iterator;
 use old_io::{fs, IoError, IoErrorKind, IoResult};
 use old_io;
 use ops::Drop;
diff --git a/src/libstd/old_path/mod.rs b/src/libstd/old_path/mod.rs
index 50bda04b5d0..c405df2824e 100644
--- a/src/libstd/old_path/mod.rs
+++ b/src/libstd/old_path/mod.rs
@@ -70,7 +70,7 @@ use core::marker::Sized;
 use ffi::CString;
 use clone::Clone;
 use fmt;
-use iter::IteratorExt;
+use iter::Iterator;
 use option::Option;
 use option::Option::{None, Some};
 use str;
diff --git a/src/libstd/old_path/posix.rs b/src/libstd/old_path/posix.rs
index 67bfe2bd770..bbc1756bee6 100644
--- a/src/libstd/old_path/posix.rs
+++ b/src/libstd/old_path/posix.rs
@@ -16,7 +16,7 @@ use fmt;
 use hash;
 use old_io::Writer;
 use iter::{AdditiveIterator, Extend};
-use iter::{Iterator, IteratorExt, Map};
+use iter::{Iterator, Map};
 use marker::Sized;
 use option::Option::{self, Some, None};
 use result::Result::{self, Ok, Err};
@@ -444,13 +444,13 @@ mod tests {
     use super::*;
 
     use clone::Clone;
-    use iter::IteratorExt;
     use option::Option::{self, Some, None};
     use old_path::GenericPath;
     use slice::AsSlice;
     use str::{self, Str};
     use string::ToString;
     use vec::Vec;
+    use iter::Iterator;
 
     macro_rules! t {
         (s: $path:expr, $exp:expr) => (
diff --git a/src/libstd/old_path/windows.rs b/src/libstd/old_path/windows.rs
index 869a8127301..bd67855bf1b 100644
--- a/src/libstd/old_path/windows.rs
+++ b/src/libstd/old_path/windows.rs
@@ -21,7 +21,7 @@ use fmt;
 use hash;
 use old_io::Writer;
 use iter::{AdditiveIterator, Extend};
-use iter::{Iterator, IteratorExt, Map, repeat};
+use iter::{Iterator, Map, repeat};
 use mem;
 use option::Option::{self, Some, None};
 use result::Result::{self, Ok, Err};
@@ -1126,7 +1126,7 @@ mod tests {
     use super::*;
 
     use clone::Clone;
-    use iter::IteratorExt;
+    use iter::Iterator;
     use option::Option::{self, Some, None};
     use old_path::GenericPath;
     use slice::AsSlice;
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index 2e8521cc94b..e19c734b8a3 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -43,7 +43,7 @@ use env;
 use error::{FromError, Error};
 use ffi::{OsString, OsStr};
 use fmt;
-use iter::{Iterator, IteratorExt};
+use iter::Iterator;
 use libc::{c_void, c_int, c_char};
 use libc;
 use marker::{Copy, Send};
diff --git a/src/libstd/prelude/v1.rs b/src/libstd/prelude/v1.rs
index 6e12ac1a226..611dd85a71b 100644
--- a/src/libstd/prelude/v1.rs
+++ b/src/libstd/prelude/v1.rs
@@ -36,7 +36,7 @@
 #[stable(feature = "rust1", since = "1.0.0")]
 #[doc(no_inline)] pub use iter::ExactSizeIterator;
 #[stable(feature = "rust1", since = "1.0.0")]
-#[doc(no_inline)] pub use iter::{Iterator, IteratorExt, Extend};
+#[doc(no_inline)] pub use iter::{Iterator, Extend};
 #[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/rand/mod.rs b/src/libstd/rand/mod.rs
index cfd4e17c021..fad57323d34 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -231,7 +231,7 @@
 use cell::RefCell;
 use clone::Clone;
 use old_io::IoResult;
-use iter::{Iterator, IteratorExt};
+use iter::Iterator;
 use mem;
 use rc::Rc;
 use result::Result::{Ok, Err};
diff --git a/src/libstd/sys/windows/process2.rs b/src/libstd/sys/windows/process2.rs
index 4c2777459dd..9e9bb86446e 100644
--- a/src/libstd/sys/windows/process2.rs
+++ b/src/libstd/sys/windows/process2.rs
@@ -127,7 +127,7 @@ impl Process {
 
         use env::split_paths;
         use mem;
-        use iter::IteratorExt;
+        use iter::Iterator;
 
         // To have the spawning semantics of unix/windows stay the same, we need to
         // read the *child's* PATH if one is provided. See #15149 for more details.