0.简介

代码静态分析从广义上讲，是指在不运行计算机程序的条件下，进行程序分析的方法。具体分析的包括语法错误，可能出现的程序错误，代码样式规范等内容。大部分的静态程序分析的对象是针对源代码的，也有些静态程序分析的对象是中间代码或者目标代码的，总之以不同的目的会有不同的需求。
对代码进行静态分析，主要目的还是通过这一种辅助手段，减少代码出错的可能性，提升代码间接性，可读性等多方面工程化性质，间接提升工程质量，降低开发成本。

1.AST

静态分析很大一部分是从源代码角度分析的，比较适合用于分析各种代码样式等东西，这也是我们一般可以想到的方法。但是更复杂的静态分析，比如我要分析fopen之后是不是完了fclose，从源码角度就很困难了。这个时候，代码编译的中间数据——抽象语法树就可以帮大忙了。

抽象语法树即AST是代码编译的过程中会生成的一个树状结构，树上的每一个的节点是代码中的一个元素，包括数据，操作符，代码块，for，if，while，类，方法。只要是一个代码中的元素，都被抽象为了一个结点类型。而这个元素下面的东西，比如操作符的左表达式右表达式，方法的名字入参返参方法体，for的3个语句循环体，都是这个个结点的子结点，而子结点又是有起对应的类型。

可以理解，一般情况下，随便一段代码都会被编译为一棵很复杂的树，如果有出现循环调用或者流程控制的代码，那就是一个图了。干说无用，举一个clang编译的栗子：

int abs(int input) {
    if (input<0) {
        return -input;
    }
    return input;
}

执行clang -cc1 -ast-dump test.c

`-FunctionDecl 0x10484d8b0 prev 0x103805550 <col:1, line:6:1> line:1:5 abs 'int (int)'
  |-ParmVarDecl 0x103805488 <col:9, col:13> col:13 used input 'int'
  `-CompoundStmt 0x10484db50 <col:20, line:6:1>
    |-IfStmt 0x10484dac8 <line:2:2, line:4:2>
    | |-<<<NULL>>>
    | |-BinaryOperator 0x10484da08 <line:2:6, col:12> 'int' '<'
    | | |-ImplicitCastExpr 0x10484d9f0 <col:6> 'int' <LValueToRValue>
    | | | `-DeclRefExpr 0x10484d9a8 <col:6> 'int' lvalue ParmVar 0x103805488 'input' 'int'
    | | `-IntegerLiteral 0x10484d9d0 <col:12> 'int' 0
    | |-CompoundStmt 0x10484daa8 <col:15, line:4:2>
    | | `-ReturnStmt 0x10484da90 <line:3:3, col:11>
    | |   `-UnaryOperator 0x10484da70 <col:10, col:11> 'int' prefix '-'
    | |     `-ImplicitCastExpr 0x10484da58 <col:11> 'int' <LValueToRValue>
    | |       `-DeclRefExpr 0x10484da30 <col:11> 'int' lvalue ParmVar 0x103805488 'input' 'int'
    | `-<<<NULL>>>
    `-ReturnStmt 0x10484db38 <line:5:2, col:9>
      `-ImplicitCastExpr 0x10484db20 <col:9> 'int' <LValueToRValue>
        `-DeclRefExpr 0x10484daf8 <col:9> 'int' lvalue ParmVar 0x103805488 'input' 'int'

    
可以清晰的看到，这一段代码的每一个元素与其子结点的关系。其中的结点有两大类型，一个是Stmt类，包括Expr表达式类也是继承于Stmt，它是语句，有一定操作；另一大类元素是Decl类，即定义，所有的类，方法，函数变量均是一个Decl类(这两个类互不兼容，需要特殊容器结点来转换，比如DeclStmt结点)。具体看数据结构的话，比如FunctionDecl，除了各种个样它自己本身特性的属性和方法，可以注意到ArrayRef< ParmVarDecl * >   parameters () const方法，即可获得这个函数的参数列表了，然后还有一个显而易见的Stmt *   getBody () const，默认会返回这个函数体的最顶层元素，一般也就是一个CompoundStmt元素了。这个CompoundStmt又是一个可迭代的结构，它的子元素也全是Stmt，就可以自己深入下去了。另外从数据结构中可以看到，这个树是单向的，只有从某一个顶层元素向下爬树，而没法逆向向上爬，只有回缩回去了。

