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