Class 4: Generics and Traits

Let's take a step back and revisit a concept that we've been brushing over for some time now: generic types.

Thus far, we've used Vec<T>, Option<T>, and Result<T, E>, which are all generic types, but we haven't really talked about how they work. If you remember from CS35, these are somewhat analogous to C++ template types, which allow for type polymorphism.

Generics

We'll begin with a simple motivating example, where we'll define our own container type, Either, which is either a string message or an integer:

pub enum Either {
    Left(String),
    Right(i32),
}

impl Either {
    pub fn into_left(self) -> Option<String> {
        match self {
            Either::Left(string) => Some(string),
            Either::Right(_) => None,
        }
    }
}

If we implemented a lot more methods for this type (into_right, flip, ...), then it could be pretty handy! However, what if we wanted an Either for Strings/f32s? One strategy is to create another enum, but that would require having to rewrite every method that we've implemented.

Instead, we can use type parameters on the Either type to make it generic over any two types.

To do this, we can replace the String and i32 with type parameters which looks like the following:

pub enum Either<L, R> {
    Left(L),
    Right(R),
}

Here, we've added <L, R> after the name of the type, which introduces two new type parameters called L and R, sometimes referred to as generic types. We could have named them anything we wanted, but one letter names are common for simple types.

Just like how we can describe a vector of bytes as Vec<u8>, or a return value as Result<u8, Error>, we can describe of Either<L, R> by plugging in types for L and R:

enum Either<L, R> {
    Left(L),
    Right(R),
}
// The `L` and `R` types are replaced with `String` and `i32` respectively for these.
let message: Either<String, i32> = Either::Left("Hello, world!".to_string());
let integer: Either<String, i32> = Either::Right(5);

Adding type parameters also requires changing how the impl block looks:

#![allow(unused)]
fn main() {
enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
//  ^^^^^^ We need this now
    pub fn into_left(self) -> Option<L> { // <- was `Option<String>` before
        match self {
            Either::Left(left) => Some(left),
            Either::Right(_right) => None,
        }
    }

    // other methods here
}
}

The type parameters need to first be introduced into scope with the <L, R> syntax following the impl keyword. If you prefer thinking in math language, you can read this as "For any types L and R, we will define Either<L, R> to have the following methods."

Note that impl blocks aren't the only place that type parameters can be defined. Both functions and methods can also introduce their own generic types parameters as well. Let's add a replace_left method to Either<L, R> that can replace the left item with a value of a different type:

#![allow(unused)]
fn main() {
enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
    // ...

    fn replace_left<T>(self, new_left: T) -> Either<T, R> {
        match self {
            Either::Left(_) => Either::Left(new_left),
            Either::Right(right) => Either::Right(right),
        }
    }
}
}

Mathematically, we can think of this as saying "For any types L and R, and for any type T, we define replace_left to be a function that maps an Either<L, R> and a T to a Either<T, R>.

And here's an example of how it could be used:

enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
    fn replace_left<T>(self, new_left: T) -> Either<T, R> {
        match self {
            Either::Left(_) => Either::Left(new_left),
            Either::Right(right) => Either::Right(right),
        }
    }
}
let string_or_int: Either<String, i32> = Either::Left("Hello".to_string());

// We can call `.replace_left(...)` with any type we want, here's with `f32`
let float_or_int: Either<f32, i32> = string_or_int.replace_left(5.0);

For a thorough walkthrough of generics, check out Chapter 10.1 of the Rust Book.

Traits

Unlike most object-oriented languages which you've probably worked with in the past, Rust has no concept of super classes and extending other classes. Instead, Rust has traits to define shared behavior between different types.

Let's look at an example from Chapter 10.2 of the Rust Book:

trait Summary {
    fn summarize(&self) -> String;
}

Here, we've defined a trait called Summary with one function, summarize, which has no implementation. There are many kinds of things we might want to summarize like tweets and books, so let's create types for those:

struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}

If we want to write a function that can take something that can be summarized like a Tweet or a Book, we can make them both implement the Summary trait:

trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}

impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}

Here, we use the format! macro which is like println! except it writes the contents to a new String.

