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