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