Transform static dispatch code into dynamic dispatch

Question

In Chapter 10 of the rust lang book there is a an example of static dispatch that looks like so:

fn largest<T: PartialOrd + Copy>(list: &[T]) -> T {
    let mut largest = list[0];
    for &i in list {
        if i > largest {
            largest = i;
        }
    }
    largest
}

I'm trying to re-implement the same example using dynamic dispatch, as described in chapter 17. My best attempt so far:

fn largest_dyn(list: &[Box<dyn PartialOrd<i32>>]) -> Box<dyn PartialOrd<i32>> {
    let mut largest = &list[0];
    for &i in list {
        if *i > **largest {
            **largest = *i;
        }
    }
    **largest
}

But this doesn't compile. The error I get is:

expected `i32`, found trait object `dyn PartialOrd`

I have a bunch of questions I was hoping someone could help with:

1. Why does the above not compile? It seems that I'm dereferencing left and right sides the same number of times, yet one is an i32 but another one is a dyn trait object?
2. The compiler forced me to put <i32> after dyn PartialOrd to even get this far. I don't get it - wasn't the purpose of trait objects specifically that they didn't require you to specify a type, and only a trait? Why am I forced to put a type here?
3. The original function actually implements two traits: PartialOrd and Copy. I couldn't find a way to do that with Box<> - Box<dyn PartialOrd + dyn Copy> doesn't seem to work. Is there a way to have a trait object for multiple traits at once?

Answer 1

1. Why does the above not compile? It seems that I'm dereferencing left and right sides the same number of times, yet one is an i32 but another one is a dyn trait object?

Both sides dereference (at most) to a trait object, and both those trait objects implement PartialOrd<i32> through which they can each be compared with values of type i32. The comparison tries to use the left-hand operand's implementation of PartialOrd; the reason it does not compile is because the right-hand operand is not a value of type i32, it's a trait object!

If you think about this, it makes perfect sense. You have two trait objects, each of which comprises two pointers: one to an object (whose type Rust does not know) and another to that object's vtable for the PartialOrd trait in order that Rust can invoke that trait's methods for the object. PartialOrd provides a partial_cmp method through which the object can be compared with a value... but if you only have a pointer to an object of unknown type and a pointer to another vtable, how could the comparison be implemented?

2. The compiler forced me to put <i32> after dyn PartialOrd to even get this far. I don't get it - wasn't the purpose of trait objects specifically that they didn't require you to specify a type, and only a trait? Why am I forced to put a type here?

To make a trait object, every instance of that trait object must have exactly the same shape of vtable: hence any type parameters or associated types must be the same for all objects, and the compiler enforces this by requiring those types to be explicitly provided in the trait object's type.

Of course, many traits do not have type parameters or associated types—and they can still very usefully be made into trait objects (subject to the usual rules over object safety). But even where a trait does have such types, we can generify over them (so that Rust creates a different type of trait object for each combination of types with which the generic parameters are instantiated); for example:

fn foo<T>(list: &[Box<dyn SomeTrait<T>>])

3. The original function actually implements two traits: PartialOrd and Copy. I couldn't find a way to do that with Box<> - Box<dyn PartialOrd + dyn Copy> doesn't seem to work. Is there a way to have a trait object for multiple traits at once?

You can only have one non-auto trait, but you can specify additional auto traits (such as Send and Sync): Box<dyn PartialOrd<T> + Send + Sync>. In this case, both PartialOrd and Copy are non-auto traits, hence trait objects cannot be created over both.

Answer 2

eggyal's answer explains why you are running into problems with PartialOrd. However, the fact that some trait from the standard library is not conducive to use in trait objects doesn't mean that you can't use trait objects. You'll just need to create a trait better taylored to your needs, and Rust in fact makes it quite easy to define your own traits.

For example, to compare arbitrary values as numbers, it might be easier to provide a way to extract a number from the value. (This is often used in sorting APIs that accept a "key function" to the sort, in addition to or instead of a "comparison function".) Such a trait would look like this:

trait AsInt {
    fn as_int(&self) -> i32;
}

We can trivially implement it for i32 itself:

impl AsInt for i32 {
    fn as_int(&self) -> i32 {
        *self
    }
}

largest_dyn would now look like this:

// XXX doesn't compile
fn largest_dyn(list: &[Box<dyn AsInt>]) -> Box<dyn AsInt> {
    let mut largest = list[0];
    for i in list {
        if i.as_int() > largest.as_int() {
            largest = i;
        }
    }
    largest
}

The problem with this implementation is that it tries to extract values from a slice consisting of Box<dyn ...>. The original implementation required T: Copy, so it could do that, but Box<T> can't be Copy regardless of T, so we need to clone the value in the list. For technical reasons, cloning a trait object is not as easy as requesting a Clone bound - instead, we must provide the clone ability by extending the trait with a separate method:

trait AsInt {
    fn as_int(&self) -> i32;
    fn box_clone(&self) -> Box<dyn AsInt>;
}

impl AsInt for i32 {
    fn as_int(&self) -> i32 {
        *self
    }

    fn box_clone(&self) -> Box<dyn AsInt> {
        Box::new(*self)
    }
}

With this in place, largest_dyn() can be fully dynamic:

fn largest_dyn(list: &[Box<dyn AsInt>]) -> Box<dyn AsInt> {
    let mut largest = list[0].box_clone();
    for i in list {
        if i.as_int() > largest.as_int() {
            largest = i.box_clone();
        }
    }
    largest
}

Playground