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 <deque>
  24 #include <set>
  25
  26 namespace clang {
  27 namespace ast_matchers {
  28 namespace internal {
  29 namespace {
  30
  31 typedef MatchFinder::MatchCallback MatchCallback;
  32
  33 // The maximum number of memoization entries to store.
  34 // 10k has been experimentally found to give a good trade-off
  35 // of performance vs. memory consumption by running matcher
  36 // that match on every statement over a very large codebase.
  37 //
  38 // FIXME: Do some performance optimization in general and
  39 // revisit this number; also, put up micro-benchmarks that we can
  40 // optimize this on.
  41 static const unsigned MaxMemoizationEntries = 10000;
  42
  43 // We use memoization to avoid running the same matcher on the same
  44 // AST node twice.  This struct is the key for looking up match
  45 // result.  It consists of an ID of the MatcherInterface (for
  46 // identifying the matcher), a pointer to the AST node and the
  47 // bound nodes before the matcher was executed.
  48 //
  49 // We currently only memoize on nodes whose pointers identify the
  50 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
  51 // For \c QualType and \c TypeLoc it is possible to implement
  52 // generation of keys for each type.
  53 // FIXME: Benchmark whether memoization of non-pointer typed nodes
  54 // provides enough benefit for the additional amount of code.
  55 struct MatchKey {
  56   uint64_t MatcherID;
  57   ast_type_traits::DynTypedNode Node;
  58   BoundNodesTreeBuilder BoundNodes;
  59
  60   bool operator<(const MatchKey &Other) const {
  61     return std::tie(MatcherID, Node, BoundNodes) <
  62            std::tie(Other.MatcherID, Other.Node, Other.BoundNodes);
  63   }
  64 };
  65
  66 // Used to store the result of a match and possibly bound nodes.
  67 struct MemoizedMatchResult {
  68   bool ResultOfMatch;
  69   BoundNodesTreeBuilder Nodes;
  70 };
  71
  72 // A RecursiveASTVisitor that traverses all children or all descendants of
  73 // a node.
  74 class MatchChildASTVisitor
  75     : public RecursiveASTVisitor<MatchChildASTVisitor> {
  76 public:
  77   typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
  78
  79   // Creates an AST visitor that matches 'matcher' on all children or
  80   // descendants of a traversed node. max_depth is the maximum depth
  81   // to traverse: use 1 for matching the children and INT_MAX for
  82   // matching the descendants.
  83   MatchChildASTVisitor(const DynTypedMatcher *Matcher,
  84                        ASTMatchFinder *Finder,
  85                        BoundNodesTreeBuilder *Builder,
  86                        int MaxDepth,
  87                        ASTMatchFinder::TraversalKind Traversal,
  88                        ASTMatchFinder::BindKind Bind)
  89       : Matcher(Matcher),
  90         Finder(Finder),
  91         Builder(Builder),
  92         CurrentDepth(0),
  93         MaxDepth(MaxDepth),
  94         Traversal(Traversal),
  95         Bind(Bind),
  96         Matches(false) {}
  97
  98   // Returns true if a match is found in the subtree rooted at the
  99   // given AST node. This is done via a set of mutually recursive
 100   // functions. Here's how the recursion is done (the  *wildcard can
 101   // actually be Decl, Stmt, or Type):
 102   //
 103   //   - Traverse(node) calls BaseTraverse(node) when it needs
 104   //     to visit the descendants of node.
 105   //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
 106   //     Traverse*(c) for each child c of 'node'.
 107   //   - Traverse*(c) in turn calls Traverse(c), completing the
 108   //     recursion.
 109   bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
 110     reset();
 111     if (const Decl *D = DynNode.get<Decl>())
 112       traverse(*D);
 113     else if (const Stmt *S = DynNode.get<Stmt>())
 114       traverse(*S);
 115     else if (const NestedNameSpecifier *NNS =
 116              DynNode.get<NestedNameSpecifier>())
 117       traverse(*NNS);
 118     else if (const NestedNameSpecifierLoc *NNSLoc =
 119              DynNode.get<NestedNameSpecifierLoc>())
 120       traverse(*NNSLoc);
 121     else if (const QualType *Q = DynNode.get<QualType>())
 122       traverse(*Q);
 123     else if (const TypeLoc *T = DynNode.get<TypeLoc>())
 124       traverse(*T);
 125     // FIXME: Add other base types after adding tests.
 126
 127     // It's OK to always overwrite the bound nodes, as if there was
 128     // no match in this recursive branch, the result set is empty
 129     // anyway.
 130     *Builder = ResultBindings;
 131
 132     return Matches;
 133   }
 134
 135   // The following are overriding methods from the base visitor class.
 136   // They are public only to allow CRTP to work. They are *not *part
 137   // of the public API of this class.
 138   bool TraverseDecl(Decl *DeclNode) {
 139     ScopedIncrement ScopedDepth(&CurrentDepth);
 140     return (DeclNode == nullptr) || traverse(*DeclNode);
 141   }
 142   bool TraverseStmt(Stmt *StmtNode) {
 143     ScopedIncrement ScopedDepth(&CurrentDepth);
 144     const Stmt *StmtToTraverse = StmtNode;
 145     if (Traversal ==
 146         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
 147       const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
 148       if (ExprNode) {
 149         StmtToTraverse = ExprNode->IgnoreParenImpCasts();
 150       }
 151     }
 152     return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse);
 153   }
 154   // We assume that the QualType and the contained type are on the same
 155   // hierarchy level. Thus, we try to match either of them.
 156   bool TraverseType(QualType TypeNode) {
 157     if (TypeNode.isNull())
 158       return true;
 159     ScopedIncrement ScopedDepth(&CurrentDepth);
 160     // Match the Type.
 161     if (!match(*TypeNode))
 162       return false;
 163     // The QualType is matched inside traverse.
 164     return traverse(TypeNode);
 165   }
 166   // We assume that the TypeLoc, contained QualType and contained Type all are
 167   // on the same hierarchy level. Thus, we try to match all of them.
 168   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
 169     if (TypeLocNode.isNull())
 170       return true;
 171     ScopedIncrement ScopedDepth(&CurrentDepth);
 172     // Match the Type.
 173     if (!match(*TypeLocNode.getType()))
 174       return false;
 175     // Match the QualType.
 176     if (!match(TypeLocNode.getType()))
 177       return false;
 178     // The TypeLoc is matched inside traverse.
 179     return traverse(TypeLocNode);
 180   }
 181   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
 182     ScopedIncrement ScopedDepth(&CurrentDepth);
 183     return (NNS == nullptr) || traverse(*NNS);
 184   }
 185   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
 186     if (!NNS)
 187       return true;
 188     ScopedIncrement ScopedDepth(&CurrentDepth);
 189     if (!match(*NNS.getNestedNameSpecifier()))
 190       return false;
 191     return traverse(NNS);
 192   }
 193
 194   bool shouldVisitTemplateInstantiations() const { return true; }
 195   bool shouldVisitImplicitCode() const { return true; }
 196   // Disables data recursion. We intercept Traverse* methods in the RAV, which
 197   // are not triggered during data recursion.
 198   bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
 199
 200 private:
 201   // Used for updating the depth during traversal.
 202   struct ScopedIncrement {
 203     explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
 204     ~ScopedIncrement() { --(*Depth); }
 205
 206    private:
 207     int *Depth;
 208   };
 209
 210   // Resets the state of this object.
 211   void reset() {
 212     Matches = false;
 213     CurrentDepth = 0;
 214   }
 215
 216   // Forwards the call to the corresponding Traverse*() method in the
 217   // base visitor class.
 218   bool baseTraverse(const Decl &DeclNode) {
 219     return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
 220   }
 221   bool baseTraverse(const Stmt &StmtNode) {
 222     return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
 223   }
 224   bool baseTraverse(QualType TypeNode) {
 225     return VisitorBase::TraverseType(TypeNode);
 226   }
 227   bool baseTraverse(TypeLoc TypeLocNode) {
 228     return VisitorBase::TraverseTypeLoc(TypeLocNode);
 229   }
 230   bool baseTraverse(const NestedNameSpecifier &NNS) {
 231     return VisitorBase::TraverseNestedNameSpecifier(
 232         const_cast<NestedNameSpecifier*>(&NNS));
 233   }
 234   bool baseTraverse(NestedNameSpecifierLoc NNS) {
 235     return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
 236   }
 237
 238   // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
 239   //   0 < CurrentDepth <= MaxDepth.
 240   //
 241   // Returns 'true' if traversal should continue after this function
 242   // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
 243   template <typename T>
 244   bool match(const T &Node) {
 245     if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
 246       return true;
 247     }
 248     if (Bind != ASTMatchFinder::BK_All) {
 249       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 250       if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
 251                            &RecursiveBuilder)) {
 252         Matches = true;
 253         ResultBindings.addMatch(RecursiveBuilder);
 254         return false; // Abort as soon as a match is found.
 255       }
 256     } else {
 257       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 258       if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
 259                            &RecursiveBuilder)) {
 260         // After the first match the matcher succeeds.
 261         Matches = true;
 262         ResultBindings.addMatch(RecursiveBuilder);
 263       }
 264     }
 265     return true;
 266   }
 267
 268   // Traverses the subtree rooted at 'Node'; returns true if the
 269   // traversal should continue after this function returns.
 270   template <typename T>
 271   bool traverse(const T &Node) {
 272     static_assert(IsBaseType<T>::value,
 273                   "traverse can only be instantiated with base type");
 274     if (!match(Node))
 275       return false;
 276     return baseTraverse(Node);
 277   }
 278
 279   const DynTypedMatcher *const Matcher;
 280   ASTMatchFinder *const Finder;
 281   BoundNodesTreeBuilder *const Builder;
 282   BoundNodesTreeBuilder ResultBindings;
 283   int CurrentDepth;
 284   const int MaxDepth;
 285   const ASTMatchFinder::TraversalKind Traversal;
 286   const ASTMatchFinder::BindKind Bind;
 287   bool Matches;
 288 };
 289
 290 // Controls the outermost traversal of the AST and allows to match multiple
 291 // matchers.
 292 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
 293                         public ASTMatchFinder {
 294 public:
 295   MatchASTVisitor(
 296       std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *
 297           MatcherCallbackPairs)
 298       : MatcherCallbackPairs(MatcherCallbackPairs), ActiveASTContext(nullptr) {}
 299
 300   void onStartOfTranslationUnit() {
 301     for (std::vector<std::pair<internal::DynTypedMatcher,
 302                                MatchCallback *> >::const_iterator
 303              I = MatcherCallbackPairs->begin(),
 304              E = MatcherCallbackPairs->end();
 305          I != E; ++I) {
 306       I->second->onStartOfTranslationUnit();
 307     }
 308   }
 309
 310   void onEndOfTranslationUnit() {
 311     for (std::vector<std::pair<internal::DynTypedMatcher,
 312                                MatchCallback *> >::const_iterator
 313              I = MatcherCallbackPairs->begin(),
 314              E = MatcherCallbackPairs->end();
 315          I != E; ++I) {
 316       I->second->onEndOfTranslationUnit();
 317     }
 318   }
 319
 320   void set_active_ast_context(ASTContext *NewActiveASTContext) {
 321     ActiveASTContext = NewActiveASTContext;
 322   }
 323
 324   // The following Visit*() and Traverse*() functions "override"
 325   // methods in RecursiveASTVisitor.
 326
 327   bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
 328     // When we see 'typedef A B', we add name 'B' to the set of names
 329     // A's canonical type maps to.  This is necessary for implementing
 330     // isDerivedFrom(x) properly, where x can be the name of the base
 331     // class or any of its aliases.
 332     //
 333     // In general, the is-alias-of (as defined by typedefs) relation
 334     // is tree-shaped, as you can typedef a type more than once.  For
 335     // example,
 336     //
 337     //   typedef A B;
 338     //   typedef A C;
 339     //   typedef C D;
 340     //   typedef C E;
 341     //
 342     // gives you
 343     //
 344     //   A
 345     //   |- B
 346     //   `- C
 347     //      |- D
 348     //      `- E
 349     //
 350     // It is wrong to assume that the relation is a chain.  A correct
 351     // implementation of isDerivedFrom() needs to recognize that B and
 352     // E are aliases, even though neither is a typedef of the other.
 353     // Therefore, we cannot simply walk through one typedef chain to
 354     // find out whether the type name matches.
 355     const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
 356     const Type *CanonicalType =  // root of the typedef tree
 357         ActiveASTContext->getCanonicalType(TypeNode);
 358     TypeAliases[CanonicalType].insert(DeclNode);
 359     return true;
 360   }
 361
 362   bool TraverseDecl(Decl *DeclNode);
 363   bool TraverseStmt(Stmt *StmtNode);
 364   bool TraverseType(QualType TypeNode);
 365   bool TraverseTypeLoc(TypeLoc TypeNode);
 366   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
 367   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
 368
 369   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 370   bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
 371                                   const DynTypedMatcher &Matcher,
 372                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
 373                                   TraversalKind Traversal, BindKind Bind) {
 374     // For AST-nodes that don't have an identity, we can't memoize.
 375     if (!Node.getMemoizationData())
 376       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
 377                                 Bind);
 378
 379     MatchKey Key;
 380     Key.MatcherID = Matcher.getID();
 381     Key.Node = Node;
 382     // Note that we key on the bindings *before* the match.
 383     Key.BoundNodes = *Builder;
 384
 385     MemoizationMap::iterator I = ResultCache.find(Key);
 386     if (I != ResultCache.end()) {
 387       *Builder = I->second.Nodes;
 388       return I->second.ResultOfMatch;
 389     }
 390
 391     MemoizedMatchResult Result;
 392     Result.Nodes = *Builder;
 393     Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
 394                                               MaxDepth, Traversal, Bind);
 395     ResultCache[Key] = Result;
 396     *Builder = Result.Nodes;
 397     return Result.ResultOfMatch;
 398   }
 399
 400   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 401   bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
 402                           const DynTypedMatcher &Matcher,
 403                           BoundNodesTreeBuilder *Builder, int MaxDepth,
 404                           TraversalKind Traversal, BindKind Bind) {
 405     MatchChildASTVisitor Visitor(
 406       &Matcher, this, Builder, MaxDepth, Traversal, Bind);
 407     return Visitor.findMatch(Node);
 408   }
 409
 410   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
 411                           const Matcher<NamedDecl> &Base,
 412                           BoundNodesTreeBuilder *Builder) override;
 413
 414   // Implements ASTMatchFinder::matchesChildOf.
 415   bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
 416                       const DynTypedMatcher &Matcher,
 417                       BoundNodesTreeBuilder *Builder,
 418                       TraversalKind Traversal,
 419                       BindKind Bind) override {
 420     if (ResultCache.size() > MaxMemoizationEntries)
 421       ResultCache.clear();
 422     return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
 423                                       Bind);
 424   }
 425   // Implements ASTMatchFinder::matchesDescendantOf.
 426   bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
 427                            const DynTypedMatcher &Matcher,
 428                            BoundNodesTreeBuilder *Builder,
 429                            BindKind Bind) override {
 430     if (ResultCache.size() > MaxMemoizationEntries)
 431       ResultCache.clear();
 432     return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
 433                                       TK_AsIs, Bind);
 434   }
 435   // Implements ASTMatchFinder::matchesAncestorOf.
 436   bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
 437                          const DynTypedMatcher &Matcher,
 438                          BoundNodesTreeBuilder *Builder,
 439                          AncestorMatchMode MatchMode) override {
 440     // Reset the cache outside of the recursive call to make sure we
 441     // don't invalidate any iterators.
 442     if (ResultCache.size() > MaxMemoizationEntries)
 443       ResultCache.clear();
 444     return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
 445                                                 MatchMode);
 446   }
 447
 448   // Matches all registered matchers on the given node and calls the
 449   // result callback for every node that matches.
 450   void match(const ast_type_traits::DynTypedNode& Node) {
 451     for (std::vector<std::pair<internal::DynTypedMatcher,
 452                                MatchCallback *> >::const_iterator
 453              I = MatcherCallbackPairs->begin(),
 454              E = MatcherCallbackPairs->end();
 455          I != E; ++I) {
 456       BoundNodesTreeBuilder Builder;
 457       if (I->first.matches(Node, this, &Builder)) {
 458         MatchVisitor Visitor(ActiveASTContext, I->second);
 459         Builder.visitMatches(&Visitor);
 460       }
 461     }
 462   }
 463
 464   template <typename T> void match(const T &Node) {
 465     match(ast_type_traits::DynTypedNode::create(Node));
 466   }
 467
 468   // Implements ASTMatchFinder::getASTContext.
 469   ASTContext &getASTContext() const override { return *ActiveASTContext; }
 470
 471   bool shouldVisitTemplateInstantiations() const { return true; }
 472   bool shouldVisitImplicitCode() const { return true; }
 473   // Disables data recursion. We intercept Traverse* methods in the RAV, which
 474   // are not triggered during data recursion.
 475   bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
 476
 477 private:
 478   // Returns whether an ancestor of \p Node matches \p Matcher.
 479   //
 480   // The order of matching ((which can lead to different nodes being bound in
 481   // case there are multiple matches) is breadth first search.
 482   //
 483   // To allow memoization in the very common case of having deeply nested
 484   // expressions inside a template function, we first walk up the AST, memoizing
 485   // the result of the match along the way, as long as there is only a single
 486   // parent.
 487   //
 488   // Once there are multiple parents, the breadth first search order does not
 489   // allow simple memoization on the ancestors. Thus, we only memoize as long
 490   // as there is a single parent.
 491   bool memoizedMatchesAncestorOfRecursively(
 492       const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
 493       BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
 494     if (Node.get<TranslationUnitDecl>() ==
 495         ActiveASTContext->getTranslationUnitDecl())
 496       return false;
 497     assert(Node.getMemoizationData() &&
 498            "Invariant broken: only nodes that support memoization may be "
 499            "used in the parent map.");
 500     ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
 501     if (Parents.empty()) {
 502       assert(false && "Found node that is not in the parent map.");
 503       return false;
 504     }
 505     MatchKey Key;
 506     Key.MatcherID = Matcher.getID();
 507     Key.Node = Node;
 508     Key.BoundNodes = *Builder;
 509
 510     // Note that we cannot use insert and reuse the iterator, as recursive
 511     // calls to match might invalidate the result cache iterators.
 512     MemoizationMap::iterator I = ResultCache.find(Key);
 513     if (I != ResultCache.end()) {
 514       *Builder = I->second.Nodes;
 515       return I->second.ResultOfMatch;
 516     }
 517     MemoizedMatchResult Result;
 518     Result.ResultOfMatch = false;
 519     Result.Nodes = *Builder;
 520     if (Parents.size() == 1) {
 521       // Only one parent - do recursive memoization.
 522       const ast_type_traits::DynTypedNode Parent = Parents[0];
 523       if (Matcher.matches(Parent, this, &Result.Nodes)) {
 524         Result.ResultOfMatch = true;
 525       } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
 526         // Reset the results to not include the bound nodes from the failed
 527         // match above.
 528         Result.Nodes = *Builder;
 529         Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
 530             Parent, Matcher, &Result.Nodes, MatchMode);
 531         // Once we get back from the recursive call, the result will be the
 532         // same as the parent's result.
 533       }
 534     } else {
 535       // Multiple parents - BFS over the rest of the nodes.
 536       llvm::DenseSet<const void *> Visited;
 537       std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
 538                                                       Parents.end());
 539       while (!Queue.empty()) {
 540         Result.Nodes = *Builder;
 541         if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
 542           Result.ResultOfMatch = true;
 543           break;
 544         }
 545         if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
 546           ASTContext::ParentVector Ancestors =
 547               ActiveASTContext->getParents(Queue.front());
 548           for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(),
 549                                                         E = Ancestors.end();
 550                I != E; ++I) {
 551             // Make sure we do not visit the same node twice.
 552             // Otherwise, we'll visit the common ancestors as often as there
 553             // are splits on the way down.
 554             if (Visited.insert(I->getMemoizationData()).second)
 555               Queue.push_back(*I);
 556           }
 557         }
 558         Queue.pop_front();
 559       }
 560     }
 561     ResultCache[Key] = Result;
 562
 563     *Builder = Result.Nodes;
 564     return Result.ResultOfMatch;
 565   }
 566
 567   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
 568   // the aggregated bound nodes for each match.
 569   class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
 570   public:
 571     MatchVisitor(ASTContext* Context,
 572                  MatchFinder::MatchCallback* Callback)
 573       : Context(Context),
 574         Callback(Callback) {}
 575
 576     void visitMatch(const BoundNodes& BoundNodesView) override {
 577       Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
 578     }
 579
 580   private:
 581     ASTContext* Context;
 582     MatchFinder::MatchCallback* Callback;
 583   };
 584
 585   // Returns true if 'TypeNode' has an alias that matches the given matcher.
 586   bool typeHasMatchingAlias(const Type *TypeNode,
 587                             const Matcher<NamedDecl> Matcher,
 588                             BoundNodesTreeBuilder *Builder) {
 589     const Type *const CanonicalType =
 590       ActiveASTContext->getCanonicalType(TypeNode);
 591     const std::set<const TypedefNameDecl *> &Aliases =
 592         TypeAliases[CanonicalType];
 593     for (std::set<const TypedefNameDecl*>::const_iterator
 594            It = Aliases.begin(), End = Aliases.end();
 595          It != End; ++It) {
 596       BoundNodesTreeBuilder Result(*Builder);
 597       if (Matcher.matches(**It, this, &Result)) {
 598         *Builder = Result;
 599         return true;
 600       }
 601     }
 602     return false;
 603   }
 604
 605   std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *const
 606   MatcherCallbackPairs;
 607   ASTContext *ActiveASTContext;
 608
 609   // Maps a canonical type to its TypedefDecls.
 610   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
 611
 612   // Maps (matcher, node) -> the match result for memoization.
 613   typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
 614   MemoizationMap ResultCache;
 615 };
 616
 617 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
 618   // Type::getAs<...>() drills through typedefs.
 619   if (TypeNode->getAs<DependentNameType>() != nullptr ||
 620       TypeNode->getAs<DependentTemplateSpecializationType>() != nullptr ||
 621       TypeNode->getAs<TemplateTypeParmType>() != nullptr)
 622     // Dependent names and template TypeNode parameters will be matched when
 623     // the template is instantiated.
 624     return nullptr;
 625   TemplateSpecializationType const *TemplateType =
 626       TypeNode->getAs<TemplateSpecializationType>();
 627   if (!TemplateType) {
 628     return TypeNode->getAsCXXRecordDecl();
 629   }
 630   if (TemplateType->getTemplateName().isDependent())
 631     // Dependent template specializations will be matched when the
 632     // template is instantiated.
 633     return nullptr;
 634
 635   // For template specialization types which are specializing a template
 636   // declaration which is an explicit or partial specialization of another
 637   // template declaration, getAsCXXRecordDecl() returns the corresponding
 638   // ClassTemplateSpecializationDecl.
 639   //
 640   // For template specialization types which are specializing a template
 641   // declaration which is neither an explicit nor partial specialization of
 642   // another template declaration, getAsCXXRecordDecl() returns NULL and
 643   // we get the CXXRecordDecl of the templated declaration.
 644   CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
 645   if (SpecializationDecl) {
 646     return SpecializationDecl;
 647   }
 648   NamedDecl *Templated =
 649       TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
 650   if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
 651     return TemplatedRecord;
 652   }
 653   // Now it can still be that we have an alias template.
 654   TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
 655   assert(AliasDecl);
 656   return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
 657 }
 658
 659 // Returns true if the given class is directly or indirectly derived
 660 // from a base type with the given name.  A class is not considered to be
 661 // derived from itself.
 662 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
 663                                          const Matcher<NamedDecl> &Base,
 664                                          BoundNodesTreeBuilder *Builder) {
 665   if (!Declaration->hasDefinition())
 666     return false;
 667   for (const auto &It : Declaration->bases()) {
 668     const Type *TypeNode = It.getType().getTypePtr();
 669
 670     if (typeHasMatchingAlias(TypeNode, Base, Builder))
 671       return true;
 672
 673     CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
 674     if (!ClassDecl)
 675       continue;
 676     if (ClassDecl == Declaration) {
 677       // This can happen for recursive template definitions; if the
 678       // current declaration did not match, we can safely return false.
 679       return false;
 680     }
 681     BoundNodesTreeBuilder Result(*Builder);
 682     if (Base.matches(*ClassDecl, this, &Result)) {
 683       *Builder = Result;
 684       return true;
 685     }
 686     if (classIsDerivedFrom(ClassDecl, Base, Builder))
 687       return true;
 688   }
 689   return false;
 690 }
 691
 692 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
 693   if (!DeclNode) {
 694     return true;
 695   }
 696   match(*DeclNode);
 697   return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
 698 }
 699
 700 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
 701   if (!StmtNode) {
 702     return true;
 703   }
 704   match(*StmtNode);
 705   return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
 706 }
 707
 708 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
 709   match(TypeNode);
 710   return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
 711 }
 712
 713 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
 714   // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
 715   // We still want to find those types via matchers, so we match them here. Note
 716   // that the TypeLocs are structurally a shadow-hierarchy to the expressed
 717   // type, so we visit all involved parts of a compound type when matching on
 718   // each TypeLoc.
 719   match(TypeLocNode);
 720   match(TypeLocNode.getType());
 721   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
 722 }
 723
 724 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
 725   match(*NNS);
 726   return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
 727 }
 728
 729 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
 730     NestedNameSpecifierLoc NNS) {
 731   match(NNS);
 732   // We only match the nested name specifier here (as opposed to traversing it)
 733   // because the traversal is already done in the parallel "Loc"-hierarchy.
 734   match(*NNS.getNestedNameSpecifier());
 735   return
 736       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
 737 }
 738
 739 class MatchASTConsumer : public ASTConsumer {
 740 public:
 741   MatchASTConsumer(MatchFinder *Finder,
 742                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
 743       : Finder(Finder), ParsingDone(ParsingDone) {}
 744
 745 private:
 746   void HandleTranslationUnit(ASTContext &Context) override {
 747     if (ParsingDone != nullptr) {
 748       ParsingDone->run();
 749     }
 750     Finder->matchAST(Context);
 751   }
 752
 753   MatchFinder *Finder;
 754   MatchFinder::ParsingDoneTestCallback *ParsingDone;
 755 };
 756
 757 } // end namespace
 758 } // end namespace internal
 759
 760 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
 761                                       ASTContext *Context)
 762   : Nodes(Nodes), Context(Context),
 763     SourceManager(&Context->getSourceManager()) {}
 764
 765 MatchFinder::MatchCallback::~MatchCallback() {}
 766 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
 767
 768 MatchFinder::MatchFinder() : ParsingDone(nullptr) {}
 769
 770 MatchFinder::~MatchFinder() {}
 771
 772 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
 773                              MatchCallback *Action) {
 774   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 775 }
 776
 777 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
 778                              MatchCallback *Action) {
 779   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 780 }
 781
 782 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
 783                              MatchCallback *Action) {
 784   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 785 }
 786
 787 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
 788                              MatchCallback *Action) {
 789   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 790 }
 791
 792 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
 793                              MatchCallback *Action) {
 794   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 795 }
 796
 797 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
 798                              MatchCallback *Action) {
 799   MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
 800 }
 801
 802 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
 803                                     MatchCallback *Action) {
 804   if (NodeMatch.canConvertTo<Decl>()) {
 805     addMatcher(NodeMatch.convertTo<Decl>(), Action);
 806     return true;
 807   } else if (NodeMatch.canConvertTo<QualType>()) {
 808     addMatcher(NodeMatch.convertTo<QualType>(), Action);
 809     return true;
 810   } else if (NodeMatch.canConvertTo<Stmt>()) {
 811     addMatcher(NodeMatch.convertTo<Stmt>(), Action);
 812     return true;
 813   } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
 814     addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
 815     return true;
 816   } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
 817     addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
 818     return true;
 819   } else if (NodeMatch.canConvertTo<TypeLoc>()) {
 820     addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
 821     return true;
 822   }
 823   return false;
 824 }
 825
 826 ASTConsumer *MatchFinder::newASTConsumer() {
 827   return new internal::MatchASTConsumer(this, ParsingDone);
 828 }
 829
 830 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
 831                         ASTContext &Context) {
 832   internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
 833   Visitor.set_active_ast_context(&Context);
 834   Visitor.match(Node);
 835 }
 836
 837 void MatchFinder::matchAST(ASTContext &Context) {
 838   internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
 839   Visitor.set_active_ast_context(&Context);
 840   Visitor.onStartOfTranslationUnit();
 841   Visitor.TraverseDecl(Context.getTranslationUnitDecl());
 842   Visitor.onEndOfTranslationUnit();
 843 }
 844
 845 void MatchFinder::registerTestCallbackAfterParsing(
 846     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
 847   ParsingDone = NewParsingDone;
 848 }
 849
 850 } // end namespace ast_matchers
 851 } // end namespace clang