1 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Implements an algorithm to efficiently search for matches on AST nodes.
11 // Uses memoization to support recursive matches like HasDescendant.
12 //
13 // The general idea is to visit all AST nodes with a RecursiveASTVisitor,
14 // calling the Matches(...) method of each matcher we are running on each
15 // AST node. The matcher can recurse via the ASTMatchFinder interface.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "clang/ASTMatchers/ASTMatchFinder.h"
20 #include "clang/AST/ASTConsumer.h"
21 #include "clang/AST/ASTContext.h"
22 #include "clang/AST/RecursiveASTVisitor.h"
23 #include <deque>
24 #include <set>
25
26 namespace clang {
27 namespace ast_matchers {
28 namespace internal {
29 namespace {
30
31 typedef MatchFinder::MatchCallback MatchCallback;
32
33 // The maximum number of memoization entries to store.
34 // 10k has been experimentally found to give a good trade-off
35 // of performance vs. memory consumption by running matcher
36 // that match on every statement over a very large codebase.
37 //
38 // FIXME: Do some performance optimization in general and
39 // revisit this number; also, put up micro-benchmarks that we can
40 // optimize this on.
41 static const unsigned MaxMemoizationEntries = 10000;
42
43 // We use memoization to avoid running the same matcher on the same
44 // AST node twice. This struct is the key for looking up match
45 // result. It consists of an ID of the MatcherInterface (for
46 // identifying the matcher), a pointer to the AST node and the
47 // bound nodes before the matcher was executed.
48 //
49 // We currently only memoize on nodes whose pointers identify the
50 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
51 // For \c QualType and \c TypeLoc it is possible to implement
52 // generation of keys for each type.
53 // FIXME: Benchmark whether memoization of non-pointer typed nodes
54 // provides enough benefit for the additional amount of code.
55 struct MatchKey {
56 uint64_t MatcherID;
57 ast_type_traits::DynTypedNode Node;
58 BoundNodesTreeBuilder BoundNodes;
59
operator <clang::ast_matchers::internal::__anon101cc5e10111::MatchKey60 bool operator<(const MatchKey &Other) const {
61 if (MatcherID != Other.MatcherID)
62 return MatcherID < Other.MatcherID;
63 if (Node != Other.Node)
64 return Node < Other.Node;
65 return BoundNodes < Other.BoundNodes;
66 }
67 };
68
69 // Used to store the result of a match and possibly bound nodes.
70 struct MemoizedMatchResult {
71 bool ResultOfMatch;
72 BoundNodesTreeBuilder Nodes;
73 };
74
75 // A RecursiveASTVisitor that traverses all children or all descendants of
76 // a node.
77 class MatchChildASTVisitor
78 : public RecursiveASTVisitor<MatchChildASTVisitor> {
79 public:
80 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
81
82 // Creates an AST visitor that matches 'matcher' on all children or
83 // descendants of a traversed node. max_depth is the maximum depth
84 // to traverse: use 1 for matching the children and INT_MAX for
85 // matching the descendants.
MatchChildASTVisitor(const DynTypedMatcher * Matcher,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,int MaxDepth,ASTMatchFinder::TraversalKind Traversal,ASTMatchFinder::BindKind Bind)86 MatchChildASTVisitor(const DynTypedMatcher *Matcher,
87 ASTMatchFinder *Finder,
88 BoundNodesTreeBuilder *Builder,
89 int MaxDepth,
90 ASTMatchFinder::TraversalKind Traversal,
91 ASTMatchFinder::BindKind Bind)
92 : Matcher(Matcher),
93 Finder(Finder),
94 Builder(Builder),
95 CurrentDepth(0),
96 MaxDepth(MaxDepth),
97 Traversal(Traversal),
98 Bind(Bind),
99 Matches(false) {}
100
101 // Returns true if a match is found in the subtree rooted at the
102 // given AST node. This is done via a set of mutually recursive
103 // functions. Here's how the recursion is done (the *wildcard can
104 // actually be Decl, Stmt, or Type):
105 //
106 // - Traverse(node) calls BaseTraverse(node) when it needs
107 // to visit the descendants of node.
108 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
109 // Traverse*(c) for each child c of 'node'.
110 // - Traverse*(c) in turn calls Traverse(c), completing the
111 // recursion.
findMatch(const ast_type_traits::DynTypedNode & DynNode)112 bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
113 reset();
114 if (const Decl *D = DynNode.get<Decl>())
115 traverse(*D);
116 else if (const Stmt *S = DynNode.get<Stmt>())
117 traverse(*S);
118 else if (const NestedNameSpecifier *NNS =
119 DynNode.get<NestedNameSpecifier>())
120 traverse(*NNS);
121 else if (const NestedNameSpecifierLoc *NNSLoc =
122 DynNode.get<NestedNameSpecifierLoc>())
123 traverse(*NNSLoc);
124 else if (const QualType *Q = DynNode.get<QualType>())
125 traverse(*Q);
126 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
127 traverse(*T);
128 // FIXME: Add other base types after adding tests.
129
130 // It's OK to always overwrite the bound nodes, as if there was
131 // no match in this recursive branch, the result set is empty
132 // anyway.
133 *Builder = ResultBindings;
134
135 return Matches;
136 }
137
138 // The following are overriding methods from the base visitor class.
139 // They are public only to allow CRTP to work. They are *not *part
140 // of the public API of this class.
TraverseDecl(Decl * DeclNode)141 bool TraverseDecl(Decl *DeclNode) {
142 ScopedIncrement ScopedDepth(&CurrentDepth);
143 return (DeclNode == NULL) || traverse(*DeclNode);
144 }
TraverseStmt(Stmt * StmtNode)145 bool TraverseStmt(Stmt *StmtNode) {
146 ScopedIncrement ScopedDepth(&CurrentDepth);
147 const Stmt *StmtToTraverse = StmtNode;
148 if (Traversal ==
149 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
150 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
151 if (ExprNode != NULL) {
152 StmtToTraverse = ExprNode->IgnoreParenImpCasts();
153 }
154 }
155 return (StmtToTraverse == NULL) || traverse(*StmtToTraverse);
156 }
157 // We assume that the QualType and the contained type are on the same
158 // hierarchy level. Thus, we try to match either of them.
TraverseType(QualType TypeNode)159 bool TraverseType(QualType TypeNode) {
160 if (TypeNode.isNull())
161 return true;
162 ScopedIncrement ScopedDepth(&CurrentDepth);
163 // Match the Type.
164 if (!match(*TypeNode))
165 return false;
166 // The QualType is matched inside traverse.
167 return traverse(TypeNode);
168 }
169 // We assume that the TypeLoc, contained QualType and contained Type all are
170 // on the same hierarchy level. Thus, we try to match all of them.
TraverseTypeLoc(TypeLoc TypeLocNode)171 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
172 if (TypeLocNode.isNull())
173 return true;
174 ScopedIncrement ScopedDepth(&CurrentDepth);
175 // Match the Type.
176 if (!match(*TypeLocNode.getType()))
177 return false;
178 // Match the QualType.
179 if (!match(TypeLocNode.getType()))
180 return false;
181 // The TypeLoc is matched inside traverse.
182 return traverse(TypeLocNode);
183 }
TraverseNestedNameSpecifier(NestedNameSpecifier * NNS)184 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
185 ScopedIncrement ScopedDepth(&CurrentDepth);
186 return (NNS == NULL) || traverse(*NNS);
187 }
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)188 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
189 if (!NNS)
190 return true;
191 ScopedIncrement ScopedDepth(&CurrentDepth);
192 if (!match(*NNS.getNestedNameSpecifier()))
193 return false;
194 return traverse(NNS);
195 }
196
shouldVisitTemplateInstantiations() const197 bool shouldVisitTemplateInstantiations() const { return true; }
shouldVisitImplicitCode() const198 bool shouldVisitImplicitCode() const { return true; }
199 // Disables data recursion. We intercept Traverse* methods in the RAV, which
200 // are not triggered during data recursion.
shouldUseDataRecursionFor(clang::Stmt * S) const201 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
202
203 private:
204 // Used for updating the depth during traversal.
205 struct ScopedIncrement {
ScopedIncrementclang::ast_matchers::internal::__anon101cc5e10111::MatchChildASTVisitor::ScopedIncrement206 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
~ScopedIncrementclang::ast_matchers::internal::__anon101cc5e10111::MatchChildASTVisitor::ScopedIncrement207 ~ScopedIncrement() { --(*Depth); }
208
209 private:
210 int *Depth;
211 };
212
213 // Resets the state of this object.
reset()214 void reset() {
215 Matches = false;
216 CurrentDepth = 0;
217 }
218
219 // Forwards the call to the corresponding Traverse*() method in the
220 // base visitor class.
baseTraverse(const Decl & DeclNode)221 bool baseTraverse(const Decl &DeclNode) {
222 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
223 }
baseTraverse(const Stmt & StmtNode)224 bool baseTraverse(const Stmt &StmtNode) {
225 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
226 }
baseTraverse(QualType TypeNode)227 bool baseTraverse(QualType TypeNode) {
228 return VisitorBase::TraverseType(TypeNode);
229 }
baseTraverse(TypeLoc TypeLocNode)230 bool baseTraverse(TypeLoc TypeLocNode) {
231 return VisitorBase::TraverseTypeLoc(TypeLocNode);
232 }
baseTraverse(const NestedNameSpecifier & NNS)233 bool baseTraverse(const NestedNameSpecifier &NNS) {
234 return VisitorBase::TraverseNestedNameSpecifier(
235 const_cast<NestedNameSpecifier*>(&NNS));
236 }
baseTraverse(NestedNameSpecifierLoc NNS)237 bool baseTraverse(NestedNameSpecifierLoc NNS) {
238 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
239 }
240
241 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
242 // 0 < CurrentDepth <= MaxDepth.
243 //
244 // Returns 'true' if traversal should continue after this function
245 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
246 template <typename T>
match(const T & Node)247 bool match(const T &Node) {
248 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
249 return true;
250 }
251 if (Bind != ASTMatchFinder::BK_All) {
252 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
253 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
254 &RecursiveBuilder)) {
255 Matches = true;
256 ResultBindings.addMatch(RecursiveBuilder);
257 return false; // Abort as soon as a match is found.
258 }
259 } else {
260 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
261 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
262 &RecursiveBuilder)) {
263 // After the first match the matcher succeeds.
264 Matches = true;
265 ResultBindings.addMatch(RecursiveBuilder);
266 }
267 }
268 return true;
269 }
270
271 // Traverses the subtree rooted at 'Node'; returns true if the
272 // traversal should continue after this function returns.
273 template <typename T>
traverse(const T & Node)274 bool traverse(const T &Node) {
275 TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
276 traverse_can_only_be_instantiated_with_base_type);
277 if (!match(Node))
278 return false;
279 return baseTraverse(Node);
280 }
281
282 const DynTypedMatcher *const Matcher;
283 ASTMatchFinder *const Finder;
284 BoundNodesTreeBuilder *const Builder;
285 BoundNodesTreeBuilder ResultBindings;
286 int CurrentDepth;
287 const int MaxDepth;
288 const ASTMatchFinder::TraversalKind Traversal;
289 const ASTMatchFinder::BindKind Bind;
290 bool Matches;
291 };
292
293 // Controls the outermost traversal of the AST and allows to match multiple
294 // matchers.
295 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
296 public ASTMatchFinder {
297 public:
MatchASTVisitor(std::vector<std::pair<const internal::DynTypedMatcher *,MatchCallback * >> * MatcherCallbackPairs)298 MatchASTVisitor(std::vector<std::pair<const internal::DynTypedMatcher*,
299 MatchCallback*> > *MatcherCallbackPairs)
300 : MatcherCallbackPairs(MatcherCallbackPairs),
301 ActiveASTContext(NULL) {
302 }
303
onStartOfTranslationUnit()304 void onStartOfTranslationUnit() {
305 for (std::vector<std::pair<const internal::DynTypedMatcher*,
306 MatchCallback*> >::const_iterator
307 I = MatcherCallbackPairs->begin(), E = MatcherCallbackPairs->end();
308 I != E; ++I) {
309 I->second->onStartOfTranslationUnit();
310 }
311 }
312
onEndOfTranslationUnit()313 void onEndOfTranslationUnit() {
314 for (std::vector<std::pair<const internal::DynTypedMatcher*,
315 MatchCallback*> >::const_iterator
316 I = MatcherCallbackPairs->begin(), E = MatcherCallbackPairs->end();
317 I != E; ++I) {
318 I->second->onEndOfTranslationUnit();
319 }
320 }
321
set_active_ast_context(ASTContext * NewActiveASTContext)322 void set_active_ast_context(ASTContext *NewActiveASTContext) {
323 ActiveASTContext = NewActiveASTContext;
324 }
325
326 // The following Visit*() and Traverse*() functions "override"
327 // methods in RecursiveASTVisitor.
328
VisitTypedefNameDecl(TypedefNameDecl * DeclNode)329 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
330 // When we see 'typedef A B', we add name 'B' to the set of names
331 // A's canonical type maps to. This is necessary for implementing
332 // isDerivedFrom(x) properly, where x can be the name of the base
333 // class or any of its aliases.
334 //
335 // In general, the is-alias-of (as defined by typedefs) relation
336 // is tree-shaped, as you can typedef a type more than once. For
337 // example,
338 //
339 // typedef A B;
340 // typedef A C;
341 // typedef C D;
342 // typedef C E;
343 //
344 // gives you
345 //
346 // A
347 // |- B
348 // `- C
349 // |- D
350 // `- E
351 //
352 // It is wrong to assume that the relation is a chain. A correct
353 // implementation of isDerivedFrom() needs to recognize that B and
354 // E are aliases, even though neither is a typedef of the other.
355 // Therefore, we cannot simply walk through one typedef chain to
356 // find out whether the type name matches.
357 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
358 const Type *CanonicalType = // root of the typedef tree
359 ActiveASTContext->getCanonicalType(TypeNode);
360 TypeAliases[CanonicalType].insert(DeclNode);
361 return true;
362 }
363
364 bool TraverseDecl(Decl *DeclNode);
365 bool TraverseStmt(Stmt *StmtNode);
366 bool TraverseType(QualType TypeNode);
367 bool TraverseTypeLoc(TypeLoc TypeNode);
368 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
369 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
370
371 // Matches children or descendants of 'Node' with 'BaseMatcher'.
memoizedMatchesRecursively(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,int MaxDepth,TraversalKind Traversal,BindKind Bind)372 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
373 const DynTypedMatcher &Matcher,
374 BoundNodesTreeBuilder *Builder, int MaxDepth,
375 TraversalKind Traversal, BindKind Bind) {
376 // For AST-nodes that don't have an identity, we can't memoize.
377 if (!Node.getMemoizationData())
378 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
379 Bind);
380
381 MatchKey Key;
382 Key.MatcherID = Matcher.getID();
383 Key.Node = Node;
384 // Note that we key on the bindings *before* the match.
385 Key.BoundNodes = *Builder;
386
387 MemoizationMap::iterator I = ResultCache.find(Key);
388 if (I != ResultCache.end()) {
389 *Builder = I->second.Nodes;
390 return I->second.ResultOfMatch;
391 }
392
393 MemoizedMatchResult Result;
394 Result.Nodes = *Builder;
395 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
396 MaxDepth, Traversal, Bind);
397 ResultCache[Key] = Result;
398 *Builder = Result.Nodes;
399 return Result.ResultOfMatch;
400 }
401
402 // Matches children or descendants of 'Node' with 'BaseMatcher'.
matchesRecursively(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,int MaxDepth,TraversalKind Traversal,BindKind Bind)403 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
404 const DynTypedMatcher &Matcher,
405 BoundNodesTreeBuilder *Builder, int MaxDepth,
406 TraversalKind Traversal, BindKind Bind) {
407 MatchChildASTVisitor Visitor(
408 &Matcher, this, Builder, MaxDepth, Traversal, Bind);
409 return Visitor.findMatch(Node);
410 }
411
412 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
413 const Matcher<NamedDecl> &Base,
414 BoundNodesTreeBuilder *Builder);
415
416 // Implements ASTMatchFinder::matchesChildOf.
matchesChildOf(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,TraversalKind Traversal,BindKind Bind)417 virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
418 const DynTypedMatcher &Matcher,
419 BoundNodesTreeBuilder *Builder,
420 TraversalKind Traversal,
421 BindKind Bind) {
422 if (ResultCache.size() > MaxMemoizationEntries)
423 ResultCache.clear();
424 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
425 Bind);
426 }
427 // Implements ASTMatchFinder::matchesDescendantOf.
matchesDescendantOf(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,BindKind Bind)428 virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
429 const DynTypedMatcher &Matcher,
430 BoundNodesTreeBuilder *Builder,
431 BindKind Bind) {
432 if (ResultCache.size() > MaxMemoizationEntries)
433 ResultCache.clear();
434 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
435 TK_AsIs, Bind);
436 }
437 // Implements ASTMatchFinder::matchesAncestorOf.
matchesAncestorOf(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,AncestorMatchMode MatchMode)438 virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
439 const DynTypedMatcher &Matcher,
440 BoundNodesTreeBuilder *Builder,
441 AncestorMatchMode MatchMode) {
442 // Reset the cache outside of the recursive call to make sure we
443 // don't invalidate any iterators.
444 if (ResultCache.size() > MaxMemoizationEntries)
445 ResultCache.clear();
446 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
447 MatchMode);
448 }
449
450 // Matches all registered matchers on the given node and calls the
451 // result callback for every node that matches.
match(const ast_type_traits::DynTypedNode & Node)452 void match(const ast_type_traits::DynTypedNode& Node) {
453 for (std::vector<std::pair<const internal::DynTypedMatcher*,
454 MatchCallback*> >::const_iterator
455 I = MatcherCallbackPairs->begin(), E = MatcherCallbackPairs->end();
456 I != E; ++I) {
457 BoundNodesTreeBuilder Builder;
458 if (I->first->matches(Node, this, &Builder)) {
459 MatchVisitor Visitor(ActiveASTContext, I->second);
460 Builder.visitMatches(&Visitor);
461 }
462 }
463 }
464
match(const T & Node)465 template <typename T> void match(const T &Node) {
466 match(ast_type_traits::DynTypedNode::create(Node));
467 }
468
469 // Implements ASTMatchFinder::getASTContext.
getASTContext() const470 virtual ASTContext &getASTContext() const { return *ActiveASTContext; }
471
shouldVisitTemplateInstantiations() const472 bool shouldVisitTemplateInstantiations() const { return true; }
shouldVisitImplicitCode() const473 bool shouldVisitImplicitCode() const { return true; }
474 // Disables data recursion. We intercept Traverse* methods in the RAV, which
475 // are not triggered during data recursion.
shouldUseDataRecursionFor(clang::Stmt * S) const476 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
477
478 private:
479 // Returns whether an ancestor of \p Node matches \p Matcher.
480 //
481 // The order of matching ((which can lead to different nodes being bound in
482 // case there are multiple matches) is breadth first search.
483 //
484 // To allow memoization in the very common case of having deeply nested
485 // expressions inside a template function, we first walk up the AST, memoizing
486 // the result of the match along the way, as long as there is only a single
487 // parent.
488 //
489 // Once there are multiple parents, the breadth first search order does not
490 // allow simple memoization on the ancestors. Thus, we only memoize as long
491 // as there is a single parent.
memoizedMatchesAncestorOfRecursively(const ast_type_traits::DynTypedNode & Node,const DynTypedMatcher & Matcher,BoundNodesTreeBuilder * Builder,AncestorMatchMode MatchMode)492 bool memoizedMatchesAncestorOfRecursively(
493 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
494 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
495 if (Node.get<TranslationUnitDecl>() ==
496 ActiveASTContext->getTranslationUnitDecl())
497 return false;
498 assert(Node.getMemoizationData() &&
499 "Invariant broken: only nodes that support memoization may be "
500 "used in the parent map.");
501 ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
502 if (Parents.empty()) {
503 assert(false && "Found node that is not in the parent map.");
504 return false;
505 }
506 MatchKey Key;
507 Key.MatcherID = Matcher.getID();
508 Key.Node = Node;
509 Key.BoundNodes = *Builder;
510
511 // Note that we cannot use insert and reuse the iterator, as recursive
512 // calls to match might invalidate the result cache iterators.
513 MemoizationMap::iterator I = ResultCache.find(Key);
514 if (I != ResultCache.end()) {
515 *Builder = I->second.Nodes;
516 return I->second.ResultOfMatch;
517 }
518 MemoizedMatchResult Result;
519 Result.ResultOfMatch = false;
520 Result.Nodes = *Builder;
521 if (Parents.size() == 1) {
522 // Only one parent - do recursive memoization.
523 const ast_type_traits::DynTypedNode Parent = Parents[0];
524 if (Matcher.matches(Parent, this, &Result.Nodes)) {
525 Result.ResultOfMatch = true;
526 } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
527 // Reset the results to not include the bound nodes from the failed
528 // match above.
529 Result.Nodes = *Builder;
530 Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
531 Parent, Matcher, &Result.Nodes, MatchMode);
532 // Once we get back from the recursive call, the result will be the
533 // same as the parent's result.
534 }
535 } else {
536 // Multiple parents - BFS over the rest of the nodes.
537 llvm::DenseSet<const void *> Visited;
538 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
539 Parents.end());
540 while (!Queue.empty()) {
541 Result.Nodes = *Builder;
542 if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
543 Result.ResultOfMatch = true;
544 break;
545 }
546 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
547 ASTContext::ParentVector Ancestors =
548 ActiveASTContext->getParents(Queue.front());
549 for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(),
550 E = Ancestors.end();
551 I != E; ++I) {
552 // Make sure we do not visit the same node twice.
553 // Otherwise, we'll visit the common ancestors as often as there
554 // are splits on the way down.
555 if (Visited.insert(I->getMemoizationData()).second)
556 Queue.push_back(*I);
557 }
558 }
559 Queue.pop_front();
560 }
561 }
562 ResultCache[Key] = Result;
563
564 *Builder = Result.Nodes;
565 return Result.ResultOfMatch;
566 }
567
568 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
569 // the aggregated bound nodes for each match.
570 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
571 public:
MatchVisitor(ASTContext * Context,MatchFinder::MatchCallback * Callback)572 MatchVisitor(ASTContext* Context,
573 MatchFinder::MatchCallback* Callback)
574 : Context(Context),
575 Callback(Callback) {}
576
visitMatch(const BoundNodes & BoundNodesView)577 virtual void visitMatch(const BoundNodes& BoundNodesView) {
578 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
579 }
580
581 private:
582 ASTContext* Context;
583 MatchFinder::MatchCallback* Callback;
584 };
585
586 // Returns true if 'TypeNode' has an alias that matches the given matcher.
typeHasMatchingAlias(const Type * TypeNode,const Matcher<NamedDecl> Matcher,BoundNodesTreeBuilder * Builder)587 bool typeHasMatchingAlias(const Type *TypeNode,
588 const Matcher<NamedDecl> Matcher,
589 BoundNodesTreeBuilder *Builder) {
590 const Type *const CanonicalType =
591 ActiveASTContext->getCanonicalType(TypeNode);
592 const std::set<const TypedefNameDecl *> &Aliases =
593 TypeAliases[CanonicalType];
594 for (std::set<const TypedefNameDecl*>::const_iterator
595 It = Aliases.begin(), End = Aliases.end();
596 It != End; ++It) {
597 BoundNodesTreeBuilder Result(*Builder);
598 if (Matcher.matches(**It, this, &Result)) {
599 *Builder = Result;
600 return true;
601 }
602 }
603 return false;
604 }
605
606 std::vector<std::pair<const internal::DynTypedMatcher*,
607 MatchCallback*> > *const MatcherCallbackPairs;
608 ASTContext *ActiveASTContext;
609
610 // Maps a canonical type to its TypedefDecls.
611 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
612
613 // Maps (matcher, node) -> the match result for memoization.
614 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
615 MemoizationMap ResultCache;
616 };
617
getAsCXXRecordDecl(const Type * TypeNode)618 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
619 // Type::getAs<...>() drills through typedefs.
620 if (TypeNode->getAs<DependentNameType>() != NULL ||
621 TypeNode->getAs<DependentTemplateSpecializationType>() != NULL ||
622 TypeNode->getAs<TemplateTypeParmType>() != NULL)
623 // Dependent names and template TypeNode parameters will be matched when
624 // the template is instantiated.
625 return NULL;
626 TemplateSpecializationType const *TemplateType =
627 TypeNode->getAs<TemplateSpecializationType>();
628 if (TemplateType == NULL) {
629 return TypeNode->getAsCXXRecordDecl();
630 }
631 if (TemplateType->getTemplateName().isDependent())
632 // Dependent template specializations will be matched when the
633 // template is instantiated.
634 return NULL;
635
636 // For template specialization types which are specializing a template
637 // declaration which is an explicit or partial specialization of another
638 // template declaration, getAsCXXRecordDecl() returns the corresponding
639 // ClassTemplateSpecializationDecl.
640 //
641 // For template specialization types which are specializing a template
642 // declaration which is neither an explicit nor partial specialization of
643 // another template declaration, getAsCXXRecordDecl() returns NULL and
644 // we get the CXXRecordDecl of the templated declaration.
645 CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
646 if (SpecializationDecl != NULL) {
647 return SpecializationDecl;
648 }
649 NamedDecl *Templated =
650 TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
651 if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
652 return TemplatedRecord;
653 }
654 // Now it can still be that we have an alias template.
655 TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
656 assert(AliasDecl);
657 return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
658 }
659
660 // Returns true if the given class is directly or indirectly derived
661 // from a base type with the given name. A class is not considered to be
662 // derived from itself.
classIsDerivedFrom(const CXXRecordDecl * Declaration,const Matcher<NamedDecl> & Base,BoundNodesTreeBuilder * Builder)663 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
664 const Matcher<NamedDecl> &Base,
665 BoundNodesTreeBuilder *Builder) {
666 if (!Declaration->hasDefinition())
667 return false;
668 typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
669 for (BaseIterator It = Declaration->bases_begin(),
670 End = Declaration->bases_end();
671 It != End; ++It) {
672 const Type *TypeNode = It->getType().getTypePtr();
673
674 if (typeHasMatchingAlias(TypeNode, Base, Builder))
675 return true;
676
677 CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
678 if (ClassDecl == NULL)
679 continue;
680 if (ClassDecl == Declaration) {
681 // This can happen for recursive template definitions; if the
682 // current declaration did not match, we can safely return false.
683 return false;
684 }
685 BoundNodesTreeBuilder Result(*Builder);
686 if (Base.matches(*ClassDecl, this, &Result)) {
687 *Builder = Result;
688 return true;
689 }
690 if (classIsDerivedFrom(ClassDecl, Base, Builder))
691 return true;
692 }
693 return false;
694 }
695
TraverseDecl(Decl * DeclNode)696 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
697 if (DeclNode == NULL) {
698 return true;
699 }
700 match(*DeclNode);
701 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
702 }
703
TraverseStmt(Stmt * StmtNode)704 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
705 if (StmtNode == NULL) {
706 return true;
707 }
708 match(*StmtNode);
709 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
710 }
711
TraverseType(QualType TypeNode)712 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
713 match(TypeNode);
714 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
715 }
716
TraverseTypeLoc(TypeLoc TypeLocNode)717 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
718 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
719 // We still want to find those types via matchers, so we match them here. Note
720 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
721 // type, so we visit all involved parts of a compound type when matching on
722 // each TypeLoc.
723 match(TypeLocNode);
724 match(TypeLocNode.getType());
725 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
726 }
727
TraverseNestedNameSpecifier(NestedNameSpecifier * NNS)728 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
729 match(*NNS);
730 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
731 }
732
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)733 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
734 NestedNameSpecifierLoc NNS) {
735 match(NNS);
736 // We only match the nested name specifier here (as opposed to traversing it)
737 // because the traversal is already done in the parallel "Loc"-hierarchy.
738 match(*NNS.getNestedNameSpecifier());
739 return
740 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
741 }
742
743 class MatchASTConsumer : public ASTConsumer {
744 public:
MatchASTConsumer(std::vector<std::pair<const internal::DynTypedMatcher *,MatchCallback * >> * MatcherCallbackPairs,MatchFinder::ParsingDoneTestCallback * ParsingDone)745 MatchASTConsumer(
746 std::vector<std::pair<const internal::DynTypedMatcher*,
747 MatchCallback*> > *MatcherCallbackPairs,
748 MatchFinder::ParsingDoneTestCallback *ParsingDone)
749 : Visitor(MatcherCallbackPairs),
750 ParsingDone(ParsingDone) {}
751
752 private:
HandleTranslationUnit(ASTContext & Context)753 virtual void HandleTranslationUnit(ASTContext &Context) {
754 if (ParsingDone != NULL) {
755 ParsingDone->run();
756 }
757 Visitor.set_active_ast_context(&Context);
758 Visitor.onStartOfTranslationUnit();
759 Visitor.TraverseDecl(Context.getTranslationUnitDecl());
760 Visitor.onEndOfTranslationUnit();
761 Visitor.set_active_ast_context(NULL);
762 }
763
764 MatchASTVisitor Visitor;
765 MatchFinder::ParsingDoneTestCallback *ParsingDone;
766 };
767
768 } // end namespace
769 } // end namespace internal
770
MatchResult(const BoundNodes & Nodes,ASTContext * Context)771 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
772 ASTContext *Context)
773 : Nodes(Nodes), Context(Context),
774 SourceManager(&Context->getSourceManager()) {}
775
~MatchCallback()776 MatchFinder::MatchCallback::~MatchCallback() {}
~ParsingDoneTestCallback()777 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
778
MatchFinder()779 MatchFinder::MatchFinder() : ParsingDone(NULL) {}
780
~MatchFinder()781 MatchFinder::~MatchFinder() {
782 for (std::vector<std::pair<const internal::DynTypedMatcher*,
783 MatchCallback*> >::const_iterator
784 It = MatcherCallbackPairs.begin(), End = MatcherCallbackPairs.end();
785 It != End; ++It) {
786 delete It->first;
787 }
788 }
789
addMatcher(const DeclarationMatcher & NodeMatch,MatchCallback * Action)790 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
791 MatchCallback *Action) {
792 MatcherCallbackPairs.push_back(std::make_pair(
793 new internal::Matcher<Decl>(NodeMatch), Action));
794 }
795
addMatcher(const TypeMatcher & NodeMatch,MatchCallback * Action)796 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
797 MatchCallback *Action) {
798 MatcherCallbackPairs.push_back(std::make_pair(
799 new internal::Matcher<QualType>(NodeMatch), Action));
800 }
801
addMatcher(const StatementMatcher & NodeMatch,MatchCallback * Action)802 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
803 MatchCallback *Action) {
804 MatcherCallbackPairs.push_back(std::make_pair(
805 new internal::Matcher<Stmt>(NodeMatch), Action));
806 }
807
addMatcher(const NestedNameSpecifierMatcher & NodeMatch,MatchCallback * Action)808 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
809 MatchCallback *Action) {
810 MatcherCallbackPairs.push_back(std::make_pair(
811 new NestedNameSpecifierMatcher(NodeMatch), Action));
812 }
813
addMatcher(const NestedNameSpecifierLocMatcher & NodeMatch,MatchCallback * Action)814 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
815 MatchCallback *Action) {
816 MatcherCallbackPairs.push_back(std::make_pair(
817 new NestedNameSpecifierLocMatcher(NodeMatch), Action));
818 }
819
addMatcher(const TypeLocMatcher & NodeMatch,MatchCallback * Action)820 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
821 MatchCallback *Action) {
822 MatcherCallbackPairs.push_back(std::make_pair(
823 new TypeLocMatcher(NodeMatch), Action));
824 }
825
newASTConsumer()826 ASTConsumer *MatchFinder::newASTConsumer() {
827 return new internal::MatchASTConsumer(&MatcherCallbackPairs, ParsingDone);
828 }
829
match(const clang::ast_type_traits::DynTypedNode & Node,ASTContext & Context)830 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
831 ASTContext &Context) {
832 internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
833 Visitor.set_active_ast_context(&Context);
834 Visitor.match(Node);
835 }
836
registerTestCallbackAfterParsing(MatchFinder::ParsingDoneTestCallback * NewParsingDone)837 void MatchFinder::registerTestCallbackAfterParsing(
838 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
839 ParsingDone = NewParsingDone;
840 }
841
842 } // end namespace ast_matchers
843 } // end namespace clang
844