[Concepts] Fix overload resolution bug with constrained candidates

[royjacobson]

Summary

When doing overload resolution, we have to check that candidates' parameter types are equal before trying to find a better candidate through checking which candidate is more constrained.
This revision adds this missing check and makes us diagnose those cases as ambiguous calls when the types are not equal.

Fixes GitHub issue https://github.com/llvm/llvm-project/issues/53640

[royjacobson]

Fixed missing doc for new argument

[erichkeane]

Can you improve the commit-message? Title in particular, but more details would be greatly appreciated.

clang/lib/Sema/SemaOverload.cpp

2954–2955

2958

I don't really get what you mean for 'Reversed', can you better clarify? Both in comments, and here?

2971

Now I REALLY don't get it :)

9829

Since the point of this is to just calculate the CanCompareConstraints, I think it should be a separate function called below where it is used.

[royjacobson]

Formatting + clarify docs a bit

[royjacobson]

clang/lib/Sema/SemaOverload.cpp

2958

I tried to modify the documentation a bit, I hope it's more understandable :)

C++20 added 'synthesized reverse operator overloads'. We support them in the overload resolution code by just remembering if we use a candidate with reverse order.

I need this here so the example in p6 with operator== works. It's a pretty annoying and weird corner case, but if it's explicitly in one of the standard's examples I might as well support it...

(BTW, GCC just don't implement this: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105174)

9829

Do you mean as in a separate Sema function? Or a local lambda?

[erichkeane]

clang/lib/Sema/SemaOverload.cpp

2967

Thanks for the clarification on 'Reversed'. The comment makes it more clear.

This whole 'for' header is... really tough to mentally parse, even BEFORE this, and now it is even worse with 'Reversed' involved. I would prefer that the iterators be initialized ahead of time. Additionally, can we use reverse_iterator for the 'NewType' instead of branching on Reversed here?

Any other suggestions you have to simplify this loop would also be appreciated. I might ALSO consider using 'zip' here?

2972

O AND O !=E? This condition reads wackily....

[royjacobson]

Update for look inside FunctionParamTypesAreEqual to be index based and simpler.

[royjacobson]

clang/lib/Sema/SemaOverload.cpp

2967

I made it index based which IMO is easier to understand now.

I thought reverse_iterator would be annoying because I would need to make the code a template since it's a different type.

Also - ping about the comment in isBetterOverloadCandidate :)

[erichkeane]

clang/lib/Sema/SemaOverload.cpp

2967

Ah, right, you'd have 1 reverse iterator on one side of the 'zip'. Thats unfortunate. I guess this reads well-enough though, iti s definitely an improvement.

9829

Just a static function is fine, basically its a whole lot of work happening in this function for a single result, so I'm suggesting splitting off the calculation for CanCompareConstraints into its own function, so you get:

bool CanCompareConstrants = new_function(...);

[royjacobson]

Split the 'can compare constraints' code into a static function.

[royjacobson]

clang/lib/Sema/SemaOverload.cpp

9829

Done

[erichkeane]

I'm happy with this.

[royjacobson]

Rebase

[royjacobson]

Rebase again (HEAD CI was broken)

[royjacobson]

Thanks @erichkeane! I will land this on Monday if there are no further comments and the CI looks good.

[erichkeane]

Pretty sure those OMP bugs are unrelated, we've been seeing those a ton lately on just about every patch.

[royjacobson]

So, it seems like this broke one of basic_arg_format's private constructors.. Sorry for that.

//format_arg.h:167
explicit basic_format_arg(_Tp __v) noexcept
      requires(same_as<_Tp, char_type> ||
               (same_as<_Tp, char> && same_as<char_type, wchar_t>)) [....]

//format_arg.h:248
explicit basic_format_arg(const _Tp& __v) [...]

This is now ambiguous when calling basic_format_arg(char) because the argument type is different and comparing constraints is not allowed. @Mordante could you maybe take a look? I've reverted in the meantime.

[Mordante]

In D123182#3458712, @royjacobson wrote:

