contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchFinder.cpp

   1 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  Implements an algorithm to efficiently search for matches on AST nodes.
  11 //  Uses memoization to support recursive matches like HasDescendant.
  12 //
  13 //  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
  14 //  calling the Matches(...) method of each matcher we are running on each
  15 //  AST node. The matcher can recurse via the ASTMatchFinder interface.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "clang/ASTMatchers/ASTMatchFinder.h"
  20 #include "clang/AST/ASTConsumer.h"
  21 #include "clang/AST/ASTContext.h"
  22 #include "clang/AST/RecursiveASTVisitor.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/StringMap.h"
  25 #include "llvm/Support/Timer.h"
  26 #include <deque>
  27 #include <memory>
  28 #include <set>
  29
  30 namespace clang {
  31 namespace ast_matchers {
  32 namespace internal {
  33 namespace {
  34
  35 typedef MatchFinder::MatchCallback MatchCallback;
  36
  37 // The maximum number of memoization entries to store.
  38 // 10k has been experimentally found to give a good trade-off
  39 // of performance vs. memory consumption by running matcher
  40 // that match on every statement over a very large codebase.
  41 //
  42 // FIXME: Do some performance optimization in general and
  43 // revisit this number; also, put up micro-benchmarks that we can
  44 // optimize this on.
  45 static const unsigned MaxMemoizationEntries = 10000;
  46
  47 // We use memoization to avoid running the same matcher on the same
  48 // AST node twice.  This struct is the key for looking up match
  49 // result.  It consists of an ID of the MatcherInterface (for
  50 // identifying the matcher), a pointer to the AST node and the
  51 // bound nodes before the matcher was executed.
  52 //
  53 // We currently only memoize on nodes whose pointers identify the
  54 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
  55 // For \c QualType and \c TypeLoc it is possible to implement
  56 // generation of keys for each type.
  57 // FIXME: Benchmark whether memoization of non-pointer typed nodes
  58 // provides enough benefit for the additional amount of code.
  59 struct MatchKey {
  60   DynTypedMatcher::MatcherIDType MatcherID;
  61   ast_type_traits::DynTypedNode Node;
  62   BoundNodesTreeBuilder BoundNodes;
  63
  64   bool operator<(const MatchKey &Other) const {
  65     return std::tie(MatcherID, Node, BoundNodes) <
  66            std::tie(Other.MatcherID, Other.Node, Other.BoundNodes);
  67   }
  68 };
  69
  70 // Used to store the result of a match and possibly bound nodes.
  71 struct MemoizedMatchResult {
  72   bool ResultOfMatch;
  73   BoundNodesTreeBuilder Nodes;
  74 };
  75
  76 // A RecursiveASTVisitor that traverses all children or all descendants of
  77 // a node.
  78 class MatchChildASTVisitor
  79     : public RecursiveASTVisitor<MatchChildASTVisitor> {
  80 public:
  81   typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
  82
  83   // Creates an AST visitor that matches 'matcher' on all children or
  84   // descendants of a traversed node. max_depth is the maximum depth
  85   // to traverse: use 1 for matching the children and INT_MAX for
  86   // matching the descendants.
  87   MatchChildASTVisitor(const DynTypedMatcher *Matcher,
  88                        ASTMatchFinder *Finder,
  89                        BoundNodesTreeBuilder *Builder,
  90                        int MaxDepth,
  91                        ASTMatchFinder::TraversalKind Traversal,
  92                        ASTMatchFinder::BindKind Bind)
  93       : Matcher(Matcher),
  94         Finder(Finder),
  95         Builder(Builder),
  96         CurrentDepth(0),
  97         MaxDepth(MaxDepth),
  98         Traversal(Traversal),
  99         Bind(Bind),
 100         Matches(false) {}
 101
 102   // Returns true if a match is found in the subtree rooted at the
 103   // given AST node. This is done via a set of mutually recursive
 104   // functions. Here's how the recursion is done (the  *wildcard can
 105   // actually be Decl, Stmt, or Type):
 106   //
 107   //   - Traverse(node) calls BaseTraverse(node) when it needs
 108   //     to visit the descendants of node.
 109   //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
 110   //     Traverse*(c) for each child c of 'node'.
 111   //   - Traverse*(c) in turn calls Traverse(c), completing the
 112   //     recursion.
 113   bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
 114     reset();
 115     if (const Decl *D = DynNode.get<Decl>())
 116       traverse(*D);
 117     else if (const Stmt *S = DynNode.get<Stmt>())
 118       traverse(*S);
 119     else if (const NestedNameSpecifier *NNS =
 120              DynNode.get<NestedNameSpecifier>())
 121       traverse(*NNS);
 122     else if (const NestedNameSpecifierLoc *NNSLoc =
 123              DynNode.get<NestedNameSpecifierLoc>())
 124       traverse(*NNSLoc);
 125     else if (const QualType *Q = DynNode.get<QualType>())
 126       traverse(*Q);
 127     else if (const TypeLoc *T = DynNode.get<TypeLoc>())
 128       traverse(*T);
 129     else if (const auto *C = DynNode.get<CXXCtorInitializer>())
 130       traverse(*C);
 131     // FIXME: Add other base types after adding tests.
 132
 133     // It's OK to always overwrite the bound nodes, as if there was
 134     // no match in this recursive branch, the result set is empty
 135     // anyway.
 136     *Builder = ResultBindings;
 137
 138     return Matches;
 139   }
 140
 141   // The following are overriding methods from the base visitor class.
 142   // They are public only to allow CRTP to work. They are *not *part
 143   // of the public API of this class.
 144   bool TraverseDecl(Decl *DeclNode) {
 145     ScopedIncrement ScopedDepth(&CurrentDepth);
 146     return (DeclNode == nullptr) || traverse(*DeclNode);
 147   }
 148   bool TraverseStmt(Stmt *StmtNode) {
 149     ScopedIncrement ScopedDepth(&CurrentDepth);
 150     const Stmt *StmtToTraverse = StmtNode;
 151     if (Traversal ==
 152         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
 153       const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
 154       if (ExprNode) {
 155         StmtToTraverse = ExprNode->IgnoreParenImpCasts();
 156       }
 157     }
 158     return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse);
 159   }
 160   // We assume that the QualType and the contained type are on the same
 161   // hierarchy level. Thus, we try to match either of them.
 162   bool TraverseType(QualType TypeNode) {
 163     if (TypeNode.isNull())
 164       return true;
 165     ScopedIncrement ScopedDepth(&CurrentDepth);
 166     // Match the Type.
 167     if (!match(*TypeNode))
 168       return false;
 169     // The QualType is matched inside traverse.
 170     return traverse(TypeNode);
 171   }
 172   // We assume that the TypeLoc, contained QualType and contained Type all are
 173   // on the same hierarchy level. Thus, we try to match all of them.
 174   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
 175     if (TypeLocNode.isNull())
 176       return true;
 177     ScopedIncrement ScopedDepth(&CurrentDepth);
 178     // Match the Type.
 179     if (!match(*TypeLocNode.getType()))
 180       return false;
 181     // Match the QualType.
 182     if (!match(TypeLocNode.getType()))
 183       return false;
 184     // The TypeLoc is matched inside traverse.
 185     return traverse(TypeLocNode);
 186   }
 187   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
 188     ScopedIncrement ScopedDepth(&CurrentDepth);
 189     return (NNS == nullptr) || traverse(*NNS);
 190   }
 191   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
 192     if (!NNS)
 193       return true;
 194     ScopedIncrement ScopedDepth(&CurrentDepth);
 195     if (!match(*NNS.getNestedNameSpecifier()))
 196       return false;
 197     return traverse(NNS);
 198   }
 199   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
 200     if (!CtorInit)
 201       return true;
 202     ScopedIncrement ScopedDepth(&CurrentDepth);
 203     return traverse(*CtorInit);
 204   }
 205
 206   bool shouldVisitTemplateInstantiations() const { return true; }
 207   bool shouldVisitImplicitCode() const { return true; }
 208
 209 private:
 210   // Used for updating the depth during traversal.
 211   struct ScopedIncrement {
 212     explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
 213     ~ScopedIncrement() { --(*Depth); }
 214
 215    private:
 216     int *Depth;
 217   };
 218
 219   // Resets the state of this object.
 220   void reset() {
 221     Matches = false;
 222     CurrentDepth = 0;
 223   }
 224
 225   // Forwards the call to the corresponding Traverse*() method in the
 226   // base visitor class.
 227   bool baseTraverse(const Decl &DeclNode) {
 228     return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
 229   }
 230   bool baseTraverse(const Stmt &StmtNode) {
 231     return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
 232   }
 233   bool baseTraverse(QualType TypeNode) {
 234     return VisitorBase::TraverseType(TypeNode);
 235   }
 236   bool baseTraverse(TypeLoc TypeLocNode) {
 237     return VisitorBase::TraverseTypeLoc(TypeLocNode);
 238   }
 239   bool baseTraverse(const NestedNameSpecifier &NNS) {
 240     return VisitorBase::TraverseNestedNameSpecifier(
 241         const_cast<NestedNameSpecifier*>(&NNS));
 242   }
 243   bool baseTraverse(NestedNameSpecifierLoc NNS) {
 244     return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
 245   }
 246   bool baseTraverse(const CXXCtorInitializer &CtorInit) {
 247     return VisitorBase::TraverseConstructorInitializer(
 248         const_cast<CXXCtorInitializer *>(&CtorInit));
 249   }
 250
 251   // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
 252   //   0 < CurrentDepth <= MaxDepth.
 253   //
 254   // Returns 'true' if traversal should continue after this function
 255   // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
 256   template <typename T>
 257   bool match(const T &Node) {
 258     if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
 259       return true;
 260     }
 261     if (Bind != ASTMatchFinder::BK_All) {
 262       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 263       if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
 264                            &RecursiveBuilder)) {
 265         Matches = true;
 266         ResultBindings.addMatch(RecursiveBuilder);
 267         return false; // Abort as soon as a match is found.
 268       }
 269     } else {
 270       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 271       if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
 272                            &RecursiveBuilder)) {
 273         // After the first match the matcher succeeds.
 274         Matches = true;
 275         ResultBindings.addMatch(RecursiveBuilder);
 276       }
 277     }
 278     return true;
 279   }
 280
 281   // Traverses the subtree rooted at 'Node'; returns true if the
 282   // traversal should continue after this function returns.
 283   template <typename T>
 284   bool traverse(const T &Node) {
 285     static_assert(IsBaseType<T>::value,
 286                   "traverse can only be instantiated with base type");
 287     if (!match(Node))
 288       return false;
 289     return baseTraverse(Node);
 290   }
 291
 292   const DynTypedMatcher *const Matcher;
 293   ASTMatchFinder *const Finder;
 294   BoundNodesTreeBuilder *const Builder;
 295   BoundNodesTreeBuilder ResultBindings;
 296   int CurrentDepth;
 297   const int MaxDepth;
 298   const ASTMatchFinder::TraversalKind Traversal;
 299   const ASTMatchFinder::BindKind Bind;
 300   bool Matches;
 301 };
 302
 303 // Controls the outermost traversal of the AST and allows to match multiple
 304 // matchers.
 305 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
 306                         public ASTMatchFinder {
 307 public:
 308   MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
 309                   const MatchFinder::MatchFinderOptions &Options)
 310       : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
 311
 312   ~MatchASTVisitor() override {
 313     if (Options.CheckProfiling) {
 314       Options.CheckProfiling->Records = std::move(TimeByBucket);
 315     }
 316   }
 317
 318   void onStartOfTranslationUnit() {
 319     const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
 320     TimeBucketRegion Timer;
 321     for (MatchCallback *MC : Matchers->AllCallbacks) {
 322       if (EnableCheckProfiling)
 323         Timer.setBucket(&TimeByBucket[MC->getID()]);
 324       MC->onStartOfTranslationUnit();
 325     }
 326   }
 327
 328   void onEndOfTranslationUnit() {
 329     const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
 330     TimeBucketRegion Timer;
 331     for (MatchCallback *MC : Matchers->AllCallbacks) {
 332       if (EnableCheckProfiling)
 333         Timer.setBucket(&TimeByBucket[MC->getID()]);
 334       MC->onEndOfTranslationUnit();
 335     }
 336   }
 337
 338   void set_active_ast_context(ASTContext *NewActiveASTContext) {
 339     ActiveASTContext = NewActiveASTContext;
 340   }
 341
 342   // The following Visit*() and Traverse*() functions "override"
 343   // methods in RecursiveASTVisitor.
 344
 345   bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
 346     // When we see 'typedef A B', we add name 'B' to the set of names
 347     // A's canonical type maps to.  This is necessary for implementing
 348     // isDerivedFrom(x) properly, where x can be the name of the base
 349     // class or any of its aliases.
 350     //
 351     // In general, the is-alias-of (as defined by typedefs) relation
 352     // is tree-shaped, as you can typedef a type more than once.  For
 353     // example,
 354     //
 355     //   typedef A B;
 356     //   typedef A C;
 357     //   typedef C D;
 358     //   typedef C E;
 359     //
 360     // gives you
 361     //
 362     //   A
 363     //   |- B
 364     //   `- C
 365     //      |- D
 366     //      `- E
 367     //
 368     // It is wrong to assume that the relation is a chain.  A correct
 369     // implementation of isDerivedFrom() needs to recognize that B and
 370     // E are aliases, even though neither is a typedef of the other.
 371     // Therefore, we cannot simply walk through one typedef chain to
 372     // find out whether the type name matches.
 373     const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
 374     const Type *CanonicalType =  // root of the typedef tree
 375         ActiveASTContext->getCanonicalType(TypeNode);
 376     TypeAliases[CanonicalType].insert(DeclNode);
 377     return true;
 378   }
 379
 380   bool TraverseDecl(Decl *DeclNode);
 381   bool TraverseStmt(Stmt *StmtNode);
 382   bool TraverseType(QualType TypeNode);
 383   bool TraverseTypeLoc(TypeLoc TypeNode);
 384   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
 385   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
 386   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
 387
 388   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 389   bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
 390                                   const DynTypedMatcher &Matcher,
 391                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
 392                                   TraversalKind Traversal, BindKind Bind) {
 393     // For AST-nodes that don't have an identity, we can't memoize.
 394     if (!Node.getMemoizationData() || !Builder->isComparable())
 395       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
 396                                 Bind);
 397
 398     MatchKey Key;
 399     Key.MatcherID = Matcher.getID();
 400     Key.Node = Node;
 401     // Note that we key on the bindings *before* the match.
 402     Key.BoundNodes = *Builder;
 403
 404     MemoizationMap::iterator I = ResultCache.find(Key);
 405     if (I != ResultCache.end()) {
 406       *Builder = I->second.Nodes;
 407       return I->second.ResultOfMatch;
 408     }
 409
 410     MemoizedMatchResult Result;
 411     Result.Nodes = *Builder;
 412     Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
 413                                               MaxDepth, Traversal, Bind);
 414
 415     MemoizedMatchResult &CachedResult = ResultCache[Key];
 416     CachedResult = std::move(Result);
 417
 418     *Builder = CachedResult.Nodes;
 419     return CachedResult.ResultOfMatch;
 420   }
 421
 422   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 423   bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
 424                           const DynTypedMatcher &Matcher,
 425                           BoundNodesTreeBuilder *Builder, int MaxDepth,
 426                           TraversalKind Traversal, BindKind Bind) {
 427     MatchChildASTVisitor Visitor(
 428       &Matcher, this, Builder, MaxDepth, Traversal, Bind);
 429     return Visitor.findMatch(Node);
 430   }
 431
 432   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
 433                           const Matcher<NamedDecl> &Base,
 434                           BoundNodesTreeBuilder *Builder) override;
 435
 436   // Implements ASTMatchFinder::matchesChildOf.
 437   bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
 438                       const DynTypedMatcher &Matcher,
 439                       BoundNodesTreeBuilder *Builder,
 440                       TraversalKind Traversal,
 441                       BindKind Bind) override {
 442     if (ResultCache.size() > MaxMemoizationEntries)
 443       ResultCache.clear();
 444     return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
 445                                       Bind);
 446   }
 447   // Implements ASTMatchFinder::matchesDescendantOf.
 448   bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
 449                            const DynTypedMatcher &Matcher,
 450                            BoundNodesTreeBuilder *Builder,
 451                            BindKind Bind) override {
 452     if (ResultCache.size() > MaxMemoizationEntries)
 453       ResultCache.clear();
 454     return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
 455                                       TK_AsIs, Bind);
 456   }
 457   // Implements ASTMatchFinder::matchesAncestorOf.
 458   bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
 459                          const DynTypedMatcher &Matcher,
 460                          BoundNodesTreeBuilder *Builder,
 461                          AncestorMatchMode MatchMode) override {
 462     // Reset the cache outside of the recursive call to make sure we
 463     // don't invalidate any iterators.
 464     if (ResultCache.size() > MaxMemoizationEntries)
 465       ResultCache.clear();
 466     return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
 467                                                 MatchMode);
 468   }
 469
 470   // Matches all registered matchers on the given node and calls the
 471   // result callback for every node that matches.
 472   void match(const ast_type_traits::DynTypedNode &Node) {
 473     // FIXME: Improve this with a switch or a visitor pattern.
 474     if (auto *N = Node.get<Decl>()) {
 475       match(*N);
 476     } else if (auto *N = Node.get<Stmt>()) {
 477       match(*N);
 478     } else if (auto *N = Node.get<Type>()) {
 479       match(*N);
 480     } else if (auto *N = Node.get<QualType>()) {
 481       match(*N);
 482     } else if (auto *N = Node.get<NestedNameSpecifier>()) {
 483       match(*N);
 484     } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
 485       match(*N);
 486     } else if (auto *N = Node.get<TypeLoc>()) {
 487       match(*N);
 488     } else if (auto *N = Node.get<CXXCtorInitializer>()) {
 489       match(*N);
 490     }
 491   }
 492
 493   template <typename T> void match(const T &Node) {
 494     matchDispatch(&Node);
 495   }
 496
 497   // Implements ASTMatchFinder::getASTContext.
 498   ASTContext &getASTContext() const override { return *ActiveASTContext; }
 499
 500   bool shouldVisitTemplateInstantiations() const { return true; }
 501   bool shouldVisitImplicitCode() const { return true; }
 502
 503 private:
 504   class TimeBucketRegion {
 505   public:
 506     TimeBucketRegion() : Bucket(nullptr) {}
 507     ~TimeBucketRegion() { setBucket(nullptr); }
 508
 509     /// \brief Start timing for \p NewBucket.
 510     ///
 511     /// If there was a bucket already set, it will finish the timing for that
 512     /// other bucket.
 513     /// \p NewBucket will be timed until the next call to \c setBucket() or
 514     /// until the \c TimeBucketRegion is destroyed.
 515     /// If \p NewBucket is the same as the currently timed bucket, this call
 516     /// does nothing.
 517     void setBucket(llvm::TimeRecord *NewBucket) {
 518       if (Bucket != NewBucket) {
 519         auto Now = llvm::TimeRecord::getCurrentTime(true);
 520         if (Bucket)
 521           *Bucket += Now;
 522         if (NewBucket)
 523           *NewBucket -= Now;
 524         Bucket = NewBucket;
 525       }
 526     }
 527
 528   private:
 529     llvm::TimeRecord *Bucket;
 530   };
 531
 532   /// \brief Runs all the \p Matchers on \p Node.
 533   ///
 534   /// Used by \c matchDispatch() below.
 535   template <typename T, typename MC>
 536   void matchWithoutFilter(const T &Node, const MC &Matchers) {
 537     const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
 538     TimeBucketRegion Timer;
 539     for (const auto &MP : Matchers) {
 540       if (EnableCheckProfiling)
 541         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
 542       BoundNodesTreeBuilder Builder;
 543       if (MP.first.matches(Node, this, &Builder)) {
 544         MatchVisitor Visitor(ActiveASTContext, MP.second);
 545         Builder.visitMatches(&Visitor);
 546       }
 547     }
 548   }
 549
 550   void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
 551     auto Kind = DynNode.getNodeKind();
 552     auto it = MatcherFiltersMap.find(Kind);
 553     const auto &Filter =
 554         it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
 555
 556     if (Filter.empty())
 557       return;
 558
 559     const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
 560     TimeBucketRegion Timer;
 561     auto &Matchers = this->Matchers->DeclOrStmt;
 562     for (unsigned short I : Filter) {
 563       auto &MP = Matchers[I];
 564       if (EnableCheckProfiling)
 565         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
 566       BoundNodesTreeBuilder Builder;
 567       if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
 568         MatchVisitor Visitor(ActiveASTContext, MP.second);
 569         Builder.visitMatches(&Visitor);
 570       }
 571     }
 572   }
 573
 574   const std::vector<unsigned short> &
 575   getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
 576     auto &Filter = MatcherFiltersMap[Kind];
 577     auto &Matchers = this->Matchers->DeclOrStmt;
 578     assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
 579     for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
 580       if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
 581         Filter.push_back(I);
 582       }
 583     }
 584     return Filter;
 585   }
 586
 587   /// @{
 588   /// \brief Overloads to pair the different node types to their matchers.
 589   void matchDispatch(const Decl *Node) {
 590     return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
 591   }
 592   void matchDispatch(const Stmt *Node) {
 593     return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
 594   }
 595
 596   void matchDispatch(const Type *Node) {
 597     matchWithoutFilter(QualType(Node, 0), Matchers->Type);
 598   }
 599   void matchDispatch(const TypeLoc *Node) {
 600     matchWithoutFilter(*Node, Matchers->TypeLoc);
 601   }
 602   void matchDispatch(const QualType *Node) {
 603     matchWithoutFilter(*Node, Matchers->Type);
 604   }
 605   void matchDispatch(const NestedNameSpecifier *Node) {
 606     matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
 607   }
 608   void matchDispatch(const NestedNameSpecifierLoc *Node) {
 609     matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
 610   }
 611   void matchDispatch(const CXXCtorInitializer *Node) {
 612     matchWithoutFilter(*Node, Matchers->CtorInit);
 613   }
 614   void matchDispatch(const void *) { /* Do nothing. */ }
 615   /// @}
 616
 617   // Returns whether an ancestor of \p Node matches \p Matcher.
 618   //
 619   // The order of matching ((which can lead to different nodes being bound in
 620   // case there are multiple matches) is breadth first search.
 621   //
 622   // To allow memoization in the very common case of having deeply nested
 623   // expressions inside a template function, we first walk up the AST, memoizing
 624   // the result of the match along the way, as long as there is only a single
 625   // parent.
 626   //
 627   // Once there are multiple parents, the breadth first search order does not
 628   // allow simple memoization on the ancestors. Thus, we only memoize as long
 629   // as there is a single parent.
 630   bool memoizedMatchesAncestorOfRecursively(
 631       const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
 632       BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
 633     if (Node.get<TranslationUnitDecl>() ==
 634         ActiveASTContext->getTranslationUnitDecl())
 635       return false;
 636
 637     // For AST-nodes that don't have an identity, we can't memoize.
 638     if (!Builder->isComparable())
 639       return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
 640
 641     MatchKey Key;
 642     Key.MatcherID = Matcher.getID();
 643     Key.Node = Node;
 644     Key.BoundNodes = *Builder;
 645
 646     // Note that we cannot use insert and reuse the iterator, as recursive
 647     // calls to match might invalidate the result cache iterators.
 648     MemoizationMap::iterator I = ResultCache.find(Key);
 649     if (I != ResultCache.end()) {
 650       *Builder = I->second.Nodes;
 651       return I->second.ResultOfMatch;
 652     }
 653
 654     MemoizedMatchResult Result;
 655     Result.Nodes = *Builder;
 656     Result.ResultOfMatch =
 657         matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode);
 658
 659     MemoizedMatchResult &CachedResult = ResultCache[Key];
 660     CachedResult = std::move(Result);
 661
 662     *Builder = CachedResult.Nodes;
 663     return CachedResult.ResultOfMatch;
 664   }
 665
 666   bool matchesAncestorOfRecursively(const ast_type_traits::DynTypedNode &Node,
 667                                     const DynTypedMatcher &Matcher,
 668                                     BoundNodesTreeBuilder *Builder,
 669                                     AncestorMatchMode MatchMode) {
 670     const auto &Parents = ActiveASTContext->getParents(Node);
 671     assert(!Parents.empty() && "Found node that is not in the parent map.");
 672     if (Parents.size() == 1) {
 673       // Only one parent - do recursive memoization.
 674       const ast_type_traits::DynTypedNode Parent = Parents[0];
 675       BoundNodesTreeBuilder BuilderCopy = *Builder;
 676       if (Matcher.matches(Parent, this, &BuilderCopy)) {
 677         *Builder = std::move(BuilderCopy);
 678         return true;
 679       }
 680       if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
 681         return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder,
 682                                                     MatchMode);
 683         // Once we get back from the recursive call, the result will be the
 684         // same as the parent's result.
 685       }
 686     } else {
 687       // Multiple parents - BFS over the rest of the nodes.
 688       llvm::DenseSet<const void *> Visited;
 689       std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
 690                                                       Parents.end());
 691       while (!Queue.empty()) {
 692         BoundNodesTreeBuilder BuilderCopy = *Builder;
 693         if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
 694           *Builder = std::move(BuilderCopy);
 695           return true;
 696         }
 697         if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
 698           for (const auto &Parent :
 699                ActiveASTContext->getParents(Queue.front())) {
 700             // Make sure we do not visit the same node twice.
 701             // Otherwise, we'll visit the common ancestors as often as there
 702             // are splits on the way down.
 703             if (Visited.insert(Parent.getMemoizationData()).second)
 704               Queue.push_back(Parent);
 705           }
 706         }
 707         Queue.pop_front();
 708       }
 709     }
 710     return false;
 711   }
 712
 713   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
 714   // the aggregated bound nodes for each match.
 715   class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
 716   public:
 717     MatchVisitor(ASTContext* Context,
 718                  MatchFinder::MatchCallback* Callback)
 719       : Context(Context),
 720         Callback(Callback) {}
 721
 722     void visitMatch(const BoundNodes& BoundNodesView) override {
 723       Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
 724     }
 725
 726   private:
 727     ASTContext* Context;
 728     MatchFinder::MatchCallback* Callback;
 729   };
 730
 731   // Returns true if 'TypeNode' has an alias that matches the given matcher.
 732   bool typeHasMatchingAlias(const Type *TypeNode,
 733                             const Matcher<NamedDecl> &Matcher,
 734                             BoundNodesTreeBuilder *Builder) {
 735     const Type *const CanonicalType =
 736       ActiveASTContext->getCanonicalType(TypeNode);
 737     auto Aliases = TypeAliases.find(CanonicalType);
 738     if (Aliases == TypeAliases.end())
 739       return false;
 740     for (const TypedefNameDecl *Alias : Aliases->second) {
 741       BoundNodesTreeBuilder Result(*Builder);
 742       if (Matcher.matches(*Alias, this, &Result)) {
 743         *Builder = std::move(Result);
 744         return true;
 745       }
 746     }
 747     return false;
 748   }
 749
 750   /// \brief Bucket to record map.
 751   ///
 752   /// Used to get the appropriate bucket for each matcher.
 753   llvm::StringMap<llvm::TimeRecord> TimeByBucket;
 754
 755   const MatchFinder::MatchersByType *Matchers;
 756
 757   /// \brief Filtered list of matcher indices for each matcher kind.
 758   ///
 759   /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
 760   /// kind (and derived kinds) so it is a waste to try every matcher on every
 761   /// node.
 762   /// We precalculate a list of matchers that pass the toplevel restrict check.
 763   /// This also allows us to skip the restrict check at matching time. See
 764   /// use \c matchesNoKindCheck() above.
 765   llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
 766       MatcherFiltersMap;
 767
 768   const MatchFinder::MatchFinderOptions &Options;
 769   ASTContext *ActiveASTContext;
 770
 771   // Maps a canonical type to its TypedefDecls.
 772   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
 773
 774   // Maps (matcher, node) -> the match result for memoization.
 775   typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
 776   MemoizationMap ResultCache;
 777 };
 778
 779 static CXXRecordDecl *
 780 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
 781   if (auto *RD = TypeNode->getAsCXXRecordDecl())
 782     return RD;
 783
 784   // Find the innermost TemplateSpecializationType that isn't an alias template.
 785   auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
 786   while (TemplateType && TemplateType->isTypeAlias())
 787     TemplateType =
 788         TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
 789
 790   // If this is the name of a (dependent) template specialization, use the
 791   // definition of the template, even though it might be specialized later.
 792   if (TemplateType)
 793     if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
 794           TemplateType->getTemplateName().getAsTemplateDecl()))
 795       return ClassTemplate->getTemplatedDecl();
 796
 797   return nullptr;
 798 }
 799
 800 // Returns true if the given class is directly or indirectly derived
 801 // from a base type with the given name.  A class is not considered to be
 802 // derived from itself.
 803 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
 804                                          const Matcher<NamedDecl> &Base,
 805                                          BoundNodesTreeBuilder *Builder) {
 806   if (!Declaration->hasDefinition())
 807     return false;
 808   for (const auto &It : Declaration->bases()) {
 809     const Type *TypeNode = It.getType().getTypePtr();
 810
 811     if (typeHasMatchingAlias(TypeNode, Base, Builder))
 812       return true;
 813
 814     // FIXME: Going to the primary template here isn't really correct, but
 815     // unfortunately we accept a Decl matcher for the base class not a Type
 816     // matcher, so it's the best thing we can do with our current interface.
 817     CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
 818     if (!ClassDecl)
 819       continue;
 820     if (ClassDecl == Declaration) {
 821       // This can happen for recursive template definitions; if the
 822       // current declaration did not match, we can safely return false.
 823       return false;
 824     }
 825     BoundNodesTreeBuilder Result(*Builder);
 826     if (Base.matches(*ClassDecl, this, &Result)) {
 827       *Builder = std::move(Result);
 828       return true;
 829     }
 830     if (classIsDerivedFrom(ClassDecl, Base, Builder))
 831       return true;
 832   }
 833   return false;
 834 }
 835
 836 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
 837   if (!DeclNode) {
 838     return true;
 839   }
 840   match(*DeclNode);
 841   return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
 842 }
 843
 844 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
 845   if (!StmtNode) {
 846     return true;
 847   }
 848   match(*StmtNode);
 849   return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
 850 }
 851
 852 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
 853   match(TypeNode);
 854   return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
 855 }
 856
 857 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
 858   // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
 859   // We still want to find those types via matchers, so we match them here. Note
 860   // that the TypeLocs are structurally a shadow-hierarchy to the expressed
 861   // type, so we visit all involved parts of a compound type when matching on
 862   // each TypeLoc.
 863   match(TypeLocNode);
 864   match(TypeLocNode.getType());
 865   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
 866 }
 867
 868 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
 869   match(*NNS);
 870   return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
 871 }
 872
 873 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
 874     NestedNameSpecifierLoc NNS) {
 875   if (!NNS)
 876     return true;
 877
 878   match(NNS);
 879
 880   // We only match the nested name specifier here (as opposed to traversing it)
 881   // because the traversal is already done in the parallel "Loc"-hierarchy.
 882   if (NNS.hasQualifier())
 883     match(*NNS.getNestedNameSpecifier());
 884   return
 885       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
 886 }
 887
 888 bool MatchASTVisitor::TraverseConstructorInitializer(
 889     CXXCtorInitializer *CtorInit) {
 890   if (!CtorInit)
 891     return true;
 892
 893   match(*CtorInit);
 894
 895   return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
 896       CtorInit);
 897 }
 898
 899 class MatchASTConsumer : public ASTConsumer {
 900 public:
 901   MatchASTConsumer(MatchFinder *Finder,
 902                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
 903       : Finder(Finder), ParsingDone(ParsingDone) {}
 904
 905 private:
 906   void HandleTranslationUnit(ASTContext &Context) override {
 907     if (ParsingDone != nullptr) {
 908       ParsingDone->run();
 909     }
 910     Finder->matchAST(Context);
 911   }
 912
 913   MatchFinder *Finder;
 914   MatchFinder::ParsingDoneTestCallback *ParsingDone;
 915 };
 916
 917 } // end namespace
 918 } // end namespace internal
 919
 920 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
 921                                       ASTContext *Context)
 922   : Nodes(Nodes), Context(Context),
 923     SourceManager(&Context->getSourceManager()) {}
 924
 925 MatchFinder::MatchCallback::~MatchCallback() {}
 926 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
 927
 928 MatchFinder::MatchFinder(MatchFinderOptions Options)
 929     : Options(std::move(Options)), ParsingDone(nullptr) {}
 930
 931 MatchFinder::~MatchFinder() {}
 932
 933 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
 934                              MatchCallback *Action) {
 935   Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
 936   Matchers.AllCallbacks.insert(Action);
 937 }
 938
 939 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
 940                              MatchCallback *Action) {
 941   Matchers.Type.emplace_back(NodeMatch, Action);
 942   Matchers.AllCallbacks.insert(Action);
 943 }
 944
 945 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
 946                              MatchCallback *Action) {
 947   Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
 948   Matchers.AllCallbacks.insert(Action);
 949 }
 950
 951 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
 952                              MatchCallback *Action) {
 953   Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
 954   Matchers.AllCallbacks.insert(Action);
 955 }
 956
 957 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
 958                              MatchCallback *Action) {
 959   Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
 960   Matchers.AllCallbacks.insert(Action);
 961 }
 962
 963 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
 964                              MatchCallback *Action) {
 965   Matchers.TypeLoc.emplace_back(NodeMatch, Action);
 966   Matchers.AllCallbacks.insert(Action);
 967 }
 968
 969 void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
 970                              MatchCallback *Action) {
 971   Matchers.CtorInit.emplace_back(NodeMatch, Action);
 972   Matchers.AllCallbacks.insert(Action);
 973 }
 974
 975 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
 976                                     MatchCallback *Action) {
 977   if (NodeMatch.canConvertTo<Decl>()) {
 978     addMatcher(NodeMatch.convertTo<Decl>(), Action);
 979     return true;
 980   } else if (NodeMatch.canConvertTo<QualType>()) {
 981     addMatcher(NodeMatch.convertTo<QualType>(), Action);
 982     return true;
 983   } else if (NodeMatch.canConvertTo<Stmt>()) {
 984     addMatcher(NodeMatch.convertTo<Stmt>(), Action);
 985     return true;
 986   } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
 987     addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
 988     return true;
 989   } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
 990     addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
 991     return true;
 992   } else if (NodeMatch.canConvertTo<TypeLoc>()) {
 993     addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
 994     return true;
 995   } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
 996     addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
 997     return true;
 998   }
 999   return false;
1000 }
1001
1002 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1003   return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1004 }
1005
1006 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
1007                         ASTContext &Context) {
1008   internal::MatchASTVisitor Visitor(&Matchers, Options);
1009   Visitor.set_active_ast_context(&Context);
1010   Visitor.match(Node);
1011 }
1012
1013 void MatchFinder::matchAST(ASTContext &Context) {
1014   internal::MatchASTVisitor Visitor(&Matchers, Options);
1015   Visitor.set_active_ast_context(&Context);
1016   Visitor.onStartOfTranslationUnit();
1017   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
1018   Visitor.onEndOfTranslationUnit();
1019 }
1020
1021 void MatchFinder::registerTestCallbackAfterParsing(
1022     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1023   ParsingDone = NewParsingDone;
1024 }
1025
1026 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1027
1028 } // end namespace ast_matchers
1029 } // end namespace clang