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

[baloghadamsoftware]

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.

[Eugene.Zelenko]

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

179

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

194

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

[njames93]

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

132

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

153

likewise

197

elide braces

[gribozavr2]

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

186

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

202

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]

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

186

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.

202

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.

[baloghadamsoftware]

Updated according to the comments.

[gribozavr2]

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

186

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

69

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--;
}

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

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

186

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]

Minor fix.

[gribozavr2]

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

[njames93]

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); }
}

[gribozavr2]

In D73270#1838883, @njames93 wrote:

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!

[njames93]

In D73270#1838956, @gribozavr2 wrote:

In D73270#1838883, @njames93 wrote:

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

[baloghadamsoftware]

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?

[gribozavr2]

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

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

static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func,
 
   for (const Stmt *Child : Cond->children()) {
     if (!Child)
       continue;
 
     if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
       return true;
   }
+
   return false;
 }
 
 /// Return the variable names in `Cond`.
 static std::string getCondVarNames(const Stmt *Cond) {
   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
       return Var->getName();
   }
 
   std::string Result;
   for (const Stmt *Child : Cond->children()) {
     if (!Child)
       continue;
 
     std::string NewNames = getCondVarNames(Child);
     if (!Result.empty() && !NewNames.empty())
       Result += ", ";
     Result += NewNames;
   }
+
   return Result;
 }
 
 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
   const auto LoopCondition = allOf(
       hasCondition(
           expr(forFunction(functionDecl().bind("func"))).bind("condition")),
       unless(hasBody(hasDescendant(
           loopEndingStmt(forFunction(equalsBoundNode("func")))))));
 
   Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
                                 forStmt(LoopCondition)))
                          .bind("loop-stmt"),
                      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");
 
   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
     return;
 
+  if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
+    if (const auto *LoopVarDecl = While->getConditionVariable()) {
+      if (const Expr *Init = LoopVarDecl->getInit()) {
+        if (isAtLeastOneCondVarChanged(Func, LoopStmt, Init,
+                                       Result.Context))
+          return;
+      }
+    }
+  }
+
   std::string CondVarNames = getCondVarNames(Cond);
+
   if (CondVarNames.empty())
     return;
 
+  if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
+    if (const auto *LoopVarDecl = While->getConditionVariable()) {
+      if (const Expr *Init = LoopVarDecl->getInit()) {
+        std::string AdditionalVarNames = getCondVarNames(Init);
+        if (!AdditionalVarNames.empty()) {
+          CondVarNames += ", " + AdditionalVarNames;
+        }
+      }
+    }
+  }
+
   diag(LoopStmt->getBeginLoc(),
        "this loop is infinite; none of its condition variables (%0)"
        " are updated in the loop body")
       << CondVarNames;
 }
 
 } // namespace bugprone
 } // namespace tidy
 } // namespace clang

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

 // RUN: %check_clang_tidy %s bugprone-infinite-loop %t -- -- -fexceptions
 
 void simple_infinite_loop1() {
   int i = 0;
   int j = 0;
   while (i < 10) {
     // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop]
     j++;
   }
 
+  while (int k = 10) {
+    // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (k) are updated in the loop body [bugprone-infinite-loop]
+    j--;
+  }
+
   do {
   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop]
     j++;
   } while (i < 10);
 
   for (i = 0; i < 10; ++j) {
     // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i) are updated in the loop body [bugprone-infinite-loop]
   }
 }
 
 void simple_infinite_loop2() {
   int i = 0;
   int j = 0;
   int Limit = 10;
   while (i < Limit) {
     // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
+    j--;
+  }
+
+  while (int k = Limit) {
+    // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (k, Limit) are updated in the loop body [bugprone-infinite-loop]
     j++;
   }
 
   do {
   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
     j++;
   } while (i < Limit);
 
   for (i = 0; i < Limit; ++j) {
     // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (i, Limit) are updated in the loop body [bugprone-infinite-loop]
   }
 }
 
 void simple_not_infinite1() {
   int i = 0;
   int Limit = 100;
   while (i < Limit) {
     // Not an error since 'Limit' is updated.
     Limit--;
   }
+
+  while (int k = Limit) {
+    // Not an error since 'Limit' is updated.
+    Limit--;
+  }
+
   do {
     Limit--;
   } while (i < Limit);
 
   for (i = 0; i < Limit; Limit--) {
   }
 }
 
 void simple_not_infinite2() {
   for (int i = 10; i-- > 0;) {
     // Not an error, since loop variable is modified in its condition part.
   }
 }
 
 int unknown_function();