AST（抽象语法树）分析用于C/C++ 源文件头文件对比_c++ ast

AST（抽象语法树）分析用于C/C++ 源文件头文件对比

本文主要设计了一个 基于AST解析的 函数声明&定义收集工具。

背景

在某项目中，需要收集项目中头文件中对函数的声明，以及收集源文件中对函数的实现，用于在代码层面判断源文件是否完全实现了所有函数声明。简单来说，假设A集合为头文件函数声明集合，B集为源文件函数定义集合，我们的目的是找出A与B的差集A-B。

分析与设计

我们程序要提供如下几个功能。

词法解析：C系列代码文本转化为对象

目的是将文件转化为某种便于访问的数据结构，比较成熟的技术是利用抽象语法树解析，也是编译期领域的前端编译技术。

一般的编译型语言的编译经历 词法分析、语法分析、语义分析、IR生成、代码优化、机器码生成 几个阶段。

其中词法分析的输入是CLike文件xxx.c/h/cpp，输出是一组token，一个token可以理解为一个代码元素，例如操作符token，关键字token，字面token（标识符、数字、字符串），特殊token等等。

其中语法分析的输入是token，输出是一颗树状结构的数据结构。是由没有语法意义的一个一个单词，按照一定的文法，转化为有层次结构，有一定语义的语法树的过程。

遍历语法树：寻找感兴趣的元素

语法分析的结果是一棵“树”（又称AST 抽象语法树），通常以组合模式的结构性设计模式保存，提供一种访问者模式的行为设计模式来遍历。

词法分析会给每个“树”的节点赋予特殊的含义，例如是可以是一个名称、一个声明、一个定义、一个表达式等等。

   -(函数定义)CPPASTFunctionDefinition (offset: 2421,774) -> int32
     -(返回值，类型声明符)CPPASTNamedTypeSpecifier (offset: 2421,7) -> int32_t
       -(具体类型)CPPASTName (offset: 2421,7) -> int32_t
     -(函数描述)CPPASTFunctionDeclarator (offset: 2429,146) -> HwKey
       -(函数名: 带::的名字)CPPASTQualifiedName (offset: 2429,36) -> HwKeystoreServiceClient::GenerateKey
         -CPPASTName (offset: 2429,23) -> HwKeystoreServiceClient
         -CPPASTName (offset: 2454,11) -> GenerateKey
       -(函数参数1)CPPASTParameterDeclaration (offset: 2466,20) -> const String16 &name
         -(函数参数类型)CPPASTNamedTypeSpecifier (offset: 2466,14) -> const String16
           -CPPASTName (offset: 2472,8) -> String16
         -(函数参数名)CPPASTDeclarator (offset: 2481,5) -> &name
           -CPPASTReferenceOperator (offset: 2481,1) -> &
           -CPPASTName (offset: 2482,4) -> name
       -CPPASTParameterDeclaration (offset: 2488,32) -> const KeymasterArguments &params
         -CPPASTNamedTypeSpecifier (offset: 2488,24) -> const KeymasterArguments
           -CPPASTName (offset: 2494,18) -> KeymasterArguments
         -CPPASTDeclarator (offset: 2513,7) -> &params
           -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) -> { 。。。（下省略）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

我们需要实现具体的访问者，来遍历到关心的元素。

抽取收集：针对特定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);
}
1
2
3
4
5
6

// 纯虚函数应当不扫描
class XXX{
	void funcName(int32_t , int32_t ) = 0;
}
1
2
3
4

问题2：类中类嵌套的层次关系问题如何表达

• 对于函数定义，由于语法要求必须写全QualifiedName，可以通过QualifiedName解析层次关系。

AAA::BBB::~CCC()
{
 
}
1
2
3
4

• 对于头文件内的函数声明，通常直接写在类里，需要通过while循环不断获取parent节点来得到层次关系。

class AAA {
public:
    class BBB : public XXX {
    public:
        virtual ~CCC();
    };
};
1
2
3
4
5
6
7

问题3： 函数指针被误识别为函数声明问题

// 这种并不是函数声明，需要识别出并排除这种情况
class XXX {
    int (*AAA)(const char *, uint8_t *, uint32_t );
}
1
2
3
4

问题4：头文件直接对函数进行inline实现

解决方法。1. 在.h中实现的函数定义，从header集合里去除。2. .h文件也加入到函数定义扫描中

class Arena {
 public:
  char* Allocate(size_t bytes);
};

inline char* Arena::Allocate(size_t bytes) {
  // 直接在头文件中实现
}

1
2
3
4
5
6
7
8
9

问题5： 默认返回值问题

// 默认返回值导致声明定义差异
{
				"signature":"Iterator*(const ReadOptions&, uint64_t, uint64_t, Table**=nullptr)",
				"simpleName":"NewIterator"
}
// 定义时不带返回值，可以把默认值去掉
{
				"signature":"Iterator*(const ReadOptions&, uint64_t, uint64_t, Table**)",
				"simpleName":"NewIterator"
}
1
2
3
4
5
6
7
8
9
10

问题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

1
2
3
4
5
6
7
8
9

7. 其他细节问题

数据结构：承载结果

UnitBean为类级别的单元，unitName为类名，每个UnitBean以Sorted方式保存了函数和类中类。
Method为函数级别单元，signature为函数签名，simpleName为函数名。

public class UnitBean {
    private String unitName;
    private SortedSet<Method> methods = new TreeSet<>();
    private SortedMap<String, UnitBean> classes = new TreeMap<>();
}

class Method implements Comparable<Method> {
    private String signature;
    private String simpleName;
}

1
2
3
4
5
6
7
8
9
10
11

输入输出：序列化、反序列化

采用fastjson方式序列化反序列化。技术比较成熟，不再赘述。

对于maven构建的工程，需要在pom文件中添加对fastjson的依赖。

对比能力：最终实现寻找差异

利用集合求差集的方式可以方便的求出差异。

程序设计图

整体UML如下图

AST数据结构：组合模式

利用eclipse-cdt分析CLike文件后，可得到组合模式构建的AST树。

收集数据行为：访问者模式

实现具体的函数声明访问者，函数实现访问者，用于收集关键数据。并写入存储数据结构。

存储数据结构

采用SortedSet的方式存储函数，SortedMap方式存储嵌套类。函数Method分为签名signature和名称simpleName。

函数抽取效果

红色：头文件中函数的抽取。

蓝色：源文件中函数的抽取。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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分析的源码定制化修复扩展方案