[BUG] Incorrect PartialOrd code for two bit vectors with different sizes

[luojia65]

I am working on simple exhaustive algorithm to CNF satisfiability problem. Tried my minimum code here:

pub fn solve_cnf_plain() -> bool {
    let n = 3;
    let one = bitvec![1];
    let mut var = bitvec![0; n];
    let max = bitvec![1; n];
    while var <= max {
        println!("{:?} {:?}", &var, &max);
        var += one.clone();
    }
    true
}

I expect to print only 8 line of output assuring bits 000 to 111 is searched. However the actual output is like:

BitVec<Lsb0, usize> [000] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [001] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [010] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [011] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [100] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [101] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [110] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [111] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1000] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1001] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1010] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1011] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1100] BitVec<Lsb0, usize> [111]
BitVec<Lsb0, usize> [1101] BitVec<Lsb0, usize> [111]

There are extra lines when I add 1 to 111 (into 1000), it seems that the program misjudged 1000 <= 111 (actually should be 1000 > 111).

Is my code correct, or is there some problem in this library? Thanks!

(My persional opinion is that the problem may be found at some PartialOrd impl inside this crate)

[myrrlyn]

The behavior you describe matches the test case as written, c.f. https://github.com/myrrlyn/bitvec/blob/master/src/slice/traits.rs#L133-L177

The original behavior from core is here: https://github.com/rust-lang/rust/blob/6cad7542da2f10e2110f942de4db59716bacb3df/src/libcore/slice/mod.rs#L5591-L5609

This occurred because BitSlice uses a lexicographic sort per-bit before comparing lengths; string "aaa" sorts less than "ab" for the same reason.

---

This is a confluence of behavior I actually hadn't considered before, thank you. I provided arithmetic operators so that people could use the structures as arbitrary-sized integers, but I use lexicographic instead of integer sorting! That is a bug.

In the interim, you can get fixed-width arithmetic by using .as_mut_bitslice().

[myrrlyn]

I am going to remove the integer arithmetic capability entirely in 0.18. I do not have a plan at this time to pull it into a bitvec_num crate. Your current code can be replaced with

for n in 0u8 .. 8 {
  let pat = &n.bits::<Lsb0>()[.. 3];
  println!("{:?}", pat);
}

in order to correctly count through the integers while viewing their bit-pattern representation.

If you expect to need integer arithmetic beyond what can be done with ordinary Rust integers and bit-pattern views of them, please weigh in on #17 and I can get that ball rolling.