Added missing unqualified name lookup of operator overloads for fold expressions

[jonathanmeier]

Summary

Valid operator overloads for fold expressions are not found in the current scope, since unqualified name lookup is not performed.

This is a proposal to fix Bug 30590 (and its duplicates Bug 30738 and Bug 42518). The core issue is that fold expressions get expanded during template instantiation (second phase of name lookup) when the current scope is not available anymore (current scope is available in the first phase of name lookup, i.e. while parsing the template definition).

My approach is to attach to the fold expression the operator overload candidates found by the unqualified name lookup while parsing. During template instantiation these candidates are then considered when the fold expressions are expanded and the actual binary operations are built.

Please comment on whether you deem this a reasonable approach or if you know of a better way of solving the issue.

[jonathanmeier]

ping @rsmith

[jonathanmeier]

• Rebased to adapt to the latest changes for spaceship operator and comparison operator rewrite support in rL375305 and rL375306.
• Added tests for comparison operator rewrites in fold expressions.
• Changed to using llvm::iterator_range instead of separate begin/end iterators.

ping @rsmith

clang/include/clang/AST/ExprCXX.h

 /// Represents a folding of a pack over an operator.
 ///
 /// This expression is always dependent and represents a pack expansion of the
 /// forms:
 ///
 ///    ( expr op ... )
 ///    ( ... op expr )
 ///    ( expr op ... op expr )
