clang static analyzer基于的是经典符号执行，经典的符号执行中存在的问题，clang static analyzer中也都存在，例如内存开销，路径爆炸，内存模型

https://www.zhihu.com/question/46358643/answer/134173861

https://arxiv.org/pdf/1610.00502.pdf
https://github.com/llvm-mirror/clang/tree/master/lib/StaticAnalyzer

stmt和expr是什么意思？
statement 和expression 也就是 语句 和 表达式

一般编程语言的语法单位有下面这些：

定义：指变量定义、函数定义或类定义等
声明
语句：函数或方法的定义的本体中包含有语句
表达式： 表达式是比语句小、具有值的语法单位
项：项这一语法单位是表达式中构成二元运算的一方，也就是仅由一元运算符构成的语法。
https://www.dazhuanlan.com/2019/10/19/5daace2a3758d/

AST语法树关键字解析
https://www.jianshu.com/p/d21c16b8953e
https://www.cnblogs.com/zhangke007/p/4714245.html
https://www.jianshu.com/p/e38786de29c7?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

https://www.jianshu.com/p/d21c16b8953e

https://www.zhihu.com/question/27907848/answer/71515399

go/ast（抽象语法树):
https://www.breakyizhan.com/go/35520.html
func Inspect(node Node, f func(Node) bool)
检查以深度优先顺序遍历AST：它通过调用f(node) 开始；节点不能为零。如果 f 返回 true，Inspect 会为节点的每个非零子节点递归调用f，然后调用 f(nil)。

func Print(fset *token.FileSet, x interface{}) error
Print打印x到标准输出，跳过零字段。打印（fset，x）与Fprint（os.Stdout，fset，x，NotNilFilter）相同。

func SortImports(fset *token.FileSet, f *File)
SortImports 对f中的导入块中的连续导入行进行排序。它还可以在不丢失数据的情况下删除重复导入。

func Walk（显示源代码）
func Walk(v Visitor, node Node)
以深度优先顺序遍历 AST：它通过调用 v.Visit（节点）开始; 节点不能为零。如果由 v.Visit（节点）返回的访问者 w 不为零，则对于节点的每个非零子节点，访问者 w 递归地调用 Walk，随后调用 w.Visit（nil）。

Go的parser接受的输入是源文件,内嵌了一个scanner,最后把scanner生成的token变成一颗抽象语法树(AST).
编译时的错误也是在这个时候报告的,但是大部分编译器编译时的错误系统并不是很完美,有时候报的错误文不对题,这主要是因为写对的方式有几种
但是写错的方式有很多种,编译器只能把一些错误进行归类,并且指出当前认为可疑的地方,并不能完完全全的知道到底是什么语法错误.这个需要结合给出的错误进行判断,clang作为一个C编译器做得好很多,这都是开发者不断地添加错误处理的结果,比gcc的报错完善很多.然而Go的编译时的错误处理也是秉承了gcc的风格,并不明确,但是会指出可疑的地方,在大多数场景下或者对语言标准熟悉的情况下也不是很麻烦.
下面看一下Go是怎么定义这些语法结构.这些结构都在go/ast当中.
https://studygolang.com/articles/6709

http://www.coder55.com/article/6826

https://studygolang.com/articles/984

http://ilovers.sinaapp.com/doc/golang-specification.html

