Lua的类型实现 ? LonelyBoy

Lua的类型实现

作者 lonelyboy 在 25 五月 2012, 10:44 下午

Lua是一个轻量级的脚本语言,本人大爱之一,所以就拿她5.2的源码开刀了…

类型和GC是息息相关的,不过先无视掉GC,认识了类型的存储结构,再去解析GC.

因为Lua是完全使用C语言实现的,所以他通过union来实现多态,以及通过一个bitmark的tag来记录类型信息.

首先在lua.h中可以看到基础类型的tag定义,通过tag我们可以快速了解到Lua中一共有哪些类型.

/*** basic types*/#define LUA_TNONE		(-1)#define LUA_TNIL		0 //nil#define LUA_TBOOLEAN		1 //boolean#define LUA_TLIGHTUSERDATA	2 //lightusedata#define LUA_TNUMBER		3 //number#define LUA_TSTRING		4 //string#define LUA_TTABLE		5 //table#define LUA_TFUNCTION		6 //function#define LUA_TUSERDATA		7 //userdata#define LUA_TTHREAD		8 //thread#define LUA_NUMTAGS		9 //这个意思是说基础类型的tag有9个,在lobject里面还有额外的类型/* type for integer functions */typedef LUA_INTEGER lua_Integer;/* unsigned integer type */typedef LUA_UNSIGNED lua_Unsigned;

然后视线转移进lobject.h,这里有具体每种类型的定义,首先是更详细的tag定义,3个非值类型的tag,以及tag的结构(0-3记录类型值,4-5是留个具体类型的,6是来标记是否可回收).接下来是Func的的tag分为lua, lightC, CClosure三种.

/*** Extra tags for non-values*/#define LUA_TPROTO	LUA_NUMTAGS#define LUA_TUPVAL	(LUA_NUMTAGS+1)#define LUA_TDEADKEY	(LUA_NUMTAGS+2)/*** number of all possible tags (including LUA_TNONE but excluding DEADKEY)*/#define LUA_TOTALTAGS	(LUA_TUPVAL+2)/*** tags for Tagged Values have the following use of bits:** bits 0-3: actual tag (a LUA_T* value)** bits 4-5: variant bits** bit 6: whether value is collectable*//*** LUA_TFUNCTION variants:** 0 - Lua function** 1 - light C function** 2 - regular C function (closure)*//* Variant tags for functions */#define LUA_TLCL	(LUA_TFUNCTION | (0 << 4))  /* Lua closure */#define LUA_TLCF	(LUA_TFUNCTION | (1 << 4))  /* light C function */#define LUA_TCCL	(LUA_TFUNCTION | (2 << 4))  /* C closure *//* Bit mark for collectable types */#define BIT_ISCOLLECTABLE	(1 << 6)/* mark a tag as collectable */#define ctb(t)			((t) | BIT_ISCOLLECTABLE)

接下来是union Value的定义,GC可回收对象,轻量用户数据,bool,轻量C函数,数字(这也说明后面4个是不需要回收的,直接以值的形象存在,除了这4种类型,其他皆可被GC回收).接下来是TValue的定义,在Lua中真正使用的是TaggedValues,因为每个对象必须通过tag知道他的类型.

union Value {  GCObject *gc;    /* collectable objects */  void *p;         /* light userdata */  int b;           /* booleans */  lua_CFunction f; /* light C functions */  numfield         /* numbers */};/*** Tagged Values. This is the basic representation of values in Lua,** an actual value plus a tag with its type.*/#define TValuefields	Value value_; int tt_typedef struct lua_TValue TValue;struct lua_TValue {  TValuefields;};

然后就是各种GCObject类型的定义,但在此之前先介绍一下GCObject,每种GCObject都会有一个GCheader,他有3个值GCObject *next; lu_byte tt; lu_byte marked, 可以清晰的看出GC是一个单向链表,tt目测是类型信息,marked用于标记节点颜色.对于GCObject的具体定义并不在lobject.h中,而是在lstate.h里面…

/*** Union of all collectable objects*/typedef union GCObject GCObject;/*** Common Header for all collectable objects (in macro form, to be** included in other objects)*/#define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked/*** Common header in struct form*/typedef struct GCheader {  CommonHeader;} GCheader;/*** Union of all collectable objects*/union GCObject {  GCheader gch;  /* common header */  union TString ts;  union Udata u;  union Closure cl;  struct Table h;  struct Proto p;  struct UpVal uv;  struct lua_State th;  /* thread */};

GCObject中最简单的是TString和Udata,他们的结构也十分相似,都是将数据附于结构体之后.其中L_Umaxalign dummy;这个是用于数据对齐的,并没有实际意义,他定义在llimits.h中

