auto merge of #7015 : huonw/rust/each-fn-kill, r=thestinger

Continuation of #6995/#6999.

78 files changed, 447 insertions, 951 deletions

diff --git a/src/compiletest/procsrv.rs b/src/compiletest/procsrv.rs
index 62f0731dab6..f86ab2c9093 100644
--- a/src/compiletest/procsrv.rs
+++ b/src/compiletest/procsrv.rs
@@ -10,14 +10,9 @@
 
 use core::prelude::*;
 
-use core::comm;
-use core::io;
-use core::libc::c_int;
 use core::os;
 use core::run;
 use core::str;
-use core::task;
-use core::vec;
 
 #[cfg(target_os = "win32")]
 fn target_env(lib_path: &str, prog: &str) -> ~[(~str,~str)] {
@@ -74,4 +69,3 @@ pub fn run(lib_path: &str,
         err: str::from_bytes(output.error)
     }
 }
-
diff --git a/src/compiletest/runtest.rs b/src/compiletest/runtest.rs
index c174057aaaa..1015373d7ce 100644
--- a/src/compiletest/runtest.rs
+++ b/src/compiletest/runtest.rs
@@ -22,6 +22,7 @@ use procsrv;
 use util;
 use util::logv;
 
+use core::iterator::IteratorUtil;
 use core::io;
 use core::os;
 use core::str;
@@ -780,7 +781,7 @@ fn _arm_exec_compiled_test(config: &config, props: &TestProps,
                      Some(~""));
 
     let mut exitcode : int = 0;
