Toward recursion aware complexity metrics

Abstract

Context: Software developers spend a significant amount of time on reading, comprehending, and debugging of source code. Numerous software metrics can give us awareness of incomprehensible functions or of flaws in their collaboration. Invocation chains, especially recursive ones, affect solution complexity, readability, and understandability. Even though decomposed and recursive solutions are characterized as short and clear in comparison with iterative ones, they hide the complexity of the observed problem and solution. As the collaboration between functions can strongly depend on context, difficulties are usually detected in debugging, testing or by static analysis, while metrics support is still very weak.Objective: We introduce a new complexity metric, called Overall Path Complexity (OPC), which is aware of (recursive) call chains in the observed source code. As invocations are basic collaboration mechanism and recursions are broadly accepted, the OPC metric is intended to be applicable independently on programming language and paradigm.Method: We propose four different versions of the OPC calculation algorithm and explore and discuss their suitability. We have validated proposed metrics based on a Framework specially designed for evaluation and validation of software complexity metrics and accordingly performed theoretical, empirical and practical validation. Practical validation was performed on toy examples and industrial cases (47012 LOCs, 2899 functions, and 758 recursive paths) written in Erlang.Result: Based on our analysis we selected the most suitable (of 4 proposed) OPC calculation formula, and showed that the new metric expresses advanced properties of the software in comparison with other available metrics that was confirmed by low correlation.Conclusion: We introduced the OPC metric calculated on the Overall Control Flow Graph as an extension of Cyclomatic Complexity by adding awareness of (recursive) invocations. The values of the new metric can lead us to find the problematic fragments of the code or of the execution paths.