The Symmetry in Rust Generics

2023-04-23 - (21 min read)

Rust's generics are a powerful tool, one which can be hard to feel comfortable with. Sometimes when working with a library's generic code, it can feel like being bounced around by the compiler to satisfy some incantation the library author wrote between < and >. While I can't help you avoid being buffeted by the compiler in all situations, if the thought of writing generic Rust code feels daunting, then I hope this guide will help you.

This guide will build off the Rust book chapter on Generics, as it will look at the same concept in a different way. We will focus on the symmetry that generics have to the rest of Rust and ways to think about generics to make them feel natural. Note that we will not be covering lifetimes, saving them for a lifetimes-specific guide. There is enough cognitive overhead in learning generics without diving into what affine typing means, and once generics are understood it makes lifetimes much easier to understand.

1. Motivation🔗

Different languages feature a variety of ways of making things "generic," and there isn't one correct way to do it. There are a number of trade-offs language designers evaluate, such as complexity, ease of implementation, and flexibility. As you might expect, Rust went with the solution which favors correctness, errors, and performance, with the trade-offs of complexity and compile-times. I want to be up-front about the expectations: it will take time to learn, but you also won't be able to shoot yourself in the foot (though you might deal with some difficult compile-time errors).

To better understand the trade-offs, let's start out by looking at duck typing in dynamic languages, which is the opposite end of the spectrum, in this case a Python example (without any static typing hints):

def get_message_for_length(arr):
    if len(arr) > 10:
        return 'Greater than 10 elements'
    else:
        return f'Exactly {len(arr)} elements'

You might expect this function to take in an array for the argument arr, something like get_message_for_length([1, 2, 3]), and perhaps that is all the author of the function expected as well. However, if at some point you decide to use a numpy.array instead, or some other array-like thing, you can continue using the same function as-is. This is the power and flexibility behind duck typing; you can change the underlying structures and so long as they have the same behavior, you don't have to modify any other code. In dynamic languages everything is generic, and you get the flexibility for free.

The downside, of course, is that if you pass in the wrong thing, you will not know until runtime. For instance, Python will happily accept code such as get_message_for_length(12), and it will just throw an exception when you try to run it. This is the trade-off of duck typing: low conceptual complexity, extremely flexible, but no protection from misuse.

Let's consider what it would look like if there was protection from misuse. We would want some way to say "this function can be called on array-like things." Or, perhaps we just care that its something which has a concept of length, and it doesn't have to be array-like. Essentially, we care about restricting our input arguments to some behavior. So let's look at some not-real Python which does this:

def get_message_for_length(arr: impl Length):
    if len(arr) > 10:
        return 'Greater than 10 elements'
    else:
        return f'Exactly {len(arr)} elements'

The above syntax isn't real, but we can imagine it as some way of restricting arr to something which has the behavior of Length. Now, if we try to call get_message_for_length(12), we would get a parser error, because the interpreter would know that arr is restricted to only things that have the behavior defined by Length. We're not going to focus on how this would work in Python, we're just using this as motivation to understand why Rust is the way it is. Because at the end of the day, this is exactly what Rust's generics are for.

Rust has traits which define some behavior which you can restrict variables to. And in simple situations like this, equivalent Rust code would look similar:

trait Length {
    fn len(&self) -> usize;
}

fn get_message_for_length(arr: impl Length) -> String {
    if arr.len() > 10 {
        "Greater than 10 elements".into()
    } else {
        format!("Exactly {} elements", arr.len())
    }
}

The tricky part is when the behavior we want to restrict to is complicated, like really complicated. For example, how would you describe in code the behavior of "two arguments, where the first argument has a method with a return value that can be used as the input to a method on the second argument"?

The answer to that question is where the complexity of Rust's generics lies. It is in the ability to describe any behavior you might want. Because Rusts generics give us the ability to write code as flexible as Python, but with the guarantees we expect from a statically typed language.

2. Generics🔗

This section covers the basic building blocks of generics in Rust. There are only a handful of things to learn, and the real complexity is in combining them to describe the behavior you want. If you scroll through quickly and are put-off by the length, just know that all of this is about how its the same thing applied to different language features.

2.1. Generic Functions🔗

