本文代码基于Go 1.19

这是两篇系列文章中的第一篇，采取了基于教程的方法来探索Go编译器。编译器涵盖的内容太多了，细细讲完恐怕一本书都不够！所以这两篇文章的想法是提供一个快速的深度探索。我计划在将来在编译器的特定领域写更多的描述性文章。

我们将修改Go编译器以添加一个新的(玩具级的)语言特性，并重新构建编译器来支持我们添加的语法。

任务-添加新语句

许多语言都有while语句，在Go中的表示为for:

for <条件> {
  <循环体>
}

因此，在Go中添加一个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 i := 4; i == 0 {
    i--
    fmt.Println("Hello, until!")
}

下面我们将着手实现这些内容。

免责声明: 这只是一个玩具和练习，我不认为在Go中添加until是一个好主意; Go的极简主义是它的优势。

Go 编译器的顶层结构

默认的Go编译器(gc^[1])有一个相当经典的结构，如果您以前使用过其他编译器，应该会很容易上手:

Go编译器的实现在Go根目录的src/cmd/compile/internal下，文章后面提到的所有代码路径都将与此目录有关。这些代码都是用Go编写的，代码可读性很高。在这篇文章中，我们将逐个检查这些阶段，同时添加必要的代码来支持until语句。

Scan

scanner(也称为 lexer)帮助编译器将源代码文本分解为一个个的token，例如源码中的for变成了常量_For,...变成了_DotDotDot,.变成了_Dot等。

scanner的实现在syntax包内，我们需要让它理解一个新的关键词——until,文件syntax/token.go内有编译器能够理解的token列表，我们将在这里新加一个:

_Fallthrough // fallthrough
_For         // for
_Until       // until 👈
_Func        // func

token常量右边的注释很重要，它用来在文本中标识token，这是通过syntax/tokens.go中的代码生成来完成的，在token列表的上面有这样一行:

//go:generate stringer -type token -linecomment

go generate需要手动运行，输出的文件syntax/token_string.go会放在Go源码目录下，我们需要在syntax目录下运行以下命令来重新生成它:

GOROOT=<src checkout> go generate tokens.go

设置GOROOT对于Go 1.12来说是必须的^[2]，它必须指向我们修改编译器的源代码根目录。

在运行代码生成器并生成了syntax/token_string.go之后。现在有了新的token，我重新构建编译器并尝试运行后出现了panic:

panic: imperfect hash

它来自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”的查找。所谓”完美”是指它不希望出现碰撞，它只是一个线性数组，每个关键词都映射到一个索引。哈希函数非常特殊（它只看字符串标记的第一个字符的内容），而且很难去调试为什么一个新token会产生碰撞。为了解决这个问题，我们需要增加查找表的大小，将其改为[1<<7]token，从而将查找数组的大小从64改为128。这给了哈希函数更多的空间来分配它的key，碰撞也就消失了。

Parse

Go有一个相当标准的递归下降parser，它将词法分析器产生的Token流转换为具体的语法树。我们将先在syntax/nodes.go中为until添加一个新的节点类型:

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 _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语句进行解析。在其一般形式下，它支持三个部分（由分号分隔）。在for语句中，第三部分可以用于 “post”语句^[3]，但我们不打算让until支持这个，我们只对前两部分感兴趣。请注意，header接受源token，以便能够区分它当前处理的语句种类；例如，它将拒绝为if提供”post”语句。我们也应该明确地拒绝为until提供服务，尽管我现在还没有费心去实现这一点。

这些就是我们需要对语法分析器要做的所有变化。由于until在结构上与现有的语句非常相似，我们可以重复使用大部分的功能。

如果我们使用下面这段代码运行编译器来输出语法树的话(使用syntax.Fdump):

