[PATCH] Add tests for Bitmapset

On Fri, Aug 15, 2025 at 11:39:23AM -0400, Greg Burd wrote:

I noticed that there are no tests for Bitmapset in src/test/modules as
is the case for other similar things like radixtree, rbtree, etc. so I
created one. I realize that Bitmapset is already "tested" by all the
other code that uses it, but I was able to find one minor oversight[1]
in that code with these new tests.

I hope I've covered all the bases, but if you have thoughts on other
ways to test Bitmapset I'll happily add them to the patch.

Adding some tests here seems like a good idea. I might look into some ways
to trim it down a bit, but that'd just be minor editorialization. One
other thing to consider is adding randomness to the tests (see
test_radixtree and test_binaryheap for examples).

--
nathan

On Sep 4, 2025, at 10:00 PM, Nathan Bossart <nathandbossart@gmail.com> wrote:

On Fri, Aug 15, 2025 at 11:39:23AM -0400, Greg Burd wrote:

I noticed that there are no tests for Bitmapset in src/test/modules as
is the case for other similar things like radixtree, rbtree, etc. so I
created one. I realize that Bitmapset is already "tested" by all the
other code that uses it, but I was able to find one minor oversight[1]
in that code with these new tests.

I hope I've covered all the bases, but if you have thoughts on other
ways to test Bitmapset I'll happily add them to the patch.

Adding some tests here seems like a good idea. I might look into some ways
to trim it down a bit, but that'd just be minor editorialization. One
other thing to consider is adding randomness to the tests (see
test_radixtree and test_binaryheap for examples).

Nathan,

Thank you for your interest in this patch, I appreciate that your time is
limited and highly valuable to the community. This patch isn't "earth
shattering", but I think it's valuable to have test coverage even in cases
where the code being tested is already very well exercised.

I looked at both radix tree and binary heap and how they use random sets when
testing. Binary heap uses it to create different random sets of numbers to
use across multiple tests while radix tree has a single function that focuses
on randomized data. I decided not to add randomization into the tests of
Bitmapset simply because I like avoiding non-deterministic behavior. But in
tests I guess that can be helpful finding future unknown corner cases. I'm
on the fence as to the value, your call. :)

Let me know if you'd like that or not.

--
Nathan

best, and thanks again for the attention,

-greg

On Fri, Sep 05, 2025 at 10:48:21AM -0400, Burd, Greg wrote:

I looked at both radix tree and binary heap and how they use random sets when
testing. Binary heap uses it to create different random sets of numbers to
use across multiple tests while radix tree has a single function that focuses
on randomized data. I decided not to add randomization into the tests of
Bitmapset simply because I like avoiding non-deterministic behavior. But in
tests I guess that can be helpful finding future unknown corner cases. I'm
on the fence as to the value, your call. :)

I'm not too concerned about it. We've lived without a dedicated test suite
for Bitmapset for a very long time, so any amount of test coverage is an
improvement. Like you said, adding some randomization might be helpful for
finding weird bugs we wouldn't have thought to test. And, given the many,
many machines that run the tests, IMHO it'd only help build even more
confidence in the code. If my suggestion inspires you to update the patch,
great, but I'm fine with proceeding with what you already wrote, too.

--
nathan

On Sep 5, 2025, at 2:43 PM, Nathan Bossart <nathandbossart@gmail.com> wrote:

On Fri, Sep 05, 2025 at 10:48:21AM -0400, Burd, Greg wrote:

I looked at both radix tree and binary heap and how they use random sets when
testing. Binary heap uses it to create different random sets of numbers to
use across multiple tests while radix tree has a single function that focuses
on randomized data. I decided not to add randomization into the tests of
Bitmapset simply because I like avoiding non-deterministic behavior. But in
tests I guess that can be helpful finding future unknown corner cases. I'm
on the fence as to the value, your call. :)

I'm not too concerned about it. We've lived without a dedicated test suite
for Bitmapset for a very long time, so any amount of test coverage is an
improvement. Like you said, adding some randomization might be helpful for
finding weird bugs we wouldn't have thought to test. And, given the many,
many machines that run the tests, IMHO it'd only help build even more
confidence in the code. If my suggestion inspires you to update the patch,
great, but I'm fine with proceeding with what you already wrote, too.

Nathan, thanks for considering the patch. Honestly, I'm fine with it as is.
We can revisit later if needed. This does what I'd intended, test and document
in code the API and implementation making future changes to that more
transparent.

Thanks!

-greg

--

On Mon, Sep 8, 2025 at 11:21 AM Burd, Greg <greg@burd.me> wrote:

