Add postorder support to RecursiveASTVisitor

[teemperor]

Summary

This patch adds postorder traversal support to the RecursiveASTVisitor.

This feature needs to be explicitly enabled by overriding shouldTraversePostOrder()
as it has performance drawbacks for the iterative Stmt-traversal.

[teemperor]

The motivation for this patch is a hashing algorithm for all AST nodes
which reuses child hash values to be O(n) and therefore needs postorder support
(think Java's Object.hashCode() but on AST nodes as an example).

The full code that currently uses this feature can be seen here:
https://github.com/Teemperor/clang/commit/9fdb10a8a910968a795cdd48e1271fe2140fcd2f

[klimek]

Generally makes sense; adding d0k for additional thoughts.

[bkramer]

Having postorder traversal makes sense to me. The thing I'm worried about is how much this will bloat object code. RecursiveASTVisitor is already a major contributor to the size of clang's binary and we've hit issues with it in the past (hitting .obj size limits on Windows for example) can you show numbers of the size of clang before and after this change? Ideally in Release and Debug configurations.

If it grows it too much we'll have to find another way of enabling/disabling it.

[teemperor]

This comment was removed by teemperor.

[teemperor]

The previous stats were wrong (only applied this patch, not the patch using the code):

Release:
63311672 Byte -> 77212960 Byte (+22% or +13.8 MB)
Debug:
1240292520 Byte -> 1264866776 Byte (+2% or +24.6 MB)

[bkramer]

IMO a 20% release binary size increase is not acceptable. Is there a way to compile in support only if it's actually used? Maybe some constexpr or template magic?

[teemperor]

Reduced executable size bloat. Made postorder and preorder mutually exclusive and postorder also uses the normal Visit* methods for callbacks.

[teemperor]

Agreed. The new patch is now reusing the Visit methods so that the executable size stays the same.
The downside is that you can no longer create a single Visitor class that is both post- and preorder traversing,
but I don't think there is any major use case for that.

[teemperor]

ping

[v.g.vassilev]

@bkramer are those modifications enough to accept this patch? It is holding back quite a lot of ongoing development from @teemperor as part of his GSoC project.

[bkramer]

If there's no more executable size bloat this seems fine to me.

[rsmith]

include/clang/AST/RecursiveASTVisitor.h

630–635

Does this really give a postorder traversal rather than some kind of postorder / reverse preorder hybrid (based on whether we use data recursion or regular recursion for different parts of the graph)?

I would expect the right way to handle this would be to call PostVisitStmt from the if (Visited) branch above, where we call dataTraverseStmtPost.

[teemperor]

• Stmt traversal is now always postorder, even if child statements don't support iterative traversal (thanks Richard). The test also tests this behavior now.

[v.g.vassilev]

Landed in r274348 and r274349.

include/clang/AST/RecursiveASTVisitor.h

       return false;                                                            \
   } while (0)
 
-/// \brief A class that does preorder depth-first traversal on the
-/// entire Clang AST and visits each node.
+/// \brief A class that does preordor or postorder
+/// depth-first traversal on the entire Clang AST and visits each node.
 ///
 /// This class performs three distinct tasks:
 ///   1. traverse the AST (i.e. go to each node);

 /// to return true, in which case all known implicit and explicit
 /// instantiations will be visited at the same time as the pattern
 /// from which they were produced.
