条件判断中的逻辑运算

逻辑运算包括3个：与and、或or、非not。其中最后一个“非not”是一元运算，已经在之前一元运算一节中介绍过了。本章只介绍前面两个“与and”和“或or”。

那为什么没有在之前的二元运算一节中介绍与and和或or呢？因为“短路”！在主流编程语言（比如C、Rust）中逻辑运算都是短路的。比如对于与and运算，如果第一个操作数是false，那么就没必要（也不能）求第二个操作数了。比如语句is_valid() and count()，假如is_valid()的返回值是false，那么就不能执行后续的count()。所以，逻辑运算的执行过程是：1.先判断左操作数，2.如果是false则退出，3.否则判断右操作数。而之前介绍二元数值运算的执行过程是：1.先求左操作数，2.再求右操作数，3.最后计算。可见逻辑运算跟数值运算的流程不同，不能套用之前的做法。

在具体介绍逻辑运行之前，先来看逻辑运算的两个使用场景：

  1. 作为判断条件，比如上一章中if、while等语句中的判断条件语句，比如if t and t.k then ... end；
  2. 求值，比如print(v>0 and v or -v)。

其实第1种场景可以看做是第2种场景的一种特殊情况。比如上述的if语句例子，就等价于下面的代码：

  1. local tmp = t and t.k
  2. if tmp then
  3.     ...
  4. end

就是先对t and t.k这个运算语句进行求值，然后把值放到临时变量中，最后再判断这个值的真假来决定是否跳转。但是，这里我们其实并不关心具体的求值结果是t还是t.k，而只关心true或者false，所以可以省去临时变量！下面可以看到省去临时变量可以省掉一个字节码，是很大的优化。由于逻辑运算大部分应用是第1种场景，所以是值得把这个场景从第2种通用场景中独立出来特地做优化的，通过省去临时变量，直接根据求值结果来判断是否跳转。

如本节标题所示，本节只介绍第1种场景；下一节再介绍第2种场景。

跳转规律

上面介绍了逻辑运算的短路特性，在每次判断完一个操作数后，都可能发生跳转，跳过下一个操作数。逻辑运算最终对应的字节码，就是根据每个操作数做跳转。不同的运算组合就会导致各种各样的跳转组合。现在就要从各种跳转组合中归纳出跳转规律，以便用作后续的解析规则。这可能是整个解释器中最绕的一部分。

下面都用最简单的if语句作为应用场景，并先看最基础的and和or运算。下面两图分别是if A and B then ... end和if X or Y then ... end的跳转示意图：

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

左图是与and运算。两个操作数A和B判断后的处理一样，都是True则继续执行；False则跳转到代码块结尾。

右图是或or运算。两个操作数的处理流程不一样。第一个操作数X的处理是：False则继续执行，True则跳转到下面代码块开始。而第二个操作数Y的处理跟之前A、B的处理方式一样。

不过只看这两个例子是总结不出通用规律的。还需要看些复杂的：

  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   +-False>+    |       |   Z   +-False-\    |       |   Y   +-False-\    |       |   Y   +-False>+
  15. +---+---+       |    |       +---+---+       |    |       +---+---+       |    |       +---+---+       |
  16.     |True       |    \---------->|True       |    \---------->|True       |    \---------->|True       |
  17.     V           |                V           |                V           |                V           |
  18.   block         |              block         |              block         |              block         |
  19.     |           |                |           |                |           |                |           |
  20.     +<---------/                 +<----------/                +<---------/                 +<---------/
  21.     V                            V                            V                            V

根据这4个图可以归纳如下规律（这里省略了归纳的具体步骤。实际中可能需要更多的例子才能归纳，但是举太多例子又太多臃肿）：

  • 跳转条件取决于语句（比如上面例子中的A,B,X,Y等）后面的逻辑运算符（也就是and或者or）：

    • 如果后面跟and运算，则False跳转而True继续执行。比如第1个图中的A和B，后面都是and运算，所以都是False跳转。

    • 如果后面跟or运算，则True跳转而False继续执行。比如第2个图中的X和Z，后面都是or运算，所以都是True跳转。

    • 如果后面没有逻辑运算符，也就是整条判断语句结束，则False跳转而True继续执行。这个规则跟上面and的相同。上面4个图最后一个判断语句都是如此。

  • 跳转目标位置的规则：

    • 如果连续相同的跳转条件，则跳转到同样位置。比如第1个图中连续3个False跳转，第2个图中连续2个True跳转；而第3个图中的两个False跳转并不连续，所以跳转位置不同。那么在语法分析时，如果两个操作数具有相同的跳转条件，就合并跳转列表。

    • 如果遇到不同的跳转条件，则终结前面的跳转列表，并跳转到当前判断语句之后。比如第2个图中Z的False终结前面的两个True的跳转列表，并跳转到Z语句后面；再比如第3个图中B的True终结之前的False跳转列表，并跳转到B语句后面。

    • 不过第4个图貌似没有遵守上述两条规则，两个False跳转并不连续但也连起来了，或者说X的True跳转并没有终结A的False跳转列表。这是因为A并不是跟X运算，而是跟(X or Y)运算；要先求(X or Y)，此时X的True跳转是全新的，并不知道前面的A的False跳转列表；然后再求A and (X or Y)时，就是True和False两个跳转列表并存了；最终语句结束的False，合并之前A的False跳转列表，并终结X的True跳转列表。

    • 判断语句的结束对应的是False跳转，所以会终结True跳转列表，并继续False跳转列表。在block结束后，终结False跳转列表到block结尾。上面4个图中都是如此。

至此，介绍完准备知识。下面开始编码实现。

字节码

