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