【翻译】Subtyping and Variance / 子类型与变型

Published: at 19:09

本文于 2021 年 1 月 5 日译自 《The Rustonomicon》中 Subtyping and Variance 一章，在原文基础上增加了部分目录格式以便于阅读。

ToC

前言

子类型是类型之间的一种关系，使静态类型语言更加宽松、灵活。

Rust 中的子类型和其他语言有所不同，更难举出简单的例子——毕竟子类型，尤其是变型，其本身已经很难理解了。

为了方便理解，这章首先考虑的是 Rust 的简单扩展——其增加了一个简单的子类型关系。在建立好知识框架之后，我们再回头看实际 Rust 的子类型是如何运作的。

子类型

Objective Rust

这就是我们的扩展：Objective Rust，有三种新类型：

trait Animal {
    fn snuggle(&self);
    fn eat(&mut self);
}


trait Cat: Animal {
    fn meow(&self);
}


trait Dog: Animal {
    fn bark(&self);
}

和一般的 Trait 不同，我们可以像 struct 一样把它们当作具体的类型使用。

我们来看一个简单的例子：

fn love(pet: Animal) {
    pet.snuggle();
}

默认情况下，静态类型必须和编译时类型完全一致。由此，下述的代码就无法编译了：

let mr_snuggles: Cat = ...;
love(mr_snuggles);         // ERROR: expected Animal, found Cat

mr_snuggles 是 Cat，而 Cat 并不等同于 Animal，因此 love 无法执行（😿

很奇怪吧，毕竟 Cat 属于 Animal，它有着 Animal 拥有的一切特性。所以根据直觉，love 不应该在意这是 Cat 而非 Animal。它应该抛弃 Cat 的一切非 Animal 特性——毕竟这对于 love 并不重要。

子类型解决的问题

这就是子类型希望解决的问题。因为 Cat 是 Animal+其他，所以我们描述：Cat 是 Animal 的子类型（subtype）——因为猫是所有动物中的一种；同样地，我们描述：Animal 是 Cat 的超类型（supertype）。

有了子类型，我没就可以给上述的严格静态类型系统增加一条简单的规则了：当某处希望接收类型 T 时，除 T 外还接收类型 T 的子类型。

或者更具体一点：希望接收 Animal 的地方也可以接收 Cat 或 Dog。

在这一章剩下的内容中，子类型会比这个描述复杂而微妙地多，但这条简单的规则表示了 99% 的直觉。并且，编译器会自动处理所有的 corner case——除非你要写 unsafe 代码。

但这是 Rustonomicon，我们要写的就是 unsafe 代码，所以我们需要理解它们的运作原理，以及我们在什么地方可能出问题。

简单 find-replace 的问题

问题的核心就是这条规则，如果简单地应用，可能会导致 meowing dog 问题。在这种情况下，我们可以让别人相信：一条狗实际上是一只猫。这种情况完全摧毁了静态类型系统的结构（还会导致未定义行为的出现）。

来看一个例子，如果完全应用 find-replace 规则会如何：

fn evil_feeder(pet: &mut Animal) {
    let spike: Dog = ...;


    // `pet` 是 Animal, Dog 是 Animal 的子类型
    // 所以没问题……吧？
    *pet = spike;
}


fn main() {
    let mut mr_snuggles: Cat = ...;
    evil_feeder(&mut mr_snuggles);  // 把 mr_snuggles 替换成 Dog
    mr_snuggles.meow();             // OH NO, MEOWING DOG!
}

显然，我们需要一个比 find-replace 规则更可靠的系统。这个系统就是变型（variance），一套管理子类型组成方式的规则。最重要的是，变型定义了禁止套用子类型的情形。

生命周期

不过在介绍变型之前，我们来看一下子类型在 Rust 中的实际应用：生命周期（lifetimes）！

注：生命周期的类型性是一个相当随意的构造，有些人并不认同。但将生命周期统一为类型能够简化我们的分析。

生命周期是代码的区域，而区域可以通过包含（outlives）关系进行部分排序。生命周期的子类型就是以这种关系为条件的：如果 'bit: 'small（big 大于 small，这里的大于是 contains 或 outlives），则 'big 是 'small 的子类型。这看上去有点反直觉：大区域是小区域的子类型。但仔细想想 Animal 的例子就能明白了：Cat 是 Animal+其他，而 big 则是 small+其他。

生命周期的 meowing dog 问题会导致短生命周期被应用于期望长生命周期的地方，形成悬垂引用，最终导致 UAF。

需要注意的是 'static——永久生命周期，是所有生命周期的子类型，因为它比所有生命周期都要长。我们会利用这种关系简化后续的示例。

说了这么多，我们仍然不知道如何实际使用生命周期的子类型，因为没有任何存在是 'a 类型的。生命周期只会在一些更大的类型中作为其中的一部分出现，例如 &'a u32 或 IterMut<&'a, u32>。为了应用生命周期的子类型，我们需要知道如何组成子类型。繰り返す：我们需要变型。

变型

说到变型，事情就开始变得有点复杂了。

类型构造器

变型是类型构造器对其参数（应用）的一种属性。Rust 中的类型构造器是指任何具有非绑定参数的通用类型。比如 Vec 就是一个接收类型 T 并返回 Vec<T> 的类型构造器；& 和 &mut 则是接收两个参数：生命周期和指向类型的类型构造器。

注：方便起见，下文使用 F<T> 代表类型构造器，以便于关注其中的 T。

协变、逆变与不变

类型构造器 F 的变型指输入子类型如何影响输出子类型。Rust 中有三种变型。给定两个类型 Sub 和 Super，其中 Sub 是 Super 的子类型，则有：

如果 F 有多个类型参数，我们可以讨论单个参数的变型，比如：F<T, U> 对 T 协变而对 U 逆变。

从实用角度来看，变型基本指的就是协变（It is very useful to keep in mind that covariance is, in practical terms, “the” variance.）。几乎所有针对变型的考量都是考虑其是协变还是不变。在 Rust 很少能看到逆变的存在——虽然有还是有。

Rust 中的变型

下面的表格简单总结了重要的变型类型，下文也是围绕着它讲述的：

*类型’aTU
*&'a T协变协变
*&'a mut T协变不变
*Box<T>协变
Vec<T>协变
*UnsafeCell<T>不变
Cell<T>不变
*fn(T) -> U逆变协变
*const T协变
*mut T不变

带 * 的行是我们重点关注的，某种意义上的基础。其他未带 * 的可以通过类比进行理解：

注：Rust 中唯一存在逆变的就是函数的参数，在实践中并不常用。逆变涉及到高阶编程，其中函数指针采用了指定生命周期的引用（区别于通常的生命周期，进入了高阶的生命周期，它的工作和子类型无关）。

回顾 meowing dog 问题

知识铺垫就到这里，接下来来看一些例子。首先我们先来回顾一下 meowing dog 问题：

fn evil_feeder(pet: &mut Animal) {
    let spike: Dog = ...;


    // `pet` 是 Animal, Dog 是 Animal 的子类型
    // 所以没问题……吧？
    *pet = spike;
}


fn main() {
    let mut mr_snuggles: Cat = ...;
    evil_feeder(&mut mr_snuggles);  // 把 mr_snuggles 替换成 Dog
    mr_snuggles.meow();             // OH NO, MEOWING DOG!
}

查阅上面的变型表，我们发现 &mut T 对 T 是不变的。也就是说，问题已经解决了：尽管 Cat 是 Animal 的子类型，但 &mut Cat 不再是 &mut Animal 的子类型了。由此，静态类型检查器就能够阻止我们将 Cat 类型传给 evil_feeder。

子类型化的合理性是基于部分细节可以忽略的前提的。但对于引用而言，这样的细节并不能忽略——有一个变量存储着这种细节。当使用这个变量时，我们期望细节信息被保留；当违背期望时，则可能会产生错误的行为。

使得 &mut T 对于 T 协变的问题在于在不知道细节的前提下，我们被赋予了修改原始值的权力，由此导致了 meowing dog 问题。

我们再来看 &T。&T 对于 T 是协变的，因为 &T 不允许修改，在不修改的前提下，任何操作都不会影响细节。同样地，UnsafeCell 和其他内部可变类型必须保持不变：它们使得 &T 的工作方式类似于 &mut T。

生命周期的协变

那生命周期呢？为什么引用的生命周期是协变的呢？

首先，生命周期引用化是 Rust 类型的根本所在。拥有类型系统的根本目的在于我们能够将长生命周期的参数传递给接收短生命周期的函数。

其次，更准确地说，生命周期只是引用的一部分。引用者的类型是共享的，这就是为什么在一个地方调整这个类型会出问题的原因。但如果你在把生命周期移交给他人时削减生命周期（从 'long 到 'short），生命周期信息就不再共享了。现在有了两个独立的、不相关的生命周期，二者也就不会互相扰乱了。

简单来说，唯一的扰乱生命周期的方式就是制造出 meowing dog。但当你试图构建一只 meowing dog 时，其生命周期已经是不变的一部分了，生命周期也就不会被削减。

为了更好地理解这一部分，我们将 meowing dog 问题迁移到实际的 Rust 中。在 meowing dog 问题中，我们取了子类型 Cat，并且将其转换为超类型 Animal，最后用一个满足超类型 Animal 约束条件但不满足子类型 Cat 约束条件的 Dog 覆盖子类型。

因此，对于生命周期，我们希望将长生命周期（longest）转换为短生命周期（shortest），然后以不够长的生命周期（longer）覆盖。如下所示：

fn evil_feeder<T>(input: &mut T, val: T) {
    *input = val;
}


fn main() {
    let mut mr_snuggles: &'static str = "meow! :3";  // mr. snuggles forever!!
    {
        let spike = String::from("bark! >:V");
        let spike_str: &str = &spike;                // 只能活过这个 block
        evil_feeder(&mut mr_snuggles, spike_str);    // EVIL!
    }
    println!("{}", mr_snuggles);                     // UAF?
}

如果我们尝试运行，会得到什么结果呢？

error[E0597]: `spike` does not live long enough
  --> src/main.rs:9:32
   |