上一章控制结构的几个条件判断语句，包括if、while、和repeat..until等，对判断条件的处理都是False跳转，所以只有一个测试并跳转的字节码，即Test。而现在需要2种跳转，False跳转和True跳转。为此我们去掉之前的Test，并新增2个字节码：

  1. pub enum ByteCode {
  2.     TestAndJump(u8, i16),  // 如果Test为True，则Jump。
  3.     TestOrJump(u8, i16),   // 如果Test为False，则Jump。跟上一章的`Test`功能相同。

命名中的“And”和“Or”，跟本节介绍的逻辑运算并无关系，而是源自Rust语言中Option和Error类型的方法名，分别是“那么就”和“否则就”的意思。不过本节最开头的两个例子中，t and t.k可以描述为：如果t存在“那么就”取t.k，t.k or 100可以描述为：如果t.k存在就取其值“否则就”取100。也可以说是相关联的。

只不过上面介绍的跳转规则第1条，如果后面跟and运算，则False跳转，对应的是TestOrJump。这里的and和Or没有对应上，不过关系不大。

官方Lua实现中，仍然只是一条字节码TEST，关联两个参数分别是：判断条件的栈地址（跟我们的一样），和跳转条件（True跳转还是False跳转）。而具体的跳转位置，则需要再加一条无条件跳转的JUMP字节码。看上去2条字节码不太高效。这么做是为了跟另外一个应用场景，在下一节中介绍。

ExpDesc

在解析逻辑运算符生成跳转字节码时，还不知道跳转的目的位置。只能先生成一个字节码占位，而留空跳转位置的参数。在后续确定目的位置后再填补参数。这个做法跟上一章介绍控制结构时是一样的。而不一样的是，上一章里只会有1个跳转字节码，而这次可能会出现多个字节码拉链的情况，比如上面的第1个图，3个字节码跳转到同一位置。这个拉链可能是True跳转，也可能是False跳转，也可能这两条链同时存在，比如上面第4个图中解析到Y时候。所以需要一个新的ExpDesc类型来保存跳转链表。为此，新增Test类型，定义如下：

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

关联3个参数。第1个是判断条件在栈上的位置，无论什么类型（常量、变量、表索引等）都会先discharge到栈上，然后再判断真假。后面2个参数是True和False这2条跳转链表，内容分别是需要补齐的字节码的位置。

Lua官方实现中，跳转表是通过跳转字节码中留空的参数来实现的。比如上面第1个图中连续3个False的跳转，判断A、B、C生成的字节码分别是JUMP 0, JUMP $A, JUMP $B，然后在ExpDesc中保存$C。这样通过$C就可以找到$B，通过$B就可以找到$A，而参数0表示链表末尾。最后一边遍历，一边统一修复为JUMP $end。这种设计很高效，无需额外存储，利用暂时留空的Jump参数就可以实现拉链。同时也略显晦涩，容易出错。这种充分利用资源，按bit微操内存，是很典型的C语言项目的做法。而Rust语言标准库中提供了列表Vec，虽然会产生在堆上的内存分配，稍微影响性能，但是逻辑清晰很多，一目了然。只要不是性能瓶颈，就应该尽量避免晦涩而危险的做法，尤其是在使用追求安全的Rust语言时。

语法分析代码

现在终于可以语法分析了。从exp()函数的二元运算部分开始。之前介绍二元数值运算的求值顺序，要先处理第一个操作数。本节开头也介绍了，对于逻辑运算的处理顺序，由于短路的特性，也要先处理第一个操作和可能的跳转，然后才能解析第二个操作数。所以，在继续解析第二个操作数前，先处理跳转：

  1.     fn preprocess_binop_left(&mut self, left: ExpDesc, binop: &Token) -> ExpDesc {
  2.         match binop {
  3.             Token::And => ExpDesc::Test(0, Vec::new(), self.test_or_jump(left)),
  4.             Token::Or => ExpDesc::Test(0, self.test_and_jump(left), Vec::new()),
  6.             _ => // 省略discharge其他类型的部分
  7.         }
  8.     }

这个函数中，新增了对逻辑运算的处理部分。以and为例，生成ExpDesc::Test类型，临时保存处理后的2条跳转列表，而关联的第1个参数没有用，这里填0。调用test_or_jump()函数来处理跳转列表。按照上面介绍的规则，and运算符对应的是False跳转，是会终结之前的True跳转列表，所以test_or_jump()函数会终结之前的True跳转列表，并只返回False跳转列表。那么这里就新建一个列表Vec::new()作为True跳转列表。

再看test_or_jump()的具体实现：

  1.     fn test_or_jump(&mut self, condition: ExpDesc) -> Vec<usize> {
  2.         let (icondition, true_list, mut false_list) = match condition {
  3.             // 为True的常量，无需测试或者跳转，直接跳过。
  4.             // 例子：while true do ... end
  5.             ExpDesc::Boolean(true) | ExpDesc::Integer(_) | ExpDesc::Float(_) | ExpDesc::String(_) => {
  6.                 return Vec::new();
  7.             }
  9.             // 第一个操作数已经是Test类型，说明这不是第一个逻辑运算符。
  10.             // 直接返回已有的两个跳转列表即可。
  11.             ExpDesc::Test(icondition, true_list, false_list) =>
  12.                 (icondition, Some(true_list), false_list),
  14.             // 第一个操作数是其他类型，说明这是第一个逻辑运算符。
  15.             // 只需要discharge第一个操作数到栈上即可。
  16.             // 之前也没有True跳转列表，所以返回None。
  17.             // 也没有False跳转列表，所以新建一个列表，用来保存本次跳转指令。
  18.             _ => (self.discharge_any(condition), None, Vec::new()),
  19.         };
  21.         // 生成TestOrJump，但第二个参数留空
  22.         self.byte_codes.push(ByteCode::TestOrJump(icondition as u8, 0));
  24.         // 把刚生成的字节码，假如到False跳转列表中，以便后续修复
  25.         false_list.push(self.byte_codes.len() - 1);
  27.         // 终结之前的True跳转列表，并跳转到这里，如果有的话
  28.         if let Some(true_list) = true_list {
  29.             self.fix_test_list(true_list);
  30.         }
  32.         // 返回False跳转列表
  33.         false_list
  34.     }

对于or运算符和对应的test_and_jump()函数，大同小异，只是翻转下True和False跳转列表。这里不再介绍。

处理完第一个操作数和跳转后，再来处理第二个操作数就很简单了，只需要连接跳转列表即可：

  1.     fn process_binop(&mut self, binop: Token, left: ExpDesc, right: ExpDesc) -> ExpDesc {
  2.         match binop {
  3.             // 省略其他二元运算符处理
  4.             Token::And | Token::Or => {
  5.                 // 第一个操作数已经在上面的preprocess_binop_left()中被转换为ExpDesc::Test
  6.                 if let ExpDesc::Test(_, mut left_true_list, mut left_false_list) = left {
  7.                     let icondition = match right {
  8.                         // 如果第二个操作数也是Test类型，比如本节上面第4个图中`A and (X or Y)`的例子，
  9.                         // 那么分别连接两个跳转列表。
  10.                         ExpDesc::Test(icondition, mut right_true_list, mut right_false_list) => {
  11.                             left_true_list.append(&mut right_true_list);
  12.                             left_false_list.append(&mut right_false_list);
  13.                             icondition
  14.                         }
  15.                         // 如果第二个操作数是其他类型，则无需处理跳转链表
  16.                         _ => self.discharge_any(right),
  17.                     };
  19.                     // 返回连接后想新跳转列表
  20.                     ExpDesc::Test(icondition, left_true_list, left_false_list)
  21.                 } else {
  22.                     panic!("impossible");
  23.                 }
  24.             }

处理完二元运算部分，接下来就是应用场景。本节只介绍作为判断条件的应用场景，而在下一节中再介绍求值。上一章中的几个控制结构语句（if、while、repeat..until等）都是直接处理跳转字节码，代码逻辑类似。本节开头介绍的跳转规则中，整条逻辑运算的判断语句结束，是False跳转，所以调用刚才介绍的test_or_jump()函数处理，可以代替并简化上一章的直接处理字节码的代码逻辑。这里仍然用if语句为例：

  1.     fn do_if_block(&mut self, jmp_ends: &mut Vec<usize>) -> Token {
  2.         let condition = self.exp();
  4.         // 上一章，这里是生成Test字节码。
  5.         // 现在，替换并简化为test_or_jump()函数。
  6.         // 终结True跳转列表，并返回新的False跳转列表。
  7.         let false_list = self.test_or_jump(condition);
  9.         self.lex.expect(Token::Then);
  11.         let end_token = self.block();
  13.         if matches!(end_token, Token::Elseif | Token::Else) {
  14.             self.byte_codes.push(ByteCode::Jump(0));
  15.             jmp_ends.push(self.byte_codes.len() - 1);
  16.         }
  18.         // 上一章，这里是修复刚才生成的一条Test字节码。
  19.         // 现在，需要修改一条False跳转列表。
  20.         self.fix_test_list(false_list);
  22.         end_token
  23.     }

至此完成语法分析部分。

虚拟机执行

虚拟机执行部分，首先是要处理新增的2个字节码，都很简单，这里忽略不讲。需要讲的是一个栈操作的细节。之前向栈上赋值时的函数如下：

  1.     fn set_stack(&mut self, dst: u8, v: Value) {
  2.         let dst = dst as usize;
  3.         match dst.cmp(&self.stack.len()) {
  4.             Ordering::Equal => self.stack.push(v),
  5.             Ordering::Less => self.stack[dst] = v,
  6.             Ordering::Greater => panic!("fail in set_stack"),
  7.         }
  8.     }

首先判断目标地址dst是否在栈的范围内：

  • 如果在，则直接赋值；
  • 如果不在并且刚好是下一个位置，则使用push()压入栈中；
  • 如果不在，并且超过下一个位置，之前是不可能出现的，所以调用panic!()。

但是逻辑运算的短路特性，是可能导致上述第3种情况出现的。比如下面的语句：

  1. if (g1 or g2) and g3 then
  2. end

按照我们的解析方式，会生成如下临时变量，占用栈上位置：

  1. |      |
  2. +------+
  3. |  g1  |
  4. +------+
  5. |  g2  |
  6. +------+
  7. |  g3  |
  8. +------+
  9. |      |

但在执行过程中，如果g1为真，则会跳过对g2的处理，而直接处理g3，此时上图中g2的位置并未设置，那么g3就会超过栈顶的位置，如下图所示：

  1. |      |
  2. +------+
  3. |  g1  |
  4. +------+
  5. |      |
  6. :      :
  7. :      : <-- 设置g3，超过栈顶位置

所以，要修改上述set_stack()函数，支持设置超过栈顶的元素。这可以通过调用set_vec()实现。

测试

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