BitvSet intersect_with has incorrect behavior when called with an empty set

[kaseyc]

The intersection of a BitvSet with an empty (returned from BitvSet::new()) set is incorrect, as it will return the original set. However, if the arguments are reversed (an empty BitvSet calls intersect_with with some set as a parameter), the correct result is returned.

Additionally, if the set returned by new is modified (e.g. add and remove a value), the correct result will be returned.

Examples:
http://is.gd/Aksaz6
http://is.gd/6zTo9R

[Gankra]

Alright, so the bug is that intersect_with delegates to an internal method other_op, which iterates over other's underlying uints to set the bits of self. So if self occupies more uints than other, it doesn't actually touch those extra bits.

other_op has no documentation, so I'm not sure if intersect_with is using it wrong, or if other_op itself is wrong. Investigating further usage now.

[kaseyc]

That makes sense. I think other_op is wrong, or to be more precise it is flawed in a way that only intersect exposes (for union and difference, leaving the higher bits unchanged is technically correct). It looks like some people went through and cleaned up bitv.rs in July, so I think the breakage happened then, as the function worked properly before.

[Gankra]

I guess one underlying question is if a BitVSet should be assumed to be all 1's or all 0's or undefined out of its known range. My intuition says all 0's, however the current implementation of BitV seems to be "undefined". For instance:

let mut a = BitvSet::from_bitv(bitv::from_bytes([0b00000000]));
let b = BitvSet::new();
println!("{}", a == b);

prints false.

[kaseyc]

I have a feeling that that is due to the mbits of the two being different, as BitvSet just derives Eq from Bitv:

https://github.com/rust-lang/rust/blob/master/src/libcollections/bitv.rs#L866

[Gankra]

I suppose this could be interpreted as two BitVSets with differing (implementation defined!) sizes representing subsets of different universes, and are therefore unequal, but that's... stupid?

CC @aturon: Agree that BitVSet should be changed to behave as if it was a set over all integers, and therefore internally should behave like an infinite stream of 0's outside of its known bounds?

[kaseyc]

I agree with @gankro . A BitvSet is a set implemented using Bitv's, though they do not represent the same things, and it makes more sense for a BitvSet to act as if it is all 0's outside of the bounds.

[Gankra]

Wait yeah I'm thinking of BitVSet too much in terms of BitV's. Of course it should be a set over all integers!

Although now I'm wondering if BitV's should behave as if they were 0's forever out of sight, instead of fail horribly on OOB accesses.

Edit: Probably not. Probably.

[Gankra]

CC @apoelstra

[apoelstra]

Hey all,

other_op is carried over from the old implementation, so I'm surprised that it's causing new problems now. My recommendation is to drop it entirely, it did cause me a fair bit of pain inferring its behaviour, which apparently I did wrong :).

The correct behaviour is definitely that BitvSet should assume all zeros outside of the range of its underlying Bitv. This was the behaviour I intended when I did the cleanup.

[kaseyc]

@gankro You rock!