Simpler programs are more reliable. Omar Bashir sees how to make improvements.
Conditional statements are used to alter the flow of control. Increase in the number of variables in these statements, the number of alternative branches or the depth of conditional statements add to the complexity of sections of programs where these statements exist. Design patterns can help manage this complexity by dividing these conditional statements between different participants of the patterns used.
Introduction
All programming languages contain conditional statements that are used to alter the flow of control. Based on the values of certain variables, these conditional statements determine the branch of the program that is executed. Popular conditional statement constructs are IF, IF ELSE, IF ELSE IF and SWITCH. While IF determines whether a certain branch of the program is executed or not, alternative branches to be executed are determined using IF ELSE, IF ELSE IF and SWITCH statements.
Complexity due to conditional statements depends on at least three factors,
- Number of variables examined to determine which branch is to be executed,
- Number of alternative branches to be selected from,
- Depth of nested conditional statements.
In each of the above mentioned cases, complexity arises due to the increase in the number of conditions a developer needs to consider to implement an algorithm correctly. Attempting to reduce complexity arising due to the number of variables examined by rearranging conditional expressions may, in certain cases, increase complexity by increasing the depth of conditional statements. For example, consider the following,
if (A && B){
doThis();
} else if (A && !B){
doThat();
} else {
throwAnException();
}
where A and B are conditional expressions that may also be considerably complex. This can, however, be rearranged as follows, introducing nesting,
if (A){
if (B){
doThis();
} else {
doThat();
}
} else {
throwAnException();
}
Historically, complexity in programs arising due to the number of conditional and iterative statements has been measured using the cyclomatic complexity metric [ McCabe1976 ]. As explained later in the article, cyclomatic complexity of a program module is directly related to the number of conditional and iterative statements within that module. It has also been argued that higher cyclomatic complexity leads to higher defects [ McCabeEtAl1989 ], [ Sharpe2008 ], lower cohesion [ SteinEtAl2005 ] and larger number of unit tests for greater code coverage [ WatsonEtAl1996 ].
This article uses a simple example to demonstrate the management of cyclomatic complexity through the application of design patterns [ GammaEtAl1995 ]. As conditional statements affect program behaviour, some behavioural patterns can help design and implement modules with lower complexities. These lower complexity modules are then connected appropriately to provide the required behaviour.
After discussing cyclomatic complexity and its use in software development, the article proceeds with an example of a class with moderate cyclomatic complexity. The class in the example is refactored to the Chain of Responsibility design pattern and later to the Strategy design pattern to show reduced cyclomatic complexity in the participating classes.
Cyclomatic complexity
Cyclomatic complexity measures the amount of decision logic in a program module as a function of the number of edges and nodes in a control flow graph representing that module. The following rules provide a simple mechanism to determine cyclomatic complexity of a module,
-
Each module without any control flow statements is assigned a complexity measure of 1. For example, the following method,
public static void main(String[] args){ int operand1 = Integer.parseInt(args[0]); int operand2 = Integer.parseInt(args[1]); int sum = operand1 + operand2; System.out.println( operand1 + "+" + operand2 + "=" + sum); } -
If there are only p binary predicates in a module, its cyclomatic complexity is p+1. For example, the cyclomatic complexity of the following method is 2.
public static int abs(int in){ int out = in; if (out < 0){ out = -1 * out; } return out; }Complexity is incremented for every boolean operator (e.g., AND, OR) in a predicate. For example, the cyclomatic complexity of the following method is 3.
public static boolean isSingleDigitPositive( int in){ boolean singleDigitPositiveFlag = false; if ((in >= 0) && (in < 10)){ singleDigitPositiveFlag = true; } return singleDigitPositiveFlag; } -
Cyclomatic complexity of multiway decisions is one less than the number of edges out of the decision node. For example, the cyclomatic complexity of the following method is 8. This includes 1 for method itself, 4 for the multiway if block (5 edges including the last else, i.e., the default edge) and 3 for logical AND operators.
public static double calculatePayment( int hoursParked){ double parkingCharge; if ((hoursParked >= 1) && (hoursParked < 3)){ parkingCharge = 1.25; } else if ((hoursParked >= 3) && ( hoursParked < 6)){ parkingCharge = 3.0; } else if ((hoursParked >= 6) && ( hoursParked < 12)){ parkingCharge = 7.5; } else if (hoursParked >= 12){ parkingCharge = 15.0; } else { parkingCharge = 0.75; } return parkingCharge; }
Because this measure is based on the decision structure of the code, it is completely independent of text formatting and is nearly independent of programming languages as they usually contain the same fundamental decision structures. Therefore, it can be applied uniformly across projects [ McCabeEtAl1989 ].
Cyclomatic complexity fundamentally focuses on the complexity of a module. It has been ascertained that number of tests required to test all the paths in a module is equal to the cyclomatic complexity of the module. It has been widely suggested that cyclomatic complexity greater than 10 results in modules with higher defect rates thus implying this as a threshold beyond which modules are considered complex [ Glover2006 ].
Integration complexity is a measure that provides the number of independent integration tests through an entire program but it depends on the cyclomatic complexities of component modules [ McCabeEtAl1989 ], [ WatsonEtAl1996 ]. While cyclomatic complexity of a particular module can be lowered by further modularisation, overall complexity may rise when considering integration complexity unless the process of modularisation produces a considerable number of common, reusable modules [ McCabeEtAl1989 ]. Inheritance and polymorphism in object oriented programs result in implicit control flow which is used to resolve dynamic method invocation (i.e., deciding the concrete implementation of an abstract method to be executed). This is considered to increase the cyclomatic complexity and the number of tests required to perform structured testing of a module containing a reference to an instance of a class [ WatsonEtAl1996 ]. However, in most circumstances, a program may reference only a segment of a particular class hierarchy, thereby only exercising a segment of the overall implicit control flow. It may, therefore, be practical to only consider cyclomatic complexity arising from the relevant segment of the implicit control flow and perform testing accordingly.
Lower cyclomatic complexity as a consequence of modularisation is desirable despite possibly increased integration complexity resulting in higher overall number of tests. This is because lower cyclomatic complexity results in higher cohesion and fewer anticipated defects within modules [SteinEtAl2005]. Therefore, this article discusses, through the application of design patterns, refactoring code with higher cyclomatic complexity into a structure where constituents have lower individual cyclomatic complexity.
Design patterns and their impact on cyclomatic complexity
A design pattern describes a solution to a recurring software engineering problem at the design level. Design patterns aim to promote reusability of successful designs and architectures. A design pattern is identified by a name, solves a particular problem, provides a general arrangement of components in a representative solution and describes the consequences of applying that pattern. Gamma et al have documented a catalogue of general purpose design patterns which are often referred to as GoF (Gang of Four) patterns [ GammaEtAl1995 ]. They classify these patterns on the basis of their purpose as well as scope. Purpose reflects what patterns do whereas scope specifies whether the pattern applies primarily to classes or objects.
Gamma et al suggest that patterns can have a creational, structural or behavioural purpose. Creational patterns provide mechanisms for object creation. Structural patterns suggest the composition of classes or objects. Behavioural patterns describe the interaction of classes or objects and the division of responsibilities among them.
Metsker et al provide an alternative and a finer grained classification of GoF patterns on the basis of their purpose. They suggest classifying GoF patterns on the basis of their intent into interface, responsibility, construction, operation and extension pattern classes [ MetskerEtAl2006 ]. Interface patterns provide convenient or appropriate interfaces to their respective implementations or to a collection or composition of objects. Responsibility patterns assign responsibility of operations to various objects and also define mechanisms to determine the objects in the system having the responsibility. Construction patterns define mechanisms to construct various objects. Operation patterns address the contexts in which more than one method is needed in a design to perform similar operations or variations of the same operation. Finally, extension patterns extend or vary the fundamental operation of an object.
Other classifications of GoF patterns are also possible. Table 1 lists GoF patterns with the two classifications mentioned above.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Table 1 |
Although design patterns focus on reusability and extensibility, most design patterns, particularly behavioural patterns, can assist in the reduction of cyclomatic complexity. This is accomplished by organising participants such that each solves a part of the problem resulting in simpler control flows within each participant hence lowering their cyclomatic complexity. Overall, each is more cohesive resulting in simpler testing. The GoF's description of some of the design patterns specifically mentions simplification of the control flow in the resulting solution (e.g., Strategy).
Example - arithmetic calculator
Listing 1 shows a Java class that performs basic arithmetic calculations. The main method of the program takes two operands separated by an operator. These are used by the calculate method to perform the operation related to the operator provided. The calculate method employs a switch statement to determine the branch that contains the statement to perform the required arithmetic operation. Cyclomatic complexity of the calculate method is 6.
package calc;
import java.lang.IllegalArgumentException;
public class Calculator {
public double calculate(double operand1,
double operand2, char operator){
double result = 0.0;
switch(operator){
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
if (Math.abs(operand2) > 0.0){
result = operand1 / operand2;
} else {
throw new ArithmeticException(
"Numerator is zero.");
}
break;
default:
throw new IllegalArgumentException(
operator + " unknown.");
}
return result;
}
public static void main(String[] args){
double operand1
= Double.parseDouble(args[0]);
double operand2
= Double.parseDouble(args[2]);
char operator = args[1].charAt(0);
double result = new Calculator().calculate(
operand1, operand2, operator);
System.out.println(operand1 + args[1]
+ operand2 + "=" + result);
}
}
|
| Listing 1 |
Refactoring arithmetic calculator using chain of responsibility
Chain of Responsibility consists of a chain of loosely coupled objects with responsibilities between objects kept specific and minimal. These include knowing the task they can perform and the next object in the chain to which a message can be propagated if they cannot process the message. Client objects need not know which object in the chain has to be sent a message to perform a particular task. Instead, clients only know of the object at the head of the chain and they send the message to it. That object processes the message if it can otherwise it passes it on to the next object in the chain.
The calculator shown in Listing 1 can be refactored into a Chain of Responsibility as shown in Figure 1. Four classes, Adder , Subtractor , Multiplier and Divider perform respective arithmetic operations (Listing 3). These classes inherit from an abstract base class Processor (Listing 2). An instance of a Processor 's subclass is an element in the Chain of Responsibility and maintains a reference ( successor ) to another object of one of its subclasses. An object of the Calculator class (Listing 4) acts as a client to an instance of a Processor 's subclass, which is the head of the chain.
|
| Figure 1 |
package calculator;
public abstract class Processor {
protected Processor successor;
public Processor(){
successor = null;
}
public void setSuccessor(Processor successor){
this.successor = successor;
}
protected abstract boolean canProcess(
char operator);
protected abstract double process(
double operand1, double operand2);
public double calculate(double operand1,
double operand2, char operator)
throws Exception {
double result;
if (canProcess(operator)){
result = process(operand1, operand2);
} else {
if (null != successor){
result = successor.calculate(
operand1, operand2, operator);
} else {
throw new Exception("No successor set");
}
}
return result;
}
}
|
| Listing 2 |
public class Adder extends Processor {
protected boolean canProcess(char operator) {
return operator == '+';
}
protected double process(double operand1,
double operand2) {
return operand1 + operand2;
}
}
public class Subtractor extends Processor {
protected boolean canProcess(char operator) {
return operator == '-';
}
protected double process(double operand1,
double operand2) {
return operand1 - operand2;
}
}
public class Multiplier extends Processor {
protected boolean canProcess(char operator) {
return operator == '*';
}
protected double process(double operand1,
double operand2) {
return operand1 * operand2;
}
}
public class Divider extends Processor {
protected boolean canProcess(char operator) {
return operator == '/';
}
protected double process(double operand1,
double operand2) {
double result;
if (Math.abs(operand2) > 0.0){
result = operand1/operand2;
} else {
throw new ArithmeticException(
"Divide by zero.");
}
return result;
}
}
|
| Listing 3 |
package calculator;
public class Calculator {
private Processor processor;
public Calculator(){
processor = null;
}
public void setProcessor(Processor processor){
this.processor = processor;
}
public double calculate(double operand1,
double operand2,
char operator) throws Exception{
return processor.calculate(operand1,
operand2, operator);
}
public static void main(String[] args){
Adder adder = new Adder();
Subtractor subtractor = new Subtractor();
Multiplier multiplier = new Multiplier();
Divider divider = new Divider();
adder.setSuccessor(subtractor);
subtractor.setSuccessor(multiplier);
multiplier.setSuccessor(divider);
Processor processor = adder;
Calculator calculator = new Calculator();
calculator.setProcessor(processor);
if (args.length != 3){
System.out.println(
"USAGE: java calculator operand1
operator operand2");
} else {
double operand1
= Double.parseDouble(args[0]);
double operand2
= Double.parseDouble(args[2]);
char operator = args[1].charAt(0);
try{
double result
= calculator.calculate(operand1,
operand2, operator);
System.out.println(operand1 + args[1]
+ operand2 + "=" + result);
} catch (Exception exp){
System.out.println(exp.toString());
}
}
}
}
|
| Listing 4 |
In the main method of the Calculator class, a chain of Adder , Subtractor , Multiplier and Divider instances are created with the Adder instance at the head of the chain. The Adder instance is then assigned to the processor attribute of the Calculator instance by passing it as a parameter to the setProcessor method on the Calculator instance. To perform a calculation, a Calculator instance calls the calculate method on the object referenced by its processor attribute. The calculate method calls the canProcess method to determine if that instance can perform the calculation. If it can, it calls the process method to perform the calculation and return the results. If it cannot and a successor exists in the chain (i.e., the value of the successor attribute is not null), it calls the calculate method on the successor.
In addition to Chain of Responsibility, Processor and its subclasses also implement the Template Method pattern. calculate method is a concrete method in the Processor base class. However, both canProcess and process methods are abstract methods, specialised implementations of which exist in the subclasses of Processor .
The code in listings 2 to 4 results in more classes than the code in listing 1 but these classes are more cohesive and have lower individual cyclomatic complexities. The cyclomatic complexities of all methods of Adder , Subtractor and Multiplier classes are 1 whereas that of the process method of the Divider class is 2. The cyclomatic complexities of all instance methods of the Calculator class are also 1. The main method of the Calculator class and the calculate method of the Processor class have the highest cyclomatic complexities of 3.
Although it may be argued that this exercise has increased the number of classes in the application, each of these classes is far less complex than the original program. Specialised behaviour of these classes allows developers to conveniently focus on the functionality of the class being developed and an extension to the application (e.g., a class to provide the remainder, i.e., modulus operation) only requires developing a new class and adding its instance to the end of the chain in the main method of the Calculator class. Techniques like dependency injection [ Fowler2004 ] allow creation of such chains via application configuration rather than directly in code. Furthermore, each class can be tested independently with simpler unit tests. These advantages, especially in more complicated applications (e.g., message handling in a communications application or update handling in a GUI based on the Observer pattern), may offset the increased integration complexity due to an increased number of classes in the application.
Refactoring arithmetic calculator using Strategy
The Strategy pattern allows the definition of a family of algorithms such that they are interchangeable within an application. Thus it lets algorithms vary independently from the clients that use it. Strategy is typically used to configure a class with one of many behaviours, when different variants of an algorithm are needed or when a class defines may behaviours and these appear as multiple conditional statements in its operations [ GammaEtAl1995 ].
Figure 2 is the class diagram of the calculator application implemented using a variation of the Strategy pattern. The Processor interface represents the abstract strategy in the application:
|
| Figure 2 |
package calculator;
public interface Processor {
double process(double operand1,
double operand2);
}
Its implementations, Adder , Subtractor , Multiplier and Divider (Listing 5) form concrete strategies for the application. Calculator class (Listing 6) is the context. However, it differs from the context in the GoF's description of the Strategy pattern as it contains a collection of concrete strategy instances from which it selects the appropriate strategy instance on the basis of the operation requested.
public class Adder implements Processor {
public double process(double operand1,
double operand2) {
return operand1 + operand2;
}
}
public class Subtractor implements Processor {
public double process(double operand1,
double operand2) {
return operand1 - operand2;
}
}
public class Multiplier implements Processor {
public double process(double operand1,
double operand2) {
return operand1 * operand2;
}
}
public class Divider implements Processor {
public double process(double operand1,
double operand2) {
double result;
if (Math.abs(operand2) > 0.0){
result = operand1/operand2;
} else {
throw new ArithmeticException(
"Divide by zero");
}
return result;
}
}
|
| Listing 6 |
package calculator;
import java.util.Map;
import java.util.TreeMap;
public class Calculator {
private Map<String, Processor> processors;
public Calculator(){
processors = new TreeMap<String,
Processor>();
processors.put("+", new Adder());
processors.put("-", new Subtractor());
processors.put("*", new Multiplier());
processors.put("/", new Divider());
}
public double calculate(double operand1,
double operand2,
String operator) throws Exception{
double result;
if (processors.containsKey(operator)){
result = processors.get(operator).process(
operand1, operand2);
} else {
throw new Exception(
"No processor for " + operator);
}
return result;
}
public static void main(String[] args){
if (args.length != 3){
System.out.println("Usage:java Calculator
<operand1> <operator> <operand2>");
} else {
double operand1
= Double.parseDouble(args[0]);
double operand2
= Double.parseDouble(args[2]);
Calculator calculator = new Calculator();
try{
double result = calculator.calculate(
operand1, operand2, args[1]);
System.out.println(operand1 + args[1]
+ operand2 + "=" + result);
} catch(Exception exp){
System.out.println(exp.toString());
}
}
}
}
|
| Listing 6 |
Adder , Subtractor , Multiplier and Divider (Listing 5) contain only one method, process . For Adder , Subtractor and Multiplier , this method has a cyclomatic complexity of 1 whereas for the Divider , it has a cyclomatic complexity of 2. The constructor of the Calculator class creates a mapping between arithmetic operators and instances of the corresponding implementations of the Processor interface (the processors attribute of the Calculator class). The calculate method determines, using the operator parameter, if an instance of an implementation of the Processor interface has been mapped to this operator. If such a mapping exists, that instance of the implementation of Processor interface is accessed and its process method called to perform the requested operation. If such a mapping does not exist, an exception is thrown. Cyclomatic complexity of the calculate method of the Calculator class is 2 whereas that of the main method is 3.
Like the Chain of Responsibility implementation of the calculator, this implementation also requires an initialisation step, which is performed in the constructor of the Calculator class. As mentioned earlier, this can also be delegated to a dependency injector. Individual classes are more cohesive than the original implementation of calculator which, as mentioned earlier, is usually preferred even at the cost of possible higher integration complexity.
Conclusions
The cyclomatic complexity of a program module is determined by examining the control flow within the module. It has been suggested that complicated control flows in a single module may also have an adverse impact on developers' productivity through cognitive overload [ Klemola2000 ]. Thus, quantification of cyclomatic complexity provides an opportunity to reduce module complexity by delegating parts of control flow to other modules. This leads to lower individual cyclomatic complexities with possibly higher integration complexity. However, reduction of cyclomatic complexity also leads to higher cohesion which is proven to be a key aspect of well designed software.
This article discusses the reduction of cyclomatic complexity in a method of a class through the application of design patterns. It has been demonstrated, with a simple example, that refactoring code with higher cyclomatic complexity using design patterns can lead to flexible, configurable and extensible systems. However, it can also be seen that such refactoring increases the structural complexity of the solution due to more number of resulting classes with possible coupling between them. Therefore, the application of these techniques may be more appropriate in systems where conditional statements allow selection from several elaborate and complex branches with a possibility of variation in these branches in the future versions of the system. This variation can be in the number of these branches as well as functionality within each branch. A typical example may be of a message receiver in a data communications application communicating many different types of messages. Each message type may be handled by a separate message handler. These message handlers can be arranged in a Chain of Responsibility or a Strategy. Not only is each message handler more cohesive but the resulting application is also extensible in handling newer message types.
References
[Fowler2004] M. Fowler (2004), 'Inversion of Control Containers and the Dependency Injection Pattern', http://martinfowler.com/articles/injection.html .
[GammaEtAl1995] E. Gamma, R. Helm, R. Johnson, J. Vlissides (1995), Design Patterns - Elements of Reusable Object Oriented Software, Pearson Education.
[Glover2006] A. Glover (2006), 'In Pursuit of Code Quality: Monitoring Cyclomatic Complexity', http://www.ibm.com/developerworks/java/library/j-cq03316/
[Klemola2000] T. Klemola (2000), 'A Cognitive Model for Complexity Metrics', Proceedings of the 4th International Workshop on Quantitative Approaches in Object Oriented Software Engineering.
[McCabe1976] T. J. McCabe (1976), 'A Complexity Measure', IEEE Transactions on Software Engineering, SE-2(4), December 1976, pp 308-320.
[McCabeEtAl1989] T. J. McCabe, C.W. Butler (1989), 'Design Complexity, Measurement and Testing', Communications of the ACM, December 1989, 32(12), pp 1415-1425.
[MetskerEtAl2006] S. J. Metsker, W. C. Wake (2006), Design Patterns in Java, Pearson Education.
[Sharpe2008] R. Sharpe (2008), McCabe 'Cyclomatic Complexity: The Proof in the Pudding', http://www.enerjy.com/blog/?p=198
[SteinEtAl2005] C. Stein, G. Cox, L. Etzkorn, S. Gholston, S. Virani, P. Farrington, D. Utley, J. Fortune (2005), 'Exploring the Relationship Between Cohesion and Complexity', Journal of Computer Science, 1(2), pp 137-144.
[WatsonEtAl1996] A.H. Watson, T.J. McCabe (1996), Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric, NIST (National Institute of Standards and Technology) Special Publication 500-235.
