std: Use the new `for` protocol

9 files changed, 433 insertions, 51 deletions

diff --git a/src/libstd/bitv.rs b/src/libstd/bitv.rs
index 461fb61ed56..09f86f30d32 100644
--- a/src/libstd/bitv.rs
+++ b/src/libstd/bitv.rs
@@ -143,6 +143,7 @@ pub impl BigBitv {
     }
 
     #[inline(always)]
+    #[cfg(stage0)]
     fn each_storage(&mut self, op: &fn(v: &mut uint) -> bool) {
         for uint::range(0, self.storage.len()) |i| {
             let mut w = self.storage[i];
@@ -150,7 +151,12 @@ pub impl BigBitv {
             self.storage[i] = w;
             if !b { break; }
         }
-     }
+    }
+    #[inline(always)]
+    #[cfg(not(stage0))]
+    fn each_storage(&mut self, op: &fn(v: &mut uint) -> bool) -> bool {
+        uint::range(0, self.storage.len(), |i| op(&mut self.storage[i]))
+    }
 
     #[inline(always)]
     fn invert(&mut self) { for self.each_storage |w| { *w = !*w } }
@@ -193,6 +199,7 @@ pub impl BigBitv {
     }
 
     #[inline(always)]
+    #[cfg(stage0)]
     fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
         let len = b.storage.len();
         for uint::iterate(0, len) |i| {
@@ -203,6 +210,19 @@ pub impl BigBitv {
         }
     }
 
+    #[inline(always)]
+    #[cfg(not(stage0))]
+    fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
+        let len = b.storage.len();
+        for uint::iterate(0, len) |i| {
+            let mask = big_mask(nbits, i);
+            if mask & self.storage[i] != mask & b.storage[i] {
+                return false;
+            }
+        }
+        return true;
+    }
+
 }
 
 enum BitvVariant { Big(~BigBitv), Small(~SmallBitv) }
@@ -387,6 +407,7 @@ pub impl Bitv {
     }
 
     #[inline(always)]
