求值中的逻辑运算

上一节介绍了逻辑运算在条件判断中的应用。这一节介绍另外一个应用场景，即在求值时的处理。

上一节中，逻辑运算在 条件判断 场景中的语法分析过程可以分为两部分：

  • 处理逻辑运算本身，具体说就是在exp()函数中遇到and或or运算符后，生成对应的字节码并处理True和False跳转列表；

  • 在整条逻辑运算语句解析完毕后，把解析结果放到if等语句的条件判断场景中，首先终结True跳转列表，然后在block结束后终结False跳转列表。

而在本节要介绍的 求值 场景中，也是分为两部分：

  • 处理逻辑运算本身，这部分跟上一节完全一样；

  • 在整条逻辑运算语句解析完毕后，对语句求值，这就是本节中要介绍的部分。

如下图所示，上一节完成了(a)和(b)部分，本节在(a)的基础上，实现(c)部分。

  1.                                           +------------+
  2.                                      /--->| (b)条件判断 |
  3. +---------------+   ExpDesc::Test   |     +------------+
  4. | (a)处理逻辑运算 |------------------>+
  5. +---------------+                   |     +---------+
  6.                                      \--->| (c)求值  |
  7.                                           +---------+

结果类型

Lua中的逻辑运算跟C、Rust中的逻辑运算有所不同。C和Rust语言中逻辑运算的结果是布尔类型，只分真假，比如下面C语言代码：

  1.     int i=10, j=11;
  2.     printf("%d\n", i && j);  // 输出：1

会输出1，因为&&运算符会先把两个操作数转换为布尔类型（这个例子里都是true），然后再执行&&运算，结果是true，在C语言里就是1。而Rust语言更严格，强制要求&&的两个操作数都必须是布尔类型，那么结果自然也是布尔类型。

但是Lua中的逻辑运算的求值结果是最后一个 求值 的操作数。比如下面都是很常见的用法：

  • print(t and t.k)，先判断t是否存在，再对t求索引。如果t不存在那么就不用判断t.k了，所以结果就是t即nil；否则就是t.k。

  • print(t.k or 100)，索引表并提供默认值。先判断t中是否有k，如果有那么就不用判断100了，所以结果就是t.k；否则就是100。

  • print(v>0 and v or -v)，求绝对值。如果是正数则结果是v，否则就是-v。模拟C语言中的?:三元运算符。

求值规律

为了更清楚地理解“逻辑运算的求值结果是最后一个求值的操作数”这句话，下面通过一些例子展示。这里仍然用上一节开头的流程图为例。先看最基本的运算：

  1.  A and B                      X or Y
  3. +-------+                    +-------+
  4. |   A   +-False-\    /--True-+   X   |
  5. +---+---+       |    |       +---+---+
  6.     |True       |    |           |False
  7.     V           |    |           V
  8. +-------+       |    |       +-------+
  9. |   B   |       |    |       |   Y   |
  10. +---+---+       |    |       +---+---+
  11.     |<----------/    \---------->|
  12.     V                            V

左图中，如果A为False，则求值结果即为A；否则，对B求值，由于B是最后一个操作数，所以无需再做判断，B就是求值结果。

右图中，如果X为True，则求值结果即为X；否则，对Y求值，由于Y是最后一个操作数，所以无需再做判断，Y就是求值结果。

再来看几个复杂的例子：

  1. A and B and C               X or Y or Z                 (A and B) or Y               A and (X or Y)
  3. +-------+                    +-------+                    +-------+                    +-------+
  4. |   A   +-False-\    /--True-+   X   |                    |   A   |-False-\            |   A   +-False-\
  5. +---+---+       |    |       +---+---+                    +---+---+       |            +---+---+       |
  6.     |True       |    |           |False                       |True       |                |True       |
  7.     V           |    |           V                            V           |                V           |
  8. +-------+       |    |       +-------+                    +-------+       |            +-------+       |
  9. |   B   +-False>+    +<-True-+   Y   |            /--True-+   B   |       |    /--True-+   X   |       |
  10. +---+---+       |    |       +---+---+            |       +---+---+       |    |       +---+---+       |
  11.     |True       |    |           |False           |      False|<---------/     |           |False      |
  12.     V           |    |           V                |           V                |           V           |
  13. +-------+       |    |       +-------+            |       +-------+            |       +-------+       |
  14. |   C   |       |    |       |   Z   |            |       |   Y   |            |       |   Y   |       |
  15. +---+---+       |    |       +---+---+            |       +---+---+            |       +---+---+       |
  16.     |<---------/     \---------->|                \---------->|                \---------->|<---------/
  17.     V                            V                            V                            V