-class CXXFoldExpr : public Expr {
+class CXXFoldExpr final
+    : public Expr,
+      private llvm::TrailingObjects<CXXFoldExpr, DeclAccessPair> {
   friend class ASTStmtReader;
   friend class ASTStmtWriter;
 
   SourceLocation LParenLoc;
   SourceLocation EllipsisLoc;
   SourceLocation RParenLoc;
   // When 0, the number of expansions is not known. Otherwise, this is one more
   // than the number of expansions.
   unsigned NumExpansions;
   Stmt *SubExprs[2];
   BinaryOperatorKind Opcode;
 
-public:
+  unsigned NumOverloadCands;
+
   CXXFoldExpr(QualType T, SourceLocation LParenLoc, Expr *LHS,
               BinaryOperatorKind Opcode, SourceLocation EllipsisLoc, Expr *RHS,
-              SourceLocation RParenLoc, Optional<unsigned> NumExpansions)
+              SourceLocation RParenLoc, Optional<unsigned> NumExpansions,
+              llvm::iterator_range<UnresolvedSetIterator> OverloadCands)
       : Expr(CXXFoldExprClass, T, VK_RValue, OK_Ordinary,
              /*Dependent*/ true, true, true,
              /*ContainsUnexpandedParameterPack*/ false),
         LParenLoc(LParenLoc), EllipsisLoc(EllipsisLoc), RParenLoc(RParenLoc),
-        NumExpansions(NumExpansions ? *NumExpansions + 1 : 0), Opcode(Opcode) {
+        NumExpansions(NumExpansions ? *NumExpansions + 1 : 0), Opcode(Opcode),
+        NumOverloadCands(
+            std::distance(OverloadCands.begin(), OverloadCands.end())) {
     SubExprs[0] = LHS;
     SubExprs[1] = RHS;
+    DeclAccessPair *Results = getTrailingObjects<DeclAccessPair>();
+    memcpy(Results, OverloadCands.begin().I,
+           NumOverloadCands * sizeof(DeclAccessPair));
+  }
+
+  CXXFoldExpr(EmptyShell Empty, unsigned NumOverloadCands)
+      : Expr(CXXFoldExprClass, Empty), NumOverloadCands(NumOverloadCands) {}
+
+public:
+  static CXXFoldExpr *
+  Create(const ASTContext &Ctx, QualType T, SourceLocation LParenLoc, Expr *LHS,
+         BinaryOperatorKind Opcode, SourceLocation EllipsisLoc, Expr *RHS,
+         SourceLocation RParenLoc, Optional<unsigned> NumExpansions,
+         llvm::iterator_range<UnresolvedSetIterator> OverloadCands) {
+    unsigned Size = CXXFoldExpr::totalSizeToAlloc<DeclAccessPair>(
+        std::distance(OverloadCands.begin(), OverloadCands.end()));
+    void *Mem = Ctx.Allocate(Size, alignof(CXXFoldExpr));
+    return new (Mem) CXXFoldExpr(T, LParenLoc, LHS, Opcode, EllipsisLoc, RHS,
+                                 RParenLoc, NumExpansions, OverloadCands);
   }
 
-  CXXFoldExpr(EmptyShell Empty) : Expr(CXXFoldExprClass, Empty) {}
+  static CXXFoldExpr *CreateEmpty(const ASTContext &Ctx,
+                                  unsigned NumOverloadCands) {
+    unsigned Size =
+        CXXFoldExpr::totalSizeToAlloc<DeclAccessPair>(NumOverloadCands);
+    void *Mem = Ctx.Allocate(Size, alignof(CXXFoldExpr));
+    return new (Mem) CXXFoldExpr(EmptyShell(), NumOverloadCands);
+  }
 
   Expr *getLHS() const { return static_cast<Expr*>(SubExprs[0]); }
   Expr *getRHS() const { return static_cast<Expr*>(SubExprs[1]); }
 
+  unsigned getNumOverloadCands() { return NumOverloadCands; }
+
+  unsigned numTrailingObjects(OverloadToken<DeclAccessPair>) {
+    return getNumOverloadCands();
+  }
+
+  llvm::iterator_range<UnresolvedSetIterator> overloadCands() const {
+    auto Begin = UnresolvedSetIterator(getTrailingObjects<DeclAccessPair>());
+    return llvm::make_range(Begin, Begin + NumOverloadCands);
+  }
+
   /// Does this produce a right-associated sequence of operators?
   bool isRightFold() const {
     return getLHS() && getLHS()->containsUnexpandedParameterPack();
   }
 
   /// Does this produce a left-associated sequence of operators?
   bool isLeftFold() const { return !isRightFold(); }
 

clang/include/clang/AST/UnresolvedSet.h

 
 /// The iterator over UnresolvedSets.  Serves as both the const and
 /// non-const iterator.
 class UnresolvedSetIterator : public llvm::iterator_adaptor_base<
                                   UnresolvedSetIterator, DeclAccessPair *,
                                   std::random_access_iterator_tag, NamedDecl *,
                                   std::ptrdiff_t, NamedDecl *, NamedDecl *> {
   friend class ASTUnresolvedSet;
+  friend class CXXFoldExpr;
   friend class OverloadExpr;
   friend class UnresolvedSetImpl;
 
   explicit UnresolvedSetIterator(DeclAccessPair *Iter)
       : iterator_adaptor_base(Iter) {}
   explicit UnresolvedSetIterator(const DeclAccessPair *Iter)
       : iterator_adaptor_base(const_cast<DeclAccessPair *>(Iter)) {}
 

clang/include/clang/Sema/Sema.h

bool LookupParsedName(LookupResult &R, Scope *S, CXXScopeSpec *SS,
                         bool AllowBuiltinCreation = false,
                         bool EnteringContext = false);
   ObjCProtocolDecl *LookupProtocol(IdentifierInfo *II, SourceLocation IdLoc,
                                    RedeclarationKind Redecl
                                      = NotForRedeclaration);
   bool LookupInSuper(LookupResult &R, CXXRecordDecl *Class);
 
   void LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S,
-                                    QualType T1, QualType T2,
                                     UnresolvedSetImpl &Functions);
 
   LabelDecl *LookupOrCreateLabel(IdentifierInfo *II, SourceLocation IdentLoc,
                                  SourceLocation GnuLabelLoc = SourceLocation());
 
   DeclContextLookupResult LookupConstructors(CXXRecordDecl *Class);
   CXXConstructorDecl *LookupDefaultConstructor(CXXRecordDecl *Class);
   CXXConstructorDecl *LookupCopyingConstructor(CXXRecordDecl *Class,
ExprResult ActOnDesignatedInitializer(Designation &Desig,
                                         ExprResult Init);
 
 private:
   static BinaryOperatorKind ConvertTokenKindToBinaryOpcode(tok::TokenKind Kind);
 
 public:
   ExprResult ActOnBinOp(Scope *S, SourceLocation TokLoc,
                         tok::TokenKind Kind, Expr *LHSExpr, Expr *RHSExpr);
-  ExprResult BuildBinOp(Scope *S, SourceLocation OpLoc,
-                        BinaryOperatorKind Opc, Expr *LHSExpr, Expr *RHSExpr);
+  ExprResult BuildBinOp(Scope *S, SourceLocation OpLoc, BinaryOperatorKind Opc,
+                        Expr *LHSExpr, Expr *RHSExpr,
+                        const UnresolvedSetImpl *OverloadCands = nullptr);
   ExprResult CreateBuiltinBinOp(SourceLocation OpLoc, BinaryOperatorKind Opc,
                                 Expr *LHSExpr, Expr *RHSExpr);
 
   void DiagnoseCommaOperator(const Expr *LHS, SourceLocation Loc);
 
   /// ActOnConditionalOp - Parse a ?: operation.  Note that 'LHS' may be null
   /// in the case of a the GNU conditional expr extension.
   ExprResult ActOnConditionalOp(SourceLocation QuestionLoc,
public:
 
   /// ActOnCXXUuidof - Parse __uuidof( something ).
   ExprResult ActOnCXXUuidof(SourceLocation OpLoc,
                             SourceLocation LParenLoc, bool isType,
                             void *TyOrExpr,
                             SourceLocation RParenLoc);
 
   /// Handle a C++1z fold-expression: ( expr op ... op expr ).
-  ExprResult ActOnCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
+  ExprResult ActOnCXXFoldExpr(Scope *Sc, SourceLocation LParenLoc, Expr *LHS,
                               tok::TokenKind Operator,
                               SourceLocation EllipsisLoc, Expr *RHS,
                               SourceLocation RParenLoc);
-  ExprResult BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
-                              BinaryOperatorKind Operator,
-                              SourceLocation EllipsisLoc, Expr *RHS,
-                              SourceLocation RParenLoc,
-                              Optional<unsigned> NumExpansions);
+  ExprResult
+  BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
+                   BinaryOperatorKind Operator, SourceLocation EllipsisLoc,
+                   Expr *RHS, SourceLocation RParenLoc,
+                   Optional<unsigned> NumExpansions,
+                   llvm::iterator_range<UnresolvedSetIterator> OverloadCands);
   ExprResult BuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
                                    BinaryOperatorKind Operator);
 
   //// ActOnCXXThis -  Parse 'this' pointer.
   ExprResult ActOnCXXThis(SourceLocation loc);
 
   /// Build a CXXThisExpr and mark it referenced in the current context.
   Expr *BuildCXXThisExpr(SourceLocation Loc, QualType Type, bool IsImplicit);

clang/lib/Parse/ParseExpr.cpp

if (Tok.isNot(tok::r_paren)) {
     }
   }
 
   Diag(EllipsisLoc, getLangOpts().CPlusPlus17
                         ? diag::warn_cxx14_compat_fold_expression
                         : diag::ext_fold_expression);
 
   T.consumeClose();
