[AST] Traverse templates in LexicallyOrderedRecursiveASTVisitor

[johannes]

Summary

We need to specialize this because RecursiveASTVisitor visits template
template parameters after the templated declaration, unlike the order in
which they appear in the source code.

[johannes]

use LexicallyOrderedRecursiveASTVisitor

[johannes]

unittests/Tooling/LexicallyOrderedRecursiveASTVisitorTest.cpp

154

This test also works before the change; what is the best way to enforce an ordering here?

[arphaman]

Awesome, thanks!

unittests/Tooling/LexicallyOrderedRecursiveASTVisitorTest.cpp

154

You can add a flag to LexicallyOrderedDeclVisitor that emits the ordering index when it's true and turn it on for this test. Then you'd should get something like /f/T@0 and /f/T@1.

Please test a class template as well.

[johannes]

test ordering, class template

[johannes]

This is currently broken, if a user provides a TraverseClassTemplateDecl, then the same method in this class will not be called, I think I will add a flag (probably not user visible) in RecursiveASTVisitor.h to switch the order for templates

[johannes]

fix by adding an option in RecursiveASTVisitor

[arphaman]

include/clang/AST/RecursiveASTVisitor.h

507–508

I don't think you need to make this public with the new patch, right?

[johannes]

undo visibility change

[arphaman]

LGTM

[pdouglas]

This comment was removed by pdouglas.

include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

for (auto I = DC->decls_begin(), E = DC->decls_end(); I != E;) {
           LexicallyNestedDeclarations.push_back(Sibling);
       }
       if (!BaseType::getDerived().TraverseDecl(Child))
         return false;
     }
     return true;
   }
 
