Rust 中的逆变与协变 | RiversJin's Blog

subtyping 在编程理论中, 是一个很有趣的话题. Rust虽然并不那么OOP, 但是其生命周期系统依然会有逆变,协变以及子类型的概念.

逆变 && 协变

让我们忘掉Rust, 先来复习一下逆变与协变的概念. 为了简化描述, 我们来定义一下下面的记号

A <: B 代表A是B的子类型 A -> B 以 A 为参数类型, 以 B 为返回值类型的函数类型 x : A x是一个变量, 其类型为A

我们有三个类型 Greyhound <: Dog <: Animal

Greyhound 是 Dog 的子类型 (或者说 Greyhound 是 Dog 的一种); Dog 是 Animal 的子类型 ( Dog 是 Animal 的一种).

从概念上讲, 子类型至少有着父类型的全部内涵(或者说特性), 并且可能还会多一些.

所以很显然 A <: A 是成立的. A当然至少有着A的全部特性. 这是一种大于等于的关系

协变(Covariance)是指子类向基类的转换.

比如我需要一个 Dog, 但是你给了我一个 Greyhound, 这样我获得的不仅是 Dog, 甚至还有更多的特性(灰毛). 这种情形就是协变

逆变(Contravariance)是指基类向子类的转换.

还是用上面的方法举例, 假如我们需要一个 Dog, 但是你只给我了一个 Animal. 那么这种情形就是逆变

听起来这种情形不太合理, 是不是, 但也不一定, 我们接下来会讲

函数类型的逆变与协变

函数类型由其参数类型与返回类型决定. 当我们需要将函数作为参数或者返回值传递时, 同样需要考虑函数类型的协变与逆变过程.

那么, 在函数类型上, 子类型意味着什么呢?

从上面数据的子类型角度讲, 假如A <: B. 意味着一个需要B的场景下, 向其提供一个A是合理的.

因为A包含了B的全部特性嘛

按照这个思路, 假设一个需要 Dog -> Dog 类型函数的场景下, 如果我们向其提供一个类型 A -> B的函数这个行为是合适的, 那么 A, B 与 Greyhound, Dog, Animal 需要满足什么关系?

即如果 A -> B 是 Dog -> Dog 的子类型的话, 那么A,B应当与上面三个类型满足什么关系?

我就不给大家上数学课了, 打个比方. 我们可以将函数视为一种容器(映射).

首先思考参数类型

在以 Dog为参数的情况下, 就是说, 这里需要一个装狗的箱子. 那么我们需要提供给它什么箱子呢?

可以装狗的箱子. 正合适!
只能装灰狗的箱子. 这不行, 因为用来装狗的容器可能会被用来装狮子狗, 装哈巴狗.
一个可以装所有动物的箱子. 可以!

所以, 如果 A -> B : Dog -> Dog 成立的话, 那么A需要是 Dog或者 Dog的父类型

然后是返回类型. 跟上面一样, 我们依旧将函数想象为一种箱子, 不过现在的需求变了. 参数是"放进去"的东西, 而返回值是"取出来"的东西.

->Dog 就是说, 这里需要一个能从中取出狗的箱子(假设箱子不是空的就好:P). 那么我们需要提供什么箱子呢?

里面可以拿出一只狗的箱子. 合适
里面可以取出一只灰狗的箱子. 合适: 因为我们要的是一只狗, 灰狗当然也是狗.
可以取出一只动物的箱子. 不行: 我们需要一个取出狗的箱子, 但是从这个箱子里面我们可能拿到的是一只兔子, 这不好.

所以, 对于函数类型来说, 参数类型和返回类型是反过来的, 对吧?

用正式一点的话说, 就是, 函数的 参数类型可以逆变, 而 返回类型可以协变

用更加正式的描述就是

1
2
3
4
如果有 A <: B (T为任意类型), 那么有
1. (B -> T) <: (A -> T)
2. (T -> A) <: (T -> B)
成立

Rust 声明周期的子类型概念

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
fn main() {
    let r;                // ---------+-- 'a
                          //          |
    {                     //          |
        let x = 5;        // -+-- 'b  |
        r = &x;           //  |       |
    }                     // -+       |
                          //          |
    println!("r: {}", r); //          |
}                         // ---------+

Rust的类型系统虽然在空间上没有子类型的概念, 但是在时间上却是有的.

以上面的标记为例. r的生命周期为 'a, 而 x的声明周期为 'b.

我们可以用一个简单的类比来理解这个关系, 这里显然 'a要比 'b的存在时间更长, 那么我随便编一个数字:

'a 代表"至少可以活10s", 而 'b代表"至少可以活5s".

用上面的子类型的概念来理解它们两个的关系:

假如在某个场景下, 我们需要一个"至少能活5s"的东东, 那么我们给这它提供一个"至少能活10s"的东东行不行呢? 当然可以. 但是反过来, 需要一个"至少能活10s"的东东, 而只提供了一个"至少能活5s"的东西, 那是不行的, 因为可能在第6s时提供的东东噶了, 不满足此时的需求.

所以, 从这个角度来看, 我们可以简单理解生命周期的内涵(或者说特性)为"存活的秒数". 那么这就会得到一个看起来有点反直觉的结论(但实际上肥肠合理):

能活的更久的东西具有更多的"存活秒数",在时间的角度上具有更多的"内涵", 是活的更短的东西的子类型

比如 'static 代表贯穿整个程序的生命周期, 它可以是任意更短周期的子类型. 在需要一个存活n秒的东东场景下, 给它一个能无限存活的变量总是可以满足需要的

