Programming for coverage part 6

Drawing insights

We can draw interesting insights from measuring code coverage. This is a binary search that I borrowed from the internet and used in my talk on prime path coverage in GCC at TechTown 2024, very slightly revised. It returns the index of the needle (x) in a sorted array, or not-found (-1) if it could not be found.

int bs(const int A[], int N, int x) {
    int min = 0;
    int max = N - 1;
    int mid = min + ((max - min) / 2);
    while (A[mid] != x && min <= max) {
        mid = min + ((max - min) / 2);
        if (x > A[mid])
            min = mid + 1;
        else
            max = mid - 1;
    }

    return A[mid] == x ? mid : -1;
}

We add tests for the cases we can think of along with the expected results. All good so far, no real problems, and the tests looks solid.

void check() {
    static const int haystack[] = {
        1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
        233, 377, 610, 987, 1597, 2584, 4181,
    };

    const int len = sizeof (haystack) / sizeof (*haystack);

    // smaller than smallest
    assert(bs(haystack, len, 0) == -1);
    // hit left
    assert(bs(haystack, len, 2) == 1);
    // miss left
    assert(bs(haystack, len, 4) == -1);

    // larger than largest
    assert(bs(haystack, len, 5000) == -1);
    // hit right
    assert(bs(haystack, len, 1597) == 15);
    // miss right
    assert(bs(haystack, len, 1024) == -1);
}

Measuring coverage

We measure the coverage and are surprised to find that we have 100% block- and edge coverage, but just ~63% prime path coverage, with 15/24 paths covered. If we search for all values between 0 and 5000, which covers the whole haystack with margins on either side we end up covering 16/24 paths, just one more than our hand-written set. We need to understand why coverage is still so poor. This is the CFG from zcov:

Path 2, 3

These are the paths where min > max on the first iteration, which can only happen when N <= 0. N is the array length, so a negative value does not make sense. These are both inputs we simply didn’t test for, but that we surely want to handle correctly by always returning not-found, and making sure we’re not accessing memory out of bounds.

Path 5, 23

We found the value we’re looking for, but we’re testing if we should return not-found (-1). This is a contradiction; since we broke the loop on A[mid] == x, we can never see A[mid] != x in the ternary.

Path 7, 10

These are also contradictions. In these paths we break the loop on min > max, which is checked after A[mid] != x => true. Since A[mid] == x and A[mid] != x can’t be true at the same time, we cannot cover these paths.

Path 19, 20

These paths are hard to distinguish from 7, 10; they start in block 7, which is the comparison min <= max. In these paths, x > A[mid] is true, but the loop immediately breaks on A[mid] != x => false, which implies A[mid] == x => true. This is a contradiction; x > A[mid] and A[mid] == x cannot be true simultaneously, and these paths cannot be covered.

Rewriting the algorithm

The key insight from measuring the coverage is that we have a lot of redundant checks. Poor coverage aside, this is a common source of bugs. When we read code we often simulate the execution, draw mental data flow diagrams and compose long chains of reasoning. Even when the comparisons are reused they form yet another branching point, just like the control flow graph. We can rewrite the binary search with the new insights in mind and eliminate the redundant comparisons.

We move the A[mid] == x check into the loop. mid is no longer carried between iterations, and the value can be moved into the loop, too. If we find the value we’re looking for we immediately return as there is nothing more to do, which eliminates the ternary in the return statement.

int bs(const int A[], int N, int x) {
    int min = 0;
    int max = N - 1;
    while (min <= max) {
        int mid = min + ((max - min) / 2);
        if (x == A[mid])
            return mid;
        else if (x > A[mid])
            min = mid + 1;
        else
            max = mid - 1;
    }

    return -1;
}

We test it using the same checks and measure the coverage. This version has 16/18 (89%) paths covered, and we can quicky spot the missing test cases with zcov. These are the missing cases, paths 0 and 3.

These are the cases where the needle is in the exact middle (path 0) and where the loop is never entered (the empty list). Both of these are oversights that should clearly be a part of the functional testing suite. We add these checks to complete our test suite and measure to verify that 18/18 paths are covered.

    // missing tests:
    // empty list
    assert(bs(haystack, 0, 1) == -1);
    // mid hit
    assert(bs(haystack, len, 55) == 8);

The new function violates MISRA (only a single return per function), but I find that perfectly acceptable and better than the alternatives.