-  return Actions.ActOnCXXFoldExpr(T.getOpenLocation(), LHS.get(), Kind,
-                                  EllipsisLoc, RHS.get(), T.getCloseLocation());
+  return Actions.ActOnCXXFoldExpr(getCurScope(), T.getOpenLocation(), LHS.get(),
+                                  Kind, EllipsisLoc, RHS.get(),
+                                  T.getCloseLocation());
 }
 
 /// ParseExpressionList - Used for C/C++ (argument-)expression-list.
 ///
 /// \verbatim
 ///       argument-expression-list:
 ///         assignment-expression
 ///         argument-expression-list , assignment-expression

clang/lib/Sema/SemaExpr.cpp

ExprResult Sema::ActOnBinOp(Scope *S, SourceLocation TokLoc,
   // Emit warnings for tricky precedence issues, e.g. "bitfield & 0x4 == 0"
   DiagnoseBinOpPrecedence(*this, Opc, TokLoc, LHSExpr, RHSExpr);
 
   return BuildBinOp(S, TokLoc, Opc, LHSExpr, RHSExpr);
 }
 
 /// Build an overloaded binary operator expression in the given scope.
 static ExprResult BuildOverloadedBinOp(Sema &S, Scope *Sc, SourceLocation OpLoc,
-                                       BinaryOperatorKind Opc,
-                                       Expr *LHS, Expr *RHS) {
+                                       BinaryOperatorKind Opc, Expr *LHS,
+                                       Expr *RHS,
+                                       const UnresolvedSetImpl *OverloadCands) {
   switch (Opc) {
   case BO_Assign:
   case BO_DivAssign:
   case BO_RemAssign:
   case BO_SubAssign:
   case BO_AndAssign:
   case BO_OrAssign:
   case BO_XorAssign:
     DiagnoseSelfAssignment(S, LHS, RHS, OpLoc, false);
     CheckIdentityFieldAssignment(LHS, RHS, OpLoc, S);
     break;
   default:
     break;
   }
 
+  UnresolvedSet<16> Functions;
+  if (OverloadCands)
+    Functions.append(OverloadCands->begin(), OverloadCands->end());
+
   // Find all of the overloaded operators visible from this
   // point. We perform both an operator-name lookup from the local
   // scope and an argument-dependent lookup based on the types of
   // the arguments.
-  UnresolvedSet<16> Functions;
-  OverloadedOperatorKind OverOp
-    = BinaryOperator::getOverloadedOperator(Opc);
-  if (Sc && OverOp != OO_None && OverOp != OO_Equal)
-    S.LookupOverloadedOperatorName(OverOp, Sc, LHS->getType(),
-                                   RHS->getType(), Functions);
+  OverloadedOperatorKind OverOp = BinaryOperator::getOverloadedOperator(Opc);
+  if (Sc) {
+    if (OverOp != OO_None && OverOp != OO_Equal)
+      S.LookupOverloadedOperatorName(OverOp, Sc, Functions);
 
     // In C++20 onwards, we may have a second operator to look up.
     if (S.getLangOpts().CPlusPlus2a) {
-    if (OverloadedOperatorKind ExtraOp = getRewrittenOverloadedOperator(OverOp))
-      S.LookupOverloadedOperatorName(ExtraOp, Sc, LHS->getType(),
-                                     RHS->getType(), Functions);
+      if (OverloadedOperatorKind ExtraOp =
+              getRewrittenOverloadedOperator(OverOp))
+        S.LookupOverloadedOperatorName(ExtraOp, Sc, Functions);
+    }
   }
 
   // Build the (potentially-overloaded, potentially-dependent)
   // binary operation.
   return S.CreateOverloadedBinOp(OpLoc, Opc, Functions, LHS, RHS);
 }
 
 ExprResult Sema::BuildBinOp(Scope *S, SourceLocation OpLoc,
-                            BinaryOperatorKind Opc,
-                            Expr *LHSExpr, Expr *RHSExpr) {
+                            BinaryOperatorKind Opc, Expr *LHSExpr,
+                            Expr *RHSExpr,
+                            const UnresolvedSetImpl *OverloadCands) {
   ExprResult LHS, RHS;
   std::tie(LHS, RHS) = CorrectDelayedTyposInBinOp(*this, Opc, LHSExpr, RHSExpr);
   if (!LHS.isUsable() || !RHS.isUsable())
     return ExprError();
   LHSExpr = LHS.get();
   RHSExpr = RHS.get();
 
   // We want to end up calling one of checkPseudoObjectAssignment
if (getLangOpts().CPlusPlus && pty->getKind() == BuiltinType::Overload) {
       // that an overload set can be dependently-typed, but it never
       // instantiates to having an overloadable type.
       ExprResult resolvedRHS = CheckPlaceholderExpr(RHSExpr);
       if (resolvedRHS.isInvalid()) return ExprError();
       RHSExpr = resolvedRHS.get();
 
       if (RHSExpr->isTypeDependent() ||
           RHSExpr->getType()->isOverloadableType())
-        return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr);
+        return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr,
+                                    OverloadCands);
     }
 
     // If we're instantiating "a.x < b" or "A::x < b" and 'x' names a function
     // template, diagnose the missing 'template' keyword instead of diagnosing
     // an invalid use of a bound member function.
     //
     // Note that "A::x < b" might be valid if 'b' has an overloadable type due
     // to C++1z [over.over]/1.4, but we already checked for that case above.
