4

I know how code coverage works in general, and I know what branch coverage is. But I can not seem to find an explanation for how branch coverage handles loops.

Does it work like path coverage? Where a loop which runs 10 times is a different path from the exact same loop running 11 times. Or would those two cases be the same thing in branch coverage?

7

Branch coverage and path coverage are distinct concepts.

Branch coverage

To measure branch coverage, we look for all the points where branching can take place. At each branching point, both branches should have been executed at least once. E.g. in this pseudo-code:

A
if B:
  C
else:
  D
E
if F:
  G
I

we have two branch points – the if B and if F conditionals. To get full branch coverage, each of these conditionals should execute the true and false branch, i.e. both B and F would have to each be false and true each. A test plan could be:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = true
  F = true
  # executes A B C _ E F G I

As you can see, full branch coverage implies full statement coverage.

When dealing with loops, it might be helpful to “compile” it to a more low-level representation that only has conditionals and gotos. E.g.:

// C99 code
A;
for (int i = 0; i < length; ++i)
  B;
C;

could be understood as

// Block 1
  A;
  int i = 0;

// Block 2
loop_start:
  if (!(i < length))
    goto loop_end;  // -> Block 4

// Block 3
  B;
  ++i;
  goto loop_start;

// Block 4
loop_end:
  C;

There is only one conditional here, in block 2. So to get full branch coverage, it must once evaluate both false and true. A test plan could be:

Run 1:
  length = 1
  # executes B1 B2 B3 B2 B4

So the loop condition will evaluate to both true and false with this test plan. But clearly, this is not a satisfactory test: what happens when the loop is skipped altogether (e.g. with length = 0)? What happens if the loop body modifies some state, will it still work with hundreds of iterations?

Path coverage

When we group the code into a control flow graph, path coverage measures the fraction of paths taken from all possible paths. Path coverage implies branch coverage. When we look back at the first example, we could get branch coverage with only two test cases. But to get path coverage we will need 4 cases: two for each path through the first conditional, multiplied by two cases for the second conditional:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = false
  F = true
  # executes A B _ D E F G I
Run 3:
  B = true
  F = false
  # executes A B C _ E F _ I
Run 4:
  B = true
  F = true
  # executes A B C _ E F G I

When our control flow graph includes loops, there are in general infinitely many possible paths. In some cases, the number of loop iterations is bounded by a constant and can be tested, but in general this is not the case. Since complete path coverage is useful but not reachable, we tend to use other coverage metrics.

When I write tests, I tend to ignore full path coverage for loops (path coverage for simple conditionals is still very useful). However, multiple paths could be grouped into equivalence classes for testing – running the code with 0, 1, 2, and “many” iterations should be a decent approximation. A possible test plan:

Run 1:
  length = 0
  # executes B1 B2 B5
Run 2:
  length = 1
  # executes B1 B2 B3 B2 B5
Run 3:
  length = 2
  # executes B1 B2 B3 B2 B3 B2 B5
Run 4:
  length = 123
  # executes B1 B2 B3 B2 B3 ... B2 B3 B2 B5

There are also formal code metrics that allow us to quantify loop tests, such as Linear code sequence and jump-coverage. However, I have never used it.

Testing loops via recursion

When loops are expressed as recursion, the loop is not explicit and thus “hidden” from path coverage. Is this a problem? Kind of. The loop is still present in the control flow graph of the program as whole, but not in the CFG of the recursive function.

However, it is far easier to show that the loop is correct when expressed recursively. We can test the base cases, and a non-base case. Since each non-base-case result is constructed from the base cases (which we have already shown to be correct), then the function as whole can be presumed to be correct. This is analogue to the proof by induction technique, except that tests aren't proofs of correctness, but merely examples of correctness.

  • 2
    Regarding your last paragraph: many of these metrics were developed in the times of Fortran, Cobol, Pascal, C, and friends, and it shows. Functional Programming with (tail) recursion instead of loops and the implicit conditional that is ad-hoc polymorphism (ubiquitous in OO) are two things that are typically very poorly represented in those metrics. – Jörg W Mittag Oct 18 '15 at 17:18
  • Great answer, although you are not really explaining what is needed for full branch coverage. I spoke to my teacher and he told me we need two cases essentially: one where the loop is not executed, and one where it is executed once or more. Would you consider adding that to your answer before I mark your answer as the right one? – AntonNiklasson Oct 20 '15 at 8:39
  • 2
    @AntonNiklasson well, as my answer shows you can get full branch coverage of a loop by a single test case that leads to more than one loop execution, since the loop condition will evaluate to both true and false. Your teacher and I agree that a separate test case where the loop body is skipped would be beneficial. But the reason for that isn't that we wouldn't have full branch coverage otherwise, but merely that branch coverage is not a very useful metric for loops. Intuitively, it makes sense to treat the number of loop iterations as an integer input, and e.g. test the cases 0,1,2,567 – amon Oct 20 '15 at 18:20
  • Alright, sounds good to me. Thanks for all your input on this. Marking your answer :) – AntonNiklasson Oct 21 '15 at 10:25
  • This answer doesn't have enough credit! I searched for at least an hour before finding this - very clear explanation. I especially find merit in your pseudo-compiling step. – Jason Cemra Jun 13 '18 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.