Lua5.0原理探究

前言

马上要去公司搬砖了，想要提前做一下准备，emm。。。其他倒还好，Lua没用过，也没详细了解过，怕到时候拉胯，所以先准备一下Lua吧。

Lua作为一个内部的软件开发工具，诞生于学院实验室，然而，不知何故，很快被全世界的几个工业项目所采用，而且目前正被广泛运用于游戏行业。

Lua基础

解释与执行

首先，Lua是一个基于C而制作的的脚本语言（动态语言，弱类型语言），他与我们常使用的C++，C#这些编程语言（静态语言，强类型语言）的最大差别之一就是前者在运行时进行编译，后者则是在运行前就编译好
用图片表示就是这样

下面是我做了一个Lua与C#编译运行的对照表格

语言	编辑	预编译	运行时编译	执行
Lua	编写lua文件	无	虚拟机读取字节码并转换成虚拟机指令，汇编器编译成机器码	CPU执行机器码
C#	编写cs文件	被C#编译器编译成dll，包含IL代码	CLR使用JIT编译把IL转换成机器码	CPU执行机器码

我们可以看到，Lua较为核心和重要的点就是他的虚拟机了，接下来就看看虚拟机在这个过程中具体做了什么

编译系统

编译系统的工作就是将符合语法规则的chunk转换成可运行的closure。要了解编译系统，首先要了解作为输入的chunk和最为输出的closure以及他们的对应关系。

chunk代表一段符合Lua的语法的代码。

closure对象是lua运行期一个函数的实例对象，我们在运行期调用的都是一个closure。

proto对象是lua内部代表一个closure原型的对象，有关函数的大部分信息都保存在这里。这些信息包括：

指令列表（Instructions）：包含了函数编译后生成的虚拟机指令。
常量表（Constant table）：这个函数运行期需要的所有常量，在指令中，常量使用常量表id进行索引。
子proto表（Child proto table）：所有内嵌于这个函数的proto列表，在OP_CLOSURE指令中的proto id就是索引的这个表。
局部变量描述（Local vars desc）：这个函数使用到的所有局部变量名称，以及生命期。由于所有的局部变量运行期都被转化成了寄存器id，所以这些信息只是debug使用。
Upvalue描述（Upvalue des）：设个函数所使用到的Upvalue的描述，用来在创建closure时初始化Upvalue。

每个closure都对应着自己的proto，而运行期一个proto可以产生多个closure来代表这个函数实例，就像下图所示

由此可见，closure是运行期的对象，与运行期关系更大；而与编译期相关的其实是proto对象，他才是编译过程真正需要生成的目标对象。

我们可以调用lua_load api，将一个chunk进行编译。lua_load根据当前chunk生成一个mainfunc proto，然后为这个proto创建一个closure放到当前的栈顶，等待接下来的执行。Chunk内部的每个function statement也都会生成一个对应的proto，保存在外层函数的子函数列表中。所有最外层的function statement的proto会被保存到mainfunc proto的子函数列表中。所以，整个编译过程会生成一个以mainfunc为根节点的proto树。

虚拟机

在十年的时间里（从 1993 年 Lua 发布开始），各种版本的 Lua 都使用基于堆栈的虚拟机，包括现在的C#，Java也是使用的基于堆栈的虚拟机。从 2003 年开始，随着 Lua5.0 的发布，Lua 改用基于寄存器的虚拟机。

用寄存器式虚拟机消除了用堆栈式虚拟机时为了在栈中拷贝数据而必需要的大量出入栈（push/pop）指令，在 Lua 中，这些出入栈指令相当费时，因为它们需要拷贝带标志的值（tagged value, TObject），因此寄存器结构既消除了昂贵的值拷贝操作，又减少了为每个函数生成的指令码数量。

寄存器式虚拟机相关的两个难题是： 指令大小和译码速度。寄存器式虚拟机的指令需要指明操作数位置，因此通常要比堆栈式虚拟机的同类指令长。（例如，当前 Lua 虚拟机的指令长度是 4 字节，而其他许多典型的堆栈式虚拟机的指令长度只有 1-2 字节，包括前一版本的 Lua 也是。）但在另一方面，基于寄存器的虚拟机生成的操作码要比堆栈式虚拟机少，因此指令总长度大不了多少。

