Traits and Generics

Intro to Traits

Rust's implementation of polymorphism comes from two mechanisms:

1. Traits
2. Generics

Traits are Rust's take on the interfaces or abstract base classes found in OOP-world.

Here's a condensed version of the std::io::Write trait:

#![allow(unused)]
fn main() {
// std::io::Write
trait Write {
    fn write(&mut self, buf: &[u8]) -> Result<usize>;
    fn flush(&mut self) -> Result<()>;
    fn write_all(&mut self, buf: &[u8]) -> Result<()>;
    // There's lots more
}
}

Assume we wait to write a function whose parameter is a value of any type that can write to a stream. It'd look something like this:

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

fn say_hello(out: &mut Write) -> std::io::Result<()> {
    out.write_all(b"hello!\n")?;
    out.flush();
}
}

Pronunciation: The parameter of the above out function is of type &mut Write, meaning "a mutable reference to any value that implements the Write trait.

Intro to Generics

A generic function or type can be used with values of many different types.

#![allow(unused)]
fn main() {
// Given two values, pick whichever one is less
fn min<T: Ord>(value1: T, value2: T) -> T {
    if value1 <= value2 {
        value1
    } else {
        value2
    }
}
println!("Minimum of two integers: {}", min(1, 2));
println!("Minimum of two strings: {}", min("a", "b"));
}

Pronunciation: The type parameter of the above min function is written <T: Ord>, meaning "this function can be used with arguments of any type T that implements the Ord trait". Or, more simply, "any ordered type".

Term: The T: Ord requirement of the above min function is called a bound.

Using Traits

A trait is a feature that any given type may or may not support. Think of a trait as a type capability.

Rule: For trait methods to be accessible, the trait itself must be in scope! Otherwise, all of its methods are hidden.

#![allow(unused)]
fn main() {
let mut buf: Vec<u8> = vec![];
buf.write_all(b"hello!")?; // ERR: no method named write_all
}

Adding use std::io::Write; to the top of the above file will bring the Write trait into scope and fix the issue.

Trait Objects

There are two ways to use traits:

1. Trait objects
2. Generics

Rust doesn't allow variables of type Write (the trait) because a variable's size must be known at compile-time, and types that implement Write can be of any size.

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

let mut buf: Vec<u8> = vec![];
let writer: Write = buf; // ERR: `Write` does not have a constant size
}

However, what we can do is create a value that's a reference to a trait.

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

let mut buf: Vec<u8> = vec![];
let writer: &mut Write = &mut buf; // OK!
}

Term: A reference to a trait type, like writer in the above code, is called a trait object.

Trait Object Layout

In memory, a trait object is a fat pointer (two words on the stack) consisting of a pointer to the value, plus a pointer to a table representing that value's type. That table, as is the case with C++, is called a virtual table (vtable).

Implicit Behavior: Rust automatically converts ordinary referencs into trait object when needed. This was the case with the writer variable in the above code.

Generic Functions

Earlier we created a function that accepted any parameter that implemented the Write trait (aka, a trait object):

#![allow(unused)]
fn main() {
use std::io::Write;
fn say_hello(out: &mut Write) -> std::io::Result<()> {
    out.write_all(b"hello!\n")?;
    out.flush();
}
}

We can make that function generic by tweaking the type signature:

#![allow(unused)]
fn main() {
use std::io::Write;
fn say_hello<W: Write>(out: &mut W) -> std::io::Result<()> {
    out.write_all(b"hello!\n")?;
    out.flush();
}
}

Term: In the above say_hello function, the phrase <W: Write> is what makes the function generic. W is called a type parameter. And : Write, as mentioned earlier, is the bound.

Convention: Type parameters are usually single uppercase letters.

If the generic function you're calling doesn't have any arguments that provide useful clues about the type parameter's type, you might have to spell it out using the turbofish ::<>.

Operator: If your type parameter needs to support several traits, you can chain the needed traits together using the + operator.

#![allow(unused)]
fn main() {
fn top_ten<T: Debug + Hash + Eq>(values: &Vec<T>) { ... }
}

Generic functions can have multiple type parameters:

