Cydhra / vers

Succinct data structures using very efficient rank and select
Apache License 2.0
62 stars 4 forks source link

Errors in `iter1()` #6

Closed pmarks closed 4 months ago

pmarks commented 5 months ago

Very cool crate! I ran into some cases where iter1() returns incorrect results - it appears to skip blocks of ~8 ONE bits. I augmented test_random_data_rank() with some tests of iter0/1 and ran into a crash. The test below will fail with thread 'bit_vec::fast_rs_vec::tests::test_random_data_rank' panicked at src/bit_vec/fast_rs_vec/iter.rs:327:19: attempt to shift left with overflow on x86_64. I get the same failure with and without target-cpu=native

Test:

#[test]
fn test_random_data_rank() {
    let mut bv = BitVec::with_capacity(LENGTH);
    let mut rng = StdRng::from_seed([
        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,
        6, 7,
    ]);
    let sample = Uniform::new(0, 2);
    static LENGTH: usize = 4 * SUPER_BLOCK_SIZE;

    for _ in 0..LENGTH {
        bv.append_bit(sample.sample(&mut rng));
    }

    let bv = RsVec::from_bit_vec(bv);

    assert_eq!(bv.len(), LENGTH);

    // new iter0/1 tests
    for bit1 in bv.iter1() {
        assert_eq!(bv.get(bit1), Some(1));
    }

    for bit0 in bv.iter0() {
        assert_eq!(bv.get(bit0), Some(0));
    }

    let mut all_bits: Vec<_> = bv.iter0().chain(bv.iter1()).collect();
    all_bits.sort();
    all_bits.dedup();
    assert_eq!(all_bits.len(), LENGTH);
}

Relevant stack:


                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/iter.rs:327:19
  21:     0x559235af78b8 - <vers_vecs::bit_vec::fast_rs_vec::iter::SelectIter<_> as core::iter::traits::iterator::Iterator>::next::h917ec949850a2aeb
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/iter.rs:358:13
  22:     0x559235adffcf - vers_vecs::bit_vec::fast_rs_vec::tests::test_random_data_rank::hbe5742e7b9163e43
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/tests.rs:36:17
  23:     0x559235ac5077 - vers_vecs::bit_vec::fast_rs_vec::tests::test_random_data_rank::{{closure}}::h661c2093803983ac
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/tests.rs:19:27
  24:     0x559235b27da6 - core::ops::function::FnOnce::call_once::h22b1d390239012f7```
Cydhra commented 4 months ago

Fixed in 685b673. Released as 1.3.2 on crates.io. Will be merged into master before next minor release.