[c++] implements tentative DR1432 for partial ordering of function template

[ychen]

Summary

D128745 handled DR1432 for the partial ordering of partial specializations, but
missed the handling for the partial ordering of function templates. This patch
implements the latter. While at it, also simplifies the previous implementation to
be more close to the wording without functional changes.

Fixes https://github.com/llvm/llvm-project/issues/56090

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5195–5196

This should work, as all the properties you are testing below are present on the canonical type.

5455–5456

This is a bug, T1 and T2 are not in general canonical types for this function, and this castAs can pick up an alias template, and these should never participate in deduction.

(Also, can you please add a test for that?)

You should not need to keep sugar here, everything being tested below is present on the canonical type, so this is simple to solve, as suggested.

[ychen]

@mizvekov Thanks for taking a look.

clang/lib/Sema/SemaTemplateDeduction.cpp

5195–5196

Gotta admit that I was confused by DesugaredType and CanonicalType. But since you pointed it out, I could see the differences now. The CanonicalType could be sugared, and desugaring is not necessary here. Thanks.

5455–5456

I see. I'll add a test.

[ychen]

• address comments
• rebase

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5455–5456

Looking more closely, T1/T2 is mostly returned by ASTContext::getTemplateSpecializationType and for injected template specialization, always unqualified https://github.com/llvm/llvm-project/blob/52dce8900c46d5842a021619537ede598983dfde/clang/include/clang/AST/Type.h#L5431-L5432 , it does not seem possible to have aliase template involved? I could've missed something though.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5455–5456

Yeah you are right, I missed that all the uses of this function, those types either come from an Injected TST, or a dependent TST created on the spot.

But yeah, the change to a simple cast instead of castAs makes this more clear.

Otherwise, if there could have been any sugar node on top of the TST, that sugar could have easily been an alias TST,
and I think it's very unlikely one wouldn't care, as they are very different things.

So I tend to view these as potential bugs, a simple getAs and castAs on TSTs, which does not check or keeps digging through alias templates is highly suspicious :)

Thanks for taking a look at this though!

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5170–5216

One thing I have been thinking about all of these "more constrained" checks, is whether we should actually be performing them over the results of the deductions for the least constrained checks.

Ie especially with regards to this new check and the one for [temp.deduct.partial]p11:, it seems that we should be instead considering as more constrained the deduction which deduced a lesser amount of template parameters, including ones in packs. Or something along this line.

This way, we do one sweeping general rule to handle all these cases, instead of just appending these ad-hoc tie-breaking rules which look more like workarounds.

What do you think about that?

But this is a big change and I don't want to block you on that. Because otherwise, this new change is keeping in line with other workarounds that have already been added here, so this is within existing practice.

Since this patch was submitted quite recently and it's a speculative fix, I would let this patch marinate a little more and wait for any other reviewers.

5190

I would make it more clear in this comment that this is a speculative fix, that there is no wording or even resolution for this issue.

clang/test/CXX/drs/dr6xx.cpp

1099

I would expect the call to g not to be ambiguous here, in the same vein of keeping with the spirit of the rules.

If you agree, can we at least add a FIXME to make a note of that?

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5455–5456

Thanks for the explanation. Yeah, castAs looks misleading indeed. I wasn't aware of the subtle difference between cast and castAs. BTW, are you comfortable accepting this patch?

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5455–5456

I hope I answered that in my other comment, but since this is a speculative wording fix, I think it's more reasonable to wait more than a week for other reviewers, specially since folks can be on time off and such.

But lacking interest from other folks in reviewing this, yeah sure.

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5170–5216

Ie especially with regards to this new check and the one for [temp.deduct.partial]p11:, it seems that we should be instead considering as more constrained the deduction which deduced a lesser amount of template parameters, including ones in packs. Or something along this line.

This way, we do one sweeping general rule to handle all these cases, instead of just appending these ad-hoc tie-breaking rules which look more like workarounds.

What do you think about that?

I think you meant the cases that for a P/A deduction pair, either P/A is pack and the other is not empty, right? If so, it already works that way. https://eel.is/c++draft/temp.deduct#type-9

If neither P/A is pack and either is empty, then they wouldn't get into the stage of partial ordering at all because the function arguments list can only have one length, P/A would not be in the same candidate sets.

Here handles the case that either P/A is pack and the other is empty. Then the deduction rule could not kick in because one of the P/Apair is none. So we have to tie-break after the deduction.

[mizvekov]

clang/lib/Sema/SemaTemplateDeduction.cpp

5170–5216

I understand we need to tie break after the at-least-as-specialized check, but I was wondering if we could come up with one sweeping rule / mechanism, which incorporates not only these two cases but also the concept more-constrained check, instead of appending multiple completely separate tie breakers.

