Returning an impl Trait in associated type position results in error at point-of-use instead of point-of-definition

[Nemo157]

Example (playground):

pub trait Foo {
    type Bar: std::ops::Add<Self::Bar>;
    fn bar(self) -> Self::Bar;
}

impl<T: std::ops::Add<T>> Foo for T {
    type Bar = T;
    fn bar(self) -> Self::Bar {
        self
    }
}

pub fn foo() -> impl Foo<Bar = impl std::ops::Sub<usize>> {
    5usize
}

fn main() {
    foo().bar() - 4usize;
}

This should error at the definition of foo since impl std::ops::Sub<usize> does not satisfy the std::ops::Add bound required by Foo::Bar. Instead it errors at the use-site in main, and if that line is deleted (e.g. if this is a pub fn in a library) there is no error.

error[E0277]: cannot add `impl std::ops::Sub<usize>` to `impl std::ops::Sub<usize>`
  --> src/main.rs:18:11
   |
18 |     foo().bar() - 4usize;
   |           ^^^ no implementation for `impl std::ops::Sub<usize> + impl std::ops::Sub<usize>`
   |
   = help: the trait `std::ops::Add` is not implemented for `impl std::ops::Sub<usize>`

[Nemo157]

@rustbot modify labels to +A-impl-trait

[aliemjay]

Fixed in 1.49.0

@rustbot label E-needs-test

[JohnTitor]

So the problem here was diagnostics, right? Since it now compiles fine, I think it's more of "hidden" than "fixed". Given that, I'm not sure if it's really worth adding a regression test, any thoughts?

[Nemo157]

Wait, how does this compile now? fn foo should be invalid, it's returning a type that doesn't implement the trait it claims to implement.

A slight modification shows that it's now somehow leaking additional trait impls that weren't declared on the impl Sub type (playground):

pub trait Foo {
    type Bar: std::ops::Add<Self::Bar, Output = Self::Bar> + std::fmt::Debug;
    fn bar(self) -> Self::Bar;
}

impl<T: std::ops::Add<T, Output = T> + std::fmt::Debug> Foo for T {
    type Bar = T;
    fn bar(self) -> Self::Bar {
        self
    }
}

pub fn foo() -> impl Foo<Bar = impl std::ops::Sub<usize>> {
    5usize
}

fn baz<T: Foo>(foo1: T, foo2: T) { dbg!(foo1.bar() + foo2.bar()); }

fn main() {
    baz(foo(), foo());
}

[oli-obk]

Yea, this is pretty much that one backcompat hack that I want to eliminate:

rust/compiler/rustc_trait_selection/src/traits/project.rs

Line 260 in 4f372b1

selcx.infcx().replace_opaque_types_with_inference_vars(

should get removed and cratered.

[JohnTitor]

@oli-obk thanks for the pointer! Are we ready to run crater or do you want to add some more patches before it?

[oli-obk]

Unless something comes up during the removal PR itself, this should be ready to go

[oli-obk]

Fixed in 1.49.0

Fixed by #73905 specifically.

[oli-obk]

The reason this works is that in the original example we replace all opaque types in the function signature with inference variables (for typeck, nowhere else!). So in

pub fn foo() -> impl Foo<Bar = impl std::ops::Sub<usize>> {
    5usize
}

• impl std::ops::Sub<usize> becomes _1 with an obligation that _1: Sub<usize>.
• meaning impl Foo<Bar = impl Sub<usize>> becomes impl Foo<Bar = _1>
• and then that becomes _2 with an obligation that _2: Foo and <_2 as Foo>::Bar = _1 (from the impl) and <_2 as Foo>::Bar: Add<<_2 as Foo>::Bar> (from the trait)

now... during typeck we figure out that the return type of the function is usize because of the 5usize. So we figure out that _2 is actually 5usize.

This means that we now have to prove usize: Foo and <usize as Foo>::Bar = _1

Luckily that is easy to prove, as there's

impl<T: std::ops::Add<T>> Foo for T {
    type Bar = T;
    fn bar(self) -> Self::Bar {
        self
    }
}

that usize trivially satisfies (usize: Add<usize> does hold after all).

Due to that impl we know

<usize as Foo>::Bar = usize

Due to our obligations we know

<_2 as Foo>:: Bar = _1 + _2 = usize so

<usize as Foo>::Bar = _1

makes us know that _1 = usize.

Furthermore we got <_2 as Foo>::Bar: Add<<_2 as Foo>::Bar> from the trait, which we can now resolve to <usize as Foo>::Bar: Add<<usize as Foo>::Bar> which is usize: Add<usize> which holds.

So this passes compilation so far. Now the question is why foo().bar() - 4usize; passes, which was what originally failed before #73905. The reason that failed is that it tried to prove impl Sub<usize>: Add<impl Sub<usize>> instead of just accepting that it must hold, as otherwise foo would not have compiled. Note that you can't immediately assume that Add holds (foo().bar() + 4usize; does not compile after all), but you can get there as shown in #72614 (comment)

[JohnTitor]

Thanks for the detailed explanation, Oli! I've now understood it :)
So, the original issue here was a diagnostics one and the compiler now accepts that code, I think we could just clone this issue without a test.
If someone wants to add it, feel free to re-open and add the needs-test label.

[Nemo157]

I don't understand why it is allowed to bring this additional information in:

and <_2 as Foo>::Bar: Add<<_2 as Foo>::Bar> (from the trait)

The type impl Sub<usize> should not allow leaking other non-auto traits it implements.

[oli-obk]

There is no leaking happening. There is a weird situation where as long as you only know about the associated type, but not what it resolves to, you know about the Add but not the Sub. When you normalize the assoc type to its concrete type, you lose the information about the Add but gain the Sub.