[Sema] Change order of displayed overloads in diagnostics

[ilya-biryukov]

Summary

Make it a strict weak order.

Fixes #64121.

Current implementation uses the definition the definition of ordering
in the C++ standard. The definition provides only a partial order and
cannot be used in sorting algorithms.

The debug builds of libc++ are capable of detecting that problem
and this failure was found when building Clang with libc++ and
those extra checks enabled, see #64121.

The new ordering is a strict weak order and still
pushes most interesting functions to the start of the list.
In some cases, it leads to better results, e.g.

struct Foo {
  operator int();
  operator const char*();
};

void test() { Foo() - Foo(); }

Now produces a list with two most relevant builtin operators at the top,
i.e. operator-(int, int) and operator-(const char*, const char*).
Previously operator-(const char*, const char*) was the first element,
but operator-(int, int) was only the 13th element in the output.
This is a consequence of stable_sort now being able to compare those
two candidates, which are indistinguishable in the semantic partial order
despite being two local minimums in their respective comparable
subsets.

However, new implementation does not take into account some aspects of
C++ semantics, e.g. which function template is more specialized. This
can also lead to worse ordering sometimes.

[ilya-biryukov]

This change mainly tried to address the assertion failure in libc++, but got into the territory of changing the order of displayed overloads.
Which might be a more complicated topic, so it would be great to get feedback from Clang maintainers.

I am on vacation next week, so @rnk might want pick this up if fixing the assertion turns out to be urgent.

[cor3ntin]

@hubert.reinterpretcast @rsmith Opinions on that?

[rnk]

+@cjdb , do you have time to review this?

[ilya-biryukov]

@cor3ntin any suggestions on how to proceed here?

I hope the approach taken in the current patch should already provide meaningful and improved results in most cases.
It only affects the diagnostics output, so changing or reverting it should be relatively easy in the future.

I'm happy to ask someone from my team to do the detailed code review, but I just wanted to make sure the Clang contributors are generally ok with the direction here.

[cor3ntin]

+ @aaron.ballman

[shafik]

You say "attempts to be a strict weak order" does that mean there are still cases which will cause an assert or are we not sure?

[ilya-biryukov]

In D159351#4653687, @shafik wrote:

You say "attempts to be a strict weak order" does that mean there are still cases which will cause an assert or are we not sure?

No, it's an actual strict weak order. It's a bad choice of wording on my part.

[aaron.ballman]

I think the changes should come with a release note so users know about the improved user experience (it would be great to show the code example from this patch summary in the release notes with the explanation you gave). Overall, I think this gives reasonable diagnostic behavior (I expect it to roughly be a wash in terms of showing the "best" order -- some will improve, some will degrade) but the ability to make the sets sortable without triggering checked STL diagnostics is definitely an improvement. Thanks!

clang/lib/Sema/SemaOverload.cpp

11817–11819

Coding style nit.

11872–11874

11927–11928

11955

[ilya-biryukov]

• Addressed comments
• Added a release note

clang/lib/Sema/SemaOverload.cpp

 #include "clang/Sema/Overload.h"
 #include "clang/Sema/SemaInternal.h"
 #include "clang/Sema/Template.h"
 #include "clang/Sema/TemplateDeduction.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 #include <algorithm>
+#include <cstddef>
 #include <cstdlib>
 #include <optional>
 
 using namespace clang;
 using namespace sema;
 
 using AllowedExplicit = Sema::AllowedExplicit;
 
