02-变量赋值

引言

先写下这节需要解释执行的Lua代码：

local s = "Where is rua?"
local print = print
print(s)

none = nil

local thezzw = none
print(thezzw)

none_alias = none
print(none_alias)

none = "none"
print(none)

以上代码包括了局部变量赋值、全局变量赋值、全局变量赋值给局部变量、全局变量赋值给全局变量四种赋值情况。在继续上一节的内容，拓展解释器以支持这些功能之前，我们可以先用luac看看官方实现的流程。官方实现的字节码结果如下：

main <test/hello.lua:0,0> (21 instructions at 0000000000c69330)
0+ params, 5 slots, 1 upvalue, 3 locals, 5 constants, 0 functions
        1       [1]     VARARGPREP      0
        2       [1]     LOADK           0 0     ; "Where is rua?"
        3       [2]     GETTABUP        1 0 1   ; _ENV "print"
        4       [3]     MOVE            2 1
        5       [3]     MOVE            3 0
        6       [3]     CALL            2 2 1   ; 1 in 0 out
        7       [5]     SETTABUP        0 2 3k  ; _ENV "none" nil
        8       [6]     GETTABUP        2 0 2   ; _ENV "none"
        9       [7]     MOVE            3 1
        10      [7]     MOVE            4 2
        11      [7]     CALL            3 2 1   ; 1 in 0 out
        12      [9]     GETTABUP        3 0 2   ; _ENV "none"
        13      [9]     SETTABUP        0 4 3   ; _ENV "none_alias"
        14      [10]    MOVE            3 1
        15      [10]    GETTABUP        4 0 4   ; _ENV "none_alias"
        16      [10]    CALL            3 2 1   ; 1 in 0 out
        17      [12]    SETTABUP        0 2 2k  ; _ENV "none" "none"
        18      [13]    MOVE            3 1
        19      [13]    GETTABUP        4 0 2   ; _ENV "none"
        20      [13]    CALL            3 2 1   ; 1 in 0 out
        21      [13]    RETURN          3 1 1   ; 0 out

第一行

本次翻译的基本信息，test/hello.lua共翻译出了21个字节码。

第二行

翻译函数的一些资源使用情况（一个Lua文件可以视作一个匿名函数，其内容在require加载时会被执行一次，并返回其最后一条表达式的值（或return显式指定的值）。其他文件通过require可以获取该文件返回的值，从而实现模块化导出。）：

• 0+ params表示该函数的参数数量为 0，且不使用可变参数。
• 5 slots表示该函数使用了5个寄存器位置。
• 1 upvalue表示该函数引用了1个外部变量，即print。
• 3 locals表示该函数声明了3个局部变量，显而易见，不多赘述。
• 5 constants表示该函数中引用了5个常量，按其常量表的位置顺序分别是"Where is rua?"、"print"、"none"、nil、"none_alias"。

• 0 functions表示该函数中没有嵌套的子函数。

  字节码部分

• VARARGPREP 0

  Lua 函数入口的常规操作，用于初始化参数栈。参数 0 表示不保留任何参数到寄存器中。

• LOADK 0 0

  将常量 0（即字符串 "Where is rua?"）加载到寄存器 0。

• GETTABUP 1 0 1

  从环境表0的值（_ENV）中获取常量1 "print" 的值，存入寄存器 1。

• MOVE 2 1

  将寄存器 1 的值（即 print 函数）复制到寄存器 2。因为MOVE字节码，所以开发中可以通过将多次使用的全局变量的值赋值给局部变量以提高访问速度。

• MOVE 3 0

  将寄存器 0 的值（即 "Where is rua?"）复制到寄存器 3。用作print的参数。

