Design

引子

A2的设计思路大部分来自lua，正如home page上面说的。A2被创造出来的主要目的就是：笔者能够实现个仅次于lua的解释器。 到目前来说，从对5000个数据进行选择排序的性能测试上来说，A2的跑分还是很不错的。;-) 在此，我不得不要佩服下lua的作者，尽管我只是读过部分lua源代码。 在A2的实现过程中借鉴了lua的很多想法和设计(opcode)。在没看到lua的opcode之前，你很难想象lua能够将单条指令压缩到32位bit上。也很难想象作者能够将lua在那么多的平台上通过编译。 作者本人并未全部精读lua的源代码，而且看的部分也很散乱，完成了A2之后，也打算花一段时间，精读下。相信会更有深层次的体会吧！

本文主要是描述了A2解释器是如何工作的，以及各个模块的大致设计思路。写的不算很细，里面有些花费大量时间的设计细节就没提及了。主要还是以让读者能够 了解整个设计思路为目标。 当然，如果阁下能花点时间，去读下源码(我已经尽力把源码写的模块化和简洁)，觉得不爽的地方，欢迎强喷。如果获得阁下的认同， 我想，那必然是一件很好的事情！ 呵呵

A2其中不乏有些是从lua那借鉴过来，但同时也加入了很多作者自己的想象力-_-!，碰到问题解决问题，尽量保证处理的漂亮，但是依然能看到些不好的地方， 正如Home上所说，相信会有更加优雅和完美的实现方式。

最后，感谢lua. ;-)

执行流程

最初作者的想法是要把A2设计成像lua那样的one pass编译的基于寄存器vm的解释器。但在编译阶段，one pass的方式太过于繁杂， 由于作者的能力有限，实在是搞不定-_-!。于是就退而求其次：lex词法分析阶段是全解析，生成一个token链表，传入给parse语法分析模块， 在语法分析阶段中，并不是一次性将token chain全部遍历完全生成AST(抽象语法树)再提交给编译阶段处理；而是按照以trunk为单位生成 AST(抽象语法树)，之后提交给编译阶段生成中间指令。trunk的文法定义如下：

trunk  ::= expression | if | for | foreach | function

在语法解析和编译阶段倒是有点one pass的味道，但是跟真正意义上的one pass还是有很大差距(lua的one pass处理中，都极少出现AST而直接生成opcode)。

当阁下每次加载一段源码，经过一系列的分析处理之后，在vm中最终生成的是一个closure(闭包，匿名function)对象。 这个closure对象中包含了编译之后的 ir chain(中间指令序列)以及所需要的upvalue(升量)列表。 之后将这个closure对象添加到vm的函数调用链中，同时分配stack frame (栈帧)，遍历此clousre中的ir chain来执行逻辑。对于一段源码到执行，大致是以上这个流程。描述如下：

[a2 env new]
     |
     |
     |
[IO读取源代码] --> [lex 进行词法分析生成token chain] --> [parse 以trunk为单位进行语法解析生成 AST]  --> [遍历AST编译生成IR] -
                                                           ^                                                        |
                                                           |________________________________________________________|
                                                                                         |
                                                                                         | trunk 读取完毕
                                                                                         |
                                                         [ 创建 closure，将closure加载到调用链，同时逐条执行 closure中的IR ]

io流

实现文件a2_io.c和a2_io.h ，这两个文件简单的实现了对文件和字符串的一个简单流操作。a2_io对象创建后，会有一段用于读写的固定buf。 提供给外部的接口主要有a2_io_readchar 读取一个字符 和 a2_io_matchchar 匹配n个字符之后的字符。 a2_io的唯一工作就是根据游标不停的向这个 buf中读取数据，一旦buf读到末尾，而且当前文件依然未读完，会将buf clear，再次读取。以上是对文件的流操作，对于字符串的操作，更加简单。 仅仅是将原本指向固定buf的指针指向传入的string地址。每次的read，以及match都不会从新copy到缓存中。对string的操作，只会进行读操作。 因此不必担心对string流的操作会出现副作用。

