[AST] Traverse CXXOperatorCallExpr in LexicallyOrderedRecursiveASTVisitor

[johannes]

Summary

This affects overloaded operators, which are represented by a
CXXOperatorCallExpr whose first child is always a DeclRefExpr referring to the
operator. For infix, postfix and call operators we want the first argument
to be traversed before the operator.

[arphaman]

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

67

I don't think you need this since getDerived in RecursiveASTVisitor is already public.

69

Why exactly is this template struct needed?

include/clang/AST/RecursiveASTVisitor.h

3212

Getting rid of undef is not ideal. You might want to extract these macros into one .def file that's included by both RecursiveASTVisitor.h and the LexicallyOrdered one.

[johannes]

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

67

has_same_member_pointer and getDerived are used by the TRAVERSE_STMT macro, which should be the right one to use here.
Also the RecursiveASTVisitor typedef just above.

include/clang/AST/RecursiveASTVisitor.h

3212

Ok, I will do that

[arphaman]

Ah I see,

then you should something completely different (forget the header).
Please extract this code into a protected function in RecursiveASTVisitor:

for (Stmt *SubStmt : Children)
  if (!TRAVERSE_STMT_BASE(Stmt, Stmt, SubStmt, Queue))
    return false;

And reuse it in this class. Then you won't have to use any macros or related template magic here.

[johannes]

use RecursiveASTVisitor::TraverseStmt

[arphaman]

This works as well I think

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

63

Do you still need the using here?

[johannes]

do call derived TraverseStmt for children of CXXOperatorCallExpr

[johannes]

The previous version didn't call TraverseDecl of the derived class, this is fixed now.
The public getDerived.TraverseStmt() does not accept a DataRecursionQueue, so this also could not be used (I think)
I used the wrapper TraverseStmtBase, which should behave exactly as the method that originally traverses CXXOperatorCallExpr

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

63

removed it now as it's only used once

[arphaman]

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

149

For ++ and -- you can see whether its prefix or postfix by looking at the number of arguments. If there's one argument, then ++ and -- are prefix. Otherwise, they're postfix.

[johannes]

detect prefix/postfix from number of arguments

[arphaman]

The fact that TraverseCXXOperatorCallExpr can't call its super TraverseCXXOperatorCallExpr makes the current solution kind of broken. The super implementation of TraverseCXXOperatorCallExpr is responsible for dispatch to WalkUp##STMT functions which actually call VisitCXXOperatorCallExpr which our current visitor will never call because of the custom "override". I would like to suggest an alternative approach that I think solves the problem more "elegantly":

Modify the DEF_TRAVERSE_STMT macro in RecursiveASTVisitor.h call to a wrapper function to get the children:

class RecursiveASTVisitor {
public:

  Stmt::child_range getStmtChildren(Stmt *S) {
    return S->children();
  }
 
...

#define DEF_TRAVERSE_STMT(STMT, CODE)                                          \
  template <typename Derived>                                                  \
  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)) {                                    \   // The only change is on this line.
        TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);                              \
      }                                                                        \
    }                                                                          \
    if (!Queue && ReturnValue && getDerived().shouldTraversePostOrder())       \
      TRY_TO(WalkUpFrom##STMT(S));                                             \
    return ReturnValue;                                                        \
  }

...

};

Then you could provide an "override" in the LexicallyOrderedRecursiveASTVisitor that adjusts children just for CXXOperatorCallExpr. Something like this should work:

class LexicallyOrderedRecursiveASTVisitor {
public:
...

  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;
  }

...
};

WDYT?

Sorry about not seeing this earlier. Thanks for your patience!

[johannes]

use a specialized getStmtChildren to fix the order for CXXOperatorCallExpr

[johannes]

Yeah, this seems to be the best solution for this. I think I ran into the same issue when working on the StmtDataCollector - basically there can only be two Traverse*, one in the Derived class and the other one needs to do all the magic with walking the specialisation hierarchy.

[arphaman]

Lgtm with two requests below

include/clang/AST/RecursiveASTVisitor.h

354

I don't think you need this function now

2089

