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( "bugprone-incorrect-roundings"); + CheckFactories.registerCheck( + "bugprone-infinite-loop"); CheckFactories.registerCheck( "bugprone-integer-division"); CheckFactories.registerCheck( 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/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,225 @@ +//===--- 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/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace tidy { +namespace bugprone { + +static internal::Matcher loopEndingStmt() { + return stmt(anyOf(breakStmt(), returnStmt(), gotoStmt(), cxxThrowExpr())); +} + +static bool isAccessForVar(const Stmt *St, const VarDecl *Var) { + if (const auto *DRE = dyn_cast(St)) + return DRE->getDecl() == Var; + + return false; +} + +static bool isPtrOrReferenceForVar(const Stmt *St, const VarDecl *Var) { + if (const auto *DRE = dyn_cast(St)) { + if (const auto *LeftVar = dyn_cast(DRE->getDecl())) { + if (LeftVar->hasInit() && LeftVar->getType()->isReferenceType()) { + return isAccessForVar(LeftVar->getInit(), Var); + } + } + } else if (const auto *UnOp = dyn_cast(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 isPassedByRef(const FunctionDecl *Func, unsigned Idx) { + if (!Func) + return false; + + if (Idx >= Func->getNumParams()) + return false; + + QualType ParamType = Func->getParamDecl(Idx)->getType(); + if (ParamType->isReferenceType() && !ParamType.isConstQualified()) + return true; + + return false; +} + +static bool isChangedInChild(const Stmt *St, const VarDecl *Var) { + if (const auto *UnOp = dyn_cast(St)) { + if (UnOp->isIncrementDecrementOp()) { + if (isAccessForVar(UnOp->getSubExpr(), Var)) + return true; + } + } + + if (const auto *BinOp = dyn_cast(St)) { + if (BinOp->isAssignmentOp()) { + if (isAccessForVar(BinOp->getLHS(), Var)) + return true; + } + } + + if (isPtrOrReferenceForVar(St, Var)) + return true; + + if (const auto *Call = dyn_cast(St)) { + for (unsigned i = 0; i < Call->getNumArgs(); ++i) { + const Expr *Arg = Call->getArg(i); + if (isAccessForVar(Arg->IgnoreParenImpCasts(), Var) && + isPassedByRef(Call->getDirectCallee(), i)) + return true; + } + } + + for (const Stmt *Child : St->children()) { + if (!Child) + continue; + + if (isChangedInChild(Child, Var)) + return true; + } + return false; +} + +static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var) { + if (const auto *ForLoop = dyn_cast(LoopStmt)) + return (ForLoop->getInc() && isChangedInChild(ForLoop->getInc(), Var)) || + (ForLoop->getBody() && isChangedInChild(ForLoop->getBody(), Var)) || + (ForLoop->getCond() && isChangedInChild(ForLoop->getCond(), Var)); + + return isChangedInChild(LoopStmt, Var); +} + +static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func, + const Stmt *LoopStmt, const Stmt *Cond) { + if (const auto *DRE = dyn_cast(Cond)) { + if (const auto *Var = dyn_cast(DRE->getDecl())) { + if (!Var->isLocalVarDeclOrParm()) + return true; + + if (!Var->getType().getTypePtr()->isIntegerType()) + return true; + + return hasPtrOrReferenceBefore(Func, LoopStmt, Var) || + isChanged(LoopStmt, Var); + // FIXME: Track references. + } + } else if (isa(Cond) || isa(Cond)) { + // FIXME: Handle MemberExpr. + return true; + } + + for (const Stmt *Child : Cond->children()) { + if (!Child) + continue; + + if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child)) + return true; + } + return false; +} + +static std::string getCondVarNames(const Stmt *Cond) { + if (const auto *DRE = dyn_cast(Cond)) { + if (const auto *Var = dyn_cast(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(Cond)) { + if (const auto *Var = dyn_cast(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("condition"); + const auto *LoopStmt = Result.Nodes.getNodeAs("loop-stmt"); + const auto *Func = Result.Nodes.getNodeAs("func"); + + if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond)) + 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: docs/ReleaseNotes.rst =================================================================== --- docs/ReleaseNotes.rst +++ docs/ReleaseNotes.rst @@ -111,6 +111,11 @@ This checks ensures that ``pipe2()`` is called with the O_CLOEXEC flag. +- New :doc:`bugprone-infinite-loop + ` check. + + FIXME: add release notes. + - New :doc:`bugprone-unhandled-self-assignment ` check. @@ -230,6 +235,10 @@ If set to true, the check will provide fix-its with literal initializers (``int i = 0;``) instead of curly braces (``int i{};``). +- New :doc:`bugprone-infinite-loop ` + check to detect obvious infinite loops (loops where the condition variable is + not changed at all). + Improvements to include-fixer ----------------------------- 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/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: 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. +}