ひとり勉強会

ひとり楽しく勉強会

データ構造

LUA

値を表すデータ構造

// 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;

RubyでいうVALUE型みたいなのです。大きく分けて

  • GC管理されるオブジェクト（文字列やテーブル、関数等）
  • GC管理されないユーザー定義のデータ
  • 数値（普通はdouble。lua_Numberのtypedefを変えてlong等で使うカスタマイズも可能）
  • Bool値

の４通りの場合があって、タグ .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、という３つの部分からできています。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にありました。そんなとこでしょうか。