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