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 MatchKey Key; 620 Key.MatcherID = Matcher.getID(); 621 Key.Node = Node; 622 Key.BoundNodes = *Builder; 623 624 // Note that we cannot use insert and reuse the iterator, as recursive 625 // calls to match might invalidate the result cache iterators. 626 MemoizationMap::iterator I = ResultCache.find(Key); 627 if (I != ResultCache.end()) { 628 *Builder = I->second.Nodes; 629 return I->second.ResultOfMatch; 630 } 631 632 MemoizedMatchResult Result; 633 Result.ResultOfMatch = false; 634 Result.Nodes = *Builder; 635 636 const auto &Parents = ActiveASTContext->getParents(Node); 637 assert(!Parents.empty() && "Found node that is not in the parent map."); 638 if (Parents.size() == 1) { 639 // Only one parent - do recursive memoization. 640 const ast_type_traits::DynTypedNode Parent = Parents[0]; 641 if (Matcher.matches(Parent, this, &Result.Nodes)) { 642 Result.ResultOfMatch = true; 643 } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 644 // Reset the results to not include the bound nodes from the failed 645 // match above. 646 Result.Nodes = *Builder; 647 Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively( 648 Parent, Matcher, &Result.Nodes, MatchMode); 649 // Once we get back from the recursive call, the result will be the 650 // same as the parent's result. 651 } 652 } else { 653 // Multiple parents - BFS over the rest of the nodes. 654 llvm::DenseSet<const void *> Visited; 655 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(), 656 Parents.end()); 657 while (!Queue.empty()) { 658 Result.Nodes = *Builder; 659 if (Matcher.matches(Queue.front(), this, &Result.Nodes)) { 660 Result.ResultOfMatch = true; 661 break; 662 } 663 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { 664 for (const auto &Parent : 665 ActiveASTContext->getParents(Queue.front())) { 666 // Make sure we do not visit the same node twice. 667 // Otherwise, we'll visit the common ancestors as often as there 668 // are splits on the way down. 669 if (Visited.insert(Parent.getMemoizationData()).second) 670 Queue.push_back(Parent); 671 } 672 } 673 Queue.pop_front(); 674 } 675 } 676 677 MemoizedMatchResult &CachedResult = ResultCache[Key]; 678 CachedResult = std::move(Result); 679 680 *Builder = CachedResult.Nodes; 681 return CachedResult.ResultOfMatch; 682 } 683 684 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with 685 // the aggregated bound nodes for each match. 686 class MatchVisitor : public BoundNodesTreeBuilder::Visitor { 687 public: 688 MatchVisitor(ASTContext* Context, 689 MatchFinder::MatchCallback* Callback) 690 : Context(Context), 691 Callback(Callback) {} 692 693 void visitMatch(const BoundNodes& BoundNodesView) override { 694 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context)); 695 } 696 697 private: 698 ASTContext* Context; 699 MatchFinder::MatchCallback* Callback; 700 }; 701 702 // Returns true if 'TypeNode' has an alias that matches the given matcher. 703 bool typeHasMatchingAlias(const Type *TypeNode, 704 const Matcher<NamedDecl> Matcher, 705 BoundNodesTreeBuilder *Builder) { 706 const Type *const CanonicalType = 707 ActiveASTContext->getCanonicalType(TypeNode); 708 for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) { 709 BoundNodesTreeBuilder Result(*Builder); 710 if (Matcher.matches(*Alias, this, &Result)) { 711 *Builder = std::move(Result); 712 return true; 713 } 714 } 715 return false; 716 } 717 718 /// \brief Bucket to record map. 719 /// 720 /// Used to get the appropriate bucket for each matcher. 721 llvm::StringMap<llvm::TimeRecord> TimeByBucket; 722 723 const MatchFinder::MatchersByType *Matchers; 724 725 /// \brief Filtered list of matcher indices for each matcher kind. 726 /// 727 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node 728 /// kind (and derived kinds) so it is a waste to try every matcher on every 729 /// node. 730 /// We precalculate a list of matchers that pass the toplevel restrict check. 731 /// This also allows us to skip the restrict check at matching time. See 732 /// use \c matchesNoKindCheck() above. 733 llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>> 734 MatcherFiltersMap; 735 736 const MatchFinder::MatchFinderOptions &Options; 737 ASTContext *ActiveASTContext; 738 739 // Maps a canonical type to its TypedefDecls. 740 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases; 741 742 // Maps (matcher, node) -> the match result for memoization. 743 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap; 744 MemoizationMap ResultCache; 745 }; 746 747 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) { 748 // Type::getAs<...>() drills through typedefs. 749 if (TypeNode->getAs<DependentNameType>() != nullptr || 750 TypeNode->getAs<DependentTemplateSpecializationType>() != nullptr || 751 TypeNode->getAs<TemplateTypeParmType>() != nullptr) 752 // Dependent names and template TypeNode parameters will be matched when 753 // the template is instantiated. 754 return nullptr; 755 TemplateSpecializationType const *TemplateType = 756 TypeNode->getAs<TemplateSpecializationType>(); 757 if (!TemplateType) { 758 return TypeNode->getAsCXXRecordDecl(); 759 } 760 if (TemplateType->getTemplateName().isDependent()) 761 // Dependent template specializations will be matched when the 762 // template is instantiated. 763 return nullptr; 764 765 // For template specialization types which are specializing a template 766 // declaration which is an explicit or partial specialization of another 767 // template declaration, getAsCXXRecordDecl() returns the corresponding 768 // ClassTemplateSpecializationDecl. 769 // 770 // For template specialization types which are specializing a template 771 // declaration which is neither an explicit nor partial specialization of 772 // another template declaration, getAsCXXRecordDecl() returns NULL and 773 // we get the CXXRecordDecl of the templated declaration. 774 CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl(); 775 if (SpecializationDecl) { 776 return SpecializationDecl; 777 } 778 NamedDecl *Templated = 779 TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(); 780 if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) { 781 return TemplatedRecord; 782 } 783 // Now it can still be that we have an alias template. 784 TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated); 785 assert(AliasDecl); 786 return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr()); 787 } 788 789 // Returns true if the given class is directly or indirectly derived 790 // from a base type with the given name. A class is not considered to be 791 // derived from itself. 792 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration, 793 const Matcher<NamedDecl> &Base, 794 BoundNodesTreeBuilder *Builder) { 795 if (!Declaration->hasDefinition()) 796 return false; 797 for (const auto &It : Declaration->bases()) { 798 const Type *TypeNode = It.getType().getTypePtr(); 799 800 if (typeHasMatchingAlias(TypeNode, Base, Builder)) 801 return true; 802 803 CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode); 804 if (!ClassDecl) 805 continue; 806 if (ClassDecl == Declaration) { 807 // This can happen for recursive template definitions; if the 808 // current declaration did not match, we can safely return false. 809 return false; 810 } 811 BoundNodesTreeBuilder Result(*Builder); 812 if (Base.matches(*ClassDecl, this, &Result)) { 813 *Builder = std::move(Result); 814 return true; 815 } 816 if (classIsDerivedFrom(ClassDecl, Base, Builder)) 817 return true; 818 } 819 return false; 820 } 821 822 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) { 823 if (!DeclNode) { 824 return true; 825 } 826 match(*DeclNode); 827 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode); 828 } 829 830 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) { 831 if (!StmtNode) { 832 return true; 833 } 834 match(*StmtNode); 835 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode); 836 } 837 838 bool MatchASTVisitor::TraverseType(QualType TypeNode) { 839 match(TypeNode); 840 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode); 841 } 842 843 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) { 844 // The RecursiveASTVisitor only visits types if they're not within TypeLocs. 845 // We still want to find those types via matchers, so we match them here. Note 846 // that the TypeLocs are structurally a shadow-hierarchy to the expressed 847 // type, so we visit all involved parts of a compound type when matching on 848 // each TypeLoc. 849 match(TypeLocNode); 850 match(TypeLocNode.getType()); 851 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode); 852 } 853 854 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { 855 match(*NNS); 856 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS); 857 } 858 859 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc( 860 NestedNameSpecifierLoc NNS) { 861 if (!NNS) 862 return true; 863 864 match(NNS); 865 866 // We only match the nested name specifier here (as opposed to traversing it) 867 // because the traversal is already done in the parallel "Loc"-hierarchy. 868 if (NNS.hasQualifier()) 869 match(*NNS.getNestedNameSpecifier()); 870 return 871 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS); 872 } 873 874 class MatchASTConsumer : public ASTConsumer { 875 public: 876 MatchASTConsumer(MatchFinder *Finder, 877 MatchFinder::ParsingDoneTestCallback *ParsingDone) 878 : Finder(Finder), ParsingDone(ParsingDone) {} 879 880 private: 881 void HandleTranslationUnit(ASTContext &Context) override { 882 if (ParsingDone != nullptr) { 883 ParsingDone->run(); 884 } 885 Finder->matchAST(Context); 886 } 887 888 MatchFinder *Finder; 889 MatchFinder::ParsingDoneTestCallback *ParsingDone; 890 }; 891 892 } // end namespace 893 } // end namespace internal 894 895 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes, 896 ASTContext *Context) 897 : Nodes(Nodes), Context(Context), 898 SourceManager(&Context->getSourceManager()) {} 899 900 MatchFinder::MatchCallback::~MatchCallback() {} 901 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {} 902 903 MatchFinder::MatchFinder(MatchFinderOptions Options) 904 : Options(std::move(Options)), ParsingDone(nullptr) {} 905 906 MatchFinder::~MatchFinder() {} 907 908 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch, 909 MatchCallback *Action) { 910 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action); 911 Matchers.AllCallbacks.insert(Action); 912 } 913 914 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch, 915 MatchCallback *Action) { 916 Matchers.Type.emplace_back(NodeMatch, Action); 917 Matchers.AllCallbacks.insert(Action); 918 } 919 920 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch, 921 MatchCallback *Action) { 922 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action); 923 Matchers.AllCallbacks.insert(Action); 924 } 925 926 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch, 927 MatchCallback *Action) { 928 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action); 929 Matchers.AllCallbacks.insert(Action); 930 } 931 932 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch, 933 MatchCallback *Action) { 934 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action); 935 Matchers.AllCallbacks.insert(Action); 936 } 937 938 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch, 939 MatchCallback *Action) { 940 Matchers.TypeLoc.emplace_back(NodeMatch, Action); 941 Matchers.AllCallbacks.insert(Action); 942 } 943 944 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, 945 MatchCallback *Action) { 946 if (NodeMatch.canConvertTo<Decl>()) { 947 addMatcher(NodeMatch.convertTo<Decl>(), Action); 948 return true; 949 } else if (NodeMatch.canConvertTo<QualType>()) { 950 addMatcher(NodeMatch.convertTo<QualType>(), Action); 951 return true; 952 } else if (NodeMatch.canConvertTo<Stmt>()) { 953 addMatcher(NodeMatch.convertTo<Stmt>(), Action); 954 return true; 955 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) { 956 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action); 957 return true; 958 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) { 959 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action); 960 return true; 961 } else if (NodeMatch.canConvertTo<TypeLoc>()) { 962 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action); 963 return true; 964 } 965 return false; 966 } 967 968 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() { 969 return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone); 970 } 971 972 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node, 973 ASTContext &Context) { 974 internal::MatchASTVisitor Visitor(&Matchers, Options); 975 Visitor.set_active_ast_context(&Context); 976 Visitor.match(Node); 977 } 978 979 void MatchFinder::matchAST(ASTContext &Context) { 980 internal::MatchASTVisitor Visitor(&Matchers, Options); 981 Visitor.set_active_ast_context(&Context); 982 Visitor.onStartOfTranslationUnit(); 983 Visitor.TraverseDecl(Context.getTranslationUnitDecl()); 984 Visitor.onEndOfTranslationUnit(); 985 } 986 987 void MatchFinder::registerTestCallbackAfterParsing( 988 MatchFinder::ParsingDoneTestCallback *NewParsingDone) { 989 ParsingDone = NewParsingDone; 990 } 991 992 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; } 993 994 } // end namespace ast_matchers 995 } // end namespace clang 996