所以, 到这里, 我们就可以将协变与逆变的概念放在Rust的生命周期系统上了.

如果一个生命周期标记发生了协变, 那么就意味着这个生命周期发生了"缩短". 反之, 如果一个声明周期发生了逆变, 那么就是发生了"延长"(当然, 在真实编码中, 延长一般来说是不太可能的…)

跟Golang那种残废不一样, Rust即使是生命周期标记的系统上, 其类型也是支持逆变与协变概念的.

如果你学的是Golang, 那么完全不需要理解这些逆变, 协变, 子类型的概念. Golang中一切类型都是不变(invariant)的, 除非手动强制转换, 不然不存在类型的变化

借用的可变性与生命周期变化

首先说逆变. 这种当然是不允许的, 本来代码中, 一个变量只能活4s, 你在8s后访问它, 这是不合适的. 也就是说, 引用的生命周期不可逆变(协变)

当然, 如果论起一些黑魔法, unsafe, 那当我没说

但是协变呢? 如果一个引用在5s内有效, 但是我们将其视为一个只在2s内有效的引用, 可不可以呢? 可以, 但没有完全可以.

对于不可变借用, 那么生命周期可以缩短.
对于可变借用, 就不行了(invariant).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn baz(){
    #[derive(Debug)]
    struct NoClone(i32);

    fn print_numbers<'a>(num_1: &mut &'a NoClone, num_2: &mut &'a NoClone) {
        println!("{:?} {:?}", num_1, num_2);
    }

    let num_1 = NoClone(1);
    let mut num_1_ref = &num_1;
    let num_2 = NoClone(2);
    let mut num_2_ref = &num_2;
    print_numbers(&mut num_1_ref, &mut num_2_ref);
    std::mem::drop(num_2); // delete this line to make it compile
    println!("{:?}", num_1_ref);
}

这段代码中, 由于print_numbers要求两个参数的生命周期必须一致, 如果可以协变的话, 那么num_1_ref协变一下得到print_numbers的形参. 那么这段代码是可以通过编译的. 但是并没有, 为了满足print_number的要求, Rust自动推导出num_1_ref与num_2_ref具有一致的生命周期. 这就使得在drop num_2 之后, Rust认为num_1_ref的生命周期同样已经结束了, 所以最后的println!不能通过编译.

这里有点微妙, 比如下面的代码是可以通过编译的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#[test]
fn bar(){
	let mut a = 1;
	let ref_longer: &mut i32 = &mut a;
	{
		let ref_shorter: &mut i32 = ref_longer;
		println!("ref_shorter: {}", ref_shorter);
		*ref_shorter = 4;
	}
	println!("ref_longer: {}", ref_longer);
}

通过 ref_longer初始化 ref_shorter时, 看似发生了协变, 但其实并没有, 因为ref_longer的生命周期并没有发生变化. 编译器只是检查到ref_longer的生命周期可以满足ref_shorter的生命周期要求, 就允许了赋值操作, 并没有限定初始化ref_shorter的东东的生命周期必须与ref_longer一致.

为什么可变借用的生命周期不可协变?

我们可以从两个层面来理解这个问题. 首先是实际的逻辑

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
fn bar(){
	fn overwrite<T: Copy>(input: &mut T, new: &mut T) {
		*input = *new;
	}
	let mut a: &'static str = "hello";
	{
		let b = "b".to_string();
	
		overwrite(&mut a, &mut &*b); // compile fails
	}
}

如果这段代码是可以通过编译的, 那么必然意味着overwrite的第一个参数的生命周期从'static协变到了b的生命周期. 但这样会导致a在b的生命周期结束后, 变成了一个悬垂指针.

其次我们可以从子类型的角度来理解这个问题. 相对于不可变借用, 可变借用实现了对于原变量的两种接口, Read And Write.

假设有两个类型, A 和 B, 其中 A 的生命周期长于 B. 那么在时间的角度上, A 是 B 的子类型, 即 A <: B.

对于Read, 我们可以将其视为一个 getter 函数. 记为 -> T. 对于Write, 我们可以将其视为一个 setter 函数. 记为 T -> (). 我们可以记为:

1
2
3
4
5
A <: B
getter_a : -> A
getter_b : -> B
setter_a : A -> ()
setter_b : B -> ()

根据上面的理论, 我们知道

1
2
3
if A <: B, then
1. (B -> T) <: (A -> T), 即 getter_b <: getter_a
2. (T -> A) <: (T -> B), 即 setter_a <: setter_b

这样一来, 对于一个不可变借用, 由于只有getter没有setter, 所以其生命周期可以协变. 但是对于可变借用, 由于其具有setter, 它有且只有一个子类型, 就是它自己, 这就意味着它的生命周期是不可协变的.

从这里推广一下其他的语言. 假如在一个OOP的语言中, 如果我们为一个类实现了getter和setter, 那么它的引用类型就是不可协变的. 这也是为什么在Java中, 数组是不可协变的, 因为数组具有setter方法.

知道了这些有什么用?

呃, 其实用处不大, But it’s fun to know.

在一些特殊场景下, 假如由于某些原因, 我们可能希望限制一个不可变借用的生命周期, 就可以用这个特性来实现, 比如:

1
2
3
4
5
6
7
8
struct Foo<'a> {
	data: &'a i32
}

struct Bar<'b> {
	data: &'b i32,
	_marker: std::marker::PhantomData<&'b mut &'b ()>
}

在Crossbeam的ScopeThread中用到了这种技巧, 但是具体解决了什么问题, 别急, 请听下回分解.

END