On Sep 5, 2025, at 2:43 PM, Nathan Bossart <nathandbossart@gmail.com> wrote:

On Fri, Sep 05, 2025 at 10:48:21AM -0400, Burd, Greg wrote:

I looked at both radix tree and binary heap and how they use random sets when
testing. Binary heap uses it to create different random sets of numbers to
use across multiple tests while radix tree has a single function that focuses
on randomized data. I decided not to add randomization into the tests of
Bitmapset simply because I like avoiding non-deterministic behavior. But in
tests I guess that can be helpful finding future unknown corner cases. I'm
on the fence as to the value, your call. :)

I'm not too concerned about it. We've lived without a dedicated test suite
for Bitmapset for a very long time, so any amount of test coverage is an
improvement. Like you said, adding some randomization might be helpful for
finding weird bugs we wouldn't have thought to test. And, given the many,
many machines that run the tests, IMHO it'd only help build even more
confidence in the code. If my suggestion inspires you to update the patch,
great, but I'm fine with proceeding with what you already wrote, too.

Nathan, thanks for considering the patch. Honestly, I'm fine with it as is.
We can revisit later if needed. This does what I'd intended, test and document
in code the API and implementation making future changes to that more
transparent.

I appreciate your work on this. While I agree that adding more tests
to bitmapset.c is a good idea, I'm concerned about the minimal
improvement in test coverage despite the addition of new test cases
(only three lines of code are newly covered). Apart from adding some
randomness to the tests we've discussed, given that we're implementing
a dedicated test module for bitmapset.c, I would expect to see a more
increase in test coverage.

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com

On Thu, Sep 11, 2025, at 2:48 AM, Masahiko Sawada wrote:

On Mon, Sep 8, 2025 at 11:21 AM Burd, Greg <greg@burd.me> wrote:

On Sep 5, 2025, at 2:43 PM, Nathan Bossart <nathandbossart@gmail.com> wrote:

On Fri, Sep 05, 2025 at 10:48:21AM -0400, Burd, Greg wrote:

I looked at both radix tree and binary heap and how they use random sets when
testing. Binary heap uses it to create different random sets of numbers to
use across multiple tests while radix tree has a single function that focuses
on randomized data. I decided not to add randomization into the tests of
Bitmapset simply because I like avoiding non-deterministic behavior. But in
tests I guess that can be helpful finding future unknown corner cases. I'm
on the fence as to the value, your call. :)

I'm not too concerned about it. We've lived without a dedicated test suite
for Bitmapset for a very long time, so any amount of test coverage is an
improvement. Like you said, adding some randomization might be helpful for
finding weird bugs we wouldn't have thought to test. And, given the many,
many machines that run the tests, IMHO it'd only help build even more
confidence in the code. If my suggestion inspires you to update the patch,
great, but I'm fine with proceeding with what you already wrote, too.

Nathan, thanks for considering the patch. Honestly, I'm fine with it as is.
We can revisit later if needed. This does what I'd intended, test and document
in code the API and implementation making future changes to that more
transparent.

I appreciate your work on this. While I agree that adding more tests
to bitmapset.c is a good idea, I'm concerned about the minimal
improvement in test coverage despite the addition of new test cases
(only three lines of code are newly covered). Apart from adding some
randomness to the tests we've discussed, given that we're implementing
a dedicated test module for bitmapset.c, I would expect to see a more
increase in test coverage.

Good point and thanks for taking the time to reply. The only thing it identified
was a small issue fixed in b463288 so I'd not expect coverage to increase much.

I'll take a stab at adding some randomness to the tests and check the delta in
coverage. Thanks for the nudge. :)

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com

Just for reference I started this not to increase coverage, which is a good
goal just not the one I had. I was reviewing the API and considering some
changes based on other work I've done. Now that I see how deeply baked in
this code is I think that's unlikely. Maybe something else distinct for
bitmaps over 64-bit space at some point will be useful. I wrote this code
just to capture the API in test form.

best,

-greg

On Thu, Sep 11, 2025 at 06:56:07AM -0400, Greg Burd wrote:

Just for reference I started this not to increase coverage, which is a good
goal just not the one I had. I was reviewing the API and considering some
changes based on other work I've done. Now that I see how deeply baked in
this code is I think that's unlikely. Maybe something else distinct for
bitmaps over 64-bit space at some point will be useful. I wrote this code
just to capture the API in test form.

