[clang-tidy] Fixing a bug raising false alarms on static local variables in the Infinite Loop Checker

[ziqingluo-90]

Summary

The Infinite Loop Checker could report a false positive on the example below:

void f() {
  static int i = 0;
  i++;
  while (i < 10)
     f();
}

This patch adds checking for recursive calls in the Infinite Loop Checker when loop condition involves static local variables.

[Eugene.Zelenko]

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

159

auto could be used, because type is spelled in same statement.

166

Ditto.

200

Ditto.

201

Ditto.

[gribozavr2]

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

159

Please clang-format before submitting (it looks like this block is indented 4 instead of 2).

184–185

188–191

Canonical => Can is the usual abbreviation, if you want to use one (e.g., see CanQualType)

198–199

210

Cond is not the loop itself.

[LegalizeAdulthood]

Clang-Tidy tests and docs have moved to module subdirectories.

Please rebase this onto main:HEAD and:

• fold your changes into the appropriate subdirs, stripping the module prefix from new files.
• make the target check-clang-extra to validate your tests
• make the target docs-clang-tools-html to validate any docs changes

[ziqingluo-90]

rebased with the latest main:HEAD where clang-tidy file structure has changed

[ziqingluo-90]

Addressing Dmitri's comments.

[gribozavr2]

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

184–185

It seems like you missed this one.

[NoQ]

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

34

Ok so this whole checker does this procedure involving ExprMutationAnalyzer trying to figure out if the variable can be changed from within the loop. I wonder if our problem of whether the static variable can be changed within the loop is a sub-problem of this problem and therefore could have a general solution inside ExprMutationAnalyzer. If so, other clang-tidy checks that use ExprMutationAnalyzer could immediately benefit from such solution. WDYT?

[LegalizeAdulthood]

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

190

Personally I'm not a fan of using bitwise operators with booleans. It involves implicit casts of bool to int and int to bool and doesn't use the usual short-circuiting logic of || and &&. It also means this code won't be analyzed by clang-tidy as "performing operations on booleans" for things like readability-simplify-boolean-expr.

[ziqingluo-90]

addressing more comments

[ziqingluo-90]

trying to be consistent in that auto is used wherever possible

[Eugene.Zelenko]

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

160

Please don't use auto when type is not spelled explicitly or iterator.

187

Ditto.

[ziqingluo-90]

I missed the part of coding standard about the usage of auto. Now change to conform to it.

[ziqingluo-90]

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

34

I think this is a good point. I can do it after this patch.

[ziqingluo-90]

Hi @LegalizeAdulthood, @NoQ, @gribozavr2, @Eugene.Zelenko,

Is there any further issue I should address for this patch?

[NoQ]

Looks great, thanks!

Yes, I think refactoring can be done in a follow-up patch.

[ziqingluo-90]

In D128401#3656559, @NoQ wrote:

Looks great, thanks!

Yes, I think refactoring can be done in a follow-up patch.

Thank you, @NoQ!

Let me politely ping the rest of the commenters: @LegalizeAdulthood, @gribozavr2, @Eugene.Zelenko. Is this patch looking good to you?

[NoQ]

I think let's commit. @ziqingluo-90 addressed all existing concerns and promises follow-up patches where he'll have a chance to address future concerns as well.

[njames93]

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

166

194

This will always be false as if it's true, the loop would return.

[ziqingluo-90]

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

194

Thanks for pointing this out. I will make the change before commit!

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

 //===--- InfiniteLoopCheck.cpp - clang-tidy -------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InfiniteLoopCheck.h"
 #include "../utils/Aliasing.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
