std: Remove extra type params on iter adaptors

Now that associated types are fully implemented the iterator adaptors only need
type parameters which are associated with actual storage. All other type
parameters can either be derived from these (e.g. they are an associated type)
or can be bare on the `impl` block itself.

This is a breaking change due to the removal of type parameters on these
iterator adaptors, but code can fairly easily migrate by just deleting the
relevant type parameters for each adaptor. Other behavior should not be
affected.

Closes #21839
[breaking-change]

12 files changed, 137 insertions, 290 deletions

diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index ce5e8f07be1..b007f275980 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -116,13 +116,13 @@ pub struct IntoIter<K, V> {
 /// An iterator over a BTreeMap's keys.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Keys<'a, K: 'a, V: 'a> {
-    inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
+    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
 }
 
 /// An iterator over a BTreeMap's values.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Values<'a, K: 'a, V: 'a> {
-    inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
+    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
 }
 
 /// An iterator over a sub-range of BTreeMap's entries.
diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs
index 72d5bf6d799..1445db12a90 100644
--- a/src/libcollections/btree/set.rs
+++ b/src/libcollections/btree/set.rs
@@ -45,40 +45,40 @@ pub struct Iter<'a, T: 'a> {
 /// An owning iterator over a BTreeSet's items.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<T> {
-    iter: Map<(T, ()), T, ::btree_map::IntoIter<T, ()>, fn((T, ())) -> T>
+    iter: Map<::btree_map::IntoIter<T, ()>, fn((T, ())) -> T>
 }
 
 /// An iterator over a sub-range of BTreeSet's items.
 pub struct Range<'a, T: 'a> {
-    iter: Map<(&'a T, &'a ()), &'a T, ::btree_map::Range<'a, T, ()>, fn((&'a T, &'a ())) -> &'a T>
+    iter: Map<::btree_map::Range<'a, T, ()>, fn((&'a T, &'a ())) -> &'a T>
 }
 
 /// A lazy iterator producing elements in the set difference (in-order).
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Difference<'a, T:'a> {
-    a: Peekable<&'a T, Iter<'a, T>>,
-    b: Peekable<&'a T, Iter<'a, T>>,
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
 }
 
 /// A lazy iterator producing elements in the set symmetric difference (in-order).
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct SymmetricDifference<'a, T:'a> {
-    a: Peekable<&'a T, Iter<'a, T>>,
-    b: Peekable<&'a T, Iter<'a, T>>,
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
 }
 
 /// A lazy iterator producing elements in the set intersection (in-order).
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Intersection<'a, T:'a> {
-    a: Peekable<&'a T, Iter<'a, T>>,
-    b: Peekable<&'a T, Iter<'a, T>>,
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
 }
 
 /// A lazy iterator producing elements in the set union (in-order).
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Union<'a, T:'a> {
-    a: Peekable<&'a T, Iter<'a, T>>,
-    b: Peekable<&'a T, Iter<'a, T>>,
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
 }
 
 impl<T: Ord> BTreeSet<T> {
diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs
index f2a9bb4392c..b677b361300 100644
--- a/src/libcollections/vec_map.rs
+++ b/src/libcollections/vec_map.rs
@@ -687,7 +687,7 @@ double_ended_iterator! { impl IterMut -> (uint, &'a mut V), as_mut }
 /// An iterator over the keys of a map.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Keys<'a, V: 'a> {
-    iter: Map<(uint, &'a V), uint, Iter<'a, V>, fn((uint, &'a V)) -> uint>
+    iter: Map<Iter<'a, V>, fn((uint, &'a V)) -> uint>
 }
 
 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
@@ -702,7 +702,7 @@ impl<'a, V> Clone for Keys<'a, V> {
 /// An iterator over the values of a map.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Values<'a, V: 'a> {
-    iter: Map<(uint, &'a V), &'a V, Iter<'a, V>, fn((uint, &'a V)) -> &'a V>
+    iter: Map<Iter<'a, V>, fn((uint, &'a V)) -> &'a V>
 }
 
 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
