clang  16.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/PrettyStackTrace.h"
25 #include "llvm/Support/Timer.h"
26 #include <deque>
27 #include <memory>
28 #include <set>
29 
30 namespace clang {
31 namespace ast_matchers {
32 namespace internal {
33 namespace {
34 
35 typedef MatchFinder::MatchCallback MatchCallback;
36 
37 // The maximum number of memoization entries to store.
38 // 10k has been experimentally found to give a good trade-off
39 // of performance vs. memory consumption by running matcher
40 // that match on every statement over a very large codebase.
41 //
42 // FIXME: Do some performance optimization in general and
43 // revisit this number; also, put up micro-benchmarks that we can
44 // optimize this on.
45 static const unsigned MaxMemoizationEntries = 10000;
46 
47 enum class MatchType {
48  Ancestors,
49 
50  Descendants,
51  Child,
52 };
53 
54 // We use memoization to avoid running the same matcher on the same
55 // AST node twice. This struct is the key for looking up match
56 // result. It consists of an ID of the MatcherInterface (for
57 // identifying the matcher), a pointer to the AST node and the
58 // bound nodes before the matcher was executed.
59 //
60 // We currently only memoize on nodes whose pointers identify the
61 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
62 // For \c QualType and \c TypeLoc it is possible to implement
63 // generation of keys for each type.
64 // FIXME: Benchmark whether memoization of non-pointer typed nodes
65 // provides enough benefit for the additional amount of code.
66 struct MatchKey {
67  DynTypedMatcher::MatcherIDType MatcherID;
69  BoundNodesTreeBuilder BoundNodes;
71  MatchType Type;
72 
73  bool operator<(const MatchKey &Other) const {
74  return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
75  std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
76  Other.BoundNodes);
77  }
78 };
79 
80 // Used to store the result of a match and possibly bound nodes.
81 struct MemoizedMatchResult {
83  BoundNodesTreeBuilder Nodes;
84 };
85 
86 // A RecursiveASTVisitor that traverses all children or all descendants of
87 // a node.
88 class MatchChildASTVisitor
89  : public RecursiveASTVisitor<MatchChildASTVisitor> {
90 public:
91  typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
92 
93  // Creates an AST visitor that matches 'matcher' on all children or
94  // descendants of a traversed node. max_depth is the maximum depth
95  // to traverse: use 1 for matching the children and INT_MAX for
96  // matching the descendants.
97  MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
98  BoundNodesTreeBuilder *Builder, int MaxDepth,
99  bool IgnoreImplicitChildren,
100  ASTMatchFinder::BindKind Bind)
101  : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
102  MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
103  Bind(Bind), Matches(false) {}
104 
105  // Returns true if a match is found in the subtree rooted at the
106  // given AST node. This is done via a set of mutually recursive
107  // functions. Here's how the recursion is done (the *wildcard can
108  // actually be Decl, Stmt, or Type):
109  //
110  // - Traverse(node) calls BaseTraverse(node) when it needs
111  // to visit the descendants of node.
112  // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
113  // Traverse*(c) for each child c of 'node'.
114  // - Traverse*(c) in turn calls Traverse(c), completing the
115  // recursion.
116  bool findMatch(const DynTypedNode &DynNode) {
117  reset();
118  if (const Decl *D = DynNode.get<Decl>())
119  traverse(*D);
120  else if (const Stmt *S = DynNode.get<Stmt>())
121  traverse(*S);
122  else if (const NestedNameSpecifier *NNS =
123  DynNode.get<NestedNameSpecifier>())
124  traverse(*NNS);
125  else if (const NestedNameSpecifierLoc *NNSLoc =
126  DynNode.get<NestedNameSpecifierLoc>())
127  traverse(*NNSLoc);
128  else if (const QualType *Q = DynNode.get<QualType>())
129  traverse(*Q);
130  else if (const TypeLoc *T = DynNode.get<TypeLoc>())
131  traverse(*T);
132  else if (const auto *C = DynNode.get<CXXCtorInitializer>())
133  traverse(*C);
134  else if (const TemplateArgumentLoc *TALoc =
135  DynNode.get<TemplateArgumentLoc>())
136  traverse(*TALoc);
137  else if (const Attr *A = DynNode.get<Attr>())
138  traverse(*A);
139  // FIXME: Add other base types after adding tests.
140 
141  // It's OK to always overwrite the bound nodes, as if there was
142  // no match in this recursive branch, the result set is empty
143  // anyway.
144  *Builder = ResultBindings;
145 
146  return Matches;
147  }
148 
149  // The following are overriding methods from the base visitor class.
150  // They are public only to allow CRTP to work. They are *not *part
151  // of the public API of this class.
152  bool TraverseDecl(Decl *DeclNode) {
153 
154  if (DeclNode && DeclNode->isImplicit() &&
155  Finder->isTraversalIgnoringImplicitNodes())
156  return baseTraverse(*DeclNode);
157 
158  ScopedIncrement ScopedDepth(&CurrentDepth);
159  return (DeclNode == nullptr) || traverse(*DeclNode);
160  }
161 
162  Stmt *getStmtToTraverse(Stmt *StmtNode) {
163  Stmt *StmtToTraverse = StmtNode;
164  if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
165  auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
166  if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
167  StmtToTraverse = LambdaNode;
168  else
169  StmtToTraverse =
170  Finder->getASTContext().getParentMapContext().traverseIgnored(
171  ExprNode);
172  }
173  return StmtToTraverse;
174  }
175 
176  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
177  // If we need to keep track of the depth, we can't perform data recursion.
178  if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
179  Queue = nullptr;
180 
181  ScopedIncrement ScopedDepth(&CurrentDepth);
182  Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
183  if (!StmtToTraverse)
184  return true;
185 
186  if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(StmtNode))
187  return true;
188 
189  if (!match(*StmtToTraverse))
190  return false;
191  return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
192  }
193  // We assume that the QualType and the contained type are on the same
194  // hierarchy level. Thus, we try to match either of them.
195  bool TraverseType(QualType TypeNode) {
196  if (TypeNode.isNull())
197  return true;
198  ScopedIncrement ScopedDepth(&CurrentDepth);
199  // Match the Type.
200  if (!match(*TypeNode))
201  return false;
202  // The QualType is matched inside traverse.
203  return traverse(TypeNode);
204  }
205  // We assume that the TypeLoc, contained QualType and contained Type all are
206  // on the same hierarchy level. Thus, we try to match all of them.
207  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
208  if (TypeLocNode.isNull())
209  return true;
210  ScopedIncrement ScopedDepth(&CurrentDepth);
211  // Match the Type.
212  if (!match(*TypeLocNode.getType()))
213  return false;
214  // Match the QualType.
215  if (!match(TypeLocNode.getType()))
216  return false;
217  // The TypeLoc is matched inside traverse.
218  return traverse(TypeLocNode);
219  }
220  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
221  ScopedIncrement ScopedDepth(&CurrentDepth);
222  return (NNS == nullptr) || traverse(*NNS);
223  }
224  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
225  if (!NNS)
226  return true;
227  ScopedIncrement ScopedDepth(&CurrentDepth);
228  if (!match(*NNS.getNestedNameSpecifier()))
229  return false;
230  return traverse(NNS);
231  }
232  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
233  if (!CtorInit)
234  return true;
235  ScopedIncrement ScopedDepth(&CurrentDepth);
236  return traverse(*CtorInit);
237  }
238  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
239  ScopedIncrement ScopedDepth(&CurrentDepth);
240  return traverse(TAL);
241  }
242  bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
243  if (!Finder->isTraversalIgnoringImplicitNodes())
244  return VisitorBase::TraverseCXXForRangeStmt(Node);
245  if (!Node)
246  return true;
247  ScopedIncrement ScopedDepth(&CurrentDepth);
248  if (auto *Init = Node->getInit())
249  if (!traverse(*Init))
250  return false;
251  if (!match(*Node->getLoopVariable()))
252  return false;
253  if (match(*Node->getRangeInit()))
254  if (!VisitorBase::TraverseStmt(Node->getRangeInit()))
255  return false;
256  if (!match(*Node->getBody()))
257  return false;
258  return VisitorBase::TraverseStmt(Node->getBody());
259  }
260  bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
261  if (!Finder->isTraversalIgnoringImplicitNodes())
262  return VisitorBase::TraverseCXXRewrittenBinaryOperator(Node);
263  if (!Node)
264  return true;
265  ScopedIncrement ScopedDepth(&CurrentDepth);
266 
267  return match(*Node->getLHS()) && match(*Node->getRHS());
268  }
269  bool TraverseAttr(Attr *A) {
270  if (A == nullptr ||
271  (A->isImplicit() &&
272  Finder->getASTContext().getParentMapContext().getTraversalKind() ==
274  return true;
275  ScopedIncrement ScopedDepth(&CurrentDepth);
276  return traverse(*A);
277  }
278  bool TraverseLambdaExpr(LambdaExpr *Node) {
279  if (!Finder->isTraversalIgnoringImplicitNodes())
280  return VisitorBase::TraverseLambdaExpr(Node);
281  if (!Node)
282  return true;
283  ScopedIncrement ScopedDepth(&CurrentDepth);
284 
285  for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
286  const auto *C = Node->capture_begin() + I;
287  if (!C->isExplicit())
288  continue;
289  if (Node->isInitCapture(C) && !match(*C->getCapturedVar()))
290  return false;
291  if (!match(*Node->capture_init_begin()[I]))
292  return false;
293  }
294 
295  if (const auto *TPL = Node->getTemplateParameterList()) {
296  for (const auto *TP : *TPL) {
297  if (!match(*TP))
298  return false;
299  }
300  }
301 
302  for (const auto *P : Node->getCallOperator()->parameters()) {
303  if (!match(*P))
304  return false;
305  }
306 
307  if (!match(*Node->getBody()))
308  return false;
309 
310  return VisitorBase::TraverseStmt(Node->getBody());
311  }
312 
313  bool shouldVisitTemplateInstantiations() const { return true; }
314  bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
315 
316 private:
317  // Used for updating the depth during traversal.
318  struct ScopedIncrement {
319  explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
320  ~ScopedIncrement() { --(*Depth); }
321 
322  private:
323  int *Depth;
324  };
325 
326  // Resets the state of this object.
327  void reset() {
328  Matches = false;
329  CurrentDepth = 0;
330  }
331 
332  // Forwards the call to the corresponding Traverse*() method in the
333  // base visitor class.
334  bool baseTraverse(const Decl &DeclNode) {
335  return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
336  }
337  bool baseTraverse(const Stmt &StmtNode) {
338  return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
339  }
340  bool baseTraverse(QualType TypeNode) {
341  return VisitorBase::TraverseType(TypeNode);
342  }
343  bool baseTraverse(TypeLoc TypeLocNode) {
344  return VisitorBase::TraverseTypeLoc(TypeLocNode);
345  }
346  bool baseTraverse(const NestedNameSpecifier &NNS) {
348  const_cast<NestedNameSpecifier*>(&NNS));
349  }
350  bool baseTraverse(NestedNameSpecifierLoc NNS) {
352  }
353  bool baseTraverse(const CXXCtorInitializer &CtorInit) {
355  const_cast<CXXCtorInitializer *>(&CtorInit));
356  }
357  bool baseTraverse(TemplateArgumentLoc TAL) {
359  }
360  bool baseTraverse(const Attr &AttrNode) {
361  return VisitorBase::TraverseAttr(const_cast<Attr *>(&AttrNode));
362  }
363 
364  // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
365  // 0 < CurrentDepth <= MaxDepth.
366  //
367  // Returns 'true' if traversal should continue after this function
368  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
369  template <typename T>
370  bool match(const T &Node) {
371  if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
372  return true;
373  }
374  if (Bind != ASTMatchFinder::BK_All) {
375  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
376  if (Matcher->matches(DynTypedNode::create(Node), Finder,
377  &RecursiveBuilder)) {
378  Matches = true;
379  ResultBindings.addMatch(RecursiveBuilder);
380  return false; // Abort as soon as a match is found.
381  }
382  } else {
383  BoundNodesTreeBuilder RecursiveBuilder(*Builder);
384  if (Matcher->matches(DynTypedNode::create(Node), Finder,
385  &RecursiveBuilder)) {
386  // After the first match the matcher succeeds.
387  Matches = true;
388  ResultBindings.addMatch(RecursiveBuilder);
389  }
390  }
391  return true;
392  }
393 
394  // Traverses the subtree rooted at 'Node'; returns true if the
395  // traversal should continue after this function returns.
396  template <typename T>
397  bool traverse(const T &Node) {
398  static_assert(IsBaseType<T>::value,
399  "traverse can only be instantiated with base type");
400  if (!match(Node))
401  return false;
402  return baseTraverse(Node);
403  }
404 
405  const DynTypedMatcher *const Matcher;
406  ASTMatchFinder *const Finder;
407  BoundNodesTreeBuilder *const Builder;
408  BoundNodesTreeBuilder ResultBindings;
409  int CurrentDepth;
410  const int MaxDepth;
411  const bool IgnoreImplicitChildren;
412  const ASTMatchFinder::BindKind Bind;
413  bool Matches;
414 };
415 
416 // Controls the outermost traversal of the AST and allows to match multiple
417 // matchers.
418 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
419  public ASTMatchFinder {
420 public:
421  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
422  const MatchFinder::MatchFinderOptions &Options)
423  : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
424 
425  ~MatchASTVisitor() override {
426  if (Options.CheckProfiling) {
427  Options.CheckProfiling->Records = std::move(TimeByBucket);
428  }
429  }
430 
431  void onStartOfTranslationUnit() {
432  const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
433  TimeBucketRegion Timer;
434  for (MatchCallback *MC : Matchers->AllCallbacks) {
435  if (EnableCheckProfiling)
436  Timer.setBucket(&TimeByBucket[MC->getID()]);
437  MC->onStartOfTranslationUnit();
438  }
439  }
440 
441  void onEndOfTranslationUnit() {
442  const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
443  TimeBucketRegion Timer;
444  for (MatchCallback *MC : Matchers->AllCallbacks) {
445  if (EnableCheckProfiling)
446  Timer.setBucket(&TimeByBucket[MC->getID()]);
447  MC->onEndOfTranslationUnit();
448  }
449  }
450 
451  void set_active_ast_context(ASTContext *NewActiveASTContext) {
452  ActiveASTContext = NewActiveASTContext;
453  }
454 
455  // The following Visit*() and Traverse*() functions "override"
456  // methods in RecursiveASTVisitor.
457 
458  bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
459  // When we see 'typedef A B', we add name 'B' to the set of names
460  // A's canonical type maps to. This is necessary for implementing
461  // isDerivedFrom(x) properly, where x can be the name of the base
462  // class or any of its aliases.
463  //
464  // In general, the is-alias-of (as defined by typedefs) relation
465  // is tree-shaped, as you can typedef a type more than once. For
466  // example,
467  //
468  // typedef A B;
469  // typedef A C;
470  // typedef C D;
471  // typedef C E;
472  //
473  // gives you
474  //
475  // A
476  // |- B
477  // `- C
478  // |- D
479  // `- E
480  //
481  // It is wrong to assume that the relation is a chain. A correct
482  // implementation of isDerivedFrom() needs to recognize that B and
483  // E are aliases, even though neither is a typedef of the other.
484  // Therefore, we cannot simply walk through one typedef chain to
485  // find out whether the type name matches.
486  const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
487  const Type *CanonicalType = // root of the typedef tree
488  ActiveASTContext->getCanonicalType(TypeNode);
489  TypeAliases[CanonicalType].insert(DeclNode);
490  return true;
491  }
492 
493  bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
494  const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
495  CompatibleAliases[InterfaceDecl].insert(CAD);
496  return true;
497  }
498 
499  bool TraverseDecl(Decl *DeclNode);
500  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
501  bool TraverseType(QualType TypeNode);
502  bool TraverseTypeLoc(TypeLoc TypeNode);
503  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
504  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
505  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
506  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
507  bool TraverseAttr(Attr *AttrNode);
508 
509  bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
510  if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
511  {
512  ASTNodeNotAsIsSourceScope RAII(this, true);
513  TraverseStmt(RF->getInit());
514  // Don't traverse under the loop variable
515  match(*RF->getLoopVariable());
516  TraverseStmt(RF->getRangeInit());
517  }
518  {
519  ASTNodeNotSpelledInSourceScope RAII(this, true);
520  for (auto *SubStmt : RF->children()) {
521  if (SubStmt != RF->getBody())
522  TraverseStmt(SubStmt);
523  }
524  }
525  TraverseStmt(RF->getBody());
526  return true;
527  } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(S)) {
528  {
529  ASTNodeNotAsIsSourceScope RAII(this, true);
530  TraverseStmt(const_cast<Expr *>(RBO->getLHS()));
531  TraverseStmt(const_cast<Expr *>(RBO->getRHS()));
532  }
533  {
534  ASTNodeNotSpelledInSourceScope RAII(this, true);
535  for (auto *SubStmt : RBO->children()) {
536  TraverseStmt(SubStmt);
537  }
538  }
539  return true;
540  } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {
541  for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {
542  auto C = std::get<0>(I);
543  ASTNodeNotSpelledInSourceScope RAII(
544  this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
545  TraverseLambdaCapture(LE, &C, std::get<1>(I));
546  }
547 
548  {
549  ASTNodeNotSpelledInSourceScope RAII(this, true);
550  TraverseDecl(LE->getLambdaClass());
551  }
552  {
553  ASTNodeNotAsIsSourceScope RAII(this, true);
554 
555  // We need to poke around to find the bits that might be explicitly
556  // written.
557  TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
558  FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
559 
560  if (auto *TPL = LE->getTemplateParameterList()) {
561  for (NamedDecl *D : *TPL) {
562  TraverseDecl(D);
563  }
564  if (Expr *RequiresClause = TPL->getRequiresClause()) {
565  TraverseStmt(RequiresClause);
566  }
567  }
568 
569  if (LE->hasExplicitParameters()) {
570  // Visit parameters.
571  for (ParmVarDecl *Param : Proto.getParams())
572  TraverseDecl(Param);
573  }
574 
575  const auto *T = Proto.getTypePtr();
576  for (const auto &E : T->exceptions())
577  TraverseType(E);
578 
579  if (Expr *NE = T->getNoexceptExpr())
580  TraverseStmt(NE, Queue);
581 
582  if (LE->hasExplicitResultType())
583  TraverseTypeLoc(Proto.getReturnLoc());
584  TraverseStmt(LE->getTrailingRequiresClause());
585  }
586 
587  TraverseStmt(LE->getBody());
588  return true;
589  }
591  }
592 
593  // Matches children or descendants of 'Node' with 'BaseMatcher'.
594  bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
595  const DynTypedMatcher &Matcher,
596  BoundNodesTreeBuilder *Builder, int MaxDepth,
597  BindKind Bind) {
598  // For AST-nodes that don't have an identity, we can't memoize.
599  if (!Node.getMemoizationData() || !Builder->isComparable())
600  return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
601 
602  MatchKey Key;
603  Key.MatcherID = Matcher.getID();
604  Key.Node = Node;
605  // Note that we key on the bindings *before* the match.
606  Key.BoundNodes = *Builder;
607  Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
608  // Memoize result even doing a single-level match, it might be expensive.
609  Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
610  MemoizationMap::iterator I = ResultCache.find(Key);
611  if (I != ResultCache.end()) {
612  *Builder = I->second.Nodes;
613  return I->second.ResultOfMatch;
614  }
615 
616  MemoizedMatchResult Result;
617  Result.Nodes = *Builder;
618  Result.ResultOfMatch =
619  matchesRecursively(Node, Matcher, &Result.Nodes, MaxDepth, Bind);
620 
621  MemoizedMatchResult &CachedResult = ResultCache[Key];
622  CachedResult = std::move(Result);
623 
624  *Builder = CachedResult.Nodes;
625  return CachedResult.ResultOfMatch;
626  }
627 
628  // Matches children or descendants of 'Node' with 'BaseMatcher'.
629  bool matchesRecursively(const DynTypedNode &Node,
630  const DynTypedMatcher &Matcher,
631  BoundNodesTreeBuilder *Builder, int MaxDepth,
632  BindKind Bind) {
633  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
634  TraversingASTChildrenNotSpelledInSource;
635 
636  bool IgnoreImplicitChildren = false;
637 
638  if (isTraversalIgnoringImplicitNodes()) {
639  IgnoreImplicitChildren = true;
640  }
641 
642  ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
643 
644  MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
645  IgnoreImplicitChildren, Bind);
646  return Visitor.findMatch(Node);
647  }
648 
649  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
650  const Matcher<NamedDecl> &Base,
651  BoundNodesTreeBuilder *Builder,
652  bool Directly) override;
653 
654  bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
655  const Matcher<NamedDecl> &Base,
656  BoundNodesTreeBuilder *Builder,
657  bool Directly) override;
658 
659  // Implements ASTMatchFinder::matchesChildOf.
660  bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
661  const DynTypedMatcher &Matcher,
662  BoundNodesTreeBuilder *Builder, BindKind Bind) override {
663  if (ResultCache.size() > MaxMemoizationEntries)
664  ResultCache.clear();
665  return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Bind);
666  }
667  // Implements ASTMatchFinder::matchesDescendantOf.
668  bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
669  const DynTypedMatcher &Matcher,
670  BoundNodesTreeBuilder *Builder,
671  BindKind Bind) override {
672  if (ResultCache.size() > MaxMemoizationEntries)
673  ResultCache.clear();
674  return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
675  Bind);
676  }
677  // Implements ASTMatchFinder::matchesAncestorOf.
678  bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
679  const DynTypedMatcher &Matcher,
680  BoundNodesTreeBuilder *Builder,
681  AncestorMatchMode MatchMode) override {
682  // Reset the cache outside of the recursive call to make sure we
683  // don't invalidate any iterators.
684  if (ResultCache.size() > MaxMemoizationEntries)
685  ResultCache.clear();
686  if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
687  return matchesParentOf(Node, Matcher, Builder);
688  return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
689  }
690 
691  // Matches all registered matchers on the given node and calls the
692  // result callback for every node that matches.
693  void match(const DynTypedNode &Node) {
694  // FIXME: Improve this with a switch or a visitor pattern.
695  if (auto *N = Node.get<Decl>()) {
696  match(*N);
697  } else if (auto *N = Node.get<Stmt>()) {
698  match(*N);
699  } else if (auto *N = Node.get<Type>()) {
700  match(*N);
701  } else if (auto *N = Node.get<QualType>()) {
702  match(*N);
703  } else if (auto *N = Node.get<NestedNameSpecifier>()) {
704  match(*N);
705  } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
706  match(*N);
707  } else if (auto *N = Node.get<TypeLoc>()) {
708  match(*N);
709  } else if (auto *N = Node.get<CXXCtorInitializer>()) {
710  match(*N);
711  } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
712  match(*N);
713  } else if (auto *N = Node.get<Attr>()) {
714  match(*N);
715  }
716  }
717 
718  template <typename T> void match(const T &Node) {
719  matchDispatch(&Node);
720  }
721 
722  // Implements ASTMatchFinder::getASTContext.
723  ASTContext &getASTContext() const override { return *ActiveASTContext; }
724 
725  bool shouldVisitTemplateInstantiations() const { return true; }
726  bool shouldVisitImplicitCode() const { return true; }
727 
728  // We visit the lambda body explicitly, so instruct the RAV
729  // to not visit it on our behalf too.
730  bool shouldVisitLambdaBody() const { return false; }
731 
732  bool IsMatchingInASTNodeNotSpelledInSource() const override {
733  return TraversingASTNodeNotSpelledInSource;
734  }
735  bool isMatchingChildrenNotSpelledInSource() const override {
736  return TraversingASTChildrenNotSpelledInSource;
737  }
738  void setMatchingChildrenNotSpelledInSource(bool Set) override {
739  TraversingASTChildrenNotSpelledInSource = Set;
740  }
741 
742  bool IsMatchingInASTNodeNotAsIs() const override {
743  return TraversingASTNodeNotAsIs;
744  }
745 
746  bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
747  ASTNodeNotSpelledInSourceScope RAII(this, true);
748  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
749  D);
750  }
751 
752  bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
753  ASTNodeNotSpelledInSourceScope RAII(this, true);
754  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
755  D);
756  }
757 
758  bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
759  ASTNodeNotSpelledInSourceScope RAII(this, true);
760  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
761  D);
762  }
763 
764 private:
765  bool TraversingASTNodeNotSpelledInSource = false;
766  bool TraversingASTNodeNotAsIs = false;
767  bool TraversingASTChildrenNotSpelledInSource = false;
768 
769  class CurMatchData {
770 // We don't have enough free low bits in 32bit builds to discriminate 8 pointer
771 // types in PointerUnion. so split the union in 2 using a free bit from the
772 // callback pointer.
773 #define CMD_TYPES_0 \
774  const QualType *, const TypeLoc *, const NestedNameSpecifier *, \
775  const NestedNameSpecifierLoc *
776 #define CMD_TYPES_1 \
777  const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *, \
778  const DynTypedNode *
779 
780 #define IMPL(Index) \
781  template <typename NodeType> \
782  typename std::enable_if_t< \
783  llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value> \
784  SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) { \
785  assertEmpty(); \
786  Callback.setPointerAndInt(CB, Index); \
787  Node##Index = &N; \
788  } \
789  \
790  template <typename T> \
791  typename std::enable_if_t< \
792  llvm::is_one_of<const T *, CMD_TYPES_##Index>::value, const T *> \
793  getNode() const { \
794  assertHoldsState(); \
795  return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>() \
796  : nullptr; \
797  }
798 
799  public:
800  CurMatchData() : Node0(nullptr) {}
801 
802  IMPL(0)
803  IMPL(1)
804 
805  const MatchCallback *getCallback() const { return Callback.getPointer(); }
806 
807  void SetBoundNodes(const BoundNodes &BN) {
808  assertHoldsState();
809  BNodes = &BN;
810  }
811 
812  void clearBoundNodes() {
813  assertHoldsState();
814  BNodes = nullptr;
815  }
816 
817  const BoundNodes *getBoundNodes() const {
818  assertHoldsState();
819  return BNodes;
820  }
821 
822  void reset() {
823  assertHoldsState();
824  Callback.setPointerAndInt(nullptr, 0);
825  Node0 = nullptr;
826  }
827 
828  private:
829  void assertHoldsState() const {
830  assert(Callback.getPointer() != nullptr && !Node0.isNull());
831  }
832 
833  void assertEmpty() const {
834  assert(Callback.getPointer() == nullptr && Node0.isNull() &&
835  BNodes == nullptr);
836  }
837 
838  llvm::PointerIntPair<const MatchCallback *, 1> Callback;
839  union {
840  llvm::PointerUnion<CMD_TYPES_0> Node0;
841  llvm::PointerUnion<CMD_TYPES_1> Node1;
842  };
843  const BoundNodes *BNodes = nullptr;
844 
845 #undef CMD_TYPES_0
846 #undef CMD_TYPES_1
847 #undef IMPL
848  } CurMatchState;
849 
850  struct CurMatchRAII {
851  template <typename NodeType>
852  CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,
853  const NodeType &NT)
854  : MV(MV) {
855  MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
856  }
857 
858  ~CurMatchRAII() { MV.CurMatchState.reset(); }
859 
860  private:
861  MatchASTVisitor &MV;
862  };
863 
864 public:
865  class TraceReporter : llvm::PrettyStackTraceEntry {
866  static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,
867  raw_ostream &OS) {
868  if (const auto *D = Node.get<Decl>()) {
869  OS << D->getDeclKindName() << "Decl ";
870  if (const auto *ND = dyn_cast<NamedDecl>(D)) {
871  ND->printQualifiedName(OS);
872  OS << " : ";
873  } else
874  OS << ": ";
875  D->getSourceRange().print(OS, Ctx.getSourceManager());
876  } else if (const auto *S = Node.get<Stmt>()) {
877  OS << S->getStmtClassName() << " : ";
878  S->getSourceRange().print(OS, Ctx.getSourceManager());
879  } else if (const auto *T = Node.get<Type>()) {
880  OS << T->getTypeClassName() << "Type : ";
881  QualType(T, 0).print(OS, Ctx.getPrintingPolicy());
882  } else if (const auto *QT = Node.get<QualType>()) {
883  OS << "QualType : ";
884  QT->print(OS, Ctx.getPrintingPolicy());
885  } else {
886  OS << Node.getNodeKind().asStringRef() << " : ";
887  Node.getSourceRange().print(OS, Ctx.getSourceManager());
888  }
889  }
890 
891  static void dumpNodeFromState(const ASTContext &Ctx,
892  const CurMatchData &State, raw_ostream &OS) {
893  if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {
894  dumpNode(Ctx, *MatchNode, OS);
895  } else if (const auto *QT = State.getNode<QualType>()) {
896  dumpNode(Ctx, DynTypedNode::create(*QT), OS);
897  } else if (const auto *TL = State.getNode<TypeLoc>()) {
898  dumpNode(Ctx, DynTypedNode::create(*TL), OS);
899  } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {
900  dumpNode(Ctx, DynTypedNode::create(*NNS), OS);
901  } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {
902  dumpNode(Ctx, DynTypedNode::create(*NNSL), OS);
903  } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {
904  dumpNode(Ctx, DynTypedNode::create(*CtorInit), OS);
905  } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {
906  dumpNode(Ctx, DynTypedNode::create(*TAL), OS);
907  } else if (const auto *At = State.getNode<Attr>()) {
908  dumpNode(Ctx, DynTypedNode::create(*At), OS);
909  }
910  }
911 
912  public:
913  TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}
914  void print(raw_ostream &OS) const override {
915  const CurMatchData &State = MV.CurMatchState;
916  const MatchCallback *CB = State.getCallback();
917  if (!CB) {
918  OS << "ASTMatcher: Not currently matching\n";
919  return;
920  }
921 
922  assert(MV.ActiveASTContext &&
923  "ActiveASTContext should be set if there is a matched callback");
924 
925  ASTContext &Ctx = MV.getASTContext();
926 
927  if (const BoundNodes *Nodes = State.getBoundNodes()) {
928  OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";
929  dumpNodeFromState(Ctx, State, OS);
930  const BoundNodes::IDToNodeMap &Map = Nodes->getMap();
931  if (Map.empty()) {
932  OS << "\nNo bound nodes\n";
933  return;
934  }
935  OS << "\n--- Bound Nodes Begin ---\n";
936  for (const auto &Item : Map) {
937  OS << " " << Item.first << " - { ";
938  dumpNode(Ctx, Item.second, OS);
939  OS << " }\n";
940  }
941  OS << "--- Bound Nodes End ---\n";
942  } else {
943  OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";
944  dumpNodeFromState(Ctx, State, OS);
945  OS << '\n';
946  }
947  }
948 
949  private:
950  const MatchASTVisitor &MV;
951  };
952 
953 private:
954  struct ASTNodeNotSpelledInSourceScope {
955  ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
956  : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
957  V->TraversingASTNodeNotSpelledInSource = B;
958  }
959  ~ASTNodeNotSpelledInSourceScope() {
960  MV->TraversingASTNodeNotSpelledInSource = MB;
961  }
962 
963  private:
964  MatchASTVisitor *MV;
965  bool MB;
966  };
967 
968  struct ASTNodeNotAsIsSourceScope {
969  ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
970  : MV(V), MB(V->TraversingASTNodeNotAsIs) {
971  V->TraversingASTNodeNotAsIs = B;
972  }
973  ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
974 
975  private:
976  MatchASTVisitor *MV;
977  bool MB;
978  };
979 
980  class TimeBucketRegion {
981  public:
982  TimeBucketRegion() : Bucket(nullptr) {}
983  ~TimeBucketRegion() { setBucket(nullptr); }
984 
985  /// Start timing for \p NewBucket.
986  ///
987  /// If there was a bucket already set, it will finish the timing for that
988  /// other bucket.
989  /// \p NewBucket will be timed until the next call to \c setBucket() or
990  /// until the \c TimeBucketRegion is destroyed.
991  /// If \p NewBucket is the same as the currently timed bucket, this call
992  /// does nothing.
993  void setBucket(llvm::TimeRecord *NewBucket) {
994  if (Bucket != NewBucket) {
995  auto Now = llvm::TimeRecord::getCurrentTime(true);
996  if (Bucket)
997  *Bucket += Now;
998  if (NewBucket)
999  *NewBucket -= Now;
1000  Bucket = NewBucket;
1001  }
1002  }
1003 
1004  private:
1005  llvm::TimeRecord *Bucket;
1006  };
1007 
1008  /// Runs all the \p Matchers on \p Node.
1009  ///
1010  /// Used by \c matchDispatch() below.
1011  template <typename T, typename MC>
1012  void matchWithoutFilter(const T &Node, const MC &Matchers) {
1013  const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1014  TimeBucketRegion Timer;
1015  for (const auto &MP : Matchers) {
1016  if (EnableCheckProfiling)
1017  Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1018  BoundNodesTreeBuilder Builder;
1019  CurMatchRAII RAII(*this, MP.second, Node);
1020  if (MP.first.matches(Node, this, &Builder)) {
1021  MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1022  Builder.visitMatches(&Visitor);
1023  }
1024  }
1025  }
1026 
1027  void matchWithFilter(const DynTypedNode &DynNode) {
1028  auto Kind = DynNode.getNodeKind();
1029  auto it = MatcherFiltersMap.find(Kind);
1030  const auto &Filter =
1031  it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
1032 
1033  if (Filter.empty())
1034  return;
1035 
1036  const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1037  TimeBucketRegion Timer;
1038  auto &Matchers = this->Matchers->DeclOrStmt;
1039  for (unsigned short I : Filter) {
1040  auto &MP = Matchers[I];
1041  if (EnableCheckProfiling)
1042  Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1043  BoundNodesTreeBuilder Builder;
1044 
1045  {
1046  TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
1047  if (getASTContext().getParentMapContext().traverseIgnored(DynNode) !=
1048  DynNode)
1049  continue;
1050  }
1051 
1052  CurMatchRAII RAII(*this, MP.second, DynNode);
1053  if (MP.first.matches(DynNode, this, &Builder)) {
1054  MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1055  Builder.visitMatches(&Visitor);
1056  }
1057  }
1058  }
1059 
1060  const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
1061  auto &Filter = MatcherFiltersMap[Kind];
1062  auto &Matchers = this->Matchers->DeclOrStmt;
1063  assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
1064  for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
1065  if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
1066  Filter.push_back(I);
1067  }
1068  }
1069  return Filter;
1070  }
1071 
1072  /// @{
1073  /// Overloads to pair the different node types to their matchers.
1074  void matchDispatch(const Decl *Node) {
1075  return matchWithFilter(DynTypedNode::create(*Node));
1076  }
1077  void matchDispatch(const Stmt *Node) {
1078  return matchWithFilter(DynTypedNode::create(*Node));
1079  }
1080 
1081  void matchDispatch(const Type *Node) {
1082  matchWithoutFilter(QualType(Node, 0), Matchers->Type);
1083  }
1084  void matchDispatch(const TypeLoc *Node) {
1085  matchWithoutFilter(*Node, Matchers->TypeLoc);
1086  }
1087  void matchDispatch(const QualType *Node) {
1088  matchWithoutFilter(*Node, Matchers->Type);
1089  }
1090  void matchDispatch(const NestedNameSpecifier *Node) {
1091  matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
1092  }
1093  void matchDispatch(const NestedNameSpecifierLoc *Node) {
1094  matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
1095  }
1096  void matchDispatch(const CXXCtorInitializer *Node) {
1097  matchWithoutFilter(*Node, Matchers->CtorInit);
1098  }
1099  void matchDispatch(const TemplateArgumentLoc *Node) {
1100  matchWithoutFilter(*Node, Matchers->TemplateArgumentLoc);
1101  }
1102  void matchDispatch(const Attr *Node) {
1103  matchWithoutFilter(*Node, Matchers->Attr);
1104  }
1105  void matchDispatch(const void *) { /* Do nothing. */ }
1106  /// @}
1107 
1108  // Returns whether a direct parent of \p Node matches \p Matcher.
1109  // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
1110  bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
1111  BoundNodesTreeBuilder *Builder) {
1112  for (const auto &Parent : ActiveASTContext->getParents(Node)) {
1113  BoundNodesTreeBuilder BuilderCopy = *Builder;
1114  if (Matcher.matches(Parent, this, &BuilderCopy)) {
1115  *Builder = std::move(BuilderCopy);
1116  return true;
1117  }
1118  }
1119  return false;
1120  }
1121 
1122  // Returns whether an ancestor of \p Node matches \p Matcher.
1123  //
1124  // The order of matching (which can lead to different nodes being bound in
1125  // case there are multiple matches) is breadth first search.
1126  //
1127  // To allow memoization in the very common case of having deeply nested
1128  // expressions inside a template function, we first walk up the AST, memoizing
1129  // the result of the match along the way, as long as there is only a single
1130  // parent.
1131  //
1132  // Once there are multiple parents, the breadth first search order does not
1133  // allow simple memoization on the ancestors. Thus, we only memoize as long
1134  // as there is a single parent.
1135  //
1136  // We avoid a recursive implementation to prevent excessive stack use on
1137  // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
1138  bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
1139  const DynTypedMatcher &Matcher,
1140  BoundNodesTreeBuilder *Builder) {
1141 
1142  // Memoization keys that can be updated with the result.
1143  // These are the memoizable nodes in the chain of unique parents, which
1144  // terminates when a node has multiple parents, or matches, or is the root.
1145  std::vector<MatchKey> Keys;
1146  // When returning, update the memoization cache.
1147  auto Finish = [&](bool Matched) {
1148  for (const auto &Key : Keys) {
1149  MemoizedMatchResult &CachedResult = ResultCache[Key];
1150  CachedResult.ResultOfMatch = Matched;
1151  CachedResult.Nodes = *Builder;
1152  }
1153  return Matched;
1154  };
1155 
1156  // Loop while there's a single parent and we want to attempt memoization.
1157  DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
1158  for (;;) {
1159  // A cache key only makes sense if memoization is possible.
1160  if (Builder->isComparable()) {
1161  Keys.emplace_back();
1162  Keys.back().MatcherID = Matcher.getID();
1163  Keys.back().Node = Node;
1164  Keys.back().BoundNodes = *Builder;
1165  Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
1166  Keys.back().Type = MatchType::Ancestors;
1167 
1168  // Check the cache.
1169  MemoizationMap::iterator I = ResultCache.find(Keys.back());
1170  if (I != ResultCache.end()) {
1171  Keys.pop_back(); // Don't populate the cache for the matching node!
1172  *Builder = I->second.Nodes;
1173  return Finish(I->second.ResultOfMatch);
1174  }
1175  }
1176 
1177  Parents = ActiveASTContext->getParents(Node);
1178  // Either no parents or multiple parents: leave chain+memoize mode and
1179  // enter bfs+forgetful mode.
1180  if (Parents.size() != 1)
1181  break;
1182 
1183  // Check the next parent.
1184  Node = *Parents.begin();
1185  BoundNodesTreeBuilder BuilderCopy = *Builder;
1186  if (Matcher.matches(Node, this, &BuilderCopy)) {
1187  *Builder = std::move(BuilderCopy);
1188  return Finish(true);
1189  }
1190  }
1191  // We reached the end of the chain.
1192 
1193  if (Parents.empty()) {
1194  // Nodes may have no parents if:
1195  // a) the node is the TranslationUnitDecl
1196  // b) we have a limited traversal scope that excludes the parent edges
1197  // c) there is a bug in the AST, and the node is not reachable
1198  // Usually the traversal scope is the whole AST, which precludes b.
1199  // Bugs are common enough that it's worthwhile asserting when we can.
1200 #ifndef NDEBUG
1201  if (!Node.get<TranslationUnitDecl>() &&
1202  /* Traversal scope is full AST if any of the bounds are the TU */
1203  llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
1204  return D->getKind() == Decl::TranslationUnit;
1205  })) {
1206  llvm::errs() << "Tried to match orphan node:\n";
1207  Node.dump(llvm::errs(), *ActiveASTContext);
1208  llvm_unreachable("Parent map should be complete!");
1209  }
1210 #endif
1211  } else {
1212  assert(Parents.size() > 1);
1213  // BFS starting from the parents not yet considered.
1214  // Memoization of newly visited nodes is not possible (but we still update
1215  // results for the elements in the chain we found above).
1216  std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1218  while (!Queue.empty()) {
1219  BoundNodesTreeBuilder BuilderCopy = *Builder;
1220  if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
1221  *Builder = std::move(BuilderCopy);
1222  return Finish(true);
1223  }
1224  for (const auto &Parent : ActiveASTContext->getParents(Queue.front())) {
1225  // Make sure we do not visit the same node twice.
1226  // Otherwise, we'll visit the common ancestors as often as there
1227  // are splits on the way down.
1228  if (Visited.insert(Parent.getMemoizationData()).second)
1229  Queue.push_back(Parent);
1230  }
1231  Queue.pop_front();
1232  }
1233  }
1234  return Finish(false);
1235  }
1236 
1237  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
1238  // the aggregated bound nodes for each match.
1239  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
1240  struct CurBoundScope {
1241  CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)
1242  : State(State) {
1243  State.SetBoundNodes(BN);
1244  }
1245 
1246  ~CurBoundScope() { State.clearBoundNodes(); }
1247 
1248  private:
1249  MatchASTVisitor::CurMatchData &State;
1250  };
1251 
1252  public:
1253  MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
1254  MatchFinder::MatchCallback *Callback)
1255  : State(MV.CurMatchState), Context(Context), Callback(Callback) {}
1256 
1257  void visitMatch(const BoundNodes& BoundNodesView) override {
1258  TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
1259  CurBoundScope RAII2(State, BoundNodesView);
1260  Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
1261  }
1262 
1263  private:
1264  MatchASTVisitor::CurMatchData &State;
1265  ASTContext* Context;
1266  MatchFinder::MatchCallback* Callback;
1267  };
1268 
1269  // Returns true if 'TypeNode' has an alias that matches the given matcher.
1270  bool typeHasMatchingAlias(const Type *TypeNode,
1271  const Matcher<NamedDecl> &Matcher,
1272  BoundNodesTreeBuilder *Builder) {
1273  const Type *const CanonicalType =
1274  ActiveASTContext->getCanonicalType(TypeNode);
1275  auto Aliases = TypeAliases.find(CanonicalType);
1276  if (Aliases == TypeAliases.end())
1277  return false;
1278  for (const TypedefNameDecl *Alias : Aliases->second) {
1279  BoundNodesTreeBuilder Result(*Builder);
1280  if (Matcher.matches(*Alias, this, &Result)) {
1281  *Builder = std::move(Result);
1282  return true;
1283  }
1284  }
1285  return false;
1286  }
1287 
1288  bool
1289  objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
1290  const Matcher<NamedDecl> &Matcher,
1291  BoundNodesTreeBuilder *Builder) {
1292  auto Aliases = CompatibleAliases.find(InterfaceDecl);
1293  if (Aliases == CompatibleAliases.end())
1294  return false;
1295  for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1296  BoundNodesTreeBuilder Result(*Builder);
1297  if (Matcher.matches(*Alias, this, &Result)) {
1298  *Builder = std::move(Result);
1299  return true;
1300  }
1301  }
1302  return false;
1303  }
1304 
1305  /// Bucket to record map.
1306  ///
1307  /// Used to get the appropriate bucket for each matcher.
1308  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1309 
1310  const MatchFinder::MatchersByType *Matchers;
1311 
1312  /// Filtered list of matcher indices for each matcher kind.
1313  ///
1314  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
1315  /// kind (and derived kinds) so it is a waste to try every matcher on every
1316  /// node.
1317  /// We precalculate a list of matchers that pass the toplevel restrict check.
1318  llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1319 
1320  const MatchFinder::MatchFinderOptions &Options;
1321  ASTContext *ActiveASTContext;
1322 
1323  // Maps a canonical type to its TypedefDecls.
1324  llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1325 
1326  // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
1327  llvm::DenseMap<const ObjCInterfaceDecl *,
1329  CompatibleAliases;
1330 
1331  // Maps (matcher, node) -> the match result for memoization.
1332  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1333  MemoizationMap ResultCache;
1334 };
1335 
1336 static CXXRecordDecl *
1337 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
1338  if (auto *RD = TypeNode->getAsCXXRecordDecl())
1339  return RD;
1340 
1341  // Find the innermost TemplateSpecializationType that isn't an alias template.
1342  auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1343  while (TemplateType && TemplateType->isTypeAlias())
1344  TemplateType =
1345  TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1346 
1347  // If this is the name of a (dependent) template specialization, use the
1348  // definition of the template, even though it might be specialized later.
1349  if (TemplateType)
1350  if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1351  TemplateType->getTemplateName().getAsTemplateDecl()))
1352  return ClassTemplate->getTemplatedDecl();
1353 
1354  return nullptr;
1355 }
1356 
1357 // Returns true if the given C++ class is directly or indirectly derived
1358 // from a base type with the given name. A class is not considered to be
1359 // derived from itself.
1360 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
1361  const Matcher<NamedDecl> &Base,
1362  BoundNodesTreeBuilder *Builder,
1363  bool Directly) {
1364  if (!Declaration->hasDefinition())
1365  return false;
1366  for (const auto &It : Declaration->bases()) {
1367  const Type *TypeNode = It.getType().getTypePtr();
1368 
1369  if (typeHasMatchingAlias(TypeNode, Base, Builder))
1370  return true;
1371 
1372  // FIXME: Going to the primary template here isn't really correct, but
1373  // unfortunately we accept a Decl matcher for the base class not a Type
1374  // matcher, so it's the best thing we can do with our current interface.
1375  CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1376  if (!ClassDecl)
1377  continue;
1378  if (ClassDecl == Declaration) {
1379  // This can happen for recursive template definitions.
1380  continue;
1381  }
1382  BoundNodesTreeBuilder Result(*Builder);
1383  if (Base.matches(*ClassDecl, this, &Result)) {
1384  *Builder = std::move(Result);
1385  return true;
1386  }
1387  if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
1388  return true;
1389  }
1390  return false;
1391 }
1392 
1393 // Returns true if the given Objective-C class is directly or indirectly
1394 // derived from a matching base class. A class is not considered to be derived
1395 // from itself.
1396 bool MatchASTVisitor::objcClassIsDerivedFrom(
1397  const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1398  BoundNodesTreeBuilder *Builder, bool Directly) {
1399  // Check if any of the superclasses of the class match.
1400  for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1401  ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1402  // Check if there are any matching compatibility aliases.
1403  if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
1404  return true;
1405 
1406  // Check if there are any matching type aliases.
1407  const Type *TypeNode = ClassDecl->getTypeForDecl();
1408  if (typeHasMatchingAlias(TypeNode, Base, Builder))
1409  return true;
1410 
1411  if (Base.matches(*ClassDecl, this, Builder))
1412  return true;
1413 
1414  // Not `return false` as a temporary workaround for PR43879.
1415  if (Directly)
1416  break;
1417  }
1418 
1419  return false;
1420 }
1421 
1422 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1423  if (!DeclNode) {
1424  return true;
1425  }
1426 
1427  bool ScopedTraversal =
1428  TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1429  bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1430 
1431  if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(DeclNode)) {
1432  auto SK = CTSD->getSpecializationKind();
1435  ScopedChildren = true;
1436  } else if (const auto *FD = dyn_cast<FunctionDecl>(DeclNode)) {
1437  if (FD->isDefaulted())
1438  ScopedChildren = true;
1439  if (FD->isTemplateInstantiation())
1440  ScopedTraversal = true;
1441  } else if (isa<BindingDecl>(DeclNode)) {
1442  ScopedChildren = true;
1443  }
1444 
1445  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1446  ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
1447 
1448  match(*DeclNode);
1450 }
1451 
1452 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1453  if (!StmtNode) {
1454  return true;
1455  }
1456  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1457  TraversingASTChildrenNotSpelledInSource;
1458 
1459  ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
1460  match(*StmtNode);
1462 }
1463 
1464 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1465  match(TypeNode);
1467 }
1468 
1469 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1470  // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
1471  // We still want to find those types via matchers, so we match them here. Note
1472  // that the TypeLocs are structurally a shadow-hierarchy to the expressed
1473  // type, so we visit all involved parts of a compound type when matching on
1474  // each TypeLoc.
1475  match(TypeLocNode);
1476  match(TypeLocNode.getType());
1478 }
1479 
1480 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1481  match(*NNS);
1483 }
1484 
1485 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1486  NestedNameSpecifierLoc NNS) {
1487  if (!NNS)
1488  return true;
1489 
1490  match(NNS);
1491 
1492  // We only match the nested name specifier here (as opposed to traversing it)
1493  // because the traversal is already done in the parallel "Loc"-hierarchy.
1494  if (NNS.hasQualifier())
1495  match(*NNS.getNestedNameSpecifier());
1496  return
1498 }
1499 
1500 bool MatchASTVisitor::TraverseConstructorInitializer(
1501  CXXCtorInitializer *CtorInit) {
1502  if (!CtorInit)
1503  return true;
1504 
1505  bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1506  TraversingASTChildrenNotSpelledInSource;
1507 
1508  if (!CtorInit->isWritten())
1509  ScopedTraversal = true;
1510 
1511  ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1512 
1513  match(*CtorInit);
1514 
1516  CtorInit);
1517 }
1518 
1519 bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1520  match(Loc);
1522 }
1523 
1524 bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1525  match(*AttrNode);
1527 }
1528 
1529 class MatchASTConsumer : public ASTConsumer {
1530 public:
1531  MatchASTConsumer(MatchFinder *Finder,
1532  MatchFinder::ParsingDoneTestCallback *ParsingDone)
1533  : Finder(Finder), ParsingDone(ParsingDone) {}
1534 
1535 private:
1536  void HandleTranslationUnit(ASTContext &Context) override {
1537  if (ParsingDone != nullptr) {
1538  ParsingDone->run();
1539  }
1540  Finder->matchAST(Context);
1541  }
1542 
1543  MatchFinder *Finder;
1544  MatchFinder::ParsingDoneTestCallback *ParsingDone;
1545 };
1546 
1547 } // end namespace
1548 } // end namespace internal
1549 
1551  ASTContext *Context)
1552  : Nodes(Nodes), Context(Context),
1553  SourceManager(&Context->getSourceManager()) {}
1554 
1557 
1559  : Options(std::move(Options)), ParsingDone(nullptr) {}
1560 
1562 
1564  MatchCallback *Action) {
1566  if (Action)
1567  TK = Action->getCheckTraversalKind();
1568  if (TK)
1569  Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1570  else
1571  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1572  Matchers.AllCallbacks.insert(Action);
1573 }
1574 
1575 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1576  MatchCallback *Action) {
1577  Matchers.Type.emplace_back(NodeMatch, Action);
1578  Matchers.AllCallbacks.insert(Action);
1579 }
1580 
1582  MatchCallback *Action) {
1584  if (Action)
1585  TK = Action->getCheckTraversalKind();
1586  if (TK)
1587  Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
1588  else
1589  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1590  Matchers.AllCallbacks.insert(Action);
1591 }
1592 
1594  MatchCallback *Action) {
1595  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1596  Matchers.AllCallbacks.insert(Action);
1597 }
1598 
1600  MatchCallback *Action) {
1601  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1602  Matchers.AllCallbacks.insert(Action);
1603 }
1604 
1606  MatchCallback *Action) {
1607  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1608  Matchers.AllCallbacks.insert(Action);
1609 }
1610 
1612  MatchCallback *Action) {
1613  Matchers.CtorInit.emplace_back(NodeMatch, Action);
1614  Matchers.AllCallbacks.insert(Action);
1615 }
1616 
1618  MatchCallback *Action) {
1619  Matchers.TemplateArgumentLoc.emplace_back(NodeMatch, Action);
1620  Matchers.AllCallbacks.insert(Action);
1621 }
1622 
1623 void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
1624  MatchCallback *Action) {
1625  Matchers.Attr.emplace_back(AttrMatch, Action);
1626  Matchers.AllCallbacks.insert(Action);
1627 }
1628 
1629 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1630  MatchCallback *Action) {
1631  if (NodeMatch.canConvertTo<Decl>()) {
1632  addMatcher(NodeMatch.convertTo<Decl>(), Action);
1633  return true;
1634  } else if (NodeMatch.canConvertTo<QualType>()) {
1635  addMatcher(NodeMatch.convertTo<QualType>(), Action);
1636  return true;
1637  } else if (NodeMatch.canConvertTo<Stmt>()) {
1638  addMatcher(NodeMatch.convertTo<Stmt>(), Action);
1639  return true;
1640  } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1641  addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1642  return true;
1643  } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1644  addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1645  return true;
1646  } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1647  addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
1648  return true;
1649  } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1650  addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1651  return true;
1652  } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1653  addMatcher(NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1654  return true;
1655  } else if (NodeMatch.canConvertTo<Attr>()) {
1656  addMatcher(NodeMatch.convertTo<Attr>(), Action);
1657  return true;
1658  }
1659  return false;
1660 }
1661 
1662 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1663  return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1664 }
1665 
1667  internal::MatchASTVisitor Visitor(&Matchers, Options);
1668  Visitor.set_active_ast_context(&Context);
1669  Visitor.match(Node);
1670 }
1671 
1673  internal::MatchASTVisitor Visitor(&Matchers, Options);
1674  internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
1675  Visitor.set_active_ast_context(&Context);
1676  Visitor.onStartOfTranslationUnit();
1677  Visitor.TraverseAST(Context);
1678  Visitor.onEndOfTranslationUnit();
1679 }
1680 
1682  MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1683  ParsingDone = NewParsingDone;
1684 }
1685 
1686 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1687 
1690  return llvm::None;
1691 }
1692 
1693 } // end namespace ast_matchers
1694 } // end namespace clang
clang::TraversalKind
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:38
clang::ast_matchers::StatementMatcher
internal::Matcher< Stmt > StatementMatcher
Definition: ASTMatchers.h:142
clang::ast_matchers::TypeLocMatcher
internal::Matcher< TypeLoc > TypeLocMatcher
Definition: ASTMatchers.h:144
clang::ast_matchers::MatchFinder::newASTConsumer
std::unique_ptr< clang::ASTConsumer > newASTConsumer()
Creates a clang ASTConsumer that finds all matches.
Definition: ASTMatchFinder.cpp:1662
clang::ast_matchers::MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback
virtual ~ParsingDoneTestCallback()
Definition: ASTMatchFinder.cpp:1556
clang::ast_matchers::NestedNameSpecifierLocMatcher
internal::Matcher< NestedNameSpecifierLoc > NestedNameSpecifierLocMatcher
Definition: ASTMatchers.h:146
Nodes
BoundNodesTreeBuilder Nodes
Definition: ASTMatchFinder.cpp:83
clang::RecursiveASTVisitor::TraverseConstructorInitializer
bool TraverseConstructorInitializer(CXXCtorInitializer *Init)
Recursively visit a constructor initializer.
Definition: RecursiveASTVisitor.h:935
Node0
llvm::PointerUnion< CMD_TYPES_0 > Node0
Definition: ASTMatchFinder.cpp:840
IMPL
#define IMPL(Index)
Definition: ASTMatchFinder.cpp:780
clang::RecursiveASTVisitor::TraverseType
bool TraverseType(QualType T)
Recursively visit a type, by dispatching to Traverse*Type() based on the argument's getTypeClass() pr...
Definition: RecursiveASTVisitor.h:699
INT_MAX
#define INT_MAX
Definition: limits.h:46
clang::DynTypedNode::create
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
Definition: ASTTypeTraits.h:253
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:737
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:55
clang::NestedNameSpecifier
Represents a C++ nested name specifier, such as "\::std::vector<int>::".
Definition: NestedNameSpecifier.h:50
clang::tooling::Filter
llvm::cl::opt< std::string > Filter
clang::ast_matchers::CXXCtorInitializerMatcher
internal::Matcher< CXXCtorInitializer > CXXCtorInitializerMatcher
Definition: ASTMatchers.h:148
clang::ast_matchers::MatchFinder::MatchFinderOptions
Definition: ASTMatchFinder.h:128
clang::ast_matchers::AttrMatcher
internal::Matcher< Attr > AttrMatcher
Definition: ASTMatchers.h:152
llvm::Optional
Definition: LLVM.h:40
llvm::SmallPtrSet
Definition: ASTContext.h:82
ASTMatchFinder.h
clang::ast_matchers::TypeMatcher
internal::Matcher< QualType > TypeMatcher
Definition: ASTMatchers.h:143
clang::RecursiveASTVisitor::TraverseStmt
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument's dy...
Definition: RecursiveASTVisitor.h:658
print
void print(llvm::raw_ostream &OS, const Pointer &P, ASTContext &Ctx, QualType Ty)
Definition: InterpFrame.cpp:63
clang::ast_matchers::traverse
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:815
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:627
clang::ast_matchers::TemplateArgumentLocMatcher
internal::Matcher< TemplateArgumentLoc > TemplateArgumentLocMatcher
Definition: ASTMatchers.h:150
clang::ast_matchers::MatchFinder::MatchCallback::getID
virtual StringRef getID() const
An id used to group the matchers.
Definition: ASTMatchFinder.cpp:1686
MatcherID
DynTypedMatcher::MatcherIDType MatcherID
Definition: ASTMatchFinder.cpp:67
clang::CodeGen::AlignmentSource::Decl
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
clang::ast_matchers::MatchFinder::MatchCallback::getCheckTraversalKind
virtual llvm::Optional< TraversalKind > getCheckTraversalKind() const
TraversalKind to use while matching and processing the result nodes.
Definition: ASTMatchFinder.cpp:1689
USHRT_MAX
#define USHRT_MAX
Definition: limits.h:55
clang::TSK_ExplicitInstantiationDeclaration
@ TSK_ExplicitInstantiationDeclaration
This template specialization was instantiated from a template due to an explicit instantiation declar...
Definition: Specifiers.h:190
V
#define V(N, I)
Definition: ASTContext.h:3233
clang::index::SymbolRole::Declaration
@ Declaration
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:68
Traversal
TraversalKind Traversal
Definition: ASTMatchFinder.cpp:70
clang::ast_matchers::MatchFinder::ParsingDoneTestCallback
Called when parsing is finished. Intended for testing only.
Definition: ASTMatchFinder.h:122
clang::RecursiveASTVisitor::TraverseNestedNameSpecifier
bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS)
Recursively visit a C++ nested-name-specifier.
Definition: RecursiveASTVisitor.h:765
MatchResult
MatchFinder::MatchResult MatchResult
Definition: RangeSelector.cpp:30
clang::interp::LE
bool LE(InterpState &S, CodePtr OpPC)
Definition: Interp.h:268
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
clang::ast_matchers::MatchFinder::registerTestCallbackAfterParsing
void registerTestCallbackAfterParsing(ParsingDoneTestCallback *ParsingDone)
Registers a callback to notify the end of parsing.
Definition: ASTMatchFinder.cpp:1681
clang::ast_matchers::MatchFinder::~MatchFinder
~MatchFinder()
Definition: ASTMatchFinder.cpp:1561
Depth
int Depth
Definition: ASTDiff.cpp:191
clang::RecursiveASTVisitor::TraverseAttr
bool TraverseAttr(Attr *At)
Recursively visit an attribute, by dispatching to Traverse*Attr() based on the argument's dynamic typ...
clang::RecursiveASTVisitor::TraverseTemplateArgumentLoc
bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc)
Recursively visit a template argument location and dispatch to the appropriate method for the argumen...
Definition: RecursiveASTVisitor.h:886
clang::ast_matchers::MatchFinder::MatchFinder
MatchFinder(MatchFinderOptions Options=MatchFinderOptions())
Definition: ASTMatchFinder.cpp:1558
clang::TemplateArgumentLoc
Location wrapper for a TemplateArgument.
Definition: TemplateBase.h:457
clang::diff::DynTypedNode
DynTypedNode DynTypedNode
Definition: ASTDiffInternal.h:18
ASTContext.h
clang::TSK_ExplicitInstantiationDefinition
@ TSK_ExplicitInstantiationDefinition
This template specialization was instantiated from a template due to an explicit instantiation defini...
Definition: Specifiers.h:194
llvm::DenseSet< const void * >
clang::RecursiveASTVisitor::dataTraverseNode
bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue)
Definition: RecursiveASTVisitor.h:557
clang::NestedNameSpecifierLoc
A C++ nested-name-specifier augmented with source location information.
Definition: NestedNameSpecifier.h:243
Base
BoundNodes
BoundNodesTreeBuilder BoundNodes
Definition: ASTMatchFinder.cpp:69
clang::ast_matchers::MatchFinder::match
void match(const T &Node, ASTContext &Context)
Calls the registered callbacks on all matches on the given Node.
Definition: ASTMatchFinder.h:193
clang::ast_matchers::MatchFinder::MatchCallback::~MatchCallback
virtual ~MatchCallback()
Definition: ASTMatchFinder.cpp:1555
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::ast_matchers::MatchFinder::addMatcher
void addMatcher(const DeclarationMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.
Definition: ASTMatchFinder.cpp:1563
Node1
llvm::PointerUnion< CMD_TYPES_1 > Node1
Definition: ASTMatchFinder.cpp:841
clang::TK_AsIs
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
clang::ast_matchers::MatchFinder::MatchResult::MatchResult
MatchResult(const BoundNodes &Nodes, clang::ASTContext *Context)
Definition: ASTMatchFinder.cpp:1550
clang::TypeLoc
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:58
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1139
ASTConsumer.h
clang::TK_IgnoreUnlessSpelledInSource
@ TK_IgnoreUnlessSpelledInSource
Ignore AST nodes not written in the source.
Definition: ASTTypeTraits.h:43
clang::ObjCPropertyAttribute::Kind
Kind
Definition: DeclObjCCommon.h:22
std
Definition: Format.h:4321
clang::ast_matchers::BoundNodes::IDToNodeMap
internal::BoundNodesMap::IDToNodeMap IDToNodeMap
Type of mapping from binding identifiers to bound nodes.
Definition: ASTMatchers.h:121
clang::interp::NE
bool NE(InterpState &S, CodePtr OpPC)
Definition: Interp.h:254
clang
Definition: CalledOnceCheck.h:17
RecursiveASTVisitor.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:70
ResultOfMatch
bool ResultOfMatch
Definition: ASTMatchFinder.cpp:82
clang::ast_matchers::match
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
Definition: ASTMatchFinder.h:312
clang::operator<
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Definition: DeclarationName.h:549
clang::Attr
Attr - This represents one attribute.
Definition: Attr.h:40
clang::RecursiveASTVisitor::TraverseDecl
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Definition: RecursiveASTVisitor.h:737
clang::ast_matchers::MatchFinder::addDynamicMatcher
bool addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.
Definition: ASTMatchFinder.cpp:1629
clang::ast_matchers::BoundNodes
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:107
clang::DynTypedNode
A dynamically typed AST node container.
Definition: ASTTypeTraits.h:249
clang::ast_matchers::NestedNameSpecifierMatcher
internal::Matcher< NestedNameSpecifier > NestedNameSpecifierMatcher
Definition: ASTMatchers.h:145
clang::ast_matchers::DeclarationMatcher
internal::Matcher< Decl > DeclarationMatcher
Types of matchers for the top-level classes in the AST class hierarchy.
Definition: ASTMatchers.h:141
Parent
NodeId Parent
Definition: ASTDiff.cpp:192
clang::CXXCtorInitializer
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2207
clang::ast_matchers::MatchFinder::MatchCallback
Called when the Match registered for it was successfully found in the AST.
Definition: ASTMatchFinder.h:91
clang::ast_matchers::MatchFinder::matchAST
void matchAST(ASTContext &Context)
Finds all matches in the given AST.
Definition: ASTMatchFinder.cpp:1672
clang::RecursiveASTVisitor::TraverseNestedNameSpecifierLoc
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)
Recursively visit a C++ nested-name-specifier with location information.
Definition: RecursiveASTVisitor.h:790
clang::RecursiveASTVisitor::TraverseTypeLoc
bool TraverseTypeLoc(TypeLoc TL)
Recursively visit a type with location, by dispatching to Traverse*TypeLoc() based on the argument ty...
Definition: RecursiveASTVisitor.h:716
clang::ento::ObjKind::OS
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
Type
MatchType Type
Definition: ASTMatchFinder.cpp:71