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