本科生毕业设计 [论文]
面向内存安全的并发编译器
院 系 网络空间安全
专业班级 信安1 805
姓 名 李博修
学 号 U 201811662
指导教师 代炜琦
2 022 年 5 月 4 日
学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包括任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。
作者签名： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士论文评选机构将本学位论文的全部或部分内容编入有关数据进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本学位论文属于 1、保密囗，在 年解密后适用本授权书
2、不保密囗 。
（请在以上相应方框内打“√”）
作者签名： 年 月 日
导师签名： 年 月 日
摘 要
此编译器和其配套的新语言“Calc”，在具有与C类似的底层功能与性能的同时能提供Java级别的内存安全保障，并且不需要如同Rust一样加入繁琐的安全检查。该语言实现了现代语言的大部分先进特性，例如泛型、接口、闭包与无栈协程等。编译器主要实现了前端部分，生成llvm ir，后端使用llvm进行编译。编译器本身附带一个language server，能给出很多诊断信息，甚至自动补全信息并且不会因为语法错误而停止分析。其编译速度经过并发优化，能达到1 3 秒编译1, 000,000 行源代码。
关键词： 编译器 ； 内存安全 ； 并发编译 ； 高级语言
Abstract
The compiler and the new language named “Calc”, which has functionality and efficiency almost same as C and can provide memory-safe guarantee as same as Java, without compile time safety-check like Rust. It has many edge-cutting features such as closure, duck-type interface, generics, stack-less coroutine and so on. The compiler is basically a frontend generating llvm ir, using llvm as its backend. It’s built with a language server which can generate diagnostic messages on-the-fly and give autocomplete recommendations. It can compile up to 1,000,000 lines of Calc code in 13 seconds.
Key Words： Compiler; Programing language ; Memory safe ; Parallel compile
目录
世界上存在众多的语言与编译器，广泛使用的有以Java为首的依赖虚拟机（运行时）的语言和以C、C ++ 为首的底层静态编译语言。 现代高级编程语言如Java之类，往往为了内存安全而隐藏指针操作。本编译器将使用独特的栈逃逸分析算法，在允许用户使用指针的同时能在编译期间发现可能产生悬挂指针的地方，自动的更改内存分配地点。
这种设计使得语言 在具有低级语言的能力的同时，拥有一些较高等级的语言特性和安全保证。同时，本语言会构造并发的编译系统，解决c/cpp等低层次语言编译速度过慢的问题。
语言将引入Garbage Collector来进行内存的自动分配和回收。尽管Rust已经证明了语言依靠静态检查就足以避免很多的内存问题 [1] ，但是加入这种静态检查无疑增加了编译时的损耗，并且这种类似引用计数的检查方法无法处理循环引用的问题，使得Rust在不使用unsafe时难以实现双向链表 [1] 。
G C 采用mark -and-sweep 方法，尽管一些基于引用计数的回收算法一般具有更高的性能，但是初代的引用计数无法处理循环引用情况（会造成memory -leak） [2] ,而改进版的引用计数则常常需要引入弱指针等机制，对使用者造成额外的负担。
同时，语言尽可能的添加了一些现代化功能，例如闭包、泛型、接口、无栈协程、模块化、包管理等等，其编译器也支持并发编译以提高效率。
C alc 编译器在借鉴众多已有语言独特功能的同时，加入了自身的独特设计以保证协程、内存分配等方面的安全性。
编译分为词法分析、语法分析、中间代码生成、代码优化与目标代码生成几个步骤 [3] 。其中的代码优化与目标代码生成我采用llvm，因此我需要自行设计实现的是词法分析、语法分析和中 间代码生成的三个步骤。lexer用golang手写，避免了正则表达式的性能问题。而parser使用递归下降分析法，手动进行实现。在编译时 P arser通过使用Lexer获取一个一个token来对源码进行分析并且生成ast，之后通过遍历ast来生成中间代码。
Calc编程语言的文法规则如下：
program: P -> PD NL * IS ? ( FN | NL | T | D | DA ) +
call_func: CF -> VC GPC ? LP ( RP | ( E ( COMMA AE ) * RP ) ) ( DOT CF | VC ) *
generic_params: GP -> SM var ( COMMA var ) * LG
generic_call_params: GPC -> SM TYPE ( COMMA TYPE ) * LG
function: FN -> FUNC var GP ? FPS TYPE ASYNC ? SB
func_params: FPS -> LP ( RP | ( EFP ? FP ( COMMA FP ) * RP ) )
ext_func_param: EFP -> THIS FP
func_param: FP -> var TYPE
statemnt_list: SL -> S +
statement: S -> CS | BS | EM | D | A | R | ( CF NL ) | I | ( DA NL ) | YI | ( AWAIT AE )
return: R -> RET | ( RET AE )
empty: EM -> NL
yield: YI -> YIELD AE ? NL
define: D -> VAR var TYPE NL
inline_func: IFUN -> FT ASYNC ? SB
all_types: TYPE -> MUL * BTYPE | AT | ST | IT
basic_types: BTYPE -> tp GPC ?
array_types: AT -> LSB n ? RSB TYPE
func_types: FT -> FUNC FPS TYPE
type_def: T -> TP var GP TYPE
struct_type: ST -> STRUCT LB ( ( var TYPE NL ) | NL ) * RB
interface_type: IT -> INTERFACE LB ( ( var FPS TYPE NL ) | NL ) * RB
asssign: A -> MUL * VC ASSIGN AE
all_exp: AE -> BE | TPE | IFUNC | ( AWAIT AE )
exp: E -> AF ( ( SHL | SHR ) AF ) *
bool_exp: BE -> BO ( ( AND | OR ) BE ) ?
bit_op: BO -> C ( ( BO | ESP | XOR ) C ) *
compare_exp: C -> ( B ) ( ( EQ | NEQ | LG | SM | LEQ | SEQ ) ( B ) ) *
boolean: B -> TRUE | FALSE | E | NE | ( LP BE RP ) | NOT B
added_factor: AF -> F ( ( ADD | MIN ) F ) *
factor: F -> S | S ( ( MUL | DIV | PS ) S ) *
symbol: S -> N | ( ( ADD | MIN ) N )
number: N -> n | ( LP E RP ) | TVE | SE
statement_block: SB -> LB SL RB NL
def_ass: DA -> var DEFA E | VAR var ASSIGN E
if_st: I -> IF BE SB ( ( EL SB | I ) ? )
for_st: F -> FOR ( DA ? SEMI BE SEMI A ? ) ? SB
break_statement: BS -> BR NL
continue_statement: CS -> CT NL
struct_init_exp: SI -> ( var LB ( ( var COLON AE COMMA ) | NL ) * RB )
array_init_exp: AI -> AT LB ( ( AE COMMA ) | NL ) * RB
take_ptr_exp: TPE -> ESP AI | SI | VC
take_val_exp: TVE -> MUL * AI | SI | VC | CF
var_chain: VC -> VB ( DOT VB ) *
var_block: VB -> var ( LSB AE RSB ) *
null_exp: NE -> NIL
pkg_declare: PD -> PKG var
string_exp: SE -> str
import_statement: IS -> imp str | imp LP ( ( SE var ? ) | NL ) * RP
idx_op_reload: IOR -> OP LSB RSB LP EFP COMMA FP RP TYPE SB
Calc的保留字有两种，分别是内置类型和关键字。这些保留字不能作为变量名或者函数名。
目前的calc内置类型共有1 0 种，分别是：
1. int：默认整数类型取决于系统架构， 32 位系统就是3 2 位，6 4 位就是6 4 位
2. float：默认小数类型取决于系统架构， 32 位系统就是3 2 位，6 4 位就是6 4 位
3. int3 2 ：3 2 位整数
4. float3 2 ：3 2 位小数
5. int 64 ：6 4 位整数
6. float 64 ：6 4 位小数
7. void ：void类型
8. bool ：布尔类型
9. b yte ：字节类型，int 8 或char
10. s tring ：在系统库中定义，定义名为String，这是一个编译器李支持的别名
目前的calc关键字共有 21 种，分别是：
1. v ar：声明变量
2. f unc ：声明函数
3. r eturn ：返回
4. t rue ：布尔真
5. f alse ：布尔假
6. i f ：条件判断
7. e lse ：条件判断
8. f or ：循环
9. b reak ：跳出循环
10. continue ：继续循环
11. t ype ：类型定义
12. s truct ：结构体
13. t his ：定义方法
14. i nterface ：接口
15. n il ：空值
16. p ackage ：定义包
17. import ：导入包
18. o p ：运算符重载
19. y ield ：状态机
20. a sync ：异步方法标记
21. a wait ：异步原语
逃逸分析使用修改后的快速逃逸分析算法 [4] 。逃逸分析的本质是对源码进行分析后构造一个call - graph，创建出变量之间相互赋值的网络。然后找出可能造成栈逃逸的逃逸点，从逃逸点开始反推所有会逃逸的变量。
逃逸分析需要额外遍历一次ast，但是由于遍历时可以跳过大部分的节点所以并不会消耗太多时间。在便利的过程中使用hashmap记录所有的赋值语句（key为被赋值变量，value为值变量列表），遍历之后hashmap里保存的内容就构成了一张图。遍历的同时也要将所有的逃逸点保存在另一张表里，在遍历结束之后遍历所有的逃逸点，从逃逸点开始沿着图的边遍历所有可达变量，将这些变量标记为应该逃逸，这样在生成中间代码的时候就可以进行特殊的处理。
逃逸点一般有以下四个地方：
1. 函数返回值
2. 函数形参
3. 函数实参
4. 被闭包捕获的变量
逃逸点与作用域变化息息相关：如果变量的生命周期超过当前作用域，那么他就是逃逸点。
其中函数返回值和实参是比较容易理解的逃逸点，因为这两个值都是跨越作用域传递的。而形参也是逃逸点，是因为形参在调用时对应的实参的生命周期对于一个函数来说是不可知的，如果它对应的实参被判定为逃逸，那么如果不把它标记为逃逸点，在函数中对形参的某个字段赋值的时候这个值将存在于栈上，在函数执行完之后栈就被销毁了而形参对应的实参却仍然引用着这个值，之后如果访问这个值将造成Memory -Access Violation 错误，这也是通称的“野指针”问题。所以为了避免这种情况，函数的形参也是逃逸点之一。
闭包对逃逸分析的影响比较复杂，在之后的闭包章节仔细解释。
模块化方面，类似C语言的方法，直接使用类似源码合并的方案，并没有使用llvm模块功能。实际上在编译时整个程序都会对应一个llvm模块。
Calc的模块申明文件叫做 calc.mod ，这个文件类似golang里的go .mod ，它只会出现在一个Calc项目的根目录。里边需要声明该目录的模块名，之后它之下的任何目录都是以该模块名为前缀的子模块，子模块的模块名为父模块名加上斜杠和文件夹名。
Calc的第三方模块必须是git repo的网址。目前版本中引入的第三方模块不需要特殊在某个文件中声明，只要在某个文件里import了对应的第三方模块，然后运行以下clacc，calcc就会自动clone对用的git repo。目前无法限定第三方库的版本。
Calc在安装的时候会有一个对应的语言根目录，同时它会设置对应的环境变量。该环境变量名为CALC_BIN，在Windows上它下边会安装编译所需要的bdwgc与libuv的链接文件，动态链接库，calc前端编译器，和真正的编译命令calcc的执行脚本calcc. ps1 ；在Linux上这里不会有bdwgc和libuv的链接文件与动态链接库，这些东西会被安装脚本安装到用户的lib目录去。同理别的可执行文件和calcc .sh 脚本会被安装到用户的bin目录去。而在引入第三方库依赖时，所有的第三方repo都会被克隆到CALC_REPO目录下。目前这个目录没有加任何保护措施，以后应该会把它改为只读权限。
但是与C不同的是，Calc的所有函数与结构体、接口都是免提前申明的，而且类似golang可以分布在一个文件夹下的不同文件里，也没有头文件。为了实现这些特性，我设计了一种叫“代码提前”的方法。
具体而言，在生成中间代码时，所有的结构体都会被提到模块的最开头尝试进行定义。如果发现某个结构体引用了一个未定义的结构体，那么将该结构体的定义放入失败列表，继续定义剩下的结构体。全部定义完后，将失败列表的结构体取出重复上述步骤，直到所有结构体定义完成。如果某次迭代中没有任何新的结构体被定义，则代表代码中引用了未定义的结构体。
在此之后，会将所有在本模块中定义的函数进行提前声明，然后剩下的代码进行正常顺序的编译。
在Calc语言中，循环引用时不被允许的，循环引用可能导致编译器进入死循环，因此必须有一种机制来在编译时发现循环引用。Calc的编译是以模块为单位的，每个模块在编译的时候会找它自己引入的其它模块，如果这个模块没有编译过则调用方法线编译该模块。因此为了找出循环引用，编译模块的函数会相互传递一个上下文变量，这个变量里边有个哈希表，记录了这个编译路线里出现过的所有模块，如果某次调用函数的时候发现上下文里已经存在当前模块，则代表出现了循环引用。
在上述内容之后，应该容易发现编译过程中有以下部分可以并发进行：
1. 一个模块中的不同文件可以并发进行语法分析
2. 不同不相干模块可以进行并发的编译
Calc实现了以上两种并发。具体而言，在编译同意模块的时候，不同的文件是并发进行语法分析的。在它们分别生成了各自的抽象语法树之后，会使用特殊的同模块语法树合并算法进行合并。而不相干的不同模块本身也可以轻松进行并发，虽然有一些部分需要进行同步。
目前能实现并发的部分其实只有词法分析和语法分析，中间代码生成必须串行，这是为了保证模块顺序的正确性。而并发编译本身在一些情况下也肯能造成一些不好的影响，比如每次编译生成的中间代码不一样，这对手动检查中间代码进行debug很不友好。
事实证明并发编译对速度的加成是显著的，在笔者机器上进行的测试表明，1 ,000 , 000 行源代码的Calc程序只需要1 3 秒就可以编译成llvm ir。
为了保证不同的模块在编译之后不会出现相互冲突的符号、能够顺利合并到一起，同时为了生成的中间代码具有一定的可读性，需要规定一种从源码中的id映射到中间代码的id的映射方案。
Calc符号映射方案如下：
1. 所有的Symbol名映射的时候加上模块名前缀和“.”，比如main模块中的main方法的中间代码签名就是m ain.main
2. 所有的扩展方法，由附属类型的全名加上方法名组成。比如main中的结构体Struct有名为Add的扩展方法，那么映射后的签名就是m ain.Struct.Add
3. 所有泛型的签名加上尖括号和具体类型参数，详见2 .6
作为一个目标为现代化高级语言的计算机语言，泛型是不可或缺的一部分。Calc语言的泛型使用代码膨胀方法实现 [5] ，而非Java的类型擦除方法。
尽管有数量不少的语言（Java等）早期选择使用类型擦除来实现泛型，并且证明了类型擦除是个可行的实现泛型的方案，其对性能造成的影响仍然是很明显的。 Jaime Niño 在他的文章中表示Java使用类型擦除的做法，不仅影响到了程序的性能，也影响到了整个语言的类型系统 [6] 。
因此，尽管会引入额外的复杂性，我还是使用了代码膨胀的做法。具体而言，一个泛型方法/结构体定义的时候，并不会生成对应的中间代码，它们会在被实际使用的时候再生成对应的方法/类型。也就是说在中间代码中的多个函数可能对应单个泛型函数。
为了使用者方便，我实现了泛型推断的功能：每次使用泛型的时候，都需要写全泛型的类型参数是一个很烦人的事情，而这个做法其实是没必要的，因为编译器大部分情况下已经可以从返回值或者入参的类型来推断出泛型参数的类型。所以我使用了一个简单的上下文机制，并且在生成函数调用代码的时候先生成参数对应的代码，并记录每个参数的类型。这样在最后生成泛型函数的时候就可以通过提前记录的参数类型对泛型进行一些推断 [7] 。
然而需要注意的是泛型推断并不是万能的，泛型推断尽管在很多情况下都足以应对，但是对于一些特殊定义的系统泛型函数泛型推断是不起作用的。另外如果你希望输入的值类型在输入时进行隐式的类型转换，那么当然也要显示的写出泛型参数。另外在一些信息不足的情况下泛型推断也会出现问题，并且目前Language Server并不会针对泛型参数给出建议。
另外，目前的泛型推断设计并不美观，急需重构，本身似乎也有一些比较难以发现的bug。所以目前版本不建议过度依赖泛型推断功能。
一个健壮的泛型系统一定会面对这样的情况：一个泛型函数里用泛型作为泛型参数调用了另一个泛型函数。为了让泛型参数可以在实际生成泛型方法的实现时传递给内部的其它泛型元素，上下文中需要额外增加一个泛型映射表，从泛型的形参映射到实参。并且必须注意这个表每次传递给内部作用域的时候必须复制传递，不能引用传递。否则有可能出现以下情况：内部的泛型元素覆盖了表中的某个泛型参数，而超出该元素作用域之后外界看到的表里的泛型映射关系已经变成了覆盖之后的，泛型类型发生了改变。这会导致严重的内存安全问题。
泛型带给现代语言的加持无疑是明显的。实现泛型之后，实现链表再也不需要像golang那样进行拆装箱，可以用很少的代码实现万能的容器。
另外本语言是极少见的泛型结合Duck -type 接口的语言，这带来了一些之前从未在其它语言中见过的有趣特性。比如似乎泛型不再需要泛型约束语法了，我目前还没遇到必须要使用泛型约束语法的地方。
下方是使用Calc语言的泛型双向链表举例，它在Calc的runtime中被大量用到。
package linkedlist
type Node<T> struct {
val T
next *Node<T>
prev *Node<T>
}
type List<T> struct {
first *Node<T>
tail *Node<T>
len int
}
func UnShift<T>(this li *List<T>, t T) void {
li.len = li.len + 1
n := &Node<T>{val:t}
if li.first == nil {
li.first = n
li.tail = n
return
}
n.next = li.first
li.first.prev = n
li.first = n
return
}
func Push<T>(this li *List<T>, t T) void {
li.len = li.len + 1
n := &Node<T>{val:t}
if li.first==nil {
li.first = n
li.tail = n
return
}
li.tail.next = n
n.prev = li.tail
li.tail = n
return
}
func Len<T>(this li *List<T>) int {
return li.len
}
func IndexOp<T>(this li *List<T>, index int) T {
i := 0
var n *Node<T>
for n = li.first;i!=index;n=n.next {
i=i+1
}
return n.val
}
func Shift<T>(this li *List<T>) T {
n := li.first
val := n.val
li.remove(n)
return val
}
func Pop<T>(this li *List<T>) T {
n := li.tail
li.remove(n)
return n.val
}
func remove<T>(this li *List<T>, n *Node<T>) void {
li.len = li.len - 1
if n.prev==nil&&n.next==nil {// 唯一一个元素被删除
li.first = nil
li.tail = nil
} else if n.prev==nil {// head被删除
li.first = n.next
n.next.prev = nil
} else if n.next==nil {// tail被删除
li.tail = n.prev
li.tail.next = nil
} else {
n.prev.next = n.next
n.next.prev = n.prev
}
return
}
func New<T>() *List<T> {
return &List<T>{}
}
一个成熟的语言必须具有系统调用相关的功能，而操作系统的ABI一般很难学习，缺少文档。所以正常来说，这部分调用系统ABI的工作会交给C库来进行。当然也有一些语言倾向于实现自己的系统调用库，但是这么做工作量过大，且不同操作系统往往接口不一样，而且不完全符合POSIX标准，这直接导致维护成本飙升。因此我采用调用C库的方法来进行系统调用。
由于底层使用llvm作为后端，而llvm有一个很有名的C ++ 编译器Clang，所以Calc和C的互操作是相对简单的。Calc不需要预先声明函数签名，所以声明语法被视作外部函数。如果要使用一个外部C库的函数，只需要在Calc中声明相应的函数签名，并且编译时对该库进行链接即可。
而C与语言调用Calc的库函数也是同理，只要写一个header file声明需要引入的函数再在编译时进行链接即可。
需要注意的是，在互操作时，两种语言之间只能相互传递基础数据类型。任何自定义的结构体传递都会导致未定义的行为，这是因为不同编译器之间对于字段的顺序和内存布局、内存对齐之间的处理可能有出入。尽管Calc在设计的时候尽量采用了与大部分C编译器相同的内存对齐模式 [8] ，对这种特性的依赖仍然是不建议的，因为这种行为可能破坏程序的跨平台性。举例而言，不同的操作系统里的同一个C库的实现细节往往会有区别，这体现在方方面面，有些时候同一个结构体的字段顺序就会有差别。而Clang和Calcc编译器对于结构体字段都是按照定义顺序来处理的，所以这种时候你按照Windows上C库结构体的字段顺序定义了一个Calc中的对应结构体，那么程序在windows上可以正确的运行，但是一旦到Linux上，由于Linux上C库定义的结构体字段顺序和Windows不一样，Calc在使用该结构体和C进行互操作的时候一些字段所对应的内存区域其实是错误的。这个时候如果对顺序错误的字段进行访问就会导致严重的Memory Access Violation错误，整个程序会直接崩溃。如果一定要依赖这种行为的话，请记住即使你很细心的将Windows和Linux上对应的代码都改对了，字段顺序仍然有可能会随着库的版本变化而变化。这个时候仍然会出现类似的未定义行为。
跨平台的统一IO接口是一个成熟语言所必须提供的功能。很遗憾的是，这部分功能不方便直接代理给C的标准库，因为C标准库只有统一的同步IO接口。而直接使用syscall来封装跨平台的异步接口是不现实的：不同的而操作系统对于异步机制的实现有很大的出入，Linux使用epoll [9] ，select等机制，而Windows是IOCP，Unix是Kqueue [10] ，这几种方案并不都符合POSIX标准，而且各自都有出入 [11] 。如果要全部适配它们工作量过大，所以我决定使用已有的成熟跨平台异步库。
一开始我是倾向于选择Asio作为异步库的，但是后来发现Asio基本是完全面向C ++ 的，不方便进行互操作。所以最后选择了libuv。libuv同时也是Node .js 的底层异步库，其代码大部分采用回调的形式，便于使用和改造。
但是回调模式会产生所谓的“回调地狱”问题，为了避免该问题，我需要为Calc语言实现一个协程模型，使用协程消除回调。这部分内容详见后文的协程部分。
使用Calc语言的异步IO接口可以轻松的实现一个TCP echo server：
package main
import (
"github.com/Chronostasys/calc/runtime/coro"
"github.com/Chronostasys/calc/runtime/libuv"
"github.com/Chronostasys/calc/runtime/strings"
)
func getchar() byte
func main() void {
libuv.TCPListen("0.0.0.0",8888,func (server libuv.UVTcp, status int32) void {
s := "new tcp conn"
s.PrintLn()
jobf := func () coro.Task<int> async {
for {
buf := await server.ReadBufAsync(1)
ss := strings.NewStr(buf.Data,buf.Len)
ss.Print()
re := await server.WriteBufAsync(ss)
if re !=0 {
sss := "write failed"
sss.PrintLn()
printIntln(re)
}
}
return 0
}
jobf()
return
})
s1 := "tcp echo server started at 0.0.0.0:8888"
s1.PrintLn()
getchar()
return
}
可以使用netcat进行连接和验证（ nc 127.0.0.1 8888 ）
接口功能对于解耦合与重构有着巨大的意义。一般而言接口分为两个种类：普通接口和Duck -type 接口 [12] 。计算机语言中的接口可以简单的理解为一种约定，一般来说一切符合约定的结构体/类都可以隐式的转换为对应的接口。而Duck - type与否的影响，则是接口是否需要结构体/类显式的继承。普通的接口，不止需要数据结构满足它约定的规则，还需要显示的被继承才能使用，而Duck - type接口则只需要满足接口条件即可。
从实现角度来讲，Duck - type接口实际上更简单一些，而普通接口更加符合面向对象的继承思想。所以大部分面向对象的语言采用普通接口（Java，C#，TypeScript等），而一些不存在面向对象元素的语言（golang）则可以采用Duck - type接口。由于Calc语言也是没有面向对象元素的语言，所以我采用了Duck -type 接口。
在Calc语言中，Duck - type接口底层是一个普通的结构体，它具备以下几个特点：
1. 所有的字段都是int类型
2. 字段个数等于接口规定的方法个数+ 1
3. 第一个int记录了一个指针地址，它指向实际的对应对象的地址
4. 剩下的int字段记录对应结构体的方法的指针
5. 这个类型不会被直接使用，且每次出现一定是它的指针类型，不过在源码中会隐藏这一点
6. 符合条件的结构体指针可以隐式转化为该接口
因此考虑接口的赋值操作，编译器需要加入以下的额外指令：首先，检查右值是否具有接口规定的方法，如果不是记录该错误，编译标记为失败。否则，开始赋值操作；赋值操作中使用ptrtoint命令将将右值的地址和对应的满足条件的各个方法的地址分别转化为int，写入左值接口对应结构体的各个字段中。
闭包是由函数和其周围上下文执行环境的引用一起组成的。它对于一些函数式编程语言尤为重要，在这些语言中函数往往是所谓的“first -class” ，也就是能作为普通的变量值来进行传递。而仅仅能传递普通函数对于这些语言来说是不够的，因为很多时候我们希望可以临时生成一个函数，并且让他可以修改它外边的变量，这种时候就需要加上函数外界环境的引用了。
闭包的实现方案可以分为两大类，一类是构造一个特殊的结构体，此结构体含有两个指针，一个指向实际的函数，一个指向该函数闭包引用的环境；另一类是使用跳板函数，在执行的时候动态从栈/堆中分配一块地址，构造一个小跳板函数，在此函数中将寄存器设置为特定值以使得该函数执行的时候可以引用闭包外的变量 [13] 。而保存闭包引用的环境也由两种主流方案：一种是保存当前的执行栈状态，在执行必报的时候进行还原，另一种是编译器在编译时进行分析，将所有被引用的外界变量保存在一个特殊的上下文结构体中，在执行闭包时传入。
在上述的两类方案中，一般语言的匿名函数使用第一类方案实现，因为第一类相对来讲比较简单，不需要运行时生成函数。运行时生成调整寄存器的函数是具有平台依赖性的，如果要让他成功需要每个平台都实现一遍。但是第一类方法也有其缺陷，使用它的语言，例如C ++ 中的function，C # 中的Func和Action类，实际上都不是原生的函数指针，这样虽然看起来闭包和函数很像，但是实际上闭包还是个语法糖，它本质上和原生的函数不同，原生函数转化为闭包这些类时需要进行装箱，具有性能损耗。因此Calc采用了跳板函数的实现方法。
传递环境的方案，Calc选择了由编译器分析被捕获的变量然后生成对应的特殊闭包变量。尽管保存执行栈状态可能具有更好的性能，但是其本质是用空间换时间。而且使用这种方法需要编译器能对执行栈由非常高的掌握，例如golang，Calc不具有该特点。
根据上文的论述，很明显闭包对于生命周期是有很大的影响的：一个作用域在没有闭包的时候，其必然会在函数返回时结束，此时其中的所有局部变量也会和函数栈一起被回收；而如果某个作用域产生了一个闭包，那么该闭包引用的局部变量生命周期会被扩展至和闭包一致。
既然被闭包引用的变量的生命周期发生了改变，那么很明显该变量符合2 .3 逃逸分析中关于逃逸点的定义。所以逃逸分析时同时需要找出所有被闭包引用的外界变量并标记为逃逸点。
垃圾回收算法是Calc语言内存管理的核心模块之一。其采用经典的Mark and sweep方案（BDWGC），结合分代算法、差量并发回收算法。
Calc使用的GC算法的基本原理是：先对所有的栈空间进行扫描，找出所用指向堆空间的指针（这一步可能发生误判，比如有个位置正好等于堆空间的某个地址，但是它实际上并不是一个指针。不过误判并不会影响GC算法的正确性，而且出现概率极低），然后从这些指针触发进行树的遍历，没遍历一个对象都把它标记为已扫描，如果遇到已扫描的就返回防止死循环。这个工作完成之后，GC会遍历所欲呕已经分配的内存空间，看哪些空间没被标记，没被标记的空间代表它们已经不被使用，GC会立马释放它们。对比引用计数算法，引用计数会记录每个指针被引用的次数，如果它被引用的次数变成0则自动释放它。容易发现，引用计数很明显会有更好的性能但是却不能处理循环引用的问题：如果出现对象相互引用形成闭环的情况，引用计数将因为环里的对象计数永远不归0而永不回收，导致memory - leak，而标记法GC却能判断出这个环不可达而成功回收。
实际上引用计数有改进方法可以一定程度上改进循环引用的问题，那就是引入弱指针和主从概念。普通的指针都是强指针，强指针的起点为主人，重点为仆从。而如果出现了双向的引用，那么反向的指针为弱指针，弱指针不表示主从。而引用计数的时候只考虑主从关系，也就是只考虑强指针，这样子就解决了循环引用的问题。
但是上述的解决方案有明显的缺陷：引入了弱指针和强指针的概念，使得编程变得复杂，而且更加容易出错了 — 无论是乱用弱指针还是全用强指针都会导致内存安全问题，总体而言其实增加了程序员的心智负担。
还有一种方法，就是如同python一样，一部分使用引用计数，另一部分使用GC：在python中普通的变量哦都是使用引用计数来进行管理的，而任何容器对象则使用GC来进行管理。因为只有容器对象有相互引用的可能性。但是这种做法也为整个系统带来了额外的复杂度，且目前并没有有力证据证明这种机制的优越性。实际上我认为，通过逃逸分析将能分配到堆上的变量都分配到堆上可能会带来相比python的做法更大的性能提升。
尽管一些语言的设计师认为，相比总消耗的时间，低延迟更适用于现代语言的需求 [14] ，然而分代GC相比普通的非分代三色标记GC无疑在总CPU时间上具有优势。
由于底层使用LLVM，Calc编译器对于函数栈的控制并非尽善尽美，而LLVM本身对于GC接口的支持也尚不完善，所以采用的GC算法为通用的全栈扫描GC算法 [15] ，而非通过记录GCROOT之后进行定向扫描的方法。该方案性能可能稍低，不过具有较好的健壮性和可移植性。
尽管GC进行过并发优化，但由于GC的mark阶段目前不可能完全并发，所以还是存在一些STW时间，一般在数毫秒以内 [16] 。
另外，由于GC需要能获取所有它控制的线程的信息，所以如果在Calc中使用涉及多线程的第三方库，请注意第三方库的内存管理可能无法与Calc的GC进行互动。举例而言，如果将第三方库中的某个变量的字段设为Calc分配的堆中对象，GC可能因为无法找到第三方库中线程的信息而将该对象过早回收。
Calc内置无栈协程支持，很多功能与异步IO操作都依赖于该功能。
随着近年来cpu的发展，近几年出现的高级语言已经将协程作为重要买点 [17] 。其中主要分为两派：以操作系统线程为蓝本的真正精简版线程方案 - 有栈协程；原理不同于于线程的新时代并发概念-无栈协程。
有栈协程与线程在使用上基本没有区别，一般而言只是具有减少了分配的栈空间并且切换协程时不需要进入内核态这两个优势。使用这种协程方案需要编译器能够完整的控制栈空间，能够随时对运行栈的状态进行保存和恢复 [18] 。这种协程的调度与管理十分接近于操作系统的线程，具有易于理解、易于使用的特点，其缺点为难以扩展，普通用户不方便指定自己的调度规则，且调度算法比较复杂。
而无栈协程则出现的比较晚。它的思想在1 999 年第一次被提出，并被基于当时的Haskell实现 [19] 。 8 年后它的改进版第一次出现在F#的正式版本更新中 [20] ，此时它的模式仍然和现在的async / await模式有区别。直到2 011 年，今天常见的async / await模式才首次在C#中出现，它由天才程序员海尔斯伯格带领团队创造 [21] 。
无栈协程基于Generator思想，将协程理解为可以自行暂停的函数。每个协程函数中可以有复数个暂停点，而这些暂停点由用户自行定义。相比有栈协程，它的调度算法更加简单，不需要抢占式调度，且总体来说具有更高的性能。但是它相比有栈协程更加难以理解，且具有所谓的“传染性” [22] 。并且它的一些功能可能造成死锁，或者memory -leak 。
由于Calc并没自行管理执行栈，实现有栈协程较为困难，所以Calc的协程功能是无栈协程。
无栈协程的实现是基于状态机的，所以在讨论无栈协程之前必须先说明状态机的实现方法。
状态机，有时候也叫generator（生成器），其实指的都是一个东西。它往往用于一些语言实现foreach功能。它的特性是：当一个函数返回状态机的时候，它内部可以使用yield关键字来暂停函数的执行，并返回一个值。调用该函数的时候，其函数中的所有内容都不会被执行，而是会生成一个状态机。状态机会拥有一个“下一步”方法，每次调用下一步的时候都会执行到下一个yield并且获取返回值。
编译时，原函数签名会被编译为一个初始化状态机结构体的函数，实际源码里的函数内容会被编译到状态机的StepNext函数中。在yield的时候，编译器会在yield之后创建一个新的block，并把新block地址存在状态机的字段中。每次调用StepNext的时候，都会对状态机中存的block地址进行检查，如果不是空就直接跳转到该block继续执行。由于能够被暂停，所以函数的所有局部变量都存在状态机的字段中。
异步函数和状态机函数类似，它产生的实际上也是一个状态机，这个状态机会多一些特殊的字段，其中比较重要的是会有一个指针字段叫做ContinuousTask，有个字段存一个互斥锁，还有一个布尔字段记录异步状态机的执行状态。异步函数的yield改名为await，并且这个特殊的yield不再返回内容。另外，在await的时候还需要加入一些额外步骤：
1. 状态机互斥锁加锁
2. 检查状态机是否执行完成
3. 如果执行完成，则跳转4，否则将被await的异步函数生成的异步状态机的ContinuousTask字段设置为当前异步函数产生的状态机指针值，跳转5
4. 状态机互斥锁解锁，直接跳转下一个block继续执行
5. 状态机互斥锁解锁，当前Step Next 函数返回
以上内容需要结合异步调度器一起理解。所有的异步函数调用，无论是否被await，都会在编译时自动添加对QueueTask函数的调用，进入异步调度器的调度队列等待执行。
调度器包含一个线程池，每个线程都会从调度队列中不断请求新的任务来执行，执行的逻辑如下：
1. 从队列获取新的任务
2. 执行任务
3. 任务状态机互斥锁加锁
4. 将任务状态设置为已完成
5. 检查任务的ContinuousTask是否设置，如果被设置了则将ContinuousTask入任务队列
6. 任务状态机互斥锁解锁
7. 返回1
实际的实现中有很多优化，例如调度器的线程并非忙等，如果队列为空它们会等待signal唤醒，这些细节这里不表。
Calc线程池会在程序启动时自动创建，其数量一般与CPU的线程数相等。线程池可以用于并发的执行用户代码，并且避免过多的上下文切换 [23] 。
设计中，Calc的异步状态机c oro.Task<T> 是一个泛型接口，所以状态机并不是一定要编译器来生成，完全可以用Calc源码手动实现。所以libuv回调模式的api可以很容易用Calc进行封装，这也体现了Duck -type 接口配合泛型的优越性。
A sync /await模式面临的一个巨大问题就是死锁，这常常发生在同步等待异步方法的代码中 [24] 。了避免此问题，在Calc中同步等待异步函数的结果被视为非法行为，从根源上杜绝了此类事故。
Calc 的主要目标操作系统是Windows和Linux，在这两个平台上我设计了专门的安装脚本。而Unix平台虽然理论上也是可以使用的，但是使用者将需要自行从源码构筑编译器。
Calc发行的编译器实际上分为两个部分，一个部分是前端编译器，另一部分是Clang（llvm）。它的编译命令是calcc，在Windows上它对应的是一个powershell脚本 [25] ，而在Linux上对应的是一个bash脚本 [26] 。在两个平台上编译器的表现基本一致，并且都支持指定输入或者输出文件。
Calc在安装的时候会设定一个对应的语言根目录，同时它会设置一个名为CALC_BIN的环境变量，该环境变量对应的值就是这个目录，在Windows上它下边会安装编译所需要的calc前端编译器，bdwgc与libuv的链接文件，动态链接库，和真正的编译命令calcc的执行脚本calcc. ps1 ；在Linux上这里不会有bdwgc和libuv的链接文件与动态链接库，这些东西会被安装脚本安装到用户的lib目录去。同理别的可执行文件和calcc .sh 脚本会被安装到用户的bin目录去。而在引入第三方库依赖时，所有的第三方repo都会被克隆到CALC_REPO目录下。目前这个目录没有加任何保护措施，以后应该会把它改为只读权限。
目前calcc无法进行单文件编译，它只能指定编译的目录然后将被指定的目录作为模块来编译。并且交叉编译暂时也是不支持的，不过理论上calcc很容易就可以做到交叉编译。
Calc的跨平台特性来源于其底层llvm后端的支持，并且在设计的时候使用的所有外部依赖C库也都是跨平台的。Calc的标准库在开发的时候严格遵守了 2 .7.1中的C语言互操作规范以确保代码在不同的平台下运行具有完全一样的效果。
经过测试，Calc编写的TCP echo server无论是在Linux上还是在Windows上都可以很好的工作，且都可以使用netcat进行连接测试。
语言服务器是为现代编辑器提供各种语法支持的软件 [27] ，Calc作为一个现代化语言当然应该具有现代的编辑体验。所以Calc编辑器本身具有Language Server模块，能够为现代编辑器提供语法支持 [28] 。
普通的简单器是不满足Language Server的条件的。如果要制作Language Server，编译器至少要能容忍错误：如果一个编译器在遇到第一个编译错误的时候就直接报错退出，那么它给用户的错误信息就只有编译时的第一条，而实际上能犯了非常多个错误，编译器却只能提示一个。
为了让Calc编译器可以从错误中恢复，程序中设计了一个全局的错误计数器和诊断信息列表，每次出错都会将错误计数器加一、将 错 误内容添加进入诊断信息列表并且跳过当前错误内容。跳过错误内容的算法如下 [29] ：
1. 如果 错误内容 不 包含 任何 左 括号，则跳过当前行
2. 如果错误内容包含任何左括号，则错误内容一直延续到与它配对的反括号所在行
如上文所述，诊断信息是编译期间生成的错误信息。在这里还需要补充一些细节：诊断信息不止是单纯的错误message，它还包括了错误信息所在的文件、错误的行号、错误的字符范围。这些信息在出版编译器中并不会被记录，在制作language Server的时候我加入了这些相关内容，不仅为了这些诊断信息，也为以后的debug做准备。
Calc的Language Server的自动补全功能比较特殊，它并不是每次请求的时候计算的，而是在每次用户做出更改的时候提前计算好的。每次编译的时候，如果遇到了语法错误的位置，编译器会判断这个错误是否属于不完整代码的类型，如果有几率是的话，编译器将会通过出错内容尝试进行补全，补全后的推荐列表将会存在一个哈希表里。在Language Server接收到自动补全请求的时候可以通过使用位置信息查表来获取AutoComplete的内容。
符号跳转类似自动补全功能的设计，也是使用哈希表对位置进行反向索引，在编译分析的时候往表里记录信息，在接收到查询api的时候进行查表。
为了保证Language Server在处理大项目时的反应速度，Calc使用了一种差量重分析技术。Calc Language Server在实际运作时，只有第一次启动时需要对完整的项目进行分析，之后每次代码变化它只会对变化的部分进行重新分析。这保证了代码分析极快的速度和Language Server几乎无延迟的回复。
具体而言，首先编译器在分析模式时会对源码文件进行cache，同时也会对每个源码编译之后对应的抽象代码子树 [30] 进行cache。在某次重新分析的时候，Language Server会通知分析器变化了哪些文件，分析器就会重新分析对应的文件，并结合之前缓存的抽象代码子树重新生成完整的抽象代码树以生成最新的分析结果。
这种差量重分析法使得分析器的磁盘IO次数降低至不到原本的1 0 分之1，非常明显的增强了性能，减少了生成代码提示和诊断信息的延迟。
我创建了一种新的跨平台高级语言和编译器，成功的解决了无栈协程常见的死锁问题和内存泄漏问题，实现了逃逸分析算法帮助使用者科学的分配内存空间，实现了闭包、duck-type接口、泛型、协程、状态机、包管理、异步IO等前沿的高级语言特性，并且实现了高效的并发编译，能1 3 秒将1, 000,000 行源代码编译为llvm ir中间代码。同时完成了Language Server的功能设计和实现，使用差量重分析技术达成了几乎无延迟的代码提示和错误提示、符号跳转等功能。
但是，系统库仍然很不完善，异步IO只完成了TCP的封装，还缺少文件IO、http等功能。泛型虽然实现了却没有添加泛型约束，也没有来得及针对duck - type接口结合泛型之后泛型约束的必要性进行讨论，这是很大的一个遗憾。截至写论文时，Language Server其实还没有完全完工，目前的诊断信息只有错误级别的，缺少Warning和Info。另外Debug功能还完全没有做，语言debug目前只能靠llvm ir。
首先感谢代炜琦老师，没有您我无法选择这个题目，做出如此让我感到自豪的毕业设计。感谢李子怡同学，没有你的激励我可能在寒假就会放弃堆编译器的研究。感谢刘铭和骆婷老师，没有你们的编译原理课相比我无法做到像今天热爱编译器。感谢李升辉老师和陈凯老师对我中途更换课题的理解与支持，没有你们我可能现在还在做以前的课题。感谢肖益同学和谭俊同学对我的编译器研究的支持，没有和你们的讨论编译器一定无法达到今天这样的完成度。感谢维护l lir/llvm 项目的 Robin ，解决了我在该项目提出的issue，使得状态机能够顺利的实现。
[1] | N. D. Matsakis 和 F. S. Klock, “The rust language,” ACM SIGAda Ada Letters, 卷 34, 编号 3, 2014. |
[2] | T. W. Christopher, “Reference count garbage collection,” Software Practice and Experience, pp. 503-507, 6 1984. |
[3] | A. W. Appel, Modern Compiler Implementation in C, Google, 2004. |
[4] | D. G. &. B. Steensgaard, “Fast Escape Analysis and Stack Allocation for Object-Based Programs,” 出处 Compiler Construction , 2001. |
[5] | R. Garcia, “A comparative study of language support for generic programming,” 出处 OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications , 2003. |
[6] | J. Niño, “The Cost of Erasure in Java Generics Type System,” 2010. |
[7] | B. C. Pierce 和 D. N. Turner, “Local type inference,” 出处 ACM Transactions on Programming Languages and Systems , 2000. |
[8] | E. S. A. S. V. T. D. V. Kostya Serebryany, “Memory Tagging and how it improves C/C++ memory safety,” arxiv, 2018. |
[9] | K.-C. Zhan, Comparing and Evaluating I/O Event Notification Mechanisms Based on Embedded Linux, 2021. |
[10] | L. Leonard, Event-driven servers using asynchronous, non-blocking network I/O: Performance evaluation of kqueue and epoll, 2021. |
[11] | S. Dolan, S. Eliopoulos, D. Hillerström 和 A. Madhavapeddy, “Effectively Tackling the Awkward Squad,” ML Workshop, 2017. |
[12] | gurumoorthyP, arvindpdmn 和 arvindpdmn, “Duck Typing,” devopedia.org, 2022. |
[13] | T. G. Authors, “Trampolines,” 3 5 2022. [联机]. Available: https://gcc.gnu.org/onlinedocs/gccint/Trampolines.html. [访问日期: 3 5 2022]. |
[14] | A. Kashinath, “Providing timing guarantees in software using Golang,” 出处 UC San Diego Electronic Theses and Dissertations , 2017. |
[15] | H. a. M. W. Boehm, “Garbage Collection in an Uncooperative Environment,” Software Practice & Experience, pp. 807-820, 1988. |
[16] | H. A. D. a. S. S. Boehm, “Mostly Parallel Garbage Collection,” 出处 Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26 , 1991. |
[17] | J. Timm, “An OS-level adaptive thread pool scheme for I/O-heavy workloads,” 2021. |
[18] | A. P. a. F. Liu, “Theory and Practice of Coroutines with Snapshots,” 出处 32nd European Conference on Object-Oriented Programming , 2018. |
[19] | K. Claessen, “A poor man's concurrency monad,” Journal of Functional Programming, 卷 9, 编号 3, pp. 313-323, 1999. |
[20] | P. L. Zdancewic, “Combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives,” ACM SIGPLAN Notices, 卷 42, 编号 6, pp. 189-199, 2007. |
[21] | A. Hejlsberg, Interviewee, Anders Hejlsberg interview for Channel 9 about Asynchronous Programming. [采访]. 2011. |
[22] | S. Cleary, “Async/Await - Best Practices in Asynchronous Programming,” MSDN Magazine, 卷 28, 编号 3, 2013. |
[23] | A. M. R. F. F. R.-F. DL Freire, “Performance Evaluation of Thread Pool Configurations in the Run-time Systems of Integration Platforms,” 2021. |
[24] | C. Voss, “An ownership policy and deadlock detector for promises,” Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 348-361, February 2021. |
[25] | V. Sukhija, PowerShell Basics, Apress, 2021. |
[26] | R. Anderson, Basics of Bash, 2022. |
[27] | H. Bunder, “Decoupling Language and Editor - The Impact of the Language Server Protocol on Textual Domain-Specific Languages,” MODELSWARD,, 2019. |
[28] | H. B. &. H. Kuchen, Towards Multi-editor Support for Domain-Specific Languages Utilizing the Language Server Protocol, 2020. |
[29] | N. G. Marcus, Language Server Protocol and Implementation, Apress, 2022. |
[30] | Z. O. J. Z. J. C. H. L. a. R. W. C. Lin, “Improving Code Summarization with Block-wise Abstract Syntax Tree Splitting,” 2021 IEEE/ACM 29th International Conference on Program Comprehension (ICPC), pp. 184-195, 2021. |
附录
本文章由word文档转换而成