How much does this measure in terms of numbers produced by
coverage-html (see [1]https://www.postgresql.org/docs/devel/regress-coverage.html -- Michael)? The paths taken don't always matter as it
can also be important to check combinations of code paths that are
taken by other tests when checking after edge cases, but that would
give an idea of gain vs extra runtime. Not objecting to your patch,
just being curious as I am not seeing any numbers posted on this
thread.

[1]: https://www.postgresql.org/docs/devel/regress-coverage.html -- Michael
--
Michael

On Sep 11, 2025, at 9:36 PM, Michael Paquier <michael@paquier.xyz> wrote:

On Thu, Sep 11, 2025 at 06:56:07AM -0400, Greg Burd wrote:

Just for reference I started this not to increase coverage, which is a good
goal just not the one I had. I was reviewing the API and considering some
changes based on other work I've done. Now that I see how deeply baked in
this code is I think that's unlikely. Maybe something else distinct for
bitmaps over 64-bit space at some point will be useful. I wrote this code
just to capture the API in test form.

How much does this measure in terms of numbers produced by
coverage-html (see [1])? The paths taken don't always matter as it
can also be important to check combinations of code paths that are
taken by other tests when checking after edge cases, but that would
give an idea of gain vs extra runtime. Not objecting to your patch,
just being curious as I am not seeing any numbers posted on this
thread.

[1]: https://www.postgresql.org/docs/devel/regress-coverage.html
--
Michael

Sawada-san, Michael,

Thank you both for the push to measure. Before the patch as it stands now the
coverage for src/backend/nodes/bitmapset.c is 63.5% and after it is 66.5%. Not
an amazing difference, but something. I guess I expected this to be higher given
the degree to which this datatype is used.

I'll review the gaps in coverage and update the tests. I'll look for a way to add
meaningful randomization.

-greg

On Sep 13 2025, at 10:23 am, Greg Burd <greg@burd.me> wrote:

Sawada-san, Michael,

Thank you both for the push to measure.  Before the patch as it stands
now the
coverage for src/backend/nodes/bitmapset.c is 63.5% and after it is
66.5%.  Not
an amazing difference, but something.  I guess I expected this to be
higher given
the degree to which this datatype is used.

I'll review the gaps in coverage and update the tests.  I'll look for
a way to add meaningful randomization.

-greg

Hello hackers,

Here's the progress I've made in coverage for testing Bitmapset.

coverage: HEAD v1 v2
lines......: 87.1 87.7 91.3
functions..: 100 100 100
branches...: 63.5 66.5 77.9

I've also added a function that performs a variety of operations using
random data.

For reference radixtree has:

coverage: HEAD
lines......: 98.3
functions..: 97.2
branches...: 89.4

best,

-greg

On Mon, Sep 15, 2025 at 2:00 PM Greg Burd <greg@burd.me> wrote:

For reference radixtree has:

coverage: HEAD
lines......: 98.3
functions..: 97.2
branches...: 89.4

+ /* Test negative member in bms_make_singleton */
+ error_caught = false;
+ PG_TRY();
+ {
+ bms_make_singleton(-1);
+ }
+ PG_CATCH();
+ {
+ error_caught = true;
+ FlushErrorState();
+ }
+ PG_END_TRY();
+ EXPECT_TRUE(error_caught);

This is an anti-pattern for PostgreSQL code. You can't just flush an
error without aborting a transaction or subtransaction to recover.
Even if it could be shown that this were harmless here, I think it's a
terrible idea to have code like this in the tree, as it encourages
people to do exactly the wrong thing.

But backing up a step, this also doesn't really seem like the right
way to test the error conditions. It deliberately throws away the
error message. All this verifies is that you caught an error. If you
let the error escape to the client you could have the expected output
test that you got the expected message.

I think it would be a better idea to structure this as a set of
SQL-callable functions and move a bunch of the logic into SQL.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Sep 15 2025, at 2:54 pm, Robert Haas <robertmhaas@gmail.com> wrote:

On Mon, Sep 15, 2025 at 2:00 PM Greg Burd <greg@burd.me> wrote:

For reference radixtree has:

coverage: HEAD
lines......: 98.3
functions..: 97.2
branches...: 89.4

+ /* Test negative member in bms_make_singleton */
+ error_caught = false;
+ PG_TRY();
+ {
+ bms_make_singleton(-1);
+ }
+ PG_CATCH();
+ {
+ error_caught = true;
+ FlushErrorState();
+ }
+ PG_END_TRY();
+ EXPECT_TRUE(error_caught);

This is an anti-pattern for PostgreSQL code. You can't just flush an
error without aborting a transaction or subtransaction to recover.
Even if it could be shown that this were harmless here, I think it's a
terrible idea to have code like this in the tree, as it encourages
people to do exactly the wrong thing.

Fair enough, I'll rework it.

But backing up a step, this also doesn't really seem like the right
way to test the error conditions. It deliberately throws away the
error message. All this verifies is that you caught an error. If you
let the error escape to the client you could have the expected output
test that you got the expected message.

I think it would be a better idea to structure this as a set of
SQL-callable functions and move a bunch of the logic into SQL.

I'll give that approach a try, thanks for the suggestion.

-greg

On Sep 15 2025, at 3:03 pm, Greg Burd <greg@burd.me> wrote:

On Sep 15 2025, at 2:54 pm, Robert Haas <robertmhaas@gmail.com> wrote:

On Mon, Sep 15, 2025 at 2:00 PM Greg Burd <greg@burd.me> wrote:

For reference radixtree has:

coverage: HEAD
lines......: 98.3
functions..: 97.2
branches...: 89.4

+ /* Test negative member in bms_make_singleton */
+ error_caught = false;
+ PG_TRY();
+ {
+ bms_make_singleton(-1);
+ }
+ PG_CATCH();
+ {
+ error_caught = true;
+ FlushErrorState();
+ }
+ PG_END_TRY();
+ EXPECT_TRUE(error_caught);

This is an anti-pattern for PostgreSQL code. You can't just flush an
error without aborting a transaction or subtransaction to recover.
Even if it could be shown that this were harmless here, I think it's a
terrible idea to have code like this in the tree, as it encourages
people to do exactly the wrong thing.

Fair enough, I'll rework it.

But backing up a step, this also doesn't really seem like the right
way to test the error conditions. It deliberately throws away the
error message. All this verifies is that you caught an error. If you
let the error escape to the client you could have the expected output
test that you got the expected message.

I think it would be a better idea to structure this as a set of
SQL-callable functions and move a bunch of the logic into SQL.

I'll give that approach a try, thanks for the suggestion.

-greg

Robert,

Reworked as indicated, thanks for pointing out the anti-pattern I'd
missed.

best.

-greg

On Mon, Sep 15, 2025 at 03:56:30PM -0400, Greg Burd wrote:

Reworked as indicated, thanks for pointing out the anti-pattern I'd
missed.

Hmm. Should we try to get something closer in shape to what we do for
the SLRU tests, with one SQL function mapping to each C function we
are testing? This counts for bms_is_member(), bms_num_members(), add,
del, mul, hash and make_singleton.

+test_bms_del_member_negative(PG_FUNCTION_ARGS)
+{
+	/* This should throw an error for negative member */
+	bms_del_member(NULL, -20);
+	PG_RETURN_VOID();

For example, this case could use a Bitmapset and a number (or an array
of numbers for repeated operations), with NULL being one option for
the input Bitmapset. This makes the tests a bit more representative
of what they do at SQL level, hence there would be no need to
double-check a given line where a failure happens. The Bitmapset
could then be passed around as bytea blobs using \gset, for example.
This should not be a problem as long as they are palloc'd in the
TopMemoryContext. The SQL output for true/false/NULL/non-NULL
generated as output of the test could then be used instead of the
EXPECT_*() macros reported then in the elogs.

Perhaps my view of things is too cute and artistic, but when these
test suites grow over time and differ across branches, having to dig
into a specific line of a specific branch to get what a problem is
about is more error-prone. Particularly annoying when calling one
single function that does a lot of various actions, like the proposed
test_bitmapset().

Side note: `git diff --check` is reporting a bunch of indents with
spaces around the EXPECT macros.
--
Michael

On Tue, Sep 16, 2025 at 2:04 AM Michael Paquier <michael@paquier.xyz> wrote:

one SQL function mapping to each C function we are testing?

Yes, I think we should do this, if possible.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Sep 16 2025, at 8:02 am, Robert Haas <robertmhaas@gmail.com> wrote:

On Tue, Sep 16, 2025 at 2:04 AM Michael Paquier <michael@paquier.xyz> wrote:

one SQL function mapping to each C function we are testing?

Yes, I think we should do this, if possible.

Michael, Robert,

Thanks for your time reviewing the proposed code and for providing
feedback. This patch started life as simply copy of the test_radixtree
module which uses a single test function triggered in SQL, hence my
approach. I guess I should have copied the test_slru module instead! :)

I see the value in the idea of splitting it up into separate functions
and I'll give that a try.

Michael, apologies for the white space issues. I'll clean that up, and
thank you for the `git diff --check` tip, I'll add that to my toolbox/routine.

--
Robert Haas
EDB: http://www.enterprisedb.com

best.

-greg

I've re-written the set of tests as suggested (I hope!). I've not
re-run the coverage report (yet) to ensure we're at least as well
covered as v3, but attached is v4 for your inspection (amusement?).
I've tried to author the SQL tests such that failures clearly indicate
what's at gone wrong.

This exercise turned into a lot more LOC than I'd expected, I hope it
provides some value to the community for testing this important data
structure and helps to codify the API clearly.

best.

-greg

On Tue, Sep 16, 2025 at 12:04 PM Greg Burd <greg@burd.me> wrote:

I've re-written the set of tests as suggested (I hope!). I've not
re-run the coverage report (yet) to ensure we're at least as well
covered as v3, but attached is v4 for your inspection (amusement?).
I've tried to author the SQL tests such that failures clearly indicate
what's at gone wrong.

This exercise turned into a lot more LOC than I'd expected, I hope it
provides some value to the community for testing this important data
structure and helps to codify the API clearly.

Thank you for updating the patch. It seems cfbot caught a regression
test error[1]https://cirrus-ci.com/task/5290864655728640 in a 32-bit build.

Regards,

[1]: https://cirrus-ci.com/task/5290864655728640

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com

On Tue, Sep 16, 2025 at 03:00:40PM -0700, Masahiko Sawada wrote:

Thank you for updating the patch. It seems cfbot caught a regression
test error[1] in a 32-bit build.

- bitmap_hash [1,3,5] |   49870778
+ bitmap_hash [1,3,5] | 1509752520

This one is able the hash value computation being not portable across
architectures. I would just change these to be non-NULL, I guess.
--
Michael

On Tue, Sep 16, 2025 at 03:04:39PM -0400, Greg Burd wrote:

I've re-written the set of tests as suggested (I hope!). I've not
re-run the coverage report (yet) to ensure we're at least as well
covered as v3, but attached is v4 for your inspection (amusement?).
I've tried to author the SQL tests such that failures clearly indicate
what's at gone wrong.

Thanks for the update, that's easier to follow, even if it's more
code overall. It looks like all the 29 APIs are present, plus the
extras for the array mapping routines required for the tests with the
list APIs.

+static void
+elog_bitmapset(int elevel, const char *label, const Bitmapset *bms)

This routine, that's able to translate a bytea into a readable form,
is also something that I would have added as an extra function, then
used it in some of the tests where I would care about the bitmap in
output generated after a given operation, removing the DEBUG parts
that I guess have also a risk of rotting over time. That would make
the tests for simple operations that generate a bms as a result in
easier to read, because we would call less SQL calls. For example,
take the "add_member idempotent" case, that calls twice
test_bms_make_singleton() to compare the output byteas, we could just
do a test_bms_add_member(test_bms_make_singleton(10), 10) and show the
output?

We could perhaps use the CTE style for the basic calls, to reduce the
test_bms_make_singleton() calls. What you are doing feels OK as well,
just a thought in passing.

FWIW, I tend to write the regression test queries so as these are
limited to 72-80 characters per line, to fit even in a small
terminals. That's just an old-school take, even if it means more
lines in the SQL input file..

Perhaps it would be worth documenting what's the value of
test_random_operations? It is a mean of testing add, del and
is_member with a modulo 1000 of the member number. With the other
functions that offer deterministic tests, I am not sure what's the
extra value gained in it.

+		bms1_data = PG_GETARG_BYTEA_PP(0);
+		if (VARSIZE_ANY_EXHDR(bms1_data) > 0)
+		{
+			bms1 = (Bitmapset *) palloc(VARSIZE_ANY_EXHDR(bms1_data));
+			memcpy(bms1, VARDATA_ANY(bms1_data), VARSIZE_ANY_EXHDR(bms1_data));
+		}

This pattern is repeated 9 times, if my fingers got it right. Perhaps
hide it in a macro, or invent an extra static inline routine that does
the translation?

+DO $$
+BEGIN
+    BEGIN
+	PERFORM test_bms_singleton_member(test_bms_from_array(ARRAY[1,2]));
+	RAISE NOTICE 'ERROR: singleton_member([1,2]) should have failed!';

Do we need all these DO blocks to catch failures? These cases bump on
elog(ERROR) in the internals of bitmapset.c, which are not something
the end-users would expect, but in a test module that's fine to
trigger. The function call would just fail, which is fine.

The queries with CTEs and UNION ALL are elegant, nice.

This exercise turned into a lot more LOC than I'd expected, I hope it
provides some value to the community for testing this important data
structure and helps to codify the API clearly.

It does, at least that's my opinion. So thanks for caring about this
level of testing.
--
Michael