Otherwise, I think this gets pretty hard to incorporate into your mental model of what overload resolution should pick up and such.

For example, even the order which we tie break seems arbitrary, and this makes it harder for folks to learn / memorize them and for them to actually be useful, instead of just programming traps. But this is C++ so I may be barking at the wrong tree.

[ychen]

clang/lib/Sema/SemaTemplateDeduction.cpp

5170–5216

The rules are complicated and we should definitely simplify these if possible. I'll give it more thought. @hubert.reinterpretcast worked a lot in this area. If he is interested, may shed some light here.

5455–5456

Thanks, that makes sense. I wasn't aware of your other comments when writing this.

clang/test/CXX/drs/dr6xx.cpp

1099

Yeah, I agree it is intuitive to work that way. I think it is not in the standard right now because it does not have a strong use case and it requires a big change because right now deduction for partial ordering and the following tie-breakers do not consider the function template parameter list at all, if we do this, then all partial orderings and template specializations are affected.

The use case of CWG1432 is partial specialization which is very important and easier to catch attention.

[ychen]

• update comments suggested by @mizvekov

[ychen]

ping ?

[mizvekov]

Looks good, aside some points:

• Please add test for the conditioning on ClangABICompat15.
• Missing release notes.
• FWIW GCC treats the g(42) case as not ambiguous, as I expected, so it might be worth pointing that out with a FIXME regardless.

[erichkeane]

Just fix @mizvekov 's nits (the fixme, release notes, and ABI test), and LGTM.

[ychen]

• add test for the conditioning on ClangABICompat15.

[ychen]

In D133683#3817523, @mizvekov wrote:

• Missing release notes.

I didn't add that because this patch is logically part of D128745 which has a release note already.

• FWIW GCC treats the g(42) case as not ambiguous, as I expected, so it might be worth pointing that out with a FIXME regardless.

