Conflicting implementations of trait when rewriting with associated type

Question

In the below code, I define a struct called Wrap (local type) for wrapping a value and a trait called WrapOut (local trait) for extracting the value. I use the Wrap on both key and value of the HashMap (foreign type). This version of the code works as intended

use std::collections::HashMap;

struct Wrap<T> {
    val: T
}

trait WrapOut<T> {
    fn wrap_out(self) -> T;
}

impl<T, U> WrapOut<HashMap<T, U>> for HashMap<Wrap<T>, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash
{
    fn wrap_out(self) -> HashMap<T, U> {
        println!("both");
        self.into_iter().map(|(k, v)| (k.val, v.val)).collect()
    }
    
}

impl<T, U> WrapOut<HashMap<T, U>> for HashMap<T, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash
{
    fn wrap_out(self) -> HashMap<T, U> {
        println!("only val");
        self.into_iter().map(|(k, v)| (k, v.val)).collect()
    }
    
}


impl<T, U> WrapOut<HashMap<T, U>> for HashMap<Wrap<T>, U> 
where T: std::cmp::Eq + std::hash::Hash
{
    fn wrap_out(self) -> HashMap<T, U> {
        println!("only key");
        self.into_iter().map(|(k, v)| (k.val, v)).collect()
    }
    
}

fn main() {
    let m1 = HashMap::<Wrap<u32>, Wrap<u32>>::new();
    let m2 = HashMap::<u32, Wrap<u32>>::new();
    let m3 = HashMap::<Wrap<u32>, u32>::new();

    let m1: HashMap<u32, u32> = m1.wrap_out();
    let m2: HashMap<u32, u32> = m2.wrap_out();
    let m3: HashMap<u32, u32> = m3.wrap_out();
}

A conflicting implementation error occurs when I rewrote WrapOut by changing the generic type parameter to an associated type. I'm wondering why impl<T, U> WrapOut for HashMap<Wrap<T>, U> reports a conflict but impl<T, U> WrapOut for HashMap<T, Wrap<U>> does not.

trait WrapOut {
    type Target;
    fn wrap_out(self) -> Self::Target;
}

impl<T, U> WrapOut for HashMap<Wrap<T>, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash
{
    type Target = HashMap<T, U>;
    fn wrap_out(self) -> HashMap<T, U> {
        println!("both");
        self.into_iter().map(|(k, v)| (k.val, v.val)).collect()
    }
    
}

impl<T, U> WrapOut for HashMap<T, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash
{
    type Target = HashMap<T, U>;
    fn wrap_out(self) -> HashMap<T, U> {
        println!("only val");
        self.into_iter().map(|(k, v)| (k, v.val)).collect()
    }
    
}

// Occurs Error!
impl<T, U> WrapOut for HashMap<Wrap<T>, U> 
where T: std::cmp::Eq + std::hash::Hash
{
    type Target = HashMap<T, U>;
    fn wrap_out(self) -> HashMap<T, U> {
        println!("only key");
        self.into_iter().map(|(k, v)| (k.val, v)).collect()
    }
    
}

Error message:

   |
51 | impl<T, U> WrapOut for HashMap<Wrap<T>, Wrap<U>> 
   | ------------------------------------------------ first implementation here
...
75 | impl<T, U> WrapOut for HashMap<Wrap<T>, U> 
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `HashMap<Wrap<_>, Wrap<_>>`

Rust Playground

Expect you can explain why the associated type version of code does not work and the reason behind? Which versions of code is better?

Answer 1

The reason the first WrapOut impl doesn't conflict is a little subtle:

impl<T, U> WrapOut for HashMap<Wrap<T>, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash ...

impl<T, U> WrapOut for HashMap<Wrap<T>, U> 
where T: std::cmp::Eq + std::hash::Hash ...

These two conflict, because Wrap<U> is a subset of U. U is any type at all, Wrap<U> is a type, so they conflict. Given a Wrap<U>, Rust couldn't pick one implementation over the other, they're both valid.

impl<T, U> WrapOut for HashMap<Wrap<T>, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash ...

impl<T, U> WrapOut for HashMap<T, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash ...

These two, on the other hand, don't conflict because T is constrained on Eq + Hash. Wrap<T> doesn't implement Eq + Hash so Rust can differentiate the two impls. Were you to #[derive(Eq, Hash)] on Wrap, the impls would conflict.

It's not quite clear yet how this is different from the generic version, though. After all, the same argument could be applied to this:

impl<T, U> WrapOut<HashMap<T, U>> for HashMap<Wrap<T>, Wrap<U>> 
where T: std::cmp::Eq + std::hash::Hash ...

impl<T, U> WrapOut<HashMap<T, U>> for HashMap<Wrap<T>, U> 
where T: std::cmp::Eq + std::hash::Hash ...

U is any type at all, Wrap<U> is a type, so they should conflict, no? But for there to be a conflict, the more general impl (the second one) would have to include the first one. Let's fix T and U to be concrete types A and B and try to create a conflict. The first blanket impl gives us this when we plug in A and B for T and U:

impl WrapOut<HashMap<A, B>> for HashMap<A, Wrap<B>>
...

For there to be a conflict we have to be able to generate the same impl from the second blanket impl. To generate the matching impl from the second blanket impl, we have to plug in A and Wrap<B> for T and U such that the implementing types match, but this actually gives us:

impl WrapOut<HashMap<A, Wrap<B>>> for HashMap<A, Wrap<B>>
//                      ^^^^^^^
...

If we make the implementing types match, the trait we're implementing changes, so there can't be a conflict.

As for your more general question, the difference between a trait with a generic parameter and a trait with an associated type is exactly that you can only implement the trait with an associated type once for a given type. Rust can't distinguish these impls, they look the same:

impl Trait for Type {
    type A = X;
}
impl Trait for Type {
    type A = Y;
}

But with a generic parameter, you can implement it as many times as you want, so long as the generic type argument is different:

impl Trait<X> for Type {}
impl Trait<Y> for Type {}

Once you do blanket impls, you start having to deal with Rust's coherence rules which can get pretty subtle and complex, as you saw above.

Which one is prefereable comes down solely to the use case. Some traits should be generic, some should use associated types.

In this case, making it generic would mean that one type can get unwrapped into multiple different types, which might be preferable. Note that it'll make type inference harder, so you'll need to add annotations more often than with associated types.