Programming for coverage part 3
In this post we will work with the basic structure of a switch in a loop, and look at how slightly different decisions and designs affect the complexity and the testing requirements. This construct shows up in many programs, such as state machines, file format parsing parsing, command line argument processing, and event loops. It a consideration became sensitive to when I started measuring prime path coverage, and since I have used it both to significantly simplify my programs and squash some bugs.
This snippet shows the general structure, a loop with a switch body. It has two main sources of complexity; the number of cases (in this case, events), and the code handling each case. In this post we will focus on the number of cases.
while (true) {
switch (next_event()) {
case event_a:
// process a
break;
case event_b:
// process b
break;
// more events
...
case event_quit:
return;
}
}The switch and the if
Here is an example we can compile. These two functions are functionally the same, but one is implemented with the the switch, and the other conditionals. In both functions, each case is handled with a single function call, which is about as simple as it can be. This allows us to focus on the control flow implications of the switch-loop structure.
int next();
void dispatch_switch() {
int e;
while (e = next()) {
switch (e) {
case 1:
puts("1");
break;
case 2:
puts("2");
break;
default:
puts("unknown");
break;
}
}
}
void dispatch_ifs() {
int e;
while (e = next()) {
if (e == 1)
puts("1");
else if (e == 2)
puts("2");
else
puts("unknown");
}
}
As seen in the zcov screenshots, these functions have roughly the same number of prime paths (28 and 27), which makes sense since they’re mostly equivalent. In fact, given a few more cases and optimizations enabled, the ifs would likely be transformed to a jump table. The switch provides a useful piece of information to the reader; all comparisons are simple value equality and there are no overlapping values or precedence rules. Note how in the CFG representation, all the switch cases are laid out on the same level, which is how the case dispatch is understood. In this example, all the comparison operators are equality, but if we modify dispatch_ifs() slightly and change the comparison, the structure remains unchanged but the semantics are quite different.
void dispatch_ifs() {
int e;
while (e = next()) {
if (e <= 1) // was ==
puts("1");
else if (e <= 2) // was ==
puts("2");
else
puts("unknown");
}
}Now e = 0 prints 1 where it before printed unknown, as we have
widened the first condition. Because there are only two cases we can
tell all comparisons are equality, but this does not work when there
are more than a handful, or when there is non-trivial bodies. The
switch guarantees an equality comparison and communicates that as
clear intent, while the ifs open up for anything. This is a good
demonstration of how we can leverage the different properties and
power of the constructs we choose in our programs for clarity.
Prime path growth and complexity
If we double the number of cases in the switch (to six cases) the
function gets 73 prime paths, up from 28, which shows that the prime
paths grow faster than the cases. I have seen straight forward
switch-loop constructs with roughly 15 000 prime paths. Recall that a
prime path is a maximal simple path or maximal simple cycle. Each
case label will be the first node in the paths that go through the
loop header and to every other case, such as the emphasized paths in
these screenshots. Both prime paths start at 4, case 1:, and go
through the loop, but branch at 3, switch (e). Prime path coverage
requires that both these paths are taken, but we can decide from
reading the source that the sequence is uninteresting as long as
next() can produce every value.
We also need to cover the path from every case to the loop exit. Depending on the program this may not even make sense at all as some programs are designed to loop until there is a quit or interrupt event.
while (more) {
switch (next_event()) {
case event_a:
// do something
break;
// ...
case event_quit:
more = false;
}
}
work();Paths like event_a; while (!more); work() cannot be covered. That’s
not necessarily a problem if we take this into consideration and
decide it is acceptable, but it does means a portion of the prime
paths will remain uncovered and we lose some sensitivity to changes in
coverage. A small rewrite could fix the problem, by weaving the exit
condition into the loop structure. The unreachable() is added to
silence the warning on unhandled cases, but it could be removed
without really changing the program.
for (event e = next_event(); e != event_quit; e = next_event()) {
switch (e) {
// ...
case event_quit:
unreachable();
}
}
work();Why even care about paths from a case, through the loop, and to some other case? The updated state from the previous step is an implicit input to every case in the switch at the current step. This specific function doesn’t really use any of that state, but the structure still suggests it might. Here is an example where it does:
int acc = 1;
for (; *c; ++c) {
switch (*c) {
case 1: acc = (acc + 1) + 1; break;
case 2: acc = (acc + 1) * 2; break;
case 3: acc = (acc + 1) * 3; break;
case 4: acc = (acc * 1.5) / acc; break;
case 5: // fallthrough
default: acc = 0; break;
}
}If the sequence of values were *c >= 5, *c = 4 we would
divide-by-zero in case 4, which is undefined in C. Executing this
sequence is not required to achieve block coverage, edge coverage, or
MC/DC, but it is required by prime path coverage. In fairness, prime
path coverage only requires exercising such sequences goin through the
looping once (otherwise the loop header repeat), so if a problem would
only occur for the block sequence (5, 1, 4) it would still not be
required by prime path coverage. The tests might accidentally
exercise the path because of the required block sequences (5,1) and
(5,4), or you might notice the problem in the process. Either way is
clearly a win and in line with our goal of better programs.
Tweaking the structure
We can rewrite the switch-loop so that it both captures the intent and is more practical to test. First we need to understand what constraints we are working with.
- Are the cases truly independent and does the order-of-processing matter?
- Do we need to share data between cases?
- Are the details of handling each case important?
We can split the iteration and processing by rewriting the first example and move the loop body to a separate function. Making a separate function obviously does not change the program semantics, but it greatly affects structure.
void dispatch1_process(int e) {
switch (e) {
case 1:
puts("1");
break;
case 2:
puts("2");
break;
default:
puts("unknown");
break;
}
}
void dispatch1() {
int e;
while (e = next())
dispatch1_process(e);
}
We can see the effect of this change with gcc -fpath-coverage --coverage dispatch.c -o dispatch.o and zcov. We went from a single
function with 27 paths to two functions with 3 and 6 paths,
respectively. Not only do we need fewer tests, roughly a third, but
it is emphasized that each step is processed independently. There is
no way (except through globals) for the consecutive calls to
communicate or carry dependencies. We can test our processing
function by calling it directly, and don’t need to bother setting up a
stream and calling next(). All of these properties aid in testing. A
test may end up looking like this, testing dispatch1_process()
independently of the event generator:
void check_dispatch() {
assert_prints(dispatch1_process(1), "1");
assert_prints(dispatch1_process(2), "2");
assert_prints(dispatch1_process(3), "unknown");
// Skip the loop
next_reset();
dispatch1();
// Loop twice
next_reset();
next_add(1);
next_add(1);
dispatch1();
}Making state explicit
Sometimes we do need to maintain some state between steps. We extend the example and count how many times we have seen each case:
void dispatch2() {
int e;
size_t count[3] = {};
while (e = next()) {
switch (e) {
case 1:
count[0] += 1;
printf("1: %d\n", count[0]);
break;
case 2:
count[1] += 1;
printf("2: %d\n", count[1]);
break;
default:
count[2] += 1;
printf("unknown: %d\n", count[2]);
break;
}
}
}Count is an implicit parameter to each case. If we were to split
processing and iteration again we need to pass the state explicitly.
We move the whole switch into a process function and add a size_t*
argument. Thanks to inlining, no performance should be lost in
optimized builds.
void dispatch2_process(int e, size_t *count) {
switch (e) {
case 1:
count[0] += 1;
printf("1: %d\n", count[0]);
break;
case 2:
count[1] += 1;
printf("2: %d\n", count[1]);
break;
default:
count[2] += 1;
printf("unknown: %d\n", count[2]);
break;
}
}
void dispatch2() {
int e;
size_t count[3] = {};
while (e = next())
dispatch2_process(e, count);
}This structure is also letting your readers know that the count is indeed shared and updated in the processing step and that is clearly your intention to do so. In this case our state was a single variable and array. For more complex states I like using a bespoke struct for maintaining, but if there are only a couple of variables I usually just pass pointers to them.
Since its responsibility of the process function is to only process a
single event, we can afford more sophisticated control flow and more
code for each case code for each case. It opens up for using return
which no longer terminates the loop, just the step, which may
significantly simplify the control flow.
Returning to the example with divide-by-zero. If the switch is moved to a separate function we get this. This redesign is driven by the goal of reducing the number of prime paths as a proxy for complexity, and as a result problems stands out. Programmers are sensitive to division by unchecked inputs, but less so when the operand is a variable that is used in a complex context with a large surface area. This is a nice example of how even small restructurings “open up” for even more significant improvements.
int process(int acc, int c) {
switch (c) {
case 1: return (acc + 1) + 1;
case 2: return (acc + 1) * 2;
case 3: return (acc + 1) * 3;
case 4: return (acc * 1.5) / acc;
case 5: // fallthrough
default: return 0;
}
}
// original function
int acc = 1;
for (; *c; ++c)
acc = process(acc, *c);A real world example
Here is a real world example from GNU coreutils v9.7 od.c. This is the original:
static void
print_ascii (idx_t fields, idx_t blank, void const *block,
MAYBE_UNUSED char const *unused_fmt_string, int width,
idx_t pad)
{
unsigned char const *p = block;
idx_t pad_remaining = pad;
for (idx_t i = fields; blank < i; i--)
{
unsigned char c = *p++;
char const *s;
char buf[4];
switch (c)
{
case '\0':
s = "\\0";
break;
case '\a':
s = "\\a";
break;
case '\b':
s = "\\b";
break;
case '\f':
s = "\\f";
break;
case '\n':
s = "\\n";
break;
case '\r':
s = "\\r";
break;
case '\t':
s = "\\t";
break;
case '\v':
s = "\\v";
break;
default:
sprintf (buf, (isprint (c) ? "%c" : "%03o"), c);
s = buf;
}
idx_t next_pad = pad_at (fields, i - 1, pad);
int adjusted_width = pad_remaining - next_pad + width;
xprintf ("%*s", adjusted_width, s);
pad_remaining = next_pad;
}
}And rewritten using state explicitly passed to a helper function:
static char const *
as_ascii_octal (unsigned char c, char *buf) {
switch (c)
{
case '\0':
return "\\0";
case '\a':
return "\\a";
case '\b':
return "\\b";
case '\f':
return "\\f";
case '\n':
return "\\n";
case '\r':
return "\\r";
case '\t':
return "\\t";
case '\v':
return "\\v";
default:
sprintf (buf, (isprint (c) ? "%c" : "%03o"), c);
return buf;
}
}
static void
print_ascii (idx_t fields, idx_t blank, void const *block,
MAYBE_UNUSED char const *unused_fmt_string, int width,
idx_t pad)
{
unsigned char const *p = block;
idx_t pad_remaining = pad;
for (idx_t i = fields; blank < i; i--)
{
char buf[4];
char const *s = as_ascii_octal (*p++, buf);
idx_t next_pad = pad_at (fields, i - 1, pad);
int adjusted_width = pad_remaining - next_pad + width;
xprintf ("%*s", adjusted_width, s);
pad_remaining = next_pad;
}
}Because all the cases fit in half a screen and simply assigned a
literal to s, the value proposition is not immediately obvious, but
I do find the revised version an improvement. If anything, it lets us
focus on the other things going on in the loop (the padding and width
adjustment) rather than the mapping from a character to its octal
representation. If anything, prime path coverage is significantly
simplified; all paths through as_ascii_octal() can be tested with a
single run of print_ascii with the input "\0\a\b\f\n\r\t\vc\0x01".
Non-trivial cases
I want to include one last example in this post to show what happens
when the cases include control flow by updating the previous example
to only print on the first and then every 10th occurrence. This adds
what I initially would think was moderate complexity, but this change
takes us to 54 prime paths. The control flow in each case acts as a
multiplier in a way, as the path case 1; if-then; (e); case 2: if-then is different from case 1; if-then; (e); case 2: if-else.
These two paths can be seen in the screenshots. We can apply the same
tricks are in the other examples to bring the complexity down, and the
ability to do so would verify the independence of each case.
void dispatch3() {
int e;
size_t count[3] = {};
while (e = next()) {
switch (e) {
case 1:
count[0] += 1;
if (count[0] % 10 == 1)
printf("1: %d\n", count[0]);
break;
case 2:
count[1] += 1;
if (count[1] % 10 == 1)
printf("2: %d\n", count[1]);
break;
default:
count[2] += 1;
printf("unknown: %d\n", count[2]);
break;
}
}
}Closing remarks
Most of the examples in this post are what I would call standard refactoring techniques and can neatly summed up as “move a block into a separate function”. That summary does not capture the process of deciding which blocks to move into separate functions, it describes the what and not the why. The prime paths and coverage is a data driven approach that approximates complexity by associating it with the number of prime paths that, when mixed with good engineering and sensibilities, guides testing and results in better programs (ideally).
The observations of this post actually don’t just apply to the switch-loop, they apply to any complex structure in a loop. The switch is a bit special because it is a simple dispatch based on simple values and often handle a lot of cases that makes loops larger, while each case at the same time has little overlap.
Breaking up sources of complexity also helps clean up the signal from your test suite. Having covered 12 out of 357 prime paths probably means that you cannot use that data to make a qualified decision on whether the structure is well exercised or if a key path is missing. 352/357 prime paths covered, means that you can look at the each of the missing coverage and determine if it is valuable, or even possible, to cover them.
Duff’s device
I want to include a showcase of maybe the most (in)famous switch-loop, Duff’s device. Looking at this construct with the zcov CFG visualization is a great way of demystifying the uncommon technique of putting a loop inside a switch where every case falls through. Complexity wise it’s not all that bad either, as Duff’s device only has 27 prime paths and mostly straight forward control flow.
void send(short *to, short *from, int count) {
register int n = (count + 7) / 8;
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
}