[clang-tidy] New bugprone-infinite-loop check for detecting obvious infinite loops

[baloghadamsoftware]

Summary

Finding infinite loops is well-known to be impossible (halting problem). However, it is possible to detect some obvious infinite loops, for example, if the loop condition is not changed. Detecting such loops is beneficial since the tests will hang on programs containing infinite loops so testing-time detection may be costly in large systems. Obvious cases are where the programmer forgets to increment/decrement the counter or increments/decrements the wrong variable.

[lebedev.ri]

Thanks for working on this!
You want to use clang/Analysis/Analyses/ExprMutationAnalyzer.h.
See also: D51870

[Eugene.Zelenko]

clang-tidy/bugprone/InfiniteLoopCheck.cpp

164 ↗

(On Diff #209837)

Unnecessary initialization. See readability-redundant-string-init.

docs/ReleaseNotes.rst

114 ↗

(On Diff #209837)

Wrong entry.

238 ↗

(On Diff #209837)

Please move into new checks list (in alphabetical order)

239 ↗

(On Diff #209837)

Please separate with empty line and use first statement from documentation here.

docs/clang-tidy/checks/bugprone-infinite-loop.rst

13 ↗

(On Diff #209837)

Please use double back-ticks to highlight language constructs. Same below.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

In D64736#1585484, @lebedev.ri wrote:

Thanks for working on this!
You want to use clang/Analysis/Analyses/ExprMutationAnalyzer.h.
See also: D51870

Thank you for your suggestion. I was not aware of this function. Now I use it and it seems to work perfectly. Sorry, neither was aware of your pending patch for the same functionality.

[lebedev.ri]

Thanks.
Are there any tests missing for volatile, atomics?
I'm not really current on clang-tidy state of affairs, so i'm gonna leave most of the review for others..

clang-tidy/bugprone/InfiniteLoopCheck.cpp

21 ↗

(On Diff #210070)

What about function calls marked noreturn?

[baloghadamsoftware]

Tests for volatile, atomics and noreturn functions added. Check fixed to make these tests pass.

[gribozavr]

clang-tidy/bugprone/InfiniteLoopCheck.cpp

25 ↗

(On Diff #210287)

St => S

"S" is a common abbreviation in the Clang codebase, "St" isn't.

(everywhere in the patch)

49 ↗

(On Diff #210287)

Please add documentation comments.

92 ↗

(On Diff #210287)

Please separate the logic that finds variables from the rest of the logic.

Finding variables has to be recursive, the rest does not have to be.

160 ↗

(On Diff #210287)

hasDescendant will recurse into other functions defined in the loop body, for example into lambdas.

for (...) {
  auto x = []() { throw 0; }
}

You can add the forFunction matcher to the loop ending statement matcher, and then use equalsNode to confirm that the loop ending statement is in the same function as the for loop.

Please also add tests for this case.

181 ↗

(On Diff #210287)

I'd suggest to attach the diagnostic to the loop -- the problem is with the loop, not with the first reference to the variable.

182 ↗

(On Diff #210287)

ClangTidy messages are sentence fragments that start with a lowercase letter.

It would be also helpful to state the problem explicitly.

"this loop is infinite; none of its condition variables are updated in the loop body"

docs/clang-tidy/checks/bugprone-infinite-loop.rst

6 ↗

(On Diff #210287)

s/checks for/finds/ (everywhere in the patch)

9 ↗

(On Diff #210287)

"Finding infinite loops is well-known to be impossible (halting problem)."

10 ↗

(On Diff #210287)

"However, it is possible to detect some obvious infinite loops, for example, if the loop condition is not changed."

16 ↗

(On Diff #210287)

"It is a local variable" (local variables can only be declared in functions)

18 ↗

(On Diff #210287)

I don't quite understand what you mean by "it is no member expression". Also, users likely won't understand the term "member expression".

23 ↗

(On Diff #210287)

s/considered as infinite/considered infinite/

24 ↗

(On Diff #210287)

I don't think we can say the "mistakenly" part. Explaining checker's behavior like that suggests that the checker detects the user's intent, which it does not. For example, it could also be the case that the user wanted to increment both i and j in the loop body.

All we can say is the loop is infinite because in the loop condition "i < 10" all variables (i) never change.

test/clang-tidy/bugprone-infinite-loop.cpp

43 ↗

(On Diff #210287)

Please add a period at the end of the comment.

Please also put comments on separate lines to avoid awkward wrapping like in tests below (such complex wrapping also discourages people from writing more detailed comments.)

59 ↗

(On Diff #210287)

"unknown_function"?

108 ↗

(On Diff #210287)

Please also add tests for lambdas capturing the loop variable by reference.

156 ↗

(On Diff #210287)

Is all escaping that syntactically follows the loop actually irrelevant? For example:

int i = 0;
int j = 0;
int *p = &j;
for (int k = 0; k < 5; k++) {
  *p = 100;
  if (k != 0) {
    // This loop would be reported as infinite.
    while (i < 10) {
    }
  }
  p = &i;
}

225 ↗

(On Diff #210287)

Why?

Intentional infinite loops *that perform side-effects in their body* are quite common -- for example, network servers, command-line interpreters etc.

Also, if the loop body calls an arbitrary function, we don't know if it will throw, or exit(), or kill the current thread or whatnot.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

Thank you for the very thorough review. I updated my patch according to your comments and tried to answer your concerns.

test/clang-tidy/bugprone-infinite-loop.cpp

156 ↗

(On Diff #210287)

You are right, but how frequent are such cases? I found no false positives at all when checking some ope-source projects. Should we spend resources to detect escaping in a nesting loop? I could not find a cheap way yet. I suppose this can only be done when nesting two loops. (I am sure we can ignore the cases where the outer loop is implemented using a goto.

225 ↗

(On Diff #210287)

We already handle loop exit statements including calls to [[noreturn]] functions. Is that not enough?

[gribozavr]

docs/clang-tidy/checks/bugprone-infinite-loop.rst

12 ↗

(On Diff #211933)

s/as//

test/clang-tidy/bugprone-infinite-loop.cpp

156 ↗

(On Diff #210287)

I don't know, however, this is one of the few sources of false positives for this check. This check generally can't detect all infinite loops, it is only trying to detect obvious ones. Therefore, I don't think it is exchange a bit more precision for false positives.

My best advice is to drop the heuristic about variable escaping after the loop. Any escaping => silence the warning.

If you want to handle this case correctly, you have to use the CFG.

225 ↗

(On Diff #210287)

User-defined functions are not always annotated with `[[noreturn]], and sometimes can't be annotated, for example, because they call exit()` conditionally:

while (true) {
  std::string command = readCommand();
  executeCommand(command);
}

void executeCommand(const std::string &command) {
  if (command == "exit") {
    exit();
  }
  ...
}

[baloghadamsoftware]

Updated according to the comments.

[gribozavr]

Thanks for following up!

clang-tidy/bugprone/InfiniteLoopCheck.cpp

53 ↗

(On Diff #218876)

Please delete "\brief" (everywhere in the patch) -- it is the default for the first sentence.

Also s/pointer of reference/pointer or reference/

docs/clang-tidy/checks/bugprone-infinite-loop.rst

18 ↗

(On Diff #218876)

Please add a period at the end.

test/clang-tidy/bugprone-infinite-loop.cpp

152 ↗

(On Diff #211933)

I'd prefer you to add these tests back and add a short comment that this code triggers false negatives that are difficult to solve without CFG-based analysis.

[baloghadamsoftware]

Updated according to the comment.

[gribozavr]

Thanks! Please let me know if you need me to commit the patch for you.

[RKSimon]

@baloghadamsoftware I'm sorry but I've reverted this at as rL372704 it was causing buildbot failures in cmake: http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/18147

[baloghadamsoftware]

In D64736#1680309, @RKSimon wrote:

@baloghadamsoftware I'm sorry but I've reverted this at as rL372704 it was causing buildbot failures in cmake: http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/18147

Oops! Sorry! I forgot svn add. However we do not get e-mails about buildbot failures for a couple of weeks. I will retry now.

clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp

 #include "DanglingHandleCheck.h"
 #include "DynamicStaticInitializersCheck.h"
 #include "ExceptionEscapeCheck.h"
 #include "FoldInitTypeCheck.h"
 #include "ForwardDeclarationNamespaceCheck.h"
 #include "ForwardingReferenceOverloadCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundingsCheck.h"
-#include "InfiniteLoopCheck.h"
 #include "IntegerDivisionCheck.h"
 #include "LambdaFunctionNameCheck.h"
 #include "MacroParenthesesCheck.h"
 #include "MacroRepeatedSideEffectsCheck.h"
 #include "MisplacedOperatorInStrlenInAllocCheck.h"
 #include "MisplacedWideningCastCheck.h"
 #include "MoveForwardingReferenceCheck.h"
 #include "MultipleStatementMacroCheck.h"
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ForwardDeclarationNamespaceCheck>(
         "bugprone-forward-declaration-namespace");
     CheckFactories.registerCheck<ForwardingReferenceOverloadCheck>(
         "bugprone-forwarding-reference-overload");
     CheckFactories.registerCheck<InaccurateEraseCheck>(
         "bugprone-inaccurate-erase");
     CheckFactories.registerCheck<IncorrectRoundingsCheck>(
         "bugprone-incorrect-roundings");
-    CheckFactories.registerCheck<InfiniteLoopCheck>(
-        "bugprone-infinite-loop");
     CheckFactories.registerCheck<IntegerDivisionCheck>(
         "bugprone-integer-division");
     CheckFactories.registerCheck<LambdaFunctionNameCheck>(
         "bugprone-lambda-function-name");
     CheckFactories.registerCheck<MacroParenthesesCheck>(
         "bugprone-macro-parentheses");
     CheckFactories.registerCheck<MacroRepeatedSideEffectsCheck>(
         "bugprone-macro-repeated-side-effects");

clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt

add_clang_library(clangTidyBugproneModule
   DanglingHandleCheck.cpp
   DynamicStaticInitializersCheck.cpp
   ExceptionEscapeCheck.cpp
   FoldInitTypeCheck.cpp
   ForwardDeclarationNamespaceCheck.cpp
   ForwardingReferenceOverloadCheck.cpp
   InaccurateEraseCheck.cpp
   IncorrectRoundingsCheck.cpp
-  InfiniteLoopCheck.cpp
   IntegerDivisionCheck.cpp
   LambdaFunctionNameCheck.cpp
   MacroParenthesesCheck.cpp
   MacroRepeatedSideEffectsCheck.cpp
   MisplacedOperatorInStrlenInAllocCheck.cpp
   MisplacedWideningCastCheck.cpp
   MoveForwardingReferenceCheck.cpp
   MultipleStatementMacroCheck.cpp

clang-tools-extra/docs/ReleaseNotes.rst

 The improvements are...
 
 Improvements to clang-tidy
 --------------------------
 
 - New :doc:`bugprone-dynamic-static-initializers
   <clang-tidy/checks/bugprone-dynamic-static-initializers>` check.
 
-- New OpenMP module.
-
-  For checks specific to `OpenMP <https://www.openmp.org/>`_ API.
-
-- New :doc:`abseil-duration-addition
-  <clang-tidy/checks/abseil-duration-addition>` check.
-
-  Checks for cases where addition should be performed in the ``absl::Time``
-  domain.
-
-- New :doc:`abseil-duration-conversion-cast
-  <clang-tidy/checks/abseil-duration-conversion-cast>` check.
-
-  Checks for casts of ``absl::Duration`` conversion functions, and recommends
-  the right conversion function instead.
-
-- New :doc:`abseil-duration-unnecessary-conversion
-  <clang-tidy/checks/abseil-duration-unnecessary-conversion>` check.
-
-  Finds and fixes cases where ``absl::Duration`` values are being converted to
-  numeric types and back again.
-
-- New :doc:`abseil-time-comparison
-  <clang-tidy/checks/abseil-time-comparison>` check.
-
-  Prefer comparisons in the ``absl::Time`` domain instead of the integer
-  domain.
-
-- New :doc:`abseil-time-subtraction
-  <clang-tidy/checks/abseil-time-subtraction>` check.
-
-  Finds and fixes ``absl::Time`` subtraction expressions to do subtraction
-  in the Time domain instead of the numeric domain.
-
-- New :doc:`android-cloexec-pipe
-  <clang-tidy/checks/android-cloexec-pipe>` check.
-
-  This check detects usage of ``pipe()``.
-
-- New :doc:`android-cloexec-pipe2
-  <clang-tidy/checks/android-cloexec-pipe2>` check.
-
-  This checks ensures that ``pipe2()`` is called with the O_CLOEXEC flag.
-
-- New :doc:`bugprone-infinite-loop
-  <clang-tidy/checks/bugprone-infinite-loop>` check.
-
-  Finds obvious infinite loops (loops where the condition variable is not
-  changed at all).
-
-- New :doc:`bugprone-unhandled-self-assignment
-  <clang-tidy/checks/bugprone-unhandled-self-assignment>` check.
-
-  Finds user-defined copy assignment operators which do not protect the code
-  against self-assignment either by checking self-assignment explicitly or
-  using the copy-and-swap or the copy-and-move method.
-
-- New :doc:`bugprone-branch-clone
-  <clang-tidy/checks/bugprone-branch-clone>` check.
-
-  Checks for repeated branches in ``if/else if/else`` chains, consecutive
-  repeated branches in ``switch`` statements and indentical true and false
-  branches in conditional operators.
-
-- New :doc:`bugprone-posix-return
-  <clang-tidy/checks/bugprone-posix-return>` check.
-
-  Checks if any calls to POSIX functions (except ``posix_openpt``) expect negative
-  return values.
-
-- New :doc:`fuchsia-default-arguments-calls
-  <clang-tidy/checks/fuchsia-default-arguments-calls>` check.
-
-  Warns if a function or method is called with default arguments.
-  This was previously done by `fuchsia-default-arguments check`, which has been
-  removed.
-
-- New :doc:`fuchsia-default-arguments-calls
-  <clang-tidy/checks/fuchsia-default-arguments-calls>` check.
-
   Finds instances where variables with static storage are initialized
   dynamically in header files.
 
 - New :doc:`linuxkernel-must-use-errs
   <clang-tidy/checks/linuxkernel-must-use-errs>` check.
 
   Checks Linux kernel code to see if it uses the results from the functions in
   ``linux/err.h``.
- New :doc:`objc-missing-hash
   appropriately implementing ``-hash``.
 
 - Improved :doc:`bugprone-posix-return
   <clang-tidy/checks/bugprone-posix-return>` check.
 
   Now also checks if any calls to ``pthread_*`` functions expect negative return
   values.
 
-- New :doc:`bugprone-infinite-loop <clang-tidy/checks/bugprone-infinite-loop>`
-  check to detect obvious infinite loops (loops where the condition variable is
-  not changed at all).
-
 Improvements to include-fixer
 -----------------------------
 
 The improvements are...
 
 Improvements to clang-include-fixer
 -----------------------------------
 

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. toctree::
    bugprone-dangling-handle
    bugprone-dynamic-static-initializers
    bugprone-exception-escape
    bugprone-fold-init-type
    bugprone-forward-declaration-namespace
    bugprone-forwarding-reference-overload
    bugprone-inaccurate-erase
    bugprone-incorrect-roundings
-   bugprone-infinite-loop
    bugprone-integer-division
    bugprone-lambda-function-name
    bugprone-macro-parentheses
    bugprone-macro-repeated-side-effects
    bugprone-misplaced-operator-in-strlen-in-alloc
    bugprone-misplaced-widening-cast
    bugprone-move-forwarding-reference
    bugprone-multiple-statement-macro