Although the amount of decision logic in a program is to some extent determined by the intended functionality, software is often unnecessarily complex, especially at the level of individual modules. Unnecessary complexity is an impediment to effective testing for three major reasons. First, the extra logic must be tested, which requires extra tests. Second, tests that exercise the unnecessary logic may not appear distinct from other tests in terms of the software's functionality, which requires extra effort to perform each test. Finally, it may be impossible to test the extra logic due to control flow dependencies in the software, which means that unless the risk of not satisfying the testing criterion is accepted, significant effort must be expended to identify the dependencies and show that the criterion is satisfied to the greatest possible extent.

Unnecessary complexity also complicates maintenance, since the extra logic is misleading unless its unnecessary nature is clearly identified. Even worse, unnecessary complexity may indicate that the original developer did not understand the software, which is symptomatic of both maintenance difficulty and outright errors. This section quantifies unnecessary complexity, and discusses techniques for removing and testing it.

9.1 Actual complexity and realizable complexity

A more problematic kind of unnecessary complexity prevents structured testing as described in section 5 from being fully satisfied by any amount of testing. The problem is that data-driven dependencies between the control structures of a software module can prevent a basis set of paths through the module's control flow graph from being exercised. The "classify" module in Figure 9-1 and its control flow graph in Figure 9-2 illustrate this phenomenon. Although the cyclomatic complexity is 4, only 3 paths can possibly be executed, because the "TRUE" outcome of exactly one of the three decisions must be exercised on any path. Another way to view this is that the outcome of the first decision may determine the outcome of the second, and the outcomes of the first two decisions always determine the outcome of the third. Figures 9-3 and 9-4 show "classify2," a reengineered version with no unnecessary complexity.

Figure 9-1. Code for module with unnecessary complexity.

Figure 9-2. Graph for module with unnecessary complexity.

Figure 9-3. Code after removing unnecessary complexity.

Figure 9-4. Graph after removing unnecessary complexity.

The actual complexity, ac, of a module is defined as the number of linearly independent paths that have been executed during testing, or more formally as the rank of the set of paths that have been executed during testing. The structured testing criterion requires that the actual complexity equal the cyclomatic complexity after testing. Note that the actual complexity is a property of both the module and the testing. For example, each new independent test increases the actual complexity.

The realizable complexity, rc, is the maximum possible actual complexity, i.e., the rank of the set of the paths induced by all possible tests. This is similar to the characterization of cyclomatic complexity as the rank of the set of all possible paths, except that some paths may not be induced by any test. In the "classify" example, rc is 3 whereas v(G) is 4. Although rc is an objective and well-defined metric, it may be hard to calculate. In fact, calculating rc is theoretically undecidable [HOPCROFT], since, if it were possible to calculate rc, it would also be possible to determine whether rc is at least 1, which would indicate whether at least one complete path could be executed, which is equivalent to the module halting on some input.

One obvious property of rc is that after any amount of testing has been performed on a module, ac <= rc <= v(G). Satisfying the structured testing criterion therefore suffices to prove that rc = v(G). However, when ac < v(G), one of two situations can hold:

1. At least one additional independent test can be executed.
2. ac = rc, and hence rc < v(G).

There are many situations in which it is easy to see that rc < v(G). One example is a loop with a constant number of iterations, such as the "min" module in Figure 9-5.

Figure 9-5. Loop with constant number of iterations.

The "TRUE" outcome of the loop is always executed ten times as frequently as the "ENTRY" branch along any executable path, which is a linear control dependency and thus reduces rc by one. Loops with a constant number of iterations are fairly common in software. When the constant might change during maintenance (for example, a hash table size), it is worth running a test with a different constant value. When the constant will not change (for example, the number of axes in graphics rendering code), the dependency can simply be taken into account during testing.

9.2 Removing control dependencies

Figure 9-6. Module with three dependencies.

One dependency is the "&& k-- > 0" condition at line 50. This condition is always true, since it can only be reached when "k > 0" is true at line 49, and the value of k is not changed in the interim. The condition can therefore be eliminated, moving the "k--" to the initialization part of the loop on line 51 to preserve functionality. The other two dependencies are due to the hash table being traversed twice, once to get the value of "max" for the list allocation, then again to fill the list. These dependencies can be eliminated by modularization of the "max" calculation. Figures 9-7 and 9-8 show the reengineered functions "printwords2" and "getmax," for which rc = v(G) and the maximum v(G) has been reduced from 11 to 7.

Figure 9-7. First reengineered module.

Figure 9-8. Second reengineered module.

9.3 Trade-offs when reducing complexity

Figure 9-9. Code for structured module, rc < v(G).

Figure 9-10. Graph for structured module, rc < v(G).

Figures 9-11 and 9-12 show the code and graph for a reengineered version of the same module, with rc and v(G) both equal to 3. Although in principle this is an improvement, the new version is not well-structured. The loop has two exit points, the bottom test and the conditional return in the middle. Even so, most programmers would agree that the reengineered version is better in this simple example. However, for more complex programs the structural degradation from complexity reduction can be much more severe, in which case the original version would be preferred. There is also a "middle ground" of programs for which reasonable programmers can disagree about the desirability of reengineering, depending on their experience and stylistic preferences. In such cases, it is less important to worry about making the "right" choice, and more important to document the reasons for the trade-off.

Figure 9-11. Reengineered code, rc = v(G) but not well-structured.

Figure 9-12. Reengineered graph, v(G) = rc but not well-structured.

In addition to the trade-off between direct complexity reduction and structural quality, there is also a trade-off between modularization and design quality [PARNAS]. When splitting a control dependency across a module boundary, there is the risk of introducing control coupling between the modules and limiting the cohesion of each module. As when considering splitting up a module to satisfy a complexity threshold, the most important consideration is whether each new module performs a single cohesive function. If it does, then the modularization is consistent with design quality. Otherwise, the design quality degradation must be weighed against the benefits of the reduced complexity. In the "printwords" example, the new "getmax" function performed a single cohesive function, so the complexity reduction was justified. If, on the other hand, the module was split in such a way as to require passing local variables by reference and the only name that could be thought of for the new module was "more_printwords," the modularization would not have been justified. As with structural quality, having a clearly documented reasoning process is vital when the trade-off seems fairly balanced.