ziqingluo-90 created this revision.
ziqingluo-90 added reviewers: NoQ, t-rasmud, usama54321, rsundahl, yln,
kubamracek, krispy1994, jkorous, delcypher, chrisdangelo, thetruestblue,
dcoughlin, aaron.ballman, alexfh, gribozavr, njames93, LegalizeAdulthood.
Herald added subscribers: carlosgalvezp, xazax.hun.
Herald added a project: All.
ziqingluo-90 requested review of this revision.
Herald added projects: clang, clang-tools-extra.
Herald added a subscriber: cfe-commits.
Fixing 2 bugs in the infinite loop checker:
Bug 1. Missing handling of noreturn attributes for ObjC nodes.
Bug 2. The checker reports a false positive for a loop whose condition
involves static local variables, which can be changed in recursion.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D128314
Files:
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
clang-tools-extra/test/clang-tidy/checkers/bugprone-infinite-loop-noreturn.mm
clang-tools-extra/test/clang-tidy/checkers/bugprone-infinite-loop.cpp
clang/include/clang/ASTMatchers/ASTMatchers.h
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<ObjCMethodDecl>,
+ 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<NoReturnAttr>() ||
+ Node.hasAttr<CXX11NoReturnAttr>() ||
+ Node.hasAttr<C11NoReturnAttr>(); }
+
+/// 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:
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-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/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<Stmt>
loopEndingStmt(internal::Matcher<Stmt> 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<QualType> isNoReturnFunType =
+ ignoringParens(functionType(typeHasNoReturnAttr()));
+ internal::Matcher<Decl> 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<const Decl*, 16> &Callees) {
+ if (const CallExpr *Call = dyn_cast<CallExpr>(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<ObjCMessageExpr>(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<CallGraphNode*> SCC,
+ const llvm::SmallSet<const Decl*, 16> &Callees,
+ const Decl *Func) {
+ bool containsFunc = false;
+ bool overlap = false;
+
+ for (llvm::ArrayRef<CallGraphNode*>::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<DeclRefExpr>(Cond))
+ if (const VarDecl * VD = dyn_cast<VarDecl>(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<const Decl *, 16> 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<CallGraph *> 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;
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