So, it seems like this broke one of basic_arg_format's private constructors.. Sorry for that.

This is now ambiguous when calling basic_format_arg(char) because the argument type is different and comparing constraints is not allowed. @Mordante could you maybe take a look? I've reverted in the meantime.

Thanks for the ping!

I'll have a look, probably tomorrow.

[Mordante]

I've a fix in D124103.

[royjacobson]

Rebase after fix.

[erichkeane]

@nkreeger : Can you please explain your revert, both in the revert commit message (next time), as well as the patch so that the author/rest of us have SOME hint as to why it was reverted? Frequent reverts make it painful as a downstream, and confusing as a reviewer/implementer as to the state of things.

[nkreeger]

In D123182#3471661, @erichkeane wrote:

@nkreeger : Can you please explain your revert, both in the revert commit message (next time), as well as the patch so that the author/rest of us have SOME hint as to why it was reverted? Frequent reverts make it painful as a downstream, and confusing as a reviewer/implementer as to the state of things.

Apologies - I was reverting my commit and accidently had the wrong git-revert commit in my tree locally. I thought I had it cleaned up, but was wrong when I pushed. I ensured the tree was back in place with another revert. Please let me know if this is not the case. Sorry again :-(

[erichkeane]

In D123182#3471687, @nkreeger wrote:

In D123182#3471661, @erichkeane wrote:

@nkreeger : Can you please explain your revert, both in the revert commit message (next time), as well as the patch so that the author/rest of us have SOME hint as to why it was reverted? Frequent reverts make it painful as a downstream, and confusing as a reviewer/implementer as to the state of things.

Apologies - I was reverting my commit and accidently had the wrong git-revert commit in my tree locally. I thought I had it cleaned up, but was wrong when I pushed. I ensured the tree was back in place with another revert. Please let me know if this is not the case. Sorry again :-(

I see that now, thanks for the explanation! IN the future, even when reverting your OWN commit, it is appreciated if you explain the WHY to the revert so that it has some level of context. Particularly when you show some sort of example of the failure (like a link to the broken bot, etc), as it helps the downstream test-failure-analysis a ton.

[nkreeger]

In D123182#3471789, @erichkeane wrote:

In D123182#3471687, @nkreeger wrote:

In D123182#3471661, @erichkeane wrote:

@nkreeger : Can you please explain your revert, both in the revert commit message (next time), as well as the patch so that the author/rest of us have SOME hint as to why it was reverted? Frequent reverts make it painful as a downstream, and confusing as a reviewer/implementer as to the state of things.

Apologies - I was reverting my commit and accidently had the wrong git-revert commit in my tree locally. I thought I had it cleaned up, but was wrong when I pushed. I ensured the tree was back in place with another revert. Please let me know if this is not the case. Sorry again :-(

I see that now, thanks for the explanation! IN the future, even when reverting your OWN commit, it is appreciated if you explain the WHY to the revert so that it has some level of context. Particularly when you show some sort of example of the failure (like a link to the broken bot, etc), as it helps the downstream test-failure-analysis a ton.

Roger noted - apologies again I felt horrible!

clang/docs/ReleaseNotes.rst

 - Unevaluated lambdas in dependant contexts no longer result in clang crashing.
   This fixes Issues `50376 <https://github.com/llvm/llvm-project/issues/50376>`_,
   `51414 <https://github.com/llvm/llvm-project/issues/51414>`_,
   `51416 <https://github.com/llvm/llvm-project/issues/51416>`_,
   and `51641 <https://github.com/llvm/llvm-project/issues/51641>`_.
 - The builtin function __builtin_dump_struct would crash clang when the target 
   struct contains a bitfield. It now correctly handles bitfields.
   This fixes Issue `Issue 54462 <https://github.com/llvm/llvm-project/issues/54462>`_.
+- Overload resolution for constrained function templates could use the partial
+  order of constraints to select an overload, even if the parameter types of
+  the functions were different. It now diagnoses this case correctly as an
+  ambiguous call and an error. Fixes
+  `Issue 53640 <https://github.com/llvm/llvm-project/issues/53640>`_.
 
 Improvements to Clang's diagnostics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 - ``-Wliteral-range`` will warn on floating-point equality comparisons with
   constants that are not representable in a casted value. For example,
   ``(float) f == 0.1`` is always false.
 - ``-Winline-namespace-reopened-noninline`` now takes into account that the
   ``inline`` keyword must appear on the original but not necessarily all

clang/include/clang/Sema/Sema.h

public:
   bool isObjCPointerConversion(QualType FromType, QualType ToType,
                                QualType& ConvertedType, bool &IncompatibleObjC);
   bool isObjCWritebackConversion(QualType FromType, QualType ToType,
                                  QualType &ConvertedType);
   bool IsBlockPointerConversion(QualType FromType, QualType ToType,
                                 QualType& ConvertedType);
   bool FunctionParamTypesAreEqual(const FunctionProtoType *OldType,
                                   const FunctionProtoType *NewType,
-                                  unsigned *ArgPos = nullptr);
+                                  unsigned *ArgPos = nullptr,
+                                  bool Reversed = false);
   void HandleFunctionTypeMismatch(PartialDiagnostic &PDiag,
                                   QualType FromType, QualType ToType);
 
   void maybeExtendBlockObject(ExprResult &E);
   CastKind PrepareCastToObjCObjectPointer(ExprResult &E);
   bool CheckPointerConversion(Expr *From, QualType ToType,
                               CastKind &Kind,
                               CXXCastPath& BasePath,

 
   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);
+      unsigned NumCallArguments2, bool Reversed = false,
+      bool AllowOrderingByConstraints = true);
   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/Sema/SemaOverload.cpp

if (cast<FunctionProtoType>(FromFunction->getCanonicalTypeUnqualified())
     PDiag << ft_noexcept;
     return;
   }
 
   // Unable to find a difference, so add no extra info.
   PDiag << ft_default;
 }
 
 /// FunctionParamTypesAreEqual - This routine checks two function proto types
