ASTMatchFinder.cpp [plain text]
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/AST/ASTConsumer.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include <deque>
#include <set>
namespace clang {
namespace ast_matchers {
namespace internal {
namespace {
typedef MatchFinder::MatchCallback MatchCallback;
static const unsigned MaxMemoizationEntries = 10000;
struct MatchKey {
uint64_t MatcherID;
ast_type_traits::DynTypedNode Node;
BoundNodesTreeBuilder BoundNodes;
bool operator<(const MatchKey &Other) const {
if (MatcherID != Other.MatcherID)
return MatcherID < Other.MatcherID;
if (Node != Other.Node)
return Node < Other.Node;
return BoundNodes < Other.BoundNodes;
}
};
struct MemoizedMatchResult {
bool ResultOfMatch;
BoundNodesTreeBuilder Nodes;
};
class MatchChildASTVisitor
: public RecursiveASTVisitor<MatchChildASTVisitor> {
public:
typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
MatchChildASTVisitor(const DynTypedMatcher *Matcher,
ASTMatchFinder *Finder,
BoundNodesTreeBuilder *Builder,
int MaxDepth,
ASTMatchFinder::TraversalKind Traversal,
ASTMatchFinder::BindKind Bind)
: Matcher(Matcher),
Finder(Finder),
Builder(Builder),
CurrentDepth(0),
MaxDepth(MaxDepth),
Traversal(Traversal),
Bind(Bind),
Matches(false) {}
bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
reset();
if (const Decl *D = DynNode.get<Decl>())
traverse(*D);
else if (const Stmt *S = DynNode.get<Stmt>())
traverse(*S);
else if (const NestedNameSpecifier *NNS =
DynNode.get<NestedNameSpecifier>())
traverse(*NNS);
else if (const NestedNameSpecifierLoc *NNSLoc =
DynNode.get<NestedNameSpecifierLoc>())
traverse(*NNSLoc);
else if (const QualType *Q = DynNode.get<QualType>())
traverse(*Q);
else if (const TypeLoc *T = DynNode.get<TypeLoc>())
traverse(*T);
*Builder = ResultBindings;
return Matches;
}
bool TraverseDecl(Decl *DeclNode) {
ScopedIncrement ScopedDepth(&CurrentDepth);
return (DeclNode == NULL) || traverse(*DeclNode);
}
bool TraverseStmt(Stmt *StmtNode) {
ScopedIncrement ScopedDepth(&CurrentDepth);
const Stmt *StmtToTraverse = StmtNode;
if (Traversal ==
ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
if (ExprNode != NULL) {
StmtToTraverse = ExprNode->IgnoreParenImpCasts();
}
}
return (StmtToTraverse == NULL) || traverse(*StmtToTraverse);
}
bool TraverseType(QualType TypeNode) {
if (TypeNode.isNull())
return true;
ScopedIncrement ScopedDepth(&CurrentDepth);
if (!match(*TypeNode))
return false;
return traverse(TypeNode);
}
bool TraverseTypeLoc(TypeLoc TypeLocNode) {
if (TypeLocNode.isNull())
return true;
ScopedIncrement ScopedDepth(&CurrentDepth);
if (!match(*TypeLocNode.getType()))
return false;
if (!match(TypeLocNode.getType()))
return false;
return traverse(TypeLocNode);
}
bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
ScopedIncrement ScopedDepth(&CurrentDepth);
return (NNS == NULL) || traverse(*NNS);
}
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
if (!NNS)
return true;
ScopedIncrement ScopedDepth(&CurrentDepth);
if (!match(*NNS.getNestedNameSpecifier()))
return false;
return traverse(NNS);
}
bool shouldVisitTemplateInstantiations() const { return true; }
bool shouldVisitImplicitCode() const { return true; }
bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
private:
struct ScopedIncrement {
explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
~ScopedIncrement() { --(*Depth); }
private:
int *Depth;
};
void reset() {
Matches = false;
CurrentDepth = 0;
}
bool baseTraverse(const Decl &DeclNode) {
return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
}
bool baseTraverse(const Stmt &StmtNode) {
return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
}
bool baseTraverse(QualType TypeNode) {
return VisitorBase::TraverseType(TypeNode);
}
bool baseTraverse(TypeLoc TypeLocNode) {
return VisitorBase::TraverseTypeLoc(TypeLocNode);
}
bool baseTraverse(const NestedNameSpecifier &NNS) {
return VisitorBase::TraverseNestedNameSpecifier(
const_cast<NestedNameSpecifier*>(&NNS));
}
bool baseTraverse(NestedNameSpecifierLoc NNS) {
return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
}
template <typename T>
bool match(const T &Node) {
if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
return true;
}
if (Bind != ASTMatchFinder::BK_All) {
BoundNodesTreeBuilder RecursiveBuilder(*Builder);
if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
&RecursiveBuilder)) {
Matches = true;
ResultBindings.addMatch(RecursiveBuilder);
return false; }
} else {
BoundNodesTreeBuilder RecursiveBuilder(*Builder);
if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
&RecursiveBuilder)) {
Matches = true;
ResultBindings.addMatch(RecursiveBuilder);
}
}
return true;
}
template <typename T>
bool traverse(const T &Node) {
TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
traverse_can_only_be_instantiated_with_base_type);
if (!match(Node))
return false;
return baseTraverse(Node);
}
const DynTypedMatcher *const Matcher;
ASTMatchFinder *const Finder;
BoundNodesTreeBuilder *const Builder;
BoundNodesTreeBuilder ResultBindings;
int CurrentDepth;
const int MaxDepth;
const ASTMatchFinder::TraversalKind Traversal;
const ASTMatchFinder::BindKind Bind;
bool Matches;
};
class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
public ASTMatchFinder {
public:
MatchASTVisitor(
std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *
MatcherCallbackPairs)
: MatcherCallbackPairs(MatcherCallbackPairs), ActiveASTContext(NULL) {}
void onStartOfTranslationUnit() {
for (std::vector<std::pair<internal::DynTypedMatcher,
MatchCallback *> >::const_iterator
I = MatcherCallbackPairs->begin(),
E = MatcherCallbackPairs->end();
I != E; ++I) {
I->second->onStartOfTranslationUnit();
}
}
void onEndOfTranslationUnit() {
for (std::vector<std::pair<internal::DynTypedMatcher,
MatchCallback *> >::const_iterator
I = MatcherCallbackPairs->begin(),
E = MatcherCallbackPairs->end();
I != E; ++I) {
I->second->onEndOfTranslationUnit();
}
}
void set_active_ast_context(ASTContext *NewActiveASTContext) {
ActiveASTContext = NewActiveASTContext;
}
bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
const Type *CanonicalType = ActiveASTContext->getCanonicalType(TypeNode);
TypeAliases[CanonicalType].insert(DeclNode);
return true;
}
bool TraverseDecl(Decl *DeclNode);
bool TraverseStmt(Stmt *StmtNode);
bool TraverseType(QualType TypeNode);
bool TraverseTypeLoc(TypeLoc TypeNode);
bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder, int MaxDepth,
TraversalKind Traversal, BindKind Bind) {
if (!Node.getMemoizationData())
return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
Bind);
MatchKey Key;
Key.MatcherID = Matcher.getID();
Key.Node = Node;
Key.BoundNodes = *Builder;
MemoizationMap::iterator I = ResultCache.find(Key);
if (I != ResultCache.end()) {
*Builder = I->second.Nodes;
return I->second.ResultOfMatch;
}
MemoizedMatchResult Result;
Result.Nodes = *Builder;
Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
MaxDepth, Traversal, Bind);
ResultCache[Key] = Result;
*Builder = Result.Nodes;
return Result.ResultOfMatch;
}
bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder, int MaxDepth,
TraversalKind Traversal, BindKind Bind) {
MatchChildASTVisitor Visitor(
&Matcher, this, Builder, MaxDepth, Traversal, Bind);
return Visitor.findMatch(Node);
}
virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
const Matcher<NamedDecl> &Base,
BoundNodesTreeBuilder *Builder);
virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder,
TraversalKind Traversal,
BindKind Bind) {
if (ResultCache.size() > MaxMemoizationEntries)
ResultCache.clear();
return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
Bind);
}
virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder,
BindKind Bind) {
if (ResultCache.size() > MaxMemoizationEntries)
ResultCache.clear();
return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
TK_AsIs, Bind);
}
virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder,
AncestorMatchMode MatchMode) {
if (ResultCache.size() > MaxMemoizationEntries)
ResultCache.clear();
return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
MatchMode);
}
void match(const ast_type_traits::DynTypedNode& Node) {
for (std::vector<std::pair<internal::DynTypedMatcher,
MatchCallback *> >::const_iterator
I = MatcherCallbackPairs->begin(),
E = MatcherCallbackPairs->end();
I != E; ++I) {
BoundNodesTreeBuilder Builder;
if (I->first.matches(Node, this, &Builder)) {
MatchVisitor Visitor(ActiveASTContext, I->second);
Builder.visitMatches(&Visitor);
}
}
}
template <typename T> void match(const T &Node) {
match(ast_type_traits::DynTypedNode::create(Node));
}
virtual ASTContext &getASTContext() const { return *ActiveASTContext; }
bool shouldVisitTemplateInstantiations() const { return true; }
bool shouldVisitImplicitCode() const { return true; }
bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
private:
bool memoizedMatchesAncestorOfRecursively(
const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
if (Node.get<TranslationUnitDecl>() ==
ActiveASTContext->getTranslationUnitDecl())
return false;
assert(Node.getMemoizationData() &&
"Invariant broken: only nodes that support memoization may be "
"used in the parent map.");
ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
if (Parents.empty()) {
assert(false && "Found node that is not in the parent map.");
return false;
}
MatchKey Key;
Key.MatcherID = Matcher.getID();
Key.Node = Node;
Key.BoundNodes = *Builder;
MemoizationMap::iterator I = ResultCache.find(Key);
if (I != ResultCache.end()) {
*Builder = I->second.Nodes;
return I->second.ResultOfMatch;
}
MemoizedMatchResult Result;
Result.ResultOfMatch = false;
Result.Nodes = *Builder;
if (Parents.size() == 1) {
const ast_type_traits::DynTypedNode Parent = Parents[0];
if (Matcher.matches(Parent, this, &Result.Nodes)) {
Result.ResultOfMatch = true;
} else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
Result.Nodes = *Builder;
Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
Parent, Matcher, &Result.Nodes, MatchMode);
}
} else {
llvm::DenseSet<const void *> Visited;
std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
Parents.end());
while (!Queue.empty()) {
Result.Nodes = *Builder;
if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
Result.ResultOfMatch = true;
break;
}
if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
ASTContext::ParentVector Ancestors =
ActiveASTContext->getParents(Queue.front());
for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(),
E = Ancestors.end();
I != E; ++I) {
if (Visited.insert(I->getMemoizationData()).second)
Queue.push_back(*I);
}
}
Queue.pop_front();
}
}
ResultCache[Key] = Result;
*Builder = Result.Nodes;
return Result.ResultOfMatch;
}
class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
public:
MatchVisitor(ASTContext* Context,
MatchFinder::MatchCallback* Callback)
: Context(Context),
Callback(Callback) {}
virtual void visitMatch(const BoundNodes& BoundNodesView) {
Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
}
private:
ASTContext* Context;
MatchFinder::MatchCallback* Callback;
};
bool typeHasMatchingAlias(const Type *TypeNode,
const Matcher<NamedDecl> Matcher,
BoundNodesTreeBuilder *Builder) {
const Type *const CanonicalType =
ActiveASTContext->getCanonicalType(TypeNode);
const std::set<const TypedefNameDecl *> &Aliases =
TypeAliases[CanonicalType];
for (std::set<const TypedefNameDecl*>::const_iterator
It = Aliases.begin(), End = Aliases.end();
It != End; ++It) {
BoundNodesTreeBuilder Result(*Builder);
if (Matcher.matches(**It, this, &Result)) {
*Builder = Result;
return true;
}
}
return false;
}
std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *const
MatcherCallbackPairs;
ASTContext *ActiveASTContext;
llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
MemoizationMap ResultCache;
};
static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
if (TypeNode->getAs<DependentNameType>() != NULL ||
TypeNode->getAs<DependentTemplateSpecializationType>() != NULL ||
TypeNode->getAs<TemplateTypeParmType>() != NULL)
return NULL;
TemplateSpecializationType const *TemplateType =
TypeNode->getAs<TemplateSpecializationType>();
if (TemplateType == NULL) {
return TypeNode->getAsCXXRecordDecl();
}
if (TemplateType->getTemplateName().isDependent())
return NULL;
CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
if (SpecializationDecl != NULL) {
return SpecializationDecl;
}
NamedDecl *Templated =
TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
return TemplatedRecord;
}
TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
assert(AliasDecl);
return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
}
bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
const Matcher<NamedDecl> &Base,
BoundNodesTreeBuilder *Builder) {
if (!Declaration->hasDefinition())
return false;
typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
for (BaseIterator It = Declaration->bases_begin(),
End = Declaration->bases_end();
It != End; ++It) {
const Type *TypeNode = It->getType().getTypePtr();
if (typeHasMatchingAlias(TypeNode, Base, Builder))
return true;
CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
if (ClassDecl == NULL)
continue;
if (ClassDecl == Declaration) {
return false;
}
BoundNodesTreeBuilder Result(*Builder);
if (Base.matches(*ClassDecl, this, &Result)) {
*Builder = Result;
return true;
}
if (classIsDerivedFrom(ClassDecl, Base, Builder))
return true;
}
return false;
}
bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
if (DeclNode == NULL) {
return true;
}
match(*DeclNode);
return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
}
bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
if (StmtNode == NULL) {
return true;
}
match(*StmtNode);
return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
}
bool MatchASTVisitor::TraverseType(QualType TypeNode) {
match(TypeNode);
return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
}
bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
match(TypeLocNode);
match(TypeLocNode.getType());
return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
}
bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
match(*NNS);
return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
}
bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
NestedNameSpecifierLoc NNS) {
match(NNS);
match(*NNS.getNestedNameSpecifier());
return
RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
}
class MatchASTConsumer : public ASTConsumer {
public:
MatchASTConsumer(MatchFinder *Finder,
MatchFinder::ParsingDoneTestCallback *ParsingDone)
: Finder(Finder), ParsingDone(ParsingDone) {}
private:
virtual void HandleTranslationUnit(ASTContext &Context) {
if (ParsingDone != NULL) {
ParsingDone->run();
}
Finder->matchAST(Context);
}
MatchFinder *Finder;
MatchFinder::ParsingDoneTestCallback *ParsingDone;
};
} }
MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
ASTContext *Context)
: Nodes(Nodes), Context(Context),
SourceManager(&Context->getSourceManager()) {}
MatchFinder::MatchCallback::~MatchCallback() {}
MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
MatchFinder::MatchFinder() : ParsingDone(NULL) {}
MatchFinder::~MatchFinder() {}
void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
MatchCallback *Action) {
MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
}
bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
MatchCallback *Action) {
if (NodeMatch.canConvertTo<Decl>()) {
addMatcher(NodeMatch.convertTo<Decl>(), Action);
return true;
} else if (NodeMatch.canConvertTo<QualType>()) {
addMatcher(NodeMatch.convertTo<QualType>(), Action);
return true;
} else if (NodeMatch.canConvertTo<Stmt>()) {
addMatcher(NodeMatch.convertTo<Stmt>(), Action);
return true;
} else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
return true;
} else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
return true;
} else if (NodeMatch.canConvertTo<TypeLoc>()) {
addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
return true;
}
return false;
}
ASTConsumer *MatchFinder::newASTConsumer() {
return new internal::MatchASTConsumer(this, ParsingDone);
}
void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
ASTContext &Context) {
internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
Visitor.set_active_ast_context(&Context);
Visitor.match(Node);
}
void MatchFinder::matchAST(ASTContext &Context) {
internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
Visitor.set_active_ast_context(&Context);
Visitor.onStartOfTranslationUnit();
Visitor.TraverseDecl(Context.getTranslationUnitDecl());
Visitor.onEndOfTranslationUnit();
}
void MatchFinder::registerTestCallbackAfterParsing(
MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
ParsingDone = NewParsingDone;
}
} }