+    #[cfg(stage0)]
     fn each(&self, f: &fn(bool) -> bool) {
         let mut i = 0;
         while i < self.nbits {
@@ -394,6 +415,16 @@ pub impl Bitv {
             i += 1;
         }
     }
+    #[inline(always)]
+    #[cfg(not(stage0))]
+    fn each(&self, f: &fn(bool) -> bool) -> bool {
+        let mut i = 0;
+        while i < self.nbits {
+            if !f(self.get(i)) { return false; }
+            i += 1;
+        }
+        return true;
+    }
 
     /// Returns true if all bits are 0
     fn is_false(&self) -> bool {
@@ -488,6 +519,7 @@ pub impl Bitv {
         true
     }
 
+    #[cfg(stage0)]
     fn ones(&self, f: &fn(uint) -> bool) {
         for uint::range(0, self.nbits) |i| {
             if self.get(i) {
@@ -495,6 +527,10 @@ pub impl Bitv {
             }
         }
     }
+    #[cfg(not(stage0))]
+    fn ones(&self, f: &fn(uint) -> bool) -> bool {
+        uint::range(0, self.nbits, |i| !self.get(i) || f(i))
+    }
 
 }
 
@@ -661,18 +697,21 @@ pub impl BitvSet {
     }
 }
 
+#[cfg(not(stage0))]
 impl BaseIter<uint> for BitvSet {
     fn size_hint(&self) -> Option<uint> { Some(self.len()) }
 
-    fn each(&self, blk: &fn(v: &uint) -> bool) {
+    fn each(&self, blk: &fn(v: &uint) -> bool) -> bool {
         for self.bitv.storage.eachi |i, &w| {
             if !iterate_bits(i * uint::bits, w, |b| blk(&b)) {
-                return;
+                return false;
             }
         }
+        return true;
     }
 }
 
+#[cfg(not(stage0))]
 impl cmp::Eq for BitvSet {
     fn eq(&self, other: &BitvSet) -> bool {
         if self.size != other.size {
@@ -706,6 +745,7 @@ impl Mutable for BitvSet {
     }
 }
 
+#[cfg(not(stage0))]
 impl Set<uint> for BitvSet {
     fn contains(&self, value: &uint) -> bool {
         *value < self.bitv.storage.len() * uint::bits && self.bitv.get(*value)
@@ -773,64 +813,55 @@ impl Set<uint> for BitvSet {
         other.is_subset(self)
     }
 
-    fn difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) {
+    fn difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool {
         for self.each_common(other) |i, w1, w2| {
             if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
-                return;
+                return false;
             }
         }
         /* everything we have that they don't also shows up */
         self.each_outlier(other, |mine, i, w|
             !mine || iterate_bits(i, w, |b| f(&b))
-        );
+        )
     }
 
     fn symmetric_difference(&self, other: &BitvSet,
-                                 f: &fn(&uint) -> bool) {
+                            f: &fn(&uint) -> bool) -> bool {
         for self.each_common(other) |i, w1, w2| {
             if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
-                return;
+                return false;
             }
         }
-        self.each_outlier(other, |_, i, w|
-            iterate_bits(i, w, |b| f(&b))
-        );
+        self.each_outlier(other, |_, i, w| iterate_bits(i, w, |b| f(&b)))
     }
 
-    fn intersection(&self, other: &BitvSet, f: &fn(&uint) -> bool) {
-        for self.each_common(other) |i, w1, w2| {
-            if !iterate_bits(i, w1 & w2, |b| f(&b)) {
-                return;
-            }
-        }
+    fn intersection(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool {
+        self.each_common(other, |i, w1, w2| iterate_bits(i, w1 & w2, |b| f(&b)))
     }
 
-    fn union(&self, other: &BitvSet, f: &fn(&uint) -> bool) {
+    fn union(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool {
         for self.each_common(other) |i, w1, w2| {
             if !iterate_bits(i, w1 | w2, |b| f(&b)) {
-                return;
+                return false;
             }
         }
-        self.each_outlier(other, |_, i, w|
-            iterate_bits(i, w, |b| f(&b))
-        );
+        self.each_outlier(other, |_, i, w| iterate_bits(i, w, |b| f(&b)))
     }
 }
 
+#[cfg(not(stage0))]
 priv impl BitvSet {
     /// Visits each of the words that the two bit vectors (self and other)
     /// both have in common. The three yielded arguments are (bit location,
     /// w1, w2) where the bit location is the number of bits offset so far,
     /// and w1/w2 are the words coming from the two vectors self, other.
     fn each_common(&self, other: &BitvSet,
-                        f: &fn(uint, uint, uint) -> bool) {
+                   f: &fn(uint, uint, uint) -> bool) -> bool {
         let min = uint::min(self.bitv.storage.len(),
                             other.bitv.storage.len());
-        for self.bitv.storage.slice(0, min).eachi |i, &w| {
-            if !f(i * uint::bits, w, other.bitv.storage[i]) {
-                return;
-            }
-        }
+        self.bitv.storage.slice(0, min).eachi(|i, &w| {
+            f(i * uint::bits, w, other.bitv.storage[i])
+        })
     }
 
     /// Visits each word in self or other that extends beyond the other. This
@@ -841,7 +872,7 @@ priv impl BitvSet {
     /// is true if the word comes from 'self', and false if it comes from
     /// 'other'.
     fn each_outlier(&self, other: &BitvSet,
-                         f: &fn(bool, uint, uint) -> bool) {
+                    f: &fn(bool, uint, uint) -> bool) -> bool {
         let len1 = self.bitv.storage.len();
         let len2 = other.bitv.storage.len();
         let min = uint::min(len1, len2);
@@ -849,14 +880,15 @@ priv impl BitvSet {
         /* only one of these loops will execute and that's the point */
         for self.bitv.storage.slice(min, len1).eachi |i, &w| {
             if !f(true, (i + min) * uint::bits, w) {
-                return;
+                return false;
             }
         }
         for other.bitv.storage.slice(min, len2).eachi |i, &w| {
             if !f(false, (i + min) * uint::bits, w) {
-                return;
+                return false;
             }
         }
+        return true;
     }
 }
 
diff --git a/src/libstd/deque.rs b/src/libstd/deque.rs
index 4c7f2edc6b0..4eb359e48a8 100644
--- a/src/libstd/deque.rs
+++ b/src/libstd/deque.rs
@@ -63,15 +63,25 @@ pub impl<T> Deque<T> {
     }
 
     /// Iterate over the elements in the deque
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&T) -> bool) {
         self.eachi(|_i, e| f(e))
     }
+    /// Iterate over the elements in the deque
+    #[cfg(not(stage0))]
+    fn each(&self, f: &fn(&T) -> bool) -> bool {
+        self.eachi(|_i, e| f(e))
+    }
 
     /// Iterate over the elements in the deque by index
+    #[cfg(stage0)]
     fn eachi(&self, f: &fn(uint, &T) -> bool) {
-        for uint::range(0, self.nelts) |i| {
-            if !f(i, self.get(i as int)) { return; }
-        }
+        uint::range(0, self.nelts, |i| f(i, self.get(i as int)))
+    }
+    /// Iterate over the elements in the deque by index
+    #[cfg(not(stage0))]
+    fn eachi(&self, f: &fn(uint, &T) -> bool) -> bool {
+        uint::range(0, self.nelts, |i| f(i, self.get(i as int)))
     }
 
     /// Remove and return the first element in the deque
diff --git a/src/libstd/dlist.rs b/src/libstd/dlist.rs
index 1257d554532..93740f31b9b 100644
--- a/src/libstd/dlist.rs
+++ b/src/libstd/dlist.rs
@@ -492,12 +492,13 @@ pub impl<T:Copy> DList<T> {
 
 impl<T> BaseIter<T> for @mut DList<T> {
     /**
-    * Iterates through the current contents.
-    *
-    * Attempts to access this dlist during iteration are allowed (to
-    * allow for e.g. breadth-first search with in-place enqueues), but
-    * removing the current node is forbidden.
-    */
+     * Iterates through the current contents.
+     *
+     * Attempts to access this dlist during iteration are allowed (to
+     * allow for e.g. breadth-first search with in-place enqueues), but
+     * removing the current node is forbidden.
+     */
+    #[cfg(stage0)]
     fn each(&self, f: &fn(v: &T) -> bool) {
         let mut link = self.peek_n();
         while link.is_some() {
@@ -525,6 +526,42 @@ impl<T> BaseIter<T> for @mut DList<T> {
             link = nobe.next_link();
         }
     }
+    /**
+     * Iterates through the current contents.
+     *
+     * Attempts to access this dlist during iteration are allowed (to
+     * allow for e.g. breadth-first search with in-place enqueues), but
+     * removing the current node is forbidden.
+     */
+    #[cfg(not(stage0))]
+    fn each(&self, f: &fn(v: &T) -> bool) -> bool {
+        let mut link = self.peek_n();
+        while link.is_some() {
+            let nobe = link.get();
+            assert!(nobe.linked);
+
+            {
+                let frozen_nobe = &*nobe;
+                if !f(&frozen_nobe.data) { return false; }
+            }
+
+            // Check (weakly) that the user didn't do a remove.
+            if self.size == 0 {
+                fail!("The dlist became empty during iteration??")
+            }
+            if !nobe.linked ||
+                (!((nobe.prev.is_some()
+                    || managed::mut_ptr_eq(self.hd.expect(~"headless dlist?"),
+                                           nobe))
+                   && (nobe.next.is_some()
+                    || managed::mut_ptr_eq(self.tl.expect(~"tailless dlist?"),
+                                           nobe)))) {
+                fail!("Removing a dlist node during iteration is forbidden!")
+            }
+            link = nobe.next_link();
+        }
+        return true;
+    }
 
     #[inline(always)]
     fn size_hint(&self) -> Option<uint> { Some(self.len()) }
diff --git a/src/libstd/list.rs b/src/libstd/list.rs
index 8d15508b26e..13ef377fabe 100644
--- a/src/libstd/list.rs
+++ b/src/libstd/list.rs
@@ -140,6 +140,7 @@ pub fn iter<T>(l: @List<T>, f: &fn(&T)) {
 }
 
 /// Iterate over a list
+#[cfg(stage0)]
 pub fn each<T>(l: @List<T>, f: &fn(&T) -> bool) {
     let mut cur = l;
     loop {
@@ -152,9 +153,24 @@ pub fn each<T>(l: @List<T>, f: &fn(&T) -> bool) {
         }
     }
 }
+/// Iterate over a list
+#[cfg(not(stage0))]
+pub fn each<T>(l: @List<T>, f: &fn(&T) -> bool) -> bool {
+    let mut cur = l;
+    loop {
+        cur = match *cur {
+          Cons(ref hd, tl) => {
+            if !f(hd) { return false; }
+            tl
+          }
+          Nil => { return true; }
+        }
+    }
+}
 
 impl<T> MutList<T> {
     /// Iterate over a mutable list
+    #[cfg(stage0)]
     pub fn each(@mut self, f: &fn(&mut T) -> bool) {
         let mut cur = self;
         loop {
@@ -170,6 +186,24 @@ impl<T> MutList<T> {
             }
         }
     }
+    /// Iterate over a mutable list
+    #[cfg(not(stage0))]
+    pub fn each(@mut self, f: &fn(&mut T) -> bool) -> bool {
+        let mut cur = self;
+        loop {
+            let borrowed = &mut *cur;
+            cur = match *borrowed {
+                MutCons(ref mut hd, tl) => {
+                    if !f(hd) {
+                        return false;
+                    }
+                    tl
+                }
+                MutNil => break
+            }
+        }
+        return true;
+    }
 }
 
 #[cfg(test)]
diff --git a/src/libstd/net_url.rs b/src/libstd/net_url.rs
index ba3fd69e344..e7cf710cf67 100644
--- a/src/libstd/net_url.rs
+++ b/src/libstd/net_url.rs
@@ -703,11 +703,18 @@ impl ToStr for Url {
     }
 }
 
+#[cfg(stage0)]
 impl IterBytes for Url {
     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
         self.to_str().iter_bytes(lsb0, f)
     }
 }
+#[cfg(not(stage0))]
+impl IterBytes for Url {
+    fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) -> bool {
+        self.to_str().iter_bytes(lsb0, f)
+    }
+}
 
 // Put a few tests outside of the 'test' module so they can test the internal
 // functions and those functions don't need 'pub'
diff --git a/src/libstd/priority_queue.rs b/src/libstd/priority_queue.rs
index b2f8c9c3c4e..bdb93142472 100644
--- a/src/libstd/priority_queue.rs
+++ b/src/libstd/priority_queue.rs
@@ -28,7 +28,14 @@ impl<T:Ord> BaseIter<T> for PriorityQueue<T> {
     /// Visit all values in the underlying vector.
     ///
     /// The values are **not** visited in order.
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&T) -> bool) { self.data.each(f) }
+    /// Visit all values in the underlying vector.
+    ///
+    /// The values are **not** visited in order.
+    #[cfg(not(stage0))]
+    fn each(&self, f: &fn(&T) -> bool) -> bool { self.data.each(f) }
+
     fn size_hint(&self) -> Option<uint> { self.data.size_hint() }
 }
 
diff --git a/src/libstd/smallintmap.rs b/src/libstd/smallintmap.rs
index fc83a39cacf..afc1d0fe65f 100644
--- a/src/libstd/smallintmap.rs
+++ b/src/libstd/smallintmap.rs
@@ -51,6 +51,7 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
     }
 
     /// Visit all key-value pairs in order
+    #[cfg(stage0)]
     fn each<'a>(&'a self, it: &fn(&uint, &'a V) -> bool) {
         for uint::range(0, self.v.len()) |i| {
             match self.v[i] {
@@ -60,25 +61,62 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
         }
     }
 
+    /// Visit all key-value pairs in order
+    #[cfg(not(stage0))]
+    fn each<'a>(&'a self, it: &fn(&uint, &'a V) -> bool) -> bool {
+        for uint::range(0, self.v.len()) |i| {
+            match self.v[i] {
+              Some(ref elt) => if !it(&i, elt) { return false; },
+              None => ()
+            }
+        }
+        return true;
+    }
+
     /// Visit all keys in order
+    #[cfg(stage0)]
     fn each_key(&self, blk: &fn(key: &uint) -> bool) {
         self.each(|k, _| blk(k))
     }
+    #[cfg(not(stage0))]
+    /// Visit all keys in order
+    fn each_key(&self, blk: &fn(key: &uint) -> bool) -> bool {
+        self.each(|k, _| blk(k))
+    }
 
     /// Visit all values in order
+    #[cfg(stage0)]
     fn each_value<'a>(&'a self, blk: &fn(value: &'a V) -> bool) {
         self.each(|_, v| blk(v))
     }
 
+    /// Visit all values in order
+    #[cfg(not(stage0))]
+    fn each_value<'a>(&'a self, blk: &fn(value: &'a V) -> bool) -> bool {
+        self.each(|_, v| blk(v))
+    }
+
     /// Iterate over the map and mutate the contained values
+    #[cfg(stage0)]
     fn mutate_values(&mut self, it: &fn(&uint, &mut V) -> bool) {
         for uint::range(0, self.v.len()) |i| {
             match self.v[i] {
-              Some(ref mut elt) => if !it(&i, elt) { break },
+              Some(ref mut elt) => if !it(&i, elt) { return; },
               None => ()
             }
         }
     }
+    /// Iterate over the map and mutate the contained values
+    #[cfg(not(stage0))]
+    fn mutate_values(&mut self, it: &fn(&uint, &mut V) -> bool) -> bool {
+        for uint::range(0, self.v.len()) |i| {
+            match self.v[i] {
+              Some(ref mut elt) => if !it(&i, elt) { return false; },
+              None => ()
+            }
+        }
+        return true;
+    }
 
     /// Return a reference to the value corresponding to the key
     fn find<'a>(&'a self, key: &uint) -> Option<&'a V> {
@@ -149,6 +187,7 @@ pub impl<V> SmallIntMap<V> {
     fn new() -> SmallIntMap<V> { SmallIntMap{v: ~[]} }
 
     /// Visit all key-value pairs in reverse order
+    #[cfg(stage0)]
     fn each_reverse<'a>(&'a self, it: &fn(uint, &'a V) -> bool) {
         for uint::range_rev(self.v.len(), 0) |i| {
             match self.v[i - 1] {
@@ -158,6 +197,18 @@ pub impl<V> SmallIntMap<V> {
         }
     }
 
+    /// Visit all key-value pairs in reverse order
+    #[cfg(not(stage0))]
+    fn each_reverse<'a>(&'a self, it: &fn(uint, &'a V) -> bool) -> bool {
+        for uint::range_rev(self.v.len(), 0) |i| {
+            match self.v[i - 1] {
+              Some(ref elt) => if !it(i - 1, elt) { return false; },
+              None => ()
+            }
+        }
+        return true;
+    }
+
     fn get<'a>(&'a self, key: &uint) -> &'a V {
         self.find(key).expect("key not present")
     }
diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index 06ac1a71bac..d68b08dc475 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -105,24 +105,48 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
     }
 
     /// Visit all key-value pairs in order
+    #[cfg(stage0)]
     fn each<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) {
+        each(&self.root, f);
+    }
+    /// Visit all key-value pairs in order
+    #[cfg(not(stage0))]
+    fn each<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) -> bool {
         each(&self.root, f)
     }
 
     /// Visit all keys in order
+    #[cfg(stage0)]
     fn each_key(&self, f: &fn(&K) -> bool) {
         self.each(|k, _| f(k))
     }
+    /// Visit all keys in order
+    #[cfg(not(stage0))]
+    fn each_key(&self, f: &fn(&K) -> bool) -> bool {
+        self.each(|k, _| f(k))
+    }
 
     /// Visit all values in order
+    #[cfg(stage0)]
     fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) {
         self.each(|_, v| f(v))
     }
