Skip to content

with_capacity_and_blocks() can create bitsets that don't compare equal to logically identical ones #139

@hniksic

Description

@hniksic

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions