This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by ychen on Jun 28 2022, 12:06 PM.

Details

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)

Diff Detail

Event Timeline

ychen created this revision.Jun 28 2022, 12:06 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 28 2022, 12:06 PM
ychen requested review of this revision.Jun 28 2022, 12:06 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 28 2022, 12:06 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript

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.

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 added a comment.Jun 28 2022, 1:11 PM

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 updated this revision to Diff 440789.Jun 28 2022, 3:14 PM
  • add release notes
  • update www-status
ychen added a reviewer: Restricted Project.Jun 28 2022, 3:33 PM
royjacobson requested changes to this revision.Jul 3 2022, 5:25 AM

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
173–174

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

clang/lib/Sema/SemaTemplate.cpp
8029

Consider adding

clang/lib/Sema/SemaTemplateDeduction.cpp
5154–5155

Curious, why was this removed?

This revision now requires changes to proceed.Jul 3 2022, 5:25 AM
ychen added inline comments.Jul 6 2022, 3:25 PM
clang/lib/Sema/SemaTemplateDeduction.cpp
5154–5155

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 added a comment.Jul 6 2022, 4:25 PM

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 marked an inline comment as done.Jul 18 2022, 10:59 PM

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.

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

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.

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 retitled this revision from [c++20] Implement P2113R0: Changes to the Partial Ordering of Constrained Functions to [C++20] Implement P2113R0: Changes to the Partial Ordering of Constrained Functions.Aug 12 2022, 3:00 PM
ychen edited the summary of this revision. (Show Details)
ychen updated this revision to Diff 452311.Aug 12 2022, 3:04 PM
  • Remove code for temp.func.order p6.2.1
  • Add missing handling for partial ordering of partial specialization
  • Add more tests
  • Rebase
ychen added a comment.Aug 12 2022, 3:08 PM

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 accepted this revision.Aug 13 2022, 2:27 PM

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
850–858
clang/lib/Sema/SemaTemplateDeduction.cpp
5174–5175

update docs here

5194

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?

5275

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
26

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?

This revision is now accepted and ready to land.Aug 13 2022, 2:27 PM
ychen updated this revision to Diff 452561.Aug 14 2022, 2:02 PM
ychen marked 3 inline comments as done.
  • address Roy's comments.
clang/lib/Sema/SemaTemplateDeduction.cpp
5194

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 marked an inline comment as done.Aug 14 2022, 2:02 PM

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 updated this revision to Diff 452579.Aug 14 2022, 6:24 PM
  • rebase
ychen added a comment.Aug 22 2022, 3:59 PM

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

ychen planned changes to this revision.Aug 24 2022, 11:35 PM

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 updated this revision to Diff 456528.Aug 29 2022, 8:16 PM
  • handle constrained placeholder [pack] types
This revision is now accepted and ready to land.Aug 29 2022, 8:16 PM
ychen requested review of this revision.Aug 29 2022, 8:23 PM
ychen added a comment.Aug 29 2022, 8:23 PM

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

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

clang/lib/Sema/SemaConcept.cpp
1111
clang/lib/Sema/SemaTemplateInstantiate.cpp
1838 ↗(On Diff #456528)

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 updated this revision to Diff 456743.Aug 30 2022, 11:54 AM
ychen marked an inline comment as done.
  • For function templates, compare canonical types of funtion parameters directly.

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

Thanks!

clang/lib/Sema/SemaTemplateInstantiate.cpp
1838 ↗(On Diff #456528)

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.

ychen edited the summary of this revision. (Show Details)Aug 30 2022, 12:05 PM

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 added inline comments.Sep 4 2022, 4:27 PM
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
1115

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
9790–9791

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
1268

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

clang/lib/Sema/SemaTemplateDeduction.cpp
5275–5276
5284–5285
ychen marked 4 inline comments as done.Sep 6 2022, 8:07 PM

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

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
9790–9791

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

clang/lib/Sema/SemaTemplate.cpp
1268

Agreed. Removed.

ychen marked an inline comment as done.Sep 6 2022, 8:08 PM

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
9790–9791

Yeah that makes the most sense :)

mizvekov added inline comments.Sep 13 2022, 9:19 AM
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 updated this revision to Diff 465543.Oct 5 2022, 1:46 PM
  • rebase
ychen updated this revision to Diff 465547.Oct 5 2022, 1:52 PM
  • rebase
ychen updated this revision to Diff 465549.Oct 5 2022, 1:56 PM
ychen added a comment.Oct 11 2022, 4:47 PM

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

mizvekov added inline comments.Oct 11 2022, 11:29 PM
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 updated this revision to Diff 467031.Oct 11 2022, 11:53 PM
  • remove dead code.

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

mizvekov added inline comments.Oct 12 2022, 12:36 AM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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.

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 edited the summary of this revision. (Show Details)Oct 13 2022, 1:58 PM

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 updated this revision to Diff 467845.Oct 14 2022, 11:04 AM
  • skip non-dependent NTTP comparison because they're equivalent (match GCC)
ychen added inline comments.Oct 14 2022, 12:59 PM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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 added inline comments.Oct 15 2022, 7:00 AM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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 added inline comments.Oct 15 2022, 7:19 AM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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 added inline comments.Oct 15 2022, 10:04 AM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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 added inline comments.Oct 15 2022, 10:13 AM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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 updated this revision to Diff 468286.Oct 17 2022, 12:12 PM
  • use getTemplateArgs
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

'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 added inline comments.Oct 17 2022, 1:02 PM
clang/lib/Sema/SemaTemplateDeduction.cpp
5516–5544

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.

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

ychen updated this revision to Diff 468602.Oct 18 2022, 9:55 AM
  • rebase

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

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

mizvekov accepted this revision.Oct 18 2022, 11:10 AM

LGTM, thanks!

This revision is now accepted and ready to land.Oct 18 2022, 11:10 AM

@mizvekov Thanks for the review and provided valuable feedback.

This revision was landed with ongoing or failed builds.Oct 18 2022, 11:59 AM
This revision was automatically updated to reflect the committed changes.
usaxena95 added inline comments.Oct 18 2022, 1:02 PM
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 added inline comments.Oct 18 2022, 3:30 PM
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 added inline comments.Oct 19 2022, 5:47 AM
clang/test/CXX/over/over.match/over.match.best/p1-2a.cpp
106

Thanks for the clarification.