这里省略根据这4个图归纳总结的过程，直接给出求值的规则：

  1. 最后一个操作数无需判断，只要前面的判断没有跳过这最后的操作数，那么这最后的操作数就是最终的求值结果。比如上面第1个图中，如果A和B都是True，就会执行到C，那么C就是整条语句的求值结果。C本身是不需要再做判断的。

  2. 在语法分析阶段，整条逻辑运算语句解析结束后，没有被终结的跳转列表上的操作数都可能作为最终的求值结果。这个说法比较绕，下面举例说明。比如上面第1个图中，A和B的True跳转列表分别终结在B和C，但是False跳转列表都没有终结，那么A和B都可能是最终的求值结果，比如A如果是False那么A就是最终求值结果。再举个反例，比如上面第3个图中的A的True和False两个跳转列表分别终结在B和Y，也就是说在整条语句解析完毕的时候，A的跳转列表都终结了，那么A就不可能是求值结果，无论哪种情况A都不会走到语句结尾。除了这第3个图以外其他图中的所有判断条件都可能作为最终的求值结果。

总结出求值的规则后，下面开始编码实现。

ExpDesc

上一节中引入了表示逻辑运算的新ExpDesc类型，定义如下：

  1. enum ExpDesc {
  2.     Test(usize, Vec<usize>, Vec<usize>), // (condition, true-list, false-list)

后面两个参数分别表示两个跳转链表，这里不做介绍，主要关注第一个参数：判断条件语句在栈上的位置。上一节中说过，所有的语句（比如变量、常量、表索引等）要判断真假，都要先discharge到栈上，所以这里使用usize类型的栈索引表示语句即可。这在上一节里是没问题的，但是在这一节里的求值场景下，如上面所述，最后一个操作数是无需判断的，所以就可能不需要discharge到栈上。比如下面的例子：

  1. local x = t and t.k

按照现在的做法，是先把后面第2个操作数t.k discharge到栈上临时变量；如果t为真，则通过Move字节码把临时变量赋值给x。很明显这个临时变量是不需要的，是可以把t.k直接赋值给x的。为此，我们需要对条件语句延迟求值，或者说延迟discharge。那么就需要改造ExpDesc::Test类型。

Lua官方的做法是，给ExpDesc的所有类型都配上两个跳转列表：

  1. typedef struct expdesc {
  2.   expkind k;  // 类型tag
  3.   union {
  4.     // 各种expkind关联的数据，这里省略
  5.   } u;
  6.   int t;  /* patch list of 'exit when true' */
  7.   int f;  /* patch list of 'exit when false' */
  8. } expdesc;

上述代码中的t和f分别是True和False的跳转列表。但是在Rust语言中也这么定义的话，就有点不方便。因为Rust的enum是包括了tag和关联数据的，对应上面的k和u，本来一个enum就可以定义ExpDesc；但如果增加两个跳转列表，就需要再在外面封装一层struct定义了。而且Rust语言中定义struct变量时必须显式初始化所有成员，那么现在代码里所有定义ExpDesc的地方，都要初始化t和f为Vec::new()。为了这一个类型而影响其他类型，实在不值得。

我们的做法是递归定义。把ExpDesc::Test的第一个参数类型，从usize修改为ExpDesc。当然不能直接定义，而是需要封装一层Box指针：

  1. enum ExpDesc {
  2.     Test(Box<ExpDesc>, Vec<usize>, Vec<usize>), // (condition, true-list, false-list)

这么定义，对现有代码中其他类型的ExpDesc完全没有影响。对现有代码中的Test类型，也只需要去掉discharge的处理即可。

字节码

上一节中新增的两个字节码TestAndJump和TestOrJump的功能都是：“测试”+“跳转”。而我们现在需要的功能是：“测试”+“赋值”+“跳转”。为此，我们再新增2个字节码：

  1. pub enum ByteCode {
  2.     Jump(i16),
  3.     TestAndJump(u8, i16),
  4.     TestOrJump(u8, i16),
  5.     TestAndSetJump(u8, u8, u8), // 新增
  6.     TestOrSetJump(u8, u8, u8),  // 新增

TestAndSetJump的功能是：如果测试第1个参数的栈索引的值为真，则赋值到第2个参数的栈位置，并跳转到第3个参数的字节码位置。TestOrSetJump的类似。

这里带来一个问题。之前的跳转字节码（上面代码中的前3个）中，跳转参数都是2个字节，i16类型，可以跳转范围很大。而新增的2个字节码都关联了3个参数，那么留给跳转参数的只剩一个字节了。

这也就是为什么上一节中提到的，Lua官方实现中，用了2个字节码来表示条件跳转指令。比如跟TestAndJump(t, jmp)相对的，就是 TEST(t, 0); JUMP(jmp)；而本节介绍的求值场景中，需要新增一个目标地址参数dst，就是TESTSET(dst, t, 0); JUMP(jmp)。这样就保证跳转参数有2个字节空间。并且，虽然是2条字节码，但是在虚拟机执行过程中，在执行到TEST或TESTSET字节码时，如果需要跳转，那么可以直接取下一条字节码JUMP的参数并执行跳转，而无需再为JUMP执行一次指令分发。相当于是1条字节码，而JUMP只是作为扩展参数，所以并不影响执行时的性能。

但我们这里仍然使用1条字节码，并使用1个字节来表示跳转参数。上一节的条件判断场景中，最后一个操作数的判断是要跳转到整个block结尾处，跳转距离可能很长，是需要2字节空间的。而本节的求值场景中，只是在逻辑运算语句内部跳转，可以参考上面的6个图，跳转距离不会很长；而且由于只会向前跳转，无需表示负数。所以1个字节u8类型表示256距离足够覆盖。条件允许的情况下，1条字节码总归是比2条要好的。

语法分析

介绍完上面的修改点后，现在开始语法分析。所谓求值，就是discharge。所以只需要完成discharge()函数中ExpDesc::Test类型即可。上一节中，这里是没有完成的。具体的discharge方法是：先discharge递归定义的条件语句，然后修复两条跳转列表中的判断字节码。

  1.     fn discharge(&mut self, dst: usize, desc: ExpDesc) {
  2.         let code = match desc {
  3.             // 省略其他类型
  4.             ExpDesc::Test(condition, true_list, false_list) => {
  5.                 // fix TestSet list after discharging
  6.                 self.discharge(dst, *condition); // 先discharge递归定义的条件语句
  7.                 self.fix_test_set_list(true_list, dst); // 修复True跳转列表中的判断字节码
  8.                 self.fix_test_set_list(false_list, dst); // 修复False跳转列表中的判断字节码
  9.                 return;
  10.             }

修复跳转列表fix_test_set_list()函数需要做2件事情：

  • 填充之前留空的跳转参数；
  • 把之前生成的TestAndJump和TestOrJump字节码，分别替换为TestAndSetJump和TestOrSetJump。

具体代码如下：

  1.     fn fix_test_set_list(&mut self, list: Vec<usize>, dst: usize) {
  2.         let here = self.byte_codes.len();
  3.         let dst = dst as u8;
  4.         for i in list.into_iter() {
  5.             let jmp = here - i - 1; // should not be negative
  6.             let code = match self.byte_codes[i] {
  7.                 ByteCode::TestOrJump(icondition, 0) =>
  8.                     if icondition == dst { // 如果条件语句刚好就在目标位置，就不需要改为TestAndSetJump
  9.                         ByteCode::TestOrJump(icondition, jmp as i16)
  10.                     } else { // 修改为TestAndSetJump字节码
  11.                         ByteCode::TestOrSetJump(dst as u8, icondition, jmp as u8)
  12.                     }
  13.                 ByteCode::TestAndJump(icondition, 0) =>
  14.                     if icondition == dst {
  15.                         ByteCode::TestAndJump(icondition, jmp as i16)
  16.                     } else {
  17.                         ByteCode::TestAndSetJump(dst as u8, icondition, jmp as u8)
  18.                     }
  19.                 _ => panic!("invalid Test"),
  20.             };
  21.             self.byte_codes[i] = code;
  22.         }
  23.     }

测试

至此，完成了逻辑运算在求值中的应用场景。可以通过本节开头的几个图中的例子来测试。这里省略。