-/// for equality of their argument types. Caller has already checked that
-/// they have same number of arguments.  If the parameters are different,
+/// for equality of their parameter types. Caller has already checked that
+/// they have same number of parameters.  If the parameters are different,
 /// ArgPos will have the parameter index of the first different parameter.
+/// If `Reversed` is true, the parameters of `NewType` will be compared in
+/// reverse order. That's useful if one of the functions is being used as a C++20
+/// synthesized operator overload with a reversed parameter order.
 bool Sema::FunctionParamTypesAreEqual(const FunctionProtoType *OldType,
                                       const FunctionProtoType *NewType,
-                                      unsigned *ArgPos) {
-  for (FunctionProtoType::param_type_iterator O = OldType->param_type_begin(),
-                                              N = NewType->param_type_begin(),
-                                              E = OldType->param_type_end();
-       O && (O != E); ++O, ++N) {
+                                      unsigned *ArgPos, bool Reversed) {
+  assert(OldType->getNumParams() == NewType->getNumParams() &&
+         "Can't compare parameters of functions with different number of "
+         "parameters!");
+  for (size_t I = 0; I < OldType->getNumParams(); I++) {
+    // Reverse iterate over the parameters of `OldType` if `Reversed` is true.
+    size_t J = Reversed ? (OldType->getNumParams() - I - 1) : I;
+
     // Ignore address spaces in pointee type. This is to disallow overloading
     // on __ptr32/__ptr64 address spaces.
-    QualType Old = Context.removePtrSizeAddrSpace(O->getUnqualifiedType());
-    QualType New = Context.removePtrSizeAddrSpace(N->getUnqualifiedType());
+    QualType Old = Context.removePtrSizeAddrSpace(OldType->getParamType(I).getUnqualifiedType());
+    QualType New = Context.removePtrSizeAddrSpace(NewType->getParamType(J).getUnqualifiedType());
 
     if (!Context.hasSameType(Old, New)) {
       if (ArgPos)
-        *ArgPos = O - OldType->param_type_begin();
+        *ArgPos = I;
       return false;
     }
   }
   return true;
 }
 
 /// CheckPointerConversion - Check the pointer conversion from the
 /// expression From to the type ToType. This routine checks for
bool clang::isBetterOverloadCandidate(
   //       specialization, or, if not that,
   bool Cand1IsSpecialization = Cand1.Function &&
                                Cand1.Function->getPrimaryTemplate();
   bool Cand2IsSpecialization = Cand2.Function &&
                                Cand2.Function->getPrimaryTemplate();
   if (Cand1IsSpecialization != Cand2IsSpecialization)
     return Cand2IsSpecialization;
 
+  // We're allowed to use constraints partial ordering only if the functions
+  // have the same parameters:
+  // [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 [...]
+  bool CanCompareConstraints = false;
+  if (Cand1.Function && Cand2.Function && Cand1.Function->hasPrototype() &&
+      Cand2.Function->hasPrototype()) {
+    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()))
+      CanCompareConstraints = true;
+  }
+
   //   -- F1 and F2 are function template specializations, and the function
   //      template for F1 is more specialized than the template for F2
   //      according to the partial ordering rules described in 14.5.5.2, or,
   //      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()))