+  bool shouldTraverseTemplateArgumentsBeforeDecl() const { return true; }
+
 private:
   bool TraverseAdditionalLexicallyNestedDeclarations() {
     // FIXME: Ideally the gathered declarations and the declarations in the
     // @implementation should be mixed and sorted to get a true lexical order,
     // but right now we only care about getting the correct lexical parent, so
     // we can traverse the gathered nested declarations after the declarations
     // in the decl context.
     assert(!BaseType::getDerived().shouldTraversePostOrder() &&

include/clang/AST/RecursiveASTVisitor.h

bool WalkUpFrom##CLASS##Decl(CLASS##Decl *D) {                               \
     TRY_TO(Visit##CLASS##Decl(D));                                             \
     return true;                                                               \
   }                                                                            \
   bool Visit##CLASS##Decl(CLASS##Decl *D) { return true; }
 #include "clang/AST/DeclNodes.inc"
 
   bool canIgnoreChildDeclWhileTraversingDeclContext(const Decl *Child);
 
-private:
   // These are helper methods used by more than one Traverse* method.
   bool TraverseTemplateParameterListHelper(TemplateParameterList *TPL);
 
+private:
   // Traverses template parameter lists of either a DeclaratorDecl or TagDecl.
   template <typename T>
   bool TraverseDeclTemplateParameterLists(T *D);
 
 #define DEF_TRAVERSE_TMPL_INST(TMPLDECLKIND)                                   \
   bool TraverseTemplateInstantiations(TMPLDECLKIND##TemplateDecl *D);
   DEF_TRAVERSE_TMPL_INST(Class)
   DEF_TRAVERSE_TMPL_INST(Var)
   DEF_TRAVERSE_TMPL_INST(Function)
 #undef DEF_TRAVERSE_TMPL_INST
   bool TraverseTemplateArgumentLocsHelper(const TemplateArgumentLoc *TAL,
#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);
+  bool shouldTraverseTemplateArgumentsBeforeDecl() const { return false; }
 };
 
 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);
 
bool RecursiveASTVisitor<Derived>::TraverseTemplateInstantiations(
 
   return true;
 }
 
 // This macro unifies the traversal of class, variable and function
 // template declarations.
 #define DEF_TRAVERSE_TMPL_DECL(TMPLDECLKIND)                                   \
   DEF_TRAVERSE_DECL(TMPLDECLKIND##TemplateDecl, {                              \
-    TRY_TO(TraverseDecl(D->getTemplatedDecl()));                               \
-    TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));   \
+    if (getDerived().shouldTraverseTemplateArgumentsBeforeDecl()) {            \
+      TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters())); \
+      TRY_TO(TraverseDecl(D->getTemplatedDecl()));                             \
+    } else {                                                                   \
+      TRY_TO(TraverseDecl(D->getTemplatedDecl()));                             \
+      TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters())); \
+    }                                                                          \
                                                                                \
     /* By default, we do not traverse the instantiations of                    \
        class templates since they do not appear in the user code. The          \
        following code optionally traverses them.                               \
                                                                                \
        We only traverse the class instantiations when we see the canonical     \
        declaration of the template, to ensure we only visit them once. */      \
     if (getDerived().shouldVisitTemplateInstantiations() &&                    \

unittests/Tooling/LexicallyOrderedRecursiveASTVisitorTest.cpp

 namespace {
 
 class DummyMatchVisitor;
 
 class LexicallyOrderedDeclVisitor
     : public LexicallyOrderedRecursiveASTVisitor<LexicallyOrderedDeclVisitor> {
 public:
   LexicallyOrderedDeclVisitor(DummyMatchVisitor &Matcher,
-                              const SourceManager &SM)
-      : LexicallyOrderedRecursiveASTVisitor(SM), Matcher(Matcher) {}
+                              const SourceManager &SM, bool EmitIndices)
+      : LexicallyOrderedRecursiveASTVisitor(SM), Matcher(Matcher),
+        EmitIndices(EmitIndices) {}
 
   bool TraverseDecl(Decl *D) {
     TraversalStack.push_back(D);
     LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
     TraversalStack.pop_back();
     return true;
   }
 
   bool VisitNamedDecl(const NamedDecl *D);
 
 private:
   DummyMatchVisitor &Matcher;
+  bool EmitIndices;
+  unsigned Index = 0;
   llvm::SmallVector<Decl *, 8> TraversalStack;
 };
 
 class DummyMatchVisitor : public ExpectedLocationVisitor<DummyMatchVisitor> {
+  bool EmitIndices;
+
 public:
+  DummyMatchVisitor(bool EmitIndices = false) : EmitIndices(EmitIndices) {}
   bool VisitTranslationUnitDecl(TranslationUnitDecl *TU) {
     const ASTContext &Context = TU->getASTContext();
     const SourceManager &SM = Context.getSourceManager();
-    LexicallyOrderedDeclVisitor SubVisitor(*this, SM);
+    LexicallyOrderedDeclVisitor SubVisitor(*this, SM, EmitIndices);
     SubVisitor.TraverseDecl(TU);
     return false;
   }
 
   void match(StringRef Path, const Decl *D) { Match(Path, D->getLocStart()); }
 };
 
 bool LexicallyOrderedDeclVisitor::VisitNamedDecl(const NamedDecl *D) {
   std::string Path;
   llvm::raw_string_ostream OS(Path);
   assert(TraversalStack.back() == D);
   for (const Decl *D : TraversalStack) {
     if (isa<TranslationUnitDecl>(D)) {
       OS << "/";
       continue;
     }
     if (const auto *ND = dyn_cast<NamedDecl>(D))
       OS << ND->getNameAsString();
     else
       OS << "???";
-    if (isa<DeclContext>(D))
+    if (isa<DeclContext>(D) or isa<TemplateDecl>(D))
       OS << "/";
   }
+  if (EmitIndices)
+    OS << "@" << Index++;
   Matcher.match(OS.str(), D);
   return true;
 }
 
 TEST(LexicallyOrderedRecursiveASTVisitor, VisitDeclsInImplementation) {
   StringRef Source = R"(
 @interface I
 @end

 )";
   DummyMatchVisitor Visitor;
   Visitor.ExpectMatch("/outerFunction/", 5, 1);
   Visitor.ExpectMatch("/I/nestedFunction1/", 7, 20);
   Visitor.ExpectMatch("/nestedFunction2/", 7, 20);
   EXPECT_TRUE(Visitor.runOver(Source, DummyMatchVisitor::Lang_OBJC));
 }
 
+TEST(LexicallyOrderedRecursiveASTVisitor, VisitTemplateDecl) {
+  StringRef Source = R"(
+template <class T> T f();
+template <class U, class = void> class Class {};
+)";
+  DummyMatchVisitor Visitor(/*EmitIndices=*/true);
+  Visitor.ExpectMatch("/f/T@1", 2, 11);
+  Visitor.ExpectMatch("/f/f/@2", 2, 20);
+  Visitor.ExpectMatch("/Class/U@4", 3, 11);
+  Visitor.ExpectMatch("/Class/@5", 3, 20);
+  Visitor.ExpectMatch("/Class/Class/@6", 3, 34);
+  EXPECT_TRUE(Visitor.runOver(Source));
+}
+
 } // end anonymous namespace