szepet updated this revision to Diff 125965.
szepet marked 9 inline comments as done.
szepet added a comment.
Updates based on comments.
https://reviews.llvm.org/D40937
Files:
clang-tidy/misc/CMakeLists.txt
clang-tidy/misc/InfiniteLoopCheck.cpp
clang-tidy/misc/InfiniteLoopCheck.h
clang-tidy/misc/MiscTidyModule.cpp
docs/ReleaseNotes.rst
docs/clang-tidy/checks/list.rst
docs/clang-tidy/checks/misc-infinite-loop.rst
test/clang-tidy/misc-infinite-loop.cpp
Index: test/clang-tidy/misc-infinite-loop.cpp
===================================================================
--- /dev/null
+++ test/clang-tidy/misc-infinite-loop.cpp
@@ -0,0 +1,114 @@
+// RUN: %check_clang_tidy %s misc-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 [misc-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 [misc-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;
+ int 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++;
+ }
+}
+
+bool foo(int n);
+void fun_call() {
+ int i = 0;
+ int Limit = 100;
+ while (foo(i)) { // Do not warn, since foo can have state.
+ Limit--;
+ }
+}
Index: docs/clang-tidy/checks/misc-infinite-loop.rst
===================================================================
--- /dev/null
+++ docs/clang-tidy/checks/misc-infinite-loop.rst
@@ -0,0 +1,30 @@
+.. title:: clang-tidy - misc-infinite-loop
+
+misc-infinite-loop
+==================
+
+The check 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/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -120,6 +120,7 @@
misc-definitions-in-headers
misc-forwarding-reference-overload
misc-incorrect-roundings
+ misc-infinite-loop
misc-lambda-function-name
misc-macro-parentheses
misc-macro-repeated-side-effects
Index: docs/ReleaseNotes.rst
===================================================================
--- docs/ReleaseNotes.rst
+++ docs/ReleaseNotes.rst
@@ -158,6 +158,11 @@
Finds uses of bitwise operations on signed integer types, which may lead to
undefined or implementation defined behaviour.
+- New `misc-infinite-loop
+ <http://clang.llvm.org/extra/clang-tidy/checks/misc-infinite-loop.html>`_ check
+
+ Finds loops where none of the condition variables are updated in the body.
+
- New `objc-avoid-nserror-init
<http://clang.llvm.org/extra/clang-tidy/checks/objc-avoid-nserror-init.html>`_ check
Index: clang-tidy/misc/MiscTidyModule.cpp
===================================================================
--- clang-tidy/misc/MiscTidyModule.cpp
+++ clang-tidy/misc/MiscTidyModule.cpp
@@ -13,6 +13,7 @@
#include "DefinitionsInHeadersCheck.h"
#include "ForwardingReferenceOverloadCheck.h"
#include "IncorrectRoundings.h"
+#include "InfiniteLoopCheck.h"
#include "LambdaFunctionNameCheck.h"
#include "MacroParenthesesCheck.h"
#include "MacroRepeatedSideEffectsCheck.h"
@@ -50,6 +51,8 @@
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
CheckFactories.registerCheck<ForwardingReferenceOverloadCheck>(
"misc-forwarding-reference-overload");
+ CheckFactories.registerCheck<InfiniteLoopCheck>(
+ "misc-infinite-loop");
CheckFactories.registerCheck<LambdaFunctionNameCheck>(
"misc-lambda-function-name");
CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
Index: clang-tidy/misc/InfiniteLoopCheck.h
===================================================================
--- /dev/null
+++ clang-tidy/misc/InfiniteLoopCheck.h
@@ -0,0 +1,37 @@
+//===--- 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_MISC_INFINITELOOPCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INFINITELOOPCHECK_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// 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/misc-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 misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INFINITELOOPCHECK_H
Index: clang-tidy/misc/InfiniteLoopCheck.cpp
===================================================================
--- /dev/null
+++ clang-tidy/misc/InfiniteLoopCheck.cpp
@@ -0,0 +1,196 @@
+//===--- 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 misc {
+
+static internal::Matcher<Stmt> loopEndingStmt() {
+ return stmt(anyOf(breakStmt(), returnStmt(), gotoStmt(), cxxThrowExpr()));
+}
+
+void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
+ const auto loopCondition = []() {
+ return allOf(
+ hasCondition(expr().bind("condition")),
+ anyOf(hasAncestor(lambdaExpr().bind("containing-lambda")),
+ hasAncestor(functionDecl().bind("containing-func"))),
+ unless(
+ anyOf(hasBody(hasDescendant(loopEndingStmt())),
+ // Exclude the cases where the condition contain function
+ // calls. They can possibly change the program state.
+ hasCondition(anyOf(callExpr(), hasDescendant(callExpr()))))));
+ };
+
+ Finder->addMatcher(
+ stmt(anyOf(whileStmt(loopCondition()), doStmt(loopCondition()),
+ forStmt(loopCondition())))
+ .bind("loop-stmt"),
+ this);
+}
+
+static internal::Matcher<Stmt>
+changeByOperator(internal::Matcher<Decl> VarNodeMatcher) {
+ return anyOf(
+ unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
+ hasUnaryOperand(ignoringParenImpCasts(
+ declRefExpr(to(varDecl(VarNodeMatcher)))))),
+ binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="),
+ hasOperatorName("/="), hasOperatorName("*="),
+ hasOperatorName("-="), hasOperatorName("%="),
+ hasOperatorName("&="), hasOperatorName("|="),
+ hasOperatorName("^="), hasOperatorName("<<="),
+ hasOperatorName(">>=")),
+ hasLHS(ignoringParenImpCasts(
+ declRefExpr(to(varDecl(VarNodeMatcher)))))));
+}
+
+static internal::Matcher<Stmt>
+callByRef(internal::Matcher<Decl> VarNodeMatcher) {
+ return callExpr(forEachArgumentWithParam(
+ declRefExpr(to(varDecl(VarNodeMatcher))),
+ parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
+}
+
+static internal::Matcher<Stmt>
+assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
+ return declStmt(hasDescendant(varDecl(
+ allOf(hasType(referenceType()),
+ hasInitializer(anyOf(
+ initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
+ declRefExpr(to(varDecl(VarNodeMatcher)))))))));
+}
+
+static internal::Matcher<Stmt>
+getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
+ return unaryOperator(
+ hasOperatorName("&"),
+ hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
+}
+
+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(equalsNode(VD)), getAddrTo(equalsNode(VD)),
+ assignedToRef(equalsNode(VD))));
+}
+
+static internal::Matcher<Stmt> potentiallyModifyVarStmt(const VarDecl *VD) {
+ return anyOf(hasDescendant(stmt(
+ anyOf(changeByOperator(equalsNode(VD)), escapeStmt(VD)))),
+ stmt(anyOf(changeByOperator(equalsNode(VD)), escapeStmt(VD))));
+}
+
+static std::unique_ptr<ExprSequence> createSequence(Stmt *FunctionBody,
+ ASTContext &ASTCtx) {
+ CFG::BuildOptions Options;
+ Options.AddImplicitDtors = true;
+ Options.AddTemporaryDtors = true;
+ std::unique_ptr<CFG> TheCFG =
+ CFG::buildCFG(nullptr, FunctionBody, &ASTCtx, Options);
+ if (!TheCFG)
+ return std::unique_ptr<ExprSequence>{};
+
+ return llvm::make_unique<ExprSequence>(TheCFG.get(), &ASTCtx);
+}
+
+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);
+
+ // Skip the cases where there is no condition variables.
+ if (CondVarMatches.empty())
+ return;
+
+ std::unique_ptr<ExprSequence> Sequence = createSequence(FunctionBody, ASTCtx);
+ for (const auto &E : CondVarMatches) {
+ const VarDecl *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) {
+ CondVarNames += CVM.getNodeAs<VarDecl>("condvar")->getNameAsString() + ", ";
+ }
+ CondVarNames.resize(CondVarNames.size() - 2);
+
+ 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 misc
+} // namespace tidy
+} // namespace clang
Index: clang-tidy/misc/CMakeLists.txt
===================================================================
--- clang-tidy/misc/CMakeLists.txt
+++ clang-tidy/misc/CMakeLists.txt
@@ -2,6 +2,7 @@
add_clang_library(clangTidyMiscModule
ForwardingReferenceOverloadCheck.cpp
+ InfiniteLoopCheck.cpp
LambdaFunctionNameCheck.cpp
MisplacedConstCheck.cpp
UnconventionalAssignOperatorCheck.cpp
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
