clang  8.0.0svn
ASTMatchFinder.cpp
Go to the documentation of this file.
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 
20 #include "clang/AST/ASTConsumer.h"
21 #include "clang/AST/ASTContext.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;
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 {
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.
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);
847 }
848 
849 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
850  if (!StmtNode) {
851  return true;
852  }
853  match(*StmtNode);
855 }
856 
857 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
858  match(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());
871 }
872 
873 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
874  match(*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
891 }
892 
893 bool MatchASTVisitor::TraverseConstructorInitializer(
894  CXXCtorInitializer *CtorInit) {
895  if (!CtorInit)
896  return true;
897 
898  match(*CtorInit);
899 
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 
926  ASTContext *Context)
927  : Nodes(Nodes), Context(Context),
928  SourceManager(&Context->getSourceManager()) {}
929 
932 
934  : Options(std::move(Options)), ParsingDone(nullptr) {}
935 
937 
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 
951  MatchCallback *Action) {
952  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
953  Matchers.AllCallbacks.insert(Action);
954 }
955 
957  MatchCallback *Action) {
958  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
959  Matchers.AllCallbacks.insert(Action);
960 }
961 
963  MatchCallback *Action) {
964  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
965  Matchers.AllCallbacks.insert(Action);
966 }
967 
969  MatchCallback *Action) {
970  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
971  Matchers.AllCallbacks.insert(Action);
972 }
973 
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 
1012  ASTContext &Context) {
1013  internal::MatchASTVisitor Visitor(&Matchers, Options);
1014  Visitor.set_active_ast_context(&Context);
1015  Visitor.match(Node);
1016 }
1017 
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 
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
Defines the clang::ASTContext interface.
A (possibly-)qualified type.
Definition: Type.h:641
internal::Matcher< NestedNameSpecifier > NestedNameSpecifierMatcher
Definition: ASTMatchers.h:149
Stmt - This represents one statement.
Definition: Stmt.h:66
internal::Matcher< Stmt > StatementMatcher
Definition: ASTMatchers.h:146
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
llvm::SmallPtrSet< MatchCallback *, 16 > AllCallbacks
All the callbacks in one container to simplify iteration.
Called when parsing is finished. Intended for testing only.
MatchFinder(MatchFinderOptions Options=MatchFinderOptions())
internal::Matcher< QualType > TypeMatcher
Definition: ASTMatchers.h:147
BoundNodesTreeBuilder Nodes
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument&#39;s dynamic ty...
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:56
void match(const T &Node, ASTContext &Context)
Calls the registered callbacks on all matches on the given Node.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:153
A C++ nested-name-specifier augmented with source location information.
Definition: Format.h:2031
void addMatcher(const DeclarationMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.
std::vector< std::pair< CXXCtorInitializerMatcher, MatchCallback * > > CtorInit
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
DynTypedMatcher::MatcherIDType MatcherID
NodeId Parent
Definition: ASTDiff.cpp:192
bool TraverseConstructorInitializer(CXXCtorInitializer *Init)
Recursively visit a constructor initializer.
int Depth
Definition: ASTDiff.cpp:191
void registerTestCallbackAfterParsing(ParsingDoneTestCallback *ParsingDone)
Registers a callback to notify the end of parsing.
MatchResult(const BoundNodes &Nodes, clang::ASTContext *Context)
std::unique_ptr< clang::ASTConsumer > newASTConsumer()
Creates a clang ASTConsumer that finds all matches.
#define USHRT_MAX
Definition: limits.h:71
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:102
bool ResultOfMatch
Kind
virtual StringRef getID() const
An id used to group the matchers.
bool TraverseTypeLoc(TypeLoc TL)
Recursively visit a type with location, by dispatching to Traverse*TypeLoc() based on the argument ty...
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)
Recursively visit a C++ nested-name-specifier with location information.
Represents a C++ nested name specifier, such as "\::std::vector<int>::".
void matchAST(ASTContext &Context)
Finds all matches in the given AST.
std::vector< std::pair< NestedNameSpecifierLocMatcher, MatchCallback * > > NestedNameSpecifierLoc
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument&#39;s dy...
std::vector< std::pair< internal::DynTypedMatcher, MatchCallback * > > DeclOrStmt
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
bool TraverseType(QualType T)
Recursively visit a type, by dispatching to Traverse*Type() based on the argument&#39;s getTypeClass() pr...
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
std::vector< std::pair< NestedNameSpecifierMatcher, MatchCallback * > > NestedNameSpecifier
std::vector< std::pair< TypeMatcher, MatchCallback * > > Type
BoundNodesTreeBuilder BoundNodes
ast_type_traits::DynTypedNode DynTypedNode
ast_type_traits::DynTypedNode Node
Dataflow Directional Tag Classes.
internal::Matcher< CXXCtorInitializer > CXXCtorInitializerMatcher
Definition: ASTMatchers.h:151
A dynamically typed AST node container.
std::vector< std::pair< TypeLocMatcher, MatchCallback * > > TypeLoc
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2258
bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS)
Recursively visit a C++ nested-name-specifier.
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:1016
#define INT_MAX
Definition: limits.h:62
internal::Matcher< NestedNameSpecifierLoc > NestedNameSpecifierLocMatcher
Definition: ASTMatchers.h:150
internal::Matcher< TypeLoc > TypeLocMatcher
Definition: ASTMatchers.h:148
Called when the Match registered for it was successfully found in the AST.
This class handles loading and caching of source files into memory.
internal::Matcher< Decl > DeclarationMatcher
Types of matchers for the top-level classes in the AST class hierarchy.
Definition: ASTMatchers.h:145
bool addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.