ExprResult Sema::BuildBinOp(Scope *S, SourceLocation OpLoc,
   // Handle pseudo-objects in the RHS.
   if (const BuiltinType *pty = RHSExpr->getType()->getAsPlaceholderType()) {
     // An overload in the RHS can potentially be resolved by the type
     // being assigned to.
     if (Opc == BO_Assign && pty->getKind() == BuiltinType::Overload) {
       if (getLangOpts().CPlusPlus &&
           (LHSExpr->isTypeDependent() || RHSExpr->isTypeDependent() ||
            LHSExpr->getType()->isOverloadableType()))
-        return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr);
+        return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr,
+                                    OverloadCands);
 
       return CreateBuiltinBinOp(OpLoc, Opc, LHSExpr, RHSExpr);
     }
 
     // Don't resolve overloads if the other type is overloadable.
     if (getLangOpts().CPlusPlus && pty->getKind() == BuiltinType::Overload &&
         LHSExpr->getType()->isOverloadableType())
-      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr);
+      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr,
+                                  OverloadCands);
 
     ExprResult resolvedRHS = CheckPlaceholderExpr(RHSExpr);
     if (!resolvedRHS.isUsable()) return ExprError();
     RHSExpr = resolvedRHS.get();
   }
 
   if (getLangOpts().CPlusPlus) {
     // If either expression is type-dependent, always build an
     // overloaded op.
     if (LHSExpr->isTypeDependent() || RHSExpr->isTypeDependent())
-      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr);
+      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr,
+                                  OverloadCands);
 
     // Otherwise, build an overloaded op if either expression has an
     // overloadable type.
     if (LHSExpr->getType()->isOverloadableType() ||
         RHSExpr->getType()->isOverloadableType())
-      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr);
+      return BuildOverloadedBinOp(*this, S, OpLoc, Opc, LHSExpr, RHSExpr,
+                                  OverloadCands);
   }
 
   // Build a built-in binary operation.
   return CreateBuiltinBinOp(OpLoc, Opc, LHSExpr, RHSExpr);
 }
 
 static bool isOverflowingIntegerType(ASTContext &Ctx, QualType T) {
   if (T.isNull() || T->isDependentType())
if (getLangOpts().CPlusPlus && Input->getType()->isOverloadableType() &&
       !(Opc == UO_AddrOf && isQualifiedMemberAccess(Input))) {
     // Find all of the overloaded operators visible from this
     // point. We perform both an operator-name lookup from the local
     // scope and an argument-dependent lookup based on the types of
     // the arguments.
     UnresolvedSet<16> Functions;
     OverloadedOperatorKind OverOp = UnaryOperator::getOverloadedOperator(Opc);
     if (S && OverOp != OO_None)
-      LookupOverloadedOperatorName(OverOp, S, Input->getType(), QualType(),
-                                   Functions);
+      LookupOverloadedOperatorName(OverOp, S, Functions);
 
     return CreateOverloadedUnaryOp(OpLoc, Opc, Functions, Input);
   }
 
   return CreateBuiltinUnaryOp(OpLoc, Opc, Input);
 }
 
 // Unary Operators.  'Tok' is the token for the operator.

clang/lib/Sema/SemaLookup.cpp

ObjCProtocolDecl *Sema::LookupProtocol(IdentifierInfo *II,
                                        SourceLocation IdLoc,
                                        RedeclarationKind Redecl) {
   Decl *D = LookupSingleName(TUScope, II, IdLoc,
                              LookupObjCProtocolName, Redecl);
   return cast_or_null<ObjCProtocolDecl>(D);
 }
 
 void Sema::LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S,
