定义和调用

我们的解释器最开始只支持顺序执行，后来加入控制结构后支持条件跳转，并且block也有控制变量作用域的功能。而函数在解析、执行或作用域等方面都是更加独立的存在。为此，需要修改当前的语法分析和虚拟机执行的框架。

改造ParseProto

函数的定义是可以嵌套的，即可以在函数内部再次定义函数。如果把整个代码看做是主函数，那么我们当前的语法分析相当于只支持这一个函数。为了支持函数的嵌套定义，需要对语法分析进行改造。首先改造数据结构。

当前，语法分析过程的上下文结构体是ParseProto，同时这也是返回给虚拟机执行的结构体。定义如下：

  1. pub struct ParseProto<R: Read> {
  2.     pub constants: Vec<Value>,
  3.     pub byte_codes: Vec<ByteCode>,
  5.     sp: usize,
  6.     locals: Vec<String>,
  7.     break_blocks: Vec<Vec<usize>>,
  8.     continue_blocks: Vec<Vec<(usize, usize)>>,
  9.     gotos: Vec<GotoLabel>,
  10.     labels: Vec<GotoLabel>,
  11.     lex: Lex<R>,
  12. }

每个字段的具体含义之前已经详细介绍过，这里忽略。这里只按照函数的独立性来区分这些字段：

  • 最后的lex字段是贯穿整个代码解析的；
  • 其余所有字段都是函数内部的数据。

为了支持函数的嵌套定义，需要把全局部分（lex字段）和函数部分（其他字段）拆开。新定义函数解析的数据结构PerFuncProto_（因为我们最终不会采用这个方案，所以结构体名字最后加了_），包括原来的ParseProto中去掉lex后剩下的其他字段：

  1. struct PerFuncProto_ {
  2.     pub constants: Vec<Value>,
  3.     pub byte_codes: Vec<ByteCode>,
  4.     sp: usize,
  5.     ... // 省略更多字段
  6. }

为了支持函数的嵌套，就需要支持同时有多个函数解析体。最直观的思路是定义一个函数体列表：

  1. struct ParseProto<R: Read> {
  2.     funcs: Vec<PerFuncProto_>,  // 刚才定义的函数解析体PerFuncProto_的列表
  3.     lex: Lex<R>,  // 全局数据
  4. }

每次新嵌套一层函数，就向funcs字段中压入一个新成员；解析完函数后弹出。funcs的最后一个成员就代表当前函数。这样定义很直观，但是有个问题，访问当前函数的所有字段都很麻烦，比如要访问constants字段，就需要 self.funcs.last().unwrap().constants 读取或者 self.funcs.last_mut().unwrap().constants 写入。太不方便了，执行效率应该也受影响。

如果是C语言，那么这个问题很好解决：在ParseProto中再新增一个PerFuncProto_类型的指针成员，比如叫current，指向funcs的最后一个成员。每次压入或弹出函数体时，都更新这个指针。然后就可以直接使用这个指针来访问当前函数了，比如 self.current.constants 。这个做法很方便但是Rust认为这是不“安全”的，因为在Rust的语法层面无法保证这个指针的有效性。虽然对这个指针的更新只有两个地方，相对安全，但是既然用了Rust，就要按照Rust的规矩。

对于Rust而言，可行的解决方案是增加一个索引（而非指针），比如叫icurrent，指向funcs的最后一个成员。同样也是每次在压入或弹出函数体时，都更新这个索引。而在访问当前函数信息时就可以用 self.funcs[icurrent].constants 。虽然Rust语言允许这么做，但这其实只是上面指针方案的变种，仍然可能由于索引的错误更新导致bug。比如索引超过funcs长度则会panic，而如果小于预期则会出现更难调试的代码逻辑bug。另外在执行时，Rust的列表索引会跟列表长度做比较，也会稍微影响性能。

还有一个不那么直观但没有上述问题的方案：利用递归。在解析嵌套的函数时，最自然的方法就是递归调用解析函数的代码，那么每次调用都会有独立的栈（Rust的调用栈），于是可以每次调用时都创建一个函数解析体并用于解析当前Lua函数，在调用结束后就返回这个解析体供外层函数处理。这个方案中，解析过程中只能访问当前函数的信息，不能访问外层函数的信息，自然也就没有刚才说的访问当前函数信息不方便的问题了。比如访问constants依然是用self.constants，甚至无需修改现有代码。唯一要解决的是全局数据Lex，这个可以作为解析函数的参数一直传递下去。

