ztamas updated this revision to Diff 173573.
ztamas added a comment.
- Add requested test case
Repository:
rCTE Clang Tools Extra
https://reviews.llvm.org/D53974
Files:
clang-tidy/bugprone/BugproneTidyModule.cpp
clang-tidy/bugprone/CMakeLists.txt
clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp
clang-tidy/bugprone/TooSmallLoopVariableCheck.h
docs/ReleaseNotes.rst
docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst
docs/clang-tidy/checks/list.rst
test/clang-tidy/bugprone-too-small-loop-variable.cpp
Index: test/clang-tidy/bugprone-too-small-loop-variable.cpp
===================================================================
--- /dev/null
+++ 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 <long size>
+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 <class T>
+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<long>();
+ // This one triggers the warning.
+ doSomething<short>();
+}
+
+// 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
+ }
+}
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: 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,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: docs/ReleaseNotes.rst
===================================================================
--- docs/ReleaseNotes.rst
+++ 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
+ <clang-tidy/checks/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
<clang-tidy/checks/cppcoreguidelines-macro-usage>` check.
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,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<BinaryOperator>(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<IntegerLiteral>(RHSE);
+ bool LHSEIsConstantValue = LHSEType->isEnumeralType() ||
+ LHSEType.isConstQualified() ||
+ isa<IntegerLiteral>(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<Expr>(LoopVarName);
+ const auto *UpperBound =
+ Result.Nodes.getNodeAs<Expr>(LoopUpperBoundName)->IgnoreParenImpCasts();
+ const auto *LoopIncrement =
+ Result.Nodes.getNodeAs<Expr>(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-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/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<MultipleStatementMacroCheck>(
"bugprone-multiple-statement-macro");
+ CheckFactories.registerCheck<TooSmallLoopVariableCheck>(
+ "bugprone-too-small-loop-variable");
CheckFactories.registerCheck<cppcoreguidelines::NarrowingConversionsCheck>(
"bugprone-narrowing-conversions");
CheckFactories.registerCheck<ParentVirtualCallCheck>(
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
