How can I create hashable trait objects / trait objects with generic method parameters?

Question

I have some structs that implement both Hash and MyTrait. I'm using them as &dyn MyTrait trait objects.

Now I want &dyn MyTrait to also implement Hash. I've tried a few things:

• Naively, trait MyTrait: Hash {}:

  the trait `MyTrait` cannot be made into an object
  

• Then I tried this:

  impl Hash for dyn MyTrait {
      fn hash<H: Hasher>(&self, hasher: &mut H) {
          // ...
      }
  }
  

  but I need to delegate to the hash method of the concrete type of self, I think.

• So the naive next step is to put this on MyTrait:

  fn my_hash<H: Hasher>(&self, hasher: &mut H);
  

  which brings me right back to the first point.

• I read something about using a trait object instead of generic parameter, which sounds smart, so I put this on MyTrait

  fn my_hash(&self, hasher: &mut H);
  

  Then I need to actually implement this. Preferably not by hand for every trait:

  impl<T: 'static + Hash> MyTrait for T {
      fn as_any(&self) -> &dyn Any {
          self as &dyn Any
      }
  
      fn my_hash(&self, hasher: &mut Hasher) {
          self.as_any().downcast_ref::<T>().unwrap().hash(hasher)
      }
  }
  

  but then

  the trait bound `std::hash::Hasher: std::marker::Sized` is not satisfied
  `std::hash::Hasher` does not have a constant size known at compile-time
  

  So I'd have to downcast Hasher…

• If downcasting Hasher is the way, I need a generic parameter H that can convert to an Any Hasher, Let's try:

  trait AnyHasher {
      fn as_any(&self) -> &dyn Any;
  }
  
  impl<H: 'static + Hasher> AnyHasher for H {
      fn as_any(&self) -> &dyn Any {
          self as &dyn Any
      }
  }
  

  and then to downcast

  impl<T: 'static + Hash, H: 'static + Hasher> MyTrait for T {
      // ...
      fn my_hash(&self, hasher: &mut AnyHasher) {
          let h = hasher.as_any().downcast_ref::<H>().unwrap();
          self.as_any().downcast_ref::<T>().unwrap().hash(h)
      }
  }
  

  but alas

  the type parameter `H` is not constrained by the impl trait, self type, or predicates
  

  which I guess is true, but then I'm stuck. (Also it seems kind of ridiculous so far).

Can this can be done? If so, how?

I previously asked about PartialEq for trait objects, which was hard because information the concrete type of the trait object is needed. That was solved with downcasting, but I didn't manage to apply that solution here.

Answer 1

You can put the desired functionalities in your trait, i.e. you mix your second and third attempts:

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

#[derive(Hash)]
struct Foo(i32);

#[derive(Hash)]
struct Bar(String);

// Put the desired functionalities in your trait

trait MyTrait {
    fn my_hash(&self, h: &mut dyn Hasher);
    fn my_eq(&self, other: &dyn MyTrait) -> bool {
        let mut hasher1 = DefaultHasher::new();
        let mut hasher2 = DefaultHasher::new();

        self.my_hash(&mut hasher1);
        other.my_hash(&mut hasher2);
        hasher1.finish() == hasher2.finish()
    }

    // other funcs
}

impl MyTrait for Foo {
    fn my_hash(&self, mut h: &mut dyn Hasher) {
        self.hash(&mut h);
    }
}

impl MyTrait for Bar {
    fn my_hash(&self, mut h: &mut dyn Hasher) {
        self.hash(&mut h);
    }
}

// Implement needed traits for your trait

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

impl PartialEq for dyn MyTrait {
    fn eq(&self, other: &dyn MyTrait) -> bool {
        self.my_eq(other)
    }
}

impl Eq for dyn MyTrait {}

// This compiles

fn main() {
    let foo = Foo(42);
    let bar = Bar("answer".into());
    let mut set = HashSet::new();

    set.insert(&foo as &dyn MyTrait);
    set.insert(&bar);
}

In my opinion, this is not a good thing to implement Hash for a trait in your way, because you do not know what is the concrete type beside the trait. Someone could implement the trait for both the same type, like:

struct Foo(String);
struct Bar(String);

In this case, how do you want to handle Foo("hello") vs Bar("hello")? Are they the same item? Because they will have the same hash.

The real question, in your case, is: how do you define what is same or not from a trait? In my opinion, a better way to handle this is to calculate the hash from "business" trait methods, for example:

#[derive(Hash)]
struct Baz(...); // Business item
#[derive(Hash)]
struct Qux(...); // Another business item

trait MyTrait {
    // all those returned items make my MyTrait unique
    fn description(&self) -> &str;
    fn get_baz(&self) -> Baz;
    fn get_qux(&self) -> Qux;
}

impl Hash for dyn MyTrait {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.description().hash(hasher);
        self.get_baz().hash(hasher);
        self.get_qux().hash(hasher);
    }
}

A trait is only a contract or a partial consideration of a thing (just like when you say that a "human being" is a "developer"). You should not (in my humble opinion) consider a trait as a concrete type.

Answer 2

I'm not a Rust expert, but it seems to me that you try to turn Rust into Java (don't be offended: I really do like Java).

How can I create hashable trait objects?

You don't want to create a hashtable of trait objects (it's easy), you want to create a hashtable of traits that are not trait objects and that's why you encounter difficulties.

The problem

I summarize: you have some various structs that implement traits MyTrait, Hash and Eq, and you would like to put those mixed structs into a single a hashtable as a TunedMyTrait trait objects. This requires TunedMyTrait to be a subtrait of Hash and Eq. But whereas MyTrait can be made a trait object, TunedMyTrait cannot.