基础结构说明
普通Node,不是特定语法结构,属于某个语法结构的一部分.
Comment 表示一行注释 // 或者 / /
CommentGroup 表示多行注释
Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值
FieldList 表示以”{}”或者”()”包围的Filed列表
Expression & Types (都划分成Expr接口)
BadExpr 用来表示错误表达式的占位符
Ident 比如报名,函数名,变量名
Ellipsis 省略号表达式,比如参数列表的最后一个可以写成arg…
BasicLit 基本字面值,数字或者字符串
FuncLit 函数定义
CompositeLit 构造类型,比如{1,2,3,4}
ParenExpr 括号表达式,被括号包裹的表达式
SelectorExpr 选择结构,类似于a.b的结构
IndexExpr 下标结构,类似这样的结构 expr[expr]
SliceExpr 切片表达式,类似这样 expr[low:mid:high]
TypeAssertExpr 类型断言类似于 X.(type)
CallExpr 调用类型,类似于 expr()
StarExpr 指针表达式,类似于 *X
UnaryExpr 一元表达式
BinaryExpr 二元表达式
KeyValueExp 键值表达式 key:value
ArrayType 数组类型
StructType 结构体类型
FuncType 函数类型
InterfaceType 接口类型
MapType map类型
ChanType 管道类型
Statements语句
BadStmt 错误的语句
DeclStmt 在语句列表里的申明
EmptyStmt 空语句
LabeledStmt 标签语句类似于 indent:stmt
ExprStmt 包含单独的表达式语句
SendStmt chan发送语句
IncDecStmt 自增或者自减语句
AssignStmt 赋值语句
GoStmt Go语句
DeferStmt 延迟语句
ReturnStmt return 语句
BranchStmt 分支语句 例如break continue
BlockStmt 块语句 {} 包裹
IfStmt If 语句
CaseClause case 语句
SwitchStmt switch 语句
TypeSwitchStmt 类型switch 语句 switch x:=y.(type)
CommClause 发送或者接受的case语句,类似于 case x <-:
SelectStmt select 语句
ForStmt for 语句
RangeStmt range 语句
Declarations声明
Spec type
Import Spec
Value Spec
Type Spec
BadDecl 错误申明
GenDecl 一般申明(和Spec相关,比如 import “a”,var a,type a)
FuncDecl 函数申明
Files and Packages
File 代表一个源文件节点,包含了顶级元素.
Package 代表一个包,包含了很多文件.

https://www.jianshu.com/p/e38786de29c7

go的背景介绍
在进行分析前，先简单介绍下golang的特点，这对“用go的办法解决go的问题”有一定的引导作用，同时也是一种约束。

go是一种需要编译才能运行的编程语言。
go有比较严格的类型检查，拥有interface机制，拥有较为强大的反射机制，但缺少泛型机制。
go的设计思路：简单即复杂，用简单的语法表达复杂的逻辑。
数据结构分析方案一——golang编译前端之AST
AST即抽象语法树。
阅读资料
go 语言设计与实现 第二章 编译原理

golang深入源代码系列之一：AST的遍历

golang深入源代码系列之二：反向调用关系的生成

Go的AST(抽象语法树)

golang提供的静态编译工具链：

golang.org/x/tools/go/loader

Package loader loads a complete Go program from source code, parsing and type-checking the initial packages plus their transitive closure of dependencies. The ASTs and the derived facts are retained for later use.

golang.org/x/tools/go/pointer

Package ssa defines a representation of the elements of Go programs (packages, types, functions, variables and constants) using a static single-assignment (SSA) form intermediate representation (IR) for the bodies of functions.

golang.org/x/tools/go/ssa

Package pointer implements Andersen’s analysis, an inclusion-based pointer analysis algorithm first described in (Andersen, 1994).

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

go语言编译可大致分为词法与语法分析、类型检查和 AST 转换、通用 SSA 生成和最后的机器代码生成四个逻辑阶段。

词法分析的输入是源文件xxx.go，输出是一组token，包路径src\go\token，一个token可以理解为一个代码元素，分为几组。

特殊token。例如，ILLEGAL（非法TOKEN）、EOF（文件末尾）、COMMENT（注释）
字面token。例如，标识符IDENT、数字INT、字符串STRING等等。
操作符token。+ - * / , . ; ( )等等。
关键字token。var,select,chan等。
注：词法分析阶段，会给源码的每行的最后添加上分号;。这就是go代码每行最后不用加分号的原因。

语法分析的输入是词法分析的结果，输出是一颗树状结构的树。是由没有语法意义的一个一个单词，按照一定的文法，转化为有层次结构，有一定语义的语法树。每个 go 源代码文件最终都会被解析成一个独立的抽象语法树。树的根节点是一个*ast.File的元素，下面不断的递归包含了文件内所有的语法元素，并且有了一定的层次关系。

