auto merge of #8120 : blake2-ppc/rust/iterator-fixes, r=thestinger

Implement RandomAccessIterator (RAI) where possible, for Iterator adaptors such as Map, Enumerate, Peek, Skip, Take, Cycle, where the adapted iterator is already RAI, and for collections where it is relevant (ringbuf and bitv).

After discussion with thestinger, remove the RAI impl for VecMutIterator, we cannot soundly provide mutable access with this trait.

Implement Extendable everywhere FromIterator is already implemented.

Fixes issue #8108.

5 files changed, 355 insertions, 63 deletions

diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index a9a11b611d6..e43293f3212 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -19,7 +19,7 @@ use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 use clone::Clone;
 use cmp::{Eq, Equiv};
 use hash::Hash;
-use iterator::{Iterator, IteratorUtil, FromIterator, Chain};
+use iterator::{Iterator, IteratorUtil, FromIterator, Extendable, Chain};
 use num;
 use option::{None, Option, Some};
 use rand::RngUtil;
@@ -618,15 +618,19 @@ impl<K> Iterator<K> for HashSetConsumeIterator<K> {
 }
 
 impl<K: Eq + Hash, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for HashMap<K, V> {
-    pub fn from_iterator(iter: &mut T) -> HashMap<K, V> {
+    fn from_iterator(iter: &mut T) -> HashMap<K, V> {
         let (lower, _) = iter.size_hint();
         let mut map = HashMap::with_capacity(lower);
+        map.extend(iter);
+        map
+    }
+}
 
+impl<K: Eq + Hash, V, T: Iterator<(K, V)>> Extendable<(K, V), T> for HashMap<K, V> {
+    fn extend(&mut self, iter: &mut T) {
         for iter.advance |(k, v)| {
-            map.insert(k, v);
+            self.insert(k, v);
         }
-
-        map
     }
 }
 
@@ -771,15 +775,19 @@ impl<T:Hash + Eq> HashSet<T> {
 }
 
 impl<K: Eq + Hash, T: Iterator<K>> FromIterator<K, T> for HashSet<K> {
-    pub fn from_iterator(iter: &mut T) -> HashSet<K> {
+    fn from_iterator(iter: &mut T) -> HashSet<K> {
         let (lower, _) = iter.size_hint();
         let mut set = HashSet::with_capacity(lower);
+        set.extend(iter);
+        set
+    }
+}
 
+impl<K: Eq + Hash, T: Iterator<K>> Extendable<K, T> for HashSet<K> {
+    fn extend(&mut self, iter: &mut T) {
         for iter.advance |k| {
-            set.insert(k);
+            self.insert(k);
         }
-
-        set
     }
 }
 
diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 6828de51622..9fe865333a2 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -529,7 +529,7 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
     #[inline]
     fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
         -> FlatMap<'r, A, T, U> {
-        FlatMap{iter: self, f: f, subiter: None }
+        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
     }
 
     // FIXME: #5898: should be called `peek`
@@ -811,6 +811,30 @@ impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
     }
 }
 
+impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        if self.orig.indexable() > 0 {
+            uint::max_value
+        } else {
+            0
+        }
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        let liter = self.iter.indexable();
+        let lorig = self.orig.indexable();
+        if lorig == 0 {
+            None
+        } else if index < liter {
+            self.iter.idx(index)
+        } else {
+            self.orig.idx((index - liter) % lorig)
+        }
+    }
+}
+
 /// An iterator which strings two iterators together
 #[deriving(Clone)]
 pub struct Chain<T, U> {
@@ -924,20 +948,44 @@ impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
     }
 }
 
+impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
+RandomAccessIterator<(A, B)> for Zip<T, U> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        cmp::min(self.a.indexable(), self.b.indexable())
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<(A, B)> {
+        match (self.a.idx(index), self.b.idx(index)) {
+            (Some(x), Some(y)) => Some((x, y)),
+            _ => None
+        }
+    }
+}
+
 /// An iterator which maps the values of `iter` with `f`
 pub struct Map<'self, A, B, T> {
     priv iter: T,
     priv f: &'self fn(A) -> B
 }
 
