xref: /freebsd-src/contrib/llvm-project/clang/lib/ASTMatchers/ASTMatchFinder.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad)
10b57cec5SDimitry Andric //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric //  Implements an algorithm to efficiently search for matches on AST nodes.
100b57cec5SDimitry Andric //  Uses memoization to support recursive matches like HasDescendant.
110b57cec5SDimitry Andric //
120b57cec5SDimitry Andric //  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
130b57cec5SDimitry Andric //  calling the Matches(...) method of each matcher we are running on each
140b57cec5SDimitry Andric //  AST node. The matcher can recurse via the ASTMatchFinder interface.
150b57cec5SDimitry Andric //
160b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
170b57cec5SDimitry Andric 
180b57cec5SDimitry Andric #include "clang/ASTMatchers/ASTMatchFinder.h"
190b57cec5SDimitry Andric #include "clang/AST/ASTConsumer.h"
200b57cec5SDimitry Andric #include "clang/AST/ASTContext.h"
21*5f757f3fSDimitry Andric #include "clang/AST/DeclCXX.h"
220b57cec5SDimitry Andric #include "clang/AST/RecursiveASTVisitor.h"
230b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h"
24*5f757f3fSDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
250b57cec5SDimitry Andric #include "llvm/ADT/StringMap.h"
2681ad6265SDimitry Andric #include "llvm/Support/PrettyStackTrace.h"
270b57cec5SDimitry Andric #include "llvm/Support/Timer.h"
280b57cec5SDimitry Andric #include <deque>
290b57cec5SDimitry Andric #include <memory>
300b57cec5SDimitry Andric #include <set>
310b57cec5SDimitry Andric 
320b57cec5SDimitry Andric namespace clang {
330b57cec5SDimitry Andric namespace ast_matchers {
340b57cec5SDimitry Andric namespace internal {
350b57cec5SDimitry Andric namespace {
360b57cec5SDimitry Andric 
370b57cec5SDimitry Andric typedef MatchFinder::MatchCallback MatchCallback;
380b57cec5SDimitry Andric 
390b57cec5SDimitry Andric // The maximum number of memoization entries to store.
400b57cec5SDimitry Andric // 10k has been experimentally found to give a good trade-off
410b57cec5SDimitry Andric // of performance vs. memory consumption by running matcher
420b57cec5SDimitry Andric // that match on every statement over a very large codebase.
430b57cec5SDimitry Andric //
440b57cec5SDimitry Andric // FIXME: Do some performance optimization in general and
450b57cec5SDimitry Andric // revisit this number; also, put up micro-benchmarks that we can
460b57cec5SDimitry Andric // optimize this on.
470b57cec5SDimitry Andric static const unsigned MaxMemoizationEntries = 10000;
480b57cec5SDimitry Andric 
495ffd83dbSDimitry Andric enum class MatchType {
505ffd83dbSDimitry Andric   Ancestors,
515ffd83dbSDimitry Andric 
525ffd83dbSDimitry Andric   Descendants,
535ffd83dbSDimitry Andric   Child,
545ffd83dbSDimitry Andric };
555ffd83dbSDimitry Andric 
560b57cec5SDimitry Andric // We use memoization to avoid running the same matcher on the same
570b57cec5SDimitry Andric // AST node twice.  This struct is the key for looking up match
580b57cec5SDimitry Andric // result.  It consists of an ID of the MatcherInterface (for
590b57cec5SDimitry Andric // identifying the matcher), a pointer to the AST node and the
600b57cec5SDimitry Andric // bound nodes before the matcher was executed.
610b57cec5SDimitry Andric //
620b57cec5SDimitry Andric // We currently only memoize on nodes whose pointers identify the
630b57cec5SDimitry Andric // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
640b57cec5SDimitry Andric // For \c QualType and \c TypeLoc it is possible to implement
650b57cec5SDimitry Andric // generation of keys for each type.
660b57cec5SDimitry Andric // FIXME: Benchmark whether memoization of non-pointer typed nodes
670b57cec5SDimitry Andric // provides enough benefit for the additional amount of code.
680b57cec5SDimitry Andric struct MatchKey {
690b57cec5SDimitry Andric   DynTypedMatcher::MatcherIDType MatcherID;
705ffd83dbSDimitry Andric   DynTypedNode Node;
710b57cec5SDimitry Andric   BoundNodesTreeBuilder BoundNodes;
725ffd83dbSDimitry Andric   TraversalKind Traversal = TK_AsIs;
735ffd83dbSDimitry Andric   MatchType Type;
740b57cec5SDimitry Andric 
operator <clang::ast_matchers::internal::__anonbe2d60470111::MatchKey750b57cec5SDimitry Andric   bool operator<(const MatchKey &Other) const {
765ffd83dbSDimitry Andric     return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
775ffd83dbSDimitry Andric            std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
785ffd83dbSDimitry Andric                     Other.BoundNodes);
790b57cec5SDimitry Andric   }
800b57cec5SDimitry Andric };
810b57cec5SDimitry Andric 
820b57cec5SDimitry Andric // Used to store the result of a match and possibly bound nodes.
830b57cec5SDimitry Andric struct MemoizedMatchResult {
840b57cec5SDimitry Andric   bool ResultOfMatch;
850b57cec5SDimitry Andric   BoundNodesTreeBuilder Nodes;
860b57cec5SDimitry Andric };
870b57cec5SDimitry Andric 
880b57cec5SDimitry Andric // A RecursiveASTVisitor that traverses all children or all descendants of
890b57cec5SDimitry Andric // a node.
900b57cec5SDimitry Andric class MatchChildASTVisitor
910b57cec5SDimitry Andric     : public RecursiveASTVisitor<MatchChildASTVisitor> {
920b57cec5SDimitry Andric public:
930b57cec5SDimitry Andric   typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
940b57cec5SDimitry Andric 
950b57cec5SDimitry Andric   // Creates an AST visitor that matches 'matcher' on all children or
960b57cec5SDimitry Andric   // descendants of a traversed node. max_depth is the maximum depth
970b57cec5SDimitry Andric   // to traverse: use 1 for matching the children and INT_MAX for
980b57cec5SDimitry Andric   // matching the descendants.
MatchChildASTVisitor(const DynTypedMatcher * Matcher,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,int MaxDepth,bool IgnoreImplicitChildren,ASTMatchFinder::BindKind Bind)990b57cec5SDimitry Andric   MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
1000b57cec5SDimitry Andric                        BoundNodesTreeBuilder *Builder, int MaxDepth,
101e8d8bef9SDimitry Andric                        bool IgnoreImplicitChildren,
102e8d8bef9SDimitry Andric                        ASTMatchFinder::BindKind Bind)
1030b57cec5SDimitry Andric       : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
104e8d8bef9SDimitry Andric         MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
105e8d8bef9SDimitry Andric         Bind(Bind), Matches(false) {}
1060b57cec5SDimitry Andric 
1070b57cec5SDimitry Andric   // Returns true if a match is found in the subtree rooted at the
1080b57cec5SDimitry Andric   // given AST node. This is done via a set of mutually recursive
1090b57cec5SDimitry Andric   // functions. Here's how the recursion is done (the  *wildcard can
1100b57cec5SDimitry Andric   // actually be Decl, Stmt, or Type):
1110b57cec5SDimitry Andric   //
1120b57cec5SDimitry Andric   //   - Traverse(node) calls BaseTraverse(node) when it needs
1130b57cec5SDimitry Andric   //     to visit the descendants of node.
1140b57cec5SDimitry Andric   //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
1150b57cec5SDimitry Andric   //     Traverse*(c) for each child c of 'node'.
1160b57cec5SDimitry Andric   //   - Traverse*(c) in turn calls Traverse(c), completing the
1170b57cec5SDimitry Andric   //     recursion.
findMatch(const DynTypedNode & DynNode)1185ffd83dbSDimitry Andric   bool findMatch(const DynTypedNode &DynNode) {
1190b57cec5SDimitry Andric     reset();
1200b57cec5SDimitry Andric     if (const Decl *D = DynNode.get<Decl>())
1210b57cec5SDimitry Andric       traverse(*D);
1220b57cec5SDimitry Andric     else if (const Stmt *S = DynNode.get<Stmt>())
1230b57cec5SDimitry Andric       traverse(*S);
1240b57cec5SDimitry Andric     else if (const NestedNameSpecifier *NNS =
1250b57cec5SDimitry Andric              DynNode.get<NestedNameSpecifier>())
1260b57cec5SDimitry Andric       traverse(*NNS);
1270b57cec5SDimitry Andric     else if (const NestedNameSpecifierLoc *NNSLoc =
1280b57cec5SDimitry Andric              DynNode.get<NestedNameSpecifierLoc>())
1290b57cec5SDimitry Andric       traverse(*NNSLoc);
1300b57cec5SDimitry Andric     else if (const QualType *Q = DynNode.get<QualType>())
1310b57cec5SDimitry Andric       traverse(*Q);
1320b57cec5SDimitry Andric     else if (const TypeLoc *T = DynNode.get<TypeLoc>())
1330b57cec5SDimitry Andric       traverse(*T);
1340b57cec5SDimitry Andric     else if (const auto *C = DynNode.get<CXXCtorInitializer>())
1350b57cec5SDimitry Andric       traverse(*C);
136e8d8bef9SDimitry Andric     else if (const TemplateArgumentLoc *TALoc =
137e8d8bef9SDimitry Andric                  DynNode.get<TemplateArgumentLoc>())
138e8d8bef9SDimitry Andric       traverse(*TALoc);
139349cc55cSDimitry Andric     else if (const Attr *A = DynNode.get<Attr>())
140349cc55cSDimitry Andric       traverse(*A);
1410b57cec5SDimitry Andric     // FIXME: Add other base types after adding tests.
1420b57cec5SDimitry Andric 
1430b57cec5SDimitry Andric     // It's OK to always overwrite the bound nodes, as if there was
1440b57cec5SDimitry Andric     // no match in this recursive branch, the result set is empty
1450b57cec5SDimitry Andric     // anyway.
1460b57cec5SDimitry Andric     *Builder = ResultBindings;
1470b57cec5SDimitry Andric 
1480b57cec5SDimitry Andric     return Matches;
1490b57cec5SDimitry Andric   }
1500b57cec5SDimitry Andric 
1510b57cec5SDimitry Andric   // The following are overriding methods from the base visitor class.
1520b57cec5SDimitry Andric   // They are public only to allow CRTP to work. They are *not *part
1530b57cec5SDimitry Andric   // of the public API of this class.
TraverseDecl(Decl * DeclNode)1540b57cec5SDimitry Andric   bool TraverseDecl(Decl *DeclNode) {
155e8d8bef9SDimitry Andric 
156e8d8bef9SDimitry Andric     if (DeclNode && DeclNode->isImplicit() &&
157e8d8bef9SDimitry Andric         Finder->isTraversalIgnoringImplicitNodes())
158e8d8bef9SDimitry Andric       return baseTraverse(*DeclNode);
159e8d8bef9SDimitry Andric 
1600b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
1610b57cec5SDimitry Andric     return (DeclNode == nullptr) || traverse(*DeclNode);
1620b57cec5SDimitry Andric   }
163480093f4SDimitry Andric 
getStmtToTraverse(Stmt * StmtNode)164480093f4SDimitry Andric   Stmt *getStmtToTraverse(Stmt *StmtNode) {
165480093f4SDimitry Andric     Stmt *StmtToTraverse = StmtNode;
166480093f4SDimitry Andric     if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
167480093f4SDimitry Andric       auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
168e8d8bef9SDimitry Andric       if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
169480093f4SDimitry Andric         StmtToTraverse = LambdaNode;
170480093f4SDimitry Andric       else
1715ffd83dbSDimitry Andric         StmtToTraverse =
1725ffd83dbSDimitry Andric             Finder->getASTContext().getParentMapContext().traverseIgnored(
1735ffd83dbSDimitry Andric                 ExprNode);
174480093f4SDimitry Andric     }
175480093f4SDimitry Andric     return StmtToTraverse;
176480093f4SDimitry Andric   }
177480093f4SDimitry Andric 
TraverseStmt(Stmt * StmtNode,DataRecursionQueue * Queue=nullptr)1780b57cec5SDimitry Andric   bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
1790b57cec5SDimitry Andric     // If we need to keep track of the depth, we can't perform data recursion.
1800b57cec5SDimitry Andric     if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
1810b57cec5SDimitry Andric       Queue = nullptr;
1820b57cec5SDimitry Andric 
1830b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
184480093f4SDimitry Andric     Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
1850b57cec5SDimitry Andric     if (!StmtToTraverse)
1860b57cec5SDimitry Andric       return true;
187e8d8bef9SDimitry Andric 
188e8d8bef9SDimitry Andric     if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
189e8d8bef9SDimitry Andric       return true;
190e8d8bef9SDimitry Andric 
1910b57cec5SDimitry Andric     if (!match(*StmtToTraverse))
1920b57cec5SDimitry Andric       return false;
1930b57cec5SDimitry Andric     return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
1940b57cec5SDimitry Andric   }
1950b57cec5SDimitry Andric   // We assume that the QualType and the contained type are on the same
1960b57cec5SDimitry Andric   // hierarchy level. Thus, we try to match either of them.
TraverseType(QualType TypeNode)1970b57cec5SDimitry Andric   bool TraverseType(QualType TypeNode) {
1980b57cec5SDimitry Andric     if (TypeNode.isNull())
1990b57cec5SDimitry Andric       return true;
2000b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
2010b57cec5SDimitry Andric     // Match the Type.
2020b57cec5SDimitry Andric     if (!match(*TypeNode))
2030b57cec5SDimitry Andric       return false;
2040b57cec5SDimitry Andric     // The QualType is matched inside traverse.
2050b57cec5SDimitry Andric     return traverse(TypeNode);
2060b57cec5SDimitry Andric   }
2070b57cec5SDimitry Andric   // We assume that the TypeLoc, contained QualType and contained Type all are
2080b57cec5SDimitry Andric   // on the same hierarchy level. Thus, we try to match all of them.
TraverseTypeLoc(TypeLoc TypeLocNode)2090b57cec5SDimitry Andric   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
2100b57cec5SDimitry Andric     if (TypeLocNode.isNull())
2110b57cec5SDimitry Andric       return true;
2120b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
2130b57cec5SDimitry Andric     // Match the Type.
2140b57cec5SDimitry Andric     if (!match(*TypeLocNode.getType()))
2150b57cec5SDimitry Andric       return false;
2160b57cec5SDimitry Andric     // Match the QualType.
2170b57cec5SDimitry Andric     if (!match(TypeLocNode.getType()))
2180b57cec5SDimitry Andric       return false;
2190b57cec5SDimitry Andric     // The TypeLoc is matched inside traverse.
2200b57cec5SDimitry Andric     return traverse(TypeLocNode);
2210b57cec5SDimitry Andric   }
TraverseNestedNameSpecifier(NestedNameSpecifier * NNS)2220b57cec5SDimitry Andric   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
2230b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
2240b57cec5SDimitry Andric     return (NNS == nullptr) || traverse(*NNS);
2250b57cec5SDimitry Andric   }
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)2260b57cec5SDimitry Andric   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
2270b57cec5SDimitry Andric     if (!NNS)
2280b57cec5SDimitry Andric       return true;
2290b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
2300b57cec5SDimitry Andric     if (!match(*NNS.getNestedNameSpecifier()))
2310b57cec5SDimitry Andric       return false;
2320b57cec5SDimitry Andric     return traverse(NNS);
2330b57cec5SDimitry Andric   }
TraverseConstructorInitializer(CXXCtorInitializer * CtorInit)2340b57cec5SDimitry Andric   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
2350b57cec5SDimitry Andric     if (!CtorInit)
2360b57cec5SDimitry Andric       return true;
2370b57cec5SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
2380b57cec5SDimitry Andric     return traverse(*CtorInit);
2390b57cec5SDimitry Andric   }
TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL)240e8d8bef9SDimitry Andric   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
241e8d8bef9SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
242e8d8bef9SDimitry Andric     return traverse(TAL);
243e8d8bef9SDimitry Andric   }
TraverseCXXForRangeStmt(CXXForRangeStmt * Node)244e8d8bef9SDimitry Andric   bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
245e8d8bef9SDimitry Andric     if (!Finder->isTraversalIgnoringImplicitNodes())
246e8d8bef9SDimitry Andric       return VisitorBase::TraverseCXXForRangeStmt(Node);
247e8d8bef9SDimitry Andric     if (!Node)
248e8d8bef9SDimitry Andric       return true;
249e8d8bef9SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
250e8d8bef9SDimitry Andric     if (auto *Init = Node->getInit())
251d409305fSDimitry Andric       if (!traverse(*Init))
252e8d8bef9SDimitry Andric         return false;
253d409305fSDimitry Andric     if (!match(*Node->getLoopVariable()))
254d409305fSDimitry Andric       return false;
255d409305fSDimitry Andric     if (match(*Node->getRangeInit()))
256d409305fSDimitry Andric       if (!VisitorBase::TraverseStmt(Node->getRangeInit()))
257d409305fSDimitry Andric         return false;
258d409305fSDimitry Andric     if (!match(*Node->getBody()))
259e8d8bef9SDimitry Andric       return false;
260e8d8bef9SDimitry Andric     return VisitorBase::TraverseStmt(Node->getBody());
261e8d8bef9SDimitry Andric   }
TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator * Node)262e8d8bef9SDimitry Andric   bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
263e8d8bef9SDimitry Andric     if (!Finder->isTraversalIgnoringImplicitNodes())
264e8d8bef9SDimitry Andric       return VisitorBase::TraverseCXXRewrittenBinaryOperator(Node);
265e8d8bef9SDimitry Andric     if (!Node)
266e8d8bef9SDimitry Andric       return true;
267e8d8bef9SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
268e8d8bef9SDimitry Andric 
269e8d8bef9SDimitry Andric     return match(*Node->getLHS()) && match(*Node->getRHS());
270e8d8bef9SDimitry Andric   }
TraverseAttr(Attr * A)271349cc55cSDimitry Andric   bool TraverseAttr(Attr *A) {
272349cc55cSDimitry Andric     if (A == nullptr ||
273349cc55cSDimitry Andric         (A->isImplicit() &&
274349cc55cSDimitry Andric          Finder->getASTContext().getParentMapContext().getTraversalKind() ==
275349cc55cSDimitry Andric              TK_IgnoreUnlessSpelledInSource))
276349cc55cSDimitry Andric       return true;
277349cc55cSDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
278349cc55cSDimitry Andric     return traverse(*A);
279349cc55cSDimitry Andric   }
TraverseLambdaExpr(LambdaExpr * Node)280480093f4SDimitry Andric   bool TraverseLambdaExpr(LambdaExpr *Node) {
281e8d8bef9SDimitry Andric     if (!Finder->isTraversalIgnoringImplicitNodes())
282480093f4SDimitry Andric       return VisitorBase::TraverseLambdaExpr(Node);
283480093f4SDimitry Andric     if (!Node)
284480093f4SDimitry Andric       return true;
285480093f4SDimitry Andric     ScopedIncrement ScopedDepth(&CurrentDepth);
286480093f4SDimitry Andric 
287480093f4SDimitry Andric     for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
288480093f4SDimitry Andric       const auto *C = Node->capture_begin() + I;
289480093f4SDimitry Andric       if (!C->isExplicit())
290480093f4SDimitry Andric         continue;
291480093f4SDimitry Andric       if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))
292480093f4SDimitry Andric         return false;
293480093f4SDimitry Andric       if (!match(*Node->capture_init_begin()[I]))
294480093f4SDimitry Andric         return false;
295480093f4SDimitry Andric     }
296480093f4SDimitry Andric 
297480093f4SDimitry Andric     if (const auto *TPL = Node->getTemplateParameterList()) {
298480093f4SDimitry Andric       for (const auto *TP : *TPL) {
299480093f4SDimitry Andric         if (!match(*TP))
300480093f4SDimitry Andric           return false;
301480093f4SDimitry Andric       }
302480093f4SDimitry Andric     }
303480093f4SDimitry Andric 
304480093f4SDimitry Andric     for (const auto *P : Node->getCallOperator()->parameters()) {
305480093f4SDimitry Andric       if (!match(*P))
306480093f4SDimitry Andric         return false;
307480093f4SDimitry Andric     }
308480093f4SDimitry Andric 
309480093f4SDimitry Andric     if (!match(*Node->getBody()))
310480093f4SDimitry Andric       return false;
311480093f4SDimitry Andric 
312d409305fSDimitry Andric     return VisitorBase::TraverseStmt(Node->getBody());
313480093f4SDimitry Andric   }
3140b57cec5SDimitry Andric 
shouldVisitTemplateInstantiations() const3150b57cec5SDimitry Andric   bool shouldVisitTemplateInstantiations() const { return true; }
shouldVisitImplicitCode() const316e8d8bef9SDimitry Andric   bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
3170b57cec5SDimitry Andric 
3180b57cec5SDimitry Andric private:
3190b57cec5SDimitry Andric   // Used for updating the depth during traversal.
3200b57cec5SDimitry Andric   struct ScopedIncrement {
ScopedIncrementclang::ast_matchers::internal::__anonbe2d60470111::MatchChildASTVisitor::ScopedIncrement3210b57cec5SDimitry Andric     explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
~ScopedIncrementclang::ast_matchers::internal::__anonbe2d60470111::MatchChildASTVisitor::ScopedIncrement3220b57cec5SDimitry Andric     ~ScopedIncrement() { --(*Depth); }
3230b57cec5SDimitry Andric 
3240b57cec5SDimitry Andric    private:
3250b57cec5SDimitry Andric     int *Depth;
3260b57cec5SDimitry Andric   };
3270b57cec5SDimitry Andric 
3280b57cec5SDimitry Andric   // Resets the state of this object.
reset()3290b57cec5SDimitry Andric   void reset() {
3300b57cec5SDimitry Andric     Matches = false;
3310b57cec5SDimitry Andric     CurrentDepth = 0;
3320b57cec5SDimitry Andric   }
3330b57cec5SDimitry Andric 
3340b57cec5SDimitry Andric   // Forwards the call to the corresponding Traverse*() method in the
3350b57cec5SDimitry Andric   // base visitor class.
baseTraverse(const Decl & DeclNode)3360b57cec5SDimitry Andric   bool baseTraverse(const Decl &DeclNode) {
3370b57cec5SDimitry Andric     return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
3380b57cec5SDimitry Andric   }
baseTraverse(const Stmt & StmtNode)3390b57cec5SDimitry Andric   bool baseTraverse(const Stmt &StmtNode) {
3400b57cec5SDimitry Andric     return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
3410b57cec5SDimitry Andric   }
baseTraverse(QualType TypeNode)3420b57cec5SDimitry Andric   bool baseTraverse(QualType TypeNode) {
3430b57cec5SDimitry Andric     return VisitorBase::TraverseType(TypeNode);
3440b57cec5SDimitry Andric   }
baseTraverse(TypeLoc TypeLocNode)3450b57cec5SDimitry Andric   bool baseTraverse(TypeLoc TypeLocNode) {
3460b57cec5SDimitry Andric     return VisitorBase::TraverseTypeLoc(TypeLocNode);
3470b57cec5SDimitry Andric   }
baseTraverse(const NestedNameSpecifier & NNS)3480b57cec5SDimitry Andric   bool baseTraverse(const NestedNameSpecifier &NNS) {
3490b57cec5SDimitry Andric     return VisitorBase::TraverseNestedNameSpecifier(
3500b57cec5SDimitry Andric         const_cast<NestedNameSpecifier*>(&NNS));
3510b57cec5SDimitry Andric   }
baseTraverse(NestedNameSpecifierLoc NNS)3520b57cec5SDimitry Andric   bool baseTraverse(NestedNameSpecifierLoc NNS) {
3530b57cec5SDimitry Andric     return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
3540b57cec5SDimitry Andric   }
baseTraverse(const CXXCtorInitializer & CtorInit)3550b57cec5SDimitry Andric   bool baseTraverse(const CXXCtorInitializer &CtorInit) {
3560b57cec5SDimitry Andric     return VisitorBase::TraverseConstructorInitializer(
3570b57cec5SDimitry Andric         const_cast<CXXCtorInitializer *>(&CtorInit));
3580b57cec5SDimitry Andric   }
baseTraverse(TemplateArgumentLoc TAL)359e8d8bef9SDimitry Andric   bool baseTraverse(TemplateArgumentLoc TAL) {
360e8d8bef9SDimitry Andric     return VisitorBase::TraverseTemplateArgumentLoc(TAL);
361e8d8bef9SDimitry Andric   }
baseTraverse(const Attr & AttrNode)362349cc55cSDimitry Andric   bool baseTraverse(const Attr &AttrNode) {
363349cc55cSDimitry Andric     return VisitorBase::TraverseAttr(const_cast<Attr *>(&AttrNode));
364349cc55cSDimitry Andric   }
3650b57cec5SDimitry Andric 
3660b57cec5SDimitry Andric   // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
3670b57cec5SDimitry Andric   //   0 < CurrentDepth <= MaxDepth.
3680b57cec5SDimitry Andric   //
3690b57cec5SDimitry Andric   // Returns 'true' if traversal should continue after this function
3700b57cec5SDimitry Andric   // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
3710b57cec5SDimitry Andric   template <typename T>
match(const T & Node)3720b57cec5SDimitry Andric   bool match(const T &Node) {
3730b57cec5SDimitry Andric     if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
3740b57cec5SDimitry Andric       return true;
3750b57cec5SDimitry Andric     }
3760b57cec5SDimitry Andric     if (Bind != ASTMatchFinder::BK_All) {
3770b57cec5SDimitry Andric       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
3785ffd83dbSDimitry Andric       if (Matcher->matches(DynTypedNode::create(Node), Finder,
3790b57cec5SDimitry Andric                            &RecursiveBuilder)) {
3800b57cec5SDimitry Andric         Matches = true;
3810b57cec5SDimitry Andric         ResultBindings.addMatch(RecursiveBuilder);
3820b57cec5SDimitry Andric         return false; // Abort as soon as a match is found.
3830b57cec5SDimitry Andric       }
3840b57cec5SDimitry Andric     } else {
3850b57cec5SDimitry Andric       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
3865ffd83dbSDimitry Andric       if (Matcher->matches(DynTypedNode::create(Node), Finder,
3870b57cec5SDimitry Andric                            &RecursiveBuilder)) {
3880b57cec5SDimitry Andric         // After the first match the matcher succeeds.
3890b57cec5SDimitry Andric         Matches = true;
3900b57cec5SDimitry Andric         ResultBindings.addMatch(RecursiveBuilder);
3910b57cec5SDimitry Andric       }
3920b57cec5SDimitry Andric     }
3930b57cec5SDimitry Andric     return true;
3940b57cec5SDimitry Andric   }
3950b57cec5SDimitry Andric 
3960b57cec5SDimitry Andric   // Traverses the subtree rooted at 'Node'; returns true if the
3970b57cec5SDimitry Andric   // traversal should continue after this function returns.
3980b57cec5SDimitry Andric   template <typename T>
traverse(const T & Node)3990b57cec5SDimitry Andric   bool traverse(const T &Node) {
4000b57cec5SDimitry Andric     static_assert(IsBaseType<T>::value,
4010b57cec5SDimitry Andric                   "traverse can only be instantiated with base type");
4020b57cec5SDimitry Andric     if (!match(Node))
4030b57cec5SDimitry Andric       return false;
4040b57cec5SDimitry Andric     return baseTraverse(Node);
4050b57cec5SDimitry Andric   }
4060b57cec5SDimitry Andric 
4070b57cec5SDimitry Andric   const DynTypedMatcher *const Matcher;
4080b57cec5SDimitry Andric   ASTMatchFinder *const Finder;
4090b57cec5SDimitry Andric   BoundNodesTreeBuilder *const Builder;
4100b57cec5SDimitry Andric   BoundNodesTreeBuilder ResultBindings;
4110b57cec5SDimitry Andric   int CurrentDepth;
4120b57cec5SDimitry Andric   const int MaxDepth;
413e8d8bef9SDimitry Andric   const bool IgnoreImplicitChildren;
4140b57cec5SDimitry Andric   const ASTMatchFinder::BindKind Bind;
4150b57cec5SDimitry Andric   bool Matches;
4160b57cec5SDimitry Andric };
4170b57cec5SDimitry Andric 
4180b57cec5SDimitry Andric // Controls the outermost traversal of the AST and allows to match multiple
4190b57cec5SDimitry Andric // matchers.
4200b57cec5SDimitry Andric class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
4210b57cec5SDimitry Andric                         public ASTMatchFinder {
4220b57cec5SDimitry Andric public:
MatchASTVisitor(const MatchFinder::MatchersByType * Matchers,const MatchFinder::MatchFinderOptions & Options)4230b57cec5SDimitry Andric   MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
4240b57cec5SDimitry Andric                   const MatchFinder::MatchFinderOptions &Options)
4250b57cec5SDimitry Andric       : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
4260b57cec5SDimitry Andric 
~MatchASTVisitor()4270b57cec5SDimitry Andric   ~MatchASTVisitor() override {
4280b57cec5SDimitry Andric     if (Options.CheckProfiling) {
4290b57cec5SDimitry Andric       Options.CheckProfiling->Records = std::move(TimeByBucket);
4300b57cec5SDimitry Andric     }
4310b57cec5SDimitry Andric   }
4320b57cec5SDimitry Andric 
onStartOfTranslationUnit()4330b57cec5SDimitry Andric   void onStartOfTranslationUnit() {
43481ad6265SDimitry Andric     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
4350b57cec5SDimitry Andric     TimeBucketRegion Timer;
4360b57cec5SDimitry Andric     for (MatchCallback *MC : Matchers->AllCallbacks) {
4370b57cec5SDimitry Andric       if (EnableCheckProfiling)
4380b57cec5SDimitry Andric         Timer.setBucket(&TimeByBucket[MC->getID()]);
4390b57cec5SDimitry Andric       MC->onStartOfTranslationUnit();
4400b57cec5SDimitry Andric     }
4410b57cec5SDimitry Andric   }
4420b57cec5SDimitry Andric 
onEndOfTranslationUnit()4430b57cec5SDimitry Andric   void onEndOfTranslationUnit() {
44481ad6265SDimitry Andric     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
4450b57cec5SDimitry Andric     TimeBucketRegion Timer;
4460b57cec5SDimitry Andric     for (MatchCallback *MC : Matchers->AllCallbacks) {
4470b57cec5SDimitry Andric       if (EnableCheckProfiling)
4480b57cec5SDimitry Andric         Timer.setBucket(&TimeByBucket[MC->getID()]);
4490b57cec5SDimitry Andric       MC->onEndOfTranslationUnit();
4500b57cec5SDimitry Andric     }
4510b57cec5SDimitry Andric   }
4520b57cec5SDimitry Andric 
set_active_ast_context(ASTContext * NewActiveASTContext)4530b57cec5SDimitry Andric   void set_active_ast_context(ASTContext *NewActiveASTContext) {
4540b57cec5SDimitry Andric     ActiveASTContext = NewActiveASTContext;
4550b57cec5SDimitry Andric   }
4560b57cec5SDimitry Andric 
4570b57cec5SDimitry Andric   // The following Visit*() and Traverse*() functions "override"
4580b57cec5SDimitry Andric   // methods in RecursiveASTVisitor.
4590b57cec5SDimitry Andric 
VisitTypedefNameDecl(TypedefNameDecl * DeclNode)4600b57cec5SDimitry Andric   bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
4610b57cec5SDimitry Andric     // When we see 'typedef A B', we add name 'B' to the set of names
4620b57cec5SDimitry Andric     // A's canonical type maps to.  This is necessary for implementing
4630b57cec5SDimitry Andric     // isDerivedFrom(x) properly, where x can be the name of the base
4640b57cec5SDimitry Andric     // class or any of its aliases.
4650b57cec5SDimitry Andric     //
4660b57cec5SDimitry Andric     // In general, the is-alias-of (as defined by typedefs) relation
4670b57cec5SDimitry Andric     // is tree-shaped, as you can typedef a type more than once.  For
4680b57cec5SDimitry Andric     // example,
4690b57cec5SDimitry Andric     //
4700b57cec5SDimitry Andric     //   typedef A B;
4710b57cec5SDimitry Andric     //   typedef A C;
4720b57cec5SDimitry Andric     //   typedef C D;
4730b57cec5SDimitry Andric     //   typedef C E;
4740b57cec5SDimitry Andric     //
4750b57cec5SDimitry Andric     // gives you
4760b57cec5SDimitry Andric     //
4770b57cec5SDimitry Andric     //   A
4780b57cec5SDimitry Andric     //   |- B
4790b57cec5SDimitry Andric     //   `- C
4800b57cec5SDimitry Andric     //      |- D
4810b57cec5SDimitry Andric     //      `- E
4820b57cec5SDimitry Andric     //
4830b57cec5SDimitry Andric     // It is wrong to assume that the relation is a chain.  A correct
4840b57cec5SDimitry Andric     // implementation of isDerivedFrom() needs to recognize that B and
4850b57cec5SDimitry Andric     // E are aliases, even though neither is a typedef of the other.
4860b57cec5SDimitry Andric     // Therefore, we cannot simply walk through one typedef chain to
4870b57cec5SDimitry Andric     // find out whether the type name matches.
4880b57cec5SDimitry Andric     const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
4890b57cec5SDimitry Andric     const Type *CanonicalType =  // root of the typedef tree
4900b57cec5SDimitry Andric         ActiveASTContext->getCanonicalType(TypeNode);
4910b57cec5SDimitry Andric     TypeAliases[CanonicalType].insert(DeclNode);
4920b57cec5SDimitry Andric     return true;
4930b57cec5SDimitry Andric   }
4940b57cec5SDimitry Andric 
VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl * CAD)495a7dea167SDimitry Andric   bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
496a7dea167SDimitry Andric     const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
497a7dea167SDimitry Andric     CompatibleAliases[InterfaceDecl].insert(CAD);
498a7dea167SDimitry Andric     return true;
499a7dea167SDimitry Andric   }
500a7dea167SDimitry Andric 
5010b57cec5SDimitry Andric   bool TraverseDecl(Decl *DeclNode);
5020b57cec5SDimitry Andric   bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
5030b57cec5SDimitry Andric   bool TraverseType(QualType TypeNode);
5040b57cec5SDimitry Andric   bool TraverseTypeLoc(TypeLoc TypeNode);
5050b57cec5SDimitry Andric   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
5060b57cec5SDimitry Andric   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
5070b57cec5SDimitry Andric   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
508e8d8bef9SDimitry Andric   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
509349cc55cSDimitry Andric   bool TraverseAttr(Attr *AttrNode);
510e8d8bef9SDimitry Andric 
dataTraverseNode(Stmt * S,DataRecursionQueue * Queue)511e8d8bef9SDimitry Andric   bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
512e8d8bef9SDimitry Andric     if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
513d409305fSDimitry Andric       {
514d409305fSDimitry Andric         ASTNodeNotAsIsSourceScope RAII(this, true);
515d409305fSDimitry Andric         TraverseStmt(RF->getInit());
516d409305fSDimitry Andric         // Don't traverse under the loop variable
517d409305fSDimitry Andric         match(*RF->getLoopVariable());
518d409305fSDimitry Andric         TraverseStmt(RF->getRangeInit());
519d409305fSDimitry Andric       }
520d409305fSDimitry Andric       {
521e8d8bef9SDimitry Andric         ASTNodeNotSpelledInSourceScope RAII(this, true);
522d409305fSDimitry Andric         for (auto *SubStmt : RF->children()) {
523d409305fSDimitry Andric           if (SubStmt != RF->getBody())
524d409305fSDimitry Andric             TraverseStmt(SubStmt);
525e8d8bef9SDimitry Andric         }
526e8d8bef9SDimitry Andric       }
527d409305fSDimitry Andric       TraverseStmt(RF->getBody());
528e8d8bef9SDimitry Andric       return true;
529e8d8bef9SDimitry Andric     } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
530e8d8bef9SDimitry Andric       {
531e8d8bef9SDimitry Andric         ASTNodeNotAsIsSourceScope RAII(this, true);
532e8d8bef9SDimitry Andric         TraverseStmt(const_cast<Expr *>(RBO->getLHS()));
533e8d8bef9SDimitry Andric         TraverseStmt(const_cast<Expr *>(RBO->getRHS()));
534e8d8bef9SDimitry Andric       }
535e8d8bef9SDimitry Andric       {
536e8d8bef9SDimitry Andric         ASTNodeNotSpelledInSourceScope RAII(this, true);
537e8d8bef9SDimitry Andric         for (auto *SubStmt : RBO->children()) {
538e8d8bef9SDimitry Andric           TraverseStmt(SubStmt);
539e8d8bef9SDimitry Andric         }
540e8d8bef9SDimitry Andric       }
541e8d8bef9SDimitry Andric       return true;
542e8d8bef9SDimitry Andric     } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {
543e8d8bef9SDimitry Andric       for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {
544e8d8bef9SDimitry Andric         auto C = std::get<0>(I);
545e8d8bef9SDimitry Andric         ASTNodeNotSpelledInSourceScope RAII(
546e8d8bef9SDimitry Andric             this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
547e8d8bef9SDimitry Andric         TraverseLambdaCapture(LE, &C, std::get<1>(I));
548e8d8bef9SDimitry Andric       }
549e8d8bef9SDimitry Andric 
550e8d8bef9SDimitry Andric       {
551e8d8bef9SDimitry Andric         ASTNodeNotSpelledInSourceScope RAII(this, true);
552e8d8bef9SDimitry Andric         TraverseDecl(LE->getLambdaClass());
553e8d8bef9SDimitry Andric       }
554e8d8bef9SDimitry Andric       {
555e8d8bef9SDimitry Andric         ASTNodeNotAsIsSourceScope RAII(this, true);
556e8d8bef9SDimitry Andric 
557e8d8bef9SDimitry Andric         // We need to poke around to find the bits that might be explicitly
558e8d8bef9SDimitry Andric         // written.
559e8d8bef9SDimitry Andric         TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
560e8d8bef9SDimitry Andric         FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
561e8d8bef9SDimitry Andric 
562e8d8bef9SDimitry Andric         if (auto *TPL = LE->getTemplateParameterList()) {
563e8d8bef9SDimitry Andric           for (NamedDecl *D : *TPL) {
564e8d8bef9SDimitry Andric             TraverseDecl(D);
565e8d8bef9SDimitry Andric           }
566e8d8bef9SDimitry Andric           if (Expr *RequiresClause = TPL->getRequiresClause()) {
567e8d8bef9SDimitry Andric             TraverseStmt(RequiresClause);
568e8d8bef9SDimitry Andric           }
569e8d8bef9SDimitry Andric         }
570e8d8bef9SDimitry Andric 
571e8d8bef9SDimitry Andric         if (LE->hasExplicitParameters()) {
572e8d8bef9SDimitry Andric           // Visit parameters.
573e8d8bef9SDimitry Andric           for (ParmVarDecl *Param : Proto.getParams())
574e8d8bef9SDimitry Andric             TraverseDecl(Param);
575e8d8bef9SDimitry Andric         }
576e8d8bef9SDimitry Andric 
577e8d8bef9SDimitry Andric         const auto *T = Proto.getTypePtr();
578e8d8bef9SDimitry Andric         for (const auto &E : T->exceptions())
579e8d8bef9SDimitry Andric           TraverseType(E);
580e8d8bef9SDimitry Andric 
581e8d8bef9SDimitry Andric         if (Expr *NE = T->getNoexceptExpr())
582e8d8bef9SDimitry Andric           TraverseStmt(NE, Queue);
583e8d8bef9SDimitry Andric 
584e8d8bef9SDimitry Andric         if (LE->hasExplicitResultType())
585e8d8bef9SDimitry Andric           TraverseTypeLoc(Proto.getReturnLoc());
586e8d8bef9SDimitry Andric         TraverseStmt(LE->getTrailingRequiresClause());
587d409305fSDimitry Andric       }
588e8d8bef9SDimitry Andric 
589e8d8bef9SDimitry Andric       TraverseStmt(LE->getBody());
590e8d8bef9SDimitry Andric       return true;
591e8d8bef9SDimitry Andric     }
592e8d8bef9SDimitry Andric     return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);
593e8d8bef9SDimitry Andric   }
5940b57cec5SDimitry Andric 
5950b57cec5SDimitry Andric   // Matches children or descendants of 'Node' with 'BaseMatcher'.
memoizedMatchesRecursively(const DynTypedNode & Node,ASTContext & Ctx,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,int MaxDepth,BindKind Bind)5965ffd83dbSDimitry Andric   bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
5970b57cec5SDimitry Andric                                   const DynTypedMatcher &Matcher,
5980b57cec5SDimitry Andric                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
599e8d8bef9SDimitry Andric                                   BindKind Bind) {
6000b57cec5SDimitry Andric     // For AST-nodes that don't have an identity, we can't memoize.
6010b57cec5SDimitry Andric     if (!Node.getMemoizationData() || !Builder->isComparable())
602e8d8bef9SDimitry Andric       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
6030b57cec5SDimitry Andric 
6040b57cec5SDimitry Andric     MatchKey Key;
6050b57cec5SDimitry Andric     Key.MatcherID = Matcher.getID();
6060b57cec5SDimitry Andric     Key.Node = Node;
6070b57cec5SDimitry Andric     // Note that we key on the bindings *before* the match.
6080b57cec5SDimitry Andric     Key.BoundNodes = *Builder;
6095ffd83dbSDimitry Andric     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
6105ffd83dbSDimitry Andric     // Memoize result even doing a single-level match, it might be expensive.
6115ffd83dbSDimitry Andric     Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
6120b57cec5SDimitry Andric     MemoizationMap::iterator I = ResultCache.find(Key);
6130b57cec5SDimitry Andric     if (I != ResultCache.end()) {
6140b57cec5SDimitry Andric       *Builder = I->second.Nodes;
6150b57cec5SDimitry Andric       return I->second.ResultOfMatch;
6160b57cec5SDimitry Andric     }
6170b57cec5SDimitry Andric 
6180b57cec5SDimitry Andric     MemoizedMatchResult Result;
6190b57cec5SDimitry Andric     Result.Nodes = *Builder;
620e8d8bef9SDimitry Andric     Result.ResultOfMatch =
621e8d8bef9SDimitry Andric         matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);
6220b57cec5SDimitry Andric 
6230b57cec5SDimitry Andric     MemoizedMatchResult &CachedResult = ResultCache[Key];
6240b57cec5SDimitry Andric     CachedResult = std::move(Result);
6250b57cec5SDimitry Andric 
6260b57cec5SDimitry Andric     *Builder = CachedResult.Nodes;
6270b57cec5SDimitry Andric     return CachedResult.ResultOfMatch;
6280b57cec5SDimitry Andric   }
6290b57cec5SDimitry Andric 
6300b57cec5SDimitry Andric   // Matches children or descendants of 'Node' with 'BaseMatcher'.
matchesRecursively(const DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,int MaxDepth,BindKind Bind)6315ffd83dbSDimitry Andric   bool matchesRecursively(const DynTypedNode &Node,
6320b57cec5SDimitry Andric                           const DynTypedMatcher &Matcher,
6330b57cec5SDimitry Andric                           BoundNodesTreeBuilder *Builder, int MaxDepth,
634e8d8bef9SDimitry Andric                           BindKind Bind) {
635e8d8bef9SDimitry Andric     bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
636e8d8bef9SDimitry Andric                            TraversingASTChildrenNotSpelledInSource;
637e8d8bef9SDimitry Andric 
638e8d8bef9SDimitry Andric     bool IgnoreImplicitChildren = false;
639e8d8bef9SDimitry Andric 
640e8d8bef9SDimitry Andric     if (isTraversalIgnoringImplicitNodes()) {
641e8d8bef9SDimitry Andric       IgnoreImplicitChildren = true;
642e8d8bef9SDimitry Andric     }
643e8d8bef9SDimitry Andric 
644e8d8bef9SDimitry Andric     ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
645e8d8bef9SDimitry Andric 
646e8d8bef9SDimitry Andric     MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
647e8d8bef9SDimitry Andric                                  IgnoreImplicitChildren, Bind);
6480b57cec5SDimitry Andric     return Visitor.findMatch(Node);
6490b57cec5SDimitry Andric   }
6500b57cec5SDimitry Andric 
6510b57cec5SDimitry Andric   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
6520b57cec5SDimitry Andric                           const Matcher<NamedDecl> &Base,
653a7dea167SDimitry Andric                           BoundNodesTreeBuilder *Builder,
654a7dea167SDimitry Andric                           bool Directly) override;
655a7dea167SDimitry Andric 
656*5f757f3fSDimitry Andric private:
657*5f757f3fSDimitry Andric   bool
658*5f757f3fSDimitry Andric   classIsDerivedFromImpl(const CXXRecordDecl *Declaration,
659*5f757f3fSDimitry Andric                          const Matcher<NamedDecl> &Base,
660*5f757f3fSDimitry Andric                          BoundNodesTreeBuilder *Builder, bool Directly,
661*5f757f3fSDimitry Andric                          llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited);
662*5f757f3fSDimitry Andric 
663*5f757f3fSDimitry Andric public:
664a7dea167SDimitry Andric   bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
665a7dea167SDimitry Andric                               const Matcher<NamedDecl> &Base,
666a7dea167SDimitry Andric                               BoundNodesTreeBuilder *Builder,
667a7dea167SDimitry Andric                               bool Directly) override;
6680b57cec5SDimitry Andric 
669*5f757f3fSDimitry Andric public:
6700b57cec5SDimitry Andric   // Implements ASTMatchFinder::matchesChildOf.
matchesChildOf(const DynTypedNode & Node,ASTContext & Ctx,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,BindKind Bind)6715ffd83dbSDimitry Andric   bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
6725ffd83dbSDimitry Andric                       const DynTypedMatcher &Matcher,
673e8d8bef9SDimitry Andric                       BoundNodesTreeBuilder *Builder, BindKind Bind) override {
6740b57cec5SDimitry Andric     if (ResultCache.size() > MaxMemoizationEntries)
6750b57cec5SDimitry Andric       ResultCache.clear();
676e8d8bef9SDimitry Andric     return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);
6770b57cec5SDimitry Andric   }
6780b57cec5SDimitry Andric   // Implements ASTMatchFinder::matchesDescendantOf.
matchesDescendantOf(const DynTypedNode & Node,ASTContext & Ctx,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,BindKind Bind)6795ffd83dbSDimitry Andric   bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
6805ffd83dbSDimitry Andric                            const DynTypedMatcher &Matcher,
6810b57cec5SDimitry Andric                            BoundNodesTreeBuilder *Builder,
6820b57cec5SDimitry Andric                            BindKind Bind) override {
6830b57cec5SDimitry Andric     if (ResultCache.size() > MaxMemoizationEntries)
6840b57cec5SDimitry Andric       ResultCache.clear();
685480093f4SDimitry Andric     return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
686e8d8bef9SDimitry Andric                                       Bind);
6870b57cec5SDimitry Andric   }
6880b57cec5SDimitry Andric   // Implements ASTMatchFinder::matchesAncestorOf.
matchesAncestorOf(const DynTypedNode & Node,ASTContext & Ctx,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,AncestorMatchMode MatchMode)6895ffd83dbSDimitry Andric   bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
6905ffd83dbSDimitry Andric                          const DynTypedMatcher &Matcher,
6910b57cec5SDimitry Andric                          BoundNodesTreeBuilder *Builder,
6920b57cec5SDimitry Andric                          AncestorMatchMode MatchMode) override {
6930b57cec5SDimitry Andric     // Reset the cache outside of the recursive call to make sure we
6940b57cec5SDimitry Andric     // don't invalidate any iterators.
6950b57cec5SDimitry Andric     if (ResultCache.size() > MaxMemoizationEntries)
6960b57cec5SDimitry Andric       ResultCache.clear();
697e8d8bef9SDimitry Andric     if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
698e8d8bef9SDimitry Andric       return matchesParentOf(Node, Matcher, Builder);
699e8d8bef9SDimitry Andric     return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
7000b57cec5SDimitry Andric   }
7010b57cec5SDimitry Andric 
7020b57cec5SDimitry Andric   // Matches all registered matchers on the given node and calls the
7030b57cec5SDimitry Andric   // result callback for every node that matches.
match(const DynTypedNode & Node)7045ffd83dbSDimitry Andric   void match(const DynTypedNode &Node) {
7050b57cec5SDimitry Andric     // FIXME: Improve this with a switch or a visitor pattern.
7060b57cec5SDimitry Andric     if (auto *N = Node.get<Decl>()) {
7070b57cec5SDimitry Andric       match(*N);
7080b57cec5SDimitry Andric     } else if (auto *N = Node.get<Stmt>()) {
7090b57cec5SDimitry Andric       match(*N);
7100b57cec5SDimitry Andric     } else if (auto *N = Node.get<Type>()) {
7110b57cec5SDimitry Andric       match(*N);
7120b57cec5SDimitry Andric     } else if (auto *N = Node.get<QualType>()) {
7130b57cec5SDimitry Andric       match(*N);
7140b57cec5SDimitry Andric     } else if (auto *N = Node.get<NestedNameSpecifier>()) {
7150b57cec5SDimitry Andric       match(*N);
7160b57cec5SDimitry Andric     } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
7170b57cec5SDimitry Andric       match(*N);
7180b57cec5SDimitry Andric     } else if (auto *N = Node.get<TypeLoc>()) {
7190b57cec5SDimitry Andric       match(*N);
7200b57cec5SDimitry Andric     } else if (auto *N = Node.get<CXXCtorInitializer>()) {
7210b57cec5SDimitry Andric       match(*N);
722e8d8bef9SDimitry Andric     } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
723e8d8bef9SDimitry Andric       match(*N);
724349cc55cSDimitry Andric     } else if (auto *N = Node.get<Attr>()) {
725349cc55cSDimitry Andric       match(*N);
7260b57cec5SDimitry Andric     }
7270b57cec5SDimitry Andric   }
7280b57cec5SDimitry Andric 
match(const T & Node)7290b57cec5SDimitry Andric   template <typename T> void match(const T &Node) {
7300b57cec5SDimitry Andric     matchDispatch(&Node);
7310b57cec5SDimitry Andric   }
7320b57cec5SDimitry Andric 
7330b57cec5SDimitry Andric   // Implements ASTMatchFinder::getASTContext.
getASTContext() const7340b57cec5SDimitry Andric   ASTContext &getASTContext() const override { return *ActiveASTContext; }
7350b57cec5SDimitry Andric 
shouldVisitTemplateInstantiations() const7360b57cec5SDimitry Andric   bool shouldVisitTemplateInstantiations() const { return true; }
shouldVisitImplicitCode() const7370b57cec5SDimitry Andric   bool shouldVisitImplicitCode() const { return true; }
7380b57cec5SDimitry Andric 
739d409305fSDimitry Andric   // We visit the lambda body explicitly, so instruct the RAV
740d409305fSDimitry Andric   // to not visit it on our behalf too.
shouldVisitLambdaBody() const741d409305fSDimitry Andric   bool shouldVisitLambdaBody() const { return false; }
742d409305fSDimitry Andric 
IsMatchingInASTNodeNotSpelledInSource() const743e8d8bef9SDimitry Andric   bool IsMatchingInASTNodeNotSpelledInSource() const override {
744e8d8bef9SDimitry Andric     return TraversingASTNodeNotSpelledInSource;
745e8d8bef9SDimitry Andric   }
isMatchingChildrenNotSpelledInSource() const746e8d8bef9SDimitry Andric   bool isMatchingChildrenNotSpelledInSource() const override {
747e8d8bef9SDimitry Andric     return TraversingASTChildrenNotSpelledInSource;
748e8d8bef9SDimitry Andric   }
setMatchingChildrenNotSpelledInSource(bool Set)749e8d8bef9SDimitry Andric   void setMatchingChildrenNotSpelledInSource(bool Set) override {
750e8d8bef9SDimitry Andric     TraversingASTChildrenNotSpelledInSource = Set;
751e8d8bef9SDimitry Andric   }
752e8d8bef9SDimitry Andric 
IsMatchingInASTNodeNotAsIs() const753e8d8bef9SDimitry Andric   bool IsMatchingInASTNodeNotAsIs() const override {
754e8d8bef9SDimitry Andric     return TraversingASTNodeNotAsIs;
755e8d8bef9SDimitry Andric   }
756e8d8bef9SDimitry Andric 
TraverseTemplateInstantiations(ClassTemplateDecl * D)757e8d8bef9SDimitry Andric   bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
758e8d8bef9SDimitry Andric     ASTNodeNotSpelledInSourceScope RAII(this, true);
759e8d8bef9SDimitry Andric     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
760e8d8bef9SDimitry Andric         D);
761e8d8bef9SDimitry Andric   }
762e8d8bef9SDimitry Andric 
TraverseTemplateInstantiations(VarTemplateDecl * D)763e8d8bef9SDimitry Andric   bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
764e8d8bef9SDimitry Andric     ASTNodeNotSpelledInSourceScope RAII(this, true);
765e8d8bef9SDimitry Andric     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
766e8d8bef9SDimitry Andric         D);
767e8d8bef9SDimitry Andric   }
768e8d8bef9SDimitry Andric 
TraverseTemplateInstantiations(FunctionTemplateDecl * D)769e8d8bef9SDimitry Andric   bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
770e8d8bef9SDimitry Andric     ASTNodeNotSpelledInSourceScope RAII(this, true);
771e8d8bef9SDimitry Andric     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
772e8d8bef9SDimitry Andric         D);
773e8d8bef9SDimitry Andric   }
774e8d8bef9SDimitry Andric 
7750b57cec5SDimitry Andric private:
776e8d8bef9SDimitry Andric   bool TraversingASTNodeNotSpelledInSource = false;
777e8d8bef9SDimitry Andric   bool TraversingASTNodeNotAsIs = false;
778e8d8bef9SDimitry Andric   bool TraversingASTChildrenNotSpelledInSource = false;
779e8d8bef9SDimitry Andric 
78081ad6265SDimitry Andric   class CurMatchData {
78181ad6265SDimitry Andric // We don't have enough free low bits in 32bit builds to discriminate 8 pointer
78281ad6265SDimitry Andric // types in PointerUnion. so split the union in 2 using a free bit from the
78381ad6265SDimitry Andric // callback pointer.
78481ad6265SDimitry Andric #define CMD_TYPES_0                                                            \
78581ad6265SDimitry Andric   const QualType *, const TypeLoc *, const NestedNameSpecifier *,              \
78681ad6265SDimitry Andric       const NestedNameSpecifierLoc *
78781ad6265SDimitry Andric #define CMD_TYPES_1                                                            \
78881ad6265SDimitry Andric   const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *,       \
78981ad6265SDimitry Andric       const DynTypedNode *
79081ad6265SDimitry Andric 
79181ad6265SDimitry Andric #define IMPL(Index)                                                            \
79281ad6265SDimitry Andric   template <typename NodeType>                                                 \
793bdd1243dSDimitry Andric   std::enable_if_t<                                                            \
79481ad6265SDimitry Andric       llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value>             \
79581ad6265SDimitry Andric   SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) {          \
79681ad6265SDimitry Andric     assertEmpty();                                                             \
79781ad6265SDimitry Andric     Callback.setPointerAndInt(CB, Index);                                      \
79881ad6265SDimitry Andric     Node##Index = &N;                                                          \
79981ad6265SDimitry Andric   }                                                                            \
80081ad6265SDimitry Andric                                                                                \
80181ad6265SDimitry Andric   template <typename T>                                                        \
802bdd1243dSDimitry Andric   std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value,       \
803bdd1243dSDimitry Andric                    const T *>                                                  \
80481ad6265SDimitry Andric   getNode() const {                                                            \
80581ad6265SDimitry Andric     assertHoldsState();                                                        \
80681ad6265SDimitry Andric     return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>()    \
80781ad6265SDimitry Andric                                         : nullptr;                             \
80881ad6265SDimitry Andric   }
80981ad6265SDimitry Andric 
81081ad6265SDimitry Andric   public:
CurMatchData()81181ad6265SDimitry Andric     CurMatchData() : Node0(nullptr) {}
81281ad6265SDimitry Andric 
81381ad6265SDimitry Andric     IMPL(0)
81481ad6265SDimitry Andric     IMPL(1)
81581ad6265SDimitry Andric 
getCallback() const81681ad6265SDimitry Andric     const MatchCallback *getCallback() const { return Callback.getPointer(); }
81781ad6265SDimitry Andric 
SetBoundNodes(const BoundNodes & BN)81881ad6265SDimitry Andric     void SetBoundNodes(const BoundNodes &BN) {
81981ad6265SDimitry Andric       assertHoldsState();
82081ad6265SDimitry Andric       BNodes = &BN;
82181ad6265SDimitry Andric     }
82281ad6265SDimitry Andric 
clearBoundNodes()82381ad6265SDimitry Andric     void clearBoundNodes() {
82481ad6265SDimitry Andric       assertHoldsState();
82581ad6265SDimitry Andric       BNodes = nullptr;
82681ad6265SDimitry Andric     }
82781ad6265SDimitry Andric 
getBoundNodes() const82881ad6265SDimitry Andric     const BoundNodes *getBoundNodes() const {
82981ad6265SDimitry Andric       assertHoldsState();
83081ad6265SDimitry Andric       return BNodes;
83181ad6265SDimitry Andric     }
83281ad6265SDimitry Andric 
reset()83381ad6265SDimitry Andric     void reset() {
83481ad6265SDimitry Andric       assertHoldsState();
83581ad6265SDimitry Andric       Callback.setPointerAndInt(nullptr, 0);
83681ad6265SDimitry Andric       Node0 = nullptr;
83781ad6265SDimitry Andric     }
83881ad6265SDimitry Andric 
83981ad6265SDimitry Andric   private:
assertHoldsState() const84081ad6265SDimitry Andric     void assertHoldsState() const {
84181ad6265SDimitry Andric       assert(Callback.getPointer() != nullptr && !Node0.isNull());
84281ad6265SDimitry Andric     }
84381ad6265SDimitry Andric 
assertEmpty() const84481ad6265SDimitry Andric     void assertEmpty() const {
84581ad6265SDimitry Andric       assert(Callback.getPointer() == nullptr && Node0.isNull() &&
84681ad6265SDimitry Andric              BNodes == nullptr);
84781ad6265SDimitry Andric     }
84881ad6265SDimitry Andric 
84981ad6265SDimitry Andric     llvm::PointerIntPair<const MatchCallback *, 1> Callback;
85081ad6265SDimitry Andric     union {
85181ad6265SDimitry Andric       llvm::PointerUnion<CMD_TYPES_0> Node0;
85281ad6265SDimitry Andric       llvm::PointerUnion<CMD_TYPES_1> Node1;
85381ad6265SDimitry Andric     };
85481ad6265SDimitry Andric     const BoundNodes *BNodes = nullptr;
85581ad6265SDimitry Andric 
85681ad6265SDimitry Andric #undef CMD_TYPES_0
85781ad6265SDimitry Andric #undef CMD_TYPES_1
85881ad6265SDimitry Andric #undef IMPL
85981ad6265SDimitry Andric   } CurMatchState;
86081ad6265SDimitry Andric 
86181ad6265SDimitry Andric   struct CurMatchRAII {
86281ad6265SDimitry Andric     template <typename NodeType>
CurMatchRAIIclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::CurMatchRAII86381ad6265SDimitry Andric     CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,
86481ad6265SDimitry Andric                  const NodeType &NT)
86581ad6265SDimitry Andric         : MV(MV) {
86681ad6265SDimitry Andric       MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
86781ad6265SDimitry Andric     }
86881ad6265SDimitry Andric 
~CurMatchRAIIclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::CurMatchRAII86981ad6265SDimitry Andric     ~CurMatchRAII() { MV.CurMatchState.reset(); }
87081ad6265SDimitry Andric 
87181ad6265SDimitry Andric   private:
87281ad6265SDimitry Andric     MatchASTVisitor &MV;
87381ad6265SDimitry Andric   };
87481ad6265SDimitry Andric 
87581ad6265SDimitry Andric public:
87681ad6265SDimitry Andric   class TraceReporter : llvm::PrettyStackTraceEntry {
dumpNode(const ASTContext & Ctx,const DynTypedNode & Node,raw_ostream & OS)87781ad6265SDimitry Andric     static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,
87881ad6265SDimitry Andric                          raw_ostream &OS) {
87981ad6265SDimitry Andric       if (const auto *D = Node.get<Decl>()) {
88081ad6265SDimitry Andric         OS << D->getDeclKindName() << "Decl ";
88181ad6265SDimitry Andric         if (const auto *ND = dyn_cast<NamedDecl>(D)) {
88281ad6265SDimitry Andric           ND->printQualifiedName(OS);
88381ad6265SDimitry Andric           OS << " : ";
88481ad6265SDimitry Andric         } else
88581ad6265SDimitry Andric           OS << ": ";
88681ad6265SDimitry Andric         D->getSourceRange().print(OS, Ctx.getSourceManager());
88781ad6265SDimitry Andric       } else if (const auto *S = Node.get<Stmt>()) {
88881ad6265SDimitry Andric         OS << S->getStmtClassName() << " : ";
88981ad6265SDimitry Andric         S->getSourceRange().print(OS, Ctx.getSourceManager());
89081ad6265SDimitry Andric       } else if (const auto *T = Node.get<Type>()) {
89181ad6265SDimitry Andric         OS << T->getTypeClassName() << "Type : ";
89281ad6265SDimitry Andric         QualType(T, 0).print(OS, Ctx.getPrintingPolicy());
89381ad6265SDimitry Andric       } else if (const auto *QT = Node.get<QualType>()) {
89481ad6265SDimitry Andric         OS << "QualType : ";
89581ad6265SDimitry Andric         QT->print(OS, Ctx.getPrintingPolicy());
89681ad6265SDimitry Andric       } else {
89781ad6265SDimitry Andric         OS << Node.getNodeKind().asStringRef() << " : ";
89881ad6265SDimitry Andric         Node.getSourceRange().print(OS, Ctx.getSourceManager());
89981ad6265SDimitry Andric       }
90081ad6265SDimitry Andric     }
90181ad6265SDimitry Andric 
dumpNodeFromState(const ASTContext & Ctx,const CurMatchData & State,raw_ostream & OS)90281ad6265SDimitry Andric     static void dumpNodeFromState(const ASTContext &Ctx,
90381ad6265SDimitry Andric                                   const CurMatchData &State, raw_ostream &OS) {
90481ad6265SDimitry Andric       if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {
90581ad6265SDimitry Andric         dumpNode(Ctx, *MatchNode, OS);
90681ad6265SDimitry Andric       } else if (const auto *QT = State.getNode<QualType>()) {
90781ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*QT), OS);
90881ad6265SDimitry Andric       } else if (const auto *TL = State.getNode<TypeLoc>()) {
90981ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*TL), OS);
91081ad6265SDimitry Andric       } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {
91181ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*NNS), OS);
91281ad6265SDimitry Andric       } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {
91381ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*NNSL), OS);
91481ad6265SDimitry Andric       } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {
91581ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*CtorInit), OS);
91681ad6265SDimitry Andric       } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {
91781ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*TAL), OS);
91881ad6265SDimitry Andric       } else if (const auto *At = State.getNode<Attr>()) {
91981ad6265SDimitry Andric         dumpNode(Ctx, DynTypedNode::create(*At), OS);
92081ad6265SDimitry Andric       }
92181ad6265SDimitry Andric     }
92281ad6265SDimitry Andric 
92381ad6265SDimitry Andric   public:
TraceReporter(const MatchASTVisitor & MV)92481ad6265SDimitry Andric     TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}
print(raw_ostream & OS) const92581ad6265SDimitry Andric     void print(raw_ostream &OS) const override {
92681ad6265SDimitry Andric       const CurMatchData &State = MV.CurMatchState;
92781ad6265SDimitry Andric       const MatchCallback *CB = State.getCallback();
92881ad6265SDimitry Andric       if (!CB) {
92981ad6265SDimitry Andric         OS << "ASTMatcher: Not currently matching\n";
93081ad6265SDimitry Andric         return;
93181ad6265SDimitry Andric       }
93281ad6265SDimitry Andric 
93381ad6265SDimitry Andric       assert(MV.ActiveASTContext &&
93481ad6265SDimitry Andric              "ActiveASTContext should be set if there is a matched callback");
93581ad6265SDimitry Andric 
93681ad6265SDimitry Andric       ASTContext &Ctx = MV.getASTContext();
93781ad6265SDimitry Andric 
93881ad6265SDimitry Andric       if (const BoundNodes *Nodes = State.getBoundNodes()) {
93981ad6265SDimitry Andric         OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";
94081ad6265SDimitry Andric         dumpNodeFromState(Ctx, State, OS);
94181ad6265SDimitry Andric         const BoundNodes::IDToNodeMap &Map = Nodes->getMap();
94281ad6265SDimitry Andric         if (Map.empty()) {
94381ad6265SDimitry Andric           OS << "\nNo bound nodes\n";
94481ad6265SDimitry Andric           return;
94581ad6265SDimitry Andric         }
94681ad6265SDimitry Andric         OS << "\n--- Bound Nodes Begin ---\n";
94781ad6265SDimitry Andric         for (const auto &Item : Map) {
94881ad6265SDimitry Andric           OS << "    " << Item.first << " - { ";
94981ad6265SDimitry Andric           dumpNode(Ctx, Item.second, OS);
95081ad6265SDimitry Andric           OS << " }\n";
95181ad6265SDimitry Andric         }
95281ad6265SDimitry Andric         OS << "--- Bound Nodes End ---\n";
95381ad6265SDimitry Andric       } else {
95481ad6265SDimitry Andric         OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";
95581ad6265SDimitry Andric         dumpNodeFromState(Ctx, State, OS);
95681ad6265SDimitry Andric         OS << '\n';
95781ad6265SDimitry Andric       }
95881ad6265SDimitry Andric     }
95981ad6265SDimitry Andric 
96081ad6265SDimitry Andric   private:
96181ad6265SDimitry Andric     const MatchASTVisitor &MV;
96281ad6265SDimitry Andric   };
96381ad6265SDimitry Andric 
96481ad6265SDimitry Andric private:
965e8d8bef9SDimitry Andric   struct ASTNodeNotSpelledInSourceScope {
ASTNodeNotSpelledInSourceScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::ASTNodeNotSpelledInSourceScope966e8d8bef9SDimitry Andric     ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
967e8d8bef9SDimitry Andric         : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
968e8d8bef9SDimitry Andric       V->TraversingASTNodeNotSpelledInSource = B;
969e8d8bef9SDimitry Andric     }
~ASTNodeNotSpelledInSourceScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::ASTNodeNotSpelledInSourceScope970e8d8bef9SDimitry Andric     ~ASTNodeNotSpelledInSourceScope() {
971e8d8bef9SDimitry Andric       MV->TraversingASTNodeNotSpelledInSource = MB;
972e8d8bef9SDimitry Andric     }
973e8d8bef9SDimitry Andric 
974e8d8bef9SDimitry Andric   private:
975e8d8bef9SDimitry Andric     MatchASTVisitor *MV;
976e8d8bef9SDimitry Andric     bool MB;
977e8d8bef9SDimitry Andric   };
978e8d8bef9SDimitry Andric 
979e8d8bef9SDimitry Andric   struct ASTNodeNotAsIsSourceScope {
ASTNodeNotAsIsSourceScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::ASTNodeNotAsIsSourceScope980e8d8bef9SDimitry Andric     ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
981e8d8bef9SDimitry Andric         : MV(V), MB(V->TraversingASTNodeNotAsIs) {
982e8d8bef9SDimitry Andric       V->TraversingASTNodeNotAsIs = B;
983e8d8bef9SDimitry Andric     }
~ASTNodeNotAsIsSourceScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::ASTNodeNotAsIsSourceScope984e8d8bef9SDimitry Andric     ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
985e8d8bef9SDimitry Andric 
986e8d8bef9SDimitry Andric   private:
987e8d8bef9SDimitry Andric     MatchASTVisitor *MV;
988e8d8bef9SDimitry Andric     bool MB;
989e8d8bef9SDimitry Andric   };
990e8d8bef9SDimitry Andric 
9910b57cec5SDimitry Andric   class TimeBucketRegion {
9920b57cec5SDimitry Andric   public:
993*5f757f3fSDimitry Andric     TimeBucketRegion() = default;
~TimeBucketRegion()9940b57cec5SDimitry Andric     ~TimeBucketRegion() { setBucket(nullptr); }
9950b57cec5SDimitry Andric 
9960b57cec5SDimitry Andric     /// Start timing for \p NewBucket.
9970b57cec5SDimitry Andric     ///
9980b57cec5SDimitry Andric     /// If there was a bucket already set, it will finish the timing for that
9990b57cec5SDimitry Andric     /// other bucket.
10000b57cec5SDimitry Andric     /// \p NewBucket will be timed until the next call to \c setBucket() or
10010b57cec5SDimitry Andric     /// until the \c TimeBucketRegion is destroyed.
10020b57cec5SDimitry Andric     /// If \p NewBucket is the same as the currently timed bucket, this call
10030b57cec5SDimitry Andric     /// does nothing.
setBucket(llvm::TimeRecord * NewBucket)10040b57cec5SDimitry Andric     void setBucket(llvm::TimeRecord *NewBucket) {
10050b57cec5SDimitry Andric       if (Bucket != NewBucket) {
10060b57cec5SDimitry Andric         auto Now = llvm::TimeRecord::getCurrentTime(true);
10070b57cec5SDimitry Andric         if (Bucket)
10080b57cec5SDimitry Andric           *Bucket += Now;
10090b57cec5SDimitry Andric         if (NewBucket)
10100b57cec5SDimitry Andric           *NewBucket -= Now;
10110b57cec5SDimitry Andric         Bucket = NewBucket;
10120b57cec5SDimitry Andric       }
10130b57cec5SDimitry Andric     }
10140b57cec5SDimitry Andric 
10150b57cec5SDimitry Andric   private:
1016*5f757f3fSDimitry Andric     llvm::TimeRecord *Bucket = nullptr;
10170b57cec5SDimitry Andric   };
10180b57cec5SDimitry Andric 
10190b57cec5SDimitry Andric   /// Runs all the \p Matchers on \p Node.
10200b57cec5SDimitry Andric   ///
10210b57cec5SDimitry Andric   /// Used by \c matchDispatch() below.
10220b57cec5SDimitry Andric   template <typename T, typename MC>
matchWithoutFilter(const T & Node,const MC & Matchers)10230b57cec5SDimitry Andric   void matchWithoutFilter(const T &Node, const MC &Matchers) {
102481ad6265SDimitry Andric     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
10250b57cec5SDimitry Andric     TimeBucketRegion Timer;
10260b57cec5SDimitry Andric     for (const auto &MP : Matchers) {
10270b57cec5SDimitry Andric       if (EnableCheckProfiling)
10280b57cec5SDimitry Andric         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
10290b57cec5SDimitry Andric       BoundNodesTreeBuilder Builder;
103081ad6265SDimitry Andric       CurMatchRAII RAII(*this, MP.second, Node);
10310b57cec5SDimitry Andric       if (MP.first.matches(Node, this, &Builder)) {
103281ad6265SDimitry Andric         MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
10330b57cec5SDimitry Andric         Builder.visitMatches(&Visitor);
10340b57cec5SDimitry Andric       }
10350b57cec5SDimitry Andric     }
10360b57cec5SDimitry Andric   }
10370b57cec5SDimitry Andric 
matchWithFilter(const DynTypedNode & DynNode)10385ffd83dbSDimitry Andric   void matchWithFilter(const DynTypedNode &DynNode) {
10390b57cec5SDimitry Andric     auto Kind = DynNode.getNodeKind();
10400b57cec5SDimitry Andric     auto it = MatcherFiltersMap.find(Kind);
10410b57cec5SDimitry Andric     const auto &Filter =
10420b57cec5SDimitry Andric         it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
10430b57cec5SDimitry Andric 
10440b57cec5SDimitry Andric     if (Filter.empty())
10450b57cec5SDimitry Andric       return;
10460b57cec5SDimitry Andric 
104781ad6265SDimitry Andric     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
10480b57cec5SDimitry Andric     TimeBucketRegion Timer;
10490b57cec5SDimitry Andric     auto &Matchers = this->Matchers->DeclOrStmt;
10500b57cec5SDimitry Andric     for (unsigned short I : Filter) {
10510b57cec5SDimitry Andric       auto &MP = Matchers[I];
10520b57cec5SDimitry Andric       if (EnableCheckProfiling)
10530b57cec5SDimitry Andric         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
10540b57cec5SDimitry Andric       BoundNodesTreeBuilder Builder;
1055d409305fSDimitry Andric 
1056d409305fSDimitry Andric       {
1057d409305fSDimitry Andric         TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
1058d409305fSDimitry Andric         if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
1059d409305fSDimitry Andric             DynNode)
1060d409305fSDimitry Andric           continue;
1061d409305fSDimitry Andric       }
1062d409305fSDimitry Andric 
106381ad6265SDimitry Andric       CurMatchRAII RAII(*this, MP.second, DynNode);
1064480093f4SDimitry Andric       if (MP.first.matches(DynNode, this, &Builder)) {
106581ad6265SDimitry Andric         MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
10660b57cec5SDimitry Andric         Builder.visitMatches(&Visitor);
10670b57cec5SDimitry Andric       }
10680b57cec5SDimitry Andric     }
10690b57cec5SDimitry Andric   }
10700b57cec5SDimitry Andric 
getFilterForKind(ASTNodeKind Kind)10715ffd83dbSDimitry Andric   const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
10720b57cec5SDimitry Andric     auto &Filter = MatcherFiltersMap[Kind];
10730b57cec5SDimitry Andric     auto &Matchers = this->Matchers->DeclOrStmt;
10740b57cec5SDimitry Andric     assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
10750b57cec5SDimitry Andric     for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
10760b57cec5SDimitry Andric       if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
10770b57cec5SDimitry Andric         Filter.push_back(I);
10780b57cec5SDimitry Andric       }
10790b57cec5SDimitry Andric     }
10800b57cec5SDimitry Andric     return Filter;
10810b57cec5SDimitry Andric   }
10820b57cec5SDimitry Andric 
10830b57cec5SDimitry Andric   /// @{
10840b57cec5SDimitry Andric   /// Overloads to pair the different node types to their matchers.
matchDispatch(const Decl * Node)10850b57cec5SDimitry Andric   void matchDispatch(const Decl *Node) {
10865ffd83dbSDimitry Andric     return matchWithFilter(DynTypedNode::create(*Node));
10870b57cec5SDimitry Andric   }
matchDispatch(const Stmt * Node)10880b57cec5SDimitry Andric   void matchDispatch(const Stmt *Node) {
10895ffd83dbSDimitry Andric     return matchWithFilter(DynTypedNode::create(*Node));
10900b57cec5SDimitry Andric   }
10910b57cec5SDimitry Andric 
matchDispatch(const Type * Node)10920b57cec5SDimitry Andric   void matchDispatch(const Type *Node) {
10930b57cec5SDimitry Andric     matchWithoutFilter(QualType(Node, 0), Matchers->Type);
10940b57cec5SDimitry Andric   }
matchDispatch(const TypeLoc * Node)10950b57cec5SDimitry Andric   void matchDispatch(const TypeLoc *Node) {
10960b57cec5SDimitry Andric     matchWithoutFilter(*Node, Matchers->TypeLoc);
10970b57cec5SDimitry Andric   }
matchDispatch(const QualType * Node)10980b57cec5SDimitry Andric   void matchDispatch(const QualType *Node) {
10990b57cec5SDimitry Andric     matchWithoutFilter(*Node, Matchers->Type);
11000b57cec5SDimitry Andric   }
matchDispatch(const NestedNameSpecifier * Node)11010b57cec5SDimitry Andric   void matchDispatch(const NestedNameSpecifier *Node) {
11020b57cec5SDimitry Andric     matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
11030b57cec5SDimitry Andric   }
matchDispatch(const NestedNameSpecifierLoc * Node)11040b57cec5SDimitry Andric   void matchDispatch(const NestedNameSpecifierLoc *Node) {
11050b57cec5SDimitry Andric     matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
11060b57cec5SDimitry Andric   }
matchDispatch(const CXXCtorInitializer * Node)11070b57cec5SDimitry Andric   void matchDispatch(const CXXCtorInitializer *Node) {
11080b57cec5SDimitry Andric     matchWithoutFilter(*Node, Matchers->CtorInit);
11090b57cec5SDimitry Andric   }
matchDispatch(const TemplateArgumentLoc * Node)1110e8d8bef9SDimitry Andric   void matchDispatch(const TemplateArgumentLoc *Node) {
1111e8d8bef9SDimitry Andric     matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);
1112e8d8bef9SDimitry Andric   }
matchDispatch(const Attr * Node)1113349cc55cSDimitry Andric   void matchDispatch(const Attr *Node) {
1114349cc55cSDimitry Andric     matchWithoutFilter(*Node, Matchers->Attr);
1115349cc55cSDimitry Andric   }
matchDispatch(const void *)11160b57cec5SDimitry Andric   void matchDispatch(const void *) { /* Do nothing. */ }
11170b57cec5SDimitry Andric   /// @}
11180b57cec5SDimitry Andric 
1119e8d8bef9SDimitry Andric   // Returns whether a direct parent of \p Node matches \p Matcher.
1120e8d8bef9SDimitry Andric   // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
matchesParentOf(const DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder)1121e8d8bef9SDimitry Andric   bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
1122e8d8bef9SDimitry Andric                        BoundNodesTreeBuilder *Builder) {
1123e8d8bef9SDimitry Andric     for (const auto &Parent : ActiveASTContext->getParents(Node)) {
1124e8d8bef9SDimitry Andric       BoundNodesTreeBuilder BuilderCopy = *Builder;
1125e8d8bef9SDimitry Andric       if (Matcher.matches(Parent, this, &BuilderCopy)) {
1126e8d8bef9SDimitry Andric         *Builder = std::move(BuilderCopy);
1127e8d8bef9SDimitry Andric         return true;
1128e8d8bef9SDimitry Andric       }
1129e8d8bef9SDimitry Andric     }
1130e8d8bef9SDimitry Andric     return false;
1131e8d8bef9SDimitry Andric   }
1132e8d8bef9SDimitry Andric 
11330b57cec5SDimitry Andric   // Returns whether an ancestor of \p Node matches \p Matcher.
11340b57cec5SDimitry Andric   //
1135e8d8bef9SDimitry Andric   // The order of matching (which can lead to different nodes being bound in
11360b57cec5SDimitry Andric   // case there are multiple matches) is breadth first search.
11370b57cec5SDimitry Andric   //
11380b57cec5SDimitry Andric   // To allow memoization in the very common case of having deeply nested
11390b57cec5SDimitry Andric   // expressions inside a template function, we first walk up the AST, memoizing
11400b57cec5SDimitry Andric   // the result of the match along the way, as long as there is only a single
11410b57cec5SDimitry Andric   // parent.
11420b57cec5SDimitry Andric   //
11430b57cec5SDimitry Andric   // Once there are multiple parents, the breadth first search order does not
11440b57cec5SDimitry Andric   // allow simple memoization on the ancestors. Thus, we only memoize as long
11450b57cec5SDimitry Andric   // as there is a single parent.
1146e8d8bef9SDimitry Andric   //
1147e8d8bef9SDimitry Andric   // We avoid a recursive implementation to prevent excessive stack use on
1148e8d8bef9SDimitry Andric   // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
matchesAnyAncestorOf(DynTypedNode Node,ASTContext & Ctx,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder)1149e8d8bef9SDimitry Andric   bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
11505ffd83dbSDimitry Andric                             const DynTypedMatcher &Matcher,
1151e8d8bef9SDimitry Andric                             BoundNodesTreeBuilder *Builder) {
11520b57cec5SDimitry Andric 
1153e8d8bef9SDimitry Andric     // Memoization keys that can be updated with the result.
1154e8d8bef9SDimitry Andric     // These are the memoizable nodes in the chain of unique parents, which
1155e8d8bef9SDimitry Andric     // terminates when a node has multiple parents, or matches, or is the root.
1156e8d8bef9SDimitry Andric     std::vector<MatchKey> Keys;
1157e8d8bef9SDimitry Andric     // When returning, update the memoization cache.
1158e8d8bef9SDimitry Andric     auto Finish = [&](bool Matched) {
1159e8d8bef9SDimitry Andric       for (const auto &Key : Keys) {
11600b57cec5SDimitry Andric         MemoizedMatchResult &CachedResult = ResultCache[Key];
1161e8d8bef9SDimitry Andric         CachedResult.ResultOfMatch = Matched;
1162e8d8bef9SDimitry Andric         CachedResult.Nodes = *Builder;
1163e8d8bef9SDimitry Andric       }
1164e8d8bef9SDimitry Andric       return Matched;
1165e8d8bef9SDimitry Andric     };
11660b57cec5SDimitry Andric 
1167e8d8bef9SDimitry Andric     // Loop while there's a single parent and we want to attempt memoization.
1168e8d8bef9SDimitry Andric     DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
1169e8d8bef9SDimitry Andric     for (;;) {
1170e8d8bef9SDimitry Andric       // A cache key only makes sense if memoization is possible.
1171e8d8bef9SDimitry Andric       if (Builder->isComparable()) {
1172e8d8bef9SDimitry Andric         Keys.emplace_back();
1173e8d8bef9SDimitry Andric         Keys.back().MatcherID = Matcher.getID();
1174e8d8bef9SDimitry Andric         Keys.back().Node = Node;
1175e8d8bef9SDimitry Andric         Keys.back().BoundNodes = *Builder;
1176e8d8bef9SDimitry Andric         Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
1177e8d8bef9SDimitry Andric         Keys.back().Type = MatchType::Ancestors;
1178e8d8bef9SDimitry Andric 
1179e8d8bef9SDimitry Andric         // Check the cache.
1180e8d8bef9SDimitry Andric         MemoizationMap::iterator I = ResultCache.find(Keys.back());
1181e8d8bef9SDimitry Andric         if (I != ResultCache.end()) {
1182e8d8bef9SDimitry Andric           Keys.pop_back(); // Don't populate the cache for the matching node!
1183e8d8bef9SDimitry Andric           *Builder = I->second.Nodes;
1184e8d8bef9SDimitry Andric           return Finish(I->second.ResultOfMatch);
1185e8d8bef9SDimitry Andric         }
11860b57cec5SDimitry Andric       }
11870b57cec5SDimitry Andric 
1188e8d8bef9SDimitry Andric       Parents = ActiveASTContext->getParents(Node);
1189e8d8bef9SDimitry Andric       // Either no parents or multiple parents: leave chain+memoize mode and
1190e8d8bef9SDimitry Andric       // enter bfs+forgetful mode.
1191e8d8bef9SDimitry Andric       if (Parents.size() != 1)
1192e8d8bef9SDimitry Andric         break;
1193e8d8bef9SDimitry Andric 
1194e8d8bef9SDimitry Andric       // Check the next parent.
1195e8d8bef9SDimitry Andric       Node = *Parents.begin();
1196e8d8bef9SDimitry Andric       BoundNodesTreeBuilder BuilderCopy = *Builder;
1197e8d8bef9SDimitry Andric       if (Matcher.matches(Node, this, &BuilderCopy)) {
1198e8d8bef9SDimitry Andric         *Builder = std::move(BuilderCopy);
1199e8d8bef9SDimitry Andric         return Finish(true);
1200e8d8bef9SDimitry Andric       }
1201e8d8bef9SDimitry Andric     }
1202e8d8bef9SDimitry Andric     // We reached the end of the chain.
1203e8d8bef9SDimitry Andric 
12040b57cec5SDimitry Andric     if (Parents.empty()) {
12050b57cec5SDimitry Andric       // Nodes may have no parents if:
12060b57cec5SDimitry Andric       //  a) the node is the TranslationUnitDecl
12070b57cec5SDimitry Andric       //  b) we have a limited traversal scope that excludes the parent edges
12080b57cec5SDimitry Andric       //  c) there is a bug in the AST, and the node is not reachable
12090b57cec5SDimitry Andric       // Usually the traversal scope is the whole AST, which precludes b.
12100b57cec5SDimitry Andric       // Bugs are common enough that it's worthwhile asserting when we can.
12110b57cec5SDimitry Andric #ifndef NDEBUG
12120b57cec5SDimitry Andric       if (!Node.get<TranslationUnitDecl>() &&
12130b57cec5SDimitry Andric           /* Traversal scope is full AST if any of the bounds are the TU */
12140b57cec5SDimitry Andric           llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
12150b57cec5SDimitry Andric             return D->getKind() == Decl::TranslationUnit;
12160b57cec5SDimitry Andric           })) {
12170b57cec5SDimitry Andric         llvm::errs() << "Tried to match orphan node:\n";
12185ffd83dbSDimitry Andric         Node.dump(llvm::errs(), *ActiveASTContext);
12190b57cec5SDimitry Andric         llvm_unreachable("Parent map should be complete!");
12200b57cec5SDimitry Andric       }
12210b57cec5SDimitry Andric #endif
12220b57cec5SDimitry Andric     } else {
1223e8d8bef9SDimitry Andric       assert(Parents.size() > 1);
1224e8d8bef9SDimitry Andric       // BFS starting from the parents not yet considered.
1225e8d8bef9SDimitry Andric       // Memoization of newly visited nodes is not possible (but we still update
1226e8d8bef9SDimitry Andric       // results for the elements in the chain we found above).
12275ffd83dbSDimitry Andric       std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1228e8d8bef9SDimitry Andric       llvm::DenseSet<const void *> Visited;
12290b57cec5SDimitry Andric       while (!Queue.empty()) {
12300b57cec5SDimitry Andric         BoundNodesTreeBuilder BuilderCopy = *Builder;
12310b57cec5SDimitry Andric         if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
12320b57cec5SDimitry Andric           *Builder = std::move(BuilderCopy);
1233e8d8bef9SDimitry Andric           return Finish(true);
12340b57cec5SDimitry Andric         }
1235e8d8bef9SDimitry Andric         for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {
12360b57cec5SDimitry Andric           // Make sure we do not visit the same node twice.
12370b57cec5SDimitry Andric           // Otherwise, we'll visit the common ancestors as often as there
12380b57cec5SDimitry Andric           // are splits on the way down.
12390b57cec5SDimitry Andric           if (Visited.insert(Parent.getMemoizationData()).second)
12400b57cec5SDimitry Andric             Queue.push_back(Parent);
12410b57cec5SDimitry Andric         }
12420b57cec5SDimitry Andric         Queue.pop_front();
12430b57cec5SDimitry Andric       }
12440b57cec5SDimitry Andric     }
1245e8d8bef9SDimitry Andric     return Finish(false);
12460b57cec5SDimitry Andric   }
12470b57cec5SDimitry Andric 
12480b57cec5SDimitry Andric   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
12490b57cec5SDimitry Andric   // the aggregated bound nodes for each match.
12500b57cec5SDimitry Andric   class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
125181ad6265SDimitry Andric     struct CurBoundScope {
CurBoundScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::MatchVisitor::CurBoundScope125281ad6265SDimitry Andric       CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)
125381ad6265SDimitry Andric           : State(State) {
125481ad6265SDimitry Andric         State.SetBoundNodes(BN);
125581ad6265SDimitry Andric       }
125681ad6265SDimitry Andric 
~CurBoundScopeclang::ast_matchers::internal::__anonbe2d60470111::MatchASTVisitor::MatchVisitor::CurBoundScope125781ad6265SDimitry Andric       ~CurBoundScope() { State.clearBoundNodes(); }
125881ad6265SDimitry Andric 
125981ad6265SDimitry Andric     private:
126081ad6265SDimitry Andric       MatchASTVisitor::CurMatchData &State;
126181ad6265SDimitry Andric     };
126281ad6265SDimitry Andric 
12630b57cec5SDimitry Andric   public:
MatchVisitor(MatchASTVisitor & MV,ASTContext * Context,MatchFinder::MatchCallback * Callback)126481ad6265SDimitry Andric     MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
12650b57cec5SDimitry Andric                  MatchFinder::MatchCallback *Callback)
126681ad6265SDimitry Andric         : State(MV.CurMatchState), Context(Context), Callback(Callback) {}
12670b57cec5SDimitry Andric 
visitMatch(const BoundNodes & BoundNodesView)12680b57cec5SDimitry Andric     void visitMatch(const BoundNodes& BoundNodesView) override {
1269fe6060f1SDimitry Andric       TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
127081ad6265SDimitry Andric       CurBoundScope RAII2(State, BoundNodesView);
12710b57cec5SDimitry Andric       Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
12720b57cec5SDimitry Andric     }
12730b57cec5SDimitry Andric 
12740b57cec5SDimitry Andric   private:
127581ad6265SDimitry Andric     MatchASTVisitor::CurMatchData &State;
12760b57cec5SDimitry Andric     ASTContext* Context;
12770b57cec5SDimitry Andric     MatchFinder::MatchCallback* Callback;
12780b57cec5SDimitry Andric   };
12790b57cec5SDimitry Andric 
12800b57cec5SDimitry Andric   // Returns true if 'TypeNode' has an alias that matches the given matcher.
typeHasMatchingAlias(const Type * TypeNode,const Matcher<NamedDecl> & Matcher,BoundNodesTreeBuilder * Builder)12810b57cec5SDimitry Andric   bool typeHasMatchingAlias(const Type *TypeNode,
12820b57cec5SDimitry Andric                             const Matcher<NamedDecl> &Matcher,
12830b57cec5SDimitry Andric                             BoundNodesTreeBuilder *Builder) {
12840b57cec5SDimitry Andric     const Type *const CanonicalType =
12850b57cec5SDimitry Andric       ActiveASTContext->getCanonicalType(TypeNode);
12860b57cec5SDimitry Andric     auto Aliases = TypeAliases.find(CanonicalType);
12870b57cec5SDimitry Andric     if (Aliases == TypeAliases.end())
12880b57cec5SDimitry Andric       return false;
12890b57cec5SDimitry Andric     for (const TypedefNameDecl *Alias : Aliases->second) {
12900b57cec5SDimitry Andric       BoundNodesTreeBuilder Result(*Builder);
12910b57cec5SDimitry Andric       if (Matcher.matches(*Alias, this, &Result)) {
12920b57cec5SDimitry Andric         *Builder = std::move(Result);
12930b57cec5SDimitry Andric         return true;
12940b57cec5SDimitry Andric       }
12950b57cec5SDimitry Andric     }
12960b57cec5SDimitry Andric     return false;
12970b57cec5SDimitry Andric   }
12980b57cec5SDimitry Andric 
1299a7dea167SDimitry Andric   bool
objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl * InterfaceDecl,const Matcher<NamedDecl> & Matcher,BoundNodesTreeBuilder * Builder)1300a7dea167SDimitry Andric   objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
1301a7dea167SDimitry Andric                                          const Matcher<NamedDecl> &Matcher,
1302a7dea167SDimitry Andric                                          BoundNodesTreeBuilder *Builder) {
1303a7dea167SDimitry Andric     auto Aliases = CompatibleAliases.find(InterfaceDecl);
1304a7dea167SDimitry Andric     if (Aliases == CompatibleAliases.end())
1305a7dea167SDimitry Andric       return false;
1306a7dea167SDimitry Andric     for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1307a7dea167SDimitry Andric       BoundNodesTreeBuilder Result(*Builder);
1308a7dea167SDimitry Andric       if (Matcher.matches(*Alias, this, &Result)) {
1309a7dea167SDimitry Andric         *Builder = std::move(Result);
1310a7dea167SDimitry Andric         return true;
1311a7dea167SDimitry Andric       }
1312a7dea167SDimitry Andric     }
1313a7dea167SDimitry Andric     return false;
1314a7dea167SDimitry Andric   }
1315a7dea167SDimitry Andric 
13160b57cec5SDimitry Andric   /// Bucket to record map.
13170b57cec5SDimitry Andric   ///
13180b57cec5SDimitry Andric   /// Used to get the appropriate bucket for each matcher.
13190b57cec5SDimitry Andric   llvm::StringMap<llvm::TimeRecord> TimeByBucket;
13200b57cec5SDimitry Andric 
13210b57cec5SDimitry Andric   const MatchFinder::MatchersByType *Matchers;
13220b57cec5SDimitry Andric 
13230b57cec5SDimitry Andric   /// Filtered list of matcher indices for each matcher kind.
13240b57cec5SDimitry Andric   ///
13250b57cec5SDimitry Andric   /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
13260b57cec5SDimitry Andric   /// kind (and derived kinds) so it is a waste to try every matcher on every
13270b57cec5SDimitry Andric   /// node.
13280b57cec5SDimitry Andric   /// We precalculate a list of matchers that pass the toplevel restrict check.
13295ffd83dbSDimitry Andric   llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
13300b57cec5SDimitry Andric 
13310b57cec5SDimitry Andric   const MatchFinder::MatchFinderOptions &Options;
13320b57cec5SDimitry Andric   ASTContext *ActiveASTContext;
13330b57cec5SDimitry Andric 
13340b57cec5SDimitry Andric   // Maps a canonical type to its TypedefDecls.
13350b57cec5SDimitry Andric   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
13360b57cec5SDimitry Andric 
1337a7dea167SDimitry Andric   // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
1338a7dea167SDimitry Andric   llvm::DenseMap<const ObjCInterfaceDecl *,
1339a7dea167SDimitry Andric                  llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
1340a7dea167SDimitry Andric       CompatibleAliases;
1341a7dea167SDimitry Andric 
13420b57cec5SDimitry Andric   // Maps (matcher, node) -> the match result for memoization.
13430b57cec5SDimitry Andric   typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
13440b57cec5SDimitry Andric   MemoizationMap ResultCache;
13450b57cec5SDimitry Andric };
13460b57cec5SDimitry Andric 
13470b57cec5SDimitry Andric static CXXRecordDecl *
getAsCXXRecordDeclOrPrimaryTemplate(const Type * TypeNode)13480b57cec5SDimitry Andric getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
13490b57cec5SDimitry Andric   if (auto *RD = TypeNode->getAsCXXRecordDecl())
13500b57cec5SDimitry Andric     return RD;
13510b57cec5SDimitry Andric 
13520b57cec5SDimitry Andric   // Find the innermost TemplateSpecializationType that isn't an alias template.
13530b57cec5SDimitry Andric   auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
13540b57cec5SDimitry Andric   while (TemplateType && TemplateType->isTypeAlias())
13550b57cec5SDimitry Andric     TemplateType =
13560b57cec5SDimitry Andric         TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
13570b57cec5SDimitry Andric 
13580b57cec5SDimitry Andric   // If this is the name of a (dependent) template specialization, use the
13590b57cec5SDimitry Andric   // definition of the template, even though it might be specialized later.
13600b57cec5SDimitry Andric   if (TemplateType)
13610b57cec5SDimitry Andric     if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
13620b57cec5SDimitry Andric           TemplateType->getTemplateName().getAsTemplateDecl()))
13630b57cec5SDimitry Andric       return ClassTemplate->getTemplatedDecl();
13640b57cec5SDimitry Andric 
13650b57cec5SDimitry Andric   return nullptr;
13660b57cec5SDimitry Andric }
13670b57cec5SDimitry Andric 
1368a7dea167SDimitry Andric // Returns true if the given C++ class is directly or indirectly derived
13690b57cec5SDimitry Andric // from a base type with the given name.  A class is not considered to be
13700b57cec5SDimitry Andric // derived from itself.
classIsDerivedFrom(const CXXRecordDecl * Declaration,const Matcher<NamedDecl> & Base,BoundNodesTreeBuilder * Builder,bool Directly)13710b57cec5SDimitry Andric bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
13720b57cec5SDimitry Andric                                          const Matcher<NamedDecl> &Base,
1373a7dea167SDimitry Andric                                          BoundNodesTreeBuilder *Builder,
1374a7dea167SDimitry Andric                                          bool Directly) {
1375*5f757f3fSDimitry Andric   llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;
1376*5f757f3fSDimitry Andric   return classIsDerivedFromImpl(Declaration, Base, Builder, Directly, Visited);
1377*5f757f3fSDimitry Andric }
1378*5f757f3fSDimitry Andric 
classIsDerivedFromImpl(const CXXRecordDecl * Declaration,const Matcher<NamedDecl> & Base,BoundNodesTreeBuilder * Builder,bool Directly,llvm::SmallPtrSetImpl<const CXXRecordDecl * > & Visited)1379*5f757f3fSDimitry Andric bool MatchASTVisitor::classIsDerivedFromImpl(
1380*5f757f3fSDimitry Andric     const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,
1381*5f757f3fSDimitry Andric     BoundNodesTreeBuilder *Builder, bool Directly,
1382*5f757f3fSDimitry Andric     llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) {
13830b57cec5SDimitry Andric   if (!Declaration->hasDefinition())
13840b57cec5SDimitry Andric     return false;
1385*5f757f3fSDimitry Andric   if (!Visited.insert(Declaration).second)
1386*5f757f3fSDimitry Andric     return false;
13870b57cec5SDimitry Andric   for (const auto &It : Declaration->bases()) {
13880b57cec5SDimitry Andric     const Type *TypeNode = It.getType().getTypePtr();
13890b57cec5SDimitry Andric 
13900b57cec5SDimitry Andric     if (typeHasMatchingAlias(TypeNode, Base, Builder))
13910b57cec5SDimitry Andric       return true;
13920b57cec5SDimitry Andric 
13930b57cec5SDimitry Andric     // FIXME: Going to the primary template here isn't really correct, but
13940b57cec5SDimitry Andric     // unfortunately we accept a Decl matcher for the base class not a Type
13950b57cec5SDimitry Andric     // matcher, so it's the best thing we can do with our current interface.
13960b57cec5SDimitry Andric     CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
13970b57cec5SDimitry Andric     if (!ClassDecl)
13980b57cec5SDimitry Andric       continue;
13990b57cec5SDimitry Andric     if (ClassDecl == Declaration) {
14005ffd83dbSDimitry Andric       // This can happen for recursive template definitions.
14015ffd83dbSDimitry Andric       continue;
14020b57cec5SDimitry Andric     }
14030b57cec5SDimitry Andric     BoundNodesTreeBuilder Result(*Builder);
14040b57cec5SDimitry Andric     if (Base.matches(*ClassDecl, this, &Result)) {
14050b57cec5SDimitry Andric       *Builder = std::move(Result);
14060b57cec5SDimitry Andric       return true;
14070b57cec5SDimitry Andric     }
1408*5f757f3fSDimitry Andric     if (!Directly &&
1409*5f757f3fSDimitry Andric         classIsDerivedFromImpl(ClassDecl, Base, Builder, Directly, Visited))
14100b57cec5SDimitry Andric       return true;
14110b57cec5SDimitry Andric   }
14120b57cec5SDimitry Andric   return false;
14130b57cec5SDimitry Andric }
14140b57cec5SDimitry Andric 
1415a7dea167SDimitry Andric // Returns true if the given Objective-C class is directly or indirectly
1416a7dea167SDimitry Andric // derived from a matching base class. A class is not considered to be derived
1417a7dea167SDimitry Andric // from itself.
objcClassIsDerivedFrom(const ObjCInterfaceDecl * Declaration,const Matcher<NamedDecl> & Base,BoundNodesTreeBuilder * Builder,bool Directly)1418a7dea167SDimitry Andric bool MatchASTVisitor::objcClassIsDerivedFrom(
1419a7dea167SDimitry Andric     const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1420a7dea167SDimitry Andric     BoundNodesTreeBuilder *Builder, bool Directly) {
1421a7dea167SDimitry Andric   // Check if any of the superclasses of the class match.
1422a7dea167SDimitry Andric   for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1423a7dea167SDimitry Andric        ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1424a7dea167SDimitry Andric     // Check if there are any matching compatibility aliases.
1425a7dea167SDimitry Andric     if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
1426a7dea167SDimitry Andric       return true;
1427a7dea167SDimitry Andric 
1428a7dea167SDimitry Andric     // Check if there are any matching type aliases.
1429a7dea167SDimitry Andric     const Type *TypeNode = ClassDecl->getTypeForDecl();
1430a7dea167SDimitry Andric     if (typeHasMatchingAlias(TypeNode, Base, Builder))
1431a7dea167SDimitry Andric       return true;
1432a7dea167SDimitry Andric 
1433a7dea167SDimitry Andric     if (Base.matches(*ClassDecl, this, Builder))
1434a7dea167SDimitry Andric       return true;
1435a7dea167SDimitry Andric 
1436480093f4SDimitry Andric     // Not `return false` as a temporary workaround for PR43879.
1437a7dea167SDimitry Andric     if (Directly)
1438480093f4SDimitry Andric       break;
1439a7dea167SDimitry Andric   }
1440a7dea167SDimitry Andric 
1441a7dea167SDimitry Andric   return false;
1442a7dea167SDimitry Andric }
1443a7dea167SDimitry Andric 
TraverseDecl(Decl * DeclNode)14440b57cec5SDimitry Andric bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
14450b57cec5SDimitry Andric   if (!DeclNode) {
14460b57cec5SDimitry Andric     return true;
14470b57cec5SDimitry Andric   }
1448e8d8bef9SDimitry Andric 
1449e8d8bef9SDimitry Andric   bool ScopedTraversal =
1450e8d8bef9SDimitry Andric       TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1451e8d8bef9SDimitry Andric   bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1452e8d8bef9SDimitry Andric 
1453e8d8bef9SDimitry Andric   if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1454e8d8bef9SDimitry Andric     auto SK = CTSD->getSpecializationKind();
1455e8d8bef9SDimitry Andric     if (SK == TSK_ExplicitInstantiationDeclaration ||
1456e8d8bef9SDimitry Andric         SK == TSK_ExplicitInstantiationDefinition)
1457e8d8bef9SDimitry Andric       ScopedChildren = true;
1458e8d8bef9SDimitry Andric   } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1459e8d8bef9SDimitry Andric     if (FD->isDefaulted())
1460e8d8bef9SDimitry Andric       ScopedChildren = true;
1461e8d8bef9SDimitry Andric     if (FD->isTemplateInstantiation())
1462e8d8bef9SDimitry Andric       ScopedTraversal = true;
1463fe6060f1SDimitry Andric   } else if (isa<BindingDecl>(DeclNode)) {
1464fe6060f1SDimitry Andric     ScopedChildren = true;
1465e8d8bef9SDimitry Andric   }
1466e8d8bef9SDimitry Andric 
1467e8d8bef9SDimitry Andric   ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1468e8d8bef9SDimitry Andric   ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
1469e8d8bef9SDimitry Andric 
14700b57cec5SDimitry Andric   match(*DeclNode);
14710b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
14720b57cec5SDimitry Andric }
14730b57cec5SDimitry Andric 
TraverseStmt(Stmt * StmtNode,DataRecursionQueue * Queue)14740b57cec5SDimitry Andric bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
14750b57cec5SDimitry Andric   if (!StmtNode) {
14760b57cec5SDimitry Andric     return true;
14770b57cec5SDimitry Andric   }
1478e8d8bef9SDimitry Andric   bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1479e8d8bef9SDimitry Andric                          TraversingASTChildrenNotSpelledInSource;
1480e8d8bef9SDimitry Andric 
1481e8d8bef9SDimitry Andric   ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
14820b57cec5SDimitry Andric   match(*StmtNode);
14830b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue);
14840b57cec5SDimitry Andric }
14850b57cec5SDimitry Andric 
TraverseType(QualType TypeNode)14860b57cec5SDimitry Andric bool MatchASTVisitor::TraverseType(QualType TypeNode) {
14870b57cec5SDimitry Andric   match(TypeNode);
14880b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
14890b57cec5SDimitry Andric }
14900b57cec5SDimitry Andric 
TraverseTypeLoc(TypeLoc TypeLocNode)14910b57cec5SDimitry Andric bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
14920b57cec5SDimitry Andric   // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
14930b57cec5SDimitry Andric   // We still want to find those types via matchers, so we match them here. Note
14940b57cec5SDimitry Andric   // that the TypeLocs are structurally a shadow-hierarchy to the expressed
14950b57cec5SDimitry Andric   // type, so we visit all involved parts of a compound type when matching on
14960b57cec5SDimitry Andric   // each TypeLoc.
14970b57cec5SDimitry Andric   match(TypeLocNode);
14980b57cec5SDimitry Andric   match(TypeLocNode.getType());
14990b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
15000b57cec5SDimitry Andric }
15010b57cec5SDimitry Andric 
TraverseNestedNameSpecifier(NestedNameSpecifier * NNS)15020b57cec5SDimitry Andric bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
15030b57cec5SDimitry Andric   match(*NNS);
15040b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
15050b57cec5SDimitry Andric }
15060b57cec5SDimitry Andric 
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)15070b57cec5SDimitry Andric bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
15080b57cec5SDimitry Andric     NestedNameSpecifierLoc NNS) {
15090b57cec5SDimitry Andric   if (!NNS)
15100b57cec5SDimitry Andric     return true;
15110b57cec5SDimitry Andric 
15120b57cec5SDimitry Andric   match(NNS);
15130b57cec5SDimitry Andric 
15140b57cec5SDimitry Andric   // We only match the nested name specifier here (as opposed to traversing it)
15150b57cec5SDimitry Andric   // because the traversal is already done in the parallel "Loc"-hierarchy.
15160b57cec5SDimitry Andric   if (NNS.hasQualifier())
15170b57cec5SDimitry Andric     match(*NNS.getNestedNameSpecifier());
15180b57cec5SDimitry Andric   return
15190b57cec5SDimitry Andric       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
15200b57cec5SDimitry Andric }
15210b57cec5SDimitry Andric 
TraverseConstructorInitializer(CXXCtorInitializer * CtorInit)15220b57cec5SDimitry Andric bool MatchASTVisitor::TraverseConstructorInitializer(
15230b57cec5SDimitry Andric     CXXCtorInitializer *CtorInit) {
15240b57cec5SDimitry Andric   if (!CtorInit)
15250b57cec5SDimitry Andric     return true;
15260b57cec5SDimitry Andric 
1527e8d8bef9SDimitry Andric   bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1528e8d8bef9SDimitry Andric                          TraversingASTChildrenNotSpelledInSource;
1529e8d8bef9SDimitry Andric 
1530e8d8bef9SDimitry Andric   if (!CtorInit->isWritten())
1531e8d8bef9SDimitry Andric     ScopedTraversal = true;
1532e8d8bef9SDimitry Andric 
1533e8d8bef9SDimitry Andric   ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1534e8d8bef9SDimitry Andric 
15350b57cec5SDimitry Andric   match(*CtorInit);
15360b57cec5SDimitry Andric 
15370b57cec5SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
15380b57cec5SDimitry Andric       CtorInit);
15390b57cec5SDimitry Andric }
15400b57cec5SDimitry Andric 
TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc)1541e8d8bef9SDimitry Andric bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1542e8d8bef9SDimitry Andric   match(Loc);
1543e8d8bef9SDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(Loc);
1544e8d8bef9SDimitry Andric }
1545e8d8bef9SDimitry Andric 
TraverseAttr(Attr * AttrNode)1546349cc55cSDimitry Andric bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1547349cc55cSDimitry Andric   match(*AttrNode);
1548349cc55cSDimitry Andric   return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(AttrNode);
1549349cc55cSDimitry Andric }
1550349cc55cSDimitry Andric 
15510b57cec5SDimitry Andric class MatchASTConsumer : public ASTConsumer {
15520b57cec5SDimitry Andric public:
MatchASTConsumer(MatchFinder * Finder,MatchFinder::ParsingDoneTestCallback * ParsingDone)15530b57cec5SDimitry Andric   MatchASTConsumer(MatchFinder *Finder,
15540b57cec5SDimitry Andric                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
15550b57cec5SDimitry Andric       : Finder(Finder), ParsingDone(ParsingDone) {}
15560b57cec5SDimitry Andric 
15570b57cec5SDimitry Andric private:
HandleTranslationUnit(ASTContext & Context)15580b57cec5SDimitry Andric   void HandleTranslationUnit(ASTContext &Context) override {
15590b57cec5SDimitry Andric     if (ParsingDone != nullptr) {
15600b57cec5SDimitry Andric       ParsingDone->run();
15610b57cec5SDimitry Andric     }
15620b57cec5SDimitry Andric     Finder->matchAST(Context);
15630b57cec5SDimitry Andric   }
15640b57cec5SDimitry Andric 
15650b57cec5SDimitry Andric   MatchFinder *Finder;
15660b57cec5SDimitry Andric   MatchFinder::ParsingDoneTestCallback *ParsingDone;
15670b57cec5SDimitry Andric };
15680b57cec5SDimitry Andric 
15690b57cec5SDimitry Andric } // end namespace
15700b57cec5SDimitry Andric } // end namespace internal
15710b57cec5SDimitry Andric 
MatchResult(const BoundNodes & Nodes,ASTContext * Context)15720b57cec5SDimitry Andric MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
15730b57cec5SDimitry Andric                                       ASTContext *Context)
15740b57cec5SDimitry Andric   : Nodes(Nodes), Context(Context),
15750b57cec5SDimitry Andric     SourceManager(&Context->getSourceManager()) {}
15760b57cec5SDimitry Andric 
~MatchCallback()15770b57cec5SDimitry Andric MatchFinder::MatchCallback::~MatchCallback() {}
~ParsingDoneTestCallback()15780b57cec5SDimitry Andric MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
15790b57cec5SDimitry Andric 
MatchFinder(MatchFinderOptions Options)15800b57cec5SDimitry Andric MatchFinder::MatchFinder(MatchFinderOptions Options)
15810b57cec5SDimitry Andric     : Options(std::move(Options)), ParsingDone(nullptr) {}
15820b57cec5SDimitry Andric 
~MatchFinder()15830b57cec5SDimitry Andric MatchFinder::~MatchFinder() {}
15840b57cec5SDimitry Andric 
addMatcher(const DeclarationMatcher & NodeMatch,MatchCallback * Action)15850b57cec5SDimitry Andric void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
15860b57cec5SDimitry Andric                              MatchCallback *Action) {
1587bdd1243dSDimitry Andric   std::optional<TraversalKind> TK;
1588fe6060f1SDimitry Andric   if (Action)
1589fe6060f1SDimitry Andric     TK = Action->getCheckTraversalKind();
1590fe6060f1SDimitry Andric   if (TK)
1591fe6060f1SDimitry Andric     Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1592fe6060f1SDimitry Andric   else
15930b57cec5SDimitry Andric     Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
15940b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
15950b57cec5SDimitry Andric }
15960b57cec5SDimitry Andric 
addMatcher(const TypeMatcher & NodeMatch,MatchCallback * Action)15970b57cec5SDimitry Andric void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
15980b57cec5SDimitry Andric                              MatchCallback *Action) {
15990b57cec5SDimitry Andric   Matchers.Type.emplace_back(NodeMatch, Action);
16000b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16010b57cec5SDimitry Andric }
16020b57cec5SDimitry Andric 
addMatcher(const StatementMatcher & NodeMatch,MatchCallback * Action)16030b57cec5SDimitry Andric void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
16040b57cec5SDimitry Andric                              MatchCallback *Action) {
1605bdd1243dSDimitry Andric   std::optional<TraversalKind> TK;
1606fe6060f1SDimitry Andric   if (Action)
1607fe6060f1SDimitry Andric     TK = Action->getCheckTraversalKind();
1608fe6060f1SDimitry Andric   if (TK)
1609fe6060f1SDimitry Andric     Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1610fe6060f1SDimitry Andric   else
16110b57cec5SDimitry Andric     Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
16120b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16130b57cec5SDimitry Andric }
16140b57cec5SDimitry Andric 
addMatcher(const NestedNameSpecifierMatcher & NodeMatch,MatchCallback * Action)16150b57cec5SDimitry Andric void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
16160b57cec5SDimitry Andric                              MatchCallback *Action) {
16170b57cec5SDimitry Andric   Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
16180b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16190b57cec5SDimitry Andric }
16200b57cec5SDimitry Andric 
addMatcher(const NestedNameSpecifierLocMatcher & NodeMatch,MatchCallback * Action)16210b57cec5SDimitry Andric void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
16220b57cec5SDimitry Andric                              MatchCallback *Action) {
16230b57cec5SDimitry Andric   Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
16240b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16250b57cec5SDimitry Andric }
16260b57cec5SDimitry Andric 
addMatcher(const TypeLocMatcher & NodeMatch,MatchCallback * Action)16270b57cec5SDimitry Andric void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
16280b57cec5SDimitry Andric                              MatchCallback *Action) {
16290b57cec5SDimitry Andric   Matchers.TypeLoc.emplace_back(NodeMatch, Action);
16300b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16310b57cec5SDimitry Andric }
16320b57cec5SDimitry Andric 
addMatcher(const CXXCtorInitializerMatcher & NodeMatch,MatchCallback * Action)16330b57cec5SDimitry Andric void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
16340b57cec5SDimitry Andric                              MatchCallback *Action) {
16350b57cec5SDimitry Andric   Matchers.CtorInit.emplace_back(NodeMatch, Action);
16360b57cec5SDimitry Andric   Matchers.AllCallbacks.insert(Action);
16370b57cec5SDimitry Andric }
16380b57cec5SDimitry Andric 
addMatcher(const TemplateArgumentLocMatcher & NodeMatch,MatchCallback * Action)1639e8d8bef9SDimitry Andric void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
1640e8d8bef9SDimitry Andric                              MatchCallback *Action) {
1641e8d8bef9SDimitry Andric   Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1642e8d8bef9SDimitry Andric   Matchers.AllCallbacks.insert(Action);
1643e8d8bef9SDimitry Andric }
1644e8d8bef9SDimitry Andric 
addMatcher(const AttrMatcher & AttrMatch,MatchCallback * Action)1645349cc55cSDimitry Andric void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
1646349cc55cSDimitry Andric                              MatchCallback *Action) {
1647349cc55cSDimitry Andric   Matchers.Attr.emplace_back(AttrMatch, Action);
1648349cc55cSDimitry Andric   Matchers.AllCallbacks.insert(Action);
1649349cc55cSDimitry Andric }
1650349cc55cSDimitry Andric 
addDynamicMatcher(const internal::DynTypedMatcher & NodeMatch,MatchCallback * Action)16510b57cec5SDimitry Andric bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
16520b57cec5SDimitry Andric                                     MatchCallback *Action) {
16530b57cec5SDimitry Andric   if (NodeMatch.canConvertTo<Decl>()) {
16540b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<Decl>(), Action);
16550b57cec5SDimitry Andric     return true;
16560b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<QualType>()) {
16570b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<QualType>(), Action);
16580b57cec5SDimitry Andric     return true;
16590b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<Stmt>()) {
16600b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<Stmt>(), Action);
16610b57cec5SDimitry Andric     return true;
16620b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
16630b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
16640b57cec5SDimitry Andric     return true;
16650b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
16660b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
16670b57cec5SDimitry Andric     return true;
16680b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<TypeLoc>()) {
16690b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
16700b57cec5SDimitry Andric     return true;
16710b57cec5SDimitry Andric   } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
16720b57cec5SDimitry Andric     addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
16730b57cec5SDimitry Andric     return true;
1674e8d8bef9SDimitry Andric   } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1675e8d8bef9SDimitry Andric     addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1676e8d8bef9SDimitry Andric     return true;
1677349cc55cSDimitry Andric   } else if (NodeMatch.canConvertTo<Attr>()) {
1678349cc55cSDimitry Andric     addMatcher(NodeMatch.convertTo<Attr>(), Action);
1679349cc55cSDimitry Andric     return true;
16800b57cec5SDimitry Andric   }
16810b57cec5SDimitry Andric   return false;
16820b57cec5SDimitry Andric }
16830b57cec5SDimitry Andric 
newASTConsumer()16840b57cec5SDimitry Andric std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1685a7dea167SDimitry Andric   return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
16860b57cec5SDimitry Andric }
16870b57cec5SDimitry Andric 
match(const clang::DynTypedNode & Node,ASTContext & Context)16885ffd83dbSDimitry Andric void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
16890b57cec5SDimitry Andric   internal::MatchASTVisitor Visitor(&Matchers, Options);
16900b57cec5SDimitry Andric   Visitor.set_active_ast_context(&Context);
16910b57cec5SDimitry Andric   Visitor.match(Node);
16920b57cec5SDimitry Andric }
16930b57cec5SDimitry Andric 
matchAST(ASTContext & Context)16940b57cec5SDimitry Andric void MatchFinder::matchAST(ASTContext &Context) {
16950b57cec5SDimitry Andric   internal::MatchASTVisitor Visitor(&Matchers, Options);
169681ad6265SDimitry Andric   internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
16970b57cec5SDimitry Andric   Visitor.set_active_ast_context(&Context);
16980b57cec5SDimitry Andric   Visitor.onStartOfTranslationUnit();
16990b57cec5SDimitry Andric   Visitor.TraverseAST(Context);
17000b57cec5SDimitry Andric   Visitor.onEndOfTranslationUnit();
17010b57cec5SDimitry Andric }
17020b57cec5SDimitry Andric 
registerTestCallbackAfterParsing(MatchFinder::ParsingDoneTestCallback * NewParsingDone)17030b57cec5SDimitry Andric void MatchFinder::registerTestCallbackAfterParsing(
17040b57cec5SDimitry Andric     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
17050b57cec5SDimitry Andric   ParsingDone = NewParsingDone;
17060b57cec5SDimitry Andric }
17070b57cec5SDimitry Andric 
getID() const17080b57cec5SDimitry Andric StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
17090b57cec5SDimitry Andric 
1710bdd1243dSDimitry Andric std::optional<TraversalKind>
getCheckTraversalKind() const1711fe6060f1SDimitry Andric MatchFinder::MatchCallback::getCheckTraversalKind() const {
1712bdd1243dSDimitry Andric   return std::nullopt;
1713fe6060f1SDimitry Andric }
1714fe6060f1SDimitry Andric 
17150b57cec5SDimitry Andric } // end namespace ast_matchers
17160b57cec5SDimitry Andric } // end namespace clang
1717