1 files changed, 219 insertions, 70 deletions

diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp
index 23708e2ff0c7..fa7968a805c4 100644
--- a/lib/ASTMatchers/ASTMatchFinder.cpp
+++ b/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -20,7 +20,11 @@
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/Timer.h"
 #include <deque>
+#include <memory>
 #include <set>
 
 namespace clang {
@@ -53,7 +57,7 @@ static const unsigned MaxMemoizationEntries = 10000;
 // FIXME: Benchmark whether memoization of non-pointer typed nodes
 // provides enough benefit for the additional amount of code.
 struct MatchKey {
-  uint64_t MatcherID;
+  DynTypedMatcher::MatcherIDType MatcherID;
   ast_type_traits::DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
 
@@ -292,28 +296,33 @@ private:
 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
                         public ASTMatchFinder {
 public:
-  MatchASTVisitor(
-      std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *
-          MatcherCallbackPairs)
-      : MatcherCallbackPairs(MatcherCallbackPairs), ActiveASTContext(nullptr) {}
+  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
+                  const MatchFinder::MatchFinderOptions &Options)
+      : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
+
+  ~MatchASTVisitor() {
+    if (Options.CheckProfiling) {
+      Options.CheckProfiling->Records = std::move(TimeByBucket);
+    }
+  }
 
   void onStartOfTranslationUnit() {
-    for (std::vector<std::pair<internal::DynTypedMatcher,
-                               MatchCallback *> >::const_iterator
-             I = MatcherCallbackPairs->begin(),
-             E = MatcherCallbackPairs->end();
-         I != E; ++I) {
-      I->second->onStartOfTranslationUnit();
+    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+    TimeBucketRegion Timer;
+    for (MatchCallback *MC : Matchers->AllCallbacks) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MC->getID()]);
+      MC->onStartOfTranslationUnit();
     }
   }
 
   void onEndOfTranslationUnit() {
-    for (std::vector<std::pair<internal::DynTypedMatcher,
-                               MatchCallback *> >::const_iterator
-             I = MatcherCallbackPairs->begin(),
-             E = MatcherCallbackPairs->end();
-         I != E; ++I) {
-      I->second->onEndOfTranslationUnit();
+    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+    TimeBucketRegion Timer;
+    for (MatchCallback *MC : Matchers->AllCallbacks) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MC->getID()]);
+      MC->onEndOfTranslationUnit();
     }
   }
 
@@ -372,7 +381,7 @@ public:
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   TraversalKind Traversal, BindKind Bind) {
     // For AST-nodes that don't have an identity, we can't memoize.
-    if (!Node.getMemoizationData())
+    if (!Node.getMemoizationData() || !Builder->isComparable())
       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
                                 Bind);
 
@@ -392,9 +401,12 @@ public:
     Result.Nodes = *Builder;
     Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
                                               MaxDepth, Traversal, Bind);
-    ResultCache[Key] = Result;
-    *Builder = Result.Nodes;
-    return Result.ResultOfMatch;
+
+    MemoizedMatchResult &CachedResult = ResultCache[Key];
+    CachedResult = std::move(Result);
+
+    *Builder = CachedResult.Nodes;
+    return CachedResult.ResultOfMatch;
   }
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
@@ -447,22 +459,27 @@ public:
 
   // Matches all registered matchers on the given node and calls the
   // result callback for every node that matches.
