Trait Objects

There are two ways of using traits to write polymorphic code in Rust: trait objects and generics. We’ll present trait objects first and turn to generics in the next section.

Rust doesn’t permit variables of type Write:

use std::io::Write;

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

A variable’s size has to be known at compile time, and types that implement Write can be any size.

This may be surprising if you’re coming from C# or Java, but the reason is simple. In Java, a variable of type OutputStream (the Java standard interface analogous to std::io::Write) is a reference to any object that implements OutputStream. The fact that it’s a reference goes without saying. It’s the same with interfaces in C# and most other languages.

What we want in Rust is the same thing, but in Rust, references are explicit:

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

A reference to a trait type, like writer, is called a trait object. Like any other reference, a trait object points to some value, it has a lifetime, and it can be either mut or shared.

What makes a trait object different is that Rust usually doesn’t know the type of the referent at compile time. So a trait object includes a little extra information about the referent’s type. This is strictly for Rust’s own use behind the scenes: when you call writer.write(data), Rust needs the type information to dynamically call the right write method depending on the type of *writer. You can’t query the type information directly, and Rust does not support downcasting from the trait object &mut Write back to a concrete type like Vec<u8>.

Trait Object Layout

In memory, a trait object is a fat pointer consisting of a pointer to the value, plus a pointer to a table representing that value’s type. Each trait object therefore takes up two machine words, as shown in Figure 11-1.

Figure 11-1. Trait objects in memory

C++ has this kind of run-time type information as well. It’s called a virtual table, or vtable. In Rust, as in C++, the vtable is generated once, at compile time, and shared by all objects of the same type. Everything shown in dark gray in Figure 11-1, including the vtable, is a private implementation detail of Rust. Again, these aren’t fields and data structures that you can access directly. Instead, the language automatically uses the vtable when you call a method of a trait object, to determine which implementation to call.

Seasoned C++ programmers will notice that Rust and C++ use memory a bit differently. In C++, the vtable pointer, or vptr, is stored as part of the struct. Rust uses fat pointers instead. The struct itself contains nothing but its fields. This way, a struct can implement dozens of traits without containing dozens of vptrs. Even types like i32, which aren’t big enough to accommodate a vptr, can implement traits.

Rust automatically converts ordinary references into trait objects when needed. This is why we’re able to pass &mut local_file to say_hello in this example:

let mut local_file = File::create("hello.txt")?;
say_hello(&mut local_file)?;

The type of &mut local_file is &mut File, and the type of the argument to say_hello is &mut Write. Since a File is a kind of writer, Rust allows this, automatically converting the plain reference to a trait object.

Likewise, Rust will happily convert a Box<File> to a Box<Write>, a value that owns a writer in the heap:

let w: Box<Write> = Box::new(local_file);

Box<Write>, like &mut Write, is a fat pointer: it contains the address of the writer itself and the address of the vtable. The same goes for other pointer types, like Rc<Write>.

This kind of conversion is the only way to create a trait object. What the computer is actually doing here is very simple. At the point where the conversion happens, Rust knows the referent’s true type (in this case, File), so it just adds the address of the appropriate vtable, turning the regular pointer into a fat pointer.

Generic Functions

At the beginning of this chapter, we showed a say_hello() function that took a trait object as an argument. Let’s rewrite that function as a generic function:

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

Only the type signature has changed:

fn say_hello(out: &mut Write)         // plain function

fn say_hello<W: Write>(out: &mut W)   // generic function

The phrase <W: Write> is what makes the function generic. This is a type parameter. It means that throughout the body of this function, W stands for some type that implements the Write trait. Type parameters are usually single uppercase letters, by convention.

Which type W stands for depends on how the generic function is used:

say_hello(&mut local_file)?;  // calls say_hello::<File>
say_hello(&mut bytes)?;       // calls say_hello::<Vec<u8>>

When you pass &mut local_file to the generic say_hello() function, you’re calling say_hello::<File>(). Rust generates machine code for this function that calls File::write_all() and File::flush(). When you pass &mut bytes, you’re calling say_hello::<Vec<u8>>(). Rust generates separate machine code for this version of the function, calling the corresponding Vec<u8> methods. In both cases, Rust infers the type W from the type of the argument. You can always spell out the type parameters:

