baloghadamsoftware updated this revision to Diff 211933.
baloghadamsoftware marked 3 inline comments as done.
baloghadamsoftware added a comment.
Updated according to the comments.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D64736/new/
https://reviews.llvm.org/D64736
Files:
clang-tidy/bugprone/BugproneTidyModule.cpp
clang-tidy/bugprone/CMakeLists.txt
clang-tidy/bugprone/InfiniteLoopCheck.cpp
clang-tidy/bugprone/InfiniteLoopCheck.h
docs/ReleaseNotes.rst
docs/clang-tidy/checks/bugprone-infinite-loop.rst
docs/clang-tidy/checks/list.rst
test/clang-tidy/bugprone-infinite-loop.cpp
Index: test/clang-tidy/bugprone-infinite-loop.cpp
===================================================================
--- /dev/null
+++ test/clang-tidy/bugprone-infinite-loop.cpp
@@ -0,0 +1,322 @@
+// RUN: %check_clang_tidy %s bugprone-infinite-loop %t
+
+void simple_infinite_loop1() {
+ int i = 0;
+ int j = 0;
+ 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]
+ j++;
+ }
+
+ do {
+ // 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]
+ j++;
+ } while (i < 10);
+
+ for (i = 0; i < 10; ++j) {
+ // 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]
+ }
+}
+
+void simple_infinite_loop2() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+ while (i < Limit) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ j++;
+ }
+
+ do {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ j++;
+ } while (i < Limit);
+
+ for (i = 0; i < Limit; ++j) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ }
+}
+
+void simple_not_infinite1() {
+ int i = 0;
+ int Limit = 100;
+ while (i < Limit) {
+ // Not an error since 'Limit' is updated.
+ Limit--;
+ }
+ do {
+ Limit--;
+ } while (i < Limit);
+
+ for (i = 0; i < Limit; Limit--) {
+ }
+}
+
+void simple_not_infinite2() {
+ for (int i = 10; i-- > 0;) {
+ // Not an error, since loop variable is modified in its condition part.
+ }
+}
+
+int unknown_function();
+
+void function_call() {
+ int i = 0;
+ while (i < unknown_function()) {
+ // Not an error, since the function may return different values.
+ }
+
+ do {
+ // Not an error, since the function may return different values.
+ } while (i < unknown_function());
+
+ for (i = 0; i < unknown_function();) {
+ // Not an error, since the function may return different values.
+ }
+}
+
+void escape_before1() {
+ int i = 0;
+ int Limit = 100;
+ int *p = &i;
+ while (i < Limit) {
+ // Not an error, since *p is alias of i.
+ (*p)++;
+ }
+
+ do {
+ (*p)++;
+ } while (i < Limit);
+
+ for (i = 0; i < Limit; ++(*p)) {
+ }
+}
+
+void escape_before2() {
+ int i = 0;
+ int Limit = 100;
+ int &ii = i;
+ while (i < Limit) {
+ // Not an error, since ii is alias of i.
+ ii++;
+ }
+
+ do {
+ ii++;
+ } while (i < Limit);
+
+ for (i = 0; i < Limit; ++ii) {
+ }
+}
+
+void escape_inside1() {
+ int i = 0;
+ int Limit = 100;
+ int *p = &i;
+ while (i < Limit) {
+ // Not an error, since *p is alias of i.
+ int *p = &i;
+ (*p)++;
+ }
+
+ do {
+ int *p = &i;
+ (*p)++;
+ } while (i < Limit);
+}
+
+void escape_inside2() {
+ int i = 0;
+ int Limit = 100;
+ while (i < Limit) {
+ // Not an error, since ii is alias of i.
+ int &ii = i;
+ ii++;
+ }
+
+ do {
+ int &ii = i;
+ ii++;
+ } while (i < Limit);
+}
+
+void escape_after1() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+
+ while (i < Limit) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ }
+ int *p = &i;
+}
+
+void escape_after2() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+
+ while (i < Limit) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ }
+ int &ii = i;
+}
+
+int glob;
+
+void global1(int &x) {
+ int i = 0, Limit = 100;
+ while (x < Limit) {
+ // Not an error since 'x' can be an alias of 'glob'.
+ glob++;
+ }
+}
+
+void global2() {
+ int i = 0, Limit = 100;
+ while (glob < Limit) {
+ // Since 'glob' is declared out of the function we do not warn.
+ i++;
+ }
+}
+
+struct X {
+ int m;
+
+ void change_m();
+
+ void member_expr1(int i) {
+ while (i < m) {
+ // False negative: No warning, since skipping the case where a struct or
+ // class can be found in its condition.
+ ;
+ }
+ }
+
+ void member_expr2(int i) {
+ while (i < m) {
+ --m;
+ }
+ }
+
+ void member_expr3(int i) {
+ while (i < m) {
+ change_m();
+ }
+ }
+};
+
+void array_index() {
+ int i = 0;
+ int v[10];
+ while (i < 10) {
+ v[i++] = 0;
+ }
+
+ i = 0;
+ do {
+ v[i++] = 0;
+ } while (i < 9);
+
+ for (i = 0; i < 10;) {
+ v[i++] = 0;
+ }
+
+ for (i = 0; i < 10; v[i++] = 0) {
+ }
+}
+
+void no_loop_variable() {
+ while (0)
+ ;
+ while (1)
+ ; //FIXME: We expect report in this case.
+}
+
+void volatile_in_condition() {
+ volatile int cond = 0;
+ while (!cond) {
+ }
+}
+
+namespace std {
+template<typename T> class atomic {
+ T val;
+public:
+ atomic(T v): val(v) {};
+ operator T() { return val; };
+};
+}
+
+void atomic_in_condition() {
+ std::atomic<int> cond = 0;
+ while (!cond) {
+ }
+}
+
+void loop_exit1() {
+ int i = 0;
+ while (i) {
+ if (unknown_function())
+ break;
+ }
+}
+
+void loop_exit2() {
+ int i = 0;
+ while (i) {
+ if (unknown_function())
+ return;
+ }
+}
+
+void loop_exit3() {
+ int i = 0;
+ while (i) {
+ if (unknown_function())
+ goto end;
+ }
+ end:
+ ;
+}
+
+void loop_exit4() {
+ int i = 0;
+ while (i) {
+ if (unknown_function())
+ throw 1;
+ }
+}
+
+[[noreturn]] void exit(int);
+
+void loop_exit5() {
+ int i = 0;
+ while (i) {
+ if (unknown_function())
+ exit(1);
+ }
+}
+
+void loop_exit_in_lambda() {
+ int i = 0;
+ while (i) {
+ // 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]
+ auto l = []() { return 0; };
+ }
+}
+
+void lambda_capture() {
+ int i = 0;
+ int Limit = 100;
+ int *p = &i;
+ while (i < Limit) {
+ // Not an error, since i is captured by reference in a lambda.
+ auto l = [&i]() { ++i; };
+ }
+
+ do {
+ int *p = &i;
+ (*p)++;
+ } while (i < Limit);
+}
Index: docs/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -49,6 +49,7 @@
bugprone-forwarding-reference-overload
bugprone-inaccurate-erase
bugprone-incorrect-roundings
+ bugprone-infinite-loop
bugprone-integer-division
bugprone-lambda-function-name
bugprone-macro-parentheses
Index: docs/clang-tidy/checks/bugprone-infinite-loop.rst
===================================================================
--- /dev/null
+++ docs/clang-tidy/checks/bugprone-infinite-loop.rst
@@ -0,0 +1,32 @@
+.. title:: clang-tidy - bugprone-infinite-loop
+
+bugprone-infinite-loop
+======================
+
+Finds obvious infinite loops (loops where the condition variable is not changed
+at all).
+
+Finding infinite loops is well-known to be impossible (halting problem).
+However, it is possible to detect some obvious infinite loops, for example, if
+the loop condition is not changed. This check detects such loops. A loop is
+considered as infinite if it does not have any loop exit statement (``break``,
+``continue``, ``goto``, ``return``, ``throw`` or a call to a function called as
+``[[noreturn]]``) and all of the following conditions hold for every variable in
+the condition:
+
+- It is a local variable.
+- It has no reference or pointer aliases before or inside the loop.
+- It is not a structure or class member.
+
+Furthermore, the condition must not contain a function call to consider the loop
+infinite since functions may return different values for different calls.
+
+For example, the following loop is considered infinite `i` is not changed in
+the body:
+
+.. code-block:: c++
+
+ int i = 0, j = 0;
+ while (i < 10) {
+ ++j;
+ }
Index: docs/ReleaseNotes.rst
===================================================================
--- docs/ReleaseNotes.rst
+++ docs/ReleaseNotes.rst
@@ -111,6 +111,12 @@
This checks ensures that ``pipe2()`` is called with the O_CLOEXEC flag.
+- New :doc:`bugprone-infinite-loop
+ <clang-tidy/checks/bugprone-infinite-loop>` check.
+
+ Finds obvious infinite loops (loops where the condition variable is not
+ changed at all).
+
- New :doc:`bugprone-unhandled-self-assignment
<clang-tidy/checks/bugprone-unhandled-self-assignment>` check.
Index: clang-tidy/bugprone/InfiniteLoopCheck.h
===================================================================
--- /dev/null
+++ clang-tidy/bugprone/InfiniteLoopCheck.h
@@ -0,0 +1,35 @@
+//===--- InfiniteLoopCheck.h - clang-tidy -----------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INFINITELOOPCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INFINITELOOPCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+/// Finds obvious infinite loops (loops where the condition variable is
+/// not changed at all).
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/bugprone-infinite-loop.html
+class InfiniteLoopCheck : public ClangTidyCheck {
+public:
+ InfiniteLoopCheck(StringRef Name, ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context) {}
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INFINITELOOPCHECK_H
Index: clang-tidy/bugprone/InfiniteLoopCheck.cpp
===================================================================
--- /dev/null
+++ clang-tidy/bugprone/InfiniteLoopCheck.cpp
@@ -0,0 +1,195 @@
+//===--- InfiniteLoopCheck.cpp - clang-tidy -------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InfiniteLoopCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+static internal::Matcher<Stmt>
+loopEndingStmt(internal::Matcher<Stmt> Internal) {
+ return stmt(anyOf(breakStmt(Internal), returnStmt(Internal),
+ gotoStmt(Internal), cxxThrowExpr(Internal),
+ callExpr(Internal, callee(functionDecl(isNoReturn())))));
+}
+
+/// \brief Return whether `S` is a reference to the declaration of `Var`.
+static bool isAccessForVar(const Stmt *S, const VarDecl *Var) {
+ if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
+ return DRE->getDecl() == Var;
+
+ return false;
+}
+
+/// \brief Return whether `Var` has a pointer of reference in `S`.
+static bool isPtrOrReferenceForVar(const Stmt *S, const VarDecl *Var) {
+ if (const auto *DS = dyn_cast<DeclStmt>(S)) {
+ for (const Decl *D : DS->getDeclGroup()) {
+ if (const auto *LeftVar = dyn_cast<VarDecl>(D)) {
+ if (LeftVar->hasInit() && LeftVar->getType()->isReferenceType()) {
+ return isAccessForVar(LeftVar->getInit(), Var);
+ }
+ }
+ }
+ } else if (const auto *UnOp = dyn_cast<UnaryOperator>(S)) {
+ if (UnOp->getOpcode() == UO_AddrOf)
+ return isAccessForVar(UnOp->getSubExpr(), Var);
+ }
+
+ return false;
+}
+
+/// \brief Return whether `Var` has a pointer of reference before `LoopStmt`
+/// in `S`.
+static bool hasPtrOrReferenceBefore(const Stmt *S, const Stmt *LoopStmt,
+ const VarDecl *Var) {
+ if (isPtrOrReferenceForVar(S, Var))
+ return true;
+
+ for (const Stmt *Child : S->children()) {
+ if (!Child)
+ continue;
+
+ if (Child == LoopStmt)
+ return false;
+
+ if (hasPtrOrReferenceBefore(Child, LoopStmt, Var))
+ return true;
+ }
+
+ return false;
+}
+
+/// \brief Return whether `Var` has a pointer of reference before `LoopStmt`
+/// in `Func`.
+static bool hasPtrOrReferenceBefore(const FunctionDecl *Func,
+ const Stmt *LoopStmt, const VarDecl *Var) {
+ return hasPtrOrReferenceBefore(Func->getBody(), LoopStmt, Var);
+}
+
+/// \brief Return whether `Var` was changed in `LoopStmt`.
+static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
+ ASTContext *Context) {
+ if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
+ return (ForLoop->getInc() &&
+ ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
+ .isMutated(Var)) ||
+ (ForLoop->getBody() &&
+ ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
+ .isMutated(Var)) ||
+ (ForLoop->getCond() &&
+ ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
+
+ return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
+}
+
+/// \brief Return whether `Cond` is a variable that is possibly changed in
+/// `LoopStmt`.
+static bool isVarThatIsPossiblyChanged(const FunctionDecl *Func,
+ const Stmt *LoopStmt, const Stmt *Cond,
+ ASTContext *Context) {
+ if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
+ if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
+ if (!Var->isLocalVarDeclOrParm())
+ return true;
+
+ if (Var->getType().isVolatileQualified())
+ return true;
+
+ if (!Var->getType().getTypePtr()->isIntegerType())
+ return true;
+
+ return hasPtrOrReferenceBefore(Func, LoopStmt, Var) ||
+ isChanged(LoopStmt, Var, Context);
+ // FIXME: Track references.
+ }
+ } else if (isa<MemberExpr>(Cond) || isa<CallExpr>(Cond)) {
+ // FIXME: Handle MemberExpr.
+ return true;
+ }
+
+ return false;
+}
+
+/// \brief Return whether at least one variable of `Cond` changed in `LoopStmt`.
+static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func,
+ const Stmt *LoopStmt, const Stmt *Cond,
+ ASTContext *Context) {
+ if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
+ return true;
+
+ for (const Stmt *Child : Cond->children()) {
+ if (!Child)
+ continue;
+
+ if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
+ return true;
+ }
+ return false;
+}
+
+/// \brief Return the variable names in `Cond`.
+static std::string getCondVarNames(const Stmt *Cond) {
+ if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
+ if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
+ return Var->getName();
+ }
+
+ std::string Result;
+ for (const Stmt *Child : Cond->children()) {
+ if (!Child)
+ continue;
+
+ std::string NewNames = getCondVarNames(Child);
+ if (!Result.empty() && !NewNames.empty())
+ Result += ", ";
+ Result += NewNames;
+ }
+ return Result;
+}
+
+void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
+ const auto LoopCondition = allOf(
+ hasCondition(
+ expr(forFunction(functionDecl().bind("func"))).bind("condition")),
+ unless(hasBody(hasDescendant(
+ loopEndingStmt(forFunction(equalsBoundNode("func")))))));
+
+ Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
+ forStmt(LoopCondition)))
+ .bind("loop-stmt"),
+ this);
+}
+
+void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
+ const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
+ const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
+ const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
+
+ if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
+ return;
+
+ std::string CondVarNames = getCondVarNames(Cond);
+ if (CondVarNames.empty())
+ return;
+
+ diag(LoopStmt->getBeginLoc(),
+ "this loop is infinite; none of its condition variables (%0)"
+ " are updated in the loop body")
+ << CondVarNames;
+}
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang
Index: clang-tidy/bugprone/CMakeLists.txt
===================================================================
--- clang-tidy/bugprone/CMakeLists.txt
+++ clang-tidy/bugprone/CMakeLists.txt
@@ -14,6 +14,7 @@
ForwardingReferenceOverloadCheck.cpp
InaccurateEraseCheck.cpp
IncorrectRoundingsCheck.cpp
+ InfiniteLoopCheck.cpp
IntegerDivisionCheck.cpp
LambdaFunctionNameCheck.cpp
MacroParenthesesCheck.cpp
Index: clang-tidy/bugprone/BugproneTidyModule.cpp
===================================================================
--- clang-tidy/bugprone/BugproneTidyModule.cpp
+++ clang-tidy/bugprone/BugproneTidyModule.cpp
@@ -22,6 +22,7 @@
#include "ForwardingReferenceOverloadCheck.h"
#include "InaccurateEraseCheck.h"
#include "IncorrectRoundingsCheck.h"
+#include "InfiniteLoopCheck.h"
#include "IntegerDivisionCheck.h"
#include "LambdaFunctionNameCheck.h"
#include "MacroParenthesesCheck.h"
@@ -85,6 +86,8 @@
"bugprone-inaccurate-erase");
CheckFactories.registerCheck<IncorrectRoundingsCheck>(
"bugprone-incorrect-roundings");
+ CheckFactories.registerCheck<InfiniteLoopCheck>(
+ "bugprone-infinite-loop");
CheckFactories.registerCheck<IntegerDivisionCheck>(
"bugprone-integer-division");
CheckFactories.registerCheck<LambdaFunctionNameCheck>(
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
