szepet updated this revision to Diff 143949.
szepet marked 2 inline comments as done.
szepet added a comment.
Changes made based on comments.
The CFG recreating problem is handled the following (only for this check):
Always store the last visited function and its CFG* (in form of the Sequence*)
and check if we are visiting it again. If so, then the check reuses the
previous one, if not, then replaces them. As far as I know the AST traverse
done by the tidy fits this model (at least for this check, since it not uses
narrowing matchers to other functions).
Sure, it would be better to find a general solution to this problem, and make
the CFG reusable by every check which needs it, but I would left it for a
follow-up (and a change like this probably would worth an own patch/review
anyway).
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
@@ -28,6 +28,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
@@ -64,6 +64,12 @@
- New module ``zircon`` for checks related to Fuchsia's Zircon kernel.
+- New :doc:`bugprone-infinite-loop
+ <http://clang.llvm.org/extra/clang-tidy/checks/bugprone-infinite-loop.html>` check
+
+ Warns on loops where none of the condition variables are updated in the
+ body.
+
- New :doc:`bugprone-throw-keyword-missing
<clang-tidy/checks/bugprone-throw-keyword-missing>` 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,198 @@
+//===--- 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.
+bool InfiniteLoopCheck::updateSequence(Stmt *FunctionBody, ASTContext &ASTCtx) {
+ if (FunctionBody == PrevFunctionBody)
+ return false;
+ 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>();
+ return true;
+}
+
+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"
@@ -74,6 +75,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
