clang  12.0.0git
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 enum class MatchType {
47  Ancestors,
48 
49  Descendants,
50  Child,
51 };
52 
53 // We use memoization to avoid running the same matcher on the same
54 // AST node twice. This struct is the key for looking up match
55 // result. It consists of an ID of the MatcherInterface (for
56 // identifying the matcher), a pointer to the AST node and the
57 // bound nodes before the matcher was executed.
58 //
59 // We currently only memoize on nodes whose pointers identify the
60 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
61 // For \c QualType and \c TypeLoc it is possible to implement
62 // generation of keys for each type.
63 // FIXME: Benchmark whether memoization of non-pointer typed nodes
64 // provides enough benefit for the additional amount of code.
65 struct MatchKey {
66  DynTypedMatcher::MatcherIDType MatcherID;
68  BoundNodesTreeBuilder BoundNodes;
70  MatchType Type;
71 
72  bool operator<(const MatchKey &Other) const {
73  return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
74  std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
75  Other.BoundNodes);
76  }
77 };
78 
79 // Used to store the result of a match and possibly bound nodes.
80 struct MemoizedMatchResult {
82  BoundNodesTreeBuilder Nodes;
83 };
84 
85 // A RecursiveASTVisitor that traverses all children or all descendants of
86 // a node.
87 class MatchChildASTVisitor
88  : public RecursiveASTVisitor<MatchChildASTVisitor> {
89 public:
90  typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
91 
92  // Creates an AST visitor that matches 'matcher' on all children or
93  // descendants of a traversed node. max_depth is the maximum depth
94  // to traverse: use 1 for matching the children and INT_MAX for
95  // matching the descendants.
96  MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
97  BoundNodesTreeBuilder *Builder, int MaxDepth,
98  bool IgnoreImplicitChildren,
99  ASTMatchFinder::BindKind Bind)
100  : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
101  MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
102  Bind(Bind), Matches(false) {}
103 
104  // Returns true if a match is found in the subtree rooted at the
105  // given AST node. This is done via a set of mutually recursive
106  // functions. Here's how the recursion is done (the *wildcard can
107  // actually be Decl, Stmt, or Type):
108  //
109  // - Traverse(node) calls BaseTraverse(node) when it needs
110  // to visit the descendants of node.
111  // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
112  // Traverse*(c) for each child c of 'node'.
113  // - Traverse*(c) in turn calls Traverse(c), completing the
114  // recursion.
115  bool findMatch(const DynTypedNode &DynNode) {
116  reset();
117  if (const Decl *D = DynNode.get<Decl>())
118  traverse(*D);
119  else if (const Stmt *S = DynNode.get<Stmt>())
120  traverse(*S);
121  else if (const NestedNameSpecifier *NNS =
122  DynNode.get<NestedNameSpecifier>())
123  traverse(*NNS);
124  else if (const NestedNameSpecifierLoc *NNSLoc =
125  DynNode.get<NestedNameSpecifierLoc>())
126  traverse(*NNSLoc);
127  else if (const QualType *Q = DynNode.get<QualType>())
128  traverse(*Q);
129  else if (const TypeLoc *T = DynNode.get<TypeLoc>())
130  traverse(*T);
131  else if (const auto *C = DynNode.get<CXXCtorInitializer>())
132  traverse(*C);
133  else if (const TemplateArgumentLoc *TALoc =
134  DynNode.get<TemplateArgumentLoc>())
135  traverse(*TALoc);
136  // FIXME: Add other base types after adding tests.
137 
138  // It's OK to always overwrite the bound nodes, as if there was
139  // no match in this recursive branch, the result set is empty
140  // anyway.
141  *Builder = ResultBindings;
142 
143  return Matches;
144  }
145 
146  // The following are overriding methods from the base visitor class.
147  // They are public only to allow CRTP to work. They are *not *part
148  // of the public API of this class.
149  bool TraverseDecl(Decl *DeclNode) {
150 
151  if (DeclNode && DeclNode->isImplicit() &&
152  Finder->isTraversalIgnoringImplicitNodes())
153  return baseTraverse(*DeclNode);
154 
155  ScopedIncrement ScopedDepth(&CurrentDepth);
156  return (DeclNode == nullptr) || traverse(*DeclNode);
157  }
158 
159  Stmt *getStmtToTraverse(Stmt *StmtNode) {
160  Stmt *StmtToTraverse = StmtNode;
161  if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
162  auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
163  if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
164  StmtToTraverse = LambdaNode;
165  else
166  StmtToTraverse =
167  Finder->getASTContext().getParentMapContext().traverseIgnored(
168  ExprNode);
169  }
170  return StmtToTraverse;
171  }
172 
173  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
174  // If we need to keep track of the depth, we can't perform data recursion.
175  if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
176  Queue = nullptr;
177 
178  ScopedIncrement ScopedDepth(&CurrentDepth);
179  Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
180  if (!StmtToTraverse)
181  return true;
182 
183  if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
184  return true;
185 
186  if (!match(*StmtToTraverse))
187  return false;
188  return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
189  }
190  // We assume that the QualType and the contained type are on the same
191  // hierarchy level. Thus, we try to match either of them.
192  bool TraverseType(QualType TypeNode) {
193  if (TypeNode.isNull())
194  return true;
195  ScopedIncrement ScopedDepth(&CurrentDepth);
196  // Match the Type.
197  if (!match(*TypeNode))
198  return false;
199  // The QualType is matched inside traverse.
200  return traverse(TypeNode);
201  }
202  // We assume that the TypeLoc, contained QualType and contained Type all are
203  // on the same hierarchy level. Thus, we try to match all of them.
204  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
205  if (TypeLocNode.isNull())
206  return true;
207  ScopedIncrement ScopedDepth(&CurrentDepth);
208  // Match the Type.
209  if (!match(*TypeLocNode.getType()))
210  return false;
211  // Match the QualType.
212  if (!match(TypeLocNode.getType()))
213  return false;
214  // The TypeLoc is matched inside traverse.
215  return traverse(TypeLocNode);
216  }
217  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
218  ScopedIncrement ScopedDepth(&CurrentDepth);
219  return (NNS == nullptr) || traverse(*NNS);
220  }
221  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
222  if (!NNS)
223  return true;
224  ScopedIncrement ScopedDepth(&CurrentDepth);
225  if (!match(*NNS.getNestedNameSpecifier()))
226  return false;
227  return traverse(NNS);
228  }
229  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
230  if (!CtorInit)
231  return true;
232  ScopedIncrement ScopedDepth(&CurrentDepth);
233  return traverse(*CtorInit);
234  }
235  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
236  ScopedIncrement ScopedDepth(&CurrentDepth);
237  return traverse(TAL);
238  }
239  bool TraverseLambdaExpr(LambdaExpr *Node) {
240  if (!Finder->isTraversalIgnoringImplicitNodes())
241  return VisitorBase::TraverseLambdaExpr(Node);
242  if (!Node)
243  return true;
244  ScopedIncrement ScopedDepth(&CurrentDepth);
245 
246  for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
247  const auto *C = Node->capture_begin() + I;
248  if (!C->isExplicit())
249  continue;
250  if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))
251  return false;
252  if (!match(*Node->capture_init_begin()[I]))
253  return false;
254  }
255 
256  if (const auto *TPL = Node->getTemplateParameterList()) {
257  for (const auto *TP : *TPL) {
258  if (!match(*TP))
259  return false;
260  }
261  }
262 
263  for (const auto *P : Node->getCallOperator()->parameters()) {
264  if (!match(*P))
265  return false;
266  }
267 
268  if (!match(*Node->getBody()))
269  return false;
270 
271  return true;
272  }
273 
274  bool shouldVisitTemplateInstantiations() const { return true; }
275  bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
276 
277 private:
278  // Used for updating the depth during traversal.
279  struct ScopedIncrement {
280  explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
281  ~ScopedIncrement() { --(*Depth); }
282 
283  private:
284  int *Depth;
285  };
286 
287  // Resets the state of this object.
288  void reset() {
289  Matches = false;
290  CurrentDepth = 0;
291  }
292 
293  // Forwards the call to the corresponding Traverse*() method in the
294  // base visitor class.
295  bool baseTraverse(const Decl &DeclNode) {
296  return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
297  }
298  bool baseTraverse(const Stmt &StmtNode) {
299  return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
300  }
301  bool baseTraverse(QualType TypeNode) {
302  return VisitorBase::TraverseType(TypeNode);
303  }
304  bool baseTraverse(TypeLoc TypeLocNode) {
305  return VisitorBase::TraverseTypeLoc(TypeLocNode);
306  }
307  bool baseTraverse(const NestedNameSpecifier &NNS) {
309  const_cast<NestedNameSpecifier*>(&NNS));
310  }
311  bool baseTraverse(NestedNameSpecifierLoc NNS) {
313  }
314  bool baseTraverse(const CXXCtorInitializer &CtorInit) {
316  const_cast<CXXCtorInitializer *>(&CtorInit));
317  }
318  bool baseTraverse(TemplateArgumentLoc TAL) {
320  }
321 
322  // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
323  // 0 < CurrentDepth <= MaxDepth.
324  //
325  // Returns 'true' if traversal should continue after this function
326  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
327  template <typename T>
328  bool match(const T &Node) {
329  if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
330  return true;
331  }
332  if (Bind != ASTMatchFinder::BK_All) {
333  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
334  if (Matcher->matches(DynTypedNode::create(Node), Finder,
335  &RecursiveBuilder)) {
336  Matches = true;
337  ResultBindings.addMatch(RecursiveBuilder);
338  return false; // Abort as soon as a match is found.
339  }
340  } else {
341  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
342  if (Matcher->matches(DynTypedNode::create(Node), Finder,
343  &RecursiveBuilder)) {
344  // After the first match the matcher succeeds.
345  Matches = true;
346  ResultBindings.addMatch(RecursiveBuilder);
347  }
348  }
349  return true;
350  }
351 
352  // Traverses the subtree rooted at 'Node'; returns true if the
353  // traversal should continue after this function returns.
354  template <typename T>
355  bool traverse(const T &Node) {
356  static_assert(IsBaseType<T>::value,
357  "traverse can only be instantiated with base type");
358  if (!match(Node))
359  return false;
360  return baseTraverse(Node);
361  }
362 
363  const DynTypedMatcher *const Matcher;
364  ASTMatchFinder *const Finder;
365  BoundNodesTreeBuilder *const Builder;
366  BoundNodesTreeBuilder ResultBindings;
367  int CurrentDepth;
368  const int MaxDepth;
369  const bool IgnoreImplicitChildren;
370  const ASTMatchFinder::BindKind Bind;
371  bool Matches;
372 };
373 
374 // Controls the outermost traversal of the AST and allows to match multiple
375 // matchers.
376 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
377  public ASTMatchFinder {
378 public:
379  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
380  const MatchFinder::MatchFinderOptions &Options)
381  : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
382 
383  ~MatchASTVisitor() override {
384  if (Options.CheckProfiling) {
385  Options.CheckProfiling->Records = std::move(TimeByBucket);
386  }
387  }
388 
389  void onStartOfTranslationUnit() {
390  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
391  TimeBucketRegion Timer;
392  for (MatchCallback *MC : Matchers->AllCallbacks) {
393  if (EnableCheckProfiling)
394  Timer.setBucket(&TimeByBucket[MC->getID()]);
395  MC->onStartOfTranslationUnit();
396  }
397  }
398 
399  void onEndOfTranslationUnit() {
400  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
401  TimeBucketRegion Timer;
402  for (MatchCallback *MC : Matchers->AllCallbacks) {
403  if (EnableCheckProfiling)
404  Timer.setBucket(&TimeByBucket[MC->getID()]);
405  MC->onEndOfTranslationUnit();
406  }
407  }
408 
409  void set_active_ast_context(ASTContext *NewActiveASTContext) {
410  ActiveASTContext = NewActiveASTContext;
411  }
412 
413  // The following Visit*() and Traverse*() functions "override"
414  // methods in RecursiveASTVisitor.
415 
416  bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
417  // When we see 'typedef A B', we add name 'B' to the set of names
418  // A's canonical type maps to. This is necessary for implementing
419  // isDerivedFrom(x) properly, where x can be the name of the base
420  // class or any of its aliases.
421  //
422  // In general, the is-alias-of (as defined by typedefs) relation
423  // is tree-shaped, as you can typedef a type more than once. For
424  // example,
425  //
426  // typedef A B;
427  // typedef A C;
428  // typedef C D;
429  // typedef C E;
430  //
431  // gives you
432  //
433  // A
434  // |- B
435  // `- C
436  // |- D
437  // `- E
438  //
439  // It is wrong to assume that the relation is a chain. A correct
440  // implementation of isDerivedFrom() needs to recognize that B and
441  // E are aliases, even though neither is a typedef of the other.
442  // Therefore, we cannot simply walk through one typedef chain to
443  // find out whether the type name matches.
444  const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
445  const Type *CanonicalType = // root of the typedef tree
446  ActiveASTContext->getCanonicalType(TypeNode);
447  TypeAliases[CanonicalType].insert(DeclNode);
448  return true;
449  }
450 
451  bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
452  const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
453  CompatibleAliases[InterfaceDecl].insert(CAD);
454  return true;
455  }
456 
457  bool TraverseDecl(Decl *DeclNode);
458  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
459  bool TraverseType(QualType TypeNode);
460  bool TraverseTypeLoc(TypeLoc TypeNode);
461  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
462  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
463  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
464  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
465 
466  // Matches children or descendants of 'Node' with 'BaseMatcher'.
467  bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
468  const DynTypedMatcher &Matcher,
469  BoundNodesTreeBuilder *Builder, int MaxDepth,
470  BindKind Bind) {
471  // For AST-nodes that don't have an identity, we can't memoize.
472  if (!Node.getMemoizationData() || !Builder->isComparable())
473  return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
474 
475  MatchKey Key;
476  Key.MatcherID = Matcher.getID();
477  Key.Node = Node;
478  // Note that we key on the bindings *before* the match.
479  Key.BoundNodes = *Builder;
480  Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
481  // Memoize result even doing a single-level match, it might be expensive.
482  Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
483  MemoizationMap::iterator I = ResultCache.find(Key);
484  if (I != ResultCache.end()) {
485  *Builder = I->second.Nodes;
486  return I->second.ResultOfMatch;
487  }
488 
489  MemoizedMatchResult Result;
490  Result.Nodes = *Builder;
491  Result.ResultOfMatch =
492  matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);
493 
494  MemoizedMatchResult &CachedResult = ResultCache[Key];
495  CachedResult = std::move(Result);
496 
497  *Builder = CachedResult.Nodes;
498  return CachedResult.ResultOfMatch;
499  }
500 
501  // Matches children or descendants of 'Node' with 'BaseMatcher'.
502  bool matchesRecursively(const DynTypedNode &Node,
503  const DynTypedMatcher &Matcher,
504  BoundNodesTreeBuilder *Builder, int MaxDepth,
505  BindKind Bind) {
506  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
507  TraversingASTChildrenNotSpelledInSource;
508 
509  bool IgnoreImplicitChildren = false;
510 
511  if (isTraversalIgnoringImplicitNodes()) {
512  IgnoreImplicitChildren = true;
513  if (Node.get<CXXForRangeStmt>())
514  ScopedTraversal = true;
515  }
516 
517  ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
518 
519  MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
520  IgnoreImplicitChildren, Bind);
521  return Visitor.findMatch(Node);
522  }
523 
524  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
525  const Matcher<NamedDecl> &Base,
526  BoundNodesTreeBuilder *Builder,
527  bool Directly) override;
528 
529  bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
530  const Matcher<NamedDecl> &Base,
531  BoundNodesTreeBuilder *Builder,
532  bool Directly) override;
533 
534  // Implements ASTMatchFinder::matchesChildOf.
535  bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
536  const DynTypedMatcher &Matcher,
537  BoundNodesTreeBuilder *Builder, BindKind Bind) override {
538  if (ResultCache.size() > MaxMemoizationEntries)
539  ResultCache.clear();
540  return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);
541  }
542  // Implements ASTMatchFinder::matchesDescendantOf.
543  bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
544  const DynTypedMatcher &Matcher,
545  BoundNodesTreeBuilder *Builder,
546  BindKind Bind) override {
547  if (ResultCache.size() > MaxMemoizationEntries)
548  ResultCache.clear();
549  return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
550  Bind);
551  }
552  // Implements ASTMatchFinder::matchesAncestorOf.
553  bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
554  const DynTypedMatcher &Matcher,
555  BoundNodesTreeBuilder *Builder,
556  AncestorMatchMode MatchMode) override {
557  // Reset the cache outside of the recursive call to make sure we
558  // don't invalidate any iterators.
559  if (ResultCache.size() > MaxMemoizationEntries)
560  ResultCache.clear();
561  if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
562  return matchesParentOf(Node, Matcher, Builder);
563  return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
564  }
565 
566  // Matches all registered matchers on the given node and calls the
567  // result callback for every node that matches.
568  void match(const DynTypedNode &Node) {
569  // FIXME: Improve this with a switch or a visitor pattern.
570  if (auto *N = Node.get<Decl>()) {
571  match(*N);
572  } else if (auto *N = Node.get<Stmt>()) {
573  match(*N);
574  } else if (auto *N = Node.get<Type>()) {
575  match(*N);
576  } else if (auto *N = Node.get<QualType>()) {
577  match(*N);
578  } else if (auto *N = Node.get<NestedNameSpecifier>()) {
579  match(*N);
580  } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
581  match(*N);
582  } else if (auto *N = Node.get<TypeLoc>()) {
583  match(*N);
584  } else if (auto *N = Node.get<CXXCtorInitializer>()) {
585  match(*N);
586  } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
587  match(*N);
588  }
589  }
590 
591  template <typename T> void match(const T &Node) {
592  matchDispatch(&Node);
593  }
594 
595  // Implements ASTMatchFinder::getASTContext.
596  ASTContext &getASTContext() const override { return *ActiveASTContext; }
597 
598  bool shouldVisitTemplateInstantiations() const { return true; }
599  bool shouldVisitImplicitCode() const { return true; }
600 
601  bool IsMatchingInASTNodeNotSpelledInSource() const override {
602  return TraversingASTNodeNotSpelledInSource;
603  }
604 
605  bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
606  ASTNodeNotSpelledInSourceScope RAII(this, true);
607  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
608  D);
609  }
610 
611  bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
612  ASTNodeNotSpelledInSourceScope RAII(this, true);
613  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
614  D);
615  }
616 
617  bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
618  ASTNodeNotSpelledInSourceScope RAII(this, true);
619  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
620  D);
621  }
622 
623 private:
624  bool TraversingASTNodeNotSpelledInSource = false;
625  bool TraversingASTChildrenNotSpelledInSource = false;
626 
627  struct ASTNodeNotSpelledInSourceScope {
628  ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
629  : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
630  V->TraversingASTNodeNotSpelledInSource = B;
631  }
632  ~ASTNodeNotSpelledInSourceScope() {
633  MV->TraversingASTNodeNotSpelledInSource = MB;
634  }
635 
636  private:
637  MatchASTVisitor *MV;
638  bool MB;
639  };
640 
641  struct ASTChildrenNotSpelledInSource {
642  ASTChildrenNotSpelledInSource(MatchASTVisitor *V, bool B)
643  : MV(V), MB(V->TraversingASTChildrenNotSpelledInSource) {
644  V->TraversingASTChildrenNotSpelledInSource = B;
645  }
646  ~ASTChildrenNotSpelledInSource() {
647  MV->TraversingASTChildrenNotSpelledInSource = MB;
648  }
649 
650  private:
651  MatchASTVisitor *MV;
652  bool MB;
653  };
654 
655  class TimeBucketRegion {
656  public:
657  TimeBucketRegion() : Bucket(nullptr) {}
658  ~TimeBucketRegion() { setBucket(nullptr); }
659 
660  /// Start timing for \p NewBucket.
661  ///
662  /// If there was a bucket already set, it will finish the timing for that
663  /// other bucket.
664  /// \p NewBucket will be timed until the next call to \c setBucket() or
665  /// until the \c TimeBucketRegion is destroyed.
666  /// If \p NewBucket is the same as the currently timed bucket, this call
667  /// does nothing.
668  void setBucket(llvm::TimeRecord *NewBucket) {
669  if (Bucket != NewBucket) {
670  auto Now = llvm::TimeRecord::getCurrentTime(true);
671  if (Bucket)
672  *Bucket += Now;
673  if (NewBucket)
674  *NewBucket -= Now;
675  Bucket = NewBucket;
676  }
677  }
678 
679  private:
680  llvm::TimeRecord *Bucket;
681  };
682 
683  /// Runs all the \p Matchers on \p Node.
684  ///
685  /// Used by \c matchDispatch() below.
686  template <typename T, typename MC>
687  void matchWithoutFilter(const T &Node, const MC &Matchers) {
688  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
689  TimeBucketRegion Timer;
690  for (const auto &MP : Matchers) {
691  if (EnableCheckProfiling)
692  Timer.setBucket(&TimeByBucket[MP.second->getID()]);
693  BoundNodesTreeBuilder Builder;
694  if (MP.first.matches(Node, this, &Builder)) {
695  MatchVisitor Visitor(ActiveASTContext, MP.second);
696  Builder.visitMatches(&Visitor);
697  }
698  }
699  }
700 
701  void matchWithFilter(const DynTypedNode &DynNode) {
702  auto Kind = DynNode.getNodeKind();
703  auto it = MatcherFiltersMap.find(Kind);
704  const auto &Filter =
705  it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
706 
707  if (Filter.empty())
708  return;
709 
710  const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
711  TimeBucketRegion Timer;
712  auto &Matchers = this->Matchers->DeclOrStmt;
713  for (unsigned short I : Filter) {
714  auto &MP = Matchers[I];
715  if (EnableCheckProfiling)
716  Timer.setBucket(&TimeByBucket[MP.second->getID()]);
717  BoundNodesTreeBuilder Builder;
718  if (MP.first.matches(DynNode, this, &Builder)) {
719  MatchVisitor Visitor(ActiveASTContext, MP.second);
720  Builder.visitMatches(&Visitor);
721  }
722  }
723  }
724 
725  const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
726  auto &Filter = MatcherFiltersMap[Kind];
727  auto &Matchers = this->Matchers->DeclOrStmt;
728  assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
729  for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
730  if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
731  Filter.push_back(I);
732  }
733  }
734  return Filter;
735  }
736 
737  /// @{
738  /// Overloads to pair the different node types to their matchers.
739  void matchDispatch(const Decl *Node) {
740  return matchWithFilter(DynTypedNode::create(*Node));
741  }
742  void matchDispatch(const Stmt *Node) {
743  return matchWithFilter(DynTypedNode::create(*Node));
744  }
745 
746  void matchDispatch(const Type *Node) {
747  matchWithoutFilter(QualType(Node, 0), Matchers->Type);
748  }
749  void matchDispatch(const TypeLoc *Node) {
750  matchWithoutFilter(*Node, Matchers->TypeLoc);
751  }
752  void matchDispatch(const QualType *Node) {
753  matchWithoutFilter(*Node, Matchers->Type);
754  }
755  void matchDispatch(const NestedNameSpecifier *Node) {
756  matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
757  }
758  void matchDispatch(const NestedNameSpecifierLoc *Node) {
759  matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
760  }
761  void matchDispatch(const CXXCtorInitializer *Node) {
762  matchWithoutFilter(*Node, Matchers->CtorInit);
763  }
764  void matchDispatch(const TemplateArgumentLoc *Node) {
765  matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);
766  }
767  void matchDispatch(const void *) { /* Do nothing. */ }
768  /// @}
769 
770  // Returns whether a direct parent of \p Node matches \p Matcher.
771  // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
772  bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
773  BoundNodesTreeBuilder *Builder) {
774  for (const auto &Parent : ActiveASTContext->getParents(Node)) {
775  BoundNodesTreeBuilder BuilderCopy = *Builder;
776  if (Matcher.matches(Parent, this, &BuilderCopy)) {
777  *Builder = std::move(BuilderCopy);
778  return true;
779  }
780  }
781  return false;
782  }
783 
784  // Returns whether an ancestor of \p Node matches \p Matcher.
785  //
786  // The order of matching (which can lead to different nodes being bound in
787  // case there are multiple matches) is breadth first search.
788  //
789  // To allow memoization in the very common case of having deeply nested
790  // expressions inside a template function, we first walk up the AST, memoizing
791  // the result of the match along the way, as long as there is only a single
792  // parent.
793  //
794  // Once there are multiple parents, the breadth first search order does not
795  // allow simple memoization on the ancestors. Thus, we only memoize as long
796  // as there is a single parent.
797  //
798  // We avoid a recursive implementation to prevent excessive stack use on
799  // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
800  bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
801  const DynTypedMatcher &Matcher,
802  BoundNodesTreeBuilder *Builder) {
803 
804  // Memoization keys that can be updated with the result.
805  // These are the memoizable nodes in the chain of unique parents, which
806  // terminates when a node has multiple parents, or matches, or is the root.
807  std::vector<MatchKey> Keys;
808  // When returning, update the memoization cache.
809  auto Finish = [&](bool Matched) {
810  for (const auto &Key : Keys) {
811  MemoizedMatchResult &CachedResult = ResultCache[Key];
812  CachedResult.ResultOfMatch = Matched;
813  CachedResult.Nodes = *Builder;
814  }
815  return Matched;
816  };
817 
818  // Loop while there's a single parent and we want to attempt memoization.
819  DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
820  for (;;) {
821  // A cache key only makes sense if memoization is possible.
822  if (Builder->isComparable()) {
823  Keys.emplace_back();
824  Keys.back().MatcherID = Matcher.getID();
825  Keys.back().Node = Node;
826  Keys.back().BoundNodes = *Builder;
827  Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
828  Keys.back().Type = MatchType::Ancestors;
829 
830  // Check the cache.
831  MemoizationMap::iterator I = ResultCache.find(Keys.back());
832  if (I != ResultCache.end()) {
833  Keys.pop_back(); // Don't populate the cache for the matching node!
834  *Builder = I->second.Nodes;
835  return Finish(I->second.ResultOfMatch);
836  }
837  }
838 
839  Parents = ActiveASTContext->getParents(Node);
840  // Either no parents or multiple parents: leave chain+memoize mode and
841  // enter bfs+forgetful mode.
842  if (Parents.size() != 1)
843  break;
844 
845  // Check the next parent.
846  Node = *Parents.begin();
847  BoundNodesTreeBuilder BuilderCopy = *Builder;
848  if (Matcher.matches(Node, this, &BuilderCopy)) {
849  *Builder = std::move(BuilderCopy);
850  return Finish(true);
851  }
852  }
853  // We reached the end of the chain.
854 
855  if (Parents.empty()) {
856  // Nodes may have no parents if:
857  // a) the node is the TranslationUnitDecl
858  // b) we have a limited traversal scope that excludes the parent edges
859  // c) there is a bug in the AST, and the node is not reachable
860  // Usually the traversal scope is the whole AST, which precludes b.
861  // Bugs are common enough that it's worthwhile asserting when we can.
862 #ifndef NDEBUG
863  if (!Node.get<TranslationUnitDecl>() &&
864  /* Traversal scope is full AST if any of the bounds are the TU */
865  llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
866  return D->getKind() == Decl::TranslationUnit;
867  })) {
868  llvm::errs() << "Tried to match orphan node:\n";
869  Node.dump(llvm::errs(), *ActiveASTContext);
870  llvm_unreachable("Parent map should be complete!");
871  }
872 #endif
873  } else {
874  assert(Parents.size() > 1);
875  // BFS starting from the parents not yet considered.
876  // Memoization of newly visited nodes is not possible (but we still update
877  // results for the elements in the chain we found above).
878  std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
880  while (!Queue.empty()) {
881  BoundNodesTreeBuilder BuilderCopy = *Builder;
882  if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
883  *Builder = std::move(BuilderCopy);
884  return Finish(true);
885  }
886  for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {
887  // Make sure we do not visit the same node twice.
888  // Otherwise, we'll visit the common ancestors as often as there
889  // are splits on the way down.
890  if (Visited.insert(Parent.getMemoizationData()).second)
891  Queue.push_back(Parent);
892  }
893  Queue.pop_front();
894  }
895  }
896  return Finish(false);
897  }
898 
899  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
900  // the aggregated bound nodes for each match.
901  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
902  public:
903  MatchVisitor(ASTContext* Context,
904  MatchFinder::MatchCallback* Callback)
905  : Context(Context),
906  Callback(Callback) {}
907 
908  void visitMatch(const BoundNodes& BoundNodesView) override {
909  Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
910  }
911 
912  private:
913  ASTContext* Context;
914  MatchFinder::MatchCallback* Callback;
915  };
916 
917  // Returns true if 'TypeNode' has an alias that matches the given matcher.
918  bool typeHasMatchingAlias(const Type *TypeNode,
919  const Matcher<NamedDecl> &Matcher,
920  BoundNodesTreeBuilder *Builder) {
921  const Type *const CanonicalType =
922  ActiveASTContext->getCanonicalType(TypeNode);
923  auto Aliases = TypeAliases.find(CanonicalType);
924  if (Aliases == TypeAliases.end())
925  return false;
926  for (const TypedefNameDecl *Alias : Aliases->second) {
927  BoundNodesTreeBuilder Result(*Builder);
928  if (Matcher.matches(*Alias, this, &Result)) {
929  *Builder = std::move(Result);
930  return true;
931  }
932  }
933  return false;
934  }
935 
936  bool
937  objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
938  const Matcher<NamedDecl> &Matcher,
939  BoundNodesTreeBuilder *Builder) {
940  auto Aliases = CompatibleAliases.find(InterfaceDecl);
941  if (Aliases == CompatibleAliases.end())
942  return false;
943  for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
944  BoundNodesTreeBuilder Result(*Builder);
945  if (Matcher.matches(*Alias, this, &Result)) {
946  *Builder = std::move(Result);
947  return true;
948  }
949  }
950  return false;
951  }
952 
953  /// Bucket to record map.
954  ///
955  /// Used to get the appropriate bucket for each matcher.
956  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
957 
958  const MatchFinder::MatchersByType *Matchers;
959 
960  /// Filtered list of matcher indices for each matcher kind.
961  ///
962  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
963  /// kind (and derived kinds) so it is a waste to try every matcher on every
964  /// node.
965  /// We precalculate a list of matchers that pass the toplevel restrict check.
966  llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
967 
968  const MatchFinder::MatchFinderOptions &Options;
969  ASTContext *ActiveASTContext;
970 
971  // Maps a canonical type to its TypedefDecls.
972  llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
973 
974  // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
975  llvm::DenseMap<const ObjCInterfaceDecl *,
977  CompatibleAliases;
978 
979  // Maps (matcher, node) -> the match result for memoization.
980  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
981  MemoizationMap ResultCache;
982 };
983 
984 static CXXRecordDecl *
985 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
986  if (auto *RD = TypeNode->getAsCXXRecordDecl())
987  return RD;
988 
989  // Find the innermost TemplateSpecializationType that isn't an alias template.
990  auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
991  while (TemplateType && TemplateType->isTypeAlias())
992  TemplateType =
993  TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
994 
995  // If this is the name of a (dependent) template specialization, use the
996  // definition of the template, even though it might be specialized later.
997  if (TemplateType)
998  if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
999  TemplateType->getTemplateName().getAsTemplateDecl()))
1000  return ClassTemplate->getTemplatedDecl();
1001 
1002  return nullptr;
1003 }
1004 
1005 // Returns true if the given C++ class is directly or indirectly derived
1006 // from a base type with the given name. A class is not considered to be
1007 // derived from itself.
1008 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
1009  const Matcher<NamedDecl> &Base,
1010  BoundNodesTreeBuilder *Builder,
1011  bool Directly) {
1012  if (!Declaration->hasDefinition())
1013  return false;
1014  for (const auto &It : Declaration->bases()) {
1015  const Type *TypeNode = It.getType().getTypePtr();
1016 
1017  if (typeHasMatchingAlias(TypeNode, Base, Builder))
1018  return true;
1019 
1020  // FIXME: Going to the primary template here isn't really correct, but
1021  // unfortunately we accept a Decl matcher for the base class not a Type
1022  // matcher, so it's the best thing we can do with our current interface.
1023  CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1024  if (!ClassDecl)
1025  continue;
1026  if (ClassDecl == Declaration) {
1027  // This can happen for recursive template definitions.
1028  continue;
1029  }
1030  BoundNodesTreeBuilder Result(*Builder);
1031  if (Base.matches(*ClassDecl, this, &Result)) {
1032  *Builder = std::move(Result);
1033  return true;
1034  }
1035  if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
1036  return true;
1037  }
1038  return false;
1039 }
1040 
1041 // Returns true if the given Objective-C class is directly or indirectly
1042 // derived from a matching base class. A class is not considered to be derived
1043 // from itself.
1044 bool MatchASTVisitor::objcClassIsDerivedFrom(
1045  const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1046  BoundNodesTreeBuilder *Builder, bool Directly) {
1047  // Check if any of the superclasses of the class match.
1048  for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1049  ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1050  // Check if there are any matching compatibility aliases.
1051  if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
1052  return true;
1053 
1054  // Check if there are any matching type aliases.
1055  const Type *TypeNode = ClassDecl->getTypeForDecl();
1056  if (typeHasMatchingAlias(TypeNode, Base, Builder))
1057  return true;
1058 
1059  if (Base.matches(*ClassDecl, this, Builder))
1060  return true;
1061 
1062  // Not `return false` as a temporary workaround for PR43879.
1063  if (Directly)
1064  break;
1065  }
1066 
1067  return false;
1068 }
1069 
1070 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1071  if (!DeclNode) {
1072  return true;
1073  }
1074 
1075  bool ScopedTraversal =
1076  TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1077  bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1078 
1079  if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1080  auto SK = CTSD->getSpecializationKind();
1083  ScopedChildren = true;
1084  } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1085  if (FD->isDefaulted())
1086  ScopedChildren = true;
1087  }
1088 
1089  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1090  ASTChildrenNotSpelledInSource RAII2(this, ScopedChildren);
1091 
1092  match(*DeclNode);
1094 }
1095 
1096 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1097  if (!StmtNode) {
1098  return true;
1099  }
1100  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1101  TraversingASTChildrenNotSpelledInSource;
1102 
1103  ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
1104  match(*StmtNode);
1106 }
1107 
1108 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1109  match(TypeNode);
1111 }
1112 
1113 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1114  // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
1115  // We still want to find those types via matchers, so we match them here. Note
1116  // that the TypeLocs are structurally a shadow-hierarchy to the expressed
1117  // type, so we visit all involved parts of a compound type when matching on
1118  // each TypeLoc.
1119  match(TypeLocNode);
1120  match(TypeLocNode.getType());
1122 }
1123 
1124 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1125  match(*NNS);
1127 }
1128 
1129 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1130  NestedNameSpecifierLoc NNS) {
1131  if (!NNS)
1132  return true;
1133 
1134  match(NNS);
1135 
1136  // We only match the nested name specifier here (as opposed to traversing it)
1137  // because the traversal is already done in the parallel "Loc"-hierarchy.
1138  if (NNS.hasQualifier())
1139  match(*NNS.getNestedNameSpecifier());
1140  return
1142 }
1143 
1144 bool MatchASTVisitor::TraverseConstructorInitializer(
1145  CXXCtorInitializer *CtorInit) {
1146  if (!CtorInit)
1147  return true;
1148 
1149  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1150  TraversingASTChildrenNotSpelledInSource;
1151 
1152  if (!CtorInit->isWritten())
1153  ScopedTraversal = true;
1154 
1155  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1156 
1157  match(*CtorInit);
1158 
1160  CtorInit);
1161 }
1162 
1163 bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1164  match(Loc);
1166 }
1167 
1168 class MatchASTConsumer : public ASTConsumer {
1169 public:
1170  MatchASTConsumer(MatchFinder *Finder,
1171  MatchFinder::ParsingDoneTestCallback *ParsingDone)
1172  : Finder(Finder), ParsingDone(ParsingDone) {}
1173 
1174 private:
1175  void HandleTranslationUnit(ASTContext &Context) override {
1176  if (ParsingDone != nullptr) {
1177  ParsingDone->run();
1178  }
1179  Finder->matchAST(Context);
1180  }
1181 
1182  MatchFinder *Finder;
1183  MatchFinder::ParsingDoneTestCallback *ParsingDone;
1184 };
1185 
1186 } // end namespace
1187 } // end namespace internal
1188 
1190  ASTContext *Context)
1191  : Nodes(Nodes), Context(Context),
1192  SourceManager(&Context->getSourceManager()) {}
1193 
1196 
1198  : Options(std::move(Options)), ParsingDone(nullptr) {}
1199 
1201 
1203  MatchCallback *Action) {
1204  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1205  Matchers.AllCallbacks.insert(Action);
1206 }
1207 
1208 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1209  MatchCallback *Action) {
1210  Matchers.Type.emplace_back(NodeMatch, Action);
1211  Matchers.AllCallbacks.insert(Action);
1212 }
1213 
1215  MatchCallback *Action) {
1216  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1217  Matchers.AllCallbacks.insert(Action);
1218 }
1219 
1221  MatchCallback *Action) {
1222  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1223  Matchers.AllCallbacks.insert(Action);
1224 }
1225 
1227  MatchCallback *Action) {
1228  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1229  Matchers.AllCallbacks.insert(Action);
1230 }
1231 
1233  MatchCallback *Action) {
1234  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1235  Matchers.AllCallbacks.insert(Action);
1236 }
1237 
1239  MatchCallback *Action) {
1240  Matchers.CtorInit.emplace_back(NodeMatch, Action);
1241  Matchers.AllCallbacks.insert(Action);
1242 }
1243 
1245  MatchCallback *Action) {
1246  Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1247  Matchers.AllCallbacks.insert(Action);
1248 }
1249 
1250 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1251  MatchCallback *Action) {
1252  if (NodeMatch.canConvertTo<Decl>()) {
1253  addMatcher(NodeMatch.convertTo<Decl>(), Action);
1254  return true;
1255  } else if (NodeMatch.canConvertTo<QualType>()) {
1256  addMatcher(NodeMatch.convertTo<QualType>(), Action);
1257  return true;
1258  } else if (NodeMatch.canConvertTo<Stmt>()) {
1259  addMatcher(NodeMatch.convertTo<Stmt>(), Action);
1260  return true;
1261  } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1262  addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1263  return true;
1264  } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1265  addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1266  return true;
1267  } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1268  addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
1269  return true;
1270  } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1271  addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1272  return true;
1273  } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1274  addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1275  return true;
1276  }
1277  return false;
1278 }
1279 
1280 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1281  return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1282 }
1283 
1285  internal::MatchASTVisitor Visitor(&Matchers, Options);
1286  Visitor.set_active_ast_context(&Context);
1287  Visitor.match(Node);
1288 }
1289 
1291  internal::MatchASTVisitor Visitor(&Matchers, Options);
1292  Visitor.set_active_ast_context(&Context);
1293  Visitor.onStartOfTranslationUnit();
1294  Visitor.TraverseAST(Context);
1295  Visitor.onEndOfTranslationUnit();
1296 }
1297 
1299  MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1300  ParsingDone = NewParsingDone;
1301 }
1302 
1303 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1304 
1305 } // end namespace ast_matchers
1306 } // end namespace clang
Defines the clang::ASTContext interface.
A (possibly-)qualified type.
Definition: Type.h:661
internal::Matcher< NestedNameSpecifier > NestedNameSpecifierMatcher
Definition: ASTMatchers.h:145
::clang::DynTypedNode DynTypedNode
Stmt - This represents one statement.
Definition: Stmt.h:68
internal::Matcher< Stmt > StatementMatcher
Definition: ASTMatchers.h:142
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
StringRef P
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:39
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
MatchFinder::MatchResult MatchResult
Called when parsing is finished. Intended for testing only.
Will traverse all child nodes.
Definition: ASTTypeTraits.h:41
MatchFinder(MatchFinderOptions Options=MatchFinderOptions())
internal::Matcher< QualType > TypeMatcher
Definition: ASTMatchers.h:143
BoundNodesTreeBuilder Nodes
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:58
MatchType Type
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:185
A C++ nested-name-specifier augmented with source location information.
Definition: Format.h:2835
void addMatcher(const DeclarationMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.
::clang::ASTNodeKind ASTNodeKind
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
DynTypedMatcher::MatcherIDType MatcherID
NodeId Parent
Definition: ASTDiff.cpp:192
bool TraverseConstructorInitializer(CXXCtorInitializer *Init)
Recursively visit a constructor initializer.
DynTypedNode Node
#define V(N, I)
Definition: ASTContext.h:2983
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)
internal::Matcher< TemplateArgumentLoc > TemplateArgumentLocMatcher
Definition: ASTMatchers.h:149
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:107
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.
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument's dy...
internal::Matcher< T > traverse(TraversalKind TK, const internal::Matcher< T > &InnerMatcher)
Causes all nested matchers to be matched with the specified traversal kind.
Definition: ASTMatchers.h:791
This template specialization was instantiated from a template due to an explicit instantiation defini...
Definition: Specifiers.h:181
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's getTypeClass() pr...
BoundNodesTreeBuilder BoundNodes
A dynamically typed AST node container.
Dataflow Directional Tag Classes.
This template specialization was instantiated from a template due to an explicit instantiation declar...
Definition: Specifiers.h:177
internal::Matcher< CXXCtorInitializer > CXXCtorInitializerMatcher
Definition: ASTMatchers.h:147
Location wrapper for a TemplateArgument.
Definition: TemplateBase.h:457
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2151
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:146
internal::Matcher< TypeLoc > TypeLocMatcher
Definition: ASTMatchers.h:144
Called when the Match registered for it was successfully found in the AST.
TraversalKind Traversal
This class handles loading and caching of source files into memory.
bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc)
Recursively visit a template argument location and dispatch to the appropriate method for the argumen...
internal::Matcher< Decl > DeclarationMatcher
Types of matchers for the top-level classes in the AST class hierarchy.
Definition: ASTMatchers.h:141
bool addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.