DynamicBitSetUnmanaged: .setAll() incorrectly sets all bits, or .iterator incorrectly traverses bits outside the bit_length.

[ITR13]

Zig Version

0.13.0-dev.75+5c9eb4081

Steps to Reproduce and Observed Behavior

Code

Running the following program:

const std = @import("std");
const BitSet = std.bit_set.DynamicBitSetUnmanaged;
const Allocator = std.mem.Allocator;
const print = std.debug.print;
const bitset_iterator_options = std.bit_set.IteratorOptions{};

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var bitset = try BitSet.initFull(allocator, 19);

    print("After init:", .{});
    printSet(bitset);

    bitset.unsetAll();
    print("\nAfter unsetAll:", .{});
    printSet(bitset);

    bitset.setAll();
    print("\nAfter setAll:", .{});
    printSet(bitset);

    print("\n", .{});
}

fn printSet(bitset: BitSet) void {
    var iter = bitset.iterator(bitset_iterator_options);
    while (iter.next()) |i| {
        print(" {}", .{i});
    }
}

Has the following output:

After init: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
After unsetAll:
After setAll: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

Which means that setAll is setting the bits of the set differently than how initFull sets them. Alternatively it could be an issue with the iterator going outside the range of bit_length.

Other testing done

• This happens both for small sets and big sets, as long as the amount of bits is not a multiple of 64. I've tested up to 1000000001.
• Iterating the bits in reverse makes it start out of bounds.
• Using .unsetAll and only iterating unset bits does not have the same issue.

Expected Behavior

The following output:

After init: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
After unsetAll:
After setAll: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

[travisstaloch]

Which means that setAll is setting the bits of the set differently than how initFull sets them.

Would you agree that the solution is to make setAll() and unsetAll() only set bits from 0..self.bit_length? Currently these set all masks which means 1 full mask of 64 bits being set in the code above instead of only bits 0..19.

I just wanted to see if others agree before making any changes.

[travisstaloch]

After looking at the DynamicBitSetUnmanaged code, I think that there are 2 problems. The first is that setAll() shouldn't change the padding bits. And second is that iterator() shouldn't include padding bits.

[ITR13]

After looking at the DynamicBitSetUnmanaged code, I think that there are 2 problems. The first is that setAll() shouldn't change the padding bits. And second is that iterator() shouldn't include padding bits.

Either change would fix my issue, I was leaning more towards setAll not changing the padding bits because initFull already had that behaviour. And I was unsure if changing the iterator to verify the length might impact performance.

I'm new to zig though, so I trust everyone elses judgement on this matter ^^

[travisstaloch]

I think its definitely correct to change setAll() since it says in the 'masks' field doc comments

the padding bits must be zeroed .

In my PR yesterday I changed iterator() to skip the padding bits. But now, I think that shouldn't be necessary since the padding bits should never be set. And if the user sets them, thats on them. This would make count() and iterator() consistent again whether or not any padding bits are set. So I'm going to revert the iterator() changes from my PR.