-impl<'self, A, B, T: Iterator<A>> Iterator<B> for Map<'self, A, B, T> {
+impl<'self, A, B, T> Map<'self, A, B, T> {
     #[inline]
-    fn next(&mut self) -> Option<B> {
-        match self.iter.next() {
+    fn do_map(&self, elt: Option<A>) -> Option<B> {
+        match elt {
             Some(a) => Some((self.f)(a)),
             _ => None
         }
     }
+}
+
+impl<'self, A, B, T: Iterator<A>> Iterator<B> for Map<'self, A, B, T> {
+    #[inline]
+    fn next(&mut self) -> Option<B> {
+        let next = self.iter.next();
+        self.do_map(next)
+    }
 
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) {
@@ -949,10 +997,21 @@ impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
 for Map<'self, A, B, T> {
     #[inline]
     fn next_back(&mut self) -> Option<B> {
-        match self.iter.next_back() {
-            Some(a) => Some((self.f)(a)),
-            _ => None
-        }
+        let next = self.iter.next_back();
+        self.do_map(next)
+    }
+}
+
+impl<'self, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B>
+for Map<'self, A, B, T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        self.iter.indexable()
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<B> {
+        self.do_map(self.iter.idx(index))
     }
 }
 
@@ -1069,6 +1128,21 @@ impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
     }
 }
 
+impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        self.iter.indexable()
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<(uint, A)> {
+        match self.iter.idx(index) {
+            Some(a) => Some((self.count + index, a)),
+            _ => None,
+        }
+    }
+}
+
 /// An iterator which rejects elements while `predicate` is true
 pub struct SkipWhile<'self, A, T> {
     priv iter: T,
@@ -1189,6 +1263,27 @@ impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
     }
 }
 
+impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        let N = self.iter.indexable();
+        if N < self.n {
+            0
+        } else {
+            N - self.n
+        }
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        if index >= self.indexable() {
+            None
+        } else {
+            self.iter.idx(index + self.n)
+        }
+    }
+}
+
 /// An iterator which only iterates over the first `n` iterations of `iter`.
 #[deriving(Clone)]
 pub struct Take<T> {
@@ -1223,6 +1318,23 @@ impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
     }
 }
 
+impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        cmp::min(self.iter.indexable(), self.n)
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        if index >= self.n {
+            None
+        } else {
+            self.iter.idx(index)
+        }
+    }
+}
+
+
 /// An iterator to maintain state while iterating another iterator
 pub struct Scan<'self, A, B, T, St> {
     priv iter: T,
@@ -1251,7 +1363,8 @@ impl<'self, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'self, A, B, T, St> {
 pub struct FlatMap<'self, A, T, U> {
     priv iter: T,
     priv f: &'self fn(A) -> U,
-    priv subiter: Option<U>,
+    priv frontiter: Option<U>,
+    priv backiter: Option<U>,
 }
 
 impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for
@@ -1259,14 +1372,45 @@ impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for
     #[inline]
     fn next(&mut self) -> Option<B> {
         loop {
-            for self.subiter.mut_iter().advance |inner| {
+            for self.frontiter.mut_iter().advance |inner| {
                 for inner.advance |x| {
                     return Some(x)
                 }
             }
             match self.iter.next().map_consume(|x| (self.f)(x)) {
-                None => return None,
-                next => self.subiter = next,
+                None => return self.backiter.chain_mut_ref(|it| it.next()),
+                next => self.frontiter = next,
+            }
+        }
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (uint, Option<uint>) {
+        let (flo, fhi) = self.frontiter.map_default((0, Some(0)), |it| it.size_hint());
+        let (blo, bhi) = self.backiter.map_default((0, Some(0)), |it| it.size_hint());
+        match (self.iter.size_hint(), fhi, bhi) {
+            ((0, Some(0)), Some(a), Some(b)) => (flo + blo, Some(a + b)),
+            _ => (flo + blo, None)
+        }
+    }
+}
+
+impl<'self,
+     A, T: DoubleEndedIterator<A>,
+     B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
+     for FlatMap<'self, A, T, U> {
+    #[inline]
+    fn next_back(&mut self) -> Option<B> {
+        loop {
+            for self.backiter.mut_iter().advance |inner| {
+                match inner.next_back() {
+                    None => (),
+                    y => return y
+                }
+            }
+            match self.iter.next_back().map_consume(|x| (self.f)(x)) {
+                None => return self.frontiter.chain_mut_ref(|it| it.next_back()),
+                next => self.backiter = next,
             }
         }
     }
@@ -1279,17 +1423,23 @@ pub struct Peek<'self, A, T> {
     priv f: &'self fn(&A)
 }
 
