auto merge of #5005 : alexcrichton/rust/bitv++, r=catamorphism

These commits take the old bitv implementation and modernize it with an explicit self, some minor touchups, and using what I think is some more recent patterns (like `::new` instead of `Type()`).

Additionally, this adds an implementation of `container::Set` on top of a bit vector to have as a set of `uint`s. I initially tried to parameterize the type for the set to be `T: NumCast` but I was hitting build problems in stage0 which I think means that it's not in a snapshot yet, so it's just hardcoded as a set of `uint`s now. In the future perhaps it could be parameterized. I'm not sure if it would really add anything, though, so maybe it's nicer to be hardcoded anyway.

I also added some extra methods to do normal bit vector operations on the set in-place, but these aren't a part of the `Set` trait right now. I haven't benchmarked any of these operations just yet, but I imagine that there's quite a lot of room for optimization here and there.

1 files changed, 8 insertions, 4 deletions

diff --git a/src/libsyntax/ext/pipes/liveness.rs b/src/libsyntax/ext/pipes/liveness.rs
index c690c89c025..a7f01d75648 100644
--- a/src/libsyntax/ext/pipes/liveness.rs
+++ b/src/libsyntax/ext/pipes/liveness.rs
@@ -43,13 +43,13 @@ use ext::base::ext_ctxt;
 use ext::pipes::proto::protocol;
 
 use core::str;
-use std::bitv::{Bitv};
+use std::bitv::Bitv;
 
 pub fn analyze(proto: protocol, _cx: ext_ctxt) {
     debug!("initializing colive analysis");
     let num_states = proto.num_states();
-    let colive = do (copy proto.states).map_to_vec |state| {
-        let bv = ~Bitv(num_states, false);
+    let mut colive = do (copy proto.states).map_to_vec |state| {
+        let mut bv = ~Bitv::new(num_states, false);
         for state.reachable |s| {
             bv.set(s.id, true);
         }
@@ -61,15 +61,19 @@ pub fn analyze(proto: protocol, _cx: ext_ctxt) {
     while changed {
         changed = false;
         debug!("colive iteration %?", i);
+        let mut new_colive = ~[];
         for colive.eachi |i, this_colive| {
+            let mut result = ~this_colive.clone();
             let this = proto.get_state_by_id(i);
             for this_colive.ones |j| {
                 let next = proto.get_state_by_id(j);
                 if this.dir == next.dir {
-                    changed = changed || this_colive.union(colive[j]);
+                    changed = result.union(colive[j]) || changed;
                 }
             }
+            new_colive.push(result)
         }
+        colive = new_colive;
         i += 1;
     }