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

 // object (s.t. a user of RecursiveASTVisitor can override the method
 // in CALL_EXPR).
 #define TRY_TO(CALL_EXPR)                                                      \
   do {                                                                         \
     if (!getDerived().CALL_EXPR)                                               \
       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);
 ///   2. at a given node, walk up the class hierarchy, starting from
 ///      the node's dynamic type, until the top-most class (e.g. Stmt,
 ///      Decl, or Type) is reached.
 ///   3. given a (node, class) combination, where 'class' is some base
 ///      class of the dynamic type of 'node', call a user-overridable

 /// is to descend into the 'pattern' class or function body, not any
 /// explicit or implicit instantiations.  Explicit specializations
 /// are still visited, and the patterns of partial specializations
 /// are visited separately.  This behavior can be changed by
 /// overriding shouldVisitTemplateInstantiations() in the derived class
 /// 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.
   /// Parameters involving this type are used to implement data
   /// recursion over Stmts and Exprs within this class, and should
   /// typically not be explicitly specified by derived classes.
   /// The bool bit indicates whether the statement has been traversed or not.
   typedef SmallVectorImpl<llvm::PointerIntPair<Stmt *, 1, bool>>

   /// \brief Return whether this visitor should recurse into the types of
   /// TypeLocs.
   bool shouldWalkTypesOfTypeLocs() const { return true; }
 
   /// \brief Return whether this visitor should recurse into implicit
   /// 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.
   ///
   /// \returns false if the visitation was terminated early, true
   /// otherwise (including when the argument is nullptr).
   bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue = nullptr);
 
   /// Invoked before visiting a statement or expression via data recursion.

 
 // Define Traverse*(), WalkUpFrom*(), and Visit*() for unary
 // operator methods.  Unary operators are not classes in themselves
 // (they're all opcodes in UnaryOperator) but do have visitors.
 #define OPERATOR(NAME)                                                         \
   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) {                               \
     TRY_TO(WalkUpFromUnaryOperator(S));                                        \
     TRY_TO(VisitUnary##NAME(S));                                               \
     return true;                                                               \
   }                                                                            \
   bool VisitUnary##NAME(UnaryOperator *S) { return true; }
 
   UNARYOP_LIST()
 #undef OPERATOR
 
 // Define Traverse*(), WalkUpFrom*(), and Visit*() for binary
 // operator methods.  Binary operators are not classes in themselves
 // (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) {                                    \
     TRY_TO(WalkUpFrom##BINOP_TYPE(S));                                         \
     TRY_TO(VisitBin##NAME(S));                                                 \
     return true;                                                               \
   }                                                                            \
   bool VisitBin##NAME(BINOP_TYPE *S) { return true; }

 #include "clang/Basic/OpenMPKinds.def"
   /// \brief Process clauses with list of variables.
   template <typename T> bool VisitOMPClauseList(T *Node);
   /// Process clauses with pre-initis.
   bool VisitOMPClauseWithPreInit(OMPClauseWithPreInit *Node);
   bool VisitOMPClauseWithPostUpdate(OMPClauseWithPostUpdate *Node);
 
   bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue);
+  bool PostVisitStmt(Stmt *S);
 };
 
 template <typename Derived>
 bool RecursiveASTVisitor<Derived>::dataTraverseNode(Stmt *S,
                                                     DataRecursionQueue *Queue) {
 #define DISPATCH_STMT(NAME, CLASS, VAR)                                        \
   return TRAVERSE_STMT_BASE(NAME, CLASS, VAR, Queue);
 

 #include "clang/AST/StmtNodes.inc"
   }
 
   return true;
 }
 
 #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 (!S)
     return true;
 
   if (Queue) {
     Queue->push_back({S, false});
     return true;
   }
 
   SmallVector<llvm::PointerIntPair<Stmt *, 1, bool>, 8> LocalQueue;
   LocalQueue.push_back({S, false});
 