+    /// Visit all values in order
+    #[cfg(not(stage0))]
+    fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) -> bool {
+        self.each(|_, v| f(v))
+    }
 
     /// Iterate over the map and mutate the contained values
+    #[cfg(stage0)]
     fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool) {
         mutate_values(&mut self.root, f);
     }
+    /// Iterate over the map and mutate the contained values
+    #[cfg(not(stage0))]
+    fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool) -> bool {
+        mutate_values(&mut self.root, f)
+    }
 
     /// Return a reference to the value corresponding to the key
     fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
@@ -177,6 +201,7 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
     }
 }
 
+#[cfg(stage0)]
 pub impl<K: TotalOrd, V> TreeMap<K, V> {
     /// Create an empty TreeMap
     fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
@@ -202,6 +227,32 @@ pub impl<K: TotalOrd, V> TreeMap<K, V> {
         TreeMapIterator{stack: ~[], node: &self.root}
     }
 }
+#[cfg(not(stage0))]
+pub impl<K: TotalOrd, V> TreeMap<K, V> {
+    /// Create an empty TreeMap
+    fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
+
+    /// Visit all key-value pairs in reverse order
+    fn each_reverse<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) -> bool {
+        each_reverse(&self.root, f)
+    }
+
+    /// Visit all keys in reverse order
+    fn each_key_reverse(&self, f: &fn(&K) -> bool) -> bool {
+        self.each_reverse(|k, _| f(k))
+    }
+
+    /// Visit all values in reverse order
+    fn each_value_reverse(&self, f: &fn(&V) -> bool) -> bool {
+        self.each_reverse(|_, v| f(v))
+    }
+
+    /// Get a lazy iterator over the key-value pairs in the map.
+    /// Requires that it be frozen (immutable).
+    fn iter<'a>(&'a self) -> TreeMapIterator<'a, K, V> {
+        TreeMapIterator{stack: ~[], node: &self.root}
+    }
+}
 
 /// Lazy forward iterator over a map
 pub struct TreeMapIterator<'self, K, V> {