/* type to ensure maximum alignment */#if !defined(LUAI_USER_ALIGNMENT_T)#define LUAI_USER_ALIGNMENT_T	union { double u; void *s; long l; }#endiftypedef LUAI_USER_ALIGNMENT_T L_Umaxalign;/*** Header for string value; string bytes follow the end of this structure*/typedef union TString {  L_Umaxalign dummy;  /* ensures maximum alignment for strings */  struct {    CommonHeader;    lu_byte reserved;    unsigned int hash;    size_t len;  /* number of characters in string */  } tsv;} TString;/* get the actual string (array of bytes) from a TString */#define getstr(ts)	cast(const char *, (ts) + 1)/* get the actual string (array of bytes) from a Lua value */#define svalue(o)       getstr(rawtsvalue(o))/*** Header for userdata; memory area follows the end of this structure*/typedef union Udata {  L_Umaxalign dummy;  /* ensures maximum alignment for `local' udata */  struct {    CommonHeader;    struct Table *metatable;    struct Table *env;    size_t len;  /* number of bytes */  } uv;} Udata;

按照源码的顺序,接下来是函数的实现…不过里面东西太多了…各种不明其意…需要具体看代码才能知道…大概可以了解到每个Closure会有一个Proto和一个UpVal表来保持所有函数内用到的外部引用…可以直接跳过去了…

/*** Description of an upvalue for function prototypes*/typedef struct Upvaldesc {  TString *name;  /* upvalue name (for debug information) */  lu_byte instack;  /* whether it is in stack */  lu_byte idx;  /* index of upvalue (in stack or in outer function's list) */} Upvaldesc;/*** Description of a local variable for function prototypes** (used for debug information)*/typedef struct LocVar {  TString *varname;  int startpc;  /* first point where variable is active */  int endpc;    /* first point where variable is dead */} LocVar;/*** Function Prototypes*/typedef struct Proto {  CommonHeader;  TValue *k;  /* constants used by the function */  Instruction *code;  struct Proto **p;  /* functions defined inside the function */  int *lineinfo;  /* map from opcodes to source lines (debug information) */  LocVar *locvars;  /* information about local variables (debug information) */  Upvaldesc *upvalues;  /* upvalue information */  union Closure *cache;  /* last created closure with this prototype */  TString  *source;  /* used for debug information */  int sizeupvalues;  /* size of 'upvalues' */  int sizek;  /* size of `k' */  int sizecode;  int sizelineinfo;  int sizep;  /* size of `p' */  int sizelocvars;  int linedefined;  int lastlinedefined;  GCObject *gclist;  lu_byte numparams;  /* number of fixed parameters */  lu_byte is_vararg;  lu_byte maxstacksize;  /* maximum stack used by this function */} Proto;/*** Lua Upvalues*/typedef struct UpVal {  CommonHeader;  TValue *v;  /* points to stack or to its own value */  union {    TValue value;  /* the value (when closed) */    struct {  /* double linked list (when open) */      struct UpVal *prev;      struct UpVal *next;    } l;  } u;} UpVal;/*** Closures*/#define ClosureHeader 	CommonHeader; lu_byte isC; lu_byte nupvalues; GCObject *gclisttypedef struct CClosure {  ClosureHeader;  lua_CFunction f;  TValue upvalue[1];  /* list of upvalues */} CClosure;typedef struct LClosure {  ClosureHeader;  struct Proto *p;  UpVal *upvals[1];  /* list of upvalues */} LClosure;typedef union Closure {  CClosure c;  LClosure l;} Closure;#define isLfunction(o)	ttisLclosure(o)#define getproto(o)	(clLvalue(o)->p)

最后是table,Lua里的table比较有意思,他是一种混合结构.一般的table类似C++中的map,key映射value,因为Lua中table经常被当作数组使用,所以他同时混合了数组结构,当table中存在较多的int值的key,将会把这些以int为key映射直接装入数组.在看传统的映射处理部分,从struct上来看,这部分映射并没有使用红黑树,而是简单的Node链表,嗯,应该是个hashMap.

/*** Tables*/typedef union TKey {  struct {    TValuefields;    struct Node *next;  /* for chaining */  } nk;  TValue tvk;} TKey;typedef struct Node {  TValue i_val;  TKey i_key;} Node;typedef struct Table {  CommonHeader;  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */  lu_byte lsizenode;  /* log2 of size of `node' array */  struct Table *metatable;  TValue *array;  /* array part */  Node *node;  Node *lastfree;  /* any free position is before this position */  GCObject *gclist;  int sizearray;  /* size of `array' array */} Table;

到此为止简单的观察了Lua的类型,欲知详情,敬请期待下文.