+#include "clang/Analysis/CallGraph.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SmallVector.h"
 
 using namespace clang::ast_matchers;
 using clang::tidy::utils::hasPtrOrReferenceInFunc;
 
 namespace clang {
 namespace tidy {
 namespace bugprone {
 
 static internal::Matcher<Stmt>
 loopEndingStmt(internal::Matcher<Stmt> Internal) {
   // FIXME: Cover noreturn ObjC methods (and blocks?).
   return stmt(anyOf(
       mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
       callExpr(Internal, callee(functionDecl(isNoReturn())))));
 }
 
 /// Return whether `Var` was changed in `LoopStmt`.
 static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
                       ASTContext *Context) {
   if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
     return (ForLoop->getInc() &&
             ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
                 .isMutated(Var)) ||
            (ForLoop->getBody() &&
             ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
                 .isMutated(Var)) ||
if (Cond.isValueDependent()) {
     return false;
   }
   bool Result = false;
   if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
     return Result == ExpectedValue;
   return false;
 }
 
+/// populates the set `Callees` with all function (and objc method) declarations
+/// called in `StmtNode` if all visited call sites have resolved call targets.
+///
+/// \return true iff all `CallExprs` visited have callees; false otherwise
+///         indicating there is an unresolved indirect call.
+static bool populateCallees(const Stmt *StmtNode,
+                            llvm::SmallSet<const Decl *, 16> &Callees) {
+  if (const auto *Call = dyn_cast<CallExpr>(StmtNode)) {
+    const auto *Callee = Call->getDirectCallee();
+
+    if (!Callee)
+      return false; // unresolved call
+    Callees.insert(Callee->getCanonicalDecl());
+  }
+  if (const auto *Call = dyn_cast<ObjCMessageExpr>(StmtNode)) {
+    const auto *Callee = Call->getMethodDecl();
+
+    if (!Callee)
+      return false; // unresolved call
+    Callees.insert(Callee->getCanonicalDecl());
+  }
+  for (const auto *Child : StmtNode->children())
+    if (Child && !populateCallees(Child, Callees))
+      return false;
+  return true;
+}
+
+/// returns true iff `SCC` contains `Func` and its' function set overlaps with
+/// `Callees`
+static bool overlap(ArrayRef<CallGraphNode *> SCC,
+                    const llvm::SmallSet<const Decl *, 16> &Callees,
+                    const Decl *Func) {
+  bool ContainsFunc = false, Overlap = false;
+
+  for (const auto *GNode : SCC) {
+    const auto *CanDecl = GNode->getDecl()->getCanonicalDecl();
+
+    ContainsFunc = ContainsFunc || (CanDecl == Func);
+    Overlap = Overlap || Callees.contains(CanDecl);
+    if (ContainsFunc && Overlap)
+      return true;
+  }
+  return ContainsFunc && Overlap;
+}
+
+/// returns true iff `Cond` involves at least one static local variable.
+static bool hasStaticLocalVariable(const Stmt *Cond) {
+  if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond))
+    if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()))
+      if (VD->isStaticLocal())
+        return true;
+  for (const auto *Child : Cond->children())
+    if (Child && hasStaticLocalVariable(Child))
+      return true;
+  return false;
+}
+
+/// Tests if the loop condition `Cond` involves static local variables and
+/// the enclosing function `Func` is recursive.
+///
+///  \code
+///    void f() {
+///       static int i = 10;
+///       i--;
+///       while (i >= 0) f();
+///    }
+///  \endcode
+///  The example above is NOT an infinite loop.
+static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond,
+                                                    const Stmt *LoopStmt,
+                                                    const Decl *Func,
+                                                    const ASTContext *Ctx) {
+  if (!hasStaticLocalVariable(Cond))
+    return false;
+
+  llvm::SmallSet<const Decl *, 16> CalleesInLoop;
+
+  if (!populateCallees(LoopStmt, CalleesInLoop)) {
+    // If there are unresolved indirect calls, we assume there could
+    // be recursion so to avoid false alarm.
+    return true;
+  }
+  if (CalleesInLoop.empty())
+    return false;
+
+  TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl();
+  CallGraph CG;
+
+  CG.addToCallGraph(TUDecl);
+  // For each `SCC` containing `Func`, if functions in the `SCC`
+  // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`.
+  for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
+                                       SCCE = llvm::scc_end(&CG);
+       SCCI != SCCE; ++SCCI) {
+    if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
+      continue;
+    // `SCC`s are mutually disjoint, so there will be no redundancy in
+    // comparing `SCC` with the callee set one by one.
+    if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl()))
+      return true;
+  }
+  return false;
+}
+
 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
   const auto LoopCondition = allOf(
       hasCondition(
           expr(forCallable(decl().bind("func"))).bind("condition")),
       unless(hasBody(hasDescendant(
           loopEndingStmt(forCallable(equalsBoundNode("func")))))));
 
   Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
     }
   }
 
   if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *LoopStmt, *Result.Context))
     return;
 
   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
     return;
+  if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,
+                                              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"

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

void test_typeof_dowhile_infinite() {
   __typeof__({
     int i = 0;
     do {
 
     } while (i < 10);
     0;
   }) x;
 }
+
+void test_local_static_recursion() {
+  static int i = 10;
+  int j = 0;
+
+  i--;
+  while (i >= 0)
+    test_local_static_recursion(); // no warning, recursively decrement i
+  for (; i >= 0;)
+    test_local_static_recursion(); // no warning, recursively decrement i
+  for (; i + j >= 0;)
+    test_local_static_recursion(); // no warning, recursively decrement i
+  for (; i >= 0; i--)
+    ; // no warning, i decrements
+  while (j >= 0)
+    // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this loop is infinite; none of its condition variables (j) are updated in the loop body [bugprone-infinite-loop]
+    test_local_static_recursion();
+
+  int (*p)(int) = 0;
+
+  while (i >= 0)
+    // 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]
+    p = 0;
+  while (i >= 0)
+    p(0); // we don't know what p points to so no warning
+}

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

 + (void)classMethod {
   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++;
   }
 }
+
++ (void)recursiveMethod {
+  static int i = 0;
+
+  i++;
+  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]
+    [I classMethod];
+  }
+
+  id x = [[I alloc] init];
+
+  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]
+    [x instanceMethod];
+  }
+  while (i < 10) {
+    // no warning, there is a recursive call that can mutate the static local variable
+    [I recursiveMethod];
+  }
+}
 @end
 
 void testArrayCount() {
   NSArray *arr = [[NSArray alloc] init];
   NSUInteger max_count = 10;
   while ([arr count] < max_count) {
     // No warning. Array count is updated on every iteration.
     [arr addObject: [[I alloc] init]];