Fix the postorder visting of the ClassTemplateSpecializationDecl nodes in the RecursiveASTVisitor.

[MontyKutyi]

Summary

The TraverseDecl method of the RecursiveASTVisitor reaches different number of nodes in postorder than in preorder visit mode in some cases, which must be a bug.
In the following example during traversing the TranslationUnitDecl node the preorder visitor reaches the ClassTemplateSpecializationDecl node but the postorder visitor does not.

template <typename> class X
{};

template class X<int>;

This must be the result of a bug in the DEF_TRAVERSE_TMPL_SPEC_DECL, which returns true in some cases and preventing not only the traversal of the declaration context of that node but the calling of the postorder visit action in the DEF_TRAVERSE_DECL macro too.

[MontyKutyi]

Just added the whole file instead of a small surrounding to be able to check the DEF_TRAVERSE_DECL macro too.

[MontyKutyi]

Could anybody take a look at on this please?

Thanks,
Peter

[MontyKutyi]

Ping.

[bruno]

Hi Peter,

Please add a testcase for this change, it also seems that you should update the comment.

[MontyKutyi]

Updated the comment.

[MontyKutyi]

As I can see the clang/test contains a lot of different simple tests, but for testing this I think it is not enough to run the clang with some arguments on a specific input. So I should create a new executable which uses the postorder mode of the RecursiveASTVisitor. Am I right or is there another preferred way for doing this?

[bruno]

In D34030#819699, @MontyKutyi wrote:

As I can see the clang/test contains a lot of different simple tests, but for testing this I think it is not enough to run the clang with some arguments on a specific input. So I should create a new executable which uses the postorder mode of the RecursiveASTVisitor. Am I right or is there another preferred way for doing this?

The place you're looking for here is in unittests. For example, see unittests/AST/PostOrderASTVisitor.cpp.

[MontyKutyi]

Added test for the fix.

[bruno]

In D34030#821282, @MontyKutyi wrote:

Added test for the fix.

Great! The test code you added doesn't seem to be compatible with clang style, can you run clang format and update the test?

[MontyKutyi]

Is there any particular parameter for the clang-format what I should use? If I just run it without any parameter it changes lines of the original test too.

[MontyKutyi]

I run the clang-format with -style=llvm on the added code parts.

[bruno]

Nice!

One more comment: please also fix names of local variables, member variables and function parameters. See https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly. Yes, there is precedence for violations in other places in this file, but that doesn't mean we should keep adding those :-)

[MontyKutyi]

Did the renamings.

[MontyKutyi]

Any further request on this?

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[MontyKutyi]

Updated to the latest trunk version.

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[MontyKutyi]

Ping.

[bruno]

The change seems good to me in general. I wonder if this will hit any broken assumption in the code. Did you run other tests beside unittests?

[rsmith]

Generally this looks good.

Is there some way we can prevent this bug from recurring by construction (eg, by making a return ill-formed, or making it "just work")? Wrapping the code block in the DEF_TRAVERSE_* invocation in a lambda would help, but would probably significantly increase the compile-time (and possibly code size) cost of RecursiveASTVisitor, so I'd prefer a different solution if possible. We could move the post-code-block actions into the destructor of an RAII object, but then we can't suppress running them when the code block returns false. Ideas welcome.

include/clang/AST/RecursiveASTVisitor.h

1587

Same problem here?

2430

Likewise.

[MontyKutyi]

In D34030#967749, @bruno wrote:

The change seems good to me in general. I wonder if this will hit any broken assumption in the code. Did you run other tests beside unittests?

I run the tests available by building the clang-test only.

include/clang/AST/RecursiveASTVisitor.h

DEF_TRAVERSE_DECL(OMPThreadPrivateDecl, {
   }
 })
 
 DEF_TRAVERSE_DECL(OMPDeclareReductionDecl, {
   TRY_TO(TraverseStmt(D->getCombiner()));
   if (auto *Initializer = D->getInitializer())
     TRY_TO(TraverseStmt(Initializer));
   TRY_TO(TraverseType(D->getType()));
   return true;
 })
 
 DEF_TRAVERSE_DECL(OMPCapturedExprDecl, { TRY_TO(TraverseVarHelper(D)); })
 
 // A helper method for TemplateDecl's children.
 template <typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseTemplateParameterListHelper(
     TemplateParameterList *TPL) {
/* For implicit instantiations ("set<int> x;"), we don't want to           \
        is the only callback that's made for this instantiation.                \
        We use getTypeAsWritten() to distinguish. */                            \
     if (TypeSourceInfo *TSI = D->getTypeAsWritten())                           \
       TRY_TO(TraverseTypeLoc(TSI->getTypeLoc()));                              \
                                                                                \
     TRY_TO(TraverseNestedNameSpecifierLoc(D->getQualifierLoc()));              \
     if (!getDerived().shouldVisitTemplateInstantiations() &&                   \
         D->getTemplateSpecializationKind() != TSK_ExplicitSpecialization)      \
-      /* Returning from here skips traversing the                              \
-         declaration context of the *TemplateSpecializationDecl                \
-         (embedded in the DEF_TRAVERSE_DECL() macro)                           \
-         which contains the instantiated members of the template. */           \
-      return true;                                                             \
+      /* Skip traversing the declaration context of the                        \
+         *TemplateSpecializationDecl (embedded in the DEF_TRAVERSE_DECL()      \
+         macro) which contains the instantiated members of the template. */    \
+      ShouldVisitChildren = false;                                             \
   })
 
 DEF_TRAVERSE_TMPL_SPEC_DECL(Class)
 DEF_TRAVERSE_TMPL_SPEC_DECL(Var)
 
 template <typename Derived>
 bool RecursiveASTVisitor<Derived>::TraverseTemplateArgumentLocsHelper(
     const TemplateArgumentLoc *TAL, unsigned Count) {

 // These exprs (most of them), do not need any action except iterating
 // over the children.
 DEF_TRAVERSE_STMT(AddrLabelExpr, {})
 DEF_TRAVERSE_STMT(ArraySubscriptExpr, {})
 DEF_TRAVERSE_STMT(OMPArraySectionExpr, {})
 
 DEF_TRAVERSE_STMT(BlockExpr, {
   TRY_TO(TraverseDecl(S->getBlockDecl()));
   return true; // no child statements to loop through.
 })
 
 DEF_TRAVERSE_STMT(ChooseExpr, {})
 DEF_TRAVERSE_STMT(CompoundLiteralExpr, {
   TRY_TO(TraverseTypeLoc(S->getTypeSourceInfo()->getTypeLoc()));
 })
 DEF_TRAVERSE_STMT(CXXBindTemporaryExpr, {})
 DEF_TRAVERSE_STMT(CXXBoolLiteralExpr, {})

unittests/AST/PostOrderASTVisitor.cpp

 // This file contains tests for the post-order traversing functionality
 // of RecursiveASTVisitor.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include <algorithm>
 
 using namespace clang;
 
 namespace {
 
   class RecordingVisitor
     : public RecursiveASTVisitor<RecordingVisitor> {
 
public:
     }
 
     bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
       VisitedNodes.push_back(T->getDecl()->getQualifiedNameAsString());
       return true;
     }
   };
 
+
+// Serializes the AST. It is not complete! It only serializes the Statement
+// and the Declaration nodes.
+class ASTSerializerVisitor : public RecursiveASTVisitor<ASTSerializerVisitor> {
+private:
+  std::vector<void *> &VisitedNodes;
+  const bool PostOrderTraverse;
+
+public:
+  ASTSerializerVisitor(bool PostOrderTraverse,
+                       std::vector<void *> &VisitedNodes)
+      : VisitedNodes(VisitedNodes), PostOrderTraverse(PostOrderTraverse) {}
+
+  bool shouldTraversePostOrder() const { return PostOrderTraverse; }
+
+  bool VisitStmt(Stmt *S) {
+    VisitedNodes.push_back(S);
+    return true;
   }
 
+  bool VisitDecl(Decl *D) {
+    VisitedNodes.push_back(D);
+    return true;
+  }
+};
+
+} // anonymous namespace
+
 TEST(RecursiveASTVisitor, PostOrderTraversal) {
   auto ASTUnit = tooling::buildASTFromCode(
     "class A {"
     "  class B {"
     "    int foo() { while(4) { int i = 9; int j = -5; } return (1 + 3) + 2; }"
     "  };"
     "};"
   );
TEST(RecursiveASTVisitor, NoPostOrderTraversal) {
   };
   // 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, PrePostComparisonTest) {
+  auto ASTUnit = tooling::buildASTFromCode("template <typename> class X {};"
+                                           "template class X<int>;");
+
+  auto TU = ASTUnit->getASTContext().getTranslationUnitDecl();
+
+  std::vector<void *> PreorderNodeList, PostorderNodeList;
+
+  ASTSerializerVisitor PreVisitor(false, PreorderNodeList);
+  PreVisitor.TraverseTranslationUnitDecl(TU);
+
+  ASTSerializerVisitor PostVisitor(true, PostorderNodeList);
+  PostVisitor.TraverseTranslationUnitDecl(TU);
+
+  // The number of visited nodes must be independent of the ordering mode.
+  ASSERT_EQ(PreorderNodeList.size(), PostorderNodeList.size());
+
+  std::sort(PreorderNodeList.begin(), PreorderNodeList.end());
+  std::sort(PostorderNodeList.begin(), PostorderNodeList.end());
+
+  // Both traversal must visit the same nodes.
+  ASSERT_EQ(std::mismatch(PreorderNodeList.begin(), PreorderNodeList.end(),
+                          PostorderNodeList.begin())
+                .first,
+            PreorderNodeList.end());
+}