i = 4
until i == 0 {
    i--
    fmt.Println("Hello, 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  .  .  .  .  .  }

Type-check

编译的下一步是类型检查，它是在语法树上进行的，并使用 `types2` 包^[4]。除了检测类型错误外，Go中的类型检查还包括类型推断，这使得我们可以编写下面这样，不需要明确声明返回值类型的代码:

res, err := func(args)

Go类型检查器还做了一些工作，比如将标识符与它们的声明联系起来，以及计算编译时常量。代码在type2/中。我们再一次跟随for语句的引导，在Checker的stmt方法中的switch里加入这个子句:

case *syntax.UntilStmt:
    inner |= breakOk | continueOk

    check.openScope(s, "until")
    defer check.closeScope()

    check.simpleStmt(s.Init)
    if s.Cond != nil {
        var x operand
        check.expr(&x, s.Cond)
        if x.mode != invalid && !allBoolean(x.typ) {
            check.error(s.Cond, "non-boolean condition in for statement")
        }
    }
    check.stmt(inner, s.Body)

创建AST

现在我们有了一个经过类型检查的语法树，编译器建立了一个抽象的语法树。我过去写过关于抽象语法树与具体语法树的文章^[5]–如果你不熟悉它们的区别可以看看。不过，就Go而言，这一点在未来可能会被改变。Go编译器最初是用C语言编写的，后来翻译成了Go语言；它的一些部分是古老的C语言时代的遗留物，而另外一些部分则是新的。未来的重构可能只留下一种语法树，但现在（Go 1.19）这是我们必须遵循的过程。

AST代码存在于ir包中，节点类型在ir/node.go和ir/stmt.go中定义。

我们将首先在ir/node.go中添加一个新的常量来标识一个until节点。

// statements
// ...
OFALL     // fallthrough
OFOR      // for Init; Cond; Post { Body }
OUNTIL

我们将再次运行go generate，这次是在ir/node.go上，为新节点类型生成一个字符串表示:

// from the ir directory
GOROOT=<src checkout> go generate node.go

这应该会更新gc/op_string.go文件，以包括OUNTIL^[6]。我们需要运行的另一个工具是mknode.go，来自同一目录。这个工具为新节点生成了额外的代码:

// from the ir directory
GOROOT=<src checkout> <checkout/bin>go run -mod=mod mknode.go

现在让我们为我们的新语句定义AST节点类型:

type UntilStmt struct {
    miniStmt
    Label    *types.Sym
    Cond     Node
    Body     Nodes
    HasBreak bool
}

func NewUntilStmt(pos src.XPos, init Node, cond Node, body []Node) *UntilStmt {
    n := &UntilStmt{Cond: cond}
    n.pos = pos
    n.op = OUNTIL
    if init != nil {
        n.init = []Node{init}
    }
    n.Body = body
    return n
}

我们还需要更新ir/fmt.go，以便能够格式化/打印出我们的新节点进行调试:

// ... add this in OpNamse slice
OFOR:         "for",
OUNTIL:       "until", // 👈

还有stmtFmt方法中的这个switch语句:

case OUNTIL:
    n := n.(*UntilStmt)
    opname := "for"
    if !exportFormat {
        fmt.Fprintf(s, "%s loop", opname)
        break
    }

    fmt.Fprint(s, opname)
    if simpleinit {
        fmt.Fprintf(s, " %v;", n.Init()[0])
    }

    if n.Cond != nil {
        fmt.Fprintf(s, " %v", n.Cond)
    }

    if simpleinit {
        fmt.Fprint(s, ";")
    }

    fmt.Fprintf(s, " { %v }", n.Body)

最后，noder组件负责将语法树转换为AST；我们将在noder/stmt.go中添加下面这些代码:

// in irgen's stmt method...

case *syntax.ForStmt:
    return g.forStmt(stmt)
case *syntax.UntilStmt:      // 👈
    return g.untilStmt(stmt) // 👈

再添加一个新的方法:

func (g *irgen) untilStmt(stmt *syntax.UntilStmt) ir.Node {
    return ir.NewUntilStmt(g.pos(stmt), g.stmt(stmt.Init), g.expr(stmt.Cond), g.blockStmt(stmt.Body))
}

Analyze and rewrite AST

经过类型检查后，编译器会进行几个AST分析和重写阶段。准确的顺序在gc/main.go中的gc.Main函数中列出。在编译器术语中，这些阶段通常被称为passes。

许多passes不需要修改以支持until，因为它们在所有语句种类上都是通用的（这里gc.Node的通用结构很有用）。然而，仍有一些需要进行修改。例如逃逸分析，它试图找出哪些变量“逃离”了它们的函数作用域，因此必须在堆上而不是栈上分配。

逃逸分析按语句类型工作，因此我们必须在escape.stmt中添加这个switch子句：

case ir.OUNTIL:
    n := n.(*ir.UntilStmt)
    e.loopDepth++
    e.discard(n.Cond)
    e.block(n.Body)
    e.loopDepth--

现在我们进入编译器中间阶段的最后一个阶段：重写AST。在Go编译器术语中，这一步被称为“walk”。其主要目标是将复杂操作分解成更简单的操作，以便编译器后端处理更少的操作类型。

我们需要更新walk/order.go文件，以便它能够识别我们添加的新AST节点。这个节点并没有做太多事情，只是作为转换的一个传递点：

case ir.OUNTIL:
    n := n.(*ir.UntilStmt)
    t := o.markTemp()
    n.Cond = o.exprInPlace(n.Cond)
    n.Body.Prepend(o.cleanTempNoPop(t)...)
    orderBlock(&n.Body, o.free)
    o.out = append(o.out, n)
    o.cleanTemp(t)

代码的其余部分收集了一堆AST转换，有助于稍后将AST改写为SSA。例如，它会将for循环中的`range`重写^[7]为具有显式循环变量的简单形式。它还将map操作^[8]重写为运行时调用等等。

接下来才是我们将实现新until语句的地方: 通过将其转化为一个反向条件的for循环。

我们从walk/stmt.go中处理switch语句的部分开始：

case ir.OUNTIL:
    n := n.(*ir.UntilStmt)
    return walkUntil(n)

然后再添加walkUntil函数:

func walkUntil(n *ir.UntilStmt) ir.Node {
    if n.Cond != nil {
        init := ir.TakeInit(n.Cond)
        walkStmtList(init)
        n.Cond = ir.NewUnaryExpr(base.Pos, ir.ONOT, walkExpr(n.Cond, &init))
        n.Cond = ir.InitExpr(init, n.Cond)
    }

    walkStmtList(n.Body)
    return ir.NewForStmt(n.Pos(), nil, n.Cond, nil, n.Body)
}

这样就好了！将UntilStmt节点重写为ForStmt节点，并在条件上添加一元布尔否定（实质上是!运算符），就像文章开头所讨论的那样。

试试看

我们现在可以尝试使用修改后的编译器，并运行一个使用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!

提醒："<src checkout>" 是我们修改Go代码、修改并编译的目录（更多细节请参见附录）。

第一部分总结

这就是第一部分的全部内容。我们已经成功地在Go编译器中实现了一个新语句。虽然我们没有涵盖编译器的所有部分，但我们可以采取将until节点的AST重写为for节点的捷径。这是一种很有效的编译策略，而且Go编译器已经有许多类似的转换来规范化AST（将许多形式减少到较少的形式，以便最后阶段的编译工作量更小）。尽管如此，我们仍然会探索最后两个编译阶段——转换为SSA和生成机器代码。这将在第二部分中介绍。