This is an archive of the discontinued LLVM Phabricator instance.

[clang-tidy] Fix false positive in bugprone-infinite-loop
ClosedPublic

Authored by baloghadamsoftware on Jan 23 2020, 6:09 AM.

Details

Summary

The checker bugprone-infinite-loop does not track changes of variables in the initialization expression of a variable declared inside the condition of the while statement. This leads to false positives, similarly to the one in the bug report 44618. This patch fixes this issue by enabling tracking of the variables of this expression as well.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptJan 23 2020, 6:09 AM
Eugene.Zelenko added inline comments.Jan 23 2020, 6:44 AM
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
187

Please don't use auto unless type is explicitly stated or iterator.

191

Please don't use auto unless type is explicitly stated or iterator.

Eugene.Zelenko retitled this revision from [clan-tidy] Fix false positive in bugprone-infinite-loop to [clang-tidy] Fix false positive in bugprone-infinite-loop.Jan 23 2020, 6:45 AM
njames93 added inline comments.
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
132

Don't change formatting of code this patch doesn't need to touch

152

likewise

194

elide braces

gribozavr2 added inline comments.Jan 23 2020, 9:24 AM
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
194

I think this logic should go into isChanged(), similarly to how it handles for loops today.

199

I think this logic should go into getCondVarNames. It even seems like the existing logic should work without changes, it is walking all children of a provided statement.

baloghadamsoftware marked 2 inline comments as done.Jan 23 2020, 9:42 AM
baloghadamsoftware added inline comments.
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
194

isChanged() looks for changes of a specific variable. This part collects the variables to check. The fundamental problem with the current logic is that it only look for the condition variables in the Condition of the loop statement, but it does not contain the initial value of the variable declared inside the condition part of the while statement. Thus in case of while (int m = n) { n--; } the condition is only the expression m. Thus we simply cannot grab n by only checking the condition thus consider this loop as infinite because m is not changed. Taking the whole loop statement instead of the condition is also wrong because then the following obviously infinite loop is not detected: while (n) { m--; } because m is also grabbed from the body which must not. We must explicitly check the variable of the initialization expression of variable declared in the condition of while loops because it is a separate child of the statement.

199

The same is valid here that I wrote above. getCondVarNames() did not grab the variable names in the initialization expression of the variable declared inside the condition part of the while loop because they are no children of the Condition part in Clang. You can see this in the bugzilla bug report as well. There the variable pattern did not appear in the diagnostic message.

Updated according to the comments.

baloghadamsoftware marked 5 inline comments as done.Jan 23 2020, 9:56 AM
gribozavr2 added inline comments.Jan 23 2020, 11:11 AM
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
194

Yes, I see what you mean -- and my suggestion was incorrect.

However, right now the variable declared in the while loop is being treated like something that carries over to the next loop iteration:

while (int k = Limit) { k--; } // no warning with this patch

This is because this while loop still has a condition that checks that k != 0, and we scan that in the isAtLeastOneCondVarChanged call on line 173.

I think a better fix would bind Cond to the initialization expression of the while loop variable. Like this:

void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
  const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
  const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
  const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");

  bool ShouldHaveConditionVariables = true;
  if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
    if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
      if (const Expr *Init = LoopVarDecl->getInit()) {
        ShouldHaveConditionVariables = false;
        Cond = Init;
      }
    }
  }
  Cond->dump();

  if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context)) {
    return;
  }

  std::string CondVarNames = getCondVarNames(Cond);
  if (ShouldHaveConditionVariables && CondVarNames.empty())
    return;

  if (CondVarNames.empty()) {
    diag(LoopStmt->getBeginLoc(),
         "this loop is infinite; it does not check any variables in the condition");
  } else {
    diag(LoopStmt->getBeginLoc(),
         "this loop is infinite; none of its condition variables (%0)"
         " are updated in the loop body")
        << CondVarNames;
  }
}

If you agree, please also add while (int k = Limit) { k--; } to the tests.

clang-tools-extra/test/clang-tidy/checkers/bugprone-infinite-loop.cpp
89

There seems to be no test coverage for the following case:

while (i--) { // no warning
  j--;
}

I'd appreciate if you could add that.

And also this one, relevant to the bug you're fixing:

while (int k = Limit--) { // no warning
  i--;
}

Updated according to the comments.

baloghadamsoftware marked 3 inline comments as done.Jan 24 2020, 7:31 AM
baloghadamsoftware added inline comments.
clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp
194

Oh, I forgot that the declared variable gets a new value at every iteration thus its changes are not relevant. Thank you, I fixed this now.

baloghadamsoftware updated this revision to Diff 240195.EditedJan 24 2020, 7:33 AM
baloghadamsoftware marked an inline comment as done.

Minor fix.

gribozavr2 accepted this revision.Jan 24 2020, 8:00 AM

LGTM! Please commit if you have commit access, or let me know if I should push it for you.

This revision is now accepted and ready to land.Jan 24 2020, 8:00 AM

May not be one for this patch, but how does this check handle volatile loop variables and cases where modification isn't visible in the context e.g.

extern void mutate(bool &);
volatile bool* LoopCond;

void foo() {
  for (bool Cond = true; Cond; mutate(Cond)) { wait(0); }
  for (*LoopCond = true; *LoopCond;) { wait(0); }
}

May not be one for this patch, but how does this check handle volatile loop variables and cases where modification isn't visible in the context e.g.

Should be OK, see "if (Var->getType().isVolatileQualified())" in the implementation. Feel free to submit another patch with more tests!

May not be one for this patch, but how does this check handle volatile loop variables and cases where modification isn't visible in the context e.g.

Should be OK, see "if (Var->getType().isVolatileQualified())" in the implementation. Feel free to submit another patch with more tests!

Ahh I see, it also handles calls which take the var as a reference or pointer, test cases would be good but doesn't need to be in here

This revision was automatically updated to reflect the committed changes.

Should I also commit it to the release 10.0 branch? This is a bugfix so it should be fixed in the release, I think. I added a dependency between this bug and the 10.0.0 release blockers. Is that enough?

Please talk to Hans Wennborg <hwennborg@google.com> about cherry-picking this change into the release. I think it is a safe change, if Hans needs that sort of review from someone.