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