[c++20] Add rewriting from comparison operators to <=> / ==.

This adds support for rewriting <, >, <=, and >= to a normal or reversed
call to operator<=>, for rewriting != to a normal or reversed call to
operator==, and for rewriting <=> and == to reversed forms of those same
operators.

Note that this is a breaking change for various C++17 code patterns,
including some in use in LLVM. The most common patterns (where an
operator== becomes ambiguous with a reversed form of itself) are still
accepted under this patch, as an extension (with a warning). I'm hopeful
that we can get the language rules fixed before C++20 ships, and the
extension warning is aimed primarily at providing data to inform that
decision.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@375306 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 343 insertions, 5 deletions

diff --git a/test/CXX/over/over.match/over.match.funcs/over.match.oper/p3-2a.cpp b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p3-2a.cpp
new file mode 100644
index 0000000000..3be8dc7749
--- /dev/null
+++ b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p3-2a.cpp
@@ -0,0 +1,172 @@
+// RUN: %clang_cc1 -std=c++2a -verify %s
+// RUN: %clang_cc1 -std=c++2a -verify -Wall -DNO_ERRORS %s
+
+#ifndef NO_ERRORS
+namespace bullet3 {
+  // the built-in candidates include all of the candidate operator fnuctions
+  // [...] that, compared to the given operator
+
+  // - do not have the same parameter-type-list as any non-member candidate
+
+  enum E { e };
+
+  // Suppress both builtin operator<=>(E, E) and operator<(E, E).
+  void operator<=>(E, E); // expected-note {{while rewriting}}
+  bool cmp = e < e; // expected-error {{invalid operands to binary expression ('void' and 'int')}}
+
+  // None of the other bullets have anything to test here. In principle we
+  // need to suppress both builtin operator@(A, B) and operator@(B, A) when we
+  // see a user-declared reversible operator@(A, B), and we do, but that's
+  // untestable because the only built-in reversible candidates are
+  // operator<=>(E, E) and operator==(E, E) for E an enumeration type, and
+  // those are both symmetric anyway.
+}
+
+namespace bullet4 {
+  // The rewritten candidate set is determined as follows:
+
+  template<int> struct X {};
+  X<1> x1;
+  X<2> x2;
+
+  struct Y {
+    int operator<=>(X<2>) = delete; // #1member
+    bool operator==(X<2>) = delete; // #2member
+  };
+  Y y;
+
+  // - For the relational operators, the rewritten candidates include all
+  //   non-rewritten candidates for the expression x <=> y.
+  int operator<=>(X<1>, X<2>) = delete; // #1
+
+  // expected-note@#1 5{{candidate function has been explicitly deleted}}
+  // expected-note@#1 5{{candidate function (with reversed parameter order) not viable: no known conversion from 'X<1>' to 'X<2>' for 1st argument}}
+  bool lt = x1 < x2; // expected-error {{selected deleted operator '<=>'}}
+  bool le = x1 <= x2; // expected-error {{selected deleted operator '<=>'}}
+  bool gt = x1 > x2; // expected-error {{selected deleted operator '<=>'}}
+  bool ge = x1 >= x2; // expected-error {{selected deleted operator '<=>'}}
+  bool cmp = x1 <=> x2; // expected-error {{selected deleted operator '<=>'}}
+
+  // expected-note@#1member 5{{candidate function has been explicitly deleted}}
+  // expected-note@#1 5{{candidate function not viable: no known conversion from 'bullet4::Y' to 'X<1>' for 1st argument}}
+  // expected-note@#1 5{{candidate function (with reversed parameter order) not viable: no known conversion from 'bullet4::Y' to 'X<2>' for 1st argument}}
+  bool mem_lt = y < x2; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_le = y <= x2; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_gt = y > x2; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_ge = y >= x2; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_cmp = y <=> x2; // expected-error {{selected deleted operator '<=>'}}
+
+  // - For the relational and three-way comparison operators, the rewritten
+  //   candidates also include a synthesized candidate, with the order of the
+  //   two parameters reversed, for each non-rewritten candidate for the
+  //   expression y <=> x.
+
+  // expected-note@#1 5{{candidate function (with reversed parameter order) has been explicitly deleted}}
+  // expected-note@#1 5{{candidate function not viable: no known conversion from 'X<2>' to 'X<1>' for 1st argument}}
+  bool rlt = x2 < x1; // expected-error {{selected deleted operator '<=>'}}
+  bool rle = x2 <= x1; // expected-error {{selected deleted operator '<=>'}}
+  bool rgt = x2 > x1; // expected-error {{selected deleted operator '<=>'}}
+  bool rge = x2 >= x1; // expected-error {{selected deleted operator '<=>'}}
+  bool rcmp = x2 <=> x1; // expected-error {{selected deleted operator '<=>'}}
+
+  // expected-note@#1member 5{{candidate function (with reversed parameter order) has been explicitly deleted}}
+  // expected-note@#1 5{{candidate function not viable: no known conversion from 'X<2>' to 'X<1>' for 1st argument}}
+  // expected-note@#1 5{{candidate function (with reversed parameter order) not viable: no known conversion from 'bullet4::Y' to 'X<1>' for 2nd argument}}
+  bool mem_rlt = x2 < y; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_rle = x2 <= y; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_rgt = x2 > y; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_rge = x2 >= y; // expected-error {{selected deleted operator '<=>'}}
+  bool mem_rcmp = x2 <=> y; // expected-error {{selected deleted operator '<=>'}}
+
+  // For the != operator, the rewritten candidates include all non-rewritten
+  // candidates for the expression x == y
+  int operator==(X<1>, X<2>) = delete; // #2
+
+  // expected-note@#2 2{{candidate function has been explicitly deleted}}
+  // expected-note@#2 2{{candidate function (with reversed parameter order) not viable: no known conversion from 'X<1>' to 'X<2>' for 1st argument}}
+  bool eq = x1 == x2; // expected-error {{selected deleted operator '=='}}
+  bool ne = x1 != x2; // expected-error {{selected deleted operator '=='}}
+
+  // expected-note@#2member 2{{candidate function has been explicitly deleted}}
+  // expected-note@#2 2{{candidate function not viable: no known conversion from 'bullet4::Y' to 'X<1>' for 1st argument}}
+  // expected-note@#2 2{{candidate function (with reversed parameter order) not viable: no known conversion from 'bullet4::Y' to 'X<2>' for 1st argument}}
+  bool mem_eq = y == x2; // expected-error {{selected deleted operator '=='}}
+  bool mem_ne = y != x2; // expected-error {{selected deleted operator '=='}}
+
+  // For the equality operators, the rewritten candidates also include a
+  // synthesized candidate, with the order of the two parameters reversed, for
+  // each non-rewritten candidate for the expression y == x
+
+  // expected-note@#2 2{{candidate function (with reversed parameter order) has been explicitly deleted}}
+  // expected-note@#2 2{{candidate function not viable: no known conversion from 'X<2>' to 'X<1>' for 1st argument}}
+  bool req = x2 == x1; // expected-error {{selected deleted operator '=='}}
+  bool rne = x2 != x1; // expected-error {{selected deleted operator '=='}}
+
+  // expected-note@#2member 2{{candidate function (with reversed parameter order) has been explicitly deleted}}
+  // expected-note@#2 2{{candidate function not viable: no known conversion from 'X<2>' to 'X<1>' for 1st argument}}
+  // expected-note@#2 2{{candidate function (with reversed parameter order) not viable: no known conversion from 'bullet4::Y' to 'X<1>' for 2nd argument}}
+  bool mem_req = x2 == y; // expected-error {{selected deleted operator '=='}}
+  bool mem_rne = x2 != y; // expected-error {{selected deleted operator '=='}}
+
+  // For all other operators, the rewritten candidate set is empty.
+  X<3> operator+(X<1>, X<2>) = delete; // expected-note {{no known conversion from 'X<2>' to 'X<1>'}}
+  X<3> reversed_add = x2 + x1; // expected-error {{invalid operands}}
+}
+
+// Various C++17 cases that are known to be broken by the C++20 rules.
+namespace problem_cases {
+  // We can have an ambiguity between an operator and its reversed form. This
+  // wasn't intended by the original "consistent comparison" proposal, and we
+  // allow it as extension, picking the non-reversed form.
+  struct A {
+    bool operator==(const A&); // expected-note {{ambiguity is between a regular call to this operator and a call with the argument order reversed}}
+  };
+  bool cmp_non_const = A() == A(); // expected-warning {{ambiguous}}
+
+  struct B {
+    virtual bool operator==(const B&) const;
+  };
+  struct D : B {
+    bool operator==(const B&) const override; // expected-note {{operator}}
+  };
+  bool cmp_base_derived = D() == D(); // expected-warning {{ambiguous}}
+
+  template<typename T> struct CRTPBase {
+    bool operator==(const T&) const; // expected-note {{operator}}
+  };
+  struct CRTP : CRTPBase<CRTP> {};
+  bool cmp_crtp = CRTP() == CRTP(); // expected-warning {{ambiguous}}
+
+  // We can select a non-rewriteable operator== for a != comparison, when there
+  // was a viable operator!= candidate we could have used instead.
+  //
+  // Rejecting this seems OK on balance.
+  using UBool = signed char; // ICU uses this.
+  struct ICUBase {
+    virtual UBool operator==(const ICUBase&) const;
+    UBool operator!=(const ICUBase &arg) const { return !operator==(arg); }
+  };
+  struct ICUDerived : ICUBase {
+    UBool operator==(const ICUBase&) const override; // expected-note {{declared here}}
+  };
+  bool cmp_icu = ICUDerived() != ICUDerived(); // expected-error {{not 'bool'}}
+}
+
+#else // NO_ERRORS
+
+namespace problem_cases {
+  // We can select a reversed candidate where we used to select a non-reversed
+  // one, and in the worst case this can dramatically change the meaning of the
+  // program. Make sure we at least warn on the worst cases under -Wall.
+  struct iterator;
+  struct const_iterator {
+    const_iterator(iterator);
+    bool operator==(const const_iterator&) const;
+  };
+  struct iterator {
+    bool operator==(const const_iterator &o) const { // expected-warning {{all paths through this function will call itself}}
+      return o == *this;
+    }
+  };
+}
+#endif // NO_ERRORS
diff --git a/test/CXX/over/over.match/over.match.funcs/over.match.oper/p8-2a.cpp b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p8-2a.cpp
new file mode 100644
index 0000000000..da0f576f8c
--- /dev/null
+++ b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p8-2a.cpp
@@ -0,0 +1,70 @@
+// RUN: %clang_cc1 -std=c++2a -verify %s
+
+template<typename L, typename R> struct Op { L l; const char *op; R r; };
+// FIXME: Remove once we implement P1816R0.
+template<typename L, typename R> Op(L, R) -> Op<L, R>;
+
+struct A {};
+struct B {};
+constexpr Op<A, B> operator<=>(A a, B b) { return {a, "<=>", b}; }
+
+template<typename T, typename U, typename V> constexpr Op<Op<T, U>, V> operator<  (Op<T, U> a, V b) { return {a, "<",   b}; }
+template<typename T, typename U, typename V> constexpr Op<Op<T, U>, V> operator<= (Op<T, U> a, V b) { return {a, "<=",  b}; }
+template<typename T, typename U, typename V> constexpr Op<Op<T, U>, V> operator>  (Op<T, U> a, V b) { return {a, ">",   b}; }
+template<typename T, typename U, typename V> constexpr Op<Op<T, U>, V> operator>= (Op<T, U> a, V b) { return {a, ">=",  b}; }
+template<typename T, typename U, typename V> constexpr Op<Op<T, U>, V> operator<=>(Op<T, U> a, V b) { return {a, "<=>", b}; }
+
+template<typename T, typename U, typename V> constexpr Op<T, Op<U, V>> operator<  (T a, Op<U, V> b) { return {a, "<",   b}; }
+template<typename T, typename U, typename V> constexpr Op<T, Op<U, V>> operator<= (T a, Op<U, V> b) { return {a, "<=",  b}; }
+template<typename T, typename U, typename V> constexpr Op<T, Op<U, V>> operator>  (T a, Op<U, V> b) { return {a, ">",   b}; }
+template<typename T, typename U, typename V> constexpr Op<T, Op<U, V>> operator>= (T a, Op<U, V> b) { return {a, ">=",  b}; }
+template<typename T, typename U, typename V> constexpr Op<T, Op<U, V>> operator<=>(T a, Op<U, V> b) { return {a, "<=>", b}; }
+
+constexpr bool same(A, A) { return true; }
+constexpr bool same(B, B) { return true; }
+constexpr bool same(int a, int b) { return a == b; }
+template<typename T, typename U>
+constexpr bool same(Op<T, U> x, Op<T, U> y) {
+  return same(x.l, y.l) && __builtin_strcmp(x.op, y.op) == 0 && same(x.r, y.r);
+}
+
+// x @ y is interpreted as:
+void f(A x, B y) {
+  //   --  (x <=> y) @ 0 if not reversed
+  static_assert(same(x < y, (x <=> y) < 0));
+  static_assert(same(x <= y, (x <=> y) <= 0));
+  static_assert(same(x > y, (x <=> y) > 0));
+  static_assert(same(x >= y, (x <=> y) >= 0));
+  static_assert(same(x <=> y, x <=> y)); // (not rewritten)
+}
+
+void g(B x, A y) {
+  //   --  0 @ (y <=> x) if reversed
+  static_assert(same(x < y, 0 < (y <=> x)));
+  static_assert(same(x <= y, 0 <= (y <=> x)));
+  static_assert(same(x > y, 0 > (y <=> x)));
+  static_assert(same(x >= y, 0 >= (y <=> x)));
+  static_assert(same(x <=> y, 0 <=> (y <=> x)));
+}
+
+
+// We can rewrite into a call involving a builtin operator.
+struct X { int result; };
+struct Y {};
+constexpr int operator<=>(X x, Y) { return x.result; }
+static_assert(X{-1} < Y{});
+static_assert(X{0} < Y{}); // expected-error {{failed}}
+static_assert(X{0} <= Y{});
+static_assert(X{1} <= Y{}); // expected-error {{failed}}
+static_assert(X{1} > Y{});
+static_assert(X{0} > Y{}); // expected-error {{failed}}
+static_assert(X{0} >= Y{});
+static_assert(X{-1} >= Y{}); // expected-error {{failed}}
+static_assert(Y{} < X{1});
+static_assert(Y{} < X{0}); // expected-error {{failed}}
+static_assert(Y{} <= X{0});
+static_assert(Y{} <= X{-1}); // expected-error {{failed}}
+static_assert(Y{} > X{-1});
+static_assert(Y{} > X{0}); // expected-error {{failed}}
+static_assert(Y{} >= X{0});
+static_assert(Y{} >= X{1}); // expected-error {{failed}}
diff --git a/test/CXX/over/over.match/over.match.funcs/over.match.oper/p9-2a.cpp b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p9-2a.cpp
new file mode 100644
index 0000000000..fce46816ce
--- /dev/null
+++ b/test/CXX/over/over.match/over.match.funcs/over.match.oper/p9-2a.cpp
@@ -0,0 +1,38 @@
+// RUN: %clang_cc1 -std=c++2a -verify %s
+
+// ... return type shall be cv bool ...
+namespace not_bool {
+  struct X {} x;
+  struct Y {} y;
+  int operator==(X, Y); // expected-note 4{{here}}
+  bool a = x == y; // ok
+  bool b = y == x; // expected-error {{return type 'int' of selected 'operator==' function for rewritten '==' comparison is not 'bool'}}
+  bool c = x != y; // expected-error {{return type 'int' of selected 'operator==' function for rewritten '!=' comparison is not 'bool'}}
+  bool d = y != x; // expected-error {{return type 'int' of selected 'operator==' function for rewritten '!=' comparison is not 'bool'}}
+
+  // cv-qualifiers are OK
+  const bool operator==(Y, X);
+  bool e = y != x; // ok
+
+  // We don't prefer a function with bool return type over one witn non-bool return type.
+  bool f = x != y; // expected-error {{return type 'int' of selected 'operator==' function for rewritten '!=' comparison is not 'bool'}}
+}
+
+struct X { bool equal; };
+struct Y {};
+constexpr bool operator==(X x, Y) { return x.equal; }
+
+static_assert(X{true} == Y{});
+static_assert(X{false} == Y{}); // expected-error {{failed}}
+
+// x == y -> y == x
+static_assert(Y{} == X{true});
+static_assert(Y{} == X{false}); // expected-error {{failed}}
+
+// x != y -> !(x == y)
+static_assert(X{true} != Y{}); // expected-error {{failed}}
+static_assert(X{false} != Y{});
+
+// x != y -> !(y == x)
+static_assert(Y{} != X{true}); // expected-error {{failed}}
+static_assert(Y{} != X{false});
diff --git a/test/CXX/temp/temp.fct.spec/temp.deduct/p7.cpp b/test/CXX/temp/temp.fct.spec/temp.deduct/p7.cpp
index bc074ba25e..f0ab7b8ea7 100644
--- a/test/CXX/temp/temp.fct.spec/temp.deduct/p7.cpp
+++ b/test/CXX/temp/temp.fct.spec/temp.deduct/p7.cpp
@@ -1,4 +1,5 @@
 // RUN: %clang_cc1 -std=c++11 -verify %s
