问题
对于习惯了C/C++的程序员来说，像lua/python这种动态语言总是有一些看起来新奇的特性。其中一个比较典型的例子就是闭包，尽管C++的lambda表达式隐约有了闭包的影子，但是相比较而言还是lua的闭包更强大：
lua的闭包可以捕捉任意存储类型(函数参数，全局i变量，局部变量)变量，并且更重要的是可以把这个闭包作为“first class”对象返回。如果用C++的视角来看，当函数调用返回后，闭包中引用的局部变量可能已经销毁或者内存已经被重用。直观的解决方法就是单独拷贝一份，如果C++的lambda都是通过value capture的，那返回lambda也没问题。
栈结构
状态机结构
一个lua虚拟机中栈相关的变量包括stack、top和stack_last三个，分别指向了栈底，栈顶和可用内存空间的结尾。结构本身和vector这类容器的内存挂历思路一样：预留/预分配一个足够大的空间，然后按需使用，避免频繁地内存申请和释放操作。
/*
** 'per thread' state
*/
struct lua_State {
CommonHeader;
unsigned short nci; /* number of items in 'ci' list */
lu_byte status;
StkId top; /* first free slot in the stack */
global_State *l_G;
CallInfo *ci; /* call info for current function */
const Instruction *oldpc; /* last pc traced */
StkId stack_last; /* last free slot in the stack */
StkId stack; /* stack base */
UpVal *openupval; /* list of open upvalues in this stack */
GCObject *gclist;
///...
};
StkId类型
这些字段的类型都是一个指针，但是指向的内容都足够小：不会大于一个指针的大小。这样配合类型信息，可以完整的存储整数、浮点数两种类型。
typedef TValue *StkId; /* index to stack elements */
/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/
/*
** Union of all Lua values
*/
typedef union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;
#define TValuefields Value value_; int tt_
typedef struct lua_TValue {
TValuefields;
} TValue;
使用场景
在解析字符串时，直接是通过递增指针(L->top--)，这意味着栈变量的使用是连续的，栈是一个数组结构(每个元素都有相同的结构和内存大小)。
/*
** creates a new string and anchors it in scanner's table so that
** it will not be collected until the end of the compilation
** (by that time it should be anchored somewhere)
*/
TString *luaX_newstring (LexState *ls, const char *str, size_t l) {
lua_State *L = ls->L;
TValue *o; /* entry for 'str' */
TString *ts = luaS_newlstr(L, str, l); /* create new string */
setsvalue2s(L, L->top++, ts); /* temporarily anchor it in stack */
o = luaH_set(L, ls->h, L->top - 1);
if (ttisnil(o)) { /* not in use yet? */
/* boolean value does not need GC barrier;
table has no metatable, so it does not need to invalidate cache */
setbvalue(o, 1); /* t[string] = true */
luaC_checkGC(L);
}
else { /* string already present */
ts = tsvalue(keyfromval(o)); /* re-use value previously stored */
}
L->top--; /* remove string from stack */
return ts;
}
官方例子
以lua官方关于closure的文档为例
function newCounter ()
local i = 0
return function () -- anonymous function
i = i + 1
return i
end
end
c1 = newCounter()
print(c1()) --> 1
print(c1()) --> 2
closure内部使用了局部变量i，当执行流从newCounter返回值后，对i的访问是否会像C++中的lambda引用栈变量一样引用到“脏数据”(注意：此时的变量i是一个整数，可以直接放入到栈上的一个TValue内存而不需要额外存储空间)。
实现问题
直观上考虑，应该是和C++的实现一样：发现有capture的时候自己拷贝一份。 但是还有另外两个问题：
- 局部变量 vs 全局变量
全局变量不需要/也不能拷贝，以为直观上看closure对于全局变量的访问应该是相同的。
- 深拷贝 vs 浅拷贝
如果栈变量是一个string，那么栈变量只是通过gc指向了TString结构。由于lua有自动垃圾回收机制，所以应该不需要深拷贝字符串内容。
lua实现
官方文档《The Implementation of Lua 5.0》的第五节“Functions and Closures”系统/准确的说明了lua的这部分实现。
When the variable goes out of scope, it migrates into a slot inside the upvalue itself (Figure 4, right). Because access is indirect through a pointer in the upvalue, this migration is transparent to any code that reads or writes the variable. Unlike its inner functions, the function that declares the variable accesses it as it accesses its own local variables: directly in the stack.
在closure生成的时候，的确是把stack中的对象拷贝一份过来。
一些细节
寻址方式
由于upvalue存储的物理位置不同，所以lua虚拟机也需要体现这种区别，就像386中栈操作使用单独的push/pop一样。在lua中访问栈变量，函数参数，常量使用的都是不同的指令模式。
从下面的反编译代码可以看到，对于upvalue的读写访问使用的是特殊的GETUPVAL/SETUPVAL指令。
tsecer@harry: cat -n luaclosure.lua
1 function newCounter ()
2 local i = 0
3 return function () -- anonymous function
4 i = i + 1
5 return i
6 end
7 end
8
9 c1 = newCounter()
10 print(c1())
11 print(c1())
12
tsecer@harry: luac -v
Lua 5.1.4 Copyright (C) 1994-2008 Lua.org, PUC-Rio
tsecer@harry: luac -l luaclosure.lua
main <luaclosure.lua:0,0> (14 instructions, 56 bytes at 0x15d7530)
0+ params, 2 slots, 0 upvalues, 0 locals, 3 constants, 1 function
1 [7] CLOSURE 0 0 ; 0x15d7710
2 [1] SETGLOBAL 0 -1 ; newCounter
3 [9] GETGLOBAL 0 -1 ; newCounter
4 [9] CALL 0 1 2
5 [9] SETGLOBAL 0 -2 ; c1
6 [10] GETGLOBAL 0 -3 ; print
7 [10] GETGLOBAL 1 -2 ; c1
8 [10] CALL 1 1 0
9 [10] CALL 0 0 1
10 [11] GETGLOBAL 0 -3 ; print
11 [11] GETGLOBAL 1 -2 ; c1
12 [11] CALL 1 1 0
13 [11] CALL 0 0 1
14 [11] RETURN 0 1
function <luaclosure.lua:1,7> (5 instructions, 20 bytes at 0x15d7710)
0 params, 2 slots, 0 upvalues, 1 local, 1 constant, 1 function
1 [2] LOADK 0 -1 ; 0
2 [6] CLOSURE 1 0 ; 0x15d78c0
3 [6] MOVE 0 0
4 [6] RETURN 1 2
5 [7] RETURN 0 1
function <luaclosure.lua:3,6> (6 instructions, 24 bytes at 0x15d78c0)
0 params, 2 slots, 1 upvalue, 0 locals, 1 constant, 0 functions
1 [4] GETUPVAL 0 0 ; i
2 [4] ADD 0 0 -1 ; - 1
3 [4] SETUPVAL 0 0 ; i
4 [5] GETUPVAL 0 0 ; i
5 [5] RETURN 0 2
6 [6] RETURN 0 1
tsecer@harry:
数据结构
在一个Closure结构中，和函数原型(Proto)同等级别的就有一个UpVal数组，也就是Closure = Proto + upvalue。我们甚至可以把Closure理解为一个功能比C++模板更强大的“函数模板”，C++的模板函数只接受全局指针和编译常量，而lua的闭包可以接受任意变量(例如栈变量)。
typedef struct LClosure {
ClosureHeader;
struct Proto *p;
UpVal *upvals[1]; /* list of upvalues */
} LClosure;
/*
** Upvalues for Lua closures
*/
struct UpVal {
TValue *v; /* points to stack or to its own value */
lu_mem refcount; /* reference counter */
union {
struct { /* (when open) */
UpVal *next; /* linked list */
int touched; /* mark to avoid cycles with dead threads */
} open;
TValue value; /* the value (when closed) */
} u;
};
upvalue的复制
在执行CLOSURE指令时触发pushclosure调用
vmcase(OP_CLOSURE) {
Proto *p = cl->p->p[GETARG_Bx(i)];
LClosure *ncl = getcached(p, cl->upvals, base); /* cached closure */
if (ncl == NULL) /* no match? */
pushclosure(L, p, cl->upvals, base, ra); /* create a new one */
else
setclLvalue(L, ra, ncl); /* push cashed closure */
checkGC(L, ra + 1);
vmbreak;
}
逐个upvalue调用luaF_findupval函数
/*
** create a new Lua closure, push it in the stack, and initialize
** its upvalues. Note that the closure is not cached if prototype is
** already black (which means that 'cache' was already cleared by the
** GC).
*/
static void pushclosure (lua_State *L, Proto *p, UpVal **encup, StkId base,
StkId ra) {
int nup = p->sizeupvalues;
Upvaldesc *uv = p->upvalues;
int i;
LClosure *ncl = luaF_newLclosure(L, nup);
ncl->p = p;
setclLvalue(L, ra, ncl); /* anchor new closure in stack */
for (i = 0; i < nup; i++) { /* fill in its upvalues */
if (uv[i].instack) /* upvalue refers to local variable? */
ncl->upvals[i] = luaF_findupval(L, base + uv[i].idx);
else /* get upvalue from enclosing function */
ncl->upvals[i] = encup[uv[i].idx];
ncl->upvals[i]->refcount++;
/* new closure is white, so we do not need a barrier here */
}
if (!isblack(p)) /* cache will not break GC invariant? */
p->cache = ncl; /* save it on cache for reuse */
}
在luaF_findupval函数中如果不存在则通过luaM_new创建一个新变量。
UpVal *luaF_findupval (lua_State *L, StkId level) {
UpVal **pp = &L->openupval;
UpVal *p;
UpVal *uv;
lua_assert(isintwups(L) || L->openupval == NULL);
while (*pp != NULL && (p = *pp)->v >= level) {
lua_assert(upisopen(p));
if (p->v == level) /* found a corresponding upvalue? */
return p; /* return it */
pp = &p->u.open.next;
}
/* not found: create a new upvalue */
uv = luaM_new(L, UpVal);
uv->refcount = 0;
uv->u.open.next = *pp; /* link it to list of open upvalues */
uv->u.open.touched = 1;
*pp = uv;
uv->v = level; /* current value lives in the stack */
if (!isintwups(L)) { /* thread not in list of threads with upvalues? */
L->twups = G(L)->twups; /* link it to the list */
G(L)->twups = L;
}
return uv;
}
非栈变量的处理
注意到pushclosure尝试拷贝upvalue的时候，会有一个额外的instack判断，非instack变量不会触发拷贝。这也就达到了closure中捕捉的全局变量只有一份的目的。
static int newupvalue (FuncState *fs, TString *name, expdesc *v) {
Proto *f = fs->f;
int oldsize = f->sizeupvalues;
checklimit(fs, fs->nups + 1, MAXUPVAL, "upvalues");
luaM_growvector(fs->ls->L, f->upvalues, fs->nups, f->sizeupvalues,
Upvaldesc, MAXUPVAL, "upvalues");
while (oldsize < f->sizeupvalues)
f->upvalues[oldsize++].name = NULL;
f->upvalues[fs->nups].instack = (v->k == VLOCAL);
f->upvalues[fs->nups].idx = cast_byte(v->u.info);
f->upvalues[fs->nups].name = name;
luaC_objbarrier(fs->ls->L, f, name);
return fs->nups++;
}
C++中函数返回lambda
如果分析gcc的lambda实现的话，可以发现gcc的内部实现和lua差不多：gcc是在内部创建了一个匿名的(编译器可见)struct，struct将捕捉的参数作为成员变量，并且生成一个函数调用的operator，这两个分别对应lua中typedef struct LClosure结构的
UpVal upvals[1]; / list of upvalues */
和
struct Proto *p;
从下面的测试代码可以看到，c++中捕捉的变量也是拷贝了自己的一份。
tsecer@harry: cat lambda.cpp
#include <stdio.h>
#include <string.h>
struct S
{
int a[10];
};
auto ret_lambda()
{
S s{1, 2, 3};
auto local = [s]()
{
printf("%d, %d\n", s.a[0], s.a[1]);
};
memset(&s, 0 , sizeof(s));
return local;
}
int main(int argc, const char *argv[])
{
ret_lambda()();
return 0;
}
tsecer@harry: g++ lambda.cpp
tsecer@harry: ./a.out
1, 2
tsecer@harry: