This project aims to reimplement the MCDC test vector indexing in clang LLVM, which is described here.

The problem is the following: when performing MC/DC analysis, we must keep track of evaluated test vectors¹ of a decision to compute coverage after execution.

Since we are saving stuff in a bitmap, the naive implementation is to assign a number x to each operand of the boolean expression, and build and index from the evaluation of each operand, setting the x-th bit of an integer n, and then using the result n as an index in the bitmap. While this works, it is highly inefficient, since the value of n can increase exponentially by the number of operands. Moreover, since boolean operators are short-circuiting, most values between 0 and the highest possible value of n are unreachable, leaving a large part of the bitmap completely useless.

For a given expression, this algorithm assigns 0-based contiguous values to every possible test vector, so no bitmap space is wasted. The explanation lies in the code comments.