subtyping和variance在Rust里属于比较难理解的概念,和lifetime联系在一起更是难以理解,本篇文章尝试弄清楚这些概念及原理,加强对Rust类型系统的理解。

本篇文章介绍subtyping、variance等概念,通过对一段无法通过编译的代码,尝试从variance、lifetime、subtype等方面进行分析,从Rust的角度来思考问题,解释了为什么Rust会报这样的错误,并最终根据对相关概念的理解提出了解决方法,最终解决了问题,相信这个过程对理解variance、subtyping等概念非常有帮助。

Subtyping

subtyping definetion

In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype. If S is a subtype of T, the subtyping relation is often written S <: T, to mean that any term of type S can be safely used in a context where a term of type T is expected.1

Subtyping is a relationship between types that allows statically typed languages to be a bit more flexible and permissive.2

从上述引用来看,Subtyping是个关系,所以至少是两个类型比较才会有这种关系,sub一般与super对应,如果T1是T2的subtype,那T2就是T1的supertype。以继承关系为例,假设有个类型 Cat 继承自 Animal ,那么可以确定在使用Animal的地方也一定可以使用Cat,因为Cat拥有Animal拥有的一切能力,在这两个类型的关系里,我们可以说 Cat是Animal的Subtype,Animal是Cat的superbype

根据上面的描述,可以总结出一个规则, 任何期望接受T的地方,也一定可以接受T的subtype

nomicon文档举了个例子,简单应用上面的规则会出现 meowing Dogs 问题,也就是明明类型是狗叫声却是猫,这样的类型系统是不够健壮的,可能会出现 Undefined Behaviour ,所以需要一个更健壮的系统来解决这种问题,这个系统就是 Variance ,它是控制如何构成subtype的一组规则。

subtype in lifetime

subtype实际上已经应用在Rust的lifetime里了,所以这里以lifetime为例理解下subtype的应用。假设有两个lifetime 'big: 'small (这种写法表示 'big'small 生命周期长或者说 'big 的生命周期包含 'small 的生命周期),在可以使用 'small 的地方一定可以使用 'big ,所以 'big'small 的subtype ,那么根据上面的规则可以得出 在任何接受 'small lifetime的地方一定可以接受 'big 的lifetime 。由于 'static 的生命周期从初始化到程序中止,生命周期是程序里最长的,所以 'static 是任何lifetime的subtype ,所以在期望使用 'a 的地方一定可以使用 'static

要应用lifetime的subtype,需要知道subtype是如何组成的,这就不得不提到 variance

Variance

  • Variance is a property that type constructors have with respect to their arguments. A type constructor in Rust is any generic type with unbound arguments. For instance Vec is a type constructor that takes a type T and returns Vec<T>. & and &mut are type constructors that take two inputs: a lifetime, and a type to point to.
  • A type constructor F's variance is how the subtyping of its inputs affects the subtyping of its outputs. There are three kinds of variance in Rust. Given two types Sub and Super, where Sub is a subtype of S~uper~:

    • F is covariant if F<Sub> is a subtype of F<Super> (subtyping "passes through")
    • F is contravariant if F<Super> is a subtype of F<Sub> (subtyping is "inverted")
    • F is invariant otherwise (no subtyping relationship exists)
  • If F has multiple type parameters, we can talk about the individual variances by saying that, for example, F<T, U> is covariant over T and invariant over U.

从上述Rust nomicon文档来看, variance 是一个property,更准确的说是 type constructor 的property。

type constructor

type constructor 又是什么?

a type constructor is a feature of a typed formal language that builds new types from old ones.3

从字面意思可以理解为类型构造器,和其它构造器一样,可以根据不同输入构造不同的对象,而type constructor就是根据不同的输入构造不同的类型。

在Rust里任何未绑定参数的泛型就是 type constructor ,比如 Vec 就是一个type constructor,如果绑定了参数 T 就会返回 Vec<T> 类型。 &&mut 也是type constructor,它们可以携带 lifetime 、指向的类型 T 等参数,返回新的类型。

为了方便讨论 T ,我们使用 F<T> 来表示 T 的type constructor。

variance