-                                        QualType T1, QualType T2,
                                         UnresolvedSetImpl &Functions) {
   // C++ [over.match.oper]p3:
   //     -- The set of non-member candidates is the result of the
   //        unqualified lookup of operator@ in the context of the
   //        expression according to the usual rules for name lookup in
   //        unqualified function calls (3.4.2) except that all member
   //        functions are ignored.
   DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op);

clang/lib/Sema/SemaTemplateVariadic.cpp

if ((OCE && OCE->isInfixBinaryOp()) || isa<BinaryOperator>(E) ||
       isa<AbstractConditionalOperator>(E)) {
     S.Diag(E->getExprLoc(), diag::err_fold_expression_bad_operand)
         << E->getSourceRange()
         << FixItHint::CreateInsertion(E->getBeginLoc(), "(")
         << FixItHint::CreateInsertion(E->getEndLoc(), ")");
   }
 }
 
-ExprResult Sema::ActOnCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
-                                  tok::TokenKind Operator,
+ExprResult Sema::ActOnCXXFoldExpr(Scope *Sc, SourceLocation LParenLoc,
+                                  Expr *LHS, tok::TokenKind Operator,
                                   SourceLocation EllipsisLoc, Expr *RHS,
                                   SourceLocation RParenLoc) {
   // LHS and RHS must be cast-expressions. We allow an arbitrary expression
   // in the parser and reduce down to just cast-expressions here.
   CheckFoldOperand(*this, LHS);
   CheckFoldOperand(*this, RHS);
 
   auto DiscardOperands = [&] {
if (!LHS || !RHS) {
     assert(Pack && "fold expression with neither LHS nor RHS");
     DiscardOperands();
     if (!Pack->containsUnexpandedParameterPack())
       return Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
              << Pack->getSourceRange();
   }
 
   BinaryOperatorKind Opc = ConvertTokenKindToBinaryOpcode(Operator);
+
+  UnresolvedSet<8> Functions;
+  OverloadedOperatorKind OverOp = BinaryOperator::getOverloadedOperator(Opc);
+  if (Sc) {
+    if (OverOp != OO_None && OverOp != OO_Equal)
+      LookupOverloadedOperatorName(OverOp, Sc, Functions);
+
+    // In C++20 onwards, we may have a second operator to look up.
+    if (getLangOpts().CPlusPlus2a) {
+      if (OverloadedOperatorKind ExtraOp =
+              getRewrittenOverloadedOperator(OverOp))
+        LookupOverloadedOperatorName(ExtraOp, Sc, Functions);
+    }
+  }
+
   return BuildCXXFoldExpr(LParenLoc, LHS, Opc, EllipsisLoc, RHS, RParenLoc,
-                          None);
+                          None,
+                          llvm::make_range(Functions.begin(), Functions.end()));
 }
 
-ExprResult Sema::BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
-                                  BinaryOperatorKind Operator,
-                                  SourceLocation EllipsisLoc, Expr *RHS,
-                                  SourceLocation RParenLoc,
-                                  Optional<unsigned> NumExpansions) {
-  return new (Context) CXXFoldExpr(Context.DependentTy, LParenLoc, LHS,
-                                   Operator, EllipsisLoc, RHS, RParenLoc,
-                                   NumExpansions);
+ExprResult Sema::BuildCXXFoldExpr(
+    SourceLocation LParenLoc, Expr *LHS, BinaryOperatorKind Operator,
+    SourceLocation EllipsisLoc, Expr *RHS, SourceLocation RParenLoc,
+    Optional<unsigned> NumExpansions,
+    llvm::iterator_range<UnresolvedSetIterator> OverloadCands) {
+  return CXXFoldExpr::Create(Context, Context.DependentTy, LParenLoc, LHS,
+                             NumExpansions, OverloadCands);
 }
 
 ExprResult Sema::BuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
                                        BinaryOperatorKind Operator) {
   // [temp.variadic]p9:
   //   If N is zero for a unary fold-expression, the value of the expression is
   //       &&  ->  true
   //       ||  ->  false

clang/lib/Sema/TreeTransform.h

return getSema().BuildMemberReferenceExpr(Base, BaseType, OpLoc, isArrow,
                                               R, ExplicitTemplateArgs,
                                               /*S*/nullptr);
   }
 
   /// Build a new binary operator expression.
   ///
   /// By default, performs semantic analysis to build the new expression.
   /// Subclasses may override this routine to provide different behavior.
