数值型for语句

Lua的for语句支持两种类型：

  • 数值型：for Name ‘=’ exp ‘,’ exp [‘,’ exp] do block end
  • 泛型：for namelist in explist do block end

泛型for需要函数支持，在下一章介绍了函数后再实现。本节实现数值型for。从BNF定义中可见，这两个类型的前2个Token一样，数值型的第3个Token是=。通过这个区别可以区分两种类型：

  1.     fn for_stat(&mut self) {
  2.         let name = self.read_name();
  3.         if self.lex.peek() == &Token::Assign {
  4.             self.for_numerical(name);  // 数值型
  5.         } else {
  6.             todo!("generic for");  // 泛型
  7.         }
  8.     }

控制结构

数值型for语句的语义很明显，等号=后面3个表达式依次是初始值init、限制limit、和步长step。step可以是正数或负数，不能是0。控制结构图如下（图中假设step>0）：

  1.      +--------------+
  2. /--->| i <= limit ? |--No--\ 如果超过limit则跳转到结尾
  3. |    +--------------+      |
  4. |                          |
  5. |        block             |
  6. |                          |
  7. |    +-----------+         |
  8. \----| i += step |         |
  9.      +-----------+         |
  10.          <-----------------/

图中方框中的执行逻辑都可以分别用1条字节码实现，每此循环都要执行2条字节码：先i+=step，然后判断i<=limit。为了性能，可以把第1条字节码的判断功能也加到下面的字节码中，这样每次循环只用执行1条字节码。控制结构图如下：

  1.        +--------------+
  2.        | i <= limit ? |--No--\ 如果超过limit则跳转到结尾
  3.        +--------------+      |
  4. /------>                     |
  5. |       block                |
  6. |                            |
  7. |       +--------------+     |
  8. |       | i += step    |     |
  9. \--Yes--| i <= limit ? |     |
  10.         +--------------+     |
  11.             <----------------/