The general syntax for generic functions in Rust is:

fn foo<T: SomeTrait>(arg_1: T) {
}

Before diving into what this means, I want to point out the symmetry in the above function definition. We define the function with fn foo and then we have two lists of parameters. One is <T: SomeTrait> and the other is (arg_1: T).

The usual parameter list, (arg_1: T), defines the arguments usable within the function. We have an argument name and the type. The type determines how we're able to use that argument within the function. For example, if we had arg_1: i32 we can use methods and functions defined for i32 but not ones defined for String or any other type.

Now let's take a look at the <T: SomeTrait> parameter list. It defines some generic type parameter, T, and what is known as a trait bound, : SomeTrait. We can see that we use the generic type parameter we defined within our normal parameter list: arg_1: T. We use a normal argument in a function body, and we use a generic type parameter in the function definition.

The trait bound, the : SomeTrait, is also very similar to the normal type definitions we define. A normal type definition, like arg_1: i32, constrains what we can do with that variable. The trait bound is the exact same concept but slightly more abstract. Rather than restricting a variable to a specific type we restrict it to a specific behavior which is defined by a trait.

Using just this symmetry with the rest of the language we can understand the rest of the rules of using generics:

We can define multiple generics in the same way we do normal arguments:

fn foo<T: SomeTrait, U: SomeOtherBehavior>(arg_1: T, arg_2: U) {
}

We can use a generic type parameter multiple times in a function definition (like a normal argument variable multiple times in a function):

fn foo<T: SomeTrait>(arg_1: T, arg_2: T) -> T {
}

A generic type parameter is one type when used, much like an argument variable is one value when used:

fn foo<T: SomeTrait>(arg_1: T, arg_2: T) {
}

foo(300i32, 9000i32); // Okay, both are the same type i32, and i32 implements SomeTrait
foo(300i32, 12u64); // Errors because i32 and u64 are different types (even if they both implement SomeTrait)

And like an argument variable, generic type parameters can have the same trait bounds (to fix the above code!):

fn foo<T: SomeTrait, U: SomeTrait>(arg_1: T, arg_2: U) {
}

foo(300i32, 9000i32); // Okay, both are the same type i32 which implements SomeTrait
foo(300i32, 12u64); // Okay, both i32 and u64 implement SomeTrait

We can mix and match generic type parameters with concrete types (You can think of this as a function body able to use arguments and constants):

fn foo<T: SomeTrait>(arg_1: T, arg_2: i32) {
}

Where generics start to deviate from our normal parameter list is really just for convenience.

It can be useful to constrain a generic type to multiple kinds of behavior without having to define a new trait (and we use a + to denote this):

fn foo<T: SomeTrait + SomeOtherBehavior>(arg: T) {
}

Given that we can use + to compose multiple behaviors together, these generic argument lists can get pretty long, so there is an alternative syntax which is just syntactical sugar (this is identical to above):

fn foo<T>(arg: T)
where
    T: SomeTrait + SomeOtherBehavior
{
}

And there is a bit of other syntactical sugar (for the most part) which I will describe in more depth in a later section:

fn foo<T: SomeTrait>(arg: T) {
}

// Same as foo
fn bar(arg: impl SomeTrait) {
}

Tip: impl Trait syntax is nice, but can also be a local-maximum in terms of using generics. I recommend trying to avoid them to force yourself to get comfortable with the more powerful <T> syntax

That's all there is to generic functions. To recap, generics in functions are just an additional parameter list enclosed by <> where instead of the arguments being used in-code, we can use them in the function definition. And everything else is pretty much the same as for normal arguments, albeit a few minor differences.

2.2. Generic Structs/Enums🔗

Structs and Enums in Rust can also be generic, and the way they work should look very similar to what we saw for functions:

struct MyStruct<T> {
    generic_type: T,
}

struct MyEnum<T> {
    SomeGenericVariant(T),
    OtherVariant,
}

Those generic type parameters have the exact same behavior as for function generics. Except instead of being used in the function definition they are used in the Struct/Enum definition:

// Mix and match generics and concrete types
struct MyStruct3<T> {
    generic_type: T,
    other_variable: i32,
}

struct MyEnum3<T> {
    SomeGenericVariant(T),
    OtherVariant(12),
}

