272 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "NoRecursionCheck.h"10#include "clang/AST/ASTContext.h"11#include "clang/ASTMatchers/ASTMatchFinder.h"12#include "clang/Analysis/CallGraph.h"13#include "llvm/ADT/SCCIterator.h"14 15using namespace clang::ast_matchers;16 17namespace clang::tidy::misc {18 19namespace {20 21/// Much like SmallSet, with two differences:22/// 1. It can *only* be constructed from an ArrayRef<>. If the element count23/// is small, there is no copy and said storage *must* outlive us.24/// 2. it is immutable, the way it was constructed it will stay.25template <typename T, unsigned SmallSize> class ImmutableSmallSet {26 ArrayRef<T> Vector;27 llvm::DenseSet<T> Set;28 29 static_assert(SmallSize <= 32, "N should be small");30 31 bool isSmall() const { return Set.empty(); }32 33public:34 using size_type = size_t;35 36 ImmutableSmallSet() = delete;37 ImmutableSmallSet(const ImmutableSmallSet &) = delete;38 ImmutableSmallSet(ImmutableSmallSet &&) = delete;39 T &operator=(const ImmutableSmallSet &) = delete;40 T &operator=(ImmutableSmallSet &&) = delete;41 42 // WARNING: Storage *must* outlive us if we decide that the size is small.43 ImmutableSmallSet(ArrayRef<T> Storage) {44 // Is size small-enough to just keep using the existing storage?45 if (Storage.size() <= SmallSize) {46 Vector = Storage;47 return;48 }49 50 // We've decided that it isn't performant to keep using vector.51 // Let's migrate the data into Set.52 Set.reserve(Storage.size());53 Set.insert_range(Storage);54 }55 56 /// count - Return 1 if the element is in the set, 0 otherwise.57 size_type count(const T &V) const {58 if (isSmall()) {59 // Since the collection is small, just do a linear search.60 return llvm::is_contained(Vector, V) ? 1 : 0;61 }62 63 return Set.count(V);64 }65};66 67/// Much like SmallSetVector, but with one difference:68/// when the size is \p SmallSize or less, when checking whether an element is69/// already in the set or not, we perform linear search over the vector,70/// but if the size is larger than \p SmallSize, we look in set.71/// FIXME: upstream this into SetVector/SmallSetVector itself.72template <typename T, unsigned SmallSize> class SmartSmallSetVector {73public:74 using size_type = size_t;75 76private:77 SmallVector<T, SmallSize> Vector;78 llvm::DenseSet<T> Set;79 80 static_assert(SmallSize <= 32, "N should be small");81 82 // Are we still using Vector for uniqness tracking?83 bool isSmall() const { return Set.empty(); }84 85 // Will one more entry cause Vector to switch away from small-size storage?86 bool entiretyOfVectorSmallSizeIsOccupied() const {87 assert(isSmall() && Vector.size() <= SmallSize &&88 "Shouldn't ask if we have already [should have] migrated into Set.");89 return Vector.size() == SmallSize;90 }91 92 void populateSet() {93 assert(Set.empty() && "Should not have already utilized the Set.");94 // Magical growth factor prediction - to how many elements do we expect to95 // sanely grow after switching away from small-size storage?96 const size_t NewMaxElts = 4 * Vector.size();97 Vector.reserve(NewMaxElts);98 Set.reserve(NewMaxElts);99 Set.insert_range(Vector);100 }101 102 /// count - Return 1 if the element is in the set, 0 otherwise.103 size_type count(const T &V) const {104 if (isSmall()) {105 // Since the collection is small, just do a linear search.106 return llvm::is_contained(Vector, V) ? 1 : 0;107 }108 // Look-up in the Set.109 return Set.count(V);110 }111 112 bool setInsert(const T &V) {113 if (count(V) != 0)114 return false; // Already exists.115 // Does not exist, Can/need to record it.116 if (isSmall()) { // Are we still using Vector for uniqness tracking?117 // Will one more entry fit within small-sized Vector?118 if (!entiretyOfVectorSmallSizeIsOccupied())119 return true; // We'll insert into vector right afterwards anyway.120 // Time to switch to Set.121 populateSet();122 }123 // Set time!124 // Note that this must be after `populateSet()` might have been called.125 const bool SetInsertionSucceeded = Set.insert(V).second;126 (void)SetInsertionSucceeded;127 assert(SetInsertionSucceeded && "We did check that no such value existed");128 return true;129 }130 131public:132 /// Insert a new element into the SmartSmallSetVector.133 /// \returns true if the element was inserted into the SmartSmallSetVector.134 bool insert(const T &X) {135 const bool Result = setInsert(X);136 if (Result)137 Vector.push_back(X);138 return Result;139 }140 141 /// Clear the SmartSmallSetVector and return the underlying vector.142 decltype(Vector) takeVector() {143 Set.clear();144 return std::move(Vector);145 }146};147 148constexpr unsigned SmallCallStackSize = 16;149constexpr unsigned SmallSCCSize = 32;150 151using CallStackTy =152 llvm::SmallVector<CallGraphNode::CallRecord, SmallCallStackSize>;153 154} // namespace155 156// In given SCC, find *some* call stack that will be cyclic.157// This will only find *one* such stack, it might not be the smallest one,158// and there may be other loops.159static CallStackTy pathfindSomeCycle(ArrayRef<CallGraphNode *> SCC) {160 // We'll need to be able to performantly look up whether some CallGraphNode161 // is in SCC or not, so cache all the SCC elements in a set.162 const ImmutableSmallSet<CallGraphNode *, SmallSCCSize> SCCElts(SCC);163 164 // Is node N part if the current SCC?165 auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) {166 return SCCElts.count(N) != 0;167 };168 169 // Track the call stack that will cause a cycle.170 SmartSmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize>171 CallStackSet;172 173 // Arbitrarily take the first element of SCC as entry point.174 CallGraphNode::CallRecord EntryNode(SCC.front(), /*CallExpr=*/nullptr);175 // Continue recursing into subsequent callees that are part of this SCC,176 // and are thus known to be part of the call graph loop, until loop forms.177 CallGraphNode::CallRecord *Node = &EntryNode;178 while (true) {179 // Did we see this node before?180 if (!CallStackSet.insert(*Node))181 break; // Cycle completed! Note that didn't insert the node into stack!182 // Else, perform depth-first traversal: out of all callees, pick first one183 // that is part of this SCC. This is not guaranteed to yield shortest cycle.184 Node = llvm::find_if(Node->Callee->callees(), NodeIsPartOfSCC);185 }186 187 // Note that we failed to insert the last node, that completes the cycle.188 // But we really want to have it. So insert it manually into stack only.189 CallStackTy CallStack = CallStackSet.takeVector();190 CallStack.emplace_back(*Node);191 192 return CallStack;193}194 195void NoRecursionCheck::registerMatchers(MatchFinder *Finder) {196 Finder->addMatcher(translationUnitDecl().bind("TUDecl"), this);197}198 199void NoRecursionCheck::handleSCC(ArrayRef<CallGraphNode *> SCC) {200 assert(!SCC.empty() && "Empty SCC does not make sense.");201 202 // First of all, call out every strongly connected function.203 for (const CallGraphNode *N : SCC) {204 const FunctionDecl *D = N->getDefinition();205 diag(D->getLocation(), "function %0 is within a recursive call chain") << D;206 }207 208 // Now, SCC only tells us about strongly connected function declarations in209 // the call graph. It doesn't *really* tell us about the cycles they form.210 // And there may be more than one cycle in SCC.211 // So let's form a call stack that eventually exposes *some* cycle.212 const CallStackTy EventuallyCyclicCallStack = pathfindSomeCycle(SCC);213 assert(!EventuallyCyclicCallStack.empty() && "We should've found the cycle");214 215 // While last node of the call stack does cause a loop, due to the way we216 // pathfind the cycle, the loop does not necessarily begin at the first node217 // of the call stack, so drop front nodes of the call stack until it does.218 const auto CyclicCallStack =219 ArrayRef<CallGraphNode::CallRecord>(EventuallyCyclicCallStack)220 .drop_until([LastNode = EventuallyCyclicCallStack.back()](221 CallGraphNode::CallRecord FrontNode) {222 return FrontNode == LastNode;223 });224 assert(CyclicCallStack.size() >= 2 && "Cycle requires at least 2 frames");225 226 // Which function we decided to be the entry point that lead to the recursion?227 const FunctionDecl *CycleEntryFn =228 CyclicCallStack.front().Callee->getDefinition();229 // And now, for ease of understanding, let's print the call sequence that230 // forms the cycle in question.231 diag(CycleEntryFn->getLocation(),232 "example recursive call chain, starting from function %0",233 DiagnosticIDs::Note)234 << CycleEntryFn;235 for (int CurFrame = 1, NumFrames = CyclicCallStack.size();236 CurFrame != NumFrames; ++CurFrame) {237 const CallGraphNode::CallRecord PrevNode = CyclicCallStack[CurFrame - 1];238 const CallGraphNode::CallRecord CurrNode = CyclicCallStack[CurFrame];239 240 Decl *PrevDecl = PrevNode.Callee->getDecl();241 Decl *CurrDecl = CurrNode.Callee->getDecl();242 243 diag(CurrNode.CallExpr->getBeginLoc(),244 "Frame #%0: function %1 calls function %2 here:", DiagnosticIDs::Note)245 << CurFrame << cast<NamedDecl>(PrevDecl) << cast<NamedDecl>(CurrDecl);246 }247 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);252}253 254void NoRecursionCheck::check(const MatchFinder::MatchResult &Result) {255 // Build call graph for the entire translation unit.256 const auto *TU = Result.Nodes.getNodeAs<TranslationUnitDecl>("TUDecl");257 CallGraph CG;258 CG.addToCallGraph(const_cast<TranslationUnitDecl *>(TU));259 260 // Look for cycles in call graph,261 // by looking for Strongly Connected Components (SCC's)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()) // We only care about cycles, not standalone nodes.266 continue;267 handleSCC(*SCCI);268 }269}270 271} // namespace clang::tidy::misc272