0 package main
1 func main() {
2 println(“Hello, World!”)
3 }
1
2
3
4
如上代码，会被转化为如下的语法树，箭头部分是我加的注解。

// Output:
// 0 ast.File {
// 1 . Package: 2:1
// 2 . Name: *ast.Ident {
// 3 . . NamePos: 2:9
// 4 . . Name: “main”
// 5 . }
// 6 . Decls: []ast.Decl (len = 1) { ——————————————>声明slice
// 7 . . 0: *ast.FuncDecl { ——————————————>函数定义元素
// 8 . . . Name: *ast.Ident { ——————————————>函数定义由 Name Type Body组成 其实还有Doc（关联的文档），Recv(Receiver)
// 9 . . . . NamePos: 3:6 ——————————————>函数定义的Name的位置
// 10 . . . . Name: “main”
// 11 . . . . Obj: *ast.Object { ——————————————>函数定义的Object
// 12 . . . . . Kind: func
// 13 . . . . . Name: “main”
// 14 . . . . . Decl: *(obj @ 7)
// 15 . . . . }
// 16 . . . }
// 17 . . . Type: *ast.FuncType { ——————————————>函数定义的type，包括入参，出参，和func关键字的位置。
// 18 . . . . Func: 3:1 ——————————————>func关键字的位置。
// 19 . . . . Params: *ast.FieldList { ——————————————>函数定义的入参。
// 20 . . . . . Opening: 3:10
// 21 . . . . . Closing: 3:11
// 22 . . . . }——————————————>函数没有出参，所以Results为nil。
// 23 . . . }
// 24 . . . Body: *ast.BlockStmt {——————————————>函数体。
// 25 . . . . Lbrace: 3:13——————————————>函数体左花括号。
// 26 . . . . List: []ast.Stmt (len = 1) {——————————————>函数体每一个statement，实现了ast.Stmt接口的都可以放进去。
// 27 . . . . . 0: *ast.ExprStmt {——————————————>第一个元素是一个表达式
// 28 . . . . . . X: *ast.CallExpr {——————————————>函数调用表达式
// 29 . . . . . . . Fun: *ast.Ident {——————————————>函数调用函数名
// 30 . . . . . . . . NamePos: 4:2
// 31 . . . . . . . . Name: “println”
// 32 . . . . . . . }
// 33 . . . . . . . Lparen: 4:9——————————————>函数调用左括号
// 34 . . . . . . . Args: []ast.Expr (len = 1) {——————————————>函数调用参数
// 35 . . . . . . . . 0: *ast.BasicLit {——————————————>函数调用第一个参数
// 36 . . . . . . . . . ValuePos: 4:10
// 37 . . . . . . . . . Kind: STRING
// 38 . . . . . . . . . Value: “"Hello, World!"”
// 39 . . . . . . . . }
// 40 . . . . . . . }
// 41 . . . . . . . Ellipsis: -
// 42 . . . . . . . Rparen: 4:25——————————————>函数调用右
// 43 . . . . . . }
// 44 . . . . . }
// 45 . . . . }
// 46 . . . . Rbrace: 5:1——————————————>函数体右花括号。
// 47 . . . }
// 48 . . }
// 49 . }
// 50 . Scope: *ast.Scope {——————————————>作用域信息。
// 51 . . Objects: map[string]ast.Object (len = 1) {
// 52 . . . “main”: (obj @ 11)
// 53 . . }
// 54 . }
// 55 . Unresolved: []ast.Ident (len = 1) {——————————————>未识别的Ident，此处为29行的println。
// 56 . . 0: *(obj @ 29)
// 57 . }
// 58 }

方案的可行性分析
语法树是源码的另一种表现形式，他一定包含了源码的所有信息，根据树状的结构，我们也可以很方便的通过递归方式获取想要的元素。

*ast.StructType是我们这次数据结构分析关心的语法元素，我们可以对StructType进行深入的分析，从而找到我们想要的信息。

优劣势分析
相比于直接读取源码，进行模式匹配，语法树的方式更加方便和准确，不需要自己写正则表达式，遍历也更简单。语法树的元素类型提供了更强大的模式匹配能力。