+// RUN: %clang_cc1 -std=c++2a -verify %s
 
 struct Q { typedef int type; };
 
@@ -20,3 +21,36 @@ template<typename T, template<typename T::type...> class ...X> void c(T);
 int &c(...);
 int &c_disabled = c(0);
 int &c_enabled = c(Q()); // expected-error {{cannot bind to a temporary of type 'void'}}
+
+// The substitution proceeds in lexical order and stops when a condition that
+// causes deduction to fail is encountered.
+#if __cplusplus > 201702L
+namespace reversed_operator_substitution_order {
+  struct X { X(int); };
+  struct Y { Y(int); };
+  struct Cat {};
+  namespace no_adl {
+    Cat operator<=>(Y, X);
+    bool operator<(int, Cat);
+
+    template<typename T> struct indirect_sizeof {
+      static_assert(sizeof(T) != 0);
+      static const auto value = sizeof(T);
+    };
+
+    // We should substitute into the construction of the X object before the
+    // construction of the Y object, so this is a SFINAE case rather than a
+    // hard error. This requires substitution to proceed in lexical order
+    // despite the prior rewrite to
+    //    0 < (Y(...) <=> X(...))
+    template<typename T> float &f(
+        decltype(
+          X(sizeof(T)) < Y(indirect_sizeof<T>::value)
+        )
+    );
+    template<typename T> int &f(...);
+  }
+  int &r = no_adl::f<void>(true);
+  float &s = no_adl::f<int>(true);
+}
+#endif
diff --git a/test/CodeGenCXX/mangle-cxx2a.cpp b/test/CodeGenCXX/mangle-cxx2a.cpp
new file mode 100644
index 0000000000..3e4689948a
--- /dev/null
+++ b/test/CodeGenCXX/mangle-cxx2a.cpp
@@ -0,0 +1,11 @@
+// RUN: %clang_cc1 -emit-llvm %s -o - -triple=x86_64-linux-gnu -std=c++2a | FileCheck %s
+
+namespace spaceship {
+  struct X {};
+  struct Y {};
+  int operator<=>(X, Y);
+
+  // CHECK-LABEL: define {{.*}} @_ZN9spaceship1fIiEEvDTcmltcvNS_1YE_EcvNS_1XE_EcvT__EE
+  template<typename T> void f(decltype(Y() < X(), T()) x) {}
+  template void f<int>(int);
+}
diff --git a/test/PCH/cxx2a-compare.cpp b/test/PCH/cxx2a-compare.cpp
index 9ad368d88f..019544d28c 100644
--- a/test/PCH/cxx2a-compare.cpp
+++ b/test/PCH/cxx2a-compare.cpp
@@ -15,6 +15,16 @@ inline auto bar(int x) {
   return (1 <=> x);
 }
 