这个方案中，无需定义新的数据结构，只需要把原来的ParseProto中的lex字段从Lex类型修改为&mut Lex即可。解析Lua函数的语法分析函数定义原来是ParseProto的方法，定义为：

  1. impl<'a, R: Read> ParseProto<'a, R> {
  2.     fn chunk(&mut self) {
  3.         ...
  4.     }

现在改为普通函数，定义为：

  1. fn chunk(lex: &mut Lex<impl Read>) -> ParseProto {
  2.     ...
  3. }

其中参数lex是全局数据，每次递归调用都直接传入下一层。返回值是在chunk()内创建的当前Lua函数的解析信息。

另外，chunk()函数内部调用block()函数解析代码，后者返回block的结束Token。之前chunk()函数只用来处理整个代码块，所以结束Token只可能是Token::Eos；而现在也可能被用来解析其他的内部函数，此时预期的结束Token就是Token::End。所以chunk()函数要新增一个参数，表示预期的结束Token。于是定义改成：

  1. fn chunk(lex: &mut Lex<impl Read>, end_token: Token) -> ParseProto {
  2.     ...
  3. }

新增FuncProto

刚才改造了ParseProto，修改了lex的类型。现在顺便再做个小的优化。ParseProto中前面两个pub修饰的字段同时也是返回给虚拟机执行使用的；后面的大部分字段只是语法分析时使用的，是内部数据，并不需要返回给虚拟机。可以把这两部分拆开，从而只返回给虚拟机需要的部分。为此，新增FuncProto数据结构：

  1. // 返回给虚拟机执行的信息
  2. pub struct FuncProto {
  3.     pub constants: Vec<Value>,
  4.     pub byte_codes: Vec<ByteCode>,
  5. }
  7. #[derive(Debug)]
  8. struct ParseProto<'a, R: Read> {
  9.     // 返回给虚拟机执行的信息
  10.     fp: FuncProto,
  12.     // 语法分析内部数据
  13.     sp: usize,
  14.     locals: Vec<String>,
  15.     break_blocks: Vec<Vec<usize>>,
  16.     continue_blocks: Vec<Vec<(usize, usize)>>,
  17.     gotos: Vec<GotoLabel>,
  18.     labels: Vec<GotoLabel>,
  19.     lex: Lex<R>,
  21.     // 全局数据
  22.     lex: &'a mut Lex<R>,
  23. }

于是chunk()函数的返回值就从ParseProto改为FuncProto。其完整定义如下：

  1. fn chunk(lex: &mut Lex<impl Read>, end_token: Token) -> FuncProto {
  2.     // 生成新的ParseProto，用以解析当前新的Lua函数
  3.     let mut proto = ParseProto::new(lex);
  5.     // 调用block()解析函数
  6.     assert_eq!(proto.block(), end_token);
  7.     if let Some(goto) = proto.gotos.first() {
  8.         panic!("goto {} no destination", &goto.name);
  9.     }
  11.     // 只返回FuncProto部分
  12.     proto.fp
  13. }

这样，在语法分析Lua内嵌函数时，只要递归调用chunk(self.lex, Token::End)即可。下面介绍具体的语法分析。

语法分析

上面介绍了解析Lua函数的大致流程，现在来看具体的语法分析。到现在语法分析应该已经轻车熟路了，按照BNF执行即可。Lua的函数定义有3个地方：

  1. 全局函数；
  2. 局部函数：
  3. 匿名函数，是表达式exp语句的一种情况。

其BNF规则分别如下：

  1. stat :=
  2.     `function` funcname funcbody | # 1.全局函数
  3.     `local` `function` Name funcbody | # 2.局部函数
  4.     # 省略其他情况 
  6. exp := functiondef | 省略其他情况
  7. functiondef := `function` funcbody # 3.匿名函数
  9. funcbody ::= ‘(’ [parlist] ‘)’ block end # 函数定义

由上述规则可见这3种定义的区别只是在开头，而最后都是归于funcbody。这里只介绍最简单的第2种情况，局部函数。

  1.     fn local_function(&mut self) {
  2.         self.lex.next(); // 跳过关键字`function`
  3.         let name = self.read_name(); // 函数名，或者称为局部变量名
  4.         println!("== function: {name}");
  6.         // 暂时不支持参数，跳过 `()`
  7.         self.lex.expect(Token::ParL);
  8.         self.lex.expect(Token::ParR);
  10.         // 调用chunk()解析函数
  11.         let proto = chunk(self.lex, Token::End);
  13.         // 把解析的结果FuncProto，放入常量表中
  14.         let i = self.add_const(Value::LuaFunction(Rc::new(proto)));
  15.         // 通过LoadConst字节码加载函数
  16.         self.fp.byte_codes.push(ByteCode::LoadConst(self.sp as u8, i as u16));
  18.         // 创建局部变量
  19.         self.locals.push(name);
  20.     }