Lua 的虚拟机指令将 32 位分成 3 或 4 个区域，如下。 OP 域是指令，占 6 位。其他域是操作数。 A 域总是存在的，占 8 位。 B 域和 C 域各占 9 位。它们可以组合成一个 18 位的 Bx 域（无符号）或 sBx（有符号）

有一个解释器可以把这些字节转译成虚拟机指令（对应我们上面提到的指令列表（Instructions）内容），其实就类似我们常说的的机器码与汇编码的关系，不过要上层的多。

最后虚拟机读取到这些Lua指令，因为本身Lua由C编写，所以直接使用汇编器把这些这些虚拟机指令对应的真正的汇编代码汇编成机器码，让CPU执行。

值的内部表示

Lua 是动态类型的语言：类型是与值而不是与变量相关。

Lua 有 8 种基本的值类型： nil， boolean， number， string， table， function， userdata 和 thread。

nil类型是个标记类型，只有一种值，就是 nil。
Boolean 类型的值有 true 和 false 两种值。
number 类型是双精度的浮点数，对应于 C 语言中的 double，但这不是绝对的，可以通过重新编译 Lua 来将其重设为 float 或 long 型。（一些游戏终端和小型机缺乏支持 double 数据类型的硬件。）
string 是字节数组，有一个显式的长度，因此可以容纳任何二进制数，包括 0。
table 是关联数组，可以通过任何（除了 nil）值来索引，也能容纳任意值。
function 可以是 Lua 函数或根据 Lua 虚拟机接口函数的原型编写的 C 函数。
Userdata 实际上是一个指向用户内存块的指针，分两种情况： heavy，内存由 Lua 分派，并由垃圾回收机制负责处理， light，内存由用户分配并释放。
thread 代表协程。

任何类型的值都是 first-class 的:可以将其存入全局变量、局部变量或 table 域中，或作为实际参数传递给函数，或从函数中返回值，等等

Lua 将值表示成带标志的联合结构，即（t， v）对，其中 t 是个整数，代表

值 v 的类型， v 是一个 C 语言 union 类型数据结构，它存储有实际的值。

nil 型只有单个值。
boolean 和 number 实现为未包装的值： v 直接对应于 union 中由 t指示的域。这意味着 union 必须有足够空间容纳一个 double 型。
string， table，function， thread 和 userdata 型数据通过引用来实现： v 中含有一个指向结构的指针（类似C#的类型对象指针），该结构实现由 t 指定的类型。这些结构共用一个头结构（类似C#的同步块索引，但是包含了更多内容），头结构中含有垃圾回收所需的信息。结构的剩余部分包含的信息对应于指定的数据类型。

typedef struct
{
	int t;//标志v的类型
	Value v;//对应的值
}TObject;

typedef union
{
	GCObject *gc;//类型对象指针，GCObject包含GC所需要的信息
	void *p;//轻量级userdata
	lua_Number n;//表示number，默认为double类型
	int b;//boolean
}Value;

用带标志的联合结构来表示Lua值导致的一个直接结果就是拷贝Lua值比较费时：在 double 值为 64 位的 32 位机器上， TObject 是 12 字节（或 16 字节，如果机器以 8 字节边界对齐 double 的话），因此拷贝一个值需要拷贝 3 或 4 个机器字，然而，在 ANSI C 范围内，很难再更好地表示一个 Lua 值了。

就像早期的解释型语言，如 Snobol和 Icon一样， Lua 用一个散列表将 string 内部化： Lua 为每个字符串只保留一份拷贝，而且字符串是不变的：一旦内部化，字符串将不可更改。字符串的散列值由一个结合了位运算和数学运算的简单表达式计算出来，计算过程中会对所有数据位进行随机洗牌。当字符串内部化时，散列值被保存起来，以便后面的字符串比较和表索引操作能快速进行。如果字符串太长，那么散列函数就不再逐个考察每个字节，因而能快速计算长字符串的散列值。避免长字符串处理时的性能损失是非常重要的，因为在 Lua 中，计算长字符串的散列值是很普遍的。例如，在 Lua 中经常将整个文件读入一个长字符串中进行处理。（怪不得Lua可以放飞自我的使用字符串）

