条件判断中的关系运算

前面两节介绍了逻辑运算，接下来两节介绍关系运算。

关系运算，即比较大小，共6个运算符：等于、不等、大于、小于、大于等于、小于等于。前两节介绍逻辑运算时说过，逻辑运算不能用第5章中的二元数值运算的解析流程，是因为短路这个特性。而关系运算也没有用第5章的解析流程，是不同的原因：为了性能。

如果不考虑性能，关系运算是可以用第5章的解析流程的。比如对于等于运算，可以生成如下字节码：EQ $r $a $b，即比较a和b，并把布尔类型的结果赋值给r。如果要考虑性能，就要看关系运算的应用场景。这部分跟前两节介绍的逻辑运算几乎一样，也有两个应用场景：

  1. 作为判断条件，比如上一章中if、while等语句中的判断条件语句，比如if a == b then ...；
  2. 求值，比如print(a == b)。

跟逻辑运算一样，第1种场景可以看做是第2种场景的简化版，不需要具体求值，只需要判断真假。比如上述的if语句例子，也可以按照第2种场景来解释，认为是先对a == b求值到临时变量，然后再判断临时变量是否为真，来决定是否跳转。这里可以省去临时变量！由于关系运算大部分应用是第1种场景，所以是值得把这个场景从第2种通用场景中独立出来特地做优化的，通过省去临时变量，直接根据求值结果来判断是否跳转。

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

字节码

还是用if语句和等于运算为例，在if a == b then ... end场景下，最先想到的字节码序列如下：

EQ   $tmp $a $b  # 比较a和b是否相等，结果存在临时变量中
TEST $tmp $jmp   # 根据临时变量来决定是否跳转

现在要省去临时变量$tmp，合并两条字节码，如下：

EQ   $a $b $jmp  # 比较a和b是否相等，来决定是否跳转

但问题是这样需要3个参数，留给最后的跳转参数的只有1个字节的空间，表示范围太小了。为此可以再拆成2个字节码：

EQ   $a $b  # 判断a和b是否相等，如果相等则跳过下一条语句，即pc++
JUMP $jmp   # 无条件跳转

这样就可以用2个字节来表示跳转参数了。但是，既然还是需要2条字节码，那跟最开始的“EQ+TEST”方案，又有什么区别呢？搞这么复杂是为了什么呢？

  • 虚拟机执行时，如果判断a和b相等，跳过下面JUMP字节码，那么就只执行了1条字节码；而最开始的“EQ+TEST”方案总是会执行2条字节码。对于if语句判断为真的概率不知道，但对于while语句判断为真的概率还是很大的，所以这里相当于是大概率省去了1条字节码的执行；

  • 即便判断为假，需要执行下面的JUMP字节码，那么也可以在执行EQ字节码的时候，直接读取下一条字节码，而不用再走一次指令分发。这里的JUMP字节码相当于是EQ字节码的扩展参数，而不是一条独立执行的字节码。Lua的官方实现就是这么做的，这也是因为C语言中可以忽略字节码的类型，通过位运算直接读取字节码中的参数。但是在Rust语言中如果不用unsafe，是不能忽略enum的tag而直接读取参数的，所以我们的解释器里不能实现这个优化。

  • 根据判断结果可以直接决定是否跳转。而最开始的“EQ+TEST”方案，需要先把判断结果写入栈上临时变量，然后在TEST字节码执行时再读取临时变量，然后再次判断真假，这样就多了一次临时变量的读和写，也多了一次真假的判断。

优势呢就是这么个优势。有，但不多。尤其是跟其带来的实现复杂度相比，就更显得少了。最开始的“EQ+TEST”方案只需要在之前介绍的二元数值运算中，增加几个运算符即可；但新的方案需要跟前面讲的逻辑运算配合。不过我们还是选择跟随Lua官方实现，用实现的复杂度换一些执行效率优化。

另外，关于字节码中两个操作数的类型，按照之前字节码参数类型的说明，跟二元数值运算的字节码相似，每个关系运算符也都对应3个字节码，比如对于相等运算符有：Equal、EqualInt和EqualConst共3个字节码。一共6个关系运算符，就是18个字节码。

跟逻辑运算相结合

关系运算和逻辑运算相结合是非常常见的。以a>b and b<c语句为例，按照前面两节的介绍，这是一条逻辑运算语句，两个操作数分别是a>b和b<c，需要把这两个操作数discharge到栈上临时变量以便判断真假。这里为了避免使用临时变量，就需要让关系运算和逻辑运算互相配合。

对于关系运算语句，需要新增ExpDesc类型：Compare。下面来看如果要跟逻辑运算相结合，即对于以关系运算为操作数的逻辑运算语句，那么这个类型需要关联什么参数。