+            Cand1.isReversed() ^ Cand2.isReversed(), CanCompareConstraints))
       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 (Cand1.Function && Cand2.Function && !Cand1IsSpecialization &&
-      !Cand2IsSpecialization && Cand1.Function->hasPrototype() &&
-      Cand2.Function->hasPrototype()) {
-    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)) {
-      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))
-          return false;
-        if (AtLeastAsConstrained1 != AtLeastAsConstrained2)
-          return AtLeastAsConstrained1;
-      } else if (RC1 || RC2) {
-        return RC1 != nullptr;
-      }
-    }
-  }
+  if (!Cand1IsSpecialization && !Cand2IsSpecialization &&
+      CanCompareConstraints) {
+      if (S.IsAtLeastAsConstrained(Cand1.Function, {RC1}, Cand2.Function, {RC2},
+                                   AtLeastAsConstrained1) ||
+          S.IsAtLeastAsConstrained(Cand2.Function, {RC2}, Cand1.Function, {RC1},
+                                   AtLeastAsConstrained2))
 
   //   -- F1 is a constructor for a class D, F2 is a constructor for a base
   //      class B of D, and for all arguments the corresponding parameters of
   //      F1 and F2 have the same type.
   // FIXME: Implement the "all parameters have the same type" check.
   bool Cand1IsInherited =
       isa_and_nonnull<ConstructorUsingShadowDecl>(Cand1.FoundDecl.getDecl());
   bool Cand2IsInherited =

clang/lib/Sema/SemaTemplateDeduction.cpp

 ///
 /// \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) {
+FunctionTemplateDecl *Sema::getMoreSpecializedTemplate(
+    FunctionTemplateDecl *FT1, FunctionTemplateDecl *FT2, SourceLocation Loc,
+    TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1,
+    unsigned NumCallArguments2, bool Reversed,
+    bool AllowOrderingByConstraints) {
 
-  auto JudgeByConstraints = [&] () -> FunctionTemplateDecl * {
+  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;

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>;
+
+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>);
+
+bool h() {
+  return X<void *, int>{} == 0;
+}
+
+namespace PR53640 {
+
+template <typename T>
+concept C = true;
+
+template <C T>
+void f(T t) {} // expected-note {{candidate function [with T = int]}}
+
+template <typename T>
+void f(const T &t) {} // expected-note {{candidate function [with T = int]}}
+
+int g() {
+  f(0); // expected-error {{call to 'f' is ambiguous}}
+}
+
+struct S {
+  template <typename T> explicit S(T) noexcept requires C<T> {} // expected-note {{candidate constructor}}
+  template <typename T> explicit S(const T &) noexcept {}       // expected-note {{candidate constructor}}
+};
+
+int h() {
+  S s(4); // expected-error-re {{call to constructor of {{.*}} is ambiguous}}
+}
+
+}