[转载] AST 获取和分析：Clang And Tree-sitter
前言
本文不仅介绍了如何使用各类 AST 分析工具，还简单分析了各类工具的工作原理，大家可以按需阅读。其中基于 Clang 的 AST 分析工具的工作原理结合源码一起食用效果更佳。文章主要围绕下面几个方向展开:
初探 AST
基于 Clang 获取分析 AST
基于 Tree-sitter 获取分析 AST
总结
初探 AST
AST 是什么
AST（Abstract Syntax Tree）抽象语法树是编译执行过程中必不可少的中间产物：
AST 是源代码语法结构的一种抽象表示。它以树状的结构表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法树是”抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。但是 AST 也描述了源代码的基本信息。
下面用一个简单的例子来理解基于 Clang 获取到的 AST 及 AST 包含的信息：准备一个最简单的 C 代码文件 text.c ：
1 | int someFunc(int x) { |
然后执行下面指令获取 text.c 的 AST:
1 | Clang -XClang -ast-dump -fsyntax-only test.c |
根节点是
TranslationUnit，其余节点均是该节点的的子节点TypedefDecl描述了通过typedef关键字定义的类型声明FunctionDecl及其子节点描述一个方法，其中<../test.cpp:1:1, line:4:1>描述方法所属文件、行号范围；紧随的line:1:5 someFunc 'int (int)'描述了方法名的位置、方法名、方法的类型（返回值和参数类型）子节点
ParmVarDecl描述了方法参数的位置、名称、类型子节点
CompoundStmt及其子节点描述方法实现DeclStmt及其子节点描述了方法体的位置和详细信息ReturnStmt及其子节点描述了返回语句的位置和详细信息
可以看出，AST 用 Tree struct 描述源代码，且包含足够多的源代码相关的信息。基于 AST 可以做很多关于代码分析相关的工作。
上面例子中的 AST 是基于 Clang 获取到的。基于不同的工具可以获取到不同的 AST，获取到的 AST 的内容取决于工具的 LR 文法文件。例如 Clang 是 LLVM 提供的 C/C++/OC 的编译器前端，内部包含了成熟通用的文法文件，获取到的 AST 和编译过程中产生的 AST 相同；Tree sitter 也是一个用于分析代码语法，将当前代码整理成抽象语法树的工具，但是它需要开发者自己写语言的 LR 文法文件，输出的 AST 和提供的 LR 文法文件匹配。目前 Tree sitter 在众多开发者的贡献下支持了多种语言的 LR 文法文件，进而支持获取这些语言的 AST。如果想基于 Tree sitter 获取一门新语言的 AST，需要首先提供这门新语言的 LR 文法文件。
基于 AST 能做什么
AST 以树状的形式表现源代码的语法结构，非常有利于分析遍历，且包含了足够多的源代码信息，因此基于 AST 可以做很多语法分析相关的工作：
语法检查
自动修复编译错误
自动修改代码格式
代码高亮
语法折叠
代码结构分析
那么业界通用的 AST 获取、分析工具有哪些呢？下面进行简单介绍：
基于 Clang 获取分析 AST
Clang 介绍
LLVM 是一个模块化、可重用、可扩展的编译器和工具链技术的集合，项目包含数个子工程，如编译器、链接器、调试器、标准库等，其中他的编译器部分是典型的三段式设计 Front-end、Middle-end、Back-end：
Clang 是 OC、C++、C 语言的 Front-end，主要负责预处理、词法分析、语法分析、语义分析等，生成 AST、并把 AST 转换为 IR，作为 Middle-end 的输入。
关于 Clang 有几个概念需要区分：
Clang
- OC、C++、C 语言的编译器的 Front-end，负责预处理、词法分析、语法分析、语义分析等，生成 AST、并把 AST 转换为 IR
Clang CC1
- Clang cc1 是 Clang 编译器，不仅包含编译器前端 Clang， 还包含编译器的 Middle-end、Back-end 部分。
Clang Driver
- 命令行使用的 Clang 是 Clang driver。Clang driver 不仅调用了编译器前端 Clang，同时还调用了编译器的 Middle-end、Back-end，并且因为 LLVM 没有自己的 Linker 的缘故，在编译的最后阶段，还调用了系统的 linker 进行静态链接。LLVM 的 linker 产品 lld 仍然在开发中。简单来说 Clang Driver 是一个把 编译 Front-end、Middle-end、Back-end，静态链接器等工作组织串联起来的驱动。
上述的定义来自于《Getting Started with LLVM Core Libraries》，还是比较有权威性的。
Xcode Build Settings 中 Other C/C++ Flags、Other Link Flags 设置的参数都是传递给 Clang Driver，前者编译时传递给 Clang Driver，后者链接的时候传递给 Clang Driver。Clang Driver 根据参数内容的不同进行传递，例如：
wl，XX 代表把 XX 传递给链接器
Xclang，XX 代表把 XX 传递给 Clang CC1
mllvm，XX 代表把 XX 传递给 Clang Middle-end
XX 代表 XX 直接交由 Clang Driver 本身处理
Clang 作为 OC、C、C++ 的编译器 Front-end，提供了一些列工具和 API 用于获取、遍历、分析 AST，下面对业界通用的基于 clang 的 AST 分析工具进行介绍。
不过需要注意的是基于 Clang 的 AST 分析工具，在 AST 之前都需要执行预处理，因此需要提供待处理文件编译参数和编译环境。
基于 Clang 的 AST 获取分析工具
LibClang
是什么
LibClang 是一系列稳定 C 接口的集合，这些 C 接口提供了访问 Clang 上层高级抽象对象的能力，比如获取所有 Token、语法树等。AST 的获取、遍历、分析只是它提供的能力之一。可以基于 LibClang 开发独立运行的代码分析工具。
基于 LibClang 分析 AST 的优点是 LibClang 提供的 API 很稳定，Clang 版本更新对工具影响不大；缺点是 LibClang 并不能访问 Clang AST 的全部信息。
如何编写&使用
目前 LibClang 有多种语言版本的封装，供各个语言调用。例如：
使用 C/C++ 语言基于 LibClang 开发一个 AST 分析工具，只需要：
编写 CMakeLists.txt，引入 LibClang.a 、相关头文件、自己编写的文件（main 等）
调用 LibClang 的 API 编写 AST 获取、分析逻辑
- 这里值得注意的是 AST 获取 api 是需要提供编译参数的，原因是基于 Clang 的 AST 分析工具，在 AST 之前都需要执行预处理
执行 Cmake && make 编译得到的可执行文件，可执行文件可用于 AST 分析
使用 python 语言基于 LibClang开发一个 AST 分析工具，只需要：
执行pip install Clang安装 python 版本的 Clang 库
编写 Python 脚本，Python 脚本中可以依赖 Clang 模块，调用 LibClang API 完成 AST 获取、分析
至于 LibClang 提供了哪些 AST 分析 API 以及如何使用，大家可以自行搜索。因为 LibClang 提供的 AST 分析 API 不能获取全部 AST 信息，所以一般不使用 LibClang 分析 AST。
Clang Plugins
是什么
Clang Plugins 是动态库，支持运行时由编译器加载集成到构建系统中，成为编译的一部分：
Clang Plugin 动态库的内容由开发者自己编写实现：基于 LLVM Project，调用丰富的 Clang API 实现自定义行为，然后编译成 Clang Plugin，参与到编译的流程中去。Clang Plugin 可以调用很多 Clang API，这些 API 支持获取、分析 AST、预处理等多种行为，其中和编译器前端相关的 API 就有如下多种类：
其中 AST 获取、分析可以通过 FrontendAction 中的 ASTFrontendAction 实现，因此可以开发一个集成到编译流程中 Clang Plugin 用于获取、遍历、分析 AST。使用 Clang Plugins 获取分析 AST，一般都是希望能够完全控制 Clang AST，同时能够集成在编译流程中，影响编译的过程，进行中断或者提示。
如何编写&使用
如何编写一个简单的 AST 获取、遍历 Clang plugin ，并应用起来呢？
下载 llvm-project 源码，并进行构建
在 llvm/clang/tools 目录下创建工程文件夹，如 ClassHeaderCheck
编写 ClassHeaderCheck.cpp、ClassHeaderCheck.hpp 文件，通过调用 Clang 提供的 api 实现 AST 获取、遍历逻辑
编写 CMakeListss.txt，标明参与编译的文件（ClassHeaderCheck.cpp/hpp)，依赖的库（AST 分析获取通过调用这些库的 API 实现）
修改 llvm/clang/tools下的 CMakeListss.txt，保证新增加的工程文件能够参与 LLVM 工程的构建
重新构建 llvm，即可得到 Clang Plugin 动态库文件(.dylib)
- 使用 Clang Plugin：
在 Xcdoe Build Settings Other C/C++ Flags 增加编译参数：Xclang load Xclang ./XXX.dylib 实现编译时动态加载 Clang Plugin，增加 Xclang -add-plugin Xclang class_header_check 实现编译时运行 class_header_check Clang plugin
工作原理
使用 Clang Plugin 最关键的步骤是 AST 获取分析逻辑的编写。而弄明白该步骤也有助于理解 Clang Plugin 的工作原理。下面通过介绍如何编写 AST 分析逻辑来介绍 clang plugin 的工作原理：
- Clang 提供了
ASTFrontendAction接口类用于获取、分析 AST，因此：
自定义一个继承 ASTFrontendAction 的 class，并实现父类的 CreateASTConsumer 接口，该接口需要返回一个 ASTConsumer 类型实例。
编译器前端执行时会调用有注册过的 FrontendAction 的 ExecuteAction 方法，ExecuteAction 方法内部首先获取 AST，调用 CreateASTConsumer 方法获取 Consumer ，通过调用 Consumer 的一系列执行 AST 分析逻辑。
When writing a clang based tool like a Clang Plugin or a standalone tool based on LibTooling, the common entry point is the FrontendAction. FrontendAction is an interface that allows execution of user specific actions as part of the compilation. Running tools over the AST clang provide the convenience interface ASTFrontendAction, which takes care of executing the action. The only part left is to implement the CreateASTConsumer method that returns an ASTConsumer per translation unit.
- 定义
ASTComsumer子类
定义 ASTComsumer 的子类作为上文 CreateASTConsumer 方法的返回值，ASTConsumer class 定义了一系列接口，获取、分析 AST 只需实现 HandleTranslationUnit 接口，上文获取Consumer 后会调用 Consumer 的 HandleTranslationUnit 方法。因为我们的 AST 分析逻辑通过重写 HandleTranslationUnit 方法实现。
实现 HandleTranslationUnit 的接口时，可以借助 RecursiveASTVisitor class 分析、遍历 AST ，RecursiveASTVisitor 为大多数 AST 节点提供形如 bool VisitXXXNodeType(NodeType *) 形式的 hooks。调用 RecursiveASTVisitor 的 TraverseDecl 方法遍历 AST，TraverseDecl内部遍历到节点时会调用这些 hook api。
因此我们只需按需
定义
RecursiveASTVisitor子类，按需实现 hook apiHandleTranslationUnit中通过RecursiveASTVisitor子类调用TraverseDecl方法
ASTConsumer is an interface used to write generic actions on an AST, regardless of how the AST was produced. ASTConsumer provides many different entry points, but for our use case the only one needed is HandleTranslationUnit, which is called with the ASTContext for the translation unit.The RecursiveASTVisitor provides hooks of the form bool VisitNodeType(NodeType *) for most AST nodes. We only need to implement the methods for the relevant node types.
- 通过定义静态变量注册 Clang Plugin
只有注册过的 Clang plugin ，才能在 Xcode 增加编译参数 Xclang load Xclang ./XXX.dylib Xclang -add-plugin Xclang XXX后被调起。
定义 FrontendPluginRegistry 类型的静态变量，静态变量在动态库 load 的时候初始化，FrontendPluginRegistry 类型变量初始化时，会触发其构造函数执行，构造函数执行会把参数(自定义 Clang Plugin ）注册到一个全局 map，用于解析 Xcode 增加的编译参数 -add-plugin Xclang XXX。当增加编译参数-add-plugin Xclang XXX时，会把 XXX clang plugin 注册到待执行的 plugins 中。
LibTooling
是什么
LibTooling 和 Clang Plugin 的功能几乎一模一样，通过调用 Clang API
实现代码分析的功能，二者的代码可以共用。二者的区别是：
Clang Plugin
是动态库，不能独立使用，需要在编译过程中动态加载执行，是编译流程的一部分
LibTooling
是一个可独立运行的工具，不依赖编译流程
如何编写&使用
LibTooling 的工作原理和上面介绍的 Clang Plugin 相同，也因此二者代码可以共用。需要注意的是
LibTooling 复用这份代码时，需要去掉 Clang Plugin 的注册逻辑，增加类似下面的代码，实现 LibTooling 不依赖编译流程，而是一个独立运行的工具。
- Clang Plugin 先通过定义静态变量和增加编译参数的方式注册 Clang Plugin，然后依赖于编译器前端执行时吊起所有注册过的 FrontedAction（Clang Plugin 本质是 FrontedAction），进而执行后续的 AST 分析逻辑；
- LIbTooling 通过 ClangTool 的 Run 方法主动触发FrontedAction 的执行。FrontedAction 之后的逻辑就一致了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int main(int argc, const char **argv) {
CommonOptionsParser op(argc, argv, AddOptionCategory);
ClangTool Tool(op.getCompilations(), op.getSourcePathList());
int result = Tool.run(newFrontendActionFactory<AddCodePlugin::ClassHeaderCheckAction>().get());
return result;
}
因为 Clang Plugin 和 Libtooing 的编译产物不同，二者编译方式也不同：
使用时直接使用得到的可执行文件，需要注意提供编译参数和编译环境：
1
2
3
4
5ClassHeaderCheckTool test.m -- XXX（编译参数）
//或者
ClassHeaderCheckTool test.m -p XXX（compile_commands.json）
应用
OCLint
是什么
OCLint 是基于 LibTooling 开发的可以独立运行的静态分析工具，通过 AST 分析发现编译器检查不到的潜在的关键技术问题，例如语法上的基础规则、一些约定俗成的规则、命名上长变量名短变量名检查、无用的语句变量和参数的检查。OCLint 支持动态加载检测规则，每条检测规则是 AST 分析逻辑编译成的动态库。
如何使用
OCLint 使用时需要提供待处理文件的编译参数和编译环境。因此使用 OCLint 进行静态分分析时可以这样做：先通过 XcodeBuild 编译获取编译参数和编译环境，然后利用 xcpretty 生成 OCLint 接收的编译命令文件
1 | compile_commands.json，最后触发 OCLint 静态检测，其中 -R |
工作原理
那么 OCLint 的工作原理是什么呢？下面进行简单介绍：
OCLint 是基于 LibTooling 开发的可独立运行的工具。因此原理和上文介绍的 LibTooling 、Clang Plugins 工作原理类似。
LibTooling 的入口如下图：
OCLint 的入口如下：
1 | int main(int argc, const char **argv){ |
LibTooling 通过 ClangTool 的 run 触发 FrontendAction 运行，FrontendAction 会触发后续 AST 获取、分析逻辑执行（详见上文）。OCLint 对这个步骤封装和扩展，形成了 Driver，支持运行多条 AST 检测规则，下面进行简单介绍：
Driver的 Run 方法触发
invoke方法，invoke方法 触发AST 获取和分析 ：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57static void invoke(CompileCommandPairs &compileCommands,
std::string &mainExecutable, oclint::Analyzer &analyzer)
{
std::vector<oclint::CompilerInstance *> compilers;
constructCompilers(compilers, compileCommands, mainExecutable);
// AST 获取
std::vector<clang::ASTContext *> localContexts;
for (auto compiler : compilers)
{
localContexts.push_back(&compiler->getASTContext());
}
// AST 分析
analyzer.preprocess(localContexts);
analyzer.analyze(localContexts);
analyzer.postprocess(localContexts);
}analyzer.analyze(localContexts)是调用 AST 检测规则的核心，如下所示：_filteredRules是注册过的 AST 检测逻辑集合， analyzer 遍历集合，调用每个 AST rule 的takeoff方法，takeoff触发 rule 的applyC方法，applyC中通过调用TraverseDecl方法遍历 AST。后续逻辑就和 Clang Plugin、LibTooling 的逻辑对应上了，AST Rule 均为 RecursiveASTVisitor 子类，实现了RecursiveASTVisitor 中的 Hook api，当TraverseDecl 遍历到节点时，会调用相关api。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56void RulesetBasedAnalyzer::analyze(std::vector<clang::ASTContext *> &contexts){
for (const auto& context : contexts){
LOG_VERBOSE("Analyzing ");
.....
for (RuleBase *rule : _filteredRules){// _filteredRules 为 AST 检测逻辑集合
rule->takeoff(carrier);
}
.....
LOG_VERBOSE_LINE(" - Done");
}
}
void RuleBase::takeoff(RuleCarrier *carrier){
_carrier = carrier;
applyC();
}
void applyC() {
clang::DeclContext *tu = getTranslationUnit();
for (clang::DeclContext::decl_iterator it = tu->decls_begin(), declEnd = tu->decls_end();it != declEnd; ++it){
if (isValidDecl(*it)) {
traverse(*it);
}
}
}
void traverse(clang::Decl *decl) {
(void) /* explicitly ignore the return of this function */
clang::RecursiveASTVisitor<T>::TraverseDecl(decl);
}
如何自定义 AST 检测规则
OCLint 支持开发者自定义规则。编写自定义 AST 检测规则和上文 Clang Plugin、LibTooling 编写 AST 逻辑几乎一模一样。
基于 OCLint 工程：
定义
AbstractASTVisitorRule子类，按需实现接口- Clang Plugin 中实现 AST 分析逻辑时是定义
RecursiveASTVisitor子类按需实现接口，OCLint 定义AbstractASTVisitorRule子类，然后按需实现接口。而AbstractASTVisitorRule继承自RecursiveASTVisitor，因此原理一致。1
2
3template<typename T>
class AbstractASTVisitorRule : public AbstractASTRuleBase, protected clang::RecursiveASTVisitor<T>
- Clang Plugin 中实现 AST 分析逻辑时是定义
注册 AST rule
通过定义静态变量实现 AST Rule 的注册，当静态变量初始化的时候调用 RuleSet 的初始化方法实现把 AST Rule 添加到上文中待执行 Rule 集合 _filteredRules。
每条 AST cule 会被编译成动态库，OCLint 会 load 需要执行的检测规则，触发静态变量初始化。
1
static RuleSet rules(new ConstantConditionalOperatorRule());
编写CMakeLists 文件把实现增加的 AST rule 编译为动态库，供 OCLint 动态加载使用
Clang Static Analyzer
是什么
Clang Static Analyzer（以下简称CSA）是 Clang 提供的代码静态检测工具。和其他静态检测工具不同，CAS 支持运行两种类型的检测规则：AST 规则和路径敏感规则。
AST 规则基于分析 AST 信息完成上下文无关的检测，如某个函数是否调用、函数参数类型、函数命名、方法命名等；路径敏感规则基于 AST分析完成上下文相关的检测，原理更复杂。
举个例子说明这两种规则的区别：对于下面代码， AST 规则能检测 writeCharToLog 方法是否调用 fopen 和 flose；而路径敏感规则能检测 flose 调用是否缺失。
1 |
|
如何使用
如何使用 CSA 呢？
和 CLang Plugin 类似，不能独立运行，依赖于编译。编译时增加 --analyze 参数就可以调用 CSA 的所有默认规则（主要是路径敏感规则）。CSA 也支持通过编译参数 -Xclang -load -Xclang ../path/to/.dylib 动态加载我们自定义的规则。
工作原理
接下来简单介绍下 CSA 支持两种类型规则的原理。
CSA 的原理和 Clang Plugins 的原理几乎一致：CAS 也是定义了一个 ASTFrontendAction 子类 AnalysisAction，并实现了 CreateASTConsumer 接口返回 AnalysisConsumer 类型实例。AnalysisConsumer 继承自 ASTConsumer 和 RecursiveASTVisitor，AnalysisConsumer 实现了 HandleTranslationUnit ，在 HandleTranslationUnit 中分析 AST。
1 | void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) { |
其中 AST 检测规则的执行很熟悉：TraverseDecl 触发 RecursiveASTVisitor 子类的 hook api 执行，AnalysisConsumer 继承自 RecursiveASTVisitor，实现了部分 hook API：
1 | /// Handle callbacks for arbitrary Decls. |
其中 checkerMgr->runCheckersOnASTDecl 会执行所有的注册的 AST 检测规则；HandleCode 会执行所有注册的 AST 检测规则和路径敏感规则
1 | void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr, |
可以看出无论是 AST 检测规则还是路径敏感规则，都是在基于分析 AST 实现的。路径敏感规则的执行原理是什么呢？
首先针对当前被遍历的 AST 节点构建 CFG，然后会按顺序遍历 CFG 中的每个节点，CFG 中每个节点也是 AST 类型节点，每个节点都执行全部注册的敏感路径规则。路径敏感规则中可以从 CFG 节点中提取信息进行检测。和普通 AST 规则不同，访问 CFG 每个节点时可以调用 API 存储 key value 信息，到下一个节点可以获取 Key Value 信息，判断是否符合要求，实现上下文相关的检测。
1 | void AnalysisConsumer::RunPathSensitiveChecks(Decl *D, |
举例说明 CSA 路径敏感检测规则：下图为根据某方法 AST 构建的
CFG，会按照如下顺序遍历 CFG， CFG 中每个节点都会调用敏感路径规则。
1 | Entry-B1-B2-B4-B5-B7-Exit |
假设方法中存在 Lock 的使用，可以在遍历过程中从 AST 中提取信息，判断是否是 Lock 相关的操作，当是 Lock 时先 get lock（key），得到该节点之前 Lock 的状态，进而可以判断当前是否是重复 Lock，然后 set lock（key）lock（value） 。类似的还可以检测是否缺失 unlock 操作。
CSA 支持的路径敏感规则其实分为两类：inline 路径敏感规则和非 Inline 路径敏感规则。上面介绍的是非 Inline 路径敏感规则，在执行 AnalysisConsumer 的 TraverseDecl 遍历 AST 每个节点时执行；InLine 路径敏感规则在 TraverseDecl 执行完毕后执行，运行原理和 非 Inline 一致，只是输入是 AST 跟节点，构造 CFG 时会把所有的方法调用 inline ，实现更全面的检测。
1 | void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) { |
上述介绍的 CSA 的工作原理可以简叙如下：
如何自定义检测规则
如何实现一个 CAS 规则呢？
路径敏感规则
- 简单来说就是，基于 LLVM Project，实现一个继承 Checker Class 的子 class，按需实现接口，注册这个 Class，编译成动态库。编译时通过 –analyze -anXclang -load -Xclang ../path/to/.dylib 打开 CSA 功能，同时加载这个动态库，上面介绍的 CSA 工作流程中就会调用这个路径敏感 checker。
AST 规则
- 和上文介绍的 Clang Plugin 类似，只不过更简单，因为 consumer、RecursiveASTVisitor 等逻辑都已经帮你实现了。只需定义如下几个 Class 之一的子类，并实现父类接口。
1
2
3
4
5class：ASTCodeBody，interface：checkASTCodeBody
class：ASTDecl，interface：checkASTDecl
class：EndOfTranslationUnit， interface：checkEndOfTranslationUnit然后进行注册, registerTestChecker 方法会被调用，执行 CheckerManager 的 registerChecker 方法，registerChecker 中调用注册 class 的 register 方法，register 方法来自于注册 class 的父类，实现把自定义 ，checker， 注册到全局数组中，上面介绍的 CSA 工作流程中会访问这个全局数组，执行数组中的全部 AST checker。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55void ento::registerTestChecker(CheckerManager &mgr) {
mgr.registerChecker<TestChecker>();
}
// CheckerManager
template <typename CHECKER, typename... AT>
CHECKER *registerChecker(AT &&... Args) {
CHECKER *checker = new CHECKER(std::forward<AT>(Args)...);
checker->Name = CurrentCheckerName;
CheckerDtors.push_back(CheckerDtor(checker, destruct<CHECKER>));
CHECKER::_register(checker, *this);
ref = checker;
return checker;
}
class ASTCodeBody {
template <typename CHECKER>
static void _checkBody(void *checker, const Decl *D, AnalysisManager& mgr,
BugReporter &BR) {
((const CHECKER *)checker)->checkASTCodeBody(D, mgr, BR);
}
public:
template <typename CHECKER>
static void _register(CHECKER *checker, CheckerManager &mgr) {
mgr._registerForBody(CheckerManager::CheckDeclFunc(checker,
_checkBody<CHECKER>));
}
};
void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
BodyCheckers.push_back(checkfn);
}
静态检测
静态检测就是基于 OCLint 实现的检测编译不能发现的问题。
其他
LLVM project 中提供了一系列使用 clang API 实现的工具，这些工具中大部分都是基于 AST 分析工具 Clang Plugin / LibTooling 实现的，感兴趣的同学可以通过阅读这些工具的源码进行学习。
优缺点
基于 Tree-sitter 获取分析 AST
Tree-sitter 介绍
Tree-sitter 是一个高速、轻量的增量式代码分析工具，主要是做代码的语法分析，将当前代码整理成抽象语法树并返回给编辑器。它的特点是：
支持将任何编程语言解析成 AST
高效
不需要进行预处理，也不需要编译参数和编译环境，因此更高效
即使输入文件存在语法错误，也可以成功获取 AST
而基于 clang 的 AST 分析遇到语法错误、预处理错误会终止的
基于 C 语言编写，可以嵌入到任何应用程序中
可基于 Tree-sitter 编写出用于分析 AST 的可执行文件，用于独立运行
Tree-sitter 还被封装成了多种语言，支持基于多种语言进行开发。
与基于 clang 的 AST 分析工具依赖编译参数和编译环境不同，Tree-sitter 只需要输入待处理的文件，不依赖任何额外操作，例如不需要编译参数，不会执行预处理。
基于 Tree-sitter 的 AST 分析获取
AST 获取
Tree-sitter 支持把任意编程语言解析为抽象语法树 AST 的原理是：开发者使用 js 编写需求语言的 LR 文法文件 grammar.js；官方提供的 Tree-sitter-cli 工具支持将 grammar.js 生成为解析需求语言所需的 C 代码，即 parser.c/h；后续 Tree-sitter-cli 会根据 parser.c/h 语法规则把需求语言的文件解析成 AST。其中关键核心在于 grammar.js 的编写。
基于 clang 的 AST 分析工具不需要我们自己编写 LR 文法文件，它已经拥有了完备的文法文件，文法文件是编译器不可获取的一部分。而 Tree-sitter 是一个通用的语法分析、AST 生成工具，需要开发者自己编写文法文件，然后 Tree-sitter 按照你提供的文法规则对输入文件进行文法分析、生成 AST。
这里提到了两个和 Tree-sitter 相关的概念 Tree-sitter 和 Tree-sitter-cli，二者什么关系呢：如下图所示，Tree-sitter-cli 是对 Tree-sitter 的 js 封装，通过调用 Tree-sitter 的 C 接口实现 AST 获取等功能。正如上文提到的 Tree-sitter 被多种语言封装。
那如果我们想基于 Tree-sitter 实现获取一门新语言的 AST 需要怎么办呢？
- 编写 package.json 文件，指定相关依赖
必须要依赖用于生成 prase.c 的工具 Tree-sitter-cli、 nan；如果我们的文法依赖其他文法，也需要依赖的对应文法库。例如下图 objc 是依赖 C 语言的文法规则，所有需要依赖 Tree-sitter-c
执行 npm install，根据上面的 package.json 安装依赖
写一个文法文件 grammar.js，可以依赖其他语言的文法文件，例如 OC 的文法文件依赖 C 语言的文法文件
如何编写一门语言的文法文件 grammar.js 是核心，也比较复杂，篇幅较长，不在本文进行展开。感兴趣的同学可以自行搜索。
- 执行 Tree-sitter generate 把 grammar.js 生成为 prase.c，后续解析语言为 AST 使用
Tree-sitter 根据文法文件分析语言文件生成 AST 的原理感兴趣的同学可以阅读源码，本文不再赘述。
- 测试是否能按照我们规定的文法解析文件
1 | Tree-sitter parse XXX//应该输出对应的AST的 |
这里有个值得注意的点，Tree-sitter-cli 的 Tree-sitter generate、generate 指令分别实现了 prase.c 获取、AST 获取，那么 Tree-sitter-cli 还支持哪些指令呢？
AST 遍历分析
Tree-sitter 提供了 API 用于获取、分析、遍历 AST，也提供了模式匹配用于在 AST 中进行高效查找。下面简单介绍如何通过 API 完成 AST 获取、遍历，以及如何使用模式匹配功能。至于 Tree-sitter 遍历 AST原理，模式匹配工作原理，不在本文介绍，感兴趣同学可以阅读源码。
首先介绍如何基于 Tree-sitter API 生成、分析 AST：
建立文件夹和文件
1
2
3parser
|___main.c
|___CMakeLists.txt在 Prase 文件夹下
git clone https://github.com/Tree-sitter/Tree-sitter- Tree-sitter 提供 api 生成、分析 AST，所有需要依赖 Tree-sitter
在 Prase 文件夹下 Git clone 需要生成 AST 的语言的 parse.c 文件
- Tree-sitter 需要根据 prase.c 生成 AST
编写 main.c 文件
- 调用调用 Tree-sitter 的 api 实现获取、分析 AST
编写 CMakeLists.txt
保证 main.c、prase.c Tree-sitter 源码 均需参与编译
执行 cmake && make 得到可执行文件，可以用于 AST 获取和分析
上述步骤的核心是如何基于 Tree-sitter api 获取、分析 AST：
获取 AST
每个待生成 AST 的语言都需要提供文法文件 grammar.js，Tree-sitter-cli 会把 grammar.js 转换为 parse.c 文件，parse.c 提供了一个如下方法，返回了文法数据结构：
1
2
3
4
5
6
7
8
9extern const TSLanguage *tree_sitter_cpp(void) {
static const TSLanguage language = {
......
}
return &language;
}
获取 AST 需要依赖 Tree-sitter 的 Parser class 的 parser 相关方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
TSLanguage *language = tree_sitter_cpp();
//创建待解析语言的解析器
TSParser* parser = ts_parser_new();
ts_parser_set_language(parser,language)
// get AST
TSTree* tree = ts_parser_parse_string(parser, NULL, sourceCode, strlen(sourceCode));//sourceCode 为从待解析文件提取的内容
TSNode rootNode = ts_tree_root_node(tree);
- 遍历 AST
可以通过 Tree-sitter 提供的如下 API 遍历 AST：获取一个节点的子节点的个数，然后按照 index 遍历每个子节点；或者直接跟进节点的 name 获取节点。
1 |
|
Tree-sitter 文法规则中提供了下面语法 field(name, rule) 实现给语法树中某个匹配规则的节点加上一个名字。比如 C++ 模板的声明，对于 template_parameter_list节点，
1 | template_declaration: $ => seq( |
Tree-sitter 还支持通过下面 API 获取节点的内容：
1 | //Get the mNode's start byte. |
根据模式匹配功能遍历 AST
分析 AST 时可能只需提取、分析某种类型的节点，如果按照上面的 API 顺序遍历 AST 效率比较低。Tree-sitter 提供了模式匹配功能，用于提取指定类型的节点。
例如 objc 的文法文件中存在objc 方法节点定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18method_definition: $ => seq(
field('scope', $._class_member_scope),
field('return_type', optional($._method_argument_type_specifier)),
field('selector', $._method_selector),
optional($.attribute_specifier),
optional(';'), // compatible with: - (void)method; {}
field('body', $.compound_statement),
optional(';'),
),
利用模式匹配功能提取上述两种类型的节点，只需要：
编写模式匹配文件 XXX.scm，包含需要匹配的节点类型
1
2
3//When matching patterns, you may want to process specific nodes within the pattern. Captures allow you to associate names with specific nodes in a pattern, so that you can later refer to those nodes by those names. Capture names are written after the nodes that they refer to, and start with an @ character.
(method_definition)@method.definition定义
TSQuery实例,输入为上面 scm 文件内容，然后调用 TSQueryCursor classts_query_cursor_exec方法实现模式匹配
1 | TSQueryError errorType = TSQueryErrorNone; |
- 通过
ts_query_cursor_next_matchapi 获取到匹配节点TSQueryMatch
1 | typedef struct { |
应用
获取文件中方法信息
基于 Tree-sitter 的 AST 获取和模式匹配功能，可以从文件中提取方法名称、方法行号范围，以及方法子调用等信息，格式如下：
1 | [ |
其他可落地场景
编辑器语法高亮和 Clode IDE 跳转
静态代码检查
代码规范准入检查
包大小预估
Spell Check
优缺点
基于Tree-sitter 的 AST 分析优点非常明显：
高效获取 AST，即使存在语法错误也能获取 AST
- 获取 AST 前不需执行预处理带来了多个好处：不需要提供编译参数和编译环境、效率更高，节省了预处理时间、即使存在语法错误也可以进行 AST 分析。
支持多种语言的 AST 获取、分析
Clang 之支持 C、C++、OC 的 AST 分析，如果我们想分析 swift AST 还需要学习 Swift 相关 AST 分析工具，成本比较高。
而 tree-sitter 只要提供不同语言的文法文件，AST 分析、获取、匹配 API 都是相同的。
学习成本相对较低
- 相比于基于 Clang 的 AST 分析，Tree-sitter 的入门和学习成本更低。
当然 tree-sitter 也存在缺点：
需要编写文法文件
- 基于 Tree-sitter 进行文法分析的前提是提供文法文件，而文法文件的编写还是比较复杂的。不过目前业界已经支持了大部分语言的文法文件，例如 swift、C++、OC、C ，至少满足了 iOS 的 AST 分析需求
只能基于 AST 进行分析
- Tree-sitter 只是一个 AST 获取、分析工具，而 Clang 时 OC/C/C++ 的编译器前端，提供的 API 不仅仅局限于 AST 的分析，还有更丰富的功能可以探索
文法文件可能没有涵盖所有语法或者写法，导致部分写法/语法不能遍历识别
总结
我们可以根据自己的需求选择合适的工具进行代码分析，例如：
如果我们需要开发一个集成到编译流程的代码分析工具，只能选择 Clang 得 Clang Plugins
如果我们需要利用到 AST 之外的更多代码信息，也只能选择基于 Clang 的分析工具
如果我们只需根据 AST 进行代码分析，且需要的是一个独立运行的工具，那使用 Tree-sitter 更方便、高效
如果我们只需根据 AST 进行代码分析，且需要的是一个独立运行的工具，那使用 Tree-sitter 更方便、高效
参考资料
libclang
OCLint:
CSA
Tree-sitter