@@ -246,17 +297,29 @@ pub struct TreeSet<T> {
 impl<T: TotalOrd> BaseIter<T> for TreeSet<T> {
     /// Visit all values in order
     #[inline(always)]
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&T) -> bool) { self.map.each_key(f) }
+    /// Visit all values in order
+    #[inline(always)]
+    #[cfg(not(stage0))]
+    fn each(&self, f: &fn(&T) -> bool) -> bool { self.map.each_key(f) }
     #[inline(always)]
     fn size_hint(&self) -> Option<uint> { Some(self.len()) }
 }
 
 impl<T: TotalOrd> ReverseIter<T> for TreeSet<T> {
     /// Visit all values in reverse order
+    #[cfg(stage0)]
     #[inline(always)]
     fn each_reverse(&self, f: &fn(&T) -> bool) {
         self.map.each_key_reverse(f)
     }
+    /// Visit all values in reverse order
+    #[cfg(not(stage0))]
+    #[inline(always)]
+    fn each_reverse(&self, f: &fn(&T) -> bool) -> bool {
+        self.map.each_key_reverse(f)
+    }
 }
 
 impl<T: Eq + TotalOrd> Eq for TreeSet<T> {
@@ -361,6 +424,7 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
     }
 
     /// Visit the values (in-order) representing the difference
