[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

5 files changed, 188 insertions, 63 deletions

diff --git a/include/clang/AST/ExprCXX.h b/include/clang/AST/ExprCXX.h
index 2b3085183c..7b7ca9bf8f 100644
--- a/include/clang/AST/ExprCXX.h
+++ b/include/clang/AST/ExprCXX.h
@@ -220,6 +220,40 @@ public:
   }
 };
 
+/// Represents a call to a CUDA kernel function.
+class CUDAKernelCallExpr final : public CallExpr {
+  friend class ASTStmtReader;
+
+  enum { CONFIG, END_PREARG };
+
+  // CUDAKernelCallExpr has some trailing objects belonging
+  // to CallExpr. See CallExpr for the details.
+
+  CUDAKernelCallExpr(Expr *Fn, CallExpr *Config, ArrayRef<Expr *> Args,
+                     QualType Ty, ExprValueKind VK, SourceLocation RP,
+                     unsigned MinNumArgs);
+
+  CUDAKernelCallExpr(unsigned NumArgs, EmptyShell Empty);
+
+public:
+  static CUDAKernelCallExpr *Create(const ASTContext &Ctx, Expr *Fn,
+                                    CallExpr *Config, ArrayRef<Expr *> Args,
+                                    QualType Ty, ExprValueKind VK,
+                                    SourceLocation RP, unsigned MinNumArgs = 0);
+
+  static CUDAKernelCallExpr *CreateEmpty(const ASTContext &Ctx,
+                                         unsigned NumArgs, EmptyShell Empty);
+
+  const CallExpr *getConfig() const {
+    return cast_or_null<CallExpr>(getPreArg(CONFIG));
+  }
+  CallExpr *getConfig() { return cast_or_null<CallExpr>(getPreArg(CONFIG)); }
+
+  static bool classof(const Stmt *T) {
+    return T->getStmtClass() == CUDAKernelCallExprClass;
+  }
+};
+
 /// A rewritten comparison expression that was originally written using
 /// operator syntax.
 ///
@@ -310,40 +344,6 @@ public:
   }
 };
 
-/// Represents a call to a CUDA kernel function.
-class CUDAKernelCallExpr final : public CallExpr {
-  friend class ASTStmtReader;
-
-  enum { CONFIG, END_PREARG };
-
-  // CUDAKernelCallExpr has some trailing objects belonging
-  // to CallExpr. See CallExpr for the details.
-
-  CUDAKernelCallExpr(Expr *Fn, CallExpr *Config, ArrayRef<Expr *> Args,
-                     QualType Ty, ExprValueKind VK, SourceLocation RP,
-                     unsigned MinNumArgs);
-
-  CUDAKernelCallExpr(unsigned NumArgs, EmptyShell Empty);
-
-public:
-  static CUDAKernelCallExpr *Create(const ASTContext &Ctx, Expr *Fn,
-                                    CallExpr *Config, ArrayRef<Expr *> Args,
-                                    QualType Ty, ExprValueKind VK,
-                                    SourceLocation RP, unsigned MinNumArgs = 0);
-
-  static CUDAKernelCallExpr *CreateEmpty(const ASTContext &Ctx,
-                                         unsigned NumArgs, EmptyShell Empty);
-
-  const CallExpr *getConfig() const {
-    return cast_or_null<CallExpr>(getPreArg(CONFIG));
-  }
-  CallExpr *getConfig() { return cast_or_null<CallExpr>(getPreArg(CONFIG)); }
-
-  static bool classof(const Stmt *T) {
-    return T->getStmtClass() == CUDAKernelCallExprClass;
-  }
-};
-
 /// Abstract class common to all of the C++ "named"/"keyword" casts.
 ///
 /// This abstract class is inherited by all of the classes
diff --git a/include/clang/Basic/DiagnosticSemaKinds.td b/include/clang/Basic/DiagnosticSemaKinds.td
index 755fac842d..e41cfe2fe7 100644
--- a/include/clang/Basic/DiagnosticSemaKinds.td
+++ b/include/clang/Basic/DiagnosticSemaKinds.td
@@ -3769,7 +3769,8 @@ def note_ovl_too_many_candidates : Note<
     "pass -fshow-overloads=all to show them">;
 
 def select_ovl_candidate_kind : TextSubstitution<