-  ExprResult RebuildBinaryOperator(SourceLocation OpLoc,
-                                         BinaryOperatorKind Opc,
-                                         Expr *LHS, Expr *RHS) {
-    return getSema().BuildBinOp(/*Scope=*/nullptr, OpLoc, Opc, LHS, RHS);
+  ExprResult
+  RebuildBinaryOperator(SourceLocation OpLoc, BinaryOperatorKind Opc, Expr *LHS,
+                        Expr *RHS,
+                        const UnresolvedSetImpl *OverloadCands = nullptr) {
+    return getSema().BuildBinOp(/*Scope=*/nullptr, OpLoc, Opc, LHS, RHS,
+                                OverloadCands);
   }
 
   /// Build a new rewritten operator expression.
   ///
   /// By default, performs semantic analysis to build the new expression.
   /// Subclasses may override this routine to provide different behavior.
   ExprResult RebuildCXXRewrittenBinaryOperator(
       SourceLocation OpLoc, BinaryOperatorKind Opcode,
ExprResult RebuildPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
                                   Optional<unsigned> NumExpansions) {
     return getSema().CheckPackExpansion(Pattern, EllipsisLoc, NumExpansions);
   }
 
   /// Build a new C++1z fold-expression.
   ///
   /// By default, performs semantic analysis in order to build a new fold
   /// expression.
-  ExprResult RebuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
-                                BinaryOperatorKind Operator,
-                                SourceLocation EllipsisLoc, Expr *RHS,
-                                SourceLocation RParenLoc,
-                                Optional<unsigned> NumExpansions) {
+  ExprResult RebuildCXXFoldExpr(
+      SourceLocation LParenLoc, Expr *LHS, BinaryOperatorKind Operator,
+      SourceLocation EllipsisLoc, Expr *RHS, SourceLocation RParenLoc,
+      Optional<unsigned> NumExpansions,
+      llvm::iterator_range<UnresolvedSetIterator> OverloadCands) {
     return getSema().BuildCXXFoldExpr(LParenLoc, LHS, Operator, EllipsisLoc,
-                                      RHS, RParenLoc, NumExpansions);
+                                      RHS, RParenLoc, NumExpansions,
+                                      OverloadCands);
   }
 
   /// Build an empty C++1z fold-expression with the given operator.
   ///
   /// By default, produces the fallback value for the fold-expression, or
   /// produce an error if there is no fallback value.
   ExprResult RebuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
                                      BinaryOperatorKind Operator) {
if (RHS.isInvalid())
       return true;
 
     if (!getDerived().AlwaysRebuild() &&
         LHS.get() == E->getLHS() && RHS.get() == E->getRHS())
       return E;
 
     return getDerived().RebuildCXXFoldExpr(
         E->getBeginLoc(), LHS.get(), E->getOperator(), E->getEllipsisLoc(),
-        RHS.get(), E->getEndLoc(), NumExpansions);
+        RHS.get(), E->getEndLoc(), NumExpansions, E->overloadCands());
   }
 
   // The transform has determined that we should perform an elementwise
   // expansion of the pattern. Do so.
   ExprResult Result = getDerived().TransformExpr(E->getInit());
   if (Result.isInvalid())
     return true;
   bool LeftFold = E->isLeftFold();
 
   // If we're retaining an expansion for a right fold, it is the innermost
   // component and takes the init (if any).
   if (!LeftFold && RetainExpansion) {
     ForgetPartiallySubstitutedPackRAII Forget(getDerived());
 
     ExprResult Out = getDerived().TransformExpr(Pattern);
     if (Out.isInvalid())
       return true;
 
     Result = getDerived().RebuildCXXFoldExpr(
         E->getBeginLoc(), Out.get(), E->getOperator(), E->getEllipsisLoc(),
-        Result.get(), E->getEndLoc(), OrigNumExpansions);
+        Result.get(), E->getEndLoc(), OrigNumExpansions, E->overloadCands());
     if (Result.isInvalid())
       return true;
   }
 