• CALL 2 2 1

  调用位于寄存器2的函数（即print），有2-1=1个参数，1-1=0个返回值。至于为什么不是更直观的CALL 2 1 0，可以看lvm.c的第1673~1689行的代码，同时深入ldo.c的luaD_precall函数，看到Lua非常重要的一个数据结构CallInfo的构造过程。CALL的三个参数的语义分别是：

  1. 被调用函数在栈中的位置，会被转换成StkId传给luaD_precall。
  2. 函数参数数量+1。在luaD_precall里可以看到计算逻辑int narg = cast_int(L->top.p - func) - 1;，而L->top.p在调用luaD_precall前被设置为了函数位置+该参数（L->top.p = ra + b;）。
  3. 函数返回值数量+1，当值为0时意味着保留所有的返回值。在lvm.c的第1677行。

• SETTABUP 0 2 3k

  在环境表0（_ENV）中将常量2"none"的值设置为nil。至于第三个参数为什么显示的是3k，翻阅luac.c的代码可知（第350行），当一个字节码满足iABC的格式，且POS_k位置为1，则会在打印字节码时加上'k'，这个标志位用于区分参数是直接值还是常量表引用。

• GETTABUP 2 0 2

  从环境表0的值（_ENV）中获取常量2 "none" 的值（即nil），存入寄存器 2。

• MOVE 3 1

  将寄存器 1 的值（即 print 函数）复制到寄存器 3。

• MOVE 4 2

  将寄存器 2 的值（即 nil ）复制到寄存器 4。

• CALL 3 2 1

  调用位于寄存器3的函数（即print函数），有2-1=1个参数，1-1=0个返回值。

• GETTABUP 3 0 2

  从环境表0的值（_ENV）中获取常量2 （"none"） 的值（仍为nil），存入寄存器 3。

• SETTABUP 0 4 3

  在环境表0（_ENV）中将常量4（"none_alias"）的值设置为寄存器3的值（nil）。

• MOVE 3 1

  将寄存器 1 的值（即 print 函数）复制到寄存器 3。

• GETTABUP 4 0 4

  从环境表0的值（_ENV）中获取常量4 （"none_alias"） 的值（即nil），存入寄存器 4。

• CALL 3 2 1

  调用位于寄存器3的函数（即print函数），有2-1=1个参数，1-1=0个返回值。

• SETTABUP 0 2 2k

  在环境表0（_ENV）中将常量2"none"的值设置为常量2 （"none"） 的值。注意这里，这个"none"既用做了常量名也用作了字符串值。

• MOVE 3 1

  将寄存器 1 的值（即 print 函数）复制到寄存器 3。

• GETTABUP 4 0 2

  从环境表0的值（_ENV）中获取常量2 （"none"） 的值（即"none"），存入寄存器 4。

• CALL 3 2 1

  调用位于寄存器3的函数（即print函数），有2-1=1个参数，1-1=0个返回值。

• RETURN 3 1 1

  终止函数执行并返回执行结果。第一个参数表示返回值的其实位置，第二个参数返回值的个数，第三个参数是个标志位，为1时表示需要保留闭包或处理变长参数。具体细节之后章节实现CallInfo时进一步深入。

到这里，我们过了一遍这节要解释执行的代码的官方实现。考虑到这篇笔记内容比较长，而且内容比较完整，这节的笔记将分上下篇，将在下篇介绍用rust的实现。

实现

拓展词法分析器

上一节因为只需要分析print "Hello, world!"这样只有两个词法单元的语句，所以词法分析器的逻辑非常简单。这节我们的第一步就是拓展词法分析器，拓展后支持的词法单元如下：

#[derive(Debug, PartialEq)]
pub enum Token {
//  keywards
    And,    Break,  Do,     Else,   Elseif, End,
    False,  For,    Function, Goto, If,     In,
    Local,  Nil,    Not,    Or,     Repeat, Return,
    Then,   True,   Until,  While,

//  +       -       *       /       %       ^       #
    Add,    Sub,    Mul,    Div,    Mod,    Pow,    Len,
//  &       ~       |       <<      >>      //
    BitAnd, BitXor, BitOr,  ShiftL, ShiftR, Idiv,
//  ==       ~=     <=      >=      <       >        =
    Equal,  NotEq,  LesEq,  GreEq,  Less,   Greater, Assign,
//  (       )       {       }       [       ]       ::
    ParL,   ParR,   CurlyL, CurlyR, SqurL,  SqurR,  DoubColon,
//  ;               :       ,       .       ..      ...
    SemiColon,      Colon,  Comma,  Dot,    Concat, Dots,

