Is this on purpose? -- Conflicting Impl Check

[Gankra]

This was stumbled across while trying to hack around the conflicting trait implementation checker. I can intuit why it's sound, but it was surprising to me that the compiler was this "smart". I wanted to put this up to make sure we intend things to work this way.

So here's a program that is desired to work:

trait Backend {
    type Metadata;
}

struct SuperBackend<B: Backend> {
    metadata: B::Metadata,
}

impl<B: Backend> ::std::borrow::Borrow<B::Metadata> for SuperBackend<B> {
    fn borrow(&self) -> &B::Metadata {
        &self.metadata
    }
}

fn main() { }

But the borrow implementation is rejected as conflicting:

error[E0119]: conflicting implementations of trait `std::borrow::Borrow<SuperBackend<_>>` for type `SuperBackend<_>`:
 --> src/main.rs:9:1
  |
9 | impl<B: Backend> ::std::borrow::Borrow<B::Metadata> for SuperBackend<B> {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: conflicting implementation in crate `core`:
          - impl<T> std::borrow::Borrow<T> for T
            where T: ?Sized;

The issue raised is that the given impl can potentially allow for B::Metadata=Self which completely overlaps with the blanket implementation in core. And indeed we can write a Backend implementation that does this:

struct EvilBackend { }
impl Backend for EvilBackend {
    type Metadata = SuperBackend<EvilBackend>;
}

Although we cannot actually instantiate the type SuperBackend<EvilBackend> for use in our borrow impl, because it has infinite size! Sadly the compiler doesn't acknowledge this fact, and refuses to let us proceed.

Now here's the interesting part: if we tweak our code to make the associated type a generic that we default, it compiles!

trait Backend {
    type Metadata;
}

struct SuperBackend<B: Backend, S=<B as Backend>::Metadata> {
    metadata: S,
    _boo: ::std::marker::PhantomData<B>,
}

impl<B: Backend, S> ::std::borrow::Borrow<S> for SuperBackend<B, S> {
    fn borrow(&self) -> &S {
        &self.metadata
    }
}

fn main() { }

Again I can reason that this is correct, because the EvilBackend implementation is now inexpressable, leading to a compilation error:

struct EvilBackend { }
impl Backend for EvilBackend {
    type Metadata = SuperBackend<EvilBackend>;
}

Because SuperBackend<EvilBackend> is actually sugar for a type with infinite complexity: SuperBackend<EvilBackend, SuperBackend<EvilBackend, SuperBackend< .................

It's a bit surprising to me that this kind of reasoning is (apparently?) being applied now that the infinity is at the type-description level and not hidden inside a recursive associated type projection. I can imagine those are a bit different, as perhaps static members of the trait implementation could be invoked even if the implementation is unusable (due to infinite size_of)?

Anyway, just wanted to check that this is all intentional.

[zakarumych]

My guess is that rustc can just figure that with struct Foo<T> {...} Foo<T> != T.

[arielb1]

It's a bit surprising to me that this kind of reasoning is (apparently?) being applied now that the infinity is at the type-description level and not hidden inside a recursive associated type projection.

The requirement that types be finite in length - the occurs check - is a standard rule of Hindley-Milner-style type systems that is built pretty deeply into all such type inference engines. That e.g. allows the compiler to conclude that Foo<$0> != $0.

See e.g. this code:

fn main() {
    let mut x = None;
    x = Some(Box::new(x)); //~ ERROR mismatched types
    //~| cyclic type of infinite size
}

However, Rust's requirement that types have a finite size is not that deep (it might be as a requirement in order for the type to implement Sized. However, there is no Self: Sized requirement in sight AFAICT, AND that check is not implemented that well with the current trait-checker), and in any case the overlap checker is fairly stupid with projections - see #20400 for an even simpler example.

[arielb1]

If you had a where Self: Sized bound somewhere, the compiler might be able to see that in order for Self: Sized, then Self::Metadata: Sized must hold too, which given that we know Self : SuperBackend<Metadata = Self>, is just Self : Sized - an infinite loop. This might lead to coherence succeeding.

However:

1. The current trait-solver is not quite that smart to handle this case and would give up - Chalk should fix that.
2. Can't write non-overlapping blanket impls that involve associated type bindings #20400 means that even if it was that smart, it still ignores the Self : SuperBackend<Metadata = Self> requirement when looking for contradictions in other requirements.

[arielb1]

So to sum up:

1. This is completely intentional.
2. A future version of rustc might theoretically have the first example working, especially if you add a where Self: Sized bound to the impl.

[Gankra]

Makes sense, thanks!