+///
+/// By default, this visitor preorder traverses the AST. If postorder traversal
+/// is needed, the \c shouldTraversePostOrder method needs to be overriden
+/// to return \c true.
 template <typename Derived> class RecursiveASTVisitor {
 public:
   /// A queue used for performing data recursion over statements.

   /// code, e.g., implicit constructors and destructors.
   bool shouldVisitImplicitCode() const { return false; }
 
+  /// \brief Return whether this visitor should traverse post-order.
+  bool shouldTraversePostOrder() const { return false; }
+
   /// \brief Recursively visit a statement or expression, by
   /// dispatching to Traverse*() based on the argument's dynamic type.
   ///

   bool TraverseUnary##NAME(UnaryOperator *S,                                   \
                            DataRecursionQueue *Queue = nullptr) {              \
     TRY_TO(WalkUpFromUnary##NAME(S));                                          \
-    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getSubExpr());                                    \
+    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getSubExpr());                          \
     return true;                                                               \
   }                                                                            \
   bool WalkUpFromUnary##NAME(UnaryOperator *S) {                               \

 // (they're all opcodes in BinaryOperator) but do have visitors.
 #define GENERAL_BINOP_FALLBACK(NAME, BINOP_TYPE)                               \
   bool TraverseBin##NAME(BINOP_TYPE *S, DataRecursionQueue *Queue = nullptr) { \
-    TRY_TO(WalkUpFromBin##NAME(S));                                            \
-    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getLHS());                                        \
-    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getRHS());                                        \
+    if (!getDerived().shouldTraversePostOrder())                               \
+      TRY_TO(WalkUpFromBin##NAME(S));                                          \
+    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getLHS());                              \
+    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getRHS());                              \
     return true;                                                               \
   }                                                                            \
   bool WalkUpFromBin##NAME(BINOP_TYPE *S) {                                    \

   bool VisitOMPClauseWithPostUpdate(OMPClauseWithPostUpdate *Node);
 
   bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue);
+  bool PostVisitStmt(Stmt *S);
 };
 
 template <typename Derived>

 
 #undef DISPATCH_STMT
 