// Define multiple generics
struct MyStruct1<T, U> {
    inner: T,
    other: U,
}

struct MyEnum1<T, U> {
    Left(T),
    Right(U),
}

// Use the generic definition multiple times
struct MyStruct2<T> {
    first: T,
    second: T,
}

struct MyEnum2<T> {
    First(T),
    Second(T),
}

// A generic type variable resolves to _one_ type
let my_struct_2 = MyStruct2 {
    first: 12i32,
    second: 23u64, // ERR: this is a u64, first and second have the same type
}

Now we could use trait bounds on the generic type parameters we define for Structs and Enums but idiomatic Rust generally doesn't. The reason for this is that when you try to use a generic Struct/Enum in a function or impl block you will have to repeat the trait bound anyway:

// Non-idiomatic: Avoid using trait-bounds in Struct/Enum definitions
struct MyStruct<T: Clone> {
    inner: T
}

// Because we still have to bound T here...
fn takes_cloneable_thing<T: Clone>(arg: MyStruct<T>) {
}

Note: There is no real downside to writing the trait bound, it just doesn't really do much

I snuck some new Rust in the previous example, but maybe you didn't notice it! When using a generic Struct or Enum you simply fill in the generic types they define with either concrete types or other generic types. This should look very familiar since you've used Option<T> or Result<T, E>:

fn do_something<T: SomeTrait>(arg: Option<T>) -> Result<i32, String> {
}

Note that I'm using the full "name" for Option and Result to highlight that they are just generic structs

The generic type parameter we defined can be used where we would normally fill in a concrete type for an Option<T>. Generic Structs and Enums are cohesive with generic functions: there is nothing new to learn or understand when using them together. The generic type parameters you define for a generic function can fill in as the generic type arguments for generic Structs/Enums.

And note that there are no real restrictions here outside the rules we've laid out. We can get crazy; generic Structs and Enums can be nested, and we can mix and match:

struct MyStruct<T, U, V> {
    inner: T,
    other: MyEnum<U, V>,
}

enum MyEnum<T, U> {
    Tee(T),
    You(AnotherStruct<U>),
}

struct AnotherStruct<T> {
    something: T,
}

// Notice that AnotherStruct<T> is generic over MyStruct<T, U, V>
// (which itself indirectly constructs AnotherStruct<T>). This doesn't
// cause issues because the two AnotherStruct<T> instances are of
// different concrete types
fn some_function<T, U>(
    arg: MyStruct<i32, T, U>,
    anotha: AnotherStruct<MyStruct<i32, MyEnum<i64, i64>, U>>
) {
}

The above is absolute nonsense, but it hints at where the true complexity of this stuff lies. The rules are simple, and it's in the combinations that the complexity lies.

2.3. Generic Impls🔗

Generics are not limited to just functions, Structs and Enums. The implementation of methods or traits can be generic:

struct MyStruct {
    val: i32,
}

impl<T> MyStruct {
    fn foo(&self, arg: T) {
    }
}

impl<T> SomeTrait for MyStruct {
    fn bar(&self, arg: T) {
    }
}

The generic type parameter list is just after the impl keyword, and acts in the same exact way as we've seen for functions, Structs and Enums. The rules are all identical, including the where keyword and trait bounds, as well as being cohesive with the other generics:

impl<T, U> MyStruct
where T: Clone
{
    fn foo(&self, arg: T) -> Option<U> {
    }
}

struct OtherStruct<T> {
    val: T
}

// Cohesive with generic structs
impl<T> OtherStruct<T> {
    fn foo(&self) {
    }

    // A generic method, where one argument is a generic type parameter
    // defined by the method and the other is a generic type parameter
    // defined by the impl. Just think of the possibilities!
    fn bar<U: Clone>(arg_1: U, arg_2: T) {
    }
}

To understand why you'd want this is most easily demonstrated with an example. Let's take a look at some error handling code you might be familiar with:

impl From<std::io::Error> for MyError {
    fn from(err: std::io::Error) -> MyError {
        MyError::Something(err);
    }
}

impl From<serde::Error> for MyError {
    fn from(err: serde::Error) -> MyError {
        MyError::SomethingElse(err);
    }
}

