clang-tools 20.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
18using namespace clang::ast_matchers;
20
21namespace clang {
22namespace ast_matchers {
23/// matches a Decl if it has a "no return" attribute of any kind
24AST_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
30AST_MATCHER(FunctionType, typeHasNoReturnAttr) {
31 return Node.getNoReturnAttr();
32}
33} // namespace ast_matchers
34namespace tidy::bugprone {
35
36static internal::Matcher<Stmt>
37loopEndingStmt(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`.
53static 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`.
69static 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`.
107static 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`.
123static 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
142static 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.
176static 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`
200static 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.
217static 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.
239static 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
275void 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
288void 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
const FunctionDecl * Decl
CaptureExpr CE
::clang::DynTypedNode Node
DiagnosticBuilder diag(SourceLocation Loc, StringRef Description, DiagnosticIDs::Level Level=DiagnosticIDs::Warning)
Add a diagnostic with the check's name.
void check(const ast_matchers::MatchFinder::MatchResult &Result) override
ClangTidyChecks that register ASTMatchers should do the actual work in here.
void registerMatchers(ast_matchers::MatchFinder *Finder) override
Override this to register AST matchers with Finder.
AST_MATCHER(Decl, declHasNoReturnAttr)
matches a Decl if it has a "no return" attribute of any kind
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
static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var, ASTContext *Context)
Return whether Var was changed in LoopStmt.
static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx, bool ExpectedValue)
static internal::Matcher< Stmt > loopEndingStmt(internal::Matcher< Stmt > Internal)
static bool hasStaticLocalVariable(const Stmt *Cond)
returns true iff Cond involves at least one static local variable.
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.
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...
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 ...
static std::string getCondVarNames(const Stmt *Cond)
Return the variable names in Cond.
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.
bool hasPtrOrReferenceInFunc(const Decl *Func, const VarDecl *Var)
Returns whether Var has a pointer or reference in Func.
Definition: Aliasing.cpp:92
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//