say_hello::<File>(&mut local_file)?;

but it’s seldom necessary, because Rust can usually deduce the type parameters by looking at the arguments. Here, the say_hello generic function expects a &mut W argument, and we’re passing it a &mut File, so Rust infers that W = File.

If the generic function you’re calling doesn’t have any arguments that provide useful clues, you may have to spell it out:

// calling a generic method collect<C>() that takes no arguments
let v1 = (0 .. 1000).collect();  // error: can't infer type
let v2 = (0 .. 1000).collect::<Vec<i32>>(); // ok

Sometimes we need multiple abilities from a type parameter. For example, if we want to print out the top 10 most common values in a vector, we’ll need for those values to be printable:

use std::fmt::Debug;

fn top_ten<T: Debug>(values: &Vec<T>) { ... }

But this isn’t good enough. How are we planning to determine which values are the most common? The usual way is to use the values as keys in a hash table. That means the values need to support the Hash and Eq operations. The bounds on T must include these as well as Debug. The syntax for this uses the + sign:

fn top_ten<T: Debug + Hash + Eq>(values: &Vec<T>) { ... }

Some types implement Debug, some implement Hash, some support Eq; and a few, like u32 and String, implement all three, as shown in Figure 11-2.

Figure 11-2. Traits as sets of types

It’s also possible for a type parameter to have no bounds at all, but you can’t do much with a value if you haven’t specified any bounds for it. You can move it. You can put it into a box or vector. That’s about it.

Generic functions can have multiple type parameters:

/// Run a query on a large, partitioned data set.
/// See <http://research.google.com/archive/mapreduce.html>.
fn run_query<M: Mapper + Serialize, R: Reducer + Serialize>(
    data: &DataSet, map: M, reduce: R) -> Results
{ ... }

As this example shows, the bounds can get to be so long that they are hard on the eyes. Rust provides an alternative syntax using the keyword where:

fn run_query<M, R>(data: &DataSet, map: M, reduce: R) -> Results
    where M: Mapper + Serialize,
          R: Reducer + Serialize
{ ... }

The type parameters M and R are still declared up front, but the bounds are moved to separate lines. This kind of where clause is also allowed on generic structs, enums, type aliases, and methods—anywhere bounds are permitted.

Of course, an alternative to where clauses is to keep it simple: find a way to write the program without using generics quite so intensively.

“Receiving References as Parameters” introduced the syntax for lifetime parameters. A generic function can have both lifetime parameters and type parameters. Lifetime parameters come first.

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

This function takes two arguments, target and candidates. Both are references, and we give them distinct lifetimes 't and 'c (as discussed in “Distinct Lifetime Parameters”). Furthermore, the function works with any type P that implements the MeasureDistance trait, so we might use it on Point2d values in one program and Point3d values in another.

Lifetimes never have any impact on machine code. Two calls to nearest() using the same type P, but different lifetimes, will call the same compiled function. Only differing types cause Rust to compile multiple copies of a generic function.

Of course, functions are not the only kind of generic code in Rust.

• We’ve already covered generic types in “Generic Structs” and “Generic Enums”.

• An individual method can be generic, even if the type it’s defined on is not generic:

  impl PancakeStack {
      fn push<T: Topping>(&mut self, goop: T) -> PancakeResult<()> {
          ...
      }
  }

• Type aliases can be generic, too:

  type PancakeResult<T> = Result<T, PancakeError>;

• We’ll cover generic traits later in this chapter.

All the features introduced in this section—bounds, where clauses, lifetime parameters, and so forth—can be used on all generic items, not just functions.

Which to Use

The choice of whether to use trait objects or generic code is subtle. Since both features are based on traits, they have a lot in common.

Trait objects are the right choice whenever you need a collection of values of mixed types, all together. It is technically possible to make generic salad:

trait Vegetable {
    ...
}

struct Salad<V: Vegetable> {
    veggies: Vec<V>
}

