用 go 实现 lua 虚拟机

虚拟机执行流程

解释型语言的解释过程一般经过下面的步骤

1. 词法分析，即按照一定的规则解析出所有 token，这是 lexer 完成的工作。
2. 组合成语法树，我们之前介绍的 yacc 就是根据语法规则，自动解析语法树的工具。除了 goyacc，go 里面还有一些工具可以帮助解析 go 风格的代码语法树，很多 go 语法脚本语言就是利用 go 源代码种的这些工具，简化了他们的实现难度。
3. 定义一套指令集，这套指令风格各异，又有基于栈或寄存器的虚拟机区别，但是大都比较类似，类似这样的命令: (optAdd) , 这个例子的命令表示一个 加法操作，可能的意思是：从栈上取两个数字，相加之后再返回到栈上。有时候这种命令还有一些操作数，但是会尽量用一个数字表示【通过不同位的划分，分别表示 命令类型、多个操作数】。
   • Lua 采用定长指令集. 每个指令 4 字节，其中 6 bit用于操作码 (Opcode), 26 bit用于操作数(Operand)
4. 生成字节码【指令集中的指令的集合】，将所有的运行命令解析成一组指令，
5. 做一些优化，生成的字节码一般时有一些优化空间的，比如常见的 尾调用优化 等
6. 执行字节码则比较简单，在操作指令设计完善并解析完成之后，执行字节码只是依次执行一个个指令就可以。
   • 这里把执行字节码的主体命名为 luaState, 他实现一组 luaAPI，这部分参考 lua 的官方实现

下面依次介绍上面的一些步骤，本文旨在一篇文章写清楚大概流程，具体的细节将会忽略，实际的实现也会尽可能的简化，本文主要参考 自己动手实现 lua，和 gopher-lua

词法分析/解析语法树

这个其实在 goyacc 实战 里面已经给出了不少例子了。这步其实比较简单，重要的时了解 lua 中的 token，lua 语法。bnf 语法参考这里.

• gopher-lua 使用手写 lexer + goyacc 实现【yacc 实现】，而 lua-go 都是手写。
• 这里我们主要参考 gopher-lua 的实现，这个实现基本和 bnf 可以完全对应上。gopher-lua 在解析语法树的时候并没有定义 block，而是直接用的列表 []stmt 表示一组语句 【下面的 Stmts=[]stmt】，stmt 则由 一些 expr 组成，所以解析的时候，最核心的部分就是定义出 stmt 和 expr.
• 根据 bnf 的定义，stmt/expr 可以分成下面的几类：