表

表是Lua 中唯一的表示数据结构的工具。

Lua 中的表是关联数组，即可以通过任何值（除了 nil）来索引表项，表项可以存储任何类型的值。此外，表是动态的，当有数据加入其中（对不存在的表项赋值），或从中移除数据（将 nil 赋给表项）时，它们可以自动伸缩。

不同于其他脚本语言， Lua 中没有内置对数组类型的支持。数组是用表和整数索引来模拟的。用表来模拟数组有助于语言的实现。这样做主要是出于简单性：Lua 不需要两套截然不同的指令来处理表和数组。

在 Lua 中实现稀疏数组价值不大，例如，在 Perl 中，如果你试图执行程序： a[1000000000]=1;可能导致内存不足，因为这会导致 Perl创建一个拥有 10 亿个元素的数组，而等价的 Lua 程序， a={[1000000000]=1}，创建的表只有一个表项。

截至 Lua4.0 版，表都是严格地以散列表（哈希表）实现的：所有的键、值都明确地存在于表中。在 Lua5.0 中，对表被用作数组的情形使用了一种新的算法来进行优化：对于键是整数的表项，将不保存键，只将值存入一个真正的数组中。更准确地说，在 Lua5.0 中，表以一种混合型数据结构来实现，它包含一个散列表部分和一个数组部分。对于键、值对 "x"→9.3, 1→100, 2→200, 3→ 300，图 2 展示了一种可能的形式。注意右边的数组部分：它不保存整数键。只有在底层实现时才需要注意这点区别，其他情况下，即使是对虚拟机来说，访问表项也是由底层自动统一操作的，因而用户不必考虑这种区别。表会根据其自身的内容自动动态地使用这两个部分：数组部分试图保存所有那些键介于 1 和某个上限 n之间的值。非整数键和超过数组范围 n 的整数键对应的值将被存入散列表部分。

当表需要增长时， Lua 重新计算散列表部分和数组部分的大小。最初表的两个部分有可能都是空的。新的数组部分的大小是满足以下条件的最大的 n 值： 1到 n 之间至少一半的空间会被利用（避免像稀疏数组一样浪费空间） ； 并且 n/2+1到 n 之间的空间至少有一个空间被利用（避免 n/2 个空间就能容纳所有数据时申请 n 个空间而造成浪费） 。当新的大小计算出来后， Lua 为数组部分重新申请空间，并将原来的数据存入新的空间。

举例来说，假设 a 是一个空表，散列表部分和数组部分都是 0 大小。如果执行 a[1]=v,那么表就需要增长以容纳新键。 Lua 会选择 n=1 作为新数组的大小（存储一个数据 1→v）。散列表部分仍保持为空。
这种混合型结构有两个优点。

第一，存取整数键的值很快，因为无需计算散列值。
第二，也是更重要的，相比于将其数据存入散列表部分，数组部分大概只占用一半的空间，因为在数组部分，键是隐含的，而在散列表部分则不是。

结论就是，如果表被当作数组用，只要其整数键是紧凑的（非稀疏的），那么它就具有数组的性能，而且无需承担散列表部分的时间和空间开销，因为这种情况下散列表部分根本就不存在。相反，如果表被当作关联数组用，而不是当数组用，那么数组部分就可能不存在。

这种内存空间的节省很重要，因为在 Lua 程序中，常常创建许多小的表，例如，当用表来实现对象时。使用的是 Brent论文提到的HashTable增查新方法地址：https://maths-people.anu.edu.au/~brent/pd/rpb013.pdf 这种表的主要确定性是：如果一个元素不在其主位置上（例如，由散列值给出的原始位置），那么冲突元素就会在这个主位置上。换句话说，只有在两个元素拥有同样的主位置时才会出现冲突。（例如，俩元素对同一个表大小，有同样的散列值。）由于不存在次级冲突，这种表的负载因子可以达到 100%而没有任何性能损失。