a2_io是对file和string的一个流抽象，主要用途在lex词法分析阶段便于查找、读取以及匹配相应的字符。

lex词法分析

词法分析阶段会从当前的a2_io流中逐个读取字符，进行解析成token串，模块为a2_lex.c和a2_lex.h。结构如下：

struct a2_lex{
	struct a2_env* env_p;
	char* lex_map[LEX_MAP_DEEP];
	byte  lex_str2hash[sizeof(_key)/sizeof(char*)];
	size_t line;
	char*  a2_s_num_bufs;
	struct{
		size_t cap;
		size_t size;
		struct a2_token* token_p;
	}ts;
};

在这里有个小的优化（如果算的上是的话），lex_map是用来存储关键词的map，关键字字符串是经过hash散列之后无碰撞存储的。之所以没有创建一个 map对象来保存是因为：不想仅仅为几个关键字就开辟一段远超于关键字个数的slot。而且还无法控制关键字的hash散列是否存在冲突。

词法分析阶段的流程并非像lua那样是分布的。词法分析阶段将会把当前流中的数据全部取出，生成token chain。每个token的结构如下：

struct a2_token{ 
	uint32 tt;    // 类型和操作码
	size_t line;  // 行号	
	a2_value v;   // value 值 
};

在a2_token结构中 tt是一个uint32的一个字段，其中包含了 这个token的type类型，以及op操作码。tt的高8bits存储的是type, 后24bits存储的是op。 tt的生成，以及type,op的获取可以通过一下三个宏可以明显的看到:

#define tt2tk(tt)	((tt)>>24)
#define tt2op(tt)	((tt)&0xffffff)
#define kp2tt(k, p) (((k)<<24) | (p)) 

type标示了某个token的类型。

op只有在type为tk_op时才会有值。标示当前是何种的操作。

每个token的内存是由a2_lex模块中一段 连续的内存token_p分配的。结构入下：

struct{
		size_t cap;
		size_t size;
		struct a2_token* token_p;
	}ts;

这块内存是与a2_lex模块一个生命周期，在a2_lex模块被new时一起创建出来。 每生成一个token仅仅是向这个内存中取出 一块sizeof(token)大小的内存，如果当前内存不够，将会realloc两倍之后之后再分配。由于token的分配不牵涉到删除的问题，而且每次都是整块取出固定大小 的内存，所以不存在内存碎片的问题。仅仅需要一个变量cap记录当前已经分配了多少，当解析阶段完成时，将会把cap的记录清零。下次的词法分析将会重复的使用这些内存。

词法分析中一旦解析到一个标示符、关键字和字符串时，将会把解析到string加载到全局string表中。之所以会有全局string表，是为了避免同样一个string 被创建两次。在token对象中，仅仅是保留了这个string的指针，对于数字类型是直接写入到token中。

当把a2_io流中的数据全部读取之后，同时生成了token chain，lex词法分析的过程就算是完成了。

简而言之，lex的功能只做：将a2_io的流数据完全读取出来，之后生成token chain这一件事情。

parse语法分析

语法分析阶段会接受lex词法分析阶段给出来的tokan chain，以trunk为单位进行解析生成AST, 之后将AST提交给IR模块进行编译。 parse模块所在源代码a2_parse.h和a2_parse.c。数据结构如下：

struct a2_parse{
	struct a2_env* env_p;
	struct a2_token* token_chain;
	size_t len;
	size_t t_idx;

	// node buf
	byte level;
	size_t cap;
	struct a2_node* node_buf;
};

在lex阶段是对整个源码进行解析生成token chain，然而对于parse阶段并非是一次将token chain全部读取。而是以trunk为单位读取。 trunk的定义在执行流程章节给出了其文法定义。简单点说就是，parse阶段就是一个遍历token chain的过程，每次的迭代读取 一个或者多个token，这些一个或者多个的token可能是描述了一个表达式、if、for、foreach function这样一个语句。 假如有一下源码：

