本文屬于Java ASM系列三：Tree API當(dāng)中的一篇。
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類(lèi)的test方法的復(fù)雜度是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類(lèi)的test方法的復(fù)雜度是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類(lèi)的test方法的復(fù)雜度是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類(lèi)的test方法的復(fù)雜度是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類(lèi)的test方法的復(fù)雜度是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. 數(shù)學(xué)視角
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. 復(fù)雜度分級(jí)
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. 示例：計(jì)算圈復(fù)雜度
2.1. 預(yù)期目標(biāo)
假如有一個(gè)HelloWorld類(lèi)，代碼如下：
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"); } }}我們的預(yù)期目標(biāo)：確定test方法的復(fù)雜度。
2.2. 編碼實(shí)現(xiàn)
在下面的CyclomaticComplexityFrame類(lèi)當(dāng)中，關(guān)鍵點(diǎn)是定義了一個(gè)successors字段，用來(lái)記錄當(dāng)前Frame與其它Frame之間的關(guān)聯(lián)關(guān)系。
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類(lèi)當(dāng)中，從兩點(diǎn)來(lái)把握：
- 第一點(diǎn)，兩個(gè)
newFrame方法是用來(lái)替換掉默認(rèn)的Frame類(lèi)，而使用上面定義的CyclomaticComplexityFrame類(lèi)。 - 第二點(diǎn)，修改
newControlFlowEdge方法，記錄Frame之間的關(guān)聯(lián)關(guān)系。
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類(lèi)當(dāng)中，應(yīng)用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); // 第二步，計(jì)算復(fù)雜度 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. 進(jìn)行分析
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）構(gòu)建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）進(jìn)行分析 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. 驗(yàn)證結(jié)果
:()V complexity: 1test:(I)V complexity: 3 另外，要說(shuō)明一點(diǎn)，Cyclomatic Complexity計(jì)算的是return的復(fù)雜度。
下面的HelloWorld類(lèi)的test方法的復(fù)雜度是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類(lèi)的test方法的復(fù)雜度是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. 總結(jié)
本文內(nèi)容總結(jié)如下：
- 第一點(diǎn)，介紹Cyclomatic Complexity的概念，如何用數(shù)學(xué)公式表達(dá)，以及復(fù)雜度分級(jí)。
- 第二點(diǎn)，代碼示例，如何使用Java ASM實(shí)現(xiàn)Cyclomatic Complexity計(jì)算。