-impl<'self, A, T: Iterator<A>> Iterator<A> for Peek<'self, A, T> {
+impl<'self, A, T> Peek<'self, A, T> {
     #[inline]
-    fn next(&mut self) -> Option<A> {
-        let next = self.iter.next();
-
-        match next {
+    fn do_peek(&self, elt: Option<A>) -> Option<A> {
+        match elt {
             Some(ref a) => (self.f)(a),
             None => ()
         }
 
-        next
+        elt
+    }
+}
+
+impl<'self, A, T: Iterator<A>> Iterator<A> for Peek<'self, A, T> {
+    #[inline]
+    fn next(&mut self) -> Option<A> {
+        let next = self.iter.next();
+        self.do_peek(next)
     }
 
     #[inline]
@@ -1302,13 +1452,19 @@ impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Peek<'self,
     #[inline]
     fn next_back(&mut self) -> Option<A> {
         let next = self.iter.next_back();
+        self.do_peek(next)
+    }
+}
 
-        match next {
-            Some(ref a) => (self.f)(a),
-            None => ()
-        }
+impl<'self, A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Peek<'self, A, T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        self.iter.indexable()
+    }
 
-        next
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        self.do_peek(self.iter.idx(index))
     }
 }
 
@@ -1376,6 +1532,7 @@ mod tests {
     use super::*;
     use prelude::*;
 
+    use cmp;
     use uint;
 
     #[test]
@@ -1768,6 +1925,43 @@ mod tests {
         assert_eq!(it.next_back(), None)
     }
 
+    #[cfg(test)]
+    fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
+    {
+        let mut b = a.clone();
+        assert_eq!(len, b.indexable());
+        let mut n = 0;
+        for a.enumerate().advance |(i, elt)| {
+            assert_eq!(Some(elt), b.idx(i));
+            n += 1;
+        }
+        assert_eq!(n, len);
+        assert_eq!(None, b.idx(n));
+        // call recursively to check after picking off an element
+        if len > 0 {
+            b.next();
+            check_randacc_iter(b, len-1);
+        }
+    }
+
+
+    #[test]
+    fn test_double_ended_flat_map() {
+        let u = [0u,1];
+        let v = [5,6,7,8];
+        let mut it = u.iter().flat_map_(|x| v.slice(*x, v.len()).iter());
+        assert_eq!(it.next_back().unwrap(), &8);
+        assert_eq!(it.next().unwrap(),      &5);
+        assert_eq!(it.next_back().unwrap(), &7);
+        assert_eq!(it.next_back().unwrap(), &6);
+        assert_eq!(it.next_back().unwrap(), &8);
+        assert_eq!(it.next().unwrap(),      &6);
+        assert_eq!(it.next_back().unwrap(), &7);
+        assert_eq!(it.next_back(), None);
+        assert_eq!(it.next(),      None);
+        assert_eq!(it.next_back(), None);
+    }
+
     #[test]
     fn test_random_access_chain() {
         let xs = [1, 2, 3, 4, 5];
@@ -1785,5 +1979,71 @@ mod tests {
         assert_eq!(it.idx(0).unwrap(), &3);
         assert_eq!(it.idx(4).unwrap(), &9);
         assert!(it.idx(6).is_none());
+
+        check_randacc_iter(it, xs.len() + ys.len() - 3);
+    }
+
+    #[test]
+    fn test_random_access_enumerate() {
+        let xs = [1, 2, 3, 4, 5];
+        check_randacc_iter(xs.iter().enumerate(), xs.len());
+    }
+
+    #[test]
+    fn test_random_access_zip() {
+        let xs = [1, 2, 3, 4, 5];
+        let ys = [7, 9, 11];
+        check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
+    }
+
+    #[test]
+    fn test_random_access_take() {
+        let xs = [1, 2, 3, 4, 5];
+        let empty: &[int] = [];
+        check_randacc_iter(xs.iter().take_(3), 3);
+        check_randacc_iter(xs.iter().take_(20), xs.len());
+        check_randacc_iter(xs.iter().take_(0), 0);
+        check_randacc_iter(empty.iter().take_(2), 0);
+    }
+
+    #[test]
+    fn test_random_access_skip() {
+        let xs = [1, 2, 3, 4, 5];
+        let empty: &[int] = [];
+        check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
+        check_randacc_iter(empty.iter().skip(2), 0);
+    }
+
+    #[test]
+    fn test_random_access_peek() {
+        let xs = [1, 2, 3, 4, 5];
+
+        // test .transform and .peek_ that don't implement Clone
+        let it = xs.iter().peek_(|_| {});
+        assert_eq!(xs.len(), it.indexable());
+        for xs.iter().enumerate().advance |(i, elt)| {
+            assert_eq!(Some(elt), it.idx(i));
+        }
+
+    }
+
+    #[test]
+    fn test_random_access_transform() {
+        let xs = [1, 2, 3, 4, 5];
+
+        // test .transform and .peek_ that don't implement Clone
+        let it = xs.iter().transform(|x| *x);
+        assert_eq!(xs.len(), it.indexable());
+        for xs.iter().enumerate().advance |(i, elt)| {
+            assert_eq!(Some(*elt), it.idx(i));
+        }
+    }
+
+    #[test]
+    fn test_random_access_cycle() {
+        let xs = [1, 2, 3, 4, 5];
+        let empty: &[int] = [];
+        check_randacc_iter(xs.iter().cycle().take_(27), 27);
+        check_randacc_iter(empty.iter().cycle(), 0);
     }
 }
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index 2aa5f586dd8..fff859321fb 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -23,7 +23,8 @@ use char::Char;
 use clone::Clone;
 use container::{Container, Mutable};
 use iter::Times;
-use iterator::{Iterator, FromIterator, IteratorUtil, Filter, AdditiveIterator, Map};
+use iterator::{Iterator, FromIterator, Extendable, IteratorUtil};
+use iterator::{Filter, AdditiveIterator, Map};
 use libc;
 use num::Zero;
 use option::{None, Option, Some};
@@ -2323,10 +2324,20 @@ impl<T: Iterator<char>> FromIterator<char, T> for ~str {
     fn from_iterator(iterator: &mut T) -> ~str {
         let (lower, _) = iterator.size_hint();
         let mut buf = with_capacity(lower);
+        buf.extend(iterator);
+        buf
+    }
+}
+
+impl<T: Iterator<char>> Extendable<char, T> for ~str {
+    #[inline]
+    fn extend(&mut self, iterator: &mut T) {
+        let (lower, _) = iterator.size_hint();
+        let reserve = lower + self.len();
+        self.reserve_at_least(reserve);
         for iterator.advance |ch| {
-            buf.push_char(ch)
+            self.push_char(ch)
         }
-        buf
     }
 }
 
@@ -2504,6 +2515,16 @@ mod tests {
     }
 
     #[test]
+    fn test_extend() {
+        let data = ~"ประเทศไทย中";
+        let mut cpy = data.clone();
+        let other = "abc";
+        let mut it = other.iter();
+        cpy.extend(&mut it);
+        assert_eq!(cpy, data + other);
+    }
+
+    #[test]
     fn test_clear() {
         let mut empty = ~"";
         empty.clear();
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index 4665f361340..6a0554a8c8d 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -11,7 +11,7 @@
 //! An ordered map and set for integer keys implemented as a radix trie
 
 use prelude::*;
-use iterator::{IteratorUtil, FromIterator};
+use iterator::{IteratorUtil, FromIterator, Extendable};
 use uint;
 use util::{swap, replace};
 
@@ -155,14 +155,18 @@ impl<T> TrieMap<T> {
 }
 
 impl<T, Iter: Iterator<(uint, T)>> FromIterator<(uint, T), Iter> for TrieMap<T> {
-    pub fn from_iterator(iter: &mut Iter) -> TrieMap<T> {
+    fn from_iterator(iter: &mut Iter) -> TrieMap<T> {
         let mut map = TrieMap::new();
+        map.extend(iter);
+        map
+    }
+}
 
+impl<T, Iter: Iterator<(uint, T)>> Extendable<(uint, T), Iter> for TrieMap<T> {
+    fn extend(&mut self, iter: &mut Iter) {
         for iter.advance |(k, v)| {
-            map.insert(k, v);
+            self.insert(k, v);
         }
-
-        map
     }
 }
 
@@ -222,14 +226,18 @@ impl TrieSet {
 }
 
 impl<Iter: Iterator<uint>> FromIterator<uint, Iter> for TrieSet {
-    pub fn from_iterator(iter: &mut Iter) -> TrieSet {
+    fn from_iterator(iter: &mut Iter) -> TrieSet {
         let mut set = TrieSet::new();
+        set.extend(iter);
+        set
+    }
+}
 
+impl<Iter: Iterator<uint>> Extendable<uint, Iter> for TrieSet {
+    fn extend(&mut self, iter: &mut Iter) {
         for iter.advance |elem| {
-            set.insert(elem);
+            self.insert(elem);
         }
-
-        set
     }
 }
 
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index fdfe357ae51..cfd28fcfc5e 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -2106,7 +2106,8 @@ macro_rules! iterator {
 
             #[inline]
             fn size_hint(&self) -> (uint, Option<uint>) {
-                let exact = self.indexable();
+                let diff = (self.end as uint) - (self.ptr as uint);
+                let exact = diff / sys::nonzero_size_of::<T>();
                 (exact, Some(exact))
             }
         }
@@ -2134,23 +2135,19 @@ macro_rules! double_ended_iterator {
     }
 }
 
-macro_rules! random_access_iterator {
-    (impl $name:ident -> $elem:ty) => {
-        impl<'self, T> RandomAccessIterator<$elem> for $name<'self, T> {
-            #[inline]
-            fn indexable(&self) -> uint {
-                let diff = (self.end as uint) - (self.ptr as uint);
-                diff / sys::nonzero_size_of::<T>()
-            }
+impl<'self, T> RandomAccessIterator<&'self T> for VecIterator<'self, T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        let (exact, _) = self.size_hint();
+        exact
+    }
 
-            fn idx(&self, index: uint) -> Option<$elem> {
-                unsafe {
-                    if index < self.indexable() {
-                        cast::transmute(self.ptr.offset(index))
-                    } else {
-                        None
-                    }
-                }
+    fn idx(&self, index: uint) -> Option<&'self T> {
+        unsafe {
+            if index < self.indexable() {
+                cast::transmute(self.ptr.offset(index))
+            } else {
+                None
             }
         }
     }
@@ -2165,7 +2162,6 @@ pub struct VecIterator<'self, T> {
 }
 iterator!{impl VecIterator -> &'self T}
 double_ended_iterator!{impl VecIterator -> &'self T}
-random_access_iterator!{impl VecIterator -> &'self T}
 pub type RevIterator<'self, T> = Invert<VecIterator<'self, T>>;
 
 impl<'self, T> Clone for VecIterator<'self, T> {
@@ -2181,7 +2177,6 @@ pub struct VecMutIterator<'self, T> {
 }
 iterator!{impl VecMutIterator -> &'self mut T}
 double_ended_iterator!{impl VecMutIterator -> &'self mut T}
-random_access_iterator!{impl VecMutIterator -> &'self mut T}
 pub type MutRevIterator<'self, T> = Invert<VecMutIterator<'self, T>>;
 
 /// An iterator that moves out of a vector.