static unsigned RankDeductionFailure(const DeductionFailureInfo &DFI) {
   case Sema::TDK_TooManyArguments:
   case Sema::TDK_TooFewArguments:
     return 6;
   }
   llvm_unreachable("Unhandled deduction result");
 }
 
 namespace {
+
 struct CompareOverloadCandidatesForDisplay {
   Sema &S;
   SourceLocation Loc;
   size_t NumArgs;
   OverloadCandidateSet::CandidateSetKind CSK;
 
   CompareOverloadCandidatesForDisplay(
       Sema &S, SourceLocation Loc, size_t NArgs,
bool operator()(const OverloadCandidate *L,
                   const OverloadCandidate *R) {
     // Fast-path this check.
     if (L == R) return false;
 
     // Order first by viability.
     if (L->Viable) {
       if (!R->Viable) return true;
 
-      // TODO: introduce a tri-valued comparison for overload
-      // candidates.  Would be more worthwhile if we had a sort
-      // that could exploit it.
-      if (isBetterOverloadCandidate(S, *L, *R, SourceLocation(), CSK))
-        return true;
-      if (isBetterOverloadCandidate(S, *R, *L, SourceLocation(), CSK))
-        return false;
+      if (int Ord = CompareConversions(*L, *R)) {
+        return Ord < 0;
+      }
+      // Use other tie breakers.
     } else if (R->Viable)
       return false;
 
     assert(L->Viable == R->Viable);
 
     // Criteria by which we can sort non-viable candidates:
     if (!L->Viable) {
       OverloadFailureKind LFailureKind = EffectiveFailureKind(L);
if (!L->Viable) {
         unsigned numRFixes = R->Fix.NumConversionsFixed;
         numLFixes = (numLFixes == 0) ? UINT_MAX : numLFixes;
         numRFixes = (numRFixes == 0) ? UINT_MAX : numRFixes;
         if (numLFixes != numRFixes) {
           return numLFixes < numRFixes;
         }
 
         // If there's any ordering between the defined conversions...
-        // FIXME: this might not be transitive.
-        assert(L->Conversions.size() == R->Conversions.size());
-
-        int leftBetter = 0;
-        unsigned I = (L->IgnoreObjectArgument || R->IgnoreObjectArgument);
-        for (unsigned E = L->Conversions.size(); I != E; ++I) {
-          switch (CompareImplicitConversionSequences(S, Loc,
-                                                     L->Conversions[I],
-                                                     R->Conversions[I])) {
-          case ImplicitConversionSequence::Better:
-            leftBetter++;
-            break;
-
-          case ImplicitConversionSequence::Worse:
-            leftBetter--;
-            break;
-
-          case ImplicitConversionSequence::Indistinguishable:
-            break;
-          }
-        }
-        if (leftBetter > 0) return true;
-        if (leftBetter < 0) return false;
-
+        if (int Ord = CompareConversions(*L, *R)) {
+          return Ord < 0;
       } else if (RFailureKind == ovl_fail_bad_conversion)
         return false;
 
       if (LFailureKind == ovl_fail_bad_deduction) {
         if (RFailureKind != ovl_fail_bad_deduction)
           return true;
 
         if (L->DeductionFailure.Result != R->DeductionFailure.Result)
           return RankDeductionFailure(L->DeductionFailure)
                < RankDeductionFailure(R->DeductionFailure);
       } else if (RFailureKind == ovl_fail_bad_deduction)
         return false;
 
       // TODO: others?
     }
 
     // Sort everything else by location.
     SourceLocation LLoc = GetLocationForCandidate(L);
     SourceLocation RLoc = GetLocationForCandidate(R);
 
     // Put candidates without locations (e.g. builtins) at the end.
-    if (LLoc.isInvalid()) return false;
-    if (RLoc.isInvalid()) return true;
-
+    if (LLoc.isValid() && RLoc.isValid())
       return S.SourceMgr.isBeforeInTranslationUnit(LLoc, RLoc);
+    if (LLoc.isValid() && !RLoc.isValid())
+      return true;
+    if (RLoc.isValid() && !LLoc.isValid())
+      return false;
+    assert(!LLoc.isValid() && !RLoc.isValid());
+    // For builtins and other functions without locations, fallback to the order
+    // in which they were added into the candidate set.
+    return L < R;
+  }
+
+private:
+  struct ConversionSignals {
+    unsigned KindRank = 0;
+    ImplicitConversionRank Rank = ICR_Exact_Match;
+
+    static ConversionSignals ForSequence(ImplicitConversionSequence &Seq) {
+      ConversionSignals Sig;
+      Sig.KindRank = Seq.getKindRank();
+      if (Seq.isStandard())
+        Sig.Rank = Seq.Standard.getRank();
+      else if (Seq.isUserDefined())
+        Sig.Rank = Seq.UserDefined.After.getRank();
+      // We intend StaticObjectArgumentConversion to compare the same as
+      // StandardConversion with ICR_ExactMatch rank.
+      return Sig;
+    }
+
+    static ConversionSignals ForObjectArgument() {
+      // We intend StaticObjectArgumentConversion to compare the same as
+      // StandardConversion with ICR_ExactMatch rank.
+      // Default give us that.
+      return {};
+    }
+  };
+
+  // Returns -1 if conversions in L are considered better.
+  //          0 if they are considered indistinguishable.
+  //          1 if conversions in R are better.
+  int CompareConversions(const OverloadCandidate &L,
+                         const OverloadCandidate &R) {
+    // We cannot use `isBetterOverloadCandidate` because it is defined
+    // according to the C++ standard and provides a partial order, but we need
+    // a total order as this function is used in sort.
+    assert(L.Conversions.size() == R.Conversions.size());
+    for (unsigned I = 0, N = L.Conversions.size(); I != N; ++I) {
+      auto LS = L.IgnoreObjectArgument && I == 0
+                    ? ConversionSignals::ForObjectArgument()
+                    : ConversionSignals::ForSequence(L.Conversions[I]);
+      auto RS = R.IgnoreObjectArgument
+                    ? ConversionSignals::ForObjectArgument()
+                    : ConversionSignals::ForSequence(R.Conversions[I]);
+      if (std::tie(LS.KindRank, LS.Rank) != std::tie(RS.KindRank, RS.Rank))
+        return std::tie(LS.KindRank, LS.Rank) < std::tie(RS.KindRank, RS.Rank)
+                   ? -1
+                   : 1;
+    }
+    // FIXME: find a way to compare templates for being more or less
+    // specialized that provides a weak ordering.
+    return 0;
   }
 };
 }
 
 /// CompleteNonViableCandidate - Normally, overload resolution only
 /// computes up to the first bad conversion. Produces the FixIt set if
 /// possible.
 static void

clang/test/SemaCXX/overloaded-operators-display-order-crash.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify %s
+
+namespace ambig {
+  struct Foo {
+    operator int();
+    operator const char *();
+  };
+
+
+  void func(const char*, long);
+  void func(const char*, const char*);
+  void func(int, int);
+
+  bool doit(Foo x) {
+    func(x, x); // expected-error {{call to 'func' is ambiguous}}
+                // expected-note@* 3{{candidate}}
+  }
+}
+
+namespace bad_conversion {
+  struct Foo {
+    operator int();
+    operator const char *();
+  };
+
+
+  void func(double*, const char*, long);
+  void func(double*, const char*, const char*);
+  void func(double*, int, int);
+
+  bool doit(Foo x) {
+    func((int*)0, x, x); // expected-error {{no matching function for call to 'func'}}
+                         // expected-note@* 3{{candidate}}
+  }
+}