summaryrefslogtreecommitdiffstats
path: root/lib/ASTMatchers/ASTMatchFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/ASTMatchers/ASTMatchFinder.cpp')
-rw-r--r--lib/ASTMatchers/ASTMatchFinder.cpp289
1 files changed, 219 insertions, 70 deletions
diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp
index 23708e2..fa7968a 100644
--- a/lib/ASTMatchers/ASTMatchFinder.cpp
+++ b/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -20,7 +20,11 @@
#include "clang/AST/ASTConsumer.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/RecursiveASTVisitor.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/Timer.h"
#include <deque>
+#include <memory>
#include <set>
namespace clang {
@@ -53,7 +57,7 @@ static const unsigned MaxMemoizationEntries = 10000;
// FIXME: Benchmark whether memoization of non-pointer typed nodes
// provides enough benefit for the additional amount of code.
struct MatchKey {
- uint64_t MatcherID;
+ DynTypedMatcher::MatcherIDType MatcherID;
ast_type_traits::DynTypedNode Node;
BoundNodesTreeBuilder BoundNodes;
@@ -292,28 +296,33 @@ private:
class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
public ASTMatchFinder {
public:
- MatchASTVisitor(
- std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *
- MatcherCallbackPairs)
- : MatcherCallbackPairs(MatcherCallbackPairs), ActiveASTContext(nullptr) {}
+ MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
+ const MatchFinder::MatchFinderOptions &Options)
+ : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
+
+ ~MatchASTVisitor() {
+ if (Options.CheckProfiling) {
+ Options.CheckProfiling->Records = std::move(TimeByBucket);
+ }
+ }
void onStartOfTranslationUnit() {
- for (std::vector<std::pair<internal::DynTypedMatcher,
- MatchCallback *> >::const_iterator
- I = MatcherCallbackPairs->begin(),
- E = MatcherCallbackPairs->end();
- I != E; ++I) {
- I->second->onStartOfTranslationUnit();
+ const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+ TimeBucketRegion Timer;
+ for (MatchCallback *MC : Matchers->AllCallbacks) {
+ if (EnableCheckProfiling)
+ Timer.setBucket(&TimeByBucket[MC->getID()]);
+ MC->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();
+ const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+ TimeBucketRegion Timer;
+ for (MatchCallback *MC : Matchers->AllCallbacks) {
+ if (EnableCheckProfiling)
+ Timer.setBucket(&TimeByBucket[MC->getID()]);
+ MC->onEndOfTranslationUnit();
}
}
@@ -372,7 +381,7 @@ public:
BoundNodesTreeBuilder *Builder, int MaxDepth,
TraversalKind Traversal, BindKind Bind) {
// For AST-nodes that don't have an identity, we can't memoize.
- if (!Node.getMemoizationData())
+ if (!Node.getMemoizationData() || !Builder->isComparable())
return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
Bind);
@@ -392,9 +401,12 @@ public:
Result.Nodes = *Builder;
Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
MaxDepth, Traversal, Bind);
- ResultCache[Key] = Result;
- *Builder = Result.Nodes;
- return Result.ResultOfMatch;
+
+ MemoizedMatchResult &CachedResult = ResultCache[Key];
+ CachedResult = std::move(Result);
+
+ *Builder = CachedResult.Nodes;
+ return CachedResult.ResultOfMatch;
}
// Matches children or descendants of 'Node' with 'BaseMatcher'.
@@ -447,22 +459,27 @@ public:
// Matches all registered matchers on the given node and calls the
// result callback for every node that matches.
- 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);
- }
+ void match(const ast_type_traits::DynTypedNode &Node) {
+ // FIXME: Improve this with a switch or a visitor pattern.
+ if (auto *N = Node.get<Decl>()) {
+ match(*N);
+ } else if (auto *N = Node.get<Stmt>()) {
+ match(*N);
+ } else if (auto *N = Node.get<Type>()) {
+ match(*N);
+ } else if (auto *N = Node.get<QualType>()) {
+ match(*N);
+ } else if (auto *N = Node.get<NestedNameSpecifier>()) {
+ match(*N);
+ } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
+ match(*N);
+ } else if (auto *N = Node.get<TypeLoc>()) {
+ match(*N);
}
}
template <typename T> void match(const T &Node) {
- match(ast_type_traits::DynTypedNode::create(Node));
+ matchDispatch(&Node);
}
// Implements ASTMatchFinder::getASTContext.
@@ -475,6 +492,116 @@ public:
bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
private:
+ class TimeBucketRegion {
+ public:
+ TimeBucketRegion() : Bucket(nullptr) {}
+ ~TimeBucketRegion() { setBucket(nullptr); }
+
+ /// \brief Start timing for \p NewBucket.
+ ///
+ /// If there was a bucket already set, it will finish the timing for that
+ /// other bucket.
+ /// \p NewBucket will be timed until the next call to \c setBucket() or
+ /// until the \c TimeBucketRegion is destroyed.
+ /// If \p NewBucket is the same as the currently timed bucket, this call
+ /// does nothing.
+ void setBucket(llvm::TimeRecord *NewBucket) {
+ if (Bucket != NewBucket) {
+ auto Now = llvm::TimeRecord::getCurrentTime(true);
+ if (Bucket)
+ *Bucket += Now;
+ if (NewBucket)
+ *NewBucket -= Now;
+ Bucket = NewBucket;
+ }
+ }
+
+ private:
+ llvm::TimeRecord *Bucket;
+ };
+
+ /// \brief Runs all the \p Matchers on \p Node.
+ ///
+ /// Used by \c matchDispatch() below.
+ template <typename T, typename MC>
+ void matchWithoutFilter(const T &Node, const MC &Matchers) {
+ const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+ TimeBucketRegion Timer;
+ for (const auto &MP : Matchers) {
+ if (EnableCheckProfiling)
+ Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+ BoundNodesTreeBuilder Builder;
+ if (MP.first.matches(Node, this, &Builder)) {
+ MatchVisitor Visitor(ActiveASTContext, MP.second);
+ Builder.visitMatches(&Visitor);
+ }
+ }
+ }
+
+ void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
+ auto Kind = DynNode.getNodeKind();
+ auto it = MatcherFiltersMap.find(Kind);
+ const auto &Filter =
+ it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
+
+ if (Filter.empty())
+ return;
+
+ const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
+ TimeBucketRegion Timer;
+ auto &Matchers = this->Matchers->DeclOrStmt;
+ for (unsigned short I : Filter) {
+ auto &MP = Matchers[I];
+ if (EnableCheckProfiling)
+ Timer.setBucket(&TimeByBucket[MP.second->getID()]);
+ BoundNodesTreeBuilder Builder;
+ if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
+ MatchVisitor Visitor(ActiveASTContext, MP.second);
+ Builder.visitMatches(&Visitor);
+ }
+ }
+ }
+
+ const std::vector<unsigned short> &
+ getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
+ auto &Filter = MatcherFiltersMap[Kind];
+ auto &Matchers = this->Matchers->DeclOrStmt;
+ assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
+ for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
+ if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
+ Filter.push_back(I);
+ }
+ }
+ return Filter;
+ }
+
+ /// @{
+ /// \brief Overloads to pair the different node types to their matchers.
+ void matchDispatch(const Decl *Node) {
+ return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
+ }
+ void matchDispatch(const Stmt *Node) {
+ return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
+ }
+
+ void matchDispatch(const Type *Node) {
+ matchWithoutFilter(QualType(Node, 0), Matchers->Type);
+ }
+ void matchDispatch(const TypeLoc *Node) {
+ matchWithoutFilter(*Node, Matchers->TypeLoc);
+ }
+ void matchDispatch(const QualType *Node) {
+ matchWithoutFilter(*Node, Matchers->Type);
+ }
+ void matchDispatch(const NestedNameSpecifier *Node) {
+ matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
+ }
+ void matchDispatch(const NestedNameSpecifierLoc *Node) {
+ matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
+ }
+ void matchDispatch(const void *) { /* Do nothing. */ }
+ /// @}
+
// Returns whether an ancestor of \p Node matches \p Matcher.
//
// The order of matching ((which can lead to different nodes being bound in
@@ -497,11 +624,7 @@ private:
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;
@@ -514,9 +637,13 @@ private:
*Builder = I->second.Nodes;
return I->second.ResultOfMatch;
}
+
MemoizedMatchResult Result;
Result.ResultOfMatch = false;
Result.Nodes = *Builder;
+
+ const auto &Parents = ActiveASTContext->getParents(Node);
+ assert(!Parents.empty() && "Found node that is not in the parent map.");
if (Parents.size() == 1) {
// Only one parent - do recursive memoization.
const ast_type_traits::DynTypedNode Parent = Parents[0];
@@ -543,25 +670,24 @@ private:
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) {
+ for (const auto &Parent :
+ ActiveASTContext->getParents(Queue.front())) {
// Make sure we do not visit the same node twice.
// Otherwise, we'll visit the common ancestors as often as there
// are splits on the way down.
- if (Visited.insert(I->getMemoizationData()).second)
- Queue.push_back(*I);
+ if (Visited.insert(Parent.getMemoizationData()).second)
+ Queue.push_back(Parent);
}
}
Queue.pop_front();
}
}
- ResultCache[Key] = Result;
- *Builder = Result.Nodes;
- return Result.ResultOfMatch;
+ MemoizedMatchResult &CachedResult = ResultCache[Key];
+ CachedResult = std::move(Result);
+
+ *Builder = CachedResult.Nodes;
+ return CachedResult.ResultOfMatch;
}
// Implements a BoundNodesTree::Visitor that calls a MatchCallback with
@@ -588,22 +714,35 @@ private:
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) {
+ for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) {
BoundNodesTreeBuilder Result(*Builder);
- if (Matcher.matches(**It, this, &Result)) {
- *Builder = Result;
+ if (Matcher.matches(*Alias, this, &Result)) {
+ *Builder = std::move(Result);
return true;
}
}
return false;
}
- std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *const
- MatcherCallbackPairs;
+ /// \brief Bucket to record map.
+ ///
+ /// Used to get the appropriate bucket for each matcher.
+ llvm::StringMap<llvm::TimeRecord> TimeByBucket;
+
+ const MatchFinder::MatchersByType *Matchers;
+
+ /// \brief Filtered list of matcher indices for each matcher kind.
+ ///
+ /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
+ /// kind (and derived kinds) so it is a waste to try every matcher on every
+ /// node.
+ /// We precalculate a list of matchers that pass the toplevel restrict check.
+ /// This also allows us to skip the restrict check at matching time. See
+ /// use \c matchesNoKindCheck() above.
+ llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
+ MatcherFiltersMap;
+
+ const MatchFinder::MatchFinderOptions &Options;
ASTContext *ActiveASTContext;
// Maps a canonical type to its TypedefDecls.
@@ -680,7 +819,7 @@ bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
}
BoundNodesTreeBuilder Result(*Builder);
if (Base.matches(*ClassDecl, this, &Result)) {
- *Builder = Result;
+ *Builder = std::move(Result);
return true;
}
if (classIsDerivedFrom(ClassDecl, Base, Builder))
@@ -731,7 +870,8 @@ bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
match(NNS);
// We only match the nested name specifier here (as opposed to traversing it)
// because the traversal is already done in the parallel "Loc"-hierarchy.
- match(*NNS.getNestedNameSpecifier());
+ if (NNS.hasQualifier())
+ match(*NNS.getNestedNameSpecifier());
return
RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
}
@@ -765,38 +905,45 @@ MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
MatchFinder::MatchCallback::~MatchCallback() {}
MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
-MatchFinder::MatchFinder() : ParsingDone(nullptr) {}
+MatchFinder::MatchFinder(MatchFinderOptions Options)
+ : Options(std::move(Options)), ParsingDone(nullptr) {}
MatchFinder::~MatchFinder() {}
void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.Type.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.DeclOrStmt.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.NestedNameSpecifier.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.NestedNameSpecifierLoc.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
MatchCallback *Action) {
- MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.TypeLoc.push_back(std::make_pair(NodeMatch, Action));
+ Matchers.AllCallbacks.push_back(Action);
}
bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
@@ -823,19 +970,19 @@ bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
return false;
}
-ASTConsumer *MatchFinder::newASTConsumer() {
- return new internal::MatchASTConsumer(this, ParsingDone);
+std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
+ return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
}
void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
ASTContext &Context) {
- internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
+ internal::MatchASTVisitor Visitor(&Matchers, Options);
Visitor.set_active_ast_context(&Context);
Visitor.match(Node);
}
void MatchFinder::matchAST(ASTContext &Context) {
- internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
+ internal::MatchASTVisitor Visitor(&Matchers, Options);
Visitor.set_active_ast_context(&Context);
Visitor.onStartOfTranslationUnit();
Visitor.TraverseDecl(Context.getTranslationUnitDecl());
@@ -847,5 +994,7 @@ void MatchFinder::registerTestCallbackAfterParsing(
ParsingDone = NewParsingDone;
}
+StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
+
} // end namespace ast_matchers
} // end namespace clang
OpenPOWER on IntegriCloud