[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)

[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

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]

• 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

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.

[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

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]

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

[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

9790–9791

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

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.

[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

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]

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]

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]

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]

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]

• 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]

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.

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