blob: b081f5426eaeae2fdd7a8ae190c9a5c4279f501f [file] [log] [blame]
Manuel Klimek4da21662012-07-06 05:48:52 +00001//===--- 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 <set>
24
25namespace clang {
26namespace ast_matchers {
27namespace internal {
28namespace {
29
Manuel Klimeka78d0d62012-09-05 12:12:07 +000030typedef MatchFinder::MatchCallback MatchCallback;
31
Manuel Klimek579b1202012-09-07 09:26:10 +000032/// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
33/// parents as defined by the \c RecursiveASTVisitor.
34///
35/// Note that the relationship described here is purely in terms of AST
36/// traversal - there are other relationships (for example declaration context)
37/// in the AST that are better modeled by special matchers.
38///
39/// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes.
40class ParentMapASTVisitor : public RecursiveASTVisitor<ParentMapASTVisitor> {
41public:
42 /// \brief Maps from a node to its parent.
43 typedef llvm::DenseMap<const void*, ast_type_traits::DynTypedNode> ParentMap;
44
45 /// \brief Builds and returns the translation unit's parent map.
46 ///
47 /// The caller takes ownership of the returned \c ParentMap.
48 static ParentMap *buildMap(TranslationUnitDecl &TU) {
49 ParentMapASTVisitor Visitor(new ParentMap);
50 Visitor.TraverseDecl(&TU);
51 return Visitor.Parents;
52 }
53
54private:
55 typedef RecursiveASTVisitor<ParentMapASTVisitor> VisitorBase;
56
57 ParentMapASTVisitor(ParentMap *Parents) : Parents(Parents) {}
58
59 bool shouldVisitTemplateInstantiations() const { return true; }
60 bool shouldVisitImplicitCode() const { return true; }
61
62 template <typename T>
63 bool TraverseNode(T *Node, bool (VisitorBase::*traverse)(T*)) {
64 if (Node == NULL)
65 return true;
66 if (ParentStack.size() > 0)
67 (*Parents)[Node] = ParentStack.back();
68 ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node));
69 bool Result = (this->*traverse)(Node);
70 ParentStack.pop_back();
71 return Result;
72 }
73
74 bool TraverseDecl(Decl *DeclNode) {
75 return TraverseNode(DeclNode, &VisitorBase::TraverseDecl);
76 }
77
78 bool TraverseStmt(Stmt *StmtNode) {
79 return TraverseNode(StmtNode, &VisitorBase::TraverseStmt);
80 }
81
82 ParentMap *Parents;
83 llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
84
85 friend class RecursiveASTVisitor<ParentMapASTVisitor>;
86};
87
Manuel Klimek4da21662012-07-06 05:48:52 +000088// We use memoization to avoid running the same matcher on the same
89// AST node twice. This pair is the key for looking up match
90// result. It consists of an ID of the MatcherInterface (for
91// identifying the matcher) and a pointer to the AST node.
Manuel Klimeka78d0d62012-09-05 12:12:07 +000092//
93// We currently only memoize on nodes whose pointers identify the
94// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
95// For \c QualType and \c TypeLoc it is possible to implement
96// generation of keys for each type.
97// FIXME: Benchmark whether memoization of non-pointer typed nodes
98// provides enough benefit for the additional amount of code.
Manuel Klimek4da21662012-07-06 05:48:52 +000099typedef std::pair<uint64_t, const void*> UntypedMatchInput;
100
101// Used to store the result of a match and possibly bound nodes.
102struct MemoizedMatchResult {
103 bool ResultOfMatch;
104 BoundNodesTree Nodes;
105};
106
107// A RecursiveASTVisitor that traverses all children or all descendants of
108// a node.
109class MatchChildASTVisitor
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000110 : public RecursiveASTVisitor<MatchChildASTVisitor> {
Manuel Klimek4da21662012-07-06 05:48:52 +0000111public:
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000112 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
Manuel Klimek4da21662012-07-06 05:48:52 +0000113
114 // Creates an AST visitor that matches 'matcher' on all children or
115 // descendants of a traversed node. max_depth is the maximum depth
116 // to traverse: use 1 for matching the children and INT_MAX for
117 // matching the descendants.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000118 MatchChildASTVisitor(const DynTypedMatcher *Matcher,
Manuel Klimek4da21662012-07-06 05:48:52 +0000119 ASTMatchFinder *Finder,
120 BoundNodesTreeBuilder *Builder,
121 int MaxDepth,
122 ASTMatchFinder::TraversalKind Traversal,
123 ASTMatchFinder::BindKind Bind)
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000124 : Matcher(Matcher),
Manuel Klimek4da21662012-07-06 05:48:52 +0000125 Finder(Finder),
126 Builder(Builder),
Daniel Jaspera267cf62012-10-29 10:14:44 +0000127 CurrentDepth(0),
Manuel Klimek4da21662012-07-06 05:48:52 +0000128 MaxDepth(MaxDepth),
129 Traversal(Traversal),
130 Bind(Bind),
131 Matches(false) {}
132
133 // Returns true if a match is found in the subtree rooted at the
134 // given AST node. This is done via a set of mutually recursive
135 // functions. Here's how the recursion is done (the *wildcard can
136 // actually be Decl, Stmt, or Type):
137 //
138 // - Traverse(node) calls BaseTraverse(node) when it needs
139 // to visit the descendants of node.
140 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
141 // Traverse*(c) for each child c of 'node'.
142 // - Traverse*(c) in turn calls Traverse(c), completing the
143 // recursion.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000144 bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000145 reset();
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000146 if (const Decl *D = DynNode.get<Decl>())
147 traverse(*D);
148 else if (const Stmt *S = DynNode.get<Stmt>())
149 traverse(*S);
Daniel Jasperd1ce3c12012-10-30 15:42:00 +0000150 else if (const NestedNameSpecifier *NNS =
151 DynNode.get<NestedNameSpecifier>())
152 traverse(*NNS);
153 else if (const NestedNameSpecifierLoc *NNSLoc =
154 DynNode.get<NestedNameSpecifierLoc>())
155 traverse(*NNSLoc);
Daniel Jaspera267cf62012-10-29 10:14:44 +0000156 else if (const QualType *Q = DynNode.get<QualType>())
157 traverse(*Q);
158 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
159 traverse(*T);
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000160 // FIXME: Add other base types after adding tests.
Manuel Klimek4da21662012-07-06 05:48:52 +0000161 return Matches;
162 }
163
164 // The following are overriding methods from the base visitor class.
165 // They are public only to allow CRTP to work. They are *not *part
166 // of the public API of this class.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000167 bool TraverseDecl(Decl *DeclNode) {
Daniel Jaspera267cf62012-10-29 10:14:44 +0000168 ScopedIncrement ScopedDepth(&CurrentDepth);
Manuel Klimek4da21662012-07-06 05:48:52 +0000169 return (DeclNode == NULL) || traverse(*DeclNode);
170 }
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000171 bool TraverseStmt(Stmt *StmtNode) {
Daniel Jaspera267cf62012-10-29 10:14:44 +0000172 ScopedIncrement ScopedDepth(&CurrentDepth);
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000173 const Stmt *StmtToTraverse = StmtNode;
Manuel Klimek4da21662012-07-06 05:48:52 +0000174 if (Traversal ==
175 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000176 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000177 if (ExprNode != NULL) {
178 StmtToTraverse = ExprNode->IgnoreParenImpCasts();
179 }
180 }
181 return (StmtToTraverse == NULL) || traverse(*StmtToTraverse);
182 }
Daniel Jaspera267cf62012-10-29 10:14:44 +0000183 // We assume that the QualType and the contained type are on the same
184 // hierarchy level. Thus, we try to match either of them.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000185 bool TraverseType(QualType TypeNode) {
Daniel Jaspera267cf62012-10-29 10:14:44 +0000186 ScopedIncrement ScopedDepth(&CurrentDepth);
187 // Match the Type.
188 if (!match(*TypeNode))
189 return false;
190 // The QualType is matched inside traverse.
Manuel Klimek4da21662012-07-06 05:48:52 +0000191 return traverse(TypeNode);
192 }
Daniel Jaspera267cf62012-10-29 10:14:44 +0000193 // We assume that the TypeLoc, contained QualType and contained Type all are
194 // on the same hierarchy level. Thus, we try to match all of them.
195 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
196 ScopedIncrement ScopedDepth(&CurrentDepth);
197 // Match the Type.
198 if (!match(*TypeLocNode.getType()))
199 return false;
200 // Match the QualType.
201 if (!match(TypeLocNode.getType()))
202 return false;
203 // The TypeLoc is matched inside traverse.
204 return traverse(TypeLocNode);
205 }
Daniel Jasperd1ce3c12012-10-30 15:42:00 +0000206 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
207 ScopedIncrement ScopedDepth(&CurrentDepth);
208 return (NNS == NULL) || traverse(*NNS);
209 }
210 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
211 ScopedIncrement ScopedDepth(&CurrentDepth);
212 if (!match(*NNS.getNestedNameSpecifier()))
213 return false;
214 return !NNS || traverse(NNS);
215 }
Manuel Klimek4da21662012-07-06 05:48:52 +0000216
217 bool shouldVisitTemplateInstantiations() const { return true; }
218 bool shouldVisitImplicitCode() const { return true; }
219
220private:
221 // Used for updating the depth during traversal.
222 struct ScopedIncrement {
223 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
224 ~ScopedIncrement() { --(*Depth); }
225
226 private:
227 int *Depth;
228 };
229
230 // Resets the state of this object.
231 void reset() {
232 Matches = false;
Daniel Jaspera267cf62012-10-29 10:14:44 +0000233 CurrentDepth = 0;
Manuel Klimek4da21662012-07-06 05:48:52 +0000234 }
235
236 // Forwards the call to the corresponding Traverse*() method in the
237 // base visitor class.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000238 bool baseTraverse(const Decl &DeclNode) {
239 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
Manuel Klimek4da21662012-07-06 05:48:52 +0000240 }
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000241 bool baseTraverse(const Stmt &StmtNode) {
242 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
Manuel Klimek4da21662012-07-06 05:48:52 +0000243 }
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000244 bool baseTraverse(QualType TypeNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000245 return VisitorBase::TraverseType(TypeNode);
246 }
Daniel Jaspera267cf62012-10-29 10:14:44 +0000247 bool baseTraverse(TypeLoc TypeLocNode) {
248 return VisitorBase::TraverseTypeLoc(TypeLocNode);
249 }
Daniel Jasperd1ce3c12012-10-30 15:42:00 +0000250 bool baseTraverse(const NestedNameSpecifier &NNS) {
251 return VisitorBase::TraverseNestedNameSpecifier(
252 const_cast<NestedNameSpecifier*>(&NNS));
253 }
254 bool baseTraverse(NestedNameSpecifierLoc NNS) {
255 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
256 }
Manuel Klimek4da21662012-07-06 05:48:52 +0000257
Daniel Jaspera267cf62012-10-29 10:14:44 +0000258 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
259 // 0 < CurrentDepth <= MaxDepth.
260 //
261 // Returns 'true' if traversal should continue after this function
262 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
Manuel Klimek4da21662012-07-06 05:48:52 +0000263 template <typename T>
Daniel Jaspera267cf62012-10-29 10:14:44 +0000264 bool match(const T &Node) {
265 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
266 return true;
Manuel Klimek4da21662012-07-06 05:48:52 +0000267 }
268 if (Bind != ASTMatchFinder::BK_All) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000269 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node),
270 Finder, Builder)) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000271 Matches = true;
272 return false; // Abort as soon as a match is found.
273 }
Manuel Klimek4da21662012-07-06 05:48:52 +0000274 } else {
275 BoundNodesTreeBuilder RecursiveBuilder;
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000276 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node),
277 Finder, &RecursiveBuilder)) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000278 // After the first match the matcher succeeds.
279 Matches = true;
280 Builder->addMatch(RecursiveBuilder.build());
281 }
Manuel Klimek4da21662012-07-06 05:48:52 +0000282 }
Daniel Jaspera267cf62012-10-29 10:14:44 +0000283 return true;
284 }
285
286 // Traverses the subtree rooted at 'Node'; returns true if the
287 // traversal should continue after this function returns.
288 template <typename T>
289 bool traverse(const T &Node) {
290 TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
291 traverse_can_only_be_instantiated_with_base_type);
292 if (!match(Node))
293 return false;
294 return baseTraverse(Node);
Manuel Klimek4da21662012-07-06 05:48:52 +0000295 }
296
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000297 const DynTypedMatcher *const Matcher;
Manuel Klimek4da21662012-07-06 05:48:52 +0000298 ASTMatchFinder *const Finder;
299 BoundNodesTreeBuilder *const Builder;
300 int CurrentDepth;
301 const int MaxDepth;
302 const ASTMatchFinder::TraversalKind Traversal;
303 const ASTMatchFinder::BindKind Bind;
304 bool Matches;
305};
306
307// Controls the outermost traversal of the AST and allows to match multiple
308// matchers.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000309class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
Manuel Klimek4da21662012-07-06 05:48:52 +0000310 public ASTMatchFinder {
311public:
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000312 MatchASTVisitor(std::vector<std::pair<const internal::DynTypedMatcher*,
313 MatchCallback*> > *MatcherCallbackPairs)
314 : MatcherCallbackPairs(MatcherCallbackPairs),
Manuel Klimek4da21662012-07-06 05:48:52 +0000315 ActiveASTContext(NULL) {
316 }
317
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000318 void set_active_ast_context(ASTContext *NewActiveASTContext) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000319 ActiveASTContext = NewActiveASTContext;
320 }
321
322 // The following Visit*() and Traverse*() functions "override"
323 // methods in RecursiveASTVisitor.
324
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000325 bool VisitTypedefDecl(TypedefDecl *DeclNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000326 // When we see 'typedef A B', we add name 'B' to the set of names
327 // A's canonical type maps to. This is necessary for implementing
Daniel Jasper76dafa72012-09-07 12:48:17 +0000328 // isDerivedFrom(x) properly, where x can be the name of the base
Manuel Klimek4da21662012-07-06 05:48:52 +0000329 // class or any of its aliases.
330 //
331 // In general, the is-alias-of (as defined by typedefs) relation
332 // is tree-shaped, as you can typedef a type more than once. For
333 // example,
334 //
335 // typedef A B;
336 // typedef A C;
337 // typedef C D;
338 // typedef C E;
339 //
340 // gives you
341 //
342 // A
343 // |- B
344 // `- C
345 // |- D
346 // `- E
347 //
348 // It is wrong to assume that the relation is a chain. A correct
Daniel Jasper76dafa72012-09-07 12:48:17 +0000349 // implementation of isDerivedFrom() needs to recognize that B and
Manuel Klimek4da21662012-07-06 05:48:52 +0000350 // E are aliases, even though neither is a typedef of the other.
351 // Therefore, we cannot simply walk through one typedef chain to
352 // find out whether the type name matches.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000353 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
354 const Type *CanonicalType = // root of the typedef tree
Manuel Klimek4da21662012-07-06 05:48:52 +0000355 ActiveASTContext->getCanonicalType(TypeNode);
Daniel Jasper20b802d2012-07-17 07:39:27 +0000356 TypeAliases[CanonicalType].insert(DeclNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000357 return true;
358 }
359
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000360 bool TraverseDecl(Decl *DeclNode);
361 bool TraverseStmt(Stmt *StmtNode);
362 bool TraverseType(QualType TypeNode);
363 bool TraverseTypeLoc(TypeLoc TypeNode);
Daniel Jaspera7564432012-09-13 13:11:25 +0000364 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
365 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
Manuel Klimek4da21662012-07-06 05:48:52 +0000366
367 // Matches children or descendants of 'Node' with 'BaseMatcher'.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000368 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
369 const DynTypedMatcher &Matcher,
Manuel Klimek4da21662012-07-06 05:48:52 +0000370 BoundNodesTreeBuilder *Builder, int MaxDepth,
371 TraversalKind Traversal, BindKind Bind) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000372 const UntypedMatchInput input(Matcher.getID(), Node.getMemoizationData());
Daniel Jaspera267cf62012-10-29 10:14:44 +0000373
374 // For AST-nodes that don't have an identity, we can't memoize.
375 if (!input.second)
376 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
377 Bind);
378
Manuel Klimek4da21662012-07-06 05:48:52 +0000379 std::pair<MemoizationMap::iterator, bool> InsertResult
380 = ResultCache.insert(std::make_pair(input, MemoizedMatchResult()));
381 if (InsertResult.second) {
382 BoundNodesTreeBuilder DescendantBoundNodesBuilder;
383 InsertResult.first->second.ResultOfMatch =
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000384 matchesRecursively(Node, Matcher, &DescendantBoundNodesBuilder,
Manuel Klimek4da21662012-07-06 05:48:52 +0000385 MaxDepth, Traversal, Bind);
386 InsertResult.first->second.Nodes =
387 DescendantBoundNodesBuilder.build();
388 }
389 InsertResult.first->second.Nodes.copyTo(Builder);
390 return InsertResult.first->second.ResultOfMatch;
391 }
392
393 // Matches children or descendants of 'Node' with 'BaseMatcher'.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000394 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
395 const DynTypedMatcher &Matcher,
Manuel Klimek4da21662012-07-06 05:48:52 +0000396 BoundNodesTreeBuilder *Builder, int MaxDepth,
397 TraversalKind Traversal, BindKind Bind) {
398 MatchChildASTVisitor Visitor(
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000399 &Matcher, this, Builder, MaxDepth, Traversal, Bind);
Manuel Klimek4da21662012-07-06 05:48:52 +0000400 return Visitor.findMatch(Node);
401 }
402
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000403 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
Daniel Jasper20b802d2012-07-17 07:39:27 +0000404 const Matcher<NamedDecl> &Base,
405 BoundNodesTreeBuilder *Builder);
Manuel Klimek4da21662012-07-06 05:48:52 +0000406
Daniel Jasperc99a3ad2012-10-22 16:26:51 +0000407 // Implements ASTMatchFinder::matchesChildOf.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000408 virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
409 const DynTypedMatcher &Matcher,
Manuel Klimek4da21662012-07-06 05:48:52 +0000410 BoundNodesTreeBuilder *Builder,
411 TraversalKind Traversal,
412 BindKind Bind) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000413 return matchesRecursively(Node, Matcher, Builder, 1, Traversal,
Manuel Klimek4da21662012-07-06 05:48:52 +0000414 Bind);
415 }
Daniel Jasperc99a3ad2012-10-22 16:26:51 +0000416 // Implements ASTMatchFinder::matchesDescendantOf.
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000417 virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
418 const DynTypedMatcher &Matcher,
Manuel Klimek4da21662012-07-06 05:48:52 +0000419 BoundNodesTreeBuilder *Builder,
420 BindKind Bind) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000421 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
Manuel Klimek4da21662012-07-06 05:48:52 +0000422 TK_AsIs, Bind);
423 }
Manuel Klimek579b1202012-09-07 09:26:10 +0000424 // Implements ASTMatchFinder::matchesAncestorOf.
425 virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
426 const DynTypedMatcher &Matcher,
Daniel Jasperc99a3ad2012-10-22 16:26:51 +0000427 BoundNodesTreeBuilder *Builder,
428 AncestorMatchMode MatchMode) {
Manuel Klimek579b1202012-09-07 09:26:10 +0000429 if (!Parents) {
430 // We always need to run over the whole translation unit, as
431 // \c hasAncestor can escape any subtree.
432 Parents.reset(ParentMapASTVisitor::buildMap(
433 *ActiveASTContext->getTranslationUnitDecl()));
434 }
435 ast_type_traits::DynTypedNode Ancestor = Node;
436 while (Ancestor.get<TranslationUnitDecl>() !=
437 ActiveASTContext->getTranslationUnitDecl()) {
438 assert(Ancestor.getMemoizationData() &&
439 "Invariant broken: only nodes that support memoization may be "
440 "used in the parent map.");
441 ParentMapASTVisitor::ParentMap::const_iterator I =
442 Parents->find(Ancestor.getMemoizationData());
443 if (I == Parents->end()) {
444 assert(false &&
445 "Found node that is not in the parent map.");
446 return false;
447 }
448 Ancestor = I->second;
449 if (Matcher.matches(Ancestor, this, Builder))
450 return true;
Daniel Jasperc99a3ad2012-10-22 16:26:51 +0000451 if (MatchMode == ASTMatchFinder::AMM_ParentOnly)
452 return false;
Manuel Klimek579b1202012-09-07 09:26:10 +0000453 }
454 return false;
455 }
Manuel Klimek4da21662012-07-06 05:48:52 +0000456
457 bool shouldVisitTemplateInstantiations() const { return true; }
458 bool shouldVisitImplicitCode() const { return true; }
459
460private:
461 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
462 // the aggregated bound nodes for each match.
463 class MatchVisitor : public BoundNodesTree::Visitor {
464 public:
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000465 MatchVisitor(ASTContext* Context,
Manuel Klimek4da21662012-07-06 05:48:52 +0000466 MatchFinder::MatchCallback* Callback)
467 : Context(Context),
468 Callback(Callback) {}
469
470 virtual void visitMatch(const BoundNodes& BoundNodesView) {
471 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
472 }
473
474 private:
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000475 ASTContext* Context;
Manuel Klimek4da21662012-07-06 05:48:52 +0000476 MatchFinder::MatchCallback* Callback;
477 };
478
Daniel Jasper20b802d2012-07-17 07:39:27 +0000479 // Returns true if 'TypeNode' has an alias that matches the given matcher.
480 bool typeHasMatchingAlias(const Type *TypeNode,
481 const Matcher<NamedDecl> Matcher,
482 BoundNodesTreeBuilder *Builder) {
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000483 const Type *const CanonicalType =
Manuel Klimek4da21662012-07-06 05:48:52 +0000484 ActiveASTContext->getCanonicalType(TypeNode);
Daniel Jasper20b802d2012-07-17 07:39:27 +0000485 const std::set<const TypedefDecl*> &Aliases = TypeAliases[CanonicalType];
486 for (std::set<const TypedefDecl*>::const_iterator
487 It = Aliases.begin(), End = Aliases.end();
488 It != End; ++It) {
489 if (Matcher.matches(**It, this, Builder))
490 return true;
491 }
492 return false;
Manuel Klimek4da21662012-07-06 05:48:52 +0000493 }
494
495 // Matches all registered matchers on the given node and calls the
496 // result callback for every node that matches.
497 template <typename T>
498 void match(const T &node) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000499 for (std::vector<std::pair<const internal::DynTypedMatcher*,
500 MatchCallback*> >::const_iterator
501 I = MatcherCallbackPairs->begin(), E = MatcherCallbackPairs->end();
502 I != E; ++I) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000503 BoundNodesTreeBuilder Builder;
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000504 if (I->first->matches(ast_type_traits::DynTypedNode::create(node),
505 this, &Builder)) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000506 BoundNodesTree BoundNodes = Builder.build();
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000507 MatchVisitor Visitor(ActiveASTContext, I->second);
Manuel Klimek4da21662012-07-06 05:48:52 +0000508 BoundNodes.visitMatches(&Visitor);
509 }
510 }
511 }
512
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000513 std::vector<std::pair<const internal::DynTypedMatcher*,
514 MatchCallback*> > *const MatcherCallbackPairs;
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000515 ASTContext *ActiveASTContext;
Manuel Klimek4da21662012-07-06 05:48:52 +0000516
Daniel Jasper20b802d2012-07-17 07:39:27 +0000517 // Maps a canonical type to its TypedefDecls.
518 llvm::DenseMap<const Type*, std::set<const TypedefDecl*> > TypeAliases;
Manuel Klimek4da21662012-07-06 05:48:52 +0000519
520 // Maps (matcher, node) -> the match result for memoization.
521 typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
522 MemoizationMap ResultCache;
Manuel Klimek579b1202012-09-07 09:26:10 +0000523
524 llvm::OwningPtr<ParentMapASTVisitor::ParentMap> Parents;
Manuel Klimek4da21662012-07-06 05:48:52 +0000525};
526
527// Returns true if the given class is directly or indirectly derived
Daniel Jasper76dafa72012-09-07 12:48:17 +0000528// from a base type with the given name. A class is not considered to be
529// derived from itself.
Daniel Jasper20b802d2012-07-17 07:39:27 +0000530bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
531 const Matcher<NamedDecl> &Base,
532 BoundNodesTreeBuilder *Builder) {
Daniel Jasper20b802d2012-07-17 07:39:27 +0000533 if (!Declaration->hasDefinition())
Manuel Klimek4da21662012-07-06 05:48:52 +0000534 return false;
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000535 typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
Manuel Klimek4da21662012-07-06 05:48:52 +0000536 for (BaseIterator It = Declaration->bases_begin(),
537 End = Declaration->bases_end(); It != End; ++It) {
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000538 const Type *TypeNode = It->getType().getTypePtr();
Manuel Klimek4da21662012-07-06 05:48:52 +0000539
Daniel Jasper20b802d2012-07-17 07:39:27 +0000540 if (typeHasMatchingAlias(TypeNode, Base, Builder))
Manuel Klimek4da21662012-07-06 05:48:52 +0000541 return true;
542
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000543 // Type::getAs<...>() drills through typedefs.
544 if (TypeNode->getAs<DependentNameType>() != NULL ||
Daniel Jasper08f0c532012-09-18 14:17:42 +0000545 TypeNode->getAs<DependentTemplateSpecializationType>() != NULL ||
Daniel Jasper20b802d2012-07-17 07:39:27 +0000546 TypeNode->getAs<TemplateTypeParmType>() != NULL)
Manuel Klimek4da21662012-07-06 05:48:52 +0000547 // Dependent names and template TypeNode parameters will be matched when
548 // the template is instantiated.
549 continue;
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000550 CXXRecordDecl *ClassDecl = NULL;
551 TemplateSpecializationType const *TemplateType =
552 TypeNode->getAs<TemplateSpecializationType>();
Manuel Klimek4da21662012-07-06 05:48:52 +0000553 if (TemplateType != NULL) {
Daniel Jasper20b802d2012-07-17 07:39:27 +0000554 if (TemplateType->getTemplateName().isDependent())
Manuel Klimek4da21662012-07-06 05:48:52 +0000555 // Dependent template specializations will be matched when the
556 // template is instantiated.
557 continue;
Daniel Jasper20b802d2012-07-17 07:39:27 +0000558
Manuel Klimek4da21662012-07-06 05:48:52 +0000559 // For template specialization types which are specializing a template
560 // declaration which is an explicit or partial specialization of another
561 // template declaration, getAsCXXRecordDecl() returns the corresponding
562 // ClassTemplateSpecializationDecl.
563 //
564 // For template specialization types which are specializing a template
565 // declaration which is neither an explicit nor partial specialization of
566 // another template declaration, getAsCXXRecordDecl() returns NULL and
567 // we get the CXXRecordDecl of the templated declaration.
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000568 CXXRecordDecl *SpecializationDecl =
Manuel Klimek4da21662012-07-06 05:48:52 +0000569 TemplateType->getAsCXXRecordDecl();
570 if (SpecializationDecl != NULL) {
571 ClassDecl = SpecializationDecl;
572 } else {
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000573 ClassDecl = llvm::dyn_cast<CXXRecordDecl>(
Manuel Klimek4da21662012-07-06 05:48:52 +0000574 TemplateType->getTemplateName()
575 .getAsTemplateDecl()->getTemplatedDecl());
576 }
577 } else {
578 ClassDecl = TypeNode->getAsCXXRecordDecl();
579 }
580 assert(ClassDecl != NULL);
581 assert(ClassDecl != Declaration);
Daniel Jasper76dafa72012-09-07 12:48:17 +0000582 if (Base.matches(*ClassDecl, this, Builder))
583 return true;
Daniel Jasper20b802d2012-07-17 07:39:27 +0000584 if (classIsDerivedFrom(ClassDecl, Base, Builder))
Manuel Klimek4da21662012-07-06 05:48:52 +0000585 return true;
Manuel Klimek4da21662012-07-06 05:48:52 +0000586 }
587 return false;
588}
589
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000590bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000591 if (DeclNode == NULL) {
592 return true;
593 }
594 match(*DeclNode);
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000595 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000596}
597
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000598bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000599 if (StmtNode == NULL) {
600 return true;
601 }
602 match(*StmtNode);
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000603 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000604}
605
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000606bool MatchASTVisitor::TraverseType(QualType TypeNode) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000607 match(TypeNode);
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000608 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000609}
610
Daniel Jasperce620072012-10-17 08:52:59 +0000611bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
612 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
613 // We still want to find those types via matchers, so we match them here. Note
614 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
615 // type, so we visit all involved parts of a compound type when matching on
616 // each TypeLoc.
617 match(TypeLocNode);
618 match(TypeLocNode.getType());
619 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
Manuel Klimek4da21662012-07-06 05:48:52 +0000620}
621
Daniel Jaspera7564432012-09-13 13:11:25 +0000622bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
623 match(*NNS);
624 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
625}
626
627bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
628 NestedNameSpecifierLoc NNS) {
629 match(NNS);
630 // We only match the nested name specifier here (as opposed to traversing it)
631 // because the traversal is already done in the parallel "Loc"-hierarchy.
632 match(*NNS.getNestedNameSpecifier());
633 return
634 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
635}
636
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000637class MatchASTConsumer : public ASTConsumer {
Manuel Klimek4da21662012-07-06 05:48:52 +0000638public:
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000639 MatchASTConsumer(
640 std::vector<std::pair<const internal::DynTypedMatcher*,
641 MatchCallback*> > *MatcherCallbackPairs,
642 MatchFinder::ParsingDoneTestCallback *ParsingDone)
643 : Visitor(MatcherCallbackPairs),
644 ParsingDone(ParsingDone) {}
Manuel Klimek4da21662012-07-06 05:48:52 +0000645
646private:
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000647 virtual void HandleTranslationUnit(ASTContext &Context) {
Manuel Klimek4da21662012-07-06 05:48:52 +0000648 if (ParsingDone != NULL) {
649 ParsingDone->run();
650 }
651 Visitor.set_active_ast_context(&Context);
652 Visitor.TraverseDecl(Context.getTranslationUnitDecl());
653 Visitor.set_active_ast_context(NULL);
654 }
655
656 MatchASTVisitor Visitor;
657 MatchFinder::ParsingDoneTestCallback *ParsingDone;
658};
659
660} // end namespace
661} // end namespace internal
662
663MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000664 ASTContext *Context)
Manuel Klimek4da21662012-07-06 05:48:52 +0000665 : Nodes(Nodes), Context(Context),
666 SourceManager(&Context->getSourceManager()) {}
667
668MatchFinder::MatchCallback::~MatchCallback() {}
669MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
670
671MatchFinder::MatchFinder() : ParsingDone(NULL) {}
672
673MatchFinder::~MatchFinder() {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000674 for (std::vector<std::pair<const internal::DynTypedMatcher*,
675 MatchCallback*> >::const_iterator
676 It = MatcherCallbackPairs.begin(), End = MatcherCallbackPairs.end();
Manuel Klimek4da21662012-07-06 05:48:52 +0000677 It != End; ++It) {
678 delete It->first;
679 }
680}
681
682void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
683 MatchCallback *Action) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000684 MatcherCallbackPairs.push_back(std::make_pair(
685 new internal::Matcher<Decl>(NodeMatch), Action));
Manuel Klimek4da21662012-07-06 05:48:52 +0000686}
687
688void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
689 MatchCallback *Action) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000690 MatcherCallbackPairs.push_back(std::make_pair(
691 new internal::Matcher<QualType>(NodeMatch), Action));
Manuel Klimek4da21662012-07-06 05:48:52 +0000692}
693
694void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
695 MatchCallback *Action) {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000696 MatcherCallbackPairs.push_back(std::make_pair(
697 new internal::Matcher<Stmt>(NodeMatch), Action));
Manuel Klimek4da21662012-07-06 05:48:52 +0000698}
699
Daniel Jaspera7564432012-09-13 13:11:25 +0000700void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
701 MatchCallback *Action) {
702 MatcherCallbackPairs.push_back(std::make_pair(
703 new NestedNameSpecifierMatcher(NodeMatch), Action));
704}
705
706void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
707 MatchCallback *Action) {
708 MatcherCallbackPairs.push_back(std::make_pair(
709 new NestedNameSpecifierLocMatcher(NodeMatch), Action));
710}
711
Daniel Jasperce620072012-10-17 08:52:59 +0000712void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
713 MatchCallback *Action) {
714 MatcherCallbackPairs.push_back(std::make_pair(
715 new TypeLocMatcher(NodeMatch), Action));
716}
717
Daniel Jaspere0e6b9e2012-07-10 20:20:19 +0000718ASTConsumer *MatchFinder::newASTConsumer() {
Manuel Klimeka78d0d62012-09-05 12:12:07 +0000719 return new internal::MatchASTConsumer(&MatcherCallbackPairs, ParsingDone);
Manuel Klimek4da21662012-07-06 05:48:52 +0000720}
721
Manuel Klimek3e2aa992012-10-24 14:47:44 +0000722void MatchFinder::findAll(const Decl &Node, ASTContext &Context) {
723 internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
724 Visitor.set_active_ast_context(&Context);
725 Visitor.TraverseDecl(const_cast<Decl*>(&Node));
726}
727
728void MatchFinder::findAll(const Stmt &Node, ASTContext &Context) {
729 internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
730 Visitor.set_active_ast_context(&Context);
731 Visitor.TraverseStmt(const_cast<Stmt*>(&Node));
732}
733
Manuel Klimek4da21662012-07-06 05:48:52 +0000734void MatchFinder::registerTestCallbackAfterParsing(
735 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
736 ParsingDone = NewParsingDone;
737}
738
739} // end namespace ast_matchers
740} // end namespace clang