Golang 解釋器：Yaegi 內部實現

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/thgV_jg5cr5rrozso0lZ9w