local a, func, c
a, c = 123, 456

func = function (a, b){
	return a+b
}

if(a>c){
	print('>')
}else
	print('<=')

func(1,2)

按照trunk的文法定义，将会被切分为如下trunk:

# trunk 1
local a, func, c

# trunk 2
a, c = 123, 456

# trunk 3
func = function (a, b){
	return a+b
}

# trunk 4
if(a>c){
	print('>')
}else
	print('<=')

# trunk 5
func(1,2)

parse模块会先将trunk1生成AST，之后提交给IR模块编译生成对应的ir指令。IR执行完成之后，再继续解析trunk2，如此循环。流程如下代码：

for( ; !is_end; ){  // 是否到token chain的末尾
		if(tt2tk(cur_token.tt)==tk_end){
			parse_readtoken(typedef uint32  ir;parse_p);
			continue;
		}
		size_t root = parse_segcontent(parse_p); // 解析当前trunk，生成AST，root为AST的根节点索引地址
		// IR generation
		#ifdef _DEBUG_
		 printf("----parse----\n");
		 dump_node(parse_p, root);
		 printf("----end------\n");
		 #endif 
		a2_irexec(parse_p->env_p, root);    // 提交给IR模块编译生成ir指令
		// clear node buf
		clear_node(parse_p);				// 清空存储node的缓存
	}

AST是一个多叉树结构，每个节点是由一个叫a2_node的对象构成，数据结构如下：

struct a2_node{
	uint16_t type;  // node 的类型
	struct a2_token* token;  // `lex`描述当前node所对应的token
	size_t childs[4];		// 子节点索引地址
	size_t next;			// 兄弟节点索引地址
};

每个node的内存分配并不是通过独立的malloc进行离散的获得。而是像lex模块中的token_p一样，有一段连续的内存而分配的。就是在struct a2_parse 中的 node_buf。每当成功的解析一段trunk都将会把node_buf进行清空(仅仅是把cap清零)，以便下一个trunk继续重复使用内存。

IR编译

IR模块接受传送过来的AST，进行树遍历，之后将其编译成对应的ir指令(字节码)。模块为a2_ir.c和a2_ir.h这两个文件。 IR模块编译的ir指令，极大的借鉴了lua的opcode的指令集。在A2中单条指令是一个32bits，定义为:typedef uint32 ir;，整个ir的设计 在本质上与lua很像，32bits的指令，有如下构成：

| 6bits op 操作码 | 8bits A 寄存器目标地址(无符号) | 9bits B 寄存器源地址/值(有符号) | 9bits C 寄存器源地址/值(有符号) |

其中B和C统一合成BX(有符号)，来表示更大的数据。

指令被分为两种模式: ABC_MODE 0 和 ABX_MODE 1，每种指令只会有一种模式存在(此处与lua不一样)，每条指令的对应何种的mode，是在IR模块被加载时初始化的，初始化的位置在a2_ir.c中的_init_op_modle函数，指令的模式一旦初始化之后，是不会被 修改的，而且都是常量，这点其实可以通过static变量来存储。但是在IR中并没这么处理， 模式表是在IR模块中创建出来，并没有用静态变量， 这样做的目的是为了保证线程安全，以及不同state之间的读取操作可能会遇到的潜在问题。

ir指令的总类个数是38个，其中NIL指令为无效指令。实际使用过程中是用37个指令，这些指令的类型定义在，a2_ir.h的enum ir_op中。 由于op操作码占用6bits，因此能够表示的上限是2^6 = 64个。

