Lua數據結構 — 閉包（四）

前麵幾篇文章已經說明了Lua裏麵很常用的幾個數據結構，這次要分享的也是常用的數據結構之一 – 函數的結構。函數在Lua裏也是一種變量，但是它卻很特殊，能存儲執行語句和被執行，本章主要描述Lua是怎麼實現這種函數的。

在腳本世界裏，相信閉包這個詞大家也不陌生，閉包是由函數與其相關引用環境組成的實體。可能有點抽象，下麵詳細說明：

一、 閉包的組成

閉包主要由以下2個元素組成：

1. 函數原型：上圖意在表明是一段可執行代碼。在Lua中可以是lua_CFunction，也可以是lua自身的虛擬機指令。
2. 上下文環境：在Lua裏主要是Upvalues和env，下麵會有說明Upvalues和env。 在Lua裏，我們也從閉包開始，逐步看出整個結構模型，下麵是Closure的數據結構：(lobject.h 291-312)

不難發現，Lua的閉包分成2類，一類是CClosure，即luaC函數的閉包。另一類是LClosure，是Lua裏麵原生的函數的閉包。下麵先討論2者都有相同部分ClosureHeader：

1. CommonHeader：和與TValue中的GCHeader能對應起來的部分
2. isC：是否CClosure
3. nupvalues：外部對象個數
4. gclist：用於GC銷毀，超出本章話題，在GC章節將詳細說明
5. env：函數的運行環境，下麵會有補充說明

對於CClosure數據結構：

1. lua_CFunction f：函數指針，指向自定義的C函數
2. TValue upvalue[1]：C的閉包中，用戶綁定的任意數量個upvalue

對於LClosure數據結構：

1. Proto *p：Lua的函數原型，在下麵會有詳細說明
2. 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）

1. CommHeader： UpVal也是可回收的類型，一般有的CommHeader也會有
2. TValue* v：當函數打開時是指向對應stack位置值，當關閉後則指向自己
3. TValue value：函數關閉後保存的值
4. UpVal* prev、UpVal* next：用於GC，全局綁定的一條UpVal回收鏈表

三、 函數原型

之前說的，函數原型是表明一段可執行的代碼或者操作指令。在綁定到Lua空間的C函數，函數原型就是lua_CFunction的一個函數指針，指向用戶綁定的C函數。下麵描述一下Lua中的原生函數的函數原型，即Proto數據結構（lobject.h 231-253）：

引用內容：

1. CommonHeader：Proto也是需要回收的對象，也會有與GCHeader對應的CommonHeader
2. TValue* k：函數使用的常量數組，比如local d = 10，則會有一個10的數值常量
3. Instruction *code：虛擬機指令碼數組
4. Proto **p：函數裏定義的函數的函數原型，比如funcA裏定義了funcB，在funcA的5. Proto中，這個指針的[0]會指向funcB的Proto
5. int *lineinfo：主要用於調試，每個操作碼所對應的行號
6. LocVar *locvars：主要用於調試，記錄每個本地變量的名稱和作用範圍
7. TString **upvalues：一來用於調試，二來用於給API使用，記錄所有upvalues的名稱
8. TString *source：用於調試，函數來源，如c:\t1.lua@ main
9. sizeupvalues： upvalues名稱的數組長度
10. sizek：常量數組長度
11. sizecode：code數組長度
12. sizelineinfo：lineinfo數組長度
13. sizep：p數組長度
14. sizelocvars：locvars數組長度
15. linedefined：函數定義起始行號，即function語句行號
16. lastlinedefined：函數結束行號，即end語句行號
17. gclist：用於回收
18. nups：upvalue的個數，其實在Closure裏也有nupvalues，這裏我也不太清楚為什麼要弄兩個，nups是語法分析時會生成的，而nupvalues是動態計算的。
19. numparams：參數個數
20. is_vararg：是否參數是”…”（可變參數傳遞）
21. maxstacksize：函數所使用的stacksize

Proto的所有參數都是在語法分析和中間代碼生成時獲取的，相當於編譯出來的匯編碼一樣是不會變的，動態性是在Closure中體現的。

四、 閉包運行環境

在前麵說到的閉包數據結構中，有一個成員env，是一個Table*指針，用於指向當前閉包運行環境的Table。

什麼是閉包運行環境呢？以下麵代碼舉例：

上麵代碼中的d = 20，其實就是在環境變量中取env[“d”]，所以env一定是個table，而當定義了本地變量之後，之後的所有變量都對從本地變量中操作。

五、 函數調用信息

函數調用相當於一個狀態信息，每次函數調用都會生成一個狀態，比如遞歸調用，則會有一個棧去記錄每個函數調用狀態信息，比如說下麵這段沒有意義的代碼：

那麼每次調用將會生成一個調用狀態信息，上麵代碼會無限生成下去：

究竟一個CallInfo要記錄哪些狀態信息呢？下麵來看看CallInfo的數據結構：

1. Instruction *savedpc：如果這個調用被中斷，則用於記錄當前閉包執行到的pc位置
2. nresults：返回值個數，-1為任意返回個數
3. tailcalls：用於調試，記錄尾調用次數信息，關於尾調用下麵會有詳細解釋
4. 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可能遲些再分享。