Code complexity analysis is the process of examining your system under test and producing a number which measures how complicated the SUT is. There are many different types of code complexity analysis. One of the most common is called McCabe’s Cyclomatic Complexity. Developed in the mid-1970s it has stood the test of time quite well. Cyclomatic complexity measures the number of linearly independent paths through a program module. For example, consider this artificially-simple module:
function foo(int n)
if (n < 0)
result = -1;
else if (n >= 0 && n <= 9)
result = 1;
result = 0;
It is fairly obvious that there are exactly 3 paths through the code. Cyclomatic complexity was designed, in theory, to be independent of computer language. If a code module is represented as a graph structure then the definition of cyclomatic complexity is
CC = E – N + 2
where E is the number of edges in the graph, and N is the number of nodes in the graph. (Note: there are several variations on this formula.) A graph corresponding to the module above is shown at the bottom of this blog entry. The cyclomatic complexity would be calculated as CC = 8 – 7 + 2 = 3.
It’s not practical to directly translate a program module into a graph structure, so cyclomatic complexity is calculated by looking at the branching instructions (typically if-then, case, and so on) in the SUT source code. It is not feasible to compute cyclomatic complexity by hand, so there are a large number of commercial and Open Source tools which can do the job for you. You can also write your own complexity metric generation tool fairly easily. Unfortunately to actually calculate cyclomatic complexity you must take into account the syntax and constructs of a particular programming language. This means that the same pseudocode translated into Visual Basic may not yield the exact same cyclomatic complexity metric as the pseudocode translated into Java. But in practical terms this usually isn’t an issue.
So, what is code complexity analysis good for? During the development process, if you monitor complexity, you can early identify situations where your source code’s complexity is rapidly increasing. You can also use code complexity metrics to help estimate how much testing resources you’ll need — more complex code requires a greater test effort.
Cyclomatic complexity is just one of many code complexity metrics. You can group all complexity metrics into two categories: static and dynamic (or run-time). Static metrics analyze the system under test’s source code. Dynamic metrics analyze the SUT’s behavior during run time. Cyclomatic complexity is an example of static analysis. One way to group static code complexity metrics is to categorize them into "traditional" (my term) and object-oriented metrics. Many of the original code complexity metrics, including cyclomatic complexity, were created before the use of object oriented languages was common. So, starting in the mid 1980s, new complexity measures were created which are specifically intended for object oriented programming. Now the traditional and OOP complexity measures are by no means exclusive — the categorization is just a useful way to think about the large number of complexity metrics available to you. In a future blog entry I’ll describe alternative static complexity measures and OOP complexity measures.
If you enjoyed reading this blog you might enjoy working at Microsoft. My parent company, Volt Information Sciences, is always looking for software engineers. Check out the job listings at http://jobs.volt.com/.