#![allow(unused)]
fn main() {
fn run_query<M: Mapper + Serialize, R: Reducer + Serialize>(
    data: &DataSet, map: M, reduce: R,
) -> Results {
    ...
}
}

Keyword: The type parameter bounds in the above run_query function are way too long and it makes it less readable. The where keyword allows us to move the bounds outside of the <>:

#![allow(unused)]
fn main() {
fn run_query<M, R>(data: &DataSet, map: M, reduce: R) -> Results
    where M: Mapper + Serialize,
          R: Reducer + Serialize {
              ...
}
}

Shorthand: The where clause can be used anywhere bounds are permitted: generic structs, enums, type aliases, methods, etc.

A generic function can have both lifetime parameters and type parameters. Lifetime parameters come first:

#![allow(unused)]
fn main() {
// Return a ref to the point in `candidates` that's closest to `target`
fn nearest<'t, 'c, P>(target: &'t P, candidates: &'c [P]) -> &'c P
    where P: MeasureDistance {
    ...
}
}

Which to Use

Tip: Traits objects are the right choice whenever you need a collection of values of mixed types, all together. (think salad)

Generics have two major advantages over trait objects:

1. Speed. When the compiler generates machine code for a generic function, it knows which types it's working with, so it knows at that time which write method to call. No need for dynamic dispatch. Wheras with trait objects, Rust never knows what type of value a trait object points to until runtime.
2. Not every trait can support trait objects.

Defining and Implementing Traits

Defining a trait is just a matter of giving it a name and a list of type signatures of the trait's methods.

#![allow(unused)]
fn main() {
/// A trait for entities in a videogame's world that are displayed on a screen
trait Visible {
    /// Render the object on the given canvas
    fn draw(&self, canvas: &mut Canvas);

    /// Return true if clicking at (x, y) should select this object
    fn hit_test(&self, x: i32, y: i32) -> bool;
}
}

Syntax: The syntax for implementing a trait is the following: impl TraitName for Type

Implementing the Visible trait for the Broom type might look like this:

#![allow(unused)]
fn main() {
impl Visible for Broom {
    fn draw(&self, canvas: &mut Canvas) {
        for y in self.y - self.height - 1 .. self.y {
            canvas.write_at(self.x, y, '|');
        }
        canvas.write_at(self.x, self.y, 'M');
    }

    fn hit_test(&self, x: i32, y: i32) -> bool {
        self.x == x
        && self.y - self.height - 1 <= y
        && y <= self.y
    }
}
}

Default Methods

Term: Methods listed within traits can have default implementations. In such cases, it's not required that a type implementing the trait explicitly define the method.

Traits and Other People's Types

Rule: Rust lets you implement any trait on any type, as long as either the trait or the type is introduced in the current trait. This is called the coherence rule. It helps Rust ensure that trait implementations are unique.

Term: A trait that adds a single method to a type is called an extension traits.

Generic impl blocks can be used to add an extension trait to a whole family of types at once.

#![allow(unused)]
fn main() {
// Add the `write_html` method to all types that implement `Write`
use std::io::{self, Write};

// Trait for values to which you can send HTML
trait WriteHtml {
    fn write_html(&mut self, &HtmlDocument) -> io::Result<()>;
}

// Add the HTML write capability to any std:io writer
impl<W: Write> WriteHtml for W {
    fn write_html(&mut self, html: &HtmlDocument) -> io::Result<()> {
        ...
    }
}
}

Self in Traits

Traits can use the keyword Self as a type.

#![allow(unused)]
fn main() {
pub trait Clone {
    fn clone(&self) -> Self;
}
}

A trait that uses the Self type is incompatible with trait objects.

#![allow(unused)]
fn main() {
// ERR: the trait `Spliceable` cannot be made into an object
fn splice_anything(left: &Spliceable, right: &Spliceable) {
    let combo = left.splice(right);
    ...
}
}

Subtraits

We can declare that a trait is an extension of another trait.

#![allow(unused)]
fn main() {
// A living item in our videogame world
trait Creature: Visible {
    fn position(&self) -> (i32, i32);
    fn facing(&self) -> Direction;
    ...
}
}

Static Methods

Traits can include static methods and constructors.

#![allow(unused)]
fn main() {
trait StringSet {
    // constructor
    fn new() -> Self;

    // static method
    fn from_slice(strings: &[&str]) -> Self;
}
}