+
+template <typename Derived>
+bool RecursiveASTVisitor<Derived>::PostVisitStmt(Stmt *S) {
+  switch (S->getStmtClass()) {
+  case Stmt::NoStmtClass:
+    break;
+#define ABSTRACT_STMT(STMT)
+#define STMT(CLASS, PARENT)                                                    \
+  case Stmt::CLASS##Class:                                                     \
+    TRY_TO(WalkUpFrom##CLASS(static_cast<CLASS *>(S))); break;
+#include "clang/AST/StmtNodes.inc"
+  }
+
+  return true;
+}
+
+#undef DISPATCH_STMT
+
 template <typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseStmt(Stmt *S,
                                                 DataRecursionQueue *Queue) {

     if (Visited) {
       LocalQueue.pop_back();
       TRY_TO(dataTraverseStmtPost(CurrS));
+      if (getDerived().shouldTraversePostOrder()) {
+        TRY_TO(PostVisitStmt(CurrS));
+      }
       continue;
     }
 

 #define DEF_TRAVERSE_TYPE(TYPE, CODE)                                          \
   template <typename Derived>                                                  \
   bool RecursiveASTVisitor<Derived>::Traverse##TYPE(TYPE *T) {                 \
-    TRY_TO(WalkUpFrom##TYPE(T));                                               \
+    if (!getDerived().shouldTraversePostOrder())                               \
+      TRY_TO(WalkUpFrom##TYPE(T));                                             \
     { CODE; }                                                                  \
+    if (getDerived().shouldTraversePostOrder())                                \
+      TRY_TO(WalkUpFrom##TYPE(T));                                             \
     return true;                                                               \
   }
 

 #define DEF_TRAVERSE_DECL(DECL, CODE)                                          \
   template <typename Derived>                                                  \
   bool RecursiveASTVisitor<Derived>::Traverse##DECL(DECL *D) {                 \
-    TRY_TO(WalkUpFrom##DECL(D));                                               \
+    bool ShouldVisitChildren = true;                                           \
+    bool ReturnValue = true;                                                   \
+    if (!getDerived().shouldTraversePostOrder())                               \
+      TRY_TO(WalkUpFrom##DECL(D));                                             \
     { CODE; }                                                                  \
-    TRY_TO(TraverseDeclContextHelper(dyn_cast<DeclContext>(D)));               \
-    return true;                                                               \
+    if (ReturnValue && ShouldVisitChildren)                                    \
+      TRY_TO(TraverseDeclContextHelper(dyn_cast<DeclContext>(D)));             \
+    if (ReturnValue && getDerived().shouldTraversePostOrder())                 \
+      TRY_TO(WalkUpFrom##DECL(D));                                             \
+    return ReturnValue;                                                        \
   }
 
 DEF_TRAVERSE_DECL(AccessSpecDecl, {})

       TRY_TO(TraverseStmt(I.getCopyExpr()));
     }
   }
-  // This return statement makes sure the traversal of nodes in
-  // decls_begin()/decls_end() (done in the DEF_TRAVERSE_DECL macro)
-  // is skipped - don't remove it.
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(CapturedDecl, {
   TRY_TO(TraverseStmt(D->getBody()));
-  // This return statement makes sure the traversal of nodes in
-  // decls_begin()/decls_end() (done in the DEF_TRAVERSE_DECL macro)
-  // is skipped - don't remove it.
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(EmptyDecl, {})

 
   // We shouldn't traverse an aliased namespace, since it will be
   // defined (and, therefore, traversed) somewhere else.
-  //
-  // This return statement makes sure the traversal of nodes in
-  // decls_begin()/decls_end() (done in the DEF_TRAVERSE_DECL macro)
-  // is skipped - don't remove it.
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(LabelDecl, {// There is no code in a LabelDecl.

   if (D->isThisDeclarationADefinition()) {
     TRY_TO(TraverseStmt(D->getBody()));
   }
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(ObjCTypeParamDecl, {

     TRY_TO(TraverseTypeLoc(D->getTypeSourceInfo()->getTypeLoc()));
   else
     TRY_TO(TraverseType(D->getType()));
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(UsingDecl, {

 DEF_TRAVERSE_DECL(FunctionDecl, {
   // We skip decls_begin/decls_end, which are already covered by
   // TraverseFunctionHelper().
-  return TraverseFunctionHelper(D);
+  ShouldVisitChildren = false;
+  ReturnValue = TraverseFunctionHelper(D);
 })
 
 DEF_TRAVERSE_DECL(CXXMethodDecl, {
   // We skip decls_begin/decls_end, which are already covered by
   // TraverseFunctionHelper().
-  return TraverseFunctionHelper(D);
+  ShouldVisitChildren = false;
+  ReturnValue = TraverseFunctionHelper(D);
 })
 
 DEF_TRAVERSE_DECL(CXXConstructorDecl, {
   // We skip decls_begin/decls_end, which are already covered by
   // TraverseFunctionHelper().
-  return TraverseFunctionHelper(D);
+  ShouldVisitChildren = false;
+  ReturnValue = TraverseFunctionHelper(D);
 })
 
 // CXXConversionDecl is the declaration of a type conversion operator.

 DEF_TRAVERSE_DECL(CXXConversionDecl, {
   // We skip decls_begin/decls_end, which are already covered by
   // TraverseFunctionHelper().
-  return TraverseFunctionHelper(D);
+  ShouldVisitChildren = false;
+  ReturnValue = TraverseFunctionHelper(D);
 })
 
 DEF_TRAVERSE_DECL(CXXDestructorDecl, {
   // We skip decls_begin/decls_end, which are already covered by
   // TraverseFunctionHelper().
-  return TraverseFunctionHelper(D);
+  ShouldVisitChildren = false;
+  ReturnValue = TraverseFunctionHelper(D);
 })
 
 template <typename Derived>

   template <typename Derived>                                                  \
   bool RecursiveASTVisitor<Derived>::Traverse##STMT(                           \
       STMT *S, DataRecursionQueue *Queue) {                                    \
-    TRY_TO(WalkUpFrom##STMT(S));                                               \
+    bool ShouldVisitChildren = true;                                           \
+    bool ReturnValue = true;                                                   \
+    if (!getDerived().shouldTraversePostOrder())                               \
+      TRY_TO(WalkUpFrom##STMT(S));                                             \
     { CODE; }                                                                  \
-    for (Stmt *SubStmt : S->children()) {                                      \
-      TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);                                          \
+    if (ShouldVisitChildren) {                                                 \
+      for (Stmt *SubStmt : S->children()) {                                    \
+        TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);                              \
+      }                                                                        \
     }                                                                          \
-    return true;                                                               \
+    if (!Queue && ReturnValue && getDerived().shouldTraversePostOrder())       \
+      TRY_TO(WalkUpFrom##STMT(S));                                             \
+    return ReturnValue;                                                        \
   }
 
 DEF_TRAVERSE_STMT(GCCAsmStmt, {

   // initializer]'.  The decls above already traverse over the
   // initializers, so we don't have to do it again (which
   // children() would do).
-  return true;
+  ShouldVisitChildren = false;
 })
 
 // These non-expr stmts (most of them), do not need any action except

     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getRangeInit());
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getBody());
     // Visit everything else only if shouldVisitImplicitCode().
-    return true;
+    ShouldVisitChildren = false;
   }
 })
 DEF_TRAVERSE_STMT(MSDependentExistsStmt, {

 bool RecursiveASTVisitor<Derived>::TraverseSynOrSemInitListExpr(
     InitListExpr *S, DataRecursionQueue *Queue) {
   if (S) {
-    TRY_TO(WalkUpFromInitListExpr(S));
+    // Skip this if we traverse postorder. We will visit it later
+    // in PostVisitStmt.
+    if (!getDerived().shouldTraversePostOrder())
+      TRY_TO(WalkUpFromInitListExpr(S));
+
     // All we need are the default actions.  FIXME: use a helper function.
     for (Stmt *SubStmt : S->children()) {
       TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt);

       S->isSemanticForm() ? S->getSyntacticForm() : S, Queue));
   TRY_TO(TraverseSynOrSemInitListExpr(
       S->isSemanticForm() ? S : S->getSemanticForm(), Queue));
-  return true;
+  ShouldVisitChildren = false;
 })
 
 // GenericSelectionExpr is a special case because the types and expressions

       TRY_TO(TraverseTypeLoc(TS->getTypeLoc()));
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getAssocExpr(i));
   }
-  return true;
+  ShouldVisitChildren = false;
 })
 
 // PseudoObjectExpr is a special case because of the weirdness with

       sub = OVE->getSourceExpr();
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(sub);
   }
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_STMT(CXXScalarValueInitExpr, {

       TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(NE);
   }
 
-  return TRAVERSE_STMT_BASE(LambdaBody, LambdaExpr, S, Queue);
+  ReturnValue = TRAVERSE_STMT_BASE(LambdaBody, LambdaExpr, S, Queue);
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_STMT(CXXUnresolvedConstructExpr, {

 DEF_TRAVERSE_STMT(CoroutineBodyStmt, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getBody());
-    return true;
+    ShouldVisitChildren = false;
   }
 })
 DEF_TRAVERSE_STMT(CoreturnStmt, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getOperand());
-    return true;
+    ShouldVisitChildren = false;
   }
 })
 DEF_TRAVERSE_STMT(CoawaitExpr, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getOperand());
