求值中的逻辑运算
上一节介绍了逻辑运算在条件判断中的应用。这一节介绍另外一个应用场景，即在求值时的处理。
上一节中，逻辑运算在 条件判断 场景中的语法分析过程可以分为两部分：
-
处理逻辑运算本身，具体说就是在
exp()函数中遇到and或or运算符后，生成对应的字节码并处理True和False跳转列表； -
在整条逻辑运算语句解析完毕后，把解析结果放到if等语句的条件判断场景中，首先终结True跳转列表，然后在block结束后终结False跳转列表。
而在本节要介绍的 求值 场景中，也是分为两部分：
-
处理逻辑运算本身，这部分跟上一节完全一样；
-
在整条逻辑运算语句解析完毕后，对语句求值，这就是本节中要介绍的部分。
如下图所示，上一节完成了(a)和(b)部分，本节在(a)的基础上，实现(c)部分。
+------------+
/--->| (b)条件判断 |
+---------------+ ExpDesc::Test | +------------+
| (a)处理逻辑运算 |------------------>+
+---------------+ | +---------+
\--->| (c)求值 |
+---------+
结果类型
Lua中的逻辑运算跟C、Rust中的逻辑运算有所不同。C和Rust语言中逻辑运算的结果是布尔类型，只分真假，比如下面C语言代码：
int i=10, j=11;
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语言中的?:三元运算符。
求值规律
为了更清楚地理解“逻辑运算的求值结果是最后一个求值的操作数”这句话，下面通过一些例子展示。这里仍然用上一节开头的流程图为例。先看最基本的运算：
A and B X or Y
+-------+ +-------+
| A +-False-\ /--True-+ X |
+---+---+ | | +---+---+
|True | | |False
V | | V
+-------+ | | +-------+
| B | | | | Y |
+---+---+ | | +---+---+
|<----------/ \---------->|
V V
左图中，如果A为False，则求值结果即为A；否则，对B求值，由于B是最后一个操作数，所以无需再做判断，B就是求值结果。
右图中，如果X为True，则求值结果即为X；否则，对Y求值，由于Y是最后一个操作数，所以无需再做判断，Y就是求值结果。
再来看几个复杂的例子：
A and B and C X or Y or Z (A and B) or Y A and (X or Y)
+-------+ +-------+ +-------+ +-------+
| A +-False-\ /--True-+ X | | A |-False-\ | A +-False-\
+---+---+ | | +---+---+ +---+---+ | +---+---+ |
|True | | |False |True | |True |
V | | V V | V |
+-------+ | | +-------+ +-------+ | +-------+ |
| B +-False>+ +<-True-+ Y | /--True-+ B | | /--True-+ X | |
+---+---+ | | +---+---+ | +---+---+ | | +---+---+ |
|True | | |False | False|<---------/ | |False |
V | | V | V | V |
+-------+ | | +-------+ | +-------+ | +-------+ |
| C | | | | Z | | | Y | | | Y | |
+---+---+ | | +---+---+ | +---+---+ | +---+---+ |
|<---------/ \---------->| \---------->| \---------->|<---------/
V V V V
这里省略根据这4个图归纳总结的过程，直接给出求值的规则：
-
最后一个操作数无需判断，只要前面的判断没有跳过这最后的操作数，那么这最后的操作数就是最终的求值结果。比如上面第1个图中，如果A和B都是True，就会执行到C，那么C就是整条语句的求值结果。C本身是不需要再做判断的。
-
在语法分析阶段，整条逻辑运算语句解析结束后，没有被终结的跳转列表上的操作数都可能作为最终的求值结果。这个说法比较绕，下面举例说明。比如上面第1个图中，A和B的True跳转列表分别终结在B和C，但是False跳转列表都没有终结，那么A和B都可能是最终的求值结果，比如A如果是False那么A就是最终求值结果。再举个反例，比如上面第3个图中的A的True和False两个跳转列表分别终结在B和Y，也就是说在整条语句解析完毕的时候，A的跳转列表都终结了，那么A就不可能是求值结果，无论哪种情况A都不会走到语句结尾。除了这第3个图以外其他图中的所有判断条件都可能作为最终的求值结果。
总结出求值的规则后，下面开始编码实现。
ExpDesc
上一节中引入了表示逻辑运算的新ExpDesc类型，定义如下：
enum ExpDesc {
Test(usize, Vec<usize>, Vec<usize>), // (condition, true-list, false-list)
后面两个参数分别表示两个跳转链表，这里不做介绍，主要关注第一个参数：判断条件语句在栈上的位置。上一节中说过，所有的语句（比如变量、常量、表索引等）要判断真假，都要先discharge到栈上，所以这里使用usize类型的栈索引表示语句即可。这在上一节里是没问题的，但是在这一节里的求值场景下，如上面所述，最后一个操作数是无需判断的，所以就可能不需要discharge到栈上。比如下面的例子：
local x = t and t.k
按照现在的做法，是先把后面第2个操作数t.k discharge到栈上临时变量；如果t为真，则通过Move字节码把临时变量赋值给x。很明显这个临时变量是不需要的，是可以把t.k直接赋值给x的。为此，我们需要对条件语句延迟求值，或者说延迟discharge。那么就需要改造ExpDesc::Test类型。
Lua官方的做法是，给ExpDesc的所有类型都配上两个跳转列表：
typedef struct expdesc {
expkind k; // 类型tag
union {
// 各种expkind关联的数据，这里省略
} u;
int t; /* patch list of 'exit when true' */
int f; /* patch list of 'exit when false' */
} 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指针：
enum ExpDesc {
Test(Box<ExpDesc>, Vec<usize>, Vec<usize>), // (condition, true-list, false-list)
这么定义，对现有代码中其他类型的ExpDesc完全没有影响。对现有代码中的Test类型，也只需要去掉discharge的处理即可。
字节码
上一节中新增的两个字节码TestAndJump和TestOrJump的功能都是：“测试”+“跳转”。而我们现在需要的功能是：“测试”+“赋值”+“跳转”。为此，我们再新增2个字节码：
pub enum ByteCode {
Jump(i16),
TestAndJump(u8, i16),
TestOrJump(u8, i16),
TestAndSetJump(u8, u8, u8), // 新增
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递归定义的条件语句，然后修复两条跳转列表中的判断字节码。
fn discharge(&mut self, dst: usize, desc: ExpDesc) {
let code = match desc {
// 省略其他类型
ExpDesc::Test(condition, true_list, false_list) => {
// fix TestSet list after discharging
self.discharge(dst, *condition); // 先discharge递归定义的条件语句
self.fix_test_set_list(true_list, dst); // 修复True跳转列表中的判断字节码
self.fix_test_set_list(false_list, dst); // 修复False跳转列表中的判断字节码
return;
}
修复跳转列表fix_test_set_list()函数需要做2件事情：
- 填充之前留空的跳转参数；
- 把之前生成的
TestAndJump和TestOrJump字节码，分别替换为TestAndSetJump和TestOrSetJump。
具体代码如下：
fn fix_test_set_list(&mut self, list: Vec<usize>, dst: usize) {
let here = self.byte_codes.len();
let dst = dst as u8;
for i in list.into_iter() {
let jmp = here - i - 1; // should not be negative
let code = match self.byte_codes[i] {
ByteCode::TestOrJump(icondition, 0) =>
if icondition == dst { // 如果条件语句刚好就在目标位置，就不需要改为TestAndSetJump
ByteCode::TestOrJump(icondition, jmp as i16)
} else { // 修改为TestAndSetJump字节码
ByteCode::TestOrSetJump(dst as u8, icondition, jmp as u8)
}
ByteCode::TestAndJump(icondition, 0) =>
if icondition == dst {
ByteCode::TestAndJump(icondition, jmp as i16)
} else {
ByteCode::TestAndSetJump(dst as u8, icondition, jmp as u8)
}
_ => panic!("invalid Test"),
};
self.byte_codes[i] = code;
}
}
测试
至此，完成了逻辑运算在求值中的应用场景。可以通过本节开头的几个图中的例子来测试。这里省略。