but this is a rather severe design. Each such salad consists entirely of a single type of vegetable. Not everyone is cut out for this sort of thing. One of your authors once paid $14 for a Salad<IcebergLettuce> and has never quite gotten over the experience.

How can we build a better salad? Since Vegetable values can be all different sizes, we can’t ask Rust for a Vec<Vegetable>:

struct Salad {
    veggies: Vec<Vegetable>  // error: `Vegetable` does not have
                             //        a constant size
}

Trait objects are the solution:

struct Salad {
    veggies: Vec<Box<Vegetable>>
}

Each Box<Vegetable> can own any type of vegetable, but the box itself has a constant size—two pointers—suitable for storing in a vector. Apart from the unfortunate mixed metaphor of having boxes in one’s food, this is precisely what’s called for, and it would work out just as well for shapes in a drawing app, monsters in a game, pluggable routing algorithms in a network router, and so on.

Another possible reason to use trait objects is to reduce the total amount of compiled code. Rust may have to compile a generic function many times, once for each type it’s used with. This could make the binary large, a phenomenon called code bloat in C++ circles. These days, memory is plentiful, and most of us have the luxury of ignoring code size; but constrained environments do exist.

Outside of situations involving salad or microcontrollers, generics have two important advantages over trait objects, with the result that in Rust, generics are the more common choice.

The first advantage is speed. Each time the Rust 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. There’s no need for dynamic dispatch.

The generic min() function shown in the introduction is just as fast as if we had written separate functions min_u8, min_i64, min_string, and so on. The compiler can inline it, like any other function, so in a release build, a call to min::<i32> is likely just two or three instructions. A call with constant arguments, like min(5, 3), will be even faster: Rust can evaluate it at compile time, so that there’s no runtime cost at all.

Or consider this generic function call:

let mut sink = std::io::sink();
say_hello(&mut sink)?;

std::io::sink() returns a writer of type Sink that quietly discards all bytes written to it.

When Rust generates machine code for this, it could emit code that calls Sink::write_all, checks for errors, then calls Sink::flush. That’s what the body of the generic function says to do.

Or, Rust could look at those methods and realize the following:

• Sink::write_all() does nothing.

• Sink::flush() does nothing.

• Neither method ever returns an error.

In short, Rust has all the information it needs to optimize away this function entirely.

Compare that to the behavior with trait objects. Rust never knows what type of value a trait object points to until run time. So even if you pass a Sink, the overhead of calling virtual methods and checking for errors still applies.

The second advantage of generics is that not every trait can support trait objects. Traits support several features, such as static methods, that work only with generics: they rule out trait objects entirely. We’ll point out these features as we come to them.

Default Methods

The Sink writer type we discussed earlier can be implemented in a few lines of code. First, we define the type:

/// A Writer that ignores whatever data you write to it.
pub struct Sink;

Sink is an empty struct, since we don’t need to store any data in it. Next, we provide an implementation of the Write trait for Sink:

use std::io::{Write, Result};

impl Write for Sink {
    fn write(&mut self, buf: &[u8]) -> Result<usize> {
        // Claim to have successfully written the whole buffer.
        Ok(buf.len())
    }

    fn flush(&mut self) -> Result<()> {
        Ok(())
    }
}

So far, this is very much like the Visible trait. But we have also seen that the Write trait has a write_all method:

out.write_all(b"hello world
")?;

Why does Rust let us impl Write for Sink without defining this method? The answer is that the standard library’s definition of the Write trait contains a default implementation for write_all:

trait Write {
    fn write(&mut self, buf: &[u8]) -> Result<usize>;
    fn flush(&mut self) -> Result<()>;

    fn write_all(&mut self, buf: &[u8]) -> Result<()> {
        let mut bytes_written = 0;
        while bytes_written < buf.len() {
            bytes_written += self.write(&buf[bytes_written..])?;
        }
        Ok(())
    }

    ...
}

The write and flush methods are the basic methods that every writer must implement. A writer may also implement write_all, but if not, the default implementation shown above will be used.

Your own traits can include default implementations using the same syntax.

The most dramatic use of default methods in the standard library is the Iterator trait, which has one required method (.next()) and dozens of default methods. Chapter 15 explains why.

Traits and Other People’s Types

Rust lets you implement any trait on any type, as long as either the trait or the type is introduced in the current crate.

This means that any time you want to add a method to any type, you can use a trait to do it:

trait IsEmoji {
    fn is_emoji(&self) -> bool;
}

/// Implement IsEmoji for the built-in character type.
impl IsEmoji for char {
    fn is_emoji(&self) -> bool {
        ...
    }
}

assert_eq!('$'.is_emoji(), false);

Like any other trait method, this new is_emoji method is only visible when IsEmoji is in scope.

The sole purpose of this particular trait is to add a method to an existing type, char. This is called an extension trait. Of course, you can add this trait to types, too, by writing impl IsEmoji for str { ... } and so forth.

You can even use a generic impl block to add an extension trait to a whole family of types at once. The following extension trait adds a method to all Rust writers:

use std::io::{self, Write};

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

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

The line impl<W: Write> WriteHtml for W means “for every type W that implements Write, here’s an implementation of WriteHtml for W.”

The serde library offers a nice example of how useful it can be to implement user-defined traits on standard types. serde is a serialization library. That is, you can use it to write Rust data structures to disk and reload them later. The library defines a trait, Serialize, that’s implemented for every data type the library supports. So in the serde source code, there is code implementing Serialize for bool, i8, i16, i32, array and tuple types, and so on, through all the standard data structures like Vec and HashMap.

The upshot of all this is that serde adds a .serialize() method to all these types. It can be used like this:

use serde::Serialize;
use serde_json;

pub fn save_configuration(config: &HashMap<String, String>)
    -> std::io::Result<()>
{
    // Create a JSON serializer to write the data to a file.
    let writer = File::create(config_filename())?;
    let mut serializer = serde_json::Serializer::new(writer);

    // The serde `.serialize()` method does the rest.
    config.serialize(&mut serializer)?;

    Ok(())
}

We said earlier that when you implement a trait, either the trait or the type must be new in the current crate. This is called the coherence rule. It helps Rust ensure that trait implementations are unique. Your code can’t impl Write for u8, because both Write and u8 are defined in the standard library. If Rust let crates do that, there could be multiple implementations of Write for u8, in different crates, and Rust would have no reasonable way to decide which implementation to use for a given method call.

(C++ has a similar uniqueness restriction: the One Definition Rule. In typical C++ fashion, it isn’t enforced by the compiler, except in the simplest cases, and you get undefined behavior if you break it.)

Self in Traits

A trait can use the keyword Self as a type. The standard Clone trait, for example, looks like this (slightly simplified):

pub trait Clone {
    fn clone(&self) -> Self;
    ...
}

Using Self as the return type here means that the type of x.clone() is the same as the type of x, whatever that might be. If x is a String, then the type of x.clone() is String—not Clone or any other cloneable type.

Likewise, if we define this trait:

pub trait Spliceable {
    fn splice(&self, other: &Self) -> Self;
}

with two implementations:

impl Spliceable for CherryTree {
    fn splice(&self, other: &Self) -> Self {
        ...
    }
}

impl Spliceable for Mammoth {
    fn splice(&self, other: &Self) -> Self {
        ...
    }
}

then inside the first impl, Self is simply an alias for CherryTree, and in the second, it’s an alias for Mammoth. This means that we can splice together two cherry trees or two mammoths, not that we can create a mammoth-cherry hybrid. The type of self and the type of other must match.

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

// error: the trait `Spliceable` cannot be made into an object
fn splice_anything(left: &Spliceable, right: &Spliceable) {
    let combo = left.splice(right);
    ...
}

The reason is something we’ll see again and again as we dig into the advanced features of traits. Rust rejects this code because it has no way to type-check the call left.splice(right). The whole point of trait objects is that the type isn’t known until runtime. Rust has no way to know at compile time if left and right will be the same type, as required.

Trait objects are really intended for the simplest kinds of traits, the kinds that could be implemented using interfaces in Java or abstract base classes in C++. The more advanced features of traits are useful, but they can’t coexist with trait objects because with trait objects, you lose the type information Rust needs to type-check your program.

Now, had we wanted genetically improbable splicing, we could have designed a trait-object-friendly trait:

pub trait MegaSpliceable {
    fn splice(&self, other: &MegaSpliceable) -> Box<MegaSpliceable>;
}

This trait is compatible with trait objects. There’s no problem type-checking calls to this .splice() method because the type of the argument other is not required to match the type of self, as long as both types are MegaSpliceable.

Subtraits

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

/// Someone in the game world, either the player or some other
/// pixie, gargoyle, squirrel, ogre, etc.
trait Creature: Visible {
    fn position(&self) -> (i32, i32);
    fn facing(&self) -> Direction;
    ...
}

The phrase trait Creature: Visible means that all creatures are visible. Every type that implements Creature must also implement the Visible trait:

impl Visible for Broom {
    ...
}

impl Creature for Broom {
    ...
}

We can implement the two traits in either order, but it’s an error to implement Creature for a type without also implementing Visible.

Subtraits are like subinterfaces in Java or C#. They’re a way to describe a trait that extends an existing trait with a few more methods. In this example, all your code that works with Creatures can also use the methods from the Visible trait.

Static Methods

In most object-oriented languages, interfaces can’t include static methods or constructors. However, Rust traits can include static methods and constructors, here is how:

trait StringSet {
    /// Return a new empty set.
    fn new() -> Self;

    /// Return a set that contains all the strings in `strings`.
    fn from_slice(strings: &[&str]) -> Self;

    /// Find out if this set contains a particular `value`.
    fn contains(&self, string: &str) -> bool;

    /// Add a string to this set.
    fn add(&mut self, string: &str);
}

Every type that implements the StringSet trait must implement these four associated functions. The first two, new() and from_slice(), don’t take a self argument. They serve as constructors.

In nongeneric code, these functions can be called using :: syntax, just like any other static method:

// Create sets of two hypothetical types that impl StringSet:
let set1 = SortedStringSet::new();
let set2 = HashedStringSet::new();

In generic code, it’s the same, except the type is often a type variable, as in the call to S::new() shown here:

/// Return the set of words in `document` that aren't in `wordlist`.
fn unknown_words<S: StringSet>(document: &Vec<String>, wordlist: &S) -> S {
    let mut unknowns = S::new();
    for word in document {
        if !wordlist.contains(word) {
            unknowns.add(word);
        }
    }
    unknowns
}

Like Java and C# interfaces, trait objects don’t support static methods. If you want to use &StringSet trait objects, you must change the trait, adding the bound where Self: Sized to each static method:

trait StringSet {
    fn new() -> Self
        where Self: Sized;

    fn from_slice(strings: &[&str]) -> Self
        where Self: Sized;

    fn contains(&self, string: &str) -> bool;

    fn add(&mut self, string: &str);
}

This bound tells Rust that trait objects are excused from supporting this method. StringSet trait objects are then allowed; they still don’t support the two static methods, but you can create them and use them to call .contains() and .add(). The same trick works for any other method that is incompatible with trait objects. (We will forgo the rather tedious technical explanation of why this works, but the Sized trait is covered in Chapter 13.)

Associated Types (or How Iterators Work)

We’ll start with iterators. By now every object-oriented language has some sort of built-in support for iterators, objects that represent the traversal of some sequence of values.

Rust has a standard Iterator trait, defined like this:

pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
    ...
}