解析过程很简单。需要说明的是，对chunk()函数返回的函数原型FuncProto的处理方法，是作为一个常量放到常量表中。可以对比字符串是由一系列字符序列组成的常量；而函数原型FuncProto就是由一系列常量表和字节码序列组成的常量。同样也是存在常量表中，同样也是用LoadConst字节码来加载。

为此，需要新增一种Value类型LuaFunction来代表Rust函数，并把原来代表Lua函数的类型从Function改为RustFunction：

  1. pub enum Value {
  2.     LongStr(Rc<Vec<u8>>),
  3.     LuaFunction(Rc<FuncProto>),
  4.     RustFunction(fn (&mut ExeState) -> i32),

LuaFunction关联的数据类型是Rc<FuncProto>，从这里也可以看到跟字符串常量的相似。

以上完成了“定义函数”的语法分析，跟函数相关的还有“调用函数”的语法分析。但是在“调用函数”的时候，Lua函数和Rust函数是同等对待的，Lua程序员在调用函数时甚至不知道这个函数是用什么实现的；由于之前已经完成了Rust函数print()调用的语法分析，所以这里无需特定为Lua函数的调用再做语法分析。

虚拟机执行

跟语法分析一样，我们之前的虚拟机执行部分也是只支持一层Lua函数。为了支持函数调用，最简单的办法就是递归调用虚拟机执行，即execute()函数。代码如下：

  1.     ByteCode::Call(func, _) => {
  2.         self.func_index = func as usize;
  3.         match &self.stack[self.func_index] {
  4.             Value::RustFunction(f) => { // 之前就支持的Rust函数
  5.                 f(self);
  6.             }
  7.             Value::LuaFunction(f) => { // 新增的Lua函数
  8.                 let f = f.clone();
  9.                 self.execute(&f); // 递归调用虚拟机！
  10.             }
  11.             f => panic!("invalid function: {f:?}"),
  12.         }
  13.     }

但是，需要对栈做特殊处理。语法分析时，每次解析新函数，栈指针（ParseProto结构中的sp字段）都是从0开始。因为在语法分析时，并不知道在虚拟机执行时栈的绝对起始地址。那么，在虚拟机执行的时候，在访问栈时，使用的字节码中的栈索引，需要加上当前函数的栈起始地址的偏移。比如对于如下Lua代码：

  1. local a, b = 1, 2
  2. local function foo()
  3.     local x, y = 1, 2
  4. end
  5. foo()

在语法分析foo()函数定义时，局部变量x和y的栈地址分别是0和1。在执行最后一行代码，调用foo()函数时，函数foo放在栈的绝对索引2处，此时局部变量x和y的绝对索引就是3和4。那么虚拟机执行的时候，就需要把相对地址0和1，转换为3和4。

  1.    绝对地址     相对地址
  2.         +-----+ <---主函数的base
  3.       0 |  a  | 0
  4.         +-----+
  5.       1 |  b  | 1
  6.         +-----+
  7.       2 | foo | 2
  8.         +-----+ <---foo()函数的base
  9.       3 |  x  | 0
  10.         +-----+
  11.       4 |  y  | 1
  12.         +-----+
  13.         |     |

之前在执行Rust函数print()时，为了让print()函数能读取到参数，所以在ExeState中设置了func_index成员，用来指向函数在栈上的地址。现在调用Lua函数，依然如此。只不过，这里把func_index改名为base，并指向函数的下一个地址。

  1.     ByteCode::Call(func, _) => {
  2.         self.base += func as usize + 1; // 设置函数在栈上的绝对地址
  3.         match &self.stack[self.base-1] {
  4.             Value::RustFunction(f) => {
  5.                 f(self);
  6.             }
  7.             Value::LuaFunction(f) => {
  8.                 let f = f.clone();
  9.                 self.execute(&f);
  10.             }
  11.             f => panic!("invalid function: {f:?}"),
  12.         }
  13.         self.base -= func as usize + 1; // 恢复
  14.     }

之前所有对栈的写操作，都是调用的set_stack()方法，现在需要加上self.base偏移：

  1.     fn set_stack(&mut self, dst: u8, v: Value) {
  2.         set_vec(&mut self.stack, self.base + dst as usize, v);  // 加上self.base
  3.     }

之前所有对栈的读操作都是直接self.stack[i]，现在也要提取一个新函数get_stack()，并在访问栈时加上self.base偏移：

  1.     fn get_stack(&self, dst: u8) -> &Value {
  2.         &self.stack[self.base + dst as usize]  // 加上self.base
  3.     }

至此，我们完成了Lua函数的最基本的定义和调用。有赖于递归的力量，代码改动并不大。但距离完整的函数功能，这只是一个起步。下一节增加参数和返回值的支持。