Clang Project

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