[AST] Add MatchFinder::matchSubtree

[martong]

Summary

Add matchSubtree, so we can traverse on a subtree rooted on a specific node.

Currently, we can match one node against a matcher, but we will not traverse
into the children (this is MatchFinder::match).
Or we can traverse through the whole tree rooted at the TUDecl (this
is MatchFinder::matchAST).
Note, findAll may provide an alternative, but that will traverse throught the
whole AST, and that has some weaknesses:
https://bugs.llvm.org/show_bug.cgi?id=38318

[klimek]

Usually we use match(anyOf(node), hasDescendant(node)). Or did I misunderstand what you want?

[martong]

Usually we use match(anyOf(node), hasDescendant(node)). Or did I misunderstand what you want?

My understanding is that, the free function template match uses MatchFinder::matchAST, which will start the traverse from the TranslationUnitDecl.
And there is no option to pick a specific node and specify that as the root of the traverse. I'd like an option to be able to start the traverse from a specific node, if it makes sense.

[martong]

MatchFinder::match allows you to match a node. Wrapping your matcher code with:
auto m = <my cool matcher>;
ast_matchers::match(anyOf(m, hashDescendant(m)), node, context);

Okay, I understand and accept that.
However, I consider that a different level of abstraction. ast_matchers::match uses internal::CollectMatchesCallback in its implementation. If I already have my own custom MatchCallback implemented then there is no way to achieve the desired behavior.

For example, in ASTImporter tests we use the following customized callback class:

enum class DeclMatcherKind { First, Last };

// Matcher class to retrieve the first/last matched node under a given AST.
template <typename NodeType, DeclMatcherKind MatcherKind>
class DeclMatcher : public MatchFinder::MatchCallback {
  NodeType *Node = nullptr;
  void run(const MatchFinder::MatchResult &Result) override {
    if ((MatcherKind == DeclMatcherKind::First && Node == nullptr) ||
        MatcherKind == DeclMatcherKind::Last) {
      Node = const_cast<NodeType *>(Result.Nodes.getNodeAs<NodeType>(""));
    }
  }
public:
  // Returns the first/last matched node under the tree rooted in the TranslationUnitDecl of `D`.
  template <typename MatcherType>
  NodeType *match(const Decl *D, const MatcherType &AMatcher) {
    MatchFinder Finder;
    Finder.addMatcher(AMatcher.bind(""), this);
    Finder.matchAST(D->getASTContext());
    assert(Node);
    return Node;
  }
};
template <typename NodeType>
using LastDeclMatcher = DeclMatcher<NodeType, DeclMatcherKind::Last>;
template <typename NodeType>
using FirstDeclMatcher = DeclMatcher<NodeType, DeclMatcherKind::First>;

And this is how we use it in the tests:

Decl *FromTU = getTuDecl("void f(); void f(); void f() { int a; }", Lang_CXX);
auto Pattern = functionDecl(hasName("f"));
auto *D0 = FirstDeclMatcher<FunctionDecl>().match(FromTU, Pattern);
auto *D2 = LastDeclMatcher<FunctionDecl>().match(FromTU, Pattern);

At this point we would like to extend this DeclMatcher to be able to match a subtree, and be able to start the traverse from a specific Decl, something like this :

auto *DV = FirsDeclMatcher<VarDecl>().match(D2, SomeOtherPattern);

Currently, I don't see how could we do this extension without the proposed matchSubtree.
(Perhaps, we could refactor our DeclMatcher to not use a customized MatchCallback, rather use ast_matchers::match, but that sounds like a bad workaround to me.)

Hope this makes the the goal of this patch cleaner.

[martong]

Finder.match also has an overload that takes the node. Can you wrap "Pattern" above in the anyOf(hasDescendant(...), ...) and match on the node instead of the full AST?

Ok, I changed and wrapped the pattern:

template <typename MatcherType>
NodeType *match(const Decl *D, const MatcherType &AMatcher) {
  MatchFinder Finder;
  auto WrappedMatcher = anyOf(AMatcher.bind(""), hasDescendant(AMatcher.bind("")));
  Finder.addMatcher(WrappedMatcher, this);
  // ...
}

But this results in an ambigous call of addMatcher because the compiler cannot choose the appropriate overload:

../../git/llvm/tools/clang/unittests/AST/DeclMatcher.h:36:12: error: call to member function 'addMatcher' is ambiguous
    Finder.addMatcher(WrappedMatcher, this);
    ~~~~~~~^~~~~~~~~~
...
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:149:8: note: candidate function
  void addMatcher(const DeclarationMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:151:8: note: candidate function
  void addMatcher(const TypeMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:153:8: note: candidate function
  void addMatcher(const StatementMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:155:8: note: candidate function
  void addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:157:8: note: candidate function
  void addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:159:8: note: candidate function
  void addMatcher(const TypeLocMatcher &NodeMatch,
       ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:161:8: note: candidate function
  void addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
       ^

This seems quite logical to me, since anyOf wraps many matchers, which could refer to Nodes with different type.
So, I went on and specified which overload to call (note, from this point this is getting hacky and would not consider such an API easy to use):

And then I gave up.
  template <typename MatcherType>
  NodeType *match(const Decl *D, const MatcherType &AMatcher) {
    MatchFinder Finder;
    auto WrappedMatcher = anyOf(AMatcher.bind(""), hasDescendant(AMatcher.bind("")));
    auto PtrToMemFun = static_cast<void (MatchFinder::*)(
        const DeclarationMatcher&, MatchCallback*)>(&MatchFinder::addMatcher);
    (Finder.*PtrToMemFun)(WrappedMatcher, this);

This time it turned out that we can't just add a matcker like this because getMatchers in anyOf would call the private ctor of Matcher:

../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h:1339:13: error: calling a private constructor of class 'clang::ast_matchers::internal::Matcher<clang::Decl>'
    return {Matcher<T>(std::get<Is>(Params))...};
            ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h:1331:16: note: in instantiation of function template specialization 'clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::Matcher<clang::Stmt>, clang::ast_matchers::internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::QualType, clang::Type, clang::TypeLoc, clang::CXXCtorInitializer>, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::TypeLoc, clang::QualType> >::Adaptor<clang::Stmt> >::getMatchers<clang::Decl, 0, 1>' requested here
               getMatchers<T>(llvm::index_sequence_for<Ps...>()))
               ^

As an alternative, I tried to call addDynamicMatcher, which resulted in a conversion error:

template <typename MatcherType>
NodeType *match(const Decl *D, const MatcherType &AMatcher) {
  MatchFinder Finder;
  auto WrappedMatcher = anyOf(AMatcher.bind(""), hasDescendant(AMatcher.bind("")));
  Finder.addDynamicMatcher(WrappedMatcher, this);

../../git/llvm/tools/clang/unittests/AST/DeclMatcher.h:40:30: error: no viable conversion from 'clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::Matcher<clang::Decl>, clang::ast_matchers::internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::QualType, clang::Type, clang::TypeLoc, clang::CXXCtorInitializer>, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::TypeLoc, clang::QualType> >::Adaptor<clang::Decl> >' to 'const internal::DynTypedMatcher'
    Finder.addDynamicMatcher(WrappedMatcher, this);
                             ^~~~~~~~~~~~~~

Perhaps I am doing something wrong because I really could not find a way to add the wrapped matcher.
These results motivated me to double check your original idea of using ast_matchers::match:

Decl *FromTU = getTuDecl("void f();", Lang_CXX);
auto Pattern = functionDecl(hasName("f"));
match(anyOf(Pattern, hasDescendant(Pattern)), FromTU, FromTU->getASTContext());

This resulted an ambigous call again, but this time the compiler could not resolve the call inside ast_matchers::match:

../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchFinder.h:301:10: error: call to member function 'addMatcher' is ambiguous
  Finder.addMatcher(Matcher, &Callback);
  ~~~~~~~^~~~~~~~~~

[martong]

If you know the node is a decl, wrapping it in decl() should be enough.
Does this work?
auto WrappedMatcher = decl(anyOf(...));

Unfortunately this gives again the private ctor error (the same error when I called explicitly the overload with the DeclarationMatcher):

../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h:1339:13: error: calling a private constructor of class 'clang::ast_matchers::internal::Matcher<clang::Decl>'
    return {Matcher<T>(std::get<Is>(Params))...};
            ^
../../git/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h:1331:16: note: in instantiation of function template specialization 'clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::Matcher<clang::Stmt>, clang::ast_matchers::internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::QualType, clang::Type, clang::TypeLoc, clang::CXXCtorInitializer>, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::TypeLoc, clang::QualType> >::Adaptor<clang::Stmt> >::getMatchers<clang::Decl, 0, 1>' requested here
               getMatchers<T>(llvm::index_sequence_for<Ps...>()))
               ^
../../git/llvm/tools/clang/unittests/AST/DeclMatcher.h:35:32: note: in instantiation of function template specialization 'clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::Matcher<clang::Stmt>, clang::ast_matchers::internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::QualType, clang::Type, clang::TypeLoc, clang::CXXCtorInitializer>, clang::ast_matchers::internal::TypeList<clang::Decl, clang::Stmt, clang::NestedNameSpecifier, clang::NestedNameSpecifierLoc, clang::TypeLoc, clang::QualType> >::Adaptor<clang::Stmt> >::operator Matcher<clang::Decl>' requested here
    auto WrappedMatcher = decl(anyOf(AMatcher.bind(""), hasDescendant(AMatcher.bind(""))));
                               ^

Even if it would work then how could I support nodes other than decls (e.g. stmt())?

[steveire]

In D49840#1176405, @klimek wrote:

Usually we use match(anyOf(node), hasDescendant(node)). Or did I misunderstand what you want?

See http://lists.llvm.org/pipermail/cfe-dev/2018-July/058625.html for a bug that prevents this working.

[martong]

Ping.

Manuel, I still don't see how could we apply match(anyOf(node), hasDescendant(node)) to the problem of general subtree traversal.
(I'd like to have support for not just decl() but other kind of nodes too.)
Could you please advise how to move on? Also, could you please describe your specific technical arguments against this patch?

include/clang/ASTMatchers/ASTMatchFinder.h

public:
   /// @{
   template <typename T> void match(const T &Node, ASTContext &Context) {
     match(clang::ast_type_traits::DynTypedNode::create(Node), Context);
   }
   void match(const clang::ast_type_traits::DynTypedNode &Node,
              ASTContext &Context);
   /// @}
 
+  /// \brief Finds all matches in the given subtree rooted at \p Node
+  /// @{
+  template <typename T> void matchSubtree(const T &Node, ASTContext &Context) {
+    matchSubtree(clang::ast_type_traits::DynTypedNode::create(Node), Context);
+  }
+  void matchSubtree(const clang::ast_type_traits::DynTypedNode &Node,
+                    ASTContext &Context);
+  /// @}
+
   /// Finds all matches in the given AST.
   void matchAST(ASTContext &Context);
 
   /// Registers a callback to notify the end of parsing.
   ///
   /// The provided closure is called after parsing is done, before the AST is
   /// traversed. Useful for benchmarking.
   /// Each call to FindAll(...) will call the closure once.

lib/ASTMatchers/ASTMatchFinder.cpp

 
 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
                         ASTContext &Context) {
   internal::MatchASTVisitor Visitor(&Matchers, Options);
   Visitor.set_active_ast_context(&Context);
   Visitor.match(Node);
 }
 
+void MatchFinder::matchSubtree(const clang::ast_type_traits::DynTypedNode &Node,
+                               ASTContext &Context) {
+  internal::MatchASTVisitor Visitor(&Matchers, Options);
+  Visitor.set_active_ast_context(&Context);
+  // FIXME: Improve this with a switch or a visitor pattern.
+  if (auto *N = Node.get<Decl>()) {
+    if (dyn_cast<TranslationUnitDecl>(N))
+      Visitor.onStartOfTranslationUnit();
+    Visitor.TraverseDecl(const_cast<Decl *>(N));
+    if (dyn_cast<TranslationUnitDecl>(N))
+      Visitor.onEndOfTranslationUnit();
+  } else if (auto *N = Node.get<Stmt>()) {
+    Visitor.TraverseStmt(const_cast<Stmt *>(N));
+  } else if (auto *N = Node.get<QualType>()) {
+    Visitor.TraverseType(*N);
+  } else if (auto *N = Node.get<TypeLoc>()) {
+    Visitor.TraverseTypeLoc(*N);
+  } else if (auto *N = Node.get<NestedNameSpecifier>()) {
+    Visitor.TraverseNestedNameSpecifier(const_cast<NestedNameSpecifier *>(N));
+  } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
+    Visitor.TraverseNestedNameSpecifierLoc(*N);
+  } else if (auto *N = Node.get<CXXCtorInitializer>()) {
+    Visitor.TraverseConstructorInitializer(const_cast<CXXCtorInitializer *>(N));
+  }
+}
+
 void MatchFinder::matchAST(ASTContext &Context) {
   internal::MatchASTVisitor Visitor(&Matchers, Options);
   Visitor.set_active_ast_context(&Context);
   Visitor.onStartOfTranslationUnit();
   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
   Visitor.onEndOfTranslationUnit();
 }
 

unittests/ASTMatchers/ASTMatchersInternalTest.cpp

EXPECT_TRUE(matchesConditionally(
       "#include <bar>\n"
       "class X {};",
       recordDecl(isExpansionInFileMatching("f.*"), hasName("X")), false,
       "-isystem/", M));
 }
 
 #endif // _WIN32
 
+
+TEST(Matcher, matchSubtree) {
+
+  std::unique_ptr<ASTUnit> AST =
+      clang::tooling::buildASTFromCode(
+      R"(
+      template <typename T>
+      struct X {
+        void f() {}
+        void g() {}
+      };
+      void foo() {
+          X<char> xc;
+          xc.f();
+          X<int> xi;
+      }
+      )");
+  ASSERT_TRUE(AST.get());
+
+  // To get the "f" FunctionDecl inside the instantiation ...
+  auto FullPattern =
+      functionDecl(hasName("f")
+          // ... we must specify the parent.
+          ,hasParent(classTemplateSpecializationDecl()));
+  auto *FunD = selectFirst<FunctionDecl>(
+      "dontcare", match(FullPattern.bind("dontcare"), AST->getASTContext()));
+
+
+  auto *SpecD = selectFirst<ClassTemplateSpecializationDecl>(
+      "dontcare", match(classTemplateSpecializationDecl().bind("dontcare"),
+                        AST->getASTContext()));
+  MatchFinder Finder;
+  struct TestCallback : MatchFinder::MatchCallback {
+    FunctionDecl *Node = nullptr;
+    void run(const MatchFinder::MatchResult &Result) override {
+      Node =
+          const_cast<FunctionDecl *>(Result.Nodes.getNodeAs<FunctionDecl>(""));
+    }
+  };
+  TestCallback Cb;
+
+  // With matchSubtree we can traverse through the given instantiation.
+  auto SimplePattern = functionDecl(hasName("f"));
+  Finder.addMatcher(SimplePattern.bind(""), &Cb);
+  Finder.matchSubtree(*SpecD, AST->getASTContext());
+  EXPECT_EQ(FunD, Cb.Node);
+}
+
 } // end namespace ast_matchers
 } // end namespace clang