Rewrite eachOf/allOf/anyOf to use a variadic operator.

Summary:
Rewrite eachOf/allOf/anyOf to use a variadic operator, instead of hand-written calls to Polymorphic matchers.
This simplifies their definition and future changes to add them to the dynamic registry.

Reviewers: klimek

CC: cfe-commits, revane

Differential Revision: http://llvm-reviews.chandlerc.com/D1427

llvm-svn: 189357

5 files changed, 211 insertions, 185 deletions

diff --git a/clang/docs/LibASTMatchersReference.html b/clang/docs/LibASTMatchersReference.html
index 544e06dc7b6..6f8f6a07c79 100644
--- a/clang/docs/LibASTMatchersReference.html
+++ b/clang/docs/LibASTMatchersReference.html
@@ -1273,14 +1273,14 @@ which allow users to create more powerful match expressions.</p>
 <tr style="text-align:left"><th>Return type</th><th>Name</th><th>Parameters</th></tr>
 <!-- START_NARROWING_MATCHERS -->
 
-<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('allOf0')"><a name="allOf0Anchor">allOf</a></td><td>Matcher&lt;*&gt;  P1, Matcher&lt;*&gt;  P2</td></tr>
+<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('allOf0')"><a name="allOf0Anchor">allOf</a></td><td>Matcher&lt;*&gt;, ..., Matcher&lt;*&gt;</td></tr>
 <tr><td colspan="4" class="doc" id="allOf0"><pre>Matches if all given matchers match.
 
 Usable as: Any Matcher
 </pre></td></tr>
 
 
-<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('anyOf0')"><a name="anyOf0Anchor">anyOf</a></td><td>Matcher&lt;*&gt;  P1, Matcher&lt;*&gt;  P2</td></tr>
+<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('anyOf0')"><a name="anyOf0Anchor">anyOf</a></td><td>Matcher&lt;*&gt;, ..., Matcher&lt;*&gt;</td></tr>
 <tr><td colspan="4" class="doc" id="anyOf0"><pre>Matches if any of the given matchers matches.
 
 Usable as: Any Matcher
@@ -1999,7 +1999,7 @@ match expressions.</p>
 <tr style="text-align:left"><th>Return type</th><th>Name</th><th>Parameters</th></tr>
 <!-- START_TRAVERSAL_MATCHERS -->
 
-<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('eachOf0')"><a name="eachOf0Anchor">eachOf</a></td><td>Matcher&lt;*&gt;  P1, Matcher&lt;*&gt;  P2</td></tr>
+<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('eachOf0')"><a name="eachOf0Anchor">eachOf</a></td><td>Matcher&lt;*&gt;, ..., Matcher&lt;*&gt;</td></tr>
 <tr><td colspan="4" class="doc" id="eachOf0"><pre>Matches if any of the given matchers matches.
 
 Unlike anyOf, eachOf will generate a match result for each
@@ -2018,21 +2018,6 @@ Usable as: Any Matcher
 </pre></td></tr>
 
 
-<tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('findAll0')"><a name="findAll0Anchor">findAll</a></td><td>Matcher&lt;T&gt;  Matcher</td></tr>
-<tr><td colspan="4" class="doc" id="findAll0"><pre>Matches if the node or any descendant matches.
-
-Generates results for each match.
-
-For example, in:
-  class A { class B {}; class C {}; };
-The matcher:
-  recordDecl(hasName("::A"), findAll(recordDecl(isDefinition()).bind("m")))
-will generate results for A, B and C.
-
-Usable as: Any Matcher
-</pre></td></tr>
-
-
 <tr><td>Matcher&lt;*&gt;</td><td class="name" onclick="toggle('forEach0')"><a name="forEach0Anchor">forEach</a></td><td>Matcher&lt;*&gt;</td></tr>
 <tr><td colspan="4" class="doc" id="forEach0"><pre>Matches AST nodes that have child AST nodes that match the
 provided matcher.
@@ -3316,6 +3301,21 @@ Usable as: Matcher&lt<a href="http://clang.llvm.org/doxygen/classclang_1_1QualTy
 </pre></td></tr>
 
 
