baloghadamsoftware updated this revision to Diff 210070.
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,226 @@
+// 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]]:10: warning: None of the condition variables (i) are updated in the loop body [bugprone-infinite-loop]
+ j++;
+ }
+
+ do {
+ j++;
+ } while (i < 10);
+ // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: None of the condition variables (i) are updated in the loop body [bugprone-infinite-loop]
+
+ for (i = 0; i < 10; ++j) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: None of the 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]]:10: warning: None of the condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ j++;
+ }
+
+ do {
+ j++;
+ } while (i < Limit);
+ // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: None of the condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+
+ for (i = 0; i < Limit; ++j) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: None of the 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
+ ; // the condition part.
+}
+
+int any_function();
+
+void function_call() {
+ int i = 0;
+ while (i < any_function()) { // Not an error, since the function may return
+ // different values
+ }
+
+ do { // Not an error, since the function may return
+ // different values
+ } while (i < any_function());
+
+ for (i = 0; i < any_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]]:10: warning: None of the 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]]:10: warning: None of the 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 member_expr can be found in the 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.
+}
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,31 @@
+.. title:: clang-tidy - bugprone-infinite-loop
+
+bugprone-infinite-loop
+======================
+
+Checks for obvious infinite loops (loops where the condition variable is not
+changed at all).
+
+Detecting infinite loops by a finite program is well known to be impossible
+(Halting-problem). However there are some simple but common cases where it
+is possible: the loop condition is not changed in the loop at all. 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``)
+and all of the following conditions hold for every variable in the condition:
+
+- It is a local variable of the function.
+- It has no reference or pointer aliases before or inside the loop.
+- It is no member expression.
+
+Furthermore, the condition must not contain a function call to consider the loop
+as infinite since functions may return different values for different calls.
+
+For example, the following loop is considered as infinite since mistakenly
+`j` is incremented instead of `i`:
+
+.. 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.
+
+ Checks for 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 {
+
+/// Checks for 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,185 @@
+//===--- 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/Analysis/Analyses/ExprMutationAnalyzer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+static internal::Matcher<Stmt> loopEndingStmt() {
+ return stmt(anyOf(breakStmt(), returnStmt(), gotoStmt(), cxxThrowExpr()));
+}
+
+static bool isAccessForVar(const Stmt *St, const VarDecl *Var) {
+ if (const auto *DRE = dyn_cast<DeclRefExpr>(St))
+ return DRE->getDecl() == Var;
+
+ return false;
+}
+
+static bool isPtrOrReferenceForVar(const Stmt *St, const VarDecl *Var) {
+ if (const auto *DS = dyn_cast<DeclStmt>(St)) {
+ 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>(St)) {
+ if (UnOp->getOpcode() == UO_AddrOf)
+ return isAccessForVar(UnOp->getSubExpr(), Var);
+ }
+
+ return false;
+}
+
+static bool hasPtrOrReferenceBefore(const Stmt *St, const Stmt *LoopStmt,
+ const VarDecl *Var) {
+ if (isPtrOrReferenceForVar(St, Var))
+ return true;
+
+ for (const Stmt *Child : St->children()) {
+ if (!Child)
+ continue;
+
+ if (Child == LoopStmt)
+ return false;
+
+ if (hasPtrOrReferenceBefore(Child, LoopStmt, Var))
+ return true;
+ }
+
+ return false;
+}
+
+static bool hasPtrOrReferenceBefore(const FunctionDecl *Func,
+ const Stmt *LoopStmt, const VarDecl *Var) {
+ return hasPtrOrReferenceBefore(Func->getBody(), LoopStmt, Var);
+}
+
+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);
+}
+
+static bool isAtLeastOneCondVarChanged(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().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;
+ }
+
+ for (const Stmt *Child : Cond->children()) {
+ if (!Child)
+ continue;
+
+ if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
+ return true;
+ }
+ return false;
+}
+
+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;
+}
+
+static const DeclRefExpr *getFirstCondVar(const Stmt *Cond) {
+ if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
+ if (isa<VarDecl>(DRE->getDecl()))
+ return DRE;
+ }
+
+ for (const Stmt *Child : Cond->children()) {
+ if (!Child)
+ continue;
+
+ if (const DeclRefExpr *DRE = getFirstCondVar(Child))
+ return DRE;
+ }
+ return nullptr;
+}
+
+void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
+ const auto LoopCondition =
+ allOf(hasCondition(expr().bind("condition")),
+ unless(hasBody(hasDescendant(loopEndingStmt()))));
+
+ Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
+ forStmt(LoopCondition)),
+ forFunction(functionDecl().bind("func")))
+ .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(getFirstCondVar(Cond)->getLocation(),
+ "None of the 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