-  void match(const ast_type_traits::DynTypedNode& Node) {
-    for (std::vector<std::pair<internal::DynTypedMatcher,
-                               MatchCallback *> >::const_iterator
-             I = MatcherCallbackPairs->begin(),
-             E = MatcherCallbackPairs->end();
-         I != E; ++I) {
-      BoundNodesTreeBuilder Builder;
-      if (I->first.matches(Node, this, &Builder)) {
-        MatchVisitor Visitor(ActiveASTContext, I->second);
-        Builder.visitMatches(&Visitor);
-      }
+  void match(const ast_type_traits::DynTypedNode &Node) {
+    // FIXME: Improve this with a switch or a visitor pattern.
+    if (auto *N = Node.get<Decl>()) {
+      match(*N);
+    } else if (auto *N = Node.get<Stmt>()) {
+      match(*N);
+    } else if (auto *N = Node.get<Type>()) {
+      match(*N);
+    } else if (auto *N = Node.get<QualType>()) {
+      match(*N);
+    } else if (auto *N = Node.get<NestedNameSpecifier>()) {
+      match(*N);
+    } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
+      match(*N);
+    } else if (auto *N = Node.get<TypeLoc>()) {
+      match(*N);
     }
   }
 
   template <typename T> void match(const T &Node) {
-    match(ast_type_traits::DynTypedNode::create(Node));
+    matchDispatch(&Node);
   }
 
   // Implements ASTMatchFinder::getASTContext.
@@ -475,6 +492,116 @@ public:
   bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
 
 private:
+  class TimeBucketRegion {
+  public:
+    TimeBucketRegion() : Bucket(nullptr) {}
+    ~TimeBucketRegion() { setBucket(nullptr); }
+
+    /// \brief Start timing for \p NewBucket.
+    ///
+    /// If there was a bucket already set, it will finish the timing for that
+    /// other bucket.
+    /// \p NewBucket will be timed until the next call to \c setBucket() or
+    /// until the \c TimeBucketRegion is destroyed.
+    /// If \p NewBucket is the same as the currently timed bucket, this call
+    /// does nothing.
+    void setBucket(llvm::TimeRecord *NewBucket) {
+      if (Bucket != NewBucket) {
+        auto Now = llvm::TimeRecord::getCurrentTime(true);
+        if (Bucket)
+          *Bucket += Now;
+        if (NewBucket)
+          *NewBucket -= Now;
+        Bucket = NewBucket;
+      }
+    }
+
+  private:
+    llvm::TimeRecord *Bucket;
+  };
+
+  /// \brief Runs all the \p Matchers on \p Node.
+  ///
+  /// Used by \c matchDispatch() below.
+  template <typename T, typename MC>
+  void matchWithoutFilter(const T &Node, const MC &Matchers) {
+    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+    TimeBucketRegion Timer;
+    for (const auto &MP : Matchers) {
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+      BoundNodesTreeBuilder Builder;
+      if (MP.first.matches(Node, this, &Builder)) {
+        MatchVisitor Visitor(ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
+    auto Kind = DynNode.getNodeKind();
+    auto it = MatcherFiltersMap.find(Kind);
+    const auto &Filter =
+        it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
+
+    if (Filter.empty())
+      return;
+
+    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+    TimeBucketRegion Timer;
+    auto &Matchers = this->Matchers->DeclOrStmt;
+    for (unsigned short I : Filter) {
+      auto &MP = Matchers[I];
+      if (EnableCheckProfiling)
+        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+      BoundNodesTreeBuilder Builder;
+      if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
+        MatchVisitor Visitor(ActiveASTContext, MP.second);
+        Builder.visitMatches(&Visitor);
+      }
+    }
+  }
+
+  const std::vector<unsigned short> &
+  getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
+    auto &Filter = MatcherFiltersMap[Kind];
+    auto &Matchers = this->Matchers->DeclOrStmt;
+    assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
+    for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
+      if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
+        Filter.push_back(I);
+      }
+    }
+    return Filter;
+  }
+
+  /// @{
+  /// \brief Overloads to pair the different node types to their matchers.
+  void matchDispatch(const Decl *Node) {
+    return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
+  }
+  void matchDispatch(const Stmt *Node) {
+    return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
+  }
+
+  void matchDispatch(const Type *Node) {
+    matchWithoutFilter(QualType(Node, 0), Matchers->Type);
+  }
+  void matchDispatch(const TypeLoc *Node) {
+    matchWithoutFilter(*Node, Matchers->TypeLoc);
+  }
+  void matchDispatch(const QualType *Node) {
+    matchWithoutFilter(*Node, Matchers->Type);
+  }
+  void matchDispatch(const NestedNameSpecifier *Node) {
+    matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
+  }
+  void matchDispatch(const NestedNameSpecifierLoc *Node) {
+    matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
+  }
+  void matchDispatch(const void *) { /* Do nothing. */ }
+  /// @}
+
   // Returns whether an ancestor of \p Node matches \p Matcher.
   //
   // The order of matching ((which can lead to different nodes being bound in
@@ -497,11 +624,7 @@ private:
     assert(Node.getMemoizationData() &&
            "Invariant broken: only nodes that support memoization may be "
            "used in the parent map.");
-    ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
-    if (Parents.empty()) {
-      assert(false && "Found node that is not in the parent map.");
-      return false;
-    }
+
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
@@ -514,9 +637,13 @@ private:
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
+
     MemoizedMatchResult Result;
     Result.ResultOfMatch = false;
     Result.Nodes = *Builder;
+
+    const auto &Parents = ActiveASTContext->getParents(Node);
+    assert(!Parents.empty() && "Found node that is not in the parent map.");
     if (Parents.size() == 1) {
       // Only one parent - do recursive memoization.
       const ast_type_traits::DynTypedNode Parent = Parents[0];
@@ -543,25 +670,24 @@ private:
           break;
         }
         if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