    Integer(i64),
    Float(f64),

    Ident(String),
    String(String),
    Eos
}

如教程里说的一样，增加这些词法规则不过是繁琐的字符串解析。每次向前看一个词素，逐词素匹配词法单元，代码见lexer.rs。为了方便查看词法分析的结果，添加一个可以单独执行的词法分析器，对我们这节要实现的代码执行cargo run --bin lexer -- assets/02_variable.lua可得到如下结果：

Local
Ident("s")
Assign
String("Where is rua?")
Local
Ident("print")
Assign
Ident("print")
Ident("print")
ParL
Ident("s")
ParR
Ident("none")
Assign
Nil
Local
Ident("thezzw")
Assign
Ident("none")
Ident("print")
ParL
Ident("thezzw")
ParR
Ident("none_alias")
Assign
Ident("none")
Ident("print")
ParL
Ident("none_alias")
ParR
Ident("none")
Assign
String("none")
Ident("print")
ParL
Ident("none")
ParR

拓展Lua值

上节定义了三个值，分别是Nil、String(String)和Function(fn (&mut ExeState) -> i32)。随着支持的词法单元的增加，Lua值也需要提供对应的支持，拓展后的Lua值如下：

#[derive(Default, Clone)]
pub enum Value {
    Function(fn(&mut ExeState) -> i32),
    String(String),
    Integer(i64),
    Float(f64),
    Boolean(bool),
    #[default]
    Nil
}

默认值为Nil，Value的default()方法将会返回Nil。相比上一节，增加了三个简单类型Integer(i64)、Float(f64)和Boolean(bool)。Value没有实现Copy特型，因为String没有实现Copy，这也意味着即使是其他只包含简单类型的Value值在赋值时也会发生所有权的转移。

拓展语法分析器

Lua使用的是寄存器式的虚拟机，因此生成的三地址指令中会包含操作数的地址。上一节中，函数和参数的位置分别固定在栈的0和1位置，如图：

fn rs_print(state: &mut ExeState) -> i32 {
    println!("{}", state.stack[1]);
    0
}

而现在支持了局部变量，栈上会多出定义的局部变量，因此调用函数时就需要动态确定函数和参数的位置。在官方实现中，OP_CALL的逻辑我们已经在引言部分做过分析，包括函数的位置、入参个数和返回值个数三个值的信息。这节中，我们只实现函数位置的确定逻辑，参数个数在函数中确定，同时忽略返回值的逻辑，比如print接受一个入参，那么print的代码如下：

fn rs_print(state: &mut ExeState) -> i32 {
    println!("{}", state.stack[state.func_index + 1]);
    0
}

要确定被调用函数的位置，就要知道当前有多少局部变量，栈顶的位置在哪里，然后将函数和入参按顺序入栈。因此，在语法分析时，需要一个保存当前有多少局部变量的数据结构，为此在ParseProto（对应上节实现中的Parser，叫ParseProto更符合该数据结构的行为）中增加locals字段。拓展后的ParseProto如下：

pub struct ParseProto {
    pub constants: Vec<Value>,
    pub bytecodes: Vec<Bytecode>,

    locals: Vec<String>,
    lexer: Lexer,
}

同时，上节定义的字节码在需要实现这节的功能也有点力不从心了，因此字节码也需要进行拓展，参考引言中的分析，拓展后的字节码如下：

#[derive(Debug)]
pub enum Bytecode {
    GetGlobal(u8, u8),
    SetGlobal(u8, u8),
    SetGlobalConst(u8, u8),
    SetGlobalGlobal(u8, u8),
    LoadConst(u8, u16),
    LoadNil(u8),
    LoadBool(u8, bool),
    LoadInt(u8, i16),
    Move(u8, u8),
    Call(u8, u8),
}