-    return true;
+    ShouldVisitChildren = false;
   }
 })
 DEF_TRAVERSE_STMT(CoyieldExpr, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getOperand());
-    return true;
+    ShouldVisitChildren = false;
   }
 })
 

unittests/AST/CMakeLists.txt

   EvaluateAsRValueTest.cpp
   ExternalASTSourceTest.cpp
   NamedDeclPrinterTest.cpp
+  PostOrderASTVisitor.cpp
   SourceLocationTest.cpp
   StmtPrinterTest.cpp
   )

unittests/AST/PostOrderASTVisitor.cpp

+//===- unittests/AST/PostOrderASTVisitor.cpp - Declaration printer tests --===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains tests for the post-order traversing functionality
+// of RecursiveASTVisitor.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Tooling/Tooling.h"
+
+using namespace clang;
+
+namespace {
+
+  class RecordingVisitor
+    : public RecursiveASTVisitor<RecordingVisitor> {
+
+    bool VisitPostOrder;
+  public:
+    explicit RecordingVisitor(bool VisitPostOrder)
+      : VisitPostOrder(VisitPostOrder) {
+    }
+
+    // List of visited nodes during traversal.
+    std::vector<std::string> VisitedNodes;
+
+    bool shouldTraversePostOrder() const { return VisitPostOrder; }
+
+    bool VisitBinaryOperator(BinaryOperator *Op) {
+      VisitedNodes.push_back(Op->getOpcodeStr());
+      return true;
+    }
+
+    bool VisitIntegerLiteral(IntegerLiteral *Lit) {
+      VisitedNodes.push_back(Lit->getValue().toString(10, false));
+      return true;
+    }
+
+    bool VisitVarDecl(VarDecl* D) {
+      VisitedNodes.push_back(D->getNameAsString());
+      return true;
+    }
+
+    bool VisitCXXMethodDecl(CXXMethodDecl *D) {
+      VisitedNodes.push_back(D->getQualifiedNameAsString());
+      return true;
+    }
+
+    bool VisitReturnStmt(Stmt *S) {
+      VisitedNodes.push_back("return");
+      return true;
+    }
+
+    bool VisitCXXRecordDecl(CXXRecordDecl *Declaration) {
+      VisitedNodes.push_back(Declaration->getQualifiedNameAsString());
+      return true;
+    }
+
+    bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
+      VisitedNodes.push_back(T->getDecl()->getQualifiedNameAsString());
+      return true;
+    }
+  };
+
+}
+
+TEST(RecursiveASTVisitor, PostOrderTraversal) {
+  auto ASTUnit = tooling::buildASTFromCode(
+    "template <class T> class A {"
+    "  class B {"
+    "    int foo() { while(4) { int i = 9; } return (1 + 3) + 2; }"
+    "  };"
+    "};"
+  );
+  auto TU = ASTUnit->getASTContext().getTranslationUnitDecl();
+  // We traverse the translation unit and store all
+  // visited nodes.
+  RecordingVisitor Visitor(true);
+  Visitor.TraverseTranslationUnitDecl(TU);
+
+  std::vector<std::string> expected = {
+    "4", "9", "i", "1", "3", "+", "2", "+", "return", "A::B::foo", "A::B", "A", "A::T"
+  };
+  // Compare the list of actually visited nodes
+  // with the expected list of visited nodes.
+  ASSERT_EQ(expected.size(), Visitor.VisitedNodes.size());
+  for (std::size_t I = 0; I < expected.size(); I++) {
+    ASSERT_EQ(expected[I], Visitor.VisitedNodes[I]);
+  }
+}
+
+TEST(RecursiveASTVisitor, NoPostOrderTraversal) {
+  auto ASTUnit = tooling::buildASTFromCode(
+    "template <class T> class A {"
+    "  class B {"
+    "    int foo() { return 1 + 2; }"
+    "  };"
+    "};"
+  );
+  auto TU = ASTUnit->getASTContext().getTranslationUnitDecl();
+  // We traverse the translation unit and store all
+  // visited nodes.
+  RecordingVisitor Visitor(false);
+  Visitor.TraverseTranslationUnitDecl(TU);
+
+  std::vector<std::string> expected = {
+    "A", "A::B", "A::B::foo", "return", "+", "1", "2", "A::T"
+  };
+  // Compare the list of actually visited nodes
+  // with the expected list of visited nodes.
+  ASSERT_EQ(expected.size(), Visitor.VisitedNodes.size());
+  for (std::size_t I = 0; I < expected.size(); I++) {
+    ASSERT_EQ(expected[I], Visitor.VisitedNodes[I]);
+  }
+}