Go+ 探究：如何 10 天实现工业级的 C 编译器
上周发表的《》引起了非常大的反响，小伙伴们纷纷表示支持，不少人就问起这个事情的时间表到底如何。
方向定了，时间表首当其冲，这最正常不过。其实当我把要做 c2go 这个想法发到 Go+ 贡献者群，并且解释了整个项目的执行思路后，小伙伴们问的第一个问题也是：“方向不错，计划第一个版本什么时候出来？”
我没有犹豫，回答：半年。过了一会，我补充了一句：“半年是最悲观的估计”。是的，我认为并不需要半年。理想情况下，三个月内就要有结果。
怎么才算 Go+ 完美兼容了 C 语言？半年内我们要出什么样的结果？
在我设想中是这事要分三步走：
第一步，实现对 C 语法的支持，将各类 C 语法转换为对应的 Go 代码来表示。这一步重点是支持 C 语言文法本身，如果功能测试或展示需要涉及到 C 标准库，就用 Go 来 mock 一个。我们以 Hello world 程序为例：
因为是以验证 C 语法为主，这个 Hello, world 比经典版本要复杂一些。我们设想通过 c2go hello.c 这样的命令行来运行这个例子。简单考虑我们就会发现，大部分代码都只需要考虑它的语法对应到 Go 语言需要翻译成什么样子，但是里面的 printf 是 C 标准库中的函数，Go 并没有对应的函数可以进行映射。
我们找到 printf 的源代码，也通过 c2go 进行翻译？这理论上来说当然可行。但是这样问题域就被扩大了，不再是一个简单的 Hello world。我们可能只是想验证一下我们已经支持的 C 语法，比如定义整型常量、定义字符串变量、函数调用等。而 printf 可能代码可能会非常复杂，甚至可能会涉及部分的汇编代码，这些会导致我们想要做的最小化验证变得困难。
怎么办？我们在 hello.c 同目录放一个 libc.go 文件，用 Go 来 mock 一个 printf 函数的实现。一个典型的 printf 函数的 mock 长这样：
这当然并非准确的 printf 函数的行为复现。只是虽然其行为不完全和 C 库的 printf 一致，但用来验证我们的例子程序是否正常工作绰绰有余（只需要在 mock 中实现了例子中用到的 printf 的功能即可）。
这样，在 c2go hello.c 运行时，它会先把 hello.c 转换为 Go 代码，比如叫 hello.go（实际上我们取的名字是 hello.c.i.go，这个名字体现了我们转换的流程，下文详细展开），然后调用 go run *.go 将 hello.go 和 libc.go 一起编译成可执行文件来执行。
第二步，将 C 标准库转化为 Go 模块，并且支持在 Go+ 中进行 import。这一步有两个相对独立的工作：一个是 C 标准库转为 Go 代码，一个是在 Go+ 增加一些对 C 的支持。
大部分工作量集中在 C 标准库转为 Go 代码这个过程上。这里面可能会遇到的麻烦主要分为以下几类：
其一，某个 C 库函数的实现使用了汇编。这种情况下，我们需要让转换程序忽略该函数，我们用 Go 手工实现一个。
这件事情的工作量，完全取决于 C 标准库到底用了多少汇编代码，这决定了我有多少个需要手工实现的函数。
其二，Go 与 C 线程模型的差异。Go 语言中是 goroutine，C 语言用的是操作系统的线程。最典型的，是 goroutine 并不支持 TLS（线程局部存储）。如果我们用 goroutine 来实现 C 的 pthread 标准库，无疑工作量会非常大。但如果我们用操作系统的线程，则与 Go 的代码在协同上会有很多坑。我们不能在普通 Go 代码中调用 pthread 的线程协同机制进行协同，也不能在 pthread 线程下运行的 Go 代码中调用 Go 的 "sync" 标准库，这些行为都可能将导致 Go 程序的行为不可预期。
如何决策？这个问题我们留待以后讨论。
最后，我们还可能会遇到未实现的 C 语法。不管我们前面第一步支持的 C 语法多么全，哪怕我们把最新的 C spec 都 100% 实现了，也不代表我们不会在转换 C 标准库的时候遇到语法问题。因为，每个编译器都有自己的扩展语法，而很可能在某个 C 标准库的实现上，就会用到了这样的扩展语法。
当然这个障碍可能是几个问题中是最小的。不支持，那就加上呗。新增一个语法支持的工作量并不算高。下文我们在谈及我们的正题，如何 10 天内实现 95%+ 以上的 C spec 支持，大家可能会更加有体会。
同样的道理，在 Go+ 增加一些对 C 的支持，它主要体现为 import "C" 和引入 C 字符串 C"..." 等有限的新语法上，工作量也并不太多。
第三步，支持各类第三方的 C 库。这包括支持各类知名的 C 开源库（比如 sqlite），以及用户自己（公司或个人）积累下来的 C 库。
那么，半年内我们要得到什么样的结果？
最低限度，要实现上面的第一步和第二步，也就是支持绝大部分的 C 语法，以及迁移完最常见的 C 标准库。如果有可能，对第三步做一个示范，迁移一个知名的开源库，大概率我们也会选择 sqlite。
如果没有好的路径，这个事情做起来很难。在《》里面我们提到了 github.com/elliotchance/c2go 这个项目，从 2017 年开始到今天已经 5 年了，迁移 sqlite3 的小目标没实现。最近一周我发现了另一个项目 gitlab.com/cznic/ccgo，它也是 5 年前开始的，完成度更高一些，实现了一个 libc（gitlab.com/cznic/libc），也成功迁移了 sqlite（gitlab.com/cznic/sqlite）。
看起来它似乎已经实现了我们想要的目标？但是我研究了一下发现，ccgo 并不是全自动化的编译，而它实现的 libc 也并不和 C 标准库兼容。
为什么他们 5 年没有干成的事情，而我们半年就可以实现？
这里面最重要的，其实是第一步，实现对 C 语法的全面支持。C 标准库用的汇编再多，也终归是有限的，最后总能够找到办法绕过去。但是 C 语言文法上的兼容度，是实现无人工干预，全自动化转换最重要的基础。否则我们即便是可以转换 sqlite，但是整个迁移的经验不可复制，并不能让更多的项目因此受益。
实现一个兼容最新的 C spec 95%+ 以上功能的 C 编译器，要多久？
我们给出了非常精准的答案：10 天。
你可能觉得不可思议，但这是真的。github.com/goplus/c2go 这个工程创建到今天是第 11 天，而 C 语法支持的工作于昨天正式告一段落（我们发布了 github.com/goplus/c2go/releases/tag/v0.3.2，即 c2go v0.3.2 版本）。
我们先来看看我们对 C 语法的支持情况：
通过这个表可以看出，我们的确还有非常少量的 C 语法没有去支持，但是并不是因为它们实现起来比较难。事实上最难的几个功能点：
指针（比 Go 的功能强所以难，指针可以移动，可以当数组用）
联合体（即 union，在 Go 语言没有对应语法）
BitField（在 Go 语言中没有对应语法）
都已经得到了支持，在 Go 中实现所有 C 语法的可行性已经被证明，后面在需要时候加上这些未实现的功能比较简单。
为了验证我们的确已经实现了所有这些功能，我们这里提供了一些测试用例：
https://github.com/goplus/c2go/tree/main/testdata
这些测试用例分为两类。一类是测试特定的语法上的，比如：
https://github.com/goplus/c2go/tree/main/testdata/hello（基础语法）
https://github.com/goplus/c2go/tree/main/testdata/flow（控制语句）
https://github.com/goplus/c2go/tree/main/testdata/operator（操作符）
https://github.com/goplus/c2go/tree/main/testdata/struct（结构体）
https://github.com/goplus/c2go/tree/main/testdata/union（联合体）
https://github.com/goplus/c2go/tree/main/testdata/bitfield（BitField）
https://github.com/goplus/c2go/tree/main/testdata/complex（复数）
https://github.com/goplus/c2go/tree/main/testdata/init（变量初始化）
另一类是 C 标准库迁移的尝试（也就是第二步工作的前置），比如：
https://github.com/goplus/c2go/tree/main/testdata/strlen（取字符串长度）
https://github.com/goplus/c2go/tree/main/testdata/printf（文本显示）
https://github.com/goplus/c2go/tree/main/testdata/qsort（快速排序）
标准库的迁移有验证我们 C 语法支持的成分，但也在为我们第二步的工作量评估做基础。这三个函数的选择有一定的考究。
strlen 是一个简单的算法（但也比大家想象的要复杂），适合作为第一个迁移验证的例子。
printf 大家想象可能觉得复杂，但是单独看它是简单的：
因为它底层实际上调用的是 vfprintf，自己并没有做什么。我们为什么选择迁移 printf，更多是为了验证我们对支持不定参数的函数是否能够正确处理。以下是我们转换后的结果：
强调一下，所有这些转换都是自动的，没有任何人工干预。
qsort 代码量比较长，我们把它作为我们第一步（对 C 语法支持）的阶段结束。附图是我们验证 qsort 迁移成功的示例：
从这段代码实际上已经可以看到未来 Go/Go+ 调用 C 的样子。只不过因为还没有支持包（ package）的功能，所有代码在同一个包里面，所以这里直接用 qsort，未来需要改为 C.qsort，其他不变。
那么重点来了，我们究竟做对了什么，让我们可以在 10 天实现一个工业级的 C 编译器？
我们对比一下与 github.com/elliotchance/c2go（我们简称 ec2go）、gitlab.com/cznic/ccgo（我们简称 ccgo）这两个方案的差异。
其一，C 预处理过程（preprocessor）的选择。这点我们和 ec2go 一致，让 C 编译器来处理。而 ccgo 选择了自己实现（gitlab.com/cznic/cc，里面包含 C scanner, preprocessor, ast 以及 parser）。
在我们规划里面，preprocessor 我们永远都不会自己做，甚至相反，我们最终会支持多数主流的 C 编译器。这背后考虑的主要因素有：
首先，preprocessor 功能看似比较简单，但是实际上负责了 C 语言对平台适应性的主要工作，这个过程细节较多，不同编译器的差异较大。每个 C 的开源库都有自己 C 编译器的采纳习惯，我们如果硬是给改成其他 C 编译器，遇到编译问题的挑战会比较多。
其次，就算我们自己实现了 preprocessor，它也通常不是编译的起点。我们知道大部分开源项目都有 ./configure 脚本，它背后是 autoconf 这样的工具，通过它与 C preprocessor 配合，达到适应不同平台实现自动化配置的目的。所以替换 preprocessor 意味着我们还要把它和 autoconf 进行整合。
而在 preprocessor 过程结束后，生成的 C 代码是不带任何 include 语句的一个大文件，这个文件中用的 C 语法，在不同编译器之间的差异化减少到了最小。
其二，C 文法的解析（C parser），将 C 源代码解析为 C AST。这点我们和 ec2go 一致，由 clang 这个 C 编译器来处理。而 ccgo 选择了自己实现（gitlab.com/cznic/cc）。
实现 C parser 的工作量并不算大，最终我们也会倾向于自己干。但这总归帮我们暂时省下来一块工作量。
其三，C AST 转 Go AST 过程。这个过程工作量最大，也最为关键（此后的第四步 Go AST 到 Go 源代码，大家都一样，都是调用 go/format 标准库来实现）。
这也是三个方案差别最大的部分。
ec2go 并没有用到任何特殊的技巧，直接操作 C AST，并裸写 Go AST。
ccgo 的规划非常大。它引入了自己的 ir（internal representations，熟悉编译器的人可能比较了解 ir 的概念，我们这里略过）作为中间转换的标准。所以 ccgo 并不是直接转 C AST 到 Go AST，而是先 C AST 到 ir（gitlab.com/cznic/ccir），然后再 ir 到 Go AST（gitlab.com/cznic/irgo）。
这种做法当然有它的好处，但是不幸的是，它也让工作量放大了许多。
那么我们的方案是什么样的呢？
其实，我们的方案和 ccgo 在大方向上是类似的，我们也引入了 ir，只不过我们没有选择自己定义一种新的 ir，而是认为 Go AST 就是 ir。
为什么我说 Go AST 我们把它看做 ir？因为 Go+ 语言的编译器编译的时候，会实现 Go+ AST 到 Go AST 的变换。我们的 c2go 会实现 C AST 到 Go AST 的变换。未来我们在做大数据生态的时候，可能还会实现 Python AST 到 Go AST 的变换。所有语法变换以 Go AST 作为中间的桥梁，这可以大幅提升组件之间的互操作性。
例如，我们基于 Go AST 实现了一个虚拟机（github.com/goplus/gossa），那么所有我们 ir 生态里面的语言，无论是 Go+ 还是 C，就可以直接基于字节码来执行。
那么为什么选择 Go AST 作为 ir？因为它是最稳定的，并且广为人们接受的标准。定义一个新的 ir 是很容易的。但是：
如何保证这套 ir 的稳定性，长期保持其使用接口的不变？
如何为这套 ir 构建繁荣的生态？
Go 语言是最吝啬增加新功能的语言之一，所以基于 Go AST 作为 ir，我们能够减少因为 ir 实现上的调整，导致生态中的上下游需要跟着变化。
当然，选择 Go AST 作为 ir 并不会降低我们做 C AST 转 Go AST 的工作量。真正让我们提高开发效率的是我们基于 ir 构建的能力层：ir 的 DOM Writer 组件 gox（github.com/goplus/gox）。
简单说，gox 是方便你生成 Go AST 的工具。但是它与普通的 Go AST 生成工具又很不一样。一种非常直白的 Go AST 辅助生成工具可能是这样的：
func NewInt(v int) *ast.BasicLit
func NewString(v string) *ast.BasicLit
func BinaryOp(op token.Token, a, b ast.Expr) *ast.BinaryExpr
有了它们，表达 100 + "Hi" 这样的运算，就可以直接调用 BinaryOp(token.ADD, NewInt(100), NewString("Hi")) 来生成对应的 Go AST。
但是这对 C AST 到 Go AST 的转换工作减负并不大。NewInt(100) 只是 &ast.BasicLit{Kind: token.INT, Value: "100"} 的简写，少敲了几个字符而已。
在 gox 中，100 + "Hi" 这样的运算被转换为类 “逆波兰表达式” 的调用方式：
var cb gox.CodeBuilder
cb.Val(100).Val("Hi").BinaryOp(token.ADD)
但调用的语法形式并不是重点。重点是：这里 gox 在执行 BinaryOp(token.ADD) 的时候会报错，告诉你整数和字符串不能执行 + 运算。gox 的所有操作都是有类型推导能力。再如函数调用的例子：
fmt := pkg.Import("fmt")
cb.Val(fmt.Ref("Println")).Val("Hi").Call(1)
这段代码可以判断：fmt 包有没有 Println 函数，函数传入的参数列表每个参数的类型对不对，函数调用后的返回值是什么类型，等等，它最终生成的 Go 代码是：
import "fmt"
...
fmt.Println("Hi")
这有什么好处？
我们拿 C 的 binaryOp 与 Go binaryOp 的差异作为例子。当我们要把 C 语言中的 a + b 翻译成 Go 语言的代码时，并不总是简单把它翻译成 a + b。我们至少要要考虑这样一些情况：
首先，a 可能是一个指针类型（*T），b 是一个指针要移动的步长。对于这种情况，翻译成 Go 代码需要变换为 (*T)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) + sizeof(T)*b))。
其次，a 和 b 可能类型并不匹配。比如 a 是 int，b 是 short。由于 Go 并不会像 C 一样做隐式的类型转换，所以翻译成 Go 代码就需要变换为 a + int(b)。
我们可以看到，将 C 的 binaryOp 转为 Go binaryOp 是需要根据 a 和 b 的类型信息进行判断的。也就是我们不能只有语法上的上下文，我们还需要语义上的上下文。而在 gox 中有每一个表达式的类型信息，在这一点上就给用户提供了极大的便捷性。
gox 的类型推导能力的强大，还体现在它可以自动推导闭包的参数和返回值的类型上。
我们再举一个将 C 的 a++ 转化为 Go 语言代码的例子。它其实挺复杂，因为我们要考虑以下这几点：
首先，a 可能是一个指针类型（*T）。对于这种情况，翻译成 Go 代码需要变换为 *(*uintptr)(unsafe.Pointer(a)) += sizeof(T)。
其次，C 语言的 a++ 并不是一个语句（statement），而是一个表达式（expression），它有返回值。这意味着简单翻译成 Go 语言中的 a++ 哪怕对非指针的情况下也是错误的。不考虑 a 是指针的情形，正确的翻译应该是：
func() (ret T) {
addr := &a
ret = *addr
*addr++
return
}()
其中，类型 T 表示 a 的类型。但是它是要等我们编译 a 的时候才能知晓，并不是一个可以提前拿到的信息。但是由于 gox 支持自动推导能力，创建闭包的时候我们简单声明返回值为自动类型即可。具体闭包的生成代码看起来是这样的（为简化，部分函数调用去掉了语义不相关的参数）：
// func() (ret T) {
ret := pkg.NewAutoParam("ret")
cb.NewClosure(nil, types.NewTuple(ret), false).BodyStart()
// addr := &a
cb.DefineVarStart("addr")
compileExprLHS(a)
cb.UnaryOp(token.AND).EndInit(1)
// ret = *addr
addr := cb.Lookup("addr")
cb.VarRef(ret).Val(addr).Elem().Assign(1)
// *addr++
cb.Val(addr).ElemRef().IncDec(token.INC)
cb.Return(0) // return
cb.End().Call(0) // }()
仔细阅读这段代码，感受它背后完成的复杂性，你方可感受到 gox 对于 Go AST 这个 ir 的支持有多强大。
所以和 ccgo 不一样的是，我们不只是引入了 ir，它通常只是一个规范，只是基础的一些数据结构。更重要的是，我们还基于 ir 提供了完整的生产力工具。
如果说上面的介绍还不能让你有直观的我们节约了多大的工作量，那么我们列几个关键包的代码行数（不含注释、空白以及测试案例）：
go/types (基于 go v1.18 统计)：1.3万行
github.com/goplus/gox：1万行
github.com/goplus/gop：1.8万行
github.com/goplus/c2go：0.3万行
为什么我们统计了 go/types 这个包？因为 gox 重度依赖 go/types，而这也是 ec2go 和 ccgo 这两个并没有依赖的。
为什么 go/types 很重要？这个包为什么代码量会这么大？
我们可以简单把 go/types 的代码分为两部分：Go 类型系统 DOM API，以及根据 Go AST 生成 Go 类型信息的工具（主要指 types.Checker 类）。
这是 Go 标准库唯一的 Go 语义分析相关的库。借助它做类型推导就会轻松很多。当前 gox 主要依赖 go/types 的 Go 类型系统 DOM API 那部分，初略估计这应该占整个包一半以上的代码。types.Checker 同样非常重要，未来 gox 也会用到（关于这一点，后面我们单独介绍）。
从根本上来说，gox 和 go/types 的思路是非常相通的：他们都是一种 DOM API。只不过 go/types 只处理 Go 语义分析中的类型系统部分，而 gox 处理 Go 语法完整的语义系统。所以 go/types 天然是 gox 不可分割的组成部分。这一点从 gox 对外暴露的 API 接口就可以看出来。对于大部分 gox 依赖的 package，通常它们在 gox 的对外接口中并不体现，只是一种实现上的依赖。而 go/types 在 gox 的外部接口中到处都是，它已经成为 gox 不可分割的组成部分。
最后总结：虽然目前 c2go 只有 0.3 万行代码，但是这是建立在它重度依赖 go/types + gox（合计 2.3 万行代码）的基础上的，所以你可以认为 c2go 业务相关的代码实际上是 2.6 万行。同样，Go+ 自身的代码是 1.8 万行，但是它也同样建立在重度依赖 go/types + gox 基础上的，所以 Go+ 业务相关的代码实际上是 4.1 万行。
而这，才是我们能够实现 10 天做一个工业级的 C 编译器的真正原因。