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