This is an archive of the discontinued LLVM Phabricator instance.

[clang-tidy] Infinite loop checker
Needs RevisionPublic

Authored by szepet on Dec 6 2017, 5:49 PM.

Details

Summary

The check aims to find loops where none of the condition variables are updated in the body.
In this version it only works on integer types but the final aim is to make it work for objects as well. (via checking non-const method calls, etc)

Note: this kind of check is supported by clang warning as well (-Wfor-loop-analysis), however, it only works on for-loops and not investigate escape statements (modification via alias generates false positives e.g. escape_before1() test case).

Any suggestions on the check are welcome!

Diff Detail

Event Timeline

szepet created this revision.Dec 6 2017, 5:49 PM

Does it really belong to Clang-tidy or Clang Analyzer is better place because of path-ensitivity?

Please rebase from trunk.

General note: CLang-tidy use check in terminology, not checker.

docs/ReleaseNotes.rst
63

Just Finds instead of The checker aims to find. Please also align on 80 symbols per line. Same in documentation.

Eugene.Zelenko set the repository for this revision to rL LLVM.
Eugene.Zelenko added a project: Restricted Project.
Eugene.Zelenko added a subscriber: zaks.anna.
szepet edited the summary of this revision. (Show Details)Dec 6 2017, 6:40 PM
szepet updated this revision to Diff 125870.Dec 6 2017, 6:50 PM
szepet marked an inline comment as done.

Updated the wording in the docs.

szepet added a comment.Dec 6 2017, 7:06 PM

Hi Eugen!
Good question, probably should have detailed it in the description.
This matcher based solution would not gain much benefit from the symbolic execution provided information. (I mean, it would mean a much different type of check on the states.)
The main problems that the analyzer does not completely unroll the loops only the first steps and we always have information about the simulated path. However, detecting that some variables will surely not be modified requires a top level overview on the loop and the AST provides these informations. The one thing (that I can say right now) that can come handy is that we would able to detect more precisely the happened-before relation on the escape and the loop statements. Since the CFG can provide us fair enough information on this one, I do not think that this is enough reason to put this checker to the analyzer.

Other note: If somebody would came up with an approach which can benefit from the symbolic execution, these solutions could still live happily in the different tools eg. UseAfterMove (tidy) and MisusedMovedObjectChecker (analyzer).

Other note: If somebody would came up with an approach which can benefit from the symbolic execution, these solutions could still live happily in the different tools eg. UseAfterMove (tidy) and MisusedMovedObjectChecker (analyzer).

I'm more concerned with path sensitivity and reporting. From my point of view UseAfterMove also belongs to Analyzer realm.

Actually bugprone module may be better choice then misc.

docs/ReleaseNotes.rst
63

Please remove The check. See other checks release notes and documentation as style examples.

Please rebase from trunk, since I sorted Clang-tidy notes recently, so just prefer to avoid this task in future :-)