2.爬树法

当然，说到爬树的方法，没得改肯定是深搜了，而且无论是Stmt还是Decl也都自带迭代器，可以方便的遍历所有元素再判断其类型进行操作。不过在clang中还有更方便的方法：继承RecursiveASTVisitor类。

RecursiveASTVisitor看名字就知道，它是一个ast树递归器，可以递归的访问一个ast树的所有结点。最常用的方法是TraverseStmt和TraverseDecl，以一个Stmt或者Decl作为入口递归的访问ast树中每一个结点。那么我们接下来就是重写访问结点的方法了。需要重写的是bool VisitXXXXXX(XXXXXX *xxxx);方法，XXXXXX是一个特定的Stmt或者Decl类，然后获得的入参就是一个这个类的实例了。比如我要访问我这么一段代码中所有的函数，即FunctionDecl，并且输出这些函数的名字，我就要重写这么一个方法：

bool VisitFunctionDecl(FunctionDecl *decl){
    string name = decl->getNameAsString();
    printf(name);
    return true;
}

这样，我就能够访问到这棵ast树中所有的FunctionDecl并且把其中函数名字给输出出来了。同时，我们既然获得了这个结点本体decl，我们当然也可以自行通过这个结点进行爬树来获取需要的信息，甚至可以再new一个RecursiveASTVisitor的实现出来对FunctionDecl或者其中的某个元素进行递归，简直善哉。再来一个比较简单的爬树实用例子，oclint规则中的ObjCVerifyMustCallSuperRule，它检查的是重写方法的时候有强制调super方法的父级方法到底有没有调用super。这个规则的主检查器主要重写的方法是这样的：

bool VisitObjCMethodDecl(ObjCMethodDecl* decl) {
    // Save the method name
    string selectorName = decl->getSelector().getAsString();

    // Figure out if anything in the super chain is marked
    if(declRequiresSuperCall(decl)) {
        // If so, start a separate checker to look for method sends just in the method body
        ContainsCallToSuperMethod checker(selectorName);
        checker.TraverseDecl(decl);
        if(!checker.foundSuperCall()) {
            string message = "overridden method " + selectorName + " must call super";
            addViolation(decl, this, message);
        }
    }
    return true;
}

首先，遍历器访问的是每一个oc方法，获得当前方法名后，调用私有方法declRequiresSuperCall，这个方法的内容也很简单，就是取出当前方法重写的所有父级方法，挨个检查到底有没有enforce咯，如下：

bool declRequiresSuperCall(ObjCMethodDecl* decl) {
    if(decl->isOverriding()) {
        SmallVector<const ObjCMethodDecl*, 4> overridden;
        decl->getOverriddenMethods(overridden);
        for (auto& elem : overridden) {
            if (declHasActionAttribute(decl, "enforce", this)) {
                return true;
            }
        }
    }
    return false;
}

如果有重写的方法是有enforce标示的，我们new了一个ContainsCallToSuperMethod出来，这个是啥，这是我们写的另一个遍历检查器，当然，也是一个RecursiveASTVisitor。它做了什么？先看代码：

class ContainsCallToSuperMethod : public RecursiveASTVisitor<ContainsCallToSuperMethod> {
private:
    string _selector;
    bool _foundSuperCall;
public:
    explicit ContainsCallToSuperMethod(string selectorString) : _selector(std::move(selectorString)) {
        _foundSuperCall = false;
    }
    bool VisitObjCMessageExpr(ObjCMessageExpr* expr) {
        if(expr->getSelector().getAsString() == _selector && expr->getReceiverKind() == ObjCMessageExpr::SuperInstance) {
            _foundSuperCall = true;
        }
        return true;
    }
    bool foundSuperCall() const {
        return _foundSuperCall;
    }
};

