Index: clang-tools-extra/trunk/clang-tidy/bugprone/BugproneTidyModule.cpp =================================================================== --- clang-tools-extra/trunk/clang-tidy/bugprone/BugproneTidyModule.cpp +++ clang-tools-extra/trunk/clang-tidy/bugprone/BugproneTidyModule.cpp @@ -44,6 +44,7 @@ #include "SwappedArgumentsCheck.h" #include "TerminatingContinueCheck.h" #include "ThrowKeywordMissingCheck.h" +#include "TooSmallLoopVariableCheck.h" #include "UndefinedMemoryManipulationCheck.h" #include "UndelegatedConstructorCheck.h" #include "UnusedRaiiCheck.h" @@ -96,6 +97,8 @@ "bugprone-move-forwarding-reference"); CheckFactories.registerCheck( "bugprone-multiple-statement-macro"); + CheckFactories.registerCheck( + "bugprone-too-small-loop-variable"); CheckFactories.registerCheck( "bugprone-narrowing-conversions"); CheckFactories.registerCheck( Index: clang-tools-extra/trunk/clang-tidy/bugprone/CMakeLists.txt =================================================================== --- clang-tools-extra/trunk/clang-tidy/bugprone/CMakeLists.txt +++ clang-tools-extra/trunk/clang-tidy/bugprone/CMakeLists.txt @@ -35,6 +35,7 @@ SwappedArgumentsCheck.cpp TerminatingContinueCheck.cpp ThrowKeywordMissingCheck.cpp + TooSmallLoopVariableCheck.cpp UndefinedMemoryManipulationCheck.cpp UndelegatedConstructorCheck.cpp UnusedRaiiCheck.cpp Index: clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.h =================================================================== --- clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.h +++ clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.h @@ -0,0 +1,43 @@ +//===--- TooSmallLoopVariableCheck.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_TOOSMALLLOOPVARIABLECHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_TOOSMALLLOOPVARIABLECHECK_H + +#include "../ClangTidy.h" + +namespace clang { +namespace tidy { +namespace bugprone { + +/// This check gives a warning if a loop variable has a too small type which +/// might not be able to represent all values which are part of the whole range +/// in which the loop iterates. +/// If the loop variable's type is too small we might end up in an infinite +/// loop. Example: +/// \code +/// long size = 294967296l; +/// for (short i = 0; i < size; ++i) {} { ... } +/// \endcode +/// +/// For the user-facing documentation see: +/// http://clang.llvm.org/extra/clang-tidy/checks/bugprone-too-small-loop-variable.html +class TooSmallLoopVariableCheck : public ClangTidyCheck { +public: + TooSmallLoopVariableCheck(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_TOOSMALLLOOPVARIABLECHECK_H Index: clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp =================================================================== --- clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp +++ clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp @@ -0,0 +1,168 @@ +//===--- TooSmallLoopVariableCheck.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 "TooSmallLoopVariableCheck.h" +#include "clang/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace tidy { +namespace bugprone { + +static constexpr llvm::StringLiteral LoopName = + llvm::StringLiteral("forLoopName"); +static constexpr llvm::StringLiteral LoopVarName = + llvm::StringLiteral("loopVar"); +static constexpr llvm::StringLiteral LoopVarCastName = + llvm::StringLiteral("loopVarCast"); +static constexpr llvm::StringLiteral LoopUpperBoundName = + llvm::StringLiteral("loopUpperBound"); +static constexpr llvm::StringLiteral LoopIncrementName = + llvm::StringLiteral("loopIncrement"); + +/// \brief The matcher for loops with suspicious integer loop variable. +/// +/// In this general example, assuming 'j' and 'k' are of integral type: +/// \code +/// for (...; j < 3 + 2; ++k) { ... } +/// \endcode +/// The following string identifiers are bound to these parts of the AST: +/// LoopVarName: 'j' (as a VarDecl) +/// LoopVarCastName: 'j' (after implicit conversion) +/// LoopUpperBoundName: '3 + 2' (as an Expr) +/// LoopIncrementName: 'k' (as an Expr) +/// LoopName: The entire for loop (as a ForStmt) +/// +void TooSmallLoopVariableCheck::registerMatchers(MatchFinder *Finder) { + StatementMatcher LoopVarMatcher = + expr( + ignoringParenImpCasts(declRefExpr(to(varDecl(hasType(isInteger())))))) + .bind(LoopVarName); + + // We need to catch only those comparisons which contain any integer cast. + StatementMatcher LoopVarConversionMatcher = + implicitCastExpr(hasImplicitDestinationType(isInteger()), + has(ignoringParenImpCasts(LoopVarMatcher))) + .bind(LoopVarCastName); + + // We are interested in only those cases when the loop bound is a variable + // value (not const, enum, etc.). + StatementMatcher LoopBoundMatcher = + expr(ignoringParenImpCasts(allOf(hasType(isInteger()), + unless(integerLiteral()), + unless(hasType(isConstQualified())), + unless(hasType(enumType()))))) + .bind(LoopUpperBoundName); + + // We use the loop increment expression only to make sure we found the right + // loop variable. + StatementMatcher IncrementMatcher = + expr(ignoringParenImpCasts(hasType(isInteger()))).bind(LoopIncrementName); + + Finder->addMatcher( + forStmt( + hasCondition(anyOf( + binaryOperator(hasOperatorName("<"), + hasLHS(LoopVarConversionMatcher), + hasRHS(LoopBoundMatcher)), + binaryOperator(hasOperatorName("<="), + hasLHS(LoopVarConversionMatcher), + hasRHS(LoopBoundMatcher)), + binaryOperator(hasOperatorName(">"), hasLHS(LoopBoundMatcher), + hasRHS(LoopVarConversionMatcher)), + binaryOperator(hasOperatorName(">="), hasLHS(LoopBoundMatcher), + hasRHS(LoopVarConversionMatcher)))), + hasIncrement(IncrementMatcher)) + .bind(LoopName), + this); +} + +/// Returns the positive part of the integer width for an integer type. +static unsigned calcPositiveBits(const ASTContext &Context, + const QualType &IntExprType) { + assert(IntExprType->isIntegerType()); + + return IntExprType->isUnsignedIntegerType() + ? Context.getIntWidth(IntExprType) + : Context.getIntWidth(IntExprType) - 1; +} + +/// \brief Calculate the upper bound expression's positive bits, but ignore +/// constant like values to reduce false positives. +static unsigned calcUpperBoundPositiveBits(const ASTContext &Context, + const Expr *UpperBound, + const QualType &UpperBoundType) { + // Ignore casting caused by constant values inside a binary operator. + // We are interested in variable values' positive bits. + if (const auto *BinOperator = dyn_cast(UpperBound)) { + const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts(); + const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts(); + + QualType RHSEType = RHSE->getType(); + QualType LHSEType = LHSE->getType(); + + if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType()) + return 0; + + bool RHSEIsConstantValue = RHSEType->isEnumeralType() || + RHSEType.isConstQualified() || + isa(RHSE); + bool LHSEIsConstantValue = LHSEType->isEnumeralType() || + LHSEType.isConstQualified() || + isa(LHSE); + + // Avoid false positives produced by two constant values. + if (RHSEIsConstantValue && LHSEIsConstantValue) + return 0; + if (RHSEIsConstantValue) + return calcPositiveBits(Context, LHSEType); + if (LHSEIsConstantValue) + return calcPositiveBits(Context, RHSEType); + + return std::max(calcPositiveBits(Context, LHSEType), + calcPositiveBits(Context, RHSEType)); + } + + return calcPositiveBits(Context, UpperBoundType); +} + +void TooSmallLoopVariableCheck::check(const MatchFinder::MatchResult &Result) { + const auto *LoopVar = Result.Nodes.getNodeAs(LoopVarName); + const auto *UpperBound = + Result.Nodes.getNodeAs(LoopUpperBoundName)->IgnoreParenImpCasts(); + const auto *LoopIncrement = + Result.Nodes.getNodeAs(LoopIncrementName)->IgnoreParenImpCasts(); + + // We matched the loop variable incorrectly. + if (LoopVar->getType() != LoopIncrement->getType()) + return; + + QualType LoopVarType = LoopVar->getType(); + QualType UpperBoundType = UpperBound->getType(); + + ASTContext &Context = *Result.Context; + + unsigned LoopVarPosBits = calcPositiveBits(Context, LoopVarType); + unsigned UpperBoundPosBits = + calcUpperBoundPositiveBits(Context, UpperBound, UpperBoundType); + + if (UpperBoundPosBits == 0) + return; + + if (LoopVarPosBits < UpperBoundPosBits) + diag(LoopVar->getBeginLoc(), "loop variable has narrower type %0 than " + "iteration's upper bound %1") + << LoopVarType << UpperBoundType; +} + +} // namespace bugprone +} // namespace tidy +} // namespace clang Index: clang-tools-extra/trunk/docs/ReleaseNotes.rst =================================================================== --- clang-tools-extra/trunk/docs/ReleaseNotes.rst +++ clang-tools-extra/trunk/docs/ReleaseNotes.rst @@ -110,6 +110,13 @@ Flags uses of ``absl::StrCat()`` to append to a ``std::string``. Suggests ``absl::StrAppend()`` should be used instead. +- New :doc:`bugprone-too-small-loop-variable + ` check. + + Detects those ``for`` loops that have a loop variable with a "too small" type + which means this type can't represent all values which are part of the + iteration range. + - New :doc:`cppcoreguidelines-macro-usage ` check. Index: clang-tools-extra/trunk/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst =================================================================== --- clang-tools-extra/trunk/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst +++ clang-tools-extra/trunk/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst @@ -0,0 +1,29 @@ +.. title:: clang-tidy - bugprone-too-small-loop-variable + +bugprone-too-small-loop-variable +================================ + +Detects those ``for`` loops that have a loop variable with a "too small" type +which means this type can't represent all values which are part of the +iteration range. + +.. code-block:: c++ + + int main() { + long size = 294967296l; + for (short i = 0; i < size; ++i) {} + } + +This ``for`` loop is an infinite loop because the ``short`` type can't represent +all values in the ``[0..size]`` interval. + +In a real use case size means a container's size which depends on the user input. + +.. code-block:: c++ + + int doSomething(const std::vector& items) { + for (short i = 0; i < items.size(); ++i) {} + } + +This algorithm works for small amount of objects, but will lead to freeze for a +a larger user input. Index: clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst =================================================================== --- clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst +++ clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst @@ -59,6 +59,7 @@ bugprone-swapped-arguments bugprone-terminating-continue bugprone-throw-keyword-missing + bugprone-too-small-loop-variable bugprone-undefined-memory-manipulation bugprone-undelegated-constructor bugprone-unused-raii Index: clang-tools-extra/trunk/test/clang-tidy/bugprone-too-small-loop-variable.cpp =================================================================== --- clang-tools-extra/trunk/test/clang-tidy/bugprone-too-small-loop-variable.cpp +++ clang-tools-extra/trunk/test/clang-tidy/bugprone-too-small-loop-variable.cpp @@ -0,0 +1,251 @@ +// RUN: %check_clang_tidy %s bugprone-too-small-loop-variable %t + +long size() { return 294967296l; } + +//////////////////////////////////////////////////////////////////////////////// +/// Test cases correctly caught by bugprone-too-small-loop-variable. + +void voidBadForLoop() { + for (int i = 0; i < size(); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidBadForLoop2() { + for (int i = 0; i < size() + 10; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidBadForLoop3() { + for (int i = 0; i <= size() - 1; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidBadForLoop4() { + for (int i = 0; size() > i; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:28: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidBadForLoop5() { + for (int i = 0; size() - 1 >= i; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:33: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidBadForLoop6() { + int i = 0; + for (; i < size(); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:10: warning: loop variable has narrower type 'int' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidForLoopUnsignedBound() { + unsigned size = 3147483647; + for (int i = 0; i < size; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has narrower type 'int' than iteration's upper bound 'unsigned int' [bugprone-too-small-loop-variable] + } +} + +// The iteration's upper bound has a template dependent value. +template +void doSomething() { + for (short i = 0; i < size; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +// The iteration's upper bound has a template dependent type. +template +void doSomething() { + for (T i = 0; i < size(); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: loop variable has narrower type 'short' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +void voidForLoopInstantiation() { + // This line does not trigger the warning. + doSomething(); + // This one triggers the warning. + doSomething(); +} + +// A suspicious function used in a macro. +#define SUSPICIOUS_SIZE (size()) +void voidBadForLoopWithMacroBound() { + for (short i = 0; i < SUSPICIOUS_SIZE; ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'long' [bugprone-too-small-loop-variable] + } +} + +//////////////////////////////////////////////////////////////////////////////// +/// Correct loops: we should not warn here. + +// A simple use case when both expressions have the same type. +void voidGoodForLoop() { + for (long i = 0; i < size(); ++i) { // no warning + } +} + +// Other use case where both expressions have the same type, +// but short expressions are converted to int by the compare operator. +void voidGoodForLoop2() { + short loopCond = 10; + for (short i = 0; i < loopCond; ++i) { // no warning + } +} + +// Because of the integer literal, the iteration's upper bound is int, but we suppress the warning here. +void voidForLoopShortPlusLiteral() { + short size = 30000; + for (short i = 0; i <= (size - 1); ++i) { // no warning + } +} + +// Addition of two short variables results in an int value, but we suppress this to avoid false positives. +void voidForLoopShortPlusShort() { + short size = 256; + short increment = 14; + for (short i = 0; i < size + increment; ++i) { // no warning + } +} + +// In this test case we have different integer types, but here the loop variable has the bigger type. +// The iteration's bound is cast implicitly, not the loop variable. +void voidForLoopBoundImplicitCast() { + short start = 256; + short end = 14; + for (int i = start; i >= end; --i) { // no warning + } +} + +// Range based loop and other iterator based loops are ignored by this check. +void voidRangeBasedForLoop() { + int array[] = {1, 2, 3, 4, 5}; + for (const int &i : array) { // no warning + } +} + +//////////////////////////////////////////////////////////////////////////////// +/// Future possibilites to improve the check. + +// False positive: because of the int literal, iteration's upper bound has int type. +void voidForLoopFalsePositive() { + short size = 30000; + bool cond = false; + for (short i = 0; i < (cond ? 0 : size); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'int' [bugprone-too-small-loop-variable] + } +} + +void voidForLoopFalsePositive2() { + short size = 30000; + bool cond = false; + for (short i = 0; i < (!cond ? size : 0); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'int' [bugprone-too-small-loop-variable] + } +} + +// False positive: The loop bound expression contains nested binary operators. +void voidForLoopFalsePositive3() { + short number = 30000; + for (short i = 0; i < ((number & 0x7f) + 1); ++i) { + // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'int' [bugprone-too-small-loop-variable] + } +} + +// TODO: handle while loop. +void voidBadWhileLoop() { + short i = 0; + while (i < size()) { // missing warning + ++i; + } +} + +// TODO: handle do-while loop. +void voidBadDoWhileLoop() { + short i = 0; + do { + ++i; + } while (i < size()); // missing warning +} + +// TODO: handle complex loop conditions. +void voidComplexForCond() { + bool additionalCond = true; + for (int i = 0; i < size() && additionalCond; ++i) { // missing warning + } +} + +//////////////////////////////////////////////////////////////////////////////// +/// Suspicious test cases ingored by this check. + +// Test case with a reverse iteration. +// This is caught by -Wimplicit-int-conversion. +void voidReverseForLoop() { + for (short i = size() - 1; i >= 0; --i) { // no warning + } +} + +// Macro defined literals are used inside the loop condition. +#define SIZE 125 +#define SIZE2 (SIZE + 1) +void voidForLoopWithMacroBound() { + for (short i = 0; i < SIZE2; ++i) { // no warning + } +} + +// A suspicious loop is not caught if the iteration's upper bound is a literal. +void voidForLoopWithLiteralBound() { + for (short i = 0; i < 125; ++i) { // no warning + } +} + +// The used literal leads to an infinite loop. +// This is caught by -Wtautological-constant-out-of-range-compare. +void voidForLoopWithBigLiteralBound() { + for (short i = 0; i < 294967296l; ++i) { // no warning + } +} + +enum eSizeType { + START, + Y, + END +}; + +// A suspicious loop is not caught if the iteration's upper bound is an enum value. +void voidForLoopWithEnumBound() { + for (short i = eSizeType::START; i < eSizeType::END; ++i) { // no warning + } +} + +enum eSizeType2 : long { + START2 = 294967296l, + Y2, + END2 +}; + +// The used enum value leads to an infinite loop. +// This is caught by -Wtautological-constant-out-of-range-compare. +void voidForLoopWithBigEnumBound() { + for (short i = eSizeType2::START2; i < eSizeType2::END2; ++i) { // no warning + } +} + +// A suspicious loop is not caught if the iteration's upper bound is a constant variable. +void voidForLoopWithConstBound() { + const long size = 252l; + for (short i = 0; i < size; ++i) { // no warning + } +} + +// The used constant variable leads to an infinite loop. +// This is caught by -Wtautological-constant-out-of-range-compare. +void voidForLoopWithBigConstBound() { + const long size = 294967296l; + for (short i = 0; i < size; ++i) { // no warning + } +}