Item 2: Use the type system to express common behaviour

Item 1 discussed how to express data structures in the type system; this Item moves on to discuss the encoding of behaviour in Rust's type system.

Methods

The first place where behaviour is visible in Rust's type system is the addition of methods to data structures: functions that act on an item of that type, identified by self. This encapsulates related data and code together in a object-oriented way that's similar to other languages; however, in Rust methods can be added to to enum types as well as to struct types, in keeping with the pervasive nature of Rust's enum (Item 1).

#![allow(unused)]
fn main() {
enum Shape {
    Rectangle { width: f64, height: f64 },
    Circle { radius: f64 },
}

impl Shape {
    pub fn area(&self) -> f64 {
        match self {
            Shape::Rectangle { width, height } => width * height,
            Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
        }
    }
}
}

The name of a method gives a label for the behaviour that it encodes, and the method signature gives type information for its inputs and outputs. The first input for a method will be some variant of self, indicating what the method might do to the data structure:

A &self parameter indicates that the contents of the data structure may be read from, but will not be modified.
A &mut self parameter indicates that the method might modify the contents of the data structure.
A self parameter indicates that the method consumes the data structure.

Abstracting Behaviour

Invoking a method always results in the same code being executed; all that changes from invocation to invocation is the data that the method operates on. That covers a lot of possible scenarios, but what if the code needs to vary at runtime?

Rust includes several features in its type system to accomodate this, which this section explores.

Function Pointers

The simplest behavioural abstraction is the function pointer: a pointer to (just) some code, with a type that reflects the signature of the function. The type is checked at compile time, so by the time the program runs the value is just the size of a pointer.

    fn sum(x: i32, y: i32) -> i32 {
        x + y
    }
    // Explicit coercion to `fn` type is required...
    let op: fn(i32, i32) -> i32 = sum;

Function pointers have no other data associated with them, so they can be treated as values in various ways:

    // `fn` types implement `Copy`
    let op1 = op;
    let op2 = op;
    // `fn` types implement `Eq`
    assert!(op1 == op2);
    // `fn` implements `std::fmt::Pointer`, used by the {:p} format specifier.
    println!("op = {:p}", op);
    // Example output: "op = 0x101e9aeb0"

One technical detail to watch out for: explicit coercion to a fn type is needed, because just using the name of a function doesn't give you something of fn type;

        let op1 = sum;
        let op2 = sum;
        // Both op1 and op2 are of a type that cannot be named in user code,
        // and this internal type does not implement `Eq`.
        assert!(op1 == op2);

error[E0369]: binary operation `==` cannot be applied to type `fn(i32, i32) -> i32 {main::sum}`
   --> use-types-behaviour/src/main.rs:117:21
    |
117 |         assert!(op1 == op2);
    |                 --- ^^ --- fn(i32, i32) -> i32 {main::sum}
    |                 |
    |                 fn(i32, i32) -> i32 {main::sum}
    |
help: you might have forgotten to call this function
    |
117 |         assert!(op1( /* arguments */ ) == op2);
    |                    +++++++++++++++++++
help: you might have forgotten to call this function
    |
117 |         assert!(op1 == op2( /* arguments */ ));
    |                           +++++++++++++++++++

Instead, the compiler error indicates that the type is something like fn(i32, i32) -> i32 {main::sum}, a type that's entirely internal to the compiler (i.e. could not be written in user code), and which identifies the specific function as well as its signature. To put it another way, the type of sum encodes both the function's signature and its location (for optimization reasons); this type can be automatically coerced (Item 6) to a fn type.

Closures

Bare function pointers are limiting, because the only inputs available to the invoked function are those that are explicitly passed as parameter values.

For example, consider some code that modified every element of a slice using a function pointer.

#![allow(unused)]
fn main() {
    // In real code, an `Iterator` method would be more appropriate.
    pub fn modify_all(data: &mut [u32], mutator: fn(u32) -> u32) {
        for value in data {
            *value = mutator(*value);
        }
    }
}

This works for a simple mutation of the slice:

        fn add2(v: u32) -> u32 {
            v + 2
        }
        let mut data = vec![1, 2, 3];
        modify_all(&mut data, add2);
        assert_eq!(data, vec![3, 4, 5,]);

However, if the modification relies on any additional state, it's not possible to implicitly pass that into the function pointer.

        let amount_to_add = 3;
        fn add_n(v: u32) -> u32 {
            v + amount_to_add
        }
        let mut data = vec![1, 2, 3];
        modify_all(&mut data, add_n);
        assert_eq!(data, vec![3, 4, 5,]);

error[E0434]: can't capture dynamic environment in a fn item
   --> use-types-behaviour/src/main.rs:142:17
    |
142 |             v + amount_to_add
    |                 ^^^^^^^^^^^^^
    |
    = help: use the `|| { ... }` closure form instead

The error message points to the right tool for the job: a closure. A closure is a chunk of code that looks like the body of a function definition (a lambda expression), except that:

it can be built as part of an expression, and so need not have a name associated with it
the input parameters are given in vertical bars |param1, param2| (their associated types can usually be automatically deduced by the compiler)
it can capture parts of the environment around it.

#![allow(unused)]
fn main() {
    let amount_to_add = 3;
    let add_n = |y| {
        // a closure capturing `amount_to_add`
        y + amount_to_add
    };
    let z = add_n(5);
    assert_eq!(z, 8);
}

To (roughly) understand how the capture works, imagine that the compiler creates a one-off, internal type that holds all of the parts of the environment that get mentioned in the lambda expression. When the closure is created, an instance of this ephemeral type is created to hold the relevant values, and when the closure is invoked that instance is used as additional context.

#![allow(unused)]
fn main() {
    let amount_to_add = 3;
    // *Rough* equivalent to a capturing closure.
    struct InternalContext<'a> {
        // references to captured variables
        amount_to_add: &'a u32,
    }
    impl<'a> InternalContext<'a> {
        fn internal_op(&self, y: u32) -> u32 {
            // body of the lambda expression
            y + *self.amount_to_add
        }
    }
    let add_n = InternalContext {
        amount_to_add: &amount_to_add,
    };
    let z = add_n.internal_op(5);
    assert_eq!(z, 8);
}

The values that are held in this notional context are often references (Item 9) as here, but they can also be mutable references to things in the environment, or values that are moved out of the environment altogether (by using the move keyword before the input parameters).

Returning to the modify_all example, a closure can't be used where a function pointer is expected.

error[E0308]: mismatched types
   --> use-types-behaviour/src/main.rs:165:31
    |
165 |         modify_all(&mut data, |y| y + amount_to_add);
    |                               ^^^^^^^^^^^^^^^^^^^^^ expected fn pointer, found closure
    |
    = note: expected fn pointer `fn(u32) -> u32`
                  found closure `[closure@use-types-behaviour/src/main.rs:165:31: 165:52]`
note: closures can only be coerced to `fn` types if they do not capture any variables
   --> use-types-behaviour/src/main.rs:165:39
    |
165 |         modify_all(&mut data, |y| y + amount_to_add);
    |                                       ^^^^^^^^^^^^^ `amount_to_add` captured here

Instead, the code that receives the closure has to accept an instance of one of the Fn* traits.

#![allow(unused)]
fn main() {
    pub fn modify_all<F>(data: &mut [u32], mut mutator: F)
    where
        F: FnMut(u32) -> u32,
    {
        for value in data {
            *value = mutator(*value);
        }
    }
}

Rust has three different Fn* traits, which between them express some distinctions around this environment capturing behaviour.

FnOnce describes a closure that can only be called once. If some part of its environment is moved into the closure, then that move can only happen once – there's no other copy of the source item to move from – and so the closure can only be invoked once.
FnMut describes a closure that can be called repeatedly, and which can make changes to its environment because it mutably borrows from the environment.
Fn describes a closure that can be called repeatedly, and which only borrows values from the environment immutably.

The compiler automatically implements the appropriate subset of these Fn* traits for any lambda expression in the code; it's not possible to manually implement any of these traits¹ (unlike C++'s operator() overload).

Returning to the rough mental model of closures above, which of the traits the compiler auto-implements roughly corresponds to whether the captured environmental context has:

FnOnce: any moved values
FnMut: any mutable references to values (&mut T)
Fn: only normal references to values (&T).

The latter two traits in the list above each has a trait bound of the preceding trait, which makes sense when you consider the things that use the closures.

If something only expects to call a closure once (indicated by receiving a FnOnce), it's OK to pass it a closure that's capable of being repeatedly called (FnMut).
If something expects to repeatedly call a closure that might mutate its environment (indicated by receiving a FnMut), it's OK to pass it a closure that doesn't need to mutate its environment (Fn).

The bare function pointer type fn also notionally belongs at the end of this list; any (not-unsafe) fn type automatically implements all of the Fn* traits, because it borrows nothing from the environment.

As a result, when writing code that accepts closures, use the most general Fn* trait that works, to allow the greatest flexibility for callers – for example, accept FnOnce for closures that are only used once. The same reasoning also leads to advice to prefer Fn* trait bounds to bare function pointers (fn).

Traits

The Fn* traits are more flexible than a bare function pointer, but they can still only describe the behaviour of a single function, and even then only in terms of the function's signature.

However, they are themselves examples of another mechanism for describing behaviour in Rust's type system, the trait. A trait defines a set of related methods that some underlying item makes publicly available. Each method in a trait also has a name, providing a label which allows the compiler to disambiguate methods with the same signature, and more importantly which allows programmers to deduce the intent of the method.

A Rust trait is roughly analogous to an "interface" in Go and Java, or to an "abstract class" (all virtual methods, no data members) in C++. Implementations of the trait must provide all the methods (but note that the trait definition can include a default implementation, Item 13), and can also have associated data that those implementations make use of. This means that code and data gets encapsulated together in a common abstraction, in a somewhat object-oriented manner.

Code that accepts a struct and calls methods on it is constrained to only ever work with that specific type. If there are multiple types that implement common behaviour, then it is more flexible to define a trait that encapsulates that common behaviour, and have the code make use of the trait's methods rather than methods on a specific struct.

This leads to the same kind of advice that turns up for other OO-influenced languages²: prefer accepting trait types to concrete types if future flexibility is anticipated.

Sometimes, there is some behaviour that you want to distinguish in the type system, but which cannot be expressed as some specific method signature in a trait definition. For example, consider a trait for sorting collections; an implementation might be stable (elements that compare the same will appear in the same order before and after the sort) but there's no way to express this in the sort method arguments.

In this case, it's still worth using the type system to track this requirement, using a marker trait.

#![allow(unused)]
fn main() {
pub trait Sort {
    /// Re-arrange contents into sorted order.
    fn sort(&mut self);
}

/// Marker trait to indicate that a [`Sortable`] sorts stably.
pub trait StableSort: Sort {}
}

A marker trait has no methods, but an implementation still has to declare that it is implementing the trait – which acts as a promise from the implementer: "I solemnly swear that my implementation sorts stably". Code that relies on a stable sort can then specify the StableSort trait bound, relying on the honour system to preserve its invariants. Use marker traits to distinguish behaviours that cannot be expressed in the trait method signatures.

Once behaviour has been encapsulated into Rust's type system as a trait, there are two ways it can be used:

as a trait bound, which constrains what types are acceptable for a generic data type or method at compile-time, or
as a trait object. which constrains what types can be stored or passed to a method at run-time.

Item 12 discusses the trade-offs between these in more detail.

A trait bound indicates that generic code which is parameterized by some type T can only be used when that type T implements some specific trait. The presence of the trait bound means that the implementation of the generic can use the methods from that trait, secure in the knowledge that the compiler will ensure that any T that compiles does indeed have those methods. This check happens at compile-time, when the generic is monomorphized (Rust's term for what C++ would call "template instantiation").

This restriction on the target type T is explicit, encoded in the trait bounds: the trait can only be implemented by types that satisfy the trait bounds. This is in contrast to the equivalent situation in C++, where the constraints on the type T used in a template<typename T> are implicit ³: C++ template code still only compiles if all of the referenced methods are available at compile-time, but the checks are purely based on method and signature. (This "duck typing" leads to the chance of confusion; a C++ template that uses t.pop() might compile for a T type parameter of either Stack or Balloon – which is unlikely to be desired behaviour.)

The need for explicit trait bounds also means that a large fraction of generics use trait bounds. To see why this is, turn the observation around and consider what can be done with a struct Thing<T> where there no trait bounds on T. Without a trait bound, the Thing can only perform operations that apply to any type T; this allows for containers, collections and smart pointers, but not much else. Anything that uses the type T is going to need a trait bound.

pub fn dump_sorted<T>(mut collection: T)
where
    T: Sort + IntoIterator,
    T::Item: Debug,
{
    // Next line requires `T: Sort` trait bound.
    collection.sort();
    // Next line requires `T: IntoIterator` trait bound.
    for item in collection {
        // Next line requires `T::Item : Debug` trait bound
        println!("{:?}", item);
    }
}

So the advice here is to use trait bounds to express requirements on the types used in generics, but it's easy advice to follow – the compiler will force you to comply with it regardless.

A trait object is the other way of making use of the encapsulation defined by a trait, but here different possible implementations of the trait are chosen at run-time rather than compile-time. This dynamic dispatch is analogous to the use of virtual functions in C++, and under the covers Rust has 'vtable' objects that are roughly analogous to those in C++.

This dynamic aspect of trait objects also means that they always have to be handled indirectly, via a reference (&dyn Trait) or a pointer (Box<dyn Trait>). This is because the size of the object implementing the trait isn't known at compile time – it could be a giant struct or a tiny enum – so there's no way to allocate the right amount of space for a bare trait object.

A similar concern means that traits used as trait objects cannot have methods that return the Self type, because the compiled-in-advance code that uses the trait object would have no idea how big that Self might be.

A trait that has a generic method fn method<T>(t:T) allows for the possibility of an infinite number of implemented methods, for all the different types T that might exist. This is fine for a trait used as a trait bound, because the infinite set of possibly invoked generic methods becomes a finite set of actually invoked generic methods at compile time. The same is not true for a trait object: the code available at compile time has to cope with all possible Ts that might arrive at run-time.

These two restrictions – no returning Self and no generic methods – are combined into the concept of object safety. Only object safe traits can be used as trait objects.

1: At least, not in stable Rust at the time of writing. The unboxed_closures and fn_traits experimental features may change this in future.

2: For example, Effective Java Item 64: Refer to objects by their interfaces

3: The addition of concepts in C++20 allows explicit specification of constraints on template types, but the checks are still only performed when the template is instantiated, not when it is declared.