[译] 添加一个新语句到Golang编译器内部-第一部分
Leonard_Wang · · 1296 次点击 · · 开始浏览序
这是两部分系列中的第一篇文章,该系列采用基于教程的方法来探索Go编译器。编译器很大,可能需要一本书去正确描述,本文章的想法是提供一种"深度优先"的探索思路。作者计划在将来写更多关于编译器特定领域的描述性文章。 我们将更改Go编译器添加一个新的语言特性(仅用来探索编译器的实现),并构建一个修改后的编译器来使用。
原文链接
注:一些编译器专业术语仍然沿用了英文。
任务:添加一个新语句
许多语言都有一个while语句,在Go中使用for表示:
for <some-condition> {
<loop body>
}
在Go中添加while语句是简单的,因为只需要简单的将while翻译为for。所以我们选择了一个更具有挑战性的任务:添加until。until与while相似,只是将判定条件改为了否定,意为"直到......"。例如:
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
与下面代码的意思是相同的:
i := 4
for i != 0 {
i--
fmt.Println("Hello, until!")
}
我们还可以继续增大任务的难度,在until语句中加入初始化功能。
until i := 4; i == 0 {
i--
fmt.Println("Hello, until!")
}
本系列文章将会实现这个功能。
Ps:这只是一个实验性的练习,因为Go的极简主义是绝对正确的设计选择,所以我认为在Go中添加until并不是一个好的想法。
Go编译器的高级结构
Go默认的编译器(gc)有一个相当传统的结构,如果您之前使用过其他编译器,你可以很快熟悉它:
相对于Go存储库根目录,编译器的代码实现位于Go根目录下src/cmd/compile/internal;本文后续内容提到的代码路径都是相对于该目录的相对路径。它全部用Go编写,具有很好的可读性。 在这篇文章中,我们将逐一分析这些阶段,以便添加了支持until语句所需的代码。
查看src/cmd/compile中的README文件,以获得编译步骤的详细分步说明,该文件是这篇文章的好伴侣。
词法分析器
扫描器(也称为词法分析器)将源代码文本分解为编译器的离散实体。例如关键字for转换为常量_For;...字符转换为_DotDotDot;而.自身被转换为_Dot等等。
词法分析器在syntax包中实现,我们需要做的只是使它理解一个新的关键字-until。 文件syntax/tokens.go包含编译器理解的所有词法单元(tokens),我们将添加一个新的词法单元_Until:
_Fallthrough // fallthrough
_For // for
_Until // until
_Func // func
右侧的注释是很重要的,它用来标识文本中的token。运行在tokens列表的上方的go generate可以自动生成相关代码。
//go:generate stringer -type token -linecomment
添加token后必须手动运行go generate,来生成源码中的syntax/token_string.go。为了重新生成它,在syntax目录运行以下命令:
GOROOT=<src checkout> go generate tokens.go 你可能会遇到running "stringer": exec: "stringer": executable file not found in $PATH,需要执行如下命令后继续:
go get -u golang.org/x/tools/cmd/stringer
从Go 1.12开始,GOROOT设置是必不可少的,并且必须指向我们正在修改编译器代码的源码根路径。
运行go generate重新生成syntax/token_string.go后,我尝试重新编译编译器时遇到了panic: imperfect hash
panic来自syntax/scanner.go中的这段代码:
// hash is a perfect hash function for keywords.
// It assumes that s has at least length 2.
func hash(s []byte) uint {
return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
}
var keywordMap [1 << 6]token // size must be power of two
func init() {
// populate keywordMap
for tok := _Break; tok <= _Var; tok++ {
h := hash([]byte(tok.String()))
if keywordMap[h] != 0 {
panic("imperfect hash")
}
keywordMap[h] = tok
}
}
编译器试图构建"完美"哈希表去对应关键字和token的关系以便进行查找。"完美"意味着它希望没有碰撞,将每个关键字都映射到一个索引组成一个线性数组。哈希函数是ad-hoc(它只查看字符串标记的第一个字符的内容),并且调试冲突的原因很困难。为了暂时解决这个问题,我将查找表的大小更改为[1<<7]token,从而将查找数组的大小从64更改为128。这给了散列函数更多的空间来分发它的关键字,结果是冲突消失了。
为了解决这个问题,您需要修改syntax/scanner.go中的
var keywordMap [1 << 6]token 修改为:
var keywordMap [1 << 7]token
语法分析器
Go有一个相当标准的递归下降式的语法分析器(Parse),它将词法分析器生成的tokens换为具体的语法树。 我们首先在syntax/nodes.go中为until添加一个新的节点类型(可以添加在ForStmt struct后):
UntilStmt struct {
Init SimpleStmt
Cond Expr
Body *BlockStmt
stmt
}
我从ForStmt借用了整体结构,用于for循环。 与for类似,我们的until语句有几个可选的子语句:
until <init>; <cond> {
<body>
}
<init>和<cond>都是可选的,但省略<cond>并不常见。 UntilStmt.stmt嵌入字段用于所有语法树语句并包含位置信息。
语法分析器本身在syntax/parser.go中完成。parser.stmtOrNil方法解析当前位置的语句。 它查看当前token并决定要解析哪个语句。 以下是我们添加的代码的摘录(在switch p.tok中添加case _Until:):
switch p.tok {
case _Lbrace:
return p.blockStmt("")
// ...
case _For:
return p.forStmt()
case _Until:
return p.untilStmt()
下面是untilStmt:
func (p *parser) untilStmt() Stmt {
if trace {
defer p.trace("untilStmt")()
}
s := new(UntilStmt)
s.pos = p.pos()
s.Init, s.Cond, _ = p.header(_Until)
s.Body = p.blockStmt("until clause")
return s
}
我们重用现有的parser.header方法,该方法解析if和for语句的header。在一般的形式中,它支持三个部分(用分号分隔)。在for语句中,第三部分可以用于"post"语句,但我们不会支持这个,在until中我们只对前两个感兴趣。
请注意,header接受原始的token,以便能够区分它所服务的语句类型;例如,它会拒绝if的"post"语句(在if语句中只可以加入初始化和判断条件语句,没有第三个参数去修改条件变量)。在until中我们也应该明确地拒绝它,但这个现在还没有实现。
这些都是我们需要对解析器进行的所有更改。因为until在结构上与现有语句非常相似,所以我们可以重用大部分功能。
如果我们使用编译器转储语法树(syntax.Fdump)解析并运行下面的代码后:
i = 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
我们将得到until语句的这个片段:
84 . . . . . 3: *syntax.UntilStmt {
85 . . . . . . Init: nil
86 . . . . . . Cond: *syntax.Operation {
87 . . . . . . . Op: ==
88 . . . . . . . X: i @ ./useuntil.go:13:8
89 . . . . . . . Y: *syntax.BasicLit {
90 . . . . . . . . Value: "0"
91 . . . . . . . . Kind: 0
92 . . . . . . . }
93 . . . . . . }
94 . . . . . . Body: *syntax.BlockStmt {
95 . . . . . . . List: []syntax.Stmt (2 entries) {
96 . . . . . . . . 0: *syntax.AssignStmt {
97 . . . . . . . . . Op: -
98 . . . . . . . . . Lhs: i @ ./useuntil.go:14:3
99 . . . . . . . . . Rhs: *(Node @ 52)
100 . . . . . . . . }
101 . . . . . . . . 1: *syntax.ExprStmt {
102 . . . . . . . . . X: *syntax.CallExpr {
103 . . . . . . . . . . Fun: *syntax.SelectorExpr {
104 . . . . . . . . . . . X: fmt @ ./useuntil.go:15:3
105 . . . . . . . . . . . Sel: Println @ ./useuntil.go:15:7
106 . . . . . . . . . . }
107 . . . . . . . . . . ArgList: []syntax.Expr (1 entries) {
108 . . . . . . . . . . . 0: *syntax.BasicLit {
109 . . . . . . . . . . . . Value: "\"Hello, until!\""
110 . . . . . . . . . . . . Kind: 4
111 . . . . . . . . . . . }
112 . . . . . . . . . . }
113 . . . . . . . . . . HasDots: false
114 . . . . . . . . . }
115 . . . . . . . . }
116 . . . . . . . }
117 . . . . . . . Rbrace: syntax.Pos {}
118 . . . . . . }
119 . . . . . }
建立抽象语法树(AST)
现在已经具有了源代码的语法树表示,编译器构建了一个抽象语法树。我曾经写过关于抽象语法树和具体语法树的文章(Abstract vs. Concrete syntax trees)——如果您不熟悉它们之间的区别,那么有必要查看一下。然而,在Go中这种情况在将来可能会改变。Golang编译器最初是用C语言编写的,后来自动翻译成Golang,所以编译器的部分代码是C时代遗留下来的,另外一部分则是较新的。未来可能会重构只留下一种语法树,但是现在(Go 1.12),这是我们必须遵循的过程。
AST代码存在于gc包中,节点类型在gc/syntax.go中定义(不要与定义CST的语法包混淆!)
Go的AST的结构与CST不同。所有AST节点都使用syntax.Node类型,而不是每个节点类型具有其专用的结构类型,这是一种区分联合,它包含许多不同类型的字段。并且某些字段是通用的,可以用于大多数节点类型:
// A Node is a single node in the syntax tree.
// Actually the syntax tree is a syntax DAG, because there is only one
// node with Op=ONAME for a given instance of a variable x.
// The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared.
type Node struct {
// Tree structure.
// Generic recursive walks should follow these fields.
Left *Node
Right *Node
Ninit Nodes
Nbody Nodes
List Nodes
Rlist Nodes
// ...
我们首先在gc/syntax.go的const列表中添加一个新的常量来标识until节点
// statements
// ...
OFALL // fallthrough
OFOR // for Ninit; Left; Right { Nbody }
OUNTIL // until Ninit; Left { Nbody }
我们将再次运行go generate,这次是在gc/syntax.go上,为新节点类型生成一个字符串表示:
// from the gc directory
GOROOT=<src checkout> go generate syntax.go
这应该更新gc/op_string.go文件以包含OUNTIL。现在是时候为我们的新节点类型编写实际的CST->AST转换代码了。
转换在gc/noder.go中完成。 我们将在现有的for语句支持之后继续对我们的更改进行建模,从stmtFall开始,stmtFall具有语句类型的switch-case结构,即在gc/noder.go的stmtFall方法中添加case *syntax.UntilStmt:
case *syntax.ForStmt:
return p.forStmt(stmt)
case *syntax.UntilStmt:
return p.untilStmt(stmt)
然后仍然在gc/noder.go中对noder类型添加新的方法untilStmt:
// untilStmt converts the concrete syntax tree node UntilStmt into an AST
// node.
func (p *noder) untilStmt(stmt *syntax.UntilStmt) *Node {
p.openScope(stmt.Pos())
var n *Node
n = p.nod(stmt, OUNTIL, nil, nil)
if stmt.Init != nil {
n.Ninit.Set1(p.stmt(stmt.Init))
}
if stmt.Cond != nil {
n.Left = p.expr(stmt.Cond)
}
n.Nbody.Set(p.blockStmt(stmt.Body))
p.closeAnotherScope()
return n
}
回想一下上面解释的通用Node字段。这里,我们使用Init字段作为可选初始化器,Left字段作为条件,Nbody字段作为循环体。
这就是我们为until语句构造AST节点所需的全部内容。如果在完成后对AST进行dump操作,我们将会得到:
. . UNTIL l(13)
. . . EQ l(13)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-0 l(13) untyped number
. . UNTIL-body
. . . ASOP-SUB l(14) implicit(true)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-1 l(14) untyped number
. . . CALL l(15)
. . . . NONAME-fmt.Println a(true) x(0) fmt.Println
. . . CALL-list
. . . . LITERAL-"Hello, until!" l(15) untyped string
类型检查
编译的下一步是类型检查,它在AST上完成。 除了检测类型错误之外,Go中的类型检查还包括类型推断,它允许我们编写如下语句:
res, err := func(args)
不需要明确声明res和err的类型。Go类型检查器还会执行一些任务,比如将标识符链接到它们的声明中,以及计算编译时的常数。类型检查的相关代码在gc/typecheck.go中,同样,在for语句的引导下,我们将把这个子句添加到typecheck中的switch-case中(gc/typecheck.go中typecheck1的switch n.Op中):
case OUNTIL:
ok |= ctxStmt
typecheckslice(n.Ninit.Slice(), ctxStmt)
decldepth++
n.Left = typecheck(n.Left, ctxExpr)
n.Left = defaultlit(n.Left, nil)
if n.Left != nil {
t := n.Left.Type
if t != nil && !t.IsBoolean() {
yyerror("non-bool %L used as for condition", n.Left)
}
}
typecheckslice(n.Nbody.Slice(), ctxStmt)
decldepth--
它为语句的各个部分分配类型,并检查条件在布尔上下文中是否有效。
分析和重写抽象语法树
在类型检查之后,编译器会经历AST分析和重写的几个阶段。 确切的顺序在gc/ main.go中的gc.Main函数中列出。 在编译器命名法中,这些阶段通常称为passes。
大部分的pass不需要修改去支持until,因为它们通常用于所有语句类型(这里gc.Node的通用结构很有用)。然而,还是有些需要修改,例如escape analysis(逃逸分析),它试图找到哪些变量"逃出"了它们的函数范围,因此必须在堆上而不是堆栈上分配。
Escape分析适用于每种语句类型,因此我们必须在Escape.stmt中添加switch-case结构(译者没有找到在哪里添加下面的代码,可能版本不同,可能逃逸分析是另外的工程实现的,不过这个代码不影响我们正常编译和后续的功能验证):
case OUNTIL:
e.loopDepth++
e.discard(n.Left)
e.stmts(n.Nbody)
e.loopDepth--
最后,gc.Main调用可移植代码生成器(gc/pgen.go)来编译分析的代码。 代码生成器首先应用一系列AST转换,将AST降低为更容易编译的形式。 这是在compile函数中完成的,它从调用order开始。
这种转换(在gc/order.go中)对语句和表达式重新排序,以强制执行求值顺序。例如,它将把foo /= 10重写为foo = foo/10,用多个单赋值语句替换多赋值语句,等等。 为支持until语句,我们将其添加到gc/order.go中Order.stmt的switch-case结构中:
case OUNTIL:
t := o.markTemp()
n.Left = o.exprInPlace(n.Left)
n.Nbody.Prepend(o.cleanTempNoPop(t)...)
orderBlock(&n.Nbody, o.free)
o.out = append(o.out, n)
o.cleanTemp(t)
在order之后,compile函数调用gc/walk.go中的walk。walk收集了一系列AST转换,这些转换有助于稍后将AST降低到SSA。例如,它将for循环中的range子句重写为具有显式循环变量的简单形式的for循环[1]。 它还重写了对运行时调用的map的访问等等。
要在walk中支持新语句,我们必须在walkstmt函数中添加switch-case子句。顺便说一下,这也是我们可以通过将它重写为编译器已经知道如何处理的AST节点来"实现"我们的until语句的地方。在until的case中是很简单的,如文章开头所示,我们只是将它重写为一个for循环,并使用倒装条件。下面是转换的代码实现:
case OUNTIL:
if n.Left != nil {
walkstmtlist(n.Left.Ninit.Slice())
init := n.Left.Ninit
n.Left.Ninit.Set(nil)
n.Left = nod(ONOT, walkexpr(n.Left, &init), nil)
n.Left = addinit(n.Left, init.Slice())
n.Op = OFOR
}
walkstmtlist(n.Nbody.Slice())
请注意,我们用一个包含n.Left的ONOT类型(表示一元!运算符)的新节点替换n.Left(条件),并用OFOR替换n.Op。
如果我们在walk之后再次对AST进行dump操作,我们将看到OUNTIL节点消失并且新的OFOR节点取而代之。
看下效果
现在,我们可以试用修改后的编译器并运行一个使用until语句的示例程序:
$ cat useuntil.go
package main
import "fmt"
func main() {
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
}
$ <src checkout>/bin/go run useuntil.go
Hello, until!
Hello, until!
Hello, until!
Hello, until!
大功告成~
你也可以将 i := 4 until i == 0合并为一条语句until i:=4;i == 0
提醒:<src checkout>是我们检出Go的目录,更改并编译它(有关详细信息,请参阅附录)。
结束
这是第一部分。我们已经在Go编译器中成功实现了一个新语句。我们没有覆盖编译器的所有部分,因为我们采取了一个捷径,通过使用for节点去替换until节点的AST。这是一个非常有效的编译策略,Go编译器已经有许多类似的转换来规范化AST(将许多形式减少为更少的形式,因此编译的最后阶段做的工作较少)。但我们仍然有兴趣探索最后两个编译阶段 - 转换为SSA和生成机器代码。这将在第2部分中介绍。
附录-编译Go工具链
请先阅读《Go贡献指南》。 以下是有关复制修改后的Go编译器的一些快速说明,如本文所示。 有两种方式可以尝试本文的修改:
- 克隆Go官方仓库,手动应用本文中描述的修改。
- 克隆作者fork的Go官方仓库,并且检出
adduntil分支,所有这些更改已经与一些调试助手一起应用。 克隆目录是整个帖子中<src checkout>的位置。
要编译工具链,请进入src/目录并运行./make.bash。 我们也可以运行./all.bash来构建它之后运行许多测试。 运行make.bash会调用构建Go的完整3步引导过程,但在我的(老化)机器上只需要大约50秒。
构建完成后,工具链将安装在与src同级的bin中。 然后我们可以通过运行bin /go install cmd/compile来更快地重建编译器本身。
[1]Go has some special "magic" range clauses like a range over a string which splits its up into runes. This is where such transformations are implemented.
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
序
这是两部分系列中的第一篇文章,该系列采用基于教程的方法来探索Go编译器。编译器很大,可能需要一本书去正确描述,本文章的想法是提供一种"深度优先"的探索思路。作者计划在将来写更多关于编译器特定领域的描述性文章。 我们将更改Go编译器添加一个新的语言特性(仅用来探索编译器的实现),并构建一个修改后的编译器来使用。
原文链接
注:一些编译器专业术语仍然沿用了英文。
任务:添加一个新语句
许多语言都有一个while语句,在Go中使用for表示:
for <some-condition> {
<loop body>
}
在Go中添加while语句是简单的,因为只需要简单的将while翻译为for。所以我们选择了一个更具有挑战性的任务:添加until。until与while相似,只是将判定条件改为了否定,意为"直到......"。例如:
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
与下面代码的意思是相同的:
i := 4
for i != 0 {
i--
fmt.Println("Hello, until!")
}
我们还可以继续增大任务的难度,在until语句中加入初始化功能。
until i := 4; i == 0 {
i--
fmt.Println("Hello, until!")
}
本系列文章将会实现这个功能。
Ps:这只是一个实验性的练习,因为Go的极简主义是绝对正确的设计选择,所以我认为在Go中添加until并不是一个好的想法。
Go编译器的高级结构
Go默认的编译器(gc)有一个相当传统的结构,如果您之前使用过其他编译器,你可以很快熟悉它:
相对于Go存储库根目录,编译器的代码实现位于Go根目录下src/cmd/compile/internal;本文后续内容提到的代码路径都是相对于该目录的相对路径。它全部用Go编写,具有很好的可读性。 在这篇文章中,我们将逐一分析这些阶段,以便添加了支持until语句所需的代码。
查看src/cmd/compile中的README文件,以获得编译步骤的详细分步说明,该文件是这篇文章的好伴侣。
词法分析器
扫描器(也称为词法分析器)将源代码文本分解为编译器的离散实体。例如关键字for转换为常量_For;...字符转换为_DotDotDot;而.自身被转换为_Dot等等。
词法分析器在syntax包中实现,我们需要做的只是使它理解一个新的关键字-until。 文件syntax/tokens.go包含编译器理解的所有词法单元(tokens),我们将添加一个新的词法单元_Until:
_Fallthrough // fallthrough
_For // for
_Until // until
_Func // func
右侧的注释是很重要的,它用来标识文本中的token。运行在tokens列表的上方的go generate可以自动生成相关代码。
//go:generate stringer -type token -linecomment
添加token后必须手动运行go generate,来生成源码中的syntax/token_string.go。为了重新生成它,在syntax目录运行以下命令:
GOROOT=<src checkout> go generate tokens.go 你可能会遇到running "stringer": exec: "stringer": executable file not found in $PATH,需要执行如下命令后继续:
go get -u golang.org/x/tools/cmd/stringer
从Go 1.12开始,GOROOT设置是必不可少的,并且必须指向我们正在修改编译器代码的源码根路径。
运行go generate重新生成syntax/token_string.go后,我尝试重新编译编译器时遇到了panic: imperfect hash
panic来自syntax/scanner.go中的这段代码:
// hash is a perfect hash function for keywords.
// It assumes that s has at least length 2.
func hash(s []byte) uint {
return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
}
var keywordMap [1 << 6]token // size must be power of two
func init() {
// populate keywordMap
for tok := _Break; tok <= _Var; tok++ {
h := hash([]byte(tok.String()))
if keywordMap[h] != 0 {
panic("imperfect hash")
}
keywordMap[h] = tok
}
}
编译器试图构建"完美"哈希表去对应关键字和token的关系以便进行查找。"完美"意味着它希望没有碰撞,将每个关键字都映射到一个索引组成一个线性数组。哈希函数是ad-hoc(它只查看字符串标记的第一个字符的内容),并且调试冲突的原因很困难。为了暂时解决这个问题,我将查找表的大小更改为[1<<7]token,从而将查找数组的大小从64更改为128。这给了散列函数更多的空间来分发它的关键字,结果是冲突消失了。
为了解决这个问题,您需要修改syntax/scanner.go中的
var keywordMap [1 << 6]token 修改为:
var keywordMap [1 << 7]token
语法分析器
Go有一个相当标准的递归下降式的语法分析器(Parse),它将词法分析器生成的tokens换为具体的语法树。 我们首先在syntax/nodes.go中为until添加一个新的节点类型(可以添加在ForStmt struct后):
UntilStmt struct {
Init SimpleStmt
Cond Expr
Body *BlockStmt
stmt
}
我从ForStmt借用了整体结构,用于for循环。 与for类似,我们的until语句有几个可选的子语句:
until <init>; <cond> {
<body>
}
<init>和<cond>都是可选的,但省略<cond>并不常见。 UntilStmt.stmt嵌入字段用于所有语法树语句并包含位置信息。
语法分析器本身在syntax/parser.go中完成。parser.stmtOrNil方法解析当前位置的语句。 它查看当前token并决定要解析哪个语句。 以下是我们添加的代码的摘录(在switch p.tok中添加case _Until:):
switch p.tok {
case _Lbrace:
return p.blockStmt("")
// ...
case _For:
return p.forStmt()
case _Until:
return p.untilStmt()
下面是untilStmt:
func (p *parser) untilStmt() Stmt {
if trace {
defer p.trace("untilStmt")()
}
s := new(UntilStmt)
s.pos = p.pos()
s.Init, s.Cond, _ = p.header(_Until)
s.Body = p.blockStmt("until clause")
return s
}
我们重用现有的parser.header方法,该方法解析if和for语句的header。在一般的形式中,它支持三个部分(用分号分隔)。在for语句中,第三部分可以用于"post"语句,但我们不会支持这个,在until中我们只对前两个感兴趣。
请注意,header接受原始的token,以便能够区分它所服务的语句类型;例如,它会拒绝if的"post"语句(在if语句中只可以加入初始化和判断条件语句,没有第三个参数去修改条件变量)。在until中我们也应该明确地拒绝它,但这个现在还没有实现。
这些都是我们需要对解析器进行的所有更改。因为until在结构上与现有语句非常相似,所以我们可以重用大部分功能。
如果我们使用编译器转储语法树(syntax.Fdump)解析并运行下面的代码后:
i = 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
我们将得到until语句的这个片段:
84 . . . . . 3: *syntax.UntilStmt {
85 . . . . . . Init: nil
86 . . . . . . Cond: *syntax.Operation {
87 . . . . . . . Op: ==
88 . . . . . . . X: i @ ./useuntil.go:13:8
89 . . . . . . . Y: *syntax.BasicLit {
90 . . . . . . . . Value: "0"
91 . . . . . . . . Kind: 0
92 . . . . . . . }
93 . . . . . . }
94 . . . . . . Body: *syntax.BlockStmt {
95 . . . . . . . List: []syntax.Stmt (2 entries) {
96 . . . . . . . . 0: *syntax.AssignStmt {
97 . . . . . . . . . Op: -
98 . . . . . . . . . Lhs: i @ ./useuntil.go:14:3
99 . . . . . . . . . Rhs: *(Node @ 52)
100 . . . . . . . . }
101 . . . . . . . . 1: *syntax.ExprStmt {
102 . . . . . . . . . X: *syntax.CallExpr {
103 . . . . . . . . . . Fun: *syntax.SelectorExpr {
104 . . . . . . . . . . . X: fmt @ ./useuntil.go:15:3
105 . . . . . . . . . . . Sel: Println @ ./useuntil.go:15:7
106 . . . . . . . . . . }
107 . . . . . . . . . . ArgList: []syntax.Expr (1 entries) {
108 . . . . . . . . . . . 0: *syntax.BasicLit {
109 . . . . . . . . . . . . Value: "\"Hello, until!\""
110 . . . . . . . . . . . . Kind: 4
111 . . . . . . . . . . . }
112 . . . . . . . . . . }
113 . . . . . . . . . . HasDots: false
114 . . . . . . . . . }
115 . . . . . . . . }
116 . . . . . . . }
117 . . . . . . . Rbrace: syntax.Pos {}
118 . . . . . . }
119 . . . . . }
建立抽象语法树(AST)
现在已经具有了源代码的语法树表示,编译器构建了一个抽象语法树。我曾经写过关于抽象语法树和具体语法树的文章(Abstract vs. Concrete syntax trees)——如果您不熟悉它们之间的区别,那么有必要查看一下。然而,在Go中这种情况在将来可能会改变。Golang编译器最初是用C语言编写的,后来自动翻译成Golang,所以编译器的部分代码是C时代遗留下来的,另外一部分则是较新的。未来可能会重构只留下一种语法树,但是现在(Go 1.12),这是我们必须遵循的过程。
AST代码存在于gc包中,节点类型在gc/syntax.go中定义(不要与定义CST的语法包混淆!)
Go的AST的结构与CST不同。所有AST节点都使用syntax.Node类型,而不是每个节点类型具有其专用的结构类型,这是一种区分联合,它包含许多不同类型的字段。并且某些字段是通用的,可以用于大多数节点类型:
// A Node is a single node in the syntax tree.
// Actually the syntax tree is a syntax DAG, because there is only one
// node with Op=ONAME for a given instance of a variable x.
// The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared.
type Node struct {
// Tree structure.
// Generic recursive walks should follow these fields.
Left *Node
Right *Node
Ninit Nodes
Nbody Nodes
List Nodes
Rlist Nodes
// ...
我们首先在gc/syntax.go的const列表中添加一个新的常量来标识until节点
// statements
// ...
OFALL // fallthrough
OFOR // for Ninit; Left; Right { Nbody }
OUNTIL // until Ninit; Left { Nbody }
我们将再次运行go generate,这次是在gc/syntax.go上,为新节点类型生成一个字符串表示:
// from the gc directory
GOROOT=<src checkout> go generate syntax.go
这应该更新gc/op_string.go文件以包含OUNTIL。现在是时候为我们的新节点类型编写实际的CST->AST转换代码了。
转换在gc/noder.go中完成。 我们将在现有的for语句支持之后继续对我们的更改进行建模,从stmtFall开始,stmtFall具有语句类型的switch-case结构,即在gc/noder.go的stmtFall方法中添加case *syntax.UntilStmt:
case *syntax.ForStmt:
return p.forStmt(stmt)
case *syntax.UntilStmt:
return p.untilStmt(stmt)
然后仍然在gc/noder.go中对noder类型添加新的方法untilStmt:
// untilStmt converts the concrete syntax tree node UntilStmt into an AST
// node.
func (p *noder) untilStmt(stmt *syntax.UntilStmt) *Node {
p.openScope(stmt.Pos())
var n *Node
n = p.nod(stmt, OUNTIL, nil, nil)
if stmt.Init != nil {
n.Ninit.Set1(p.stmt(stmt.Init))
}
if stmt.Cond != nil {
n.Left = p.expr(stmt.Cond)
}
n.Nbody.Set(p.blockStmt(stmt.Body))
p.closeAnotherScope()
return n
}
回想一下上面解释的通用Node字段。这里,我们使用Init字段作为可选初始化器,Left字段作为条件,Nbody字段作为循环体。
这就是我们为until语句构造AST节点所需的全部内容。如果在完成后对AST进行dump操作,我们将会得到:
. . UNTIL l(13)
. . . EQ l(13)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-0 l(13) untyped number
. . UNTIL-body
. . . ASOP-SUB l(14) implicit(true)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-1 l(14) untyped number
. . . CALL l(15)
. . . . NONAME-fmt.Println a(true) x(0) fmt.Println
. . . CALL-list
. . . . LITERAL-"Hello, until!" l(15) untyped string
类型检查
编译的下一步是类型检查,它在AST上完成。 除了检测类型错误之外,Go中的类型检查还包括类型推断,它允许我们编写如下语句:
res, err := func(args)
不需要明确声明res和err的类型。Go类型检查器还会执行一些任务,比如将标识符链接到它们的声明中,以及计算编译时的常数。类型检查的相关代码在gc/typecheck.go中,同样,在for语句的引导下,我们将把这个子句添加到typecheck中的switch-case中(gc/typecheck.go中typecheck1的switch n.Op中):
case OUNTIL:
ok |= ctxStmt
typecheckslice(n.Ninit.Slice(), ctxStmt)
decldepth++
n.Left = typecheck(n.Left, ctxExpr)
n.Left = defaultlit(n.Left, nil)
if n.Left != nil {
t := n.Left.Type
if t != nil && !t.IsBoolean() {
yyerror("non-bool %L used as for condition", n.Left)
}
}
typecheckslice(n.Nbody.Slice(), ctxStmt)
decldepth--
它为语句的各个部分分配类型,并检查条件在布尔上下文中是否有效。
分析和重写抽象语法树
在类型检查之后,编译器会经历AST分析和重写的几个阶段。 确切的顺序在gc/ main.go中的gc.Main函数中列出。 在编译器命名法中,这些阶段通常称为passes。
大部分的pass不需要修改去支持until,因为它们通常用于所有语句类型(这里gc.Node的通用结构很有用)。然而,还是有些需要修改,例如escape analysis(逃逸分析),它试图找到哪些变量"逃出"了它们的函数范围,因此必须在堆上而不是堆栈上分配。
Escape分析适用于每种语句类型,因此我们必须在Escape.stmt中添加switch-case结构(译者没有找到在哪里添加下面的代码,可能版本不同,可能逃逸分析是另外的工程实现的,不过这个代码不影响我们正常编译和后续的功能验证):
case OUNTIL:
e.loopDepth++
e.discard(n.Left)
e.stmts(n.Nbody)
e.loopDepth--
最后,gc.Main调用可移植代码生成器(gc/pgen.go)来编译分析的代码。 代码生成器首先应用一系列AST转换,将AST降低为更容易编译的形式。 这是在compile函数中完成的,它从调用order开始。
这种转换(在gc/order.go中)对语句和表达式重新排序,以强制执行求值顺序。例如,它将把foo /= 10重写为foo = foo/10,用多个单赋值语句替换多赋值语句,等等。 为支持until语句,我们将其添加到gc/order.go中Order.stmt的switch-case结构中:
case OUNTIL:
t := o.markTemp()
n.Left = o.exprInPlace(n.Left)
n.Nbody.Prepend(o.cleanTempNoPop(t)...)
orderBlock(&n.Nbody, o.free)
o.out = append(o.out, n)
o.cleanTemp(t)
在order之后,compile函数调用gc/walk.go中的walk。walk收集了一系列AST转换,这些转换有助于稍后将AST降低到SSA。例如,它将for循环中的range子句重写为具有显式循环变量的简单形式的for循环[1]。 它还重写了对运行时调用的map的访问等等。
要在walk中支持新语句,我们必须在walkstmt函数中添加switch-case子句。顺便说一下,这也是我们可以通过将它重写为编译器已经知道如何处理的AST节点来"实现"我们的until语句的地方。在until的case中是很简单的,如文章开头所示,我们只是将它重写为一个for循环,并使用倒装条件。下面是转换的代码实现:
case OUNTIL:
if n.Left != nil {
walkstmtlist(n.Left.Ninit.Slice())
init := n.Left.Ninit
n.Left.Ninit.Set(nil)
n.Left = nod(ONOT, walkexpr(n.Left, &init), nil)
n.Left = addinit(n.Left, init.Slice())
n.Op = OFOR
}
walkstmtlist(n.Nbody.Slice())
请注意,我们用一个包含n.Left的ONOT类型(表示一元!运算符)的新节点替换n.Left(条件),并用OFOR替换n.Op。
如果我们在walk之后再次对AST进行dump操作,我们将看到OUNTIL节点消失并且新的OFOR节点取而代之。
看下效果
现在,我们可以试用修改后的编译器并运行一个使用until语句的示例程序:
$ cat useuntil.go
package main
import "fmt"
func main() {
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
}
$ <src checkout>/bin/go run useuntil.go
Hello, until!
Hello, until!
Hello, until!
Hello, until!
大功告成~
你也可以将 i := 4 until i == 0合并为一条语句until i:=4;i == 0
提醒:<src checkout>是我们检出Go的目录,更改并编译它(有关详细信息,请参阅附录)。
结束
这是第一部分。我们已经在Go编译器中成功实现了一个新语句。我们没有覆盖编译器的所有部分,因为我们采取了一个捷径,通过使用for节点去替换until节点的AST。这是一个非常有效的编译策略,Go编译器已经有许多类似的转换来规范化AST(将许多形式减少为更少的形式,因此编译的最后阶段做的工作较少)。但我们仍然有兴趣探索最后两个编译阶段 - 转换为SSA和生成机器代码。这将在第2部分中介绍。
附录-编译Go工具链
请先阅读《Go贡献指南》。 以下是有关复制修改后的Go编译器的一些快速说明,如本文所示。 有两种方式可以尝试本文的修改:
- 克隆Go官方仓库,手动应用本文中描述的修改。
- 克隆作者fork的Go官方仓库,并且检出
adduntil分支,所有这些更改已经与一些调试助手一起应用。 克隆目录是整个帖子中<src checkout>的位置。
要编译工具链,请进入src/目录并运行./make.bash。 我们也可以运行./all.bash来构建它之后运行许多测试。 运行make.bash会调用构建Go的完整3步引导过程,但在我的(老化)机器上只需要大约50秒。
构建完成后,工具链将安装在与src同级的bin中。 然后我们可以通过运行bin /go install cmd/compile来更快地重建编译器本身。
[1]Go has some special "magic" range clauses like a range over a string which splits its up into runes. This is where such transformations are implemented.