Lua进阶

函数和闭包

当Lua 编译一个函数时，会生成一个原型。该原型包含有函数的虚拟机指令、常数值（数值、字符串等），以及一些调试信息。在运行期，任何时候只要 Lua执行一个 function...end 表达式，它就会创建一个新的闭包。每个闭包都有一个对函数原型的引用、一个对环境的引用（环境其实是一个表，函数可在该表中索引全局变量，后面细述），和一个数组，数组中每个元素都是一个对 upvalue 的引用，可通过该数组来存取外层的局部变量。

作用域（生存期）规则下的嵌套函数给如何实现内层函数存取外层函数的局部变量出了个众所周知的难题。考虑图 3 的例子。当 add2 被调用时，其函数体存取外层局部变量 x（Lua 中，函数参数也是局部变量）。然而，此时创建 add2的函数 add 已经返回了。如果是 x 在栈中分配的，此刻 x 已经不存在了（x 的存储空间已经被回收了）

function add(x)
	return function(y)
			return x+y
			end
end
---------------------------------
add2 = add(2)
print(add2(5))

Lua 用一种称为 upvalue 的结构来实现闭包。对任何外层局部变量的存取间接地通过 upvalue 来进行。 upvalue 最初指向栈中变量活跃的地方（图 4 左边）。当离开变量作用域时（超过变量生存期时），变量被复制到 upvalue 中（图 4 右边）。由于对变量的存取是通过 upvalue 里的指针间接进行的，因此复制动作对任何存取此变量的代码来说都是没有影响的。

与内层函数不同的是，声明该局部变量的函数直接在堆栈中存取它的局部变量。通过为每个变量至少创建一个 upvalue 并按所需情况进行重复利用，保证了未决状态（是否超过生存期）的局部变量（pending vars）能够在闭包间正确地共享。为了保证这种唯一性， Lua 为整个运行栈保存了一个链接着所有正打开着的 upvalue（那些当前正指向栈内局部变量的 upvalue）的链表（图 4 中未决状态的局部变量的链表）。当 Lua 创建一个新的闭包时，它开始遍历所有的外层局部变量，对于其中的每一个，若在上述 upvalue 链表中找到它，就重用此 upvalue，否则， Lua 将创建一个新的 upvalue 并加入链表中。注意，一般情况下这种遍历过程在探查了少数几个节点后就结束了，因为对于每个被内层函数用到的外层局部变量来说，该链表至少包含一个与其对应的入口（upvalue）。一旦某个关闭的upvalue 不再被任何闭包所引用，那么它的存储空间就立刻被回收。

一个函数有可能存取其更外层函数而非直接外层函数的局部变量。这种情况下，有可能当闭包创建时，此局部变量尚不存在。 Lua 使用 flat 闭包来处理这种情况。有了 flat 闭包，无论何时只要函数存取更外层的局部变量，该变量也会进入其直接外层函数的闭包中。这样，当一个函数被实例化时，所有进入其闭包的变量就在直接外层函数的栈或闭包中了

线程和协程

Lua 5.0 版开始， Lua 实现不对称协程（也称为半不对称协程或不完全协程）。三个 Lua 标准库函数提供了对协程的支持： create， resume 和 yield。（这些函数位于 coroutine 名字空间中。）

create 函数接收“主” 函数并用此函数创建一个新的协程。它返回一个代表协程的值，该值具有 thread 类型。（与 Lua 中任何其他值一样，协程也是 first-class 的）。
resume 函数让指定协程（重新）开始执行，进而调用其主函数。
yield 函数暂停执行中的协程 B，并将其控制权返还给之前调用 resume 使 B 得以执行的协程 A。

概念上讲，每个协程都有各自的栈。（具体说，每个协程有两个栈，正如我们第七节会讲到的，但我们可以把它们看成是一个抽象栈）。 Lua 中协程是有栈的，这样我们就可以在多级函数嵌套调用内挂起（暂停执行）一个协程。解释器只是简单地将整个栈放在一边而在另一个栈上继续执行。一个程序可以任意重启任何挂起的协程。当与栈相关的协程不可用时，垃圾回收器就回收栈空间。