-  "%select{function|function|constructor|"
+  "%select{function|function|function (with reversed parameter order)|"
+    "constructor|"
     "constructor (the implicit default constructor)|"
     "constructor (the implicit copy constructor)|"
     "constructor (the implicit move constructor)|"
@@ -3990,6 +3991,13 @@ def err_ovl_ambiguous_oper_unary : Error<
   "use of overloaded operator '%0' is ambiguous (operand type %1)">;
 def err_ovl_ambiguous_oper_binary : Error<
   "use of overloaded operator '%0' is ambiguous (with operand types %1 and %2)">;
+def ext_ovl_ambiguous_oper_binary_reversed : ExtWarn<
+  "ISO C++20 considers use of overloaded operator '%0' (with operand types %1 "
+  "and %2) to be ambiguous despite there being a unique best viable function">,
+  InGroup<DiagGroup<"ambiguous-reversed-operator">>, SFINAEFailure;
+def note_ovl_ambiguous_oper_binary_reversed_candidate : Note<
+  "ambiguity is between a regular call to this operator and a call with the "
+  "argument order reversed">;
 def err_ovl_no_viable_oper : Error<"no viable overloaded '%0'">;
 def note_assign_lhs_incomplete : Note<"type %0 is incomplete">;
 def err_ovl_deleted_oper : Error<
@@ -3997,6 +4005,9 @@ def err_ovl_deleted_oper : Error<
 def err_ovl_deleted_special_oper : Error<
   "object of type %0 cannot be %select{constructed|copied|moved|assigned|"
   "assigned|destroyed}1 because its %sub{select_special_member_kind}1 is implicitly deleted">;
+def err_ovl_rewrite_equalequal_not_bool : Error<
+  "return type %0 of selected 'operator==' function for rewritten "
+  "'%1' comparison is not 'bool'">;
 def err_ovl_no_viable_subscript :
     Error<"no viable overloaded operator[] for type %0">;
 def err_ovl_no_oper :
@@ -9961,6 +9972,8 @@ def err_std_compare_type_not_supported : Error<
    "member '%2' is missing|"
    "the type is not trivially copyable|"
    "the type does not have the expected form}1">;
+def note_rewriting_operator_as_spaceship : Note<
+  "while rewriting comparison as call to 'operator<=>' declared here">;
 
 // Memory Tagging Extensions (MTE) diagnostics
 def err_memtag_arg_null_or_pointer : Error<
diff --git a/include/clang/Basic/OperatorKinds.h b/include/clang/Basic/OperatorKinds.h
index 9757acaa53..d661891445 100644
--- a/include/clang/Basic/OperatorKinds.h
+++ b/include/clang/Basic/OperatorKinds.h
@@ -30,6 +30,25 @@ enum OverloadedOperatorKind : int {
 /// the preceding "operator" keyword.
 const char *getOperatorSpelling(OverloadedOperatorKind Operator);
 
+/// Get the other overloaded operator that the given operator can be rewritten
+/// into, if any such operator exists.
+inline OverloadedOperatorKind
+getRewrittenOverloadedOperator(OverloadedOperatorKind Kind) {
+  switch (Kind) {
+  case OO_Less:
+  case OO_LessEqual:
+  case OO_Greater:
+  case OO_GreaterEqual:
+    return OO_Spaceship;
+
+  case OO_ExclaimEqual:
+    return OO_EqualEqual;
+
+  default:
+    return OO_None;
+  }
+}
+
 } // end namespace clang
 
 #endif
diff --git a/include/clang/Sema/Overload.h b/include/clang/Sema/Overload.h
index 144e6d927c..a97a7181f7 100644
--- a/include/clang/Sema/Overload.h
+++ b/include/clang/Sema/Overload.h
@@ -71,6 +71,30 @@ class Sema;
     OCD_ViableCandidates
   };
 
+  /// The parameter ordering that will be used for the candidate. This is
+  /// used to represent C++20 binary operator rewrites that reverse the order
+  /// of the arguments. If the parameter ordering is Reversed, the Args list is
+  /// reversed (but obviously the ParamDecls for the function are not).
+  ///
+  /// After forming an OverloadCandidate with reversed parameters, the list
+  /// of conversions will (as always) be indexed by argument, so will be
+  /// in reverse parameter order.
+  enum class OverloadCandidateParamOrder : char { Normal, Reversed };
+
+  /// The kinds of rewrite we perform on overload candidates. Note that the
+  /// values here are chosen to serve as both bitflags and as a rank (lower
+  /// values are preferred by overload resolution).
+  enum OverloadCandidateRewriteKind : unsigned {
+    /// Candidate is not a rewritten candidate.
+    CRK_None = 0x0,
+
+    /// Candidate is a rewritten candidate with a different operator name.
+    CRK_DifferentOperator = 0x1,
+
+    /// Candidate is a rewritten candidate with a reversed order of parameters.
+    CRK_Reversed = 0x2,
+  };
+
   /// ImplicitConversionKind - The kind of implicit conversion used to
   /// convert an argument to a parameter's type. The enumerator values
   /// match with the table titled 'Conversions' in [over.ics.scs] and are listed
