szepet updated this revision to Diff 145160.
szepet marked 2 inline comments as done.
szepet added a comment.
Changes based on comments.
https://reviews.llvm.org/D40937
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,121 @@
+// 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: the condition variable (i) is not updated in the loop body [bugprone-infinite-loop]
+ j++;
+ }
+
+ do {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: the condition variable (i) is not updated in the loop body
+ j++;
+ } while (i < 10);
+
+ for (i = 0; i < 10; ++j) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: the condition variable (i) is not updated in the loop body
+ }
+}
+
+void simple_infinite_loop2() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+ while (i < Limit) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: none of the condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+ j++;
+ }
+
+ do {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: none of the condition variables (i, Limit) are updated in the loop body
+ j++;
+ } while (i < Limit);
+
+ for (i = 0; i < Limit; ++j) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: none of the condition variables (i, Limit) are updated in the loop body
+ }
+}
+
+void simple_not_infinite() {
+ 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 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 *p = &i;
+ while (i < Limit) { // We do not warn since the var 'i' is escaped but it is
+ // an actual error, since the pointer 'p' is increased.
+ *(p++);
+ }
+}
+
+void escape_after() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+
+ while (i < Limit) {
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: none of the condition variables (i, Limit) are updated in the loop body
+ }
+ int *p = &i;
+}
+
+int glob;
+void glob_var(int &x) {
+ int i = 0, Limit = 100;
+ while (x < Limit) { // Not an error since 'x' can be an alias of glob.
+ glob++;
+ }
+}
+
+void glob_var2() {
+ int i = 0, Limit = 100;
+ while (glob < Limit) { // Since 'glob' is declared out of the function we do not warn.
+ i++;
+ }
+}
+
+struct X {
+ void memberExpr_test(int i) {
+ while (i < m) { // False negative: No warning, since skipping the case where
+ // a memberExpr can be found in the condition.
+ ;
+ }
+ }
+
+ void memberExpr_test2(int i) {
+ while (i < m) {
+ --m;
+ }
+ }
+ int m;
+};
Index: docs/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -29,6 +29,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,30 @@
+.. title:: clang-tidy - bugprone-infinite-loop
+
+bugprone-infinite-loop
+======================
+
+Finds loops where none of the condition variables are updated in the body. This
+performs a very conservative check in order to avoid false positives and work
+only on integer types at the moment.
+
+Examples:
+
+.. code-block:: c++
+
+ void simple_infinite_loop() {
+ int i = 0;
+ int j = 0;
+ int Limit = 10;
+ while (i < Limit) { // Error, since none of the variables are updated.
+ j++;
+ }
+ }
+
+ void escape_before() {
+ int i = 0;
+ int Limit = 100;
+ int *p = &i;
+ while (i < Limit) { // Not an error, since p is alias of i.
+ *++p;
+ }
+ }
Index: docs/ReleaseNotes.rst
===================================================================
--- docs/ReleaseNotes.rst
+++ docs/ReleaseNotes.rst
@@ -70,6 +70,12 @@
Diagnoses comparisons that appear to be incorrectly placed in the argument to
the ``TEMP_FAILURE_RETRY`` macro.
+- New :doc:`bugprone-infinite-loop
+ <clang-tidy/checks/bugprone-infinite-loop>` check.
+
+ Warns on loops where none of the condition variables are updated in the
+ body.
+
- New :doc:`bugprone-parent-virtual-call
<clang-tidy/checks/bugprone-parent-virtual-call>` check.
Index: clang-tidy/bugprone/InfiniteLoopCheck.h
===================================================================
--- /dev/null
+++ clang-tidy/bugprone/InfiniteLoopCheck.h
@@ -0,0 +1,46 @@
+//===--- InfiniteLoopCheck.h - clang-tidy------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INFINITELOOPCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INFINITELOOPCHECK_H
+
+#include "../ClangTidy.h"
+#include "../utils/ExprSequence.h"
+
+using namespace clang::tidy::utils;
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+/// The check aims to find loops where none of the condition variables are
+/// updated in the body. This performs a very conservative check in order to
+/// avoid false positives and work only on integer types at the moment.
+///
+/// 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), PrevFunctionBody(nullptr),
+ Sequence(nullptr) {}
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+ bool updateSequence(Stmt *FunctionBody, ASTContext &ASTCtx);
+ const Stmt *PrevFunctionBody;
+ std::unique_ptr<ExprSequence> Sequence;
+};
+
+} // 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,197 @@
+//===--- InfiniteLoopCheck.cpp - clang-tidy -------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InfiniteLoopCheck.h"
+#include "../utils/ExprSequence.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/CFG.h"
+
+using namespace clang::ast_matchers;
+using namespace clang::tidy::utils;
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+static internal::Matcher<Expr> exprAccessToVar(const VarDecl *VD) {
+ return ignoringParenImpCasts(declRefExpr(hasDeclaration(equalsNode(VD))));
+}
+
+void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
+ const auto LoopEndingStmt =
+ stmt(anyOf(breakStmt(), returnStmt(), gotoStmt(), cxxThrowExpr()));
+
+ const auto LoopCondition =
+ allOf(hasCondition(expr().bind("condition")),
+ anyOf(hasAncestor(lambdaExpr().bind("containing-lambda")),
+ hasAncestor(functionDecl().bind("containing-func"))),
+ unless(hasBody(hasDescendant(LoopEndingStmt))));
+
+ Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
+ forStmt(LoopCondition)))
+ .bind("loop-stmt"),
+ this);
+}
+
+static internal::Matcher<Stmt>
+changeByOperator(internal::Matcher<Expr> ExprNodeMatcher) {
+ return anyOf(
+ unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
+ hasUnaryOperand(ignoringParenImpCasts(ExprNodeMatcher))),
+ binaryOperator(isAssignmentOperator(), hasLHS(ExprNodeMatcher)));
+}
+
+static internal::Matcher<Stmt>
+callByRef(internal::Matcher<Expr> ExprNodeMatcher) {
+ return callExpr(forEachArgumentWithParam(
+ ExprNodeMatcher,
+ parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
+}
+
+static internal::Matcher<Stmt>
+assignedToRef(internal::Matcher<Expr> ExprNodeMatcher) {
+ return declStmt(hasDescendant(
+ varDecl(allOf(hasType(referenceType()),
+ hasInitializer(anyOf(initListExpr(has(ExprNodeMatcher)),
+ ExprNodeMatcher))))));
+}
+
+static internal::Matcher<Stmt>
+getAddrTo(internal::Matcher<Expr> ExprNodeMatcher) {
+ return unaryOperator(hasOperatorName("&"), hasUnaryOperand(ExprNodeMatcher));
+}
+
+static internal::Matcher<Stmt> escapeStmt(const VarDecl *VD) {
+ // Escaping is covered as address-of operators, pass-by-ref function calls and
+ // reference initialization on the variable body.
+ return stmt(anyOf(callByRef(exprAccessToVar(VD)),
+ getAddrTo(exprAccessToVar(VD)),
+ assignedToRef(exprAccessToVar(VD))));
+}
+
+static internal::Matcher<Stmt>
+hasDescendantOrIsItselfStmt(internal::Matcher<Stmt> VarNodeMatcher) {
+ return anyOf(VarNodeMatcher, hasDescendant(VarNodeMatcher));
+}
+
+static internal::Matcher<Stmt> potentiallyModifyVarStmt(const VarDecl *VD) {
+ return hasDescendantOrIsItselfStmt(
+ anyOf(changeByOperator(exprAccessToVar(VD)), escapeStmt(VD)));
+}
+
+// In order to avoid unnecessary rebuilding of the CFG we check whether the
+// currently analyzed function is the same as the previous one. In this case
+// we can use the CFG and the created Sequence from that analysis instead of
+// constructing them again. We rely on the fact that clang-tidy visits the
+// matches of a function in a row.
+void InfiniteLoopCheck::updateSequence(Stmt *FunctionBody, ASTContext &ASTCtx) {
+ if (FunctionBody == PrevFunctionBody)
+ return;
+ PrevFunctionBody = FunctionBody;
+ CFG::BuildOptions Options;
+ Options.AddImplicitDtors = true;
+ Options.AddTemporaryDtors = true;
+ if (std::unique_ptr<CFG> TheCFG =
+ CFG::buildCFG(nullptr, FunctionBody, &ASTCtx, Options))
+ Sequence = llvm::make_unique<ExprSequence>(TheCFG.get(), &ASTCtx);
+ else
+ Sequence = std::unique_ptr<ExprSequence>();
+}
+
+void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
+ const auto *ContainingLambda =
+ Result.Nodes.getNodeAs<LambdaExpr>("containing-lambda");
+ const auto *ContainingFunc =
+ Result.Nodes.getNodeAs<FunctionDecl>("containing-func");
+ const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
+ const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
+ auto &ASTCtx = *Result.Context;
+
+ Stmt *FunctionBody = nullptr;
+ if (ContainingLambda)
+ FunctionBody = ContainingLambda->getBody();
+ else if (ContainingFunc)
+ FunctionBody = ContainingFunc->getBody();
+ else
+ return;
+
+ const auto CondVarMatches =
+ match(findAll(declRefExpr(to(varDecl().bind("condvar")))), *Cond, ASTCtx);
+
+ // Since MemberExprs can be modified by outer functions this case is excluded
+ // right now.
+ const auto MemberExprsInCond =
+ match(hasDescendantOrIsItselfStmt(memberExpr()), *Cond, ASTCtx);
+ if (!MemberExprsInCond.empty())
+ return;
+
+ updateSequence(FunctionBody, ASTCtx);
+
+ for (const auto &E : CondVarMatches) {
+ auto CondVar = E.getNodeAs<VarDecl>("condvar");
+ // TODO: handle cases with non-integer condition variables
+ if (!CondVar->getType().getTypePtr()->isIntegerType())
+ return;
+
+ // In case the loop potentially changes any of the condition variables we
+ // assume the loop is not infinite.
+ SmallVector<BoundNodes, 1> Match;
+ // In case of for loop we check the increment stmt and the body for changes
+ // (excluding the init stmt).
+ if (const auto ForLoop = dyn_cast<ForStmt>(LoopStmt)) {
+ if (ForLoop->getInc())
+ Match = match(potentiallyModifyVarStmt(CondVar), *ForLoop->getInc(),
+ ASTCtx);
+ if (Match.empty() && ForLoop->getBody())
+ Match = match(potentiallyModifyVarStmt(CondVar), *ForLoop->getBody(),
+ ASTCtx);
+ } else {
+ // In cases of while and do-while we can match the whole loop.
+ Match = match(potentiallyModifyVarStmt(CondVar), *LoopStmt, ASTCtx);
+ }
+ if (!Match.empty())
+ return;
+
+ // Skip the cases where any of the condition variables come from outside
+ // of the function in order to avoid false positives.
+ Match = match(stmt(hasDescendant(varDecl(equalsNode(CondVar)))),
+ *FunctionBody, ASTCtx);
+ if (Match.empty())
+ return;
+
+ // When a condition variable is escaped before the loop we skip since we
+ // have no precise pointer analysis and want to avoid false positives.
+ Match = match(
+ stmt(forEachDescendant(stmt(escapeStmt(CondVar)).bind("escStmt"))),
+ *FunctionBody, ASTCtx);
+
+ for (const auto &ES : Match) {
+ if (Sequence->potentiallyAfter(LoopStmt, ES.getNodeAs<Stmt>("escStmt")))
+ return;
+ }
+ }
+
+ // Creating the string containing the name of condition variables.
+ std::string CondVarNames;
+ for (const auto &CVM : CondVarMatches) {
+ if (!CondVarNames.empty())
+ CondVarNames.append(", ");
+ CondVarNames.append(CVM.getNodeAs<VarDecl>("condvar")->getNameAsString());
+ }
+
+ diag(LoopStmt->getLocStart(),
+ "%plural{1:the condition variable|:none of the condition variables}0 "
+ "(%1) %plural{1:is not|:are}0 updated in the loop body")
+ << (unsigned)CondVarMatches.size() << CondVarNames;
+}
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang
Index: clang-tidy/bugprone/CMakeLists.txt
===================================================================
--- clang-tidy/bugprone/CMakeLists.txt
+++ clang-tidy/bugprone/CMakeLists.txt
@@ -12,6 +12,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
@@ -20,6 +20,7 @@
#include "ForwardingReferenceOverloadCheck.h"
#include "InaccurateEraseCheck.h"
#include "IncorrectRoundingsCheck.h"
+#include "InfiniteLoopCheck.h"
#include "IntegerDivisionCheck.h"
#include "LambdaFunctionNameCheck.h"
#include "MacroParenthesesCheck.h"
@@ -75,6 +76,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
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
