[ASTMatchers] Add mapAnyOf matcher

[steveire]

Summary

Make it possible to compose a matcher for different base nodes.

This accepts one or more node matcher functors and zero or more
matchers, composing the latter into the former.

This allows composing of matchers where the same inner matcher name is
used for the same concept, but with a different node functor. Currently,
there is a limitation that the nodes must be in the same "clade", so
while

mapAnyOf(ifStmt, forStmt).with(hasBody(stmt()))

can be used, functionDecl can not be added to the tuple.

It is possible to use this in clang-query, but it will require changes
to the QueryParser, so is deferred to a future review.

[steveire]

This is part of a series of commits. See them in context here: https://github.com/steveire/llvm-project/commits/mapAnyOf

[aaron.ballman]

LGTM!

[steveire]

Changed the implementation a bit to make clang-query integration easier

[aaron.ballman]

LGTM!

clang/docs/LibASTMatchersReference.html

 "int* p" and "void f()" in
   int* p;
   void f();
 
 Usable as: Any Matcher
 </pre></td></tr>
 
 
+<tr><td><em>unspecified</em></td><td class="name" onclick="toggle('mapAnyOf0')"><a name="mapAnyOf0Anchor">mapAnyOf</a></td><td>nodeMatcherFunction...</td></tr>
+<tr><td colspan="4" class="doc" id="mapAnyOf0"><pre>Matches any of the NodeMatchers with InnerMatchers nested within
+
+Given
+  if (true);
+  for (; true; );
+with the matcher
+  mapAnyOf(ifStmt, forStmt).with(
+    hasCondition(cxxBoolLiteralExpr(equals(true)))
+    ).bind("trueCond")
+matches the if and the for. It is equivalent to:
+  auto trueCond = hasCondition(cxxBoolLiteralExpr(equals(true)));
+  anyOf(
+    ifStmt(trueCond).bind("trueCond"),
+    forStmt(trueCond).bind("trueCond")
+    );
+
+The with() chain-call accepts zero or more matchers which are combined
+as-if with allOf() in each of the node matchers.
+Usable as: Any Matcher
+</pre></td></tr>
+
+
 <tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('unless0')"><a name="unless0Anchor">unless</a></td><td>Matcher&lt;*&gt;</td></tr>
 <tr><td colspan="4" class="doc" id="unless0"><pre>Matches if the provided matcher does not match.
 
 Example matches Y (matcher = cxxRecordDecl(unless(hasName("X"))))
   class X {};
   class Y {};
 
 Usable as: Any Matcher
Given
   explicit S(double) -&gt; S&lt;false&gt; // #6
 cxxConstructorDecl(isExplicit()) will match #2 and #8, but not #1, #7 or #9.
 cxxConversionDecl(isExplicit()) will match #4, but not #3.
 cxxDeductionGuideDecl(isExplicit()) will match #6, but not #5.
 </pre></td></tr>
 
 
 <tr><td>Matcher&lt;<a href="https://clang.llvm.org/doxygen/classclang_1_1CXXDependentScopeMemberExpr.html">CXXDependentScopeMemberExpr</a>&gt;</td><td class="name" onclick="toggle('hasMemberName0')"><a name="hasMemberName0Anchor">hasMemberName</a></td><td>std::string N</td></tr>
-<tr><td colspan="4" class="doc" id="hasMemberName0"><pre>Matches template-dependent, but known, member names
+<tr><td colspan="4" class="doc" id="hasMemberName0"><pre>Matches template-dependent, but known, member names.
 
 In template declarations, dependent members are not resolved and so can
 not be matched to particular named declarations.
 
 This matcher allows to match on the known name of members.
 
 Given
   template &lt;typename T&gt;

clang/docs/tools/dump_ast_matchers.py

def add_matcher(result_type, name, args, comment, is_dyncast=False):
   """Adds a matcher to one of our categories."""
   if name == 'id':
      # FIXME: Figure out whether we want to support the 'id' matcher.
      return
   matcher_id = '%s%d' % (name, ids[name])
   ids[name] += 1
   args = unify_arguments(args)
   result_type = unify_type(result_type)
