作者：罗日健
前面几篇文章已经说明了Lua里面很常用的几个数据结构，这次要分享的也是常用的数据结构之一 – 函数的结构。函数在Lua里也是一种变量，但是它却很特殊，能存储执行语句和被执行，本章主要描述Lua是怎么实现这种函数的。
在脚本世界里，相信闭包这个词大家也不陌生，闭包是由函数与其相关引用环境组成的实体。可能有点抽象，下面详细说明：
一、 闭包的组成
闭包主要由以下2个元素组成：
- 函数原型：上图意在表明是一段可执行代码。在Lua中可以是lua_CFunction，也可以是lua自身的虚拟机指令。
- 上下文环境：在Lua里主要是Upvalues和env，下面会有说明Upvalues和env。 在Lua里，我们也从闭包开始，逐步看出整个结构模型，下面是Closure的数据结构：(lobject.h 291-312)
不难发现，Lua的闭包分成2类，一类是CClosure，即luaC函数的闭包。另一类是LClosure，是Lua里面原生的函数的闭包。下面先讨论2者都有相同部分ClosureHeader：
- CommonHeader：和与TValue中的GCHeader能对应起来的部分
- isC：是否CClosure
- nupvalues：外部对象个数
- gclist：用于GC销毁，超出本章话题，在GC章节将详细说明
- env：函数的运行环境，下面会有补充说明
对于CClosure数据结构：
- lua_CFunction f：函数指针，指向自定义的C函数
- TValue upvalue[1]：C的闭包中，用户绑定的任意数量个upvalue
对于LClosure数据结构：
- Proto *p：Lua的函数原型，在下面会有详细说明
- UpVal *upvals：Lua的函数upvalue，这里的类型是UpVal，这个数据结构下面会详细说明，这里之所以不直接用TValue是因为具体实现需要一些额外数据。
二、 闭包的UpVal实现
究竟什么是UpVal呢？先来看看代码：
分析一下上面这段代码，最终testB的值显然是3+5+10=18。当调用testA(5)的时候，其实是在调用FuncB(5)，但是这个FuncB知道a = 3，这个是由FuncA调用时，记录到FuncB的外部变量，我们把a和c称为FuncB的upvalue。那么Lua是如何实现upvalue的呢？ 以上面这段代码为例，从虚拟机的角度去分析实现流程：
1) FuncA(3)执行流程
- 把3这个常量放到栈顶，执行FuncA
虚拟机操作：（帮助理解，与真实值有差别）
LOADK top 3 //把3这个常量放到栈顶 CALL top FuncA nresults //调用对应的FuncA函数
- 虚拟机的pc已经在FuncA里面了，FuncA中的局部变量都是放到栈中的，所以第一句loacl c = 10是把10放到栈顶（这里假设先放到栈顶简化一些复杂细节问题，下同）
虚拟机操作：
LOADK top 10 //local c = 10
- 遇到Function FuncB这个语句，会生成FuncB的闭包，这个过程同时会绑定upval到这个闭包上，但这是值还在栈上，upval只是个指针。
上面生成一个闭包之后，因为在Lua里，函数也是一个变量，上面的语句等价于local FuncB = function() … end，所以也会生成一个临时的FuncB到栈顶。
虚拟机操作：
- 最后return FuncB，就会把这个闭包关闭并返回出去，同时会把所有的upval进行unlink操作，让upval本身保存值。
虚拟机操作：
2) FuncB的执行过程
到了FuncB执行的时候，参数b=5已经放到栈顶，然后执行FuncB。语句比较简单和容易理解，return a+b+c 虚拟机操作如下：
到这里UpVal的创建和使用也在上面给出事例说明，总结一下UpVal的实现：
- UpVal是在函数闭包生成的时候（运行到function时）绑定的。
- UpVal在闭包还没关闭前（即函数返回前），是对栈的引用，这样做的目的是可以在函数里修改对应的值从而修改UpVal的值，比如：
lua code:
- 闭包关闭后（即函数退出后），UpVal不再是指针，而是值。 知道UpVal的原理后，就只需要简要叙述一下UpVal的数据结构：（lobject.h 274 – 284）
- CommHeader： UpVal也是可回收的类型，一般有的CommHeader也会有
- TValue* v：当函数打开时是指向对应stack位置值，当关闭后则指向自己
- TValue value：函数关闭后保存的值
- UpVal* prev、UpVal* next：用于GC，全局绑定的一条UpVal回收链表
三、 函数原型
之前说的，函数原型是表明一段可执行的代码或者操作指令。在绑定到Lua空间的C函数，函数原型就是lua_CFunction的一个函数指针，指向用户绑定的C函数。下面描述一下Lua中的原生函数的函数原型，即Proto数据结构（lobject.h 231-253）：
引用内容：
- CommonHeader：Proto也是需要回收的对象，也会有与GCHeader对应的CommonHeader
- TValue* k：函数使用的常量数组，比如local d = 10，则会有一个10的数值常量
- Instruction *code：虚拟机指令码数组
- Proto **p：函数里定义的函数的函数原型，比如funcA里定义了funcB，在funcA的5. Proto中，这个指针的[0]会指向funcB的Proto
- int *lineinfo：主要用于调试，每个操作码所对应的行号
- LocVar *locvars：主要用于调试，记录每个本地变量的名称和作用范围
- TString **upvalues：一来用于调试，二来用于给API使用，记录所有upvalues的名称
- TString *source：用于调试，函数来源，如c:\t1.lua@ main
- sizeupvalues： upvalues名称的数组长度
- sizek：常量数组长度
- sizecode：code数组长度
- sizelineinfo：lineinfo数组长度
- sizep：p数组长度
- sizelocvars：locvars数组长度
- linedefined：函数定义起始行号，即function语句行号
- lastlinedefined：函数结束行号，即end语句行号
- gclist：用于回收
- nups：upvalue的个数，其实在Closure里也有nupvalues，这里我也不太清楚为什么要弄两个，nups是语法分析时会生成的，而nupvalues是动态计算的。
- numparams：参数个数
- is_vararg：是否参数是”…”（可变参数传递）
- maxstacksize：函数所使用的stacksize
Proto的所有参数都是在语法分析和中间代码生成时获取的，相当于编译出来的汇编码一样是不会变的，动态性是在Closure中体现的。
四、 闭包运行环境
在前面说到的闭包数据结构中，有一个成员env，是一个Table*指针，用于指向当前闭包运行环境的Table。
什么是闭包运行环境呢？以下面代码举例：
上面代码中的d = 20，其实就是在环境变量中取env[“d”]，所以env一定是个table，而当定义了本地变量之后，之后的所有变量都对从本地变量中操作。
五、 函数调用信息
函数调用相当于一个状态信息，每次函数调用都会生成一个状态，比如递归调用，则会有一个栈去记录每个函数调用状态信息，比如说下面这段没有意义的代码：
那么每次调用将会生成一个调用状态信息，上面代码会无限生成下去：
究竟一个CallInfo要记录哪些状态信息呢？下面来看看CallInfo的数据结构：
- Instruction *savedpc：如果这个调用被中断，则用于记录当前闭包执行到的pc位置
- nresults：返回值个数，-1为任意返回个数
- tailcalls：用于调试，记录尾调用次数信息，关于尾调用下面会有详细解释
- base、func、top：如下：
六、 函数调用的栈操作
上面描述的CallInfo信息，具体整个流程是怎么走的，结合下面代码详细地叙述整个调用过程，栈是怎么变化的：
假设现在走到了funcA(30, 40)这个语句，在执行前已经存在了global这个闭包和funcA这个闭包，在调用global这个闭包时，已经生成了一个global的CallInfo。
1） 函数调用的栈操作：（OP_CALL lvm.c 582-601）
- global的CallInfo信息记录，并把funcA放到栈顶
当前虚拟机的pc指针，指向global函数原型中的CALL指令，这时global的CallInfo的savedpc就会保存当前pc。然后会把要执行的funcA的闭包放到栈顶。 – 参数分别放到栈顶（从左到右分别进栈），生成funcA的CallInfo，并把完成对应CallInfo栈操作
- 设置虚拟机pc到funcA闭包第一条虚拟机Instruction，并继续执行虚拟机
2） 函数返回的栈操作：（OP_RETURN lvm.c 635-648）
- 记录第一个返回值的位置到firstResult，把栈中的funcA位置设置为base和top
- 把返回值根据nresult参数重新push到栈
- 从全局CallInfo栈弹出funcA，并还原虚拟机pc到global的savedpc和栈信息
- 继续执行虚拟机
七、 尾调用（TAILCALL）
尾调用是一种对函数解释的优化方法，对于上面代码，改造成下面代码后，则不会出现stack overflow：
上面的Recursion方法不会出现stack overflow错误，也能顺利算出Recursion(20000) = 200010000。尾调用的使用方法十分简单，就是在return后直接调用函数，不能有其它操作，这样的写法即会进入尾调用方式。
那究竟lua是如何实现这种尾调用优化的呢？尾调用是在编译时分析出来的，有独立的操作码OP_TAILCALL，在虚拟机中的执行代码在lvm.c 603-634，具体原理如下：
1）首先像普通调用一样，准备调用Recursion函数
2）关闭Recursion1的调用状态，把Recursion2的对应栈数据下移，然后重新执行
本质优化思想：先关闭前一个函数，销毁CallInfo，再调用新的CallInfo，这样就会避免全局CallInfo栈溢出。
八、 总结
本文讨论了闭包、UpVal、函数原型、环境、栈操作、尾调用等相关知识，基本上把大部分的知识点和细节也囊括了，另外还有2大块知识：函数原型的生成和闭包GC可能迟些再分享。
