表的构造
本节介绍表的构造。表的构造支持3种类型：列表式、记录式、和通用式。分别见如下示例代码：
local key = "kkk"
print { 100, 200, 300; -- list style
x="hello", y="world"; -- record style
[key]="vvv"; -- general style
}
先来看下Lua官方实现中是如何处理表的构造的。luac的输出如下：
$ luac -l test_lua/table.lua
main <test_lua/table.lua:0,0> (14 instructions at 0x600001820080)
0+ params, 6 slots, 1 upvalue, 1 local, 7 constants, 0 functions
1 [1] VARARGPREP 0
2 [1] LOADK 0 0 ; "kkk"
3 [2] GETTABUP 1 0 1 ; _ENV "print"
4 [2] NEWTABLE 2 3 3 ; 3
5 [2] EXTRAARG 0
6 [2] LOADI 3 100
7 [2] LOADI 4 200
8 [2] LOADI 5 300
9 [3] SETFIELD 2 2 3k ; "x" "hello"
10 [3] SETFIELD 2 4 5k ; "y" "world"
11 [4] SETTABLE 2 0 6k ; "vvv"
12 [5] SETLIST 2 3 0
13 [2] CALL 1 2 1 ; 1 in 0 out
14 [5] RETURN 1 1 1 ; 0 out
跟表的构造相关的字节码是第4到第12行：
- 第4行，NEWTABLE，用以创建一个表。一共3个参数，分别是新表在栈上位置，数组部分长度，和散列表部分长度。
- 第5行，看不懂，暂时忽略。
- 第6，7，8行，三个LOADI，分别加载数组部分的值100,200,300到栈上，供后面使用。
- 第9，10行，字节码SETFIELD，分别向散列表部分插入x和y。
- 第11行，字节码SETTABLE，向散列表部分插入key。
- 第12行，SETLIST，把上述第6-8行加载到栈上的数据，一次性插入到数组中。
每个字节码的执行对应的栈情况如下：
| | /<--- 9.SETFILED
+-------+ |<---10.SETFILED
4.NEWTABLE | { } |<----+--+<---11.SETTABLE
+-------+ |
6.LOADI | 100 |---->|
+-------+ |12.SETLIST
7.LOADI | 200 |---->|
+-------+ |
8.LOADI | 300 |---->/
+-------+
| |
首先可以看到，表的构造是在虚拟机执行过程中，通过插入逐个成员，实时构造出来的。这一点有点出乎我的意料（虽然之前并没有想过应该是什么过程）。我以前写过类似如下的代码：
local function day_of_week(day)
local days = {
"Sunday"=0, "Monday"=1, "Tuesday"=2,
"Wednesday"=3, "Thursday"=4, "Friday"=5,
"Saturday"=6,
}
return days[day]
end
代码中把days放在函数内部是很自然的，因为这个变量只在这个函数内部使用。但是根据上面表的构造的实现，每次调用这个函数都会实时构建这个表，也就是把这7个日期插入到表里，这个代价就有点大了（需要8次字符串hash和1次字符串比较，至少需要9条字节码，还有创建表带来的不止一次的内存分配）。感觉上甚至不如逐个星期名比较来的快（平均需要4次字符串比较，每次比较2条字节码一共8条）。更好的方法是把days这个变量放到函数外面（就是以后介绍的UpValue），每次进入函数就不需要构造表，但这样就把一个函数内部变量放到外面，不是好的编程习惯。另外一种做法（Lua的官方实现并不支持）就是对于这种全部由常量组成的表，在解析阶段就构建好，后续只要引用即可，但这么做会带来一些复杂性，后续看有没有精力完成。
回到表的构造，对于数组部分和散列表部分的处理方式是不同的：
- 数组部分，是先把值依次加载到栈上，最后一次性插入到数组中；
- 散列表部分，是每次直接插入到散列表中。
一个是批量的一个是逐次的。采用不同方式的原因猜测如下：
-
数组部分如果也逐一插入，那么插入某些类型的表达式就需要2条字节码。比如对于全局变量，就需要先用
GetGlobal字节码加载到栈上，然后再用一个类似AppendTable的字节码插入到数组中，那么插入N个值最多就需要2N条字节码。如果批量插入，N个值就只需要N+1条字节码。所以批量插入更适合数组部分。 -
而对于散列表部分，每条数据有key和value两个值，如果也采用批量的方式，把两个值都加载到栈上就需要2条字节码。而如果是逐个插入，很多情况下只需要1条字节码即可。比如上述示例代码中的后面3项都只分别对应1条字节码。这么一来，批量的方式反而需要更多字节码了，所以逐个插入更适合散列表部分。
这一节按照Lua官方实现方法，对应增加下面等4个字节码：
pub enum ByteCode {
NewTable(u8, u8, u8),
SetTable(u8, u8, u8), // key在栈上
SetField(u8, u8, u8), // key是字符串常量
SetList(u8, u8),
不过中间的两个字节码并不支持值是常量的情况，只支持栈上索引。我们在后面小节会加入对常量的优化。
语法分析
在介绍完表构造的原理后，现在来看具体实现。先看语法分析部分。代码很长，但都只是依照上面的介绍，逻辑很简单。把代码贴在这里仅作参考，没兴趣的读者可以跳过这里。
fn table_constructor(&mut self, dst: usize) {
let table = dst as u8;
let inew = self.byte_codes.len();
self.byte_codes.push(ByteCode::NewTable(table, 0, 0)); // 新建表
let mut narray = 0;
let mut nmap = 0;
let mut sp = dst + 1;
loop {
match self.lex.peek() {
Token::CurlyR => { // `}`
self.lex.next();
break;
}
Token::SqurL => { // `[` exp `]` `=` exp，通用式
nmap += 1;
self.lex.next();
self.load_exp(sp); // key
self.lex.expect(Token::SqurR); // `]`
self.lex.expect(Token::Assign); // `=`
self.load_exp(sp + 1); // value
self.byte_codes.push(ByteCode::SetTable(table, sp as u8, sp as u8 + 1));
},
Token::Name(_) => { // Name `=` exp | Name
nmap += 1;
let key = if let Token::Name(key) = self.lex.next() {
self.add_const(key)
};
if self.lex.peek() == &Token::Assign { // Name `=` exp，记录式
self.lex.next();
self.load_exp(sp); // value
self.byte_codes.push(ByteCode::SetField(table, key as u8, sp as u8));
} else {
narray += 1;
self.load_exp_with_ahead(sp, Token::Name(key)); // exp，列表式
sp += 1;
if sp - (dst + 1) > 50 { // too many, reset it
self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
sp = dst + 1;
}
}
},
_ => { // exp，列表式
narray += 1;
self.load_exp(sp);
sp += 1;
if sp - (dst + 1) > 50 { // too many, reset it
self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
sp = dst + 1;
}
},
}
match self.lex.next() {
Token::SemiColon | Token::Comma => (),
Token::CurlyR => break,
t => panic!("invalid table {t:?}"),
}
}
if sp > dst + 1 {
self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
}
// reset narray and nmap
self.byte_codes[inew] = ByteCode::NewTable(table, narray, nmap);
}
函数开头生成NewTable字节码，但由于目前还不知道数组和散列表的成员数量，所以后面两个参数暂时填0。并记下这个字节码的位置，在函数最后修改参数。
中间循环就是遍历表的所有成员。一共3种语法类型：
-
通用式，
[ exp ] = exp，key和value都是表达式，通过load_exp()函数分别加载到栈的sp和sp+1的位置，然后生成SetTable字节码； -
记录式，
Name = exp，key是Name即字符串常量，加入到常量表中，value是表达式，最后生成SetField字节码。这里有个地方跟Rust的所有权机制相关，就是通过match self.lex.peek()的模式分支Token::Name(key)匹配拿到的key是不能直接通过add_const(*key)添加到常量表中的。这是因为peek()返回的不是Token本身，而是Token的引用，这个引用是self.lex.peek()返回的，所以关联的self.lex和self也都处于被引用的状态；而调用self.add_const()也是对self的mut引用，就违反了引用规则。正确的做法是放弃peek()的返回值，而是调用self.lex.next()返回Token并重新匹配。这时Rust的检查显得过于严格，因为self.lex.peek()返回的Token引用并不会影响self.add_const()。应该是Rust没有能力确定这两者间没有影响。 -
列表式，
exp，加载到栈的sp位置，并更新sp，以待最后的SetList执行插入。但不能无限向栈上加载数据，因为这会导致栈一直重分配内存，所以如果当前栈上数据超过50，就生成一次SetList字节码，清理栈。
这里需要说明的一点是，在解析到Name的时候，既可能是记录式也可能是列表式，需要再peek下一个Token才能区分两者：如果下一个Token是=则是记录式，否则是列表式。这里的问题是，Name已经是peek的了，而词法分析由于使用了Peekable所以只支持peek一个Token，于是就只能修改表达式解析的函数load_exp()，支持一个提前读取的Token，为此新增load_exp_with_ahead()函数。整个Lua语法中，只有这一个地方需要向前看两个Token。
这种需要向前看两个Token才能确定表达式的行为，不知道是不是叫LL(2)？
虚拟机执行
下面是新增的4个字节码的虚拟机执行代码，同样很简单，可以跳过：
ByteCode::NewTable(dst, narray, nmap) => {
let table = Table::new(narray as usize, nmap as usize);
self.set_stack(dst, Value::Table(Rc::new(RefCell::new(table))));
}
ByteCode::SetTable(table, key, value) => {
let key = self.stack[key as usize].clone();
let value = self.stack[value as usize].clone();
if let Value::Table(table) = &self.stack[table as usize] {
table.borrow_mut().map.insert(key, value);
} else {
panic!("not table");
}
}
ByteCode::SetField(table, key, value) => {
let key = proto.constants[key as usize].clone();
let value = self.stack[value as usize].clone();
if let Value::Table(table) = &self.stack[table as usize] {
table.borrow_mut().map.insert(key, value);
} else {
panic!("not table");
}
}
ByteCode::SetList(table, n) => {
let ivalue = table as usize + 1;
if let Value::Table(table) = self.stack[table as usize].clone() {
let values = self.stack.drain(ivalue .. ivalue + n as usize);
table.borrow_mut().array.extend(values);
} else {
panic!("not table");
}
}
第一个字节码NewTable很简单，不做介绍。后面两个字节码SetTable和SetField类似，都需要通过borrow_mut()来获取表的mut引用。最后的字节码SetList再次遇到Rust的所有权问题，需要对栈上的表显式调用clone()函数，创建一个独立的表的指针。如果不调用clone()的话，那么第一行if let语句匹配得到的table变量是对栈上成员的引用，也就是对栈的引用，并且这个引用还需要持续到第三行，所以不能提前释放；第二行调用stack.drain()是需要获取栈的可变引用，就跟前面第一行table变量获取的引用出现冲突了。所以需要clone()出一个独立的表的指针，这样第一行匹配的table变量就只是对表的引用，而脱离了对栈的引用，从而避免了冲突。
这里强制的clone()增加了性能消耗，但也避免了潜在bug。比如这个table所在的栈位置，是可能被后续的stack.drain()包括的，从而地址失效，那么后续第三行向table中插入数据的操作就会异常。当然，在SetList这个场景下，语法分析会保证stack.drain()清理的栈位置不包括table，但Rust编译器并不知道，而且也不能保证以后不会包括。所以这里的clone()彻底杜绝了这个隐患，是值得的。
至此，我们完成了表的构造，后面几节介绍表的读写。