1 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Implements an algorithm to efficiently search for matches on AST nodes. 11 // Uses memoization to support recursive matches like HasDescendant. 12 // 13 // The general idea is to visit all AST nodes with a RecursiveASTVisitor, 14 // calling the Matches(...) method of each matcher we are running on each 15 // AST node. The matcher can recurse via the ASTMatchFinder interface. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #include "clang/ASTMatchers/ASTMatchFinder.h" 20 #include "clang/AST/ASTConsumer.h" 21 #include "clang/AST/ASTContext.h" 22 #include "clang/AST/RecursiveASTVisitor.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 63 bool operator<(const MatchKey &Other) const { 64 return std::tie(MatcherID, Node, BoundNodes) < 65 std::tie(Other.MatcherID, Other.Node, Other.BoundNodes); 66 } 67 }; 68 69 // Used to store the result of a match and possibly bound nodes. 70 struct MemoizedMatchResult { 71 bool ResultOfMatch; 72 BoundNodesTreeBuilder Nodes; 73 }; 74 75 // A RecursiveASTVisitor that traverses all children or all descendants of 76 // a node. 77 class MatchChildASTVisitor 78 : public RecursiveASTVisitor<MatchChildASTVisitor> { 79 public: 80 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase; 81 82 // Creates an AST visitor that matches 'matcher' on all children or 83 // descendants of a traversed node. max_depth is the maximum depth 84 // to traverse: use 1 for matching the children and INT_MAX for 85 // matching the descendants. 86 MatchChildASTVisitor(const DynTypedMatcher *Matcher, 87 ASTMatchFinder *Finder, 88 BoundNodesTreeBuilder *Builder, 89 int MaxDepth, 90 ASTMatchFinder::TraversalKind Traversal, 91 ASTMatchFinder::BindKind Bind) 92 : Matcher(Matcher), 93 Finder(Finder), 94 Builder(Builder), 95 CurrentDepth(0), 96 MaxDepth(MaxDepth), 97 Traversal(Traversal), 98 Bind(Bind), 99 Matches(false) {} 100 101 // Returns true if a match is found in the subtree rooted at the 102 // given AST node. This is done via a set of mutually recursive 103 // functions. Here's how the recursion is done (the *wildcard can 104 // actually be Decl, Stmt, or Type): 105 // 106 // - Traverse(node) calls BaseTraverse(node) when it needs 107 // to visit the descendants of node. 108 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node)) 109 // Traverse*(c) for each child c of 'node'. 110 // - Traverse*(c) in turn calls Traverse(c), completing the 111 // recursion. 112 bool findMatch(const ast_type_traits::DynTypedNode &DynNode) { 113 reset(); 114 if (const Decl *D = DynNode.get<Decl>()) 115 traverse(*D); 116 else if (const Stmt *S = DynNode.get<Stmt>()) 117 traverse(*S); 118 else if (const NestedNameSpecifier *NNS = 119 DynNode.get<NestedNameSpecifier>()) 120 traverse(*NNS); 121 else if (const NestedNameSpecifierLoc *NNSLoc = 122 DynNode.get<NestedNameSpecifierLoc>()) 123 traverse(*NNSLoc); 124 else if (const QualType *Q = DynNode.get<QualType>()) 125 traverse(*Q); 126 else if (const TypeLoc *T = DynNode.get<TypeLoc>()) 127 traverse(*T); 128 // FIXME: Add other base types after adding tests. 129 130 // It's OK to always overwrite the bound nodes, as if there was 131 // no match in this recursive branch, the result set is empty 132 // anyway. 133 *Builder = ResultBindings; 134 135 return Matches; 136 } 137 138 // The following are overriding methods from the base visitor class. 139 // They are public only to allow CRTP to work. They are *not *part 140 // of the public API of this class. 141 bool TraverseDecl(Decl *DeclNode) { 142 ScopedIncrement ScopedDepth(&CurrentDepth); 143 return (DeclNode == nullptr) || traverse(*DeclNode); 144 } 145 bool TraverseStmt(Stmt *StmtNode) { 146 ScopedIncrement ScopedDepth(&CurrentDepth); 147 const Stmt *StmtToTraverse = StmtNode; 148 if (Traversal == 149 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) { 150 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode); 151 if (ExprNode) { 152 StmtToTraverse = ExprNode->IgnoreParenImpCasts(); 153 } 154 } 155 return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse); 156 } 157 // We assume that the QualType and the contained type are on the same 158 // hierarchy level. Thus, we try to match either of them. 159 bool TraverseType(QualType TypeNode) { 160 if (TypeNode.isNull()) 161 return true; 162 ScopedIncrement ScopedDepth(&CurrentDepth); 163 // Match the Type. 164 if (!match(*TypeNode)) 165 return false; 166 // The QualType is matched inside traverse. 167 return traverse(TypeNode); 168 } 169 // We assume that the TypeLoc, contained QualType and contained Type all are 170 // on the same hierarchy level. Thus, we try to match all of them. 171 bool TraverseTypeLoc(TypeLoc TypeLocNode) { 172 if (TypeLocNode.isNull()) 173 return true; 174 ScopedIncrement ScopedDepth(&CurrentDepth); 175 // Match the Type. 176 if (!match(*TypeLocNode.getType())) 177 return false; 178 // Match the QualType. 179 if (!match(TypeLocNode.getType())) 180 return false; 181 // The TypeLoc is matched inside traverse. 182 return traverse(TypeLocNode); 183 } 184 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { 185 ScopedIncrement ScopedDepth(&CurrentDepth); 186 return (NNS == nullptr) || traverse(*NNS); 187 } 188 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) { 189 if (!NNS) 190 return true; 191 ScopedIncrement ScopedDepth(&CurrentDepth); 192 if (!match(*NNS.getNestedNameSpecifier())) 193 return false; 194 return traverse(NNS); 195 } 196 197 bool shouldVisitTemplateInstantiations() const { return true; } 198 bool shouldVisitImplicitCode() const { return true; } 199 // Disables data recursion. We intercept Traverse* methods in the RAV, which 200 // are not triggered during data recursion. 201 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; } 202 203 private: 204 // Used for updating the depth during traversal. 205 struct ScopedIncrement { 206 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); } 207 ~ScopedIncrement() { --(*Depth); } 208 209 private: 210 int *Depth; 211 }; 212 213 // Resets the state of this object. 214 void reset() { 215 Matches = false; 216 CurrentDepth = 0; 217 } 218 219 // Forwards the call to the corresponding Traverse*() method in the 220 // base visitor class. 221 bool baseTraverse(const Decl &DeclNode) { 222 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode)); 223 } 224 bool baseTraverse(const Stmt &StmtNode) { 225 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode)); 226 } 227 bool baseTraverse(QualType TypeNode) { 228 return VisitorBase::TraverseType(TypeNode); 229 } 230 bool baseTraverse(TypeLoc TypeLocNode) { 231 return VisitorBase::TraverseTypeLoc(TypeLocNode); 232 } 233 bool baseTraverse(const NestedNameSpecifier &NNS) { 234 return VisitorBase::TraverseNestedNameSpecifier( 235 const_cast<NestedNameSpecifier*>(&NNS)); 236 } 237 bool baseTraverse(NestedNameSpecifierLoc NNS) { 238 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS); 239 } 240 241 // Sets 'Matched' to true if 'Matcher' matches 'Node' and: 242 // 0 < CurrentDepth <= MaxDepth. 243 // 244 // Returns 'true' if traversal should continue after this function 245 // returns, i.e. if no match is found or 'Bind' is 'BK_All'. 246 template <typename T> 247 bool match(const T &Node) { 248 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) { 249 return true; 250 } 251 if (Bind != ASTMatchFinder::BK_All) { 252 BoundNodesTreeBuilder RecursiveBuilder(*Builder); 253 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder, 254 &RecursiveBuilder)) { 255 Matches = true; 256 ResultBindings.addMatch(RecursiveBuilder); 257 return false; // Abort as soon as a match is found. 258 } 259 } else { 260 BoundNodesTreeBuilder RecursiveBuilder(*Builder); 261 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder, 262 &RecursiveBuilder)) { 263 // After the first match the matcher succeeds. 264 Matches = true; 265 ResultBindings.addMatch(RecursiveBuilder); 266 } 267 } 268 return true; 269 } 270 271 // Traverses the subtree rooted at 'Node'; returns true if the 272 // traversal should continue after this function returns. 273 template <typename T> 274 bool traverse(const T &Node) { 275 static_assert(IsBaseType<T>::value, 276 "traverse can only be instantiated with base type"); 277 if (!match(Node)) 278 return false; 279 return baseTraverse(Node); 280 } 281 282 const DynTypedMatcher *const Matcher; 283 ASTMatchFinder *const Finder; 284 BoundNodesTreeBuilder *const Builder; 285 BoundNodesTreeBuilder ResultBindings; 286 int CurrentDepth; 287 const int MaxDepth; 288 const ASTMatchFinder::TraversalKind Traversal; 289 const ASTMatchFinder::BindKind Bind; 290 bool Matches; 291 }; 292 293 // Controls the outermost traversal of the AST and allows to match multiple 294 // matchers. 295 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>, 296 public ASTMatchFinder { 297 public: 298 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers, 299 const MatchFinder::MatchFinderOptions &Options) 300 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {} 301 302 ~MatchASTVisitor() { 303 if (Options.CheckProfiling) { 304 Options.CheckProfiling->Records = std::move(TimeByBucket); 305 } 306 } 307 308 void onStartOfTranslationUnit() { 309 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 310 TimeBucketRegion Timer; 311 for (MatchCallback *MC : Matchers->AllCallbacks) { 312 if (EnableCheckProfiling) 313 Timer.setBucket(&TimeByBucket[MC->getID()]); 314 MC->onStartOfTranslationUnit(); 315 } 316 } 317 318 void onEndOfTranslationUnit() { 319 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 320 TimeBucketRegion Timer; 321 for (MatchCallback *MC : Matchers->AllCallbacks) { 322 if (EnableCheckProfiling) 323 Timer.setBucket(&TimeByBucket[MC->getID()]); 324 MC->onEndOfTranslationUnit(); 325 } 326 } 327 328 void set_active_ast_context(ASTContext *NewActiveASTContext) { 329 ActiveASTContext = NewActiveASTContext; 330 } 331 332 // The following Visit*() and Traverse*() functions "override" 333 // methods in RecursiveASTVisitor. 334 335 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) { 336 // When we see 'typedef A B', we add name 'B' to the set of names 337 // A's canonical type maps to. This is necessary for implementing 338 // isDerivedFrom(x) properly, where x can be the name of the base 339 // class or any of its aliases. 340 // 341 // In general, the is-alias-of (as defined by typedefs) relation 342 // is tree-shaped, as you can typedef a type more than once. For 343 // example, 344 // 345 // typedef A B; 346 // typedef A C; 347 // typedef C D; 348 // typedef C E; 349 // 350 // gives you 351 // 352 // A 353 // |- B 354 // `- C 355 // |- D 356 // `- E 357 // 358 // It is wrong to assume that the relation is a chain. A correct 359 // implementation of isDerivedFrom() needs to recognize that B and 360 // E are aliases, even though neither is a typedef of the other. 361 // Therefore, we cannot simply walk through one typedef chain to 362 // find out whether the type name matches. 363 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr(); 364 const Type *CanonicalType = // root of the typedef tree 365 ActiveASTContext->getCanonicalType(TypeNode); 366 TypeAliases[CanonicalType].insert(DeclNode); 367 return true; 368 } 369 370 bool TraverseDecl(Decl *DeclNode); 371 bool TraverseStmt(Stmt *StmtNode); 372 bool TraverseType(QualType TypeNode); 373 bool TraverseTypeLoc(TypeLoc TypeNode); 374 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS); 375 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS); 376 377 // Matches children or descendants of 'Node' with 'BaseMatcher'. 378 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node, 379 const DynTypedMatcher &Matcher, 380 BoundNodesTreeBuilder *Builder, int MaxDepth, 381 TraversalKind Traversal, BindKind Bind) { 382 // For AST-nodes that don't have an identity, we can't memoize. 383 if (!Node.getMemoizationData() || !Builder->isComparable()) 384 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal, 385 Bind); 386 387 MatchKey Key; 388 Key.MatcherID = Matcher.getID(); 389 Key.Node = Node; 390 // Note that we key on the bindings *before* the match. 391 Key.BoundNodes = *Builder; 392 393 MemoizationMap::iterator I = ResultCache.find(Key); 394 if (I != ResultCache.end()) { 395 *Builder = I->second.Nodes; 396 return I->second.ResultOfMatch; 397 } 398 399 MemoizedMatchResult Result; 400 Result.Nodes = *Builder; 401 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes, 402 MaxDepth, Traversal, Bind); 403 404 MemoizedMatchResult &CachedResult = ResultCache[Key]; 405 CachedResult = std::move(Result); 406 407 *Builder = CachedResult.Nodes; 408 return CachedResult.ResultOfMatch; 409 } 410 411 // Matches children or descendants of 'Node' with 'BaseMatcher'. 412 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node, 413 const DynTypedMatcher &Matcher, 414 BoundNodesTreeBuilder *Builder, int MaxDepth, 415 TraversalKind Traversal, BindKind Bind) { 416 MatchChildASTVisitor Visitor( 417 &Matcher, this, Builder, MaxDepth, Traversal, Bind); 418 return Visitor.findMatch(Node); 419 } 420 421 bool classIsDerivedFrom(const CXXRecordDecl *Declaration, 422 const Matcher<NamedDecl> &Base, 423 BoundNodesTreeBuilder *Builder) override; 424 425 // Implements ASTMatchFinder::matchesChildOf. 426 bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, 427 const DynTypedMatcher &Matcher, 428 BoundNodesTreeBuilder *Builder, 429 TraversalKind Traversal, 430 BindKind Bind) override { 431 if (ResultCache.size() > MaxMemoizationEntries) 432 ResultCache.clear(); 433 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal, 434 Bind); 435 } 436 // Implements ASTMatchFinder::matchesDescendantOf. 437 bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node, 438 const DynTypedMatcher &Matcher, 439 BoundNodesTreeBuilder *Builder, 440 BindKind Bind) override { 441 if (ResultCache.size() > MaxMemoizationEntries) 442 ResultCache.clear(); 443 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX, 444 TK_AsIs, Bind); 445 } 446 // Implements ASTMatchFinder::matchesAncestorOf. 447 bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, 448 const DynTypedMatcher &Matcher, 449 BoundNodesTreeBuilder *Builder, 450 AncestorMatchMode MatchMode) override { 451 // Reset the cache outside of the recursive call to make sure we 452 // don't invalidate any iterators. 453 if (ResultCache.size() > MaxMemoizationEntries) 454 ResultCache.clear(); 455 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder, 456 MatchMode); 457 } 458 459 // Matches all registered matchers on the given node and calls the 460 // result callback for every node that matches. 461 void match(const ast_type_traits::DynTypedNode &Node) { 462 // FIXME: Improve this with a switch or a visitor pattern. 463 if (auto *N = Node.get<Decl>()) { 464 match(*N); 465 } else if (auto *N = Node.get<Stmt>()) { 466 match(*N); 467 } else if (auto *N = Node.get<Type>()) { 468 match(*N); 469 } else if (auto *N = Node.get<QualType>()) { 470 match(*N); 471 } else if (auto *N = Node.get<NestedNameSpecifier>()) { 472 match(*N); 473 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) { 474 match(*N); 475 } else if (auto *N = Node.get<TypeLoc>()) { 476 match(*N); 477 } 478 } 479 480 template <typename T> void match(const T &Node) { 481 matchDispatch(&Node); 482 } 483 484 // Implements ASTMatchFinder::getASTContext. 485 ASTContext &getASTContext() const override { return *ActiveASTContext; } 486 487 bool shouldVisitTemplateInstantiations() const { return true; } 488 bool shouldVisitImplicitCode() const { return true; } 489 // Disables data recursion. We intercept Traverse* methods in the RAV, which 490 // are not triggered during data recursion. 491 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; } 492 493 private: 494 class TimeBucketRegion { 495 public: 496 TimeBucketRegion() : Bucket(nullptr) {} 497 ~TimeBucketRegion() { setBucket(nullptr); } 498 499 /// \brief Start timing for \p NewBucket. 500 /// 501 /// If there was a bucket already set, it will finish the timing for that 502 /// other bucket. 503 /// \p NewBucket will be timed until the next call to \c setBucket() or 504 /// until the \c TimeBucketRegion is destroyed. 505 /// If \p NewBucket is the same as the currently timed bucket, this call 506 /// does nothing. 507 void setBucket(llvm::TimeRecord *NewBucket) { 508 if (Bucket != NewBucket) { 509 auto Now = llvm::TimeRecord::getCurrentTime(true); 510 if (Bucket) 511 *Bucket += Now; 512 if (NewBucket) 513 *NewBucket -= Now; 514 Bucket = NewBucket; 515 } 516 } 517 518 private: 519 llvm::TimeRecord *Bucket; 520 }; 521 522 /// \brief Runs all the \p Matchers on \p Node. 523 /// 524 /// Used by \c matchDispatch() below. 525 template <typename T, typename MC> 526 void matchImpl(const T &Node, const MC &Matchers) { 527 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 528 TimeBucketRegion Timer; 529 for (const auto &MP : Matchers) { 530 if (EnableCheckProfiling) 531 Timer.setBucket(&TimeByBucket[MP.second->getID()]); 532 BoundNodesTreeBuilder Builder; 533 if (MP.first.matches(Node, this, &Builder)) { 534 MatchVisitor Visitor(ActiveASTContext, MP.second); 535 Builder.visitMatches(&Visitor); 536 } 537 } 538 } 539 540 /// @{ 541 /// \brief Overloads to pair the different node types to their matchers. 542 void matchDispatch(const Decl *Node) { matchImpl(*Node, Matchers->Decl); } 543 void matchDispatch(const Stmt *Node) { matchImpl(*Node, Matchers->Stmt); } 544 void matchDispatch(const Type *Node) { 545 matchImpl(QualType(Node, 0), Matchers->Type); 546 } 547 void matchDispatch(const TypeLoc *Node) { 548 matchImpl(*Node, Matchers->TypeLoc); 549 } 550 void matchDispatch(const QualType *Node) { matchImpl(*Node, Matchers->Type); } 551 void matchDispatch(const NestedNameSpecifier *Node) { 552 matchImpl(*Node, Matchers->NestedNameSpecifier); 553 } 554 void matchDispatch(const NestedNameSpecifierLoc *Node) { 555 matchImpl(*Node, Matchers->NestedNameSpecifierLoc); 556 } 557 void matchDispatch(const void *) { /* Do nothing. */ } 558 /// @} 559 560 // Returns whether an ancestor of \p Node matches \p Matcher. 561 // 562 // The order of matching ((which can lead to different nodes being bound in 563 // case there are multiple matches) is breadth first search. 564 // 565 // To allow memoization in the very common case of having deeply nested 566 // expressions inside a template function, we first walk up the AST, memoizing 567 // the result of the match along the way, as long as there is only a single 568 // parent. 569 // 570 // Once there are multiple parents, the breadth first search order does not 571 // allow simple memoization on the ancestors. Thus, we only memoize as long 572 // as there is a single parent. 573 bool memoizedMatchesAncestorOfRecursively( 574 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, 575 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { 576 if (Node.get<TranslationUnitDecl>() == 577 ActiveASTContext->getTranslationUnitDecl()) 578 return false; 579 assert(Node.getMemoizationData() && 580 "Invariant broken: only nodes that support memoization may be " 581 "used in the parent map."); 582 583 MatchKey Key; 584 Key.MatcherID = Matcher.getID(); 585 Key.Node = Node; 586 Key.BoundNodes = *Builder; 587 588 // Note that we cannot use insert and reuse the iterator, as recursive 589 // calls to match might invalidate the result cache iterators. 590 MemoizationMap::iterator I = ResultCache.find(Key); 591 if (I != ResultCache.end()) { 592 *Builder = I->second.Nodes; 593 return I->second.ResultOfMatch; 594 } 595 596 MemoizedMatchResult Result; 597 Result.ResultOfMatch = false; 598 Result.Nodes = *Builder; 599 600 const auto &Parents = ActiveASTContext->getParents(Node); 601 assert(!Parents.empty() && "Found node that is not in the parent map."); 602 if (Parents.size() == 1) { 603 // Only one parent - do recursive memoization. 604 const ast_type_traits::DynTypedNode Parent = Parents[0]; 605 if (Matcher.matches(Parent, this, &Result.Nodes)) { 606 Result.ResultOfMatch = true; 607 } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 608 // Reset the results to not include the bound nodes from the failed 609 // match above. 610 Result.Nodes = *Builder; 611 Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively( 612 Parent, Matcher, &Result.Nodes, MatchMode); 613 // Once we get back from the recursive call, the result will be the 614 // same as the parent's result. 615 } 616 } else { 617 // Multiple parents - BFS over the rest of the nodes. 618 llvm::DenseSet<const void *> Visited; 619 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(), 620 Parents.end()); 621 while (!Queue.empty()) { 622 Result.Nodes = *Builder; 623 if (Matcher.matches(Queue.front(), this, &Result.Nodes)) { 624 Result.ResultOfMatch = true; 625 break; 626 } 627 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 628 for (const auto &Parent : 629 ActiveASTContext->getParents(Queue.front())) { 630 // Make sure we do not visit the same node twice. 631 // Otherwise, we'll visit the common ancestors as often as there 632 // are splits on the way down. 633 if (Visited.insert(Parent.getMemoizationData()).second) 634 Queue.push_back(Parent); 635 } 636 } 637 Queue.pop_front(); 638 } 639 } 640 641 MemoizedMatchResult &CachedResult = ResultCache[Key]; 642 CachedResult = std::move(Result); 643 644 *Builder = CachedResult.Nodes; 645 return CachedResult.ResultOfMatch; 646 } 647 648 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with 649 // the aggregated bound nodes for each match. 650 class MatchVisitor : public BoundNodesTreeBuilder::Visitor { 651 public: 652 MatchVisitor(ASTContext* Context, 653 MatchFinder::MatchCallback* Callback) 654 : Context(Context), 655 Callback(Callback) {} 656 657 void visitMatch(const BoundNodes& BoundNodesView) override { 658 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context)); 659 } 660 661 private: 662 ASTContext* Context; 663 MatchFinder::MatchCallback* Callback; 664 }; 665 666 // Returns true if 'TypeNode' has an alias that matches the given matcher. 667 bool typeHasMatchingAlias(const Type *TypeNode, 668 const Matcher<NamedDecl> Matcher, 669 BoundNodesTreeBuilder *Builder) { 670 const Type *const CanonicalType = 671 ActiveASTContext->getCanonicalType(TypeNode); 672 for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) { 673 BoundNodesTreeBuilder Result(*Builder); 674 if (Matcher.matches(*Alias, this, &Result)) { 675 *Builder = std::move(Result); 676 return true; 677 } 678 } 679 return false; 680 } 681 682 /// \brief Bucket to record map. 683 /// 684 /// Used to get the appropriate bucket for each matcher. 685 llvm::StringMap<llvm::TimeRecord> TimeByBucket; 686 687 const MatchFinder::MatchersByType *Matchers; 688 const MatchFinder::MatchFinderOptions &Options; 689 ASTContext *ActiveASTContext; 690 691 // Maps a canonical type to its TypedefDecls. 692 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases; 693 694 // Maps (matcher, node) -> the match result for memoization. 695 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap; 696 MemoizationMap ResultCache; 697 }; 698 699 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) { 700 // Type::getAs<...>() drills through typedefs. 701 if (TypeNode->getAs<DependentNameType>() != nullptr || 702 TypeNode->getAs<DependentTemplateSpecializationType>() != nullptr || 703 TypeNode->getAs<TemplateTypeParmType>() != nullptr) 704 // Dependent names and template TypeNode parameters will be matched when 705 // the template is instantiated. 706 return nullptr; 707 TemplateSpecializationType const *TemplateType = 708 TypeNode->getAs<TemplateSpecializationType>(); 709 if (!TemplateType) { 710 return TypeNode->getAsCXXRecordDecl(); 711 } 712 if (TemplateType->getTemplateName().isDependent()) 713 // Dependent template specializations will be matched when the 714 // template is instantiated. 715 return nullptr; 716 717 // For template specialization types which are specializing a template 718 // declaration which is an explicit or partial specialization of another 719 // template declaration, getAsCXXRecordDecl() returns the corresponding 720 // ClassTemplateSpecializationDecl. 721 // 722 // For template specialization types which are specializing a template 723 // declaration which is neither an explicit nor partial specialization of 724 // another template declaration, getAsCXXRecordDecl() returns NULL and 725 // we get the CXXRecordDecl of the templated declaration. 726 CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl(); 727 if (SpecializationDecl) { 728 return SpecializationDecl; 729 } 730 NamedDecl *Templated = 731 TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(); 732 if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) { 733 return TemplatedRecord; 734 } 735 // Now it can still be that we have an alias template. 736 TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated); 737 assert(AliasDecl); 738 return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr()); 739 } 740 741 // Returns true if the given class is directly or indirectly derived 742 // from a base type with the given name. A class is not considered to be 743 // derived from itself. 744 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration, 745 const Matcher<NamedDecl> &Base, 746 BoundNodesTreeBuilder *Builder) { 747 if (!Declaration->hasDefinition()) 748 return false; 749 for (const auto &It : Declaration->bases()) { 750 const Type *TypeNode = It.getType().getTypePtr(); 751 752 if (typeHasMatchingAlias(TypeNode, Base, Builder)) 753 return true; 754 755 CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode); 756 if (!ClassDecl) 757 continue; 758 if (ClassDecl == Declaration) { 759 // This can happen for recursive template definitions; if the 760 // current declaration did not match, we can safely return false. 761 return false; 762 } 763 BoundNodesTreeBuilder Result(*Builder); 764 if (Base.matches(*ClassDecl, this, &Result)) { 765 *Builder = std::move(Result); 766 return true; 767 } 768 if (classIsDerivedFrom(ClassDecl, Base, Builder)) 769 return true; 770 } 771 return false; 772 } 773 774 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) { 775 if (!DeclNode) { 776 return true; 777 } 778 match(*DeclNode); 779 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode); 780 } 781 782 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) { 783 if (!StmtNode) { 784 return true; 785 } 786 match(*StmtNode); 787 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode); 788 } 789 790 bool MatchASTVisitor::TraverseType(QualType TypeNode) { 791 match(TypeNode); 792 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode); 793 } 794 795 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) { 796 // The RecursiveASTVisitor only visits types if they're not within TypeLocs. 797 // We still want to find those types via matchers, so we match them here. Note 798 // that the TypeLocs are structurally a shadow-hierarchy to the expressed 799 // type, so we visit all involved parts of a compound type when matching on 800 // each TypeLoc. 801 match(TypeLocNode); 802 match(TypeLocNode.getType()); 803 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode); 804 } 805 806 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { 807 match(*NNS); 808 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS); 809 } 810 811 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc( 812 NestedNameSpecifierLoc NNS) { 813 match(NNS); 814 // We only match the nested name specifier here (as opposed to traversing it) 815 // because the traversal is already done in the parallel "Loc"-hierarchy. 816 if (NNS.hasQualifier()) 817 match(*NNS.getNestedNameSpecifier()); 818 return 819 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS); 820 } 821 822 class MatchASTConsumer : public ASTConsumer { 823 public: 824 MatchASTConsumer(MatchFinder *Finder, 825 MatchFinder::ParsingDoneTestCallback *ParsingDone) 826 : Finder(Finder), ParsingDone(ParsingDone) {} 827 828 private: 829 void HandleTranslationUnit(ASTContext &Context) override { 830 if (ParsingDone != nullptr) { 831 ParsingDone->run(); 832 } 833 Finder->matchAST(Context); 834 } 835 836 MatchFinder *Finder; 837 MatchFinder::ParsingDoneTestCallback *ParsingDone; 838 }; 839 840 } // end namespace 841 } // end namespace internal 842 843 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes, 844 ASTContext *Context) 845 : Nodes(Nodes), Context(Context), 846 SourceManager(&Context->getSourceManager()) {} 847 848 MatchFinder::MatchCallback::~MatchCallback() {} 849 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {} 850 851 MatchFinder::MatchFinder(MatchFinderOptions Options) 852 : Options(std::move(Options)), ParsingDone(nullptr) {} 853 854 MatchFinder::~MatchFinder() {} 855 856 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch, 857 MatchCallback *Action) { 858 Matchers.Decl.push_back(std::make_pair(NodeMatch, Action)); 859 Matchers.AllCallbacks.push_back(Action); 860 } 861 862 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch, 863 MatchCallback *Action) { 864 Matchers.Type.push_back(std::make_pair(NodeMatch, Action)); 865 Matchers.AllCallbacks.push_back(Action); 866 } 867 868 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch, 869 MatchCallback *Action) { 870 Matchers.Stmt.push_back(std::make_pair(NodeMatch, Action)); 871 Matchers.AllCallbacks.push_back(Action); 872 } 873 874 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch, 875 MatchCallback *Action) { 876 Matchers.NestedNameSpecifier.push_back(std::make_pair(NodeMatch, Action)); 877 Matchers.AllCallbacks.push_back(Action); 878 } 879 880 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch, 881 MatchCallback *Action) { 882 Matchers.NestedNameSpecifierLoc.push_back(std::make_pair(NodeMatch, Action)); 883 Matchers.AllCallbacks.push_back(Action); 884 } 885 886 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch, 887 MatchCallback *Action) { 888 Matchers.TypeLoc.push_back(std::make_pair(NodeMatch, Action)); 889 Matchers.AllCallbacks.push_back(Action); 890 } 891 892 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, 893 MatchCallback *Action) { 894 if (NodeMatch.canConvertTo<Decl>()) { 895 addMatcher(NodeMatch.convertTo<Decl>(), Action); 896 return true; 897 } else if (NodeMatch.canConvertTo<QualType>()) { 898 addMatcher(NodeMatch.convertTo<QualType>(), Action); 899 return true; 900 } else if (NodeMatch.canConvertTo<Stmt>()) { 901 addMatcher(NodeMatch.convertTo<Stmt>(), Action); 902 return true; 903 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) { 904 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action); 905 return true; 906 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) { 907 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action); 908 return true; 909 } else if (NodeMatch.canConvertTo<TypeLoc>()) { 910 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action); 911 return true; 912 } 913 return false; 914 } 915 916 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() { 917 return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone); 918 } 919 920 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node, 921 ASTContext &Context) { 922 internal::MatchASTVisitor Visitor(&Matchers, Options); 923 Visitor.set_active_ast_context(&Context); 924 Visitor.match(Node); 925 } 926 927 void MatchFinder::matchAST(ASTContext &Context) { 928 internal::MatchASTVisitor Visitor(&Matchers, Options); 929 Visitor.set_active_ast_context(&Context); 930 Visitor.onStartOfTranslationUnit(); 931 Visitor.TraverseDecl(Context.getTranslationUnitDecl()); 932 Visitor.onEndOfTranslationUnit(); 933 } 934 935 void MatchFinder::registerTestCallbackAfterParsing( 936 MatchFinder::ParsingDoneTestCallback *NewParsingDone) { 937 ParsingDone = NewParsingDone; 938 } 939 940 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; } 941 942 } // end namespace ast_matchers 943 } // end namespace clang 944