6.2 型变与子类型

4 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/sixth-variance.html

现在把这事拖到以后再修会很烦，所以我们现在就做硬核布局。

写 unsafe Rust 集合有五匹可怕的天启骑士：

幸运的是，后两个对我们不是问题。

第三个我们可以自找麻烦，但不值得——既然选了 LinkedList，内存效率这场仗你早就输了一百倍。

第二个我曾经坚持很重要、std 也会折腾，但默认是安全的，能折腾它的方式不稳定，而且你得极其努力才能注意到默认限制，所以别担心。

就剩方差了。老实说，这个你也可以先搁置，但我作为集合库作者的自尊还在，所以我们要做方差那套。

所以，惊喜：Rust 有子类型。具体来说，&'big T 是 &'small T 的子类型。为什么？因为如果某段代码需要存活于程序某区域的引用，给它存活更久的引用通常完全没问题。直觉上就是这样，对吧？

为什么重要？想象某段代码接受两个相同类型的值：

1
fn take_two<T>(_val1: T, _val2: T) { }

这段代码无聊透顶，用 T = &u32 应该没问题吧？

1
2
3
4
5
6
7
8
fn two_refs<'big: 'small, 'small>(
    big: &'big u32, 
    small: &'small u32,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }

嗯，编译通过！

来点乐子，包一层，比如 std::cell::Cell：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
use std::cell::Cell;

fn two_refs<'big: 'small, 'small>(
    // 注意：这两行变了
    big: Cell<&'big u32>, 
    small: Cell<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
error[E0623]: lifetime mismatch
 --> src/main.rs:7:19
  |
4 |     big: Cell<&'big u32>, 
  |               ---------
5 |     small: Cell<&'small u32>,
  |                 ----------- these two types are declared with different lifetimes...
6 | ) {
7 |     take_two(big, small);
  |                   ^^^^^ ...but data from `small` flows into `big` here

哈？？？生命周期没动，编译器为什么发火！？

啊，生命周期「子类型」肯定特别简单，包一层就崩了，看 Vec 也会崩：

1
2
3
4
5
6
7
8
fn two_refs<'big: 'small, 'small>(
    big: Vec<&'big u32>, 
    small: Vec<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }

1
2
   Finished dev [unoptimized + debuginfo] target(s) in 1.07s
     Running `target/debug/playground`

看，也不编译——等等什么？？？Vec 是魔法？？？？？

嗯，是。也不是。魔法一直在我们心里，那魔法就是 ✨方差✨。

想看血肉细节，读 nomicon 子类型章节。简单说，子类型并不总安全。尤其涉及可变引用时不安全，因为可以用 mem::swap 之类，然后悬垂指针，糟糕！

「类似可变引用」的东西是*不变的（invariant）**，会阻止泛型参数上的子类型。为安全，&mut T 对 T 不变，Cell<T> 对 T 也不变，因为 &Cell<T> 基本就是 &mut T（内部可变性）。

几乎不变的东西都是*协变的（covariant）**，子类型能「穿过去」照常工作（还有逆变的，很少见，没人喜欢，不再提）。

集合通常含指向数据的可变指针，你可能以为它们也不变，但其实不必！在 Rust 所有权下，Vec<T> 语义上等价于 T，所以协变是安全的！

可惜这个定义是不变的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = *mut Node<T>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}

Rust 怎么决定方差？1.0 之前我们让人自己指定方差……绝对车祸现场！子类型和方差很难理解，核心开发者对基本术语都有分歧！于是改成「按字段抄方差」：编译器看字段，抄它们的方差。有分歧就不变，因为那样安全。

我们类型定义里 Rust 在抱怨什么？*mut！

Rust 裸指针尽量让你为所欲为，但有一个安全特性：多数人不知道 Rust 有方差和子类型，错误地协变会极其危险，所以 *mut T 不变，因为它很可能被当作 &mut T 用。

对我这种写了很多 Rust 集合的人极其烦人。所以我做 std::ptr::NonNull 时加了这段魔法：

与 *mut T 不同，NonNull<T> 被设计成对 T 协变。这样可以在协变类型里用 `NonNull``，但若用在不该协变的类型里，就有不健全风险。

但它的接口围绕 *mut T 建的，怎么回事！是魔法吗？看：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub struct NonNull<T> {
    pointer: *const T,
}


impl<T> NonNull<T> {
    pub unsafe fn new_unchecked(ptr: *mut T) -> Self {
        // SAFETY: 调用者必须保证 `ptr` 非空。
        unsafe { NonNull { pointer: ptr as *const T } }
    }
}

没有魔法！NonNull 滥用 *const T 协变的事实，存那个，在 API 边界和 *mut T 来回转换，让它看起来像存 *mut T。Rust 集合协变就靠这个！很痛苦！所以我让好指针类型替你做了！不客气！享受子类型 footgun！

万灵药是用 NonNull，若要可空指针再用 Option<NonNull<T>>。我们真要做吗……？

要！很烦，但我们在做生产级链表，得把蔬菜吃完，走难路（也可以裸用 *const T 到处转换，但我真想看看有多痛……为了人体工学科学）。

最终类型定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
use std::ptr::NonNull;

// !!!这里变了!!!
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = Option<NonNull<Node<T>>>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}

……等等，还有一件事。做裸指针时应该加 Ghost 保护指针：

1
2
3
4
5
6
7
8
9
use std::marker::PhantomData;

pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
    /// 语义上我们按值存储 T。
    _boo: PhantomData<T>,
}

这里我觉得其实不需要 PhantomData，但用 NonNull（或裸指针）时应该加上，对编译器和别人表明你认为自己在做什么。

PhantomData 是给编译器一个额外「示例」字段的方式，概念上存在于类型里，但因间接、类型擦除等实际上不存在。这里用 NonNull 是因为我们声称类型行为「好像」存了 T，所以加 PhantomData 明说。

标准库还有其他理由，因为它能碰被诅咒的 Drop Check 覆盖，但那功能改了很多次，我不知道 PhantomData 那套还算不算。我会永远 cargo-cult 它，因为 Drop Check 魔法刻在我脑子里！

（Node 字面量存了 T，所以不用，耶！）

……好了布局真结束了！进入基本功能！

最后修改 August 23, 2026: 更新 (499855b16)