The first feature of this trait, type Item;, is an associated type. Each type that implements Iterator must specify what type of item it produces.

The second feature, the next() method, uses the associated type in its return value. next() returns an Option<Self::Item>: either Some(item), the next value in the sequence, or None when there are no more values to visit. The type is written as Self::Item, not just plain Item, because Item is a feature of each type of iterator, not a standalone type. As always, self and the Self type show up explicitly in the code everywhere their fields, methods, and so on are used.

Here’s what it looks like to implement Iterator for a type:

// (code from the std::env standard library module)
impl Iterator for Args {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        ...
    }
    ...
}

std::env::Args is the type of iterator returned by the standard library function std::env::args() that we used in Chapter 2 to access command-line arguments. It produces String values, so the impl declares type Item = String;.

Generic code can use associated types:

/// Loop over an iterator, storing the values in a new vector.
fn collect_into_vector<I: Iterator>(iter: I) -> Vec<I::Item> {
    let mut results = Vec::new();
    for value in iter {
        results.push(value);
    }
    results
}

Inside the body of this function, Rust infers the type of value for us, which is nice; but we must spell out the return type of collect_into_vector, and the Item associated type is the only way to do that. (Vec<I> would be simply wrong: we would be claiming to return a vector of iterators!)

The preceding example is not code that you would write out yourself, because after reading Chapter 15, you’ll know that iterators already have a standard method that does this: iter.collect(). So let’s look at one more example before moving on.

