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
26namespace clang {
27namespace ast_matchers {
28namespace internal {
29namespace {
30
31typedef 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.
44typedef std::pair<uint64_t, const void*> UntypedMatchInput;
45
46// Used to store the result of a match and possibly bound nodes.
47struct MemoizedMatchResult {
48  bool ResultOfMatch;
49  BoundNodesTree Nodes;
50};
51
52// A RecursiveASTVisitor that traverses all children or all descendants of
53// a node.
54class MatchChildASTVisitor
55    : public RecursiveASTVisitor<MatchChildASTVisitor> {
56public:
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
174private:
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.
263class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
264                        public ASTMatchFinder {
265public:
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
425private:
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.
553bool 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
618bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
619  if (DeclNode == NULL) {
620    return true;
621  }
622  match(*DeclNode);
623  return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
624}
625
626bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
627  if (StmtNode == NULL) {
628    return true;
629  }
630  match(*StmtNode);
631  return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
632}
633
634bool MatchASTVisitor::TraverseType(QualType TypeNode) {
635  match(TypeNode);
636  return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
637}
638
639bool 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
650bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
651  match(*NNS);
652  return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
653}
654
655bool 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
665class MatchASTConsumer : public ASTConsumer {
666public:
667  MatchASTConsumer(
668    std::vector<std::pair<const internal::DynTypedMatcher*,
669                          MatchCallback*> > *MatcherCallbackPairs,
670    MatchFinder::ParsingDoneTestCallback *ParsingDone)
671    : Visitor(MatcherCallbackPairs),
672      ParsingDone(ParsingDone) {}
673
674private:
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
692MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
693                                      ASTContext *Context)
694  : Nodes(Nodes), Context(Context),
695    SourceManager(&Context->getSourceManager()) {}
696
697MatchFinder::MatchCallback::~MatchCallback() {}
698MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
699
700MatchFinder::MatchFinder() : ParsingDone(NULL) {}
701
702MatchFinder::~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
711void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
712                             MatchCallback *Action) {
713  MatcherCallbackPairs.push_back(std::make_pair(
714    new internal::Matcher<Decl>(NodeMatch), Action));
715}
716
717void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
718                             MatchCallback *Action) {
719  MatcherCallbackPairs.push_back(std::make_pair(
720    new internal::Matcher<QualType>(NodeMatch), Action));
721}
722
723void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
724                             MatchCallback *Action) {
725  MatcherCallbackPairs.push_back(std::make_pair(
726    new internal::Matcher<Stmt>(NodeMatch), Action));
727}
728
729void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
730                             MatchCallback *Action) {
731  MatcherCallbackPairs.push_back(std::make_pair(
732    new NestedNameSpecifierMatcher(NodeMatch), Action));
733}
734
735void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
736                             MatchCallback *Action) {
737  MatcherCallbackPairs.push_back(std::make_pair(
738    new NestedNameSpecifierLocMatcher(NodeMatch), Action));
739}
740
741void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
742                             MatchCallback *Action) {
743  MatcherCallbackPairs.push_back(std::make_pair(
744    new TypeLocMatcher(NodeMatch), Action));
745}
746
747ASTConsumer *MatchFinder::newASTConsumer() {
748  return new internal::MatchASTConsumer(&MatcherCallbackPairs, ParsingDone);
749}
750
751void 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
758void MatchFinder::registerTestCallbackAfterParsing(
759    MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
760  ParsingDone = NewParsingDone;
761}
762
763} // end namespace ast_matchers
764} // end namespace clang
765