Generics and traits allow code reuse. A program can declare a generic item (function, enum, structure, trait) once and instantiate it with different concrete types.

Rust implements generics by monomorphization. It is efficient, as monomorphization incurs no runtime overhead. However, it doesn't allow a program to place values of different types into the same collection.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

// Doesn't compile.
let shapes: Vec<Area>;
#}

The above program wishes to place both Rectangle and Square into the same vector, but it cannot achieve this by declaring a vector of Area, even though both Rectangle and Square implement Area. The reason is that Rectangle and Square values have different sizes, so the vector doesn't know how much memory to allocate for each element. To solve this problem, the program could store pointers to these values instead of storing the values themselves. Storing pointers avoids the size dilemma because all pointers on the same CPU architecture have the same size.

Rust provides trait objects to allow access to a value via a pointer. If T implements U, casting or coercing &T to &U creates a trait object. The program can invoke any method declared in the trait on the trait object.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

let rectangle = Rectangle{ x: 0, y: 0, w: 1, h: 2 };
let square = Square{ x: 0, y: 0, w: 1 };
let mut shapes: Vec<&Area> = vec![];
shapes.push(&rectangle);
shapes.push(&square);
for shape in shapes {
    println!("{}", shape.area());
}
#}

Trait object raises a question on method resolution. When the program calls a method on a trait object, how does it determine which method to call, since every type implementing this trait provides this method?

Internally, a trait object is an opaque struct illustrated below. The struct is opaque because the program cannot access it directly, but can access it only indirectly via the trait object. The struct contains two pointers. The first pointer points to the value, and the second pointer points to a vtable (virtual dispatch table). If the trait contains n methods, then this vtable contains n entries where each entry points to a method implemented by the concrete type. Therefore, when the program invokes a method on a trait object, the code generated by the compiler follows the trait object to the vtable, finds the pointer to the method, and then calls the method.

# #![allow(unused_variables)]
#fn main() {
struct TraitObject {
    pub data: *mut (),
    pub vtable: *mut (),
}
#}

So far we have seen trait objects where the value lives on the stack. The type of such trait objects is &U where U is a trait. Alternatively, a program may also create trait objects where the value lives on the heap. The type of such trait objects is Box<U>. If T implements U, casting or coercing Box<T> to Box<U> creates a trait object.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

fn static_dispatch<T: Area>(x: &T) -> i32 {
    x.area()
}

fn dynamic_dispatch(x: &Area) -> i32 {
    x.area()
}

let rectangle = Rectangle{ x: 0, y: 0, w: 1, h: 2 };
let square = Square{ x: 0, y: 0, w: 1 };
static_dispatch(&rectangle);
static_dispatch(&square);
dynamic_dispatch(&rectangle);
// or `dynamic_dispatch(&rectangle as &Area)`
dynamic_dispatch(&square);
// or `dynamic_dispatch(&square as &Area)`
#}

Rust monomorphizes the static_dispatch function. If the program calls this function with n different instantiations of the type parameter T, Rust makes n specialized copies of this function, where in each copy Rust replaces T with a different concrete type. Therefore, each copy of static_dispatch knows which area method to call since it knows the concrete type of T at compile time. This is called static dispatch.

By contrast, since the function dynamic_dispatch takes a trait object, Rust does not monomorphize it. Therefore, since the type of T is unknown at compile time, dynamic_dispatch doesn't know which area method to call at compile time. At runtime, dynamic_dispatch follows the trait object x to its vtable to look up the address of the method area. This is called dynamic dispatch.

Static dispatch is efficient, since the compiler generates a direct call to the method. However, it suffers from code bloat, since the compiler generates multiple copies of the same code. Code bloat may make the program run slow because it may reduce the hit rate of the code cache.

Dynamic dispatch does not suffer from code bloat, since the compiler generates only one copy of the function. However, it reduces performance because the compiler generates indirect calls. Specifically, the compiler generates two extra dereference instructions per dynamic dispatch:

1. Dereferencing the pointer to the vtable
2. Dereferencing the pointer to the method