Trait methods can't be found by method resolution if the self type involves projections

[steffahn]

I tried this code:

pub type Id<T> = <T as IdTrait>::T;

pub trait IdTrait {
    type T: ?Sized;
}

impl<T: ?Sized> IdTrait for T {
    type T = T;
}

#[derive(Copy, Clone)]
struct Foo;
impl Foo {
    fn method(self: Id<Self>) {
        println!("hi!");
    }
}

trait FooTrait {
    fn method2(self: Id<Self>);
}
impl FooTrait for Foo {
    fn method2(self) { // or `: Id<Self>`, makes no difference here
        println!("hi!");
    }
}

pub fn main() {
    let foo = Foo;
    foo.method(); // works
    foo.method2(); // doesn't work
    Foo::method2(foo); // works
}

(playground)

I expected to see this happen: Code compiles successfully

Instead, this happened:

error[E0599]: no method named `method2` found for struct `Foo` in the current scope
  --> <source>:31:9
   |
12 | struct Foo;
   | ---------- method `method2` not found for this struct
...
20 |     fn method2(self: Id<Self>);
   |                      -------- the method might not be found because of this arbitrary self type
...
31 |     foo.method2(); // doesn't work
   |         ^^^^^^^
   |
help: there is a method `method` with a similar name
   |
31 |     foo.method(); // doesn't work
   |         ~~~~~~

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0599`.
Compiler returned: 1

This is technically an old regression in 1.22, the code compiled fine up to Rust 1.21.

[steffahn]

Of course, fixing this is also technically breaking (though unlikely problematic in practice, because who writes signatures like this?) because it not only causes compilation errors but also allows for fallbacks further down the line in method resolution candidates

pub type Id<T> = <T as IdTrait>::T;

pub trait IdTrait {
    type T: ?Sized;
}

impl<T: ?Sized> IdTrait for T {
    type T = T;
}

#[derive(Copy, Clone)]
struct Foo;
impl Foo {
    fn method_a(&self) {
        println!("assoc method_a!");
    }
    fn method_b(&self) {
        println!("assoc method_b!");
    }
}

trait FooTrait {
    fn method_a(self);
    fn method_b(self: Id<Self>);
}
impl FooTrait for Foo {
    fn method_a(self) {
        println!("trait method_a!");
    }
    fn method_b(self) {
        println!("trait method_b!");
    }
}

pub fn main() {
    let foo = Foo;
    foo.method_a(); // trait method_a!
    foo.method_b(); // assoc method_b!

}

(playground)

trait method_a!
assoc method_b!

[steffahn]

@rustbot label +T-compiler, A-traits, A-typesystem, A-resolve, -needs-triage

[compiler-errors]

For anyone investigating this from the compiler side (i.e. I'm not gonna translate to normal people speech), this is because we're not normalizing the xform_self_ty in method probing for trait candidates 🤦

[dingxiangfei2009]

I gave it a try in normalizing xform_self_ty in fn consider_probe and rightfully I got back an obligation.

Obligation(predicate=Binder { value: ProjectionPredicate(AliasTy { args: [?2t], def_id: DefId(0:6 ~ once[0394]::IdTrait::T) }, Term::Ty(?3t)), bound_vars: [] }, depth=1)

Alternatively, with -Znext-solver, I got this obligation.

Obligation(predicate=Binder { value: AliasRelate(Term::Ty(Foo), Subtype, Term::Ty(Alias(Projection, AliasTy { args: [?2t], def_id: DefId(0:6 ~ once[0394]::IdTrait::T) }))), bound_vars: [] }, depth=0)

Both look very right to me. The hard part is to solve for the inference variable ?2t here, which is really just the Self type of the trait ref under probing. I am not sure how to unify ?2t with the proposed self_ty at the moment.

So @compiler-errors, would you mind dropping a hint at how this could be done? Thank you so much!

[dingxiangfei2009]

Actually I have thought about it a bit more. I am not sure if unifying Self with self_ty makes sense in most cases. We could apply heuristic, like adding or dropping reference, but it won't work in general. 🤔

[dingxiangfei2009]

I think we can perform the normalization, but I don't think we can fulfill <?'2 as IdTrait>::T == Foo by directly inferring ?'2 is Foo. It may have to consider specialization cases and I might need some mentoring, or leave it as is for now because there might be unknown consequences.

// We might override the blanket impl IdTrait if we have specialization in associated type
impl IdTrait for Baz {
    type T = Foo;
}
// So then we need to use impl FooTrait for Baz. Should specialization allow this probe result, or no?

cc @compiler-errors I have a tiny patch ready to just apply the normalization, but at this point I can't "solve" this issue entirely.

[compiler-errors]

@steffahn: I do not expect the code you shared to work as it is written. <?0 as IdTrait>::T == Foo doesn't currently ever infer ?0 == Foo, neither in the old trait solver and the new trait solver, since neither considers trait goals when the self type is an inference variable, and I don't expect that to change. You can slightly modify the example to get something I expect should work:

pub type Id<T> = <Wrapper<T> as IdTrait>::T;

pub trait IdTrait {
    type T: ?Sized;
}

struct Wrapper<T: ?Sized>(T);
impl<T: ?Sized> IdTrait for Wrapper<T> {
    type T = T;
}

---

@dingxiangfei2009: This code works in the new trait solver (-Znext-solver) because of deferred projection equality. I don't think this needs to be fixed in the old trait solver, or at least I don't have the capacity to mentor any fixes currently.

[steffahn]

@compiler-errors With less compiler insight than you obviously, I was expecting it to work, because at some point the compiler (obviously) figured out that self: Id<Self> actually means self: Self when looking at the method definition/declaration. Otherwise, it would have been rejected for “not being a valid self-type”. Now my thinking is that in this process of checking the validity of the self-type, it might have just as well just sort-of “re-written the signature” into the more simple/normalized equivalent. Feel free to point out if such a process seems too wild / unprecedented, or otherwise problematic. (Or e.g. maybe the check for valid self-type doesn’t even necessarily happen earlier in compilation than the method resolution of possible users?)

[steffahn]

Also don’t forget that the code …somehow… did compile up to Rust 1.21. So – naively – it seems doable to me that it would be made to compile again. (Unless that relied on any compiler bugs at the time, or some wildly different compiler internals or whatnot...)

[compiler-errors]

@steffahn:

Now my thinking is that in this process of checking the validity of the self-type, it might have just as well just sort-of “re-written the signature” into the more simple/normalized equivalent. Feel free to point out if such a process seems too wild / unprecedented, or otherwise problematic

No, the compiler does not typically "rewrite" things like this. We always start with an unnormalized signature and work forwards from there, which as I mentioned above, would result in ambiguity due the way that trait selection is implemented currently.

because at some point the compiler (obviously) figured out that self: Id actually means self: Self when looking at the method definition/declaration. Otherwise, it would have been rejected for “not being a valid self-type”.

I see this instead as a shortcoming of the code that validates self types for method definitions. It currnetly uses a placeholder type (think of a skolem in haskell if you're familiar with that), which does allow projection to side-step the built-in ambiguity that we have when projecting the IdTrait::Assoc type when self is an inference variable.

Also don’t forget that the code …somehow… did compile up to Rust 1.21

Reminder that 1.21 was in 2017, and the type system has changed a lot since then. I wouldn't be surprised if whatever broke that code in 1.22 was a fundamental change that fixed normalization or something in the type system.