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...