I think GCC is the one that is not conforming. MSVC agrees it is ambiguous (https://godbolt.org/z/T5zbxaTYq). Basically, only the first parameter is considered for partial ordering. (https://eel.is/c++draft/temp.deduct.partial#3.1)

[mizvekov]

In D133683#3818752, @ychen wrote:

I didn't add that because this patch is logically part of D128745 which has a release note already.

Okay, I see that the existing release note entry talks just about implementing those DRs without going specific, so that is fine.
It does not mention that DR1432 implementation is tentative as there is no published resolution though.

I think GCC is the one that is not conforming. MSVC agrees it is ambiguous (https://godbolt.org/z/T5zbxaTYq). Basically, only the first parameter is considered for partial ordering. (https://eel.is/c++draft/temp.deduct.partial#3.1)

I could totally buy that the GCC behavior is accidental, but it does make sense, with the idea behind DR1432, that we should prefer the first overload because that deduction is simpler, or because it does not deduce a parameter pack.

If there was a resolution, the answer here would be clear cut, but since there isn't, we are making up our own rules and getting into a language design discussion.
If you don't think that is clear cut, it's fine, we can move this discussion elsewhere :)

[ychen]

In D133683#3818804, @mizvekov wrote:

In D133683#3818752, @ychen wrote:

I didn't add that because this patch is logically part of D128745 which has a release note already.

Okay, I see that the existing release note entry talks just about implementing those DRs without going specific, so that is fine.
It does not mention that DR1432 implementation is tentative as there is no published resolution though.

I think GCC is the one that is not conforming. MSVC agrees it is ambiguous (https://godbolt.org/z/T5zbxaTYq). Basically, only the first parameter is considered for partial ordering. (https://eel.is/c++draft/temp.deduct.partial#3.1)

I could totally buy that the GCC behavior is accidental, but it does make sense, with the idea behind DR1432, that we should prefer the first overload because that deduction is simpler, or because it does not deduce a parameter pack.

If there was a resolution, the answer here would be clear cut, but since there isn't, we are making up our own rules and getting into a language design discussion.
If you don't think that is clear cut, it's fine, we can move this discussion elsewhere :)

It is clear cut by https://eel.is/c++draft/temp.deduct.partial#3.1. It is orthogonal to the DRs implemented in D128745 and here.
https://godbolt.org/z/s49sqrabY : if you call g(42,42), it would reveal that the function without pack indeed wins. It is ambiguous because the caller g(42) does not use the pack. So the wording prevents us from letting the non-pack version win. I do somewhat agree that it is more consistent and predictable to always consider all function parameters for partial ordering. Yeah, that needs a whole separate discussion on https://eel.is/c++draft/temp.deduct.partial#3.1.

[ychen]

• Update release notes

[mizvekov]

In D133683#3818858, @ychen wrote:

It is clear cut by https://eel.is/c++draft/temp.deduct.partial#3.1. It is orthogonal to the DRs implemented in D128745 and here.
https://godbolt.org/z/s49sqrabY : if you call g(42,42), it would reveal that the function without pack indeed wins. It is ambiguous because the caller g(42) does not use the pack. So the wording prevents us from letting the non-pack version win. I do somewhat agree that it is more consistent and predictable to always consider all function parameters for partial ordering. Yeah, that needs a whole separate discussion on https://eel.is/c++draft/temp.deduct.partial#3.1.

I think it's using the pack, the pack is just being deduced as an empty pack. This is different from a template parameter which is not being deduced because it does not appear in the arguments.

To reiterate, what you said would make sense if the second overload was written as:

template <typename T, typename... U> void g(T);

Instead of template <typename T, typename... U> void g(T, U...); as it is.

[ychen]

In D133683#3818887, @mizvekov wrote:

In D133683#3818858, @ychen wrote:

It is clear cut by https://eel.is/c++draft/temp.deduct.partial#3.1. It is orthogonal to the DRs implemented in D128745 and here.
https://godbolt.org/z/s49sqrabY : if you call g(42,42), it would reveal that the function without pack indeed wins. It is ambiguous because the caller g(42) does not use the pack. So the wording prevents us from letting the non-pack version win. I do somewhat agree that it is more consistent and predictable to always consider all function parameters for partial ordering. Yeah, that needs a whole separate discussion on https://eel.is/c++draft/temp.deduct.partial#3.1.

I think it's using the pack, the pack is just being deduced as an empty pack. This is different from a template parameter which is not being deduced because it does not appear in the arguments.

To reiterate, what you said would make sense if the second overload was written as:

template <typename T, typename... U> void g(T);

Instead of template <typename T, typename... U> void g(T, U...); as it is.

This is described in https://eel.is/c++draft/temp.deduct.partial#13. Parietal ordering currently doesn't consider the number of deduced arguments. During the partial ordering stage, by https://eel.is/c++draft/temp.func.order#3, template <typename T, typename... U> void g(T, U...); would become void g(UniqueT1, UniqueT2);. And then it applies https://eel.is/c++draft/temp.deduct.partial#3.1 to decide which parameters are compared for partial ordering.

[mizvekov]

In D133683#3818935, @ychen wrote:

This is described in https://eel.is/c++draft/temp.deduct.partial#13. Parietal ordering currently doesn't consider the number of deduced arguments. During the partial ordering stage, by https://eel.is/c++draft/temp.func.order#3, template <typename T, typename... U> void g(T, U...); would become void g(UniqueT1, UniqueT2);. And then it applies https://eel.is/c++draft/temp.deduct.partial#3.1 to decide which parameters are compared for partial ordering.

Sure, one thing is, given that we deduced a pack, does the number of elements deduced for that pack matter in partial ordering. I think temp.deduct.partial#13 answers that it doesn't.

The other thing is, is a given template parameter pack used, or deduced, as opposed to just not being used. and I think the answer here is yes for that second overload of g.

If a template parameter pack appears as a type of a function parameter in an expansion pattern, such as void g(T, U...);, then I think that, notionally, there is no way to not use it.

For any call to that overload, that parameter pack will be deduced, no matter if to an empty pack or otherwise.

[ychen]

In D133683#3819003, @mizvekov wrote:

In D133683#3818935, @ychen wrote:

This is described in https://eel.is/c++draft/temp.deduct.partial#13. Parietal ordering currently doesn't consider the number of deduced arguments. During the partial ordering stage, by https://eel.is/c++draft/temp.func.order#3, template <typename T, typename... U> void g(T, U...); would become void g(UniqueT1, UniqueT2);. And then it applies https://eel.is/c++draft/temp.deduct.partial#3.1 to decide which parameters are compared for partial ordering.

Sure, one thing is, given that we deduced a pack, does the number of elements deduced for that pack matter in partial ordering. I think temp.deduct.partial#13 answers that it doesn't.

The other thing is, is a given template parameter pack used, or deduced, as opposed to just not being used. and I think the answer here is yes for that second overload of g.

If a template parameter pack appears as a type of a function parameter in an expansion pattern, such as void g(T, U...);, then I think that, notionally, there is no way to not use it.

That's right. That requires the wording says something like pack is always used for partial ordering. I just realized that this g(42) example is from https://eel.is/c++draft/temp.func.order#note-3.

clang/lib/Sema/SemaTemplateDeduction.cpp

FunctionTemplateDecl *Sema::getMoreSpecializedTemplate(
   bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
                                           NumCallArguments1, Reversed);
   bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
                                           NumCallArguments2, Reversed);
 
   if (Better1 != Better2) // We have a clear winner
     return Better1 ? FT1 : FT2;
 
   if (!Better1 && !Better2) // Neither is better than the other
     return JudgeByConstraints();
 
   // 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;
   }
 
