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/SmallVector.h" +#include "llvm/ADT/SCCIterator.h" using namespace clang::ast_matchers; using clang::tidy::utils::hasPtrOrReferenceInFunc; @@ -21,10 +24,17 @@ static internal::Matcher loopEndingStmt(internal::Matcher Internal) { - // FIXME: Cover noreturn ObjC methods (and blocks?). - return stmt(anyOf( - mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal), - callExpr(Internal, callee(functionDecl(isNoReturn()))))); + internal::Matcher isNoReturnFunType = + ignoringParens(functionType(typeHasNoReturnAttr())); + internal::Matcher isNoReturnDecl = anyOf( + declHasNoReturnAttr(), + functionDecl(hasType(isNoReturnFunType)), + varDecl(hasType(blockPointerType(pointee(isNoReturnFunType))))); + + return stmt(anyOf(mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal), + callExpr(Internal, callee(functionDecl(isNoReturnDecl))), + objcMessageExpr(Internal, objcMessageCallee(isNoReturnDecl)), + callExpr(Internal, callee(varDecl(isNoReturnDecl))))); } /// Return whether `Var` was changed in `LoopStmt`. @@ -146,6 +156,118 @@ 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)) { + if (const Decl * Callee = Call->getDirectCallee()) { + const Decl * CanoCallee = Callee->getCanonicalDecl(); + + Callees.insert(CanoCallee); + } else + return false; // unresolved call + } + if (const ObjCMessageExpr *Call = dyn_cast(StmtNode)) { + if (const ObjCMethodDecl * Callee = Call->getMethodDecl()) { + const Decl * CanoCallee = Callee->getCanonicalDecl(); + + Callees.insert(CanoCallee); + } else + return false; // unresolved call + } + for (const Stmt * Child : StmtNode->children()) + if (Child && populateCallees(Child, Callees)) + continue; + else + 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; + bool overlap = false; + + for (llvm::ArrayRef::iterator EltI = SCC.begin(), + EltE = SCC.end(); + EltI != EltE; ++EltI) { + CallGraphNode * GNode = *EltI; + const Decl * CanoDecl = GNode->getDecl()->getCanonicalDecl(); + + containsFunc |= CanoDecl == Func; + overlap |= Callees.contains(CanoDecl); + 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 DeclRefExpr * DRE = dyn_cast(Cond)) + if (const VarDecl * 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 `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,7 +304,10 @@ 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()) return; Index: clang-tools-extra/test/clang-tidy/checkers/bugprone-infinite-loop-noreturn.mm =================================================================== --- /dev/null +++ clang-tools-extra/test/clang-tidy/checkers/bugprone-infinite-loop-noreturn.mm @@ -0,0 +1,66 @@ +// RUN: %check_clang_tidy %s bugprone-infinite-loop %t -- -- -fblocks +// RUN: %check_clang_tidy %s bugprone-infinite-loop %t -- -- -fblocks -fobjc-arc + +@interface I ++(void) foo; ++(void) bar; ++(void) baz __attribute__ ((noreturn)); ++(instancetype)alloc; +-(instancetype)init; +@end + +_Noreturn void term(); + +void plainCFunction() { + int i = 0; + int j = 0; + + while (i < 10) { + // no warning, function term has C noreturn attribute + term(); + } + while (i < 10) { + // no warning, class method baz has noreturn attribute + [I baz]; + } + while (i+j < 10) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, j) are updated in the loop body [bugprone-infinite-loop] + } + + void (^block)() = ^{}; + void __attribute__((noreturn)) (^block_nr)(void) = ^void __attribute__((noreturn))(void){throw "err";}; + + 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] + block(); + } + while (i < 10) { + // no warning, the block has "noreturn" arribute + block_nr(); + } +} + +@implementation I ++ (void) bar {} + ++ (void)foo { + static int i = 0; + + i++; + while (i < 10) { + // no warning, there is a recursive call that can mutate the static local variable + [I foo]; + } + + id x = [[I alloc] init]; + + while (i < 10) { + // no warning, cannot figure out what type x has + [x foo]; + } + 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 bar]; + } +} +@end 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,31 @@ 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/include/clang/ASTMatchers/ASTMatchers.h =================================================================== --- clang/include/clang/ASTMatchers/ASTMatchers.h +++ clang/include/clang/ASTMatchers/ASTMatchers.h @@ -3829,6 +3829,25 @@ InnerMatcher.matches(*ExprNode, Finder, Builder)); } +/// matches if ObjCMessageExpr's callee declaration matches +/// +/// Given +/// \code +/// @interface I: NSObject +/// +(void)foo; +/// @end +/// ... +/// [I foo] +/// \endcode +/// The example above matches \code [I foo] \endcode with +/// objcMessageExpr(objcMessageCallee(objcMethodDecl(hasName("foo")))) +AST_MATCHER_P(ObjCMessageExpr, objcMessageCallee, internal::Matcher, + InnerMatcher) { + const ObjCMethodDecl *msgDecl = Node.getMethodDecl(); + return (msgDecl != nullptr && + InnerMatcher.matches(*msgDecl, Finder, Builder)); +} + /// Matches if the call expression's callee's declaration matches the /// given matcher. /// @@ -5070,6 +5089,14 @@ /// \endcode AST_MATCHER(FunctionDecl, isNoReturn) { return Node.isNoReturn(); } +/// matches a Decl if it has a "no return" attribute of any kind +AST_MATCHER(Decl, declHasNoReturnAttr) { return Node.hasAttr() || + Node.hasAttr() || + Node.hasAttr(); } + +/// matches a FunctionType if the type includes the GNU no return attribute +AST_MATCHER(FunctionType, typeHasNoReturnAttr) {return Node.getNoReturnAttr();} + /// Matches the return type of a function declaration. /// /// Given: