Any mutation testing tool worth its salt uses coverage to restrict the number of tests to run. mutagen is no exception, of course, so once we had a test runner, we wanted to extend it with coverage-based testing.
Now when this was first proposed, I thought it was very complex, with a need to integrate coverage reporting tools etc. But when I tought about it some more, it dawned on me that we didn’t need full code coverage – we only needed to know which mutations were covered by a test. This is much easier, since we control the code the mutations run.
The solution per mutation is a method to report coverage. At the moment, we
just write it into a file, to be read later by the test runner. To do this
once, we currently have a global
Vec<AtomicBool> that we use to flag already
However, I’m not particularly happy about that
Vec. First, it’s an allocation
and I don’t want mutagen code to allocate if I can help it (perhaps we someday
want to mutate
no_std code?). Second, it requires another environment
variable with the number of mutations that has to be threaded from the test
runner to the mutated code, which to me looks like brittle design.
I should note that this version came about after a trial with my preferred
solution (an array of
AtomicBools per method) failed, because the array was
used before the statement creating it was added to the code.
So let’s try a slightly modified technique:
- Prepend a zero-length static array with a generated name before the outer block of any function
- Use that array as if it had the correct length
- Once the method is mutated, go back to our prepended statement and change the array size to the correct length.
Now we don’t need a global vector and each method has its own set of booleans, reducing the risk of mis-adressed mutations. There is but one niggle: Nested functions. If I use one global counter, I’ll get a “hole” in the mutation flag array. The solution here is to decouple the mutation flag count from the mutation count, which also reduces multi-mutations to one flag, thus saving even more memory.
I should note that in doing so, I refactored the
MutatorPlugin to ease
borrowing pains following the compose structs for better borrowing pattern.
For the final resizing operation, I made use of
mem::replace to avoid needless clones.
We can even go one step further and use an atomic bitset, reducing memory
consumption up to eight-fold. A simple benchmark comparing an uncontended
AtomicBool::swap(..) (the fastest method to set a flag while retrieving its
previous value) and
AtomicUsize::fetch_or(1 << _) & 1 << _ != 0 (the obvious
way to set the bit while checking the previous value) shows identical
performance on all machines I tested with (now this is not a complete bitset
implementation, but enough for our needs – perhaps I’ll start a crate to
provide a more full-featured atomic bitset, but that’s yet another yak to
Like this series? How about joining the fun? Come help us breaking a lot of Rust code for fun and profit!