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 &MyTrait trait objects.

Now I want &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 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) -> &Any {
          self as &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) -> &Any;
  }
  
  impl<H: 'static + Hasher> AnyHasher for H {
      fn as_any(&self) -> &Any {
          self as &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

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 hashstable 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 possiblities: 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 adressing 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 MyTrait in a HashMap. But if we do it for MyTrait, we get a trait that can't be a trait object, because MyTrait is not sized. Let's implement it for Box<Trait>, which is sized:

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

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

impl Eq for Box<MyTrait> {}

We used the id method to implement eq and hash.

Now, think of Box<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<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<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Foo(41)) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("answer".into())) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("question".into())) as Box<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...