阁下可能有疑问为何，B,C,以及BX这些寄存器索引，是有符号的？在B, C, BX这些中如果是>=0的值，则标示的是在stack frame(栈帧)上的地址。如果 <0，则标示的是a2_xclosure中的const stack(常量栈)的地址。stack frame和a2_xclosure这个会在下章vm中解释。在此要说下const stack(常量栈)，当IR模块解析AST时，如果碰到常量值，例如常量string和常量number，将会把这些东西push到当前解析的a2_xclosure的常量栈中. 因此当vm执行当前ir时，发现B,C或者BX的值为<0，就会向当前closure的常量栈中定位，以及取出值进行操作。

阁下应该能够发现，常量的值最大也就能放在BX中，因此应该是有上限的，这个上限是2^17 = 131072个。正确，但是这个限制仅仅是对一个函数而言，并非是在 整个A2环境中仅仅能够使用131072个。相信我，你在一个函数中，用不到那么多的常量.;-)

A寄存器索引保存的永远是>=0 的值，标示的是经过op操作之后，将值放入的目标地址。A寄存器索引的值是stack frame上的地址。同样，由于A大小的限制， 一个闭包最多能够定义256个变量。我也相信，你在一个函数中用不到那么多的变量。;-)

具体的编译流程，作者不再详细解释，尽管这块是作者实现时间比较长的地方，由于vm是基于寄存器的，不像stack的vm那样可以有求值栈来进行保存中间值， 编译的过程中，经常要考虑到目标地址，以及中间变量的问题。 这块本身就是个繁琐的流程，如果阁下感兴趣的话，请查看源码吧。 ;-) 推荐查看@云风的 lua源码赏析 的vm章节。

IR解析完成之后最终返回的是一个a2_xclosure的对象。

closure 闭包

其实这块应该放到vm之后作为存储对象来分类说明，但是由于a2_xclousre与IR模块牵涉比较多，所以就提前吧。 a2_xclousre并不是用来表示A2 中闭包这个对象的。来描述闭包这个概念的是a2_closure。a2_xclosure中保存了对应闭包在编译阶段生成的ir字节码，以及一些对这个闭包的一些描述信息，比如这个闭包是否有参数， 参数有多少，函数要分配多大的栈帧，在当前函数下定义的函数，以及所引用其他闭包的upvalue升量。结构如下：

// the describe of closure
struct a2_xclosure{
	int refs;	// the count of reference 
	int params; // the count of parameters
	int regs;	// the count of register 

	// // intermediate representation chain
	ir* ir_chain; 
	size_t* lines;
	size_t len;
	size_t size;

	// include xclosures
	struct {
		struct a2_xclosure** xcls_chain;
		int cap;
		int size;
	}xcls_stack;

	// const varable stack
	struct obj_stack c_stack;

	// upvaluex chain
	struct {
		struct upvaluex_idx* upvaluex_chain;
		int len;
		int size;
	}upvaluex;
};

a2_xclosure的存在意义是为了生成对应的a2_closure对象，他们之间的关系是1对多的关系，a2_xclosure中有一个refs的属性，标示了当前有 多少个a2_closure进行引用。 本质上来说，a2_xclosure只是对一个closure的描述，你可以认为，a2_xclosure代表的是类，而a2_closure则是a2_xclosure的实例化， 里面保存了数据， 然而这个数据需要通过a2_xclosure的描述才能解析到。 a2_closure是A2内部对函数类型变量的一个内部表示。 数据结构如下，很简单：

struct a2_closure{
	struct a2_xclosure* xcls_p;

	// uped chain
	int ud_size;
	int ud_cap;
	struct a2_upvalue** uped_chain;

	// upvalue chain
	int uv_size;
	struct a2_upvalue uv_chain[1];
};

xcls_p保存的是对应的a2_xclousre指针，uped_chain,保存的是当前引用此闭包中的变量做升量的闭包链。 uv_chain[1]这个数组存储的是 当前闭包的upvalue值。

所谓的class是在变量上绑定函数。所谓的closure是在函数上绑定变量(upvalue)。 从这个结构中可以很明了的看出来。 ;-)