相比于反射方式，语法树可以和待分析的结构解耦，不需要import待分析结构所在的package，对源码的依赖性弱，较为灵活。

劣势是需要预备一些语法树的知识，了解go词法、语法分析的工具链。分析速度比反射稍慢，不过分析一般是一次性的，性能不是主要考虑因素。另一个劣势是，它是静态的，runtime的场景不适用。

还能用ast做什么
ast的功能比较强大，用上面提到的pointer、loader等强大的工具链，我们可以对函数调用关系、对象依赖关系进行更深入的分析。

可以用于代码生成，代码替换，代码写作模式分析（编程规范识别）。

数据结构分析方案二——golang反射特性
阅读资料

Go 语言设计与实现 4.3 反射

反射三定律

反射的简单解释
反射是一种程序能够检查其自身结构的能力，尤其是通过类型信息。这是元编程的一种形式。它建立在golang的类型系统上。

可行性分析
反射是基于类型系统的，而我们要进行的正是类型分析。我们可以通过reflect.Type的Kind枚举得到我们关心的信息，例如哪些是数组，哪些是切片，哪些是结构体。

根据reflect.Value的Field相关函数，我们可以获取一个结构体内部的组成元素。由此递归，即可对数据结构进行分析。

优劣势分析
反射是runtime的，其最大优势也在于此。可以分析运行时的数据结构的内存状态。他仅利用go语言自带的反射包即可完成功能。

其弱点在于侵入性较强，需要import对应的包，编译那个包里的全部内容后，才可进行分析，在静态分析场景，较不灵活。

结果的呈现形式
分析结果最终要可视化，以对人友好的方式展现。

可采用html方式展示，或者通过csv格式，这两种都是简单易编写的方式。

实验
构造如下数据结构。

package astruct

