[c++20] Implement P2113R0: Changes to the Partial Ordering of Constrained Functions

[ychen]

Summary

Most of the wordings are implemented straightforwardly. However,
for https://eel.is/c++draft/temp.fct#temp.func.order-6.2.1.2, I didn't
directly check ... no reordering or more than one reordering ....
Instead, the reordering (or the correspondence between template
parameters) is according to the order of template parameter deducing
(this also helps to fix PR49964).

Fixes https://github.com/llvm/llvm-project/issues/54039
Fixes https://github.com/llvm/llvm-project/issues/49308 (PR49964)

[erichkeane]

Is there any chance you can validate this against https://reviews.llvm.org/D126907 as well? We touch similar code, and I'm intending to get that committed in the near future. Otherwise, after a quick look, I don't see anything particualrly bad, other than a lack of release notes and update of www-status.

[ychen]

In D128750#3616449, @erichkeane wrote:

Is there any chance you can validate this against https://reviews.llvm.org/D126907 as well? We touch similar code, and I'm intending to get that committed in the near future. Otherwise, after a quick look, I don't see anything particualrly bad, other than a lack of release notes and update of www-status.

Sure. I will test it.

[ychen]

In D128750#3616471, @ychen wrote:

In D128750#3616449, @erichkeane wrote:

Is there any chance you can validate this against https://reviews.llvm.org/D126907 as well? We touch similar code, and I'm intending to get that committed in the near future. Otherwise, after a quick look, I don't see anything particualrly bad, other than a lack of release notes and update of www-status.

Sure. I will test it.

check-all passes with this patch + D126907.

[ychen]

• add release notes
• update www-status

[royjacobson]

Thanks for working on this! I like the approach, but two comments:

I would like more tests for the different forms of template argument deduction. Some suggestions for things to test: template template arguments, 'auto' in abbreviated function templates, argument packs, non-type template parameters. We should at least test that we find the more constrained function when the parameters are equal.

I'm also a bit concerned that we're deviating from the standard here w.r.t. to the 'reordering' checks for reversed candidates. I support this - I think your version makes more sense than what the standard says to do here - but if someone could check with the committee (I don't have reflector access myself) that we're not breaking some important use case by doing it this way, I think it's a good idea.

clang/docs/ReleaseNotes.rst

134–138

You can remove this bullet from when I partially implemented this paper :)

clang/lib/Sema/SemaTemplate.cpp

7810

Consider adding

clang/lib/Sema/SemaTemplateDeduction.cpp

5119

Curious, why was this removed?

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5119

I think this is related to https://wg21.link/cwg818 and https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3086.html#US45.

I'll include this change in D128745 instead.

[ychen]

In D128750#3627085, @royjacobson wrote:

Thanks for working on this! I like the approach, but two comments:

Thanks for the review.

I would like more tests for the different forms of template argument deduction. Some suggestions for things to test: template template arguments, 'auto' in abbreviated function templates, argument packs, non-type template parameters. We should at least test that we find the more constrained function when the parameters are equal.

Sure, will do.

I'm also a bit concerned that we're deviating from the standard here w.r.t. to the 'reordering' checks for reversed candidates. I support this - I think your version makes more sense than what the standard says to do here - but if someone could check with the committee (I don't have reflector access myself) that we're not breaking some important use case by doing it this way, I think it's a good idea.

Yeah, I found it kinda hard to implement the reordering aspect efficiently. My understanding of the reordering aspect is for finding an intuitive order of template parameters that makes sense for the following constraints tie breaker. Hi @hubert.reinterpretcast, could you please shed some light on the intended implementation for https://eel.is/c++draft/temp.func.order#6.2.1.2? I'm a little hesitant to use an exhaustive approach to find the template parameter order for constraints comparison. Does using deducing order sound reason to you? Thanks.

[ychen]

In D128750#3627085, @royjacobson wrote:

I'm also a bit concerned that we're deviating from the standard here w.r.t. to the 'reordering' checks for reversed candidates. I support this - I think your version makes more sense than what the standard says to do here - but if someone could check with the committee (I don't have reflector access myself) that we're not breaking some important use case by doing it this way, I think it's a good idea.

I gave this more thought and think the current approach of using deduce order does not contradict the standardese.

The reason is that there is only one way to reorder the function parameter lists of rewritten candidates because they are all binary operators. Hence "reorder" simply means "reverse". Also, https://eel.is/c++draft/temp.func.order#6.2.1.2.2 says "the function parameters that *positionally correspond* between the two templates are of the same type,". My understanding is that *positionally correspond* and *reverse* dictates that either zero or one reordering works, but not two or more. This is also based on the assumption that rewritten candidates can only have two operands, which I believe is true as of C++20, not sure about it in the future.

For example, in

template <typename> constexpr bool True = true;
template <typename T> concept C = True<T>;
template <typename T, typename U> struct X { };

template <C T, typename U, typename V> bool operator==(X<T, U>, V);
template <C V, C U, typename T>        bool operator==(T, X<U, V>); // rewritten candidate

suppose reordering the rewritten candidate's template parameters list as the below works:

template <C U, C V, typename T>        bool operator==(X<U, V>, T); // rewritten candidate

There is *no* way to reorder the template parameters list again (to get two or more reordering) and the resulted template still works, because of the *positionally correspond* requirement. If this reasoning is sound, I think the current approach of deducing order to compare constraints for rewritten candidates is correct. I wouldn't say I'm 100% confident. But it still makes sense to me at this moment.

[royjacobson]

In D128750#3661576, @ychen wrote:

...
There is *no* way to reorder the template parameters list again (to get two or more reordering) and the resulted template still works, because of the *positionally correspond* requirement. If this reasoning is sound, I think the current approach of deducing order to compare constraints for rewritten candidates is correct. I wouldn't say I'm 100% confident. But it still makes sense to me at this moment.

I'm not sure I follow your reasoning here. I agree we can't reorder the function parameters, but in your example with T/U/V we have 3 template parameters that we could reorder in 6 different ways. According to how I read 6.2.1.2 we'd need to check there's only one way to order them equivalently, which (I think) reduces to every template parameter appears only once.

[ychen]

In D128750#3662898, @royjacobson wrote:

but in your example with T/U/V we have 3 template parameters that we could reorder in 6 different ways.

But, any reordering of the 6 that does not have consecutive U and V is not valid. Because in the other template, T/U is consecutive and used by X<T, U> in that order. I don't think it is allowed to change the template parameter references in the function parameters.

[royjacobson]

In D128750#3663161, @ychen wrote:

In D128750#3662898, @royjacobson wrote:

but in your example with T/U/V we have 3 template parameters that we could reorder in 6 different ways.

But, any reordering of the 6 that does not have consecutive U and V is not valid. Because in the other template, T/U is consecutive and used by X<T, U> in that order. I don't think it is allowed to change the template parameter references in the function parameters.

Sorry for taking the time to answer!
I'm still not sure why it wouldn't be allowed to change template parameter freely. The standard just says 'reordering of the associated template-parameter-list'. I understand it to mean any permutation of them until they match the order of the other function's template parameters (which doesn't even to be the candidate that generated this reversed candidate). I don't understand why U,V must be consecutive - might be I'm missing something, but all forms seem to be valid templates? https://godbolt.org/z/E8Y3Ez3TY

Also, in case it was understood otherwise - I still think this is reasonable and I don't think we should wait until someone gets an answer from CWG - my request for changes is because I want to see better tests coverage.