##VM虚拟机 VM模块负责执行a2_closure，维护callinfo chain函数调用链，以及分配管理stack frame栈帧功能。模块所在文件a2_vm.c和a2_vm.h 数据结构如下：

struct  a2_vm{
	struct a2_env* env_p;
	struct {
		struct a2_obj* sf_p;
		size_t cap;
		size_t size;
	}stack_frame;   // 栈帧
	struct vm_callinfo* call_chain;  // 函数调用链
};

有必要先说明下struct vm_callinfo，定义如下：

struct vm_callinfo{
	struct a2_closure* cls;
	struct {
		size_t sf_idx;
		size_t len;
	}reg_stack;

	int retbegin;
	int retnumber;
	size_t pc;

	struct vm_callinfo* next; 
	struct vm_callinfo* front;
};

call_chain这个是一个链表， 是函数调用链。每当产生一个函数调用，都会向头部添加一个struct vm_callinfo这样的一个结构。cls字段描述的是 当前正在调用的闭包对象，在closure章节中，阁下可以知道，其中包含了ir指令。 reg_stack这个是分配给当前函数调用的栈帧切片。在VM中， stack frame栈帧是一块连续的内存，如：struct a2_vm中的stack_frame，在vm被new出来时，会先对栈帧分配个默认大小，没当产生一个 函数调用，都会根据传入的a2_closure对象中的a2_xclosure中记录的当前函数需要的最多栈变量个数，来向stack_frame中获取一个slice切片， 如果stack_frame内存不够，将会realloc之后再分配。在struct vm_callinfo中的reg_stack就是描述了这个栈帧切片:

struct {
		size_t sf_idx;   // 在stack_frame的起始索引
		size_t len;		//  切片的长度
	}reg_stack;

retbegin属性记录的是当前函数返回给上个函数后，返回值在上个函数的栈帧切片中开始地址，retnumber为返回的个数，便于执行RETURN指令时用。

size_t pc; 程序计数器.

next, front双向链表指针。

VM的解析ir的函数为static int a2_vm_run(struct a2_vm* vm_p);这个函数只做一件事情，就是解析执行call_chain链表的顶端a2_closure。 函数内部很简单:

// vm 
static int a2_vm_run(struct a2_vm* vm_p){
	int ret = 0;

	for(;;){
		switch(curr_op){
			case LOAD:
				_vm_load(vm_p);
				break;
			case LOADNIL:
				_vm_loadnil(vm_p);
				break;
			case GETGLOBAL:
				_vm_getglobal(vm_p);
				break;
			case SETGLOBAL:
				_vm_setglobal(vm_p);
				break;
			.......
			/*
			*一路的 case.
			*/
			default:
				assert(0);
		}
	}
	return ret;
}

对于指令非分派使用的是可移植性比较高的swtich case，尽管这样性能比较差劲，而且R酱曾经也说因为我只用gcc，而且用switch case这样的分支，可以很容易改成dispatch的方式， 但是我却认为，这样增加了可移植性，而且lua也并没这么做，这么做的话，做性能测试的时候就不太好做比较。所以就没在指令分配上做这个优化了。 对于目前来说，我对A2的性能还算满意，尽管测试用例比较片面(请看A2的首页君)。;-)

在ir章节所说的A寄存器中存储的目标地址，其实指的就是栈帧切片上的地址，对于地址的读写是通过callinfo_sfi这个宏来操作的。具体的指令解析操作 就不在描述，流程很简单，感兴趣的可以查看下源代码a2_vm.c。

object数据对象

阁下在A2脚本中使用的所有类型的变量，在解释器中都被抽象为a2_object,数据结构如下:

struct a2_obj{
	int type;
	a2_value value;
};

type为对象类型，a2_value是个union结构。对于32位的机器，作者做过NaN Trick的优化（请参阅百科了解或者云风的lua源码赏析）， a2_value的结构如下：

typedef union {
		struct a2_gcobj* obj;
		a2_number number;
		a2_cfunction cfunction;
		void* point;
		uint32 uinteger; 
		size_t addr;
}a2_value;