type (
A struct {
Bb []bstruct.B fixType:"optional"
Cc []cstruct.C fixType:"var 2"
Ee []D fixType:"var 2"
Dd []D fixType:"optional"
Ss string fixType:"var 10"
BtFix []byte fixType:"fix 11"
BtVar []byte fixType:"var 12"
}
D struct {
}
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package bstruct

type B struct {
Ee []byte fixType:"var 4"
}
1
2
3
4
5
package cstruct

type C struct {
StrC []string fixType:"var 5"
Dd []uint32 fixType:"fix 6"
}
1
2
3
4
5
6
最终实验结果

astruct.A astruct.A: {160}
—|Bb []bstruct.B: {24}
—|—|bstruct.B bstruct.B: {24}
—|—|—|Ee []uint8: {24}
—|—|—|—|uint8 uint8: {1}
—|Cc []cstruct.C: {24}
—|—|cstruct.C cstruct.C: {48}
—|—|—|StrC []string: {24}
—|—|—|—|string string: {16}
—|—|—|Dd []uint32: {24}
—|—|—|—|uint32 uint32: {4}
—|Ee []astruct.D: {24}
—|—|astruct.D astruct.D: {0}
—|Dd []astruct.D: {24}
—|—|astruct.D astruct.D: {0}
—|Ss string: {16}
—|BtFix []uint8: {24}
—|—|uint8 uint8: {1}
—|BtVar []uint8: {24}
—|—|uint8 uint8: {1}

https://blog.csdn.net/qiankun88888/article/details/107150887

https://draveness.me/golang/docs/part1-prerequisite/ch02-compile/golang-compile-intro/

怎么分析golang源代码
我们拿到一个golang的工程后（通常是个微服务），怎么从词法、语法的角度来分析源代码呢？golang提供了一系列的工具供我们使用：

go/scanner包提供词法分析功能，将源代码转换为一系列的token，以供go/parser使用
go/parser包提供语法分析功能，将这些token转换为AST（Abstract Syntax Tree, 抽象语法树）
Scanner
任何编译器所做的第一步都是将源代码转换成token，这就是Scanner所做的事
token可以是关键字，字符串值，变量名以及函数名等等
在golang中，每个token都以它所处的位置，类型和原始字面量来表示

Parser
当源码被扫描成token之后，结果就被传递给了Parser
将token转换为抽象语法树（AST）
编译时的错误也是在这个时候报告的
什么是AST呢，这篇文章何为语法树讲的很好。简单来说，AST（Abstract Syntax Tree）是使用树状结构表示源代码的语法结构，树的每一个节点就代表源代码中的一个结构。

语法有三个主体：表达式(expression)、语句(statement)、声明(declaration)，Node是基类，用于标记该节点的位置的开始和结束。而三个主体的函数没有实际意义，只是用三个interface来划分不同的语法单位,如果某个语法是Stmt的话,就实现一个空的stmtNode函数即可。

普通Node,不是特定语法结构,属于某个语法结构的一部分.
Comment 表示一行注释 // 或者 / /
CommentGroup 表示多行注释
Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值
FieldList 表示以”{}”或者”()”包围的Filed列表
Expression & Types (都划分成Expr接口)
BadExpr 用来表示错误表达式的占位符
Ident 比如报名,函数名,变量名
Ellipsis 省略号表达式,比如参数列表的最后一个可以写成arg…
BasicLit 基本字面值,数字或者字符串
FuncLit 函数定义
CompositeLit 构造类型,比如{1,2,3,4}
ParenExpr 括号表达式,被括号包裹的表达式
SelectorExpr 选择结构,类似于a.b的结构
IndexExpr 下标结构,类似这样的结构 expr[expr]
SliceExpr 切片表达式,类似这样 expr[low:mid:high]
TypeAssertExpr 类型断言类似于 X.(type)
CallExpr 调用类型,类似于 expr()
StarExpr 表达式,类似于 X
UnaryExpr 一元表达式
BinaryExpr 二元表达式
KeyValueExp 键值表达式 key:value
ArrayType 数组类型
StructType 结构体类型
FuncType 函数类型
InterfaceType 接口类型
MapType map类型
ChanType 管道类型
Statements
BadStmt 错误的语句
DeclStmt 在语句列表里的申明
EmptyStmt 空语句
LabeledStmt 标签语句类似于 indent:stmt
ExprStmt 包含单独的表达式语句
SendStmt chan发送语句
IncDecStmt 自增或者自减语句
AssignStmt 赋值语句
GoStmt Go语句
DeferStmt 延迟语句
ReturnStmt return 语句
BranchStmt 分支语句 例如break continue
BlockStmt 块语句 {} 包裹
IfStmt If 语句
CaseClause case 语句
SwitchStmt switch 语句
TypeSwitchStmt 类型switch 语句 switch x:=y.(type)
CommClause 发送或者接受的case语句,类似于 case x <-:
SelectStmt select 语句
ForStmt for 语句
RangeStmt range 语句
Declarations
Spec type
Import Spec
Value Spec
Type Spec
BadDecl 错误申明
GenDecl 一般申明(和Spec相关,比如 import “a”,var a,type a)
FuncDecl 函数申明
Files and Packages
File 代表一个源文件节点,包含了顶级元素.
Package 代表一个包,包含了很多文件.

https://studygolang.com/articles/19353

https://studygolang.com/articles/6709

http://baixiaoustc.com/2019/01/14/2019-01-14-golang-code-inspector-1-all-case/

怎么分析golang源代码
我们拿到一个golang的工程后（通常是个微服务），怎么从词法、语法的角度来分析源代码呢？golang提供了一系列的工具供我们使用：

go/scanner包提供词法分析功能，将源代码转换为一系列的token，以供go/parser使用
go/parser包提供语法分析功能，将这些token转换为AST（Abstract Syntax Tree, 抽象语法树）
Scanner
任何编译器所做的第一步都是将源代码转换成token，这就是Scanner所做的事
token可以是关键字，字符串值，变量名以及函数名等等
在golang中，每个token都以它所处的位置，类型和原始字面量来表示

通过语法树的方式得到调用连路
https://www.jianshu.com/p/937d649039ec

在一些场景下，需要对一个项目内部的函数调用关系做分析，IDE当然是可以做到一部分。但是对于一个完整调用链，IDE就爱莫能助了。上面列举的第一篇文章讲到的golang AST遍历可以解决这个问题。分析每一个ast.FuncDecl内部的所有调用可能，记录所有A->B的调用关系，可以解决这个问题。不过本文没有直接使用AST，而是运用了golang提供的完备的工具链来实现。

使用golang提供的静态编译工具链
我们依赖了如下三个golang工具链：

“golang.org/x/tools/go/loader”
“golang.org/x/tools/go/pointer”
“golang.org/x/tools/go/ssa”
go/loader
Package loader loads a complete Go program from source code, parsing and type-checking the initial packages plus their transitive closure of dependencies. The ASTs and the derived facts are retained for later use.

这个包的官方定义如上，大意是指从源代码加载整个项目，解析代码并作类型校验，分析package之间的依赖关系，返回ASTs和衍生的关系。

go/ssa
Package ssa defines a representation of the elements of Go programs (packages, types, functions, variables and constants) using a static single-assignment (SSA) form intermediate representation (IR) for the bodies of functions.

SSA(Static Single Assignment，静态单赋值），是源代码和机器码中间的表现形式。从AST转换到SSA之后，编译器会进行一系列的优化。这些优化被应用于代码的特定阶段使得处理器能够更简单和快速地执行。

go/pointer
Package pointer implements Andersen’s analysis, an inclusion-based pointer analysis algorithm first described in (Andersen, 1994).

指针分析是一类特殊的数据流问题，它是其它静态程序分析的基础。算法最终建立各节点间的指向关系
https://www.jianshu.com/p/88bb67a86a4e

https://getstream.io/blog/how-a-go-program-compiles-down-to-machine-code/

https://studygolang.com/articles/15648?utm_source=tuicool&utm_medium=referral

https://github.com/baixiaoustc/go_code_analysis

指针分析
指针分析是一类特殊的数据流问题，它是其它静态程序分析的基础，但指针使用的灵活性导致了指针分析的复杂性，实际上指针分析是一个不可判定问题，所以实际的指针分析算法都是近似且保守的，须在效率和精度之间进行折衷。

指针分析研究的内容主要集中在分析精度和时空开销之间的取舍，精度方面，主要指流敏感性（flow-sensitivity）和上下文敏感性（context-sensitivity），一般而言，流敏感分析方法的精度明显好于流不敏感的分析方法，在上下文敏感性上也有同样的特点。

流不敏感的指针分析普遍使用在开源或者产品级高级编译器中，其中主要有两类：基于包含（inclusion-based）的指针分析和基于合并（unification-based）的指针分析。

基于包含的指针分析是一种基于约束集（constraint set）求解的流不敏感的指针分析方法，该指针分析又称为基于子集（subset-based）的指针分析或者基于约束的（constraint-based）的指针分析，在指针分析领域后来也被称之为Anderson风格的指针分析。其算法的时间复杂度为O(n3)。

https://blog.csdn.net/dashuniuniu/article/details/78704741

https://github.com/baixiaoustc/go_code_analysis/blob/master/second_post_test.go

https://github.com/ofabry/go-callvis
https://github.com/baixiaoustc/go_code_analysis/blob/master/second_post_test.go

https://baixiaoustc.github.io/2019/01/17/2019-01-17-golang-code-inspector-2-reverse-call-graph/

https://zhuanlan.zhihu.com/p/28516587

https://huang-jerryc.com/2016/03/15/%E4%BD%95%E4%B8%BA%E8%AF%AD%E6%B3%95%E6%A0%91/
https://studygolang.com/articles/6709
https://github.com/yuroyoro/goast-viewer
https://draveness.me/golang/docs/part2-foundation/ch04-basic/golang-reflect/

https://blog.golang.org/laws-of-reflection

https://www.jianshu.com/p/937d649039ec

https://studygolang.com/articles/18793?fr=email

https://studygolang.com/articles/6709

https://blog.csdn.net/weishixianglian/article/details/104262105/

http://www.voidcn.com/article/p-gtfajmmt-bvq.html

https://www.cnblogs.com/skzxc/p/12944921.html

https://blog.csdn.net/qiankun88888/article/details/107150887
https://zhuanlan.zhihu.com/p/28516587
https://juejin.im/post/5db7195df265da4d104b7fb7