这里假设有两个类型 SubSuperSubSuper 的subtype。 SubSuper 传递给同一个 type constructor 会产生新的类型 F<Sub>F<Super>F<Sub>F<Super> 之间的关系统称为 variance ,在Rust里有三种关系。

  • F is covariant if F<Sub> is a subtype of F<Super> (subtyping "passes through")

    • SubSupersubtypeF<Sub> 也是 F<Super>subtype ,这种被称为 covariant ,这是最常见的情况,比如 lifetime 就是这种情况。
  • F is contravariant if F<Super> is a subtype of F<Sub> (subtyping is "inverted")

    • SubSupersubtype , 而 F<Sub>F<Super>supertype ,也就是 F<Super>F<Sub>subtype ,关系发生了反转, fn(T) -> () 属于这种情况。
  • F is invariant otherwise (no subtyping relationship exists)

    • 这种主要是针对不可变的情况,不存在subtyping关系,因此入参必须和定义要求完全一致。

根据Rsut的reference文档,关于 type constructor 接收 'aT 产生的新类型 Type ,与原类型之间的variance关系如下。

TypeVariance in 'aVariance in T
&'a Tcovariantcovariant
&'a mut Tcovariantinvariant
*const Tcovariant
*mut Tinvariant
[T] and [T; n]covariant
fn() -> Tcovariant
fn(T) -> ()contravariant
std::cell::UnsafeCell<T>invariant
std::marker::PhantomData<T>covariant
dyn Trait<T> + 'acovariantinvariant

如下是关于 PhantomData 的variance关系。

Phantom type'aT
PhantomData<T>-covariant (with drop check)
PhantomData<&'a T>covariantcovariant
PhantomData<&'a mut T>covariantinvariant
PhantomData<*const T>-covariant
PhantomData<*mut T>-invariant
PhantomData<fn(T)>-contravariant
PhantomData<fn() -> T>-covariant
PhantomData<fn(T) -> T>-invariant
PhantomData<Cell<&'a ()>>invariant-

实例分析

示例代码

如下定义了一个 strtok 函数,作用是返回string token,输入字符串及分割字符,返回分割后的第一个token字符串,修改原字符串为分割后的剩余部分。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
  fn main() {
      let mut x = "hello world";

      let hello = strtok(&mut x, ' ');

      assert_eq!(hello, "hello");
      assert_eq!(x, "world");
  }

  pub fn strtok<'a>(s: &'a mut &'a str, delimiter: char) -> &'a str {
      if let Some(i) = s.find(delimiter) {
          let prefix = &s[..i];
          let suffix = &s[(i + delimiter.len_utf8())..];
          *s = suffix;
          prefix
      } else {
          let prefix = *s;
          *s = "";
          prefix
      }
  }

编译结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
  error[E0502]: cannot borrow `x` as immutable because it is also borrowed as mutable
   --> src/main.rs:7:5
    |
  4 |     let hello = strtok(&mut x, ' ');
    |                        ------ mutable borrow occurs here
  ...
  7 |     assert_eq!(x, "world");
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     immutable borrow occurs here
    |     mutable borrow later used here
    |
    = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

  error: aborting due to previous error

  For more information about this error, try `rustc --explain E0502`.

报错分析

上面的错误提示很清楚,在 x 生命周期内同时存在 mutable borrowedimmutable borrowed ,这是不允许的。

那我们把 mutable borrowedimmutable borrowed 分散在不同时生命周期不就可以了吗?

理论上是可以的,那我们引入新的 scope 或添加 drop ,让 mutable borrowed 提前结束,看看编译器如何处理。

添加scope

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  fn main() {
      let mut x = "hello world";

      {
          let hello = strtok(&mut x, ' ');

          assert_eq!(hello, "hello");
      }
      assert_eq!(x, "world");
  }

  pub fn strtok<'a>(s: &'a mut &'a str, delimiter: char) -> &'a str {
      if let Some(i) = s.find(delimiter) {
          let prefix = &s[..i];
          let suffix = &s[(i + delimiter.len_utf8())..];
          *s = suffix;
          prefix
      } else {
          let prefix = *s;
          *s = "";
          prefix
      }
  }

