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