[clang-tidy] new check: bugprone-too-small-loop-variable

[ztamas]

Summary

The new checker 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.

For example:

int main() {
  long size = 300000;
  for( short int i = 0; i < size; ++i) {}
}

The short type leads to infinite loop here because it can't store all values in the [0..size] interval. In a real use case, size means a container's size which depends on the user input. Which means for small amount of objects the algorithm works, but with a larger user input the software will freeze.

The idea of the checker comes from the LibreOffice project, where the same check was implemented as a clang compiler plugin, called LoopVarTooSmall (LLVM licensed).
The idea is the same behind this check, but the code is different because of the different framework.

[ztamas]

Add a description of the checker with examples to the documentation

[ztamas]

Just a note. I run the new checker on LibreOffice project. I found ~25 false positives, which seems small enough to me. This false positives can be supressed easily.
Since the LibreOffice project has a similar check as a compiler plugin the code was already cleaned up, however I still found ~30 uncaught issue with the new checker:
https://cgit.freedesktop.org/libreoffice/core/commit/?id=26ccd00bc96c585b7065af0dcce246b5bfaae5e1

[ZaMaZaN4iK]

Hmm, i thought Clang has some warning for this, but I was wrong... Did you think to implement this check as Clang warning?

[Eugene.Zelenko]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

27

Please remove unnecessary empty line.

42

Please remove unnecessary empty line.

86

Please remove unnecessary empty line.

89

Please remove unnecessary empty line.

97

Please remove unnecessary empty line.

100

Please remove unnecessary empty line.

106

Please run Clang-format.

109

Please remove unnecessary empty line.

115

Please remove unnecessary empty line.

122

Please remove unnecessary empty line.

124

Braces are not needed.

127

Please remove unnecessary empty line.

130

Braces are not needed.

131

Please remove unnecessary empty line.

133

Please remove unnecessary empty line.

134

Braces are not needed.

135

Please remove unnecessary empty line.

139

Braces are not needed.

140

Please remove unnecessary empty line.

142

Please remove unnecessary empty line.

150

Please remove unnecessary empty line.

154

Please remove unnecessary empty line.

182

Braces are not needed.

docs/ReleaseNotes.rst

70

Please sort list of new checks alphabetically.

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

7

Please synchronize with Release Notes.

13

Please insert empty line above.

14

Braces are repeated twice.

19

Please remove unnecessary empty line.

24

Please insert empty line above.

25

Braces are repeated twice.

[sberg]

I run the new checker on LibreOffice project. I found ~25 false positives, which seems small enough to me. This false positives can be supressed easily.

