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