+  SmallVector<Stmt *, 16> ReverseLocalQueue;
+  ReverseLocalQueue.push_back(S);
+
   while (!LocalQueue.empty()) {
     auto &CurrSAndVisited = LocalQueue.back();
     Stmt *CurrS = CurrSAndVisited.getPointer();
     bool Visited = CurrSAndVisited.getInt();
     if (Visited) {
       LocalQueue.pop_back();
       TRY_TO(dataTraverseStmtPost(CurrS));
       continue;
     }
 
     if (getDerived().dataTraverseStmtPre(CurrS)) {
       CurrSAndVisited.setInt(true);
       size_t N = LocalQueue.size();
       TRY_TO(dataTraverseNode(CurrS, &LocalQueue));
       // Process new children in the order they were added.
       std::reverse(LocalQueue.begin() + N, LocalQueue.end());
+
+      if (getDerived().shouldTraversePostOrder()) {
+        for (std::size_t i = N; i < LocalQueue.size(); ++i) {
+          ReverseLocalQueue.push_back(LocalQueue[i].getPointer());
+        }
+      }
     } else {
       LocalQueue.pop_back();
     }
   }
 
+  if (getDerived().shouldTraversePostOrder()) {
+    for (auto Iter = ReverseLocalQueue.rbegin();
+         Iter != ReverseLocalQueue.rend(); ++Iter) {
+      TRY_TO(PostVisitStmt(*Iter));
+    }
+  }
+
   return true;
 }
 
 #define DISPATCH(NAME, CLASS, VAR)                                             \
   return getDerived().Traverse##NAME(static_cast<CLASS *>(VAR))
 
 template <typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseType(QualType T) {

 }
 
 // ----------------- Type traversal -----------------
 
 // This macro makes available a variable T, the passed-in type.
 #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;                                                               \
   }
 
 DEF_TRAVERSE_TYPE(BuiltinType, {})
 
 DEF_TRAVERSE_TYPE(ComplexType, { TRY_TO(TraverseType(T->getElementType())); })
 
 DEF_TRAVERSE_TYPE(PointerType, { TRY_TO(TraverseType(T->getPointeeType())); })

 
   return true;
 }
 
 // This macro makes available a variable D, the passed-in decl.
 #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, {})
 
 DEF_TRAVERSE_DECL(BlockDecl, {
   if (TypeSourceInfo *TInfo = D->getSignatureAsWritten())
     TRY_TO(TraverseTypeLoc(TInfo->getTypeLoc()));
   TRY_TO(TraverseStmt(D->getBody()));
   for (const auto &I : D->captures()) {
     if (I.hasCopyExpr()) {
       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, {})
 
 DEF_TRAVERSE_DECL(FileScopeAsmDecl,
                   { TRY_TO(TraverseStmt(D->getAsmString())); })
 
 DEF_TRAVERSE_DECL(ImportDecl, {})

 
 DEF_TRAVERSE_DECL(ExternCContextDecl, {})
 
 DEF_TRAVERSE_DECL(NamespaceAliasDecl, {
   TRY_TO(TraverseNestedNameSpecifierLoc(D->getQualifierLoc()));
 
   // 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.
                              })
 
 DEF_TRAVERSE_DECL(
     NamespaceDecl,
     {// Code in an unnamed namespace shows up automatically in

   }
   for (ObjCMethodDecl::param_iterator I = D->param_begin(), E = D->param_end();
        I != E; ++I) {
     TRY_TO(TraverseDecl(*I));
   }
   if (D->isThisDeclarationADefinition()) {
     TRY_TO(TraverseStmt(D->getBody()));
   }
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(ObjCTypeParamDecl, {
   if (D->hasExplicitBound()) {
     TRY_TO(TraverseTypeLoc(D->getTypeSourceInfo()->getTypeLoc()));
     // We shouldn't traverse D->getTypeForDecl(); it's a result of
     // declaring the type alias, not something that was written in the
     // source.
   }
 })
 
 DEF_TRAVERSE_DECL(ObjCPropertyDecl, {
   if (D->getTypeSourceInfo())
     TRY_TO(TraverseTypeLoc(D->getTypeSourceInfo()->getTypeLoc()));
   else
     TRY_TO(TraverseType(D->getType()));
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_DECL(UsingDecl, {
   TRY_TO(TraverseNestedNameSpecifierLoc(D->getQualifierLoc()));
   TRY_TO(TraverseDeclarationNameInfo(D->getNameInfo()));
 })
 
 DEF_TRAVERSE_DECL(UsingDirectiveDecl, {

     TRY_TO(TraverseStmt(D->getBody())); // Function body.
   }
   return true;
 }
 
 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.
 // It's not a cast expression.
 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>
 bool RecursiveASTVisitor<Derived>::TraverseVarHelper(VarDecl *D) {
   TRY_TO(TraverseDeclaratorHelper(D));
   // Default params are taken care of when we traverse the ParmVarDecl.
   if (!isa<ParmVarDecl>(D) &&
       (!D->isCXXForRangeDecl() || getDerived().shouldVisitImplicitCode()))

 // what children() does for a given class, see, e.g.,
 //   http://clang.llvm.org/doxygen/Stmt_8cpp_source.html
 
 // This macro makes available a variable S, the passed-in stmt.
 #define DEF_TRAVERSE_STMT(STMT, CODE)                                          \
   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, {
   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) {

   for (auto *I : S->decls()) {
     TRY_TO(TraverseDecl(I));
   }
   // Suppress the default iteration over children() by
   // returning.  Here's why: A DeclStmt looks like 'type var [=
   // 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
 // iterating over the children.
 DEF_TRAVERSE_STMT(BreakStmt, {})
 DEF_TRAVERSE_STMT(CXXTryStmt, {})
 DEF_TRAVERSE_STMT(CaseStmt, {})
 DEF_TRAVERSE_STMT(CompoundStmt, {})

 DEF_TRAVERSE_STMT(ObjCForCollectionStmt, {})
 DEF_TRAVERSE_STMT(ObjCAutoreleasePoolStmt, {})
 DEF_TRAVERSE_STMT(CXXForRangeStmt, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getLoopVarStmt());
     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, {
   TRY_TO(TraverseNestedNameSpecifierLoc(S->getQualifierLoc()));
   TRY_TO(TraverseDeclarationNameInfo(S->getNameInfo()));
 })
 DEF_TRAVERSE_STMT(ReturnStmt, {})
 DEF_TRAVERSE_STMT(SwitchStmt, {})

 DEF_TRAVERSE_STMT(CXXStaticCastExpr, {
   TRY_TO(TraverseTypeLoc(S->getTypeInfoAsWritten()->getTypeLoc()));
 })
 
 template <typename Derived>
 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);
     }
   }
   return true;
 }
 
 // This method is called once for each pair of syntactic and semantic
 // InitListExpr, and it traverses the subtrees defined by the two forms. This
 // may cause some of the children to be visited twice, if they appear both in
 // the syntactic and the semantic form.
 //
 // There is no guarantee about which form \p S takes when this method is called.
 DEF_TRAVERSE_STMT(InitListExpr, {
   TRY_TO(TraverseSynOrSemInitListExpr(
       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
 // are interleaved.  We also need to watch out for null types (default
 // generic associations).
 DEF_TRAVERSE_STMT(GenericSelectionExpr, {
   TRY_TO(TraverseStmt(S->getControllingExpr()));
   for (unsigned i = 0; i != S->getNumAssocs(); ++i) {
     if (TypeSourceInfo *TS = S->getAssocTypeSourceInfo(i))
       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
 // syntactic expressions and opaque values.
 DEF_TRAVERSE_STMT(PseudoObjectExpr, {
   TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getSyntacticForm());
   for (PseudoObjectExpr::semantics_iterator i = S->semantics_begin(),
                                             e = S->semantics_end();
        i != e; ++i) {
     Expr *sub = *i;
     if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(sub))
       sub = OVE->getSourceExpr();
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(sub);
   }
-  return true;
+  ShouldVisitChildren = false;
 })
 
 DEF_TRAVERSE_STMT(CXXScalarValueInitExpr, {
   // This is called for code like 'return T()' where T is a built-in
   // (i.e. non-class) type.
   TRY_TO(TraverseTypeLoc(S->getTypeSourceInfo()->getTypeLoc()));
 })
 

     for (const auto &E : T->exceptions()) {
       TRY_TO(TraverseType(E));
     }
 
     if (Expr *NE = T->getNoexceptExpr())
       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, {
   // This is called for code like 'T()', where T is a template argument.
   TRY_TO(TraverseTypeLoc(S->getTypeSourceInfo()->getTypeLoc()));
 })
 
 // These expressions all might take explicit template arguments.

 DEF_TRAVERSE_STMT(AtomicExpr, {})
 
 // For coroutines expressions, traverse either the operand
 // as written or the implied calls, depending on what the
 // derived class requests.
 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;
   }
 })
 
 // These literals (all of them) do not need any action.
 DEF_TRAVERSE_STMT(IntegerLiteral, {})
 DEF_TRAVERSE_STMT(CharacterLiteral, {})
 DEF_TRAVERSE_STMT(FloatingLiteral, {})
 DEF_TRAVERSE_STMT(ImaginaryLiteral, {})

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 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() { return 1 + 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 = {
+    "1", "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]);
+  }
+}