[solved] Error Using Trait Objects in Maps

Consider the following code:

use std::collections::btree_map::BTreeMap;

trait KeyTrait { }
trait ValueTrait { }

type WorkingMap = BTreeMap<&'static str, &'static str>;
type BrokenMap<'a> = BTreeMap<&'a KeyTrait, &'a ValueTrait>;

#[test]
fn it_works() {
    let mut testMap = WorkingMap::new();
}

#[test]
fn it_doesnt_work() {
    let mut testMap = BrokenMap::new();
}

When I run the second test, I am met with the following error:

src\lib.rs:28:23: 28:37 error: `type collections::btree::map::BTreeMap<&KeyTrait, &ValueTrait>` does not implement any method in scope named `new`
src\lib.rs:28     let mut testMap = BrokenMap::new();

I am assuming that this is happening because Rust doesn't know whether the KeyTrait object, key, implements Ord or not in the second test. Is it possible, somehow, to indicate that this constraint is satisfied?

The current solution that I am using is that I have KeyTrait provide a method which returns an object that is Ord. Then BTreeMap uses the returned objects as keys. I feel that a cleaner approach than this should exist. Let me know if you have any ideas.

The main problem here is that &KeyTrait doesn't implement Ord. Implementing Ord on KeyStruct isn't sufficient because you need to be able to compare all &KeyTrait's with each other (and you can't just tell rust that KeyStruct implements Ord because it doesn't).

The following compiles:

use std::collections::btree_map::BTreeMap;
use std::cmp::Ordering;

trait KeyTrait { }
trait ValueTrait { }

impl<'a> PartialOrd<&'a KeyTrait> for &'a KeyTrait {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(Ordering::Equal)
    }
}

impl<'a> PartialEq<&'a KeyTrait> for &'a KeyTrait {
    fn eq(&self, other: &Self) -> bool {
        true
    }
}

impl<'a> Ord for &'a KeyTrait {
    fn cmp(&self, other: &Self) -> Ordering {
        Ordering::Equal
    }
}

impl<'a> Eq for &'a KeyTrait { }

struct KeyStruct;
struct ValueStruct;

impl KeyTrait for KeyStruct {}
impl ValueTrait for ValueStruct {}

type WorkingMap = BTreeMap<&'static str, &'static str>;

#[test]
fn it_works() {
    let mut testMap = WorkingMap::new();
    let key = "Hello";
    let value = "World";

    testMap.insert(key, value);
}

#[test]
fn it_doesnt_work() {
    let key = KeyStruct;
    let value = ValueStruct;

    {
        let mut testMap = BTreeMap::<&KeyTrait, &ValueTrait>::new();

        testMap.insert(&key, &value);
    }
}
1 Like

Hello,

Thank you for the quick response! I had a look at your solution (which worked) but I followed up by adding a line of code to get the value, and still get errors:

#[test]
fn it_doesnt_work() {
    let key = KeyStruct;
    let value = ValueStruct;

    {
        let mut testMap = BrokenMap::new();
        testMap.insert(&key, &value);
        let result = testMap.get(&key);
    }
}

Interestingly, the error that I am getting is:

error: the trait `collections::borrow::Borrow<KeyStruct>` is not implemented for the type `&KeyTrait` [E0277]
        let result = testMap.get(&key);

error: the trait `core::cmp::Ord` is not implemented for the type `KeyStruct` [E0277]
        let result = testMap.get(&key);

With the following modification:

#[test]
fn it_doesnt_work() {
    let key = KeyStruct;
    let value = ValueStruct;

    {
        let mut testMap = BrokenMap::new();
        testMap.insert(&key, &value);
        let result = testMap.get(&key as &KeyTrait);
    }
}

I get another interesting error:

error: the trait `core::cmp::Ord` is not implemented for the type `KeyTrait` [E0277]
        let result = testMap.get(&key as &KeyTrait);

Any suggestions?

Actually, a better solution is to impl directly on the traits (traits are unsized types):

use std::collections::btree_map::BTreeMap;
use std::cmp::Ordering;

trait KeyTrait { }
trait ValueTrait { }

impl<'a> PartialOrd<KeyTrait + 'a> for KeyTrait + 'a {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(Ordering::Equal)
    }
}

impl<'a> PartialEq<KeyTrait + 'a> for KeyTrait + 'a {
    fn eq(&self, other: &Self) -> bool {
        true
    }
}

impl<'a> Ord for KeyTrait + 'a {
    fn cmp(&self, other: &Self) -> Ordering {
        Ordering::Equal
    }
}

impl<'a> Eq for KeyTrait + 'a { }

struct KeyStruct;
struct ValueStruct;

impl KeyTrait for KeyStruct {}
impl ValueTrait for ValueStruct {}

type WorkingMap = BTreeMap<&'static str, &'static str>;

#[test]
fn it_works() {
    let mut testMap = WorkingMap::new();
    let key = "Hello";
    let value = "World";

    testMap.insert(key, value);
}

#[test]
fn it_doesnt_work() {
    let key = KeyStruct;
    let value = ValueStruct;

    {
        let mut testMap = BTreeMap::<&KeyTrait, &ValueTrait>::new();

        testMap.insert(&key, &value);
        let k: &KeyTrait = &key;
        let result = testMap.get(k);
    }
}

Note: To answer your actual question, you would need to borrow again because I implemented Ord on &KeyTrait:

        let result = testMap.get(&(&key as &KeyTrait));

And yes, those explicit lifetimes are extremely important.

1 Like

Very interesting and informative. Thank you so much for your help with this!

What does this actually do? Is there a good document on why I would need to do this?

https://doc.rust-lang.org/book/lifetimes.html