@@ -757,7 +781,8 @@ class Sema;
     CXXConversionDecl *Surrogate;
 
     /// The conversion sequences used to convert the function arguments
-    /// to the function parameters.
+    /// to the function parameters. Note that these are indexed by argument,
+    /// so may not match the parameter order of Function.
     ConversionSequenceList Conversions;
 
     /// The FixIt hints which can be used to fix the Bad candidate.
@@ -783,6 +808,9 @@ class Sema;
     /// True if the candidate was found using ADL.
     CallExpr::ADLCallKind IsADLCandidate : 1;
 
+    /// Whether this is a rewritten candidate, and if so, of what kind?
+    OverloadCandidateRewriteKind RewriteKind : 2;
+
     /// FailureKind - The reason why this candidate is not viable.
     /// Actually an OverloadFailureKind.
     unsigned char FailureKind;
@@ -838,7 +866,8 @@ class Sema;
 
   private:
     friend class OverloadCandidateSet;
-    OverloadCandidate() : IsADLCandidate(CallExpr::NotADL) {}
+    OverloadCandidate()
+        : IsADLCandidate(CallExpr::NotADL), RewriteKind(CRK_None) {}
   };
 
   /// OverloadCandidateSet - A set of overload candidates, used in C++
@@ -867,9 +896,54 @@ class Sema;
       CSK_InitByConstructor,
     };
 
+    /// Information about operator rewrites to consider when adding operator
+    /// functions to a candidate set.
+    struct OperatorRewriteInfo {
+      OperatorRewriteInfo()
+          : OriginalOperator(OO_None), AllowRewrittenCandidates(false) {}
+      OperatorRewriteInfo(OverloadedOperatorKind Op, bool AllowRewritten)
+          : OriginalOperator(Op), AllowRewrittenCandidates(AllowRewritten) {}
+
+      /// The original operator as written in the source.
+      OverloadedOperatorKind OriginalOperator;
+      /// Whether we should include rewritten candidates in the overload set.
+      bool AllowRewrittenCandidates;
+
+      /// Would use of this function result in a rewrite using a different
+      /// operator?
+      bool isRewrittenOperator(const FunctionDecl *FD) {
+        return OriginalOperator &&
+               FD->getDeclName().getCXXOverloadedOperator() != OriginalOperator;
+      }
+
+      bool isAcceptableCandidate(const FunctionDecl *FD) {
+        return AllowRewrittenCandidates || !isRewrittenOperator(FD);
+      }
+
+      /// Determine the kind of rewrite that should be performed for this
+      /// candidate.
+      OverloadCandidateRewriteKind
+      getRewriteKind(const FunctionDecl *FD, OverloadCandidateParamOrder PO) {
+        OverloadCandidateRewriteKind CRK = CRK_None;
+        if (isRewrittenOperator(FD))
+          CRK = OverloadCandidateRewriteKind(CRK | CRK_DifferentOperator);
+        if (PO == OverloadCandidateParamOrder::Reversed)
+          CRK = OverloadCandidateRewriteKind(CRK | CRK_Reversed);
+        return CRK;
+      }
+
+      /// Determine whether we should consider looking for and adding reversed
+      /// candidates for operator Op.
+      bool shouldAddReversed(OverloadedOperatorKind Op);
+
+      /// Determine whether we should add a rewritten candidate for \p FD with
+      /// reversed parameter order.
+      bool shouldAddReversed(ASTContext &Ctx, const FunctionDecl *FD);
+    };
+
   private:
     SmallVector<OverloadCandidate, 16> Candidates;
-    llvm::SmallPtrSet<Decl *, 16> Functions;
+    llvm::SmallPtrSet<uintptr_t, 16> Functions;
 
     // Allocator for ConversionSequenceLists. We store the first few of these
     // inline to avoid allocation for small sets.
