clang  9.0.0svn
ASTMatchFinder.cpp
Go to the documentation of this file.
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 
19 #include "clang/AST/ASTConsumer.h"
20 #include "clang/AST/ASTContext.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 
29 namespace clang {
30 namespace ast_matchers {
31 namespace internal {
32 namespace {
33 
34 typedef 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.
44 static 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.
58 struct MatchKey {
59  DynTypedMatcher::MatcherIDType MatcherID;
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.
70 struct MemoizedMatchResult {
72  BoundNodesTreeBuilder Nodes;
73 };
74 
75 // A RecursiveASTVisitor that traverses all children or all descendants of
76 // a node.
77 class MatchChildASTVisitor
78  : public RecursiveASTVisitor<MatchChildASTVisitor> {
79 public:
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, ASTMatchFinder *Finder,
87  BoundNodesTreeBuilder *Builder, int MaxDepth,
89  ASTMatchFinder::BindKind Bind)
90  : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
91  MaxDepth(MaxDepth), Traversal(Traversal), Bind(Bind), Matches(false) {}
92 
93  // Returns true if a match is found in the subtree rooted at the
94  // given AST node. This is done via a set of mutually recursive
95  // functions. Here's how the recursion is done (the *wildcard can
96  // actually be Decl, Stmt, or Type):
97  //
98  // - Traverse(node) calls BaseTraverse(node) when it needs
99  // to visit the descendants of node.
100  // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
101  // Traverse*(c) for each child c of 'node'.
102  // - Traverse*(c) in turn calls Traverse(c), completing the
103  // recursion.
104  bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
105  reset();
106  if (const Decl *D = DynNode.get<Decl>())
107  traverse(*D);
108  else if (const Stmt *S = DynNode.get<Stmt>())
109  traverse(*S);
110  else if (const NestedNameSpecifier *NNS =
111  DynNode.get<NestedNameSpecifier>())
112  traverse(*NNS);
113  else if (const NestedNameSpecifierLoc *NNSLoc =
114  DynNode.get<NestedNameSpecifierLoc>())
115  traverse(*NNSLoc);
116  else if (const QualType *Q = DynNode.get<QualType>())
117  traverse(*Q);
118  else if (const TypeLoc *T = DynNode.get<TypeLoc>())
119  traverse(*T);
120  else if (const auto *C = DynNode.get<CXXCtorInitializer>())
121  traverse(*C);
122  // FIXME: Add other base types after adding tests.
123 
124  // It's OK to always overwrite the bound nodes, as if there was
125  // no match in this recursive branch, the result set is empty
126  // anyway.
127  *Builder = ResultBindings;
128 
129  return Matches;
130  }
131 
132  // The following are overriding methods from the base visitor class.
133  // They are public only to allow CRTP to work. They are *not *part
134  // of the public API of this class.
135  bool TraverseDecl(Decl *DeclNode) {
136  ScopedIncrement ScopedDepth(&CurrentDepth);
137  return (DeclNode == nullptr) || traverse(*DeclNode);
138  }
139  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
140  // If we need to keep track of the depth, we can't perform data recursion.
141  if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
142  Queue = nullptr;
143 
144  ScopedIncrement ScopedDepth(&CurrentDepth);
145  Stmt *StmtToTraverse = StmtNode;
146  if (Traversal ==
148  if (Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode))
149  StmtToTraverse = ExprNode->IgnoreParenImpCasts();
150  }
151  if (!StmtToTraverse)
152  return true;
153  if (!match(*StmtToTraverse))
154  return false;
155  return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
156  }
157  // We assume that the QualType and the contained type are on the same
158  // hierarchy level. Thus, we try to match either of them.
159  bool TraverseType(QualType TypeNode) {
160  if (TypeNode.isNull())
161  return true;
162  ScopedIncrement ScopedDepth(&CurrentDepth);
163  // Match the Type.
164  if (!match(*TypeNode))
165  return false;
166  // The QualType is matched inside traverse.
167  return traverse(TypeNode);
168  }
169  // We assume that the TypeLoc, contained QualType and contained Type all are
170  // on the same hierarchy level. Thus, we try to match all of them.
171  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
172  if (TypeLocNode.isNull())
173  return true;
174  ScopedIncrement ScopedDepth(&CurrentDepth);
175  // Match the Type.
176  if (!match(*TypeLocNode.getType()))
177  return false;
178  // Match the QualType.
179  if (!match(TypeLocNode.getType()))
180  return false;
181  // The TypeLoc is matched inside traverse.
182  return traverse(TypeLocNode);
183  }
184  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
185  ScopedIncrement ScopedDepth(&CurrentDepth);
186  return (NNS == nullptr) || traverse(*NNS);
187  }
188  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
189  if (!NNS)
190  return true;
191  ScopedIncrement ScopedDepth(&CurrentDepth);
192  if (!match(*NNS.getNestedNameSpecifier()))
193  return false;
194  return traverse(NNS);
195  }
196  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
197  if (!CtorInit)
198  return true;
199  ScopedIncrement ScopedDepth(&CurrentDepth);
200  return traverse(*CtorInit);
201  }
202 
203  bool shouldVisitTemplateInstantiations() const { return true; }
204  bool shouldVisitImplicitCode() const { return true; }
205 
206 private:
207  // Used for updating the depth during traversal.
208  struct ScopedIncrement {
209  explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
210  ~ScopedIncrement() { --(*Depth); }
211 
212  private:
213  int *Depth;
214  };
215 
216  // Resets the state of this object.
217  void reset() {
218  Matches = false;
219  CurrentDepth = 0;
220  }
221 
222  // Forwards the call to the corresponding Traverse*() method in the
223  // base visitor class.
224  bool baseTraverse(const Decl &DeclNode) {
225  return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
226  }
227  bool baseTraverse(const Stmt &StmtNode) {
228  return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
229  }
230  bool baseTraverse(QualType TypeNode) {
231  return VisitorBase::TraverseType(TypeNode);
232  }
233  bool baseTraverse(TypeLoc TypeLocNode) {
234  return VisitorBase::TraverseTypeLoc(TypeLocNode);
235  }
236  bool baseTraverse(const NestedNameSpecifier &NNS) {
237  return VisitorBase::TraverseNestedNameSpecifier(
238  const_cast<NestedNameSpecifier*>(&NNS));
239  }
240  bool baseTraverse(NestedNameSpecifierLoc NNS) {
241  return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
242  }
243  bool baseTraverse(const CXXCtorInitializer &CtorInit) {
244  return VisitorBase::TraverseConstructorInitializer(
245  const_cast<CXXCtorInitializer *>(&CtorInit));
246  }
247 
248  // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
249  // 0 < CurrentDepth <= MaxDepth.
250  //
251  // Returns 'true' if traversal should continue after this function
252  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
253  template <typename T>
254  bool match(const T &Node) {
255  if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
256  return true;
257  }
258  if (Bind != ASTMatchFinder::BK_All) {
259  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
260  if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
261  &RecursiveBuilder)) {
262  Matches = true;
263  ResultBindings.addMatch(RecursiveBuilder);
264  return false; // Abort as soon as a match is found.
265  }
266  } else {
267  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
268  if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
269  &RecursiveBuilder)) {
270  // After the first match the matcher succeeds.
271  Matches = true;
272  ResultBindings.addMatch(RecursiveBuilder);
273  }
274  }
275  return true;
276  }
277 
278  // Traverses the subtree rooted at 'Node'; returns true if the
279  // traversal should continue after this function returns.
280  template <typename T>
281  bool traverse(const T &Node) {
282  static_assert(IsBaseType<T>::value,
283  "traverse can only be instantiated with base type");
284  if (!match(Node))
285  return false;
286  return baseTraverse(Node);
287  }
288 
289  const DynTypedMatcher *const Matcher;
290  ASTMatchFinder *const Finder;
291  BoundNodesTreeBuilder *const Builder;
292  BoundNodesTreeBuilder ResultBindings;
293  int CurrentDepth;
294  const int MaxDepth;
295  const ast_type_traits::TraversalKind Traversal;
296  const ASTMatchFinder::BindKind Bind;
297  bool Matches;
298 };
299 
300 // Controls the outermost traversal of the AST and allows to match multiple
301 // matchers.
302 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
303  public ASTMatchFinder {
304 public:
305  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
306  const MatchFinder::MatchFinderOptions &Options)
307  : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
308 
309  ~MatchASTVisitor() override {
310  if (Options.CheckProfiling) {
311  Options.CheckProfiling->Records = std::move(TimeByBucket);
312  }
313  }
314 
315  void onStartOfTranslationUnit() {
316  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
317  TimeBucketRegion Timer;
318  for (MatchCallback *MC : Matchers->AllCallbacks) {
319  if (EnableCheckProfiling)
320  Timer.setBucket(&TimeByBucket[MC->getID()]);
321  MC->onStartOfTranslationUnit();
322  }
323  }
324 
325  void onEndOfTranslationUnit() {
326  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
327  TimeBucketRegion Timer;
328  for (MatchCallback *MC : Matchers->AllCallbacks) {
329  if (EnableCheckProfiling)
330  Timer.setBucket(&TimeByBucket[MC->getID()]);
331  MC->onEndOfTranslationUnit();
332  }
333  }
334 
335  void set_active_ast_context(ASTContext *NewActiveASTContext) {
336  ActiveASTContext = NewActiveASTContext;
337  }
338 
339  // The following Visit*() and Traverse*() functions "override"
340  // methods in RecursiveASTVisitor.
341 
342  bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
343  // When we see 'typedef A B', we add name 'B' to the set of names
344  // A's canonical type maps to. This is necessary for implementing
345  // isDerivedFrom(x) properly, where x can be the name of the base
346  // class or any of its aliases.
347  //
348  // In general, the is-alias-of (as defined by typedefs) relation
349  // is tree-shaped, as you can typedef a type more than once. For
350  // example,
351  //
352  // typedef A B;
353  // typedef A C;
354  // typedef C D;
355  // typedef C E;
356  //
357  // gives you
358  //
359  // A
360  // |- B
361  // `- C
362  // |- D
363  // `- E
364  //
365  // It is wrong to assume that the relation is a chain. A correct
366  // implementation of isDerivedFrom() needs to recognize that B and
367  // E are aliases, even though neither is a typedef of the other.
368  // Therefore, we cannot simply walk through one typedef chain to
369  // find out whether the type name matches.
370  const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
371  const Type *CanonicalType = // root of the typedef tree
372  ActiveASTContext->getCanonicalType(TypeNode);
373  TypeAliases[CanonicalType].insert(DeclNode);
374  return true;
375  }
376 
377  bool TraverseDecl(Decl *DeclNode);
378  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
379  bool TraverseType(QualType TypeNode);
380  bool TraverseTypeLoc(TypeLoc TypeNode);
381  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
382  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
383  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
384 
385  // Matches children or descendants of 'Node' with 'BaseMatcher'.
386  bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
387  const DynTypedMatcher &Matcher,
388  BoundNodesTreeBuilder *Builder, int MaxDepth,
390  BindKind Bind) {
391  // For AST-nodes that don't have an identity, we can't memoize.
392  if (!Node.getMemoizationData() || !Builder->isComparable())
393  return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
394  Bind);
395 
396  MatchKey Key;
397  Key.MatcherID = Matcher.getID();
398  Key.Node = Node;
399  // Note that we key on the bindings *before* the match.
400  Key.BoundNodes = *Builder;
401 
402  MemoizationMap::iterator I = ResultCache.find(Key);
403  if (I != ResultCache.end()) {
404  *Builder = I->second.Nodes;
405  return I->second.ResultOfMatch;
406  }
407 
408  MemoizedMatchResult Result;
409  Result.Nodes = *Builder;
410  Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
411  MaxDepth, Traversal, Bind);
412 
413  MemoizedMatchResult &CachedResult = ResultCache[Key];
414  CachedResult = std::move(Result);
415 
416  *Builder = CachedResult.Nodes;
417  return CachedResult.ResultOfMatch;
418  }
419 
420  // Matches children or descendants of 'Node' with 'BaseMatcher'.
421  bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
422  const DynTypedMatcher &Matcher,
423  BoundNodesTreeBuilder *Builder, int MaxDepth,
425  BindKind Bind) {
426  MatchChildASTVisitor Visitor(
427  &Matcher, this, Builder, MaxDepth, Traversal, Bind);
428  return Visitor.findMatch(Node);
429  }
430 
431  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
432  const Matcher<NamedDecl> &Base,
433  BoundNodesTreeBuilder *Builder) override;
434 
435  // Implements ASTMatchFinder::matchesChildOf.
436  bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
437  const DynTypedMatcher &Matcher,
438  BoundNodesTreeBuilder *Builder,
440  BindKind Bind) override {
441  if (ResultCache.size() > MaxMemoizationEntries)
442  ResultCache.clear();
443  return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
444  Bind);
445  }
446  // Implements ASTMatchFinder::matchesDescendantOf.
447  bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
448  const DynTypedMatcher &Matcher,
449  BoundNodesTreeBuilder *Builder,
450  BindKind Bind) override {
451  if (ResultCache.size() > MaxMemoizationEntries)
452  ResultCache.clear();
453  return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
455  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  /// 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  /// 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  /// 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  // For AST-nodes that don't have an identity, we can't memoize.
634  if (!Builder->isComparable())
635  return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
636 
637  MatchKey Key;
638  Key.MatcherID = Matcher.getID();
639  Key.Node = Node;
640  Key.BoundNodes = *Builder;
641 
642  // Note that we cannot use insert and reuse the iterator, as recursive
643  // calls to match might invalidate the result cache iterators.
644  MemoizationMap::iterator I = ResultCache.find(Key);
645  if (I != ResultCache.end()) {
646  *Builder = I->second.Nodes;
647  return I->second.ResultOfMatch;
648  }
649 
650  MemoizedMatchResult Result;
651  Result.Nodes = *Builder;
652  Result.ResultOfMatch =
653  matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode);
654 
655  MemoizedMatchResult &CachedResult = ResultCache[Key];
656  CachedResult = std::move(Result);
657 
658  *Builder = CachedResult.Nodes;
659  return CachedResult.ResultOfMatch;
660  }
661 
662  bool matchesAncestorOfRecursively(const ast_type_traits::DynTypedNode &Node,
663  const DynTypedMatcher &Matcher,
664  BoundNodesTreeBuilder *Builder,
665  AncestorMatchMode MatchMode) {
666  const auto &Parents = ActiveASTContext->getParents(Node);
667  if (Parents.empty()) {
668  // Nodes may have no parents if:
669  // a) the node is the TranslationUnitDecl
670  // b) we have a limited traversal scope that excludes the parent edges
671  // c) there is a bug in the AST, and the node is not reachable
672  // Usually the traversal scope is the whole AST, which precludes b.
673  // Bugs are common enough that it's worthwhile asserting when we can.
674 #ifndef NDEBUG
675  if (!Node.get<TranslationUnitDecl>() &&
676  /* Traversal scope is full AST if any of the bounds are the TU */
677  llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
678  return D->getKind() == Decl::TranslationUnit;
679  })) {
680  llvm::errs() << "Tried to match orphan node:\n";
681  Node.dump(llvm::errs(), ActiveASTContext->getSourceManager());
682  llvm_unreachable("Parent map should be complete!");
683  }
684 #endif
685  return false;
686  }
687  if (Parents.size() == 1) {
688  // Only one parent - do recursive memoization.
689  const ast_type_traits::DynTypedNode Parent = Parents[0];
690  BoundNodesTreeBuilder BuilderCopy = *Builder;
691  if (Matcher.matches(Parent, this, &BuilderCopy)) {
692  *Builder = std::move(BuilderCopy);
693  return true;
694  }
695  if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
696  return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder,
697  MatchMode);
698  // Once we get back from the recursive call, the result will be the
699  // same as the parent's result.
700  }
701  } else {
702  // Multiple parents - BFS over the rest of the nodes.
704  std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
705  Parents.end());
706  while (!Queue.empty()) {
707  BoundNodesTreeBuilder BuilderCopy = *Builder;
708  if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
709  *Builder = std::move(BuilderCopy);
710  return true;
711  }
712  if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
713  for (const auto &Parent :
714  ActiveASTContext->getParents(Queue.front())) {
715  // Make sure we do not visit the same node twice.
716  // Otherwise, we'll visit the common ancestors as often as there
717  // are splits on the way down.
718  if (Visited.insert(Parent.getMemoizationData()).second)
719  Queue.push_back(Parent);
720  }
721  }
722  Queue.pop_front();
723  }
724  }
725  return false;
726  }
727 
728  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
729  // the aggregated bound nodes for each match.
730  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
731  public:
732  MatchVisitor(ASTContext* Context,
733  MatchFinder::MatchCallback* Callback)
734  : Context(Context),
735  Callback(Callback) {}
736 
737  void visitMatch(const BoundNodes& BoundNodesView) override {
738  Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
739  }
740 
741  private:
742  ASTContext* Context;
743  MatchFinder::MatchCallback* Callback;
744  };
745 
746  // Returns true if 'TypeNode' has an alias that matches the given matcher.
747  bool typeHasMatchingAlias(const Type *TypeNode,
748  const Matcher<NamedDecl> &Matcher,
749  BoundNodesTreeBuilder *Builder) {
750  const Type *const CanonicalType =
751  ActiveASTContext->getCanonicalType(TypeNode);
752  auto Aliases = TypeAliases.find(CanonicalType);
753  if (Aliases == TypeAliases.end())
754  return false;
755  for (const TypedefNameDecl *Alias : Aliases->second) {
756  BoundNodesTreeBuilder Result(*Builder);
757  if (Matcher.matches(*Alias, this, &Result)) {
758  *Builder = std::move(Result);
759  return true;
760  }
761  }
762  return false;
763  }
764 
765  /// Bucket to record map.
766  ///
767  /// Used to get the appropriate bucket for each matcher.
768  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
769 
770  const MatchFinder::MatchersByType *Matchers;
771 
772  /// Filtered list of matcher indices for each matcher kind.
773  ///
774  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
775  /// kind (and derived kinds) so it is a waste to try every matcher on every
776  /// node.
777  /// We precalculate a list of matchers that pass the toplevel restrict check.
778  /// This also allows us to skip the restrict check at matching time. See
779  /// use \c matchesNoKindCheck() above.
780  llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
781  MatcherFiltersMap;
782 
783  const MatchFinder::MatchFinderOptions &Options;
784  ASTContext *ActiveASTContext;
785 
786  // Maps a canonical type to its TypedefDecls.
787  llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
788 
789  // Maps (matcher, node) -> the match result for memoization.
790  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
791  MemoizationMap ResultCache;
792 };
793 
794 static CXXRecordDecl *
795 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
796  if (auto *RD = TypeNode->getAsCXXRecordDecl())
797  return RD;
798 
799  // Find the innermost TemplateSpecializationType that isn't an alias template.
800  auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
801  while (TemplateType && TemplateType->isTypeAlias())
802  TemplateType =
803  TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
804 
805  // If this is the name of a (dependent) template specialization, use the
806  // definition of the template, even though it might be specialized later.
807  if (TemplateType)
808  if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
809  TemplateType->getTemplateName().getAsTemplateDecl()))
810  return ClassTemplate->getTemplatedDecl();
811 
812  return nullptr;
813 }
814 
815 // Returns true if the given class is directly or indirectly derived
816 // from a base type with the given name. A class is not considered to be
817 // derived from itself.
818 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
819  const Matcher<NamedDecl> &Base,
820  BoundNodesTreeBuilder *Builder) {
821  if (!Declaration->hasDefinition())
822  return false;
823  for (const auto &It : Declaration->bases()) {
824  const Type *TypeNode = It.getType().getTypePtr();
825 
826  if (typeHasMatchingAlias(TypeNode, Base, Builder))
827  return true;
828 
829  // FIXME: Going to the primary template here isn't really correct, but
830  // unfortunately we accept a Decl matcher for the base class not a Type
831  // matcher, so it's the best thing we can do with our current interface.
832  CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
833  if (!ClassDecl)
834  continue;
835  if (ClassDecl == Declaration) {
836  // This can happen for recursive template definitions; if the
837  // current declaration did not match, we can safely return false.
838  return false;
839  }
840  BoundNodesTreeBuilder Result(*Builder);
841  if (Base.matches(*ClassDecl, this, &Result)) {
842  *Builder = std::move(Result);
843  return true;
844  }
845  if (classIsDerivedFrom(ClassDecl, Base, Builder))
846  return true;
847  }
848  return false;
849 }
850 
851 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
852  if (!DeclNode) {
853  return true;
854  }
855  match(*DeclNode);
857 }
858 
859 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
860  if (!StmtNode) {
861  return true;
862  }
863  match(*StmtNode);
865 }
866 
867 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
868  match(TypeNode);
870 }
871 
872 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
873  // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
874  // We still want to find those types via matchers, so we match them here. Note
875  // that the TypeLocs are structurally a shadow-hierarchy to the expressed
876  // type, so we visit all involved parts of a compound type when matching on
877  // each TypeLoc.
878  match(TypeLocNode);
879  match(TypeLocNode.getType());
881 }
882 
883 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
884  match(*NNS);
886 }
887 
888 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
889  NestedNameSpecifierLoc NNS) {
890  if (!NNS)
891  return true;
892 
893  match(NNS);
894 
895  // We only match the nested name specifier here (as opposed to traversing it)
896  // because the traversal is already done in the parallel "Loc"-hierarchy.
897  if (NNS.hasQualifier())
898  match(*NNS.getNestedNameSpecifier());
899  return
901 }
902 
903 bool MatchASTVisitor::TraverseConstructorInitializer(
904  CXXCtorInitializer *CtorInit) {
905  if (!CtorInit)
906  return true;
907 
908  match(*CtorInit);
909 
911  CtorInit);
912 }
913 
914 class MatchASTConsumer : public ASTConsumer {
915 public:
916  MatchASTConsumer(MatchFinder *Finder,
917  MatchFinder::ParsingDoneTestCallback *ParsingDone)
918  : Finder(Finder), ParsingDone(ParsingDone) {}
919 
920 private:
921  void HandleTranslationUnit(ASTContext &Context) override {
922  if (ParsingDone != nullptr) {
923  ParsingDone->run();
924  }
925  Finder->matchAST(Context);
926  }
927 
928  MatchFinder *Finder;
929  MatchFinder::ParsingDoneTestCallback *ParsingDone;
930 };
931 
932 } // end namespace
933 } // end namespace internal
934 
936  ASTContext *Context)
937  : Nodes(Nodes), Context(Context),
938  SourceManager(&Context->getSourceManager()) {}
939 
942 
944  : Options(std::move(Options)), ParsingDone(nullptr) {}
945 
947 
949  MatchCallback *Action) {
950  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
951  Matchers.AllCallbacks.insert(Action);
952 }
953 
954 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
955  MatchCallback *Action) {
956  Matchers.Type.emplace_back(NodeMatch, Action);
957  Matchers.AllCallbacks.insert(Action);
958 }
959 
961  MatchCallback *Action) {
962  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
963  Matchers.AllCallbacks.insert(Action);
964 }
965 
967  MatchCallback *Action) {
968  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
969  Matchers.AllCallbacks.insert(Action);
970 }
971 
973  MatchCallback *Action) {
974  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
975  Matchers.AllCallbacks.insert(Action);
976 }
977 
979  MatchCallback *Action) {
980  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
981  Matchers.AllCallbacks.insert(Action);
982 }
983 
985  MatchCallback *Action) {
986  Matchers.CtorInit.emplace_back(NodeMatch, Action);
987  Matchers.AllCallbacks.insert(Action);
988 }
989 
990 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
991  MatchCallback *Action) {
992  if (NodeMatch.canConvertTo<Decl>()) {
993  addMatcher(NodeMatch.convertTo<Decl>(), Action);
994  return true;
995  } else if (NodeMatch.canConvertTo<QualType>()) {
996  addMatcher(NodeMatch.convertTo<QualType>(), Action);
997  return true;
998  } else if (NodeMatch.canConvertTo<Stmt>()) {
999  addMatcher(NodeMatch.convertTo<Stmt>(), Action);
1000  return true;
1001  } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1002  addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1003  return true;
1004  } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1005  addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1006  return true;
1007  } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1008  addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
1009  return true;
1010  } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1011  addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1012  return true;
1013  }
1014  return false;
1015 }
1016 
1017 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1018  return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1019 }
1020 
1022  ASTContext &Context) {
1023  internal::MatchASTVisitor Visitor(&Matchers, Options);
1024  Visitor.set_active_ast_context(&Context);
1025  Visitor.match(Node);
1026 }
1027 
1029  internal::MatchASTVisitor Visitor(&Matchers, Options);
1030  Visitor.set_active_ast_context(&Context);
1031  Visitor.onStartOfTranslationUnit();
1032  Visitor.TraverseAST(Context);
1033  Visitor.onEndOfTranslationUnit();
1034 }
1035 
1037  MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1038  ParsingDone = NewParsingDone;
1039 }
1040 
1041 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1042 
1043 } // end namespace ast_matchers
1044 } // end namespace clang
Defines the clang::ASTContext interface.
A (possibly-)qualified type.
Definition: Type.h:643
internal::Matcher< NestedNameSpecifier > NestedNameSpecifierMatcher
Definition: ASTMatchers.h:150
Stmt - This represents one statement.
Definition: Stmt.h:66
internal::Matcher< Stmt > StatementMatcher
Definition: ASTMatchers.h:147
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
MatchFinder::MatchResult MatchResult
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:148
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:154
A C++ nested-name-specifier augmented with source location information.
Will traverse all child nodes.
Definition: ASTTypeTraits.h:45
Definition: Format.h:2274
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:191
bool TraverseConstructorInitializer(CXXCtorInitializer *Init)
Recursively visit a constructor initializer.
Will not traverse implicit casts and parentheses.
Definition: ASTTypeTraits.h:49
int Depth
Definition: ASTDiff.cpp:190
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:55
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:103
bool ResultOfMatch
llvm::cl::opt< std::string > Filter
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
Optional< types::ID > Type
Dataflow Directional Tag Classes.
internal::Matcher< CXXCtorInitializer > CXXCtorInitializerMatcher
Definition: ASTMatchers.h:152
A dynamically typed AST node container.
std::vector< std::pair< TypeLocMatcher, MatchCallback * > > TypeLoc
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2338
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:43
bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS)
Recursively visit a C++ nested-name-specifier.
#define INT_MAX
Definition: limits.h:46
internal::Matcher< NestedNameSpecifierLoc > NestedNameSpecifierLocMatcher
Definition: ASTMatchers.h:151
internal::Matcher< TypeLoc > TypeLocMatcher
Definition: ASTMatchers.h:149
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:146
bool addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.