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 201 private: 202 // Used for updating the depth during traversal. 203 struct ScopedIncrement { 204 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); } 205 ~ScopedIncrement() { --(*Depth); } 206 207 private: 208 int *Depth; 209 }; 210 211 // Resets the state of this object. 212 void reset() { 213 Matches = false; 214 CurrentDepth = 0; 215 } 216 217 // Forwards the call to the corresponding Traverse*() method in the 218 // base visitor class. 219 bool baseTraverse(const Decl &DeclNode) { 220 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode)); 221 } 222 bool baseTraverse(const Stmt &StmtNode) { 223 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode)); 224 } 225 bool baseTraverse(QualType TypeNode) { 226 return VisitorBase::TraverseType(TypeNode); 227 } 228 bool baseTraverse(TypeLoc TypeLocNode) { 229 return VisitorBase::TraverseTypeLoc(TypeLocNode); 230 } 231 bool baseTraverse(const NestedNameSpecifier &NNS) { 232 return VisitorBase::TraverseNestedNameSpecifier( 233 const_cast<NestedNameSpecifier*>(&NNS)); 234 } 235 bool baseTraverse(NestedNameSpecifierLoc NNS) { 236 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS); 237 } 238 239 // Sets 'Matched' to true if 'Matcher' matches 'Node' and: 240 // 0 < CurrentDepth <= MaxDepth. 241 // 242 // Returns 'true' if traversal should continue after this function 243 // returns, i.e. if no match is found or 'Bind' is 'BK_All'. 244 template <typename T> 245 bool match(const T &Node) { 246 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) { 247 return true; 248 } 249 if (Bind != ASTMatchFinder::BK_All) { 250 BoundNodesTreeBuilder RecursiveBuilder(*Builder); 251 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder, 252 &RecursiveBuilder)) { 253 Matches = true; 254 ResultBindings.addMatch(RecursiveBuilder); 255 return false; // Abort as soon as a match is found. 256 } 257 } else { 258 BoundNodesTreeBuilder RecursiveBuilder(*Builder); 259 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder, 260 &RecursiveBuilder)) { 261 // After the first match the matcher succeeds. 262 Matches = true; 263 ResultBindings.addMatch(RecursiveBuilder); 264 } 265 } 266 return true; 267 } 268 269 // Traverses the subtree rooted at 'Node'; returns true if the 270 // traversal should continue after this function returns. 271 template <typename T> 272 bool traverse(const T &Node) { 273 static_assert(IsBaseType<T>::value, 274 "traverse can only be instantiated with base type"); 275 if (!match(Node)) 276 return false; 277 return baseTraverse(Node); 278 } 279 280 const DynTypedMatcher *const Matcher; 281 ASTMatchFinder *const Finder; 282 BoundNodesTreeBuilder *const Builder; 283 BoundNodesTreeBuilder ResultBindings; 284 int CurrentDepth; 285 const int MaxDepth; 286 const ASTMatchFinder::TraversalKind Traversal; 287 const ASTMatchFinder::BindKind Bind; 288 bool Matches; 289 }; 290 291 // Controls the outermost traversal of the AST and allows to match multiple 292 // matchers. 293 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>, 294 public ASTMatchFinder { 295 public: 296 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers, 297 const MatchFinder::MatchFinderOptions &Options) 298 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {} 299 300 ~MatchASTVisitor() override { 301 if (Options.CheckProfiling) { 302 Options.CheckProfiling->Records = std::move(TimeByBucket); 303 } 304 } 305 306 void onStartOfTranslationUnit() { 307 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 308 TimeBucketRegion Timer; 309 for (MatchCallback *MC : Matchers->AllCallbacks) { 310 if (EnableCheckProfiling) 311 Timer.setBucket(&TimeByBucket[MC->getID()]); 312 MC->onStartOfTranslationUnit(); 313 } 314 } 315 316 void onEndOfTranslationUnit() { 317 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 318 TimeBucketRegion Timer; 319 for (MatchCallback *MC : Matchers->AllCallbacks) { 320 if (EnableCheckProfiling) 321 Timer.setBucket(&TimeByBucket[MC->getID()]); 322 MC->onEndOfTranslationUnit(); 323 } 324 } 325 326 void set_active_ast_context(ASTContext *NewActiveASTContext) { 327 ActiveASTContext = NewActiveASTContext; 328 } 329 330 // The following Visit*() and Traverse*() functions "override" 331 // methods in RecursiveASTVisitor. 332 333 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) { 334 // When we see 'typedef A B', we add name 'B' to the set of names 335 // A's canonical type maps to. This is necessary for implementing 336 // isDerivedFrom(x) properly, where x can be the name of the base 337 // class or any of its aliases. 338 // 339 // In general, the is-alias-of (as defined by typedefs) relation 340 // is tree-shaped, as you can typedef a type more than once. For 341 // example, 342 // 343 // typedef A B; 344 // typedef A C; 345 // typedef C D; 346 // typedef C E; 347 // 348 // gives you 349 // 350 // A 351 // |- B 352 // `- C 353 // |- D 354 // `- E 355 // 356 // It is wrong to assume that the relation is a chain. A correct 357 // implementation of isDerivedFrom() needs to recognize that B and 358 // E are aliases, even though neither is a typedef of the other. 359 // Therefore, we cannot simply walk through one typedef chain to 360 // find out whether the type name matches. 361 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr(); 362 const Type *CanonicalType = // root of the typedef tree 363 ActiveASTContext->getCanonicalType(TypeNode); 364 TypeAliases[CanonicalType].insert(DeclNode); 365 return true; 366 } 367 368 bool TraverseDecl(Decl *DeclNode); 369 bool TraverseStmt(Stmt *StmtNode); 370 bool TraverseType(QualType TypeNode); 371 bool TraverseTypeLoc(TypeLoc TypeNode); 372 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS); 373 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS); 374 375 // Matches children or descendants of 'Node' with 'BaseMatcher'. 376 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node, 377 const DynTypedMatcher &Matcher, 378 BoundNodesTreeBuilder *Builder, int MaxDepth, 379 TraversalKind Traversal, BindKind Bind) { 380 // For AST-nodes that don't have an identity, we can't memoize. 381 if (!Node.getMemoizationData() || !Builder->isComparable()) 382 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal, 383 Bind); 384 385 MatchKey Key; 386 Key.MatcherID = Matcher.getID(); 387 Key.Node = Node; 388 // Note that we key on the bindings *before* the match. 389 Key.BoundNodes = *Builder; 390 391 MemoizationMap::iterator I = ResultCache.find(Key); 392 if (I != ResultCache.end()) { 393 *Builder = I->second.Nodes; 394 return I->second.ResultOfMatch; 395 } 396 397 MemoizedMatchResult Result; 398 Result.Nodes = *Builder; 399 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes, 400 MaxDepth, Traversal, Bind); 401 402 MemoizedMatchResult &CachedResult = ResultCache[Key]; 403 CachedResult = std::move(Result); 404 405 *Builder = CachedResult.Nodes; 406 return CachedResult.ResultOfMatch; 407 } 408 409 // Matches children or descendants of 'Node' with 'BaseMatcher'. 410 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node, 411 const DynTypedMatcher &Matcher, 412 BoundNodesTreeBuilder *Builder, int MaxDepth, 413 TraversalKind Traversal, BindKind Bind) { 414 MatchChildASTVisitor Visitor( 415 &Matcher, this, Builder, MaxDepth, Traversal, Bind); 416 return Visitor.findMatch(Node); 417 } 418 419 bool classIsDerivedFrom(const CXXRecordDecl *Declaration, 420 const Matcher<NamedDecl> &Base, 421 BoundNodesTreeBuilder *Builder) override; 422 423 // Implements ASTMatchFinder::matchesChildOf. 424 bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, 425 const DynTypedMatcher &Matcher, 426 BoundNodesTreeBuilder *Builder, 427 TraversalKind Traversal, 428 BindKind Bind) override { 429 if (ResultCache.size() > MaxMemoizationEntries) 430 ResultCache.clear(); 431 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal, 432 Bind); 433 } 434 // Implements ASTMatchFinder::matchesDescendantOf. 435 bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node, 436 const DynTypedMatcher &Matcher, 437 BoundNodesTreeBuilder *Builder, 438 BindKind Bind) override { 439 if (ResultCache.size() > MaxMemoizationEntries) 440 ResultCache.clear(); 441 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX, 442 TK_AsIs, Bind); 443 } 444 // Implements ASTMatchFinder::matchesAncestorOf. 445 bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, 446 const DynTypedMatcher &Matcher, 447 BoundNodesTreeBuilder *Builder, 448 AncestorMatchMode MatchMode) override { 449 // Reset the cache outside of the recursive call to make sure we 450 // don't invalidate any iterators. 451 if (ResultCache.size() > MaxMemoizationEntries) 452 ResultCache.clear(); 453 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder, 454 MatchMode); 455 } 456 457 // Matches all registered matchers on the given node and calls the 458 // result callback for every node that matches. 459 void match(const ast_type_traits::DynTypedNode &Node) { 460 // FIXME: Improve this with a switch or a visitor pattern. 461 if (auto *N = Node.get<Decl>()) { 462 match(*N); 463 } else if (auto *N = Node.get<Stmt>()) { 464 match(*N); 465 } else if (auto *N = Node.get<Type>()) { 466 match(*N); 467 } else if (auto *N = Node.get<QualType>()) { 468 match(*N); 469 } else if (auto *N = Node.get<NestedNameSpecifier>()) { 470 match(*N); 471 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) { 472 match(*N); 473 } else if (auto *N = Node.get<TypeLoc>()) { 474 match(*N); 475 } 476 } 477 478 template <typename T> void match(const T &Node) { 479 matchDispatch(&Node); 480 } 481 482 // Implements ASTMatchFinder::getASTContext. 483 ASTContext &getASTContext() const override { return *ActiveASTContext; } 484 485 bool shouldVisitTemplateInstantiations() const { return true; } 486 bool shouldVisitImplicitCode() const { return true; } 487 488 private: 489 class TimeBucketRegion { 490 public: 491 TimeBucketRegion() : Bucket(nullptr) {} 492 ~TimeBucketRegion() { setBucket(nullptr); } 493 494 /// \brief Start timing for \p NewBucket. 495 /// 496 /// If there was a bucket already set, it will finish the timing for that 497 /// other bucket. 498 /// \p NewBucket will be timed until the next call to \c setBucket() or 499 /// until the \c TimeBucketRegion is destroyed. 500 /// If \p NewBucket is the same as the currently timed bucket, this call 501 /// does nothing. 502 void setBucket(llvm::TimeRecord *NewBucket) { 503 if (Bucket != NewBucket) { 504 auto Now = llvm::TimeRecord::getCurrentTime(true); 505 if (Bucket) 506 *Bucket += Now; 507 if (NewBucket) 508 *NewBucket -= Now; 509 Bucket = NewBucket; 510 } 511 } 512 513 private: 514 llvm::TimeRecord *Bucket; 515 }; 516 517 /// \brief Runs all the \p Matchers on \p Node. 518 /// 519 /// Used by \c matchDispatch() below. 520 template <typename T, typename MC> 521 void matchWithoutFilter(const T &Node, const MC &Matchers) { 522 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 523 TimeBucketRegion Timer; 524 for (const auto &MP : Matchers) { 525 if (EnableCheckProfiling) 526 Timer.setBucket(&TimeByBucket[MP.second->getID()]); 527 BoundNodesTreeBuilder Builder; 528 if (MP.first.matches(Node, this, &Builder)) { 529 MatchVisitor Visitor(ActiveASTContext, MP.second); 530 Builder.visitMatches(&Visitor); 531 } 532 } 533 } 534 535 void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) { 536 auto Kind = DynNode.getNodeKind(); 537 auto it = MatcherFiltersMap.find(Kind); 538 const auto &Filter = 539 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind); 540 541 if (Filter.empty()) 542 return; 543 544 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue(); 545 TimeBucketRegion Timer; 546 auto &Matchers = this->Matchers->DeclOrStmt; 547 for (unsigned short I : Filter) { 548 auto &MP = Matchers[I]; 549 if (EnableCheckProfiling) 550 Timer.setBucket(&TimeByBucket[MP.second->getID()]); 551 BoundNodesTreeBuilder Builder; 552 if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) { 553 MatchVisitor Visitor(ActiveASTContext, MP.second); 554 Builder.visitMatches(&Visitor); 555 } 556 } 557 } 558 559 const std::vector<unsigned short> & 560 getFilterForKind(ast_type_traits::ASTNodeKind Kind) { 561 auto &Filter = MatcherFiltersMap[Kind]; 562 auto &Matchers = this->Matchers->DeclOrStmt; 563 assert((Matchers.size() < USHRT_MAX) && "Too many matchers."); 564 for (unsigned I = 0, E = Matchers.size(); I != E; ++I) { 565 if (Matchers[I].first.canMatchNodesOfKind(Kind)) { 566 Filter.push_back(I); 567 } 568 } 569 return Filter; 570 } 571 572 /// @{ 573 /// \brief Overloads to pair the different node types to their matchers. 574 void matchDispatch(const Decl *Node) { 575 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node)); 576 } 577 void matchDispatch(const Stmt *Node) { 578 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node)); 579 } 580 581 void matchDispatch(const Type *Node) { 582 matchWithoutFilter(QualType(Node, 0), Matchers->Type); 583 } 584 void matchDispatch(const TypeLoc *Node) { 585 matchWithoutFilter(*Node, Matchers->TypeLoc); 586 } 587 void matchDispatch(const QualType *Node) { 588 matchWithoutFilter(*Node, Matchers->Type); 589 } 590 void matchDispatch(const NestedNameSpecifier *Node) { 591 matchWithoutFilter(*Node, Matchers->NestedNameSpecifier); 592 } 593 void matchDispatch(const NestedNameSpecifierLoc *Node) { 594 matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc); 595 } 596 void matchDispatch(const void *) { /* Do nothing. */ } 597 /// @} 598 599 // Returns whether an ancestor of \p Node matches \p Matcher. 600 // 601 // The order of matching ((which can lead to different nodes being bound in 602 // case there are multiple matches) is breadth first search. 603 // 604 // To allow memoization in the very common case of having deeply nested 605 // expressions inside a template function, we first walk up the AST, memoizing 606 // the result of the match along the way, as long as there is only a single 607 // parent. 608 // 609 // Once there are multiple parents, the breadth first search order does not 610 // allow simple memoization on the ancestors. Thus, we only memoize as long 611 // as there is a single parent. 612 bool memoizedMatchesAncestorOfRecursively( 613 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, 614 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { 615 if (Node.get<TranslationUnitDecl>() == 616 ActiveASTContext->getTranslationUnitDecl()) 617 return false; 618 619 // For AST-nodes that don't have an identity, we can't memoize. 620 if (!Builder->isComparable()) 621 return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode); 622 623 MatchKey Key; 624 Key.MatcherID = Matcher.getID(); 625 Key.Node = Node; 626 Key.BoundNodes = *Builder; 627 628 // Note that we cannot use insert and reuse the iterator, as recursive 629 // calls to match might invalidate the result cache iterators. 630 MemoizationMap::iterator I = ResultCache.find(Key); 631 if (I != ResultCache.end()) { 632 *Builder = I->second.Nodes; 633 return I->second.ResultOfMatch; 634 } 635 636 MemoizedMatchResult Result; 637 Result.Nodes = *Builder; 638 Result.ResultOfMatch = 639 matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode); 640 641 MemoizedMatchResult &CachedResult = ResultCache[Key]; 642 CachedResult = std::move(Result); 643 644 *Builder = CachedResult.Nodes; 645 return CachedResult.ResultOfMatch; 646 } 647 648 bool matchesAncestorOfRecursively(const ast_type_traits::DynTypedNode &Node, 649 const DynTypedMatcher &Matcher, 650 BoundNodesTreeBuilder *Builder, 651 AncestorMatchMode MatchMode) { 652 const auto &Parents = ActiveASTContext->getParents(Node); 653 assert(!Parents.empty() && "Found node that is not in the parent map."); 654 if (Parents.size() == 1) { 655 // Only one parent - do recursive memoization. 656 const ast_type_traits::DynTypedNode Parent = Parents[0]; 657 BoundNodesTreeBuilder BuilderCopy = *Builder; 658 if (Matcher.matches(Parent, this, &BuilderCopy)) { 659 *Builder = std::move(BuilderCopy); 660 return true; 661 } 662 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 663 return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder, 664 MatchMode); 665 // Once we get back from the recursive call, the result will be the 666 // same as the parent's result. 667 } 668 } else { 669 // Multiple parents - BFS over the rest of the nodes. 670 llvm::DenseSet<const void *> Visited; 671 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(), 672 Parents.end()); 673 while (!Queue.empty()) { 674 BoundNodesTreeBuilder BuilderCopy = *Builder; 675 if (Matcher.matches(Queue.front(), this, &BuilderCopy)) { 676 *Builder = std::move(BuilderCopy); 677 return true; 678 } 679 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 680 for (const auto &Parent : 681 ActiveASTContext->getParents(Queue.front())) { 682 // Make sure we do not visit the same node twice. 683 // Otherwise, we'll visit the common ancestors as often as there 684 // are splits on the way down. 685 if (Visited.insert(Parent.getMemoizationData()).second) 686 Queue.push_back(Parent); 687 } 688 } 689 Queue.pop_front(); 690 } 691 } 692 return false; 693 } 694 695 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with 696 // the aggregated bound nodes for each match. 697 class MatchVisitor : public BoundNodesTreeBuilder::Visitor { 698 public: 699 MatchVisitor(ASTContext* Context, 700 MatchFinder::MatchCallback* Callback) 701 : Context(Context), 702 Callback(Callback) {} 703 704 void visitMatch(const BoundNodes& BoundNodesView) override { 705 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context)); 706 } 707 708 private: 709 ASTContext* Context; 710 MatchFinder::MatchCallback* Callback; 711 }; 712 713 // Returns true if 'TypeNode' has an alias that matches the given matcher. 714 bool typeHasMatchingAlias(const Type *TypeNode, 715 const Matcher<NamedDecl> &Matcher, 716 BoundNodesTreeBuilder *Builder) { 717 const Type *const CanonicalType = 718 ActiveASTContext->getCanonicalType(TypeNode); 719 for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) { 720 BoundNodesTreeBuilder Result(*Builder); 721 if (Matcher.matches(*Alias, this, &Result)) { 722 *Builder = std::move(Result); 723 return true; 724 } 725 } 726 return false; 727 } 728 729 /// \brief Bucket to record map. 730 /// 731 /// Used to get the appropriate bucket for each matcher. 732 llvm::StringMap<llvm::TimeRecord> TimeByBucket; 733 734 const MatchFinder::MatchersByType *Matchers; 735 736 /// \brief Filtered list of matcher indices for each matcher kind. 737 /// 738 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node 739 /// kind (and derived kinds) so it is a waste to try every matcher on every 740 /// node. 741 /// We precalculate a list of matchers that pass the toplevel restrict check. 742 /// This also allows us to skip the restrict check at matching time. See 743 /// use \c matchesNoKindCheck() above. 744 llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>> 745 MatcherFiltersMap; 746 747 const MatchFinder::MatchFinderOptions &Options; 748 ASTContext *ActiveASTContext; 749 750 // Maps a canonical type to its TypedefDecls. 751 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases; 752 753 // Maps (matcher, node) -> the match result for memoization. 754 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap; 755 MemoizationMap ResultCache; 756 }; 757 758 static CXXRecordDecl * 759 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) { 760 if (auto *RD = TypeNode->getAsCXXRecordDecl()) 761 return RD; 762 763 // Find the innermost TemplateSpecializationType that isn't an alias template. 764 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>(); 765 while (TemplateType && TemplateType->isTypeAlias()) 766 TemplateType = 767 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>(); 768 769 // If this is the name of a (dependent) template specialization, use the 770 // definition of the template, even though it might be specialized later. 771 if (TemplateType) 772 if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>( 773 TemplateType->getTemplateName().getAsTemplateDecl())) 774 return ClassTemplate->getTemplatedDecl(); 775 776 return nullptr; 777 } 778 779 // Returns true if the given class is directly or indirectly derived 780 // from a base type with the given name. A class is not considered to be 781 // derived from itself. 782 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration, 783 const Matcher<NamedDecl> &Base, 784 BoundNodesTreeBuilder *Builder) { 785 if (!Declaration->hasDefinition()) 786 return false; 787 for (const auto &It : Declaration->bases()) { 788 const Type *TypeNode = It.getType().getTypePtr(); 789 790 if (typeHasMatchingAlias(TypeNode, Base, Builder)) 791 return true; 792 793 // FIXME: Going to the primary template here isn't really correct, but 794 // unfortunately we accept a Decl matcher for the base class not a Type 795 // matcher, so it's the best thing we can do with our current interface. 796 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode); 797 if (!ClassDecl) 798 continue; 799 if (ClassDecl == Declaration) { 800 // This can happen for recursive template definitions; if the 801 // current declaration did not match, we can safely return false. 802 return false; 803 } 804 BoundNodesTreeBuilder Result(*Builder); 805 if (Base.matches(*ClassDecl, this, &Result)) { 806 *Builder = std::move(Result); 807 return true; 808 } 809 if (classIsDerivedFrom(ClassDecl, Base, Builder)) 810 return true; 811 } 812 return false; 813 } 814 815 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) { 816 if (!DeclNode) { 817 return true; 818 } 819 match(*DeclNode); 820 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode); 821 } 822 823 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) { 824 if (!StmtNode) { 825 return true; 826 } 827 match(*StmtNode); 828 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode); 829 } 830 831 bool MatchASTVisitor::TraverseType(QualType TypeNode) { 832 match(TypeNode); 833 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode); 834 } 835 836 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) { 837 // The RecursiveASTVisitor only visits types if they're not within TypeLocs. 838 // We still want to find those types via matchers, so we match them here. Note 839 // that the TypeLocs are structurally a shadow-hierarchy to the expressed 840 // type, so we visit all involved parts of a compound type when matching on 841 // each TypeLoc. 842 match(TypeLocNode); 843 match(TypeLocNode.getType()); 844 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode); 845 } 846 847 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { 848 match(*NNS); 849 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS); 850 } 851 852 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc( 853 NestedNameSpecifierLoc NNS) { 854 if (!NNS) 855 return true; 856 857 match(NNS); 858 859 // We only match the nested name specifier here (as opposed to traversing it) 860 // because the traversal is already done in the parallel "Loc"-hierarchy. 861 if (NNS.hasQualifier()) 862 match(*NNS.getNestedNameSpecifier()); 863 return 864 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS); 865 } 866 867 class MatchASTConsumer : public ASTConsumer { 868 public: 869 MatchASTConsumer(MatchFinder *Finder, 870 MatchFinder::ParsingDoneTestCallback *ParsingDone) 871 : Finder(Finder), ParsingDone(ParsingDone) {} 872 873 private: 874 void HandleTranslationUnit(ASTContext &Context) override { 875 if (ParsingDone != nullptr) { 876 ParsingDone->run(); 877 } 878 Finder->matchAST(Context); 879 } 880 881 MatchFinder *Finder; 882 MatchFinder::ParsingDoneTestCallback *ParsingDone; 883 }; 884 885 } // end namespace 886 } // end namespace internal 887 888 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes, 889 ASTContext *Context) 890 : Nodes(Nodes), Context(Context), 891 SourceManager(&Context->getSourceManager()) {} 892 893 MatchFinder::MatchCallback::~MatchCallback() {} 894 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {} 895 896 MatchFinder::MatchFinder(MatchFinderOptions Options) 897 : Options(std::move(Options)), ParsingDone(nullptr) {} 898 899 MatchFinder::~MatchFinder() {} 900 901 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch, 902 MatchCallback *Action) { 903 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action); 904 Matchers.AllCallbacks.insert(Action); 905 } 906 907 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch, 908 MatchCallback *Action) { 909 Matchers.Type.emplace_back(NodeMatch, Action); 910 Matchers.AllCallbacks.insert(Action); 911 } 912 913 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch, 914 MatchCallback *Action) { 915 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action); 916 Matchers.AllCallbacks.insert(Action); 917 } 918 919 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch, 920 MatchCallback *Action) { 921 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action); 922 Matchers.AllCallbacks.insert(Action); 923 } 924 925 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch, 926 MatchCallback *Action) { 927 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action); 928 Matchers.AllCallbacks.insert(Action); 929 } 930 931 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch, 932 MatchCallback *Action) { 933 Matchers.TypeLoc.emplace_back(NodeMatch, Action); 934 Matchers.AllCallbacks.insert(Action); 935 } 936 937 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, 938 MatchCallback *Action) { 939 if (NodeMatch.canConvertTo<Decl>()) { 940 addMatcher(NodeMatch.convertTo<Decl>(), Action); 941 return true; 942 } else if (NodeMatch.canConvertTo<QualType>()) { 943 addMatcher(NodeMatch.convertTo<QualType>(), Action); 944 return true; 945 } else if (NodeMatch.canConvertTo<Stmt>()) { 946 addMatcher(NodeMatch.convertTo<Stmt>(), Action); 947 return true; 948 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) { 949 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action); 950 return true; 951 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) { 952 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action); 953 return true; 954 } else if (NodeMatch.canConvertTo<TypeLoc>()) { 955 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action); 956 return true; 957 } 958 return false; 959 } 960 961 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() { 962 return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone); 963 } 964 965 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node, 966 ASTContext &Context) { 967 internal::MatchASTVisitor Visitor(&Matchers, Options); 968 Visitor.set_active_ast_context(&Context); 969 Visitor.match(Node); 970 } 971 972 void MatchFinder::matchAST(ASTContext &Context) { 973 internal::MatchASTVisitor Visitor(&Matchers, Options); 974 Visitor.set_active_ast_context(&Context); 975 Visitor.onStartOfTranslationUnit(); 976 Visitor.TraverseDecl(Context.getTranslationUnitDecl()); 977 Visitor.onEndOfTranslationUnit(); 978 } 979 980 void MatchFinder::registerTestCallbackAfterParsing( 981 MatchFinder::ParsingDoneTestCallback *NewParsingDone) { 982 ParsingDone = NewParsingDone; 983 } 984 985 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; } 986 987 } // end namespace ast_matchers 988 } // end namespace clang 989