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 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 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 +changeByOperator(internal::Matcher 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 +callByRef(internal::Matcher VarNodeMatcher) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(VarNodeMatcher))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher +assignedToRef(internal::Matcher VarNodeMatcher) { + return declStmt(hasDescendant(varDecl( + allOf(hasType(referenceType()), + hasInitializer(anyOf( + initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), + declRefExpr(to(varDecl(VarNodeMatcher))))))))); +} + +static internal::Matcher +getAddrTo(internal::Matcher VarNodeMatcher) { + return unaryOperator( + hasOperatorName("&"), + hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); +} + +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(equalsNode(VD)), getAddrTo(equalsNode(VD)), + assignedToRef(equalsNode(VD)))); +} + +static internal::Matcher 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 createSequence(Stmt *FunctionBody, + ASTContext &ASTCtx) { + CFG::BuildOptions Options; + Options.AddImplicitDtors = true; + Options.AddTemporaryDtors = true; + std::unique_ptr TheCFG = + CFG::buildCFG(nullptr, FunctionBody, &ASTCtx, Options); + if (!TheCFG) + return std::unique_ptr{}; + + return llvm::make_unique(TheCFG.get(), &ASTCtx); +} + +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); + + // Skip the cases where there is no condition variables. + if (CondVarMatches.empty()) + return; + + std::unique_ptr Sequence = createSequence(FunctionBody, ASTCtx); + for (const auto &E : CondVarMatches) { + const VarDecl *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) { + CondVarNames += CVM.getNodeAs("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/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( "misc-forwarding-reference-overload"); + CheckFactories.registerCheck( + "misc-infinite-loop"); CheckFactories.registerCheck( "misc-lambda-function-name"); CheckFactories.registerCheck("misc-misplaced-const"); 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 + `_ check + + Finds loops where none of the condition variables are updated in the body. + - New `objc-avoid-nserror-init `_ check 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/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: 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--; + } +}