Implement consuming iterators for ~[], remove vec::{consume, consume_reverse, map_consume}.

14 files changed, 123 insertions, 158 deletions

diff --git a/doc/tutorial-container.md b/doc/tutorial-container.md
index 66bd0b9c131..5ed61d69301 100644
--- a/doc/tutorial-container.md
+++ b/doc/tutorial-container.md
@@ -108,7 +108,7 @@ impl Iterator<int> for ZeroStream {
 ## Container iterators
 
 Containers implement iteration over the contained elements by returning an
-iterator object. For example, vectors have four iterators available:
+iterator object. For example, vector slices have four iterators available:
 
 * `vector.iter()`, for immutable references to the elements
 * `vector.mut_iter()`, for mutable references to the elements
diff --git a/src/libextra/json.rs b/src/libextra/json.rs
index 210921aa3d7..71d99479693 100644
--- a/src/libextra/json.rs
+++ b/src/libextra/json.rs
@@ -24,7 +24,6 @@ use std::io::{WriterUtil, ReaderUtil};
 use std::io;
 use std::str;
 use std::to_str;
-use std::vec;
 
 use serialize::Encodable;
 use serialize;
@@ -941,7 +940,7 @@ impl serialize::Decoder for Decoder {
         let name = match self.stack.pop() {
             String(s) => s,
             List(list) => {
-                do vec::consume_reverse(list) |_i, v| {
+                for list.consume_rev_iter().advance |v| {
                     self.stack.push(v);
                 }
                 match self.stack.pop() {
@@ -1059,7 +1058,7 @@ impl serialize::Decoder for Decoder {
         let len = match self.stack.pop() {
             List(list) => {
                 let len = list.len();
-                do vec::consume_reverse(list) |_i, v| {
+                for list.consume_rev_iter().advance |v| {
                     self.stack.push(v);
                 }
                 len
diff --git a/src/libextra/par.rs b/src/libextra/par.rs
index 2d827365681..da046f6b5ce 100644
--- a/src/libextra/par.rs
+++ b/src/libextra/par.rs
@@ -78,11 +78,10 @@ fn map_slices<A:Copy + Send,B:Copy + Send>(
         info!("num_tasks: %?", (num_tasks, futures.len()));
         assert_eq!(num_tasks, futures.len());
 
-        let r = do vec::map_consume(futures) |ys| {
+        do futures.consume_iter().transform |ys| {
             let mut ys = ys;
             ys.get()
-        };
-        r
+        }.collect()
     }
 }
 
diff --git a/src/libextra/test.rs b/src/libextra/test.rs
index 59aed0055d8..313577ac67d 100644
--- a/src/libextra/test.rs
+++ b/src/libextra/test.rs
@@ -477,7 +477,7 @@ fn run_tests(opts: &TestOpts,
     }
 
     // All benchmarks run at the end, in serial.
-    do vec::consume(filtered_benchs) |_, b| {
+    for filtered_benchs.consume_iter().advance |b| {
         callback(TeWait(copy b.desc));
         run_test(!opts.run_benchmarks, b, ch.clone());
         let (test, result) = p.recv();
diff --git a/src/librustc/back/link.rs b/src/librustc/back/link.rs
index 61d39421b7f..a7abc619080 100644
--- a/src/librustc/back/link.rs
+++ b/src/librustc/back/link.rs
@@ -893,7 +893,7 @@ pub fn link_args(sess: Session,
     // Add all the link args for external crates.
     do cstore::iter_crate_data(cstore) |crate_num, _| {
         let link_args = csearch::get_link_args_for_crate(cstore, crate_num);
-        do vec::consume(link_args) |_, link_arg| {
+        for link_args.consume_iter().advance |link_arg| {
             args.push(link_arg);
         }
     }
diff --git a/src/librustc/driver/driver.rs b/src/librustc/driver/driver.rs
index a32f54fe7bb..3c507547448 100644
--- a/src/librustc/driver/driver.rs
+++ b/src/librustc/driver/driver.rs
@@ -123,10 +123,10 @@ pub fn build_configuration(sess: Session, argv0: @str, input: &input) ->
 // Convert strings provided as --cfg [cfgspec] into a crate_cfg
 fn parse_cfgspecs(cfgspecs: ~[~str],
                   demitter: diagnostic::Emitter) -> ast::crate_cfg {
-    do vec::map_consume(cfgspecs) |s| {
+    do cfgspecs.consume_iter().transform |s| {
         let sess = parse::new_parse_sess(Some(demitter));
         parse::parse_meta_from_source_str(@"cfgspec", s.to_managed(), ~[], sess)
-    }
+    }.collect()
 }
 
 pub enum input {
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index e345a9d703c..ce9ab790b11 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -24,7 +24,6 @@ use std::u16;
 use std::u32;
 use std::u64;
 use std::u8;
-use std::vec;
 use extra::smallintmap::SmallIntMap;
 use syntax::attr;
 use syntax::codemap::span;
@@ -987,7 +986,7 @@ fn lint_session() -> visit::vt<@mut Context> {
         match cx.tcx.sess.lints.pop(&id) {
             None => {},
             Some(l) => {
-                do vec::consume(l) |_, (lint, span, msg)| {
+                for l.consume_iter().advance |(lint, span, msg)| {
                     cx.span_lint(lint, span, msg)
                 }
             }
diff --git a/src/libstd/at_vec.rs b/src/libstd/at_vec.rs
index 325ce097cd5..cadd58118ed 100644
--- a/src/libstd/at_vec.rs
+++ b/src/libstd/at_vec.rs
@@ -17,8 +17,7 @@ use kinds::Copy;
 use option::Option;
 use sys;
 use uint;
-use vec;
-use vec::ImmutableVector;
+use vec::{ImmutableVector, OwnedVector};
 
 /// Code for dealing with @-vectors. This is pretty incomplete, and
 /// contains a bunch of duplication from the code for ~-vectors.
@@ -159,7 +158,7 @@ pub fn to_managed_consume<T>(v: ~[T]) -> @[T] {
     let mut av = @[];
     unsafe {
         raw::reserve(&mut av, v.len());
-        do vec::consume(v) |_i, x| {
+        for v.consume_iter().advance |x| {
             raw::push(&mut av, x);
         }
         transmute(av)
diff --git a/src/libstd/either.rs b/src/libstd/either.rs
index b6da93f9d40..8b9b3102831 100644
--- a/src/libstd/either.rs
+++ b/src/libstd/either.rs
@@ -73,7 +73,7 @@ pub fn rights<T, U: Copy>(eithers: &[Either<T, U>]) -> ~[U] {
 pub fn partition<T, U>(eithers: ~[Either<T, U>]) -> (~[T], ~[U]) {
     let mut lefts: ~[T] = ~[];
     let mut rights: ~[U] = ~[];
-    do vec::consume(eithers) |_i, elt| {
+    for eithers.consume_iter().advance |elt| {
         match elt {
             Left(l) => lefts.push(l),
             Right(r) => rights.push(r)
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index 85dca1154bc..2d80dc2be15 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -24,7 +24,7 @@ use rand::RngUtil;
 use rand;
 use uint;
 use vec;
-use vec::{ImmutableVector, MutableVector};
+use vec::{ImmutableVector, MutableVector, OwnedVector};
 use kinds::Copy;
 use util::{replace, unreachable};
 
@@ -175,7 +175,8 @@ impl<K:Hash + Eq,V> HashMap<K, V> {
                                   vec::from_fn(new_capacity, |_| None));
 
         self.size = 0;
-        do vec::consume(old_buckets) |_, bucket| {
+        // consume_rev_iter is more efficient
+        for old_buckets.consume_rev_iter().advance |bucket| {
             self.insert_opt_bucket(bucket);
         }
     }
@@ -441,7 +442,7 @@ impl<K: Hash + Eq, V> HashMap<K, V> {
                               vec::from_fn(INITIAL_CAPACITY, |_| None));
         self.size = 0;
 
-        do vec::consume(buckets) |_, bucket| {
+        for buckets.consume_iter().advance |bucket| {
             match bucket {
                 None => {},
                 Some(Bucket{key, value, _}) => {
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 28532bd54e3..3fa9df2a9e0 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -277,67 +277,6 @@ pub fn rsplitn<T:Copy>(v: &[T], n: uint, f: &fn(t: &T) -> bool) -> ~[~[T]] {
     result
 }
 
-/// Consumes all elements, in a vector, moving them out into the / closure
-/// provided. The vector is traversed from the start to the end.
-///
-/// This method does not impose any requirements on the type of the vector being
-/// consumed, but it prevents any usage of the vector after this function is
-/// called.
-///
-/// # Examples
-///
-/// ~~~ {.rust}
-/// let v = ~[~"a", ~"b"];
-/// do vec::consume(v) |i, s| {
-///   // s has type ~str, not &~str
-///   io::println(s + fmt!(" %d", i));
-/// }
-/// ~~~
-pub fn consume<T>(mut v: ~[T], f: &fn(uint, v: T)) {
-    unsafe {
-        do as_mut_buf(v) |p, ln| {
-            for uint::range(0, ln) |i| {
-                // NB: This unsafe operation counts on init writing 0s to the
-                // holes we create in the vector. That ensures that, if the
-                // iterator fails then we won't try to clean up the consumed
-                // elements during unwinding
-                let x = intrinsics::init();
-                let p = ptr::mut_offset(p, i);
-                f(i, ptr::replace_ptr(p, x));
-            }
-        }
-
-        raw::set_len(&mut v, 0);
-    }
-}
-
-/// Consumes all elements, in a vector, moving them out into the / closure
-/// provided. The vectors is traversed in reverse order (from end to start).
-///
-/// This method does not impose any requirements on the type of the vector being
-/// consumed, but it prevents any usage of the vector after this function is
-/// called.
-pub fn consume_reverse<T>(mut v: ~[T], f: &fn(uint, v: T)) {
-    unsafe {
-        do as_mut_buf(v) |p, ln| {
-            let mut i = ln;
-            while i > 0 {
-                i -= 1;
-
-                // NB: This unsafe operation counts on init writing 0s to the
-                // holes we create in the vector. That ensures that, if the
-                // iterator fails then we won't try to clean up the consumed
-                // elements during unwinding
-                let x = intrinsics::init();
-                let p = ptr::mut_offset(p, i);
-                f(i, ptr::replace_ptr(p, x));
-            }
-        }
-
-        raw::set_len(&mut v, 0);
-    }
-}
-
 // Appending
 
 /// Iterates over the `rhs` vector, copying each element and appending it to the
@@ -360,20 +299,6 @@ pub fn append_one<T>(lhs: ~[T], x: T) -> ~[T] {
 
 // Functional utilities
 
-/// Consumes a vector, mapping it into a different vector. This function takes
-/// ownership of the supplied vector `v`, moving each element into the closure
-/// provided to generate a new element. The vector of new elements is then
-/// returned.
-///
-/// The original vector `v` cannot be used after this function call (it is moved
-/// inside), but there are no restrictions on the type of the vector.
-pub fn map_consume<T, U>(v: ~[T], f: &fn(v: T) -> U) -> ~[U] {
-    let mut result = ~[];
-    do consume(v) |_i, x| {
-        result.push(f(x));
-    }
-    result
-}
 /**
  * Apply a function to each element of a vector and return a concatenation
  * of each result vector
@@ -396,7 +321,7 @@ pub fn filter_map<T, U>(
      */
 
     let mut result = ~[];
-    do consume(v) |_, elem| {
+    for v.consume_iter().advance |elem| {
         match f(elem) {
             None => {}
             Some(result_elem) => { result.push(result_elem); }
@@ -434,9 +359,7 @@ pub fn filter_mapped<T, U: Copy>(
  */
 pub fn filter<T>(v: ~[T], f: &fn(t: &T) -> bool) -> ~[T] {
     let mut result = ~[];
-    // FIXME (#4355 maybe): using v.consume here crashes
-    // do v.consume |_, elem| {
-    do consume(v) |_, elem| {
+    for v.consume_iter().advance |elem| {
         if f(&elem) { result.push(elem); }
     }
     result
@@ -542,7 +465,7 @@ pub fn unzip_slice<T:Copy,U:Copy>(v: &[(T, U)]) -> (~[T], ~[U]) {
 pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
     let mut ts = ~[];
     let mut us = ~[];
-    do consume(v) |_i, p| {
+    for v.consume_iter().advance |p| {
         let (t, u) = p;
         ts.push(t);
         us.push(u);
@@ -1202,6 +1125,9 @@ impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
 
 #[allow(missing_doc)]
 pub trait OwnedVector<T> {
+    fn consume_iter(self) -> VecConsumeIterator<T>;
+    fn consume_rev_iter(self) -> VecConsumeRevIterator<T>;
+
     fn reserve(&mut self, n: uint);
     fn reserve_at_least(&mut self, n: uint);
     fn capacity(&self) -> uint;
@@ -1218,14 +1144,38 @@ pub trait OwnedVector<T> {
     fn swap_remove(&mut self, index: uint) -> T;
     fn truncate(&mut self, newlen: uint);
     fn retain(&mut self, f: &fn(t: &T) -> bool);
-    fn consume(self, f: &fn(uint, v: T));
-    fn consume_reverse(self, f: &fn(uint, v: T));
     fn filter(self, f: &fn(t: &T) -> bool) -> ~[T];
     fn partition(self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
     fn grow_fn(&mut self, n: uint, op: &fn(uint) -> T);
 }
 
 impl<T> OwnedVector<T> for ~[T] {
+    /// Creates a consuming iterator, that is, one that moves each
+    /// value out of the vector (from start to end). The vector cannot
+    /// be used after calling this.
+    ///
+    /// Note that this performs O(n) swaps, and so `consume_rev_iter`
+    /// (which just calls `pop` repeatedly) is more efficient.
+    ///
+    /// # Examples
+    ///
+    /// ~~~ {.rust}
+    /// let v = ~[~"a", ~"b"];
+    /// for v.consume_iter().advance |s| {
+    ///   // s has type ~str, not &~str
+    ///   println(s);
+    /// }
+    /// ~~~
+    fn consume_iter(self) -> VecConsumeIterator<T> {
+        VecConsumeIterator { v: self, idx: 0 }
+    }
+    /// Creates a consuming iterator that moves out of the vector in
+    /// reverse order. Also see `consume_iter`, however note that this
+    /// is more efficient.
+    fn consume_rev_iter(self) -> VecConsumeRevIterator<T> {
+        VecConsumeRevIterator { v: self }
+    }
+
     /**
      * Reserves capacity for exactly `n` elements in the given vector.
      *
@@ -1533,16 +1483,6 @@ impl<T> OwnedVector<T> for ~[T] {
     }
 
     #[inline]
-    fn consume(self, f: &fn(uint, v: T)) {
-        consume(self, f)
-    }
-
-    #[inline]
-    fn consume_reverse(self, f: &fn(uint, v: T)) {
-        consume_reverse(self, f)
-    }
-
-    #[inline]
     fn filter(self, f: &fn(&T) -> bool) -> ~[T] {
         filter(self, f)
     }
@@ -1556,7 +1496,7 @@ impl<T> OwnedVector<T> for ~[T] {
         let mut lefts  = ~[];
         let mut rights = ~[];
 
-        do self.consume |_, elt| {
+        for self.consume_iter().advance |elt| {
             if f(&elt) {
                 lefts.push(elt);
             } else {
@@ -2132,7 +2072,7 @@ macro_rules! iterator {
 }
 
 //iterator!{struct VecIterator -> *T, &'self T}
-/// An iterator for iterating over a vector
+/// An iterator for iterating over a vector.
 pub struct VecIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
@@ -2141,7 +2081,7 @@ pub struct VecIterator<'self, T> {
 iterator!{impl VecIterator -> &'self T, 1}
 
 //iterator!{struct VecRevIterator -> *T, &'self T}
-/// An iterator for iterating over a vector in reverse
+/// An iterator for iterating over a vector in reverse.
 pub struct VecRevIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
@@ -2150,7 +2090,7 @@ pub struct VecRevIterator<'self, T> {
 iterator!{impl VecRevIterator -> &'self T, -1}
 
 //iterator!{struct VecMutIterator -> *mut T, &'self mut T}
-/// An iterator for mutating the elements of a vector
+/// An iterator for mutating the elements of a vector.
 pub struct VecMutIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
@@ -2159,7 +2099,7 @@ pub struct VecMutIterator<'self, T> {
 iterator!{impl VecMutIterator -> &'self mut T, 1}
 
 //iterator!{struct VecMutRevIterator -> *mut T, &'self mut T}
-/// An iterator for mutating the elements of a vector in reverse
+/// An iterator for mutating the elements of a vector in reverse.
 pub struct VecMutRevIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
@@ -2167,6 +2107,49 @@ pub struct VecMutRevIterator<'self, T> {
 }
 iterator!{impl VecMutRevIterator -> &'self mut T, -1}
 
+/// An iterator that moves out of a vector.
+pub struct VecConsumeIterator<T> {
+    priv v: ~[T],
+    priv idx: uint,
+}
+
+impl<T> Iterator<T> for VecConsumeIterator<T> {
+    fn next(&mut self) -> Option<T> {
+        // this is peculiar, but is required for safety with respect
+        // to dtors. It traverses the first half of the vec, and
+        // removes them by swapping them with the last element (and
+        // popping), which results in the second half in reverse
+        // order, and so these can just be pop'd off. That is,
+        //
+        // [1,2,3,4,5] => 1, [5,2,3,4] => 2, [5,4,3] => 3, [5,4] => 4,
+        // [5] -> 5, []
+
+        if self.v.is_empty() {
+            None
+        } else {
+            let l = self.v.len();
+            if self.idx < l {
+                self.v.swap(self.idx, l - 1);
+                self.idx += 1;
+            }
+
+            Some(self.v.pop())
+        }
+    }
+}
+
+/// An iterator that moves out of a vector in reverse order.
+pub struct VecConsumeRevIterator<T> {
+    priv v: ~[T]
+}
+
+impl<T> Iterator<T> for VecConsumeRevIterator<T> {
+    fn next(&mut self) -> Option<T> {
+        if self.v.is_empty() { None }
+        else { Some(self.v.pop()) }
+    }
+}
+
 #[cfg(stage0)]
 impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
     pub fn from_iterator(iterator: &mut T) -> ~[A] {
@@ -3203,20 +3186,6 @@ mod tests {
     #[test]
     #[ignore(windows)]
     #[should_fail]
-    fn test_consume_fail() {
-        let v = ~[(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do consume(v) |_i, _elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
     #[allow(non_implicitly_copyable_typarams)]
     fn test_grow_fn_fail() {
         let mut v = ~[];
@@ -3246,21 +3215,6 @@ mod tests {
     #[test]
     #[ignore(windows)]
     #[should_fail]
-    fn test_map_consume_fail() {
-        let v = ~[(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do map_consume(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            ~[(~0, @0)]
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
     fn test_flat_map_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
@@ -3429,6 +3383,20 @@ mod tests {
     }
 
     #[test]
+    fn test_consume_iterator() {
+        use iterator::*;
+        let xs = ~[1u,2,3,4,5];
+        assert_eq!(xs.consume_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
+    }
+
+    #[test]
+    fn test_consume_rev_iterator() {
+        use iterator::*;
+        let xs = ~[1u,2,3,4,5];
+        assert_eq!(xs.consume_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
+    }
+
+    #[test]
     fn test_move_from() {
         let mut a = [1,2,3,4,5];
         let b = ~[6,7,8];
diff --git a/src/libsyntax/ext/fmt.rs b/src/libsyntax/ext/fmt.rs
index 76073199f64..333570b6c9d 100644
--- a/src/libsyntax/ext/fmt.rs
+++ b/src/libsyntax/ext/fmt.rs
@@ -22,7 +22,6 @@ use ext::build::AstBuilder;
 
 use std::option;
 use std::unstable::extfmt::ct::*;
-use std::vec;
 use parse::token::{str_to_ident};
 
 pub fn expand_syntax_ext(cx: @ExtCtxt, sp: span, tts: &[ast::token_tree])
@@ -268,7 +267,7 @@ fn pieces_to_expr(cx: @ExtCtxt, sp: span,
        corresponding function in std::unstable::extfmt. Each function takes a
        buffer to insert data into along with the data being formatted. */
     let npieces = pieces.len();
-    do vec::consume(pieces) |i, pc| {
+    for pieces.consume_iter().enumerate().advance |(i, pc)| {
         match pc {
             /* Raw strings get appended via str::push_str */
             PieceString(s) => {
diff --git a/src/test/bench/graph500-bfs.rs b/src/test/bench/graph500-bfs.rs
index bc5efc5fca1..d327b73c625 100644
--- a/src/test/bench/graph500-bfs.rs
+++ b/src/test/bench/graph500-bfs.rs
@@ -95,13 +95,13 @@ fn make_graph(N: uint, edges: ~[(node_id, node_id)]) -> graph {
         }
     }
 
-    do vec::map_consume(graph) |mut v| {
+    do graph.consume_iter().transform |mut v| {
         let mut vec = ~[];
         do v.consume |i| {
             vec.push(i);
         }
         vec
-    }
+    }.collect()
 }
 
 fn gen_search_keys(graph: &[~[node_id]], n: uint) -> ~[node_id] {
diff --git a/src/test/bench/task-perf-one-million.rs b/src/test/bench/task-perf-one-million.rs
index e1366a3a869..1cd90962c5b 100644
--- a/src/test/bench/task-perf-one-million.rs
+++ b/src/test/bench/task-perf-one-million.rs
@@ -28,20 +28,21 @@ fn calc(children: uint, parent_wait_chan: &Chan<Chan<Chan<int>>>) {
         wait_port
     };
 
-    let child_start_chans: ~[Chan<Chan<int>>] = vec::map_consume(wait_ports, |port| port.recv());
+    let child_start_chans: ~[Chan<Chan<int>>] =
+        wait_ports.consume_iter().transform(|port| port.recv()).collect();
 
     let (start_port, start_chan) = stream::<Chan<int>>();
     parent_wait_chan.send(start_chan);
     let parent_result_chan: Chan<int> = start_port.recv();
 
-    let child_sum_ports: ~[Port<int>] = do vec::map_consume(child_start_chans) |child_start_chan| {
-        let (child_sum_port, child_sum_chan) = stream::<int>();
-        child_start_chan.send(child_sum_chan);
-        child_sum_port
-    };
+    let child_sum_ports: ~[Port<int>] =
+        do child_start_chans.consume_iter().transform |child_start_chan| {
+            let (child_sum_port, child_sum_chan) = stream::<int>();
+            child_start_chan.send(child_sum_chan);
+            child_sum_port
+    }.collect();
 
-    let mut sum = 0;
-    vec::consume(child_sum_ports, |_, sum_port| sum += sum_port.recv() );
+    let sum = child_sum_ports.consume_iter().fold(0, |sum, sum_port| sum + sum_port.recv() );
 
     parent_result_chan.send(sum + 1);
 }