Clang 插件计算圈复杂度

2020-3-17|最后更新: 2023-5-28|
type
status
date
slug
summary
tags
category
icon
password
notion image

圈复杂度

圈复杂度(Cyclomatic complexity,简写CC)也称为条件复杂度,是一种代码复杂度的衡量标准。由托马斯·J·麦凯布(Thomas J. McCabe, Sr.)于1976年提出,用来表示程序的复杂度,其符号为VG或是M。它可以用来衡量一个模块判定结构的复杂程度,数量上表现为独立现行路径条数,也可理解为覆盖所有的可能情况最少使用的测试用例数。圈复杂度大说明程序代码的判断逻辑复杂,可能质量低且难于测试和 维护。程序的可能错误和高的圈复杂度有着很大关系。
通俗得讲圈复杂度就是确定某一方法到达100%的覆盖率将需要多少条测试用例
References:

圈复杂度算法

点边计算法

计算公式
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布尔操作
  • ?:三元运算符
常见语句的控制流:
notion image
1、所有终点只计算一次,即便有多个return或者throw;
2、节点对应代码中的分支语句
使用Clang插件代码实现自动检测的话,我们使用节点计算法

小结

高复杂度的代码是否可维护性差 圈复杂度高的情况也并不是需要重构
复杂度相同的代码是否是一致的 圈复杂度相同的情况代码健康状况也不同
圈复杂度还需要具体情况具体分析,其只能作为重构的一个度量指标,作为决策的一个参考依据。
降低圈复杂度不在本文讨论范围,可以点击 降低圈复杂度方法 链接查看

Clang 插件逻辑

Clang命令集

  1. clang分析AST
    1. 使用命令:clang -Xclang -ast-dump -fsyntax-only xxx.m ,即可分析xxx.m 的 AST
      clang -Xclang -ast-dump -fsyntax-only jake.m
  1. clang-query作为clang的一个工具,可交互式检验Matcher正确性和有效性,可探索AST的结构和关系。
    1. ~/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
不可读
不可测
非常高
在模块编译完成后,将会在模块的结尾进行提示,类似形式如下:
notion image

思考

如下是一个圈复杂度大于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

Reference

PNG 图片的压缩原理被思绪戳穿的国庆节