I'm sure you know why, but I will try to make it clear for other readers, using this valuable resource. (I put it in my own words, don't be shy and edit it if you think that isn't clear.) Trait objects rely on something that is called "object safety" (see the RFC 255). "Object safety" means: all methods of the trait must be object-safe.

Rust makes an intensive usage of the stack, thus it has to know the size of everything it can. After the borrow checker, that's one of the difficulties and the beauties of Rust. A trait object is typed and sized: it is some kind of "fat" pointer that contains information on the concrete type. Every method call is delegated to the concrete type, using a vtable of methods. I don't get into details, but some issues may occur with this delegation and the "safety check" was created to avoid those issues. Here:

• the method fn eq(&self, other: &Rhs) -> bool where Rhs = Self is not object safe, because at runtime, Rhs was erased, and thus the concrete type and the size of other is not known.
• the method fn hash<H: Hasher>(&self, hasher: &mut H) is not object safe, because the vtable is not built for every concrete type H.

The solution

Okay. MyTrait is a trait object, but TunedMyTrait is not. Yet only TunedMyTrait objects may be valid keys for your hashtable. What can you do?

You can try, as you did, to hack the object safety mechanism. You found a solution to hack PartialEq (with a cast try, How to test for equality between trait objects?), and you have now another hack from @Boiethios (which basically makes of hash a non generic function). If you finally reach your goal, I can imagine the future reader of the code: "OMG, what is this guy trying to do?" or (worse): "I'm not sure of what it does, but I'm pretty sure it would run faster if...". You have hacked a protection of the language and your code is likely to create issues worse than the problem you are trying to solve. This reminds me this kind of discussion: Get generic type of class at runtime. And then? What will you do with this piece of code?

Or you can be reasonable. There are some possibilities: you use a hashtable with keys that are really of the same concrete type, you box your MyTrait objects, you use an enum... There may be other ways (as said, I'm not a Rust expert).

Don't get me wrong: hacking a language is really fun and helps to understand deeply its mechanics and limits (note: if you hadn't asked that question, I wouldn't have had a close look at DST and trait objects, thus I thank you). But you have to be serious if you intend to do something serious: Rust is not Java...

EDIT

I want to compare and hash objects that are runtime-polymorphic.

That's not difficult, but you also want to put them in a HashMap, and that is the problem.

I will give you another insight. Basically, you know that a hashtable is an array of buckets. Rust uses open addressing to resolve hash collisions (specifically: Robin Hood hashing), that means that every bucket will contain 0 or 1 pair (key, value). When you put a pair (key, value) in an empty bucket, the tuple (key, value) is written in the buffer array, at the position pair_start + index * sizeof::<K, V>(), according to the definition of offset. It's obvious that you need sized pairs.

If you could use trait object, you would have fat pointer, which is sized. But that's not possible for the reasons already stated. All the ideas I proposed are focused on this: have sized keys (assuming that values are already sized). Concrete type: obviously sized. Boxing: size of a pointer. Enum: size of the biggest element + size of the tag + padding.

Basic example with boxing

WARNING: I tried hard to find an example on the internet, but didn't find anything. So I decided to create from scratch a basic example with boxing, but I'm not sure this is the right way to do it. Please comment or edit if needed.

First, add to your trait a method that identifies every instance of any concrete type that implements MyTrait with a comparable and hashable value, let's say an id method that returns an i64:

trait MyTrait {
    fn id(&self) -> i64; // any comparable and hashable type works instead of i64
}

Foo and Bar concrete types will implement this method (the implementation given here is totally stupid):

struct Foo(u32);

impl MyTrait for Foo {
    fn id(&self) -> i64 {
        -(self.0 as i64)-1 // negative to avoid collisions with Bar
    }
}

struct Bar(String);

impl MyTrait for Bar {
    fn id(&self) -> i64 {
        self.0.len() as i64 // positive to avoid collisions with Foo
    }
}

Now, we have to implement Hash and Eq, in order to put dyn MyTrait in a HashMap. But if we do it for dyn MyTrait, we get a trait that can't be a trait object, because dyn MyTrait is not sized. Let's implement it for Box<dyn Trait>, which is sized:

impl Hash for Box<dyn MyTrait> {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.id().hash(state)
    }
}

impl PartialEq for Box<dyn MyTrait> {
    fn eq(&self, other: &Box<dyn MyTrait>) -> bool {
        self.id() == other.id()
    }
}

impl Eq for Box<dyn MyTrait> {}

We used the id method to implement eq and hash.

Now, think of Box<dyn MyTrait>: 1. it is sized; 2. it implements Hash and Eq. That means that it can be used as a key for a HashMap:

fn main() {
    let foo = Foo(42);
    let bar = Bar("answer".into());
    let mut my_map = HashMap::<Box<dyn MyTrait>, i32>::new();
    my_map.insert(Box::new(foo), 1);
    my_map.insert(Box::new(bar), 2);

    println!("{:?}", my_map.get(&(Box::new(Foo(42)) as Box<dyn MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Foo(41)) as Box<dyn MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("answer".into())) as Box<dyn MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("question".into())) as Box<dyn MyTrait>)));
}

Output:

Some(1)
None
Some(2)
None

try it: https://play.integer32.com/?gist=85edc6a92dd50bfacf2775c24359cd38&version=stable

I'm not sure it solves your problem, but I don't really know what you are trying to do...