@@ -877,6 +951,7 @@ class Sema;
 
     SourceLocation Loc;
     CandidateSetKind Kind;
+    OperatorRewriteInfo RewriteInfo;
 
     constexpr static unsigned NumInlineBytes =
         24 * sizeof(ImplicitConversionSequence);
@@ -915,19 +990,24 @@ class Sema;
     void destroyCandidates();
 
   public:
-    OverloadCandidateSet(SourceLocation Loc, CandidateSetKind CSK)
-        : Loc(Loc), Kind(CSK) {}
+    OverloadCandidateSet(SourceLocation Loc, CandidateSetKind CSK,
+                         OperatorRewriteInfo RewriteInfo = {})
+        : Loc(Loc), Kind(CSK), RewriteInfo(RewriteInfo) {}
     OverloadCandidateSet(const OverloadCandidateSet &) = delete;
     OverloadCandidateSet &operator=(const OverloadCandidateSet &) = delete;
     ~OverloadCandidateSet() { destroyCandidates(); }
 
     SourceLocation getLocation() const { return Loc; }
     CandidateSetKind getKind() const { return Kind; }
+    OperatorRewriteInfo getRewriteInfo() const { return RewriteInfo; }
 
     /// Determine when this overload candidate will be new to the
     /// overload set.
-    bool isNewCandidate(Decl *F) {
-      return Functions.insert(F->getCanonicalDecl()).second;
+    bool isNewCandidate(Decl *F, OverloadCandidateParamOrder PO =
+                                     OverloadCandidateParamOrder::Normal) {
+      uintptr_t Key = reinterpret_cast<uintptr_t>(F->getCanonicalDecl());
+      Key |= static_cast<uintptr_t>(PO);
+      return Functions.insert(Key).second;
     }
 
     /// Clear out all of the candidates.
diff --git a/include/clang/Sema/Sema.h b/include/clang/Sema/Sema.h
index d3481af50a..1e3d6b93d0 100644
--- a/include/clang/Sema/Sema.h
+++ b/include/clang/Sema/Sema.h
@@ -159,6 +159,8 @@ namespace clang {
   class OMPClause;
   struct OMPVarListLocTy;
   struct OverloadCandidate;
+  enum class OverloadCandidateParamOrder : char;
+  enum OverloadCandidateRewriteKind : unsigned;
   class OverloadCandidateSet;
   class OverloadExpr;
   class ParenListExpr;
@@ -3019,7 +3021,8 @@ public:
                             bool AllowExplicit = true,
                             bool AllowExplicitConversion = false,
                             ADLCallKind IsADLCandidate = ADLCallKind::NotADL,
-                            ConversionSequenceList EarlyConversions = None);
+                            ConversionSequenceList EarlyConversions = None,
+                            OverloadCandidateParamOrder PO = {});
   void AddFunctionCandidates(const UnresolvedSetImpl &Functions,
                       ArrayRef<Expr *> Args,
                       OverloadCandidateSet &CandidateSet,
@@ -3032,7 +3035,8 @@ public:
                           Expr::Classification ObjectClassification,
                           ArrayRef<Expr *> Args,
                           OverloadCandidateSet& CandidateSet,
-                          bool SuppressUserConversion = false);
+                          bool SuppressUserConversion = false,
+                          OverloadCandidateParamOrder PO = {});
   void AddMethodCandidate(CXXMethodDecl *Method,
                           DeclAccessPair FoundDecl,
                           CXXRecordDecl *ActingContext, QualType ObjectType,
@@ -3041,7 +3045,8 @@ public:
                           OverloadCandidateSet& CandidateSet,
                           bool SuppressUserConversions = false,
                           bool PartialOverloading = false,
-                          ConversionSequenceList EarlyConversions = None);
+                          ConversionSequenceList EarlyConversions = None,
+                          OverloadCandidateParamOrder PO = {});
   void AddMethodTemplateCandidate(FunctionTemplateDecl *MethodTmpl,
                                   DeclAccessPair FoundDecl,
                                   CXXRecordDecl *ActingContext,
@@ -3051,23 +3056,22 @@ public:
                                   ArrayRef<Expr *> Args,
                                   OverloadCandidateSet& CandidateSet,
                                   bool SuppressUserConversions = false,
-                                  bool PartialOverloading = false);
+                                  bool PartialOverloading = false,
+                                  OverloadCandidateParamOrder PO = {});
   void AddTemplateOverloadCandidate(
       FunctionTemplateDecl *FunctionTemplate, DeclAccessPair FoundDecl,
       TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
       OverloadCandidateSet &CandidateSet, bool SuppressUserConversions = false,
       bool PartialOverloading = false, bool AllowExplicit = true,
-      ADLCallKind IsADLCandidate = ADLCallKind::NotADL);
-  bool CheckNonDependentConversions(FunctionTemplateDecl *FunctionTemplate,
-                                    ArrayRef<QualType> ParamTypes,
-                                    ArrayRef<Expr *> Args,
-                                    OverloadCandidateSet &CandidateSet,
-                                    ConversionSequenceList &Conversions,
-                                    bool SuppressUserConversions,
-                                    CXXRecordDecl *ActingContext = nullptr,
-                                    QualType ObjectType = QualType(),
-                                    Expr::Classification
-                                        ObjectClassification = {});
+      ADLCallKind IsADLCandidate = ADLCallKind::NotADL,
+      OverloadCandidateParamOrder PO = {});
+  bool CheckNonDependentConversions(
+      FunctionTemplateDecl *FunctionTemplate, ArrayRef<QualType> ParamTypes,
+      ArrayRef<Expr *> Args, OverloadCandidateSet &CandidateSet,
+      ConversionSequenceList &Conversions, bool SuppressUserConversions,
+      CXXRecordDecl *ActingContext = nullptr, QualType ObjectType = QualType(),
+      Expr::Classification ObjectClassification = {},
+      OverloadCandidateParamOrder PO = {});
   void AddConversionCandidate(
       CXXConversionDecl *Conversion, DeclAccessPair FoundDecl,
       CXXRecordDecl *ActingContext, Expr *From, QualType ToType,
@@ -3084,10 +3088,14 @@ public:
                              const FunctionProtoType *Proto,
                              Expr *Object, ArrayRef<Expr *> Args,
                              OverloadCandidateSet& CandidateSet);
