Now that we've gotten down the utilities needed to continue with our event handling scheme, it seems like the next thing we need to do is continue working on the event handling scheme. But we can't do that because one more thing is missing from our toolbox.

We stopped at this point:

pub struct EventHooker {
    // The functions that will be called when an event occurs
    handlers: Vec<Box<dyn FnMut(EventInfo)>>
}

We created a Vec, so we may be able to create a vector of trait objects. But there is just one more problem that we need to attend to before we can create boxes of closures. Creating trait objects with boxes using Box<dyn ...> requires special support from the compiler, using specifically the Box provided by alloc or std. But we are using a custom Box. This implies that we need to figure out how to create the trait objects ourselves. To do this, we must first ask ourselves: What exactly is a trait object?

Trait Objects

Consider the following:

trait Animal {
    fn make_sound(&self);
}

struct Cat;

impl Animal for Cat {
    fn make_sound(&self) {
        println!("Meow!");
    }
}

struct Dog;

impl Animal for Dog {
    fn make_sound(&self) {
        println!("Roof!");
    }
}

In the above code snippet, we have two structs, Cat and Dog, that implement a single trait: Animal. Now, if we were to create a function that takes anything implementing Animal, and invokes make_sound we have two options. One is to do this:

fn statically_dispatched_function<T>(animal: T) where T: Animal {
    animal.make_sound();
}

When the compiler sees this function, it will interpret it like this:

1. statically_dispatched_function takes any type which implements Animal.
2. I should create multiple copies of this function, each of which takes a concrete type. For example, if at some point in the code, this function is called with a Cat type and at some other point, a Dog type, then

fn statically_dispatched_function<T>(animal: T) where T: Animal {
    animal.make_sound();
}

will become

fn statically_dispatched_function(animal: Cat) {
    animal.make_sound();
}

fn statically_dispatched_function(animal: Dog) {
    animal.make_sound();
}

This way, the address of the appropriate make_sound function to call will be known at compile-time. That's why it's called static dispatch. The address resolution of the right make_sound function is resolved statically at compile-time.

The other option:

fn dynamically_dispatched_function(animal: &dyn Animal) {
    animal.make_sound();
}

Upon an encounter with this function, the compiler will interpret it like this:

dynamically_dispatched_function takes a reference to another structure that will give me information about how to call the make_sound implementation of any Animal implementer passed into this function. Therefore, I won't bother figuring out where the implementations are now. I'll just generate code that will look up the right make_sound implementation in that structure at runtime when it's time to execute the code.

This way, the address of the appropriate make_sound function to call will be determined, not at compile-time, but at runtime. That's why it's called dynamic dispatch, because the address of the correct implementation to call is resolved dynamically.

The structure that is actually passed as an argument into the function dynamically_dispatched_function is not the Dog or Cat instance, but instead, it's something that looks like this:

struct TraitObjectishStructure {
    // Pointer to the actual instance of the structure implementing the trait 
    data: *mut (),
    // Pointer to the trait function implementations (in this case, `make_sound`)
    // It's this pointer that is followed to get the right `make_sound` implementation
    vtable: *mut ()
}

The data field is a pointer to the actual value that implements the trait, which in this case is Animal. The vtable field is a pointer to yet another structure called the virtual method table. It is this structure that holds the function pointers for all the trait implementations. A hypothetical one may look like this:

struct VTable {
    drop: /* function pointer to drop implementation */,
    make_sound: fn(*const ())
}

An actual virtual method table will probably have a bunch of other useful info stuffed in it.

To solidify knowledge, consider this piece of code and determine what the generated code will execute when statically_dispatched_function and dynamically_dispatched_function are carried out. Make sure you do this yourself before reading on.

fn main() {
    let dog = Dog;
    let cat = Cat;
    statically_dispatched_function(dog);
    dynamically_dispatched_function(&cat);
}

When statically_dispatched_function is called, it will just be like calling a regular function because a copy has been made specifically for calling with a Dog instance as the argument. The compiler already knew where the make_sound implementation will be. When animal.make_sound() is reached, the Dog's make_sound implementation, already known at compile-time, is immediately called, like any other regular function.

When dynamically_dispatched_function is called, an instance of a structure like TraitObjectishStructure will be passed as an argument. Executing animal.make_sound() in the function will then be equivalent to:

let data = animal_trait_object.data;
let vtable = animal_trait_object.vtable;
let make_sound_implementation = (*vtable).make_sound;
make_sound_implementation(data);

And voila! We have dynamic dispatch. Now you know (if you didn't know before) why trait objects are always said to be less efficient than generics. Using generics, executing animal.make_sound() in statically_dispatched_function is the same thing as calling a regular function. But the same in dynamically_dispatched_function resulted in chasing pointers to find the right implementation.

With this info, come up with an implementation of trait objects for boxed functions using our custom Box.

Take Away

• A virtual method table is a structure that holds pointers to trait function implementations.
• A trait object is a structure that tells the location of a virtual method table and the location of the instance of the type that implemented that trait.

In The Next Post

We'll implement trait objects for boxed functions using our custom Box.

References

• Trait Objects: https://brson.github.io/rust-anthology/1/all-about-trait-objects.html
• Trait Objects: https://doc.rust-lang.org/book/ch17-02-trait-objects.html
• Virtual Method Table: https://en.wikipedia.org/wiki/Virtual_method_table