Workaround for Hash trait not being object-safe

Hello,

I'm trying to use HashSet to hold an arbitrary collection of different types. So I figured I'd use a boxed dyn trait object.

My thinking was that the hash function might evaluate in unevenly for different types, but it would be ok because the Eq comparison function would still make sure the right thing happens even if the performance isn't optimal.

Here's what I tried. The trouble is that bounding my trait with Hash makes it no longer object-safe. Is there a more elegant way to do this?

use std::collections::HashSet;
use std::hash::{Hash, Hasher};

trait FooTrait : Hash {}

impl Eq for Box<dyn FooTrait> {}

impl PartialEq for Box<dyn FooTrait> {
    fn eq(&self, rhs : &Self) -> bool {
        if let Some(typecast_rhs) = std::any::Any::downcast_ref::<Self>(rhs) {
            self == typecast_rhs
        } else {
            false
        }
    }
}

impl std::hash::Hash for Box<dyn FooTrait> {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        let unboxed_ref = &(*self) as &dyn FooTrait;
        unboxed_ref.hash(unboxed_ref, state)
    }
}

fn main() {
    let mut hs : HashSet<Box<dyn FooTrait>> = HashSet::new();
    hs.insert(Box::new("bob"));
    hs.insert(Box::new(42));

    assert!(hs.contains(&Box::new("bob")));
    assert!(hs.contains(&Box::new(42)));
}

Thank you!

First, you'll need to make an object-safe version of Hash:

trait DynHash {
    /// Feeds this value into the given [`Hasher`].
    fn dyn_hash(&self, state: &mut dyn Hasher);
}

You implement Hash for dyn FooTrait as follows:

impl Hash for dyn FooTrait {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher {
        self.dyn_hash(state);
    }
}

Now, you still need to implement DynHash for every type that implements Hash. I suggest taking a look at the dyn-clone crate for that, as it involves unsafe.

@Michael-F-Bryan correctly showed, that this doesn't even involve unsafe. His code adapted to my version:

impl<T> DynHash for T
where
    T: Hash {
    fn dyn_hash(&self, state: &mut dyn Hasher) {
        self.hash(state);
    }
}
4 Likes

I don't think your problem is Hash's object safety here because I get the following error message when trying to run on the playground:

error[E0119]: conflicting implementations of trait `std::hash::Hash` for type `std::boxed::Box<(dyn FooTrait + 'static)>`:
  --> src/main.rs:18:1
   |
18 | impl std::hash::Hash for Box<dyn FooTrait> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: conflicting implementation in crate `alloc`:
           - impl<T> Hash for Box<T>
             where T: Hash, T: ?Sized;

That said, if the overlapping Hash impl for Box<T> and Box<dyn FooTrait> wasn't an issue, I'd solve it by creating an internal object-safe version of Hash and implementing it for all H: Hash:

impl std::hash::Hash for Box<dyn FooTrait> {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        let unboxed_ref = &(*self) as &dyn FooTrait;
        unboxed_ref.dyn_hash(unboxed_ref, state)
    }
}

trait DynHashable {
    fn dyn_hash(&self, hasher: &mut dyn Hasher);
}

impl<H> DynHashable for H where H: Hash {
    fn dyn_hash(&self, hasher: &mut dyn Hasher) {
        self.hash(hasher);
    }
}

EDIT: It looks like @Phlopsi and I answered at the same time. You should be able to merge our two solutions by implementing Hash for dyn FooTrait by deferring to the object's dyn_hash() method.

4 Likes

Thank you both for the answers!

Here's a cleaned version that compiles (playground link):

use std::hash::{Hash, Hasher};

trait DynHash {
    fn dyn_hash(&self, state: &mut dyn Hasher);
}

impl<H: Hash + ?Sized> DynHash for H {
    fn dyn_hash(&self, mut state: &mut dyn Hasher) {
        self.hash(&mut state);
    }
}

trait FooTrait: DynHash {}

impl Hash for dyn FooTrait {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.dyn_hash(state);
    }
}

This compiles thanks to that mut state: &mut dyn Hasher inside the implementation DynHash for H. It is needed because the parameter H in Hash::hash doesn't have a ?Sized bound (although it could). However there's an impl<H: Hasher + ?Sized> Hasher for &mut H, so &mut dyn Hasher implements Hasher and is Sized, meaning I can pass an &mut &mut dyn Hasher (with &mut state) to Hash::hash and it won't complain.

Note however that while this solves the Hash problem you will still get errors due to PartialEq and Eq

4 Likes

In your PartialEq implementation, you're downcasting to Self which is a Box<dyn FooTrait>, and that's not going to give you what you want. You want to downcast to the original type that implemented FooTrait which corresponds to the &self parameter. So you're going to need to tie it back to the trait itself.

And in general, you should implement for dyn Trait and not Box<dyn Trait>. Box<dyn Trait> will pick up the former via blanket implementation.

Here's what I came up with on the playground. The approach for Hash is different than the previous replies, but could be replaced.

2 Likes

And here's my take with support for PartialEq+Eq too: playground link

I went for a modular approach, splitting the definition of the object-safe versions of the std traits from FooTrait, and providing default implementations for them using the std traits. This allows implementors of FooTrait to not having to worry about the object-safe traits, but only about its methods (for now there's none) and the std traits.

3 Likes