9  |         let spike_str: &str = &spike;
   |                                ^^^^^ borrowed value does not live long enough
10 |         evil_feeder(&mut mr_snuggles, spike_str);
11 |     }
   |     - borrowed value only lives until here
   |
   = note: borrowed value must be valid for the static lifetime...

很好，编译失败了。让我们看看这一切到底是如何发生的。首先是新的 evil_feeder 函数：

fn evil_feeder<T>(input: &mut T, val: T) {
    *input = val;
}

它接收了一个可变引用和一个值，然后用值覆盖了引用。这个函数中重要一点是它创建了一个类型平等的约束。它在签名中明确指出引用和值的类型必须完全相同。

同时，调用者这边，我们传入了 &mut 'static str 和 &'spike_str str。

由于 &mut T 对于 T 是不变的，因此编译器得出结论：第一个参数不能接收子类型。因此 T 的类型就必须是 &'static str。

另一个参数的类型是 &'a str，对 'a 是协变的，因此编译器约束：&'spike_str str 必须是 &'static str 的子类型，也就是说 'spike_str 必须是 'static 的子类型，也就是说 'spike_str 必须包含 'static——但只有 'static 自身能包含 'static！

这就是为什么当我们试图将 &spike 赋值给 spike_str 时会出错。编译器工作的结论是 spike_str 必须永远存在，而 &spike 根本不可能活那么久。

因此，尽管在引用它们的生命周期中是协变的，但只要放到一个有问题的上下文中，它们就会继承这种不变性。在上文例子中，我们就是从 &mut T 中继承了不变性。

因此 Box（Vec、HashMap、……）之所以是协变的原因也和生命周期协变的原因相同：一旦你试图使用诸如可变引用，它们就会继承不变性，以防止坏事发生。

拥有所有权时的协变

Box 允许我们从值的层面关注被我们忽视的部分。和那些允许任意别名的语言不同，Rust 有着非常严格的规则：如果你能够修改或移动所有权，则你是唯一能够访问该变量的存在。

考虑以下代码：

let mr_snuggles: Box<Cat> = ..;
let spike: Box<Dog> = ..;


let mut pet: Box<Animal>;
pet = mr_snuggles;
pet = spike;

这段代码没有任何问题，因为当我们移动后，我们就完全忘记了 Cat 或 Dog 存在的事实——它们只剩下了 Animal。我们解决了提出问题的人！（笑）

和不可变引用协变的原因相反，拥有所有权的值之所以协变是因为你能够改变一切。旧地与新地之间不存在任何关系，而进行子类型转换所破坏的内容也就没人知道，因此就不会因为这部分信息产生矛盾了。

函数指针

我们只剩下了一件需要说明的事情：函数指针。

想要理解为什么 fn(T) -> U 对 U 协变，考虑下面的函数签名：

fn get_animal() -> Animal;

这个函数声明了返回 Animal，因此这样的函数签名是完全有效的：

fn get_animal() -> Cat;

毕竟 Cat 是 Animal，因此产生 Cat 也是产生 Animal 的有效方式。或者回到实际的 Rust，如果我们想要返回一个 'short 的内容，返回 'long 自然也是可行的。我们完全可以忘记实际的长短，对其一视同仁。

然而，这种魔法对函数参数无效。考虑以下代码：

fn handle_animal(Animal);

如果用子类型替换：

fn handle_animal(Cat);

前者可以接收 Dog，但后者就只能接收 Cat 了。但如果我们把它反过来，就完全没有问题了。如果我们希望一个函数能接收 Cat 类型的参数，那一个能接收 Animal 类型的函数自然也可以处理这个参数。回到 Rust，如果我们需要一个能处理至少为 'long 的函数，则一个能处理 'short 的函数也符合要求。

这也就是函数参数和语言中其他部分不同，是逆变的原因。

自定义类型的变型

到目前位置，标准库中定义的类型基本已经解释清楚了，那自定义类型又该如何确定变型呢？非正式地讲，一个 struct 从它的 field 中继承变型。如果 struct MyType 有着 a: xxxA，则 MyType 对 A 的变型即为 a 对 A 的变型。

而当 A 被用于多个 field 时：

use std::cell::Cell;


struct MyType<'a, 'b, A: 'a, B: 'b, C, D, E, F, G, H, In, Out, Mixed> {
    a: &'a A,     // 对 'a 和 A 协变
    b: &'b mut B, // 对 'b 协变，对 B 不变


    c: *const C,  // 对 C 协变
    d: *mut D,    // 对 D 比变


    e: E,         // 对 E 协变
    f: Vec<F>,    // 对 F 协变
    g: Cell<G>,   // 对 G 不变


    h1: H,        // 对 H 本应协变，然而……
    h2: Cell<H>,  // 对 H 不变


    i: fn(In) -> Out,       // 对 In 逆变，对 Out 协变


    k1: fn(Mixed) -> usize, // 对 Mixed 本应逆变，然而……
    k2: Mixed,              // 对 Mixed 不变
}
Previous Post
Berd's Red Envelope 2021 WriteUp
Next Post
[Windows/Linux] GC553 的 Switch 完美采集之路