Unicode和UTF-8

本章的前面三节优化了字符串相关内容，理清了一些问题，但也引入了一些混乱。比如Value中的3个字符串类型的定义，有的是[u8]类型，有的是String类型：

pub enum Value {
    ShortStr(u8, [u8; SHORT_STR_MAX]),  // [u8]类型
    MidStr(Rc<(u8, [u8; MID_STR_MAX])>),  // [u8]类型
    LongStr(Rc<String>),  // String类型

再比如上一节中“字节”和“字符”混用。词法分析的代码也是这样，从输入字符流中读取字节u8类型，但通过as转换为字符char类型。

    fn read_char(&mut self) -> char {
        match self.input.next() {
            Some(Ok(ch)) => ch as char,  // u8 -> char

目前这些混乱之所以还没有造成问题，是因为我们的测试程序只涉及了ASCII字符。如果涉及其他字符，就会出问题。比如对于如下Lua代码：

print "你好"

执行结果就是错误的：

$ cargo r -q --  test_lua/nihao.lua
constants: [print, 你好]
byte_codes:
  GetGlobal(0, 0)
  LoadConst(1, 1)
  Call(0, 1)
你好

输出的结果并不是预期中的你好，而是你好。有没有想起“手持两把锟斤拷，口中疾呼烫烫烫”？下面就来解释这个“乱码”出现的原因，并修复这个问题。

Unicode和UTF-8概念

这两个都是非常通用的概念，这里只做最基本的介绍。

Unicode对世界上大部分文字进行了统一的编码。其中为了跟ASCII码兼容，对ASCII字符集的编码保持一致。比如英文字母p的ASCII和Unicode编码都是0x70，按照Unicode的方式写作U+0070。中文你的Unicode编码是U+4F60。

Unicode只是对文字编了号，至于计算机怎么存储就是另外一回事。最简单的方式就是按照Unicode编码直接存储。由于Unicode目前已经支持14万多个文字（仍然在持续增加），那至少需要3个字节来表示，所以英文字母p就是00 00 70，中文你就是00 4F 60。这种方式的问题是，对于ASCII部分也需要3个字节表示，（对于英文而言）造成浪费。所以就有其他的编码方式，UTF-8就是其中一种。UTF-8是一种变长编码，比如每个ASCII字符只占用1个字节，比如英文字母p编码仍然是0x70，按照UTF-8的方式写作\x70；而每个中文占3个字节，比如中文你的UTF-8编码是\xE4\xBD\xA0。UTF-8更详细的编码规则这里省略。下面是几个例子：

字符 | Unicode编号 | UTF-8编码
----+------------+---------------
p   |  U+0070    | \x70
r   |  U+0072    | \x72
你  |  U+4F60    | \xE4\xBD\xA0
好  |  U+597D    | \xE5\xA5\xBD

乱码分析

介绍完编码概念，再来分析本节开头的Lua测试代码出现乱码的原因。用hexdump查看源码文件：

$ hexdump -C test_lua/nihao.lua
00000000  70 72 69 6e 74 20 22 e4  bd a0 e5 a5 bd 22 0a     |print "......".|
#         p  r  i  n  t     "  |--你---| |--好---| "

其中最后一行是我添加的注释，表示出每个Unicode文字。可以看到p和你的编码，跟上面介绍的UTF-8编码一致。说明这个文件是UTF-8编码的。文件的编码方式取决于使用的文字编辑器和操作系统。

我们目前的词法分析是逐个“字节”读取的，所以对于中文你，就被词法分析认为是3个独立的字节，分别是e4、bd和a0。然后再用as转换为char。Rust的char是Unicode编码的，所以就得到了3个Unicode文字，通过查询Unicode可以得到这3个文字分别是ä、½和 （最后一个是个空白字符），这就是我们开头遇到的“乱码”的前半部分。后面的好对应乱码的后半部分。这6个字节代表的6个文字，被依次push到Token::String（Rust的String类型）中，最终被println!打印出来。Rust的String类型是UTF-8编码的，不过这个倒是不影响输出结果。

概括下乱码出现的过程：

• 源文件是UTF-8编码；
• 逐个字节读取，此时UTF-8编码已被支离；
• 每个字节被解释为Unicode，导致乱码；
• 存储和打印。

还可以通过Rust编码再次验证下：

fn main() {
    let s = String::from("print 你好");  // Rust的String是UTF-8编码，所以可以模拟Lua源文件
    println!("string: {}", &s);  // 正常输出
    println!("bytes in UTF-8: {:x?}", s.as_bytes());  // 查看UTF-8编码

    print!("Unicode: ");
    for ch in s.chars() {  // 逐个“字符”读取，查看Unicode编码
        print!("{:x} ", ch as u32);
    }
    println!("");

    let mut x = String::new();
    for b in s.as_bytes().iter() {  // 逐个“字节”读取
        x.push(*b as char);  // as char，字节被解释为Unicode，导致乱码
    }
    println!("wrong: {}", x);
}

点击右上角可以运行看结果。

乱码问题的核心在于“字节”到“字符char”的转换。所以有2种解决方法：

1. 读取源代码时，修改为逐个“字符char”读取。这个方案问题比较大：

   • 上一节中我们介绍的Lex的输入类型是Read trait，只支持按照“字节”读取。如果要按照“字符char”读取，那就需要首先转换为String类型，就需要BufRead trait了，对输入的要求更严格了，比如字符串外封装的Cursor<T>就不支持。
   • 假如源代码输入是UTF-8编码，最后Rust的存储也是UTF-8编码，如果按照Unicode编码的“字符char”读取，那就需要UTF-8到Unicode再到UTF-8的两次无谓的转换。
   • 还有一个最重要的原因，接下来马上就会讨论的，Lua的字符串是可以包含任意数据，而不一定是合法的UTF-8内容，也就不一定能正确转换为“字符char”。

2. 读取源代码时，仍然逐个字节读取；在保存时，不再转换为“字符char”，而是直接按照“字节”保存。这就不能继续使用Rust的String类型来保存了，具体方案见下。

显而易见（只是现在看来显而易见，当初也是一头雾水，尝试了很久）应该选择第2个方案。

字符串定义

现在看下Lua和Rust语言中字符串内容的区别。

Lua中关于字符串的介绍：We can specify any byte in a short literal string。也就是说Lua的字符串可以表示任意数据。与其叫字符串，不如说就是一串连续的数据，而并不关心数据的内容。

而Rust字符串String类型的介绍：A UTF-8–encoded, growable string。简单明了。两个特点：UTF-8编码，可增长。Lua的字符串是不可变的，Rust的可增长，但这个区别不是现在要讨论的。现在关注的是前一个特点，即UTF-8编码，也就是说Rust字符串不能存储任意数据。通过Rust的字符串的定义，可以更好的观察到这点：

pub struct String {
    vec: Vec<u8>,
}

可以看到String就是对Vec<u8>类型的封装。正是通过这个封装，保证了vec中的数据是合法的UTF-8编码，而不会混进任意数据。如果允许任意数据，那直接定义别名type String = Vec<u8>;就行了。

综上，Rust的字符串String只是Lua字符串的子集；跟Lua字符串类型相对应的Rust类型不是String，而是可以存储任意数据的Vec<u8>。

修改代码

现在弄清了乱码的原因，也分析了Rust和Lua字符串的区别，就可以着手修改解释器代码了。需要修改的地方如下：

• 词法分析中Token::String关联的类型由String改为Vec<u8>，以支持任意数据，而不限于合法的UTF-8编码数据。

• 对应的，Value::LongStr关联的类型也由String改为Vec<u8>。这也就跟另外两个字符串类型ShortStr和MidStr保持了一致。

• 词法分析中，原来的读取函数peek_char()和read_char()分别改成peek_byte()和next_byte()，返回类型由“字符char”改成“字节”。原来虽然名字里是char，但实际上是逐个“字节”读取，所以这次不用修改函数内容。

• 代码中原来匹配的字符常量如'a'，要改成字节常量如b'a'。

• 原来的read_char()如果读取到结束，则返回\0，因为当时认为\0是特殊字符。现在Lua的字符串可以包含任意值，包括\0，所以\0就不能用来表示读到结束。此时就需要Rust的Option了，返回值类型定义为Option<u8>。

  但这就导致调用这个函数的地方不太方便，每次都需要模式匹配（if let Some(b) =）才能取出字节。好在这个函数调用的地方不多。但是另外一个函数peek_byte()调用的地方就很多了。照理说这个函数的返回值也应该改成Option<u8>，但实际上这个函数返回的字节都是用来“看一看”，只要跟几个可能路径都不匹配，就可以认为没有产生效果。所以这个函数读到结束时，仍然可以返回\0，因为\0不会匹配任何可能路径。如果真的读到结尾，那么就留给下一次的next_byte()去处理就行。

  正是Option带来的这个不方便（必须通过匹配才能取出值），才提现了其价值。我在C语言编程经历中，对于这种函数返回特殊情况的处理，一般都用一个特殊值来表示，比如指针类型就用NULL，int类型就用0或-1。这带来2个问题：一是调用者可能没有处理这种特殊值，会直接导致bug；二是这些特殊值后续可能就变成普通值了（比如我们这次的\0就是个典型例子），那所有调用这个函数的地方都要修改。而Rust的Option就完美解决了这两个问题。

• 词法分析中，字符串支持escape。这部分都是无趣的字符处理，这里省略介绍。

• 增加impl From<Vec<u8>> for Value，用以将Token::String(Vec<u8>)中的字符串常量转换为Value类型。这个又涉及很多Vec和字符串的细节，非常繁琐，且跟主线关系不大，下面再开两个小节专门介绍。

&str, String, &[u8], Vec到Value的转换

之前已经实现了String和&str到Value的转换。现在要增加Vec<u8>和&[u8]到Value的转换。这4个类型间的关系如下：

           slice
  &[u8] <---------> Vec<u8>
                      ^
                      |封装
           slice      |
  &str  <---------> String

• String是对Vec<u8>的一层封装。可以通过into_bytes()返回封装的Vec<u8>。
• &str是String的slice（可以认为是引用？）。
• &[u8]是Vec<u8>的slice。

所以String和&str可以分别依赖Vec<u8>和&[u8]。而且看上去Vec<u8>和&[u8]之间也可以相互依赖，即只直接实现其中之一到Value的转换即可。不过这样会损失性能。分析如下：

• 源类型：Vec<u8>是拥有所有权的，而&[u8]没有。
• 目的类型：Value::ShortStr/MidStr只需要复制字符串内容（分别到Value和Rc内部），无需获取源数据的所有权。而Value::LongStr需要获取Vec的所有权。

2个源类型，2个目的类型，可得4种转换组合：

         | Value::ShortStr/MidStr | Value::LongStr
---------+------------------------+-----------------
 &[u8]   |  1.复制字符串内容        | 2.创建Vec，申请内存
 Vec<u8> |  3.复制字符串内容        | 4.转移所有权

如果我们直接实现Vec<u8>，而对于&[8]就先通过.to_vec()创建Vec<u8>再间接转换为Value。那么对于上述第1种情况，本来只需要复制字符串内容即可，而通过.to_vec()创建的Vec就浪费了。

如果我们直接实现&[8]，而对于Vec<u8>就先通过引用来转换为&[u8]再间接转换为Value。那么对于上述的第4种情况，就要先取引用转换为&u[8]，然后再通过.to_vec()创建Vec来获得所有权。多了一次无谓的创建。

所以为了效率，还是直接实现Vec<u8>和&[u8]到Value的转换。不过，也许编译器会优化这些的，上述考虑都是瞎操心。但是，这可以帮助我们更深刻理解Vec<u8>和&[u8]这两个类型，和Rust所有权的概念。最终转换代码如下：

// convert &[u8], Vec<u8>, &str and String into Value
impl From<&[u8]> for Value {
    fn from(v: &[u8]) -> Self {
        vec_to_short_mid_str(v).unwrap_or(Value::LongStr(Rc::new(v.to_vec())))
    }
}
impl From<&str> for Value {
    fn from(s: &str) -> Self {
        s.as_bytes().into() // &[u8]
    }
}

impl From<Vec<u8>> for Value {
    fn from(v: Vec<u8>) -> Self {
        vec_to_short_mid_str(&v).unwrap_or(Value::LongStr(Rc::new(v)))
    }
}
impl From<String> for Value {
    fn from(s: String) -> Self {
        s.into_bytes().into() // Vec<u8>
    }
}

fn vec_to_short_mid_str(v: &[u8]) -> Option<Value> {
    let len = v.len();
    if len <= SHORT_STR_MAX {
        let mut buf = [0; SHORT_STR_MAX];
        buf[..len].copy_from_slice(&v);
        Some(Value::ShortStr(len as u8, buf))

    } else if len <= MID_STR_MAX {
        let mut buf = [0; MID_STR_MAX];
        buf[..len].copy_from_slice(&v);
        Some(Value::MidStr(Rc::new((len as u8, buf))))

    } else {
        None
    }
}

反向转换

之前已经实现了Value到String和&str的转换。现在要增加到Vec<u8>的转换。先列出代码：

impl<'a> From<&'a Value> for &'a [u8] {
    fn from(v: &'a Value) -> Self {
        match v {
            Value::ShortStr(len, buf) => &buf[..*len as usize],
            Value::MidStr(s) => &s.1[..s.0 as usize],
            Value::LongStr(s) => s,
            _ => panic!("invalid string Value"),
        }
    }
}

impl<'a> From<&'a Value> for &'a str {
    fn from(v: &'a Value) -> Self {
        std::str::from_utf8(v.into()).unwrap()
    }
}

impl From<&Value> for String {
    fn from(v: &Value) -> Self {
        String::from_utf8_lossy(v.into()).to_string()
    }
}

• 由于现在Value的3种字符串都是连续u8序列了，所以转换为&[u8]很简单。

• 到&str的转换，需要通过std::str::from_utf8()处理刚才得到的&[u8]类型。这个函数不涉及新的内存分配，只是验证下UTF-8编码的合法性。如果非法则失败，我们这里直接通过unwrap()来panic。

• 到String的转换，通过String::from_utf8_lossy()处理刚才得到的&[u8]类型。这个函数也是验证UTF-8编码的合法性，但如果验证失败则会用一个特殊字符u+FFFD来替换非法数据。但又不能直接修改原有数据，所以就会创建一个新的字符串。如果验证成功，则无需新创建数据，只返回原有数据的索引即可。这个函数的返回类型Cow也是值得学习。

上述两个函数的不同处理方式，是由于&str没有所有权，所以就不能创建新数据，而只能报错。可见所有权在Rust语言中非常关键。

Value到String的转换，目前的需求只是需要设置全局变量表时使用。可以看到这个转换总是会调用.to_string()来创建一个新字符串。这个使得我们这一章对字符串的优化（主要是第1节）都失去了意义。后续在介绍到Lua的表结构后，会把全局变量表的索引类型从String改为Value，届时操作全局变量表就无需这个转换了。不过在其他地方还是会用到这个转换。

测试

至此，Lua字符串的功能更加完整了。本节开头的测试代码也可以正常输出了。通过escape还可以处理更多的方式，用如下测试代码验证：

print "tab:\thi" -- tab
print "\xE4\xBD\xA0\xE5\xA5\xBD" -- 你好
print "\xE4\xBD" -- invalid UTF-8
print "\72\101\108\108\111" -- Hello
print "null: \0." -- '\0'

总结

本章学习了Rust字符串类型，涉及到所有权、内存分配、Unicode和UTF-8编码等，深刻体会到了《Rust程序设计语言》中说的：Rust的字符串是复杂的，因为字符串本身是复杂的。通过这些学习，优化了Lua的字符串类型，还涉及到泛型和From trait。虽然没有给我们的Lua解释器增加新特性，但也收获满满。