Lua 5.3 源码分析(一)类型系统

时间:2021-01-06 15:46:30

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 类型 。
Lua 5.3 源码分析(一)类型系统

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对象就可以了,速度非常快。

Lua 5.3 源码分析(一)类型系统
上图为 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;

  1. flags 字段是一个 byte 类型,用于表示在这个表中提供了哪些元方法,默认为0;当查找过至少一次以后,如果该表中存在某个元方法,那么就将该元方法对应的 flag 位置为1,这样下一次查找时只需要判断该位即可。所有的元方法映射的bit 在 ltm.h中定义
  2. lsizenode 字段是该表Hash桶大小的log2值,Hash桶数组大小一定是2的次方,当扩展Hash桶的时候每次需要乘以2。
  3. sizearray 字段表示该表数组部分的size
  4. array 指向该表的数组部分的起始位置。
  5. node 指向该表的Hash部分的起始位置。
  6. lastfree 指向Lua表的Hash 部分的末尾位置。
  7. metatable 元表。
  8. gclist GC相关的链表。
    Lua 5.3 源码分析(一)类型系统
    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;

Lua 5.3 源码分析(一)类型系统
Closure对象是lua运行期一个函数的实例对象 ,我们在运行期调用的都是一个个Cloure对象,而Proto 就是 Lua VM 编译系统的中间产物,代表了一个Cloure原型的对象,大部分的函数信息都保持在 Proto 对象中,Proto对象是对用户不可见的。

每个Cloure对象 都对应着自己的 Proto,在运行期一个Proto可以产生多个Cloure对象来代表这个函数实例。
Lua 5.3 源码分析(一)类型系统

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;

  1. varname 表示变量名。
  2. 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;
};
  1. v :指向了Upvalue 变量的值得 指针。
  2. refcount:引用计数。
  3. Upvalue 变量的值 在不同的状态 取法不同。 当 一个Proto 处于 open 状态时候(也就是这样Proto在外层的函数没有返回之前),变量的值可以直接通过 upval ->v 这个指针引用,这个时候 open 结构体把当前作用域内的所有闭包变量都链成一个链表,方便以后查找。 反之 close 状态就是 外层函数返回的时候,Proto 需要把闭包变量 的值copy 出来到 upval->u.value 中,upval->v 自然指向 upval->u.value 。
  4. 可以通过判断UpVal ->v和u->value是否相等来判断UpVal处于open还是clsoed状态。