Yaegi[2] 是一个用 Go 语言编写的 Go 语言解释器。这个项目最初是在 Traefik-Labs 启动的,目的是为 traefik 反向代理提供一个简单实用的嵌入式插件引擎。现在,社区贡献的 200 多个插件已经列在 plugins.traefik.io[3] 的公共目录中。Yaegi 的使用也扩展到其他领域,例如 数据库[4] 、 可观察性[5] 、 容器安全[6] 以及 许多其他领域[7] 。
Yaegi 精简而强大,它在一个单一的包中提供了一个完整的 Go 解释器,符合 Go 规范[8] ,没有外部依赖。精简,但也强大:它的代码密集、复杂,不总是符合惯用做法,有时可能难以理解。
本文档旨在解决这个问题。在下文中,在获得概述后,我们将深入研究内部结构,探索内部机制并讨论设计。我们的目标是提供基本的见解,阐明架构和代码组织。但首先,让我们看一下概述。
架构概述
让我们看看当执行以下行时 yaegi 内部会发生什么:
fmt.Println("Hello, World!")
图 1 显示了解析的主要步骤:
- 扫描器(由 go/scanner[9] 包提供)通过 词法分析[10] 步骤将字符流(源代码)转换为标记流。
- 解析器(由 go/parser[11] 包提供)通过 语法分析[12] 步骤将标记流转换为 抽象语法树[13] 或 AST。
- 分析器(在 yaegi/interp[14] 包中实现)执行类型、常量、变量和函数符号的检查和创建。它还通过 语义分析[15] 步骤计算 控制流图[16] 和符号的内存分配。所有这些元数据都从 AST 的节点获取并存储到节点中,使其成为带注释的 AST。
- 生成器(在 yaegi/interp[13] 包中实现)读取带注释的 AST 并生成要执行的代码指令,通过 代码生成[17] 步骤。
- 执行器(在 yaegi/interp[13] 包中实现)在解释器的上下文中运行代码指令。
解释器的设计类似于一个简单的编译器,只是代码生成到内存中而不是目标文件中,并且有一个执行器模块来运行特定的指令格式。
我们不会详细讨论由标准库提供的扫描器和解析器,而是直接研究分析器。
语义分析
分析器对要解释的程序执行语义分析。这分几个步骤完成,所有步骤都包括读取和写入 AST,所以我们首先检查 AST 表示的细节和动态。
AST 动态
下面是任何编译器、解释器或其他语言工具中最重要的数据结构,以及使用它的函数(摘自 这里[18] )。
type node struct { child []*node // child subtrees anc *node // ancestor pos token.Pos // position in source code kind nkind // kind of node action action // function to run typ *itype // type of value ident string // set if node is a var or func val interface{} // static generic value rval reflect.Value // reflection value to access runtime Go value } func (n *node) Walk(in func(n *node) bool, out func(n *node)) { if in != nil && !in(n) { return } for _, child := range n.child { child.Walk(in, out) } if out != nil { out(n) } }
上面的代码看似简单。与许多复杂系统一样,重要的部分是由元素之间的关系和它们形成的模式承载的。通过显示相应的图表并将系统视为一个整体,更容易理解它。我们可以使用一个简单的例子来做到这一点:
fmt.Println("Hello, World!")
相应的 AST 是:
这是从解析器获得的原始 AST,没有注释。每个节点包含一个索引号(仅用于标记目的),以及节点类型,由解析器从 Go 语法规则集中计算得出(例如,"stmt"表示" 语句[19] 列表","call"表示"调用 表达式[20] ",...)。我们还在叶子位置识别源标记作为字面值。
遍历树包括从根(节点 1)开始访问节点,按照它们的编号顺序(这里从 1 到 15):深度优先(子节点在兄弟节点之前)从左到右。在每个节点,在进入时调用回调 in(预处理),在退出时调用回调 out(后处理)。
当 in 回调执行时,除了在节点祖先中计算的预处理信息外,只有在节点左侧的子树中计算的信息可用。in 回调返回一个布尔值。如果结果为 false,则跳过节点子树,允许短路处理,例如避免深入函数体并只处理函数签名。
当 out 回调执行时,整个后代子树上计算的结果都可用,这对于计算跨嵌套结构定义的复合对象的大小很有用。在没有后处理的情况下,需要多次树遍历才能达到相同的结果。
因此,语义分析步骤只是带有正确回调的树遍历。在我们的解释器中,我们需要执行两次树遍历:在 interp/gta.go[21] 中进行全局和类型分析,在 interp/cfg.go[22] 中进行控制流图分析。在这两个文件中,注意对 root.Walk 的调用。
注意:我们选择将 AST 表示为统一的节点结构,而不是 Go 标准库中的 ast.Node[23] 接口,该接口由所有节点类型的专门类型实现。主要原因是树遍历方法 ast.Inspect[24] 只允许预处理回调,而不允许后处理回调,而后处理回调对于几个编译步骤是必需的。当时,从这个统一的结构开始似乎更简单,我们最终坚持使用它。
全局和类型分析
我们对 AST 的第一个操作是检查和注册在全局级别声明的程序的所有组件。这是一个部分分析,只关注声明而不是函数实现。
这一步是必要的,因为在 Go 中,在全局级别,符号可以在声明之前使用(与 Go 函数体或一般的 C 语言不同,在严格模式下禁止在声明之前使用)。
允许符号无序使用是允许代码在包中的多个文件中任意分散而不受更多约束的原因。这确实是一个重要特性,让程序员可以按照她想要的方式组织代码。
这一步在 interp/gta.go[20] 中实现,包括只有预处理回调的树遍历(没有传递 out 函数)。有两个特点:
第一个是多遍迭代遍历。实际上,在第一次全局遍历中,每当遇到不完整的定义时,不是立即失败并报错,而是将失败的子树的引用保存在要重试的节点列表中,然后遍历完成整个树。然后,所有有问题的子树都会被迭代重试,直到所有节点都被定义,或者只要有进展。也就是说,如果两次连续的迭代导致完全相同的状态,这表明没有进展,会导致无限循环,此时 yaegi 就会停止并报错。
第二个特点是,尽管处于部分分析步骤,如果表达式子树用于实现全局类型定义,仍然可能需要对其进行完整解释。例如,如果数组大小由表达式计算,如以下有效的 Go 声明:
const prefix = "/tmp/" const path = "file.txt" var buf [len(prefix+path) + 2]byte
一个悖论是编译器需要一个解释器来执行类型分析!实际上,在上面的例子中,[16]int(因为 len(prefix+path) + 2 = 16)本身就是一个特定类型,与例如 [14]int 不同。这意味着即使我们只处于类型分析阶段,我们已经必须能够计算 len(prefix+path) + 2 表达式。在 C 语言中,这是 预处理器[25] 的角色之一,这意味着编译器本身不需要能够实现这一点。在 Go 中,规范强制编译器实现者提供并尽早使用上述涉及的机制,这通常被称为常量折叠优化。因此,它在标准 gc 和 yaegi 中都有实现。同样的方法在 Zig 语言[26] 中被推到了极致,使用其 comptime[27] 关键字。
控制流图
在 GTA 之后,所有全局符号都已正确定义,无论它们的声明顺序如何。现在我们可以进行完整的代码分析,这将通过 interp/cfg.go[21] 中的单次树遍历来执行。
预处理和后处理回调都提供给遍历函数。尽管在单次遍历中激活,但执行了多种数据处理:
- 类型检查和创建。在 GTA 中开始,现在在所有函数体中也完成。
- 变量作用域分析:在预处理中打开作用域级别,在后处理中关闭,因为作用域的嵌套反映了 AST 结构。
- 精确计算对象大小和位置。
- 识别和排序操作。
最后一点对代码生成至关重要。它包括生成控制流图。CFG 通常以中间表示(IR)的形式表示,这实际上是一个简化的与机器无关的指令集,如 GCC GIMPLE[28] 、 LLVM IR[29] 或 Go 编译器中的 SSA[30] 形式。在 yaegi 中,不生成 IR,只使用 AST 注释。
让我们用之前的例子来解释:
在 AST 中,与 CFG 相关的节点是_操作_节点(蓝色),即引用算术或逻辑操作、函数调用或内存操作(分配变量、访问数组条目等)的节点。
构建 CFG 包括识别操作节点,然后找到它们的后继(存储在节点字段 tnext 和 fnext 中)。一个操作节点在一般情况下有一个后继(用绿色箭头显示),或者如果操作与条件分支相关联,则有两个后继(如果测试为真则为绿色箭头,否则为红色箭头)。
确定动作节点的后继规则是基于其邻居(祖先、兄弟和后代)的属性而固有的。例如,在if子树(节点5到12)中,要执行的第一个动作是条件测试,即条件子树中的第一个动作,这里是节点6。这个动作将有两个可选的后继:一个在测试为真时执行,另一个在测试为假时执行。"真"的后继将是if节点的第二个子子树中的第一个动作,描述"真"分支(这个子树的根是节点9,第一个动作是10)。由于我们的例子中没有if的"假"分支,整个if子树的下一个动作是if兄弟子树中的第一个动作,这里是节点13。因此,这个节点将是"假"的后继,即当if条件失败时要执行的第一个动作。最后,节点13也是"真"分支的后继,即节点10。相应的实现位于后处理CFG回调中的 16行代码块[31] 中。请注意,同样的代码还执行了死分支消除和条件有效性检查。在这个阶段,就控制流而言,我们的AST示例现在可以看作是一个更简单的表示,如下所示。
在我们的例子中,组成CFG的动作节点可以执行以下几种操作:
- 在内存中定义变量并为其赋值
- 执行算术或逻辑运算
- 条件分支
- 函数调用
添加跳转到"向后"位置的能力(目标节点索引小于源节点索引,从右到左的箭头),从而允许"循环",使动作集变得 图灵完备[32] ,实现了通用计算机。
这里的普遍性特征在于控制流图的循环性质(注意if语句图虽然看起来是循环的,但实际上不是,因为条件分支是互斥的)。
这不仅仅是理论上的。例如,在Linux eBPF验证器[33] 的设计中,禁止向后跳转是至关重要的,以便让用户提供的(因此不受信任的)代码片段在内核系统特权环境中执行,并保证不会出现无限循环。
代码生成和执行
yaegi中实现的编译器针对的是Go运行时本身,而不是特定的硬件架构。对CFG中的每个动作节点,都会生成相应的闭包。主要好处是:
- 可移植性:生成的代码可以在任何支持Go的平台上运行。
- 互操作性:解释器生成的对象可以直接以reflect值的形式被宿主程序使用。
- 内存管理,特别是垃圾收集器,由运行时提供,也适用于解释器创建的值。
- 运行时类型安全、切片、映射、通道、goroutine的支持也由运行时提供。
动作模板位于 interp/run.go[34] 和 interp/op.go[35] 中。生成闭包允许优化所有使用常量的情况(涉及常量和变量的操作比涉及两个变量的相同操作更便宜和快速)。它还允许硬编码控制流图,即预定义要执行的下一条指令,避免不必要的分支测试。
解释器针对的伪架构实际上是一个虚拟 栈机[36] ,其中内存表示为Go reflect值的切片,如下图所示,指令直接由AST中的一组动作节点(CFG)表示。这些原子指令,也称为"内置指令",比真正的硬件指令集稍高级一些,因为它们直接操作Go接口(更准确地说是它们的reflect表示),隐藏了Go运行时提供的大量低级处理和细节。
解释器执行的内存管理包括在新会话时创建一个全局帧(栈顶),填充所有全局值(常量、类型、变量和函数)。每次解释的函数调用时,都会在栈上推送一个新帧,包含该函数的所有返回值、输入参数和局部变量的值。
结论
我们描述了一个Go解释器的总体架构,重用了现有的Go扫描器和解析器。我们重点关注了基于AST注释的语义分析,直到控制流图和代码生成。这种设计导致了一个一致且简洁的编译器,适用于嵌入式解释器。我们还简要概述了基于Go运行时的虚拟栈机,利用了Go标准库提供的反射层。
现在我们可以发展这种设计来针对不同的目标架构,例如一个更高效的虚拟机,这已经在进行中。
yaegi的一些部分还没有详细介绍,将在下一篇文章中讨论:
- 与预编译包的集成
- Go泛型
- 递归类型
- 接口和方法
- 虚拟化和沙箱
- REPL和交互式使用
附:感谢 @lejatorn[37] 对这篇文章的反馈和建议。
参考链接
- Marc 的编程笔记: https://marc.vertes.org/
- Yaegi: https://github.com/traefik/yaegi
- plugins.traefik.io: https://plugins.traefik.io/
- 数据库: https://github.com/xo/xo
- 可观察性: https://github.com/slok/sloth
- 容器安全: https://github.com/cyberark/kubesploit
- 许多其他领域: https://github.com/traefik/yaegi/network/dependents?package_id=UGFja2FnZS0yMjc1NTQ3MjIy
- Go 规范: https://go.dev/ref/spec
- go/scanner: https://pkg.go.dev/go/scanner
- 词法分析: https://en.wikipedia.org/wiki/Lexical_analysis
- go/parser: https://pkg.go.dev/go/parser
- 语法分析: https://en.wikipedia.org/wiki/Syntax_analysis
- 抽象语法树: https://en.wikipedia.org/wiki/Abstract_syntax_tree
- yaegi/interp: https://pkg.go.dev/github.com/traefik/yaegi/interp
- 语义分析: https://en.wikipedia.org/wiki/Semantic_analysis_(compilers)
- 控制流图: https://en.wikipedia.org/wiki/Control-flow_graph
- 代码生成: https://en.wikipedia.org/wiki/Code_generation_(compiler)
- 这里: https://github.com/traefik/yaegi/blob/8de3add6faf471a807182c7b8198fe863debc9d8/interp/interp.go#L284-L296
- 语句: https://go.dev/ref/spec#Statements
- 表达式: https://go.dev/ref/spec#Expressions
- interp/gta.go: https://github.com/traefik/yaegi/blob/master/interp/gta.go
- interp/cfg.go: https://github.com/traefik/yaegi/blob/master/interp/cfg.go
- ast.Node: https://pkg.go.dev/go/ast#Node
- ast.Inspect: https://pkg.go.dev/go/ast#Inspect
- 预处理器: https://gcc.gnu.org/onlinedocs/cpp/
- Zig 语言: https://ziglang.org/
- comptime: https://ziglang.org/documentation/master/#comptime
- GCC GIMPLE: https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html
- LLVM IR: https://llvm.org/docs/LangRef.html
- SSA: https://github.com/golang/go/blob/bf48163e8f2b604f3b9e83951e331cd11edd8495/src/cmd/compile/internal/ssa/README.md
- 16行代码块: https://github.com/traefik/yaegi/blob/8de3add6faf471a807182c7b8198fe863debc9d8/interp/cfg.go#L1608-L1624
- 图灵完备: https://en.wikipedia.org/wiki/Turing_completeness
- eBPF验证器: https://www.kernel.org/doc/html/latest/bpf/verifier.html
- interp/run.go: https://github.com/traefik/yaegi/blob/master/interp/run.go
- interp/op.go: https://github.com/traefik/yaegi/blob/master/interp/op.go
- 栈机: https://en.wikipedia.org/wiki/Stack_machine
- @lejatorn: https://twitter.com/@lejatorn