impl From<library_b::Error> for MyError {
    fn from(err: library_b::Error) -> MyError {
        MyError::AnotherThingEntirely(err);
    }
}

Tip: You can use the thiserror crate to simplify the above.

By implementing From for the various inner error types, we can automatically return and wrap them with ? in a function body. This is nice for simplifying our error handling code, but requires quite a bit of boilerplate with all of these From implementations. Since all of those error types implement the standard library Error trait (as all errors in Rust should!), we could create a generic implementation to convert into our error type if we don't care to enumerate the errors we have:

impl<T: Error> From<T> for MyError {
    fn from(err: T) -> MyError {
        MyError::Everything(err.to_string())
    }
}

Tip: This is what the anyhow library does.

Generic impls are a powerful concept, one which allows you to implement functionality for a broad range of types. They can also get confusing quickly, especially when combining generic type parameters defined by the impl and ones defined by methods. But the rules are the same, simple rules we discussed way above. While there is nothing new to memorize, it will take time to mentally parse complicated generic impl blocks.

2.4. Generic Traits🔗

Traits themselves can be generic. You know, the thing that we use in trait bounds to constrain our generics?

trait SomeTrait<T> {
  fn some_method(arg: T);
}

I actually slipped this in in the previous section on generic impls, did you notice?

Before going into the specifics, I want to go over why this makes sense conceptually. Traits define a behavior that we can implement on types. Sometimes that behavior we want is dependent on another type. For instance, say we wanted a function which can take in any variable which can be turned into a String. The behavior we want is dependent on String, and while we could have a trait specific to turning something into a String, the behavior itself is not strictly related to String. There is the overarching behavior of turning one type into another.

Hence, we have a standard library trait for this behavior, Into<T>. And if we want to take in arguments which can turn into a String, we would just use the trait bound T: Into<String>:

fn foo<T: Into<String>>(arg: T) {
}

Hopefully this is starting to feel "right"

Generic traits are exactly the same thing as all of the above generics: you can define multiple, you can reuse them in the definition, you can apply trait bounds to them (either syntax!), they resolve to one type, etc.

trait MyTrait<T, U: Clone> {
    fn some_method(arg: T);
    fn some_other_method(arg_1: T, arg_2: U) -> T;
}

Using a generic trait for a trait bound is just as flexible as every other place we use generics. A generic type parameter is a variable for the function definition, and the definition of our trait bounds is included in that scope:

fn foo<T: SomeTrait<U>, U: Clone>(arg: T, arg_2: U) {
}

Note how U is a generic used in Ts trait bound.

Generic traits, especially when combined with generic impls on generic Structs/Enums with generic methods, will get real complicated real fast. The goal here is not to think "generics are simple" but to think "the rules are simple." Because the rules are simple. The rules are also consistent and applied across the language. Everything in Rust can be generic, and the rules for generics are the same for everything. That is the goal for now, the next section will cover the hard stuff.

There is one additional thing to traits, and it is specific and unique to traits. And that is...

2.4.1. Associated Types🔗

Traits can also have something called associated types. Associated types behave in a similar-ish manner to generics, though the syntax is different:

trait MyTrait {
    type SomeType;

    fn foo(arg: Self::SomeType);
}

Rather than defined as a parameter list between < and >, associated types are the keyword type followed by some name within the trait body. Similar to generics, associated types can be used in the definition of of the trait, however they are referenced via a prefixed Self::.

The Rust book covers associated types in an advanced chapter on traits unrelated to generics. The reason for this is that associated types are a separate "idea" from generics even though they are similar. Rather than covering what the Rust book chapter already covers, we're going to focus on how to use the associated traits and how they relate to generics.

Similar to generics, associated types can be bound to some trait, have multiple of them, be reused, etc. (they have the same exact constraints except are defined differently):

trait MyTrait {
    type SomeType: AnotherTrait + Clone;
    type AnotherType;

    fn foo(arg: Self::SomeType, arg_2: Self::AnotherType) -> Self::SomeType;

    fn bar(arg: Self::AnotherType);
}

