golang源码分析（18）添加一个新语句到Golang编译器内部

golangLeetcode

发布于 2022-08-02 16:36:23

3280

发布于 2022-08-02 16:36:23

任务：添加一个新语句

许多语言都有一个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-compiler-flow

相对于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.

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除

ide