Please avoid deleting this line

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

 /// @implementation is preserved while traversing the AST. Note that the
 /// current implementation doesn't mix these declarations with the declarations
 /// contained in the @implementation, so the traversal of all of the
 /// declarations in the @implementation still doesn't follow the lexical order.
 template <typename Derived>
 class LexicallyOrderedRecursiveASTVisitor
     : public RecursiveASTVisitor<Derived> {
   using BaseType = RecursiveASTVisitor<Derived>;
 
 public:
   LexicallyOrderedRecursiveASTVisitor(const SourceManager &SM) : SM(SM) {}
 
   bool TraverseObjCImplementationDecl(ObjCImplementationDecl *D) {
     // Objective-C @implementation declarations should not trigger early exit
     // until the additional decls are traversed as their children are not
     // lexically ordered.
     bool Result = BaseType::TraverseObjCImplementationDecl(D);
     return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
   }
 
   bool TraverseObjCCategoryImplDecl(ObjCCategoryImplDecl *D) {
     bool Result = BaseType::TraverseObjCCategoryImplDecl(D);
     return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
assert(!BaseType::getDerived().shouldVisitTemplateInstantiations() &&      \
            "instantiations here.");                                            \
     return BaseType::getDerived().TraverseDecl(TD->getTemplatedDecl());        \
   }
   DEF_TRAVERSE_TEMPLATE_DECL(Class)
   DEF_TRAVERSE_TEMPLATE_DECL(Var)
   DEF_TRAVERSE_TEMPLATE_DECL(Function)
 #undef DEF_TRAVERSE_TEMPLATE_DECL
 
+  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

 // 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)
 
+protected:
+  bool TraverseStmtBase(Stmt *S, DataRecursionQueue *Queue) {
+    return TRAVERSE_STMT_BASE(Stmt, Stmt, S, Queue);
+  }
 public:
 // Declare Traverse*() for all concrete Stmt classes.
 #define ABSTRACT_STMT(STMT)
 #define STMT(CLASS, PARENT) \
   bool Traverse##CLASS(CLASS *S, DataRecursionQueue *Queue = nullptr);
 #include "clang/AST/StmtNodes.inc"
   // The above header #undefs ABSTRACT_STMT and STMT upon exit.
 
#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 : S->children()) {                                    \
+      for (Stmt * SubStmt : getDerived().getStmtChildren(S)) {                 \
         TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);                              \
       }                                                                        \
     }                                                                          \
     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));
   }

 //
 //    http://clang.llvm.org/doxygen/classclang_1_1CXXTypeidExpr.html
 //    http://clang.llvm.org/doxygen/classclang_1_1UnaryExprOrTypeTraitExpr.html
 //    http://clang.llvm.org/doxygen/classclang_1_1TypesCompatibleExpr.html
 //    Every class that has getQualifier.
 
 #undef DEF_TRAVERSE_STMT
 #undef TRAVERSE_STMT
 #undef TRAVERSE_STMT_BASE
 
 #undef TRY_TO
 
 } // end namespace clang
 
 #endif // LLVM_CLANG_AST_RECURSIVEASTVISITOR_H

unittests/Tooling/LexicallyOrderedRecursiveASTVisitorTest.cpp

 namespace {
 
 class DummyMatchVisitor;
 
 class LexicallyOrderedDeclVisitor
     : public LexicallyOrderedRecursiveASTVisitor<LexicallyOrderedDeclVisitor> {
 public:
   LexicallyOrderedDeclVisitor(DummyMatchVisitor &Matcher,
-                              const SourceManager &SM, bool EmitIndices)
+                              const SourceManager &SM, bool EmitDeclIndices,
+                              bool EmitStmtIndices)
       : LexicallyOrderedRecursiveASTVisitor(SM), Matcher(Matcher),
-        EmitIndices(EmitIndices) {}
+        EmitDeclIndices(EmitDeclIndices), EmitStmtIndices(EmitStmtIndices) {}
 
   bool TraverseDecl(Decl *D) {
     TraversalStack.push_back(D);
     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
     TraversalStack.pop_back();
     return true;
   }
 
+  bool TraverseStmt(Stmt *S);
+
   bool VisitNamedDecl(const NamedDecl *D);
+  bool VisitDeclRefExpr(const DeclRefExpr *D);
 
 private:
   DummyMatchVisitor &Matcher;
-  bool EmitIndices;
+  bool EmitDeclIndices, EmitStmtIndices;
   unsigned Index = 0;
   llvm::SmallVector<Decl *, 8> TraversalStack;
 };
 
 class DummyMatchVisitor : public ExpectedLocationVisitor<DummyMatchVisitor> {
-  bool EmitIndices;
+  bool EmitDeclIndices, EmitStmtIndices;
 
 public:
-  DummyMatchVisitor(bool EmitIndices = false) : EmitIndices(EmitIndices) {}
+  DummyMatchVisitor(bool EmitDeclIndices = false, bool EmitStmtIndices = false)
+      : EmitDeclIndices(EmitDeclIndices), EmitStmtIndices(EmitStmtIndices) {}
   bool VisitTranslationUnitDecl(TranslationUnitDecl *TU) {
     const ASTContext &Context = TU->getASTContext();
     const SourceManager &SM = Context.getSourceManager();
-    LexicallyOrderedDeclVisitor SubVisitor(*this, SM, EmitIndices);
+    LexicallyOrderedDeclVisitor SubVisitor(*this, SM, EmitDeclIndices,
+                                           EmitStmtIndices);
     SubVisitor.TraverseDecl(TU);
     return false;
   }
 
-  void match(StringRef Path, const Decl *D) { Match(Path, D->getLocStart()); }
+  template <class T> void match(StringRef Path, const T *D) {
+    Match(Path, D->getLocStart());
+  }
 };
 
