auto merge of #11615 : adwhit/rust/master, r=cmr

This is my first patch so feedback appreciated!

Bug when initialising `bitv:Bitv::new(int,bool)` when `bool=true`. It created a `Bitv` with underlying representation `!0u` rather than the actual desired bit layout ( e.g. `11111111` instead of `00001111`). This works OK because a size attribute is included which keeps access to legal bounds.  However when using `BitvSet::from_bitv(Bitv)`, we then find that `bitvset.contains(i)` can return true when `i` should not in fact be in the set.

```
let bs = BitvSet::from_bitv(Bitv::new(100, true));
assert!(!bs.contains(&127)) //fails
```

The fix is to create the correct representation by treating various cases separately and using a bitshift `(1<<nbits) - 1` to generate correct number of `1`s where necessary.

1 files changed, 30 insertions, 7 deletions

diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs
index 5fd1bb9d599..305c9702001 100644
--- a/src/libextra/bitv.rs
+++ b/src/libextra/bitv.rs
@@ -269,14 +269,23 @@ impl Bitv {
 
 impl Bitv {
     pub fn new(nbits: uint, init: bool) -> Bitv {
-        let rep = if nbits <= uint::bits {
+        let rep = if nbits < uint::bits {
+            Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
+        } else if nbits == uint::bits {
             Small(SmallBitv::new(if init {!0} else {0}))
-        }
-        else {
-            let nelems = nbits/uint::bits +
-                         if nbits % uint::bits == 0 {0} else {1};
-            let elem = if init {!0u} else {0u};
-            let s = vec::from_elem(nelems, elem);
+        } else {
+            let exact = nbits % uint::bits == 0;
+            let nelems = nbits/uint::bits + if exact {0} else {1};
+            let s =
+                if init {
+                    if exact {
+                        vec::from_elem(nelems, !0u)
+                    } else {
+                        let mut v = vec::from_elem(nelems-1, !0u);
+                        v.push((1<<nbits % uint::bits)-1);
+                        v
+                    }
+                } else { vec::from_elem(nelems, 0u)};
             Big(BigBitv::new(s))
         };
         Bitv {rep: rep, nbits: nbits}
@@ -1330,6 +1339,20 @@ mod tests {
     }
 
     #[test]
+    fn test_bitv_set_frombitv_init() {
+        let bools = [true, false];
+        let lengths = [10, 64, 100];
+        for &b in bools.iter() {
+            for &l in lengths.iter() {
+                let bitset = BitvSet::from_bitv(Bitv::new(l, b));
+                assert_eq!(bitset.contains(&1u), b)
+                assert_eq!(bitset.contains(&(l-1u)), b)
+                assert!(!bitset.contains(&l))
+            }
+        }
+    }
+
+    #[test]
     fn test_small_difference() {
         let mut b1 = Bitv::new(3, false);
         let mut b2 = Bitv::new(3, false);