+struct X {
+  int a;
+  friend constexpr std::strong_ordering operator<=>(const X &x, const X &y) {
+    return x.a <=> y.a;
+  }
+};
+constexpr auto baz(int x) {
+  return X{3} < X{x};
+}
+
 #else
 
 // expected-no-diagnostics
@@ -25,4 +35,7 @@ auto bar2(int x) {
   return bar(x);
 }
 
+static_assert(!baz(3));
+static_assert(baz(4));
+
 #endif
diff --git a/test/SemaCXX/compare-cxx2a.cpp b/test/SemaCXX/compare-cxx2a.cpp
index b6e7fc8061..28854a77fb 100644
--- a/test/SemaCXX/compare-cxx2a.cpp
+++ b/test/SemaCXX/compare-cxx2a.cpp
@@ -298,11 +298,11 @@ void test_enum_enum_compare_no_builtin() {
 
 template <int>
 struct Tag {};
-// expected-note@+1 {{candidate}}
-Tag<0> operator<=>(EnumA, EnumA) {
+Tag<0> operator<=>(EnumA, EnumA) { // expected-note {{not viable}}
   return {};
 }
-Tag<1> operator<=>(EnumA, EnumB) {
+// expected-note@+1 {{while rewriting comparison as call to 'operator<=>' declared here}}
+Tag<1> operator<=>(EnumA, EnumB) { // expected-note {{not viable}}
   return {};
 }
 
@@ -311,7 +311,7 @@ void test_enum_ovl_provided() {
   ASSERT_EXPR_TYPE(r1, Tag<0>);
   auto r2 = (EnumA::A <=> EnumB::B);
   ASSERT_EXPR_TYPE(r2, Tag<1>);
-  (void)(EnumB::B <=> EnumA::A); // expected-error {{invalid operands to binary expression ('EnumCompareTests::EnumB' and 'EnumCompareTests::EnumA')}}
+  (void)(EnumB::B <=> EnumA::A); // expected-error {{invalid operands to binary expression ('int' and 'Tag<1>')}}
 }
 
 void enum_float_test() {
diff --git a/test/SemaCXX/self-comparison.cpp b/test/SemaCXX/self-comparison.cpp
index e20706a8b6..95b830c910 100644
--- a/test/SemaCXX/self-comparison.cpp
+++ b/test/SemaCXX/self-comparison.cpp
@@ -5,7 +5,7 @@ int foo(int x) {
 }
 
 struct X {
-  bool operator==(const X &x);
+  bool operator==(const X &x) const;
 };
 
 struct A {