话说知识推理系列坑的时间有点久,所以感觉在此期间写点别的也不错……刚好 距离第一篇博文发布正好一周年,就写点简单的东西吧。(x)

Rust 所有权系统

也许一些读者并不知道 Rust 是什么,更不知道 Rust 的所有权系统是什么(等 等你的博客有读者吗?),所以为了文章的完整性(和凑字数),首先介绍一下 Rust 的所有权系统。

那么什么叫所有权呢?简单地说,Alice 对 Bob 有着完全的控制(这里请 把 Alice 和 Bob 理解为两个东西),那么就说 Alice 拥有 Bob(Alice owns Bob),或者说 Bob 被 Alice 拥有(Bob is owned by Alice)。

换种说法,Bob 就活在 Alice 的肚子里,Bob 的生与死完全决定于 Alice。如 果拥有关系很复杂,我们就能画出一棵树。

这时,我们发现要手动管理这堆关系是比较困难的。于是聪明的人们发明了 RAII,试图把资源和编程语言中的对象绑定在一起。

在有 RAII 的语言中,「拥有」这回事是和资源的申请和释放息息相关的。毕竟, RAII 的全称是「资源获取即初始化」(Resource acquisition is initialization),即把资源获取与对象初始化画上等号,这就是构造函数的由 来。那么反过来说,对象被销毁也就对应了资源的释放。Rust 就从 C++ 这里借 鉴来了 RAII(特指析构函数)。

但请注意,虽然我们把资源编码成了对象,但语言并不会去检查这些对象之间的 关系究竟如何。比方说,一块内存我们用一个指针去表示,但 Alice 和 Bob 都 声称自己拥有这个指针,并在里面涂涂画画、或者去释放这块内存,就有可能导 致程序行为诡异,甚至崩溃。

通过大量的实践,人们发现「拥有」这个关系是排他性的,即若 Alice 拥有 Bob,那么 Cathy 就不可能拥有 Bob,但 Cathy 可以拥有 Alice 来间接拥有 Bob。有点像封建制度。 :-p

如果别人想借用 Alice 的 Bob,或者 Alice 对 Bob 不满意,想让别人修理一 番,那么 Alice 可以选择两种出借方法:

  1. 共享借用:只借给别人看,不准别人去写;
  2. 可写借用:只借给一个人,但允许这个人修改 Bob。(如果有多个人同时写, 那 Bob 可能会被整得很惨,最后无法工作了。)

或者,Alice 不想要 Bob,那么 Alice 可以把 Bob 原原本本地转交给另一个人, 称为 Bob 的移动(准确说,是 Bob 所有权的移动)。

事实上,所有权(ownership)的概念并不只有 Rust 一家有,但 Rust 是 第一个把所有权管理做到语言中、并且作为核心概念的语言。

用实际的代码来说,就是

struct Woman {
    husband: Option<String>
}

let mut alice = Woman {
    husband: Some(String::from("Bob"))
};

let mut cathy = Woman {
    husband: None
};

// 把 Bob 借给别人
fix_my_car(&alice.husband);
have_a_better_hairstyle(&mut alice.husband);

// 把 Bob 丢给别人
cathy.husband = alice.husband.take();

借用,或称引用,在 Rust 中的用得很广泛,因此借用也有一些特殊的设计,比 如生命周期参数,要求引用本身活得不长于被指向的对象。

滑铁卢之双向链表

Rust 试图把每个对象的所有权和生命周期都安排得明明白白,但天下哪有这么 好的事情?Rust 的检查是完全发生在编译时的,如果所有权或者对象的生命周 期稍微动态一点,那就彻底抓瞎了。此外,如果引用或者所有权是循环的,那自 求多福吧。

举个简单的例子,双向链表。首先你不能把节点自己放到自己里面,原因很简单, Node<T> 的大小无法确定。

struct Node<T> {
    val:  T,
    prev: Node<T>,
    next: Node<T>,
}

