Mixing roaring bitmaps with different copy_on_write flag values is unsafe

[Ezibenroc]

See the following example. Four bitmaps are created. Copy on write is enabled for all of them, except the second. Then, the union of the bitmaps is computed in the order (((bm1 | bm2) | bm3) bm4) (the order seems to be important for the bug).

When doing the last union, a supposedly unreachable false assertion is triggered. The type of one container (after unwrapping) is not defined.

void test_multiple_union() {
    roaring_bitmap_t *bm1 = roaring_bitmap_from_range(172033, 172034, 1);
    bm1->copy_on_write = 1;
    roaring_bitmap_t *bm2 = roaring_bitmap_from_range(247243, 447339, 1);
    bm2->copy_on_write = 0;
    roaring_bitmap_t *bm3 = roaring_bitmap_from_range(23705, 95255, 1);
    bm3->copy_on_write = 1;
    roaring_bitmap_t *bm4 = roaring_bitmap_from_range(163739, 393874, 1);
    bm4->copy_on_write = 1;

    roaring_bitmap_t *tmp1 = roaring_bitmap_or(bm1, bm2);
    roaring_bitmap_t *tmp2 = roaring_bitmap_or(tmp1, bm3);
    roaring_bitmap_t *result = roaring_bitmap_or(tmp2, bm4); // ← fails here

    roaring_bitmap_free(bm1);
    roaring_bitmap_free(bm2);
    roaring_bitmap_free(bm3);
    roaring_bitmap_free(bm4);
    roaring_bitmap_free(tmp1);
    roaring_bitmap_free(tmp2);
    roaring_bitmap_free(result);
}

[lemire]

Ok. I have added a comment in the last commit:

https://github.com/RoaringBitmap/CRoaring/commit/c70f20bda14f07d87f13df2876890e864b27a89b

The problem is that you are mixing bitmaps with different copy_on_write flags. This multiplies the scenarios we want to test. It creates lots of complexity.

What is your use case to mix bitmaps having different copy_on_write flags?

For the time being, this should be considered unsafe.

[Ezibenroc]

I added support for copy on write in Pyroaring (not pushed yet). I was writing some tests and came across this bug.

I do not have any use case in mind, so I agree that we could forbid this kind of scenario. Maybe it should be enforced, e.g. by returning NULL if the two bitmaps have a different value in the copy_on_write field?

[lemire]

Right so I left the issue opened because I think it is a problem that needs to be solved.

Note that your proposal does not fully solve the problem because one could activate the flag then turn it off... I am not sure there is a perfectly safe way.