rollup merge of #19770: csouth3/iterator-wrapperstructs

Using a type alias for iterator implementations is fragile since this exposes the implementation to users of the iterator, and any changes could break existing code.

This PR changes the iterators of `BTreeMap`, `BTreeSet`, `HashMap`, and `HashSet` to use proper new types, rather than type aliases.  However, since it is fair-game to treat a type-alias as the aliased type, this is a:

[breaking-change].

2 files changed, 89 insertions, 57 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 2a8d97eed05..d22e7b2f764 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, IteratorExt, FromIterator, Extend};
+use iter::{mod, Iterator, IteratorExt, FromIterator, Extend, Map};
 use kinds::Sized;
 use mem::{mod, replace};
 use num::{Int, UnsignedInt};
@@ -859,7 +859,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn keys(&self) -> Keys<K, V> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
 
-        self.iter().map(first)
+        Keys { inner: self.iter().map(first) }
     }
 
     /// An iterator visiting all values in arbitrary order.
@@ -883,7 +883,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn values(&self) -> Values<K, V> {
         fn second<A, B>((_, b): (A, B)) -> B { b }
 
-        self.iter().map(second)
+        Values { inner: self.iter().map(second) }
     }
 
     /// An iterator visiting all key-value pairs in arbitrary order.
@@ -1335,6 +1335,16 @@ pub struct MoveEntries<K, V> {
     >
 }
 
+/// HashMap keys iterator
+pub struct Keys<'a, K: 'a, V: 'a> {
+    inner: Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
+}
+
+/// HashMap values iterator
+pub struct Values<'a, K: 'a, V: 'a> {
+    inner: Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
+}
+
 /// A view into a single occupied location in a HashMap
 pub struct OccupiedEntry<'a, K:'a, V:'a> {
     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
@@ -1365,36 +1375,28 @@ enum VacantEntryState<K, V, M> {
 }
 
 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(K, V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
+}
+
+impl<'a, K, V> Iterator<&'a K> for Keys<'a, K, V> {
+    #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
+}
+
+impl<'a, K, V> Iterator<&'a V> for Values<'a, K, V> {
+    #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<'a, K, V> OccupiedEntry<'a, K, V> {
@@ -1448,14 +1450,6 @@ impl<'a, K, V> VacantEntry<'a, K, V> {
     }
 }
 
-/// HashMap keys iterator
-pub type Keys<'a, K, V> =
-    iter::Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>;
-
-/// HashMap values iterator
-pub type Values<'a, K, V> =
-    iter::Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>;
-
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
         let (lower, _) = iter.size_hint();
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index c71f0d5b935..c4356d91064 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -17,12 +17,11 @@ use default::Default;
 use fmt::Show;
 use fmt;
 use hash::{Hash, Hasher, RandomSipHasher};
-use iter::{Iterator, IteratorExt, FromIterator, FilterMap, Chain, Repeat, Zip, Extend, repeat};
-use iter;
+use iter::{Iterator, IteratorExt, FromIterator, Map, FilterMap, Chain, Repeat, Zip, Extend, repeat};
 use option::Option::{Some, None, mod};
 use result::Result::{Ok, Err};
 
-use super::map::{HashMap, Entries, MoveEntries, INITIAL_CAPACITY};
+use super::map::{HashMap, MoveEntries, Keys, INITIAL_CAPACITY};
 
 // FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
 
@@ -252,7 +251,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 iter<'a>(&'a self) -> SetItems<'a, T> {
-        self.map.keys()
+        SetItems { iter: self.map.keys() }
     }
 
     /// Creates a consuming iterator, that is, one that moves each value out
@@ -279,7 +278,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     pub fn into_iter(self) -> SetMoveItems<T> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
 
-        self.map.into_iter().map(first)
+        SetMoveItems { iter: self.map.into_iter().map(first) }
     }
 
     /// Visit the values representing the difference.
@@ -312,7 +311,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
             if !other.contains(elt) { Some(elt) } else { None }
         }
 
-        repeat(other).zip(self.iter()).filter_map(filter)
+        SetAlgebraItems { iter: repeat(other).zip(self.iter()).filter_map(filter) }
     }
 
     /// Visit the values representing the symmetric difference.
@@ -337,8 +336,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
-        -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
-        self.difference(other).chain(other.difference(self))
+        -> SymDifferenceItems<'a, T, H> {
+        SymDifferenceItems { iter: self.difference(other).chain(other.difference(self)) }
     }
 
     /// Visit the values representing the intersection.
@@ -366,7 +365,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
             if other.contains(elt) { Some(elt) } else { None }
         }
 
-        repeat(other).zip(self.iter()).filter_map(filter)
+        SetAlgebraItems { iter: repeat(other).zip(self.iter()).filter_map(filter) }
     }
 
     /// Visit the values representing the union.
@@ -387,9 +386,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
-    pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
-        -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
-        self.iter().chain(other.difference(self))
+    pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> UnionItems<'a, T, H> {
+        UnionItems { iter: self.iter().chain(other.difference(self)) }
     }
 
     /// Return the number of elements in the set
@@ -617,21 +615,61 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
 }
 
 /// HashSet iterator
-pub type SetItems<'a, K> =
-    iter::Map<(&'a K, &'a ()), &'a K, Entries<'a, K, ()>, fn((&'a K, &'a ())) -> &'a K>;
+pub struct SetItems<'a, K: 'a> {
+    iter: Keys<'a, K, ()>
+}
 
 /// HashSet move iterator
-pub type SetMoveItems<K> = iter::Map<(K, ()), K, MoveEntries<K, ()>, fn((K, ())) -> K>;
+pub struct SetMoveItems<K> {
+    iter: Map<(K, ()), K, MoveEntries<K, ()>, fn((K, ())) -> K>
+}
 
 // `Repeat` is used to feed the filter closure an explicit capture
 // of a reference to the other set
-/// Set operations iterator
-pub type SetAlgebraItems<'a, T, H> = FilterMap<
-    (&'a HashSet<T, H>, &'a T),
-    &'a T,
-    Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>,
-    for<'b> fn((&HashSet<T, H>, &'b T)) -> Option<&'b T>,
->;
+/// Set operations iterator, used directly for intersection and difference
+pub struct SetAlgebraItems<'a, T: 'a, H: 'a> {
+    iter: FilterMap<
+        (&'a HashSet<T, H>, &'a T),
+        &'a T,
+        Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>,
+        for<'b> fn((&HashSet<T, H>, &'b T)) -> Option<&'b T>,
+    >
+}
+
+/// Symmetric difference iterator.
+pub struct SymDifferenceItems<'a, T: 'a, H: 'a> {
+    iter: Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>>
+}
+
+/// Set union iterator.
+pub struct UnionItems<'a, T: 'a, H: 'a> {
+    iter: Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>>
+}
+
+impl<'a, K> Iterator<&'a K> for SetItems<'a, K> {
+    fn next(&mut self) -> Option<&'a K> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<K> Iterator<K> for SetMoveItems<K> {
+    fn next(&mut self) -> Option<K> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for SetAlgebraItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for SymDifferenceItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for UnionItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
 
 #[cfg(test)]
 mod test_set {