其次,你不能这样写,因为 Rust 没有空指针,(这里面的 'a 可以暂且无视掉。)

struct Node<'a, T: 'a> {
    val: T,
    prev: &'a Node<'a, T>,
    next: &'a Node<'a, T>,
}

那我用 Option 包一下总可以吧,

struct Node<'a, T: 'a> {
    val: T,
    prev: Option<&'a Node<'a, T>>,
    next: Option<&'a Node<'a, T>>,
}

不好意思,同一个 Node 会被多次 borrow……

那么问题的根源出在哪里呢?仔细思考后发现,是因为抽象出了问题。用户面对 的是一个单独的 List。我们可以这样说,列表对象(List 类型)拥有列表 头,列表头拥有元素 1,元素 1 拥有元素 2,元素 2 拥有元素 3……反过来, 3 可以看到 2,2 可以看到 1,1 可以看到列表头。至于这个说法对不对暂且不 论,至少它理论上可以在 Rust 中工作。

在 Rust 中,在语法上拥有 T 类型对象的的唯一手段是把 T 放到自己里面来。 这是一个巨大的限制。我们应该有一种表达逻辑拥有的手段,绕过这个限制,不 是吗?

相反,C++ 中可以通过原始指针轻易绕过这个困难:存储在哪里?放在堆上就行 了。如何访问和释放?只要有原始指针即可。Rust 为了内存安全性选择把原始 指针限定在 unsafe Rust 中。如果没有安全强迫症,我们现在改用 unsafe 其实是非常合情合理的选择。

滑铁卢之有向有环图

我之前尝试用 Rust 写一个确定性有限状态自动机,一开始就遇到了和双向链表 类似的困难。但在此处,问题就更大了,由于状态图可能有环,也可能有多个入 边出边,这导致类似于链表的链式所有权关系连理论上的存在性都没有。

不过,我们可以很快观察到,一个 DFA 的状态图其实是很少进行改变的(暂且 称为头号假设),所以可以首先把所有状态预先分配好,然后用别的手段对 状态进行引用。一个很自然的想法就是使用 Vec

type StateId = usize;

struct State {
    accept: bool,                       // 是否是接受状态
    transitions: Vec<(char, StateId)>,  // 转移函数
}

let states = vec![
    State::new(false),
    State::with_transitions(false, vec![('a', 2), ('b', 1)]),
    State::with_transitions(false, vec![('b', 3)]),
    State::new(true),
];

这里的转移函数的意思是,现在在这个状态,如果丢进来一个字符 c,那么就 转移到字符 c 指向的下一个状态,而状态号是完全由 states 的下标决定 的。

通过这种方法,我们把所有 State 对象的所有权交给了 states 这个 Vec,然后用下标访问,完全绕过了借用这个麻烦的东西。由于有头号假设, 也比较容易人工检查正确性。

现在一定有人会问:如果下标写错了,不就和野指针差不多了吗?程序照样会 panic 然后挂掉呀!唔,其实确实如此。但首先,我们是为了绕过 Rust 语言 限制不得不出此下策;其次,我们完全避免了未定义行为:解引用野指针——这是 因为 Rust 定义了 Vec 越界的行为:panic

抽象:slab 与 slot map

那么把上面两节放在一起看,实际上通过 Vec 的方法,我们发明了另一套堆 存储和指针系统。这样看来,我们是发明了一种新的分配器——这实际上就是 slab 分配器

回头看一下,头号假设(数据不常变动)事实上可以轻易地被消除掉,即不立即 删除掉这个位置,而是回收留待之后使用(很类似堆的行为)。

但我们引入了一个新的假设,就叫二号假设吧:所有元素必须是单一类型的。 不过这一点问题倒不是很大,因为我们可以使用多个这样的分配器,也可以用 enum 把不同类型的数据纠结在一起。而二号假设又保证了我们可以高效地进 行数据分配与管理!

但是 slab 分配器有一个致命缺陷,你注意到了吗?假如 A 引用了 B,而 B 被 释放后又立即在原位插入 B',那么从 A 就会读到 B'。这对一些数据结构来说 是致命性的!

extern crate slab;

use slab::Slab;

struct Node {
    message: String,
    reference: Option<usize>,
}

fn main() {
    let mut s = Slab::with_capacity(2);
    let hello = s.insert(Node { message: "hello".to_string(), reference: None });
    let world = s.insert(Node { message: "world".to_string(), reference: None });
    s[hello].reference = Some(world);
    s.remove(world);
    s.insert(Node { message: "earth".to_string(), reference: None });
    println!("{} {}", s[hello].message, s[s[hello].reference.unwrap()].message);
}

上面这段代码,(毫不令人意外地)会打印 "hello earth" 而非 "hello world" 或者 panic 掉。

slotmap 通过版本标记解决了这个问题, 即 Key 不单单是一个 usize,而是

pub struct Key {
    idx: u32,
    version: u32,
}

假如索引到的新数据是空,或者版本比 Key 中的版本高,就说明之前的数据 已经被删除了,所以将索引失败。

slotmap 的一次访问会比 slab 和普通的解引用高出不少:毕竟还要版本比较一 次。但这也是为了安全所付出的一点代价罢。现在使用 slotmap 我们就可以 轻易实现双向链表了。 不过要我说,如果能证明安全性,用用 unsafe 也没什么不好的,而且效率肯定比 slotmap 高(毕竟 C++ 这么多年都过来了)。