首先，如果不转换为ExpDesc::Test类型，那么Compare类型就需要自己维护True和False两条跳转链表；

其次，对于True和False这两种跳转，之前的逻辑运算是通过2个字节码来区分的，TestAndJump和TestOrJump。对于关系运算，也可以这么做，比如等于运算用EqualTrue和EqualFalse字节码。但是关系运算符一共有18个字节码，如果还要每个字节码都再区分True和False跳转，那么需要36个字节码了。这就太多了。还好有另外一种方法，上面介绍的EQ字节码只有2个参数，可以再增加一个布尔类型的参数，来表示True还是False跳转。

最后，对于True和False这两种跳转，是需要根据后面的逻辑运算符来决定的。比如上面的a>b and b<c的例子，在解析到a>b时还不能确定，只有解析到and时才能确定。所以在解析关系运算语句时还不能生成完整的字节码，就只能先把相关信息存入Compare类型中，然后在确定跳转类型后，再生成字节码。

综上，关系运算的新类型定义如下：

enum ExpDesc {
    Compare(fn(u8,u8,bool)->ByteCode, usize, usize, Vec<usize>, Vec<usize>),

前面3个参数是字节码类型和前2个参数，用于在确定跳转类型后以生成字节码；后面2个参数是True和False跳转列表。整个类型相当于是BinaryOp和Test类型的结合。

这里跟前面介绍的逻辑运算遇到的是同样的问题，都是在生成字节码的时候还不能确定跳转的目的地址，不能立即生成完整的字节码，需要后续确定目的地址后再处理。但是，这里跟之前的逻辑运算的解决方法不一样。之前的逻辑运算的做法是：先生成一个字节码占位，而只把跳转目的地址的参数留空；后续确定目的地址后再修复字节码中的对应参数（fix_test_list()函数）。而这里的关系运算的做法是，把信息都存到ExpDesc::Compare中（导致这个类型的定义很长），然后等后续确定目的地址后再直接生成完整的字节码。

其实对于关系运算的处理，理论上也可以采用逻辑运算那种先生成字节码再修复的方法，但是关系运算对应的字节码有18个，太多了，如果还按照fix_test_list()函数的做法先匹配再生成字节码，代码就显得太复杂了。如果是在C语言中，可以通过位操作直接修正字节码内的参数，而忽略字节码类型；而在Rust中直接修改enum内关联参数就需要unsafe了。

另外一个区别是，在解析逻辑运算时，必须立即生成字节码用来占位。而关系运算的Compare类型操作数会在紧接着的test_or_jump()函数中就确定跳转类型，就可以生成字节码了，所以并不需要占位，也就没必要先生成字节码然后再修复了。

语法分析

关系运算的语法分析分为两部分：

  • 解析运算本身，根据运算符生成对应的ExpDesc::Compare，这部分跟二元数值运算类似，这里略过。

  • 关系运算和逻辑运算的结合，即ExpDesc::Compare和ExpDesc::Test的结合。在之前逻辑运算解析部分，都增加对ExpDesc::Compare的处理。

比如在逻辑运算左操作数时，生成字节码，并处理两条跳转列表：