+bool LexicallyOrderedDeclVisitor::TraverseStmt(Stmt *S) {
+  Matcher.match("overridden TraverseStmt", S);
+  return LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
+}
+
 bool LexicallyOrderedDeclVisitor::VisitNamedDecl(const NamedDecl *D) {
   std::string Path;
   llvm::raw_string_ostream OS(Path);
   assert(TraversalStack.back() == D);
   for (const Decl *D : TraversalStack) {
     if (isa<TranslationUnitDecl>(D)) {
       OS << "/";
       continue;
     }
     if (const auto *ND = dyn_cast<NamedDecl>(D))
       OS << ND->getNameAsString();
     else
       OS << "???";
     if (isa<DeclContext>(D) or isa<TemplateDecl>(D))
       OS << "/";
   }
-  if (EmitIndices)
+  if (EmitDeclIndices)
+    OS << "@" << Index++;
+  Matcher.match(OS.str(), D);
+  return true;
+}
+
+bool LexicallyOrderedDeclVisitor::VisitDeclRefExpr(const DeclRefExpr *D) {
+  std::string Name = D->getFoundDecl()->getNameAsString();
+  llvm::raw_string_ostream OS(Name);
+  if (EmitStmtIndices)
     OS << "@" << Index++;
   Matcher.match(OS.str(), D);
   return true;
 }
 
 TEST(LexicallyOrderedRecursiveASTVisitor, VisitDeclsInImplementation) {
   StringRef Source = R"(
 @interface I
)";
   EXPECT_TRUE(Visitor.runOver(Source, DummyMatchVisitor::Lang_OBJC));
 }
 
 TEST(LexicallyOrderedRecursiveASTVisitor, VisitTemplateDecl) {
   StringRef Source = R"(
 template <class T> T f();
 template <class U, class = void> class Class {};
 )";
-  DummyMatchVisitor Visitor(/*EmitIndices=*/true);
+  DummyMatchVisitor Visitor(/*EmitDeclIndices=*/true);
   Visitor.ExpectMatch("/f/T@0", 2, 11);
   Visitor.ExpectMatch("/f/f/@1", 2, 20);
   Visitor.ExpectMatch("/Class/U@2", 3, 11);
   Visitor.ExpectMatch("/Class/@3", 3, 20);
   Visitor.ExpectMatch("/Class/Class/@4", 3, 34);
   EXPECT_TRUE(Visitor.runOver(Source));
 }
 
+TEST(LexicallyOrderedRecursiveASTVisitor, VisitCXXOperatorCallExpr) {
+  StringRef Source = R"(
+struct S {
+  S &operator+(S&);
+  S *operator->();
+  S &operator++();
+  S operator++(int);
+  void operator()(int, int);
+  void operator[](int);
+  void f();
+};
+S a, b, c;
+
+void test() {
+  a = b + c;
+  a->f();
+  a(1, 2);
+  b[0];
+  ++a;
+  b++;
+}
+)";
+  DummyMatchVisitor Visitor(/*EmitDeclIndices=*/false,
+                            /*EmitStmtIndices=*/true);
+  // There are two overloaded operators that start at this point
+  // This makes sure they are both traversed using the overridden
+  // TraverseStmt, as the traversal is implemented by us for
+  // CXXOperatorCallExpr.
+  Visitor.ExpectMatch("overridden TraverseStmt", 14, 3, 2);
+  Visitor.ExpectMatch("a@0", 14, 3);
+  Visitor.ExpectMatch("operator=@1", 14, 5);
+  Visitor.ExpectMatch("b@2", 14, 7);
+  Visitor.ExpectMatch("operator+@3", 14, 9);
+  Visitor.ExpectMatch("c@4", 14, 11);
+  Visitor.ExpectMatch("operator->@6", 15, 4);
+  Visitor.ExpectMatch("operator()@8", 16, 4);
+  Visitor.ExpectMatch("operator[]@10", 17, 4);
+  Visitor.ExpectMatch("operator++@11", 18, 3);
+  Visitor.ExpectMatch("operator++@14", 19, 4);
+  EXPECT_TRUE(Visitor.runOver(Source));
+}
+
 } // end anonymous namespace