At this point, we have Tweet and Book, which both implement the Summary trait.

When the Summary trait is in scope (either defined or brought in with use), we're able to call .summarize() on values whose types implement Summary as if it were a method directly on the type:

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}
impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}
// `Summary` definition, `Tweet` definition, and trait implementation hidden

let tweet = Tweet {
    username: "swarthmore".to_string(),
    content: "Only 12 more days until spring semester classes begin! We can't wait to welcome our students back to campus.".to_string(),
    likes: 35,
};

// Call like an ordinary method
println!("Summary of the tweet: {}", tweet.summarize());
}

However, this isn't very exciting by itself. The real abstraction in traits comes from what are called trait bounds, which is where you have a function or struct/enum with a generic type that must implement some set of traits.

For example, we can make a describe function that takes any type T where T implements Summarize:

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}
impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}
// Takes a generic `T`, but _only_ if the T type implements `Summary`!
fn describe<T: Summary>(text: T) {
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

let tweet = Tweet {
    username: "swarthmore".to_string(),
    content: "Only 12 more days until spring semester classes begin! We can't wait to welcome our students back to campus.".to_string(),
    likes: 35,
};

let book = Book {
    author: "Mara Bos".to_string(),
    title: "Atomics and Locks".to_string(),
    content: "-- omitted -".to_string(),
};

describe(tweet);
describe(book);
}

Because the describe function requires that T implements Summary, it means that the function can use any methods provided by Summary on values of type T.

For trait bounds that are more verbose, it can be inconvenient to fit everything in the angle brackets. Rust provides an alternative but equivalent method of specifying bounds with where clauses. For example, we could define the describe function with them instead:

fn describe<T>(text: T)
where
    T: Summary,
{
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

Okay, but what happens if we try to pass in a value whose type doesn't implement Summarize?

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
// Doesn't implement `Summary`
struct NetflixShow {
    year: u32,
    title: String,
    genres: Vec<String>,
}

// Takes a generic `T`, but _only_ if the T type implements `Summary`!
fn describe<T: Summary>(text: T) {
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

let movie = NetflixShow {
    year: 2022,
    title: "Stranger Things".to_string(),
    genres: vec![
        "Sci-Fi TV".to_string(),
        "Teen TV Shows".to_string(),
        "TV Horror".to_string(),
    ],
};

describe(movie);
}

The compiler complains with "the trait bound NetflixShow: Summary is not satisfied". The code will not compile because it is incorrect.

For a thorough walkthrough of traits, check out Chapter 10.2 of the Rust Book.

Generics and Zero-cost Abstraction

Zero-cost abstraction is the notion that you only pay in runtime performance for what you need, and that abstractions compile down into machine code that is equivalent or better to whatever you can write by hand.

When people talk about Rust's "zero-cost abstractions", they're usually talking about its generics in one way or another, and Chapter 10.1 of the Rust Book explains this extremely well. The following is a slightly reworded version of what you'll find there:

You might be wondering whether there is a runtime cost when using generic type parameters. The good news is that using generic types won't make your program run any slower than it would with concrete types.

Rust accomplishes this by performing monomorphization of the code using generics at compile time. Monomorphization is the process of turning generic code into specific code by filling in the concrete types that are used when compiled. In this process, the compiler looks at all the places where generic code is called and generates code for the concrete types the generic code is called with.

Let’s look at how this works by using the standard library’s generic Option<T> enum:
fn main() {
    let integer: Option<i32> = Some(5);
    let float: Option<f32> = Some(5.0);
}
When Rust compiles this code, it performs monomorphization. During that process, the compiler reads the values that have been used in Option<T> instances and identifies two kinds of Option<T>: one is i32 and the other is f64. As such, it expands the generic definition of Option<T> into two definitions specialized to i32 and f64, thereby replacing the generic definition with the specific ones.

The monomorphized version of the code looks similar to the following (the compiler uses different names than what we’re using here for illustration):
enum Option_i32 {
    Some(i32),
    None,
}

enum Option_f64 {
    Some(f64),
    None,
}

fn main() {
    let integer = Option_i32::Some(5);
    let float = Option_f64::Some(5.0);
}
The generic Option<T> is replaced with the specific definitions created by the compiler. Because Rust compiles generic code into code that specifies the type in each instance, we pay no runtime cost for using generics. When the code runs, it performs just as it would if we had duplicated each definition by hand. The process of monomorphization makes Rust’s generics extremely efficient at runtime.

The process of monomorphization comes with several advantages and disadvantages.

Advantages

The biggest advantage is that it means no heap allocations are required because the size of everything is known. We can store types with generics entirely on the stack, or really wherever we want in memory; it's as if we had defined them by hand, giving us maximum control over where things go in memory.

Another advantage is that it allows the compiler to apply clever optimizations. For example, on most types T, Option<T> will be represented in memory as a discriminant byte (the "tag" in "tagged union") and space for the T value. This means the type Option<u8> will take 2 bytes: one for the tag and one for the u8. We can illustrate this using the std::mem::size_of function:

#![allow(unused)]
fn main() {
println!("{}", std::mem::size_of::<Option<u8>>());
}

However, Rust has a special understanding of pointer types like references, where it knows that they can never be null. This means it can optimize types like Option<&Tweet> to use the null pointer to represent the None variant, eliminating the necessity for an extra tag byte altogether.

#![allow(unused)]
fn main() {
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

println!("{}", std::mem::size_of::<&Tweet>());
println!("{}", std::mem::size_of::<Option<&Tweet>>());
}

This is called the null pointer optimization, or NPO, and is only possible because monomorphization creates different types which the compiler can then optimize individually.

Disadvantages

Monomorphization is not without sacrifice, though. Programs that heavily use generic types can greatly slow down the compiler, and monomorphization can quickly inflate compiled binary sizes if many copies of the same types and functions are created. This isn't really an issue with small generic types like Option, Result, and Vec, but a good first suspect for slow compile times is when the names of generic types begin to span multiple lines of your screen, since the compiler is doing a lot of work on these types.

Here's an example of a problematic type from a blog post by fasterthanlime:

TraitPredicate(<
  futures::future::Map<warp::hyper::Server<warp::hyper::server::conn::AddrIncoming, warp::hyper::service::make::MakeServiceFn<[closure@warp::Server<warp::log::internal::WithLog<[closure@warp::log::{closure#0}], warp::filter::or::Or<warp::filter::or::Or<warp::filter::or::Or<warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filters::any::Any, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::filter::FilterFn<[closure@warp::path::end::{closure#0}]>>>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:231:14: 231:92]>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:235:19: 235:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::head::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:239:19: 239:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::post::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:243:19: 243:62]>>>>::bind_ephemeral<std::net::SocketAddr>::{closure#1}::{closure#0}]>>, [closure@warp::Server<warp::log::internal::WithLog<[closure@warp::log::{closure#0}], warp::filter::or::Or<warp::filter::or::Or<warp::filter::or::Or<warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filters::any::Any, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::filter::FilterFn<[closure@warp::path::end::{closure#0}]>>>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:231:14: 231:92]>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:235:19: 235:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::head::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:239:19: 239:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::post::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:243:19: 243:62]>>>>::bind_ephemeral<std::net::SocketAddr>::{closure#0}]>
as
  warp::Future
>)

Yes, that is one type.

These problems are not without workarounds though, and this is discussed near the end of this page.

Motivation for traits: type classes

The ability to define shared method interfaces for types via traits in Rust is extremely versatile, and helps us solve many questions that most programming languages must confront:

Operator overloading
Interfaces
Type markers

Operator overloading

Most programming languages have operators: special syntax recognized by the language as syntactic sugar for a function call. These can range from math operators like + and - to operators for displaying something in string form. For the ladder, Python has def __str__(self), Java has String toString(), and C++ has std::ostream& operator>>(std::istream&).

To allow for custom types in Rust to work with these operators, the standard library provides traits for each overloadable operator. For example, we can make a Point type that implements the std::fmt::Display trait, allowing it to be printed with {} in print statements:

#![allow(unused)]
fn main() {
use std::fmt;

struct Point {
    x: i32,
    y: i32,
}

impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

let origin = Point { x: 0, y: 0 };

println!("The point is: {}", origin);
}

We can even use our knowledge of traits and generics to make Point generic over any type T, and conditionally implement Display if and only if T does:

#![allow(unused)]
fn main() {
use std::fmt;

struct Point<T> {
    x: T,
    y: T,
}

impl<T: fmt::Display> fmt::Display for Point<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

// These values can be displayed
let point_int = Point { x: 3, y: 4 };
let point_float = Point { x: 3.14, y: 2.73 };

println!("The point is: {}", point_int);
println!("The point is: {}", point_float);

struct NotDisplay(i32);

// This one can't be printed because `NotDisplay` doesn't implement `Display`
let point_not_display = Point { x: NotDisplay(4), y: NotDisplay(5) };
}

The traits for the math operators like + and - can be found here, and traits for comparison operators like < and == can be found here.

Interfaces

Another challenge is writing programs that require a type to conform to a particular interface, but the function doesn't particularly care about the exact details of the type.

As an example, we might want to make a function that takes an iterator, but we don't care if it's backed by an array, a linked list, or some type that generates values each time one is requested. We can do this with the Iterator trait.

As described above in the Traits section, this is the most trivial problem that traits can solve, as they allow us to apply bounds to generic types so we can interface with them.

Type markers

We spent week 2 talking about ownership and borrowing, but have you noticed that you never have to worry about ownership of primitive values like i32 or bool?

How come this example compiles:

#![allow(unused)]
fn main() {
fn take_owned<T>(value: T) {
    // Do nothing with it
}

// Make a variable
let x = 5;

// Pass ownership to the function
take_owned(x);

// This is fine here...
println!("{}", x);
}

But this example won't?

#![allow(unused)]
fn main() {
fn take_owned<T>(value: T) {
    // Do nothing with it
}

// Make a variable
let x = "An owned string".to_string();

// Pass ownership to the function
take_owned(x);

// Borrow after move, compiler error!
println!("{}", x);
}

The only difference is that x is an i32 in the first example, and is a String in the second example.

Fortunately for us, the compiler error points us in the right direction: String does not implement the Copy trait. The Copy trait is a special marker trait that has no methods, but is instead special to the compiler. Most types in Rust have what are called "move semantics", meaning that when they pass ownership to something like a function, their bytes are memcpy'd into the new location in memory, and the compiler enforces that we're not allowed to interact with the old bytes anymore. When a type implements Copy, however, it gets "copy semantics", which tells the compiler that the old bytes are still valid to use after a move.

This makes sense for simple types that are semantically all in one place like primitive types, since creating a bitwise copy shouldn't invalidate the original. However, it doesn't make sense for types that aren't all in one place like a String, which is a length, capacity, and a pointer to a heap allocation. If it were Copy, then you could create two String values that both point to the same heap allocation, which will cause a use-after-free when one of them goes out of scope or reallocates.

Instead, creating a duplicate of a String requires calling .clone(), which is a method provided by the Clone trait. This will create a new String with its very own heap allocation that contains a copy of the original string's heap allocation, allowing them to both own their own allocations and prevent memory issues.

#![allow(unused)]
fn main() {
let a = "I love Rust!".to_string();
let b = a.clone();

// Each string has its own allocation now
println!("{:?}", a.as_ptr());
println!("{:?}", b.as_ptr());
}

Other significant markers are the Send and Sync traits, which are used for marking types that can be sent across threads and types that can be shared across threads respectively. These marker traits are part of the cornerstones for Rust's fantastic concurrency model.

~

Summary

Generics allow for defining types and functions that work on values of different types.
Traits are like interfaces that types can implement.
Types and functions can use trait bounds on generic types to restrict which types can be used.
Monomorphization is the process where the compiler looks at every usage of a generic and turns it into its own copy of the function or type.
Monomorphization can lead to more optimization, but slower compile times in some extreme cases.
Traits allow for operator overloading, shared interfaces, and type markers for the compiler like Copy.

Introduction to Rust Programming