+<tr><td>Matcher&lt;T&gt;</td><td class="name" onclick="toggle('findAll0')"><a name="findAll0Anchor">findAll</a></td><td>Matcher&lt;T&gt;  Matcher</td></tr>
+<tr><td colspan="4" class="doc" id="findAll0"><pre>Matches if the node or any descendant matches.
+
+Generates results for each match.
+
+For example, in:
+  class A { class B {}; class C {}; };
+The matcher:
+  recordDecl(hasName("::A"), findAll(recordDecl(isDefinition()).bind("m")))
+will generate results for A, B and C.
+
+Usable as: Any Matcher
+</pre></td></tr>
+
+
 <tr><td>Matcher&lt<a href="http://clang.llvm.org/doxygen/classclang_1_1TypeLoc.html">TypeLoc</a>&gt;</td><td class="name" onclick="toggle('loc0')"><a name="loc0Anchor">loc</a></td><td>Matcher&lt<a href="http://clang.llvm.org/doxygen/classclang_1_1QualType.html">QualType</a>&gt;  InnerMatcher</td></tr>
 <tr><td colspan="4" class="doc" id="loc0"><pre>Matches TypeLocs for which the given inner
 QualType-matcher matches.
diff --git a/clang/docs/tools/dump_ast_matchers.py b/clang/docs/tools/dump_ast_matchers.py
index e72426eafbf..6a8687715f6 100644
--- a/clang/docs/tools/dump_ast_matchers.py
+++ b/clang/docs/tools/dump_ast_matchers.py
@@ -239,6 +239,15 @@ def act_on_decl(declaration, comment, allowed_types):
       add_matcher('*', name, 'Matcher<*>', comment)
       return
 
+    # Parse Variadic operator matchers.
+    m = re.match(
+        r"""^.*VariadicOperatorMatcherFunc\s*([a-zA-Z]*)\s*=\s*{.*};$""",
+        declaration, flags=re.X)
+    if m:
+      name = m.groups()[0]
+      add_matcher('*', name, 'Matcher<*>, ..., Matcher<*>', comment)
+      return
+
 
     # Parse free standing matcher functions, like:
     #   Matcher<ResultType> Name(Matcher<ArgumentType> InnerMatcher) {
@@ -309,7 +318,7 @@ for line in open(MATCHERS_FILE).read().splitlines():
     declaration += ' ' + line
     if ((not line.strip()) or 
         line.rstrip()[-1] == ';' or
-        line.rstrip()[-1] == '{'):
+        (line.rstrip()[-1] == '{' and line.rstrip()[-3:] != '= {')):
       if line.strip() and line.rstrip()[-1] == '{':
         body = True
       else:
diff --git a/clang/include/clang/ASTMatchers/ASTMatchers.h b/clang/include/clang/ASTMatchers/ASTMatchers.h
index 6cf47d6c0ff..cad9c404b46 100644
--- a/clang/include/clang/ASTMatchers/ASTMatchers.h
+++ b/clang/include/clang/ASTMatchers/ASTMatchers.h
@@ -1297,93 +1297,23 @@ const internal::VariadicAllOfMatcher<TypeLoc> typeLoc;
 /// \c b.
 ///
 /// Usable as: Any Matcher
-template <typename M1, typename M2>
-internal::PolymorphicMatcherWithParam2<internal::EachOfMatcher, M1, M2>
-eachOf(const M1 &P1, const M2 &P2) {
-  return internal::PolymorphicMatcherWithParam2<internal::EachOfMatcher, M1,
-                                                M2>(P1, P2);
-}
-
-/// \brief Various overloads for the anyOf matcher.
-/// @{
+const internal::VariadicOperatorMatcherFunc eachOf = {
+  internal::EachOfVariadicOperator
+};
 
 /// \brief Matches if any of the given matchers matches.
 ///
 /// Usable as: Any Matcher