stat ::=  varlist1 `=´ explist1  |  【赋值语句 AssignStmt{Lhs, Rhs Exprs}】
         functioncall  |   【函数调用语句 FuncCallStmt{Expr}】
         do block end  |   【do 语句，DoBlockStmt{Stmts}】
         while exp do block end  |【 while 语句, WhileStmt{Expr, Stmts}】
         repeat block until exp  |【 repeat 语句，RepeatStmt{Expr, Stmts}】
         if exp then block {elseif exp then block} [else block] end  |【if 语句 IfStmt{Condition Expr, Then, Else Stmts}】
         for Name `=´ exp `,´ exp [`,´ exp] do block end  |【数值 for 语句】
         for namelist in explist1 do block end  |【通用 for 语句, GenericForStmt{Names, Exprs, Stmts}】
         function funcname funcbody  |【函数定义语句 FuncDefStmt{FuncName{Func,Receiver,Method},FunctionExpr{ParList,Stmts}}】
         local function Name funcbody  |【LocalAssignStmt{Names, Exprs}】
         local namelist [`=´ explist1]【LocalAssignStmt{Names, Exprs}】
         
exp ::= nil  |   【NilExpr】
        false  |  【FalseExpr】
        true  |  【TrueExpr】
        Number  |  【ConstExpr】
        String  |  【StringExpr】
        `...´  |    【Comma3Expr】
        function  |  【FunctionExpr】
        prefixexp  |  【包括 FuncCallExpr】
        tableconstructor  |  【TableExpr】
        exp binop exp  |  【算数/比较表达式 RelationalOpExpr，ArithmeticOpExpr，StringConcatOpExpr】
        unop exp  【UnaryMinusOpExpr，UnaryNotOpExpr，UnaryLenOpExpr】

定义指令集

• lua 的指令集占用 4 个字节，其中低 6 比特用于操作码，高 26 比特用于操作数。由于不同指令使用的操作数个数和方式不同，高 26 比特的使用又有几种方式：iABC; iABx; iAsBx; iAx
  

  image
• lua 5.3 有 47 种操作码
• 操作数根据其类型，可以分成几种:
  • OpArgN: 不使用
  • OpArgU: 使用
  • OpArgR: 在 iABC 下表示寄存器索引，在 iAsBx 下表示跳转偏移
  • OpArgK: 表示常量表索引或者寄存器索引
• 这些是 luavm 在实现的时候定义的指令集，当然也可以不这么实现，但是作为 vm 实现教科书存在的 luavm 的设计很值得参考，具体的 opcode 介绍可以参考这里.
• 注意这种奇怪的高度压缩的设计最主要还是为了让指令集变得更精简，以便在4个字节内表达出来
• 为了方便在代码中使用，可以定义一个指令表，把每个指令都映射到一个 结构体，比如这样:

// 《自己动手实现 lua》
type opcode struct {
	testFlag byte // operator is a test (next instruction must be a jump)
	setAFlag byte // instruction set register A
	argBMode byte // B arg mode
	argCMode byte // C arg mode
	opMode   byte // op mode
	name     string
	action   func(i Instruction, vm api.LuaVM)
}


/* OpMode */
/* basic instruction format */
const (
	IABC  = iota // [  B:9  ][  C:9  ][ A:8  ][OP:6]
	IABx         // [      Bx:18     ][ A:8  ][OP:6]
	IAsBx        // [     sBx:18     ][ A:8  ][OP:6]
	IAx          // [           Ax:26        ][OP:6]
)

/* OpArgMask */
const (
	OpArgN = iota // argument is not used
	OpArgU        // argument is used
	OpArgR        // argument is a register or a jump offset
	OpArgK        // argument is a constant or register/constant
)

var opcodes = []opcode{
	/*     T  A    B       C     mode         name       action */
	opcode{0, 1, OpArgR, OpArgN, IABC /* */, "MOVE    ", move},     // R(A) := R(B)
	opcode{0, 1, OpArgK, OpArgN, IABx /* */, "LOADK   ", loadK},    // R(A) := Kst(Bx)
	opcode{0, 1, OpArgN, OpArgN, IABx /* */, "LOADKX  ", loadKx},   // R(A) := Kst(extra arg)
	...
}

栈结构 (寄存器)

• 实现一个虚拟机有几个重要的结构，分别用来存 opcode；运行中使用的值；运行中的其他信息，比如变量，调用信息等
• 其中运行中使用的值一般使用一种栈结构来存储，lua vm 实现里面不仅仅是栈结构，因为还还支持索引操作。但是基本的 interface 类似如下.

type LuaStack interface{
    Push(value)
    Pop() value
    Get(index) value
}

• 在 LuaVm 暴露的 Get 方法里面，还分了几种情况，可能时取寄存器的值，也可能时取 Upvalues 的值，具体要看 index 的取值范围
• 具体实现的时候可能会有很多辅助函数，但是基本可以分成三类：栈操作、栈访问、入栈。比如 ：GetTop(), CheckStack(n), Pop(n), Copy(from, to), PushValue(idx), Replace(idx), Insert(idex), Remove(idx) ... 其中大部分操作 是操作 某 idx 的值 <==> 栈顶值
• lua 官方的 luaState 【可以理解成 luaVm 最主要的核心部分，stack 结构时 luaState 的一个子结构】暴露的结构大部分也属于这 3 类。gopher-lua 把这个结构命名为 registry，这是 lua 虚拟机实现时寄存器实现的一个体现。
• 函数调用也借助 "栈" 结构，区别于 Lua 栈，称为函数调用栈 (Call Stack). Lua 栈里面放值，调用栈里面放调用帧 (Call Frame)

实现指令操作

• 指令就是 上面介绍 opcode，执行指令的过程就是不断执行当前 pc 位置的 opcode 直到结束，指令的执行会操作栈结构甚至启动新的递归调用栈。
• lua 5.3 中有 47 个指令，上面按照指令的格式分成了 iABC; iABx; iAsBx; iAx；实现的时候为了理清思路也可以按照下面的方式进行分类
  • 移动和跳转类：比如 MOVE(iABC)，用 R(X) 表示寄存器 N，那么 MOVE 表示 R(A) := R(B)，下面时实现的一个例子。JMP(iAsBx).
  • 加载类：比如 LOADNIL(iABC), LOADBOOL(iABC), LOADK, LOADKX, 给寄存器设置 nil，bool, 或者来自 常量表的一个值.
  • 算术运算类：二元或者一元操作符，对操作数指定的寄存器位置的数字进行一些计算，然后放入操作数指定的另一个寄存器中.
  • 长度和拼接类：比如 LEN(iABC), CONTACT(iABC), 分别表示 R(A) := lenght of R(B); R(A) := contact(R(B)...R(C))
  • 比较类：iABC, 表示 if((RK(B) op RK(C) ~= A) then pc ++
  • 逻辑运算类：比如 NOT, TESTSET, TEST
  • For 循环指令: 由两个指令完成 FORPREP, FORLOOP； 一个是准备操作，一个是执行 loop；通用 for 循环为 TFORCALL，TFORLOOP
  • 表相关指令: 用于 lua 内部的表数据结构的相关操作，比如 NEWTABLE, GETTABLE, SETTABLE，SETLIST【由于 lua 的表融合的 hash table 和 list 的功能，SETLIST 用于对其 list 部分进行操作】 等
  • 函数调用类：函数调用类的操作稍微复杂一点，因为涉及了 "函数栈" 的操作。函数栈的实现一般可以用一个链表实现，在之前实现的栈结构里面增加一些属性，记录 函数调用的 closure， args， pc 等信息，以及一个 prev 或 parent 指针，指向调用者的栈结构. 相关的指令有:
    • CLOSURE: R(A) := closure(KPROTOBx); KPROTO 为当然函数原型的子函数原型表
    • CALL: iABC，调用 lua 函数 R(A), ... ,R(A+C-2) := R(A)(R(A+1), ... ,R(A+B-1))
    • RETURN：iABC【操作数 C 没用】，return R(A), ... ,R(A+B-2)
    • VARGS：iABC， R(A), R(A+1), ..., R(A+B-2) = vararg
    • TAILCALL：用于尾调用优化
    • SELF：用来优化方法调用语法糖，
    • 其他内置函数：由于 lua 的实现非常简单，我们实际使用的时候还需要一些内置的系统函数，比如时间，文件等操作，实现的方式也比较简单，直接注册宿主语言相关的函数到 luavm 内部即可，比如 c 实现的 luavm 会调用 c lib 函数，而 go 实现也类似，可以注册一些 go 标准库函数给 lua 使用。
    • 元函数：lua 支持元函数，类似 python 的 __init__， __call__, __get__ 之类的函数，这类函数有特殊的意义，元函数放在类型的 元表【表有自己元表，其他类型共享元表】里面。比如 __add 函数 用于加法操作，用户可以对 元表进行扩展，达到对 lua 语言进行扩展的目的。lua 中的 meta 方法调用在 内置方法不匹配之后。
  • Upvalue 相关的操作：upvalue 时 lua 的一个术语，表示闭包内部捕获的非局部变量。GET/SETUPVAL 表示 R(A) := UpValueB 和 UpValueB := R(A) 用于从 upvalue 表中取值放入寄存器，或者相反；GET/SETTABUP 分别表示 R(A) := UpValue[B][RK(C)] 和 UpValue[A][RK(B)] := RK(C) 用于 upvalue 是 table 的情况。
• 指令的实现一般用一个表【数组】来实现，这样代码会比较清晰，效率也比较高，比如 gopher-lua 的 jumptable, lua-go 的 opcodes

// R(A) := R(B)
func move(i Instruction, vm LuaVM) {
	a, b, _ := i.ABC()
	a += 1
	b += 1

	vm.Copy(b, a)
}

生成指令

• 这步完成从 stmts 到 codes 的转换，当然只是 codes 并无法运行，我们还需要要借助前面定义的栈结构，以及一些辅助的变量表，比如常量表，局部变量表，Break 表，Upvalue 表等type funcInfo struct { parent *funcInfo // 父函数，即 caller subFuncs []*funcInfo // 子函数, 即 callee usedRegs int // 使用的寄存器个数, 这里记录数量即可 在 luaVm 再分配 maxRegs int // 使用的最大寄存器个数 scopeLv int // scope level locVars []*locVarInfo // 本地变量，函数参数也是本地变量 locNames map[string]*locVarInfo // 本地变量表 upvalues map[string]upvalInfo // upvalue表 constants map[interface{}]int // 常量表 breaks [][]int // break 跳转位置，可能解析结束才知道跳转位置，在 exitScope 的时候修复 insts []uint32 // 即 code 列表 lineNums []uint32 // debug 用 line int // debug 用 lastLine int // debug 用 numParams int // 参数个数 isVararg bool // 是否是变参 }
• 编译中最重要的是编译函数，整个 lua 代码都可以看成是一个 main 函数， 以下是 函数编译生成结构的定义, 编译的过程就是生成 funcInfo 的过程
• 所有指令编译最后运行的语句都是 emitABC, emitABx .. 这种格式，表示输出格式为标准指令集格式的 code
• 根据变量名找一个变量的时候需要从 local, up, global 几种变量表中去找，找到之后根据不同生成不同的 code
• 看一个具体的编译 expr 的例子 // r[a] := exp1 op exp2 func cgBinopExp(fi *funcInfo, node *BinopExp, a int) { switch node.Op { case TOKEN_OP_AND, TOKEN_OP_OR: oldRegs := fi.usedRegs b, _ := expToOpArg(fi, node.Exp1, ARG_REG) // 编译 exp1 fi.usedRegs = oldRegs // 恢复使用的 reg 个数 if node.Op == TOKEN_OP_AND { // 写入 OP_TESTSET 指令 fi.emitTestSet(node.Line, a, b, 0) } else { fi.emitTestSet(node.Line, a, b, 1) } pcOfJmp := fi.emitJmp(node.Line, 0, 0) // 写入 OP_JMP 指令 b, _ = expToOpArg(fi, node.Exp2, ARG_REG) // 编译 exp2 fi.usedRegs = oldRegs // 恢复使用的 reg 个数 fi.emitMove(node.Line, a, b) // r[a] = r[b] fi.fixSbx(pcOfJmp, fi.pc()-pcOfJmp) // 修复 jump 指令，即设置前面的 jump 操作指向位置，这里的 jump 为短路操作 default: oldRegs := fi.usedRegs b, _ := expToOpArg(fi, node.Exp1, ARG_RK) // exp1 c, _ := expToOpArg(fi, node.Exp2, ARG_RK) // exp2 fi.emitBinaryOp(node.Line, node.Op, a, b, c) // 其他 BinaryOp 操作，比如 arith/bitwise/relational fi.usedRegs = oldRegs } } func (self *funcInfo) emitBinaryOp(line, op, a, b, c int) { if opcode, found := arithAndBitwiseBinops[op]; found { self.emitABC(line, opcode, a, b, c) // 直接查询 } else { switch op { case TOKEN_OP_EQ: self.emitABC(line, OP_EQ, 1, b, c) case TOKEN_OP_NE: self.emitABC(line, OP_EQ, 0, b, c) case TOKEN_OP_LT: self.emitABC(line, OP_LT, 1, b, c) case TOKEN_OP_GT: self.emitABC(line, OP_LT, 1, c, b) case TOKEN_OP_LE: self.emitABC(line, OP_LE, 1, b, c) case TOKEN_OP_GE: self.emitABC(line, OP_LE, 1, c, b) } // 比较表达式需要多个指令，原因参考指令集的定义 // 因为 expr1 == expr2 => jump 到 a=true 或者 jump 到 a=false self.emitJmp(line, 0, 1) self.emitLoadBool(line, a, 0, 1) self.emitLoadBool(line, a, 1, 0) } } // 这是一个辅助函数，作用是返回作为 args 用的 参数位置 和类型 // 这种情况有几种类型 ARG_CONST（常量表 index） // ARG_REG (register 表 index)， ARG_UPVAL（upvalue 表 index） func expToOpArg(fi *funcInfo, node Exp, argKinds int) (arg, argKind int) { if argKinds&ARG_CONST > 0 { idx := -1 switch x := node.(type) { case *NilExp: idx = fi.indexOfConstant(nil) case *FalseExp: idx = fi.indexOfConstant(false) case *TrueExp: idx = fi.indexOfConstant(true) case *IntegerExp: idx = fi.indexOfConstant(x.Val) case *FloatExp: idx = fi.indexOfConstant(x.Val) case *StringExp: idx = fi.indexOfConstant(x.Str) } if idx >= 0 && idx <= 0xFF { return 0x100 + idx, ARG_CONST } } if nameExp, ok := node.(*NameExp); ok { if argKinds&ARG_REG > 0 { if r := fi.slotOfLocVar(nameExp.Name); r >= 0 { return r, ARG_REG } } if argKinds&ARG_UPVAL > 0 { if idx := fi.indexOfUpval(nameExp.Name); idx >= 0 { return idx, ARG_UPVAL } } } a := fi.allocReg() cgExp(fi, node, a, 1) return a, ARG_REG }
• 下面是一个编译语句(stmt/stat) 的例子

/*
           ______________
          /  false? jmp  |
         /               |
while exp do block end <-'
      ^           \
      |___________/
           jmp
*/
func cgWhileStat(fi *funcInfo, node *WhileStat) {
	pcBeforeExp := fi.pc() // pc 

	oldRegs := fi.usedRegs // 保存使用的 reg 个数
	a, _ := expToOpArg(fi, node.Exp, ARG_REG) // 编译 exp
	fi.usedRegs = oldRegs  // 恢复

	line := lastLineOf(node.Exp) 
	fi.emitTest(line, a, 0) // 输出测试指令
	pcJmpToEnd := fi.emitJmp(line, 0, 0) // jump

	fi.enterScope(true)    // 进入 scope 
	cgBlock(fi, node.Block)  // 编译 block 
	fi.closeOpenUpvals(node.Block.LastLine) // 关闭 upvals
	fi.emitJmp(node.Block.LastLine, 0, pcBeforeExp-fi.pc()-1) // jump to  while 的开头
	fi.exitScope(fi.pc())  // 退出 scope 

	fi.fixSbx(pcJmpToEnd, fi.pc()-pcJmpToEnd) // fix jump 
}

执行指令

• 执行指令的主体是 luavm，执行过程就是不断按照指令集的定义执行指令的过程，执行的时候比较特殊的是 call 指令，需要注意处理调用栈，其他都是按照定义执行即可

type luaStack struct {
	/* virtual stack 值结构 */
	slots []luaValue
	top   int
	/* call info 增加调用信息 */
	closure *closure
	varargs []luaValue
	pc      int
	/* linked list 调用栈的体现 */
	prev *luaStack 
}

// callLuaClosure 简化流程
1. funcAndArgs := oldStack.pop(nArgs+1)
2. newStack.pushN(funcAndArgs[1:], nParams)
3. self.pushLuaStack(newStack)
4. self.runLuaClosure(newStack)
5. self.popLuaStack()
6. results := newStack.popN(newStack.pop - nRegs)
7. self.stack.pushN(results, nResults)


func (self *luaState) runLuaClosure() {
	for {
		inst := vm.Instruction(self.Fetch())
		inst.Execute(self)
		if inst.Opcode() == vm.OP_RETURN {
			break
		}
	}
}

以上是实现 lua 虚拟机的主要步骤，主体完成之后还可以对表达式做优化、增加标准库、支持更多寄生语言已经支持的特性等等。

参考

• 自己动手实现 lua
• yuin/gopher-lua