/// Print out all the values produced by an iterator
fn dump<I>(iter: I)
    where I: Iterator
{
    for (index, value) in iter.enumerate() {
        println!("{}: {:?}", index, value);   // error
    }
}

This almost works. There is just one problem: value might not be a printable type.

error[E0277]: the trait bound `<I as std::iter::Iterator>::Item:
              std::fmt::Debug` is not satisfied
  --> traits_dump.rs:10:37
   |
10 | println!("{}: {:?}", index, value);   // error
   |                             ^^^^^ the trait `std::fmt::Debug`
   |                                   is not implemented for
   |                                   `<I as std::iter::Iterator>::Item`
   |
   = help: consider adding a
           `where <I as std::iter::Iterator>::Item: std::fmt::Debug` bound
   = note: required by `std::fmt::Debug::fmt`

The error message is slightly obfuscated by Rust’s use of the syntax <I as std::iter::Iterator>::Item, which is a long, maximally explicit way of saying I::Item. This is valid Rust syntax, but you’ll rarely actually need to write a type out that way.

The gist of the error message is that to make this generic function compile, we must ensure that I::Item implements the Debug trait, the trait for formatting values with {:?}. We can do this by placing a bound on I::Item:

use std::fmt::Debug;

fn dump<I>(iter: I)
    where I: Iterator, I::Item: Debug
{
    ...
}

Or, we could write, “I must be an iterator over String values”:

fn dump<I>(iter: I)
    where I: Iterator<Item=String>
{
    ...
}

Iterator<Item=String> is itself a trait. If you think of Iterator as the set of all iterator types, then Iterator<Item=String> is a subset of Iterator: the set of iterator types that produce Strings. This syntax can be used anywhere the name of a trait can be used, including trait object types:

fn dump(iter: &mut Iterator<Item=String>) {
    for (index, s) in iter.enumerate() {
        println!("{}: {:?}", index, s);
    }
}

Traits with associated types, like Iterator, are compatible with trait methods, but only if all the associated types are spelled out, as shown here. Otherwise, the type of s could be anything, and again, Rust would have no way to type-check this code.

We’ve shown a lot of examples involving iterators. It’s hard not to; they’re by far the most prominent use of associated types. But associated types are generally useful whenever a trait needs to cover more than just methods.

• In a thread pool library, a Task trait, representing a unit of work, could have an associated Output type.

• A Pattern trait, representing a way of searching a string, could have an associated Match type, representing all the information gathered by matching the pattern to the string.

  trait Pattern {
      type Match;
  
      fn search(&self, string: &str) -> Option<Self::Match>;
  }
  
  /// You can search a string for a particular character.
  impl Pattern for char {
      /// A "match" is just the location where the
      /// character was found.
      type Match = usize;
  
      fn search(&self, string: &str) -> Option<usize> {
          ...
      }
  }

  If you’re familiar with regular expressions, it’s easy to see how impl Pattern for RegExp would have a more elaborate Match type, probably a struct that would include the start and length of the match, the locations where parenthesized groups matched, and so on.

• A library for working with relational databases might have a Database​Connection trait with associated types representing transactions, cursors, prepared statements, and so on.

Associated types are perfect for cases where each implementation has one specific related type: each type of Task produces a particular type of Output; each type of Pattern looks for a particular type of Match. However, as we’ll see, some relationships among types are not like this.

Generic Traits (or How Operator Overloading Works)

Multiplication in Rust uses this trait:

/// std::ops::Mul, the trait for types that support `*`.
pub trait Mul<RHS> {
    /// The resulting type after applying the `*` operator
    type Output;

    /// The method for the `*` operator
    fn mul(self, rhs: RHS) -> Self::Output;
}

Mul is a generic trait. The type parameter, RHS, is short for right hand side.

The type parameter here means the same thing that it means on a struct or function: Mul is a generic trait, and its instances Mul<f64>, Mul<String>, Mul<Size>, etc. are all different traits, just as min::<i32> and min::<String> are different functions and Vec<i32> and Vec<String> are different types.

A single type—say, WindowSize—can implement both Mul<f64> and Mul<i32>, and many more. You would then be able to multiply a WindowSize by many other types. Each implementation would have its own associated Output type.

The trait shown above is missing one minor detail. The real Mul trait looks like this:

pub trait Mul<RHS=Self> {
    ...
}

The syntax RHS=Self means that RHS defaults to Self. If I write impl Mul for Complex, without specifying Mul’s type parameter, it means impl Mul<Complex> for Complex. In a bound, if I write where T: Mul, it means where T: Mul<T>.

In Rust, the expression lhs * rhs is shorthand for Mul::mul(lhs, rhs). So overloading the * operator in Rust is as simple as implementing the Mul trait. We’ll show examples in the next chapter.

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

There’s one more way to use traits to express relationships between types. This way is perhaps the simplest of the bunch, since you don’t have to learn any new language features to understand it: what we’ll call buddy traits are simply traits that are designed to work together.

There’s a good example inside the rand crate, a popular crate for generating random numbers. The main feature of rand is the random() function, which returns a random value:

use rand::random;
let x = random();

If Rust can’t infer the type of the random value, which is often the case, you must specify it:

let x = random::<f64>();   // a number, 0.0 <= x < 1.0
let b = random::<bool>();  // true or false

For many programs, this one generic function is all you need. But the rand crate also offers several different, but interoperable, random number generators. All the random number generators in the library implement a common trait:

/// A random number generator.
pub trait Rng {
    fn next_u32(&mut self) -> u32;
    ...
}

An Rng is simply a value that can spit out integers on demand. The rand library provides a few different implementations, including XorShiftRng (a fast pseudorandom number generator) and OsRng (much slower, but truly unpredictable, for use in cryptography).

The buddy trait is called Rand:

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

Types like f64 and bool implement this trait. Pass any random number generator to their ::rand() method, and it returns a random value:

let x = f64::rand(rng);
let b = bool::rand(rng);

In fact random() is nothing but a thin wrapper that passes a globally allocated Rng to this rand method. One way to implement it is like this:

pub fn random<T: Rand>() -> T {
    T::rand(&mut global_rng())
}

When you see traits that use other traits as bounds, the way Rand::rand() uses Rng, you know that those two traits are mix-and-match: any Rng can generate values of every Rand type. Since the methods involved are generic, Rust generates optimized machine code for each combination of Rng and Rand that your program actually uses.

The two traits also serve to separate concerns. Whether you’re implementing Rand for your Monster type or implementing a spectacularly fast but not-so-random Rng, you don’t have to do anything special for those two pieces of code to be able to work together, as shown in Figure 11-3.

Figure 11-3. Buddy traits illustrated. The Rng types listed on the left are real random number generators provided by the rand crate.

The standard library’s support for computing hash codes provides another example of buddy traits. Types that implement Hash are hashable, so they can be used as hash table keys. Types that implement Hasher are hashing algorithms. The two are linked in the same way as Rand and Rng: Hash has a generic method Hash::hash() that accepts any type of Hasher as an argument.

Another example is the serde library’s Serialize trait, which you saw in “Traits and Other People’s Types”. It has a buddy trait we didn’t talk about: the Serializer trait, which represents the output format. serde supports pluggable serialization formats. There are Serializer implementations for JSON, YAML, a binary format called CBOR, and so on. Thanks to the close relationship between the two traits, every format automatically supports every serializable type.

In the last three sections, we’ve shown three ways traits can describe relationships between types. All of these can also be seen as ways of avoiding virtual method overhead and downcasts, since they allow Rust to know more concrete types at compile time.