How to compare two trait objects for equality

Hello,

I have Arc<dyn Trait> objects that I'd like to compare. I can't compare them with PartialEq because it's not object safe. But I'd really like to be able to tell if two Arc<dyn Trait> are equal or not, and intuitively it feels like it should be possible:

  • if the two objects don't have the same type, not equal
  • if the two objects have the same type, compare them

For the first step I guess I could use the type ID, but I don't know whether there's a clever way to achieve the second step.

1 Like

That's because it doesn't exist. Try to imagine how machine code would look like:

  1. First step is easy - compare virtual tables for objects. Suppose they are equal.
  2. And now… what can you do at this point? You need not one continuation but dozens of them!

And the solution for the #2 is obvious: put continuation in your trait!

Why would you need object safety there? dyn Trait is a concrete type and Arc<dyn Trait> is a concrete type, too.

You can easily implement PartialEq for them by delegating actual work to that function from #2

There's a way based on double dynamic dispatch and a generic (as in parametrically-polymorphic) visitor pattern. I explained the general idea here. (DynEq is adapted from LevelOne and DynEqHelper is adapted from LevelTwo).

1 Like

What does this mean @VorfeedCanal ?

I'm not sure I made my problem very clear. Here is what I like to do more or less:

trait MyTrait: PartialEq {}

impl MyTrait for u8 {}
impl MyTrait for String {}

fn main() {
    let a = 0_u8;
    let b = 0_u8;
    let c = 1_u8;
    let d = "string".to_string();
    
    let dyn_a: Box<dyn MyTrait> = Box::new(a);
    let dyn_b: Box<dyn MyTrait> = Box::new(b);
    let dyn_c: Box<dyn MyTrait> = Box::new(c);
    let dyn_d: Box<dyn MyTrait> = Box::new(d);

    assert!(dyn_a == dyn_b);
    assert!(dyn_a != dyn_c);
    assert!(dyn_a != dyn_d);
}

But I can't create a dyn MyTrait because the PartialEq bound makes MyTrait not object safe. Object safety is not something I need or don't need. It's something that gets on my way.

@H2CO3 thanks a lot! From what I see in the playground, this is exactly what I need. But I don't really understand your explanations (I'm not familiar with the visitor pattern in the first place). Would you mind dumbing it down a little, or point me at resources that would help me understand it better?

The direct way to do this if only one side were a trait object (e.g., &dyn DynEq == T or T == &dyn DynEq for some concrete type T) would be to downcast the trait object to the concrete type, and then invoke PartialEq directly. (And if the downcast fails, return false since the types were different.) That would look like this.

The problem is that you can't directly do this if both sides are trait objects, since one can't downcast to a dynamic type, only to a concrete, static one. So this is what needs to be worked around.

The workaround is to emulate double dispatch: you want to invoke an equality comparison depending on both types. Rust doesn't directly support this, but there's an easy way to emulate it. You simply dispatch in two different stages – this corresponds to the two traits.

The first stage of dynamic dispatch happens in DynEq::level_one(). It simply invokes the dynamic (or "virtual") method DynEqHelper::level_two(self) on the right-hand side. The right-hand side then attempts to downcast the LHS to its own type, and if it succeeds, it invokes right back, calling DynEq::dyn_eq with itself as the argument. This call-me-I-call-you-back mechanism is what is usually referred to as "the visitor pattern".

Since dyn_eq is generic, at this point both types are effectively statically-known. Actually, thinking about it, the whole dyn_eq method is unnecessary, since one could just invoke == directly at this point, like this.

So basically all this does is use one vtable as a trampoline for the other one, to dispatch on both arguments dynamically. At the end of the two-step dynamic dispatch chain, both types are statically known (since both methods are implemented on concrete, static types), and so equality comparison can work by simply forwarding to the PartialEq impl of the underlying concrete type.

9 Likes

This is amazing, thanks a lot @H2CO3! For the solution and for the explanation. This is a useful pattern to know about when working with trait objects.

I made this into a little utility crate, along with a dynamically-dispatched variant of the PartialOrd trait.

3 Likes

Hello @H2CO3 :slight_smile:

I've tried to integrate your solution, but for some reason, it breaks downcasting. I've started at the code for quite some time, and I'm starting to wonder whether I'm hitting a bug. A repro can be found here: Rust Playground

As it is, the code works, but if I uncomment the PartialEq impl, the test just breaks.

Any idea? Should I open an issue on rust-lang/rust?

Definitely not. Why would you? This is not a compiler bug.

This has also nothing to do with my solution. DynEq doesn't "break downcasting". It's a simple misunderstanding on your part, and a design error.

The OpaqueData trait has an as_any() method – i.e., it has the same name as the as_any() method on DynEq. That's Bad™, because DynEq is (necessarily) blanket-impl'd for all eligible types T: PartialEq + 'static, including Arc<T: PartialEq + 'static>: PartialEq + 'static.

Now dyn_a is Arc<dyn OpaqueData>, so when you call dyn_a.as_any(), it actually resolves to <Arc<dyn OpaqueData> as DynEq>::as_any(), i.e., directly on the Arc, without dereferencing it. Of course, downcasting an Arc<A> to A is not going to work, because they are not the same type.

If, however, you omit the PartialEq impl on dyn OpaqueData, then that transitively gets rid of the PartialEq impl on Arc<dyn OpaqueData>. This means that Arc<dyn OpaqueData> no longer impls DynEq. Therefore, method resolution has to dig deeper, auto-deref, and find the correct <A as DynEq>::as_any() method, which it will call.

The correct solution(s) include:

  1. Not putting identically-named methods on super- and subtraits, and/or
  2. Explicitly dereferencing smart pointers.

I.e., this works:

let downcasted = (*dyn_a).as_any().downcast_ref::<A>().unwrap();

As for the lifetime error: &dyn Trait in a signature is implicitly &'a dyn Trait + 'a, which is not what you want – you want &'_ dyn DynEq + 'static, because you can't downcast it unless it's 'static-bounded. This error is also fixed in the linked playground, and then you can just impl PartialEq as self.as_dyn_eq() == other.as_dyn_eq().

3 Likes

Thanks for the explanation :slight_smile:

After some more experiments, I noticed that the following seems to work, but maybe I'm again missing something:

use std::any::Any;

pub trait DynEq {
    fn as_any(&self) -> &dyn Any;
    fn do_eq(&self, rhs: &dyn DynEq) -> bool;
}

impl<T> DynEq for T
where
    T: PartialEq + 'static,
{
    fn as_any(&self) -> &dyn Any {
        self
    }

    fn do_eq(&self, rhs: &dyn DynEq) -> bool {
        if let Some(lhs_concrete) = self.as_any().downcast_ref::<Self>() {
            if let Some(rhs_concrete) = rhs.as_any().downcast_ref::<Self>() {
                lhs_concrete == rhs_concrete
            } else {
                false
            }
        } else {
            false
        }
    }
}

impl PartialEq for dyn DynEq {
    fn eq(&self, rhs: &Self) -> bool {
        self.do_eq(rhs)
    }
}

The outermost cast can be removed since you are not converting anything: Playground