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