+
+  docs_result_type = esc('Matcher<%s>' % result_type);
+
+  if name == 'mapAnyOf':
+    args = "nodeMatcherFunction..."
+    docs_result_type = "<em>unspecified</em>"
+
   matcher_html = TD_TEMPLATE % {
-    'result': esc('Matcher<%s>' % result_type),
+    'result': docs_result_type,
     'name': name,
     'args': esc(args),
     'comment': esc(strip_doxygen(comment)),
     'id': matcher_id,
   }
   if is_dyncast:
     dict = node_matchers
     lookup = result_type + name
   # Use a heuristic to figure out whether a matcher is a narrowing or
   # traversal matcher. By default, matchers that take other matchers as
   # arguments (and are not node matchers) do traversal. We specifically
   # exclude known narrowing matchers that also take other matchers as
   # arguments.
   elif ('Matcher<' not in args or
-        name in ['allOf', 'anyOf', 'anything', 'unless']):
+        name in ['allOf', 'anyOf', 'anything', 'unless', 'mapAnyOf']):
     dict = narrowing_matchers
     lookup = result_type + name + esc(args)
   else:
     dict = traversal_matchers
     lookup = result_type + name + esc(args)
   
   if dict.get(lookup) is None or len(dict.get(lookup)) < len(matcher_html):
     dict[lookup] = matcher_html

clang/include/clang/ASTMatchers/ASTMatchers.h

internal::TraversalWrapper<
     internal::PolymorphicMatcherWithParam2<MatcherT, P1, P2, ReturnTypesF>>
 traverse(TraversalKind TK, const internal::PolymorphicMatcherWithParam2<
                                MatcherT, P1, P2, ReturnTypesF> &InnerMatcher) {
   return internal::TraversalWrapper<
       internal::PolymorphicMatcherWithParam2<MatcherT, P1, P2, ReturnTypesF>>(
       TK, InnerMatcher);
 }
 
+template <typename... T>
+internal::Matcher<typename internal::GetClade<T...>::Type>
+traverse(TraversalKind TK, const internal::MapAnyOfHelper<T...> &InnerMatcher) {
+  return traverse(TK, InnerMatcher.with());
+}
+
 /// Matches expressions that match InnerMatcher after any implicit AST
 /// nodes are stripped off.
 ///
 /// Parentheses and explicit casts are not discarded.
 /// Given
 /// \code
 ///   class C {};
 ///   C a = C();

 ///   int y = sizeof(x) + alignof(x);
 /// \endcode
 /// unaryExprOrTypeTraitExpr()
 ///   matches \c sizeof(x) and \c alignof(x)
 extern const internal::VariadicDynCastAllOfMatcher<Stmt,
                                                    UnaryExprOrTypeTraitExpr>
     unaryExprOrTypeTraitExpr;
 
+/// Matches any of the \p NodeMatchers with InnerMatchers nested within
+///
+/// Given
+/// \code
+///   if (true);
+///   for (; true; );
+/// \endcode
+/// with the matcher
+/// \code
+///   mapAnyOf(ifStmt, forStmt).with(
+///     hasCondition(cxxBoolLiteralExpr(equals(true)))
+///     ).bind("trueCond")
+/// \endcode
+/// matches the \c if and the \c for. It is equivalent to:
+/// \code
+///   auto trueCond = hasCondition(cxxBoolLiteralExpr(equals(true)));
+///   anyOf(
+///     ifStmt(trueCond).bind("trueCond"),
+///     forStmt(trueCond).bind("trueCond")
+///     );
+/// \endcode
+///
+/// The with() chain-call accepts zero or more matchers which are combined
+/// as-if with allOf() in each of the node matchers.
+/// Usable as: Any Matcher
+template <typename T, typename... U>
+auto mapAnyOf(internal::VariadicDynCastAllOfMatcher<T, U> const &...) {
+  return internal::MapAnyOfHelper<U...>();
+}
+
 /// Matches unary expressions that have a specific type of argument.
 ///
 /// Given
 /// \code
 ///   int a, c; float b; int s = sizeof(a) + sizeof(b) + alignof(c);
 /// \endcode
 /// unaryExprOrTypeTraitExpr(hasArgumentOfType(asString("int"))
 ///   matches \c sizeof(a) and \c alignof(c)

clang/include/clang/ASTMatchers/ASTMatchersInternal.h

 bool matchesAnyBase(const CXXRecordDecl &Node,
                     const Matcher<CXXBaseSpecifier> &BaseSpecMatcher,
                     ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder);
 
 std::shared_ptr<llvm::Regex> createAndVerifyRegex(StringRef Regex,
                                                   llvm::Regex::RegexFlags Flags,
                                                   StringRef MatcherID);
 
