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

   1 //===--- InfiniteLoopCheck.cpp - clang-tidy -------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "InfiniteLoopCheck.h"
  10 #include "../utils/Aliasing.h"
  11 #include "clang/AST/ASTContext.h"
  12 #include "clang/ASTMatchers/ASTMatchFinder.h"
  13 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
  14 #include "clang/Analysis/CallGraph.h"
  15 #include "llvm/ADT/SCCIterator.h"
  16 #include "llvm/ADT/SmallVector.h"
  17
  18 using namespace clang::ast_matchers;
  19 using clang::tidy::utils::hasPtrOrReferenceInFunc;
  20
  21 namespace clang {
  22 namespace ast_matchers {
  23 /// matches a Decl if it has a  "no return" attribute of any kind
  24 AST_MATCHER(Decl, declHasNoReturnAttr) {
  25   return Node.hasAttr<NoReturnAttr>() || Node.hasAttr<CXX11NoReturnAttr>() ||
  26          Node.hasAttr<C11NoReturnAttr>();
  27 }
  28
  29 /// matches a FunctionType if the type includes the GNU no return attribute
  30 AST_MATCHER(FunctionType, typeHasNoReturnAttr) {
  31   return Node.getNoReturnAttr();
  32 }
  33 } // namespace ast_matchers
  34 namespace tidy::bugprone {
  35
  36 static internal::Matcher<Stmt>
  37 loopEndingStmt(internal::Matcher<Stmt> Internal) {
  38   internal::Matcher<QualType> isNoReturnFunType =
  39       ignoringParens(functionType(typeHasNoReturnAttr()));
  40   internal::Matcher<Decl> isNoReturnDecl =
  41       anyOf(declHasNoReturnAttr(), functionDecl(hasType(isNoReturnFunType)),
  42             varDecl(hasType(blockPointerType(pointee(isNoReturnFunType)))));
  43
  44   return stmt(anyOf(
  45       mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
  46       callExpr(Internal,
  47                callee(mapAnyOf(functionDecl, /* block callee */ varDecl)
  48                           .with(isNoReturnDecl))),
  49       objcMessageExpr(Internal, callee(isNoReturnDecl))));
  50 }
  51
  52 /// Return whether `Var` was changed in `LoopStmt`.
  53 static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
  54                       ASTContext *Context) {
  55   if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
  56     return (ForLoop->getInc() &&
  57             ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
  58                 .isMutated(Var)) ||
  59            (ForLoop->getBody() &&
  60             ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
  61                 .isMutated(Var)) ||
  62            (ForLoop->getCond() &&
  63             ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
  64
  65   return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
  66 }
  67
  68 /// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.
  69 static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt,
  70                                        const Stmt *Cond, ASTContext *Context) {
  71   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
  72     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
  73       if (!Var->isLocalVarDeclOrParm())
  74         return true;
  75
  76       if (Var->getType().isVolatileQualified())
  77         return true;
  78
  79       if (!Var->getType().getTypePtr()->isIntegerType())
  80         return true;
  81
  82       return hasPtrOrReferenceInFunc(Func, Var) ||
  83              isChanged(LoopStmt, Var, Context);
  84       // FIXME: Track references.
  85     }
  86   } else if (isa<MemberExpr, CallExpr,
  87                  ObjCIvarRefExpr, ObjCPropertyRefExpr, ObjCMessageExpr>(Cond)) {
  88     // FIXME: Handle MemberExpr.
  89     return true;
  90   } else if (const auto *CE = dyn_cast<CastExpr>(Cond)) {
  91     QualType T = CE->getType();
  92     while (true) {
  93       if (T.isVolatileQualified())
  94         return true;
  95
  96       if (!T->isAnyPointerType() && !T->isReferenceType())
  97         break;
  98
  99       T = T->getPointeeType();
 100     }
 101   }
 102
 103   return false;
 104 }
 105
 106 /// Return whether at least one variable of `Cond` changed in `LoopStmt`.
 107 static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt,
 108                                        const Stmt *Cond, ASTContext *Context) {
 109   if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
 110     return true;
 111
 112   for (const Stmt *Child : Cond->children()) {
 113     if (!Child)
 114       continue;
 115
 116     if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
 117       return true;
 118   }
 119   return false;
 120 }
 121
 122 /// Return the variable names in `Cond`.
 123 static std::string getCondVarNames(const Stmt *Cond) {
 124   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
 125     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
 126       return std::string(Var->getName());
 127   }
 128
 129   std::string Result;
 130   for (const Stmt *Child : Cond->children()) {
 131     if (!Child)
 132       continue;
 133
 134     std::string NewNames = getCondVarNames(Child);
 135     if (!Result.empty() && !NewNames.empty())
 136       Result += ", ";
 137     Result += NewNames;
 138   }
 139   return Result;
 140 }
 141
 142 static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx,
 143                                bool ExpectedValue) {
 144   if (Cond.isValueDependent()) {
 145     if (const auto *BinOp = dyn_cast<BinaryOperator>(&Cond)) {
 146       // Conjunctions (disjunctions) can still be handled if at least one
 147       // conjunct (disjunct) is known to be false (true).
 148       if (!ExpectedValue && BinOp->getOpcode() == BO_LAnd)
 149         return isKnownToHaveValue(*BinOp->getLHS(), Ctx, false) ||
 150                isKnownToHaveValue(*BinOp->getRHS(), Ctx, false);
 151       if (ExpectedValue && BinOp->getOpcode() == BO_LOr)
 152         return isKnownToHaveValue(*BinOp->getLHS(), Ctx, true) ||
 153                isKnownToHaveValue(*BinOp->getRHS(), Ctx, true);
 154       if (BinOp->getOpcode() == BO_Comma)
 155         return isKnownToHaveValue(*BinOp->getRHS(), Ctx, ExpectedValue);
 156     } else if (const auto *UnOp = dyn_cast<UnaryOperator>(&Cond)) {
 157       if (UnOp->getOpcode() == UO_LNot)
 158         return isKnownToHaveValue(*UnOp->getSubExpr(), Ctx, !ExpectedValue);
 159     } else if (const auto *Paren = dyn_cast<ParenExpr>(&Cond))
 160       return isKnownToHaveValue(*Paren->getSubExpr(), Ctx, ExpectedValue);
 161     else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(&Cond))
 162       return isKnownToHaveValue(*ImplCast->getSubExpr(), Ctx, ExpectedValue);
 163     return false;
 164   }
 165   bool Result = false;
 166   if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
 167     return Result == ExpectedValue;
 168   return false;
 169 }
 170
 171 /// populates the set `Callees` with all function (and objc method) declarations
 172 /// called in `StmtNode` if all visited call sites have resolved call targets.
 173 ///
 174 /// \return true iff all `CallExprs` visited have callees; false otherwise
 175 ///         indicating there is an unresolved indirect call.
 176 static bool populateCallees(const Stmt *StmtNode,
 177                             llvm::SmallSet<const Decl *, 16> &Callees) {
 178   if (const auto *Call = dyn_cast<CallExpr>(StmtNode)) {
 179     const Decl *Callee = Call->getDirectCallee();
 180
 181     if (!Callee)
 182       return false; // unresolved call
 183     Callees.insert(Callee->getCanonicalDecl());
 184   }
 185   if (const auto *Call = dyn_cast<ObjCMessageExpr>(StmtNode)) {
 186     const Decl *Callee = Call->getMethodDecl();
 187
 188     if (!Callee)
 189       return false; // unresolved call
 190     Callees.insert(Callee->getCanonicalDecl());
 191   }
 192   for (const Stmt *Child : StmtNode->children())
 193     if (Child && !populateCallees(Child, Callees))
 194       return false;
 195   return true;
 196 }
 197
 198 /// returns true iff `SCC` contains `Func` and its' function set overlaps with
 199 /// `Callees`
 200 static bool overlap(ArrayRef<CallGraphNode *> SCC,
 201                     const llvm::SmallSet<const Decl *, 16> &Callees,
 202                     const Decl *Func) {
 203   bool ContainsFunc = false, Overlap = false;
 204
 205   for (const CallGraphNode *GNode : SCC) {
 206     const Decl *CanDecl = GNode->getDecl()->getCanonicalDecl();
 207
 208     ContainsFunc = ContainsFunc || (CanDecl == Func);
 209     Overlap = Overlap || Callees.contains(CanDecl);
 210     if (ContainsFunc && Overlap)
 211       return true;
 212   }
 213   return false;
 214 }
 215
 216 /// returns true iff `Cond` involves at least one static local variable.
 217 static bool hasStaticLocalVariable(const Stmt *Cond) {
 218   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond))
 219     if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()))
 220       if (VD->isStaticLocal())
 221         return true;
 222   for (const Stmt *Child : Cond->children())
 223     if (Child && hasStaticLocalVariable(Child))
 224       return true;
 225   return false;
 226 }
 227
 228 /// Tests if the loop condition `Cond` involves static local variables and
 229 /// the enclosing function `Func` is recursive.
 230 ///
 231 ///  \code
 232 ///    void f() {
 233 ///       static int i = 10;
 234 ///       i--;
 235 ///       while (i >= 0) f();
 236 ///    }
 237 ///  \endcode
 238 ///  The example above is NOT an infinite loop.
 239 static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond,
 240                                                     const Stmt *LoopStmt,
 241                                                     const Decl *Func,
 242                                                     const ASTContext *Ctx) {
 243   if (!hasStaticLocalVariable(Cond))
 244     return false;
 245
 246   llvm::SmallSet<const Decl *, 16> CalleesInLoop;
 247
 248   if (!populateCallees(LoopStmt, CalleesInLoop)) {
 249     // If there are unresolved indirect calls, we assume there could
 250     // be recursion so to avoid false alarm.
 251     return true;
 252   }
 253   if (CalleesInLoop.empty())
 254     return false;
 255
 256   TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl();
 257   CallGraph CG;
 258
 259   CG.addToCallGraph(TUDecl);
 260   // For each `SCC` containing `Func`, if functions in the `SCC`
 261   // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`.
 262   for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
 263                                        SCCE = llvm::scc_end(&CG);
 264        SCCI != SCCE; ++SCCI) {
 265     if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
 266       continue;
 267     // `SCC`s are mutually disjoint, so there will be no redundancy in
 268     // comparing `SCC` with the callee set one by one.
 269     if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl()))
 270       return true;
 271   }
 272   return false;
 273 }
 274
 275 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
 276   const auto LoopCondition = allOf(
 277       hasCondition(
 278           expr(forCallable(decl().bind("func"))).bind("condition")),
 279       unless(hasBody(hasDescendant(
 280           loopEndingStmt(forCallable(equalsBoundNode("func")))))));
 281
 282   Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
 283                          .with(LoopCondition)
 284                          .bind("loop-stmt"),
 285                      this);
 286 }
 287
 288 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
 289   const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
 290   const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
 291   const auto *Func = Result.Nodes.getNodeAs<Decl>("func");
 292
 293   if (isKnownToHaveValue(*Cond, *Result.Context, false))
 294     return;
 295
 296   bool ShouldHaveConditionVariables = true;
 297   if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
 298     if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
 299       if (const Expr *Init = LoopVarDecl->getInit()) {
 300         ShouldHaveConditionVariables = false;
 301         Cond = Init;
 302       }
 303     }
 304   }
 305
 306   if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *LoopStmt, *Result.Context))
 307     return;
 308
 309   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
 310     return;
 311   if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,
 312                                               Result.Context))
 313     return;
 314
 315   std::string CondVarNames = getCondVarNames(Cond);
 316   if (ShouldHaveConditionVariables && CondVarNames.empty())
 317     return;
 318
 319   if (CondVarNames.empty()) {
 320     diag(LoopStmt->getBeginLoc(),
 321          "this loop is infinite; it does not check any variables in the"
 322          " condition");
 323   } else {
 324     diag(LoopStmt->getBeginLoc(),
 325          "this loop is infinite; none of its condition variables (%0)"
 326          " are updated in the loop body")
 327       << CondVarNames;
 328   }
 329 }
 330
 331 } // namespace tidy::bugprone
 332 } // namespace clang