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