contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchFinder.cpp

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