Special case 0 and 1 matcher in makeAllOfComposite().

[sbenza]

Summary

Remove unnecessary wrapping for the 0 and 1 matcher cases of
makeAllOfComposite(). We don't need a variadic wrapper for those cases.
Refactor TrueMatcher to take advandage of the new conversions between
DynTypedMatcher and Matcher<T>. Also, make it a singleton.
This change improves our clang-tidy related benchmarks by ~12%.

[klimek]

lg

include/clang/ASTMatchers/ASTMatchersInternal.h

450

What is this needed for? I'd prefer if we could get rid of it, but if not, it should have a comment explaining it (so we can take it out if we don't need it any more).

[sbenza]

Added comment

include/clang/ASTMatchers/ASTMatchersInternal.h

450

Matcher(DynTypedMatcher) is private because it is essentially "unsafe". You can easily create a matcher that matches nothing.
It is only called by explicit conversions like Matcher<T>::dynCastTo<U> and DynTypedMatcher::unconditionalConvertTo<T>. The friendship is for those functions.

[klimek]

lg

[sbenza]

Closed by commit rL219431 (authored by @sbenza).

include/clang/ASTMatchers/ASTMatchers.h

 /// Example: \c DeclarationMatcher(anything()) matches all declarations, e.g.,
 /// \code
 /// "int* p" and "void f()" in
 ///   int* p;
 ///   void f();
 /// \endcode
 ///
 /// Usable as: Any Matcher
-inline internal::PolymorphicMatcherWithParam0<internal::TrueMatcher>
-anything() {
-  return internal::PolymorphicMatcherWithParam0<internal::TrueMatcher>();
-}
+inline internal::TrueMatcher anything() { return internal::TrueMatcher(); }
 
 /// \brief Matches declarations.
 ///
 /// Examples matches \c X, \c C, and the friend declaration inside \c C;
 /// \code
 ///   void X();
 ///   class C {
 ///     friend X;

include/clang/ASTMatchers/ASTMatchersInternal.h

