Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
v.g.vassilev closed this revision. v.g.vassilev added a comment. Landed in r274348 and r274349. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor updated this revision to Diff 62015.
teemperor added a comment.
- Stmt traversal is now always postorder, even if child statements don't
support iterative traversal (thanks Richard).
http://reviews.llvm.org/D20382
Files:
include/clang/AST/RecursiveASTVisitor.h
unittests/AST/CMakeLists.txt
unittests/AST/PostOrderASTVisitor.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]);
+ }
+}
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: 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
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
rsmith added inline comments.
Comment at: include/clang/AST/RecursiveASTVisitor.h:630-635
@@ -593,1 +629,8 @@
+ if (getDerived().shouldTraversePostOrder()) {
+for (auto Iter = ReverseLocalQueue.rbegin();
+ Iter != ReverseLocalQueue.rend(); ++Iter) {
+ TRY_TO(PostVisitStmt(*Iter));
+}
+ }
+
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`.
http://reviews.llvm.org/D20382
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
bkramer accepted this revision. bkramer added a comment. This revision is now accepted and ready to land. If there's no more executable size bloat this seems fine to me. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
v.g.vassilev added a comment. @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. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor added a comment. ping http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor added a comment. 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 Visitor that is both post- and preorder traversing, but I don't think there is any major use case for that. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor updated this revision to Diff 60176.
teemperor added a comment.
Reduced executable size bloat. Made postorder and preorder mutually exclusive
and postorder also uses the normal Visit* methods for callbacks.
http://reviews.llvm.org/D20382
Files:
include/clang/AST/RecursiveASTVisitor.h
unittests/AST/CMakeLists.txt
unittests/AST/PostOrderASTVisitor.cpp
Index: unittests/AST/PostOrderASTVisitor.cpp
===
--- /dev/null
+++ unittests/AST/PostOrderASTVisitor.cpp
@@ -0,0 +1,118 @@
+//===- 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 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() { 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 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 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]);
+ }
+}
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: 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
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
bkramer added a comment. 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? http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor added a comment. 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) http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor added a comment. Size changes to clang's binary (build with clang): Release: 63367728 Byte -> 6326141 Byte (0.2% less, -106kB) Debug: 1239669408 Byte -> 1264216256 Byte (2% increase, +24.5 MB) http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
bkramer added a comment. 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. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
klimek added a reviewer: bkramer. klimek added a comment. Generally makes sense; adding d0k for additional thoughts. http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D20382: Add postorder support to RecursiveASTVisitor
teemperor added a comment. 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 http://reviews.llvm.org/D20382 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
