Index: clang-tidy/bugprone/BugproneTidyModule.cpp =================================================================== --- clang-tidy/bugprone/BugproneTidyModule.cpp +++ 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-tidy/bugprone/CMakeLists.txt =================================================================== --- clang-tidy/bugprone/CMakeLists.txt +++ 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-tidy/bugprone/TooSmallLoopVariableCheck.h =================================================================== --- /dev/null +++ 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-tidy/bugprone/TooSmallLoopVariableCheck.cpp =================================================================== --- /dev/null +++ clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp @@ -0,0 +1,190 @@ +//===--- 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 const char LoopName[] = "forLoopName"; +static const char loopVarName[] = "loopVar"; +static const char loopVarCastName[] = "loopVarCast"; +static const char loopCondName[] = "loopCond"; +static const char loopIncrementName[] = "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) +/// loopVarCast: 'j' (after implicit conversion) +/// loopCondName: '3 + 2' (as an Expr) +/// loopIncrementName: 'k' (as an Expr) +/// LoopName: The entire for loop (as a ForStmt) +/// +void TooSmallLoopVariableCheck::registerMatchers(MatchFinder *Finder) { + + const StatementMatcher LoopVarMatcher = + expr(ignoringParenImpCasts( + declRefExpr(to(varDecl(hasType(isInteger())))))).bind(loopVarName); + + // We need to catch only those comparisons when there is any integer cast + const StatementMatcher LoopVarConversionMatcher = + implicitCastExpr( + hasImplicitDestinationType(isInteger()), + has(ignoringParenImpCasts(LoopVarMatcher))).bind(loopVarCastName); + + // We are interested in only those cases when the condition is a variable value (not const, enum, etc.) + const StatementMatcher LoopCondMatcher = + expr(ignoringParenImpCasts(allOf( + hasType(isInteger()), + unless(integerLiteral()), + unless(hasType(isConstQualified())), + unless(hasType(enumType()))))).bind(loopCondName); + + // We use the loop increment expression only to make sure we found the right loop variable + const StatementMatcher IncrementMatcher = + expr(ignoringParenImpCasts( + hasType(isInteger()))).bind(loopIncrementName); + + Finder->addMatcher( + forStmt( + hasCondition(anyOf( + binaryOperator(hasOperatorName("<"), + hasLHS(LoopVarConversionMatcher), + hasRHS(LoopCondMatcher)), + binaryOperator(hasOperatorName("<="), + hasLHS(LoopVarConversionMatcher), + hasRHS(LoopCondMatcher)), + binaryOperator(hasOperatorName(">"), + hasLHS(LoopCondMatcher), + hasRHS(LoopVarConversionMatcher)), + binaryOperator(hasOperatorName(">="), + hasLHS(LoopCondMatcher), + hasRHS(LoopVarConversionMatcher)))), + hasIncrement(IncrementMatcher)) + .bind(LoopName), + this); +} + + +/// \brief Returns the positive part of the integer width for an integer type +unsigned calcPositiveBits(const ASTContext &Context, const QualType &IntExprType) { + + assert(IntExprType->isIntegerType()); + + return IntExprType->isUnsignedIntegerType() + ? Context.getIntWidth(IntExprType) + : Context.getIntWidth(IntExprType) - 1; +} + + +/// \brief Calculate the condition expression's positive bits, but ignore constant like values to reduce false positives +unsigned calcCondExprPositiveBits(const ASTContext &Context, const Expr *CondExpr, const QualType &CondExprType) { + + unsigned CondExprPosBits = 0; + + // Inside a binary operator ignore casting caused by constant values + // (constants, macros defiened values, enums, literals) + // We are interested in variable values' positive bits + if(const auto *BinOperator = dyn_cast(CondExpr)) { + const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts(); + const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts(); + + + if (RHSE->isTypeDependent() || RHSE->isValueDependent() || + LHSE->isTypeDependent() || LHSE->isValueDependent()) + return 0; + + + const QualType RHSEType = RHSE->getType(); + const QualType LHSEType = LHSE->getType(); + + if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType()) + return 0; + + + if(RHSEType->isEnumeralType() || RHSEType.isConstQualified() || + RHSE->getBeginLoc().isMacroID() || isa(RHSE)) { + + CondExprPosBits = calcPositiveBits(Context, LHSEType); + + } + else if (LHSEType->isEnumeralType() || LHSEType.isConstQualified() || + LHSE->getBeginLoc().isMacroID() || isa(LHSE)) { + + CondExprPosBits = calcPositiveBits(Context, RHSEType); + + } else { + + CondExprPosBits = std::max(calcPositiveBits(Context, LHSEType), + calcPositiveBits(Context, RHSEType)); + } + } else { + + CondExprPosBits = calcPositiveBits(Context, CondExprType); + + } + + return CondExprPosBits; +} + + +void TooSmallLoopVariableCheck::check(const MatchFinder::MatchResult &Result) { + + const auto *LoopVar = Result.Nodes.getNodeAs(loopVarName); + const auto *CondExpr = Result.Nodes.getNodeAs(loopCondName)->IgnoreParenImpCasts(); + const auto *LoopIncrement = Result.Nodes.getNodeAs(loopIncrementName)->IgnoreParenImpCasts(); + + + if (CondExpr->isTypeDependent() || CondExpr->isValueDependent() || + LoopVar->isTypeDependent() || LoopVar->isValueDependent() || + LoopIncrement->isTypeDependent() || LoopIncrement->isValueDependent()) + return; + + if(LoopVar->getType() != LoopIncrement->getType()) + return; // We matched the loop variable incorrectly + + const QualType LoopVarType = LoopVar->getType(); + const QualType CondExprType = CondExpr->getType(); + + if (CondExpr->getBeginLoc().isMacroID()) + return; // In most of the cases a macro defines a const value, let just ignore that to avoid false positives + + ASTContext &Context = *Result.Context; + + if (!LoopVarType->isIntegerType() || !CondExprType->isIntegerType()) + return; + + const unsigned LoopVarPosBits = calcPositiveBits(Context, LoopVarType); + const unsigned CondExprPosBits = calcCondExprPositiveBits(Context, CondExpr, CondExprType); + + if(CondExprPosBits == 0) + return; + + if (LoopVarPosBits < CondExprPosBits) + { + diag(LoopVar->getBeginLoc(), "loop variable has a narrower type (%0) than " + "the type (%1) of termination condition") + << LoopVarType << CondExprType; + } +} + +} // namespace bugprone +} // namespace tidy +} // namespace clang Index: docs/ReleaseNotes.rst =================================================================== --- docs/ReleaseNotes.rst +++ docs/ReleaseNotes.rst @@ -67,6 +67,13 @@ Improvements to clang-tidy -------------------------- +- New :doc:`bugprone-too-small-loop-variable + ` 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. + - New :doc:`abseil-duration-division ` check. Index: docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst =================================================================== --- /dev/null +++ docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst @@ -0,0 +1,28 @@ +.. title:: clang-tidy - bugprone-too-small-loop-variable + +bugprone-too-small-loop-variable +================================ + +This check searches for those for loops which has 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 doSometinhg(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: docs/clang-tidy/checks/list.rst =================================================================== --- docs/clang-tidy/checks/list.rst +++ 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: test/clang-tidy/bugprone-too-small-loop-variable.cpp =================================================================== --- /dev/null +++ test/clang-tidy/bugprone-too-small-loop-variable.cpp @@ -0,0 +1,160 @@ +// RUN: %check_clang_tidy %s bugprone-too-small-loop-variable %t + +long size() { return 294967296l; } + + +void voidBadForLoop() { + for (int i = 0; i < size(); ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidBadForLoop2() { + for (int i = 0; i < size() + 10; ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidBadForLoop3() { + for (int i = 0; i <= size() - 1; ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidBadForLoop4() { + for (int i = 0; size() > i; ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:28: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidBadForLoop5() { + for (int i = 0; size() - 1 >= i; ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:33: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidBadForLoop6() { + int i = 0; + for (; i < size(); ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:10: warning: loop variable has a narrower type ('int') than the type ('long') of termination condition [bugprone-too-small-loop-variable] +} + + +void voidForLoopUnsignedCond() { + unsigned size = 3147483647; + for (int i = 0; i < size; ++i) {} + // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: loop variable has a narrower type ('int') than the type ('unsigned int') of termination condition [bugprone-too-small-loop-variable] +} + + +// False positive: because of the integer literal, loop condition 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 a narrower type ('short') than the type ('int') of termination condition [bugprone-too-small-loop-variable] +} + + +// Simple use case when both expressions have the same type +void voidGoodForLoop() { + for (long i = 0; i < size(); ++i) {} // no warning +} + + +// Second simple use case when both expressions have the same type +void voidGoodForLoop2() { + short loopCond = 10; + for (short i = 0; i < loopCond; ++i) {} // no warning +} + + +// Because of the integer literal, the loop condition is int, but we suppress the warning here +void voidForLoopShortPlusLiteral() { + short size = 30000; + for (short i = 0; i <= (size - 1); ++i) {} // no warning +} + + +// Additions of two short variable is converted to int, 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 +} + +// Different integer types, but in this case the loop variable is the bigger type +void voidForLoopReverseCond() { + short start = 256; + short end = 14; + for (int i = start; i >= end; --i) {} // no warning +} + + +// TODO: handle while loop +void voidBadWhileLoop() { + short i = 0; + while (i < size()) {++i;} // missing warning +} + + +// TODO: handle do-while loop +void voidBadDoWhileLoop() { + short i = 0; + do {++i;} while (i < size()); // missing warning +} + + +// We do not catch this, but other conversion related checks can catch it anyway +void voidReverseForLoop() { + for (short i = size() - 1; i >= 0; --i) {} // no warning +} + + +// TODO: handle those cases when the loop condition contains a floating point expression +void voidDoubleForCond() { + double condVar = size(); + for (short i = 0; i < condVar; ++i) {} // missing warning +} + + +// TODO: handle complex loop conditions +void voidComplexForCond() { + bool additionalCond = true; + for (int i = 0; i < size() && additionalCond; ++i) {} // missing warning +} + + +// Macro in loop condition +#define SIZE 125 +#define SIZE2 (SIZE + 1) +void voidForLoopWithMacroCond() { + for (short i = 0; i < SIZE2; ++i) {} // no warning +} + + +// Literal in loop condition +void voidForLoopWithLiteralCond() { + for (short i = 0; i < 125; ++i) {} // no warning +} + + +enum eSizeType { + START, + Y, + END +}; + + +// Enum in loop condition +void voidForLoopWithEnumCond() { + for (short i = eSizeType::START; i < eSizeType::END; ++i) {} // no warning +} + + +// Const value in loop condition +void voidForLoopWithConstCond() { + const long size = 252l; + for (short i = 0; i < size; ++i) {} // no warning +} +