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

source code of clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp