Polymorphism with Traits and Bounds

[nee]

I'm trying to create a map where the keys are trait objects.

structs which impl the trait have all derived Ord, Eq etc. In my case, this is simple as the internal fields are all integers and strings.

My attempt so far has been to define a trait as below, but the compiler says that Ord is not satisfied.

I'm not sure how to tell the compiler that the concrete structs which I intend to add to the map always do satisfy Ord bounds.

use std::collections::BTreeMap;

trait EntityAPI {}

#[derive(Hash, Eq, PartialEq, Debug, Ord, PartialOrd)]
struct Entity1 {
    id: u8,
    name: String,
}

impl EntityAPI for Entity1 {}

#[derive(Hash, Eq, PartialEq, Debug, Ord, PartialOrd)]
struct Entity2 {
    id: u8,
    name: String,
}

impl EntityAPI for Entity2 {}

pub fn main() {
    let e1 = Entity1{id: 1, name: String::from("e1")};
    let e2 = Entity2{id: 2, name: String::from("e2")};
    let mut map: BTreeMap<Box<dyn EntityAPI>, f64> = BTreeMap::new();
    map.insert(e1, 11.0);
    map.insert(e2, 22.0);
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0599]: no method named `insert` found for type `std::collections::BTreeMap<std::boxed::Box<dyn EntityAPI>, f64>` in the current scope
  --> src/main.rs:25:9
   |
25 |     map.insert(e1, 11.0);
   |         ^^^^^^ method not found in `std::collections::BTreeMap<std::boxed::Box<dyn EntityAPI>, f64>`
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `std::boxed::Box<dyn EntityAPI> : std::cmp::Ord`

error[E0277]: the trait bound `dyn EntityAPI: std::cmp::Ord` is not satisfied
  --> src/main.rs:24:54
   |
24 |     let mut map: BTreeMap<Box<dyn EntityAPI>, f64> = BTreeMap::new();
   |                                                      ^^^^^^^^^^^^^ the trait `std::cmp::Ord` is not implemented for `dyn EntityAPI`
   |
   = note: required because of the requirements on the impl of `std::cmp::Ord` for `std::boxed::Box<dyn EntityAPI>`
   = note: required by `std::collections::BTreeMap::<K, V>::new`

error[E0599]: no method named `insert` found for type `std::collections::BTreeMap<std::boxed::Box<dyn EntityAPI>, f64>` in the current scope
  --> src/main.rs:26:9
   |
26 |     map.insert(e2, 22.0);
   |         ^^^^^^ method not found in `std::collections::BTreeMap<std::boxed::Box<dyn EntityAPI>, f64>`
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `std::boxed::Box<dyn EntityAPI> : std::cmp::Ord`

error: aborting due to 3 previous errors

Some errors have detailed explanations: E0277, E0599.
For more information about an error, try `rustc --explain E0277`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.

[najamelan]

You would have to specify that your trait can only be implemented for types that also implement eg. Ord:

trait EntityAPI: Ord {}

However, Ord is not object safe, so I don't think this will enable your use case.

Can you not use a generic type instead of a trait object as your map keys?

[nee]

I do need a collection of diverse types, so I cannot use a generic type. The only other option I can think is to use an enum, since I do know the types of objects. I would like to avoid this design, as it is not easily extensible.

Interestingly, I looked at the example from the chapter in the rust book on trait objects, which uses a vector. I don't know howto extend this to my example with a map.

[alice]

You can introduce a trait called MyOrd that only provides the cmp method also seen on the Ord trait (but not e.g. min which is what causes the problem). Then introduce a blanket impl that automatically implements MyOrd on anything that implements Ord.

You can now require that EntityAPI types implement MyOrd with

trait EntityAPI: MyOrd {}

Finally you can create a wrapper type around Box<dyn EntityAPI> and implement Ord for the wrapper type using the cmp method found on MyOrd.

[alice]

Oh wait I realize this doesn't work at all. If type A implements EntityApi and Ord, you can compare values of type A, but if there's another type B with the same impls, that doesn't mean you can compare a value of type A with one of type B.

Thus what you want is not possible unless you can find a way of comparing values of different underlying type.

[H2CO3]

Following that train of thought, one could just expose the list of internal fields as a uniform sequence of some sort, and provide a well-defined ordering (e.g. lexicographic) over that sequence.

If we are OK with assuming a closed set of all primitive-ish types (keeping in line with OP's example of u8 and String), it could look like this: playground

Using a non-allocating bounded collection (e.g. a small vector) instead of Vec and the creation of a #[derive(Fields)] macro for reducing boilerplate is left as an exercise to the reader.

[alice]

You can also just add a comparison key method:

trait EntityApi {
    fn cmp_key(&self) -> &str;
}

playground

Note that you still need the wrapper type around the box. Please see the playground for an example.