Lua 5.3 源码分析(一)类型系统
数据类型
/*
** basic types
*/
#define LUA_TNONE (-1)
#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
#define LUA_NUMTAGS 9
子类型
/*
** 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 */
/* Variant tags for strings */
#define LUA_TSHRSTR (LUA_TSTRING | (0 << 4)) /* short strings */
#define LUA_TLNGSTR (LUA_TSTRING | (1 << 4)) /* long strings */
/* Variant tags for numbers */
#define LUA_TNUMFLT (LUA_TNUMBER | (0 << 4)) /* float numbers */
#define LUA_TNUMINT (LUA_TNUMBER | (1 << 4)) /* integer numbers */
/* Bit mark for collectable types */
#define BIT_ISCOLLECTABLE (1 << 6)
/* mark a tag as collectable */
#define ctb(t) ((t) | BIT_ISCOLLECTABLE)
其中
1. NUMBER 类型的子类型: integer 与 float ;
2. FUNCTION 类型的子类型: Lua closure 、 light C function 、C closure
3. STRING 类型的子类型:short strings 、long strings
Lua Value
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 */
};
struct lua_TValue {
TValuefields;
};
#define TValuefields Value value_; int tt_
typedef struct lua_TValue TValue;
使用一个union 来统一表示Lua的所有类型,为了区别不同的类型添加一个tt 字段来标记。
其中0-3 bit 表示基本类型; 4-5 bit 表示子类型;第 6 bit 表示是否可GC。这样就可以完整的标记所有的 Lua 类型 。
GC Object
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 */
};
struct lua_TValue {
TValuefields;
};
#define TValuefields Value value_; int tt_
typedef struct lua_TValue TValue;
Value 联合体的第一个字段为 GCObject, 它是所有可以GC 类型的公共定义。包括 FUNCTION ,STRING,USERDATA, TABLE, THREAD 。
GCObject 用链表链接在一起。其中 tt (type tag)字段是类型标记字段,marked 字段在GC 模块中使用,表示GC 过程中对象活动状态。
所有的可 GC 类型的 struct 定义 都在首部 定义了 CommonHeader 宏,这是为了GCObject 与这些类型直接的转换。 比如看下 TString的定义
TString & UData
/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct TString {
CommonHeader;
lu_byte extra; /* reserved words for short strings; "has hash" for longs */
unsigned int hash;
size_t len; /* number of characters in string */
struct TString *hnext; /* linked list for hash table */
} TString;
/*
** Ensures that address after this type is always fully aligned.
*/
typedef union UTString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
TString tsv;
} UTString;
STRING 类型有 短字符串与长字符串之分。LUA-TSHRSTR(短字符串 ( 0x100 | 0x0 = 0x4 = 4)) ;LUA-TLNGSTR(长字符串0x100 | 0x10000 = 0x10100 = 20); 根据字符串的长度(luaconf.h中的LUAI-MAXSHORTLEN,默认为40)的不同来区别。
1. 其中 extra 字段 在短字符串中 如果 extra >0,则表示这是一个系统保留的关键字,extra的值直接对应着词法分析时的一个token值,这样可以加速词法分析的速度,同时也保证不被GC 回收; 对于长字符串,一般很少做索引或者比较,所以长字符串直接链接到allgc 链表上 做GC 对象来处理。Lua不会对新创建的长字符串对象计算哈希值,也不保证长字符串对象的唯一性。当长字符串需要被用来当作索引时,会为其计算一次哈希值,并使用extra来记录是否已经为其计算了哈希值。
2. hash字段则是用存储在全局字符串池里的哈希值;
3. len表示长度,lua的字符串 不同于 C 字符串 (并不以0结尾),所以需要记录长度信息;
4. hnext是用来把全局TString串起来,整个链表就是字符串池;
对于短字符串,在实际使用中一般用来作为索引或者需要进行字符串比较。不同于其他的对象,Lua并不是将其连接到全局的allgc对象链表上,而是将其放到全局状态global-State中的字符串表中进行管理。
这个字符串表是一个stringtable类型的全局唯一的哈希表。当需要创建一个短字符串对象时,会首先在这个表中查找已有对象。所有的短字符串都是全局唯一的,不会存在两个相同的短字符串对象。如果需要比较两个短字符串是否相等,只需要看他们指向的是否是同一个TString对象就可以了,速度非常快。
上图为 TString 的内存分布, TString 结构只是描述了 头部,真正的字符串内存紧接着直接存储在struct 之后。所以字符串对象的 size为 :sizeof(TString)+字符串长度+1。
UTString 结构体将 L-Umaxalign 与 TString 包裹是为了保证内存对齐
提供一组宏来访问字符串内容的address
/*
** Get the actual string (array of bytes) from a ‘TString’.
** (Access to ‘extra’ ensures that value is really a ‘TString’.)
*/
#define getaddrstr(ts) (cast(char *, (ts)) + sizeof(UTString))
#define getstr(ts) \
check_exp(sizeof((ts)->extra), cast(const char*, getaddrstr(ts)))
/* get the actual string (array of bytes) from a Lua value */
#define svalue(o) getstr(tsvalue(o))
/*
** Header for userdata; memory area follows the end of this structure
** (aligned according to 'UUdata'; see next).
*/
typedef struct Udata {
CommonHeader;
lu_byte ttuv_; /* user value's tag */
struct Table *metatable;
size_t len; /* number of bytes */
union Value user_; /* user value */
} Udata;
/*
** Ensures that address after this type is always fully aligned.
*/
typedef union UUdata {
L_Umaxalign dummy; /* ensures maximum alignment for 'local' udata */
Udata uv;
} UUdata;
/*
** Get the address of memory block inside 'Udata'.
** (Access to 'ttuv_' ensures that value is really a 'Udata'.)
*/
#define getudatamem(u) \
check_exp(sizeof((u)->ttuv_), (cast(char*, (u)) + sizeof(UUdata)))
#define setuservalue(L,u,o) \
{ const TValue *io=(o); Udata *iu = (u); \
iu->user_ = io->value_; iu->ttuv_ = io->tt_; \
checkliveness(G(L),io); }
#define getuservalue(L,u,o) \
{ TValue *io=(o); const Udata *iu = (u); \
io->value_ = iu->user_; io->tt_ = iu->ttuv_; \
checkliveness(G(L),io); }
UData 与TString 内存布局几乎一致。也使用一个额外的一个字段L-Umaxalign 包裹来保证内存对齐。
1. metatable 字段是一个Table 表,这也就是Lua 的元表,所有对UData 的操作都会先去这个元表里查找是否有对应的属性或者方法定义。每一个UData 实例提供一个单独的元表。
2. user 字段 可以供用户附加定义值,用 ttuv 字段来标记该字段的类型。
3. 类似于TString ,真正的内容直接存储在struct 后面的内存中,也提供一组宏来访问 真正内容的address。
Table
/*
** Tables
*/
typedef union TKey {
struct {
TValuefields;
int next; /* for chaining (offset for next node) */
} nk;
TValue tvk;
} TKey;
/* copy a value into a key without messing up field 'next' */
#define setnodekey(L,key,obj) \
{ TKey *k_=(key); const TValue *io_=(obj); \
k_->nk.value_ = io_->value_; k_->nk.tt_ = io_->tt_; \
(void)L; checkliveness(G(L),io_); }
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 */
unsigned int sizearray; /* size of 'array' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
struct Table *metatable;
GCObject *gclist;
} Table;
Table 是Lua中用途最广的数据类型,几乎可以模拟出所有的数据结构,非常方便易用。
/*
* WARNING: if you change the order of this enumeration,
* grep “ORDER TM” and “ORDER OP”
*/
typedef enum {
TM_INDEX,
TM_NEWINDEX,
TM_GC,
TM_MODE,
TM_LEN,
TM_EQ, /* last tag method with fast access */
TM_ADD,
TM_SUB,
TM_MUL,
TM_MOD,
TM_POW,
TM_DIV,
TM_IDIV,
TM_BAND,
TM_BOR,
TM_BXOR,
TM_SHL,
TM_SHR,
TM_UNM,
TM_BNOT,
TM_LT,
TM_LE,
TM_CONCAT,
TM_CALL,
TM_N /* number of elements in the enum */
} TMS;
- flags 字段是一个 byte 类型,用于表示在这个表中提供了哪些元方法,默认为0;当查找过至少一次以后,如果该表中存在某个元方法,那么就将该元方法对应的 flag 位置为1,这样下一次查找时只需要判断该位即可。所有的元方法映射的bit 在 ltm.h中定义
- lsizenode 字段是该表Hash桶大小的log2值,Hash桶数组大小一定是2的次方,当扩展Hash桶的时候每次需要乘以2。
- sizearray 字段表示该表数组部分的size
- array 指向该表的数组部分的起始位置。
- node 指向该表的Hash部分的起始位置。
- lastfree 指向Lua表的Hash 部分的末尾位置。
- metatable 元表。
- gclist GC相关的链表。
Table 分为 Array 部分与 Hash 部分,在 Hash 部分, Node 就是一个 Key-Value键值对,通过Key 部分的链表链接起来。
Function
/*
** Closures
*/
#define ClosureHeader \
CommonHeader; lu_byte nupvalues; GCObject *gclist
typedef 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)
Function 包括 Lua Closure、light C function、 C Closure三种子类型,其中light C function就是纯 C 函数,在Value的定义里直接用一个lua-CFunction 函数指针表示,剩下的 Lua Closure 和 C Closure 统一为一个联合体 Closure。
CClosure
CClosure,就是直接把lua-CFunction加上被闭包的c变量upvalue 数组。
LClosure
LClosure 结构体与 Proto 结构与 upvalues 链表组成。
/*
** Function Prototypes
*/
typedef struct Proto {
CommonHeader;
lu_byte numparams; /* number of fixed parameters */
lu_byte is_vararg;
lu_byte maxstacksize; /* maximum stack used by this function */
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;
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 */
struct LClosure *cache; /* last created closure with this prototype */
TString *source; /* used for debug information */
GCObject *gclist;
} Proto;
Closure对象是lua运行期一个函数的实例对象 ,我们在运行期调用的都是一个个Cloure对象,而Proto 就是 Lua VM 编译系统的中间产物,代表了一个Cloure原型的对象,大部分的函数信息都保持在 Proto 对象中,Proto对象是对用户不可见的。
每个Cloure对象 都对应着自己的 Proto,在运行期一个Proto可以产生多个Cloure对象来代表这个函数实例。
LocVar
局部变量 local
/*
** 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;
- varname 表示变量名。
- startpc 与 endpc 决定了变量的作用域。
Upvaldesc
/*
** 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;
upvalue 有人叫闭包变量,也有叫上值。为了让 upvalue 可比较 ,使用Upvaldesc 结构 描述了UpValue 变量的信息:
1. name :upvalue 变量名称。
2. instack :描述了函数将引用这个upvalue 是否恰好处于定义这个函数的函数中,这时,upvalue 是这个外层函数的局部变量,它位于数据栈上。
3. idx : 指的是upvalue 的序号。对于关闭的upvalue ,已经无法从栈上获取到,idx 指外层函数的upvalue 表中的索引号;对于在数据栈上的 upvalue ,序号即是变量对应的寄存器号。
这个结构体只是描述了 upvalue的信息,真正的upvalue 变量值存储在 LClosure 结构体重的 upvals 链表中。
UpVal
/*
** 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;
};
- v :指向了Upvalue 变量的值得 指针。
- refcount:引用计数。
- Upvalue 变量的值 在不同的状态 取法不同。 当 一个Proto 处于 open 状态时候(也就是这样Proto在外层的函数没有返回之前),变量的值可以直接通过 upval ->v 这个指针引用,这个时候 open 结构体把当前作用域内的所有闭包变量都链成一个链表,方便以后查找。 反之 close 状态就是 外层函数返回的时候,Proto 需要把闭包变量 的值copy 出来到 upval->u.value 中,upval->v 自然指向 upval->u.value 。
- 可以通过判断UpVal ->v和u->value是否相等来判断UpVal处于open还是clsoed状态。