+  UnresolvedSet<8> OverloadCands;
+  OverloadCands.append(E->overloadCands().begin(), E->overloadCands().end());
   for (unsigned I = 0; I != *NumExpansions; ++I) {
     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(
         getSema(), LeftFold ? I : *NumExpansions - I - 1);
     ExprResult Out = getDerived().TransformExpr(Pattern);
     if (Out.isInvalid())
       return true;
 
     if (Out.get()->containsUnexpandedParameterPack()) {
       // We still have a pack; retain a pack expansion for this slice.
       Result = getDerived().RebuildCXXFoldExpr(
           E->getBeginLoc(), LeftFold ? Result.get() : Out.get(),
           E->getOperator(), E->getEllipsisLoc(),
           LeftFold ? Out.get() : Result.get(), E->getEndLoc(),
-          OrigNumExpansions);
+          OrigNumExpansions, E->overloadCands());
     } else if (Result.isUsable()) {
       // We've got down to a single element; build a binary operator.
       Result = getDerived().RebuildBinaryOperator(
           E->getEllipsisLoc(), E->getOperator(),
           LeftFold ? Result.get() : Out.get(),
-          LeftFold ? Out.get() : Result.get());
+          LeftFold ? Out.get() : Result.get(), &OverloadCands);
     } else
       Result = Out;
 
     if (Result.isInvalid())
       return true;
   }
 
   // If we're retaining an expansion for a left fold, it is the outermost
   // component and takes the complete expansion so far as its init (if any).
   if (LeftFold && RetainExpansion) {
     ForgetPartiallySubstitutedPackRAII Forget(getDerived());
 
     ExprResult Out = getDerived().TransformExpr(Pattern);
     if (Out.isInvalid())
       return true;
 
     Result = getDerived().RebuildCXXFoldExpr(
         E->getBeginLoc(), Result.get(), E->getOperator(), E->getEllipsisLoc(),
-        Out.get(), E->getEndLoc(), OrigNumExpansions);
+        Out.get(), E->getEndLoc(), OrigNumExpansions, E->overloadCands());
     if (Result.isInvalid())
       return true;
   }
 
   // If we had no init and an empty pack, and we're not retaining an expansion,
   // then produce a fallback value or error.
   if (Result.isUnset())
     return getDerived().RebuildEmptyCXXFoldExpr(E->getEllipsisLoc(),

clang/lib/Serialization/ASTReaderStmt.cpp

void ASTStmtReader::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *E) {
   E->State = Record.readSubExpr();
   auto *VD = ReadDeclAs<ValueDecl>();
   unsigned ManglingNumber = Record.readInt();
   E->setExtendingDecl(VD, ManglingNumber);
 }
 
 void ASTStmtReader::VisitCXXFoldExpr(CXXFoldExpr *E) {
   VisitExpr(E);
+  unsigned NumOverloadCands = Record.readInt();
   E->LParenLoc = ReadSourceLocation();
   E->EllipsisLoc = ReadSourceLocation();
   E->RParenLoc = ReadSourceLocation();
   E->NumExpansions = Record.readInt();
   E->SubExprs[0] = Record.readSubExpr();
   E->SubExprs[1] = Record.readSubExpr();
   E->Opcode = (BinaryOperatorKind)Record.readInt();
+
+  DeclAccessPair *OverloadCands = E->getTrailingObjects<DeclAccessPair>();
+  for (unsigned I = 0; I != NumOverloadCands; ++I) {
+    auto *D = ReadDeclAs<NamedDecl>();
+    auto AS = (AccessSpecifier)Record.readInt();
+    OverloadCands[I].set(D, AS);
+  }
 }
 
 void ASTStmtReader::VisitOpaqueValueExpr(OpaqueValueExpr *E) {
   VisitExpr(E);
   E->SourceExpr = Record.readSubExpr();
   E->OpaqueValueExprBits.Loc = ReadSourceLocation();
   E->setIsUnique(Record.readInt());
 }
case EXPR_FUNCTION_PARM_PACK:
                                           Record[ASTStmtReader::NumExprFields]);
       break;
 
     case EXPR_MATERIALIZE_TEMPORARY:
       S = new (Context) MaterializeTemporaryExpr(Empty);
       break;
 
     case EXPR_CXX_FOLD:
-      S = new (Context) CXXFoldExpr(Empty);
+      S = CXXFoldExpr::CreateEmpty(Context,
+                                   Record[ASTStmtReader::NumExprFields]);
       break;
 
     case EXPR_OPAQUE_VALUE:
       S = new (Context) OpaqueValueExpr(Empty);
       break;
 
     case EXPR_CUDA_KERNEL_CALL:
       S = CUDAKernelCallExpr::CreateEmpty(

clang/lib/Serialization/ASTWriterStmt.cpp

void ASTStmtWriter::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *E) {
   Record.AddStmt(E->getTemporary());
   Record.AddDeclRef(E->getExtendingDecl());
   Record.push_back(E->getManglingNumber());
   Code = serialization::EXPR_MATERIALIZE_TEMPORARY;
 }
 
 void ASTStmtWriter::VisitCXXFoldExpr(CXXFoldExpr *E) {
   VisitExpr(E);
+  Record.push_back(E->getNumOverloadCands());
   Record.AddSourceLocation(E->LParenLoc);
   Record.AddSourceLocation(E->EllipsisLoc);
   Record.AddSourceLocation(E->RParenLoc);
   Record.push_back(E->NumExpansions);
   Record.AddStmt(E->SubExprs[0]);
   Record.AddStmt(E->SubExprs[1]);
   Record.push_back(E->Opcode);
+  for (UnresolvedSetIterator I = E->overloadCands().begin(),
+                             End = E->overloadCands().end();
+       I != End; ++I) {
+    Record.AddDeclRef(I.getDecl());
+    Record.push_back(I.getAccess());
+  }
   Code = serialization::EXPR_CXX_FOLD;
 }
 
 void ASTStmtWriter::VisitOpaqueValueExpr(OpaqueValueExpr *E) {
   VisitExpr(E);
   Record.AddStmt(E->getSourceExpr());
   Record.AddSourceLocation(E->getLocation());
   Record.push_back(E->isUnique());

clang/test/SemaTemplate/cxx1z-fold-expressions.cpp

struct A {
   } b;
 } a;
 template<typename T, typename ...Ts> constexpr decltype(auto) apply(T &t, Ts ...ts) {
   return (t.*....*ts);
 }
 static_assert(&apply(a, &A::b, &A::B::c, &A::B::C::d, &A::B::C::D::e) == &a.b.c.d.e);
 
 #if __cplusplus > 201703L
