Is cyclomatic complexity really related to branch coverage? by Mark Seemann
A genuine case of doubt and bewilderment.
Regular readers of this blog may be used to its confident and opinionated tone. I write that way, not because I'm always convinced that I'm right, but because prose with too many caveats and qualifications tends to bury the message in verbose and circumlocutory ambiguity.
This time, however, I write to solicit feedback, and because I'm surprised to the edge of bemusement by a recent experience.
Collatz sequence #
Consider the following code:
public static class Collatz { public static IReadOnlyCollection<int> Sequence(int n) { if (n < 1) throw new ArgumentOutOfRangeException( nameof(n), $"Only natural numbers allowed, but given {n}."); var sequence = new List<int>(); var current = n; while (current != 1) { sequence.Add(current); if (current % 2 == 0) current = current / 2; else current = current * 3 + 1; } sequence.Add(current); return sequence; } }
As the names imply, the Sequence
function calculates the Collatz sequence for a given natural number.
Please don't tune out if that sounds mathematical and difficult, because it really isn't. While the Collatz conjecture still evades mathematical proof, the sequence is easy to calculate and understand. Given a number, produce a sequence starting with that number and stop when you arrive at 1. Every new number in the sequence is based on the previous number. If the input is even, divide it by two. If it's odd, multiply it by three and add one. Repeat until you arrive at one.
The conjecture is that any natural number will produce a finite sequence. That's the unproven part, but that doesn't concern us. In this article, I'm only interested in the above code, which computes such sequences.
Here are few examples:
> Collatz.Sequence(1) List<int>(1) { 1 } > Collatz.Sequence(2) List<int>(2) { 2, 1 } > Collatz.Sequence(3) List<int>(8) { 3, 10, 5, 16, 8, 4, 2, 1 } > Collatz.Sequence(4) List<int>(3) { 4, 2, 1 }
While there seems to be a general tendency for the sequence to grow as the input gets larger, that's clearly not a rule. The examples show that the sequence for 3
is longer than the sequence for 4
.
All this, however, just sets the stage. The problem doesn't really have anything to do with Collatz sequences. I only ran into it while working with a Collatz sequence implementation that looked a lot like the above.
Cyclomatic complexity #
What is the cyclomatic complexity of the above Sequence
function? If you need a reminder of how to count cyclomatic complexity, this is a good opportunity to take a moment to refresh your memory, count the number, and compare it with my answer.
Apart from the opportunity for exercise, it was a rhetorical question. The answer is 4.
This means that we'd need at least four unit test to cover all branches. Right? Right?
Okay, let's try.
Branch coverage #
Before we start, let's make the ritual denouncement of code coverage as a target metric. The point isn't to reach 100% code coverage as such, but to gain confidence that you've added tests that cover whatever is important to you. Also, the best way to do that is usually with TDD, which isn't the situation I'm discussing here.
The first branch that we might want to cover is the Guard Clause. This is easily addressed with an xUnit.net test:
[Fact] public void ThrowOnInvalidInput() { Assert.Throws<ArgumentOutOfRangeException>(() => Collatz.Sequence(0)); }
This test calls the Sequence
function with 0
, which (in this context, at least) isn't a natural number.
If you measure test coverage (or, in this case, just think it through), there are no surprises yet. One branch is covered, the rest aren't. That's 25%.
(If you use the free code coverage option for .NET, it will surprisingly tell you that you're only at 16% branch coverage. It deems the cyclomatic complexity of the Sequence
function to be 6, not 4, and 1/6 is 16.67%. Why it thinks it's 6 is not entirely clear to me, but Visual Studio agrees with me that the cyclomatic complexity is 4. In this particular case, it doesn't matter anyway. The conclusion that follows remains the same.)
Let's add another test case, and perhaps one that gives the algorithm a good exercise.
[Fact] public void Example() { var actual = Collatz.Sequence(5); Assert.Equal(new[] { 5, 16, 8, 4, 2, 1 }, actual); }
As expected, the test passes. What's the branch coverage now?
Try to think it through instead of relying exclusively on a tool. The algorithm isn't more complicated that you can emulate execution in your head, or perhaps with the assistance of a notepad. How many branches does it execute when the input is 5
?
Branch coverage is now 100%. (Even the dotnet coverage tool agrees, despite its weird cyclomatic complexity value.) All branches are exercised.
Two tests produce 100% branch coverage of a function with a cyclomatic complexity of 4.
Surprise #
That's what befuddles me. I thought that cyclomatic complexity and branch coverage were related. I thought, that the number of branches was a good indicator of the number of tests you'd need to cover all branches. I even wrote an article to that effect, and no-one contradicted me.
That, in itself, is no proof of anything, but the notion that the article presents seems to be widely accepted. I never considered it controversial, and the only reason I didn't cite anyone is that this seems to be 'common knowledge'. I wasn't aware of a particular source I could cite.
Now, however, it seems that it's wrong. Is it wrong, or am I missing something?
To be clear, I completely understand why the above two tests are sufficient to fully cover the function. I also believe that I fully understand why the cyclomatic complexity is 4.
I am also painfully aware that the above two tests in no way fully specify the Collatz sequence. That's not the point.
The point is that it's possible to cover this function with only two tests, despite the cyclomatic complexity being 4. That surprises me.
Is this a known thing?
I'm sure it is. I've long since given up discovering anything new in programming.
Conclusion #
I recently encountered a function that performed a Collatz calculation similar to the one I've shown here. It exhibited the same trait, and since it had no Guard Clause, I could fully cover it with a single test case. That function even had a cyclomatic complexity of 6, so you can perhaps imagine my befuddlement.
Is it wrong, then, that cyclomatic complexity suggests a minimum number of test cases in order to cover all branches?
It seems so, but that's new to me. I don't mind being wrong on occasion. It's usually an opportunity to learn something new. If you have any insights, please leave a comment.
Comments
My first thought is that the code looks like an unrolled recursive function, so perhaps if it's refactored into a driver function and a "continuation passing style" it might make the cyclomatic complexity match the covering tests.
So given the following:
I calculate the Cyclomatic complexity of
Continuation
to be 2 andStep
to be 3.And it would seem you need 5 tests to properly cover the code, 3 for
Step
and 2 forContinuation
.But however you write the "n >=1" case for
Continuation
you will have to cover some ofStep
.There is a relation between cyclomatic complexity and branches to cover, but it's not one of equality, cyclomatic complexity is an upper bound for the number of branches. There's a nice example illustrating this in the Wikipedia article on cyclomatic complexity that explains this, as well as the relation with path coverage (for which cyclomatic complexity is a lower bound).
I find cyclomatic complexity to be overly pedantic at times, and you will need four tests if you get really pedantic. First, test the guard clause as you already did. Then, test with 1 in order to test the
loop body not being run. Then, test with 2 in order to test that the is executed, but we only hit the part of the . Finally, test with 3 in order to hit the inside of the . That's four tests where each test is only testing one of the branches (some tests hit more than one branch, but the "extra branch" is already covered by another test). Again, this is being really pedantic and I wouldn't test this function as laid out above (I'd probaby put in the test with 1, since it's an edge case, but otherwise test as you did).I don't think there's a rigorous relationship between cyclomatic complexity and number of tests. In simple cases, treating things as though the relationship exists can be helpful. But once you start having iterrelated branches in a function, things get murky, and you may have to go to pedantic lengths in order to maintain the relationship. The same thing goes for code coverage, which can be 100% even though you haven't actually tested all paths through your code if there are multiple branches in the function that depend on each other.
Thank you, all, for writing. I'm extraordinarily busy at the moment, so it'll take me longer than usual to respond. Rest assured, however, that I haven't forgotten.