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