对于number,注册的c function类型都记录在非obj字段中，struct a2_gcobj* obj字段保存了可回收的数据类型：stirng, map, function, arraylist。关于a2_gcobj会在gc章节解释。

gc垃圾回收

这是作者实现起来最麻烦的模块之一，其实真正的代码量并不多，主要是在编写是要有清晰的思路。A2的gc实现比较简单，当gc工作时，是stop world 的概念， 这个可能跟早期的lua gc实现很像(推测，作者并未考证过5.1之前的源码)。lua的gc早已改成了分步完成。实现分步的话，对程序的控制要求很高，而且gc 这个设计并非作者的最初目的。所以就偷懒了-_-!，但是尽管降低了要求，可依然还花费了很多时间去实现。

gc模块主要在a2_gc.c和a2_gc.h，还有一些是在a2_vm.c中。 数据结构如下:

struct a2_gc{
	byte gc_flag;
	size_t gc_threshold;
	size_t gc_count;
	struct a2_env* env_p;
	struct a2_gcobj* chain;
};

所有的可被回收的对象都被chain单向链表连接。A2的gc使用的标记回收，和引用计数(对于a2_xclosue这些对象来说)。这点可以在看a2_gcobj的 数据结构中看得到：

struct a2_gcobj{
	int type;
	byte mark;
	union{
		char* str;
		struct a2_closure* cls;
		struct a2_array* array;
		struct a2_map* map;
		struct a2_obj* uv;
		void* obj;
	}value;
	struct a2_gcobj* next;
};

mark字段描述的是当前可回收对象描述的标记，标记分为三种: white,black和blue。每当创建一个可回收对象，都会首先被添加进chain链表的 头部中，同时mark为white，标示的是这个对象是可被回收，对于全局变量来说将会标记为blue。当gc被触发之后，将会先遍历vm的stack frame栈帧，从底部开始直到栈顶，对于存在的gcobj标记为black，意思为，当前变量被引用，不可回收。标记完成之后，将会开始回收操作， 遍历struct a2_gc中的chain开始清理white节点，遇到black会将其改变为white之后再运行，跳过blue节点。 对于全变量的set操作， 将会把blue改为white,下次回收时将会处理。

整个过程跟大部分的标记回收算法类似。

exception异常错误捕获

A2中使用的异常是longjump，异常模块主要在a2_error.c和a2_error.h这两个文件中。 函数int a2_xpcall(struct a2_env* env_p, a2_pfunc pfunc, void* ud);，主要功能为创建一个longjump，追加到异常链中。一旦异常抛出 之后，将会把当前的longjump断开，如果当前异常链为NULL,将会调用panic函数之后exit。

整个异常过程很简单，目前是只提供了a2_error这个函数来抛出异常。这块实现参照了lua。

lib库绑定

如果阁下熟悉lua的话，将会很熟悉库绑定的概念。通过make编译出来的只是一个liba2.a的一个静态库，库的API是a2.h这个头文件中声明，API的函数前都会用A2_API这个宏进行区分。 库中实现了dofile，dostring这些加载源代码，返回值为非零，标示着 将会有异常产生，异常的描述是个string，在c与A2交互的stack顶部，阁下可以通过a2_tostring函数取出进行打印。 test_a2.c中实例如下:

	struct a2_state* as = a2_open();
	a2_openutil(as);
	if(a2_loadfile(as, argv[1])){
		printf("%s\n", a2_tostring(as, a2_top(as)-1));
	}

A2默认提供了一个libutil的一个库绑定，里面有print,len, add, eve。这些简单的函数。 A2.h中定义的API目前没有LUA的强大， 但是基本的操作已经给出，比如获取当前栈顶高度，push,to,new, set等操作。 对于API日后会有专门的文档说明，相信与lua很像。 如果阁下对这块不了解的话，建议熟悉下lua与C之间的交互，作者本人不再描述.;-)