可以看到现在有三种SetGlobal开头的字节码，如教程里所说，有点多余了。从我们在引言里的分析可以看出，官方实现里这三种字节码的功能都由SETTABUP实现。总之，有了以上的准备工作，就可以实现带局部变量的函数调用了，拓展后的函数调用的生成式方法如下：

fn call_function(&mut self, name: String) {
    let ifunc = self.locals.len();
    let iarg = ifunc + 1;
    let code = self.load_var(ifunc, name);
    self.bytecodes.push(code);
    match self.lexer.next() {
        Token::ParL => {
            self.load_exp(iarg);
            if self.lexer.next() != Token::ParR {
                panic!("expected `)`");
            }
        },
        Token::String(s) => {
            let code = self.load_const(iarg, Value::String(s));
            self.bytecodes.push(code);
        },
        _ => panic!("expected `(` or string")
    }
    self.bytecodes.push(Bytecode::Call(ifunc as u8, 1));
}

ifunc为栈顶的位置，iarg这里固定为ifunc的下一个位置，会在以后拓展以支持入参列表。目前call_function会固定生成三个字节码，三个字节码的作用分别是将函数压入栈顶、将入参压入栈顶和调用栈中函数。和官方实现一致，这里也是用递归下降分析法的一种简单形式————预测分析法（见编译原理2.4.2节），来实现文法的解析，并在生成式的特定位置执行字节码的生成动作。预测分析法要求所有文法的FIRST()集不相交，显然Lua的文法满足这个规则。如果在产生式的某个点上，预期的终结符号和下一个词法单元不符合（终结符号一般和词法单元用作同义词，在语法分析语境下叫终结符号，在词法分析语境下叫词法单元），则汇报一个语法错误。这里，遇见语法错误会直接panic!，翻到教程最后一章，作者在最后也没有用自定义的错误类型实现规范化的错误处理，不过毕竟本教程仅作教学目的，panic!似乎已经够用。至于call_function中用到的load_var和load_exp方法，此处也不多赘述，都是生成式规则的语言化实现。学到这里，再去看lparser.c中的官方实现理解起来也就相对没那么晦涩了。执行cargo run --bin rlua -- assets/02_variable.lua查看结果：

constants: [
   String("Where is rua?"), 
   String("print"), 
   String("none"), 
   Nil, 
   String("none_alias")
]
bytecodes: [
   LoadConst(0, 0), 
   GetGlobal(1, 1), 
   Move(2, 1), 
   Move(3, 0), 
   Call(2, 1), 
   SetGlobalConst(2, 3), 
   GetGlobal(2, 2), 
   Move(3, 1), 
   Move(4, 2), 
   Call(3, 1), 
   SetGlobalGlobal(4, 2), 
   Move(3, 1), 
   GetGlobal(4, 4), 
   Call(3, 1), 
   SetGlobalConst(2, 2), 
   Move(3, 1), 
   GetGlobal(4, 2), 
   Call(3, 1)
]
Where is rua?
nil
nil
none

执行结果符合预期，生成的常量的数量和顺序都和官方实现一致，字节码是18个，相比官方实现少了3个，分别是引言中的第1、12、21个字节码。

小结

本节主要工作是对上节的内容加以拓展，以支持变量的赋值，引入局部变量并完善了函数的调用的语法分析流程。

本节代码：02-variable

前言

出于学习的目的，想通过从头实现Lua解释器的方式来对Lua有更深入的了解。正好学习Rust也有段时间了，于是找了份用Rust实现Lua的教程，动手实现一下。这个系列的文章将基本是学习这篇教程的课程笔记。

01-Hello, world!

这节的目标是实现一个简单的，只能解析print "Hello, world!"这样只有两个Token的简单语句的解释器。虽然简单，但是完整的包含了一个Lua解释器需要的词法分析生成Token流、语法分析生成字节码（没有生成抽象语法树的环节）、虚拟机执行字节码三个部分。

词法解析生成Token流

数据结构定义

