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( "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 @@ -12,6 +12,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,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 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 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 +changeByOperator(internal::Matcher ExprNodeMatcher) { + return anyOf( + unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts(ExprNodeMatcher))), + binaryOperator(isAssignmentOperator(), hasLHS(ExprNodeMatcher))); +} + +static internal::Matcher +callByRef(internal::Matcher ExprNodeMatcher) { + return callExpr(forEachArgumentWithParam( + ExprNodeMatcher, + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher +assignedToRef(internal::Matcher ExprNodeMatcher) { + return declStmt(hasDescendant( + varDecl(allOf(hasType(referenceType()), + hasInitializer(anyOf(initListExpr(has(ExprNodeMatcher)), + ExprNodeMatcher)))))); +} + +static internal::Matcher +getAddrTo(internal::Matcher ExprNodeMatcher) { + return unaryOperator(hasOperatorName("&"), hasUnaryOperand(ExprNodeMatcher)); +} + +static internal::Matcher 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 +hasDescendantOrIsItselfStmt(internal::Matcher VarNodeMatcher) { + return anyOf(VarNodeMatcher, hasDescendant(VarNodeMatcher)); +} + +static internal::Matcher 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 TheCFG = + CFG::buildCFG(nullptr, FunctionBody, &ASTCtx, Options)) + Sequence = llvm::make_unique(TheCFG.get(), &ASTCtx); + else + Sequence = std::unique_ptr(); + return true; +} + +void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) { + const auto *ContainingLambda = + Result.Nodes.getNodeAs("containing-lambda"); + const auto *ContainingFunc = + Result.Nodes.getNodeAs("containing-func"); + const auto *Cond = Result.Nodes.getNodeAs("condition"); + const auto *LoopStmt = Result.Nodes.getNodeAs("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("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 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(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("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("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: 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 + ` check + + Warns on loops where none of the condition variables are updated in the + body. + - New :doc:`bugprone-throw-keyword-missing ` check 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/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: 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; +};