10#include "clang/AST/ASTContext.h"
11#include "clang/ASTMatchers/ASTMatchFinder.h"
12#include "clang/Analysis/CallGraph.h"
13#include "llvm/ADT/DenseMapInfo.h"
14#include "llvm/ADT/SCCIterator.h"
26template <
typename T,
unsigned SmallSize>
class ImmutableSmallSet {
28 llvm::DenseSet<T> Set;
30 static_assert(SmallSize <= 32,
"N should be small");
32 bool isSmall()
const {
return Set.empty(); }
35 using size_type = size_t;
37 ImmutableSmallSet() =
delete;
38 ImmutableSmallSet(
const ImmutableSmallSet &) =
delete;
39 ImmutableSmallSet(ImmutableSmallSet &&) =
delete;
40 T &operator=(
const ImmutableSmallSet &) =
delete;
41 T &operator=(ImmutableSmallSet &&) =
delete;
44 ImmutableSmallSet(ArrayRef<T> Storage) {
46 if (Storage.size() <= SmallSize) {
53 Set.reserve(Storage.size());
54 Set.insert(Storage.begin(), Storage.end());
58 size_type count(
const T &V)
const {
61 return llvm::is_contained(Vector, V) ? 1 : 0;
73template <
typename T,
unsigned SmallSize>
class SmartSmallSetVector {
75 using size_type = size_t;
78 SmallVector<T, SmallSize> Vector;
79 llvm::DenseSet<T> Set;
81 static_assert(SmallSize <= 32,
"N should be small");
84 bool isSmall()
const {
return Set.empty(); }
87 bool entiretyOfVectorSmallSizeIsOccupied()
const {
88 assert(isSmall() && Vector.size() <= SmallSize &&
89 "Shouldn't ask if we have already [should have] migrated into Set.");
90 return Vector.size() == SmallSize;
94 assert(Set.empty() &&
"Should not have already utilized the Set.");
97 const size_t NewMaxElts = 4 * Vector.size();
98 Vector.reserve(NewMaxElts);
99 Set.reserve(NewMaxElts);
100 Set.insert(Vector.begin(), Vector.end());
104 size_type count(
const T &V)
const {
107 return llvm::is_contained(Vector, V) ? 1 : 0;
113 bool setInsert(
const T &V) {
119 if (!entiretyOfVectorSmallSizeIsOccupied())
126 bool SetInsertionSucceeded = Set.insert(V).second;
127 (void)SetInsertionSucceeded;
128 assert(SetInsertionSucceeded &&
"We did check that no such value existed");
135 bool insert(
const T &
X) {
136 bool Result = setInsert(
X);
143 decltype(Vector) takeVector() {
145 return std::move(Vector);
149constexpr unsigned SmallCallStackSize = 16;
150constexpr unsigned SmallSCCSize = 32;
153 llvm::SmallVector<CallGraphNode::CallRecord, SmallCallStackSize>;
158CallStackTy pathfindSomeCycle(ArrayRef<CallGraphNode *> SCC) {
161 const ImmutableSmallSet<CallGraphNode *, SmallSCCSize> SCCElts(SCC);
164 auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) {
165 return SCCElts.count(N) != 0;
169 SmartSmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize>
173 CallGraphNode::CallRecord EntryNode(SCC.front(),
nullptr);
176 CallGraphNode::CallRecord *
Node = &EntryNode;
179 if (!CallStackSet.insert(*Node))
183 Node = llvm::find_if(
Node->Callee->callees(), NodeIsPartOfSCC);
188 CallStackTy CallStack = CallStackSet.takeVector();
189 CallStack.emplace_back(*Node);
197 Finder->addMatcher(translationUnitDecl().bind(
"TUDecl"),
this);
200void NoRecursionCheck::handleSCC(ArrayRef<CallGraphNode *> SCC) {
201 assert(!SCC.empty() &&
"Empty SCC does not make sense.");
204 for (CallGraphNode *N : SCC) {
205 FunctionDecl *D = N->getDefinition();
206 diag(D->getLocation(),
"function %0 is within a recursive call chain") << D;
213 const CallStackTy EventuallyCyclicCallStack = pathfindSomeCycle(SCC);
214 assert(!EventuallyCyclicCallStack.empty() &&
"We should've found the cycle");
219 const auto CyclicCallStack =
220 ArrayRef<CallGraphNode::CallRecord>(EventuallyCyclicCallStack)
221 .drop_until([LastNode = EventuallyCyclicCallStack.back()](
222 CallGraphNode::CallRecord FrontNode) {
223 return FrontNode == LastNode;
225 assert(CyclicCallStack.size() >= 2 &&
"Cycle requires at least 2 frames");
228 FunctionDecl *CycleEntryFn = CyclicCallStack.front().Callee->getDefinition();
231 diag(CycleEntryFn->getLocation(),
232 "example recursive call chain, starting from function %0",
235 for (
int CurFrame = 1, NumFrames = CyclicCallStack.size();
236 CurFrame != NumFrames; ++CurFrame) {
237 CallGraphNode::CallRecord PrevNode = CyclicCallStack[CurFrame - 1];
238 CallGraphNode::CallRecord CurrNode = CyclicCallStack[CurFrame];
240 Decl *PrevDecl = PrevNode.Callee->getDecl();
241 Decl *CurrDecl = CurrNode.Callee->getDecl();
243 diag(CurrNode.CallExpr->getBeginLoc(),
244 "Frame #%0: function %1 calls function %2 here:", DiagnosticIDs::Note)
245 << CurFrame << cast<NamedDecl>(PrevDecl) << cast<NamedDecl>(CurrDecl);
248 diag(CyclicCallStack.back().CallExpr->getBeginLoc(),
249 "... which was the starting point of the recursive call chain; there "
250 "may be other cycles",
251 DiagnosticIDs::Note);
256 const auto *TU = Result.Nodes.getNodeAs<TranslationUnitDecl>(
"TUDecl");
258 CG.addToCallGraph(
const_cast<TranslationUnitDecl *
>(TU));
262 for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
263 SCCE = llvm::scc_end(&CG);
264 SCCI != SCCE; ++SCCI) {
265 if (!SCCI.hasCycle())
const FunctionDecl * Decl
::clang::DynTypedNode Node
DiagnosticBuilder diag(SourceLocation Loc, StringRef Description, DiagnosticIDs::Level Level=DiagnosticIDs::Warning)
Add a diagnostic with the check's name.
void registerMatchers(ast_matchers::MatchFinder *Finder) override
Override this to register AST matchers with Finder.
void check(const ast_matchers::MatchFinder::MatchResult &Result) override
ClangTidyChecks that register ASTMatchers should do the actual work in here.