• Token

  用来表示Lua的词法单元，在官方的C实现中，Token是一个结构体（见llex.h中定义的Token），包括一个表明token类型的int值和token语法信息的SemInfo。在Rust中，这个结构可以用TagedUnion，即SumType实现。教程里Token::Ident(String)叫做Token::Name(String)，从含义上感觉叫Ident更合适一点，也对应Rust宏里的片段类型ident。

  #[derive(Debug)]
  pub enum Token {
      Ident(String),
      String(String),
      Eos,
  }

• Lexer

  对应官方C实现中的LexState，但是考虑我们当前只需要实现一条简单的语句，所以不用太复杂，定义如下。包含一个类型别名type LexerBytes = Peekable<Bytes<File>>;，教程里，这里是一个std::fs::File类型的字段表示输入文件，此处做简单预处理，转成u8类型的迭代器。

  pub struct Lexer {
      bytes: LexerBytes
  }

  算法实现

  使用DFA（确定有限状态自动机），读取代码文件字节流，以字节为单位，逐个ASCII字符匹配Token。见Lexer的next方法。

  pub fn next(&mut self) -> Token {
    loop {
        let next_byte = self.bytes.next();
        match next_byte {
            Some(Ok(byte)) => {
                match byte as char {
                  // TLDR, DFA.
                }
            },
            Some(Err(e)) => panic!("Error reading token: {}", e),
            _ => break Token::Eos
        }
    }
  }

  或许这里可以返回一个Iterator<Item = Token>类型的迭代器?

语法分析生成字节码

数据结构定义

• ByteCode

  Lua官方的实现是用32位的无符号整数表示一个字节码，前7位是op类型，即最多128种字节码，后25位作为参数，按位划分成了5种格式。而LuaJit则使用了更简单的字节码格式，同样是使用32位无符号整数，以字节位最小的单位，划分了2种格式。在Rust里，我们用TagedUnion来表示字节码，和LuaJit一样，字节是最小的控制单位。代码如下，值得一提的是，当前只有3种字节码，ByteCode的大小为3字节即24位。

  #[derive(Debug)]
  pub enum Bytecode {
      GetGlobal(u8, u8),
      LoadConst(u8, u8),
      Call(u8, u8)
  }

• Value

  Lua是动态类型语言，类型与值绑定，也就意味着从底层看，Lua的每种值都是同一种类型。在C中，可以用union这种数据结构来表示（见lobject.h中定义的Value），在Rust中，同样可以用TagedUnion轻松的实现这一点（暴论：所有语言都应该有SumType）。定义如下，当前只包括三种值，或者说实现print "Hello, world!"只需要这三种值。

  #[derive(Clone)]
  pub enum Value {
      Nil,
      String(String),
      Function(fn (&mut ExeState) -> i32),
  }

