szepet created this revision.
Herald added subscribers: rnkovacs, baloghadamsoftware, whisperity, mgorny.
The checker aims to find loops where none of the condition variables are
updated in the body.
In this version it only works on integer types but the final aim is to make it
work for objects as well. (via checking non-const method calls, etc)
Note: this kind of check is supported by clang warning as well
(-Wfor-loop-analysis), however, it only works on for-loops and not investigate
escape statements (modification via alias generates false positives e.g.
`escape_before1()` test case).
Any suggestions on the checker are welcome!
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,104 @@
+// 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, 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++;
+ }
+}
Index: docs/clang-tidy/checks/misc-infinite-loop.rst
===================================================================
--- /dev/null
+++ docs/clang-tidy/checks/misc-infinite-loop.rst
@@ -0,0 +1,31 @@
+.. title:: clang-tidy - misc-infinite-loop
+
+misc-infinite-loop
+==================
+
+The checker 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.
+
+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;
+ }
+ }
+
\ No newline at end of file
Index: docs/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -119,6 +119,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
@@ -57,6 +57,12 @@
Improvements to clang-tidy
--------------------------
+- New `misc-infinite-loop
+ <http://clang.llvm.org/extra/clang-tidy/checks/misc-infinite-loop.html>`_ check
+
+ The checker aims to find loops where none of the
+ condition variables are updated in the body.
+
- The 'misc-move-constructor-init' check was renamed to `performance-move-constructor-init
<http://clang.llvm.org/extra/clang-tidy/checks/performance-move-constructor-init.html>`_
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"
@@ -52,6 +53,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 checker 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,189 @@
+//===--- 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(hasBody(hasDescendant(loopEndingStmt()))));
+ };
+
+ 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))));
+}
+
+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>(
+ *(new 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;
+
+ auto CondVarMatches =
+ match(findAll(declRefExpr(to(varDecl().bind("condvar")))), *Cond, ASTCtx);
+
+ std::unique_ptr<ExprSequence> Sequence = createSequence(FunctionBody, ASTCtx);
+
+ for (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 (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 (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 (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
