A Deep Dive Into the Rust Type System

Introduction

This post is going to be a deep dive into Rust's type system and how compares to the Scala 3 type system. I use the Scala type system as comparison as I know it well and it's one of the most powerful type systems available in a "production grade" language. It can express most everything found in the Rust type system (except everything related to borrowing checking of course), but the opposite is not true since Scala has many advanced type features which Rust lacks (for example union/intersection types, subtyping, HKT's etc. etc.).

Type Relationships

The relationships between types in Scala are specified using subtyping (C extends A with B), union types (type C = A | B) and intersection types (type C = A & B). In Rust there are no relationships between types (except type aliases, type B = A). There is however a way to specify subtype-like relationships for traits, which we will get into in the next section.

Traits

Rust traits is a description of a type, or rather what properties a type is expected to have. In this way they are similar to Java interfaces or Scala traits, but the most important difference is that Rust traits are not types. So this example doesn't work:

trait T {}

fn foo(a: &T) {}  // Compiler error

This took me a while to grasp coming from the Java/Scala world. Trait implementations are not first class values you can pass around, and traits are totally separated from the universe of types. They are more like type classes in Haskell.

However, you can use the dyn or impl keyword in front of a trait name to construct an abstract type.

Impl Trait

A impl Trait type is basically syntactic sugar for introducing a new, anonymous type parameter that is bounded by the trait, so it only works in places where you can add type parameters (i.e. functions and methods). For example:

trait T {}

// These function definitions are equivalent

fn foo1(a: &impl T) {}

fn foo2<A: T>(a: &A) {}

Dyn Trait

The dyn keyword is used for dynamic dispatch and is most similar to how Java interfaces/Scala traits works as types. The difference is that a value of type &dyn Trait is a pair of a pointer to the value and a pointer to the trait vtable for the value type, typically called a fat pointer. In Java/Scala it's only a single pointer to the object which in turn contains a pointer to it's class which in turn contains a pointer to the interface/trait vtable. Rust must use fat pointers because trait implementations can be separate from the actual type, but in Java/Scala interfaces are always implemented as part of a type.

The closest similarity to a fat pointer in Scala would be an object paired with an implementation of a trait for the object type, i.e. (A, T[A]). However this is rarely used in practice, instead a context bound is used:

// These are equivalent

def foo[A: T](a: A)

def foo[A](v: A)(using t: T[A])

So the context bounds adds an additional, implicit parameter to the method containing the "vtable" for the trait implementation. Note that even though Scala context bounds and Rust type parameter bounds looks similar and can be used in many of the same situations, they are quite different as there is no dynamic dispatch when using Rust type parameter bounds.

The simple pointer in Java/Scala compared to the fat pointer in Rust is an important difference, and as a consequence value references (&A) in Rust are not dyn trait references (&dyn T) even though the type A implements the trait T. However, there is an implicit conversion done by the Rust compiler (and you can write the conversion explicitly as well using as).

This is apparent when you for example put references in collections. Take this Rust example:

trait T {}

struct A;

impl T for A {}

fn foo(v: &[&dyn T]) {}

fn main() {

    let a = A {};

    

    // This vector contains simple pointers

    let va: Vec<&A> = vec![&a, &a];

    // foo(&va);  // Doesn't compile

    

    // This vector contains fat pointers (a pointer pair)

    let vt: Vec<&dyn T> = va.iter().map(|e| *e as &dyn T).collect();

    foo(&vt);  // Now it works!

    

    use std::mem::size_of;

    println!("&A: {}, &dyn T: {}", size_of::<&A>(), size_of::<&dyn T>());

}

So you cannot pass a Vec<&A> directly to foo() even though A implements the trait T. You first have to transform the Vec<&A> into a Vec<&dyn T> which is twice the size (as you can see in the program output).

In Scala you wouldn't have to do this conversion as A would be a subtype of T (i.e. the Liskov substitution principle holds), and thus Seq[A] would be a subtype of Seq[T] (if Seq is read only).

Supertraits

You can write trait U: T in Rust to indicate that T is a supertrait of U which means that any type which implements U must also implement T. However, unfortunately that doesn't mean that a &dyn U can be converted into a &dyn T. For example:

trait T {}

trait U: T {}

struct A;

impl T for A {}

impl U for A {}

fn main() {

    let a = A {};

    let u: &dyn U = &a;

    let t: &dyn T = u as &dyn T;  // This doesn't compile

    let t: &dyn T = &a;  // But this does

}

There seems to be ongoing work to fix this issue, so in the future this might be valid Rust code. Obviously in Scala/Java this would work just fine because of subtyping.

Enums

Enums in Rust are unfortunately quite limited compared to Scala 3 enums. In Scala every enum variant is a proper type (a subtype of the enum type), but in Rust only the enum itself is a type, not the variants. So this is perfectly valid Scala code:

enum E {

  case A(v: Int)

  case B

}

val a: E.A = E.A(10)

In Rust you can sometimes work around this limitation by creating new types which are wrapped in enum variants, for example:

struct A(i32);

enum E {

    A(A),

    B

}

However this doesn't work in all cases, for example if you need a type parameter like in the following Scala example:

enum E {

  case A[T](v: T)

  case B

}

In Rust you would have to put the type parameter on the enum type:

struct A<T>(T);

enum E<T> {

    A(A<T>),

    B

}

which has some downsides. I think one reason why type parameters on variants would be hard to add would be that in many cases the compiler wouldn't know the size of the enum type. But it could possibly be allowed if the size doesn't depend on the type parameter, for example:

enum E {

    A<T>(Box<T>),

    B

}

However, that might be of limited use unless existential types are also added:

fn foo(e: E) -> Option<for<T> Box<T>> {

    match e {

        E::A(b) => Some(b),

        _ => None

    }

}

Summary

Well, that's enough for this post. I've highlighted some of the differences between the Rust and Scala type systems, and how Rust's is lacking in some regards. There are certainly many other aspects to cover on this topic, and I might come back to it in future blog posts.