Using branch coverage to drive test cases

[AttilaMihaly]

Problem Statement

Making sure that your business logic is correct is one of the main focus areas of the Morphir tooling. At the lowest level we have compile -time checks which ensure that your logic handles every possible value that can be passed into it. We also have to make sure that it's doing what's expected. We already have support for defining test cases, saving them in a JSON and then running them against the logic either interactively on the UI or as part of the CI. But how do you know if you have enough test cases to know that the logic is always right?

Analysis

To be absolutely sure you would have to have a test case for every possible input which is not feasible in most cases since the number of possible inputs is large or even infinite (assuming arbitrary precision). But even functions with an infinite number of possible inputs make a finite number of decisions in the logic, so it is possible to check every possible combination of decisions a piece of logic could make. This is where the concept of Cyclomatic Complexity and Branch Coverage comes in:

• Cyclomatic Complexity in simple terms is the number of different paths the logic could follow during execution. It was originally defined as a metric to measure the complexity and testability of a piece of code but there are other uses as you will see.
• Branch Coverage is another metric which shows what percentage of all the execution paths the logic could take is covered with a unit-test. When this is a 100% that means that you have tested every possible combination of decisions the logic might make so you can be almost certain that it's correct.
  • Note: Interestingly, there are situations when you cannot reach 100% coverage because one of the branches has conflicting conditions. This branch is unreachable so it should be removed from the code which will make it possible to reach 100% coverage. So this metric is also useful to improve the code.

These metrics are very useful by themselves and we can build even more on top of the core functionality that underpins them: identifying all the branches of a piece of business logic. Let me lay all those out in user story form.

User Stories

• As a Morphir author, I want to understand the complexity of each function in my business logic so that I can focus on getting them right and simplify them if possible.
• As a Morphir author, I want to know what percentage of execution paths is covered by my test cases so that I can focus my attention on adding more test cases where needed and know when I'm done.
• As a Morphir author, I want to know which exact branches have not been covered with a test case yet so that I can add coverage for them.
• As a Morphir author, I want to know what conditions my input has to satisfy to cover a certain branch so that it's easier for me to come up with the right test case.
• As a Morphir author, I want the system to highlight inputs that violate the conditions of the branch I'm trying to cover so that it's easier for me to come up with the right test case.
• As a Morphir author, I want the system to populate the inputs that satisfy the conditions for a certain branch where possible so that I can add coverage with less effort.
• As a Morphir author, I want the system to be able to shrink a large set of test cases to a minimal set that has the same branch coverage so that I can optimize my manual test cases or use regression test data to generate human-readable test cases.

[AttilaMihaly]

Another interesting observation is that different branches of the code will use different subsets of the data points passed into the function. For example looking at this logic:

if a = 1 then
    if b = 2 then
        "foo"
    else
        "bar"
else
    if c = 3 then
        "baz"
    else
        "bat"

This logic has 4 branches, 2 of those uses a and b, the other 2 uses a and c. So if we want to minimize the amount of input data we need to test the function we can take this into account and specify these test cases:

a	b	c	out
1	2		foo
1	3		bar
2		3	baz
2		4	bat

So at this point we might say that it shouldn't matter what you put in the empty cells so we'll just let the system replace it with any random value. But does that provide full coverage?

Let's assume that we are using this to ensure that we came up with this logic based on an existing system but we made a mistake in the process and missed a condition:

if a = 1 then
    if b = 2 then
        "foo"
    else
        -- we missed this before
        if c = 4 then
            "crash"
        else
            "bar"
else
    if c = 3 then
        "baz"
    else
        "bat"

Will our test cases catch this? Not unless we happen to accidentally pass in 4 as the random number for c.

This is because our interpretation of an empty cell was wrong. It doesn't mean "any value will do", it means "every possible value should yield the same result".

Technically we cannot generate all the possible inputs, but the tooling could apply property-based testing to approximate it. With that we would get better coverage than full branch coverage. Branch coverage makes sure that every decision that the logic makes is right and this extension is trying to ensure that there are no decisions that the logic is missing.