+template <typename F, typename Tuple, std::size_t... I>
+constexpr auto applyMatcherImpl(F &&f, Tuple &&args,
+                                std::index_sequence<I...>) {
+  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(args))...);
+}
+
+template <typename F, typename Tuple>
+constexpr auto applyMatcher(F &&f, Tuple &&args) {
+  return applyMatcherImpl(
+      std::forward<F>(f), std::forward<Tuple>(args),
+      std::make_index_sequence<
+          std::tuple_size<typename std::decay<Tuple>::type>::value>());
+}
+
+template <typename T, bool IsBaseOf, typename Head, typename Tail>
+struct GetCladeImpl {
+  using Type = Head;
+};
+template <typename T, typename Head, typename Tail>
+struct GetCladeImpl<T, false, Head, Tail>
+    : GetCladeImpl<T, std::is_base_of<typename Tail::head, T>::value,
+                   typename Tail::head, typename Tail::tail> {};
+
+template <typename T, typename... U>
+struct GetClade : GetCladeImpl<T, false, T, AllNodeBaseTypes> {};
+
+template <typename CladeType, typename... MatcherTypes>
+struct MapAnyOfMatcherImpl {
+
+  template <typename... InnerMatchers>
+  BindableMatcher<CladeType>
+  operator()(InnerMatchers &&... InnerMatcher) const {
+    // TODO: Use std::apply from c++17
+    return VariadicAllOfMatcher<CladeType>()(applyMatcher(
+        internal::VariadicOperatorMatcherFunc<
+            0, std::numeric_limits<unsigned>::max()>{
+            internal::DynTypedMatcher::VO_AnyOf},
+        applyMatcher(
+            [&](auto... Matcher) {
+              return std::make_tuple(Matcher(
+                  std::forward<decltype(InnerMatcher)>(InnerMatcher)...)...);
+            },
+            std::tuple<
+                VariadicDynCastAllOfMatcher<CladeType, MatcherTypes>...>())));
+  }
+};
+
+template <typename... MatcherTypes>
+using MapAnyOfMatcher =
+    MapAnyOfMatcherImpl<typename GetClade<MatcherTypes...>::Type,
+                        MatcherTypes...>;
+
+template <typename... MatcherTypes> struct MapAnyOfHelper {
+  using CladeType = typename GetClade<MatcherTypes...>::Type;
+
+  MapAnyOfMatcher<MatcherTypes...> with;
+
+  operator BindableMatcher<CladeType>() const { return with(); }
+
+  Matcher<CladeType> bind(StringRef ID) const { return with().bind(ID); }
+};
+
 } // namespace internal
 
 } // namespace ast_matchers
 
 } // namespace clang
 
 #endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H

clang/unittests/ASTMatchers/ASTMatchersNarrowingTest.cpp

TEST_P(ASTMatchersTest, AnyOf) {
   EXPECT_TRUE(matches("int F() { if (true) return 1; }", MixedTypes));
   EXPECT_TRUE(notMatches("int F() { return 1; }", MixedTypes));
 
   EXPECT_TRUE(
       matches("void f() try { } catch (int) { } catch (...) { }",
               cxxCatchStmt(anyOf(hasDescendant(varDecl()), isCatchAll()))));
 }
 
+TEST_P(ASTMatchersTest, MapAnyOf) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+
+  StringRef Code = R"cpp(
+void F() {
+  if (true) {}
+  for ( ; false; ) {}
+}
+)cpp";
+
+  auto trueExpr = cxxBoolLiteral(equals(true));
+  auto falseExpr = cxxBoolLiteral(equals(false));
+
+  EXPECT_TRUE(matches(
+      Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                     mapAnyOf(ifStmt, forStmt).with(hasCondition(trueExpr)))));
+  EXPECT_TRUE(matches(
+      Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                     mapAnyOf(ifStmt, forStmt).with(hasCondition(falseExpr)))));
+
+  Code = R"cpp(
+void func(bool b) {}
+struct S {
+  S(bool b) {}
+};
+void F() {
+  func(false);
+  S s(true);
+}
+)cpp";
+  EXPECT_TRUE(matches(Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                                     mapAnyOf(callExpr, cxxConstructExpr)
+                                         .with(hasArgument(0, trueExpr)))));
+  EXPECT_TRUE(matches(Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                                     mapAnyOf(callExpr, cxxConstructExpr)
+                                         .with(hasArgument(0, falseExpr)))));
+
+  EXPECT_TRUE(
+      matches(Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                             mapAnyOf(callExpr, cxxConstructExpr)
+                                 .with(hasArgument(0, expr()),
+                                       hasDeclaration(functionDecl())))));
+
+  EXPECT_TRUE(matches(Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                                     mapAnyOf(callExpr, cxxConstructExpr))));
+
+  EXPECT_TRUE(matches(
+      Code, traverse(TK_IgnoreUnlessSpelledInSource,
+                     mapAnyOf(callExpr, cxxConstructExpr).bind("call"))));
+}
+
 TEST_P(ASTMatchersTest, IsDerivedFrom) {
   if (!GetParam().isCXX()) {
     return;
   }
 
   DeclarationMatcher IsDerivedFromX = cxxRecordDecl(isDerivedFrom("X"));
 
   EXPECT_TRUE(matches("class X {}; class Y : public X {};", IsDerivedFromX));