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

lf- · 2021-09-04T06:54:30Z

Fixes #716
Related to rust-lang/rust-analyzer#4558

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- · 2021-09-04T06:56:05Z

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- · 2021-09-04T06:59:51Z

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

Based on the code that actually generates these binders, it's all the binders on both the item and the impl, and the docs must have drifted.

lf- · 2021-09-04T07:06:57Z

sigh added a cargo update commit

nikomatsakis

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

nikomatsakis · 2021-09-09T17:30:12Z

chalk-solve/src/split.rs

@@ -194,6 +194,146 @@ pub trait Split<I: Interner>: RustIrDatabase<I> {
        let (other_params, trait_params) = parameters.split_at(split_point);
        (trait_params, other_params)
    }
+
+    /// Given the full set of parameters (or binders) for an


Hmm, this duplication is a bit unfortunate. I wonder if there's a good way to refactor things to avoid it. I guess it's a consequence of trying to preserve the split between associated types and functions.

nikomatsakis · 2021-09-09T17:31:06Z

tests/test/impls.rs

+}
+
+#[test]
+fn impl_function_basic_generics() {


Can we have a variant of this test that includes method generics?

e.g.,

trait Trait<T> { fn a<U>(self); }

nikomatsakis · 2021-09-09T17:32:03Z

tests/test/impls.rs

+                fn a(v: T);
+            }
+            impl@NotImpl<T> Trait<T> for B<T> {
+                fn a(v: T);


Can we have a test where the choice between impls is driven by the where clauses?

e.g.

impl<T> Trait<T> for T: Copy { fn a(); } impl<T> Trait<T> for Vec<T> { fn a(); }

normalizing Vec<u32> should give the second impl.

This necessitates overlapping impls, does it not?

T: Copy and Vec<T> do not overlap, or do you mean something else?

tests/test/impls.rs

lf- · 2021-09-09T18:13:49Z

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 · 2021-09-10T13:37:10Z

@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- · 2021-09-10T15:45:52Z

@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- · 2021-09-16T08:37:43Z

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 · 2021-10-03T19:43:41Z

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

nikomatsakis · 2021-10-04T14:35:39Z

@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 · 2022-02-14T15:50:32Z

@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.

lf- force-pushed the source-impl branch from 4e93c01 to f17edd8 Compare September 4, 2021 06:59

lf- added 8 commits September 4, 2021 00:06

Deps update

01a9331

Refactor: generate impls of Zip for slice-based types with a macro

de72510

Refactor: Make a FnDefTy

08fa473

Update the docs of AssociatedTyValue to reflect the state now

3995798

Based on the code that actually generates these binders, it's all the binders on both the item and the impl, and the docs must have drifted.

Mechanical doc changes: fix warnings, add links

cf4b239

Add documentation to trait data

2f89347

Add associated functions to the AST and parser

058e4a7

Implement NormalizeFn in the back end

69178a6

lf- force-pushed the source-impl branch from f17edd8 to 69178a6 Compare September 4, 2021 07:06

nikomatsakis self-assigned this Sep 8, 2021

nikomatsakis requested changes Sep 9, 2021

View reviewed changes

Add requested tests; add tracing debugging to chalk-integration

bf4de02

nikomatsakis closed this Feb 14, 2022

HKalbasi mentioned this pull request Apr 17, 2022

Add ProjectionTerm #745

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

lf- commented Sep 4, 2021 •

edited

Loading

lf- commented Sep 4, 2021

lf- commented Sep 4, 2021

lf- commented Sep 4, 2021

nikomatsakis left a comment

nikomatsakis Sep 9, 2021

nikomatsakis Sep 9, 2021

nikomatsakis Sep 9, 2021

lf- Sep 16, 2021

Aloso Oct 10, 2021

lf- commented Sep 9, 2021

nikomatsakis commented Sep 10, 2021

lf- commented Sep 10, 2021

lf- commented Sep 16, 2021

bors commented Oct 3, 2021

nikomatsakis commented Oct 4, 2021

nikomatsakis commented Feb 14, 2022

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

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

Conversation

lf- commented Sep 4, 2021 • edited Loading

lf- commented Sep 4, 2021

lf- commented Sep 4, 2021

lf- commented Sep 4, 2021

nikomatsakis left a comment

Choose a reason for hiding this comment

nikomatsakis Sep 9, 2021

Choose a reason for hiding this comment

nikomatsakis Sep 9, 2021

Choose a reason for hiding this comment

nikomatsakis Sep 9, 2021

Choose a reason for hiding this comment

lf- Sep 16, 2021

Choose a reason for hiding this comment

Aloso Oct 10, 2021

Choose a reason for hiding this comment

lf- commented Sep 9, 2021

nikomatsakis commented Sep 10, 2021

lf- commented Sep 10, 2021

lf- commented Sep 16, 2021

bors commented Oct 3, 2021

nikomatsakis commented Oct 4, 2021

nikomatsakis commented Feb 14, 2022

lf- commented Sep 4, 2021 •

edited

Loading