表的构造

本节介绍表的构造。表的构造支持3种类型：列表式、记录式、和通用式。分别见如下示例代码：

  1. local key = "kkk"
  2. print { 100, 200, 300;  -- list style
  3.         x="hello", y="world";  -- record style
  4.         [key]="vvv";  -- general style
  5. }

先来看下Lua官方实现中是如何处理表的构造的。luac的输出如下：

  1. $ luac -l test_lua/table.lua
  3. main <test_lua/table.lua:0,0> (14 instructions at 0x600001820080)
  4. 0+ params, 6 slots, 1 upvalue, 1 local, 7 constants, 0 functions
  5.     1    [1]    VARARGPREP    0
  6.     2    [1]    LOADK        0 0    ; "kkk"
  7.     3    [2]    GETTABUP     1 0 1    ; _ENV "print"
  8.     4    [2]    NEWTABLE     2 3 3    ; 3
  9.     5    [2]    EXTRAARG     0
  10.     6    [2]    LOADI        3 100
  11.     7    [2]    LOADI        4 200
  12.     8    [2]    LOADI        5 300
  13.     9    [3]    SETFIELD     2 2 3k    ; "x" "hello"
  14.     10    [3]    SETFIELD     2 4 5k    ; "y" "world"
  15.     11    [4]    SETTABLE     2 0 6k    ; "vvv"
  16.     12    [5]    SETLIST      2 3 0
  17.     13    [2]    CALL         1 2 1    ; 1 in 0 out
  18.     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行加载到栈上的数据，一次性插入到数组中。

每个字节码的执行对应的栈情况如下：

  1.            |       |        /<--- 9.SETFILED
  2.            +-------+        |<---10.SETFILED
  3. 4.NEWTABLE |  { }  |<----+--+<---11.SETTABLE
  4.            +-------+     |
  5.    6.LOADI |  100  |---->|
  6.            +-------+     |12.SETLIST
  7.    7.LOADI |  200  |---->|
  8.            +-------+     |
  9.    8.LOADI |  300  |---->/
  10.            +-------+
  11.            |       |

首先可以看到，表的构造是在虚拟机执行过程中，通过插入逐个成员，实时构造出来的。这一点有点出乎我的意料（虽然之前并没有想过应该是什么过程）。我以前写过类似如下的代码：

  1. local function day_of_week(day)
  2.     local days = {
  3.         "Sunday"=0, "Monday"=1, "Tuesday"=2,
  4.         "Wednesday"=3, "Thursday"=4, "Friday"=5,
  5.         "Saturday"=6,
  6.     }
  7.     return days[day]
  8. 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个字节码：

  1. pub enum ByteCode {
  2.     NewTable(u8, u8, u8),
  3.     SetTable(u8, u8, u8),  // key在栈上
  4.     SetField(u8, u8, u8),  // key是字符串常量
  5.     SetList(u8, u8),

不过中间的两个字节码并不支持值是常量的情况，只支持栈上索引。我们在后面小节会加入对常量的优化。

语法分析

在介绍完表构造的原理后，现在来看具体实现。先看语法分析部分。代码很长，但都只是依照上面的介绍，逻辑很简单。把代码贴在这里仅作参考，没兴趣的读者可以跳过这里。

  1. fn table_constructor(&mut self, dst: usize) {
  2.     let table = dst as u8;
  3.     let inew = self.byte_codes.len();
  4.     self.byte_codes.push(ByteCode::NewTable(table, 0, 0));  // 新建表
  6.     let mut narray = 0;
  7.     let mut nmap = 0;
  8.     let mut sp = dst + 1;
  9.     loop {
  10.         match self.lex.peek() {
  11.             Token::CurlyR => { // `}`
  12.                 self.lex.next();
  13.                 break;
  14.             }
  15.             Token::SqurL => { // `[` exp `]` `=` exp，通用式
  16.                 nmap += 1;
  17.                 self.lex.next();
  19.                 self.load_exp(sp); // key
  20.                 self.lex.expect(Token::SqurR); // `]`
  21.                 self.lex.expect(Token::Assign); // `=`
  22.                 self.load_exp(sp + 1); // value
  24.                 self.byte_codes.push(ByteCode::SetTable(table, sp as u8, sp as u8 + 1));
  25.             },
  26.             Token::Name(_) => { // Name `=` exp | Name
  27.                 nmap += 1;
  28.                 let key = if let Token::Name(key) = self.lex.next() {
  29.                     self.add_const(key)
  30.                 };
  31.                 if self.lex.peek() == &Token::Assign { // Name `=` exp，记录式
  32.                     self.lex.next();
  33.                     self.load_exp(sp); // value
  34.                     self.byte_codes.push(ByteCode::SetField(table, key as u8, sp as u8));
  35.                 } else {
  36.                     narray += 1;
  37.                     self.load_exp_with_ahead(sp, Token::Name(key)); // exp，列表式
  39.                     sp += 1;
  40.                     if sp - (dst + 1) > 50 { // too many, reset it
  41.                         self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
  42.                         sp = dst + 1;
  43.                     }
  44.                 }
  45.             },
  46.             _ => { // exp，列表式
  47.                 narray += 1;
  48.                 self.load_exp(sp);
  50.                 sp += 1;
  51.                 if sp - (dst + 1) > 50 { // too many, reset it
  52.                     self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
  53.                     sp = dst + 1;
  54.                 }
  55.             },
  56.         }
  58.         match self.lex.next() {
  59.             Token::SemiColon | Token::Comma => (),
  60.             Token::CurlyR => break,
  61.             t => panic!("invalid table {t:?}"),
  62.         }
  63.     }
  65.     if sp > dst + 1 {
  66.         self.byte_codes.push(ByteCode::SetList(table, (sp - (dst + 1)) as u8));
  67.     }
  69.     // reset narray and nmap
  70.     self.byte_codes[inew] = ByteCode::NewTable(table, narray, nmap);
  71. }

函数开头生成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个字节码的虚拟机执行代码，同样很简单，可以跳过：

  1.     ByteCode::NewTable(dst, narray, nmap) => {
  2.         let table = Table::new(narray as usize, nmap as usize);
  3.         self.set_stack(dst, Value::Table(Rc::new(RefCell::new(table))));
  4.     }
  5.     ByteCode::SetTable(table, key, value) => {
  6.         let key = self.stack[key as usize].clone();
  7.         let value = self.stack[value as usize].clone();
  8.         if let Value::Table(table) = &self.stack[table as usize] {
  9.             table.borrow_mut().map.insert(key, value);
  10.         } else {
  11.             panic!("not table");
  12.         }
  13.     }
  14.     ByteCode::SetField(table, key, value) => {
  15.         let key = proto.constants[key as usize].clone();
  16.         let value = self.stack[value as usize].clone();
  17.         if let Value::Table(table) = &self.stack[table as usize] {
  18.             table.borrow_mut().map.insert(key, value);
  19.         } else {
  20.             panic!("not table");
  21.         }
  22.     }
  23.     ByteCode::SetList(table, n) => {
  24.         let ivalue = table as usize + 1;
  25.         if let Value::Table(table) = self.stack[table as usize].clone() {
  26.             let values = self.stack.drain(ivalue .. ivalue + n as usize);
  27.             table.borrow_mut().array.extend(values);
  28.         } else {
  29.             panic!("not table");
  30.         }
  31.     }

第一个字节码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()彻底杜绝了这个隐患，是值得的。

至此，我们完成了表的构造，后面几节介绍表的读写。