22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/Support/Timer.h"
30 namespace ast_matchers {
34 typedef MatchFinder::MatchCallback MatchCallback;
44 static const unsigned MaxMemoizationEntries = 10000;
46 enum class MatchType {
72 bool operator<(
const MatchKey &Other)
const {
74 std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
80 struct MemoizedMatchResult {
87 class MatchChildASTVisitor
88 :
public RecursiveASTVisitor<MatchChildASTVisitor> {
90 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
96 MatchChildASTVisitor(
const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
97 BoundNodesTreeBuilder *Builder,
int MaxDepth,
98 bool IgnoreImplicitChildren,
99 ASTMatchFinder::BindKind Bind)
100 : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
101 MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
102 Bind(Bind), Matches(
false) {}
117 if (
const Decl *D = DynNode.get<Decl>())
119 else if (
const Stmt *S = DynNode.get<Stmt>())
121 else if (
const NestedNameSpecifier *NNS =
122 DynNode.get<NestedNameSpecifier>())
124 else if (
const NestedNameSpecifierLoc *NNSLoc =
125 DynNode.get<NestedNameSpecifierLoc>())
127 else if (
const QualType *Q = DynNode.get<QualType>())
129 else if (
const TypeLoc *T = DynNode.get<TypeLoc>())
131 else if (
const auto *C = DynNode.get<CXXCtorInitializer>())
133 else if (
const TemplateArgumentLoc *TALoc =
134 DynNode.get<TemplateArgumentLoc>())
141 *Builder = ResultBindings;
149 bool TraverseDecl(Decl *DeclNode) {
151 if (DeclNode && DeclNode->isImplicit() &&
152 Finder->isTraversalIgnoringImplicitNodes())
153 return baseTraverse(*DeclNode);
155 ScopedIncrement ScopedDepth(&CurrentDepth);
156 return (DeclNode ==
nullptr) ||
traverse(*DeclNode);
159 Stmt *getStmtToTraverse(Stmt *StmtNode) {
160 Stmt *StmtToTraverse = StmtNode;
161 if (
auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
162 auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
163 if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
164 StmtToTraverse = LambdaNode;
167 Finder->getASTContext().getParentMapContext().traverseIgnored(
170 return StmtToTraverse;
173 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue =
nullptr) {
175 if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth <
INT_MAX))
178 ScopedIncrement ScopedDepth(&CurrentDepth);
179 Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
183 if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
186 if (!
match(*StmtToTraverse))
192 bool TraverseType(QualType TypeNode) {
193 if (TypeNode.isNull())
195 ScopedIncrement ScopedDepth(&CurrentDepth);
197 if (!
match(*TypeNode))
204 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
205 if (TypeLocNode.isNull())
207 ScopedIncrement ScopedDepth(&CurrentDepth);
209 if (!
match(*TypeLocNode.getType()))
212 if (!
match(TypeLocNode.getType()))
217 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
218 ScopedIncrement ScopedDepth(&CurrentDepth);
219 return (NNS ==
nullptr) ||
traverse(*NNS);
221 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
224 ScopedIncrement ScopedDepth(&CurrentDepth);
225 if (!
match(*NNS.getNestedNameSpecifier()))
229 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
232 ScopedIncrement ScopedDepth(&CurrentDepth);
235 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
236 ScopedIncrement ScopedDepth(&CurrentDepth);
239 bool TraverseCXXForRangeStmt(CXXForRangeStmt *
Node) {
240 if (!Finder->isTraversalIgnoringImplicitNodes())
241 return VisitorBase::TraverseCXXForRangeStmt(
Node);
244 ScopedIncrement ScopedDepth(&CurrentDepth);
245 if (
auto *Init =
Node->getInit())
257 bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *
Node) {
258 if (!Finder->isTraversalIgnoringImplicitNodes())
259 return VisitorBase::TraverseCXXRewrittenBinaryOperator(
Node);
262 ScopedIncrement ScopedDepth(&CurrentDepth);
266 bool TraverseLambdaExpr(LambdaExpr *
Node) {
267 if (!Finder->isTraversalIgnoringImplicitNodes())
268 return VisitorBase::TraverseLambdaExpr(
Node);
271 ScopedIncrement ScopedDepth(&CurrentDepth);
273 for (
unsigned I = 0, N =
Node->capture_size(); I != N; ++I) {
274 const auto *
C =
Node->capture_begin() + I;
275 if (!
C->isExplicit())
277 if (
Node->isInitCapture(C) && !
match(*
C->getCapturedVar()))
279 if (!
match(*
Node->capture_init_begin()[I]))
283 if (
const auto *TPL =
Node->getTemplateParameterList()) {
284 for (
const auto *TP : *TPL) {
290 for (
const auto *
P :
Node->getCallOperator()->parameters()) {
301 bool shouldVisitTemplateInstantiations()
const {
return true; }
302 bool shouldVisitImplicitCode()
const {
return !IgnoreImplicitChildren; }
306 struct ScopedIncrement {
308 ~ScopedIncrement() { --(*Depth); }
322 bool baseTraverse(
const Decl &DeclNode) {
325 bool baseTraverse(
const Stmt &StmtNode) {
328 bool baseTraverse(QualType TypeNode) {
331 bool baseTraverse(TypeLoc TypeLocNode) {
334 bool baseTraverse(
const NestedNameSpecifier &NNS) {
336 const_cast<NestedNameSpecifier*
>(&NNS));
338 bool baseTraverse(NestedNameSpecifierLoc NNS) {
341 bool baseTraverse(
const CXXCtorInitializer &CtorInit) {
343 const_cast<CXXCtorInitializer *
>(&CtorInit));
345 bool baseTraverse(TemplateArgumentLoc TAL) {
354 template <
typename T>
356 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
359 if (Bind != ASTMatchFinder::BK_All) {
360 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
362 &RecursiveBuilder)) {
364 ResultBindings.addMatch(RecursiveBuilder);
368 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
370 &RecursiveBuilder)) {
373 ResultBindings.addMatch(RecursiveBuilder);
381 template <
typename T>
383 static_assert(IsBaseType<T>::value,
384 "traverse can only be instantiated with base type");
387 return baseTraverse(
Node);
390 const DynTypedMatcher *
const Matcher;
391 ASTMatchFinder *
const Finder;
392 BoundNodesTreeBuilder *
const Builder;
393 BoundNodesTreeBuilder ResultBindings;
396 const bool IgnoreImplicitChildren;
397 const ASTMatchFinder::BindKind Bind;
403 class MatchASTVisitor :
public RecursiveASTVisitor<MatchASTVisitor>,
404 public ASTMatchFinder {
406 MatchASTVisitor(
const MatchFinder::MatchersByType *Matchers,
407 const MatchFinder::MatchFinderOptions &Options)
408 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
410 ~MatchASTVisitor()
override {
411 if (Options.CheckProfiling) {
412 Options.CheckProfiling->Records = std::move(TimeByBucket);
416 void onStartOfTranslationUnit() {
417 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
418 TimeBucketRegion Timer;
419 for (MatchCallback *MC : Matchers->AllCallbacks) {
420 if (EnableCheckProfiling)
421 Timer.setBucket(&TimeByBucket[MC->getID()]);
422 MC->onStartOfTranslationUnit();
426 void onEndOfTranslationUnit() {
427 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
428 TimeBucketRegion Timer;
429 for (MatchCallback *MC : Matchers->AllCallbacks) {
430 if (EnableCheckProfiling)
431 Timer.setBucket(&TimeByBucket[MC->getID()]);
432 MC->onEndOfTranslationUnit();
436 void set_active_ast_context(ASTContext *NewActiveASTContext) {
437 ActiveASTContext = NewActiveASTContext;
443 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
471 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
472 const Type *CanonicalType =
473 ActiveASTContext->getCanonicalType(TypeNode);
474 TypeAliases[CanonicalType].insert(DeclNode);
478 bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
479 const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
480 CompatibleAliases[InterfaceDecl].insert(CAD);
484 bool TraverseDecl(Decl *DeclNode);
485 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue =
nullptr);
486 bool TraverseType(QualType TypeNode);
487 bool TraverseTypeLoc(TypeLoc TypeNode);
488 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
489 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
490 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
491 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
493 bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
494 if (
auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
496 ASTNodeNotAsIsSourceScope RAII(
this,
true);
497 TraverseStmt(RF->getInit());
499 match(*RF->getLoopVariable());
500 TraverseStmt(RF->getRangeInit());
503 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
504 for (
auto *SubStmt : RF->children()) {
505 if (SubStmt != RF->getBody())
506 TraverseStmt(SubStmt);
509 TraverseStmt(RF->getBody());
511 }
else if (
auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
513 ASTNodeNotAsIsSourceScope RAII(
this,
true);
514 TraverseStmt(
const_cast<Expr *
>(RBO->getLHS()));
515 TraverseStmt(
const_cast<Expr *
>(RBO->getRHS()));
518 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
519 for (
auto *SubStmt : RBO->children()) {
520 TraverseStmt(SubStmt);
524 }
else if (
auto *
LE = dyn_cast<LambdaExpr>(S)) {
525 for (
auto I : llvm::zip(
LE->captures(),
LE->capture_inits())) {
526 auto C = std::get<0>(I);
527 ASTNodeNotSpelledInSourceScope RAII(
528 this, TraversingASTNodeNotSpelledInSource || !
C.isExplicit());
529 TraverseLambdaCapture(
LE, &C, std::get<1>(I));
533 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
534 TraverseDecl(
LE->getLambdaClass());
537 ASTNodeNotAsIsSourceScope RAII(
this,
true);
541 TypeLoc TL =
LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
542 FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
544 if (
auto *TPL =
LE->getTemplateParameterList()) {
545 for (NamedDecl *D : *TPL) {
548 if (Expr *RequiresClause = TPL->getRequiresClause()) {
549 TraverseStmt(RequiresClause);
553 if (
LE->hasExplicitParameters()) {
555 for (ParmVarDecl *Param : Proto.getParams())
559 const auto *T = Proto.getTypePtr();
560 for (
const auto &E : T->exceptions())
563 if (Expr *
NE = T->getNoexceptExpr())
564 TraverseStmt(
NE, Queue);
566 if (
LE->hasExplicitResultType())
567 TraverseTypeLoc(Proto.getReturnLoc());
568 TraverseStmt(
LE->getTrailingRequiresClause());
571 TraverseStmt(
LE->getBody());
579 const DynTypedMatcher &Matcher,
580 BoundNodesTreeBuilder *Builder,
int MaxDepth,
583 if (!
Node.getMemoizationData() || !Builder->isComparable())
584 return matchesRecursively(
Node, Matcher, Builder, MaxDepth, Bind);
587 Key.MatcherID = Matcher.getID();
590 Key.BoundNodes = *Builder;
591 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
593 Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
594 MemoizationMap::iterator I = ResultCache.find(Key);
595 if (I != ResultCache.end()) {
596 *Builder = I->second.Nodes;
597 return I->second.ResultOfMatch;
600 MemoizedMatchResult Result;
601 Result.Nodes = *Builder;
602 Result.ResultOfMatch =
603 matchesRecursively(
Node, Matcher, &Result.Nodes, MaxDepth, Bind);
605 MemoizedMatchResult &CachedResult = ResultCache[Key];
606 CachedResult = std::move(Result);
608 *Builder = CachedResult.Nodes;
609 return CachedResult.ResultOfMatch;
614 const DynTypedMatcher &Matcher,
615 BoundNodesTreeBuilder *Builder,
int MaxDepth,
617 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
618 TraversingASTChildrenNotSpelledInSource;
620 bool IgnoreImplicitChildren =
false;
622 if (isTraversalIgnoringImplicitNodes()) {
623 IgnoreImplicitChildren =
true;
626 ASTNodeNotSpelledInSourceScope RAII(
this, ScopedTraversal);
628 MatchChildASTVisitor Visitor(&Matcher,
this, Builder, MaxDepth,
629 IgnoreImplicitChildren, Bind);
630 return Visitor.findMatch(
Node);
633 bool classIsDerivedFrom(
const CXXRecordDecl *Declaration,
634 const Matcher<NamedDecl> &
Base,
635 BoundNodesTreeBuilder *Builder,
636 bool Directly)
override;
638 bool objcClassIsDerivedFrom(
const ObjCInterfaceDecl *Declaration,
639 const Matcher<NamedDecl> &
Base,
640 BoundNodesTreeBuilder *Builder,
641 bool Directly)
override;
645 const DynTypedMatcher &Matcher,
646 BoundNodesTreeBuilder *Builder, BindKind Bind)
override {
647 if (ResultCache.size() > MaxMemoizationEntries)
649 return memoizedMatchesRecursively(
Node, Ctx, Matcher, Builder, 1, Bind);
653 const DynTypedMatcher &Matcher,
654 BoundNodesTreeBuilder *Builder,
655 BindKind Bind)
override {
656 if (ResultCache.size() > MaxMemoizationEntries)
658 return memoizedMatchesRecursively(
Node, Ctx, Matcher, Builder,
INT_MAX,
663 const DynTypedMatcher &Matcher,
664 BoundNodesTreeBuilder *Builder,
665 AncestorMatchMode MatchMode)
override {
668 if (ResultCache.size() > MaxMemoizationEntries)
670 if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
671 return matchesParentOf(
Node, Matcher, Builder);
672 return matchesAnyAncestorOf(
Node, Ctx, Matcher, Builder);
679 if (
auto *N =
Node.get<Decl>()) {
681 }
else if (
auto *N =
Node.get<Stmt>()) {
683 }
else if (
auto *N =
Node.get<Type>()) {
685 }
else if (
auto *N =
Node.get<QualType>()) {
687 }
else if (
auto *N =
Node.get<NestedNameSpecifier>()) {
689 }
else if (
auto *N =
Node.get<NestedNameSpecifierLoc>()) {
691 }
else if (
auto *N =
Node.get<TypeLoc>()) {
693 }
else if (
auto *N =
Node.get<CXXCtorInitializer>()) {
695 }
else if (
auto *N =
Node.get<TemplateArgumentLoc>()) {
700 template <
typename T>
void match(
const T &
Node) {
701 matchDispatch(&
Node);
705 ASTContext &getASTContext()
const override {
return *ActiveASTContext; }
707 bool shouldVisitTemplateInstantiations()
const {
return true; }
708 bool shouldVisitImplicitCode()
const {
return true; }
712 bool shouldVisitLambdaBody()
const {
return false; }
714 bool IsMatchingInASTNodeNotSpelledInSource()
const override {
715 return TraversingASTNodeNotSpelledInSource;
717 bool isMatchingChildrenNotSpelledInSource()
const override {
718 return TraversingASTChildrenNotSpelledInSource;
720 void setMatchingChildrenNotSpelledInSource(
bool Set)
override {
721 TraversingASTChildrenNotSpelledInSource = Set;
724 bool IsMatchingInASTNodeNotAsIs()
const override {
725 return TraversingASTNodeNotAsIs;
728 bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
729 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
730 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
734 bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
735 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
736 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
740 bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
741 ASTNodeNotSpelledInSourceScope RAII(
this,
true);
742 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
747 bool TraversingASTNodeNotSpelledInSource =
false;
748 bool TraversingASTNodeNotAsIs =
false;
749 bool TraversingASTChildrenNotSpelledInSource =
false;
751 struct ASTNodeNotSpelledInSourceScope {
752 ASTNodeNotSpelledInSourceScope(MatchASTVisitor *
V,
bool B)
753 : MV(
V), MB(
V->TraversingASTNodeNotSpelledInSource) {
754 V->TraversingASTNodeNotSpelledInSource = B;
756 ~ASTNodeNotSpelledInSourceScope() {
757 MV->TraversingASTNodeNotSpelledInSource = MB;
765 struct ASTNodeNotAsIsSourceScope {
766 ASTNodeNotAsIsSourceScope(MatchASTVisitor *
V,
bool B)
767 : MV(
V), MB(
V->TraversingASTNodeNotAsIs) {
768 V->TraversingASTNodeNotAsIs = B;
770 ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
777 class TimeBucketRegion {
779 TimeBucketRegion() : Bucket(nullptr) {}
780 ~TimeBucketRegion() { setBucket(
nullptr); }
790 void setBucket(llvm::TimeRecord *NewBucket) {
791 if (Bucket != NewBucket) {
792 auto Now = llvm::TimeRecord::getCurrentTime(
true);
802 llvm::TimeRecord *Bucket;
808 template <
typename T,
typename MC>
809 void matchWithoutFilter(
const T &
Node,
const MC &Matchers) {
810 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
811 TimeBucketRegion Timer;
812 for (
const auto &MP : Matchers) {
813 if (EnableCheckProfiling)
814 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
815 BoundNodesTreeBuilder Builder;
816 if (MP.first.matches(
Node,
this, &Builder)) {
817 MatchVisitor Visitor(ActiveASTContext, MP.second);
818 Builder.visitMatches(&Visitor);
824 auto Kind = DynNode.getNodeKind();
825 auto it = MatcherFiltersMap.find(
Kind);
827 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(
Kind);
832 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
833 TimeBucketRegion Timer;
834 auto &Matchers = this->Matchers->DeclOrStmt;
835 for (
unsigned short I :
Filter) {
836 auto &MP = Matchers[I];
837 if (EnableCheckProfiling)
838 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
839 BoundNodesTreeBuilder Builder;
842 TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
843 if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
848 if (MP.first.matches(DynNode,
this, &Builder)) {
849 MatchVisitor Visitor(ActiveASTContext, MP.second);
850 Builder.visitMatches(&Visitor);
855 const std::vector<unsigned short> &getFilterForKind(ASTNodeKind
Kind) {
857 auto &Matchers = this->Matchers->DeclOrStmt;
858 assert((Matchers.size() <
USHRT_MAX) &&
"Too many matchers.");
859 for (
unsigned I = 0, E = Matchers.size(); I != E; ++I) {
860 if (Matchers[I].first.canMatchNodesOfKind(
Kind)) {
869 void matchDispatch(
const Decl *
Node) {
872 void matchDispatch(
const Stmt *
Node) {
876 void matchDispatch(
const Type *
Node) {
877 matchWithoutFilter(QualType(
Node, 0), Matchers->Type);
879 void matchDispatch(
const TypeLoc *
Node) {
880 matchWithoutFilter(*
Node, Matchers->TypeLoc);
882 void matchDispatch(
const QualType *
Node) {
883 matchWithoutFilter(*
Node, Matchers->Type);
885 void matchDispatch(
const NestedNameSpecifier *
Node) {
886 matchWithoutFilter(*
Node, Matchers->NestedNameSpecifier);
888 void matchDispatch(
const NestedNameSpecifierLoc *
Node) {
889 matchWithoutFilter(*
Node, Matchers->NestedNameSpecifierLoc);
891 void matchDispatch(
const CXXCtorInitializer *
Node) {
892 matchWithoutFilter(*
Node, Matchers->CtorInit);
894 void matchDispatch(
const TemplateArgumentLoc *
Node) {
895 matchWithoutFilter(*
Node, Matchers->TemplateArgumentLoc);
897 void matchDispatch(
const void *) { }
902 bool matchesParentOf(
const DynTypedNode &
Node,
const DynTypedMatcher &Matcher,
903 BoundNodesTreeBuilder *Builder) {
904 for (
const auto &
Parent : ActiveASTContext->getParents(
Node)) {
905 BoundNodesTreeBuilder BuilderCopy = *Builder;
906 if (Matcher.matches(
Parent,
this, &BuilderCopy)) {
907 *Builder = std::move(BuilderCopy);
931 const DynTypedMatcher &Matcher,
932 BoundNodesTreeBuilder *Builder) {
937 std::vector<MatchKey> Keys;
939 auto Finish = [&](
bool Matched) {
940 for (
const auto &Key : Keys) {
941 MemoizedMatchResult &CachedResult = ResultCache[Key];
942 CachedResult.ResultOfMatch = Matched;
943 CachedResult.Nodes = *Builder;
949 DynTypedNodeList Parents{ArrayRef<DynTypedNode>()};
952 if (Builder->isComparable()) {
954 Keys.back().MatcherID = Matcher.getID();
955 Keys.back().Node =
Node;
956 Keys.back().BoundNodes = *Builder;
957 Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
958 Keys.back().Type = MatchType::Ancestors;
961 MemoizationMap::iterator I = ResultCache.find(Keys.back());
962 if (I != ResultCache.end()) {
964 *Builder = I->second.Nodes;
965 return Finish(I->second.ResultOfMatch);
969 Parents = ActiveASTContext->getParents(
Node);
972 if (Parents.size() != 1)
976 Node = *Parents.begin();
977 BoundNodesTreeBuilder BuilderCopy = *Builder;
978 if (Matcher.matches(
Node,
this, &BuilderCopy)) {
979 *Builder = std::move(BuilderCopy);
985 if (Parents.empty()) {
993 if (!
Node.get<TranslationUnitDecl>() &&
995 llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
996 return D->getKind() == Decl::TranslationUnit;
998 llvm::errs() <<
"Tried to match orphan node:\n";
999 Node.dump(llvm::errs(), *ActiveASTContext);
1000 llvm_unreachable(
"Parent map should be complete!");
1004 assert(Parents.size() > 1);
1008 std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1010 while (!Queue.empty()) {
1011 BoundNodesTreeBuilder BuilderCopy = *Builder;
1012 if (Matcher.matches(Queue.front(),
this, &BuilderCopy)) {
1013 *Builder = std::move(BuilderCopy);
1014 return Finish(
true);
1016 for (
const auto &
Parent : ActiveASTContext->getParents(Queue.front())) {
1020 if (Visited.insert(
Parent.getMemoizationData()).second)
1026 return Finish(
false);
1031 class MatchVisitor :
public BoundNodesTreeBuilder::Visitor {
1033 MatchVisitor(ASTContext* Context,
1034 MatchFinder::MatchCallback* Callback)
1036 Callback(Callback) {}
1038 void visitMatch(
const BoundNodes& BoundNodesView)
override {
1039 TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
1044 ASTContext* Context;
1045 MatchFinder::MatchCallback* Callback;
1049 bool typeHasMatchingAlias(
const Type *TypeNode,
1050 const Matcher<NamedDecl> &Matcher,
1051 BoundNodesTreeBuilder *Builder) {
1052 const Type *
const CanonicalType =
1053 ActiveASTContext->getCanonicalType(TypeNode);
1054 auto Aliases = TypeAliases.find(CanonicalType);
1055 if (Aliases == TypeAliases.end())
1057 for (
const TypedefNameDecl *Alias : Aliases->second) {
1058 BoundNodesTreeBuilder Result(*Builder);
1059 if (Matcher.matches(*Alias,
this, &Result)) {
1060 *Builder = std::move(Result);
1068 objcClassHasMatchingCompatibilityAlias(
const ObjCInterfaceDecl *InterfaceDecl,
1069 const Matcher<NamedDecl> &Matcher,
1070 BoundNodesTreeBuilder *Builder) {
1071 auto Aliases = CompatibleAliases.find(InterfaceDecl);
1072 if (Aliases == CompatibleAliases.end())
1074 for (
const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1075 BoundNodesTreeBuilder Result(*Builder);
1076 if (Matcher.matches(*Alias,
this, &Result)) {
1077 *Builder = std::move(Result);
1087 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1089 const MatchFinder::MatchersByType *Matchers;
1097 llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1099 const MatchFinder::MatchFinderOptions &Options;
1100 ASTContext *ActiveASTContext;
1103 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1106 llvm::DenseMap<
const ObjCInterfaceDecl *,
1111 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1112 MemoizationMap ResultCache;
1115 static CXXRecordDecl *
1116 getAsCXXRecordDeclOrPrimaryTemplate(
const Type *TypeNode) {
1117 if (
auto *RD = TypeNode->getAsCXXRecordDecl())
1121 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1122 while (TemplateType && TemplateType->isTypeAlias())
1124 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1129 if (
auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1130 TemplateType->getTemplateName().getAsTemplateDecl()))
1131 return ClassTemplate->getTemplatedDecl();
1139 bool MatchASTVisitor::classIsDerivedFrom(
const CXXRecordDecl *Declaration,
1140 const Matcher<NamedDecl> &
Base,
1141 BoundNodesTreeBuilder *Builder,
1146 const Type *TypeNode = It.getType().getTypePtr();
1148 if (typeHasMatchingAlias(TypeNode,
Base, Builder))
1154 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1157 if (ClassDecl == Declaration) {
1161 BoundNodesTreeBuilder Result(*Builder);
1162 if (
Base.matches(*ClassDecl,
this, &Result)) {
1163 *Builder = std::move(Result);
1166 if (!Directly && classIsDerivedFrom(ClassDecl,
Base, Builder, Directly))
1175 bool MatchASTVisitor::objcClassIsDerivedFrom(
1176 const ObjCInterfaceDecl *Declaration,
const Matcher<NamedDecl> &
Base,
1177 BoundNodesTreeBuilder *Builder,
bool Directly) {
1179 for (
const ObjCInterfaceDecl *ClassDecl =
Declaration->getSuperClass();
1180 ClassDecl !=
nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1182 if (objcClassHasMatchingCompatibilityAlias(ClassDecl,
Base, Builder))
1186 const Type *TypeNode = ClassDecl->getTypeForDecl();
1187 if (typeHasMatchingAlias(TypeNode,
Base, Builder))
1190 if (
Base.matches(*ClassDecl,
this, Builder))
1201 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1206 bool ScopedTraversal =
1207 TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1208 bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1210 if (
const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1211 auto SK = CTSD->getSpecializationKind();
1214 ScopedChildren =
true;
1215 }
else if (
const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1216 if (FD->isDefaulted())
1217 ScopedChildren =
true;
1218 if (FD->isTemplateInstantiation())
1219 ScopedTraversal =
true;
1220 }
else if (isa<BindingDecl>(DeclNode)) {
1221 ScopedChildren =
true;
1224 ASTNodeNotSpelledInSourceScope RAII1(
this, ScopedTraversal);
1225 ASTChildrenNotSpelledInSourceScope RAII2(
this, ScopedChildren);
1231 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1235 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1236 TraversingASTChildrenNotSpelledInSource;
1238 ASTNodeNotSpelledInSourceScope RAII(
this, ScopedTraversal);
1243 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1248 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1255 match(TypeLocNode.getType());
1259 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1264 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1265 NestedNameSpecifierLoc NNS) {
1273 if (NNS.hasQualifier())
1274 match(*NNS.getNestedNameSpecifier());
1279 bool MatchASTVisitor::TraverseConstructorInitializer(
1280 CXXCtorInitializer *CtorInit) {
1284 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1285 TraversingASTChildrenNotSpelledInSource;
1287 if (!CtorInit->isWritten())
1288 ScopedTraversal =
true;
1290 ASTNodeNotSpelledInSourceScope RAII1(
this, ScopedTraversal);
1298 bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1303 class MatchASTConsumer :
public ASTConsumer {
1305 MatchASTConsumer(MatchFinder *Finder,
1306 MatchFinder::ParsingDoneTestCallback *ParsingDone)
1307 : Finder(Finder), ParsingDone(ParsingDone) {}
1310 void HandleTranslationUnit(ASTContext &Context)
override {
1311 if (ParsingDone !=
nullptr) {
1314 Finder->matchAST(Context);
1317 MatchFinder *Finder;
1318 MatchFinder::ParsingDoneTestCallback *ParsingDone;
1333 : Options(
std::move(Options)), ParsingDone(nullptr) {}
1343 Matchers.DeclOrStmt.emplace_back(
traverse(*TK, NodeMatch), Action);
1345 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1346 Matchers.AllCallbacks.insert(Action);
1351 Matchers.Type.emplace_back(NodeMatch, Action);
1352 Matchers.AllCallbacks.insert(Action);
1361 Matchers.DeclOrStmt.emplace_back(
traverse(*TK, NodeMatch), Action);
1363 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1364 Matchers.AllCallbacks.insert(Action);
1369 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1370 Matchers.AllCallbacks.insert(Action);
1375 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1376 Matchers.AllCallbacks.insert(Action);
1381 Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1382 Matchers.AllCallbacks.insert(Action);
1387 Matchers.CtorInit.emplace_back(NodeMatch, Action);
1388 Matchers.AllCallbacks.insert(Action);
1393 Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1394 Matchers.AllCallbacks.insert(Action);
1399 if (NodeMatch.canConvertTo<
Decl>()) {
1402 }
else if (NodeMatch.canConvertTo<
QualType>()) {
1405 }
else if (NodeMatch.canConvertTo<
Stmt>()) {
1414 }
else if (NodeMatch.canConvertTo<
TypeLoc>()) {
1428 return std::make_unique<internal::MatchASTConsumer>(
this, ParsingDone);
1432 internal::MatchASTVisitor Visitor(&Matchers, Options);
1433 Visitor.set_active_ast_context(&Context);
1434 Visitor.match(
Node);
1438 internal::MatchASTVisitor Visitor(&Matchers, Options);
1439 Visitor.set_active_ast_context(&Context);
1440 Visitor.onStartOfTranslationUnit();
1441 Visitor.TraverseAST(Context);
1442 Visitor.onEndOfTranslationUnit();
1447 ParsingDone = NewParsingDone;