Coherence when implementing Borrow<associated type>

I stumbled upon some surprising coherence errors when implementing Borrow for an associated type. (This came up in the context of this question on Stack Overflow.)

The following code

use std::borrow::Borrow;

pub trait Wrap {
    type Wrapped;
}

pub struct Wrapper<W: Wrap>(W::Wrapped);

impl<W, T> Borrow<T> for Wrapper<W>
where
    W: Wrap<Wrapped = T>,
{
    fn borrow(&self) -> &T {
        &self.0
    }
}

results in this error:

error[E0119]: conflicting implementations of trait `std::borrow::Borrow<Wrapper<_>>` for type `Wrapper<_>`:
  --> src/lib.rs:9:1
   |
9  | / impl<W, T> Borrow<T> for Wrapper<W>
10 | | where
11 | |     W: Wrap<Wrapped = T>,
12 | | {
...  |
15 | |     }
16 | | }
   | |_^
   |
   = note: conflicting implementation in crate `core`:
           - impl<T> std::borrow::Borrow<T> for T
             where T: ?Sized;

The conflict occurs because the type T might be Wrapper<T>, resulting in a conflicting implementation of impl Borrow<Wrapper<T>> for Wrapper<T>. While it is not actually possible to write an implementation of Wrap that leads to this kind of conflict – the resulting type would have an infinite recursion – I can understand that the compiler can't prove this and rejects the code.

It turns out that it is possible to convince the compiler that T can't be Wrapper<T> by introducing a dummy trait and using that as a trait bound on T:

pub trait Dummy {}

impl<W, T> Borrow<T> for Wrapper<W>
where
    W: Wrap<Wrapped = T>,
    T: Dummy,
{
    fn borrow(&self) -> &T {
        &self.0
    }
}

We would need to implement Dummy on each type we want to use as Wrap::Wrapped, but then this approach works. So far, so good.

However, if we remove the redundant type parameter T and use W::Wrapped instead, the code stops compiling again:

impl<W> Borrow<W::Wrapped> for Wrapper<W>
where
    W: Wrap,
    W::Wrapped: Dummy,
{
    fn borrow(&self) -> &W::Wrapped {
        &self.0
    }
}

I think the compiler should accept this version of the code as well if it accepts the previous one. What is the difference between the two last implementations of Borrow? Why does one compile, but the other doesn't?

https://github.com/rust-lang/rust/issues/50237

1 Like

@vitalyd Thanks for the link. This looked like a shortcoming in the compiler to me, but I wasn't sure whether I was missing anything. Good to know that chalk may resolve this at some point.

Yeah. These types of things really bother me because, from a user's perspective, they seem fully arbitrary differences (or, with a fully intentional pun, incoherent). Of course there's always a reason once someone intimately familiar with the compiler explains it, but it's hard to shake the feeling that portions of the language are glued together by bubble gum :slight_smile: (and I say this with full admiration and respect of the language and the brilliant folks working on it). The great thing is those same folks are fully aware of this, and working on/thinking about solutions.

1 Like