Eugene.Zelenko added inline comments.Dec 6 2017, 9:32 PM
clang-tidy/misc/InfiniteLoopCheck.cpp
94 ↗(On Diff #125870)

Missing static?

102 ↗(On Diff #125870)

May be return {}?

125 ↗(On Diff #125870)

const auto?

130 ↗(On Diff #125870)

const auto?

142 ↗(On Diff #125870)

const auto?

168 ↗(On Diff #125870)

const auto?

176 ↗(On Diff #125870)

const auto?

JVApen added a subscriber: JVApen.Dec 6 2017, 11:19 PM

How does this check deal with atomic members?

struct A {
std:: atomic<bool> a;

void f() const { while (a); }
};

martong added a subscriber: martong.Dec 7 2017, 5:23 AM
martong added inline comments.
clang-tidy/misc/InfiniteLoopCheck.cpp
105 ↗(On Diff #125870)

make_unique is a forwarding function, therefore there is no need to create an object and then move it. Instead you can simply forward the arguments to the constructor:
return llvm::make_unique<ExprSequence>(TheCFG.get(), &ASTCtx)

szepet updated this revision to Diff 125965.Dec 7 2017, 8:00 AM
szepet marked 9 inline comments as done.

Updates based on comments.

Eugene.Zelenko added inline comments.Dec 7 2017, 8:01 AM
docs/clang-tidy/checks/misc-infinite-loop.rst
6 ↗(On Diff #125965)

Please synchronize with release notes.

szepet added a comment.Dec 7 2017, 8:02 AM

How does this check deal with atomic members?
...

This patch only works on integer types. So, since the atomic is a non-supported type the check will skip that while loop.

xazax.hun edited edge metadata.Dec 7 2017, 8:08 AM

This does not support memberExprs as condition variables right now.

What happens if you have something like this:

struct X {
void f(int a) {
  while(a < i) {
    --i;
  } 
}
int i;
};

I think you could extend the test cases with some classes.

clang-tidy/misc/InfiniteLoopCheck.cpp
28 ↗(On Diff #125870)

Do you need this to be a lambda? Can't you just use a local variable?

31 ↗(On Diff #125870)

Maybe this is not too important, but you might also want to check for blocks here.

48 ↗(On Diff #125870)

This can be greatly simplified once https://reviews.llvm.org/D38921 is accepted. Maybe you could use that as a dependent revision? It should be close to be accepted.

xazax.hun added inline comments.Dec 7 2017, 8:14 AM
clang-tidy/misc/InfiniteLoopCheck.cpp
121 ↗(On Diff #125965)

This could be pointer to const, right?

aaron.ballman edited edge metadata.
aaron.ballman added a subscriber: dcoughlin.

I share the concerns that @Eugene.Zelenko brought up regarding this not being in the analyzer. This is a path sensitive problem that I'm not certain clang-tidy is the best home for. You cover many of the simple cases, but fail to cover cases like nested loops, unsigned integer wrapping, non-integral types, function calls, globals, etc. I'm not certain this check will generalize over time as part of clang-tidy in the way it would in the analyzer. I'd be curious to hear what @alexfh and @dcoughlin think, though.

I think, while the analyzer is more suitable for certain kinds of checks that require deep analysis, it is still useful to have quicker syntactic checks that can easily identify problems that are the results of typos or incorrectly modified copy and pasted code. I think this check is in that category. Also, the original warning Peter mentioned does something similar but has some shortcomings.

The current implementation is not path sensitive. It uses flow sensitivity to check for escaping values.
If we would try to port this check to the static analyzer, the questions we would ask from the analyzer are universally quantified (e.g. for all path this variable does not escape and does not change). Unfortunately, it is not that easy with the current analyzer to answer such questions. The static analyzer is better with existential questions (e.g. there is a path such that the condition variables are not escaped and are unchanged in the loop). Using the latter formulation we might have a larger number of false positives because the analyzer sometimes hit infeasible paths. In the first approach, the infeasible paths are less of a problem (they might cause false negatives but not false positives), but we need to be careful with all the peculiarities of the analyzer because it does not guarantee to discover all possible paths.

Hopefully, Devin will correct me if I'm wrong :)

alexfh requested changes to this revision.Mar 14 2018, 8:36 AM

Please move this check to "bugprone-", since it seems to be an appropriate category for this check.

This revision now requires changes to proceed.Mar 14 2018, 8:36 AM
szepet updated this revision to Diff 141132.EditedApr 5 2018, 5:24 AM
szepet marked 3 inline comments as done.

Moved to bugprone category,
skipping memberExpr cases for now in order to avoid false positives,
other small changes based on review comments.

clang-tidy/misc/InfiniteLoopCheck.cpp
121 ↗(On Diff #125965)

Since the createSequence uses it as a parameter for buildCFG which expects a Stmt*, I believe this is fine. (Or I could const cast is away on the call)

alexfh requested changes to this revision.Apr 5 2018, 6:17 AM
alexfh added inline comments.
clang-tidy/bugprone/InfiniteLoopCheck.cpp
24–26

This doesn't have to be a function. It can be a local variable or can be inlined into the callsite.

33

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats).

106

Why not just llvm::make_unique<ExprSequence>(TheCFG.get(), &ASTCtx)?

It also may be that you somehow lost a bunch of fixes, since this comment has already been addressed at some point: https://reviews.llvm.org/D40937?id=125870#inline-357357

187

Clang diagnostics (and clang-tidy warnings) are not complete sentences and shouldn't start with a capital letter.

This revision now requires changes to proceed.Apr 5 2018, 6:17 AM
szepet updated this revision to Diff 141322.Apr 6 2018, 5:32 AM
szepet marked 4 inline comments as done.

Addressed comments and readded the lost fixes.

alexfh requested changes to this revision.Apr 9 2018, 10:00 AM
alexfh added inline comments.
clang-tidy/bugprone/InfiniteLoopCheck.cpp
95–100

A little suggestion:

if (std::unique_ptr<CFG> TheCFG = ...)
  return llvm::make_unique<ExprSequence>(TheCFG.get(), &ASTCtx);
return {};
129

The main concern I have now is that the check may end up creating the CFG multiple times for the same function, which may be rather expensive in certain cases (consider a large function consisting of loops that trigger the matcher). It's hard to predict how common is this situation in real code. Do you see how this could be restructured to avoid unnecessary work?

180

I suggest a more straightforward version:

​ std::string CondVarNames;

for (const auto &CVM : CondVarMatches) {
  if (!CondVarNames.empty())
    CondVarNames.append(", ");
  CondVarNames.append(CVM.getNodeAs<VarDecl>("condvar")->getNameAsString());

​ }

This revision now requires changes to proceed.Apr 9 2018, 10:00 AM
szepet updated this revision to Diff 143949.Apr 25 2018, 9:34 AM
szepet marked 2 inline comments as done.

Changes made based on comments.
The CFG recreating problem is handled the following (only for this check):
Always store the last visited function and its CFG* (in form of the Sequence*) and check if we are visiting it again. If so, then the check reuses the previous one, if not, then replaces them. As far as I know the AST traverse done by the tidy fits this model (at least for this check, since it not uses narrowing matchers to other functions).
Sure, it would be better to find a general solution to this problem, and make the CFG reusable by every check which needs it, but I would left it for a follow-up (and a change like this probably would worth an own patch/review anyway).

alexfh requested changes to this revision.May 3 2018, 9:06 AM
alexfh added inline comments.
clang-tidy/bugprone/InfiniteLoopCheck.h
38

Why bool? The return value is not used anywhere.

docs/ReleaseNotes.rst
68

There should be a trailing period in each of these New ... check items. I've updated the script in r331460 and the existing release notes in r331461. Please rebase.

This revision now requires changes to proceed.May 3 2018, 9:06 AM
szepet updated this revision to Diff 145160.May 4 2018, 1:12 AM
szepet marked 2 inline comments as done.

Changes based on comments.

alexfh requested changes to this revision.May 4 2018, 10:04 AM

Could you run the check on llvm sources and post a summary of results here?

A few more inline comments.

clang-tidy/bugprone/InfiniteLoopCheck.cpp
102

What does nullptr mean here? Please add an argument comment (/*ArgumentName=*/nullptr, ...).

109–112

nit: Let's put these variable definitions into the corresponding if conditions to limit their scope. I'd also move the ifs to the start of the function.

122–123

Instead I'd check that FunctionBody is not nullptr.

148

nit: const auto *

150

Any reason to store the result of the matching instead of returning early? Same below. Please also move the definition of the Match variable to where it's actually needed first time.

175

Please use the specific type instead of auto.

clang-tidy/bugprone/InfiniteLoopCheck.h
37

You seem to have forgotten to update the header.

This revision now requires changes to proceed.May 4 2018, 10:04 AM