    fn test_or_jump(&mut self, condition: ExpDesc) -> Vec<usize> {
        let (code, true_list, mut false_list) = match condition {
            ExpDesc::Boolean(true) | ExpDesc::Integer(_) | ExpDesc::Float(_) | ExpDesc::String(_) => {
                return Vec::new();
            }
            // 新增Compare类型。
            // 生成2个字节码。
            // 两个跳转列表的处理方式跟下面的`ExpDesc::Test`的一样。
            ExpDesc::Compare(op, left, right, true_list, false_list) => {
                // 确定为True跳转，即关联的第3个参数，就可以生成完整字节码。
                self.byte_codes.push(op(left as u8, right as u8, true));

                // 生成Jump字节码，但还不知道跳转目的地址，需要后续修复。为此，
                // fix_test_list()中要新增对Jump字节码的处理。
                (ByteCode::Jump(0), Some(true_list), false_list)
            }
            ExpDesc::Test(condition, true_list, false_list) => {
                let icondition = self.discharge_any(*condition);
                (ByteCode::TestOrJump(icondition as u8, 0), Some(true_list), false_list)
            }
            _ => {
                let icondition = self.discharge_any(condition);
                (ByteCode::TestOrJump(icondition as u8, 0), None, Vec::new())
            }
        };

在比如在处理右操作数时：

    fn process_binop(&mut self, binop: Token, left: ExpDesc, right: ExpDesc) -> ExpDesc {
        match binop {
            Token::And | Token::Or => {
                if let ExpDesc::Test(_, mut left_true_list, mut left_false_list) = left {
                    match right {
                        // 新增Compare类型。
                        // 处理方式类似下面的`ExpDesc::Test`类型。
                        ExpDesc::Compare(op, l, r, mut right_true_list, mut right_false_list) => {
                            left_true_list.append(&mut right_true_list);
                            left_false_list.append(&mut right_false_list);
                            ExpDesc::Compare(op, l, r, left_true_list, left_false_list)
                        }
                        ExpDesc::Test(condition, mut right_true_list, mut right_false_list) => {
                            left_true_list.append(&mut right_true_list);
                            left_false_list.append(&mut right_false_list);
                            ExpDesc::Test(condition, left_true_list, left_false_list)
                        }
                        _ => ExpDesc::Test(Box::new(right), left_true_list, left_false_list),
                    }
                } else {
                    panic!("impossible");
                }
            }

虚拟机执行

一共6种关系运算符。由于我们之前已经为Value实现了Eq trait，所以其中的等于和不等于运算可以使用==和!=来直接比较Value操作数。但对于另外4个运算符，就需要再给Value实现新的trait了，就是PartialOrd。之所以不是Ord是因为不同类型的Value是不能比较大小的。而不需要使用PartialEq是因为不同类型的Value是可以比较是否相等的，返回结果为False。比如对下面两条语句：

print (123 == 'hello') -- 打印false
print (123 > 'hello')  -- 抛异常

Lua的大小比较运算符，只支持数字和字符串类型。所以Value的PartialOrd实现如下：

impl PartialOrd for Value {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match (self, other) {
            // numbers
            (Value::Integer(i1), Value::Integer(i2)) => Some(i1.cmp(i2)),
            (Value::Integer(i), Value::Float(f)) => (*i as f64).partial_cmp(f),
            (Value::Float(f), Value::Integer(i)) => f.partial_cmp(&(*i as f64)),
            (Value::Float(f1), Value::Float(f2)) => f1.partial_cmp(f2),

            // strings
            (Value::ShortStr(len1, s1), Value::ShortStr(len2, s2)) => Some(s1[..*len1 as usize].cmp(&s2[..*len2 as usize])),
            (Value::MidStr(s1), Value::MidStr(s2)) => Some(s1.1[..s1.0 as usize].cmp(&s2.1[..s2.0 as usize])),
            (Value::LongStr(s1), Value::LongStr(s2)) => Some(s1.cmp(s2)),

            // strings of different types
            (Value::ShortStr(len1, s1), Value::MidStr(s2)) => Some(s1[..*len1 as usize].cmp(&s2.1[..s2.0 as usize])),
            (Value::ShortStr(len1, s1), Value::LongStr(s2)) => Some(s1[..*len1 as usize].cmp(s2)),
            (Value::MidStr(s1), Value::ShortStr(len2, s2)) => Some(s1.1[..s1.0 as usize].cmp(&s2[..*len2 as usize])),
            (Value::MidStr(s1), Value::LongStr(s2)) => Some(s1.1[..s1.0 as usize].cmp(s2)),
            (Value::LongStr(s1), Value::ShortStr(len2, s2)) => Some(s1.as_ref().as_slice().cmp(&s2[..*len2 as usize])),
            (Value::LongStr(s1), Value::MidStr(s2)) => Some(s1.as_ref().as_slice().cmp(&s2.1[..s2.0 as usize])),

            (_, _) => None,
        }
    }
}

对于浮点数需要调用partial_cmp()方法是因为浮点数的Nan不能比较大小。

实现了PartialOrd trait的类型就可以直接使用>、<、>=和<=等几个比较大小的符号了。但是PartialOrd对于大小比较其实有3个返回结果：真、假、和不能比较。对应于Lua语言就分别是真、假、和抛出异常。而上述4个比较符号只能给出2个结果，对于不能比较的情况也是返回假。所以为了能判断出不能比较的情况，我们不能直接使用这4个符号，还是要用原始的partial_cmp()函数。下面是LesEq和Less两个字节码的执行代码：

    ByteCode::LesEq(a, b, r) => {
        let cmp = &self.stack[a as usize].partial_cmp(&self.stack[b as usize]).unwrap();
        if !matches!(cmp, Ordering::Greater) == r {
            pc += 1;
        }
    }
    ByteCode::Less(a, b, r) => {
        let cmp = &self.stack[a as usize].partial_cmp(&self.stack[b as usize]).unwrap();
        if matches!(cmp, Ordering::Less) == r {
            pc += 1;
        }
    }

这里用unwarp()来抛出异常。后续在规范错误处理时，这里需要做改进。