本文屬于Java ASM系列三：Tree API當中的一篇。
1. Cyclomatic Complexity
Code complexity is important, yet difficult metric to measure.
One of the most relevant complexity measurement is the Cyclomatic Complexity(CC).
1.1. 直觀視角
CC value can be calculated by measuring the number of independent execution paths of a program.
下面的HelloWorld類的test方法的復雜度是1。
public class HelloWorld { public void test() { System.out.println("Hello World"); }}其control flow graph如下：
┌───────────────────────────────────┐│ getstatic System.out ││ ldc "Hello World" ││ invokevirtual PrintStream.println ││ return │└───────────────────────────────────┘下面的HelloWorld類的test方法的復雜度是2。
public class HelloWorld { public void test(boolean flag) { if (flag) { System.out.println("flag is true"); } else { System.out.println("flag is false"); } }}其control flow graph如下：
┌───────────────────────────────────┐│ iload_1 ││ ifeq L0 ├───┐└─────────────────┬─────────────────┘ │ │ │┌─────────────────┴─────────────────┐ ││ getstatic System.out │ ││ ldc "flag is true" │ ││ invokevirtual PrintStream.println │ ││ goto L1 ├───┼──┐└───────────────────────────────────┘ │ │ │ │┌───────────────────────────────────┐ │ ││ L0 ├───┘ ││ getstatic System.out │ ││ ldc "flag is false" │ ││ invokevirtual PrintStream.println │ │└─────────────────┬─────────────────┘ │ │ │┌─────────────────┴─────────────────┐ ││ L1 ├──────┘│ return │└───────────────────────────────────┘下面的HelloWorld類的test方法的復雜度是3。
public class HelloWorld { public void test(boolean flag, boolean flag2) { if (flag && flag2) { System.out.println("both flags are true"); } else { System.out.println("one flag must be false"); } }}其control flow graph如下：
┌───────────────────────────────────┐│ iload_1 ││ ifeq L0 ├───┐└─────────────────┬─────────────────┘ │ │ │┌─────────────────┴─────────────────┐ ││ iload_2 │ ││ ifeq L0 ├───┼──┐└─────────────────┬─────────────────┘ │ │ │ │ │┌─────────────────┴─────────────────┐ │ ││ getstatic System.out │ │ ││ ldc "both flags are true" │ │ ││ invokevirtual PrintStream.println │ │ ││ goto L1 ├───┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ ││ L0 ├───┴──┘ ││ getstatic System.out │ ││ ldc "one flag must be false" │ ││ invokevirtual PrintStream.println │ │└─────────────────┬─────────────────┘ │ │ │┌─────────────────┴─────────────────┐ ││ L1 ├─────────┘│ return │└───────────────────────────────────┘下面的HelloWorld類的test方法的復雜度是4。
public class HelloWorld { public void test(int value) { String result; switch (value) { case 10: result = "val = 1"; break; case 20: result = "val = 2"; break; case 30: result = "val = 3"; break; default: result = "val is unknown"; } System.out.println(result); }}其control flow graph如下：
┌───────────────────────────────────┐│ iload_1 ││ lookupswitch { ││ 10: L0 ││ 20: L1 ││ 30: L2 ││ default: L3 ││ } ├───┐└───────────────────────────────────┘ │ │┌───────────────────────────────────┐ ││ L0 ├───┤│ ldc "val = 1" │ ││ astore_2 │ ││ goto L4 ├───┼──┐└───────────────────────────────────┘ │ │ │ │┌───────────────────────────────────┐ │ ││ L1 ├───┤ ││ ldc "val = 2" │ │ ││ astore_2 │ │ ││ goto L4 ├───┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ ││ L2 ├───┤ │ ││ ldc "val = 3" │ │ │ ││ astore_2 │ │ │ ││ goto L4 ├───┼──┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ │ ││ L3 ├───┘ │ │ ││ ldc "val is unknown" │ │ │ ││ astore_2 │ │ │ │└─────────────────┬─────────────────┘ │ │ │ │ │ │ │┌─────────────────┴─────────────────┐ │ │ ││ L4 ├──────┴──┴──┘│ getstatic System.out ││ aload_2 ││ invokevirtual PrintStream.println ││ return │└───────────────────────────────────┘下面的HelloWorld類的test方法的復雜度是5。
public class HelloWorld { public void test(int i) { String result = i % 2 == 0 ? "a" : i % 3 == 0 ? "b" : i % 5 == 0 ? "c" : i % 7 == 0 ? "d" : "e"; System.out.println(result); }}其control flow graph如下：
┌───────────────────────────────────┐│ iload_1 ││ iconst_2 ││ irem ││ ifne L0 ├───┐└─────────────────┬─────────────────┘ │ │ │┌─────────────────┴─────────────────┐ ││ ldc "a" │ ││ goto L1 ├───┼──┐└───────────────────────────────────┘ │ │ │ │┌───────────────────────────────────┐ │ ││ L0 ├───┘ ││ iload_1 │ ││ iconst_3 │ ││ irem │ ││ ifne L2 ├──────┼──┐└─────────────────┬─────────────────┘ │ │ │ │ │┌─────────────────┴─────────────────┐ │ ││ ldc "b" │ │ ││ goto L1 ├──────┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ ││ L2 ├──────┼──┘ ││ iload_1 │ │ ││ iconst_5 │ │ ││ irem │ │ ││ ifne L3 ├──────┼─────┼──┐└─────────────────┬─────────────────┘ │ │ │ │ │ │ │┌─────────────────┴─────────────────┐ │ │ ││ ldc "c" │ │ │ ││ goto L1 ├──────┼─────┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ │ ││ L3 ├──────┼─────┼──┘ ││ iload_1 │ │ │ ││ bipush 7 │ │ │ ││ irem │ │ │ ││ ifne L4 ├──────┼─────┼─────┼──┐└─────────────────┬─────────────────┘ │ │ │ │ │ │ │ │ │┌─────────────────┴─────────────────┐ │ │ │ ││ ldc "d" │ │ │ │ ││ goto L1 ├──────┼─────┼─────┼──┼──┐└───────────────────────────────────┘ │ │ │ │ │ │ │ │ │ │┌───────────────────────────────────┐ │ │ │ │ ││ L4 ├──────┼─────┼─────┼──┘ ││ ldc "e" │ │ │ │ │└─────────────────┬─────────────────┘ │ │ │ │ │ │ │ │ │┌─────────────────┴─────────────────┐ │ │ │ ││ L1 ├──────┴─────┴─────┴─────┘│ astore_2 ││ getstatic System.out ││ aload_2 ││ invokevirtual PrintStream.println ││ return │└───────────────────────────────────┘1.2. 數學視角
The complexity M is then defined as
M = E - N + 2Pwhere
E= the number of edges of the graph.N= the number of nodes of the graph.P= the number of connected components.
For a single program, P is always equal to 1. So a simpler formula for a single subroutine is
M = E - N + 21.3. 復雜度分級
The complexity level affects the testability of the code, the higher the CC, the higher the difficulty to implement pertinent tests.
In fact, the cyclomatic complexity value shows exactly the number of test cases needed to achieve a 100% branches coverage score.
Some common values used by static analysis tools are shown below:
1-4: low complexity – easy to test5-7: moderate complexity – tolerable8-10: high complexity – refactoring should be considered to ease testing11+ very high complexity – very difficult to test
Generally speaking, a code with a value higher than 11 in terms of CC, is considered very complex, and difficult to test and maintain.
2. 示例：計算圈復雜度
2.1. 預期目標
假如有一個HelloWorld類，代碼如下：
public class HelloWorld { public void test(int val) { if (val == 0) { System.out.println("val is 0"); } else if (val == 1) { System.out.println("val is 1"); } else { System.out.println("val is unknown"); } }}我們的預期目標：確定test方法的復雜度。
2.2. 編碼實現
在下面的CyclomaticComplexityFrame類當中，關鍵點是定義了一個successors字段，用來記錄當前Frame與其它Frame之間的關聯關系。
import org.objectweb.asm.tree.analysis.Frame;import org.objectweb.asm.tree.analysis.Value;import java.util.HashSet;import java.util.Set;public class CyclomaticComplexityFrame extends Frame { public Set> successors = new HashSet<>(); public CyclomaticComplexityFrame(int numLocals, int numStack) { super(numLocals, numStack); } public CyclomaticComplexityFrame(Frame frame) { super(frame); }} 在下面的CyclomaticComplexityAnalyzer類當中，從兩點來把握：
- 第一點，兩個
newFrame方法是用來替換掉默認的Frame類，而使用上面定義的CyclomaticComplexityFrame類。 - 第二點，修改
newControlFlowEdge方法，記錄Frame之間的關聯關系。
import org.objectweb.asm.tree.analysis.*;public class CyclomaticComplexityAnalyzer extends Analyzer { public CyclomaticComplexityAnalyzer(Interpreter interpreter) { super(interpreter); } @Override protected Frame newFrame(int numLocals, int numStack) { return new CyclomaticComplexityFrame<>(numLocals, numStack); } @Override protected Frame newFrame(Frame frame) { return new CyclomaticComplexityFrame<>(frame); } @Override protected void newControlFlowEdge(int insnIndex, int successorIndex) { CyclomaticComplexityFrame frame = (CyclomaticComplexityFrame) getFrames()[insnIndex]; frame.successors.add((CyclomaticComplexityFrame) getFrames()[successorIndex]); }} 在下面的CyclomaticComplexity類當中，應用M = E - N + 2公式：
import org.objectweb.asm.tree.MethodNode;import org.objectweb.asm.tree.analysis.*;public class CyclomaticComplexity { public static int getCyclomaticComplexity(String owner, MethodNode mn) throws AnalyzerException { // 第一步，獲取Frame信息 Analyzer analyzer = new CyclomaticComplexityAnalyzer<>(new BasicInterpreter()); Frame[] frames = analyzer.analyze(owner, mn); // 第二步，計算復雜度 int edges = 0; int nodes = 0; for (Frame frame : frames) { if (frame != null) { edges += ((CyclomaticComplexityFrame) frame).successors.size(); nodes += 1; } } return edges - nodes + 2; }} 2.3. 進行分析
public class HelloWorldAnalysisTree { public static void main(String[] args) throws Exception { String relative_path = "sample/HelloWorld.class"; String filepath = FileUtils.getFilePath(relative_path); byte[] bytes = FileUtils.readBytes(filepath); //（1）構建ClassReader ClassReader cr = new ClassReader(bytes); //（2）生成ClassNode int api = Opcodes.ASM9; ClassNode cn = new ClassNode(api); int parsingOptions = ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES; cr.accept(cn, parsingOptions); //（3）進行分析 String className = cn.name; List methods = cn.methods; for (MethodNode mn : methods) { int complexity = CyclomaticComplexity.getCyclomaticComplexity(className, mn); String line = String.format("%s:%s%n complexity: %d", mn.name, mn.desc, complexity); System.out.println(line); } }} 2.4. 驗證結果
:()V complexity: 1test:(I)V complexity: 3 另外，要說明一點，Cyclomatic Complexity計算的是return的復雜度。
下面的HelloWorld類的test方法的復雜度是2。
public class HelloWorld { public void test(int val) { if (val == 0) { System.out.println("val is 0"); } else if (val == 1) { throw new RuntimeException("val is 1"); // 注意，這里拋出異常 } else { System.out.println("val is unknown"); } }}下面的HelloWorld類的test方法的復雜度是1。
public class HelloWorld { public void test(int val) { if (val == 0) { System.out.println("val is 0"); } else if (val == 1) { throw new RuntimeException("val is 1"); // 注意，這里拋出異常 } else { throw new RuntimeException("val is unknown"); // 注意，這里拋出異常 } }}3. 總結
本文內容總結如下：
- 第一點，介紹Cyclomatic Complexity的概念，如何用數學公式表達，以及復雜度分級。
- 第二點，代碼示例，如何使用Java ASM實現Cyclomatic Complexity計算。