+    #[cfg(stage0)]
     fn difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) {
         let mut x = self.iter();
         let mut y = other.iter();
@@ -389,8 +453,38 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
             }
         }
     }
+    /// Visit the values (in-order) representing the difference
+    #[cfg(not(stage0))]
+    fn difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool {
+        let mut x = self.iter();
+        let mut y = other.iter();
+
+        let mut a = x.next();
+        let mut b = y.next();
+
+        while a.is_some() {
+            if b.is_none() {
+                return f(a.unwrap()) && x.advance(f);
+            }
+
+            let a1 = a.unwrap();
+            let b1 = b.unwrap();
+
+            let cmp = a1.cmp(b1);
+
+            if cmp == Less {
+                if !f(a1) { return false; }
+                a = x.next();
+            } else {
+                if cmp == Equal { a = x.next() }
+                b = y.next();
+            }
+        }
+        return true;
+    }
 
     /// Visit the values (in-order) representing the symmetric difference
+    #[cfg(stage0)]
     fn symmetric_difference(&self, other: &TreeSet<T>,
                                  f: &fn(&T) -> bool) {
         let mut x = self.iter();
@@ -427,8 +521,43 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
             if f(b1) { y.next() } else { None }
         }
     }
+    /// Visit the values (in-order) representing the symmetric difference
+    #[cfg(not(stage0))]
+    fn symmetric_difference(&self, other: &TreeSet<T>,
+                            f: &fn(&T) -> bool) -> bool {
+        let mut x = self.iter();
+        let mut y = other.iter();
+
+        let mut a = x.next();
+        let mut b = y.next();
+
+        while a.is_some() {
+            if b.is_none() {
+                return f(a.unwrap()) && x.advance(f);
+            }
+
+            let a1 = a.unwrap();
+            let b1 = b.unwrap();
+
+            let cmp = a1.cmp(b1);
+
+            if cmp == Less {
+                if !f(a1) { return false; }
+                a = x.next();
+            } else {
+                if cmp == Greater {
+                    if !f(b1) { return false; }
+                } else {
+                    a = x.next();
+                }
+                b = y.next();
+            }
+        }
+        return b.each(|&x| f(x)) && y.advance(f);
+    }
 
     /// Visit the values (in-order) representing the intersection
