Refactor Matcher<T> and DynTypedMatcher to reduce overhead of casts.

Summary:
This change introduces DynMatcherInterface and changes the internal
representation of DynTypedMatcher and Matcher<T> to use a generic
interface instead.
It removes unnecessary indirections and virtual function calls when
converting matchers by implicit and dynamic casts.
DynTypedMatcher now remembers the stricter type in the chain of casts
and checks it before calling into DynMatcherInterface.
This change improves our clang-tidy related benchmark by ~14%.
Also, it opens the door for more optimizations of this kind that are
coming in future changes.

As a side effect of removing these template instantiations, it also
speeds up compilation of Dynamic/Registry.cpp by ~17% and reduces the number of
symbols generated by ~30%.

Reviewers: klimek

Subscribers: klimek, cfe-commits

Differential Revision: http://reviews.llvm.org/D5485

llvm-svn: 218616

1 files changed, 107 insertions, 2 deletions

diff --git a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
index b95004a6d43..36a77206fda 100644
--- a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
+++ b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp
@@ -26,6 +26,113 @@ void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
   }
 }
 
+namespace {
+
+class VariadicMatcher : public DynMatcherInterface {
+ public:
+  VariadicMatcher(VariadicOperatorFunction Func,
+                  std::vector<DynTypedMatcher> InnerMatchers)
+      : Func(Func), InnerMatchers(std::move(InnerMatchers)) {}
+
+  bool matches(const ast_type_traits::DynTypedNode &DynNode,
+               ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const override {
+    return Func(DynNode, Finder, Builder, InnerMatchers);
+  }
+
+ private:
+  VariadicOperatorFunction Func;
+  std::vector<DynTypedMatcher> InnerMatchers;
+};
+
+class IdDynMatcher : public DynMatcherInterface {
+ public:
+  IdDynMatcher(StringRef ID,
+               const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
+      : ID(ID), InnerMatcher(InnerMatcher) {}
+
+  bool matches(const ast_type_traits::DynTypedNode &DynNode,
+               ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const override {
+    bool Result = InnerMatcher->matches(DynNode, Finder, Builder);
+    if (Result) Builder->setBinding(ID, DynNode);
+    return Result;
+  }
+
+ private:
+  const std::string ID;
+  const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
+};
+
+/// \brief Return the most derived type between \p Kind1 and \p Kind2.
+///
+/// Return the null type if they are not related.
+ast_type_traits::ASTNodeKind getMostDerivedType(
+    const ast_type_traits::ASTNodeKind Kind1,
+    const ast_type_traits::ASTNodeKind Kind2) {
+  if (Kind1.isBaseOf(Kind2)) return Kind2;
+  if (Kind2.isBaseOf(Kind1)) return Kind1;
+  return ast_type_traits::ASTNodeKind();
+}
+
+/// \brief Return the least derived type between \p Kind1 and \p Kind2.
+///
+/// Return the null type if they are not related.
+static ast_type_traits::ASTNodeKind getLeastDerivedType(
+    const ast_type_traits::ASTNodeKind Kind1,
+    const ast_type_traits::ASTNodeKind Kind2) {
+  if (Kind1.isBaseOf(Kind2)) return Kind1;
+  if (Kind2.isBaseOf(Kind1)) return Kind2;
+  return ast_type_traits::ASTNodeKind();
+}
+
+}  // 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 =
+        getLeastDerivedType(Result.RestrictKind, M.RestrictKind);
+  }
+  Result.Implementation = new VariadicMatcher(Func, std::move(InnerMatchers));
+  return Result;
+}
+
+DynTypedMatcher DynTypedMatcher::dynCastTo(
+    const ast_type_traits::ASTNodeKind Kind) const {
+  auto Copy = *this;
+  Copy.SupportedKind = Kind;
+  Copy.RestrictKind = getMostDerivedType(Kind, RestrictKind);
+  return Copy;
+}
+
+bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode DynNode,
+                              ASTMatchFinder *Finder,
+                              BoundNodesTreeBuilder *Builder) const {
+  if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
+      Implementation->matches(DynNode, Finder, Builder)) {
+    return true;
+  }
+  // Delete all bindings when a matcher does not match.
+  // This prevents unexpected exposure of bound nodes in unmatches
+  // branches of the match tree.
+  Builder->removeBindings([](const BoundNodesMap &) { return true; });
+  return false;
+}
+
+llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
+  if (!AllowBind) return llvm::None;
+  auto Result = *this;
+  Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
+  return Result;
+}
+
 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
   const auto From = getSupportedKind();
   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
@@ -37,8 +144,6 @@ bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
   return From.isBaseOf(To);
 }
 
-DynTypedMatcher::MatcherStorage::~MatcherStorage() {}
-
 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
   for (unsigned i = 0, e = Other.Bindings.size(); i != e; ++i) {
     Bindings.push_back(Other.Bindings[i]);