-          ASTContext::ParentVector Ancestors =
-              ActiveASTContext->getParents(Queue.front());
-          for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(),
-                                                        E = Ancestors.end();
-               I != E; ++I) {
+          for (const auto &Parent :
+               ActiveASTContext->getParents(Queue.front())) {
             // Make sure we do not visit the same node twice.
             // Otherwise, we'll visit the common ancestors as often as there
             // are splits on the way down.
-            if (Visited.insert(I->getMemoizationData()).second)
-              Queue.push_back(*I);
+            if (Visited.insert(Parent.getMemoizationData()).second)
+              Queue.push_back(Parent);
           }
         }
         Queue.pop_front();
       }
     }
-    ResultCache[Key] = Result;
 
-    *Builder = Result.Nodes;
-    return Result.ResultOfMatch;
+    MemoizedMatchResult &CachedResult = ResultCache[Key];
+    CachedResult = std::move(Result);
+
+    *Builder = CachedResult.Nodes;
+    return CachedResult.ResultOfMatch;
   }
 
   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
@@ -588,22 +714,35 @@ private:
                             BoundNodesTreeBuilder *Builder) {
     const Type *const CanonicalType =
       ActiveASTContext->getCanonicalType(TypeNode);
-    const std::set<const TypedefNameDecl *> &Aliases =
-        TypeAliases[CanonicalType];
-    for (std::set<const TypedefNameDecl*>::const_iterator
-           It = Aliases.begin(), End = Aliases.end();
-         It != End; ++It) {
+    for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) {
       BoundNodesTreeBuilder Result(*Builder);
-      if (Matcher.matches(**It, this, &Result)) {
-        *Builder = Result;
+      if (Matcher.matches(*Alias, this, &Result)) {
+        *Builder = std::move(Result);
         return true;
       }
     }
     return false;
   }
 
-  std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *const
-  MatcherCallbackPairs;
+  /// \brief Bucket to record map.
+  ///
+  /// Used to get the appropriate bucket for each matcher.
+  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
+
+  const MatchFinder::MatchersByType *Matchers;
+
+  /// \brief Filtered list of matcher indices for each matcher kind.
+  ///
+  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
+  /// kind (and derived kinds) so it is a waste to try every matcher on every
+  /// node.
+  /// We precalculate a list of matchers that pass the toplevel restrict check.
+  /// This also allows us to skip the restrict check at matching time. See
+  /// use \c matchesNoKindCheck() above.
+  llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
+      MatcherFiltersMap;
+
+  const MatchFinder::MatchFinderOptions &Options;
   ASTContext *ActiveASTContext;
 
   // Maps a canonical type to its TypedefDecls.
@@ -680,7 +819,7 @@ bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
     }
     BoundNodesTreeBuilder Result(*Builder);
     if (Base.matches(*ClassDecl, this, &Result)) {
-      *Builder = Result;
+      *Builder = std::move(Result);
       return true;
     }
     if (classIsDerivedFrom(ClassDecl, Base, Builder))
@@ -731,7 +870,8 @@ bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
   match(NNS);
   // We only match the nested name specifier here (as opposed to traversing it)
   // because the traversal is already done in the parallel "Loc"-hierarchy.
-  match(*NNS.getNestedNameSpecifier());
+  if (NNS.hasQualifier())
+    match(*NNS.getNestedNameSpecifier());
   return
       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
 }
@@ -765,38 +905,45 @@ MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
 MatchFinder::MatchCallback::~MatchCallback() {}
 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
 
-MatchFinder::MatchFinder() : ParsingDone(nullptr) {}
+MatchFinder::MatchFinder(MatchFinderOptions Options)
+    : Options(std::move(Options)), ParsingDone(nullptr) {}
 
 MatchFinder::~MatchFinder() {}
 
 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.Type.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.NestedNameSpecifier.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.NestedNameSpecifierLoc.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
                              MatchCallback *Action) {
-  MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.TypeLoc.push_back(std::make_pair(NodeMatch, Action));
+  Matchers.AllCallbacks.push_back(Action);
 }
 
 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
@@ -823,19 +970,19 @@ bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
   return false;
 }
 
-ASTConsumer *MatchFinder::newASTConsumer() {
-  return new internal::MatchASTConsumer(this, ParsingDone);
+std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
+  return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
 }
 
 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
                         ASTContext &Context) {
-  internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
+  internal::MatchASTVisitor Visitor(&Matchers, Options);
   Visitor.set_active_ast_context(&Context);
   Visitor.match(Node);
 }
 
 void MatchFinder::matchAST(ASTContext &Context) {
-  internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
+  internal::MatchASTVisitor Visitor(&Matchers, Options);
   Visitor.set_active_ast_context(&Context);
   Visitor.onStartOfTranslationUnit();
   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
@@ -847,5 +994,7 @@ void MatchFinder::registerTestCallbackAfterParsing(
   ParsingDone = NewParsingDone;
 }
 
+StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
+
 } // end namespace ast_matchers
 } // end namespace clang