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