-
Notifications
You must be signed in to change notification settings - Fork 56
Description
Two FixedBitSet instances that represent the same logical bitset can compare as not equal (and have different hashes) when one is created via with_capacity_and_blocks(). Take this program:
use fixedbitset::FixedBitSet;
fn main() {
let mut b1 = FixedBitSet::with_capacity(10);
b1.insert_range(..);
let b2 = FixedBitSet::with_capacity_and_blocks(10, std::iter::repeat(!0));
println!("b1 count_ones: {}", b1.count_ones(..)); // 10
println!("b2 count_ones: {}", b2.count_ones(..)); // 10
println!("b1 len: {}", b1.len()); // 10
println!("b2 len: {}", b2.len()); // 10
println!("b1 == b2: {}", b1 == b2); // false (!)
}I'd expect both bitsets to compare equal, as both have the same bits (10 bits set to 1) and length.
Actual behavior is that they compare as not equal because with_capacity_and_blocks() stores the provided block values as-is, including bits beyond the capacity.
Since PartialEq and Hash operate on the raw storage, these bitsets are considered different.
This makes it difficult to use with_capacity_and_blocks() for efficient initialization (e.g., creating an all-ones bitset, as discussed in #101) without risking subtle bugs when the bitset is later compared or used in a hash-based collection.
#138 keeps existing behavior of with_capacity_and_blocks(), but adds a sentence documenting current behavior, and does the masking in the new ones_with_capacity() function. But perhaps the current behavior of with_capacity_and_blocks() is a bug that should be fixed, or we should add a new constructor that truncates correctly?
To fix with_capacity_and_blocks() to do the correct masking, just revert the last commit in #138.