Upvalue

在介绍闭包前，本节先来介绍闭包的重要组成部分：Upvalue。

本节主要引入Upvalue的概念，并介绍语法分析和虚拟机执行阶段为支持Upvalue所需要做的改动。要实现Upvalue的完整特性是非常复杂的，因此为了聚焦在整体结构和流程的改动上，本节只支持最基本的Upvalue特性，而留到下一节再介绍Upvalue的逃逸（escape）和跨多层函数的复杂特性。

下面的示例代码展示了Upvalue最基本的场景：

local a = 1
local function foo()
    print(a)  -- `a`是什么类型的变量？局部变量，还是全局变量？
end

整个代码可以看做是一个顶层函数，其中定义了两个局部变量：a和函数foo。foo()函数内部的变量a引用的是函数外定义的局部变量，那a在函数内部算是什么变量？首先，它不是在foo()函数内部定义的，所以不是局部变量；其次，它是在外层函数中定义的局部变量，所以也不是全局变量。像这种引用外层函数的局部变量，在Lua中称为Upvalue。在Rust语言中也有闭包的概念，也可以引用外层函数中的局部变量，称之为“捕获环境”，应该跟Upvalue是一个概念。

Upvalue在Lua中非常常见。除了上述明显的情况外，还有就是调用同级的局部函数也是Upvalue，比如下面代码：

local function foo()
    print "hello, world"
end
local function bar()
    foo()  -- Upvalue
end

在bar()函数中调用的foo()函数就是Upvalue。另外，对局部函数的递归调用也是Upvalue。

介绍完Upvalue的概念后，下面Upvalue的语法解析流程。

变量解析流程

之前的解释器只支持局部变量和全局变量这两种变量类型，变量的解析流程如下：

  1. 在当前函数的局部变量中匹配，如果找到则是局部变量；
  2. 否则是全局变量。

现在要新增支持Upvalue类型，那么变量的解析流程就要增加一步，修改为：

  1. 在当前函数的局部变量中匹配，如果找到则是局部变量；
  2. 在上层函数的局部变量中匹配，如果找到则是Upvalue；（新增步骤）
  3. 否则是全局变量。

新增的第2步看上去简单，但是具体实现很复杂，而且这里的描述也不准确，这个留在下一节详细介绍。本节重点关注整体流程，即解析到Upvalue后要怎么处理。

类似于局部变量和全局变量，对于Upvalue也要新增一种ExpDesc：

enum ExpDesc {
    Local(usize),    // 局部变量或栈上临时变量
    Upvalue(usize),  // Upvalue
    Global(usize),   // 全局变量

复习一下，局部变量ExpDesc::Local的关联参数代表在栈上的索引，全局变量ExpDesc::Global的关联参数代表变量名在常量表中的索引。那Upvalue需要关联什么参数？用下面包含多个Upvalue的示例代码为例：

local a, b, c = 100, 200, 300
local function foo()
    print (c, b)
end

上述代码中，foo()函数中有两个Upvalue，c和b，分别对应上层函数中的局部变量的索引2和1（索引以0开始计数），那么很自然的，就可以用ExpDesc::Upvalue(2)和ExpDesc::Upvalue(1)来表示。这样在虚拟机执行时，也可以很方便的索引到上一层函数的栈上局部变量。简单而且自然。但是在下一节介绍到Upvalue的逃逸时，这个方案就不能满足要求了。不过简单起见，本节暂时先这么用。

语法分析上下文

上面变量解析流程中新增的第2步，要求能够访问外层函数的局部变量。在上一章解析函数时，利用递归来支持多层函数定义。这样不仅实现简单，而且还能提供一定程度的封装，即只能访问当前函数的信息。这本来是优点，但现在为了支持Upvalue，就需要访问外层函数的局部变量，那么这个封装就变成了需要克服的缺点了。程序都是在这样的不断增加的需求中变得越来越复杂和混乱。

之前递归解析多层函数时，有个贯穿始终的成员，即ParseProto中的lex: Lex<R>，在解析所有函数时都需要访问它。现在为了能访问外层函数的局部变量，也就需要一个类似的贯穿始终的成员，存储每一层函数的局部变量。为此，我们创建一个新的数据结构，包含原来的lex和新的局部变量列表：

struct ParseContext<R: Read> {
    all_locals: Vec<Vec<String>>, // 每一层函数的局部变量
    lex: Lex<R>,
}

其中的all_locals成员代表每一层函数的局部变量列表。每次解析新一层的函数时，向其中压入新成员；解析完毕后弹出。所以列表中最后一个成员就是当前函数的局部变量列表。

然后在ParseProto中，用ctx代替原来的lex，并且删掉原来的locals：

struct ParseProto<'a, R: Read> {
    // 删掉：locals: Vec<String>, 
    ctx: &'a mut ParseContext<R>, // 新增ctx，代替原来的lex
    ...

并且语法分析代码中所有用到locals字段的地方也都要修改为ctx.all_locals的最后一个成员，也就是当前函数的局部变量列表。这里省略具体代码。

至此，一共有3个语法分析相关的数据结构：

  • FuncProto，定义函数原型，是语法分析阶段的输出，也是虚拟机执行阶段的输入，所以所有字段都是pub的；
  • ParseProto，语法分析阶段内部使用的，当前函数的状态；
  • ParseContext，语法分析阶段内部使用的，所有函数层级都可以访问的全局状态。

在改造完ParseProto，有了访问外层函数的能力后，就可以解析Upvalue了。不过这里只是说有了解析的能力，而具体的解析流程还是要到下一节介绍。

字节码

在解析完Upvalue后，对于其处理，可以参考以前对全局变量的讨论，结论如下：

  • 读取，首先加载到栈上，转换为临时变量；
  • 赋值，只支持从局部/临时变量和常量赋值，对于其他类型表达式则先加载到栈上临时变量再赋值。

为此，对照全局变量，新增3个Upvalue相关字节码：

pub enum ByteCode {
    // global variable
    GetGlobal(u8, u8),
    SetGlobal(u8, u8),
    SetGlobalConst(u8, u8),

    // upvalue
    GetUpvalue(u8, u8),  // 加载Upvalue到栈上
    SetUpvalue(u8, u8),  // 从栈上赋值
    SetUpvalueConst(u8, u8),  // 从常量赋值

这3个新增字节码的生成，也完成可以参考全局变量。这里省略具体代码。

虚拟机执行

上面介绍了Upvalue的解析流程，已经对应的字节码，完成了语法分析阶段。剩下就是虚拟机执行阶段。

按照上面对Upvalue的处理方案，即ExpDesc::Upvalue的关联参数表示上层函数的局部变量索引，在虚拟机执行时，也会遇到跟语法分析相同的问题：当前函数要访问上层函数的局部变量。所以要完成虚拟机执行阶段，也要对目前的代码结构做较大的改动。

不过，上述Upvalue的处理方案只是本节的临时方案，在下一节中为了支持Upvalue的逃逸，会有完全不同的方案，也会有完全不同的虚拟机执行过程。所以为了避免无用功，这里就暂时不实现这个方案下的虚拟机执行了。有兴趣的小伙伴可以试着改一下。