-template<typename M1, typename M2>
-internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M1, M2>
-anyOf(const M1 &P1, const M2 &P2) {
-  return internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher,
-                                                M1, M2 >(P1, P2);
-}
-template<typename M1, typename M2, typename M3>
-internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M2, M3> >
-anyOf(const M1 &P1, const M2 &P2, const M3 &P3) {
-  return anyOf(P1, anyOf(P2, P3));
-}
-template<typename M1, typename M2, typename M3, typename M4>
-internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M2,
-        internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher,
-                                               M3, M4> > >
-anyOf(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4) {
-  return anyOf(P1, anyOf(P2, anyOf(P3, P4)));
-}
-template<typename M1, typename M2, typename M3, typename M4, typename M5>
-internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M2,
-        internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher, M3,
-            internal::PolymorphicMatcherWithParam2<internal::AnyOfMatcher,
-                                                   M4, M5> > > >
-anyOf(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4, const M5 &P5) {
-  return anyOf(P1, anyOf(P2, anyOf(P3, anyOf(P4, P5))));
-}
-
-/// @}
-
-/// \brief Various overloads for the allOf matcher.
-/// @{
+const internal::VariadicOperatorMatcherFunc anyOf = {
+  internal::AnyOfVariadicOperator
+};
 
 /// \brief Matches if all given matchers match.
 ///
 /// Usable as: Any Matcher
-template <typename M1, typename M2>
-internal::PolymorphicMatcherWithParam2<internal::AllOfMatcher, M1, M2>
-allOf(const M1 &P1, const M2 &P2) {
-  return internal::PolymorphicMatcherWithParam2<internal::AllOfMatcher, M1, M2>(
-      P1, P2);
-}
-template <typename M1, typename M2, typename M3>
-internal::PolymorphicMatcherWithParam2<
-    internal::AllOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<internal::AllOfMatcher, M2, M3> >
-allOf(const M1 &P1, const M2 &P2, const M3 &P3) {
-  return allOf(P1, allOf(P2, P3));
-}
-template <typename M1, typename M2, typename M3, typename M4>
-internal::PolymorphicMatcherWithParam2<
-    internal::AllOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<
-        internal::AllOfMatcher, M2, internal::PolymorphicMatcherWithParam2<
-                                        internal::AllOfMatcher, M3, M4> > >
-allOf(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4) {
-  return allOf(P1, allOf(P2, P3, P4));
-}
-template <typename M1, typename M2, typename M3, typename M4, typename M5>
-internal::PolymorphicMatcherWithParam2<
-    internal::AllOfMatcher, M1,
-    internal::PolymorphicMatcherWithParam2<
-        internal::AllOfMatcher, M2,
-        internal::PolymorphicMatcherWithParam2<
-            internal::AllOfMatcher, M3,
-            internal::PolymorphicMatcherWithParam2<internal::AllOfMatcher, M4,
-                                                   M5> > > >
-allOf(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4, const M5 &P5) {
-  return allOf(P1, allOf(P2, P3, P4, P5));
-}
-
-/// @}
+const internal::VariadicOperatorMatcherFunc allOf = {
+  internal::AllOfVariadicOperator
+};
 
 /// \brief Matches sizeof (C99), alignof (C++11) and vec_step (OpenCL)
 ///
@@ -1678,11 +1608,7 @@ forEachDescendant = {};
 ///
 /// Usable as: Any Matcher
 template <typename T>
-internal::PolymorphicMatcherWithParam2<
-    internal::EachOfMatcher, internal::Matcher<T>,
-    internal::ArgumentAdaptingMatcherFunc<
-        internal::ForEachDescendantMatcher>::Adaptor<T> >
-findAll(const internal::Matcher<T> &Matcher) {
+internal::Matcher<T> findAll(const internal::Matcher<T> &Matcher) {
   return eachOf(Matcher, forEachDescendant(Matcher));
 }
 
diff --git a/clang/include/clang/ASTMatchers/ASTMatchersInternal.h b/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
index b3eea639156..bb1793b7276 100644
--- a/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
+++ b/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -1080,115 +1080,161 @@ private:
   const Matcher<T> InnerMatcher;
 };
 
-/// \brief Matches nodes of type T for which both provided matchers match.
-///
-/// Type arguments MatcherT1 and MatcherT2 are required by
-/// PolymorphicMatcherWithParam2 but not actually used. They will
-/// always be instantiated with types convertible to Matcher<T>.
-template <typename T, typename MatcherT1, typename MatcherT2>
-class AllOfMatcher : public MatcherInterface<T> {
+/// \brief VariadicOperatorMatcher related types.
+/// @{
+
+/// \brief Function signature for any variadic operator. It takes the inner
+///   matchers as an array of DynTypedMatcher.
+typedef bool (*VariadicOperatorFunction)(
+    const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
+    BoundNodesTreeBuilder *Builder,
+    ArrayRef<const DynTypedMatcher *> InnerMatchers);
+
+/// \brief \c MatcherInterface<T> implementation for an variadic operator.
+template <typename T>
+class VariadicOperatorMatcherInterface : public MatcherInterface<T> {
 public:
-  AllOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
-      : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {}
+  VariadicOperatorMatcherInterface(VariadicOperatorFunction Func,
+                                   ArrayRef<const Matcher<T> *> InputMatchers)
+      : Func(Func) {
+    for (size_t i = 0, e = InputMatchers.size(); i != e; ++i) {
+      InnerMatchers.push_back(new Matcher<T>(*InputMatchers[i]));
+    }
+  }
 
-  virtual bool matches(const T &Node,
-                       ASTMatchFinder *Finder,
+  ~VariadicOperatorMatcherInterface() {
+    llvm::DeleteContainerPointers(InnerMatchers);
+  }
+
+  virtual bool matches(const T &Node, ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder) const {
-    // allOf leads to one matcher for each alternative in the first
-    // matcher combined with each alternative in the second matcher.
-    // Thus, we can reuse the same Builder.
-    return InnerMatcher1.matches(Node, Finder, Builder) &&
-           InnerMatcher2.matches(Node, Finder, Builder);
+    return Func(ast_type_traits::DynTypedNode::create(Node), Finder, Builder,
+                InnerMatchers);
   }
 
 private:
-  const Matcher<T> InnerMatcher1;
-  const Matcher<T> InnerMatcher2;
+  const VariadicOperatorFunction Func;
+  std::vector<const DynTypedMatcher *> InnerMatchers;
 };
 
-/// \brief Matches nodes of type T for which at least one of the two provided
-/// matchers matches.
+/// \brief "No argument" placeholder to use as template paratemers.
+struct VariadicOperatorNoArg {};
+
+/// \brief Polymorphic matcher object that uses a \c VariadicOperatorFunction
+///   operator.
 ///
-/// Type arguments MatcherT1 and MatcherT2 are
-/// required by PolymorphicMatcherWithParam2 but not actually
-/// used. They will always be instantiated with types convertible to
-/// Matcher<T>.
-template <typename T, typename MatcherT1, typename MatcherT2>
-class EachOfMatcher : public MatcherInterface<T> {
+/// Input matchers can have any type (including other polymorphic matcher
+/// types), and the actual Matcher<T> is generated on demand with an implicit
+/// coversion operator.
+template <typename P1, typename P2,
+          typename P3 = VariadicOperatorNoArg,
+          typename P4 = VariadicOperatorNoArg,
+          typename P5 = VariadicOperatorNoArg>
+class VariadicOperatorMatcher {
 public:
-  EachOfMatcher(const Matcher<T> &InnerMatcher1,
-                const Matcher<T> &InnerMatcher2)
-      : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {
+  VariadicOperatorMatcher(VariadicOperatorFunction Func, const P1 &Param1,
+                          const P2 &Param2,
+                          const P3 &Param3 = VariadicOperatorNoArg(),
+                          const P4 &Param4 = VariadicOperatorNoArg(),
+                          const P5 &Param5 = VariadicOperatorNoArg())
+      : Func(Func), Param1(Param1), Param2(Param2), Param3(Param3),
+        Param4(Param4), Param5(Param5) {}
+
+  template <typename T> operator Matcher<T>() const {
+    Matcher<T> *Array[5];
+    size_t Size = 0;
+
+    addMatcher<T>(Param1, Array, Size);
+    addMatcher<T>(Param2, Array, Size);
+    addMatcher<T>(Param3, Array, Size);
+    addMatcher<T>(Param4, Array, Size);
+    addMatcher<T>(Param5, Array, Size);
+    Matcher<T> Result(new VariadicOperatorMatcherInterface<T>(
+        Func, ArrayRef<const Matcher<T> *>(Array, Size)));
+    for (size_t i = 0, e = Size; i != e; ++i) delete Array[i];
+    return Result;
   }
 
-  virtual bool matches(const T &Node, ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    BoundNodesTreeBuilder Result;
-    BoundNodesTreeBuilder Builder1(*Builder);
-    bool Matched1 = InnerMatcher1.matches(Node, Finder, &Builder1);
-    if (Matched1)
-      Result.addMatch(Builder1);
-
-    BoundNodesTreeBuilder Builder2(*Builder);
-    bool Matched2 = InnerMatcher2.matches(Node, Finder, &Builder2);
-    if (Matched2)
-      Result.addMatch(Builder2);
-
-    *Builder = Result;
-    return Matched1 || Matched2;
+private:
+  template <typename T>
+  static void addMatcher(const Matcher<T> &M, Matcher<T> **Array,
+                         size_t &Size) {
+    Array[Size++] = new Matcher<T>(M);
   }
 
-private:
-  const Matcher<T> InnerMatcher1;
-  const Matcher<T> InnerMatcher2;
+  /// \brief Overload to ignore \c VariadicOperatorNoArg arguments.
+  template <typename T>
+  static void addMatcher(VariadicOperatorNoArg, Matcher<T> **Array,
+                         size_t &Size) {}
+
+  const VariadicOperatorFunction Func;
+  const P1 Param1;
+  const P2 Param2;
+  const P3 Param3;
+  const P4 Param4;
+  const P5 Param5;
 };
 
-/// \brief Matches nodes of type T for which at least one of the two provided
-/// matchers matches.
+/// \brief Overloaded function object to generate VariadicOperatorMatcher
+///   objects from arbitrary matchers.
 ///
-/// Type arguments MatcherT1 and MatcherT2 are
-/// required by PolymorphicMatcherWithParam2 but not actually
-/// used. They will always be instantiated with types convertible to
-/// Matcher<T>.
-template <typename T, typename MatcherT1, typename MatcherT2>
-class AnyOfMatcher : public MatcherInterface<T> {
-public:
-  AnyOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
-      : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {}
+/// It supports 2-5 argument overloaded operator(). More can be added if needed.
+struct VariadicOperatorMatcherFunc {
+  VariadicOperatorFunction Func;
 
-  virtual bool matches(const T &Node,
-                       ASTMatchFinder *Finder,
-                       BoundNodesTreeBuilder *Builder) const {
-    BoundNodesTreeBuilder Result = *Builder;
-    if (InnerMatcher1.matches(Node, Finder, &Result)) {
-      *Builder = Result;
-      return true;
-    }
-    Result = *Builder;
-    if (InnerMatcher2.matches(Node, Finder, &Result)) {
-      *Builder = Result;
-      return true;
-    }
-    return false;
+  template <typename M1, typename M2>
+  VariadicOperatorMatcher<M1, M2> operator()(const M1 &P1, const M2 &P2) const {
+    return VariadicOperatorMatcher<M1, M2>(Func, P1, P2);
+  }
+  template <typename M1, typename M2, typename M3>
+  VariadicOperatorMatcher<M1, M2, M3> operator()(const M1 &P1, const M2 &P2,
+                                                 const M3 &P3) const {
+    return VariadicOperatorMatcher<M1, M2, M3>(Func, P1, P2, P3);
+  }
+  template <typename M1, typename M2, typename M3, typename M4>
+  VariadicOperatorMatcher<M1, M2, M3, M4>
+  operator()(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4) const {
+    return VariadicOperatorMatcher<M1, M2, M3, M4>(Func, P1, P2, P3, P4);
+  }
+  template <typename M1, typename M2, typename M3, typename M4, typename M5>
+  VariadicOperatorMatcher<M1, M2, M3, M4, M5>
+  operator()(const M1 &P1, const M2 &P2, const M3 &P3, const M4 &P4,
+             const M5 &P5) const {
+    return VariadicOperatorMatcher<M1, M2, M3, M4, M5>(Func, P1, P2, P3, P4,
+                                                       P5);
   }
-
-private:
-  const Matcher<T> InnerMatcher1;
-  const Matcher<T> InnerMatcher2;
 };
 
+/// @}
+
+/// \brief Matches nodes for which all provided matchers match.
+bool
+AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                      ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
+                      ArrayRef<const DynTypedMatcher *> InnerMatchers);
+
+/// \brief Matches nodes for which at least one of the provided matchers
+/// matches, but doesn't stop at the first match.
+bool
+EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
+                       ArrayRef<const DynTypedMatcher *> InnerMatchers);
+
+/// \brief Matches nodes for which at least one of the provided matchers
+/// matches.
+bool
+AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                      ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
+                      ArrayRef<const DynTypedMatcher *> InnerMatchers);
+
 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
 template<typename T>
 BindableMatcher<T> makeAllOfComposite(
     ArrayRef<const Matcher<T> *> InnerMatchers) {
   if (InnerMatchers.empty())
     return BindableMatcher<T>(new TrueMatcher<T>);
-  MatcherInterface<T> *InnerMatcher = new TrueMatcher<T>;
-  for (int i = InnerMatchers.size() - 1; i >= 0; --i) {
-    InnerMatcher = new AllOfMatcher<T, Matcher<T>, Matcher<T> >(
-      *InnerMatchers[i], makeMatcher(InnerMatcher));
-  }
-  return BindableMatcher<T>(InnerMatcher);
+  return BindableMatcher<T>(new VariadicOperatorMatcherInterface<T>(
+      AllOfVariadicOperator, InnerMatchers));
 }
 
 /// \brief Creates a Matcher<T> that matches if
diff --git a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
index 757d20675ba..e7465167da1 100644
--- a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
+++ b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
@@ -36,6 +36,51 @@ DynTypedMatcher::~DynTypedMatcher() {}
 
 DynTypedMatcher *DynTypedMatcher::tryBind(StringRef ID) const { return NULL; }
 
+bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                           ASTMatchFinder *Finder,
+                           BoundNodesTreeBuilder *Builder,
+                           ArrayRef<const DynTypedMatcher *> InnerMatchers) {
+  // allOf leads to one matcher for each alternative in the first
+  // matcher combined with each alternative in the second matcher.
+  // Thus, we can reuse the same Builder.
+  for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
+    if (!InnerMatchers[i]->matches(DynNode, Finder, Builder))
+      return false;
+  }
+  return true;
+}
+
+bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                            ASTMatchFinder *Finder,
+                            BoundNodesTreeBuilder *Builder,
+                            ArrayRef<const DynTypedMatcher *> InnerMatchers) {
+  BoundNodesTreeBuilder Result;
+  bool Matched = false;
+  for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
+    BoundNodesTreeBuilder BuilderInner(*Builder);
+    if (InnerMatchers[i]->matches(DynNode, Finder, &BuilderInner)) {
+      Matched = true;
+      Result.addMatch(BuilderInner);
+    }
+  }
+  *Builder = Result;
+  return Matched;
+}
+
+bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
+                           ASTMatchFinder *Finder,
+                           BoundNodesTreeBuilder *Builder,
+                           ArrayRef<const DynTypedMatcher *> InnerMatchers) {
+  for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
+    BoundNodesTreeBuilder Result = *Builder;
+    if (InnerMatchers[i]->matches(DynNode, Finder, &Result)) {
+      *Builder = Result;
+      return true;
+    }
+  }
+  return false;
+}
+
 } // end namespace internal
 } // end namespace ast_matchers
 } // end namespace clang