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

[ychen]

Summary

This implementation matches GCC behavior in that temp.func.order p6.2.1 is not implemented [1]. I reached out to the GCC author to confirm that some changes elsewhere to overload resolution are probably needed, but no solution has been developed sufficiently [3].

Most of the wordings are implemented straightforwardly. However,
for temp.func.order p6.2.2 "... or if the function parameters that positionally correspond between the two templates are not of the same type", the "same type" is not very clear ([2] is a bug related to this). Here is a quick example

template <C T, C U>        int f(T, U);
template <typename T, C U> int f(U, T);

int x = f(0, 0);

Is the U and T from different fs the "same type"? The answer is NO even though both U and T are deduced to be int in this case. The reason is that U and T are dependent types, according to temp.over.link p3, they can not be the "same type".

To check if two function parameters are the "same type":

• For function template: compare the function parameter canonical types and return type between two function templates.
• For class template/partial specialization: by temp.spec.partial.order p1.2, compare the injected template arguments between two templates using hashing(TemplateArgument::Profile) is enough.

[1] https://gcc.gnu.org/git/gitweb.cgi?p=gcc.git;h=57b4daf8dc4ed7b669cc70638866ddb00f5b7746
[2] https://github.com/llvm/llvm-project/issues/49308
[3] https://lists.isocpp.org/core/2020/06/index.php#msg9392

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

51–52

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

clang/lib/Sema/SemaTemplate.cpp

7865

Consider adding

clang/lib/Sema/SemaTemplateDeduction.cpp

5140–5141

Curious, why was this removed?

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5140–5141

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.

[ychen]

• Remove code for temp.func.order p6.2.1
• Add missing handling for partial ordering of partial specialization
• Add more tests
• Rebase

[ychen]

In D128750#3680607, @royjacobson wrote:

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.

Thanks for the feedback! I've updated the patch description to reflect the current status of the patch. PTAL.

[royjacobson]

Some documentation/test nits, and one question, but otherwise LGTM.
Could you fix the merge conflict? It would be nice to see pre-commit CI results.

Given the complexity of the technical details here, as long as it doesn't unreasonably delay this, please wait for other people to also review it.

clang/include/clang/AST/DeclTemplate.h

848–856

clang/lib/Sema/SemaTemplateDeduction.cpp

5161–5163

update docs here

5183

Previously we continued to check by constraints, now we directly return nullptr, doesn't this mean we don't perform constraints checks that we've done before? Or was it a bug?

5234

This comment should be moved down to the if (TPOC == TPOC_Conversion && check.

clang/test/CXX/temp/temp.decls/temp.fct/temp.func.order/p6.cpp

23

This is an explicit example from the standard, so I don't like changing it so subtly. Could you revert the change and document we're deviating from the standard here?

[ychen]

• address Roy's comments.

clang/lib/Sema/SemaTemplateDeduction.cpp

5183

I think this was a bug. By https://eel.is/c++draft/temp.func.order#6, the constraints check is performed only when Better1 && Better2.

[ychen]

In D128750#3721441, @royjacobson wrote:

Some documentation/test nits, and one question, but otherwise LGTM.
Could you fix the merge conflict? It would be nice to see pre-commit CI results.

Given the complexity of the technical details here, as long as it doesn't unreasonably delay this, please wait for other people to also review it.

Thanks for the review. Sure, I'll wait for more feedback.

[ychen]

• rebase

[ychen]

I'll land this tomorrow if no objections. Thanks.

[ychen]

In D128750#3741043, @ychen wrote:

I'll land this tomorrow if no objections. Thanks.

Sorry. Before submitting, I found an unhandled case involving the constrained placeholder type. Will update the patch later.

template <class T> concept C = True<T>;
template <class T> concept D = C<T> && sizeof(T) > 0;
template<C auto T> struct W;
template<D auto T> struct W<T>;

[ychen]

• handle constrained placeholder [pack] types

[ychen]

@royjacobson: really appreciate it if you could take another look.
@mizvekov: I saw you mentioned in the Discourse that you want to review template-related stuff and you have been actively working in that area, do you mind having a look at the patch? Thanks.

[mizvekov]

Just a first glance at the patch, will try to do a more comprehensive review later.

clang/lib/Sema/SemaConcept.cpp

823 ↗

(On Diff #456528)

clang/lib/Sema/SemaTemplateInstantiate.cpp

1840

I think this change could be masking a bug.

The arguments to an instantiation should always be canonical.

We could implement one day instantiation with non-canonical args, but this would not be the only change required to get this to work.

And regardless it should be done in separate patch with proper test cases :)

[ychen]

• For function templates, compare canonical types of funtion parameters directly.

[ychen]

In D128750#3758750, @mizvekov wrote:

Just a first glance at the patch, will try to do a more comprehensive review later.

Thanks!

clang/lib/Sema/SemaTemplateInstantiate.cpp

1840

Agreed.

It turns out this is because I was using injected template arguments to instantiate a function declaration (to compare function parameter types between two function templates). The injected template type arguments seem to be not canonical.

Now I realized that I don't need this instantiation. Comparing the function parameter canonical types directly should be fine since the template parameters are uniqued by their kind/index/level etc. which is comparable between two function templates.

[royjacobson]

I looked at the new Concept auto changes, they seem fine.

Thanks a LOT @ychen for working on this, it's been a very interesting patch to me :)
I'll let @mizvekov accept since he is much more experienced than me in those areas.

[mizvekov]

clang/include/clang/Sema/SemaConcept.h

48–52 ↗

(On Diff #456743)

Why are looking at only the type of the expression?
The expression can be arbitrarily different, but as long as they are both undeduced auto, that is okay?

54–68 ↗

(On Diff #456743)

It's a bit odd to find SubstTemplateTypeParmType necessary to implement the semantics of this change.

This is just type sugar we leave behind in the template instantiator to mark where type replacement happened.

There are several potential issues here:

1. This could be marking a substitution that happened at any template depth. Ie this could be marking a substitution from an outer template. Does the level not matter here at all?
2. If the level does matter, you won't be able to reconstitute that easily without further improvements. See https://github.com/llvm/llvm-project/issues/55886 for example.
3. A substitution can replace a dependent type for another one, and when that other gets replaced, we lose track of that because SubstTemplateTypeParmType only holds a canonical underlying type.

---

Leaving that aside, I get the impression you are trying to work around the fact that when an expression appears in a canonical type, presumably because that expression is dependent on an NTTP, we can't rely on uniquing anymore to compare if they are the same type, as we lack in Clang the equivalent concept of canonicalization for expressions.

But this however is a bit hard to implement. Are we sure the standard requires this, or can we simply consider these types always different?

clang/lib/AST/ASTContext.cpp

5149–5151 ↗

(On Diff #456743)

5154–5156 ↗

(On Diff #456743)

I don't know if this change is necessary for this patch, as this looks part of the workaround in SemaConcept.h,
but I think a better way to preserve the type here might be to always use NTTPType, but then add an additional Dependent parameter to PackExpansionExpr which can be used to force the expression to be dependent.

clang/lib/Sema/SemaConcept.cpp

827 ↗

(On Diff #456743)

If you need to dig down into the pattern, then I think the pattern might also contain casts and parenthesis which you would need to keep ignoring for the rest of the code to work.

I would consider adding a test for that.

clang/lib/Sema/SemaOverload.cpp

9675–9676

Why are these hasPrototype checks not needed anymore?

I don't see other changes which would obliviate the need for it. Presumably the code below is assuming we have them when we perform that FunctionProtoType cast.

Maybe this was either not possible, or we simply never added tests for it.

clang/lib/Sema/SemaTemplate.cpp

1267

I don't think the assert is even necessary TBH, the function can't return nullptr.

clang/lib/Sema/SemaTemplateDeduction.cpp

5234–5235

5243–5244

[ychen]

@mizvekov thanks for the detailed review. It helped me a lot in reconsidering the auto type handling.

clang/include/clang/Sema/SemaConcept.h

48–52 ↗

(On Diff #456743)

In the partial ordering context, the expression is the same explicit template argument. So we could treat two undeduced autos as equal.

This code is to deal with the fact that, AuoType is currently being uniqued on type constrained, which goes against the spirit of P2113R0 which considers type constraints only when the two types are equivalent.

I think the more neat way is to unique auto template parameter with the kind of placeholder type (auto, auto*, auto&, decltype(auto), ...), and its template parameter depth/index. Then we don't need the workaround here and I could simplify the code in SemaTemplateDeduction.cpp too. WDYT?

54–68 ↗

(On Diff #456743)

It's a bit odd to find SubstTemplateTypeParmType necessary to implement the semantics of this change.

Odd indeed.

Leaving that aside, I get the impression you are trying to work around the fact that when an expression appears in a canonical type, presumably because that expression is dependent on an NTTP, we can't rely on uniquing anymore to compare if they are the same type, as we lack in Clang the equivalent concept of canonicalization for expressions.

Yeah, sort of . This workaround is to deal with the fact that DecltypeType is not uniqued. However, the injected template argument for t of template<auto t> is decltype(t) (which on a side note, might be wrong since auto means using template arg deduct rules; decltype(auto) means using decltype(expr) type, let's keep it this way now since this code path is still needed when Clang starts to support decltype(auto) as NTTP type) and concepts partial ordering rules need to compare these concept template arguments (https://eel.is/c++draft/temp.constr#atomic-1).

Looking at the motivation why DecltypeType is not uniqued (https://github.com/llvm/llvm-project/blob/main/clang/lib/AST/ASTContext.cpp#L5637-L5640), I think maybe we should unique decltype on the expr to deal with concepts cleanly. Thoughts?

clang/lib/AST/ASTContext.cpp

5154–5156 ↗

(On Diff #456743)

I don't know if this change is necessary for this patch, as this looks part of the workaround in SemaConcept.h,

Yes, it is.

but I think a better way to preserve the type here might be to always use NTTPType, but then add an additional Dependent parameter to PackExpansionExpr which can be used to force the expression to be dependent.

Giving it a second thought, I think I could inspect the pattern of the PackExpansionExpr instead. I'll revert this hunk.

clang/lib/Sema/SemaConcept.cpp

827 ↗

(On Diff #456743)

The pattern is fixed as a concept id, like C<T>. I couldn't figure out when parentheses might show up. (https://eel.is/c++draft/dcl.spec.auto#nt:placeholder-type-specifier). I might be wrong.

clang/lib/Sema/SemaOverload.cpp

9675–9676

In c++, there will always be a prototype for the function?

clang/lib/Sema/SemaTemplate.cpp

1267

Agreed. Removed.

[mizvekov]

Hello, thanks, I appreciate that you found it helpful!

It's pretty late for me now, I will give this another look tomorrow.

clang/include/clang/Sema/SemaConcept.h

48–52 ↗

(On Diff #456743)

If you mean a change so that constraints are not part of the canonical type of undeduced AutoType, that is worth a try.
I can't think right now of a reason why they should be part of it in the first place.

54–68 ↗

(On Diff #456743)

I see, there should be no problem with a change to unique a DecltypeType, but it might not help you, because expressions typically have source location information embedded in them.

clang/lib/Sema/SemaOverload.cpp

9675–9676

Yeah that makes the most sense :)

[mizvekov]

clang/include/clang/Sema/SemaConcept.h

54–68 ↗

(On Diff #456743)

By the way, I just became aware of something I missed, and this could totally work here.

We don't have 'canonical expressions', but we do have profiling based on the canonical form of an expression, eg see the Expr::Profile method, it has a Canonical argument to ask for this.

[ychen]

• rebase

[ychen]

• rebase

[ychen]

• rebased on D135088

[ychen]

Hi @mizvekov , after D135088, this patch is ready.

[mizvekov]

clang/include/clang/Sema/SemaConcept.h

53–62 ↗

(On Diff #465549)

Why didn't we manage to get rid of this workaround yet?
I thought the changes to canonical AutoType were part of this, or are we still missing something?

A dependent DecltypeType is uniqued and has a canonical type by the way, this is implemented through the DependentDecltypeType subclass.

[ychen]

• remove dead code.

[ychen]

@mizvekov it turns out I don't need that code anymore. Thanks.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

I think you are not supposed to use the TemplateArgsAsWritten here.

The injected arguments are 'Converted' arguments, and the transformation above, by unpacking the arguments, is reversing just a tiny part of the conversion process.

It's not very meaningful to canonicalize the arguments as written to perform a semantic comparison, as that works well just for some kinds of template arguments, like types and templates, but not for other kinds in which the conversion process is not trivial.

For example, I think this may fail to compare the same integers written in different ways, like 2 vs 1 + 1.

[hubert.reinterpretcast]

I reached out to the GCC author to confirm that the committee acknowledges that there should be a change to temp.func.order p6.2.1, but no consensus on what changes to make [3].

A more accurate description is that some changes elsewhere to overload resolution are probably needed, but no solution has been developed sufficiently.

[ychen]

In D128750#3854675, @hubert.reinterpretcast wrote:

I reached out to the GCC author to confirm that the committee acknowledges that there should be a change to temp.func.order p6.2.1, but no consensus on what changes to make [3].

A more accurate description is that some changes elsewhere to overload resolution are probably needed, but no solution has been developed sufficiently.

I've updated the patch description. Thanks.

[ychen]

• skip non-dependent NTTP comparison because they're equivalent (match GCC)

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

Indeed. It can happen only when comparing one partial specialization with another. I think the standard does not require an implementation to deal with this but we could use the best effort without much overhead. For 2 vs 1+1 or similar template arguments that are not dependent, we could assume the equivalence because they wouldn't be in the partial ordering stage if they're not equivalent. For more complicated cases like J+2 vs J+1+1 where J is NTTP, let's stop trying (match GCC) because the overhead is a little bit high.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

But I think the 'TemplateArgs', which are the specialization arguments and are available through getTemplateArgs(), are the converted arguments you want here, ie the AsWritten arguments converted against the template.

I don't see why you can't just use that.

How about we change:

if (!TemplateArgumentListAreEqual(S.getASTContext())(P1, P2))
  return nullptr;

Into:

{
  ArrayRef<TemplateArgument> Args1 = P1->getTemplateArgs().asArray(), Args2;
  if constexpr (IsMoreSpecialThanPrimaryCheck)
    Args2 = P2->getInjectedTemplateArgs();
  else
    Args2 = P2->getTemplateArgs().asArray();

  if (Args1.size() != Args2.size())
    return nullptr;

  for (unsigned I = 0, E = Args1.size(); I < E; ++I) {
    TemplateArgument Arg2 = Args2[I];
    // Unlike the specialization arguments, the injected arguments are not
    // always canonical.
    if constexpr (IsMoreSpecialThanPrimaryCheck)
      Arg2 = S.Context.getCanonicalTemplateArgument(Arg2);

    // We use profile, instead of structural comparison of the arguments,
    // because canonicalization can't do the right thing for dependent
    // expressions.
    llvm::FoldingSetNodeID IDA, IDB;
    Args1[I].Profile(IDA, S.Context);
    Arg2.Profile(IDB, S.Context);
    if (IDA != IDB)
      return nullptr;
  }
}

That should work, right?

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

Actually, you can even further simplify this.

You can't have two different specializations with the same specialization arguments. These arguments are used as the key to unique them anyway.

So simplify my above suggestion to:

if constexpr (IsMoreSpecialThanPrimaryCheck) {
  ArrayRef<TemplateArgument> Args1 = P1->getTemplateArgs().asArray(),
                             Args2 = P2->getInjectedTemplateArgs();
  if (Args1.size() != Args2.size())
    return nullptr;

  for (unsigned I = 0, E = Args1.size(); I < E; ++I) {
    // We use profile, instead of structural comparison of the arguments,
    // because canonicalization can't do the right thing for dependent
    // expressions.
    llvm::FoldingSetNodeID IDA, IDB;
    Args1[I].Profile(IDA, S.Context);
    // Unlike the specialization arguments, the injected arguments are not
    // always canonical.
    S.Context.getCanonicalTemplateArgument(Args2[I]).Profile(IDB, S.Context);
    if (IDA != IDB)
      return nullptr;
  }
}

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

Yet another improvement here is that you can do this check once, when we create the specialization, and then simply store a hasSameArgumentsAsPrimaryInjected flag.

When we create the specialization, we already profile the specialization arguments anyway, so it's another computation you can avoid repeating.

Could even avoid repeating the profiling of the injected arguments if there was justified runtime overhead there, which I doubt, trading that off with increased memory use.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

It doesn't even need to be a flag to store in each SpecializationDecl, because there can be only one specialization with the same arguments as the primary injected arguments, for obvious reasons :D

So probably just a pointer in the TemplateDecl...

[ychen]

• use getTemplateArgs

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

'TemplateArgs' is indeed what I needed, I don't know how I missed that. There could be multiple partial specializations with the same arguments as the primary injected arguments and they differ by constraints (https://godbolt.org/z/onME5ehEE). I'm unsure if adding a hasSameArgumentsAsPrimaryInjected flag would save much since the IsMoreSpecialThanPrimaryCheck is only performed once. We could avoid maybe one profiling by introducing the hasSameArgumentsAsPrimaryInjected flag though. On the other hand, it doesn't make the implementation much harder either.

I did some compile-time measurements, and the results seem neutral https://llvm-compile-time-tracker.com/index.php?config=NewPM-O0-g&stat=instructions&remote=yuanfang-chen.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5482–5510

There could be multiple partial specializations with the same arguments as the primary injected arguments and they differ by constraints

Ah yeah, that is true.

I think not adding the flag looks fine, thanks for looking into it!

I am working tentatively on another patch where comparing template argument lists would become as cheap as comparing two pointers, and canonicalizing would be just one pointer indirection, so that issue would become moot anyway.

[mizvekov]

Is the pre-commit CI failure here related to the patch?

[ychen]

• rebase

[ychen]

In D128750#3864612, @mizvekov wrote:

Is the pre-commit CI failure here related to the patch?

Seems not. It should've been fixed by 606245ad542491400a5475c796df86a99f5c8c12.

[mizvekov]

LGTM, thanks!

[ychen]

@mizvekov Thanks for the review and provided valuable feedback.

[usaxena95]

clang/test/CXX/over/over.match/over.match.best/p1-2a.cpp

106

Thanks for working on this.

I wanted to bring up related: https://github.com/llvm/llvm-project/issues/56154
Eg.: Removing this const still removes the ambiguity but it shouldn't.
Since you have more context, does this look related to you ?

[ychen]

clang/test/CXX/over/over.match/over.match.best/p1-2a.cpp

106

Removing const makes the partial ordering compare constraints where AtLeast2<int> && true subsumes AtLeast2<int> so it is not ambiguous anymore. Similar reasoning could be made for the original test case of https://github.com/llvm/llvm-project/issues/56154. 56154 exposes an issue in constraints partial ordering which is not related to this patch.

[usaxena95]

clang/test/CXX/over/over.match/over.match.best/p1-2a.cpp

106

Thanks for the clarification.

clang/docs/ReleaseNotes.rst

 here. Generic improvements to Clang as a whole or to its underlying
 infrastructure are described first, followed by language-specific
 sections with improvements to Clang's support for those languages.
 
 Major New Features
 ------------------
 
 Bug Fixes
 ---------
 - Fixes an accepts-invalid bug in C when using a ``_Noreturn`` function
   specifier on something other than a function declaration. This fixes
   `Issue 56800 <https://github.com/llvm/llvm-project/issues/56800>`_.
 - Fix `#56772 <https://github.com/llvm/llvm-project/issues/56772>`_ - invalid
   destructor names were incorrectly accepted on template classes.
 - Improve compile-times with large dynamic array allocations with trivial
   constructors. This fixes
   `Issue 56774 <https://github.com/llvm/llvm-project/issues/56774>`_.
 - No longer assert/miscompile when trying to make a vectorized ``_BitInt`` type

 ^^^^^^^^^^^^^^^^^^^^^
 
 - Support capturing structured bindings in lambdas
   (`P1091R3 <https://wg21.link/p1091r3>`_ and `P1381R1 <https://wg21.link/P1381R1>`).
   This fixes issues `GH52720 <https://github.com/llvm/llvm-project/issues/52720>`_,
   `GH54300 <https://github.com/llvm/llvm-project/issues/54300>`_,
   `GH54301 <https://github.com/llvm/llvm-project/issues/54301>`_,
   and `GH49430 <https://github.com/llvm/llvm-project/issues/49430>`_.
+- Implemented `P2113R0: Proposed resolution for 2019 comment CA 112 <https://wg21.link/P2113R0>`_ ([temp.func.order]p6.2.1 is not implemented, matching GCC).
 
 
 
 
 C++2b Feature Support
 ^^^^^^^^^^^^^^^^^^^^^
 
 CUDA/HIP Language Changes in Clang

clang/include/clang/AST/DeclTemplate.h

llvm::PointerIntPair<RedeclarableTemplateDecl*, 1, bool>
       InstantiatedFromMember;
 
     /// If non-null, points to an array of specializations (including
     /// partial specializations) known only by their external declaration IDs.
     ///
     /// The first value in the array is the number of specializations/partial
     /// specializations that follow.
     uint32_t *LazySpecializations = nullptr;
+
+    /// The set of "injected" template arguments used within this
+    /// class template.
+    ///
+    /// This pointer refers to the template arguments (there are as
+    /// many template arguments as template parameaters) for the class
+    /// template, and is allocated lazily, since most class templates do not
+    /// require the use of this information.
+    TemplateArgument *InjectedArgs = nullptr;
   };
 
   /// Pointer to the common data shared by all declarations of this
   /// template.
   mutable CommonBase *Common = nullptr;
 
   /// Retrieves the "common" pointer shared by all (re-)declarations of
   /// the same template. Calling this routine may implicitly allocate memory
RedeclarableTemplateDecl *getInstantiatedFromMemberTemplate() const {
     return getCommonPtr()->InstantiatedFromMember.getPointer();
   }
 
   void setInstantiatedFromMemberTemplate(RedeclarableTemplateDecl *TD) {
     assert(!getCommonPtr()->InstantiatedFromMember.getPointer());
     getCommonPtr()->InstantiatedFromMember.setPointer(TD);
   }
 
+  /// Retrieve the "injected" template arguments that correspond to the
+  /// template parameters of this template.
+  ///
+  /// Although the C++ standard has no notion of the "injected" template
+  /// arguments for a template, the notion is convenient when
+  /// we need to perform substitutions inside the definition of a template.
+  ArrayRef<TemplateArgument> getInjectedTemplateArgs();
+
   using redecl_range = redeclarable_base::redecl_range;
   using redecl_iterator = redeclarable_base::redecl_iterator;
 
   using redeclarable_base::redecls_begin;
   using redeclarable_base::redecls_end;
   using redeclarable_base::redecls;
   using redeclarable_base::getPreviousDecl;
   using redeclarable_base::getMostRecentDecl;
protected:
 
   /// Data that is common to all of the declarations of a given
   /// function template.
   struct Common : CommonBase {
     /// The function template specializations for this function
     /// template, including explicit specializations and instantiations.
     llvm::FoldingSetVector<FunctionTemplateSpecializationInfo> Specializations;
 
-    /// The set of "injected" template arguments used within this
-    /// function template.
-    ///
-    /// This pointer refers to the template arguments (there are as
-    /// many template arguments as template parameaters) for the function
-    /// template, and is allocated lazily, since most function templates do not
-    /// require the use of this information.
-    TemplateArgument *InjectedArgs = nullptr;
-
     Common() = default;
   };
 
   FunctionTemplateDecl(ASTContext &C, DeclContext *DC, SourceLocation L,
                        DeclarationName Name, TemplateParameterList *Params,
                        NamedDecl *Decl)
       : RedeclarableTemplateDecl(FunctionTemplate, C, DC, L, Name, Params,
                                  Decl) {}
public:
   spec_iterator spec_begin() const {
     return makeSpecIterator(getSpecializations(), false);
   }
 
   spec_iterator spec_end() const {
     return makeSpecIterator(getSpecializations(), true);
   }
 
-  /// Retrieve the "injected" template arguments that correspond to the
-  /// template parameters of this function template.
-  ///
-  /// Although the C++ standard has no notion of the "injected" template
-  /// arguments for a function template, the notion is convenient when
-  /// we need to perform substitutions inside the definition of a function
-  /// template.
-  ArrayRef<TemplateArgument> getInjectedTemplateArgs();
-
   /// Return whether this function template is an abbreviated function template,
   /// e.g. `void foo(auto x)` or `template<typename T> void foo(auto x)`
   bool isAbbreviated() const {
     // Since the invented template parameters generated from 'auto' parameters
     // are either appended to the end of the explicit template parameter list or
     // form a new template parameter list, we can simply observe the last
     // parameter to determine if such a thing happened.
     const TemplateParameterList *TPL = getTemplateParameters();

clang/include/clang/Sema/Sema.h

enum TemplateParameterListEqualKind {
     /// \code
     /// template<template<int Value> class Metafun> struct X;
     /// template<int Value> struct integer_c;
     /// X<integer_c> xic;
     /// \endcode
     TPL_TemplateTemplateArgumentMatch
   };
 
-  bool TemplateParameterListsAreEqual(TemplateParameterList *New,
-                                      TemplateParameterList *Old,
-                                      bool Complain,
-                                      TemplateParameterListEqualKind Kind,
-                                      SourceLocation TemplateArgLoc
-                                        = SourceLocation());
+  bool TemplateParameterListsAreEqual(
+      TemplateParameterList *New, TemplateParameterList *Old, bool Complain,
+      SourceLocation TemplateArgLoc = SourceLocation(),
+      bool PartialOrdering = false);
 
   bool CheckTemplateDeclScope(Scope *S, TemplateParameterList *TemplateParams);
 
   /// Called when the parser has parsed a C++ typename
   /// specifier, e.g., "typename T::type".
   ///
   /// \param S The scope in which this typename type occurs.
   /// \param TypenameLoc the location of the 'typename' keyword

 
   bool DeduceFunctionTypeFromReturnExpr(FunctionDecl *FD,
                                         SourceLocation ReturnLoc,
                                         Expr *&RetExpr, const AutoType *AT);
 
   FunctionTemplateDecl *getMoreSpecializedTemplate(
       FunctionTemplateDecl *FT1, FunctionTemplateDecl *FT2, SourceLocation Loc,
       TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1,
-      unsigned NumCallArguments2, bool Reversed = false,
-      bool AllowOrderingByConstraints = true);
+      unsigned NumCallArguments2, bool Reversed = false);
   UnresolvedSetIterator
   getMostSpecialized(UnresolvedSetIterator SBegin, UnresolvedSetIterator SEnd,
                      TemplateSpecCandidateSet &FailedCandidates,
                      SourceLocation Loc,
                      const PartialDiagnostic &NoneDiag,
                      const PartialDiagnostic &AmbigDiag,
                      const PartialDiagnostic &CandidateDiag,
                      bool Complain = true, QualType TargetType = QualType());

clang/lib/AST/DeclTemplate.cpp

assert(SETraits::getDecl(Existing)->isCanonicalDecl() &&
            "non-canonical specialization?");
   }
 
   if (ASTMutationListener *L = getASTMutationListener())
     L->AddedCXXTemplateSpecialization(cast<Derived>(this),
                                       SETraits::getDecl(Entry));
 }
 
+ArrayRef<TemplateArgument> RedeclarableTemplateDecl::getInjectedTemplateArgs() {
+  TemplateParameterList *Params = getTemplateParameters();
+  auto *CommonPtr = getCommonPtr();
+  if (!CommonPtr->InjectedArgs) {
+    auto &Context = getASTContext();
+    SmallVector<TemplateArgument, 16> TemplateArgs;
+    Context.getInjectedTemplateArgs(Params, TemplateArgs);
+    CommonPtr->InjectedArgs =
+        new (Context) TemplateArgument[TemplateArgs.size()];
+    std::copy(TemplateArgs.begin(), TemplateArgs.end(),
+              CommonPtr->InjectedArgs);
+  }
+
+  return llvm::makeArrayRef(CommonPtr->InjectedArgs, Params->size());
+}
+
 //===----------------------------------------------------------------------===//
 // FunctionTemplateDecl Implementation
 //===----------------------------------------------------------------------===//
 
 FunctionTemplateDecl *
 FunctionTemplateDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L,
                              DeclarationName Name,
                              TemplateParameterList *Params, NamedDecl *Decl) {

 }
 
 void FunctionTemplateDecl::addSpecialization(
       FunctionTemplateSpecializationInfo *Info, void *InsertPos) {
   addSpecializationImpl<FunctionTemplateDecl>(getSpecializations(), Info,
                                               InsertPos);
 }
 
-ArrayRef<TemplateArgument> FunctionTemplateDecl::getInjectedTemplateArgs() {
-  TemplateParameterList *Params = getTemplateParameters();
-  Common *CommonPtr = getCommonPtr();
-  if (!CommonPtr->InjectedArgs) {
-    auto &Context = getASTContext();
-    SmallVector<TemplateArgument, 16> TemplateArgs;
-    Context.getInjectedTemplateArgs(Params, TemplateArgs);
-    CommonPtr->InjectedArgs =
-        new (Context) TemplateArgument[TemplateArgs.size()];
-    std::copy(TemplateArgs.begin(), TemplateArgs.end(),
-              CommonPtr->InjectedArgs);
-  }
-
-  return llvm::makeArrayRef(CommonPtr->InjectedArgs, Params->size());
-}
-
 void FunctionTemplateDecl::mergePrevDecl(FunctionTemplateDecl *Prev) {
   using Base = RedeclarableTemplateDecl;
 
   // If we haven't created a common pointer yet, then it can just be created
   // with the usual method.
   if (!Base::Common)
     return;
 

clang/lib/Sema/SemaOverload.cpp

for (unsigned I = 0; I != NumParams; ++I) {
     if (!Context.hasSameUnqualifiedType(T1, T2))
       return false;
   }
   return true;
 }
 
 /// We're allowed to use constraints partial ordering only if the candidates
 /// have the same parameter types:
-/// [temp.func.order]p6.2.2 [...] or if the function parameters that
-/// positionally correspond between the two templates are not of the same type,
-/// neither template is more specialized than the other.
 /// [over.match.best]p2.6
 /// F1 and F2 are non-template functions with the same parameter-type-lists,
 /// and F1 is more constrained than F2 [...]
-static bool canCompareFunctionConstraints(Sema &S,
+static bool sameFunctionParameterTypeLists(Sema &S,
                                           const OverloadCandidate &Cand1,
                                           const OverloadCandidate &Cand2) {
-  // FIXME: Per P2113R0 we also need to compare the template parameter lists
-  // when comparing template functions. 
-  if (Cand1.Function && Cand2.Function && Cand1.Function->hasPrototype() &&
-      Cand2.Function->hasPrototype()) {
+  if (Cand1.Function && Cand2.Function) {
     auto *PT1 = cast<FunctionProtoType>(Cand1.Function->getFunctionType());
     auto *PT2 = cast<FunctionProtoType>(Cand2.Function->getFunctionType());
     if (PT1->getNumParams() == PT2->getNumParams() &&
         PT1->isVariadic() == PT2->isVariadic() &&
         S.FunctionParamTypesAreEqual(PT1, PT2, nullptr,
                                      Cand1.isReversed() ^ Cand2.isReversed()))
       return true;
   }
bool clang::isBetterOverloadCandidate(
   //      if not that,
   if (Cand1IsSpecialization && Cand2IsSpecialization) {
     if (FunctionTemplateDecl *BetterTemplate = S.getMoreSpecializedTemplate(
             Cand1.Function->getPrimaryTemplate(),
             Cand2.Function->getPrimaryTemplate(), Loc,
             isa<CXXConversionDecl>(Cand1.Function) ? TPOC_Conversion
                                                    : TPOC_Call,
             Cand1.ExplicitCallArguments, Cand2.ExplicitCallArguments,
-            Cand1.isReversed() ^ Cand2.isReversed(),
-            canCompareFunctionConstraints(S, Cand1, Cand2)))
+            Cand1.isReversed() ^ Cand2.isReversed()))
       return BetterTemplate == Cand1.Function->getPrimaryTemplate();
   }
 
   //   -— F1 and F2 are non-template functions with the same
   //      parameter-type-lists, and F1 is more constrained than F2 [...],
   if (!Cand1IsSpecialization && !Cand2IsSpecialization &&
-      canCompareFunctionConstraints(S, Cand1, Cand2)) {
+      sameFunctionParameterTypeLists(S, Cand1, Cand2)) {
     Expr *RC1 = Cand1.Function->getTrailingRequiresClause();
     Expr *RC2 = Cand2.Function->getTrailingRequiresClause();
     if (RC1 && RC2) {
       bool AtLeastAsConstrained1, AtLeastAsConstrained2;
       if (S.IsAtLeastAsConstrained(Cand1.Function, {RC1}, Cand2.Function, {RC2},
                                    AtLeastAsConstrained1) ||
           S.IsAtLeastAsConstrained(Cand2.Function, {RC2}, Cand1.Function, {RC1},
                                    AtLeastAsConstrained2))

clang/lib/Sema/SemaTemplate.cpp

Diag(NTTP->getTypeSourceInfo()->getTypeLoc().getBeginLoc(),
        << NTTP->getTypeSourceInfo()->getTypeLoc().getSourceRange();
     return true;
   }
   // FIXME: Concepts: This should be the type of the placeholder, but this is
   // unclear in the wording right now.
   DeclRefExpr *Ref =
       BuildDeclRefExpr(NTTP, NTTP->getType(), VK_PRValue, NTTP->getLocation());
   if (!Ref)
     return true;
   ExprResult ImmediatelyDeclaredConstraint = formImmediatelyDeclaredConstraint(
       *this, TL.getNestedNameSpecifierLoc(), TL.getConceptNameInfo(),
       TL.getNamedConcept(), TL.getLAngleLoc(), TL.getRAngleLoc(),
       BuildDecltypeType(Ref), NTTP->getLocation(),
       [&](TemplateArgumentListInfo &ConstraintArgs) {
         for (unsigned I = 0, C = TL.getNumArgs(); I != C; ++I)
           ConstraintArgs.addArgument(TL.getArgLoc(I));
       },
if (TemplateParameterListsAreEqual(
         // If the argument has no associated constraints, then the parameter is
         // definitely at least as specialized as the argument.
         // Otherwise - we need a more thorough check.
         !Template->hasAssociatedConstraints())
       return false;
 
     if (isTemplateTemplateParameterAtLeastAsSpecializedAs(Params, Template,
                                                           Arg.getLocation())) {
-      // C++2a[temp.func.order]p2
+      // P2113
+      // C++20[temp.func.order]p2
       //   [...] If both deductions succeed, the partial ordering selects the
-      //   more constrained template as described by the rules in
-      //   [temp.constr.order].
+      // more constrained template (if one exists) as determined below.
       SmallVector<const Expr *, 3> ParamsAC, TemplateAC;
       Params->getAssociatedConstraints(ParamsAC);
       // C++2a[temp.arg.template]p3
       //   [...] In this comparison, if P is unconstrained, the constraints on A
       //   are not considered.
       if (ParamsAC.empty())
         return false;
       Template->getAssociatedConstraints(TemplateAC);
E = CStyleCastExpr::Create(Context, OrigT, VK_PRValue, CK_IntegralCast, E,
                                Context.getTrivialTypeSourceInfo(OrigT, Loc),
                                Loc, Loc);
   }
 
   return E;
 }
 
 /// Match two template parameters within template parameter lists.
-static bool MatchTemplateParameterKind(Sema &S, NamedDecl *New, NamedDecl *Old,
-                                       bool Complain,
-                                     Sema::TemplateParameterListEqualKind Kind,
-                                       SourceLocation TemplateArgLoc) {
+static bool MatchTemplateParameterKind(
+    Sema &S, NamedDecl *New, NamedDecl *Old, bool Complain,
+    Sema::TemplateParameterListEqualKind Kind, SourceLocation TemplateArgLoc,
+    bool PartialOrdering) {
   // Check the actual kind (type, non-type, template).
   if (Old->getKind() != New->getKind()) {
     if (Complain) {
       unsigned NextDiag = diag::err_template_param_different_kind;
       if (TemplateArgLoc.isValid()) {
         S.Diag(TemplateArgLoc, diag::err_template_arg_template_params_mismatch);
         NextDiag = diag::note_template_param_different_kind;
       }
else if (TemplateTemplateParmDecl *OldTTP
                                     = dyn_cast<TemplateTemplateParmDecl>(Old)) {
     TemplateTemplateParmDecl *NewTTP = cast<TemplateTemplateParmDecl>(New);
     if (!S.TemplateParameterListsAreEqual(NewTTP->getTemplateParameters(),
                                           OldTTP->getTemplateParameters(),
                                           Complain,
                                         (Kind == Sema::TPL_TemplateMatch
                                            ? Sema::TPL_TemplateTemplateParmMatch
                                            : Kind),
-                                          TemplateArgLoc))
+                                          TemplateArgLoc, PartialOrdering))
       return false;
-  } else if (Kind != Sema::TPL_TemplateTemplateArgumentMatch) {
+  } else if (!PartialOrdering &&
+             Kind != Sema::TPL_TemplateTemplateArgumentMatch) {
     const Expr *NewC = nullptr, *OldC = nullptr;
     if (const auto *TC = cast<TemplateTypeParmDecl>(New)->getTypeConstraint())
       NewC = TC->getImmediatelyDeclaredConstraint();
     if (const auto *TC = cast<TemplateTypeParmDecl>(Old)->getTypeConstraint())
       OldC = TC->getImmediatelyDeclaredConstraint();
 
     auto Diagnose = [&] {
       S.Diag(NewC ? NewC->getBeginLoc() : New->getBeginLoc(),
S.Diag(New->getTemplateLoc(), NextDiag)
     << SourceRange(New->getTemplateLoc(), New->getRAngleLoc());
   S.Diag(Old->getTemplateLoc(), diag::note_template_prev_declaration)
     << (Kind != Sema::TPL_TemplateMatch)
     << SourceRange(Old->getTemplateLoc(), Old->getRAngleLoc());
 }
 
 /// Determine whether the given template parameter lists are
 /// equivalent.
 ///
 /// \param New  The new template parameter list, typically written in the
 /// source code as part of a new template declaration.
 ///
 /// \param Old  The old template parameter list, typically found via
 /// name lookup of the template declared with this template parameter
 /// list.
 ///
 /// \param Complain  If true, this routine will produce a diagnostic if

 ///
 /// \returns True if the template parameter lists are equal, false
 /// otherwise.
 bool
 Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
                                      TemplateParameterList *Old,
                                      bool Complain,
                                      TemplateParameterListEqualKind Kind,
-                                     SourceLocation TemplateArgLoc) {
+                                     SourceLocation TemplateArgLoc,
+                                     bool PartialOrdering) {
   if (Old->size() != New->size() && Kind != TPL_TemplateTemplateArgumentMatch) {
     if (Complain)
       DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
                                                  TemplateArgLoc);
 
     return false;
   }
 
if (Kind != TPL_TemplateTemplateArgumentMatch ||
       if (NewParm == NewParmEnd) {
         if (Complain)
           DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
                                                      TemplateArgLoc);
 
         return false;
       }
 
-      if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain,
-                                      Kind, TemplateArgLoc))
+      if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain, Kind,
+                                      TemplateArgLoc, PartialOrdering))
         return false;
 
       ++NewParm;
       continue;
     }
 
     // C++0x [temp.arg.template]p3:
     //   [...] When P's template- parameter-list contains a template parameter
     //   pack (14.5.3), the template parameter pack will match zero or more
     //   template parameters or template parameter packs in the
     //   template-parameter-list of A with the same type and form as the
     //   template parameter pack in P (ignoring whether those template
     //   parameters are template parameter packs).
     for (; NewParm != NewParmEnd; ++NewParm) {
-      if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain,
-                                      Kind, TemplateArgLoc))
+      if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain, Kind,
+                                      TemplateArgLoc, PartialOrdering))
         return false;
     }
   }
 
   // Make sure we exhausted all of the arguments.
   if (NewParm != NewParmEnd) {
     if (Complain)
       DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
                                                  TemplateArgLoc);
 
     return false;
   }
 
-  if (Kind != TPL_TemplateTemplateArgumentMatch) {
+  if (!PartialOrdering && Kind != TPL_TemplateTemplateArgumentMatch) {
     const Expr *NewRC = New->getRequiresClause();
     const Expr *OldRC = Old->getRequiresClause();
 
     auto Diagnose = [&] {
       Diag(NewRC ? NewRC->getBeginLoc() : New->getTemplateLoc(),
            diag::err_template_different_requires_clause);
       Diag(OldRC ? OldRC->getBeginLoc() : Old->getTemplateLoc(),
            diag::note_template_prev_declaration) << /*declaration*/0;

clang/lib/Sema/SemaTemplateDeduction.cpp

static bool isAtLeastAsSpecializedAs(Sema &S,
   for (; ArgIdx != NumArgs; ++ArgIdx)
     // If this argument had no value deduced but was used in one of the types
     // used for partial ordering, then deduction fails.
     if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
       return false;
 
   return true;
 }
 
 /// Returns the more specialized function template according
 /// to the rules of function template partial ordering (C++ [temp.func.order]).
 ///
 /// \param FT1 the first function template
 ///
 /// \param FT2 the second function template
 ///
 /// \param TPOC the context in which we are performing partial ordering of
 /// function templates.
 ///
 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
 /// only when \c TPOC is \c TPOC_Call.
 ///
 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
 /// only when \c TPOC is \c TPOC_Call.
 ///
 /// \param Reversed If \c true, exactly one of FT1 and FT2 is an overload
 /// candidate with a reversed parameter order. In this case, the corresponding
 /// P/A pairs between FT1 and FT2 are reversed.
 ///
 /// \param AllowOrderingByConstraints If \c is false, don't check whether one
 /// of the templates is more constrained than the other. Default is true.
 ///
 /// \returns the more specialized function template. If neither
 /// template is more specialized, returns NULL.
 FunctionTemplateDecl *Sema::getMoreSpecializedTemplate(
     FunctionTemplateDecl *FT1, FunctionTemplateDecl *FT2, SourceLocation Loc,
     TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1,
-    unsigned NumCallArguments2, bool Reversed,
-    bool AllowOrderingByConstraints) {
-
-  auto JudgeByConstraints = [&]() -> FunctionTemplateDecl * {
-    if (!AllowOrderingByConstraints)
-      return nullptr;
-    llvm::SmallVector<const Expr *, 3> AC1, AC2;
-    FT1->getAssociatedConstraints(AC1);
-    FT2->getAssociatedConstraints(AC2);
-    bool AtLeastAsConstrained1, AtLeastAsConstrained2;
-    if (IsAtLeastAsConstrained(FT1, AC1, FT2, AC2, AtLeastAsConstrained1))
-      return nullptr;
-    if (IsAtLeastAsConstrained(FT2, AC2, FT1, AC1, AtLeastAsConstrained2))
-      return nullptr;
-    if (AtLeastAsConstrained1 == AtLeastAsConstrained2)
-      return nullptr;
-    return AtLeastAsConstrained1 ? FT1 : FT2;
-  };
+    unsigned NumCallArguments2, bool Reversed) {
 
   bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
                                           NumCallArguments1, Reversed);
   bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
                                           NumCallArguments2, Reversed);
 
+  // C++ [temp.deduct.partial]p10:
+  //   F is more specialized than G if F is at least as specialized as G and G
+  //   is not at least as specialized as F.
   if (Better1 != Better2) // We have a clear winner
     return Better1 ? FT1 : FT2;
 
   if (!Better1 && !Better2) // Neither is better than the other
-    return JudgeByConstraints();
+    return nullptr;
+
+  TemplateParameterList *TPL1 = FT1->getTemplateParameters();
+  TemplateParameterList *TPL2 = FT2->getTemplateParameters();
+  FunctionDecl *FD1 = FT1->getTemplatedDecl();
+  FunctionDecl *FD2 = FT2->getTemplatedDecl();
 
   // C++ [temp.deduct.partial]p11:
   //   ... and if G has a trailing function parameter pack for which F does not
   //   have a corresponding parameter, and if F does not have a trailing
   //   function parameter pack, then F is more specialized than G.
-  FunctionDecl *FD1 = FT1->getTemplatedDecl();
-  FunctionDecl *FD2 = FT2->getTemplatedDecl();
   unsigned NumParams1 = FD1->getNumParams();
   unsigned NumParams2 = FD2->getNumParams();
   bool Variadic1 = NumParams1 && FD1->parameters().back()->isParameterPack();
   bool Variadic2 = NumParams2 && FD2->parameters().back()->isParameterPack();
   if (Variadic1 != Variadic2) {
     if (Variadic1 && NumParams1 > NumParams2)
       return FT2;
     if (Variadic2 && NumParams2 > NumParams1)
       return FT1;
   }
 
-  return JudgeByConstraints();
+  if (!Context.getLangOpts().CPlusPlus20 || isa<CXXDeductionGuideDecl>(FD1) ||
+      isa<CXXDeductionGuideDecl>(FD2))
+    return nullptr;
+
+  // Match GCC on not implementing [temp.func.order]p6.2.1.
+
+  // C++20 [temp.func.order]p6:
+  //   If deduction against the other template succeeds for both transformed
+  //   templates, constraints can be considered as follows:
+
+  // C++20 [temp.func.order]p6.1:
+  //   If their template-parameter-lists (possibly including template-parameters
+  //   invented for an abbreviated function template ([dcl.fct])) or function
+  //   parameter lists differ in length, neither template is more specialized
+  //   than the other.
+  if (TPL1->size() != TPL2->size() || NumParams1 != NumParams2)
+    return nullptr;
+
+  // C++20 [temp.func.order]p6.2.2:
+  //   Otherwise, if the corresponding template-parameters of the
+  //   template-parameter-lists are not equivalent ([temp.over.link]) or if the
+  //   function parameters that positionally correspond between the two
+  //   templates are not of the same type, neither template is more specialized
+  //   than the other.
+  if (!TemplateParameterListsAreEqual(
+          TPL1, TPL2, false, Sema::TPL_TemplateMatch, SourceLocation(), true))
+    return nullptr;
+
+  {
+    // C++20 [temp.func.order]p6.3:
+    //   Otherwise, if the context in which the partial ordering is done is
+    //   that of a call to a conversion function and the return types of the
+    //   templates are not the same, then neither template is more specialized
+    //   than the other.
+
+    // The "same type" check is performed by comparing FD1 with a FT2
+    // specialization that instantiated by FT1's injected template args.
+    ArrayRef<TemplateArgument> TemplateArgs = FT1->getInjectedTemplateArgs();
+    TemplateArgumentList TAL(TemplateArgumentList::OnStack, TemplateArgs);
+    FunctionDecl *FD2Inst = InstantiateFunctionDeclaration(FT2, &TAL, Loc);
+    for (unsigned i = 0; i < NumParams1; ++i)
+      if (FD1->getParamDecl(i)->getType().getCanonicalType() !=
+          FD2Inst->getParamDecl(i)->getType().getCanonicalType())
+        return nullptr;
+
+    if (TPOC == TPOC_Conversion &&
+        FD1->getReturnType().getCanonicalType() !=
+            FD2Inst->getReturnType().getCanonicalType())
+      return nullptr;
+  }
+
+  llvm::SmallVector<const Expr *, 3> AC1, AC2;
+  FT1->getAssociatedConstraints(AC1);
+  FT2->getAssociatedConstraints(AC2);
+  bool AtLeastAsConstrained1, AtLeastAsConstrained2;
+  if (IsAtLeastAsConstrained(FT1, AC1, FT2, AC2, AtLeastAsConstrained1))
+    return nullptr;
+  if (IsAtLeastAsConstrained(FT2, AC2, FT1, AC1, AtLeastAsConstrained2))
+    return nullptr;
+  if (AtLeastAsConstrained1 == AtLeastAsConstrained2)
+    return nullptr;
+  return AtLeastAsConstrained1 ? FT1 : FT2;
 }
 
 /// Determine if the two templates are equivalent.
 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
   if (T1 == T2)
     return true;
 
   if (!T1 || !T2)
T2 *operator()(T1 *, T2 *P2) {
     return P2;
   }
   template <typename T1, typename T2,
             std::enable_if_t<!std::is_same<T1, T2>::value, bool> = true>
   T1 *operator()(T1 *, T2 *) {
     return nullptr;
   }
 };
+
+// The assumption is that two template argument lists have the same size.
+struct TemplateArgumentListAreEqual {
+  Sema &S;
+  TemplateArgumentListAreEqual(Sema &S) : S(S) {}
+
+  template <typename T1, typename T2,
+            std::enable_if_t<std::is_same<T1, T2>::value, bool> = true>
+  bool operator()(T1 *PS1, T2 *PS2) {
+    // Compare two Template Argument lists using
+    // AtomicConstraint::hasMatchingParameterMapping.
+    AtomicConstraint Atomic1(S, nullptr);
+    Atomic1.ParameterMapping.emplace(
+        PS1->getTemplateArgsAsWritten()->arguments());
+    AtomicConstraint Atomic2(S, nullptr);
+    Atomic2.ParameterMapping.emplace(
+        PS2->getTemplateArgsAsWritten()->arguments());
+    return Atomic1.hasMatchingParameterMapping(S.getASTContext(), Atomic2);
+  }
+
+  template <typename T1, typename T2,
+            std::enable_if_t<!std::is_same<T1, T2>::value, bool> = true>
+  bool operator()(T1 *Spec, T2 *Primary) {
+    SmallVector<TemplateArgumentLoc, 16> Args;
+    for (const TemplateArgument &TA : Primary->getInjectedTemplateArgs()) {
+      // A injected template argument for a parameter pack is
+      // TemplateArgument::Pack. However, the TemplateArgsAsWritten
+      // represents a template argument for a parameter pack as
+      // TemplateArgument::Type with PackExpansionType. Transform the former
+      // to the same TemplateArgument kind as the latter.
+      if (TA.getKind() == TemplateArgument::Pack) {
+        assert(TA.pack_size() == 1);
+        Args.emplace_back(*TA.pack_begin(), TemplateArgumentLocInfo());
+      } else {
+        Args.emplace_back(TA, TemplateArgumentLocInfo());
+      }
+    }
+
+    AtomicConstraint Atomic1(S, nullptr);
+    Atomic1.ParameterMapping.emplace(Args);
+    AtomicConstraint Atomic2(S, nullptr);
+    Atomic2.ParameterMapping.emplace(
+        Spec->getTemplateArgsAsWritten()->arguments());
+    return Atomic1.hasMatchingParameterMapping(S.getASTContext(), Atomic2);
+  }
+};
 } // namespace
 
 /// Returns the more specialized template specialization between T1/P1 and
 /// T2/P2.
 /// - If IsMoreSpecialThanPrimaryCheck is true, T1/P1 is the partial
 ///   specialization and T2/P2 is the primary template.
 /// - otherwise, both T1/P1 and T2/P2 are the partial specialization.
 ///
 /// \param T1 the type of the first template partial specialization
 ///
 /// \param T2 if IsMoreSpecialThanPrimaryCheck is true, the type of the second
 ///           template partial specialization; otherwise, the type of the
 ///           primary template.
 ///
 /// \param P1 the first template partial specialization
getMoreSpecialized(Sema &S, QualType T1, QualType T2, TemplateLikeDecl *P1,
   bool Better1 = isAtLeastAsSpecializedAs(S, T1, T2, P2, Info);
   if (IsMoreSpecialThanPrimaryCheck && !Better1)
     return nullptr;
 
   bool Better2 = isAtLeastAsSpecializedAs(S, T2, T1, P1, Info);
   if (IsMoreSpecialThanPrimaryCheck && !Better2)
     return P1;
 
+  // C++ [temp.deduct.partial]p10:
+  //   F is more specialized than G if F is at least as specialized as G and G
+  //   is not at least as specialized as F.
+  if (Better1 != Better2) // We have a clear winner
+    return Better1 ? P1 : GetP2()(P1, P2);
+
   if (!Better1 && !Better2)
     return nullptr;
 
-  if (Better1 && Better2) {
-    bool ClangABICompat14 = S.Context.getLangOpts().getClangABICompat() <=
-                            LangOptions::ClangABI::Ver14;
-    if (!ClangABICompat14) {
-      // Consider this a fix for CWG1432. Similar to the fix for CWG1395.
-      auto *TST1 = T1->castAs<TemplateSpecializationType>();
-      auto *TST2 = T2->castAs<TemplateSpecializationType>();
-      if (TST1->getNumArgs()) {
-        const TemplateArgument &TA1 = TST1->template_arguments().back();
-        if (TA1.getKind() == TemplateArgument::Pack) {
-          assert(TST1->getNumArgs() == TST2->getNumArgs());
-          const TemplateArgument &TA2 = TST2->template_arguments().back();
-          assert(TA2.getKind() == TemplateArgument::Pack);
-          unsigned PackSize1 = TA1.pack_size();
-          unsigned PackSize2 = TA2.pack_size();
-          bool IsPackExpansion1 =
-              PackSize1 && TA1.pack_elements().back().isPackExpansion();
-          bool IsPackExpansion2 =
-              PackSize2 && TA2.pack_elements().back().isPackExpansion();
-          if (PackSize1 != PackSize2 && IsPackExpansion1 != IsPackExpansion2) {
-            if (PackSize1 > PackSize2 && IsPackExpansion1)
-              return GetP2()(P1, P2);
-            if (PackSize1 < PackSize2 && IsPackExpansion2)
-              return P1;
-          }
-        }
-      }
-    }
+  TemplateParameterList *TPL1 = P1->getTemplateParameters();
+  TemplateParameterList *TPL2 = P2->getTemplateParameters();
+
 
-    llvm::SmallVector<const Expr *, 3> AC1, AC2;
-    P1->getAssociatedConstraints(AC1);
-    P2->getAssociatedConstraints(AC2);
-    bool AtLeastAsConstrained1, AtLeastAsConstrained2;
-    if (S.IsAtLeastAsConstrained(P1, AC1, P2, AC2, AtLeastAsConstrained1) ||
-        (IsMoreSpecialThanPrimaryCheck && !AtLeastAsConstrained1))
-      return nullptr;
-    if (S.IsAtLeastAsConstrained(P2, AC2, P1, AC1, AtLeastAsConstrained2))
-      return nullptr;
-    if (AtLeastAsConstrained1 == AtLeastAsConstrained2)
-      return nullptr;
-    return AtLeastAsConstrained1 ? P1 : GetP2()(P1, P2);
-  }
+  if (!S.Context.getLangOpts().CPlusPlus20)
+    return nullptr;
+
+  // Match GCC on not implementing [temp.func.order]p6.2.1.
+
+  // C++20 [temp.func.order]p6:
+  //   If deduction against the other template succeeds for both transformed
+  //   templates, constraints can be considered as follows:
+
+  if (TPL1->size() != TPL2->size())
+    return nullptr;
+
+  // C++20 [temp.func.order]p6.2.2:
+  // Otherwise, if the corresponding template-parameters of the
+  // template-parameter-lists are not equivalent ([temp.over.link]) or if the
+  // function parameters that positionally correspond between the two
+  // templates are not of the same type, neither template is more specialized
+  // than the other.
+  if (!S.TemplateParameterListsAreEqual(
+          TPL1, TPL2, false, Sema::TPL_TemplateMatch, SourceLocation(), true))
+    return nullptr;
+
+  if (!TemplateArgumentListAreEqual(S)(P1, P2))
+    return nullptr;
+
 
-  return Better1 ? P1 : GetP2()(P1, P2);
-}
-
 /// Returns the more specialized class template partial specialization
 /// according to the rules of partial ordering of class template partial
 /// specializations (C++ [temp.class.order]).
 ///
 /// \param PS1 the first class template partial specialization
 ///
 /// \param PS2 the second class template partial specialization
 ///
QualType PT2 = Context.getTemplateSpecializationType(
       CanonTemplate, PS2->getTemplateArgs().asArray());
 
   TemplateDeductionInfo Info(Loc);
   return getMoreSpecialized(*this, PT1, PT2, PS1, PS2, Info);
 }
 
 bool Sema::isMoreSpecializedThanPrimary(
     VarTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) {
-  TemplateDecl *Primary = Spec->getSpecializedTemplate();
-  // FIXME: Cache the injected template arguments rather than recomputing
-  // them for each partial specialization.
-  SmallVector<TemplateArgument, 8> PrimaryArgs;
-  Context.getInjectedTemplateArgs(Primary->getTemplateParameters(),
-                                  PrimaryArgs);
-
+  VarTemplateDecl *Primary = Spec->getSpecializedTemplate();
   TemplateName CanonTemplate =
       Context.getCanonicalTemplateName(TemplateName(Primary));
   QualType PrimaryT = Context.getTemplateSpecializationType(
-      CanonTemplate, PrimaryArgs);
+      CanonTemplate, Primary->getInjectedTemplateArgs());
   QualType PartialT = Context.getTemplateSpecializationType(
       CanonTemplate, Spec->getTemplateArgs().asArray());
 
   VarTemplatePartialSpecializationDecl *MaybeSpec =
       getMoreSpecialized(*this, PartialT, PrimaryT, Spec, Primary, Info);
   if (MaybeSpec)
     Info.clearSFINAEDiagnostic();
   return MaybeSpec;

clang/lib/Sema/SemaTemplateInstantiate.cpp

if (T->isParameterPack()) {
 
       Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
       PackIndex = getSema().ArgumentPackSubstitutionIndex;
     }
 
     assert(Arg.getKind() == TemplateArgument::Type &&
            "Template argument kind mismatch");
 
-    QualType Replacement = Arg.getAsType();
+    QualType Replacement = SemaRef.Context.getCanonicalType(Arg.getAsType());
 
     // TODO: only do this uniquing once, at the start of instantiation.
     QualType Result = getSema().Context.getSubstTemplateTypeParmType(
         T, Replacement, PackIndex);
     SubstTemplateTypeParmTypeLoc NewTL
       = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
     NewTL.setNameLoc(TL.getNameLoc());
     return Result;

clang/test/CXX/over/over.match/over.match.best/p1-2a.cpp

namespace non_template
   // expected-note@-1 {{candidate function}}
   // expected-note@-2 {{similar constraint expression here}}
 
   static_assert(is_same_v<decltype(foo<int>()), int>);
   static_assert(is_same_v<decltype(baz<int>()), int>); // expected-error {{call to 'baz' is ambiguous}}
   static_assert(is_same_v<decltype(bar<int>()), void>); // expected-error {{call to 'bar' is ambiguous}}
 
   template<typename T>
-  constexpr int goo(int a) requires AtLeast2<int> && true {
+  constexpr int goo(int a) requires AtLeast2<int> && true { // expected-note {{candidate function}}
     return 1;
   }
 
   template<typename T>
-  constexpr int goo(const int b) requires AtLeast2<int> {
+  constexpr int goo(const int b) requires AtLeast2<int> { // expected-note {{candidate function}}
     return 2;
   }
 
-  // Only trailing requires clauses of redeclarations are compared for overload resolution.
+  // [temp.func.order] p5
+  //   Since, in a call context, such type deduction considers only parameters
+  //   for which there are explicit call arguments, some parameters are ignored
+  //   (namely, function parameter packs, parameters with default arguments, and
+  //   ellipsis parameters).
   template<typename T>
-  constexpr int doo(int a, ...) requires AtLeast2<int> && true { // expected-note {{candidate function}}
+  constexpr int doo(int a, ...) requires AtLeast2<int> && true {
     return 1;
   }
 
   template<typename T>
-  constexpr int doo(int b) requires AtLeast2<int> { // expected-note {{candidate function}}
+  constexpr int doo(int b) requires AtLeast2<int> {
     return 2;
   }
 
-  static_assert(goo<int>(1) == 1);
-  static_assert(doo<int>(2) == 1); // expected-error {{call to 'doo' is ambiguous}}
+  // By temp.func.order-6.2.2, this is ambiguous because parameter a and b have different types.
+  static_assert(goo<int>(1) == 1); // expected-error {{call to 'goo' is ambiguous}}
+  static_assert(doo<int>(2) == 1);
 }

clang/test/CXX/temp/temp.decls/temp.fct/temp.func.order/p6.cpp

 // RUN: %clang_cc1 -fsyntax-only -verify -std=c++20 %s
 
-struct A;
-struct B;
-
 template <typename> constexpr bool True = true;
 template <typename T> concept C = True<T>;
+template <typename T> concept D = C<T> && sizeof(T)>2;
+template <typename T> concept E = D<T> && alignof(T)>1;
+
+struct A {};
+template <typename, int, A, typename...> struct S {};
+template <typename T, typename U> struct X {};
+
+namespace p6 {
+
+struct B;
 
 void f(C auto &, auto &) = delete;
 template <C Q> void f(Q &, C auto &);
 
 void g(struct A *ap, struct B *bp) {
   f(*ap, *bp);
 }
 
-template <typename T, typename U> struct X {};
-
 template <typename T, C U, typename V> bool operator==(X<T, U>, V) = delete;
-template <C T, C U, C V>               bool operator==(T, X<U, V>);
+template <C U,        C V, C T>        bool operator==(X<U, V>, T);
 
 bool h() {
   return X<void *, int>{} == 0;
 }
 
+template<C T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> void foo(T, U<T,W,S,Z...>) = delete;
+template<D T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> void foo(T, U<T,W,S,Z...>) = delete;
+template<E T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> void foo(T, U<T,W,S,Z...>);
+
+void bar(S<int,1,A{},int> s) {
+  foo(0,s);
+}
+
+} // namespace p6
+
+namespace TestConversionFunction {
+struct Y {
+  template<C        T, typename U> operator X<T,U>(); // expected-note {{candidate function [with T = int, U = int]}}
+  template<typename T, typename U> operator X<U,T>(); // expected-note {{candidate function [with T = int, U = int]}}
+};
+
+X<int,int> f() {
+  return Y{}; // expected-error {{conversion from 'Y' to 'X<int, int>' is ambiguous}}
+}
+}
+
+namespace ClassPartialSpecPartialOrdering {
+template<D T> struct Y { Y()=delete; }; // expected-note {{template is declared here}}
+template<C T> struct Y<T> {}; // expected-error {{class template partial specialization is not more specialized than the primary template}}
+
+template<C T> struct B    { B()=delete; };
+template<D T> struct B<T> { B()=delete; };
+template<E T> struct B<T> {};
+
+template<C T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> struct Some { Some()=delete; };
+template<D T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> struct Some<T,W,S,U,Z...> { Some()=delete; };
+template<E T, int W, A S, template<typename,int,A,typename...> class U, typename... Z> struct Some<T,W,S,U,Z...> {};
+
+void f() {
+  B<int> b;
+  Some<int,0,A{},S,int> c;
+}
+
+template<C T, C V> struct Z; // expected-note {{template is declared here}}
+template<D T, C V> struct Z<V, T>; // expected-error {{class template partial specialization is not more specialized than the primary template}}
+}
+
 namespace PR53640 {
 
 template <typename T>
 concept C = true;
 
 template <C T>
 void f(T t) {} // expected-note {{candidate function [with T = int]}}
 

clang/www/cxx_status.html

</tr>
         <td rowspan="1" class="partial" align="center">
           <details><summary>Partial</summary>
             <tt>typename</tt> not yet optional (depends on P0634R3).
           </details>
         </td>
       </tr>
       <tr>
         <td><a href="https://wg21.link/p2113r0">P2113R0</a></td>
-        <td rowspan="1" class="none" align="center">No</td>
+        <td rowspan="1" class="unreleased" align="center">Clang 16</td>
       </tr>
     <!-- Albuquerque papers -->
     <tr>
       <td>Range-based for statements with initializer</td>
       <td><a href="https://wg21.link/p0614r1">P0614R1</a></td>
       <td class="full" align="center">Clang 8</td>
     </tr>
     <tr>