-    for str::each_char(exitcode_out) |c| {
+    for exitcode_out.iter().advance |c| {
         if !c.is_digit() { break; }
         exitcode = exitcode * 10 + match c {
             '0' .. '9' => c as int - ('0' as int),
diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs
index 52e2b75d6b6..7fac125243e 100644
--- a/src/libextra/dlist.rs
+++ b/src/libextra/dlist.rs
@@ -20,6 +20,7 @@ Do not use ==, !=, <, etc on doubly-linked lists -- it may not terminate.
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::managed;
 use core::old_iter;
 use core::vec;
@@ -110,7 +111,7 @@ pub fn from_elem<T>(data: T) -> @mut DList<T> {
 
 /// Creates a new dlist from a vector of elements, maintaining the same order
 pub fn from_vec<T:Copy>(vec: &[T]) -> @mut DList<T> {
-    do vec::foldl(DList(), vec) |list,data| {
+    do vec.iter().fold(DList()) |list,data| {
         list.push(*data); // Iterating left-to-right -- add newly to the tail.
         list
     }
diff --git a/src/libextra/fileinput.rs b/src/libextra/fileinput.rs
index 3afa9b51c59..16082732715 100644
--- a/src/libextra/fileinput.rs
+++ b/src/libextra/fileinput.rs
@@ -414,6 +414,7 @@ mod test {
 
     use super::{FileInput, pathify, input_vec, input_vec_state};
 
+    use core::iterator::IteratorUtil;
     use core::io;
     use core::str;
     use core::uint;
@@ -455,7 +456,7 @@ mod test {
 
         let fi = FileInput::from_vec(copy filenames);
 
-        for "012".each_chari |line, c| {
+        for "012".iter().enumerate().advance |(line, c)| {
             assert_eq!(fi.read_byte(), c as int);
             assert_eq!(fi.state().line_num, line);
             assert_eq!(fi.state().line_num_file, 0);
diff --git a/src/libextra/flate.rs b/src/libextra/flate.rs
index 076126e0432..0fde03b69cb 100644
--- a/src/libextra/flate.rs
+++ b/src/libextra/flate.rs
@@ -16,8 +16,6 @@ Simple compression
 
 #[allow(missing_doc)];
 
-use core::prelude::*;
-
 use core::libc::{c_void, size_t, c_int};
 use core::libc;
 use core::vec;
@@ -87,6 +85,7 @@ mod tests {
     use super::*;
     use core::rand;
     use core::rand::RngUtil;
+    use core::prelude::*;
 
     #[test]
     #[allow(non_implicitly_copyable_typarams)]
diff --git a/src/libextra/flatpipes.rs b/src/libextra/flatpipes.rs
index e8239b9f7fd..c0f619c1b85 100644
--- a/src/libextra/flatpipes.rs
+++ b/src/libextra/flatpipes.rs
@@ -654,7 +654,6 @@ mod test {
     use core::int;
     use core::io::BytesWriter;
     use core::result;
-    use core::sys;
     use core::task;
 
     #[test]
diff --git a/src/libextra/json.rs b/src/libextra/json.rs
index 22abe0edbb9..fc1597ffed4 100644
--- a/src/libextra/json.rs
+++ b/src/libextra/json.rs
@@ -18,6 +18,7 @@
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::char;
 use core::float;
 use core::hashmap::HashMap;
@@ -58,7 +59,7 @@ pub struct Error {
 
 fn escape_str(s: &str) -> ~str {
     let mut escaped = ~"\"";
-    for str::each_char(s) |c| {
+    for s.iter().advance |c| {
         match c {
           '"' => escaped += "\\\"",
           '\\' => escaped += "\\\\",
@@ -913,7 +914,8 @@ impl serialize::Decoder for Decoder {
 
     fn read_char(&mut self) -> char {
         let mut v = ~[];
-        for str::each_char(self.read_str()) |c| { v.push(c) }
+        let s = self.read_str();
+        for s.iter().advance |c| { v.push(c) }
         if v.len() != 1 { fail!("string must have one character") }
         v[0]
     }
diff --git a/src/libextra/list.rs b/src/libextra/list.rs
index 7a38be8944f..0d0b5ea00f0 100644
--- a/src/libextra/list.rs
+++ b/src/libextra/list.rs
@@ -12,7 +12,7 @@
 
 use core::prelude::*;
 
-use core::vec;
+use core::iterator::IteratorUtil;
 
 #[deriving(Eq)]
 pub enum List<T> {
@@ -28,7 +28,7 @@ pub enum MutList<T> {
 
 /// Create a list from a vector
 pub fn from_vec<T:Copy>(v: &[T]) -> @List<T> {
-    vec::foldr(v, @Nil::<T>, |h, t| @Cons(*h, t))
+    v.rev_iter().fold(@Nil::<T>, |t, h| @Cons(*h, t))
 }
 
 /**
diff --git a/src/libextra/net_url.rs b/src/libextra/net_url.rs
index 08540775864..f26019d9282 100644
--- a/src/libextra/net_url.rs
+++ b/src/libextra/net_url.rs
@@ -14,6 +14,7 @@
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::cmp::Eq;
 use core::io::{Reader, ReaderUtil};
 use core::io;
@@ -358,7 +359,7 @@ pub fn query_to_str(query: &Query) -> ~str {
 
 // returns the scheme and the rest of the url, or a parsing error
 pub fn get_scheme(rawurl: &str) -> Result<(~str, ~str), ~str> {
-    for str::each_chari(rawurl) |i,c| {
+    for rawurl.iter().enumerate().advance |(i,c)| {
         match c {
           'A' .. 'Z' | 'a' .. 'z' => loop,
           '0' .. '9' | '+' | '-' | '.' => {
@@ -418,7 +419,7 @@ fn get_authority(rawurl: &str) ->
     let mut colon_count = 0;
     let mut (pos, begin, end) = (0, 2, len);
 
-    for str::each_chari(rawurl) |i,c| {
+    for rawurl.iter().enumerate().advance |(i,c)| {
         if i < 2 { loop; } // ignore the leading //
 
         // deal with input class first
@@ -562,7 +563,7 @@ fn get_path(rawurl: &str, authority: bool) ->
     Result<(~str, ~str), ~str> {
     let len = str::len(rawurl);
     let mut end = len;
-    for str::each_chari(rawurl) |i,c| {
+    for rawurl.iter().enumerate().advance |(i,c)| {
         match c {
           'A' .. 'Z' | 'a' .. 'z' | '0' .. '9' | '&' |'\'' | '(' | ')' | '.'
           | '@' | ':' | '%' | '/' | '+' | '!' | '*' | ',' | ';' | '='
diff --git a/src/libextra/num/bigint.rs b/src/libextra/num/bigint.rs
index 77eef1d67ef..1411079d52f 100644
--- a/src/libextra/num/bigint.rs
+++ b/src/libextra/num/bigint.rs
@@ -19,7 +19,7 @@ A BigInt is a combination of BigUint and Sign.
 #[allow(missing_doc)];
 
 use core::prelude::*;
-
+use core::iterator::IteratorUtil;
 use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
 use core::int;
 use core::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix, Orderable};
@@ -129,12 +129,9 @@ impl TotalOrd for BigUint {
         if s_len < o_len { return Less; }
         if s_len > o_len { return Greater;  }
 
-        for self.data.eachi_reverse |i, elm| {
-            match (*elm, other.data[i]) {
-                (l, r) if l < r => return Less,
-                (l, r) if l > r => return Greater,
-                _               => loop
-            };
+        for self.data.rev_iter().zip(other.data.rev_iter()).advance |(&self_i, &other_i)| {
+            cond!((self_i < other_i) { return Less; }
+                  (self_i > other_i) { return Greater; })
         }
         return Equal;
     }
@@ -421,7 +418,7 @@ impl Integer for BigUint {
             let bn = *b.data.last();
             let mut d = ~[];
             let mut carry = 0;
-            for an.each_reverse |elt| {
+            for an.rev_iter().advance |elt| {
                 let ai = BigDigit::to_uint(carry, *elt);
                 let di = ai / (bn as uint);
                 assert!(di < BigDigit::base);
@@ -648,7 +645,7 @@ impl BigUint {
 
         let mut borrow = 0;
         let mut shifted = ~[];
-        for self.data.each_reverse |elem| {
+        for self.data.rev_iter().advance |elem| {
             shifted = ~[(*elem >> n_bits) | borrow] + shifted;
             borrow = *elem << (BigDigit::bits - n_bits);
         }
diff --git a/src/libextra/par.rs b/src/libextra/par.rs
index 49696a5fa25..23b7cdc0997 100644
--- a/src/libextra/par.rs
+++ b/src/libextra/par.rs
@@ -10,6 +10,7 @@
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::cast;
 use core::ptr;
 use core::sys;
@@ -122,25 +123,24 @@ pub fn alli<A:Copy + Owned>(
     xs: &[A],
     fn_factory: &fn() -> ~fn(uint, &A) -> bool) -> bool
 {
-    do vec::all(map_slices(xs, || {
+    let mapped = map_slices(xs, || {
         let f = fn_factory();
         let result: ~fn(uint, &[A]) -> bool = |base, slice| {
-            vec::alli(slice, |i, x| {
-                f(i + base, x)
-            })
+            slice.iter().enumerate().all(|(i, x)| f(i + base, x))
         };
         result
-    })) |x| { *x }
+    });
+    mapped.iter().all(|&x| x)
 }
 
 /// Returns true if the function holds for any elements in the vector.
 pub fn any<A:Copy + Owned>(
     xs: &[A],
     fn_factory: &fn() -> ~fn(&A) -> bool) -> bool {
-    do vec::any(map_slices(xs, || {
+    let mapped = map_slices(xs, || {
         let f = fn_factory();
-        let result: ~fn(uint, &[A]) -> bool =
-            |_, slice| vec::any(slice, |x| f(x));
+        let result: ~fn(uint, &[A]) -> bool = |_, slice| slice.iter().any(f);
         result
-    })) |x| { *x }
+    });
+    mapped.iter().any(|&x| x)
 }
diff --git a/src/libextra/sort.rs b/src/libextra/sort.rs
index 420c63efab5..26d1e28e122 100644
--- a/src/libextra/sort.rs
+++ b/src/libextra/sort.rs
@@ -929,11 +929,8 @@ mod test_tim_sort {
     use core::prelude::*;
 
     use sort::tim_sort;
-
-    use core::local_data;
     use core::rand::RngUtil;
     use core::rand;
-    use core::uint;
     use core::vec;
 
     struct CVal {
diff --git a/src/libextra/stats.rs b/src/libextra/stats.rs
index d224777ded7..0cc1ee9a1d7 100644
--- a/src/libextra/stats.rs
+++ b/src/libextra/stats.rs
@@ -12,6 +12,7 @@
 
 use core::prelude::*;
 
+use core::iterator::*;
 use core::vec;
 use core::f64;
 use core::cmp;
@@ -36,17 +37,17 @@ pub trait Stats {
 
 impl<'self> Stats for &'self [f64] {
     fn sum(self) -> f64 {
-        vec::foldl(0.0, self, |p,q| p + *q)
+        self.iter().fold(0.0, |p,q| p + *q)
     }
 
     fn min(self) -> f64 {
         assert!(self.len() != 0);
-        vec::foldl(self[0], self, |p,q| cmp::min(p, *q))
+        self.iter().fold(self[0], |p,q| cmp::min(p, *q))
     }
 
     fn max(self) -> f64 {
         assert!(self.len() != 0);
-        vec::foldl(self[0], self, |p,q| cmp::max(p, *q))
+        self.iter().fold(self[0], |p,q| cmp::max(p, *q))
     }
 
     fn mean(self) -> f64 {
diff --git a/src/libextra/std.rc b/src/libextra/std.rc
index 4e9a547e141..83c0bb516b4 100644
--- a/src/libextra/std.rc
+++ b/src/libextra/std.rc
@@ -148,4 +148,3 @@ pub mod extra {
     pub use serialize;
     pub use test;
 }
-
diff --git a/src/libextra/sync.rs b/src/libextra/sync.rs
index 28a5e5382be..8bbe0afa704 100644
--- a/src/libextra/sync.rs
+++ b/src/libextra/sync.rs
@@ -731,7 +731,6 @@ mod tests {
     use core::cast;
     use core::cell::Cell;
     use core::comm;
-    use core::ptr;
     use core::result;
     use core::task;
     use core::vec;
diff --git a/src/libextra/tempfile.rs b/src/libextra/tempfile.rs
index 6d0bd888195..98c57838072 100644
--- a/src/libextra/tempfile.rs
+++ b/src/libextra/tempfile.rs
@@ -34,7 +34,6 @@ mod tests {
     use core::prelude::*;
 
     use tempfile::mkdtemp;
-    use tempfile;
 
     use core::os;
     use core::str;
diff --git a/src/libextra/time.rs b/src/libextra/time.rs
index 758181980a8..dd3e4f48c63 100644
--- a/src/libextra/time.rs
+++ b/src/libextra/time.rs
@@ -16,6 +16,7 @@ use core::i32;
 use core::int;
 use core::io;
 use core::str;
+use core::iterator::IteratorUtil;
 
 static NSEC_PER_SEC: i32 = 1_000_000_000_i32;
 
@@ -261,7 +262,7 @@ impl Tm {
 priv fn do_strptime(s: &str, format: &str) -> Result<Tm, ~str> {
     fn match_str(s: &str, pos: uint, needle: &str) -> bool {
         let mut i = pos;
-        for str::each(needle) |ch| {
+        for needle.bytes_iter().advance |ch| {
             if s[i] != ch {
                 return false;
             }
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
index ebb0cdc120f..9db3d48a3b8 100644
--- a/src/libextra/treemap.rs
+++ b/src/libextra/treemap.rs
@@ -1034,8 +1034,6 @@ mod test_set {
 
     use super::*;
 
-    use core::vec;
-
     #[test]
     fn test_clear() {
         let mut s = TreeSet::new();
diff --git a/src/libextra/uv_ll.rs b/src/libextra/uv_ll.rs
index 2cb2eea8828..2522f149bf4 100644
--- a/src/libextra/uv_ll.rs
+++ b/src/libextra/uv_ll.rs
@@ -1234,7 +1234,6 @@ mod test {
 
     use core::comm::{SharedChan, stream, GenericChan, GenericPort};
     use core::libc;
-    use core::result;
     use core::str;
     use core::sys;
     use core::task;
diff --git a/src/librustc/back/link.rs b/src/librustc/back/link.rs
index 3c10324fd3d..29e7ba0e62f 100644
--- a/src/librustc/back/link.rs
+++ b/src/librustc/back/link.rs
@@ -22,6 +22,7 @@ use middle::trans::common::CrateContext;
 use middle::ty;
 use util::ppaux;
 
+use core::iterator::IteratorUtil;
 use core::char;
 use core::hash::Streaming;
 use core::hash;
@@ -636,7 +637,7 @@ pub fn get_symbol_hash(ccx: @CrateContext, t: ty::t) -> @str {
 // gas accepts the following characters in symbols: a-z, A-Z, 0-9, ., _, $
 pub fn sanitize(s: &str) -> ~str {
     let mut result = ~"";
-    for str::each_char(s) |c| {
+    for s.iter().advance |c| {
         match c {
             // Escape these with $ sequences
             '@' => result += "$SP$",
diff --git a/src/librustc/front/test.rs b/src/librustc/front/test.rs
index cda7d1fa937..5d0de535629 100644
--- a/src/librustc/front/test.rs
+++ b/src/librustc/front/test.rs
@@ -22,7 +22,6 @@ use syntax::codemap::{dummy_sp, span, ExpandedFrom, CallInfo, NameAndSpan};
 use syntax::codemap;
 use syntax::ext::base::ExtCtxt;
 use syntax::fold;
-use syntax::parse::token;
 use syntax::print::pprust;
 use syntax::{ast, ast_util};
 
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index b50c158f37a..98f8efb72c8 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -19,6 +19,7 @@ use middle::typeck::method_map;
 use middle::moves;
 use util::ppaux::ty_to_str;
 
+use core::iterator::IteratorUtil;
 use core::uint;
 use core::vec;
 use extra::sort;
@@ -242,7 +243,7 @@ pub fn is_useful(cx: @MatchCheckCtxt, m: &matrix, v: &[@pat]) -> useful {
                 not_useful
               }
               ty::ty_unboxed_vec(*) | ty::ty_evec(*) => {
-                let max_len = do m.foldr(0) |r, max_len| {
+                let max_len = do m.rev_iter().fold(0) |max_len, r| {
                   match r[0].node {
                     pat_vec(ref before, _, ref after) => {
                       uint::max(before.len() + after.len(), max_len)
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index 0327a8e81c7..45447d3993c 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -18,6 +18,7 @@ use middle;
 use syntax::{ast, ast_map, ast_util, visit};
 use syntax::ast::*;
 
+use core::iterator::IteratorUtil;
 use core::float;
 use core::hashmap::{HashMap, HashSet};
 use core::vec;
@@ -72,7 +73,7 @@ pub fn join(a: constness, b: constness) -> constness {
 }
 
 pub fn join_all(cs: &[constness]) -> constness {
-    vec::foldl(integral_const, cs, |a, b| join(a, *b))
+    cs.iter().fold(integral_const, |a, b| join(a, *b))
 }
 
 pub fn classify(e: @expr,
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 3097be242a1..8a9a67db802 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -110,6 +110,7 @@ use middle::ty;
 use middle::typeck;
 use middle::moves;
 
+use core::iterator::IteratorUtil;
 use core::cast::transmute;
 use core::hashmap::HashMap;
 use core::io;
@@ -923,7 +924,7 @@ impl Liveness {
     pub fn propagate_through_block(&self, blk: &blk, succ: LiveNode)
                                    -> LiveNode {
         let succ = self.propagate_through_opt_expr(blk.node.expr, succ);
-        do blk.node.stmts.foldr(succ) |stmt, succ| {
+        do blk.node.stmts.rev_iter().fold(succ) |succ, stmt| {
             self.propagate_through_stmt(*stmt, succ)
         }
     }
@@ -977,7 +978,7 @@ impl Liveness {
 
     pub fn propagate_through_exprs(&self, exprs: &[@expr], succ: LiveNode)
                                    -> LiveNode {
-        do exprs.foldr(succ) |expr, succ| {
+        do exprs.rev_iter().fold(succ) |succ, expr| {
             self.propagate_through_expr(*expr, succ)
         }
     }
@@ -1021,7 +1022,7 @@ impl Liveness {
                  // the construction of a closure itself is not important,
                  // but we have to consider the closed over variables.
                  let caps = self.ir.captures(expr);
-                 do caps.foldr(succ) |cap, succ| {
+                 do caps.rev_iter().fold(succ) |succ, cap| {
                      self.init_from_succ(cap.ln, succ);
                      let var = self.variable(cap.var_nid, expr.span);
                      self.acc(cap.ln, var, ACC_READ | ACC_USE);
@@ -1159,7 +1160,7 @@ impl Liveness {
 
           expr_struct(_, ref fields, with_expr) => {
             let succ = self.propagate_through_opt_expr(with_expr, succ);
-            do (*fields).foldr(succ) |field, succ| {
+            do fields.rev_iter().fold(succ) |succ, field| {
                 self.propagate_through_expr(field.node.expr, succ)
             }
           }
@@ -1215,10 +1216,10 @@ impl Liveness {
           }
 
           expr_inline_asm(ref ia) =>{
-            let succ = do ia.inputs.foldr(succ) |&(_, expr), succ| {
+            let succ = do ia.inputs.rev_iter().fold(succ) |succ, &(_, expr)| {
                 self.propagate_through_expr(expr, succ)
             };
-            do ia.outputs.foldr(succ) |&(_, expr), succ| {
+            do ia.outputs.rev_iter().fold(succ) |succ, &(_, expr)| {
                 self.propagate_through_expr(expr, succ)
             }
           }
diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs
index a42e1cd0647..49db0ee7bd3 100644
--- a/src/librustc/middle/trans/_match.rs
+++ b/src/librustc/middle/trans/_match.rs
@@ -172,6 +172,7 @@ use middle::trans::type_of;
 use middle::ty;
 use util::common::indenter;
 
+use core::iterator::IteratorUtil;
 use core::hashmap::HashMap;
 use core::vec;
 use syntax::ast;
@@ -798,7 +799,7 @@ pub fn enter_region<'r>(bcx: block,
 pub fn get_options(bcx: block, m: &[@Match], col: uint) -> ~[Opt] {
     let ccx = bcx.ccx();
     fn add_to_set(tcx: ty::ctxt, set: &mut ~[Opt], val: Opt) {
-        if set.any(|l| opt_eq(tcx, l, &val)) {return;}
+        if set.iter().any(|l| opt_eq(tcx, l, &val)) {return;}
         set.push(val);
     }
 
@@ -965,7 +966,7 @@ pub fn collect_record_or_struct_fields(bcx: block,
     fn extend(idents: &mut ~[ast::ident], field_pats: &[ast::field_pat]) {
         for field_pats.each |field_pat| {
             let field_ident = field_pat.ident;
-            if !vec::any(*idents, |x| *x == field_ident) {
+            if !idents.iter().any(|x| *x == field_ident) {
                 idents.push(field_ident);
             }
         }
@@ -976,11 +977,11 @@ pub fn pats_require_rooting(bcx: block,
                             m: &[@Match],
                             col: uint)
                          -> bool {
-    vec::any(m, |br| {
+    do m.iter().any |br| {
         let pat_id = br.pats[col].id;
         let key = root_map_key {id: pat_id, derefs: 0u };
         bcx.ccx().maps.root_map.contains_key(&key)
-    })
+    }
 }
 
 pub fn root_pats_as_necessary(mut bcx: block,
@@ -1005,12 +1006,12 @@ pub fn root_pats_as_necessary(mut bcx: block,
 // matches may be wildcards like _ or identifiers).
 macro_rules! any_pat (
     ($m:expr, $pattern:pat) => (
-        vec::any($m, |br| {
+        do ($m).iter().any |br| {
             match br.pats[col].node {
                 $pattern => true,
                 _ => false
             }
-        })
+        }
     )
 )
 
@@ -1031,7 +1032,7 @@ pub fn any_tup_pat(m: &[@Match], col: uint) -> bool {
 }
 
 pub fn any_tuple_struct_pat(bcx: block, m: &[@Match], col: uint) -> bool {
-    vec::any(m, |br| {
+    do m.iter().any |br| {
         let pat = br.pats[col];
         match pat.node {
             ast::pat_enum(_, Some(_)) => {
@@ -1043,7 +1044,7 @@ pub fn any_tuple_struct_pat(bcx: block, m: &[@Match], col: uint) -> bool {
             }
             _ => false
         }
-    })
+    }
 }
 
 pub type mk_fail = @fn() -> BasicBlockRef;
diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs
index b26f80fc355..8e1b165f408 100644
--- a/src/librustc/middle/trans/adt.rs
+++ b/src/librustc/middle/trans/adt.rs
@@ -44,6 +44,7 @@
  *   taken to it, implementing them for Rust seems difficult.
  */
 
+use core::iterator::IteratorUtil;
 use core::container::Map;
 use core::libc::c_ulonglong;
 use core::option::{Option, Some, None};
@@ -176,7 +177,7 @@ fn represent_type_uncached(cx: @CrateContext, t: ty::t) -> Repr {
             // Since there's at least one
             // non-empty body, explicit discriminants should have
             // been rejected by a checker before this point.
-            if !cases.alli(|i,c| c.discr == (i as int)) {
+            if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as int)) {
                 cx.sess.bug(fmt!("non-C-like enum %s with specified \
                                   discriminants",
                                  ty::item_path_str(cx.tcx, def_id)))
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 2d1dd34af4a..f368255030b 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -64,6 +64,7 @@ use middle::ty;
 use util::common::indenter;
 use util::ppaux::{Repr, ty_to_str};
 
+use core::iterator::IteratorUtil;
 use core::hash;
 use core::hashmap::{HashMap, HashSet};
 use core::int;
@@ -1275,7 +1276,7 @@ pub fn trans_block_cleanups_(bcx: block,
         bcx.ccx().sess.opts.debugging_opts & session::no_landing_pads != 0;
     if bcx.unreachable && !no_lpads { return bcx; }
     let mut bcx = bcx;
-    for cleanups.each_reverse |cu| {
+    for cleanups.rev_iter().advance |cu| {
         match *cu {
             clean(cfn, cleanup_type) | clean_temp(_, cfn, cleanup_type) => {
                 // Some types don't need to be cleaned up during
diff --git a/src/librustc/middle/trans/cabi_arm.rs b/src/librustc/middle/trans/cabi_arm.rs
index 39535609598..d59635ccd76 100644
--- a/src/librustc/middle/trans/cabi_arm.rs
+++ b/src/librustc/middle/trans/cabi_arm.rs
@@ -17,9 +17,9 @@ use middle::trans::cabi::{ABIInfo, FnType, LLVMType};
 use middle::trans::common::{T_i8, T_i16, T_i32, T_i64};
 use middle::trans::common::{T_array, T_ptr, T_void};
 
+use core::iterator::IteratorUtil;
 use core::option::{Option, None, Some};
 use core::uint;
-use core::vec;
 
 fn align_up_to(off: uint, a: uint) -> uint {
     return (off + a - 1u) / a * a;
@@ -43,9 +43,8 @@ fn ty_align(ty: TypeRef) -> uint {
                 if llvm::LLVMIsPackedStruct(ty) == True {
                     1
                 } else {
-                    do vec::foldl(1, struct_tys(ty)) |a, t| {
-                        uint::max(a, ty_align(*t))
-                    }
+                    let str_tys = struct_tys(ty);
+                    str_tys.iter().fold(1, |a, t| uint::max(a, ty_align(*t)))
                 }
             }
             Array => {
@@ -68,13 +67,11 @@ fn ty_size(ty: TypeRef) -> uint {
             Double => 8,
             Struct => {
                 if llvm::LLVMIsPackedStruct(ty) == True {
-                    do vec::foldl(0, struct_tys(ty)) |s, t| {
-                        s + ty_size(*t)
-                    }
+                    let str_tys = struct_tys(ty);
+                    str_tys.iter().fold(0, |s, t| s + ty_size(*t))
                 } else {
-                    let size = do vec::foldl(0, struct_tys(ty)) |s, t| {
-                        align(s, *t) + ty_size(*t)
-                    };
+                    let str_tys = struct_tys(ty);
+                    let size = str_tys.iter().fold(0, |s, t| align(s, *t) + ty_size(*t));
                     align(size, ty)
                 }
             }
diff --git a/src/librustc/middle/trans/cabi_mips.rs b/src/librustc/middle/trans/cabi_mips.rs
index c9fb01905fb..5ef5c4c35b1 100644
--- a/src/librustc/middle/trans/cabi_mips.rs
+++ b/src/librustc/middle/trans/cabi_mips.rs
@@ -10,6 +10,7 @@
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::libc::c_uint;
 use core::ptr;
 use core::uint;
@@ -56,9 +57,8 @@ fn ty_align(ty: TypeRef) -> uint {
               if llvm::LLVMIsPackedStruct(ty) == True {
                 1
               } else {
-                do vec::foldl(1, struct_tys(ty)) |a, t| {
-                    uint::max(a, ty_align(*t))
-                }
+                let str_tys = struct_tys(ty);
+                str_tys.iter().fold(1, |a, t| uint::max(a, ty_align(*t)))
               }
             }
             Array => {
@@ -81,13 +81,11 @@ fn ty_size(ty: TypeRef) -> uint {
             Double => 8,
             Struct => {
                 if llvm::LLVMIsPackedStruct(ty) == True {
-                    do vec::foldl(0, struct_tys(ty)) |s, t| {
-                        s + ty_size(*t)
-                    }
+                    let str_tys = struct_tys(ty);
+                    str_tys.iter().fold(0, |s, t| s + ty_size(*t))
                 } else {
-                    let size = do vec::foldl(0, struct_tys(ty)) |s, t| {
-                        align(s, *t) + ty_size(*t)
-                    };
+                    let str_tys = struct_tys(ty);
+                    let size = str_tys.iter().fold(0, |s, t| align(s, *t) + ty_size(*t));
                     align(size, ty)
                 }
             }
diff --git a/src/librustc/middle/trans/cabi_x86_64.rs b/src/librustc/middle/trans/cabi_x86_64.rs
index a44f203c7ab..eb2d7e619eb 100644
--- a/src/librustc/middle/trans/cabi_x86_64.rs
+++ b/src/librustc/middle/trans/cabi_x86_64.rs
@@ -19,6 +19,7 @@ use lib::llvm::True;
 use middle::trans::common::*;
 use middle::trans::cabi::*;
 
+use core::iterator::IteratorUtil;
 use core::libc::c_uint;
 use core::option;
 use core::option::Option;
@@ -80,9 +81,8 @@ fn classify_ty(ty: TypeRef) -> ~[x86_64_reg_class] {
                   if llvm::LLVMIsPackedStruct(ty) == True {
                     1
                   } else {
-                    do vec::foldl(1, struct_tys(ty)) |a, t| {
-                      uint::max(a, ty_align(*t))
-                    }
+                    let str_tys = struct_tys(ty);
+                    str_tys.iter().fold(1, |a, t| uint::max(a, ty_align(*t)))
                   }
                 }
                 Array => {
@@ -104,16 +104,14 @@ fn classify_ty(ty: TypeRef) -> ~[x86_64_reg_class] {
                 Float => 4,
                 Double => 8,
                 Struct => {
-                  if llvm::LLVMIsPackedStruct(ty) == True {
-                    do vec::foldl(0, struct_tys(ty)) |s, t| {
-                      s + ty_size(*t)
+                    if llvm::LLVMIsPackedStruct(ty) == True {
+                        let str_tys = struct_tys(ty);
+                        str_tys.iter().fold(0, |s, t| s + ty_size(*t))
+                    } else {
+                        let str_tys = struct_tys(ty);
+                        let size = str_tys.iter().fold(0, |s, t| align(s, *t) + ty_size(*t));
+                        align(size, ty)
                     }
-                  } else {
-                    let size = do vec::foldl(0, struct_tys(ty)) |s, t| {
-                      align(s, *t) + ty_size(*t)
-                    };
-                    align(size, ty)
-                  }
                 }
                 Array => {
                   let len = llvm::LLVMGetArrayLength(ty) as uint;
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 774d2df1ca3..df5000a543c 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -53,7 +53,6 @@ use syntax::ast::ident;
 use syntax::ast_map::{path, path_elt};
 use syntax::codemap::span;
 use syntax::parse::token;
-use syntax::parse::token::ident_interner;
 use syntax::{ast, ast_map};
 use syntax::abi::{X86, X86_64, Arm, Mips};
 
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index eb173fb2c44..5f475f1bb9d 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -29,7 +29,6 @@ use core::str;
 use core::sys;
 use core::vec;
 use syntax::codemap::span;
-use syntax::parse::token::ident_interner;
 use syntax::{ast, codemap, ast_util, ast_map};
 
 static LLVMDebugVersion: int = (9 << 16);
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 062f72b6feb..169cd294b43 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -32,6 +32,7 @@ use middle::ty::{FnSig};
 use middle::typeck;
 use util::ppaux::{Repr,ty_to_str};
 
+use core::iterator::IteratorUtil;
 use core::vec;
 use syntax::ast;
 use syntax::ast_map;
@@ -75,7 +76,7 @@ pub fn monomorphic_fn(ccx: @CrateContext,
     let param_uses = type_use::type_uses_for(ccx, fn_id, substs.len());
     let hash_id = make_mono_id(ccx, fn_id, substs, vtables, impl_did_opt,
                                Some(param_uses));
-    if vec::any(hash_id.params,
+    if hash_id.params.iter().any(
                 |p| match *p { mono_precise(_, _) => false, _ => true }) {
         must_cast = true;
     }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 8e2691c8a27..e8501904c6f 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -27,6 +27,7 @@ use util::ppaux::{Repr, UserString};
 use util::common::{indenter};
 use util::enum_set::{EnumSet, CLike};
 
+use core::iterator::IteratorUtil;
 use core::cast;
 use core::cmp;
 use core::hashmap::{HashMap, HashSet};
@@ -2355,8 +2356,8 @@ pub fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
 
           ty_struct(did, ref substs) => {
               seen.push(did);
-              let r = vec::any(struct_fields(cx, did, substs),
-                               |f| type_requires(cx, seen, r_ty, f.mt.ty));
+              let fields = struct_fields(cx, did, substs);
+              let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
               seen.pop();
             r
           }
@@ -2372,12 +2373,12 @@ pub fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
             ty_enum(did, ref substs) => {
                 seen.push(did);
                 let vs = enum_variants(cx, did);
-                let r = vec::len(*vs) > 0u && vec::all(*vs, |variant| {
-                    vec::any(variant.args, |aty| {
+                let r = vec::len(*vs) > 0u && do vs.iter().all |variant| {
+                    do variant.args.iter().any |aty| {
                         let sty = subst(cx, substs, *aty);
                         type_requires(cx, seen, r_ty, sty)
-                    })
-                });
+                    }
+                };
                 seen.pop();
                 r
             }
@@ -2519,11 +2520,12 @@ pub fn type_is_pod(cx: ctxt, ty: t) -> bool {
       ty_param(_) => result = false,
       ty_opaque_closure_ptr(_) => result = true,
       ty_struct(did, ref substs) => {
-        result = vec::all(lookup_struct_fields(cx, did), |f| {
+        let fields = lookup_struct_fields(cx, did);
+        result = do fields.iter().all |f| {
             let fty = ty::lookup_item_type(cx, f.id);
             let sty = subst(cx, substs, fty.ty);
             type_is_pod(cx, sty)
-        });
+        };
       }
 
       ty_estr(vstore_slice(*)) | ty_evec(_, vstore_slice(*)) => {
@@ -2569,7 +2571,7 @@ pub fn type_is_c_like_enum(cx: ctxt, ty: t) -> bool {
             if variants.len() == 0 {
                 false
             } else {
-                variants.all(|v| v.args.len() == 0)
+                variants.iter().all(|v| v.args.len() == 0)
             }
         }
         _ => false
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 9241fb6da90..9eb5f815954 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -3065,7 +3065,7 @@ pub fn check_simd(tcx: ty::ctxt, sp: span, id: ast::node_id) {
                 return;
             }
             let e = ty::lookup_field_type(tcx, did, fields[0].id, substs);
-            if !vec::all(fields,
+            if !fields.iter().all(
                          |f| ty::lookup_field_type(tcx, did, f.id, substs) == e) {
                 tcx.sess.span_err(sp, "SIMD vector should be homogeneous");
                 return;
diff --git a/src/librustc/rustc.rc b/src/librustc/rustc.rc
index baf920c04ac..0d26e4c6ef1 100644
--- a/src/librustc/rustc.rc
+++ b/src/librustc/rustc.rc
@@ -36,8 +36,6 @@ extern mod std(name = "std", vers = "0.7-pre");
 
 // For bootstrapping purposes.
 #[cfg(stage0)]
-pub use core::str;
-#[cfg(stage0)]
 pub use core::unstable;
 
 use core::prelude::*;
diff --git a/src/librustdoc/desc_to_brief_pass.rs b/src/librustdoc/desc_to_brief_pass.rs
index 7a3ab259b1d..24ade927be2 100644
--- a/src/librustdoc/desc_to_brief_pass.rs
+++ b/src/librustdoc/desc_to_brief_pass.rs
@@ -24,9 +24,9 @@ use fold::Fold;
 use fold;
 use pass::Pass;
 
+use core::iterator::IteratorUtil;
 use core::str;
 use core::util;
-use core::vec;
 
 pub fn mk_pass() -> Pass {
     Pass {
@@ -150,7 +150,7 @@ pub fn paragraphs(s: &str) -> ~[~str] {
     for str::each_line_any(s) |line| { lines.push(line.to_owned()); }
     let mut whitespace_lines = 0;
     let mut accum = ~"";
-    let paras = do vec::foldl(~[], lines) |paras, line| {
+    let paras = do lines.iter().fold(~[]) |paras, line| {
         let mut res = paras;
 
         if str::is_whitespace(*line) {
diff --git a/src/librustdoc/doc.rs b/src/librustdoc/doc.rs
index 283763c1564..2f00cd0bbce 100644
--- a/src/librustdoc/doc.rs
+++ b/src/librustdoc/doc.rs
@@ -14,6 +14,7 @@ use core::prelude::*;
 
 use doc;
 
+use core::iterator::IteratorUtil;
 use core::vec;
 
 pub type AstId = int;
@@ -174,7 +175,7 @@ pub struct IndexEntry {
 
 impl Doc {
     pub fn CrateDoc(&self) -> CrateDoc {
-        vec::foldl(None, self.pages, |_m, page| {
+        self.pages.iter().fold(None, |_m, page| {
             match copy *page {
               doc::CratePage(doc) => Some(doc),
               _ => None
diff --git a/src/librustdoc/pass.rs b/src/librustdoc/pass.rs
index 8a51339c896..31adb0f3b8d 100644
--- a/src/librustdoc/pass.rs
+++ b/src/librustdoc/pass.rs
@@ -10,7 +10,7 @@
 
 use core::prelude::*;
 
-use core::vec;
+use core::iterator::IteratorUtil;
 
 use astsrv;
 use doc;
@@ -30,7 +30,7 @@ pub fn run_passes(
     passes: ~[Pass]
 ) -> doc::Doc {
     let mut passno = 0;
-    do vec::foldl(doc, passes) |doc, pass| {
+    do passes.iter().fold(doc) |doc, pass| {
         debug!("pass #%d", passno);
         passno += 1;
         do time(copy pass.name) {
diff --git a/src/librustdoc/unindent_pass.rs b/src/librustdoc/unindent_pass.rs
index a7f195a35ee..b6753f385df 100644
--- a/src/librustdoc/unindent_pass.rs
+++ b/src/librustdoc/unindent_pass.rs
@@ -21,9 +21,9 @@ middle of a line, and each of the following lines is indented.
 
 use core::prelude::*;
 
+use core::iterator::IteratorUtil;
 use core::str;
 use core::uint;
-use core::vec;
 use pass::Pass;
 use text_pass;
 
@@ -36,7 +36,7 @@ fn unindent(s: &str) -> ~str {
     for str::each_line_any(s) |line| { lines.push(line.to_owned()); }
     let mut saw_first_line = false;
     let mut saw_second_line = false;
-    let min_indent = do vec::foldl(uint::max_value, lines)
+    let min_indent = do lines.iter().fold(uint::max_value)
         |min_indent, line| {
 
         // After we see the first non-whitespace line, look at
diff --git a/src/libstd/at_vec.rs b/src/libstd/at_vec.rs
index 23f901c23ed..a118e445fe2 100644
--- a/src/libstd/at_vec.rs
+++ b/src/libstd/at_vec.rs
@@ -286,8 +286,6 @@ pub mod raw {
 #[cfg(test)]
 mod test {
     use super::*;
-    use prelude::*;
-
     use uint;
 
     #[test]
diff --git a/src/libstd/iter.rs b/src/libstd/iter.rs
index 8a0ec3ade4d..4886588bb94 100644
--- a/src/libstd/iter.rs
+++ b/src/libstd/iter.rs
@@ -42,7 +42,6 @@ much easier to implement.
 
 use cmp::Ord;
 use option::{Option, Some, None};
-use vec::OwnedVector;
 use num::{One, Zero};
 use ops::{Add, Mul};
 
diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 4ed82f63b39..8803844fdd0 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -18,7 +18,6 @@ implementing the `Iterator` trait.
 */
 
 use cmp;
-use iter;
 use iter::{FromIter, Times};
 use num::{Zero, One};
 use option::{Option, Some, None};
@@ -326,7 +325,7 @@ pub trait IteratorUtil<A> {
     /// assert!(a.iter().all(|&x| *x > 0));
     /// assert!(!a.iter().all(|&x| *x > 2));
     /// ~~~
-    fn all(&mut self, f: &fn(&A) -> bool) -> bool;
+    fn all(&mut self, f: &fn(A) -> bool) -> bool;
 
     /// Tests whether any element of an iterator satisfies the specified
     /// predicate.
@@ -341,7 +340,7 @@ pub trait IteratorUtil<A> {
     /// assert!(it.any(|&x| *x == 3));
     /// assert!(!it.any(|&x| *x == 3));
     /// ~~~
-    fn any(&mut self, f: &fn(&A) -> bool) -> bool;
+    fn any(&mut self, f: &fn(A) -> bool) -> bool;
 }
 
 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
@@ -462,14 +461,14 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
     fn count(&mut self) -> uint { self.fold(0, |cnt, _x| cnt + 1) }
 
     #[inline(always)]
-    fn all(&mut self, f: &fn(&A) -> bool) -> bool {
-        for self.advance |x| { if !f(&x) { return false; } }
+    fn all(&mut self, f: &fn(A) -> bool) -> bool {
+        for self.advance |x| { if !f(x) { return false; } }
         return true;
     }
 
     #[inline(always)]
-    fn any(&mut self, f: &fn(&A) -> bool) -> bool {
-        for self.advance |x| { if f(&x) { return true; } }
+    fn any(&mut self, f: &fn(A) -> bool) -> bool {
+        for self.advance |x| { if f(x) { return true; } }
         return false;
     }
 }
@@ -1080,18 +1079,18 @@ mod tests {
     #[test]
     fn test_all() {
         let v = ~&[1, 2, 3, 4, 5];
-        assert!(v.iter().all(|&x| *x < 10));
+        assert!(v.iter().all(|&x| x < 10));
         assert!(!v.iter().all(|&x| x.is_even()));
-        assert!(!v.iter().all(|&x| *x > 100));
+        assert!(!v.iter().all(|&x| x > 100));
         assert!(v.slice(0, 0).iter().all(|_| fail!()));
     }
 
     #[test]
     fn test_any() {
         let v = ~&[1, 2, 3, 4, 5];
-        assert!(v.iter().any(|&x| *x < 10));
+        assert!(v.iter().any(|&x| x < 10));
         assert!(v.iter().any(|&x| x.is_even()));
-        assert!(!v.iter().any(|&x| *x > 100));
+        assert!(!v.iter().any(|&x| x > 100));
         assert!(!v.slice(0, 0).iter().any(|_| fail!()));
     }
 }
diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs
index c8e2f58d801..e2cbf716dd1 100644
--- a/src/libstd/ptr.rs
+++ b/src/libstd/ptr.rs
@@ -11,8 +11,6 @@
 //! Unsafe pointer utility functions
 
 use cast;
-#[cfg(stage0)] use libc;
-#[cfg(stage0)] use libc::{c_void, size_t};
 use option::{Option, Some, None};
 use sys;
 use unstable::intrinsics;
diff --git a/src/libstd/rand.rs b/src/libstd/rand.rs
index b763c1c2d76..7946f7e4f13 100644
--- a/src/libstd/rand.rs
+++ b/src/libstd/rand.rs
@@ -43,6 +43,7 @@ fn main () {
 use cast;
 use cmp;
 use int;
+use iterator::IteratorUtil;
 use local_data;
 use prelude::*;
 use str;
@@ -479,7 +480,7 @@ impl<R: Rng> RngUtil for R {
     fn gen_char_from(&mut self, chars: &str) -> char {
         assert!(!chars.is_empty());
         let mut cs = ~[];
-        for str::each_char(chars) |c| { cs.push(c) }
+        for chars.iter().advance |c| { cs.push(c) }
         self.choose(cs)
     }
 
diff --git a/src/libstd/repr.rs b/src/libstd/repr.rs
index 14bec48782f..46f69d020d1 100644
--- a/src/libstd/repr.rs
+++ b/src/libstd/repr.rs
@@ -22,6 +22,7 @@ use intrinsic;
 use intrinsic::{TyDesc, TyVisitor, visit_tydesc};
 use intrinsic::Opaque;
 use io::{Writer, WriterUtil};
+use iterator::IteratorUtil;
 use libc::c_void;
 use managed;
 use ptr;
@@ -209,7 +210,7 @@ impl ReprVisitor {
 
     pub fn write_escaped_slice(&self, slice: &str) {
         self.writer.write_char('"');
-        for slice.each_char |ch| {
+        for slice.iter().advance |ch| {
             self.writer.write_escaped_char(ch);
         }
         self.writer.write_char('"');
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index 359c64c5f28..f9d11164995 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -25,7 +25,7 @@ use clone::Clone;
 use cmp::{TotalOrd, Ordering, Less, Equal, Greater};
 use container::Container;
 use iter::Times;
-use iterator::Iterator;
+use iterator::{Iterator, IteratorUtil};
 use libc;
 use option::{None, Option, Some};
 use old_iter::{BaseIter, EqIter};
@@ -35,7 +35,7 @@ use str;
 use to_str::ToStr;
 use uint;
 use vec;
-use vec::{OwnedVector, OwnedCopyableVector};
+use vec::{OwnedVector, OwnedCopyableVector, ImmutableVector};
 
 #[cfg(not(test))] use cmp::{Eq, Ord, Equiv, TotalEq};
 
@@ -608,11 +608,7 @@ pub fn byte_slice_no_callback<'a>(s: &'a str) -> &'a [u8] {
 
 /// Convert a string to a unique vector of characters
 pub fn to_chars(s: &str) -> ~[char] {
-    let mut buf = ~[];
-    for each_char(s) |c| {
-        buf.push(c);
-    }
-    buf
+    s.iter().collect()
 }
 
 /**
@@ -856,12 +852,12 @@ pub fn levdistance(s: &str, t: &str) -> uint {
 
     let mut dcol = vec::from_fn(tlen + 1, |x| x);
 
-    for s.each_chari |i, sc| {
+    for s.iter().enumerate().advance |(i, sc)| {
 
         let mut current = i;
         dcol[0] = current + 1;
 
-        for t.each_chari |j, tc| {
+        for t.iter().enumerate().advance |(j, tc)| {
 
             let next = dcol[j + 1];
 
@@ -943,7 +939,7 @@ pub fn each_split_within<'a>(ss: &'a str,
     let mut cont = true;
     let slice: &fn() = || { cont = it(slice(ss, slice_start, last_end)) };
 
-    let machine: &fn(uint, char) -> bool = |i, c| {
+    let machine: &fn((uint, char)) -> bool = |(i, c)| {
         let whitespace = if char::is_whitespace(c)       { Ws }       else { Cr };
         let limit      = if (i - slice_start + 1) <= lim { UnderLim } else { OverLim };
 
@@ -968,12 +964,12 @@ pub fn each_split_within<'a>(ss: &'a str,
         cont
     };
 
-    str::each_chari(ss, machine);
+    ss.iter().enumerate().advance(machine);
 
     // Let the automaton 'run out' by supplying trailing whitespace
     let mut fake_i = ss.len();
     while cont && match state { B | C => true, A => false } {
-        machine(fake_i, ' ');
+        machine((fake_i, ' '));
         fake_i += 1;
     }
     return cont;
@@ -1247,97 +1243,12 @@ pub fn any(ss: &str, pred: &fn(char) -> bool) -> bool {
 pub fn map(ss: &str, ff: &fn(char) -> char) -> ~str {
     let mut result = ~"";
     reserve(&mut result, len(ss));
-    for ss.each_char |cc| {
+    for ss.iter().advance |cc| {
         str::push_char(&mut result, ff(cc));
     }
     result
 }
 
-/// Iterate over the bytes in a string
-#[inline(always)]
-pub fn each(s: &str, it: &fn(u8) -> bool) -> bool {
-    eachi(s, |_i, b| it(b))
-}
-
-/// Iterate over the bytes in a string, with indices
-#[inline(always)]
-pub fn eachi(s: &str, it: &fn(uint, u8) -> bool) -> bool {
-    let mut pos = 0;
-    let len = s.len();
-
-    while pos < len {
-        if !it(pos, s[pos]) { return false; }
-        pos += 1;
-    }
-    return true;
-}
-
-/// Iterate over the bytes in a string in reverse
-#[inline(always)]
-pub fn each_reverse(s: &str, it: &fn(u8) -> bool) -> bool {
-    eachi_reverse(s, |_i, b| it(b) )
-}
-
-/// Iterate over the bytes in a string in reverse, with indices
-#[inline(always)]
-pub fn eachi_reverse(s: &str, it: &fn(uint, u8) -> bool) -> bool {
-    let mut pos = s.len();
-    while pos > 0 {
-        pos -= 1;
-        if !it(pos, s[pos]) { return false; }
-    }
-    return true;
-}
-
-/// Iterate over each char of a string, without allocating
-#[inline(always)]
-pub fn each_char(s: &str, it: &fn(char) -> bool) -> bool {
-    let mut i = 0;
-    let len = len(s);
-    while i < len {
-        let CharRange {ch, next} = char_range_at(s, i);
-        if !it(ch) { return false; }
-        i = next;
-    }
-    return true;
-}
-
-/// Iterates over the chars in a string, with indices
-#[inline(always)]
-pub fn each_chari(s: &str, it: &fn(uint, char) -> bool) -> bool {
-    let mut pos = 0;
-    let mut ch_pos = 0u;
-    let len = s.len();
-    while pos < len {
-        let CharRange {ch, next} = char_range_at(s, pos);
-        pos = next;
-        if !it(ch_pos, ch) { return false; }
-        ch_pos += 1u;
-    }
-    return true;
-}
-
-/// Iterates over the chars in a string in reverse
-#[inline(always)]
-pub fn each_char_reverse(s: &str, it: &fn(char) -> bool) -> bool {
-    each_chari_reverse(s, |_, c| it(c))
-}
-
-/// Iterates over the chars in a string in reverse, with indices
-#[inline(always)]
-pub fn each_chari_reverse(s: &str, it: &fn(uint, char) -> bool) -> bool {
-    let mut pos = s.len();
-    let mut ch_pos = s.char_len();
-    while pos > 0 {
-        let CharRange {ch, next} = char_range_at_reverse(s, pos);
-        pos = next;
-        ch_pos -= 1;
-
-        if !it(ch_pos, ch) { return false; }
-    }
-    return true;
-}
-
 /*
 Section: Searching
 */
@@ -1657,7 +1568,7 @@ pub fn rfind_between(s: &str, start: uint, end: uint, f: &fn(char) -> bool) -> O
 // Utility used by various searching functions
 fn match_at<'a,'b>(haystack: &'a str, needle: &'b str, at: uint) -> bool {
     let mut i = at;
-    for each(needle) |c| { if haystack[i] != c { return false; } i += 1u; }
+    for needle.bytes_iter().advance |c| { if haystack[i] != c { return false; } i += 1u; }
     return true;
 }
 
@@ -1880,7 +1791,7 @@ pub fn is_utf16(v: &[u16]) -> bool {
 /// Converts to a vector of `u16` encoded as UTF-16
 pub fn to_utf16(s: &str) -> ~[u16] {
     let mut u = ~[];
-    for s.each_char |ch| {
+    for s.iter().advance |ch| {
         // Arithmetic with u32 literals is easier on the eyes than chars.
         let mut ch = ch as u32;
 
@@ -2396,7 +2307,7 @@ pub fn capacity(s: &const ~str) -> uint {
 pub fn escape_default(s: &str) -> ~str {
     let mut out: ~str = ~"";
     reserve_at_least(&mut out, str::len(s));
-    for s.each_char |c| {
+    for s.iter().advance |c| {
         push_str(&mut out, char::escape_default(c));
     }
     out
@@ -2406,7 +2317,7 @@ pub fn escape_default(s: &str) -> ~str {
 pub fn escape_unicode(s: &str) -> ~str {
     let mut out: ~str = ~"";
     reserve_at_least(&mut out, str::len(s));
-    for s.each_char |c| {
+    for s.iter().advance |c| {
         push_str(&mut out, char::escape_unicode(c));
     }
     out
@@ -2608,15 +2519,10 @@ pub trait StrSlice<'self> {
     fn any(&self, it: &fn(char) -> bool) -> bool;
     fn contains<'a>(&self, needle: &'a str) -> bool;
     fn contains_char(&self, needle: char) -> bool;
-    fn char_iter(&self) -> StrCharIterator<'self>;
-    fn each(&self, it: &fn(u8) -> bool) -> bool;
-    fn eachi(&self, it: &fn(uint, u8) -> bool) -> bool;
-    fn each_reverse(&self, it: &fn(u8) -> bool) -> bool;
-    fn eachi_reverse(&self, it: &fn(uint, u8) -> bool) -> bool;
-    fn each_char(&self, it: &fn(char) -> bool) -> bool;
-    fn each_chari(&self, it: &fn(uint, char) -> bool) -> bool;
-    fn each_char_reverse(&self, it: &fn(char) -> bool) -> bool;
-    fn each_chari_reverse(&self, it: &fn(uint, char) -> bool) -> bool;
+    fn iter(&self) -> StrCharIterator<'self>;
+    fn rev_iter(&self) -> StrCharRevIterator<'self>;
+    fn bytes_iter(&self) -> StrBytesIterator<'self>;
+    fn bytes_rev_iter(&self) -> StrBytesRevIterator<'self>;
     fn ends_with(&self, needle: &str) -> bool;
     fn is_empty(&self) -> bool;
     fn is_whitespace(&self) -> bool;
@@ -2670,46 +2576,28 @@ impl<'self> StrSlice<'self> for &'self str {
     }
 
     #[inline]
-    fn char_iter(&self) -> StrCharIterator<'self> {
+    fn iter(&self) -> StrCharIterator<'self> {
         StrCharIterator {
             index: 0,
             string: *self
         }
     }
-
-    /// Iterate over the bytes in a string
-    #[inline]
-    fn each(&self, it: &fn(u8) -> bool) -> bool { each(*self, it) }
-    /// Iterate over the bytes in a string, with indices
-    #[inline]
-    fn eachi(&self, it: &fn(uint, u8) -> bool) -> bool { eachi(*self, it) }
-    /// Iterate over the bytes in a string
-    #[inline]
-    fn each_reverse(&self, it: &fn(u8) -> bool) -> bool { each_reverse(*self, it) }
-    /// Iterate over the bytes in a string, with indices
-    #[inline]
-    fn eachi_reverse(&self, it: &fn(uint, u8) -> bool) -> bool {
-        eachi_reverse(*self, it)
-    }
-    /// Iterate over the chars in a string
-    #[inline]
-    fn each_char(&self, it: &fn(char) -> bool) -> bool { each_char(*self, it) }
-    /// Iterate over the chars in a string, with indices
     #[inline]
-    fn each_chari(&self, it: &fn(uint, char) -> bool) -> bool {
-        each_chari(*self, it)
+    fn rev_iter(&self) -> StrCharRevIterator<'self> {
+        StrCharRevIterator {
+            index: self.len(),
+            string: *self
+        }
     }
-    /// Iterate over the chars in a string in reverse
-    #[inline]
-    fn each_char_reverse(&self, it: &fn(char) -> bool) -> bool {
-        each_char_reverse(*self, it)
+
+    fn bytes_iter(&self) -> StrBytesIterator<'self> {
+        StrBytesIterator { it: as_bytes_slice(*self).iter() }
     }
-    /// Iterate over the chars in a string in reverse, with indices from the
-    /// end
-    #[inline]
-    fn each_chari_reverse(&self, it: &fn(uint, char) -> bool) -> bool {
-        each_chari_reverse(*self, it)
+    fn bytes_rev_iter(&self) -> StrBytesRevIterator<'self> {
+        StrBytesRevIterator { it: as_bytes_slice(*self).rev_iter() }
     }
+
+
     /// Returns true if one string ends with another
     #[inline]
     fn ends_with(&self, needle: &str) -> bool {
@@ -2880,9 +2768,55 @@ impl<'self> Iterator<char> for StrCharIterator<'self> {
         }
     }
 }
+/// External iterator for a string's characters in reverse order. Use
+/// with the `std::iterator` module.
+pub struct StrCharRevIterator<'self> {
+    priv index: uint,
+    priv string: &'self str,
+}
+
+impl<'self> Iterator<char> for StrCharRevIterator<'self> {
+    #[inline]
+    fn next(&mut self) -> Option<char> {
+        if self.index > 0 {
+            let CharRange {ch, next} = char_range_at_reverse(self.string, self.index);
+            self.index = next;
+            Some(ch)
+        } else {
+            None
+        }
+    }
+}
+
+/// External iterator for a string's bytes. Use with the `std::iterator`
+/// module.
+pub struct StrBytesIterator<'self> {
+    priv it: vec::VecIterator<'self, u8>
+}
+
+impl<'self> Iterator<u8> for StrBytesIterator<'self> {
+    #[inline]
+    fn next(&mut self) -> Option<u8> {
+        self.it.next().map_consume(|&x| x)
+    }
+}
+
+/// External iterator for a string's bytes in reverse order. Use with
+/// the `std::iterator` module.
+pub struct StrBytesRevIterator<'self> {
+    priv it: vec::VecRevIterator<'self, u8>
+}
+
+impl<'self> Iterator<u8> for StrBytesRevIterator<'self> {
+    #[inline]
+    fn next(&mut self) -> Option<u8> {
+        self.it.next().map_consume(|&x| x)
+    }
+}
 
 #[cfg(test)]
 mod tests {
+    use iterator::IteratorUtil;
     use container::Container;
     use char;
     use option::Some;
@@ -2977,7 +2911,7 @@ mod tests {
             let mut v = ~[];
             for each_split_char(s, c) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         t("abc.hello.there", '.', [~"abc", ~"hello", ~"there"]);
         t(".hello.there", '.', [~"", ~"hello", ~"there"]);
@@ -2995,7 +2929,7 @@ mod tests {
             let mut v = ~[];
             for each_split_char(s, c) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         let data = "ประเทศไทย中华Việt Nam";
         t(data, 'V', [~"ประเทศไทย中华", ~"iệt Nam"]);
@@ -3010,7 +2944,7 @@ mod tests {
             for each_splitn_char(s, c, n) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
             debug!("comparing vs. %?", u);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         t("abc.hello.there", '.', 0u, [~"abc.hello.there"]);
         t("abc.hello.there", '.', 1u, [~"abc", ~"hello.there"]);
@@ -3037,7 +2971,7 @@ mod tests {
             for each_splitn_char(s, c, n) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
             debug!("comparing vs. %?", u);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
 
         t("ประเทศไทย中华Việt Nam", '华', 1u, [~"ประเทศไทย中", ~"Việt Nam"]);
@@ -3055,7 +2989,7 @@ mod tests {
             for each_splitn_char(s, c, n) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
             debug!("comparing vs. %?", u);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         let data = "ประเทศไทย中华Việt Nam";
         t(data, 'V', 1u, [~"ประเทศไทย中华", ~"iệt Nam"]);
@@ -3069,7 +3003,7 @@ mod tests {
             let mut v = ~[];
             for each_split_char_no_trailing(s, c) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         t("abc.hello.there", '.', [~"abc", ~"hello", ~"there"]);
         t(".hello.there", '.', [~"", ~"hello", ~"there"]);
@@ -3088,7 +3022,7 @@ mod tests {
             let mut v = ~[];
             for each_split_char_no_trailing(s, c) |s| { v.push(s.to_owned()) }
             debug!("split_byte to: %?", v);
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         let data = "ประเทศไทย中华Việt Nam";
         t(data, 'V', [~"ประเทศไทย中华", ~"iệt Nam"]);
@@ -3100,7 +3034,7 @@ mod tests {
         fn t<'a>(s: &str, sep: &'a str, u: &[~str]) {
             let mut v = ~[];
             for each_split_str(s, sep) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         t("--1233345--", "12345", [~"--1233345--"]);
         t("abc::hello::there", "::", [~"abc", ~"hello", ~"there"]);
@@ -3124,7 +3058,7 @@ mod tests {
         fn t(s: &str, sepf: &fn(char) -> bool, u: &[~str]) {
             let mut v = ~[];
             for each_split(s, sepf) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
 
         t("ประเทศไทย中华Việt Nam", |cc| cc == '华', [~"ประเทศไทย中", ~"Việt Nam"]);
@@ -3140,7 +3074,7 @@ mod tests {
         fn t(s: &str, sepf: &fn(char) -> bool, u: &[~str]) {
             let mut v = ~[];
             for each_split_no_trailing(s, sepf) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
 
         t("ประเทศไทย中华Việt Nam", |cc| cc == '华', [~"ประเทศไทย中", ~"Việt Nam"]);
@@ -3159,7 +3093,7 @@ mod tests {
         fn t(s: &str, f: &fn(&str, &fn(&str) -> bool) -> bool, u: &[~str]) {
             let mut v = ~[];
             for f(s) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
 
         t(lf, each_line, [~"", ~"Mary had a little lamb", ~"Little lamb"]);
@@ -3179,7 +3113,7 @@ mod tests {
         fn t(s: &str, f: &fn(&str, &fn(&str) -> bool) -> bool, u: &[~str]) {
             let mut v = ~[];
             for f(s) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         let data = "\nMary had a little lamb\nLittle lamb\n";
 
@@ -3193,7 +3127,7 @@ mod tests {
         fn t(s: &str, i: uint, u: &[~str]) {
             let mut v = ~[];
             for each_split_within(s, i) |s| { v.push(s.to_owned()) }
-            assert!(vec::all2(v, u, |a,b| a == b));
+            assert!(v.iter().zip(u.iter()).all(|(a,b)| a == b));
         }
         t("", 0, []);
         t("", 15, []);
@@ -3964,155 +3898,13 @@ mod tests {
         let s = ~"ศไทย中华Việt Nam";
         let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
         let mut pos = s.len();
-        for v.each_reverse |ch| {
+        for v.rev_iter().advance |ch| {
             assert!(s.char_at_reverse(pos) == *ch);
             pos -= from_char(*ch).len();
         }
     }
 
     #[test]
-    fn test_each() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = [
-            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
-            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
-            109
-        ];
-        let mut pos = 0;
-
-        for s.each |b| {
-            assert_eq!(b, v[pos]);
-            pos += 1;
-        }
-    }
-
-    #[test]
-    fn test_each_empty() {
-        for "".each |b| {
-            assert_eq!(b, 0u8);
-        }
-    }
-
-    #[test]
-    fn test_eachi() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = [
-            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
-            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
-            109
-        ];
-        let mut pos = 0;
-
-        for s.eachi |i, b| {
-            assert_eq!(pos, i);
-            assert_eq!(b, v[pos]);
-            pos += 1;
-        }
-    }
-
-    #[test]
-    fn test_eachi_empty() {
-        for "".eachi |i, b| {
-            assert_eq!(i, 0);
-            assert_eq!(b, 0);
-        }
-    }
-
-    #[test]
-    fn test_each_reverse() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = [
-            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
-            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
-            109
-        ];
-        let mut pos = v.len();
-
-        for s.each_reverse |b| {
-            pos -= 1;
-            assert_eq!(b, v[pos]);
-        }
-    }
-
-    #[test]
-    fn test_each_empty_reverse() {
-        for "".each_reverse |b| {
-            assert_eq!(b, 0u8);
-        }
-    }
-
-    #[test]
-    fn test_eachi_reverse() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = [
-            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
-            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
-            109
-        ];
-        let mut pos = v.len();
-
-        for s.eachi_reverse |i, b| {
-            pos -= 1;
-            assert_eq!(pos, i);
-            assert_eq!(b, v[pos]);
-        }
-    }
-
-    #[test]
-    fn test_eachi_reverse_empty() {
-        for "".eachi_reverse |i, b| {
-            assert_eq!(i, 0);
-            assert_eq!(b, 0);
-        }
-    }
-
-    #[test]
-    fn test_each_char() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
-        let mut pos = 0;
-        for s.each_char |ch| {
-            assert_eq!(ch, v[pos]);
-            pos += 1;
-        }
-    }
-
-    #[test]
-    fn test_each_chari() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
-        let mut pos = 0;
-        for s.each_chari |i, ch| {
-            assert_eq!(pos, i);
-            assert_eq!(ch, v[pos]);
-            pos += 1;
-        }
-    }
-
-    #[test]
-    fn test_each_char_reverse() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
-        let mut pos = v.len();
-        for s.each_char_reverse |ch| {
-            pos -= 1;
-            assert_eq!(ch, v[pos]);
-        }
-    }
-
-    #[test]
-    fn test_each_chari_reverse() {
-        let s = ~"ศไทย中华Việt Nam";
-        let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
-        let mut pos = v.len();
-        for s.each_chari_reverse |i, ch| {
-            pos -= 1;
-            assert_eq!(pos, i);
-            assert_eq!(ch, v[pos]);
-        }
-    }
-
-    #[test]
     fn test_escape_unicode() {
         assert_eq!(escape_unicode("abc"), ~"\\x61\\x62\\x63");
         assert_eq!(escape_unicode("a c"), ~"\\x61\\x20\\x63");
@@ -4167,7 +3959,23 @@ mod tests {
         let v = ~['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
 
         let mut pos = 0;
-        let mut it = s.char_iter();
+        let mut it = s.iter();
+
+        for it.advance |c| {
+            assert_eq!(c, v[pos]);
+            pos += 1;
+        }
+        assert_eq!(pos, v.len());
+    }
+
+    #[test]
+    fn test_rev_iterator() {
+        use iterator::*;
+        let s = ~"ศไทย中华Việt Nam";
+        let v = ~['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ'];
+
+        let mut pos = 0;
+        let mut it = s.rev_iter();
 
         for it.advance |c| {
             assert_eq!(c, v[pos]);
@@ -4175,4 +3983,36 @@ mod tests {
         }
         assert_eq!(pos, v.len());
     }
+
+    #[test]
+    fn test_bytes_iterator() {
+        let s = ~"ศไทย中华Việt Nam";
+        let v = [
+            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+            109
+        ];
+        let mut pos = 0;
+
+        for s.bytes_iter().advance |b| {
+            assert_eq!(b, v[pos]);
+            pos += 1;
+        }
+    }
+
+    #[test]
+    fn test_bytes_rev_iterator() {
+        let s = ~"ศไทย中华Việt Nam";
+        let v = [
+            224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+            184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+            109
+        ];
+        let mut pos = v.len();
+
+        for s.bytes_rev_iter().advance |b| {
+            pos -= 1;
+            assert_eq!(b, v[pos]);
+        }
+    }
 }
diff --git a/src/libstd/str/ascii.rs b/src/libstd/str/ascii.rs
index 3b31d70f7a1..e288d605714 100644
--- a/src/libstd/str/ascii.rs
+++ b/src/libstd/str/ascii.rs
@@ -15,6 +15,7 @@ use str;
 use str::StrSlice;
 use cast;
 use old_iter::BaseIter;
+use iterator::IteratorUtil;
 use vec::{CopyableVector, ImmutableVector, OwnedVector};
 
 /// Datatype to hold one ascii character. It is 8 bit long.
@@ -101,10 +102,7 @@ impl<'self> AsciiCast<&'self[Ascii]> for &'self str {
 
     #[inline(always)]
     fn is_ascii(&self) -> bool {
-        for self.each |b| {
-            if !b.is_ascii() { return false; }
-        }
-        true
+        self.bytes_iter().all(|b| b.is_ascii())
     }
 }
 
diff --git a/src/libstd/sys.rs b/src/libstd/sys.rs
index 583923bc2e3..87e13e494aa 100644
--- a/src/libstd/sys.rs
+++ b/src/libstd/sys.rs
@@ -14,7 +14,6 @@
 
 use option::{Some, None};
 use cast;
-use cmp::{Eq, Ord};
 use gc;
 use io;
 use libc;
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index 7899edbfcb9..4bd3946f885 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -14,7 +14,6 @@ use prelude::*;
 use iterator::IteratorUtil;
 use uint;
 use util::{swap, replace};
-use vec;
 
 // FIXME: #5244: need to manually update the TrieNode constructor
 static SHIFT: uint = 4;
diff --git a/src/libstd/unstable/lang.rs b/src/libstd/unstable/lang.rs
index 350b18d4541..cd3e0cf303e 100644
--- a/src/libstd/unstable/lang.rs
+++ b/src/libstd/unstable/lang.rs
@@ -10,6 +10,7 @@
 
 //! Runtime calls emitted by the compiler.
 
+use iterator::IteratorUtil;
 use uint;
 use cast::transmute;
 use libc::{c_char, c_uchar, c_void, size_t, uintptr_t, c_int, STDERR_FILENO};
@@ -133,7 +134,7 @@ unsafe fn fail_borrowed(box: *mut BoxRepr, file: *c_char, line: size_t) {
         Some(borrow_list) => { // recording borrows
             let mut msg = ~"borrowed";
             let mut sep = " at ";
-            for borrow_list.each_reverse |entry| {
+            for borrow_list.rev_iter().advance |entry| {
                 if entry.box == box {
                     str::push_str(&mut msg, sep);
                     let filename = str::raw::from_c_str(entry.file);
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index d8424f4a29e..6137b589bdb 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -1066,138 +1066,12 @@ impl<'self, T:Copy> VectorVector<T> for &'self [&'self [T]] {
     }
 }
 
-/**
- * Reduces a vector from left to right.
- *
- * # Arguments
- * * `z` - initial accumulator value
- * * `v` - vector to iterate over
- * * `p` - a closure to operate on vector elements
- *
- * # Examples
- *
- * Sum all values in the vector [1, 2, 3]:
- *
- * ~~~ {.rust}
- * vec::foldl(0, [1, 2, 3], |a, b| a + *b);
- * ~~~
- *
- */
-pub fn foldl<'a, T, U>(z: T, v: &'a [U], p: &fn(t: T, u: &'a U) -> T) -> T {
-    let mut accum = z;
-    let mut i = 0;
-    let l = v.len();
-    while i < l {
-        // Use a while loop so that liveness analysis can handle moving
-        // the accumulator.
-        accum = p(accum, &v[i]);
-        i += 1;
-    }
-    accum
-}
-
-/**
- * Reduces a vector from right to left. Note that the argument order is
- * reversed compared to `foldl` to reflect the order they are provided to
- * the closure.
- *
- * # Arguments
- * * `v` - vector to iterate over
- * * `z` - initial accumulator value
- * * `p` - a closure to do operate on vector elements
- *
- * # Examples
- *
- * Sum all values in the vector [1, 2, 3]:
- *
- * ~~~ {.rust}
- * vec::foldr([1, 2, 3], 0, |a, b| a + *b);
- * ~~~
- *
- */
-pub fn foldr<'a, T, U>(v: &'a [T], mut z: U, p: &fn(t: &'a T, u: U) -> U) -> U {
-    let mut i = v.len();
-    while i > 0 {
-        i -= 1;
-        z = p(&v[i], z);
-    }
-    return z;
-}
-
-/**
- * Return true if a predicate matches any elements
- *
- * If the vector contains no elements then false is returned.
- */
-pub fn any<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool {
-    for each(v) |elem| { if f(elem) { return true; } }
-    false
-}
-
-/**
- * Return true if a predicate matches any elements in both vectors.
- *
- * If the vectors contains no elements then false is returned.
- */
-pub fn any2<T, U>(v0: &[T], v1: &[U],
-                   f: &fn(a: &T, b: &U) -> bool) -> bool {
-    let v0_len = len(v0);
-    let v1_len = len(v1);
-    let mut i = 0u;
-    while i < v0_len && i < v1_len {
-        if f(&v0[i], &v1[i]) { return true; };
-        i += 1u;
-    }
-    false
-}
-
-/**
- * Return true if a predicate matches all elements
- *
- * If the vector contains no elements then true is returned.
- */
-pub fn all<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool {
-    for each(v) |elem| { if !f(elem) { return false; } }
-    true
-}
-
-/**
- * Return true if a predicate matches all elements
- *
- * If the vector contains no elements then true is returned.
- */
-pub fn alli<T>(v: &[T], f: &fn(uint, t: &T) -> bool) -> bool {
-    for eachi(v) |i, elem| { if !f(i, elem) { return false; } }
-    true
-}
-
-/**
- * Return true if a predicate matches all elements in both vectors.
- *
- * If the vectors are not the same size then false is returned.
- */
-pub fn all2<T, U>(v0: &[T], v1: &[U],
-                   f: &fn(t: &T, u: &U) -> bool) -> bool {
-    let v0_len = len(v0);
-    if v0_len != len(v1) { return false; }
-    let mut i = 0u;
-    while i < v0_len { if !f(&v0[i], &v1[i]) { return false; }; i += 1u; }
-    true
-}
-
 /// Return true if a vector contains an element with the given value
 pub fn contains<T:Eq>(v: &[T], x: &T) -> bool {
     for each(v) |elt| { if *x == *elt { return true; } }
     false
 }
 
-/// Returns the number of elements that are equal to a given value
-pub fn count<T:Eq>(v: &[T], x: &T) -> uint {
-    let mut cnt = 0u;
-    for each(v) |elt| { if *x == *elt { cnt += 1u; } }
-    cnt
-}
-
 /**
  * Search for the first element that matches a given predicate
  *
@@ -1599,34 +1473,6 @@ pub fn eachi<'r,T>(v: &'r [T], f: &fn(uint, v: &'r T) -> bool) -> bool {
 }
 
 /**
- * Iterates over a vector's elements in reverse
- *
- * Return true to continue, false to break.
- */
-#[inline(always)]
-pub fn each_reverse<'r,T>(v: &'r [T], blk: &fn(v: &'r T) -> bool) -> bool {
-    eachi_reverse(v, |_i, v| blk(v))
-}
-
-/**
- * Iterates over a vector's elements and indices in reverse
- *
- * Return true to continue, false to break.
- */
-#[inline(always)]
-pub fn eachi_reverse<'r,T>(v: &'r [T],
-                            blk: &fn(i: uint, v: &'r T) -> bool) -> bool {
-    let mut i = v.len();
-    while i > 0 {
-        i -= 1;
-        if !blk(i, &v[i]) {
-            return false;
-        }
-    }
-    return true;
-}
-
-/**
  * Iterate over all permutations of vector `v`.
  *
  * Permutations are produced in lexicographic order with respect to the order
@@ -1964,6 +1810,7 @@ impl<'self,T:Copy> CopyableVector<T> for &'self [T] {
 pub trait ImmutableVector<'self, T> {
     fn slice(&self, start: uint, end: uint) -> &'self [T];
     fn iter(self) -> VecIterator<'self, T>;
+    fn rev_iter(self) -> VecRevIterator<'self, T>;
     fn head(&self) -> &'self T;
     fn head_opt(&self) -> Option<&'self T>;
     fn tail(&self) -> &'self [T];
@@ -1974,13 +1821,9 @@ pub trait ImmutableVector<'self, T> {
     fn last_opt(&self) -> Option<&'self T>;
     fn position(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
     fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
-    fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool;
-    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool;
-    fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U;
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U];
     fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U];
     fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U];
-    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool;
     fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U];
     fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U];
     unsafe fn unsafe_ref(&self, index: uint) -> *T;
@@ -2002,6 +1845,15 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
                         lifetime: cast::transmute(p)}
         }
     }
+    #[inline]
+    fn rev_iter(self) -> VecRevIterator<'self, T> {
+        unsafe {
+            let p = vec::raw::to_ptr(self);
+            VecRevIterator{ptr: p.offset(self.len() - 1),
+                           end: p.offset(-1),
+                           lifetime: cast::transmute(p)}
+        }
+    }
 
     /// Returns the first element of a vector, failing if the vector is empty.
     #[inline]
@@ -2059,24 +1911,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
         rposition(*self, f)
     }
 
-    /// Iterates over a vector's elements in reverse.
-    #[inline]
-    fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool {
-        each_reverse(*self, blk)
-    }
-
-    /// Iterates over a vector's elements and indices in reverse.
-    #[inline]
-    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool {
-        eachi_reverse(*self, blk)
-    }
-
-    /// Reduce a vector from right to left
-    #[inline]
-    fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U {
-        foldr(*self, z, p)
-    }
-
     /// Apply a function to each element of a vector and return the results
     #[inline]
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] { map(*self, f) }
@@ -2101,14 +1935,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     }
 
     /**
-     * Returns true if the function returns true for all elements.
-     *
-     *     If the vector is empty, true is returned.
-     */
-    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool {
-        alli(*self, f)
-    }
-    /**
      * Apply a function to each element of a vector and return a concatenation
      * of each result vector
      */
@@ -2350,7 +2176,8 @@ impl<T:Eq> OwnedEqVector<T> for ~[T] {
 #[allow(missing_doc)]
 pub trait MutableVector<'self, T> {
     fn mut_slice(self, start: uint, end: uint) -> &'self mut [T];
-    fn mut_iter(self) -> MutVecIterator<'self, T>;
+    fn mut_iter(self) -> VecMutIterator<'self, T>;
+    fn mut_rev_iter(self) -> VecMutRevIterator<'self, T>;
 
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T;
     unsafe fn unsafe_set(&self, index: uint, val: T);
@@ -2363,14 +2190,23 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     }
 
     #[inline]
-    fn mut_iter(self) -> MutVecIterator<'self, T> {
+    fn mut_iter(self) -> VecMutIterator<'self, T> {
         unsafe {
             let p = vec::raw::to_mut_ptr(self);
-            MutVecIterator{ptr: p, end: p.offset(self.len()),
+            VecMutIterator{ptr: p, end: p.offset(self.len()),
                            lifetime: cast::transmute(p)}
         }
     }
 
+    fn mut_rev_iter(self) -> VecMutRevIterator<'self, T> {
+        unsafe {
+            let p = vec::raw::to_mut_ptr(self);
+            VecMutRevIterator{ptr: p.offset(self.len() - 1),
+                              end: p.offset(-1),
+                              lifetime: cast::transmute(p)}
+        }
+    }
+
     #[inline(always)]
     unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T {
         let pair_ptr: &(*mut T, uint) = transmute(self);
@@ -2872,52 +2708,69 @@ impl<A:Clone> Clone for ~[A] {
     }
 }
 
-/// An external iterator for vectors (use with the std::iterator module)
+macro_rules! iterator {
+    /* FIXME: #4375 Cannot attach documentation/attributes to a macro generated struct.
+    (struct $name:ident -> $ptr:ty, $elem:ty) => {
+        pub struct $name<'self, T> {
+            priv ptr: $ptr,
+            priv end: $ptr,
+            priv lifetime: $elem // FIXME: #5922
+        }
+    };*/
+    (impl $name:ident -> $elem:ty, $step:expr) => {
+        // could be implemented with &[T] with .slice(), but this avoids bounds checks
+        impl<'self, T> Iterator<$elem> for $name<'self, T> {
+            #[inline]
+            fn next(&mut self) -> Option<$elem> {
+                unsafe {
+                    if self.ptr == self.end {
+                        None
+                    } else {
+                        let old = self.ptr;
+                        self.ptr = self.ptr.offset($step);
+                        Some(cast::transmute(old))
+                    }
+                }
+            }
+        }
+    }
+}
+
+//iterator!{struct VecIterator -> *T, &'self T}
+/// An iterator for iterating over a vector
 pub struct VecIterator<'self, T> {
     priv ptr: *T,
     priv end: *T,
     priv lifetime: &'self T // FIXME: #5922
 }
+iterator!{impl VecIterator -> &'self T, 1}
 
-// could be implemented with &[T] with .slice(), but this avoids bounds checks
-impl<'self, T> Iterator<&'self T> for VecIterator<'self, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'self T> {
-        unsafe {
-            if self.ptr == self.end {
-                None
-            } else {
-                let old = self.ptr;
-                self.ptr = self.ptr.offset(1);
-                Some(cast::transmute(old))
-            }
-        }
-    }
+//iterator!{struct VecRevIterator -> *T, &'self T}
+/// An iterator for iterating over a vector in reverse
+pub struct VecRevIterator<'self, T> {
+    priv ptr: *T,
+    priv end: *T,
+    priv lifetime: &'self T // FIXME: #5922
 }
+iterator!{impl VecRevIterator -> &'self T, -1}
 
-/// An external iterator for vectors with the possibility of mutating
-/// elements. (use with the std::iterator module)
-pub struct MutVecIterator<'self, T> {
+//iterator!{struct VecMutIterator -> *mut T, &'self mut T}
+/// An iterator for mutating the elements of a vector
+pub struct VecMutIterator<'self, T> {
     priv ptr: *mut T,
     priv end: *mut T,
     priv lifetime: &'self mut T // FIXME: #5922
 }
+iterator!{impl VecMutIterator -> &'self mut T, 1}
 
-// could be implemented with &[T] with .slice(), but this avoids bounds checks
-impl<'self, T> Iterator<&'self mut T> for MutVecIterator<'self, T> {
-    #[inline]
-    fn next(&mut self) -> Option<&'self mut T> {
-        unsafe {
-            if self.ptr == self.end {
-                None
-            } else {
-                let old = self.ptr;
-                self.ptr = self.ptr.offset(1);
-                Some(cast::transmute(old))
-            }
-        }
-    }
+//iterator!{struct VecMutRevIterator -> *mut T, &'self mut T}
+/// An iterator for mutating the elements of a vector in reverse
+pub struct VecMutRevIterator<'self, T> {
+    priv ptr: *mut T,
+    priv end: *mut T,
+    priv lifetime: &'self mut T // FIXME: #5922
 }
+iterator!{impl VecMutRevIterator -> &'self mut T, -1}
 
 impl<T> FromIter<T> for ~[T]{
     #[inline(always)]
@@ -3468,39 +3321,6 @@ mod tests {
     }
 
     #[test]
-    fn test_foldl() {
-        // Test on-stack fold.
-        let mut v = ~[1u, 2u, 3u];
-        let mut sum = foldl(0u, v, add);
-        assert_eq!(sum, 6u);
-
-        // Test on-heap fold.
-        v = ~[1u, 2u, 3u, 4u, 5u];
-        sum = foldl(0u, v, add);
-        assert_eq!(sum, 15u);
-    }
-
-    #[test]
-    fn test_foldl2() {
-        fn sub(a: int, b: &int) -> int {
-            a - *b
-        }
-        let v = ~[1, 2, 3, 4];
-        let sum = foldl(0, v, sub);
-        assert_eq!(sum, -10);
-    }
-
-    #[test]
-    fn test_foldr() {
-        fn sub(a: &int, b: int) -> int {
-            *a - b
-        }
-        let v = ~[1, 2, 3, 4];
-        let sum = foldr(v, 0, sub);
-        assert_eq!(sum, -2);
-    }
-
-    #[test]
     fn test_each_empty() {
         for each::<int>([]) |_v| {
             fail!(); // should never be executed
@@ -3528,51 +3348,14 @@ mod tests {
     }
 
     #[test]
-    fn test_each_reverse_empty() {
-        let v: ~[int] = ~[];
-        for v.each_reverse |_v| {
-            fail!(); // should never execute
-        }
-    }
-
-    #[test]
-    fn test_each_reverse_nonempty() {
-        let mut i = 0;
-        for each_reverse([1, 2, 3]) |v| {
-            if i == 0 { assert!(*v == 3); }
-            i += *v
-        }
-        assert_eq!(i, 6);
-    }
-
-    #[test]
-    fn test_eachi_reverse() {
-        let mut i = 0;
-        for eachi_reverse([0, 1, 2]) |j, v| {
-            if i == 0 { assert!(*v == 2); }
-            assert_eq!(j, *v as uint);
-            i += *v;
-        }
-        assert_eq!(i, 3);
-    }
-
-    #[test]
-    fn test_eachi_reverse_empty() {
-        let v: ~[int] = ~[];
-        for v.eachi_reverse |_i, _v| {
-            fail!(); // should never execute
-        }
-    }
-
-    #[test]
     fn test_each_ret_len0() {
-        let mut a0 : [int, .. 0] = [];
+        let a0 : [int, .. 0] = [];
         assert_eq!(each(a0, |_p| fail!()), true);
     }
 
     #[test]
     fn test_each_ret_len1() {
-        let mut a1 = [17];
+        let a1 = [17];
         assert_eq!(each(a1, |_p| true), true);
         assert_eq!(each(a1, |_p| false), false);
     }
@@ -3601,33 +3384,6 @@ mod tests {
     }
 
     #[test]
-    fn test_any_and_all() {
-        assert!(any([1u, 2u, 3u], is_three));
-        assert!(!any([0u, 1u, 2u], is_three));
-        assert!(any([1u, 2u, 3u, 4u, 5u], is_three));
-        assert!(!any([1u, 2u, 4u, 5u, 6u], is_three));
-
-        assert!(all([3u, 3u, 3u], is_three));
-        assert!(!all([3u, 3u, 2u], is_three));
-        assert!(all([3u, 3u, 3u, 3u, 3u], is_three));
-        assert!(!all([3u, 3u, 0u, 1u, 2u], is_three));
-    }
-
-    #[test]
-    fn test_any2_and_all2() {
-
-        assert!(any2([2u, 4u, 6u], [2u, 4u, 6u], is_equal));
-        assert!(any2([1u, 2u, 3u], [4u, 5u, 3u], is_equal));
-        assert!(!any2([1u, 2u, 3u], [4u, 5u, 6u], is_equal));
-        assert!(any2([2u, 4u, 6u], [2u, 4u], is_equal));
-
-        assert!(all2([2u, 4u, 6u], [2u, 4u, 6u], is_equal));
-        assert!(!all2([1u, 2u, 3u], [4u, 5u, 3u], is_equal));
-        assert!(!all2([1u, 2u, 3u], [4u, 5u, 6u], is_equal));
-        assert!(!all2([2u, 4u, 6u], [2u, 4u], is_equal));
-    }
-
-    #[test]
     fn test_zip_unzip() {
         let v1 = ~[1, 2, 3];
         let v2 = ~[4, 5, 6];
@@ -4375,113 +4131,6 @@ mod tests {
     #[ignore(windows)]
     #[should_fail]
     #[allow(non_implicitly_copyable_typarams)]
-    fn test_foldl_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do foldl((~0, @0), v) |_a, _b| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            (~0, @0)
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
-    fn test_foldr_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do foldr(v, (~0, @0)) |_a, _b| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            (~0, @0)
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_any_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do any(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_any2_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do any(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            false
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_all_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do all(v) |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_alli_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do alli(v) |_i, _elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    fn test_all2_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do all2(v, v) |_elt1, _elt2| {
-            if i == 2 {
-                fail!()
-            }
-            i += 0;
-            true
-        };
-    }
-
-    #[test]
-    #[ignore(windows)]
-    #[should_fail]
-    #[allow(non_implicitly_copyable_typarams)]
     fn test_find_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;
@@ -4643,6 +4292,30 @@ mod tests {
     }
 
     #[test]
+    fn test_rev_iterator() {
+        use iterator::*;
+
+        let xs = [1, 2, 5, 10, 11];
+        let ys = [11, 10, 5, 2, 1];
+        let mut i = 0;
+        for xs.rev_iter().advance |&x| {
+            assert_eq!(x, ys[i]);
+            i += 1;
+        }
+        assert_eq!(i, 5);
+    }
+
+    #[test]
+    fn test_mut_rev_iterator() {
+        use iterator::*;
+        let mut xs = [1u, 2, 3, 4, 5];
+        for xs.mut_rev_iter().enumerate().advance |(i,x)| {
+            *x += i;
+        }
+        assert_eq!(xs, [5, 5, 5, 5, 5])
+    }
+
+    #[test]
     fn test_reverse_part() {
         let mut values = [1,2,3,4,5];
         reverse_part(values,1,4);
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 5bbc5d4e819..f27ae3b828c 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -15,7 +15,7 @@ use core::prelude::*;
 use codemap::{span, spanned};
 use abi::AbiSet;
 use opt_vec::OptVec;
-use parse::token::{ident_to_str, interner_get, str_to_ident};
+use parse::token::{interner_get, str_to_ident};
 
 use core::hashmap::HashMap;
 use core::option::Option;
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index d99363d7ee5..b040397de72 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -792,6 +792,7 @@ mod test {
     use ast::*;
     use super::*;
     use core::io;
+    use core::iterator::IteratorUtil;
 
     #[test] fn xorpush_test () {
         let mut s = ~[];
@@ -833,7 +834,7 @@ mod test {
     // returning the resulting index
     fn unfold_test_sc(tscs : ~[TestSC], tail: SyntaxContext, table : &mut SCTable)
         -> SyntaxContext {
-        tscs.foldr(tail, |tsc : &TestSC,tail : SyntaxContext|
+        tscs.rev_iter().fold(tail, |tail : SyntaxContext, tsc : &TestSC|
                   {match *tsc {
                       M(mrk) => new_mark_internal(mrk,tail,table),
                       R(ident,name) => new_rename_internal(ident,name,tail,table)}})
@@ -874,7 +875,7 @@ mod test {
     // extend a syntax context with a sequence of marks given
     // in a vector. v[0] will be the outermost mark.
     fn unfold_marks(mrks:~[Mrk],tail:SyntaxContext,table: &mut SCTable) -> SyntaxContext {
-        mrks.foldr(tail, |mrk:&Mrk,tail:SyntaxContext|
+        mrks.rev_iter().fold(tail, |tail:SyntaxContext, mrk:&Mrk|
                    {new_mark_internal(*mrk,tail,table)})
     }
 
diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 2da64563159..51334772c84 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -19,6 +19,7 @@ use codemap::BytePos;
 use diagnostic::span_handler;
 use parse::comments::{doc_comment_style, strip_doc_comment_decoration};
 
+use core::iterator::IteratorUtil;
 use core::hashmap::HashSet;
 use core::vec;
 use extra;
@@ -313,7 +314,7 @@ pub enum inline_attr {
 /// True if something like #[inline] is found in the list of attrs.
 pub fn find_inline_attr(attrs: &[ast::attribute]) -> inline_attr {
     // FIXME (#2809)---validate the usage of #[inline] and #[inline(always)]
-    do vec::foldl(ia_none, attrs) |ia,attr| {
+    do attrs.iter().fold(ia_none) |ia,attr| {
         match attr.node.value.node {
           ast::meta_word(@~"inline") => ia_hint,
           ast::meta_list(@~"inline", ref items) => {
diff --git a/src/libsyntax/ext/bytes.rs b/src/libsyntax/ext/bytes.rs
index a046395b6f5..51fbaee7a33 100644
--- a/src/libsyntax/ext/bytes.rs
+++ b/src/libsyntax/ext/bytes.rs
@@ -10,6 +10,7 @@
 
 /* The compiler code necessary to support the bytes! extension. */
 
+use core::iterator::IteratorUtil;
 use ast;
 use codemap::span;
 use ext::base::*;
@@ -27,7 +28,7 @@ pub fn expand_syntax_ext(cx: @ExtCtxt, sp: span, tts: &[ast::token_tree]) -> bas
             ast::expr_lit(lit) => match lit.node {
                 // string literal, push each byte to vector expression
                 ast::lit_str(s) => {
-                    for s.each |byte| {
+                    for s.bytes_iter().advance |byte| {
                         bytes.push(cx.expr_u8(sp, byte));
                     }
                 }
diff --git a/src/libsyntax/ext/deriving/generic.rs b/src/libsyntax/ext/deriving/generic.rs
index b36d4496492..078fd4231ca 100644
--- a/src/libsyntax/ext/deriving/generic.rs
+++ b/src/libsyntax/ext/deriving/generic.rs
@@ -1025,11 +1025,11 @@ pub fn cs_fold(use_foldl: bool,
     match *substructure.fields {
         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
             if use_foldl {
-                do all_fields.foldl(base) |&old, &(_, self_f, other_fs)| {
+                do all_fields.iter().fold(base) |old, &(_, self_f, other_fs)| {
                     f(cx, span, old, self_f, other_fs)
                 }
             } else {
-                do all_fields.foldr(base) |&(_, self_f, other_fs), old| {
+                do all_fields.rev_iter().fold(base) |old, &(_, self_f, other_fs)| {
                     f(cx, span, old, self_f, other_fs)
                 }
             }
@@ -1094,11 +1094,11 @@ pub fn cs_same_method_fold(use_foldl: bool,
     cs_same_method(
         |cx, span, vals| {
             if use_foldl {
-                do vals.foldl(base) |&old, &new| {
+                do vals.iter().fold(base) |old, &new| {
                     f(cx, span, old, new)
                 }
             } else {
-                do vals.foldr(base) |&new, old| {
+                do vals.rev_iter().fold(base) |old, &new| {
                     f(cx, span, old, new)
                 }
             }
diff --git a/src/libsyntax/ext/deriving/iter_bytes.rs b/src/libsyntax/ext/deriving/iter_bytes.rs
index 13f83b55a40..453d867fce9 100644
--- a/src/libsyntax/ext/deriving/iter_bytes.rs
+++ b/src/libsyntax/ext/deriving/iter_bytes.rs
@@ -16,7 +16,7 @@ use ext::base::ExtCtxt;
 use ext::build::AstBuilder;
 use ext::deriving::generic::*;
 
-use core::vec;
+use core::iterator::IteratorUtil;
 
 pub fn expand_deriving_iter_bytes(cx: @ExtCtxt,
                                   span: span,
@@ -85,7 +85,7 @@ fn iter_bytes_substructure(cx: @ExtCtxt, span: span, substr: &Substructure) -> @
         cx.span_bug(span, "#[deriving(IterBytes)] needs at least one field");
     }
 
-    do vec::foldl(exprs[0], exprs.slice(1, exprs.len())) |prev, me| {
+    do exprs.slice(1, exprs.len()).iter().fold(exprs[0]) |prev, me| {
         cx.expr_binary(span, and, prev, *me)
     }
 }
diff --git a/src/libsyntax/ext/deriving/mod.rs b/src/libsyntax/ext/deriving/mod.rs
index 1107f21319c..c091ab8b617 100644
--- a/src/libsyntax/ext/deriving/mod.rs
+++ b/src/libsyntax/ext/deriving/mod.rs
@@ -19,6 +19,7 @@ library.
 */
 
 use core::prelude::*;
+use core::iterator::IteratorUtil;
 
 use ast::{enum_def, ident, item, Generics, meta_item, struct_def};
 use ext::base::ExtCtxt;
@@ -74,7 +75,7 @@ pub fn expand_meta_deriving(cx: @ExtCtxt,
             in_items
         }
         meta_list(_, ref titems) => {
-            do titems.foldr(in_items) |&titem, in_items| {
+            do titems.rev_iter().fold(in_items) |in_items, &titem| {
                 match titem.node {
                     meta_name_value(tname, _) |
                     meta_list(tname, _) |
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index e1f31b83524..1e1f411c050 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -11,11 +11,11 @@
 use core::prelude::*;
 
 use ast::{blk_, attribute_, attr_outer, meta_word};
-use ast::{crate, decl_local, expr_, expr_mac, mac_invoc_tt};
-use ast::{item_mac, local_, stmt_, stmt_decl, stmt_mac, stmt_expr, stmt_semi};
-use ast::{SCTable, illegal_ctxt};
+use ast::{crate, expr_, expr_mac, mac_invoc_tt};
+use ast::{item_mac, stmt_, stmt_mac, stmt_expr, stmt_semi};
+use ast::{illegal_ctxt};
 use ast;
-use ast_util::{new_rename, new_mark, resolve, get_sctable};
+use ast_util::{new_rename, new_mark, resolve};
 use attr;
 use codemap;
 use codemap::{span, CallInfo, ExpandedFrom, NameAndSpan, spanned};
@@ -23,10 +23,11 @@ use ext::base::*;
 use fold::*;
 use parse;
 use parse::{parse_item_from_source_str};
-use parse::token::{ident_to_str, intern, fresh_name};
+use parse::token::{ident_to_str, intern};
 use visit;
-use visit::{Visitor,mk_vt};
+use visit::Visitor;
 
+use core::iterator::IteratorUtil;
 use core::vec;
 
 pub fn expand_expr(extsbox: @mut SyntaxEnv,
@@ -128,7 +129,7 @@ pub fn expand_mod_items(extsbox: @mut SyntaxEnv,
     // decorated with "item decorators", then use that function to transform
     // the item into a new set of items.
     let new_items = do vec::flat_map(module_.items) |item| {
-        do vec::foldr(item.attrs, ~[*item]) |attr, items| {
+        do item.attrs.rev_iter().fold(~[*item]) |items, attr| {
             let mname = attr::get_attr_name(attr);
 
             match (*extsbox).find(&intern(*mname)) {
@@ -748,16 +749,14 @@ mod test {
     use super::*;
     use ast;
     use ast::{attribute_, attr_outer, meta_word, empty_ctxt};
-    use ast_util::{get_sctable};
     use codemap;
     use codemap::spanned;
     use parse;
-    use parse::token::{gensym, intern, get_ident_interner};
+    use parse::token::{intern, get_ident_interner};
     use print::pprust;
     use util::parser_testing::{string_to_item, string_to_pat, strs_to_idents};
-    use visit::{mk_vt,Visitor};
+    use visit::{mk_vt};
 
-    use core::io;
     use core::option::{None, Some};
 
     // make sure that fail! is present
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 5f43452cc83..a6ec91f899c 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -129,12 +129,12 @@ pub fn copy_up(mpu: &matcher_pos_up) -> ~MatcherPos {
 }
 
 pub fn count_names(ms: &[matcher]) -> uint {
-    vec::foldl(0u, ms, |ct, m| {
+    do ms.iter().fold(0) |ct, m| {
         ct + match m.node {
           match_tok(_) => 0u,
           match_seq(ref more_ms, _, _, _, _) => count_names((*more_ms)),
           match_nonterminal(_,_,_) => 1u
-        }})
+        }}
 }
 
 pub fn initial_matcher_pos(ms: ~[matcher], sep: Option<Token>, lo: BytePos)
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index f8a783c568a..f3bd2d4b8d1 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -19,9 +19,9 @@ use parse::token::{EOF, INTERPOLATED, IDENT, Token, nt_ident};
 use parse::token::{ident_to_str};
 use parse::lexer::TokenAndSpan;
 
+use core::iterator::IteratorUtil;
 use core::hashmap::HashMap;
 use core::option;
-use core::vec;
 
 ///an unzipping of `token_tree`s
 struct TtFrame {
@@ -113,9 +113,7 @@ fn lookup_cur_matched_by_matched(r: &mut TtReader,
           matched_seq(ref ads, _) => ads[*idx]
         }
     }
-    let r = &mut *r;
-    let repeat_idx = &r.repeat_idx;
-    vec::foldl(start, *repeat_idx, red)
+    r.repeat_idx.iter().fold(start, red)
 }
 
 fn lookup_cur_matched(r: &mut TtReader, name: ident) -> @named_match {
@@ -152,10 +150,10 @@ fn lockstep_iter_size(t: &token_tree, r: &mut TtReader) -> lis {
     }
     match *t {
       tt_delim(ref tts) | tt_seq(_, ref tts, _, _) => {
-        vec::foldl(lis_unconstrained, *tts, |lis, tt| {
+        do tts.iter().fold(lis_unconstrained) |lis, tt| {
             let lis2 = lockstep_iter_size(tt, r);
             lis_merge(lis, lis2)
-        })
+        }
       }
       tt_tok(*) => lis_unconstrained,
       tt_nonterminal(_, name) => match *lookup_cur_matched(r, name) {
diff --git a/src/libsyntax/parse/comments.rs b/src/libsyntax/parse/comments.rs
index 54fba29a19a..360ea12ec02 100644
--- a/src/libsyntax/parse/comments.rs
+++ b/src/libsyntax/parse/comments.rs
@@ -19,8 +19,8 @@ use parse::lexer::{is_line_non_doc_comment, is_block_non_doc_comment};
 use parse::lexer;
 use parse::token;
 use parse::token::{get_ident_interner};
-use parse;
 
+use core::iterator::IteratorUtil;
 use core::io;
 use core::str;
 use core::uint;
@@ -78,7 +78,7 @@ pub fn strip_doc_comment_decoration(comment: &str) -> ~str {
             if line.trim().is_empty() {
                 loop;
             }
-            for line.each_chari |j, c| {
+            for line.iter().enumerate().advance |(j, c)| {
                 if j >= i {
                     break;
                 }
@@ -91,7 +91,7 @@ pub fn strip_doc_comment_decoration(comment: &str) -> ~str {
 
         return do lines.map |line| {
             let mut chars = ~[];
-            for str::each_char(*line) |c| { chars.push(c) }
+            for line.iter().advance |c| { chars.push(c) }
             if i > chars.len() {
                 ~""
             } else {
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index d7248204e1c..559bca34f21 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -341,10 +341,9 @@ mod test {
     use codemap::{span, BytePos, spanned};
     use opt_vec;
     use ast;
-    use ast::{new_ident};
     use abi;
     use parse::parser::Parser;
-    use parse::token::{intern, str_to_ident};
+    use parse::token::{str_to_ident};
     use util::parser_testing::{string_to_tts_and_sess, string_to_parser};
     use util::parser_testing::{string_to_expr, string_to_item};
     use util::parser_testing::{string_to_stmt, strs_to_idents};
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index ecf83483c21..7359448a8f2 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -22,7 +22,6 @@ use core::char;
 use core::cmp::Equiv;
 use core::local_data;
 use core::str;
-use core::hashmap::HashSet;
 use core::rand;
 use core::rand::RngUtil;
 use core::to_bytes;
diff --git a/src/test/bench/graph500-bfs.rs b/src/test/bench/graph500-bfs.rs
index 38cc3127343..dee18c8a1b3 100644
--- a/src/test/bench/graph500-bfs.rs
+++ b/src/test/bench/graph500-bfs.rs
@@ -21,6 +21,7 @@ use extra::arc;
 use extra::time;
 use extra::deque::Deque;
 use extra::par;
+use std::iterator::IteratorUtil;
 use std::hashmap::HashSet;
 use std::int::abs;
 use std::io;
@@ -111,7 +112,7 @@ fn gen_search_keys(graph: &[~[node_id]], n: uint) -> ~[node_id] {
     while keys.len() < n {
         let k = r.gen_uint_range(0u, graph.len());
 
-        if graph[k].len() > 0u && vec::any(graph[k], |i| {
+        if graph[k].len() > 0u && graph[k].iter().any(|i| {
             *i != k as node_id
         }) {
             keys.insert(k as node_id);
@@ -187,7 +188,7 @@ fn bfs2(graph: graph, key: node_id) -> bfs_result {
     }
 
     let mut i = 0;
-    while vec::any(colors, is_gray) {
+    while colors.iter().any(is_gray) {
         // Do the BFS.
         info!("PBFS iteration %?", i);
         i += 1;
@@ -362,7 +363,7 @@ fn validate(edges: ~[(node_id, node_id)],
 
     info!(~"Verifying tree edges...");
 
-    let status = do tree.alli() |k, parent| {
+    let status = do tree.iter().enumerate().all |(k, parent)| {
         if *parent != root && *parent != -1i64 {
             level[*parent] == level[k] - 1
         }
diff --git a/src/test/compile-fail/block-arg-as-stmt-with-value.rs b/src/test/compile-fail/block-arg-as-stmt-with-value.rs
index dc90dfb2cad..ce8f5e502e8 100644
--- a/src/test/compile-fail/block-arg-as-stmt-with-value.rs
+++ b/src/test/compile-fail/block-arg-as-stmt-with-value.rs
@@ -8,12 +8,12 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 fn compute1() -> float {
     let v = ~[0f, 1f, 2f, 3f];
 
-    do vec::foldl(0f, v) |x, y| { x + *y } - 10f
+    do v.iter().fold(0f) |x, y| { x + *y } - 10f
     //~^ ERROR mismatched types: expected `()`
 }
 
diff --git a/src/test/compile-fail/issue-3044.rs b/src/test/compile-fail/issue-3044.rs
index 4cac844bdea..ee96cc293eb 100644
--- a/src/test/compile-fail/issue-3044.rs
+++ b/src/test/compile-fail/issue-3044.rs
@@ -8,13 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 fn main() {
     let needlesArr: ~[char] = ~['a', 'f'];
-    do vec::foldr(needlesArr) |x, y| {
+    do needlesArr.iter().fold() |x, y| {
     }
-    //~^ ERROR 2 parameters were supplied (including the closure passed by the `do` keyword)
+    //~^ ERROR 1 parameter was supplied (including the closure passed by the `do` keyword)
     //
     // the first error is, um, non-ideal.
 }
diff --git a/src/test/run-pass/block-arg-can-be-followed-by-binop.rs b/src/test/run-pass/block-arg-can-be-followed-by-binop.rs
index 73b436e7476..522516351d2 100644
--- a/src/test/run-pass/block-arg-can-be-followed-by-binop.rs
+++ b/src/test/run-pass/block-arg-can-be-followed-by-binop.rs
@@ -8,13 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 pub fn main() {
     let v = ~[-1f, 0f, 1f, 2f, 3f];
 
     // Trailing expressions don't require parentheses:
-    let y = do vec::foldl(0f, v) |x, y| { x + *y } + 10f;
+    let y = do v.iter().fold(0f) |x, y| { x + *y } + 10f;
 
     assert_eq!(y, 15f);
 }
diff --git a/src/test/run-pass/block-arg-can-be-followed-by-block-arg.rs b/src/test/run-pass/block-arg-can-be-followed-by-block-arg.rs
index 7894bf93848..c6d66e07444 100644
--- a/src/test/run-pass/block-arg-can-be-followed-by-block-arg.rs
+++ b/src/test/run-pass/block-arg-can-be-followed-by-block-arg.rs
@@ -8,11 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 pub fn main() {
     fn f(i: &fn() -> uint) -> uint { i() }
     let v = ~[-1f, 0f, 1f, 2f, 3f];
-    let z = do do vec::foldl(f, v) |x, _y| { x } { 22u };
+    let z = do do v.iter().fold(f) |x, _y| { x } { 22u };
     assert_eq!(z, 22u);
 }
diff --git a/src/test/run-pass/block-arg-can-be-followed-by-call.rs b/src/test/run-pass/block-arg-can-be-followed-by-call.rs
index 5fb6de19878..a205e9f8f31 100644
--- a/src/test/run-pass/block-arg-can-be-followed-by-call.rs
+++ b/src/test/run-pass/block-arg-can-be-followed-by-call.rs
@@ -8,11 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 pub fn main() {
     fn f(i: uint) -> uint { i }
     let v = ~[-1f, 0f, 1f, 2f, 3f];
-    let z = do vec::foldl(f, v) |x, _y| { x } (22u);
+    let z = do v.iter().fold(f) |x, _y| { x } (22u);
     assert_eq!(z, 22u);
 }
diff --git a/src/test/run-pass/block-arg-in-parentheses.rs b/src/test/run-pass/block-arg-in-parentheses.rs
index ec211a3a144..854b45f4672 100644
--- a/src/test/run-pass/block-arg-in-parentheses.rs
+++ b/src/test/run-pass/block-arg-in-parentheses.rs
@@ -8,25 +8,26 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::iterator::IteratorUtil;
 use std::vec;
 
 fn w_semi(v: ~[int]) -> int {
     // the semicolon causes compiler not to
     // complain about the ignored return value:
-    do vec::foldl(0, v) |x,y| { x+*y };
+    do v.iter().fold(0) |x,y| { x+*y };
     -10
 }
 
 fn w_paren1(v: ~[int]) -> int {
-    (do vec::foldl(0, v) |x,y| { x+*y }) - 10
+    (do v.iter().fold(0) |x,y| { x+*y }) - 10
 }
 
 fn w_paren2(v: ~[int]) -> int {
-    (do vec::foldl(0, v) |x,y| { x+*y} - 10)
+    (do v.iter().fold(0) |x,y| { x+*y} - 10)
 }
 
 fn w_ret(v: ~[int]) -> int {
-    return do vec::foldl(0, v) |x,y| { x+*y } - 10;
+    return do v.iter().fold(0) |x,y| { x+*y } - 10;
 }
 
 pub fn main() {
diff --git a/src/test/run-pass/block-arg.rs b/src/test/run-pass/block-arg.rs
index 906a3629f3a..c34948a8979 100644
--- a/src/test/run-pass/block-arg.rs
+++ b/src/test/run-pass/block-arg.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::iterator::IteratorUtil;
 use std::vec;
 
 // Check usage and precedence of block arguments in expressions:
@@ -20,28 +21,28 @@ pub fn main() {
     }
 
     // Usable at all:
-    let mut any_negative = do vec::any(v) |e| { e.is_negative() };
+    let mut any_negative = do v.iter().any |e| { e.is_negative() };
     assert!(any_negative);
 
     // Higher precedence than assignments:
-    any_negative = do vec::any(v) |e| { e.is_negative() };
+    any_negative = do v.iter().any |e| { e.is_negative() };
     assert!(any_negative);
 
     // Higher precedence than unary operations:
     let abs_v = do vec::map(v) |e| { e.abs() };
-    assert!(do vec::all(abs_v) |e| { e.is_positive() });
-    assert!(!do vec::any(abs_v) |e| { e.is_negative() });
+    assert!(do abs_v.iter().all |e| { e.is_positive() });
+    assert!(!do abs_v.iter().any |e| { e.is_negative() });
 
     // Usable in funny statement-like forms:
-    if !do vec::any(v) |e| { e.is_positive() } {
+    if !do v.iter().any |e| { e.is_positive() } {
         assert!(false);
     }
-    match do vec::all(v) |e| { e.is_negative() } {
+    match do v.iter().all |e| { e.is_negative() } {
         true => { fail!("incorrect answer."); }
         false => { }
     }
     match 3 {
-      _ if do vec::any(v) |e| { e.is_negative() } => {
+      _ if do v.iter().any |e| { e.is_negative() } => {
       }
       _ => {
         fail!("wrong answer.");
@@ -50,15 +51,15 @@ pub fn main() {
 
 
     // Lower precedence than binary operations:
-    let w = do vec::foldl(0f, v) |x, y| { x + *y } + 10f;
-    let y = do vec::foldl(0f, v) |x, y| { x + *y } + 10f;
-    let z = 10f + do vec::foldl(0f, v) |x, y| { x + *y };
+    let w = do v.iter().fold(0f) |x, y| { x + *y } + 10f;
+    let y = do v.iter().fold(0f) |x, y| { x + *y } + 10f;
+    let z = 10f + do v.iter().fold(0f) |x, y| { x + *y };
     assert_eq!(w, y);
     assert_eq!(y, z);
 
     // In the tail of a block
     let w =
-        if true { do vec::any(abs_v) |e| { e.is_positive() } }
+        if true { do abs_v.iter().any |e| { e.is_positive() } }
       else { false };
     assert!(w);
 }
diff --git a/src/test/run-pass/issue-2904.rs b/src/test/run-pass/issue-2904.rs
index 7670a7eee7c..fcebb528c10 100644
--- a/src/test/run-pass/issue-2904.rs
+++ b/src/test/run-pass/issue-2904.rs
@@ -14,6 +14,7 @@
 
 extern mod extra;
 
+use std::iterator::IteratorUtil;
 use std::io::ReaderUtil;
 use std::io;
 use std::str;
@@ -67,7 +68,7 @@ fn read_board_grid<rdr:'static + io::Reader>(in: rdr) -> ~[~[square]] {
     let mut grid = ~[];
     for in.each_line |line| {
         let mut row = ~[];
-        for str::each_char(line) |c| {
+        for line.iter().advance |c| {
             row.push(square_from_char(c))
         }
         grid.push(row)
diff --git a/src/test/run-pass/linear-for-loop.rs b/src/test/run-pass/linear-for-loop.rs
index 7ab915a9628..a42d70f5ae2 100644
--- a/src/test/run-pass/linear-for-loop.rs
+++ b/src/test/run-pass/linear-for-loop.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::str;
+use std::iterator::IteratorUtil;
 
 pub fn main() {
     let x = ~[1, 2, 3];
@@ -18,7 +18,7 @@ pub fn main() {
     assert_eq!(y, 6);
     let s = ~"hello there";
     let mut i: int = 0;
-    for str::each(s) |c| {
+    for s.bytes_iter().advance |c| {
         if i == 0 { assert!((c == 'h' as u8)); }
         if i == 1 { assert!((c == 'e' as u8)); }
         if i == 2 { assert!((c == 'l' as u8)); }
diff --git a/src/test/run-pass/ret-break-cont-in-block.rs b/src/test/run-pass/ret-break-cont-in-block.rs
index 80e6293bf50..4346d242c06 100644
--- a/src/test/run-pass/ret-break-cont-in-block.rs
+++ b/src/test/run-pass/ret-break-cont-in-block.rs
@@ -10,6 +10,7 @@
 
 // xfail-fast
 
+use std::iterator::IteratorUtil;
 use std::cmp::Eq;
 use std::vec;
 
@@ -54,7 +55,8 @@ fn ret_deep() -> ~str {
 
 pub fn main() {
     let mut last = 0;
-    for vec::all(~[1, 2, 3, 4, 5, 6, 7]) |e| {
+    let v = ~[1, 2, 3, 4, 5, 6, 7];
+    for v.iter().all |e| {
         last = *e;
         if *e == 5 { break; }
         if *e % 2 == 1 { loop; }
diff --git a/src/test/run-pass/test-ignore-cfg.rs b/src/test/run-pass/test-ignore-cfg.rs
index d8b12437dfa..cbfaa87b699 100644
--- a/src/test/run-pass/test-ignore-cfg.rs
+++ b/src/test/run-pass/test-ignore-cfg.rs
@@ -13,7 +13,7 @@
 
 extern mod extra;
 
-use std::vec;
+use std::iterator::IteratorUtil;
 
 #[test]
 #[ignore(cfg(ignorecfg))]
@@ -30,11 +30,9 @@ fn checktests() {
     // Pull the tests out of the secreturn test module
     let tests = __test::tests;
 
-    assert!(vec::any(
-        tests,
-        |t| t.desc.name.to_str() == ~"shouldignore" && t.desc.ignore));
+    assert!(
+        tests.iter().any(|t| t.desc.name.to_str() == ~"shouldignore" && t.desc.ignore));
 
-    assert!(vec::any(
-        tests,
-        |t| t.desc.name.to_str() == ~"shouldnotignore" && !t.desc.ignore));
+    assert!(
+        tests.iter().any(|t| t.desc.name.to_str() == ~"shouldnotignore" && !t.desc.ignore));
 }
diff --git a/src/test/run-pass/utf8.rs b/src/test/run-pass/utf8.rs
index fd5bc07e015..8a845439058 100644
--- a/src/test/run-pass/utf8.rs
+++ b/src/test/run-pass/utf8.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::str;
+use std::iterator::IteratorUtil;
 
 pub fn main() {
     let yen: char = '¥'; // 0xa5
@@ -43,7 +43,7 @@ pub fn main() {
 
     fn check_str_eq(a: ~str, b: ~str) {
         let mut i: int = 0;
-        for str::each(a) |ab| {
+        for a.bytes_iter().advance |ab| {
             debug!(i);
             debug!(ab);
             let bb: u8 = b[i];