Are short-circuiting paths considered for path coverage?

Question

In a book Doron A. Peled, he states that "

path coverage does not subsume multiple condition coverage because you can execute all the paths without exercising all the conditions.

But I believe this is not right (it implies path is only "visible" branches), because even cyclomatic complexity is increased by one for each logical operator in a decision, stating that a new decision node is created in the program control flow chart, creating immediate paths that needs to be exercised - in short-circuiting languages. Therefore: if(A && B && C) have two paths from the traditional perspective (branches), but precisely there is more than that if the language allow short circuiting. Thus, I believe the statement quoted is not correct. Even for a single decision, they are equally strong. In the context of a whole method, path coverage is obviously stronger as with every decision the total count doubles.

Am I missing something or is my reasoning correct?

Answer 1

So I understand what you are saying to mean that this:

if(A && B && C) { ... }

Has this graph:

Which after drawing it out, I think indeed has to be correct. If A,B and C have no side effects e.g. if they are just primitive Boolean values, then I think you can get away with reduce them to the same graph as the non-short cut version:

if (A & B & C) { ... }

But if A, B, and C are functions, you really can't ignore the fact that B won't evaluate unless A is true and C won't evaluate if A and B are not true. So in order to get all paths, you can't just test the situation where A is false and the situation where A,B, and C are all true. You need to test where A is true and B is false, A and B are true and C is false as well so short-circuiting adds two paths.

My first thought was that you are right and this is an error in the author's description. But I just realized this point might make sense if we consider non-short circuiting. Consider:

if (A | B | C) {...}

In this case we always evaluate all three conditions so there are only two paths. However, there are 8 different combinations of conditions. We can therefore evaluate both paths without checking all the possible condition states. Perhaps that is what the author means here?

Answer 2

There are a couple kinds of code coverage tools. Most tools have statement coverage or branch coverage. However, some do provide condition coverage. Doron's statement holds true for all coverage tools that don't provide condition coverage. Assuming you had a run where A and C were true, then those two parts of the codition will be marked as covered, but B won't be. That said, it doesn't prove you've fully tested the conditions.

In the case of short circuiting, the questions you have to ask are:

• Do my tests have side-effects? In other words does B or C do things that I'm expecting down line?
• Is short circuiting what I want? In many cases, yes.
• Have I tested the semantic meaning?

If your tests have side-effects, that can lead to very hard to find bugs, particularly if down-stream code is expecting B's side affects to be applied even if A is false. It's always best to minimize this as much as possible. I won't say eliminate it since you may be counting on the short circuiting to avoid a costly action if possible.

You haven't semantically tested your condition unless you have tested all designed eventualities. In other words, in this case there may need to be as many as 9 tests to fully evaluate the semantics of that branch--particularly if you have side-effects you are counting on. Of course, if you can prove that the semantics really are that everything must be true to run the code inside the if statement or it doesn't get called at all, it might be semantically correct to only have 2 tests.

With good design you can separate code that manipulates state from code that checks it. That will simplify the semantics greatly for your if(A && B && C) to if(true) and if(false).

Answer 3

Consider the hypothetical refactoring where we replace

function(bool A, bool B, bool C) { ..
    if(A && B && C) {..

With

function(Func<bool> conditionFn) { ..
    if(conditionFn()) {..

It doesn't matter how complex conditionFn is, function has only two paths.

But! you should obviously not only test both paths, even though this would give you 100% path coverage, but also whether the correct path is followed for given input parameters A, B and C. ie. tests for conditionFn

if however we have

function(Func<bool> A, Func<bool>B, Func<bool> C) { ..
    if(A() && B() && C()) {..

Then, yes we have more branches due to short circuiting possibly preventing the code in these functions from running if for example A returns false.

Answer 4

The statement you quoted is true, but not directly helpful due to the prevalence of short-circuiting operators in modern languages. It is not correct to interpret && or || in C-like languages as logical operators. Instead, they are control-flow operators and a sequence point. Other languages make this clearer (e.g. the logical and vs. the control-flow andalso in Standard ML).

For a program using only short-circuit operators, it is possible to interpret multiple condition coverage as equal to branch coverage and equal to simple condition coverage. Then, path coverage subsumes multiple condition coverage. This interpretation is essentially correct, but not very useful.

Multiple condition coverage is not fundamentally about the control flow of the program, but about the data flow. Condition coverage asks: the values of which boolean expressions have been covered? Multiple condition coverage is then interested in the combinations of boolean subexpressions within one decision operator. For the purpose of calculating this coverage metric, it can be sensible to disregard short-circuiting behaviour.

So in a condition without short-circuiting boolean operators or when disregarding short-circuiting behaviour, then it is clear that full path coverage for if (a & b) ... can be obtained with only two cases (e.g. a=false, b=false and a=true, b=true), whereas test cases are missing for full multiple condition coverage (here: a=false, b=true and a=true, b=false).

One practical benefit of using condition coverage is to show that the condition can actually influence the decision outcome. If not, we might unexpectedly have dead code. For this, multiple condition coverage is not necessary, but modified condition/decision coverage is sufficient. For the if (a & b) example, we would need three test cases for MC/DC: a=true, b=true; a=true, b=false; a=false, b=true. Therefore, path coverage doesn't imply MC/DC coverage either.

One problem using any kind of condition coverage is that this metric can be easily gamed by using control flow operators instead of logical operators. Additionally, incrementally building a decision like bool d = true; d &= a; d &= b; if (d) ... makes it non-obvious how a and b contribute to the decision. Therefore, condition coverage metrics are generally meaningless unless coupled to a specific coding style.