Index: clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp =================================================================== --- clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp +++ clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp @@ -11,6 +11,9 @@ #include "clang/AST/ASTContext.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h" +#include "clang/Analysis/CallGraph.h" +#include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/SmallVector.h" using namespace clang::ast_matchers; using clang::tidy::utils::hasPtrOrReferenceInFunc; @@ -146,6 +149,110 @@ return false; } +/// populates the set `Callees` with all function (and objc method) declarations +/// called in `StmtNode` if all visited call sites have resolved call targets. +/// +/// \return true iff all `CallExprs` visited have callees; false otherwise +/// indicating there is an unresolved indirect call. +static bool populateCallees(const Stmt *StmtNode, + llvm::SmallSet &Callees) { + if (const CallExpr *Call = dyn_cast(StmtNode)) { + const auto *Callee = Call->getDirectCallee(); + + if (!Callee) + return false; // unresolved call + Callees.insert(Callee->getCanonicalDecl()); + } + if (const ObjCMessageExpr *Call = dyn_cast(StmtNode)) { + const auto *Callee = Call->getMethodDecl(); + + if (!Callee) + return false; // unresolved call + Callees.insert(Callee->getCanonicalDecl()); + } + for (const Stmt *Child : StmtNode->children()) + if (Child && !populateCallees(Child, Callees)) + return false; + return true; +} + +/// returns true iff `SCC` contains `Func` and its' function set overlaps with +/// `Callees` +static bool overlap(ArrayRef SCC, + const llvm::SmallSet &Callees, + const Decl *Func) { + bool ContainsFunc = false, Overlap = false; + + for (CallGraphNode *GNode : SCC) { + const auto *CanDecl = GNode->getDecl()->getCanonicalDecl(); + + ContainsFunc = ContainsFunc || (CanDecl == Func); + Overlap = Overlap || Callees.contains(CanDecl); + if (ContainsFunc && Overlap) + return true; + } + return ContainsFunc && Overlap; +} + +/// returns true iff `Cond` involves at least one static local variable. +static bool hasStaticLocalVariable(const Stmt *Cond) { + if (const auto *DRE = dyn_cast(Cond)) + if (const auto *VD = dyn_cast(DRE->getDecl())) + if (VD->isStaticLocal()) + return true; + for (const Stmt *Child : Cond->children()) + if (Child && hasStaticLocalVariable(Child)) + return true; + return false; +} + +/// Tests if the loop condition `Cond` involves static local variables and +/// the enclosing function `Func` is recursive. +/// +/// \code +/// void f() { +/// static int i = 10; +/// i--; +/// while (i >= 0) f(); +/// } +/// \endcode +/// The example above is NOT an infinite loop. +static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond, + const Stmt *LoopStmt, + const Decl *Func, + const ASTContext *Ctx) { + if (!hasStaticLocalVariable(Cond)) + return false; + + llvm::SmallSet CalleesInLoop; + + if (!populateCallees(LoopStmt, CalleesInLoop)) { + // If there are unresolved indirect calls, we assume there could + // be recursion so to avoid false alarm. + return true; + } + if (CalleesInLoop.empty()) + return false; + + TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl(); + CallGraph CG; + + CG.addToCallGraph(TUDecl); + // For each `SCC` containing `Func`, if functions in the `SCC` + // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`. + for (llvm::scc_iterator SCCI = llvm::scc_begin(&CG), + SCCE = llvm::scc_end(&CG); + SCCI != SCCE; ++SCCI) { + if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes. + continue; + // `SCC`s are mutually disjoint, so there will be no redundancy in + // comparing `SCC` with the callee set one by one. + if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl())) + return true; + } + return false; +} + void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) { const auto LoopCondition = allOf( hasCondition( @@ -182,6 +289,9 @@ if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context)) return; + if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func, + Result.Context)) + return; std::string CondVarNames = getCondVarNames(Cond); if (ShouldHaveConditionVariables && CondVarNames.empty()) Index: clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.cpp =================================================================== --- clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.cpp +++ clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.cpp @@ -685,3 +685,29 @@ 0; }) x; } + +void test_local_static_recursion() { + static int i = 10; + int j = 0; + + i--; + while (i >= 0) + test_local_static_recursion(); // no warning, recursively decrement i + for (; i >= 0;) + test_local_static_recursion(); // no warning, recursively decrement i + for (; i + j >= 0;) + test_local_static_recursion(); // no warning, recursively decrement i + for (; i >= 0; i--) + ; // no warning, i decrements + while (j >= 0) + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (j) are updated in the loop body [bugprone-infinite-loop] + test_local_static_recursion(); + + int (*p)(int) = 0; + + while (i >= 0) + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + p = 0; + while (i >= 0) + p(0); // we don't know what p points to so no warning +} Index: clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.mm =================================================================== --- clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.mm +++ clang-tools-extra/test/clang-tidy/checkers/bugprone/infinite-loop.mm @@ -44,6 +44,27 @@ j++; } } + ++ (void)recursiveMethod { + static int i = 0; + + i++; + while (i < 10) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + [I classMethod]; + } + + id x = [[I alloc] init]; + + while (i < 10) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + [x instanceMethod]; + } + while (i < 10) { + // no warning, there is a recursive call that can mutate the static local variable + [I recursiveMethod]; + } +} @end void testArrayCount() {