字符串定义
这节暂时不添加新功能，而是停下来讨论和优化字符串类型。
《Rust程序设计语言》书中所有权一节以字符串为例介绍了堆和栈的概念，以及其和所有权的关系；在字符串String一节提到了Rust的字符串是复杂的。我们现在就通过字符串来探索Rust对堆和栈的分配，并初步体验字符串的复杂。
堆和栈
《Rust程序设计语言》中以字符串为例介绍了堆和栈的概念，以及堆栈与所有权之间的关系。这里简单复述一遍。Rust的String包括两部分：
- 元数据，一般位于栈上，包括3个字段：指向内存块的指针、字符串长度、内存块的容量。下面分别用
buffer、len和cap表示。 - 用来存储字符串内容的私有内存块，在堆上申请。由字符串拥有，所以在字符串结束时被释放。正因为拥有堆上的这块内存，所以String就不是
Copy的，进而导致Value不是Copy的。为了复制Value就只能将其定义为Clone的。
比如内容为"hello, world!"的String，内存布局如下。左边是栈上的元数据，其中buffer指向堆上的内存块，len为字符串的长度，是13，cap为内存块的容量，很有可能对齐为16。右边是位于堆上的存储字符串内容的内存块。
栈 堆
+--------+
| buffer +------->+----------------+
|--------| |hello, world! |
| len=13 | +----------------+
|--------|
| cap=16 |
+--------+
这里需要说明的是，上面说元数据“一般”位于栈上，是对于简单类型而言。但对于复杂点的类型，比如Vec<String>，那String元数据部分作为数组的内容就也存在堆上了（类似String的内存块部分）。下面就是一个有2个字符串成员的数组Vec。数组本身的元数据在栈上，但字符串的元数据就在堆上了。
栈 堆
+--------+
| buffer +------->+-------------+-------------+----
|--------| | buf|len|cap | buf|len|cap | ...
| len=2 | +--+----------+--+----------+----
|--------| | V
| cap=4 | V +----------------+
+--------+ +--------+ |hello, world! |
|print | +----------------+
+--------+
这种情况下，元数据数组部分虽然是在堆上，但是仍然有栈的特点，包括后进先出，通过索引快速访问，固定已知大小，无需管理（申请和释放）。事实上，我们Lua解释器的虚拟机的栈是就是类似的Vec<Value>类型。同样的，其数据虽然是在堆上，但有栈的特点。“栈”这个名词在这里有2个意思：Rust层面的栈，和Lua虚拟机的栈。后者是位于Rust层面的堆上。本文下面所讲到的“栈”，都是后一种意思，即Lua虚拟机的栈。不过当成Rust的栈去理解，也不影响。
使用String
目前Value的字符串类型是直接使用的Rust标准库中的字符串String：
#[derive(Clone)]
struct Value {
String(String),
这样定义的最大问题是，如果要复制一个字符串的Value，就要深度复制字符串，即Clone。下图表示了复制一个字符串的内存布局：
栈 堆
| |
+--------+
|t| |
|-+------|
| buffer +------->+----------------+
|--------| |hello, world! |
| len=13 | +----------------+
|--------|
| cap=16 |
+--------+
: :
: :
+--------+
|t| |
|-+------|
| buffer +------->+----------------+
|--------| |hello, world! |
| len=13 | +----------------+
|--------|
| cap=16 |
+--------+
| |
图中左边是Lua虚拟机的栈，每行代表一个字。由于我们基于64位系统开发，所以一个字是8字节。
第1行的t代表enum Value的tag。由于我们的Value类型小于256种，1个字节就可以表示，所以t占用1个字节。紧接着的3行buffer、len和cap构成一个Rust标准库的String。每个字段都占用一个字。buffer是8字节对齐，所以跟t之间就空了7个字节，这部分是空洞，不可用。这4行（图中四个+包围起来的矩形）总共构成一个字符串类型的Value。
Rust中并没有规定enum的默认布局（虽然可以指定）。我们这里只是列出一种布局的可能性。这并不影响本节的讨论。
深度复制这个字符串Value，就需要复制栈上的元数据和堆上的内存块，对性能和内存都是很大的浪费。Rust中解决这个问题最直接的方法就是使用Rc。
使用Rc<String>
为了快速复制字符串String，就需要允许字符串同时存在多个所有者。Rust的Rc提供了这个特性。在String外面封装Rc，在复制时只需要更新Rc计数即可。定义如下：
#[derive(Clone)]
struct Value {
String(Rc<String>),
内存布局如下：
栈 堆
| |
+--------+
|t| |
|-+------|
| Rc +----+-->+--------+--------+--------+--------+--------+
+--------+ | |count=2 | weak=0 | buffer | len=13 | cap=16 |
: : | +--------+--------+-+------+--------+--------+
: : | |
+--------+ | V
|t| | | +----------------+
|-+------| | |hello, world! |
| Rc +----/ +----------------+
+--------+
| |
图中右边的count和weak就是Rc的封装。由于当前有2个Value指向这个字符串，所以count为2。
使用Rc，直接导致了这个解释器要使用引用计数法来实现垃圾回收。在下面小节中会专门讨论这个影响重大的决定。
这个方案虽然解决了复制的问题，但也带来了一个新问题，就是访问字符串的内容需要2次指针跳转。这会浪费内存并影响执行性能。下面介绍一些优化方案。
使用Rc<str>
Lua中的字符串有个特点，是只读的！如果要对字符串做处理，比如截断、连接、替换等，都会生成新的字符串。而Rust的String是为可变字符串设计的，所以用来表示只读字符串有点浪费，比如可以省掉元数据里的cap字段，也不用为了可能的修改而预留内存。比如上述例子里，"hello, world!"长度只有13，但申请了16的内存块。Rust中更适合表示只读字符串的是&str，即String的slice。但&str是个引用，并没有对字符串的所有权，而需要依附在某个字符串上。不过它有不是字符串String的引用（字符串的引用是&String），直观看上去，应该是str的引用。那str是个什么？好像从来没有单独出现过。
举例说明。对于如下代码：
let s = String::from("hello, world!"); // String
let r = s[7..12]; // &str
其中r是&str类型，内存布局如下：
栈 堆
s: +--------+
| buffer +------->+----------------+
|--------| |hello, world! |
| len=13 | +-------^--------+
|--------| |
| cap=16 | |
+--------+ |
|
r: +--------+ |
| buffer +----------------/
|--------|
| len=5 |
+--------+
那对&str解引用，得到的就是"world"这段内存。不过一般的引用就是个地址，但这里还附加了长度信息，说明str除了内存，还包括了长度信息。只不过这个长度信息并不像String那样在原始数据上，而是跟随引用在一起。事实上，str确实不能独立存在，必须跟随引用（比如&str）或者指针（比如Box(str)）。这种属于动态大小类型。
而Rc也是一种指针，所以就可以定义Rc<str>。定义如下：
#[derive(Clone)]
struct Value {
String(Rc<str>),
内存布局如下：
栈 堆
| |
+--------+
|t| |
|-+------|
| Rc +----+-->+--------+--------+-------------+
|--------| | |count=2 | weak=0 |hello, world!|
| len=13 | | +--------+--------+-------------+
+--------+ |
: : |
: : |
+--------+ |
|t| | |
|-+------| |
| Rc +----/
+--------+
| len=13 |
+--------+
| |
其中"hello, world!"是原始数据，被Rc封装。而长度信息len=13跟随Rc一起存储在栈上。
这个方案看上去非常好！相对于上面的Rc<String>方案，这个方案去掉了没用的cap字段，无需预留内存，而且还省去了一层指针跳转。但这个方案也有2个问题：
首先，创建字符串时需要复制内容。之前的方案只需要复制字符串的元数据部分即可，只有3个字的长度。而这个方案要把字符串内容复制到新创建的Rc包内。想象要创建一个1M长的字符串，这个复制就很影响性能了。
其次，就是在栈上占用2个字的空间。虽然在最早的直接使用String的方案里占用3个字的空间，问题更严重，但是可以理解为我们现在的标准提高了。目前，Value里的其他类型都最多只占用1个字（加上tag就一共是2个字），可以剧透的是后续要增加的表、UserData等类型也都只占用1个字，所以如果单独因为字符串类型而让Value的大小从2变成3，那就是浪费了。不仅占用更多内存，而且还对CPU缓存不友好。
这个问题的关键就在于len跟随Rc一起，而不是跟随数据一起。如果能把len放到堆上，比如在图中weak和"hello, world!"之间，那就完美了。对于C语言这是很简单的，但Rust并不支持。原因在于str是动态大小类型。那如果选一个固定大小类型的，是不是就可以实现？比如数组。
使用Rc<(u8, [u8; 47])>
Rust中的数组是有内在的大小信息的，比如[u8; 10]和[u8; 20]的大小就分别是10和20，这个长度是编译时期就知道的，无需跟随指针存储。两个长度不同的数组就是不同的类型，比如[u8; 10]和[u8; 20]就是不同的类型。所以数组是固定大小类型，可以解决上一小节的问题，也就是栈上只需要1个word即可。
既然是固定长度，那就只能存储小于这个长度的字符串，所以这个方案不完整，只能是是一个性能优化的补充方案。不过Lua中遇到的字符串大部分都很短，至少我的经验如此，所以这个优化还是很有意义的。为此我们需要定义2种字符串类型，一个是固定长度数组，用于优化短字符串，另一个是之前的Rc<String>方案，用于存储长字符串。固定长度数组的第一个字节用来表示字符串的实际长度，所以数组可以拆成2部分。我们先假设使用总长度48的数组（1个字节表示长度，47个字节存储字符串内容），则定义如下：
struct Value {
FixStr(Rc<(u8, [u8; 47])>), // len<=47
String(Rc<String>), // len>47
短字符串的内存布局如下：
栈 堆
| |
+--------+
|t| |
|-+------|
| Rc +----+-->+--------+--------+----------------------------+
+--------+ | |count=2 | weak=0 |len|hello, world! |
: : | +--------+--------+----------------------------+
: : |
+--------+ |
|t| | |
|-+------| |
| Rc +----/
+--------+
| |
图中右边的数组部分开头第一个字节len表示后面字符串的实际长度。后面的47个字节可以用于存储字符串内容。
这个方案跟上述的Rc<str>一样，都需要复制字符串内容，所以不适合长字符串。这个问题不大，本来这个方案就是为了优化短字符串的。然后即便是短字符串，数组长度的选取也很关键。如果很长，则对短字符串而言空间浪费严重；如果很短，则覆盖比例不高。不过在这个方案上还可以继续优化，采用多级长度的数组，比如16、32、48、64等。不过这也会造成一些复杂性。
另外，数组长度的选取还依赖Rust使用的内存管理库。比如我们选择长度为48，加上Rc封装的2个计数字段16字节，那么上图中右边堆上的内存块长度为64字节，是个很“规整”的长度。比如内存管理库jemalloc对小内存块的管理就是分为16、32、48、64、128等长度，那么上述总长度64的内存申请就没有浪费。假如我们选择数组长度为40，内存块总长度就是56，仍然会匹配到64的分类中，就会浪费64-56=8字节。当然，依赖其他库的具体实现来做决定，这是很不好的行为，不过好在这个影响并不大。
我们这里选择数组长度为48，也就是只能表示长度从0到47的字符串。
然后跟Rc<String>方案对比下，看看优化效果如何。首先，这个方案最大的优点是只需一次内存分配，在执行时也就只需一次指针跳转。
其次，对比下分配的内存大小。在Rc<String>方案中需要申请2块内存：一是Rc计数和字符串元数据，固定2+3=5个字，40字节，按照jemalloc的内存策略，会占用48字节内存；二是字符串内容部分，所占内存大小跟字符串长度相关，也取决于Rust String的内存管理策略和底层库的实现，比如对于长度为1的字符串，可能占用16字节内存；对于长度为47的字符串，可能占用48字节，也可能占用64字节内存。两块内存加起来要占用64到112字节，大于或等于这个固定长度数组的方案。
我们沿着“优化短字符串”的思路，看下一个方案。
使用内联数组
上一个方案相对于Rc<String>而言减少了一层指针跳转。下面这个方案更进一步，直接去掉堆上存储，而把字符串完全存储在栈上。
我们希望Value类型的大小是2个字，即16个字节。其中1个用于tag，1个用于字符串长度，那么就还有14个字节的剩余，这部分空间可以用来存储长度小于14的字符串。这个方案跟上一个一样，也是补充方案，也要跟一个长字符串定义配合使用。具体如下：
// sizeof(Value) - 1(tag) - 1(len)
const INLSTR_MAX: usize = 14;
struct Value {
InlineStr(u8, [u8; INLSTR_MAX]), // len<=14
String(Rc<String>), // len>14
其中短字符串InlineStr关联两个参数：u8类型的字符串长度，和长度为14的u8数组，这也充分利用了之前一直被浪费的t后面7个字节的空洞。而长字符串String仍然使用Rc<String>方案。
短字符串的内存布局如下：
栈
| |
+vv------+
|tlhello,|
|--------|
| world! |
+--------+
: :
: :
+vv------+
|tlhello,|
|--------|
| world! |
+--------+
| |
其中格子上的箭头v指向的t和l分别代表1个字节的tag和长度。实际的字符串内容跨了2个字。如果横着画栈，看上去更清晰些：
栈：
--+-+-+--------------+......+-+-+--------------+--
|t|l|hello, world! | |t|l|hello, world! |
--+------------------+......+------------------+--
这个方案性能最优，但能力最差，只能处理长度不大于14的字符串。Lua中字符串类型的使用场景有3个：全局变量名、表索引、和字符串值。前两者绝大部分的都不大于14字节，所以应该可以覆盖大部分情况。
还可以再进一步优化，再增加一种类型，专门存储长度为15的字符串，因为长度已知，所以原来存储长度的一个字节也可以用来存储字符串内容。但这个方案带来的优化感觉不明显，小于带来的复杂度，所以不采用。定义如下。
struct Value {
InlineStr(u8, [u8; INLSTR_MAX]), // len<=14
Len15Str([u8; 15]), // len=15
String(Rc<String>), // len>15
总结和选择
这一节里，我们依次使用并分析了String、Rc<String>、Rc<str>、Rc<(u8, [u8; 47])>和内联(u8, [u8; 14])等几种方案。各有优缺点。合理的做法是区分对待长短字符串，用短字符串优化，用长字符串兜底。可选的3个方案：
- 为了保证
Value类型的长度，长字符串只能使用Rc<String>。 - 对于短字符串，最后的内联方案完全不用堆上内存，优化效果最好。
- 倒数第2个固定长度数组方案，属于上述两个方案的折中，略显鸡肋。不过缺点也只有一个，就是引入更大的复杂性，字符串需要处理3种类型。下一节通过泛型来屏蔽这3种类型，就解决了这个缺点。
最终方案如下：
const SHORT_STR_MAX: usize = 14; // sizeof(Value) - 1(tag) - 1(len)
const MID_STR_MAX: usize = 48 - 1;
struct Value {
ShortStr(u8, [u8; SHORT_STR_MAX]),
MidStr(Rc<(u8, [u8; MID_STR_MAX])>),
LongStr(Rc<Vec<u8>>),
原来的InlineStr和FixStr都是代表具体实现方案，而对外表现的特征就是长和短，所以改名为ShortStr、MidStr和LongStr，更直观。
这样，对于大部分情况（短字符串）可以快速处理，而对于小部分情况（长字符串）虽然慢但也可以正确处理，并且不影响全局（比如Rc<str>就占用了2个字，直接使得Value也变大，就算是影响了全局），最终提升整体的处理效率，这是很常见并且很有效的优化思路。我们这个方案通过区分2套定义实现优化，是个典型的例子。如果能不区分定义，而只用一套定义、一套算法就能达到这个目的，就更优美了。后面在赋值语句的语法分析时，会遇到这样的例子。
区分长短字符串后，也带来两个新问题：
-
生成字符串类型
Value时，要根据字符串长度来选择ShortStr、MidStr还是LongStr。这个选择应该是自动实现的，而不应该由调用者实现，否则一是麻烦二是可能出错。比如现在语法分析的代码中出现多次的self.add_const(Value::String(var))语句，就需要改进。 -
字符串，顾名思义是“字符”组成，但
ShortStr和MidStr都是由u8组成，区别在哪里？u8如何正确表达Unicode？如何处理非法字符？
接下来的几节讨论这两个问题。