[Question] Question about `SparseBitVector`

[enochii]

Hi, dear authors, I have a question about the SparseBitVector.

If I want to add a bit-vector source to another bit-vector target, and return the diff bit-vector which is actually added to target. That is to say, we need to

• add source to target, and
• return the diff vector.

I go through the SparseBitVector implementation, it seems the (pseudo) code should be something like:

operator - may simplies the code.

SparseBitVector diff;
// old bits of the diff will be cleared?, and the result of "source & ~target" will be stored into diff
diff.intersectWithComplement(source, target); // compute diff
target |= diff; // add `diff` to `target`
return diff;

To the best of my knowledge, if the above code is desired, the target bit-vector will be traversed twice. I wondering why not provide an API to do this internally, which is more efficient and more straightforward to the user. Moreover, this should be a common case in program analysis and not limited to the SparseBitVector. Are there other consideration?

Thanks for your time!

[yuleisui]

@mbarbar could you help take a look at this question?

[mbarbar]

Originally, we used LLVM's (sparse) bit-vector as a black box. Whatever APIs it provided, we used. Then we created a more general bit-vector API, basically just what we actually used from LLVM's (the sparse bit-vector implementation in the source tree is actually LLVM's chopped up and modified; the other bit vectors are ours). I guess we never needed a union operation that also kept track of what changed.

If @yuleisui would be okay adding it, you can open a PR implementing this, but it must be separate to the standard union (e.g. unionAndGetDiff or something) as it would incur a performance hit. Implementation would basically be a copy of the current union + a diff operation on each iterated element.