协程也具有栈性和 first-class 特征，正如中 Lua 实现的，使得它们具有独特的可扩展性。这样就允许程序员用协程来实现多种高级的控制机制，如协作式多线程，生成器，对称协程，回溯等。

在 Lua 中，实现协程的时候，一个关键点是解释器不能用其自身的 C 工作栈来实现要被解释执行的函数调用指令。 当解释器程序的主循环解释执行一个调用指令时，会在（协程的运行）栈中开辟一个新的区块并调整几个指针，然后继续执行主循环去执行被调用的函数。类似地，返回指令移除栈顶的区块，调整指针，然后继续执行主循环去执行调用者的后续指令。这并非巧合，在真实的 CPU 中正是这样执行函数调用的。

当执行 resume 时，解释器会递归地调用自身的主循环函数去执行恢复运行的协程，并利用此协程的栈实现调用和返回指令。

当协程执行 yield 调用时，将返回到前一个对解释器主循环函数的调用点，从而不再执行当前协程的后续指令。换句话说，任意时刻， Lua 都用 C 堆栈跟踪活动协程的栈。每次对 yield 的调用解释器都返回到上次执行 resume 的地方。

在某些程序语言中，实现协程的困难之处源于如何处理对外层局部变量的引用。因为一个协程中正在执行的函数可能是由另一个协程创建的，而该函数有可能引用另一个栈中的变量。这引出了一种被称为“仙人掌” 的结构。而flat 闭包的使用，完全避免了这个难题。

面向对象

提到Lua的面向对象，就少不了元表这个概念。

什么是元表，元方法

在Lua table中我们可以访问对应的key来得到value值，但是却无法对两个table进行操作。因此Lua 提供了元表(Metatable)，允许我们改变table的行为，每个行为关联了对应的元方法。通俗来说，元表就像是一个“操作指南”，里面包含了一系列操作的解决方案，例如__index方法就是定义了这个表在索引失败的情况下该怎么办，__add方法就是告诉table在相加的时候应该怎么做。这里面的__index，__add就是元方法。

实现面向对象的前提条件

Lua虚拟机从一个表中查询数据的过程：
如果查询对象是表，则尝试根据key在表中查询数据，若有则返回结果；若结果为空，且无__index成员，则返回空结果；若结果为空且有__index，则设查询对象为__index，进行下一层深度的查找；
若查询对象不是表，则尝试获取对象的metatale["__index"]（usedata可能有此成员），设为查询对象并进行下一层深度的查找；逐层深度向下查找，但有层数限制，超过则终止查找。

具体实现

基类Account

Account = {balance = 0}

function Account:new (o)
	o = o or {}
	setmetatable(o, self)//设置元表为自身
	self.__index = self//设置__index元方法为自身
	return o
end

function Account:deposit (v)
	self.balance = self.balance + v
end

function Account:withdraw (v)
	if v > self.balance then error"insufficient funds" end
	self.balance = self.balance - v
end

子类SpecialAccount

//此时代表SpecialAccount是Account的一个实例，即继承了Account所有内容
SpecialAccount = Account:new()
//SpecialAccount从Account继承了new方法
//new执行时，self指向SpecialAccount
//s的metable，__index是SpecialAccount
s = SpecialAccount:new{limit = 1000.00}//s继承了SpecialAccount
//在s中找不到deposit域，会到SpecialAccount找，然后到Account中找
s:deposit(100.00)
--------------------------------------------------------------------
//根据上面的描述，我们就可以在SpecialAccount中重写Account方法
function SpecialAccount:withdraw (v)
	if v - self.balance >= self:getLimit() then
		error"insufficient funds"
	end
	self.balance = self.balance - v
end

function SpecialAccount:getLimit ()
	return self.limit or 0
end

//调用方法 s:withdraw(200.00)，Lua 不会到 Account 中查找
//因为它第一次就在 SpecialAccount 中发现了新的 withdraw 方法
//由于 s.limit 等于 1000.00（记住我们创建 s 的时候初始化了这个值）
//程序执行了取款操作，s 的 balance 变成了负值
s:withdraw(200.00)