Page MenuHomePhabricator

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

Authored by baloghadamsoftware on Jul 15 2019, 6:16 AM.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptJul 15 2019, 6:16 AM
lebedev.ri requested changes to this revision.Jul 15 2019, 6:30 AM

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

This revision now requires changes to proceed.Jul 15 2019, 6:30 AM
Eugene.Zelenko added inline comments.
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.

Updated according to the comments.

baloghadamsoftware marked 5 inline comments as done.Jul 16 2019, 5:29 AM

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.

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?

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

baloghadamsoftware marked an inline comment as done.Jul 17 2019, 4:20 AM
gribozavr added inline comments.Jul 19 2019, 9:55 AM
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 marked 3 inline comments as done.

Updated according to the comments.

baloghadamsoftware marked 15 inline comments as done.EditedJul 26 2019, 7:02 AM

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?

baloghadamsoftware edited the summary of this revision. (Show Details)Jul 26 2019, 7:04 AM
gribozavr added inline comments.Aug 6 2019, 5:13 AM
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();
  }
  ...
}

Updated according to the comments.

baloghadamsoftware marked 5 inline comments as done.Sep 5 2019, 3:05 AM

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.

Updated according to the comment.

baloghadamsoftware marked 3 inline comments as done.Sep 23 2019, 5:24 AM
gribozavr accepted this revision.Sep 23 2019, 5:32 AM

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

This revision was not accepted when it landed; it landed in state Needs Review.Sep 24 2019, 12:45 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptSep 24 2019, 12:45 AM
RKSimon reopened this revision.Sep 24 2019, 1:55 AM
RKSimon added a subscriber: 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

This revision was not accepted when it landed; it landed in state Needs Review.Sep 24 2019, 1:56 AM
This revision was automatically updated to reflect the committed changes.

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