22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/Support/PrettyStackTrace.h"
25 #include "llvm/Support/Timer.h"
31 namespace ast_matchers {
35 typedef MatchFinder::MatchCallback MatchCallback;
45 static const unsigned MaxMemoizationEntries = 10000;
47 enum class MatchType {
73 bool operator<(
const MatchKey &Other)
const {
75 std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
81 struct MemoizedMatchResult {
88 class MatchChildASTVisitor
89 :
public RecursiveASTVisitor<MatchChildASTVisitor> {
91 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
97 MatchChildASTVisitor(
const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
98 BoundNodesTreeBuilder *Builder,
int MaxDepth,
99 bool IgnoreImplicitChildren,
100 ASTMatchFinder::BindKind Bind)
101 : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
102 MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
103 Bind(Bind), Matches(
false) {}
118 if (
const Decl *D = DynNode.get<Decl>())
120 else if (
const Stmt *S = DynNode.get<Stmt>())
122 else if (
const NestedNameSpecifier *NNS =
123 DynNode.get<NestedNameSpecifier>())
125 else if (
const NestedNameSpecifierLoc *NNSLoc =
126 DynNode.get<NestedNameSpecifierLoc>())
128 else if (
const QualType *Q = DynNode.get<QualType>())
130 else if (
const TypeLoc *T = DynNode.get<TypeLoc>())
132 else if (
const auto *C = DynNode.get<CXXCtorInitializer>())
134 else if (
const TemplateArgumentLoc *TALoc =
135 DynNode.get<TemplateArgumentLoc>())
137 else if (
const Attr *A = DynNode.get<Attr>())
144 *Builder = ResultBindings;
152 bool TraverseDecl(Decl *DeclNode) {
154 if (DeclNode && DeclNode->isImplicit() &&
155 Finder->isTraversalIgnoringImplicitNodes())
156 return baseTraverse(*DeclNode);
158 ScopedIncrement ScopedDepth(&CurrentDepth);
159 return (DeclNode ==
nullptr) ||
traverse(*DeclNode);
162 Stmt *getStmtToTraverse(Stmt *StmtNode) {
163 Stmt *StmtToTraverse = StmtNode;
164 if (
auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
165 auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
166 if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
167 StmtToTraverse = LambdaNode;
170 Finder->getASTContext().getParentMapContext().traverseIgnored(
173 return StmtToTraverse;
176 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue =
nullptr) {
178 if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth <
INT_MAX))
181 ScopedIncrement ScopedDepth(&CurrentDepth);
182 Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
186 if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
189 if (!
match(*StmtToTraverse))
195 bool TraverseType(QualType TypeNode) {
196 if (TypeNode.isNull())
198 ScopedIncrement ScopedDepth(&CurrentDepth);
200 if (!
match(*TypeNode))
207 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
208 if (TypeLocNode.isNull())
210 ScopedIncrement ScopedDepth(&CurrentDepth);
212 if (!
match(*TypeLocNode.getType()))
215 if (!
match(TypeLocNode.getType()))
220 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
221 ScopedIncrement ScopedDepth(&CurrentDepth);
222 return (NNS ==
nullptr) ||
traverse(*NNS);
224 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
227 ScopedIncrement ScopedDepth(&CurrentDepth);
228 if (!
match(*NNS.getNestedNameSpecifier()))
232 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
235 ScopedIncrement ScopedDepth(&CurrentDepth);
238 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
239 ScopedIncrement ScopedDepth(&CurrentDepth);
242 bool TraverseCXXForRangeStmt(CXXForRangeStmt *
Node) {
243 if (!Finder->isTraversalIgnoringImplicitNodes())
244 return VisitorBase::TraverseCXXForRangeStmt(
Node);
247 ScopedIncrement ScopedDepth(&CurrentDepth);
248 if (
auto *Init =
Node->getInit())
260 bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *
Node) {
261 if (!Finder->isTraversalIgnoringImplicitNodes())
262 return VisitorBase::TraverseCXXRewrittenBinaryOperator(
Node);
265 ScopedIncrement ScopedDepth(&CurrentDepth);
269 bool TraverseAttr(Attr *A) {
272 Finder->getASTContext().getParentMapContext().getTraversalKind() ==
275 ScopedIncrement ScopedDepth(&CurrentDepth);
278 bool TraverseLambdaExpr(LambdaExpr *
Node) {
279 if (!Finder->isTraversalIgnoringImplicitNodes())
280 return VisitorBase::TraverseLambdaExpr(
Node);
283 ScopedIncrement ScopedDepth(&CurrentDepth);
285 for (
unsigned I = 0, N =
Node->capture_size(); I != N; ++I) {
286 const auto *
C =
Node->capture_begin() + I;
287 if (!
C->isExplicit())
289 if (
Node->isInitCapture(C) && !
match(*
C->getCapturedVar()))
291 if (!
match(*
Node->capture_init_begin()[I]))
295 if (
const auto *TPL =
Node->getTemplateParameterList()) {
296 for (
const auto *TP : *TPL) {
302 for (
const auto *
P :
Node->getCallOperator()->parameters()) {
313 bool shouldVisitTemplateInstantiations()
const {
return true; }
314 bool shouldVisitImplicitCode()
const {
return !IgnoreImplicitChildren; }
318 struct ScopedIncrement {
320 ~ScopedIncrement() { --(*Depth); }
334 bool baseTraverse(
const Decl &DeclNode) {
337 bool baseTraverse(
const Stmt &StmtNode) {
340 bool baseTraverse(QualType TypeNode) {
343 bool baseTraverse(TypeLoc TypeLocNode) {
346 bool baseTraverse(
const NestedNameSpecifier &NNS) {
348 const_cast<NestedNameSpecifier*
>(&NNS));
350 bool baseTraverse(NestedNameSpecifierLoc NNS) {
353 bool baseTraverse(
const CXXCtorInitializer &CtorInit) {
355 const_cast<CXXCtorInitializer *
>(&CtorInit));
357 bool baseTraverse(TemplateArgumentLoc TAL) {
360 bool baseTraverse(
const Attr &AttrNode) {
369 template <
typename T>
371 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
374 if (Bind != ASTMatchFinder::BK_All) {
375 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
377 &RecursiveBuilder)) {
379 ResultBindings.addMatch(RecursiveBuilder);
383 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
385 &RecursiveBuilder)) {
388 ResultBindings.addMatch(RecursiveBuilder);
396 template <
typename T>
398 static_assert(IsBaseType<T>::value,
399 "traverse can only be instantiated with base type");
402 return baseTraverse(
Node);
405 const DynTypedMatcher *
const Matcher;
406 ASTMatchFinder *
const Finder;
407 BoundNodesTreeBuilder *
const Builder;
408 BoundNodesTreeBuilder ResultBindings;
411 const bool IgnoreImplicitChildren;
412 const ASTMatchFinder::BindKind Bind;
418 class MatchASTVisitor :
public RecursiveASTVisitor<MatchASTVisitor>,
419 public ASTMatchFinder {
421 MatchASTVisitor(
const MatchFinder::MatchersByType *Matchers,
422 const MatchFinder::MatchFinderOptions &Options)
423 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
425 ~MatchASTVisitor()
override {
426 if (Options.CheckProfiling) {
427 Options.CheckProfiling->Records = std::move(TimeByBucket);
431 void onStartOfTranslationUnit() {
432 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
433 TimeBucketRegion Timer;
434 for (MatchCallback *MC : Matchers->AllCallbacks) {
435 if (EnableCheckProfiling)
436 Timer.setBucket(&TimeByBucket[MC->getID()]);
437 MC->onStartOfTranslationUnit();
441 void onEndOfTranslationUnit() {
442 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
443 TimeBucketRegion Timer;
444 for (MatchCallback *MC : Matchers->AllCallbacks) {
445 if (EnableCheckProfiling)
446 Timer.setBucket(&TimeByBucket[MC->getID()]);
447 MC->onEndOfTranslationUnit();
451 void set_active_ast_context(ASTContext *NewActiveASTContext) {
452 ActiveASTContext = NewActiveASTContext;
458 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
486 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
487 const Type *CanonicalType =
488 ActiveASTContext->getCanonicalType(TypeNode);
489 TypeAliases[CanonicalType].insert(DeclNode);
493 bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
494 const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
495 CompatibleAliases[InterfaceDecl].insert(CAD);
499 bool TraverseDecl(Decl *DeclNode);
500 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue =
nullptr);
501 bool TraverseType(QualType TypeNode);
502 bool TraverseTypeLoc(TypeLoc TypeNode);
503 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
504 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
505 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
506 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
507 bool TraverseAttr(Attr *AttrNode);
509 bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
510 if (
auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
512 ASTNodeNotAsIsSourceScope RAII(
this,
true);
513 TraverseStmt(RF->getInit());
515 match(*RF->getLoopVariable());
516 TraverseStmt(RF->getRangeInit());
519 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
520 for (
auto *SubStmt : RF->children()) {
521 if (SubStmt != RF->getBody())
522 TraverseStmt(SubStmt);
525 TraverseStmt(RF->getBody());
527 }
else if (
auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
529 ASTNodeNotAsIsSourceScope RAII(
this,
true);
530 TraverseStmt(
const_cast<Expr *
>(RBO->getLHS()));
531 TraverseStmt(
const_cast<Expr *
>(RBO->getRHS()));
534 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
535 for (
auto *SubStmt : RBO->children()) {
536 TraverseStmt(SubStmt);
540 }
else if (
auto *
LE = dyn_cast<LambdaExpr>(S)) {
541 for (
auto I : llvm::zip(
LE->captures(),
LE->capture_inits())) {
542 auto C = std::get<0>(I);
543 ASTNodeNotSpelledInSourceScope RAII(
544 this, TraversingASTNodeNotSpelledInSource || !
C.isExplicit());
545 TraverseLambdaCapture(
LE, &C, std::get<1>(I));
549 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
550 TraverseDecl(
LE->getLambdaClass());
553 ASTNodeNotAsIsSourceScope RAII(
this,
true);
557 TypeLoc TL =
LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
558 FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
560 if (
auto *TPL =
LE->getTemplateParameterList()) {
561 for (NamedDecl *D : *TPL) {
564 if (Expr *RequiresClause = TPL->getRequiresClause()) {
565 TraverseStmt(RequiresClause);
569 if (
LE->hasExplicitParameters()) {
571 for (ParmVarDecl *Param : Proto.getParams())
575 const auto *T = Proto.getTypePtr();
576 for (
const auto &E : T->exceptions())
579 if (Expr *
NE = T->getNoexceptExpr())
580 TraverseStmt(
NE, Queue);
582 if (
LE->hasExplicitResultType())
583 TraverseTypeLoc(Proto.getReturnLoc());
584 TraverseStmt(
LE->getTrailingRequiresClause());
587 TraverseStmt(
LE->getBody());
595 const DynTypedMatcher &Matcher,
596 BoundNodesTreeBuilder *Builder,
int MaxDepth,
599 if (!
Node.getMemoizationData() || !Builder->isComparable())
600 return matchesRecursively(
Node, Matcher, Builder, MaxDepth, Bind);
603 Key.MatcherID = Matcher.getID();
606 Key.BoundNodes = *Builder;
607 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
609 Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
610 MemoizationMap::iterator I = ResultCache.find(Key);
611 if (I != ResultCache.end()) {
612 *Builder = I->second.Nodes;
613 return I->second.ResultOfMatch;
616 MemoizedMatchResult Result;
617 Result.Nodes = *Builder;
618 Result.ResultOfMatch =
619 matchesRecursively(
Node, Matcher, &Result.Nodes, MaxDepth, Bind);
621 MemoizedMatchResult &CachedResult = ResultCache[Key];
622 CachedResult = std::move(Result);
624 *Builder = CachedResult.Nodes;
625 return CachedResult.ResultOfMatch;
630 const DynTypedMatcher &Matcher,
631 BoundNodesTreeBuilder *Builder,
int MaxDepth,
633 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
634 TraversingASTChildrenNotSpelledInSource;
636 bool IgnoreImplicitChildren =
false;
638 if (isTraversalIgnoringImplicitNodes()) {
639 IgnoreImplicitChildren =
true;
642 ASTNodeNotSpelledInSourceScope RAII(
this, ScopedTraversal);
644 MatchChildASTVisitor Visitor(&Matcher,
this, Builder, MaxDepth,
645 IgnoreImplicitChildren, Bind);
646 return Visitor.findMatch(
Node);
649 bool classIsDerivedFrom(
const CXXRecordDecl *Declaration,
650 const Matcher<NamedDecl> &
Base,
651 BoundNodesTreeBuilder *Builder,
652 bool Directly)
override;
654 bool objcClassIsDerivedFrom(
const ObjCInterfaceDecl *Declaration,
655 const Matcher<NamedDecl> &
Base,
656 BoundNodesTreeBuilder *Builder,
657 bool Directly)
override;
661 const DynTypedMatcher &Matcher,
662 BoundNodesTreeBuilder *Builder, BindKind Bind)
override {
663 if (ResultCache.size() > MaxMemoizationEntries)
665 return memoizedMatchesRecursively(
Node, Ctx, Matcher, Builder, 1, Bind);
669 const DynTypedMatcher &Matcher,
670 BoundNodesTreeBuilder *Builder,
671 BindKind Bind)
override {
672 if (ResultCache.size() > MaxMemoizationEntries)
674 return memoizedMatchesRecursively(
Node, Ctx, Matcher, Builder,
INT_MAX,
679 const DynTypedMatcher &Matcher,
680 BoundNodesTreeBuilder *Builder,
681 AncestorMatchMode MatchMode)
override {
684 if (ResultCache.size() > MaxMemoizationEntries)
686 if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
687 return matchesParentOf(
Node, Matcher, Builder);
688 return matchesAnyAncestorOf(
Node, Ctx, Matcher, Builder);
695 if (
auto *N =
Node.get<Decl>()) {
697 }
else if (
auto *N =
Node.get<Stmt>()) {
699 }
else if (
auto *N =
Node.get<Type>()) {
701 }
else if (
auto *N =
Node.get<QualType>()) {
703 }
else if (
auto *N =
Node.get<NestedNameSpecifier>()) {
705 }
else if (
auto *N =
Node.get<NestedNameSpecifierLoc>()) {
707 }
else if (
auto *N =
Node.get<TypeLoc>()) {
709 }
else if (
auto *N =
Node.get<CXXCtorInitializer>()) {
711 }
else if (
auto *N =
Node.get<TemplateArgumentLoc>()) {
713 }
else if (
auto *N =
Node.get<Attr>()) {
718 template <
typename T>
void match(
const T &
Node) {
719 matchDispatch(&
Node);
723 ASTContext &getASTContext()
const override {
return *ActiveASTContext; }
725 bool shouldVisitTemplateInstantiations()
const {
return true; }
726 bool shouldVisitImplicitCode()
const {
return true; }
730 bool shouldVisitLambdaBody()
const {
return false; }
732 bool IsMatchingInASTNodeNotSpelledInSource()
const override {
733 return TraversingASTNodeNotSpelledInSource;
735 bool isMatchingChildrenNotSpelledInSource()
const override {
736 return TraversingASTChildrenNotSpelledInSource;
738 void setMatchingChildrenNotSpelledInSource(
bool Set)
override {
739 TraversingASTChildrenNotSpelledInSource = Set;
742 bool IsMatchingInASTNodeNotAsIs()
const override {
743 return TraversingASTNodeNotAsIs;
746 bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
747 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
748 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
752 bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
753 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
754 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
758 bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
759 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
760 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
765 bool TraversingASTNodeNotSpelledInSource =
false;
766 bool TraversingASTNodeNotAsIs =
false;
767 bool TraversingASTChildrenNotSpelledInSource =
false;
773 #define CMD_TYPES_0 \
774 const QualType *, const TypeLoc *, const NestedNameSpecifier *, \
775 const NestedNameSpecifierLoc *
776 #define CMD_TYPES_1 \
777 const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *, \
780 #define IMPL(Index) \
781 template <typename NodeType> \
783 llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value> \
784 SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) { \
786 Callback.setPointerAndInt(CB, Index); \
790 template <typename T> \
791 std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value, \
794 assertHoldsState(); \
795 return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>() \
800 CurMatchData() :
Node0(nullptr) {}
805 const MatchCallback *getCallback()
const {
return Callback.getPointer(); }
812 void clearBoundNodes() {
824 Callback.setPointerAndInt(
nullptr, 0);
829 void assertHoldsState()
const {
830 assert(Callback.getPointer() !=
nullptr && !
Node0.isNull());
833 void assertEmpty()
const {
834 assert(Callback.getPointer() ==
nullptr &&
Node0.isNull() &&
838 llvm::PointerIntPair<const MatchCallback *, 1> Callback;
840 llvm::PointerUnion<CMD_TYPES_0>
Node0;
841 llvm::PointerUnion<CMD_TYPES_1>
Node1;
850 struct CurMatchRAII {
851 template <
typename NodeType>
852 CurMatchRAII(MatchASTVisitor &MV,
const MatchCallback *CB,
855 MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
858 ~CurMatchRAII() { MV.CurMatchState.reset(); }
865 class TraceReporter : llvm::PrettyStackTraceEntry {
868 if (
const auto *D =
Node.get<Decl>()) {
869 OS << D->getDeclKindName() <<
"Decl ";
870 if (
const auto *ND = dyn_cast<NamedDecl>(D)) {
871 ND->printQualifiedName(OS);
875 D->getSourceRange().print(OS, Ctx.getSourceManager());
876 }
else if (
const auto *S =
Node.get<Stmt>()) {
877 OS << S->getStmtClassName() <<
" : ";
878 S->getSourceRange().print(OS, Ctx.getSourceManager());
879 }
else if (
const auto *T =
Node.get<Type>()) {
880 OS << T->getTypeClassName() <<
"Type : ";
881 QualType(T, 0).print(OS, Ctx.getPrintingPolicy());
882 }
else if (
const auto *QT =
Node.get<QualType>()) {
884 QT->print(OS, Ctx.getPrintingPolicy());
886 OS <<
Node.getNodeKind().asStringRef() <<
" : ";
887 Node.getSourceRange().print(OS, Ctx.getSourceManager());
891 static void dumpNodeFromState(
const ASTContext &Ctx,
892 const CurMatchData &
State, raw_ostream &OS) {
894 dumpNode(Ctx, *MatchNode, OS);
895 }
else if (
const auto *QT =
State.getNode<QualType>()) {
897 }
else if (
const auto *TL =
State.getNode<TypeLoc>()) {
899 }
else if (
const auto *NNS =
State.getNode<NestedNameSpecifier>()) {
901 }
else if (
const auto *NNSL =
State.getNode<NestedNameSpecifierLoc>()) {
903 }
else if (
const auto *CtorInit =
State.getNode<CXXCtorInitializer>()) {
905 }
else if (
const auto *TAL =
State.getNode<TemplateArgumentLoc>()) {
907 }
else if (
const auto *At =
State.getNode<Attr>()) {
913 TraceReporter(
const MatchASTVisitor &MV) : MV(MV) {}
914 void print(raw_ostream &OS)
const override {
915 const CurMatchData &
State = MV.CurMatchState;
916 const MatchCallback *CB =
State.getCallback();
918 OS <<
"ASTMatcher: Not currently matching\n";
922 assert(MV.ActiveASTContext &&
923 "ActiveASTContext should be set if there is a matched callback");
925 ASTContext &Ctx = MV.getASTContext();
928 OS <<
"ASTMatcher: Processing '" << CB->getID() <<
"' against:\n\t";
929 dumpNodeFromState(Ctx,
State, OS);
932 OS <<
"\nNo bound nodes\n";
935 OS <<
"\n--- Bound Nodes Begin ---\n";
936 for (
const auto &Item : Map) {
937 OS <<
" " << Item.first <<
" - { ";
938 dumpNode(Ctx, Item.second, OS);
941 OS <<
"--- Bound Nodes End ---\n";
943 OS <<
"ASTMatcher: Matching '" << CB->getID() <<
"' against:\n\t";
944 dumpNodeFromState(Ctx,
State, OS);
950 const MatchASTVisitor &MV;
954 struct ASTNodeNotSpelledInSourceScope {
955 ASTNodeNotSpelledInSourceScope(MatchASTVisitor *
V,
bool B)
956 : MV(
V), MB(
V->TraversingASTNodeNotSpelledInSource) {
957 V->TraversingASTNodeNotSpelledInSource = B;
959 ~ASTNodeNotSpelledInSourceScope() {
960 MV->TraversingASTNodeNotSpelledInSource = MB;
968 struct ASTNodeNotAsIsSourceScope {
969 ASTNodeNotAsIsSourceScope(MatchASTVisitor *
V,
bool B)
970 : MV(
V), MB(
V->TraversingASTNodeNotAsIs) {
971 V->TraversingASTNodeNotAsIs = B;
973 ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
980 class TimeBucketRegion {
982 TimeBucketRegion() : Bucket(nullptr) {}
983 ~TimeBucketRegion() { setBucket(
nullptr); }
993 void setBucket(llvm::TimeRecord *NewBucket) {
994 if (Bucket != NewBucket) {
995 auto Now = llvm::TimeRecord::getCurrentTime(
true);
1005 llvm::TimeRecord *Bucket;
1011 template <
typename T,
typename MC>
1012 void matchWithoutFilter(
const T &
Node,
const MC &Matchers) {
1013 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1014 TimeBucketRegion Timer;
1015 for (
const auto &MP : Matchers) {
1016 if (EnableCheckProfiling)
1017 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1018 BoundNodesTreeBuilder Builder;
1019 CurMatchRAII RAII(*
this, MP.second,
Node);
1020 if (MP.first.matches(
Node,
this, &Builder)) {
1021 MatchVisitor Visitor(*
this, ActiveASTContext, MP.second);
1022 Builder.visitMatches(&Visitor);
1028 auto Kind = DynNode.getNodeKind();
1029 auto it = MatcherFiltersMap.find(
Kind);
1031 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(
Kind);
1036 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1037 TimeBucketRegion Timer;
1038 auto &Matchers = this->Matchers->DeclOrStmt;
1039 for (
unsigned short I :
Filter) {
1040 auto &MP = Matchers[I];
1041 if (EnableCheckProfiling)
1042 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1043 BoundNodesTreeBuilder Builder;
1046 TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
1047 if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
1052 CurMatchRAII RAII(*
this, MP.second, DynNode);
1053 if (MP.first.matches(DynNode,
this, &Builder)) {
1054 MatchVisitor Visitor(*
this, ActiveASTContext, MP.second);
1055 Builder.visitMatches(&Visitor);
1060 const std::vector<unsigned short> &getFilterForKind(ASTNodeKind
Kind) {
1062 auto &Matchers = this->Matchers->DeclOrStmt;
1063 assert((Matchers.size() <
USHRT_MAX) &&
"Too many matchers.");
1064 for (
unsigned I = 0, E = Matchers.size(); I != E; ++I) {
1065 if (Matchers[I].first.canMatchNodesOfKind(
Kind)) {
1074 void matchDispatch(
const Decl *
Node) {
1077 void matchDispatch(
const Stmt *
Node) {
1081 void matchDispatch(
const Type *
Node) {
1082 matchWithoutFilter(QualType(
Node, 0), Matchers->Type);
1084 void matchDispatch(
const TypeLoc *
Node) {
1085 matchWithoutFilter(*
Node, Matchers->TypeLoc);
1087 void matchDispatch(
const QualType *
Node) {
1088 matchWithoutFilter(*
Node, Matchers->Type);
1090 void matchDispatch(
const NestedNameSpecifier *
Node) {
1091 matchWithoutFilter(*
Node, Matchers->NestedNameSpecifier);
1093 void matchDispatch(
const NestedNameSpecifierLoc *
Node) {
1094 matchWithoutFilter(*
Node, Matchers->NestedNameSpecifierLoc);
1096 void matchDispatch(
const CXXCtorInitializer *
Node) {
1097 matchWithoutFilter(*
Node, Matchers->CtorInit);
1099 void matchDispatch(
const TemplateArgumentLoc *
Node) {
1100 matchWithoutFilter(*
Node, Matchers->TemplateArgumentLoc);
1102 void matchDispatch(
const Attr *
Node) {
1103 matchWithoutFilter(*
Node, Matchers->Attr);
1105 void matchDispatch(
const void *) { }
1110 bool matchesParentOf(
const DynTypedNode &
Node,
const DynTypedMatcher &Matcher,
1111 BoundNodesTreeBuilder *Builder) {
1112 for (
const auto &
Parent : ActiveASTContext->getParents(
Node)) {
1113 BoundNodesTreeBuilder BuilderCopy = *Builder;
1114 if (Matcher.matches(
Parent,
this, &BuilderCopy)) {
1115 *Builder = std::move(BuilderCopy);
1139 const DynTypedMatcher &Matcher,
1140 BoundNodesTreeBuilder *Builder) {
1145 std::vector<MatchKey> Keys;
1147 auto Finish = [&](
bool Matched) {
1148 for (
const auto &Key : Keys) {
1149 MemoizedMatchResult &CachedResult = ResultCache[Key];
1150 CachedResult.ResultOfMatch = Matched;
1151 CachedResult.Nodes = *Builder;
1157 DynTypedNodeList Parents{ArrayRef<DynTypedNode>()};
1160 if (Builder->isComparable()) {
1161 Keys.emplace_back();
1162 Keys.back().MatcherID = Matcher.getID();
1163 Keys.back().Node =
Node;
1164 Keys.back().BoundNodes = *Builder;
1165 Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
1166 Keys.back().Type = MatchType::Ancestors;
1169 MemoizationMap::iterator I = ResultCache.find(Keys.back());
1170 if (I != ResultCache.end()) {
1172 *Builder = I->second.Nodes;
1173 return Finish(I->second.ResultOfMatch);
1177 Parents = ActiveASTContext->getParents(
Node);
1180 if (Parents.size() != 1)
1184 Node = *Parents.begin();
1185 BoundNodesTreeBuilder BuilderCopy = *Builder;
1186 if (Matcher.matches(
Node,
this, &BuilderCopy)) {
1187 *Builder = std::move(BuilderCopy);
1188 return Finish(
true);
1193 if (Parents.empty()) {
1201 if (!
Node.get<TranslationUnitDecl>() &&
1203 llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
1204 return D->getKind() == Decl::TranslationUnit;
1206 llvm::errs() <<
"Tried to match orphan node:\n";
1207 Node.dump(llvm::errs(), *ActiveASTContext);
1208 llvm_unreachable(
"Parent map should be complete!");
1212 assert(Parents.size() > 1);
1216 std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1218 while (!Queue.empty()) {
1219 BoundNodesTreeBuilder BuilderCopy = *Builder;
1220 if (Matcher.matches(Queue.front(),
this, &BuilderCopy)) {
1221 *Builder = std::move(BuilderCopy);
1222 return Finish(
true);
1224 for (
const auto &
Parent : ActiveASTContext->getParents(Queue.front())) {
1228 if (Visited.insert(
Parent.getMemoizationData()).second)
1234 return Finish(
false);
1239 class MatchVisitor :
public BoundNodesTreeBuilder::Visitor {
1240 struct CurBoundScope {
1241 CurBoundScope(MatchASTVisitor::CurMatchData &
State,
const BoundNodes &BN)
1243 State.SetBoundNodes(BN);
1246 ~CurBoundScope() {
State.clearBoundNodes(); }
1249 MatchASTVisitor::CurMatchData &
State;
1253 MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
1254 MatchFinder::MatchCallback *Callback)
1255 :
State(MV.CurMatchState), Context(Context), Callback(Callback) {}
1257 void visitMatch(
const BoundNodes& BoundNodesView)
override {
1258 TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
1259 CurBoundScope RAII2(
State, BoundNodesView);
1264 MatchASTVisitor::CurMatchData &
State;
1265 ASTContext* Context;
1266 MatchFinder::MatchCallback* Callback;
1270 bool typeHasMatchingAlias(
const Type *TypeNode,
1271 const Matcher<NamedDecl> &Matcher,
1272 BoundNodesTreeBuilder *Builder) {
1273 const Type *
const CanonicalType =
1274 ActiveASTContext->getCanonicalType(TypeNode);
1275 auto Aliases = TypeAliases.find(CanonicalType);
1276 if (Aliases == TypeAliases.end())
1278 for (
const TypedefNameDecl *Alias : Aliases->second) {
1279 BoundNodesTreeBuilder Result(*Builder);
1280 if (Matcher.matches(*Alias,
this, &Result)) {
1281 *Builder = std::move(Result);
1289 objcClassHasMatchingCompatibilityAlias(
const ObjCInterfaceDecl *InterfaceDecl,
1290 const Matcher<NamedDecl> &Matcher,
1291 BoundNodesTreeBuilder *Builder) {
1292 auto Aliases = CompatibleAliases.find(InterfaceDecl);
1293 if (Aliases == CompatibleAliases.end())
1295 for (
const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1296 BoundNodesTreeBuilder Result(*Builder);
1297 if (Matcher.matches(*Alias,
this, &Result)) {
1298 *Builder = std::move(Result);
1308 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1310 const MatchFinder::MatchersByType *Matchers;
1318 llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1320 const MatchFinder::MatchFinderOptions &Options;
1321 ASTContext *ActiveASTContext;
1324 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1327 llvm::DenseMap<
const ObjCInterfaceDecl *,
1332 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1333 MemoizationMap ResultCache;
1336 static CXXRecordDecl *
1337 getAsCXXRecordDeclOrPrimaryTemplate(
const Type *TypeNode) {
1338 if (
auto *RD = TypeNode->getAsCXXRecordDecl())
1342 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1343 while (TemplateType && TemplateType->isTypeAlias())
1345 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1350 if (
auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1351 TemplateType->getTemplateName().getAsTemplateDecl()))
1352 return ClassTemplate->getTemplatedDecl();
1360 bool MatchASTVisitor::classIsDerivedFrom(
const CXXRecordDecl *Declaration,
1361 const Matcher<NamedDecl> &
Base,
1362 BoundNodesTreeBuilder *Builder,
1367 const Type *TypeNode = It.getType().getTypePtr();
1369 if (typeHasMatchingAlias(TypeNode,
Base, Builder))
1375 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1378 if (ClassDecl == Declaration) {
1382 BoundNodesTreeBuilder Result(*Builder);
1383 if (
Base.matches(*ClassDecl,
this, &Result)) {
1384 *Builder = std::move(Result);
1387 if (!Directly && classIsDerivedFrom(ClassDecl,
Base, Builder, Directly))
1396 bool MatchASTVisitor::objcClassIsDerivedFrom(
1397 const ObjCInterfaceDecl *Declaration,
const Matcher<NamedDecl> &
Base,
1398 BoundNodesTreeBuilder *Builder,
bool Directly) {
1400 for (
const ObjCInterfaceDecl *ClassDecl =
Declaration->getSuperClass();
1401 ClassDecl !=
nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1403 if (objcClassHasMatchingCompatibilityAlias(ClassDecl,
Base, Builder))
1407 const Type *TypeNode = ClassDecl->getTypeForDecl();
1408 if (typeHasMatchingAlias(TypeNode,
Base, Builder))
1411 if (
Base.matches(*ClassDecl,
this, Builder))
1422 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1427 bool ScopedTraversal =
1428 TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1429 bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1431 if (
const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1432 auto SK = CTSD->getSpecializationKind();
1435 ScopedChildren =
true;
1436 }
else if (
const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1437 if (FD->isDefaulted())
1438 ScopedChildren =
true;
1439 if (FD->isTemplateInstantiation())
1440 ScopedTraversal =
true;
1441 }
else if (isa<BindingDecl>(DeclNode)) {
1442 ScopedChildren =
true;
1445 ASTNodeNotSpelledInSourceScope RAII1(
this, ScopedTraversal);
1446 ASTChildrenNotSpelledInSourceScope RAII2(
this, ScopedChildren);
1452 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1456 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1457 TraversingASTChildrenNotSpelledInSource;
1459 ASTNodeNotSpelledInSourceScope RAII(
this, ScopedTraversal);
1464 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1469 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1476 match(TypeLocNode.getType());
1480 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1485 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1486 NestedNameSpecifierLoc NNS) {
1494 if (NNS.hasQualifier())
1495 match(*NNS.getNestedNameSpecifier());
1500 bool MatchASTVisitor::TraverseConstructorInitializer(
1501 CXXCtorInitializer *CtorInit) {
1505 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1506 TraversingASTChildrenNotSpelledInSource;
1508 if (!CtorInit->isWritten())
1509 ScopedTraversal =
true;
1511 ASTNodeNotSpelledInSourceScope RAII1(
this, ScopedTraversal);
1519 bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1524 bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1529 class MatchASTConsumer :
public ASTConsumer {
1531 MatchASTConsumer(MatchFinder *Finder,
1532 MatchFinder::ParsingDoneTestCallback *ParsingDone)
1533 : Finder(Finder), ParsingDone(ParsingDone) {}
1536 void HandleTranslationUnit(ASTContext &Context)
override {
1537 if (ParsingDone !=
nullptr) {
1540 Finder->matchAST(Context);
1543 MatchFinder *Finder;
1544 MatchFinder::ParsingDoneTestCallback *ParsingDone;
1559 : Options(
std::move(Options)), ParsingDone(nullptr) {}
1565 std::optional<TraversalKind> TK;
1569 Matchers.DeclOrStmt.emplace_back(
traverse(*TK, NodeMatch), Action);
1571 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1572 Matchers.AllCallbacks.insert(Action);
1577 Matchers.Type.emplace_back(NodeMatch, Action);
1578 Matchers.AllCallbacks.insert(Action);
1583 std::optional<TraversalKind> TK;
1587 Matchers.DeclOrStmt.emplace_back(
traverse(*TK, NodeMatch), Action);
1589 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1590 Matchers.AllCallbacks.insert(Action);
1595 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1596 Matchers.AllCallbacks.insert(Action);
1601 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1602 Matchers.AllCallbacks.insert(Action);
1607 Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1608 Matchers.AllCallbacks.insert(Action);
1613 Matchers.CtorInit.emplace_back(NodeMatch, Action);
1614 Matchers.AllCallbacks.insert(Action);
1619 Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1620 Matchers.AllCallbacks.insert(Action);
1625 Matchers.Attr.emplace_back(AttrMatch, Action);
1626 Matchers.AllCallbacks.insert(Action);
1631 if (NodeMatch.canConvertTo<
Decl>()) {
1634 }
else if (NodeMatch.canConvertTo<
QualType>()) {
1637 }
else if (NodeMatch.canConvertTo<
Stmt>()) {
1646 }
else if (NodeMatch.canConvertTo<
TypeLoc>()) {
1655 }
else if (NodeMatch.canConvertTo<
Attr>()) {
1663 return std::make_unique<internal::MatchASTConsumer>(
this, ParsingDone);
1667 internal::MatchASTVisitor Visitor(&Matchers, Options);
1668 Visitor.set_active_ast_context(&Context);
1669 Visitor.match(
Node);
1673 internal::MatchASTVisitor Visitor(&Matchers, Options);
1674 internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
1675 Visitor.set_active_ast_context(&Context);
1676 Visitor.onStartOfTranslationUnit();
1677 Visitor.TraverseAST(Context);
1678 Visitor.onEndOfTranslationUnit();
1683 ParsingDone = NewParsingDone;
1688 std::optional<TraversalKind>
1690 return std::nullopt;