clang/lib/ASTMatchers/ASTMatchFinder.cpp

   1 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  Implements an algorithm to efficiently search for matches on AST nodes.
  10 //  Uses memoization to support recursive matches like HasDescendant.
  11 //
  12 //  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
  13 //  calling the Matches(...) method of each matcher we are running on each
  14 //  AST node. The matcher can recurse via the ASTMatchFinder interface.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "clang/ASTMatchers/ASTMatchFinder.h"
  19 #include "clang/AST/ASTConsumer.h"
  20 #include "clang/AST/ASTContext.h"
  21 #include "clang/AST/DeclCXX.h"
  22 #include "clang/AST/RecursiveASTVisitor.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/Support/PrettyStackTrace.h"
  27 #include "llvm/Support/Timer.h"
  28 #include <deque>
  29 #include <memory>
  30 #include <set>
  31
  32 namespace clang {
  33 namespace ast_matchers {
  34 namespace internal {
  35 namespace {
  36
  37 typedef MatchFinder::MatchCallback MatchCallback;
  38
  39 // The maximum number of memoization entries to store.
  40 // 10k has been experimentally found to give a good trade-off
  41 // of performance vs. memory consumption by running matcher
  42 // that match on every statement over a very large codebase.
  43 //
  44 // FIXME: Do some performance optimization in general and
  45 // revisit this number; also, put up micro-benchmarks that we can
  46 // optimize this on.
  47 static const unsigned MaxMemoizationEntries = 10000;
  48
  49 enum class MatchType {
  50   Ancestors,
  51
  52   Descendants,
  53   Child,
  54 };
  55
  56 // We use memoization to avoid running the same matcher on the same
  57 // AST node twice.  This struct is the key for looking up match
  58 // result.  It consists of an ID of the MatcherInterface (for
  59 // identifying the matcher), a pointer to the AST node and the
  60 // bound nodes before the matcher was executed.
  61 //
  62 // We currently only memoize on nodes whose pointers identify the
  63 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
  64 // For \c QualType and \c TypeLoc it is possible to implement
  65 // generation of keys for each type.
  66 // FIXME: Benchmark whether memoization of non-pointer typed nodes
  67 // provides enough benefit for the additional amount of code.
  68 struct MatchKey {
  69   DynTypedMatcher::MatcherIDType MatcherID;
  70   DynTypedNode Node;
  71   BoundNodesTreeBuilder BoundNodes;
  72   TraversalKind Traversal = TK_AsIs;
  73   MatchType Type;
  74
  75   bool operator<(const MatchKey &Other) const {
  76     return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
  77            std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
  78                     Other.BoundNodes);
  79   }
  80 };
  81
  82 // Used to store the result of a match and possibly bound nodes.
  83 struct MemoizedMatchResult {
  84   bool ResultOfMatch;
  85   BoundNodesTreeBuilder Nodes;
  86 };
  87
  88 // A RecursiveASTVisitor that traverses all children or all descendants of
  89 // a node.
  90 class MatchChildASTVisitor
  91     : public RecursiveASTVisitor<MatchChildASTVisitor> {
  92 public:
  93   typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
  94
  95   // Creates an AST visitor that matches 'matcher' on all children or
  96   // descendants of a traversed node. max_depth is the maximum depth
  97   // to traverse: use 1 for matching the children and INT_MAX for
  98   // matching the descendants.
  99   MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
 100                        BoundNodesTreeBuilder *Builder, int MaxDepth,
 101                        bool IgnoreImplicitChildren,
 102                        ASTMatchFinder::BindKind Bind)
 103       : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
 104         MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
 105         Bind(Bind), Matches(false) {}
 106
 107   // Returns true if a match is found in the subtree rooted at the
 108   // given AST node. This is done via a set of mutually recursive
 109   // functions. Here's how the recursion is done (the  *wildcard can
 110   // actually be Decl, Stmt, or Type):
 111   //
 112   //   - Traverse(node) calls BaseTraverse(node) when it needs
 113   //     to visit the descendants of node.
 114   //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
 115   //     Traverse*(c) for each child c of 'node'.
 116   //   - Traverse*(c) in turn calls Traverse(c), completing the
 117   //     recursion.
 118   bool findMatch(const DynTypedNode &DynNode) {
 119     reset();
 120     if (const Decl *D = DynNode.get<Decl>())
 121       traverse(*D);
 122     else if (const Stmt *S = DynNode.get<Stmt>())
 123       traverse(*S);
 124     else if (const NestedNameSpecifier *NNS =
 125              DynNode.get<NestedNameSpecifier>())
 126       traverse(*NNS);
 127     else if (const NestedNameSpecifierLoc *NNSLoc =
 128              DynNode.get<NestedNameSpecifierLoc>())
 129       traverse(*NNSLoc);
 130     else if (const QualType *Q = DynNode.get<QualType>())
 131       traverse(*Q);
 132     else if (const TypeLoc *T = DynNode.get<TypeLoc>())
 133       traverse(*T);
 134     else if (const auto *C = DynNode.get<CXXCtorInitializer>())
 135       traverse(*C);
 136     else if (const TemplateArgumentLoc *TALoc =
 137                  DynNode.get<TemplateArgumentLoc>())
 138       traverse(*TALoc);
 139     else if (const Attr *A = DynNode.get<Attr>())
 140       traverse(*A);
 141     // FIXME: Add other base types after adding tests.
 142
 143     // It's OK to always overwrite the bound nodes, as if there was
 144     // no match in this recursive branch, the result set is empty
 145     // anyway.
 146     *Builder = ResultBindings;
 147
 148     return Matches;
 149   }
 150
 151   // The following are overriding methods from the base visitor class.
 152   // They are public only to allow CRTP to work. They are *not *part
 153   // of the public API of this class.
 154   bool TraverseDecl(Decl *DeclNode) {
 155
 156     if (DeclNode && DeclNode->isImplicit() &&
 157         Finder->isTraversalIgnoringImplicitNodes())
 158       return baseTraverse(*DeclNode);
 159
 160     ScopedIncrement ScopedDepth(&CurrentDepth);
 161     return (DeclNode == nullptr) || traverse(*DeclNode);
 162   }
 163
 164   Stmt *getStmtToTraverse(Stmt *StmtNode) {
 165     Stmt *StmtToTraverse = StmtNode;
 166     if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
 167       auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
 168       if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
 169         StmtToTraverse = LambdaNode;
 170       else
 171         StmtToTraverse =
 172             Finder->getASTContext().getParentMapContext().traverseIgnored(
 173                 ExprNode);
 174     }
 175     return StmtToTraverse;
 176   }
 177
 178   bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
 179     // If we need to keep track of the depth, we can't perform data recursion.
 180     if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
 181       Queue = nullptr;
 182
 183     ScopedIncrement ScopedDepth(&CurrentDepth);
 184     Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
 185     if (!StmtToTraverse)
 186       return true;
 187
 188     if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
 189       return true;
 190
 191     if (!match(*StmtToTraverse))
 192       return false;
 193     return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
 194   }
 195   // We assume that the QualType and the contained type are on the same
 196   // hierarchy level. Thus, we try to match either of them.
 197   bool TraverseType(QualType TypeNode) {
 198     if (TypeNode.isNull())
 199       return true;
 200     ScopedIncrement ScopedDepth(&CurrentDepth);
 201     // Match the Type.
 202     if (!match(*TypeNode))
 203       return false;
 204     // The QualType is matched inside traverse.
 205     return traverse(TypeNode);
 206   }
 207   // We assume that the TypeLoc, contained QualType and contained Type all are
 208   // on the same hierarchy level. Thus, we try to match all of them.
 209   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
 210     if (TypeLocNode.isNull())
 211       return true;
 212     ScopedIncrement ScopedDepth(&CurrentDepth);
 213     // Match the Type.
 214     if (!match(*TypeLocNode.getType()))
 215       return false;
 216     // Match the QualType.
 217     if (!match(TypeLocNode.getType()))
 218       return false;
 219     // The TypeLoc is matched inside traverse.
 220     return traverse(TypeLocNode);
 221   }
 222   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
 223     ScopedIncrement ScopedDepth(&CurrentDepth);
 224     return (NNS == nullptr) || traverse(*NNS);
 225   }
 226   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
 227     if (!NNS)
 228       return true;
 229     ScopedIncrement ScopedDepth(&CurrentDepth);
 230     if (!match(*NNS.getNestedNameSpecifier()))
 231       return false;
 232     return traverse(NNS);
 233   }
 234   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
 235     if (!CtorInit)
 236       return true;
 237     ScopedIncrement ScopedDepth(&CurrentDepth);
 238     return traverse(*CtorInit);
 239   }
 240   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
 241     ScopedIncrement ScopedDepth(&CurrentDepth);
 242     return traverse(TAL);
 243   }
 244   bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
 245     if (!Finder->isTraversalIgnoringImplicitNodes())
 246       return VisitorBase::TraverseCXXForRangeStmt(Node);
 247     if (!Node)
 248       return true;
 249     ScopedIncrement ScopedDepth(&CurrentDepth);
 250     if (auto *Init = Node->getInit())
 251       if (!traverse(*Init))
 252         return false;
 253     if (!match(*Node->getLoopVariable()))
 254       return false;
 255     if (match(*Node->getRangeInit()))
 256       if (!VisitorBase::TraverseStmt(Node->getRangeInit()))
 257         return false;
 258     if (!match(*Node->getBody()))
 259       return false;
 260     return VisitorBase::TraverseStmt(Node->getBody());
 261   }
 262   bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
 263     if (!Finder->isTraversalIgnoringImplicitNodes())
 264       return VisitorBase::TraverseCXXRewrittenBinaryOperator(Node);
 265     if (!Node)
 266       return true;
 267     ScopedIncrement ScopedDepth(&CurrentDepth);
 268
 269     return match(*Node->getLHS()) && match(*Node->getRHS());
 270   }
 271   bool TraverseAttr(Attr *A) {
 272     if (A == nullptr ||
 273         (A->isImplicit() &&
 274          Finder->getASTContext().getParentMapContext().getTraversalKind() ==
 275              TK_IgnoreUnlessSpelledInSource))
 276       return true;
 277     ScopedIncrement ScopedDepth(&CurrentDepth);
 278     return traverse(*A);
 279   }
 280   bool TraverseLambdaExpr(LambdaExpr *Node) {
 281     if (!Finder->isTraversalIgnoringImplicitNodes())
 282       return VisitorBase::TraverseLambdaExpr(Node);
 283     if (!Node)
 284       return true;
 285     ScopedIncrement ScopedDepth(&CurrentDepth);
 286
 287     for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
 288       const LambdaCapture *C = Node->capture_begin() + I;
 289       if (!C->isExplicit())
 290         continue;
 291       if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))
 292         return false;
 293       const Expr *CIE = Node->capture_init_begin()[I];
 294       if (CIE != nullptr && !match(*CIE))
 295         return false;
 296     }
 297
 298     if (const auto *TPL = Node->getTemplateParameterList()) {
 299       for (const auto *TP : *TPL) {
 300         if (!match(*TP))
 301           return false;
 302       }
 303     }
 304
 305     for (const auto *P : Node->getCallOperator()->parameters()) {
 306       if (!match(*P))
 307         return false;
 308     }
 309
 310     if (!match(*Node->getBody()))
 311       return false;
 312
 313     return VisitorBase::TraverseStmt(Node->getBody());
 314   }
 315
 316   bool shouldVisitTemplateInstantiations() const { return true; }
 317   bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
 318
 319 private:
 320   // Used for updating the depth during traversal.
 321   struct ScopedIncrement {
 322     explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
 323     ~ScopedIncrement() { --(*Depth); }
 324
 325    private:
 326     int *Depth;
 327   };
 328
 329   // Resets the state of this object.
 330   void reset() {
 331     Matches = false;
 332     CurrentDepth = 0;
 333   }
 334
 335   // Forwards the call to the corresponding Traverse*() method in the
 336   // base visitor class.
 337   bool baseTraverse(const Decl &DeclNode) {
 338     return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
 339   }
 340   bool baseTraverse(const Stmt &StmtNode) {
 341     return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
 342   }
 343   bool baseTraverse(QualType TypeNode) {
 344     return VisitorBase::TraverseType(TypeNode);
 345   }
 346   bool baseTraverse(TypeLoc TypeLocNode) {
 347     return VisitorBase::TraverseTypeLoc(TypeLocNode);
 348   }
 349   bool baseTraverse(const NestedNameSpecifier &NNS) {
 350     return VisitorBase::TraverseNestedNameSpecifier(
 351         const_cast<NestedNameSpecifier*>(&NNS));
 352   }
 353   bool baseTraverse(NestedNameSpecifierLoc NNS) {
 354     return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
 355   }
 356   bool baseTraverse(const CXXCtorInitializer &CtorInit) {
 357     return VisitorBase::TraverseConstructorInitializer(
 358         const_cast<CXXCtorInitializer *>(&CtorInit));
 359   }
 360   bool baseTraverse(TemplateArgumentLoc TAL) {
 361     return VisitorBase::TraverseTemplateArgumentLoc(TAL);
 362   }
 363   bool baseTraverse(const Attr &AttrNode) {
 364     return VisitorBase::TraverseAttr(const_cast<Attr *>(&AttrNode));
 365   }
 366
 367   // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
 368   //   0 < CurrentDepth <= MaxDepth.
 369   //
 370   // Returns 'true' if traversal should continue after this function
 371   // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
 372   template <typename T>
 373   bool match(const T &Node) {
 374     if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
 375       return true;
 376     }
 377     if (Bind != ASTMatchFinder::BK_All) {
 378       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 379       if (Matcher->matches(DynTypedNode::create(Node), Finder,
 380                            &RecursiveBuilder)) {
 381         Matches = true;
 382         ResultBindings.addMatch(RecursiveBuilder);
 383         return false; // Abort as soon as a match is found.
 384       }
 385     } else {
 386       BoundNodesTreeBuilder RecursiveBuilder(*Builder);
 387       if (Matcher->matches(DynTypedNode::create(Node), Finder,
 388                            &RecursiveBuilder)) {
 389         // After the first match the matcher succeeds.
 390         Matches = true;
 391         ResultBindings.addMatch(RecursiveBuilder);
 392       }
 393     }
 394     return true;
 395   }
 396
 397   // Traverses the subtree rooted at 'Node'; returns true if the
 398   // traversal should continue after this function returns.
 399   template <typename T>
 400   bool traverse(const T &Node) {
 401     static_assert(IsBaseType<T>::value,
 402                   "traverse can only be instantiated with base type");
 403     if (!match(Node))
 404       return false;
 405     return baseTraverse(Node);
 406   }
 407
 408   const DynTypedMatcher *const Matcher;
 409   ASTMatchFinder *const Finder;
 410   BoundNodesTreeBuilder *const Builder;
 411   BoundNodesTreeBuilder ResultBindings;
 412   int CurrentDepth;
 413   const int MaxDepth;
 414   const bool IgnoreImplicitChildren;
 415   const ASTMatchFinder::BindKind Bind;
 416   bool Matches;
 417 };
 418
 419 // Controls the outermost traversal of the AST and allows to match multiple
 420 // matchers.
 421 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
 422                         public ASTMatchFinder {
 423 public:
 424   MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
 425                   const MatchFinder::MatchFinderOptions &Options)
 426       : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
 427
 428   ~MatchASTVisitor() override {
 429     if (Options.CheckProfiling) {
 430       Options.CheckProfiling->Records = std::move(TimeByBucket);
 431     }
 432   }
 433
 434   void onStartOfTranslationUnit() {
 435     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
 436     TimeBucketRegion Timer;
 437     for (MatchCallback *MC : Matchers->AllCallbacks) {
 438       if (EnableCheckProfiling)
 439         Timer.setBucket(&TimeByBucket[MC->getID()]);
 440       MC->onStartOfTranslationUnit();
 441     }
 442   }
 443
 444   void onEndOfTranslationUnit() {
 445     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
 446     TimeBucketRegion Timer;
 447     for (MatchCallback *MC : Matchers->AllCallbacks) {
 448       if (EnableCheckProfiling)
 449         Timer.setBucket(&TimeByBucket[MC->getID()]);
 450       MC->onEndOfTranslationUnit();
 451     }
 452   }
 453
 454   void set_active_ast_context(ASTContext *NewActiveASTContext) {
 455     ActiveASTContext = NewActiveASTContext;
 456   }
 457
 458   // The following Visit*() and Traverse*() functions "override"
 459   // methods in RecursiveASTVisitor.
 460
 461   bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
 462     // When we see 'typedef A B', we add name 'B' to the set of names
 463     // A's canonical type maps to.  This is necessary for implementing
 464     // isDerivedFrom(x) properly, where x can be the name of the base
 465     // class or any of its aliases.
 466     //
 467     // In general, the is-alias-of (as defined by typedefs) relation
 468     // is tree-shaped, as you can typedef a type more than once.  For
 469     // example,
 470     //
 471     //   typedef A B;
 472     //   typedef A C;
 473     //   typedef C D;
 474     //   typedef C E;
 475     //
 476     // gives you
 477     //
 478     //   A
 479     //   |- B
 480     //   `- C
 481     //      |- D
 482     //      `- E
 483     //
 484     // It is wrong to assume that the relation is a chain.  A correct
 485     // implementation of isDerivedFrom() needs to recognize that B and
 486     // E are aliases, even though neither is a typedef of the other.
 487     // Therefore, we cannot simply walk through one typedef chain to
 488     // find out whether the type name matches.
 489     const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
 490     const Type *CanonicalType =  // root of the typedef tree
 491         ActiveASTContext->getCanonicalType(TypeNode);
 492     TypeAliases[CanonicalType].insert(DeclNode);
 493     return true;
 494   }
 495
 496   bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
 497     const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
 498     CompatibleAliases[InterfaceDecl].insert(CAD);
 499     return true;
 500   }
 501
 502   bool TraverseDecl(Decl *DeclNode);
 503   bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
 504   bool TraverseType(QualType TypeNode);
 505   bool TraverseTypeLoc(TypeLoc TypeNode);
 506   bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
 507   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
 508   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
 509   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
 510   bool TraverseAttr(Attr *AttrNode);
 511
 512   bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
 513     if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
 514       {
 515         ASTNodeNotAsIsSourceScope RAII(this, true);
 516         TraverseStmt(RF->getInit());
 517         // Don't traverse under the loop variable
 518         match(*RF->getLoopVariable());
 519         TraverseStmt(RF->getRangeInit());
 520       }
 521       {
 522         ASTNodeNotSpelledInSourceScope RAII(this, true);
 523         for (auto *SubStmt : RF->children()) {
 524           if (SubStmt != RF->getBody())
 525             TraverseStmt(SubStmt);
 526         }
 527       }
 528       TraverseStmt(RF->getBody());
 529       return true;
 530     } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
 531       {
 532         ASTNodeNotAsIsSourceScope RAII(this, true);
 533         TraverseStmt(const_cast<Expr *>(RBO->getLHS()));
 534         TraverseStmt(const_cast<Expr *>(RBO->getRHS()));
 535       }
 536       {
 537         ASTNodeNotSpelledInSourceScope RAII(this, true);
 538         for (auto *SubStmt : RBO->children()) {
 539           TraverseStmt(SubStmt);
 540         }
 541       }
 542       return true;
 543     } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {
 544       for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {
 545         auto C = std::get<0>(I);
 546         ASTNodeNotSpelledInSourceScope RAII(
 547             this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
 548         TraverseLambdaCapture(LE, &C, std::get<1>(I));
 549       }
 550
 551       {
 552         ASTNodeNotSpelledInSourceScope RAII(this, true);
 553         TraverseDecl(LE->getLambdaClass());
 554       }
 555       {
 556         ASTNodeNotAsIsSourceScope RAII(this, true);
 557
 558         // We need to poke around to find the bits that might be explicitly
 559         // written.
 560         TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
 561         FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
 562
 563         if (auto *TPL = LE->getTemplateParameterList()) {
 564           for (NamedDecl *D : *TPL) {
 565             TraverseDecl(D);
 566           }
 567           if (Expr *RequiresClause = TPL->getRequiresClause()) {
 568             TraverseStmt(RequiresClause);
 569           }
 570         }
 571
 572         if (LE->hasExplicitParameters()) {
 573           // Visit parameters.
 574           for (ParmVarDecl *Param : Proto.getParams())
 575             TraverseDecl(Param);
 576         }
 577
 578         const auto *T = Proto.getTypePtr();
 579         for (const auto &E : T->exceptions())
 580           TraverseType(E);
 581
 582         if (Expr *NE = T->getNoexceptExpr())
 583           TraverseStmt(NE, Queue);
 584
 585         if (LE->hasExplicitResultType())
 586           TraverseTypeLoc(Proto.getReturnLoc());
 587         TraverseStmt(LE->getTrailingRequiresClause());
 588       }
 589
 590       TraverseStmt(LE->getBody());
 591       return true;
 592     }
 593     return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);
 594   }
 595
 596   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 597   bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
 598                                   const DynTypedMatcher &Matcher,
 599                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
 600                                   BindKind Bind) {
 601     // For AST-nodes that don't have an identity, we can't memoize.
 602     if (!Node.getMemoizationData() || !Builder->isComparable())
 603       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
 604
 605     MatchKey Key;
 606     Key.MatcherID = Matcher.getID();
 607     Key.Node = Node;
 608     // Note that we key on the bindings *before* the match.
 609     Key.BoundNodes = *Builder;
 610     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
 611     // Memoize result even doing a single-level match, it might be expensive.
 612     Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
 613     MemoizationMap::iterator I = ResultCache.find(Key);
 614     if (I != ResultCache.end()) {
 615       *Builder = I->second.Nodes;
 616       return I->second.ResultOfMatch;
 617     }
 618
 619     MemoizedMatchResult Result;
 620     Result.Nodes = *Builder;
 621     Result.ResultOfMatch =
 622         matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);
 623
 624     MemoizedMatchResult &CachedResult = ResultCache[Key];
 625     CachedResult = std::move(Result);
 626
 627     *Builder = CachedResult.Nodes;
 628     return CachedResult.ResultOfMatch;
 629   }
 630
 631   // Matches children or descendants of 'Node' with 'BaseMatcher'.
 632   bool matchesRecursively(const DynTypedNode &Node,
 633                           const DynTypedMatcher &Matcher,
 634                           BoundNodesTreeBuilder *Builder, int MaxDepth,
 635                           BindKind Bind) {
 636     bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
 637                            TraversingASTChildrenNotSpelledInSource;
 638
 639     bool IgnoreImplicitChildren = false;
 640
 641     if (isTraversalIgnoringImplicitNodes()) {
 642       IgnoreImplicitChildren = true;
 643     }
 644
 645     ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
 646
 647     MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
 648                                  IgnoreImplicitChildren, Bind);
 649     return Visitor.findMatch(Node);
 650   }
 651
 652   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
 653                           const Matcher<NamedDecl> &Base,
 654                           BoundNodesTreeBuilder *Builder,
 655                           bool Directly) override;
 656
 657 private:
 658   bool
 659   classIsDerivedFromImpl(const CXXRecordDecl *Declaration,
 660                          const Matcher<NamedDecl> &Base,
 661                          BoundNodesTreeBuilder *Builder, bool Directly,
 662                          llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited);
 663
 664 public:
 665   bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
 666                               const Matcher<NamedDecl> &Base,
 667                               BoundNodesTreeBuilder *Builder,
 668                               bool Directly) override;
 669
 670 public:
 671   // Implements ASTMatchFinder::matchesChildOf.
 672   bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
 673                       const DynTypedMatcher &Matcher,
 674                       BoundNodesTreeBuilder *Builder, BindKind Bind) override {
 675     if (ResultCache.size() > MaxMemoizationEntries)
 676       ResultCache.clear();
 677     return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);
 678   }
 679   // Implements ASTMatchFinder::matchesDescendantOf.
 680   bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
 681                            const DynTypedMatcher &Matcher,
 682                            BoundNodesTreeBuilder *Builder,
 683                            BindKind Bind) override {
 684     if (ResultCache.size() > MaxMemoizationEntries)
 685       ResultCache.clear();
 686     return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
 687                                       Bind);
 688   }
 689   // Implements ASTMatchFinder::matchesAncestorOf.
 690   bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
 691                          const DynTypedMatcher &Matcher,
 692                          BoundNodesTreeBuilder *Builder,
 693                          AncestorMatchMode MatchMode) override {
 694     // Reset the cache outside of the recursive call to make sure we
 695     // don't invalidate any iterators.
 696     if (ResultCache.size() > MaxMemoizationEntries)
 697       ResultCache.clear();
 698     if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
 699       return matchesParentOf(Node, Matcher, Builder);
 700     return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
 701   }
 702
 703   // Matches all registered matchers on the given node and calls the
 704   // result callback for every node that matches.
 705   void match(const DynTypedNode &Node) {
 706     // FIXME: Improve this with a switch or a visitor pattern.
 707     if (auto *N = Node.get<Decl>()) {
 708       match(*N);
 709     } else if (auto *N = Node.get<Stmt>()) {
 710       match(*N);
 711     } else if (auto *N = Node.get<Type>()) {
 712       match(*N);
 713     } else if (auto *N = Node.get<QualType>()) {
 714       match(*N);
 715     } else if (auto *N = Node.get<NestedNameSpecifier>()) {
 716       match(*N);
 717     } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
 718       match(*N);
 719     } else if (auto *N = Node.get<TypeLoc>()) {
 720       match(*N);
 721     } else if (auto *N = Node.get<CXXCtorInitializer>()) {
 722       match(*N);
 723     } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
 724       match(*N);
 725     } else if (auto *N = Node.get<Attr>()) {
 726       match(*N);
 727     }
 728   }
 729
 730   template <typename T> void match(const T &Node) {
 731     matchDispatch(&Node);
 732   }
 733
 734   // Implements ASTMatchFinder::getASTContext.
 735   ASTContext &getASTContext() const override { return *ActiveASTContext; }
 736
 737   bool shouldVisitTemplateInstantiations() const { return true; }
 738   bool shouldVisitImplicitCode() const { return true; }
 739
 740   // We visit the lambda body explicitly, so instruct the RAV
 741   // to not visit it on our behalf too.
 742   bool shouldVisitLambdaBody() const { return false; }
 743
 744   bool IsMatchingInASTNodeNotSpelledInSource() const override {
 745     return TraversingASTNodeNotSpelledInSource;
 746   }
 747   bool isMatchingChildrenNotSpelledInSource() const override {
 748     return TraversingASTChildrenNotSpelledInSource;
 749   }
 750   void setMatchingChildrenNotSpelledInSource(bool Set) override {
 751     TraversingASTChildrenNotSpelledInSource = Set;
 752   }
 753
 754   bool IsMatchingInASTNodeNotAsIs() const override {
 755     return TraversingASTNodeNotAsIs;
 756   }
 757
 758   bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
 759     ASTNodeNotSpelledInSourceScope RAII(this, true);
 760     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
 761         D);
 762   }
 763
 764   bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
 765     ASTNodeNotSpelledInSourceScope RAII(this, true);
 766     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
 767         D);
 768   }
 769
 770   bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
 771     ASTNodeNotSpelledInSourceScope RAII(this, true);
 772     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
 773         D);
 774   }
 775
 776 private:
 777   bool TraversingASTNodeNotSpelledInSource = false;
 778   bool TraversingASTNodeNotAsIs = false;
 779   bool TraversingASTChildrenNotSpelledInSource = false;
 780
 781   class CurMatchData {
 782 // We don't have enough free low bits in 32bit builds to discriminate 8 pointer
 783 // types in PointerUnion. so split the union in 2 using a free bit from the
 784 // callback pointer.
 785 #define CMD_TYPES_0                                                            \
 786   const QualType *, const TypeLoc *, const NestedNameSpecifier *,              \
 787       const NestedNameSpecifierLoc *
 788 #define CMD_TYPES_1                                                            \
 789   const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *,       \
 790       const DynTypedNode *
 791
 792 #define IMPL(Index)                                                            \
 793   template <typename NodeType>                                                 \
 794   std::enable_if_t<                                                            \
 795       llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value>             \
 796   SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) {          \
 797     assertEmpty();                                                             \
 798     Callback.setPointerAndInt(CB, Index);                                      \
 799     Node##Index = &N;                                                          \
 800   }                                                                            \
 801                                                                                \
 802   template <typename T>                                                        \
 803   std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value,       \
 804                    const T *>                                                  \
 805   getNode() const {                                                            \
 806     assertHoldsState();                                                        \
 807     return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>()    \
 808                                         : nullptr;                             \
 809   }
 810
 811   public:
 812     CurMatchData() : Node0(nullptr) {}
 813
 814     IMPL(0)
 815     IMPL(1)
 816
 817     const MatchCallback *getCallback() const { return Callback.getPointer(); }
 818
 819     void SetBoundNodes(const BoundNodes &BN) {
 820       assertHoldsState();
 821       BNodes = &BN;
 822     }
 823
 824     void clearBoundNodes() {
 825       assertHoldsState();
 826       BNodes = nullptr;
 827     }
 828
 829     const BoundNodes *getBoundNodes() const {
 830       assertHoldsState();
 831       return BNodes;
 832     }
 833
 834     void reset() {
 835       assertHoldsState();
 836       Callback.setPointerAndInt(nullptr, 0);
 837       Node0 = nullptr;
 838     }
 839
 840   private:
 841     void assertHoldsState() const {
 842       assert(Callback.getPointer() != nullptr && !Node0.isNull());
 843     }
 844
 845     void assertEmpty() const {
 846       assert(Callback.getPointer() == nullptr && Node0.isNull() &&
 847              BNodes == nullptr);
 848     }
 849
 850     llvm::PointerIntPair<const MatchCallback *, 1> Callback;
 851     union {
 852       llvm::PointerUnion<CMD_TYPES_0> Node0;
 853       llvm::PointerUnion<CMD_TYPES_1> Node1;
 854     };
 855     const BoundNodes *BNodes = nullptr;
 856
 857 #undef CMD_TYPES_0
 858 #undef CMD_TYPES_1
 859 #undef IMPL
 860   } CurMatchState;
 861
 862   struct CurMatchRAII {
 863     template <typename NodeType>
 864     CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,
 865                  const NodeType &NT)
 866         : MV(MV) {
 867       MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
 868     }
 869
 870     ~CurMatchRAII() { MV.CurMatchState.reset(); }
 871
 872   private:
 873     MatchASTVisitor &MV;
 874   };
 875
 876 public:
 877   class TraceReporter : llvm::PrettyStackTraceEntry {
 878     static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,
 879                          raw_ostream &OS) {
 880       if (const auto *D = Node.get<Decl>()) {
 881         OS << D->getDeclKindName() << "Decl ";
 882         if (const auto *ND = dyn_cast<NamedDecl>(D)) {
 883           ND->printQualifiedName(OS);
 884           OS << " : ";
 885         } else
 886           OS << ": ";
 887         D->getSourceRange().print(OS, Ctx.getSourceManager());
 888       } else if (const auto *S = Node.get<Stmt>()) {
 889         OS << S->getStmtClassName() << " : ";
 890         S->getSourceRange().print(OS, Ctx.getSourceManager());
 891       } else if (const auto *T = Node.get<Type>()) {
 892         OS << T->getTypeClassName() << "Type : ";
 893         QualType(T, 0).print(OS, Ctx.getPrintingPolicy());
 894       } else if (const auto *QT = Node.get<QualType>()) {
 895         OS << "QualType : ";
 896         QT->print(OS, Ctx.getPrintingPolicy());
 897       } else {
 898         OS << Node.getNodeKind().asStringRef() << " : ";
 899         Node.getSourceRange().print(OS, Ctx.getSourceManager());
 900       }
 901     }
 902
 903     static void dumpNodeFromState(const ASTContext &Ctx,
 904                                   const CurMatchData &State, raw_ostream &OS) {
 905       if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {
 906         dumpNode(Ctx, *MatchNode, OS);
 907       } else if (const auto *QT = State.getNode<QualType>()) {
 908         dumpNode(Ctx, DynTypedNode::create(*QT), OS);
 909       } else if (const auto *TL = State.getNode<TypeLoc>()) {
 910         dumpNode(Ctx, DynTypedNode::create(*TL), OS);
 911       } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {
 912         dumpNode(Ctx, DynTypedNode::create(*NNS), OS);
 913       } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {
 914         dumpNode(Ctx, DynTypedNode::create(*NNSL), OS);
 915       } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {
 916         dumpNode(Ctx, DynTypedNode::create(*CtorInit), OS);
 917       } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {
 918         dumpNode(Ctx, DynTypedNode::create(*TAL), OS);
 919       } else if (const auto *At = State.getNode<Attr>()) {
 920         dumpNode(Ctx, DynTypedNode::create(*At), OS);
 921       }
 922     }
 923
 924   public:
 925     TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}
 926     void print(raw_ostream &OS) const override {
 927       const CurMatchData &State = MV.CurMatchState;
 928       const MatchCallback *CB = State.getCallback();
 929       if (!CB) {
 930         OS << "ASTMatcher: Not currently matching\n";
 931         return;
 932       }
 933
 934       assert(MV.ActiveASTContext &&
 935              "ActiveASTContext should be set if there is a matched callback");
 936
 937       ASTContext &Ctx = MV.getASTContext();
 938
 939       if (const BoundNodes *Nodes = State.getBoundNodes()) {
 940         OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";
 941         dumpNodeFromState(Ctx, State, OS);
 942         const BoundNodes::IDToNodeMap &Map = Nodes->getMap();
 943         if (Map.empty()) {
 944           OS << "\nNo bound nodes\n";
 945           return;
 946         }
 947         OS << "\n--- Bound Nodes Begin ---\n";
 948         for (const auto &Item : Map) {
 949           OS << "    " << Item.first << " - { ";
 950           dumpNode(Ctx, Item.second, OS);
 951           OS << " }\n";
 952         }
 953         OS << "--- Bound Nodes End ---\n";
 954       } else {
 955         OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";
 956         dumpNodeFromState(Ctx, State, OS);
 957         OS << '\n';
 958       }
 959     }
 960
 961   private:
 962     const MatchASTVisitor &MV;
 963   };
 964
 965 private:
 966   struct ASTNodeNotSpelledInSourceScope {
 967     ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
 968         : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
 969       V->TraversingASTNodeNotSpelledInSource = B;
 970     }
 971     ~ASTNodeNotSpelledInSourceScope() {
 972       MV->TraversingASTNodeNotSpelledInSource = MB;
 973     }
 974
 975   private:
 976     MatchASTVisitor *MV;
 977     bool MB;
 978   };
 979
 980   struct ASTNodeNotAsIsSourceScope {
 981     ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
 982         : MV(V), MB(V->TraversingASTNodeNotAsIs) {
 983       V->TraversingASTNodeNotAsIs = B;
 984     }
 985     ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
 986
 987   private:
 988     MatchASTVisitor *MV;
 989     bool MB;
 990   };
 991
 992   class TimeBucketRegion {
 993   public:
 994     TimeBucketRegion() = default;
 995     ~TimeBucketRegion() { setBucket(nullptr); }
 996
 997     /// Start timing for \p NewBucket.
 998     ///
 999     /// If there was a bucket already set, it will finish the timing for that
1000     /// other bucket.
1001     /// \p NewBucket will be timed until the next call to \c setBucket() or
1002     /// until the \c TimeBucketRegion is destroyed.
1003     /// If \p NewBucket is the same as the currently timed bucket, this call
1004     /// does nothing.
1005     void setBucket(llvm::TimeRecord *NewBucket) {
1006       if (Bucket != NewBucket) {
1007         auto Now = llvm::TimeRecord::getCurrentTime(true);
1008         if (Bucket)
1009           *Bucket += Now;
1010         if (NewBucket)
1011           *NewBucket -= Now;
1012         Bucket = NewBucket;
1013       }
1014     }
1015
1016   private:
1017     llvm::TimeRecord *Bucket = nullptr;
1018   };
1019
1020   /// Runs all the \p Matchers on \p Node.
1021   ///
1022   /// Used by \c matchDispatch() below.
1023   template <typename T, typename MC>
1024   void matchWithoutFilter(const T &Node, const MC &Matchers) {
1025     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1026     TimeBucketRegion Timer;
1027     for (const auto &MP : Matchers) {
1028       if (EnableCheckProfiling)
1029         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1030       BoundNodesTreeBuilder Builder;
1031       CurMatchRAII RAII(*this, MP.second, Node);
1032       if (MP.first.matches(Node, this, &Builder)) {
1033         MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1034         Builder.visitMatches(&Visitor);
1035       }
1036     }
1037   }
1038
1039   void matchWithFilter(const DynTypedNode &DynNode) {
1040     auto Kind = DynNode.getNodeKind();
1041     auto it = MatcherFiltersMap.find(Kind);
1042     const auto &Filter =
1043         it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
1044
1045     if (Filter.empty())
1046       return;
1047
1048     const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1049     TimeBucketRegion Timer;
1050     auto &Matchers = this->Matchers->DeclOrStmt;
1051     for (unsigned short I : Filter) {
1052       auto &MP = Matchers[I];
1053       if (EnableCheckProfiling)
1054         Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1055       BoundNodesTreeBuilder Builder;
1056
1057       {
1058         TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
1059         if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
1060             DynNode)
1061           continue;
1062       }
1063
1064       CurMatchRAII RAII(*this, MP.second, DynNode);
1065       if (MP.first.matches(DynNode, this, &Builder)) {
1066         MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1067         Builder.visitMatches(&Visitor);
1068       }
1069     }
1070   }
1071
1072   const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
1073     auto &Filter = MatcherFiltersMap[Kind];
1074     auto &Matchers = this->Matchers->DeclOrStmt;
1075     assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
1076     for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
1077       if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
1078         Filter.push_back(I);
1079       }
1080     }
1081     return Filter;
1082   }
1083
1084   /// @{
1085   /// Overloads to pair the different node types to their matchers.
1086   void matchDispatch(const Decl *Node) {
1087     return matchWithFilter(DynTypedNode::create(*Node));
1088   }
1089   void matchDispatch(const Stmt *Node) {
1090     return matchWithFilter(DynTypedNode::create(*Node));
1091   }
1092
1093   void matchDispatch(const Type *Node) {
1094     matchWithoutFilter(QualType(Node, 0), Matchers->Type);
1095   }
1096   void matchDispatch(const TypeLoc *Node) {
1097     matchWithoutFilter(*Node, Matchers->TypeLoc);
1098   }
1099   void matchDispatch(const QualType *Node) {
1100     matchWithoutFilter(*Node, Matchers->Type);
1101   }
1102   void matchDispatch(const NestedNameSpecifier *Node) {
1103     matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
1104   }
1105   void matchDispatch(const NestedNameSpecifierLoc *Node) {
1106     matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
1107   }
1108   void matchDispatch(const CXXCtorInitializer *Node) {
1109     matchWithoutFilter(*Node, Matchers->CtorInit);
1110   }
1111   void matchDispatch(const TemplateArgumentLoc *Node) {
1112     matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);
1113   }
1114   void matchDispatch(const Attr *Node) {
1115     matchWithoutFilter(*Node, Matchers->Attr);
1116   }
1117   void matchDispatch(const void *) { /* Do nothing. */ }
1118   /// @}
1119
1120   // Returns whether a direct parent of \p Node matches \p Matcher.
1121   // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
1122   bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
1123                        BoundNodesTreeBuilder *Builder) {
1124     for (const auto &Parent : ActiveASTContext->getParents(Node)) {
1125       BoundNodesTreeBuilder BuilderCopy = *Builder;
1126       if (Matcher.matches(Parent, this, &BuilderCopy)) {
1127         *Builder = std::move(BuilderCopy);
1128         return true;
1129       }
1130     }
1131     return false;
1132   }
1133
1134   // Returns whether an ancestor of \p Node matches \p Matcher.
1135   //
1136   // The order of matching (which can lead to different nodes being bound in
1137   // case there are multiple matches) is breadth first search.
1138   //
1139   // To allow memoization in the very common case of having deeply nested
1140   // expressions inside a template function, we first walk up the AST, memoizing
1141   // the result of the match along the way, as long as there is only a single
1142   // parent.
1143   //
1144   // Once there are multiple parents, the breadth first search order does not
1145   // allow simple memoization on the ancestors. Thus, we only memoize as long
1146   // as there is a single parent.
1147   //
1148   // We avoid a recursive implementation to prevent excessive stack use on
1149   // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
1150   bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
1151                             const DynTypedMatcher &Matcher,
1152                             BoundNodesTreeBuilder *Builder) {
1153
1154     // Memoization keys that can be updated with the result.
1155     // These are the memoizable nodes in the chain of unique parents, which
1156     // terminates when a node has multiple parents, or matches, or is the root.
1157     std::vector<MatchKey> Keys;
1158     // When returning, update the memoization cache.
1159     auto Finish = [&](bool Matched) {
1160       for (const auto &Key : Keys) {
1161         MemoizedMatchResult &CachedResult = ResultCache[Key];
1162         CachedResult.ResultOfMatch = Matched;
1163         CachedResult.Nodes = *Builder;
1164       }
1165       return Matched;
1166     };
1167
1168     // Loop while there's a single parent and we want to attempt memoization.
1169     DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
1170     for (;;) {
1171       // A cache key only makes sense if memoization is possible.
1172       if (Builder->isComparable()) {
1173         Keys.emplace_back();
1174         Keys.back().MatcherID = Matcher.getID();
1175         Keys.back().Node = Node;
1176         Keys.back().BoundNodes = *Builder;
1177         Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
1178         Keys.back().Type = MatchType::Ancestors;
1179
1180         // Check the cache.
1181         MemoizationMap::iterator I = ResultCache.find(Keys.back());
1182         if (I != ResultCache.end()) {
1183           Keys.pop_back(); // Don't populate the cache for the matching node!
1184           *Builder = I->second.Nodes;
1185           return Finish(I->second.ResultOfMatch);
1186         }
1187       }
1188
1189       Parents = ActiveASTContext->getParents(Node);
1190       // Either no parents or multiple parents: leave chain+memoize mode and
1191       // enter bfs+forgetful mode.
1192       if (Parents.size() != 1)
1193         break;
1194
1195       // Check the next parent.
1196       Node = *Parents.begin();
1197       BoundNodesTreeBuilder BuilderCopy = *Builder;
1198       if (Matcher.matches(Node, this, &BuilderCopy)) {
1199         *Builder = std::move(BuilderCopy);
1200         return Finish(true);
1201       }
1202     }
1203     // We reached the end of the chain.
1204
1205     if (Parents.empty()) {
1206       // Nodes may have no parents if:
1207       //  a) the node is the TranslationUnitDecl
1208       //  b) we have a limited traversal scope that excludes the parent edges
1209       //  c) there is a bug in the AST, and the node is not reachable
1210       // Usually the traversal scope is the whole AST, which precludes b.
1211       // Bugs are common enough that it's worthwhile asserting when we can.
1212 #ifndef NDEBUG
1213       if (!Node.get<TranslationUnitDecl>() &&
1214           /* Traversal scope is full AST if any of the bounds are the TU */
1215           llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
1216             return D->getKind() == Decl::TranslationUnit;
1217           })) {
1218         llvm::errs() << "Tried to match orphan node:\n";
1219         Node.dump(llvm::errs(), *ActiveASTContext);
1220         llvm_unreachable("Parent map should be complete!");
1221       }
1222 #endif
1223     } else {
1224       assert(Parents.size() > 1);
1225       // BFS starting from the parents not yet considered.
1226       // Memoization of newly visited nodes is not possible (but we still update
1227       // results for the elements in the chain we found above).
1228       std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1229       llvm::DenseSet<const void *> Visited;
1230       while (!Queue.empty()) {
1231         BoundNodesTreeBuilder BuilderCopy = *Builder;
1232         if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
1233           *Builder = std::move(BuilderCopy);
1234           return Finish(true);
1235         }
1236         for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {
1237           // Make sure we do not visit the same node twice.
1238           // Otherwise, we'll visit the common ancestors as often as there
1239           // are splits on the way down.
1240           if (Visited.insert(Parent.getMemoizationData()).second)
1241             Queue.push_back(Parent);
1242         }
1243         Queue.pop_front();
1244       }
1245     }
1246     return Finish(false);
1247   }
1248
1249   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
1250   // the aggregated bound nodes for each match.
1251   class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
1252     struct CurBoundScope {
1253       CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)
1254           : State(State) {
1255         State.SetBoundNodes(BN);
1256       }
1257
1258       ~CurBoundScope() { State.clearBoundNodes(); }
1259
1260     private:
1261       MatchASTVisitor::CurMatchData &State;
1262     };
1263
1264   public:
1265     MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
1266                  MatchFinder::MatchCallback *Callback)
1267         : State(MV.CurMatchState), Context(Context), Callback(Callback) {}
1268
1269     void visitMatch(const BoundNodes& BoundNodesView) override {
1270       TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
1271       CurBoundScope RAII2(State, BoundNodesView);
1272       Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
1273     }
1274
1275   private:
1276     MatchASTVisitor::CurMatchData &State;
1277     ASTContext* Context;
1278     MatchFinder::MatchCallback* Callback;
1279   };
1280
1281   // Returns true if 'TypeNode' has an alias that matches the given matcher.
1282   bool typeHasMatchingAlias(const Type *TypeNode,
1283                             const Matcher<NamedDecl> &Matcher,
1284                             BoundNodesTreeBuilder *Builder) {
1285     const Type *const CanonicalType =
1286       ActiveASTContext->getCanonicalType(TypeNode);
1287     auto Aliases = TypeAliases.find(CanonicalType);
1288     if (Aliases == TypeAliases.end())
1289       return false;
1290     for (const TypedefNameDecl *Alias : Aliases->second) {
1291       BoundNodesTreeBuilder Result(*Builder);
1292       if (Matcher.matches(*Alias, this, &Result)) {
1293         *Builder = std::move(Result);
1294         return true;
1295       }
1296     }
1297     return false;
1298   }
1299
1300   bool
1301   objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
1302                                          const Matcher<NamedDecl> &Matcher,
1303                                          BoundNodesTreeBuilder *Builder) {
1304     auto Aliases = CompatibleAliases.find(InterfaceDecl);
1305     if (Aliases == CompatibleAliases.end())
1306       return false;
1307     for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1308       BoundNodesTreeBuilder Result(*Builder);
1309       if (Matcher.matches(*Alias, this, &Result)) {
1310         *Builder = std::move(Result);
1311         return true;
1312       }
1313     }
1314     return false;
1315   }
1316
1317   /// Bucket to record map.
1318   ///
1319   /// Used to get the appropriate bucket for each matcher.
1320   llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1321
1322   const MatchFinder::MatchersByType *Matchers;
1323
1324   /// Filtered list of matcher indices for each matcher kind.
1325   ///
1326   /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
1327   /// kind (and derived kinds) so it is a waste to try every matcher on every
1328   /// node.
1329   /// We precalculate a list of matchers that pass the toplevel restrict check.
1330   llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1331
1332   const MatchFinder::MatchFinderOptions &Options;
1333   ASTContext *ActiveASTContext;
1334
1335   // Maps a canonical type to its TypedefDecls.
1336   llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1337
1338   // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
1339   llvm::DenseMap<const ObjCInterfaceDecl *,
1340                  llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
1341       CompatibleAliases;
1342
1343   // Maps (matcher, node) -> the match result for memoization.
1344   typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1345   MemoizationMap ResultCache;
1346 };
1347
1348 static CXXRecordDecl *
1349 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
1350   if (auto *RD = TypeNode->getAsCXXRecordDecl())
1351     return RD;
1352
1353   // Find the innermost TemplateSpecializationType that isn't an alias template.
1354   auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1355   while (TemplateType && TemplateType->isTypeAlias())
1356     TemplateType =
1357         TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1358
1359   // If this is the name of a (dependent) template specialization, use the
1360   // definition of the template, even though it might be specialized later.
1361   if (TemplateType)
1362     if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1363           TemplateType->getTemplateName().getAsTemplateDecl()))
1364       return ClassTemplate->getTemplatedDecl();
1365
1366   return nullptr;
1367 }
1368
1369 // Returns true if the given C++ class is directly or indirectly derived
1370 // from a base type with the given name.  A class is not considered to be
1371 // derived from itself.
1372 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
1373                                          const Matcher<NamedDecl> &Base,
1374                                          BoundNodesTreeBuilder *Builder,
1375                                          bool Directly) {
1376   llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;
1377   return classIsDerivedFromImpl(Declaration, Base, Builder, Directly, Visited);
1378 }
1379
1380 bool MatchASTVisitor::classIsDerivedFromImpl(
1381     const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,
1382     BoundNodesTreeBuilder *Builder, bool Directly,
1383     llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) {
1384   if (!Declaration->hasDefinition())
1385     return false;
1386   if (!Visited.insert(Declaration).second)
1387     return false;
1388   for (const auto &It : Declaration->bases()) {
1389     const Type *TypeNode = It.getType().getTypePtr();
1390
1391     if (typeHasMatchingAlias(TypeNode, Base, Builder))
1392       return true;
1393
1394     // FIXME: Going to the primary template here isn't really correct, but
1395     // unfortunately we accept a Decl matcher for the base class not a Type
1396     // matcher, so it's the best thing we can do with our current interface.
1397     CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1398     if (!ClassDecl)
1399       continue;
1400     if (ClassDecl == Declaration) {
1401       // This can happen for recursive template definitions.
1402       continue;
1403     }
1404     BoundNodesTreeBuilder Result(*Builder);
1405     if (Base.matches(*ClassDecl, this, &Result)) {
1406       *Builder = std::move(Result);
1407       return true;
1408     }
1409     if (!Directly &&
1410         classIsDerivedFromImpl(ClassDecl, Base, Builder, Directly, Visited))
1411       return true;
1412   }
1413   return false;
1414 }
1415
1416 // Returns true if the given Objective-C class is directly or indirectly
1417 // derived from a matching base class. A class is not considered to be derived
1418 // from itself.
1419 bool MatchASTVisitor::objcClassIsDerivedFrom(
1420     const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1421     BoundNodesTreeBuilder *Builder, bool Directly) {
1422   // Check if any of the superclasses of the class match.
1423   for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1424        ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1425     // Check if there are any matching compatibility aliases.
1426     if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
1427       return true;
1428
1429     // Check if there are any matching type aliases.
1430     const Type *TypeNode = ClassDecl->getTypeForDecl();
1431     if (typeHasMatchingAlias(TypeNode, Base, Builder))
1432       return true;
1433
1434     if (Base.matches(*ClassDecl, this, Builder))
1435       return true;
1436
1437     // Not `return false` as a temporary workaround for PR43879.
1438     if (Directly)
1439       break;
1440   }
1441
1442   return false;
1443 }
1444
1445 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1446   if (!DeclNode) {
1447     return true;
1448   }
1449
1450   bool ScopedTraversal =
1451       TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1452   bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1453
1454   if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1455     auto SK = CTSD->getSpecializationKind();
1456     if (SK == TSK_ExplicitInstantiationDeclaration ||
1457         SK == TSK_ExplicitInstantiationDefinition)
1458       ScopedChildren = true;
1459   } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1460     if (FD->isDefaulted())
1461       ScopedChildren = true;
1462     if (FD->isTemplateInstantiation())
1463       ScopedTraversal = true;
1464   } else if (isa<BindingDecl>(DeclNode)) {
1465     ScopedChildren = true;
1466   }
1467
1468   ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1469   ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
1470
1471   match(*DeclNode);
1472   return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
1473 }
1474
1475 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1476   if (!StmtNode) {
1477     return true;
1478   }
1479   bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1480                          TraversingASTChildrenNotSpelledInSource;
1481
1482   ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
1483   match(*StmtNode);
1484   return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue);
1485 }
1486
1487 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1488   match(TypeNode);
1489   return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
1490 }
1491
1492 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1493   // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
1494   // We still want to find those types via matchers, so we match them here. Note
1495   // that the TypeLocs are structurally a shadow-hierarchy to the expressed
1496   // type, so we visit all involved parts of a compound type when matching on
1497   // each TypeLoc.
1498   match(TypeLocNode);
1499   match(TypeLocNode.getType());
1500   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
1501 }
1502
1503 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1504   match(*NNS);
1505   return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
1506 }
1507
1508 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1509     NestedNameSpecifierLoc NNS) {
1510   if (!NNS)
1511     return true;
1512
1513   match(NNS);
1514
1515   // We only match the nested name specifier here (as opposed to traversing it)
1516   // because the traversal is already done in the parallel "Loc"-hierarchy.
1517   if (NNS.hasQualifier())
1518     match(*NNS.getNestedNameSpecifier());
1519   return
1520       RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
1521 }
1522
1523 bool MatchASTVisitor::TraverseConstructorInitializer(
1524     CXXCtorInitializer *CtorInit) {
1525   if (!CtorInit)
1526     return true;
1527
1528   bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1529                          TraversingASTChildrenNotSpelledInSource;
1530
1531   if (!CtorInit->isWritten())
1532     ScopedTraversal = true;
1533
1534   ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1535
1536   match(*CtorInit);
1537
1538   return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
1539       CtorInit);
1540 }
1541
1542 bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1543   match(Loc);
1544   return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(Loc);
1545 }
1546
1547 bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1548   match(*AttrNode);
1549   return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(AttrNode);
1550 }
1551
1552 class MatchASTConsumer : public ASTConsumer {
1553 public:
1554   MatchASTConsumer(MatchFinder *Finder,
1555                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
1556       : Finder(Finder), ParsingDone(ParsingDone) {}
1557
1558 private:
1559   void HandleTranslationUnit(ASTContext &Context) override {
1560     if (ParsingDone != nullptr) {
1561       ParsingDone->run();
1562     }
1563     Finder->matchAST(Context);
1564   }
1565
1566   MatchFinder *Finder;
1567   MatchFinder::ParsingDoneTestCallback *ParsingDone;
1568 };
1569
1570 } // end namespace
1571 } // end namespace internal
1572
1573 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
1574                                       ASTContext *Context)
1575   : Nodes(Nodes), Context(Context),
1576     SourceManager(&Context->getSourceManager()) {}
1577
1578 MatchFinder::MatchCallback::~MatchCallback() {}
1579 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
1580
1581 MatchFinder::MatchFinder(MatchFinderOptions Options)
1582     : Options(std::move(Options)), ParsingDone(nullptr) {}
1583
1584 MatchFinder::~MatchFinder() {}
1585
1586 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
1587                              MatchCallback *Action) {
1588   std::optional<TraversalKind> TK;
1589   if (Action)
1590     TK = Action->getCheckTraversalKind();
1591   if (TK)
1592     Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1593   else
1594     Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1595   Matchers.AllCallbacks.insert(Action);
1596 }
1597
1598 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1599                              MatchCallback *Action) {
1600   Matchers.Type.emplace_back(NodeMatch, Action);
1601   Matchers.AllCallbacks.insert(Action);
1602 }
1603
1604 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
1605                              MatchCallback *Action) {
1606   std::optional<TraversalKind> TK;
1607   if (Action)
1608     TK = Action->getCheckTraversalKind();
1609   if (TK)
1610     Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1611   else
1612     Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1613   Matchers.AllCallbacks.insert(Action);
1614 }
1615
1616 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
1617                              MatchCallback *Action) {
1618   Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1619   Matchers.AllCallbacks.insert(Action);
1620 }
1621
1622 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
1623                              MatchCallback *Action) {
1624   Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1625   Matchers.AllCallbacks.insert(Action);
1626 }
1627
1628 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
1629                              MatchCallback *Action) {
1630   Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1631   Matchers.AllCallbacks.insert(Action);
1632 }
1633
1634 void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
1635                              MatchCallback *Action) {
1636   Matchers.CtorInit.emplace_back(NodeMatch, Action);
1637   Matchers.AllCallbacks.insert(Action);
1638 }
1639
1640 void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
1641                              MatchCallback *Action) {
1642   Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1643   Matchers.AllCallbacks.insert(Action);
1644 }
1645
1646 void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
1647                              MatchCallback *Action) {
1648   Matchers.Attr.emplace_back(AttrMatch, Action);
1649   Matchers.AllCallbacks.insert(Action);
1650 }
1651
1652 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1653                                     MatchCallback *Action) {
1654   if (NodeMatch.canConvertTo<Decl>()) {
1655     addMatcher(NodeMatch.convertTo<Decl>(), Action);
1656     return true;
1657   } else if (NodeMatch.canConvertTo<QualType>()) {
1658     addMatcher(NodeMatch.convertTo<QualType>(), Action);
1659     return true;
1660   } else if (NodeMatch.canConvertTo<Stmt>()) {
1661     addMatcher(NodeMatch.convertTo<Stmt>(), Action);
1662     return true;
1663   } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1664     addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1665     return true;
1666   } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1667     addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1668     return true;
1669   } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1670     addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
1671     return true;
1672   } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1673     addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1674     return true;
1675   } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1676     addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1677     return true;
1678   } else if (NodeMatch.canConvertTo<Attr>()) {
1679     addMatcher(NodeMatch.convertTo<Attr>(), Action);
1680     return true;
1681   }
1682   return false;
1683 }
1684
1685 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1686   return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1687 }
1688
1689 void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
1690   internal::MatchASTVisitor Visitor(&Matchers, Options);
1691   Visitor.set_active_ast_context(&Context);
1692   Visitor.match(Node);
1693 }
1694
1695 void MatchFinder::matchAST(ASTContext &Context) {
1696   internal::MatchASTVisitor Visitor(&Matchers, Options);
1697   internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
1698   Visitor.set_active_ast_context(&Context);
1699   Visitor.onStartOfTranslationUnit();
1700   Visitor.TraverseAST(Context);
1701   Visitor.onEndOfTranslationUnit();
1702 }
1703
1704 void MatchFinder::registerTestCallbackAfterParsing(
1705     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1706   ParsingDone = NewParsingDone;
1707 }
1708
1709 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1710
1711 std::optional<TraversalKind>
1712 MatchFinder::MatchCallback::getCheckTraversalKind() const {
1713   return std::nullopt;
1714 }
1715
1716 } // end namespace ast_matchers
1717 } // end namespace clang