新增2条字节码：

  1. pub enum ByteCode {
  2.     // for-loop
  3.     ForPrepare(u8, u16),
  4.     ForLoop(u8, u16),

这2个字节码分别对应上图中两个方框的字节码，关联的两个参数都分别是栈起始位置和跳转位置。后续会看到第一个字节码除了判断跳转以外，还需要做其他的准备工作，所以名叫prepare。

变量存储

上面2个字节码关联的第1个参数都是栈的起始位置。准确说就是存储上述3个值（init，limit，step）的位置。这3个值自然是需要存储在栈上的，因为栈的功能之一就是存储临时变量，另外也因为没有其他地方可用。这3个值依次存储，所以只需要一个参数就可以定位3个值。

另外，for语句还有个控制变量，可以复用init的栈上位置。在语法分析时，创建一个内部临时变量，名字就是BNF中的Name，指向栈上第一个变量的位置。为了让另外2个临时变量的位置不被占用，需要再创建2个匿名局部变量。所以，执行时的栈如下：

  1.       |        |
  2. sp    +--------+
  3.       | init/i |  控制变量Name
  4. sp+1  +--------+
  5.       | limit  |  匿名变量""
  6. sp+2  +--------+
  7.       | step   |  匿名变量""
  8.       +--------+
  9.       |        |

数值型for语句就上面的3个临时变量比较特殊，其余部分跟之前介绍的控制结构类似，无非就是根据条件判断语句做跳转。语法分析代码如下：

  1.     fn for_numerical(&mut self, name: String) {
  2.         self.lex.next(); // skip `=`
  4.         // 读取3个表达式：init、limit、step（默认是1），依次放置到栈上
  5.         match self.explist() {
  6.             2 => self.discharge(self.sp, ExpDesc::Integer(1)),
  7.             3 => (),
  8.             _ => panic!("invalid numerical for exp"),
  9.         }
  11.         // 创建3个局部变量，用以占住栈上位置。后续如果内部block需要局部或临时变量，
  12.         // 就会使用栈上这3个变量之后的位置。
  13.         self.locals.push(name);  // 控制变量，可以在内部block中被引用
  14.         self.locals.push(String::from(""));  // 匿名变量，纯粹占位用
  15.         self.locals.push(String::from(""));  // 同上
  17.         self.lex.expect(Token::Do);
  19.         // 生成ForPrepare字节码
  20.         self.byte_codes.push(ByteCode::ForPrepare(0, 0));
  21.         let iprepare = self.byte_codes.len() - 1;
  22.         let iname = self.sp - 3;
  24.         self.push_loop_block();
  26.         // 内部block
  27.         assert_eq!(self.block(), Token::End);
  29.         // 删除3个临时变量
  30.         self.locals.pop();
  31.         self.locals.pop();
  32.         self.locals.pop();
  34.         // 生成ForLoop字节码，并修复之前的ForPrepare
  35.         let d = self.byte_codes.len() - iprepare;
  36.         self.byte_codes.push(ByteCode::ForLoop(iname as u8, d as u16));
  37.         self.byte_codes[iprepare] = ByteCode::ForPrepare(iname as u8, d as u16);
  39.         self.pop_loop_block(self.byte_codes.len() - 1);
  40.     }

整数和浮点数类型

之前支持的语句类型，都主要介绍语法分析部分；而虚拟机执行部分只是按照字节码对栈进行简单的操作。但数值型for循环的语法分析部分相对比较简单（主要是因为跟之前的几个控制结构类似），而虚拟机执行部分却很复杂。其实也不难，就是繁琐。繁琐的原因是因为Lua支持2种数值类型，整数和浮点数。数值型for语句中一共3个语句（或者称为变量），init、limit、和step，每个都可能是两种类型之一，一共就是8种可能。虽然某些情况下在语法分析阶段就可以确定某些变量的类型的（比如是常量），但对这种特殊情况单独处理的意义不大，最终还是需要处理全部3个变量都是未知类型的情况，这就需要在虚拟机执行阶段处理。

逐个处理8种类型实在太复杂；又不能完全归为一种类型，因为整数和浮点数的表示范围不一样。对此，Lua语言规定分为2类：

  • 如果init和step是整数，那么按照整数处理；
  • 否则，都按照浮点数处理。

至于在第一类里为什么没有考虑第2个limit的变量，就不清楚了。我想到有一些可能的原因，但都不确定，这里就不讨论了。就按照Lua的规定实现即可。但这也确实带来了一些复杂。

需要在某个地方把8种可能归类为上述2种类型。在语法分析阶段做不到，而在每次执行循环时又太费性能，所以就在循环开始的时候归类一次。这也就是ForPrepare字节码要做的事情：

  • 如果init和step是整数，那么把limit也转换为整数；
  • 否则，把3个变量都转换为浮点数。

这样，在每次执行循环时，即ForLoop字节码时，只需要处理2种情况即可。

第2类中把整数转换为浮点数简单，但第1类中把浮点数limit转换为整数，就要注意下面两点：

  • 如果step为正，则limit向下取整；如果step为负，则limit向上取整。
  • 如果limit超过整数的表示范围，那么就转换为整数的最大或最小值。这里就有个极端情况，比如step为负，init为整数最大值，limit超过了整数的最大值，那么init就小于limit，又因为Lua明确规定数值型for循环的控制变量不会溢出反转，所以预期是不会执行循环。但按照上述转换，limit由于超过整数的最大值，就被转换为最大值，就等于init了，就会执行一次循环。所以要特殊处理，可以把init和limit分别设置为0和1，这样就不会执行循环了。

limit变量转换的具体代码如下：

  1. fn for_int_limit(limit: f64, is_step_positive: bool, i: &mut i64) -> i64 {
  2.     if is_step_positive {
  3.         if limit < i64::MIN as f64 {
  4.             *i = 0;  // 一并修改init，保证不会执行循环
  5.             -1
  6.         } else {
  7.             limit.floor() as i64  // 向下取整
  8.         }
  9.     } else {
  10.         if limit > i64::MAX as f64 {
  11.             *i = 0;
  12.             1
  13.         } else {
  14.             limit.ceil() as i64  // 向上取整
  15.         }
  16.     }
  17. }

虚拟机执行

介绍完上述整数和浮点数类型和转换细节后，接下来就实现相关两个字节码的虚拟机执行部分。

ForPrepare字节码做2件事情：首先根据变量类型分为整数和浮点数类型循环；然后比较init和limit判断是否执行第一次循环。代码如下：

  1. {{#include ../listing/ch06.control_structures/src/vm.rs:for_prepare}}

ForLoop字节码也做2件事情：首先控制变量加上step；然后比较控制变量和limit判断是否执行下一次循环。这里省略代码。

至此，我们完成数值型for语句。