文章目录AST (抽象语法树)分析C/用于c源文件头文件比较背景分析和设计词法分析)从c系列代码文本到对象的转换语法树遍历)查找和收集感兴趣的元素)特定AST节点问题1 )参数的命名空间问题纯函数必须实现一点如何表现子层次关系问题3 :函数指针被误认为是函数声明问题4 :头文件直接inline实现函数问题5 :默认返回值问题6 :通过宏展开实现语法结构文件联动(include宏定义) )序列化、反序列化比较能力)最终寻找差异的程序设计图实现AST数据结构)组合模式收集数据行为)访问者模式积累数据结构函数提取效果参考资料官网非正式网站
抽象语法树(AST )分析用于比较C/C源文件头文件
本文主要设计了基于AST分析的函数声明定义采集工具。
在背景项目中，为了在代码级别确定源文件是否完全实现了所有函数声明，必须收集项目头文件中的函数声明，并收集源文件中的函数实现。 简单地说，将a集合作为头文件函数声明集合，将b集合作为源文件函数定义集合，以找出a和b的差集合A-B为目的。
分析和设计我们的程序需要提供以下功能。
词法分析：将c系列代码文本转换为对象的目的是将文件转换为易于访问的数据结构，比较成熟的技术是利用抽象语法树进行分析，也是编译期领域的前端编译技术。
常规编译型语言的编译历史记录词法分析，语法分析，语义分析，IR生成，33愚人节5
其中，代码优化的输入是CLike文件xxx.c/h/cpp，输出是一组token，token是操作员token、关键字token、字面上token (标识符
其中机器码生成的输入为token，输出为树形结构的数据结构。 这是一个从无语法意义的单词，按照一定的语法，转化为有层次、有一定意义的语法树的过程。
遍历语法树：查找感兴趣的元素并进行语法分析后，创建“树”(也称为AST抽象语法树)，通常以词法分析的结构设计模式保存，http://www.
词法分析为每个“树”节点提供特殊意义，如名称、声明、定义和表达式。
- (函数定义(offset :2421，774 )- int32 -)返回值，类型声明符) cppastnamedtypespecifier offset 33602421 7 )- int32_t -(具体类型(cppastname(offset:2421， 7 )- int32_t -(函数说明) cppastfunctiondeclarator ) offset33602429 146(-HWkey ) (命名为函数名：33603360 ) cppastqualifiedniednset 36 )-hwkeystoreserviceclient :3360 generate key-cppastname (offset 33602429， 23 )-hwkeystoreserviceclient-cppastname 11 )- GenerateKey -((函数参数1 ) cppastparameterdeclaration (offset 33602466 )， 20 )- const String16 name -)函数参数类型) cpastnamedtypeer 14 )-conststring 16-cppastname (offset :2472， 8 )- String16 -(函数参数名称) cppastdeclarator (offset :2481，5 )-name-cppastreferenceoperator (offset 33602481，1 ) 4 )-name-cpastparameterdereence 32 )-constkeymasterargumentsparams-cppastnamedtypespecifier (offset 33602488，24 )--
PPASTName (offset: 2494,18) -> KeymasterArguments -CPPASTDeclarator (offset: 2513,7) -> ¶ms -CPPASTReferenceOperator (offset: 2513,1) -> & -CPPASTName (offset: 2514,6) -> params -CPPASTParameterDeclaration (offset: 2527,7) -> int uid -CPPASTSimpleDeclSpecifier (offset: 2527,3) -> int -CPPASTDeclarator (offset: 2531,3) -> uid -CPPASTName (offset: 2531,3) -> uid -CPPASTParameterDeclaration (offset: 2536,38) -> KeyCharacteristics *outCharacteristics -CPPASTNamedTypeSpecifier (offset: 2536,18) -> KeyCharacteristics -CPPASTName (offset: 2536,18) -> KeyCharacteristics -CPPASTDeclarator (offset: 2555,19) -> *outCharacteristics -CPPASTPointer (offset: 2555,1) -> * -CPPASTName (offset: 2556,18) -> outCharacteristics -(函数体)CPPASTCompoundStatement (offset: 2577,618) -> { 。。。（下省略）我们需要实现具体的访问者，来遍历到关心的元素。
抽取收集：针对特定AST节点由于AST不好直接对比，并且有一些细节上的问题，我们不能直接拿AST做对比。需要由AST节点反向生成能够唯一表征这个函数的特征。
经过多次实验，采用ASTStringUtil.getSignatureString和ASTStringUtil.getQualifiedName、ASTStringUtil.getSimpleName三个接口获取函数签名，带::的函数名，和不带::的函数名。分别存储函数签名和函数名（这样1. 可以充分利用成熟API；2. 便于对比）。
这一步细节问题很多，例如
问题1：参数的命名空间问题，纯虚函数不一点要实现问题 // .h中大多需要指明namespace，.cpp中大多不需要指明，为了统一，需要去掉namespace// 可采用正则匹配`[0-9a-zA-Z_]+::`替换输出class XXX {public: static int32_t Del(const namespace::String16 &name, int uid);} // 纯虚函数应当不扫描class XXX{void funcName(int32_t , int32_t ) = 0;} 问题2：类中类嵌套的层次关系问题如何表达 对于函数定义，由于语法要求必须写全QualifiedName，可以通过QualifiedName解析层次关系。 AAA::BBB::~CCC(){ } 对于头文件内的函数声明，通常直接写在类里，需要通过while循环不断获取parent节点来得到层次关系。 class AAA {public: class BBB : public XXX { public: virtual ~CCC(); };}; 问题3： 函数指针被误识别为函数声明问题 // 这种并不是函数声明，需要识别出并排除这种情况class XXX { int (*AAA)(const char *, uint8_t *, uint32_t );} 问题4：头文件直接对函数进行inline实现解决方法。1. 在.h中实现的函数定义，从header集合里去除。2. .h文件也加入到函数定义扫描中
class Arena { public: char* Allocate(size_t bytes);};inline char* Arena::Allocate(size_t bytes) { // 直接在头文件中实现} 问题5： 默认返回值问题 // 默认返回值导致声明定义差异{"signature":"Iterator*(const ReadOptions&, uint64_t, uint64_t, Table**=nullptr)","simpleName":"NewIterator"}// 定义时不带返回值，可以把默认值去掉{"signature":"Iterator*(const ReadOptions&, uint64_t, uint64_t, Table**)","simpleName":"NewIterator"} 问题6：宏展开导致语法结构，不做文件联动(include宏定义)无法解析 // 其中GUARDED_BY定义在另外的文件里uint64_t logfile_number_ GUARDED_BY(mutex_);// GUARDED_BY定义位置#ifndef GUARDED_BY#define GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))#endif 其他细节问题 数据结构：承载结果UnitBean为类级别的单元，unitName为类名，每个UnitBean以Sorted方式保存了函数和类中类。
Method为函数级别单元，signature为函数签名，simpleName为函数名。
采用fastjson方式序列化反序列化。技术比较成熟，不再赘述。
对于maven构建的工程，需要在pom文件中添加对fastjson的依赖。
对比能力：最终实现寻找差异利用集合求差集的方式可以方便的求出差异。
程序设计图整体UML如下图
AST数据结构：组合模式利用eclipse-cdt分析CLike文件后，可得到组合模式构建的AST树。
收集数据行为：访问者模式实现具体的函数声明访问者，函数实现访问者，用于收集关键数据。并写入存储数据结构。
存储数据结构采用SortedSet的方式存储函数，SortedMap方式存储嵌套类。函数Method分为签名signature和名称simpleName。
AST数据结构：组合模式 收集数据行为：访问者模式 存储数据结构 <<Data>> UnitBean - unitName : type = String - methods : type = SortedSet< Method > - classes : type = SortedMap<String, UnitBean > <<Data>> Method - signature : type = String - simpleName : type = String org.eclipse.cdt.core.dom.ast. ASTVisitor + visit(IASTName) + visit(IASTDeclaration) + … AstVisitorBase - unitBean: type = UnitBead AstVisitorOfDefinition + visit(IASTDeclaration) IASTTranslationUnit + accept(ASTVisitor) <<interface>> IASTNode + accept( ASTVisitor ) LeafNode + accept( ASTVisitor ) Composite - children : IASTNode [] + accept(ASTVisitor) AstVisitorOfDeclaration + visit(IASTDeclaration)
函数抽取效果红色：头文件中函数的抽取。
蓝色：源文件中函数的抽取。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qs3DNkf2-1615776467805)(decoupling_ast.assets/result.PNG)]
参考资料 官网eclipse的CDT官网 ：Eclipse官网
LSU大学的eclipse-cdt的文档 : API文档类
How to useASTRewriteinorg.eclipse.jdt.core.dom.rewrite ：在如何使用AST的复写(rewrite)功能。
非官网Clang 中 AST 相关类简介（不定时更新）：Clang工具解析AST的介绍。
Eclipse中的CDT解析C++/C的简单使用
golang数据结构可视化分析
基于AST分析的源码定制化修复扩展方案