• Parser

  负责语法分析，用Token流生成字节码，同时记录常量值等必要的语法信息。在官方实现中，可以从lua.c中的doREPL函数开始，逐层深入lparser.c中的statement和expr函数，东西很多，但这里我们只需要最简单的逻辑，毕竟我们的目标也很简单。定义中包括constants和bytecodes两个字段，分别存放从Token流中记录的常量和解析出的字节码。

  pub struct Parser {
      pub constants: Vec<Value>,
      pub bytecodes: Vec<Bytecode>
  }

  算法实现

  采用自顶向下的方法，因为这节要实现的逻辑很简单，不多赘述。见Parser的load方法。

  pub fn load(mut lexer: Lexer) -> Self {
    let mut constants = Vec::new();
    let mut bytecodes = Vec::new();
  
    loop {
        match lexer.next() {
            Token::Ident(ident) => {
                constants.push(Value::String(ident));
                bytecodes.push(Bytecode::GetGlobal(0, (constants.len(- 1) as u8));
  
                if let Token::String(s) = lexer.next() {
                    constants.push(Value::String(s));
                    bytecodes.push(Bytecode::LoadConst(1, (constantlen() - 1) as u8));
                    bytecodes.push(Bytecode::Call(0, 1));
                } else {
                    panic!("Expected string after ident.");
                }
            }
            Token::Eos => break,
            _ => panic!("Unexpected token.")
        }
    }
  
    Self { constants, bytecodes }
  }

虚拟机执行字节码

数据结构定义

• ExeState

  包含虚拟机的状态和执行逻辑，参考lstate.h中定义的lua_State，此处只包含两个字段globals和stack，分别用于保存全局变量和用作函数执行栈。

  pub struct ExeState {
      globals: HashMap<String, Value>,
      stack: Vec::<Value>,
  }

  算法实现

  逐字节码执行对应逻辑，实现简单的参数入栈函数调用逻辑。官方的完整实现在lvm.c的luaV_execute函数。当前实现见ExeState`execute`方法。

  pub fn execute(&mut self, proto: &Parser) {
    for bytecode in &proto.bytecodes {
        match *bytecode {
            Bytecode::GetGlobal(stack_dst, const_idx) => {
                match &proto.constants[const_idx as usize] {
                    Value::String(key) => {
                        let global_value = self.globals.get(key).unwrap_or(&Value::default()).clone();
                        self.set_stack(stack_dst, global_value);
                    },
                    unknown => panic!("Unexpected global key: {:?}", unknown)
                };
            },
            Bytecode::LoadConst(stack_dst, const_idx) => {
                let const_value = proto.constants[const_idx as usize].clone();
                self.set_stack(stack_dst, const_value);
            },
            Bytecode::Call(func, _) => {
                let func = &self.stack[func as usize];
                match func {
                    Value::Function(f) => {
                        f(self);
                    },
                    unknown => panic!("Expected function: {:?}", unknown)
                }
            }
        }
    }
  }

小结

本章搭建了一个简单但相对完整的，可以解释执行print "Hello, world!"的Lua解释器。内容简单明了，Lua的官方源码虽然不多，但是一次性全部掌握还是比较困难。后面跟着教程循序渐进，会逐渐深入Lua的实现细节。
本节代码：01-Hello,world!

因为过于相信明天的自己，这篇本来应该在过完年回来就写的文章拖到了今天，拖延症真可怕。内容如题，是对今年要做的事做一些简单规划，当然这里只说代码上的事。目前手上一共有4个开发中的项目，或者说4个学习用的玩具更合适一点，均是使用rust语言。它们分别是：

• xnum
  一个定点数数学库，包括使用CORDIC算法实现的高效三角函数计算、以safe_作为前缀的各种定点数安全的数学方法、使用梅森旋转算法实现的简单伪随机数以及诸如vec2、vec3、mat2、mat3、euler、quat等各种常见的数据结构及其方法的定点数实现。
• horizon_eye
  一个bevy的相机控制插件，目前包括自由飞行、目标跟随和正交拖动三种模式，可以在运行时任意切换模式，很简陋，纯玩具，但名字取得还不错。
• xcollider
  一个用xnum实现的碰撞检测库，用定点数实现了碰撞检测的基本流程，核心是使用GJK+EPA算法实现多边形的碰撞检测以及最短分离距离的计算，对圆形正方形等简单的形状使用分离轴等更简单高效的算法。
• rlua
  一个用rust实现lua的项目，刚刚开始，基本是这篇教程的课程作业——《用Rust实现Lua解释器》，当然，会夹杂一些我认为更好的写法。

其中前三个玩具已经做了有一段时间了，断断续续有了一点点模样，但感觉暂时可能不会继续做了，考虑到AI发展这么快，继续花时间去写这些具体的算法好像没那么划算，了解学习还是可以的。至于rlua，是为了学习lua源码而开始的项目，希望自己能尽快完成吧，目标放低点，一周至少一个章节。

rlua这个完成之后，可能会去继续膜拜一下bellard大佬的quickjs，但这就是后话了，不给自己压力，想学再说，网上似乎也没有像《用Rust实现Lua解释器》这样比较好的教程去跟着实现quickjs了。

0:12了，明天还要上班，就到这里，多的之后再说。