type
status
date
slug
summary
tags
category
icon
password
圈复杂度
圈复杂度(Cyclomatic complexity,简写CC)也称为条件复杂度,是一种代码复杂度的衡量标准。由托马斯·J·麦凯布(Thomas J. McCabe, Sr.)于1976年提出,用来表示程序的复杂度,其符号为VG或是M。它可以用来衡量一个模块判定结构的复杂程度,数量上表现为独立现行路径条数,也可理解为覆盖所有的可能情况最少使用的测试用例数。圈复杂度大说明程序代码的判断逻辑复杂,可能质量低且难于测试和 维护。程序的可能错误和高的圈复杂度有着很大关系。通俗得讲圈复杂度就是确定某一方法到达100%的覆盖率将需要多少条测试用例
References:
- McCabe (December 1976). “A Complexity Measure”.IEEE Transactions on Software Engineering: 308–320http://www.literateprogramming.com/mccabe.pdf
圈复杂度算法
点边计算法
计算公式
V(G) = e – n + 2 * p
e:控制流图中边的数量(对应代码中顺序结构的部分)n:代表在控制流图中的判定节点数量,包括起点和终点(对应代码中的分支语句)ps:所有终点只计算一次,即使有多个 return 或者 throw
p:独立组件的个数
节点计算法
圈复杂度实际上就是等于判定节点的数量再加上1,也即控制流图的区域数,对应的计算公式为:
V (G) = P + 1
其中P为判定节点数,判定节点举例:
- if语句
- while语句
- for语句
- case语句
- catch语句
- and和or布尔操作
- ?:三元运算符
常见语句的控制流:
1、所有终点只计算一次,即便有多个return或者throw;
2、节点对应代码中的分支语句
使用Clang插件代码实现自动检测的话,我们使用节点计算法
小结
如高复杂度的代码是否可维护性差 圈复杂度高的情况也并不是需要重构
如复杂度相同的代码是否是一致的 圈复杂度相同的情况代码健康状况也不同
圈复杂度还需要具体情况具体分析,其只能作为重构的一个度量指标,作为决策的一个参考依据。
降低圈复杂度不在本文讨论范围,可以点击 降低圈复杂度方法 链接查看
Clang 插件逻辑
Clang命令集
- clang分析AST
使用命令:
clang -Xclang -ast-dump -fsyntax-only xxx.m
,即可分析xxx.m 的 ASTclang -Xclang -ast-dump -fsyntax-only jake.m
- clang-query作为clang的一个工具,可交互式检验Matcher正确性和有效性,可探索AST的结构和关系。
~/clang-llvm/build/bin/clang-query jake.m
Clang 圈复杂度算法实现
文中的两种圈复杂度计算方法,点边计算对人更加直观,不过在代码中实现,用节点计算法对计算机而言才是更直观的方法。
V (G) = P + 1
只需要统计一个模块(函数)中所有P出现的次数,具体在Clang中可以重载
RecursiveASTVisitor
类(此类用于搜索整个AST,并访问每一个节点),然后重载里面的这些方法bool VisitIfStmt(clang::IfStmt *stmt); bool VisitForStmt(clang::ForStmt *stmt); bool VisitObjCForCollectionStmt(clang::ObjCForCollectionStmt *stmt); bool VisitWhileStmt(clang::WhileStmt *stmt); bool VisitDoStmt(clang::DoStmt *stmt); bool VisitCaseStmt(clang::CaseStmt *stmt); bool VisitObjCAtCatchStmt(clang::ObjCAtCatchStmt *stmt); bool VisitCXXCatchStmt(clang::CXXCatchStmt *stmt); bool VisitConditionalOperator(clang::ConditionalOperator *op); bool VisitBinaryOperator(clang::BinaryOperator *op);
在重载的方法内对此模块中节点P的次数进行一次累加并返回true,如:
bool VisitIfStmt(clang::IfStmt *stmt) { _count++; return true; }
遍历一次模块语法树之后获得此模块的圈复杂度值,再在另一个
RecursiveASTVisitor
类中进行判断,一般圈复杂度不要超过10,以下规范来自网络仅做参考圈复杂度 | 代码状况 | 可测性 | 维护成本 |
1-10 | 清晰、结构化 | 高 | 低 |
10-20 | 复杂 | 中 | 中 |
20-30 | 非常复杂 | 低 | 高 |
30 | 不可读 | 不可测 | 非常高 |
在模块编译完成后,将会在模块的结尾进行提示,类似形式如下:
思考
如下是一个圈复杂度大于10的AST语法树示例:
CompoundStmt 0x7ff7f2898788 |-CallExpr 0x7ff7f289af60 'void' | |-ImplicitCastExpr 0x7ff7f289af48 'void (*)(id, ...)' <FunctionToPointerDecay> | | `-DeclRefExpr 0x7ff7f289ae60 'void (id, ...)' Function 0x7ff7f2055540 'NSLog' 'void (id, ...)' | `-ImplicitCastExpr 0x7ff7f289af88 'id':'id' <BitCast> | `-ObjCStringLiteral 0x7ff7f289aed0 'NSString *' | `-StringLiteral 0x7ff7f289aeb8 'char [1]' lvalue "" |-DeclStmt 0x7ff7f289b040 | `-VarDecl 0x7ff7f289afb8 used num 'int' cinit | `-IntegerLiteral 0x7ff7f289b020 'int' 0 |-IfStmt 0x7ff7f289b238 has_else | |-BinaryOperator 0x7ff7f289b0c8 'int' '==' | | |-ImplicitCastExpr 0x7ff7f289b0b0 'int' <LValueToRValue> | | | `-DeclRefExpr 0x7ff7f289b058 'int' lvalue Var 0x7ff7f289afb8 'num' 'int' | | `-IntegerLiteral 0x7ff7f289b090 'int' 0 | |-CompoundStmt 0x7ff7f289b1d8 | | `-IfStmt 0x7ff7f289b1c0 | | |-BinaryOperator 0x7ff7f289b158 'int' '==' | | | |-ImplicitCastExpr 0x7ff7f289b140 'int' <LValueToRValue> | | | | `-DeclRefExpr 0x7ff7f289b0e8 'int' lvalue Var 0x7ff7f289afb8 'num' 'int' | | | `-UnaryOperator 0x7ff7f289b128 'int' prefix '-' | | | `-IntegerLiteral 0x7ff7f289b108 'int' 1 | | `-CompoundStmt 0x7ff7f289b1a8 | | `-ReturnStmt 0x7ff7f289b198 | | `-IntegerLiteral 0x7ff7f289b178 'int' 0 | `-CompoundStmt 0x7ff7f289b220 | `-ReturnStmt 0x7ff7f289b210 | `-IntegerLiteral 0x7ff7f289b1f0 'int' 0 |-DeclStmt 0x7ff7f289b300 | `-VarDecl 0x7ff7f289b278 used index 'int' cinit | `-IntegerLiteral 0x7ff7f289b2e0 'int' 0 |-SwitchStmt 0x7ff7f289b368 | |-ImplicitCastExpr 0x7ff7f289b350 'int' <LValueToRValue> | | `-DeclRefExpr 0x7ff7f289b318 'int' lvalue Var 0x7ff7f289b278 'index' 'int' | `-CompoundStmt 0x7ff7f2898700 | |-CaseStmt 0x7ff7f289b3c0 | | |-ConstantExpr 0x7ff7f289b3a8 'int' | | | `-IntegerLiteral 0x7ff7f289b388 'int' 1 | | `-BreakStmt 0x7ff7f289b3e8 | |-CaseStmt 0x7ff7f2898438 | | |-ConstantExpr 0x7ff7f2898420 'int' | | | `-IntegerLiteral 0x7ff7f2898400 'int' 2 | | `-BreakStmt 0x7ff7f2898460 | |-CaseStmt 0x7ff7f28984a0 | | |-ConstantExpr 0x7ff7f2898488 'int' | | | `-IntegerLiteral 0x7ff7f2898468 'int' 3 | | `-BreakStmt 0x7ff7f28984c8 | |-CaseStmt 0x7ff7f2898508 | | |-ConstantExpr 0x7ff7f28984f0 'int' | | | `-IntegerLiteral 0x7ff7f28984d0 'int' 4 | | `-BreakStmt 0x7ff7f2898530 | |-CaseStmt 0x7ff7f2898570 | | |-ConstantExpr 0x7ff7f2898558 'int' | | | `-IntegerLiteral 0x7ff7f2898538 'int' 5 | | `-BreakStmt 0x7ff7f2898598 | |-CaseStmt 0x7ff7f28985d8 | | |-ConstantExpr 0x7ff7f28985c0 'int' | | | `-IntegerLiteral 0x7ff7f28985a0 'int' 6 | | `-BreakStmt 0x7ff7f2898600 | |-CaseStmt 0x7ff7f2898640 | | |-ConstantExpr 0x7ff7f2898628 'int' | | | `-IntegerLiteral 0x7ff7f2898608 'int' 7 | | `-BreakStmt 0x7ff7f2898668 | |-CaseStmt 0x7ff7f28986a8 | | |-ConstantExpr 0x7ff7f2898690 'int' | | | `-IntegerLiteral 0x7ff7f2898670 'int' 8 | | `-BreakStmt 0x7ff7f28986d0 | `-DefaultStmt 0x7ff7f28986e0 | `-BreakStmt 0x7ff7f28986d8 `-ReturnStmt 0x7ff7f2898778 `-IntegerLiteral 0x7ff7f2898758 'int' 0
其源码为:
- (int)func { NSLog(@""); int num = 0; if (num == 0) { if (num == -1) { return 0; } } else { return 0; } int index = 0; switch (index) { case 1: break; case 2: break; case 3: break; case 4: break; case 5: break; case 6: break; case 7: break; case 8: break; default: break; } return 0; }
Pod 集成
pod 'TYCCDetector', '0.0.1', :configuration => 'Debug' post_install do |installer| installer.pods_project.targets.each do |target| installer.development_pod_targets().each do |dp_target| if target.name == dp_target.name target.build_configurations.each do |config| config.build_settings["COMPILER_INDEX_STORE_ENABLE"] = 'NO' config.build_settings["OTHER_CFLAGS"] = '-Xclang -load -Xclang $(SRCROOT)/TYCCDetector/TYCCDetector/Clang/lib/CCDetector.dylib -Xclang -add-plugin -Xclang CCDetector' config.build_settings["CC"] = "$(SRCROOT)/TYCCDetector/TYCCDetector/Clang/bin/clang" config.build_settings["CXX"] = "$(SRCROOT)/TYCCDetector/TYCCDetector/Clang/bin/clang++"end end end end end