+  // Consider this a fix for CWG1432. Similar to the fix for CWG1395.
+  bool ClangABICompat15 =
+      Context.getLangOpts().getClangABICompat() <= LangOptions::ClangABI::Ver15;
+  if (!ClangABICompat15) {
+    for (int i = 0, e = std::min(NumParams1, NumParams2); i < e; ++i) {
+      QualType T1 = FD1->getParamDecl(i)->getType().getDesugaredType(Context);
+      QualType T2 = FD2->getParamDecl(i)->getType().getDesugaredType(Context);
+      auto *TST1 = dyn_cast<TemplateSpecializationType>(T1);
+      auto *TST2 = dyn_cast<TemplateSpecializationType>(T2);
+      if (TST1 && TST2) {
+        unsigned NumArgs1 = TST1->getNumArgs();
+        unsigned NumArgs2 = TST2->getNumArgs();
+        bool IsPackExpansion1 =
+            NumArgs1 && TST1->template_arguments().back().isPackExpansion();
+        bool IsPackExpansion2 =
+            NumArgs2 && TST2->template_arguments().back().isPackExpansion();
+        if (NumArgs1 != NumArgs2 && IsPackExpansion1 != IsPackExpansion2) {
+          if (NumArgs1 > NumArgs2 && IsPackExpansion1)
+            return FT2;
+          if (NumArgs1 < NumArgs2 && IsPackExpansion2)
+            return FT1;
+        }
+      }
+    }
+  }
+
   return JudgeByConstraints();
 }
 
 /// Determine if the two templates are equivalent.
 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
   if (T1 == T2)
     return true;
 
   if (!T1 || !T2)
getMoreSpecialized(Sema &S, QualType T1, QualType T2, TemplateLikeDecl *P1,
   bool Better2 = isAtLeastAsSpecializedAs(S, T2, T1, P1, Info);
   if (IsMoreSpecialThanPrimaryCheck && !Better2)
     return P1;
 
   if (!Better1 && !Better2)
     return nullptr;
 
   if (Better1 && Better2) {
+    // Consider this a fix for CWG1432. Similar to the fix for CWG1395.
     bool ClangABICompat15 = S.Context.getLangOpts().getClangABICompat() <=
                             LangOptions::ClangABI::Ver15;
     if (!ClangABICompat15) {
-      // 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;
-          }
-        }
-      }
-    }
+      unsigned PackSize1 =
+          TA1.getKind() == TemplateArgument::Pack ? TA1.pack_size() : 0u;
+      unsigned PackSize2 =
+          TA2.getKind() == TemplateArgument::Pack ? TA2.pack_size() : 0u;
+      unsigned NumArgs1 = TST1->getNumArgs() + PackSize1;
+      unsigned NumArgs2 = TST2->getNumArgs() + PackSize2;
+      if (NumArgs1 != NumArgs2 && IsPackExpansion1 != IsPackExpansion2) {
+        if (NumArgs1 > NumArgs2 && IsPackExpansion1)
+        if (NumArgs1 < NumArgs2 && IsPackExpansion2)
 
     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;

clang/test/CXX/drs/dr6xx.cpp

#endif
     template g<int>(a); // expected-error {{expected expression}}
   }
 }
 
 namespace dr692 { // dr692: no
   // Also see dr1395.
 
   namespace temp_func_order_example2 {
-    template <typename T, typename U> struct A {};
-    template <typename T, typename U> void f(U, A<U, T> *p = 0); // expected-note {{candidate}}
+    template <typename... T> struct A {}; // expected-error 0-1{{C++11}}
+    template <class T1, class... U> void e(A<T1, U...>) = delete; // expected-error 0-2{{C++11}}
+    template <class T1> void e(A<T1>);
+    template <typename T, typename U> void f(U, A<U, T> *p = 0) = delete; // expected-note {{candidate}} expected-error 0-1{{C++11}}
     template <typename U> int &f(U, A<U, U> *p = 0); // expected-note {{candidate}}
     template <typename T> void g(T, T = T()); // expected-note {{candidate}}
     template <typename T, typename... U> void g(T, U...); // expected-note {{candidate}} expected-error 0-1{{C++11}}
     void h() {
-      int &r = f<int>(42, (A<int, int> *)0);
+      A<int, int> a;
+      int &r = f<int>(42, &a);
+      A<int> b;
+      e(b);
       f<int>(42); // expected-error {{ambiguous}}
       g(42); // expected-error {{ambiguous}}
     }
   }
 
   namespace temp_func_order_example3 {
     template <typename T, typename... U> void f(T, U...); // expected-error 0-1{{C++11}}
     template <typename T> void f(T);
     template <typename T, typename... U> int &g(T *, U...); // expected-error 0-1{{C++11}}
     template <typename T> void g(T);