Llogiq on stuff

Under Cover

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 reported mutations.

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:

  1. Prepend a zero-length static array with a generated name before the outer block of any function
  2. Use that array as if it had the correct length
  3. 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 shave).

Like this series? How about joining the fun? Come help us breaking a lot of Rust code for fun and profit!