public:
   /// \brief Construct from a variadic function.
   typedef bool (*VariadicOperatorFunction)(
       const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
       BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
   static DynTypedMatcher
   constructVariadic(VariadicOperatorFunction Func,
                     std::vector<DynTypedMatcher> InnerMatchers);
 
+  /// \brief Get a "true" matcher for \p NodeKind.
+  ///
+  /// It only checks that the node is of the right kind.
+  static DynTypedMatcher trueMatcher(ast_type_traits::ASTNodeKind NodeKind);
+
   void setAllowBind(bool AB) { AllowBind = AB; }
 
   /// \brief Return a matcher that points to the same implementation, but
   ///   restricts the node types for \p Kind.
   DynTypedMatcher dynCastTo(const ast_type_traits::ASTNodeKind Kind) const;
 
   /// \brief Returns true if the matcher matches the given \c DynNode.
   bool matches(const ast_type_traits::DynTypedNode &DynNode,
public:
 
   /// \brief Same as \c convertTo(), but does not check that the underlying
   ///   matcher can handle a value of T.
   ///
   /// If it is not compatible, then this matcher will never match anything.
   template <typename T> Matcher<T> unconditionalConvertTo() const;
 
 private:
+ DynTypedMatcher(ast_type_traits::ASTNodeKind SupportedKind,
+                 ast_type_traits::ASTNodeKind RestrictKind,
+                 IntrusiveRefCntPtr<DynMatcherInterface> Implementation)
+     : AllowBind(false),
+       SupportedKind(SupportedKind),
+       RestrictKind(RestrictKind),
+       Implementation(std::move(Implementation)) {}
+
   bool AllowBind;
   ast_type_traits::ASTNodeKind SupportedKind;
   /// \brief A potentially stricter node kind.
   ///
   /// It allows to perform implicit and dynamic cast of matchers without
   /// needing to change \c Implementation.
   ast_type_traits::ASTNodeKind RestrictKind;
   IntrusiveRefCntPtr<DynMatcherInterface> Implementation;
bool matches(const QualType &Node, ASTMatchFinder *Finder,
       return InnerMatcher.matches(*Node, Finder, Builder);
     }
    private:
     const Matcher<TypeT> InnerMatcher;
   };
 
 private:
   template <typename U> friend class Matcher;
+  friend class DynTypedMatcher;
 
   static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) {
     return Other.dynCastTo(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
   }
 
   explicit Matcher(const DynTypedMatcher &Implementation)
       : Implementation(restrictMatcher(Implementation)) {
     assert(this->Implementation.getSupportedKind()
private:
   const P1 Param1;
   const P2 Param2;
 };
 
 /// \brief Matches any instance of the given NodeType.
 ///
 /// This is useful when a matcher syntactically requires a child matcher,
 /// but the context doesn't care. See for example: anything().
-///
-/// FIXME: Alternatively we could also create a IsAMatcher or something
-/// that checks that a dyn_cast is possible. This is purely needed for the
-/// difference between calling for example:
-///   record()
-/// and
-///   record(SomeMatcher)
-/// In the second case we need the correct type we were dyn_cast'ed to in order
-/// to get the right type for the inner matcher. In the first case we don't need
-/// that, but we use the type conversion anyway and insert a TrueMatcher.
-template <typename T>
-class TrueMatcher : public SingleNodeMatcherInterface<T>  {
+class TrueMatcher {
  public:
-  bool matchesNode(const T &Node) const override {
-    return true;
-  }
-};
+  typedef AllNodeBaseTypes ReturnTypes;
 
-/// \brief Matcher<T> that wraps an inner Matcher<T> and binds the matched node
-/// to an ID if the inner matcher matches on the node.
   template <typename T>
-class IdMatcher : public MatcherInterface<T> {
-public:
-  /// \brief Creates an IdMatcher that binds to 'ID' if 'InnerMatcher' matches
-  /// the node.
-  IdMatcher(StringRef ID, const Matcher<T> &InnerMatcher)
-      : ID(ID), InnerMatcher(InnerMatcher) {}
-
-  bool matches(const T &Node, ASTMatchFinder *Finder,
-               BoundNodesTreeBuilder *Builder) const override {
-    bool Result = InnerMatcher.matches(Node, Finder, Builder);
-    if (Result) {
-      Builder->setBinding(ID, ast_type_traits::DynTypedNode::create(Node));
-    }
-    return Result;
+  operator Matcher<T>() const {
+    return DynTypedMatcher::trueMatcher(
+               ast_type_traits::ASTNodeKind::getFromNodeKind<T>())
+        .template unconditionalConvertTo<T>();
   }
-
-private:
-  const std::string ID;
-  const Matcher<T> InnerMatcher;
 };
 
 /// \brief A Matcher that allows binding the node it matches to an id.
 ///
 /// BindableMatcher provides a \a bind() method that allows binding the
 /// matched node to an id if the match was successful.
 template <typename T>
 class BindableMatcher : public Matcher<T> {
 public:
   explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {}
   explicit BindableMatcher(MatcherInterface<T> *Implementation)
     : Matcher<T>(Implementation) {}
 
   /// \brief Returns a matcher that will bind the matched node on a match.
   ///
   /// The returned matcher is equivalent to this matcher, but will
   /// bind the matched node on a match.
   Matcher<T> bind(StringRef ID) const {
-    // FIXME: Use DynTypedMatcher's IdMatcher instead. No need for a template
-    // version anymore.
-    return Matcher<T>(new IdMatcher<T>(ID, *this));
+    return DynTypedMatcher(*this)
+        .tryBind(ID)
+        ->template unconditionalConvertTo<T>();
   }
 
   /// \brief Same as Matcher<T>'s conversion operator, but enables binding on
   /// the returned matcher.
   operator DynTypedMatcher() const {
     DynTypedMatcher Result = static_cast<const Matcher<T>&>(*this);
     Result.setAllowBind(true);
     return Result;

 /// matches.
 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
                            ASTMatchFinder *Finder,
                            BoundNodesTreeBuilder *Builder,
                            ArrayRef<DynTypedMatcher> InnerMatchers);
 
 template <typename T>
 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const {
-  // FIXME: Remove this extra indirection and connect directly to Matcher<T>().
-  return Matcher<T>(new VariadicOperatorMatcherInterface<T>(
-      AllOfVariadicOperator, llvm::makeArrayRef(*this)));
+  return Matcher<T>(*this);
 }
 
 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
 template<typename T>
 BindableMatcher<T> makeAllOfComposite(
     ArrayRef<const Matcher<T> *> InnerMatchers) {
-  // FIXME: Optimize for the cases of size()==0 and size()==1
+  // For the size() == 0 case, we return a "true" matcher.
+  if (InnerMatchers.size() == 0) {
+    return BindableMatcher<T>(TrueMatcher());
+  }
+  // For the size() == 1 case, we simply return that one matcher.
+  // No need to wrap it in a variadic operation.
+  if (InnerMatchers.size() == 1) {
+    return BindableMatcher<T>(*InnerMatchers[0]);
+  }
+
   std::vector<DynTypedMatcher> DynMatchers;
   for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
     DynMatchers.push_back(*InnerMatchers[i]);
   }
   // FIXME: Use DynTypedMatcher::constructVariadic() instead.
   return BindableMatcher<T>(new VariadicOperatorMatcherInterface<T>(
       AllOfVariadicOperator, std::move(DynMatchers)));
 }

lib/ASTMatchers/ASTMatchersInternal.cpp

 //===--- ASTMatchersInternal.cpp - Structural query framework -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  Implements the base layer of the matcher framework.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/ASTMatchers/ASTMatchersInternal.h"
+#include "llvm/Support/ManagedStatic.h"
 
 namespace clang {
 namespace ast_matchers {
 namespace internal {
 
 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
   if (Bindings.empty())
     Bindings.push_back(BoundNodesMap());
bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
     return Result;
   }
 
  private:
   const std::string ID;
   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
 };
 
+/// \brief A matcher that always returns true.
+///
+/// We only ever need one instance of this matcher, so we create a global one
+/// and reuse it to reduce the overhead of the matcher and increase the chance
+/// of cache hits.
+struct TrueMatcherImpl {
+  TrueMatcherImpl() : Instance(new Impl) {}
+  const IntrusiveRefCntPtr<DynMatcherInterface> Instance;
+
+  class Impl : public DynMatcherInterface {
+   public:
+    bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
+                    BoundNodesTreeBuilder *) const override {
+      return true;
+    }
+  };
+};
+static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
+
 }  // namespace
 
 DynTypedMatcher DynTypedMatcher::constructVariadic(
     VariadicOperatorFunction Func, std::vector<DynTypedMatcher> InnerMatchers) {
   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
   DynTypedMatcher Result = InnerMatchers[0];
   // Use the least derived type as the restriction for the wrapper.
   // This allows mismatches to be resolved on the inner matchers.
   for (const DynTypedMatcher &M : InnerMatchers) {
     assert(Result.SupportedKind.isSame(M.SupportedKind) &&
            "SupportedKind must match!");
     Result.RestrictKind =
         ast_type_traits::ASTNodeKind::getMostDerivedCommonAncestor(
             Result.RestrictKind, M.RestrictKind);
   }
   Result.Implementation = new VariadicMatcher(Func, std::move(InnerMatchers));
   return Result;
 }
 
+DynTypedMatcher DynTypedMatcher::trueMatcher(
+    ast_type_traits::ASTNodeKind NodeKind) {
+  return DynTypedMatcher(NodeKind, NodeKind, TrueMatcherInstance->Instance);
+}
+
 DynTypedMatcher DynTypedMatcher::dynCastTo(
     const ast_type_traits::ASTNodeKind Kind) const {
   auto Copy = *this;
   Copy.SupportedKind = Kind;
   Copy.RestrictKind =
       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
   return Copy;
 }

unittests/ASTMatchers/Dynamic/ParserTest.cpp

 namespace dynamic {
 namespace {
 
 class MockSema : public Parser::Sema {
 public:
   virtual ~MockSema() {}
 
   uint64_t expectMatcher(StringRef MatcherName) {
-    ast_matchers::internal::Matcher<Stmt> M = stmt();
+    // Optimizations on the matcher framework make simple matchers like
+    // 'stmt()' to be all the same matcher.
+    // Use a more complex expression to prevent that.
+    ast_matchers::internal::Matcher<Stmt> M = stmt(stmt(), stmt());
     ExpectedMatchers.insert(std::make_pair(MatcherName, M));
     return M.getID().second;
   }
 
   void parse(StringRef Code) {
     Diagnostics Error;
     VariantValue Value;
     Parser::parseExpression(Code, this, &Value, &Error);