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