Index: include/clang/AST/RecursiveASTVisitor.h =================================================================== --- include/clang/AST/RecursiveASTVisitor.h +++ include/clang/AST/RecursiveASTVisitor.h @@ -72,8 +72,8 @@ 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); @@ -133,6 +133,10 @@ /// 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 class RecursiveASTVisitor { public: /// A queue used for performing data recursion over statements. @@ -158,6 +162,9 @@ /// 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. /// @@ -349,7 +356,7 @@ 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) { \ @@ -367,9 +374,10 @@ // (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) { \ @@ -499,6 +507,7 @@ bool VisitOMPClauseWithPostUpdate(OMPClauseWithPostUpdate *Node); bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue); + bool PostVisitStmt(Stmt *S); }; template @@ -556,6 +565,24 @@ #undef DISPATCH_STMT + +template +bool RecursiveASTVisitor::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(S))); break; +#include "clang/AST/StmtNodes.inc" + } + + return true; +} + +#undef DISPATCH_STMT + template bool RecursiveASTVisitor::TraverseStmt(Stmt *S, DataRecursionQueue *Queue) { @@ -577,6 +604,9 @@ if (Visited) { LocalQueue.pop_back(); TRY_TO(dataTraverseStmtPost(CurrS)); + if (getDerived().shouldTraversePostOrder()) { + TRY_TO(PostVisitStmt(CurrS)); + } continue; } @@ -874,8 +904,11 @@ #define DEF_TRAVERSE_TYPE(TYPE, CODE) \ template \ bool RecursiveASTVisitor::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; \ } @@ -1278,10 +1311,16 @@ #define DEF_TRAVERSE_DECL(DECL, CODE) \ template \ bool RecursiveASTVisitor::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(D))); \ - return true; \ + if (ReturnValue && ShouldVisitChildren) \ + TRY_TO(TraverseDeclContextHelper(dyn_cast(D))); \ + if (ReturnValue && getDerived().shouldTraversePostOrder()) \ + TRY_TO(WalkUpFrom##DECL(D)); \ + return ReturnValue; \ } DEF_TRAVERSE_DECL(AccessSpecDecl, {}) @@ -1295,18 +1334,12 @@ 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, {}) @@ -1376,11 +1409,7 @@ // 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. @@ -1436,7 +1465,7 @@ if (D->isThisDeclarationADefinition()) { TRY_TO(TraverseStmt(D->getBody())); } - return true; + ShouldVisitChildren = false; }) DEF_TRAVERSE_DECL(ObjCTypeParamDecl, { @@ -1453,7 +1482,7 @@ TRY_TO(TraverseTypeLoc(D->getTypeSourceInfo()->getTypeLoc())); else TRY_TO(TraverseType(D->getType())); - return true; + ShouldVisitChildren = false; }) DEF_TRAVERSE_DECL(UsingDecl, { @@ -1854,19 +1883,22 @@ 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. @@ -1874,13 +1906,15 @@ 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 @@ -1932,12 +1966,19 @@ template \ bool RecursiveASTVisitor::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, { @@ -1974,7 +2015,7 @@ // 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 @@ -2006,7 +2047,7 @@ 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, { @@ -2083,7 +2124,11 @@ bool RecursiveASTVisitor::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); @@ -2103,7 +2148,7 @@ 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 @@ -2116,7 +2161,7 @@ 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 @@ -2131,7 +2176,7 @@ sub = OVE->getSourceExpr(); TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(sub); } - return true; + ShouldVisitChildren = false; }) DEF_TRAVERSE_STMT(CXXScalarValueInitExpr, { @@ -2235,7 +2280,8 @@ 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, { @@ -2361,25 +2407,25 @@ 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; } }) Index: unittests/AST/CMakeLists.txt =================================================================== --- unittests/AST/CMakeLists.txt +++ unittests/AST/CMakeLists.txt @@ -14,6 +14,7 @@ EvaluateAsRValueTest.cpp ExternalASTSourceTest.cpp NamedDeclPrinterTest.cpp + PostOrderASTVisitor.cpp SourceLocationTest.cpp StmtPrinterTest.cpp ) Index: unittests/AST/PostOrderASTVisitor.cpp =================================================================== --- /dev/null +++ unittests/AST/PostOrderASTVisitor.cpp @@ -0,0 +1,123 @@ +//===- 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 { + + bool VisitPostOrder; + public: + explicit RecordingVisitor(bool VisitPostOrder) + : VisitPostOrder(VisitPostOrder) { + } + + // List of visited nodes during traversal. + std::vector 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 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 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 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 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]); + } +}