[clang-tidy] Add MagnitudeBitsUpperLimit option to bugprone-too-small-loop-variable

[ztamas]

Summary

The bugprone-too-small-loop-variable check often catches loop variables which can represent "big enough" values, so we don't actually need to worry about that this variable will overflow in a loop when the code iterates through a container. For example a 32 bit signed integer type's maximum value is 2 147 483 647 and a container's size won't reach this maximum value in most of the cases.
So the idea of this option to allow the user to specify an upper limit (using magnitude bit of the integer type) to filter out those catches which are not interesting for the user, so he/she can focus on the more risky integer incompatibilities.
Next to the option I replaced the term "positive bits" to "magnitude bits" which seems a better naming both in the code and in the name of the new option.

[ztamas]

I run the check with and without the option on llvm source code. Without the option I found 370 catches, while setting MagnitudeBitsUpperLimit to 30 I found only two catches:

/home/zolnai/libreoffice/clang/llvm-project/llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp:390:32: warning: loop variable has narrower type 'uint16_t' (aka 'unsigned short') than iteration's upper bound 'uint32_t' (aka 'unsigned int') [bugprone-too-small-loop-variable]
  for (uint16_t StreamIdx = 0; StreamIdx < StreamCount; ++StreamIdx) {
                               ^

/home/zolnai/libreoffice/clang/llvm-project/llvm/tools/llvm-pdbutil/StreamUtil.cpp:98:32: warning: loop variable has narrower type 'uint16_t' (aka 'unsigned short') than iteration's upper bound 'uint32_t' (aka 'unsigned int') [bugprone-too-small-loop-variable]
  for (uint16_t StreamIdx = 0; StreamIdx < StreamCount; ++StreamIdx) {
                               ^

[ztamas]

I found a project where the bugprone-too-small-loop-variable was used:
https://github.com/openMSX/openMSX/commit/55006063daffa90941d4c3f9b0034e494d9cf45a

As the commit message says for 32-bit integers the overflow never happens in practice.

[Eugene.Zelenko]

docs/ReleaseNotes.rst

122 ↗

(On Diff #192417)

:doc prefix and ` is missing. Please also rebase patch from trunk.

[JonasToth]

I think in general this is a good direction. What do you think about other heuristics?
E.g. one could say that a vector will not contain more then X GB or similar. That is probably more complicated to figure out though.

docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst

44 ↗

(On Diff #192417)

no warning for which value? 31? Please make that explicit in the doc.

[ztamas]

In D59870#1444645, @JonasToth wrote:

I think in general this is a good direction. What do you think about other heuristics?
E.g. one could say that a vector will not contain more then X GB or similar. That is probably more complicated to figure out though.

Yes, it would be very complicated to find out the memory size of the container used in the code, I think. The used size method is not always the size() function. In llvm code I see also std::string::length() and array_lengthof(). Also a code might use a non-standard container, which might have different method for getting the size of the container which makes it hard to create a matcher for this and find out which container I need to get it's size.

Also the check can catch loops which are not related to containers, so a container related option would have no meening in these cases.

I think it's the easiest way to specify the bits of the ineteger type to limit the catches. In real life, I met with this overflow / infinite loop problem with 16-bit short type, so I think the real use cases are 8 and 16 bit integers. It seems intuitive to me to use the size of the loop variable's type to separate those catches which can lead broken functionality in practice from those use cases which are just integer incompatibilities.

docs/ReleaseNotes.rst

122 ↗

(On Diff #192417)

I'm a bit confused now about the code repositories, because of the recent changes. Which repo should I clone and rebase my commit?
Is this one the trunk?: http://llvm.org/svn/llvm-project/llvm/trunk

[ztamas]

Rebased patch on https://github.com/llvm/llvm-project.git repo.
Updated the docs based on review comments.

[JonasToth]

I think it's the easiest way to specify the bits of the ineteger type to limit the catches. In real life, I met with this overflow / infinite loop problem with 16-bit short type, so I think the real use cases are 8 and 16 bit integers. It seems intuitive to me to use the size of the loop variable's type to separate those catches which can lead broken functionality in practice from those use cases which are just integer incompatibilities.

Given your experience and the false positive rate in some projects, should we maybe default to 16 for that option?

[ztamas]

In D59870#1446537, @JonasToth wrote:

I think it's the easiest way to specify the bits of the ineteger type to limit the catches. In real life, I met with this overflow / infinite loop problem with 16-bit short type, so I think the real use cases are 8 and 16 bit integers. It seems intuitive to me to use the size of the loop variable's type to separate those catches which can lead broken functionality in practice from those use cases which are just integer incompatibilities.

Given your experience and the false positive rate in some projects, should we maybe default to 16 for that option?

Seems a good idea. I'll update the code accordingly.

[ztamas]

Make 16 the default value of MagnitudeBitsUpperLimit option.

[JonasToth]

clang-tools-extra/docs/ReleaseNotes.rst

124 ↗

(On Diff #193017)

Please add the new default here as its a change in behaviour of the check.

clang-tools-extra/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst

33 ↗

(On Diff #193017)

typo magnitude

The commit you reference to the project fixing the "bugs" stated, that the version without conversions is more efficient (by one instruction :)). I think this might be worth a note, that even though the
code is not a bug in itself it might still be preferable to remove those code locations in the long run.

[ztamas]

Fixed typo.
Mentioned the default value in release notes.

[ztamas]

clang-tools-extra/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst

33 ↗

(On Diff #193017)

Typo is fixed

The referenced commit message mentions 32 bit system, where changing integer types was a bit faster. I'm not sure how general this is. I'm not familiar with the low level implementation of integer comparison, so I would not mention something, that I don't actually understand how it works.

[JonasToth]

LGTM

clang-tools-extra/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst

33 ↗

(On Diff #193017)

I dont understand it either in detail, it sounded logical that you need to convert the different integer sizes first somehow, but I am fine with not mentioning it :)

[ztamas]

Fixed a typo in release notes.
Rebased the patch withh git pull -r.

[ztamas]

Ok, I just fixed a remaining typo and rebased the patch to have it work with a more recent version of the code base, so I guess this patch is ready for commit.
Jonas, can you commit this change for me? I still don't have commit access, I just applied for it some days ago.

[ztamas]

In the meantime, I've got the commit access, so I'll give it a try to push this myself.

clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.h

 ///   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) {}
+  TooSmallLoopVariableCheck(StringRef Name, ClangTidyContext *Context);
+
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  const unsigned MagnitudeBitsUpperLimit;
 };
 
 } // namespace bugprone
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_TOOSMALLLOOPVARIABLECHECK_H

clang-tools-extra/trunk/clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

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");
 
+TooSmallLoopVariableCheck::TooSmallLoopVariableCheck(StringRef Name,
+                                                     ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      MagnitudeBitsUpperLimit(Options.get<unsigned>(
+          "MagnitudeBitsUpperLimit", 16)) {}
+
+void TooSmallLoopVariableCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "MagnitudeBitsUpperLimit", MagnitudeBitsUpperLimit);
+}
+
 /// \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)
Finder->addMatcher(
                              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,
+/// Returns the magnitude bits of an integer type.
+static unsigned calcMagnitudeBits(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
+/// \brief Calculate the upper bound expression's magnitude bits, but ignore
 /// constant like values to reduce false positives.
-static unsigned calcUpperBoundPositiveBits(const ASTContext &Context,
+static unsigned calcUpperBoundMagnitudeBits(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.
+  // We are interested in variable values' magnitude 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);
+      return calcMagnitudeBits(Context, LHSEType);
     if (LHSEIsConstantValue)
-      return calcPositiveBits(Context, RHSEType);
+      return calcMagnitudeBits(Context, RHSEType);
 
-    return std::max(calcPositiveBits(Context, LHSEType),
-                    calcPositiveBits(Context, RHSEType));
+    return std::max(calcMagnitudeBits(Context, LHSEType),
+                    calcMagnitudeBits(Context, RHSEType));
   }
 
-  return calcPositiveBits(Context, UpperBoundType);
+  return calcMagnitudeBits(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);
+  unsigned LoopVarMagnitudeBits = calcMagnitudeBits(Context, LoopVarType);
+  unsigned UpperBoundMagnitudeBits =
+      calcUpperBoundMagnitudeBits(Context, UpperBound, UpperBoundType);
+
+  if (UpperBoundMagnitudeBits == 0)
+    return;
 
-  if (UpperBoundPosBits == 0)
+  if (LoopVarMagnitudeBits > MagnitudeBitsUpperLimit)
     return;
 
-  if (LoopVarPosBits < UpperBoundPosBits)
+  if (LoopVarMagnitudeBits < UpperBoundMagnitudeBits)
     diag(LoopVar->getBeginLoc(), "loop variable has narrower type %0 than "
                                  "iteration's upper bound %1")
         << LoopVarType << UpperBoundType;
 }
 
 } // namespace bugprone
 } // namespace tidy
 } // namespace clang

clang-tools-extra/trunk/docs/ReleaseNotes.rst

- New alias :doc:`cppcoreguidelines-explicit-virtual-functions
   <clang-tidy/checks/modernize-use-override>` was added.
 
 - The :doc:`bugprone-argument-comment
   <clang-tidy/checks/bugprone-argument-comment>` now supports
   `CommentBoolLiterals`, `CommentIntegerLiterals`, `CommentFloatLiterals`,
   `CommentUserDefiniedLiterals`, `CommentStringLiterals`,
   `CommentCharacterLiterals` & `CommentNullPtrs` options.
 
+- The :doc:`bugprone-too-small-loop-variable
+  <clang-tidy/checks/bugprone-too-small-loop-variable>` now supports
+  `MagnitudeBitsUpperLimit` option. The default value was set to 16,
+  which greatly reduces warnings related to loops which are unlikely to
+  cause an actual functional bug.
+
 - The :doc:`google-runtime-int <clang-tidy/checks/google-runtime-int>`
   check has been disabled in Objective-C++.
 
 - The `Acronyms` and `IncludeDefaultAcronyms` options for the
   :doc:`objc-property-declaration <clang-tidy/checks/objc-property-declaration>`
   check have been removed.
 
 - The :doc:`modernize-use-override

clang-tools-extra/trunk/docs/clang-tidy/checks/bugprone-too-small-loop-variable.rst

 .. 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.
+
+.. option:: MagnitudeBitsUpperLimit
+
+  Upper limit for the magnitude bits of the loop variable. If it's set the check
+  filters out those catches in which the loop variable's type has more magnitude
+  bits as the specified upper limit. The default value is 16.
+  For example, if the user sets this option to 31 (bits), then a 32-bit ``unsigend int``
+  is ignored by the check, however a 32-bit ``int`` is not (A 32-bit ``signed int``
+  has 31 magnitude bits).
+
+.. code-block:: c++
+
+  int main() {
+    long size = 294967296l;
+    for (unsigned i = 0; i < size; ++i) {} // no warning with MagnitudeBitsUpperLimit = 31 on a system where unsigned is 32-bit
+    for (int i = 0; i < size; ++i) {} // warning with MagnitudeBitsUpperLimit = 31 on a system where int is 32-bit
+  }

clang-tools-extra/trunk/test/clang-tidy/bugprone-too-small-loop-variable-magniute-bits-upper-limit.cpp

+// RUN: %check_clang_tidy %s bugprone-too-small-loop-variable %t -- -- --target=x86_64-linux
+
+// MagnitudeBitsUpperLimit = 16 (default value)
+
+unsigned long size() { return 294967296l; }
+
+void voidFilteredOutForLoop1() {
+  for (long i = 0; i < size(); ++i) {
+    // no warning
+  }
+}
+
+void voidCaughtForLoop1() {
+  for (int i = 0; i < size(); ++i) {
+    // no warning
+  }
+}
+
+void voidCaughtForLoop2() {
+  for (short i = 0; i < size(); ++i) {
+    // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: loop variable has narrower type 'short' than iteration's upper bound 'unsigned long' [bugprone-too-small-loop-variable]
+  }
+}

clang-tools-extra/trunk/test/clang-tidy/bugprone-too-small-loop-variable.cpp

-// RUN: %check_clang_tidy %s bugprone-too-small-loop-variable %t -- -- --target=x86_64-linux
+// RUN: %check_clang_tidy %s bugprone-too-small-loop-variable %t -- \
+// RUN:   -config="{CheckOptions: \
+// RUN:             [{key: bugprone-too-small-loop-variable.MagnitudeBitsUpperLimit, \
+// RUN:               value: 1024}]}" \
+// RUN:   -- --target=x86_64-linux
 
 long size() { return 294967296l; }
 
 ////////////////////////////////////////////////////////////////////////////////
 /// Test cases correctly caught by bugprone-too-small-loop-variable.
 
 void voidBadForLoop() {
   for (int i = 0; i < size(); ++i) {