Where associated types differ is writing trait bounds for them. Let's say we want to constrain some generic type parameter to a trait where the associated type is some specific value. For normal generic traits, we can just pop in a generic or concrete type into the generic parameter list, such as Into<String>. However, associated types aren't defined in the <> parameter list for a trait, so for associated types we have to name them explicitly:

trait Iterator {
    type Item;

    fn next(&self) -> Self::Item;
}

fn foo<T: Iterator<Item = i64>>(arg: T) {
}

This function takes in some generic argument T which is an Iterator that returns i64. Note how similar it is to a normal generic trait except we specify the associated type name. If we want to apply a trait bound to an associated type (eg. an Iterator which returns something that is Clone) we have two options:

fn foo<T: Iterator<Item = U>, U: Clone>(arg: T) {
}

// Or

fn foo<T>(arg: T)
where
    T: Iterator,
    <T as Iterator>::Item: Clone,
{
}

The above two methods are the same, with the first one looking familiar and the second one looking different. The Rust compiler will oftentimes suggest the second method, as it avoids introducing an additional generic type parameter. Its just the turbo-fish in a different place, and while different from what we've previously seen, is something specific to associated types so hopefully isn't world-shattering.

2.4.1.1. Generic Associated Types🔗

Remember how I said everything can be generic in Rust? Well its true, everything can be made generic. Including associated types, the thing that is somewhat like a generic but not really. We call them generic associated types (GATs). This is a niche use-case and primarily useful for lifetimes (which we haven't covered, nor will we cover in depth, leaving them for a future guide). However, this guide wouldn't be complete without mentioning them:

trait MyTrait {
    type SomeType<T>;

    fn foo<T>(arg: Self::SomeType<T>);
}

The RFC for generic associated types covers why they are useful, with a specific section on non-lifetimes use-cases. It turns out compiler support for GATs is really hard, hence why they have a special name and are something you may have heard about. But in general they are a niche tool that just rounds out the generics story in Rust.

2.5 The "impl Trait" Syntax🔗

Speaking of rounding out the generics story in Rust, there is really only one thing new left to cover, and that is the impl Trait syntax. Nominally, impl Trait is a way to have the compiler "fill in" the type. For instance, in the following code, we use impl Iterator to avoid having to write out the exact type:

fn foo(arg: &[u64]) -> impl Iterator {
    arg.iter()
        .map(|x| /* do something */)
        .take(10)
        .filter(|x| /* do something */)
}

The compiler fills in the actual type returned by the function, which is some crazy Filter<Take<Map<...>>> type. For a return type, impl Trait is simply "fill this in for me" to the compiler. For argument types its just syntactical sugar for generics, simply because calling the same function with different types and having it fail (because the compiler doesn't know which type to fill it in with) would be a poor experience:

fn foo(arg: impl MyTrait) {
}

// is identical to:

fn foo<T: MyTrait>(arg: T) {
}

impl Trait is like generics-lite. It gives you some of the same flexibility of generics without having to use the <> parameter list. However they are also pretty limited in what they can do as a generics-lite, for instance there is no way to specify two arguments taking the same generic type:

fn foo(arg_1: impl MyTrait, arg_1: impl MyTrait) {
}

// desugars into:

fn foo<T: MyTrait, U: MyTrait>(arg_1: T, arg_2: U) {
}

I generally reserve using the impl Trait syntax for return types, as I find the consistency of "all things generic look like <>", but many Rust developers find impl Trait to be cleaner in certain situations. This is one of those cases where it is up to preference, though I recommend avoiding impl Trait as much as you can until you feel comfortable with normal generics.

3. Summary🔗

Generics in Rust are a powerful tool for abstraction, one which can seem daunting and full of new things to learn. Hopefully this guide has shown that there is very little that needs to be learned, and there is symmetry with the rest of the language. However, that doesn't mean generics in Rust are simple. They can be combined in complicated ways, and offer the tools to describe any behavior you can imagine (they are Turing complete after all).

While it will take a while to get comfortable with writing and reading traits like the Service Trait from Tower, the best way to start is by trying to make things generic to get a feel for how it all works. It doesn't always make sense to use generics, as it has an impact on readability and compile-times, but learning when to use them or not takes practice, and the only way to learn is by doing.

The best part of generics in Rust is that its all just compile-time errors. It may be frustrating, but at least it won't take down production!