Do you have a link to such a false positive and how it got suppressed in the LibreOffice code base? (If those are included in the referenced https://cgit.freedesktop.org/libreoffice/core/commit/?id=26ccd00bc96c585b7065af0dcce246b5bfaae5e1, I failed to spot them.)

[ztamas]

In D53974#1283833, @sberg wrote:

I run the new checker on LibreOffice project. I found ~25 false positives, which seems small enough to me. This false positives can be supressed easily.

Do you have a link to such a false positive and how it got suppressed in the LibreOffice code base? (If those are included in the referenced https://cgit.freedesktop.org/libreoffice/core/commit/?id=26ccd00bc96c585b7065af0dcce246b5bfaae5e1, I failed to spot them.)

I did not supress anything yet, since this checker is still work in progress. The final version might avoid those false postives.
One example in basic/source/runtime/dllmgr-x86.cxx
This line:
for (sal_uInt16 i = 1; i < (arguments == 0 ? 0 : arguments->Count()); ++i)

arguments->Count() returns a sal_uInt16 too, which is unsigned short, however "0" is an int literal so the "<>?<>:<>" expression will have an int type.
To supress that you can cast the literal:

for (sal_uInt16 i = 1; i < (arguments == 0 ? (sal_uInt16)0 : arguments->Count()); ++i)

Or cast the whole expression:

for (sal_uInt16 i = 1; i < (sal_uInt16)(arguments == 0 ? 0 : arguments->Count()); ++i)

Or use int for the loop variable:

for (int i = 1; i < (arguments == 0 ? 0 : arguments->Count()); ++i)

[ztamas]

In D53974#1283759, @ZaMaZaN4iK wrote:

Hmm, i thought Clang has some warning for this, but I was wrong... Did you think to implement this check as Clang warning?

It did not come in my mind to do that. It might be good idea, I guess. This version of the check however might find too much false positives for a clang warning.

[ztamas]

In D53974#1283833, @sberg wrote:

I run the new checker on LibreOffice project. I found ~25 false positives, which seems small enough to me. This false positives can be supressed easily.

Do you have a link to such a false positive and how it got suppressed in the LibreOffice code base? (If those are included in the referenced https://cgit.freedesktop.org/libreoffice/core/commit/?id=26ccd00bc96c585b7065af0dcce246b5bfaae5e1, I failed to spot them.)

I uploaded here the output of the new checker on LibreOffice after my referenced commit:
https://gist.github.com/tzolnai/9c2c78323c098e2e09d63c1a1384274b

Search for bugprone-too-small-loop-variable in the log. Not all are false positives.

[JonasToth]

For general understanding: Couldn't this check be generalized to comparing integers of different sizes? We tried a 'dont-mix-int-types' check for arithmetic already, its complicated :)
But this as a specialization of the category could be done easier (i think).

What do you think?

[ztamas]

In D53974#1284000, @JonasToth wrote:

For general understanding: Couldn't this check be generalized to comparing integers of different sizes? We tried a 'dont-mix-int-types' check for arithmetic already, its complicated :)
But this as a specialization of the category could be done easier (i think).

What do you think?

I don't think so. This comparison is suspicious only inside a loop, not in general.
For example see this code:

long size = 300000;
short index = 100;

if(index < size) {
 // ....
}

You can choose the two values as you want, this comparison will work correctly.
However in a loop condition this comparison means a problem, because the loop stops only if the "index" variable gets bigger than the "size" variable.
So the loop context is important here.

[JonasToth]

But that reasoning would apply to if and while loops, as it might be
an "always true". But you are right, this case is not generally problematic.

long size = 300000;
short index = 100;
// Opposite comparison
if(index > size) {
 // ....
}

[ztamas]

Run clang-formats on files, remove unneeded empty lines, fix up documentation.

[ztamas]

I fixed up formatting and the docs based on comments.

[ztamas]

Just to make it clear. I think this check is in a good shape now. I mean it catches usefull issues and also does not produce too many false positives, as I see.
So my intention here is to get it in as it is now (of course after I fixed things reviewers find) and later it can be improved in separate patches (e.g. reduce false positives even more, handle other use cases like while loop etc.). I think it would be better to have smaller patches than polishing this big one until it gets ~prefect.
In the test file I added some TODO comments. They were added as a documentation of future possibilities.

[whisperity]

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

19

Format the interval as code (monospace): [0 .. size]

25

There is a typo in the function's name.

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

117

(Misc: You might want to check out D52730 for floats later down the line.)

[JonasToth]

In D53974#1285585, @ztamas wrote:

Just to make it clear. I think this check is in a good shape now. I mean it catches usefull issues and also does not produce too many false positives, as I see.

Yes, I did not want to stop the patch or so! It would be great to remove the false-positive as they might annoy users and as consequence turn the check off.

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

Please move these variable in the matcher function and make them StringRef instead of const char[].

41

please do not qualify values as const. LLVM style only qualifies pointers and references. (here and elsewhere).

46

Please make all comments full sentences with punctuation and working grammar (here and elsewhere). I won't be the judge, but aaron ;)

83

You can ellide the \brief here.

107

isInstantiationDependent(), but please filter that already while matching.

111

const

118

As noted on the other place, i think macros should not be ignored. If the macro defines a constant, it is handled by IntegerLiteral

135

You can move the ignoreParenImpCasts to the matchers, there is a specific one for that.

139

You can replace the two conditions with isInstantiationDependent(), there shuold be a matcher for that too. Ignoring them there already should be beneficial.

150

I do not agree with the comment here. Macros can hide weird stuff from time to time, especially "inlined" functions. These should be analyzed as well.

159

const

167

The diag can be shortened a bit loop variable has narrower typ %0 than terminating condition %1 or similar. Diags are not sentences.

docs/ReleaseNotes.rst

116

Please mark code-constructs with two backticks to emphasize them in documentation. in this case for

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

7

for

18

for, short

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

7

please add tests where the rhs is a literal.

153

It is possible to specify the underlying type of an enum.
For the case enum eSizeType2 : int; the problem does occur as well. I think especially this case is tricky to spot manually and should be handled too. What do you think?

[ztamas]

Update code based on reviewer comments:

• Remove const qualifier
• Fix some comments
• Use isInstantiationDependent() method
• Do not ignore macros
• Mark code-constructs in docs
• Handle the use case when both operands of the binary operator is constant inside the condition expression.

[ztamas]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

These variables are used not only inside the matcher function but also in the check() function.

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

117

In the meantime, I thought this float comparison is not a real use case. It just came in my mind while I was trying to find out test cases. So I just removed it. The referenced conversion check might catch it anyway.

[ztamas]

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

7

Do you mean tests like voidForLoopWithLiteralCond()?
Is it worth to add more tests like that?

153

Hmm, it can be handled I think. However, I'm not sure how often it is, that an enum has an item value bigger than 32767 (short) or 65535 (unsigned short) or another even bigger value.
For now, I think it's better to just ignore these cases to avoid false positives and keep the first version of the check simple. The scope can be extended anytime later I think.

[JonasToth]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

I didn't see that, but they should still be StringRef as type.

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

7

I didn't see it. In principle yes, but i would like to see a test with a bigger number then iterateable (maybe there is a frontend warning for that?). If there is no warning, this should definitely be implemented here (possible follow up) or even become a frontend warning.

153

enum values can become very big for flag-enums

enum Foo {
  value1 = 1 << 1;
// ...
  value 24 = 1 << 24;
};

You should still add a test for a enum with specified underlying type to ensure, there is no noise.

[Szelethus]

In D53974#1283759, @ZaMaZaN4iK wrote:

Hmm, i thought Clang has some warning for this, but I was wrong... Did you think to implement this check as Clang warning?

That is an interesting point actually -- maybe it'd be worth doing that, and if more powerful analysis is required, Static Analyzer would be the next step. I haven't actually implemented any 'regular' clang warning, so I'm not sure.

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

109

You seem to have code for handling templates, but I don't see test cases for it.

[ztamas]

• Use StringRef instead of char[]
• Add test cases about big constant / literal / enum values

[ztamas]

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

7

I added a test case. This kind of test cases are caught by -Wtautological-constant-out-of-range-compare, so we are good I think.

[Eugene.Zelenko]

docs/ReleaseNotes.rst

116

Please avoid This check, may be Detects? Same in documentation.

116

Somehow for is still highlighted with single , should be `. Same in documentation.

[ztamas]

• Analyze template dependant for loops too (add some test cases)
• Use double backticks for marking code in docs

[ztamas]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

109

Thanks for mentioning it. I was overdefensive against false positives. This isInstantiationDependent() is not needed here. So I removed and added some test cases with templates.

[ztamas]

Update docs based on reviewer comment

[ztamas]

In D53974#1285930, @Szelethus wrote:

In D53974#1283759, @ZaMaZaN4iK wrote:

Hmm, i thought Clang has some warning for this, but I was wrong... Did you think to implement this check as Clang warning?

That is an interesting point actually -- maybe it'd be worth doing that, and if more powerful analysis is required, Static Analyzer would be the next step. I haven't actually implemented any 'regular' clang warning, so I'm not sure.

Well, I'm implementing it as a clang-tidy check now. I guess in the future anyone can replace it with a clang warning if he/she can implement it effectively (e.g. no false positives).

My first impression was that having something accepted as clang static analyzer check takes ages and so I expect that implementing something as a clang warning takes even more time. My impression is based on bugzilla activity and on some read review history. It seems to me it's not rare to have comments like: "Ping, let's not abandon this change" or the author says that he/she has no more time for further work, etc. However clang-tidy seems more progressive. So I prefer to have something as a clang-tidy check (and actually get it in the upstream tool) than implementing it as a clang warning (if it can be implemented effectively at all), wait for a year of review and most probably abandon the change. Of course, it's just a first impression, but why should I take the risk. I think this clang-tidy check is powerful, so useful to have it.

[Szelethus]

In D53974#1286434, @ztamas wrote:

In D53974#1285930, @Szelethus wrote:

In D53974#1283759, @ZaMaZaN4iK wrote:

Hmm, i thought Clang has some warning for this, but I was wrong... Did you think to implement this check as Clang warning?

That is an interesting point actually -- maybe it'd be worth doing that, and if more powerful analysis is required, Static Analyzer would be the next step. I haven't actually implemented any 'regular' clang warning, so I'm not sure.

Well, I'm implementing it as a clang-tidy check now. I guess in the future anyone can replace it with a clang warning if he/she can implement it effectively (e.g. no false positives).

My first impression was that having something accepted as clang static analyzer check takes ages and so I expect that implementing something as a clang warning takes even more time. My impression is based on bugzilla activity and on some read review history. It seems to me it's not rare to have comments like: "Ping, let's not abandon this change" or the author says that he/she has no more time for further work, etc. However clang-tidy seems more progressive. So I prefer to have something as a clang-tidy check (and actually get it in the upstream tool) than implementing it as a clang warning (if it can be implemented effectively at all), wait for a year of review and most probably abandon the change. Of course, it's just a first impression, but why should I take the risk. I think this clang-tidy check is powerful, so useful to have it.

Okay, I'm sold on that :).

[ztamas]

Mark all handled inline comments as Done.

[JonasToth]

Regarding the warning discussion: It is ok to have this check here in clang-tidy first and let it mature. Once we can handle all kind of loops and do not produce false positives this logic can move into the frontend.
But in my opinion the warning-version should handle all loops. Until then we can happily have this here :)

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

46

missing full stop.

52

same

61

same.

83

same, other places too, but i won't mark them anymore.

101

marco defined is outdated.

I think the sentence should be improved. Maybe Ignore casting cause by constant values inside a binary operator, e.g. from ... .?

121

I think that comment should be before the if to be consistent with other comment positions, and missing full stop.

123

you can utilize early return for all these cases.
Please don't use if-else then, because no return after else-rule.

143

Does this try to ensure a precondition? Then it should become an assertion instead.
Please adjust the comment like above (punctuation, position)

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

7

Disclaimer: english isn't my mother tongue and its not perfect :)

which has -> that have? Sounds better to me.

11

the .. code-block:: c++ is usually not indended, only the code itself.

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

6

please add tests for range-for loops to ensure the implicitly generated loop does not generate any false positives or the like.

[ztamas]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

46

Sorry, I forgot the punctuation what you've already mentioned.

143

It's not an assumed precondition. This if handles the case when LoopVarMatcher is not fitted with the actual loop variable. That's why the IncrementMatcher is there so we can check whether we found the loop variable.
See voidForLoopReverseCond() test case which hits this if branch.
I did not find a solution to handle this check inside the matcher.

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

11

Hmm, I copied this from somewhere. It might be a good idea to make this consistent across all the *.rst files. See bugprone-suspicious-semicolon.rst or bugprone-use-after-move.rst for example.

[ztamas]

• Add a range-based loop test case
• Restructure test cases a bit
• Fix-up comments, position, punctuation

[ztamas]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

143

voidForLoopReverseCond() was renamed to voidForLoopCondImplicitCast() in the mean time.

[JonasToth]

last nits from my side (for now :)).
If the other reviews could take a look at it as well, would be great.
I am uncertain about the english in some comments @aaron.ballman finds all these language bugs ;)

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

124

please no else after return

127

same

143

Ok, I can't think of a solution of head right now as well. It's fine to leave as is.

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

11

True, but nobody want's to do the documentation work :D

[Eugene.Zelenko]

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

11

I could try to fix, but I need to be pointed to proper example :-)

[JonasToth]

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

11

A nice little sed line i had to write 3 times fixed the thing :D

[JonasToth]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

One more nit i forgot: these variables should be static for linkage and be CamelCase to match the naming conventions.

[Szelethus]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

Hmmm, StringRef actually has a constexpr constructor, we could make these constexpr too I guess.

[lebedev.ri]

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

21

You want StringLiteral:

static constexpr llvm::StringLiteral loopVarCastName = llvm::StringLiteral("loopVarCast");
static constexpr llvm::StringLiteral loopCondName = llvm::StringLiteral("loopCond");
static constexpr llvm::StringLiteral loopIncrementName = llvm::StringLiteral("loopIncrement");

[ztamas]

• no else after return
• static constexpr llvm::StringLiteral
• CamelCase variable names
• Remove unneeded isIntegerType() check
• Better terminology: not terminating condition, but iteration's upper bound.

[JonasToth]

LG from my side. Please wait for feedback from @aaron.ballman or @alexfh before committing.

[ztamas]

• Make local functions static

[JonasToth]

LGTM.
Did you run this check in its final form against a bigger project? These results would be interesting.
Do you have commit access?

[ztamas]

In D53974#1293268, @JonasToth wrote:

LGTM.
Did you run this check in its final form against a bigger project? These results would be interesting.

I'll run it on LibreOffice code again and we'll see.

Do you have commit access?

Commit access? This is my first patch.

[JonasToth]

I'll run it on LibreOffice code again and we'll see.

Perfect, if you have the time, running it against LLVM would be very interesting as well.

Do you have commit access?

Commit access? This is my first patch.

If you plan to regularly contribute to LLVM you can ask for commit access (process written here: https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access).
I (or someone else) can commit this patch for you in the meanwhile (of course with attribution to you).

[ztamas]

I have the result after running the current version of the check on LibreOffice.

Found around 50 new issues were hidden by macros:
https://cgit.freedesktop.org/libreoffice/core/commit/?id=afbfe42e63cdba1a18c292d7eb4875009b0f19c0

Also found some new false positives related to macros. The number of all false positives is around 38, which is still seems good to me.

[ztamas]

I also tested on LLVm code.
The output is here:
https://gist.github.com/tzolnai/fe4f23031d3f9fdbdbf1ee38abda00a4

I found 362 warnings.

Around 95% of these warnings are similar to the next example:

/home/zolnai/lohome/llvm/lib/Support/Chrono.cpp:64:24: warning: loop variable has narrower type 'unsigned int' than iteration's upper bound 'size_t' (aka 'unsigned long') [bugprone-too-small-loop-variable]
  for (unsigned I = 0; I < Style.size(); ++I) {

Where the loop variable has an unsigned int type while in the loop condition it is compared with a container size which has size_t type. The actual size method can be std::string::length() or array_lengthof() too.

An interesting catch related to a template function:

/home/zolnai/lohome/llvm/tools/clang/lib/CodeGen/CGNonTrivialStruct.cpp:310:24: warning: loop variable has narrower type 'unsigned int' than iteration's upper bound 'size_t' (aka 'unsigned long') [bugprone-too-small-loop-variable]
  for (unsigned I = 0; I < N; ++I)

Where N is a template value with size_t type. If the container function is instantiated with a "large" value I expect the function won't work. I guess it never actually happens.

An other catch inside a macro:

/home/zolnai/lohome/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp:157:5: warning: loop variable has narrower type 'uint32_t' (aka 'unsigned int') than iteration's upper bound 'std::vector::size_type' (aka 'unsigned long') [bugprone-too-small-loop-variable]
    IMPLEMENT_VECTOR_INTEGER_ICMP(ne,Ty);
    ^
/home/zolnai/lohome/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp:123:24: note: expanded from macro 'IMPLEMENT_VECTOR_INTEGER_ICMP'
    for( uint32_t _i=0;_i<Src1.AggregateVal.size();_i++)

I can't see similar false positives what LibreOffice code produces. In the case of LibreOffice short type loop variables used to lead to false positives. I expect that in LLVM code short type is not used frequently in a loop. The closest case which can be interpreted as a false positive is the next one:

/home/zolnai/lohome/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp:2432:21: warning: loop variable has narrower type 'unsigned int' than iteration's upper bound 'unsigned long' [bugprone-too-small-loop-variable]
    for (Chunk = 0; Chunk < NumBytes / sizeof(uint64_t); ++Chunk)

Where Chunk and NumBytes both have unsigned type. sizeof(uint64_t) leads to the warning, which won't make the whole expression actually bigger. It's a similar constant like value as enums, literals, etc, which are ignored by the check. I count around 10 similar use cases where I saw that the sizeof() is used on a type, so must be constant in runtime.

I did not see any other kind of false positives.

[JonasToth]

Thank you for checking these two projects!

In D53974#1294375, @ztamas wrote:

I have the result after running the current version of the check on LibreOffice.

Found around 50 new issues were hidden by macros:
https://cgit.freedesktop.org/libreoffice/core/commit/?id=afbfe42e63cdba1a18c292d7eb4875009b0f19c0

Also found some new false positives related to macros. The number of all false positives is around 38, which is still seems good to me.

I would be very interested why these false positives are created. Is there a way to avoid them and maybe it makes sense to already add FIXME at the possible places the check needs improvements.

[whisperity]

In D53974#1294385, @ztamas wrote:

I also tested on LLVm code.
The output is here:
https://gist.github.com/tzolnai/fe4f23031d3f9fdbdbf1ee38abda00a4

I found 362 warnings.

Around 95% of these warnings are similar to the next example:

/home/zolnai/lohome/llvm/lib/Support/Chrono.cpp:64:24: warning: loop variable has narrower type 'unsigned int' than iteration's upper bound 'size_t' (aka 'unsigned long') [bugprone-too-small-loop-variable]
  for (unsigned I = 0; I < Style.size(); ++I) {

Where the loop variable has an unsigned int type while in the loop condition it is compared with a container size which has size_t type. The actual size method can be std::string::length() or array_lengthof() too.

[snip snip]

I can't see similar false positives what LibreOffice code produces.

I am fairly concerned the example with unsigned use for container iteration are not false positives, just examples of bad happenstance code which never breaks under real life applications due to uint32_t being good enough but is actually not type-safe.
Those examples that I kept in my quote are especially bad and should be fixed eventually...

[ztamas]

• Add new test cases based on findings in LibreOffice code base

[ztamas]

Also found some new false positives related to macros. The number of all false positives is around 38, which is still seems good to me.

I would be very interested why these false positives are created. Is there a way to avoid them and maybe it makes sense to already add FIXME at the possible places the check needs improvements.

voidForLoopFalsePositive() and voidForLoopFalsePositive2() test cases covers most of the false positives found in LibreOffice.

[ztamas]

• Fix comment

[JonasToth]

I would be very interested why these false positives are created. Is there a way to avoid them and maybe it makes sense to already add FIXME at the possible places the check needs improvements.

voidForLoopFalsePositive() and voidForLoopFalsePositive2() test cases covers most of the false positives found in LibreOffice.

I would not consider them as full false positives, the constants that are created allow to filter more, but type-based the diagnostics are correct. So I think that is fine. If the constants would be a big value, the check does find a real problem.

@whisperity

I am fairly concerned the example with unsigned use for container iteration are not false positives, just examples of bad happenstance code which never breaks under real life applications due to uint32_t being good enough but is actually not type-safe.
Those examples that I kept in my quote are especially bad and should be fixed eventually...

clang-tidy is not about finding _only_ bugs, but find patterns that can be problematic but are not in every instance (therefore bugprone- and not bug-).
uint32_t does not span the whole memory-space for current hardware and a std::string can have more then uint32_t::max elements. Diagnosing this is valid.
Containers where uint32_t::max * sizeof(element_type) > size_t::max could be filtered for normal iteration over the container. I would consider it still a bugprone pattern.

[ztamas]

In D53974#1294659, @JonasToth wrote:

I would be very interested why these false positives are created. Is there a way to avoid them and maybe it makes sense to already add FIXME at the possible places the check needs improvements.

voidForLoopFalsePositive() and voidForLoopFalsePositive2() test cases covers most of the false positives found in LibreOffice.

I would not consider them as full false positives, the constants that are created allow to filter more, but type-based the diagnostics are correct. So I think that is fine. If the constants would be a big value, the check does find a real problem.

Yes, that's right, these are not full false positives, but the check's main focus is on those loops which are runtime dependent. If a loop's upper bound can be calculated in compile time then this loop should be caught by a compiler warning based on the actual value of that constant. See -Wtautological-constant-out-of-range-compare for example. So I think it's the best if we can avoid catching these issues using a type based matching.
Anyway, there is not too many of this kind of false positives, so it's not a big issue. In LLVM code I did not find any similar case.
I can't see full false positives where the check works incorrectly. The detected type mismatch seems correctly detected in every case.

[JonasToth]

Yes, that's right, these are not full false positives, but the check's main focus is on those loops which are runtime dependent. If a loop's upper bound can be calculated in compile time then this loop should be caught by a compiler warning based on the actual value of that constant. See -Wtautological-constant-out-of-range-compare for example. So I think it's the best if we can avoid catching these issues using a type based matching.
Anyway, there is not too many of this kind of false positives, so it's not a big issue. In LLVM code I did not find any similar case.
I can't see full false positives where the check works incorrectly. The detected type mismatch seems correctly detected in every case.

Agree. I think this check is good to go.

I would commit this check tomorrow if that is ok with you.

[JonasToth]

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

139

Could you please add a test

for (short i = 0; i < (!cond ? size : 0); ++i) {
}

as well. Just to make sure the analysis does not depent on the type of the LHS. If it does, add a FIXME for later.

[ztamas]

• Add requested test case

[ztamas]

Agree. I think this check is good to go.

I would commit this check tomorrow if that is ok with you.

Of course, It would be great if this check can get in, Thanks!

[JonasToth]

Committed r346665.

Thank you very much for the patch!

[ztamas]

Thank you very much for the patch!

Thank you for reviewing!

clang-tidy/bugprone/BugproneTidyModule.cpp

 #include "SuspiciousEnumUsageCheck.h"
 #include "SuspiciousMemsetUsageCheck.h"
 #include "SuspiciousMissingCommaCheck.h"
 #include "SuspiciousSemicolonCheck.h"
 #include "SuspiciousStringCompareCheck.h"
 #include "SwappedArgumentsCheck.h"
 #include "TerminatingContinueCheck.h"
 #include "ThrowKeywordMissingCheck.h"
+#include "TooSmallLoopVariableCheck.h"
 #include "UndefinedMemoryManipulationCheck.h"
 #include "UndelegatedConstructorCheck.h"
 #include "UnusedRaiiCheck.h"
 #include "UnusedReturnValueCheck.h"
 #include "UseAfterMoveCheck.h"
 #include "VirtualNearMissCheck.h"
 
 namespace clang {
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<MisplacedOperatorInStrlenInAllocCheck>(
         "bugprone-misplaced-operator-in-strlen-in-alloc");
     CheckFactories.registerCheck<MisplacedWideningCastCheck>(
         "bugprone-misplaced-widening-cast");
     CheckFactories.registerCheck<MoveForwardingReferenceCheck>(
         "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>(
         "bugprone-parent-virtual-call");
     CheckFactories.registerCheck<SizeofContainerCheck>(
         "bugprone-sizeof-container");
     CheckFactories.registerCheck<SizeofExpressionCheck>(
         "bugprone-sizeof-expression");

clang-tidy/bugprone/CMakeLists.txt

add_clang_library(clangTidyBugproneModule
   SuspiciousEnumUsageCheck.cpp
   SuspiciousMemsetUsageCheck.cpp
   SuspiciousMissingCommaCheck.cpp
   SuspiciousSemicolonCheck.cpp
   SuspiciousStringCompareCheck.cpp
   SwappedArgumentsCheck.cpp
   TerminatingContinueCheck.cpp
   ThrowKeywordMissingCheck.cpp
+  TooSmallLoopVariableCheck.cpp
   UndefinedMemoryManipulationCheck.cpp
   UndelegatedConstructorCheck.cpp
   UnusedRaiiCheck.cpp
   UnusedReturnValueCheck.cpp
   UseAfterMoveCheck.cpp
   VirtualNearMissCheck.cpp
 
   LINK_LIBS

clang-tidy/bugprone/TooSmallLoopVariableCheck.h

+//===--- 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

clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

+//===--- 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) {
+  StatementMatcher LoopVarMatcher =
+      expr(
+          ignoringParenImpCasts(allOf(declRefExpr(to(varDecl(hasType(isInteger())))),
+                                      unless(isInstantiationDependent()))))
+          .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 condition is a variable
+  // value (not const, enum, etc.)
+  StatementMatcher LoopCondMatcher =
+      expr(ignoringParenImpCasts(allOf(hasType(isInteger()),
+                                       unless(integerLiteral()),
+                                       unless(hasType(isConstQualified())),
+                                       unless(hasType(enumType())),
+                                       unless(isInstantiationDependent()))))
+          .bind(loopCondName);
+
+  // We use the loop increment expression only to make sure we found the right
+  // loop variable
+  StatementMatcher IncrementMatcher =
+      expr(ignoringParenImpCasts(allOf(hasType(isInteger()),
+                                       unless(isInstantiationDependent())))).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);
+}
+
+/// 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<BinaryOperator>(CondExpr)) {
+    const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts();
+    const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts();
+
+    if (RHSE->isInstantiationDependent() || LHSE->isInstantiationDependent())
+      return 0;
+
+    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);
+
+    if (RHSEIsConstantValue && LHSEIsConstantValue)
+        return 0; // Avoid false positives produced by two constant values
+    else if (RHSEIsConstantValue)
+      CondExprPosBits = calcPositiveBits(Context, LHSEType);
+    else if (LHSEIsConstantValue)
+      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<Expr>(loopVarName);
+  const auto *CondExpr =
+      Result.Nodes.getNodeAs<Expr>(loopCondName)->IgnoreParenImpCasts();
+  const auto *LoopIncrement =
+      Result.Nodes.getNodeAs<Expr>(loopIncrementName)->IgnoreParenImpCasts();
+
+  if (LoopVar->getType() != LoopIncrement->getType())
+    return; // We matched the loop variable incorrectly
+
+  QualType LoopVarType = LoopVar->getType();
+  QualType CondExprType = CondExpr->getType();
+
+  ASTContext &Context = *Result.Context;
+
+  if (!LoopVarType->isIntegerType() || !CondExprType->isIntegerType())
+    return;
+
+  unsigned LoopVarPosBits = calcPositiveBits(Context, LoopVarType);
+  unsigned CondExprPosBits =
+      calcCondExprPositiveBits(Context, CondExpr, CondExprType);
+
+  if (CondExprPosBits == 0)
+    return;
+
+  if (LoopVarPosBits < CondExprPosBits)
+    diag(LoopVar->getBeginLoc(), "loop variable has narrower type %0 than "
+                                 "terminating condition %1")
+        << LoopVarType << CondExprType;
+}
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang

docs/ReleaseNotes.rst

 Improvements to clang-rename
 ----------------------------
 
 The improvements are...
 
 Improvements to clang-tidy
 --------------------------
 
 - New :doc:`abseil-duration-division
   <clang-tidy/checks/abseil-duration-division>` check.
 
   Checks for uses of ``absl::Duration`` division that is done in a
   floating-point context, and recommends the use of a function that
   returns a floating-point value.
 
 - New :doc:`abseil-duration-factory-float
   <clang-tidy/checks/abseil-duration-factory-float>` check.
- New :doc:`abseil-redundant-strcat-calls
   being passed to another ``absl::StrCat`` or ``absl::StrAppend``.
 
 - New :doc:`abseil-str-cat-append
   <clang-tidy/checks/abseil-str-cat-append>` check.
 
   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.
+
+  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.
+
 - New :doc:`cppcoreguidelines-macro-usage
   <clang-tidy/checks/cppcoreguidelines-macro-usage>` check.
 
   Finds macro usage that is considered problematic because better language
   constructs exist for the task.
 
 - New :doc:`misc-non-private-member-variables-in-classes
   <clang-tidy/checks/misc-non-private-member-variables-in-classes>` check.

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

+.. 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 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.

docs/clang-tidy/checks/list.rst

.. toctree::
    bugprone-suspicious-enum-usage
    bugprone-suspicious-memset-usage
    bugprone-suspicious-missing-comma
    bugprone-suspicious-semicolon
    bugprone-suspicious-string-compare
    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
    bugprone-unused-return-value
    bugprone-use-after-move
    bugprone-virtual-near-miss
    cert-dcl03-c (redirects to misc-static-assert) <cert-dcl03-c>
    cert-dcl16-c (redirects to readability-uppercase-literal-suffix) <cert-dcl16-c>

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

+// 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 narrower type 'int' than terminating condition '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 terminating condition '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 terminating condition '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 terminating condition '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 terminating condition '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 terminating condition 'long' [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 narrower type 'int' than terminating condition 'unsigned int' [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 narrower type 'short' than terminating condition 'int' [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()) { // missing warning
+    ++i;
+  }
+}
+
+// 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 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
+  }
+}