1802 lines · cpp
1//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Implements an algorithm to efficiently search for matches on AST nodes.10// Uses memoization to support recursive matches like HasDescendant.11//12// The general idea is to visit all AST nodes with a RecursiveASTVisitor,13// calling the Matches(...) method of each matcher we are running on each14// AST node. The matcher can recurse via the ASTMatchFinder interface.15//16//===----------------------------------------------------------------------===//17 18#include "clang/ASTMatchers/ASTMatchFinder.h"19#include "clang/AST/ASTConsumer.h"20#include "clang/AST/ASTContext.h"21#include "clang/AST/DeclCXX.h"22#include "clang/AST/RecursiveASTVisitor.h"23#include "llvm/ADT/DenseMap.h"24#include "llvm/ADT/SmallPtrSet.h"25#include "llvm/ADT/StringMap.h"26#include "llvm/Support/PrettyStackTrace.h"27#include "llvm/Support/Timer.h"28#include <deque>29#include <memory>30#include <set>31 32namespace clang {33namespace ast_matchers {34namespace internal {35namespace {36 37typedef MatchFinder::MatchCallback MatchCallback;38 39// The maximum number of memoization entries to store.40// 10k has been experimentally found to give a good trade-off41// of performance vs. memory consumption by running matcher42// that match on every statement over a very large codebase.43//44// FIXME: Do some performance optimization in general and45// revisit this number; also, put up micro-benchmarks that we can46// optimize this on.47static const unsigned MaxMemoizationEntries = 10000;48 49enum class MatchType {50 Ancestors,51 52 Descendants,53 Child,54};55 56// We use memoization to avoid running the same matcher on the same57// AST node twice. This struct is the key for looking up match58// result. It consists of an ID of the MatcherInterface (for59// identifying the matcher), a pointer to the AST node and the60// bound nodes before the matcher was executed.61//62// We currently only memoize on nodes whose pointers identify the63// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).64// For \c QualType and \c TypeLoc it is possible to implement65// generation of keys for each type.66// FIXME: Benchmark whether memoization of non-pointer typed nodes67// provides enough benefit for the additional amount of code.68struct MatchKey {69 DynTypedMatcher::MatcherIDType MatcherID;70 DynTypedNode Node;71 BoundNodesTreeBuilder BoundNodes;72 TraversalKind Traversal = TK_AsIs;73 MatchType Type;74 75 bool operator<(const MatchKey &Other) const {76 return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <77 std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,78 Other.BoundNodes);79 }80};81 82// Used to store the result of a match and possibly bound nodes.83struct MemoizedMatchResult {84 bool ResultOfMatch;85 BoundNodesTreeBuilder Nodes;86};87 88// A RecursiveASTVisitor that traverses all children or all descendants of89// a node.90class MatchChildASTVisitor91 : public RecursiveASTVisitor<MatchChildASTVisitor> {92public:93 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;94 95 // Creates an AST visitor that matches 'matcher' on all children or96 // descendants of a traversed node. max_depth is the maximum depth97 // to traverse: use 1 for matching the children and INT_MAX for98 // matching the descendants.99 MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,100 BoundNodesTreeBuilder *Builder, int MaxDepth,101 bool IgnoreImplicitChildren,102 ASTMatchFinder::BindKind Bind)103 : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),104 MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),105 Bind(Bind), Matches(false) {}106 107 // Returns true if a match is found in the subtree rooted at the108 // given AST node. This is done via a set of mutually recursive109 // functions. Here's how the recursion is done (the *wildcard can110 // actually be Decl, Stmt, or Type):111 //112 // - Traverse(node) calls BaseTraverse(node) when it needs113 // to visit the descendants of node.114 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))115 // Traverse*(c) for each child c of 'node'.116 // - Traverse*(c) in turn calls Traverse(c), completing the117 // recursion.118 bool findMatch(const DynTypedNode &DynNode) {119 reset();120 if (const Decl *D = DynNode.get<Decl>())121 traverse(*D);122 else if (const Stmt *S = DynNode.get<Stmt>())123 traverse(*S);124 else if (const NestedNameSpecifier *NNS =125 DynNode.get<NestedNameSpecifier>())126 traverse(*NNS);127 else if (const NestedNameSpecifierLoc *NNSLoc =128 DynNode.get<NestedNameSpecifierLoc>())129 traverse(*NNSLoc);130 else if (const QualType *Q = DynNode.get<QualType>())131 traverse(*Q, /*TraverseQualifier=*/true);132 else if (const TypeLoc *T = DynNode.get<TypeLoc>())133 traverse(*T, /*TraverseQualifier=*/true);134 else if (const auto *C = DynNode.get<CXXCtorInitializer>())135 traverse(*C);136 else if (const TemplateArgumentLoc *TALoc =137 DynNode.get<TemplateArgumentLoc>())138 traverse(*TALoc);139 else if (const Attr *A = DynNode.get<Attr>())140 traverse(*A);141 // FIXME: Add other base types after adding tests.142 143 // It's OK to always overwrite the bound nodes, as if there was144 // no match in this recursive branch, the result set is empty145 // anyway.146 *Builder = ResultBindings;147 148 return Matches;149 }150 151 // The following are overriding methods from the base visitor class.152 // They are public only to allow CRTP to work. They are *not *part153 // of the public API of this class.154 bool TraverseDecl(Decl *DeclNode) {155 156 if (DeclNode && DeclNode->isImplicit() &&157 Finder->isTraversalIgnoringImplicitNodes())158 return baseTraverse(*DeclNode);159 160 ScopedIncrement ScopedDepth(&CurrentDepth);161 return (DeclNode == nullptr) || traverse(*DeclNode);162 }163 164 Stmt *getStmtToTraverse(Stmt *StmtNode) {165 Stmt *StmtToTraverse = StmtNode;166 if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {167 auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);168 if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())169 StmtToTraverse = LambdaNode;170 else171 StmtToTraverse =172 Finder->getASTContext().getParentMapContext().traverseIgnored(173 ExprNode);174 }175 return StmtToTraverse;176 }177 178 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {179 // If we need to keep track of the depth, we can't perform data recursion.180 if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))181 Queue = nullptr;182 183 ScopedIncrement ScopedDepth(&CurrentDepth);184 Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);185 if (!StmtToTraverse)186 return true;187 188 if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))189 return true;190 191 if (!match(*StmtToTraverse))192 return false;193 return VisitorBase::TraverseStmt(StmtToTraverse, Queue);194 }195 // We assume that the QualType and the contained type are on the same196 // hierarchy level. Thus, we try to match either of them.197 bool TraverseType(QualType TypeNode, bool TraverseQualifier = true) {198 if (TypeNode.isNull())199 return true;200 ScopedIncrement ScopedDepth(&CurrentDepth);201 // Match the Type.202 if (!match(*TypeNode))203 return false;204 // The QualType is matched inside traverse.205 return traverse(TypeNode, TraverseQualifier);206 }207 // We assume that the TypeLoc, contained QualType and contained Type all are208 // on the same hierarchy level. Thus, we try to match all of them.209 bool TraverseTypeLoc(TypeLoc TypeLocNode, bool TraverseQualifier = true) {210 if (TypeLocNode.isNull())211 return true;212 ScopedIncrement ScopedDepth(&CurrentDepth);213 // Match the Type.214 if (!match(*TypeLocNode.getType()))215 return false;216 // Match the QualType.217 if (!match(TypeLocNode.getType()))218 return false;219 // The TypeLoc is matched inside traverse.220 return traverse(TypeLocNode, TraverseQualifier);221 }222 bool TraverseNestedNameSpecifier(NestedNameSpecifier NNS) {223 ScopedIncrement ScopedDepth(&CurrentDepth);224 return !NNS || traverse(NNS);225 }226 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {227 if (!NNS)228 return true;229 ScopedIncrement ScopedDepth(&CurrentDepth);230 if (!match(NNS.getNestedNameSpecifier()))231 return false;232 return traverse(NNS);233 }234 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {235 if (!CtorInit)236 return true;237 ScopedIncrement ScopedDepth(&CurrentDepth);238 return traverse(*CtorInit);239 }240 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {241 ScopedIncrement ScopedDepth(&CurrentDepth);242 return traverse(TAL);243 }244 bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {245 if (!Finder->isTraversalIgnoringImplicitNodes())246 return VisitorBase::TraverseCXXForRangeStmt(Node);247 if (!Node)248 return true;249 ScopedIncrement ScopedDepth(&CurrentDepth);250 if (auto *Init = Node->getInit())251 if (!traverse(*Init))252 return false;253 if (!match(*Node->getLoopVariable()))254 return false;255 if (match(*Node->getRangeInit()))256 if (!VisitorBase::TraverseStmt(Node->getRangeInit()))257 return false;258 if (!match(*Node->getBody()))259 return false;260 return VisitorBase::TraverseStmt(Node->getBody());261 }262 bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {263 if (!Finder->isTraversalIgnoringImplicitNodes())264 return VisitorBase::TraverseCXXRewrittenBinaryOperator(Node);265 if (!Node)266 return true;267 ScopedIncrement ScopedDepth(&CurrentDepth);268 269 return match(*Node->getLHS()) && match(*Node->getRHS());270 }271 bool TraverseAttr(Attr *A) {272 if (A == nullptr ||273 (A->isImplicit() &&274 Finder->getASTContext().getParentMapContext().getTraversalKind() ==275 TK_IgnoreUnlessSpelledInSource))276 return true;277 ScopedIncrement ScopedDepth(&CurrentDepth);278 return traverse(*A);279 }280 bool TraverseLambdaExpr(LambdaExpr *Node) {281 if (!Finder->isTraversalIgnoringImplicitNodes())282 return VisitorBase::TraverseLambdaExpr(Node);283 if (!Node)284 return true;285 ScopedIncrement ScopedDepth(&CurrentDepth);286 287 for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {288 const LambdaCapture *C = Node->capture_begin() + I;289 if (!C->isExplicit())290 continue;291 if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))292 return false;293 const Expr *CIE = Node->capture_init_begin()[I];294 if (CIE != nullptr && !match(*CIE))295 return false;296 }297 298 if (const auto *TPL = Node->getTemplateParameterList()) {299 for (const auto *TP : *TPL) {300 if (!match(*TP))301 return false;302 }303 }304 305 for (const auto *P : Node->getCallOperator()->parameters()) {306 if (!match(*P))307 return false;308 }309 310 if (!match(*Node->getBody()))311 return false;312 313 return VisitorBase::TraverseStmt(Node->getBody());314 }315 316 bool shouldVisitTemplateInstantiations() const { return true; }317 bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }318 319private:320 // Used for updating the depth during traversal.321 struct ScopedIncrement {322 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }323 ~ScopedIncrement() { --(*Depth); }324 325 private:326 int *Depth;327 };328 329 // Resets the state of this object.330 void reset() {331 Matches = false;332 CurrentDepth = 0;333 }334 335 // Forwards the call to the corresponding Traverse*() method in the336 // base visitor class.337 bool baseTraverse(const Decl &DeclNode) {338 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));339 }340 bool baseTraverse(const Stmt &StmtNode) {341 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));342 }343 bool baseTraverse(QualType TypeNode, bool TraverseQualifier) {344 return VisitorBase::TraverseType(TypeNode, TraverseQualifier);345 }346 bool baseTraverse(TypeLoc TypeLocNode, bool TraverseQualifier) {347 return VisitorBase::TraverseTypeLoc(TypeLocNode, TraverseQualifier);348 }349 bool baseTraverse(NestedNameSpecifier NNS) {350 return VisitorBase::TraverseNestedNameSpecifier(NNS);351 }352 bool baseTraverse(NestedNameSpecifierLoc NNS) {353 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);354 }355 bool baseTraverse(const CXXCtorInitializer &CtorInit) {356 return VisitorBase::TraverseConstructorInitializer(357 const_cast<CXXCtorInitializer *>(&CtorInit));358 }359 bool baseTraverse(TemplateArgumentLoc TAL) {360 return VisitorBase::TraverseTemplateArgumentLoc(TAL);361 }362 bool baseTraverse(const Attr &AttrNode) {363 return VisitorBase::TraverseAttr(const_cast<Attr *>(&AttrNode));364 }365 366 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:367 // 0 < CurrentDepth <= MaxDepth.368 //369 // Returns 'true' if traversal should continue after this function370 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.371 template <typename T>372 bool match(const T &Node) {373 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {374 return true;375 }376 if (Bind != ASTMatchFinder::BK_All) {377 BoundNodesTreeBuilder RecursiveBuilder(*Builder);378 if (Matcher->matches(DynTypedNode::create(Node), Finder,379 &RecursiveBuilder)) {380 Matches = true;381 ResultBindings.addMatch(RecursiveBuilder);382 return false; // Abort as soon as a match is found.383 }384 } else {385 BoundNodesTreeBuilder RecursiveBuilder(*Builder);386 if (Matcher->matches(DynTypedNode::create(Node), Finder,387 &RecursiveBuilder)) {388 // After the first match the matcher succeeds.389 Matches = true;390 ResultBindings.addMatch(RecursiveBuilder);391 }392 }393 return true;394 }395 396 // Traverses the subtree rooted at 'Node'; returns true if the397 // traversal should continue after this function returns.398 template <typename T, class... Args>399 bool traverse(const T &Node, Args &&...args) {400 static_assert(IsBaseType<T>::value,401 "traverse can only be instantiated with base type");402 if (!match(Node))403 return false;404 return baseTraverse(Node, std::forward<Args>(args)...);405 }406 407 const DynTypedMatcher *const Matcher;408 ASTMatchFinder *const Finder;409 BoundNodesTreeBuilder *const Builder;410 BoundNodesTreeBuilder ResultBindings;411 int CurrentDepth;412 const int MaxDepth;413 const bool IgnoreImplicitChildren;414 const ASTMatchFinder::BindKind Bind;415 bool Matches;416};417 418// Controls the outermost traversal of the AST and allows to match multiple419// matchers.420class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,421 public ASTMatchFinder {422public:423 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,424 const MatchFinder::MatchFinderOptions &Options)425 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}426 427 ~MatchASTVisitor() override {428 if (Options.CheckProfiling) {429 Options.CheckProfiling->Records = std::move(TimeByBucket);430 }431 }432 433 void onStartOfTranslationUnit() {434 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();435 TimeBucketRegion Timer;436 for (MatchCallback *MC : Matchers->AllCallbacks) {437 if (EnableCheckProfiling)438 Timer.setBucket(&TimeByBucket[MC->getID()]);439 MC->onStartOfTranslationUnit();440 }441 }442 443 void onEndOfTranslationUnit() {444 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();445 TimeBucketRegion Timer;446 for (MatchCallback *MC : Matchers->AllCallbacks) {447 if (EnableCheckProfiling)448 Timer.setBucket(&TimeByBucket[MC->getID()]);449 MC->onEndOfTranslationUnit();450 }451 }452 453 void set_active_ast_context(ASTContext *NewActiveASTContext) {454 ActiveASTContext = NewActiveASTContext;455 }456 457 // The following Visit*() and Traverse*() functions "override"458 // methods in RecursiveASTVisitor.459 460 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {461 // When we see 'typedef A B', we add name 'B' to the set of names462 // A's canonical type maps to. This is necessary for implementing463 // isDerivedFrom(x) properly, where x can be the name of the base464 // class or any of its aliases.465 //466 // In general, the is-alias-of (as defined by typedefs) relation467 // is tree-shaped, as you can typedef a type more than once. For468 // example,469 //470 // typedef A B;471 // typedef A C;472 // typedef C D;473 // typedef C E;474 //475 // gives you476 //477 // A478 // |- B479 // `- C480 // |- D481 // `- E482 //483 // It is wrong to assume that the relation is a chain. A correct484 // implementation of isDerivedFrom() needs to recognize that B and485 // E are aliases, even though neither is a typedef of the other.486 // Therefore, we cannot simply walk through one typedef chain to487 // find out whether the type name matches.488 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();489 const Type *CanonicalType = // root of the typedef tree490 ActiveASTContext->getCanonicalType(TypeNode);491 TypeAliases[CanonicalType].insert(DeclNode);492 return true;493 }494 495 bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {496 const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();497 CompatibleAliases[InterfaceDecl].insert(CAD);498 return true;499 }500 501 bool TraverseDecl(Decl *DeclNode);502 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);503 bool TraverseType(QualType TypeNode, bool TraverseQualifier = true);504 bool TraverseTypeLoc(TypeLoc TypeNode, bool TraverseQualifier = true);505 bool TraverseNestedNameSpecifier(NestedNameSpecifier NNS);506 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);507 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);508 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);509 bool TraverseAttr(Attr *AttrNode);510 511 bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {512 if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {513 {514 ASTNodeNotAsIsSourceScope RAII(this, true);515 TraverseStmt(RF->getInit());516 // Don't traverse under the loop variable517 match(*RF->getLoopVariable());518 TraverseStmt(RF->getRangeInit());519 }520 {521 ASTNodeNotSpelledInSourceScope RAII(this, true);522 for (auto *SubStmt : RF->children()) {523 if (SubStmt != RF->getBody())524 TraverseStmt(SubStmt);525 }526 }527 TraverseStmt(RF->getBody());528 return true;529 } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {530 {531 ASTNodeNotAsIsSourceScope RAII(this, true);532 TraverseStmt(const_cast<Expr *>(RBO->getLHS()));533 TraverseStmt(const_cast<Expr *>(RBO->getRHS()));534 }535 {536 ASTNodeNotSpelledInSourceScope RAII(this, true);537 for (auto *SubStmt : RBO->children()) {538 TraverseStmt(SubStmt);539 }540 }541 return true;542 } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {543 for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {544 auto C = std::get<0>(I);545 ASTNodeNotSpelledInSourceScope RAII(546 this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());547 TraverseLambdaCapture(LE, &C, std::get<1>(I));548 }549 550 {551 ASTNodeNotSpelledInSourceScope RAII(this, true);552 TraverseDecl(LE->getLambdaClass());553 }554 {555 ASTNodeNotAsIsSourceScope RAII(this, true);556 557 // We need to poke around to find the bits that might be explicitly558 // written.559 TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();560 FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();561 562 if (auto *TPL = LE->getTemplateParameterList()) {563 for (NamedDecl *D : *TPL) {564 TraverseDecl(D);565 }566 if (Expr *RequiresClause = TPL->getRequiresClause()) {567 TraverseStmt(RequiresClause);568 }569 }570 571 if (LE->hasExplicitParameters()) {572 // Visit parameters.573 for (ParmVarDecl *Param : Proto.getParams())574 TraverseDecl(Param);575 }576 577 const auto *T = Proto.getTypePtr();578 for (const auto &E : T->exceptions())579 TraverseType(E, /*TraverseQualifier=*/true);580 581 if (Expr *NE = T->getNoexceptExpr())582 TraverseStmt(NE, Queue);583 584 if (LE->hasExplicitResultType())585 TraverseTypeLoc(Proto.getReturnLoc(), /*TraverseQualifier=*/true);586 TraverseStmt(587 const_cast<Expr *>(LE->getTrailingRequiresClause().ConstraintExpr));588 }589 590 TraverseStmt(LE->getBody());591 return true;592 }593 return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);594 }595 596 // Matches children or descendants of 'Node' with 'BaseMatcher'.597 bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,598 const DynTypedMatcher &Matcher,599 BoundNodesTreeBuilder *Builder, int MaxDepth,600 BindKind Bind) {601 // For AST-nodes that don't have an identity, we can't memoize.602 if (!Node.getMemoizationData() || !Builder->isComparable())603 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);604 605 MatchKey Key;606 Key.MatcherID = Matcher.getID();607 Key.Node = Node;608 // Note that we key on the bindings *before* the match.609 Key.BoundNodes = *Builder;610 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();611 // Memoize result even doing a single-level match, it might be expensive.612 Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;613 MemoizationMap::iterator I = ResultCache.find(Key);614 if (I != ResultCache.end()) {615 *Builder = I->second.Nodes;616 return I->second.ResultOfMatch;617 }618 619 MemoizedMatchResult Result;620 Result.Nodes = *Builder;621 Result.ResultOfMatch =622 matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);623 624 MemoizedMatchResult &CachedResult = ResultCache[Key];625 CachedResult = std::move(Result);626 627 *Builder = CachedResult.Nodes;628 return CachedResult.ResultOfMatch;629 }630 631 // Matches children or descendants of 'Node' with 'BaseMatcher'.632 bool matchesRecursively(const DynTypedNode &Node,633 const DynTypedMatcher &Matcher,634 BoundNodesTreeBuilder *Builder, int MaxDepth,635 BindKind Bind) {636 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||637 TraversingASTChildrenNotSpelledInSource;638 639 bool IgnoreImplicitChildren = false;640 641 if (isTraversalIgnoringImplicitNodes()) {642 IgnoreImplicitChildren = true;643 }644 645 ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);646 647 MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,648 IgnoreImplicitChildren, Bind);649 return Visitor.findMatch(Node);650 }651 652 bool classIsDerivedFrom(const CXXRecordDecl *Declaration,653 const Matcher<NamedDecl> &Base,654 BoundNodesTreeBuilder *Builder,655 bool Directly) override;656 657private:658 bool659 classIsDerivedFromImpl(const CXXRecordDecl *Declaration,660 const Matcher<NamedDecl> &Base,661 BoundNodesTreeBuilder *Builder, bool Directly,662 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited);663 664public:665 bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,666 const Matcher<NamedDecl> &Base,667 BoundNodesTreeBuilder *Builder,668 bool Directly) override;669 670public:671 // Implements ASTMatchFinder::matchesChildOf.672 bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,673 const DynTypedMatcher &Matcher,674 BoundNodesTreeBuilder *Builder, BindKind Bind) override {675 if (ResultCache.size() > MaxMemoizationEntries)676 ResultCache.clear();677 return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);678 }679 // Implements ASTMatchFinder::matchesDescendantOf.680 bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,681 const DynTypedMatcher &Matcher,682 BoundNodesTreeBuilder *Builder,683 BindKind Bind) override {684 if (ResultCache.size() > MaxMemoizationEntries)685 ResultCache.clear();686 return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,687 Bind);688 }689 // Implements ASTMatchFinder::matchesAncestorOf.690 bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,691 const DynTypedMatcher &Matcher,692 BoundNodesTreeBuilder *Builder,693 AncestorMatchMode MatchMode) override {694 // Reset the cache outside of the recursive call to make sure we695 // don't invalidate any iterators.696 if (ResultCache.size() > MaxMemoizationEntries)697 ResultCache.clear();698 if (MatchMode == AncestorMatchMode::AMM_ParentOnly)699 return matchesParentOf(Node, Matcher, Builder);700 return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);701 }702 703 // Matches all registered matchers on the given node and calls the704 // result callback for every node that matches.705 void match(const DynTypedNode &Node) {706 // FIXME: Improve this with a switch or a visitor pattern.707 if (auto *N = Node.get<Decl>()) {708 match(*N);709 } else if (auto *N = Node.get<Stmt>()) {710 match(*N);711 } else if (auto *N = Node.get<Type>()) {712 match(*N);713 } else if (auto *N = Node.get<QualType>()) {714 match(*N);715 } else if (auto *N = Node.get<NestedNameSpecifier>()) {716 match(*N);717 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {718 match(*N);719 } else if (auto *N = Node.get<TypeLoc>()) {720 match(*N);721 } else if (auto *N = Node.get<CXXCtorInitializer>()) {722 match(*N);723 } else if (auto *N = Node.get<TemplateArgumentLoc>()) {724 match(*N);725 } else if (auto *N = Node.get<Attr>()) {726 match(*N);727 }728 }729 730 template <typename T> void match(const T &Node) {731 matchDispatch(&Node);732 }733 734 // Implements ASTMatchFinder::getASTContext.735 ASTContext &getASTContext() const override { return *ActiveASTContext; }736 737 bool shouldVisitTemplateInstantiations() const { return true; }738 bool shouldVisitImplicitCode() const { return true; }739 740 // We visit the lambda body explicitly, so instruct the RAV741 // to not visit it on our behalf too.742 bool shouldVisitLambdaBody() const { return false; }743 744 bool IsMatchingInASTNodeNotSpelledInSource() const override {745 return TraversingASTNodeNotSpelledInSource;746 }747 bool isMatchingChildrenNotSpelledInSource() const override {748 return TraversingASTChildrenNotSpelledInSource;749 }750 void setMatchingChildrenNotSpelledInSource(bool Set) override {751 TraversingASTChildrenNotSpelledInSource = Set;752 }753 754 bool IsMatchingInASTNodeNotAsIs() const override {755 return TraversingASTNodeNotAsIs;756 }757 758 bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {759 ASTNodeNotSpelledInSourceScope RAII(this, true);760 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(761 D);762 }763 764 bool TraverseTemplateInstantiations(VarTemplateDecl *D) {765 ASTNodeNotSpelledInSourceScope RAII(this, true);766 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(767 D);768 }769 770 bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {771 ASTNodeNotSpelledInSourceScope RAII(this, true);772 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(773 D);774 }775 776private:777 bool TraversingASTNodeNotSpelledInSource = false;778 bool TraversingASTNodeNotAsIs = false;779 bool TraversingASTChildrenNotSpelledInSource = false;780 781 class CurMatchData {782// We don't have enough free low bits in 32bit builds to discriminate 8 pointer783// types in PointerUnion. so split the union in 2 using a free bit from the784// callback pointer.785#define CMD_TYPES_0 \786 const QualType *, const TypeLoc *, const NestedNameSpecifier *, \787 const NestedNameSpecifierLoc *788#define CMD_TYPES_1 \789 const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *, \790 const DynTypedNode *791 792#define IMPL(Index) \793 template <typename NodeType> \794 std::enable_if_t< \795 llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value> \796 SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) { \797 assertEmpty(); \798 Callback.setPointerAndInt(CB, Index); \799 Node##Index = &N; \800 } \801 \802 template <typename T> \803 std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value, \804 const T *> \805 getNode() const { \806 assertHoldsState(); \807 return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>() \808 : nullptr; \809 }810 811 public:812 CurMatchData() : Node0(nullptr) {}813 814 IMPL(0)815 IMPL(1)816 817 const MatchCallback *getCallback() const { return Callback.getPointer(); }818 819 void SetBoundNodes(const BoundNodes &BN) {820 assertHoldsState();821 BNodes = &BN;822 }823 824 void clearBoundNodes() {825 assertHoldsState();826 BNodes = nullptr;827 }828 829 const BoundNodes *getBoundNodes() const {830 assertHoldsState();831 return BNodes;832 }833 834 void reset() {835 assertHoldsState();836 Callback.setPointerAndInt(nullptr, 0);837 Node0 = nullptr;838 }839 840 private:841 void assertHoldsState() const {842 assert(Callback.getPointer() != nullptr && !Node0.isNull());843 }844 845 void assertEmpty() const {846 assert(Callback.getPointer() == nullptr && Node0.isNull() &&847 BNodes == nullptr);848 }849 850 llvm::PointerIntPair<const MatchCallback *, 1> Callback;851 union {852 llvm::PointerUnion<CMD_TYPES_0> Node0;853 llvm::PointerUnion<CMD_TYPES_1> Node1;854 };855 const BoundNodes *BNodes = nullptr;856 857#undef CMD_TYPES_0858#undef CMD_TYPES_1859#undef IMPL860 } CurMatchState;861 862 struct CurMatchRAII {863 template <typename NodeType>864 CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,865 const NodeType &NT)866 : MV(MV) {867 MV.CurMatchState.SetCallbackAndRawNode(CB, NT);868 }869 870 ~CurMatchRAII() { MV.CurMatchState.reset(); }871 872 private:873 MatchASTVisitor &MV;874 };875 876public:877 class TraceReporter : llvm::PrettyStackTraceEntry {878 static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,879 raw_ostream &OS) {880 if (const auto *D = Node.get<Decl>()) {881 OS << D->getDeclKindName() << "Decl ";882 if (const auto *ND = dyn_cast<NamedDecl>(D)) {883 ND->printQualifiedName(OS);884 OS << " : ";885 } else886 OS << ": ";887 D->getSourceRange().print(OS, Ctx.getSourceManager());888 } else if (const auto *S = Node.get<Stmt>()) {889 OS << S->getStmtClassName() << " : ";890 S->getSourceRange().print(OS, Ctx.getSourceManager());891 } else if (const auto *T = Node.get<Type>()) {892 OS << T->getTypeClassName() << "Type : ";893 QualType(T, 0).print(OS, Ctx.getPrintingPolicy());894 } else if (const auto *QT = Node.get<QualType>()) {895 OS << "QualType : ";896 QT->print(OS, Ctx.getPrintingPolicy());897 } else {898 OS << Node.getNodeKind().asStringRef() << " : ";899 Node.getSourceRange().print(OS, Ctx.getSourceManager());900 }901 }902 903 static void dumpNodeFromState(const ASTContext &Ctx,904 const CurMatchData &State, raw_ostream &OS) {905 if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {906 dumpNode(Ctx, *MatchNode, OS);907 } else if (const auto *QT = State.getNode<QualType>()) {908 dumpNode(Ctx, DynTypedNode::create(*QT), OS);909 } else if (const auto *TL = State.getNode<TypeLoc>()) {910 dumpNode(Ctx, DynTypedNode::create(*TL), OS);911 } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {912 dumpNode(Ctx, DynTypedNode::create(*NNS), OS);913 } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {914 dumpNode(Ctx, DynTypedNode::create(*NNSL), OS);915 } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {916 dumpNode(Ctx, DynTypedNode::create(*CtorInit), OS);917 } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {918 dumpNode(Ctx, DynTypedNode::create(*TAL), OS);919 } else if (const auto *At = State.getNode<Attr>()) {920 dumpNode(Ctx, DynTypedNode::create(*At), OS);921 }922 }923 924 public:925 TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}926 void print(raw_ostream &OS) const override {927 const CurMatchData &State = MV.CurMatchState;928 const MatchCallback *CB = State.getCallback();929 if (!CB) {930 OS << "ASTMatcher: Not currently matching\n";931 return;932 }933 934 assert(MV.ActiveASTContext &&935 "ActiveASTContext should be set if there is a matched callback");936 937 ASTContext &Ctx = MV.getASTContext();938 939 if (const BoundNodes *Nodes = State.getBoundNodes()) {940 OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";941 dumpNodeFromState(Ctx, State, OS);942 const BoundNodes::IDToNodeMap &Map = Nodes->getMap();943 if (Map.empty()) {944 OS << "\nNo bound nodes\n";945 return;946 }947 OS << "\n--- Bound Nodes Begin ---\n";948 for (const auto &Item : Map) {949 OS << " " << Item.first << " - { ";950 dumpNode(Ctx, Item.second, OS);951 OS << " }\n";952 }953 OS << "--- Bound Nodes End ---\n";954 } else {955 OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";956 dumpNodeFromState(Ctx, State, OS);957 OS << '\n';958 }959 }960 961 private:962 const MatchASTVisitor &MV;963 };964 965private:966 struct ASTNodeNotSpelledInSourceScope {967 ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)968 : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {969 V->TraversingASTNodeNotSpelledInSource = B;970 }971 ~ASTNodeNotSpelledInSourceScope() {972 MV->TraversingASTNodeNotSpelledInSource = MB;973 }974 975 private:976 MatchASTVisitor *MV;977 bool MB;978 };979 980 struct ASTNodeNotAsIsSourceScope {981 ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)982 : MV(V), MB(V->TraversingASTNodeNotAsIs) {983 V->TraversingASTNodeNotAsIs = B;984 }985 ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }986 987 private:988 MatchASTVisitor *MV;989 bool MB;990 };991 992 class TimeBucketRegion {993 public:994 TimeBucketRegion() = default;995 ~TimeBucketRegion() { setBucket(nullptr); }996 997 /// Start timing for \p NewBucket.998 ///999 /// If there was a bucket already set, it will finish the timing for that1000 /// other bucket.1001 /// \p NewBucket will be timed until the next call to \c setBucket() or1002 /// until the \c TimeBucketRegion is destroyed.1003 /// If \p NewBucket is the same as the currently timed bucket, this call1004 /// does nothing.1005 void setBucket(llvm::TimeRecord *NewBucket) {1006 if (Bucket != NewBucket) {1007 auto Now = llvm::TimeRecord::getCurrentTime(true);1008 if (Bucket)1009 *Bucket += Now;1010 if (NewBucket)1011 *NewBucket -= Now;1012 Bucket = NewBucket;1013 }1014 }1015 1016 private:1017 llvm::TimeRecord *Bucket = nullptr;1018 };1019 1020 /// Runs all the \p Matchers on \p Node.1021 ///1022 /// Used by \c matchDispatch() below.1023 template <typename T, typename MC>1024 void matchWithoutFilter(const T &Node, const MC &Matchers) {1025 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();1026 TimeBucketRegion Timer;1027 for (const auto &MP : Matchers) {1028 if (EnableCheckProfiling)1029 Timer.setBucket(&TimeByBucket[MP.second->getID()]);1030 BoundNodesTreeBuilder Builder;1031 CurMatchRAII RAII(*this, MP.second, Node);1032 if (MP.first.matches(Node, this, &Builder)) {1033 MatchVisitor Visitor(*this, ActiveASTContext, MP.second);1034 Builder.visitMatches(&Visitor);1035 }1036 }1037 }1038 1039 void matchWithFilter(const DynTypedNode &DynNode) {1040 auto Kind = DynNode.getNodeKind();1041 auto it = MatcherFiltersMap.find(Kind);1042 const auto &Filter =1043 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);1044 1045 if (Filter.empty())1046 return;1047 1048 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();1049 TimeBucketRegion Timer;1050 auto &Matchers = this->Matchers->DeclOrStmt;1051 for (unsigned short I : Filter) {1052 auto &MP = Matchers[I];1053 if (EnableCheckProfiling)1054 Timer.setBucket(&TimeByBucket[MP.second->getID()]);1055 BoundNodesTreeBuilder Builder;1056 1057 {1058 TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());1059 if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=1060 DynNode)1061 continue;1062 }1063 1064 CurMatchRAII RAII(*this, MP.second, DynNode);1065 if (MP.first.matches(DynNode, this, &Builder)) {1066 MatchVisitor Visitor(*this, ActiveASTContext, MP.second);1067 Builder.visitMatches(&Visitor);1068 }1069 }1070 }1071 1072 const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {1073 auto &Filter = MatcherFiltersMap[Kind];1074 auto &Matchers = this->Matchers->DeclOrStmt;1075 assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");1076 for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {1077 if (Matchers[I].first.canMatchNodesOfKind(Kind)) {1078 Filter.push_back(I);1079 }1080 }1081 return Filter;1082 }1083 1084 /// @{1085 /// Overloads to pair the different node types to their matchers.1086 void matchDispatch(const Decl *Node) {1087 return matchWithFilter(DynTypedNode::create(*Node));1088 }1089 void matchDispatch(const Stmt *Node) {1090 return matchWithFilter(DynTypedNode::create(*Node));1091 }1092 1093 void matchDispatch(const Type *Node) {1094 matchWithoutFilter(QualType(Node, 0), Matchers->Type);1095 }1096 void matchDispatch(const TypeLoc *Node) {1097 matchWithoutFilter(*Node, Matchers->TypeLoc);1098 }1099 void matchDispatch(const QualType *Node) {1100 matchWithoutFilter(*Node, Matchers->Type);1101 }1102 void matchDispatch(const NestedNameSpecifier *Node) {1103 matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);1104 }1105 void matchDispatch(const NestedNameSpecifierLoc *Node) {1106 matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);1107 }1108 void matchDispatch(const CXXCtorInitializer *Node) {1109 matchWithoutFilter(*Node, Matchers->CtorInit);1110 }1111 void matchDispatch(const TemplateArgumentLoc *Node) {1112 matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);1113 }1114 void matchDispatch(const Attr *Node) {1115 matchWithoutFilter(*Node, Matchers->Attr);1116 }1117 void matchDispatch(const void *) { /* Do nothing. */ }1118 /// @}1119 1120 // Returns whether a direct parent of \p Node matches \p Matcher.1121 // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.1122 bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,1123 BoundNodesTreeBuilder *Builder) {1124 for (const auto &Parent : ActiveASTContext->getParents(Node)) {1125 BoundNodesTreeBuilder BuilderCopy = *Builder;1126 if (Matcher.matches(Parent, this, &BuilderCopy)) {1127 *Builder = std::move(BuilderCopy);1128 return true;1129 }1130 }1131 return false;1132 }1133 1134 // Returns whether an ancestor of \p Node matches \p Matcher.1135 //1136 // The order of matching (which can lead to different nodes being bound in1137 // case there are multiple matches) is breadth first search.1138 //1139 // To allow memoization in the very common case of having deeply nested1140 // expressions inside a template function, we first walk up the AST, memoizing1141 // the result of the match along the way, as long as there is only a single1142 // parent.1143 //1144 // Once there are multiple parents, the breadth first search order does not1145 // allow simple memoization on the ancestors. Thus, we only memoize as long1146 // as there is a single parent.1147 //1148 // We avoid a recursive implementation to prevent excessive stack use on1149 // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).1150 bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,1151 const DynTypedMatcher &Matcher,1152 BoundNodesTreeBuilder *Builder) {1153 1154 // Memoization keys that can be updated with the result.1155 // These are the memoizable nodes in the chain of unique parents, which1156 // terminates when a node has multiple parents, or matches, or is the root.1157 std::vector<MatchKey> Keys;1158 // When returning, update the memoization cache.1159 auto Finish = [&](bool Matched) {1160 for (const auto &Key : Keys) {1161 MemoizedMatchResult &CachedResult = ResultCache[Key];1162 CachedResult.ResultOfMatch = Matched;1163 CachedResult.Nodes = *Builder;1164 }1165 return Matched;1166 };1167 1168 // Loop while there's a single parent and we want to attempt memoization.1169 DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 11170 for (;;) {1171 // A cache key only makes sense if memoization is possible.1172 if (Builder->isComparable()) {1173 Keys.emplace_back();1174 Keys.back().MatcherID = Matcher.getID();1175 Keys.back().Node = Node;1176 Keys.back().BoundNodes = *Builder;1177 Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();1178 Keys.back().Type = MatchType::Ancestors;1179 1180 // Check the cache.1181 MemoizationMap::iterator I = ResultCache.find(Keys.back());1182 if (I != ResultCache.end()) {1183 Keys.pop_back(); // Don't populate the cache for the matching node!1184 *Builder = I->second.Nodes;1185 return Finish(I->second.ResultOfMatch);1186 }1187 }1188 1189 Parents = ActiveASTContext->getParents(Node);1190 // Either no parents or multiple parents: leave chain+memoize mode and1191 // enter bfs+forgetful mode.1192 if (Parents.size() != 1)1193 break;1194 1195 // Check the next parent.1196 Node = *Parents.begin();1197 BoundNodesTreeBuilder BuilderCopy = *Builder;1198 if (Matcher.matches(Node, this, &BuilderCopy)) {1199 *Builder = std::move(BuilderCopy);1200 return Finish(true);1201 }1202 }1203 // We reached the end of the chain.1204 1205 if (Parents.empty()) {1206 // Nodes may have no parents if:1207 // a) the node is the TranslationUnitDecl1208 // b) we have a limited traversal scope that excludes the parent edges1209 // c) there is a bug in the AST, and the node is not reachable1210 // Usually the traversal scope is the whole AST, which precludes b.1211 // Bugs are common enough that it's worthwhile asserting when we can.1212#ifndef NDEBUG1213 if (!Node.get<TranslationUnitDecl>() &&1214 /* Traversal scope is full AST if any of the bounds are the TU */1215 llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {1216 return D->getKind() == Decl::TranslationUnit;1217 })) {1218 llvm::errs() << "Tried to match orphan node:\n";1219 Node.dump(llvm::errs(), *ActiveASTContext);1220 llvm_unreachable("Parent map should be complete!");1221 }1222#endif1223 } else {1224 assert(Parents.size() > 1);1225 // BFS starting from the parents not yet considered.1226 // Memoization of newly visited nodes is not possible (but we still update1227 // results for the elements in the chain we found above).1228 std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());1229 llvm::DenseSet<const void *> Visited;1230 while (!Queue.empty()) {1231 BoundNodesTreeBuilder BuilderCopy = *Builder;1232 if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {1233 *Builder = std::move(BuilderCopy);1234 return Finish(true);1235 }1236 for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {1237 // Make sure we do not visit the same node twice.1238 // Otherwise, we'll visit the common ancestors as often as there1239 // are splits on the way down.1240 if (Visited.insert(Parent.getMemoizationData()).second)1241 Queue.push_back(Parent);1242 }1243 Queue.pop_front();1244 }1245 }1246 return Finish(false);1247 }1248 1249 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with1250 // the aggregated bound nodes for each match.1251 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {1252 struct CurBoundScope {1253 CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)1254 : State(State) {1255 State.SetBoundNodes(BN);1256 }1257 1258 ~CurBoundScope() { State.clearBoundNodes(); }1259 1260 private:1261 MatchASTVisitor::CurMatchData &State;1262 };1263 1264 public:1265 MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,1266 MatchFinder::MatchCallback *Callback)1267 : State(MV.CurMatchState), Context(Context), Callback(Callback) {}1268 1269 void visitMatch(const BoundNodes& BoundNodesView) override {1270 TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());1271 CurBoundScope RAII2(State, BoundNodesView);1272 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));1273 }1274 1275 private:1276 MatchASTVisitor::CurMatchData &State;1277 ASTContext* Context;1278 MatchFinder::MatchCallback* Callback;1279 };1280 1281 // Returns true if 'TypeNode' has an alias that matches the given matcher.1282 bool typeHasMatchingAlias(const Type *TypeNode,1283 const Matcher<NamedDecl> &Matcher,1284 BoundNodesTreeBuilder *Builder) {1285 const Type *const CanonicalType =1286 ActiveASTContext->getCanonicalType(TypeNode);1287 auto Aliases = TypeAliases.find(CanonicalType);1288 if (Aliases == TypeAliases.end())1289 return false;1290 1291 auto matches = [&](const TypedefNameDecl *Alias) {1292 BoundNodesTreeBuilder Result(*Builder);1293 if (Matcher.matches(*Alias, this, &Result)) {1294 *Builder = std::move(Result);1295 return true;1296 }1297 return false;1298 };1299 1300 if (const auto *T = TypeNode->getAs<TypedefType>()) {1301 const auto *TD = T->getDecl()->getCanonicalDecl();1302 1303 // Prioritize exact matches.1304 SmallVector<const TypedefNameDecl *, 8> NonExactMatches;1305 for (const TypedefNameDecl *Alias : Aliases->second) {1306 if (!declaresSameEntity(TD, Alias)) {1307 NonExactMatches.push_back(Alias);1308 continue;1309 }1310 if (matches(Alias))1311 return true;1312 }1313 1314 for (const TypedefNameDecl *Alias : NonExactMatches) {1315 BoundNodesTreeBuilder Result(*Builder);1316 if (Matcher.matches(*Alias, this, &Result)) {1317 *Builder = std::move(Result);1318 return true;1319 }1320 }1321 return false;1322 }1323 1324 for (const TypedefNameDecl *Alias : Aliases->second)1325 if (matches(Alias))1326 return true;1327 return false;1328 }1329 1330 bool1331 objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,1332 const Matcher<NamedDecl> &Matcher,1333 BoundNodesTreeBuilder *Builder) {1334 auto Aliases = CompatibleAliases.find(InterfaceDecl);1335 if (Aliases == CompatibleAliases.end())1336 return false;1337 for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {1338 BoundNodesTreeBuilder Result(*Builder);1339 if (Matcher.matches(*Alias, this, &Result)) {1340 *Builder = std::move(Result);1341 return true;1342 }1343 }1344 return false;1345 }1346 1347 template <typename T> static SourceLocation getNodeLocation(const T &Node) {1348 return Node.getBeginLoc();1349 }1350 1351 static SourceLocation getNodeLocation(const CXXCtorInitializer &Node) {1352 return Node.getSourceLocation();1353 }1354 1355 static SourceLocation getNodeLocation(const TemplateArgumentLoc &Node) {1356 return Node.getLocation();1357 }1358 1359 static SourceLocation getNodeLocation(const Attr &Node) {1360 return Node.getLocation();1361 }1362 1363 bool isInSystemHeader(SourceLocation Loc) {1364 const SourceManager &SM = getASTContext().getSourceManager();1365 return SM.isInSystemHeader(Loc);1366 }1367 1368 template <typename T> bool shouldSkipNode(T &Node) {1369 if (Options.IgnoreSystemHeaders && isInSystemHeader(getNodeLocation(Node)))1370 return true;1371 return false;1372 }1373 1374 template <typename T> bool shouldSkipNode(T *Node) {1375 return (Node == nullptr) || shouldSkipNode(*Node);1376 }1377 1378 bool shouldSkipNode(QualType &) { return false; }1379 1380 bool shouldSkipNode(NestedNameSpecifier &) { return false; }1381 1382 /// Bucket to record map.1383 ///1384 /// Used to get the appropriate bucket for each matcher.1385 llvm::StringMap<llvm::TimeRecord> TimeByBucket;1386 1387 const MatchFinder::MatchersByType *Matchers;1388 1389 /// Filtered list of matcher indices for each matcher kind.1390 ///1391 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node1392 /// kind (and derived kinds) so it is a waste to try every matcher on every1393 /// node.1394 /// We precalculate a list of matchers that pass the toplevel restrict check.1395 llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;1396 1397 const MatchFinder::MatchFinderOptions &Options;1398 ASTContext *ActiveASTContext;1399 1400 // Maps a canonical type to its TypedefDecls.1401 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;1402 1403 // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.1404 llvm::DenseMap<const ObjCInterfaceDecl *,1405 llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>1406 CompatibleAliases;1407 1408 // Maps (matcher, node) -> the match result for memoization.1409 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;1410 MemoizationMap ResultCache;1411};1412 1413static CXXRecordDecl *1414getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {1415 if (auto *RD = TypeNode->getAsCXXRecordDecl())1416 return RD;1417 1418 // Find the innermost TemplateSpecializationType that isn't an alias template.1419 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();1420 while (TemplateType && TemplateType->isTypeAlias())1421 TemplateType =1422 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();1423 1424 // If this is the name of a (dependent) template specialization, use the1425 // definition of the template, even though it might be specialized later.1426 if (TemplateType)1427 if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(1428 TemplateType->getTemplateName().getAsTemplateDecl()))1429 return ClassTemplate->getTemplatedDecl();1430 1431 return nullptr;1432}1433 1434// Returns true if the given C++ class is directly or indirectly derived1435// from a base type with the given name. A class is not considered to be1436// derived from itself.1437bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,1438 const Matcher<NamedDecl> &Base,1439 BoundNodesTreeBuilder *Builder,1440 bool Directly) {1441 llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;1442 return classIsDerivedFromImpl(Declaration, Base, Builder, Directly, Visited);1443}1444 1445bool MatchASTVisitor::classIsDerivedFromImpl(1446 const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,1447 BoundNodesTreeBuilder *Builder, bool Directly,1448 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) {1449 if (!Declaration->hasDefinition())1450 return false;1451 if (!Visited.insert(Declaration).second)1452 return false;1453 for (const auto &It : Declaration->bases()) {1454 const Type *TypeNode = It.getType().getTypePtr();1455 1456 if (typeHasMatchingAlias(TypeNode, Base, Builder))1457 return true;1458 1459 // FIXME: Going to the primary template here isn't really correct, but1460 // unfortunately we accept a Decl matcher for the base class not a Type1461 // matcher, so it's the best thing we can do with our current interface.1462 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);1463 if (!ClassDecl)1464 continue;1465 if (ClassDecl == Declaration) {1466 // This can happen for recursive template definitions.1467 continue;1468 }1469 BoundNodesTreeBuilder Result(*Builder);1470 if (Base.matches(*ClassDecl, this, &Result)) {1471 *Builder = std::move(Result);1472 return true;1473 }1474 if (!Directly &&1475 classIsDerivedFromImpl(ClassDecl, Base, Builder, Directly, Visited))1476 return true;1477 }1478 return false;1479}1480 1481// Returns true if the given Objective-C class is directly or indirectly1482// derived from a matching base class. A class is not considered to be derived1483// from itself.1484bool MatchASTVisitor::objcClassIsDerivedFrom(1485 const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,1486 BoundNodesTreeBuilder *Builder, bool Directly) {1487 // Check if any of the superclasses of the class match.1488 for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();1489 ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {1490 // Check if there are any matching compatibility aliases.1491 if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))1492 return true;1493 1494 // Check if there are any matching type aliases.1495 const Type *TypeNode = ClassDecl->getTypeForDecl();1496 if (typeHasMatchingAlias(TypeNode, Base, Builder))1497 return true;1498 1499 if (Base.matches(*ClassDecl, this, Builder))1500 return true;1501 1502 // Not `return false` as a temporary workaround for PR43879.1503 if (Directly)1504 break;1505 }1506 1507 return false;1508}1509 1510bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {1511 if (shouldSkipNode(DeclNode))1512 return true;1513 1514 bool ScopedTraversal =1515 TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();1516 bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;1517 1518 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {1519 auto SK = CTSD->getSpecializationKind();1520 if (SK == TSK_ExplicitInstantiationDeclaration ||1521 SK == TSK_ExplicitInstantiationDefinition)1522 ScopedChildren = true;1523 } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {1524 if (FD->isDefaulted())1525 ScopedChildren = true;1526 if (FD->isTemplateInstantiation())1527 ScopedTraversal = true;1528 } else if (isa<BindingDecl>(DeclNode)) {1529 ScopedChildren = true;1530 }1531 1532 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);1533 ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);1534 1535 match(*DeclNode);1536 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);1537}1538 1539bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {1540 if (shouldSkipNode(StmtNode))1541 return true;1542 1543 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||1544 TraversingASTChildrenNotSpelledInSource;1545 1546 ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);1547 match(*StmtNode);1548 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue);1549}1550 1551bool MatchASTVisitor::TraverseType(QualType TypeNode, bool TraverseQualifier) {1552 if (shouldSkipNode(TypeNode))1553 return true;1554 1555 match(TypeNode);1556 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode,1557 TraverseQualifier);1558}1559 1560bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode,1561 bool TraverseQualifier) {1562 if (shouldSkipNode(TypeLocNode))1563 return true;1564 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.1565 // We still want to find those types via matchers, so we match them here. Note1566 // that the TypeLocs are structurally a shadow-hierarchy to the expressed1567 // type, so we visit all involved parts of a compound type when matching on1568 // each TypeLoc.1569 match(TypeLocNode);1570 match(TypeLocNode.getType());1571 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(1572 TypeLocNode, TraverseQualifier);1573}1574 1575bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier NNS) {1576 if (shouldSkipNode(NNS))1577 return true;1578 1579 match(NNS);1580 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);1581}1582 1583bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(1584 NestedNameSpecifierLoc NNS) {1585 if (!NNS)1586 return true;1587 1588 if (shouldSkipNode(NNS))1589 return true;1590 1591 match(NNS);1592 1593 // We only match the nested name specifier here (as opposed to traversing it)1594 // because the traversal is already done in the parallel "Loc"-hierarchy.1595 if (NNS.hasQualifier())1596 match(NNS.getNestedNameSpecifier());1597 return1598 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);1599}1600 1601bool MatchASTVisitor::TraverseConstructorInitializer(1602 CXXCtorInitializer *CtorInit) {1603 if (shouldSkipNode(CtorInit))1604 return true;1605 1606 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||1607 TraversingASTChildrenNotSpelledInSource;1608 1609 if (!CtorInit->isWritten())1610 ScopedTraversal = true;1611 1612 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);1613 1614 match(*CtorInit);1615 1616 return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(1617 CtorInit);1618}1619 1620bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {1621 if (shouldSkipNode(Loc))1622 return true;1623 1624 match(Loc);1625 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(Loc);1626}1627 1628bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {1629 if (shouldSkipNode(AttrNode))1630 return true;1631 1632 match(*AttrNode);1633 return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(AttrNode);1634}1635 1636class MatchASTConsumer : public ASTConsumer {1637public:1638 MatchASTConsumer(MatchFinder *Finder,1639 MatchFinder::ParsingDoneTestCallback *ParsingDone)1640 : Finder(Finder), ParsingDone(ParsingDone) {}1641 1642private:1643 void HandleTranslationUnit(ASTContext &Context) override {1644 if (ParsingDone != nullptr) {1645 ParsingDone->run();1646 }1647 Finder->matchAST(Context);1648 }1649 1650 MatchFinder *Finder;1651 MatchFinder::ParsingDoneTestCallback *ParsingDone;1652};1653 1654} // end namespace1655} // end namespace internal1656 1657MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,1658 ASTContext *Context)1659 : Nodes(Nodes), Context(Context),1660 SourceManager(&Context->getSourceManager()) {}1661 1662MatchFinder::MatchCallback::~MatchCallback() {}1663MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}1664 1665MatchFinder::MatchFinder(MatchFinderOptions Options)1666 : Options(std::move(Options)), ParsingDone(nullptr) {}1667 1668MatchFinder::~MatchFinder() {}1669 1670void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,1671 MatchCallback *Action) {1672 std::optional<TraversalKind> TK;1673 if (Action)1674 TK = Action->getCheckTraversalKind();1675 if (TK)1676 Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);1677 else1678 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);1679 Matchers.AllCallbacks.insert(Action);1680}1681 1682void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,1683 MatchCallback *Action) {1684 Matchers.Type.emplace_back(NodeMatch, Action);1685 Matchers.AllCallbacks.insert(Action);1686}1687 1688void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,1689 MatchCallback *Action) {1690 std::optional<TraversalKind> TK;1691 if (Action)1692 TK = Action->getCheckTraversalKind();1693 if (TK)1694 Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);1695 else1696 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);1697 Matchers.AllCallbacks.insert(Action);1698}1699 1700void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,1701 MatchCallback *Action) {1702 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);1703 Matchers.AllCallbacks.insert(Action);1704}1705 1706void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,1707 MatchCallback *Action) {1708 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);1709 Matchers.AllCallbacks.insert(Action);1710}1711 1712void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,1713 MatchCallback *Action) {1714 Matchers.TypeLoc.emplace_back(NodeMatch, Action);1715 Matchers.AllCallbacks.insert(Action);1716}1717 1718void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,1719 MatchCallback *Action) {1720 Matchers.CtorInit.emplace_back(NodeMatch, Action);1721 Matchers.AllCallbacks.insert(Action);1722}1723 1724void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,1725 MatchCallback *Action) {1726 Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);1727 Matchers.AllCallbacks.insert(Action);1728}1729 1730void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,1731 MatchCallback *Action) {1732 Matchers.Attr.emplace_back(AttrMatch, Action);1733 Matchers.AllCallbacks.insert(Action);1734}1735 1736bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,1737 MatchCallback *Action) {1738 if (NodeMatch.canConvertTo<Decl>()) {1739 addMatcher(NodeMatch.convertTo<Decl>(), Action);1740 return true;1741 } else if (NodeMatch.canConvertTo<QualType>()) {1742 addMatcher(NodeMatch.convertTo<QualType>(), Action);1743 return true;1744 } else if (NodeMatch.canConvertTo<Stmt>()) {1745 addMatcher(NodeMatch.convertTo<Stmt>(), Action);1746 return true;1747 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {1748 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);1749 return true;1750 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {1751 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);1752 return true;1753 } else if (NodeMatch.canConvertTo<TypeLoc>()) {1754 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);1755 return true;1756 } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {1757 addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);1758 return true;1759 } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {1760 addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);1761 return true;1762 } else if (NodeMatch.canConvertTo<Attr>()) {1763 addMatcher(NodeMatch.convertTo<Attr>(), Action);1764 return true;1765 }1766 return false;1767}1768 1769std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {1770 return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);1771}1772 1773void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {1774 internal::MatchASTVisitor Visitor(&Matchers, Options);1775 Visitor.set_active_ast_context(&Context);1776 Visitor.match(Node);1777}1778 1779void MatchFinder::matchAST(ASTContext &Context) {1780 internal::MatchASTVisitor Visitor(&Matchers, Options);1781 internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);1782 Visitor.set_active_ast_context(&Context);1783 Visitor.onStartOfTranslationUnit();1784 Visitor.TraverseAST(Context);1785 Visitor.onEndOfTranslationUnit();1786}1787 1788void MatchFinder::registerTestCallbackAfterParsing(1789 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {1790 ParsingDone = NewParsingDone;1791}1792 1793StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }1794 1795std::optional<TraversalKind>1796MatchFinder::MatchCallback::getCheckTraversalKind() const {1797 return std::nullopt;1798}1799 1800} // end namespace ast_matchers1801} // end namespace clang1802