Trait objects don't support static methods.

Fully Qualified Method Calls

Term: A qualified method call is one that specifies the type or trait that a method is associated with. A fully qualified method call is one that specifies both type and trait.

When You Need Them

Generally, you'll use value.method() to call a method, but occasionally you'll need a qualified method call:

1. When two methods have the same name:

#![allow(unused)]
fn main() {
// Outlaw is a type that implements Visible and HasPistol, both of which have a `draw` method
let mut outlaw = Outlaw::new();

outlaw.draw(); // ERR: draw on the screen or draw pistol?

Visible::draw(&outlaw); // OK!
HasPistol::draw(&outlaw); // OK!
}

2. When the type of the self argument can't be inferred:

#![allow(unused)]
fn main() {
let zero = 0; // all we know so far is this could be i8, u8, i32, etc

zero.abs(); // ERR: which `.abs()` should be called?
i64::abs(zero); // OK!
}

3. When using the function itself as the function value:

#![allow(unused)]
fn main() {
let words: Vec<String> =
    line.split_whitespace()
        .map(<str as ToString>::to_string) // OK!
        .collect();
}

4. When calling trait methods in macros.

Traits That Define Relationships Between Types

Traits can be used in situations where there are multiple types that have to work together. They can describe relationships between types.

Associated Types (or How Iterators Work)

Rust's standard iterator trait looks a little like this:

#![allow(unused)]
fn main() {
trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}
}

Term: In the Iterator trait, Item is called an associated type. Each type that implements Iterator must specify what type of item it produces.

The implementation of Iterator for std::io::Args looks a bit like this:

#![allow(unused)]
fn main() {
impl Iterator for Args {
    // the associated `Item` type for `Args` is a `String`
    type Item = String;
    fn next(&mut self) -> Option<String> {
        ...
    }
}
}

Bounds can be placed on a trait's associated type.

#![allow(unused)]
fn main() {
fn dump<I>(iter: I) where I: Iterator, I::Item: Debug {
    ...
}
}

Or, we can place bounds on an associated type as if it were a generic type parameter of the trait:

#![allow(unused)]
fn main() {
fn dump<I>(iter: I) where I: Iterator<Item=String> {
    ...
}
}

Use Case: Associated types are perfect for cases where each implementation has one specific related type.

Generic Traits (or How Operator Overloading Works)

The trait signature for Rust's multiplication method looks a bit like this:

#![allow(unused)]
fn main() {
pub trait Mul<RHS=Self> {
    ...
}
}

The syntax RHS=Self means that the type parameter RHS defaults to Self.

Buddy Traits (or How rand::random() Works)

Term: Traits that are designed to work together are called buddy traits.

A good example of buddy trait use is in the rand, particularly the random() method, which returns a random value:

#![allow(unused)]
fn main() {
let x = rand::random();
}

Rust wouldn't be able to infer the type of x so we'd need to specify it with turbofish:

#![allow(unused)]
fn main() {
let x = rand::random::<f64>(); // float between 0.0 and 1.0
let b = rand::random::<bool>(); // true or false
}

But rand has many different kinds of random number generators (RNGs). They all implement the same trait, Rng:

#![allow(unused)]
fn main() {
// An Rng is just a value that can spit out integers on demand,
pub trait Rng {
    fn next_u32(&mut self) -> u32;
    ...
}
}

There are lots of implementations of Rng: XorShiftRing, OsRng, etc.

The Rng has a buddy trait called Rand:

#![allow(unused)]
fn main() {
// A type that can be randomly generated using an `Rng`
pub trait Rand: Sized {
    fn rand<R: Rng>(rng: &mut R) -> Self;
}
}

Rand is implemented by the types that are produced by Rng: u64, bool, etc.

Ultimately, rand::random() is just a thin wrapper that passes a globally allocated Rng to Rand::rand():

#![allow(unused)]
fn main() {
pub fn random<T: Rand>() -> T {
    T::rand(&mut global_rng())
}
}

Concept: When you see traits that use other traits as bounds, the way Rand::rand() uses Rng, you know those two traits are mix-and-match (buddy traits). Any Rng can generate values of every Rand type.