データ構造
値を表すデータ構造
// lua.h #define LUA_TNIL 0 #define LUA_TBOOLEAN 1 #define LUA_TLIGHTUSERDATA 2 #define LUA_TNUMBER 3 #define LUA_TSTRING 4 #define LUA_TTABLE 5 #define LUA_TFUNCTION 6 #define LUA_TUSERDATA 7 #define LUA_TTHREAD 8 // lobject.h typedef union { GCObject *gc; void *p; lua_Number n; int b; } Value; ... #define TValuefields Value value; int tt typedef struct lua_TValue { TValuefields; } TValue;
- GC管理されるオブジェクト(文字列やテーブル、関数等)
- GC管理されないユーザー定義のデータ
- 数値(普通はdouble。lua_Numberのtypedefを変えてlong等で使うカスタマイズも可能)
- Bool値
の4通りの場合があって、タグ .tt で場合を分けています。
ANSI完全互換としたいので「ポインタの下位ビットが通常0なのを利用してタグを埋め込み」のテクニックは使っていないと論文に書いてありました。こうすると標準的な環境で sizeof(TValue) が 12 と大きめになってコピーのコストが無視できなくなるので、TValueのコピー回数が増えがちなスタックマシンではなくレジスタマシンで実装したそうです。
TValue の値の読み取り・設定は
#define ttype(o) ((o)->tt) #define nvalue(o) check_exp(ttisnumber(o), (o)->value.n)
や
#define setnvalue(obj,x) \ { TValue *i_o=(obj); i_o->value.n=(x); i_o->tt=LUA_TNUMBER; }
のようなマクロを通してやるみたい。*valueとset*value。
GCObject *gc の指す先のデータ型は・・・文字列やテーブルは普通なので飛ばして、関数オブジェクトの表現を見てみます。
// lobject.h #define ClosureHeader \ CommonHeader; lu_byte isC; lu_byte nupvalues; GCObject *gclist; \ struct Table *env typedef struct CClosure { ClosureHeader; lua_CFunction f; TValue upvalue[1]; } CClosure; typedef struct LClosure { ClosureHeader; struct Proto *p; UpVal *upvals[1]; } LClosure; typedef union Closure { CClosure c; LClosure l; } Closure;
CClosureがCで実装された関数に何か値を束縛したもの、かな?LClosureがLuaで書いた関数でできたクロージャで、共通ヘッダと、Proto(関数プロトタイプ)と、UpValue、という3つの部分からできています。Protoが要するに関数のソースコードをコンパイルしたもので、UpValueは、その関数が参照してる外部スコープの変数がある場合、それを扱う仕組みだそうな。
function addFunc(x) return function(y) return x+y end end f = addFunc(3) print( f(4) ) -- 7 print( f(5) ) -- 8
と書くと、f には "function(y) return x+y end" というコードを表す Proto オブジェクトと、3の入ってる変数xを表すUpValueを格納したLClosureオブジェクトが入ります。
このUpValueっていうの、LuaVMでクロージャをシンプルに実装するために導入した概念だそうです。そのうち深く踏み込んで読んでみます。
// lobject.h typedef struct Proto { CommonHeader; TValue *k; /* constants used by the function */ Instruction *code; struct Proto **p; /* functions defined inside the function */ ...
Protoの定義(の最初の方)はこんなんでした。関数内で使われる定数リテラルの配列と、VMの命令列と、関数内関数の配列と。
仮想マシンのデータ構造
まず仮想マシン全体を表すglobal_State構造体があって・・・
// lstate.h typedef struct global_State { ... } global_State;
中身はほとんどGCの管理情報でした。これとは別に、それぞれのスレッド(コルーチン)を表す lua_State 構造体があります。こっちがメインです。
// lobject.h typedef TValue *StkId; /* index to stack elements */ // lstate.h struct lua_State { CommonHeader; lu_byte status; StkId top; /* first free slot in the stack */ StkId base; /* base of current function */ global_State *l_G; CallInfo *ci; /* call info for current function */ const Instruction *savedpc; /* `savedpc' of current function */ StkId stack_last; /* last free slot in the stack */ StkId stack; /* stack base */ CallInfo *end_ci; /* points after end of ci array*/ CallInfo *base_ci; /* array of CallInfo's */ int stacksize; int size_ci; /* size of array `base_ci' */ unsigned short nCcalls; /* number of nested C calls */ unsigned short baseCcalls; /* nested C calls when resuming coroutine */ lu_byte hookmask; lu_byte allowhook; int basehookcount; int hookcount; lua_Hook hook; TValue l_gt; /* table of globals */ TValue env; /* temporary place for environments */ GCObject *openupval; /* list of open upvalues in this stack */ GCObject *gclist; struct lua_longjmp *errorJmp; /* current error recover point */ ptrdiff_t errfunc; /* current error handling function (stack index) */ };
ちょっと長いですが、重要そうな部分をピックアップすると・・・
StkId top; /* first free slot in the stack */ StkId base; /* base of current function */ StkId stack_last; /* last free slot in the stack */ StkId stack; /* stack base */
まずスタック情報。StkIdはTValue*の別名なので、スタックはTValueの配列ということになります。レジスタマシンとはいえ、関数呼び出しの際の引数や返値の管理にはスタックを使用します。
というより、そもそも、現在のLuaVM実装での「レジスタ」は、実際にはこのスタックを指しているようです。
// lvm.c / 命令iのオペランドAで指定されたレジスタにアクセスするマクロ #define RA(i) (base+GETARG_A(i))
1番レジスタ==base+1、2番レジスタ==base+2、・・・となってます。なので、仮想マシンの「マシン」自体はスタックマシンとあまり変わりはなくて、大きく違うのは命令体系、と理解しました。演算の対象をスタック先頭に暗黙に限定するのではなくて、スタック内のインデックスで明示指定するのがLuaのVMということのようです。
他に重要そうなフィールドは・・・
CallInfo *ci; /* call info for current function */ CallInfo *end_ci; /* points after end of ci array*/ CallInfo *base_ci; /* array of CallInfo's */
ciは現在の呼び出し履歴を、これもスタック状に管理しています。CallInfoの定義は以下の通り。
// lstate.h typedef struct CallInfo { StkId base; /* base for this function */ StkId func; /* function index in the stack */ StkId top; /* top for this function */ const Instruction *savedpc; int nresults; /* expected number of results from this function */ int tailcalls; /* number of tail calls lost under this entry */ } CallInfo;
多分returnするときにはスタックのbaseやtopを復元して、savedpcを戻すんだと思います。
他には
TValue l_gt; /* table of globals */
グローバル関数/変数のテーブルがlua_Stateにありました。そんなとこでしょうか。
起動の流れ
〜mainからluaV_executeまで〜
ということで、次に、luaインタプリタの起動から、VMのメインループにたどりつくまでの流れを読みます。Luaはアプリケーションへの組み込みを考えてしっかり内部もAPI化されているので、始めて読む身には逆に中身が入り組んでいてちょっと大変でした(><)。それはともかく、mainです。mainのお仕事は、2つ関数を呼ぶことです。
// lua.c int main (int argc, char **argv) { ...略... lua_State *L = lua_open(); /* create state */ ...略... status = lua_cpcall(L, &pmain, &s); ...略... }
lua_open は luaL_newstate への #define で、ここで、global_State と lua_State を新規に作って返します。新しいVMです。以下このVMで作業します。
lua_cpcallというのは(たぶん)Luaの枠組みでCの関数を呼び出す時の汎用の仕組みで、コルーチンを使ってる時などに重要になってくるのだと思いますが、ひとまずその辺りは置いておきます。あとで読みます。やることは要するに、pmain という関数の呼び出しです。
pmainも、おおざっぱに見ると、2つの関数を呼ぶだけの簡単なお仕事です。
// lua.c static int pmain (lua_State *L) { ...略... luaL_openlibs(L); /* open libraries */ ...略... if (script) s->status = handle_script(L, argv, script); }
luaL_openlibsは標準ライブラリの関数をグローバルテーブルに登録します。詳細はスキップ。引数の解析(これも詳細はスキップ)で、スクリプトファイルが指定されていると変数scriptに名前が入って、handle_script関数に渡されます。スクリプトファイルが指定されてない場合は対話シェルが始まりますが、そっちもとりあえずスキップ。一つのファイルを実行する場合に絞っていきましょう。
static int handle_script (lua_State *L, char **argv, int n) { ...略... status = luaL_loadfile(L, fname); lua_insert(L, -(narg+1)); if (status == 0) status = docall(L, narg, 0); ...略... }
handle_scriptは、luaL_loadfileでファイルをロードして、トップレベルのスクリプトをコンパイルした関数オブジェクトをスタックに積みます。それを、docallで呼び出すと、いよいよ実行スタート!
そのまえに、luaL_loadfileの方も見ておかないとですね。怒濤のforwardingがはじまります。
// lauxlib.c LUALIB_API int luaL_loadfile (lua_State *L, const char *filename) { ...略... status = lua_load(L, getF, &lf, lua_tostring(L, -1)); ...略... }
lua_loadへ
// lapi.c LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data, const char *chunkname) { ...略... status = luaD_protectedparser(L, &z, chunkname); ...略... }
luaD_protectedparserへ
int luaD_protectedparser (lua_State *L, ZIO *z, const char *name) { ...略... status = luaD_pcall(L, f_parser, &p, savestack(L, L->top), L->errfunc); ...略... }
f_parserへ
// ldo.c static void f_parser (lua_State *L, void *ud) { ...略... tf = ((c == LUA_SIGNATURE[0]) ? luaU_undump : luaY_parser)(L, p->z, &p->buff, p->name); cl = luaF_newLclosure(L, tf->nups, hvalue(gt(L))); cl->l.p = tf; for (i = 0; i < tf->nups; i++) /* initialize eventual upvalues */ cl->l.upvals[i] = luaF_newupval(L); setclvalue(L, L->top, cl); incr_top(L); }
ここです。スクリプトがprecompile済みのバイナリだった場合、luaU_undumpでロードします。そうでなかった場合は、luaY_parserで構文解析&VMの機械語へとコンパイルします。どちらの関数もProtoオブジェクトを返すので、それをClosureオブジェクトにして、スタック先頭 L->top の TValue に setclvalue でセットします。incr_top(L) でスタックを一つ進めて、実行準備完了です。
一方、docall側は・・・
static int docall (lua_State *L, int narg, int clear) { ...略... status = lua_pcall(L, narg, (clear ? 0 : LUA_MULTRET), base); ...略... }
lua_pcallへ。スタックに積まれた引数と関数オブジェクトを適用する処理です。
// lapi.c LUA_API int lua_pcall (lua_State *L, int nargs, int nresults, int errfunc) { ...略... status = luaD_pcall(L, f_call, &c, savestack(L, c.func), func); ...略... }
f_callへ
// lapi.c static void f_call (lua_State *L, void *ud) { struct CallS *c = cast(struct CallS *, ud); luaD_call(L, c->func, c->nresults); }
luaD_callへ
// ldo.h void luaD_call (lua_State *L, StkId func, int nResults) { ...略... if (luaD_precall(L, func, nResults) == PCRLUA) /* is a Lua function? */ luaV_execute(L, 1); /* call it */ ...略... }
luaD_precallはCの関数だった場合はそれを呼び出し、Luaの関数だった場合は何もせずPCRLUAを返すようです。今回は必ずトップレベルのスクリプトをコンパイルしたコードが入っているはずで、絶対Luaの関数なので、luaV_executeに行きます。
// lvm.c void luaV_execute (lua_State *L, int nexeccalls) { ...略... /* main loop of interpreter */ for (;;) { ...略... } ...略... }
到着!!!
到着しました。次回は、このluaV_execute関数を調べていきます。よろしくお願いします。
おまけ:LuLu (1)
読んだコードの確認として、"LuaVM on Lua" 略して "LuLu" を作ってみようと思います。
Luaの字句解析や構文解析から入るのは大変そうなので、まずは、プリコンパイル済みのコードを読み込んで実行するVMを作ります。読み込み分は、lundump.c/lundump.h の luaU_undump関数を参考に実装します。コンパイルはluacコマンドでできます。
luac.outの構造
luacの出力をロードするコードのツリーはこんなんでした。
- luaU_undump
- LoadHeader (12バイトのヘッダ情報)
- LoadFunction (トップレベルのスクリプト)
- LoadString (ソースコード名)
- LoadInt (開始行番号)
- LoadInt (終了行番号)
- LoadByte (UpValueの数)
- LoadByte (引数の数)
- LoadByte (可変長引数かどうか?)
- LoadByte (使用するスタックサイズ)
- LoadCode (命令列)
- n = LoadSizeT (命令の個数)
- n個のInstruction
- LoadConstants (定数表)
- n = LoadInt (定数の個数)
- n個のNil/Boolean/Number/String
- m = LoadInt (関数内関数の個数)
- m個のLoadFunction
- LoadDebug (デバッグ情報)
- 色々(詳細略)
あとはこれをそのままLuaに移植するだけです。とりあえず、TValue はそのままLuaの値で表現することにしました。(Functionについては後で考えなおすかも。)手抜きなのでsizeof(int)==sizeof(size_t)==4、sizeof(lua_Number==double)==8、リトルエンディアン前提です。
→ 今のソースコード
実は10行以上のLuaのコード書くのこれが始めてです。変なことしてたらすみません。ビット演算が無いみたいだったので無駄に苦労してます。もっとちゃんとした方法あるのかな・・・。