[AST] Make RecursiveASTVisitor visit CXXOperatorCallExpr in source order

[johannes]

Summary

This adds a special case for traversing CXXOperatorCallExpr. Its
children are traversed in the order in which they appear in the source
code, so infix and postfix operators are visited after their first
argument.

This behavior was previously only in
LexicallyOrderedRecursiveASTVisitor, moving it here could avoid bugs in
the future. It is still tested in
LexicallyOrderedRecursiveASTVisitorTest.cpp in VisitTemplateDecl.
Clients that somehow rely on the original traversal order will have to
be updated though.

[klimek]

include/clang/AST/RecursiveASTVisitor.h

334

Why do we need to swap for calls?

[johannes]

include/clang/AST/RecursiveASTVisitor.h

334

The idea is that the opening parenthesis/bracket comes after the caller, for example in this call with two arguments.

`-CXXOperatorCallExpr
  |-ImplicitCastExpr
  | `-DeclRefExpr operator()
  |-DeclRefExpr caller
  |-IntegerLiteral
  `-IntegerLiteral

Of course we fail to capture the fact that there is also a closing parenthesis or bracket. So this is no perfect solution.

[rsmith]

include/clang/AST/RecursiveASTVisitor.h

327

The copy here is more expensive than I'd like. Instead of returning a list of children, please make this function *traverse* the children (which is what its one and only caller is going to do anyway) to avoid the copy.

334

Of course we fail to capture the fact that there is also a closing parenthesis or bracket.

One way we could handle this would be to effectively order by the start location for preorder traversal, and by the end location for postorder traversal. So for a case like your caller(1,2), we would visit CXXOperatorCallExpr, caller, operator(), 1, then 2 when doing preorder visitation, and caller, 1, 2, operator(), then CXXOperatorCallExpr when doing postorder visitation (because the notional source location for the operator() invocation extends across both 1 and 2 subexpressions).

But I think it's probably not worthwhile to go to this level of detail, and treating the ( as the location of the operator() call and ignoring the ) seems like a reasonable approach to me.

340–341

This would be clearer as Children.size() == 3.

However, instead of changing that, please add a CXXOperatorCallExpr::isPrefixOp() function (getNumArgs() == 1 && Op != OO_Call && Op != OO_Arrow); we should visit the callee after visiting the first argument if and only if we have a prefix operator.

[johannes]

use CXXOperatorCallExpr::isPrefixOp() to determine whether it's infix or postfix
directly traverse statement children instead of copying

[johannes]

include/clang/AST/RecursiveASTVisitor.h

327

I wasn't sure whether there is a way to do this in a function without writing a custom iterator that checks whether it should be swapped; I used a different approach.

334

Yeah, we can do that if someone needs it.

Another way would be to model the operator as parent of the operands, although I assume that this would not compose well.
I don't expect it to be feasible but I imagine CXXOperatorCallExpr could also inherit from DeclRefExpr.

include/clang/AST/ExprCXX.h

return Opc == OO_Equal || Opc == OO_StarEqual ||
            Opc == OO_AmpEqual || Opc == OO_CaretEqual ||
            Opc == OO_PipeEqual;
   }
   bool isAssignmentOp() const { return isAssignmentOp(getOperator()); }
 
   /// \brief Is this written as an infix binary operator?
   bool isInfixBinaryOp() const;
 
+  bool isPrefixOp() const;
+
   /// \brief Returns the location of the operator symbol in the expression.
   ///
   /// When \c getOperator()==OO_Call, this is the location of the right
   /// parentheses; when \c getOperator()==OO_Subscript, this is the location
   /// of the right bracket.
   SourceLocation getOperatorLoc() const { return getRParenLoc(); }
 
   SourceLocation getExprLoc() const LLVM_READONLY {

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

for (auto I = DC->decls_begin(), E = DC->decls_end(); I != E;) {
           LexicallyNestedDeclarations.push_back(Sibling);
       }
       if (!BaseType::getDerived().TraverseDecl(Child))
         return false;
     }
     return true;
   }
 
-  Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); }
-
-  SmallVector<Stmt *, 8> getStmtChildren(CXXOperatorCallExpr *CE) {
-    SmallVector<Stmt *, 8> Children(CE->children());
-    bool Swap;
-    // Switch the operator and the first operand for all infix and postfix
-    // operations.
-    switch (CE->getOperator()) {
-    case OO_Arrow:
-    case OO_Call:
-    case OO_Subscript:
-      Swap = true;
-      break;
-    case OO_PlusPlus:
-    case OO_MinusMinus:
-      // These are postfix unless there is exactly one argument.
-      Swap = Children.size() != 2;
-      break;
-    default:
-      Swap = CE->isInfixBinaryOp();
-      break;
-    }
-    if (Swap && Children.size() > 1)
-      std::swap(Children[0], Children[1]);
-    return Children;
-  }
-
 private:
   bool TraverseAdditionalLexicallyNestedDeclarations() {
     // FIXME: Ideally the gathered declarations and the declarations in the
     // @implementation should be mixed and sorted to get a true lexical order,
     // but right now we only care about getting the correct lexical parent, so
     // we can traverse the gathered nested declarations after the declarations
     // in the decl context.
     assert(!BaseType::getDerived().shouldTraversePostOrder() &&

include/clang/AST/RecursiveASTVisitor.h

 
 // Declare Traverse* and empty Visit* for all Attr classes.
 #define ATTR_VISITOR_DECLS_ONLY
 #include "clang/AST/AttrVisitor.inc"
 #undef ATTR_VISITOR_DECLS_ONLY
 
 // ---- Methods on Stmts ----
 
-  Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); }
-
 private:
   template<typename T, typename U>
   struct has_same_member_pointer_type : std::false_type {};
   template<typename T, typename U, typename R, typename... P>
   struct has_same_member_pointer_type<R (T::*)(P...), R (U::*)(P...)>
       : std::true_type {};
 
   // Traverse the given statement. If the most-derived traverse function takes a
   // data recursion queue, pass it on; otherwise, discard it. Note that the
   // first branch of this conditional must compile whether or not the derived
   // class can take a queue, so if we're taking the second arm, make the first
   // arm call our function rather than the derived class version.
 #define TRAVERSE_STMT_BASE(NAME, CLASS, VAR, QUEUE)                            \
   (has_same_member_pointer_type<decltype(                                      \
                                     &RecursiveASTVisitor::Traverse##NAME),     \
                                 decltype(&Derived::Traverse##NAME)>::value     \
        ? static_cast<typename std::conditional<                                \
              has_same_member_pointer_type<                                     \
                  decltype(&RecursiveASTVisitor::Traverse##NAME),               \
                  decltype(&Derived::Traverse##NAME)>::value,                   \
              Derived &, RecursiveASTVisitor &>::type>(*this)                   \
              .Traverse##NAME(static_cast<CLASS *>(VAR), QUEUE)                 \
        : getDerived().Traverse##NAME(static_cast<CLASS *>(VAR)))
 
 // Try to traverse the given statement, or enqueue it if we're performing data
 // recursion in the middle of traversing another statement. Can only be called
 // from within a DEF_TRAVERSE_STMT body or similar context.
 #define TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S)                                     \
   do {                                                                         \
     if (!TRAVERSE_STMT_BASE(Stmt, Stmt, S, Queue))                             \
       return false;                                                            \
   } while (false)
#define DEF_TRAVERSE_STMT(STMT, CODE)                                          \
   bool RecursiveASTVisitor<Derived>::Traverse##STMT(                           \
       STMT *S, DataRecursionQueue *Queue) {                                    \
     bool ShouldVisitChildren = true;                                           \
     bool ReturnValue = true;                                                   \
     if (!getDerived().shouldTraversePostOrder())                               \
       TRY_TO(WalkUpFrom##STMT(S));                                             \
     { CODE; }                                                                  \
     if (ShouldVisitChildren) {                                                 \
-      for (Stmt * SubStmt : getDerived().getStmtChildren(S)) {                 \
-        TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);                              \
+      auto ChildIterator = S->child_begin();                                   \
+      /* Make the operator come second for infix and postfix overloaded        \
+       * operators. */                                                         \
+      if (auto *CE = dyn_cast<CXXOperatorCallExpr>(S)) {                       \
+        if (CE->isInfixBinaryOp() || !CE->isPrefixOp()) {                      \
+          Stmt *Operator = *ChildIterator;                                     \
+          TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(*++ChildIterator);                   \
+          TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(Operator);                           \
+          ++ChildIterator;                                                     \
+        }                                                                      \
+      }                                                                        \
+      for (auto ChildEnd = S->child_end(); ChildIterator != ChildEnd;          \
+           ++ChildIterator) {                                                  \
+        TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(*ChildIterator);                       \
       }                                                                        \
     }                                                                          \
     if (!Queue && ReturnValue && getDerived().shouldTraversePostOrder())       \
       TRY_TO(WalkUpFrom##STMT(S));                                             \
     return ReturnValue;                                                        \
   }
-
 DEF_TRAVERSE_STMT(GCCAsmStmt, {
   TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getAsmString());
   for (unsigned I = 0, E = S->getNumInputs(); I < E; ++I) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getInputConstraintLiteral(I));
   }
   for (unsigned I = 0, E = S->getNumOutputs(); I < E; ++I) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getOutputConstraintLiteral(I));
   }

lib/AST/ExprCXX.cpp

bool CXXOperatorCallExpr::isInfixBinaryOp() const {
   switch (getOperator()) {
   case OO_Call: case OO_Subscript:
     return false;
   default:
     return true;
   }
 }
 
+bool CXXOperatorCallExpr::isPrefixOp() const {
+  return getNumArgs() == 1 && getOperator() != OO_Call &&
+         getOperator() != OO_Arrow;
+}
+
+
 bool CXXTypeidExpr::isPotentiallyEvaluated() const {
   if (isTypeOperand())
     return false;
 
   // C++11 [expr.typeid]p3:
   //   When typeid is applied to an expression other than a glvalue of
   //   polymorphic class type, [...] the expression is an unevaluated operand.
   const Expr *E = getExprOperand();