+    #[cfg(stage0)]
     fn intersection(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) {
         let mut x = self.iter();
         let mut y = other.iter();
@@ -452,8 +581,35 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
             }
         }
     }
+    /// Visit the values (in-order) representing the intersection
+    #[cfg(not(stage0))]
+    fn intersection(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool {
+        let mut x = self.iter();
+        let mut y = other.iter();
+
+        let mut a = x.next();
+        let mut b = y.next();
+
+        while a.is_some() && b.is_some() {
+            let a1 = a.unwrap();
+            let b1 = b.unwrap();
+
+            let cmp = a1.cmp(b1);
+
+            if cmp == Less {
+                a = x.next();
+            } else {
+                if cmp == Equal {
+                    if !f(a1) { return false }
+                }
+                b = y.next();
+            }
+        }
+        return true;
+    }
 
     /// Visit the values (in-order) representing the union
+    #[cfg(stage0)]
     fn union(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) {
         let mut x = self.iter();
         let mut y = other.iter();
@@ -488,6 +644,38 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
             if f(b1) { y.next() } else { None }
         }
     }
+    /// Visit the values (in-order) representing the union
+    #[cfg(not(stage0))]
+    fn union(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool {
+        let mut x = self.iter();
+        let mut y = other.iter();
+
+        let mut a = x.next();
+        let mut b = y.next();
+
+        while a.is_some() {
+            if b.is_none() {
+                return f(a.unwrap()) && x.advance(f);
+            }
+
+            let a1 = a.unwrap();
+            let b1 = b.unwrap();
+
+            let cmp = a1.cmp(b1);
+
+            if cmp == Greater {
+                if !f(b1) { return false; }
+                b = y.next();
+            } else {
+                if !f(a1) { return false; }
+                if cmp == Equal {
+                    b = y.next();
+                }
+                a = x.next();
+            }
+        }
+        return a.each(|&x| f(x)) && y.advance(f);
+    }
 }
 
 pub impl <T: TotalOrd> TreeSet<T> {
@@ -525,20 +713,28 @@ pub impl<K: TotalOrd, V> TreeNode<K, V> {
     }
 }
 