编译依然报错,Rust提示了同样的错误,显然Rust并不认为引入新的 scope 后, mutable borrowed 可以提前结束。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
  error[E0502]: cannot borrow `x` as immutable because it is also borrowed as mutable
   --> src/main.rs:9:5
    |
  5 |         let hello = strtok(&mut x, ' ');
    |                            ------ mutable borrow occurs here
  ...
  9 |     assert_eq!(x, "world");
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     immutable borrow occurs here
    |     mutable borrow later used here
    |
    = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

  error: aborting due to previous error

  For more information about this error, try `rustc --explain E0502`.

添加drop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  fn main() {
      let mut x = "hello world";

      let hello = strtok(&mut x, ' ');

      assert_eq!(hello, "hello");
      drop(hello);

      assert_eq!(x, "world");
  }

  pub fn strtok<'a>(s: &'a mut &'a str, delimiter: char) -> &'a str {
      if let Some(i) = s.find(delimiter) {
          let prefix = &s[..i];
          let suffix = &s[(i + delimiter.len_utf8())..];
          *s = suffix;
          prefix
      } else {
          let prefix = *s;
          *s = "";
          prefix
      }
  }

编译依然报错,Rust提示了同样的错误,显然Rust并不认为添加 drop 后, mutable borrowed 可以提前结束。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
  error[E0502]: cannot borrow `x` as immutable because it is also borrowed as mutable
   --> src/main.rs:9:5
    |
  4 |     let hello = strtok(&mut x, ' ');
    |                        ------ mutable borrow occurs here
  ...
  9 |     assert_eq!(x, "world");
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     immutable borrow occurs here
    |     mutable borrow later used here
    |
    = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

  error: aborting due to previous error

  For more information about this error, try `rustc --explain E0502`.

分析过程

根据前面对 variance 的理解,以及上述reference文档的表格,我们有如下结论:

  • &mut T'a 的variance关系是 covariant
  • &mut TT 的variance关系是 invariant

根据Rust的报错信息,存在冲突的地方出现在 &mut xx 之间,那我们继续分析。

  1. x 的完整定义是 &'a str
  2. &mut x 的完整定义是 &'a mut &'a str

可以看到 x&mut x 分别有各自的lifetime参数,在 strtok 定义中这两个的lifetime都是 'a

为什么上面的方法不生效呢?

  1. strtok 定义中, &mut xx 的lifetime都是 'a ,因为 &mut TT 的variance关系是 invariant ,所以 strtok 中的 'ax 为准
  2. x 的生命周期始终没有变化,一直都是从 x 初始化到 main 函数结束
  3. 不管是添加 scope 还是添加 drop ,在 x 的生命周期始终存在 mutable borrowedimmutable borrowed
  4. 因此Rust告诉我们存在冲突

因为 &mut x 是由 &mutx 组合的新类型,即 &mut xx 是两个类型,所以 &mut xx 的lifetime是可以独立存在 ,这正是我们想要的效果,给这两个类型独立的生命周期,需要修改 strtok 定义。

解决方法

根据前面的分析,我们需要调整 strtok 定义,让 &mut x 具有独立的lifetime,如下所示。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
  fn main() {
      let mut x = "hello world";

      let hello = strtok(&mut x, ' ');

      assert_eq!(hello, "hello");
      assert_eq!(x, "world");
  }

  pub fn strtok<'a, 'b>(s: &'a mut &'b str, delimiter: char) -> &'b str {
      if let Some(i) = s.find(delimiter) {
          let prefix = &s[..i];
          let suffix = &s[(i + delimiter.len_utf8())..];
          *s = suffix;
          prefix
      } else {
          let prefix = *s;
          *s = "";
          prefix
      }
  }

结果与理论分析一致,编译器通过了。

总结

一个type constructor F 可以接收一个 T 参数产生一个新类型 F<T> ,在给定 SubSuper 两个有subtyping关系的输入后,产生了两个新类型 F<Sub>F<Super> ,这两个新类型之间的关系称为variance,在Rust里会有3种形态,由于存在 & &mut 'a fn(T) -> () 等多种type constructor,在分析具体问题时可以参考reference文档的variance来快速了解新类型是哪类variance。

Footnotes