@@ -718,8 +718,6 @@ impl<'a, V> Clone for Values<'a, V> {
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<V> {
     iter: FilterMap<
-    (uint, Option<V>),
-    (uint, V),
     Enumerate<vec::IntoIter<Option<V>>>,
     fn((uint, Option<V>)) -> Option<(uint, V)>>
 }
@@ -727,8 +725,6 @@ pub struct IntoIter<V> {
 #[unstable(feature = "collections")]
 pub struct Drain<'a, V> {
     iter: FilterMap<
-    (uint, Option<V>),
-    (uint, V),
     Enumerate<vec::Drain<'a, Option<V>>>,
     fn((uint, Option<V>)) -> Option<(uint, V)>>
 }
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 751b5959d8b..84db07266b8 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -239,9 +239,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn zip<B, U>(self, other: U) -> Zip<Self, U> where
-        U: Iterator<Item=B>,
-    {
+    fn zip<U: Iterator>(self, other: U) -> Zip<Self, U> {
         Zip{a: self, b: other}
     }
 
@@ -259,7 +257,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn map<B, F>(self, f: F) -> Map<Self::Item, B, Self, F> where
+    fn map<B, F>(self, f: F) -> Map<Self, F> where
         F: FnMut(Self::Item) -> B,
     {
         Map{iter: self, f: f}
@@ -279,7 +277,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn filter<P>(self, predicate: P) -> Filter<Self::Item, Self, P> where
+    fn filter<P>(self, predicate: P) -> Filter<Self, P> where
         P: FnMut(&Self::Item) -> bool,
     {
         Filter{iter: self, predicate: predicate}
@@ -299,7 +297,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn filter_map<B, F>(self, f: F) -> FilterMap<Self::Item, B, Self, F> where
+    fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
         F: FnMut(Self::Item) -> Option<B>,
     {
         FilterMap { iter: self, f: f }
@@ -342,7 +340,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn peekable(self) -> Peekable<Self::Item, Self> {
+    fn peekable(self) -> Peekable<Self> {
         Peekable{iter: self, peeked: None}
     }
 
@@ -362,7 +360,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn skip_while<P>(self, predicate: P) -> SkipWhile<Self::Item, Self, P> where
+    fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
         P: FnMut(&Self::Item) -> bool,
     {
         SkipWhile{iter: self, flag: false, predicate: predicate}
@@ -383,7 +381,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn take_while<P>(self, predicate: P) -> TakeWhile<Self::Item, Self, P> where
+    fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
         P: FnMut(&Self::Item) -> bool,
     {
         TakeWhile{iter: self, flag: false, predicate: predicate}
@@ -448,12 +446,8 @@ 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::Item, B, Self, St, F> where
-        F: FnMut(&mut St, Self::Item) -> Option<B>,
+    fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
+        where F: FnMut(&mut St, Self::Item) -> Option<B>,
     {
         Scan{iter: self, f: f, state: initial_state}
     }
@@ -474,9 +468,8 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn flat_map<B, U, F>(self, f: F) -> FlatMap<Self::Item, B, Self, U, F> where
-        U: Iterator<Item=B>,
-        F: FnMut(Self::Item) -> U,
+    fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
+        where U: Iterator, F: FnMut(Self::Item) -> U,
     {
         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
     }
@@ -534,7 +527,7 @@ pub trait IteratorExt: Iterator + Sized {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn inspect<F>(self, f: F) -> Inspect<Self::Item, Self, F> where
+    fn inspect<F>(self, f: F) -> Inspect<Self, F> where
         F: FnMut(&Self::Item),
     {
         Inspect{iter: self, f: f}
@@ -1077,16 +1070,14 @@ pub trait ExactSizeIterator: Iterator {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, F> ExactSizeIterator for Inspect<A, I, F> where
-    I: ExactSizeIterator<Item=A>,
-    F: FnMut(&A),
+impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F> where
+    F: FnMut(&I::Item),
 {}
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<I> ExactSizeIterator for Rev<I> where I: ExactSizeIterator + DoubleEndedIterator {}
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> ExactSizeIterator for Map<A, B, I, F> where
-    I: ExactSizeIterator<Item=A>,
-    F: FnMut(A) -> B,
+impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F> where
+    F: FnMut(I::Item) -> B,
 {}
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> ExactSizeIterator for Zip<A, B> where A: ExactSizeIterator, B: ExactSizeIterator {}
@@ -1561,28 +1552,15 @@ impl<T, U, A, B> RandomAccessIterator for Zip<A, B> where
 /// An iterator that maps the values of `iter` with `f`
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Map<A, B, I: Iterator<Item=A>, F: FnMut(A) -> B> {
+#[derive(Clone)]
+pub struct Map<I, F> {
     iter: I,
     f: F,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> Clone for Map<A, B, I, F> where
-    I: Clone + Iterator<Item=A>,
-    F: Clone + FnMut(A) -> B,
-{
-    fn clone(&self) -> Map<A, B, I, F> {
-        Map {
-            iter: self.iter.clone(),
-            f: self.f.clone(),
-        }
-    }
-}
-
-impl<A, B, I, F> Map<A, B, I, F> where I: Iterator<Item=A>, F: FnMut(A) -> B {
+impl<I: Iterator, F, B> Map<I, F> where F: FnMut(I::Item) -> B {
     #[inline]
-    fn do_map(&mut self, elt: Option<A>) -> Option<B> {
+    fn do_map(&mut self, elt: Option<I::Item>) -> Option<B> {
         match elt {
             Some(a) => Some((self.f)(a)),
             _ => None
@@ -1591,7 +1569,7 @@ impl<A, B, I, F> Map<A, B, I, F> where I: Iterator<Item=A>, F: FnMut(A) -> B {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> Iterator for Map<A, B, I, F> where I: Iterator<Item=A>, F: FnMut(A) -> B {
+impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
     type Item = B;
 
     #[inline]
@@ -1607,9 +1585,8 @@ impl<A, B, I, F> Iterator for Map<A, B, I, F> where I: Iterator<Item=A>, F: FnMu
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> DoubleEndedIterator for Map<A, B, I, F> where
-    I: DoubleEndedIterator<Item=A>,
-    F: FnMut(A) -> B,
+impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
+    F: FnMut(I::Item) -> B,
 {
     #[inline]
     fn next_back(&mut self) -> Option<B> {
@@ -1619,9 +1596,8 @@ impl<A, B, I, F> DoubleEndedIterator for Map<A, B, I, F> where
 }
 
 #[unstable(feature = "core", reason = "trait is experimental")]
-impl<A, B, I, F> RandomAccessIterator for Map<A, B, I, F> where
-    I: RandomAccessIterator<Item=A>,
-    F: FnMut(A) -> B,
+impl<B, I: RandomAccessIterator, F> RandomAccessIterator for Map<I, F> where
+    F: FnMut(I::Item) -> B,
 {
     #[inline]
     fn indexable(&self) -> usize {
@@ -1638,31 +1614,18 @@ impl<A, B, I, F> RandomAccessIterator for Map<A, B, I, F> where
 /// An iterator that filters the elements of `iter` with `predicate`
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Filter<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
+#[derive(Clone)]
+pub struct Filter<I, P> {
     iter: I,
     predicate: P,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Clone for Filter<A, I, P> where
-    I: Clone + Iterator<Item=A>,
-    P: Clone + FnMut(&A) -> bool,
-{
-    fn clone(&self) -> Filter<A, I, P> {
-        Filter {
-            iter: self.iter.clone(),
-            predicate: self.predicate.clone(),
-        }
-    }
-}
-
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Iterator for Filter<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
-    type Item = A;
+impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
+    type Item = I::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<A> {
+    fn next(&mut self) -> Option<I::Item> {
         for x in self.iter.by_ref() {
             if (self.predicate)(&x) {
                 return Some(x);
@@ -1681,12 +1644,11 @@ impl<A, I, P> Iterator for Filter<A, I, P> where I: Iterator<Item=A>, P: FnMut(&
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> DoubleEndedIterator for Filter<A, I, P> where
-    I: DoubleEndedIterator<Item=A>,
-    P: FnMut(&A) -> bool,
+impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
+    where P: FnMut(&I::Item) -> bool,
 {
     #[inline]
-    fn next_back(&mut self) -> Option<A> {
+    fn next_back(&mut self) -> Option<I::Item> {
         for x in self.iter.by_ref().rev() {
             if (self.predicate)(&x) {
                 return Some(x);
@@ -1699,29 +1661,15 @@ impl<A, I, P> DoubleEndedIterator for Filter<A, I, P> where
 /// An iterator that uses `f` to both filter and map elements from `iter`
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct FilterMap<A, B, I, F> where I: Iterator<Item=A>, F: FnMut(A) -> Option<B> {
+#[derive(Clone)]
+pub struct FilterMap<I, F> {
     iter: I,
     f: F,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> Clone for FilterMap<A, B, I, F> where
-    I: Clone + Iterator<Item=A>,
-    F: Clone + FnMut(A) -> Option<B>,
-{
-    fn clone(&self) -> FilterMap<A, B, I, F> {
-        FilterMap {
-            iter: self.iter.clone(),
-            f: self.f.clone(),
-        }
-    }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> Iterator for FilterMap<A, B, I, F> where
-    I: Iterator<Item=A>,
-    F: FnMut(A) -> Option<B>,
+impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
+    where F: FnMut(I::Item) -> Option<B>,
 {
     type Item = B;
 
@@ -1744,9 +1692,8 @@ impl<A, B, I, F> Iterator for FilterMap<A, B, I, F> where
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, F> DoubleEndedIterator for FilterMap<A, B, I, F> where
-    I: DoubleEndedIterator<Item=A>,
-    F: FnMut(A) -> Option<B>,
+impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
+    where F: FnMut(I::Item) -> Option<B>,
 {
     #[inline]
     fn next_back(&mut self) -> Option<B> {
@@ -1824,20 +1771,28 @@ impl<I> RandomAccessIterator for Enumerate<I> where I: RandomAccessIterator {
 }
 
 /// An iterator with a `peek()` that returns an optional reference to the next element.
-#[derive(Clone)]
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Peekable<T, I> where I: Iterator<Item=T> {
+pub struct Peekable<I: Iterator> {
     iter: I,
-    peeked: Option<T>,
+    peeked: Option<I::Item>,
+}
+
+impl<I: Iterator + Clone> Clone for Peekable<I> where I::Item: Clone {
+    fn clone(&self) -> Peekable<I> {
+        Peekable {
+            iter: self.iter.clone(),
+            peeked: self.peeked.clone(),
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T, I> Iterator for Peekable<T, I> where I: Iterator<Item=T> {
-    type Item = T;
+impl<I: Iterator> Iterator for Peekable<I> {
+    type Item = I::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<T> {
+    fn next(&mut self) -> Option<I::Item> {
         if self.peeked.is_some() { self.peeked.take() }
         else { self.iter.next() }
     }
@@ -1859,14 +1814,14 @@ impl<T, I> Iterator for Peekable<T, I> where I: Iterator<Item=T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T, I> ExactSizeIterator for Peekable<T, I> where I: ExactSizeIterator<Item = T> {}
+impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T, I> Peekable<T, I> where I: Iterator<Item=T> {
-    /// Return a reference to the next element of the iterator with out advancing it,
-    /// or None if the iterator is exhausted.
+impl<I: Iterator> Peekable<I> {
+    /// Return a reference to the next element of the iterator with out
+    /// advancing it, or None if the iterator is exhausted.
     #[inline]
-    pub fn peek(&mut self) -> Option<&T> {
+    pub fn peek(&mut self) -> Option<&I::Item> {
         if self.peeked.is_none() {
             self.peeked = self.iter.next();
         }
@@ -1886,33 +1841,21 @@ impl<T, I> Peekable<T, I> where I: Iterator<Item=T> {
 /// An iterator that rejects elements while `predicate` is true
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct SkipWhile<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
+#[derive(Clone)]
+pub struct SkipWhile<I, P> {
     iter: I,
     flag: bool,
     predicate: P,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Clone for SkipWhile<A, I, P> where
-    I: Clone + Iterator<Item=A>,
-    P: Clone + FnMut(&A) -> bool,
+impl<I: Iterator, P> Iterator for SkipWhile<I, P>
+    where P: FnMut(&I::Item) -> bool
 {
-    fn clone(&self) -> SkipWhile<A, I, P> {
-        SkipWhile {
-            iter: self.iter.clone(),
-            flag: self.flag,
-            predicate: self.predicate.clone(),
-        }
-    }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Iterator for SkipWhile<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
-    type Item = A;
+    type Item = I::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<A> {
+    fn next(&mut self) -> Option<I::Item> {
         for x in self.iter.by_ref() {
             if self.flag || !(self.predicate)(&x) {
                 self.flag = true;
@@ -1932,33 +1875,21 @@ impl<A, I, P> Iterator for SkipWhile<A, I, P> where I: Iterator<Item=A>, P: FnMu
 /// An iterator that only accepts elements while `predicate` is true
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct TakeWhile<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
+#[derive(Clone)]
+pub struct TakeWhile<I, P> {
     iter: I,
     flag: bool,
     predicate: P,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Clone for TakeWhile<A, I, P> where
-    I: Clone + Iterator<Item=A>,
-    P: Clone + FnMut(&A) -> bool,
+impl<I: Iterator, P> Iterator for TakeWhile<I, P>
+    where P: FnMut(&I::Item) -> bool
 {
-    fn clone(&self) -> TakeWhile<A, I, P> {
-        TakeWhile {
-            iter: self.iter.clone(),
-            flag: self.flag,
-            predicate: self.predicate.clone(),
-        }
-    }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, P> Iterator for TakeWhile<A, I, P> where I: Iterator<Item=A>, P: FnMut(&A) -> bool {
-    type Item = A;
+    type Item = I::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<A> {
+    fn next(&mut self) -> Option<I::Item> {
         if self.flag {
             None
         } else {
@@ -2118,7 +2049,8 @@ impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
 /// An iterator to maintain state while iterating another iterator
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Scan<A, B, I, St, F> where I: Iterator, F: FnMut(&mut St, A) -> Option<B> {
+#[derive(Clone)]
+pub struct Scan<I, St, F> {
     iter: I,
     f: F,
 
@@ -2126,26 +2058,9 @@ pub struct Scan<A, B, I, St, F> where I: Iterator, F: FnMut(&mut St, A) -> Optio
     pub state: St,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, St, F> Clone for Scan<A, B, I, St, F> where
-    I: Clone + Iterator<Item=A>,
-    St: Clone,
-    F: Clone + FnMut(&mut St, A) -> Option<B>,
-{
-    fn clone(&self) -> Scan<A, B, I, St, F> {
-        Scan {
-            iter: self.iter.clone(),
-            f: self.f.clone(),
-            state: self.state.clone(),
-        }
-    }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, St, F> Iterator for Scan<A, B, I, St, F> where
-    I: Iterator<Item=A>,
-    F: FnMut(&mut St, A) -> Option<B>,
+impl<B, I: Iterator, St, F> Iterator for Scan<I, St, F> where
+    F: FnMut(&mut St, I::Item) -> Option<B>,
 {
     type Item = B;
 
@@ -2166,44 +2081,22 @@ impl<A, B, I, St, F> Iterator for Scan<A, B, I, St, F> where
 ///
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct FlatMap<A, B, I, U, F> where
-    I: Iterator<Item=A>,
-    U: Iterator<Item=B>,
-    F: FnMut(A) -> U,
-{
+#[derive(Clone)]
+pub struct FlatMap<I, U, F> {
     iter: I,
     f: F,
     frontiter: Option<U>,
     backiter: Option<U>,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, U, F> Clone for FlatMap<A, B, I, U, F> where
-    I: Clone + Iterator<Item=A>,
-    U: Clone + Iterator<Item=B>,
-    F: Clone + FnMut(A) -> U,
-{
-    fn clone(&self) -> FlatMap<A, B, I, U, F> {
-        FlatMap {
-            iter: self.iter.clone(),
-            f: self.f.clone(),
-            frontiter: self.frontiter.clone(),
-            backiter: self.backiter.clone(),
-        }
-    }
-}
-
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, U, F> Iterator for FlatMap<A, B, I, U, F> where
-    I: Iterator<Item=A>,
-    U: Iterator<Item=B>,
-    F: FnMut(A) -> U,
+impl<I: Iterator, U: Iterator, F> Iterator for FlatMap<I, U, F>
+    where F: FnMut(I::Item) -> U,
 {
-    type Item = B;
+    type Item = U::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<B> {
+    fn next(&mut self) -> Option<U::Item> {
         loop {
             for inner in self.frontiter.iter_mut() {
                 for x in inner.by_ref() {
@@ -2230,13 +2123,12 @@ impl<A, B, I, U, F> Iterator for FlatMap<A, B, I, U, F> where
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B, I, U, F> DoubleEndedIterator for FlatMap<A, B, I, U, F> where
-    I: DoubleEndedIterator<Item=A>,
-    U: DoubleEndedIterator<Item=B>,
-    F: FnMut(A) -> U,
+impl<I: DoubleEndedIterator, U: DoubleEndedIterator, F> DoubleEndedIterator
+    for FlatMap<I, U, F>
+    where F: FnMut(I::Item) -> U
 {
     #[inline]
-    fn next_back(&mut self) -> Option<B> {
+    fn next_back(&mut self) -> Option<U::Item> {
         loop {
             for inner in self.backiter.iter_mut() {
                 match inner.next_back() {
@@ -2340,28 +2232,15 @@ impl<I> Fuse<I> {
 /// element before yielding it.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Inspect<A, I, F> where I: Iterator<Item=A>, F: FnMut(&A) {
+#[derive(Clone)]
+pub struct Inspect<I, F> {
     iter: I,
     f: F,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, F> Clone for Inspect<A, I, F> where
-    I: Clone + Iterator<Item=A>,
-    F: Clone + FnMut(&A),
-{
-    fn clone(&self) -> Inspect<A, I, F> {
-        Inspect {
-            iter: self.iter.clone(),
-            f: self.f.clone(),
-        }
-    }
-}
-
-impl<A, I, F> Inspect<A, I, F> where I: Iterator<Item=A>, F: FnMut(&A) {
+impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
     #[inline]
-    fn do_inspect(&mut self, elt: Option<A>) -> Option<A> {
+    fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
         match elt {
             Some(ref a) => (self.f)(a),
             None => ()
@@ -2372,11 +2251,11 @@ impl<A, I, F> Inspect<A, I, F> where I: Iterator<Item=A>, F: FnMut(&A) {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, F> Iterator for Inspect<A, I, F> where I: Iterator<Item=A>, F: FnMut(&A) {
-    type Item = A;
+impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
+    type Item = I::Item;
 
     #[inline]
-    fn next(&mut self) -> Option<A> {
+    fn next(&mut self) -> Option<I::Item> {
         let next = self.iter.next();
         self.do_inspect(next)
     }
@@ -2388,21 +2267,19 @@ impl<A, I, F> Iterator for Inspect<A, I, F> where I: Iterator<Item=A>, F: FnMut(
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, I, F> DoubleEndedIterator for Inspect<A, I, F> where
-    I: DoubleEndedIterator<Item=A>,
-    F: FnMut(&A),
+impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
+    where F: FnMut(&I::Item),
 {
     #[inline]
-    fn next_back(&mut self) -> Option<A> {
+    fn next_back(&mut self) -> Option<I::Item> {
         let next = self.iter.next_back();
         self.do_inspect(next)
     }
 }
 
 #[unstable(feature = "core", reason = "trait is experimental")]
-impl<A, I, F> RandomAccessIterator for Inspect<A, I, F> where
-    I: RandomAccessIterator<Item=A>,
-    F: FnMut(&A),
+impl<I: RandomAccessIterator, F> RandomAccessIterator for Inspect<I, F>
+    where F: FnMut(&I::Item),
 {
     #[inline]
     fn indexable(&self) -> usize {
@@ -2410,7 +2287,7 @@ impl<A, I, F> RandomAccessIterator for Inspect<A, I, F> where
     }
 
     #[inline]
-    fn idx(&mut self, index: usize) -> Option<A> {
+    fn idx(&mut self, index: usize) -> Option<I::Item> {
         let element = self.iter.idx(index);
         self.do_inspect(element)
     }
@@ -2426,9 +2303,11 @@ impl<A, I, F> RandomAccessIterator for Inspect<A, I, F> where
 /// use std::iter::Unfold;
 /// use std::num::Int; // For `.checked_add()`
 ///
-/// // This iterator will yield up to the last Fibonacci number before the max value of `u32`.
-/// // You can simply change `u32` to `u64` in this line if you want higher values than that.
-/// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)), |&mut (ref mut x2, ref mut x1)| {
+/// // This iterator will yield up to the last Fibonacci number before the max
+/// // value of `u32`. You can simply change `u32` to `u64` in this line if
+/// // you want higher values than that.
+/// let mut fibonacci = Unfold::new((Some(0u32), Some(1u32)),
+///                                 |&mut (ref mut x2, ref mut x1)| {
 ///     // Attempt to get the next Fibonacci number
 ///     // `x1` will be `None` if previously overflowed.
 ///     let next = match (*x2, *x1) {
@@ -2449,32 +2328,19 @@ impl<A, I, F> RandomAccessIterator for Inspect<A, I, F> where
 /// }
 /// ```
 #[unstable(feature = "core")]
-pub struct Unfold<A, St, F> where F: FnMut(&mut St) -> Option<A> {
+#[derive(Clone)]
+pub struct Unfold<St, F> {
     f: F,
     /// Internal state that will be passed to the closure on the next iteration
     pub state: St,
 }
 
-// FIXME(#19839) Remove in favor of `#[derive(Clone)]`
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, St, F> Clone for Unfold<A, St, F> where
-    F: Clone + FnMut(&mut St) -> Option<A>,
-    St: Clone,
-{
-    fn clone(&self) -> Unfold<A, St, F> {
-        Unfold {
-            f: self.f.clone(),
-            state: self.state.clone(),
-        }
-    }
-}
-
 #[unstable(feature = "core")]
-impl<A, St, F> Unfold<A, St, F> where F: FnMut(&mut St) -> Option<A> {
+impl<A, St, F> Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
     /// Creates a new iterator with the specified closure as the "iterator
     /// function" and an initial state to eventually pass to the closure
     #[inline]
-    pub fn new(initial_state: St, f: F) -> Unfold<A, St, F> {
+    pub fn new(initial_state: St, f: F) -> Unfold<St, F> {
         Unfold {
             f: f,
             state: initial_state
@@ -2483,7 +2349,7 @@ impl<A, St, F> Unfold<A, St, F> where F: FnMut(&mut St) -> Option<A> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A, St, F> Iterator for Unfold<A, St, F> where F: FnMut(&mut St) -> Option<A> {
+impl<A, St, F> Iterator for Unfold<St, F> where F: FnMut(&mut St) -> Option<A> {
     type Item = A;
 
     #[inline]
@@ -2921,7 +2787,7 @@ type IterateState<T, F> = (F, Option<T>, bool);
 /// An iterator that repeatedly applies a given function, starting
 /// from a given seed value.
 #[unstable(feature = "core")]
-pub type Iterate<T, F> = Unfold<T, IterateState<T, F>, fn(&mut IterateState<T, F>) -> Option<T>>;
+pub type Iterate<T, F> = Unfold<IterateState<T, F>, fn(&mut IterateState<T, F>) -> Option<T>>;
 
 /// Create a new iterator that produces an infinite sequence of
 /// repeated applications of the given function `f`.
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index cb7af3b3d35..85b4a202644 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -478,7 +478,7 @@ impl<'a> DoubleEndedIterator for CharIndices<'a> {
 /// Created with `StrExt::bytes`
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Clone)]
-pub struct Bytes<'a>(Map<&'a u8, u8, slice::Iter<'a, u8>, BytesDeref>);
+pub struct Bytes<'a>(Map<slice::Iter<'a, u8>, BytesDeref>);
 delegate_iter!{exact u8 : Bytes<'a>}
 
 /// A temporary fn new type that ensures that the `Bytes` iterator
@@ -526,7 +526,7 @@ pub struct Lines<'a> {
 /// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct LinesAny<'a> {
-    inner: Map<&'a str, &'a str, Lines<'a>, fn(&str) -> &str>,
+    inner: Map<Lines<'a>, fn(&str) -> &str>,
 }
 
 impl<'a, Sep> CharSplits<'a, Sep> {
diff --git a/src/librustc_trans/trans/basic_block.rs b/src/librustc_trans/trans/basic_block.rs
index d3ff432b5e4..f11c3154274 100644
--- a/src/librustc_trans/trans/basic_block.rs
+++ b/src/librustc_trans/trans/basic_block.rs
@@ -16,12 +16,7 @@ use std::iter::{Filter, Map};
 #[derive(Copy)]
 pub struct BasicBlock(pub BasicBlockRef);
 
-pub type Preds = Map<
-    Value,
-    BasicBlock,
-    Filter<Value, Users, fn(&Value) -> bool>,
-    fn(Value) -> BasicBlock,
->;
+pub type Preds = Map<Filter<Users, fn(&Value) -> bool>, fn(Value) -> BasicBlock>;
 
 /// Wrapper for LLVM BasicBlockRef
 impl BasicBlock {
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 3e2c7627dbe..852d5a86fc0 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -1300,18 +1300,13 @@ pub struct IterMut<'a, K: 'a, V: 'a> {
 /// HashMap move iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<K, V> {
-    inner: iter::Map<
-        (SafeHash, K, V),
-        (K, V),
-        table::IntoIter<K, V>,
-        fn((SafeHash, K, V)) -> (K, V),
-    >
+    inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
 }
 
 /// HashMap keys iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Keys<'a, K: 'a, V: 'a> {
-    inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
+    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
 }
 
 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
@@ -1326,7 +1321,7 @@ impl<'a, K, V> Clone for Keys<'a, K, V> {
 /// HashMap values iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Values<'a, K: 'a, V: 'a> {
-    inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
+    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
 }
 
 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
@@ -1342,12 +1337,7 @@ impl<'a, K, V> Clone for Values<'a, K, V> {
 #[unstable(feature = "std_misc",
            reason = "matches collection reform specification, waiting for dust to settle")]
 pub struct Drain<'a, K: 'a, V: 'a> {
-    inner: iter::Map<
-        (SafeHash, K, V),
-        (K, V),
-        table::Drain<'a, K, V>,
-        fn((SafeHash, K, V)) -> (K, V),
-    >
+    inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
 }
 
 /// A view into a single occupied location in a HashMap.
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index c6dcb0d230f..e6b06e5ef1f 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -794,13 +794,13 @@ pub struct Iter<'a, K: 'a> {
 /// HashSet move iterator
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<K> {
-    iter: Map<(K, ()), K, map::IntoIter<K, ()>, fn((K, ())) -> K>
+    iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K>
 }
 
 /// HashSet drain iterator
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Drain<'a, K: 'a> {
-    iter: Map<(K, ()), K, map::Drain<'a, K, ()>, fn((K, ())) -> K>,
+    iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>,
 }
 
 /// Intersection iterator
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 6a0c8a93010..69f815e3f8b 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -31,7 +31,7 @@ pub type Components<'a> = Split<'a, u8, fn(&u8) -> bool>;
 
 /// Iterator that yields successive components of a Path as Option<&str>
 pub type StrComponents<'a> =
-    Map<&'a [u8], Option<&'a str>, Components<'a>, fn(&[u8]) -> Option<&str>>;
+    Map<Components<'a>, fn(&[u8]) -> Option<&str>>;
 
 /// Represents a POSIX file path
 #[derive(Clone)]
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index b524b89ef9f..750af47ff8c 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -40,11 +40,11 @@ use super::{contains_nul, BytesContainer, GenericPath, GenericPathUnsafe};
 /// Each component is yielded as Option<&str> for compatibility with PosixPath, but
 /// every component in WindowsPath is guaranteed to be Some.
 pub type StrComponents<'a> =
-    Map<&'a str, Option<&'a str>, SplitTerminator<'a, char>, fn(&'a str) -> Option<&'a str>>;
+    Map<SplitTerminator<'a, char>, fn(&'a str) -> Option<&'a str>>;
 
 /// Iterator that yields successive components of a Path as &[u8]
 pub type Components<'a> =
-    Map<Option<&'a str>, &'a [u8], StrComponents<'a>, fn(Option<&str>) -> &[u8]>;
+    Map<StrComponents<'a>, fn(Option<&str>) -> &[u8]>;
 
 /// Represents a Windows path
 // Notes for Windows path impl:
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index 8ac5b6e5274..3e8eab39d88 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -436,7 +436,7 @@ pub fn str_lit(lit: &str) -> String {
     let error = |&: i| format!("lexer should have rejected {} at {}", lit, i);
 
     /// Eat everything up to a non-whitespace
-    fn eat<'a>(it: &mut iter::Peekable<(usize, char), str::CharIndices<'a>>) {
+    fn eat<'a>(it: &mut iter::Peekable<str::CharIndices<'a>>) {
         loop {
             match it.peek().map(|x| x.1) {
                 Some(' ') | Some('\n') | Some('\r') | Some('\t') => {
@@ -605,7 +605,7 @@ pub fn binary_lit(lit: &str) -> Rc<Vec<u8>> {
     let error = |&: i| format!("lexer should have rejected {} at {}", lit, i);
 
     /// Eat everything up to a non-whitespace
-    fn eat<'a, I: Iterator<Item=(usize, u8)>>(it: &mut iter::Peekable<(usize, u8), I>) {
+    fn eat<'a, I: Iterator<Item=(usize, u8)>>(it: &mut iter::Peekable<I>) {
         loop {
             match it.peek().map(|x| x.1) {
                 Some(b' ') | Some(b'\n') | Some(b'\r') | Some(b'\t') => {
diff --git a/src/libunicode/u_str.rs b/src/libunicode/u_str.rs
index 9a757c0c980..0e3aacbc09a 100644
--- a/src/libunicode/u_str.rs
+++ b/src/libunicode/u_str.rs
@@ -32,7 +32,7 @@ use tables::grapheme::GraphemeCat;
 /// An iterator over the words of a string, separated by a sequence of whitespace
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Words<'a> {
-    inner: Filter<&'a str, Split<'a, fn(char) -> bool>, fn(&&str) -> bool>,
+    inner: Filter<Split<'a, fn(char) -> bool>, fn(&&str) -> bool>,
 }
 
 /// Methods for Unicode string slices