Measuring code complexity as a way to determine number of test cases

There are tools which will measure code complexity (cyclomatic complexity) for a software project. Cyclomatic complexity is the number of linearly independent paths through a program's source code. For example, given the following code:

if(expr1) {
    // option1
} else if(expr2) {
    // option2
} else {
    // option3
}

if(expr1) {
    // option4
} else {
    // option5
}

Assuming expr1 != expr2, the following paths through the code exist:

1. option1, option4 (expr1 == true)
2. option2, option5 (expr2 == true)
3. option3, option5 (expr1 == false, expr2 == false)

If you look carefully at this list, when testing this snippet of code, for full path coverage, I want a set of tests which will cause each line of code to be executed at least once. I want each if/elseif/else to get evaluated and the body of each to get executed. To make this happen I need:

1. expr1 == true, which implies expr2 == false
2. expr2 == true, which implies expr1 == false
3. expr1 == false and expr2 == false

The number of paths through the code is the number of test cases! If you are looking at branch coverage the number of paths required for branch coverage is going to be similar. You can give an example where the branch coverage requires less than the code complexity. For example:

if(expr1) {
    // option1
} else {
    // option2
}

if(expr2) {
    // option3
} else {
    // option4
}

For this example, I need the following:

1. expr1 == true, expr2 == true
2. expr1 == false, expr2 == false

or I could use:

1. expr1 == true, expr2 == false
2. expr1 == false, expr2 == true

Both examples will cause all branches to be taken at least once. Generally speaking the rule is:

branch coverage <= code complexity <= path coverage

So if you have the code complexity, you know the number of paths through the program has to be at least the code complexity of the application. This also assumes that all paths are reachable. A code complexity tool should also tell you if certain paths are not reachable. Actually, many development environments will warn you if a path is not reachable.

So next time you are asked to estimate how many test cases you will require to adequately test an application, use a code complexity tool to give you a rough idea.

Additionally, the complex of the code can give you some idea of the number of defects which should be found. The more complex the code, the greater the number of defects should be suspected. This is not always true but can be a good rule of thumb.

See an article from Enerjy for an example of this phenomenon.