+
+namespace N {
+
+  struct Bool {
+    constexpr Bool(const bool& b) : b(b) {}
+    bool b;
+  };
+
+}
+
+constexpr bool operator==(const N::Bool& b1, const N::Bool& b2) { return b1.b == b2.b; }
+constexpr int operator<=>(const N::Bool& b1, const N::Bool& b2) { return b1.b - b2.b; }
+
+template<typename ...T> constexpr auto fold_eq(T ...t) { return (t == ...); }
+template<typename ...T> constexpr auto fold_neq(T ...t) { return (t != ...); }
+template<typename ...T> constexpr auto fold_le(T ...t) { return (t < ...); }
+template<typename ...T> constexpr auto fold_leq(T ...t) { return (t <= ...); }
+template<typename ...T> constexpr auto fold_ge(T ...t) { return (t > ...); }
+template<typename ...T> constexpr auto fold_geq(T ...t) { return (t >= ...); }
+
+static_assert(fold_eq(N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}));
+static_assert(!fold_eq(N::Bool{true}, N::Bool{true}, N::Bool{false}, N::Bool{true}, N::Bool{true}));
+static_assert(fold_neq(N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}));
+static_assert(!fold_neq(N::Bool{true}, N::Bool{true}, N::Bool{false}, N::Bool{true}, N::Bool{true}));
+
+static_assert(!fold_le(N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}));
+static_assert(fold_leq(N::Bool{false}, N::Bool{true}, N::Bool{true}, N::Bool{true}, N::Bool{true}));
+static_assert(fold_ge(N::Bool{true}, N::Bool{false}, N::Bool{true}, N::Bool{false}, N::Bool{false}));
+static_assert(!fold_ge(N::Bool{false}, N::Bool{false}, N::Bool{true}, N::Bool{false}, N::Bool{false}));
+
 // The <=> operator is unique among binary operators in not being a
 // fold-operator.
 // FIXME: This diagnostic is not great.
 template<typename ...T> constexpr auto spaceship1(T ...t) { return (t <=> ...); } // expected-error {{expected expression}}
 template<typename ...T> constexpr auto spaceship2(T ...t) { return (... <=> t); } // expected-error {{expected expression}}
 template<typename ...T> constexpr auto spaceship3(T ...t) { return (t <=> ... <=> 0); } // expected-error {{expected expression}}
 #endif
 
 // The GNU binary conditional operator ?: is not recognized as a fold-operator.
 // FIXME: Why not? This seems like it would be useful.
 template<typename ...T> constexpr auto binary_conditional1(T ...t) { return (t ?: ...); } // expected-error {{expected expression}}
 template<typename ...T> constexpr auto binary_conditional2(T ...t) { return (... ?: t); } // expected-error {{expected expression}}
 template<typename ...T> constexpr auto binary_conditional3(T ...t) { return (t ?: ... ?: 0); } // expected-error {{expected expression}}
 
 namespace PR41845 {
   template <int I> struct Constant {};
 
   template <int... Is> struct Sum {
     template <int... Js> using type = Constant<((Is + Js) + ... + 0)>; // expected-error {{pack expansion contains parameter pack 'Js' that has a different length (1 vs. 2) from outer parameter packs}}
   };
 
   Sum<1>::type<1, 2> x; // expected-note {{instantiation of}}
 }
+
+namespace N {
+  
+  struct A { int i; };
+  struct B { int i; };
+  
+  constexpr B operator+(const B& a, const B& b) { return { a.i + b.i }; }
+  
+}
+
+struct C { int i; };
+
+constexpr C operator+(const C& a, const C& b) { return { a.i + b.i }; }
+constexpr N::A operator+(const N::A& a, const N::A& b) { return { a.i + b.i }; }
+
+template<typename T1, typename ...T2> constexpr auto custom_fold(T1 t1, T2 ...t2) {
+  return (t2 + ...) + (... + t2) + (t2 + ... + t1) + (t1 + ... + t2);
+}
+
+static_assert(custom_fold(N::A{1}, N::A{2}, N::A{3}, N::A{4}, N::A{5}).i == 58);
+static_assert(custom_fold(N::B{1}, N::B{2}, N::B{3}, N::B{4}, N::B{5}).i == 58);
+static_assert(custom_fold(C{1}, C{2}, C{3}, C{4}, C{5}).i == 58);
+
+template<typename T, int I1, int ...I2> constexpr auto func_fold(
+    decltype((T{ I2 } + ...) + (... + T{ I2 }) + (T{ I2 } + ... + T{ I1 }) + (T{ I1 } + ... + T{ I2 })) t) {
+  return t.i;
+}
+
+static_assert(func_fold<N::A, 1, 2, 3, 4, 5>(N::A{ 42 }) == 42);
+static_assert(func_fold<N::B, 1, 2, 3, 4, 5>(N::B{ 42 }) == 42);
+static_assert(func_fold<C, 1, 2, 3, 4, 5>(C{ 42 }) == 42);
+
+struct D { int i; };
+
+namespace N {
+  
+  constexpr D operator+(const D& a, const D& b) { return { a.i + b.i }; }
+  
+}
+
+template<typename T1, typename ...T2> constexpr auto custom_fold_using(T1 t1, T2 ...t2) {
+  using N::operator+;
+  return (t2 + ...) + (... + t2) + (t2 + ... + t1) + (t1 + ... + t2);
+}
+
+static_assert(custom_fold_using(D{1}, D{2}, D{3}, D{4}, D{5}).i == 58);