Rust 之不可为 (1) 暴露内部结构

原文

发现很多人在学习Rust期间会不约而同地尝试做一些事情,然后不约而同地做chongxie了le很hen久duobian,最后和最初的设想大相径庭。为什么呢?其实根本原因是不够了解Rust的特性。Rust是一个有自己“性格”的语言,对 很多事情的观点都是很鲜明的,意思是,有一些事情是它在明确反对的。按照Rust反对的方法做事情,能不能成功呢?或许吧,反正肯定不会很快乐就是了。

似乎目前还没有文章认真的讨论这些事情为什么不能做,怎么做才是正确的。于是新的系列就这样出炉啦。这一次我们来看一个最简单的例子:暴露内部结构。先看结论,稍后我们再来举例解释。

结论

在设计中不可以把不同抽象层次的结构放在相同层次上。内部结构不可以用& &mut 来引用外层结构。正确的思路有1. 运用共享、Cell机制共有共享的内层结构(而非外层结构本身) 2. 使用索引或者模拟的指针来把主动使用变成被动使用 3. 运用裸指针机制。

示例

我们来设计一个单向链表吧。

错误的示范1:

struct ForwardList<T> {
     data: T,
     next: Option<Box<ForwardList<T>>>,
}

错误的示范2:

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}
type ForwardList<T> = Option<Node<T>>;

正确的做法1(运用共享、Cell机制,在ForwardList的例子里不需要,只要Box即可):

struct Node<T> {
   data: T,
   next: Option<Box<Node<T>>>,
}
struct ForwardList<T> {
   head: Option<Box<Node<T>>>,
}

正确的做法2(运用索引、模拟指针机制):

struct Node<T> {
  data: T,
  next: Option<usize>,
}
struct ForwardList<T> {
  nodes: Vec<Node<T>>,
  head: Option<usize>,
}

更新(2018年3月9日):对于这种方法,话说carllerche君写了个挺好用的库,叫slab。推荐~

extern crate slab;
use ::slab::Slab;

struct Node<T> {
  data: T,
  next: Option<usize>,
}
struct ForwardList<T> {
  nodes: Slab<Node<T>>,
  head: Option<usize>,
}

正确的做法3(运用裸指针):

struct Node<T> {
  data: T,
  next: * mut Node<T>,
}
struct ForwardList<T> {
  head: * mut Node<T>,
}

对错误做法的解释

看了上面的例子,有人会说。噫,我用上面两个错误的版本,也用得好好的。没什么问题嘛。

当你尝试把问题推广一点。比如推广到图、树,甚至于最简单的双向链表。你会发现错误的版本都是没有办法直接照搬过去的。为什么呢?

根本原因就在于ForwardList 和 Node 不是同一个层级的事物。标准库里的Mutex和MutexGuard是同一个层级的事物,所以MutexGuard引用Mutex是没有问题的。而在这里,Node是ForwardList的一部分。ForwardList是Node的所有者,但不是struct对field的那种所有者。在Rust的规则下,在Node的层级你在通常情况下不可以谈起你的主人:ForwardList。

为什么不可以呢?因为借用Node的唯一途径就是透过作为主人的ForwardList来借用。ForwardList在这个时候一定处于借用状态,如果Node处于不变借用&状态,ForwardList也最多只能获得一个不变借用。如果Node处于可变借用&mut状态,从Node的角度看ForwardList一定是锁定无法访问的。

所以当你犯了以上错误,在你写读方法(比如各种getter)的时候不会遇到任何阻碍,但是当你使用修改状态的方法的时候,你会处处碰壁。利用内部可变性你可以绕过一些问题,但是今后的生活一定会不好过。

当然有人会说:以函数式编程的名义,我不修改状态不就行了?嗯……可以……你大概会发现你需要经常Clone一些东西=。=

对正确做法的解释

第一种方法把Rust的所有权模型套入内部结构中。如果是简单的单链或者树状模型,用Box就可以,视情况考虑是否用Cell/RefCell(一般不用)。如果是有向图,要用Rc/Weak套装。制订一个规则,从里面选出一个所有权的有向无环图,然后有所有权的引用用Rc,没有所有权的引用用Weak。如果需要修改再在里面套一个Cell/RefCell。这种设计适合写一些业务,偶尔也用来完成一些非通用的设计。还有就是新手的练习喜欢这么做。(补充:警示:这个办法可能会造成析构函数的深层级调用,数据规模稍大时,就可能会栈溢出。)

第二种方法是比较通用的,适合于树、图和其他类似Composite Design Pattern的情况。方法就是把节点存储在一起,边(如果有的话)存储在一起。(存储时可以考虑用各种arena机制哦。)然后用索引之类的机制进行访问。Rust库里有一个叫petgraph,专用于这种情况。需要的话可以看看是否直接用这个会比较好。

第三种方法适合于比较紧凑的通用数据结构。方法就是利用裸指针或者标准库里的Unique/Shared来自行管理内存。(写起来跟C/C++没啥区别。)写好后封装成一个单独的crate,然后使用安全的接口访问 。嘛,标准库libcollections里的都是这一种 。http://crates.io上也有一些。

Last modification:March 6th, 2021 at 12:12 am
安安,亲觉得有用, 请随意打赏嗷