+#[cfg(stage0)]
+fn each<'r, K: TotalOrd, V>(_: &'r Option<~TreeNode<K, V>>,
+                            _: &fn(&'r K, &'r V) -> bool) -> bool {
+    fail!(~"don't use me in stage0!")
+}
+#[cfg(not(stage0))]
 fn each<'r, K: TotalOrd, V>(node: &'r Option<~TreeNode<K, V>>,
-                            f: &fn(&'r K, &'r V) -> bool) {
-    for node.each |x| {
-        each(&x.left, f);
-        if f(&x.key, &x.value) { each(&x.right, f) }
-    }
+                            f: &fn(&'r K, &'r V) -> bool) -> bool {
+    node.each(|x| each(&x.left, f) && f(&x.key, &x.value) &&
+                  each(&x.right, f))
 }
 
+#[cfg(stage0)]
+fn each_reverse<'r, K: TotalOrd, V>(_: &'r Option<~TreeNode<K, V>>,
+                                    _: &fn(&'r K, &'r V) -> bool) -> bool {
+    fail!(~"don't use me in stage0!")
+}
+#[cfg(not(stage0))]
 fn each_reverse<'r, K: TotalOrd, V>(node: &'r Option<~TreeNode<K, V>>,
-                                    f: &fn(&'r K, &'r V) -> bool) {
-    for node.each |x| {
-        each_reverse(&x.right, f);
-        if f(&x.key, &x.value) { each_reverse(&x.left, f) }
-    }
+                                    f: &fn(&'r K, &'r V) -> bool) -> bool {
+    node.each(|x| each_reverse(&x.right, f) && f(&x.key, &x.value) &&
+                  each_reverse(&x.left, f))
 }
 
 fn mutate_values<'r, K: TotalOrd, V>(node: &'r mut Option<~TreeNode<K, V>>,
diff --git a/src/libstd/workcache.rs b/src/libstd/workcache.rs
index dc9204f62f4..9b0a6cb6226 100644
--- a/src/libstd/workcache.rs
+++ b/src/libstd/workcache.rs
@@ -99,6 +99,7 @@ struct WorkKey {
     name: ~str
 }
 
+#[cfg(stage0)]
 impl to_bytes::IterBytes for WorkKey {
     #[inline(always)]
     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
@@ -108,6 +109,13 @@ impl to_bytes::IterBytes for WorkKey {
         self.name.iter_bytes(lsb0, f);
     }
 }
+#[cfg(not(stage0))]
+impl to_bytes::IterBytes for WorkKey {
+    #[inline(always)]
+    fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) -> bool {
+        self.kind.iter_bytes(lsb0, f) && self.name.iter_bytes(lsb0, f)
+    }
+}
 
 impl cmp::Ord for WorkKey {
     fn lt(&self, other: &WorkKey) -> bool {