+  void AddNonMemberOperatorCandidates(
+      const UnresolvedSetImpl &Functions, ArrayRef<Expr *> Args,
+      OverloadCandidateSet &CandidateSet,
+      TemplateArgumentListInfo *ExplicitTemplateArgs = nullptr);
   void AddMemberOperatorCandidates(OverloadedOperatorKind Op,
                                    SourceLocation OpLoc, ArrayRef<Expr *> Args,
-                                   OverloadCandidateSet& CandidateSet,
-                                   SourceRange OpRange = SourceRange());
+                                   OverloadCandidateSet &CandidateSet,
+                                   OverloadCandidateParamOrder PO = {});
   void AddBuiltinCandidate(QualType *ParamTys, ArrayRef<Expr *> Args,
                            OverloadCandidateSet& CandidateSet,
                            bool IsAssignmentOperator = false,
@@ -3103,9 +3111,10 @@ public:
                                             bool PartialOverloading = false);
 
   // Emit as a 'note' the specific overload candidate
-  void NoteOverloadCandidate(NamedDecl *Found, FunctionDecl *Fn,
-                             QualType DestType = QualType(),
-                             bool TakingAddress = false);
+  void NoteOverloadCandidate(
+      NamedDecl *Found, FunctionDecl *Fn,
+      OverloadCandidateRewriteKind RewriteKind = OverloadCandidateRewriteKind(),
+      QualType DestType = QualType(), bool TakingAddress = false);
 
   // Emit as a series of 'note's all template and non-templates identified by
   // the expression Expr
@@ -3237,7 +3246,8 @@ public:
                                    BinaryOperatorKind Opc,
                                    const UnresolvedSetImpl &Fns,
                                    Expr *LHS, Expr *RHS,
-                                   bool RequiresADL = true);
+                                   bool RequiresADL = true,
+                                   bool AllowRewrittenCandidates = true);
 
   ExprResult CreateOverloadedArraySubscriptExpr(SourceLocation LLoc,
                                                 SourceLocation RLoc,
@@ -7665,6 +7675,9 @@ public:
       // We are substituting template arguments into a constraint expression.
       ConstraintSubstitution,
 
+      /// We are rewriting a comparison operator in terms of an operator<=>.
+      RewritingOperatorAsSpaceship,
+
       /// Added for Template instantiation observation.
       /// Memoization means we are _not_ instantiating a template because
       /// it is already instantiated (but we entered a context where we