Index: clang-tidy/bugprone/BugproneTidyModule.cpp =================================================================== --- clang-tidy/bugprone/BugproneTidyModule.cpp +++ clang-tidy/bugprone/BugproneTidyModule.cpp @@ -23,6 +23,7 @@ #include "ForwardingReferenceOverloadCheck.h" #include "InaccurateEraseCheck.h" #include "IncorrectRoundingsCheck.h" +#include "InfiniteLoopCheck.h" #include "IntegerDivisionCheck.h" #include "LambdaFunctionNameCheck.h" #include "MacroParenthesesCheck.h" @@ -88,6 +89,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 @@ -15,6 +15,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 { + +/// Finds 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,188 @@ +//===--- 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" +#include "clang/Analysis/Analyses/ExprMutationAnalyzer.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace tidy { +namespace bugprone { + +static internal::Matcher +loopEndingStmt(internal::Matcher Internal) { + return stmt(anyOf(breakStmt(Internal), returnStmt(Internal), + gotoStmt(Internal), cxxThrowExpr(Internal), + callExpr(Internal, callee(functionDecl(isNoReturn()))))); +} + +/// Return whether `S` is a reference to the declaration of `Var`. +static bool isAccessForVar(const Stmt *S, const VarDecl *Var) { + if (const auto *DRE = dyn_cast(S)) + return DRE->getDecl() == Var; + + return false; +} + +/// Return whether `Var` has a pointer or reference in `S`. +static bool isPtrOrReferenceForVar(const Stmt *S, const VarDecl *Var) { + if (const auto *DS = dyn_cast(S)) { + for (const Decl *D : DS->getDeclGroup()) { + if (const auto *LeftVar = dyn_cast(D)) { + if (LeftVar->hasInit() && LeftVar->getType()->isReferenceType()) { + return isAccessForVar(LeftVar->getInit(), Var); + } + } + } + } else if (const auto *UnOp = dyn_cast(S)) { + if (UnOp->getOpcode() == UO_AddrOf) + return isAccessForVar(UnOp->getSubExpr(), Var); + } + + return false; +} + +/// Return whether `Var` has a pointer or reference in `S`. +static bool hasPtrOrReferenceInStmt(const Stmt *S, const VarDecl *Var) { + if (isPtrOrReferenceForVar(S, Var)) + return true; + + for (const Stmt *Child : S->children()) { + if (!Child) + continue; + + if (hasPtrOrReferenceInStmt(Child, Var)) + return true; + } + + return false; +} + +/// Return whether `Var` has a pointer or reference in `Func`. +static bool hasPtrOrReferenceInFunc(const FunctionDecl *Func, + const VarDecl *Var) { + return hasPtrOrReferenceInStmt(Func->getBody(), Var); +} + +/// Return whether `Var` was changed in `LoopStmt`. +static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var, + ASTContext *Context) { + if (const auto *ForLoop = dyn_cast(LoopStmt)) + return (ForLoop->getInc() && + ExprMutationAnalyzer(*ForLoop->getInc(), *Context) + .isMutated(Var)) || + (ForLoop->getBody() && + ExprMutationAnalyzer(*ForLoop->getBody(), *Context) + .isMutated(Var)) || + (ForLoop->getCond() && + ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var)); + + return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var); +} + +/// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`. +static bool isVarThatIsPossiblyChanged(const FunctionDecl *Func, + const Stmt *LoopStmt, const Stmt *Cond, + ASTContext *Context) { + if (const auto *DRE = dyn_cast(Cond)) { + if (const auto *Var = dyn_cast(DRE->getDecl())) { + if (!Var->isLocalVarDeclOrParm()) + return true; + + if (Var->getType().isVolatileQualified()) + return true; + + if (!Var->getType().getTypePtr()->isIntegerType()) + return true; + + return hasPtrOrReferenceInFunc(Func, Var) || + isChanged(LoopStmt, Var, Context); + // FIXME: Track references. + } + } else if (isa(Cond) || isa(Cond)) { + // FIXME: Handle MemberExpr. + return true; + } + + return false; +} + +/// Return whether at least one variable of `Cond` changed in `LoopStmt`. +static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func, + const Stmt *LoopStmt, const Stmt *Cond, + ASTContext *Context) { + if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context)) + return true; + + for (const Stmt *Child : Cond->children()) { + if (!Child) + continue; + + if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context)) + return true; + } + return false; +} + +/// Return the variable names in `Cond`. +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; +} + +void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) { + const auto LoopCondition = allOf( + hasCondition( + expr(forFunction(functionDecl().bind("func"))).bind("condition")), + unless(hasBody(hasDescendant( + loopEndingStmt(forFunction(equalsBoundNode("func"))))))); + + Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition), + forStmt(LoopCondition))) + .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, Result.Context)) + return; + + std::string CondVarNames = getCondVarNames(Cond); + if (CondVarNames.empty()) + return; + + diag(LoopStmt->getBeginLoc(), + "this loop is infinite; none of its 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 @@ -70,6 +70,86 @@ - New :doc:`bugprone-dynamic-static-initializers ` check. +- New OpenMP module. + + For checks specific to `OpenMP `_ API. + +- New :doc:`abseil-duration-addition + ` check. + + Checks for cases where addition should be performed in the ``absl::Time`` + domain. + +- New :doc:`abseil-duration-conversion-cast + ` check. + + Checks for casts of ``absl::Duration`` conversion functions, and recommends + the right conversion function instead. + +- New :doc:`abseil-duration-unnecessary-conversion + ` check. + + Finds and fixes cases where ``absl::Duration`` values are being converted to + numeric types and back again. + +- New :doc:`abseil-time-comparison + ` check. + + Prefer comparisons in the ``absl::Time`` domain instead of the integer + domain. + +- New :doc:`abseil-time-subtraction + ` check. + + Finds and fixes ``absl::Time`` subtraction expressions to do subtraction + in the Time domain instead of the numeric domain. + +- New :doc:`android-cloexec-pipe + ` check. + + This check detects usage of ``pipe()``. + +- New :doc:`android-cloexec-pipe2 + ` check. + + This checks ensures that ``pipe2()`` is called with the O_CLOEXEC flag. + +- New :doc:`bugprone-infinite-loop + ` check. + + Finds obvious infinite loops (loops where the condition variable is not + changed at all). + +- New :doc:`bugprone-unhandled-self-assignment + ` check. + + Finds user-defined copy assignment operators which do not protect the code + against self-assignment either by checking self-assignment explicitly or + using the copy-and-swap or the copy-and-move method. + +- New :doc:`bugprone-branch-clone + ` check. + + Checks for repeated branches in ``if/else if/else`` chains, consecutive + repeated branches in ``switch`` statements and indentical true and false + branches in conditional operators. + +- New :doc:`bugprone-posix-return + ` check. + + Checks if any calls to POSIX functions (except ``posix_openpt``) expect negative + return values. + +- New :doc:`fuchsia-default-arguments-calls + ` check. + + Warns if a function or method is called with default arguments. + This was previously done by `fuchsia-default-arguments check`, which has been + removed. + +- New :doc:`fuchsia-default-arguments-calls + ` check. + Finds instances where variables with static storage are initialized dynamically in header files. Index: docs/clang-tidy/checks/bugprone-infinite-loop.rst =================================================================== --- /dev/null +++ docs/clang-tidy/checks/bugprone-infinite-loop.rst @@ -0,0 +1,32 @@ +.. title:: clang-tidy - bugprone-infinite-loop + +bugprone-infinite-loop +====================== + +Finds obvious infinite loops (loops where the condition variable is not changed +at all). + +Finding infinite loops is well-known to be impossible (halting problem). +However, it is possible to detect some obvious infinite loops, for example, if +the loop condition is not changed. This check detects such loops. A loop is +considered infinite if it does not have any loop exit statement (``break``, +``continue``, ``goto``, ``return``, ``throw`` or a call to a function called as +``[[noreturn]]``) and all of the following conditions hold for every variable in +the condition: + +- It is a local variable. +- It has no reference or pointer aliases. +- It is not a structure or class member. + +Furthermore, the condition must not contain a function call to consider the loop +infinite since functions may return different values for different calls. + +For example, the following loop is considered infinite `i` is not changed in +the body: + +.. 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 @@ -51,6 +51,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,321 @@ +// 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: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + j++; + } + + do { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + j++; + } while (i < 10); + + for (i = 0; i < 10; ++j) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its 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]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop] + j++; + } + + do { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop] + j++; + } while (i < Limit); + + for (i = 0; i < Limit; ++j) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its 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 its condition part. + } +} + +int unknown_function(); + +void function_call() { + int i = 0; + while (i < unknown_function()) { + // Not an error, since the function may return different values. + } + + do { + // Not an error, since the function may return different values. + } while (i < unknown_function()); + + for (i = 0; i < unknown_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) { + // False negative, but difficult to detect without CFG-based analysis + } + int *p = &i; +} + +void escape_after2() { + int i = 0; + int j = 0; + int Limit = 10; + + while (i < Limit) { + // False negative, but difficult to detect without CFG-based analysis + } + 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 struct or + // class can be found in its 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) + ; +} + +void volatile_in_condition() { + volatile int cond = 0; + while (!cond) { + } +} + +namespace std { +template class atomic { + T val; +public: + atomic(T v): val(v) {}; + operator T() { return val; }; +}; +} + +void atomic_in_condition() { + std::atomic cond = 0; + while (!cond) { + } +} + +void loop_exit1() { + int i = 0; + while (i) { + if (unknown_function()) + break; + } +} + +void loop_exit2() { + int i = 0; + while (i) { + if (unknown_function()) + return; + } +} + +void loop_exit3() { + int i = 0; + while (i) { + if (unknown_function()) + goto end; + } + end: + ; +} + +void loop_exit4() { + int i = 0; + while (i) { + if (unknown_function()) + throw 1; + } +} + +[[noreturn]] void exit(int); + +void loop_exit5() { + int i = 0; + while (i) { + if (unknown_function()) + exit(1); + } +} + +void loop_exit_in_lambda() { + int i = 0; + while (i) { + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop] + auto l = []() { return 0; }; + } +} + +void lambda_capture() { + int i = 0; + int Limit = 100; + int *p = &i; + while (i < Limit) { + // Not an error, since i is captured by reference in a lambda. + auto l = [&i]() { ++i; }; + } + + do { + int *p = &i; + (*p)++; + } while (i < Limit); +}