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