Add NormalizeFn domain goal that associates projections of functions on traits with the matching implementation

lf- commented 3 years ago

This adds a NormalizeFn domain goal that's analogous to Normalize for types, which can be used to infer the related impl functions.

Along with this, I modify the chalk integration testing system's parser to add syntax naming impls: impl SomeTrait@MyImpl<T> for SomeType<T>. Impl functions can be referenced with @MyImpl::some_func<P1, P2, .....>. The parser also now supports functions in traits and impls.

The current state of this patch is ready for others to break it ;-) I don't have enough edge cases of traits in my head to think of all the ways to find more bugs in it.

Here is one of the tests from the PR, for context on what it does:

#[test]
fn impl_function_basic_generics() {
    test! {
        program {
            trait Trait<T> {
                fn a();
            }

            struct A<T> {}
            struct B<T> {}
            struct C {}

            impl@Impl<T> Trait<T> for A<T> {
                fn a();
            }
            impl@NotImpl<T> Trait<T> for B<T> {
                fn a();
            }
        }

        goal {
            exists <F> {
                NormalizeFn(<A<C> as Trait<C>>::a -> F)
            }
        } yields {
            "Unique; substitution [?0 := {impl @Impl}::a<C>], lifetime constraints []"
        }
    }
}

This may be generalizable to constants also? I didn't explore this yet. If it's desired to explore it for this PR, I will have to take a break for a while before getting to it.

lf- commented 3 years ago

I created a thread on Zulip here for questions: https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/Chalk.20PR.20to.20identify.20which.20impl.20provides.20a.20function

lf- commented 3 years ago

tried rebasing, see if that fixes the spurious CI failure due to lalrpop failing to build

lf- commented 3 years ago

sigh added a cargo update commit

lf- commented 3 years ago

This looks very good! I left some requests for more tests.

So I've been working a little on implementing this in rust analyzer and I feel like I might really want to just refactor the whole thing to work on any kind of associated item, which is a refactoring I'm slightly dreading doing because it feels overwhelming (it shouldn't actually be that bad but still). I'm increasingly convinced it needs to happen both for this use case and for the compiler :/

It should not actually be that terrible because hardly any of this is actually function-specific logic, really, I just have to try it.

I'll see about writing those tests because they'll be useful regardless.

nikomatsakis commented 3 years ago

@lf- I don't understand what refactoring you have in mind exactly. Do you mean having just one kind of domain goal, used for both associated types and for associated functions?

lf- commented 3 years ago

@lf- I don't understand what refactoring you have in mind exactly. Do you mean having just one kind of domain goal, used for both associated types and for associated functions?

Not quite: I want one domain goal for identifying the appropriate definition in impls, for all item types including constants and associated types, as proposed on the original r-a thread. Normalize would be kept as is and NormalizeFn would be changed.

lf- commented 3 years ago

I found a bug I probably wrote in chalk-integration that I can't solve right now, with "duplicate or shadowed parameters" in the case of function generics, where the generic is introduced in the binders in the outer scope and also in LowerFnDefn. Need to do more work to figure this out.

bors commented 2 years ago

:umbrella: The latest upstream changes (presumably #730) made this pull request unmergeable. Please resolve the merge conflicts.

nikomatsakis commented 2 years ago

@lf- I've been talking with @tmandry about the idea of exposing an associated type for every associated function. I think that is very likely to happen. That suggests that I was wrong to encourage you to split associated functions and associated types, and it would be better to combine the two. We should definitely find some time to sync up on the best path forward for this PR!

nikomatsakis commented 2 years ago

@lf- I'm going to close this PR, because I think you've kind of run out of time to pursue it, but I would like to pick it up again.

rust-lang / chalk

Add NormalizeFn domain goal that associates projections of functions on traits with the matching implementation #726