十分清晰，最核心的还是VisitObjCMessageExpr，访问了这个树上的每一个ObjCMessageExpr，也就是每一个发送消息，也就是调用别的方法的地方，然后检查，调用的这个方法的名字是不是我之前那个方法的名字呢？调用的方法的接收者是不是super呢？是，嗯，这个方法调用了super了，标示位标上。回到主检查器，我们通过checker.TraverseDecl(decl);把这个方法下的所有结点检查完成之后，调用checker.foundSuperCall()获取到子检查器遍历过后得到的结果，最后对结果进行输出。

3.oclint规则编写

知道了代码检测方法，我们就可以开始写规则了。oclint编写规则可以基层于3个类，

- 其中最简单的类是AbstractSourceCodeReaderRule，这个类和RecursiveASTVisitor无关，它会通过抽象方法void eachLine(int lineNumber, string line);把每一行代码返回回来，我们把代码当普通字符串处理就可以了。

- 然后就是最常用的AbstractASTVisitorRule了，它本身就继承于RecursiveASTVisitor，因此它就是一个递归检查器，每次检查器被调用从代码根部进行检测，自动遍历所有元素，上文的ObjCVerifyMustCallSuperRule就是这么一个类。

- 再次，还有一个叫AbstractASTMatcherRule的基类，它不但继承于AbstractASTVisitorRule还继承于clang::ast_matchers::MatchFinder::MatchCallback，可以很方便的对需要的结点元素通过它的一些属性和计算结果进行筛选。可用的筛选器非常多，参看：http://clang.llvm.org/docs/LibASTMatchersReference.html

当然，总的来说，对于规则编写，源码检查多用于样式上的检查，用过关键字找到关键字前后的语法样式是否符合要求，比如ifelsewhile之内的有无空格啊，注释的样式啊之类的；而AbstractASTMatcherRule能做的，当然其父类AbstractASTVisitorRule也能手动筛选出来，必要性也没有那么大。因此我们大部分规则，还说以AbstractASTVisitorRule即RecursiveASTVisitor为核心，写遍历器就可以了。最后展示一个清晰明白的完整的自定义规则——fugu属性名命名规则：

#include "oclint/AbstractASTVisitorRule.h"
#include "oclint/RuleSet.h"

using namespace std;
using namespace clang;
using namespace oclint;

class FuguOCPropertyNameRule : public AbstractASTVisitorRule<FuguOCPropertyNameRule> {
public:
    virtual const string name() const override {
        return "fugu oc property name";
    }
    virtual int priority() const override {
        return 3;
    }
    virtual const string category() const override {
        return "fuguCustom";
    }
    virtual unsigned int supportedLanguages() const override{
        return LANG_OBJC;
    }
    bool VisitObjCPropertyDecl(ObjCPropertyDecl *decl){
        string name = decl->getNameAsString();
        string::iterator itor = name.begin();
        if(*itor >= 'A' && *itor <= 'Z'){
            addViolation(decl, this, "Property "+name+" start with uppercase letter");
        }
        return true;
    }
    bool VisitObjCPropertyImplDecl(ObjCPropertyImplDecl *decl){
        string name = decl->getPropertyDecl()->getNameAsString();
        string::iterator itor = name.begin();
        if(*itor != '_'){
            addViolation(decl, this, "Inner property "+name+" don't start with _");
        }else if(*(itor+1) >= 'A' && *(itor+1) <= 'Z'){
            addViolation(decl, this, "Inner property "+name+" start with uppercase letter");
        }
        return true;
    }
};

static RuleSet rules(new FuguOCPropertyNameRule());

除了RecursiveASTVisitor中重写的遍历器，还需要重写抽象方法给出规则名称，类型，优先级以及适用语言（oclint的规则不止适用于oc，适用于所有clang可编译的语言）。需要报错的地方通过基类的方法addViolation给报出来既可以。并且保持Visit方法始终返回true来保证遍历不中断。最后，在外面的makefile中把对应的文件和文件夹加进去，就可以编译出来了。（一次全局编译后，之后只需要调用./build -release就可以单独编译规则了）。规则最后会输出到./build/oclint-rules/rules.dl文件夹中，取出来用上吧。