BitSet.bitand operation returns non-empty BitSetAnd even if no ids match.

[prixt]

Code:

use hibitset::*;

fn main() {
    let mut a = BitSet::new();
    let mut b = BitSet::new();
    assert!( a.is_empty() && b.is_empty(), "This shouldn't happen!");
    a.add(0);
    b.add(10);
    assert!( !a.is_empty() && !b.is_empty(), "This also shouldn't happen!");
    assert!( (a&b).is_empty(), "This definetely shouldn't happen!");
}

Output:

thread 'main' panicked at 'This definetely shouldn't happen!', src\main.rs:10:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
error: process didn't exit successfully: `target\debug\rust-test.exe` (exit code: 101)

[prixt]

Currently using hibitset version 0.6.1.

[prixt]

https://github.com/prixt/hibitset/blob/master/src/ops.rs 88c5d57f6156f999ade724f10efb8b27cc9d05b1

A band-aid fix. Basically created a separate 'is_empty' function for BitSetAnd.

#[inline]
fn is_empty(&self) -> bool {
    self.iter().count() == 0
}

There probably is a better solution, but this will fix the problem for now.

[torkleyy]

Argh, this is a severe bug in our operators! We can not simply AND / XOR layers 1 - 3; they need to be recomputed.

[torkleyy]

This essentially means we'll likely have to drop our "lazy" operators and rely exclusively on *Assign, so we can recalculate the layers.

[prixt]

https://github.com/prixt/hibitset/blob/and_xor_assign/src/ops.rs b5d3b60abedcc3625fe59e564a39cfa6c9fce907

Tried to create new BitSetAnd and BitSetXor structs. While these do pass the tests, I think these won't work in all cases, since they internally use BitSet.

[WaDelma]

Should we also do eager calculation of BitSetNot? I first looked at it again because I was thinking you could do the -(-a | -b) trick

[WaDelma]

Yeah this pretty much forces dropping lazy operators.

[prixt]

~Only bitand op and bitxor op need eager calculation.~ nvm, bitnot seems to need some adjustsments too.

[prixt]

If all operators need to create a new BitSetLike structure, and now need to be recalculated, why not just return a BitSet?

[hjfreyer]

Am I correct in thinking this means the bitsets simply return incorrect answers?? This crate has been downloaded more than 400,000 times, so if its logic is incorrect it should really get pulled!

[torkleyy]

@hjfreyer

Am I correct in thinking this means the bitsets simply return incorrect answers?? This crate has been downloaded more than 400,000 times, so if its logic is incorrect it should really get pulled!

This bug has three implications as far as I see it:

• it means is_empty can return false even though in fact the bit set is empty
• higher-up layers might have a set bit even though the corresponding bits on the lower layer are all 0
• however, layer0 always has the correct bits set meaning that this bug (which really should be a documented limitation in this latter case) only has a performance cost while iterating, i.e. the results are still correct